[ConstantRange] Remove costly udivrem from ConstantRange::truncate

[craig.topper]

Summary

Truncate currently uses a udivrem call which is going to be slow particularly for larger than 64-bit widths.

As far as I can tell all we were trying to do was modulo LowerDiv by (MaxValue+1) and make sure whatever value was effectively subtracted from LowerDiv was also subtracted from UpperDiv.

This patch recognizes that MaxValue+1 is a power of 2 so we can just use a bitwise AND to accomplish a modulo operation or isolate the upper bits.

[craig.topper]

Refine this even more to remove another temporary APInt. Now we count bits to replace the compares with MaxValue.

[craig.topper]

lib/IR/ConstantRange.cpp

579 ↗

(On Diff #97202)

Note this countTrailingOnes check isn't strictly necessary. If Upper is equal to MaxValue(DstTy), Union will be FullSet. We could continue on and trust unionWith to return FullSet.

592 ↗

(On Diff #97202)

Note the original code used uge, but I believe ugt was sufficient. Thus I've only implemented the equivalent of ugt with the getActiveBits check here.

[craig.topper]

Ping

[craig.topper]

Ping x2

[craig.topper]

Ping x3.

[spatel]

Do we have (or can you add) unit tests to make sure this is behaving as expected?

[craig.topper]

We had some unittests. I added a missing EXPECT for one of them in r304693. And added a few more tests in r304694.

[spatel]

LGTM.

llvm/trunk/lib/IR/ConstantRange.cpp

 
 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
   assert(getBitWidth() > DstTySize && "Not a value truncation");
   if (isEmptySet())
     return ConstantRange(DstTySize, /*isFullSet=*/false);
   if (isFullSet())
     return ConstantRange(DstTySize, /*isFullSet=*/true);
 
-  APInt MaxValue = APInt::getLowBitsSet(getBitWidth(), DstTySize);
-  APInt MaxBitValue = APInt::getOneBitSet(getBitWidth(), DstTySize);
-
   APInt LowerDiv(Lower), UpperDiv(Upper);
   ConstantRange Union(DstTySize, /*isFullSet=*/false);
 
   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
   // then we do the union with [MaxValue, Upper)
   if (isWrappedSet()) {
-    // If Upper is greater than Max Value, it covers the whole truncated range.
-    if (Upper.uge(MaxValue))
+    // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
+    // truncated range.
+    if (Upper.getActiveBits() > DstTySize ||
+        Upper.countTrailingOnes() == DstTySize)
       return ConstantRange(DstTySize, /*isFullSet=*/true);
 
     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
     UpperDiv.setAllBits();
 
     // Union covers the MaxValue case, so return if the remaining range is just
-    // MaxValue.
+    // MaxValue(DstTy).
     if (LowerDiv == UpperDiv)
       return Union;
   }
 
   // Chop off the most significant bits that are past the destination bitwidth.
-  if (LowerDiv.uge(MaxValue)) {
-    APInt Div(getBitWidth(), 0);
-    APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
-    UpperDiv -= MaxBitValue * Div;
+  if (LowerDiv.getActiveBits() > DstTySize) {
+    // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
+    APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
+    LowerDiv -= Adjust;
+    UpperDiv -= Adjust;
   }
 
-  if (UpperDiv.ule(MaxValue))
+  unsigned UpperDivWidth = UpperDiv.getActiveBits();
+  if (UpperDivWidth <= DstTySize)
     return ConstantRange(LowerDiv.trunc(DstTySize),
                          UpperDiv.trunc(DstTySize)).unionWith(Union);
 
   // The truncated value wraps around. Check if we can do better than fullset.
-  UpperDiv -= MaxBitValue;
+  if (UpperDivWidth == DstTySize + 1) {
+    // Clear the MSB so that UpperDiv wraps around.
+    UpperDiv.clearBit(DstTySize);
     if (UpperDiv.ult(LowerDiv))
       return ConstantRange(LowerDiv.trunc(DstTySize),
                            UpperDiv.trunc(DstTySize)).unionWith(Union);
+  }
 
   return ConstantRange(DstTySize, /*isFullSet=*/true);
 }
 
 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
   unsigned SrcTySize = getBitWidth();
   if (SrcTySize > DstTySize)
     return truncate(DstTySize);