[thinlto] Basic thinlto fdo heuristic

Summary:
This patch improves thinlto importer
by importing 3x larger functions that are called from hot block.

I compared performance with the trunk on spec, and there
were about 2% on povray and 3.33% on milc. These results seems
to be consistant and match the results Teresa got with her simple
heuristic. Some benchmarks got slower but I think they are just
noisy (mcf, xalancbmki, omnetpp)- running the benchmarks again with
more iterations to confirm. Geomean of all benchmarks including the noisy ones
were about +0.02%.

I see much better improvement on google branch with Easwaran patch
for pgo callsite inlining (the inliner actually inline those big functions)
Over all I see +0.5% improvement, and I get +8.65% on povray.
So I guess we will see much bigger change when Easwaran patch will land
(it depends on new pass manager), but it is still worth putting this to trunk
before it.

Implementation details changes:
- Removed CallsiteCount.
- ProfileCount got replaced by Hotness
- hot-import-multiplier is set to 3.0 for now,
didn't have time to tune it up, but I see that we get most of the interesting
functions with 3, so there is no much performance difference with higher, and
binary size doesn't grow as much as with 10.0.

Reviewers: eraman, mehdi_amini, tejohnson

Subscribers: mehdi_amini, llvm-commits

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

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

11 files changed, 156 insertions, 14 deletions

diff --git a/test/Bitcode/Inputs/thinlto-function-summary-callgraph-combined.1.bc b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-combined.1.bc
new file mode 100644
index 00000000000..e6a13402005
--- /dev/null
+++ b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-combined.1.bc
diff --git a/test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo-combined.1.bc b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo-combined.1.bc
new file mode 100644
index 00000000000..11b9037e568
--- /dev/null
+++ b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo-combined.1.bc
diff --git a/test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo.1.bc b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo.1.bc
new file mode 100644
index 00000000000..cb3380efcb8
--- /dev/null
+++ b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-pgo.1.bc
diff --git a/test/Bitcode/Inputs/thinlto-function-summary-callgraph-profile-summary.ll b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-profile-summary.ll
new file mode 100644
index 00000000000..f7d2ca839b9
--- /dev/null
+++ b/test/Bitcode/Inputs/thinlto-function-summary-callgraph-profile-summary.ll
@@ -0,0 +1,27 @@
+; ModuleID = 'thinlto-function-summary-callgraph-profile-summary2.ll'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+
+define void @hot1() #1 {
+  ret void
+}
+define void @hot2() #1 {
+  ret void
+}
+define void @hot3() #1 {
+  ret void
+}
+define void @cold() #1 {
+  ret void
+}
+define void @none1() #1 {
+  ret void
+}
+define void @none2() #1 {
+  ret void
+}
+define void @none3() #1 {
+  ret void
+}
+
diff --git a/test/Bitcode/Inputs/thinlto-function-summary-callgraph.1.bc b/test/Bitcode/Inputs/thinlto-function-summary-callgraph.1.bc
new file mode 100644
index 00000000000..d42da69fcff
--- /dev/null
+++ b/test/Bitcode/Inputs/thinlto-function-summary-callgraph.1.bc
diff --git a/test/Bitcode/summary_version.ll b/test/Bitcode/summary_version.ll
index 718a0ab9bd7..dfb9e9b15e7 100644
--- a/test/Bitcode/summary_version.ll
+++ b/test/Bitcode/summary_version.ll
@@ -2,7 +2,7 @@
 ; RUN: opt  -module-summary  %s -o - | llvm-bcanalyzer -dump | FileCheck %s
 
 ; CHECK: <GLOBALVAL_SUMMARY_BLOCK
-; CHECK: <VERSION op0=1/>
+; CHECK: <VERSION op0=2/>
 
 
 
diff --git a/test/Bitcode/thinlto-alias.ll b/test/Bitcode/thinlto-alias.ll
index 58411ca6523..cfdf8f7b0bd 100644
--- a/test/Bitcode/thinlto-alias.ll
+++ b/test/Bitcode/thinlto-alias.ll
@@ -9,7 +9,7 @@
 ; CHECK-NEXT:    <VERSION
 ; See if the call to func is registered, using the expected callsite count
 ; and value id matching the subsequent value symbol table.
-; CHECK-NEXT:    <PERMODULE {{.*}} op4=[[FUNCID:[0-9]+]] op5=1/>
+; CHECK-NEXT:    <PERMODULE {{.*}} op4=[[FUNCID:[0-9]+]]/>
 ; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; CHECK-NEXT:  <VALUE_SYMTAB
 ; CHECK-NEXT:    <FNENTRY {{.*}} record string = 'main'
@@ -21,7 +21,7 @@
 ; COMBINED-NEXT:    <VERSION
 ; See if the call to analias is registered, using the expected callsite count
 ; and value id matching the subsequent value symbol table.
-; COMBINED-NEXT:    <COMBINED {{.*}} op5=[[ALIASID:[0-9]+]] op6=1/>
+; COMBINED-NEXT:    <COMBINED {{.*}} op5=[[ALIASID:[0-9]+]]/>
 ; Followed by the alias and aliasee
 ; COMBINED-NEXT:    <COMBINED {{.*}}
 ; COMBINED-NEXT:    <COMBINED_ALIAS  {{.*}} op3=[[ALIASEEID:[0-9]+]]
diff --git a/test/Bitcode/thinlto-function-summary-callgraph-pgo.ll b/test/Bitcode/thinlto-function-summary-callgraph-pgo.ll
index a927a16be15..713e36dd14d 100644
--- a/test/Bitcode/thinlto-function-summary-callgraph-pgo.ll
+++ b/test/Bitcode/thinlto-function-summary-callgraph-pgo.ll
@@ -1,15 +1,20 @@
 ; Test to check the callgraph in summary when there is PGO
 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
+
 ; RUN: opt -module-summary %p/Inputs/thinlto-function-summary-callgraph.ll -o %t2.o
 ; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o
 ; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED
 
+; Check parsing for old summary versions generated from this file.
+; RUN: llvm-lto -thinlto-index-stats %p/Inputs/thinlto-function-summary-callgraph-pgo.1.bc  | FileCheck %s --check-prefix=OLD
+; RUN: llvm-lto -thinlto-index-stats %p/Inputs/thinlto-function-summary-callgraph-pgo-combined.1.bc  | FileCheck %s --check-prefix=OLD-COMBINED
+
 ; CHECK:       <GLOBALVAL_SUMMARY_BLOCK
 ; CHECK-NEXT:    <VERSION
 ; See if the call to func is registered, using the expected callsite count
-; and profile count, with value id matching the subsequent value symbol table.
-; CHECK-NEXT:    <PERMODULE_PROFILE {{.*}} op4=[[FUNCID:[0-9]+]] op5=1 op6=1/>
+; and hotness type, with value id matching the subsequent value symbol table.
+; CHECK-NEXT:    <PERMODULE_PROFILE {{.*}} op4=[[FUNCID:[0-9]+]] op5=2/>
 ; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; CHECK-NEXT:  <VALUE_SYMTAB
 ; CHECK-NEXT:    <FNENTRY {{.*}} record string = 'main'
@@ -21,8 +26,9 @@
 ; COMBINED-NEXT:    <VERSION
 ; COMBINED-NEXT:    <COMBINED
 ; See if the call to func is registered, using the expected callsite count
-; and profile count, with value id matching the subsequent value symbol table.
-; COMBINED-NEXT:    <COMBINED_PROFILE {{.*}} op5=[[FUNCID:[0-9]+]] op6=1 op7=1/>
+; and hotness type, with value id matching the subsequent value symbol table.
+; op6=2 which is hotnessType::None.
+; COMBINED-NEXT:    <COMBINED_PROFILE {{.*}} op5=[[FUNCID:[0-9]+]] op6=2/>
 ; COMBINED-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; COMBINED-NEXT:  <VALUE_SYMTAB
 ; Entry for function func should have entry with value id FUNCID
@@ -44,3 +50,6 @@ entry:
 declare void @func(...) #1
 
 !2 = !{!"function_entry_count", i64 1}
+
+; OLD: Index {{.*}} contains 1 nodes (1 functions, 0 alias, 0 globals) and 1 edges (0 refs and 1 calls)
+; OLD-COMBINED: Index {{.*}} contains 2 nodes (2 functions, 0 alias, 0 globals) and 1 edges (0 refs and 1 calls)
diff --git a/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll b/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll
new file mode 100644
index 00000000000..fd12d3f99f6
--- /dev/null
+++ b/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll
@@ -0,0 +1,98 @@
+; Test to check the callgraph in summary when there is PGO
+; RUN: opt -module-summary %s -o %t.o
+; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
+; RUN: opt -module-summary %p/Inputs/thinlto-function-summary-callgraph-profile-summary.ll -o %t2.o
+; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o
+; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED
+
+
+; CHECK-LABEL:       <GLOBALVAL_SUMMARY_BLOCK
+; CHECK-NEXT:    <VERSION
+; See if the call to func is registered, using the expected callsite count
+; and profile count, with value id matching the subsequent value symbol table.
+; CHECK-NEXT:    <PERMODULE_PROFILE {{.*}} op4=[[HOT1:.*]] op5=3 op6=[[HOT2:.*]] op7=3 op8=[[HOT3:.*]] op9=3 op10=[[COLD:.*]] op11=1 op12=[[NONE1:.*]] op13=2 op14=[[NONE2:.*]] op15=2 op16=[[NONE3:.*]] op17=2/>
+; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
+; CHECK-LABEL:  <VALUE_SYMTAB
+; CHECK-NEXT:       <FNENTRY {{.*}} record string = 'hot_function
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[NONE1]] {{.*}} record string = 'none1'
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[COLD]] {{.*}} record string = 'cold'
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[NONE2]] {{.*}} record string = 'none2'
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[NONE3]] {{.*}} record string = 'none3'
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[HOT1]] {{.*}} record string = 'hot1'
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[HOT2]] {{.*}} record string = 'hot2'
+; CHECK-DAG:        <ENTRY abbrevid=6 op0=[[HOT3]] {{.*}} record string = 'hot3'
+; CHECK-LABEL:  </VALUE_SYMTAB>
+
+; COMBINED:       <GLOBALVAL_SUMMARY_BLOCK
+; COMBINED-NEXT:    <VERSION
+; COMBINED-NEXT:    <COMBINED abbrevid=
+; COMBINED-NEXT:    <COMBINED abbrevid=
+; COMBINED-NEXT:    <COMBINED abbrevid=
+; COMBINED-NEXT:    <COMBINED abbrevid=
+; COMBINED-NEXT:    <COMBINED abbrevid=
+; COMBINED-NEXT:    <COMBINED abbrevid=
+; COMBINED-NEXT:    <COMBINED_PROFILE {{.*}} op5=[[HOT1:.*]] op6=3 op7=[[HOT2:.*]] op8=3 op9=[[HOT3:.*]] op10=3 op11=[[COLD:.*]] op12=1 op13=[[NONE1:.*]] op14=2 op15=[[NONE2:.*]] op16=2 op17=[[NONE3:.*]] op18=2/>
+; COMBINED_NEXT:    <COMBINED abbrevid=
+; COMBINED_NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
+
+
+; ModuleID = 'thinlto-function-summary-callgraph.ll'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; This function have high profile count, so entry block is hot.
+define void @hot_function(i1 %a, i1 %a2) !prof !20 {
+entry:
+    call void @hot1()
+    br i1 %a, label %Cold, label %Hot, !prof !41
+Cold:           ; 1/1000 goes here
+  call void @cold()
+  call void @hot2()
+  call void @none1()
+  br label %exit
+Hot:            ; 999/1000 goes here
+  call void @hot2()
+  call void @hot3()
+  br i1 %a2, label %None1, label %None2, !prof !42
+None1:          ; half goes here
+  call void @none1()
+  call void @none2()
+  br label %exit
+None2:          ; half goes here
+  call void @none3()
+  br label %exit
+exit:
+  ret void
+}
+
+declare void @hot1() #1
+declare void @hot2() #1
+declare void @hot3() #1
+declare void @cold() #1
+declare void @none1() #1
+declare void @none2() #1
+declare void @none3() #1
+
+
+!41 = !{!"branch_weights", i32 1, i32 1000}
+!42 = !{!"branch_weights", i32 1, i32 1}
+
+
+
+!llvm.module.flags = !{!1}
+!20 = !{!"function_entry_count", i64 110}
+
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 10000}
+!5 = !{!"MaxCount", i64 10}
+!6 = !{!"MaxInternalCount", i64 1}
+!7 = !{!"MaxFunctionCount", i64 1000}
+!8 = !{!"NumCounts", i64 3}
+!9 = !{!"NumFunctions", i64 3}
+!10 = !{!"DetailedSummary", !11}
+!11 = !{!12, !13, !14}
+!12 = !{i32 10000, i64 100, i32 1}
+!13 = !{i32 999000, i64 100, i32 1}
+!14 = !{i32 999999, i64 1, i32 2}
diff --git a/test/Bitcode/thinlto-function-summary-callgraph.ll b/test/Bitcode/thinlto-function-summary-callgraph.ll
index af38c3ef121..c00907b7fb2 100644
--- a/test/Bitcode/thinlto-function-summary-callgraph.ll
+++ b/test/Bitcode/thinlto-function-summary-callgraph.ll
@@ -1,15 +1,20 @@
 ; Test to check the callgraph in summary
 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: llvm-bcanalyzer -dump %t.o | FileCheck %s
+
 ; RUN: opt -module-summary %p/Inputs/thinlto-function-summary-callgraph.ll -o %t2.o
 ; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o
 ; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED
 
+; Check parsing for old summary versions generated from this file.
+; RUN: llvm-lto -thinlto-index-stats %p/Inputs/thinlto-function-summary-callgraph.1.bc  | FileCheck %s --check-prefix=OLD
+; RUN: llvm-lto -thinlto-index-stats %p/Inputs/thinlto-function-summary-callgraph-combined.1.bc  | FileCheck %s --check-prefix=OLD-COMBINED
+
 ; CHECK:       <GLOBALVAL_SUMMARY_BLOCK
 ; CHECK-NEXT:    <VERSION
 ; See if the call to func is registered, using the expected callsite count
 ; and value id matching the subsequent value symbol table.
-; CHECK-NEXT:    <PERMODULE {{.*}} op4=[[FUNCID:[0-9]+]] op5=1/>
+; CHECK-NEXT:    <PERMODULE {{.*}} op4=[[FUNCID:[0-9]+]]/>
 ; CHECK-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; CHECK-NEXT:  <VALUE_SYMTAB
 ; CHECK-NEXT:    <FNENTRY {{.*}} record string = 'main'
@@ -22,7 +27,7 @@
 ; COMBINED-NEXT:    <COMBINED
 ; See if the call to func is registered, using the expected callsite count
 ; and value id matching the subsequent value symbol table.
-; COMBINED-NEXT:    <COMBINED {{.*}} op5=[[FUNCID:[0-9]+]] op6=1/>
+; COMBINED-NEXT:    <COMBINED {{.*}} op5=[[FUNCID:[0-9]+]]/>
 ; COMBINED-NEXT:  </GLOBALVAL_SUMMARY_BLOCK>
 ; COMBINED-NEXT:  <VALUE_SYMTAB
 ; Entry for function func should have entry with value id FUNCID
@@ -42,3 +47,6 @@ entry:
 }
 
 declare void @func(...) #1
+
+; OLD: Index {{.*}} contains 1 nodes (1 functions, 0 alias, 0 globals) and 1 edges (0 refs and 1 calls)
+; OLD-COMBINED: Index {{.*}} contains 2 nodes (2 functions, 0 alias, 0 globals) and 1 edges (0 refs and 1 calls)
\ No newline at end of file
diff --git a/test/Bitcode/thinlto-function-summary-refgraph.ll b/test/Bitcode/thinlto-function-summary-refgraph.ll
index 73aeb08545e..882f86509ab 100644
--- a/test/Bitcode/thinlto-function-summary-refgraph.ll
+++ b/test/Bitcode/thinlto-function-summary-refgraph.ll
@@ -11,20 +11,20 @@
 ; llvm.ctpop.i8.
 ; CHECK:       <GLOBALVAL_SUMMARY_BLOCK
 ; Function main contains call to func, as well as address reference to func:
-; CHECK-DAG:    <PERMODULE {{.*}} op0=[[MAINID:[0-9]+]] op1=0 {{.*}} op3=1 op4=[[FUNCID:[0-9]+]] op5=[[FUNCID]] op6=1/>
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[MAINID:[0-9]+]] op1=0 {{.*}} op3=1 op4=[[FUNCID:[0-9]+]] op5=[[FUNCID]]/>
 ; Function W contains a call to func3 as well as a reference to globalvar:
-; CHECK-DAG:    <PERMODULE {{.*}} op0=[[WID:[0-9]+]] op1=5 {{.*}} op3=1 op4=[[GLOBALVARID:[0-9]+]] op5=[[FUNC3ID:[0-9]+]] op6=1/>
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[WID:[0-9]+]] op1=5 {{.*}} op3=1 op4=[[GLOBALVARID:[0-9]+]] op5=[[FUNC3ID:[0-9]+]]/>
 ; Function X contains call to foo, as well as address reference to foo
 ; which is in the same instruction as the call:
-; CHECK-DAG:    <PERMODULE {{.*}} op0=[[XID:[0-9]+]] op1=1 {{.*}} op3=1 op4=[[FOOID:[0-9]+]] op5=[[FOOID]] op6=1/>
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[XID:[0-9]+]] op1=1 {{.*}} op3=1 op4=[[FOOID:[0-9]+]] op5=[[FOOID]]/>
 ; Function Y contains call to func2, and ensures we don't incorrectly add
 ; a reference to it when reached while earlier analyzing the phi using its
 ; return value:
-; CHECK-DAG:    <PERMODULE {{.*}} op0=[[YID:[0-9]+]] op1=8 {{.*}} op3=0 op4=[[FUNC2ID:[0-9]+]] op5=1/>
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[YID:[0-9]+]] op1=8 {{.*}} op3=0 op4=[[FUNC2ID:[0-9]+]]/>
 ; Function Z contains call to func2, and ensures we don't incorrectly add
 ; a reference to it when reached while analyzing subsequent use of its return
 ; value:
-; CHECK-DAG:    <PERMODULE {{.*}} op0=[[ZID:[0-9]+]] op1=3 {{.*}} op3=0 op4=[[FUNC2ID:[0-9]+]] op5=1/>
+; CHECK-DAG:    <PERMODULE {{.*}} op0=[[ZID:[0-9]+]] op1=3 {{.*}} op3=0 op4=[[FUNC2ID:[0-9]+]]/>
 ; Variable bar initialization contains address reference to func:
 ; CHECK-DAG:    <PERMODULE_GLOBALVAR_INIT_REFS {{.*}} op0=[[BARID:[0-9]+]] op1=0 op2=[[FUNCID]]/>
 ; CHECK:  </GLOBALVAL_SUMMARY_BLOCK>