LLVM  8.0.1
ADCE.cpp
Go to the documentation of this file.
1 //===- ADCE.cpp - Code to perform dead code elimination -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the Aggressive Dead Code Elimination pass. This pass
11 // optimistically assumes that all instructions are dead until proven otherwise,
12 // allowing it to eliminate dead computations that other DCE passes do not
13 // catch, particularly involving loop computations.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/MapVector.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Statistic.h"
29 #include "llvm/IR/BasicBlock.h"
30 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/DebugLoc.h"
33 #include "llvm/IR/DomTreeUpdater.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/IR/IRBuilder.h"
37 #include "llvm/IR/InstIterator.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instruction.h"
40 #include "llvm/IR/Instructions.h"
41 #include "llvm/IR/IntrinsicInst.h"
42 #include "llvm/IR/PassManager.h"
43 #include "llvm/IR/Use.h"
44 #include "llvm/IR/Value.h"
45 #include "llvm/Pass.h"
47 #include "llvm/Support/Casting.h"
49 #include "llvm/Support/Debug.h"
51 #include "llvm/Transforms/Scalar.h"
52 #include <cassert>
53 #include <cstddef>
54 #include <utility>
55 
56 using namespace llvm;
57 
58 #define DEBUG_TYPE "adce"
59 
60 STATISTIC(NumRemoved, "Number of instructions removed");
61 STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");
62 
63 // This is a temporary option until we change the interface to this pass based
64 // on optimization level.
65 static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow",
66  cl::init(true), cl::Hidden);
67 
68 // This option enables removing of may-be-infinite loops which have no other
69 // effect.
70 static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false),
71  cl::Hidden);
72 
73 namespace {
74 
75 /// Information about Instructions
76 struct InstInfoType {
77  /// True if the associated instruction is live.
78  bool Live = false;
79 
80  /// Quick access to information for block containing associated Instruction.
81  struct BlockInfoType *Block = nullptr;
82 };
83 
84 /// Information about basic blocks relevant to dead code elimination.
85 struct BlockInfoType {
86  /// True when this block contains a live instructions.
87  bool Live = false;
88 
89  /// True when this block ends in an unconditional branch.
90  bool UnconditionalBranch = false;
91 
92  /// True when this block is known to have live PHI nodes.
93  bool HasLivePhiNodes = false;
94 
95  /// Control dependence sources need to be live for this block.
96  bool CFLive = false;
97 
98  /// Quick access to the LiveInfo for the terminator,
99  /// holds the value &InstInfo[Terminator]
100  InstInfoType *TerminatorLiveInfo = nullptr;
101 
102  /// Corresponding BasicBlock.
103  BasicBlock *BB = nullptr;
104 
105  /// Cache of BB->getTerminator().
106  Instruction *Terminator = nullptr;
107 
108  /// Post-order numbering of reverse control flow graph.
109  unsigned PostOrder;
110 
111  bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }
112 };
113 
114 class AggressiveDeadCodeElimination {
115  Function &F;
116 
117  // ADCE does not use DominatorTree per se, but it updates it to preserve the
118  // analysis.
119  DominatorTree *DT;
120  PostDominatorTree &PDT;
121 
122  /// Mapping of blocks to associated information, an element in BlockInfoVec.
123  /// Use MapVector to get deterministic iteration order.
125  bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }
126 
127  /// Mapping of instructions to associated information.
129  bool isLive(Instruction *I) { return InstInfo[I].Live; }
130 
131  /// Instructions known to be live where we need to mark
132  /// reaching definitions as live.
134 
135  /// Debug info scopes around a live instruction.
137 
138  /// Set of blocks with not known to have live terminators.
139  SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators;
140 
141  /// The set of blocks which we have determined whose control
142  /// dependence sources must be live and which have not had
143  /// those dependences analyzed.
144  SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;
145 
146  /// Set up auxiliary data structures for Instructions and BasicBlocks and
147  /// initialize the Worklist to the set of must-be-live Instruscions.
148  void initialize();
149 
150  /// Return true for operations which are always treated as live.
151  bool isAlwaysLive(Instruction &I);
152 
153  /// Return true for instrumentation instructions for value profiling.
154  bool isInstrumentsConstant(Instruction &I);
155 
156  /// Propagate liveness to reaching definitions.
157  void markLiveInstructions();
158 
159  /// Mark an instruction as live.
160  void markLive(Instruction *I);
161 
162  /// Mark a block as live.
163  void markLive(BlockInfoType &BB);
164  void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); }
165 
166  /// Mark terminators of control predecessors of a PHI node live.
167  void markPhiLive(PHINode *PN);
168 
169  /// Record the Debug Scopes which surround live debug information.
170  void collectLiveScopes(const DILocalScope &LS);
171  void collectLiveScopes(const DILocation &DL);
172 
173  /// Analyze dead branches to find those whose branches are the sources
174  /// of control dependences impacting a live block. Those branches are
175  /// marked live.
176  void markLiveBranchesFromControlDependences();
177 
178  /// Remove instructions not marked live, return if any instruction was
179  /// removed.
180  bool removeDeadInstructions();
181 
182  /// Identify connected sections of the control flow graph which have
183  /// dead terminators and rewrite the control flow graph to remove them.
184  void updateDeadRegions();
185 
186  /// Set the BlockInfo::PostOrder field based on a post-order
187  /// numbering of the reverse control flow graph.
188  void computeReversePostOrder();
189 
190  /// Make the terminator of this block an unconditional branch to \p Target.
191  void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
192 
193 public:
194  AggressiveDeadCodeElimination(Function &F, DominatorTree *DT,
195  PostDominatorTree &PDT)
196  : F(F), DT(DT), PDT(PDT) {}
197 
198  bool performDeadCodeElimination();
199 };
200 
201 } // end anonymous namespace
202 
203 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
204  initialize();
205  markLiveInstructions();
206  return removeDeadInstructions();
207 }
208 
209 static bool isUnconditionalBranch(Instruction *Term) {
210  auto *BR = dyn_cast<BranchInst>(Term);
211  return BR && BR->isUnconditional();
212 }
213 
215  auto NumBlocks = F.size();
216 
217  // We will have an entry in the map for each block so we grow the
218  // structure to twice that size to keep the load factor low in the hash table.
219  BlockInfo.reserve(NumBlocks);
220  size_t NumInsts = 0;
221 
222  // Iterate over blocks and initialize BlockInfoVec entries, count
223  // instructions to size the InstInfo hash table.
224  for (auto &BB : F) {
225  NumInsts += BB.size();
226  auto &Info = BlockInfo[&BB];
227  Info.BB = &BB;
228  Info.Terminator = BB.getTerminator();
229  Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator);
230  }
231 
232  // Initialize instruction map and set pointers to block info.
233  InstInfo.reserve(NumInsts);
234  for (auto &BBInfo : BlockInfo)
235  for (Instruction &I : *BBInfo.second.BB)
236  InstInfo[&I].Block = &BBInfo.second;
237 
238  // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not
239  // add any more elements to either after this point.
240  for (auto &BBInfo : BlockInfo)
241  BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];
242 
243  // Collect the set of "root" instructions that are known live.
244  for (Instruction &I : instructions(F))
245  if (isAlwaysLive(I))
246  markLive(&I);
247 
249  return;
250 
251  if (!RemoveLoops) {
252  // This stores state for the depth-first iterator. In addition
253  // to recording which nodes have been visited we also record whether
254  // a node is currently on the "stack" of active ancestors of the current
255  // node.
256  using StatusMap = DenseMap<BasicBlock *, bool>;
257 
258  class DFState : public StatusMap {
259  public:
260  std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) {
261  return StatusMap::insert(std::make_pair(BB, true));
262  }
263 
264  // Invoked after we have visited all children of a node.
265  void completed(BasicBlock *BB) { (*this)[BB] = false; }
266 
267  // Return true if \p BB is currently on the active stack
268  // of ancestors.
269  bool onStack(BasicBlock *BB) {
270  auto Iter = find(BB);
271  return Iter != end() && Iter->second;
272  }
273  } State;
274 
275  State.reserve(F.size());
276  // Iterate over blocks in depth-first pre-order and
277  // treat all edges to a block already seen as loop back edges
278  // and mark the branch live it if there is a back edge.
279  for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {
280  Instruction *Term = BB->getTerminator();
281  if (isLive(Term))
282  continue;
283 
284  for (auto *Succ : successors(BB))
285  if (State.onStack(Succ)) {
286  // back edge....
287  markLive(Term);
288  break;
289  }
290  }
291  }
292 
293  // Mark blocks live if there is no path from the block to a
294  // return of the function.
295  // We do this by seeing which of the postdomtree root children exit the
296  // program, and for all others, mark the subtree live.
297  for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
298  auto *BB = PDTChild->getBlock();
299  auto &Info = BlockInfo[BB];
300  // Real function return
301  if (isa<ReturnInst>(Info.Terminator)) {
302  LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()
303  << '\n';);
304  continue;
305  }
306 
307  // This child is something else, like an infinite loop.
308  for (auto DFNode : depth_first(PDTChild))
309  markLive(BlockInfo[DFNode->getBlock()].Terminator);
310  }
311 
312  // Treat the entry block as always live
313  auto *BB = &F.getEntryBlock();
314  auto &EntryInfo = BlockInfo[BB];
315  EntryInfo.Live = true;
316  if (EntryInfo.UnconditionalBranch)
317  markLive(EntryInfo.Terminator);
318 
319  // Build initial collection of blocks with dead terminators
320  for (auto &BBInfo : BlockInfo)
321  if (!BBInfo.second.terminatorIsLive())
322  BlocksWithDeadTerminators.insert(BBInfo.second.BB);
323 }
324 
326  // TODO -- use llvm::isInstructionTriviallyDead
327  if (I.isEHPad() || I.mayHaveSideEffects()) {
328  // Skip any value profile instrumentation calls if they are
329  // instrumenting constants.
330  if (isInstrumentsConstant(I))
331  return false;
332  return true;
333  }
334  if (!I.isTerminator())
335  return false;
336  if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I)))
337  return false;
338  return true;
339 }
340 
341 // Check if this instruction is a runtime call for value profiling and
342 // if it's instrumenting a constant.
343 bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) {
344  // TODO -- move this test into llvm::isInstructionTriviallyDead
345  if (CallInst *CI = dyn_cast<CallInst>(&I))
346  if (Function *Callee = CI->getCalledFunction())
348  if (isa<Constant>(CI->getArgOperand(0)))
349  return true;
350  return false;
351 }
352 
353 void AggressiveDeadCodeElimination::markLiveInstructions() {
354  // Propagate liveness backwards to operands.
355  do {
356  // Worklist holds newly discovered live instructions
357  // where we need to mark the inputs as live.
358  while (!Worklist.empty()) {
359  Instruction *LiveInst = Worklist.pop_back_val();
360  LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump(););
361 
362  for (Use &OI : LiveInst->operands())
363  if (Instruction *Inst = dyn_cast<Instruction>(OI))
364  markLive(Inst);
365 
366  if (auto *PN = dyn_cast<PHINode>(LiveInst))
367  markPhiLive(PN);
368  }
369 
370  // After data flow liveness has been identified, examine which branch
371  // decisions are required to determine live instructions are executed.
372  markLiveBranchesFromControlDependences();
373 
374  } while (!Worklist.empty());
375 }
376 
377 void AggressiveDeadCodeElimination::markLive(Instruction *I) {
378  auto &Info = InstInfo[I];
379  if (Info.Live)
380  return;
381 
382  LLVM_DEBUG(dbgs() << "mark live: "; I->dump());
383  Info.Live = true;
384  Worklist.push_back(I);
385 
386  // Collect the live debug info scopes attached to this instruction.
387  if (const DILocation *DL = I->getDebugLoc())
388  collectLiveScopes(*DL);
389 
390  // Mark the containing block live
391  auto &BBInfo = *Info.Block;
392  if (BBInfo.Terminator == I) {
393  BlocksWithDeadTerminators.erase(BBInfo.BB);
394  // For live terminators, mark destination blocks
395  // live to preserve this control flow edges.
396  if (!BBInfo.UnconditionalBranch)
397  for (auto *BB : successors(I->getParent()))
398  markLive(BB);
399  }
400  markLive(BBInfo);
401 }
402 
403 void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {
404  if (BBInfo.Live)
405  return;
406  LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
407  BBInfo.Live = true;
408  if (!BBInfo.CFLive) {
409  BBInfo.CFLive = true;
410  NewLiveBlocks.insert(BBInfo.BB);
411  }
412 
413  // Mark unconditional branches at the end of live
414  // blocks as live since there is no work to do for them later
415  if (BBInfo.UnconditionalBranch)
416  markLive(BBInfo.Terminator);
417 }
418 
419 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {
420  if (!AliveScopes.insert(&LS).second)
421  return;
422 
423  if (isa<DISubprogram>(LS))
424  return;
425 
426  // Tail-recurse through the scope chain.
427  collectLiveScopes(cast<DILocalScope>(*LS.getScope()));
428 }
429 
430 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {
431  // Even though DILocations are not scopes, shove them into AliveScopes so we
432  // don't revisit them.
433  if (!AliveScopes.insert(&DL).second)
434  return;
435 
436  // Collect live scopes from the scope chain.
437  collectLiveScopes(*DL.getScope());
438 
439  // Tail-recurse through the inlined-at chain.
440  if (const DILocation *IA = DL.getInlinedAt())
441  collectLiveScopes(*IA);
442 }
443 
444 void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) {
445  auto &Info = BlockInfo[PN->getParent()];
446  // Only need to check this once per block.
447  if (Info.HasLivePhiNodes)
448  return;
449  Info.HasLivePhiNodes = true;
450 
451  // If a predecessor block is not live, mark it as control-flow live
452  // which will trigger marking live branches upon which
453  // that block is control dependent.
454  for (auto *PredBB : predecessors(Info.BB)) {
455  auto &Info = BlockInfo[PredBB];
456  if (!Info.CFLive) {
457  Info.CFLive = true;
458  NewLiveBlocks.insert(PredBB);
459  }
460  }
461 }
462 
463 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
464  if (BlocksWithDeadTerminators.empty())
465  return;
466 
467  LLVM_DEBUG({
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';
474  });
475 
476  // The dominance frontier of a live block X in the reverse
477  // control graph is the set of blocks upon which X is control
478  // dependent. The following sequence computes the set of blocks
479  // which currently have dead terminators that are control
480  // dependence sources of a block which is in NewLiveBlocks.
481 
483  ReverseIDFCalculator IDFs(PDT);
484  IDFs.setDefiningBlocks(NewLiveBlocks);
485  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
486  IDFs.calculate(IDFBlocks);
487  NewLiveBlocks.clear();
488 
489  // Dead terminators which control live blocks are now marked live.
490  for (auto *BB : IDFBlocks) {
491  LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
492  markLive(BB->getTerminator());
493  }
494 }
495 
496 //===----------------------------------------------------------------------===//
497 //
498 // Routines to update the CFG and SSA information before removing dead code.
499 //
500 //===----------------------------------------------------------------------===//
501 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
502  // Updates control and dataflow around dead blocks
503  updateDeadRegions();
504 
505  LLVM_DEBUG({
506  for (Instruction &I : instructions(F)) {
507  // Check if the instruction is alive.
508  if (isLive(&I))
509  continue;
510 
511  if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
512  // Check if the scope of this variable location is alive.
513  if (AliveScopes.count(DII->getDebugLoc()->getScope()))
514  continue;
515 
516  // If intrinsic is pointing at a live SSA value, there may be an
517  // earlier optimization bug: if we know the location of the variable,
518  // why isn't the scope of the location alive?
519  if (Value *V = DII->getVariableLocation())
520  if (Instruction *II = dyn_cast<Instruction>(V))
521  if (isLive(II))
522  dbgs() << "Dropping debug info for " << *DII << "\n";
523  }
524  }
525  });
526 
527  // The inverse of the live set is the dead set. These are those instructions
528  // that have no side effects and do not influence the control flow or return
529  // value of the function, and may therefore be deleted safely.
530  // NOTE: We reuse the Worklist vector here for memory efficiency.
531  for (Instruction &I : instructions(F)) {
532  // Check if the instruction is alive.
533  if (isLive(&I))
534  continue;
535 
536  if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
537  // Check if the scope of this variable location is alive.
538  if (AliveScopes.count(DII->getDebugLoc()->getScope()))
539  continue;
540 
541  // Fallthrough and drop the intrinsic.
542  }
543 
544  // Prepare to delete.
545  Worklist.push_back(&I);
546  I.dropAllReferences();
547  }
548 
549  for (Instruction *&I : Worklist) {
550  ++NumRemoved;
551  I->eraseFromParent();
552  }
553 
554  return !Worklist.empty();
555 }
556 
557 // A dead region is the set of dead blocks with a common live post-dominator.
558 void AggressiveDeadCodeElimination::updateDeadRegions() {
559  LLVM_DEBUG({
560  dbgs() << "final dead terminator blocks: " << '\n';
561  for (auto *BB : BlocksWithDeadTerminators)
562  dbgs() << '\t' << BB->getName()
563  << (BlockInfo[BB].Live ? " LIVE\n" : "\n");
564  });
565 
566  // Don't compute the post ordering unless we needed it.
567  bool HavePostOrder = false;
568 
569  for (auto *BB : BlocksWithDeadTerminators) {
570  auto &Info = BlockInfo[BB];
571  if (Info.UnconditionalBranch) {
572  InstInfo[Info.Terminator].Live = true;
573  continue;
574  }
575 
576  if (!HavePostOrder) {
577  computeReversePostOrder();
578  HavePostOrder = true;
579  }
580 
581  // Add an unconditional branch to the successor closest to the
582  // end of the function which insures a path to the exit for each
583  // live edge.
584  BlockInfoType *PreferredSucc = nullptr;
585  for (auto *Succ : successors(BB)) {
586  auto *Info = &BlockInfo[Succ];
587  if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
588  PreferredSucc = Info;
589  }
590  assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
591  "Failed to find safe successor for dead branch");
592 
593  // Collect removed successors to update the (Post)DominatorTrees.
594  SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
595  bool First = true;
596  for (auto *Succ : successors(BB)) {
597  if (!First || Succ != PreferredSucc->BB) {
598  Succ->removePredecessor(BB);
599  RemovedSuccessors.insert(Succ);
600  } else
601  First = false;
602  }
603  makeUnconditional(BB, PreferredSucc->BB);
604 
605  // Inform the dominators about the deleted CFG edges.
607  for (auto *Succ : RemovedSuccessors) {
608  // It might have happened that the same successor appeared multiple times
609  // and the CFG edge wasn't really removed.
610  if (Succ != PreferredSucc->BB) {
611  LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
612  << BB->getName() << " -> " << Succ->getName()
613  << "\n");
614  DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
615  }
616  }
617 
619  .applyUpdates(DeletedEdges);
620 
621  NumBranchesRemoved += 1;
622  }
623 }
624 
625 // reverse top-sort order
626 void AggressiveDeadCodeElimination::computeReversePostOrder() {
627  // This provides a post-order numbering of the reverse control flow graph
628  // Note that it is incomplete in the presence of infinite loops but we don't
629  // need numbers blocks which don't reach the end of the functions since
630  // all branches in those blocks are forced live.
631 
632  // For each block without successors, extend the DFS from the block
633  // backward through the graph
635  unsigned PostOrder = 0;
636  for (auto &BB : F) {
637  if (succ_begin(&BB) != succ_end(&BB))
638  continue;
639  for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
640  BlockInfo[Block].PostOrder = PostOrder++;
641  }
642 }
643 
644 void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
645  BasicBlock *Target) {
646  Instruction *PredTerm = BB->getTerminator();
647  // Collect the live debug info scopes attached to this instruction.
648  if (const DILocation *DL = PredTerm->getDebugLoc())
649  collectLiveScopes(*DL);
650 
651  // Just mark live an existing unconditional branch
652  if (isUnconditionalBranch(PredTerm)) {
653  PredTerm->setSuccessor(0, Target);
654  InstInfo[PredTerm].Live = true;
655  return;
656  }
657  LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
658  NumBranchesRemoved += 1;
659  IRBuilder<> Builder(PredTerm);
660  auto *NewTerm = Builder.CreateBr(Target);
661  InstInfo[NewTerm].Live = true;
662  if (const DILocation *DL = PredTerm->getDebugLoc())
663  NewTerm->setDebugLoc(DL);
664 
665  InstInfo.erase(PredTerm);
666  PredTerm->eraseFromParent();
667 }
668 
669 //===----------------------------------------------------------------------===//
670 //
671 // Pass Manager integration code
672 //
673 //===----------------------------------------------------------------------===//
675  // ADCE does not need DominatorTree, but require DominatorTree here
676  // to update analysis if it is already available.
677  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
678  auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
679  if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
680  return PreservedAnalyses::all();
681 
683  PA.preserveSet<CFGAnalyses>();
684  PA.preserve<GlobalsAA>();
687  return PA;
688 }
689 
690 namespace {
691 
692 struct ADCELegacyPass : public FunctionPass {
693  static char ID; // Pass identification, replacement for typeid
694 
695  ADCELegacyPass() : FunctionPass(ID) {
697  }
698 
699  bool runOnFunction(Function &F) override {
700  if (skipFunction(F))
701  return false;
702 
703  // ADCE does not need DominatorTree, but require DominatorTree here
704  // to update analysis if it is already available.
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();
710  }
711 
712  void getAnalysisUsage(AnalysisUsage &AU) const override {
715  AU.setPreservesCFG();
716  else {
719  }
721  }
722 };
723 
724 } // end anonymous namespace
725 
726 char ADCELegacyPass::ID = 0;
727 
728 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
729  "Aggressive Dead Code Elimination", false, false)
732  false, false)
733 
734 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }
Legacy wrapper pass to provide the GlobalsAAResult object.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
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.
Definition: User.h:295
Aggressive Dead Code Elimination
Definition: ADCE.cpp:731
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
This class represents lattice values for constants.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
adce
Definition: ADCE.cpp:731
static cl::opt< bool > RemoveControlFlowFlag("adce-remove-control-flow", cl::init(true), cl::Hidden)
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isTerminator() const
Definition: Instruction.h:129
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...
Definition: MapVector.h:38
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
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...
Definition: BasicBlock.cpp:138
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
This defines the Use class.
A scope for locals.
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4298
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
void initializeADCELegacyPassPass(PassRegistry &)
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.
Definition: Use.h:56
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...
Definition: IRBuilder.h:743
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...
Definition: Interval.h:103
static bool isUnconditionalBranch(Instruction *Term)
Definition: ADCE.cpp:209
Debug location.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
amdgpu Simplify well known AMD library false Value * Callee
Analysis containing CSE Info
Definition: CSEInfo.cpp:21
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:629
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
StringRef getInstrProfValueProfFuncName()
Return the name profile runtime entry point to do value profiling for a given site.
Definition: InstrProf.h:73
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:562
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.
Definition: Pass.h:285
op_range operands()
Definition: User.h:238
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
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...
Definition: STLExtras.h:1207
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: ADCE.cpp:674
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...
Definition: SmallPtrSet.h:418
void calculate(SmallVectorImpl< BasicBlock *> &IDFBlocks)
Calculate iterated dominance frontiers.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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)
Definition: CFG.h:125
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
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&#39; control flow.
Definition: PassManager.h:115
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 ...
Definition: StringRef.h:169
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.
Definition: Instruction.h:311
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:789
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
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.
Definition: Value.h:73
static bool isAlwaysLive(Instruction *I)
succ_range successors(Instruction *I)
Definition: CFG.h:264
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional &#39;br label X&#39; instruction.
Definition: IRBuilder.h:848
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:573
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
FunctionPass * createAggressiveDCEPass()
Definition: ADCE.cpp:734
const BasicBlock * getParent() const
Definition: Instruction.h:67
DIScopeRef getScope() const