LLVM  10.0.0svn
ADCE.cpp
Go to the documentation of this file.
1 //===- ADCE.cpp - Code to perform dead code elimination -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the Aggressive Dead Code Elimination pass. This pass
10 // optimistically assumes that all instructions are dead until proven otherwise,
11 // allowing it to eliminate dead computations that other DCE passes do not
12 // catch, particularly involving loop computations.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/MapVector.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Statistic.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CFG.h"
33 #include "llvm/IR/DebugLoc.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  SmallSetVector<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())
347  if (Callee->getName().equals(getInstrProfValueProfFuncName()))
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.remove(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  BlocksWithDeadTerminators.begin(),
484  BlocksWithDeadTerminators.end()
485  };
487  ReverseIDFCalculator IDFs(PDT);
488  IDFs.setDefiningBlocks(NewLiveBlocks);
489  IDFs.setLiveInBlocks(BWDT);
490  IDFs.calculate(IDFBlocks);
491  NewLiveBlocks.clear();
492 
493  // Dead terminators which control live blocks are now marked live.
494  for (auto *BB : IDFBlocks) {
495  LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
496  markLive(BB->getTerminator());
497  }
498 }
499 
500 //===----------------------------------------------------------------------===//
501 //
502 // Routines to update the CFG and SSA information before removing dead code.
503 //
504 //===----------------------------------------------------------------------===//
505 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
506  // Updates control and dataflow around dead blocks
507  updateDeadRegions();
508 
509  LLVM_DEBUG({
510  for (Instruction &I : instructions(F)) {
511  // Check if the instruction is alive.
512  if (isLive(&I))
513  continue;
514 
515  if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
516  // Check if the scope of this variable location is alive.
517  if (AliveScopes.count(DII->getDebugLoc()->getScope()))
518  continue;
519 
520  // If intrinsic is pointing at a live SSA value, there may be an
521  // earlier optimization bug: if we know the location of the variable,
522  // why isn't the scope of the location alive?
523  if (Value *V = DII->getVariableLocation())
524  if (Instruction *II = dyn_cast<Instruction>(V))
525  if (isLive(II))
526  dbgs() << "Dropping debug info for " << *DII << "\n";
527  }
528  }
529  });
530 
531  // The inverse of the live set is the dead set. These are those instructions
532  // that have no side effects and do not influence the control flow or return
533  // value of the function, and may therefore be deleted safely.
534  // NOTE: We reuse the Worklist vector here for memory efficiency.
535  for (Instruction &I : instructions(F)) {
536  // Check if the instruction is alive.
537  if (isLive(&I))
538  continue;
539 
540  if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
541  // Check if the scope of this variable location is alive.
542  if (AliveScopes.count(DII->getDebugLoc()->getScope()))
543  continue;
544 
545  // Fallthrough and drop the intrinsic.
546  }
547 
548  // Prepare to delete.
549  Worklist.push_back(&I);
550  I.dropAllReferences();
551  }
552 
553  for (Instruction *&I : Worklist) {
554  ++NumRemoved;
555  I->eraseFromParent();
556  }
557 
558  return !Worklist.empty();
559 }
560 
561 // A dead region is the set of dead blocks with a common live post-dominator.
562 void AggressiveDeadCodeElimination::updateDeadRegions() {
563  LLVM_DEBUG({
564  dbgs() << "final dead terminator blocks: " << '\n';
565  for (auto *BB : BlocksWithDeadTerminators)
566  dbgs() << '\t' << BB->getName()
567  << (BlockInfo[BB].Live ? " LIVE\n" : "\n");
568  });
569 
570  // Don't compute the post ordering unless we needed it.
571  bool HavePostOrder = false;
572 
573  for (auto *BB : BlocksWithDeadTerminators) {
574  auto &Info = BlockInfo[BB];
575  if (Info.UnconditionalBranch) {
576  InstInfo[Info.Terminator].Live = true;
577  continue;
578  }
579 
580  if (!HavePostOrder) {
581  computeReversePostOrder();
582  HavePostOrder = true;
583  }
584 
585  // Add an unconditional branch to the successor closest to the
586  // end of the function which insures a path to the exit for each
587  // live edge.
588  BlockInfoType *PreferredSucc = nullptr;
589  for (auto *Succ : successors(BB)) {
590  auto *Info = &BlockInfo[Succ];
591  if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
592  PreferredSucc = Info;
593  }
594  assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
595  "Failed to find safe successor for dead branch");
596 
597  // Collect removed successors to update the (Post)DominatorTrees.
598  SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
599  bool First = true;
600  for (auto *Succ : successors(BB)) {
601  if (!First || Succ != PreferredSucc->BB) {
602  Succ->removePredecessor(BB);
603  RemovedSuccessors.insert(Succ);
604  } else
605  First = false;
606  }
607  makeUnconditional(BB, PreferredSucc->BB);
608 
609  // Inform the dominators about the deleted CFG edges.
611  for (auto *Succ : RemovedSuccessors) {
612  // It might have happened that the same successor appeared multiple times
613  // and the CFG edge wasn't really removed.
614  if (Succ != PreferredSucc->BB) {
615  LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
616  << BB->getName() << " -> " << Succ->getName()
617  << "\n");
618  DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
619  }
620  }
621 
623  .applyUpdates(DeletedEdges);
624 
625  NumBranchesRemoved += 1;
626  }
627 }
628 
629 // reverse top-sort order
630 void AggressiveDeadCodeElimination::computeReversePostOrder() {
631  // This provides a post-order numbering of the reverse control flow graph
632  // Note that it is incomplete in the presence of infinite loops but we don't
633  // need numbers blocks which don't reach the end of the functions since
634  // all branches in those blocks are forced live.
635 
636  // For each block without successors, extend the DFS from the block
637  // backward through the graph
639  unsigned PostOrder = 0;
640  for (auto &BB : F) {
641  if (succ_begin(&BB) != succ_end(&BB))
642  continue;
643  for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
644  BlockInfo[Block].PostOrder = PostOrder++;
645  }
646 }
647 
648 void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
649  BasicBlock *Target) {
650  Instruction *PredTerm = BB->getTerminator();
651  // Collect the live debug info scopes attached to this instruction.
652  if (const DILocation *DL = PredTerm->getDebugLoc())
653  collectLiveScopes(*DL);
654 
655  // Just mark live an existing unconditional branch
656  if (isUnconditionalBranch(PredTerm)) {
657  PredTerm->setSuccessor(0, Target);
658  InstInfo[PredTerm].Live = true;
659  return;
660  }
661  LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
662  NumBranchesRemoved += 1;
663  IRBuilder<> Builder(PredTerm);
664  auto *NewTerm = Builder.CreateBr(Target);
665  InstInfo[NewTerm].Live = true;
666  if (const DILocation *DL = PredTerm->getDebugLoc())
667  NewTerm->setDebugLoc(DL);
668 
669  InstInfo.erase(PredTerm);
670  PredTerm->eraseFromParent();
671 }
672 
673 //===----------------------------------------------------------------------===//
674 //
675 // Pass Manager integration code
676 //
677 //===----------------------------------------------------------------------===//
679  // ADCE does not need DominatorTree, but require DominatorTree here
680  // to update analysis if it is already available.
681  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
682  auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
683  if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
684  return PreservedAnalyses::all();
685 
687  PA.preserveSet<CFGAnalyses>();
688  PA.preserve<GlobalsAA>();
691  return PA;
692 }
693 
694 namespace {
695 
696 struct ADCELegacyPass : public FunctionPass {
697  static char ID; // Pass identification, replacement for typeid
698 
699  ADCELegacyPass() : FunctionPass(ID) {
701  }
702 
703  bool runOnFunction(Function &F) override {
704  if (skipFunction(F))
705  return false;
706 
707  // ADCE does not need DominatorTree, but require DominatorTree here
708  // to update analysis if it is already available.
709  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
710  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
711  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
712  return AggressiveDeadCodeElimination(F, DT, PDT)
713  .performDeadCodeElimination();
714  }
715 
716  void getAnalysisUsage(AnalysisUsage &AU) const override {
719  AU.setPreservesCFG();
720  else {
723  }
725  }
726 };
727 
728 } // end anonymous namespace
729 
730 char ADCELegacyPass::ID = 0;
731 
732 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
733  "Aggressive Dead Code Elimination", false, false)
736  false, false)
737 
738 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:67
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
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:294
Aggressive Dead Code Elimination
Definition: ADCE.cpp:735
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
adce
Definition: ADCE.cpp:735
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:128
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:37
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
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:137
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
This defines the Use class.
void calculate(SmallVectorImpl< NodeTy *> &IDFBlocks)
Calculate iterated dominance frontiers.
A scope for locals.
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4424
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
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:55
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
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:102
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:144
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:657
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:318
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void setLiveInBlocks(const SmallPtrSetImpl< NodeTy *> &Blocks)
Give the IDF calculator the set of blocks in which the value is live on entry to the block...
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:72
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:370
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:572
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:284
op_range operands()
Definition: User.h:237
DIScope * getScope() const
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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:1213
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: ADCE.cpp:678
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy *> &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Analysis pass which computes a PostDominatorTree.
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
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.
amdgpu Simplify well known AMD library false FunctionCallee Callee
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:114
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:321
iterator begin() const
Definition: SmallPtrSet.h:396
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: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:795
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:332
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
static bool isAlwaysLive(Instruction *I)
succ_range successors(Instruction *I)
Definition: CFG.h:259
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional &#39;br label X&#39; instruction.
Definition: IRBuilder.h:884
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:583
inst_range instructions(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
FunctionPass * createAggressiveDCEPass()
Definition: ADCE.cpp:738
const BasicBlock * getParent() const
Definition: Instruction.h:66