Lua

The LuaJIT Wiki

not logged in | [Login]

LuaJIT 2.0 SSA IR

Introduction

The following document describes the Intermediate Representation (IR) used by the JIT-compiler of LuaJIT 2.0. The trace-compiler records bytecode instructions, following the control-flow, and emits the corresponding IR instructions on-the-fly.

The IR has the following characteristics:

  • The IR is in SSA (Static Single Assignment) form. Every instruction (node) represents a single definition of a value. Multiple instructions form a partially connected data-flow graph. Data-flow for loops is represented using PHI-instructions. Control-flow is always implicit.

  • The IR is linear, pointer-free and implicitly numbered: every instruction can be uniquely referenced (IRRef) by its position in a linear array. Specially crafted, biased IR references allow fast const vs. non-const decisions. No space is wasted on storing an explicit reference number, value number or similar.

  • The IR is in 2-operand-normalized form: every instruction has an opcode and a maximum of two operands. A few instructions may need more operands (e.g. CALL*), which are composed using extension instructions (CARG).

  • The IR is typed: every instruction has an output data type. The modeled types correspond to the basic Lua data types plus low-level data types. Higher-level data types are indirectly modeled as-needed with guarded assertions.

  • The IR has segregated, per-opcode chaining: this allows fast searching for specific instructions in reverse order without a full traversal. This is used to speed up many optimizations, like CSE or alias analysis. Most searches stop after zero (no match), one or two dereferences in practice.

  • The IR is very compact: it needs only 64 bits per instruction and all instructions are adjacent to each other. This layout is very cache-efficient and very fast to index or traverse.

  • The IR is incrementally generated: the IR array is bi-directionally grown: constants grow downwards, all other instructions grow upwards. Most optimizations are perfomed on-the-fly and eliminated instructions are either simply not emitted, ignored during code generation or appropriately tagged. There's no general need to insert or delete instructions in the middle. This avoids the very cache-inefficient linked-sea-of-nodes data structure, presented in most compiler textbooks.

  • The IR is unified: it carries both high-level semantics and low-level details. Different stages of the compiler use different aspects of the IR, but share a common IR format. Eliminating the classic HIR, MIR, LIR separation (high-, medium-, low-level IR) greatly reduces complexity and compiler overhead. It avoids semantic information loss due to abstraction mismatches and allows cheap and effective high-level semantic disambiguation for memory references.

  • The IR uses auxiliary snapshots: a snapshot captures the IR references corresponding to modified slots and frames in the bytecode execution stack. Every snapshot saves a specific bytecode execution state, which can later be restored on trace exits. Snapshots are sparsely emitted and compressed. Snapshots provide the link between the IR and the bytecode domain (and transitively the source code domain, via the bytecode debug info).

Status

COMPLETE REWRITE IN PROGRESS

See src/lj_ir.h and src/lj_jit.h in the LuaJIT source code for the full details. The generated IR can be listed with luajit -jdump (traced bytecode, IR and machine code) or luajit -jdump=i (IR only).

Overview

Basic example:

$ ./luajit -jdump=bitmsr
LuaJIT 2.0.0-beta10 -- Copyright (C) 2005-2012 Mike Pall. http://luajit.org/
JIT: ON CMOV SSE2 SSE3 AMD fold cse dce fwd dse narrow loop abc sink fuse
> local x = 1.2 for i=1,1e3 do x = x * -3 end
---- TRACE 1 start stdin:1
0006  MULVN    0   0   1  ; -3
0007  FORL     1 => 0006
---- TRACE 1 IR
....              SNAP   #0   [ ---- ]
0001 rbp      int SLOAD  #2    CI
0002 xmm7  >  num SLOAD  #1    T
0003 xmm7   + num MUL    0002  -3  
0004 rbp    + int ADD    0001  +1  
....              SNAP   #1   [ ---- 0003 ]
0005       >  int LE     0004  +1000
....              SNAP   #2   [ ---- 0003 0004 ---- ---- 0004 ]
0006 ------------ LOOP ------------
0007 xmm7   + num MUL    0003  -3  
0008 rbp    + int ADD    0004  +1  
....              SNAP   #3   [ ---- 0007 ]
0009       >  int LE     0008  +1000
0010 rbp      int PHI    0004  0008
0011 xmm7     num PHI    0003  0007
---- TRACE 1 mcode 81
394cffa3  mov dword [0x4183f4a0], 0x1
394cffae  movsd xmm0, [0x4184f698]
394cffb7  cvtsd2si ebp, [rdx+0x8]
394cffbc  cmp dword [rdx+0x4], 0xfffeffff
394cffc3  jnb 0x394c0010	->0
394cffc9  movsd xmm7, [rdx]
394cffcd  mulsd xmm7, xmm0
394cffd1  add ebp, +0x01
394cffd4  cmp ebp, 0x3e8
394cffda  jg 0x394c0014	->1
->LOOP:
394cffe0  mulsd xmm7, xmm0
394cffe4  add ebp, +0x01
394cffe7  cmp ebp, 0x3e8
394cffed  jle 0x394cffe0	->LOOP
394cffef  jmp 0x394c001c	->3
---- TRACE 1 stop -> loop

The above prints the bytecode of the trace, the IR generated from that bytecode with snapshots, and the machine code generated from the IR.

The columns of the IR are as follows:

1st column: IR instruction number (implicit SSA ref)
2nd column: physical CPU register or physical CPU stack slot that
  value is written to when converted to machine code.
  '[%x+]' (rather than register name) indicates hexadecimal offset
  from stack pointer.
  (This column is only present if the 'r' flags is included in -jdump, which
  augments the IR with register/stack slots.  It is not part of the IR itself.)
3nd column: Instruction flags:
  ">" (IRT_GUARD = 0x80 instruction flag) are locations of
    guards (leading to possible side exits from the trace).
  "+" (IRT_ISPHI = 0x40 instruction flag) indicates
    instruction is left or right PHI operand. (i.e referred
    to in some PHI instruction).
4rd column: IR type (see IR Types below)
5th column: IR opcode (see opcode reference)
6th/7th column: IR operands (SSA refs or literals)
  '#' prefixes refer to slot numbers, used in SLOADS.
     #0 is the base frame (modified only in tail calls).
     #1 is the first slot in the first frame (register 0 in
     the bytecode)
  '[+-]' prefixes indicate positive or negative numeric literals.
  '[0x%d+]' and NULL are memory addresses.
  '"..."' are strings.
  '@' prefixes indicate slots (what is this?).
  Other possible values: "bias" (number 2^52+2^51 ?), "userdata:%p",
     "userdata:%p" (table)--when do these occur?.

See also SSA dump format comments: http://lua-users.org/lists/lua-l/2008-06/msg00225.html (older version). See formatk in dump.lua.

Each snaphot (SNAP) lists the modified stack slots and their values. The i-th value in the snapshot list represents the index of the IR that writes a value in slot number #i. '---' indicates that the slot is not written. Frames are separated by '|'. For further comments on snapshots, see http://lua-users.org/lists/lua-l/2009-11/msg00089.html.

IR types (see irtype_text in dump.lua or IRTDEF in lj_ir.h:

"nil" 0
"fal" 1
"tru" 2
"lud" 3
"str" 4
"p32" 5
"thr" 6
"pro" 7
"fun" 8
"p64" 9
"cdt" 10
"tab" 11
"udt" 12
"flt" 13
"num" 14
"i8 " 15
"u8 " 16
"i16" 17
"u16" 18
"int" 19
"u32" 20
"i64" 21
"u64" 22

"Mode bits" (used in below opcode definitions, the second column): Commutative (C), {Normal/Ref (N), Alloc (A), Load (L), Store (S)}, Non-weak guard (W).

Memory ops

A = array, H = hash, U = upvalue, F = field, S = stack.

Memory references.

AREF, R , ref, ref

Array reference

HREFK, R , ref, ref

Hash reference (with constant key?)

  • op1: index to IR for table hash part (tab.node)?
  • op2: key?

HREF, L , ref, ref

Hash reference.

  • op1: index to IR for table
  • op2: index to IR for key

NEWREF, S , ref, ref

This is something related to creating a new table key (lj_tab_newkey).

  • op1: index to IR for table
  • op2: index to IR for key

UREFO, LW, ref, lit

Upvalue reference, open?

  • op1 is the index to the IR for the function value.
  • op2 - bits 0..7 are some type of hash value for the upvalue (see rec_upvalue). Bits above that represent the upvalue index (0-based integer) in the function.

UREFC, LW, ref, lit

upvalue reference, closed?

op1 and op2 are the same as in UREFO.

FREF, R , ref, lit

Field reference

  • op1:
  • op2: field identifier - see op2 values in FLOAD.

STRREF, N , ref, ref

String reference

Loads and Stores

ALOAD, L , ref, ___

Array load

HLOAD, L , ref, ___

Hash table load

ULOAD, L , ref, ___

Upvalue load

op1: index of IR for upvalue reference (e.g. UREFC/UREFO).

FLOAD, L , ref, lit

Field load. This accesses the field identified by (lit) in a C struct located at the address referred to in (ref). The fields are at known constant offsets from the structure base address.

op2: (values from irfield in vmdef.lua and IRFLDEF in lj_ir.h)
"str.len" (0) STR_LEN - string length (GCstr.len)
"func.env" (1) FUNC_ENV - function environment (GCfunc.l.env)
"tab.meta" (2) TAB_META - table metatable (GCtab.metatable)
"tab.array" (3) TAB_ARRAY - table array part (GCtab.array)
"tab.node" (4) TAB_NODE - table hash part (GCtab.node)
"tab.asize" (5) TAB_ASIZE - table array part size (GCtab.asize)
"tab.hmask" (6) TAB_HMASK - table "Hash part mask (size of hash part - 1)" (GCtab.hmask)
"tab.nomm" (7) TAB_NOMM - table "Negative cache for fast metamethods" (GCtab.nomm)
"udata.meta" (8) UDATA_META - userdata metatable (GCudata.metatable)
"udata.udtype" (9) UDATA_UDTYPE "Userdata type" (GCudata.udtype)
"udata.file" (10) UDATA_FILE
"cdata.typeid" (11) CDATA_TYPEID (GCcdata.typeid) - FFI C type ID (unique to every C type)
"cdata.ptr" (12) CDATA_PTR 

XLOAD, L , ref, lit

Load from pointer? Note: can occur with FFI cdata.

  • op1: index of IR for pointer to load from
  • op2: bitwise OR of
"R" 1 (IRXLOAD_READONLY,  Load from read-only data.)
"V" 2 (IRXLOAD_VOLATILE,  Load from volatile data.)
"U" 4 (IRXLOAD_UNALIGNED, Unaligned load.)

SLOAD, L , lit, lit

Stack load

  • op1: stack slot number to load from.
  • op2 values:
"P"  1 (IRSLOAD_PARENT, Coalesce with parent trace)
"F"  2 (IRSLOAD_FRAME, Load hiword of frame)
"T"  4 (IRSLOAD_TYPECHECK, Needs type check)
"C"  8 (IRSLOAD_CONVERT, Number to integer conversion)
"R" 16 (IRSLOAD_READONLY, Read-only, omit slot store)
"I" 32 (IRSLOAD_INHERIT, Inherited by exits/side traces)

VLOAD, L , ref, ___

Vararg load

ASTORE, S , ref, ref

Array store

HSTORE, S , ref, ref

Hash table store

  • op1: index of IR for reference to value in hash table.
  • op2: key

USTORE, S , ref, ref

Upvalue store

FSTORE, S , ref, ref

Field store

XSTORE, S , ref, ref

Store to pointer? Note: can occur with FFI cdata.

  • op1: index of IR for pointer to store to
  • op2: index of of IR for value to store

Allocations.

SNEW, N , ref, ref

Create new string. (lj_str_new)

  • op1: const char *str; op2: size_t len.

XSNEW, A , ref, ref

TNEW, AW, lit, lit

Create new table.

TDUP, AW, ref, ___

Duplicate a table. (lj_tab_dup)

  • op1: table to copy

CNEW, AW, ref, ref

Allocate new FFI cdata.

CNEWI, NW, ref, ref

Initialize new FFI cdata.

Write barriers

TBAR, S , ref, ___

(?)

OBAR, S , ref, ref

Specialized barrier for closed upvalue?

XBAR, S , __, __

Writer barrier for XLOAD/XSTORE.

Type conversions

CONV, N , ref, lit

Various int and float number conversions.

  • op1: lref
  • op2: type conversion.
Bits 0..4 (IRCONV_SRCMASK) are type converted from.
Bits 5..9 (IRCONV_DSTMASK) are type converted to.  See "IR Types" above.
Bit 10 (0x400, IRCONV_TRUNC) is "trunc" (Truncate number to integer).
Bit 11 (0x800, IRCONV_SEXT) is "sext" (Sign-extend integer to integer).
Bits 14..15 are 2 "index"  or 3 "check". (?? - dump.lua and IRCONV_* inconsistent?)

TOBIT, N , ref, ref

(see bit.tobit)

  • op1: dest
  • op1: source

TOSTR, N , ref, ___

Convert to string.

STRTO, N , ref, ___

Convert string to number.

Calls

CALLN, N , ref, lit

Call Normal/Ref (N)?

CALLL, L , ref, lit

Call Load (L)?

CALLS, S , ref, lit

Call Store (S)?

CALLXS, S , ref, ref

CARG, N , ref, ref

(?) something related to function call arguments

Constants

Constant instructions are only present in the constant part of the IR (growing upwards to lower refs). IR constants are interned (de-duplicated) and can be compared for equality only by looking at their references.

Constant instructions never appear in dumps, since -jdump always shows the actual constant value inlined into the referencing instructions.

OP
Left
Right
Description
KPRI     Primitive type: nil, false, true
KINT #int 32 bit integer constant
KGC #ptr Garbage collected constant
KPTR #ptr Pointer constant
KKPTR #ptr Pointer constant to constant data
KNULL #ptr Typed NULL constant
KNUM #k64ptr Double-precision floating-point constant
KINT64 #k64ptr 64 bit integer constant
KSLOT kref #slot Hash slot for constant

Every trace has three KPRI instructions at fixed references for the constants nil, false and true (REF_NIL, REF_FALSE, REF_TRUE).

The 32 bit integer or pointer values occupy the space for both the left and the right 16 bit operand. 64 bit values are interned in a global constant table and indirectly referenced by 32 bit pointers.

KPTR is a constant pointer (absolute address) to possibly non-constant data. KKPTR points to definitely constant data. Only data known by the VM to be constant qualifies, e.g. an interned Lua string. Content tagged as 'const' by users (e.g. const char *) doesn't qualify.

KSLOT is used as a key for HREFK and holds the hash slot where the key is to be found and a reference to the constant key itself.

Guarded Assertions

Guarded assertions have a dual purpose:

  • They provide an assertion about their operands that can be used by the compiler to optimize all following instructions in the same trace.
  • They are emitted by the backend as branching comparisons, with the 'true' outcome in the fall-through path. A 'false' outcome exits the trace and restores the state to the most recent snapshot.
OP
Left
Right
Description
LT left right left < right (signed)
GE left right left ≥ right (signed)
LE left right left ≤ right (signed)
GT left right left > right (signed)
ULT left right left < right (unsigned/unordered)
UGE left right left ≥ right (unsigned/unordered)
ULE left right left ≤ right (unsigned/unordered)
UGT left right left > right (unsigned/unordered)
EQ left right left = right
NE left right left ≠ right
ABC bound index Array Bounds Check: bound > index (unsigned)
RETF proto pc Return to lower frame: check target PC, shift base

The U.. opcodes provide unsigned comparison semantics for integer types and unordered comparison semantics for floating-point types. A NaN operand causes a 'false' outcome for EQ and ordered comparisons, and a 'true' outcome for NE and unordered comparisons.

ABC is treated just like UGT in the backend. But it follows different FOLD rules, which simplifies ABC elimination.

The prototype returned to by RETF is below the call graph covered by the trace up to this point. Thus RETF needs to anchor the prototype to prevent recycling the PC after garbage collection.

Bit Ops

OP
Left
Right
Description
BNOT ref   Bitwise NOT of ref
BSWAP ref   Byte-swapped ref
BAND left right Bitwise AND of left and right
BOR left right Bitwise OR of left and right
BXOR left right Bitwise XOR of left and right
BSHL ref shift Bitwise left shift of ref
BSHR ref shift Bitwise logical right shift of ref
BSAR ref shift Bitwise arithmetic right shift of ref
BROL ref shift Bitwise left rotate of ref
BROR ref shift Bitwise right rotate of ref

The shift count for shift and rotate instructions is interpreted modulo the bit width of the shifted type, i.e. only the lowest N bits are significant. Appropriate bit masking instructions (BAND) are inserted for backends where the underlying machine instructions don't perform the masking themselves. Similarly, rotates are unified to one direction, in case the architecture doesn't provide machine instructions for both.

Arithmetic Ops

OP
Left
Right
Description
ADD left right left + right
SUB left right left - right
MUL left right left * right
DIV left right left / right
MOD left right left % right
POW left right left ^ right
NEG ref kneg -ref
ABS ref kabs abs(ref)
ATAN2 left right atan2(left, right)
LDEXP left right ldexp(left, right)
MIN left right min(left, right)
MAX left right max(left, right)
FPMATH ref #fpm fpmath(ref), see below
ADDOV left right left + right, overflow-checked
SUBOV left right left - right, overflow-checked
MULOV left right left * right, overflow-checked

All arithmetic ops operate within the domain of their types: integers, pointers or floating-point numbers. Not all ops are defined for all possible types. Both signed and unsigned integers wrap around on overflow.

Overflow-checking operations exit the trace upon signed integer arithmetic overflow.

MOD is decomposed into left-floor(left/right)right for floating-point numbers. POW is either turned into POW with an integer as the right operand, or into sqrt(left) if right is 0.5, or into exp2(log2(left)right) otherwise (the backend may later merge this into a call to pow()).

The undefined cases for the integer variants of DIV, MOD and POW return the integer value with only the highest bit set.

NEG and ABS for floating-point numbers reference a SIMD-aligned constant in the right operand. Some backends implement these as a bitwise XOR or AND of the number and the constant.

The right operand of LDEXP is a floating-point number on x86 and x64 platforms and a 32 bit integer on all others.

All floating-point arithmetic operations obey the standard definitions from IEEE 754 wrt. +-0, +-Inf, NaN and denormals. MIN and MAX have no defined behavior for NaN operands.

FPMATH is used for unary floating-point arithmetic operations. The right operand specifies the actual operation:

OP
Description
FPM_FLOOR floor(ref)
FPM_CEIL ceil(ref)
FPM_TRUNC trunc(ref)
FPM_SQRT sqrt(ref)
FPM_EXP exp(ref)
FPM_EXP2 exp2(ref)
FPM_LOG log(ref)
FPM_LOG2 log2(ref)
FPM_LOG10 log10(ref)
FPM_SIN sin(ref)
FPM_COS cos(ref)
FPM_TAN tan(ref)

Memory References

Loads and Stores

Allocations

Barriers

Type Conversions

Calls

Miscellaneous Ops

OP
Left
Right
Description
NOP     No operation
BASE #parent #exit BASE reference, link to parent side exit
PVAL #pref   Parent value reference
GCSTEP     Explicit GC step
HIOP left right Hold hi-word operands of split instructions
LOOP     Separator before loop-part of a trace
USE ref   Explicit use of a reference
PHI left right PHI node for loops
RENAME ref #snap Renamed reference below snapshot

NOP is used to patch previously emitted IR instructions, in case they cannot eliminated or ignored on-the-fly.

BASE is a fixed instruction at REF_BASE, used to hold the BASE pointer. It's implicitly referenced by e.g. SLOAD.

PVAL provides an alternate way to reference specific values of the parent trace, which cannot be referenced with a parent SLOAD (since they are not stored in the stack at the snapshot).

GCSTEP provides an explicit GC step for certain cases where it needs to be done after the initial snapshot.

HIOP must immediately follow a split instruction (split 64 bit op or soft-fp op).

USE is needed to keep instructions for their side-effects that would otherwise be eliminated: e.g. an ADDOV that's used to check for potential integer overflow of loop bounds.

PHI instructions are positioned at the end of a looping trace. The left operand holds a reference to the initial value, the right operand holds a reference to the value after each loop iteration.

RENAME is generated by the register allocator, when it renames a register for a value (for efficiency or to preserve PHI registers). A RENAME instruction holds the register used for the reference below the given snapshot. Multiple instances of this may be present for the same reference. The originally referenced instruction holds the register used above of the highest such snapshot (if any).