A catalog of ways to generate SSA

Static Single Assignment is a program representation where each “variable”
(though this term can be misleading) is assigned exactly once. Mostly the
variables aren’t variables at all, but instead names for values—for
expressions. SSA is used a lot in compilers. I’m making this page to catalog
the papers I have found interesting and leave a couple of comments on them.

A brief bit of background

It comes from the 1980s. Wikipedia claims the first paper about it (though not
by the name SSA) was Code
Motion of Control Structures in High Level
Languages (PDF), which I had not seen
before today. There was also Global Value Numbers and Redundant
Computations (PDF), which I had also not seen
before today.

If you’re confused about what a phi function is: they are annotations that join
dataflow edges from predecessor blocks into new variables. It’s not a real
function, it doesn’t (directly) generate any code, and it needs to be handled
differently than other instructions in your IR.

Let’s generate some variables

Finally, in 1991, the same group produced the first SSA paper I was already
familiar with: The Cytron Paper (PDF). This
approach requires computing dominance frontiers for an existing control-flow
graph, which may or may not be useful or applicable in your situation. If you
have bytecode, this might be workable, but you’ll need to “discover” the basic
blocks hiding within. It’s also a notable
paper because it produces the minimal amount of phi instructions.

In 1994, Brandis and Mössenböck write Single-Pass Generation of Static
Single-Assignment Form for Structured
Languages (PDF). This is a neat approach
because it shows that you don’t need to do Fancy Algorithms or Fancy Data
Structures to get SSA—you can build it as soon as during parsing, something I
have taken to doing recently. It turns out that if you don’t have goto,
things get easier for the compiler developer.

In 1995, Richard Kelsey writes about how CPS and SSA are similar in A
Correspondence between Continuation Passing Style and Static Single Assignment
Form (PDF). Part of the paper involves
converting CPS to SSA (and the reverse, too).

Also in 1995, Cliff Click and Michael Paleczny publish A Simple Graph-Based
Intermediate Representation (PDF), which has become
known as the Sea of Nodes IR. It’s like “normal” SSA except that instead of
just having blocks and data edges between instructions, all instructions are
“unscheduled” and have control edges between them. It means your graph looks
all funky but doesn’t implicitly have (kind of arbitrary) code linearization so
code motion is easier. Cliff and co are building a working demo
compiler. See also Global Code Motion /
Global Value Numbering (PDF) by Cliff Click.

In 1998, Appel (of functional language fame) describes briefly a correspondence
between functional languages and SSA in SSA is Functional
Programming (PDF). I think this
is the first paper that introduced a notion of “basic block arguments” (instead
of phi functions). He also suggests a “really crude” algorithm for generating
SSA that places phi nodes all over the place for every variable.

In 2000, Aycock and Horspool publish Simple Generation of Static
Single-Assignment Form (PDF). It starts
from Appel’s approach and then iteratively deletes phi nodes that don’t need to
exist. They find that for reducible control-flow graphs (the common case for
most compilers, I think), their approach also produces minimal SSA.

In 2009, Michael Bebenita writes Constructing SSA the Easy
Way (PDF) which is “essentially a rehashing of
Aycock’s SSA construction algorithm but using forwarding pointers instead”. I
only found it the other day. It’s fantastic and I wish more people knew about
it. It uses one of my favorite data structures, union-find, though for some
reason it does not mention it by name.

In 2013, my former coworker Matthias Braun and his labmates write Simple and
Efficient Construction of Static Single Assignment
Form (PDF), which describes converting to SSA from
an AST and building the CFG on the fly. It’s fairly popular because it is
simpler than the Cytron paper. I find the phase transitions in the blocks
(filled/sealed/…) a little tricky to keep straight though.

In 2023, Matthieu Lemerre writes SSA Translation Is an Abstract
Interpretation (PDF), which I would love to
understand one day.

Other papers

I will eventually add some papers on extensions to SSA, analyses on SSA,
converting out of SSA (including register allocation). Just not this evening.

I am also probably missing or forgetting some big hit papers for converting
into SSA, so please drop me a line if you have favorites.

Other resources

The SSA book (PDF; draft) is a huge tour de force
of SSA-based compiler design. That is even the new name of the book, which has
since been published in
print. It’s on my
shelf.

A keyword dump

Here are some keywords which you may search for but mostly serve as notes to
self to write more about one day:

windmill, lost copy
SCCP
liveness
DCE
chordal

Efficient global register allocation

In a compiler, an essential component is the register allocator. Two main algorithms have dominated implementations, graph coloring and linear scan, differing in how live values are modeled. Graph coloring uses an edge in an `interference graph’ to show that two values cannot reside in the same register.

SSI and e-SSA and sparseness
GVN and CSE and hash consing
load/store forwarding
mem2reg
SROA and memory ssa
eager constant folding / smart constructors
points-to and CFA
flattening tuples
webs (see Muchnick’s 1997 Advanced compiler design and implementation)
RVSDG and co
e-graphs