Confirmed users
156
edits
IonMonkey/MIR: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
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. | 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= | =Control-Flow Graphs= | ||
| Line 85: | Line 96: | ||
Snapshots 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. | Snapshots 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>ion/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>ion/TypeOracle.h</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 queried from a <tt>TypeOracle</tt>. Currently, there is only one (bogus) oracle, but oracles based on Brian Hackett's type inference, and runtime profiling, are planned. | |||
The oracle helps guide specialization. There are generally three modes of specialization: | |||
* Unknown. Nothing is known about the operation, and it may have to be assumed effectful. | |||
* Observed. A particular type (or set of types) has been observed, so we will compile expecting those. This may introduce guard instructions which protect these assumptions, deoptimizing if the guards do not hold. | |||
* Known. A particular type has been proven to hold (for example, via type inference). | |||
==Respecialization== | |||
''Found in: <tt>ion/IonAnalysis.cpp, ion/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 snapshot.) | |||
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. | |||