Tagged: compiler

Build an interpeter in .NET

A long while ago I noted one could build an efficient language interpreter if the runtime could inline operations more aggressively. .NET has long had an attribute called MethodImplAttribute that gives the runtime some hints on how to compile a method. In .NET 4.5 they added one more hint: AggressiveInlining. This instructs the JIT to inline the method if possible. It took some doing, but I verified that it does inline methods most of the time. This post talks more about it. Plus, at the bottom is a comment from (probably) a .NET dev that says, “It simply turns off all our heuristics, and causes us to inline the method if the JIT is capable of inlining the method. The reason the documentation is so vague is that there are limitations to what the JIT can actually inline…”. So it works, but it might not sometimes.

To determine if inlining is working you can scan the ETW output from the JIT as described here. I did the following:

// Run wevtutil only once on your machine. It should work fine forever after. :)
wevtutil im C:\Windows\Microsoft.NET\Framework\v4.0.30319\CLR-ETW.man
// Do the following each time.
logman start clrevents -p {e13c0d23-ccbc-4e12-931b-d9cc2eee27e4} 0x1000 5 -ets
logman stop clrevents -ets
tracerpt clrevents.etl

Search in dumpfile.xml for MethodJitInliningSucceeded and MethodJitInliningFailed. They will give you a reason for what it chose to do. To make this a bit easier you might be able to use Reactive Extensions to monitor the logfile as described here.

The goal is to inline and optimize the interpreter directly into the program, thus creating a compiled program. This is the first Futamura projection. This is already pretty good, but to get the 2nd and 3rd projections you’d need to do the inlining at the bytecode level at compile time, not at runtime. That way you can save the optimized assembly and specialize again. This should exist somewhere. I couldn’t find anything comparable in the JVM. Perhaps LLVM? Maybe Rosyln?


Compiler generator using method inlining

It should be possible to write a language interpreter on top of Java or .NET and rely on method inlining to instantly get compiled code. Implement most of your interpreter opcodes as small static methods: Add, Subtract, LessThan, etc. Translate your language into Java/C# methods that call these opcodes. When the JIT sees all these small static methods, it should inline and optimize them. Presto! You’ve just written a compiler. It’s a bit like using partial evaluation to generate a compiler from an interpreter. I think Peter Sestof did this the hard way a long time ago.