IonMonkey: Optimizing Away

Firefox 32

Firefox uses two just-in-time compilers: Baseline and IonMonkey. When a web page contains some JavaScript code, this code is first executed in the interpreter. Then after running the same code multiple times, we compile the code with Baseline. After hundreds of iterations on the same code, we trigger a compilation with IonMonkey.

Baseline is a method compiler which focuses on optimizing each instruction individually. Each instruction checks for optimized cases based on what was previously observed, and it modifies itself every time a new case is detected.

IonMonkey is a method compiler too, but its goal is to optimize instructions across the entire method, and it can remove instructions which are not needed. IonMonkey is also a greedy optimizer, as it takes the currently observed cases as the only possible options and assumes that nothing will change. For example, if a variable has only ever held numbers, IonMonkey assumes that variable will always be a number. If one of the assumptions fails, we cannot continue execution in IonMonkey. Otherwise we might compute incorrect results, or worse, execute random pieces of code. In fact we must discard the IonMonkey code and resume execution in Baseline.

Bailouts

Resuming execution in Baseline implies that we need to stop IonMonkey execution, list all local and temporary variables, reconstruct a stack frame with the layout expected by Baseline, and jump to Baseline code. This process is called a bailout.

To list all variables, IonMonkey emulates the Baseline stack frame when we generate the control flow graph. On the graph, we annotate every block entry and instructions which are doing side effects, such as calls and stores, with resume points. These resume points are used in a similar way as checkpoints in video games — they’re the location where you will start over if something goes wrong. Each resume point captures the layout of the Baseline stack frame, and is used by the generated code to resume execution of the program if IonMonkey’s code is no longer valid.

Representation of a Snapshot

Each resume point contains a list of MIR (Middle-level Intermediate Representation) Instructions which are listed in the same order as the Baseline’s frame is stored on the stack. These MIR Instructions are listed so that we can track the register/stack allocations of the return value for each captured instruction.

Resume points are used by instructions which might fail. For example, when a call returns an object where it used to always return a Number, or when a math operation/function returns a floating point number where it used to only return integers.

When an instruction that might fail is lowered (converted to a lower intermediate representation), we attach a snapshot to the instruction. The snapshot captures the allocation of every MIR Instruction which is listed in the resume point, at the location of the lowered instruction. We do this for each instruction because a value contained in a register might be evicted to the stack if we no longer need it. Thus, for bailing out we need to track all register allocation changes.

An allocation is either a register, a floating point register, a stack offset in IonMonkey’s frame or a constant which is stored next to the code. All these snapshots and allocations are serialized in order to be used during bailouts.

When an instruction fails, the bailout decodes the snapshot and each allocation. The snapshot is used to reconstruct the Baseline frame that we were supposed to have at the last resume point. Allocations are used to read the value out of IonMonkey’s frame and code, to fill the reconstructed frame. And finally, we replace the IonMonkey frame with the Baseline frame and resume Baseline execution.

What Baseline wants, IonMonkey executes

IonMonkey has multiple optimizations, such as Unreachable Code Elimination (UCE) and Dead Code Elimination (DCE). UCE removes then/else blocks which are never taken as the condition can be inferred. DCE removes instructions which are never used. These optimizations help IonMonkey to generate faster code, as there are fewer instructions to execute.

Baseline makes no assumptions about which part of the code needs to run. Its stack frames are always complete and correct. Thus, IonMonkey cannot remove a MIR Instruction if there is a resume point which captures it. This also implies that a MIR Instruction has to be executed before all of the resume points that use it. As a consequence, any unused MIR Instruction, which is captured by a resume point, has to be executed by IonMonkey.

IonMonkey’s optimizations are limited by the expectations of Baseline. Any optimization done by IonMonkey should not be observable within Baseline. The following pieces of code illustrates the limitations added by Baseline:

function getCond() {
  console.log("getCond returns false");
  return false;
}

function maybeMul2(arg) {
  var x = 2 * arg;
  // Baseline expects "x" to be on the stack.

  var cond = getCond();
  // IonMonkey cannot resume before a call.

  if (cond) {
    return x;
  }
  return arg;
}

Once the call of “getCond()” has executed in IonMonkey, we cannot resume in Baseline before that call. If we did, Baseline would execute the call to “console.log” a second time. This implies that the resume point has to capture the MIR Instruction which computes “x”. Thus we have to compute the value of “x” before the call, even in IonMonkey.

IonMonkey can inline the function “getCond()”, determine that “cond” is always false, and eliminate the body of the if-statement as dead code. The optimized IonMonkey code therefore looks like this:

function maybeMul2(arg) {
  var x = 2 * arg; // expected by Baseline.

  // inlined code of getCond
  console.log("getCond returns false");

  return arg;
}

Still, we must compute “x” even though the optimized code clearly doesn’t use it — just in case we are forced to bail out after the call to console.log.

We want IonMonkey to remove that instruction computing “x”.

Recover Instructions

To work around Baseline expectations, we need to remove the instruction from IonMonkey code and move it to the bailout path. The problem is that we need to carry this information to the bailout function.

Currently, allocations are used to carry information about where the values are located. What we need is similar, we need a way to express an allocation which refers to the result of an instruction. The difference being that the instruction is not executed by IonMonkey but that it is executed before reconstructing the Baseline stack frame.

Resume points are listing all the MIR Instructions which are needed to reconstruct a stack frame. Even if we do not execute these instructions, we still want to have them listed in the resume points.

The solution implemented in IonMonkey adds a flag to every MIR instruction. This flag, named RecoveredOnBailout, is used to indicate that for the current instruction, which is still in the control flow graph, we won’t emit any JIT code. Instead, when we attach a snapshot to an instruction, we order and serialize all the instructions which are flagged as RecoveredOnBailout.

Now that instructions are ordered, we can index their results in a similar way as we do for stack offsets. This way, when we bailout, we reserve a vector which is large enough to contain the result of all instructions which are used during the bailout. The allocations are modified so that, in addition to the register, stack offset, and constants, we can refer to an index in this vector of instruction results.

Representation of a Snapshot with Recover Instructions

When an instruction fails, in addition to decoding the snapshot, the bailout process iterates over the list of instructions. Each instruction reads the values of the allocations that it needs, and stores its result in the reserved vector. Then, another allocation will refer to this result to fill the reconstructed frame.

Optimizing Away

The goal of recover instructions is to open a new class of optimizations where resume points are almost nonexistent.

Due to the resume points, we had to restrict our optimizations to optimizations which hoist instructions in the control flow graph, such as Global Value Numbering (GVN) and Loop Invariant Code Motion (LICM), but we could barely remove instructions or even sink them in the control flow graph.

With recover instructions, we should be able to remove instructions or move them closer to their uses. In the previous example, if we are unable to prove that the branch is dead, we can still move the computation of “x” to the only branch which uses it.

function maybeMul2(arg) {
  // no more overhead.

  var cond = getCond();
  // Baseline can recover "x = 2 * arg".

  if (cond) {
    var x = 2 * arg;
    return x;
  }
  return arg;
}

In the meantime, recover instructions are a good abstraction for improving our Dead Code Elimination (DCE), and implementing optimizations such as Escape Analysis. All of these optimizations allow IonMonkey to generate faster code by transforming the code to be even more different from what Baseline expects. Whenever a bailout occurs, recover instructions stand ready to put the world back in a Baseline-friendly state.

Contributors inside

In addition to improving our scope of optimizations, recover instructions are simple to implement. This project has provided a good trampoline for multiple contributors to join the project. Please thank and welcome the 12 new contributors who contributed their first patches to the JavaScript engine:

1 response

Post a comment

  1. tigertownpc wrote on :

    Great post and I’m very happy to see this enables a whole new realm of optimization possibilities!
    I’m also appreciative of actually having a blog posted about it. It had been quite a long time since the JS Team published an update, so thanks for that as well!

    Reply

Post Your Comment