58 #define DEBUG_TYPE "adce" 60 STATISTIC(NumRemoved,
"Number of instructions removed");
61 STATISTIC(NumBranchesRemoved,
"Number of branch instructions removed");
81 struct BlockInfoType *Block =
nullptr;
85 struct BlockInfoType {
90 bool UnconditionalBranch =
false;
93 bool HasLivePhiNodes =
false;
100 InstInfoType *TerminatorLiveInfo =
nullptr;
111 bool terminatorIsLive()
const {
return TerminatorLiveInfo->Live; }
114 class AggressiveDeadCodeElimination {
125 bool isLive(
BasicBlock *BB) {
return BlockInfo[BB].Live; }
157 void markLiveInstructions();
163 void markLive(BlockInfoType &BB);
164 void markLive(
BasicBlock *BB) { markLive(BlockInfo[BB]); }
176 void markLiveBranchesFromControlDependences();
180 bool removeDeadInstructions();
184 void updateDeadRegions();
188 void computeReversePostOrder();
196 : F(F), DT(DT), PDT(PDT) {}
198 bool performDeadCodeElimination();
203 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
205 markLiveInstructions();
206 return removeDeadInstructions();
211 return BR &&
BR->isUnconditional();
215 auto NumBlocks =
F.size();
219 BlockInfo.reserve(NumBlocks);
225 NumInsts += BB.size();
226 auto &
Info = BlockInfo[&BB];
228 Info.Terminator = BB.getTerminator();
233 InstInfo.reserve(NumInsts);
234 for (
auto &BBInfo : BlockInfo)
236 InstInfo[&
I].Block = &BBInfo.second;
240 for (
auto &BBInfo : BlockInfo)
241 BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];
258 class DFState :
public StatusMap {
260 std::pair<StatusMap::iterator, bool> insert(
BasicBlock *BB) {
261 return StatusMap::insert(std::make_pair(BB,
true));
265 void completed(
BasicBlock *BB) { (*this)[BB] =
false; }
270 auto Iter =
find(BB);
271 return Iter !=
end() && Iter->second;
275 State.reserve(F.size());
285 if (State.onStack(Succ)) {
297 for (
auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
298 auto *BB = PDTChild->getBlock();
299 auto &
Info = BlockInfo[BB];
301 if (isa<ReturnInst>(
Info.Terminator)) {
302 LLVM_DEBUG(
dbgs() <<
"post-dom root child is a return: " << BB->getName()
309 markLive(BlockInfo[DFNode->getBlock()].Terminator);
313 auto *BB = &F.getEntryBlock();
314 auto &EntryInfo = BlockInfo[BB];
315 EntryInfo.Live =
true;
316 if (EntryInfo.UnconditionalBranch)
317 markLive(EntryInfo.Terminator);
320 for (
auto &BBInfo : BlockInfo)
321 if (!BBInfo.second.terminatorIsLive())
322 BlocksWithDeadTerminators.insert(BBInfo.second.BB);
330 if (isInstrumentsConstant(I))
343 bool AggressiveDeadCodeElimination::isInstrumentsConstant(
Instruction &I) {
345 if (
CallInst *CI = dyn_cast<CallInst>(&I))
348 if (isa<Constant>(CI->getArgOperand(0)))
353 void AggressiveDeadCodeElimination::markLiveInstructions() {
358 while (!Worklist.empty()) {
366 if (
auto *PN = dyn_cast<PHINode>(LiveInst))
372 markLiveBranchesFromControlDependences();
374 }
while (!Worklist.empty());
377 void AggressiveDeadCodeElimination::markLive(
Instruction *I) {
378 auto &
Info = InstInfo[
I];
384 Worklist.push_back(I);
388 collectLiveScopes(*DL);
391 auto &BBInfo = *
Info.Block;
392 if (BBInfo.Terminator == I) {
393 BlocksWithDeadTerminators.erase(BBInfo.BB);
396 if (!BBInfo.UnconditionalBranch)
403 void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {
406 LLVM_DEBUG(
dbgs() <<
"mark block live: " << BBInfo.BB->getName() <<
'\n');
408 if (!BBInfo.CFLive) {
409 BBInfo.CFLive =
true;
410 NewLiveBlocks.insert(BBInfo.BB);
415 if (BBInfo.UnconditionalBranch)
416 markLive(BBInfo.Terminator);
419 void AggressiveDeadCodeElimination::collectLiveScopes(
const DILocalScope &
LS) {
420 if (!AliveScopes.insert(&LS).second)
423 if (isa<DISubprogram>(LS))
427 collectLiveScopes(cast<DILocalScope>(*LS.
getScope()));
430 void AggressiveDeadCodeElimination::collectLiveScopes(
const DILocation &DL) {
433 if (!AliveScopes.insert(&DL).second)
437 collectLiveScopes(*DL.getScope());
441 collectLiveScopes(*IA);
444 void AggressiveDeadCodeElimination::markPhiLive(
PHINode *PN) {
447 if (
Info.HasLivePhiNodes)
449 Info.HasLivePhiNodes =
true;
455 auto &
Info = BlockInfo[PredBB];
458 NewLiveBlocks.insert(PredBB);
463 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
464 if (BlocksWithDeadTerminators.empty())
468 dbgs() <<
"new live blocks:\n";
469 for (
auto *BB : NewLiveBlocks)
470 dbgs() <<
"\t" << BB->getName() <<
'\n';
471 dbgs() <<
"dead terminator blocks:\n";
472 for (
auto *BB : BlocksWithDeadTerminators)
473 dbgs() <<
"\t" << BB->getName() <<
'\n';
487 NewLiveBlocks.clear();
490 for (
auto *BB : IDFBlocks) {
491 LLVM_DEBUG(
dbgs() <<
"live control in: " << BB->getName() <<
'\n');
492 markLive(BB->getTerminator());
501 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
511 if (
auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
513 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
519 if (
Value *V = DII->getVariableLocation())
522 dbgs() <<
"Dropping debug info for " << *DII <<
"\n";
536 if (
auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
538 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
545 Worklist.push_back(&I);
554 return !Worklist.empty();
558 void AggressiveDeadCodeElimination::updateDeadRegions() {
560 dbgs() <<
"final dead terminator blocks: " <<
'\n';
561 for (
auto *BB : BlocksWithDeadTerminators)
562 dbgs() <<
'\t' << BB->getName()
563 << (BlockInfo[BB].Live ?
" LIVE\n" :
"\n");
567 bool HavePostOrder =
false;
569 for (
auto *BB : BlocksWithDeadTerminators) {
570 auto &
Info = BlockInfo[BB];
571 if (
Info.UnconditionalBranch) {
572 InstInfo[
Info.Terminator].Live =
true;
576 if (!HavePostOrder) {
577 computeReversePostOrder();
578 HavePostOrder =
true;
584 BlockInfoType *PreferredSucc =
nullptr;
586 auto *
Info = &BlockInfo[Succ];
587 if (!PreferredSucc || PreferredSucc->PostOrder <
Info->PostOrder)
588 PreferredSucc =
Info;
590 assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
591 "Failed to find safe successor for dead branch");
597 if (!First || Succ != PreferredSucc->BB) {
598 Succ->removePredecessor(BB);
599 RemovedSuccessors.
insert(Succ);
603 makeUnconditional(BB, PreferredSucc->BB);
607 for (
auto *Succ : RemovedSuccessors) {
610 if (Succ != PreferredSucc->BB) {
611 LLVM_DEBUG(
dbgs() <<
"ADCE: (Post)DomTree edge enqueued for deletion" 612 << BB->getName() <<
" -> " << Succ->getName()
621 NumBranchesRemoved += 1;
626 void AggressiveDeadCodeElimination::computeReversePostOrder() {
635 unsigned PostOrder = 0;
640 BlockInfo[Block].PostOrder = PostOrder++;
644 void AggressiveDeadCodeElimination::makeUnconditional(
BasicBlock *BB,
649 collectLiveScopes(*DL);
654 InstInfo[PredTerm].Live =
true;
658 NumBranchesRemoved += 1;
660 auto *NewTerm = Builder.
CreateBr(Target);
661 InstInfo[NewTerm].Live =
true;
665 InstInfo.erase(PredTerm);
679 if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
705 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
706 auto *DT = DTWP ? &DTWP->getDomTree() :
nullptr;
707 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
708 return AggressiveDeadCodeElimination(F, DT, PDT)
709 .performDeadCodeElimination();
729 "Aggressive Dead Code Elimination",
false,
false)
Legacy wrapper pass to provide the GlobalsAAResult object.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const_iterator end(StringRef path)
Get end iterator over path.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void dropAllReferences()
Drop all references to operands.
Aggressive Dead Code Elimination
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents lattice values for constants.
This is the interface for a simple mod/ref and alias analysis over globals.
void push_back(const T &Elt)
static cl::opt< bool > RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden)
This class represents a function call, abstracting a target machine's calling convention.
bool isTerminator() const
static cl::opt< bool > RemoveLoops("adce-remove-loops", cl::init(false), cl::Hidden)
This class implements a map that also provides access to all stored values in a deterministic order...
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
This defines the Use class.
void dump() const
Support for debugging, callable in GDB: V->dump()
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
void initializeADCELegacyPassPass(PassRegistry &)
static constexpr UpdateKind Delete
static cl::opt< bool > Aggressive("aggressive-ext-opt", cl::Hidden, cl::desc("Aggressive extension optimization"))
A Use represents the edge between a Value definition and its users.
void setDefiningBlocks(const SmallPtrSetImpl< BasicBlock *> &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
static bool isUnconditionalBranch(Instruction *Term)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
amdgpu Simplify well known AMD library false Value * Callee
Analysis containing CSE Info
Interval::succ_iterator succ_end(Interval *I)
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Control flow instructions. These all have token chains.
A set of analyses that are preserved following a run of a transformation pass.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM Basic Block Representation.
Conditional or Unconditional Branch instruction.
StringRef getInstrProfValueProfFuncName()
Return the name profile runtime entry point to do value profiling for a given site.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Compute iterated dominance frontiers using a linear time algorithm.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
void setLiveInBlocks(const SmallPtrSetImpl< BasicBlock *> &Blocks)
Give the IDF calculator the set of blocks in which the value is live on entry to the block...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
void calculate(SmallVectorImpl< BasicBlock *> &IDFBlocks)
Calculate iterated dominance frontiers.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Analysis pass which computes a PostDominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates, bool ForceRemoveDuplicates=false)
Apply updates on all available trees.
pred_range predecessors(BasicBlock *BB)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", false, false) INITIALIZE_PASS_END(ADCELegacyPass
Target - Wrapper for Target specific information.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents analyses that only rely on functions' control flow.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
void preserveSet()
Mark an analysis set as preserved.
StringRef getName() const
Return a constant reference to the value's name.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
void preserve()
Mark an analysis as preserved.
iterator_range< df_iterator< T > > depth_first(const T &G)
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
static bool isAlwaysLive(Instruction *I)
succ_range successors(Instruction *I)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
inst_range instructions(Function *F)
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
This header defines various interfaces for pass management in LLVM.
FunctionPass * createAggressiveDCEPass()
const BasicBlock * getParent() const
DIScopeRef getScope() const