@samitouri / QOS-React-2
Code Commits Issues Pulls Sessions CI/CD
main
main
md 213 lines 7.74 KB
Rendered Raw
1 # mergeReactiveScopesThatInvalidateTogether
2
3 ## File
4 `src/ReactiveScopes/MergeReactiveScopesThatInvalidateTogether.ts`
5
6 ## Purpose
7 This pass is an optimization that reduces memoization overhead in the compiled output by merging reactive scopes that will always invalidate together. The pass operates on the ReactiveFunction representation and works in two main scenarios:
8
9 1. **Consecutive Scopes**: When two scopes appear sequentially in the same reactive block with identical dependencies (or where the output of the first scope is the sole input to the second), they are merged into a single scope. This reduces the number of memo cache slots used and eliminates redundant dependency comparisons.
10
11 2. **Nested Scopes**: When an inner scope has the same dependencies as its parent scope, the inner scope is flattened into the parent. Since PropagateScopeDependencies propagates dependencies upward, nested scopes can only have equal or fewer dependencies than their parents, never more. When they're equal, the inner scope always invalidates with the parent, making it safe and beneficial to flatten.
12
13 ## Input Invariants
14 - The ReactiveFunction has already undergone scope dependency propagation (via `PropagateScopeDependencies`)
15 - The function has been pruned of unused scopes (via `pruneNonReactiveDependencies` and `pruneUnusedScopes`)
16 - Scopes have valid `dependencies`, `declarations`, `range`, and `reassignments` fields
17 - The ReactiveFunction is in a valid structural state with properly formed blocks and instructions
18
19 ## Output Guarantees
20 - **Fewer scopes**: Consecutive and nested scopes with identical dependencies are merged
21 - **Valid scope ranges**: Merged scopes have their `range.end` updated to cover all merged instructions
22 - **Updated declarations**: Scope declarations are updated to remove any that are no longer used after the merged scope
23 - **Merged scope tracking**: The `scope.merged` set tracks which scope IDs were merged into each surviving scope
24 - **Preserved semantics**: Only safe-to-memoize intermediate instructions are absorbed into merged scopes
25
26 ## Algorithm
27
28 The pass operates in multiple phases:
29
30 ### Phase 1: Find Last Usage
31 A visitor (`FindLastUsageVisitor`) collects the last usage instruction ID for each declaration:
32
33 ```typescript
34 class FindLastUsageVisitor extends ReactiveFunctionVisitor<void> {
35 lastUsage: Map<DeclarationId, InstructionId> = new Map();
36
37 override visitPlace(id: InstructionId, place: Place, _state: void): void {
38 const previousUsage = this.lastUsage.get(place.identifier.declarationId);
39 const lastUsage =
40 previousUsage !== undefined
41 ? makeInstructionId(Math.max(previousUsage, id))
42 : id;
43 this.lastUsage.set(place.identifier.declarationId, lastUsage);
44 }
45 }
46 ```
47
48 ### Phase 2: Transform (Nested Scope Flattening)
49 The `transformScope` method flattens nested scopes with identical dependencies:
50
51 ```typescript
52 override transformScope(
53 scopeBlock: ReactiveScopeBlock,
54 state: ReactiveScopeDependencies | null,
55 ): Transformed<ReactiveStatement> {
56 this.visitScope(scopeBlock, scopeBlock.scope.dependencies);
57 if (
58 state !== null &&
59 areEqualDependencies(state, scopeBlock.scope.dependencies)
60 ) {
61 return {kind: 'replace-many', value: scopeBlock.instructions};
62 } else {
63 return {kind: 'keep'};
64 }
65 }
66 ```
67
68 ### Phase 3: Visit Block (Consecutive Scope Merging)
69 Within `visitBlock`, the pass:
70 1. First traverses nested blocks recursively
71 2. Iterates through instructions, tracking merge candidates
72 3. Determines if consecutive scopes can merge based on:
73 - Identical dependencies, OR
74 - Output of first scope is input to second scope (with always-invalidating types)
75 4. Collects intermediate lvalues and ensures they're only used by the next scope
76 5. Merges eligible scopes by combining instructions and updating range/declarations
77
78 ### Key Merging Conditions (`canMergeScopes`):
79 ```typescript
80 function canMergeScopes(
81 current: ReactiveScopeBlock,
82 next: ReactiveScopeBlock,
83 temporaries: Map<DeclarationId, DeclarationId>,
84 ): boolean {
85 // Don't merge scopes with reassignments
86 if (current.scope.reassignments.size !== 0 || next.scope.reassignments.size !== 0) {
87 return false;
88 }
89 // Merge scopes whose dependencies are identical
90 if (areEqualDependencies(current.scope.dependencies, next.scope.dependencies)) {
91 return true;
92 }
93 // Merge scopes where outputs of previous are inputs of next
94 // (with always-invalidating type check)
95 // ...
96 }
97 ```
98
99 ### Always-Invalidating Types:
100 ```typescript
101 export function isAlwaysInvalidatingType(type: Type): boolean {
102 switch (type.kind) {
103 case 'Object': {
104 switch (type.shapeId) {
105 case BuiltInArrayId:
106 case BuiltInObjectId:
107 case BuiltInFunctionId:
108 case BuiltInJsxId: {
109 return true;
110 }
111 }
112 break;
113 }
114 case 'Function': {
115 return true;
116 }
117 }
118 return false;
119 }
120 ```
121
122 ## Edge Cases
123
124 ### Terminals
125 The pass does not merge across terminals (control flow boundaries).
126
127 ### Pruned Scopes
128 Merging stops at pruned scopes.
129
130 ### Reassignments
131 Scopes containing reassignments cannot be merged (side-effect ordering concerns).
132
133 ### Intermediate Reassignments
134 Non-const StoreLocal instructions between scopes prevent merging.
135
136 ### Safe Intermediate Instructions
137 Only certain instruction types are allowed between merged scopes: `BinaryExpression`, `ComputedLoad`, `JSXText`, `LoadGlobal`, `LoadLocal`, `Primitive`, `PropertyLoad`, `TemplateLiteral`, `UnaryExpression`, and const `StoreLocal`.
138
139 ### Lvalue Usage
140 Intermediate values must be last-used at or before the next scope to allow merging.
141
142 ### Non-Invalidating Outputs
143 If a scope's output may not change when inputs change (e.g., `foo(x) { return x < 10 }` returns same boolean for different x values), that scope cannot be a merge candidate for subsequent scopes.
144
145 ## TODOs
146 ```typescript
147 /*
148 * TODO LeaveSSA: use IdentifierId for more precise tracking
149 * Using DeclarationId is necessary for compatible output but produces suboptimal results
150 * in cases where a scope defines a variable, but that version is never read and always
151 * overwritten later.
152 * see reassignment-separate-scopes.js for example
153 */
154 lastUsage: Map<DeclarationId, InstructionId> = new Map();
155 ```
156
157 ## Example
158
159 ### Fixture: `merge-consecutive-scopes-deps-subset-of-decls.js`
160
161 **Input:**
162 ```javascript
163 import {useState} from 'react';
164
165 function Component() {
166 const [count, setCount] = useState(0);
167 return (
168 <div>
169 <button onClick={() => setCount(count - 1)}>Decrement</button>
170 <button onClick={() => setCount(count + 1)}>Increment</button>
171 </div>
172 );
173 }
174 ```
175
176 **After MergeReactiveScopesThatInvalidateTogether** (from `yarn snap -p merge-consecutive-scopes-deps-subset-of-decls.js -d`):
177 ```
178 scope @1 [7:24] dependencies=[count$32:TPrimitive] declarations=[$51_@5] reassignments=[] {
179 [8] $35_@1 = Function @context[setCount$33, count$32] // decrement callback
180 [10] $41 = JSXText "Decrement"
181 [12] $42_@2 = JSX <button onClick={$35_@1}>{$41}</button>
182 [15] $43_@3 = Function @context[setCount$33, count$32] // increment callback
183 [17] $49 = JSXText "Increment"
184 [19] $50_@4 = JSX <button onClick={$43_@3}>{$49}</button>
185 [22] $51_@5 = JSX <div>{$42_@2}{$50_@4}</div>
186 }
187 ```
188
189 All scopes are merged because they share `count` as a dependency. Without merging, this would have separate scopes for each callback and button element.
190
191 **Generated Code:**
192 ```javascript
193 function Component() {
194 const $ = _c(2);
195 const [count, setCount] = useState(0);
196 let t0;
197 if ($[0] !== count) {
198 t0 = (
199 <div>
200 <button onClick={() => setCount(count - 1)}>Decrement</button>
201 <button onClick={() => setCount(count + 1)}>Increment</button>
202 </div>
203 );
204 $[0] = count;
205 $[1] = t0;
206 } else {
207 t0 = $[1];
208 }
209 return t0;
210 }
211 ```
212
213 The merged version uses only 2 cache slots instead of potentially 6-8.