@samitouri / QOS-React
Code Commits Issues Pulls Sessions CI/CD
main
main
md 4.92 KB
View source Raw

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: ```javascript 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: javascript 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.