diff options
| -rw-r--r-- | llvm/lib/Analysis/ValueTracking.cpp | 28 | ||||
| -rw-r--r-- | llvm/test/Analysis/ValueTracking/known-signbit-shift.ll | 55 |
2 files changed, 78 insertions, 5 deletions
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 7f62a2685f4..e3ac4bb7831 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -795,6 +795,14 @@ static void computeKnownBitsFromShiftOperator( computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q); KnownZero = KZF(KnownZero, ShiftAmt); KnownOne = KOF(KnownOne, ShiftAmt); + // If there is conflict between KnownZero and KnownOne, this must be an + // overflowing left shift, so the shift result is undefined. Clear KnownZero + // and KnownOne bits so that other code could propagate this undef. + if ((KnownZero & KnownOne) != 0) { + KnownZero.clearAllBits(); + KnownOne.clearAllBits(); + } + return; } @@ -1065,13 +1073,23 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero, } case Instruction::Shl: { // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 - auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) { - return (KnownZero << ShiftAmt) | - APInt::getLowBitsSet(BitWidth, ShiftAmt); // Low bits known 0. + bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); + auto KZF = [BitWidth, NSW](const APInt &KnownZero, unsigned ShiftAmt) { + APInt KZResult = + (KnownZero << ShiftAmt) | + APInt::getLowBitsSet(BitWidth, ShiftAmt); // Low bits known 0. + // If this shift has "nsw" keyword, then the result is either a poison + // value or has the same sign bit as the first operand. + if (NSW && KnownZero.isNegative()) + KZResult.setBit(BitWidth - 1); + return KZResult; }; - auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) { - return KnownOne << ShiftAmt; + auto KOF = [BitWidth, NSW](const APInt &KnownOne, unsigned ShiftAmt) { + APInt KOResult = KnownOne << ShiftAmt; + if (NSW && KnownOne.isNegative()) + KOResult.setBit(BitWidth - 1); + return KOResult; }; computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, diff --git a/llvm/test/Analysis/ValueTracking/known-signbit-shift.ll b/llvm/test/Analysis/ValueTracking/known-signbit-shift.ll new file mode 100644 index 00000000000..bf984cb7474 --- /dev/null +++ b/llvm/test/Analysis/ValueTracking/known-signbit-shift.ll @@ -0,0 +1,55 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -instcombine -S | FileCheck %s + +; Result of left shifting a non-negative integer +; with nsw flag should also be non-negative +define i1 @test_shift_nonnegative(i32 %a) { +; CHECK-LABEL: @test_shift_nonnegative( +; CHECK-NEXT: ret i1 true +; + %b = lshr i32 %a, 2 + %shift = shl nsw i32 %b, 3 + %cmp = icmp sge i32 %shift, 0 + ret i1 %cmp +} + +; Result of left shifting a negative integer with +; nsw flag should also be negative +define i1 @test_shift_negative(i32 %a, i32 %b) { +; CHECK-LABEL: @test_shift_negative( +; CHECK-NEXT: ret i1 true +; + %c = or i32 %a, -2147483648 + %d = and i32 %b, 7 + %shift = shl nsw i32 %c, %d + %cmp = icmp slt i32 %shift, 0 + ret i1 %cmp +} + +; If sign bit is a known zero, it cannot be a known one. +; This test should not crash opt. +define i32 @test_no_sign_bit_conflict1(i1 %b) { +; CHECK-LABEL: @test_no_sign_bit_conflict1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SEL:%.*]] = select i1 %b, i32 -2147221504, i32 -2147483648 +; CHECK-NEXT: ret i32 [[SEL]] +; +entry: + %sel = select i1 %b, i32 8193, i32 8192 + %mul = shl nsw i32 %sel, 18 + ret i32 %mul +} + +; If sign bit is a known one, it cannot be a known zero. +; This test should not crash opt. +define i32 @test_no_sign_bit_conflict2(i1 %b) { +; CHECK-LABEL: @test_no_sign_bit_conflict2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SEL:%.*]] = select i1 %b, i32 2147221504, i32 2146959360 +; CHECK-NEXT: ret i32 [[SEL]] +; +entry: + %sel = select i1 %b, i32 -8193, i32 -8194 + %mul = shl nsw i32 %sel, 18 + ret i32 %mul +} |
