| 1 | # constantPropagation |
| 2 | |
| 3 | ## File |
| 4 | `src/Optimization/ConstantPropagation.ts` |
| 5 | |
| 6 | ## Purpose |
| 7 | 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. |
| 8 | |
| 9 | ## Input Invariants |
| 10 | - HIR must be in SSA form (runs after `enterSSA`) |
| 11 | - Redundant phi nodes should be eliminated (runs after `eliminateRedundantPhi`) |
| 12 | - Consistent identifiers must be ensured (`assertConsistentIdentifiers`) |
| 13 | - Terminal successors must exist (`assertTerminalSuccessorsExist`) |
| 14 | |
| 15 | ## Output Guarantees |
| 16 | - Instructions with compile-time evaluable operands are replaced with `Primitive` constants |
| 17 | - `ComputedLoad`/`ComputedStore` with constant string/number properties are converted to `PropertyLoad`/`PropertyStore` |
| 18 | - `LoadLocal` and `StoreLocal` propagate known constant values |
| 19 | - `IfTerminal` with constant boolean test values are replaced with `goto` terminals |
| 20 | - Unreachable blocks are removed and the CFG is minimized |
| 21 | - Phi nodes with unreachable predecessor operands are pruned |
| 22 | - Nested functions (`FunctionExpression`, `ObjectMethod`) are recursively processed |
| 23 | |
| 24 | ## Algorithm |
| 25 | The pass uses Sparse Conditional Constant Propagation (SCCP) with fixpoint iteration: |
| 26 | |
| 27 | 1. **Data Structure**: A `Constants` map (`Map<IdentifierId, Constant>`) tracks known constant values (either `Primitive` or `LoadGlobal`) |
| 28 | |
| 29 | 2. **Single Pass per Iteration**: Visits all blocks in order: |
| 30 | - Evaluates phi nodes - if all operands have the same constant value, the phi result is constant |
| 31 | - Evaluates instructions - replaces evaluable expressions with constants |
| 32 | - Evaluates terminals - if an `IfTerminal` test is a constant, replaces it with a `goto` |
| 33 | |
| 34 | 3. **Fixpoint Loop**: If any terminals changed (branch elimination): |
| 35 | - Recomputes block ordering (`reversePostorderBlocks`) |
| 36 | - Removes unreachable code (`removeUnreachableForUpdates`, `removeDeadDoWhileStatements`, `removeUnnecessaryTryCatch`) |
| 37 | - Renumbers instructions (`markInstructionIds`) |
| 38 | - Updates predecessors (`markPredecessors`) |
| 39 | - Prunes phi operands from unreachable predecessors |
| 40 | - Eliminates newly-redundant phis (`eliminateRedundantPhi`) |
| 41 | - Merges consecutive blocks (`mergeConsecutiveBlocks`) |
| 42 | - Repeats until no more changes |
| 43 | |
| 44 | 4. **Instruction Evaluation**: Handles various instruction types: |
| 45 | - **Primitives/LoadGlobal**: Directly constant |
| 46 | - **BinaryExpression**: Folds arithmetic (`+`, `-`, `*`, `/`, `%`, `**`), bitwise (`|`, `&`, `^`, `<<`, `>>`, `>>>`), and comparison (`<`, `<=`, `>`, `>=`, `==`, `===`, `!=`, `!==`) operators |
| 47 | - **UnaryExpression**: Folds `!` (boolean negation) and `-` (numeric negation) |
| 48 | - **PostfixUpdate/PrefixUpdate**: Folds `++`/`--` on constant numbers |
| 49 | - **PropertyLoad**: Folds `.length` on constant strings |
| 50 | - **TemplateLiteral**: Folds template strings with constant interpolations |
| 51 | - **ComputedLoad/ComputedStore**: Converts to property access when property is constant string/number |
| 52 | |
| 53 | ## Key Data Structures |
| 54 | - `Constant = Primitive | LoadGlobal` - The lattice values (no top/bottom, absence means unknown) |
| 55 | - `Constants = Map<IdentifierId, Constant>` - Maps identifier IDs to their known constant values |
| 56 | - Uses HIR types: `Instruction`, `Phi`, `Place`, `Primitive`, `LoadGlobal`, `InstructionValue` |
| 57 | |
| 58 | ## Edge Cases |
| 59 | - **Last instruction of sequence blocks**: Skipped to preserve evaluation order |
| 60 | - **Phi nodes with back-edges**: Single-pass analysis means loop back-edges won't have constant values propagated |
| 61 | - **Template literals with Symbol**: Not folded (would throw at runtime) |
| 62 | - **Template literals with objects/arrays**: Not folded (custom toString behavior) |
| 63 | - **Division results**: Computed at compile time (may produce `NaN`, `Infinity`, etc.) |
| 64 | - **LoadGlobal in phis**: Only propagated if all operands reference the same global name |
| 65 | - **Nested functions**: Constants from outer scope are propagated into nested function expressions |
| 66 | |
| 67 | ## TODOs |
| 68 | - `// TODO: handle more cases` - The default case in `evaluateInstruction` has room for additional instruction types |
| 69 | |
| 70 | ## Example |
| 71 | |
| 72 | **Input:** |
| 73 | ```javascript |
| 74 | function Component() { |
| 75 | let a = 1; |
| 76 | |
| 77 | let b; |
| 78 | if (a === 1) { |
| 79 | b = true; |
| 80 | } else { |
| 81 | b = false; |
| 82 | } |
| 83 | |
| 84 | let c; |
| 85 | if (b) { |
| 86 | c = 'hello'; |
| 87 | } else { |
| 88 | c = null; |
| 89 | } |
| 90 | |
| 91 | return c; |
| 92 | } |
| 93 | ``` |
| 94 | |
| 95 | **After ConstantPropagation:** |
| 96 | - `a === 1` evaluates to `true` |
| 97 | - The `if (a === 1)` branch is eliminated, only consequent remains |
| 98 | - `b` is known to be `true` |
| 99 | - `if (b)` branch is eliminated, only consequent remains |
| 100 | - `c` is known to be `'hello'` |
| 101 | - All intermediate blocks are merged |
| 102 | |
| 103 | **Output:** |
| 104 | ```javascript |
| 105 | function Component() { |
| 106 | return "hello"; |
| 107 | } |
| 108 | ``` |
| 109 | |
| 110 | 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. |