Static single assignment form, SSA for short, is the shape almost every optimizing compiler gives a program before it improves it. The idea fits in one sentence: every value is written in exactly one place. What follows from that sentence is most of what a modern optimizer does, and it is easiest to learn by watching a real compiler do it.
This series uses Mica as the lab. One flag, --export, makes the compiler
write every stage of its work on your program into a folder: the
intermediate code, the control-flow graph, the dominator tree, the program in
SSA form, the program after leaving it, and a ledger of what each optimization
did. Each chapter compiles one small program, opens the files the chapter
explains, and asks you to change one thing and look again.
You do not need to know anything about SSA, dominators or dataflow analysis. You need to know what a variable, a loop and a function are, and you need to be able to read a few lines of Pascal-like code. Every term is explained the first time it appears.
The chapters
| # | Chapter | What you get out of it |
|---|---|---|
| 1 | The question SSA answers | the intermediate code a compiler works on, the question “which write does this read see?”, and how SSA puts the answer into the name |
| 2 | The graph and its dominators | basic blocks, edges, loops, and the dominator tree with its frontiers, read from the compiler’s own files |
| 3 | Where the φ functions go | why the merges go at the dominance frontiers, how the frontier is iterated, and why a variable nobody reads gets none |
| 4 | Renaming | how every write becomes a version and every read finds its version, by one walk over the dominator tree |
| 5 | What SSA makes easy | forwarding, constant folding, value numbering and dead code, before and after, with the ledger that counts them |
| 6 | Leaving SSA | why a machine needs the φ functions gone, the two classic traps, how Mica leaves the form by renaming, and further reading |
Read them in order: each chapter uses what the one before it explained.
What you need
The Mica compiler, mica. The Mica Developer container has it, and
Get started with Mica sets that up from nothing;
Installing Mica puts it on a Linux machine of your own.
Every command in the series runs in one terminal, in a folder of its own that
the first chapter makes. VS Code with the Mica extension is optional: it opens
the same files with colours, an outline by routine and block, and a drawing of
each routine’s graph and dominator tree.
How the series reads the files
Every listing on these pages is cut from a file the page’s own commands
write. The commands name the target, --platform linux,amd64,utf-8, so you
get the same files on any machine: the files this series reads come out the
same for either target, and naming one keeps every number on the page the
number on your screen. --compile stops after the assembly, so nothing is
linked and the commands work on an ARM64 machine too.
The numbers in the listings, such as t2.7, #21 or block 6, are the
compiler’s own. They change when a program changes. When you edit a program
and export it again, expect new numbers, and read them the way the chapters
read these.
The compiler, exported is the reference for every file the export writes. This series reads the six of them that tell the story of SSA, and explains each one as it arrives.