49#include "llvm/ADT/STLExtras.h"
50#include "llvm/Support/Debug.h"
51#include "llvm/Support/DebugLog.h"
58#define DEBUG_TYPE "remove-dead-values"
61#define GEN_PASS_DEF_REMOVEDEADVALUESPASS
62#include "mlir/Transforms/Passes.h.inc"
78struct FunctionToCleanUp {
79 FunctionOpInterface funcOp;
80 BitVector nonLiveArgs;
81 BitVector nonLiveRets;
84struct ResultsToCleanup {
89struct OperandsToCleanup {
93 Operation *callee =
nullptr;
96 bool replaceWithPoison =
false;
99struct BlockArgsToCleanup {
101 BitVector nonLiveArgs;
104struct SuccessorOperandsToCleanup {
105 BranchOpInterface branch;
106 unsigned successorIndex;
107 BitVector nonLiveOperands;
110struct RDVFinalCleanupList {
111 SmallVector<Operation *> operations;
112 SmallVector<FunctionToCleanUp> functions;
113 SmallVector<OperandsToCleanup> operands;
114 SmallVector<ResultsToCleanup> results;
115 SmallVector<BlockArgsToCleanup> blocks;
116 SmallVector<SuccessorOperandsToCleanup> successorOperands;
125 for (
Value value : values) {
126 if (nonLiveSet.contains(value)) {
127 LDBG() <<
"Value " << value <<
" is already marked non-live (dead)";
133 LDBG() <<
"Value " << value
134 <<
" has no liveness info, conservatively considered live";
138 LDBG() <<
"Value " << value <<
" is live according to liveness analysis";
141 LDBG() <<
"Value " << value <<
" is dead according to liveness analysis";
150 BitVector lives(values.size(),
true);
152 for (
auto [
index, value] : llvm::enumerate(values)) {
153 if (nonLiveSet.contains(value)) {
155 LDBG() <<
"Value " << value
156 <<
" is already marked non-live (dead) at index " <<
index;
168 LDBG() <<
"Value " << value <<
" at index " <<
index
169 <<
" has no liveness info, conservatively considered live";
174 LDBG() <<
"Value " << value <<
" at index " <<
index
175 <<
" is dead according to liveness analysis";
177 LDBG() <<
"Value " << value <<
" at index " <<
index
178 <<
" is live according to liveness analysis";
189 const BitVector &nonLive) {
190 for (
auto [
index,
result] : llvm::enumerate(range)) {
193 nonLiveSet.insert(
result);
194 LDBG() <<
"Marking value " <<
result <<
" as non-live (dead) at index "
216 RDVFinalCleanupList &cl) {
217 if (isa<SymbolOpInterface>(op) && !symbolUserMap.
useEmpty(op)) {
218 LDBG() <<
"Simple op is a symbol with known users, preserving it: "
227 bool hasDeadOperand =
228 markLives(op->
getOperands(), nonLiveSet, la).flip().any();
229 if (hasDeadOperand) {
230 LDBG() <<
"Simple op has dead operands, so the op must be dead: "
233 assert(!hasLive(op->
getResults(), nonLiveSet, la) &&
234 "expected the op to have no live results");
235 cl.operations.push_back(op);
236 collectNonLiveValues(nonLiveSet, op->
getResults(),
242 LDBG() <<
"Simple op is not memory effect free or has live results, "
250 <<
"Simple op has all dead results and is memory effect free, scheduling "
253 cl.operations.push_back(op);
254 collectNonLiveValues(nonLiveSet, op->
getResults(),
269static void processFuncOp(FunctionOpInterface funcOp,
272 RDVFinalCleanupList &cl) {
273 LDBG() <<
"Processing function op: "
277 if (funcOp.isPublic() || funcOp.isExternal() ||
279 LDBG() <<
"Function is public, external, or has unknown users, skipping: "
280 << funcOp.getOperation()->getName();
284 if (!llvm::all_of(users, llvm::IsaPred<CallOpInterface>)) {
292 BitVector nonLiveArgs = markLives(arguments, nonLiveSet, la);
293 nonLiveArgs = nonLiveArgs.flip();
296 for (
auto [
index, arg] : llvm::enumerate(arguments))
297 if (arg && nonLiveArgs[
index])
298 nonLiveSet.insert(arg);
308 cl.operands.push_back({callOp, BitVector(callOp->getNumOperands(),
false),
309 funcOp.getOperation()});
335 size_t numReturns = funcOp.getNumResults();
336 BitVector nonLiveRets(numReturns,
true);
340 BitVector liveCallRets = markLives(
341 cast<CallOpInterface>(callOp).getForwardedResults(), nonLiveSet, la);
342 nonLiveRets &= liveCallRets.flip();
348 for (
Block &block : funcOp.getBlocks()) {
349 Operation *returnOp = block.getTerminator();
353 cl.operands.push_back({returnOp, nonLiveRets});
357 cl.functions.push_back({funcOp, nonLiveArgs, nonLiveRets});
367 cast<CallOpInterface>(callOp).getForwardedResults();
368 BitVector nonLiveCallResults(callOp->getNumResults(),
false);
369 for (
int index : nonLiveRets.set_bits())
370 nonLiveCallResults.set(forwardedResults[
index].getResultNumber());
371 cl.results.push_back({callOp, nonLiveCallResults});
372 collectNonLiveValues(nonLiveSet, callOp->getResults(), nonLiveCallResults);
395static void processRegionBranchOp(RegionBranchOpInterface regionBranchOp,
398 RDVFinalCleanupList &cl) {
399 LDBG() <<
"Processing region branch op: "
409 !hasLive(regionBranchOp->getResults(), nonLiveSet, la)) {
410 cl.operations.push_back(regionBranchOp.getOperation());
434 regionBranchOp.getSuccessorOperandInputMapping(operandToSuccessorInputs);
437 for (
auto [opOperand, successorInputs] : operandToSuccessorInputs) {
440 auto markOperandDead = [&opOperand = opOperand, &deadOperandsPerOp]() {
445 BitVector &deadOperands =
447 .try_emplace(opOperand->getOwner(),
448 opOperand->getOwner()->getNumOperands(),
false)
450 deadOperands.set(opOperand->getOperandNumber());
454 if (!hasLive(opOperand->get(), nonLiveSet, la)) {
461 if (!hasLive(successorInputs, nonLiveSet, la))
465 for (
auto [op, deadOperands] : deadOperandsPerOp) {
466 cl.operands.push_back(
467 {op, deadOperands,
nullptr,
true});
485 RDVFinalCleanupList &cl) {
486 LDBG() <<
"Processing branch op: " << *branchOp;
489 BitVector deadNonForwardedOperands =
490 markLives(branchOp->getOperands(), nonLiveSet, la).flip();
491 unsigned numSuccessors = branchOp->getNumSuccessors();
492 for (
unsigned succIdx = 0; succIdx < numSuccessors; ++succIdx) {
494 branchOp.getSuccessorOperands(succIdx);
497 deadNonForwardedOperands[opOperand.getOperandNumber()] =
false;
499 if (deadNonForwardedOperands.any()) {
500 cl.operations.push_back(branchOp.getOperation());
504 for (
unsigned succIdx = 0; succIdx < numSuccessors; ++succIdx) {
509 branchOp.getSuccessorOperands(succIdx);
511 for (
unsigned operandIdx = 0; operandIdx < successorOperands.
size();
513 operandValues.push_back(successorOperands[operandIdx]);
517 BitVector successorNonLive =
518 markLives(operandValues, nonLiveSet, la).flip();
519 collectNonLiveValues(nonLiveSet, successorBlock->
getArguments(),
523 cl.blocks.push_back({successorBlock, successorNonLive});
524 cl.successorOperands.push_back({branchOp, succIdx, successorNonLive});
533 return ub::PoisonOp::create(
b, value.
getLoc(), value.
getType()).getResult();
539 void notifyOperationErased(Operation *op)
override {
540 if (
auto poisonOp = dyn_cast<ub::PoisonOp>(op))
541 poisonOps.erase(poisonOp);
543 void notifyOperationInserted(Operation *op,
544 OpBuilder::InsertPoint previous)
override {
545 if (
auto poisonOp = dyn_cast<ub::PoisonOp>(op))
546 poisonOps.insert(poisonOp);
554static void cleanUpDeadVals(
MLIRContext *ctx, RDVFinalCleanupList &list) {
555 LDBG() <<
"Starting cleanup of dead values...";
560 TrackingListener listener;
566 LDBG() <<
"Replacing dead operands with poison in " << list.operands.size()
568 for (OperandsToCleanup &o : list.operands) {
569 if (!o.replaceWithPoison || !o.nonLive.any())
572 os <<
"Replacing non-live operands [";
573 llvm::interleaveComma(o.nonLive.set_bits(), os);
574 os <<
"] with poison in operation: "
578 rewriter.setInsertionPoint(o.op);
579 for (
auto deadIdx : o.nonLive.set_bits()) {
581 assert(operand &&
"expected non-null operand for poison replacement");
582 o.op->
setOperand(deadIdx, createPoisonedValue(rewriter, operand));
588 LDBG() <<
"Cleaning up " << list.blocks.size() <<
" block argument lists";
589 for (
auto &
b : list.blocks) {
591 if (
b.b->getNumArguments() !=
b.nonLiveArgs.size())
594 os <<
"Erasing non-live arguments [";
595 llvm::interleaveComma(
b.nonLiveArgs.set_bits(), os);
596 os <<
"] from block #" <<
b.b->computeBlockNumber() <<
" in region #"
597 <<
b.b->getParent()->getRegionNumber() <<
" of operation "
603 for (
int i =
b.nonLiveArgs.size() - 1; i >= 0; --i) {
604 if (!
b.nonLiveArgs[i])
606 b.b->getArgument(i).dropAllUses();
607 b.b->eraseArgument(i);
612 LDBG() <<
"Cleaning up " << list.successorOperands.size()
613 <<
" successor operand lists";
614 for (
auto &op : list.successorOperands) {
616 op.branch.getSuccessorOperands(op.successorIndex);
618 if (successorOperands.
size() != op.nonLiveOperands.size())
621 os <<
"Erasing non-live successor operands [";
622 llvm::interleaveComma(op.nonLiveOperands.set_bits(), os);
623 os <<
"] from successor " << op.successorIndex <<
" of branch: "
628 for (
int i = successorOperands.
size() - 1; i >= 0; --i) {
629 if (!op.nonLiveOperands[i])
631 successorOperands.
erase(i);
636 LDBG() <<
"Cleaning up " << list.functions.size() <<
" functions";
641 for (
auto &f : list.functions) {
642 LDBG() <<
"Cleaning up function: " << f.funcOp.getName() <<
" ("
643 << f.funcOp.getOperation() <<
")";
645 os <<
" Erasing non-live arguments [";
646 llvm::interleaveComma(f.nonLiveArgs.set_bits(), os);
648 os <<
" Erasing non-live return values [";
649 llvm::interleaveComma(f.nonLiveRets.set_bits(), os);
656 for (
auto deadIdx : f.nonLiveArgs.set_bits()) {
661 rewriter.setInsertionPointToStart(arg.
getOwner());
664 rewriter.replaceAllUsesWith(arg, poison);
669 if (succeeded(f.funcOp.eraseArguments(f.nonLiveArgs))) {
671 if (f.nonLiveArgs.any())
672 erasedFuncArgs.try_emplace(f.funcOp.getOperation(), f.nonLiveArgs);
674 LDBG() <<
"Failed to erase arguments for function: "
675 << f.funcOp.getName();
677 (
void)f.funcOp.eraseResults(f.nonLiveRets);
681 LDBG() <<
"Cleaning up " << list.operands.size() <<
" operand lists";
682 for (OperandsToCleanup &o : list.operands) {
683 if (o.replaceWithPoison)
688 bool handledAsCall =
false;
689 if (o.callee && isa<CallOpInterface>(o.op)) {
690 auto call = cast<CallOpInterface>(o.op);
691 auto it = erasedFuncArgs.find(o.callee);
692 if (it != erasedFuncArgs.end()) {
693 const BitVector &deadArgIdxs = it->second;
697 for (
unsigned argIdx : llvm::reverse(deadArgIdxs.set_bits()))
703 if (o.nonLive.any()) {
705 int operandOffset = call.getArgOperands().getBeginOperandIndex();
706 for (
int argIdx : deadArgIdxs.set_bits()) {
707 int operandNumber = operandOffset + argIdx;
708 if (operandNumber <
static_cast<int>(o.nonLive.size()))
709 o.nonLive.reset(operandNumber);
712 handledAsCall =
true;
719 if (!handledAsCall && o.nonLive.any()) {
721 os <<
"Erasing non-live operands [";
722 llvm::interleaveComma(o.nonLive.set_bits(), os);
723 os <<
"] from operation: "
727 rewriter.eraseOperands(o.op, o.nonLive);
732 LDBG() <<
"Cleaning up " << list.results.size() <<
" result lists";
733 for (
auto &r : list.results) {
735 os <<
"Erasing non-live results [";
736 llvm::interleaveComma(r.nonLive.set_bits(), os);
737 os <<
"] from operation: "
744 rewriter.setInsertionPoint(r.op);
745 for (
auto deadIdx : r.nonLive.set_bits()) {
749 rewriter.replaceAllUsesWith(
result,
750 createPoisonedValue(rewriter,
result));
752 rewriter.eraseOpResults(r.op, r.nonLive);
756 LDBG() <<
"Cleaning up " << list.operations.size() <<
" operations";
758 LDBG() <<
"Erasing operation: "
761 rewriter.setInsertionPoint(op);
764 ub::UnreachableOp::create(rewriter, op->
getLoc());
777 for (
Value opResult : opResults) {
780 if (opResult.use_empty())
783 rewriter.setInsertionPoint(op);
784 Value poisonedValue = createPoisonedValue(rewriter, opResult);
785 rewriter.replaceAllUsesWith(opResult, poisonedValue);
789 rewriter.eraseOp(op);
793 for (ub::PoisonOp poisonOp : listener.poisonOps) {
794 if (poisonOp.use_empty())
798 LDBG() <<
"Finished cleanup of dead values";
801struct RemoveDeadValues
803 using impl::RemoveDeadValuesPassBase<
804 RemoveDeadValues>::RemoveDeadValuesPassBase;
805 void runOnOperation()
override;
809void RemoveDeadValues::runOnOperation() {
810 auto &la = getAnalysis<RunLivenessAnalysis>();
811 Operation *root = getOperation();
817 SymbolTableCollection symbolTableCollection;
818 SymbolUserMap symbolUserMap(symbolTableCollection, root);
826 RDVFinalCleanupList finalCleanupList;
828 root->
walk([&](Operation *op) {
834 if (
auto funcOp = dyn_cast<FunctionOpInterface>(op)) {
835 processFuncOp(funcOp, symbolUserMap, la, deadVals, finalCleanupList);
836 }
else if (
auto regionBranchOp = dyn_cast<RegionBranchOpInterface>(op)) {
837 processRegionBranchOp(regionBranchOp, la, deadVals, finalCleanupList);
838 }
else if (
auto branchOp = dyn_cast<BranchOpInterface>(op)) {
839 processBranchOp(branchOp, la, deadVals, finalCleanupList);
840 }
else if (op->
hasTrait<::mlir::OpTrait::IsTerminator>()) {
843 }
else if (isa<CallOpInterface>(op)) {
847 processSimpleOp(op, la, symbolUserMap, deadVals, finalCleanupList);
852 cleanUpDeadVals(context, finalCleanupList);
858 RewritePatternSet owningPatterns(context);
860 root->
walk([&](RegionBranchOpInterface regionBranchOp) {
861 Operation *op = regionBranchOp.getOperation();
865 if (populatedPatterns.insert(*info).second)
866 info->getCanonicalizationPatterns(owningPatterns, context);
868 FrozenRewritePatternSet patterns(std::move(owningPatterns));
873 SmallVector<Operation *> opsToCanonicalize;
874 region.walk([&](RegionBranchOpInterface regionBranchOp) {
875 opsToCanonicalize.push_back(regionBranchOp.getOperation());
879 GreedyRewriteConfig config;
882 root->
emitError(
"greedy pattern rewrite failed to converge");
883 return signalPassFailure();
This class represents an argument of a Block.
Location getLoc() const
Return the location for this argument.
Block * getOwner() const
Returns the block that owns this argument.
Block represents an ordered list of Operations.
BlockArgListType getArguments()
Block * getSuccessor(unsigned i)
GreedyRewriteConfig & setScope(Region *scope)
This class coordinates rewriting a piece of IR outside of a pattern rewrite, providing a way to keep ...
MLIRContext is the top-level object for a collection of MLIR operations.
This class provides a mutable adaptor for a range of operands.
void erase(unsigned subStart, unsigned subLen=1)
Erase the operands within the given sub-range.
This class helps build Operations.
This class represents an operand of an operation.
Set of flags used to control the behavior of the various IR print methods (e.g.
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.
Value getOperand(unsigned idx)
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
void dropAllUses()
Drop all uses of results of this operation.
void setOperand(unsigned idx, Value value)
Location getLoc()
The source location the operation was defined or derived from.
std::optional< RegisteredOperationName > getRegisteredInfo()
If this operation has a registered operation description, return it.
unsigned getNumOperands()
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
operand_range getOperands()
Returns an iterator on the underlying Value's.
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
result_range getResults()
MLIRContext * getContext()
Return the context this operation is associated with.
unsigned getNumResults()
Return the number of results held by this operation.
This class implements the result iterators for the Operation class.
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.
MutableOperandRange getMutableForwardedOperands() const
Get the range of operands that are simply forwarded to the successor.
unsigned size() const
Returns the amount of operands passed to the successor.
This class represents a map of symbols to users, and provides efficient implementations of symbol que...
bool useEmpty(Operation *symbol) const
Return true if the given symbol has no uses within this map's scope.
bool areAllUsesVisible(Operation *symbol) const
Return true if all uses of the symbol within the IR are within this scope.
ArrayRef< Operation * > getUsers(Operation *symbol) const
Return the users of the provided symbol operation within this map's scope.
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...
bool use_empty() const
Returns true if this value has no uses.
Type getType() const
Return the type of this value.
Location getLoc() const
Return the location of this value.
Include the generated interface declarations.
DenseMap< OpOperand *, SmallVector< Value > > RegionBranchSuccessorMapping
A mapping from successor operands to successor inputs.
llvm::DenseSet< ValueT, ValueInfoT > DenseSet
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
LogicalResult applyOpPatternsGreedily(ArrayRef< Operation * > ops, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr, bool *allErased=nullptr)
Rewrite the specified ops by repeatedly applying the highest benefit patterns in a greedy worklist dr...
llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT > DenseMap
This trait indicates that a terminator operation is "return-like".
This lattice represents, for a given value, whether or not it is "live".
Runs liveness analysis on the IR defined by op.
const Liveness * getLiveness(Value val)