31. Optimization with Executable-Path Reasoning

Constant folding evaluates an operation with known arguments. Conditional constant propagation also reasons about which control-flow edges can execute. That difference lets it ignore an unreachable phi input while remaining conservative about unknown runtime values.

31.1 Three lattice states, not two

Each SSA value is initially UNDEFINED, a known constant, or OVERDEFINED. UNDEFINED means analysis has not established information yet; it does not mean an uninitialized source variable is legal. The frontend already rejected those. OVERDEFINED means the value cannot be represented as one constant by this analysis. Parameters begin OVERDEFINED.

The join rules are:

A value's state only moves upward. It can become a constant, then become OVERDEFINED when another path contributes a different value; it never becomes a constant again after that. Executable edges also only accumulate. These monotonic properties give a finite fixed-point computation.

31.2 Control flow participates in the proof

Start with the entry executable and no executable edges. Evaluate instructions in executable blocks. An unconditional jump enables its edge. A constant condition enables only its selected edge. An OVERDEFINED condition enables both edges. An UNDEFINED condition enables neither yet; later scans may establish more information and enable the correct edges.

For a phi, join operands only from executable incoming edges. Consider:

def f(n):
    flag = 1
    if flag:
        x = 5
    else:
        x = n
    return x * 2

Joining every syntactic incoming operand would combine 5 with unknown n and lose the constant. Executable-edge reasoning proves the else edge unavailable, so x is 5 and the result is 10. After rewriting, the dead arm is pruned and the unused phi disappears.

Now replace flag=1 with flag=n. Both branches become executable. The phi is OVERDEFINED; returning 10 unconditionally would be wrong. Tests need both cases to distinguish valid path reasoning from an optimizer that simply follows the first path it encounters.

31.3 Loops require revisiting optimistic facts

For x=0; while x<n: x+=1; return x, the header phi first sees the entry value 0. If the body can execute, its backedge eventually contributes 1, then the phi becomes OVERDEFINED. The analysis must revisit instructions and branch decisions affected by that change. Assuming the initially observed zero is permanent would miscompile every multi-iteration case.

This implementation scans to a fixed point for readability. A production sparse implementation would keep value-user and executable-block worklists, evaluating only affected nodes. The lattice, edge policy, and correctness conditions remain the same; the scan is not a claim about compile-time scalability.

31.4 Rewrite only after the analysis converges

Once facts stabilize, substitute constants into operands and pure results, convert constant branches to jumps, remove unreachable blocks, and repair phi edge maps. Keep trapping loads and stores in order. The result is reverified before any later pass consumes it.

An unreachable bounds error can disappear: that instruction cannot execute. A reachable load whose result is unused must remain: its failure is still observable. This distinction is precisely why “dead result” and “dead instruction” are different ideas.

"""Sparse conditional constant propagation and effect-preserving dead code removal.

The worklist is expressed as a fixed-point scan to keep the lattice mechanics visible.
Values move only UNDEFINED -> constant -> OVERDEFINED; executable edges only grow.
"""
from copy import deepcopy
from enum import Enum
from minicc.analysis import verify
from minicc.ir import EFFECTS, PURE, Terminator, alu, operands, prune


class State(Enum):
  UNDEFINED = 0
  OVERDEFINED = 1


def join(a, b):
  if a == State.UNDEFINED: return b
  if b == State.UNDEFINED or a == b: return a
  return State.OVERDEFINED


def sccp(original):
  if not original.ssa: raise ValueError("SCCP requires SSA")
  verify(original)
  function = deepcopy(original)
  values = {p.name: State.OVERDEFINED for p in function.parameters}
  executable, edges = {function.entry}, set()

  def value(arg): return arg if isinstance(arg, int) else values.get(arg, State.UNDEFINED)

  def update(dest, result):
    nonlocal changed
    combined = join(values.get(dest, State.UNDEFINED), result)
    if combined != values.get(dest, State.UNDEFINED):
      values[dest], changed = combined, True

  while True:
    changed = False
    for name, block in function.blocks.items():
      if name not in executable: continue
      for phi in block.phis:
        result = State.UNDEFINED
        for parent, arg in phi.incoming.items():
          if (parent, name) in edges: result = join(result, value(arg))
        update(phi.dest, result)
      for instruction in block.instructions:
        if instruction.dest is None: continue
        args = [value(arg) for arg in instruction.args]
        if instruction.op in EFFECTS or State.OVERDEFINED in args: result = State.OVERDEFINED
        elif State.UNDEFINED in args: result = State.UNDEFINED
        else: result = alu(instruction.op, args)
        update(instruction.dest, result)
      term = block.terminator
      if term.op == "jump": targets = term.targets
      elif term.op == "return": targets = ()
      else:
        condition = value(term.args[0])
        if condition == State.UNDEFINED: targets = ()
        elif condition == State.OVERDEFINED: targets = term.targets
        else: targets = (term.targets[0 if condition else 1],)
      for target in targets:
        if (name, target) not in edges: edges.add((name, target)); changed = True
        if target not in executable: executable.add(target); changed = True
    if not changed: break

  def replace(arg):
    candidate = value(arg)
    return candidate if isinstance(candidate, int) else arg

  for name, block in function.blocks.items():
    for phi in block.phis: phi.incoming = {p: replace(arg) for p, arg in phi.incoming.items()}
    for instruction in block.instructions:
      instruction.args = tuple(replace(arg) for arg in instruction.args)
      if instruction.op in PURE and isinstance(value(instruction.dest), int):
        instruction.op, instruction.args = "copy", (value(instruction.dest),)
    term = block.terminator
    term.args = tuple(replace(arg) for arg in term.args)
    if term.op == "branch" and isinstance(term.args[0], int):
      block.terminator = Terminator("jump", targets=(term.targets[0 if term.args[0] else 1],))
  prune(function)
  verify(function)
  return function


def eliminate_dead_code(original):
  if not original.ssa: raise ValueError("dead-code removal requires SSA")
  function = deepcopy(original)
  definitions = {}
  roots = set()
  for block in function.blocks.values():
    roots |= operands(block.terminator.args)
    for phi in block.phis: definitions[phi.dest] = operands(phi.incoming.values())
    for instruction in block.instructions:
      if instruction.dest is not None: definitions[instruction.dest] = operands(instruction.args)
      if instruction.op in EFFECTS: roots |= operands(instruction.args)
  live, pending = set(), list(roots)
  while pending:
    value = pending.pop()
    if value in live: continue
    live.add(value)
    pending.extend(definitions.get(value, ()))
  for block in function.blocks.values():
    block.phis = [phi for phi in block.phis if phi.dest in live]
    block.instructions = [i for i in block.instructions if i.op in EFFECTS or i.dest in live]
  verify(function)
  return function


def optimize(function): return eliminate_dead_code(sccp(function))

The transfer function deliberately declines identities that require more reasoning. For instance, an unknown integer multiplied by zero can be simplified in this language, but basic constant propagation leaves it unknown. Missing a valid optimization is different from making an invalid one. Add identities separately with their semantic domain and counterexample tests.

31.5 Dead-code elimination is backward reachability

Seed a live-value set with return and branch operands plus the operands needed by effectful instructions. Follow each live definition backward through its dependencies; a phi contributes its incoming values. Remove pure instructions and phis whose results are not reached. Preserve all reachable loads and stores, even when their scalar results are dead.

A cycle of phis and arithmetic with no connection to an observable root can be removed. Conversely, a value that computes an index for a store remains live even if no scalar return depends on it. Thinking of DCE as graph reachability handles both without relying on source-line intuition.

31.6 Experiments that can falsify the optimizer

The test suite compares pre-optimization and post-optimization execution against trusted source oracles, then checks separately specified cases that differ from Python:

• Wrapping arithmetic at signed boundaries and in large products.
• Unknown branch conditions, not only constant conditions.
• Loops with zero, one, and multiple iterations.
• Stores through aliased buffers followed by loads through the other name.
• An unused invalid load, which must still raise an error.
• A store before a trapping load, which remains visible after failure.
• A later store after that load, which must not execute.

Run these directly:

.venv/bin/python -m pytest tests/test_minicc.py -q

Extension: add copy propagation, algebraic simplification, global value numbering, and loop-invariant code motion one at a time. For load motion, first implement an effect/alias model capable of proving that intervening writes and traps permit the move. Do not reuse pure-expression legality rules for memory operations. For each new pass, verify the output and retain a minimized test that would fail if its key precondition were omitted.