xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/ADCE.cpp (revision d56accc7c3dcc897489b6a07834763a03b9f3d68)
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 
16 #include "llvm/Transforms/Scalar/ADCE.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/MapVector.h"
21 #include "llvm/ADT/PostOrderIterator.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"
26 #include "llvm/Analysis/DomTreeUpdater.h"
27 #include "llvm/Analysis/GlobalsModRef.h"
28 #include "llvm/Analysis/IteratedDominanceFrontier.h"
29 #include "llvm/Analysis/PostDominators.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/DebugInfoMetadata.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"
47 #include "llvm/ProfileData/InstrProf.h"
48 #include "llvm/Support/Casting.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/raw_ostream.h"
52 #include "llvm/Transforms/Scalar.h"
53 #include "llvm/Transforms/Utils/Local.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.
126   MapVector<BasicBlock *, BlockInfoType> BlockInfo;
127   bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }
128 
129   /// Mapping of instructions to associated information.
130   DenseMap<Instruction *, InstInfoType> InstInfo;
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.
135   SmallVector<Instruction *, 128> Worklist;
136 
137   /// Debug info scopes around a live instruction.
138   SmallPtrSet<const Metadata *, 32> AliveScopes;
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 
211 static bool isUnconditionalBranch(Instruction *Term) {
212   auto *BR = dyn_cast<BranchInst>(Term);
213   return BR && BR->isUnconditional();
214 }
215 
216 void AggressiveDeadCodeElimination::initialize() {
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 
250   if (!RemoveControlFlowFlag)
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 
327 bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) {
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 
484   const SmallPtrSet<BasicBlock *, 16> BWDT{
485       BlocksWithDeadTerminators.begin(),
486       BlocksWithDeadTerminators.end()
487   };
488   SmallVector<BasicBlock *, 32> IDFBlocks;
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.
541   for (Instruction &I : llvm::reverse(instructions(F))) {
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);
556     salvageDebugInfo(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   SmallVector<DominatorTree::UpdateType, 10> DeletedEdges;
583 
584   for (auto *BB : BlocksWithDeadTerminators) {
585     auto &Info = BlockInfo[BB];
586     if (Info.UnconditionalBranch) {
587       InstInfo[Info.Terminator].Live = true;
588       continue;
589     }
590 
591     if (!HavePostOrder) {
592       computeReversePostOrder();
593       HavePostOrder = true;
594     }
595 
596     // Add an unconditional branch to the successor closest to the
597     // end of the function which insures a path to the exit for each
598     // live edge.
599     BlockInfoType *PreferredSucc = nullptr;
600     for (auto *Succ : successors(BB)) {
601       auto *Info = &BlockInfo[Succ];
602       if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
603         PreferredSucc = Info;
604     }
605     assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
606            "Failed to find safe successor for dead branch");
607 
608     // Collect removed successors to update the (Post)DominatorTrees.
609     SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
610     bool First = true;
611     for (auto *Succ : successors(BB)) {
612       if (!First || Succ != PreferredSucc->BB) {
613         Succ->removePredecessor(BB);
614         RemovedSuccessors.insert(Succ);
615       } else
616         First = false;
617     }
618     makeUnconditional(BB, PreferredSucc->BB);
619 
620     // 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     NumBranchesRemoved += 1;
633     Changed = true;
634   }
635 
636   if (!DeletedEdges.empty())
637     DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)
638         .applyUpdates(DeletedEdges);
639 
640   return Changed;
641 }
642 
643 // reverse top-sort order
644 void AggressiveDeadCodeElimination::computeReversePostOrder() {
645   // This provides a post-order numbering of the reverse control flow graph
646   // Note that it is incomplete in the presence of infinite loops but we don't
647   // need numbers blocks which don't reach the end of the functions since
648   // all branches in those blocks are forced live.
649 
650   // For each block without successors, extend the DFS from the block
651   // backward through the graph
652   SmallPtrSet<BasicBlock*, 16> Visited;
653   unsigned PostOrder = 0;
654   for (auto &BB : F) {
655     if (!succ_empty(&BB))
656       continue;
657     for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
658       BlockInfo[Block].PostOrder = PostOrder++;
659   }
660 }
661 
662 void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
663                                                       BasicBlock *Target) {
664   Instruction *PredTerm = BB->getTerminator();
665   // Collect the live debug info scopes attached to this instruction.
666   if (const DILocation *DL = PredTerm->getDebugLoc())
667     collectLiveScopes(*DL);
668 
669   // Just mark live an existing unconditional branch
670   if (isUnconditionalBranch(PredTerm)) {
671     PredTerm->setSuccessor(0, Target);
672     InstInfo[PredTerm].Live = true;
673     return;
674   }
675   LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
676   NumBranchesRemoved += 1;
677   IRBuilder<> Builder(PredTerm);
678   auto *NewTerm = Builder.CreateBr(Target);
679   InstInfo[NewTerm].Live = true;
680   if (const DILocation *DL = PredTerm->getDebugLoc())
681     NewTerm->setDebugLoc(DL);
682 
683   InstInfo.erase(PredTerm);
684   PredTerm->eraseFromParent();
685 }
686 
687 //===----------------------------------------------------------------------===//
688 //
689 // Pass Manager integration code
690 //
691 //===----------------------------------------------------------------------===//
692 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
693   // ADCE does not need DominatorTree, but require DominatorTree here
694   // to update analysis if it is already available.
695   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
696   auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
697   if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
698     return PreservedAnalyses::all();
699 
700   PreservedAnalyses PA;
701   // TODO: We could track if we have actually done CFG changes.
702   if (!RemoveControlFlowFlag)
703     PA.preserveSet<CFGAnalyses>();
704   else {
705     PA.preserve<DominatorTreeAnalysis>();
706     PA.preserve<PostDominatorTreeAnalysis>();
707   }
708   return PA;
709 }
710 
711 namespace {
712 
713 struct ADCELegacyPass : public FunctionPass {
714   static char ID; // Pass identification, replacement for typeid
715 
716   ADCELegacyPass() : FunctionPass(ID) {
717     initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
718   }
719 
720   bool runOnFunction(Function &F) override {
721     if (skipFunction(F))
722       return false;
723 
724     // ADCE does not need DominatorTree, but require DominatorTree here
725     // to update analysis if it is already available.
726     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
727     auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
728     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
729     return AggressiveDeadCodeElimination(F, DT, PDT)
730         .performDeadCodeElimination();
731   }
732 
733   void getAnalysisUsage(AnalysisUsage &AU) const override {
734     AU.addRequired<PostDominatorTreeWrapperPass>();
735     if (!RemoveControlFlowFlag)
736       AU.setPreservesCFG();
737     else {
738       AU.addPreserved<DominatorTreeWrapperPass>();
739       AU.addPreserved<PostDominatorTreeWrapperPass>();
740     }
741     AU.addPreserved<GlobalsAAWrapperPass>();
742   }
743 };
744 
745 } // end anonymous namespace
746 
747 char ADCELegacyPass::ID = 0;
748 
749 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
750                       "Aggressive Dead Code Elimination", false, false)
751 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
752 INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
753                     false, false)
754 
755 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }
756