@samitouri / QOS-React
Code Commits Issues Pulls Sessions CI/CD
main
main
md 149 lines 6.98 KB
Rendered Raw
1 # inferMutationAliasingRanges
2
3 ## File
4 `src/Inference/InferMutationAliasingRanges.ts`
5
6 ## Purpose
7 This pass builds an abstract model of the heap and interprets the effects of the given function to determine: (1) the mutable ranges of all identifiers, (2) the externally-visible effects of the function (mutations of params/context-vars, aliasing relationships), and (3) the legacy `Effect` annotation for each Place.
8
9 ## Input Invariants
10 - InferMutationAliasingEffects must have already run, populating `instr.effects` on each instruction with aliasing/mutation effects
11 - SSA form must be established (identifiers are in SSA)
12 - Type inference has been run (InferTypes)
13 - Functions have been analyzed (AnalyseFunctions)
14 - Dead code elimination has been performed
15
16 ## Output Guarantees
17 - Every identifier has a populated `mutableRange` (start:end instruction IDs)
18 - Every Place has a legacy `Effect` annotation (Read, Capture, Store, Freeze, etc.)
19 - The function's `aliasingEffects` array is populated with externally-visible effects (mutations of params/context-vars, aliasing between params/context-vars/return)
20 - Validation errors are collected for invalid effects like `MutateFrozen` or `MutateGlobal`
21
22 ## Algorithm
23 The pass operates in three main phases:
24
25 **Part 1: Build Data Flow Graph and Infer Mutable Ranges**
26 1. Creates an `AliasingState` which maintains a `Node` for each identifier
27 2. Iterates through all blocks and instructions, processing effects in program order
28 3. For each effect:
29 - `Create`/`CreateFunction`: Creates a new node in the graph
30 - `CreateFrom`/`Assign`/`Alias`: Adds alias edges between nodes (with ordering index)
31 - `MaybeAlias`: Adds conditional alias edges
32 - `Capture`: Adds capture edges (for transitive mutations)
33 - `Mutate*`: Queues mutations for later processing
34 - `Render`: Queues render effects for later processing
35 4. Phi node operands are connected once their predecessor blocks have been visited
36 5. After the graph is built, mutations are processed:
37 - Mutations propagate both forward (via edges) and backward (via aliases/captures)
38 - Each mutation extends the `mutableRange.end` of affected identifiers
39 - Transitive mutations also traverse capture edges backward
40 - `MaybeAlias` edges downgrade mutations to `Conditional`
41 6. Render effects are processed to mark values as rendered
42
43 **Part 2: Populate Legacy Per-Place Effects**
44 - Sets legacy effects on lvalues and operands based on instruction effects and mutable ranges
45 - Fixes up mutable range start values for identifiers that are mutated after creation
46
47 **Part 3: Infer Externally-Visible Function Effects**
48 - Creates a `Create` effect for the return value
49 - Simulates transitive mutations of each param/context-var/return to detect capture relationships
50 - Produces `Alias`/`Capture` effects showing data flow between params/context-vars/return
51
52 ## Key Data Structures
53
54 ### `AliasingState`
55 The main state class maintaining the data flow graph:
56 - `nodes: Map<Identifier, Node>` - Maps identifiers to their graph nodes
57
58 ### `Node`
59 Represents an identifier in the data flow graph:
60 ```typescript
61 type Node = {
62 id: Identifier;
63 createdFrom: Map<Identifier, number>; // CreateFrom edges (source -> index)
64 captures: Map<Identifier, number>; // Capture edges (source -> index)
65 aliases: Map<Identifier, number>; // Alias/Assign edges (source -> index)
66 maybeAliases: Map<Identifier, number>; // MaybeAlias edges (source -> index)
67 edges: Array<{index, node, kind}>; // Forward edges to other nodes
68 transitive: {kind: MutationKind; loc} | null; // Transitive mutation info
69 local: {kind: MutationKind; loc} | null; // Local mutation info
70 lastMutated: number; // Index of last mutation affecting this node
71 mutationReason: MutationReason | null; // Reason for mutation
72 value: {kind: 'Object'} | {kind: 'Phi'} | {kind: 'Function'; function: HIRFunction};
73 render: Place | null; // Render context if used in JSX
74 };
75 ```
76
77 ### `MutationKind`
78 Enum describing mutation certainty:
79 ```typescript
80 enum MutationKind {
81 None = 0,
82 Conditional = 1, // May mutate (e.g., via MaybeAlias or MutateConditionally)
83 Definite = 2, // Definitely mutates
84 }
85 ```
86
87 ## Edge Cases
88
89 ### Phi Nodes
90 - Phi nodes are created as special `{kind: 'Phi'}` nodes
91 - Phi operands from predecessor blocks are processed with pending edges until the predecessor is visited
92 - When traversing "forwards" through edges and encountering a phi, backward traversal is stopped (prevents mutation from one phi input affecting other inputs)
93
94 ### Transitive vs Local Mutations
95 - Local mutations (`Mutate`) only affect alias/assign edges backward
96 - Transitive mutations (`MutateTransitive`) also affect capture edges backward
97 - Both affect all forward edges
98
99 ### MaybeAlias
100 - Mutations through MaybeAlias edges are downgraded to `Conditional`
101 - This prevents false positive errors when we cannot be certain about aliasing
102
103 ### Function Values
104 - Functions are tracked specially as `{kind: 'Function'}` nodes
105 - When a function is mutated (transitively), errors from the function body are propagated
106 - This handles cases where mutating a captured value in a function affects render safety
107
108 ### Render Effect Propagation
109 - Render effects traverse backward through alias/capture/createFrom edges
110 - Functions that have not been mutated are skipped during render traversal (except for JSX-returning functions)
111 - Ref types (`isUseRefType`) stop render traversal
112
113 ## TODOs
114 1. Assign effects should have an invariant that the node is not initialized yet. Currently `InferFunctionExpressionAliasingEffectSignatures` infers Assign effects that should be Alias, causing reinitialization.
115
116 2. Phi place effects are not properly set today.
117
118 3. Phi mutable range start calculation is imprecise - currently just sets it to the instruction before the block rather than computing the exact start.
119
120 ## Example
121
122 Consider the following code:
123 ```javascript
124 function foo() {
125 let a = {}; // Create a (instruction 1)
126 let b = {}; // Create b (instruction 3)
127 a = b; // Assign a <- b (instruction 8)
128 mutate(a, b); // MutateTransitiveConditionally a, b (instruction 16)
129 return a;
130 }
131 ```
132
133 The pass builds a graph:
134 1. Creates node for `{}` at instruction 1 (initially assigned to `a`)
135 2. Creates node for `{}` at instruction 3 (initially assigned to `b`)
136 3. At instruction 8, creates alias edge: `b -> a` with index 8
137 4. At instruction 16, mutations are queued for `a` and `b`
138
139 When processing the mutation of `a` at instruction 16:
140 - Extends `a`'s mutableRange.end to 17
141 - Traverses backward through alias edge to `b`, extends `b`'s mutableRange.end to 17
142 - Since `a = b`, both objects must be considered mutable until instruction 17
143
144 The output shows identifiers with range annotations like `$25[3:17]` meaning:
145 - `$25` is the identifier
146 - `3` is the instruction where it was created
147 - `17` is the instruction after which it is no longer mutated
148
149 For aliased values, the ranges are unified - all values that could be affected by a mutation have their ranges extended to include that mutation point.