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);
65 std::vector<Operation *> v(forwardSlice->takeVector());
66 forwardSlice->insert(v.rbegin(), v.rend());
77 std::vector<Operation *> v(forwardSlice->takeVector());
78 forwardSlice->insert(v.rbegin(), v.rend());
90 if (filter && !filter(op))
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)) {
99 Block *block = blockArg.getOwner();
104 if (parentOp && backwardSlice->count(parentOp) == 0) {
110 llvm_unreachable(
"No definingOp and not a block argument.");
114 backwardSlice->insert(op);
125 backwardSlice->remove(op);
146 unsigned currentIndex = 0;
149 while (currentIndex != slice.size()) {
150 auto *currentOp = (slice)[currentIndex];
152 backwardSlice.clear();
154 slice.insert(backwardSlice.begin(), backwardSlice.end());
157 forwardSlice.clear();
159 slice.insert(forwardSlice.begin(), forwardSlice.end());
180 std::vector<Operation *> ops;
181 while (!queue.empty()) {
182 Operation *current = queue.pop_back_val();
183 ops.push_back(current);
188 queue.push_back(&op);
192 for (
Operation *op : llvm::reverse(ops)) {
193 if (state->seen.insert(op).second && state->toSort.count(op) > 0)
194 state->topologicalCounts.push_back(op);
200 if (toSort.empty()) {
205 DFSState state(toSort);
206 for (
auto *s : toSort) {
207 assert(toSort.count(s) == 1 &&
"NYI: multi-sets not supported");
213 for (
auto it = state.topologicalCounts.rbegin(),
214 eit = state.topologicalCounts.rend();
234 iterCarriedArgs.end());
235 if (iterCarriedValSet.contains(value))
240 if (iterCarriedValSet.contains(operand))
277 assert(redPos < iterCarriedArgs.size() &&
"'redPos' is out of bounds");
292 iterCarriedArgs.front().getOwner()->getParent()->getParentOp();
304 combinerOps.push_back(combinerOp);
305 combinerOp = *combinerOp->
getUsers().begin();
310 if (combinerOps.size() != 1)
316 if (terminatorOp->
getOperand(redPos) != combinerOps.back()->getResults()[0])
static void getForwardSliceImpl(Operation *op, SetVector< Operation * > *forwardSlice, TransitiveFilter filter)
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, TransitiveFilter filter)
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)
This header declares functions that assit transformations in the MemRef dialect.
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, TransitiveFilter backwardFilter=nullptr, TransitiveFilter forwardFilter=nullptr, bool inclusive=false)
Iteratively computes backward slices and forward slices until a fixed point is reached.
void getForwardSlice(Operation *op, SetVector< Operation * > *forwardSlice, TransitiveFilter filter=nullptr, bool inclusive=false)
Fills forwardSlice with the computed forward slice (i.e.
void getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, TransitiveFilter filter=nullptr, bool inclusive=false)
Fills backwardSlice with the computed backward slice (i.e.
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Multi-root DAG topological sort.