Skip to content

Lab 16.L2 · Out of SSA: naive copies vs edge splitting with optimal sequentialization vs value-based coalescing

Chapter: 16 · Static Single Assignment Form · Lessons: 16.6, 16.7 · Time: 8–10 hours · Tests: ./course test 16 (label ch16)

Goal

Translate Chapter 8's block-argument SSA back into three-address code in three ways, and count the copies each one leaves:

  • naive: Cytron et al.'s copies at the end of each predecessor. This reproduces the lost-copy and swap problems on purpose.
  • split: critical-edge splitting, with each edge's parallel copy sequentialized with the proven minimum number of moves.
  • coalesce: value-based coalescing in the style of Boissinot et al., then split on what is left.

Requirements

An edge copy of edge \(P \to B\) is the pair (parameter \(p_\ell\) of \(B\), argument \(a_\ell\) of the branch), for each \(\ell\). It is trivial if \(p_\ell = a_\ell\) as names. An edge is critical if \(P\) has two or more outgoing edges and \(B\) has two or more incoming edges. A cbr whose two targets are the same block has two edges. A copy in the output is a TAC instruction x = a.

  • R1. Output. destruct(F, M) returns a TAC listing (Chapter 8 tac format) that the reader accepts: labels unique, last instruction goto or return. Every SSA name becomes a TAC variable of the same name. Instructions keep their order within a block, and every block keeps its name as a label.
  • R2. Naive (Algorithm 16.6.1). For every edge \(P \to B\), append the non-trivial edge copies p = a to the end of \(P\), in parameter order, before \(P\)'s jump. For a cbr, emit the true edge's copies first, then the false edge's. Split no edges and add no temporaries. The result is then fully determined: the tests check its value (right or wrong) and its copy count (body copies + non-trivial edge copies).
  • R3. Split (Algorithms 16.6.3 and 16.7.5). Place each edge's non-trivial edge copies, as one parallel copy, in the first place that applies:
  • at the end of \(P\), if \(P\) has exactly one outgoing edge;
  • otherwise at the start of \(B\), if \(B\) has exactly one incoming edge;
  • otherwise in a new block on the edge.

Sequentialize every parallel copy with the minimum number of moves (Theorem 16.7.6). Its copy count is then exactly body copies + \(\sum_{\text{edges}}\) (non-trivial edge copies + pure cycles). The result must compute the SSA function's value. - R4. Coalesce (Algorithm 16.7.3). The result must compute the SSA function's value, with at most as many copies as R3 gives. - On conventional inputs (the .pruned entries: Cytron's pruned SSA, which folds no copies), every copy between a parameter and a name argument must disappear. The copy count is then at most body copies + the edge copies whose argument is a constant. - Use value-based interference (Definition 16.7.2). Remember that two parameters of one block always interfere. - R5. Fresh names. - The cycle-breaking temporary and the new blocks must not clash with any name in \(F\). The reference uses tmp (tmp.N if taken) and split.N. - One temporary per function is enough: sequentialize edge by edge. - R6. Counting and speed. ch16-out-of-ssa --stats prints copies: N on stderr, where N is the number of copy instructions in the output. All 564 test functions with all three methods must run in under 5 s.

The contract

// labs/ch16-out-of-ssa/include/outofssa/Destruct.h  (provided; do not change)
namespace outofssa {
enum class Method { Naive, Split, Coalesce };
const char *methodName(Method M);                        // provided: "naive", "split", "coalesce"
std::expected<irforms::tac::Listing, std::string>
destruct(const ssair::Function &F, Method M);            // yours (R1-R5)
}

ssair::Function is lab L1's value type (labs/ch16-ssa-construct/include/ssair/SSA.h). The input always passes irforms::validateSSA. Return an error string only for input outside that (the tests never pass one).

usage: ch16-out-of-ssa [--method=naive|split|coalesce] [--stats] (<file> | -)

The driver (provided) reads ssa text and prints tac text on stdout. The default method is split.

Input and output formats

Input: Chapter 8 ssa text. Here is Briggs et al.'s lost-copy program, inputs/lost-copy.ssa, which returns 4:

ssa
entry:
  br H(1)
H(x2):
  x3 = add x2, 1
  t = lt x3, 5
  cbr t, H(x3), X()
X:
  ret x2

Naive destruction puts x2 = x3 at the end of H, before the cbr. The exit then returns the new x2, which is 5. split places the copy for the critical edge H → H in a new block and returns 4 with 2 copies (x2 = 1 and the loop's x2 = x3). inputs/swap.ssa is the swap problem: the right value is −1, naive gives 0, and split needs 7 copies.

Output: a tac listing; see the lit test tests/ch16/lit/lab-destruct.test for the exact driver runs.

Provided infrastructure

File What it gives you
include/ssair/SSA.h (lab L1) the SSA value type and its parser and printer
Chapter 8's irforms library the TAC listing type, printer and interpreter (irforms::tac::run)
provided/Names.cpp, tools/DestructMain.cpp methodName and the driver
inputs/lost-copy.ssa, inputs/swap.ssa Briggs et al.'s two problems

Edge copies, edge splitting, the sequentializer, liveness of SSA names, interference and the coalescer are the learning objective and are not provided.

What the tests check

The corpus is tests/ch16/Inputs/destruct-corpus.txt, 564 functions, with goldens from tools/course/lib/ssa.py:

  • the lost-copy and swap programs;
  • the pruned (conventional) and Braun (transformed) SSA of the construction corpus;
  • all 256 parallel copies \((a, b, c, d) \gets (x_1, x_2, x_3, x_4)\) with \(x_i \in \{a, b, c, d\}\) on a critical loop edge.
Test Checks
ch16_destruct_test Destruct.NaiveFollowsR2 naive value and copy count equal the goldens (R2)
Destruct.NaiveShowsLostCopyAndSwap naive gets lost-copy and swap wrong
Destruct.SplitIsCorrectAndOptimal split value right; copy count exactly R3's
Destruct.CoalesceIsCorrectAndCheaper coalesce value right; copies ≤ split; on .pruned inputs ≤ the R4 bound
tests/ch16/lit/lab-destruct.test the driver: naive 5 and 0, split and coalesce 4 and −1, copies: 2 and copies: 7; coalesce leaves copies: 0 on tests/ch16/Inputs/value-copy.ssa, where a copy b = a is live together with a (only value-based interference merges them, R4)

Milestones

  1. Naive. Make NaiveFollowsR2 and NaiveShowsLostCopyAndSwap pass. Run the lit test and see 5 instead of 4.
  2. Split. Start with naive copies plus splitting. The swap and pcopy inputs fail until you sequentialize, so then write Algorithm 16.7.5. Check it on the drill: ./course drill parallel-copy --difficulty hard.
  3. Coalesce. Compute liveness of SSA names, then the pairwise interference test with values, then union–find classes. Rename to representatives and reuse split.
  4. Measure. Sum copies: over the corpus for each method and compare with the reference:
Inputs naive split coalesce Method I (for comparison)
pruned (conventional) 7 176 7 176 2 615 9 110
Braun (transformed) 4 594 4 595 2 195 6 468
256 parallel copies 2 304 2 342 2 086 —

(Naive is wrong on 158 of the 564 functions; its counts are not a success.)

Hints

Hint 1 — where to start

Collect, for every edge, the list of (parameter, argument) pairs and whether the edge is critical. Print them for lost-copy.ssa and compare with Lesson 16.6 §3. Everything else is built on this list.

Hint 2 — the key idea
  • A parallel copy is a graph where each destination has one source.
  • Emit copies whose destination nobody still needs to read first. When you copy d ← s, the old value of s now also lives in d, so redirect later readers of s to d.
  • Only when every remaining destination is still needed are you left with pure cycles. Break each one with a single move to the temporary.
  • For coalescing, two names whose live ranges overlap may still share a variable if one is a copy of the other: the value, not the name, decides (Definition 16.7.2).
Hint 3 — a design sketch
  • An EdgeCopies record per edge: source block, target block, pairs.
  • A sequentializer that takes pairs and a temporary name and returns moves.
  • A liveness pass over SSA names: backward, with block parameters defined at the block entry and branch arguments used at the end of the predecessor.
  • A values map (copy chains to their root) and a union–find of classes.

The bug the tests catch most often: treating a cycle with a copy hanging off it, like \((a, b, c) \gets (b, a, a)\), as a pure cycle. That emits one move too many, and SplitIsCorrectAndOptimal reports the count.

Stretch goals ★

  • Implement Sreedhar's Method I as a fourth mode and check its copy count against the table (the oracle's sreedhar_method1_copies).
  • Replace the pairwise class-interference test with Algorithm 16.7.4 (dominance order) and time both on large generated functions.