[BasicAA] Add add-hoc rule to distinguish different fields in arrays of structs.

[ab]

Summary

As discussed on the ML, here is a draft patch that implements some BasicAA improvements to struct GEPs.
It's very naive, but does the trick. I don't think it can reuse much of the GEP decomposition machinery, so it just checks indices manually.

How does it sound?

Hidden behind a flag to ease pre-commit testing; on the few added testcases, we go from:

5 no alias responses (4.9%)

to

25 no alias responses (24.7%)

Also, I obviously added Chandler's counterexample, thanks again ;)

[chandlerc]

lib/Analysis/BasicAliasAnalysis.cpp

45–46 ↗

(On Diff #19449)

Why do we need a flag here? If we discover bugs, we can just revert to green.

1021 ↗

(On Diff #19449)

Please extract this into a helper function and use early return to simplify all of the flag usage.

1033–1034 ↗

(On Diff #19449)

I would add to this comment an explanation of why we don't need to consider the array indices. I had to think quite some time to fully convince myself this is correct. Something along the lines of:

Because both GEPs begin indexing from the exact same pointer, and only index through arrays prior to the constant index into a struct, 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.

1037–1043 ↗

(On Diff #19449)

Sink all of this into the lambda and capture LastIndexedType instead? Then you can just pass C1 and C2 to the lambda.

1055 ↗

(On Diff #19449)

No need for else after return.

[ab]

lib/Analysis/BasicAliasAnalysis.cpp

45–46 ↗

(On Diff #19449)

Right, we don't, it was only in case you had some nice corner cases you wanted to test.

1033–1034 ↗

(On Diff #19449)

Added the explanation verbatim, thanks!

1037–1043 ↗

(On Diff #19449)

Eh, you'd still need to get the offsets; you might as well avoid doing it twice. I removed the *Idx variables though, makes it more readable.

[ab]

Various cleanups suggested by Chandler.

[chandlerc]

lib/Analysis/BasicAliasAnalysis.cpp

1016–1020 ↗

(On Diff #19520)

I still think this would all be much more readable in a separate static helper function rather than being inlined (even using lambdas heavily like this to get early return).

This lambda wouldn't be needed, the code would be much less indented, and it would be a good place to hang the high-level comments about this approach, and a good place to add other structural analysis of GEPs in the future.

[ab]

Extract analysis into separate function.

[ab]

Thanks for the review!

lib/Analysis/BasicAliasAnalysis.cpp

1016–1020 ↗

(On Diff #19520)

Fair enough; did that, and made it return AA::AliasResult. The name is overly specific, but for now that's fine.

[chandlerc]

This is looking really nice now. A minor comment below to try to lay some groundwork for any future enhancements here. Feel free to submit with that addressed.

lib/Analysis/BasicAliasAnalysis.cpp

893–898 ↗

(On Diff #19527)

I would probably comment this and name it as something more general so someone else would think to add more logic here rather than in the function below.

Specifically, I think the right interesting criteria is when we have two GEPs off of the exact same pointer.

If we come up with any other ways to analyze two GEPs themselves when starting from the same pointer and concluding no-alias, it would make sense to me to add that logic here.

(Naturally, I would hoist the pointer operand comparison up to the caller, and just leave the check on the number if indices here.

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS1,
   // particular memory location.
   if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2))
     return NoModRef;
 
   // The AliasAnalysis base class has some smarts, lets use them.
   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),
 /// UnderlyingV2 is the same for V2.
 ///
 AliasAnalysis::AliasResult
 BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
                              const AAMDNodes &V1AAInfo,
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
 
     // DecomposeGEPExpression and GetUnderlyingObject should return the
     // same result except when DecomposeGEPExpression has no DataLayout.
     if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
       assert(!DL &&
              "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;
 
     // Subtract the GEP2 pointer from the GEP1 pointer to find out their
     // symbolic difference.
     GEP1BaseOffset -= GEP2BaseOffset;
     GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices);

llvm/trunk/test/Analysis/BasicAA/struct-geps.ll

+; 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
+}