[ScalarEvolution] Analyze ranges for heap allocations

[aeubanks]

Summary

Followup to D153624. Allows for better exit count calculations for loops checking heap allocations against null.

[nikic]

LGTM

[xbolva00]

llvm/lib/Analysis/ScalarEvolution.cpp

6813

Update comment

[aeubanks]

llvm/lib/Analysis/ScalarEvolution.cpp

6813

missed this before submitting, done in b4d9cd2d61c037996ba972becbe45b79df99a15a

llvm/lib/Analysis/ScalarEvolution.cpp

if (Known.getMinValue() != Known.getMaxValue() + 1)
           RangeType);
     if (NS > 1)
       ConservativeResult = ConservativeResult.intersectWith(
           ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
                         APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1),
           RangeType);
 
     if (U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
       // Strengthen the range if the underlying IR value is a global/alloca
       // using the size of the object.
       ObjectSizeOpts Opts;
       Opts.RoundToAlign = false;
       Opts.NullIsUnknownSize = true;
       uint64_t ObjSize;
-      if ((isa<GlobalVariable>(V) || isa<AllocaInst>(V)) &&
+      if ((isa<GlobalVariable>(V) || isa<AllocaInst>(V) ||
+           isAllocationFn(V, &TLI)) &&
           getObjectSize(V, ObjSize, DL, &TLI, Opts) && ObjSize > 1) {
         // The highest address the object can start is ObjSize bytes before the
         // end (unsigned max value). If this value is not a multiple of the
         // alignment, the last possible start value is the next lowest multiple
         // of the alignment. Note: The computations below cannot overflow,
         // because if they would there's no possible start address for the
         // object.
         APInt MaxVal = APInt::getMaxValue(BitWidth) - APInt(BitWidth, ObjSize);

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
 
 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: full-set S: full-set
+; 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: full-set S: full-set
+; 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
 }
 
 declare noalias noundef ptr @malloc(i64 noundef) allockind("alloc,uninitialized") allocsize(0)

llvm/test/Transforms/PhaseOrdering/gep-null-compare-in-loop.ll

 ; CHECK-SAME: () local_unnamed_addr #[[ATTR1:[0-9]+]] {
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[ALLOC:%.*]] = tail call dereferenceable_or_null(64) ptr @malloc(i64 64)
 ; CHECK-NEXT:    store i32 1, ptr [[ALLOC]], align 4
 ; CHECK-NEXT:    [[GETELEMENTPTR:%.*]] = getelementptr i32, ptr [[ALLOC]], i64 1
 ; CHECK-NEXT:    store i32 2, ptr [[GETELEMENTPTR]], align 4
 ; CHECK-NEXT:    [[GETELEMENTPTR1:%.*]] = getelementptr i32, ptr [[ALLOC]], i64 2
 ; CHECK-NEXT:    store i32 3, ptr [[GETELEMENTPTR1]], align 4
-; CHECK-NEXT:    [[GETELEMENTPTR2:%.*]] = getelementptr i32, ptr [[ALLOC]], i64 3
-; CHECK-NEXT:    br label [[BB11_I:%.*]]
-; CHECK:       bb11.i:
-; CHECK-NEXT:    [[PHI37_I:%.*]] = phi i32 [ [[ADD_I:%.*]], [[BB11_I]] ], [ 0, [[BB:%.*]] ]
-; CHECK-NEXT:    [[PHI6_I:%.*]] = phi ptr [ [[SPEC_SELECT_I:%.*]], [[BB11_I]] ], [ [[ALLOC]], [[BB]] ]
-; CHECK-NEXT:    [[SPEC_SELECT_I]] = getelementptr i32, ptr [[PHI6_I]], i64 1
-; CHECK-NEXT:    [[LOAD_I:%.*]] = load i32, ptr [[PHI6_I]], align 4
-; CHECK-NEXT:    [[ADD_I]] = add i32 [[LOAD_I]], [[PHI37_I]]
-; CHECK-NEXT:    [[ICMP4_I:%.*]] = icmp ne ptr [[SPEC_SELECT_I]], [[GETELEMENTPTR2]]
-; CHECK-NEXT:    [[ICMP102_I:%.*]] = icmp ne ptr [[SPEC_SELECT_I]], null
-; CHECK-NEXT:    [[ICMP10_NOT_I:%.*]] = and i1 [[ICMP102_I]], [[ICMP4_I]]
-; CHECK-NEXT:    br i1 [[ICMP10_NOT_I]], label [[BB11_I]], label [[LOOP_EXIT:%.*]]
-; CHECK:       loop.exit:
-; CHECK-NEXT:    ret i32 [[ADD_I]]
+; CHECK-NEXT:    [[SPEC_SELECT_I:%.*]] = getelementptr i32, ptr [[ALLOC]], i64 1
+; CHECK-NEXT:    [[LOAD_I:%.*]] = load i32, ptr [[ALLOC]], align 4
+; CHECK-NEXT:    [[SPEC_SELECT_I_1:%.*]] = getelementptr i32, ptr [[ALLOC]], i64 2
+; CHECK-NEXT:    [[LOAD_I_1:%.*]] = load i32, ptr [[SPEC_SELECT_I]], align 4
+; CHECK-NEXT:    [[ADD_I_1:%.*]] = add i32 [[LOAD_I_1]], [[LOAD_I]]
+; CHECK-NEXT:    [[LOAD_I_2:%.*]] = load i32, ptr [[SPEC_SELECT_I_1]], align 4
+; CHECK-NEXT:    [[ADD_I_2:%.*]] = add i32 [[LOAD_I_2]], [[ADD_I_1]]
+; CHECK-NEXT:    ret i32 [[ADD_I_2]]
 ;
 bb:
   %alloc = call dereferenceable_or_null(64) ptr @malloc(i64 64)
   store i32 1, ptr %alloc, align 4
   %getelementptr = getelementptr i32, ptr %alloc, i64 1
   store i32 2, ptr %getelementptr, align 4
   %getelementptr1 = getelementptr i32, ptr %alloc, i64 2
   store i32 3, ptr %getelementptr1, align 4
   %getelementptr2 = getelementptr i32, ptr %alloc, i64 3
   %call = call i32 @loop(ptr %alloc, ptr %getelementptr2)
   ret i32 %call
 }
 
 declare ptr @malloc(i64)
 
 declare void @free(ptr)