IonMonkey/LIR

WIP, OMG K

LIR

Overview

IonMonkey's LIR (Low-level IR) is an SSA IR. IR nodes are represented as objects, and organized into basic blocks, which comprise a control-flow graph. Unlike MIR, LIR focuses on code generation, having a few major differences:

• It is augmented on a per-platform basis. There are shared LIR nodes that are expected to work on every platform, but platforms can also introduce their own LIR only available for a certain CPU.
• It is lightweight. LIR does not maintain def/use chains and maintains little state beyond its register allocation policies.
• Its inputs and outputs are virtual registers, rather than SSA names.

Nodes

Found in: ion/IonLIR.*, ion/LOpcodes.h, ion/LIR-$(ARCH).h, ion/LOpcodes-$(ARCH).tbl

LIR nodes are encapsulated in LInstructions, which are attached to LBlocks. LBlocks have a 1:1 mapping, and the same ordering as, MBasicBlocks, mirrored the LGraph data structure.

LInstructions have the following properties:

• An opcode identifier.
• A snapshot, containing LAllocation policies capturing the virtual registers of each SSA name on the stack at the last resume point.
• Defs: Zero or more LDefinition policies specifying the outputs of the instruction.
• Operands: Zero or more LAllocation policies specifying the inputs of the instruction.
• Temps: Zero or more LDefinition policies specifying temporary registers needed by the instruction.

To make accessing and allocating nodes as fast as possible, LInstructionHelper<D, I, T> is a template class where D is the number of definitions, I is the number of input operands, and T is the number of temporaries. Instructions should inherit from this class if possible.

Representing Values

One tricky aspect of LIR is that we would like to abstract it as much as possible, however, the representation of a js::Value is architecture-specific. For instructions that define values, or take in values as operands, we use a BOX_PIECES macro which is 1 for punboxing and 2 for nunboxing.

We treat value inputs and definitions as untyped, and therefore, as non-constant.

Virtual Registers and Policies

LIR describes how the register allocator should assign physical registers or memory locations to its instructions. The heart of representing physical or virtual allocations is an LAllocation, which derives into the following classes:

• LUse, containing a virtual register and a physical allocation policy. A virtual register is an integer, and they are allocated sequentially.
• LGeneralReg, containing a general-purpose register.
• LFloatReg, containing a floating-point register.
• LArgument, containing a reference to one of the method's input arguments.
• LConstant*, a constant value.
• LStackSlot, containing a reference to a stack slot.

An LDefinition is a separate structure, a tuple containing the following properties:

• A virtual register. Every LDefinition defines a unique virtual register.
• A type (double, integer, pointer, box, etcetera).
• An LAllocation, which is the initial allocation for the definition.

Inputs

Inputs to an instruction are represented with LAllocations, and fall into the following categories:

• LUse: A use of a virtual register, with an associated policy.
• LConstant*: A constant value that will be ignored by the register allocator.

The register allocator transforms LUses into register or memory variants of LAllocation. The associated policies for doing so are:

• ANY: The instruction supports this operand being in a stack slot or register.
• REGISTER: The instruction requires this operand to be in a register.
• FIXED: Not only does this instruction require a register, it requires a specific register which is specified in the LUse.
• KEEPALIVE: Same as ANY; however, the register allocator should not apply heuristics. If the value is already in a stack slot, it should not be loaded into a register. This is used only for snapshots.
• COPY: This instruction requires the input be in a writable register. This means the register allocator will copy the input into a new register, unless it knows the value is dead.

Outputs

Outputs to an instruction are represented with LDefinitions. As mentioned earlier, they define unique virtual registers. Definitions fall into two categories:

• Preset, which specify a *physical*, non-constant LAllocation ahead of time.
• Unallocated, which means the register allocator will use the LDefinition's policy to allocate a register.

LDefinitions have the following policies:

• DEFAULT, meaning a register.
• PRESET, meaning the register allocator must use the allocation specified in the definition's LAllocation.
• MUST_REUSE_INPUT, which requires that the definition have the same register as the 0th input operand. This is for two-register architectures like x86, and is conceptually similar to the COPY input policy.
• REDEFINED, which says that this LDefinition is actually the same as another LDefinition. When REDEFINED is used, the LDefinition is completely ignored. The instruction is informing the register allocator that, rather than producing a new output, it is a "pass-through" mechanism (like boxes and unboxes on x86).