| 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} from '..'; |
| 9 | import { |
| 10 | DeclarationId, |
| 11 | GeneratedSource, |
| 12 | InstructionId, |
| 13 | InstructionKind, |
| 14 | Place, |
| 15 | ReactiveBlock, |
| 16 | ReactiveFunction, |
| 17 | ReactiveScope, |
| 18 | ReactiveScopeBlock, |
| 19 | ReactiveScopeDependencies, |
| 20 | ReactiveScopeDependency, |
| 21 | ReactiveStatement, |
| 22 | Type, |
| 23 | areEqualPaths, |
| 24 | makeInstructionId, |
| 25 | } from '../HIR'; |
| 26 | import { |
| 27 | BuiltInArrayId, |
| 28 | BuiltInFunctionId, |
| 29 | BuiltInJsxId, |
| 30 | BuiltInObjectId, |
| 31 | } from '../HIR/ObjectShape'; |
| 32 | import {eachInstructionLValue} from '../HIR/visitors'; |
| 33 | import {assertExhaustive, Iterable_some} from '../Utils/utils'; |
| 34 | import {printReactiveScopeSummary} from './PrintReactiveFunction'; |
| 35 | import { |
| 36 | ReactiveFunctionTransform, |
| 37 | ReactiveFunctionVisitor, |
| 38 | Transformed, |
| 39 | visitReactiveFunction, |
| 40 | } from './visitors'; |
| 41 | |
| 42 | /* |
| 43 | * The primary goal of this pass is to reduce memoization overhead, specifically: |
| 44 | * - Use fewer memo slots |
| 45 | * - Reduce the number of comparisons and other memoization-related instructions |
| 46 | * |
| 47 | * The algorithm merges in two main cases: consecutive scopes that invalidate together |
| 48 | * or nested scopes that invalidate together |
| 49 | * |
| 50 | * ## Consecutive Scopes |
| 51 | * |
| 52 | * The idea is that if two consecutive scopes would always invalidate together, |
| 53 | * it's more efficient to group the scopes together to save on memoization overhead. |
| 54 | * |
| 55 | * This optimization is necessarily somewhat limited. First, we only merge |
| 56 | * scopes that are in the same (reactive) block, ie we don't merge across |
| 57 | * control-flow or block-scoping boundaries. Second, we can only merge scopes |
| 58 | * so long as any intermediate instructions are safe to memoize — specifically, |
| 59 | * as long as the values created by those instructions are only referenced by |
| 60 | * the second scope and not elsewhere. This is to avoid changing control-flow |
| 61 | * and to avoid increasing the number of scope outputs (which defeats the optimization). |
| 62 | * |
| 63 | * With that in mind we can apply the optimization in two cases. Given a block with |
| 64 | * scope A, some safe-to-memoize instructions I, and scope B, we can merge scopes when: |
| 65 | * - A and B have identical dependencies. This means they will invalidate together, so |
| 66 | * by merging the scopes we can avoid duplicate cache slots and duplicate checks of |
| 67 | * those dependencies. |
| 68 | * - The output of A is the input to B. Any invalidation of A will change its output |
| 69 | * which invalidates B, so we can similarly merge scopes. Note that this optimization |
| 70 | * may not be beneficial if the outupts of A are not guaranteed to change if its input |
| 71 | * changes, but in practice this is generally the case. |
| 72 | * |
| 73 | * ## Nested Scopes |
| 74 | * |
| 75 | * In this case, if an inner scope has the same dependencies as its parent, then we can |
| 76 | * flatten away the inner scope since it will always invalidate at the same time. |
| 77 | * |
| 78 | * Note that PropagateScopeDependencies propagates scope dependencies upwards. This ensures |
| 79 | * that parent scopes have the union of their own direct dependencies as well as those of |
| 80 | * their (transitive) children. As a result nested scopes may have the same or fewer |
| 81 | * dependencies than their parents, but not more dependencies. If they have fewer dependncies, |
| 82 | * it means that the inner scope does not always invalidate with the parent and we should not |
| 83 | * flatten. If they inner scope has the exact same dependencies, however, then it's always |
| 84 | * better to flatten. |
| 85 | */ |
| 86 | export function mergeReactiveScopesThatInvalidateTogether( |
| 87 | fn: ReactiveFunction, |
| 88 | ): void { |
| 89 | const lastUsageVisitor = new FindLastUsageVisitor(); |
| 90 | visitReactiveFunction(fn, lastUsageVisitor, undefined); |
| 91 | visitReactiveFunction(fn, new Transform(lastUsageVisitor.lastUsage), null); |
| 92 | } |
| 93 | |
| 94 | const DEBUG: boolean = false; |
| 95 | function log(msg: string): void { |
| 96 | if (DEBUG) { |
| 97 | console.log(msg); |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | class FindLastUsageVisitor extends ReactiveFunctionVisitor<void> { |
| 102 | /* |
| 103 | * TODO LeaveSSA: use IdentifierId for more precise tracking |
| 104 | * Using DeclarationId is necessary for compatible output but produces suboptimal results |
| 105 | * in cases where a scope defines a variable, but that version is never read and always |
| 106 | * overwritten later. |
| 107 | * see reassignment-separate-scopes.js for example |
| 108 | */ |
| 109 | lastUsage: Map<DeclarationId, InstructionId> = new Map(); |
| 110 | |
| 111 | override visitPlace(id: InstructionId, place: Place, _state: void): void { |
| 112 | const previousUsage = this.lastUsage.get(place.identifier.declarationId); |
| 113 | const lastUsage = |
| 114 | previousUsage !== undefined |
| 115 | ? makeInstructionId(Math.max(previousUsage, id)) |
| 116 | : id; |
| 117 | this.lastUsage.set(place.identifier.declarationId, lastUsage); |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | class Transform extends ReactiveFunctionTransform<ReactiveScopeDependencies | null> { |
| 122 | lastUsage: Map<DeclarationId, InstructionId>; |
| 123 | temporaries: Map<DeclarationId, DeclarationId> = new Map(); |
| 124 | |
| 125 | constructor(lastUsage: Map<DeclarationId, InstructionId>) { |
| 126 | super(); |
| 127 | this.lastUsage = lastUsage; |
| 128 | } |
| 129 | |
| 130 | override transformScope( |
| 131 | scopeBlock: ReactiveScopeBlock, |
| 132 | state: ReactiveScopeDependencies | null, |
| 133 | ): Transformed<ReactiveStatement> { |
| 134 | this.visitScope(scopeBlock, scopeBlock.scope.dependencies); |
| 135 | if ( |
| 136 | state !== null && |
| 137 | areEqualDependencies(state, scopeBlock.scope.dependencies) |
| 138 | ) { |
| 139 | return {kind: 'replace-many', value: scopeBlock.instructions}; |
| 140 | } else { |
| 141 | return {kind: 'keep'}; |
| 142 | } |
| 143 | } |
| 144 | |
| 145 | override visitBlock( |
| 146 | block: ReactiveBlock, |
| 147 | state: ReactiveScopeDependencies | null, |
| 148 | ): void { |
| 149 | // Pass 1: visit nested blocks to potentially merge their scopes |
| 150 | this.traverseBlock(block, state); |
| 151 | |
| 152 | // Pass 2: identify scopes for merging |
| 153 | type MergedScope = { |
| 154 | block: ReactiveScopeBlock; |
| 155 | from: number; |
| 156 | to: number; |
| 157 | lvalues: Set<DeclarationId>; |
| 158 | }; |
| 159 | let current: MergedScope | null = null; |
| 160 | const merged: Array<MergedScope> = []; |
| 161 | function reset(): void { |
| 162 | CompilerError.invariant(current !== null, { |
| 163 | reason: |
| 164 | 'MergeConsecutiveScopes: expected current scope to be non-null if reset()', |
| 165 | loc: GeneratedSource, |
| 166 | }); |
| 167 | if (current.to > current.from + 1) { |
| 168 | merged.push(current); |
| 169 | } |
| 170 | current = null; |
| 171 | } |
| 172 | for (let i = 0; i < block.length; i++) { |
| 173 | const instr = block[i]!; |
| 174 | switch (instr.kind) { |
| 175 | case 'terminal': { |
| 176 | // For now we don't merge across terminals |
| 177 | if (current !== null) { |
| 178 | log( |
| 179 | `Reset scope @${current.block.scope.id} from terminal [${instr.terminal.id}]`, |
| 180 | ); |
| 181 | reset(); |
| 182 | } |
| 183 | break; |
| 184 | } |
| 185 | case 'pruned-scope': { |
| 186 | // For now we don't merge across pruned scopes |
| 187 | if (current !== null) { |
| 188 | log( |
| 189 | `Reset scope @${current.block.scope.id} from pruned scope @${instr.scope.id}`, |
| 190 | ); |
| 191 | reset(); |
| 192 | } |
| 193 | break; |
| 194 | } |
| 195 | case 'instruction': { |
| 196 | switch (instr.instruction.value.kind) { |
| 197 | case 'BinaryExpression': |
| 198 | case 'ComputedLoad': |
| 199 | case 'JSXText': |
| 200 | case 'LoadGlobal': |
| 201 | case 'LoadLocal': |
| 202 | case 'Primitive': |
| 203 | case 'PropertyLoad': |
| 204 | case 'TemplateLiteral': |
| 205 | case 'UnaryExpression': { |
| 206 | /* |
| 207 | * We can merge two scopes if there are intervening instructions, but: |
| 208 | * - Only if the instructions are simple and it's okay to make them |
| 209 | * execute conditionally (hence allowing a conservative subset of value kinds) |
| 210 | * - The values produced are used at or before the next scope. If they are used |
| 211 | * later and we move them into the scope, then they wouldn't be accessible to |
| 212 | * subsequent code wo expanding the set of declarations, which we want to avoid |
| 213 | */ |
| 214 | if (current !== null && instr.instruction.lvalue !== null) { |
| 215 | current.lvalues.add( |
| 216 | instr.instruction.lvalue.identifier.declarationId, |
| 217 | ); |
| 218 | if (instr.instruction.value.kind === 'LoadLocal') { |
| 219 | this.temporaries.set( |
| 220 | instr.instruction.lvalue.identifier.declarationId, |
| 221 | instr.instruction.value.place.identifier.declarationId, |
| 222 | ); |
| 223 | } |
| 224 | } |
| 225 | break; |
| 226 | } |
| 227 | case 'StoreLocal': { |
| 228 | /** |
| 229 | * It's safe to have intervening StoreLocal instructions _if_ they are const |
| 230 | * and the last usage of the variable is at or before the next scope. This is |
| 231 | * similar to the case above for simple instructions. |
| 232 | * |
| 233 | * Reassignments are *not* safe to merge since they are a side-effect that we |
| 234 | * don't want to make conditional. |
| 235 | */ |
| 236 | if (current !== null) { |
| 237 | if ( |
| 238 | instr.instruction.value.lvalue.kind === InstructionKind.Const |
| 239 | ) { |
| 240 | for (const lvalue of eachInstructionLValue( |
| 241 | instr.instruction, |
| 242 | )) { |
| 243 | current.lvalues.add(lvalue.identifier.declarationId); |
| 244 | } |
| 245 | this.temporaries.set( |
| 246 | instr.instruction.value.lvalue.place.identifier |
| 247 | .declarationId, |
| 248 | this.temporaries.get( |
| 249 | instr.instruction.value.value.identifier.declarationId, |
| 250 | ) ?? instr.instruction.value.value.identifier.declarationId, |
| 251 | ); |
| 252 | } else { |
| 253 | log( |
| 254 | `Reset scope @${current.block.scope.id} from StoreLocal in [${instr.instruction.id}]`, |
| 255 | ); |
| 256 | reset(); |
| 257 | } |
| 258 | } |
| 259 | break; |
| 260 | } |
| 261 | default: { |
| 262 | // Other instructions are known to prevent merging, so we reset the scope if present |
| 263 | if (current !== null) { |
| 264 | log( |
| 265 | `Reset scope @${current.block.scope.id} from instruction [${instr.instruction.id}]`, |
| 266 | ); |
| 267 | reset(); |
| 268 | } |
| 269 | } |
| 270 | } |
| 271 | break; |
| 272 | } |
| 273 | case 'scope': { |
| 274 | if ( |
| 275 | current !== null && |
| 276 | canMergeScopes(current.block, instr, this.temporaries) && |
| 277 | areLValuesLastUsedByScope( |
| 278 | instr.scope, |
| 279 | current.lvalues, |
| 280 | this.lastUsage, |
| 281 | ) |
| 282 | ) { |
| 283 | // The current and next scopes can merge! |
| 284 | log( |
| 285 | `Can merge scope @${current.block.scope.id} with @${instr.scope.id}`, |
| 286 | ); |
| 287 | // Update the merged scope's range |
| 288 | current.block.scope.range.end = makeInstructionId( |
| 289 | Math.max(current.block.scope.range.end, instr.scope.range.end), |
| 290 | ); |
| 291 | // Add declarations |
| 292 | for (const [key, value] of instr.scope.declarations) { |
| 293 | current.block.scope.declarations.set(key, value); |
| 294 | } |
| 295 | /* |
| 296 | * Then prune declarations - this removes declarations from the earlier |
| 297 | * scope that are last-used at or before the newly merged subsequent scope |
| 298 | */ |
| 299 | updateScopeDeclarations(current.block.scope, this.lastUsage); |
| 300 | current.to = i + 1; |
| 301 | /* |
| 302 | * We already checked that intermediate values were used at-or-before the merged |
| 303 | * scoped, so we can reset |
| 304 | */ |
| 305 | current.lvalues.clear(); |
| 306 | |
| 307 | if (!scopeIsEligibleForMerging(instr)) { |
| 308 | /* |
| 309 | * The subsequent scope that we just merged isn't guaranteed to invalidate if its |
| 310 | * inputs change, so it is not a candidate for future merging |
| 311 | */ |
| 312 | log( |
| 313 | ` but scope @${instr.scope.id} doesnt guaranteed invalidate so it cannot merge further`, |
| 314 | ); |
| 315 | reset(); |
| 316 | } |
| 317 | } else { |
| 318 | // No previous scope, or the scope cannot merge |
| 319 | if (current !== null) { |
| 320 | // Reset if necessary |
| 321 | log( |
| 322 | `Reset scope @${current.block.scope.id}, not mergeable with subsequent scope @${instr.scope.id}`, |
| 323 | ); |
| 324 | reset(); |
| 325 | } |
| 326 | // Only set a new merge candidate if the scope is guaranteed to invalidate on changes |
| 327 | if (scopeIsEligibleForMerging(instr)) { |
| 328 | current = { |
| 329 | block: instr, |
| 330 | from: i, |
| 331 | to: i + 1, |
| 332 | lvalues: new Set(), |
| 333 | }; |
| 334 | } else { |
| 335 | log( |
| 336 | `scope @${instr.scope.id} doesnt guaranteed invalidate so it cannot merge further`, |
| 337 | ); |
| 338 | } |
| 339 | } |
| 340 | break; |
| 341 | } |
| 342 | default: { |
| 343 | assertExhaustive( |
| 344 | instr, |
| 345 | `Unexpected instruction kind \`${(instr as any).kind}\``, |
| 346 | ); |
| 347 | } |
| 348 | } |
| 349 | } |
| 350 | if (current !== null) { |
| 351 | reset(); |
| 352 | } |
| 353 | if (merged.length) { |
| 354 | log(`merged ${merged.length} scopes:`); |
| 355 | for (const entry of merged) { |
| 356 | log( |
| 357 | printReactiveScopeSummary(entry.block.scope) + |
| 358 | ` from=${entry.from} to=${entry.to}`, |
| 359 | ); |
| 360 | } |
| 361 | } |
| 362 | |
| 363 | // Pass 3: optional: if scopes can be merged, merge them and update the block |
| 364 | if (merged.length === 0) { |
| 365 | // Nothing merged, nothing to do! |
| 366 | return; |
| 367 | } |
| 368 | const nextInstructions = []; |
| 369 | let index = 0; |
| 370 | for (const entry of merged) { |
| 371 | if (index < entry.from) { |
| 372 | nextInstructions.push(...block.slice(index, entry.from)); |
| 373 | index = entry.from; |
| 374 | } |
| 375 | const mergedScope = block[entry.from]!; |
| 376 | CompilerError.invariant(mergedScope.kind === 'scope', { |
| 377 | reason: |
| 378 | 'MergeConsecutiveScopes: Expected scope starting index to be a scope', |
| 379 | loc: GeneratedSource, |
| 380 | }); |
| 381 | nextInstructions.push(mergedScope); |
| 382 | index++; |
| 383 | while (index < entry.to) { |
| 384 | const instr = block[index++]!; |
| 385 | if (instr.kind === 'scope') { |
| 386 | mergedScope.instructions.push(...instr.instructions); |
| 387 | mergedScope.scope.merged.add(instr.scope.id); |
| 388 | } else { |
| 389 | mergedScope.instructions.push(instr); |
| 390 | } |
| 391 | } |
| 392 | } |
| 393 | while (index < block.length) { |
| 394 | nextInstructions.push(block[index++]!); |
| 395 | } |
| 396 | block.length = 0; |
| 397 | block.push(...nextInstructions); |
| 398 | } |
| 399 | } |
| 400 | |
| 401 | /* |
| 402 | * Updates @param scope's declarations to remove any declarations that are not |
| 403 | * used after the scope, based on the scope's updated range post-merging. |
| 404 | */ |
| 405 | function updateScopeDeclarations( |
| 406 | scope: ReactiveScope, |
| 407 | lastUsage: Map<DeclarationId, InstructionId>, |
| 408 | ): void { |
| 409 | for (const [id, decl] of scope.declarations) { |
| 410 | const lastUsedAt = lastUsage.get(decl.identifier.declarationId)!; |
| 411 | if (lastUsedAt < scope.range.end) { |
| 412 | scope.declarations.delete(id); |
| 413 | } |
| 414 | } |
| 415 | } |
| 416 | |
| 417 | /* |
| 418 | * Returns whether the given @param scope is the last usage of all |
| 419 | * the given @param lvalues. Returns false if any of the lvalues |
| 420 | * are used again after the scope. |
| 421 | */ |
| 422 | function areLValuesLastUsedByScope( |
| 423 | scope: ReactiveScope, |
| 424 | lvalues: Set<DeclarationId>, |
| 425 | lastUsage: Map<DeclarationId, InstructionId>, |
| 426 | ): boolean { |
| 427 | for (const lvalue of lvalues) { |
| 428 | const lastUsedAt = lastUsage.get(lvalue)!; |
| 429 | if (lastUsedAt >= scope.range.end) { |
| 430 | log(` lvalue ${lvalue} used after scope @${scope.id}, cannot merge`); |
| 431 | return false; |
| 432 | } |
| 433 | } |
| 434 | return true; |
| 435 | } |
| 436 | |
| 437 | function canMergeScopes( |
| 438 | current: ReactiveScopeBlock, |
| 439 | next: ReactiveScopeBlock, |
| 440 | temporaries: Map<DeclarationId, DeclarationId>, |
| 441 | ): boolean { |
| 442 | // Don't merge scopes with reassignments |
| 443 | if ( |
| 444 | current.scope.reassignments.size !== 0 || |
| 445 | next.scope.reassignments.size !== 0 |
| 446 | ) { |
| 447 | log(` cannot merge, has reassignments`); |
| 448 | return false; |
| 449 | } |
| 450 | // Merge scopes whose dependencies are identical |
| 451 | if ( |
| 452 | areEqualDependencies(current.scope.dependencies, next.scope.dependencies) |
| 453 | ) { |
| 454 | log(` canMergeScopes: dependencies are equal`); |
| 455 | return true; |
| 456 | } |
| 457 | /* |
| 458 | * Merge scopes where the outputs of the previous scope are the inputs |
| 459 | * of the subsequent scope. Note that the output of a scope is not |
| 460 | * guaranteed to change when its inputs change, for example `foo(x)` |
| 461 | * may not change when `x` changes, for example `foo(x) { return x < 10}` |
| 462 | * will not change as x changes from 0 -> 1. |
| 463 | * Therefore we check that the outputs of the previous scope are of a type |
| 464 | * that is guaranteed to invalidate with its inputs, and only merge in this case. |
| 465 | */ |
| 466 | if ( |
| 467 | areEqualDependencies( |
| 468 | new Set( |
| 469 | [...current.scope.declarations.values()].map(declaration => ({ |
| 470 | identifier: declaration.identifier, |
| 471 | reactive: true, |
| 472 | path: [], |
| 473 | loc: GeneratedSource, |
| 474 | })), |
| 475 | ), |
| 476 | next.scope.dependencies, |
| 477 | ) || |
| 478 | (next.scope.dependencies.size !== 0 && |
| 479 | [...next.scope.dependencies].every( |
| 480 | dep => |
| 481 | dep.path.length === 0 && |
| 482 | isAlwaysInvalidatingType(dep.identifier.type) && |
| 483 | Iterable_some( |
| 484 | current.scope.declarations.values(), |
| 485 | decl => |
| 486 | decl.identifier.declarationId === dep.identifier.declarationId || |
| 487 | decl.identifier.declarationId === |
| 488 | temporaries.get(dep.identifier.declarationId), |
| 489 | ), |
| 490 | )) |
| 491 | ) { |
| 492 | log(` outputs of prev are input to current`); |
| 493 | return true; |
| 494 | } |
| 495 | log(` cannot merge scopes:`); |
| 496 | log( |
| 497 | ` ${printReactiveScopeSummary(current.scope)} ${[...current.scope.declarations.values()].map(decl => decl.identifier.declarationId)}`, |
| 498 | ); |
| 499 | log( |
| 500 | ` ${printReactiveScopeSummary(next.scope)} ${[...next.scope.dependencies].map(dep => `${dep.identifier.declarationId} ${temporaries.get(dep.identifier.declarationId) ?? dep.identifier.declarationId}`)}`, |
| 501 | ); |
| 502 | return false; |
| 503 | } |
| 504 | |
| 505 | export function isAlwaysInvalidatingType(type: Type): boolean { |
| 506 | switch (type.kind) { |
| 507 | case 'Object': { |
| 508 | switch (type.shapeId) { |
| 509 | case BuiltInArrayId: |
| 510 | case BuiltInObjectId: |
| 511 | case BuiltInFunctionId: |
| 512 | case BuiltInJsxId: { |
| 513 | return true; |
| 514 | } |
| 515 | } |
| 516 | break; |
| 517 | } |
| 518 | case 'Function': { |
| 519 | return true; |
| 520 | } |
| 521 | } |
| 522 | return false; |
| 523 | } |
| 524 | |
| 525 | function areEqualDependencies( |
| 526 | a: Set<ReactiveScopeDependency>, |
| 527 | b: Set<ReactiveScopeDependency>, |
| 528 | ): boolean { |
| 529 | if (a.size !== b.size) { |
| 530 | return false; |
| 531 | } |
| 532 | for (const aValue of a) { |
| 533 | let found = false; |
| 534 | for (const bValue of b) { |
| 535 | if ( |
| 536 | aValue.identifier.declarationId === bValue.identifier.declarationId && |
| 537 | areEqualPaths(aValue.path, bValue.path) |
| 538 | ) { |
| 539 | found = true; |
| 540 | break; |
| 541 | } |
| 542 | } |
| 543 | if (!found) { |
| 544 | return false; |
| 545 | } |
| 546 | } |
| 547 | return true; |
| 548 | } |
| 549 | |
| 550 | /** |
| 551 | * Is this scope eligible for merging with subsequent scopes? In general this |
| 552 | * is only true if the scope's output values are guaranteed to change when its |
| 553 | * input changes. When the output may not change, it's better to avoid merging |
| 554 | * with subsequent scopes so that they can compare the input and avoid updating |
| 555 | * when there are no changes. |
| 556 | * |
| 557 | * A special-case is if the scope has no dependencies, then its output will |
| 558 | * *never* change and it's also eligible for merging. |
| 559 | */ |
| 560 | function scopeIsEligibleForMerging(scopeBlock: ReactiveScopeBlock): boolean { |
| 561 | if (scopeBlock.scope.dependencies.size === 0) { |
| 562 | /* |
| 563 | * Regardless of the type of value produced, if the scope has no dependencies |
| 564 | * then its value will never change. |
| 565 | */ |
| 566 | return true; |
| 567 | } |
| 568 | return [...scopeBlock.scope.declarations].some(([, decl]) => |
| 569 | isAlwaysInvalidatingType(decl.identifier.type), |
| 570 | ); |
| 571 | } |