[FunctionAttrs] Identify norecurse functions

A function can be marked as norecurse if:
  * The SCC to which it belongs has cardinality 1; and either
    a) It does not call any non-norecurse function. This includes self-recursion; or
    b) It only has one callsite and the function that callsite is within is marked norecurse.

a) is best propagated bottom-up and b) is best propagated top-down.

We build up the norecurse attributes bottom-up using the existing SCC pass, and mark functions with no obvious recursion (but not provably norecurse) to sweep later, top-down.

llvm-svn: 252862

6 files changed, 74 insertions, 10 deletions

diff --git a/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll b/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll
index 6c9439afeea..44031417032 100644
--- a/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll
+++ b/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll
@@ -30,7 +30,7 @@ define void @test1_yes(i32* %p) nounwind {
   ret void
 }
 
-; CHECK: define void @test1_no(i32* %p) #1 {
+; CHECK: define void @test1_no(i32* %p) #3 {
 define void @test1_no(i32* %p) nounwind {
   call void @callee(i32* %p), !tbaa !2
   ret void
@@ -72,9 +72,11 @@ define i32 @test3_no(i8* %p) nounwind {
 declare void @callee(i32* %p) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1) nounwind
 
-; CHECK: attributes #0 = { nounwind readnone }
-; CHECK: attributes #1 = { nounwind }
+; CHECK: attributes #0 = { norecurse nounwind readnone }
+; CHECK: attributes #1 = { norecurse nounwind }
 ; CHECK: attributes #2 = { nounwind readonly }
+; CHECK: attributes #3 = { nounwind }
+; CHECK: attributes #4 = { nounwind argmemonly }
 
 ; Root note.
 !0 = !{ }
diff --git a/llvm/test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll b/llvm/test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll
index ca05d63743b..b62698a776f 100644
--- a/llvm/test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll
+++ b/llvm/test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll
@@ -10,15 +10,16 @@ define i32 @f() {
 	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 }
diff --git a/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll b/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll
index 1a64a839380..23bb18e92b4 100644
--- a/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll
+++ b/llvm/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 }
diff --git a/llvm/test/Transforms/FunctionAttrs/atomic.ll b/llvm/test/Transforms/FunctionAttrs/atomic.ll
index bb867011cc2..dd915a6027f 100644
--- a/llvm/test/Transforms/FunctionAttrs/atomic.ll
+++ b/llvm/test/Transforms/FunctionAttrs/atomic.ll
@@ -19,5 +19,5 @@ entry:
   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 }
diff --git a/llvm/test/Transforms/FunctionAttrs/norecurse.ll b/llvm/test/Transforms/FunctionAttrs/norecurse.ll
new file mode 100644
index 00000000000..47481191d27
--- /dev/null
+++ b/llvm/test/Transforms/FunctionAttrs/norecurse.ll
@@ -0,0 +1,57 @@
+; RUN: opt < %s -basicaa -functionattrs -S | FileCheck %s
+
+; CHECK: define i32 @leaf() #0
+define i32 @leaf() {
+  ret i32 1
+}
+
+; CHECK: define i32 @self_rec() #1
+define i32 @self_rec() {
+  %a = call i32 @self_rec()
+  ret i32 4
+}
+
+; CHECK: define i32 @indirect_rec() #1
+define i32 @indirect_rec() {
+  %a = call i32 @indirect_rec2()
+  ret i32 %a
+}
+; CHECK: define i32 @indirect_rec2() #1
+define i32 @indirect_rec2() {
+  %a = call i32 @indirect_rec()
+  ret i32 %a
+}
+
+; CHECK: define i32 @extern() #1
+define i32 @extern() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+declare i32 @k() readnone
+
+; CHECK: define internal i32 @called_by_norecurse() #0
+define internal i32 @called_by_norecurse() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+define void @m() norecurse {
+  %a = call i32 @called_by_norecurse()
+  ret void
+}
+
+; CHECK: define internal i32 @called_by_norecurse_indirectly() #0
+define internal i32 @called_by_norecurse_indirectly() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+define internal void @o() {
+  %a = call i32 @called_by_norecurse_indirectly()
+  ret void
+}
+define void @p() norecurse {
+  call void @o()
+  ret void
+}
+
+; CHECK: attributes #0 = { norecurse readnone }
+; CHECK: attributes #1 = { readnone }
diff --git a/llvm/test/Transforms/FunctionAttrs/optnone.ll b/llvm/test/Transforms/FunctionAttrs/optnone.ll
index 7694bfe13aa..441ff4da65e 100644
--- a/llvm/test/Transforms/FunctionAttrs/optnone.ll
+++ b/llvm/test/Transforms/FunctionAttrs/optnone.ll
@@ -16,9 +16,11 @@ define void @test_optnone(i8* %p) noinline optnone {
 
 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 }