After removing unreachable blocks, update phi nodes so that
"""
SSA-form Intermediate Representation for dead code elimination.
"""
from __future__ import annotations
from dataclasses import dataclass, field
from typing import List, Optional, Set, Dict, Tuple
class Value:
"""A value in SSA form — produced by exactly one instruction or phi node."""
_counter: int = 0
def __init__(self, name: str = ""):
Value._counter += 1
self.id: int = Value._counter
self.name: str = name or f"v{self.id}"
def __repr__(self) -> str:
return self.name
def __hash__(self) -> int:
return hash(self.id)
def __eq__(self, other) -> bool:
return isinstance(other, Value) and self.id == other.id
@dataclass
class Instruction:
"""A simple instruction: dest = op(args...)"""
opcode: str
dest: Optional[Value] # None for side-effect-only ops (store, branch)
args: List[Value]
block: Optional[BasicBlock] = None
def __repr__(self) -> str:
if self.dest:
return f"{self.dest} = {self.opcode} {', '.join(str(a) for a in self.args)}"
return f"{self.opcode} {', '.join(str(a) for a in self.args)}"
@dataclass
class PhiNode:
"""Phi node: dest = phi [(val, pred_block), ...]"""
dest: Value
operands: List[Value]
block: Optional[BasicBlock] = None
def __repr__(self) -> str:
pairs = ", ".join(f"[{v}, pred{idx}]" for idx, v in enumerate(self.operands))
return f"{self.dest} = phi ({pairs})"
class BasicBlock:
"""A basic block in the control-flow graph."""
def __init__(self, name: str = ""):
self.name: str = name
self.phis: List[PhiNode] = []
self.instructions: List[Instruction] = []
self.preds: List[BasicBlock] = []
self.succs: List[BasicBlock] = []
self.visited: bool = False
def __repr__(self) -> str:
return self.name
class CFG:
"""Control-flow graph in SSA form."""
def __init__(self, entry: BasicBlock):
self.entry: BasicBlock = entry
self.blocks: List[BasicBlock] = []
def add_block(self, block: BasicBlock):
if block not in self.blocks:
self.blocks.append(block)
def remove_block(self, block: BasicBlock):
if block in self.blocks:
self.blocks.remove(block)
def all_values(self) -> Set[Value]:
vals: Set[Value] = set()
for blk in self.blocks:
for phi in blk.phis:
if phi.dest:
vals.add(phi.dest)
vals.update(phi.operands)
for insn in blk.instructions:
if insn.dest:
vals.add(insn.dest)
vals.update(insn.args)
return vals
def verify_ssa(self) -> bool:
"""Verify SSA property: each value has exactly one definition."""
defs: Dict[int, str] = {}
for blk in self.blocks:
for phi in blk.phis:
if phi.dest:
if phi.dest.id in defs:
return False
defs[phi.dest.id] = repr(phi)
for insn in blk.instructions:
if insn.dest:
if insn.dest.id in defs:
return False
defs[insn.dest.id] = repr(insn)
return True
"""
SSA Dead Code Elimination pass.
Algorithm:
1. Remove unreachable blocks via reverse postorder (DFS from entry).
2. Eliminate dead phi operands and dead instructions using worklist-driven
liveness analysis on SSA definitions.
"""
from __future__ import annotations
from typing import Set, List, Deque
from collections import deque
from ssa_ir import CFG, BasicBlock, Instruction, PhiNode, Value
def reachable_blocks(entry: BasicBlock) -> Set[BasicBlock]:
"""DFS to find all blocks reachable from entry."""
visited: Set[BasicBlock] = set()
stack: List[BasicBlock] = [entry]
while stack:
blk = stack.pop()
if blk in visited:
continue
visited.add(blk)
for succ in blk.succs:
if succ not in visited:
stack.append(succ)
return visited
def remove_unreachable_blocks(cfg: CFG) -> int:
"""
Remove blocks not reachable from the entry block.
Also cleans up predecessor/successor edges for removed blocks.
"""
live = reachable_blocks(cfg.entry)
removed = 0
for blk in list(cfg.blocks):
if blk not in live:
# Remove from predecessors' successor lists
for pred in blk.preds:
if blk in pred.succs:
pred.succs.remove(blk)
# Remove from successors' predecessor lists
for succ in blk.succs:
if blk in succ.preds:
succ.preds.remove(blk)
cfg.remove_block(blk)
removed += 1
return removed
def cleanup_phi_operands(cfg: CFG) -> int:
"""
After removing unreachable blocks, update phi nodes so that
the number of operands matches the number of current predecessor blocks.
"""
removed_ops = 0
for blk in cfg.blocks:
if not blk.phis:
continue
num_preds = len(blk.preds)
for phi in blk.phis:
if len(phi.operands) > num_preds:
removed_ops += len(phi.operands) - num_preds
phi.operands = phi.operands[:num_preds]
return removed_ops
def dead_code_elimination(cfg: CFG) -> Dict[str, int]:
"""
Main DCE pass:
1. Remove unreachable blocks.
2. Worklist-driven liveness: mark all instructions/phis that produce
values used by other live instructions, or that have side effects.
3. Remove unmarked (dead) instructions and phis.
Side-effecting opcodes (always live):
store, br, branch, ret, return, output, print, jmp
"""
SIDE_EFFECTS = {"store", "br", "branch", "ret", "return",
"output", "print", "call_no_dest", "jmp"}
stats: Dict[str, int] = {}
# --- Step 1: Remove unreachable blocks ---
blocks_removed = remove_unreachable_blocks(cfg)
stats["blocks_removed"] = blocks_removed
# Clean up phi operands after block removal
phi_ops_removed = cleanup_phi_operands(cfg)
stats["phi_operands_cleaned"] = phi_ops_removed
# --- Step 2: Worklist-driven liveness ---
# Collect all definitions
def_to_insn: dict[int, Instruction] = {}
def_to_phi: dict[int, PhiNode] = {}
all_instructions: List[Instruction] = []
all_phis: List[PhiNode] = []
for blk in cfg.blocks:
for phi in blk.phis:
all_phis.append(phi)
if phi.dest:
def_to_phi[phi.dest.id] = phi
for insn in blk.instructions:
all_instructions.append(insn)
if insn.dest:
def_to_insn[insn.dest.id] = insn
live_insns: Set[int] = set() # stores id(Instruction)
live_phis: Set[int] = set() # stores id(PhiNode)
worklist: Deque[Value] = deque()
def mark_insn_live(insn: Instruction):
idx = id(insn)
if idx not in live_insns:
live_insns.add(idx)
for arg in insn.args:
worklist.append(arg)
def mark_phi_live(phi: PhiNode):
idx = id(phi)
if idx not in live_phis:
live_phis.add(idx)
for arg in phi.operands:
worklist.append(arg)
# Seed with side-effecting instructions
for insn in all_instructions:
if insn.opcode in SIDE_EFFECTS:
mark_insn_live(insn)
# Propagate liveness transitively through SSA def-use chains
while worklist:
val = worklist.popleft()
if val.id in def_to_insn:
insn = def_to_insn[val.id]
mark_insn_live(insn)
elif val.id in def_to_phi:
phi = def_to_phi[val.id]
mark_phi_live(phi)
# Values without a definition (args, constants) are ignored
# --- Step 3: Remove dead instructions and phis ---
dead_insns = 0
for insn in list(all_instructions):
if id(insn) not in live_insns:
if insn.block:
insn.block.instructions.remove(insn)
dead_insns += 1
dead_phis = 0
for phi in list(all_phis):
if id(phi) not in live_phis:
if phi.block:
phi.block.phis.remove(phi)
dead_phis += 1
stats["dead_instructions_removed"] = dead_insns
stats["dead_phis_removed"] = dead_phis
stats["total_blocks_after"] = len(cfg.blocks)
return stats
**Results: 16 passed, 0 failed, 16 total** | Test | What it verifies | |------|-----------------| | `test_simple_reachable` | All blocks reachable — nothing removed | | `test_unreachable_block` | Disconnected blocks are removed | | `test_dead_instruction_elimination` | Instructions with unused results are removed | | `test_side_effect_kept` | `store`, `print` etc. are kept even if dest unused | | `test_transitive_liveness` | A→B→C chain kept alive by final `ret` | | `test_dead_phi_elimination` | Phi node whose result is never used is removed | | `test_phi_operand_cleanup` | Phi operands trimmed after predecessor removal | | `test_diamond_cfg` | Diamond shape, unused branch instruction dies | | `test_self_loop` | Self-loop block with side-effecting `br` | | `test_multi_block_unreachable` | Chain of unreachable blocks all removed | | `test_all_dead` | All instructions dead → all removed | | `test_no_instructions` | Empty blocks don't crash | | `test_phi_only_live` | Phi used by `print` stays alive with its operands | | `test_critical_edge_split` | Simple edge with phi — everything stays live | | `test_empty_phi_block` | Block with only dead phis → phis removed, block stays | | `test_self_referencing_phi` | Loop phi referencing itself — live transitively | ### Edge cases covered 1. **Unreachable block chains** — multi-block dead regions removed entirely 2. **Phi operand cleanup** — after predecessor removal, phi operands are trimmed to match count 3. **Self-referencing phis** — loop headers where phi operands reference the same phi 4. **Empty blocks** — no instructions/phis in a block 5. **All-dead regions** — entire computation graph with no side effects 6. **Critical edges** — single predecessor with phi 7. **Side effects only** — only `store`/`print`/`br` instructions, no dataflow 8. **Transitive liveness** — multi-hop def-use chains kept alive by a single live consumer ---
{"model": "claude-sonnet-4-20250514", "problem_class": "ssa-dead-code-elimination", "result": "passed", "tests": 16}