[SCEV] Fix potentially empty set for unsigned ranges

[tejas]

Summary

The following commit enabled the analysis of ranges for heap allocations:
22ca38da25e19a7c5fcfeb3f22159aba92ec381e

The range turns out to be empty in cases such as the one in test (which
is [1,1)), leading to an assertion failure. This patch fixes for the
same case.

Fixes https://github.com/llvm/llvm-project/issues/63856

[fhahn]

Looks like this fixes the same issue as D155255. @davide are you planning on addressing the outstanding comments for D155255?

[davide]

Fine to get this one instead.

[tejas]

@davide @fhahn Oops! I didn't check if there was already a patch about to be submitted. Pardon, I didn't check before sending this one in.

[fhahn]

LGTM, thanks!

llvm/test/Analysis/ScalarEvolution/malloc.ll

33

nit: fix indent here.

[fhahn]

Please add Fixes https://github.com/llvm/llvm-project/issues/63856 to the commit message to auto-close the related issue.

[tejas]

Added the github issue link for the fix.

[tejas]

@fhahn Can you please commit on my behalf? I do not have the permissions. Thanks!

llvm/lib/Analysis/ScalarEvolution.cpp

if (U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
         APInt MaxVal = APInt::getMaxValue(BitWidth) - APInt(BitWidth, ObjSize);
         uint64_t Align = U->getValue()->getPointerAlignment(DL).value();
         uint64_t Rem = MaxVal.urem(Align);
         MaxVal -= APInt(BitWidth, Rem);
         APInt MinVal = APInt::getZero(BitWidth);
         if (llvm::isKnownNonZero(V, DL))
           MinVal = Align;
         ConservativeResult = ConservativeResult.intersectWith(
-            {MinVal, MaxVal + 1}, RangeType);
+            ConstantRange::getNonEmpty(MinVal, MaxVal + 1), RangeType);
       }
     }
 
     // A range of Phi is a subset of union of all ranges of its input.
     if (PHINode *Phi = dyn_cast<PHINode>(V)) {
       // Make sure that we do not run over cycled Phis.
       if (PendingPhiRanges.insert(Phi).second) {
         ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false);

llvm/test/Analysis/ScalarEvolution/malloc.ll

 ; CHECK-NEXT:    %alloc = tail call dereferenceable_or_null(64) ptr @malloc(i64 64)
 ; CHECK-NEXT:    --> %alloc U: [0,-64) S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @f2
 ;
   %alloc = tail call dereferenceable_or_null(64) ptr @malloc(i64 64)
   ret ptr %alloc
 }
 
+define ptr @undefined_max() {
+; CHECK-LABEL: 'undefined_max'
+; CHECK-NEXT:  Classifying expressions for: @undefined_max
+; CHECK-NEXT:    %alloc = call nonnull ptr @malloc(i64 -1)
+; CHECK-NEXT:    -->  %alloc U: full-set S: full-set
+; CHECK-NEXT:  Determining loop execution counts for: @undefined_max
+;
+  %alloc = call nonnull ptr @malloc(i64 -1)
+  ret ptr %alloc
+}
+
 declare noalias noundef ptr @malloc(i64 noundef) allockind("alloc,uninitialized") allocsize(0)