Rewrite Aggressive Dead Code Elimination

[david2050]

Summary

We noticed that a source of performance difference between llvm and
gcc was in dead code elimination. This diff replaces ADCE with a new
implementation which will remove control flow and, under option, also
remove may-be-infinite loops which are dead. The patch current has
"ADCE_new.h" and "ADCE_new.cpp" to clarify that this is essentially a
full rewrite of the deleted "ADCE.h" and "ADCE.cpp", When ready to
land, I plan to change these names back to the originals.

The new algorithm uses the iterated dominance frontier to
incrementally identify control dependence sources for live operations
to determine when branch operations are live. It adds a new fix-up
phase to correct update phi-nodeswhen control flow changes.

Below are compile time and performance impacts based on Facebook
internal code sets.

Baseline ADCE compared to new ADCE compile time, -O3 removing loops
Comparing compile times for ~400 source files from folly code base

"baseline" is total time in seconds for all files
"net_difference" is increase due to changes
"percent" is increase expressed aa persent of baseline
"samples" is number of distinct tests, these vary in some cases
as runs with high variance in timing are excluded from summary

baseline net_difference percent samples .
28,591.41 165.91 0.58 413 .

Baseline ADCE compared with new ADCE, also removing loops

baseline net_difference percent samples .
28,591.02 215.35 0.75 411 .

Here are the impacts on runtimes for three different internal sets of
benchmarks, again compiled -O3

baseline, percent, samples as above

Without removing loops:

baseline                           total  samples  .
105,846,951,721,178.10  1.000    85      .
  28,317,122,801,690.20  0.998  2
         364,771,688,928.1  0.997    64      .

With removing loops: (adding -mllvm -adce-remove-loops)

baseline                           total  samples  .
105,845,678,704,074.98  1.000   78      .
  29,901,291,181,631.10  0.988  280      .
    332,140,718,056.76     0.982   61      .

[mehdi_amini]

(added llvm-commits as subscriber)

[david2050]

Modified to use IDFCalculator (itself modified to work on the reverse graph)

[david2050]

Update to new IDFCalculator

[david2050]

Update to recent ADCE changes

[david2050]

Cleanp in response to review comments

[zzheng]

Just some drive-by nitpicks on format: acdec.[h|cpp] files' banner and 80 columns. Please comply with coding standard.

include/llvm/Transforms/Scalar.h

96

Exceeds 80 columns.

include/llvm/Transforms/Scalar/ACDCE.h

2 ↗

(On Diff #55007)

//===- ACDCE.h - Aggressive CONTROL dead code elimination--------===//

lib/Transforms/Scalar/ACDCE.cpp

2 ↗

(On Diff #55007)

Please fix the banner.

[mehdi_amini]

Just in case you didn't know David, we have a tool called clang-format that automatically format your code for the LLVM coding standard. LLVM comes also with a git-clang-format script that if you put in your path enables a command git clang-format <range> that format only the lines that are touched by the diff.
(this is an optional tool, you don't *have to* use it, I'm just pointing it for your convenience)

[david2050]

Thanks.

[david2050]

Fix formatting errors

[david2050]

and the formatting one in ACDCE.h

[david2050]

Update two recently added test and fix a bug incorporating changes to
ADCE.cpp

[david2050]

Bug fix in handling of "hard" phi nodes

[majnemer]

lib/Transforms/IPO/PassManagerBuilder.cpp

302–303

Please format this appropriately.

lib/Transforms/Scalar/ACDCE.cpp

508–513 ↗

(On Diff #55715)

Why are EHPads always considered live?

609 ↗

(On Diff #55715)

Please use // comments.

617 ↗

(On Diff #55715)

Please start sentences with a capital letter.

617–623 ↗

(On Diff #55715)

It would be helpful if you gave a short example of this in IR (as a comment).

620–621 ↗

(On Diff #55715)

The formatting got weird here.

645–647 ↗

(On Diff #55715)

Some strange indentation made its way here.

731 ↗

(On Diff #55715)

Please obey the naming convention.

818 ↗

(On Diff #55715)

Please start each sentence with a capital letter and end it with a period.

849 ↗

(On Diff #55715)

Ditto.

877–878 ↗

(On Diff #55715)

I wouldn't bother with an IRBuilder for a single instruction, BranchInst::Create(Target, PredTerm) would do.

[david2050]

Thanks for the review

lib/Transforms/IPO/PassManagerBuilder.cpp

302–303

I assume this means removing the braces.

lib/Transforms/Scalar/ACDCE.cpp

508–513 ↗

(On Diff #55715)

I cribbed the condition from the existing ADCE pass. I assumed that it would be impossible to remove the corresponding invoke so simplest to just keep the operation live.

[david2050]

Address comments

[david2050]

• Merge branch 'master' into acdce-with-idf-for-review

[david2050]

From Chandler by email:

t would be good to at least send a fresh mail to the list with an updated rationale and such.

One thing that I'm having trouble even making out from the patch description in Phab is exactly what numbers you have collected. The formatting makes it really hard to understand what change this actually introduces.

As one high-level comment, why would we want this *and* ADCE to exist? I feel like we don't need 4 or 5 different dead code elimination passes and would benefit from this actually just being a patch to one of the existing ones.

Another high-level comment: if we must have both ADCE and this pass, I find the name "ACDCE" or "Aggressive Control Dead Code Elimination" very confusing. The order of the words seems all wrong. If we need to distinguish between eliminating dead control flows independent of eliminating dead instructions within basic blocks, I would name them "Aggressive Dead Control Flow Elimination" and "Aggressive Dead Code Elimination". And I would consider stripping the "Aggressive" prefix because I doubt that really makes sense these days.

Thanks Chandler

Changes in response shortly.

[david2050]

Replace the baseline ADCE with this implementation modified to
not build the post-dominator tree and in that case retain all
control flow. This preserves prior behavior for -O1 and -O2 and avoids
the extra cost needed to remove control flow.

[david2050]

Following Chandler's feedback, modified to simply replace the existing
ADCE rather than having two implementations. Reused baseline names.

Fixed some bugs in handling debug scopes/operations.

[chandlerc]

In D18762#471336, @david2050 wrote:

Following Chandler's feedback, modified to simply replace the existing
ADCE rather than having two implementations. Reused baseline names.

Fixed some bugs in handling debug scopes/operations.

Unfortunately, the way this patch is structured, it just shows you deleting the entire ADCE patch, and then adding a new one with no way to tell what the history is. This makes reviewing it really challenging.

I think the best way to go about this is to post small, incremental cleanups and refactorings to the existing ADCE pass until there is a clean design where you can submit a patch that adds control flow deletion (or whatever other logic you want) to the *existing* pass behind a flag.

Does that make sense?

[david2050]

I am sympathetic of course to the view of incremental changes but I don't really think it is effective in this case because so much functionality has to come online in one go. There is a kernel this is common (propagating liveness as a sparse backwards flow problem, lines 488-497) but that is quite small. The next logical step is to defer deleting branches until you know they control something live. This needs to be done in batches to use IDFCalculator efficiently and adds an outer loop. However, once you start having *any* dead control flow you need to deal with the complexities of phi nodes and the attendant problems with changing the control flow graph. There is not really any useful intermediate step,

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       // We must reference the passes in such a way that compilers will not
       // delete it all as dead code, even with whole program optimization,
       // yet is effectively a NO-OP. As the compiler isn't smart enough
       // to know that getenv() never returns -1, this will do the job.
       if (std::getenv("bar") != (char*) -1)
         return;
 
       (void) llvm::createAAEvalPass();
-      (void) llvm::createAggressiveDCEPass();
+      (void) llvm::createAggressiveDCEPass(/*RemoveControlFLow*/false);
       (void) llvm::createBitTrackingDCEPass();
       (void) llvm::createArgumentPromotionPass();
       (void) llvm::createAlignmentFromAssumptionsPass();
       (void) llvm::createBasicAAWrapperPass();
       (void) llvm::createSCEVAAWrapperPass();
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBoundsCheckingPass();

include/llvm/Transforms/Scalar.h

 // that (optimistically) combines multiple guards into one to have fewer checks
 // at runtime.
 //
 FunctionPass *createGuardWideningPass();
 
 
 //===----------------------------------------------------------------------===//
 //
+// AggressiveControlDCE - This pass uses the SSA based Aggressive DCE algorithm.
+// This algorithm assumes instructions are dead until proven otherwise, which
+// makes it more successful at removing non-obviously dead instructions. This
+// variant does not treat branches as automatically live
+//
+FunctionPass *createAggressiveDCEPass(bool RemoveControlFlow = false);
+
+//===----------------------------------------------------------------------===//
+//
 // BitTrackingDCE - This pass uses a bit-tracking DCE algorithm in order to
 // remove computations of dead bits.
 //
 FunctionPass *createBitTrackingDCEPass();
 
 //===----------------------------------------------------------------------===//
 //
 // SROA - Replace aggregates or pieces of aggregates with scalar SSA values.

include/llvm/Transforms/Scalar/ADCE_new.h

 //===- ADCE.h - Aggressive dead code elimination --------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file provides the interface for the Aggressive Dead Code Elimination
-// pass. This pass optimistically assumes that all instructions are dead until
-// proven otherwise, allowing it to eliminate dead computations that other DCE
-// passes do not catch, particularly involving loop computations.
+// This file provides the interface for the Aggressive Dead Code
+// Elimination pass. This pass optimistically assumes that all instructions are
+// dead until proven otherwise, allowing it to eliminate dead computations that
+// other DCE passes do not catch, particularly involving loop computations.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_ADCE_H
 #define LLVM_TRANSFORMS_SCALAR_ADCE_H
 
 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
-/// A DCE pass that assumes instructions are dead until proven otherwise.
+/// A DCE pass that assumes instructions including branches are dead until
+/// proven otherwise.
 ///
 /// This pass eliminates dead code by optimistically assuming that all
 /// instructions are dead until proven otherwise. This allows it to eliminate
 /// dead computations that other DCE passes do not catch, particularly involving
-/// loop computations.
+/// loop computations. This pass augments the predecessor "Aggressive DCE" by
+/// not treating all branch operations as automatically live and by altering the
+/// control flow graph remove dead branching.
 struct ADCEPass : PassInfoMixin<ADCEPass> {
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
 };
 }
 
 #endif // LLVM_TRANSFORMS_SCALAR_ADCE_H

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/InstrProfiling.h"
 #include "llvm/Transforms/PGOInstrumentation.h"
 #include "llvm/Transforms/SampleProfile.h"
-#include "llvm/Transforms/Scalar/ADCE.h"
+#include "llvm/Transforms/Scalar/ADCE_new.h"
 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
 #include "llvm/Transforms/Scalar/BDCE.h"
 #include "llvm/Transforms/Scalar/DCE.h"
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/GuardWidening.h"
 #include "llvm/Transforms/Scalar/IndVarSimplify.h"

lib/Transforms/IPO/PassManagerBuilder.cpp

if (BBVectorize) {
       if (!DisableUnrollLoops)
         MPM.add(createLoopUnrollPass());
     }
   }
 
   if (LoadCombine)
     MPM.add(createLoadCombinePass());
 
-  MPM.add(createAggressiveDCEPass());         // Delete dead instructions
+  MPM.add(createAggressiveDCEPass(OptLevel > CodeGenOpt::Default)); 
   MPM.add(createCFGSimplificationPass()); // Merge & remove BBs
   // Clean up after everything.
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
 }
 
 void PassManagerBuilder::populateModulePassManager(
     legacy::PassManagerBase &MPM) {
   // Allow forcing function attributes as a debugging and tuning aid.
   MPM.add(createForceFunctionAttrsLegacyPass());
 

lib/Transforms/Scalar/ADCE.cpp

-//===- ADCE.cpp - Code to perform dead code elimination -------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the Aggressive Dead Code Elimination pass.  This pass
-// optimistically assumes that all instructions are dead until proven otherwise,
-// allowing it to eliminate dead computations that other DCE passes do not
-// catch, particularly involving loop computations.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Transforms/Scalar/ADCE.h"
-#include "llvm/ADT/DepthFirstIterator.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/GlobalsModRef.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/CFG.h"
-#include "llvm/IR/DebugInfoMetadata.h"
-#include "llvm/IR/InstIterator.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/Pass.h"
-#include "llvm/ProfileData/InstrProf.h"
-#include "llvm/Transforms/Scalar.h"
-using namespace llvm;
-
-#define DEBUG_TYPE "adce"
-
-STATISTIC(NumRemoved, "Number of instructions removed");
-
-static void collectLiveScopes(const DILocalScope &LS,
-                              SmallPtrSetImpl<const Metadata *> &AliveScopes) {
-  if (!AliveScopes.insert(&LS).second)
-    return;
-
-  if (isa<DISubprogram>(LS))
-    return;
-
-  // Tail-recurse through the scope chain.
-  collectLiveScopes(cast<DILocalScope>(*LS.getScope()), AliveScopes);
-}
-
-static void collectLiveScopes(const DILocation &DL,
-                              SmallPtrSetImpl<const Metadata *> &AliveScopes) {
-  // Even though DILocations are not scopes, shove them into AliveScopes so we
-  // don't revisit them.
-  if (!AliveScopes.insert(&DL).second)
-    return;
-
-  // Collect live scopes from the scope chain.
-  collectLiveScopes(*DL.getScope(), AliveScopes);
-
-  // Tail-recurse through the inlined-at chain.
-  if (const DILocation *IA = DL.getInlinedAt())
-    collectLiveScopes(*IA, AliveScopes);
-}
-
-// Check if this instruction is a runtime call for value profiling and
-// if it's instrumenting a constant.
-static bool isInstrumentsConstant(Instruction &I) {
-  if (CallInst *CI = dyn_cast<CallInst>(&I))
-    if (Function *Callee = CI->getCalledFunction())
-      if (Callee->getName().equals(getInstrProfValueProfFuncName()))
-        if (isa<Constant>(CI->getArgOperand(0)))
-          return true;
-  return false;
-}
-
-static bool aggressiveDCE(Function& F) {
-  SmallPtrSet<Instruction*, 32> Alive;
-  SmallVector<Instruction*, 128> Worklist;
-
-  // Collect the set of "root" instructions that are known live.
-  for (Instruction &I : instructions(F)) {
-    if (isa<TerminatorInst>(I) || I.isEHPad() || I.mayHaveSideEffects()) {
-      // Skip any value profile instrumentation calls if they are
-      // instrumenting constants.
-      if (isInstrumentsConstant(I))
-        continue;
-      Alive.insert(&I);
-      Worklist.push_back(&I);
-    }
-  }
-
-  // Propagate liveness backwards to operands.  Keep track of live debug info
-  // scopes.
-  SmallPtrSet<const Metadata *, 32> AliveScopes;
-  while (!Worklist.empty()) {
-    Instruction *Curr = Worklist.pop_back_val();
-
-    // Collect the live debug info scopes attached to this instruction.
-    if (const DILocation *DL = Curr->getDebugLoc())
-      collectLiveScopes(*DL, AliveScopes);
-
-    for (Use &OI : Curr->operands()) {
-      if (Instruction *Inst = dyn_cast<Instruction>(OI))
-        if (Alive.insert(Inst).second)
-          Worklist.push_back(Inst);
-    }
-  }
-
-  // The inverse of the live set is the dead set.  These are those instructions
-  // which have no side effects and do not influence the control flow or return
-  // value of the function, and may therefore be deleted safely.
-  // NOTE: We reuse the Worklist vector here for memory efficiency.
-  for (Instruction &I : instructions(F)) {
-    // Check if the instruction is alive.
-    if (Alive.count(&I))
-      continue;
-
-    if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
-      // Check if the scope of this variable location is alive.
-      if (AliveScopes.count(DII->getDebugLoc()->getScope()))
-        continue;
-
-      // Fallthrough and drop the intrinsic.
-      DEBUG({
-        // If intrinsic is pointing at a live SSA value, there may be an
-        // earlier optimization bug: if we know the location of the variable,
-        // why isn't the scope of the location alive?
-        if (Value *V = DII->getVariableLocation())
-          if (Instruction *II = dyn_cast<Instruction>(V))
-            if (Alive.count(II))
-              dbgs() << "Dropping debug info for " << *DII << "\n";
-      });
-    }
-
-    // Prepare to delete.
-    Worklist.push_back(&I);
-    I.dropAllReferences();
-  }
-
-  for (Instruction *&I : Worklist) {
-    ++NumRemoved;
-    I->eraseFromParent();
-  }
-
-  return !Worklist.empty();
-}
-
-PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &) {
-  if (!aggressiveDCE(F))
-    return PreservedAnalyses::all();
-
-  // FIXME: ADCE should also 'preserve the CFG'.
-  // The new pass manager has currently no way to do it.
-  auto PA = PreservedAnalyses();
-  PA.preserve<GlobalsAA>();
-  return PA;
-}
-
-namespace {
-struct ADCELegacyPass : public FunctionPass {
-  static char ID; // Pass identification, replacement for typeid
-  ADCELegacyPass() : FunctionPass(ID) {
-    initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
-  }
-
-  bool runOnFunction(Function& F) override {
-    if (skipFunction(F))
-      return false;
-    return aggressiveDCE(F);
-  }
-
-  void getAnalysisUsage(AnalysisUsage& AU) const override {
-    AU.setPreservesCFG();
-    AU.addPreserved<GlobalsAAWrapperPass>();
-  }
-};
-}
-
-char ADCELegacyPass::ID = 0;
-INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
-                false, false)
-
-FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }

lib/Transforms/Scalar/ADCE_new.cpp

+//===- ADCE.cpp - Code to perform dead code elimination -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Aggressive Dead Code Elimination pass.  This pass
+// optimistically assumes that all instructions are dead until proven otherwise,
+// allowing it to eliminate dead computations that other DCE passes do not
+// catch by not assuming that control operations are live. Under option, it will
+// also remove may-be-infinite loops (legal in C++, not generally in Java)
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/ADCE_new.h"
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFGPrinter.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/IteratedDominanceFrontier.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/Pass.h"
+#include "llvm/ProfileData/InstrProf.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Transforms/Scalar.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "adce"
+
+static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow",
+                                           cl::init(false), cl::Hidden);
+static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false),
+                                 cl::Hidden);
+
+STATISTIC(NumRemoved, "Number of instructions removed");
+STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");
+
+namespace {
+
+// helper functions ...
+bool isUnconditional(TerminatorInst *Term) {
+  auto BR = dyn_cast<BranchInst>(Term);
+  return BR && BR->isUnconditional();
+}
+
+// simplified erase pattern
+template <typename V, typename Pred>
+void erase(V *Vec, Pred P) {
+  Vec->erase(std::remove_if(Vec->begin(), Vec->end(), P), Vec->end());
+}
+// a composite transform and copy-if which test for non-null
+template <class InputIterator, class OutputIterator, class UnaryOperator>
+OutputIterator copy_non_null(InputIterator First1, InputIterator Last1,
+                             OutputIterator Result, UnaryOperator Op) {
+  while (First1 != Last1) {
+    auto Value = Op(*First1);
+    if (Value) {
+      *Result = Value;
+      ++Result;
+    }
+    ++First1;
+  }
+  return Result;
+}
+}
+
+namespace llvm {
+
+// Specialize po_iterator_storage to identify loop bottoms
+// which we define simply as back edges in a depth first
+// traversal of the CFG starting at the entry.
+class PO_WithLoops;
+
+template <> class po_iterator_storage<PO_WithLoops, true> {
+  PO_WithLoops &Storage;
+
+public:
+  po_iterator_storage(PO_WithLoops &Storage) : Storage(Storage) {}
+  // These functions are defined below.
+  bool insertEdge(BasicBlock *From, BasicBlock *To);
+  void finishPostorder(BasicBlock *BB);
+};
+
+class PO_WithLoops {
+  typedef SmallPtrSet<BasicBlock *, 32> LoopBottomsType;
+  typedef po_iterator<BasicBlock *, PO_WithLoops, true> POTIterator;
+
+  Function &F;
+  // Visited[BB] is true while the basic block *BB is on
+  // the stack of being visited nodes and false after
+  // all children have been visited
+  DenseMap<BasicBlock *, bool> Visited;
+  LoopBottomsType LoopBottoms;
+
+public:
+  PO_WithLoops(Function &F) : F(F) { Visited.grow(2 * F.size()); }
+  POTIterator begin() { return po_ext_begin(&F.getEntryBlock(), *this); }
+  POTIterator end() { return po_ext_end(&F.getEntryBlock(), *this); }
+  bool insertEdge(BasicBlock *From, BasicBlock *To) {
+    auto P = Visited.insert(std::make_pair(To, true));
+    if (P.second) {
+      return true;
+    }
+    if (P.first->second) {
+      // back edge to an ancestor in DFS
+      LoopBottoms.insert(From);
+    }
+    return false;
+  }
+
+  void finishPostorder(BasicBlock *BB) { Visited[BB] = false; }
+  bool reachable(BasicBlock *BB) const {
+    return (Visited.find(BB) != Visited.end());
+  }
+  const LoopBottomsType &getLoopBottoms() { return LoopBottoms; }
+};
+
+bool po_iterator_storage<PO_WithLoops, true>::insertEdge(BasicBlock *From,
+                                                         BasicBlock *To) {
+  return Storage.insertEdge(From, To);
+}
+void po_iterator_storage<PO_WithLoops, true>::finishPostorder(BasicBlock *BB) {
+  Storage.finishPostorder(BB);
+}
+}
+
+namespace {
+
+struct BlockInfoType;
+/// A Dead Region is a set of dead basic blocks with a common
+/// post-dominating live block
+struct DeadRegionInfo {
+  /// true when all blocks have unconditional branches
+  bool Trivial = true; // dead blocks are just unconditional branches
+  /// the set of dead blocks in this region
+  SmallVector<BlockInfoType *, 16> DeadBlocks;
+  /// sources of edges from live nodes into dead ones of this region
+  SmallPtrSet<BlockInfoType *, 16> LivePreds;
+};
+
+/// Information about Instruction's
+struct InstInfoType {
+
+  bool Live = false; ///< true if this unstruction is live
+
+  /// quick access to information for block containing associated Instruction
+  struct BlockInfoType *Block = nullptr;
+};
+
+/// Information about basic blocks relevant to dead code elimination
+struct BlockInfoType {
+  /// true when this block contains a live instructions
+  bool Live = false;
+  /// this block ends in an unconditional branch
+  bool UnconditionalBranch = false;
+
+  /// quick access to the LiveInfo for the terminator
+  InstInfoType *TerminatorLiveInfo = nullptr; // == & InstInfo[Terminator]
+
+  bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }
+
+  /// corresponding BasicBlock
+  BasicBlock *BB = nullptr;
+
+  /// points to this BB when this block is live, otherwise the most immediate
+  /// live post-dominator of BB
+  BasicBlock *LivePostDom = nullptr;
+
+  TerminatorInst *Terminator = nullptr; ///< cache of BB->getTerminator()
+
+  /// block found to not reach a function return point
+  bool isUnreachable() const { return Terminator == nullptr; }
+
+  /// the collection of dead blocks which have this block as
+  /// the most-immediate live post-dominator
+  DeadRegionInfo DeadRegion;
+
+  /// used to control exploration of dead connected components
+  unsigned RegionVisited = 0;
+};
+
+/// This class implements analysis to determine instructions including branching
+/// which does not effect the output. Such operations are removed as are
+/// unreachable operations for some scenarions. Dead loops are optionally
+/// removed
+/// or retained.
+class AggressiveDCE {
+  Function &F;
+  bool RemoveControlFlow;
+
+  /// reverse partial order of blocks with a collection of sources of backward
+  /// edges referred to as loop bottoms
+  PO_WithLoops PO;
+  PostDominatorTree &PDT;
+  bool GraphWasModified = false;
+
+  /// function-level statistics
+  unsigned FuncNumBranchesRemoved = 0;
+  unsigned FuncNumInstRemoved = 0;
+
+  /// one per basic block in the function
+  std::vector<BlockInfoType> BlockInfoVec;
+
+  /// mapping of blocks to associated information, element in BlockInfoVec
+  DenseMap<BasicBlock *, BlockInfoType *> BlockInfo;
+  bool isLive(BasicBlock *BB) { return BlockInfo[BB]->Live; }
+
+  /// mapping of instructions to associated information
+  DenseMap<Instruction *, InstInfoType> InstInfo;
+  bool isLive(Instruction *I) { return InstInfo[I].Live; }
+
+  /// initialize maps and BlockInfoVec
+  void initialize();
+
+  /// live instructions to be processed or dead instructions to be deleted
+  SmallVector<Instruction *, 128> Worklist;
+  SmallPtrSet<const Metadata *, 32> AliveScopes;
+
+  /// Propagate "live-ness" to definitions which reach "live" instructions
+  void markLive();
+  /// Mark I and its containing block as live.
+  void markLive(Instruction *I);
+  void collectLiveScopes(Instruction *I) {
+    if (const DILocation *DL = I->getDebugLoc())
+      collectLiveScopes(*DL);
+  }
+  void collectLiveScopes(const DILocalScope &LS);
+  void collectLiveScopes(const DILocation &DL);
+
+  /// true for any instructions which is always treated as live
+  bool alwaysLive(Instruction &I) const;
+
+  /// vector of blocks with not known to be live terminators,
+  SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators;
+
+  /// The set of blocks which we have determined are live in the
+  /// most recent pass
+  SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;
+
+  /// Analyze basic blocks to find to loop bottoms to keep live and
+  /// remove unreachable blocks
+  void analyzeBlocks();
+
+  /// blocks found to be unreachable when searching for back edges
+  SmallVector<BasicBlock *, 16> UnreachableBlocks;
+  void removeUnreachable(BasicBlock *);
+
+  /// Analyze dead branches to find those whose branches are the sources
+  /// of control dependences impacting a live block. Those branches are
+  /// marked live.
+  void checkControlDependences();
+
+  /// look for phi nodes with complex value which force
+  /// source blocks of reaching values to be treated as live.
+  void checkPhiNodes();
+
+  typedef SmallPtrSet<BasicBlock *, 8> RegionSetType;
+
+  /// Traverse the connected component associated with BBInfo where
+  /// nodes whose RegionVisited field is greater than FirstVisit are considered
+  /// already 'visited' and we stop at tops of live blocks.
+  /// Set RegionVisited for blocks newly visited to CurrentVisit.
+  /// Record live blocks that are successors of DeadBlocks on this
+  /// componente in LivePdoms
+  void visitRegion(BlockInfoType *, unsigned FirstVisit, unsigned CurrentVisit,
+                   RegionSetType *LivePdoms);
+
+  /// Incremented for each new traversal of connected components
+  unsigned LastCurrentVisit = 0;
+
+  /// Verify that all edges from "dead" predecessors into PN
+  /// have the same associated value. To refine the precision, the
+  /// dead blocks are partitioned into connnected components and
+  /// all definitions associated with predecessor blocks in the same
+  /// connected component must be the same
+  void checkPhiNode(PHINode *PN, unsigned FirstVisit);
+
+  /// find groups of dead blocks with common live post-dominator
+  /// and rewrite the control flow graph
+  void processDeadRegions();
+
+  /// Rewrite non-trivial dead regions by redirection incoming live
+  /// control flow to the post-dominator and updating phi-nnodes in the
+  /// post-dominator
+  void updateDeadRegion(BasicBlock *BB, DeadRegionInfo *Info);
+
+  /// adjust BB so it has an unconditional branch to Target
+  /// mark that branch live.
+  void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
+
+  /// the collection of unconditional branch instructions created
+  /// by makeUnconditional
+  SmallVector<Instruction *, 32> NewBranches;
+
+  /// for trivial regions, we just mark all the branches as live to be
+  /// cleaned up by other phases
+  void cleanTrivialRegion(const DeadRegionInfo &Info);
+
+  void removeDeadCode();
+
+#ifndef NDEBUG
+  /// the set of live blocks with dead predecessors
+  SmallPtrSet<BasicBlock *, 31> BlocksForPhiValidation;
+
+  /// verify one value for each predecessor after dead blocks are removed
+  void validatePhiNodes(BasicBlock *);
+#endif
+
+public:
+  AggressiveDCE(Function &F, PostDominatorTree &PDT, bool RemoveControlFlow)
+      : F(F), RemoveControlFlow(RemoveControlFlow || RemoveControlFlowFlag ||
+                                RemoveLoops),
+        PO(F), PDT(PDT) {}
+  bool doAggressiveCDCE();
+};
+}
+
+bool AggressiveDCE::doAggressiveCDCE() {
+
+  initialize();
+  markLive();
+  processDeadRegions();
+  removeDeadCode();
+
+  return GraphWasModified;
+}
+
+//===----------------------------------------------------------------------===//
+//
+//
+// Initialize of data structures and identification of
+// loops and unreachable code
+//
+//===----------------------------------------------------------------------===//
+void AggressiveDCE::initialize() {
+
+  DEBUG(PDT.print(dbgs()));
+  
+  auto NumBlocks = F.size();
+  BlockInfoVec.resize(NumBlocks);
+  BlockInfo.grow(2 * NumBlocks);
+  auto InfoP = BlockInfoVec.begin();
+  size_t NumInsts = 0;
+  for (auto &BB : F) {
+    NumInsts += BB.size();
+    auto &Info = *InfoP;
+    BlockInfo[&BB] = &Info;
+    DEBUG(dbgs() << "initializing block " << BB.getName() << '\n');
+    Info.BB = &BB;
+    Info.Terminator = BB.getTerminator();
+    Info.UnconditionalBranch = isUnconditional(Info.Terminator);
+    ++InfoP;
+  }
+  if (!RemoveLoops) {
+    // remove unreachable code, identify loop bottoms
+    // to be forced live below.
+    analyzeBlocks();
+  }
+  InstInfo.grow(2 * NumInsts);
+  for (auto &BBInfo : BlockInfoVec) {
+    if (BBInfo.isUnreachable()) { // removed unreachable node
+      continue;
+    }
+    for (Instruction &I : *BBInfo.BB) {
+      auto &IInfo = InstInfo[&I];
+      IInfo.Block = &BBInfo;
+      if (alwaysLive(I)) {
+        markLive(&I);
+      }
+    }
+  }
+
+  // For blocks which do not reach a function return, mark
+  // them live. Also branches where some reach the return
+  // and some done as live.
+  for (auto &BBInfo : BlockInfoVec) {
+    if (!BBInfo.isUnreachable() && !PDT.getNode(BBInfo.BB)) {
+      markLive(BBInfo.Terminator);
+      for (auto Pred : predecessors(BBInfo.BB)) {
+        DEBUG(dbgs() << "no pdom pred live: " << Pred->getName() << '\n');
+        markLive(Pred->getTerminator());
+      }
+    }
+  }
+
+  // mark all loop bottom terminators as live so loops are not
+  // deleted (in case they are infinite)
+  for (auto BB : PO.getLoopBottoms()) {
+    DEBUG(dbgs() << "loop bottom " << BB->getName() << '\n');
+    markLive(BB->getTerminator());
+  }
+
+  for (auto &BBInfo : BlockInfoVec) {
+    BBInfo.TerminatorLiveInfo = &InstInfo[BBInfo.Terminator];
+    if (!BBInfo.TerminatorLiveInfo->Live) {
+      BlocksWithDeadTerminators.insert(BBInfo.BB);
+    }
+  }
+
+  // Treat the entry block as always live
+  auto BB = &F.getEntryBlock();
+  auto &EntryInfo = *BlockInfo[BB];
+  EntryInfo.Live = true;
+  EntryInfo.LivePostDom = BB;
+  if (EntryInfo.UnconditionalBranch) {
+    EntryInfo.TerminatorLiveInfo->Live = true;
+    BlocksWithDeadTerminators.erase(BB);
+    collectLiveScopes(EntryInfo.Terminator);
+  }
+}
+
+// Find and remove unreachable code and compute the bottoms of loops
+// which will be forced live so loops are retained.
+void AggressiveDCE::analyzeBlocks() {
+
+  // This loop drives a Post Order traversal of the
+  // control flow graph which will determine the set
+  // of blocks reachable from the entry and also mark
+  // those which are the sources of back edges (loop bottoms)
+  for (auto BB : PO) {
+    (void)BB;
+  }
+
+  for (auto &BB : F) {
+    if (PO.reachable(&BB)) {
+      continue;
+    }
+    DEBUG(dbgs() << "unreachable " << BB.getName() << '\n');
+    removeUnreachable(&BB);
+    UnreachableBlocks.push_back(&BB);
+  }
+  if (Worklist.empty()) {
+    return;
+  }
+  GraphWasModified = true;
+  for (auto I : Worklist) {
+    I->eraseFromParent();
+  }
+  Worklist.clear();
+}
+
+// since we go to the trouble of finding unreachable blocks
+// might as well remove them.
+void AggressiveDCE::removeUnreachable(BasicBlock *BB) {
+  auto &Info = *BlockInfo[BB];
+  Info.Live = true;
+  Info.Terminator = nullptr;
+
+  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
+    PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
+    BB->getInstList().pop_front();
+  }
+  for (auto Succ : successors(BB)) {
+    Succ->removePredecessor(BB);
+  }
+  BB->dropAllReferences();
+  for (Instruction &I : *BB) {
+    Worklist.push_back(&I);
+  }
+}
+
+//===----------------------------------------------------------------------===//
+//
+// Core algorithm to propagate liveness
+//
+//===----------------------------------------------------------------------===//
+void AggressiveDCE::markLive() {
+
+  DEBUG(dbgs() << "propagate live\n" << '\n');
+
+  // Propagate liveness backwards to operands.
+  do {
+    while (!Worklist.empty()) {
+      Instruction *Curr = Worklist.pop_back_val();
+      DEBUG(dbgs() << "work live: "; Curr->dump(););
+      for (Use &OI : Curr->operands()) {
+        if (Instruction *Inst = dyn_cast<Instruction>(OI)) {
+          markLive(Inst);
+        }
+      }
+    }
+    checkControlDependences();
+    if (Worklist.empty()) {
+      checkPhiNodes();
+    }
+  } while (!Worklist.empty());
+
+  // Find blocks with dead terminators which are simply
+  // unconditional branches and mark them live to avoid
+  // trivial edits
+  SmallVector<BasicBlock *, 32> NowLiveBlocks;
+  for (auto BB : BlocksWithDeadTerminators) {
+    auto Info = BlockInfo[BB];
+    if (!Info->Live && Info->UnconditionalBranch &&
+        &Info->BB->front() == Info->Terminator) {
+      if (auto Pred = Info->BB->getSinglePredecessor()) {
+        if (isLive(Pred->getTerminator())) {
+          // this mostly avoids unnecessary work removing trival dead regions
+          DEBUG(dbgs() << "unconditional from live pred " << Info->BB->getName()
+                       << '\n');
+          Info->Live = true;
+          Info->TerminatorLiveInfo->Live = true;
+          collectLiveScopes(Info->Terminator);
+          Info->LivePostDom = BB;
+          NowLiveBlocks.push_back(BB);
+        }
+      }
+    }
+  }
+  for (auto BB : NowLiveBlocks) {
+    BlocksWithDeadTerminators.erase(BB);
+  }
+}
+
+// Check if this instruction is a runtime call for value profiling and
+// if it's instrumenting a constant.
+static bool isInstrumentsConstant(Instruction &I) {
+  if (CallInst *CI = dyn_cast<CallInst>(&I))
+    if (Function *Callee = CI->getCalledFunction())
+      if (Callee->getName().equals(getInstrProfValueProfFuncName()))
+        if (isa<Constant>(CI->getArgOperand(0)))
+          return true;
+  return false;
+}
+
+bool AggressiveDCE::alwaysLive(Instruction &I) const {
+  if (I.isEHPad() || I.mayHaveSideEffects()) {
+    if (isInstrumentsConstant(I))
+      return false;
+    return true;
+  }
+  if (!isa<TerminatorInst>(I)) {
+    return false;
+  }
+  if (RemoveControlFlow && (isa<BranchInst>(I) || isa<SwitchInst>(I))) {
+    return false;
+  }
+  return true;
+}
+
+void AggressiveDCE::markLive(Instruction *I) {
+  auto &Info = InstInfo[I];
+  if (Info.Live) {
+    return;
+  }
+  DEBUG(dbgs() << "mark live: "; I->dump());
+  Info.Live = true;
+  Worklist.push_back(I);
+
+  // Collect the live debug info scopes attached to this instruction.
+  collectLiveScopes(I);
+
+  auto &BBInfo = *Info.Block;
+  if (BBInfo.Live) {
+    return;
+  }
+  DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
+  BBInfo.Live = true;
+  NewLiveBlocks.insert(BBInfo.BB);
+
+  BBInfo.LivePostDom = BBInfo.BB;
+  if (!BBInfo.UnconditionalBranch) {
+    return;
+  }
+  BlocksWithDeadTerminators.erase(BBInfo.BB);
+
+  if (!BBInfo.TerminatorLiveInfo) { // not set in first initialization pass
+    InstInfo[BBInfo.Terminator].Live = true;
+  } else {
+    BBInfo.TerminatorLiveInfo->Live = true;
+  }
+
+  // Collect the live debug info scopes attached to this instruction.
+  collectLiveScopes(BBInfo.Terminator);
+}
+
+void AggressiveDCE::collectLiveScopes(const DILocalScope &LS) {
+  if (!AliveScopes.insert(&LS).second)
+    return;
+
+  if (isa<DISubprogram>(LS))
+    return;
+
+  // Tail-recurse through the scope chain.
+  collectLiveScopes(cast<DILocalScope>(*LS.getScope()));
+}
+
+void AggressiveDCE::collectLiveScopes(const DILocation &DL) {
+  // Even though DILocations are not scopes, shove them into AliveScopes so we
+  // don't revisit them.
+  if (!AliveScopes.insert(&DL).second)
+    return;
+
+  // Collect live scopes from the scope chain.
+  collectLiveScopes(*DL.getScope());
+
+  // Tail-recurse through the inlined-at chain.
+  if (const DILocation *IA = DL.getInlinedAt())
+    collectLiveScopes(*IA);
+}
+
+// Use the IDFCalculator to find control dependences
+// strting at newly discovered live blocks but stopping
+// at blocks with live terminators.
+void AggressiveDCE::checkControlDependences() {
+
+  if (BlocksWithDeadTerminators.empty()) {
+    return;
+  }
+
+  DEBUG({
+    dbgs() << "new live blocks:\n";
+    for (auto BB : NewLiveBlocks) {
+      dbgs() << "\t" << BB->getName() << '\n';
+    }
+    dbgs() << "dead terminator blocks:\n";
+    for (auto BB : BlocksWithDeadTerminators) {
+      dbgs() << "\t" << BB->getName() << '\n';
+    }
+  });
+
+  SmallVector<BasicBlock *, 32> IDFBlocks;
+  ReverseIDFCalculator IDFs(PDT);
+  IDFs.setDefiningBlocks(NewLiveBlocks);
+  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
+  IDFs.calculate(IDFBlocks);
+  NewLiveBlocks.clear();
+
+  /* dead terminators which control live blocks become live */
+  for (auto BB : IDFBlocks) {
+    DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
+    markLive(BB->getTerminator());
+    BlocksWithDeadTerminators.erase(BB);
+  }
+}
+
+// there are scenarios in which a phi node is really short-hand
+// for a copy operations on the edge and the semantics of the program
+// rely on this. We look for situations where there are distinct values from
+// blocks with dead terminators (which we assume
+// are all replaced with
+// a single edge) and if we find this case we mark some of those terminators
+// as live.
+void AggressiveDCE::checkPhiNodes() {
+  RegionSetType LivePdoms;
+  auto FirstVisit = LastCurrentVisit;
+  for (auto DB : BlocksWithDeadTerminators) {
+    auto DBInfo = BlockInfo[DB];
+    if (DBInfo->RegionVisited > FirstVisit || DBInfo->terminatorIsLive()) {
+      continue;
+    }
+    ++LastCurrentVisit;
+    visitRegion(DBInfo, FirstVisit, LastCurrentVisit, &LivePdoms);
+  }
+  for (auto Succ : LivePdoms) {
+    DEBUG(dbgs() << "checking Phi Nodes " << Succ->getName() << '\n');
+    for (auto it = Succ->begin(); PHINode *PN = dyn_cast<PHINode>(it); ++it) {
+      if (isLive(PN)) {
+        checkPhiNode(PN, FirstVisit);
+      }
+    }
+  }
+}
+
+// Traverse the connected component associated with BBInfo where
+//    nodes whose RegionVisited field is > FirstVisit are considered 'visited'
+//    and we stop at tops of live blocks.
+void AggressiveDCE::visitRegion(BlockInfoType *BBInfo, unsigned FirstVisit,
+                                unsigned CurrentVisit,
+                                RegionSetType *LivePdoms) {
+  BBInfo->RegionVisited = CurrentVisit;
+  DEBUG(dbgs() << "region visited " << CurrentVisit << " "
+               << BBInfo->BB->getName() << '\n');
+  if (!BBInfo->Live) {
+    for (auto Pred : predecessors(BBInfo->BB)) {
+      auto PredInfo = BlockInfo[Pred];
+      if (PredInfo->RegionVisited <= FirstVisit) {
+        visitRegion(PredInfo, FirstVisit, CurrentVisit, LivePdoms);
+      }
+    }
+  }
+  for (auto Succ : successors(BBInfo->BB)) {
+    auto SuccInfo = BlockInfo[Succ];
+    if (SuccInfo->Live) {
+      LivePdoms->insert(SuccInfo->BB);
+      continue;
+    }
+    if (SuccInfo->RegionVisited <= FirstVisit) {
+      visitRegion(SuccInfo, FirstVisit, CurrentVisit, LivePdoms);
+    }
+  }
+}
+
+// This code verifies that all edges from "dead" predecessors
+// have the same associated value. This might not be true
+// after certain optimizations of eliminated intermediate PHI
+// nodes
+void AggressiveDCE::checkPhiNode(PHINode *PN, unsigned FirstVisit) {
+  DenseMap<unsigned, Value *> DeadValues;
+
+  auto NumIdx = PN->getNumIncomingValues();
+  // A block P may be a direct predecessor of a block Q and have a live
+  // terminator. It may also have a path from dead blocks leading to When that
+  // path is removed, there will only be one edge from P to Q and so we can
+  // only have one value in that case.
+  for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+    auto PredBB = PN->getIncomingBlock(Idx);
+    auto &Info = *BlockInfo[PredBB];
+    if (Info.RegionVisited > FirstVisit && Info.Live &&
+        Info.terminatorIsLive()) {
+      DeadValues[Info.RegionVisited] = PN->getIncomingValue(Idx);
+      DEBUG(dbgs() << "live for region " << Info.RegionVisited << " from "
+                   << PredBB->getName() << '\n');
+    }
+  }
+  for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+    auto PredBB = PN->getIncomingBlock(Idx);
+    auto PredInfo = BlockInfo[PredBB];
+    if (PredInfo->terminatorIsLive()) {
+      continue;
+    }
+    DEBUG(dbgs() << "check pred " << PredInfo->RegionVisited << " "
+                 << PredBB->getName() << '\n');
+    auto Value = PN->getIncomingValue(Idx);
+    auto &DeadValue = DeadValues[PredInfo->RegionVisited];
+    if (DeadValue) {
+      if (Value != DeadValue) {
+        DEBUG(dbgs() << "hard phi, region = " << PredInfo->RegionVisited
+                     << " pred " << PredBB->getName() << '\n';
+              PN->dump());
+        markLive(PredInfo->Terminator);
+      }
+    } else {
+      DeadValue = Value;
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+//
+//  Routines to update the CFG and SSA information before removing dead code
+//
+//===----------------------------------------------------------------------===//
+// A dead region is the set of dead blocks with a common live post-dominator
+// A trivial region is a region which consists of blocks with unconditional
+// branches. We don't bother removing such blocks and defer to other phases
+void AggressiveDCE::processDeadRegions() {
+
+  // Set LivePostDom fields for blocks which dead terminators
+  SmallVector<DomTreeNodeBase<BasicBlock> *, 16> deadPdoms;
+  for (auto &Info : BlockInfoVec) {
+    if (Info.isUnreachable()) {
+      continue;
+    }
+    if (Info.LivePostDom == nullptr) {
+      assert(!Info.Live);
+      auto Node = PDT.getNode(Info.BB)->getIDom();
+      while (!isLive(Node->getBlock())) {
+        deadPdoms.push_back(Node);
+        Node = Node->getIDom();
+      }
+      Info.LivePostDom = Node->getBlock();
+      for (auto DeadNode : deadPdoms) {
+        BlockInfo[DeadNode->getBlock()]->LivePostDom = Info.LivePostDom;
+      }
+      deadPdoms.clear();
+    }
+    if (Info.LivePostDom != Info.BB) {
+      DEBUG(dbgs() << "live pdom " << Info.BB->getName() << " "
+                   << Info.LivePostDom->getName() << '\n');
+    }
+  }
+  SmallPtrSet<BlockInfoType *, 32> DeadRegions;
+
+  // Examine dead blocks and collect them at their
+  // live post-dominator to be processed as a region.
+  for (auto DB : BlocksWithDeadTerminators) {
+    auto Info = BlockInfo[DB];
+    assert(!Info->terminatorIsLive());
+    if (Info->Live) {
+      // Look for live blocks with dead branches which
+      // will need to be converted to unconditional branches
+      for (auto Succ : successors(Info->BB)) {
+        auto &SuccInfo = *BlockInfo[Succ];
+        if (!SuccInfo.Live) {
+          continue;
+        }
+        DEBUG(dbgs() << "dead br in pred " << Info->BB->getName() << " reaches "
+                     << Succ->getName() << '\n');
+        SuccInfo.DeadRegion.LivePreds.insert(Info);
+        SuccInfo.DeadRegion.Trivial = false;
+        DeadRegions.insert(&SuccInfo);
+      }
+      continue;
+    }
+    auto LivePdom = Info->LivePostDom;
+    DEBUG(dbgs() << "Dead block: " << Info->BB->getName() << " pdom "
+                 << LivePdom->getName() << '\n');
+    auto &LivePdomInfo = *BlockInfo[LivePdom];
+    DeadRegions.insert(&LivePdomInfo);
+    auto &DeadRegion = LivePdomInfo.DeadRegion;
+    for (auto PredBB : predecessors(Info->BB)) {
+      auto &PredInfo = *BlockInfo[PredBB];
+      if (PredInfo.Live) {
+        DeadRegion.LivePreds.insert(&PredInfo);
+        if (!PredInfo.terminatorIsLive()) {
+          DeadRegion.Trivial = false;
+        }
+      }
+    }
+    if (!Info->UnconditionalBranch) {
+      DeadRegion.Trivial = false;
+    } else if (DeadRegion.Trivial) {
+      DeadRegion.DeadBlocks.push_back(Info);
+    }
+  }
+
+  for (auto Info : DeadRegions) {
+    if (!Info->DeadRegion.Trivial) {
+      updateDeadRegion(Info->BB, &Info->DeadRegion);
+    } else {
+      cleanTrivialRegion(Info->DeadRegion);
+    }
+  }
+}
+
+void AggressiveDCE::updateDeadRegion(BasicBlock *BB, DeadRegionInfo *Info) {
+
+  DEBUG({
+    dbgs() << "live edges (unique predecessors) into " << BB->getName() << "\n";
+    for (auto PredInfo : Info->LivePreds) {
+      dbgs() << "\t" << PredInfo->BB->getName() << '\n';
+    }
+  });
+
+  // update each phi based on the new incoming edges
+  for (auto it = BB->begin(); PHINode *PN = dyn_cast<PHINode>(it); ++it) {
+    if (!isLive(PN)) {
+      continue;
+    }
+    DEBUG(dbgs() << "old phi: "; PN->dump());
+    // Note that we have verified in checkPhiNodes that all are
+    // the same from dead predecessors.
+    DenseMap<unsigned, Value *> DeadValues;
+
+    for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
+      auto PredBB = PN->getIncomingBlock(i);
+      auto PredInfo = BlockInfo[PredBB];
+      if (PredInfo->terminatorIsLive()) {
+        continue;
+      }
+      DEBUG(dbgs() << "   removing " << PredInfo->RegionVisited << " "
+                   << PredBB->getName() << '\n');
+      auto &DeadValue = DeadValues[PredInfo->RegionVisited];
+      assert(!DeadValue || DeadValue == PN->getIncomingValue(i));
+      DeadValue = PN->getIncomingValue(i);
+      PN->removeIncomingValue(i, /*DeletePHIIfEmpty*/ false);
+    }
+    for (auto PredInfo : Info->LivePreds) {
+      auto DeadValue = DeadValues[PredInfo->RegionVisited];
+      assert(DeadValue && "Failed to find value for dead predecessor");
+      PN->addIncoming(DeadValue, PredInfo->BB);
+    }
+    DEBUG(dbgs() << "new phi: "; PN->dump());
+  }
+
+  // update edges
+  for (auto PredInfo : Info->LivePreds) {
+    if (!PredInfo->terminatorIsLive()) {
+      makeUnconditional(PredInfo->BB, BB);
+    } else {
+      auto PredTerm = PredInfo->Terminator;
+      auto NumSucc = PredTerm->getNumSuccessors();
+      for (unsigned Idx = 0; Idx != NumSucc; ++Idx) {
+        auto Succ = PredTerm->getSuccessor(Idx);
+        auto SuccInfo = BlockInfo[Succ];
+        if (SuccInfo->LivePostDom == BB) {
+          PredTerm->setSuccessor(Idx, BB);
+        }
+      }
+    }
+  }
+#ifndef NDEBUG
+  BlocksForPhiValidation.insert(BB);
+#endif
+}
+void AggressiveDCE::makeUnconditional(BasicBlock *BB, BasicBlock *Target) {
+  auto PredTerm = BB->getTerminator();
+  collectLiveScopes(PredTerm);
+  if (isUnconditional(PredTerm)) {
+    InstInfo[PredTerm].Live = true;
+    return;
+  }
+  DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
+  IRBuilder<> Builder(PredTerm);
+  auto NewTerm = Builder.CreateBr(Target);
+  // don't update InstInfo to protect pointers into it...
+  NewBranches.push_back(NewTerm);
+}
+
+// mark trivial blocks live and their unconditional-branch terminators as well.
+void AggressiveDCE::cleanTrivialRegion(const DeadRegionInfo &DRInfo) {
+  for (auto DBInfo : DRInfo.DeadBlocks) {
+    DEBUG(dbgs() << "Trivial: " << DBInfo->BB->getName() << '\n');
+    DBInfo->Live = true;
+    DBInfo->TerminatorLiveInfo->Live = true;
+    collectLiveScopes(DBInfo->Terminator);
+  }
+}
+
+// the actual work of removing dead instructions and blocks
+void AggressiveDCE::removeDeadCode() {
+
+  assert(Worklist.empty() &&
+         "Expected empty work list when removing dead code");
+  
+  // The inverse of the live set is the dead set.  These are those instructions
+  // which have no side effects and do not influence the control flow or return
+  // value of the function, and may therefore be deleted safely.
+  // NOTE: We reuse the Worklist vector here for memory efficiency.
+  unsigned LocalNumBranchesRemoved = std::count_if(
+      BlocksWithDeadTerminators.begin(), BlocksWithDeadTerminators.end(),
+      [this](BasicBlock *DB) { return !isLive(DB->getTerminator()); });
+
+  // this update invalidates BlockInfoType::TerminatorLive fields
+  for (Instruction *I : NewBranches) {
+    InstInfo[I].Live = true;
+  }
+  for (Instruction &I : instructions(F)) {
+    if (!isLive(&I)) {
+      if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
+        // Check if the scope of this variable location is alive.
+        auto Scope = DII->getDebugLoc()->getScope();
+        if (AliveScopes.count(Scope))
+          continue;
+
+        // Fallthrough and drop the intrinsic.
+        DEBUG({
+          // If intrinsic is pointing at a live SSA value, there may be an
+          // earlier optimization bug: if we know the location of the variable,
+          // why isn't the scope of the location alive?
+          if (Value *V = DII->getVariableLocation())
+            if (Instruction *II = dyn_cast<Instruction>(V))
+              if (isLive(II))
+                dbgs() << "Dropping debug info for " << *DII << "\n";
+        });
+      }
+
+      DEBUG(dbgs() << "dead: "; I.dump());
+      Worklist.push_back(&I);
+      I.dropAllReferences();
+    }
+  }
+  for (auto UB : UnreachableBlocks) {
+    DEBUG(dbgs() << "removing unreachble " << UB->getName() << '\n');
+    UB->eraseFromParent();
+  }
+  if (Worklist.empty()) {
+    return;
+  }
+  GraphWasModified = true;
+  for (Instruction *I : Worklist) {
+    I->eraseFromParent();
+  }
+  for (auto BB : BlocksWithDeadTerminators) {
+    auto DB = BlockInfo[BB];
+    if (!DB->Live) {
+      DEBUG(dbgs() << "deleting block " << DB->BB->getName() << '\n');
+      DB->BB->eraseFromParent();
+    }
+  }
+  auto LocalNumRemoved = Worklist.size();
+  DEBUG(dbgs() << "Num removed " << LocalNumRemoved << "\n"
+               << "Num branches removed " << LocalNumBranchesRemoved << '\n');
+  FuncNumInstRemoved += LocalNumRemoved;
+  FuncNumBranchesRemoved += LocalNumBranchesRemoved;
+  NumBranchesRemoved += FuncNumBranchesRemoved;
+  NumRemoved += FuncNumInstRemoved;
+}
+
+//===----------------------------------------------------------------------===//
+//
+// Debugging and validation code
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef NDEBUG
+void AggressiveDCE::validatePhiNodes(BasicBlock *BB) {
+
+  if (BB->empty())
+    return;
+  PHINode *APN = dyn_cast<PHINode>(&BB->front());
+  if (!APN)
+    return;
+
+  SmallVector<std::pair<BasicBlock *, Value *>, 16> Preds;
+  for (auto Pred : predecessors(BB)) {
+    Preds.emplace_back(Pred, nullptr);
+  }
+  auto error = [this, BB](PHINode *PN, BasicBlock *Pred, const char *Message) {
+    errs() << "Error in function: " << F.getName() << "\n\t" << Message << '\n';
+    errs() << "\tblock " << BB->getName() << '\n';
+    errs() << "\tpred  " << Pred->getName() << "\n\t";
+    PN->print(errs());
+    errs() << '\n';
+  };
+
+  for (auto it = BB->begin(); PHINode *PN = dyn_cast<PHINode>(it); ++it) {
+    if (!isLive(PN)) {
+      continue;
+    }
+    auto NumIdx = PN->getNumIncomingValues();
+    for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+      auto Value = PN->getIncomingValue(Idx);
+      auto Pred = PN->getIncomingBlock(Idx);
+      bool Found = false;
+      for (auto &P : Preds) {
+        if (P.first == Pred) {
+          if (!P.second) {
+            P.second = Value;
+            Found = true;
+            break;
+          }
+          if (P.second != Value) {
+            error(PN, Pred, "multiple distinct values");
+          }
+        }
+      }
+      if (!Found) {
+        error(PN, Pred, "no predecessor for value");
+      }
+    }
+    for (auto &P : Preds) {
+      if (!P.second) {
+        error(PN, P.first, "no value for predecessor");
+      }
+      P.second = nullptr; // reset for next PHI
+    }
+  }
+}
+#endif
+
+//===----------------------------------------------------------------------===//
+//
+// Pass Manager integration code
+//
+//===----------------------------------------------------------------------===//
+PreservedAnalyses ADCEPass::run(Function &F, AnalysisManager<Function> &AM) {
+  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
+  bool TODO = false;
+  if (AggressiveDCE(F, PDT, TODO).doAggressiveCDCE())
+    return PreservedAnalyses::none();
+  return PreservedAnalyses::all();
+}
+
+namespace {
+struct ADCELegacyPass : public FunctionPass {
+  bool RemoveControlFlow;
+  static char ID; // Pass identification, replacement for typeid
+  ADCELegacyPass(bool RemoveControlFlow = false)
+      : FunctionPass(ID), RemoveControlFlow(RemoveControlFlow) {
+    initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
+    return AggressiveDCE(F, PDT, RemoveControlFlow).doAggressiveCDCE();
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<PostDominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+  }
+};
+}
+
+char ADCELegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
+                      "Aggressive Dead Code Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
+INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
+                    false, false)
+
+FunctionPass *llvm::createAggressiveDCEPass(bool RemoveControlFlow) {
+  return new ADCELegacyPass(RemoveControlFlow);
+}

lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_library(LLVMScalarOpts
-  ADCE.cpp
+  ADCE_new.cpp
   AlignmentFromAssumptions.cpp
   BDCE.cpp
   ConstantHoisting.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
   EarlyCSE.cpp

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeLoopVersioningPassPass(Registry);
 }
 
 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) {
-  unwrap(PM)->add(createAggressiveDCEPass());
+  unwrap(PM)->add(createAggressiveDCEPass(/*RemoveControlFlow*/false));
 }
 
 void LLVMAddBitTrackingDCEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createBitTrackingDCEPass());
 }
 
 void LLVMAddAlignmentFromAssumptionsPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAlignmentFromAssumptionsPass());

test/Transforms/ADCE/2002-01-31-UseStuckAround.ll

 ; RUN:  opt < %s -adce
+; RUN:  opt < %s -adce -adce-remove-control-flow
 
 define i32 @"main"(i32 %argc) {
   br label %2
 
   %retval = phi i32 [ %argc, %2 ]    ; <i32>  [#uses=2]
   %two = add i32 %retval, %retval   ; <i32> [#uses=1]
   ret i32 %two
 
   br label %1
 }

test/Transforms/ADCE/2002-05-22-PHITest.ll

 ; It is illegal to remove BB1 because it will mess up the PHI node!
 ;
-; RUN: opt < %s -adce -S | grep BB1
+; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-control-flow -S | grep BB1
 
 define i32 @test(i1 %C, i32 %A, i32 %B) {
 ; <label>:0
         br i1 %C, label %BB1, label %BB2
 
 BB1:            ; preds = %0
         br label %BB2
 
 BB2:            ; preds = %BB1, %0
         %R = phi i32 [ %A, %0 ], [ %B, %BB1 ]           ; <i32> [#uses=1]
         ret i32 %R
 }
 

test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll

 ; This testcase contains a entire loop that should be removed.  The only thing
 ; left is the store instruction in BB0.  The problem this testcase was running
 ; into was that when the reg109 PHI was getting zero predecessors, it was 
 ; removed even though there were uses still around.  Now the uses are filled
 ; in with a dummy value before the PHI is deleted.
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -S -adce -adce-remove-control-flow | grep bb1
+; RUN: opt < %s -S -adce -adce-remove-loops | FileCheck %s
   
         %node_t = type { double*, %node_t*, %node_t**, double**, double*, i32, i32 }
 
 define void @localize_local(%node_t* %nodelist) {
 bb0:
         %nodelist.upgrd.1 = alloca %node_t*             ; <%node_t**> [#uses=2]
         store %node_t* %nodelist, %node_t** %nodelist.upgrd.1
         br label %bb1
 
+; CHECK-NOT: bb1:
+; CHECK-NOT: bb2:
 bb1:            ; preds = %bb0
         %reg107 = load %node_t*, %node_t** %nodelist.upgrd.1              ; <%node_t*> [#uses=2]
         %cond211 = icmp eq %node_t* %reg107, null               ; <i1> [#uses=1]
         br i1 %cond211, label %bb3, label %bb2
 
 bb2:            ; preds = %bb2, %bb1
         %reg109 = phi %node_t* [ %reg110, %bb2 ], [ %reg107, %bb1 ]             ; <%node_t*> [#uses=1]
         %reg212 = getelementptr %node_t, %node_t* %reg109, i64 0, i32 1          ; <%node_t**> [#uses=1]
         %reg110 = load %node_t*, %node_t** %reg212                ; <%node_t*> [#uses=2]
         %cond213 = icmp ne %node_t* %reg110, null               ; <i1> [#uses=1]
         br i1 %cond213, label %bb2, label %bb3
 
 bb3:            ; preds = %bb2, %bb1
         ret void
 }
 

test/Transforms/ADCE/2002-05-28-Crash-distilled.ll

 ; This testcase is a distilled form of: 2002-05-28-Crash.ll
 
 ; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-control-flow
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define float @test(i32 %i) {
         %F = sitofp i32 %i to float             ; <float> [#uses=1]
         %I = bitcast i32 %i to i32              ; <i32> [#uses=1]
         br label %Loop
 
+; CHECK-NOT: Loop:
 Loop:           ; preds = %Loop, %0
         %B = icmp ne i32 %I, 0          ; <i1> [#uses=1]
         br i1 %B, label %Out, label %Loop
 
 Out:            ; preds = %Loop
         ret float %F
 }
 

test/Transforms/ADCE/2002-05-28-Crash.ll

 ; This testcase is distilled from the GNU rx package.  The loop should be 
 ; removed but causes a problem when ADCE does.  The source function is:
 ; int rx_bitset_empty (int size, rx_Bitset set) {
 ;  int x;
 ;  RX_subset s;
 ;  s = set[0];
 ;  set[0] = 1;
 ;  for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
 ;    ;
 ;  set[0] = s;
 ;  return !s;
 ;}
 ;
 ; RUN: opt < %s -adce
+; RUN: opt < %s -adce -adce-remove-control-flow
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define i32 @rx_bitset_empty(i32 %size, i32* %set) {
 bb1:
         %reg110 = load i32, i32* %set                ; <i32> [#uses=2]
         store i32 1, i32* %set
         %cast112 = sext i32 %size to i64                ; <i64> [#uses=1]
         %reg113 = add i64 %cast112, 31          ; <i64> [#uses=1]
         %reg114 = lshr i64 %reg113, 5           ; <i64> [#uses=2]
         %cast109 = trunc i64 %reg114 to i32             ; <i32> [#uses=1]
         %reg129 = add i32 %cast109, -1          ; <i32> [#uses=1]
         %reg114-idxcast = trunc i64 %reg114 to i32              ; <i32> [#uses=1]
         %reg114-idxcast-offset = add i32 %reg114-idxcast, 1073741823            ; <i32> [#uses=1]
         %reg114-idxcast-offset.upgrd.1 = zext i32 %reg114-idxcast-offset to i64         ; <i64> [#uses=1]
         %reg124 = getelementptr i32, i32* %set, i64 %reg114-idxcast-offset.upgrd.1           ; <i32*> [#uses=1]
         %reg125 = load i32, i32* %reg124             ; <i32> [#uses=1]
         %cond232 = icmp ne i32 %reg125, 0               ; <i1> [#uses=1]
         br i1 %cond232, label %bb3, label %bb2
 
+; CHECK-NOT: bb2:
 bb2:            ; preds = %bb2, %bb1
         %cann-indvar = phi i32 [ 0, %bb1 ], [ %add1-indvar, %bb2 ]              ; <i32> [#uses=2]
         %reg130-scale = mul i32 %cann-indvar, -1                ; <i32> [#uses=1]
         %reg130 = add i32 %reg130-scale, %reg129                ; <i32> [#uses=1]
         %add1-indvar = add i32 %cann-indvar, 1          ; <i32> [#uses=1]
         %reg130-idxcast = bitcast i32 %reg130 to i32            ; <i32> [#uses=1]
         %reg130-idxcast-offset = add i32 %reg130-idxcast, 1073741823            ; <i32> [#uses=1]
         %reg130-idxcast-offset.upgrd.2 = zext i32 %reg130-idxcast-offset to i64         ; <i64> [#uses=1]

test/Transforms/ADCE/2002-07-17-AssertionFailure.ll

 ; This testcase fails because ADCE does not correctly delete the chain of 
 ; three instructions that are dead here.  Ironically there were a dead basic
 ; block in this function, it would work fine, but that would be the part we 
 ; have to fix now, wouldn't it....
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce -S | FileCheck %s
 
 define void @foo(i8* %reg5481) {
         %cast611 = bitcast i8* %reg5481 to i8**         ; <i8**> [#uses=1]
         %reg162 = load i8*, i8** %cast611            ; <i8*> [#uses=1]
+; CHECK-NOT: ptrtoint
         ptrtoint i8* %reg162 to i32             ; <i32>:1 [#uses=0]
         ret void
 }

test/Transforms/ADCE/2002-07-17-PHIAssertion.ll

 ; This testcase was extracted from the gzip SPEC benchmark
 ;
 ; RUN: opt < %s -adce
+; RUN: opt < %s -adce -adce-remove-control-flow | FileCheck %s
 
 @bk = external global i32               ; <i32*> [#uses=2]
 @hufts = external global i32            ; <i32*> [#uses=1]
 
 define i32 @inflate() {
 bb0:
         br label %bb2
 
 bb2:            ; preds = %bb6, %bb0
         %reg128 = phi i32 [ %reg130, %bb6 ], [ 0, %bb0 ]                ; <i32> [#uses=2]
         br i1 true, label %bb4, label %bb3
 
 bb3:            ; preds = %bb2
         br label %UnifiedExitNode
 
+; CHECK-NOT: bb4:
+; CHECK-NOT: bb5:
 bb4:            ; preds = %bb2
         %reg117 = load i32, i32* @hufts              ; <i32> [#uses=2]
         %cond241 = icmp ule i32 %reg117, %reg128                ; <i1> [#uses=1]
         br i1 %cond241, label %bb6, label %bb5
 
 bb5:            ; preds = %bb4
         br label %bb6
 

test/Transforms/ADCE/2002-07-29-Segfault.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define void @test() {
         br label %BB3
 
 BB3:            ; preds = %BB3, %0
         br label %BB3
 }
 

test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll

 ; Testcase reduced from 197.parser by bugpoint
 ; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-control-flow 
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define void @conjunction_prune() {
 ; <label>:0
         br label %bb19
 
+; CHECK-NOT: bb19:
 bb19:           ; preds = %bb23, %bb22, %0
         %reg205 = phi i8* [ null, %bb22 ], [ null, %bb23 ], [ null, %0 ]                ; <i8*> [#uses=1]
         br i1 false, label %bb21, label %bb22
 
+; CHECK-NOT: bb21:
 bb21:           ; preds = %bb19
         %cast455 = bitcast i8* %reg205 to i8**          ; <i8**> [#uses=0]
         br label %bb22
 
 bb22:           ; preds = %bb21, %bb19
         br i1 false, label %bb19, label %bb23
 
 bb23:           ; preds = %bb22
         br i1 false, label %bb19, label %bb28
 
 bb28:           ; preds = %bb23
         ret void
 }
 

test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll

 ; THis testcase caused an assertion failure because a PHI node did not have 
 ; entries for it's postdominator.  But I think this can only happen when the 
 ; PHI node is dead, so we just avoid patching up dead PHI nodes.
 
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-control-flow -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 target datalayout = "e-p:32:32"
 
 define void @dead_test8() {
 entry:
         br label %loopentry
 
 loopentry:              ; preds = %endif, %entry
         %k.1 = phi i32 [ %k.0, %endif ], [ 0, %entry ]          ; <i32> [#uses=1]
         br i1 false, label %no_exit, label %return
 
+; CHECK-NOT: no_exit:
+; CHECK-NOT: then:
+; CHECK-NOT: else:
 no_exit:                ; preds = %loopentry
         br i1 false, label %then, label %else
 
 then:           ; preds = %no_exit
         br label %endif
 
 else:           ; preds = %no_exit
         %dec = add i32 %k.1, -1         ; <i32> [#uses=1]

test/Transforms/ADCE/2003-06-11-InvalidCFG.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 @G = external global i32*               ; <i32**> [#uses=1]
 
 declare void @Fn(i32*)
 
 define i32 @main(i32 %argc.1, i8** %argv.1) {
 entry:
         br label %endif.42

test/Transforms/ADCE/2003-06-24-BadSuccessor.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
 target datalayout = "e-p:32:32"
   %struct..CppObjTypeDesc = type { i32, i16, i16 }
   %struct..TypeToken = type { i32, i16, i16 }
 
 define i32 @C_ReFaxToDb() {
 entry:
   br i1 false, label %endif.0, label %then.0
 

 endif.14:   ; preds = %loopentry.0
   br i1 false, label %loopentry.1, label %loopentry.0
 
 loopentry.1:    ; preds = %then.53, %endif.14
   %SubArrays.10 = phi i32* [ %SubArrays.8, %then.53 ], [ null, %endif.14 ]    ; <i32*> [#uses=3]
   br i1 false, label %no_exit.1, label %loopentry.0
 
 no_exit.1:    ; preds = %loopentry.1
+; CHECK: switch
   switch i32 0, label %label.17 [
      i32 2, label %label.11
      i32 19, label %label.10
   ]
 
 label.10:   ; preds = %no_exit.1
   br i1 false, label %then.43, label %endif.43
 
shortcirc_next.7:   ; preds = %label.17
   br i1 false, label %then.53, label %shortcirc_next.8
 
 shortcirc_next.8:   ; preds = %shortcirc_next.7
   ret i32 0
 
 then.53:    ; preds = %shortcirc_next.7, %label.17
   %SubArrays.8 = phi i32* [ %SubArrays.10, %shortcirc_next.7 ], [ %SubArrays.10, %label.17 ]    ; <i32*> [#uses=1]
   %tmp.1023 = load i32, i32* null    ; <i32> [#uses=1]
+; CHECK-NOT: switch
   switch i32 %tmp.1023, label %loopentry.1 [
   ]
 
 loopexit.0:   ; preds = %loopentry.0
   ret i32 0
 
 else.2:   ; preds = %then.11
   ret i32 0
 }

test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll

 ; RUN: opt < %s -adce -simplifycfg -S | not grep then:
+; RUN: opt < %s -adce -adce-remove-control-flow -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define void @dead_test8(i32* %data.1, i32 %idx.1) {
 entry:
         %tmp.1 = load i32, i32* %data.1              ; <i32> [#uses=2]
         %tmp.41 = icmp sgt i32 %tmp.1, 0                ; <i1> [#uses=1]
         br i1 %tmp.41, label %no_exit.preheader, label %return
 
 no_exit.preheader:              ; preds = %entry
         %tmp.11 = getelementptr i32, i32* %data.1, i64 1             ; <i32*> [#uses=1]
         %tmp.22-idxcast = sext i32 %idx.1 to i64                ; <i64> [#uses=1]
         %tmp.28 = getelementptr i32, i32* %data.1, i64 %tmp.22-idxcast               ; <i32*> [#uses=1]
         br label %no_exit
 
 no_exit:                ; preds = %endif, %no_exit.preheader
         %k.1 = phi i32 [ %k.0, %endif ], [ 0, %no_exit.preheader ]              ; <i32> [#uses=3]
         %i.0 = phi i32 [ %inc.1, %endif ], [ 0, %no_exit.preheader ]            ; <i32> [#uses=1]
         %tmp.12 = load i32, i32* %tmp.11             ; <i32> [#uses=1]
         %tmp.14 = sub i32 0, %tmp.12            ; <i32> [#uses=1]
         %tmp.161 = icmp ne i32 %k.1, %tmp.14            ; <i1> [#uses=1]
         br i1 %tmp.161, label %then, label %else
 
+; CHECK-NOT: %tmp.161
+; CHECK-NOT: then:
+; CHECK-NOT: else
+
 then:           ; preds = %no_exit
         %inc.0 = add i32 %k.1, 1                ; <i32> [#uses=1]
         br label %endif
 
 else:           ; preds = %no_exit
         %dec = add i32 %k.1, -1         ; <i32> [#uses=1]
         br label %endif
 

test/Transforms/ADCE/2003-09-10-UnwindInstFail.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -disable-output -adce-remove-loops
 
 define void @test() personality i32 (...)* @__gxx_personality_v0 {
         br i1 false, label %then, label %endif
 
 then:           ; preds = %0
         invoke void null( i8* null )
                         to label %invoke_cont unwind label %invoke_catch
 

test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define i32 @main() {
         br label %loop
 
 loop:           ; preds = %loop, %0
         br label %loop
 }
 

test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll

 ; RUN: opt < %s -adce -simplifycfg -S | grep call
+; RUN: opt < %s -adce -adce-remove-control-flow -simplifycfg -S | grep call
+; RUN: opt < %s -adce -adce-remove-loops -simplifycfg -S | grep call
+
 declare void @exit(i32)
 
 define i32 @main(i32 %argc) {
         %C = icmp eq i32 %argc, 1               ; <i1> [#uses=2]
         br i1 %C, label %Cond, label %Done
 
 Cond:           ; preds = %0
         br i1 %C, label %Loop, label %Done

test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define void @test() {
 entry:
         br label %UnifiedReturnBlock
 
 UnifiedReturnBlock:             ; preds = %invoke_catch.0, %entry
         ret void
 
 invoke_catch.0:         ; No predecessors!
         br i1 false, label %UnifiedUnwindBlock, label %UnifiedReturnBlock
 
 UnifiedUnwindBlock:             ; preds = %invoke_catch.0
         unreachable
 }
 

test/Transforms/ADCE/2005-02-17-PHI-Invoke-Crash.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
 
 declare void @strlen()
 
 declare void @_ZN10QByteArray6resizeEi()
 
 declare void @q_atomic_decrement()
 
 define void @_ZNK10QByteArray13leftJustifiedEicb() personality i32 (...)* @__gxx_personality_v0 {

test/Transforms/ADCE/basictest.ll

 ; RUN: opt < %s -adce -simplifycfg | llvm-dis
 ; RUN: opt < %s -passes=adce | llvm-dis
+; RUN: opt < %s -adce -adce-remove-control-flow | llvm-dis
+; RUN: opt < %s -passes=adce  -adce-remove-control-flow | llvm-dis
 
 define i32 @Test(i32 %A, i32 %B) {
 BB1:
         br label %BB4
 
 BB2:            ; No predecessors!
         br label %BB3
 
 BB3:            ; preds = %BB4, %BB2
         %ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ]               ; <i32> [#uses=1]
         ret i32 %ret
 
 BB4:            ; preds = %BB1
         %X = phi i32 [ %A, %BB1 ]               ; <i32> [#uses=1]
         br label %BB3
 }

test/Transforms/ADCE/basictest1.ll

 ; RUN: opt < %s -adce -simplifycfg | llvm-dis  
+; RUN: opt < %s -adce -adce-remove-control-flow -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
 %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 }
   %spec_fd_t = type { i32, i32, i32, i8* }
 @__iob = external global [20 x %FILE]    ; <[20 x %FILE]*> [#uses=1]
 @dbglvl = global i32 4    ; <i32*> [#uses=3]
 @spec_fd = external global [3 x %spec_fd_t]    ; <[3 x %spec_fd_t]*> [#uses=4]
 @.LC9 = internal global [34 x i8] c"spec_read: fd=%d, > MAX_SPEC_FD!\0A\00"    ; <[34 x i8]*> [#uses=1]
 @.LC10 = internal global [4 x i8] c"EOF\00"    ; <[4 x i8]*> [#uses=1]
 @.LC11 = internal global [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=1]

 
 declare void @perror(i8*)
 
 define i32 @spec_getc(i32 %fd) {
   %reg109 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond266 = icmp sle i32 %reg109, 4    ; <i1> [#uses=1]
   br i1 %cond266, label %bb3, label %bb2
 
+; CHECK-NOT: bb2:
+
 bb2:    ; preds = %0
   %cast273 = getelementptr [17 x i8], [17 x i8]* @.LC12, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb3
 
 bb3:    ; preds = %bb2, %0
   %cond267 = icmp sle i32 %fd, 3    ; <i1> [#uses=1]
   br i1 %cond267, label %bb5, label %bb4
 
bb5:    ; preds = %bb3
   %reg1311 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast2    ; <%spec_fd_t*> [#uses=1]
   %idx1 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast1, i32 2    ; <i32*> [#uses=1]
   %reg1321 = load i32, i32* %idx1    ; <i32> [#uses=3]
   %idx2 = getelementptr %spec_fd_t, %spec_fd_t* %reg1311, i64 0, i32 1    ; <i32*> [#uses=1]
   %reg1331 = load i32, i32* %idx2    ; <i32> [#uses=1]
   %cond270 = icmp slt i32 %reg1321, %reg1331    ; <i1> [#uses=1]
   br i1 %cond270, label %bb9, label %bb6
 
+; CHECK-NOT: bb6:
+; CHECK-NOT: bb7:
+; CHECK-NOT: bb8:
+
 bb6:    ; preds = %bb5
   %reg134 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond271 = icmp sle i32 %reg134, 4    ; <i1> [#uses=1]
   br i1 %cond271, label %bb8, label %bb7
 
 bb7:    ; preds = %bb6
   %cast277 = getelementptr [4 x i8], [4 x i8]* @.LC10, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb8
bb9:    ; preds = %bb5
   %cast108 = zext i8 %reg1621 to i64    ; <i64> [#uses=0]
   %reg157 = add i32 %reg1321, 1   ; <i32> [#uses=1]
   %idx5 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast1, i32 2    ; <i32*> [#uses=1]
   store i32 %reg157, i32* %idx5
   %reg163 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond272 = icmp sle i32 %reg163, 4    ; <i1> [#uses=1]
   br i1 %cond272, label %bb11, label %bb10
 
+; CHECK-NOT: bb10:
+
 bb10:   ; preds = %bb9
   %cast279 = getelementptr [4 x i8], [4 x i8]* @.LC11, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb11
 
 bb11:   ; preds = %bb10, %bb9
   %cast291 = zext i8 %reg1621 to i32    ; <i32> [#uses=1]
   br label %UnifiedExitNode
 
 UnifiedExitNode:    ; preds = %bb11, %bb8, %bb4
   %UnifiedRetVal = phi i32 [ 42, %bb4 ], [ -1, %bb8 ], [ %cast291, %bb11 ]    ; <i32> [#uses=1]
   ret i32 %UnifiedRetVal
 }
 
 declare i32 @puts(i8*)
 
 declare i32 @printf(i8*, ...)

test/Transforms/ADCE/basictest2.ll

 ; RUN: opt < %s -adce -simplifycfg | llvm-dis
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
   %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 }
   %spec_fd_t = type { i32, i32, i32, i8* }
 @__iob = external global [20 x %FILE]    ; <[20 x %FILE]*> [#uses=1]
 @dbglvl = global i32 4    ; <i32*> [#uses=3]
 @spec_fd = external global [3 x %spec_fd_t]    ; <[3 x %spec_fd_t]*> [#uses=4]
 @.LC9 = internal global [34 x i8] c"spec_read: fd=%d, > MAX_SPEC_FD!\0A\00"    ; <[34 x i8]*> [#uses=1]
 @.LC10 = internal global [4 x i8] c"EOF\00"    ; <[4 x i8]*> [#uses=1]
 @.LC11 = internal global [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=1]

 
 declare void @perror(i8*)
 
 define i32 @spec_getc(i32 %fd) {
   %reg109 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond266 = icmp sle i32 %reg109, 4    ; <i1> [#uses=1]
   br i1 %cond266, label %bb3, label %bb2
 
+; CHECK-NOT: bb2:
 bb2:    ; preds = %0
   %cast273 = getelementptr [17 x i8], [17 x i8]* @.LC12, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb3
 
 bb3:    ; preds = %bb2, %0
   %cond267 = icmp sle i32 %fd, 3    ; <i1> [#uses=0]
   br label %bb5
 
bb5:    ; preds = %bb3
   %reg1311 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast2    ; <%spec_fd_t*> [#uses=1]
   %idx1 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast1, i32 2    ; <i32*> [#uses=1]
   %reg1321 = load i32, i32* %idx1    ; <i32> [#uses=3]
   %idx2 = getelementptr %spec_fd_t, %spec_fd_t* %reg1311, i64 0, i32 1    ; <i32*> [#uses=1]
   %reg1331 = load i32, i32* %idx2    ; <i32> [#uses=1]
   %cond270 = icmp slt i32 %reg1321, %reg1331    ; <i1> [#uses=1]
   br i1 %cond270, label %bb9, label %bb6
 
+; CHECK-NOT: bb6:
+; CHECK-NOT: bb7:
+; CHECK-NOT: bb:
 bb6:    ; preds = %bb5
   %reg134 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond271 = icmp sle i32 %reg134, 4    ; <i1> [#uses=1]
   br i1 %cond271, label %bb8, label %bb7
 
 bb7:    ; preds = %bb6
   %cast277 = getelementptr [4 x i8], [4 x i8]* @.LC10, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb8
bb9:    ; preds = %bb5
   %cast108 = zext i8 %reg1621 to i64    ; <i64> [#uses=0]
   %reg157 = add i32 %reg1321, 1   ; <i32> [#uses=1]
   %idx5 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast1, i32 2    ; <i32*> [#uses=1]
   store i32 %reg157, i32* %idx5
   %reg163 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond272 = icmp sle i32 %reg163, 4    ; <i1> [#uses=1]
   br i1 %cond272, label %bb11, label %bb10
 
+; CHECK-NOT: bb10:
 bb10:   ; preds = %bb9
   %cast279 = getelementptr [4 x i8], [4 x i8]* @.LC11, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb11
 
 bb11:   ; preds = %bb10, %bb9
   %cast291 = zext i8 %reg1621 to i32    ; <i32> [#uses=1]
   br label %UnifiedExitNode
 
 UnifiedExitNode:    ; preds = %bb11, %bb8, %bb4
   %UnifiedRetVal = phi i32 [ 42, %bb4 ], [ -1, %bb8 ], [ %cast291, %bb11 ]    ; <i32> [#uses=1]
   ret i32 %UnifiedRetVal
 }
 
 declare i32 @puts(i8*)
 
 declare i32 @printf(i8*, ...)

test/Transforms/ADCE/unreachable-function.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-control-flow -disable-output
 
 define void @test() {
   unreachable
 }