contrib/llvm-project/llvm/lib/Transforms/Scalar/ADCE.cpp

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