Skip to content

Lab 16.L1 · SSA construction: minimal, semi-pruned and pruned (Cytron) vs Braun et al. (vs ★ Aycock–Horspool)

Chapter: 16 · Static Single Assignment Form · Lessons: 16.1, 16.2, 16.3 · Time: 8–12 hours · Tests: ./course test 16 (label ch16)

Goal

Turn Chapter 8's three-address code into Chapter 8's block-argument SSA with four algorithms:

  • Cytron et al.'s construction in the three flavors: minimal, semi-pruned and pruned.
  • Braun et al.'s on-the-fly construction, with trivial-phi and redundant-SCC removal.
  • ★ Optionally, Aycock and Horspool's "phis everywhere, then minimize".

Every algorithm must produce valid SSA that computes the same value, with exactly the number of phis (block parameters) the lessons predict. Then measure how the phi counts and running times differ on a 306-listing corpus.

Requirements

Terms: blocks, the CFG and the entry block are as in Input and output formats. A variable is any name that appears in the listing. \(\mathrm{defs}(v)\) is entry plus every block that assigns \(v\). Every variable is implicitly 0 on entry, as in the tac semantics. A phi is a block parameter.

  • R1. Valid SSA. construct(L, A) returns a function that ssair::print prints and irforms::validateSSA accepts: rules S0–S4 of Lab 8 · forms.
  • R2. Same value. Running the result (irforms::run(Form::SSA, …)) returns what the listing returns (irforms::tac::run).
  • R3. Minimal (Cytron et al.). For every variable \(v\), there is one parameter for \(v\) at each block of \(\mathrm{DF}^+(\mathrm{defs}(v))\) and nowhere else (Definition 16.1.7, Algorithms 16.2.1 and 16.2.3). Copies x = a stay copy instructions. \(\mathrm{DF}\) is computed on the CFG of reachable blocks.
  • R4. Semi-pruned. As R3, but only for variables that are upward-exposed in some block: read in the block before any assignment in it.
  • R5. Pruned. As R3, restricted to the blocks where \(v\) is live on entry (Definition 16.1.7). Liveness is computed on the variables of the listing, and a use in an instruction happens before that instruction's definition.
  • R6. Braun et al. Algorithms 16.3.2–16.3.4:
  • Blocks are filled in listing order, and each block is sealed as soon as all its predecessors are filled.
  • Copies are folded: x = a emits nothing, and makes x's current value the current value of a.
  • Integer constants are values, and two constants are equal when their integers are equal.
  • Trivial phis are removed recursively, then redundant phi SCCs.

The number of parameters left is fixed by Theorem 16.3.8. It is the same as this procedure: place a phi for \(v\) at every join block where \(v\) is live on entry, rename with copy folding, then remove trivial phis and redundant SCCs until nothing changes. - R7 ★. Aycock–Horspool. - Place a parameter for every variable at every block with two or more predecessors. - Rename with copy folding, as in R6. - Apply the two rules of Algorithm 16.3.5 until neither applies: x = φ(x, …, x) is removed, and x = φ(x|y, …, x|y) is replaced by y. - There is no SCC step and no liveness.

implementsAlgorithm(AycockHorspool) returns true only once you do this; its tests are skipped until then. - R8. Contract and speed. - implementsAlgorithm is true for Minimal, SemiPruned, Pruned and Braun. - construct returns an error string only for input outside this spec. The tests never pass one. - ch16-ssa-compare must finish every required algorithm on its 306 listings in under 2 s (the reference solution needs 120–230 ms per algorithm in the course container).

Names of SSA values, the order of parameters and the order of instructions within the rules of S2 are yours: the tests compare values and counts, not text.

The contract

// labs/ch16-ssa-construct/include/ssalab/Construct.h  (provided; do not change)
namespace ssalab {
enum class Algorithm { Minimal, SemiPruned, Pruned, Braun, AycockHorspool };
const char *algorithmName(Algorithm A);               // provided
std::expected<ssair::Function, std::string>
construct(const irforms::tac::Listing &L, Algorithm A); // yours (R1-R7)
bool implementsAlgorithm(Algorithm A);                   // yours (R8)
}

ssair::Function (include/ssair/SSA.h, provided) is a plain value type: blocks with a name, parameters, instructions and a terminator (br, cbr, ret) whose targets carry argument lists. ssair::print and ssair::parse convert it to and from Chapter 8's ssa text. phiCount() is the number of parameters.

The command-line driver is provided:

usage: ch16-ssa [--algo=minimal|semi-pruned|pruned|braun|aycock-horspool] [--stats] (<file> | -)

It prints the SSA text on stdout (default pruned). With --stats it also prints phis: N on stderr.

Input and output formats

The input is a Chapter 8 tac listing (format), cut into basic blocks at the Chapter 8 leaders:

  • A block is named by the first label of its first instruction, and otherwise B<k>.
  • If the first block has predecessors, an empty block entry (entry.N if the name is taken) is prepended, so that the entry block has no predecessors (rule S4).
  • Unreachable blocks are dropped.
  • A block's successors are the jump target first, then the fall-through.

include/ssair/BlockCFG.h (provided) does exactly this and also gives you the dominator tree, \(\mathrm{DF}\) and RPO. inputs/running.tac is the running example of Lessons 15.3 and 16.2:

$ ch16-ssa --algo=pruned --stats inputs/running.tac > /dev/null
phis: 5

The expected counts for it:

Algorithm minimal semi-pruned pruned braun aycock-horspool
phis 10 7 5 5 10

The program returns 65.

Provided infrastructure

File What it gives you
include/ssair/SSA.h, provided/SSA.cpp the SSA value type, printer, parser, isConstant, phiCount
include/ssair/BlockCFG.h, provided/BlockCFG.cpp TAC basic blocks, CFG, dominator tree (children in RPO), \(\mathrm{DF}\), dominates, usesOf
provided/Names.cpp algorithmName
tools/ConstructMain.cpp, bench/Compare.cpp the ch16-ssa driver and the ch16-ssa-compare benchmark
inputs/running.tac the running example
Chapter 8's irforms library the TAC reader, irforms::run, irforms::validateSSA

Liveness, \(\mathrm{DF}^+\), renaming and Braun et al.'s maps are the learning objective and are not provided.

What the tests check

Test Checks
ch16_construct_test Construct.Minimal, .SemiPruned, .Pruned, .Braun, .AycockHorspool R1, R2 and the exact count of R3–R7 on all 303 listings of tests/ch16/Inputs/construct-corpus.txt: the running example, a two-entry (irreducible) loop, a copy-swap loop, 140 lowered random Tiny programs and 160 random goto programs, some of them irreducible. The goldens come from the Python oracle (tools/course/lib/ssa.py).
Construct.FlavorsAreNested minimal ≥ semi-pruned ≥ pruned ≥ Braun on every listing (Theorems 16.1.12 and 16.3.8)
Construct.RequiredAlgorithms R8's implementsAlgorithm
tests/ch16/lit/lab-construct.test the driver on inputs/running.tac: 10/7/5/5 phis, value 65
ch16.lab.compare-smoke ch16-ssa-compare --quick runs without errors

Milestones

  1. Minimal. \(\mathrm{DF}^+\) by the worklist, then renaming with one stack per variable (Algorithm 16.2.3). Make Construct.Minimal pass.
  2. Semi-pruned and pruned. Add the upward-exposed scan and a liveness pass (Ch 14). Make Construct.SemiPruned and Construct.Pruned pass.
  3. Braun et al. Write readVariable, sealBlock and tryRemoveTrivialPhi with copy folding, then the SCC pass. The irreducible inputs fail until the SCC pass is right.
  4. ★ Aycock–Horspool.
  5. Measure. Run build/<preset>/labs/ch16-ssa-construct/ch16-ssa-compare and fill in:
Algorithm phis (306 listings) time (ms) reference: phis on the 303 corpus listings
minimal 19 106
semi-pruned 8 620
pruned 4 477
braun 4 352
★ aycock-horspool 18 990

Explain in two sentences why Braun can be below pruned (copy folding: Lesson 16.3 §5, "At scale") and why Aycock–Horspool is so close to minimal on this corpus (Theorem 16.3.9: its phis lie in \(\Phi_{\min}\) on reducible CFGs, but it never removes dead phis).

Hints

Hint 1 — where to start

Build a BlockCFG from the listing and print its blocks, \(\mathrm{DF}\) and dominator tree for inputs/running.tac. Compare them with Lesson 16.2 §3. Then do minimal placement for one variable and check the blocks against the lesson's table before renaming anything.

Hint 2 — the key idea

All three Cytron flavors share one renaming walk; only the phi blocks differ. Renaming must visit dominator-tree children and pop exactly what it pushed. Branch arguments for a successor \(S\) are the stack tops at the end of the current block, in the order of \(S\)'s parameters. For Braun, readVariable in an unsealed block must create an incomplete phi and record it; sealing fills it later. A trivial phi's users must be re-checked after its replacement (Lesson 16.3's pitfall).

Hint 3 — a design sketch
  • Keep a per-variable list of definition blocks, a per-block upward-exposed set and a live-in bit set.
  • For renaming, keep a std::vector<std::string> stack per variable, starting with the constant "0".
  • For Braun, give each phi an id and a replacement pointer. Follow replacements whenever you read a value, like union–find without ranks.
  • Run the SCC pass (Tarjan on the phi-operand graph, operands first) after all blocks are sealed.

The most common failure is an off-by-one in the irreducible inputs: the trivial-only version leaves a redundant 2-phi SCC, and Construct.Braun reports one phi too many.

Stretch goals ★

  • R7 (Aycock–Horspool).
  • A --trace flag for the driver that prints Braun's events (created, incomplete, removed) the way the oracle's braun_ssa(..., trace=[]) does. Compare with Lesson 16.3's trace table.