Unions and Tagged Variants

How a frontend lowers unions and tagged variants to Esper IR: the layout of a tag beside a payload, and dispatching on it.

This page describes the current SSA builder and backend implementation. Its unversioned esp examples are compatibility snapshots, still accepted by the reader. Start with the new text walkthrough for esper 1 syntax and the roadmap for the library-first migration boundary.

Many languages have types that can hold one of several alternatives: C union, Rust enum, TypeScript discriminated unions, ML variants. This guide covers what a frontend does with them: how a union declaration describes the storage, how a tag and a payload are laid out next to each other, and how a switch on the tag reaches the arm that knows the payload’s real type.

First-class union types

A union declaration overlays its members at offset 0. Declaring one is the same call that declares a struct, with the last argument set:

EsperTypeRef members[2] = {ESP_TYPE_I32, ESP_TYPE_F32};
const char *names[2] = {"as_int", "as_float"};
uint32_t value = esper_unit_add_struct(unit, "Value", members, names, 2, true);

What the declaration buys is layout and naming. esper_type_size reports the widest member’s size, esper_type_align the strictest alignment, and esper_member_offset returns 0 for every member. Those are the numbers a frontend would otherwise compute per target, and they are what the debug information carries a member’s name into.

A union value is built with union.new, not struct.new. struct.new takes one operand per declared member, and a union has one live member, so the member index has to be named:

%1 = union.new Value 1, %0    // %0 is the f32, so it is member 1
%2 = field i32 %1, 0          // read it back as the i32 member

esper_build_union_new is the same thing from the builder, and struct.new refuses a union rather than guessing which operand is the live one.

Reading a member other than the one stored is a reinterpretation of the same bytes. Only the bytes the stored member occupies are written, so reading a wider member after storing a narrower one sees storage union.new did not set.

A frontend can also reach a union through its storage, which is what the rest of this guide does.

One slot, read at two types

The union’s own storage is the reinterpretation. Store through the member whose type produced the value, load through the member whose type the reader wants, and let EsperMemAccess say which member each access is:

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef members[2] = {ESP_TYPE_I32, ESP_TYPE_F32};
  const char *names[2] = {"as_int", "as_float"};

  // The last argument is what makes it a union rather than a struct.
  uint32_t value = esper_unit_add_struct(unit, "Value", members, names, 2, true);
  EsperTypeRef value_ty = esper_tref_agg(value);

  EsperTypeRef params[1] = {ESP_TYPE_F32};
  EsperTypeRef rets[1] = {ESP_TYPE_I32};

  EsperBuilder *b = esper_build_begin(unit, "bits_of", params, 1, rets, 1);
  esper_build_bind(b, esper_build_block(b, "entry"));

  EsperVal size = esper_build_ldi(b, ESP_TYPE_I32,
                                  (int32_t)esper_type_size(unit, value_ty));
  EsperVal slot = esper_build_alloc(b, ESP_OP_SALLOC, size);

  // Both accesses name the same union at offset zero, and differ only
  // in which member they claim to be reaching.
  EsperMemAccess as_float = {0};
  as_float.type_index = value;
  as_float.member_index = 1;
  esper_build_store_at(b, ESP_OP_STORE, ESP_TYPE_F32, slot,
                       esper_build_param(b, 0), &as_float);

  EsperMemAccess as_int = {0};
  as_int.type_index = value;
  as_int.member_index = 0;
  EsperVal bits = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_I32, slot,
                                      &as_int);
  esper_build_ret(b, &bits, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "bits_of: %s\n", esper_builder_last_error(b));
  esper_builder_free(b);
}
type Value = union {
  i32 as_int,
  f32 as_float,
}

func $bits_of(%0 f32) -> i32 {
entry:
  %1 = ldi i32 4
  %2 = salloc %1
  store f32 %2, %0 [type=Value, field=as_float]
  %4 = load i32 %2 [type=Value, field=as_int]
  ret i32 %4
}

Neither the size nor the offsets are written down: the frontend asks the type table, and the answer is already correct for the target the unit was laid out for.

Bit-cast without memory

When the reinterpretation is between two register-sized types and no union type is wanted, bitcast does it with no storage at all:

%0 = ldi i32 0x3F800000               // IEEE 754 for 1.0f
%1 = bitcast f32 %0                   // now 1.0

The destination type is written; the source type is not, because it is already known from the instruction that defined the operand. esper_build_unary with ESP_OP_BITCAST is the builder’s spelling.

Tagged unions (discriminated variants)

A tagged union is a discriminant next to a union payload, wrapped in an outer struct. This is the shape a frontend hits first, so it is worth seeing whole.

enum Shape {
    case circle(radius: Double)               // tag 0
    case rect(width: Double, height: Double)  // tag 1
}

The layout, and the constructor

Four declarations describe it: one struct per variant’s payload, a union that overlays them, and an outer struct holding the tag and that union. Once they exist, esper_type_size and esper_member_offset say where everything sits, so the constructor never writes a literal offset:

/// Declares the four types a tagged union needs, then lets the layout
/// helper say where the tag and the payload sit.
static uint32_t declare_shape(EsperUnit *unit) {
  EsperTypeRef radius[1] = {ESP_TYPE_F64};
  const char *radius_name[1] = {"radius"};
  uint32_t circle = esper_unit_add_struct(unit, "CirclePayload", radius,
                                          radius_name, 1, false);

  EsperTypeRef sides[2] = {ESP_TYPE_F64, ESP_TYPE_F64};
  const char *side_names[2] = {"width", "height"};
  uint32_t rect = esper_unit_add_struct(unit, "RectPayload", sides, side_names,
                                        2, false);

  EsperTypeRef arms[2] = {esper_tref_agg(circle),
                          esper_tref_agg(rect)};
  const char *arm_names[2] = {"circle", "rect"};
  uint32_t payload = esper_unit_add_struct(unit, "ShapePayload", arms,
                                           arm_names, 2, true);

  EsperTypeRef fields[2] = {ESP_TYPE_I32,
                            esper_tref_agg(payload)};
  const char *field_names[2] = {"tag", "payload"};
  return esper_unit_add_struct(unit, "Shape", fields, field_names, 2, false);
}

static void esper_doc_build(EsperUnit *unit) {
  uint32_t shape = declare_shape(unit);
  EsperTypeRef shape_ty = esper_tref_agg(shape);

  // The frontend asks for the offsets rather than computing them.
  uint32_t size = esper_type_size(unit, shape_ty);
  uint32_t payload_at = esper_member_offset(unit, shape_ty, 1, NULL);

  EsperTypeRef params[1] = {ESP_TYPE_F64};
  EsperTypeRef rets[1] = {ESP_TYPE_PTR};

  EsperBuilder *b = esper_build_begin(unit, "make_circle", params, 1, rets, 1);
  esper_build_bind(b, esper_build_block(b, "entry"));

  // The heap, not the frame: the caller outlives this function.
  EsperVal bytes = esper_build_ldi(b, ESP_TYPE_I32, (int32_t)size);
  EsperVal p = esper_build_alloc(b, ESP_OP_HALLOC, bytes);

  EsperMemAccess at = {0};
  at.type_index = shape;
  at.member_index = 0;
  esper_build_store_at(b, ESP_OP_STORE, ESP_TYPE_I32, p,
                       esper_build_ldi(b, ESP_TYPE_I32, 0), &at);

  at.member_index = 1;
  at.byte_offset = payload_at;
  esper_build_store_at(b, ESP_OP_STORE, ESP_TYPE_F64, p,
                       esper_build_param(b, 0), &at);

  esper_build_ret(b, &p, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "make_circle: %s\n", esper_builder_last_error(b));
  esper_builder_free(b);
}
type CirclePayload = struct {
  f64 radius,
}
type RectPayload = struct {
  f64 width,
  f64 height,
}
type ShapePayload = union {
  CirclePayload circle,
  RectPayload rect,
}
type Shape = struct {
  i32 tag,
  ShapePayload payload,
}

func $make_circle(%0 f64) -> ptr {
entry:
  %1 = ldi i32 24
  %2 = halloc %1
  %3 = ldi i32 0
  store i32 %2, %3 [type=Shape, field=tag]
  store f64 %2, %0, byte=8 [type=Shape, field=payload]
  ret ptr %2
}

Shape comes out 24 bytes: the i32 tag at offset 0, four bytes of padding so the f64-aligned payload starts at offset 8, and the larger of the two payloads (16 bytes for rect) after it. The 24 and the byte=8 in the printed IR are what esper_type_size and esper_member_offset returned, not constants the frontend chose. Point the unit at a target with a different pointer width through esper_unit_layout_for and the same code emits the offsets that target needs.

ESP_OP_HALLOC rather than ESP_OP_SALLOC because the pointer outlives the call. A frame allocation returned to a caller is a dangling pointer, and nothing in the IR will catch it.

Dispatching on the tag

The tag read is one annotated load. Each arm then reads the payload at the offset the layout gave, at the type that arm knows the payload to be: one f64 in the circle arm, two in the rect arm, both starting from the same byte.

/// Reads the tag, branches on it, and reads the payload at the type the
/// arm expects. Both arms load from the same offset.
static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef radius[1] = {ESP_TYPE_F64};
  const char *radius_name[1] = {"radius"};
  uint32_t circle_p = esper_unit_add_struct(unit, "CirclePayload", radius,
                                            radius_name, 1, false);

  EsperTypeRef sides[2] = {ESP_TYPE_F64, ESP_TYPE_F64};
  const char *side_names[2] = {"width", "height"};
  uint32_t rect_p = esper_unit_add_struct(unit, "RectPayload", sides,
                                          side_names, 2, false);

  EsperTypeRef arms[2] = {esper_tref_agg(circle_p),
                          esper_tref_agg(rect_p)};
  const char *arm_names[2] = {"circle", "rect"};
  uint32_t payload_ty = esper_unit_add_struct(unit, "ShapePayload", arms,
                                              arm_names, 2, true);

  EsperTypeRef fields[2] = {ESP_TYPE_I32,
                            esper_tref_agg(payload_ty)};
  const char *field_names[2] = {"tag", "payload"};
  uint32_t shape = esper_unit_add_struct(unit, "Shape", fields, field_names, 2,
                                         false);

  EsperTypeRef shape_ty = esper_tref_agg(shape);
  uint32_t base = esper_member_offset(unit, shape_ty, 1, NULL);
  uint32_t pi = esper_unit_add_const_float(unit, ESP_TYPE_F64,
                                           3.14159265358979);

  EsperTypeRef params[1] = {ESP_TYPE_PTR};
  EsperTypeRef rets[1] = {ESP_TYPE_F64};

  EsperBuilder *b = esper_build_begin(unit, "area", params, 1, rets, 1);
  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId is_circle = esper_build_block(b, "circle");
  EsperBlockId is_rect = esper_build_block(b, "rect");

  esper_build_bind(b, entry);
  EsperVal p = esper_build_param(b, 0);

  EsperMemAccess tag = {0};
  tag.type_index = shape;
  tag.member_index = 0;
  EsperVal which = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_I32, p, &tag);
  EsperVal zero = esper_build_unary(b, ESP_OP_EQZ, ESP_TYPE_I32, which);
  esper_build_jmp_if(b, zero, is_circle, is_rect);

  // The circle arm reads one f64 where the rect arm reads two.
  EsperMemAccess at = {0};
  at.type_index = shape;
  at.member_index = 1;
  at.byte_offset = base;

  esper_build_bind(b, is_circle);
  EsperVal r = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_F64, p, &at);
  EsperVal r2 = esper_build_binary(b, ESP_OP_FMUL, ESP_TYPE_F64, r, r);
  EsperVal k = esper_build_ldc(b, ESP_TYPE_F64, pi);
  EsperVal disc = esper_build_binary(b, ESP_OP_FMUL, ESP_TYPE_F64, k, r2);
  esper_build_ret(b, &disc, 1);

  esper_build_bind(b, is_rect);
  EsperVal w = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_F64, p, &at);
  at.byte_offset = base + esper_member_offset(unit, esper_tref_agg(rect_p), 1,
                                              NULL);
  EsperVal h = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_F64, p, &at);
  EsperVal box = esper_build_binary(b, ESP_OP_FMUL, ESP_TYPE_F64, w, h);
  esper_build_ret(b, &box, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "area: %s\n", esper_builder_last_error(b));
  esper_builder_free(b);
}
type CirclePayload = struct {
  f64 radius,
}
type RectPayload = struct {
  f64 width,
  f64 height,
}
type ShapePayload = union {
  CirclePayload circle,
  RectPayload rect,
}
type Shape = struct {
  i32 tag,
  ShapePayload payload,
}

const c0 f64 = 3.14159265358979

func $area(%0 ptr) -> f64 {
entry:
  %1 = load i32 %0 [type=Shape, field=tag]
  %2 = eqz i32 %1
  jmp.if %2 circle rect

circle:
  %4 = load f64 %0, byte=8 [type=Shape, field=payload]
  %5 = fmul f64 %4, %4
  %6 = ldc f64 c0
  %7 = fmul f64 %6, %5
  ret f64 %7

rect:
  %9 = load f64 %0, byte=8 [type=Shape, field=payload]
  %10 = load f64 %0, byte=16 [type=Shape, field=payload]
  %11 = fmul f64 %9, %10
  ret f64 %11
}

Both arms load from byte=8. That is the whole trick: the union’s members overlap, so the arm’s own type is the only thing that decides how those bytes are read.

The offsets in the two arms are computed relative to base, so the payload structs’ own layouts compose rather than being flattened by hand. A three-field variant needs no new arithmetic in the frontend, only another esper_member_offset.

More arms than a branch can carry

A variant type with more than two cases does not want a chain of comparisons. jmp.table takes one target per tag value plus a default, and the blocks are created before the table names them, so nothing has to be back-patched:

/// Dispatch on a tag with more arms than a conditional branch can carry.
static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef fields[2] = {ESP_TYPE_I32, ESP_TYPE_I32};
  const char *names[2] = {"tag", "payload"};
  uint32_t node = esper_unit_add_struct(unit, "Node", fields, names, 2, false);
  EsperTypeRef node_ty = esper_tref_agg(node);

  EsperTypeRef params[1] = {ESP_TYPE_PTR};
  EsperTypeRef rets[1] = {ESP_TYPE_I32};

  EsperBuilder *b = esper_build_begin(unit, "eval", params, 1, rets, 1);
  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId arms[3];
  arms[0] = esper_build_block(b, "lit");
  arms[1] = esper_build_block(b, "neg");
  arms[2] = esper_build_block(b, "dbl");
  EsperBlockId bad = esper_build_block(b, "unreachable_tag");

  esper_build_bind(b, entry);
  EsperVal p = esper_build_param(b, 0);

  EsperMemAccess tag = {0};
  tag.type_index = node;
  tag.member_index = 0;
  EsperVal which = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_I32, p, &tag);

  // One target per variant, and a default for a tag the frontend never
  // emits. The blocks exist already, so no back-patching is needed.
  esper_build_jmp_table(b, which, arms, 3, bad);

  EsperMemAccess body = {0};
  body.type_index = node;
  body.member_index = 1;
  body.byte_offset = esper_member_offset(unit, node_ty, 1, NULL);

  esper_build_bind(b, arms[0]);
  EsperVal lit = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_I32, p, &body);
  esper_build_ret(b, &lit, 1);

  esper_build_bind(b, arms[1]);
  EsperVal n = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_I32, p, &body);
  EsperVal neg = esper_build_unary(b, ESP_OP_NEG, ESP_TYPE_I32, n);
  esper_build_ret(b, &neg, 1);

  esper_build_bind(b, arms[2]);
  EsperVal d = esper_build_load_at(b, ESP_OP_LOAD, ESP_TYPE_I32, p, &body);
  EsperVal twice = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I32, d, d);
  esper_build_ret(b, &twice, 1);

  esper_build_bind(b, bad);
  EsperVal zero = esper_build_ldi(b, ESP_TYPE_I32, 0);
  esper_build_ret(b, &zero, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "eval: %s\n", esper_builder_last_error(b));
  esper_builder_free(b);
}
type Node = struct {
  i32 tag,
  i32 payload,
}

func $eval(%0 ptr) -> i32 {
entry:
  %1 = load i32 %0 [type=Node, field=tag]
  jmp.table %1 [lit, neg, dbl] unreachable_tag

lit:
  %3 = load i32 %0, byte=4 [type=Node, field=payload]
  ret i32 %3

neg:
  %5 = load i32 %0, byte=4 [type=Node, field=payload]
  %6 = neg i32 %5
  ret i32 %6

dbl:
  %8 = load i32 %0, byte=4 [type=Node, field=payload]
  %9 = add i32 %8, %8
  ret i32 %9

unreachable_tag:
  %11 = ldi i32 0
  ret i32 %11
}

The default block is not optional. A tag the frontend proved it never emits still needs somewhere for the table to send an out-of-range index, and a block that traps or returns a sentinel is cheaper than the alternative of a bounds check the frontend writes itself.

Option and Maybe types

An Option<T> is a tagged union with two variants, and the pattern above covers it. For pointer-sized payloads the null-pointer optimization removes the tag entirely: the pointer is its own discriminant.

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef params[2] = {ESP_TYPE_PTR, ESP_TYPE_PTR};
  EsperTypeRef rets[1] = {ESP_TYPE_PTR};

  EsperBuilder *b = esper_build_begin(unit, "unwrap_or", params, 2, rets, 1);
  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId use_default = esper_build_block(b, "use_default");
  EsperBlockId use_value = esper_build_block(b, "use_value");

  esper_build_bind(b, entry);
  EsperVal opt = esper_build_param(b, 0);

  // None is the null pointer, so the tag is the pointer itself.
  EsperVal none = esper_build_unary(b, ESP_OP_EQZ, ESP_TYPE_PTR, opt);
  esper_build_jmp_if(b, none, use_default, use_value);

  esper_build_bind(b, use_default);
  EsperVal fallback = esper_build_param(b, 1);
  esper_build_ret(b, &fallback, 1);

  esper_build_bind(b, use_value);
  esper_build_ret(b, &opt, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "unwrap_or: %s\n", esper_builder_last_error(b));
  esper_builder_free(b);
}
func $unwrap_or(%0 ptr, %1 ptr) -> ptr {
entry:
  %2 = eqz ptr %0
  jmp.if %2 use_default use_value

use_default:
  ret ptr %1

use_value:
  ret ptr %0
}

Blocks are bound in creation order, which is why use_default is written before use_value even though the branch names them the other way round. The branch does not care; a block is referenceable as a target from the moment esper_build_block returns.

Offsets as pointer arithmetic

EsperMemAccess is not the only way to reach a member. A frontend that already computes addresses can emit the offset as a value and add it, which is the same program with the displacement spelled out:

%1 = ldi i32 8
%2 = add i64 %0, %1
%3 = load f64 %2                // payload, as an f64

The annotated form is preferable where the frontend knows which member it is reaching: the offset does not become an instruction, and the type and field attribution reaches the debug information. The arithmetic form is what to use when the offset is not a compile-time constant, which is the case a type declaration cannot describe: a record with a trailing flexible array, or a layout an external ABI dictates.

Nothing requires a load’s type to match a declared member either way. The union declaration describes the storage; the access decides how those bytes are read. That is the whole of what a union is in this IR, and it is why the tag has to be carried alongside rather than inferred.