Index: llvm/lib/Analysis/LazyValueInfo.cpp
===================================================================
--- llvm/lib/Analysis/LazyValueInfo.cpp
+++ llvm/lib/Analysis/LazyValueInfo.cpp
@@ -956,12 +956,6 @@
     BinaryOperator *BO, BasicBlock *BB) {
   assert(BO->getOperand(0)->getType()->isSized() &&
          "all operands to binary operators are sized");
-  if (BO->getOpcode() == Instruction::Xor) {
-    // Xor is the only operation not supported by ConstantRange::binaryOp().
-    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
-                      << "' - overdefined (unknown binary operator).\n");
-    return ValueLatticeElement::getOverdefined();
-  }
 
   if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
     unsigned NoWrapKind = 0;
Index: llvm/lib/IR/ConstantRange.cpp
===================================================================
--- llvm/lib/IR/ConstantRange.cpp
+++ llvm/lib/IR/ConstantRange.cpp
@@ -1412,6 +1412,37 @@
   if (isSingleElement() && getSingleElement()->isAllOnes())
     return Other.binaryNot();
 
+  if (isFullSet() || Other.isFullSet())
+    return getFull();
+  // Get the upper bits that don't change between the Upper and Lower bound for
+  // both ConstantRanges. If we xor these bits together, we can produce
+  // a resulting ConstantRange. This does not work if the Upper and Lower
+  // bound are different signages, because that means it does not have
+  // any upper common bits.
+  // E.G 0111 0111 < x < 0110 0011
+  // Common upper bits = 011? ????
+  // Known ones        = 0110 0000
+  // Known zeros       = 1000 0000
+  const APInt Min = getSignedMin();
+  const APInt Max = getSignedMax();
+  const APInt OtherMin = Other.getSignedMin();
+  const APInt OtherMax = Other.getSignedMax();
+  if (Min.isNegative() == Max.isNegative() &&
+      OtherMin.isNegative() == OtherMax.isNegative()) {
+    APInt DiffBitsA = Min ^ Max;
+    APInt DiffBitsB = OtherMin ^ OtherMax;
+    unsigned CommonUpperBitsMin =
+        std::min(DiffBitsA.countLeadingZeros(), DiffBitsB.countLeadingZeros());
+    APInt CommonUpperBitsMask =
+        APInt(getBitWidth(), -1).lshr(CommonUpperBitsMin);
+    CommonUpperBitsMask.flipAllBits();
+
+    KnownBits Known;
+    Known.One = (Min ^ OtherMin) & CommonUpperBitsMask;
+    Known.Zero = ~Known.One & CommonUpperBitsMask;
+    return fromKnownBits(Known, /*IsSigned*/ false);
+  }
+
   // TODO: replace this with something less conservative
   return getFull();
 }
Index: llvm/test/Transforms/CorrelatedValuePropagation/xor.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/CorrelatedValuePropagation/xor.ll
@@ -0,0 +1,119 @@
+; RUN: opt -correlated-propagation -S %s -debug 2>&1 | FileCheck %s
+
+; CHECK-LABEL: @vrp_xor1
+; CHECK: br i1 false
+; 64 < x < 113
+; 75 < y < 120
+; x^y cannot be > 127
+define void @vrp_xor1(i32 %x, i32 %y) {
+entry:
+  %cmpx.0 = icmp sgt i32 %x, 65
+  %cmpx.1 = icmp slt i32 %x, 113
+  %cmpx = and i1 %cmpx.0, %cmpx.1
+  %cmpy.0 = icmp sgt i32 %y, 75
+  %cmpy.1 = icmp slt i32 %y, 120
+  %cmpy = and i1 %cmpy.0, %cmpy.1
+  %cmp = and i1 %cmpx, %cmpy
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %xor = xor i32 %x, %y
+  %eq = icmp eq i32 %xor, 128
+  br i1 %eq, label %if.then5, label %if.else
+
+if.then5:                                         ; preds = %if.then, %if.then, %if.then
+  call void @error()
+  ret void
+
+if.else:                                          ; preds = %entry
+  ret void
+}
+
+; CHECK-LABEL: @vrp_xor2
+; CHECK: br i1 %eq
+; 64 < x < 113
+; 75 < y < 120
+; x^y can be 16
+; E.g x = 97, y = 113, x ^ y = 16
+define void @vrp_xor2(i32 %x, i32 %y) {
+entry:
+  %cmpx.0 = icmp sgt i32 %x, 65
+  %cmpx.1 = icmp slt i32 %x, 113
+  %cmpx = and i1 %cmpx.0, %cmpx.1
+  %cmpy.0 = icmp sgt i32 %y, 75
+  %cmpy.1 = icmp slt i32 %y, 120
+  %cmpy = and i1 %cmpy.0, %cmpy.1
+  %cmp = and i1 %cmpx, %cmpy
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %xor = xor i32 %x, %y
+  %eq = icmp eq i32 %xor, 16
+  br i1 %eq, label %if.then5, label %if.else
+
+if.then5:                                         ; preds = %if.then, %if.then, %if.then
+  call void @error()
+  ret void
+
+if.else:                                          ; preds = %entry
+  ret void
+}
+
+; CHECK-LABEL: @vrp_xor3
+; CHECK: br i1 false
+; -113 < x < -64
+; -120 < y < -75
+; x^y cannot be -128
+define void @vrp_xor3(i32 %x, i32 %y) {
+entry:
+  %cmpx.0 = icmp slt i32 %x, -65
+  %cmpx.1 = icmp sgt i32 %x, -113
+  %cmpx = and i1 %cmpx.0, %cmpx.1
+  %cmpy.0 = icmp slt i32 %y, -75
+  %cmpy.1 = icmp sgt i32 %y, -120
+  %cmpy = and i1 %cmpy.0, %cmpy.1
+  %cmp = and i1 %cmpx, %cmpy
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %xor = xor i32 %x, %y
+  %eq = icmp eq i32 %xor, -128
+  br i1 %eq, label %if.then5, label %if.else
+
+if.then5:                                         ; preds = %if.then, %if.then, %if.then
+  call void @error()
+  ret void
+
+if.else:                                          ; preds = %entry
+  ret void
+}
+
+; CHECK-LABEL: @vrp_xor4
+; CHECK: br i1 %eq
+; -113 < x < -64
+; -120 < y < -75
+; x^y can be 1
+define void @vrp_xor4(i32 %x, i32 %y) {
+entry:
+  %cmpx.0 = icmp slt i32 %x, -65
+  %cmpx.1 = icmp sgt i32 %x, -113
+  %cmpx = and i1 %cmpx.0, %cmpx.1
+  %cmpy.0 = icmp slt i32 %y, -75
+  %cmpy.1 = icmp sgt i32 %y, -120
+  %cmpy = and i1 %cmpy.0, %cmpy.1
+  %cmp = and i1 %cmpx, %cmpy
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %xor = xor i32 %x, %y
+  %eq = icmp eq i32 %xor, 1
+  br i1 %eq, label %if.then5, label %if.else
+
+if.then5:                                         ; preds = %if.then, %if.then, %if.then
+  call void @error()
+  ret void
+
+if.else:                                          ; preds = %entry
+  ret void
+}
+declare void @error()
Index: llvm/unittests/IR/ConstantRangeTest.cpp
===================================================================
--- llvm/unittests/IR/ConstantRangeTest.cpp
+++ llvm/unittests/IR/ConstantRangeTest.cpp
@@ -2520,9 +2520,15 @@
   // Ranges with more than a single element. Handled conservatively for now.
   ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
   ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
-  EXPECT_TRUE(R16_35.binaryXor(R16_35).isFullSet());
-  EXPECT_TRUE(R16_35.binaryXor(R0_99).isFullSet());
-  EXPECT_TRUE(R0_99.binaryXor(R16_35).isFullSet());
+  KnownBits Known(8);
+  Known.Zero = -64;
+  Known.One = 0;
+  EXPECT_EQ(R16_35.binaryXor(R16_35),
+            ConstantRange::fromKnownBits(Known, true));
+  Known.Zero = 128;
+  Known.One = 0;
+  EXPECT_EQ(R16_35.binaryXor(R0_99), ConstantRange::fromKnownBits(Known, true));
+  EXPECT_EQ(R0_99.binaryXor(R16_35), ConstantRange::fromKnownBits(Known, true));
 }
 
 TEST_F(ConstantRangeTest, binaryNot) {