Handle accesses to sturctures with embedded arrays and different offsets better

[• dberlin]

Summary

Fixes the simple testcase:
struct S00 {

char mC_0;
short mS_1;
int mI_2;
int mI_3;

};
struct S03 {

short mS_0;
struct S00 mS00_1[4];
short mS_2;

};
int test_s03c(struct S03* a, struct S03* b)
{

a->mS00_1[0].mI_2=1;
b->mS00_1[1].mI_2=2;
return a->mS00_1[0].mI_2;

}

so that we return 1.

[• dberlin]

• Update borked comment

[• dberlin]

lib/Analysis/BasicAliasAnalysis.cpp

1072

Technically, the check should be "if the variable indices are equal, or we can prove they can't have values that make offset, size overlap when they wouldn't otherwise".

In particular, if we could prove the the variable indices are always 0 or positive, they can't overlap.

Sadly, we don't have range info in BasicAA to use, and this check is already strictly better than what we have now.

[nlewycky]

lib/Analysis/BasicAliasAnalysis.cpp

979

I really don't understand this comment, either from "actual" or "reason about the offsets directly".

Looking at the uses, I don't see any reason not to use llvm::isIdentifiedObject. I think what you need to know is that [V, V+Offset] does not overlap any other object. isIdentifiedObject should be sufficient for that.

983

What about GlobalAlias? GlobalAlias isa GlobalValue.

1063

Full stop after "alias".

1069

Extra space between "both" and "arguments".

1069

Tense agreement between "arguments" and "global variable" and "alloca".

1070

Full stop after "alias".

test/Analysis/BasicAA/gep-alias.ll

235

But they can, I just need to call @test13 with %a = %b + 13 . Did you mean to check whether arguments are noalias?

%6 is %b+17 (aka gep %5, i32 0, i32 1, i32 2)
%10 loads %a+5 (aka gep %a, i32 0, i32 1, i32 0, i32 2)

[I assume one byte of padding in %struct.S00 after the i16.]

236

Full stop after "alias".

lib/Analysis/BasicAliasAnalysis.cpp

aliasSameBasePointerGEPs(const GEPOperator *GEP1, uint64_t V1Size,
 
   if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
       EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
     return AliasAnalysis::NoAlias;
 
   return AliasAnalysis::MayAlias;
 }
 
+/// isActualObject -  Return true if V represents an actual object where we can
+/// reason about the offsets directly, like an argument, alloca, or global
+/// value.
+static bool isActualObject(const Value *V) {
+  if (isa<GlobalValue>(V) || isa<Argument>(V) || isa<AllocaInst>(V))
+    return true;
+
+  return false;
+}
+
 /// 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)) {
     // Do the base pointers alias?
     AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, AAMDNodes(),
                                        UnderlyingV2, UnknownSize, AAMDNodes());
 
     // Check for geps of non-aliasing underlying pointers where the offsets are
     // identical.
     if ((BaseAlias == MayAlias) && V1Size == V2Size) {
       // Do the base pointers alias assuming type and size.
-      AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
-                                                V1AAInfo, UnderlyingV2,
-                                                V2Size, V2AAInfo);
-      if (PreciseBaseAlias == NoAlias) {
-        // See if the computed offset from the common pointer tells us about the
-        // relation of the resulting pointer.
-        int64_t GEP2BaseOffset;
-        bool GEP2MaxLookupReached;
-        SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
-        const Value *GEP2BasePtr =
-            DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
-                                   GEP2MaxLookupReached, *DL, AC2, DT);
-        const Value *GEP1BasePtr =
-            DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
-                                   GEP1MaxLookupReached, *DL, AC1, DT);
-        // 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 the max search depth is reached the result is undefined
-        if (GEP2MaxLookupReached || GEP1MaxLookupReached)
-          return MayAlias;
+      AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo,
+                                                UnderlyingV2, V2Size, V2AAInfo);
 
-        // Same offsets.
+      if (PreciseBaseAlias == NoAlias) {
+        // If they have the same offsets, and the underlying object is noalias,
+        // they must not alias
         if (GEP1BaseOffset == GEP2BaseOffset &&
             GEP1VariableIndices == GEP2VariableIndices)
           return NoAlias;
         GEP1VariableIndices.clear();
+      } else {
+        // If these are both  arguments, global variable, or alloca, and the
+        // [offset, offset+size] ranges don't overlap, they can't alias
+        if (isActualObject(UnderlyingV1) && isActualObject(UnderlyingV2) &&
+            GEP1VariableIndices == GEP2VariableIndices)
+          if ((GEP2BaseOffset - (GEP1BaseOffset + V1Size) > 0) ||
+              (GEP1BaseOffset - (GEP2BaseOffset + V2Size) > 0))
+            return NoAlias;
       }
     }
 
     // If we get a No or May, then return it immediately, no amount of analysis
     // will improve this situation.
     if (BaseAlias != MustAlias) return BaseAlias;
 
     // Otherwise, we have a MustAlias.  Since the base pointers alias each other

test/Analysis/BasicAA/gep-alias.ll

define i32 @test12(i32 %x, i32 %y, i8* %p) nounwind {
   %castp = bitcast i8* %p to i32*
   store i32 1, i32* %castp
   store i32 0, i32* %castd
   %r = load i32, i32* %castp
   ret i32 %r
 ; CHECK-LABEL: @test12(
 ; CHECK: ret i32 %r
 }
+
+%struct.S03 = type { i16, [4 x %struct.S00], i16 }
+%struct.S00 = type { i8, i16, i32, i32 }
+
+; We should be able to determine the second store and the load do not conflict, 
+; but the first store and the load are must alias
+define i32 @test13(%struct.S03* %a, %struct.S03* %b) {
+  %1 = getelementptr inbounds %struct.S03, %struct.S03* %a, i32 0, i32 1
+  %2 = getelementptr inbounds [4 x %struct.S00], [4 x %struct.S00]* %1, i32 0, i64 0
+  %3 = getelementptr inbounds %struct.S00, %struct.S00* %2, i32 0, i32 2
+  store i32 1, i32* %3, align 4
+  %4 = getelementptr inbounds %struct.S03, %struct.S03* %b, i32 0, i32 1
+  %5 = getelementptr inbounds [4 x %struct.S00], [4 x %struct.S00]* %4, i32 0, i64 1
+  %6 = getelementptr inbounds %struct.S00, %struct.S00* %5, i32 0, i32 2
+  store i32 2, i32* %6, align 4
+  %7 = getelementptr inbounds %struct.S03, %struct.S03* %a, i32 0, i32 1
+  %8 = getelementptr inbounds [4 x %struct.S00], [4 x %struct.S00]* %7, i32 0, i64 0
+  %9 = getelementptr inbounds %struct.S00, %struct.S00* %8, i32 0, i32 2
+  %10 = load i32, i32* %9, align 4
+; CHECK-LABEL: @test13
+; CHECK:  ret i32 1
+  ret i32 %10
+}