[BasicAA] Integrate MaxObjSize for NoAlias

[atmnpatel]

Summary

With the introduction of the maxobjsize attribute (D87975, D87978), we should be able
to more easily determine when two objects cannot alias by using
dereferenceable as the lower bound on the object size and maxobjsize
as the upper bound on the object size, that is, if either object is
known to be at least larger than the other, we know that they cannot
alias. This patch implements these changes within BasicAliasAnalysis.

[fhahn]

llvm/test/Transforms/DeadStoreElimination/MSSA/calloc-store.ll

1 ↗

(On Diff #294481)

are there any real changes in this test? It does not use the new attribute, so are there changes expected?

llvm/test/Transforms/LoopVectorize/X86/pr23997.ll

30 ↗

(On Diff #294481)

are there any real changes in this test? looks like just renaming of value names in the IR?

[jdoerfert]

We need new tests specifically for this. Using the maxobjsize attribute especially

llvm/lib/Analysis/BasicAliasAnalysis.cpp

263

Add a comment above getPointerMaxObjSizeBytes stating that this is an over-approximation of the "extend till the end". In fact it is multi kinds of over-approximation, one of which is that it is an over-approximation of the maximal extend of the object, regardless of the offset \p V has into it.

llvm/test/Transforms/Attributor/readattrs.ll

158 ↗

(On Diff #294481)

We have to check if this is not unrelated. I'll run the update script on the attributor files again.

[jdoerfert]

Statistics changes for CTMark, this patch w/o maxobjsize deduction.

before_base.json.stats vs after_base.json.stats
CHANGED: branch-folder                NumHoist                                              438 ->        431 (    -1.598%)
CHANGED: codegenprepare               NumBlocksElim                                       16093 ->      15885 (    -1.292%)
CHANGED: codegenprepare               NumExtsMoved                                         6373 ->       6439 (    +1.036%)
CHANGED: gvn                          IsValueFullyAvailableInBlockNumSpeculationsMax       6746 ->       6858 (    +1.660%)
CHANGED: gvn                          NumGVNInstr                                         78434 ->      79330 (    +1.142%)
CHANGED: instcombine                  NumReassoc                                          22830 ->      23213 (    +1.678%)
CHANGED: instsimplify                 NumSimplified                                       21278 ->      21495 (    +1.020%)
CHANGED: licm                         NumPromoted                                           407 ->        497 (   +22.113%)
CHANGED: loop-rotate                  NumNotRotatedDueToHeaderSize                           37 ->         35 (    -5.405%)
CHANGED: loop-simplify                NumNested                                             126 ->        128 (    +1.587%)
CHANGED: machinelicm                  NumPostRAHoisted                                      131 ->        134 (    +2.290%)
CHANGED: memory-builtins              ObjectVisitorLoad                                   96077 ->      97496 (    +1.477%)
CHANGED: regalloc                     NumDCEFoldedLoads                                      38 ->         37 (    -2.632%)
CHANGED: regalloc                     NumLaneConflicts                                     4408 ->       4332 (    -1.724%)
CHANGED: regalloc                     NumReloadsRemoved                                    1062 ->       1050 (    -1.130%)
CHANGED: regalloc                     NumSnippets                                          1168 ->       1152 (    -1.370%)
CHANGED: regalloc                     NumSpillsRemoved                                      672 ->        665 (    -1.042%)
CHANGED: stack-slot-coloring          NumDead                                                14 ->         18 (   +28.571%)
CHANGED: twoaddressinstruction        NumConvertedTo3Addr                                 27054 ->      26695 (    -1.327%)

[atmnpatel]

Added a specific basic-aa maxobjsize test.

[jdoerfert]

The new test looks good. There are two tests in tree you need to fix (they improved), see the Unit test results from the pre-commit build.

[atmnpatel]

Fixed broken tests, think the changes make sense.

[efriedma]

Statistics changes for CTMark, this patch w/o maxobjsize deduction.

If this is profitable even without the maxobjsize actually being present anywhere, can we just land this before the maxobjsize attribute? I'm not sure I understand what this is doing differently from the existing isObjectSmallerThan check.

[atmnpatel]

I think that phrase ("w/o maxobjsize deduction") could be a bit misleading, IINM, when @jdoerfert says w/o maxobjsize deduction he means without having the functionality built into the attributor to update the maximum object size estimate. So in the patch D87975, there's a crude over-approximation for the maxobjsize (getPointerMaxObjSize) and the numbers are for just using that over-approximation without including the changes in D87978 that refine it, so we would still need the maxobjsize attribute first in order to do this.

[jdoerfert]

In D88353#2330829, @atmnpatel wrote:

I think that phrase ("w/o maxobjsize deduction") could be a bit misleading, IINM, when @jdoerfert says w/o maxobjsize deduction he means without having the functionality built into the attributor to update the maximum object size estimate. So in the patch D87975, there's a crude over-approximation for the maxobjsize (getPointerMaxObjSize) and the numbers are for just using that over-approximation without including the changes in D87978 that refine it, so we would still need the maxobjsize attribute first in order to do this.

I don't think we do. All the logic is there but since we never manifest maxobjsize to see this improvements we can commit this w/o the attribute part just fine. The attribute will come in when the Attributor deduces it, and when we annotate malloc and other library functions accordingly.

[efriedma]

In D88353#2330829, @atmnpatel wrote:

I think that phrase ("w/o maxobjsize deduction") could be a bit misleading, IINM, when @jdoerfert says w/o maxobjsize deduction he means without having the functionality built into the attributor to update the maximum object size estimate. So in the patch D87975, there's a crude over-approximation for the maxobjsize (getPointerMaxObjSize) and the numbers are for just using that over-approximation without including the changes in D87978 that refine it, so we would still need the maxobjsize attribute first in order to do this.

As far as I can tell, without D87978, clang-generated IR won't contain any maxobjsize attributes. So any changes to the generated code are unrelated to maxobjsize attribute.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

static uint64_t getMinimalExtentFrom(const Value &V,
   DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes;
   // If queried with a precise location size, we assume that location size to be
   // accessed, thus valid.
   if (LocSize.isPrecise())
     DerefBytes = std::max(DerefBytes, LocSize.getValue());
   return DerefBytes;
 }
 
+/// Return the maximal extent from \p V to the end of the underlying object,
+/// assuming the result is used in an aliasing query.
+static uint64_t getMaximalExtentFrom(const Value &V,
+                                     const LocationSize &LocSize,
+                                     const DataLayout &DL) {
+  // This is an over-approximation of the number of bytes until the end of
+  // the object. This approximation ignores the offset in \p V.
+  return V.getPointerMaxObjSizeBytes(DL);
+}
+
 /// Returns true if we can prove that the object specified by V has size Size.
 static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
                          const TargetLibraryInfo &TLI, bool NullIsValidLoc) {
   uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc);
   return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
 }
 
 //===----------------------------------------------------------------------===//
if (O1 != O2) {
     if (isEscapeSource(O2) &&
         isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache))
       return NoAlias;
   }
 
   // If the size of one access is larger than the entire object on the other
   // side, then we know such behavior is undefined and can assume no alias.
   bool NullIsValidLocation = NullPointerIsDefined(&F);
-  if ((isObjectSmallerThan(
-          O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,
-          TLI, NullIsValidLocation)) ||
-      (isObjectSmallerThan(
-          O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL,
-          TLI, NullIsValidLocation)))
+  uint64_t V1MinSize =
+      getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation);
+  uint64_t V2MinSize =
+      getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation);
+  uint64_t V1MaxSize = getMaximalExtentFrom(*V1, V1Size, DL);
+  uint64_t V2MaxSize = getMaximalExtentFrom(*V2, V2Size, DL);
+
+  if (V1MaxSize < V2MinSize || V2MaxSize < V1MinSize ||
+      isObjectSmallerThan(O2, V1MinSize, DL, TLI, NullIsValidLocation) ||
+      isObjectSmallerThan(O1, V2MinSize, DL, TLI, NullIsValidLocation))
     return NoAlias;
 
   // Check the cache before climbing up use-def chains. This also terminates
   // otherwise infinitely recursive queries.
   AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
                             MemoryLocation(V2, V2Size, V2AAInfo));
   if (V1 > V2)
     std::swap(Locs.first, Locs.second);

llvm/test/Analysis/BasicAA/maxobjsize.ll

+; RUN: opt < %s -basic-aa -print-no-aliases -print-may-aliases -print-must-aliases -aa-eval -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @no_alias_1(i8* dereferenceable(1) maxobjsize(4) %a, i8* dereferenceable(5) maxobjsize(8) %b) {
+; CHECK: NoAlias:
+  ret void
+}
+
+define void @no_alias_2(i8* dereferenceable(5) maxobjsize(8) %a, i8* dereferenceable(1) maxobjsize(4) %b) {
+; CHECK: NoAlias:
+  ret void
+}
+
+define void @may_alias_1(i8* dereferenceable(1) maxobjsize(4) %a, i8* dereferenceable(2) maxobjsize(8) %b) {
+; CHECK: MayAlias:
+  ret void
+}
+
+define void @may_alias_2(i8* dereferenceable(2) maxobjsize(8) %a, i8* dereferenceable(1) maxobjsize(4) %b) {
+; CHECK: MayAlias:
+  ret void
+}
+
+define void @may_alias_3(i8* dereferenceable(4) maxobjsize(4) %a, i8* dereferenceable(4) maxobjsize(4) %b) {
+; CHECK: MayAlias:
+  ret void
+}
+

llvm/test/CodeGen/SystemZ/int-cmp-59.ll

 ; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z14 -O3 -stop-before=finalize-isel \
 ; RUN:   | FileCheck %s
 ;
 ; Check that an i1 in memory used in a comparison is loaded correctly.
 
 @bPtr = external dso_local local_unnamed_addr global i32*, align 8
 @c = external hidden unnamed_addr global i1, align 4
 
 define i64 @main() {
 ; CHECK-LABEL: bb.0.entry:
 ; CHECK: %1:addr64bit = LARL @c
-; CHECK: %2:gr64bit = LLGC %1, 0, $noreg :: (dereferenceable load 1 from @c, align 4)
-; CHECK-NEXT: %4:gr64bit = IMPLICIT_DEF
-; CHECK-NEXT: %3:gr64bit = RISBGN %4, killed %2, 63, 191, 0
-; CHECK-NEXT: %5:gr64bit = LCGR killed %3, implicit-def dead $cc
-; CHECK-NEXT: CGHI killed %5, 1, implicit-def $cc
+; CHECK: MVI killed %1, 0, 1 :: (store 1 into @c, align 4)
+; CHECK: MVHI killed %0, 0, 8 :: (store 4 into %ir.0)
+; CHECK: %2:gr64bit = LGHI 0
+; CHECK: $r2d = COPY %2
 entry:
   %0 = load i32*, i32** @bPtr
   store i1 true, i1* @c
   store i32 8, i32* %0
   %.b = load i1, i1* @c
   %conv.i = select i1 %.b, i64 1, i64 3
   %div.i = sdiv i64 -1, %conv.i
   %cmp.i = icmp eq i64 %div.i, 1
   %conv2.i = zext i1 %cmp.i to i64
   ret i64 %conv2.i
 }
 

llvm/test/Transforms/InstCombine/pr46680.ll

 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[I5:%.*]] = load i16, i16* [[ARG:%.*]], align 2
 ; CHECK-NEXT:    [[I6:%.*]] = trunc i16 [[I5]] to i8
 ; CHECK-NEXT:    store i8 [[I6]], i8* @c, align 1
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[I3]])
 ; CHECK-NEXT:    br label [[BB22:%.*]]
 ; CHECK:       bb13:
 ; CHECK-NEXT:    [[I14:%.*]] = load i16, i16* [[ARG]], align 2
-; CHECK-NEXT:    [[I15:%.*]] = trunc i16 [[I14]] to i8
-; CHECK-NEXT:    store i8 [[I15]], i8* @c, align 1
+; CHECK-NEXT:    [[I19:%.*]] = trunc i16 [[I14]] to i8
+; CHECK-NEXT:    store i8 [[I19]], i8* @c, align 1
 ; CHECK-NEXT:    br label [[BB22]]
 ; CHECK:       bb22:
-; CHECK-NEXT:    [[STOREMERGE2_IN:%.*]] = load i16, i16* [[ARG]], align 2
-; CHECK-NEXT:    [[STOREMERGE2:%.*]] = trunc i16 [[STOREMERGE2_IN]] to i8
-; CHECK-NEXT:    store i8 [[STOREMERGE2]], i8* @c, align 1
-; CHECK-NEXT:    [[STOREMERGE1_IN:%.*]] = load i16, i16* [[ARG]], align 2
-; CHECK-NEXT:    [[STOREMERGE1:%.*]] = trunc i16 [[STOREMERGE1_IN]] to i8
-; CHECK-NEXT:    store i8 [[STOREMERGE1]], i8* @c, align 1
-; CHECK-NEXT:    [[STOREMERGE_IN:%.*]] = load i16, i16* [[ARG]], align 2
+; CHECK-NEXT:    [[STOREMERGE_IN:%.*]] = phi i16 [ [[I5]], [[BB4]] ], [ [[I14]], [[BB13]] ]
 ; CHECK-NEXT:    [[STOREMERGE:%.*]] = trunc i16 [[STOREMERGE_IN]] to i8
 ; CHECK-NEXT:    store i8 [[STOREMERGE]], i8* @c, align 1
 ; CHECK-NEXT:    br label [[BB23:%.*]]
 ; CHECK:       bb23:
 ; CHECK-NEXT:    br label [[BB23]]
 ;
 bb:
   %i = load i64, i64* @d, align 8

polly/test/Isl/Ast/alias_checks_with_empty_context.ll

 bb18:                                             ; preds = %bb17
   br label %bb19
 
 bb19:                                             ; preds = %bb18, %bb17
   %tmp20 = phi i32* [ %tmp3, %bb17 ], [ bitcast (void ()* @hoge to i32*), %bb18 ]
   br label %bb1
 }
 
-; CHECK: if (1 && (&MemRef_global_1[1] <= &MemRef_tmp3[0] || &MemRef_tmp3[1] <= &MemRef_global_1[0]) && (&MemRef_tmp[1] <= &MemRef_tmp3[0] || &MemRef_tmp3[1] <= &MemRef_tmp[0]) && (&MemRef_tmp[1] <= &MemRef_global_1[0] || &MemRef_global_1[1] <= &MemRef_tmp[0]))
+; CHECK: if (1 && (&MemRef_global_1[1] <= &MemRef_tmp3[0] || &MemRef_tmp3[1] <= &MemRef_global_1[0]))
 
 ; CHECK:            for (int c0 = 0; c0 <= 64; c0 += 1) {
 ; CHECK-NEXT:         Stmt_bb7(c0);
 ; CHECK-NEXT:         Stmt_bb10(c0);
 ; CHECK-NEXT:       }
 
 ; CHECK: else
 ; CHECK-NEXT:     {  /* original code */ }