Index: lib/Transforms/Scalar/ADCE.cpp
===================================================================
--- lib/Transforms/Scalar/ADCE.cpp
+++ lib/Transforms/Scalar/ADCE.cpp
@@ -109,6 +109,13 @@
   void markLiveInstructions();
   /// Mark an instruction as live.
   void markLive(Instruction *I);
+  /// Mark reaching defintions and possibly reaching blocks live for a PHINode.
+  void markPhiReachingDefs(PHINode *PN);
+
+  /// Verify that a live phi node that has inputs in blocks with
+  /// dead terminators has a unique reaching definition from all such blocks.
+  void markLivePhiNodeInputs();
+  void markLivePhiNodeInputs(BasicBlock *BB);
 
   /// Record the Debug Scopes which surround live debug information.
   void collectLiveScopes(const DILocalScope &LS);
@@ -264,23 +271,38 @@
 void AggressiveDeadCodeElimination::markLiveInstructions() {
 
   // Propagate liveness backwards to operands.
+  bool PhiNodeInputsChecked = false;
   do {
     // Worklist holds newly discovered live instructions
     // where we need to mark the inputs as live.
     while (!Worklist.empty()) {
       Instruction *LiveInst = Worklist.pop_back_val();
+      DEBUG(dbgs() << "work live: "; LiveInst->dump(););
 
       // Collect the live debug info scopes attached to this instruction.
       if (const DILocation *DL = LiveInst->getDebugLoc())
         collectLiveScopes(*DL);
 
-      DEBUG(dbgs() << "work live: "; LiveInst->dump(););
+      if (auto *PN = dyn_cast<PHINode>(LiveInst)) {
+        markPhiReachingDefs(PN);
+        continue;
+      }
+
       for (Use &OI : LiveInst->operands())
         if (Instruction *Inst = dyn_cast<Instruction>(OI))
           markLive(Inst);
     }
     markLiveBranchesFromControlDependences();
 
+    // After we have incorporated all data and control flow effects, make
+    // a scan of phi nodes to make sure there are no situations where the
+    // effects of a branch are realized only in different reaching values
+    // at a live phi node.
+    if (Worklist.empty() && !PhiNodeInputsChecked) {
+      PhiNodeInputsChecked = true;
+      markLivePhiNodeInputs();
+    }
+
     if (Worklist.empty()) {
       // Temporary until we can actually delete branches.
       SmallVector<TerminatorInst *, 16> DeadTerminators;
@@ -296,6 +318,24 @@
   assert(BlocksWithDeadTerminators.empty());
 }
 
+void AggressiveDeadCodeElimination::markPhiReachingDefs(PHINode *PN) {
+
+  // For each reaching definition, if it is an instruction, mark it live.
+  // Otherwise, mark the terminator of the associated block live so we preserve
+  // the control flow associated with this value.
+  auto NumIdx = PN->getNumIncomingValues();
+  for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+    auto *Value = PN->getIncomingValue(Idx);
+    if (auto *ReachingDef = dyn_cast<Instruction>(Value)) {
+      markLive(ReachingDef);
+      continue;
+    }
+    auto *PredTerm = PN->getIncomingBlock(Idx)->getTerminator();
+    DEBUG(dbgs() << "constant phi live: "; PredTerm->dump(););
+    markLive(PredTerm);
+  }
+}
+
 void AggressiveDeadCodeElimination::markLive(Instruction *I) {
 
   auto &Info = InstInfo[I];
@@ -382,6 +422,56 @@
   }
 }
 
+void AggressiveDeadCodeElimination::markLivePhiNodeInputs() {
+  SmallPtrSet<BasicBlock *, 16> LiveJoinBlocks;
+
+  // Find all successors of blocks with dead terminators
+  // and mark the live phi nodes in them.
+  SmallVector<BasicBlock *, 16> Elements(BlocksWithDeadTerminators.begin(),
+                                         BlocksWithDeadTerminators.end());
+  for (auto *BB : Elements)
+    for (auto *SuccBB : successors(BB))
+      if (LiveJoinBlocks.insert(SuccBB).second)
+        markLivePhiNodeInputs(SuccBB);
+}
+
+void AggressiveDeadCodeElimination::markLivePhiNodeInputs(BasicBlock *BB) {
+  auto &Info = BlockInfo[BB];
+  if (!Info.Live)
+    return;
+  // Iterate over all live PHINodes.
+  for (auto it = BB->begin(); auto *PN = dyn_cast<PHINode>(it); ++it) {
+    if (!isLive(PN))
+      continue;
+
+    // Verify a common reaching definition from predecessors with
+    // dead terminators, marking some live to enforce this.
+    Value *CommonReachngDefintion = nullptr;
+    auto NumIdx = PN->getNumIncomingValues();
+    for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+      auto PredTerm = PN->getIncomingBlock(Idx)->getTerminator();
+      if (isLive(PredTerm))
+        continue;
+      auto *Value = PN->getIncomingValue(Idx);
+      if (!CommonReachngDefintion) {
+        CommonReachngDefintion = Value;
+        continue;
+      }
+      if (CommonReachngDefintion != Value) {
+        // When there are two definitions from "dead" predecessor paths we
+        // preserve one of those paths so the two values can be distinguished.
+        DEBUG(dbgs() << "Live due to phi conflict "; PredTerm->dump());
+        markLive(PredTerm);
+      }
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+//
+//  Routines to update the CFG and SSA information before removing dead code.
+//
+//===----------------------------------------------------------------------===//
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
 
   // The inverse of the live set is the dead set.  These are those instructions