Reading IR back

This page describes the current SSA builder and backend implementation. Start with the new text walkthrough for esper 1 syntax and the roadmap for the library-first migration boundary.

Most of this documentation is about producing IR. This page is about the other direction: a unit already exists, and something wants to look at it. A custom backend, a viewer, a linter, a language server that reports what the optimizer did to a function, a test that asserts a pass fired.

None of those may include src/core/esp_internal.h. That header holds the IR’s layout and is not installed. Everything on this page is in esper.h, and every handle it deals in is a block index, a function index, or an SSA id rather than a pointer into instruction storage, so nothing here can be invalidated by the unit growing.

Functions, blocks, and the graph between them

A unit holds functions, a function holds blocks, and a block owns a contiguous run of the function’s instruction stream. esper_block_first and esper_block_last are positions in that stream, and the last instruction of a block is always its terminator.

The successors of a block come from esper_block_succ_count and esper_block_succ without the caller having to know which opcodes branch. That matters more than it sounds: a block whose last instruction is not a terminator falls through to the next one in order, and reading the opcode yourself would miss that.

static void esper_doc_run(void) {
  const char *src =
    "func $abs(%0 i32) -> i32 {\n"
    "entry:\n"
    "  %1 = ldi i32 0\n"
    "  %2 = lt.s i32 %0, %1\n"
    "  jmp.if %2 neg pos\n"
    "neg:\n"
    "  %4 = neg i32 %0\n"
    "  ret i32 %4\n"
    "pos:\n"
    "  ret i32 %0\n"
    "}\n";

  EsperUnit *unit = esper_parse_string(src, strlen(src), "abs");
  const EsperFunc *func = esper_unit_func(unit, 0);

  printf("%s takes %u, returns %u\n", esper_func_name(func),
         esper_func_param_count(func), esper_func_ret_count(func));

  for (uint32_t b = 0; b < esper_func_block_count(func); b++) {
    const EsperBlock *block = esper_func_block(func, b);

    printf("  %s: %u instructions ->", esper_block_label(block),
           esper_block_inst_count(block));

    // Both arms of a conditional can enter the same block, so a
    // successor may appear twice. That is one predecessor and two
    // edges, each carrying its own arguments.
    for (uint32_t e = 0; e < esper_block_succ_count(func, b); e++) {
      uint32_t s = esper_block_succ(func, b, e);
      printf(" %s", esper_block_label(esper_func_block(func, s)));
    }

    printf("\n");
  }

  esper_unit_free(unit);
}

abs takes 1, returns 1
  entry: 3 instructions -> neg pos
  neg: 2 instructions ->
  pos: 1 instructions ->

esper_unit_func_count and esper_unit_func enumerate functions; esper_unit_find_func looks one up by name. A function with esper_func_is_extern true is a declaration with no body, so it has no blocks to walk.

Operands are not the whole instruction

An instruction’s operands live in a flat run of 32-bit slots, and this is the part a consumer cannot guess. Not every slot is an SSA value. A call names its callee in slot zero. A branch names its targets. A conditional branch that carries block arguments spends two more slots on how many it carries each way.

So there are two ways to read an instruction, and they answer different questions:

esper_inst_operand_count and esper_inst_operand hand out only the SSA operands, numbered densely. This is what you want when the question is “which values does this read”.
esper_inst_slot_count, esper_inst_slot_kind and esper_inst_slot hand out the run as it is, each slot tagged with what it means. This is what you want when the question is “what is this instruction made of”.

Reading raw slots as though they were operands is the single most common way to get this wrong, and it fails quietly: a block index and an SSA id are both a uint32_t, so substituting one for the other compiles and produces a program that branches somewhere else.

static const char *kind_name(EsperSlotKind kind) {
  switch (kind) {
  case ESP_SLOT_SSA:        return "value";
  case ESP_SLOT_BLOCK:      return "block";
  case ESP_SLOT_FUNC:       return "func";
  case ESP_SLOT_GLOBAL:     return "global";
  case ESP_SLOT_CONST:      return "const";
  case ESP_SLOT_IMMEDIATE:  return "immediate";
  case ESP_SLOT_BRANCH_TAB: return "table";
  default:                  return "unused";
  }
}

static void esper_doc_run(void) {
  const char *src =
    "func $pick(%0 i32, %1 i32) -> i32 {\n"
    "entry:\n"
    "  jmp.if %0 hit(%1) miss\n"
    "hit(%3 i32):\n"
    "  ret i32 %3\n"
    "miss:\n"
    "  ret i32 %1\n"
    "}\n";

  EsperUnit *unit = esper_parse_string(src, strlen(src), "pick");
  const EsperFunc *func = esper_unit_func(unit, 0);

  for (uint32_t i = 0; i < esper_func_inst_count(func); i++) {
    const EsperInst *inst = esper_func_inst(func, i);

    printf("%-12s", esper_op_name(esper_inst_op(inst)));

    for (uint32_t s = 0; s < esper_inst_slot_count(inst); s++) {
      printf(" %s=%u", kind_name(esper_inst_slot_kind(inst, s)),
             esper_inst_slot(inst, s));
    }

    printf("\n");
  }

  esper_unit_free(unit);
}

jmp.if       value=0 block=1 block=2 immediate=1 immediate=0 value=1
param       
ret          value=3
ret          value=1

Six slots of four different kinds, and only two of them are values: the condition, the two targets, the argument counts for each arm, and the one argument the taken arm carries. esper_inst_operand_count on that same instruction reports two.

For the common branch questions there are direct accessors that save the arithmetic: esper_jmp_target, esper_inst_edge_arg_count and esper_inst_edge_arg for what an edge carries, esper_block_param_count and esper_block_param for what a block takes, and esper_branch_table_case_count, esper_branch_table_case and esper_branch_table_default for a jump table.

Values and their types

An SSA id is a position, not a name. Value i for i below esper_func_param_count is parameter i; above that it is the instruction at index id - param_count. esper_func_value_inst does that conversion, and esper_inst_result goes the other way.

esper_func_value_type gives the type of a value. Note that a comparison names the type of its operands, so eq ptr records ptr while producing a boolean; esper_op_yields_bool is what tells you the difference, and esper_op_result_type applies it.

The type table

Aggregates live in a per-unit table. The accessors come in two families, and the difference between them is worth stating plainly because both take a uint32_t and mixing them compiles:

The name family takes a type index: esper_type_name, esper_type_kind, esper_type_member_count, esper_type_member_name, esper_type_member_type, esper_type_array_count.
The layout family takes a type ref: esper_type_size, esper_type_align, esper_member_offset.

esper_tref_agg(index) converts an index to a ref, and esper_tref_agg_index converts back. esper_tref_is_aggregate says whether a ref names the table at all, since a ref can equally describe a primitive.

static void esper_doc_run(void) {
  const char *src =
    "type Point = struct {\n"
    "  i32 x,\n"
    "  i32 y,\n"
    "}\n"
    "\n"
    "func $sum(%0 Point) -> i32 {\n"
    "entry:\n"
    "  %1 = field i32 %0, 0\n"
    "  %2 = field i32 %0, 1\n"
    "  %3 = add i32 %1, %2\n"
    "  ret i32 %3\n"
    "}\n";

  EsperUnit *unit = esper_parse_string(src, strlen(src), "point");

  for (uint32_t t = 0; t < esper_unit_type_count(unit); t++) {
    // The layout accessors take a type ref where the name accessors
    // take the index. Both are a u32, so the conversion is the
    // caller's to remember.
    EsperTypeRef ref = esper_tref_agg(t);

    printf("%s: %u bytes, align %u\n", esper_type_name(unit, t),
           esper_type_size(unit, ref), esper_type_align(unit, ref));

    for (uint32_t m = 0; m < esper_type_member_count(unit, t); m++) {
      printf("  %s at +%u\n", esper_type_member_name(unit, t, m),
             esper_member_offset(unit, ref, m, NULL));
    }
  }

  esper_unit_free(unit);
}

Point: 8 bytes, align 4
  x at +0
  y at +4

Sizes and offsets depend on the pointer width, so they are computed for a target. esper_unit_layout_for recomputes them and esper_unit_layout_matches reports whether the cached ones belong to the target you are about to generate for. Every backend asks before emitting, because a mismatch that is not refused becomes offsets that are quietly wrong.

What the frontend called things

Debug information is a second layer over the same IR, and it is what lets a tool report in the frontend’s terms rather than in SSA ids.

esper_func_source, esper_func_line and esper_func_column give a function’s position in the frontend’s own source, and esper_inst_has_debug_loc, esper_inst_line and esper_inst_column do the same per instruction.
esper_unit_source_count and the source table turn a source index into a file name.
esper_func_scope_count and esper_func_scope walk the lexical scopes, each with a parent and a range of instructions it covers.
esper_func_local_count and esper_func_local walk the named values, each with a name, a type, the scope it belongs to, and the SSA id or stack slot holding it.

A local whose esper_local_value is ESP_VAL_NONE had no value left after optimization. That is normal and it is why esper_locals_prune exists: it drops the locals whose values no longer exist rather than leaving a debugger to print something that is not there.

Globals, constants, and signatures

esper_unit_global_count walks the globals, each with a name, a type, mutability, an initializer constant index, and a position. esper_unit_global_is_extern marks the ones defined elsewhere, which is the set that must keep its names.

esper_unit_const_count and esper_unit_const_type walk the constant table. The reader to use depends on the type: an integer, a float, a string, or an aggregate blob, and the aggregate case is unpacked with the esper_const_agg_* accessors rather than read as bytes.

esper_unit_signature_count and the signature accessors describe the call shapes an indirect call can name, which is what esper_build_call_indirect takes an index into.

Printing

esper_print writes the whole unit as .esp text, which is the fastest way to see what a pass did. esper_op_name gives a single opcode’s mnemonic, and it is available whether or not the text format was compiled into the build, so a tool that names instructions does not have to depend on the printer.