20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/PostOrderIterator.h"
29 for (
auto &use : llvm::make_early_inc_range(orig.
getUses())) {
30 if (region.
isAncestor(use.getOwner()->getParentRegion()))
38 "expected isolation limit to be an ancestor of the given region");
45 properAncestors.insert(reg);
51 if (properAncestors.count(operand.get().getParentRegion()))
58 for (
Region ®ion : regions)
65 values.insert(operand->
get());
71 for (
Region ®ion : regions)
87 std::deque<Value> worklist(initialCapturedValues.begin(),
88 initialCapturedValues.end());
94 while (!worklist.empty()) {
95 Value currValue = worklist.front();
97 if (visited.count(currValue))
99 visited.insert(currValue);
102 if (!definingOp || visitedOps.count(definingOp)) {
103 finalCapturedValues.insert(currValue);
106 visitedOps.insert(definingOp);
108 if (!cloneOperationIntoRegion(definingOp)) {
111 finalCapturedValues.insert(currValue);
118 if (visited.count(operand))
120 worklist.push_back(operand);
122 clonedOperations.push_back(definingOp);
139 for (
auto value : finalCapturedValues) {
140 newArgTypes.push_back(value.getType());
141 newArgLocs.push_back(value.getLoc());
145 Block *newEntryBlock =
152 return use.getOwner()->getBlock()->getParent() == ®ion;
154 for (
auto [arg, capturedVal] :
155 llvm::zip(newEntryBlockArgs.take_back(finalCapturedValues.size()),
156 finalCapturedValues)) {
157 map.
map(capturedVal, arg);
161 for (
auto *clonedOp : clonedOperations) {
166 entryBlock, newEntryBlock,
168 return llvm::to_vector(finalCapturedValues);
181 llvm::df_iterator_default_set<Block *, 16> reachable;
183 bool erasedDeadBlocks =
false;
186 worklist.reserve(regions.size());
187 for (
Region ®ion : regions)
188 worklist.push_back(®ion);
189 while (!worklist.empty()) {
190 Region *region = worklist.pop_back_val();
195 if (std::next(region->
begin()) == region->
end()) {
198 worklist.push_back(®ion);
204 for (
Block *block : depth_first_ext(®ion->
front(), reachable))
209 for (
Block &block : llvm::make_early_inc_range(*region)) {
210 if (!reachable.count(&block)) {
211 block.dropAllDefinedValueUses();
213 erasedDeadBlocks =
true;
220 worklist.push_back(®ion);
224 return success(erasedDeadBlocks);
243 bool wasProvenLive(
Value value) {
246 if (
OpResult result = dyn_cast<OpResult>(value))
247 return wasProvenLive(result.getOwner());
248 return wasProvenLive(cast<BlockArgument>(value));
250 bool wasProvenLive(
BlockArgument arg) {
return liveValues.count(arg); }
251 void setProvedLive(
Value value) {
254 if (
OpResult result = dyn_cast<OpResult>(value))
255 return setProvedLive(result.getOwner());
256 setProvedLive(cast<BlockArgument>(value));
259 changed |= liveValues.insert(arg).second;
263 bool wasProvenLive(
Operation *op) {
return liveOps.count(op); }
264 void setProvedLive(
Operation *op) { changed |= liveOps.insert(op).second; }
267 void resetChanged() { changed =
false; }
268 bool hasChanged() {
return changed; }
271 bool changed =
false;
292 if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(owner))
293 if (
auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
294 return !liveMap.wasProvenLive(*arg);
302 if (isUseSpeciallyKnownDead(use, liveMap))
304 return liveMap.wasProvenLive(use.getOwner());
307 liveMap.setProvedLive(value);
314 liveMap.setProvedLive(op);
317 BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(op);
318 if (!branchInterface) {
321 liveMap.setProvedLive(arg);
329 branchInterface.getSuccessorOperands(i);
346 if (liveMap.wasProvenLive(op))
351 return liveMap.setProvedLive(op);
362 for (
Block *block : llvm::post_order(®ion.
front())) {
365 for (
Operation &op : llvm::reverse(block->getOperations()))
372 if (block->isEntryBlock())
375 for (
Value value : block->getArguments()) {
376 if (!liveMap.wasProvenLive(value))
384 BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(terminator);
389 succI < succE; succI++) {
394 unsigned succ = succE - succI - 1;
398 for (
unsigned argI = 0, argE = succOperands.
size(); argI < argE; ++argI) {
401 unsigned arg = argE - argI - 1;
402 if (!liveMap.wasProvenLive(successor->
getArgument(arg)))
403 succOperands.
erase(arg);
411 bool erasedAnything =
false;
412 for (
Region ®ion : regions) {
415 bool hasSingleBlock = llvm::hasSingleElement(region);
422 for (
Block *block : llvm::post_order(®ion.
front())) {
426 llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
427 if (!liveMap.wasProvenLive(&childOp)) {
428 erasedAnything =
true;
429 childOp.dropAllUses();
432 erasedAnything |= succeeded(
441 block.eraseArguments(
442 [&](
BlockArgument arg) {
return !liveMap.wasProvenLive(arg); });
445 return success(erasedAnything);
469 liveMap.resetChanged();
471 for (
Region ®ion : regions)
473 }
while (liveMap.hasChanged());
502 struct BlockEquivalenceData {
503 BlockEquivalenceData(
Block *block);
507 unsigned getOrderOf(
Value value)
const;
512 llvm::hash_code hash;
520 BlockEquivalenceData::BlockEquivalenceData(
Block *block)
521 : block(block), hash(0) {
525 opOrderIndex.try_emplace(&op, orderIt);
526 orderIt += numResults;
532 hash = llvm::hash_combine(hash, opHash);
536 unsigned BlockEquivalenceData::getOrderOf(
Value value)
const {
537 assert(value.
getParentBlock() == block &&
"expected value of this block");
544 OpResult result = cast<OpResult>(value);
546 assert(opOrderIt != opOrderIndex.end() &&
"expected op to have an order");
555 class BlockMergeCluster {
557 BlockMergeCluster(BlockEquivalenceData &&leaderData)
558 : leaderData(std::move(leaderData)) {}
562 LogicalResult addToCluster(BlockEquivalenceData &blockData);
569 BlockEquivalenceData leaderData;
572 llvm::SmallSetVector<Block *, 1> blocksToMerge;
576 std::set<std::pair<int, int>> operandsToMerge;
580 LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
581 if (leaderData.hash != blockData.hash)
583 Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
589 auto lhsIt = leaderBlock->
begin(), lhsE = leaderBlock->
end();
590 auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
591 for (
int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
593 if (!OperationEquivalence::isEquivalentTo(
594 &*lhsIt, &*rhsIt, OperationEquivalence::ignoreValueEquivalence,
596 OperationEquivalence::Flags::IgnoreLocations))
601 auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
602 for (
int operand : llvm::seq<int>(0, lhsIt->getNumOperands())) {
603 Value lhsOperand = lhsOperands[operand];
604 Value rhsOperand = rhsOperands[operand];
605 if (lhsOperand == rhsOperand)
614 if (lhsIsInBlock != rhsIsInBlock)
624 auto isValidSuccessorArg = [](
Block *block,
Value operand) {
625 if (operand.getDefiningOp() !=
626 operand.getParentBlock()->getTerminator())
629 operand.getParentBlock());
632 if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
633 !isValidSuccessorArg(mergeBlock, rhsOperand))
636 mismatchedOperands.emplace_back(opI, operand);
642 if (leaderData.getOrderOf(lhsOperand) != blockData.getOrderOf(rhsOperand))
652 if (rhsIt->isUsedOutsideOfBlock(mergeBlock) ||
653 lhsIt->isUsedOutsideOfBlock(leaderBlock)) {
658 if (lhsIt != lhsE || rhsIt != rhsE)
662 operandsToMerge.insert(mismatchedOperands.begin(), mismatchedOperands.end());
663 blocksToMerge.insert(blockData.block);
671 if (!isa<BranchOpInterface>((*it)->getTerminator()))
677 LogicalResult BlockMergeCluster::merge(
RewriterBase &rewriter) {
679 if (blocksToMerge.empty())
682 Block *leaderBlock = leaderData.block;
683 if (!operandsToMerge.empty()) {
696 blockIterators.reserve(blocksToMerge.size() + 1);
697 blockIterators.push_back(leaderBlock->
begin());
698 for (
Block *mergeBlock : blocksToMerge)
699 blockIterators.push_back(mergeBlock->begin());
703 1 + blocksToMerge.size(),
705 unsigned curOpIndex = 0;
707 unsigned nextOpOffset = it.value().first - curOpIndex;
708 curOpIndex = it.value().first;
711 for (
unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
713 std::advance(blockIter, nextOpOffset);
714 auto &operand = blockIter->getOpOperand(it.value().second);
715 newArguments[i][it.index()] = operand.get();
719 Value operandVal = operand.get();
726 auto updatePredecessors = [&](
Block *block,
unsigned clusterIndex) {
728 predIt != predE; ++predIt) {
729 auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
730 unsigned succIndex = predIt.getSuccessorIndex();
731 branch.getSuccessorOperands(succIndex).append(
732 newArguments[clusterIndex]);
735 updatePredecessors(leaderBlock, 0);
736 for (
unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
737 updatePredecessors(blocksToMerge[i], i + 1);
741 for (
Block *block : blocksToMerge) {
753 if (region.
empty() || llvm::hasSingleElement(region))
760 for (
Block &block : llvm::drop_begin(region, 1))
763 bool mergedAnyBlocks =
false;
765 if (blocks.size() == 1)
769 for (
Block *block : blocks) {
770 BlockEquivalenceData data(block);
774 bool hasNonEmptyRegion = llvm::any_of(*block, [](
Operation &op) {
776 [](
Region ®ion) { return !region.empty(); });
778 if (hasNonEmptyRegion)
782 bool addedToCluster =
false;
783 for (
auto &cluster : clusters)
784 if ((addedToCluster = succeeded(cluster.addToCluster(data))))
787 clusters.emplace_back(std::move(data));
789 for (
auto &cluster : clusters)
790 mergedAnyBlocks |= succeeded(cluster.merge(rewriter));
793 return success(mergedAnyBlocks);
800 llvm::SmallSetVector<Region *, 1> worklist;
801 for (
auto ®ion : regions)
802 worklist.insert(®ion);
803 bool anyChanged =
false;
804 while (!worklist.empty()) {
805 Region *region = worklist.pop_back_val();
807 worklist.insert(region);
812 for (
Block &block : *region)
813 for (
auto &op : block)
815 worklist.insert(&nestedRegion);
818 return success(anyChanged);
833 bool eliminatedOpsOrArgs = succeeded(
runRegionDCE(rewriter, regions));
834 bool mergedIdenticalBlocks =
false;
837 return success(eliminatedBlocks || eliminatedOpsOrArgs ||
838 mergedIdenticalBlocks);
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.
BlockListType & getBlocks()
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...
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 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, bool *allUsesReplaced=nullptr)
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.
void replaceAllUsesInRegionWith(Value orig, Value replacement, Region ®ion)
Replace all uses of orig within the given region with replacement.
bool computeTopologicalSorting(MutableArrayRef< Operation * > ops, function_ref< bool(Value, Operation *)> isOperandReady=nullptr)
Compute a topological ordering of the given ops.
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.
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...
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.