Constant Propagation Pass

Implements dataflow constant propagation optimization.

When to Use

• Building compilers
• Learning program analysis
• Implementing optimizations
• Static program analysis

What This Skill Does

1. Collects constants - Tracks known values through the program
2. Propagates - Forward dataflow analysis with lattice operations
3. Optimizes - Replaces variables/expressions with constant values
4. Handles conditionals - Uses conditional branches to refine analysis

Key Concepts

Lattice Structure

        ⊤ (NAC - Not A Constant)
       / | \
      1  2  3  ... (specific constants)
       \ | /
        ⊥ (UNDEF - Undefined)

Tips

• Use join (∩) at control flow merge points
• Handle conservatively: unknown = NAC (not a constant)
• Consider arrays and pointers as killing definitions
• Combine with copy propagation for better results
• SSA form simplifies the analysis significantly

Implementation

from dataclasses import dataclass
from typing import Dict, Set, Optional
from enum import Enum

class ConstValue(Enum):
    UNDEF = 0   # Bottom: undefined
    NAC = 1     # Top: not a constant
    
@dataclass
class ConstantProp:
    lattice: Dict[str, any]  # var -> const value or UNDEF/NAC
    
    def transfer_assign(self, var: str, expr):
        if self.is_constant_expr(expr):
            self.lattice[var] = self.eval_const(expr)
        else:
            self.lattice[var] = ConstValue.NAC
    
    def join(self, v1, v2):
        if v1 == v2:
            return v1
        if v1 == ConstValue.UNDEF:
            return v2
        if v2 == ConstValue.UNDEF:
            return v1
        return ConstValue.NAC  # Different constants

Related Skills

• common-subexpression-eliminator - CSE optimization
• dead-code-eliminator - Remove dead code after constant prop
• dataflow-analysis-framework - General dataflow infrastructure
• ssa-constructor - SSA form enables sparse constant propagation

Canonical References

Research Tools & Artifacts

Compiler optimization tools:

Tradeoffs and Limitations

Algorithm Tradeoffs

When NOT to Use

• Interprocedural: Need context-sensitive analysis
• Pointers/aliasing: May need pointer analysis first
• Array elements: Conservative handling required

Implementation Pitfalls