19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
38 if (filter && !filter(op))
42 for (
Block &block : region)
44 if (forwardSlice->count(&blockOp) == 0) {
50 visited.insert(&blockOp);
52 visited.erase(&blockOp);
65 if (forwardSlice->count(userOp) == 0 && visited.insert(userOp).second)
68 visited.erase(userOp);
71 forwardSlice->insert(op);
82 forwardSlice->remove(op);
89 forwardSlice->insert(v.rbegin(), v.rend());
105 forwardSlice->insert(v.rbegin(), v.rend());
122 if (
auto *definingOp = value.getDefiningOp()) {
123 if (backwardSlice->count(definingOp) == 0 &&
124 visited.insert(definingOp).second)
128 visited.erase(definingOp);
129 }
else if (
auto blockArg = dyn_cast<BlockArgument>(value)) {
130 if (
options.omitBlockArguments)
133 Block *block = blockArg.getOwner();
138 if (parentOp && backwardSlice->count(parentOp) == 0) {
151 bool succeeded =
true;
153 if (!
options.omitUsesFromAbove) {
157 SmallPtrSet<Region *, 4> descendents;
159 [&](Region *childRegion) { descendents.insert(childRegion); });
162 if (!descendents.contains(operand.get().getParentRegion()))
163 if (!processValue(operand.get()).succeeded()) {
164 return WalkResult::interrupt();
173 backwardSlice->insert(op);
174 return success(succeeded);
182 LogicalResult result =
188 backwardSlice->remove(op);
209 unsigned currentIndex = 0;
212 while (currentIndex != slice.size()) {
213 auto *currentOp = (slice)[currentIndex];
215 backwardSlice.clear();
216 LogicalResult result =
218 assert(result.succeeded());
220 slice.insert_range(backwardSlice);
223 forwardSlice.clear();
225 slice.insert_range(forwardSlice);
243 assert(result.succeeded());
249 if (iterCarriedValSet.contains(value))
253 for (
Value operand : op->getOperands())
254 if (iterCarriedValSet.contains(operand))
291 assert(redPos < iterCarriedArgs.size() &&
"'redPos' is out of bounds");
306 iterCarriedArgs.front().getOwner()->getParent()->getParentOp();
318 combinerOps.push_back(combinerOp);
319 combinerOp = *combinerOp->
getUsers().begin();
324 if (combinerOps.size() != 1)
330 if (terminatorOp->
getOperand(redPos) != combinerOps.back()->getResults()[0])
static llvm::ManagedStatic< PassManagerOptions > options
static void processValue(Value value, LiveMap &liveMap)
static LogicalResult getBackwardSliceImpl(Operation *op, DenseSet< Operation * > &visited, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options)
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 getForwardSliceImpl(Operation *op, DenseSet< Operation * > &visited, SetVector< Operation * > *forwardSlice, const SliceOptions::TransitiveFilter &filter=nullptr)
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 represents an operand of an operation.
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.
MutableArrayRef< OpOperand > getOpOperands()
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.
bool hasOneBlock()
Return true if this region has exactly one block.
RetT walk(FnT &&callback)
Walk all nested operations, blocks or regions (including this region), depending on the type of callb...
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.
static WalkResult advance()
Include the generated interface declarations.
LogicalResult 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)
Sorts all operations in toSort topologically while also considering region semantics.
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.