PIR — the Pebble Intermediate Representation¶

Version 1.0 · text header pir 1.0

PIR is the contract between front ends and the shared middle and back end (docs/architecture.md). A front end, in any language, compiles its source to PIR text. The course's C++ code parses it, verifies it, and either interprets it (pir-run) or lowers it to LLVM IR (pebblec). PIR is modeled on Rust's MIR and Swift's SIL:

Values live in typed locals (_0, _1, ...), not in SSA registers. A front end never has to compute phi nodes or dominance: SSA construction is the back end's job (via mem2reg, and in Chapter 16, your own pass).
Code is a control-flow graph of basic blocks. Each block holds statements and ends in exactly one terminator.
Memory is addressed by places with projections (_1.pos.x, _2[_3], (*_4).len), which keeps aggregates and references first-class without pointer arithmetic.
Safety checks are explicit. A checked a + b in the source language becomes an overflow predicate, an assert and a wrapping add. The optimization chapters can then see, count and remove redundant checks.
Rvalues have no side effects. Only calls and asserts can do anything besides writing their destination.

This document defines the text format, the semantics, and the verifier rules. pebble/include/pebble/PIR/ is the C++ API for the same concepts. Chapter 8 introduces PIR as a case study in IR design.

Contents

Versioning and compatibility
Lexical syntax
Grammar
Types
Modules
Functions, locals and blocks
Places
Operands and constants
Rvalues
Statements
Terminators
Undefined behavior
Verifier rules
Canonical form
Runtime interface
Tools and C++ API
Lowering PIR to LLVM IR
Worked example

1. Versioning and compatibility¶

Every file starts with pir <major>.<minor>.

Minor versions only add constructs, such as a new opcode, trap kind or type. Every 1.0 file is a valid 1.x file with the same meaning. A reader accepts files whose major version equals its own and whose minor version is at most its own. It rejects newer minor versions with a clear message ("unsupported PIR version 1.1"), because such a file may use constructs the reader does not know.
Major versions may change the meaning of existing constructs. A reader rejects any other major version.
Writers emit the version of the library they were built against (pir::VersionMajor, pir::VersionMinor). An external front end should emit the lowest version that covers the constructs it uses. The --pir-version= argument of the protocol (docs/architecture.md) tells it the highest version the consumer accepts.
Changes to the canonical printing (§14) that do not change meaning, such as whitespace or ordering, do not bump the version. Golden tests should compare canonical output, which pir-opt produces.

Change log:

Version	Changes
1.0	initial version

2. Lexical syntax¶

Whitespace (space, tab, CR, LF) separates tokens and is otherwise insignificant. Statements are conventionally one per line, but line breaks carry no meaning.
Comments run from // to the end of the line.
Tokens:

Token	Form	Examples
local	`_` followed by decimal digits only	`_0`, `_17`
global / function	`@` followed by `[A-Za-z0-9_.$]+`	`@main`, `@pebble_print_int`, `@tbl.1`
struct name	`%` followed by `[A-Za-z0-9_.$]+`	`%Point`
location	`@` followed by `line:col` in decimal	`@12:5`
identifier	`[A-Za-z_][A-Za-z0-9_]*`, but not a local	`add`, `bb3`, `i64`, `true`, field names
integer	`-`? digits, then an optional `_i8`, `_i16`, `_i32` or `_i64` suffix	`5`, `-1`, `255_i8`
float	`-`? digits `.` digits [exponent], or `-`? digits exponent; optional `_f64` suffix; also `inf`, `-inf`, `nan`	`0.5`, `-2.0e10`, `1e+21`
string	`"` … `"` with escapes `\n` `\t` `\r` `\0` `\\` `\"` `\xHH`	`"hi\n"`
punctuation	`( ) { } [ ] , : ; = -> & * . !`

Keywords are identifiers with a special meaning in context: pir source struct const extern fn let call assert goto br switch otherwise return trap unreachable to mut true false, the type names, the opcode names and the trap kinds. Because every local starts with _ followed by a digit, and every global with @, keywords never clash with names.

3. Grammar¶

module      = header { struct | const | extern | function } ;
header      = "pir" VERSION [ "source" STRING ] ;

struct      = "struct" STRUCT_NAME "{" [ field { "," field } ] "}" ;
field       = IDENT ":" type ;
const       = "const" GLOBAL ":" type "=" const_value ;
const_value = constant
            | "[" const_value { "," const_value } "]"
            | STRUCT_NAME "{" [ IDENT ":" const_value { "," IDENT ":" const_value } ] "}" ;
extern      = "extern" "fn" GLOBAL "(" [ type { "," type } ] ")" [ "->" type ] ;

function    = "fn" GLOBAL "(" [ param { "," param } ] ")" [ "->" type ] "{"
                { "let" LOCAL ":" type [ STRING ] }
                block { block }
              "}" ;
param       = LOCAL ":" type [ STRING ] ;
block       = LABEL ":" { statement } terminator ;          (* LABEL = bbN *)

statement   = place "=" rvalue [ LOC ]
            | [ place "=" ] "call" GLOBAL "(" [ operand { "," operand } ] ")" [ LOC ]
            | "assert" [ "!" ] operand "," TRAP_KIND [ LOC ] ;
terminator  = ( "goto" LABEL
              | "br" operand "," LABEL "," LABEL
              | "switch" operand "," "[" [ case { "," case } ] "]" "otherwise" LABEL
              | "return" [ operand ]
              | "trap" TRAP_KIND
              | "unreachable" ) [ LOC ] ;
case        = INTEGER ":" LABEL ;

rvalue      = operand
            | BINOP operand "," operand
            | UNOP operand
            | CAST operand "to" type
            | "&" [ "mut" ] place
            | "[" operand { "," operand } "]"
            | "[" operand ";" INTEGER "]"
            | STRUCT_NAME "{" [ IDENT ":" operand { "," IDENT ":" operand } ] "}" ;
operand     = place | constant ;
constant    = INTEGER | FLOAT | STRING | "true" | "false" | "(" ")" ;
place       = "*" place
            | "(" place ")" { projection }
            | ( LOCAL | GLOBAL ) { projection } ;
projection  = "." IDENT | "[" LOCAL "]" | "[" INTEGER "]" ;

type        = "i8" | "i16" | "i32" | "i64" | "f64" | "bool" | "str" | "unit"
            | "[" type ";" INTEGER "]" | STRUCT_NAME | "&" [ "mut" ] type ;

Scoping of declarations. - Structs and constants must be declared before they are used, as in C: the parser resolves field names as it reads places. - Functions may be called before their definition or declaration. - Functions and constants share one namespace (E: "redefinition of @x").

Numbering. - A function's locals are numbered _0, _1, … consecutively. Parameters come first, then the let declarations in order. - Blocks are labeled bb0, bb1, … consecutively in order of appearance, and bb0 is the entry block. - The parser enforces both rules. Canonical files are therefore trivial to diff, and a local's or block's number is its index in the C++ data structures.

Operand typing. Every constant carries its own type: unsuffixed integers are i64, unsuffixed floats are f64. Nothing is inferred from context. The one exception is const initializers, where unsuffixed integers take the declared element type: const @t: [i8; 2] = [1, 2]. The , after a switch operand is required, because switch _0 [1: bb1] would read [1 as an index projection.

4. Types¶

Type	Meaning	Size in LLVM (bytes)
`i8` `i16` `i32` `i64`	two's-complement integers; signedness is a property of operations, as in LLVM	1, 2, 4, 8
`f64`	IEEE 754 binary64	8
`bool`	`true` / `false`	1 in memory
`str`	pointer to an immutable NUL-terminated byte string	pointer
`unit`	the single value `()`; function result "void"	0
`[T; N]`	N ≥ 1 elements of T	N · size(T)
`%S`	a struct declared in the module; C layout	C rules
`&T` / `&mut T`	a non-null pointer to a place of type T; `&mut` allows writes through it	pointer

Types are equal when they are spelled the same. Struct types are nominal.
unit may be the type of a local and the result of a function. It cannot be a field, an array element, a global's type, a parameter, or a reference's pointee.
References may be stored in locals, fields and arrays, and returned. PIR does not track lifetimes: using a reference after its target local's function has returned is undefined behavior (§12). The Pebble front end never produces such code (its references are second-class).
Recursive structs must go through a reference: struct %Node { val: i64, next: &%Node }.

5. Modules¶

A module consists of the version header, an optional source "path", and then struct declarations, global constants, extern declarations and function definitions, in any order that respects §3 "Scoping".

source "path" names the file that the @line:col locations refer to. Trap messages print it (… at fib.pbl:3:12). A module without it has locations but no file name.
const @name: T = value defines read-only memory, initialized at program start. Its name can be the root of a place (@primes[_2]). Writing to it, or taking &mut of it, is a verifier error.
extern fn @name(T1, …) -> R declares a function implemented outside the module, called with the C ABI. Parameters and result are limited to integers, f64, bool and str (result also unit). The Pebble runtime's functions (§15) are declared this way.
fn @name(…) -> R { … } defines a function. A function named @main is the program's entry point and must have type fn() -> i64. Names beginning with pebble_ are reserved for the runtime.

6. Functions, locals and blocks¶

fn @max(_0: i64 "a", _1: i64 "b") -> i64 {
  let _2: bool
bb0:
  _2 = sgt _0, _1 @2:8
  br _2, bb1, bb2 @2:5
bb1:
  return _0 @2:17
bb2:
  return _1 @3:5
}

Parameters are locals _0 … _{n-1}, initialized with the arguments. Other locals start uninitialized: reading one before writing it is undefined behavior (§12). The optional string after a local is its debug name, for diagnostics and readable LLVM IR. It has no semantic meaning.
Every local lives for the whole activation of the function (no scopes, no storage-live/dead markers).
Execution starts at bb0, runs its statements in order and then its terminator, which transfers control to another block or leaves the function. Blocks that are unreachable from bb0 are allowed.

7. Places¶

A place denotes a memory location:

Form	Meaning	Requires
`_N`	local N
`@g`	global constant g (read-only)
`p.f`	field f of struct place p	p : `%S` with a field f
`p[_N]`	element `_N` of array place p	p : `[T; M]`, `_N : i64`
`p[K]`	element K (a constant) of p	p : `[T; M]`, K < M
`*p`	the place p points to	p : `&T` or `&mut T`

Projections apply left to right. A deref applies to everything on its left, so the text uses parentheses: (*_1).x dereferences _1 and then selects x, while *_1.x selects field x of _1 and dereferences it. Index operands are restricted to locals and constants, as in MIR. Compute other index expressions into a temporary first.

Indexing is unchecked. An index outside 0 … M-1 is undefined behavior. A front end that wants a checked index emits c = ult _i, M; assert c, bounds first. The unsigned comparison also catches negative indices.

8. Operands and constants¶

An operand is a place, which is read and yields a copy of its value, including whole aggregates, or a constant:

Constant	Type
`5`, `-5`, `5_i64`	i64
`5_i8`, `255_i8` (= −1), `-128_i8`	i8 (and likewise `_i16`, `_i32`)
`1.5`, `-2e10`, `inf`, `-inf`, `nan`	f64
`true`, `false`	bool
`"text"`	str (must not contain a NUL byte)
`()`	unit

An integer constant may be written in its type's signed or unsigned range. 255_i8 and -1_i8 are the same bit pattern, and the canonical form prints the signed value. Aggregate constants exist only as const initializers.

9. Rvalues¶

An rvalue computes a value without side effects. It can have undefined behavior (§12), but it cannot trap, print or write memory.

9.1 Binary operations¶

op a, b: both operands have the same type. The result type is that type, or bool for comparisons and overflow predicates. The opcodes are listed in pebble/include/pebble/PIR/Operations.def.

Opcodes	Operands	Result
`add sub mul`	int	wrapping (modulo 2ʷ)
`sdiv srem`	int	truncating signed division, remainder with the dividend's sign. UB if b = 0 or a = MIN, b = −1
`udiv urem`	int	unsigned. UB if b = 0
`and or xor`	int or bool	bitwise / logical, both operands evaluated
`shl lshr ashr`	int	shift left / logical right / arithmetic right. UB if b, read as unsigned, is ≥ w
`saddo ssubo smulo`	int	`true` iff the signed result does not fit in w bits
`uaddo usubo umulo`	int	`true` iff the unsigned result does not fit in w bits
`fadd fsub fmul fdiv frem`	f64	IEEE 754, round to nearest even. `frem` is C `fmod`. Never traps
`eq ne`	int or bool	equality
`slt sle sgt sge`	int	signed comparison
`ult ule ugt uge`	int	unsigned comparison
`feq flt fle fgt fge`	f64	ordered: false if either operand is NaN
`fne`	f64	unordered or not equal: true if either operand is NaN, so `fne` = ¬`feq`

A checked operation is the combination of a predicate, an assert and the wrapping operation:

_3 = saddo _1, _2
assert !_3, overflow
_4 = add _1, _2

A code generator may fuse the pair into one llvm.sadd.with.overflow, whose two results are the sum and the flag. The reference code generator emits them separately and leaves the combining to LLVM.

9.2 Unary operations¶

Opcode	Operand	Result
`neg`	int	0 − a, wrapping (use `ssubo 0, a` to check)
`not`	int / bool	bitwise complement / logical not
`fneg`	f64	sign flip (also of NaN and 0)

9.3 Casts¶

kind a to T:

Kind	From	To	Semantics
`trunc`	iN	iM, M < N	keep the low M bits
`sext`	iN	iM, M > N	sign-extend
`zext`	iN or bool	iM, M > N (any iM from bool)	zero-extend; `true` → 1
`sitofp` / `uitofp`	int	f64	the nearest double to the signed / unsigned value
`fptosi` / `fptoui`	f64	int	truncate toward zero, saturating at the signed / unsigned range of the target; NaN → 0 (LLVM `llvm.fpto[su]i.sat`)

There are no bitcasts, no pointer casts and no int-to-bool casts (use ne a, 0).

9.4 References and aggregates¶

Rvalue	Type	Meaning
`&p`	`&T`	the address of place p : T
`&mut p`	`&mut T`	the same; p must be writable (§13, V9)
`[a, b, c]`	`[T; 3]`	T is the type of the first element; all elements must have type T
`[a; N]`	`[T; N]`	N copies of a
`%S { f: a, g: b }`	`%S`	every field, in declaration order

All operands of an aggregate are read before its destination is written. _1 = [_1[1], _1[0]] swaps the two elements.

10. Statements¶

place = rvalue: (1) evaluate the rvalue completely, (2) evaluate the place, including index loads and derefs, (3) store. The types must match exactly.
[place =] call @f(args): evaluate the arguments left to right (reading places), bind them to the callee's parameters by value (aggregates are copied, so the callee may modify its parameters without the caller noticing), and run the callee. When it returns, evaluate the destination place and store the result. The destination is evaluated after the call, so a callee that modifies an index local through a reference moves the destination. Omit the destination to discard the result. A unit result may also be stored into a unit local.
assert op, kind traps with kind (§11) unless op is true. assert !op, kind traps unless it is false. The trap location is the statement's @line:col.

11. Terminators¶

Terminator	Meaning
`goto bbN`	continue at bbN
`br op, bbT, bbF`	op : bool; continue at bbT if true, else bbF
`switch op, [v1: bbA, …] otherwise bbZ`	op : integer; the case values are distinct and fit op's type; jump to the matching case, else to bbZ
`return` / `return op`	leave the function; `return` without an operand only in `unit` functions
`trap kind`	stop the program with a trap
`unreachable`	undefined behavior if executed; tells the optimizer this point is dead

Trap kinds and their runtime codes (docs/runtime-abi.md):

Kind	Code	Message
`overflow`	1	arithmetic overflow
`div_by_zero`	2	division by zero
`bounds`	3	index out of bounds
`shift`	4	shift amount out of range
`assert`	5	assertion failed
`unreachable`	6	entered unreachable code

A trap stops the program immediately. Standard output is flushed, the message is printed with the location of the trapping statement, and the exit status is 101. A trap is defined behavior: optimizations must preserve it, including the output printed before it.

Source locations (@line:col) may follow any statement or terminator. Line 0 (or no location) means "unknown". Locations have no semantic effect except in trap messages, where they are observable. Keep them accurate.

12. Undefined behavior¶

A PIR program that does any of the following has no meaning. The code generator may assume these never happen (and LLVM will), and pir-run detects them and stops with exit status 70:

reading an uninitialized scalar in a computation: an operand of a binary or unary operation, cast, br, switch, assert, index, extern call argument, or the result of @main (copying an uninitialized value is allowed);
an index outside the array bounds;
sdiv/srem by zero or of MIN by −1; udiv/urem by zero;
a shift amount ≥ the width;
executing unreachable;
dereferencing a reference whose target no longer exists, or that was never initialized.

Integer overflow of add, sub, mul and neg is not UB: those operations wrap. Front ends that want checks emit them.

13. Verifier rules¶

pir::verifyModule (and pir-opt) check these static rules. Code generators and the interpreter may assume a verified module. Each message names the rule, the function, the block and the statement index ([term] for the terminator), for example @main bb2[3] (line 7:9): V15: mismatched types in assignment: _4 is i64, value is bool.

Rule	Checks
V1	structs have a body, unique field names, fields of non-unit type, and do not contain themselves by value
V2	global constants have a non-unit, non-reference type and an initializer of exactly that type
V3	functions have a result type; parameters are not `unit`; every local has a type, and no array element or reference pointee is `unit`
V4	extern parameters are integers, `f64`, `bool` or `str`; the result is one of those or `unit`
V5	defined functions are not named `pebble_*`
V6	`@main`, if present, has type `fn() -> i64`
V7	every function has at least one block, and every block has a terminator
V8	places are well-typed: fields exist, only arrays are indexed, index locals are `i64`, constant indices are in bounds, only references are dereferenced
V9	assignments, call destinations and `&mut` never target a global constant or a place behind an immutable reference
V10	constants are well-formed: integers fit their width, strings contain no NUL
V11	binary and unary operands have the same, permitted type (§9.1, §9.2)
V12	casts go between the types §9.3 allows
V13	references are not taken to `unit` places
V14	aggregates have the right number of operands of the right types
V15	an assignment's rvalue type equals its place's type
V16	calls have a callee, the right number and types of arguments, and a destination of the callee's result type
V17	assert conditions are `bool`
V18	branch targets exist
V19	`br` conditions are `bool`; `switch` operands are integers, and case values are unique and fit the operand's type
V20	`return` operands match the function's result type (none for `unit`)

The parser already enforces name resolution: known locals, globals, structs, fields and functions, consecutive numbering, one terminator per block, and existing targets. A module built with the C++ Builder API skips the parser, so the verifier re-checks what it can.

14. Canonical form¶

pir-opt and pir::printModule print this layout. Printing a canonical file reproduces it byte for byte:

pir 1.0, then source "…" if set;
a blank line and all structs, one per line, in declaration order;
a blank line and all constants, one per line;
a blank line and all extern declarations, one per line;
for each defined function, a blank line and then the function: the header, the let lines indented by 2, each label at column 0, statements and terminators indented by 2, and }.

Other conventions: - Integers print as signed decimal, with a _iN suffix unless the type is i64. Floats print in the runtime's shortest round-trip format (docs/runtime-abi.md), which always contains a ., an exponent, inf or nan. - Strings escape \n, \t, \r, \\ and ", and print other bytes outside 0x20–0x7e as \xHH. - Locations print as @line:col at the end of the line when known. pir-opt --strip-locations and --strip-debug-names produce location- and name-free output for comparing modules that differ only in those.

15. Runtime interface¶

A PIR program does I/O only by calling the runtime's functions, which it declares as externs:

extern fn @pebble_print_int(i64)
extern fn @pebble_print_float(f64)
extern fn @pebble_print_bool(bool)
extern fn @pebble_print_str(str)
extern fn @pebble_print_newline()

pir-run implements these five with the runtime's own formatting code, so its output is byte-identical to a compiled program's.
Calling any other extern function under pir-run is an error (status 1). Compiled programs may call arbitrary C functions.
Traps are expressed with assert and trap, never by calling pebble_trap directly.

docs/runtime-abi.md specifies the symbols, types and calling convention at the machine level.

16. Tools and C++ API¶

Tools. - pir-run file.pir interprets @main (see pir-run --help). Exit status: @main's result on return; 101 after a trap, with the runtime's message on stderr; 70 for undefined behavior; 1 for parse, verifier or other errors. - pir-opt file.pir [-o out] parses, verifies and prints the canonical form. Use --verify-only to print nothing. - pebblec --from-pir file.pir compiles PIR to an executable (or --emit=llvm|obj).

C++ API (pebble/include/pebble/PIR/):

Header	Provides
`Type.h`	`Type` and its subclasses (LLVM-style RTTI); `TypeContext` uniquing
`IR.h`	`Place`, `Operand`, `Constant`, the `Rvalue` variant, `Statement`, `Terminator` (std::variant based), opcode enums from `Operations.def`
`Module.h`	`Module`, `Function`, `BasicBlock`, `GlobalConst`; `getPlaceType`, `getOperandType`, `getRvalueType`
`Builder.h`	`Builder`: insertion point, current location, helpers for constants and checked code
`Printer.h`	`printModule`, `toString(...)`, `formatFloat`
`Parser.h`	`parseModule(text, name)`, `parseModuleFile(path)` → `std::expected<Module, Error>`
`Verifier.h`	`verifyModule`, `collectVerifierErrors`
`Interpreter.h`	`runMain(module, options)` → `ExecutionResult`

17. Lowering PIR to LLVM IR¶

The shared back end (pebble/include/pebble/CodeGen/PIRToLLVM.h, Chapter 11) maps PIR to LLVM IR:

PIR	LLVM IR
`iN`, `f64`, `bool`, `str`, `&T`, `unit`	`iN`, `double`, `i1` in registers and `i8` in memory, `ptr`, `ptr`, `void` result or `{}` in memory
`[T; N]`, `%S`	`[N x T']`, a named struct `%S`
a local	an `alloca` in the entry block (aggregate parameters: the incoming pointer)
place	`getelementptr inbounds` chains; a `load ptr` per deref
`saddo a, b`	`extractvalue (llvm.sadd.with.overflow(a, b)), 1`
`fptosi`	`llvm.fptosi.sat`
`assert c, k`	`br c, %ok, %trap`, where `%trap` calls `pebble_trap(k, file, line, col)` and ends in `unreachable`
aggregate assignment	`llvm.memcpy` (`[0; N]` becomes `llvm.memset`)
aggregate parameter / result	`ptr` to a caller-made copy / `sret` pointer
`@main`	`define i64 @pebble_main()`

The acceptance test is behavioral. For every sample program, the executable must print exactly what pir-run prints, exit with the same status, and produce the same trap message (tests/pir/unit/CodeGenTest.cpp).

18. Worked example¶

The Pebble function

fn sum(xs: &[int; 4]) -> int {
    var s = 0;
    for i in 0..4 { s += xs[i]; }
    return s;
}

lowers (with the reference scheme) to:

fn @sum(_0: &[i64; 4] "xs") -> i64 {
  let _1: i64 "s"
  let _2: i64 "i"
  let _3: i64
  let _4: bool
  let _5: bool
  let _6: bool
bb0:
  _1 = 0 @2:5
  _2 = 0 @3:9
  _3 = 4 @3:17
  goto bb1 @3:5
bb1:
  _4 = slt _2, _3 @3:5
  br _4, bb2, bb3 @3:5
bb2:
  _5 = ult _2, 4 @3:26
  assert _5, bounds @3:26
  _6 = saddo _1, (*_0)[_2] @3:21
  assert !_6, overflow @3:21
  _1 = add _1, (*_0)[_2] @3:21
  _2 = add _2, 1 @3:5
  goto bb1 @3:5
bb3:
  return _1 @4:5
}

Things to notice: - The loop bound is evaluated once into _3. - The bounds check is an explicit assert that Chapter 18's bounds-check elimination can remove, since _2 < _3 = 4 is known in bb2. - The checked += becomes a predicate, an assert and a wrapping add. - The loop increment uses a plain add, because it cannot overflow.

More complete programs, with expected output, are in tests/conformance/lit/pir/.