Index: lib/Transforms/IPO/FunctionAttrs.cpp
===================================================================
--- lib/Transforms/IPO/FunctionAttrs.cpp
+++ lib/Transforms/IPO/FunctionAttrs.cpp
@@ -74,6 +74,7 @@
   bool AddArgumentAttrs(const CallGraphSCC &SCC);
   bool AddNoAliasAttrs(const CallGraphSCC &SCC);
   bool AddNonNullAttrs(const CallGraphSCC &SCC);
+  bool AddNoRecurseAttrs(const CallGraphSCC &SCC);
   bool annotateLibraryCalls(const CallGraphSCC &SCC);
 };
 }
@@ -1826,6 +1827,29 @@
   return MadeChange;
 }
 
+bool FunctionAttrs::AddNoRecurseAttrs(const CallGraphSCC &SCC) {
+  // For a function not to recurse, it must be in its own SCC and must not
+  // call itself or be callable by external functions.
+  if (!SCC.isSingular())
+    return false;
+
+  const CallGraphNode *CGN = *SCC.begin();
+  Function *F = CGN->getFunction();
+  if (!F || F->isDeclaration())
+    return false;
+
+  if (std::any_of(CGN->begin(), CGN->end(),
+                  [](const CallGraphNode::CallRecord &CR) {
+                    Function *F = CR.second->getFunction();
+                    return !F || !F->doesNotRecurse();
+                  }))
+    // Function calls a potentially recursive function.
+    return false;
+
+  F->setDoesNotRecurse();
+  return true;
+}
+
 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
@@ -1834,5 +1858,6 @@
   Changed |= AddArgumentAttrs(SCC);
   Changed |= AddNoAliasAttrs(SCC);
   Changed |= AddNonNullAttrs(SCC);
+  Changed |= AddNoRecurseAttrs(SCC);
   return Changed;
 }
Index: test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll
===================================================================
--- test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll
+++ test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll
@@ -10,15 +10,16 @@
 	ret i32 %tmp
 }
 
-; CHECK: define i32 @g() #0
+; CHECK: define i32 @g() #1
 define i32 @g() readonly {
 	ret i32 0
 }
 
-; CHECK: define i32 @h() #0
+; CHECK: define i32 @h() #1
 define i32 @h() readnone {
 	%tmp = load i32, i32* @x		; <i32> [#uses=1]
 	ret i32 %tmp
 }
 
 ; CHECK: attributes #0 = { readnone }
+; CHECK: attributes #1 = { norecurse readnone }
Index: test/Transforms/FunctionAttrs/2010-10-30-volatile.ll
===================================================================
--- test/Transforms/FunctionAttrs/2010-10-30-volatile.ll
+++ test/Transforms/FunctionAttrs/2010-10-30-volatile.ll
@@ -4,7 +4,9 @@
 @g = constant i32 1
 
 define void @foo() {
-; CHECK: void @foo() {
+; CHECK: void @foo() #0 {
   %tmp = load volatile i32, i32* @g
   ret void
 }
+
+; CHECK: attributes #0 = { norecurse }
Index: test/Transforms/FunctionAttrs/atomic.ll
===================================================================
--- test/Transforms/FunctionAttrs/atomic.ll
+++ test/Transforms/FunctionAttrs/atomic.ll
@@ -19,5 +19,5 @@
   ret i32 %r
 }
 
-; CHECK: attributes #0 = { readnone ssp uwtable }
-; CHECK: attributes #1 = { ssp uwtable }
+; CHECK: attributes #0 = { norecurse readnone ssp uwtable }
+; CHECK: attributes #1 = { norecurse ssp uwtable }
Index: test/Transforms/FunctionAttrs/norecurse.ll
===================================================================
--- /dev/null
+++ test/Transforms/FunctionAttrs/norecurse.ll
@@ -0,0 +1,33 @@
+; RUN: opt < %s -basicaa -functionattrs -S | FileCheck %s
+
+; CHECK: define i32 @f() #0
+define i32 @f() {
+  ret i32 1
+}
+
+; CHECK: define i32 @g() #1
+define i32 @g() {
+  %a = call i32 @g()
+  ret i32 4
+}
+
+; CHECK: define i32 @h() #1
+define i32 @h() {
+  %a = call i32 @i()
+  ret i32 %a
+}
+; CHECK: define i32 @i() #1
+define i32 @i() {
+  %a = call i32 @h()
+  ret i32 %a
+}
+
+; CHECK: define i32 @j() #1
+define i32 @j() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+declare i32 @k() readnone
+
+; CHECK: attributes #0 = { norecurse readnone }
+; CHECK: attributes #1 = { readnone }
Index: test/Transforms/FunctionAttrs/optnone.ll
===================================================================
--- test/Transforms/FunctionAttrs/optnone.ll
+++ test/Transforms/FunctionAttrs/optnone.ll
@@ -16,9 +16,11 @@
 
 declare i8 @strlen(i8*) noinline optnone
 ; CHECK-LABEL: @strlen
-; CHECK: (i8*) #1
+; CHECK: (i8*) #2
 
 ; CHECK-LABEL: attributes #0
-; CHECK: = { readnone }
+; CHECK: = { norecurse readnone }
 ; CHECK-LABEL: attributes #1
+; CHECK: = { noinline norecurse optnone }
+; CHECK-LABEL: attributes #2
 ; CHECK: = { noinline optnone }