[ValueTracking] Improve ValueTracking on left shift with nsw flag

[lihuang]

Summary

Improve ValueTracking on left shift with nsw flag

If a left shift has nsw flag, it produces a poison value if it shifts out any bits that disagree with the resultant sign bit. So we can assume the result has the same sign bit as the first operand.

This patch is separated from D18777.

[sanjoy]

lgtm with some minor comments inline.

lib/Analysis/ValueTracking.cpp

1028

Use APInt::setBit here and below (otherwise we'll unnecessarily allocate a new APInt if the bitwidth is larger than 64).

test/Analysis/ValueTracking/known-signbit-shift.ll

20

Why do you need to and with 7 here? Why not just shl directly with %b?

[lihuang]

test/Analysis/ValueTracking/known-signbit-shift.ll

20

It just didn't work without the "and", it seems like this optimization doesn't recognize the case when the second operand of shift is totally unknown. But this should be some other problem, not the problem with this change. I will investigate.

[lihuang]

Use APInt::setBit, add comment

[lihuang]

This review was not closed automatically. Committed as r278172

[lihuang]

reopen this review because the committed change has been reverted

[lihuang]

Hi Sanjoy,

This change is mostly same as before, but with the fix for PR28946 added in computeKnownBitsFromShiftOperator.

[sanjoy]

Comments inline.

lib/Analysis/ValueTracking.cpp

809

This looks excessively pessimistic -- why can't we KnownOne &= ~KnownZero or KnownZero &= ~KnownOne instead? Both seem better than what we have here.

1027

Indent is off.

[lihuang]

lib/Analysis/ValueTracking.cpp

809

You are right that's too pessimistic. I changed it to KnownOne &= ~KnownZero.

I just copied the logic at the end of this function, looks like we could also change that.

[majnemer]

lib/Analysis/ValueTracking.cpp

804–808

This goes against the ethos of ComputeKnownValues. Conflicts should return "I don't know" so that we can transform stuff into undef.

[lihuang]

lib/Analysis/ValueTracking.cpp

804–808

Hi David, I'm not familiar with this part but can we transform "i don't know" to undef? What if we just cannot infer anything from this value?

[lihuang]

lib/Analysis/ValueTracking.cpp

804–808

Sorry, I think I misunderstood what you meant. I agree that this should return "I don't know" so it won't prevent transforming stuff to undef.

[lihuang]

Should clear KnownZero and KnownOne bits when there is conflicts to allow propagation of undef. Changed the code in computeKnownBitsFromShiftOperator to have the same logic as that at the end of this function.

[majnemer]

lib/Analysis/ValueTracking.cpp

805–806

Please remove "We can return arbitrary values."

[majnemer]

LGTM, thanks!

[evstupac]

Committed r279684.

[sanjoy]

Removing from queue (since this has been committed).

lib/Analysis/ValueTracking.cpp

static void computeKnownBitsFromShiftOperator(Operator *I,
   unsigned BitWidth = KnownZero.getBitWidth();
 
   if (auto *SA = dyn_cast<ConstantInt>(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);
     return;
   }
 
   computeKnownBits(I->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
 
   // Note: We cannot use KnownZero.getLimitedValue() here, because if
   // BitWidth > 64 and any upper bits are known, we'll end up returning the
   // limit value (which implies all bits are known).
   uint64_t ShiftAmtKZ = KnownZero.zextOrTrunc(64).getZExtValue();
   uint64_t ShiftAmtKO = KnownOne.zextOrTrunc(64).getZExtValue();
 
   // It would be more-clearly correct to use the two temporaries for this
   // calculation. Reusing the APInts here to prevent unnecessary allocations.
   KnownZero.clearAllBits();
case Instruction::SExt: {
     if (KnownZero[SrcBitWidth-1])             // Input sign bit known zero
       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
     else if (KnownOne[SrcBitWidth-1])           // Input sign bit known set
       KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
     break;
   }
   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) |
+    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 (NSW && KnownZero.isNegative())
+        KZResult |= APInt::getSignBit(BitWidth);
+      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 |= APInt::getSignBit(BitWidth);
+      return KOResult;
     };
 
     computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
                                       KnownZero2, KnownOne2, Depth, Q, KZF,
                                       KOF);
     break;
   }
   case Instruction::LShr: {

test/Analysis/ValueTracking/known-signbit-shift.ll

+; 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: 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: 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
+}