Glossary

axis

One dimension of a tensor. A matrix has two axes: rows and columns. Also called a dimension.

shape (3, 4): axis 0 has size 3

Taught in 0.4 Tensors and shapes, 5.1 Any rank, flat memory

bounds analysis

Working out an interval [lo, hi] that a value must fall in, from the intervals of its sources. The course uses it to simplify and to prove memory accesses are in range.

max(x, 0) is in [0, INT_MAX]

Taught in 1.4 Symbolic simplification, 2.3 Proving bounds

broadcast

Reusing one value across a whole axis, so a scalar or a size-1 axis acts as if it were repeated. In .uir you broadcast with expand. It's never implicit.

expand 2.0 to shape [4] gives [2.0 2.0 2.0 2.0]

Taught in 4.1 Vectors and elementwise ops, 4.2 Reduce and expand, 5.3 Pad, shrink, expand, stack

buffer

Global memory the program reads and writes, given to the compiled kernel as a pointer. Buffers are the program's inputs and outputs.

%x = buffer 4 dtype=f32 slot=0

Taught in 2.1 Buffers and views

byte

8 bits, the smallest unit of memory with its own address. An int32 is 4 bytes, a pointer on a 64-bit machine 8.

Taught in 0.1 C and pointers

cache

A small, fast memory next to the CPU that keeps recently used data. Reading from cache is many times faster than reading from main memory.

Taught in 0.2 Memory and caches

cache line

The block of bytes the cache moves at once: 64 bytes on most x86 and ARM chips, 128 on Apple M-series. Touching one byte brings in its whole line.

Taught in 0.2 Memory and caches

call

The .uir op that evaluates a body with its params bound to arguments: arg i fills param i.

%r = call %body 41

canonical form

One fixed way to write equivalent expressions, so a rewrite rule only has to match one shape. The course puts constants on the right of commutative ops such as add and mul.

add 3 x becomes add x 3

cast

Converting a value to another dtype. f32 to i32 truncates toward zero, and out-of-range values are an error.

cast 3.7 dtype=i32 gives 3

clamp

Forcing an index into a range, so a read can't go out of bounds. A padded read is clamped before it's masked.

max(min(i, n-1), 0)

Taught in 5.5 Rangeify movement ops

closed body

A call body that only sees its own params: substitution doesn't reach inside a nested call's body, only its arguments.

closure

An OCaml function together with the variables it captured when it was made. A function that returns a function returns a closure. Python functions capture variables the same way, and assigning to a captured variable needs nonlocal.

let make () = let n = ref 0 in fun () -> incr n; !n

Taught in 0.6 OCaml crash course, 0.7 Python for this course, 1.1 The UOp

cmplt

The .uir less-than comparison. It returns a bool, and any NaN makes it false.

cmplt 1 2 is true

commutative

An op whose operand order doesn't change the result, such as add and mul. Rewrites use this to put operands in canonical order.

compiler

A program that translates a program from one form to another, usually from something people write into something a machine runs.

Taught in 0.3 Compilers and IRs

const

The .uir op for a fixed value. A bare number in an operand position is a const.

%c = const 3 dtype=f32 is 3.0

constant folding

Replacing an op whose inputs are all constants with its result, at compile time.

add 2 3 becomes 5

convolution

Sliding a small window of weights over an input and taking a weighted sum at each position. The workhorse of image models.

Taught in 3.4 A convolution by hand, 5.4 Matmul and conv from movement

DAG

A directed acyclic graph: nodes with arrows and no cycles. A program as a DAG lets shared subexpressions be one node used twice.

(a+b)*(a+b) has one a+b node with two users

Taught in 0.3 Compilers and IRs, 1.1 The UOp

dataclass

A Python class whose fields are declared once, with __init__ and friends generated for you. frozen=True makes it immutable, a good fit for IR nodes. It plays the role of an OCaml record.

@dataclass(frozen=True) class Const: value: int

Taught in 0.7 Python for this course

dtype

A value's element type. In .uir: void, bool, i32 or f32.

dune

OCaml's build tool. dune build compiles your project, and dune exec runs it. Python has no build step: you run your compiler with python main.py.

Taught in 0.6 OCaml crash course

effect

Something that changes memory instead of producing a value: a store, or an end that repeats stores. Effects have dtype void.

Taught in 3.1 Ranges and end

elementwise

An op applied to each element separately, position by position.

[1 2] add [10 20] gives [11 22]

Taught in 4.1 Vectors and elementwise ops

end

The .uir op that repeats its effects once for every value of a range, then closes the range.

%e = end %s %i

Taught in 3.1 Ranges and end

enum

A Python class whose members are a fixed set of named values, such as the ops of an IR. It plays the role of an OCaml variant whose constructors carry no data.

class Op(Enum): ADD = auto()

Taught in 0.7 Python for this course

environment

A map from param slot to value for the call being evaluated. The usual way to implement substitution in an interpreter.

Taught in 1.5 CALL, PARAM, STACK, INDEX, 1.6 Lab: your compiler

exit code

The number a program returns to whoever ran it. Your compiler's run command uses 0 (pass), 1 (assert failed), 2 (invalid).

Taught in 1.2 .uir and interpreting, 1.6 Lab: your compiler

expand

The .uir op that broadcasts: a scalar becomes a vector, or size-1 axes grow to a target shape.

expand %r shape=[4096]

Taught in 4.2 Reduce and expand, 5.3 Pad, shrink, expand, stack

f32

A 32-bit floating-point number (IEEE binary32). Every f32 op rounds its result to the nearest representable value.

0.1 + 0.2 == 0.3 in f32, though not in doubles

fixpoint

The state where applying the rewrite rules again changes nothing. A simplifier runs passes until it reaches one.

flat index

The single position of an element in a buffer, computed from a multi-dimensional index and the strides.

[1, 2] in shape (3, 4) is 1*4 + 2 = 6

Taught in 0.4 Tensors and shapes, 5.1 Any rank, flat memory

fold

Combining a list into one value step by step. A left fold combines from the first element onward. A reduce is a left fold. OCaml has List.fold_left, and Python has functools.reduce.

((x0 + x1) + x2) + x3

Taught in 0.6 OCaml crash course, 0.7 Python for this course, 4.2 Reduce and expand

fused multiply-add (FMA)

One instruction computing a*b + c with a single rounding. It gives different f32 bits than two separate ops, which is why the grader compiles with -ffp-contract=off.

Taught in 2.4 Rendering C

fusion

Computing a value where it's needed, every time it's needed, instead of storing it. Saves memory traffic, costs arithmetic.

Taught in 4.4 Fuse or materialize

GEMM

General matrix multiply, C = A @ B. Most of the compute in a neural network.

Taught in 0.5 Matrix multiply, 3.3 A matmul by hand, 5.4 Matmul and conv from movement

grader

The course's test runner, tools/test.py. It compares your compiler's behavior to the oracle's on every test.

Taught in 1.6 Lab: your compiler

hash consing

Building every node through a table, so two nodes with the same op, sources and arg are the same node. Equality becomes one pointer comparison.

two statements add 2 3 become one node

Taught in 0.3 Compilers and IRs, 1.1 The UOp

hash table

A dictionary: give it a key and it quickly gives back the stored value. OCaml's is Hashtbl, and Python's is dict.

Taught in 0.3 Compilers and IRs, 0.6 OCaml crash course, 0.7 Python for this course

hex

Writing numbers in base 16, with digits 0-9 then a-f, marked with 0x.

0x10 is 16, and 0xff is 255

Taught in 0.1 C and pointers

hex float

A float written in base 16 with an exponent, which C reads back exactly. Your renderer prints f32 constants this way.

0x1.8p+1f is 3.0

Taught in 2.4 Rendering C

hoisting

Moving a computation out of a loop because it doesn't change between iterations.

Taught in 3.5 Rendering loops, 4.5 Rendering vectors

i32

A 32-bit signed integer in two's complement. add, mul and shl wrap around instead of failing.

add 2147483647 1 gives -2147483648

implementation-defined

Behavior the C standard lets each compiler choose, as long as it documents the choice. Different from undefined behavior.

converting 3000000000 to int32_t: every compiler you'll use wraps

Taught in 0.1 C and pointers

index

The .uir op that picks elements by position, dropping leading axes.

index (stack 10 20 30) 1 gives 20

Taught in 1.5 CALL, PARAM, STACK, INDEX, 5.1 Any rank, flat memory

inline

Replacing a call with its body, params substituted. Always allowed for a pure call.

interpreter

A program that runs another program directly instead of translating it. Your week 1 compiler starts as one.

interval

A pair [lo, hi] meaning every value between them, used in bounds analysis.

mod x 8 with x >= 0 is in [0, 7]

Taught in 1.4 Symbolic simplification, 2.3 Proving bounds

IR

Intermediate representation: the form a compiler holds a program in between reading it and printing output. The course's IR is a graph of UOps.

Taught in 0.3 Compilers and IRs

kernel

One function your compiler generates to do the work, here a C function named kernel that takes the buffers as pointers.

Taught in 0.1 C and pointers, 2.4 Rendering C

lexer

The part of a compiler that splits source text into words (tokens).

Taught in 0.3 Compilers and IRs

linearize

Turning a graph into an ordered list of steps, with loops nested where they belong. Both run and render work from this order.

Taught in 3.5 Rendering loops

load

The .uir op that reads memory through a view into a value.

%x = load %v

Taught in 2.2 Load, store, after

load placement

The rule for which loop a load runs in. Like any value it sits at the depth of its ranges, except that it moves into a loop holding all its uses when that loop writes the version it reads.

Taught in 3.2 Memory in loops, 3.5 Rendering loops

loop-carried

A value one iteration produces and the next iteration reads, like an accumulator.

Taught in 3.2 Memory in loops

loop-invariant

A value that's the same in every iteration of a loop, so it can be hoisted out.

Taught in 3.5 Rendering loops

mask

A bool deciding whether a computed value is used or replaced, typically with where. Padding uses a mask to put zeros outside the data.

Taught in 3.4 A convolution by hand, 5.5 Rangeify movement ops

materialize

Computing a value once into a temporary buffer and reading the buffer wherever it's used. In .uir, stage forces it.

Taught in 4.4 Fuse or materialize

memoization

Remembering each node's result so shared work runs once. Without it, a graph with lots of sharing takes exponential time.

Taught in 1.1 The UOp, 1.2 .uir and interpreting

movement op

An op that rearranges elements without computing anything: reshape, permute, pad, shrink, expand.

Taught in 5.2 Reshape and permute, 5.3 Pad, shrink, expand, stack

mutant

A copy of the reference compiler with one plausible bug planted in it. The tests must make every mutant fail, which proves they catch that kind of mistake.

Taught in 1.6 Lab: your compiler

NaN

Not a number: the f32 result of things like inf - inf or 0/0. Every ordered comparison with NaN (like cmplt) is false, but in .uir asserts NaN equals NaN.

Taught in 1.2 .uir and interpreting, 1.4 Symbolic simplification

negative zero (-0.0)

A second zero in f32 with its sign bit set. It compares equal to 0.0, but recip tells them apart (-inf vs inf).

-1.0 * 0.0 is -0.0

Taught in 1.2 .uir and interpreting, 1.4 Symbolic simplification

opam

OCaml's package manager. It installs compilers and libraries such as dune. Python's counterpart is pip, though this course's Python track needs only the standard library.

Taught in 0.6 OCaml crash course

open range

A range a value depends on that no end has closed yet. A value with open ranges lives inside those loops.

Taught in 3.1 Ranges and end

option

An OCaml type for a value that may be missing: Some v or None. Code that uses one has to handle both. Python uses None for a missing value, and a type hint such as int | None says it may be missing, but nothing forces you to check.

match o with Some v -> v | None -> 0

Taught in 0.6 OCaml crash course, 0.7 Python for this course, 1.2 .uir and interpreting

oracle

The reference compiler, _reference/uirc.py. Run it to see what any program should do. The grader compares you to it. Don't read its source.

python _reference/uirc.py run FILE

Taught in 1.6 Lab: your compiler

overflow

A result too big for its type. i32 overflow wraps in .uir, but in C, signed overflow is undefined behavior.

Taught in 0.1 C and pointers, 2.4 Rendering C

pad

The .uir movement op that grows a tensor with zeros on each side of each axis.

pad [1 2] by 1 on both sides gives [0 1 2 0]

Taught in 5.3 Pad, shrink, expand, stack

param

A function input in .uir: param N is slot N of the enclosing call.

%x = param 0 dtype=i32

Taught in 1.2 .uir and interpreting, 1.5 CALL, PARAM, STACK, INDEX

parser

The part of a compiler that works out the structure of the words the lexer found.

Taught in 0.3 Compilers and IRs

pattern match

OCaml's way of branching on the shape of a value, naming its parts as it goes. Python 3.10 has the same idea in its match statement, with class patterns such as case Add(x, y):.

match card with Number (n, _) -> n | Ace _ -> 11

Taught in 0.6 OCaml crash course, 0.7 Python for this course

permute

The .uir movement op that reorders axes. A transpose is permute [1 0].

shape (2, 3) permuted [1 0] is (3, 2)

Taught in 5.2 Reshape and permute

pointer

A variable holding an address. *p reads what it points at, and p + 1 moves by one element, not one byte.

int *p = a;

Taught in 0.1 C and pointers

pure

Having no side effects: the same inputs always give the same result and nothing else changes. Pure calls can be inlined or computed once.

range

The .uir loop counter: range n takes the values 0 to n-1. Its statement name is the loop's name.

%i = range 4

Taught in 3.1 Ranges and end

rangeify

The pass that removes shapes from ops by asking each value for its element at an index, turning whole-tensor programs into loops.

Taught in 4.3 Rangeify, 5.5 Rangeify movement ops

rank

The number of axes a value has. A scalar is rank 0, a vector rank 1, a matrix rank 2.

Taught in 0.4 Tensors and shapes, 5.1 Any rank, flat memory

recip

The .uir reciprocal, 1/x, on f32. recip 0.0 is inf and recip -0.0 is -inf.

reduce

The .uir op that collapses leading axes with add, mul or max, as a left fold from the first element.

reduce [1 2 3] op=add gives 6

Taught in 4.2 Reduce and expand, 5.1 Any rank, flat memory

ref

An OCaml mutable cell. ! reads it and := writes it. Python has no separate cell: variables and attributes can be reassigned directly.

let r = ref 0 in r := !r + 1

Taught in 0.6 OCaml crash course

register

One of a few dozen named storage slots inside the CPU, where arithmetic actually happens.

Taught in 0.2 Memory and caches

render

Printing the program as C. From week 2 your compiler has a render command whose C the grader compiles and runs.

Taught in 2.4 Rendering C

reshape

The .uir movement op that reads the same elements, in row-major order, under a new shape.

[0..11] as shape (3, 4)

Taught in 5.2 Reshape and permute

rewrite rule

A pattern and a replacement: wherever the pattern matches, put in the replacement.

add(x, 0) -> x

round to nearest even

The f32 rounding rule: go to the nearest representable value, and on an exact tie go to the one whose last bit is 0.

like rounding 2.5 to 2 and 3.5 to 4

row-major

Storing a tensor so the last axis changes fastest: a matrix is stored row after row.

Taught in 0.2 Memory and caches, 0.4 Tensors and shapes, 5.1 Any rank, flat memory

runtime

The part of the system that compiles the rendered C, runs it, and reads the results back.

Taught in 2.5 The runtime

scalar

A single value with no axes: shape ().

Taught in 0.4 Tensors and shapes, 1.2 .uir and interpreting

schedule

The order a compiler runs operations in. Loads of a version have to be scheduled before the store that overwrites it.

Taught in 2.4 Rendering C, 3.5 Rendering loops

shape

The size of each axis of a value, written as a tuple. () is a scalar, and (3, 4) is a 3 by 4 matrix.

Taught in 0.4 Tensors and shapes, 1.2 .uir and interpreting

shrink

A window. On memory it's a view into a buffer (week 2), and on a value it's a sub-tensor at given offsets (week 5).

shrink %b 1 shape=[2]

Taught in 2.1 Buffers and views, 5.3 Pad, shrink, expand, stack

simplify

Your compiler's second command: rewrite %out to fewer ops while computing the same value for every input.

Taught in 1.3 Rewrites and folding, 1.4 Symbolic simplification

slot

A numbered position: a param's input number in a call, or a buffer's position in the kernel's arguments.

Taught in 1.5 CALL, PARAM, STACK, INDEX, 2.1 Buffers and views

spec

The written rules of the .uir language for each week, in spec/uir-weekN.md.

Taught in 1.6 Lab: your compiler

src

The list of nodes a UOp takes as inputs (its sources).

add %a %b has src (a, b)

Taught in 1.1 The UOp

stack

The .uir op that joins values of one shape along a new leading axis.

stack 10 20 30 has shape (3,)

Taught in 1.5 CALL, PARAM, STACK, INDEX, 5.3 Pad, shrink, expand, stack

stage

The .uir op that tells the compiler to materialize a value into a temp buffer. Same value, different cost.

Taught in 4.4 Fuse or materialize

store

The .uir op that writes a value into memory through a view. It produces an effect, not a value.

%s = store %v 99

Taught in 2.2 Load, store, after

stride

How far apart, in elements, two neighbors along an axis are in memory. In a row-major (3, 4) matrix, axis 0 has stride 4 and axis 1 stride 1.

Taught in 0.2 Memory and caches, 0.4 Tensors and shapes

subnormal

An f32 smaller than the smallest normal f32, stored with less precision. The smallest positive one is about 1.4e-45.

substitution

Replacing each param in a body with the matching argument. The mental model for how call works.

tensor

An array with any number of axes: a number has 0, a vector 1, a matrix 2.

Taught in 0.4 Tensors and shapes

toposort

Putting a graph's nodes in an order where every node comes after its sources.

Taught in 0.3 Compilers and IRs, 2.4 Rendering C

truncation

Rounding toward zero. C's integer division truncates, so -7 / 2 is -3.

Taught in 0.1 C and pointers, 1.2 .uir and interpreting

two's complement

How signed integers are stored: the top bit is worth minus 2^31 instead of plus. All ones means -1.

0xffffffff is -1

Taught in 0.1 C and pointers

undefined behavior (UB)

Code the C standard gives no meaning to, such as signed overflow or INT_MIN / -1. The compiler may assume it never happens, and the grader's sanitizer turns it into a crash.

Taught in 0.1 C and pointers, 2.4 Rendering C

UOp

The course's graph node: an op name, a tuple of sources (src) and an argument (arg), plus its dtype and shape.

UOp(op, src, arg)

Taught in 1.1 The UOp

variant

An OCaml type made of named alternatives (constructors), each possibly carrying data. In Python, an Enum covers alternatives with no data, and one dataclass per alternative covers the rest.

type suit = Hearts | Spades

Taught in 0.6 OCaml crash course, 0.7 Python for this course

version

Memory as it is at one point in the program: the original buffer, or the buffer after some store. Each after makes a new version.

Taught in 2.2 Load, store, after

view

A window into memory made with shrink: a start offset and a length (or one element). Loads and stores go through views.

Taught in 2.1 Buffers and views

void

The dtype with no value. Asserts, stores and ends produce void.

Taught in 1.2 .uir and interpreting, 3.1 Ranges and end

where

The .uir select: where c a b is a if c is true, else b. Both branches are evaluated.

where (cmplt x 0) 0 x