20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/PostOrderIterator.h"
22 #include "llvm/ADT/SmallSet.h"
30 for (
auto &use : llvm::make_early_inc_range(orig.
getUses())) {
31 if (region.
isAncestor(use.getOwner()->getParentRegion()))
39 "expected isolation limit to be an ancestor of the given region");
46 properAncestors.insert(reg);
52 if (properAncestors.count(operand.get().getParentRegion()))
59 for (
Region ®ion : regions)
66 values.insert(operand->
get());
72 for (
Region ®ion : regions)
88 std::deque<Value> worklist(initialCapturedValues.begin(),
89 initialCapturedValues.end());
95 while (!worklist.empty()) {
96 Value currValue = worklist.front();
98 if (visited.count(currValue))
100 visited.insert(currValue);
103 if (!definingOp || visitedOps.count(definingOp)) {
104 finalCapturedValues.insert(currValue);
107 visitedOps.insert(definingOp);
109 if (!cloneOperationIntoRegion(definingOp)) {
112 finalCapturedValues.insert(currValue);
119 if (visited.count(operand))
121 worklist.push_back(operand);
123 clonedOperations.push_back(definingOp);
140 for (
auto value : finalCapturedValues) {
141 newArgTypes.push_back(value.getType());
142 newArgLocs.push_back(value.getLoc());
146 Block *newEntryBlock =
153 return use.getOwner()->getBlock()->getParent() == ®ion;
155 for (
auto [arg, capturedVal] :
156 llvm::zip(newEntryBlockArgs.take_back(finalCapturedValues.size()),
157 finalCapturedValues)) {
158 map.
map(capturedVal, arg);
162 for (
auto clonedOp : clonedOperations) {
167 entryBlock, newEntryBlock,
169 return llvm::to_vector(finalCapturedValues);
182 llvm::df_iterator_default_set<Block *, 16> reachable;
184 bool erasedDeadBlocks =
false;
187 worklist.reserve(regions.size());
188 for (
Region ®ion : regions)
189 worklist.push_back(®ion);
190 while (!worklist.empty()) {
191 Region *region = worklist.pop_back_val();
196 if (std::next(region->
begin()) == region->
end()) {
199 worklist.push_back(®ion);
205 for (
Block *block : depth_first_ext(®ion->
front(), reachable))
210 for (
Block &block : llvm::make_early_inc_range(*region)) {
211 if (!reachable.count(&block)) {
212 block.dropAllDefinedValueUses();
214 erasedDeadBlocks =
true;
221 worklist.push_back(®ion);
225 return success(erasedDeadBlocks);
244 bool wasProvenLive(
Value value) {
247 if (
OpResult result = dyn_cast<OpResult>(value))
248 return wasProvenLive(result.getOwner());
249 return wasProvenLive(cast<BlockArgument>(value));
251 bool wasProvenLive(
BlockArgument arg) {
return liveValues.count(arg); }
252 void setProvedLive(
Value value) {
255 if (
OpResult result = dyn_cast<OpResult>(value))
256 return setProvedLive(result.getOwner());
257 setProvedLive(cast<BlockArgument>(value));
260 changed |= liveValues.insert(arg).second;
264 bool wasProvenLive(
Operation *op) {
return liveOps.count(op); }
265 void setProvedLive(
Operation *op) { changed |= liveOps.insert(op).second; }
268 void resetChanged() { changed =
false; }
269 bool hasChanged() {
return changed; }
272 bool changed =
false;
293 if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(owner))
294 if (
auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
295 return !liveMap.wasProvenLive(*arg);
303 if (isUseSpeciallyKnownDead(use, liveMap))
305 return liveMap.wasProvenLive(use.getOwner());
308 liveMap.setProvedLive(value);
315 liveMap.setProvedLive(op);
318 BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(op);
319 if (!branchInterface) {
322 liveMap.setProvedLive(arg);
330 branchInterface.getSuccessorOperands(i);
347 if (liveMap.wasProvenLive(op))
352 return liveMap.setProvedLive(op);
363 for (
Block *block : llvm::post_order(®ion.
front())) {
366 for (
Operation &op : llvm::reverse(block->getOperations()))
373 if (block->isEntryBlock())
376 for (
Value value : block->getArguments()) {
377 if (!liveMap.wasProvenLive(value))
385 BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(terminator);
390 succI < succE; succI++) {
395 unsigned succ = succE - succI - 1;
399 for (
unsigned argI = 0, argE = succOperands.
size(); argI < argE; ++argI) {
402 unsigned arg = argE - argI - 1;
403 if (!liveMap.wasProvenLive(successor->
getArgument(arg)))
404 succOperands.
erase(arg);
412 bool erasedAnything =
false;
413 for (
Region ®ion : regions) {
416 bool hasSingleBlock = llvm::hasSingleElement(region);
423 for (
Block *block : llvm::post_order(®ion.
front())) {
427 llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
428 if (!liveMap.wasProvenLive(&childOp)) {
429 erasedAnything =
true;
430 childOp.dropAllUses();
442 block.eraseArguments(
443 [&](
BlockArgument arg) {
return !liveMap.wasProvenLive(arg); });
446 return success(erasedAnything);
470 liveMap.resetChanged();
472 for (
Region ®ion : regions)
474 }
while (liveMap.hasChanged());
503 struct BlockEquivalenceData {
504 BlockEquivalenceData(
Block *block);
508 unsigned getOrderOf(
Value value)
const;
513 llvm::hash_code hash;
521 BlockEquivalenceData::BlockEquivalenceData(
Block *block)
522 : block(block), hash(0) {
526 opOrderIndex.try_emplace(&op, orderIt);
527 orderIt += numResults;
533 hash = llvm::hash_combine(hash, opHash);
537 unsigned BlockEquivalenceData::getOrderOf(
Value value)
const {
538 assert(value.
getParentBlock() == block &&
"expected value of this block");
545 OpResult result = cast<OpResult>(value);
547 assert(opOrderIt != opOrderIndex.end() &&
"expected op to have an order");
556 class BlockMergeCluster {
558 BlockMergeCluster(BlockEquivalenceData &&leaderData)
559 : leaderData(std::move(leaderData)) {}
570 BlockEquivalenceData leaderData;
573 llvm::SmallSetVector<Block *, 1> blocksToMerge;
577 std::set<std::pair<int, int>> operandsToMerge;
581 LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
582 if (leaderData.hash != blockData.hash)
584 Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
590 auto lhsIt = leaderBlock->
begin(), lhsE = leaderBlock->
end();
591 auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
592 for (
int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
594 if (!OperationEquivalence::isEquivalentTo(
595 &*lhsIt, &*rhsIt, OperationEquivalence::ignoreValueEquivalence,
597 OperationEquivalence::Flags::IgnoreLocations))
602 auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
603 for (
int operand : llvm::seq<int>(0, lhsIt->getNumOperands())) {
604 Value lhsOperand = lhsOperands[operand];
605 Value rhsOperand = rhsOperands[operand];
606 if (lhsOperand == rhsOperand)
615 if (lhsIsInBlock != rhsIsInBlock)
625 auto isValidSuccessorArg = [](
Block *block,
Value operand) {
626 if (operand.getDefiningOp() !=
627 operand.getParentBlock()->getTerminator())
630 operand.getParentBlock());
633 if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
634 !isValidSuccessorArg(mergeBlock, rhsOperand))
637 mismatchedOperands.emplace_back(opI, operand);
643 if (leaderData.getOrderOf(lhsOperand) != blockData.getOrderOf(rhsOperand))
653 if (rhsIt->isUsedOutsideOfBlock(mergeBlock) ||
654 lhsIt->isUsedOutsideOfBlock(leaderBlock)) {
659 if (lhsIt != lhsE || rhsIt != rhsE)
663 operandsToMerge.insert(mismatchedOperands.begin(), mismatchedOperands.end());
664 blocksToMerge.insert(blockData.block);
672 if (!isa<BranchOpInterface>((*it)->getTerminator()))
680 if (blocksToMerge.empty())
683 Block *leaderBlock = leaderData.block;
684 if (!operandsToMerge.empty()) {
697 blockIterators.reserve(blocksToMerge.size() + 1);
698 blockIterators.push_back(leaderBlock->
begin());
699 for (
Block *mergeBlock : blocksToMerge)
700 blockIterators.push_back(mergeBlock->begin());
704 1 + blocksToMerge.size(),
706 unsigned curOpIndex = 0;
708 unsigned nextOpOffset = it.value().first - curOpIndex;
709 curOpIndex = it.value().first;
712 for (
unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
714 std::advance(blockIter, nextOpOffset);
715 auto &operand = blockIter->getOpOperand(it.value().second);
716 newArguments[i][it.index()] = operand.get();
720 Value operandVal = operand.get();
727 auto updatePredecessors = [&](
Block *block,
unsigned clusterIndex) {
729 predIt != predE; ++predIt) {
730 auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
731 unsigned succIndex = predIt.getSuccessorIndex();
732 branch.getSuccessorOperands(succIndex).append(
733 newArguments[clusterIndex]);
736 updatePredecessors(leaderBlock, 0);
737 for (
unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
738 updatePredecessors(blocksToMerge[i], i + 1);
742 for (
Block *block : blocksToMerge) {
754 if (region.
empty() || llvm::hasSingleElement(region))
761 for (
Block &block : llvm::drop_begin(region, 1))
764 bool mergedAnyBlocks =
false;
766 if (blocks.size() == 1)
770 for (
Block *block : blocks) {
771 BlockEquivalenceData data(block);
775 bool hasNonEmptyRegion = llvm::any_of(*block, [](
Operation &op) {
777 [](
Region ®ion) { return !region.empty(); });
779 if (hasNonEmptyRegion)
783 bool addedToCluster =
false;
784 for (
auto &cluster : clusters)
785 if ((addedToCluster =
succeeded(cluster.addToCluster(data))))
788 clusters.emplace_back(std::move(data));
790 for (
auto &cluster : clusters)
791 mergedAnyBlocks |=
succeeded(cluster.merge(rewriter));
794 return success(mergedAnyBlocks);
801 llvm::SmallSetVector<Region *, 1> worklist;
802 for (
auto ®ion : regions)
803 worklist.insert(®ion);
804 bool anyChanged =
false;
805 while (!worklist.empty()) {
806 Region *region = worklist.pop_back_val();
808 worklist.insert(region);
813 for (
Block &block : *region)
814 for (
auto &op : block)
816 worklist.insert(&nestedRegion);
834 bool mergedIdenticalBlocks =
836 return success(eliminatedBlocks || eliminatedOpsOrArgs ||
837 mergedIdenticalBlocks);
844 for (
Block &b : region) {
845 if (blocks.count(&b) == 0) {
846 llvm::ReversePostOrderTraversal<Block *> traversal(&b);
847 blocks.insert(traversal.begin(), traversal.end());
850 assert(blocks.size() == region.
getBlocks().size() &&
851 "some blocks are not sorted");
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 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()
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.
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.
Block * createBlock(Region *parent, Region::iterator insertPt={}, TypeRange argTypes=std::nullopt, ArrayRef< Location > locs=std::nullopt)
Add new block with 'argTypes' arguments and set the insertion point to the end of it.
This class represents an operand of an operation.
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
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.
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()
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()
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.
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.
std::enable_if_t< std::is_same< RetT, void >::value, RetT > walk(FnT &&callback)
Walk the operations in this region.
BlockListType & getBlocks()
This class coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
virtual void replaceOpWithIf(Operation *op, ValueRange newValues, bool *allUsesReplaced, llvm::unique_function< bool(OpOperand &) const > functor)
This method replaces the uses of the results of op with the values in newValues when the provided fun...
virtual void eraseBlock(Block *block)
This method erases all operations in a block.
void mergeBlocks(Block *source, Block *dest, ValueRange argValues=std::nullopt)
Inline the operations of block 'source' into the end of block 'dest'.
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)
Find uses of from and replace them with to if the functor returns true.
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.
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.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
void replaceAllUsesInRegionWith(Value orig, Value replacement, Region ®ion)
Replace all uses of orig within the given region with replacement.
SetVector< Block * > getTopologicallySortedBlocks(Region ®ion)
Get a topologically sorted list of blocks of the given region.
bool computeTopologicalSorting(MutableArrayRef< Operation * > ops, function_ref< bool(Value, Operation *)> isOperandReady=nullptr)
Compute a topological ordering of the given ops.
LogicalResult simplifyRegions(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Run a set of structural simplifications over the given regions.
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
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.
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...
This class represents an efficient way to signal success or failure.
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.