[BasicAA] Try to disambiguate GEPs through arrays of structs into

different fields.

We can show that two GEPs off of the same (possibly multidimensional)
array of structs, into different fields, can't alias.  Quoting:

For two GEPOperators GEP1 and GEP2, if we find that:
- both GEPs begin indexing from the exact same pointer;
- the last indices in both GEPs are constants, indexing into a struct;
- said indices are different, hence,the pointed-to fields are different;
- and both GEPs only index through arrays prior to that;

this lets us determine that the struct that GEP1 indexes into and the
struct that GEP2 indexes into must either precisely overlap or be
completely disjoint.  Because they cannot partially overlap, indexing
into different non-overlapping fields of the struct will never alias.

The other BasicAA::aliasGEP rules worked in some cases, but not all
(for example, the i32x3 struct in the testcase).
We can add this simple ad-hoc rule to complement them.

rdar://19717375
Differential Revision: http://reviews.llvm.org/D7453

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@228498 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 7537f6e5423df9188e07c1f4dd9c0b393e23ddb0..46ca6ee91f5eaf84da7e2b0681267c8d18d9135d 100644 (file)
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -890,6 +890,99 @@ BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS1,
   return AliasAnalysis::getModRefInfo(CS1, CS2);
 }
 
+/// \brief Provide ad-hoc rules to disambiguate accesses through two GEP
+/// operators, both having the exact same pointer operand.
+static AliasAnalysis::AliasResult
+aliasSameBasePointerGEPs(const GEPOperator *GEP1, uint64_t V1Size,
+                         const GEPOperator *GEP2, uint64_t V2Size,
+                         const DataLayout &DL) {
+
+  assert(GEP1->getPointerOperand() == GEP2->getPointerOperand() &&
+         "Expected GEPs with the same pointer operand");
+
+  // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
+  // such that the struct field accesses provably cannot alias.
+  // We also need at least two indices (the pointer, and the struct field).
+  if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
+      GEP1->getNumIndices() < 2)
+    return AliasAnalysis::MayAlias;
+
+  // If we don't know the size of the accesses through both GEPs, we can't
+  // determine whether the struct fields accessed can't alias.
+  if (V1Size == AliasAnalysis::UnknownSize ||
+      V2Size == AliasAnalysis::UnknownSize)
+    return AliasAnalysis::MayAlias;
+
+  ConstantInt *C1 =
+      dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
+  ConstantInt *C2 =
+      dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
+
+  // If the last (struct) indices aren't constants, we can't say anything.
+  // If they're identical, the other indices might be also be dynamically
+  // equal, so the GEPs can alias.
+  if (!C1 || !C2 || C1 == C2)
+    return AliasAnalysis::MayAlias;
+
+  // Find the last-indexed type of the GEP, i.e., the type you'd get if
+  // you stripped the last index.
+  // On the way, look at each indexed type.  If there's something other
+  // than an array, different indices can lead to different final types.
+  SmallVector<Value *, 8> IntermediateIndices;
+
+  // Insert the first index; we don't need to check the type indexed
+  // through it as it only drops the pointer indirection.
+  assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine");
+  IntermediateIndices.push_back(GEP1->getOperand(1));
+
+  // Insert all the remaining indices but the last one.
+  // Also, check that they all index through arrays.
+  for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) {
+    if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
+            GEP1->getPointerOperandType(), IntermediateIndices)))
+      return AliasAnalysis::MayAlias;
+    IntermediateIndices.push_back(GEP1->getOperand(i + 1));
+  }
+
+  StructType *LastIndexedStruct =
+      dyn_cast<StructType>(GetElementPtrInst::getIndexedType(
+          GEP1->getPointerOperandType(), IntermediateIndices));
+
+  if (!LastIndexedStruct)
+    return AliasAnalysis::MayAlias;
+
+  // We know that:
+  // - both GEPs begin indexing from the exact same pointer;
+  // - the last indices in both GEPs are constants, indexing into a struct;
+  // - said indices are different, hence, the pointed-to fields are different;
+  // - both GEPs only index through arrays prior to that.
+  //
+  // This lets us determine that the struct that GEP1 indexes into and the
+  // struct that GEP2 indexes into must either precisely overlap or be
+  // completely disjoint.  Because they cannot partially overlap, indexing into
+  // different non-overlapping fields of the struct will never alias.
+
+  // Therefore, the only remaining thing needed to show that both GEPs can't
+  // alias is that the fields are not overlapping.
+  const StructLayout *SL = DL.getStructLayout(LastIndexedStruct);
+  const uint64_t StructSize = SL->getSizeInBytes();
+  const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue());
+  const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue());
+
+  auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
+                                      uint64_t V2Off, uint64_t V2Size) {
+    return V1Off < V2Off && V1Off + V1Size <= V2Off &&
+           ((V2Off + V2Size <= StructSize) ||
+            (V2Off + V2Size - StructSize <= V1Off));
+  };
+
+  if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
+      EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
+    return AliasAnalysis::NoAlias;
+
+  return AliasAnalysis::MayAlias;
+}
+
 /// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
 /// against another pointer.  We know that V1 is a GEP, but we don't know
 /// anything about V2.  UnderlyingV1 is GetUnderlyingObject(GEP1, DL),
@@ -997,6 +1090,17 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
              "DecomposeGEPExpression and GetUnderlyingObject disagree!");
       return MayAlias;
     }
+
+    // If we know the two GEPs are based off of the exact same pointer (and not
+    // just the same underlying object), see if that tells us anything about
+    // the resulting pointers.
+    if (DL && GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
+      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, *DL);
+      // If we couldn't find anything interesting, don't abandon just yet.
+      if (R != MayAlias)
+        return R;
+    }
+
     // If the max search depth is reached the result is undefined
     if (GEP2MaxLookupReached || GEP1MaxLookupReached)
       return MayAlias;

diff --git a/test/Analysis/BasicAA/struct-geps.ll b/test/Analysis/BasicAA/struct-geps.ll
new file mode 100644 (file)
index 0000000..3764d48
--- /dev/null
+++ b/test/Analysis/BasicAA/struct-geps.ll
@@ -0,0 +1,164 @@
+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct = type { i32, i32, i32 }
+
+; CHECK-LABEL: test_simple
+
+; CHECK-DAG: PartialAlias: %struct* %st, i32* %x
+; CHECK-DAG: PartialAlias: %struct* %st, i32* %y
+; CHECK-DAG: PartialAlias: %struct* %st, i32* %z
+
+; CHECK-DAG: NoAlias: i32* %x, i32* %y
+; CHECK-DAG: NoAlias: i32* %x, i32* %z
+; CHECK-DAG: NoAlias: i32* %y, i32* %z
+
+; CHECK-DAG: PartialAlias: %struct* %st, %struct* %y_12
+; CHECK-DAG: PartialAlias: %struct* %y_12, i32* %x
+; CHECK-DAG: PartialAlias: i32* %x, i80* %y_10
+
+; CHECK-DAG: PartialAlias: %struct* %st, i64* %y_8
+; CHECK-DAG: PartialAlias: i32* %z, i64* %y_8
+; CHECK-DAG: NoAlias: i32* %x, i64* %y_8
+
+; CHECK-DAG: MustAlias: %struct* %y_12, i32* %y
+; CHECK-DAG: MustAlias: i32* %y, i64* %y_8
+; CHECK-DAG: MustAlias: i32* %y, i80* %y_10
+
+define void @test_simple(%struct* %st, i64 %i, i64 %j, i64 %k) {
+  %x = getelementptr %struct* %st, i64 %i, i32 0
+  %y = getelementptr %struct* %st, i64 %j, i32 1
+  %z = getelementptr %struct* %st, i64 %k, i32 2
+  %y_12 = bitcast i32* %y to %struct*
+  %y_10 = bitcast i32* %y to i80*
+  %y_8 = bitcast i32* %y to i64*
+  ret void
+}
+
+; CHECK-LABEL: test_in_array
+
+; CHECK-DAG: PartialAlias: [1 x %struct]* %st, i32* %x
+; CHECK-DAG: PartialAlias: [1 x %struct]* %st, i32* %y
+; CHECK-DAG: PartialAlias: [1 x %struct]* %st, i32* %z
+
+; CHECK-DAG: NoAlias: i32* %x, i32* %y
+; CHECK-DAG: NoAlias: i32* %x, i32* %z
+; CHECK-DAG: NoAlias: i32* %y, i32* %z
+
+; CHECK-DAG: PartialAlias: %struct* %y_12, [1 x %struct]* %st
+; CHECK-DAG: PartialAlias: %struct* %y_12, i32* %x
+; CHECK-DAG: PartialAlias: i32* %x, i80* %y_10
+
+; CHECK-DAG: PartialAlias: [1 x %struct]* %st, i64* %y_8
+; CHECK-DAG: PartialAlias: i32* %z, i64* %y_8
+; CHECK-DAG: NoAlias: i32* %x, i64* %y_8
+
+; CHECK-DAG: MustAlias: %struct* %y_12, i32* %y
+; CHECK-DAG: MustAlias: i32* %y, i64* %y_8
+; CHECK-DAG: MustAlias: i32* %y, i80* %y_10
+
+define void @test_in_array([1 x %struct]* %st, i64 %i, i64 %j, i64 %k, i64 %i1, i64 %j1, i64 %k1) {
+  %x = getelementptr [1 x %struct]* %st, i64 %i, i64 %i1, i32 0
+  %y = getelementptr [1 x %struct]* %st, i64 %j, i64 %j1, i32 1
+  %z = getelementptr [1 x %struct]* %st, i64 %k, i64 %k1, i32 2
+  %y_12 = bitcast i32* %y to %struct*
+  %y_10 = bitcast i32* %y to i80*
+  %y_8 = bitcast i32* %y to i64*
+  ret void
+}
+
+; CHECK-LABEL: test_in_3d_array
+
+; CHECK-DAG: PartialAlias: [1 x [1 x [1 x %struct]]]* %st, i32* %x
+; CHECK-DAG: PartialAlias: [1 x [1 x [1 x %struct]]]* %st, i32* %y
+; CHECK-DAG: PartialAlias: [1 x [1 x [1 x %struct]]]* %st, i32* %z
+
+; CHECK-DAG: NoAlias: i32* %x, i32* %y
+; CHECK-DAG: NoAlias: i32* %x, i32* %z
+; CHECK-DAG: NoAlias: i32* %y, i32* %z
+
+; CHECK-DAG: PartialAlias: %struct* %y_12, [1 x [1 x [1 x %struct]]]* %st
+; CHECK-DAG: PartialAlias: %struct* %y_12, i32* %x
+; CHECK-DAG: PartialAlias: i32* %x, i80* %y_10
+
+; CHECK-DAG: PartialAlias: [1 x [1 x [1 x %struct]]]* %st, i64* %y_8
+; CHECK-DAG: PartialAlias: i32* %z, i64* %y_8
+; CHECK-DAG: NoAlias: i32* %x, i64* %y_8
+
+; CHECK-DAG: MustAlias: %struct* %y_12, i32* %y
+; CHECK-DAG: MustAlias: i32* %y, i64* %y_8
+; CHECK-DAG: MustAlias: i32* %y, i80* %y_10
+
+define void @test_in_3d_array([1 x [1 x [1 x %struct]]]* %st, i64 %i, i64 %j, i64 %k, i64 %i1, i64 %j1, i64 %k1, i64 %i2, i64 %j2, i64 %k2, i64 %i3, i64 %j3, i64 %k3) {
+  %x = getelementptr [1 x [1 x [1 x %struct]]]* %st, i64 %i, i64 %i1, i64 %i2, i64 %i3, i32 0
+  %y = getelementptr [1 x [1 x [1 x %struct]]]* %st, i64 %j, i64 %j1, i64 %j2, i64 %j3, i32 1
+  %z = getelementptr [1 x [1 x [1 x %struct]]]* %st, i64 %k, i64 %k1, i64 %k2, i64 %k3, i32 2
+  %y_12 = bitcast i32* %y to %struct*
+  %y_10 = bitcast i32* %y to i80*
+  %y_8 = bitcast i32* %y to i64*
+  ret void
+}
+
+; CHECK-LABEL: test_same_underlying_object_same_indices
+
+; CHECK-DAG: NoAlias: i32* %x, i32* %x2
+; CHECK-DAG: NoAlias: i32* %y, i32* %y2
+; CHECK-DAG: NoAlias: i32* %z, i32* %z2
+
+; CHECK-DAG: PartialAlias: i32* %x, i32* %y2
+; CHECK-DAG: PartialAlias: i32* %x, i32* %z2
+
+; CHECK-DAG: PartialAlias: i32* %x2, i32* %y
+; CHECK-DAG: PartialAlias: i32* %y, i32* %z2
+
+; CHECK-DAG: PartialAlias: i32* %x2, i32* %z
+; CHECK-DAG: PartialAlias: i32* %y2, i32* %z
+
+define void @test_same_underlying_object_same_indices(%struct* %st, i64 %i, i64 %j, i64 %k) {
+  %st2 = getelementptr %struct* %st, i32 10
+  %x2 = getelementptr %struct* %st2, i64 %i, i32 0
+  %y2 = getelementptr %struct* %st2, i64 %j, i32 1
+  %z2 = getelementptr %struct* %st2, i64 %k, i32 2
+  %x = getelementptr %struct* %st, i64 %i, i32 0
+  %y = getelementptr %struct* %st, i64 %j, i32 1
+  %z = getelementptr %struct* %st, i64 %k, i32 2
+  ret void
+}
+
+; CHECK-LABEL: test_same_underlying_object_different_indices
+
+; CHECK-DAG: PartialAlias: i32* %x, i32* %x2
+; CHECK-DAG: PartialAlias: i32* %y, i32* %y2
+; CHECK-DAG: PartialAlias: i32* %z, i32* %z2
+
+; CHECK-DAG: PartialAlias: i32* %x, i32* %y2
+; CHECK-DAG: PartialAlias: i32* %x, i32* %z2
+
+; CHECK-DAG: PartialAlias: i32* %x2, i32* %y
+; CHECK-DAG: PartialAlias: i32* %y, i32* %z2
+
+; CHECK-DAG: PartialAlias: i32* %x2, i32* %z
+; CHECK-DAG: PartialAlias: i32* %y2, i32* %z
+
+define void @test_same_underlying_object_different_indices(%struct* %st, i64 %i1, i64 %j1, i64 %k1, i64 %i2, i64 %k2, i64 %j2) {
+  %st2 = getelementptr %struct* %st, i32 10
+  %x2 = getelementptr %struct* %st2, i64 %i2, i32 0
+  %y2 = getelementptr %struct* %st2, i64 %j2, i32 1
+  %z2 = getelementptr %struct* %st2, i64 %k2, i32 2
+  %x = getelementptr %struct* %st, i64 %i1, i32 0
+  %y = getelementptr %struct* %st, i64 %j1, i32 1
+  %z = getelementptr %struct* %st, i64 %k1, i32 2
+  ret void
+}
+
+
+%struct2 = type { [1 x { i32, i32 }], [2 x { i32 }] }
+
+; CHECK-LABEL: test_struct_in_array
+; CHECK-DAG: MustAlias: i32* %x, i32* %y
+define void @test_struct_in_array(%struct2* %st, i64 %i, i64 %j, i64 %k) {
+  %x = getelementptr %struct2* %st, i32 0, i32 1, i32 1, i32 0
+  %y = getelementptr %struct2* %st, i32 0, i32 0, i32 1, i32 1
+  ret void
+}