[PGO] add MST min edge selection heuristic to ensure non-zero entry count

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


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

9 files changed, 35 insertions, 14 deletions

diff --git a/test/Transforms/PGOProfile/Inputs/landingpad.proftext b/test/Transforms/PGOProfile/Inputs/landingpad.proftext
index 07b1bf86fc7..c71fd04170b 100644
--- a/test/Transforms/PGOProfile/Inputs/landingpad.proftext
+++ b/test/Transforms/PGOProfile/Inputs/landingpad.proftext
@@ -11,6 +11,6 @@ foo
 bar
 24868915205
 2
-1
+3
 2
 
diff --git a/test/Transforms/PGOProfile/Inputs/noreturncall.proftext b/test/Transforms/PGOProfile/Inputs/noreturncall.proftext
index 73ee83f6e9d..1bedce5b9f9 100644
--- a/test/Transforms/PGOProfile/Inputs/noreturncall.proftext
+++ b/test/Transforms/PGOProfile/Inputs/noreturncall.proftext
@@ -6,6 +6,6 @@ foo
 # Num Counters:
 3
 # Counter Values:
-20
+21
 21
 0
diff --git a/test/Transforms/PGOProfile/branch1.ll b/test/Transforms/PGOProfile/branch1.ll
index 1a6d44b4a97..bbc7b722913 100644
--- a/test/Transforms/PGOProfile/branch1.ll
+++ b/test/Transforms/PGOProfile/branch1.ll
@@ -32,7 +32,7 @@ define i32 @test_br_1(i32 %i) {
 ; USE-SAME: !prof ![[FUNC_ENTRY_COUNT:[0-9]+]]
 entry:
 ; GEN: entry:
-; GEN-NOT: llvm.instrprof.increment
+; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @__profn_test_br_1, i32 0, i32 0), i64 25571299074, i32 2, i32 0)
   %cmp = icmp sgt i32 %i, 0
   br i1 %cmp, label %if.then, label %if.end
 ; USE: br i1 %cmp, label %if.then, label %if.end
@@ -50,7 +50,8 @@ if.then:
 
 if.end:
 ; GEN: if.end:
-; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @__profn_test_br_1, i32 0, i32 0), i64 25571299074, i32 2, i32 0)
+; GEN-NOT: llvm.instrprof.increment
+; GEN: ret i32
   %retv = phi i32 [ %add, %if.then ], [ %i, %entry ]
   ret i32 %retv
 }
diff --git a/test/Transforms/PGOProfile/counter_promo.ll b/test/Transforms/PGOProfile/counter_promo.ll
index 125e7d77cdf..812d0fefaa7 100644
--- a/test/Transforms/PGOProfile/counter_promo.ll
+++ b/test/Transforms/PGOProfile/counter_promo.ll
@@ -5,6 +5,9 @@
 
 define void @foo(i32 %n, i32 %N) {
 ; PROMO-LABEL: @foo
+; PROMO: {{.*}} = load {{.*}} @__profc_foo{{.*}} 3)
+; PROMO-NEXT: add 
+; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}3)
 bb:
   %tmp = add nsw i32 %n, 1
   %tmp1 = add nsw i32 %n, -1
@@ -57,9 +60,6 @@ bb12:                                             ; preds = %bb9
 ; ATOMIC_PROMO: atomicrmw add {{.*}} @__profc_foo{{.*}}0), i64 %[[LIVEOUT1]] seq_cst
 ; ATOMIC_PROMO-NEXT: atomicrmw add {{.*}} @__profc_foo{{.*}}1), i64 %[[LIVEOUT2]] seq_cst
 ; ATOMIC_PROMO-NEXT: atomicrmw add {{.*}} @__profc_foo{{.*}}2), i64 %[[LIVEOUT3]] seq_cst
-; PROMO: {{.*}} = load {{.*}} @__profc_foo{{.*}} 3)
-; PROMO-NEXT: add 
-; PROMO-NEXT: store {{.*}}@__profc_foo{{.*}}3)
 ; PROMO-NOT: @__profc_foo
 
 
diff --git a/test/Transforms/PGOProfile/infinite_loop_gen.ll b/test/Transforms/PGOProfile/infinite_loop_gen.ll
new file mode 100644
index 00000000000..4c5cb483a5d
--- /dev/null
+++ b/test/Transforms/PGOProfile/infinite_loop_gen.ll
@@ -0,0 +1,17 @@
+; RUN: opt < %s -pgo-instr-gen -S -o -   | FileCheck %s
+
+define void @foo() {
+entry:
+  br label %while.body
+  ; CHECK: llvm.instrprof.increment
+
+    while.body:                                       ; preds = %entry, %while.body
+    ; CHECK: llvm.instrprof.increment
+        call void (...) @bar() #2
+    br label %while.body
+}
+
+declare void @bar(...)
+
+attributes #0 = { nounwind }
+
diff --git a/test/Transforms/PGOProfile/landingpad.ll b/test/Transforms/PGOProfile/landingpad.ll
index 9452cd41b00..3a1a3eb57b0 100644
--- a/test/Transforms/PGOProfile/landingpad.ll
+++ b/test/Transforms/PGOProfile/landingpad.ll
@@ -16,7 +16,7 @@ target triple = "x86_64-unknown-linux-gnu"
 define i32 @bar(i32 %i) {
 entry:
 ; GEN: entry:
-; GEN-NOT: call void @llvm.instrprof.increment
+; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_bar, i32 0, i32 0), i64 24868915205, i32 2, i32 0)
   %rem = srem i32 %i, 3
   %tobool = icmp ne i32 %rem, 0
   br i1 %tobool, label %if.then, label %if.end
@@ -34,7 +34,8 @@ if.then:
 
 if.end:
 ; GEN: if.end:
-; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_bar, i32 0, i32 0), i64 24868915205, i32 2, i32 0)
+; GEN-NOT: call void @llvm.instrprof.increment
+; GEN: ret i32
   ret i32 0
 }
 
diff --git a/test/Transforms/PGOProfile/loop1.ll b/test/Transforms/PGOProfile/loop1.ll
index 5d3be183694..dbc728a49bb 100644
--- a/test/Transforms/PGOProfile/loop1.ll
+++ b/test/Transforms/PGOProfile/loop1.ll
@@ -13,7 +13,7 @@ target triple = "x86_64-unknown-linux-gnu"
 define i32 @test_simple_for(i32 %n) {
 entry:
 ; GEN: entry:
-; GEN-NOT: call void @llvm.instrprof.increment
+; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @__profn_test_simple_for, i32 0, i32 0), i64 34137660316, i32 2, i32 1)
   br label %for.cond
 
 for.cond:
@@ -41,6 +41,7 @@ for.inc:
 
 for.end:
 ; GEN: for.end:
-; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @__profn_test_simple_for, i32 0, i32 0), i64 34137660316, i32 2, i32 1)
+; GEN-NOT: call void @llvm.instrprof.increment
+; GEN: ret i32
   ret i32 %sum
 }
diff --git a/test/Transforms/PGOProfile/loop2.ll b/test/Transforms/PGOProfile/loop2.ll
index 1fad53a90dc..5a86f0299ad 100644
--- a/test/Transforms/PGOProfile/loop2.ll
+++ b/test/Transforms/PGOProfile/loop2.ll
@@ -13,7 +13,7 @@ target triple = "x86_64-unknown-linux-gnu"
 define i32 @test_nested_for(i32 %r, i32 %s) {
 entry:
 ; GEN: entry:
-; GEN-NOT: call void @llvm.instrprof.increment
+; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @__profn_test_nested_for, i32 0, i32 0), i64 53929068288, i32 3, i32 2)
   br label %for.cond.outer
 
 for.cond.outer:
@@ -65,7 +65,8 @@ for.inc.outer:
 
 for.end.outer:
 ; GEN: for.end.outer:
-; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @__profn_test_nested_for, i32 0, i32 0), i64 53929068288, i32 3, i32 2)
+; GEN-NOT: call void @llvm.instrprof.increment
+; GEN: ret i32
   ret i32 %sum.0
 }
 
diff --git a/test/Transforms/PGOProfile/noreturncall.ll b/test/Transforms/PGOProfile/noreturncall.ll
index 5f4b531e833..c108a82abf0 100644
--- a/test/Transforms/PGOProfile/noreturncall.ll
+++ b/test/Transforms/PGOProfile/noreturncall.ll
@@ -42,4 +42,4 @@ if.end7:
   ret i32 %mul
 }
 ; USE: ![[BW_ENTRY]] = !{!"branch_weights", i32 21, i32 0}
-; USE: ![[BW_IF]] = !{!"branch_weights", i32 0, i32 20}
+; USE: ![[BW_IF]] = !{!"branch_weights", i32 0, i32 21}