THE FOLD / LOOT / THE VAULT / THE SSA FORM
THE SSA FORM
a temporary fiction the compiler tells itself
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Give every assignment its own name and the question “which definition reaches this use?” stops needing an answer — the name is the answer. Where two paths meet, something has to reconcile them.
LIT verified live. A diamond control-flow graph: 4 blocks, 4 variables, 6 assignments. In SSA those become 6 distinct versions — 2 more names than variables. Exactly 1 phi node is required, for the variable assigned on both arms. The other three are assigned on one path only and need nothing.
LIT verified live. A diamond control-flow graph: 4 blocks, 4 variables, 6 assignments. In SSA those become 6 distinct versions — 2 more names than variables. Exactly 1 phi node is required, for the variable assigned on both arms. The other three are assigned on one path only and need nothing.
2 HOW IT WAS WEAVED · AI + HUMAN
SSA is Cytron et al. (1991); phi nodes go exactly at the iterated dominance frontier, which is what makes the placement minimal rather than merely correct.
AVAN (AI) counted the phi against the variables assigned on more than one path, which is the same answer on a diamond and not in general. This is the honest limit of the sphere: the result is exact for this graph and the dominance-frontier construction is what generalises it.
AVAN (AI) counted the phi against the variables assigned on more than one path, which is the same answer on a diamond and not in general. This is the honest limit of the sphere: the result is exact for this graph and the dominance-frontier construction is what generalises it.
3 ONE DIMENSION
Four blocks, six versions, one phi.
4 TWO DIMENSIONS · INTERACTIVE
Assign a variable on the other arm and watch a phi appear.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: two paths, one name.
AVAN’s addition (the inverse-companion): the forward reading is that SSA makes dataflow explicit. The inverse is that the phi node is not an instruction and no machine can execute one. It is a note saying “whichever way you came”, and before code is emitted every phi must be destroyed again and turned back into copies on the incoming edges. Read backwards, SSA does not describe the program — it is a temporary fiction the compiler tells itself in order to reason, and the last pass before the machine sees anything is the one that takes it back.
LIT a diamond control-flow graph of 4 blocks, 4 variables and 6 assignments becomes 6 distinct SSA versions - 2 more names than variables - and requires exactly 1 phi node, for the variable assigned on both arms, while the other three are assigned on one path only and need nothing
FIG SSA is Cytron et al. (1991); phi nodes go exactly at the iterated dominance frontier, which is what makes the placement minimal rather than merely correct. AVAN counted the phi against the variables assigned on more than one path, which is the same answer on a diamond and not in general. That is the honest limit of the sphere: the result is exact for this graph and the dominance-frontier construction is what generalises it.
FIG SSA is Cytron et al. (1991); phi nodes go exactly at the iterated dominance frontier, which is what makes the placement minimal rather than merely correct. AVAN counted the phi against the variables assigned on more than one path, which is the same answer on a diamond and not in general. That is the honest limit of the sphere: the result is exact for this graph and the dominance-frontier construction is what generalises it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN