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

87

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

312–313

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

312–313

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/InitializePasses.h

 
 /// Initialize all passes linked into the GlobalISel library.
 void initializeGlobalISel(PassRegistry &Registry);
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
 void initializeAAEvalLegacyPassPass(PassRegistry&);
+void initializeACDCELegacyPassPass(PassRegistry&);
 void initializeAddDiscriminatorsPass(PassRegistry&);
 void initializeADCELegacyPassPass(PassRegistry&);
 void initializeBDCELegacyPassPass(PassRegistry &);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlwaysInlinerPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);
 void initializeAtomicExpandPass(PassRegistry&);
 void initializeSampleProfileLoaderLegacyPassPass(PassRegistry&);

include/llvm/Transforms/Scalar.h

 //
 // DeadStoreElimination - This pass deletes stores that are post-dominated by
 // must-aliased stores and are not loaded used between the stores.
 //
 FunctionPass *createDeadStoreEliminationPass();
 
 //===----------------------------------------------------------------------===//
 //
-// AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm.  This
-// algorithm assumes instructions are dead until proven otherwise, which makes
-// it more successful are removing non-obviously dead instructions.
-//
-FunctionPass *createAggressiveDCEPass();
-
-
-//===----------------------------------------------------------------------===//
-//
 // GuardWidening - An optimization over the @llvm.experimental.guard intrinsic
 // 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 RetainControlFlow = true);
+
+//===----------------------------------------------------------------------===//
+//
 // 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.h

-//===- ADCE.h - Aggressive dead code elimination --------------------------===//
+//===- ACDCE.h - Aggressive control 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
+#ifndef LLVM_TRANSFORMS_SCALAR_ACDCE_H
+#define LLVM_TRANSFORMS_SCALAR_ACDCE_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);
+  bool RetainControlFlow;
+  ADCEPass(bool RetainControlFlow = true);
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
 };
 }
 
-#endif // LLVM_TRANSFORMS_SCALAR_ADCE_H
+#endif // LLVM_TRANSFORMS_SCALAR_ACDCE_H

lib/Transforms/IPO/PassManagerBuilder.cpp

 //===- PassManagerBuilder.cpp - Build Standard Pass -----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the PassManagerBuilder class, which is used to set up a
 // "standard" optimization sequence suitable for languages like C and C++.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm-c/Transforms/PassManagerBuilder.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFLAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Vectorize.h"
 
 using namespace llvm;
 
 static cl::opt<bool>
     RunLoopVectorization("vectorize-loops", cl::Hidden,
                          cl::desc("Run the Loop vectorization passes"));
 
 static cl::opt<bool>
     RunSLPVectorization("vectorize-slp", cl::Hidden,
                         cl::desc("Run the SLP vectorization passes"));
 
 static cl::opt<bool>
     RunBBVectorization("vectorize-slp-aggressive", cl::Hidden,
                        cl::desc("Run the BB vectorization passes"));
 
-static cl::opt<bool>
-UseGVNAfterVectorization("use-gvn-after-vectorization",
-  cl::init(false), cl::Hidden,
+static cl::opt<bool> UseGVNAfterVectorization(
+    "use-gvn-after-vectorization", cl::init(false), cl::Hidden,
     cl::desc("Run GVN instead of Early CSE after vectorization passes"));
 
 static cl::opt<bool> ExtraVectorizerPasses(
     "extra-vectorizer-passes", cl::init(false), cl::Hidden,
     cl::desc("Run cleanup optimization passes after vectorization."));
 
-static cl::opt<bool> UseNewSROA("use-new-sroa",
-  cl::init(true), cl::Hidden,
+static cl::opt<bool>
+    UseNewSROA("use-new-sroa", cl::init(true), cl::Hidden,
                cl::desc("Enable the new, experimental SROA pass"));
 
-static cl::opt<bool>
-RunLoopRerolling("reroll-loops", cl::Hidden,
+static cl::opt<bool> RunLoopRerolling("reroll-loops", cl::Hidden,
                                       cl::desc("Run the loop rerolling pass"));
 
 static cl::opt<bool>
     RunFloat2Int("float-to-int", cl::Hidden, cl::init(true),
                  cl::desc("Run the float2int (float demotion) pass"));
 
 static cl::opt<bool> RunLoadCombine("combine-loads", cl::init(false),
                                     cl::Hidden,
                                     cl::desc("Run the load combining pass"));
 
-static cl::opt<bool>
-RunSLPAfterLoopVectorization("run-slp-after-loop-vectorization",
-  cl::init(true), cl::Hidden,
+static cl::opt<bool> RunSLPAfterLoopVectorization(
+    "run-slp-after-loop-vectorization", cl::init(true), cl::Hidden,
     cl::desc("Run the SLP vectorizer (and BB vectorizer) after the Loop "
              "vectorizer instead of before"));
 
-static cl::opt<bool> UseCFLAA("use-cfl-aa",
-  cl::init(false), cl::Hidden,
+static cl::opt<bool>
+    UseCFLAA("use-cfl-aa", cl::init(false), cl::Hidden,
              cl::desc("Enable the new, experimental CFL alias analysis"));
 
 static cl::opt<bool>
     EnableMLSM("mlsm", cl::init(true), cl::Hidden,
                cl::desc("Enable motion of merged load and store"));
 
 static cl::opt<bool> EnableLoopInterchange(
     "enable-loopinterchange", cl::init(false), cl::Hidden,
     cl::desc("Enable the new, experimental LoopInterchange Pass"));
 
 static cl::opt<bool> EnableNonLTOGlobalsModRef(
     "enable-non-lto-gmr", cl::init(true), cl::Hidden,
     cl::desc(
         "Enable the GlobalsModRef AliasAnalysis outside of the LTO pipeline."));
 
-static cl::opt<bool> EnableLoopLoadElim(
-    "enable-loop-load-elim", cl::init(true), cl::Hidden,
+static cl::opt<bool>
+    EnableLoopLoadElim("enable-loop-load-elim", cl::init(true), cl::Hidden,
                        cl::desc("Enable the LoopLoadElimination Pass"));
 
 static cl::opt<std::string> RunPGOInstrGen(
     "profile-generate", cl::init(""), cl::Hidden,
     cl::desc("Enable generation phase of PGO instrumentation and specify the "
              "path of profile data file"));
 
 static cl::opt<std::string> RunPGOInstrUse(
     "profile-use", cl::init(""), cl::Hidden, cl::value_desc("filename"),
     cl::desc("Enable use phase of PGO instrumentation and specify the path "
              "of profile data file"));
 
 static cl::opt<bool> UseLoopVersioningLICM(
     "enable-loop-versioning-licm", cl::init(false), cl::Hidden,
     cl::desc("Enable the experimental Loop Versioning LICM pass"));
 
 PassManagerBuilder::PassManagerBuilder() {
-    OptLevel = 2;
-    SizeLevel = 0;
-    LibraryInfo = nullptr;
-    Inliner = nullptr;
-    ModuleSummary = nullptr;
-    DisableUnitAtATime = false;
-    DisableUnrollLoops = false;
-    BBVectorize = RunBBVectorization;
-    SLPVectorize = RunSLPVectorization;
-    LoopVectorize = RunLoopVectorization;
-    RerollLoops = RunLoopRerolling;
-    LoadCombine = RunLoadCombine;
-    DisableGVNLoadPRE = false;
-    VerifyInput = false;
-    VerifyOutput = false;
-    MergeFunctions = false;
-    PrepareForLTO = false;
-    PGOInstrGen = RunPGOInstrGen;
-    PGOInstrUse = RunPGOInstrUse;
-    PrepareForThinLTO = false;
-    PerformThinLTO = false;
 }
 
 PassManagerBuilder::~PassManagerBuilder() {
   delete LibraryInfo;
   delete Inliner;
 }
 
 /// Set of global extensions, automatically added as part of the standard set.
 static ManagedStatic<SmallVector<std::pair<PassManagerBuilder::ExtensionPointTy,
-   PassManagerBuilder::ExtensionFn>, 8> > GlobalExtensions;
+                                           PassManagerBuilder::ExtensionFn>,
+                                 8>>
+    GlobalExtensions;
 
 void PassManagerBuilder::addGlobalExtension(
     PassManagerBuilder::ExtensionPointTy Ty,
     PassManagerBuilder::ExtensionFn Fn) {
   GlobalExtensions->push_back(std::make_pair(Ty, std::move(Fn)));
 }
 
 void PassManagerBuilder::addExtension(ExtensionPointTy Ty, ExtensionFn Fn) {

 void PassManagerBuilder::populateFunctionPassManager(
     legacy::FunctionPassManager &FPM) {
   addExtensionsToPM(EP_EarlyAsPossible, FPM);
 
   // Add LibraryInfo if we have some.
   if (LibraryInfo)
     FPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 
-  if (OptLevel == 0) return;
+  if (OptLevel == 0)
+    return;
 
   addInitialAliasAnalysisPasses(FPM);
 
   FPM.add(createCFGSimplificationPass());
   if (UseNewSROA)
     FPM.add(createSROAPass());
   else
     FPM.add(createScalarReplAggregatesPass());

 void PassManagerBuilder::addFunctionSimplificationPasses(
     legacy::PassManagerBase &MPM) {
   // Start of function pass.
   // Break up aggregate allocas, using SSAUpdater.
   if (UseNewSROA)
     MPM.add(createSROAPass());
   else
     MPM.add(createScalarReplAggregatesPass(-1, false));
-  MPM.add(createEarlyCSEPass());              // Catch trivial redundancies
+  MPM.add(createEarlyCSEPass()); // Catch trivial redundancies
   // Speculative execution if the target has divergent branches; otherwise nop.
   MPM.add(createSpeculativeExecutionIfHasBranchDivergencePass());
-  MPM.add(createJumpThreadingPass());         // Thread jumps.
+  MPM.add(createJumpThreadingPass());              // Thread jumps.
   MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
-  MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
+  MPM.add(createCFGSimplificationPass());          // Merge & remove BBs
   // Combine silly seq's
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
-  MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
-  MPM.add(createReassociatePass());           // Reassociate expressions
+  MPM.add(createCFGSimplificationPass());   // Merge & remove BBs
+  MPM.add(createReassociatePass());         // Reassociate expressions
   // Rotate Loop - disable header duplication at -Oz
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
-  MPM.add(createLICMPass());                  // Hoist loop invariants
+  MPM.add(createLICMPass()); // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createCFGSimplificationPass());
   addInstructionCombiningPass(MPM);
-  MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
-  MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
-  MPM.add(createLoopDeletionPass());          // Delete dead loops
+  MPM.add(createIndVarSimplifyPass()); // Canonicalize indvars
+  MPM.add(createLoopIdiomPass());      // Recognize idioms like memset.
+  MPM.add(createLoopDeletionPass());   // Delete dead loops
   if (EnableLoopInterchange) {
     MPM.add(createLoopInterchangePass()); // Interchange loops
     MPM.add(createCFGSimplificationPass());
   }
   if (!DisableUnrollLoops)
-    MPM.add(createSimpleLoopUnrollPass());    // Unroll small loops
+    MPM.add(createSimpleLoopUnrollPass()); // Unroll small loops
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
 
   if (OptLevel > 1) {
     if (EnableMLSM)
       MPM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds
-    MPM.add(createGVNPass(DisableGVNLoadPRE));  // Remove redundancies
+    MPM.add(createGVNPass(DisableGVNLoadPRE));    // Remove redundancies
   }
-  MPM.add(createMemCpyOptPass());             // Remove memcpy / form memset
-  MPM.add(createSCCPPass());                  // Constant prop with SCCP
+  MPM.add(createMemCpyOptPass()); // Remove memcpy / form memset
+  MPM.add(createSCCPPass());      // Constant prop with SCCP
 
   // Delete dead bit computations (instcombine runs after to fold away the dead
   // computations, and then ADCE will run later to exploit any new DCE
   // opportunities that creates).
-  MPM.add(createBitTrackingDCEPass());        // Delete dead bit computations
+  MPM.add(createBitTrackingDCEPass()); // Delete dead bit computations
 
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
-  MPM.add(createJumpThreadingPass());         // Thread jumps
+  MPM.add(createJumpThreadingPass()); // Thread jumps
   MPM.add(createCorrelatedValuePropagationPass());
-  MPM.add(createDeadStoreEliminationPass());  // Delete dead stores
+  MPM.add(createDeadStoreEliminationPass()); // Delete dead stores
   MPM.add(createLICMPass());
 
   addExtensionsToPM(EP_ScalarOptimizerLate, MPM);
 
   if (RerollLoops)
     MPM.add(createLoopRerollPass());
   if (!RunSLPAfterLoopVectorization) {
     if (SLPVectorize)
-      MPM.add(createSLPVectorizerPass());   // Vectorize parallel scalar chains.
+      MPM.add(createSLPVectorizerPass()); // Vectorize parallel scalar chains.
 
     if (BBVectorize) {
       MPM.add(createBBVectorizePass());
       addInstructionCombiningPass(MPM);
       addExtensionsToPM(EP_Peephole, MPM);
       if (OptLevel > 1 && UseGVNAfterVectorization)
         MPM.add(createGVNPass(DisableGVNLoadPRE)); // Remove redundancies
       else
-        MPM.add(createEarlyCSEPass());      // Catch trivial redundancies
+        MPM.add(createEarlyCSEPass()); // Catch trivial redundancies
 
       // BBVectorize may have significantly shortened a loop body; unroll again.
       if (!DisableUnrollLoops)
         MPM.add(createLoopUnrollPass());
     }
   }
 
   if (LoadCombine)
     MPM.add(createLoadCombinePass());
 
-  MPM.add(createAggressiveDCEPass());         // Delete dead instructions
+  bool RetainControlFlow = (OptLevel <= 2);
+  MPM.add(
+      createAggressiveDCEPass(RetainControlFlow)); // Delete dead instructions
+
   MPM.add(createCFGSimplificationPass()); // Merge & remove BBs
   // Clean up after everything.
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
 }
 
 void PassManagerBuilder::populateModulePassManager(
     legacy::PassManagerBase &MPM) {
if (PerformThinLTO)
     MPM.add(createGlobalOptimizerPass());
 
   // Scheduling LoopVersioningLICM when inlining is over, because after that
   // we may see more accurate aliasing. Reason to run this late is that too
   // early versioning may prevent further inlining due to increase of code
   // size. By placing it just after inlining other optimizations which runs
   // later might get benefit of no-alias assumption in clone loop.
   if (UseLoopVersioningLICM) {
-    MPM.add(createLoopVersioningLICMPass());    // Do LoopVersioningLICM
-    MPM.add(createLICMPass());                  // Hoist loop invariants
+    MPM.add(createLoopVersioningLICMPass()); // Do LoopVersioningLICM
+    MPM.add(createLICMPass());               // Hoist loop invariants
   }
 
   if (EnableNonLTOGlobalsModRef)
     // We add a fresh GlobalsModRef run at this point. This is particularly
     // useful as the above will have inlined, DCE'ed, and function-attr
     // propagated everything. We should at this point have a reasonably minimal
     // and richly annotated call graph. By computing aliasing and mod/ref
     // information for all local globals here, the late loop passes and notably
if (OptLevel > 1 && ExtraVectorizerPasses) {
     MPM.add(createLICMPass());
     MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
     MPM.add(createCFGSimplificationPass());
     addInstructionCombiningPass(MPM);
   }
 
   if (RunSLPAfterLoopVectorization) {
     if (SLPVectorize) {
-      MPM.add(createSLPVectorizerPass());   // Vectorize parallel scalar chains.
+      MPM.add(createSLPVectorizerPass()); // Vectorize parallel scalar chains.
       if (OptLevel > 1 && ExtraVectorizerPasses) {
         MPM.add(createEarlyCSEPass());
       }
     }
 
     if (BBVectorize) {
       MPM.add(createBBVectorizePass());
       addInstructionCombiningPass(MPM);
       addExtensionsToPM(EP_Peephole, MPM);
       if (OptLevel > 1 && UseGVNAfterVectorization)
         MPM.add(createGVNPass(DisableGVNLoadPRE)); // Remove redundancies
       else
-        MPM.add(createEarlyCSEPass());      // Catch trivial redundancies
+        MPM.add(createEarlyCSEPass()); // Catch trivial redundancies
 
       // BBVectorize may have significantly shortened a loop body; unroll again.
       if (!DisableUnrollLoops)
         MPM.add(createLoopUnrollPass());
     }
   }
 
   addExtensionsToPM(EP_Peephole, MPM);
   MPM.add(createCFGSimplificationPass());
   addInstructionCombiningPass(MPM);
 
   if (!DisableUnrollLoops) {
-    MPM.add(createLoopUnrollPass());    // Unroll small loops
+    MPM.add(createLoopUnrollPass()); // Unroll small loops
 
     // LoopUnroll may generate some redundency to cleanup.
     addInstructionCombiningPass(MPM);
 
     // Runtime unrolling will introduce runtime check in loop prologue. If the
     // unrolled loop is a inner loop, then the prologue will be inside the
     // outer loop. LICM pass can help to promote the runtime check out if the
     // checked value is loop invariant.
void PassManagerBuilder::populateModulePassManager(
 
   if (!DisableUnitAtATime) {
     // FIXME: We shouldn't bother with this anymore.
     MPM.add(createStripDeadPrototypesPass()); // Get rid of dead prototypes
 
     // GlobalOpt already deletes dead functions and globals, at -O2 try a
     // late pass of GlobalDCE.  It is capable of deleting dead cycles.
     if (OptLevel > 1) {
-      MPM.add(createGlobalDCEPass());         // Remove dead fns and globals.
-      MPM.add(createConstantMergePass());     // Merge dup global constants
+      MPM.add(createGlobalDCEPass());     // Remove dead fns and globals.
+      MPM.add(createConstantMergePass()); // Merge dup global constants
     }
   }
 
   if (MergeFunctions)
     MPM.add(createMergeFunctionsPass());
 
   addExtensionsToPM(EP_OptimizerLast, MPM);
 }
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
 
   // Inline small functions
   bool RunInliner = Inliner;
   if (RunInliner) {
     PM.add(Inliner);
     Inliner = nullptr;
   }
 
-  PM.add(createPruneEHPass());   // Remove dead EH info.
+  PM.add(createPruneEHPass()); // Remove dead EH info.
 
   // Optimize globals again if we ran the inliner.
   if (RunInliner)
     PM.add(createGlobalOptimizerPass());
   PM.add(createGlobalDCEPass()); // Remove dead functions.
 
   // If we didn't decide to inline a function, check to see if we can
   // transform it to pass arguments by value instead of by reference.
   PM.add(createArgumentPromotionPass());
 
   // The IPO passes may leave cruft around.  Clean up after them.
   addInstructionCombiningPass(PM);
   addExtensionsToPM(EP_Peephole, PM);
   PM.add(createJumpThreadingPass());
 
   // Break up allocas
   if (UseNewSROA)
     PM.add(createSROAPass());
   else
     PM.add(createScalarReplAggregatesPass());
 
   // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
-  PM.add(createGlobalsAAWrapperPass()); // IP alias analysis.
+  PM.add(createGlobalsAAWrapperPass());             // IP alias analysis.
 
-  PM.add(createLICMPass());                 // Hoist loop invariants.
+  PM.add(createLICMPass()); // Hoist loop invariants.
   if (EnableMLSM)
     PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
-  PM.add(createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
-  PM.add(createMemCpyOptPass());            // Remove dead memcpys.
+  PM.add(createGVNPass(DisableGVNLoadPRE));    // Remove redundancies.
+  PM.add(createMemCpyOptPass());               // Remove dead memcpys.
 
   // Nuke dead stores.
   PM.add(createDeadStoreEliminationPass());
 
   // More loops are countable; try to optimize them.
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());
   if (EnableLoopInterchange)
     PM.add(createLoopInterchangePass());
 
   if (!DisableUnrollLoops)
-    PM.add(createSimpleLoopUnrollPass());   // Unroll small loops
+    PM.add(createSimpleLoopUnrollPass()); // Unroll small loops
   PM.add(createLoopVectorizePass(true, LoopVectorize));
   // The vectorizer may have significantly shortened a loop body; unroll again.
   if (!DisableUnrollLoops)
     PM.add(createLoopUnrollPass());
 
   // Now that we've optimized loops (in particular loop induction variables),
   // we may have exposed more scalar opportunities. Run parts of the scalar
   // optimizer again at this point.
-  addInstructionCombiningPass(PM); // Initial cleanup
+  addInstructionCombiningPass(PM);       // Initial cleanup
   PM.add(createCFGSimplificationPass()); // if-convert
-  PM.add(createSCCPPass()); // Propagate exposed constants
-  addInstructionCombiningPass(PM); // Clean up again
+  PM.add(createSCCPPass());              // Propagate exposed constants
+  addInstructionCombiningPass(PM);       // Clean up again
   PM.add(createBitTrackingDCEPass());
 
   // More scalar chains could be vectorized due to more alias information
   if (RunSLPAfterLoopVectorization)
     if (SLPVectorize)
       PM.add(createSLPVectorizerPass()); // Vectorize parallel scalar chains.
 
   // After vectorization, assume intrinsics may tell us more about pointer
void PassManagerBuilder::populateLTOPassManager(legacy::PassManagerBase &PM) {
   if (OptLevel != 0)
     addLateLTOOptimizationPasses(PM);
 
   if (VerifyOutput)
     PM.add(createVerifierPass());
 }
 
 inline PassManagerBuilder *unwrap(LLVMPassManagerBuilderRef P) {
-    return reinterpret_cast<PassManagerBuilder*>(P);
+  return reinterpret_cast<PassManagerBuilder *>(P);
 }
 
 inline LLVMPassManagerBuilderRef wrap(PassManagerBuilder *P) {
   return reinterpret_cast<LLVMPassManagerBuilderRef>(P);
 }
 
 LLVMPassManagerBuilderRef LLVMPassManagerBuilderCreate() {
   PassManagerBuilder *PMB = new PassManagerBuilder();
   return wrap(PMB);
 }
 
 void LLVMPassManagerBuilderDispose(LLVMPassManagerBuilderRef PMB) {
   PassManagerBuilder *Builder = unwrap(PMB);
   delete Builder;
 }
 
-void
-LLVMPassManagerBuilderSetOptLevel(LLVMPassManagerBuilderRef PMB,
+void LLVMPassManagerBuilderSetOptLevel(LLVMPassManagerBuilderRef PMB,
                                        unsigned OptLevel) {
   PassManagerBuilder *Builder = unwrap(PMB);
   Builder->OptLevel = OptLevel;
 }
 
-void
-LLVMPassManagerBuilderSetSizeLevel(LLVMPassManagerBuilderRef PMB,
+void LLVMPassManagerBuilderSetSizeLevel(LLVMPassManagerBuilderRef PMB,
                                         unsigned SizeLevel) {
   PassManagerBuilder *Builder = unwrap(PMB);
   Builder->SizeLevel = SizeLevel;
 }
 
-void
-LLVMPassManagerBuilderSetDisableUnitAtATime(LLVMPassManagerBuilderRef PMB,
+void LLVMPassManagerBuilderSetDisableUnitAtATime(LLVMPassManagerBuilderRef PMB,
                                                  LLVMBool Value) {
   PassManagerBuilder *Builder = unwrap(PMB);
   Builder->DisableUnitAtATime = Value;
 }
 
-void
-LLVMPassManagerBuilderSetDisableUnrollLoops(LLVMPassManagerBuilderRef PMB,
+void LLVMPassManagerBuilderSetDisableUnrollLoops(LLVMPassManagerBuilderRef PMB,
                                                  LLVMBool Value) {
   PassManagerBuilder *Builder = unwrap(PMB);
   Builder->DisableUnrollLoops = Value;
 }
 
-void
-LLVMPassManagerBuilderSetDisableSimplifyLibCalls(LLVMPassManagerBuilderRef PMB,
-                                                 LLVMBool Value) {
+void LLVMPassManagerBuilderSetDisableSimplifyLibCalls(
+    LLVMPassManagerBuilderRef PMB, LLVMBool Value) {
   // NOTE: The simplify-libcalls pass has been removed.
 }
 
-void
-LLVMPassManagerBuilderUseInlinerWithThreshold(LLVMPassManagerBuilderRef PMB,
-                                              unsigned Threshold) {
+void LLVMPassManagerBuilderUseInlinerWithThreshold(
+    LLVMPassManagerBuilderRef PMB, unsigned Threshold) {
   PassManagerBuilder *Builder = unwrap(PMB);
   Builder->Inliner = createFunctionInliningPass(Threshold);
 }
 
-void
-LLVMPassManagerBuilderPopulateFunctionPassManager(LLVMPassManagerBuilderRef PMB,
-                                                  LLVMPassManagerRef PM) {
+void LLVMPassManagerBuilderPopulateFunctionPassManager(
+    LLVMPassManagerBuilderRef PMB, LLVMPassManagerRef PM) {
   PassManagerBuilder *Builder = unwrap(PMB);
   legacy::FunctionPassManager *FPM = unwrap<legacy::FunctionPassManager>(PM);
   Builder->populateFunctionPassManager(*FPM);
 }
 
-void
-LLVMPassManagerBuilderPopulateModulePassManager(LLVMPassManagerBuilderRef PMB,
-                                                LLVMPassManagerRef PM) {
+void LLVMPassManagerBuilderPopulateModulePassManager(
+    LLVMPassManagerBuilderRef PMB, LLVMPassManagerRef PM) {
   PassManagerBuilder *Builder = unwrap(PMB);
   legacy::PassManagerBase *MPM = unwrap(PM);
   Builder->populateModulePassManager(*MPM);
 }
 
 void LLVMPassManagerBuilderPopulateLTOPassManager(LLVMPassManagerBuilderRef PMB,
                                                   LLVMPassManagerRef PM,
                                                   LLVMBool Internalize,

lib/Transforms/Scalar/ADCE.cpp

-//===- ADCE.cpp - Code to perform dead code elimination -------------------===//
+//===- ACDCE.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.
+// 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.h"
-#include "llvm/ADT/DepthFirstIterator.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/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"
+#define DEBUG_MSG(x) DEBUG(dbgs() << x << '\n';)
+
+static cl::opt<bool> RemoveControlFlow("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 non-branch instructions removed");
+STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");
+
+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 {
+
+bool isUnconditional(TerminatorInst *Term) {
+  auto BR = dyn_cast<BranchInst>(Term);
+  return BR && BR->isUnconditional();
+}
+
+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;
+
+  /// reverse partial order of blocks with a collection of sources of backward
+  /// edges referred to as loop bottoms
+  PO_WithLoops PO;
+  PostDominatorTree *PDT; // Will be null when we retain control flow
+  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; }
 
-STATISTIC(NumRemoved, "Number of instructions removed");
+  /// initialize maps and BlockInfoVec
+  void initialize();
 
-static void collectLiveScopes(const DILocalScope &LS,
-                              SmallPtrSetImpl<const Metadata *> &AliveScopes) {
+  /// 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(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) : F(F), 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(if (PDT) 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_MSG("initializing block " << BB.getName());
+    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.
+  if (PDT) {
+    for (auto &BBInfo : BlockInfoVec) {
+      if (!BBInfo.isUnreachable() && !PDT->getNode(BBInfo.BB)) {
+        markLive(BBInfo.Terminator);
+        for (auto Pred : predecessors(BBInfo.BB)) {
+          DEBUG_MSG("no pdom pred live: " << Pred->getName());
+          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_MSG("loop bottom " << BB->getName());
+    markLive(BB->getTerminator());
+  }
+
+  for (auto &BBInfo : BlockInfoVec) {
+    BBInfo.TerminatorLiveInfo = &InstInfo[BBInfo.Terminator];
+    if (!BBInfo.isUnreachable() && !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);
+  }
+}
+
+// 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_MSG("unreachable " << BB.getName());
+    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_MSG("propagate live\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_MSG("unconditional from live pred " << Info->BB->getName());
+          Info->Live = true;
+          Info->TerminatorLiveInfo->Live = true;
+          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 (PDT && (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.
+  if (const DILocation *DL = I->getDebugLoc())
+    collectLiveScopes(*DL);
+
+  auto &BBInfo = *Info.Block;
+  if (BBInfo.Live) {
+    return;
+  }
+  DEBUG_MSG("mark block live: " << BBInfo.BB->getName());
+  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;
+  }
+}
+
+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()), AliveScopes);
+  collectLiveScopes(cast<DILocalScope>(*LS.getScope()));
 }
 
-static void collectLiveScopes(const DILocation &DL,
-                              SmallPtrSetImpl<const Metadata *> &AliveScopes) {
+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(), AliveScopes);
+  collectLiveScopes(*DL.getScope());
 
   // Tail-recurse through the inlined-at chain.
   if (const DILocation *IA = DL.getInlinedAt())
-    collectLiveScopes(*IA, AliveScopes);
+    collectLiveScopes(*IA);
 }
 
-// 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;
+// 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;
   }
 
-static bool aggressiveDCE(Function& F) {
-  SmallPtrSet<Instruction*, 32> Alive;
-  SmallVector<Instruction*, 128> Worklist;
+  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';
+    }
+  });
 
-  // 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);
-    }
-  }
+  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_MSG("live control in: " << BB->getName());
+    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. As a trivial example, the first branch should be marked as live
+// to distinguish which constant value is selected by the phi.
+
+// br i1 %1, label %2, label %3
+// ; <label>:2:                                      ; preds = %0
+// br label %4
+// ; <label>:3:                                      ; preds = %0
+// br label %4
+// ; <label>:4:                                      ; preds = %3, %2
+// %s.0 = phi i32 [ 0, %2 ], [ 1, %3 ]
+
+void AggressiveDCE::checkPhiNodes() {
+  RegionSetType LivePdoms;
+  auto FirstVisit = LastCurrentVisit;
+  for (auto DB : BlocksWithDeadTerminators) {
+    auto DBInfo = BlockInfo[DB];
+    if (DBInfo->RegionVisited > FirstVisit || DBInfo->terminatorIsLive()) {
+    }
+    ++LastCurrentVisit;
+    visitRegion(DBInfo, FirstVisit, LastCurrentVisit, &LivePdoms);
+  }
+  for (auto Succ : LivePdoms) {
+    DEBUG_MSG("checking Phi Nodes " << Succ->getName());
+    for (auto it = Succ->begin(); PHINode *PN = dyn_cast<PHINode>(it); ++it) {
+      if (isLive(PN)) {
+        checkPhiNode(PN, FirstVisit);
+      }
+    }
 
-  // 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();
+// 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_MSG("region visited " << CurrentVisit << " " << BBInfo->BB->getName());
+  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);
+    }
+  }
+}
 
-    // Collect the live debug info scopes attached to this instruction.
-    if (const DILocation *DL = Curr->getDebugLoc())
-      collectLiveScopes(*DL, AliveScopes);
+// 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_MSG("live for region " << Info.RegionVisited << " from "
+                                   << PredBB->getName());
+    }
+  }
+  for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+    auto PredBB = PN->getIncomingBlock(Idx);
+    auto PredInfo = BlockInfo[PredBB];
+    if (PredInfo->terminatorIsLive()) {
+      continue;
+    }
+    DEBUG_MSG("check pred " << PredInfo->RegionVisited << " "
+                            << PredBB->getName());
+    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);
+        BlocksWithDeadTerminators.erase(PredBB);
+      }
+    } else {
+      DeadValue = Value;
+    }
+  }
+}
 
-    for (Use &OI : Curr->operands()) {
-      if (Instruction *Inst = dyn_cast<Instruction>(OI))
-        if (Alive.insert(Inst).second)
-          Worklist.push_back(Inst);
+//===----------------------------------------------------------------------===//
+//
+//  Routines to update the CFG and SSA information before removing dead code
+//
+//===----------------------------------------------------------------------===//
+// A dead region i>s 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_MSG("live pdom " << Info.BB->getName() << " "
+                             << Info.LivePostDom->getName());
+    }
+  }
+  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_MSG("dead br in pred " << Info->BB->getName() << " reaches "
+                                     << Succ->getName());
+        SuccInfo.DeadRegion.LivePreds.insert(Info);
+        SuccInfo.DeadRegion.Trivial = false;
+        DeadRegions.insert(&SuccInfo);
+      }
+      continue;
+    }
+    auto LivePdom = Info->LivePostDom;
+    DEBUG_MSG("Dead block: " << Info->BB->getName() << " pdom "
+                             << LivePdom->getName());
+    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_MSG("   removing " << PredInfo->RegionVisited << " "
+                               << PredBB->getName());
+      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();
+  if (isUnconditional(PredTerm)) {
+    InstInfo[PredTerm].Live = true;
+    return;
+  }
+  DEBUG_MSG("making unconditional " << BB->getName());
+  auto NewTerm = BranchInst::Create(Target, PredTerm);
+  // 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_MSG("Trivial: " << DBInfo->BB->getName());
+    DBInfo->Live = true;
+    DBInfo->TerminatorLiveInfo->Live = true;
+  }
+}
+
+// the actual work of removing dead instructions and blocks
+void AggressiveDCE::removeDeadCode() {
+
+  assert(Worklist.empty() &&
+         "Expected empty work list when removing dead code");
+
+  // this update invalidates BlockInfoType::TerminatorLiveInfo fields
+  for (Instruction *I : NewBranches) {
+    InstInfo[I].Live = true;
+  }
+
   // 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()); });
+  DEBUG({
     for (Instruction &I : instructions(F)) {
-    // Check if the instruction is alive.
-    if (Alive.count(&I))
-      continue;
-
+      if (!isLive(&I)) {
         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))
+              if (isLive(II))
                 dbgs() << "Dropping debug info for " << *DII << "\n";
-      });
+        }
+        dbgs() << "dead: ";
+        I.dump();
+      }
+    }
+
+  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.
+        if (AliveScopes.count(DII->getDebugLoc()->getScope()))
+          continue;
+        // Fallthrough and drop the intrinsic.
       }
 
-    // Prepare to delete.
+      //      DEBUG(dbgs() << "dead: "; I.dump());
       Worklist.push_back(&I);
       I.dropAllReferences();
     }
+  }
 
-  for (Instruction *&I : Worklist) {
-    ++NumRemoved;
+  for (auto UB : UnreachableBlocks) {
+    DEBUG_MSG("removing unreachble " << UB->getName());
+    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_MSG("deleting block " << DB->BB->getName());
+      DB->BB->eraseFromParent();
+    }
+  }
+  auto LocalNumRemoved = Worklist.size();
+  DEBUG_MSG("Num removed " << LocalNumRemoved << "\n"
+                           << "Num branches removed "
+                           << LocalNumBranchesRemoved);
+  FuncNumInstRemoved += LocalNumRemoved;
+  FuncNumBranchesRemoved += LocalNumBranchesRemoved;
+  NumBranchesRemoved += FuncNumBranchesRemoved;
+  NumRemoved += FuncNumInstRemoved;
+}
 
-  return !Worklist.empty();
+//===----------------------------------------------------------------------===//
+//
+// 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';
+  };
 
-PreservedAnalyses ADCEPass::run(Function &F) {
-  if (!aggressiveDCE(F))
-    return PreservedAnalyses::all();
+  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
 
-  // 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;
+//===----------------------------------------------------------------------===//
+//
+// Pass Manager integration code
+//
+//===----------------------------------------------------------------------===//
+ADCEPass::ADCEPass(bool RetainControlFlow)
+    : RetainControlFlow(RetainControlFlow &&
+                        !(RemoveLoops || RemoveControlFlow)) {}
+
+PreservedAnalyses ADCEPass::run(Function &F, AnalysisManager<Function> &AM) {
+  PostDominatorTree *PDT = nullptr;
+  if (!RetainControlFlow)
+    PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
+  if (AggressiveDCE(F, PDT).doAggressiveCDCE())
+    return PreservedAnalyses::none();
+  return PreservedAnalyses::all();
 }
 
 namespace {
 struct ADCELegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
-  ADCELegacyPass() : FunctionPass(ID) {
+  bool RetainControlFlow;
+  ADCELegacyPass(bool RetainControlFlow = false)
+      : FunctionPass(ID),
+        RetainControlFlow(RetainControlFlow &&
+                          !(RemoveLoops || RemoveControlFlow)) {
     initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
-  bool runOnFunction(Function& F) override {
+  bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
-    return aggressiveDCE(F);
+    PostDominatorTree *PDT = nullptr;
+    if (!RetainControlFlow)
+      PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
+    return AggressiveDCE(F, PDT).doAggressiveCDCE();
   }
 
-  void getAnalysisUsage(AnalysisUsage& AU) const override {
-    AU.setPreservesCFG();
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    if (!RetainControlFlow)
+      AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 }
 
 char ADCELegacyPass::ID = 0;
-INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
+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() { return new ADCELegacyPass(); }
+FunctionPass *llvm::createAggressiveDCEPass(bool RetainControlFlow) {
+  return new ADCELegacyPass(RetainControlFlow);
+}

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());
+  bool RetainControlFlow = true;
+  unwrap(PM)->add(createAggressiveDCEPass(RetainControlFlow));
 }
 
 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 -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-control-flow -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-control-flow -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 -adce-remove-control-flow -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-control-flow -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 -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-control-flow -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 -adce-remove-control-flow -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-control-flow -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-control-flow -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-control-flow -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-control-flow -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 -adce-remove-control-flow -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-control-flow -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-control-flow -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-control-flow -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-control-flow -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-control-flow -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/debug-info-intrinsic.ll

 ; RUN: opt -adce -S < %s | FileCheck %s
-; Test that debug info intrinsics in dead scopes get eliminated by -adce.
+; RUN: opt -adce -adce-remove-control-flow -S < %s | FileCheck %s
+; Test that debug info intrinsics in dead scopes get eliminated by -adce and -adce -adce-remove-control-flow
 
 ; Generated with 'clang -g -S -emit-llvm | opt -mem2reg -inline' at r262899
 ; (before -adce was augmented) and then hand-reduced.  This was the input:
 ;
 ;;void sink(void);
 ;;
 ;;void variable_in_unused_subscope(void) {
 ;;  { int i = 0; }

test/Transforms/ADCE/delete-profiling-calls-to-constant.ll

 ; RUN: opt < %s -adce | FileCheck %s
 ; RUN: opt < %s -passes=adce | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-control-flow | FileCheck %s
+; RUN: opt < %s -passes=adce -adce-remove-control-flow | FileCheck %s
 
 ; Verify that a call to instrument a constant is deleted.
 
 @__profc_foo = private global [1 x i64] zeroinitializer, section "__llvm_prf_cnts", align 8
 @__profd_foo = private global { i64, i64, i64*, i8*, i8*, i32, [1 x i16] } { i64 6699318081062747564, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc_foo, i32 0, i32 0), i8* bitcast (i32 ()* @foo to i8*), i8* null, i32 1, [1 x i16] [i16 1] }, section "__llvm_prf_data", align 8
 
 define i32 @foo() {
 ; CHECK-NOT: __llvm_profile_instrument_target

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
 }