[Analysis] allow caller to choose signed/unsigned when computing constant range

[spatel]

Summary

We should not lose analysis precision if an 'add' has both no-wrap flags (nsw and nuw) compared to just one or the other.

This patch is modeled on a similar construct that was added with D59386.

I don't think it is possible to expose a problem with an unsigned compare because of the way this was coded (nuw is handled first).

InstCombine has an assert that fires with the example from:
https://github.com/llvm/llvm-project/issues/52884
...because it was expecting InstSimplify to handle this kind of pattern with an smax.

[nikic]

LGTM. I implemented something similar in https://reviews.llvm.org/D59668 and then dropped it because my implementation was broken and my immediate need went away :)

[spatel]

In D116322#3211291, @nikic wrote:

LGTM. I implemented something similar in https://reviews.llvm.org/D59668 and then dropped it because my implementation was broken and my immediate need went away :)

Thanks - I didn't remember that patch, but yes, it's very close to this.

Our exhaustive unit testing has matured since then, so it shouldn't be too hard to implement. I'll look at that as a follow-up. I'd like to get this in to avoid the crashing bug.

[anna]

@spatel: inline comment added about incorrect arguments for one of the callsites. Pls fix.

llvm/lib/Analysis/ValueTracking.cpp

7149

just noticed this while reading the code. The bool arguments are swapped here. Should be:

computeConstantRange(Cmp->getOperand(1), /* ForSigned */ false, UseInstrInfo, AC, I, DT, Depth + 1);

[spatel]

llvm/lib/Analysis/ValueTracking.cpp

7149

Thanks for reviewing!
1e50d064666f

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// used only along the paths control dependent on the computation
   /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
   bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
                                  const DominatorTree &DT);
 
 
   /// Determine the possible constant range of an integer or vector of integer
   /// value. This is intended as a cheap, non-recursive check.
-  ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true,
+  ConstantRange computeConstantRange(const Value *V, bool ForSigned,
+                                     bool UseInstrInfo = true,
                                      AssumptionCache *AC = nullptr,
                                      const Instruction *CtxI = nullptr,
                                      const DominatorTree *DT = nullptr,
                                      unsigned Depth = 0);
 
   /// Return true if this function can prove that the instruction I will
   /// always transfer execution to one of its successors (including the next
   /// instruction that follows within a basic block). E.g. this is not

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (!Index.IsNSW)
       ScaleForGCD = APInt::getOneBitSet(Scale.getBitWidth(),
                                         Scale.countTrailingZeros());
 
     if (i == 0)
       GCD = ScaleForGCD.abs();
     else
       GCD = APIntOps::GreatestCommonDivisor(GCD, ScaleForGCD.abs());
 
-    ConstantRange CR =
-        computeConstantRange(Index.Val.V, true, &AC, Index.CxtI);
+    ConstantRange CR = computeConstantRange(Index.Val.V, /* ForSigned */ false,
+                                            true, &AC, Index.CxtI);
     KnownBits Known =
         computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT);
     CR = CR.intersectWith(
         ConstantRange::fromKnownBits(Known, /* Signed */ true),
         ConstantRange::Signed);
     CR = Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth());
 
     assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
 
   // Rule out tautological comparisons (eg., ult 0 or uge 0).
   ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C);
   if (RHS_CR.isEmptySet())
     return ConstantInt::getFalse(ITy);
   if (RHS_CR.isFullSet())
     return ConstantInt::getTrue(ITy);
 
-  ConstantRange LHS_CR = computeConstantRange(LHS, IIQ.UseInstrInfo);
+  ConstantRange LHS_CR =
+      computeConstantRange(LHS, CmpInst::isSigned(Pred), IIQ.UseInstrInfo);
   if (!LHS_CR.isFullSet()) {
     if (RHS_CR.contains(LHS_CR))
       return ConstantInt::getTrue(ITy);
     if (RHS_CR.inverse().contains(LHS_CR))
       return ConstantInt::getFalse(ITy);
   }
 
   // (mul nuw/nsw X, MulC) != C --> true  (if C is not a multiple of MulC)

llvm/lib/Analysis/ValueTracking.cpp

Optional<bool> llvm::isImpliedByDomCondition(CmpInst::Predicate Pred,
   auto PredCond = getDomPredecessorCondition(ContextI);
   if (PredCond.first)
     return isImpliedCondition(PredCond.first, Pred, LHS, RHS, DL,
                               PredCond.second);
   return None;
 }
 
 static void setLimitsForBinOp(const BinaryOperator &BO, APInt &Lower,
-                              APInt &Upper, const InstrInfoQuery &IIQ) {
+                              APInt &Upper, const InstrInfoQuery &IIQ,
+                              bool PreferSignedRange) {
   unsigned Width = Lower.getBitWidth();
   const APInt *C;
   switch (BO.getOpcode()) {
   case Instruction::Add:
     if (match(BO.getOperand(1), m_APInt(C)) && !C->isZero()) {
       bool HasNSW = IIQ.hasNoSignedWrap(&BO);
       bool HasNUW = IIQ.hasNoUnsignedWrap(&BO);
-      // FIXME: If we have both nuw and nsw, we should reduce the range further.
+
+      // If the caller expects a signed compare, then try to use a signed range.
+      // Otherwise if both no-wraps are set, use the unsigned range because it
+      // is never larger than the signed range. Example:
+      // "add nuw nsw i8 X, -2" is unsigned [254,255] vs. signed [-128, 125].
+      if (PreferSignedRange && HasNSW && HasNUW)
+        HasNUW = false;
+
       if (HasNUW) {
         // 'add nuw x, C' produces [C, UINT_MAX].
         Lower = *C;
       } else if (HasNSW) {
         if (C->isNegative()) {
           // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
           Lower = APInt::getSignedMinValue(Width);
           Upper = APInt::getSignedMaxValue(Width) + *C + 1;
static void setLimitForFPToI(const Instruction *I, APInt &Lower, APInt &Upper) {
   }
 
   if (isa<FPToUIInst>(I) && BitWidth >= 16) {
     // For a fptoui the lower limit is left as 0.
     Upper = APInt(BitWidth, 65505);
   }
 }
 
-ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo,
-                                         AssumptionCache *AC,
+ConstantRange llvm::computeConstantRange(const Value *V, bool ForSigned,
+                                         bool UseInstrInfo, AssumptionCache *AC,
                                          const Instruction *CtxI,
                                          const DominatorTree *DT,
                                          unsigned Depth) {
   assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction");
 
   if (Depth == MaxAnalysisRecursionDepth)
     return ConstantRange::getFull(V->getType()->getScalarSizeInBits());
 
   const APInt *C;
   if (match(V, m_APInt(C)))
     return ConstantRange(*C);
 
   InstrInfoQuery IIQ(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);
+    setLimitsForBinOp(*BO, Lower, Upper, IIQ, ForSigned);
   else if (auto *II = dyn_cast<IntrinsicInst>(V))
     setLimitsForIntrinsic(*II, Lower, Upper);
   else if (auto *SI = dyn_cast<SelectInst>(V))
     setLimitsForSelectPattern(*SI, Lower, Upper, IIQ);
   else if (isa<FPToUIInst>(V) || isa<FPToSIInst>(V))
     setLimitForFPToI(cast<Instruction>(V), Lower, Upper);
 
   ConstantRange CR = ConstantRange::getNonEmpty(Lower, Upper);
for (auto &AssumeVH : AC->assumptionsFor(V)) {
 
       if (!isValidAssumeForContext(I, CtxI, DT))
         continue;
       Value *Arg = I->getArgOperand(0);
       ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
       // Currently we just use information from comparisons.
       if (!Cmp || Cmp->getOperand(0) != V)
         continue;
-      ConstantRange RHS = computeConstantRange(Cmp->getOperand(1), UseInstrInfo,
-                                               AC, I, DT, Depth + 1);
+      // TODO: Set "ForSigned" parameter via Cmp->isSigned()?
+      ConstantRange RHS =
+          computeConstantRange(Cmp->getOperand(1), UseInstrInfo,
+                               /* ForSigned */ false, AC, I, DT, Depth + 1);
       CR = CR.intersectWith(
           ConstantRange::makeAllowedICmpRegion(Cmp->getPredicate(), RHS));
     }
   }
 
   return CR;
 }
 

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

static ScalarizationResult canScalarizeAccess(FixedVectorType *VecTy,
 
   unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
   APInt Zero(IntWidth, 0);
   APInt MaxElts(IntWidth, VecTy->getNumElements());
   ConstantRange ValidIndices(Zero, MaxElts);
   ConstantRange IdxRange(IntWidth, true);
 
   if (isGuaranteedNotToBePoison(Idx, &AC)) {
-    if (ValidIndices.contains(computeConstantRange(Idx, true, &AC, CtxI, &DT)))
+    if (ValidIndices.contains(computeConstantRange(Idx, /* ForSigned */ false,
+                                                   true, &AC, CtxI, &DT)))
       return ScalarizationResult::safe();
     return ScalarizationResult::unsafe();
   }
 
   // If the index may be poison, check if we can insert a freeze before the
   // range of the index is restricted.
   Value *IdxBase;
   ConstantInt *CI;

llvm/test/Transforms/InstCombine/minmax-intrinsics.ll

 ; CHECK-NEXT:    [[A:%.*]] = add nuw <3 x i8> [[X:%.*]], <i8 undef, i8 64, i8 64>
 ; CHECK-NEXT:    [[R:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[A]], <3 x i8> <i8 13, i8 -126, i8 -126>)
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %a = add nuw <3 x i8> %x, <i8 undef, i8 64, i8 64>
   %r = call <3 x i8> @llvm.umax.v3i8(<3 x i8> %a, <3 x i8> <i8 13, i8 130, i8 130>)
   ret <3 x i8> %r
 }
+
+; Issue #52884 - this would assert because of a failure to simplify.
+
+define i8 @smax_offset_simplify(i8 %x) {
+; CHECK-LABEL: @smax_offset_simplify(
+; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i8 [[X:%.*]], 50
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %1 = add nuw nsw i8 50, %x
+  %m = call i8 @llvm.smax.i8(i8 %1, i8 -124)
+  ret i8 %m
+}

llvm/test/Transforms/InstSimplify/icmp-constant.ll

 ; CHECK-LABEL: @add_nsw_sgt(
 ; CHECK-NEXT:    ret i1 true
 ;
   %add = add nsw i8 %x, 5
   %cmp = icmp sgt i8 %add, -124
   ret i1 %cmp
 }
 
+; nuw should not inhibit the fold.
+
 define i1 @add_nsw_nuw_sgt(i8 %x) {
 ; CHECK-LABEL: @add_nsw_nuw_sgt(
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[ADD]], -124
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add = add nsw nuw i8 %x, 5
   %cmp = icmp sgt i8 %add, -124
   ret i1 %cmp
 }
 
-; minimum x is -128, so add could be -124.
+; negative test - minimum x is -128, so add could be -124.
 
 define i1 @add_nsw_sgt_limit(i8 %x) {
 ; CHECK-LABEL: @add_nsw_sgt_limit(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i8 [[X:%.*]], 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[ADD]], -124
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i8 %x, 4
   %cmp = icmp sgt i8 %add, -124
   ret i1 %cmp
 }
 
 define i1 @add_nsw_slt(i8 %x) {
 ; CHECK-LABEL: @add_nsw_slt(
 ; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw i8 %x, 5
   %cmp = icmp slt i8 %add, -123
   ret i1 %cmp
 }
 
+; nuw should not inhibit the fold.
+
 define i1 @add_nsw_nuw_slt(i8 %x) {
 ; CHECK-LABEL: @add_nsw_nuw_slt(
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ADD]], -123
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw nuw i8 %x, 5
   %cmp = icmp slt i8 %add, -123
   ret i1 %cmp
 }
 
-; minimum x is -128, so add could be -123.
+; negative test - minimum x is -128, so add could be -123.
 
 define i1 @add_nsw_slt_limit(i8 %x) {
 ; CHECK-LABEL: @add_nsw_slt_limit(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ADD]], -122
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i8 %x, 5

llvm/unittests/Analysis/ValueTrackingTest.cpp

define i32 @test(i32 %stride) {
     call void @llvm.assume(i1 %lt)
     %stride.plus.one = add nsw nuw i32 %stride, 1
     ret i32 %stride.plus.one
   })");
     Function *F = M->getFunction("test");
 
     AssumptionCache AC(*F);
     Value *Stride = &*F->arg_begin();
-    ConstantRange CR1 = computeConstantRange(Stride, true, &AC, nullptr);
+    ConstantRange CR1 = computeConstantRange(Stride, false, true, &AC, nullptr);
     EXPECT_TRUE(CR1.isFullSet());
 
     Instruction *I = &findInstructionByName(F, "stride.plus.one");
-    ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
+    ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I);
     EXPECT_EQ(5, CR2.getLower());
     EXPECT_EQ(10, CR2.getUpper());
   }
 
   {
     // Assumptions:
     //  * stride >= 5
     //  * stride < 200
define i32 @test(i32 %stride) {
     %stride.plus.one = add nsw nuw i32 %stride, 1
     ret i32 %stride.plus.one
   })");
     Function *F = M->getFunction("test");
 
     AssumptionCache AC(*F);
     Value *Stride = &*F->arg_begin();
     Instruction *I = &findInstructionByName(F, "stride.plus.one");
-    ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
+    ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I);
     EXPECT_EQ(99, *CR.getSingleElement());
   }
 
   {
     // Assumptions:
     //  * stride >= 5
     //  * stride >= 50
     //  * stride < 100
TEST_F(ValueTrackingTest, ComputeConstantRange) {
   bb2:
     ret i32 0
   })");
     Function *F = M->getFunction("test");
 
     AssumptionCache AC(*F);
     Value *Stride = &*F->arg_begin();
     Instruction *GT2 = &findInstructionByName(F, "gt.2");
-    ConstantRange CR = computeConstantRange(Stride, true, &AC, GT2);
+    ConstantRange CR = computeConstantRange(Stride, false, true, &AC, GT2);
     EXPECT_EQ(5, CR.getLower());
     EXPECT_EQ(0, CR.getUpper());
 
     Instruction *I = &findInstructionByName(F, "stride.plus.one");
-    ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
+    ConstantRange CR2 = computeConstantRange(Stride, false, true, &AC, I);
     EXPECT_EQ(50, CR2.getLower());
     EXPECT_EQ(100, CR2.getUpper());
   }
 
   {
     // Assumptions:
     //  * stride > 5
     //  * stride < 5
define i32 @test(i32 %stride, i1 %cond) {
     ret i32 %stride.plus.one
   })");
     Function *F = M->getFunction("test");
 
     AssumptionCache AC(*F);
     Value *Stride = &*F->arg_begin();
 
     Instruction *I = &findInstructionByName(F, "stride.plus.one");
-    ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
+    ConstantRange CR = computeConstantRange(Stride, false, true, &AC, I);
     EXPECT_TRUE(CR.isEmptySet());
   }
 
   {
     // Assumptions:
     //  * x.1 >= 5
     //  * x.2 < x.1
     //
TEST_F(ValueTrackingTest, ComputeConstantRange) {
   })");
     Function *F = M->getFunction("test");
 
     AssumptionCache AC(*F);
     Value *X1 = &*(F->arg_begin());
     Value *X2 = &*std::next(F->arg_begin());
 
     Instruction *I = &findInstructionByName(F, "stride.plus.one");
-    ConstantRange CR1 = computeConstantRange(X1, true, &AC, I);
-    ConstantRange CR2 = computeConstantRange(X2, true, &AC, I);
+    ConstantRange CR1 = computeConstantRange(X1, false, true, &AC, I);
+    ConstantRange CR2 = computeConstantRange(X2, false, true, &AC, I);
 
     EXPECT_EQ(5, CR1.getLower());
     EXPECT_EQ(0, CR1.getUpper());
 
     EXPECT_EQ(0, CR2.getLower());
     EXPECT_EQ(0xffffffff, CR2.getUpper());
 
     // Check the depth cutoff results in a conservative result (full set) by
     // passing Depth == MaxDepth == 6.
-    ConstantRange CR3 = computeConstantRange(X2, true, &AC, I, nullptr, 6);
+    ConstantRange CR3 = computeConstantRange(X2, false, true, &AC, I, nullptr, 6);
     EXPECT_TRUE(CR3.isFullSet());
   }
   {
     // Assumptions:
     //  * x.2 <= x.1
     auto M = parseModule(R"(
   declare void @llvm.assume(i1)
 
   define i32 @test(i32 %x.1, i32 %x.2) {
     %lt = icmp ule i32 %x.2, %x.1
     call void @llvm.assume(i1 %lt)
     %stride.plus.one = add nsw nuw i32 %x.1, 1
     ret i32 %stride.plus.one
   })");
     Function *F = M->getFunction("test");
 
     AssumptionCache AC(*F);
     Value *X2 = &*std::next(F->arg_begin());
 
     Instruction *I = &findInstructionByName(F, "stride.plus.one");
-    ConstantRange CR1 = computeConstantRange(X2, true, &AC, I);
+    ConstantRange CR1 = computeConstantRange(X2, false, true, &AC, I);
     // If we don't know the value of x.2, we don't know the value of x.1.
     EXPECT_TRUE(CR1.isFullSet());
   }
 }
 
 struct FindAllocaForValueTestParams {
   const char *IR;
   bool AnyOffsetResult;