View source for IonMonkey/MIR

IonMonkey's MIR (Middle-level IR) is an SSA IR. IR nodes are represented as objects, and organized into basic blocks, which comprise a control-flow graph.

=Overview=
The MIR pipeline is fairly straightforward. It is composed of two major phases:
*Building.
**Generate MIR and CFG from bytecode.
**Analyze control-flow graph.
**Analyze type flow and insert conversions.
*Optimization.
**Perform loop-invariant code motion.
**Perform global value numbering.
**Dead code elimination.

=Control-Flow Graphs=

''Found in: <tt>jit/MIRGraph.*</tt>

The control-flow graph for MIR is represented via basic blocks (<tt>MBasicBlock</tt>). Basic blocks are collected in a <tt>MIRGraph</tt>, in reverse postorder. 

Each basic block has the following information:
*List of SSA phis.
*List of MIR instructions.
*List of predecessors.
*A "last" instruction, which must be a control instruction.
*List of successors.
*Dominator information.
*An entry "resume point" (described later).

During MIR building, an MBasicBlock also models the interpreter stack, mapping local variables and stack slots to SSA names.

=MIR Nodes=

''Found in: <tt>jit/MIR.*</tt>

MIR objects are organized into the following class hierarchy:

[[File:ionmonkey_mir.png]]

IR nodes are separated into definitions (which provide an SSA name) and resume points, which are purely informative and described later.

*'''MDefinition''': A node which provides an SSA name.
*'''MPhi''': A pseudo-instruction representing an SSA phi. Phis are placed at the top of basic blocks. They have ''n'' inputs, where ''n'' is the number of predecessors to its containing block.
*'''MInstruction''': An actual instruction that either produces a value, has an effect, or guards on a condition. Instructions may be added to basic blocks.

Definitions have the following information:
*An opcode, describing which class the IR node can be cast to.
*A list of input operands.
*A return type, if the definition returns anything.
*A list of IR nodes which use this definition. Def-use chains are created automatically when adding input operands.
*An instruction ID, assigned incrementally in reverse postorder.
*A resume point, described later.

=Building MIR=

''Found in: <tt>jit/IonBuilder.*</tt>''

==Parsing Bytecode==
MIR is currently built directly off the bytecode in a <tt>JSScript</tt>. The entire bytecode is traversed in a single pass. The builder uses abstract interpretation, modelling the stack transitions of each bytecode to break it down into SSA.

The bytecode is traversed as if it were an AST. For example, both arms of an "if" are read before proceeding at the join point. (Note, we can do this in one pass thanks to SpiderMonkey's source notes.) However, join blocks are created ahead of time, and its predecessors are added incrementally. This allows us to lazily place phis, which is necessary when two predecessors have different definitions for the same slot.

Backedges need to be handled specially. If the definition of a slot differ between a loop header and its backedge, a phi is created at the header. Any uses of the original slot in the header, that are dominated by the header, are replaced with the phi. (Also see, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.4503&rep=rep1&type=pdf "Single Pass Generation of SSA Form for Structured Languages"]).

For example, here is a diagram of MIR generation for the following script. Red indicates key control flow triggers in the bytecode.
<pre>
function f(a) {
  var x;
  if (a)
    x = 5;
  else
    x = 10;
  return x;
}</pre>
[[File:ionmonkey_building_mir.png]]

Timeline:
* The initial block is built, until the builder reaches IFEQ.
* The builder creates blocks for the "true" arm (5-10), the "false" arm (14-19), and the join position, which starts at 20. It then pushes an "if" indicator onto an internal traversal stack, which describes both arms.
* The builder traverses the "true" arm, until it reaches position 11.
* The builder traverses the "false" arm, until it reaches position 19.
* The builder pops the traversal stack, and resumes building MIR into the join block at position 20.

'''Note 1:''' Certain control-flow triggers will automatically terminate traversal for the current control structure. These are "break", "continue", and "return". Bytecode after these are automatically determined to be not reachable.

'''Note 2:''' Copy or constant propagation is NOT ALLOWED during MIR generation. This would break phi replacement, for reasons described in <tt>MIRGraph.cpp</tt>.

==Resume Points==

Resume points are special IR nodes whose function is at the heart of IonMonkey. When deoptimization occurs, it is necessary that we resume the JavaScript program in another execution mode. This means translating the highly optimized Ion state back into the interpreter. Resume points capture the information necessary to make this happen.

For a given point in the program, MResumePoints save the SSA names corresponding to each local variable and slot in the expression stack. MResumePoints can be taken anywhere, but minimally, '''MUST''' be taken at these critical points:
*At the start of basic blocks. Execution cannot resume before an already-taken control keyword.
*After non-idempotent instructions. For example, calls, or modifications to the heap, are both observable.

This is because when deoptimization occurs, we resume the JavaScript program at the most recently-taken resume point. If this re-executes idempotent code, that is okay. If it re-executes an observable operation, it could lead to a correctness bug.

MResumePoints participate in def-use chains, but are not actual definitions or instructions. Rather, they are attached to instructions or basic blocks. When attached to instructions, they are meant to be captured ''after'' the instruction. '''This means an MInstruction's effects must be atomic.''' There is no facility to resume in the "middle" of an instruction.

==Graph Fixups==

''Found in: <tt>jit/IonAnalysis.*</tt>''

After building MIR, a few passes are run to make the graph suitable for future analyses and optimizations:
*Critical edges are split.
*Blocks are re-ordered to be in reverse postorder.
*A dominator tree is built.

=Types=

==Specialization==

''Found in: <tt>jit/IonBuilder.cpp</tt>''

While building MIR, we attempt to attach type information to certain nodes. For example, the likely inputs and outputs of arithmetic operations, the likely targets of a call, or the likely shapes of objects for property accesses. This information is retrieved from Type Inference or baseline caches.

Type Inference:
During execution the types are saved and TI gives back this list of output types that were observed. During compilation this list is frozen and cannot get adjusted anymore without requiring to invalidate the IonScript based on this type information.

Baseline Engine:
During execution the baseline compiler needs to create specialized stubs. When specializing we can take put specialized information on those stubs and use these hints to better optimize the MIR nodes. Since those are hints we still need to guard during execution this is true.

==Respecialization==

''Found in: <tt>jit/IonAnalysis.cpp, jit/TypePolicy.*</tt>''

After MIR is built, each instruction is analyzed in postorder. If the instruction exposes a <tt>TypePolicy</tt>, it is asked to perform two tasks:
*Respecialize if needed, and,
*Propagation specialization.

For example, an "add" operation that has been specialized to take 32-bit integers, may actually have a floating-point input. In this case, the add will respecialize. When an instruction is respecialized, any uses of the instruction are re-analyzed. (Note that nodes can never respecialize from idempotent to non-idempotent, unless they have a resume point.) 

Next, an "add" operation may notice that one of its inputs' types is not known: for example, the result of call. In this case, the add's specialization is propagated to the input. Every untyped input has a set containing the types it should be specialized as. If an untyped input has only one specialization request, that type is considered its ''observed'' or effective type.

Finally, phis are handled specially. By default, phis return values. However, if all inputs to a phi have the same type or effective type, the phi is specialized, and its uses re-analyzed.

This algorithm runs to a fixpoint.

==Conversion Insertion==

The final phase necessary to make MIR complete is insertion of conversion operations. For example, a "bitand" operation might have a boolean input, which is illegal. This pass corrects that.

All definitions are iterated in reverse postorder, such that all definitions are seen before their uses. If an untyped value is encountered, and it has an effective type, an Unbox operation is inserted immediately after its definition. Any uses of the instruction are then replaced with the unboxed version. The goal of this is to make sure wider representation of values are killed off as soon as possible (on x86, untyped values carry an extra register).

If an instruction has any inputs, and specifies a type policy, the type policy may then insert conversion operations. For example, a specialized bitand may insert MTruncateToInt32, while an unspecialized add may insert MBox, since it requires untyped inputs.

After this phase, the MIR type checks and is ready for optimization.