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(BO)) { unsigned NoWrapKind = 0; Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -1412,8 +1412,32 @@ if (isSingleElement() && getSingleElement()->isAllOnes()) return Other.binaryNot(); - // TODO: replace this with something less conservative - return getFull(); + 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 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 | 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 @@ -2517,12 +2517,27 @@ 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) {