Radiance Intermediate Language

The Radiance Intermediate Language, or RIL is a minimal, low-level, SSA-based intermediate representation for Radiance.

Why an intermediate language?

Though intermediate languages (ILs) are very common for compiled languages, it’s worth stating some of the reasons we chose to have one for Radiance, given that our constraints are different than most languages. It’s important that the Radiance compiler stays simple. We don’t want to end up with a compiler toolchain in the millions of lines of code like Zig’s or Rust’s, and having ILs in a compiler increases the surface area a lot. However, trying to build a serious compiler without one is challenging and presents trade-offs.

Wirth languages like Pascal and Modula often had single-pass implementations that emitted machine code while parsing source code. This made the compilers very fast and very small in size, at the expense of other things; namely the size of the resulting binary code, the flexibility of the language semantics and the quality of the compiler diagnostics.

For Radiance, we wanted something that would better scale to the demands of the Radiant system, would produce fast machine code, and would have great usability. Intermediate languages are a very useful abstraction that makes compilers easier to write, understand, debug, and build tooling for. We therefore decided it was a worthy trade-off on this basis alone.

However, there is another reason to have an IL that is specific to Radiant: our operating system does not execute machine code directly. This avoids a plethora of security issues that would otherwise require something like CHERI. Since the OS cannot audit machine code, only hardware-level safety is applicable. This has a cost in performance and complexity.

On the other hand, having a verifiable IL allows for native sandboxing capabilities without the costs. This is similar to what is offered by WebAssembly. It means that the OS only loads IL programs and internally compiles them to machine code once it has verified that they do not break any of the safety rules. This is more limiting than allowing arbitrary machine code to run, but the trade-off in this case is worth it.

Radiance’s IL

We’ve tried to keep the IL small, but it’s a balancing act: too small and you give the frontend more work to do; too large and you give the backend more work to do. So we found a middle ground that is still low-level, while having some affordances that give compiler backends enough flexibility in lowering the IL to machine code.

The IL is also designed with RISC-V as the primary target for lowering. Hence, there are instructions that map one to one with RISC-V instructions, such as beq, bge etc. We also took a lot of inspiration from QBE, a minimal, open source intermediate language.

fn w32 $fib(w32 %0) {
  @entry
    br.slt w32 1 %0 @merge @done;
  @done
    ret %0;
  @merge
    sub  w32 %1 %0 1;
    call w32 %2 $fib(%1);
    sub  w32 %3 %0 2;
    call w32 %4 $fib(%3);
    add  w32 %5 %2 %4;
    ret  %5;
}

The above RIL code is generated from the following Radiance function:

fn fib(n: i32) -> i32 {
    if n <= 1 {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

The lowering phase that produces RIL takes a typed abstract syntax tree (AST) as input, and generates RIL incrementally. The IL has infinite registers, and instructions don’t have a size limit. The job of instruction selection and register allocation is left to the next phase, which turns RIL into platform dependent machine code.

The SSA form that RIL uses also lends itself to various optimizations, such as constant folding and dead-code elimination.

Instead of phi nodes wich are used in popular ILs such as LLVM and QBE, RIL uses block parameters for SSA construction. This is similar to MLIR and SIL. Each basic block can declare parameters, and jumps/branches pass arguments to their targets. This simplifies reasoning about control flow merges.

If we take the following example code that involves a control flow merge between the if and else branch, we see that the generated RIL has a merge block that takes a block parameter. This is the equivalent of a phi node, which is used to select between between multiple register assignments.

fn mergeExample(flag: bool) -> i32 {
    let mut x: i32 = 0;
    if flag {
        x = 1;
    } else {
        x = 2;
    }
    return x;
}

fn w32 $mergeExample(w8 %0) {
  @entry
    br.ne w32 %0 0 @then @else;
  @then
    jmp @merge(1);
  @else
    jmp @merge(2);
  @merge(w32 %1)
    ret %1;
}

Types & Values

The IR supports four word-sized primitive types. Signedness is encoded in operations (e.g. sdiv vs udiv), not in types.

Operands in instructions can be registers, immediates, symbols or blocks.

Instructions

RIL has about 40 instructions currently. As Radiance involves, more instructions may be added.

Memory operations. Stack allocation, loads, stores, and bulk memory copies.

Basic arithmetic operations. Signedness is encoded in the operation name.

Equality and relational comparisons. Results are stored as W8.

Bitwise logic and shift operations.

Control flow. Jumps, calls, returns.

Intrinsics. Low-level operations for interacting with the environment.

Data directives

RIL supports directives for defining static data and external declarations.

Static data. The data directive defines a named, aligned block of static data.

data $<name> align <n> {
    <values>...
}

Values inside data blocks can be:

Example:

// A static string.
data $Greeting align 1 {
    str "hello";
}
// An 8-byte record of {1, 42}.
data $Padded align 4 {
    w8 1;
    undef * 3;
    w32 42;
}

External functions. The extern directive declares an externally-defined function.

extern fn <type> $<name>(<params>...)

Lowering strategy

Since RIL only has scalar types, we need a way to lower aggregates like slices and records.

For records, RIL uses loads and stores with pointer arithmetic to implement field access. For unions, we reserve enough space for the largest variant, and place a numeric tag in front of it.

Slices are lowered as records with a pointer and length field. Optionals use the same strategy as unions.

Arithmetic

In terms of arithmetic, there is no truncation instruction — narrow values use word-sized registers with undefined high bits; truncation happens implicitly via narrow stores.

There’s also no widening on arithmetic — type annotations on arithmetic ops indicate logical width but don’t change code generation; arithmetic is always machine-word sized.

We use zext/sext for loads — widening happens when loading narrow values from memory.