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

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