Refactor basicaa's main alias function somethin' fierce.

This fixes several minor bugs (such as returning noalias
for comparisons between external weak functions an null) but
is mostly a cleanup.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52299 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 94 insertions, 104 deletions

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 599a6f650f..7e096cd0bc 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -143,7 +143,7 @@ ImmutablePass *llvm::createBasicAliasAnalysisPass() {
 /// a unique object or an argument, return it.  This returns:
 ///    Arguments, GlobalVariables, Functions, Allocas, Mallocs.
 static const Value *getUnderlyingObject(const Value *V) {
-  if (!isa<PointerType>(V->getType())) return 0;
+  if (!isa<PointerType>(V->getType())) return V;
 
   // If we are at some type of object, return it. GlobalValues and Allocations
   // have unique addresses. 
@@ -159,7 +159,7 @@ static const Value *getUnderlyingObject(const Value *V) {
         CE->getOpcode() == Instruction::GetElementPtr)
       return getUnderlyingObject(CE->getOperand(0));
   }
-  return 0;
+  return V;
 }
 
 static const User *isGEP(const Value *V) {
@@ -193,9 +193,9 @@ static const Value *GetGEPOperands(const Value *V,
 /// pointsToConstantMemory - Chase pointers until we find a (constant
 /// global) or not.
 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
-  if (const Value *V = getUnderlyingObject(P))
-    if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
-      return GV->isConstant();
+  if (const GlobalVariable *GV = 
+        dyn_cast<GlobalVariable>(getUnderlyingObject(P)))
+    return GV->isConstant();
   return false;
 }
 
@@ -248,9 +248,19 @@ AliasAnalysis::ModRefResult
 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
   if (!isa<Constant>(P)) {
     const Value *Object = getUnderlyingObject(P);
+    
+    // If this is a tail call and P points to a stack location, we know that
+    // the tail call cannot access or modify the local stack.
+    // We cannot exclude byval arguments here; these belong to the caller of
+    // the current function not to the current function, and a tail callee
+    // may reference them.
+    if (isa<AllocaInst>(Object))
+      if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
+        if (CI->isTailCall())
+          return NoModRef;
+    
     // Allocations and byval arguments are "new" objects.
-    if (Object &&
-        (isa<AllocationInst>(Object) || isa<Argument>(Object))) {
+    if (isa<AllocationInst>(Object) || isa<Argument>(Object)) {
       // Okay, the pointer is to a stack allocated (or effectively so, for 
       // for noalias parameters) object.  If the address of this object doesn't
       // escape from this function body to a callee, then we know that no
@@ -263,23 +273,13 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
           for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
               CI != CE; ++CI)
             if (isa<PointerType>((*CI)->getType()) &&
-                ( getUnderlyingObject(*CI) == P ||
-                  alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias) )
+                (getUnderlyingObject(*CI) == P ||
+                 alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias))
               passedAsArg = true;
           
           if (!passedAsArg)
             return NoModRef;
         }
-
-      // If this is a tail call and P points to a stack location, we know that
-      // the tail call cannot access or modify the local stack.
-      // We cannot exclude byval arguments here; these belong to the caller of
-      // the current function not to the current function, and a tail callee
-      // may reference them.
-      if (isa<AllocaInst>(Object))
-        if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
-          if (CI->isTailCall())
-            return NoModRef;
     }
   }
 
@@ -287,6 +287,57 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
   return AliasAnalysis::getModRefInfo(CS, P, Size);
 }
 
+/// isIdentifiedObject - Return true if this pointer refers to a distinct and
+/// identifiable object.  This returns true for:
+///    Global Variables and Functions
+///    Allocas and Mallocs
+///    ByVal and NoAlias Arguments
+///
+static bool isIdentifiedObject(const Value *V) {
+  if (isa<GlobalValue>(V) || isa<AllocationInst>(V))
+    return true;
+  if (const Argument *A = dyn_cast<Argument>(V))
+    return A->hasNoAliasAttr() || A->hasByValAttr();
+  return false;
+}
+
+/// isKnownNonNull - Return true if we know that the specified value is never
+/// null.
+static bool isKnownNonNull(const Value *V) {
+  // Alloca never returns null, malloc might.
+  if (isa<AllocaInst>(V)) return true;
+  
+  // A byval argument is never null.
+  if (const Argument *A = dyn_cast<Argument>(V))
+    return A->hasByValAttr();
+
+  // Global values are not null unless extern weak.
+  if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
+    return !GV->hasExternalWeakLinkage();
+  return false;
+}
+
+/// isObjectSmallerThan - Return true if we can prove that the object specified
+/// by V is smaller than Size.
+static bool isObjectSmallerThan(const Value *V, unsigned Size,
+                                const TargetData &TD) {
+  const Type *AccessTy = 0;
+  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
+    AccessTy = GV->getType()->getElementType();
+  
+  if (const AllocationInst *AI = dyn_cast<AllocationInst>(V))
+    if (!AI->isArrayAllocation())
+      AccessTy = AI->getType()->getElementType();
+
+  if (const Argument *A = dyn_cast<Argument>(V))
+    if (A->hasByValAttr())
+      AccessTy = cast<PointerType>(A->getType())->getElementType();
+  
+  if (AccessTy && AccessTy->isSized())
+    return TD.getABITypeSize(AccessTy) < Size;
+  return false;
+}
+
 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
 // as array references.  Note that this function is heavily tail recursive.
 // Hopefully we have a smart C++ compiler.  :)
@@ -319,92 +370,31 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
   const Value *O1 = getUnderlyingObject(V1);
   const Value *O2 = getUnderlyingObject(V2);
 
-  // Pointing at a discernible object?
-  if (O1) {
-    if (O2) {
-      if (const Argument *O1Arg = dyn_cast<Argument>(O1)) {
-        // Incoming argument cannot alias locally allocated object!
-        if (isa<AllocationInst>(O2)) return NoAlias;
-        
-        // If they are two different objects, and one is a noalias argument
-        // then they do not alias.
-        if (O1 != O2 && O1Arg->hasNoAliasAttr())
-          return NoAlias;
-
-        // Byval arguments can't alias globals or other arguments.
-        if (O1 != O2 && O1Arg->hasByValAttr()) return NoAlias;
-        
-        // Otherwise, nothing is known...
-      } 
-      
-      if (const Argument *O2Arg = dyn_cast<Argument>(O2)) {
-        // Incoming argument cannot alias locally allocated object!
-        if (isa<AllocationInst>(O1)) return NoAlias;
-        
-        // If they are two different objects, and one is a noalias argument
-        // then they do not alias.
-        if (O1 != O2 && O2Arg->hasNoAliasAttr())
-          return NoAlias;
-          
-        // Byval arguments can't alias globals or other arguments.
-        if (O1 != O2 && O2Arg->hasByValAttr()) return NoAlias;
-        
-        // Otherwise, nothing is known...
-      
-      } else if (O1 != O2 && !isa<Argument>(O1)) {
-        // If they are two different objects, and neither is an argument,
-        // we know that we have no alias.
-        return NoAlias;
-      }
-
-      // If they are the same object, they we can look at the indexes.  If they
-      // index off of the object is the same for both pointers, they must alias.
-      // If they are provably different, they must not alias.  Otherwise, we
-      // can't tell anything.
-    }
-
-    // Unique values don't alias null, except non-byval arguments.
-    if (isa<ConstantPointerNull>(V2)) {
-      if (const Argument *O1Arg = dyn_cast<Argument>(O1)) {
-        if (O1Arg->hasByValAttr()) 
-          return NoAlias;
-      } else {
-        return NoAlias;                    
-      }
-    }
-
-    if (isa<GlobalVariable>(O1) ||
-        (isa<AllocationInst>(O1) &&
-         !cast<AllocationInst>(O1)->isArrayAllocation()))
-      if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
-        // If the size of the other access is larger than the total size of the
-        // global/alloca/malloc, it cannot be accessing the global (it's
-        // undefined to load or store bytes before or after an object).
-        const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
-        unsigned GlobalSize = getTargetData().getABITypeSize(ElTy);
-        if (GlobalSize < V2Size && V2Size != ~0U)
-          return NoAlias;
-      }
-  }
-
-  if (O2) {
-    if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
-      return NoAlias;                    // Unique values don't alias null
-
-    if (isa<GlobalVariable>(O2) ||
-        (isa<AllocationInst>(O2) &&
-         !cast<AllocationInst>(O2)->isArrayAllocation()))
-      if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
-        // If the size of the other access is larger than the total size of the
-        // global/alloca/malloc, it cannot be accessing the object (it's
-        // undefined to load or store bytes before or after an object).
-        const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
-        unsigned GlobalSize = getTargetData().getABITypeSize(ElTy);
-        if (GlobalSize < V1Size && V1Size != ~0U)
-          return NoAlias;
-      }
+  if (O1 != O2) {
+    // If V1/V2 point to two different objects we know that we have no alias.
+    if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
+      return NoAlias;
+  
+    // Incoming argument cannot alias locally allocated object!
+    if ((isa<Argument>(O1) && isa<AllocationInst>(O2)) ||
+        (isa<Argument>(O2) && isa<AllocationInst>(O1)))
+      return NoAlias;
+    
+    // Most objects can't alias null.
+    if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) ||
+        (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2)))
+      return NoAlias;
   }
-
+  
+  // If the size of one access is larger than the entire object on the other
+  // side, then we know such behavior is undefined and can assume no alias.
+  const TargetData &TD = getTargetData();
+  if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, TD)) ||
+      (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, TD)))
+    return NoAlias;
+  
+  
+  
   // If we have two gep instructions with must-alias'ing base pointers, figure
   // out if the indexes to the GEP tell us anything about the derived pointer.
   // Note that we also handle chains of getelementptr instructions as well as