[SCEV] Don't update the range value if empty

[davide]

Summary

The recent commit 22ca38da25e19a7c5fcfeb3f22159aba92ec381e introduces the ability to analyze ranges for heap allocations.

In some cases, like the one in the test, the range is empty as ConstantRange represents an half-open range on the upper side (in the very specific case, [1;1)). Detect this case, similarly to other ranges transformations in SCEV, rather than crashing.

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

[davide]

https://github.com/llvm/llvm-project/issues/63856 contains a full C++ testcase.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

6838

It would be better to use ConstantRange::getNonEmpty() here.

llvm/test/Transforms/LoopStrengthReduce/scev-operator-new.ll

25

Please add the test to llvm/test/Analysis/ScalarEvolution/malloc.ll, with the same testing approach used there.

[fhahn]

Could you add something like Fixes https://github.com/llvm/llvm-project/issues/63856 to the description/commit message so the GitHub issue gets auto-closed when the commit lands?

[davide]

Addressed @nikic and @fhahn review comments

[davide]

Reupload with context.

[fhahn]

LGTM thanks. I think the title still needs updating to match the latest implementation.

llvm/test/Analysis/ScalarEvolution/malloc.ll

28

it would probably be good to use a more descriptive name making it clear that this is with operator new and full range? Also, could mention the issue

llvm/test/Transforms/LoopStrengthReduce/scev-operator-new.ll

1

Does this test add anything over the one in malloc.ll? If not, probably best to remove it.

[nikic]

To be clear, the test I expected to see here is just this:

define ptr @size_max() {
  %alloc = call nonnull ptr @malloc(i64 -1)
  ret ptr %alloc
}

This is enough to reproduce the assertion failure for me.

llvm/test/Analysis/ScalarEvolution/malloc.ll

4

Why does this need a data layout?

34

Can reuse malloc.

40

This loop shouldn't be necessary.

[davide]

I would like to apologize for dropping the ball here, I'm coming back to this in the next day or two.

[davide]

https://reviews.llvm.org/D159160 fixes the same problem and has been committed.

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);
 
         for (const auto &Op : Phi->operands()) {

llvm/test/Analysis/ScalarEvolution/malloc.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
 
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
 define ptr @f() {
 ; CHECK-LABEL: 'f'
 ; CHECK-NEXT:  Classifying expressions for: @f
 ; CHECK-NEXT:    %alloc = tail call dereferenceable(64) ptr @malloc(i64 64)
 ; CHECK-NEXT:    --> %alloc U: [1,-64) S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @f
 ;
   %alloc = tail call dereferenceable(64) ptr @malloc(i64 64)
   ret ptr %alloc
 }
 
 define ptr @f2() {
 ; CHECK-LABEL: 'f2'
 ; CHECK-NEXT:  Classifying expressions for: @f2
 ; 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 void @patatino() {
+; CHECK-LABEL: 'patatino'
+; CHECK-NEXT: Classifying expressions for: @patatino
+; CHECK-NEXT: %call443 = tail call nonnull ptr @_Znam(i64 -1)
+; CHECK-NEXT: --> %call443 U: full-set S: full-set
+entry:
+  %call443 = tail call nonnull ptr @_Znam(i64 -1)
+  br label %for.cond9
+
+for.cond9:
+  %lsr.iv = phi ptr [ %call443, %entry ], [ %scevgep, %for.cond9 ]
+  %scevgep = getelementptr i8, ptr %lsr.iv, i64 4
+  br label %for.cond9
+}
+
+declare ptr @_Znam(i64)
+
 declare noalias noundef ptr @malloc(i64 noundef) allockind("alloc,uninitialized") allocsize(0)

llvm/test/Transforms/LoopStrengthReduce/scev-operator-new.ll

+; RUN: opt < %s -passes=loop-reduce -S | FileCheck %s
+
+; CHECK: define void @patatino() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:  br label %for.cond9
+
+; CHECK: for.cond9:
+; CHECK-NEXT:  br label %for.cond9
+; CHECK-NEXT:}
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @patatino() {
+entry:
+  %call443 = tail call nonnull ptr @_Znam(i64 -1)
+  br label %for.cond9
+
+for.cond9:
+  %lsr.iv = phi ptr [ %call443, %entry ], [ %scevgep, %for.cond9 ]
+  %scevgep = getelementptr i8, ptr %lsr.iv, i64 4
+  br label %for.cond9
+}
+
+declare ptr @_Znam(i64)