LLVM  16.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"
32 #include "llvm/IR/DebugInfo.h"
34 #include "llvm/IR/DebugLoc.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/IRBuilder.h"
38 #include "llvm/IR/InstIterator.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 (const 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  // Avoid removing a dbg.assign that is linked to instructions because it
548  // holds information about an existing store.
549  if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII))
550  if (!at::getAssignmentInsts(DAI).empty())
551  continue;
552  // Check if the scope of this variable location is alive.
553  if (AliveScopes.count(DII->getDebugLoc()->getScope()))
554  continue;
555 
556  // Fallthrough and drop the intrinsic.
557  }
558 
559  // Prepare to delete.
560  Worklist.push_back(&I);
562  }
563 
564  for (Instruction *&I : Worklist)
565  I->dropAllReferences();
566 
567  for (Instruction *&I : Worklist) {
568  ++NumRemoved;
569  I->eraseFromParent();
570  }
571 
572  return !Worklist.empty() || RegionsUpdated;
573 }
574 
575 // A dead region is the set of dead blocks with a common live post-dominator.
576 bool AggressiveDeadCodeElimination::updateDeadRegions() {
577  LLVM_DEBUG({
578  dbgs() << "final dead terminator blocks: " << '\n';
579  for (auto *BB : BlocksWithDeadTerminators)
580  dbgs() << '\t' << BB->getName()
581  << (BlockInfo[BB].Live ? " LIVE\n" : "\n");
582  });
583 
584  // Don't compute the post ordering unless we needed it.
585  bool HavePostOrder = false;
586  bool Changed = false;
588 
589  for (auto *BB : BlocksWithDeadTerminators) {
590  auto &Info = BlockInfo[BB];
591  if (Info.UnconditionalBranch) {
592  InstInfo[Info.Terminator].Live = true;
593  continue;
594  }
595 
596  if (!HavePostOrder) {
597  computeReversePostOrder();
598  HavePostOrder = true;
599  }
600 
601  // Add an unconditional branch to the successor closest to the
602  // end of the function which insures a path to the exit for each
603  // live edge.
604  BlockInfoType *PreferredSucc = nullptr;
605  for (auto *Succ : successors(BB)) {
606  auto *Info = &BlockInfo[Succ];
607  if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
608  PreferredSucc = Info;
609  }
610  assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
611  "Failed to find safe successor for dead branch");
612 
613  // Collect removed successors to update the (Post)DominatorTrees.
614  SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
615  bool First = true;
616  for (auto *Succ : successors(BB)) {
617  if (!First || Succ != PreferredSucc->BB) {
618  Succ->removePredecessor(BB);
619  RemovedSuccessors.insert(Succ);
620  } else
621  First = false;
622  }
623  makeUnconditional(BB, PreferredSucc->BB);
624 
625  // Inform the dominators about the deleted CFG edges.
626  for (auto *Succ : RemovedSuccessors) {
627  // It might have happened that the same successor appeared multiple times
628  // and the CFG edge wasn't really removed.
629  if (Succ != PreferredSucc->BB) {
630  LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
631  << BB->getName() << " -> " << Succ->getName()
632  << "\n");
633  DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
634  }
635  }
636 
637  NumBranchesRemoved += 1;
638  Changed = true;
639  }
640 
641  if (!DeletedEdges.empty())
642  DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)
643  .applyUpdates(DeletedEdges);
644 
645  return Changed;
646 }
647 
648 // reverse top-sort order
649 void AggressiveDeadCodeElimination::computeReversePostOrder() {
650  // This provides a post-order numbering of the reverse control flow graph
651  // Note that it is incomplete in the presence of infinite loops but we don't
652  // need numbers blocks which don't reach the end of the functions since
653  // all branches in those blocks are forced live.
654 
655  // For each block without successors, extend the DFS from the block
656  // backward through the graph
658  unsigned PostOrder = 0;
659  for (auto &BB : F) {
660  if (!succ_empty(&BB))
661  continue;
662  for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
663  BlockInfo[Block].PostOrder = PostOrder++;
664  }
665 }
666 
667 void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
668  BasicBlock *Target) {
669  Instruction *PredTerm = BB->getTerminator();
670  // Collect the live debug info scopes attached to this instruction.
671  if (const DILocation *DL = PredTerm->getDebugLoc())
672  collectLiveScopes(*DL);
673 
674  // Just mark live an existing unconditional branch
675  if (isUnconditionalBranch(PredTerm)) {
676  PredTerm->setSuccessor(0, Target);
677  InstInfo[PredTerm].Live = true;
678  return;
679  }
680  LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
681  NumBranchesRemoved += 1;
682  IRBuilder<> Builder(PredTerm);
683  auto *NewTerm = Builder.CreateBr(Target);
684  InstInfo[NewTerm].Live = true;
685  if (const DILocation *DL = PredTerm->getDebugLoc())
686  NewTerm->setDebugLoc(DL);
687 
688  InstInfo.erase(PredTerm);
689  PredTerm->eraseFromParent();
690 }
691 
692 //===----------------------------------------------------------------------===//
693 //
694 // Pass Manager integration code
695 //
696 //===----------------------------------------------------------------------===//
698  // ADCE does not need DominatorTree, but require DominatorTree here
699  // to update analysis if it is already available.
702  if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
703  return PreservedAnalyses::all();
704 
706  // TODO: We could track if we have actually done CFG changes.
708  PA.preserveSet<CFGAnalyses>();
709  else {
712  }
713  return PA;
714 }
715 
716 namespace {
717 
718 struct ADCELegacyPass : public FunctionPass {
719  static char ID; // Pass identification, replacement for typeid
720 
721  ADCELegacyPass() : FunctionPass(ID) {
723  }
724 
725  bool runOnFunction(Function &F) override {
726  if (skipFunction(F))
727  return false;
728 
729  // ADCE does not need DominatorTree, but require DominatorTree here
730  // to update analysis if it is already available.
731  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
732  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
733  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
734  return AggressiveDeadCodeElimination(F, DT, PDT)
735  .performDeadCodeElimination();
736  }
737 
738  void getAnalysisUsage(AnalysisUsage &AU) const override {
741  AU.setPreservesCFG();
742  else {
745  }
747  }
748 };
749 
750 } // end anonymous namespace
751 
752 char ADCELegacyPass::ID = 0;
753 
754 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
755  "Aggressive Dead Code Elimination", false, false)
759 
760 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:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:774
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:60
llvm::Value::dump
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4918
Pass.h
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:150
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1600
DenseMap.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
isAlwaysLive
static bool isAlwaysLive(Instruction *I)
Definition: DemandedBits.cpp:75
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:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
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:150
Aggressive
static cl::opt< bool > Aggressive("aggressive-ext-opt", cl::Hidden, cl::desc("Aggressive extension optimization"))
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
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:55
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:24
PostDominators.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:141
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:252
llvm::Instruction
Definition: Instruction.h:42
InstrProf.h
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:306
llvm::salvageDebugInfo
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1361
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::AArch64PACKey::IA
@ IA
Definition: AArch64BaseInfo.h:819
DebugLoc.h
SmallPtrSet.h
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::at::getAssignmentInsts
AssignmentInstRange getAssignmentInsts(DIAssignID *ID)
Return a range of instructions (typically just one) that have ID as an attachment.
Definition: DebugInfo.cpp:1681
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
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:81
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:1754
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::DenseMap
Definition: DenseMap.h:714
DebugInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
ADCE.h
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IDFCalculator
Definition: IteratedDominanceFrontier.h:39
Elimination
Aggressive Dead Code Elimination
Definition: ADCE.cpp:757
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:259
adce
adce
Definition: ADCE.cpp:757
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:265
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:838
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:113
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:187
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::createAggressiveDCEPass
FunctionPass * createAggressiveDCEPass()
Definition: ADCE.cpp:760
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::ISD::BR
@ BR
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:982
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:793
Casting.h
Function.h
PassManager.h
IteratedDominanceFrontier.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:271
Instructions.h
PostOrderIterator.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:359
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
llvm::PHINode
Definition: Instructions.h:2697
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
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:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
llvm::getInstrProfValueProfFuncName
StringRef getInstrProfValueProfFuncName()
Return the name profile runtime entry point to do value profiling for a given site.
Definition: InstrProf.h:79
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
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:1570
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:157
Debug.h
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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:365