[Attributor] Implement "norecurse" function attribute deduction

Summary:
This patch introduces `norecurse` function attribute deduction.

`norecurse` will be deduced if the following conditions hold:
* The size of SCC in which the function belongs equals to 1.
* The function doesn't have self-recursion.
* We have `norecurse` for all call site.

To avoid a large change, SCC is calculated using scc_iterator in InfoCache initialization for now.

Reviewers: jdoerfert, sstefan1

Reviewed By: jdoerfert

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D67751

llvm-svn: 372475

2 files changed, 103 insertions, 48 deletions

diff --git a/llvm/test/Transforms/FunctionAttrs/norecurse.ll b/llvm/test/Transforms/FunctionAttrs/norecurse.ll
index 0293938e479..ed086341c47 100644
--- a/llvm/test/Transforms/FunctionAttrs/norecurse.ll
+++ b/llvm/test/Transforms/FunctionAttrs/norecurse.ll
@@ -1,81 +1,88 @@
-; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s
-; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs),rpo-functionattrs' -S | FileCheck %s
+; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s --check-prefixes=CHECK,BOTH
+; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs),rpo-functionattrs' -S | FileCheck %s --check-prefixes=CHECK,BOTH
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,BOTH
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: norecurse nounwind readnone
-; CHECK-NEXT: define i32 @leaf()
+; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind willreturn
+; BOTH-NEXT: define i32 @leaf()
 define i32 @leaf() {
   ret i32 1
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @self_rec()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @self_rec()
 define i32 @self_rec() {
   %a = call i32 @self_rec()
   ret i32 4
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @indirect_rec()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @indirect_rec()
 define i32 @indirect_rec() {
   %a = call i32 @indirect_rec2()
   ret i32 %a
 }
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @indirect_rec2()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @indirect_rec2()
 define i32 @indirect_rec2() {
   %a = call i32 @indirect_rec()
   ret i32 %a
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @extern()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @extern()
 define i32 @extern() {
   %a = call i32 @k()
   ret i32 %a
 }
 
-; CHECK: Function Attrs
-; CHECK-NEXT: declare i32 @k()
+; BOTH: Function Attrs
+; BOTH-NEXT: declare i32 @k()
 declare i32 @k() readnone
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: nounwind
-; CHECK-NOT: norecurse
+; BOTH-NOT: norecurse
 ; CHECK-NEXT: define void @intrinsic(i8* nocapture %dest, i8* nocapture readonly %src, i32 %len)
+; ATTRIBUTOR-NEXT: define void @intrinsic(i8* nocapture %dest, i8* nocapture %src, i32 %len)
 define void @intrinsic(i8* %dest, i8* %src, i32 %len) {
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 false)
   ret void
 }
 
-; CHECK: Function Attrs
-; CHECK-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32
+; BOTH: Function Attrs
+; BOTH-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i1)
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: norecurse readnone
+; FIXME: missing "norecurse"
+; ATTRIBUTOR-SAME: nosync
 ; CHECK-NEXT: define internal i32 @called_by_norecurse()
 define internal i32 @called_by_norecurse() {
   %a = call i32 @k()
   ret i32 %a
 }
-; CHECK: Function Attrs
-; CHECK-NEXT: define void @m()
+; BOTH: Function Attrs
+; BOTH-NEXT: define void @m()
 define void @m() norecurse {
   %a = call i32 @called_by_norecurse()
   ret void
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: norecurse readnone
+; FIXME: missing "norecurse"
+; ATTRIBUTOR-SAME: nosync
 ; CHECK-NEXT: define internal i32 @called_by_norecurse_indirectly()
 define internal i32 @called_by_norecurse_indirectly() {
   %a = call i32 @k()
@@ -89,3 +96,54 @@ define void @p() norecurse {
   call void @o()
   ret void
 }
+
+; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
+; ATTRIBUTOR-NEXT: define void @f(i32 %x)
+define void @f(i32 %x)  {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4
+  %tobool = icmp ne i32 %0, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  call void @g() norecurse
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; BOTH: define void @g()
+define void @g() norecurse {
+entry:
+  call void @f(i32 0)
+  ret void
+}
+
+; ATTRIBUTOR-NOT: Function Attrs
+; ATTRIBUTOR: define linkonce_odr i32 @leaf_redefinable()
+define linkonce_odr i32 @leaf_redefinable() {
+  ret i32 1
+}
+
+; Call through a function pointer
+; ATTRIBUTOR-NOT: Function Attrs
+; ATTRIBUTOR: define i32 @eval_func(i32 (i32)* nocapture %0, i32 %1)
+define i32 @eval_func(i32 (i32)* , i32) local_unnamed_addr {
+  %3 = tail call i32 %0(i32 %1) #2
+  ret i32 %3
+}
+
+declare void @unknown()
+; Call an unknown function in a dead block.
+; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind willreturn
+; ATTRIBUTOR: define i32 @call_unknown_in_dead_block()
+define i32 @call_unknown_in_dead_block() local_unnamed_addr {
+  ret i32 0
+Dead:
+  tail call void @unknown()
+  ret i32 1
+}
+
diff --git a/llvm/test/Transforms/FunctionAttrs/willreturn.ll b/llvm/test/Transforms/FunctionAttrs/willreturn.ll
index 7821658c952..a1f28e03f19 100644
--- a/llvm/test/Transforms/FunctionAttrs/willreturn.ll
+++ b/llvm/test/Transforms/FunctionAttrs/willreturn.ll
@@ -1,5 +1,5 @@
 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
@@ -11,7 +11,7 @@ target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 ; TEST 1 (positive case)
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define void @only_return()
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable willreturn
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @only_return()
 define void @only_return() #0 {
     ret void
@@ -59,7 +59,7 @@ define i32 @fib(i32 %0) local_unnamed_addr #0 {
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr
 define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr #0 {
@@ -95,7 +95,7 @@ define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr #0 {
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @fact_loop(i32 %0)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @fact_loop(i32 %0) local_unnamed_addr
 define i32 @fact_loop(i32 %0) local_unnamed_addr #0 {
   %2 = icmp slt i32 %0, 1
@@ -253,27 +253,24 @@ define void @call_maybe_noreturn() #0 {
 ; TEST 8 (positive case)
 ; Check propagation.
 
-; FNATTR: Function Attrs: willreturn
+; FNATTR: Function Attrs: norecurse willreturn
 ; FNATTR-NEXT: declare void @will_return()
-; ATTRIBUTOR: Function Attrs: willreturn
+; ATTRIBUTOR: Function Attrs: norecurse willreturn
 ; ATTRIBUTOR-NEXT: declare void @will_return()
-declare void @will_return() willreturn
+declare void @will_return() willreturn norecurse
 
-; FIXME: missing willreturn
-; FNATTR: Function Attrs: noinline nounwind uwtable
+; FNATTR: Function Attrs: noinline norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @f1()
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @f1()
 define void @f1() #0 {
     tail call void @will_return()
     ret void
 }
 
-; FIXME: missing willreturn
-; FNATTR: Function Attrs: noinline nounwind uwtable
+; FNATTR: Function Attrs: noinline norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @f2()
-; FIXME: missing willreturn
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @f2()
 define void @f2() #0 {
     tail call void @f1()
@@ -284,10 +281,10 @@ define void @f2() #0 {
 ; TEST 9 (negative case)
 ; call willreturn function in endless loop.
 
-; FNATTR: Function Attrs: noinline nounwind uwtable
+; FNATTR: Function Attrs: noinline norecurse nounwind uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define void @call_will_return_but_has_loop()
-; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline norecurse noreturn nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define void @call_will_return_but_has_loop()
 define void @call_will_return_but_has_loop() #0 {
@@ -340,7 +337,7 @@ declare i32 @__gxx_personality_v0(...)
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly %0)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly %0)
 define i32 @loop_constant_trip_count(i32* nocapture readonly %0) #0 {
   br label %3
@@ -373,7 +370,7 @@ define i32 @loop_constant_trip_count(i32* nocapture readonly %0) #0 {
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr
 define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr #0 {
@@ -411,7 +408,7 @@ define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2,
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr
 
 define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr #0 {
@@ -442,7 +439,7 @@ define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr
 
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @multiple_return(i32 %a)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable willreturn
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define i32 @multiple_return(i32 %a)
 define i32 @multiple_return(i32 %a) #0 {
   %b =  icmp eq i32 %a, 0
@@ -460,7 +457,7 @@ f:
 ; 15.1 (positive case)
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define void @unreachable_exit_positive1()
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable willreturn
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1()
 define void @unreachable_exit_positive1() #0 {
   tail call void @will_return()
@@ -474,7 +471,7 @@ unreachable_label:
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32 %0)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32 %0)
 define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 {
   %2 = icmp slt i32 %0, 1
@@ -518,7 +515,7 @@ unreachable_label:
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define void @unreachable_exit_negative2()
-; ATTRIBUTOR: Function Attrs: nofree noinline noreturn nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse noreturn nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2()
 define void @unreachable_exit_negative2() #0 {