Fix a README item: have functionattrs look through selects and

phi nodes when deciding which pointers point to local memory.
I actually checked long ago how useful this is, and it isn't
very: it hardly ever fires in the testsuite, but since Chris
wants it here it is!


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

3 files changed, 69 insertions, 42 deletions

diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 38c3daa938..69da35f1c7 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -1648,36 +1648,7 @@ would delete the or instruction for us.
 
 //===---------------------------------------------------------------------===//
 
-FunctionAttrs is not marking this function as readnone (just readonly):
-$ clang t.c -emit-llvm -S -o - -O0 | opt -mem2reg -S -functionattrs
-
-int t(int a, int b, int c) {
- int *p;
- if (a)
-   p = &a;
- else
-   p = &c;
- return *p;
-}
-
-This is because we codegen this to:
-
-define i32 @t(i32 %a, i32 %b, i32 %c) nounwind readonly ssp {
-entry:
-  %a.addr = alloca i32                            ; <i32*> [#uses=3]
-  %c.addr = alloca i32                            ; <i32*> [#uses=2]
-...
-
-if.end:
-  %p.0 = phi i32* [ %a.addr, %if.then ], [ %c.addr, %if.else ]
-  %tmp2 = load i32* %p.0                          ; <i32> [#uses=1]
-  ret i32 %tmp2
-}
-
-And functionattrs doesn't realize that the p.0 load points to function local
-memory.
-
-Also, functionattrs doesn't know about memcpy/memset.  This function should be
+functionattrs doesn't know much about memcpy/memset.  This function should be
 marked readnone rather than readonly, since it only twiddles local memory, but
 functionattrs doesn't handle memset/memcpy/memmove aggressively:
 
diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp
index 0bff2b94e9..f41698adc5 100644
--- a/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -79,16 +79,47 @@ Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
 /// memory that is local to the function.  Global constants are considered
 /// local to all functions.
 bool FunctionAttrs::PointsToLocalMemory(Value *V) {
-  V = V->getUnderlyingObject();
-  // An alloca instruction defines local memory.
-  if (isa<AllocaInst>(V))
-    return true;
-  // A global constant counts as local memory for our purposes.
-  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
-    return GV->isConstant();
-  // Could look through phi nodes and selects here, but it doesn't seem
-  // to be useful in practice.
-  return false;
+  SmallVector<Value*, 8> Worklist;
+  unsigned MaxLookup = 4;
+
+  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.
diff --git a/test/Transforms/FunctionAttrs/2008-10-04-LocalMemory.ll b/test/Transforms/FunctionAttrs/2008-10-04-LocalMemory.ll
index 460780d8ea..c6c2e13e33 100644
--- a/test/Transforms/FunctionAttrs/2008-10-04-LocalMemory.ll
+++ b/test/Transforms/FunctionAttrs/2008-10-04-LocalMemory.ll
@@ -1,10 +1,11 @@
-; RUN: opt < %s -functionattrs -S | grep readonly | count 3
+; RUN: opt < %s -functionattrs -S | FileCheck %s
 
 %struct.X = type { i32*, i32* }
 
-declare i32 @g(i32*) readonly
+declare i32 @g(i32*) readnone
 
 define i32 @f() {
+; CHECK: @f() readnone
 	%x = alloca i32		; <i32*> [#uses=2]
 	store i32 0, i32* %x
 	%y = call i32 @g(i32* %x)		; <i32> [#uses=1]
@@ -12,6 +13,7 @@ define i32 @f() {
 }
 
 define i32 @foo() nounwind {
+; CHECK: @foo() nounwind readonly
 entry:
   %y = alloca %struct.X                           ; <%struct.X*> [#uses=2]
   %x = alloca %struct.X                           ; <%struct.X*> [#uses=2]
@@ -36,4 +38,27 @@ return:                                           ; preds = %entry
   ret i32 %4
 }
 
+define i32 @t(i32 %a, i32 %b, i32 %c) nounwind {
+; CHECK: @t(i32 %a, i32 %b, i32 %c) nounwind readnone
+entry:
+  %a.addr = alloca i32                            ; <i32*> [#uses=3]
+  %c.addr = alloca i32                            ; <i32*> [#uses=2]
+  store i32 %a, i32* %a.addr
+  store i32 %c, i32* %c.addr
+  %tmp = load i32* %a.addr                        ; <i32> [#uses=1]
+  %tobool = icmp ne i32 %tmp, 0                   ; <i1> [#uses=1]
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %p.0 = phi i32* [ %a.addr, %if.then ], [ %c.addr, %if.else ] ; <i32*> [#uses=1]
+  %tmp2 = load i32* %p.0                          ; <i32> [#uses=1]
+  ret i32 %tmp2
+}
+
 declare void @llvm.memcpy.i64(i8* nocapture, i8* nocapture, i64, i32) nounwind