sscp-lattice-propagation
The SCCP algorithm works on SSA-form IR using an abstract-interpretation lattice: ⊤ (unknown) → Constant(c) → ⊥ (overdefined). Values monotonically descend the lattice as the solver encounters conflicting information.
Initialize all SSA values → ⊤, all blocks → not executable
Mark entry block executable, evaluate its instructions
Worklist loop (SSA edges + CFG edges):
When a block becomes executable via a CFG edge:
- Evaluate all phi nodes (meet of values from executable preds)
- Evaluate all non-phi instructions left-to-right
- For branches: add reachable successor edges to CFG worklist
When a value's lattice changes (SSA edge):
- Re-evaluate every instruction that uses the value
- If the result changes, add it to the SSA worklist
- If the instruction is a conditional branch and the condition
just became constant, update the CFG worklist
| Component | Implementation |
|---|---|
| Lattice | Three-level: Lat.top() → Lat.constant(v) → Lat.bottom() |
| Phi nodes | meet of incoming values from executable predecessors |
| Conditional branches | If condition is ⊤ or ⊥ → both successors reachable; if constant → only taken branch |
| Arithmetic | If both operands are constants → fold; if any is ⊥ → result is ⊥; otherwise ⊤ |
| Memory SSA | Per-location lattice, stores update the location, loads read from it |
| Optimizer pass | Dead blocks (not executable) removed, constant-folded instructions replaced with const, conditional branches replaced with unconditional br |
The critical fix that makes SCCP work correctly is phi evaluation using the meet operation over executable predecessors only:
def _eval_phi(self, ins: Instr) -> Lat:
result = Lat.top()
for val, pred_block in ins.phi_args:
if self.executable.get(pred_block, False):
v_lat = self.lat.get(val, Lat.top())
result = result.meet(v_lat)
return result
Without this, phi nodes would incorrectly mix values from dead code paths, producing ⊥ when they should produce a constant, or producing a constant when they should produce ⊤.
All 7 tests pass, demonstrating each aspect of SCCP: ### Test 1 – Simple Constant Propagation ``` Before: %a = 3, %b = 5, %c = add %a, %b, %d = mul %c, %a After: %c = const 8, %d = const 24 ✓ ``` ### Test 2 – Phi Folding + Dead Block Elimination ``` Before: br %c(1), left, right → left: x=10, right: x=20 After: br left → right block removed, phi → const 10 ✓ ``` ### Test 3 – Chained Phis ``` Before: left: x=10+20=30, right: (dead), phi y=[x_left, x_right] After: y = const 30, z = y + 10 = const 40 ✓ ``` ### Test 4 – Non-constant Conditional (both paths live) ``` cond = undef (⊤) → both branches executable y = phi(12, -2) = meet(12, -2) = ⊥ ✓ ``` ### Test 5 – Memory SSA (must-alias) ``` store mem, 42; br %c(1)→case1: store mem, 100 load mem → 100 (case2 with store 200 is dead) ✓ ``` ### Test 6 – False Branch Elimination ``` br %c(0), if_true, if_false → if_true block removed phi → const 2 ✓ ``` ### Test 7 – Must-alias via Same Location ``` store mem, 77; load mem → 77 ✓ ``` ### Edge Cases Tested 1. **Dead-block isolation**: Values in non-executable blocks remain ⊤ (never pollute live paths) 2. **Phi with mixed executable/non-executable preds**: Only executable predecessors contribute 3. **Chained constant folding**: Constants propagate through phis and arithmetic 4. **Non-constant conditions**: Both paths remain executable, phi produces ⊥ for conflicting constants 5. **Memory aliasing**: Same-name memory locations propagate stored values to subsequent loads 6. **Both true and false branch elimination**: Works symmetrically for `const 0` and `const 1` ---
{"model": "claude-haiku", "problem_class": "sscp-lattice-propagation", "result": "passed", "tests": 7}