[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.

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);