[ValueTracking] Compute range for abs without nsw

[nikic]

Summary

This is a small followup to D59511. The code that was moved into computeConstantRange() there is a bit overly conversative: If the abs is not nsw, it does not compute any range. However, abs without nsw still has a well-defined contiguous unsigned range from 0 to SIGNED_MIN (inclusive). This is a lot less useful than the usual 0 to SIGNED_MAX (inclusive) range, but if we're already here we might as well specify it...

[lebedev.ri]

llvm/test/Transforms/InstSimplify/icmp-abs-nabs.ll

158

Hm, after thinking about it a bit more, i think the test coverage could be improved.
In reality, this test only shows that we end up folding this pattern to true.
But what are the thresholds for that opt to happen?
I.e. i think you'd want to add two more test cases here, with 2147483649+1 and 2147483649-1 constants.

[nikic]

llvm/test/Transforms/InstSimplify/icmp-abs-nabs.ll

158

The test directly below this one checks the <2147483648 case, which does not fold. So if <2147483648 does not fold but <2147483649 does, this has to be the upper boundary of the range. (It does not check the lower boundary, but as it's zero and >= 0 in unsigned domain is tautological we can't do a direct check for it.)

[lebedev.ri]

Actually, i haven't fully noticed that there was that second test.
Looks good then modulo comment nit.

llvm/lib/Analysis/ValueTracking.cpp

5677–5678

This comment reads weird.
I think you want something more like:

// If the negation part of the abs (in RHS) has NSW flag,
// then the result of abs(X) is [0..SIGNED_MAX],
// else it is [0..-SIGNED_MIN],

?

llvm/test/Transforms/InstSimplify/icmp-abs-nabs.ll

158

Okay, https://rise4fun.com/Alive/tya

llvm/lib/Analysis/ValueTracking.cpp

static void setLimitsForSelectPattern(const SelectInst &SI, APInt &Lower,
                                       APInt &Upper) {
   const Value *LHS, *RHS;
   SelectPatternResult R = matchSelectPattern(&SI, LHS, RHS);
   if (R.Flavor == SPF_UNKNOWN)
     return;
 
   unsigned BitWidth = SI.getType()->getScalarSizeInBits();
 
-  // matchSelectPattern() returns the negation part of an abs pattern in RHS.
-  // If the negate has an NSW flag, abs(INT_MIN) is undefined. Without that
-  // constraint, we can't make a contiguous range for the result of abs.
-  if (R.Flavor == SelectPatternFlavor::SPF_ABS &&
-      cast<Instruction>(RHS)->hasNoSignedWrap()) {
-    // The result of abs(X) is >= 0 (with nsw).
+  if (R.Flavor == SelectPatternFlavor::SPF_ABS) {
+    // The result of abs(X) is >= 0, or SignedMin if the negation part of the
+    // abs (in RHS) has no NSW flag.
     Lower = APInt::getNullValue(BitWidth);
+    if (cast<Instruction>(RHS)->hasNoSignedWrap())
       Upper = APInt::getSignedMaxValue(BitWidth) + 1;
+    else
+      Upper = APInt::getSignedMinValue(BitWidth) + 1;
     return;
   }
 
   if (R.Flavor == SelectPatternFlavor::SPF_NABS) {
     // The result of -abs(X) is <= 0.
     Lower = APInt::getSignedMinValue(BitWidth);
     Upper = APInt(BitWidth, 1);
     return;

llvm/test/Transforms/InstSimplify/icmp-abs-nabs.ll

;
   %abs = select i1 %cmp, i32 %negx, i32 %x
   %r = icmp sle i32 %abs, 0
   ret i1 %r
 }
 
 ; Even if we don't have nsw, the range is still limited in the unsigned domain.
 define i1 @abs_positive_or_signed_min(i32 %x) {
 ; CHECK-LABEL: @abs_positive_or_signed_min(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[NEGX]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[ABS]], -2147483647
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i32 %x, 0
   %negx = sub i32 0, %x
   %abs = select i1 %cmp, i32 %negx, i32 %x
   %r = icmp ult i32 %abs, 2147483649
   ret i1 %r
 }
 
 define i1 @abs_positive_or_signed_min_reduced_range(i32 %x) {
 ; CHECK-LABEL: @abs_positive_or_signed_min_reduced_range(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
 ; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[NEGX]], i32 [[X]]