Index: include/llvm/IR/CFGDeadness.h
===================================================================
--- include/llvm/IR/CFGDeadness.h
+++ include/llvm/IR/CFGDeadness.h
@@ -39,9 +39,9 @@
     return PU.getUser()->getOperandUse(PU.getOperandNo());
   }
 
-  /// Return the edge that corresponds to the basic block listed in the phi
-  /// node.
-  static const Use* getIncomingEdge(const PHINode *PN, const BasicBlock *InBB);
+  /// Return true if there is at least one live edge that corresponds to the
+  /// basic block InBB listed in the phi node.
+  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const;
 
   bool isDeadBlock(const BasicBlock *BB) const {
     return DeadBlocks.count(BB);
@@ -63,7 +63,6 @@
 protected:
   void addDeadBlock(const BasicBlock *BB);
   void addDeadEdge(const Use &DeadEdge);
-  void processInstruction(const Instruction *I);
 };
 
 /// Analysis pass which computes a \c CFGDeadness.
Index: lib/IR/CFGDeadness.cpp
===================================================================
--- lib/IR/CFGDeadness.cpp
+++ lib/IR/CFGDeadness.cpp
@@ -83,24 +83,6 @@
   addDeadBlock(BB);
 }
 
-void CFGDeadness::processInstruction(const Instruction *I) {
-  // For conditional branches, we can perform simple conditional propagation on
-  // the condition value itself.
-  const BranchInst *BI = dyn_cast<BranchInst>(I);
-  if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
-      return;
-
-  // If a branch has two identical successors, we cannot declare either dead.
-  if (BI->getSuccessor(0) == BI->getSuccessor(1))
-    return;
-
-  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
-  if (!Cond)
-    return;
-
-  addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
-}
-
 void CFGDeadness::processFunction(const Function &F, const DominatorTree &DT) {
   this->DT = &DT;
 
@@ -111,29 +93,42 @@
 
   // Top-down walk of the dominator tree
   ReversePostOrderTraversal<const Function *> RPOT(&F);
-  for (const BasicBlock *BB : RPOT)
-    for (auto &BI : *BB)
-      processInstruction(&BI);
+  for (const BasicBlock *BB : RPOT) {
+    const TerminatorInst *TI = BB->getTerminator();
+    assert(TI && "blocks must be well formed");
+
+    // For conditional branches, we can perform simple conditional propagation on
+    // the condition value itself.
+    const BranchInst *BI = dyn_cast<BranchInst>(TI);
+    if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
+      continue;
+
+    // If a branch has two identical successors, we cannot declare either dead.
+    if (BI->getSuccessor(0) == BI->getSuccessor(1))
+      continue;
+
+    ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
+    if (!Cond)
+      continue;
+
+    addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
+  }
 }
 
-const Use* CFGDeadness::getIncomingEdge(const PHINode *PN,
-                                        const BasicBlock *InBB) {
+bool CFGDeadness::hasLiveIncomingEdge(const PHINode *PN,
+                                      const BasicBlock *InBB) const {
+  assert(!isDeadBlock(InBB) && "block must be live");
   const BasicBlock* BB = PN->getParent();
-  const Use* result = nullptr;
+  bool Listed = false;
   for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
     if (InBB == *PredIt) {
-      auto &PU = PredIt.getUse();
-      const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
-      assert(!result &&
-             "Phi is not expected to refer to one block several times");
-      result = &U;
-#ifdef NDEBUG
-      break;
-#endif
+      if (!isDeadEdge(&getEdge(PredIt)))
+        return true;
+      Listed = true;
     }
   }
-  assert(result && "Cannot find incoming edge from block.");
-  return result;
+  assert(Listed && "basic block is not found among incoming blocks");
+  return false;
 }
 
 //===----------------------------------------------------------------------===//
@@ -157,10 +152,10 @@
 char CFGDeadnessWrapperPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(CFGDeadnessWrapperPass, "cfgdeadness",
-                      "CFG Deadness", true, true)
+                      "CFG Deadness", false, true)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(CFGDeadnessWrapperPass, "cfgdeadness",
-                      "CFG Deadness", true, true)
+                      "CFG Deadness", false, true)
 
 bool CFGDeadnessWrapperPass::runOnFunction(Function &F) {
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Index: lib/IR/SafepointIRVerifier.cpp
===================================================================
--- lib/IR/SafepointIRVerifier.cpp
+++ lib/IR/SafepointIRVerifier.cpp
@@ -312,8 +312,8 @@
   GCPtrTracker(const Function &F, const DominatorTree &DT,
                const CFGDeadness &CD);
 
-  bool isDeadEdge(const Use* E) const {
-    return CD.isDeadEdge(E);
+  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
+    return CD.hasLiveIncomingEdge(PN, InBB);
   }
 
   BasicBlockState *getBasicBlockState(const BasicBlock *BB);
@@ -477,7 +477,7 @@
     for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
       const BasicBlock *PBB = *PredIt;
       BasicBlockState *PBBS = getBasicBlockState(PBB);
-      if (PBBS && !isDeadEdge(&CFGDeadness::getEdge(PredIt)))
+      if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
         set_intersect(BBS->AvailableIn, PBBS->AvailableOut);
     }
 
@@ -519,7 +519,7 @@
         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
           const BasicBlock *InBB = PN->getIncomingBlock(i);
           if (!isMapped(InBB) ||
-              isDeadEdge(CFGDeadness::getIncomingEdge(PN, InBB)))
+              !CD.hasLiveIncomingEdge(PN, InBB))
             continue; // Skip dead block or dead edge.
 
           const Value *InValue = PN->getIncomingValue(i);
@@ -653,7 +653,7 @@
         const BasicBlock *InBB = PN->getIncomingBlock(i);
         const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);
         if (!InBBS ||
-            Tracker->isDeadEdge(CFGDeadness::getIncomingEdge(PN, InBB)))
+            !Tracker->hasLiveIncomingEdge(PN, InBB))
           continue; // Skip dead block or dead edge.
 
         const Value *InValue = PN->getIncomingValue(i);