Larva IR

Larva IR is the form a program takes between HIR and machine code. A language writes HIR; Larva.Hir.Lowering turns classes, interfaces, closures, strings and exceptions into IR; the IR is checked, linked, made concrete and handed to a back end: the Larva VM (through IL), LLVM, the direct x86-64 back end or WebAssembly.

 HIR (.lva)              Larva IR                                       code
 ----------  lowering   ---------------------------------------------   ------------------
 classes,    ------->   structs, gc/box/&/* handles, basic blocks   --> IL (.lvm, the VM)
 interfaces,            type check -> region check -> borrow check  --> LLVM IR -> .obj/.exe
 closures,              link (.lvo objects) -> monomorphize         --> x86-64 (own back end)
 async ...                                                          --> WebAssembly

The design document puts the split this way: the program always goes down the same road. The frontend writes HIR, Larva lowers it to IR, and the back ends generate code. HIR is the truth about a program, with full metadata; IR is deliberately small and low level, so that every check and every back end works on one simple language, whatever source language the program came from.

The code lives in Larva.IR:

A first look

This Antril program allocates an object, builds an array and loops over it:

import System;

into namespace Cells
{
	public class Cell
	{
		public:
			i64 value;
	}

	Sum(i64[] items) : i64
	{
		i64 total = 0;
		loop (i64 item in items)
			total = total + item;
		return total;
	}

	Main()
	{
		Cell cell = new Cell();
		cell.value = Sum([1, 2, 3]);
		Console.WriteLine(cell.value);
	}
}

After lowering, Sum is this IR (the listing is what IrPrinter prints for the lowered function):

fn Cells.$Module.Sum(mut _1: gc [i64]) -> i64 {
    let mut _0: i64;            // return
    let mut _2: i64;            // total
    let mut _3: gc [i64];       // $items1
    let mut _4: i32;            // $index2
    let mut _5: i64;            // item
    let mut _6: bool;
    let mut _7: i32;
    let mut _8: u64;
    let mut _9: i32;

    bb0: {
        _2 = const 0_i64;
        _3 = copy _1;
        _4 = const 0_i32;
        goto -> bb1;
    }

    bb1: {
        _8 = Len((*_3));
        _7 = copy _8 as i32;
        _6 = Lt(copy _4, copy _7);
        if copy _6 -> [true: bb2, false: bb4];
    }

    bb2: {
        _5 = copy (*_3)[_4];
        _2 = Add(copy _2, copy _5);
        goto -> bb3;
    }

    bb3: {
        _9 = copy _4;
        _4 = Add(copy _4, const 1_i32);
        goto -> bb1;
    }

    bb4: {
        _0 = copy _2;
        return;
    }
}

And Main:

unsafe fn Cells.$Module.Main() -> () {
    let mut _0: ();             // return
    let mut _1: gc Cells.Cell;  // cell
    let mut _2: Cells.Cell;
    let mut _3: *mut Cells.Cell$vt;
    let mut _4: gc Cells.Cell;
    let mut _5: gc [i64];
    let mut _6: gc [i64];
    let mut _7: u64;
    let mut _8: ();

    bb0: {
        _2 = filler Cells.Cell;
        _2.0 = classid Cells.Cell;
        _3 = Cells.Cell.$vtable() -> bb1;
    }

    bb1: {
        _2.1 = copy _3 as *mut Larva.Object$vt;
        _4 = gc move _2;
        _1 = copy _4;
        _6 = gc [i64; const 3_u64];
        _7 = const 0_u64;
        (*_6)[_7] = const 1_i64;
        _7 = const 1_u64;
        (*_6)[_7] = const 2_i64;
        _7 = const 2_u64;
        (*_6)[_7] = const 3_i64;
        _5 = copy _6;
        (*_1).2 = Cells.$Module.Sum(copy _5) -> bb2;
    }

    bb2: {
        _8 = System.Console.WriteLine$40(copy (*_1).2) -> bb3;
    }

    bb3: {
        return;
    }
}

Several things show already:

• A function is a control-flow graph of basic blocks. Every block is a list of statements and one terminator; a call is a terminator, because it may continue somewhere else (an exception handler).
• Locals are numbered. _0 is the return place, _1 to _N are the arguments, the rest are variables and temporaries. Names are kept only for messages.
• A class is a struct (Cells.Cell: the class id, the vtable, then the field value, so cell.value is field 2). An object is a gc handle to it; gc move _2 copies a struct value into a new object.
• Reads say whether they copy or move.
• Main is unsafe because the array literal writes its elements through the new array's gc handle. Outside unsafe code only the fields of classes may be assigned through a gc handle; arrays and other objects are immutable through them (see the borrow checker).

No larva command prints IR as text: IR is an internal form. Messages from the checks and the linker quote it (types, places, signatures), and the listings on this page come from the same printer, run over the program that larva build lowers.

Types

IrType is a family of records compared structurally: two gc [i64] are equal wherever they were made.

Handles, references and pointers are what the GC and the borrow checker care about. gc, box and *mut are three ways to own memory, and each GC mode decides what a gc handle costs; see Garbage collection.

Primitives

The first twelve fit a single nibble in the binary form; the wide and less common ones take an escape nibble and a second one (see the binary form).

A constant (ConstOperand) holds its value as an arbitrary-size integer: the value itself for integers and bool, the raw IEEE bit pattern for floats. The constructor rejects a value that does not fit the type. The printer shows a type suffix, and floats without a native counterpart in the compiler (f128, f256) as their bits:

_1 = const 1_u256;
_1 = Shl(copy _1, const 200_u256);
_2 = const -5_i128;
_0 = Mul(copy _1, const 0x3FFB999999999999999999999999999A_f128);
_3 = const 1.5_f16;

Those lines come from this program (0.1f128 is the f128 nearest to one tenth, exactly as written, not a widened f64):

import System;

into namespace Wide
{
	Scale(f128 x) : f128 => x * 0.1f128;

	Main()
	{
		u256 big = 1;
		big = big << 200;
		i128 small = -5;
		Console.WriteLine(big);
		Console.WriteLine(small * 3);
		Console.WriteLine(Scale(3f128));
		f16 h = 1.5f16;
		Console.WriteLine(h);
	}
}

$ larva build --backend x64 -o wide.exe wide.ant
wide.exe (x64 back end, entry wide::Wide.$Module.Main)
$ wide.exe
1606938044258990275541962092341162602522202993782792835301376
-15
0.30000000000000000000000000000000004
1.5

Wide integers and floats

The IR had the wide types from the start; teaching every back end to compute with them came later, in steps the design document records as restorations 12, 13, 31 and 32. The rule they settled on: every back end computes exactly the same bits.

SoftFloat is the reference. It works on bit patterns of any IEEE binary format (FloatFormat: exponent and fraction widths; half, single, double, quad and octuple are predefined) and gives correctly rounded results, to nearest with ties to even, with gradual subnormals and overflow to infinity. NaN results are always the canonical quiet NaN. It offers Add, Sub, Mul, Div, Rem (an exact fmod), Sqrt, Neg, Abs, RoundToInteger, Min, Max, Compare (null when unordered), Convert between formats, conversions from and to integers and doubles, and FromText/FromDecimal for exact literals. The same source file is compiled into the VM, the in-process native runtime, the lowering and the Antril frontend (which reads 0.1f128 with it); larva_rt.c (executables) and larva_rt.js (WebAssembly) carry bit-for-bit ports.

Why LLVM does not use its own fp128: in-process code generation crashed on Windows for any function with an fp128 parameter and arithmetic on it. Treating f128 and f256 as their bits and calling the runtime made LLVM agree with the other back ends and gave it f256, which it has no type for.

Restoration 31 added a related operation: intrinsic 89, mem.cmp, compares bytes in one runtime call (memcmp in C) instead of a loop, and literal strings copy their units with one mem.copy.

Known gaps: Larva's own WebAssembly back end has no wide integers or floats (i256 stops it). Sqrt and friends on f128/f256 exist only in the VM (there are no math.* intrinsics for them). On Windows, an LLVM executable that formats an f128 currently fails to link (__umodti3 is missing); the x64 back end builds it.

Places and operands

A place is a memory location: a local followed by projections.

(*_1).2 is "field 2 of the object _1 points to". Indexes are always locals, never expressions: the bounds-check analysis and the borrow checker reason about locals.

An operand is what a statement reads:

Copy types are the primitives, &T, *T, gc T and function addresses: values that can be duplicated without owning anything new. &mut T, box T and structs that hold them are not Copy.

Rvalues

An assignment place = rvalue computes an rvalue and stores it:

Intrinsics

The runtime's services are a fixed table, Intrinsics.All: 97 entries numbered 0 to 96. Each has a name, a signature, an id (the operand of the IL's sys.intrinsic) and the C symbol native code calls. The VM, the in-process native runtime, larva_rt.c and larva_rt.js implement the same table.

The others cover files, folders, the environment, time, threads, memory copies and math. Intrinsics take and give numbers, pointers and &[u8]/&[u16] buffers; strings are built by the language from units, so the runtime never allocates on the collected heap.

HostStreams is the stream half of that table for the runtimes that run inside larva's own process: the VM and the in-process native runtime. It keeps a table of handles (0, 1 and 2 are standard input, output and error), opens files with mode bits (1 read, 2 write, 4 create, 8 truncate, 16 append, 32 only a new file), and also registers TCP connections, listeners and started processes as handles, so stream.read works on all of them. Standard output and error go to text writers a host can replace, which is how tests and tools capture a program's output. Every call returns -1 on failure rather than throwing.

Statements and terminators

Exceptions are part of the control-flow graph: a call, throw and resume list their catch clauses (CatchClause: a type, or any, and a block), so every analysis sees where an exception can go.

Functions and modules

IrFunction is a name, an argument count, the locals (LocalDecl: type, optional name, Mutable, and an optional region for arena checks) and the blocks. Block 0 is the entry. Besides those:

IrModule is a list of structs and functions plus the rest of a compilation unit:

Building a function

FunctionBuilder builds a function the way a lowering pass thinks: declare the arguments (before any other local), open blocks with NewBlock, select one with At, append statements (Assign, StorageLive, Free, RegionEnter…) and close it with a terminator (Goto, If, Call, CallRequired, CallIndirect, Throw…). Build checks that every block has a terminator and every jump lands on a block. ImportFrom("module::name") turns it into a declaration.

The builder also records source positions: the lowering sets Position before each HIR statement, and every statement or terminator appended afterwards is marked with it. The result is IrFunction.Positions, a map from (block, index) to file, line and column; PositionOf finds the nearest marked statement at or before a point in its block. The design document added this so that borrow errors, found on IR, can point at source lines. Positions live in memory only: they are not written to object files.

Generic requirements

Generic code is checked once, before it is instantiated. A generic parameter carries two kinds of knowledge:

• A constraint (TypeConstraint) about the type itself: any, a group, an exact type, and/or/not of those, or size <= N. The groups are int, uint, integer, float, numeric, unmanaged (owns no gc handle), managed, fixedsize, copy, plain (all-zero bytes are a value), object, value and unborrowed (holds no borrow).
• Requirements (Requirement): operations every type argument must provide, written as signatures over the parameters: an operator (op+(T, T) -> T, postfix ones end in .postfix), a conversion (conv(T) -> U), a constructor (new(A) -> T) or a named static member (Zero() -> T).

The printer shows both: fn max<T: numeric>(_1: T, _2: T) -> T, or T: op+(T, T) -> T for a requirement. A call through a requirement is a call terminator with Required set and function -1, printed require T.op+(…).

Requirements.Resolve decides how a requirement is met for concrete types:

1. A built-in operation when every type is a primitive that has it (BuiltinBinary, BuiltinUnary, BuiltinCast): op+ on i32, conv between numbers.
2. Otherwise the one function in Implementations with that name whose signature unifies with the requirement, binding its own type parameters, and whose own constraints and requirements hold (checked recursively, at most 8 deep).
3. When several match, the most specific wins (one whose parameters every other's can be made into).
4. When none matches, an implementation named name!fallback is tried, then name!fallback!fallback.

CheckPerMember handles a parameter limited to a list of types (T : [i16, f32], a number group): such a function is compiled per type, so a requirement holds when it holds for each member. The monomorphizer replaces each requirement call by the built-in operation or the implementing function of each instantiation.

The text form

Larva.IR.Text.IrPrinter renders IR in a form close to Rust's MIR:

• module NAME, then structs (export struct Point { x: i32, y: i32 } // struct#0), static data, globals and implementations;
• each function as // fn#N and its signature, with export, import … from module::name, linkonce, unsafe and #[reflect(…)] prefixes; generic parameters and region parameters in <…>;
• the locals as let mut _N: T; with the source name as a comment, then each block.

IrPrinter.FloatsAsBits prints every float constant as its bit pattern, for tools that compare IR. The checks and the linker use the same printer for the types and places in their messages, which is why errors say `c.0` or struct#0.

Here is a whole object, geom, the first of the two modules used as the example in Objects, modules and linking:

module geom
export struct Point { x: i32, y: i32 }    // struct#0

// fn#0
export fn make(_1: i32, _2: i32) -> Point {
    let mut _0: Point;          // return

    bb0: {
        _0.0 = copy _1;
        _0.1 = copy _2;
        return;
    }
}

// fn#1
export fn norm1(_1: &Point) -> i32 {
    let mut _0: i32;            // return
    let _2: i32;                // ax
    let _3: i32;                // ay

    bb0: {
        _2 = abs(copy (*_1).0) -> bb1;
    }

    bb1: {
        _3 = abs(copy (*_1).1) -> bb2;
    }

    bb2: {
        _0 = Add(copy _2, copy _3);
        return;
    }
}

// fn#2
fn abs(_1: i32) -> i32 {
    let mut _0: i32;            // return
    let _2: bool;

    bb0: {
        _2 = Lt(copy _1, const 0_i32);
        if move _2 -> [true: bb1, false: bb2];
    }

    bb1: {
        _0 = Neg(copy _1);
        return;
    }

    bb2: {
        _0 = copy _1;
        return;
    }
}

// fn#3
export fn max<T: numeric>(_1: T, _2: T) -> T {
    let mut _0: T;              // return
    let _3: bool;

    bb0: {
        _3 = Gt(copy _1, copy _2);
        if move _3 -> [true: bb1, false: bb2];
    }

    bb1: {
        _0 = copy _1;
        return;
    }

    bb2: {
        _0 = copy _2;
        return;
    }
}

// fn#4
export fn identity<T>(_1: T) -> T {
    let mut _0: T;              // return

    bb0: {
        _0 = move _1;
        return;
    }
}

Here ax and ay are immutable locals (no mut), while the locals Antril's lowering makes are mut: the IR leaves that choice to whoever writes it, and the borrow checker enforces it.

The binary form

Objects (.lvo) store IR in a compact binary form written by IrEncoder and read by IrDecoder; IrFormat holds the tags. Everything is a stream of 4-bit units (nibbles), high nibble first:

• unsigned integers are nibble varints: each nibble carries 3 data bits plus a continuation bit (0b1000), so 0 to 7 cost one nibble, 8 to 63 two, 64 to 511 three;
• signed integers are zigzag varints; constants of any width (up to 256 bits) use the same encoding;
• a name is its byte count and its UTF-8 bytes.

The layout, in the notation of IrFormat:

module    = name structs:uv {name generics meta:4 [names] linkage:4 [symbol] fields:uv type* base attributes field-attributes}*
            functions:uv function*  data:uv static*  globals:uv global*  implementations:uv {name function:uv}*
function  = name flags:4 linkage:4 [symbol] generics regions:uv name* args:uv
            locals:uv {flags:4 type [name] [region:uv]}* attributes blocks:uv {stmts:uv stmt* term}*
generics  = count:uv {name constraint}*
type      = 0..11 common primitive (unit..f64) | 12 id:uv args:uv type* (struct) | 13 type (&) | 14 type (&mut)
          | 15 0 type ([]) | 15 1..7 wide primitive (f16 f128 f256 i128 i256 u128 u256)
          | 15 8 type (gc) | 15 9 type (box) | 15 10 type (*) | 15 11 type (*mut) | 15 12 index:uv (generic param)
          | 15 13 [T; N] | 15 14 fn type | 15 15 ?T
constraint= 0 (any) | 1 group:4 | 2 type (exact) | 3 n:uv constraint* (and) | 4 n:uv constraint* (or)
          | 5 constraint (not) | 6 bits:uv (size <=)
place     = local:uv projections:uv {0 | 1 field:uv | 2 local:uv}*
operand   = 0 place (copy) | 1 place (move) | 2 type bits:sv
stmt      = tag place? payload          (tag: one nibble 0-14, or 15 + nibble for the rest)
term      = tag payload                 (call / throw / resume end with handlers = n:uv {hasType:4 [type] block:uv}*)

The flag nibbles: a function's has bit 0 for unsafe, bits 1–2 for the reflection level and bit 3 for a mangled symbol; a local's has bit 0 mutable, bit 1 named, bit 2 a region follows; a struct's has bit 0 for a class, bits 1–2 reflection and bit 3 when field names follow.

Statement tags fold the rvalue kind into the statement: AssignUse is 0, AssignBinary 1, AssignRef 3, and so on up to 34 (AssignImplementation); tags from 15 on take an escape nibble. So the most common statement, _1 = copy _2, takes six nibbles, three bytes: the tag, the target place (local and projection count), the operand's tag and its place. Terminator tags are Goto, If, Switch, Return, Call, Drop, Unreachable, Throw and Resume; a call encodes its callee as 0 (through a requirement), 1 (indirect) or the function index plus 2.

The design document's reason for nibbles is the same as for Larva's IL: libraries ship as IR, and small files load fast. The object file adds Brotli on top when it helps (see the object format): the geom object above is 197 bytes on disk.

The analyses

Larva.IR.Analysis holds the checks every program passes and the analyses that back ends and the runtime rely on. Compiler.Verify runs the checks in order; a module that fails one is not made into an object:

type check (always) -> region check (modes with regions) -> borrow check (enforce or warn)

TypeChecker reports TypeErrors with a kind (UnsatisfiedConstraint, TypeArgumentCount, OperationNotAllowed, GcNotAvailable, UnsafeRequired, UnknownGenericParameter, TypeMismatch, InvalidHandler, LinkageViolation, RegionsNotAvailable, RegionNesting, RegionEscape), printed as error[Kind]: message followed by --> item bbN[i]. A type error is always fatal. Language frontends catch almost everything earlier; IR errors are for bugs in a lowering, and for hand-written IR.

Regions

In arena modes, objects live in regions freed as a block, so the region checker proves, for every function, that:

• regions close innermost first, are never re-entered while open, are all closed at return, and every path into a block sees the same open regions;
• every value that can point into a region carries tags: a body region (r0), a region parameter of the signature ('a), an argument private to the call, or the caller's region; tags follow copies, moves, borrows, fields and calls;
• a local tagged with rN is dead after region_exit(rN), a value stored behind a pointer does not outlive that memory, and the result carries only what the signature allows (-> T in 'a) plus the caller's region;
• calls are checked against the callee's signature, not trusted.

After linking, RegionChecker.CheckMixed adds the rule between GC domains: a value that carries a region may not be passed to a function of another domain, which nothing checks for what it keeps. See GC domains.

Safepoints

A tracing collector can only run when every thread is at a known point with its roots described. Safepoints chooses as few polls as keep that true:

• the header of every loop whose body allocates (or asks for a collection), found from the back edges of a depth-first walk, polls once per iteration;
• the entry of a function that allocates, of one in a cycle of direct calls (recursion), and of one that calls through a function value or a vtable;
• in a program that starts threads (it calls thread.start), every loop polls, because a collection must stop every thread, even one in a loop that allocates nothing.

Every other function runs a bounded amount of code before it returns or reaches a poll. A loop that only calls needs no poll of its own: a callee that allocates polls at its entry.

Bounds checks

BoundsAnalysis is a forward must-analysis over facts about locals: len(*a) == n (from a = new [T; n] or n = len(*a), which stays true while neither local is reassigned), i < n (on the then edge of a comparison), and i >= 0 (from non-negative constants, lengths, unsigned types, and i = i + 1 while i was bounded above). An access (*a)[i] is safe when 0 <= i < n == len(*a). Locals that are ever borrowed mutably never take part, since they can change behind the analysis' back. Back ends drop the checks it proves; larva native --no-bce keeps them all, and the native commands report how many were kept and eliminated.

Borrowed handle reads

Under reference counting every copy of a handle retains and every drop releases. FieldBorrows finds the locals that read a handle out of memory (t = copy (*r).f) only to use it right away: same block, no call in between (a callee could overwrite the field), and no statement in between that stores to memory, replaces or drops an owning local, frees, stores a global or runs an intrinsic. Such a read borrows the reference instead of taking one; the design document measured this on dictionary lookups, whose search loop lost every retain and release.