Lab 17 · Simple CP vs SCCP, and hash-based vs partition-based value numbering¶

Chapter: 17 · SSA-Based Scalar Optimizations · Lessons: 17.1 (Part A), 17.4 and 17.5 (Part B) · Time: 8–12 hours · Tests: ./course test 17 (label ch17: ch17.Compare.*, ch17.lab)

Goal¶

This is the chapter's comparison lab. It asks for two pairs of analyses on LLVM IR in SSA form, each pair sharing one contract function. You will measure the difference in precision within each pair.

Part A. Simple sparse constant propagation, which treats every block as executable (Algorithm 17.1.6), and sparse conditional constant propagation (SCCP, Algorithm 17.1.8). Theorem 17.1.12 says SCCP finds at least as much. The corpus shows how much more.
Part B. Dominator-based hash value numbering (DVNT, Algorithm 17.4.5) and Alpern–Wegman–Zadeck congruence partitioning (Algorithms 17.5.3–17.5.4). Theorem 17.5.12 says the partition contains the hash classes. The corpus shows where they differ: loop phis and sibling blocks.

Both parts are analyses: they report facts and never modify the function. The provided driver ch17-compare prints the facts, and a Python oracle computes the same facts independently, so the tests can require exact agreement.

Requirements¶

Part A: constant propagation¶

Tracked instructions. An instruction is tracked if its result type is an integer type (including i1), and it is a phi, a binary operator, an icmp, a select, or a cast whose source type is also an integer type. Every other instruction that produces a value is overdefined as soon as its block is executable.

R1 (lattice). Each tracked instruction has a value in the constant lattice of Definition 17.1.1: Unknown (⊥, the optimistic start), one ConstantInt, or Overdefined (⊤). The value of an operand is defined as follows:
a ConstantInt operand is that constant;
an instruction operand has the instruction's current lattice value;
anything else is Overdefined: function arguments, globals, undef, poison and constant expressions.

You never fold anything to undef or poison. - R2 (transfer functions). The rules apply in this order: - A phi joins its operands on executable incoming edges (R3). Equal constants join to that constant. - A select with a constant condition takes the selected operand. With an Overdefined condition, it is Overdefined if an arm is; else the join of the arms once both are known; else it waits. - Any other tracked instruction is Overdefined if an operand is. It waits (stays Unknown) while an operand is Unknown. Otherwise it is folded with llvm::ConstantFoldInstOperands: a ConstantInt result is the new value, and anything else (for example sdiv 7, 0, whose fold is poison) is Overdefined. - R3 (A1, CPAlgorithm::Simple). Every block is executable and every CFG edge is executable. Phis join all their operands. Branch conditions are ignored. - R4 (A2, CPAlgorithm::SCCP). Definition 17.1.7 with two worklists (Algorithm 17.1.8): - The entry is executable. - A br makes its edge executable. - A conditional br or switch on a constant makes exactly the selected edge executable. On Overdefined it makes all its edges executable. On Unknown it waits. - Instructions in non-executable blocks are never evaluated. - When both worklists are empty and a branch in an executable block still waits on an Unknown instruction, set that instruction to Overdefined and continue. This can only happen when the condition depends on values the solver never reached.

Output. propagateConstants returns Constants, the tracked instructions in executable blocks whose value is a constant, and Executable, the executable blocks. For Simple, Executable is every block. F must be unchanged.

Part B: value numbering¶

Candidates and congruence. An instruction is a candidate if it is a phi, a binary operator, a compare (icmp/fcmp), a select, a cast or a getelementptr. Its label is its opcode, result type and number of operands, plus the predicate for compares, the source element type for GEPs, and the parent block for phis. Poison-generating flags (nsw, exact, …) are not part of the label. The operand list is the operands in order, except for phis, whose incoming values are ordered by incoming block (any fixed order of blocks, applied to all phis alike). Two candidates are congruent when their labels are equal and their operands are pairwise congruent. A non-candidate value (argument, constant, load, call, …) is congruent only to itself. There is no commutativity and no algebra: add a, b and add b, a are not congruent here.

R5 (B1, VNAlgorithm::Hash). DVNT (Algorithm 17.4.5).
Walk the dominator tree in preorder, visiting children in reverse postorder, with a scoped hash table from (label, value numbers of the operands) to a leader.
An operand with no value number yet counts as itself. In practice that is a phi operand over a back edge.
A candidate whose key is in the table gets the leader's number. Otherwise it becomes a new leader.
Leaving a dominator-tree node removes the keys it added.
Candidates in blocks unreachable from the entry are each in a class of their own.
R6 (B2, VNAlgorithm::Partition). The coarsest congruence (Definition 17.5.2, Theorem 17.5.10) over all candidates, including those in unreachable blocks. Start optimistically, with one class per label, and split until every class is stable. The tests compare you with a brute-force greatest fixed point on pairs. Use Hopcroft-style splitting (Algorithm 17.5.4, \(O(E \log N)\)) or signature refinement (Algorithm 17.5.3). Both give the same partition.
R7 (output). congruenceClasses returns a partition of exactly the candidates of F: every candidate in one class, singletons included, and nothing else. The order of the classes and of the members is free. F must be unchanged.
R8 (precision ordering). This follows from R5–R6 and is checked separately:
every hash class lies inside one partition class;
on the corpus, the partition finds strictly more congruences;
on the corpus, SCCP finds strictly more constants than simple CP.

Both parts¶

R9 (agreement with the oracle). ch17-compare --dump on the oracle's random functions prints exactly what tools/oracle.py dump prints (format below).
Performance. Both parts are linear or near-linear: \(O(U + e + I)\) for the CP algorithms and \(O(I + U)\) for DVNT, while AWZ is \(O(E \log N)\) with Hopcroft. On the course machine, the reference solution handles the corpus (12 functions) in under 0.2 ms per algorithm and the 60-function oracle module in about 1 ms per algorithm (ch17-compare --table --time). Anything under 100 ms per module passes.

The contract¶

// labs/ch17-scalar/include/lab17/Compare.h  (provided; do not change)
namespace lab17 {
enum class CPAlgorithm { Simple, SCCP };
struct ConstantFacts {
  std::vector<std::pair<const llvm::Instruction *, llvm::APInt>> Constants; // tracked, executable, constant
  std::vector<const llvm::BasicBlock *> Executable;                        // Simple: every block
};
ConstantFacts propagateConstants(llvm::Function &F, CPAlgorithm A);        // A1, A2 (R1-R4)

enum class VNAlgorithm { Hash, Partition };
std::vector<std::vector<const llvm::Instruction *>>
congruenceClasses(llvm::Function &F, VNAlgorithm A);                        // B1, B2 (R5-R7)
}

Neither function may modify F. They are called on functions with bodies only.

Input and output formats¶

Input: textual LLVM IR as produced by clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names followed by opt -passes=mem2reg (the corpus: corpus/*.c and their .ll files; the generating command is in each .ll header), or the oracle's random functions (oracle.py gen), which use add sub mul and or xor and icmp eq ne slt sle on i32, phis, br, conditional br and ret.

ch17-compare --dump <file.ll>... prints per function (values named as in the IR, members of a class and constants in instruction order, classes ordered by their first member, singletons omitted, i1 constants as 0/1, wider constants signed):

@run
  simple:
  sccp: x.0=1 cmp1=0 x.1=1
  sccp-executable: entry while.cond while.body if.end while.end
  hash:
  partition: {i.0 j.0} {add add2} {mul mul3}

ch17-compare --table [--time] <file.ll>... prints the measurement table (below).

Provided infrastructure¶

File	What it gives you
`include/lab17/Compare.h`	the contract
`tools/CompareMain.cpp`	`ch17-compare --dump` / `--table [--time]`
`tools/oracle.py`	`gen --count N --seed S` (random SSA functions as LLVM IR) and `dump --count N --seed S` (the expected `--dump` output), built on `tools/course/lib/scalaropt.py`, the same reference code as the drills `sccp-trace` and `vn-partition`
`corpus/.c`, `corpus/.ll`	five C files, 12 functions: the running example, branches with configured flags, loops with twin induction variables, redundancy in diamonds and siblings, bit operations
`src/Stub.cpp`	the two contract functions, stopping with `TODO(ch17)`

What the tests check¶

Test	Checks
`ch17.Compare.RunningExampleConstants`	on `corpus/running.ll`: simple CP finds no constant, and SCCP finds `x.0 = 1`, `cmp1 = 0`, `x.1 = 1`, with `if.then` not executable (R1–R4)
`ch17.Compare.RunningExampleCongruences`	hash VN finds no congruence, and the partition finds `{i.0, j.0}`, `{add, add2}`, `{mul, mul3}` (R5–R7)
`ch17.Compare.CorpusPrecisionOrderingAndSoundness`	on every corpus function: `F` is unchanged; `Simple` marks every block executable; every constant simple CP finds in a block SCCP executes is also an SCCP constant with the same value; both VN results are partitions of exactly the candidates and every class is a congruence under the label rule; the partition equals a brute-force greatest fixed point on pairs (coarsest); every hash class lies inside a partition class; totals: SCCP > simple and partition > hash (R1–R8)
`ch17.lab` `scalar-oracle.test`	`--dump` equals the oracle on 3 × 60 random functions (seeds 1–3) (R9)
`ch17.lab` `scalar-corpus.test`	the `--dump` of the running example, the `run` row and the `TOTAL` row of the `--table` output (below)

Milestones¶

A1 (simple CP): ch17-compare --dump corpus/branches.ll shows constants; ctest --test-dir build/<preset> -R ch17.Compare.RunningExampleConstants still fails, because it needs SCCP.
A2 (SCCP): -R ch17.Compare.RunningExampleConstants passes.
B1 (DVNT), then B2 (AWZ): -R ch17.Compare passes.
Oracle agreement: ctest --test-dir build/<preset> -R ch17.lab (the ★ labs' tests run in the same suite; ignore their failures if you skip them).
Measurement: fill in the table.

Measurement¶

Run build/<preset>/bin/ch17-compare --table --time labs/ch17-scalar/corpus/*.ll and fill in your numbers:

function	blocks	candidates	simple CP constants	SCCP constants	dead blocks (SCCP)	hash: redundant	partition: redundant
reference solution, `TOTAL`	48	114	7	12	5	15	26
yours

"Redundant" counts, per class, its size minus 1: the instructions a replacement pass could delete. Explain three rows with the lessons: running.ll:run (SCCP's unreachable if.then; the loop phis), loops.ll:twins (only the partition sees twin induction variables), and redundancy.ll:siblings (the hash table of one sibling is gone when the other is visited). Then compare the time columns: the partition costs a few times more than hashing, and both are microseconds.

Hints¶

Hint 1 — where to start

Write the SCCP solver once, with a flag that turns off edge tracking: Simple is SCCP where every block and edge is executable from the start. Lesson 17.1 §3 traces the running example step by step, and ./course drill sccp-trace --solution prints traces for random functions in the same notation. For Part B, write the label and the canonical operand list first, as one function each, and use them in both algorithms. Then the two algorithms cannot disagree about what "the same shape" means.

Hint 2 — the key idea

SCCP is optimistic twice. Values start at ⊥, and so do edges. A phi ignores operands on edges that are not (yet) executable, and that is what keeps x.0 at 1 in the running example.
DVNT is pessimistic at loop headers: a back-edge operand has no number when the phi is hashed, so it counts as itself.
AWZ is optimistic everywhere: all same-label values start together, and a class is split only when some operand position disagrees. The fixed point is the greatest congruence, so the tests can check it against the brute-force pair relation.

Hint 3 — a design sketch

SCCP. Use a DenseMap<Instruction*, Lattice>, a set of executable edges, a set of executable blocks, and two FIFO std::deques. Drain the edge worklist first.
DVNT. Use an explicit stack of (dominator-tree node, keys added) for the walk, a std::map from key vectors to leaders, and a DenseMap<Value*, number>.
AWZ. Give each candidate an integer id, store the operand ids per position, keep the classes as vectors, and keep a worklist of (class, position) splitters. For each splitter, collect the users at that position whose operand is in the class, and split every class they touch. Keep the larger part in place and push the smaller one (Hopcroft).

Bugs the tests catch most often: - treating undef as a constant; - evaluating instructions in non-executable blocks; - ordering phi operands by position instead of by incoming block (two phis in one block list their predecessors in different orders); - putting nsw in the label; - forgetting candidates in unreachable blocks (R6, R7).

Stretch goals ★¶

Add commutativity (sort the operands of commutative opcodes) to both VN algorithms, and measure what changes on the corpus.
Add an optimistic RPO value numbering (Algorithm 17.5.6) as a third VNAlgorithm, and check Theorem 17.5.14 (it equals AWZ) on the oracle's random functions.
Combine the two parts (Lesson 17.8): feed SCCP's executable edges into the partition (ignore phi operands on dead edges) and fold sub a, b / icmp eq a, b when a ≡ b. Then run it on mutual from Lesson 17.8 §3.