@samitouri / QOS-React-2
Code Commits Issues Pulls Sessions CI/CD
main
main
md 161 lines 6.01 KB
Rendered Raw
1 # buildReactiveScopeTerminalsHIR
2
3 ## File
4 `src/HIR/BuildReactiveScopeTerminalsHIR.ts`
5
6 ## Purpose
7 This pass transforms the HIR by inserting `ReactiveScopeTerminal` nodes to explicitly demarcate the boundaries of reactive scopes within the control flow graph. It converts the implicit scope ranges (stored on identifiers as `identifier.scope.range`) into explicit control flow structure by:
8
9 1. Inserting a `scope` terminal at the **start** of each reactive scope
10 2. Inserting a `goto` terminal at the **end** of each reactive scope
11 3. Creating fallthrough blocks to properly connect the scopes to the rest of the CFG
12
13 This transformation makes scope boundaries first-class elements in the CFG, which is essential for later passes that generate the memoization code (the `if ($[n] !== dep)` checks).
14
15 ## Input Invariants
16 - **Properly nested scopes and blocks**: The pass assumes `assertValidBlockNesting` has passed, meaning all program blocks and reactive scopes form a proper tree hierarchy
17 - **Aligned scope ranges**: Reactive scope ranges have been correctly aligned and merged by previous passes
18 - **Valid instruction IDs**: All instructions have sequential IDs that define the scope boundaries
19 - **Scopes attached to identifiers**: Reactive scopes are found by traversing all `Place` operands and collecting unique non-empty scopes
20
21 ## Output Guarantees
22 - **Explicit scope terminals**: Each reactive scope is represented in the CFG as a `ReactiveScopeTerminal` with:
23 - `block` - The BlockId containing the scope's instructions
24 - `fallthrough` - The BlockId that executes after the scope
25 - **Proper block structure**: Original blocks are split at scope boundaries
26 - **Restored HIR invariants**: The pass restores RPO ordering, predecessor sets, instruction IDs, and scope/identifier ranges
27 - **Updated phi nodes**: Phi operands are repointed when their source blocks are split
28
29 ## Algorithm
30
31 ### Step 1: Collect Scope Rewrites
32 ```
33 for each reactive scope (in range pre-order):
34 push StartScope rewrite at scope.range.start
35 push EndScope rewrite at scope.range.end
36 ```
37 The `recursivelyTraverseItems` helper traverses scopes in pre-order (outer scopes before inner scopes).
38
39 ### Step 2: Apply Rewrites by Splitting Blocks
40 ```
41 reverse queuedRewrites (to pop in ascending instruction order)
42 for each block:
43 for each instruction (or terminal):
44 while there are rewrites <= current instruction ID:
45 split block at current index
46 insert scope terminal (for start) or goto terminal (for end)
47 emit final block segment with original terminal
48 ```
49
50 ### Step 3: Repoint Phi Nodes
51 When a block is split, its final segment gets a new BlockId. Phi operands that referenced the original block are updated to reference the new final block.
52
53 ### Step 4: Restore HIR Invariants
54 - Recompute RPO (reverse post-order) block traversal
55 - Recalculate predecessor sets
56 - Renumber instruction IDs
57 - Fix scope and identifier ranges to match new instruction IDs
58
59 ## Key Data Structures
60
61 ### TerminalRewriteInfo
62 ```typescript
63 type TerminalRewriteInfo =
64 | {
65 kind: 'StartScope';
66 blockId: BlockId; // New block for scope content
67 fallthroughId: BlockId; // Block after scope ends
68 instrId: InstructionId; // Where to insert
69 scope: ReactiveScope; // The scope being created
70 }
71 | {
72 kind: 'EndScope';
73 instrId: InstructionId; // Where to insert
74 fallthroughId: BlockId; // Same as corresponding StartScope
75 };
76 ```
77
78 ### RewriteContext
79 ```typescript
80 type RewriteContext = {
81 source: BasicBlock; // Original block being split
82 instrSliceIdx: number; // Current slice start index
83 nextPreds: Set<BlockId>; // Predecessors for next emitted block
84 nextBlockId: BlockId; // BlockId for next emitted block
85 rewrites: Array<BasicBlock>; // Accumulated split blocks
86 };
87 ```
88
89 ### ScopeTraversalContext
90 ```typescript
91 type ScopeTraversalContext = {
92 fallthroughs: Map<ScopeId, BlockId>; // Cache: scope -> its fallthrough block
93 rewrites: Array<TerminalRewriteInfo>;
94 env: Environment;
95 };
96 ```
97
98 ## Edge Cases
99
100 ### Multiple Rewrites at Same Instruction ID
101 The while loop in Step 2 handles multiple scope start/ends at the same instruction ID.
102
103 ### Nested Scopes
104 The pre-order traversal ensures outer scopes are processed before inner scopes, creating proper nesting in the CFG.
105
106 ### Empty Blocks After Split
107 When a scope boundary falls at the start of a block, the split may create a block with no instructions (only a terminal).
108
109 ### Control Flow Within Scopes
110 The pass preserves existing control flow (if/else, loops) within scopes; it only adds scope entry/exit points.
111
112 ### Early Returns
113 When a return occurs within a scope, the scope terminal still has a fallthrough block, but that block may contain `Unreachable` terminal.
114
115 ## TODOs
116 Line 283-284:
117 ```typescript
118 // TODO make consistent instruction IDs instead of reusing
119 ```
120
121 ## Example
122
123 ### Fixture: `reactive-scopes-if.js`
124
125 **Before BuildReactiveScopeTerminalsHIR:**
126 ```
127 bb0 (block):
128 [1] $29_@0[1:22] = Array [] // x with scope @0 range [1:22]
129 [2] StoreLocal x$30_@0 = $29_@0
130 [3] $32 = LoadLocal a$26
131 [4] If ($32) then:bb2 else:bb3 fallthrough=bb1
132 bb2:
133 [5] $33_@1[5:11] = Array [] // y with scope @1 range [5:11]
134 ...
135 ```
136
137 **After BuildReactiveScopeTerminalsHIR:**
138 ```
139 bb0 (block):
140 [1] Scope @0 [1:28] block=bb9 fallthrough=bb10 // <-- scope terminal inserted
141 bb9:
142 [2] $29_@0 = Array []
143 [3] StoreLocal x$30_@0 = $29_@0
144 [4] $32 = LoadLocal a$26
145 [5] If ($32) then:bb2 else:bb3 fallthrough=bb1
146 bb2:
147 [6] Scope @1 [6:14] block=bb11 fallthrough=bb12 // <-- nested scope terminal
148 bb11:
149 [7] $33_@1 = Array []
150 ...
151 [13] Goto bb12 // <-- scope end goto
152 bb12:
153 ...
154 bb1:
155 [27] Goto bb10 // <-- scope @0 end goto
156 bb10:
157 [28] $50 = LoadLocal x$30_@0
158 [29] Return $50
159 ```
160
161 The key transformation is that scope boundaries become explicit control flow: a `Scope` terminal enters the scope content block, and a `Goto` terminal exits to the fallthrough block. This structure is later used to generate the memoization checks.