[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

1078

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

21

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

[lihuang]

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

21

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

803

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

1077

Indent is off.

[lihuang]

lib/Analysis/ValueTracking.cpp

803

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

798–802

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

798–802

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

798–802

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

799–800

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(const 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);
+    // 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;
   }
 
   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).
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) |
-             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) |
+      // 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,
                                       KnownZero2, KnownOne2, Depth, Q, KZF,
                                       KOF);
     break;
   }
   case Instruction::LShr: {

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

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