18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
36 if (filter && !filter(op))
40 for (
Block &block : region)
42 if (forwardSlice->count(&blockOp) == 0)
46 if (forwardSlice->count(userOp) == 0)
50 forwardSlice->insert(op);
59 forwardSlice->remove(op);
66 forwardSlice->insert(v.rbegin(), v.rend());
78 forwardSlice->insert(v.rbegin(), v.rend());
94 auto operand = en.value();
95 if (
auto *definingOp = operand.getDefiningOp()) {
96 if (backwardSlice->count(definingOp) == 0)
98 }
else if (
auto blockArg = dyn_cast<BlockArgument>(operand)) {
102 Block *block = blockArg.getOwner();
107 if (parentOp && backwardSlice->count(parentOp) == 0) {
113 llvm_unreachable(
"No definingOp and not a block argument.");
117 backwardSlice->insert(op);
128 backwardSlice->remove(op);
148 unsigned currentIndex = 0;
151 while (currentIndex != slice.size()) {
152 auto *currentOp = (slice)[currentIndex];
154 backwardSlice.clear();
156 slice.insert(backwardSlice.begin(), backwardSlice.end());
159 forwardSlice.clear();
161 slice.insert(forwardSlice.begin(), forwardSlice.end());
182 std::vector<Operation *> ops;
183 while (!queue.empty()) {
184 Operation *current = queue.pop_back_val();
185 ops.push_back(current);
190 queue.push_back(&op);
194 for (
Operation *op : llvm::reverse(ops)) {
195 if (state->seen.insert(op).second && state->toSort.count(op) > 0)
196 state->topologicalCounts.push_back(op);
202 if (toSort.empty()) {
207 DFSState state(toSort);
208 for (
auto *s : toSort) {
209 assert(toSort.count(s) == 1 &&
"NYI: multi-sets not supported");
215 for (
auto it = state.topologicalCounts.rbegin(),
216 eit = state.topologicalCounts.rend();
239 iterCarriedArgs.end());
240 if (iterCarriedValSet.contains(value))
245 if (iterCarriedValSet.contains(operand))
282 assert(redPos < iterCarriedArgs.size() &&
"'redPos' is out of bounds");
297 iterCarriedArgs.front().getOwner()->getParent()->getParentOp();
309 combinerOps.push_back(combinerOp);
310 combinerOp = *combinerOp->
getUsers().begin();
315 if (combinerOps.size() != 1)
321 if (terminatorOp->
getOperand(redPos) != combinerOps.back()->getResults()[0])
static llvm::ManagedStatic< PassManagerOptions > options
static void getForwardSliceImpl(Operation *op, SetVector< Operation * > *forwardSlice, const SliceOptions::TransitiveFilter &filter=nullptr)
static bool dependsOnCarriedVals(Value value, ArrayRef< BlockArgument > iterCarriedArgs, Operation *ancestorOp)
Returns true if value (transitively) depends on iteration-carried values of the given ancestorOp.
static void getBackwardSliceImpl(Operation *op, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options)
static void dfsPostorder(Operation *root, DFSState *state)
This class represents an argument of a Block.
Block represents an ordered list of Operations.
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
This class provides the API for ops that are known to be isolated from above.
This class provides the API for ops that are known to be terminators.
Operation is the basic unit of execution within MLIR.
Value getOperand(unsigned idx)
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
bool hasOneUse()
Returns true if this operation has exactly one use.
unsigned getNumRegions()
Returns the number of regions held by this operation.
unsigned getNumOperands()
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
operand_range getOperands()
Returns an iterator on the underlying Value's.
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
user_range getUsers()
Returns a range of all users.
result_range getResults()
unsigned getNumResults()
Return the number of results held by this operation.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
BlockListType & getBlocks()
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
user_range getUsers() const
bool hasOneUse() const
Returns true if this value has exactly one use.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Include the generated interface declarations.
void getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options={})
Fills backwardSlice with the computed backward slice (i.e.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
Value matchReduction(ArrayRef< BlockArgument > iterCarriedArgs, unsigned redPos, SmallVectorImpl< Operation * > &combinerOps)
Utility to match a generic reduction given a list of iteration-carried arguments, iterCarriedArgs and...
SetVector< Operation * > getSlice(Operation *op, const BackwardSliceOptions &backwardSliceOptions={}, const ForwardSliceOptions &forwardSliceOptions={})
Iteratively computes backward slices and forward slices until a fixed point is reached.
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Multi-root DAG topological sort.
void getForwardSlice(Operation *op, SetVector< Operation * > *forwardSlice, const ForwardSliceOptions &options={})
Fills forwardSlice with the computed forward slice (i.e.
std::function< bool(Operation *)> TransitiveFilter
Type of the condition to limit the propagation of transitive use-defs.