58#define DEBUG_TYPE "adce"
60STATISTIC(NumRemoved,
"Number of instructions removed");
61STATISTIC(NumBranchesRemoved,
"Number of branch instructions removed");
81 struct BlockInfoType *
Block =
nullptr;
90 bool UnconditionalBranch =
false;
93 bool HasLivePhiNodes =
false;
100 InstInfoType *TerminatorLiveInfo =
nullptr;
111 bool terminatorIsLive()
const {
return TerminatorLiveInfo->Live; }
115 bool ChangedAnything =
false;
116 bool ChangedNonDebugInstr =
false;
117 bool ChangedControlFlow =
false;
120class AggressiveDeadCodeElimination {
131 bool isLive(
BasicBlock *BB) {
return BlockInfo[BB].Live; }
163 void markLiveInstructions();
169 void markLive(BlockInfoType &BB);
170 void markLive(
BasicBlock *BB) { markLive(BlockInfo[BB]); }
182 void markLiveBranchesFromControlDependences();
186 ADCEChanged removeDeadInstructions();
190 bool updateDeadRegions();
194 void computeReversePostOrder();
202 :
F(
F), DT(DT), PDT(PDT) {}
204 ADCEChanged performDeadCodeElimination();
209ADCEChanged AggressiveDeadCodeElimination::performDeadCodeElimination() {
211 markLiveInstructions();
212 return removeDeadInstructions();
216 auto *BR = dyn_cast<BranchInst>(Term);
217 return BR && BR->isUnconditional();
220void AggressiveDeadCodeElimination::initialize() {
221 auto NumBlocks =
F.size();
225 BlockInfo.reserve(NumBlocks);
231 NumInsts += BB.size();
232 auto &
Info = BlockInfo[&BB];
234 Info.Terminator = BB.getTerminator();
239 InstInfo.reserve(NumInsts);
240 for (
auto &BBInfo : BlockInfo)
242 InstInfo[&
I].Block = &BBInfo.second;
246 for (
auto &BBInfo : BlockInfo)
247 BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];
264 class DFState :
public StatusMap {
266 std::pair<StatusMap::iterator, bool> insert(
BasicBlock *BB) {
267 return StatusMap::insert(std::make_pair(BB,
true));
271 void completed(
BasicBlock *BB) { (*this)[BB] =
false; }
276 auto Iter =
find(BB);
277 return Iter !=
end() && Iter->second;
281 State.reserve(
F.size());
291 if (State.onStack(Succ)) {
303 for (
const auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
304 auto *BB = PDTChild->getBlock();
305 auto &
Info = BlockInfo[BB];
307 if (isa<ReturnInst>(
Info.Terminator)) {
308 LLVM_DEBUG(
dbgs() <<
"post-dom root child is a return: " << BB->getName()
315 markLive(BlockInfo[DFNode->getBlock()].Terminator);
319 auto *BB = &
F.getEntryBlock();
320 auto &EntryInfo = BlockInfo[BB];
321 EntryInfo.Live =
true;
322 if (EntryInfo.UnconditionalBranch)
323 markLive(EntryInfo.Terminator);
326 for (
auto &BBInfo : BlockInfo)
327 if (!BBInfo.second.terminatorIsLive())
328 BlocksWithDeadTerminators.insert(BBInfo.second.BB);
331bool AggressiveDeadCodeElimination::isAlwaysLive(
Instruction &
I) {
333 if (
I.isEHPad() ||
I.mayHaveSideEffects()) {
336 if (isInstrumentsConstant(
I))
340 if (!
I.isTerminator())
349bool AggressiveDeadCodeElimination::isInstrumentsConstant(
Instruction &
I) {
351 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
352 if (
Function *Callee = CI->getCalledFunction())
354 if (isa<Constant>(CI->getArgOperand(0)))
359void AggressiveDeadCodeElimination::markLiveInstructions() {
364 while (!Worklist.empty()) {
372 if (
auto *PN = dyn_cast<PHINode>(LiveInst))
378 markLiveBranchesFromControlDependences();
380 }
while (!Worklist.empty());
383void AggressiveDeadCodeElimination::markLive(
Instruction *
I) {
384 auto &
Info = InstInfo[
I];
390 Worklist.push_back(
I);
394 collectLiveScopes(*
DL);
397 auto &BBInfo = *
Info.Block;
398 if (BBInfo.Terminator ==
I) {
399 BlocksWithDeadTerminators.remove(BBInfo.BB);
402 if (!BBInfo.UnconditionalBranch)
409void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {
412 LLVM_DEBUG(
dbgs() <<
"mark block live: " << BBInfo.BB->getName() <<
'\n');
414 if (!BBInfo.CFLive) {
415 BBInfo.CFLive =
true;
416 NewLiveBlocks.insert(BBInfo.BB);
421 if (BBInfo.UnconditionalBranch)
422 markLive(BBInfo.Terminator);
425void AggressiveDeadCodeElimination::collectLiveScopes(
const DILocalScope &LS) {
426 if (!AliveScopes.insert(&LS).second)
429 if (isa<DISubprogram>(LS))
433 collectLiveScopes(cast<DILocalScope>(*
LS.getScope()));
436void AggressiveDeadCodeElimination::collectLiveScopes(
const DILocation &
DL) {
439 if (!AliveScopes.insert(&
DL).second)
443 collectLiveScopes(*
DL.getScope());
447 collectLiveScopes(*IA);
450void AggressiveDeadCodeElimination::markPhiLive(
PHINode *PN) {
453 if (
Info.HasLivePhiNodes)
455 Info.HasLivePhiNodes =
true;
461 auto &
Info = BlockInfo[PredBB];
464 NewLiveBlocks.insert(PredBB);
469void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
470 if (BlocksWithDeadTerminators.empty())
474 dbgs() <<
"new live blocks:\n";
475 for (
auto *BB : NewLiveBlocks)
476 dbgs() <<
"\t" << BB->getName() <<
'\n';
477 dbgs() <<
"dead terminator blocks:\n";
478 for (
auto *BB : BlocksWithDeadTerminators)
479 dbgs() <<
"\t" << BB->getName() <<
'\n';
489 BlocksWithDeadTerminators.
begin(),
490 BlocksWithDeadTerminators.end()
494 IDFs.setDefiningBlocks(NewLiveBlocks);
495 IDFs.setLiveInBlocks(BWDT);
496 IDFs.calculate(IDFBlocks);
497 NewLiveBlocks.clear();
500 for (
auto *BB : IDFBlocks) {
501 LLVM_DEBUG(
dbgs() <<
"live control in: " << BB->getName() <<
'\n');
502 markLive(BB->getTerminator());
511ADCEChanged AggressiveDeadCodeElimination::removeDeadInstructions() {
514 Changed.ChangedControlFlow = updateDeadRegions();
522 if (
auto *DII = dyn_cast<DbgVariableIntrinsic>(&
I)) {
524 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
530 for (
Value *V : DII->location_ops()) {
531 if (Instruction *II = dyn_cast<Instruction>(V)) {
533 dbgs() <<
"Dropping debug info for " << *DII <<
"\n";
557 if (AliveScopes.count(DR.getDebugLoc()->getScope()))
559 I.dropOneDbgRecord(&DR);
566 if (
auto *DII = dyn_cast<DbgInfoIntrinsic>(&
I)) {
569 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII))
573 if (AliveScopes.count(DII->getDebugLoc()->getScope()))
578 Changed.ChangedNonDebugInstr =
true;
582 Worklist.push_back(&
I);
587 I->dropAllReferences();
591 I->eraseFromParent();
594 Changed.ChangedAnything = Changed.ChangedControlFlow || !Worklist.empty();
600bool AggressiveDeadCodeElimination::updateDeadRegions() {
602 dbgs() <<
"final dead terminator blocks: " <<
'\n';
603 for (
auto *BB : BlocksWithDeadTerminators)
604 dbgs() <<
'\t' << BB->getName()
605 << (BlockInfo[BB].Live ?
" LIVE\n" :
"\n");
609 bool HavePostOrder =
false;
610 bool Changed =
false;
613 for (
auto *BB : BlocksWithDeadTerminators) {
614 auto &
Info = BlockInfo[BB];
615 if (
Info.UnconditionalBranch) {
616 InstInfo[
Info.Terminator].Live =
true;
620 if (!HavePostOrder) {
621 computeReversePostOrder();
622 HavePostOrder =
true;
628 BlockInfoType *PreferredSucc =
nullptr;
630 auto *
Info = &BlockInfo[Succ];
631 if (!PreferredSucc || PreferredSucc->PostOrder <
Info->PostOrder)
632 PreferredSucc =
Info;
634 assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
635 "Failed to find safe successor for dead branch");
641 if (!
First || Succ != PreferredSucc->BB) {
642 Succ->removePredecessor(BB);
643 RemovedSuccessors.
insert(Succ);
647 makeUnconditional(BB, PreferredSucc->BB);
650 for (
auto *Succ : RemovedSuccessors) {
653 if (Succ != PreferredSucc->BB) {
654 LLVM_DEBUG(
dbgs() <<
"ADCE: (Post)DomTree edge enqueued for deletion"
655 << BB->getName() <<
" -> " << Succ->getName()
657 DeletedEdges.
push_back({DominatorTree::Delete, BB, Succ});
661 NumBranchesRemoved += 1;
665 if (!DeletedEdges.
empty())
673void AggressiveDeadCodeElimination::computeReversePostOrder() {
682 unsigned PostOrder = 0;
687 BlockInfo[
Block].PostOrder = PostOrder++;
691void AggressiveDeadCodeElimination::makeUnconditional(
BasicBlock *BB,
696 collectLiveScopes(*
DL);
701 InstInfo[PredTerm].Live =
true;
705 NumBranchesRemoved += 1;
707 auto *NewTerm = Builder.CreateBr(
Target);
708 InstInfo[NewTerm].Live =
true;
710 NewTerm->setDebugLoc(
DL);
712 InstInfo.erase(PredTerm);
726 ADCEChanged Changed =
727 AggressiveDeadCodeElimination(
F, DT, PDT).performDeadCodeElimination();
728 if (!Changed.ChangedAnything)
732 if (!Changed.ChangedControlFlow) {
734 if (!Changed.ChangedNonDebugInstr) {
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isUnconditionalBranch(Instruction *Term)
static cl::opt< bool > RemoveLoops("adce-remove-loops", cl::init(false), cl::Hidden)
static cl::opt< bool > RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden)
Expand Atomic instructions
Analysis containing CSE Info
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
static bool isAlwaysLive(Instruction *I)
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This is the interface for a simple mod/ref and alias analysis over globals.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This file implements a map that provides insertion order iteration.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
This defines the Use class.
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
LLVM Basic Block Representation.
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...
Represents analyses that only rely on functions' control flow.
This class represents a function call, abstracting a target machine's calling convention.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
Base class for non-instruction debug metadata records that have positions within IR.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
This class implements a map that also provides access to all stored values in a deterministic order.
An analysis that produces MemorySSA for a function.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Target - Wrapper for Target specific information.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
StringRef getName() const
Return a constant reference to the value's name.
void dump() const
Support for debugging, callable in GDB: V->dump()
AssignmentInstRange getAssignmentInsts(DIAssignID *ID)
Return a range of instructions (typically just one) that have ID as an attachment.
initializer< Ty > init(const Ty &Val)
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool succ_empty(const Instruction *I)
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
auto predecessors(const MachineBasicBlock *BB)
StringRef getInstrProfValueProfFuncName()
Return the name profile runtime entry point to do value profiling for a given site.
iterator_range< df_iterator< T > > depth_first(const T &G)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)