| 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 {BlockId, computePostDominatorTree, HIRFunction, Place} from '../HIR'; |
| 9 | import {PostDominator} from '../HIR/Dominator'; |
| 10 | |
| 11 | export type ControlDominators = (id: BlockId) => boolean; |
| 12 | |
| 13 | /** |
| 14 | * Returns an object that lazily calculates whether particular blocks are controlled |
| 15 | * by values of interest. Which values matter are up to the caller. |
| 16 | */ |
| 17 | export function createControlDominators( |
| 18 | fn: HIRFunction, |
| 19 | isControlVariable: (place: Place) => boolean, |
| 20 | ): ControlDominators { |
| 21 | const postDominators = computePostDominatorTree(fn, { |
| 22 | includeThrowsAsExitNode: false, |
| 23 | }); |
| 24 | const postDominatorFrontierCache = new Map<BlockId, Set<BlockId>>(); |
| 25 | |
| 26 | function isControlledBlock(id: BlockId): boolean { |
| 27 | let controlBlocks = postDominatorFrontierCache.get(id); |
| 28 | if (controlBlocks === undefined) { |
| 29 | controlBlocks = postDominatorFrontier(fn, postDominators, id); |
| 30 | postDominatorFrontierCache.set(id, controlBlocks); |
| 31 | } |
| 32 | for (const blockId of controlBlocks) { |
| 33 | const controlBlock = fn.body.blocks.get(blockId)!; |
| 34 | switch (controlBlock.terminal.kind) { |
| 35 | case 'if': |
| 36 | case 'branch': { |
| 37 | if (isControlVariable(controlBlock.terminal.test)) { |
| 38 | return true; |
| 39 | } |
| 40 | break; |
| 41 | } |
| 42 | case 'switch': { |
| 43 | if (isControlVariable(controlBlock.terminal.test)) { |
| 44 | return true; |
| 45 | } |
| 46 | for (const case_ of controlBlock.terminal.cases) { |
| 47 | if (case_.test !== null && isControlVariable(case_.test)) { |
| 48 | return true; |
| 49 | } |
| 50 | } |
| 51 | break; |
| 52 | } |
| 53 | } |
| 54 | } |
| 55 | return false; |
| 56 | } |
| 57 | |
| 58 | return isControlledBlock; |
| 59 | } |
| 60 | |
| 61 | /* |
| 62 | * Computes the post-dominator frontier of @param block. These are immediate successors of nodes that |
| 63 | * post-dominate @param targetId and from which execution may not reach @param block. Intuitively, these |
| 64 | * are the earliest blocks from which execution branches such that it may or may not reach the target block. |
| 65 | */ |
| 66 | function postDominatorFrontier( |
| 67 | fn: HIRFunction, |
| 68 | postDominators: PostDominator<BlockId>, |
| 69 | targetId: BlockId, |
| 70 | ): Set<BlockId> { |
| 71 | const visited = new Set<BlockId>(); |
| 72 | const frontier = new Set<BlockId>(); |
| 73 | const targetPostDominators = postDominatorsOf(fn, postDominators, targetId); |
| 74 | for (const blockId of [...targetPostDominators, targetId]) { |
| 75 | if (visited.has(blockId)) { |
| 76 | continue; |
| 77 | } |
| 78 | visited.add(blockId); |
| 79 | const block = fn.body.blocks.get(blockId)!; |
| 80 | for (const pred of block.preds) { |
| 81 | if (!targetPostDominators.has(pred)) { |
| 82 | // The predecessor does not always reach this block, we found an item on the frontier! |
| 83 | frontier.add(pred); |
| 84 | } |
| 85 | } |
| 86 | } |
| 87 | return frontier; |
| 88 | } |
| 89 | |
| 90 | function postDominatorsOf( |
| 91 | fn: HIRFunction, |
| 92 | postDominators: PostDominator<BlockId>, |
| 93 | targetId: BlockId, |
| 94 | ): Set<BlockId> { |
| 95 | const result = new Set<BlockId>(); |
| 96 | const visited = new Set<BlockId>(); |
| 97 | const queue = [targetId]; |
| 98 | while (queue.length) { |
| 99 | const currentId = queue.shift()!; |
| 100 | if (visited.has(currentId)) { |
| 101 | continue; |
| 102 | } |
| 103 | visited.add(currentId); |
| 104 | const current = fn.body.blocks.get(currentId)!; |
| 105 | for (const pred of current.preds) { |
| 106 | const predPostDominator = postDominators.get(pred) ?? pred; |
| 107 | if (predPostDominator === targetId || result.has(predPostDominator)) { |
| 108 | result.add(pred); |
| 109 | } |
| 110 | queue.push(pred); |
| 111 | } |
| 112 | } |
| 113 | return result; |
| 114 | } |