FunctionImport: add a progressive heuristic to limit importing too deep in the callgraph

The current function importer will walk the callgraph, importing
transitively any callee that is below the threshold. This can
lead to import very deep which is costly in compile time and not
necessarily beneficial as most of the inline would happen in
imported function and not necessarilly in user code.

The actual factor has been carefully chosen by flipping a coin ;)
Some tuning need to be done (just at the existing limiting threshold).

Reviewers: tejohnson

Differential Revision: http://reviews.llvm.org/D17082

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 260466

2 files changed, 68 insertions, 0 deletions

diff --git a/llvm/test/Transforms/FunctionImport/Inputs/adjustable_threshold.ll b/llvm/test/Transforms/FunctionImport/Inputs/adjustable_threshold.ll
new file mode 100644
index 00000000000..fd4644d264a
--- /dev/null
+++ b/llvm/test/Transforms/FunctionImport/Inputs/adjustable_threshold.ll
@@ -0,0 +1,37 @@
+define void @globalfunc1() {
+entry:
+  call void @trampoline()
+  ret void
+}
+; Adds an artificial level in the call graph to reduce the importing threshold
+define void @trampoline() {
+entry:
+  call void @largefunction()
+  ret void
+}
+
+define void @globalfunc2() {
+entry:
+  call void @largefunction()
+  ret void
+}
+
+
+; Size is 5: if two layers below in the call graph the threshold will be 4,
+; but if only one layer below the threshold will be 7.
+define void @largefunction() {
+  entry:
+  call void @staticfunc2()
+  call void @staticfunc2()
+  call void @staticfunc2()
+  call void @staticfunc2()
+  call void @staticfunc2()
+  ret void
+}
+
+define internal void @staticfunc2() {
+entry:
+  ret void
+}
+
+
diff --git a/llvm/test/Transforms/FunctionImport/adjustable_threshold.ll b/llvm/test/Transforms/FunctionImport/adjustable_threshold.ll
new file mode 100644
index 00000000000..c201666e0a1
--- /dev/null
+++ b/llvm/test/Transforms/FunctionImport/adjustable_threshold.ll
@@ -0,0 +1,31 @@
+; Do setup work for all below tests: generate bitcode and combined index
+; RUN: llvm-as -function-summary %s -o %t.bc
+; RUN: llvm-as -function-summary %p/Inputs/adjustable_threshold.ll -o %t2.bc
+; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
+
+; Test import with default progressive instruction factor
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -import-instr-limit=10 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM-DEFAULT
+; INSTLIM-DEFAULT: call void @staticfunc2.llvm.2()
+
+; Test import with a reduced progressive instruction factor
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -import-instr-limit=10 -import-instr-evolution-factor=0.5 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM-PROGRESSIVE
+; INSTLIM-PROGRESSIVE-NOT: call void @staticfunc
+
+
+
+declare void @globalfunc1()
+declare void @globalfunc2()
+
+define void @entry() {
+entry:
+; Call site are processed in reversed order!
+
+; On the direct call, we reconsider @largefunction with a higher threshold and
+; import it
+  call void @globalfunc2()
+; When importing globalfunc1, the threshold was limited and @largefunction was
+; not imported.
+  call void @globalfunc1()
+  ret void
+}
+