Index: llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -14,6 +14,7 @@
 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
@@ -120,8 +121,8 @@
   return true;
 }
 
-static bool processPHI(PHINode *P, LazyValueInfo *LVI,
-                       const SimplifyQuery &SQ) {
+static bool processPHI(PHINode *P, LazyValueInfo *LVI, const SimplifyQuery &SQ,
+                       DenseSet<BasicBlock *> &ReachableBlocks) {
   bool Changed = false;
 
   BasicBlock *BB = P->getParent();
@@ -129,7 +130,18 @@
     Value *Incoming = P->getIncomingValue(i);
     if (isa<Constant>(Incoming)) continue;
 
-    Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
+    // If the incoming value is coming from an unreachable block, replace
+    // it with undef and go on. This is good for two reasons:
+    // 1) We skip an LVI query for an unreachable block
+    // 2) We transform the incoming value so that the code below doesn't
+    //    mess around with IR in unreachable blocks.
+    BasicBlock *IncomingBB = P->getIncomingBlock(i);
+    if (!ReachableBlocks.count(IncomingBB)) {
+      P->setIncomingValue(i, UndefValue::get(P->getType()));
+      continue;
+    }
+
+    Value *V = LVI->getConstantOnEdge(Incoming, IncomingBB, BB, P);
 
     // Look if the incoming value is a select with a scalar condition for which
     // LVI can tells us the value. In that case replace the incoming value with
@@ -561,6 +573,14 @@
 
 static bool runImpl(Function &F, LazyValueInfo *LVI, const SimplifyQuery &SQ) {
   bool FnChanged = false;
+
+  // Compute reachability from the entry block of this function via an RPO
+  // walk. We use this information when processing PHIs.
+  DenseSet<BasicBlock *> ReachableBlocks;
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  for (BasicBlock *BB : RPOT)
+    ReachableBlocks.insert(BB);
+
   // Visiting in a pre-order depth-first traversal causes us to simplify early
   // blocks before querying later blocks (which require us to analyze early
   // blocks).  Eagerly simplifying shallow blocks means there is strictly less
@@ -575,7 +595,7 @@
         BBChanged |= processSelect(cast<SelectInst>(II), LVI);
         break;
       case Instruction::PHI:
-        BBChanged |= processPHI(cast<PHINode>(II), LVI, SQ);
+        BBChanged |= processPHI(cast<PHINode>(II), LVI, SQ, ReachableBlocks);
         break;
       case Instruction::ICmp:
       case Instruction::FCmp:
Index: llvm/trunk/test/Transforms/CorrelatedValuePropagation/pr35807.ll
===================================================================
--- llvm/trunk/test/Transforms/CorrelatedValuePropagation/pr35807.ll
+++ llvm/trunk/test/Transforms/CorrelatedValuePropagation/pr35807.ll
@@ -0,0 +1,65 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -correlated-propagation -S %s | FileCheck %s
+
+target triple = "x86_64-apple-darwin17.4.0"
+
+define void @patatino() {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:    br i1 undef, label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 undef, label [[BB40:%.*]], label [[BB22:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB14:%.*]]
+; CHECK:       bb12:
+; CHECK-NEXT:    br label [[BB14]]
+; CHECK:       bb14:
+; CHECK-NEXT:    [[TMP19:%.*]] = icmp sgt i32 undef, undef
+; CHECK-NEXT:    [[TMP20:%.*]] = select i1 [[TMP19]], i64 [[TMP20]], i64 0
+; CHECK-NEXT:    br i1 undef, label [[BB40]], label [[BB7:%.*]]
+; CHECK:       bb22:
+; CHECK-NEXT:    br label [[BB24:%.*]]
+; CHECK:       bb24:
+; CHECK-NEXT:    br label [[BB32:%.*]]
+; CHECK:       bb32:
+; CHECK-NEXT:    br i1 undef, label [[BB40]], label [[BB24]]
+; CHECK:       bb40:
+; CHECK-NEXT:    ret void
+;
+  br i1 undef, label %bb3, label %bb4
+
+bb3:
+  br label %bb3
+
+bb4:
+  br i1 undef, label %bb40, label %bb22
+
+bb7:
+  br label %bb14
+
+bb12:
+  br label %bb14
+
+; This block is unreachable. Due to the non-standard definition of
+; dominance in LLVM where uses in unreachable blocks are dominated
+; by anything, it contains an instruction of the form
+; %def = OP %def, %something
+bb14:
+  %tmp19 = icmp sgt i32 undef, undef
+  %tmp20 = select i1 %tmp19, i64 %tmp20, i64 0
+  br i1 undef, label %bb40, label %bb7
+
+bb22:
+  br label %bb24
+
+bb24:
+  br label %bb32
+
+bb32:
+  br i1 undef, label %bb40, label %bb24
+
+bb40:
+  %tmp41 = phi i64 [ 4, %bb4 ], [ %tmp20, %bb14 ], [ undef, %bb32 ]
+  ret void
+}