[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

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

1019

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

1031–1032

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.

1035–1041

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

1053

No need for else after return.

[ab]

lib/Analysis/BasicAliasAnalysis.cpp

45–46

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

1031–1032

Added the explanation verbatim, thanks!

1035–1041

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

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

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

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.

lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 using namespace llvm;
 
 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
 /// in a cycle. Because we are analysing 'through' phi nodes we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
 
 // The max limit of the search depth in DecomposeGEPExpression() and
 // GetUnderlyingObject(), both functions need to use the same search
 // depth otherwise the algorithm in aliasGEP will assert.
 static const unsigned MaxLookupSearchDepth = 6;
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);
 }
 
 /// 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,
                              const Value *V2, uint64_t V2Size,
                              const AAMDNodes &V2AAInfo,
                              const Value *UnderlyingV1,
                              const Value *UnderlyingV2) {
   int64_t GEP1BaseOffset;
   bool GEP1MaxLookupReached;
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 both GEPs are based on the same pointer, and said pointer is a
+    // (possibly multidimensional) array of structs, we can try to determine
+    // whether struct field accesses don't alias.
+    // Note that the same pointer the GEPs are based on has to be the same
+    // pointer operand, not just the same underlying object.
+    // We also need at least two indices (the pointer, and the struct field).
+    if (GEP1->getPointerOperand() == GEP2->getPointerOperand() &&
+        GEP1->getNumIndices() == GEP2->getNumIndices() &&
+        GEP1->getNumIndices() >= 2) {
+
+      ConstantInt *C1 =
+          dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
+      ConstantInt *C2 =
+          dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
+
+      // 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.
+      auto LookThroughArrayIndices = [](const GEPOperator *GEP) -> StructType *{
+        SmallVector<Value *, 8> IntermediateIndices;
+        assert(GEP->getNumIndices() > 1 &&
+               "Not enough GEP indices to examine");
+
+        // Insert the first index; we don't need to check the type indexed
+        // through as it only drops the pointer indirection.
+        IntermediateIndices.push_back(GEP->getOperand(1));
+
+        // Insert all the remaining indices but the last one.
+        // Also, check that they all index through arrays.
+        for (unsigned i = 1, e = GEP->getNumIndices() - 1; i != e; ++i) {
+          if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
+                GEP->getPointerOperandType(), IntermediateIndices)))
+            return nullptr;
+          IntermediateIndices.push_back(GEP->getOperand(i + 1));
+        }
+        return dyn_cast<StructType>(GetElementPtrInst::getIndexedType(
+            GEP->getPointerOperandType(), IntermediateIndices));
+      };
+
+      StructType *LastIndexedStruct = nullptr;
+
+      // If the last indices in both GEPs are constant, and they index into
+      // a struct, we can try to figure out if they access different fields.
+      // 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.
+      if (C1 && C2 && C1 != C2 &&
+          (LastIndexedStruct = LookThroughArrayIndices(GEP1))) {
+        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 V2Off,
+                                            uint64_t V1Size, uint64_t V2Size) {
+          return V1Off < V2Off && V1Off + V1Size <= V2Off &&
+                 ((V2Off + V2Size <= StructSize) ||
+                  (V2Off + V2Size - StructSize <= V1Off));
+        };
+
+        if (EltsDontOverlap(V1Off, V2Off, V1Size, V2Size) ||
+            EltsDontOverlap(V2Off, V1Off, V2Size, V1Size))
+          return NoAlias;
+      }
+    }
+
     // 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);

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"
+target triple = "x86_64-apple-darwin"
+
+%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_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
+}