Writing a BF Compiler for .net (Part 3: pointer++ and pointer–)

The last article gave an introduction to the concepts and we started looking at the memory[pointer]++/-- functions. Today is a quicky post to look at two other instructions, pointer++ and pointer-- or > and < in BF.

Unsurprisingly, these are extremely simple operations, requiring only 5 IL Commands:

  IL_0000:  ldsfld     int16 BFHelloWorldCSharp.Program::pointer
  IL_0005:  ldc.i4.1
  IL_0006:  add
  IL_0007:  conv.i2
  IL_0008:  stsfld     int16 BFHelloWorldCSharp.Program::pointer

ldsfld loads a static field onto the evaluation stack, ldc.i4.1 pushes the number 1 to the stack, add takes the two values from the stack and pushes the result back. conv.i2 converts the value on the stack (which is an Int32) to Int16 (2-Byte Int), pads it to be Int32 (as that is the smallest datatype possible on the stack) and pushes it back. stsfld then replaces the value in the static variable with the value from the stack.

As usual, pointer-- works the exact same way with the difference of using sub instead of add. One word of note: sub subtracts value2 from value1. While the order doesn't matter for add, it does for sub. Also note that add and sub do not detect overflow, so you can happily add 1 to Int16.MaxValue. If you want overflow checking, there is sub.ovf and add.ovf which throw an OverflowException.

With the 4 easy operations done, we will look at . and , next for input and output. Finally, we will look at [ and ]. After we have looked at the IL for each operation, we will write our compiler.

Comments (3)

KonradApril 19th, 2010 at 08:36

Seeing as `pointer` is actually the only value needed by BF (apart from the memory field), can’t you cut down on these five instructions? I’m wondering if it’s really necessary to store and load the value every time, instead of working exclusively on the stack.

Also, it would be interesting to see if this makes any difference performance-wise – conceivably, the JIT is smart enough to figure this out by itself and putting `pointer` into a register.

mstumApril 19th, 2010 at 10:30

I'm pretty sure it is possible to cut them down, especially since the current architecture is the one of a C# program. Compiler "optimizations" is something I have on my list. Not to the point where the compiler just executes the BF Code and only emits some Console.Write commands, but stuff like not needing a variable at all (Everything is in one method) and combining multiple equal operations. At the moment I'm leaving it overly verbose to show some concepts (BF is just a vessel to show how IL could work) and to later show possible differences between a Debug and Release build.

But thanks for the heads-up, it didn't occur to me that I don't even need a local variable at all as add/sub read from and push to the stack. Only the calls to Console.Read/Write could be a bit more complex.

[...] been through them in Part 3: Load the pointer value, add/subtract 1 from it, convert the result to an Int16, store it in the [...]