[BasicAA] Non-equal indices in a GEP of a SequentialType don't overlap

[jmolloy]

Summary

If the final indices of two GEPs can be proven to not be equal, and the GEP is of a SequentialType (not a StructType), then the two GEPs do not alias.

We have to be careful not to return a false negative when dealing with indices into array types that are larger than the number of elements in the array - in this case there can be a partial alias between the GEPs (it breaks our "must" or "no" assumption). With this patch we're quite conservative about this case and only proceed if all intermediate indices are identical between the two GEPs.

[hfinkel]

There are some comment changes, but otherwise, LGTM.

lib/Analysis/BasicAliasAnalysis.cpp

768

We don't seem to know that here, only below, because of how you've modified the C1,C2 check above. Here, we know only that we don't have equal constants.

780

final 'that' -> 'the array/pointer', or similar, to eliminate the 'that that'

lib/Analysis/BasicAliasAnalysis.cpp

if (V1Size == MemoryLocation::UnknownSize ||
       V2Size == MemoryLocation::UnknownSize)
     return 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)
+  // If the last (struct) indices are constants and are equal, the other indices
+  // might be also be dynamically equal, so the GEPs can alias.
+  if (C1 && C2 && C1 == C2)
     return 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->getSourceElementType(), IntermediateIndices)))
       return MayAlias;
     IntermediateIndices.push_back(GEP1->getOperand(i + 1));
   }
 
-  StructType *LastIndexedStruct =
-      dyn_cast<StructType>(GetElementPtrInst::getIndexedType(
-          GEP1->getSourceElementType(), IntermediateIndices));
+  auto *Ty = GetElementPtrInst::getIndexedType(
+    GEP1->getSourceElementType(), IntermediateIndices);
+  StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
 
-  if (!LastIndexedStruct)
+  if (isa<SequentialType>(Ty)) {
+    // We know that:
+    // - both GEPs begin indexing from the exact same pointer;
+    // - the last indices in both GEPs are constants, indexing into a sequential
+    //   type (array or pointer);
+    // - both GEPs only index through arrays prior to that.
+    //
+    // Because array indices greater than the number of elements are valid in
+    // GEPs, unless we know the intermediate indices are identical between
+    // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
+    // partially overlap.
+    for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
+      if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
+        return MayAlias;
+    
+    // Now we know that the array/pointer that GEP1 indexes into and that
+    // that GEP2 indexes into must either precisely overlap or be disjoint.
+    // Because they cannot partially overlap and because fields in an array
+    // cannot overlap, if we can prove the final indices are different between
+    // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
+    
+    // If the last indices are constants, we've already checked they don't
+    // equal each other so we can exit early.
+    if (C1 && C2)
+      return NoAlias;
+    if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1),
+                        GEP2->getOperand(GEP2->getNumOperands() - 1),
+                        DL))
+      return NoAlias;
     return MayAlias;
+  } else if (!LastIndexedStruct || !C1 || !C2) {
+    return 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

test/Analysis/BasicAA/sequential-gep.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: t1
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t1([8 x i32]* %p, i32 %addend, i32* %q) {
+  %knownnonzero = load i32, i32* %q, !range !0
+  %add = add nsw nuw i32 %addend, %knownnonzero
+  %gep1 = getelementptr [8 x i32], [8 x i32]* %p, i32 2, i32 %addend
+  %gep2 = getelementptr [8 x i32], [8 x i32]* %p, i32 2, i32 %add
+  ret void
+}
+
+; CHECK: Function: t2
+; CHECK: PartialAlias: i32* %gep1, i32* %gep2
+define void @t2([8 x i32]* %p, i32 %addend, i32* %q) {
+  %knownnonzero = load i32, i32* %q, !range !0
+  %add = add nsw nuw i32 %addend, %knownnonzero
+  %gep1 = getelementptr [8 x i32], [8 x i32]* %p, i32 1, i32 %addend
+  %gep2 = getelementptr [8 x i32], [8 x i32]* %p, i32 0, i32 %add
+  ret void
+}
+
+; CHECK: Function: t3
+; CHECK: MustAlias: i32* %gep1, i32* %gep2
+define void @t3([8 x i32]* %p, i32 %addend, i32* %q) {
+  %knownnonzero = load i32, i32* %q, !range !0
+  %add = add nsw nuw i32 %addend, %knownnonzero
+  %gep1 = getelementptr [8 x i32], [8 x i32]* %p, i32 0, i32 %add
+  %gep2 = getelementptr [8 x i32], [8 x i32]* %p, i32 0, i32 %add
+  ret void
+}
+
+; CHECK: Function: t4
+; CHECK: PartialAlias: i32* %gep1, i32* %gep2
+define void @t4([8 x i32]* %p, i32 %addend, i32* %q) {
+  %knownnonzero = load i32, i32* %q, !range !0
+  %add = add nsw nuw i32 %addend, %knownnonzero
+  %gep1 = getelementptr [8 x i32], [8 x i32]* %p, i32 1, i32 %addend
+  %gep2 = getelementptr [8 x i32], [8 x i32]* %p, i32 %add, i32 %add
+  ret void
+}
+
+!0 = !{ i32 1, i32 5 }