[ConstantRange] Construct constant range from xor operation

[Joe]

Summary

Retains information when two constant ranges are xor'd together. This is
only possible if both constant ranges do not range over signage.

[Joe]

Fix malformed diff.

[nikic]

llvm/lib/IR/ConstantRange.cpp

1428

I don't understand how signedness is relevant here. Can't you use Lower and Upper-1 here, independent of signedness?

llvm/unittests/IR/ConstantRangeTest.cpp

2531

Please add an exhaustive correctness test.

[Joe]

Add exhaustive correctness test.
Also remove signage test in binaryXor, as the common bits would be 0 anyway, thus creating a full set regardless.

llvm/lib/IR/ConstantRange.cpp

1428

The call to getSignedMin/Max includes a check of isFullSet and isUpperSignWrapped, which is relevant here, otherwise Upper-1 would not work.

[Joe]

Ping

[Joe]

Ping

llvm/lib/Analysis/LazyValueInfo.cpp

Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
   const ConstantRange &RHSRange = RHSRes.getValue();
   return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
 }
 
 Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp(
     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;
     if (OBO->hasNoUnsignedWrap())
       NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
     if (OBO->hasNoSignedWrap())
       NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap;
 

llvm/lib/IR/ConstantRange.cpp

if (isSingleElement() && Other.isSingleElement())
     return {*getSingleElement() ^ *Other.getSingleElement()};
 
   // Special-case binary complement, since we can give a precise answer.
   if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
     return binaryNot();
   if (isSingleElement() && getSingleElement()->isAllOnes())
     return Other.binaryNot();
 
-  // TODO: replace this with something less conservative
+  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();
+  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);
 }
 
 ConstantRange
 ConstantRange::shl(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 
   APInt Min = getUnsignedMin();

llvm/test/Transforms/CorrelatedValuePropagation/xor.ll

+; RUN: opt -correlated-propagation -S %s | 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()

llvm/unittests/IR/ConstantRangeTest.cpp

 
 TEST_F(ConstantRangeTest, binaryXor) {
   // Single element ranges.
   ConstantRange R16(APInt(8, 16));
   ConstantRange R20(APInt(8, 20));
   EXPECT_EQ(*R16.binaryXor(R16).getSingleElement(), APInt(8, 0));
   EXPECT_EQ(*R16.binaryXor(R20).getSingleElement(), APInt(8, 16 ^ 20));
 
-  // Ranges with more than a single element. Handled conservatively for now.
+  // Ranges with more than a single element.
   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));
+
+  TestBinaryOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.binaryXor(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) { return N1 ^ N2; }, PreferSmallest,
+      [](const ConstantRange &, const ConstantRange &) {
+        return false; // Check correctness only.
+      });
 }
 
 TEST_F(ConstantRangeTest, binaryNot) {
   TestUnaryOpExhaustive(
       [](const ConstantRange &CR) { return CR.binaryNot(); },
       [](const APInt &N) { return ~N; },
       PreferSmallest);
   TestUnaryOpExhaustive(