18 #include "llvm/ADT/DepthFirstIterator.h" 19 #include "llvm/ADT/PostOrderIterator.h" 20 #include "llvm/ADT/SmallSet.h" 26 for (
auto &use : llvm::make_early_inc_range(orig.
getUses())) {
27 if (region.
isAncestor(use.getOwner()->getParentRegion()))
35 "expected isolation limit to be an ancestor of the given region");
42 properAncestors.insert(reg);
48 if (properAncestors.count(operand.get().getParentRegion()))
55 for (
Region ®ion : regions)
62 values.insert(operand->
get());
68 for (
Region ®ion : regions)
82 llvm::df_iterator_default_set<Block *, 16> reachable;
84 bool erasedDeadBlocks =
false;
87 worklist.reserve(regions.size());
88 for (
Region ®ion : regions)
89 worklist.push_back(®ion);
90 while (!worklist.empty()) {
91 Region *region = worklist.pop_back_val();
96 if (std::next(region->
begin()) == region->
end()) {
98 for (
Region ®ion : op.getRegions())
99 worklist.push_back(®ion);
105 for (
Block *block : depth_first_ext(®ion->
front(), reachable))
110 for (
Block &block : llvm::make_early_inc_range(*region)) {
111 if (!reachable.count(&block)) {
112 block.dropAllDefinedValueUses();
114 erasedDeadBlocks =
true;
120 for (
Region ®ion : op.getRegions())
121 worklist.push_back(®ion);
125 return success(erasedDeadBlocks);
148 return wasProvenLive(result.getOwner());
151 bool wasProvenLive(
BlockArgument arg) {
return liveValues.count(arg); }
152 void setProvedLive(
Value value) {
156 return setProvedLive(result.getOwner());
160 changed |= liveValues.insert(arg).second;
164 bool wasProvenLive(
Operation *op) {
return liveOps.count(op); }
165 void setProvedLive(
Operation *op) { changed |= liveOps.insert(op).second; }
168 void resetChanged() { changed =
false; }
169 bool hasChanged() {
return changed; }
172 bool changed =
false;
193 if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(owner))
194 if (
auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
195 return !liveMap.wasProvenLive(*arg);
205 return liveMap.wasProvenLive(use.getOwner());
208 liveMap.setProvedLive(value);
215 liveMap.setProvedLive(op);
218 BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(op);
219 if (!branchInterface) {
222 liveMap.setProvedLive(arg);
230 branchInterface.getSuccessorOperands(i);
247 if (liveMap.wasProvenLive(op))
252 return liveMap.setProvedLive(op);
263 for (
Block *block : llvm::post_order(®ion.
front())) {
266 for (
Operation &op : llvm::reverse(block->getOperations()))
273 if (block->isEntryBlock())
277 if (!liveMap.wasProvenLive(
value))
285 BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(terminator);
290 succI < succE; succI++) {
295 unsigned succ = succE - succI - 1;
299 for (
unsigned argI = 0, argE = succOperands.
size(); argI < argE; ++argI) {
302 unsigned arg = argE - argI - 1;
303 if (!liveMap.wasProvenLive(successor->
getArgument(arg)))
304 succOperands.
erase(arg);
312 bool erasedAnything =
false;
313 for (
Region ®ion : regions) {
316 bool hasSingleBlock = llvm::hasSingleElement(region);
323 for (
Block *block : llvm::post_order(®ion.
front())) {
327 llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
328 if (!liveMap.wasProvenLive(&childOp)) {
329 erasedAnything =
true;
330 childOp.dropAllUses();
342 block.eraseArguments(
343 [&](
BlockArgument arg) {
return !liveMap.wasProvenLive(arg); });
346 return success(erasedAnything);
370 liveMap.resetChanged();
372 for (
Region ®ion : regions)
374 }
while (liveMap.hasChanged());
403 struct BlockEquivalenceData {
404 BlockEquivalenceData(
Block *block);
413 llvm::hash_code hash;
421 BlockEquivalenceData::BlockEquivalenceData(
Block *block)
422 : block(block), hash(0) {
425 if (
unsigned numResults = op.getNumResults()) {
426 opOrderIndex.try_emplace(&op, orderIt);
427 orderIt += numResults;
433 hash = llvm::hash_combine(hash, opHash);
437 unsigned BlockEquivalenceData::getOrderOf(
Value value)
const {
438 assert(value.
getParentBlock() == block &&
"expected value of this block");
442 return arg.getArgNumber();
447 assert(opOrderIt != opOrderIndex.end() &&
"expected op to have an order");
456 class BlockMergeCluster {
458 BlockMergeCluster(BlockEquivalenceData &&leaderData)
459 : leaderData(std::move(leaderData)) {}
470 BlockEquivalenceData leaderData;
473 llvm::SmallSetVector<Block *, 1> blocksToMerge;
477 std::set<std::pair<int, int>> operandsToMerge;
481 LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
482 if (leaderData.hash != blockData.hash)
484 Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
490 auto lhsIt = leaderBlock->
begin(), lhsE = leaderBlock->
end();
491 auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
492 for (
int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
497 OperationEquivalence::Flags::IgnoreLocations))
502 auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
503 for (
int operand : llvm::seq<int>(0, lhsIt->getNumOperands())) {
504 Value lhsOperand = lhsOperands[operand];
505 Value rhsOperand = rhsOperands[operand];
506 if (lhsOperand == rhsOperand)
515 if (lhsIsInBlock != rhsIsInBlock)
525 auto isValidSuccessorArg = [](
Block *block,
Value operand) {
526 if (operand.getDefiningOp() !=
527 operand.getParentBlock()->getTerminator())
530 operand.getParentBlock());
533 if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
534 !isValidSuccessorArg(mergeBlock, rhsOperand))
537 mismatchedOperands.emplace_back(opI, operand);
543 if (leaderData.getOrderOf(lhsOperand) != blockData.getOrderOf(rhsOperand))
553 if (rhsIt->isUsedOutsideOfBlock(mergeBlock) ||
554 lhsIt->isUsedOutsideOfBlock(leaderBlock)) {
559 if (lhsIt != lhsE || rhsIt != rhsE)
563 operandsToMerge.insert(mismatchedOperands.begin(), mismatchedOperands.end());
564 blocksToMerge.insert(blockData.block);
572 if (!isa<BranchOpInterface>((*it)->getTerminator()))
580 if (blocksToMerge.empty())
583 Block *leaderBlock = leaderData.block;
584 if (!operandsToMerge.empty()) {
597 blockIterators.reserve(blocksToMerge.size() + 1);
598 blockIterators.push_back(leaderBlock->
begin());
599 for (
Block *mergeBlock : blocksToMerge)
600 blockIterators.push_back(mergeBlock->begin());
604 1 + blocksToMerge.size(),
606 unsigned curOpIndex = 0;
608 unsigned nextOpOffset = it.value().first - curOpIndex;
609 curOpIndex = it.value().first;
612 for (
unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
614 std::advance(blockIter, nextOpOffset);
615 auto &operand = blockIter->getOpOperand(it.value().second);
616 newArguments[i][it.index()] = operand.get();
620 Value operandVal = operand.get();
627 auto updatePredecessors = [&](
Block *block,
unsigned clusterIndex) {
629 predIt != predE; ++predIt) {
630 auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
631 unsigned succIndex = predIt.getSuccessorIndex();
632 branch.getSuccessorOperands(succIndex).append(
633 newArguments[clusterIndex]);
636 updatePredecessors(leaderBlock, 0);
637 for (
unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
638 updatePredecessors(blocksToMerge[i], i + 1);
642 for (
Block *block : blocksToMerge) {
654 if (region.
empty() || llvm::hasSingleElement(region))
661 for (
Block &block : llvm::drop_begin(region, 1))
664 bool mergedAnyBlocks =
false;
666 if (blocks.size() == 1)
670 for (
Block *block : blocks) {
671 BlockEquivalenceData data(block);
675 bool hasNonEmptyRegion = llvm::any_of(*block, [](
Operation &op) {
679 if (hasNonEmptyRegion)
683 bool addedToCluster =
false;
684 for (
auto &cluster : clusters)
685 if ((addedToCluster =
succeeded(cluster.addToCluster(data))))
688 clusters.emplace_back(std::move(data));
690 for (
auto &cluster : clusters)
691 mergedAnyBlocks |=
succeeded(cluster.merge(rewriter));
694 return success(mergedAnyBlocks);
701 llvm::SmallSetVector<Region *, 1> worklist;
702 for (
auto ®ion : regions)
703 worklist.insert(®ion);
704 bool anyChanged =
false;
705 while (!worklist.empty()) {
706 Region *region = worklist.pop_back_val();
708 worklist.insert(region);
713 for (
Block &block : *region)
714 for (
auto &op : block)
715 for (
auto &nestedRegion : op.getRegions())
716 worklist.insert(&nestedRegion);
734 bool mergedIdenticalBlocks =
736 return success(eliminatedBlocks || eliminatedOpsOrArgs ||
737 mergedIdenticalBlocks);
Include the generated interface declarations.
This class contains a list of basic blocks and a link to the parent operation it is attached to...
static bool ableToUpdatePredOperands(Block *block)
Returns true if the predecessor terminators of the given block can not have their operands updated...
bool wouldOpBeTriviallyDead(Operation *op)
Return true if the given operation would be dead if unused, and has no side effects on memory that wo...
Operation is a basic unit of execution within MLIR.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
BlockListType & getBlocks()
This is a value defined by a result of an operation.
Block represents an ordered list of Operations.
virtual void eraseOp(Operation *op)
This method erases an operation that is known to have no uses.
static bool isEquivalentTo(Operation *lhs, Operation *rhs, function_ref< LogicalResult(Value, Value)> mapOperands, function_ref< LogicalResult(Value, Value)> mapResults, Flags flags=Flags::None)
Compare two operations and return if they are equivalent.
iterator_range< pred_iterator > getPredecessors()
LogicalResult eraseUnreachableBlocks(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Erase the unreachable blocks within the provided regions.
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value...
This class provides the API for ops that are known to be terminators.
unsigned getNumSuccessors()
void erase(unsigned subStart, unsigned subLen=1)
Erase operands forwarded to the successor.
BlockArgument getArgument(unsigned i)
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 constexpr const bool value
LogicalResult runRegionDCE(RewriterBase &rewriter, MutableArrayRef< Region > regions)
This function returns success if any operations or arguments were deleted, failure otherwise...
Region * getParentRegion()
Return the region containing this region or nullptr if the region is attached to a top-level operatio...
MutableArrayRef< OpOperand > getOpOperands()
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
This class represents an efficient way to signal success or failure.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
unsigned size() const
Returns the amount of operands passed to the successor.
OpListType::iterator iterator
Block * getSuccessor(unsigned index)
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...
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.
void replaceAllUsesWith(ValueT &&newValue)
Replace all uses of 'this' value with the new value, updating anything in the IR that uses 'this' to ...
unsigned getNumArguments()
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
unsigned getResultNumber() const
Returns the number of this result.
Block * getParentBlock()
Return the Block in which this Value is defined.
void replaceAllUsesInRegionWith(Value orig, Value replacement, Region ®ion)
Replace all uses of orig within the given region with replacement.
IRValueT get() const
Return the current value being used by this operand.
This class models how operands are forwarded to block arguments in control flow.
This class represents an argument of a Block.
Location getLoc() const
Return the location of this value.
static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap)
std::enable_if< std::is_same< RetT, void >::value, RetT >::type walk(FnT &&callback)
Walk the operations in this region.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
static void propagateLiveness(Region ®ion, LiveMap &liveMap)
static llvm::hash_code ignoreHashValue(Value)
Helper that can be used with computeHash above to ignore operation operands/result mapping...
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
SuccessorRange getSuccessors()
LogicalResult simplifyRegions(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Run a set of structural simplifications over the given regions.
Type getType() const
Return the type of this value.
Operation * getOwner() const
Return the owner of this operand.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
This class represents an operand of an operation.
unsigned getProducedOperandCount() const
Returns the amount of operands that are produced internally by the operation.
static LogicalResult ignoreValueEquivalence(Value lhs, Value rhs)
Helper that can be used with isEquivalentTo above to ignore operation operands/result mapping...
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 eraseTerminatorSuccessorOperands(Operation *terminator, LiveMap &liveMap)
SuccessorRange getSuccessors()
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
static LogicalResult deleteDeadness(RewriterBase &rewriter, MutableArrayRef< Region > regions, LiveMap &liveMap)
result_range getResults()
static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap)
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
static void processValue(Value value, LiveMap &liveMap)
This class coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
bool isAncestor(Region *other)
Return true if this region is ancestor of the other region.
virtual void eraseBlock(Block *block)
This method erases all operations in a block.
pred_iterator pred_begin()