| 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 { |
| 10 | BlockId, |
| 11 | GeneratedSource, |
| 12 | HIRFunction, |
| 13 | Identifier, |
| 14 | Place, |
| 15 | } from '../HIR/HIR'; |
| 16 | import { |
| 17 | eachInstructionLValue, |
| 18 | eachInstructionOperand, |
| 19 | eachTerminalOperand, |
| 20 | } from '../HIR/visitors'; |
| 21 | |
| 22 | const DEBUG = false; |
| 23 | |
| 24 | /* |
| 25 | * Pass to eliminate redundant phi nodes: |
| 26 | * - all operands are the same identifier, ie `x2 = phi(x1, x1, x1)`. |
| 27 | * - all operands are the same identifier *or* the output of the phi, ie `x2 = phi(x1, x2, x1, x2)`. |
| 28 | * |
| 29 | * In both these cases, the phi is eliminated and all usages of the phi identifier |
| 30 | * are replaced with the other operand (ie in both cases above, all usages of `x2` are replaced with `x1` . |
| 31 | * |
| 32 | * The algorithm is inspired by that in https://pp.ipd.kit.edu/uploads/publikationen/braun13cc.pdf |
| 33 | * but modified to reduce passes over the CFG. We visit the blocks in reverse postorder. Each time a redundant |
| 34 | * phi is encountered we add a mapping (eg x2 -> x1) to a rewrite table. Subsequent instructions, terminals, |
| 35 | * and phis rewrite all their identifiers based on this table. The algorithm loops over the CFG repeatedly |
| 36 | * until there are no new rewrites: for a CFG without back-edges it completes in a single pass. |
| 37 | */ |
| 38 | export function eliminateRedundantPhi( |
| 39 | fn: HIRFunction, |
| 40 | sharedRewrites?: Map<Identifier, Identifier>, |
| 41 | ): void { |
| 42 | const ir = fn.body; |
| 43 | const rewrites: Map<Identifier, Identifier> = |
| 44 | sharedRewrites != null ? sharedRewrites : new Map(); |
| 45 | |
| 46 | /* |
| 47 | * Whether or the CFG has a back-edge (a loop). We determine this dynamically |
| 48 | * during the first iteration over the CFG by recording which blocks were already |
| 49 | * visited, and checking if a block has any predecessors that weren't visited yet. |
| 50 | * Because blocks are in reverse postorder, the only time this can occur is a loop. |
| 51 | */ |
| 52 | let hasBackEdge = false; |
| 53 | const visited: Set<BlockId> = new Set(); |
| 54 | |
| 55 | /* |
| 56 | * size tracks the number of rewrites at the beginning of each iteration, so we can |
| 57 | * compare to see if any new rewrites were added in that iteration. |
| 58 | */ |
| 59 | let size = rewrites.size; |
| 60 | do { |
| 61 | size = rewrites.size; |
| 62 | for (const [blockId, block] of ir.blocks) { |
| 63 | /* |
| 64 | * On the first iteration of the loop check for any back-edges. |
| 65 | * if there aren't any then there won't be a second iteration |
| 66 | */ |
| 67 | if (!hasBackEdge) { |
| 68 | for (const predId of block.preds) { |
| 69 | if (!visited.has(predId)) { |
| 70 | hasBackEdge = true; |
| 71 | } |
| 72 | } |
| 73 | } |
| 74 | visited.add(blockId); |
| 75 | |
| 76 | // Find any redundant phis |
| 77 | phis: for (const phi of block.phis) { |
| 78 | // Remap phis in case operands are from eliminated phis |
| 79 | phi.operands.forEach((place, _) => rewritePlace(place, rewrites)); |
| 80 | // Find if the phi can be eliminated |
| 81 | let same: Identifier | null = null; |
| 82 | for (const [_, operand] of phi.operands) { |
| 83 | if ( |
| 84 | (same !== null && operand.identifier.id === same.id) || |
| 85 | operand.identifier.id === phi.place.identifier.id |
| 86 | ) { |
| 87 | /* |
| 88 | * This operand is the same as the phi or is the same as the |
| 89 | * previous non-phi operands |
| 90 | */ |
| 91 | continue; |
| 92 | } else if (same !== null) { |
| 93 | /* |
| 94 | * There are multiple operands not equal to the phi itself, |
| 95 | * this phi can't be eliminated. |
| 96 | */ |
| 97 | continue phis; |
| 98 | } else { |
| 99 | // First non-phi operand |
| 100 | same = operand.identifier; |
| 101 | } |
| 102 | } |
| 103 | CompilerError.invariant(same !== null, { |
| 104 | reason: 'Expected phis to be non-empty', |
| 105 | loc: GeneratedSource, |
| 106 | }); |
| 107 | rewrites.set(phi.place.identifier, same); |
| 108 | block.phis.delete(phi); |
| 109 | } |
| 110 | |
| 111 | // Rewrite all instruction lvalues and operands |
| 112 | for (const instr of block.instructions) { |
| 113 | for (const place of eachInstructionLValue(instr)) { |
| 114 | rewritePlace(place, rewrites); |
| 115 | } |
| 116 | for (const place of eachInstructionOperand(instr)) { |
| 117 | rewritePlace(place, rewrites); |
| 118 | } |
| 119 | |
| 120 | if ( |
| 121 | instr.value.kind === 'FunctionExpression' || |
| 122 | instr.value.kind === 'ObjectMethod' |
| 123 | ) { |
| 124 | const {context} = instr.value.loweredFunc.func; |
| 125 | for (const place of context) { |
| 126 | rewritePlace(place, rewrites); |
| 127 | } |
| 128 | |
| 129 | /* |
| 130 | * recursive call to: |
| 131 | * - eliminate phi nodes in child node |
| 132 | * - propagate rewrites, which may have changed between iterations |
| 133 | */ |
| 134 | eliminateRedundantPhi(instr.value.loweredFunc.func, rewrites); |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | // Rewrite all terminal operands |
| 139 | const {terminal} = block; |
| 140 | for (const place of eachTerminalOperand(terminal)) { |
| 141 | rewritePlace(place, rewrites); |
| 142 | } |
| 143 | } |
| 144 | /* |
| 145 | * We only need to loop if there were newly eliminated phis in this iteration |
| 146 | * *and* the CFG has loops. If there are no loops, then all eliminated phis |
| 147 | * have already propagated forwards since we visit in reverse postorder. |
| 148 | */ |
| 149 | } while (rewrites.size > size && hasBackEdge); |
| 150 | |
| 151 | if (DEBUG) { |
| 152 | for (const [, block] of ir.blocks) { |
| 153 | for (const phi of block.phis) { |
| 154 | CompilerError.invariant(!rewrites.has(phi.place.identifier), { |
| 155 | reason: '[EliminateRedundantPhis]: rewrite not complete', |
| 156 | loc: phi.place.loc, |
| 157 | }); |
| 158 | for (const [, operand] of phi.operands) { |
| 159 | CompilerError.invariant(!rewrites.has(operand.identifier), { |
| 160 | reason: '[EliminateRedundantPhis]: rewrite not complete', |
| 161 | loc: phi.place.loc, |
| 162 | }); |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | function rewritePlace( |
| 170 | place: Place, |
| 171 | rewrites: Map<Identifier, Identifier>, |
| 172 | ): void { |
| 173 | const rewrite = rewrites.get(place.identifier); |
| 174 | if (rewrite != null) { |
| 175 | place.identifier = rewrite; |
| 176 | } |
| 177 | } |