Making the Compilation “Pipeline” Explicit:Dynamic Compilation Using Trace Tree SerializationAndreas Gal, Michael Bebenita, Mason Chang, and Michael FranzComputer Science DepartmentUniversity of California, IrvineIrvine, CA, 92697, USA{gal,bebenita,changm,franz}@uci.eduAbstract. Trace-based compilers operate by dynamically discovering loop head-ers and then recording and compiling all paths through a loop that are executedwith sufficient frequency. The different paths through each loop form a tree, withthe loop header at the root, in which common code is shared up-stream. Suchtrace-trees can be serialized in a specific manner that allows us to organize thecompiler pipeline as a series of filters. We have implemented such a compilerpipeline that has completely linear runtime behavior. Further, it has only twowrite barriers, meaning that substantial parts of the compilation effort could po-tentially be parallelized on future multi-core platforms.1 IntroductionMost just-in-time (JIT) compilers operate at the granularity of methods. Apart fromthe fact that it happens at run-time, the actual process of compilation is often not allthat different from the way this is done in traditional compilers: First, an intermediaterepresentation incorporating a control-flow graph is built for the entire method. Then,a series of optimization steps is applied, until finally a program in the target instructionset is obtained.We have been working on an alternative compilation strategy in which no control-flow graph is ever constructed, but in which relevant (i.e., frequently executed) controlflows are instead discovered lazily during execution. We have built a compiler that dy-namically detects “hot” code paths, so-called “traces”, and generates code on-the-fly forexactly these code paths—all other parts of the program are executed by interpretationonly [10].Our compiler first dynamically detects loop headers and then incrementally discov-ers alternative paths through the resulting loops. For example, an if statement insideof a while statement corresponds to two different paths through the while loop.Each time that a new path through the loop that hasn’t been recorded before becomessufficiently “hot”, we recompile all known paths through the loop, re-balancing theprocessor resources expended on the alternatives.In this paper, we report how re-compiling the different code paths through a loopcan be pipelined in a compiler and implemented quite elegantly as a series of filtersthrough which a program passes on its way from intermediate representation to targetcode. Each compiler phase is implemented as a separate filter that manipulates the in-struction “stream” by altering, inserting, re-ordering, or removing instructions as the“stream” passes through it. Even more interestingly, the pipeline requires only two syn-chronization points, meaning that the compilation activity could potentially be highlyparallelized on a a future multicore platform in which there are idle processor resourcesavailable.The remainder of this paper is organized as follows. In Section 2, we describe howalternative paths through a program are discovered lazily and recorded in a representa-tion that we call a “Trace Tree”. In Section 3, we show how such Trace Trees can beserialized in such a way that correct compilation semantics result from a set of linearpasses over the serialized tree. This is the basis for the idea of pipelining these passes,which is discussed in Section 4. In Section 5 we report on a series of benchmarks thatdemonstrate the performance of our compiler pipeline. In particular, run-time is directlyproportional to the length of the serialized tree. Related work is discussed in Section 6.We end with conclusions and future work in Section 7.2 Trace TreesOur trace-based JIT compiler targets the Java Virtual Machine (JVM) bytecode lan-guage. It is a mixed-mode execution environment in which bytecode is initially inter-preted, and in which only frequently executed (“hot”) code is ever compiled. To detectsuch “hot” code regions that are suitable candidates for dynamic compilation, we use asimple heuristic first introduced by Bala et al. [2]. In this scheme, the interpreter keepstrack of backward branches; the targets of such branches are often loop headers. Foreach target of a backward branch, we keep a counter of how often a backward branchhas terminated at this location. When the counter exceeds a certain threshold, a loopheader has been discovered.The interpreter then records the instruction path subsequently taken, starting withthe loop header. If that path leads back to the loop header within a certain observa-tion window and fulfills certain other criteria, then we have recorded an initial tracethrough the loop. There may be other paths through the loop (recall the example of anif statement inside of a while statement) that may be disovered later. The trace isthen compiled and the resulting target code is executed.Forward branches inside of a trace indicate alternative paths that may not yet havebeen discovered by our compiler. For example, in the case of our if statement insideof a while statement, when we initially discover the loop, we only follow one paththrough the loop. If indeed the if condition is so skewed that only one of the twoalternatives is ever taken sufficiently often, then our compiler will never generate codefor the rare alternative. If the second path is common, then it will eventually be compiledas well.Branches to paths that have not yet been seen by our compiler are compiled intoguard instructions. When such a guard fails, that means that we have arrived at a paththat has not yet been compiled. This is called a “side exit” from the loop. In this case,the compiled code hands control back to the interpreter. Since this can be expensive, ourJIT compiler attempts to compile the alternative path that led to the side exit as well.2For this, at every side exit we resume interpretation, but at the same time we restartthe trace recorder to record instructions starting at the side exit point. These secondarytraces are completed when the interpreter revisits the original loop header. This resultsin a tree of traces, spanning all observed paths through the “hot” code region. The restof this paper explains how we compile such Trace Trees.We also inline method invocations into the trace. In case of a static method in-vocation, the target method is fixed and