[SCEV] Infer known bits from known sign bits

[reames]

Summary

This was suggested by lebedev.ri over on D96534.

This seems like a reasonable change, but I haven't been able to find a test case which actually changes output. All of the obvious ones are caught through the existing ashr constant range trick for signed ranges. Despite this, I think this is reasonable to land if reviewers agree.

[reames]

@lebedev.ri, poke

[lebedev.ri]

In D97064#2600628, @reames wrote:

@lebedev.ri, poke

I'm not really surprised that it doesn't affect any tests, but does it affect any code out there?
If you can pinpoint some original source file that produces different final .ll/.s, a test case can be reduced trivially.

[reames]

In D97064#2600631, @lebedev.ri wrote:

In D97064#2600628, @reames wrote:

@lebedev.ri, poke

I'm not really surprised that it doesn't affect any tests, but does it affect any code out there?
If you can pinpoint some original source file that produces different final .ll/.s, a test case can be reduced trivially.

I'm not motivated to go run a broad set of benchmarks here. I'm doing it only to address your review comment. If you don't have a motivating case (or are okay landing without one), I'd prefer to abandon the patch.

(reworded comment - realized my original wording was poor)

[lebedev.ri]

So, i've looked, and this does not cause any binary differences as of plain vanilla test-suite+RawSpeed.
That being said, the change is rather straight-forward, and is practically free,
so i think we could just land this, even that isn't great..

llvm/lib/Analysis/ScalarEvolution.cpp

if (MDRange.hasValue())
       ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue(),
                                                             RangeType);
 
     // See if ValueTracking can give us a useful range.
     const DataLayout &DL = getDataLayout();
     KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
     if (Known.getBitWidth() != BitWidth)
       Known = Known.zextOrTrunc(BitWidth);
-    // If Known does not result in full-set, intersect with it.
-    if (Known.getMinValue() != Known.getMaxValue() + 1)
-      ConservativeResult = ConservativeResult.intersectWith(
-          ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1),
-          RangeType);
 
     // ValueTracking may be able to compute a tighter result for the number of
     // sign bits than for the value of those sign bits.
     unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
+    if (U->getType()->isPointerTy()) {
       // If the pointer size is larger than the index size type, this can cause
       // NS to be larger than BitWidth. So compensate for this.
-    if (U->getType()->isPointerTy()) {
       unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType());
       int ptrIdxDiff = ptrSize - BitWidth;
       if (ptrIdxDiff > 0 && ptrSize > BitWidth && NS > (unsigned)ptrIdxDiff)
         NS -= ptrIdxDiff;
     }
 
+    if (NS > 1) {
+      // If we know any of the sign bits, we know all of the sign bits.
+      if (!Known.Zero.getHiBits(NS).isNullValue())
+        Known.Zero.setHighBits(NS);
+      if (!Known.One.getHiBits(NS).isNullValue())
+        Known.One.setHighBits(NS);
+    }
+
+    if (Known.getMinValue() != Known.getMaxValue() + 1)
+      ConservativeResult = ConservativeResult.intersectWith(
+          ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1),
+          RangeType);
     if (NS > 1)
       ConservativeResult = ConservativeResult.intersectWith(
           ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
                         APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1),
           RangeType);
 
     // A range of Phi is a subset of union of all ranges of its input.
     if (const PHINode *Phi = dyn_cast<PHINode>(U->getValue())) {