| 1 | # deadCodeElimination |
| 2 | |
| 3 | ## File |
| 4 | `src/Optimization/DeadCodeElimination.ts` |
| 5 | |
| 6 | ## Purpose |
| 7 | Eliminates instructions whose values are unused, reducing generated code size. The pass performs mark-and-sweep analysis to identify and remove dead code while preserving side effects and program semantics. |
| 8 | |
| 9 | ## Input Invariants |
| 10 | - Must run after `InferMutationAliasingEffects` because "dead" code may still affect effect inference |
| 11 | - HIR is in SSA form with phi nodes |
| 12 | - Unreachable blocks are already pruned during HIR construction |
| 13 | |
| 14 | ## Output Guarantees |
| 15 | - All instructions with unused lvalues (that are safe to prune) are removed |
| 16 | - Unused phi nodes are deleted |
| 17 | - Unused context variables are removed from `fn.context` |
| 18 | - Destructuring patterns are rewritten to remove unused bindings |
| 19 | - `StoreLocal` instructions with unused initializers are converted to `DeclareLocal` |
| 20 | |
| 21 | ## Algorithm |
| 22 | Two-phase mark-and-sweep with fixed-point iteration for loops: |
| 23 | |
| 24 | **Phase 1: Mark (findReferencedIdentifiers)** |
| 25 | 1. Detect if function has back-edges (loops) |
| 26 | 2. Iterate blocks in reverse postorder (successors before predecessors) to visit usages before declarations |
| 27 | 3. For each block: |
| 28 | - Mark all terminal operands as referenced |
| 29 | - Process instructions in reverse order: |
| 30 | - If lvalue is used OR instruction is not pruneable, mark the lvalue and all operands as referenced |
| 31 | - Special case for `StoreLocal`: only mark initializer if the SSA lvalue is actually read |
| 32 | - Mark phi operands if the phi result is used |
| 33 | 4. If loops exist and new identifiers were marked, repeat until fixed point |
| 34 | |
| 35 | **Phase 2: Sweep** |
| 36 | 1. Remove unused phi nodes from each block |
| 37 | 2. Remove instructions with unused lvalues using `retainWhere` |
| 38 | 3. Rewrite retained instructions: |
| 39 | - **Array destructuring**: Replace unused elements with holes, truncate trailing holes |
| 40 | - **Object destructuring**: Remove unused properties (only if rest element is unused or absent) |
| 41 | - **StoreLocal**: Convert to `DeclareLocal` if initializer value is never read |
| 42 | 4. Remove unused context variables |
| 43 | |
| 44 | ## Key Data Structures |
| 45 | - **State class**: Tracks referenced identifiers |
| 46 | - `identifiers: Set<IdentifierId>` - SSA-specific usages |
| 47 | - `named: Set<string>` - Named variable usages (any version) |
| 48 | - `isIdOrNameUsed()` - Checks if identifier or any version of named variable is used |
| 49 | - `isIdUsed()` - Checks if specific SSA id is used |
| 50 | - **hasBackEdge/findBlocksWithBackEdges**: Detect loops requiring fixed-point iteration |
| 51 | |
| 52 | ## Edge Cases |
| 53 | - **Preserved even if unused:** |
| 54 | - `debugger` statements (to not break debugging workflows) |
| 55 | - Call expressions and method calls (may have side effects) |
| 56 | - Await expressions |
| 57 | - Store operations (ComputedStore, PropertyStore, StoreGlobal) |
| 58 | - Delete operations (ComputedDelete, PropertyDelete) |
| 59 | - Iterator operations (GetIterator, IteratorNext, NextPropertyOf) |
| 60 | - Context operations (LoadContext, DeclareContext, StoreContext) |
| 61 | - Memoization markers (StartMemoize, FinishMemoize) |
| 62 | |
| 63 | - **SSR mode special case:** |
| 64 | - In SSR mode, unused `useState`, `useReducer`, and `useRef` hooks can be removed |
| 65 | |
| 66 | - **Object destructuring with rest:** |
| 67 | - Cannot remove unused properties if rest element is used (would change rest's value) |
| 68 | |
| 69 | - **Block value instructions:** |
| 70 | - Last instruction of value blocks (not 'block' kind) is never pruned as it's the block's value |
| 71 | |
| 72 | ## TODOs |
| 73 | - "TODO: we could be more precise and make this conditional on whether any arguments are actually modified" (for mutating instructions) |
| 74 | |
| 75 | ## Example |
| 76 | |
| 77 | **Input:** |
| 78 | ```javascript |
| 79 | function Component(props) { |
| 80 | const _ = 42; |
| 81 | return props.value; |
| 82 | } |
| 83 | ``` |
| 84 | |
| 85 | **After DeadCodeElimination:** |
| 86 | The `const _ = 42` assignment is removed since `_` is never used: |
| 87 | ```javascript |
| 88 | function Component(props) { |
| 89 | return props.value; |
| 90 | } |
| 91 | ``` |
| 92 | |
| 93 | **Array destructuring example:** |
| 94 | |
| 95 | Input: |
| 96 | ```javascript |
| 97 | function foo(props) { |
| 98 | const [x, unused, y] = props.a; |
| 99 | return x + y; |
| 100 | } |
| 101 | ``` |
| 102 | |
| 103 | Output (middle element becomes a hole): |
| 104 | ```javascript |
| 105 | function foo(props) { |
| 106 | const [x, , y] = props.a; |
| 107 | return x + y; |
| 108 | } |
| 109 | ``` |