53 #include "llvm/ADT/STLExtras.h"
54 #include "llvm/Support/Debug.h"
55 #include "llvm/Support/DebugLog.h"
62 #define DEBUG_TYPE "remove-dead-values"
65 #define GEN_PASS_DEF_REMOVEDEADVALUES
66 #include "mlir/Transforms/Passes.h.inc"
82 struct FunctionToCleanUp {
83 FunctionOpInterface funcOp;
84 BitVector nonLiveArgs;
85 BitVector nonLiveRets;
88 struct OperationToCleanup {
93 struct BlockArgsToCleanup {
95 BitVector nonLiveArgs;
98 struct SuccessorOperandsToCleanup {
99 BranchOpInterface branch;
100 unsigned successorIndex;
101 BitVector nonLiveOperands;
104 struct RDVFinalCleanupList {
120 for (
Value value : values) {
121 if (nonLiveSet.contains(value)) {
122 LDBG() <<
"Value " << value <<
" is already marked non-live (dead)";
128 LDBG() <<
"Value " << value
129 <<
" has no liveness info, conservatively considered live";
133 LDBG() <<
"Value " << value <<
" is live according to liveness analysis";
136 LDBG() <<
"Value " << value <<
" is dead according to liveness analysis";
146 BitVector lives(values.size(),
true);
149 if (nonLiveSet.contains(value)) {
151 LDBG() <<
"Value " << value
152 <<
" is already marked non-live (dead) at index " << index;
164 LDBG() <<
"Value " << value <<
" at index " << index
165 <<
" has no liveness info, conservatively considered live";
170 LDBG() <<
"Value " << value <<
" at index " << index
171 <<
" is dead according to liveness analysis";
173 LDBG() <<
"Value " << value <<
" at index " << index
174 <<
" is live according to liveness analysis";
185 const BitVector &nonLive) {
189 nonLiveSet.insert(result);
190 LDBG() <<
"Marking value " << result <<
" as non-live (dead) at index "
197 static void dropUsesAndEraseResults(
Operation *op, BitVector toErase) {
199 "expected the number of results in `op` and the size of `toErase` to "
202 std::vector<Type> newResultTypes;
204 if (!toErase[result.getResultNumber()])
205 newResultTypes.push_back(result.getType());
207 builder.setInsertionPointAfter(op);
218 while (!region.empty())
219 region.front().moveBefore(temp);
223 unsigned indexOfNextNewCallOpResultToReplace = 0;
225 assert(result &&
"expected result to be non-null");
226 if (toErase[index]) {
227 result.dropAllUses();
229 result.replaceAllUsesWith(
230 newOp->
getResult(indexOfNextNewCallOpResultToReplace++));
240 for (
unsigned i = 0, e = operands.size(); i < e; i++)
241 opOperands.push_back(&values[i]);
260 RDVFinalCleanupList &cl) {
262 LDBG() <<
"Simple op is not memory effect free or has live results, "
269 <<
"Simple op has all dead results and is memory effect free, scheduling "
272 cl.operations.push_back(op);
273 collectNonLiveValues(nonLiveSet, op->
getResults(),
287 static void processFuncOp(FunctionOpInterface funcOp,
Operation *module,
289 RDVFinalCleanupList &cl) {
290 LDBG() <<
"Processing function op: " << funcOp.getOperation()->getName();
291 if (funcOp.isPublic() || funcOp.isExternal()) {
292 LDBG() <<
"Function is public or external, skipping: "
293 << funcOp.getOperation()->getName();
299 BitVector nonLiveArgs = markLives(arguments, nonLiveSet, la);
300 nonLiveArgs = nonLiveArgs.flip();
304 if (arg && nonLiveArgs[index]) {
305 cl.values.push_back(arg);
306 nonLiveSet.insert(arg);
313 assert(isa<CallOpInterface>(callOp) &&
"expected a call-like user");
319 for (
int index : nonLiveArgs.set_bits())
320 nonLiveCallOperands.set(callOpOperands[index]->getOperandNumber());
321 cl.operands.push_back({callOp, nonLiveCallOperands});
347 size_t numReturns = funcOp.getNumResults();
348 BitVector nonLiveRets(numReturns,
true);
351 assert(isa<CallOpInterface>(callOp) &&
"expected a call-like user");
352 BitVector liveCallRets = markLives(callOp->
getResults(), nonLiveSet, la);
353 nonLiveRets &= liveCallRets.flip();
359 for (
Block &block : funcOp.getBlocks()) {
360 Operation *returnOp = block.getTerminator();
362 cl.operands.push_back({returnOp, nonLiveRets});
366 cl.functions.push_back({funcOp, nonLiveArgs, nonLiveRets});
373 assert(isa<CallOpInterface>(callOp) &&
"expected a call-like user");
374 cl.results.push_back({callOp, nonLiveRets});
375 collectNonLiveValues(nonLiveSet, callOp->
getResults(), nonLiveRets);
408 static void processRegionBranchOp(RegionBranchOpInterface regionBranchOp,
411 RDVFinalCleanupList &cl) {
412 LDBG() <<
"Processing region branch op: "
415 auto markLiveResults = [&](BitVector &liveResults) {
416 liveResults = markLives(regionBranchOp->getResults(), nonLiveSet, la);
421 for (
Region ®ion : regionBranchOp->getRegions()) {
425 BitVector regionLiveArgs = markLives(arguments, nonLiveSet, la);
426 liveArgs[®ion] = regionLiveArgs;
432 auto getSuccessors = [&](
Region *region =
nullptr) {
435 regionBranchOp.getSuccessorRegions(point, successors);
445 terminator ? cast<RegionBranchTerminatorOpInterface>(terminator)
446 .getSuccessorOperands(successor)
447 : regionBranchOp.getEntrySuccessorOperands(successor);
454 auto markNonForwardedOperands = [&](BitVector &nonForwardedOperands) {
455 nonForwardedOperands.resize(regionBranchOp->getNumOperands(),
true);
457 for (
OpOperand *opOperand : getForwardedOpOperands(successor))
458 nonForwardedOperands.reset(opOperand->getOperandNumber());
464 auto markNonForwardedReturnValues =
466 for (
Region ®ion : regionBranchOp->getRegions()) {
470 nonForwardedRets[terminator] =
474 getForwardedOpOperands(successor, terminator))
475 nonForwardedRets[terminator].reset(opOperand->getOperandNumber());
484 auto updateOperandsOrTerminatorOperandsToKeep =
485 [&](BitVector &valuesToKeep, BitVector &resultsToKeep,
488 region ? region->front().getTerminator() :
nullptr;
492 for (
auto [opOperand, input] :
493 llvm::zip(getForwardedOpOperands(successor, terminator),
495 size_t operandNum = opOperand->getOperandNumber();
498 ? argsToKeep[successorRegion]
499 [cast<BlockArgument>(input).getArgNumber()]
500 : resultsToKeep[cast<OpResult>(input).getResultNumber()];
501 valuesToKeep[operandNum] = valuesToKeep[operandNum] | updateBasedOn;
509 auto recomputeResultsAndArgsToKeep =
511 BitVector &operandsToKeep,
513 bool &resultsOrArgsToKeepChanged) {
514 resultsOrArgsToKeepChanged =
false;
519 for (
auto [opOperand, input] :
520 llvm::zip(getForwardedOpOperands(successor),
522 bool recomputeBasedOn =
523 operandsToKeep[opOperand->getOperandNumber()];
526 ? argsToKeep[successorRegion]
527 [cast<BlockArgument>(input).getArgNumber()]
528 : resultsToKeep[cast<OpResult>(input).getResultNumber()];
529 if (!toRecompute && recomputeBasedOn)
530 resultsOrArgsToKeepChanged =
true;
531 if (successorRegion) {
532 argsToKeep[successorRegion][cast<BlockArgument>(input)
534 argsToKeep[successorRegion]
535 [cast<BlockArgument>(input).getArgNumber()] |
538 resultsToKeep[cast<OpResult>(input).getResultNumber()] =
539 resultsToKeep[cast<OpResult>(input).getResultNumber()] |
547 for (
Region ®ion : regionBranchOp->getRegions()) {
550 Operation *terminator = region.front().getTerminator();
553 for (
auto [opOperand, input] :
554 llvm::zip(getForwardedOpOperands(successor, terminator),
556 bool recomputeBasedOn =
557 terminatorOperandsToKeep[region.back().getTerminator()]
558 [opOperand->getOperandNumber()];
561 ? argsToKeep[successorRegion]
562 [cast<BlockArgument>(input).getArgNumber()]
563 : resultsToKeep[cast<OpResult>(input).getResultNumber()];
564 if (!toRecompute && recomputeBasedOn)
565 resultsOrArgsToKeepChanged =
true;
566 if (successorRegion) {
567 argsToKeep[successorRegion][cast<BlockArgument>(input)
569 argsToKeep[successorRegion]
570 [cast<BlockArgument>(input).getArgNumber()] |
573 resultsToKeep[cast<OpResult>(input).getResultNumber()] =
574 resultsToKeep[cast<OpResult>(input).getResultNumber()] |
584 auto markValuesToKeep =
586 BitVector &operandsToKeep,
588 bool resultsOrArgsToKeepChanged =
true;
591 while (resultsOrArgsToKeepChanged) {
593 updateOperandsOrTerminatorOperandsToKeep(operandsToKeep,
594 resultsToKeep, argsToKeep);
597 for (
Region ®ion : regionBranchOp->getRegions()) {
600 updateOperandsOrTerminatorOperandsToKeep(
601 terminatorOperandsToKeep[region.back().getTerminator()],
602 resultsToKeep, argsToKeep, ®ion);
606 recomputeResultsAndArgsToKeep(
607 resultsToKeep, argsToKeep, operandsToKeep,
608 terminatorOperandsToKeep, resultsOrArgsToKeepChanged);
619 !hasLive(regionBranchOp->getResults(), nonLiveSet, la)) {
620 cl.operations.push_back(regionBranchOp.getOperation());
629 BitVector resultsToKeep;
634 BitVector operandsToKeep;
642 markLiveResults(resultsToKeep);
645 markLiveArgs(argsToKeep);
649 markNonForwardedOperands(operandsToKeep);
652 markNonForwardedReturnValues(terminatorOperandsToKeep);
656 markValuesToKeep(resultsToKeep, argsToKeep, operandsToKeep,
657 terminatorOperandsToKeep);
660 cl.operands.push_back({regionBranchOp, operandsToKeep.flip()});
663 for (
Region ®ion : regionBranchOp->getRegions()) {
666 BitVector argsToRemove = argsToKeep[®ion].flip();
667 cl.blocks.push_back({®ion.front(), argsToRemove});
668 collectNonLiveValues(nonLiveSet, region.front().getArguments(),
673 for (
Region ®ion : regionBranchOp->getRegions()) {
676 Operation *terminator = region.front().getTerminator();
677 cl.operands.push_back(
678 {terminator, terminatorOperandsToKeep[terminator].flip()});
682 BitVector resultsToRemove = resultsToKeep.flip();
683 collectNonLiveValues(nonLiveSet, regionBranchOp.getOperation()->getResults(),
685 cl.results.push_back({regionBranchOp.getOperation(), resultsToRemove});
698 RDVFinalCleanupList &cl) {
699 LDBG() <<
"Processing branch op: " << *branchOp;
700 unsigned numSuccessors = branchOp->getNumSuccessors();
702 for (
unsigned succIdx = 0; succIdx < numSuccessors; ++succIdx) {
707 branchOp.getSuccessorOperands(succIdx);
709 for (
unsigned operandIdx = 0; operandIdx < successorOperands.
size();
711 operandValues.push_back(successorOperands[operandIdx]);
715 BitVector successorNonLive =
716 markLives(operandValues, nonLiveSet, la).flip();
717 collectNonLiveValues(nonLiveSet, successorBlock->
getArguments(),
721 cl.blocks.push_back({successorBlock, successorNonLive});
722 cl.successorOperands.push_back({branchOp, succIdx, successorNonLive});
728 static void cleanUpDeadVals(RDVFinalCleanupList &list) {
729 LDBG() <<
"Starting cleanup of dead values...";
732 LDBG() <<
"Cleaning up " << list.operations.size() <<
" operations";
733 for (
auto &op : list.operations) {
734 LDBG() <<
"Erasing operation: "
741 LDBG() <<
"Cleaning up " << list.values.size() <<
" values";
742 for (
auto &v : list.values) {
743 LDBG() <<
"Dropping all uses of value: " << v;
748 LDBG() <<
"Cleaning up " << list.functions.size() <<
" functions";
749 for (
auto &f : list.functions) {
750 LDBG() <<
"Cleaning up function: " << f.funcOp.getOperation()->getName();
751 LDBG() <<
" Erasing " << f.nonLiveArgs.count() <<
" non-live arguments";
752 LDBG() <<
" Erasing " << f.nonLiveRets.count()
753 <<
" non-live return values";
757 (void)f.funcOp.eraseArguments(f.nonLiveArgs);
758 (void)f.funcOp.eraseResults(f.nonLiveRets);
762 LDBG() <<
"Cleaning up " << list.operands.size() <<
" operand lists";
763 for (OperationToCleanup &o : list.operands) {
764 if (o.op->getNumOperands() > 0) {
765 LDBG() <<
"Erasing " << o.nonLive.count()
766 <<
" non-live operands from operation: "
768 o.op->eraseOperands(o.nonLive);
773 LDBG() <<
"Cleaning up " << list.results.size() <<
" result lists";
774 for (
auto &r : list.results) {
775 LDBG() <<
"Erasing " << r.nonLive.count()
776 <<
" non-live results from operation: "
778 dropUsesAndEraseResults(r.op, r.nonLive);
782 LDBG() <<
"Cleaning up " << list.blocks.size() <<
" block argument lists";
783 for (
auto &b : list.blocks) {
785 if (b.b->getNumArguments() != b.nonLiveArgs.size())
787 LDBG() <<
"Erasing " << b.nonLiveArgs.count()
788 <<
" non-live arguments from block: " << b.b;
790 for (
int i = b.nonLiveArgs.size() - 1; i >= 0; --i) {
791 if (!b.nonLiveArgs[i])
793 LDBG() <<
" Erasing block argument " << i <<
": " << b.b->getArgument(i);
794 b.b->getArgument(i).dropAllUses();
795 b.b->eraseArgument(i);
800 LDBG() <<
"Cleaning up " << list.successorOperands.size()
801 <<
" successor operand lists";
802 for (
auto &op : list.successorOperands) {
804 op.branch.getSuccessorOperands(op.successorIndex);
806 if (successorOperands.
size() != op.nonLiveOperands.size())
808 LDBG() <<
"Erasing " << op.nonLiveOperands.count()
809 <<
" non-live successor operands from successor "
810 << op.successorIndex <<
" of branch: "
813 for (
int i = successorOperands.
size() - 1; i >= 0; --i) {
814 if (!op.nonLiveOperands[i])
816 LDBG() <<
" Erasing successor operand " << i <<
": "
817 << successorOperands[i];
818 successorOperands.
erase(i);
822 LDBG() <<
"Finished cleanup of dead values";
825 struct RemoveDeadValues :
public impl::RemoveDeadValuesBase<RemoveDeadValues> {
826 void runOnOperation()
override;
830 void RemoveDeadValues::runOnOperation() {
831 auto &la = getAnalysis<RunLivenessAnalysis>();
840 RDVFinalCleanupList finalCleanupList;
843 if (
auto funcOp = dyn_cast<FunctionOpInterface>(op)) {
844 processFuncOp(funcOp, module, la, deadVals, finalCleanupList);
845 }
else if (
auto regionBranchOp = dyn_cast<RegionBranchOpInterface>(op)) {
846 processRegionBranchOp(regionBranchOp, la, deadVals, finalCleanupList);
847 }
else if (
auto branchOp = dyn_cast<BranchOpInterface>(op)) {
848 processBranchOp(branchOp, la, deadVals, finalCleanupList);
852 }
else if (isa<CallOpInterface>(op)) {
856 processSimpleOp(op, la, deadVals, finalCleanupList);
860 cleanUpDeadVals(finalCleanupList);
864 return std::make_unique<RemoveDeadValues>();
static MutableArrayRef< OpOperand > operandsToOpOperands(OperandRange &operands)
Block represents an ordered list of Operations.
void erase()
Unlink this Block from its parent region and delete it.
Operation * getTerminator()
Get the terminator operation of this block.
BlockArgListType getArguments()
Block * getSuccessor(unsigned i)
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 is a value defined by a result of an operation.
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...
This class implements the operand iterators for the Operation class.
StringRef getStringRef() const
Return the name of this operation. This always succeeds.
Operation is the basic unit of execution within MLIR.
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.
OpResult getResult(unsigned idx)
Get the 'idx'th result of this operation.
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),...
unsigned getNumRegions()
Returns the number of regions held by this operation.
Location getLoc()
The source location the operation was defined or derived from.
unsigned getNumOperands()
static Operation * create(Location location, OperationName name, TypeRange resultTypes, ValueRange operands, NamedAttrList &&attributes, OpaqueProperties properties, BlockRange successors, unsigned numRegions)
Create a new Operation with the specific fields.
ArrayRef< NamedAttribute > getAttrs()
Return all of the attributes on this operation.
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
OperationName getName()
The name of an operation is the key identifier for it.
operand_range getOperands()
Returns an iterator on the underlying Value's.
result_range getResults()
void erase()
Remove this operation from its parent block and delete it.
unsigned getNumResults()
Return the number of results held by this operation.
static constexpr RegionBranchPoint parent()
Returns an instance of RegionBranchPoint representing the parent operation.
This class represents a successor of a region.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region.
Region * getSuccessor() const
Return the given region successor.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
void push_back(Block *block)
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 size() const
Returns the amount of operands passed to the successor.
This class represents a specific symbol use.
This class implements a range of SymbolRef uses.
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...
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Include the generated interface declarations.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
std::unique_ptr< Pass > createRemoveDeadValuesPass()
Creates an optimization pass to remove dead values.
This represents an operation in an abstracted form, suitable for use with the builder APIs.
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)