Go to the documentation of this file.
59 #define DEBUG_TYPE "adce"
61 STATISTIC(NumRemoved,
"Number of instructions removed");
62 STATISTIC(NumBranchesRemoved,
"Number of branch instructions removed");
82 struct BlockInfoType *Block =
nullptr;
86 struct BlockInfoType {
91 bool UnconditionalBranch =
false;
94 bool HasLivePhiNodes =
false;
101 InstInfoType *TerminatorLiveInfo =
nullptr;
112 bool terminatorIsLive()
const {
return TerminatorLiveInfo->Live; }
115 class AggressiveDeadCodeElimination {
158 void markLiveInstructions();
164 void markLive(BlockInfoType &
BB);
177 void markLiveBranchesFromControlDependences();
181 bool removeDeadInstructions();
185 bool updateDeadRegions();
189 void computeReversePostOrder();
197 :
F(
F), DT(DT), PDT(PDT) {}
199 bool performDeadCodeElimination();
204 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
206 markLiveInstructions();
207 return removeDeadInstructions();
211 auto *
BR = dyn_cast<BranchInst>(
Term);
212 return BR &&
BR->isUnconditional();
216 auto NumBlocks =
F.size();
220 BlockInfo.reserve(NumBlocks);
226 NumInsts +=
BB.size();
227 auto &
Info = BlockInfo[&
BB];
229 Info.Terminator =
BB.getTerminator();
234 InstInfo.reserve(NumInsts);
235 for (
auto &BBInfo : BlockInfo)
237 InstInfo[&
I].Block = &BBInfo.second;
241 for (
auto &BBInfo : BlockInfo)
242 BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];
259 class DFState :
public StatusMap {
261 std::pair<StatusMap::iterator, bool> insert(
BasicBlock *
BB) {
262 return StatusMap::insert(std::make_pair(
BB,
true));
272 return Iter !=
end() && Iter->second;
276 State.reserve(
F.size());
286 if (State.onStack(Succ)) {
298 for (
auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
299 auto *
BB = PDTChild->getBlock();
300 auto &
Info = BlockInfo[
BB];
302 if (isa<ReturnInst>(
Info.Terminator)) {
310 markLive(BlockInfo[DFNode->getBlock()].Terminator);
314 auto *
BB = &
F.getEntryBlock();
315 auto &EntryInfo = BlockInfo[
BB];
316 EntryInfo.Live =
true;
317 if (EntryInfo.UnconditionalBranch)
318 markLive(EntryInfo.Terminator);
321 for (
auto &BBInfo : BlockInfo)
322 if (!BBInfo.second.terminatorIsLive())
323 BlocksWithDeadTerminators.insert(BBInfo.second.BB);
328 if (
I.isEHPad() ||
I.mayHaveSideEffects()) {
331 if (isInstrumentsConstant(
I))
335 if (!
I.isTerminator())
344 bool AggressiveDeadCodeElimination::isInstrumentsConstant(
Instruction &
I) {
346 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
347 if (
Function *Callee = CI->getCalledFunction())
349 if (isa<Constant>(CI->getArgOperand(0)))
354 void AggressiveDeadCodeElimination::markLiveInstructions() {
359 while (!Worklist.empty()) {
367 if (
auto *PN = dyn_cast<PHINode>(LiveInst))
373 markLiveBranchesFromControlDependences();
375 }
while (!Worklist.empty());
378 void AggressiveDeadCodeElimination::markLive(
Instruction *
I) {
379 auto &
Info = InstInfo[
I];
385 Worklist.push_back(
I);
389 collectLiveScopes(*
DL);
392 auto &BBInfo = *
Info.Block;
393 if (BBInfo.Terminator ==
I) {
394 BlocksWithDeadTerminators.remove(BBInfo.BB);
397 if (!BBInfo.UnconditionalBranch)
404 void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {
407 LLVM_DEBUG(
dbgs() <<
"mark block live: " << BBInfo.BB->getName() <<
'\n');
409 if (!BBInfo.CFLive) {
410 BBInfo.CFLive =
true;
411 NewLiveBlocks.insert(BBInfo.BB);
416 if (BBInfo.UnconditionalBranch)
417 markLive(BBInfo.Terminator);
420 void AggressiveDeadCodeElimination::collectLiveScopes(
const DILocalScope &
LS) {
421 if (!AliveScopes.insert(&
LS).second)
424 if (isa<DISubprogram>(
LS))
428 collectLiveScopes(cast<DILocalScope>(*
LS.getScope()));
431 void AggressiveDeadCodeElimination::collectLiveScopes(
const DILocation &
DL) {
434 if (!AliveScopes.insert(&
DL).second)
438 collectLiveScopes(*
DL.getScope());
442 collectLiveScopes(*IA);
445 void AggressiveDeadCodeElimination::markPhiLive(
PHINode *PN) {
448 if (
Info.HasLivePhiNodes)
450 Info.HasLivePhiNodes =
true;
456 auto &
Info = BlockInfo[PredBB];
459 NewLiveBlocks.insert(PredBB);
464 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
465 if (BlocksWithDeadTerminators.empty())
469 dbgs() <<
"new live blocks:\n";
470 for (
auto *
BB : NewLiveBlocks)
471 dbgs() <<
"\t" <<
BB->getName() <<
'\n';
472 dbgs() <<
"dead terminator blocks:\n";
473 for (
auto *
BB : BlocksWithDeadTerminators)
474 dbgs() <<
"\t" <<
BB->getName() <<
'\n';
484 BlocksWithDeadTerminators.
begin(),
485 BlocksWithDeadTerminators.end()
489 IDFs.setDefiningBlocks(NewLiveBlocks);
490 IDFs.setLiveInBlocks(BWDT);
491 IDFs.calculate(IDFBlocks);
492 NewLiveBlocks.clear();
495 for (
auto *
BB : IDFBlocks) {
497 markLive(
BB->getTerminator());
506 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
508 bool RegionsUpdated = updateDeadRegions();
516 if (
auto *DII = dyn_cast<DbgVariableIntrinsic>(&
I)) {
518 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
524 for (
Value *V : DII->location_ops()) {
525 if (Instruction *II = dyn_cast<Instruction>(V)) {
527 dbgs() <<
"Dropping debug info for " << *DII <<
"\n";
545 if (
auto *DII = dyn_cast<DbgInfoIntrinsic>(&
I)) {
547 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
554 Worklist.push_back(&
I);
559 I->dropAllReferences();
563 I->eraseFromParent();
566 return !Worklist.empty() || RegionsUpdated;
570 bool AggressiveDeadCodeElimination::updateDeadRegions() {
572 dbgs() <<
"final dead terminator blocks: " <<
'\n';
573 for (
auto *
BB : BlocksWithDeadTerminators)
574 dbgs() <<
'\t' <<
BB->getName()
575 << (BlockInfo[
BB].Live ?
" LIVE\n" :
"\n");
579 bool HavePostOrder =
false;
580 bool Changed =
false;
583 for (
auto *
BB : BlocksWithDeadTerminators) {
584 auto &
Info = BlockInfo[
BB];
585 if (
Info.UnconditionalBranch) {
586 InstInfo[
Info.Terminator].Live =
true;
590 if (!HavePostOrder) {
591 computeReversePostOrder();
592 HavePostOrder =
true;
598 BlockInfoType *PreferredSucc =
nullptr;
600 auto *
Info = &BlockInfo[Succ];
601 if (!PreferredSucc || PreferredSucc->PostOrder <
Info->PostOrder)
602 PreferredSucc =
Info;
604 assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
605 "Failed to find safe successor for dead branch");
611 if (!
First || Succ != PreferredSucc->BB) {
612 Succ->removePredecessor(
BB);
613 RemovedSuccessors.
insert(Succ);
617 makeUnconditional(
BB, PreferredSucc->BB);
620 for (
auto *Succ : RemovedSuccessors) {
623 if (Succ != PreferredSucc->BB) {
624 LLVM_DEBUG(
dbgs() <<
"ADCE: (Post)DomTree edge enqueued for deletion"
625 <<
BB->getName() <<
" -> " << Succ->getName()
627 DeletedEdges.push_back({DominatorTree::Delete,
BB, Succ});
631 NumBranchesRemoved += 1;
635 if (!DeletedEdges.empty())
643 void AggressiveDeadCodeElimination::computeReversePostOrder() {
652 unsigned PostOrder = 0;
657 BlockInfo[
Block].PostOrder = PostOrder++;
661 void AggressiveDeadCodeElimination::makeUnconditional(
BasicBlock *
BB,
666 collectLiveScopes(*
DL);
671 InstInfo[PredTerm].Live =
true;
675 NumBranchesRemoved += 1;
678 InstInfo[NewTerm].Live =
true;
680 NewTerm->setDebugLoc(
DL);
682 InstInfo.erase(PredTerm);
696 if (!AggressiveDeadCodeElimination(
F, DT, PDT).performDeadCodeElimination())
725 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
726 auto *DT = DTWP ? &DTWP->getDomTree() :
nullptr;
727 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
728 return AggressiveDeadCodeElimination(
F, DT, PDT)
729 .performDeadCodeElimination();
749 "Aggressive Dead Code Elimination",
false,
false)
A set of analyses that are preserved following a run of a transformation pass.
This is an optimization pass for GlobalISel generic memory operations.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void dump() const
Support for debugging, callable in GDB: V->dump()
Target - Wrapper for Target specific information.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionAnalysisManager FAM
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
const_iterator end(StringRef path)
Get end iterator over path.
static bool isAlwaysLive(Instruction *I)
This class implements a map that also provides access to all stored values in a deterministic order.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
static cl::opt< bool > Aggressive("aggressive-ext-opt", cl::Hidden, cl::desc("Aggressive extension optimization"))
bool succ_empty(const Instruction *I)
INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", false, false) INITIALIZE_PASS_END(ADCELegacyPass
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Represent the analysis usage information of a pass.
into llvm powi allowing the code generator to produce balanced multiplication trees First
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Legacy analysis pass which computes a DominatorTree.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
Analysis containing CSE Info
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
static cl::opt< bool > RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden)
inst_range instructions(Function *F)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void preserve()
Mark an analysis as preserved.
initializer< Ty > init(const Ty &Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Aggressive Dead Code Elimination
static cl::opt< bool > RemoveLoops("adce-remove-loops", cl::init(false), cl::Hidden)
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents analyses that only rely on functions' control flow.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
this could be done in SelectionDAGISel along with other special for
static bool isUnconditionalBranch(Instruction *Term)
amdgpu Simplify well known AMD library false FunctionCallee Callee
iterator_range< df_iterator< T > > depth_first(const T &G)
static bool runOnFunction(Function &F, bool PostInlining)
FunctionPass * createAggressiveDCEPass()
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
@ BR
Control flow instructions. These all have token chains.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Analysis pass which computes a DominatorTree.
void preserveSet()
Mark an analysis set as preserved.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const BasicBlock * getParent() const
Legacy wrapper pass to provide the GlobalsAAResult object.
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
This class represents a function call, abstracting a target machine's calling convention.
StringRef getInstrProfValueProfFuncName()
Return the name profile runtime entry point to do value profiling for a given site.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
void initializeADCELegacyPassPass(PassRegistry &)
Analysis pass which computes a PostDominatorTree.
AnalysisUsage & addRequired()
LLVM Value Representation.
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.