Dynamic C# Compilation

This is a sequal to my previous series on expression evaluation follows up what I talked about there. I recommend reading those articles first.

In my previous post, I determined that the fastest way to repeatedly evaluate a math expression given at runtime was to dynamically compile it, by parsing it into a tree and emitting opcodes. The sample code given in that post is functional, but hardly complete. Having every operation in a giant switch is not practical considering there are over 25 operations that I should be supporting. I need to refactor. I also need a way to enter paramters, so I can graph equations in x and y.

Here's the new version:

public static EvaluatorDelegate GetDynamicMethod(Tree<IToken> e, string[] parameters)
{
    DynamicMethod m = new DynamicMethod(
        "Evaluation" + DateTime.Now.ToString(),
        typeof(double),
        new Type[] { typeof(double[]) },
        typeof(Evaluator),
        false);
    ILGenerator il = m.GetILGenerator();

    LocalBuilder temp1 = il.DeclareLocal(typeof(double));

    foreach (IToken t in e.PostFix)
    {
        // Try op
        IOperator op = t as IOperator;
        if (op != null)
        {
            op.Emit(il);
            continue;
        }

        // Try number
        Number n = t as Number;
        if (n != null)
        {
            il.Emit(OpCodes.Ldc_R8, n.Value);
            continue;
        }

        // Try parameter
        Parameter p = t as Parameter;
        if (p != null)
        {
            // Check to see if we know which parameter that is.
            int pindex = Array.IndexOf<string>(parameters, p.Name);
            if (pindex < 0)
            {
                throw new ApplicationException(
                    "Did not receive information on parameter: " + p.ToString());
            }

            il.Emit(OpCodes.Ldarg_0);
            il.Emit(OpCodes.Ldc_I4, pindex);
            il.Emit(OpCodes.Ldelem_R8);

            continue;
        }

        throw new ApplicationException(
            "Invalid parse tree element: " + t.ToString());
    }

    il.Emit(OpCodes.Ret);

    EvaluatorDelegate del = (EvaluatorDelegate)m.CreateDelegate(
        typeof(EvaluatorDelegate));
    return del;
}

The first thing to notice is that the large operator switch has been replaced with some type switching. I have a base interface IOperator, which takes care of emitting its own opcodes.

Numbers are emitted the same as before—it just pushes them to the stack as a 64-bit floating-point type.

Parameters are handled through an array of doubles. The method now takes a parameter array which is used as a reference. To make this a bit easier to understand, I'll start with how this code is used:

EvaluatorDelegate del = GetDynamicMethod(tree, new string[] { "x", "y" });
double result = del(new double[] { x, y });

The delegate created by this method takes a double array whose elements correspond to the string array passed into GetDynamicMethod(). Looking at the code, when it finds a parameter, it checks the string array for the name of the parameter and saves that index. Then it loads the parameter value from the double array with the following:

il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Ldc_I4, pindex);
il.Emit(OpCodes.Ldelem_R8);

These opcodes push the double array (which is passed into the delegate as the first method argument) to the stack, followed by the desired index (found by searching the string array). The last opcode pops both of those and replaces them with the desired array element.

This could probably be improved by creating a delegate with an argument for each desired parameter. The DynamicMethod constructor takes a Type[] detailing these, so I could create that from the string array. This would remove the array indexing and reduce the opcodes to a single load—increasing performance. I'll do that later.

That's basically the only changes to this method. The nature of postfix notation—where an operator comes after its arguments, is exactly how .NET's CLR works. Assuming an expression is syntactically correct and parsed to a tree correctly, an operator is guaranteed to have its operands already on the stack by the time Emit() is called. Look at this implementation:

public class Addition : BaseOperator
{
    public override void Emit(System.Reflection.Emit.ILGenerator ilg)
    {
        ilg.Emit(OpCodes.Add);
    }
}

Painfully easy. Method calls are also possible:

public class Sine : BaseFunction
{
    public override void Emit(System.Reflection.Emit.ILGenerator ilg)
    {
        ilg.Emit(OpCodes.Call, typeof(System.Math).GetMethod("Sin"));
    }
}

Some are not quite as simple:

public class Secant : BaseFunction
{
    public override void Emit(System.Reflection.Emit.ILGenerator ilg)
    {
        ilg.Emit(OpCodes.Call, typeof(System.Math).GetMethod("Cos"));
        ilg.Emit(OpCodes.Stloc_0);
        ilg.Emit(OpCodes.Ldc_R8, 1.0D);
        ilg.Emit(OpCodes.Ldloc_0);
        ilg.Emit(OpCodes.Div);
    }
}

Secant is defined as 1/cos(x), so I evaluate cosine, then store that in the first local variable (this is the temp1 variable created above). I push 1 on the stack, followed by the temp1 variable, and divide. The Div opcode returns double.NaN when dividing by zero, so no error checking is required.