Index: lib/Transforms/Scalar/ADCE.cpp
===================================================================
--- lib/Transforms/Scalar/ADCE.cpp
+++ lib/Transforms/Scalar/ADCE.cpp
@@ -110,6 +110,16 @@
   /// Mark an instruction as live.
   void markLive(Instruction *I);
 
+  /// A PHI node records values associated with different paths in the
+  /// control flow graph as if a logical copy operation was performed from
+  /// an input value to the named value of the PHI node. Here we identify
+  /// where multiple distinct values reach a live PHI node from otherwise
+  /// dead predecessors. We force some predecessors terminators to be live
+  /// effectively live so that the control which determines the final values
+  /// is preserved.
+  void markLivePhiNodeInputs();
+  void markLivePhiNodeInputs(BasicBlock *BB);
+
   /// Record the Debug Scopes which surround live debug information.
   void collectLiveScopes(const DILocalScope &LS);
   void collectLiveScopes(const DILocation &DL);
@@ -264,23 +274,33 @@
 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(););
       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;
@@ -382,6 +402,79 @@
   }
 }
 
+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;
+
+    // A PHI node has implicit assignments along the control flow edges from
+    // predecessors and these implicit assignments may induce a control
+    // dependences that is not visible in the data flow.
+    
+    // As an example:
+    
+    // %tobool = icmp ne i32 %a, 0
+    // br i1 %tobool, label %cond.true, label %cond.false
+    //
+    // cond.true:                           ; preds = %entry
+    // br label %cond.end
+    //
+    // cond.false:                          ; preds = %entry
+    // br label %cond.end
+    //
+    // cond.end:                            ; preds = %cond.false, %cond.true
+    // %cond = phi i32 [ %b, %cond.true ], [ %c, %cond.false ]
+    
+    // In tis example, there are no live instructions determined by the
+    // first branch but it does determine the value which is assigned into
+    // %cond as if there were copy operations in the two empty blocks.
+    // We detected the multiple distinct values from dead predecessors and
+    // force some predecessors live (such as "br label %end" in block
+    // "cond.false") to correctly model the control dependence.
+    
+    Value *CommonReachngDefinition = 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 (!CommonReachngDefinition) {
+        CommonReachngDefinition = Value;
+        continue;
+      }
+      if (CommonReachngDefinition != 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