[CodeGenPrep] Skip merging empty case blocks

Summary: Merging an empty case block into the header block of switch could cause
ISel to add COPY instructions in the header of switch, instead of the case
block, if the case block is used as an incoming block of a PHI. This could
potentially increase dynamic instructions, especially when the switch is in a
loop. I added a test case which was reduced from the benchmark I was targetting.

Reviewers: t.p.northover, mcrosier, manmanren, wmi, davidxl

Subscribers: qcolombet, danielcdh, hfinkel, mcrosier, llvm-commits

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

llvm-svn: 287553

5 files changed, 156 insertions, 11 deletions

diff --git a/llvm/test/CodeGen/X86/phi-immediate-factoring.ll b/llvm/test/CodeGen/X86/phi-immediate-factoring.ll
index 05a0bf68657..8405ca436fd 100644
--- a/llvm/test/CodeGen/X86/phi-immediate-factoring.ll
+++ b/llvm/test/CodeGen/X86/phi-immediate-factoring.ll
@@ -1,5 +1,6 @@
 ; REQUIRES: asserts
-; RUN: llc < %s -disable-preheader-prot=true  -march=x86 -stats 2>&1 | grep "Number of blocks eliminated" | grep 6
+; RUN: llc < %s -disable-preheader-prot=true  -march=x86 -stats 2>&1 | grep "Number of blocks eliminated" | grep 3
+; RUN: llc < %s -disable-preheader-prot=true  -march=x86 -stats -cgp-freq-ratio-to-skip-merge=10 2>&1 | grep "Number of blocks eliminated" | grep 6
 ; RUN: llc < %s -disable-preheader-prot=false -march=x86 -stats 2>&1 | grep "Number of blocks eliminated" | grep 3
 ; PR1296
 
diff --git a/llvm/test/CodeGen/X86/ragreedy-hoist-spill.ll b/llvm/test/CodeGen/X86/ragreedy-hoist-spill.ll
index 1d6b4f94731..0178c9ec1c9 100644
--- a/llvm/test/CodeGen/X86/ragreedy-hoist-spill.ll
+++ b/llvm/test/CodeGen/X86/ragreedy-hoist-spill.ll
@@ -177,14 +177,14 @@ for.cond357:
   br label %for.cond357
 
 sw.bb474:
+  ; CHECK: sw.bb474
+  ; spill is hoisted here. Although loop depth1 is even hotter than loop depth2, sw.bb474 is still cold.
+  ; CHECK: movq %r{{.*}}, {{[0-9]+}}(%rsp)
+  ; CHECK: land.rhs485
   %cmp476 = icmp eq i8 undef, 0
   br i1 %cmp476, label %if.end517, label %do.body479.preheader
 
 do.body479.preheader:
-  ; CHECK: do.body479.preheader
-  ; spill is hoisted here. Although loop depth1 is even hotter than loop depth2, do.body479.preheader is cold.
-  ; CHECK: movq %r{{.*}}, {{[0-9]+}}(%rsp)
-  ; CHECK: land.rhs485
   %cmp4833314 = icmp eq i8 undef, 0
   br i1 %cmp4833314, label %if.end517, label %land.rhs485
 
diff --git a/llvm/test/Transforms/CodeGenPrepare/AArch64/widen_switch.ll b/llvm/test/Transforms/CodeGenPrepare/AArch64/widen_switch.ll
index 172541a4608..cae1cc54a96 100644
--- a/llvm/test/Transforms/CodeGenPrepare/AArch64/widen_switch.ll
+++ b/llvm/test/Transforms/CodeGenPrepare/AArch64/widen_switch.ll
@@ -28,7 +28,7 @@ return:
 ; ARM64-LABEL: @widen_switch_i16(
 ; ARM64:       %0 = zext i16 %trunc to i32
 ; ARM64-NEXT:  switch i32 %0, label %sw.default [
-; ARM64-NEXT:    i32 1, label %return
+; ARM64-NEXT:    i32 1, label %sw.bb0
 ; ARM64-NEXT:    i32 65535, label %sw.bb1
 }
 
@@ -58,7 +58,7 @@ return:
 ; ARM64-LABEL: @widen_switch_i17(
 ; ARM64:       %0 = zext i17 %trunc to i32
 ; ARM64-NEXT:  switch i32 %0, label %sw.default [
-; ARM64-NEXT:    i32 10, label %return
+; ARM64-NEXT:    i32 10, label %sw.bb0
 ; ARM64-NEXT:    i32 131071, label %sw.bb1
 }
 
@@ -89,7 +89,7 @@ return:
 ; ARM64-LABEL: @widen_switch_i16_sext(
 ; ARM64:       %0 = sext i2 %a to i32
 ; ARM64-NEXT:  switch i32 %0, label %sw.default [
-; ARM64-NEXT:    i32 1, label %return
+; ARM64-NEXT:    i32 1, label %sw.bb0
 ; ARM64-NEXT:    i32 -1, label %sw.bb1
 }
 
diff --git a/llvm/test/Transforms/CodeGenPrepare/X86/widen_switch.ll b/llvm/test/Transforms/CodeGenPrepare/X86/widen_switch.ll
index 53c9cc07355..23f120f1a23 100644
--- a/llvm/test/Transforms/CodeGenPrepare/X86/widen_switch.ll
+++ b/llvm/test/Transforms/CodeGenPrepare/X86/widen_switch.ll
@@ -28,7 +28,7 @@ return:
 ; X86-LABEL: @widen_switch_i16(
 ; X86:       %trunc = trunc i32 %a to i16
 ; X86-NEXT:  switch i16 %trunc, label %sw.default [
-; X86-NEXT:    i16 1, label %return
+; X86-NEXT:    i16 1, label %sw.bb0
 ; X86-NEXT:    i16 -1, label %sw.bb1
 }
 
@@ -58,7 +58,7 @@ return:
 ; X86-LABEL: @widen_switch_i17(
 ; X86:       %0 = zext i17 %trunc to i32
 ; X86-NEXT:  switch i32 %0, label %sw.default [
-; X86-NEXT:    i32 10, label %return
+; X86-NEXT:    i32 10, label %sw.bb0
 ; X86-NEXT:    i32 131071, label %sw.bb1
 }
 
@@ -89,7 +89,7 @@ return:
 ; X86-LABEL: @widen_switch_i16_sext(
 ; X86:       %0 = sext i2 %a to i8
 ; X86-NEXT:  switch i8 %0, label %sw.default [
-; X86-NEXT:    i8 1, label %return
+; X86-NEXT:    i8 1, label %sw.bb0
 ; X86-NEXT:    i8 -1, label %sw.bb1
 }
 
diff --git a/llvm/test/Transforms/CodeGenPrepare/skip-merging-case-block.ll b/llvm/test/Transforms/CodeGenPrepare/skip-merging-case-block.ll
new file mode 100644
index 00000000000..3b14aed6eb0
--- /dev/null
+++ b/llvm/test/Transforms/CodeGenPrepare/skip-merging-case-block.ll
@@ -0,0 +1,144 @@
+; RUN: opt -codegenprepare  < %s  -mtriple=aarch64-none-linux-gnu -S  | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+; Expect to skip merging two empty blocks (sw.bb and sw.bb2) into sw.epilog
+; as both of them are unlikely executed.
+define i32 @f_switch(i32 %c)  {
+; CHECK-LABEL: @f_switch
+; CHECK-LABEL: entry:
+; CHECK: i32 10, label %sw.bb
+; CHECK: i32 20, label %sw.bb2
+entry:
+  switch i32 %c, label %sw.default [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb2
+    i32 30, label %sw.bb3
+    i32 40, label %sw.bb4
+  ], !prof !0
+
+sw.bb:                                            ; preds = %entry
+  br label %sw.epilog
+
+sw.bb2:                                           ; preds = %entry
+  br label %sw.epilog
+
+sw.bb3:                                           ; preds = %entry
+  call void bitcast (void (...)* @callcase3 to void ()*)()
+  br label %sw.epilog
+
+sw.bb4:                                           ; preds = %entry
+  call void bitcast (void (...)* @callcase4 to void ()*)()
+  br label %sw.epilog
+
+sw.default:                                       ; preds = %entry
+  call void bitcast (void (...)* @calldefault to void ()*)()
+  br label %sw.epilog
+
+; CHECK-LABEL: sw.epilog:
+; CHECK: %fp.0 = phi void (...)* [ @FD, %sw.default ], [ @F4, %sw.bb4 ], [ @F3, %sw.bb3 ], [ @F2, %sw.bb2 ], [ @F1, %sw.bb ]
+sw.epilog:                                        ; preds = %sw.default, %sw.bb3, %sw.bb2, %sw.bb
+  %fp.0 = phi void (...)* [ @FD, %sw.default ], [ @F4, %sw.bb4 ], [ @F3, %sw.bb3 ], [ @F2, %sw.bb2 ], [ @F1, %sw.bb ]
+  %callee.knr.cast = bitcast void (...)* %fp.0 to void ()*
+  call void %callee.knr.cast()
+  ret i32 0
+}
+
+; Expect not to merge sw.bb2 because of the conflict in the incoming value from
+; sw.bb which is already merged.
+define i32 @f_switch2(i32 %c)  {
+; CHECK-LABEL: @f_switch2
+; CHECK-LABEL: entry:
+; CHECK: i32 10, label %sw.epilog
+; CHECK: i32 20, label %sw.bb2
+entry:
+  switch i32 %c, label %sw.default [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb2
+    i32 30, label %sw.bb3
+    i32 40, label %sw.bb4
+  ], !prof !1
+
+sw.bb:                                            ; preds = %entry
+  br label %sw.epilog
+
+sw.bb2:                                           ; preds = %entry
+  br label %sw.epilog
+
+sw.bb3:                                           ; preds = %entry
+  call void bitcast (void (...)* @callcase3 to void ()*)()
+  br label %sw.epilog
+
+sw.bb4:                                           ; preds = %entry
+  call void bitcast (void (...)* @callcase4 to void ()*)()
+  br label %sw.epilog
+
+sw.default:                                       ; preds = %entry
+  call void bitcast (void (...)* @calldefault to void ()*)()
+  br label %sw.epilog
+
+; CHECK-LABEL: sw.epilog:
+; CHECK: %fp.0 = phi void (...)* [ @FD, %sw.default ], [ @F4, %sw.bb4 ], [ @F3, %sw.bb3 ], [ @F2, %sw.bb2 ], [ @F1, %entry ]
+sw.epilog:                                        ; preds = %sw.default, %sw.bb3, %sw.bb2, %sw.bb
+  %fp.0 = phi void (...)* [ @FD, %sw.default ], [ @F4, %sw.bb4 ], [ @F3, %sw.bb3 ], [ @F2, %sw.bb2 ], [ @F1, %sw.bb ]
+  %callee.knr.cast = bitcast void (...)* %fp.0 to void ()*
+  call void %callee.knr.cast()
+  ret i32 0
+}
+
+; Multiple empty blocks should be considered together if all incoming values
+; from them are same.  We expect to merge both empty blocks (sw.bb and sw.bb2)
+; because the sum of frequencies are higer than the threshold.
+define i32 @f_switch3(i32 %c)  {
+; CHECK-LABEL: @f_switch3
+; CHECK-LABEL: entry:
+; CHECK: i32 10, label %sw.epilog
+; CHECK: i32 20, label %sw.epilog
+entry:
+  switch i32 %c, label %sw.default [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb2
+    i32 30, label %sw.bb3
+    i32 40, label %sw.bb4
+  ], !prof !2
+
+sw.bb:                                            ; preds = %entry
+  br label %sw.epilog
+
+sw.bb2:                                           ; preds = %entry
+  br label %sw.epilog
+
+sw.bb3:                                           ; preds = %entry
+  call void bitcast (void (...)* @callcase3 to void ()*)()
+  br label %sw.epilog
+
+sw.bb4:                                           ; preds = %entry
+  call void bitcast (void (...)* @callcase4 to void ()*)()
+  br label %sw.epilog
+
+sw.default:                                       ; preds = %entry
+  call void bitcast (void (...)* @calldefault to void ()*)()
+  br label %sw.epilog
+
+; CHECK-LABEL: sw.epilog:
+; CHECK: %fp.0 = phi void (...)* [ @FD, %sw.default ], [ @F4, %sw.bb4 ], [ @F3, %sw.bb3 ], [ @F1, %entry ], [ @F1, %entry ]
+sw.epilog:                                        ; preds = %sw.default, %sw.bb3, %sw.bb2, %sw.bb
+  %fp.0 = phi void (...)* [ @FD, %sw.default ], [ @F4, %sw.bb4 ], [ @F3, %sw.bb3 ], [ @F1, %sw.bb2 ], [ @F1, %sw.bb ]
+  %callee.knr.cast = bitcast void (...)* %fp.0 to void ()*
+  call void %callee.knr.cast()
+  ret i32 0
+}
+
+declare void @F1(...) local_unnamed_addr
+declare void @F2(...) local_unnamed_addr
+declare void @F3(...) local_unnamed_addr
+declare void @F4(...) local_unnamed_addr
+declare void @FD(...) local_unnamed_addr
+declare void @callcase3(...) local_unnamed_addr
+declare void @callcase4(...) local_unnamed_addr
+declare void @calldefault(...) local_unnamed_addr
+
+!0 = !{!"branch_weights", i32 5, i32 1, i32 1,i32 5, i32 5}
+!1 = !{!"branch_weights", i32 1 , i32 5, i32 1,i32 1, i32 1}
+!2 = !{!"branch_weights", i32 1 , i32 4, i32 1,i32 1, i32 1}