IL Reading

IL Reading

[Personal Note: This title is very stupid isn't it? :-), It alsmost makes you think about some magic or mental trickery a mind reading comes in mind when looking at the title, or perhaps I watch to much Derren Brown or something, anyways onwards to the post]

I was always fascinated how virtual machines were created and how they worked, so always when doing programming I wanted to push the boundary's of a language or platform and go beyond the sandbox that the designers intended to give us. Some of the most awesome projects were born this way for example Code Injection frameworks, Aspect Frameworks, Decompilers, Profilers etc.

So this time as a referral to my previous post about IL parsing this is committed to building a simple code to parse IL instructions, and hopefully change them at some point into code.

IL Parsing isn't that complex as long as you read the ECMA or find how the instructions are presented in a byte array. The basic is this that there are single byte and multi byte instructions (most of them used in code are single byte though), each instruction can have an operand (just like in assembly) that is one, two, three or four bytes long, to get the types that get called or fields pulled we need the Module class that can get the proper data in context.

The most basic way to get bytes is to use the framework build in method GetIlAsByteArray() but, that's not as effective as to just open the assembly and take out the instructions by brute force (since we can get additional data then), but that requires a whole lot more knowledge about the platform and it's a subject to change with each new version of the framework, so for the purpose of this post I will stick to the easy way.

Prerequisites

When getting the bytes and then reading them one would need to define some ByteBuffer class, but as I designed a DataStream class with simple modifications it can be used to do just that (I will post the extensions in my next post probably), but one could use anything that can read a byte array, and have a position index.

Building It

.
    public class IlReader
    {
        private DataStreams.DataStream stream;
        private OpCode[] singleByteOpCode;
        private OpCode[] doubleByteOpCode;
        private byte[] instrunctions;
        private IList<LocalVariableInfo> locals;
        private ParameterInfo[] parameters;
        private Type[] typeArgs = null;
        private Type[] methodArgs = null;
        private MethodBase currentMethod = null;
        private List<IlInstruction> ilInstructions = null;

        public IlReader()
        {
            CreateOpCodes();
        }

        private void CreateOpCodes()
        {
            singleByteOpCode = new OpCode[225];
            doubleByteOpCode = new OpCode[31];

            FieldInfo[] fields = GetOpCodeFields();

            for (int i = 0; i < fields.Length; i++)
            {
                OpCode code = (OpCode)fields[i].GetValue(null);

                if (code.OpCodeType == OpCodeType.Nternal)
                    continue;

                if (code.Size == 1)
                    singleByteOpCode[code.Value] = code;
                else
                    doubleByteOpCode[code.Value & 0xff] = code;
            }
        }

        public List<IlInstruction> ReadInstructions(MethodBase method)
        {
            ilInstructions = new List<IlInstruction>();
            this.currentMethod = method;

            locals = method.GetMethodBody().LocalVariables;
            instrunctions = method.GetMethodBody().GetILAsByteArray();

            IStreamObject streamObject = new ByteArrayObject(instrunctions);
            stream = new DataStreams.DataStream(streamObject, Encoding.UTF8);

            if (!(method.GetType() == typeof(ConstructorInfo)))
                methodArgs = method.GetGenericArguments();

            if (method.DeclaringType != null)
                typeArgs = method.DeclaringType.GetGenericArguments();

            IlInstruction instruction = null;

            while (stream.Position < stream.Length)
            {
                instruction = new IlInstruction();

                OpCode code = ReadOpCode();
                instruction.Operand = ReadOperand(code, method.Module);
                instruction.Name = code.Name;

                ilInstructions.Add(instruction);
            }

            return ilInstructions;
        }

        private object ReadOperand(OpCode code, Module module)
        {
            object operand = null;

            switch (code.OperandType)
            {   
                case OperandType.InlineNone:
                    break;
                case OperandType.InlineSwitch:
                    int length = stream.ReadInt32();
                    int[] branches = new int[length];
                    int[] offsets = new int[length];
                    for (int i = 0; i < length; i++)
                        offsets[i] = stream.ReadInt32();
                    for (int i = 0; i < length; i++)
                        branches[i] = (int)stream.Position + offsets[i];
                    break;
                case OperandType.ShortInlineBrTarget:
                    operand = (stream.ReadOneByte() + stream.Position);
                    break;
                case OperandType.InlineBrTarget:
                    operand = (stream.ReadInt32() + stream.Position);
                    break;
                case OperandType.ShortInlineI:
                    if (code == OpCodes.Ldc_I4_S)
                        operand = (sbyte)stream.ReadOneByte();
                    else
                        operand = stream.ReadOneByte();
                    break;
                case OperandType.InlineI:
                    operand = stream.ReadInt32();
                    break;
                case OperandType.ShortInlineR:
                    operand = stream.ReadFloat();
                    break;
                case OperandType.InlineR:
                    operand = stream.ReadDouble();
                    break;
                case OperandType.InlineI8:
                    operand = stream.ReadInt64();
                    break;
                case OperandType.InlineSig:
                    operand = module.ResolveSignature(stream.ReadInt32());
                    break;
                case OperandType.InlineString:
                    operand = module.ResolveString(stream.ReadInt32());
                    break;
                case OperandType.InlineTok:
                case OperandType.InlineType:
                case OperandType.InlineMethod:
                case OperandType.InlineField:
                    operand = module.ResolveMember(stream.ReadInt32()
                        , typeArgs, methodArgs);
                    break;
                case OperandType.ShortInlineVar:
                    operand = GetVariable(code, stream.ReadOneByte());
                    break;
                case OperandType.InlineVar:
                    operand = GetVariable(code, stream.ReadUInt16());
                    break;
                default:
                    throw new NotSupportedException();
            }

            return operand;
        }

        private OpCode ReadOpCode()
        {
            byte instruction = stream.ReadOneByte();
            if (instruction != 254)
                return singleByteOpCode[instruction];
            else
                return doubleByteOpCode[stream.ReadOneByte()];
        }

        private object GetVariable(OpCode code, int index)
        {
            if (code.Name.Contains("loc"))
                return locals[index];

            if (!currentMethod.IsStatic)
                index--;

            return parameters[index];
        }

        private FieldInfo[] GetOpCodeFields()
        {
            return typeof(OpCodes).GetFields(BindingFlags.Public 
                | BindingFlags.Static);
        }
    }

That's all of the code to read the instructions from a method, but a few words of explanation is needed here, so lets take it apart method by method.

CreateOpCodes:

here we construct two arrays of possible op codes using the NET build in OpCode structure and we construct the arrays by checking the code size and putting it in the proper one. Larger instructions have minus values starting from -512 counting down so the [code.Value & 0xff] is just used to put those in the correct place in the array meaning from 0 to 30.

ReadInstructions:

This is the main method of the show here, and here we take out the byte array from the method body and take out the module and read the op code from the array and if the read byte is higher then 254 then we are dealing with multi byte instruction thus we read once more.

When having the proper OpCode all we need to do now is to determine it's operand.

ReadOperand:

Based on the operand type we just read the proper byte size to determine the operand value, the [I]type instructions are for ints the [R]type are floating point instructions, for branch types we just take the bytes depending on the type of the branch and add the stream position, the only difference from that rule is the inline switch where we have to keep track of the branches and offsets, and our operand represents the branch array. Another kind of operands are member calls and signatures where we need to use the module that we provided and resolve those operands in the proper metadata context. The very last type of operands are local operands where we need to resolve the indexes of locals taking into consideration is the method is static or not, as static methods don't have [this] pointer, the index will be smaller by one.

The rest of the methods are somewhat self explanatory so I won't cover them as this would be a waste of time :-), now that we have this little code time to test it out against ILdasm to see if it works.

Code

For the code I used the same class that I just posted here as it's more advanced than some simple test method, and if the complex example will pass so will the simple ones.

.
            var method = typeof(IlReader).GetMethod("ReadOpCode", BindingFlags.NonPublic 
            | BindingFlags.Instance);

            IlReader rdr = new IlReader();
            StringBuilder builder = new StringBuilder();

            foreach (var code in rdr.ReadInstructions(method))
            {
                builder.AppendLine(code.Name + " " + code.Operand);
            }

            Console.Write(builder.ToString());

And now let's compare the ILs of those two.

ILDasm

IL_0000:  nop
  IL_0001:  ldarg.0
  IL_0002:  ldfld      class [DataStream]DataStreams.DataStream ConsoleApplication1.IlReader::'stream'
  IL_0007:  callvirt   instance uint8 [DataStream]DataStreams.DataStream::ReadOneByte()
  IL_000c:  stloc.0
  IL_000d:  ldloc.0
  IL_000e:  ldc.i4     0xfe
  IL_0013:  ceq
  IL_0015:  stloc.2
  IL_0016:  ldloc.2
  IL_0017:  brtrue.s   IL_002d
  IL_0019:  ldarg.0
  IL_001a:  ldfld      valuetype [mscorlib]System.Reflection.Emit.OpCode[] ConsoleApplication1.IlReader::singleByteOpCode
  IL_001f:  ldloc.0
  IL_0020:  ldelema    [mscorlib]System.Reflection.Emit.OpCode
  IL_0025:  ldobj      [mscorlib]System.Reflection.Emit.OpCode
  IL_002a:  stloc.1
  IL_002b:  br.s       IL_004b
  IL_002d:  ldarg.0
  IL_002e:  ldfld      valuetype [mscorlib]System.Reflection.Emit.OpCode[] ConsoleApplication1.IlReader::doubleByteOpCode
  IL_0033:  ldarg.0
  IL_0034:  ldfld      class [DataStream]DataStreams.DataStream ConsoleApplication1.IlReader::'stream'
  IL_0039:  callvirt   instance uint8 [DataStream]DataStreams.DataStream::ReadOneByte()
  IL_003e:  ldelema    [mscorlib]System.Reflection.Emit.OpCode
  IL_0043:  ldobj      [mscorlib]System.Reflection.Emit.OpCode
  IL_0048:  stloc.1
  IL_0049:  br.s       IL_004b
  IL_004b:  ldloc.1
  IL_004c:  ret

ILReader

nop 
ldarg.0 
ldfld DataStreams.DataStream stream
callvirt Byte ReadOneByte()
stloc.0 
ldloc.0 
ldc.i4 254
ceq 
stloc.2 
ldloc.2 
brtrue.s 45
ldarg.0 
ldfld System.Reflection.Emit.OpCode[] singleByteOpCode
ldloc.0 
ldelema System.Reflection.Emit.OpCode
ldobj System.Reflection.Emit.OpCode
stloc.1 
br.s 75
ldarg.0 
ldfld System.Reflection.Emit.OpCode[] doubleByteOpCode
ldarg.0 
ldfld DataStreams.DataStream stream
callvirt Byte ReadOneByte()
ldelema System.Reflection.Emit.OpCode
ldobj System.Reflection.Emit.OpCode
stloc.1 
br.s 75
ldloc.1 
ret

As can be seen the code is identical regarding the instructions and operands, it's missing addresses and other operand data but other than that it's identical, the missing data can be also read btw.

Ending Words

The next big thing would be to parse those instructions and create C# code from it, but for this we would need to write a C# parser and that a lot harder to do properly and requires lot's or work and tears, but ultimately it would be 1000% more awesome so maybe if I will find the time I will take a stab at it, but then again Mono Cecil is in advanced stages of building a IL to C# parser so even better way of doing it would be to commit to that existing code base.

Reflector Is Not Free

Reflector Is Not Free

This is just terrible news, I used this tool when since it's beginnings then after Red Gate took over. I used this tool to fix bugs in framework codes itself! by doing better implementations and mostly to study and to see how things are designed. One time I even pointed out bugs in a library that was bought by the company I worked for and proposed a fix :-).

And now Red Gate is trying to make money on a tool that they acquired form a Developer that intended to be free, the price is set at 35$ and I think that this is to high, because they promised that it will be free, so we need to pay for broken promises.

So what would be the best way to get out of this mess is to charge just for the new version and leave the old ones, but they are now time bombed!, so Red Gate should opensource V6 of reflector and continue to charge for the newer ones, this is the best possible way to get out of this PR mess.

Building our own

By looking at the Red Gates forums people are pretty pissed and upset about all of this. This could lead to creation of some sort of community project to create an open source decompiler for .NET, I'm kinda thinking about it, so count me in.

Getting the Instructions from code is simple task, we just need to call GetILAsByteArray(), and then parse the bytes in proper context as the the instruction byte is followed by 1,2,3 or 4 byte metadata token and then get the MethodInfo.Module to get the proper object if needed, but the true challenge here is to parse the IL code into language syntax, but this is nothing that can't be done.

Summary

I wish that Red Gate would do the right thing and open source the project but I have a feeling that this will not be so and the only reliable solution will be to create another Reflector project and open source it from the start, besides the knowledge gained and the factor of teaching a lesson is priceless :-).

IL In depth look

IL In depth Look

This is next in the series of IL programming, facts, and cool stuff thats happening there, that's totally useless if you are doing a day to day job and probably some website, but it's good to know how things work on the byte code level to get a grater understanding of the platform and write better code and do some IL level optimalisations when needed.

Lets Start.

Right so normally when you have such a simple code like this:

class Program
    {
        static void Main(string[] args)
        {
            Console.Write("I was called from " + 
                MethodInfo.GetCurrentMethod().Name);
            Console.ReadKey();
        }

        static void Test(string[] args)
        {
            Console.Write("I was called from " + 
                MethodInfo.GetCurrentMethod().Name);
            Console.ReadKey();
        }
    }

the entry point is always main, normally you can change it in visual studio or by compiling the code with csc.exe, but how is this possible to change entry points exactly? If you look at the IL of the code you will see something like this.

.class private auto ansi beforefieldinit ConsoleApplication.Program
       extends [mscorlib]System.Object
{
  .method private hidebysig static void  Main(string[] args) cil managed
  {
   
    // Code size       34 (0x22)
    .maxstack  8
    IL_0000:  nop
    IL_0001:  ldstr      "I was called from"
    IL_0006:  call       class [mscorlib]System.Reflection.MethodBase
                             [mscorlib]System.Reflection.MethodBase::GetCurrentMethod()
    IL_000b:  callvirt   instance string [mscorlib]System.Reflection.MemberInfo::get_Name()
    IL_0010:  call       string [mscorlib]System.String::Concat(string,
                                                                string)
    IL_0015:  call       void [mscorlib]System.Console::Write(string)
    IL_001a:  nop
    IL_001b:  call       valuetype [mscorlib]System.ConsoleKeyInfo 
                             [mscorlib]System.Console::ReadKey()
    IL_0020:  pop
    IL_0021:  ret
  } // end of method Program::Main

  .method private hidebysig static void  Test(string[] args) cil managed
  {
    .entrypoint
    // Code size       34 (0x22)
    .maxstack  8
    IL_0000:  nop
    IL_0001:  ldstr      "I was called from"
    IL_0006:  call       class [mscorlib]System.Reflection.MethodBase 
                            [mscorlib]System.Reflection.MethodBase::GetCurrentMethod()
    IL_000b:  callvirt   instance string [mscorlib]System.Reflection.MemberInfo::get_Name()
    IL_0010:  call       string [mscorlib]System.String::Concat(string,
                                                                string)
    IL_0015:  call       void [mscorlib]System.Console::Write(string)
    IL_001a:  nop
    IL_001b:  call       valuetype [mscorlib]System.ConsoleKeyInfo 
                             [mscorlib]System.Console::ReadKey()
    IL_0020:  pop
    IL_0021:  ret
  } // end of method Program::Test

  .method public hidebysig specialname rtspecialname 
          instance void  .ctor() cil managed
  {
    // Code size       7 (0x7)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  call       instance void [mscorlib]System.Object::.ctor()
    IL_0006:  ret
  } // end of method Program::.ctor

} // end of class ConsoleApplication.Program

In this code the ".entrypoint" is responsible for setting the startup method on the code, in this case I changed it to Test, so the app will start from that place.

This simple piece of IL code has lot's of interesting properties besides the application's entrypoint, that are worth to look like:

.maxstack that informs JIT what is the maximum size of the stack for the method, but as far as I know this is just informal and it's not used in the standard implemenatation of the VM.

specialname that is an informal field and informs about static methods/fields, marshaling and some internal operations in the framework.

.hidebysig  that hides by name and signature, that basically means that you can call the base method form the derived class that has the same method name with different parameters, because the derived method does't hide the base one, so just by deleting this parameter different behavior can be enforced.

This concludes this part of my post, I will be writing more on the IL topic when I find something cool and do some research on it, this is not an easy topic but that makes it exciting and interesting :-)

IL Tweaks

IL Tweaks Part2


first part can be found here.

This time around the code example can be called a jigsaw then a real functional code, but it will show some very important code optimization that can be made in C#, a little tip is that F# uses this technique when generating IL code, so this might ring some bells to those that program in F# :-).

Let's jump straight to code, so consider the following:

public static T f1<T>(int n)
{
    return f2<T>(n + 1);
}

public static T f2<T>(int n)
{
    return f1<T>(n + 1);
}

When we run the code calling either of those two methods, we will get stack overflow exception, as recurrence calls are using a local stack where the local data of the function call is stored, but as you can see here it will go to infinity and our stack just can't handle infinity, thus resulting in a exception. Another thing of the stack based recurrence is that it's slow.

Let The Magic Begin

Ok so now let's decompile the code (my exe was on C):

ildasm C:\Test.exe /out=C:\test.il

So now lets locate our methods part in IL, and see how can we make it work without exceptions.

.method public hidebysig static !!T f1(int32 n) cil managed
{
// Code size 9 (0x9)
.maxstack 8
IL_0000: ldarg.0
IL_0001: ldc.i4.1
IL_0002: add
IL_0003: call !!0 ConsoleApplication2.Program::f2(int32)
IL_0008: ret
} // end of method Program::f1

.method public hidebysig static !!T f2(int32 n) cil managed
{
// Code size 9 (0x9)
.maxstack 8
IL_0000: ldarg.0
IL_0001: ldc.i4.1
IL_0002: add
IL_0003: call !!0 ConsoleApplication2.Program::f1(int32)
IL_0008: ret
} // end of method Program::f2


The key thing here is something thats called a Tail call. Normally a recursive call is a stack based, meaning it is stored in a stack, but with tall calls it isn't the subroutine can be considered a jump call, so there is no exception as the code will jump from place to place and never use up the stack. With tail calls a recursive problem can be just as fast as non recursive or sometimes even faster, building up sequences can be an excellent example.


To make a tail call add a "tail." opcode in both methods here:

IL_0002: add
tail.
IL_0003: call ...
IL_0008: ret

and assemble the code.


ilasm C:\test.il /out=C:\TestTail.exe


Now when you run the code, you will not get any exceptions, meaning that the tail call works as it should.

Now why C# compiler doesn't use this feature? This probably due the backwards capability, but I can't be sure of this, but it's possible as the newer languages on the NET platform make use of this feature. One language that uses tail calls is F# but in this exact example tail calls will not be used, because F# compiles is kinda 'smart' and will use other techniques of optimization.

The F# Way


When I tried this example in F# I did get an compile time exception.

let rec f1 n = f2(n+1);
let rec f2 n = f1(n+1);

"The value or constructor 'f2' is not defined".

So it would seam that such scenario is impossible in the first place, but then again this would mean a big limitation in some subset of scenarios. So i goggled around and found that in F# there is a special syntax for that.

let rec f1 n = 
    f2 (n+1)
and f2 n = 
    f1 (n+1)

Now it would seam that F# will use a tail call here, but no. I'm not going to get into IL this time as it's bigger this time around, but instead we will look, what code the compiler generated in C# using the reflector or some other disassembler.

public static a f1<a>(int n)
{
    return f2<a>(n + 1);
}

public static a f2<a>(int n)
{
    while (true)
    {
        int num = n + 1;
        n = num + 1;
    }
}

As you see the code is actually a infinite loop, so we could say that the F# compiler is smart enough to detect that, and generate the best possible code.

Concluding


Tail calls can be a game changer when dealing with recursive problems, like tree parsing etc, I can think of at least of two such problems I had to do in my previous jobs that would fit tail calling just fine, so if you are dealing with a lot of recursion you might want to check that out.

IL Tweaks

IL Tweaks


Normally NET developers don't have to know about IL and some of I know don't even want to, as this is a stack language that's close to asm, except that the register logic is hidden away and the constructs are simpler. But sometimes it's good to know what the compiler generates because numerous times out of backwards capability the generated code is not the fastest it can be, and it's good to know what to avoid.

There are numerous tweaks that can be made, like the new() constraint in generics, but one thing I would like to focus on is code branching and local copying of stack variables, consider the flowing code:

public int Method()
{
    int i = 0;
    i++;
    return i;
}

Show Me The Hardcore:

Then let's use IL dasm to get out the opcodes:

ildasm Test.exe /out:test.il


Our IL code looks like this:

.method public hidebysig instance int32
          Method() cil managed
  {
    // Code size       13 (0xd)
    .maxstack  2
    .locals init (int32 V_0,
             int32 V_1)
    IL_0000:  nop
    IL_0001:  ldc.i4.0
    IL_0002:  stloc.0
    IL_0003:  ldloc.0
    IL_0004:  ldc.i4.1
    IL_0005:  add
    IL_0006:  stloc.0
    IL_0007:  ldloc.0
    IL_0008:  stloc.1
    IL_0009:  br.s       IL_000b

    IL_000b:  ldloc.1
    IL_000c:  ret
  } // end of method Program::Method

At this point there are two that are interesting, the first one is the br.s this opcode states that a branch is always true and it jumps to a given label and in this case this is simply the next instruction. Ans as you may know branching code is expensive. The next thing that you see is that there are two locals declared, although we have only one local in our C# code.

The code part:

IL_0008:  stloc.1

IL_0009:  br.s       IL_000b

IL_000b:  ldloc.1

in the context of your method can be skipped, as we only do a local copy of variable we incremented, why make a copy and a branch that always points to the next instruction? Now I cannot guarantee that this will work in all situations (removing the local copy), but i'm certain that deleting br.s will work every time.

So if we delete the local declaration along with the opcodes that we pointed out, we will speed up the method execution time, to compile our new IL we use the following:

ilasm test.il /out:test.exe

Conclusion:

This is not going to be a big performance improvement over this sample method but if you take into consideration a more complex method and identify the places where it could be optimized via IL then there should be a noticeable effect.