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