Using Roslyn APIs to build a .NET IL interpreter

November 9, 2022

Using Roslyn APIs to build a .NET IL interpreter

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.

A brief overview of turning source code into machine code — A simplified view of how source code is turned 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 .csproj file
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.

A method's frame depicting locals array and operand stack — A simplified view of a method's stack frame

 
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] and 0x11.
stloc.* - Pop element off the operand stack and store it in the locals array. Represented by hex values in the range [0x0A, 0x0D] and 0x13.
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, and 0xA3.
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], and 0xA4.
brtrue.* - Jump to the specified offset if the element on the stack is non-zero, i.e. true. Represented by the hex values 0x2D and 0x3A.
brfalse.* - Jump to the specified offset if the element on the stack is zero, i.e. false. Represented by the hex values 0x2C and 0x39.

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.

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.