[ValueTracking] Correct early out in computeKnownBitsFromOperator to work with non power of 2 bit widths

[craig.topper]

Summary

There's an early out that's trying to detect when we don't know any bits that make up the legal range of a shift. The code subtracts one from BitWidth which creates a mask in the lower bits for power of 2 bit widths. This is then ANDed with the known bits to see if any of those bits are known. If the bit width isn't a power of 2 this creates a non-sensical mask.

This patch corrects this by rounding up to a power of 2 before doing the subtract and mask.

I found this by inspection. I'll try to put together a test, but wanted to make sure others agreed with my assessment.

[spatel]

The analysis looks right to me - this won't work for non-power-of-2 widths, and there's nothing restricting the possible widths coming into here AFAICT.

[craig.topper]

Add test case.

[craig.topper]

Fix formatting

[spatel]

LGTM.

test/Transforms/InstCombine/shift.ll

1309–1317 ↗

(On Diff #102490)

A comment or hex values to help explain why this is true would be good.

llvm/trunk/lib/Analysis/ValueTracking.cpp

static void computeKnownBitsFromShiftOperator(
   Known.resetAll();
 
   // If we know the shifter operand is nonzero, we can sometimes infer more
   // known bits. However this is expensive to compute, so be lazy about it and
   // only compute it when absolutely necessary.
   Optional<bool> ShifterOperandIsNonZero;
 
   // Early exit if we can't constrain any well-defined shift amount.
-  if (!(ShiftAmtKZ & (BitWidth - 1)) && !(ShiftAmtKO & (BitWidth - 1))) {
+  if (!(ShiftAmtKZ & (PowerOf2Ceil(BitWidth) - 1)) &&
+      !(ShiftAmtKO & (PowerOf2Ceil(BitWidth) - 1))) {
     ShifterOperandIsNonZero =
         isKnownNonZero(I->getOperand(1), Depth + 1, Q);
     if (!*ShifterOperandIsNonZero)
       return;
   }
 
   computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
 

llvm/trunk/test/Transforms/InstCombine/shift.ll

 ; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i8> %x, <i8 7, i8 7>
 ; CHECK-NEXT:    ret <2 x i8> [[SHR]]
 ;
   %and = and <2 x i8> %x, <i8 128, i8 128>
   %shr = lshr <2 x i8> %and, <i8 7, i8 7>
   ret <2 x i8> %shr
 }
 
+; Make sure known bits works correctly with non power of 2 bit widths.
+define i7 @test65(i7 %a, i7 %b) {
+; CHECK-LABEL: @test65(
+; CHECK-NEXT:    ret i7 0
+;
+  %shiftamt = and i7 %b, 6 ; this ensures the shift amount is even and less than the bit width.
+  %x = lshr i7 42, %shiftamt ; 42 has a zero in every even numbered bit and a one in every odd bit.
+  %y = and i7 %x, 1 ; this extracts the lsb which should be 0 because we shifted an even number of bits and all even bits of the shift input are 0.
+  ret i7 %y
+}