Cranelift IR Reference
Foreword
This document is likely to be outdated and missing some important information. It is recommended to look at the list of instructions as documented in the InstBuilder documentation.
Intro
The Cranelift intermediate representation ([IR]) has two primary forms: an in-memory data structure that the code generator library is using, and a text format which is used for test cases and debug output. Files containing Cranelift textual IR have the .clif filename extension.
This reference uses the text format to describe IR semantics but glosses over the finer details of the lexical and syntactic structure of the format.
Overall structure
Cranelift compiles functions independently. A .clif IR file may contain multiple functions, and the programmatic API can create multiple function handles at the same time, but the functions don't share any data or reference each other directly.
This is a simple C function that computes the average of an array of floats:
Here is the same function compiled into Cranelift IR (with 64 bit pointers):
The first line of a function definition provides the function name and the [function signature] which declares the parameter and return types. Then follows the [function preamble] which declares a number of entities that can be referenced inside the function. In the example above, the preamble declares a single explicit stack slot, ss0.
After the preamble follows the [function body] which consists of [basic block]s (BBs), the first of which is the [entry block]. Every BB ends with a [terminator instruction], so execution can never fall through to the next BB without an explicit branch.
A .clif file consists of a sequence of independent function definitions:
Static single assignment form
The instructions in the function body use and produce values in SSA form. This means that every value is defined exactly once, and every use of a value must be dominated by the definition.
Cranelift does not have phi instructions but uses [BB parameter]s instead. A BB can be defined with a list of typed parameters. Whenever control is transferred to the BB, argument values for the parameters must be provided. When entering a function, the incoming function parameters are passed as arguments to the entry BB's parameters.
Instructions define zero, one, or more result values. All SSA values are either BB parameters or instruction results.
In the example above, the loop induction variable i is represented as three SSA values: In block2, v3 is the initial value. In the loop block block3, the BB parameter v4 represents the value of the induction variable during each iteration. Finally, v11 is computed as the induction variable value for the next iteration.
The cranelift_frontend crate contains utilities for translating from programs containing multiple assignments to the same variables into SSA form for Cranelift [IR].
Such variables can also be presented to Cranelift as [stack slot]s. Stack slots are accessed with the stack_store and stack_load instructions, and can have their address taken with stack_addr, which supports C-like programming languages where local variables can have their address taken.
Value types
All SSA values have a type which determines the size and shape (for SIMD vectors) of the value. Many instructions are polymorphic -- they can operate on different types.
Integer types
Integer values have a fixed size and can be interpreted as either signed or unsigned. Some instructions will interpret an operand as a signed or unsigned number, others don't care.
i8
i16
i32
i64
i128
Of these types, i32 and i64 are the most heavily-tested because of their use by Wasmtime. There are no known bugs in i8, i16, and i128, but their use may not be supported by all instructions in all backends (that is, they may cause the compiler to crash during code generation with an error that an instruction is unsupported).
The function valid_for_target within the fuzzgen function generator contains information about which instructions support which types.
Floating point types
The floating point types have the IEEE 754 semantics that are supported by most hardware, except that non-default rounding modes, unmasked exceptions, and exception flags are not currently supported.
There is currently no support for higher-precision types like quad-precision, double-double, or extended-precision, nor for narrower-precision types like half-precision.
NaNs are encoded following the IEEE 754-2008 recommendation, with quiet NaN being encoded with the MSB of the trailing significand set to 1, and signaling NaNs being indicated by the MSB of the trailing significand set to 0.
Except for bitwise and memory instructions, NaNs returned from arithmetic instructions are encoded as follows:
If all NaN inputs to an instruction are quiet NaNs with all bits of the trailing significand other than the MSB set to 0, the result is a quiet NaN with a nondeterministic sign bit and all bits of the trailing significand other than the MSB set to 0.
Otherwise the result is a quiet NaN with a nondeterministic sign bit and all bits of the trailing significand other than the MSB set to nondeterministic values.
f32
f64
SIMD vector types
A SIMD vector type represents a vector of values from one of the scalar types (integer, and floating point). Each scalar value in a SIMD type is called a lane. The number of lanes must be a power of two in the range 2-256.
i%Bx%N A SIMD vector of integers. The lane type iB is one of the integer types i8 ... i64.
f32x%N A SIMD vector of single precision floating point numbers.
f64x%N A SIMD vector of double precision floating point numbers.
Pseudo-types and type classes
These are not concrete types, but convenient names used to refer to real types in this reference.
iAddr A Pointer-sized integer representing an address.
iB Any of the scalar integer types i8 -- i64.
Int Any scalar or vector integer type: iB or iBxN.
fB Either of the floating point scalar types: f32 or f64.
Float Any scalar or vector floating point type: fB or fBxN.
%Tx%N Any SIMD vector type.
Mem Any type that can be stored in memory: Int or Float.
Testable iN
Immediate operand types
These types are not part of the normal SSA type system. They are used to indicate the different kinds of immediate operands on an instruction.
imm64 A 64-bit immediate integer. The value of this operand is interpreted as a signed two's complement integer. Instruction encodings may limit the valid range.
offset32 A signed 32-bit immediate address offset.
ieee32 A 32-bit immediate floating point number in the IEEE 754-2008 binary32 interchange format. All bit patterns are allowed.
ieee64 A 64-bit immediate floating point number in the IEEE 754-2008 binary64 interchange format. All bit patterns are allowed.
intcc An integer condition code. See the icmp instruction for details.
floatcc A floating point condition code. See the fcmp instruction for details.
The two IEEE floating point immediate types ieee32 and ieee64 are displayed as hexadecimal floating point literals in the textual [IR] format. Decimal floating point literals are not allowed because some computer systems can round differently when converting to binary. The hexadecimal floating point format is mostly the same as the one used by C99, but extended to represent all NaN bit patterns:
Normal numbers Compatible with C99: -0x1.Tpe where T are the trailing significand bits encoded as hexadecimal, and e is the unbiased exponent as a decimal number. ieee32 has 23 trailing significand bits. They are padded with an extra LSB to produce 6 hexadecimal digits. This is not necessary for ieee64 which has 52 trailing significand bits forming 13 hexadecimal digits with no padding.
Zeros Positive and negative zero are displayed as 0.0 and -0.0 respectively.
Subnormal numbers Compatible with C99: -0x0.Tpemin where T are the trailing significand bits encoded as hexadecimal, and emin is the minimum exponent as a decimal number.
Infinities Either -Inf or Inf.
Quiet NaNs Quiet NaNs have the MSB of the trailing significand set. If the remaining bits of the trailing significand are all zero, the value is displayed as -NaN or NaN. Otherwise, -NaN:0xT where T are the trailing significand bits encoded as hexadecimal.
Signaling NaNs Displayed as -sNaN:0xT.
Control flow
Branches transfer control to a new BB and provide values for the target BB's arguments, if it has any. Conditional branches terminate a BB, and transfer to the first BB if the condition is satisfied, and the second otherwise.
The br_table v, BB(args), [BB1(args)...BBn(args)] looks up the index v in the inline jump table given as the third argument, and jumps to that BB. If v is out of bounds for the jump table, the default BB (second argument) is used instead.
Traps stop the program because something went wrong. The exact behavior depends on the target instruction set architecture and operating system. There are explicit trap instructions defined below, but some instructions may also cause traps for certain input value. For example, udiv traps when the divisor is zero.
Function calls
A function call needs a target function and a [function signature]. The target function may be determined dynamically at runtime, but the signature must be known when the function call is compiled. The function signature describes how to call the function, including parameters, return values, and the calling convention:
A function's calling convention determines exactly how arguments and return values are passed, and how stack frames are managed. Since all of these details depend on both the instruction set /// architecture and possibly the operating system, a function's calling convention is only fully determined by a (TargetIsa, CallConv) tuple.
| Name | Description |
|---|---|
| sarg | pointer to a struct argument of the given size |
| sret | pointer to a return value in memory |
| vmctx | VM context pointer, which may contain pointers to heaps etc. |
| stack_limit | limit value for the size of the stack |
| Name | Description |
|---|---|
| fast | not-ABI-stable convention for best performance |
| cold | not-ABI-stable convention for infrequently executed code |
| system_v | System V-style convention used on many platforms |
| fastcall | Windows "fastcall" convention, also used for x64 and ARM |
The "not-ABI-stable" conventions do not follow an external specification and may change between versions of Cranelift.
The "fastcall" convention is not yet implemented.
Parameters and return values have flags whose meaning is mostly target dependent. These flags support interfacing with code produced by other compilers.
Functions that are called directly must be declared in the [function preamble]:
FN = [colocated] NAME signature Declare a function so it can be called directly.
This simple example illustrates direct function calls and signatures:
Indirect function calls use a signature declared in the preamble.
Memory
Cranelift provides fully general load and store instructions for accessing memory, as well as extending loads and truncating stores.
If the memory at the given address is not [addressable], the behavior of these instructions is undefined. If it is addressable but not [accessible], they [trap].
There are also more restricted operations for accessing specific types of memory objects.
Additionally, instructions are provided for handling multi-register addressing.
Memory operation flags
Loads and stores can have flags that loosen their semantics in order to enable optimizations.
| Flag | Description |
|---|---|
| notrap | Memory is assumed to be [accessible]. |
| aligned | Trapping allowed for misaligned accesses. |
| readonly | The data at the specified address will not modified between when this function is called and exited. |
When the accessible flag is set, the behavior is undefined if the memory is not [accessible].
Loads and stores are misaligned if the resultant address is not a multiple of the expected alignment. By default, misaligned loads and stores are allowed, but when the aligned flag is set, a misaligned memory access is allowed to [trap].
Explicit Stack Slots
One set of restricted memory operations access the current function's stack frame. The stack frame is divided into fixed-size stack slots that are allocated in the [function preamble]. Stack slots are not typed, they simply represent a contiguous sequence of [accessible] bytes in the stack frame.
SS = explicit_slot Bytes, Flags... Allocate a stack slot in the preamble.
The dedicated stack access instructions are easy for the compiler to reason about because stack slots and offsets are fixed at compile time. For example, the alignment of these stack memory accesses can be inferred from the offsets and stack slot alignments.
It's also possible to obtain the address of a stack slot, which can be used in unrestricted loads and stores.
The stack_addr instruction can be used to macro-expand the stack access instructions before instruction selection:
When Cranelift code is running in a sandbox, it can also be necessary to include stack overflow checks in the prologue.
Global values
A global value is an object whose value is not known at compile time. The value is computed at runtime by global_value, possibly using information provided by the linker via relocations. There are multiple kinds of global values using different methods for determining their value. Cranelift does not track the type of a global value, for they are just values stored in non-stack memory.
When Cranelift is generating code for a virtual machine environment, globals can be used to access data structures in the VM's runtime. This requires functions to have access to a VM context pointer which is used as the base address. Typically, the VM context pointer is passed as a hidden function argument to Cranelift functions.
Chains of global value expressions are possible, but cycles are not allowed. They will be caught by the IR verifier.
GV = vmctx Declare a global value of the address of the VM context struct.
A global value can also be derived by treating another global variable as a struct pointer and loading from one of its fields. This makes it possible to chase pointers into VM runtime data structures.
GV = load.Type BaseGV [Offset] Declare a global value pointed to by BaseGV plus Offset, with type Type.
GV = iadd_imm BaseGV, Offset Declare a global value which has the value of BaseGV offset by Offset.
GV = [colocated] symbol Name Declare a symbolic address global value.
Constant materialization
A few instructions have variants that take immediate operands, but in general an instruction is required to load a constant into an SSA value: iconst, f32const and f64const serve this purpose.
Bitwise operations
The bitwise operations and operate on any value type: Integers, and floating point numbers. When operating on integer or floating point types, the bitwise operations are working on the binary representation of the values.
The shift and rotate operations only work on integer types (scalar and vector). The shift amount does not have to be the same type as the value being shifted. Only the low B bits of the shift amount is significant.
When operating on an integer vector type, the shift amount is still a scalar type, and all the lanes are shifted the same amount. The shift amount is masked to the number of bits in a lane, not the full size of the vector type.
The bit-counting instructions are scalar only.
Floating point operations
These operations generally follow IEEE 754-2008 semantics.
Sign bit manipulations
The sign manipulating instructions work as bitwise operations, so they don't have special behavior for signaling NaN operands. The exponent and trailing significand bits are always preserved.
Minimum and maximum
These instructions return the larger or smaller of their operands. Note that unlike the IEEE 754-2008 minNum and maxNum operations, these instructions return NaN when either input is NaN.
When comparing zeroes, these instructions behave as if :math:-0.0 < 0.0.
Rounding
These instructions round their argument to a nearby integral value, still represented as a floating point number.
Extending loads and truncating stores
Most ISAs provide instructions that load an integer value smaller than a register and extends it to the width of the register. Similarly, store instructions that only write the low bits of an integer register are common.
In addition to the normal load and store instructions, Cranelift provides extending loads and truncation stores for 8, 16, and 32-bit memory accesses.
These instructions succeed, trap, or have undefined behavior, under the same conditions as normal loads and stores.
ISA-specific instructions
Target ISAs can define supplemental instructions that do not make sense to support generally.
x86
Instructions that can only be used by the x86 target ISA.
Codegen implementation instructions
Frontends don't need to emit the instructions in this section themselves; Cranelift will generate them automatically as needed.
Legalization operations
These instructions are used as helpers when legalizing types and operations for the target ISA.
Special register operations
The prologue and epilogue of a function needs to manipulate special registers like the stack pointer and the frame pointer. These instructions should not be used in regular code.
CPU flag operations
These operations are for working with the "flags" registers of some CPU architectures.
Live range splitting
Cranelift's register allocator assigns each SSA value to a register or a spill slot on the stack for its entire live range. Since the live range of an SSA value can be quite large, it is sometimes beneficial to split the live range into smaller parts.
A live range is split by creating new SSA values that are copies or the original value or each other. The copies are created by inserting copy, spill, or fill instructions, depending on whether the values are assigned to registers or stack slots.
This approach permits SSA form to be preserved throughout the register allocation pass and beyond.
Instruction groups
All of the shared instructions are part of the base instruction group.
Target ISAs may define further instructions in their own instruction groups.
Implementation limits
Cranelift's intermediate representation imposes some limits on the size of functions and the number of entities allowed. If these limits are exceeded, the implementation will panic.
Number of instructions in a function At most :math:2^{31} - 1.
Number of BBs in a function At most :math:2^{31} - 1.
Number of secondary values in a function At most :math:2^{31} - 1.
Other entities declared in the preamble At most :math:2^{32} - 1.
Number of arguments to a BB At most :math:2^{16}.
Number of arguments to a function At most :math:2^{16}.
Size of function call arguments on the stack At most :math:2^{32} - 1 bytes.