[Profile] Enhance expect lowering to handle correlated branches

builtin_expect applied on && or || expressions were not
handled properly before. With this patch, the problem is fixed.

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


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

3 files changed, 515 insertions, 0 deletions

diff --git a/test/Transforms/LowerExpectIntrinsic/phi_merge.ll b/test/Transforms/LowerExpectIntrinsic/phi_merge.ll
new file mode 100644
index 00000000000..3b407c0f3a5
--- /dev/null
+++ b/test/Transforms/LowerExpectIntrinsic/phi_merge.ll
@@ -0,0 +1,356 @@
+; RUN: opt -lower-expect  -S -o - < %s | FileCheck %s
+; RUN: opt -S -passes='function(lower-expect)' < %s | FileCheck %s
+
+; The C case
+; if (__builtin_expect((x > goo() && y > hoo() && z > too()), 1)) 
+; For the above case, all 3 branches should be annotated.
+;
+; if (__builtin_expect((x > goo() && y > hoo() && z > too()), 0)) 
+; For the above case, we don't have enough information, so
+; only the last branch is annotated.
+
+define void @foo(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
+; CHECK-LABEL: void @foo
+bb:
+  %tmp8 = call i32  @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: !prof [[WEIGHT:![0-9]+]]
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13, {{.*}}!prof [[WEIGHT]]
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i32  @too()
+  %tmp17 = icmp sgt i32 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i1 [ false, %bb10 ], [ false, %bb ], [ %tmp17, %bb14 ]
+  %tmp20 = xor i1 %tmp19, true
+  %tmp21 = xor i1 %tmp20, true
+  %tmp22 = zext i1 %tmp21 to i32
+  %tmp23 = sext i32 %tmp22 to i64
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 1)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32  @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32  @hoo()
+  br label %bb30
+
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+define void @foo2(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
+; CHECK-LABEL: void @foo2
+bb:
+  %tmp8 = call i32  @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK:  br i1 %tmp9
+; CHECK-NOT: !prof
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13
+; CHECK-NOT: !prof
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i32 @too()
+  %tmp17 = icmp sgt i32 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i1 [ false, %bb10 ], [ false, %bb ], [ %tmp17, %bb14 ]
+  %tmp20 = xor i1 %tmp19, true
+  %tmp21 = xor i1 %tmp20, true
+  %tmp22 = zext i1 %tmp21 to i32
+  %tmp23 = sext i32 %tmp22 to i64
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 0)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT2:![0-9]+]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32 @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32 @hoo()
+  br label %bb30
+
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+define void @foo_i32(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
+; CHECK-LABEL: void @foo_i32
+bb:
+  %tmp8 = call i32  @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: !prof [[WEIGHT]]
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32 @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13, {{.*}}!prof [[WEIGHT]]
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i32 @too()
+  %tmp17 = icmp sgt i32 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i32 [ 5, %bb10 ], [ 5, %bb ], [ %tmp16, %bb14 ]
+  %tmp23 = sext i32 %tmp19 to i64
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 4)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32 @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32 @hoo()
+  br label %bb30
+
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+
+define void @foo_i32_not_unlikely(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo_i32_not_unlikely
+bb:
+  %tmp8 = call i32 @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: br i1 %tmp9
+; CHECK-NOT: !prof
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32 @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13
+; CHECK-NOT: !prof
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i32  @too()
+  %tmp17 = icmp sgt i32 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i32 [ 4, %bb10 ], [ 4, %bb ], [ %tmp16, %bb14 ]
+  %tmp23 = sext i32 %tmp19 to i64
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 4)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32  @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32 @hoo()
+  br label %bb30
+
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+define void @foo_i32_xor(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo_i32_xor
+bb:
+  %tmp8 = call i32  @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: br i1 %tmp9,{{.*}}!prof [[WEIGHT]]
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13,{{.*}}!prof [[WEIGHT]]
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i32  @too()
+  %tmp17 = icmp sgt i32 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i32 [ 6, %bb10 ], [ 6, %bb ], [ %tmp16, %bb14 ]
+  %tmp20 = xor i32 %tmp19, 3
+  %tmp23 = sext i32 %tmp20 to i64
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 4)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32 @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32 @hoo()
+  br label %bb30
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+define void @foo_i8_sext(i32 %arg, i32 %arg1, i8 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo_i8_sext
+bb:
+  %tmp8 = call i32  @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: br i1 %tmp9,{{.*}}!prof [[WEIGHT]]
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13,{{.*}}!prof [[WEIGHT]]
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i8  @too8()
+  %tmp17 = icmp sgt i8 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i8 [ 255, %bb10 ], [ 255, %bb ], [ %tmp16, %bb14 ]
+  %tmp23 = sext i8 %tmp19 to i64
+; after sign extension, the operand value becomes -1 which does not match 255
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 255)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32 @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32 @hoo()
+  br label %bb30
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+define void @foo_i8_sext_not_unlikely(i32 %arg, i32 %arg1, i8 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo_i8_sext_not_unlikely
+bb:
+  %tmp8 = call i32  @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: br i1 %tmp9
+; CHECK-NOT: !prof
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13
+; CHECK-NOT: !prof
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i8  @too8()
+  %tmp17 = icmp sgt i8 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i8 [ 255, %bb10 ], [ 255, %bb ], [ %tmp16, %bb14 ]
+  %tmp23 = sext i8 %tmp19 to i64
+; after sign extension, the operand value becomes -1 which matches -1
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 -1)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32 @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32 @hoo()
+  br label %bb30
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+
+define void @foo_i32_xor_not_unlikely(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo_i32_xor_not_unlikely
+bb:
+  %tmp8 = call i32 @goo() 
+  %tmp9 = icmp sgt i32 %tmp8, %arg
+  br i1 %tmp9, label %bb10, label %bb18
+; CHECK: br i1 %tmp9
+; CHECK-NOT: !prof
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br i1 %tmp13, label %bb14, label %bb18
+; CHECK: br i1 %tmp13
+; CHECK-NOT: !prof
+
+bb14:                                             ; preds = %bb10
+  %tmp16 = call i32 @too()
+  %tmp17 = icmp sgt i32 %arg2, %tmp16
+  br label %bb18
+
+bb18:                                             ; preds = %bb14, %bb10, %bb
+  %tmp19 = phi i32 [ 6, %bb10 ], [ 6, %bb ], [ %tmp16, %bb14 ]
+  %tmp20 = xor i32 %tmp19, 2
+  %tmp23 = sext i32 %tmp20 to i64
+  %tmp24 = call i64 @llvm.expect.i64(i64 %tmp23, i64 4)
+  %tmp25 = icmp ne i64 %tmp24, 0
+  br i1 %tmp25, label %bb26, label %bb28
+; CHECK: br i1 %tmp25,{{.*}}!prof [[WEIGHT]]
+
+bb26:                                             ; preds = %bb18
+  %tmp27 = call i32 @goo()
+  br label %bb30
+
+bb28:                                             ; preds = %bb18
+  %tmp29 = call i32  @hoo()
+  br label %bb30
+
+bb30:                                             ; preds = %bb28, %bb26
+  ret void
+}
+
+declare i32 @goo()
+
+declare i32 @hoo()
+
+declare i32 @too()
+
+declare i8 @too8()
+
+; Function Attrs: nounwind readnone
+declare i64 @llvm.expect.i64(i64, i64) 
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 5.0.0 (trunk 302965)"}
+; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1}
+; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000}
diff --git a/test/Transforms/LowerExpectIntrinsic/phi_or.ll b/test/Transforms/LowerExpectIntrinsic/phi_or.ll
new file mode 100644
index 00000000000..849baef3dca
--- /dev/null
+++ b/test/Transforms/LowerExpectIntrinsic/phi_or.ll
@@ -0,0 +1,103 @@
+; RUN: opt -lower-expect  -S -o - < %s | FileCheck %s
+; RUN: opt -S -passes='function(lower-expect)' < %s | FileCheck %s
+; 
+; if (__builtin_expect((x > goo() || y > hoo()), 1)) {
+;  ..
+; }
+; For the above case, only the second branch should be
+; annotated.
+; if (__builtin_expect((x > goo() || y > hoo()), 0)) {
+;  ..
+; }
+; For the above case, two branches should be annotated.
+; Function Attrs: noinline nounwind uwtable
+define void @foo(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo
+bb:
+  %tmp8 = call i32 @goo()
+  %tmp9 = icmp slt i32 %arg, %tmp8
+  br i1 %tmp9, label %bb14, label %bb10
+; CHECK: br i1 %tmp9
+; CHECK-NOT: br i1 %tmp9{{.*}}!prof
+
+bb10:                                             ; preds = %bb
+  %tmp12 = call i32  @hoo()
+  %tmp13 = icmp sgt i32 %arg1, %tmp12
+  br label %bb14
+
+bb14:                                             ; preds = %bb10, %bb
+  %tmp15 = phi i1 [ true, %bb ], [ %tmp13, %bb10 ]
+  %tmp16 = zext i1 %tmp15 to i32
+  %tmp17 = sext i32 %tmp16 to i64
+  %expect = call i64 @llvm.expect.i64(i64 %tmp17, i64 1)
+  %tmp18 = icmp ne i64 %expect, 0
+  br i1 %tmp18, label %bb19, label %bb21
+; CHECK: br i1 %tmp18{{.*}}!prof [[WEIGHT:![0-9]+]]
+
+bb19:                                             ; preds = %bb14
+  %tmp20 = call i32 @goo()
+  br label %bb23
+
+bb21:                                             ; preds = %bb14
+  %tmp22 = call i32  @hoo()
+  br label %bb23
+
+bb23:                                             ; preds = %bb21, %bb19
+  ret void
+}
+
+define void @foo2(i32 %arg, i32 %arg1, i32 %arg2, i32 %arg3)  {
+; CHECK-LABEL: void @foo2
+bb:
+  %tmp = alloca i32, align 4
+  %tmp4 = alloca i32, align 4
+  %tmp5 = alloca i32, align 4
+  %tmp6 = alloca i32, align 4
+  store i32 %arg, i32* %tmp, align 4
+  store i32 %arg1, i32* %tmp4, align 4
+  store i32 %arg2, i32* %tmp5, align 4
+  store i32 %arg3, i32* %tmp6, align 4
+  %tmp7 = load i32, i32* %tmp, align 4
+  %tmp8 = call i32  @goo()
+  %tmp9 = icmp slt i32 %tmp7, %tmp8
+  br i1 %tmp9, label %bb14, label %bb10
+; CHECK: br i1 %tmp9{{.*}}!prof [[WEIGHT2:![0-9]+]]
+
+bb10:                                             ; preds = %bb
+  %tmp11 = load i32, i32* %tmp5, align 4
+  %tmp12 = call i32 @hoo()
+  %tmp13 = icmp sgt i32 %tmp11, %tmp12
+  br label %bb14
+
+bb14:                                             ; preds = %bb10, %bb
+  %tmp15 = phi i1 [ true, %bb ], [ %tmp13, %bb10 ]
+  %tmp16 = zext i1 %tmp15 to i32
+  %tmp17 = sext i32 %tmp16 to i64
+  %expect = call i64 @llvm.expect.i64(i64 %tmp17, i64 0)
+  %tmp18 = icmp ne i64 %expect, 0
+  br i1 %tmp18, label %bb19, label %bb21
+; CHECK: br i1 %tmp18{{.*}}!prof [[WEIGHT2]]
+
+bb19:                                             ; preds = %bb14
+  %tmp20 = call i32 @goo()
+  br label %bb23
+
+bb21:                                             ; preds = %bb14
+  %tmp22 = call i32 @hoo()
+  br label %bb23
+
+bb23:                                             ; preds = %bb21, %bb19
+  ret void
+}
+
+declare i32 @goo() 
+declare i32 @hoo() 
+declare i64 @llvm.expect.i64(i64, i64) 
+
+
+!llvm.ident = !{!0}
+
+
+!0 = !{!"clang version 5.0.0 (trunk 302965)"}
+; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1}
+; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000}
diff --git a/test/Transforms/LowerExpectIntrinsic/phi_tern.ll b/test/Transforms/LowerExpectIntrinsic/phi_tern.ll
new file mode 100644
index 00000000000..3c603d51b43
--- /dev/null
+++ b/test/Transforms/LowerExpectIntrinsic/phi_tern.ll
@@ -0,0 +1,56 @@
+; RUN: opt -lower-expect  -S -o - < %s | FileCheck %s
+; RUN: opt -S -passes='function(lower-expect)' < %s | FileCheck %s
+
+; return __builtin_expect((a > b ? 1, goo(), 0);
+;  
+; Function Attrs: noinline nounwind uwtable
+define i32 @foo(i32 %arg, i32 %arg1)  {
+; CHECK-LABEL: i32 @foo
+bb:
+  %tmp5 = icmp sgt i32 %arg, %arg1
+  br i1 %tmp5, label %bb9, label %bb7
+; CHECK: br i1 %tmp5{{.*}}!prof [[WEIGHT:![0-9]+]]
+
+bb7:                                              ; preds = %bb
+  %tmp8 = call i32 @goo()
+  br label %bb9
+
+bb9:                                              ; preds = %bb7, %bb9
+  %tmp10 = phi i32 [ 1, %bb ], [ %tmp8, %bb7 ]
+  %tmp11 = sext i32 %tmp10 to i64
+  %expect = call i64 @llvm.expect.i64(i64 %tmp11, i64 0)
+  %tmp12 = trunc i64 %expect to i32
+  ret i32 %tmp12
+}
+
+define i32 @foo2(i32 %arg, i32 %arg1)  {
+bb:
+  %tmp5 = icmp sgt i32 %arg, %arg1
+  br i1 %tmp5, label %bb6, label %bb7
+; CHECK: br i1 %tmp5{{.*}}!prof [[WEIGHT:![0-9]+]]
+
+bb6:                                              ; preds = %bb
+  br label %bb9
+
+bb7:                                              ; preds = %bb
+  %tmp8 = call i32 @goo()
+  br label %bb9
+
+bb9:                                              ; preds = %bb7, %bb6
+  %tmp10 = phi i32 [ 1, %bb6 ], [ %tmp8, %bb7 ]
+  %tmp11 = sext i32 %tmp10 to i64
+  %expect = call i64 @llvm.expect.i64(i64 %tmp11, i64 0)
+  %tmp12 = trunc i64 %expect to i32
+  ret i32 %tmp12
+}
+
+declare i32 @goo() 
+declare i64 @llvm.expect.i64(i64, i64) 
+
+
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 5.0.0 (trunk 302965)"}
+
+; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 1, i32 2000}