[ValueTracking] Teach isKnownNonZero a new trick

[jmolloy]

Summary

If the shifter operand is a constant, and all of the bits shifted out are known to be zero, then if X is known non-zero at least one non-zero bit must remain.

[jmolloy]

Hi David, Hal,

Do either of you have any comments on this?

Cheers,

James

[reames]

lib/Analysis/ValueTracking.cpp

1837

This really seems like two distinct cases and the code would be clearer if organized as such.

case 1 - There's a known one bit somewhere in the portion not shifted out.

case 2 - All bits shifted out are known-zero and X is known non-zero.

I think what you have is correct, I just found the flow of the code confusing on first read.

unittests/Analysis/ValueTrackingTest.cpp

203 ↗

(On Diff #34543)

I'd probably just phrase this as a normal IR test for inst combine or inst simplify. What's here is correct, just needlessly complicated.

[hfinkel]

lib/Analysis/ValueTracking.cpp

1832

I don't think this check is necessary, and you can just use Shift->getLimitedValue(BitWidth-1) below, because it is undefined behavior for the number to be larger than that regardless.

[sanjoy]

lib/Analysis/ValueTracking.cpp

1837

You could also check for the exact flag here.

1837

How about if (KnownZero.countTrailingZeros() >= Shift->getLimitedValue())?

1838

I'd expect this first case to be handled by the fall through at the end. Do you have a case where it doesn't?

unittests/Analysis/ValueTrackingTest.cpp

203 ↗

(On Diff #34543)

+1 to Philip's comment.

[jmolloy]

lib/Analysis/ValueTracking.cpp

1837

I think the exact flag is tested for just above.

1838

Nope - this was purely a compile-speed micro optimization - we've already computed known bits, so it seemed a waste to compute them again.

[jmolloy]

Hi Hal, Sanjoy, Philip,

Thanks very much for the reviews - sorry it took so long to address.

The newest version should address these comments.

Cheers,

James

[reames]

lib/Analysis/ValueTracking.cpp

1841

Shouldn't this be countTrailingZeros?

test/Analysis/ValueTracking/knownzero-shift.ll

11

You could just return the i1 directly.

[jmolloy]

lib/Analysis/ValueTracking.cpp

1841

I don't think so, because bits in KnownZero are one if they are known to be zero. I agree it looks confusing though and I've made this mistake in the past.

[reames]

LGTM

[jmolloy]

Thanks Philip!

r248508.

lib/Analysis/ValueTracking.cpp

     ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
     if (XKnownNegative)
       return true;
+
+    // If the shifter operand is a constant, and all of the bits shifted
+    // out are known to be zero, and X is known non-zero then at least one
+    // non-zero bit must remain.
+    if (ConstantInt *Shift = dyn_cast<ConstantInt>(Y)) {
+      APInt KnownZero(BitWidth, 0);
+      APInt KnownOne(BitWidth, 0);
+      computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
+      
+      auto ShiftVal = Shift->getLimitedValue(BitWidth - 1);
+      // Is there a known one in the portion not shifted out?
+      if (KnownOne.countLeadingZeros() < BitWidth - ShiftVal)
+        return true;
+      // Are all the bits to be shifted out known zero?
+      if (KnownZero.countTrailingOnes() >= ShiftVal)
+        return isKnownNonZero(X, DL, Depth, Q);
+    }
   }
   // div exact can only produce a zero if the dividend is zero.
   else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) {

test/Analysis/ValueTracking/knownzero-shift.ll

+; RUN: opt -instsimplify -S < %s | FileCheck %s
+
+; CHECK-LABEL: @test
+define i1 @test(i8 %p, i8* %pq) {
+  %q = load i8, i8* %pq, !range !0 ; %q is known nonzero; no known bits
+  %1 = or i8 %p, 1                 ; %1[0] = 1, %1 is odd
+  %2 = shl i8 %1, %q               ; %2[0] = 0, rest unknown but cannot be zero
+  %A = lshr i8 %2, 1               ; We should know that %A is nonzero.
+  %x = icmp eq i8 %A, 0
+  ; CHECK: ret i1 false
+  ret i1 %x
+}
+
+!0 = !{ i8 1, i8 5 }