[BasicAA] Use dereferenceability to reason about aliasing

[jdoerfert]

Summary

We already use the fact that an object with known size X does not alias
another objection of size Y > X before. With this commit, we use
dereferenceability information to determine a lower bound for Y and not
only rely on the user provided query size.

The result for @global_and_deref_arg_2() and @local_and_deref_ret_2()
in test/Analysis/BasicAA/dereferenceable.ll improved with this patch.

[hfinkel]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

236

extend -> extent

llvm/test/Analysis/BasicAA/dereferenceable.ll

5

All of these tests check for the 'NoAlias' case. Can you please also add some checks for some associated MayAlias cases to insure that we're not accidentally getting too much?

[jdoerfert]

Fix typo and add baseline tests

[hfinkel]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

static bool isObjectSmallerThan(const Value *V, uint64_t Size,
   // This function needs to use the aligned object size because we allow
   // reads a bit past the end given sufficient alignment.
   uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc,
                                       /*RoundToAlign*/ true);
 
   return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size;
 }
 
+/// Return the minimal extent from \p V to the end of the underlying object,
+/// assuming the result is used in an aliasing query. E.g., we do use the query
+/// location size and the fact that null pointers cannot alias here.
+static uint64_t getMinimalExtentFrom(const Value &V,
+                                     const LocationSize &LocSize,
+                                     const DataLayout &DL,
+                                     bool NullIsValidLoc) {
+  // If we have dereferenceability information we know a lower bound for the
+  // extent as accesses for a lower offset would be valid. We need to exclude
+  // the "or null" part if null is a valid pointer.
+  bool CanBeNull;
+  uint64_t DerefBytes = V.getPointerDereferenceableBytes(DL, CanBeNull);
+  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;
+}
+
 /// 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 ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI,
-                                                 NullIsValidLocation)) ||
-      (V2Size.isPrecise() && isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI,
-                                                 NullIsValidLocation)))
+  if ((isObjectSmallerThan(
+          O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,
+          TLI, NullIsValidLocation)) ||
+      (isObjectSmallerThan(
+          O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), 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/dereferenceable.ll

+; RUN: opt -basicaa -print-all-alias-modref-info -aa-eval -analyze < %s 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@G = global i32 0, align 4
+
+define i64 @global_and_deref_arg_1(i64* dereferenceable(8) %arg) {
+; CHECK:     Function: global_and_deref_arg_1: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* @G, i64* %arg
+bb:
+  store i64 1, i64* %arg, align 8
+  store i32 0, i32* @G, align 4
+  %tmp = load i64, i64* %arg, align 8
+  ret i64 %tmp
+}
+
+define i32 @global_and_deref_arg_2(i32* dereferenceable(8) %arg) {
+; CHECK:     Function: global_and_deref_arg_2: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* %arg, i32* @G
+bb:
+  store i32 1, i32* %arg, align 8
+  store i32 0, i32* @G, align 4
+  %tmp = load i32, i32* %arg, align 8
+  ret i32 %tmp
+}
+
+define i32 @byval_and_deref_arg_1(i32* byval %obj, i64* dereferenceable(8) %arg) {
+; CHECK:     Function: byval_and_deref_arg_1: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* %obj, i64* %arg
+bb:
+  store i32 1, i32* %obj, align 4
+  store i64 0, i64* %arg, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+define i32 @byval_and_deref_arg_2(i32* byval %obj, i32* dereferenceable(8) %arg) {
+; CHECK:     Function: byval_and_deref_arg_2: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* %arg, i32* %obj
+bb:
+  store i32 1, i32* %obj, align 4
+  store i32 0, i32* %arg, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+declare dereferenceable(8) i32* @get_i32_deref8()
+declare dereferenceable(8) i64* @get_i64_deref8()
+declare void @unknown(i32*)
+
+define i32 @local_and_deref_ret_1() {
+; CHECK:     Function: local_and_deref_ret_1: 2 pointers, 2 call sites
+; CHECK-NEXT:  NoAlias: i32* %obj, i64* %ret
+bb:
+  %obj = alloca i32
+  call void @unknown(i32* %obj)
+  %ret = call dereferenceable(8) i64* @get_i64_deref8()
+  store i32 1, i32* %obj, align 4
+  store i64 0, i64* %ret, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+define i32 @local_and_deref_ret_2() {
+; CHECK:     Function: local_and_deref_ret_2: 2 pointers, 2 call sites
+; CHECK-NEXT:  NoAlias: i32* %obj, i32* %ret
+bb:
+  %obj = alloca i32
+  call void @unknown(i32* %obj)
+  %ret = call dereferenceable(8) i32* @get_i32_deref8()
+  store i32 1, i32* %obj, align 4
+  store i32 0, i32* %ret, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+
+; Baseline tests, same as above but with 2 instead of 8 dereferenceable bytes.
+
+define i64 @global_and_deref_arg_non_deref_1(i64* dereferenceable(2) %arg) {
+; CHECK:     Function: global_and_deref_arg_non_deref_1: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* @G, i64* %arg
+bb:
+  store i64 1, i64* %arg, align 8
+  store i32 0, i32* @G, align 4
+  %tmp = load i64, i64* %arg, align 8
+  ret i64 %tmp
+}
+
+define i32 @global_and_deref_arg_non_deref_2(i32* dereferenceable(2) %arg) {
+; CHECK:     Function: global_and_deref_arg_non_deref_2: 2 pointers, 0 call sites
+; Different result than above (see @global_and_deref_arg_2).
+; CHECK-NEXT:  MayAlias:  i32* %arg, i32* @G
+bb:
+  store i32 1, i32* %arg, align 8
+  store i32 0, i32* @G, align 4
+  %tmp = load i32, i32* %arg, align 8
+  ret i32 %tmp
+}
+
+define i32 @byval_and_deref_arg_non_deref_1(i32* byval %obj, i64* dereferenceable(2) %arg) {
+; CHECK:     Function: byval_and_deref_arg_non_deref_1: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* %obj, i64* %arg
+bb:
+  store i32 1, i32* %obj, align 4
+  store i64 0, i64* %arg, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+define i32 @byval_and_deref_arg_non_deref_2(i32* byval %obj, i32* dereferenceable(2) %arg) {
+; CHECK:     Function: byval_and_deref_arg_non_deref_2: 2 pointers, 0 call sites
+; CHECK-NEXT:  NoAlias: i32* %arg, i32* %obj
+bb:
+  store i32 1, i32* %obj, align 4
+  store i32 0, i32* %arg, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+declare dereferenceable(2) i32* @get_i32_deref2()
+declare dereferenceable(2) i64* @get_i64_deref2()
+
+define i32 @local_and_deref_ret_non_deref_1() {
+; CHECK:     Function: local_and_deref_ret_non_deref_1: 2 pointers, 2 call sites
+; CHECK-NEXT:  NoAlias: i32* %obj, i64* %ret
+bb:
+  %obj = alloca i32
+  call void @unknown(i32* %obj)
+  %ret = call dereferenceable(2) i64* @get_i64_deref2()
+  store i32 1, i32* %obj, align 4
+  store i64 0, i64* %ret, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}
+
+define i32 @local_and_deref_ret_non_deref_2() {
+; CHECK:     Function: local_and_deref_ret_non_deref_2: 2 pointers, 2 call sites
+; Different result than above (see @local_and_deref_ret_2).
+; CHECK-NEXT:  MayAlias:  i32* %obj, i32* %ret
+bb:
+  %obj = alloca i32
+  call void @unknown(i32* %obj)
+  %ret = call dereferenceable(2) i32* @get_i32_deref2()
+  store i32 1, i32* %obj, align 4
+  store i32 0, i32* %ret, align 8
+  %tmp = load i32, i32* %obj, align 4
+  ret i32 %tmp
+}