constantPropagation

File

src/Optimization/ConstantPropagation.ts

Purpose

Applies Sparse Conditional Constant Propagation (SCCP) to fold compile-time evaluable expressions to constant values, propagate those constants through the program, and eliminate unreachable branches when conditionals have known constant values.

Input Invariants

• HIR must be in SSA form (runs after enterSSA)
• Redundant phi nodes should be eliminated (runs after eliminateRedundantPhi)
• Consistent identifiers must be ensured (assertConsistentIdentifiers)
• Terminal successors must exist (assertTerminalSuccessorsExist)

Output Guarantees

• Instructions with compile-time evaluable operands are replaced with Primitive constants
• ComputedLoad/ComputedStore with constant string/number properties are converted to PropertyLoad/PropertyStore
• LoadLocal and StoreLocal propagate known constant values
• IfTerminal with constant boolean test values are replaced with goto terminals
• Unreachable blocks are removed and the CFG is minimized
• Phi nodes with unreachable predecessor operands are pruned
• Nested functions (FunctionExpression, ObjectMethod) are recursively processed

Algorithm

The pass uses Sparse Conditional Constant Propagation (SCCP) with fixpoint iteration:

1. Data Structure: A Constants map (Map<IdentifierId, Constant>) tracks known constant values (either Primitive or LoadGlobal)

2. Single Pass per Iteration: Visits all blocks in order:

   • Evaluates phi nodes - if all operands have the same constant value, the phi result is constant
   • Evaluates instructions - replaces evaluable expressions with constants
   • Evaluates terminals - if an IfTerminal test is a constant, replaces it with a goto

3. Fixpoint Loop: If any terminals changed (branch elimination):

   • Recomputes block ordering (reversePostorderBlocks)
   • Removes unreachable code (removeUnreachableForUpdates, removeDeadDoWhileStatements, removeUnnecessaryTryCatch)
   • Renumbers instructions (markInstructionIds)
   • Updates predecessors (markPredecessors)
   • Prunes phi operands from unreachable predecessors
   • Eliminates newly-redundant phis (eliminateRedundantPhi)
   • Merges consecutive blocks (mergeConsecutiveBlocks)
   • Repeats until no more changes

4. Instruction Evaluation: Handles various instruction types:

   • Primitives/LoadGlobal: Directly constant
   • BinaryExpression: Folds arithmetic (+, -, *, /, %, **), bitwise (|, &, ^, <<, >>, >>>), and comparison (<, <=, >, >=, ==, ===, !=, !==) operators
   • UnaryExpression: Folds ! (boolean negation) and - (numeric negation)
   • PostfixUpdate/PrefixUpdate: Folds ++/-- on constant numbers
   • PropertyLoad: Folds .length on constant strings
   • TemplateLiteral: Folds template strings with constant interpolations
   • ComputedLoad/ComputedStore: Converts to property access when property is constant string/number

Key Data Structures

• Constant = Primitive | LoadGlobal - The lattice values (no top/bottom, absence means unknown)
• Constants = Map<IdentifierId, Constant> - Maps identifier IDs to their known constant values
• Uses HIR types: Instruction, Phi, Place, Primitive, LoadGlobal, InstructionValue

Edge Cases

• Last instruction of sequence blocks: Skipped to preserve evaluation order
• Phi nodes with back-edges: Single-pass analysis means loop back-edges won't have constant values propagated
• Template literals with Symbol: Not folded (would throw at runtime)
• Template literals with objects/arrays: Not folded (custom toString behavior)
• Division results: Computed at compile time (may produce NaN, Infinity, etc.)
• LoadGlobal in phis: Only propagated if all operands reference the same global name
• Nested functions: Constants from outer scope are propagated into nested function expressions

TODOs

• // TODO: handle more cases - The default case in evaluateInstruction has room for additional instruction types

Example

Input:

function Component() {
  let a = 1;

  let b;
  if (a === 1) {
    b = true;
  } else {
    b = false;
  }

  let c;
  if (b) {
    c = 'hello';
  } else {
    c = null;
  }

  return c;
}

After ConstantPropagation:

• a === 1 evaluates to true
• The if (a === 1) branch is eliminated, only consequent remains
• b is known to be true
• if (b) branch is eliminated, only consequent remains
• c is known to be 'hello'
• All intermediate blocks are merged

Output:

function Component() {
  return "hello";
}

The pass performs iterative simplification: first iteration determines a === 1 is true and eliminates that branch. The CFG is updated, phi for b is pruned to single operand making b = true. Second iteration uses b = true to eliminate the next branch. This continues until no more branches can be eliminated.