Writing a BF Compiler for .net (Part 2: Writing BF in C# and looking at the IL)

In the last posting, we looked at BF as a language and how to write an interpreter in C#. The point of doing that was to understand what each function actually does. As I am no IL Expert, my second step was to write the Hello World BF Application as C#, that is one extremely long function with each BF command spelled out. You can find the full function here. This is an Excerpt:

static void Main(string[] args)
{
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    memory[pointer]++;
    while(memory[pointer] > 0)
    {
        pointer++;
        memory[pointer]++;
        memory[pointer]++;
        memory[pointer]++;
        // snipped
    }
    // snipped
}

As you see, we literally translated each instruction into a C# instruction. Compile this in Debug Mode, load it up in ildasm:

Whoa, now were talking! Note that the ildasm will look different between Debug and Release modes due to optimizations. I prefer Debug to get an understanding how this works, and then later on Release mode to see the differences. The point is really to understand how this stuff looks in IL as we have to write IL ourselves later on.

So the first C# instruction is memory[pointer]++, which is a short way of saying memory[pointer] = memory[pointer] + 1. It is important that many language constructs and short-hand commands simply do not exist in IL - they are convenience functions in the C# compiler. Looking at the IL, our first C# instruction is now 9 IL instructions, starting from IL_0001 and ending at IL_0019.

  IL_0001:  ldsfld     uint8[] BFHelloWorldCSharp.Program::memory
  IL_0006:  ldsfld     int16 BFHelloWorldCSharp.Program::pointer
  IL_000b:  ldelema    [mscorlib]System.Byte
  IL_0010:  dup
  IL_0011:  ldobj      [mscorlib]System.Byte
  IL_0016:  ldc.i4.1
  IL_0017:  add
  IL_0018:  conv.u1
  IL_0019:  stobj      [mscorlib]System.Byte

Let's quickly look at each command before I explain in Detail what is happening:

1. Push the value of a static field 'memory' onto the evaluation stack.
2. Push the value of a static field 'pointer' onto the evaluation stack.
3. Load the address of the array element at a specified array index onto the top of the evaluation stack as type & (managed pointer).
4. Copy the current topmost value on the evaluation stack, and then pushes the copy onto the evaluation stack.
5. Copy the value type object pointed to by an address to the top of the evaluation stack.
6. Push the integer value of 1 onto the evaluation stack as an int32.
7. Add two values and pushes the result onto the evaluation stack.
8. Convert the value on top of the evaluation stack to unsigned int8, and extends it to int32.
9. Copy a value of a specified type from the evaluation stack into a supplied memory address.

That looks more complicated than it really is, especially if you don't know how CPUs usually work or never worked with Assembler. .net/IL is a Stack Based language, and functions work against this stack. For example, the Add instruction at address IL_0016 does not take parameters. Instead, it removes 2 elements from the stack, adds them, and pushes the result back to the stack. Be aware that most functions assume that the objects on the stack have the correct type - trying to push a string and an Int32 and calling Add will crash the CLR. Not all functions require their parameters on the stack, but many do - you can find an Overview of each function in Partition III of the ECMA-335 standard or in the OpCodes Fields.

Anyway, let's dissect the instruction and look at what's happening.
1. Getting memory[pointer]
In order to increment the value at memory[pointer], we first need to get it. This is the job of the ldelema instruction at IL_000a. To quote from the documentation:
Loads the address of the array element at a specified array index onto the top of the evaluation stack as type & (managed pointer).

So this function requires an array and an array index, and it gives us a managed pointer to that element. It expects that we push the array and the index to the stack (in that order). It will then pop (remove) these two elements from the stack and pushes the pointer back to the array.

The ldsfld function pushes the value of a static field onto the stack (pointer and memory were declared static). So we first push the memory array to the stack, and then the value of the pointer variable.

Here is a diagram:

2. Incrementing the value
Now we have a pointer to memory[pointer], but we need to increase it. That is what the next 4 instructions do. The important function is add at IL_0017, which takes two values from the stack and adds them. But at the moment, we only have the managed pointer on the stack. We first need to get the value of memory[pointer] to the stack. This is that ldobj at IL_0011 does: It gets the address of the value from the stack and pushes the actual value onto it. Note that this is now just a byte - it has no connection to the memory array, it is simply a number.

Before that, you might wonder what the dup instruction does: It simply creates a copy of the topmost value on the stack, effectively duplicating it. This might seem useless for the addition, but it is required later. For now, just ignore it.

Now that we have the current value of the memory[pointer], we need the second number to perform the addition. As ++ is just a shorthand for +1, we need to push the number 1 to the stack. To push an Int32 value to the stack, you can use the ldc.i4 instruction which pushes the supplied number to the stack. However, there are also shorthand commands for some numbers, and the command ldc.i4.1 pushes the number 1 to the stack. (I do not know if these commands exist for performance or for code size reasons, also I strongly believe the latter. ldc.i4.1 is a 1-byte command, whereas ldc.i4 requires 5 bytes: 1 for the command and 4 bytes for the Int32 value to push).

So now we have the current value of memory[pointer] and the number 1 on the stack, and the Add function pops them off, performs the addition and pushes the result.

A diagram for this part:

Just a slight note: The 1 at the end is not the same 1 as the one before. Add removes 0 and 1 from the stack, "generates a new 1" through performing 0 + 1 and pushes that to the stack.

3. Storing the value in the array again
We performed the addition, but as a result we simply have the number 1 on the stack now - memory[pointer] is still 0 though! The last two instructions take care of saving it back. Now, the number 1 on the stack is an Int32, but we have an array of Bytes. The first instruction, conv.u1 at IL_0018 gets a value off the stack, converts it to an unsigned 8-bit integer (which is exactly what a Byte in .net is), adds padding to Int32 and pushes it back to the stack. This might seem silly, but the evaluation stack only holds 4- or 8-byte integers (See Partition III, 1.1 Data Types of ECMA-335). The conv instruction makes sure that the actual data is stored in the "correct" bits (the ones later used to read the value), while the other 24 bits are merely padding to make it an Int32.

stobj copies the value to the desired memory location. You may now understand why we had the dup instruction at IL_0010: We need to know where to copy the value to, but the ldobj object removed the address from the stack already at IL_0011! So by duplicating the address, we can give it to both functions (otherwise we would have to do the lookup in the first three lines again).

And that is the memory[pointer]++ C# instruction in IL! I know it looks scary at first, but it's rather simple and logical once you understood how this stuff works internally. Remember, at some point each programming language needs to be translated into very specific CPU instructions. We are not at that level (this is what the CLR and it's JITter does), but we are at a fairly low level. Remember, we have to write a compiler for this, so we need to understand a) what is happening and b) why it is happening. Making those diagrams helped me a lot, especially because I didn't understand the use of the dup instruction at first.

Now that we know how this instruction works, we will look at the other 7 BF Instructions. I can already tell you how memory[pointer]-- works: It is exactly the same function, with the difference of using sub instead of add at IL_0017, so no need for an article of it's own.

The two pointer operations (pointer++ and pointer--) will be described in the next article.