| 1 | /** |
| 2 | * Copyright (c) Meta Platforms, Inc. and affiliates. |
| 3 | * |
| 4 | * This source code is licensed under the MIT license found in the |
| 5 | * LICENSE file in the root directory of this source tree. |
| 6 | */ |
| 7 | |
| 8 | import {CompilerError, SourceLocation} from '..'; |
| 9 | import {Environment} from '../HIR'; |
| 10 | import { |
| 11 | DeclarationId, |
| 12 | GeneratedSource, |
| 13 | HIRFunction, |
| 14 | Identifier, |
| 15 | Instruction, |
| 16 | InstructionId, |
| 17 | MutableRange, |
| 18 | Place, |
| 19 | ReactiveScope, |
| 20 | makeInstructionId, |
| 21 | } from '../HIR/HIR'; |
| 22 | import { |
| 23 | doesPatternContainSpreadElement, |
| 24 | eachInstructionOperand, |
| 25 | eachPatternOperand, |
| 26 | } from '../HIR/visitors'; |
| 27 | import DisjointSet from '../Utils/DisjointSet'; |
| 28 | import {Iterable_some, assertExhaustive} from '../Utils/utils'; |
| 29 | |
| 30 | /* |
| 31 | * Note: this is the 1st of 4 passes that determine how to break a function into discrete |
| 32 | * reactive scopes (independently memoizeable units of code): |
| 33 | * 1. InferReactiveScopeVariables (this pass, on HIR) determines operands that mutate |
| 34 | * together and assigns them a unique reactive scope. |
| 35 | * 2. AlignReactiveScopesToBlockScopes (on ReactiveFunction) aligns reactive scopes |
| 36 | * to block scopes. |
| 37 | * 3. MergeOverlappingReactiveScopes (on ReactiveFunction) ensures that reactive |
| 38 | * scopes do not overlap, merging any such scopes. |
| 39 | * 4. BuildReactiveBlocks (on ReactiveFunction) groups the statements for each scope into |
| 40 | * a ReactiveScopeBlock. |
| 41 | * |
| 42 | * For each mutable variable, infers a reactive scope which will construct that |
| 43 | * variable. Variables that co-mutate are assigned to the same reactive scope. |
| 44 | * This pass does *not* infer the set of instructions necessary to compute each |
| 45 | * variable/scope, only the set of variables that will be computed by each scope. |
| 46 | * |
| 47 | * Examples: |
| 48 | * ```javascript |
| 49 | * // Mutable arguments |
| 50 | * let x = {}; |
| 51 | * let y = []; |
| 52 | * foo(x, y); // both args mutable, could alias each other |
| 53 | * y.push(x); // y is part of callee, counts as operand |
| 54 | * |
| 55 | * let z = {}; |
| 56 | * y.push(z); |
| 57 | * |
| 58 | * // Mutable assignment |
| 59 | * let x = {}; |
| 60 | * let y = []; |
| 61 | * x.y = y; // trivial aliasing |
| 62 | * ``` |
| 63 | * |
| 64 | * More generally, all mutable operands (incl lvalue) of an instruction must go in the |
| 65 | * same scope. |
| 66 | * |
| 67 | * ## Implementation |
| 68 | * |
| 69 | * 1. Iterate over all instructions in all blocks (order does not matter, single pass), |
| 70 | * and create disjoint sets ({@link DisjointSet}) for each set of operands that |
| 71 | * mutate together per above rules. |
| 72 | * 2. Iterate the contents of each set, and assign a new {@link ScopeId} to each set, |
| 73 | * and update the `scope` property of each item in that set to that scope id. |
| 74 | * |
| 75 | * ## Other Issues Uncovered |
| 76 | * |
| 77 | * Mutable lifetimes need to account for aliasing (known todo, already described in InferMutableLifetimes.ts) |
| 78 | * |
| 79 | * ```javascript |
| 80 | * let x = {}; |
| 81 | * let y = []; |
| 82 | * x.y = y; // RHS is not considered mutable here bc not further mutation |
| 83 | * mutate(x); // bc y is aliased here, it should still be considered mutable above |
| 84 | * ``` |
| 85 | */ |
| 86 | export function inferReactiveScopeVariables(fn: HIRFunction): void { |
| 87 | /* |
| 88 | * Represents the set of reactive scopes as disjoint sets of identifiers |
| 89 | * that mutate together. |
| 90 | */ |
| 91 | const scopeIdentifiers = findDisjointMutableValues(fn); |
| 92 | |
| 93 | // Maps each scope (by its identifying member) to a ScopeId value |
| 94 | const scopes: Map<Identifier, ReactiveScope> = new Map(); |
| 95 | |
| 96 | /* |
| 97 | * Iterate over all the identifiers and assign a unique ScopeId |
| 98 | * for each scope (based on the set identifier). |
| 99 | * |
| 100 | * At the same time, group the identifiers in each scope and |
| 101 | * build a MutableRange that describes the span of mutations |
| 102 | * across all identifiers in each scope. |
| 103 | */ |
| 104 | scopeIdentifiers.forEach((identifier, groupIdentifier) => { |
| 105 | let scope = scopes.get(groupIdentifier); |
| 106 | if (scope === undefined) { |
| 107 | scope = { |
| 108 | id: fn.env.nextScopeId, |
| 109 | range: identifier.mutableRange, |
| 110 | dependencies: new Set(), |
| 111 | declarations: new Map(), |
| 112 | reassignments: new Set(), |
| 113 | earlyReturnValue: null, |
| 114 | merged: new Set(), |
| 115 | loc: identifier.loc, |
| 116 | }; |
| 117 | scopes.set(groupIdentifier, scope); |
| 118 | } else { |
| 119 | if (scope.range.start === 0) { |
| 120 | scope.range.start = identifier.mutableRange.start; |
| 121 | } else if (identifier.mutableRange.start !== 0) { |
| 122 | scope.range.start = makeInstructionId( |
| 123 | Math.min(scope.range.start, identifier.mutableRange.start), |
| 124 | ); |
| 125 | } |
| 126 | scope.range.end = makeInstructionId( |
| 127 | Math.max(scope.range.end, identifier.mutableRange.end), |
| 128 | ); |
| 129 | scope.loc = mergeLocation(scope.loc, identifier.loc); |
| 130 | } |
| 131 | identifier.scope = scope; |
| 132 | identifier.mutableRange = scope.range; |
| 133 | }); |
| 134 | |
| 135 | let maxInstruction = 0; |
| 136 | for (const [, block] of fn.body.blocks) { |
| 137 | for (const instr of block.instructions) { |
| 138 | maxInstruction = makeInstructionId(Math.max(maxInstruction, instr.id)); |
| 139 | } |
| 140 | maxInstruction = makeInstructionId( |
| 141 | Math.max(maxInstruction, block.terminal.id), |
| 142 | ); |
| 143 | } |
| 144 | |
| 145 | /* |
| 146 | * Validate that all scopes have properly initialized, valid mutable ranges |
| 147 | * within the span of instructions for this function, ie from 1 to 1 past |
| 148 | * the last instruction id. |
| 149 | */ |
| 150 | for (const [, scope] of scopes) { |
| 151 | if ( |
| 152 | scope.range.start === 0 || |
| 153 | scope.range.end === 0 || |
| 154 | maxInstruction === 0 || |
| 155 | scope.range.end > maxInstruction + 1 |
| 156 | ) { |
| 157 | // Make it easier to debug why the error occurred |
| 158 | fn.env.logger?.debugLogIRs?.({ |
| 159 | kind: 'hir', |
| 160 | name: 'InferReactiveScopeVariables (invalid scope)', |
| 161 | value: fn, |
| 162 | }); |
| 163 | CompilerError.invariant(false, { |
| 164 | reason: `Invalid mutable range for scope`, |
| 165 | description: `Scope @${scope.id} has range [${scope.range.start}:${ |
| 166 | scope.range.end |
| 167 | }] but the valid range is [1:${maxInstruction + 1}]`, |
| 168 | loc: GeneratedSource, |
| 169 | }); |
| 170 | } |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | function mergeLocation(l: SourceLocation, r: SourceLocation): SourceLocation { |
| 175 | if (l === GeneratedSource) { |
| 176 | return r; |
| 177 | } else if (r === GeneratedSource) { |
| 178 | return l; |
| 179 | } else { |
| 180 | return { |
| 181 | filename: l.filename, |
| 182 | identifierName: l.identifierName, |
| 183 | start: { |
| 184 | index: Math.min(l.start.index, r.start.index), |
| 185 | line: Math.min(l.start.line, r.start.line), |
| 186 | column: Math.min(l.start.column, r.start.column), |
| 187 | }, |
| 188 | end: { |
| 189 | index: Math.max(l.end.index, r.end.index), |
| 190 | line: Math.max(l.end.line, r.end.line), |
| 191 | column: Math.max(l.end.column, r.end.column), |
| 192 | }, |
| 193 | }; |
| 194 | } |
| 195 | } |
| 196 | |
| 197 | // Is the operand mutable at this given instruction |
| 198 | export function isMutable(instr: {id: InstructionId}, place: Place): boolean { |
| 199 | return inRange(instr, place.identifier.mutableRange); |
| 200 | } |
| 201 | |
| 202 | export function inRange( |
| 203 | {id}: {id: InstructionId}, |
| 204 | range: MutableRange, |
| 205 | ): boolean { |
| 206 | return id >= range.start && id < range.end; |
| 207 | } |
| 208 | |
| 209 | function mayAllocate(_env: Environment, instruction: Instruction): boolean { |
| 210 | const {value} = instruction; |
| 211 | switch (value.kind) { |
| 212 | case 'Destructure': { |
| 213 | return doesPatternContainSpreadElement(value.lvalue.pattern); |
| 214 | } |
| 215 | case 'PostfixUpdate': |
| 216 | case 'PrefixUpdate': |
| 217 | case 'Await': |
| 218 | case 'DeclareLocal': |
| 219 | case 'DeclareContext': |
| 220 | case 'StoreLocal': |
| 221 | case 'LoadGlobal': |
| 222 | case 'MetaProperty': |
| 223 | case 'TypeCastExpression': |
| 224 | case 'LoadLocal': |
| 225 | case 'LoadContext': |
| 226 | case 'StoreContext': |
| 227 | case 'PropertyDelete': |
| 228 | case 'ComputedLoad': |
| 229 | case 'ComputedDelete': |
| 230 | case 'JSXText': |
| 231 | case 'TemplateLiteral': |
| 232 | case 'Primitive': |
| 233 | case 'GetIterator': |
| 234 | case 'IteratorNext': |
| 235 | case 'NextPropertyOf': |
| 236 | case 'Debugger': |
| 237 | case 'StartMemoize': |
| 238 | case 'FinishMemoize': |
| 239 | case 'UnaryExpression': |
| 240 | case 'BinaryExpression': |
| 241 | case 'PropertyLoad': |
| 242 | case 'StoreGlobal': { |
| 243 | return false; |
| 244 | } |
| 245 | case 'TaggedTemplateExpression': |
| 246 | case 'CallExpression': |
| 247 | case 'MethodCall': { |
| 248 | return instruction.lvalue.identifier.type.kind !== 'Primitive'; |
| 249 | } |
| 250 | case 'RegExpLiteral': |
| 251 | case 'PropertyStore': |
| 252 | case 'ComputedStore': |
| 253 | case 'ArrayExpression': |
| 254 | case 'JsxExpression': |
| 255 | case 'JsxFragment': |
| 256 | case 'NewExpression': |
| 257 | case 'ObjectExpression': |
| 258 | case 'UnsupportedNode': |
| 259 | case 'ObjectMethod': |
| 260 | case 'FunctionExpression': { |
| 261 | return true; |
| 262 | } |
| 263 | default: { |
| 264 | assertExhaustive( |
| 265 | value, |
| 266 | `Unexpected value kind \`${(value as any).kind}\``, |
| 267 | ); |
| 268 | } |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | export function findDisjointMutableValues( |
| 273 | fn: HIRFunction, |
| 274 | ): DisjointSet<Identifier> { |
| 275 | const scopeIdentifiers = new DisjointSet<Identifier>(); |
| 276 | |
| 277 | const declarations = new Map<DeclarationId, Identifier>(); |
| 278 | function declareIdentifier(lvalue: Place): void { |
| 279 | if (!declarations.has(lvalue.identifier.declarationId)) { |
| 280 | declarations.set(lvalue.identifier.declarationId, lvalue.identifier); |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | for (const [_, block] of fn.body.blocks) { |
| 285 | /* |
| 286 | * If a phi is mutated after creation, then we need to alias all of its operands such that they |
| 287 | * are assigned to the same scope. |
| 288 | */ |
| 289 | for (const phi of block.phis) { |
| 290 | const firstInstructionIdOfBlock = |
| 291 | block.instructions.at(0)?.id ?? block.terminal.id; |
| 292 | const isPhiMutatedAfterCreation = |
| 293 | phi.place.identifier.mutableRange.start + 1 !== |
| 294 | phi.place.identifier.mutableRange.end && |
| 295 | phi.place.identifier.mutableRange.end > firstInstructionIdOfBlock; |
| 296 | /* |
| 297 | * A phi operand defined at or after the phi's block is a loop back-edge: |
| 298 | * the variable is reassigned within the loop (eg a counter `a++` or |
| 299 | * `a = a + 1`). The reassignment must count as the loop's scope |
| 300 | * reassigning the variable, so union the phi with its operands and |
| 301 | * declaration. Otherwise the variable's pre-loop value would become a |
| 302 | * dependency of the scope even though the scope changes the value as it |
| 303 | * executes, making the scope's dependencies unstable (the cached |
| 304 | * dependency would be the post-loop value, which can never match the |
| 305 | * pre-loop value compared at the top of the scope). |
| 306 | */ |
| 307 | const isLoopCarriedReassignment = |
| 308 | !isPhiMutatedAfterCreation && |
| 309 | Iterable_some( |
| 310 | phi.operands.values(), |
| 311 | operand => |
| 312 | operand.identifier.mutableRange.start >= firstInstructionIdOfBlock, |
| 313 | ); |
| 314 | if (isPhiMutatedAfterCreation || isLoopCarriedReassignment) { |
| 315 | const operands = [phi.place.identifier]; |
| 316 | const declaration = declarations.get( |
| 317 | phi.place.identifier.declarationId, |
| 318 | ); |
| 319 | if (declaration !== undefined) { |
| 320 | operands.push(declaration); |
| 321 | } |
| 322 | for (const [_, phiId] of phi.operands) { |
| 323 | operands.push(phiId.identifier); |
| 324 | } |
| 325 | scopeIdentifiers.union(operands); |
| 326 | } else if (fn.env.config.enableForest) { |
| 327 | for (const [, phiId] of phi.operands) { |
| 328 | scopeIdentifiers.union([phi.place.identifier, phiId.identifier]); |
| 329 | } |
| 330 | } |
| 331 | } |
| 332 | |
| 333 | for (const instr of block.instructions) { |
| 334 | const operands: Array<Identifier> = []; |
| 335 | const range = instr.lvalue.identifier.mutableRange; |
| 336 | if (range.end > range.start + 1 || mayAllocate(fn.env, instr)) { |
| 337 | operands.push(instr.lvalue!.identifier); |
| 338 | } |
| 339 | if ( |
| 340 | instr.value.kind === 'DeclareLocal' || |
| 341 | instr.value.kind === 'DeclareContext' |
| 342 | ) { |
| 343 | declareIdentifier(instr.value.lvalue.place); |
| 344 | } else if ( |
| 345 | instr.value.kind === 'StoreLocal' || |
| 346 | instr.value.kind === 'StoreContext' |
| 347 | ) { |
| 348 | declareIdentifier(instr.value.lvalue.place); |
| 349 | if ( |
| 350 | instr.value.lvalue.place.identifier.mutableRange.end > |
| 351 | instr.value.lvalue.place.identifier.mutableRange.start + 1 |
| 352 | ) { |
| 353 | operands.push(instr.value.lvalue.place.identifier); |
| 354 | } |
| 355 | if ( |
| 356 | isMutable(instr, instr.value.value) && |
| 357 | instr.value.value.identifier.mutableRange.start > 0 |
| 358 | ) { |
| 359 | operands.push(instr.value.value.identifier); |
| 360 | } |
| 361 | } else if (instr.value.kind === 'Destructure') { |
| 362 | for (const place of eachPatternOperand(instr.value.lvalue.pattern)) { |
| 363 | declareIdentifier(place); |
| 364 | if ( |
| 365 | place.identifier.mutableRange.end > |
| 366 | place.identifier.mutableRange.start + 1 |
| 367 | ) { |
| 368 | operands.push(place.identifier); |
| 369 | } |
| 370 | } |
| 371 | if ( |
| 372 | isMutable(instr, instr.value.value) && |
| 373 | instr.value.value.identifier.mutableRange.start > 0 |
| 374 | ) { |
| 375 | operands.push(instr.value.value.identifier); |
| 376 | } |
| 377 | } else if (instr.value.kind === 'MethodCall') { |
| 378 | for (const operand of eachInstructionOperand(instr)) { |
| 379 | if ( |
| 380 | isMutable(instr, operand) && |
| 381 | /* |
| 382 | * exclude global variables from being added to scopes, we can't recreate them! |
| 383 | * TODO: improve handling of module-scoped variables and globals |
| 384 | */ |
| 385 | operand.identifier.mutableRange.start > 0 |
| 386 | ) { |
| 387 | operands.push(operand.identifier); |
| 388 | } |
| 389 | } |
| 390 | /* |
| 391 | * Ensure that the ComputedLoad to resolve the method is in the same scope as the |
| 392 | * call itself |
| 393 | */ |
| 394 | operands.push(instr.value.property.identifier); |
| 395 | } else { |
| 396 | for (const operand of eachInstructionOperand(instr)) { |
| 397 | if ( |
| 398 | isMutable(instr, operand) && |
| 399 | /* |
| 400 | * exclude global variables from being added to scopes, we can't recreate them! |
| 401 | * TODO: improve handling of module-scoped variables and globals |
| 402 | */ |
| 403 | operand.identifier.mutableRange.start > 0 |
| 404 | ) { |
| 405 | operands.push(operand.identifier); |
| 406 | } |
| 407 | } |
| 408 | } |
| 409 | if (operands.length !== 0) { |
| 410 | scopeIdentifiers.union(operands); |
| 411 | } |
| 412 | } |
| 413 | } |
| 414 | return scopeIdentifiers; |
| 415 | } |