[BasicAA] Extend negative offset logic from Allocas to GlobalVariables

[mkuper]

Summary

This extends the logic of http://reviews.llvm.org/rL270777 to also apply to GlobalVariables in addition to Allocas.
I don't think there's any other kind of base object this can cover - it doesn't seem safe for arguments, noalias calls, or global aliases.

[davidxl]

lgtm

llvm/trunk/include/llvm/Analysis/BasicAliasAnalysis.h

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 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);
+      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
+      uint64_t ObjectAccessSize);
 
   /// \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

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
   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.
+// The same applies if (b) is based on a GlobalVariable. Note that just being
+// based on isIdentifiedObject() is not enough - we need an identified object
+// that does not permit access to negative offsets. For example, a negative
+// offset from a noalias argument or call can be inbounds w.r.t the actual
+// underlying object.
 //
 // 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())
+      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, 
+      uint64_t ObjectAccessSize) {
+  // If the object access size is unknown, or the GEP isn't inbounds, bail.
+  if (ObjectAccessSize == 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())
+  // We need the object to be an alloca or a globalvariable, and want to know
+  // the offset of the pointer from the object precisely, so no variable
+  // indices are allowed.
+  if (!(isa<AllocaInst>(DecompObject.Base) ||
+        isa<GlobalVariable>(DecompObject.Base)) ||
+      !DecompObject.VarIndices.empty())
     return false;
 
-  int64_t AllocaBaseOffset = DecompAlloca.StructOffset +
-                             DecompAlloca.OtherOffset;
+  int64_t ObjectBaseOffset = DecompObject.StructOffset +
+                             DecompObject.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);
+  return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
 }
 
 /// 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.

llvm/trunk/test/Analysis/BasicAA/negoffset.ll

 ; 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
 }
 
+@gv = global i32 1
+; CHECK-LABEL: Function: global:
+; CHECK-DAG: MayAlias: i32* %p0, i32* @gv
+; CHECK-DAG: NoAlias:  i32* %p1, i32* @gv
+define void @global() {
+  %random = call i32* @random.i32(i32* @gv)
+  %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