| 1 | #include "mlir/Analysis/SliceWalk.h" |
| 2 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 3 | |
| 4 | using namespace mlir; |
| 5 | |
| 6 | WalkContinuation mlir::walkSlice(ValueRange rootValues, |
| 7 | WalkCallback walkCallback) { |
| 8 | // Search the backward slice starting from the root values. |
| 9 | SmallVector<Value> workList = rootValues; |
| 10 | llvm::SmallDenseSet<Value, 16> seenValues; |
| 11 | while (!workList.empty()) { |
| 12 | // Search the backward slice of the current value. |
| 13 | Value current = workList.pop_back_val(); |
| 14 | |
| 15 | // Skip the current value if it has already been seen. |
| 16 | if (!seenValues.insert(V: current).second) |
| 17 | continue; |
| 18 | |
| 19 | // Call the walk callback with the current value. |
| 20 | WalkContinuation continuation = walkCallback(current); |
| 21 | if (continuation.wasInterrupted()) |
| 22 | return continuation; |
| 23 | if (continuation.wasSkipped()) |
| 24 | continue; |
| 25 | |
| 26 | assert(continuation.wasAdvancedTo()); |
| 27 | // Add the next values to the work list if the walk should continue. |
| 28 | workList.append(in_start: continuation.getNextValues().begin(), |
| 29 | in_end: continuation.getNextValues().end()); |
| 30 | } |
| 31 | |
| 32 | return WalkContinuation::skip(); |
| 33 | } |
| 34 | |
| 35 | /// Returns the predecessor branch operands that match `blockArg`, or nullopt if |
| 36 | /// some of the predecessor terminators do not implement the BranchOpInterface. |
| 37 | static std::optional<SmallVector<Value>> |
| 38 | getBlockPredecessorOperands(BlockArgument blockArg) { |
| 39 | Block *block = blockArg.getOwner(); |
| 40 | |
| 41 | // Search the predecessor operands for all predecessor terminators. |
| 42 | SmallVector<Value> predecessorOperands; |
| 43 | for (auto it = block->pred_begin(); it != block->pred_end(); ++it) { |
| 44 | Block *predecessor = *it; |
| 45 | auto branchOp = dyn_cast<BranchOpInterface>(Val: predecessor->getTerminator()); |
| 46 | if (!branchOp) |
| 47 | return std::nullopt; |
| 48 | SuccessorOperands successorOperands = |
| 49 | branchOp.getSuccessorOperands(index: it.getSuccessorIndex()); |
| 50 | // Store the predecessor operand if the block argument matches an operand |
| 51 | // and is not produced by the terminator. |
| 52 | if (Value operand = successorOperands[blockArg.getArgNumber()]) |
| 53 | predecessorOperands.push_back(Elt: operand); |
| 54 | } |
| 55 | |
| 56 | return predecessorOperands; |
| 57 | } |
| 58 | |
| 59 | std::optional<SmallVector<Value>> |
| 60 | mlir::getControlFlowPredecessors(Value value) { |
| 61 | if (OpResult opResult = dyn_cast<OpResult>(Val&: value)) { |
| 62 | if (auto selectOp = opResult.getDefiningOp<SelectLikeOpInterface>()) |
| 63 | return SmallVector<Value>( |
| 64 | {selectOp.getTrueValue(), selectOp.getFalseValue()}); |
| 65 | auto regionOp = opResult.getDefiningOp<RegionBranchOpInterface>(); |
| 66 | // If the interface is not implemented, there are no control flow |
| 67 | // predecessors to work with. |
| 68 | if (!regionOp) |
| 69 | return std::nullopt; |
| 70 | // Add the control flow predecessor operands to the work list. |
| 71 | RegionSuccessor region = RegionSuccessor(regionOp.getOperation()); |
| 72 | // Find the position of `opResult` in the successor inputs of the parent. |
| 73 | // `getPredecessorValues` indexes into the successor inputs, not into the |
| 74 | // op results directly, since some results may not be successor inputs. |
| 75 | ValueRange successorInputs = regionOp.getSuccessorInputs(successor: region); |
| 76 | auto it = llvm::find(Range&: successorInputs, Val: opResult); |
| 77 | if (it == successorInputs.end()) |
| 78 | return std::nullopt; |
| 79 | SmallVector<Value> predecessorOperands; |
| 80 | regionOp.getPredecessorValues(successor: region, |
| 81 | index: std::distance(first: successorInputs.begin(), last: it), |
| 82 | predecessorValues&: predecessorOperands); |
| 83 | return predecessorOperands; |
| 84 | } |
| 85 | |
| 86 | auto blockArg = cast<BlockArgument>(Val&: value); |
| 87 | Block *block = blockArg.getOwner(); |
| 88 | // Search the region predecessor operands for structured control flow. |
| 89 | if (block->isEntryBlock()) { |
| 90 | if (auto regionBranchOp = |
| 91 | dyn_cast<RegionBranchOpInterface>(Val: block->getParentOp())) { |
| 92 | RegionSuccessor regionSuccessor(blockArg.getParentRegion()); |
| 93 | // Find the position of `blockArg` in the successor inputs of the region. |
| 94 | // `getPredecessorValues` indexes into the successor inputs, not into the |
| 95 | // block arguments directly, since some block arguments may not be |
| 96 | // successor inputs (e.g., block arguments produced by the terminator). |
| 97 | ValueRange successorInputs = |
| 98 | regionBranchOp.getSuccessorInputs(successor: regionSuccessor); |
| 99 | auto it = llvm::find(Range&: successorInputs, Val: blockArg); |
| 100 | if (it == successorInputs.end()) |
| 101 | return std::nullopt; |
| 102 | SmallVector<Value> predecessorOperands; |
| 103 | regionBranchOp.getPredecessorValues( |
| 104 | successor: regionSuccessor, index: std::distance(first: successorInputs.begin(), last: it), |
| 105 | predecessorValues&: predecessorOperands); |
| 106 | return predecessorOperands; |
| 107 | } |
| 108 | // If the interface is not implemented, there are no control flow |
| 109 | // predecessors to work with. |
| 110 | return std::nullopt; |
| 111 | } |
| 112 | |
| 113 | // Search the block predecessor operands for unstructured control flow. |
| 114 | return getBlockPredecessorOperands(blockArg); |
| 115 | } |
| 116 | |