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