Index: lib/Transforms/Scalar/ADCE.cpp
===================================================================
--- lib/Transforms/Scalar/ADCE.cpp
+++ lib/Transforms/Scalar/ADCE.cpp
@@ -21,6 +21,8 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.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"
@@ -72,6 +74,7 @@
 
 class AggressiveDeadCodeElimination {
   Function &F;
+  PostDominatorTree &PDT;
 
   /// Mapping of blocks to associated information, an element in BlockInfoVec.
   DenseMap<BasicBlock *, BlockInfoType> BlockInfo;
@@ -121,7 +124,8 @@
   bool removeDeadInstructions();
 
 public:
-  AggressiveDeadCodeElimination(Function &F) : F(F) {}
+  AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT)
+      : F(F), PDT(PDT) {}
   bool performDeadCodeElimination();
 };
 }
@@ -254,9 +258,18 @@
     }
     markLiveBranchesFromControlDependences();
     // TODO -- handle PhiNodes
+    if (Worklist.empty()) {
+      // temporary until we can actually delete branches
+      SmallVector<TerminatorInst *, 16> DeadTerminators;
+      for (auto *BB : BlocksWithDeadTerminators)
+        DeadTerminators.push_back(BB->getTerminator());
+      for (auto *I : DeadTerminators)
+        markLive(I);
+      assert(BlocksWithDeadTerminators.empty());
+      // end temporary
+    }
   } while (!Worklist.empty());
 
-  // temporary until control dependences are implemented
   assert(BlocksWithDeadTerminators.empty());
 }
 
@@ -314,16 +327,36 @@
 
 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
 
-  // This is  a place holder, mark all read operations live
-  // The next patch will replace this with using iterated dominance
-  // frontier to compute branches that need to be live because they
-  // control live blocks with live operations
-  SmallVector<TerminatorInst *, 16> DeadTerminators;
-  for (auto *BB : BlocksWithDeadTerminators)
-    DeadTerminators.push_back(BB->getTerminator());
-  for (auto I : DeadTerminators)
-    markLive(I);
+  if (BlocksWithDeadTerminators.empty())
+    return;
+
+  DEBUG({
+    dbgs() << "new live blocks:\n";
+    for (auto *BB : NewLiveBlocks)
+      dbgs() << "\t" << BB->getName() << '\n';
+    dbgs() << "dead terminator blocks:\n";
+    for (auto *BB : BlocksWithDeadTerminators)
+      dbgs() << "\t" << BB->getName() << '\n';
+  });
+
+  // The dominance frontier of a live block X in the reverse
+  // control graph is the set of blocks upon which X is control
+  // dependent. The following sequence computes the set of blocks
+  // which currently have dead terminators that are control
+  // dependence sources of a block which is in NewLiveBlocks.
+  
+  SmallVector<BasicBlock *, 32> IDFBlocks;
+  ReverseIDFCalculator IDFs(PDT);
+  IDFs.setDefiningBlocks(NewLiveBlocks);
+  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
+  IDFs.calculate(IDFBlocks);
   NewLiveBlocks.clear();
+
+  // Dead terminators which control live blocks are now marked live.
+  for (auto BB : IDFBlocks) {
+    DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
+    markLive(BB->getTerminator());
+  }
 }
 
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
@@ -369,8 +402,14 @@
   return !Worklist.empty();
 }
 
-PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &) {
-  if (!AggressiveDeadCodeElimination(F).performDeadCodeElimination())
+//===----------------------------------------------------------------------===//
+//
+// Pass Manager integration code
+//
+//===----------------------------------------------------------------------===//
+PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
+  auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
+  if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
     return PreservedAnalyses::all();
 
   // FIXME: This should also 'preserve the CFG'.
@@ -389,18 +428,23 @@
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
-    return AggressiveDeadCodeElimination(F).performDeadCodeElimination();
+    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
+    return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesCFG();
+    AU.addRequired<PostDominatorTreeWrapperPass>();
+    AU.setPreservesCFG(); // TODO -- will remove when we start removing branches
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 }
 
 char ADCELegacyPass::ID = 0;
-INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
-                false, false)
+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(); }