Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -769,8 +769,8 @@ // Compute known bits from a shift operator, including those with a // non-constant shift amount. KnownZero and KnownOne are the outputs of this -// function. KnownZero2 and KnownOne2 are pre-allocated temporaries with the -// same bit width as KnownZero and KnownOne. KZF and KOF are operator-specific +// function. Op0KnownZero and Op0KnownOne are pre-computed known-bit results +// of the first operand of this shift. KZF and KOF are operator-specific // functors that, given the known-zero or known-one bits respectively, and a // shift amount, compute the implied known-zero or known-one bits of the shift // operator's result respectively for that shift amount. The results from calling @@ -778,16 +778,15 @@ template static void computeKnownBitsFromShiftOperator(Operator *I, APInt &KnownZero, APInt &KnownOne, - APInt &KnownZero2, APInt &KnownOne2, + APInt &Op0KnownZero, APInt &Op0KnownOne, unsigned Depth, const Query &Q, KZFunctor KZF, KOFunctor KOF) { unsigned BitWidth = KnownZero.getBitWidth(); if (auto *SA = dyn_cast(I->getOperand(1))) { unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1); - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q); - KnownZero = KZF(KnownZero, ShiftAmt); - KnownOne = KOF(KnownOne, ShiftAmt); + KnownZero = KZF(Op0KnownZero, ShiftAmt); + KnownOne = KOF(Op0KnownOne, ShiftAmt); return; } @@ -817,8 +816,6 @@ return; } - computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q); - KnownZero = KnownOne = APInt::getAllOnesValue(BitWidth); for (unsigned ShiftAmt = 0; ShiftAmt < BitWidth; ++ShiftAmt) { // Combine the shifted known input bits only for those shift amounts @@ -838,8 +835,8 @@ continue; } - KnownZero &= KZF(KnownZero2, ShiftAmt); - KnownOne &= KOF(KnownOne2, ShiftAmt); + KnownZero &= KZF(Op0KnownZero, ShiftAmt); + KnownOne &= KOF(Op0KnownOne, ShiftAmt); } // If there are no compatible shift amounts, then we've proven that the shift @@ -1073,10 +1070,23 @@ KOResult.setBit(BitWidth - 1); return KOResult; }; - + + computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q); computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, KnownZero2, KnownOne2, Depth, Q, KZF, KOF); + // 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 (cast(I)->hasNoSignedWrap()) { + if (KnownZero2.isNegative()) { + KnownZero.setBit(BitWidth - 1); + KnownOne.clearBit(BitWidth - 1); + } + else if (KnownOne2.isNegative()) { + KnownOne.setBit(BitWidth - 1); + KnownZero.clearBit(BitWidth - 1); + } + } break; } case Instruction::LShr: { @@ -1091,6 +1101,7 @@ return APIntOps::lshr(KnownOne, ShiftAmt); }; + computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q); computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, KnownZero2, KnownOne2, Depth, Q, KZF, KOF); @@ -1106,6 +1117,7 @@ return APIntOps::ashr(KnownOne, ShiftAmt); }; + computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q); computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, KnownZero2, KnownOne2, Depth, Q, KZF, KOF); Index: test/Analysis/ValueTracking/known-signbit-shift.ll =================================================================== --- test/Analysis/ValueTracking/known-signbit-shift.ll +++ test/Analysis/ValueTracking/known-signbit-shift.ll @@ -1,10 +1,12 @@ +; 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 +; 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: ret i1 true +; CHECK-NEXT: ret i1 true +; %b = lshr i32 %a, 2 %shift = shl nsw i32 %b, 3 %cmp = icmp sge i32 %shift, 0 @@ -15,10 +17,39 @@ ; nsw flag should also be negative define i1 @test_shift_negative(i32 %a, i32 %b) { ; CHECK-LABEL: @test_shift_negative( -; CHECK: ret i1 true +; 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 +}