homework 7 dynamic compile

This task is to implement a trace-based speculative optimizer for Bril. You’ll implement the same concept as in a tracing JIT, but in a profile-guided AOT setting: profiling, transformation, and execution will be distinct phases. The idea is to implement the “heavy lifting” for a trace-based JIT without needing all the scaffolding that a complete JIT requires, such as on-stack replacement.

Concretely, there are three main phases:

  1. Modify the reference interpreter to produce traces.
  2. Build an optimizer that injects traces back into the original program using the speculation extension to provide a “fast path.”
  3. Check that the whole process is correct and had some effect on performance (it needn’t actually be good!).

Start by reading the documentation for the speculation extension (and watch the video!). That should give you an idea of what’s required to augment a program with a speculative execution of an extracted trace. Then make a plan for how you’ll hack the interpreter to produce one of those traces.

Here’s a recipe:

  1. Start interpreting normally.
  2. At some point during execution (at the very beginning of main, for example, or when reaching a backedge), start tracing.
  3. While tracing, record every instruction as it executes. Eliminate jumps; replace branches with guard instructions. Feel free to do the interprocedural version, and to bail out on any other instruction you don’t want to handle.
  4. Stop tracing at some point (after a fixed number of instructions, for example, or at the next backedge) and save the trace to a file.
  5. For bonus “points,” statically optimize the trace by eliminating instructions that depend on foregone conclusions enforced by guards.
  6. Transform the program to stitch the trace back into the program using speculate and commit instructions.
  7. For these tasks, unlike some previous lessons, I recommend not attempting to support all the benchmarks. It’s more important that you understand a few programs well than you apply your transformation to a large body of code. (In other words, I recommend that you work depth-first instead of breadth-first.)

In particular, you do not need to support Bril’s memory extension, which makes things more complicated because it doesn’t get automatically rolled back on speculation aborts. If you are feeling very ambitious, you can try devising a scheme to manually roll back memory modifications on aborts (consider an “undo log” or “redo log,” which are concepts from databases).

Finally, evaluate your work:

Back to top