| 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 '../CompilerError'; |
| 9 | import {inRange} from '../ReactiveScopes/InferReactiveScopeVariables'; |
| 10 | import {printDependency} from '../ReactiveScopes/PrintReactiveFunction'; |
| 11 | import { |
| 12 | Set_equal, |
| 13 | Set_filter, |
| 14 | Set_intersect, |
| 15 | Set_union, |
| 16 | getOrInsertDefault, |
| 17 | } from '../Utils/utils'; |
| 18 | import { |
| 19 | BasicBlock, |
| 20 | BlockId, |
| 21 | DependencyPathEntry, |
| 22 | FunctionExpression, |
| 23 | GeneratedSource, |
| 24 | getHookKind, |
| 25 | HIRFunction, |
| 26 | Identifier, |
| 27 | IdentifierId, |
| 28 | InstructionId, |
| 29 | InstructionValue, |
| 30 | LoweredFunction, |
| 31 | PropertyLiteral, |
| 32 | ReactiveScopeDependency, |
| 33 | ScopeId, |
| 34 | SourceLocation, |
| 35 | TInstruction, |
| 36 | } from './HIR'; |
| 37 | |
| 38 | const DEBUG_PRINT = false; |
| 39 | |
| 40 | /** |
| 41 | * Helper function for `PropagateScopeDependencies`. Uses control flow graph |
| 42 | * analysis to determine which `Identifier`s can be assumed to be non-null |
| 43 | * objects, on a per-block basis. |
| 44 | * |
| 45 | * Here is an example: |
| 46 | * ```js |
| 47 | * function useFoo(x, y, z) { |
| 48 | * // NOT safe to hoist PropertyLoads here |
| 49 | * if (...) { |
| 50 | * // safe to hoist loads from x |
| 51 | * read(x.a); |
| 52 | * return; |
| 53 | * } |
| 54 | * // safe to hoist loads from y, z |
| 55 | * read(y.b); |
| 56 | * if (...) { |
| 57 | * // safe to hoist loads from y, z |
| 58 | * read(z.a); |
| 59 | * } else { |
| 60 | * // safe to hoist loads from y, z |
| 61 | * read(z.b); |
| 62 | * } |
| 63 | * // safe to hoist loads from y, z |
| 64 | * return; |
| 65 | * } |
| 66 | * ``` |
| 67 | * |
| 68 | * Note that we currently do NOT account for mutable / declaration range when |
| 69 | * doing the CFG-based traversal, producing results that are technically |
| 70 | * incorrect but filtered by PropagateScopeDeps (which only takes dependencies |
| 71 | * on constructed value -- i.e. a scope's dependencies must have mutable ranges |
| 72 | * ending earlier than the scope start). |
| 73 | * |
| 74 | * Take this example, this function will infer x.foo.bar as non-nullable for |
| 75 | * bb0, via the intersection of bb1 & bb2 which in turn comes from bb3. This is |
| 76 | * technically incorrect bb0 is before / during x's mutable range. |
| 77 | * ``` |
| 78 | * bb0: |
| 79 | * const x = ...; |
| 80 | * if cond then bb1 else bb2 |
| 81 | * bb1: |
| 82 | * ... |
| 83 | * goto bb3 |
| 84 | * bb2: |
| 85 | * ... |
| 86 | * goto bb3: |
| 87 | * bb3: |
| 88 | * x.foo.bar |
| 89 | * ``` |
| 90 | * |
| 91 | * @param fn |
| 92 | * @param temporaries sidemap of identifier -> baseObject.a.b paths. Does not |
| 93 | * contain optional chains. |
| 94 | * @param hoistableFromOptionals sidemap of optionalBlock -> baseObject?.a |
| 95 | * optional paths for which it's safe to evaluate non-optional loads (see |
| 96 | * CollectOptionalChainDependencies). |
| 97 | * @returns |
| 98 | */ |
| 99 | export function collectHoistablePropertyLoads( |
| 100 | fn: HIRFunction, |
| 101 | temporaries: ReadonlyMap<IdentifierId, ReactiveScopeDependency>, |
| 102 | hoistableFromOptionals: ReadonlyMap<BlockId, ReactiveScopeDependency>, |
| 103 | ): ReadonlyMap<BlockId, BlockInfo> { |
| 104 | const registry = new PropertyPathRegistry(); |
| 105 | /** |
| 106 | * Due to current limitations of mutable range inference, there are edge cases in |
| 107 | * which we infer known-immutable values (e.g. props or hook params) to have a |
| 108 | * mutable range and scope. |
| 109 | * (see `destructure-array-declaration-to-context-var` fixture) |
| 110 | * We track known immutable identifiers to reduce regressions (as PropagateScopeDeps |
| 111 | * is being rewritten to HIR). |
| 112 | */ |
| 113 | const knownImmutableIdentifiers = new Set<IdentifierId>(); |
| 114 | if (fn.fnType === 'Component' || fn.fnType === 'Hook') { |
| 115 | for (const p of fn.params) { |
| 116 | if (p.kind === 'Identifier') { |
| 117 | knownImmutableIdentifiers.add(p.identifier.id); |
| 118 | } |
| 119 | } |
| 120 | } |
| 121 | return collectHoistablePropertyLoadsImpl(fn, { |
| 122 | temporaries, |
| 123 | knownImmutableIdentifiers, |
| 124 | hoistableFromOptionals, |
| 125 | registry, |
| 126 | nestedFnImmutableContext: null, |
| 127 | assumedInvokedFns: getAssumedInvokedFunctions(fn), |
| 128 | }); |
| 129 | } |
| 130 | |
| 131 | export function collectHoistablePropertyLoadsInInnerFn( |
| 132 | fnInstr: TInstruction<FunctionExpression>, |
| 133 | temporaries: ReadonlyMap<IdentifierId, ReactiveScopeDependency>, |
| 134 | hoistableFromOptionals: ReadonlyMap<BlockId, ReactiveScopeDependency>, |
| 135 | ): ReadonlyMap<BlockId, BlockInfo> { |
| 136 | const fn = fnInstr.value.loweredFunc.func; |
| 137 | const initialContext: CollectHoistablePropertyLoadsContext = { |
| 138 | temporaries, |
| 139 | knownImmutableIdentifiers: new Set(), |
| 140 | hoistableFromOptionals, |
| 141 | registry: new PropertyPathRegistry(), |
| 142 | nestedFnImmutableContext: null, |
| 143 | assumedInvokedFns: getAssumedInvokedFunctions(fn), |
| 144 | }; |
| 145 | const nestedFnImmutableContext = new Set( |
| 146 | fn.context |
| 147 | .filter(place => |
| 148 | isImmutableAtInstr(place.identifier, fnInstr.id, initialContext), |
| 149 | ) |
| 150 | .map(place => place.identifier.id), |
| 151 | ); |
| 152 | initialContext.nestedFnImmutableContext = nestedFnImmutableContext; |
| 153 | return collectHoistablePropertyLoadsImpl(fn, initialContext); |
| 154 | } |
| 155 | |
| 156 | type CollectHoistablePropertyLoadsContext = { |
| 157 | temporaries: ReadonlyMap<IdentifierId, ReactiveScopeDependency>; |
| 158 | knownImmutableIdentifiers: ReadonlySet<IdentifierId>; |
| 159 | hoistableFromOptionals: ReadonlyMap<BlockId, ReactiveScopeDependency>; |
| 160 | registry: PropertyPathRegistry; |
| 161 | /** |
| 162 | * (For nested / inner function declarations) |
| 163 | * Context variables (i.e. captured from an outer scope) that are immutable. |
| 164 | * Note that this technically could be merged into `knownImmutableIdentifiers`, |
| 165 | * but are currently kept separate for readability. |
| 166 | */ |
| 167 | nestedFnImmutableContext: ReadonlySet<IdentifierId> | null; |
| 168 | /** |
| 169 | * Functions which are assumed to be eventually called (as opposed to ones which might |
| 170 | * not be called, e.g. the 0th argument of Array.map) |
| 171 | */ |
| 172 | assumedInvokedFns: ReadonlySet<LoweredFunction>; |
| 173 | }; |
| 174 | function collectHoistablePropertyLoadsImpl( |
| 175 | fn: HIRFunction, |
| 176 | context: CollectHoistablePropertyLoadsContext, |
| 177 | ): ReadonlyMap<BlockId, BlockInfo> { |
| 178 | const nodes = collectNonNullsInBlocks(fn, context); |
| 179 | propagateNonNull(fn, nodes, context.registry); |
| 180 | |
| 181 | if (DEBUG_PRINT) { |
| 182 | console.log('(printing hoistable nodes in blocks)'); |
| 183 | for (const [blockId, node] of nodes) { |
| 184 | console.log( |
| 185 | `bb${blockId}: ${[...node.assumedNonNullObjects].map(n => printDependency(n.fullPath)).join(' ')}`, |
| 186 | ); |
| 187 | } |
| 188 | } |
| 189 | |
| 190 | return nodes; |
| 191 | } |
| 192 | |
| 193 | export function keyByScopeId<T>( |
| 194 | fn: HIRFunction, |
| 195 | source: ReadonlyMap<BlockId, T>, |
| 196 | ): ReadonlyMap<ScopeId, T> { |
| 197 | const keyedByScopeId = new Map<ScopeId, T>(); |
| 198 | for (const [_, block] of fn.body.blocks) { |
| 199 | if (block.terminal.kind === 'scope') { |
| 200 | keyedByScopeId.set( |
| 201 | block.terminal.scope.id, |
| 202 | source.get(block.terminal.block)!, |
| 203 | ); |
| 204 | } |
| 205 | } |
| 206 | return keyedByScopeId; |
| 207 | } |
| 208 | |
| 209 | export type BlockInfo = { |
| 210 | block: BasicBlock; |
| 211 | assumedNonNullObjects: ReadonlySet<PropertyPathNode>; |
| 212 | }; |
| 213 | |
| 214 | /** |
| 215 | * PropertyLoadRegistry data structure to dedupe property loads (e.g. a.b.c) |
| 216 | * and make computing sets intersections simpler. |
| 217 | */ |
| 218 | type RootNode = { |
| 219 | properties: Map<PropertyLiteral, PropertyPathNode>; |
| 220 | optionalProperties: Map<PropertyLiteral, PropertyPathNode>; |
| 221 | parent: null; |
| 222 | // Recorded to make later computations simpler |
| 223 | fullPath: ReactiveScopeDependency; |
| 224 | hasOptional: boolean; |
| 225 | root: IdentifierId; |
| 226 | }; |
| 227 | |
| 228 | type PropertyPathNode = |
| 229 | | { |
| 230 | properties: Map<PropertyLiteral, PropertyPathNode>; |
| 231 | optionalProperties: Map<PropertyLiteral, PropertyPathNode>; |
| 232 | parent: PropertyPathNode; |
| 233 | fullPath: ReactiveScopeDependency; |
| 234 | hasOptional: boolean; |
| 235 | } |
| 236 | | RootNode; |
| 237 | |
| 238 | class PropertyPathRegistry { |
| 239 | roots: Map<IdentifierId, RootNode> = new Map(); |
| 240 | |
| 241 | getOrCreateIdentifier( |
| 242 | identifier: Identifier, |
| 243 | reactive: boolean, |
| 244 | loc: SourceLocation, |
| 245 | ): PropertyPathNode { |
| 246 | /** |
| 247 | * Reads from a statically scoped variable are always safe in JS, |
| 248 | * with the exception of TDZ (not addressed by this pass). |
| 249 | */ |
| 250 | let rootNode = this.roots.get(identifier.id); |
| 251 | |
| 252 | if (rootNode === undefined) { |
| 253 | rootNode = { |
| 254 | root: identifier.id, |
| 255 | properties: new Map(), |
| 256 | optionalProperties: new Map(), |
| 257 | fullPath: { |
| 258 | identifier, |
| 259 | reactive, |
| 260 | path: [], |
| 261 | loc, |
| 262 | }, |
| 263 | hasOptional: false, |
| 264 | parent: null, |
| 265 | }; |
| 266 | this.roots.set(identifier.id, rootNode); |
| 267 | } else { |
| 268 | CompilerError.invariant(reactive === rootNode.fullPath.reactive, { |
| 269 | reason: |
| 270 | '[HoistablePropertyLoads] Found inconsistencies in `reactive` flag when deduping identifier reads within the same scope', |
| 271 | loc: identifier.loc, |
| 272 | }); |
| 273 | } |
| 274 | return rootNode; |
| 275 | } |
| 276 | |
| 277 | static getOrCreatePropertyEntry( |
| 278 | parent: PropertyPathNode, |
| 279 | entry: DependencyPathEntry, |
| 280 | ): PropertyPathNode { |
| 281 | const map = entry.optional ? parent.optionalProperties : parent.properties; |
| 282 | let child = map.get(entry.property); |
| 283 | if (child == null) { |
| 284 | child = { |
| 285 | properties: new Map(), |
| 286 | optionalProperties: new Map(), |
| 287 | parent: parent, |
| 288 | fullPath: { |
| 289 | identifier: parent.fullPath.identifier, |
| 290 | reactive: parent.fullPath.reactive, |
| 291 | path: parent.fullPath.path.concat(entry), |
| 292 | loc: entry.loc, |
| 293 | }, |
| 294 | hasOptional: parent.hasOptional || entry.optional, |
| 295 | }; |
| 296 | map.set(entry.property, child); |
| 297 | } |
| 298 | return child; |
| 299 | } |
| 300 | |
| 301 | getOrCreateProperty(n: ReactiveScopeDependency): PropertyPathNode { |
| 302 | /** |
| 303 | * We add ReactiveScopeDependencies according to instruction ordering, |
| 304 | * so all subpaths of a PropertyLoad should already exist |
| 305 | * (e.g. a.b is added before a.b.c), |
| 306 | */ |
| 307 | let currNode = this.getOrCreateIdentifier(n.identifier, n.reactive, n.loc); |
| 308 | if (n.path.length === 0) { |
| 309 | return currNode; |
| 310 | } |
| 311 | for (let i = 0; i < n.path.length - 1; i++) { |
| 312 | currNode = PropertyPathRegistry.getOrCreatePropertyEntry( |
| 313 | currNode, |
| 314 | n.path[i], |
| 315 | ); |
| 316 | } |
| 317 | |
| 318 | return PropertyPathRegistry.getOrCreatePropertyEntry( |
| 319 | currNode, |
| 320 | n.path.at(-1)!, |
| 321 | ); |
| 322 | } |
| 323 | } |
| 324 | |
| 325 | function getMaybeNonNullInInstruction( |
| 326 | value: InstructionValue, |
| 327 | context: CollectHoistablePropertyLoadsContext, |
| 328 | ): PropertyPathNode | null { |
| 329 | let path: ReactiveScopeDependency | null = null; |
| 330 | if (value.kind === 'PropertyLoad') { |
| 331 | path = context.temporaries.get(value.object.identifier.id) ?? { |
| 332 | identifier: value.object.identifier, |
| 333 | reactive: value.object.reactive, |
| 334 | path: [], |
| 335 | loc: value.loc, |
| 336 | }; |
| 337 | } else if (value.kind === 'Destructure') { |
| 338 | path = context.temporaries.get(value.value.identifier.id) ?? null; |
| 339 | } else if (value.kind === 'ComputedLoad') { |
| 340 | path = context.temporaries.get(value.object.identifier.id) ?? null; |
| 341 | } |
| 342 | return path != null ? context.registry.getOrCreateProperty(path) : null; |
| 343 | } |
| 344 | |
| 345 | function isImmutableAtInstr( |
| 346 | identifier: Identifier, |
| 347 | instr: InstructionId, |
| 348 | context: CollectHoistablePropertyLoadsContext, |
| 349 | ): boolean { |
| 350 | if (context.nestedFnImmutableContext != null) { |
| 351 | /** |
| 352 | * Comparing instructions ids across inner-outer function bodies is not valid, as they are numbered |
| 353 | */ |
| 354 | return context.nestedFnImmutableContext.has(identifier.id); |
| 355 | } else { |
| 356 | /** |
| 357 | * Since this runs *after* buildReactiveScopeTerminals, identifier mutable ranges |
| 358 | * are not valid with respect to current instruction id numbering. |
| 359 | * We use attached reactive scope ranges as a proxy for mutable range, but this |
| 360 | * is an overestimate as (1) scope ranges merge and align to form valid program |
| 361 | * blocks and (2) passes like MemoizeFbtAndMacroOperands may assign scopes to |
| 362 | * non-mutable identifiers. |
| 363 | * |
| 364 | * See comment in exported function for why we track known immutable identifiers. |
| 365 | */ |
| 366 | const mutableAtInstr = |
| 367 | identifier.mutableRange.end > identifier.mutableRange.start + 1 && |
| 368 | identifier.scope != null && |
| 369 | inRange( |
| 370 | { |
| 371 | id: instr, |
| 372 | }, |
| 373 | identifier.scope.range, |
| 374 | ); |
| 375 | return ( |
| 376 | !mutableAtInstr || context.knownImmutableIdentifiers.has(identifier.id) |
| 377 | ); |
| 378 | } |
| 379 | } |
| 380 | |
| 381 | function collectNonNullsInBlocks( |
| 382 | fn: HIRFunction, |
| 383 | context: CollectHoistablePropertyLoadsContext, |
| 384 | ): ReadonlyMap<BlockId, BlockInfo> { |
| 385 | /** |
| 386 | * Known non-null objects such as functional component props can be safely |
| 387 | * read from any block. |
| 388 | */ |
| 389 | const knownNonNullIdentifiers = new Set<PropertyPathNode>(); |
| 390 | if ( |
| 391 | fn.fnType === 'Component' && |
| 392 | fn.params.length > 0 && |
| 393 | fn.params[0].kind === 'Identifier' |
| 394 | ) { |
| 395 | const identifier = fn.params[0].identifier; |
| 396 | knownNonNullIdentifiers.add( |
| 397 | context.registry.getOrCreateIdentifier( |
| 398 | identifier, |
| 399 | true, |
| 400 | fn.params[0].loc, |
| 401 | ), |
| 402 | ); |
| 403 | } |
| 404 | const nodes = new Map< |
| 405 | BlockId, |
| 406 | { |
| 407 | block: BasicBlock; |
| 408 | assumedNonNullObjects: Set<PropertyPathNode>; |
| 409 | } |
| 410 | >(); |
| 411 | for (const [_, block] of fn.body.blocks) { |
| 412 | const assumedNonNullObjects = new Set<PropertyPathNode>( |
| 413 | knownNonNullIdentifiers, |
| 414 | ); |
| 415 | |
| 416 | const maybeOptionalChain = context.hoistableFromOptionals.get(block.id); |
| 417 | if (maybeOptionalChain != null) { |
| 418 | assumedNonNullObjects.add( |
| 419 | context.registry.getOrCreateProperty(maybeOptionalChain), |
| 420 | ); |
| 421 | } |
| 422 | for (const instr of block.instructions) { |
| 423 | const maybeNonNull = getMaybeNonNullInInstruction(instr.value, context); |
| 424 | if ( |
| 425 | maybeNonNull != null && |
| 426 | isImmutableAtInstr(maybeNonNull.fullPath.identifier, instr.id, context) |
| 427 | ) { |
| 428 | assumedNonNullObjects.add(maybeNonNull); |
| 429 | } |
| 430 | if (instr.value.kind === 'FunctionExpression') { |
| 431 | const innerFn = instr.value.loweredFunc; |
| 432 | if (context.assumedInvokedFns.has(innerFn)) { |
| 433 | const innerHoistableMap = collectHoistablePropertyLoadsImpl( |
| 434 | innerFn.func, |
| 435 | { |
| 436 | ...context, |
| 437 | nestedFnImmutableContext: |
| 438 | context.nestedFnImmutableContext ?? |
| 439 | new Set( |
| 440 | innerFn.func.context |
| 441 | .filter(place => |
| 442 | isImmutableAtInstr(place.identifier, instr.id, context), |
| 443 | ) |
| 444 | .map(place => place.identifier.id), |
| 445 | ), |
| 446 | }, |
| 447 | ); |
| 448 | const innerHoistables = assertNonNull( |
| 449 | innerHoistableMap.get(innerFn.func.body.entry), |
| 450 | ); |
| 451 | for (const entry of innerHoistables.assumedNonNullObjects) { |
| 452 | assumedNonNullObjects.add(entry); |
| 453 | } |
| 454 | } |
| 455 | } else if ( |
| 456 | fn.env.config.enablePreserveExistingMemoizationGuarantees && |
| 457 | instr.value.kind === 'StartMemoize' && |
| 458 | instr.value.deps != null |
| 459 | ) { |
| 460 | for (const dep of instr.value.deps) { |
| 461 | if (dep.root.kind === 'NamedLocal') { |
| 462 | if ( |
| 463 | !isImmutableAtInstr(dep.root.value.identifier, instr.id, context) |
| 464 | ) { |
| 465 | continue; |
| 466 | } |
| 467 | for (let i = 0; i < dep.path.length; i++) { |
| 468 | const pathEntry = dep.path[i]!; |
| 469 | if (pathEntry.optional) { |
| 470 | break; |
| 471 | } |
| 472 | const depNode = context.registry.getOrCreateProperty({ |
| 473 | identifier: dep.root.value.identifier, |
| 474 | path: dep.path.slice(0, i), |
| 475 | reactive: dep.root.value.reactive, |
| 476 | loc: dep.loc, |
| 477 | }); |
| 478 | assumedNonNullObjects.add(depNode); |
| 479 | } |
| 480 | } |
| 481 | } |
| 482 | } |
| 483 | } |
| 484 | |
| 485 | nodes.set(block.id, { |
| 486 | block, |
| 487 | assumedNonNullObjects, |
| 488 | }); |
| 489 | } |
| 490 | return nodes; |
| 491 | } |
| 492 | |
| 493 | function propagateNonNull( |
| 494 | fn: HIRFunction, |
| 495 | nodes: ReadonlyMap<BlockId, BlockInfo>, |
| 496 | registry: PropertyPathRegistry, |
| 497 | ): void { |
| 498 | const blockSuccessors = new Map<BlockId, Set<BlockId>>(); |
| 499 | const terminalPreds = new Set<BlockId>(); |
| 500 | |
| 501 | for (const [blockId, block] of fn.body.blocks) { |
| 502 | for (const pred of block.preds) { |
| 503 | getOrInsertDefault(blockSuccessors, pred, new Set()).add(blockId); |
| 504 | } |
| 505 | if (block.terminal.kind === 'throw' || block.terminal.kind === 'return') { |
| 506 | terminalPreds.add(blockId); |
| 507 | } |
| 508 | } |
| 509 | |
| 510 | /** |
| 511 | * In the context of a control flow graph, the identifiers that a block |
| 512 | * can assume are non-null can be calculated from the following: |
| 513 | * X = Union(Intersect(X_neighbors), X) |
| 514 | */ |
| 515 | function recursivelyPropagateNonNull( |
| 516 | nodeId: BlockId, |
| 517 | direction: 'forward' | 'backward', |
| 518 | traversalState: Map<BlockId, 'active' | 'done'>, |
| 519 | ): boolean { |
| 520 | /** |
| 521 | * Avoid re-visiting computed or currently active nodes, which can |
| 522 | * occur when the control flow graph has backedges. |
| 523 | */ |
| 524 | if (traversalState.has(nodeId)) { |
| 525 | return false; |
| 526 | } |
| 527 | traversalState.set(nodeId, 'active'); |
| 528 | |
| 529 | const node = nodes.get(nodeId); |
| 530 | if (node == null) { |
| 531 | CompilerError.invariant(false, { |
| 532 | reason: `Bad node ${nodeId}, kind: ${direction}`, |
| 533 | loc: GeneratedSource, |
| 534 | }); |
| 535 | } |
| 536 | const neighbors = Array.from( |
| 537 | direction === 'backward' |
| 538 | ? (blockSuccessors.get(nodeId) ?? []) |
| 539 | : node.block.preds, |
| 540 | ); |
| 541 | |
| 542 | let changed = false; |
| 543 | for (const pred of neighbors) { |
| 544 | if (!traversalState.has(pred)) { |
| 545 | const neighborChanged = recursivelyPropagateNonNull( |
| 546 | pred, |
| 547 | direction, |
| 548 | traversalState, |
| 549 | ); |
| 550 | changed ||= neighborChanged; |
| 551 | } |
| 552 | } |
| 553 | /** |
| 554 | * Note that a predecessor / successor can only be active (status != 'done') |
| 555 | * if it is a self-loop or other transitive cycle. Active neighbors can be |
| 556 | * filtered out (i.e. not included in the intersection) |
| 557 | * Example: self loop. |
| 558 | * X = Union(Intersect(X, ...X_other_neighbors), X) |
| 559 | * |
| 560 | * Example: transitive cycle through node Y, for some Y that is a |
| 561 | * predecessor / successor of X. |
| 562 | * X = Union( |
| 563 | * Intersect( |
| 564 | * Union(Intersect(X, ...Y_other_neighbors), Y), |
| 565 | * ...X_neighbors |
| 566 | * ), |
| 567 | * X |
| 568 | * ) |
| 569 | * |
| 570 | * Non-active neighbors with no recorded results can occur due to backedges. |
| 571 | * it's not safe to assume they can be filtered out (e.g. not included in |
| 572 | * the intersection) |
| 573 | */ |
| 574 | const neighborAccesses = Set_intersect( |
| 575 | Array.from(neighbors) |
| 576 | .filter(n => traversalState.get(n) === 'done') |
| 577 | .map(n => assertNonNull(nodes.get(n)).assumedNonNullObjects), |
| 578 | ); |
| 579 | |
| 580 | const prevObjects = assertNonNull(nodes.get(nodeId)).assumedNonNullObjects; |
| 581 | const mergedObjects = Set_union(prevObjects, neighborAccesses); |
| 582 | reduceMaybeOptionalChains(mergedObjects, registry); |
| 583 | |
| 584 | assertNonNull(nodes.get(nodeId)).assumedNonNullObjects = mergedObjects; |
| 585 | traversalState.set(nodeId, 'done'); |
| 586 | /** |
| 587 | * Note that it's not sufficient to compare set sizes since |
| 588 | * reduceMaybeOptionalChains may replace optional-chain loads with |
| 589 | * unconditional loads. This could in turn change `assumedNonNullObjects` of |
| 590 | * downstream blocks and backedges. |
| 591 | */ |
| 592 | changed ||= !Set_equal(prevObjects, mergedObjects); |
| 593 | return changed; |
| 594 | } |
| 595 | const traversalState = new Map<BlockId, 'done' | 'active'>(); |
| 596 | const reversedBlocks = [...fn.body.blocks]; |
| 597 | reversedBlocks.reverse(); |
| 598 | |
| 599 | let changed; |
| 600 | let i = 0; |
| 601 | do { |
| 602 | CompilerError.invariant(i++ < 100, { |
| 603 | reason: |
| 604 | '[CollectHoistablePropertyLoads] fixed point iteration did not terminate after 100 loops', |
| 605 | loc: GeneratedSource, |
| 606 | }); |
| 607 | |
| 608 | changed = false; |
| 609 | for (const [blockId] of fn.body.blocks) { |
| 610 | const forwardChanged = recursivelyPropagateNonNull( |
| 611 | blockId, |
| 612 | 'forward', |
| 613 | traversalState, |
| 614 | ); |
| 615 | changed ||= forwardChanged; |
| 616 | } |
| 617 | traversalState.clear(); |
| 618 | for (const [blockId] of reversedBlocks) { |
| 619 | const backwardChanged = recursivelyPropagateNonNull( |
| 620 | blockId, |
| 621 | 'backward', |
| 622 | traversalState, |
| 623 | ); |
| 624 | changed ||= backwardChanged; |
| 625 | } |
| 626 | traversalState.clear(); |
| 627 | } while (changed); |
| 628 | } |
| 629 | |
| 630 | export function assertNonNull<T extends NonNullable<U>, U>( |
| 631 | value: T | null | undefined, |
| 632 | source?: string, |
| 633 | ): T { |
| 634 | CompilerError.invariant(value != null, { |
| 635 | reason: 'Unexpected null', |
| 636 | description: source != null ? `(from ${source})` : null, |
| 637 | loc: GeneratedSource, |
| 638 | }); |
| 639 | return value; |
| 640 | } |
| 641 | |
| 642 | /** |
| 643 | * Any two optional chains with different operations . vs ?. but the same set of |
| 644 | * property strings paths de-duplicates. |
| 645 | * |
| 646 | * Intuitively: given <base>?.b, we know <base> to be either hoistable or not. |
| 647 | * If unconditional reads from <base> are hoistable, we can replace all |
| 648 | * <base>?.PROPERTY_STRING subpaths with <base>.PROPERTY_STRING |
| 649 | */ |
| 650 | function reduceMaybeOptionalChains( |
| 651 | nodes: Set<PropertyPathNode>, |
| 652 | registry: PropertyPathRegistry, |
| 653 | ): void { |
| 654 | let optionalChainNodes = Set_filter(nodes, n => n.hasOptional); |
| 655 | if (optionalChainNodes.size === 0) { |
| 656 | return; |
| 657 | } |
| 658 | let changed: boolean; |
| 659 | do { |
| 660 | changed = false; |
| 661 | |
| 662 | for (const original of optionalChainNodes) { |
| 663 | let { |
| 664 | identifier, |
| 665 | path: origPath, |
| 666 | reactive, |
| 667 | loc: origLoc, |
| 668 | } = original.fullPath; |
| 669 | let currNode: PropertyPathNode = registry.getOrCreateIdentifier( |
| 670 | identifier, |
| 671 | reactive, |
| 672 | origLoc, |
| 673 | ); |
| 674 | for (let i = 0; i < origPath.length; i++) { |
| 675 | const entry = origPath[i]; |
| 676 | // If the base is known to be non-null, replace with a non-optional load |
| 677 | const nextEntry: DependencyPathEntry = |
| 678 | entry.optional && nodes.has(currNode) |
| 679 | ? {property: entry.property, optional: false, loc: entry.loc} |
| 680 | : entry; |
| 681 | currNode = PropertyPathRegistry.getOrCreatePropertyEntry( |
| 682 | currNode, |
| 683 | nextEntry, |
| 684 | ); |
| 685 | } |
| 686 | if (currNode !== original) { |
| 687 | changed = true; |
| 688 | optionalChainNodes.delete(original); |
| 689 | optionalChainNodes.add(currNode); |
| 690 | nodes.delete(original); |
| 691 | nodes.add(currNode); |
| 692 | } |
| 693 | } |
| 694 | } while (changed); |
| 695 | } |
| 696 | |
| 697 | function getAssumedInvokedFunctions( |
| 698 | fn: HIRFunction, |
| 699 | temporaries: Map< |
| 700 | IdentifierId, |
| 701 | {fn: LoweredFunction; mayInvoke: Set<LoweredFunction>} |
| 702 | > = new Map(), |
| 703 | ): ReadonlySet<LoweredFunction> { |
| 704 | const hoistableFunctions = new Set<LoweredFunction>(); |
| 705 | /** |
| 706 | * Step 1: Conservatively collect identifier to function expression mappings |
| 707 | */ |
| 708 | for (const block of fn.body.blocks.values()) { |
| 709 | for (const {lvalue, value} of block.instructions) { |
| 710 | /** |
| 711 | * Conservatively only match function expressions which can have guaranteed ssa. |
| 712 | * ObjectMethods and ObjectProperties do not. |
| 713 | */ |
| 714 | if (value.kind === 'FunctionExpression') { |
| 715 | temporaries.set(lvalue.identifier.id, { |
| 716 | fn: value.loweredFunc, |
| 717 | mayInvoke: new Set(), |
| 718 | }); |
| 719 | } else if (value.kind === 'StoreLocal') { |
| 720 | const lvalue = value.lvalue.place.identifier; |
| 721 | const maybeLoweredFunc = temporaries.get(value.value.identifier.id); |
| 722 | if (maybeLoweredFunc != null) { |
| 723 | temporaries.set(lvalue.id, maybeLoweredFunc); |
| 724 | } |
| 725 | } else if (value.kind === 'LoadLocal') { |
| 726 | const maybeLoweredFunc = temporaries.get(value.place.identifier.id); |
| 727 | if (maybeLoweredFunc != null) { |
| 728 | temporaries.set(lvalue.identifier.id, maybeLoweredFunc); |
| 729 | } |
| 730 | } |
| 731 | } |
| 732 | } |
| 733 | /** |
| 734 | * Step 2: Forward pass to do analysis of assumed function calls. Note that |
| 735 | * this is conservative and does not count indirect references through |
| 736 | * containers (e.g. `return {cb: () => {...}})`). |
| 737 | */ |
| 738 | for (const block of fn.body.blocks.values()) { |
| 739 | for (const {lvalue, value} of block.instructions) { |
| 740 | if (value.kind === 'CallExpression') { |
| 741 | const callee = value.callee; |
| 742 | const maybeHook = getHookKind(fn.env, callee.identifier); |
| 743 | const maybeLoweredFunc = temporaries.get(callee.identifier.id); |
| 744 | if (maybeLoweredFunc != null) { |
| 745 | // Direct calls |
| 746 | hoistableFunctions.add(maybeLoweredFunc.fn); |
| 747 | } else if (maybeHook != null) { |
| 748 | /** |
| 749 | * Assume arguments to all hooks are safe to invoke |
| 750 | */ |
| 751 | for (const arg of value.args) { |
| 752 | if (arg.kind === 'Identifier') { |
| 753 | const maybeLoweredFunc = temporaries.get(arg.identifier.id); |
| 754 | if (maybeLoweredFunc != null) { |
| 755 | hoistableFunctions.add(maybeLoweredFunc.fn); |
| 756 | } |
| 757 | } |
| 758 | } |
| 759 | } |
| 760 | } else if (value.kind === 'JsxExpression') { |
| 761 | /** |
| 762 | * Assume JSX attributes and children are safe to invoke |
| 763 | */ |
| 764 | for (const attr of value.props) { |
| 765 | if (attr.kind === 'JsxSpreadAttribute') { |
| 766 | continue; |
| 767 | } |
| 768 | const maybeLoweredFunc = temporaries.get(attr.place.identifier.id); |
| 769 | if (maybeLoweredFunc != null) { |
| 770 | hoistableFunctions.add(maybeLoweredFunc.fn); |
| 771 | } |
| 772 | } |
| 773 | for (const child of value.children ?? []) { |
| 774 | const maybeLoweredFunc = temporaries.get(child.identifier.id); |
| 775 | if (maybeLoweredFunc != null) { |
| 776 | hoistableFunctions.add(maybeLoweredFunc.fn); |
| 777 | } |
| 778 | } |
| 779 | } else if (value.kind === 'FunctionExpression') { |
| 780 | /** |
| 781 | * Recursively traverse into other function expressions which may invoke |
| 782 | * or pass already declared functions to react (e.g. as JSXAttributes). |
| 783 | * |
| 784 | * If lambda A calls lambda B, we assume lambda B is safe to invoke if |
| 785 | * lambda A is -- even if lambda B is conditionally called. (see |
| 786 | * `conditional-call-chain` fixture for example). |
| 787 | */ |
| 788 | const loweredFunc = value.loweredFunc.func; |
| 789 | const lambdasCalled = getAssumedInvokedFunctions( |
| 790 | loweredFunc, |
| 791 | temporaries, |
| 792 | ); |
| 793 | const maybeLoweredFunc = temporaries.get(lvalue.identifier.id); |
| 794 | if (maybeLoweredFunc != null) { |
| 795 | for (const called of lambdasCalled) { |
| 796 | maybeLoweredFunc.mayInvoke.add(called); |
| 797 | } |
| 798 | } |
| 799 | } |
| 800 | } |
| 801 | if (block.terminal.kind === 'return') { |
| 802 | /** |
| 803 | * Assume directly returned functions are safe to call |
| 804 | */ |
| 805 | const maybeLoweredFunc = temporaries.get( |
| 806 | block.terminal.value.identifier.id, |
| 807 | ); |
| 808 | if (maybeLoweredFunc != null) { |
| 809 | hoistableFunctions.add(maybeLoweredFunc.fn); |
| 810 | } |
| 811 | } |
| 812 | } |
| 813 | |
| 814 | for (const [_, {fn, mayInvoke}] of temporaries) { |
| 815 | if (hoistableFunctions.has(fn)) { |
| 816 | for (const called of mayInvoke) { |
| 817 | hoistableFunctions.add(called); |
| 818 | } |
| 819 | } |
| 820 | } |
| 821 | return hoistableFunctions; |
| 822 | } |