Extend the AliasAnalysis::pointsToConstantMemory interface to allow it

to optionally look for constant or local (alloca) memory.

Teach BasicAliasAnalysis::pointsToConstantMemory to look through Select
and Phi nodes, and to support looking for local memory.

Remove FunctionAttrs' PointsToLocalOrConstantMemory function, now that
AliasAnalysis knows all the tricks that it knew.


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

9 files changed, 85 insertions, 83 deletions

diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index 6a22ad36a5..48a9396262 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -154,15 +154,16 @@ public:
     return isNoAlias(Location(V1, V1Size), Location(V2, V2Size));
   }
 
-  /// pointsToConstantMemory - If the specified memory location is known to be
-  /// constant, return true.  This allows disambiguation of store
-  /// instructions from constant pointers.
-  ///
-  virtual bool pointsToConstantMemory(const Location &Loc);
+  /// pointsToConstantMemory - If the specified memory location is
+  /// known to be constant, return true. If OrLocal is true and the
+  /// specified memory location is known to be "local" (derived from
+  /// an alloca), return true. Otherwise return false.
+  virtual bool pointsToConstantMemory(const Location &Loc,
+                                      bool OrLocal = false);
 
   /// pointsToConstantMemory - A convenient wrapper.
-  bool pointsToConstantMemory(const Value *P) {
-    return pointsToConstantMemory(Location(P));
+  bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
+    return pointsToConstantMemory(Location(P), OrLocal);
   }
 
   //===--------------------------------------------------------------------===//
diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp
index 472d57ab40..d513ebbc2a 100644
--- a/lib/Analysis/AliasAnalysis.cpp
+++ b/lib/Analysis/AliasAnalysis.cpp
@@ -49,9 +49,10 @@ AliasAnalysis::alias(const Location &LocA, const Location &LocB) {
   return AA->alias(LocA, LocB);
 }
 
-bool AliasAnalysis::pointsToConstantMemory(const Location &Loc) {
+bool AliasAnalysis::pointsToConstantMemory(const Location &Loc,
+                                           bool OrLocal) {
   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
-  return AA->pointsToConstantMemory(Loc);
+  return AA->pointsToConstantMemory(Loc, OrLocal);
 }
 
 void AliasAnalysis::deleteValue(Value *V) {
diff --git a/lib/Analysis/AliasAnalysisCounter.cpp b/lib/Analysis/AliasAnalysisCounter.cpp
index a82d959829..23be94ffb0 100644
--- a/lib/Analysis/AliasAnalysisCounter.cpp
+++ b/lib/Analysis/AliasAnalysisCounter.cpp
@@ -95,8 +95,8 @@ namespace {
     }
     
     // FIXME: We could count these too...
-    bool pointsToConstantMemory(const Location &Loc) {
-      return getAnalysis<AliasAnalysis>().pointsToConstantMemory(Loc);
+    bool pointsToConstantMemory(const Location &Loc, bool OrLocal) {
+      return getAnalysis<AliasAnalysis>().pointsToConstantMemory(Loc, OrLocal);
     }
 
     // Forwarding functions: just delegate to a real AA implementation, counting
diff --git a/lib/Analysis/AliasDebugger.cpp b/lib/Analysis/AliasDebugger.cpp
index 4b9aefcb11..f15c05153e 100644
--- a/lib/Analysis/AliasDebugger.cpp
+++ b/lib/Analysis/AliasDebugger.cpp
@@ -113,9 +113,9 @@ namespace {
       return AliasAnalysis::getModRefInfo(CS1,CS2);
     }
     
-    bool pointsToConstantMemory(const Location &Loc) {
+    bool pointsToConstantMemory(const Location &Loc, bool OrLocal) {
       assert(Vals.find(Loc.Ptr) != Vals.end() && "Never seen value in AA before");
-      return AliasAnalysis::pointsToConstantMemory(Loc);
+      return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
     }
 
     virtual void deleteValue(Value *V) {
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 221c8639e0..db493eeedc 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -456,7 +456,7 @@ namespace {
 
     /// pointsToConstantMemory - Chase pointers until we find a (constant
     /// global) or not.
-    virtual bool pointsToConstantMemory(const Location &Loc);
+    virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
 
     /// getModRefBehavior - Return the behavior when calling the given
     /// call site.
@@ -517,18 +517,61 @@ ImmutablePass *llvm::createBasicAliasAnalysisPass() {
   return new BasicAliasAnalysis();
 }
 
+/// pointsToConstantMemory - 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
+BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) {
+  assert(Visited.empty() && "Visited must be cleared after use!");
 
-/// pointsToConstantMemory - Chase pointers until we find a (constant
-/// global) or not.
-bool BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
-  if (const GlobalVariable *GV = 
-        dyn_cast<GlobalVariable>(Loc.Ptr->getUnderlyingObject()))
-    // Note: this doesn't require GV to be "ODR" because it isn't legal for a
-    // global to be marked constant in some modules and non-constant in others.
-    // GV may even be a declaration, not a definition.
-    return GV->isConstant();
+  SmallVector<const Value *, 16> Worklist;
+  Worklist.push_back(Loc.Ptr);
+  do {
+    const Value *V = Worklist.pop_back_val()->getUnderlyingObject();
+    if (!Visited.insert(V)) {
+      Visited.clear();
+      return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+    }
+
+    // An alloca instruction defines local memory.
+    if (OrLocal && isa<AllocaInst>(V))
+      continue;
+
+    // A global constant counts as local memory for our purposes.
+    if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
+      // Note: this doesn't require GV to be "ODR" because it isn't legal for a
+      // global to be marked constant in some modules and non-constant in
+      // others.  GV may even be a declaration, not a definition.
+      if (!GV->isConstant()) {
+        Visited.clear();
+        return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+      }
+      continue;
+    }
+
+    // If both select values point to local memory, then so does the select.
+    if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
+      Worklist.push_back(SI->getTrueValue());
+      Worklist.push_back(SI->getFalseValue());
+      continue;
+    }
+
+    // If all values incoming to a phi node point to local memory, then so does
+    // the phi.
+    if (const PHINode *PN = dyn_cast<PHINode>(V)) {
+      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+        Worklist.push_back(PN->getIncomingValue(i));
+      continue;
+    }
+
+    // Otherwise be conservative.
+    Visited.clear();
+    return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+
+  } while (!Worklist.empty());
 
-  return AliasAnalysis::pointsToConstantMemory(Loc);
+  Visited.clear();
+  return true;
 }
 
 /// getModRefBehavior - Return the behavior when calling the given call site.
diff --git a/lib/Analysis/NoAliasAnalysis.cpp b/lib/Analysis/NoAliasAnalysis.cpp
index 7602149edc..ab7a69241e 100644
--- a/lib/Analysis/NoAliasAnalysis.cpp
+++ b/lib/Analysis/NoAliasAnalysis.cpp
@@ -50,7 +50,10 @@ namespace {
       return UnknownModRefBehavior;
     }
 
-    virtual bool pointsToConstantMemory(const Location &Loc) { return false; }
+    virtual bool pointsToConstantMemory(const Location &Loc,
+                                        bool OrLocal) {
+      return false;
+    }
     virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
                                        const Location &Loc) {
       return ModRef;
diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp
index 0516d64a71..044a93f866 100644
--- a/lib/Analysis/TypeBasedAliasAnalysis.cpp
+++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp
@@ -138,7 +138,7 @@ namespace {
   private:
     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
     virtual AliasResult alias(const Location &LocA, const Location &LocB);
-    virtual bool pointsToConstantMemory(const Location &Loc);
+    virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
     virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
                                        const Location &Loc);
     virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
@@ -225,19 +225,20 @@ TypeBasedAliasAnalysis::alias(const Location &LocA,
   return NoAlias;
 }
 
-bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
+bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc,
+                                                    bool OrLocal) {
   if (!EnableTBAA)
-    return AliasAnalysis::pointsToConstantMemory(Loc);
+    return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 
   const MDNode *M = Loc.TBAATag;
-  if (!M) return AliasAnalysis::pointsToConstantMemory(Loc);
+  if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 
   // If this is an "immutable" type, we can assume the pointer is pointing
   // to constant memory.
   if (TBAANode(M).TypeIsImmutable())
     return true;
 
-  return AliasAnalysis::pointsToConstantMemory(Loc);
+  return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
 }
 
 AliasAnalysis::ModRefResult
diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp
index 062e366158..be5d827e8e 100644
--- a/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -66,8 +66,6 @@ namespace {
       CallGraphSCCPass::getAnalysisUsage(AU);
     }
 
-    bool PointsToLocalOrConstantMemory(Value *V);
-
   private:
     AliasAnalysis *AA;
   };
@@ -83,53 +81,6 @@ INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
 
 
-/// PointsToLocalOrConstantMemory - 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 FunctionAttrs::PointsToLocalOrConstantMemory(Value *V) {
-  SmallVector<Value*, 16> Worklist;
-  unsigned MaxLookup = 8;
-
-  Worklist.push_back(V);
-
-  do {
-    V = Worklist.pop_back_val()->getUnderlyingObject();
-
-    // An alloca instruction defines local memory.
-    if (isa<AllocaInst>(V))
-      continue;
-
-    // A global constant counts as local memory for our purposes.
-    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
-      if (!GV->isConstant())
-        return false;
-      continue;
-    }
-
-    // If both select values point to local memory, then so does the select.
-    if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
-      Worklist.push_back(SI->getTrueValue());
-      Worklist.push_back(SI->getFalseValue());
-      continue;
-    }
-
-    // If all values incoming to a phi node point to local memory, then so does
-    // the phi.
-    if (PHINode *PN = dyn_cast<PHINode>(V)) {
-      // Don't bother inspecting phi nodes with many operands.
-      if (PN->getNumIncomingValues() > MaxLookup)
-        return false;
-      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
-        Worklist.push_back(PN->getIncomingValue(i));
-      continue;
-    }
-
-    return false;
-  } while (!Worklist.empty() && --MaxLookup);
-
-  return Worklist.empty();
-}
-
 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
   SmallPtrSet<Function*, 8> SCCNodes;
@@ -190,7 +141,7 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
                CI != CE; ++CI) {
             Value *Arg = *CI;
             if (Arg->getType()->isPointerTy() &&
-                !PointsToLocalOrConstantMemory(Arg))
+                !AA->pointsToConstantMemory(Arg, /*OrLocal=*/true))
               // Writes memory.  Just give up.
               return false;
           }
@@ -203,12 +154,14 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
       } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
         // Ignore non-volatile loads from local memory.
         if (!LI->isVolatile() &&
-            PointsToLocalOrConstantMemory(LI->getPointerOperand()))
+            AA->pointsToConstantMemory(LI->getPointerOperand(),
+                                       /*OrLocal=*/true))
           continue;
       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
         // Ignore non-volatile stores to local memory.
         if (!SI->isVolatile() &&
-            PointsToLocalOrConstantMemory(SI->getPointerOperand()))
+            AA->pointsToConstantMemory(SI->getPointerOperand(),
+                                       /*OrLocal=*/true))
           continue;
       }
 
diff --git a/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll b/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll
index 672b5e1392..9655da45c6 100644
--- a/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll
+++ b/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -functionattrs -S | grep readnone
+; RUN: opt < %s -basicaa -functionattrs -S | grep readnone
 
 @s = external constant i8		; <i8*> [#uses=1]