[BasicAA] An inbounds GEP and an alloca can't alias if the base of the GEP would point "below" the alloca

[mkuper]

Summary

This is another attempt to handle situations similar to http://reviews.llvm.org/D8487 , although it won't work for that particular case (because this doesn't appear to be legal for arguments).

The basic idea is that given this code:

define void @struct() {
  %alloca = alloca %struct
  %alloca.i32 = bitcast %struct* %alloca to i32*
  %random = call i32* @random.i32(i32* %alloca.i32)
  %f0 = getelementptr inbounds %struct, %struct* %alloca, i32 0, i32 0
  %p1 = getelementptr inbounds i32, i32* %random, i32 1
  ret void
}

%f0 and %p1 can not alias.
If they did alias, then the underlying object of %p1 - and thus, of %random - must be %alloca. But that would make %random out of bounds (since it'd have a negative offset) w.r.t %alloca, and since the GEP is inbounds, we can just assume noalias. The same logic probably holds for a GlobalVariable (which isn't a GlobalAlias), but not for other identified objects, like arguments, since a negative offset from a noalias argument may still be inbounds. I'd rather do this for Alloca first, and add GV in a separate commit.

The interface is pretty ugly, perhaps wrapping the results of DecomposeGEPExpression in a class and passing that around would make it better, but I'm not entirely sure. Thoughts?

[davidxl]

lib/Analysis/BasicAliasAnalysis.cpp

345–346

Document parameter BaseStructOffs, and BaseNonStructOffs.

961

Probably add an example in C form to demonstrate it. Also document key parameters of the method.

975

Since this method does not need to update the two limits, it is better to move their checks out of line before the call. i.e.:

if (!GEPMaxLookupReached && !AllocaMaxLookupReached && isGEPBaseAtNegativeOffset(..))
    return NoAlias;

This will help make the interface cleaner.

The limit check can also be combined with the next call:

if (!GEPMaxLookupReached && !AllocaMa... ) {
     if (!isGEP....) 
        return NoAlias;
      if (!isGEP...)
         return NoAlias;
   }

1051

Perhaps passing the GEPVariableIndices directly to the callee.

[mkuper]

Thanks, David!

lib/Analysis/BasicAliasAnalysis.cpp

345–346

Right, thanks.

961

Will do, except that I really think an IR example would be more appropriate here.

975

I actually wrote that with the checks out of line first, didn't seem prettier. :-\

The problem is that the way checkGEP is currently written, there's no clear separation between (1) cases when the second argument is a GEP or not, and (2) cases when the lookup failure should cause it to bail or not. So I have to add extra checks (in the second option you suggest, an extra isGEP check, I can't put the entire isGEP code under a look success check) no matter what,

1051

Ditto - I started out with that, and changed it to passing a bool because that's all the helper cares about. Neither version is pretty.

What do you think about wrapping the entire decomposition result in a struct?

[davidxl]

lib/Analysis/BasicAliasAnalysis.cpp

961

You can treat the example as C like pseudo language to make the description more 'high level' and easier to read.

975

ok

1051

• What do you think about wrapping the entire decomposition result in a struct?

I think that will be cleaner -- enhancing the interface in the future does not require updating all use sites -- perhaps extract that as a NFC refactoring patch.

[mkuper]

Wrapped the decomposition results in a class, hopefully resulting in a cleaner interface.

[davidxl]

test/Analysis/BasicAA/negoffset.ll

47

It is also good add a more complex case where we have nested structs/arrays when constant offsets of the accesses can be collapsed (also severs as tests for the new Decompose method)

something like:
struct Inner {

int inner_f1;
int inner_f2;

};

struct Outer {

int outer_f1;
int outer_f2;
struct inner Inner[10];

} Outer_p;

Outer_p[1].Inner[2].f1 vs some local access at offset 0
Outer_p[i].inner[2].f1 vs some local access at offset 0
Outer_p[i].Inner[j].f2 vs some local access at offst 0

[mkuper]

Added a nested-struct test.
David, is this what you meant?

[mkuper]

And now, with the right CHECK.

[davidxl]

lib/Analysis/BasicAliasAnalysis.cpp

355

Also clear the var indices?

996

Is the VarIndices.empty() check too restrictive?

struct A {

int a[2];
...

};

struct B {

int b1;
int b2;
int b3;

};

struct A a;
B *bp;

bp->b3 vs a.a[i] should produce no aliasing

998

Extract this unrelated cleanup into separate patch.

1035

separate out clean up code into different patch.

1085

Ditto -- cleanup patch.

[mkuper]

lib/Analysis/BasicAliasAnalysis.cpp

355

The original code doesn't do this, but I think you're right, it's an oversight. Will add.

996

I'm not sure this is a good example.

Given:

struct __attribute__((packed)) A {
  int a[2]
  int b;
};

struct B {
  int b1;
  int b2;
  int b3;
};

struct A a;
B *bp = (B*)(&a);

I'm not sure we want, in -fno-strict-aliasing mode, to conclude that bp->b3 doesn't alias a.a[2] (which since the struct is packed, is a.b) - and so it may also alias a.a[i].

So, it seems to me that this could be less restrictive - but not too much. I think the most we can do if the alloca has variable indices, is take the maximum values that will still leave the whole gep inbounds w.r.t the alloca, and use that. If you think we actually run into those cases in practice, I can try to do that as a followup patch.

998

It's not exactly unrelated.

The old code would call DecomposeGEPExpression on-demand only in code paths that were using the decomposition. Which was, I think, the majority - but not 100%. I needed to hoist the calls up - but I don't think that should go in as a stand-alone patch, since if it goes in without the rest of my changes, it incurs compile-time cost without much benefit.

If you think the clean-up is worth that, I can split it into a separate patch, but I'd rather not.

1035

Same as above.

1085

Same as above.

[davidxl]

lib/Analysis/BasicAliasAnalysis.cpp

996

You are right that there is no 'inbound' guarantee for sub/inner array we can leverage here (even though accessing a.a[2] will lead to an error when build with -fsanitiize=undefined). Note GCC handles this with -fstrict-aliasing on.

998

I mean the part that turns return MayAlias into assert -- not the hoisting part of the change. I think you just need to make that change (lgtm to that part which can be committed first) and rebase this patch. Or perhaps just leaves the FIXME in this patch (in the hoisted code and clean it up as a follow up.

[mkuper]

lib/Analysis/BasicAliasAnalysis.cpp

998

Oh, yes, that makes perfect sense, but is slightly more annoying than it looks.

In fact, I already committed that as a separate patch a few days ago (r270268) - but reverted it because of unused variable warnings in non-asserts builds. I thought about recommitting it with dummy accesses to silence the warnings, but that seemed silly. (And I can't put the calls under NDEBUG, because only the result of the call is unused, but the output parameters aren't).

Leaving the FIXME in this patch could potentially change behavior, since it would return MayAlais on different code paths, even those that originally didn't care about the bound at all. On the other hand, it should never actually fire, so that should be fine.

I'm not too excited about either option, but if you prefer one of them to the whole thing going in in one piece, let me know which one.

[• dberlin]

At this point, i think this looks pretty good to me.

[davidxl]

lgtm too.

include/llvm/Analysis/BasicAliasAnalysis.h

bool operator==(const VariableGEPIndex &Other) const {
              SExtBits == Other.SExtBits && Scale == Other.Scale;
     }
 
     bool operator!=(const VariableGEPIndex &Other) const {
       return !operator==(Other);
     }
   };
 
+  // Represents the internal structure of a GEP, decomposed into a base pointer,
+  // constant offsets, and variable scaled indices.
+  struct DecomposedGEP {
+    // Base pointer of the GEP
+    const Value *Base;
+    // Total constant offset w.r.t the base from indexing into structs
+    int64_t StructOffset;
+    // Total constant offset w.r.t the base from indexing through
+    // pointers/arrays/vectors
+    int64_t OtherOffset;
+    // Scaled variable (non-constant) indices.
+    SmallVector<VariableGEPIndex, 4> VarIndices;
+  };
+
   /// Track alias queries to guard against recursion.
   typedef std::pair<MemoryLocation, MemoryLocation> LocPair;
   typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
   AliasCacheTy AliasCache;
 
   /// Tracks phi nodes we have visited.
   ///
   /// When interpret "Value" pointer equality as value equality we need to make
private:
   SmallPtrSet<const Value *, 16> Visited;
 
   static const Value *
   GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
                       unsigned &ZExtBits, unsigned &SExtBits,
                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
                       DominatorTree *DT, bool &NSW, bool &NUW);
 
-  static const Value *
-  DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
-                         SmallVectorImpl<VariableGEPIndex> &VarIndices,
-                         bool &MaxLookupReached, const DataLayout &DL,
-                         AssumptionCache *AC, DominatorTree *DT);
+  static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
+      const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
+
+  static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
+      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompAlloca,
+      uint64_t AllocaAccessSize);
+
   /// \brief A Heuristic for aliasGEP that searches for a constant offset
   /// between the variables.
   ///
   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
   /// will therefore conservatively refuse to decompose these expressions.
   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
   /// the addition overflows.

lib/Analysis/BasicAliasAnalysis.cpp

 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
 /// specified amount, but which may have other unrepresented high bits. As
 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
 ///
 /// When DataLayout is around, this function is capable of analyzing everything
 /// that GetUnderlyingObject can look through. To be able to do that
 /// GetUnderlyingObject and DecomposeGEPExpression must use the same search
 /// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
 /// through pointer casts.
-/*static*/ const Value *BasicAAResult::DecomposeGEPExpression(
-    const Value *V, int64_t &BaseOffs,
-    SmallVectorImpl<VariableGEPIndex> &VarIndices, bool &MaxLookupReached,
-    const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) {
+bool BasicAAResult::DecomposeGEPExpression(const Value *V,
+       DecomposedGEP &Decomposed, const DataLayout &DL, AssumptionCache *AC,
+       DominatorTree *DT) {
   // Limit recursion depth to limit compile time in crazy cases.
   unsigned MaxLookup = MaxLookupSearchDepth;
-  MaxLookupReached = false;
   SearchTimes++;
 
-  BaseOffs = 0;
+  Decomposed.StructOffset = 0;
+  Decomposed.OtherOffset = 0;
   do {
     // See if this is a bitcast or GEP.
     const Operator *Op = dyn_cast<Operator>(V);
     if (!Op) {
       // The only non-operator case we can handle are GlobalAliases.
       if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
         if (!GA->isInterposable()) {
           V = GA->getAliasee();
           continue;
         }
       }
-      return V;
+      Decomposed.Base = V;
+      return false;
     }
 
     if (Op->getOpcode() == Instruction::BitCast ||
         Op->getOpcode() == Instruction::AddrSpaceCast) {
       V = Op->getOperand(0);
       continue;
     }
 
     const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
     if (!GEPOp) {
       // If it's not a GEP, hand it off to SimplifyInstruction to see if it
       // can come up with something. This matches what GetUnderlyingObject does.
       if (const Instruction *I = dyn_cast<Instruction>(V))
         // TODO: Get a DominatorTree and AssumptionCache and use them here
         // (these are both now available in this function, but this should be
         // updated when GetUnderlyingObject is updated). TLI should be
         // provided also.
         if (const Value *Simplified =
                 SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
           V = Simplified;
           continue;
         }
 
-      return V;
+      Decomposed.Base = V;
+      return false;
     }
 
     // Don't attempt to analyze GEPs over unsized objects.
-    if (!GEPOp->getSourceElementType()->isSized())
-      return V;
+    if (!GEPOp->getSourceElementType()->isSized()) {
+      Decomposed.Base = V;
+      return false;
+    }
 
     unsigned AS = GEPOp->getPointerAddressSpace();
     // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
     gep_type_iterator GTI = gep_type_begin(GEPOp);
     unsigned PointerSize = DL.getPointerSizeInBits(AS);
     for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
          I != E; ++I) {
       const Value *Index = *I;
       // Compute the (potentially symbolic) offset in bytes for this index.
       if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
         // For a struct, add the member offset.
         unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
         if (FieldNo == 0)
           continue;
 
-        BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo);
+        Decomposed.StructOffset +=
+          DL.getStructLayout(STy)->getElementOffset(FieldNo);
         continue;
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
       if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
         if (CIdx->isZero())
           continue;
-        BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();
+        Decomposed.OtherOffset +=
+          DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();
         continue;
       }
 
       uint64_t Scale = DL.getTypeAllocSize(*GTI);
       unsigned ZExtBits = 0, SExtBits = 0;
 
       // If the integer type is smaller than the pointer size, it is implicitly
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
       if (PointerSize > Width)
         SExtBits += PointerSize - Width;
 
       // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
       APInt IndexScale(Width, 0), IndexOffset(Width, 0);
       bool NSW = true, NUW = true;
       Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
                                   SExtBits, DL, 0, AC, DT, NSW, NUW);
 
       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
-      BaseOffs += IndexOffset.getSExtValue() * Scale;
+      Decomposed.OtherOffset += IndexOffset.getSExtValue() * Scale;
       Scale *= IndexScale.getSExtValue();
 
       // If we already had an occurrence of this index variable, merge this
       // scale into it.  For example, we want to handle:
       //   A[x][x] -> x*16 + x*4 -> x*20
       // This also ensures that 'x' only appears in the index list once.
-      for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
-        if (VarIndices[i].V == Index && VarIndices[i].ZExtBits == ZExtBits &&
-            VarIndices[i].SExtBits == SExtBits) {
-          Scale += VarIndices[i].Scale;
-          VarIndices.erase(VarIndices.begin() + i);
+      for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
+        if (Decomposed.VarIndices[i].V == Index && 
+            Decomposed.VarIndices[i].ZExtBits == ZExtBits &&
+            Decomposed.VarIndices[i].SExtBits == SExtBits) {
+          Scale += Decomposed.VarIndices[i].Scale;
+          Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
           break;
         }
       }
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
       Scale = adjustToPointerSize(Scale, PointerSize);
 
       if (Scale) {
         VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
                                   static_cast<int64_t>(Scale)};
-        VarIndices.push_back(Entry);
+        Decomposed.VarIndices.push_back(Entry);
       }
     }
 
     // Take care of wrap-arounds
-    BaseOffs = adjustToPointerSize(BaseOffs, PointerSize);
+    Decomposed.StructOffset =
+      adjustToPointerSize(Decomposed.StructOffset, PointerSize);
+    Decomposed.OtherOffset =
+      adjustToPointerSize(Decomposed.OtherOffset, PointerSize);
 
     // Analyze the base pointer next.
     V = GEPOp->getOperand(0);
   } while (--MaxLookup);
 
   // If the chain of expressions is too deep, just return early.
-  MaxLookupReached = true;
+  Decomposed.Base = V;
   SearchLimitReached++;
-  return V;
+  return true;
 }
 
 /// Returns whether the given pointer value points to memory that is local to
 /// the function, with global constants being considered local to all
 /// functions.
 bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
                                            bool OrLocal) {
   assert(Visited.empty() && "Visited must be cleared after use!");
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
 
   if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
       EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
     return NoAlias;
 
   return MayAlias;
 }
 
+// If a we have (a) a GEP and (b) a pointer based on an alloca, and the
+// beginning of the object the GEP points would have a negative offset with
+// repsect to the alloca, that means the GEP can not alias pointer (b).
+// Note that the pointer based on the alloca may not be a GEP. For
+// example, it may be the alloca itself.
+//
+// For example, consider:
+//
+//   struct { int f0, int f1, ...} foo;
+//   foo alloca;
+//   foo* random = bar(alloca);
+//   int *f0 = &alloca.f0
+//   int *f1 = &random->f1;
+//
+// Which is lowered, approximately, to:
+//
+//  %alloca = alloca %struct.foo
+//  %random = call %struct.foo* @random(%struct.foo* %alloca)
+//  %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0
+//  %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1
+//
+// Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
+// by %alloca. Since the %f1 GEP is inbounds, that means %random must also
+// point into the same object. But since %f0 points to the beginning of %alloca,
+// the highest %f1 can be is (%alloca + 3). This means %random can not be higher
+// than (%alloca - 1), and so is not inbounds, a contradiction.
+bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
+      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompAlloca, 
+      uint64_t AllocaAccessSize) {
+  // If the alloca access size is unknown, or the GEP isn't inbounds, bail.
+  if (AllocaAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
+    return false;
+
+  // We need an alloca, and want to know the offset of the pointer
+  // from the alloca precisely, so no variable indices are allowed.
+  if (!isa<AllocaInst>(DecompAlloca.Base) || !DecompAlloca.VarIndices.empty())
+    return false;
+
+  int64_t AllocaBaseOffset = DecompAlloca.StructOffset +
+                             DecompAlloca.OtherOffset;
+
+  // If the GEP has no variable indices, we know the precise offset
+  // from the base, then use it. If the GEP has variable indices, we're in
+  // a bit more trouble: we can't count on the constant offsets that come
+  // from non-struct sources, since these can be "rewound" by a negative
+  // variable offset. So use only offsets that came from structs.
+  int64_t GEPBaseOffset = DecompGEP.StructOffset;
+  if (DecompGEP.VarIndices.empty())
+    GEPBaseOffset += DecompGEP.OtherOffset;
+
+  return (GEPBaseOffset >= AllocaBaseOffset + (int64_t)AllocaAccessSize);
+}
+
 /// Provides 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.
 AliasResult BasicAAResult::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;
-  SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
-
+  DecomposedGEP DecompGEP1, DecompGEP2;
+  bool GEP1MaxLookupReached =
+    DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
+  bool GEP2MaxLookupReached =
+    DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
+
+  int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
+  int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
+
+  assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
+         "DecomposeGEPExpression returned a result different from "
+         "GetUnderlyingObject");
+
+  // If the GEP's offset relative to its base is such that the base would
+  // fall below the start of the object underlying V2, then the GEP and V2
+  // cannot alias.
+  if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
+      isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size))
+    return NoAlias;
   // If we have two gep instructions with must-alias or not-alias'ing base
   // pointers, figure out if the indexes to the GEP tell us anything about the
   // derived pointer.
   if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
+    // Check for the GEP base being at a negative offset, this time in the other
+    // direction.
+    if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
+        isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
+      return NoAlias;
     // Do the base pointers alias?
     AliasResult BaseAlias =
         aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(),
                    UnderlyingV2, MemoryLocation::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, &AC, DT);
-        const Value *GEP1BasePtr =
-            DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
-                                   GEP1MaxLookupReached, DL, &AC, DT);
-        // DecomposeGEPExpression and GetUnderlyingObject should return the
-        // same result except when DecomposeGEPExpression has no DataLayout.
-        // FIXME: They always have a DataLayout, so this should become an
-        // assert.
-        if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
-          return MayAlias;
-        }
         // If the max search depth is reached the result is undefined
         if (GEP2MaxLookupReached || GEP1MaxLookupReached)
           return MayAlias;
 
         // Same offsets.
         if (GEP1BaseOffset == GEP2BaseOffset &&
-            GEP1VariableIndices == GEP2VariableIndices)
+            DecompGEP1.VarIndices == DecompGEP2.VarIndices)
           return NoAlias;
-        GEP1VariableIndices.clear();
       }
     }
 
     // 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
     // exactly, see if the computed offset from the common pointer tells us
     // about the relation of the resulting pointer.
-    const Value *GEP1BasePtr =
-        DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
-                               GEP1MaxLookupReached, DL, &AC, DT);
-
-    int64_t GEP2BaseOffset;
-    bool GEP2MaxLookupReached;
-    SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
-    const Value *GEP2BasePtr =
-        DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
-                               GEP2MaxLookupReached, DL, &AC, DT);
-
-    // DecomposeGEPExpression and GetUnderlyingObject should return the
-    // same result except when DecomposeGEPExpression has no DataLayout.
-    // FIXME: They always have a DataLayout, so this should become an assert.
-    if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
-      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 (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);
+    GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
 
   } else {
     // Check to see if these two pointers are related by the getelementptr
     // instruction.  If one pointer is a GEP with a non-zero index of the other
     // pointer, we know they cannot alias.
 
     // If both accesses are unknown size, we can't do anything useful here.
     if (V1Size == MemoryLocation::UnknownSize &&
         V2Size == MemoryLocation::UnknownSize)
       return MayAlias;
 
     AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize,
                                AAMDNodes(), V2, V2Size, V2AAInfo);
     if (R != MustAlias)
       // If V2 may alias GEP base pointer, conservatively returns MayAlias.
       // If V2 is known not to alias GEP base pointer, then the two values
       // cannot alias per GEP semantics: "A pointer value formed from a
       // getelementptr instruction is associated with the addresses associated
       // with the first operand of the getelementptr".
       return R;
 
-    const Value *GEP1BasePtr =
-        DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
-                               GEP1MaxLookupReached, DL, &AC, DT);
-
-    // DecomposeGEPExpression and GetUnderlyingObject should return the
-    // same result except when DecomposeGEPExpression has no DataLayout.
-    // FIXME: They always have a DataLayout, so this should become an assert.
-    if (GEP1BasePtr != UnderlyingV1) {
-      return MayAlias;
-    }
     // If the max search depth is reached the result is undefined
     if (GEP1MaxLookupReached)
       return MayAlias;
   }
 
   // In the two GEP Case, if there is no difference in the offsets of the
   // computed pointers, the resultant pointers are a must alias.  This
   // happens when we have two lexically identical GEP's (for example).
   //
   // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
   // must aliases the GEP, the end result is a must alias also.
-  if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty())
+  if (GEP1BaseOffset == 0 && DecompGEP1.VarIndices.empty())
     return MustAlias;
 
   // If there is a constant difference between the pointers, but the difference
   // is less than the size of the associated memory object, then we know
   // that the objects are partially overlapping.  If the difference is
   // greater, we know they do not overlap.
-  if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) {
+  if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
     if (GEP1BaseOffset >= 0) {
       if (V2Size != MemoryLocation::UnknownSize) {
         if ((uint64_t)GEP1BaseOffset < V2Size)
           return PartialAlias;
         return NoAlias;
       }
     } else {
       // We have the situation where:
       // +                +
       // | BaseOffset     |
       // ---------------->|
       // |-->V1Size       |-------> V2Size
       // GEP1             V2
       // We need to know that V2Size is not unknown, otherwise we might have
       // stripped a gep with negative index ('gep <ptr>, -1, ...).
       if (V1Size != MemoryLocation::UnknownSize &&
           V2Size != MemoryLocation::UnknownSize) {
         if (-(uint64_t)GEP1BaseOffset < V1Size)
           return PartialAlias;
         return NoAlias;
       }
     }
   }
 
-  if (!GEP1VariableIndices.empty()) {
+  if (!DecompGEP1.VarIndices.empty()) {
     uint64_t Modulo = 0;
     bool AllPositive = true;
-    for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
+    for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
 
       // Try to distinguish something like &A[i][1] against &A[42][0].
       // Grab the least significant bit set in any of the scales. We
       // don't need std::abs here (even if the scale's negative) as we'll
       // be ^'ing Modulo with itself later.
-      Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
+      Modulo |= (uint64_t)DecompGEP1.VarIndices[i].Scale;
 
       if (AllPositive) {
         // If the Value could change between cycles, then any reasoning about
         // the Value this cycle may not hold in the next cycle. We'll just
         // give up if we can't determine conditions that hold for every cycle:
-        const Value *V = GEP1VariableIndices[i].V;
+        const Value *V = DecompGEP1.VarIndices[i].V;
 
         bool SignKnownZero, SignKnownOne;
         ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL,
                        0, &AC, nullptr, DT);
 
         // Zero-extension widens the variable, and so forces the sign
         // bit to zero.
-        bool IsZExt = GEP1VariableIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
+        bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
         SignKnownZero |= IsZExt;
         SignKnownOne &= !IsZExt;
 
         // If the variable begins with a zero then we know it's
         // positive, regardless of whether the value is signed or
         // unsigned.
-        int64_t Scale = GEP1VariableIndices[i].Scale;
+        int64_t Scale = DecompGEP1.VarIndices[i].Scale;
         AllPositive =
             (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
       }
     }
 
     Modulo = Modulo ^ (Modulo & (Modulo - 1));
 
     // We can compute the difference between the two addresses
     // mod Modulo. Check whether that difference guarantees that the
     // two locations do not alias.
     uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
     if (V1Size != MemoryLocation::UnknownSize &&
         V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
         V1Size <= Modulo - ModOffset)
       return NoAlias;
 
     // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
     // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
     // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
     if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
       return NoAlias;
 
-    if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size,
+    if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
                                 GEP1BaseOffset, &AC, DT))
       return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
   // pointers have dynamic offsets which we can't resolve. And none of our
   // little tricks above worked.
   //

test/Analysis/BasicAA/negoffset.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
+target triple = "i386-unknown-linux-gnu"
+
+declare i32* @random.i32(i32* %ptr)
+
+; CHECK-LABEL: Function: arr:
+; CHECK-DAG: MayAlias: i32* %alloca, i32* %p0
+; CHECK-DAG: NoAlias:  i32* %alloca, i32* %p1
+define void @arr() {
+  %alloca = alloca i32, i32 4
+  %random = call i32* @random.i32(i32* %alloca)
+  %p0 = getelementptr inbounds i32, i32* %random, i32 0
+  %p1 = getelementptr inbounds i32, i32* %random, i32 1
+  ret void
+}
+
+; CHECK-LABEL: Function: arg:
+; CHECK-DAG: MayAlias: i32* %arg, i32* %p0
+; CHECK-DAG: MayAlias: i32* %arg, i32* %p1
+define void @arg(i32* %arg) {
+  %random = call i32* @random.i32(i32* %arg)
+  %p0 = getelementptr inbounds i32, i32* %random, i32 0
+  %p1 = getelementptr inbounds i32, i32* %random, i32 1
+  ret void
+}
+
+; CHECK-LABEL: Function: struct:
+; CHECK-DAG:  MayAlias: i32* %f0, i32* %p0
+; CHECK-DAG:  MayAlias: i32* %f1, i32* %p0
+; CHECK-DAG:  NoAlias:  i32* %f0, i32* %p1
+; CHECK-DAG:  MayAlias: i32* %f1, i32* %p1
+%struct = type { i32, i32, i32 }
+define void @struct() {
+  %alloca = alloca %struct
+  %alloca.i32 = bitcast %struct* %alloca to i32*
+  %random = call i32* @random.i32(i32* %alloca.i32)
+  %f0 = getelementptr inbounds %struct, %struct* %alloca, i32 0, i32 0
+  %f1 = getelementptr inbounds %struct, %struct* %alloca, i32 0, i32 1
+  %p0 = getelementptr inbounds i32, i32* %random, i32 0
+  %p1 = getelementptr inbounds i32, i32* %random, i32 1
+  ret void
+}
+
+; CHECK-LABEL: Function: complex1:
+; CHECK-DAG:  MayAlias:     i32* %a2.0, i32* %r2.0
+; CHECK-DAG:  NoAlias:      i32* %a2.0, i32* %r2.1
+; CHECK-DAG:  MayAlias:     i32* %a2.0, i32* %r2.i
+; CHECK-DAG:  MayAlias:     i32* %a2.0, i32* %r2.1i
+; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.0
+; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.1
+; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.i
+; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.1i
+%complex = type { i32, i32, [4 x i32] }
+define void @complex1(i32 %i) {
+  %alloca = alloca %complex
+  %alloca.i32 = bitcast %complex* %alloca to i32*
+  %r.i32 = call i32* @random.i32(i32* %alloca.i32)
+  %random = bitcast i32* %r.i32 to %complex*
+  %a1 = getelementptr inbounds %complex, %complex* %alloca, i32 0, i32 1
+  %a2.0 = getelementptr inbounds %complex, %complex* %alloca, i32 0, i32 2, i32 0
+  %r2.0 = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 0
+  %r2.1 = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 1
+  %r2.i = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 %i
+  %r2.1i = getelementptr inbounds i32, i32* %r2.1, i32 %i
+  ret void
+}
+
+; CHECK-LABEL: Function: complex2:
+; CHECK-DAG: NoAlias: i32* %alloca, i32* %p120
+; CHECK-DAG: NoAlias: i32* %alloca, i32* %pi20
+; CHECK-DAG: NoAlias: i32* %alloca, i32* %pij1
+%inner = type { i32, i32 }
+%outer = type { i32, i32, [10 x %inner] }
+declare %outer* @rand_outer(i32* %p)
+define void @complex2(i32 %i, i32 %j) {
+  %alloca = alloca i32
+  %random = call %outer* @rand_outer(i32* %alloca)
+  %p120 = getelementptr inbounds %outer, %outer* %random, i32 1, i32 2, i32 2, i32 0
+  %pi20 = getelementptr inbounds %outer, %outer* %random, i32 %i, i32 2, i32 2, i32 0
+  %pij1 = getelementptr inbounds %outer, %outer* %random, i32 %i, i32 2, i32 %j, i32 1
+  ret void
+}
+