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!

kick it on DotNetKicks.com

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# Getting started with C# 3.0 Expression Trees

Wednesday, November 22, 2006 2:20 PM by B# .NET Blog

Somewhere in October this year, a series of three posts appeared online on this blog, covering "DynCalc"

# Getting started with C# 3.0 Expression Trees

Wednesday, November 22, 2006 2:29 PM by B# .NET Blog

Somewhere in October this year, a series of three posts appeared online on this blog, covering "DynCalc"

# DynCalc - Dynamic Compilation Illustrated - Part 4: C# 3.0 Expression Trees

Thursday, November 23, 2006 9:09 AM by B# .NET Blog

Introduction In the previous posts on DynCalc , we explored how to write a simple parser for simple calculations,