23 #include "llvm/ADT/DepthFirstIterator.h"
24 #include "llvm/ADT/PostOrderIterator.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/Support/DebugLog.h"
33 #define DEBUG_TYPE "region-utils"
37 for (
auto &use : llvm::make_early_inc_range(orig.
getUses())) {
38 if (region.
isAncestor(use.getOwner()->getParentRegion()))
46 "expected isolation limit to be an ancestor of the given region");
53 properAncestors.insert(reg);
59 if (properAncestors.count(operand.get().getParentRegion()))
66 for (
Region ®ion : regions)
73 values.insert(operand->
get());
79 for (
Region ®ion : regions)
95 std::deque<Value> worklist(initialCapturedValues.begin(),
96 initialCapturedValues.end());
102 while (!worklist.empty()) {
103 Value currValue = worklist.front();
104 worklist.pop_front();
105 if (visited.count(currValue))
107 visited.insert(currValue);
110 if (!definingOp || visitedOps.count(definingOp)) {
111 finalCapturedValues.insert(currValue);
114 visitedOps.insert(definingOp);
116 if (!cloneOperationIntoRegion(definingOp)) {
119 finalCapturedValues.insert(currValue);
126 if (visited.count(operand))
128 worklist.push_back(operand);
130 clonedOperations.push_back(definingOp);
147 for (
auto value : finalCapturedValues) {
148 newArgTypes.push_back(value.getType());
149 newArgLocs.push_back(value.getLoc());
153 Block *newEntryBlock =
160 return use.getOwner()->getBlock()->getParent() == ®ion;
162 for (
auto [arg, capturedVal] :
163 llvm::zip(newEntryBlockArgs.take_back(finalCapturedValues.size()),
164 finalCapturedValues)) {
165 map.
map(capturedVal, arg);
169 for (
auto *clonedOp : clonedOperations) {
174 entryBlock, newEntryBlock,
176 return llvm::to_vector(finalCapturedValues);
188 LDBG() <<
"Starting eraseUnreachableBlocks with " << regions.size()
192 llvm::df_iterator_default_set<Block *, 16> reachable;
194 int erasedDeadBlocks = 0;
197 worklist.reserve(regions.size());
198 for (
Region ®ion : regions)
199 worklist.push_back(®ion);
201 LDBG(2) <<
"Initial worklist size: " << worklist.size();
203 while (!worklist.empty()) {
204 Region *region = worklist.pop_back_val();
205 if (region->
empty()) {
206 LDBG(2) <<
"Skipping empty region";
210 LDBG(2) <<
"Processing region with " << region->
getBlocks().size()
213 LDBG(2) <<
" -> for operation: "
220 for (
Region ®ion : op.getRegions())
221 worklist.push_back(®ion);
227 for (
Block *block : depth_first_ext(®ion->
front(), reachable))
230 LDBG(2) <<
"Found " << reachable.size() <<
" reachable blocks out of "
231 << region->
getBlocks().size() <<
" total blocks";
235 for (
Block &block : llvm::make_early_inc_range(*region)) {
236 if (!reachable.count(&block)) {
237 LDBG() <<
"Erasing unreachable block: " << █
238 block.dropAllDefinedValueUses();
246 for (
Region ®ion : op.getRegions())
247 worklist.push_back(®ion);
251 LDBG() <<
"Finished eraseUnreachableBlocks, erased " << erasedDeadBlocks
254 return success(erasedDeadBlocks > 0);
273 bool wasProvenLive(
Value value) {
276 if (
OpResult result = dyn_cast<OpResult>(value))
277 return wasProvenLive(result.getOwner());
278 return wasProvenLive(cast<BlockArgument>(value));
280 bool wasProvenLive(
BlockArgument arg) {
return liveValues.count(arg); }
281 void setProvedLive(
Value value) {
284 if (
OpResult result = dyn_cast<OpResult>(value))
285 return setProvedLive(result.getOwner());
286 setProvedLive(cast<BlockArgument>(value));
289 changed |= liveValues.insert(arg).second;
293 bool wasProvenLive(
Operation *op) {
return liveOps.count(op); }
297 void resetChanged() {
changed =
false; }
298 bool hasChanged() {
return changed; }
322 if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(owner))
323 if (
auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
324 return !liveMap.wasProvenLive(*arg);
332 if (isUseSpeciallyKnownDead(use, liveMap))
334 return liveMap.wasProvenLive(use.getOwner());
337 liveMap.setProvedLive(value);
344 liveMap.setProvedLive(op);
347 BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(op);
348 if (!branchInterface) {
351 liveMap.setProvedLive(arg);
359 branchInterface.getSuccessorOperands(i);
376 if (liveMap.wasProvenLive(op))
381 return liveMap.setProvedLive(op);
392 for (
Block *block : llvm::post_order(®ion.
front())) {
395 for (
Operation &op : llvm::reverse(block->getOperations()))
402 if (block->isEntryBlock())
405 for (
Value value : block->getArguments()) {
406 if (!liveMap.wasProvenLive(value))
414 BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(terminator);
419 succI < succE; succI++) {
424 unsigned succ = succE - succI - 1;
428 for (
unsigned argI = 0, argE = succOperands.
size(); argI < argE; ++argI) {
431 unsigned arg = argE - argI - 1;
432 if (!liveMap.wasProvenLive(successor->
getArgument(arg)))
433 succOperands.
erase(arg);
441 bool erasedAnything =
false;
442 for (
Region ®ion : regions) {
452 for (
Block *block : llvm::post_order(®ion.
front())) {
456 llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
457 if (!liveMap.wasProvenLive(&childOp)) {
458 erasedAnything =
true;
459 childOp.dropAllUses();
462 erasedAnything |= succeeded(
471 block.eraseArguments(
472 [&](
BlockArgument arg) {
return !liveMap.wasProvenLive(arg); });
475 return success(erasedAnything);
499 liveMap.resetChanged();
501 for (
Region ®ion : regions)
503 }
while (liveMap.hasChanged());
533 struct BlockEquivalenceData {
534 BlockEquivalenceData(
Block *block);
538 unsigned getOrderOf(
Value value)
const;
543 llvm::hash_code hash;
551 BlockEquivalenceData::BlockEquivalenceData(
Block *block)
552 : block(block), hash(0) {
555 if (
unsigned numResults = op.getNumResults()) {
556 opOrderIndex.try_emplace(&op, orderIt);
557 orderIt += numResults;
563 hash = llvm::hash_combine(hash, opHash);
567 unsigned BlockEquivalenceData::getOrderOf(
Value value)
const {
568 assert(value.
getParentBlock() == block &&
"expected value of this block");
575 OpResult result = cast<OpResult>(value);
577 assert(opOrderIt != opOrderIndex.end() &&
"expected op to have an order");
587 class BlockMergeCluster {
589 BlockMergeCluster(BlockEquivalenceData &&leaderData)
590 : leaderData(std::move(leaderData)) {}
594 LogicalResult addToCluster(BlockEquivalenceData &blockData);
601 BlockEquivalenceData leaderData;
604 llvm::SmallSetVector<Block *, 1> blocksToMerge;
608 std::set<std::pair<int, int>> operandsToMerge;
612 LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
613 if (leaderData.hash != blockData.hash)
615 Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
621 auto lhsIt = leaderBlock->
begin(), lhsE = leaderBlock->
end();
622 auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
623 for (
int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
625 if (!OperationEquivalence::isEquivalentTo(
626 &*lhsIt, &*rhsIt, OperationEquivalence::ignoreValueEquivalence,
628 OperationEquivalence::Flags::IgnoreLocations))
633 auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
634 for (
int operand : llvm::seq<int>(0, lhsIt->getNumOperands())) {
635 Value lhsOperand = lhsOperands[operand];
636 Value rhsOperand = rhsOperands[operand];
637 if (lhsOperand == rhsOperand)
646 if (lhsIsInBlock != rhsIsInBlock)
656 auto isValidSuccessorArg = [](
Block *block,
Value operand) {
657 if (operand.getDefiningOp() !=
658 operand.getParentBlock()->getTerminator())
661 operand.getParentBlock());
664 if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
665 !isValidSuccessorArg(mergeBlock, rhsOperand))
668 mismatchedOperands.emplace_back(opI, operand);
674 if (leaderData.getOrderOf(lhsOperand) != blockData.getOrderOf(rhsOperand))
684 if (rhsIt->isUsedOutsideOfBlock(mergeBlock) ||
685 lhsIt->isUsedOutsideOfBlock(leaderBlock)) {
690 if (lhsIt != lhsE || rhsIt != rhsE)
694 operandsToMerge.insert(mismatchedOperands.begin(), mismatchedOperands.end());
695 blocksToMerge.insert(blockData.block);
703 if (!isa<BranchOpInterface>((*it)->getTerminator()))
722 if (newArguments.empty())
726 unsigned numLists = newArguments.size();
727 unsigned numArgs = newArguments[0].size();
737 for (
unsigned j = 0;
j < numArgs; ++
j) {
738 Value newArg = newArguments[0][
j];
739 firstValueToIdx.try_emplace(newArg,
j);
743 for (
unsigned j = 0;
j < numArgs; ++
j) {
755 unsigned k = firstValueToIdx[newArguments[0][
j]];
759 bool shouldReplaceJ =
true;
760 unsigned replacement = k;
764 for (
unsigned i = 1; i < numLists; ++i)
766 shouldReplaceJ && (newArguments[i][k] == newArguments[i][
j]);
769 idxToReplacement[
j] = replacement;
773 for (
unsigned i = 0; i < numLists; ++i)
774 for (
unsigned j = 0;
j < numArgs; ++
j)
775 if (!idxToReplacement.contains(
j))
776 newArgumentsPruned[i].push_back(newArguments[i][
j]);
781 if (idxToReplacement.contains(idx)) {
784 block->
getArgument(numOldArguments + idxToReplacement[idx]);
786 toErase.push_back(numOldArguments + idx);
791 for (
unsigned idxToErase : llvm::reverse(toErase))
793 return newArgumentsPruned;
796 LogicalResult BlockMergeCluster::merge(
RewriterBase &rewriter) {
798 if (blocksToMerge.empty())
801 Block *leaderBlock = leaderData.block;
802 if (!operandsToMerge.empty()) {
815 blockIterators.reserve(blocksToMerge.size() + 1);
816 blockIterators.push_back(leaderBlock->
begin());
817 for (
Block *mergeBlock : blocksToMerge)
818 blockIterators.push_back(mergeBlock->begin());
822 1 + blocksToMerge.size(),
824 unsigned curOpIndex = 0;
827 unsigned nextOpOffset = it.value().first - curOpIndex;
828 curOpIndex = it.value().first;
831 for (
unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
833 std::advance(blockIter, nextOpOffset);
834 auto &operand = blockIter->getOpOperand(it.value().second);
835 newArguments[i][it.index()] = operand.get();
839 Value operandVal = operand.get();
848 numOldArguments, leaderBlock);
851 auto updatePredecessors = [&](
Block *block,
unsigned clusterIndex) {
853 predIt != predE; ++predIt) {
854 auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
855 unsigned succIndex = predIt.getSuccessorIndex();
856 branch.getSuccessorOperands(succIndex).append(
857 newArguments[clusterIndex]);
860 updatePredecessors(leaderBlock, 0);
861 for (
unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
862 updatePredecessors(blocksToMerge[i], i + 1);
866 for (
Block *block : blocksToMerge) {
885 for (
Block &block : llvm::drop_begin(region, 1))
888 bool mergedAnyBlocks =
false;
890 if (blocks.size() == 1)
894 for (
Block *block : blocks) {
895 BlockEquivalenceData data(block);
899 bool hasNonEmptyRegion = llvm::any_of(*block, [](
Operation &op) {
901 [](
Region ®ion) { return !region.empty(); });
903 if (hasNonEmptyRegion)
908 bool argHasExternalUsers = llvm::any_of(
910 return arg.isUsedOutsideOfBlock(block);
912 if (argHasExternalUsers)
916 bool addedToCluster =
false;
917 for (
auto &cluster : clusters)
918 if ((addedToCluster = succeeded(cluster.addToCluster(data))))
921 clusters.emplace_back(std::move(data));
923 for (
auto &cluster : clusters)
924 mergedAnyBlocks |= succeeded(cluster.merge(rewriter));
927 return success(mergedAnyBlocks);
934 llvm::SmallSetVector<Region *, 1> worklist;
935 for (
auto ®ion : regions)
936 worklist.insert(®ion);
937 bool anyChanged =
false;
938 while (!worklist.empty()) {
939 Region *region = worklist.pop_back_val();
941 worklist.insert(region);
946 for (
Block &block : *region)
947 for (
auto &op : block)
948 for (
auto &nestedRegion : op.getRegions())
949 worklist.insert(&nestedRegion);
952 return success(anyChanged);
970 predIt != predE; ++predIt) {
971 auto branch = dyn_cast<BranchOpInterface>((*predIt)->getTerminator());
976 unsigned succIndex = predIt.getSuccessorIndex();
980 commonValue = branchOperands[argIdx];
983 if (branchOperands[argIdx] != commonValue) {
990 if (commonValue && sameArg) {
991 argsToErase.push_back(argIdx);
999 for (
size_t argIdx : llvm::reverse(argsToErase)) {
1004 predIt != predE; ++predIt) {
1005 auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
1006 unsigned succIndex = predIt.getSuccessorIndex();
1008 succOperands.
erase(argIdx);
1011 return success(!argsToErase.empty());
1041 llvm::SmallSetVector<Region *, 1> worklist;
1042 for (
Region ®ion : regions)
1043 worklist.insert(®ion);
1044 bool anyChanged =
false;
1045 while (!worklist.empty()) {
1046 Region *region = worklist.pop_back_val();
1049 for (
Block &block : *region) {
1054 for (
Region &nestedRegion : op.getRegions())
1055 worklist.insert(&nestedRegion);
1058 return success(anyChanged);
1073 bool eliminatedOpsOrArgs = succeeded(
runRegionDCE(rewriter, regions));
1074 bool mergedIdenticalBlocks =
false;
1075 bool droppedRedundantArguments =
false;
1078 droppedRedundantArguments =
1081 return success(eliminatedBlocks || eliminatedOpsOrArgs ||
1082 mergedIdenticalBlocks || droppedRedundantArguments);
1097 op,
"unsupported case where operation and insertion point are not in "
1098 "the same basic block");
1103 "insertion point does not dominate op");
1111 options.omitUsesFromAbove =
false;
1114 options.omitBlockArguments =
true;
1120 assert(result.succeeded() &&
"expected a backward slice");
1124 if (slice.contains(insertionPoint)) {
1127 "cannot move dependencies before operation in backward slice of op");
1151 for (
auto value : values) {
1156 if (isa<BlockArgument>(value)) {
1159 "unsupported case of moving block argument before insertion point");
1166 "unsupported case of moving definition of value before an insertion "
1167 "point in a different basic block");
1169 prunedValues.push_back(value);
1177 options.omitUsesFromAbove =
false;
1180 options.omitBlockArguments =
true;
1185 for (
auto value : prunedValues) {
1187 assert(result.succeeded() &&
"expected a backward slice");
1192 if (slice.contains(insertionPoint)) {
1195 "cannot move dependencies before operation in backward slice of op");
static llvm::ManagedStatic< PassManagerOptions > options
static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter, Region ®ion)
Identify identical blocks within the given region and merge them, inserting new block arguments as ne...
static void propagateLiveness(Region ®ion, LiveMap &liveMap)
static void processValue(Value value, LiveMap &liveMap)
static bool ableToUpdatePredOperands(Block *block)
Returns true if the predecessor terminators of the given block can not have their operands updated.
static void eraseTerminatorSuccessorOperands(Operation *terminator, LiveMap &liveMap)
static LogicalResult dropRedundantArguments(RewriterBase &rewriter, Block &block)
If a block's argument is always the same across different invocations, then drop the argument and use...
static SmallVector< SmallVector< Value, 8 >, 2 > pruneRedundantArguments(const SmallVector< SmallVector< Value, 8 >, 2 > &newArguments, RewriterBase &rewriter, unsigned numOldArguments, Block *block)
Prunes the redundant list of new arguments.
static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap)
static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap)
static LogicalResult deleteDeadness(RewriterBase &rewriter, MutableArrayRef< Region > regions, LiveMap &liveMap)
This class represents an argument of a Block.
unsigned getArgNumber() const
Returns the number of this argument.
Block represents an ordered list of Operations.
OpListType::iterator iterator
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
BlockArgument getArgument(unsigned i)
unsigned getNumArguments()
pred_iterator pred_begin()
SuccessorRange getSuccessors()
iterator_range< pred_iterator > getPredecessors()
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
BlockArgListType getArguments()
void eraseArgument(unsigned index)
Erase the argument at 'index' and remove it from the argument list.
A class for computing basic dominance information.
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
This is a utility class for mapping one set of IR entities to another.
void map(Value from, Value to)
Inserts a new mapping for 'from' to 'to'.
void replaceAllUsesWith(ValueT &&newValue)
Replace all uses of 'this' value with the new value, updating anything in the IR that uses 'this' to ...
IRValueT get() const
Return the current value being used by this operand.
RAII guard to reset the insertion point of the builder when destroyed.
Block * createBlock(Region *parent, Region::iterator insertPt={}, TypeRange argTypes={}, ArrayRef< Location > locs={})
Add new block with 'argTypes' arguments and set the insertion point to the end of it.
Operation * clone(Operation &op, IRMapping &mapper)
Creates a deep copy of the specified operation, remapping any operands that use values outside of the...
void setInsertionPointToStart(Block *block)
Sets the insertion point to the start of the specified block.
This class represents an operand of an operation.
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
Set of flags used to control the behavior of the various IR print methods (e.g.
This is a value defined by a result of an operation.
unsigned getResultNumber() const
Returns the number of this result.
This class provides the API for ops that are known to be terminators.
A wrapper class that allows for printing an operation with a set of flags, useful to act as a "stream...
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Block * getSuccessor(unsigned index)
unsigned getNumSuccessors()
Block * getBlock()
Returns the operation block that contains this operation.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
MutableArrayRef< OpOperand > getOpOperands()
operand_range getOperands()
Returns an iterator on the underlying Value's.
SuccessorRange getSuccessors()
result_range getResults()
Implement a predecessor iterator for blocks.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Region * getParentRegion()
Return the region containing this region or nullptr if the region is attached to a top-level operatio...
bool isAncestor(Region *other)
Return true if this region is ancestor of the other region.
Operation * getParentOp()
Return the parent operation this region is attached to.
BlockListType & getBlocks()
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 coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
std::enable_if_t<!std::is_convertible< CallbackT, Twine >::value, LogicalResult > notifyMatchFailure(Location loc, CallbackT &&reasonCallback)
Used to notify the listener that the IR failed to be rewritten because of a match failure,...
void replaceOpUsesWithIf(Operation *from, ValueRange to, function_ref< bool(OpOperand &)> functor, bool *allUsesReplaced=nullptr)
virtual void eraseBlock(Block *block)
This method erases all operations in a block.
void replaceAllUsesWith(Value from, Value to)
Find uses of from and replace them with to.
virtual void eraseOp(Operation *op)
This method erases an operation that is known to have no uses.
void replaceUsesWithIf(Value from, Value to, function_ref< bool(OpOperand &)> functor, bool *allUsesReplaced=nullptr)
Find uses of from and replace them with to if the functor returns true.
void moveOpBefore(Operation *op, Operation *existingOp)
Unlink this operation from its current block and insert it right before existingOp which may be in th...
void mergeBlocks(Block *source, Block *dest, ValueRange argValues={})
Inline the operations of block 'source' into the end of block 'dest'.
This class models how operands are forwarded to block arguments in control flow.
void erase(unsigned subStart, unsigned subLen=1)
Erase operands forwarded to the successor.
unsigned getProducedOperandCount() const
Returns the amount of operands that are produced internally by the operation.
unsigned size() const
Returns the amount of operands passed to the successor.
OperandRange getForwardedOperands() const
Get the range of operands that are simply forwarded to the successor.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Type getType() const
Return the type of this value.
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Block * getParentBlock()
Return the Block in which this Value is defined.
Location getLoc() const
Return the location of this value.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Operation * getOwner() const
Return the owner of this operand.
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Include the generated interface declarations.
void replaceAllUsesInRegionWith(Value orig, Value replacement, Region ®ion)
Replace all uses of orig within the given region with replacement.
LogicalResult getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options={})
Fills backwardSlice with the computed backward slice (i.e.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
bool computeTopologicalSorting(MutableArrayRef< Operation * > ops, function_ref< bool(Value, Operation *)> isOperandReady=nullptr)
Compute a topological ordering of the given ops.
LogicalResult moveOperationDependencies(RewriterBase &rewriter, Operation *op, Operation *insertionPoint, DominanceInfo &dominance)
Move SSA values used within an operation before an insertion point, so that the operation itself (or ...
bool wouldOpBeTriviallyDead(Operation *op)
Return true if the given operation would be dead if unused, and has no side effects on memory that wo...
LogicalResult eraseUnreachableBlocks(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Erase the unreachable blocks within the provided regions.
SmallVector< Value > makeRegionIsolatedFromAbove(RewriterBase &rewriter, Region ®ion, llvm::function_ref< bool(Operation *)> cloneOperationIntoRegion=[](Operation *) { return false;})
Make a region isolated from above.
void getUsedValuesDefinedAbove(Region ®ion, Region &limit, SetVector< Value > &values)
Fill values with a list of values defined at the ancestors of the limit region and used within region...
LogicalResult runRegionDCE(RewriterBase &rewriter, MutableArrayRef< Region > regions)
This function returns success if any operations or arguments were deleted, failure otherwise.
LogicalResult simplifyRegions(RewriterBase &rewriter, MutableArrayRef< Region > regions, bool mergeBlocks=true)
Run a set of structural simplifications over the given regions.
LogicalResult moveValueDefinitions(RewriterBase &rewriter, ValueRange values, Operation *insertionPoint, DominanceInfo &dominance)
Move definitions of values before an insertion point.
void visitUsedValuesDefinedAbove(Region ®ion, Region &limit, function_ref< void(OpOperand *)> callback)
Calls callback for each use of a value within region or its descendants that was defined at the ances...
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Sorts all operations in toSort topologically while also considering region semantics.
static llvm::hash_code ignoreHashValue(Value)
Helper that can be used with computeHash above to ignore operation operands/result mapping.
static llvm::hash_code computeHash(Operation *op, function_ref< llvm::hash_code(Value)> hashOperands=[](Value v) { return hash_value(v);}, function_ref< llvm::hash_code(Value)> hashResults=[](Value v) { return hash_value(v);}, Flags flags=Flags::None)
Compute a hash for the given operation.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.