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