SPUR: A Trace-Based JIT Compiler for CIL

Besides working on Pex, for the last year I have been driving forward a new research project, SPUR.

SPUR is a “Trace-based JIT Compiler for CIL”, and it works especially well for dynamic languages, in particular JavaScript.

Now, what does “Trace-based JIT Compiler for CIL” mean anyway? In a nutshell, it translates .NET code to machine code, similar to how the normal .NET Framework would do it. What is new in our research prototype is that SPUR optimizes the code while it is running.

Consider the following example. It is written in C#, and it shows a basic problem that appears in dynamic languages such as JavaScript, where all values are (potentially boxed) objects. An interface IDictionary describing a general mapping from objects to objects is used in method ArraySwap with the implicit assumption that it is a dense array, mapping integers to doubles.

 interface IDictionary {
  int GetLength();
  object GetElement(object index);
  void SetElement(object index, object value);
}

...

 void ArraySwap(IDictionary a) {
  for (int i = 0; i < a.GetLength() - 1; i++) {
    var tmp = a.GetElement(i);
    a.SetElement(i, a.GetElement(i + 1));
    a.SetElement(i + 1, tmp);
  }
}

Is this ArraySwap method efficient? Without knowing more about the particular IDictionary implementation that is going to be passed in, that is hard to tell. Let us use the following implementation of IDictionary, which can only store floating point values in a dense array:

 class DoubleArray : IDictionary {
  private double[] _elements;
  ...
  public int GetLength() {
    return _elements.Length; 
  }
  public object GetElement(object index) {
    return (object)_elements[(int)index];
  }
  public void SetElement(object index, object value) {
    _elements[(int)index] = (double)value;
  }
}

Now it becomes clear that the arguments and results of GetElement and SetElement are going to be continually boxed, type-checked for proper types, and unboxed. Wouldn’t it be nice if the entire code could be automatically optimized as a whole, to get rid of all the fluff?

Our current research prototype of SPUR does exactly this kind of optimization for us fully automatically: First, SPUR monitors which portions of the code are executed a lot. Then SPUR collects traces of the hot code paths, in order to analyze and optimize the traces. Only a few simple checks, called guards, need to remain in place which ensure that all explicit and implicit branching decisions that were observed during tracing will repeat later on. If not, then the optimized code will jump back into unoptimized code. Here, we need guards to ensure that the actual dictionary is not null and actually has type DoubleArray, that a._elements is not null, and also that “i” is a valid index, and fulfills the loop condition. All virtual method calls can be inlined, all boxing, type-checks and unboxing code eliminated. Most guards can be hoisted out of the loop, and code similar to the following is produced by SPUR for the loop, preceeded by the hoisted guards. Note the slim loop body which no longer performs any virtual method calls, boxing or unboxing, but just the actual work. After the transformation, the code runs about four times faster.

   if (a == null ||
      a.GetType() != typeof(DoubleArray)) 
  { ... /* transfer back to unoptimized code */ }
  var elements = a._elements;
  if (elements == null)
  { ... /* transfer back to unoptimized code */ }
  var length1 = elements.Length - 1;
  while (true) {
    if (i < 0 || i >= length1)
    { ... /* transfer back to unoptimized code */ }
    double tmp = elements[i];
    elements[i] = elements[i + 1];
    elements[i + 1] = tmp;
    i++;
  }

This works well for any .NET program, and it works especially well for dynamic languages, in particular JavaScript. You can read about the current status of this research project in this technical report.

There is an interesting relation between Pex and SPUR: Both analyze program traces, gathered from monitoring actual program executions. While Pex is looking for branches in the code that can be “flipped” (if so, Pex generates another test input, possibly uncovering a bug), SPUR is looking for branches that cannot be “flipped” (if so, SPUR can remove it, and make the code run faster).