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