| 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 | BlockId, |
| 11 | HIRFunction, |
| 12 | InstructionId, |
| 13 | MutableRange, |
| 14 | Place, |
| 15 | ReactiveScope, |
| 16 | getPlaceScope, |
| 17 | makeInstructionId, |
| 18 | } from '../HIR/HIR'; |
| 19 | import { |
| 20 | eachInstructionLValue, |
| 21 | eachInstructionValueOperand, |
| 22 | eachTerminalOperand, |
| 23 | mapTerminalSuccessors, |
| 24 | terminalFallthrough, |
| 25 | } from '../HIR/visitors'; |
| 26 | import {retainWhere_Set} from '../Utils/utils'; |
| 27 | |
| 28 | type InstructionRange = MutableRange; |
| 29 | /* |
| 30 | * Note: this is the 2nd of 4 passes that determine how to break a function into discrete |
| 31 | * reactive scopes (independently memoizeable units of code): |
| 32 | * 1. InferReactiveScopeVariables (on HIR) determines operands that mutate together and assigns |
| 33 | * them a unique reactive scope. |
| 34 | * 2. AlignReactiveScopesToBlockScopes (this pass, on ReactiveFunction) aligns reactive scopes |
| 35 | * to block scopes. |
| 36 | * 3. MergeOverlappingReactiveScopes (on ReactiveFunction) ensures that reactive scopes do not |
| 37 | * overlap, merging any such scopes. |
| 38 | * 4. BuildReactiveBlocks (on ReactiveFunction) groups the statements for each scope into |
| 39 | * a ReactiveScopeBlock. |
| 40 | * |
| 41 | * Prior inference passes assign a reactive scope to each operand, but the ranges of these |
| 42 | * scopes are based on specific instructions at arbitrary points in the control-flow graph. |
| 43 | * However, to codegen blocks around the instructions in each scope, the scopes must be |
| 44 | * aligned to block-scope boundaries - we can't memoize half of a loop! |
| 45 | * |
| 46 | * This pass updates reactive scope boundaries to align to control flow boundaries, for |
| 47 | * example: |
| 48 | * |
| 49 | * ```javascript |
| 50 | * function foo(cond, a) { |
| 51 | * ⌵ original scope |
| 52 | * ⌵ expanded scope |
| 53 | * const x = []; ⌝ ⌝ |
| 54 | * if (cond) { ⎮ ⎮ |
| 55 | * ... ⎮ ⎮ |
| 56 | * x.push(a); ⌟ ⎮ |
| 57 | * ... ⎮ |
| 58 | * } ⌟ |
| 59 | * } |
| 60 | * ``` |
| 61 | * |
| 62 | * Here the original scope for `x` ended partway through the if consequent, but we can't |
| 63 | * memoize part of that block. This pass would align the scope to the end of the consequent. |
| 64 | * |
| 65 | * The more general rule is that a reactive scope may only end at the same block scope as it |
| 66 | * began: this pass therefore finds, for each scope, the block where that scope started and |
| 67 | * finds the first instruction after the scope's mutable range in that same block scope (which |
| 68 | * will be the updated end for that scope). |
| 69 | */ |
| 70 | export function alignReactiveScopesToBlockScopesHIR(fn: HIRFunction): void { |
| 71 | const activeBlockFallthroughRanges: Array<{ |
| 72 | range: InstructionRange; |
| 73 | fallthrough: BlockId; |
| 74 | }> = []; |
| 75 | const activeScopes = new Set<ReactiveScope>(); |
| 76 | const seen = new Set<ReactiveScope>(); |
| 77 | const valueBlockNodes = new Map<BlockId, ValueBlockNode>(); |
| 78 | const placeScopes = new Map<Place, ReactiveScope>(); |
| 79 | |
| 80 | function recordPlace( |
| 81 | id: InstructionId, |
| 82 | place: Place, |
| 83 | node: ValueBlockNode | null, |
| 84 | ): void { |
| 85 | if (place.identifier.scope !== null) { |
| 86 | placeScopes.set(place, place.identifier.scope); |
| 87 | } |
| 88 | |
| 89 | const scope = getPlaceScope(id, place); |
| 90 | if (scope == null) { |
| 91 | return; |
| 92 | } |
| 93 | activeScopes.add(scope); |
| 94 | node?.children.push({kind: 'scope', scope, id}); |
| 95 | |
| 96 | if (seen.has(scope)) { |
| 97 | return; |
| 98 | } |
| 99 | seen.add(scope); |
| 100 | if (node != null && node.valueRange !== null) { |
| 101 | scope.range.start = makeInstructionId( |
| 102 | Math.min(node.valueRange.start, scope.range.start), |
| 103 | ); |
| 104 | scope.range.end = makeInstructionId( |
| 105 | Math.max(node.valueRange.end, scope.range.end), |
| 106 | ); |
| 107 | } |
| 108 | } |
| 109 | |
| 110 | for (const [, block] of fn.body.blocks) { |
| 111 | const startingId = block.instructions[0]?.id ?? block.terminal.id; |
| 112 | retainWhere_Set(activeScopes, scope => scope.range.end > startingId); |
| 113 | const top = activeBlockFallthroughRanges.at(-1); |
| 114 | if (top?.fallthrough === block.id) { |
| 115 | activeBlockFallthroughRanges.pop(); |
| 116 | /* |
| 117 | * All active scopes must have either started before or within the last |
| 118 | * block-fallthrough range. In either case, they overlap this block- |
| 119 | * fallthrough range and can have their ranges extended. |
| 120 | */ |
| 121 | for (const scope of activeScopes) { |
| 122 | scope.range.start = makeInstructionId( |
| 123 | Math.min(scope.range.start, top.range.start), |
| 124 | ); |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | const {instructions, terminal} = block; |
| 129 | const node = valueBlockNodes.get(block.id) ?? null; |
| 130 | for (const instr of instructions) { |
| 131 | for (const lvalue of eachInstructionLValue(instr)) { |
| 132 | recordPlace(instr.id, lvalue, node); |
| 133 | } |
| 134 | for (const operand of eachInstructionValueOperand(instr.value)) { |
| 135 | recordPlace(instr.id, operand, node); |
| 136 | } |
| 137 | } |
| 138 | for (const operand of eachTerminalOperand(terminal)) { |
| 139 | recordPlace(terminal.id, operand, node); |
| 140 | } |
| 141 | |
| 142 | const fallthrough = terminalFallthrough(terminal); |
| 143 | if (fallthrough !== null && terminal.kind !== 'branch') { |
| 144 | /* |
| 145 | * Any currently active scopes that overlaps the block-fallthrough range |
| 146 | * need their range extended to at least the first instruction of the |
| 147 | * fallthrough |
| 148 | */ |
| 149 | const fallthroughBlock = fn.body.blocks.get(fallthrough)!; |
| 150 | const nextId = |
| 151 | fallthroughBlock.instructions[0]?.id ?? fallthroughBlock.terminal.id; |
| 152 | for (const scope of activeScopes) { |
| 153 | if (scope.range.end > terminal.id) { |
| 154 | scope.range.end = makeInstructionId( |
| 155 | Math.max(scope.range.end, nextId), |
| 156 | ); |
| 157 | } |
| 158 | } |
| 159 | /** |
| 160 | * We also record the block-fallthrough range for future scopes that begin |
| 161 | * within the range (and overlap with the range end). |
| 162 | */ |
| 163 | activeBlockFallthroughRanges.push({ |
| 164 | fallthrough, |
| 165 | range: { |
| 166 | start: terminal.id, |
| 167 | end: nextId, |
| 168 | }, |
| 169 | }); |
| 170 | |
| 171 | CompilerError.invariant(!valueBlockNodes.has(fallthrough), { |
| 172 | reason: 'Expect hir blocks to have unique fallthroughs', |
| 173 | loc: terminal.loc, |
| 174 | }); |
| 175 | if (node != null) { |
| 176 | valueBlockNodes.set(fallthrough, node); |
| 177 | } |
| 178 | } else if (terminal.kind === 'goto') { |
| 179 | /** |
| 180 | * If we encounter a goto that is not to the natural fallthrough of the current |
| 181 | * block (not the topmost fallthrough on the stack), then this is a goto to a |
| 182 | * label. Any scopes that extend beyond the goto must be extended to include |
| 183 | * the labeled range, so that the break statement doesn't accidentally jump |
| 184 | * out of the scope. We do this by extending the start and end of the scope's |
| 185 | * range to the label and its fallthrough respectively. |
| 186 | */ |
| 187 | const start = activeBlockFallthroughRanges.find( |
| 188 | range => range.fallthrough === terminal.block, |
| 189 | ); |
| 190 | if (start != null && start !== activeBlockFallthroughRanges.at(-1)) { |
| 191 | const fallthroughBlock = fn.body.blocks.get(start.fallthrough)!; |
| 192 | const firstId = |
| 193 | fallthroughBlock.instructions[0]?.id ?? fallthroughBlock.terminal.id; |
| 194 | for (const scope of activeScopes) { |
| 195 | /** |
| 196 | * activeScopes is only filtered at block start points, so some of the |
| 197 | * scopes may not actually be active anymore, ie we've past their end |
| 198 | * instruction. Only extend ranges for scopes that are actually active. |
| 199 | * |
| 200 | * TODO: consider pruning activeScopes per instruction |
| 201 | */ |
| 202 | if (scope.range.end <= terminal.id) { |
| 203 | continue; |
| 204 | } |
| 205 | scope.range.start = makeInstructionId( |
| 206 | Math.min(start.range.start, scope.range.start), |
| 207 | ); |
| 208 | scope.range.end = makeInstructionId( |
| 209 | Math.max(firstId, scope.range.end), |
| 210 | ); |
| 211 | } |
| 212 | } |
| 213 | } |
| 214 | |
| 215 | /* |
| 216 | * Visit all successors (not just direct successors for control-flow ordering) to |
| 217 | * set a value block node where necessary to align the value block start/end |
| 218 | * back to the outer block scope. |
| 219 | * |
| 220 | * TODO: add a variant of eachTerminalSuccessor() that visits _all_ successors, not |
| 221 | * just those that are direct successors for normal control-flow ordering. |
| 222 | */ |
| 223 | mapTerminalSuccessors(terminal, successor => { |
| 224 | if (valueBlockNodes.has(successor)) { |
| 225 | return successor; |
| 226 | } |
| 227 | |
| 228 | const successorBlock = fn.body.blocks.get(successor)!; |
| 229 | if (successorBlock.kind === 'block' || successorBlock.kind === 'catch') { |
| 230 | /* |
| 231 | * we need the block kind check here because the do..while terminal's |
| 232 | * successor is a block, and try's successor is a catch block |
| 233 | */ |
| 234 | } else if ( |
| 235 | node == null || |
| 236 | terminal.kind === 'ternary' || |
| 237 | terminal.kind === 'logical' || |
| 238 | terminal.kind === 'optional' |
| 239 | ) { |
| 240 | /** |
| 241 | * Create a new node whenever we transition from non-value -> value block. |
| 242 | * |
| 243 | * For compatibility with the previous ReactiveFunction-based scope merging logic, |
| 244 | * we also create new scope nodes for ternary, logical, and optional terminals. |
| 245 | * Inside value blocks we always store a range (valueRange) that is the |
| 246 | * start/end instruction ids at the nearest parent block scope level, so that |
| 247 | * scopes inside the value blocks can be extended to align with block scope |
| 248 | * instructions. |
| 249 | */ |
| 250 | let valueRange: MutableRange; |
| 251 | if (node == null) { |
| 252 | // Transition from block->value block, derive the outer block range |
| 253 | CompilerError.invariant(fallthrough !== null, { |
| 254 | reason: `Expected a fallthrough for value block`, |
| 255 | loc: terminal.loc, |
| 256 | }); |
| 257 | const fallthroughBlock = fn.body.blocks.get(fallthrough)!; |
| 258 | const nextId = |
| 259 | fallthroughBlock.instructions[0]?.id ?? |
| 260 | fallthroughBlock.terminal.id; |
| 261 | valueRange = { |
| 262 | start: terminal.id, |
| 263 | end: nextId, |
| 264 | }; |
| 265 | } else { |
| 266 | // else value->value transition, reuse the range |
| 267 | valueRange = node.valueRange; |
| 268 | } |
| 269 | const childNode: ValueBlockNode = { |
| 270 | kind: 'node', |
| 271 | id: terminal.id, |
| 272 | children: [], |
| 273 | valueRange, |
| 274 | }; |
| 275 | node?.children.push(childNode); |
| 276 | valueBlockNodes.set(successor, childNode); |
| 277 | } else { |
| 278 | // this is a value -> value block transition, reuse the node |
| 279 | valueBlockNodes.set(successor, node); |
| 280 | } |
| 281 | return successor; |
| 282 | }); |
| 283 | } |
| 284 | } |
| 285 | |
| 286 | type ValueBlockNode = { |
| 287 | kind: 'node'; |
| 288 | id: InstructionId; |
| 289 | valueRange: MutableRange; |
| 290 | children: Array<ValueBlockNode | ReactiveScopeNode>; |
| 291 | }; |
| 292 | type ReactiveScopeNode = { |
| 293 | kind: 'scope'; |
| 294 | id: InstructionId; |
| 295 | scope: ReactiveScope; |
| 296 | }; |
| 297 | |
| 298 | function _debug(node: ValueBlockNode): string { |
| 299 | const buf: Array<string> = []; |
| 300 | _printNode(node, buf, 0); |
| 301 | return buf.join('\n'); |
| 302 | } |
| 303 | function _printNode( |
| 304 | node: ValueBlockNode | ReactiveScopeNode, |
| 305 | out: Array<string>, |
| 306 | depth: number = 0, |
| 307 | ): void { |
| 308 | let prefix = ' '.repeat(depth); |
| 309 | if (node.kind === 'scope') { |
| 310 | out.push( |
| 311 | `${prefix}[${node.id}] @${node.scope.id} [${node.scope.range.start}:${node.scope.range.end}]`, |
| 312 | ); |
| 313 | } else { |
| 314 | let range = ` (range=[${node.valueRange.start}:${node.valueRange.end}])`; |
| 315 | out.push(`${prefix}[${node.id}] node${range} [`); |
| 316 | for (const child of node.children) { |
| 317 | _printNode(child, out, depth + 1); |
| 318 | } |
| 319 | out.push(`${prefix}]`); |
| 320 | } |
| 321 | } |