Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -634,8 +634,7 @@
     if (auto *CI = dyn_cast<CastInst>(BBI))
       return solveBlockValueCast(Res, CI, BB);
 
-    BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
-    if (BO && isa<ConstantInt>(BO->getOperand(1)))
+    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
       return solveBlockValueBinaryOp(Res, BO, BB);
   }
 
@@ -1056,8 +1055,20 @@
       LHSRange = LHSVal.getConstantRange();
   }
 
-  ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
-  ConstantRange RHSRange = ConstantRange(RHS->getValue());
+  // Same for RHS.
+  if (!hasBlockValue(BO->getOperand(1), BB))
+    if (pushBlockValue(std::make_pair(BB, BO->getOperand(1))))
+      // More work to do before applying this transfer rule.
+      return false;
+
+  ConstantRange RHSRange = ConstantRange(OperandBitWidth);
+  if (hasBlockValue(BO->getOperand(1), BB)) {
+    ValueLatticeElement RHSVal = getBlockValue(BO->getOperand(1), BB);
+    intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(1), RHSVal,
+                                                  BO);
+    if (RHSVal.isConstantRange())
+      RHSRange = RHSVal.getConstantRange();
+  }
 
   // NOTE: We're currently limited by the set of operations that ConstantRange
   // can evaluate symbolically.  Enhancing that set will allows us to analyze
Index: test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
===================================================================
--- test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
+++ test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll
@@ -72,7 +72,7 @@
   %cnd1 = icmp sge i32 %iv, 0
   %cnd2 = icmp sgt i32 %iv2, 0
 ; CHECK:       %cnd2 = icmp sgt i32 %iv2, 0
-; CHECK:         ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: overdefined
+; CHECK:         ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: constantrange<-1, -1>
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%backedge' is: constantrange<-1, 0>
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%exit' is: overdefined
 ; CHECK-NEXT:  %cnd = and i1 %cnd1, %cnd2
@@ -92,7 +92,7 @@
 ; CHECK-NEXT:    ; LatticeVal for: '  %cont2 = icmp sgt i32 %iv2.next, 0' in BB: '%backedge' is: overdefined
 ; CHECK-NEXT:  %cont2 = icmp sgt i32 %iv2.next, 0
   %cont2 = icmp sgt i32 %iv2.next, 0
-; CHECK-NEXT:    ; LatticeVal for: '  %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:    ; LatticeVal for: '  %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: constantrange<-1, -1>
 ; CHECK-NEXT:  %cont = and i1 %cont1, %cont2
   %cont = and i1 %cont1, %cont2
   br i1 %cont, label %loop, label %exit
Index: test/Transforms/CorrelatedValuePropagation/icmp.ll
===================================================================
--- test/Transforms/CorrelatedValuePropagation/icmp.ll
+++ test/Transforms/CorrelatedValuePropagation/icmp.ll
@@ -61,4 +61,104 @@
   unreachable
 }
 
+; Make sure binary operator transfer functions are run when RHS is non-constant
+; CHECK-LABEL: @test3
+define i1 @test3(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %add = add i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %add, 25
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Same as previous but make sure nobody gets over-zealous
+; CHECK-LABEL: @test4
+define i1 @test4(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %add = add i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %add, 15
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure binary operator transfer functions are run when RHS is non-constant
+; CHECK-LABEL: @test5
+define i1 @test5(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 5
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 5
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %shifted = shl i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %shifted, 65536
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Same as previous but make sure nobody gets over-zealous
+; CHECK-LABEL: @test6
+define i1 @test6(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 5
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 15
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %shifted = shl i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %shifted, 65536
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
 attributes #4 = { noreturn }