[ValueTracking] When calculating known bits for integer abs, make sure we're looking at a negate and not just any instruction with the nsw flag set.

[craig.topper]

Summary

The matchSelectPattern code can match patterns like (x >= 0) ? x : -x
for absolute value. But it can also match ((x-y) >= 0) ? (x-y) : (y-x).
If the latter form was matched we can only use the nsw flag if its
set on both subtracts.

This match makes sure we're looking at the former case only.

[nikic]

As we only have a handful of SPF_ABS uses, it might make sense to introduce a separate abs flavor for the nsw case (which would also allow to handle the x-y case more accurately). SPF_PABS? SPF_ABS_NSW?

(Not in this revision of course.)

llvm/lib/Analysis/ValueTracking.cpp

1098 ↗

(On Diff #213181)

I think this should still be going through IIQ, otherwise NewGVN might be unhappy.

[craig.topper]

Continue using IIQ. Also use IIQ to the other location that checks for the NSW.

[nikic]

LGTM

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (SPF == SPF_SMAX) {
       // We can derive an upper bound on the result by taking the max of the
       // leading zero bits.
       MaxHighZeros =
           std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros());
     } else if (SPF == SPF_ABS) {
       // RHS from matchSelectPattern returns the negation part of abs pattern.
       // If the negate has an NSW flag we can assume the sign bit of the result
       // will be 0 because that makes abs(INT_MIN) undefined.
-      if (Q.IIQ.hasNoSignedWrap(cast<Instruction>(RHS)))
+      if (match(RHS, m_Neg(m_Specific(LHS))) &&
+          Q.IIQ.hasNoSignedWrap(cast<Instruction>(RHS)))
         MaxHighZeros = 1;
     }
 
     // Only known if known in both the LHS and RHS.
     Known.One &= Known2.One;
     Known.Zero &= Known2.Zero;
     if (MaxHighOnes > 0)
       Known.One.setHighBits(MaxHighOnes);
case Intrinsic::ssub_sat:
     }
     break;
   default:
     break;
   }
 }
 
 static void setLimitsForSelectPattern(const SelectInst &SI, APInt &Lower,
-                                      APInt &Upper) {
+                                      APInt &Upper, const InstrInfoQuery &IIQ) {
   const Value *LHS, *RHS;
   SelectPatternResult R = matchSelectPattern(&SI, LHS, RHS);
   if (R.Flavor == SPF_UNKNOWN)
     return;
 
   unsigned BitWidth = SI.getType()->getScalarSizeInBits();
 
   if (R.Flavor == SelectPatternFlavor::SPF_ABS) {
     // If the negation part of the abs (in RHS) has the NSW flag,
     // then the result of abs(X) is [0..SIGNED_MAX],
     // otherwise it is [0..SIGNED_MIN], as -SIGNED_MIN == SIGNED_MIN.
     Lower = APInt::getNullValue(BitWidth);
-    if (cast<Instruction>(RHS)->hasNoSignedWrap())
+    if (match(RHS, m_Neg(m_Specific(LHS))) &&
+        IIQ.hasNoSignedWrap(cast<Instruction>(RHS)))
       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.
ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo) {
   unsigned BitWidth = V->getType()->getScalarSizeInBits();
   APInt Lower = APInt(BitWidth, 0);
   APInt Upper = APInt(BitWidth, 0);
   if (auto *BO = dyn_cast<BinaryOperator>(V))
     setLimitsForBinOp(*BO, Lower, Upper, IIQ);
   else if (auto *II = dyn_cast<IntrinsicInst>(V))
     setLimitsForIntrinsic(*II, Lower, Upper);
   else if (auto *SI = dyn_cast<SelectInst>(V))
-    setLimitsForSelectPattern(*SI, Lower, Upper);
+    setLimitsForSelectPattern(*SI, Lower, Upper, IIQ);
 
   ConstantRange CR = ConstantRange::getNonEmpty(Lower, Upper);
 
   if (auto *I = dyn_cast<Instruction>(V))
     if (auto *Range = IIQ.getMetadata(I, LLVMContext::MD_range))
       CR = CR.intersectWith(getConstantRangeFromMetadata(*Range));
 
   return CR;
 }

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

;
   %cond = select i1 %cmp, i32 %sub, i32 %a
   %r = icmp ne i32 %cond, -2
   ret i1 %r
 }
 
 ; We can't fold this to false unless both subs have nsw.
 define i1 @abs_sub_sub_missing_nsw(i32 %x, i32 %y) {
 ; CHECK-LABEL: @abs_sub_sub_missing_nsw(
-; CHECK-NEXT:    ret i1 false
+; CHECK-NEXT:    [[A:%.*]] = sub i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[B:%.*]] = sub nsw i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i32 [[A]], -1
+; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[A]], i32 [[B]]
+; CHECK-NEXT:    [[E:%.*]] = icmp slt i32 [[D]], 0
+; CHECK-NEXT:    ret i1 [[E]]
 ;
   %a = sub i32 %x, %y
   %b = sub nsw i32 %y, %x
   %c = icmp sgt i32 %a, -1
   %d = select i1 %c, i32 %a, i32 %b
   %e = icmp slt i32 %d, 0
   ret i1 %e
 }