@samitouri / QOS-React-1
Code Commits Issues Pulls Sessions CI/CD
main
main
md 182 lines 7.28 KB
Rendered Raw
1 # enterSSA
2
3 ## File
4 `src/SSA/EnterSSA.ts`
5
6 ## Purpose
7 Converts the HIR from a non-SSA form (where variables can be reassigned) into Static Single Assignment (SSA) form, where each variable is defined exactly once and phi nodes are inserted at control flow join points to merge values from different paths.
8
9 ## Input Invariants
10 - The HIR must have blocks in reverse postorder (predecessors visited before successors, except for back-edges)
11 - Block predecessor information (`block.preds`) must be populated correctly
12 - The function's `context` array must be empty for the root function (outer function declarations)
13 - Identifiers may be reused across multiple definitions/assignments (non-SSA form)
14
15 ## Output Guarantees
16 - Each identifier has a unique `IdentifierId` - no identifier is defined more than once
17 - All operand references use the SSA-renamed identifiers
18 - Phi nodes are inserted at join points where values from different control flow paths converge
19 - Function parameters are SSA-renamed
20 - Nested functions (FunctionExpression, ObjectMethod) are recursively converted to SSA form
21 - Context variables (captured from outer scopes) are handled specially and not redefined
22
23 ## Algorithm
24 The pass uses the Braun et al. algorithm ("Simple and Efficient Construction of Static Single Assignment Form") with adaptations for handling loops and nested functions.
25
26 ### Key Steps:
27 1. **Block Traversal**: Iterate through blocks in order (assumed reverse postorder from previous passes)
28 2. **Definition Tracking**: Maintain a per-block `defs` map from original identifiers to their SSA-renamed versions
29 3. **Renaming**:
30 - When a value is **defined** (lvalue), create a new SSA identifier with fresh `IdentifierId`
31 - When a value is **used** (operand), look up the current SSA identifier via `getIdAt`
32 4. **Phi Node Insertion**: When looking up an identifier at a block with multiple predecessors:
33 - If all predecessors have been visited, create a phi node collecting values from each predecessor
34 - If some predecessors are unvisited (back-edge/loop), create an "incomplete phi" that will be fixed later
35 5. **Incomplete Phi Resolution**: When all predecessors of a block are finally visited, fix any incomplete phi nodes by populating their operands
36 6. **Nested Function Handling**: Recursively apply SSA transformation to nested functions, temporarily adding a fake predecessor edge to enable identifier lookup from the enclosing scope
37
38 ### Phi Node Placement Logic (`getIdAt`):
39 - If the identifier is defined locally in the current block, return it
40 - If at entry block with no predecessors and not found, mark as unknown (global)
41 - If some predecessors are unvisited (loop), create incomplete phi
42 - If exactly one predecessor, recursively look up in that predecessor
43 - If multiple predecessors, create phi node with operands from all predecessors
44
45 ## Key Data Structures
46 - **SSABuilder**: Main class managing the transformation
47 - `#states: Map<BasicBlock, State>` - Per-block state (defs map and incomplete phis)
48 - `unsealedPreds: Map<BasicBlock, number>` - Count of unvisited predecessors per block
49 - `#unknown: Set<Identifier>` - Identifiers assumed to be globals
50 - `#context: Set<Identifier>` - Context variables that should not be redefined
51 - **State**: Per-block state containing:
52 - `defs: Map<Identifier, Identifier>` - Maps original identifiers to SSA-renamed versions
53 - `incompletePhis: Array<IncompletePhi>` - Phi nodes waiting for predecessor values
54 - **IncompletePhi**: Tracks a phi node created before all predecessors were visited
55 - `oldPlace: Place` - Original place being phi'd
56 - `newPlace: Place` - SSA-renamed phi result place
57 - **Phi**: The actual phi node in the HIR
58 - `place: Place` - The result of the phi
59 - `operands: Map<BlockId, Place>` - Maps predecessor block to the place providing the value
60
61 ## Edge Cases
62 - **Loops (back-edges)**: When a variable is used in a loop header before the loop body assigns it, an incomplete phi is created and later fixed when the loop body block is visited
63 - **Globals**: If an identifier is used but never defined (reaching the entry block without a definition), it's assumed to be a global and not renamed
64 - **Context variables**: Variables captured from an outer function scope are tracked specially and not redefined when reassigned
65 - **Nested functions**: Function expressions and object methods are processed recursively with a temporary predecessor edge linking them to the enclosing block
66
67 ## TODOs
68 - `[hoisting] EnterSSA: Expected identifier to be defined before being used` - Handles cases where hoisting causes an identifier to be used before definition (throws a Todo error for graceful bailout)
69
70 ## Example
71
72 ### Input (simple reassignment with control flow):
73 ```javascript
74 function foo() {
75 let y = 2;
76 if (y > 1) {
77 y = 1;
78 } else {
79 y = 2;
80 }
81 let x = y;
82 }
83 ```
84
85 ### Before SSA (HIR):
86 ```
87 bb0 (block):
88 [1] $0 = 2
89 [2] $2 = StoreLocal Let y$1 = $0
90 [3] $7 = LoadLocal y$1
91 [4] $8 = 1
92 [5] $9 = Binary $7 > $8
93 [6] If ($9) then:bb2 else:bb3 fallthrough=bb1
94
95 bb2 (block):
96 predecessor blocks: bb0
97 [7] $3 = 1
98 [8] $4 = StoreLocal Reassign y$1 = $3 // Same y$1 reassigned
99 [9] Goto bb1
100
101 bb3 (block):
102 predecessor blocks: bb0
103 [10] $5 = 2
104 [11] $6 = StoreLocal Reassign y$1 = $5 // Same y$1 reassigned
105 [12] Goto bb1
106
107 bb1 (block):
108 predecessor blocks: bb2 bb3
109 [13] $10 = LoadLocal y$1 // Which y$1?
110 [14] $12 = StoreLocal Let x$11 = $10
111 ```
112
113 ### After SSA:
114 ```
115 bb0 (block):
116 [1] $15 = 2
117 [2] $17 = StoreLocal Let y$16 = $15 // y$16: initial definition
118 [3] $18 = LoadLocal y$16
119 [4] $19 = 1
120 [5] $20 = Binary $18 > $19
121 [6] If ($20) then:bb2 else:bb3 fallthrough=bb1
122
123 bb2 (block):
124 predecessor blocks: bb0
125 [7] $21 = 1
126 [8] $23 = StoreLocal Reassign y$22 = $21 // y$22: new SSA name
127 [9] Goto bb1
128
129 bb3 (block):
130 predecessor blocks: bb0
131 [10] $24 = 2
132 [11] $26 = StoreLocal Reassign y$25 = $24 // y$25: new SSA name
133 [12] Goto bb1
134
135 bb1 (block):
136 predecessor blocks: bb2 bb3
137 y$27: phi(bb2: y$22, bb3: y$25) // PHI NODE: merges y$22 and y$25
138 [13] $28 = LoadLocal y$27 // Uses phi result
139 [14] $30 = StoreLocal Let x$29 = $28
140 ```
141
142 ### Loop Example (while loop with back-edge):
143 ```javascript
144 function foo() {
145 let x = 1;
146 while (x < 10) {
147 x = x + 1;
148 }
149 return x;
150 }
151 ```
152
153 ### After SSA:
154 ```
155 bb0 (block):
156 [1] $13 = 1
157 [2] $15 = StoreLocal Let x$14 = $13 // x$14: initial definition
158 [3] While test=bb1 loop=bb3 fallthrough=bb2
159
160 bb1 (loop):
161 predecessor blocks: bb0 bb3
162 x$16: phi(bb0: x$14, bb3: x$23) // PHI merges initial and loop-updated values
163 [4] $17 = LoadLocal x$16
164 [5] $18 = 10
165 [6] $19 = Binary $17 < $18
166 [7] Branch ($19) then:bb3 else:bb2
167
168 bb3 (block):
169 predecessor blocks: bb1
170 [8] $20 = LoadLocal x$16 // Uses phi result
171 [9] $21 = 1
172 [10] $22 = Binary $20 + $21
173 [11] $24 = StoreLocal Reassign x$23 = $22 // x$23: new SSA name in loop body
174 [12] Goto(Continue) bb1
175
176 bb2 (block):
177 predecessor blocks: bb1
178 [13] $25 = LoadLocal x$16 // Uses phi result
179 [14] Return Explicit $25
180 ```
181
182 The phi node at `bb1` (the loop header) is initially created as an "incomplete phi" when first visited because `bb3` (the loop body) hasn't been visited yet. Once `bb3` is processed and its terminal is handled, the incomplete phi is fixed by calling `fixIncompletePhis` to populate the operand from `bb3`.