Index: llvm/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/lib/Analysis/LazyValueInfo.cpp +++ llvm/lib/Analysis/LazyValueInfo.cpp @@ -956,33 +956,27 @@ 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; if (OBO->hasNoUnsignedWrap()) NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap; if (OBO->hasNoSignedWrap()) NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap; return solveBlockValueBinaryOpImpl( BO, BB, [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind); }); } return solveBlockValueBinaryOpImpl( BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.binaryOp(BO->getOpcode(), CR2); }); } Optional LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB) { Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -1412,59 +1412,89 @@ 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(); } ConstantRange ConstantRange::shl(const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) return getEmpty(); APInt Min = getUnsignedMin(); APInt Max = getUnsignedMax(); if (const APInt *RHS = Other.getSingleElement()) { unsigned BW = getBitWidth(); if (RHS->uge(BW)) return getEmpty(); unsigned EqualLeadingBits = (Min ^ Max).countLeadingZeros(); if (RHS->ule(EqualLeadingBits)) return getNonEmpty(Min << *RHS, (Max << *RHS) + 1); return getNonEmpty(APInt::getZero(BW), APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1); } APInt OtherMax = Other.getUnsignedMax(); // There's overflow! if (OtherMax.ugt(Max.countLeadingZeros())) return getFull(); // FIXME: implement the other tricky cases Min <<= Other.getUnsignedMin(); Max <<= OtherMax; return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1); } ConstantRange ConstantRange::lshr(const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) return getEmpty(); APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1; APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); return getNonEmpty(std::move(min), std::move(max)); } ConstantRange ConstantRange::ashr(const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) return getEmpty(); // May straddle zero, so handle both positive and negative cases. // 'PosMax' is the upper bound of the result of the ashr // operation, when Upper of the LHS of ashr is a non-negative. 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,11 +2520,19 @@ // 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) { TestUnaryOpExhaustive( [](const ConstantRange &CR) { return CR.binaryNot(); },