EmbIR#

This page is the reference for EmbIR, the intermediate representation between EmbCC's front end and its backends. It describes the data structures in src/ir/ir.h, every opcode, the textual form that embcc inspect ir prints and reads back, and the invariants the optimizer and the backends rely on. It is written for people who change IR generation, add a pass, or teach a backend a new operation.

Overview#

EmbIR is linear three-address code over virtual registers ("vregs"). One struct ir_unit holds one translation unit. Each function is an array of struct ir_ins in program order; control flow is expressed with labels and branches inside that array. There is no separate basic-block structure: the optimizer derives blocks and a control-flow graph when it needs them.

EmbIR is not in SSA form. Expression temporaries are written once in most cases, and the optimizer builds SSA on demand for mem2reg and takes it down again before the next pass (see The optimizer).

Values are typed by width and a few flags rather than by a type graph: an instruction says how many bytes it operates on, whether the operation is signed, and whether it is a floating-point operation. The ABI decisions that need C types (how an argument is passed, how a structure is returned) are made during IR generation and recorded on the instruction, so backends never consult the AST for them.

Where EmbIR sits in the pipeline#

The driver calls irgen(u) on the unit that semantic analysis has checked, then opt_run(iu, level), then one backend's codegen_unit* function. The DWARF emitter (src/debug/dwarf.c) and the unwind-table emitter (src/debug/eh.c) read the same struct ir_unit after code generation. See Architecture.

IR generation emits a function only if it is defined in the unit and is either external, referenced (used), or named main. At -O1 and above, the driver removes static functions that are unreachable after optimization before code generation; inspect ir reports the unit after that step.

Units, symbols and strings#

struct ir_unit#

struct ir_sym#

Instructions refer to functions and objects by index into ir_unit::syms (callee_sym, glob_sym). Symbols are interned by name and kind, so a function named by several instructions has one entry. ir_sym_func and ir_sym_global intern a symbol from an AST node and return its index.

The instructions also keep the AST pointers callee (a struct func *) and glob (a struct global *) beside the indices. Backends and the driver use the pointers to reach symbol-table indices and section offsets; the textual form uses the indices.

struct ir_str#

Each string literal is one entry with its bytes, its length including the terminating NUL, and off, its offset in .rodata. Offsets are assigned in order as strings are interned and become section offsets unchanged. ir_intern_string adds a string and returns its index; the driver uses it for strings that global initializers point at. IR_STRADDR names a string by index.

Functions#

struct ir_func#

Frame slots: struct ir_local#

Each frame slot carries the facts about its C type that the optimizer and the backends need, decided at IR generation. ir_locals_fill computes them from the function's slot types; the inliner calls it again after it adds slots.

Exception regions#

struct ir_eh describes one exception region, produced from the C front end's STMT_EHREGION (which the C++ lowering writes). lo and hi are the region's instruction range, lp_label is the landing pad's label, parent the enclosing region or -1, and acts/nacts the catch and cleanup actions. A call inside a region records 1 + region in eh_region. Code generation fills lp_off and the call sites (ir_add_csite); src/debug/eh.c turns them into .gcc_except_table.

Virtual registers#

Vregs are numbered from 0 to nvregs - 1 in three ranges:

A VLA's length is evaluated into its size slot where its declaration is reached. A block-scope typedef of a variably modified type is a STMT_DECL with is_vm_typedef set (the id its VLA nodes carry): IR generation evaluates the typedef's own array lengths into their size slots at that statement, and a later declaration, sizeof or array step that uses the name reads those slots instead of evaluating the lengths again. A typedef inside a loop is sized again on each pass.

A vreg below nvars is a frame slot. IR_LDVAR, IR_STVAR and IR_ADDR take a slot number, printed vN. A slot number used as an ordinary operand (%N with N < nvars) names the value in that slot; after mem2reg, a parameter that is never assigned is read this way, as the value the prologue stored there.

Temporaries are values. Most are written by exactly one instruction. The exceptions are deliberate:

• A merge temp receives a value on each path into a join. IR generation writes one for ?:, &&, || and the register/stack choice in va_arg, with an IR_MOV or IR_CONST on each path.
• After optimization, phi copies from mem2reg, partial-redundancy elimination and loop transformations write some temps more than once.

Code that treats a temp as a known value must first check that it has exactly one definition.

Widths#

Temporaries hold promoted values. An instruction's w field is the width of the value it operates on or produces:

w is the IR's width class, not the target's register width: on AVR an int operation still has w 4, and the backend narrows it. Pointer arithmetic uses the target's pointer size (8 on the LP64 targets, 4 on ARMv7-M and RV32).

A value whose C type is narrower than its class (only AVR's 2-byte int and unsigned) is kept equal to its extension, because a divide, a right shift, a comparison or a conversion to long reads all four bytes. After an operation that can carry out of the type's width, IR generation (int_wrap) emits an IR_EXT of the type's size, signed for int: after IR_ADD, IR_SUB, IR_MUL, IR_SHL and IR_NEG, a signed IR_DIV, and an unsigned IR_BNOT, in binary expressions, compound assignments and unary - and ~. The optimizer removes the extensions it can prove redundant.

Variables live in memory at their true size. IR_LDVAR and IR_LOAD read size bytes and extend to w (sign-extending when sign is set); IR_STVAR and IR_STORE truncate to size bytes.

Instructions#

struct ir_ins#

emit() in src/ir/irgen.c creates an instruction with dst, a, b and label set to -1, w and size set to 4 and sign set to 1, and stamps it with the current source location. Fields that do not apply to an opcode keep those defaults.

Call arguments: struct ir_arg#

Each argument of an IR_CALL, each entry of param_abi, and ret_abi is classified during IR generation.

Opcodes#

The enumeration enum ir_op has 63 opcodes, followed by IR_OPCOUNT, which is not an opcode. The order of the enumeration does not group opcodes by kind; test opcodes by name, never by numeric range. ir_opname returns an opcode's mnemonic and ir_op_from_name the reverse.

In the tables, Form is the textual form (see The textual form), W is w, S is size, and [s], [f], [v] are the flags.

Values and arithmetic#

With flt set, ADD, SUB, MUL, DIV, MOV and CMP operate on floating-point values of width w; w 16 with flt is a wide long double. IR generation negates a float or double by flipping its sign bit with an integer IR_XOR. A binary operation's b operand is printed #IMM when imm_b is set.

Conversions#

Frame slots and memory#

Addresses of symbols#

Calls and returns#

The end of the instruction array also returns: every backend emits an epilogue after the last instruction, so a void function may end without IR_RET. IR generation ends main (with an integer return type) with ret of the constant 0, as C99 requires for a main that reaches its closing brace; after a body whose every path returns, the optimizer removes it as unreachable.

Control flow#

A basic block starts at the first instruction, at every IR_LABEL, and after every IR_JMP, IR_BRZ, IR_BRNZ, IR_RET, IR_UD2, IR_IGOTO and IR_SWITCH. IR_RET and IR_UD2 have no successor; IR_JMP has its label; IR_BRZ and IR_BRNZ have their label and the next block; IR_SWITCH has its default and every table entry; IR_IGOTO has every label whose address an IR_LABELADDR in the function takes. Any other final instruction falls through to the next block (build_cfg in src/opt/opt.c).

A jump table (struct ir_jt) holds n label numbers. It belongs to the function and is referred to by index, so copies of an IR_SWITCH (made by the inliner or by switch threading) share one table. ir_jt_add creates a table with every entry -1; ir_jt_clone copies one with its labels renumbered. A dense switch becomes IR_SWITCH only where target_jump_tables() allows it (not on AVR); under -Os the density threshold is higher.

Atomics and barriers#

Atomic loads and stores are ordinary IR_LOAD and IR_STORE with vol set, with IR_FENCE placed around them by IR generation.

Variadic functions, inline assembly, exceptions#

struct ir_asm holds code/codelen (the bytes) and the inputs and outputs as struct ir_asm_op: temp (the input's value, or the output's address), reg (the fixed register), size, inout (a + operand whose register must hold the current value first) and mem (an m operand: the register holds the address and the template performs the access).

Vectors#

Vector operations work on 128-bit values. S is the element width in bytes, so a vector has 16 / S lanes. A vector temp occupies a 16-byte slot and is never given an integer register. These opcodes are produced only by the optimizer's vectorizer, which runs only for x86-64.

Producers and consumers#

IR generation (irgen, with src/arch/<arch>/irgen.c for va_arg and asm) produces every opcode except IR_SELECT and the vector opcodes, which only the optimizer creates. The optimizer also sets imm_b, and a backend's pre-codegen pass may set memoff.

A backend refuses an operation it cannot lower with a diagnostic that names the instruction, for example:

embcc: fa.c:1: error: the ARMv7-M backend cannot lower this operation at 64 bits yet (function fa) [frameaddr w=8 size=4]

The operand and control-flow knowledge of each opcode is spread over switches in the optimizer, the register allocator and each backend. The list of places to update when an opcode is added is in The optimizer.

Source locations#

Every instruction carries the line and column of the expression or statement it was generated from, or synth when it corresponds to no source construct (a prologue store, a landing pad's entry, the zero mem2reg gives a variable read before any write). IR generation stamps the location in emit(); a pass that replaces an instruction copies line, col and synth from the instruction it replaces. Code generation turns locations into the -g line table (ir_func::lines).

The textual form#

embcc inspect ir FILE.c [options] prints the IR of a C or C++ file as it stands after optimization at the -O level given, so the same command shows IR generation's output at -O0 and the optimizer's at -O2. inspect must be the first argument; the rest is an ordinary command line (--target=, -I, -D, -O, -f<pass>).

embcc inspect ir FILE.ir reads a file in the textual form with ir_parse and prints it again. With an -O level, the optimizer runs on the parsed unit before it is printed, which tests a pass on IR written to provoke it. A .ir file is accepted only by inspect ir; other modes treat it as C source.

embcc inspect ir sum.c -O2 -fno-vectorize -fno-unroll > sum.ir
embcc inspect ir sum.ir | cmp - sum.ir
embcc inspect ir -O2 case.ir

Example#

int sum(int *a, int n)
{
    int s = 0;
    for (int i = 0; i < n; i++)
        s += a[i];
    return s;
}

At -O0:

; EmbIR
func @sum nparams=2 nvars=4 vregs=23 labels=3 {
  local v0 size=8 align=8 intptr scalar
  local v1 size=4 align=4 intptr scalar
  local v2 size=4 align=4 intptr scalar
  local v3 size=4 align=4 intptr scalar
  %4 = const.4s 0	; 3:13
  stvar:4s v2, %4	; 3:9
  %5 = const.4s 0	; 4:18
  stvar:4s v3, %5	; 4:14
L0:
  %6 = ldvar.4:4s v3	; 4:21
  %7 = ldvar.4:4s v1	; 4:25
  %8 = cmp.4s lt %6, %7	; 4:21
  brz.4s %8 -> L2	; 4:14
  %9 = ldvar.4:4s v2	; 5:9
  %10 = ldvar.8:8 v0	; 5:14
  %11 = ldvar.4:4s v3	; 5:16
  %12 = ext.8:4s %11	; line 5
  %13 = const.8s 4	; 5:14
  %14 = mul.8s %12, %13	; 5:14
  %15 = add.8s %10, %14	; 5:14
  %16 = load.4:4s [%15]	; 5:14
  %17 = add.4s %9, %16	; 5:9
  stvar:4s v2, %17	; 5:9
L1:
  %18 = ldvar.4:4s v3	; line 4
  %19 = mov.4s %18	; line 4
  %20 = const.4s 1	; line 4
  %21 = add.4s %18, %20	; line 4
  stvar:4s v3, %21	; line 4
  jmp L0	; 5:9
L2:
  %22 = ldvar.4:4s v2	; 6:12
  ret %22	; 6:5
}

At -O2 -fno-vectorize -fno-unroll (x86-64): the locals are promoted to temps, the parameters are read directly as %0 and %1, the loop is rotated and walks a pointer, and %23, %24 and %28 are merge temps with several definitions.

; EmbIR
func @sum nparams=2 nvars=4 vregs=30 labels=5 {
  local v0 size=8 align=8 intptr scalar
  local v1 size=4 align=4 intptr scalar
  local v2 size=4 align=4 intptr scalar
  local v3 size=4 align=4 intptr scalar
  %25 = const.4 0	; compiler-synthesized
  %23 = mov.4 %25	; 4:14
  %24 = mov.4 %25	; 4:14
  %8 = cmp.4s lt %24, %1	; 4:21
  brz.4s %8 -> L2	; 4:14
  %28 = mov.8 %0	; line 5
L3:
  %16 = load.4:4s [%28]	; 5:14
  %17 = add.4s %16, %23	; 5:9
  %21 = add.4s %24, #1	; line 4
  %23 = mov.4 %17	; 5:9
  %24 = mov.4 %21	; 5:9
  %28 = add.8 %28, #4	; line 4
  %27 = cmp.4s lt %24, %1	; 4:21
  brnz.4s %27 -> L3	; 4:14
L2:
  ret %23	; 6:5
}

Layout of a unit#

The printer writes, in order:

1. The line ; EmbIR.

2. One line per string literal: strN = "BYTES", with \n, \t, " and \ escaped and the terminating NUL omitted. A blank line follows when there are strings.

3. One line per symbol: func @NAME [defined] [weak] [varargs] [sret] [nothrow] ;decl or data @NAME [defined] [weak] ;decl. A blank line follows when there are symbols.

4. Each function, separated by blank lines:

   func @NAME [static] [varargs] [alloca] [i128] nparams=N nvars=N vregs=N labels=N [scratch=N] [outgoing=N] {
     local vI size=N align=N [user_align=N] [volatile] [ldouble] [int128] [intptr] [scalar]
     ...one instruction per line...
   }
   

   scratch= and outgoing= are printed only when nonzero. There is one local line per frame slot; intptr is is_int_or_ptr and scalar is is_scalar_int_or_ptr.

Instructions#

A label is printed at column 0 as LN:. Every other instruction is indented two spaces and printed in the form given in the opcode tables, followed by a tab and its location:

Operands are spelled:

The mnemonic carries a suffix. For operations without a memory width it is .W followed by the flags; for those with one (ldvar, stvar, load, store, ext, the conversions, the atomics, the vector opcodes and select) it is .W:S followed by the flags. stvar and store omit .W. The flags are s (sign), f (flt) and v (vol), in that order. So ldvar.8:4s is a sign-extending 4-byte load into an 8-byte value, and load.4:1v a volatile byte load. A width or flag that is not set is not printed. Because IR generation sets sign by default, s also appears on operations whose result does not depend on it (add.4s, brz.4s, store:8s).

call prints varargs(N) when the callee is variadic, with N the number of named parameters, and sret when argument 0 is the result pointer.

Reading it back#

ir_parse(file, text) reads the form line by line and modifies text in place. It builds the unit's symbol table from the func ... ;decl and data ... ;decl lines, so a symbol must be declared before an instruction names it. A line that begins with ; is a comment. A func line without ;decl opens a function; } closes it.

An error stops the read with the file and line:

embcc: bad.ir:3: error: EmbIR: expected a known opcode

The round trip is tested by tests/golden/ir-roundtrip.sh: printing a parsed unit must reproduce the text it was parsed from, byte for byte, at -O0, -O1 and -O2, and for EmbCC's own sources at -O0 and -O2.

What the text does not carry#

The textual form encodes what passes need to be tested text-in, text-out. It does not carry:

• the classification of call arguments and return values (argv beyond the vreg, ret*, scratch, call_pcs), the function's param_abi, ret_abi and pcs;
• the width and float flag of ret and of call, and ret's structure size;
• natural, memoff and eh_region;
• exception regions, debug variables and variable scopes;
• is_scalar_float of a frame slot;
• an asm statement's bytes and operands.

A parsed unit therefore has src set to NULL and is used only to be printed: the driver does not optimize or generate code from it. Known limits of the reader:

• An asm instruction cannot be read back; the reader stops with EmbIR: 'asm' has no operand form here — teach irparse.c about it.
• The operator of armw (op '&') is not read back; the parsed instruction has imm 0.
• A line is copied into a 2048-byte buffer before its strings and key=value fields are read, so a longer line (a long string literal) is truncated.

Invariants and the verifier#

The following must hold for any IR handed to the optimizer or a backend:

• Every vreg is below nvregs and every label below nlabels.
• Every temp an instruction reads has a definition in the function. Frame slots (< nvars) may be read before they are written.
• Every label an IR_SWITCH names, including its default, is placed by an IR_LABEL in the same function.
• var_scope_lo and var_scope_hi index the current instruction array. A pass that renumbers instructions remaps or frees them.
• Every instruction has line set or is marked synth.
• IR_LANDING defines two temps, dst and b.

When the environment variable EMBCC_VERIFY is set (to any value), the optimizer checks the first four of these and the location rule for each function, once on the IR from IR generation and once after optimization. A failure is fatal and names the function, the check and when it failed (after irgen or after opt):

internal: NAME reads temp %N with no definition (after TAG) — an optimizer pass dropped a value that is still used

The verifier runs inside the optimizer, so it runs only at -O1 and above. The test suite sets EMBCC_VERIFY. The full list of messages is in The optimizer.

Related pages#

• Architecture: where IR generation and the optimizer sit in the compiler.
• The front end: the AST and type system IR generation reads.
• The optimizer: the passes over EmbIR.
• Backends: how each target lowers EmbIR to machine code.