1#include "mlir/Analysis/SliceWalk.h"
2#include "mlir/Interfaces/ControlFlowInterfaces.h"
3
4using namespace mlir;
5
6WalkContinuation 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.
37static std::optional<SmallVector<Value>>
38getBlockPredecessorOperands(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
59std::optional<SmallVector<Value>>
60mlir::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