Friday, October 13, 2006 4:38 PM
bart
DynCalc - Dynamic compilation illustrated - Part 3: Compilation to IL
Introduction
Welcome back in this series of dynamic compilation posts. Today, we'll transform our expression tree into IL code. To set our minds, take a look at the following expression tree:
+Sub
+Mul
+Add
+Add
1
2
3
2
+Div
8
4
This has to be translated into something like:
ldc.i4.s 1
ldc.i4.s 2
add
ldc.i4.s 3
add
ldc.i4.s 2
mul
ldc.i4.s 8
ldc.i4.s 4
div
add
This is what we're going to do in today's post.
The code
Recall our expression tree is represented as a single TreeNode obtained by calling
static TreeNode ToTree(Queue<MathOpOrVal> q)
IL is a stack-based language, so we need to convert this tree back into a stack-based representation. E.g. to add 1 and 2, the code should look like:
ldc.i4.s 1
ldc.i4.s 2
add
yielding to the following stack transformations:
2
1 1 3
So, some stack-building method seems appropriate:
private static void BuildStack(Stack<MathOpOrVal> stack, TreeNode root)
{
if (root.Op != null)
{
MathOpOrVal e = new MathOpOrVal(root.Op.Value);
stack.Push(e);
BuildStack(stack, root.Right);
BuildStack(stack, root.Left);
}
else
{
MathOpOrVal e = new MathOpOrVal(root.Value.Value);
stack.Push(e);
}
}
static void BuildStack(Stack<MathOpOrVal> stack, TreeNode root)
{
if (root.Op != null)
{
MathOpOrVal e = new MathOpOrVal(root.Op.Value);
stack.Push(e);
BuildStack(stack, root.Right);
BuildStack(stack, root.Left);
}
else
{
MathOpOrVal e = new MathOpOrVal(root.Value.Value);
stack.Push(e);
}
} Given some tree node (called "root"), a stack is built (passed as the first parameter). If the tree node represents an operation (add, sub, mul, div), that operation is pushed on the stack. Next, the right-hand side of the stack is traversed recursively, followed by the left-hand side. If the tree node represents a value, the value is just pushed on the stack.
(1+2)+3 ==> +Add ==> 3 ==> 2
+Add add 1
1 add
2 3
3 add
Next, the translation to IL:
private static int i = 0; private static int Execute(TreeNode root)
{
DynamicMethod method = new DynamicMethod(
"Exec_" + i++,
typeof(int),
new Type[] { },
typeof(Program).Module
);
ILGenerator gen = method.GetILGenerator();
Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
BuildStack(stack, root);
while (stack.Count > 0)
{
MathOpOrVal e = stack.Pop();
if (e.Op != null)
{
switch (e.Op)
{
case MathOp.Add:
Debug.WriteLine("add");
gen.Emit(OpCodes.Add);
break;
case MathOp.Sub:
Debug.WriteLine("sub");
gen.Emit(OpCodes.Sub);
break;
case MathOp.Mul:
Debug.WriteLine("mul");
gen.Emit(OpCodes.Mul);
break;
case MathOp.Div:
Debug.WriteLine("div");
gen.Emit(OpCodes.Div);
break;
}
}
else
{
Debug.WriteLine("ldc " + e.Value.Value);
gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
}
}
gen.Emit(OpCodes.Ret);
return (int)method.Invoke(
null,
BindingFlags.ExactBinding,
null,
new object[] { },
null
);
}
private static int Execute(TreeNode root)
{
DynamicMethod method = new DynamicMethod(
"Exec_" + i++,
typeof(int),
new Type[] { },
typeof(Program).Module
);
ILGenerator gen = method.GetILGenerator();
Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
BuildStack(stack, root);
while (stack.Count > 0)
{
MathOpOrVal e = stack.Pop();
if (e.Op != null)
{
switch (e.Op)
{
case MathOp.Add:
Debug.WriteLine("add");
gen.Emit(OpCodes.Add);
break;
case MathOp.Sub:
Debug.WriteLine("sub");
gen.Emit(OpCodes.Sub);
break;
case MathOp.Mul:
Debug.WriteLine("mul");
gen.Emit(OpCodes.Mul);
break;
case MathOp.Div:
Debug.WriteLine("div");
gen.Emit(OpCodes.Div);
break;
}
}
else
{
Debug.WriteLine("ldc " + e.Value.Value);
gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
}
}
gen.Emit(OpCodes.Ret);
return (int)method.Invoke(
null,
BindingFlags.ExactBinding,
null,
new object[] { },
null
);
}
private static int Execute(TreeNode root)
{
DynamicMethod method = new DynamicMethod(
"Exec_" + i++,
typeof(int),
new Type[] { },
typeof(Program).Module
);
ILGenerator gen = method.GetILGenerator();
Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
BuildStack(stack, root);
while (stack.Count > 0)
{
MathOpOrVal e = stack.Pop();
if (e.Op != null)
{
switch (e.Op)
{
case MathOp.Add:
Debug.WriteLine("add");
gen.Emit(OpCodes.Add);
break;
case MathOp.Sub:
Debug.WriteLine("sub");
gen.Emit(OpCodes.Sub);
break;
case MathOp.Mul:
Debug.WriteLine("mul");
gen.Emit(OpCodes.Mul);
break;
case MathOp.Div:
Debug.WriteLine("div");
gen.Emit(OpCodes.Div);
break;
}
}
else
{
Debug.WriteLine("ldc " + e.Value.Value);
gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
}
}
gen.Emit(OpCodes.Ret);
return (int)method.Invoke(
null,
BindingFlags.ExactBinding,
null,
new object[] { },
null
);
}
static int i = 0; private static int Execute(TreeNode root)
{
DynamicMethod method = new DynamicMethod(
"Exec_" + i++,
typeof(int),
new Type[] { },
typeof(Program).Module
);
ILGenerator gen = method.GetILGenerator();
Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
BuildStack(stack, root);
while (stack.Count > 0)
{
MathOpOrVal e = stack.Pop();
if (e.Op != null)
{
switch (e.Op)
{
case MathOp.Add:
Debug.WriteLine("add");
gen.Emit(OpCodes.Add);
break;
case MathOp.Sub:
Debug.WriteLine("sub");
gen.Emit(OpCodes.Sub);
break;
case MathOp.Mul:
Debug.WriteLine("mul");
gen.Emit(OpCodes.Mul);
break;
case MathOp.Div:
Debug.WriteLine("div");
gen.Emit(OpCodes.Div);
break;
}
}
else
{
Debug.WriteLine("ldc " + e.Value.Value);
gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
}
}
gen.Emit(OpCodes.Ret);
return (int)method.Invoke(
null,
BindingFlags.ExactBinding,
null,
new object[] { },
null
);
}
private static int Execute(TreeNode root)
{
DynamicMethod method = new DynamicMethod(
"Exec_" + i++,
typeof(int),
new Type[] { },
typeof(Program).Module
);
ILGenerator gen = method.GetILGenerator();
Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
BuildStack(stack, root);
while (stack.Count > 0)
{
MathOpOrVal e = stack.Pop();
if (e.Op != null)
{
switch (e.Op)
{
case MathOp.Add:
Debug.WriteLine("add");
gen.Emit(OpCodes.Add);
break;
case MathOp.Sub:
Debug.WriteLine("sub");
gen.Emit(OpCodes.Sub);
break;
case MathOp.Mul:
Debug.WriteLine("mul");
gen.Emit(OpCodes.Mul);
break;
case MathOp.Div:
Debug.WriteLine("div");
gen.Emit(OpCodes.Div);
break;
}
}
else
{
Debug.WriteLine("ldc " + e.Value.Value);
gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
}
}
gen.Emit(OpCodes.Ret);
return (int)method.Invoke(
null,
BindingFlags.ExactBinding,
null,
new object[] { },
null
);
} The first few lines are self-explanatory:
DynamicMethod method = new DynamicMethod(
"Exec_" + i++,
typeof(int),
new Type[] { },
typeof(Program).Module
);
ILGenerator gen = method.GetILGenerator();
A dynamic method is created in the current module, with some unique name (I'm using a simple int counter in case more than one expression-to-IL translation would be required). The second and third parameter to the DynamicMethod constructor call specify the return type (int) and the input parameter types (none). The last parameter specifies the target module where to put the generated method and its IL. Finally, an IL generator is created for the method. This is used to spit out the required IL.
Next, we obtain our stack that's ready for a one-on-one mapping to IL instructions:
Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
BuildStack(stack, root);
And finally, IL generatio starts by popping elements from the stack, investigating them and finding out about the required IL instruction:
gen.Emit(OpCodes.Add);
gen.Emit(OpCodes.Sub);
gen.Emit(OpCodes.Mul);
gen.Emit(OpCodes.Div);
gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
OpCodes.Ldc_I4, e.Value.Value); Take a look at the OpCodes documentation for more information about available opcodes (a bunch!).
Finally, a ret statement is emitted and the method is called using Invoke:
gen.Emit(OpCodes.Ret);
return (int)method.Invoke(
null,
BindingFlags.ExactBinding,
null,
new object[] { },
null
);
For our sample input, output should be 10:
Dynamic calculation: Result = 10
Fitting the pieces together
Here's the Main method that brings together all of this:
static void Main(string[] args)
{
Console.WriteLine("Dynamic calculator");
Console.WriteLine("------------------");
Console.WriteLine();
Console.Write("Expression: ");
string expr = Console.ReadLine();
Queue<MathOpOrVal> q = Expression.InfixToPostfix(expr);
Console.WriteLine();
Console.Write("Postfix representation: ");
Print(q);
Console.WriteLine();
Console.WriteLine("Tree representation:");
TreeNode tree = ToTree(q);
Print(tree);
Console.WriteLine();
Console.Write("Dynamic calculation: ");
Console.WriteLine("Result = {0}", Execute(tree));
}
void Main(string[] args)
{
Console.WriteLine("Dynamic calculator");
Console.WriteLine("------------------");
Console.WriteLine();
Console.Write("Expression: ");
string expr = Console.ReadLine();
Queue<MathOpOrVal> q = Expression.InfixToPostfix(expr);
Console.WriteLine();
Console.Write("Postfix representation: ");
Print(q);
Console.WriteLine();
Console.WriteLine("Tree representation:");
TreeNode tree = ToTree(q);
Print(tree);
Console.WriteLine();
Console.Write("Dynamic calculation: ");
Console.WriteLine("Result = {0}", Execute(tree));
} We're done:
You can download the code here (includes support for the mod, rem, % operator too). Enjoy!
Del.icio.us |
Digg It |
Technorati |
Blinklist |
Furl |
reddit |
DotNetKicks
Filed under: .NET Framework v2.0, C# 2.0