Using Roslyn APIs to build a .NET IL interpreter
Let us write our own IL interpreter that is capable of executing fibonacci series program
- By Pawan
- ·
- Insights
- .NET
- CSharp
Introduction to .NET
.NET is a free, cross-platform, and open source developer platform that lets you build a wide array of applications for web, mobile, desktop, games, and IoT. You can write these applications in C#, F#, or Visual Basic. Ultimately, .NET's runtime is used to execute your programs. This blog attempts to briefly explain how your code is executed and some of the technicalities involved. We'll also be writing our very own IL interpreter that is capable of executing a sample code.
What we will focus on
- Terms such as:
- Syntax Trees
- Intermediate Language (IL)
- Common Language Runtime (CLR)
- What Roslyn APIs are and how their emitter API can be of use to us.
- What CLR opcodes are and what they mean.
What we will not focus on
- Implementing the entirety of CLR's featureset.
- Type safety, optimizations, and other closely-related runtime features.
Sample code that we'll be executing
// fibonacci series
class Program
{
public static void Main()
{
var arr = new int[10];
arr[0] = 0;
arr[1] = 1;
for (var i = 2; i < 10; i++)
{
arr[i] = arr[i - 1] + arr[i - 2];
}
var fib9 = arr[9];
}
}
Prerequisites
What is static analysis
Static analysis is the technique of analyzing source code without executing it. Static analysis is what makes it possible to detect issues such as unused variables, unused methods, unreachable code, and dead code within your code without necessarily having to execute it. While compilers implement such analyses to some extent, dedicated tools do exist that can perform more in-depth analysis.
Turning source code into machine code
Compilers don't turn source code directly into something that the machine can understand. Rather, the source code has to go through certain phases to ensure that the optimal machine code is generated. The brief overview looks similar to:
Source code -> Syntax Tree -> IL (Intermediate Language) -> Machine code*.
Note: Certain runtimes and VMs turn a subset of IL into machine code on-demand. This is called JITting and is usually done for performance gains. While some JIT on demand, others turn IL directly into machine code.
Using Roslyn and MSBuild APIs to build sample source code
The .NET Compiler Platform SDK exposes APIs that facilitate static analysis and refactoring. These APIs expose information that is normally contained within the compilers and the compilation stages. We'll be using these APIs to:
- Open our sample code's
.csprojfile - Parse the code and obtain its syntax tree
- Emit the IL
- Execute this IL
Before we can go ahead and and compile our sample code, we'll have to create an MSBuild workspace and register its defaults. Doing so helps the MSBuild API locate a valid instance of the msbuild executable in the system.
MSBuildLocator.RegisterDefaults();
var workspace = MSBuildWorkspace.Create();
Once we're done with creating a workspace, we can open our project and obtain a compilation.
var project = await workspace.OpenProjectAsync(projectPath);
var compilation = await project.GetCompilationAsync();
The GetCompilationAsync() API returns a Compilation object that is an immutable representation of a single compiler invocation. Now that we're done invoking the compiler, we can write the IL to our destination. Rather than writing the IL to disk, it'd be wiser to emit it to a stream in our case.
var memoryStream = new MemoryStream();
var result = compilation.Emit(memoryStream);
The return value of Compilation.Emit() is an EmitResult, an object that specifies if the emit operation was successful and if it isn't, contains the required Diagnostics that help point out what went wrong. These diagnostics are similar to the compile time errors and warnings that you'd normally come across.
if (result.Success)
{
var assembly = Assembly.Load(memoryStream.ToArray());
}
else
{
// There was an error emitting the IL!
}
Common Language Runtime (CLR)
In .NET's case, the IL is called CIL (Common Intermediate Language) and is processed by the CLR (Common Language Runtime). Although the CLR has many features and performs many optimizations during execution, we're going to limit ourselves to interpretation.
Common Intermediate Language (CIL)
Each instruction in IL is called an opcode, which is shorthand for "operation code". Opcodes represent individual operations that the CLR understands how to perform. Some examples are add, sub, mul, and div. Most of these opcodes require operands. Operands are analogous to a function's parameters. The way opcodes may receive operands can differ according to the opcode.
Stack frame, locals array, and operand stack
Each method is executed within an environment that provides required information and support. This environment contains 2 important components called the "evaluation stack" and "local variable array". The evaluation stack is used by opcodes to push and pop operands while the local variable array is used to store these values. Any variables declared or classes instantiated occupy slots in the locals array following the first come first served policy.
public static void Method()
{
var i = 1; // Occupies slot `0`
var j = 2; // Occupies slot `1`
var k = new Class(); // Occupies slot `2`
}
Opcodes
Some opcodes that push operands to the operand stack are prefixed with "ld", shorthand for "load" and those that pop operands off the operand stack are prefixed with "st", which is short for "store" as they store values in the locals array.
The equivalent IL of:
public static void Method()
{
var i = 1;
var j = 2;
}
is:
// offset opcode clarifying comment
IL_0000 : nop // Do nothing. Either placed for debugging or alignment (cache) purposes.
IL_0001 : ldc.i4.1 // Push `1` as int32 (4 bytes, denoted by `ldc.i4`) to the operand stack.
IL_0002 : stloc.0 // Pop operand off the stack and store it in local array at pos `0`
IL_0003 : ldc.i4.2 // Push `2` as int32
IL_0004 : stloc.1 // Pop operand off the stack and store it in local array at pos `1`
IL_0005 : ret // End of method
You can use sharplab.io to view the IL that the compiler generates. Note that the generated IL depends on the compiler's version and the optimization level (debug vs release).
Opcodes and its variants
An opcode can be represented in the form of opcode.* where the * denotes that there exist various variants of the same opcode.
ldc.*- Push a numeric constant to the operand stack. Represented by hex values in the range[0x1A, 0x1F]and[0x15, 0x23].ldloc.*- Push element from the locals array onto the operand stack. Represented by hex values in the range[0x06, 0x09]and0x11.stloc.*- Pop element off the operand stack and store it in the locals array. Represented by hex values in the range[0x0A, 0x0D]and0x13.ldelem.*- Push element from an array (that is stored in the locals array) onto the operand stack. Represented by hex values in the range[0x90, 0x99],0x8F,0x9A, and0xA3.stelem.*- Pop element off the operand stack and store it in its respective array that in return is stored in the locals array. Represented by hex values in the range[0x9B, 0x9F],[0xA0, 0xA2], and0xA4.brtrue.*- Jump to the specified offset if the element on the stack is non-zero, i.e. true. Represented by the hex values0x2Dand0x3A.brfalse.*- Jump to the specified offset if the element on the stack is zero, i.e. false. Represented by the hex values0x2Cand0x39.
The entirety of a method's IL can be represented as an array of bytes, i.e. byte[]. Note that the opcode offsets maybe discontinuous due to presence of their operands. For example, if the opcode ldloc.s is at position 1 in the byte array, the next opcode is present at position 3 as ldloc.s requires 1 one-byte operand that specifies the local variable's index in the locals array. There are opcodes that take operands whose size is greater than 1 byte. In such cases, the operand is broken down into multiple byte-sized operands and inserted next to the opcode in the byte array.
You can view the entire opcode mappings here.
Since we're implementing only those instructions that we encounter in this post, we can use a simple switch block to execute the opcodes. This is more or less similar to what the runtime's feature interpreter actually does when executing a method.
RunMain() is responsible for calling Main() whereas ValidateMainMethod() is responsible for validating the Main() method's signature.
public void Run(byte[] cil, Stack<object> stack, object[] locals)
{
var i = 0;
while (i < cil.Length)
{
var opcode = cil[i];
switch (opcode)
{
// nop
// Do nothing
case 0x00:
i++;
break;
// ldloc.*
// Loads element at the specified position onto the op. stack.
case 0x06: // ldloc.0; Push element at pos `0` onto the op. stack.
case 0x07: // ldloc.1; Push element at pos `1` onto the op. stack.
case 0x08: // ldloc.2; Push element at pos `2` onto the op. stack.
case 0x09: // ldloc.3; Push element at pos `3` onto the op. stack.
{
stack.Push(locals[opcode - 0x06]);
i++;
break;
}
// stloc.*
// Pop element off the op. stack and store it in locals array.
case 0x0A: // stloc.0; pop and store at pos 0
case 0x0B: // stloc.1; pop and store at pos 1
case 0x0C: // stloc.2; pop and store at pos 2
case 0x0D: // stloc.3; pop and store at pos 3
{
var pos = opcode - 0x0A;
locals[pos] = stack.Pop();
// Move to the next instruction.
i++;
break;
}
// stloc.s
// Pop element off the op. stack and store it in locals array at position
// specified by the operand at `cil[i + 1]`.
case 0x13:
{
var pos = cil[i + 1];
locals[pos] = stack.Pop();
// Skip the operand at i + 1 and move to the next instruction that is
// placed at i + 2.
i += 2;
break;
}
// ldc.i4.*
// Push element specified by the opcode to the stack.
case 0x15: // ldc.i4.m1; Push -1 to the op. stack
case 0x16: // ldc.i4.0 ; Push 0 to the op. stack
case 0x17: // ldc.i4.1 ; Push 1 to the op. stack
case 0x18: // ldc.i4.2 ; Push 2 to the op. stack
case 0x19: // ldc.i4.3 ; Push 3 to the op. stack
case 0x1A: // ldc.i4.4 ; Push 4 to the op. stack
case 0x1B: // ldc.i4.5 ; Push 5 to the op. stack
case 0x1C: // ldc.i4.6 ; Push 6 to the op. stack
case 0x1D: // ldc.i4.7 ; Push 7 to the op. stack
case 0x1E: // ldc.i4.8 ; Push 8 to the op. stack
{
var val = opcode - 0x16;
stack.Push(val);
i++;
break;
}
// ret
// End of method.
case 0x2A:
return;
// brtrue.s
// Branch to the offset specified by `cil[i + 1]` if popped value is non-zero.
case 0x2D:
{
var val = (int) stack.Pop();
if (val != 0) // TODO: Verify
{
// Offset to jump is represented as 1 byte from the beginning of the instruction
// following the current instruction. This requires that we skip this instruction's
// operand as well. Hence, the `+2`.
i = i + 2 + (sbyte) cil[i + 1];
}
else
{
// Condition is not true. Skip `brtrue`'s operand and continue execution from the next
// instruction.
i += 2;
}
}
// math
// Pops 2 elements off the stack, performs the required math operation and pushes the result onto
// the operand stack.
//
// Assumption: We're only dealing with `int`s for now.
case 0x58: // add
case 0x59: // sub
{
var a = (int) stack.Pop();
var b = (int) stack.Pop();
var result = opcode switch
{
0x58 => a + b,
0x59 => a - b,
}
stack.Push(result);
i++;
break;
}
// newarr <etype>
// Creates a new array and pushes it onto the stack.
// Type of the array is determined by the operand following the `newarr` opcode.
//
// Assumption: We're only dealing with `int` arrays for now.
case 0x8D:
{
var len = (int) stack.Pop();
var arr = new int[len];
stack.Push(arr);
// The type of the array is specified by newarr's operand, `etype`, a metadata token.
// Since we're only dealing with an `int` array for now, we're going to ignore it.
i += 5;
break;
}
// stelem.i4
// Stores an `int` element at position `pos` in an array `arr`.
//
// Change in stack state:
// ..., val, pos, arr -> ...
case 0x9E:
{
var val = (int) stack.Pop();
var pos = (int) stack.Pop();
var arr = (int[]) stack.Pop();
arr[pos] = val;
i++;
break;
}
// clt
// Pops 2 `int`s from the stack and compares them.
// Pushes 1 onto the operand stack if value 2 is strictly lower than value 1, 0 otherwise.
case 0xFE when cil[i + 1] is 0x04:
{
var v1 = (int) stack.Pop();
var v2 = (int) stack.Pop();
stack.Push(v2 < v1 ? 1 : 0);
i += 2;
break;
}
default:
throw new NotImplementedException($"Opcode at pos {i} is not yet implemented");
} // switch
} // while
} // method
You can view the entire code here. Running Lungo through a debugger with a breakpoint set at the ret opcode confirms that we've indeed generated a valid Fibonacci series.
References
Ship clean and secure code.
