Switch lowering: extract jump tables and bit tests before building binary tree (PR22262)

This is a major rewrite of the SelectionDAG switch lowering. The previous code
would lower switches as a binary tre, discovering clusters of cases
suitable for lowering by jump tables or bit tests as it went along. To increase
the likelihood of finding jump tables, the binary tree pivot was selected to
maximize case density on both sides of the pivot.

By not selecting the pivot in the middle, the binary trees would not always
be balanced, leading to performance problems in the generated code.

This patch rewrites the lowering to search for clusters of cases
suitable for jump tables or bit tests first, and then builds the binary
tree around those clusters. This way, the binary tree will always be balanced.

This has the added benefit of decoupling the different aspects of the lowering:
tree building and jump table or bit tests finding are now easier to tweak
separately.

For example, this will enable us to balance the tree based on profile info
in the future.

The algorithm for finding jump tables is O(n^2), whereas the previous algorithm
was O(n log n) for common cases, and quadratic only in the worst-case. This
doesn't seem to be major problem in practice, e.g. compiling a file consisting
of a 10k-case switch was only 30% slower, and such large switches should be rare
in practice. Compiling e.g. gcc.c showed no compile-time difference.  If this
does turn out to be a problem, we could limit the search space of the algorithm.

This commit also disables all optimizations during switch lowering in -O0.

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

llvm-svn: 235101

1 files changed, 11 insertions, 88 deletions

diff --git a/llvm/test/MC/ARM/data-in-code.ll b/llvm/test/MC/ARM/data-in-code.ll
index 724577bb0da..c4910ff20e6 100644
--- a/llvm/test/MC/ARM/data-in-code.ll
+++ b/llvm/test/MC/ARM/data-in-code.ll
@@ -1,8 +1,8 @@
-;; RUN: llc -O0 -verify-machineinstrs -fast-isel-abort=1 \
+;; RUN: llc -verify-machineinstrs \
 ;; RUN:   -mtriple=armv7-linux-gnueabi -filetype=obj %s -o - | \
 ;; RUN:   llvm-readobj -t | FileCheck -check-prefix=ARM %s
 
-;; RUN: llc -O0 -verify-machineinstrs -fast-isel-abort=1 \
+;; RUN: llc -verify-machineinstrs \
 ;; RUN:   -mtriple=thumbv7-linux-gnueabi -filetype=obj %s -o - | \
 ;; RUN:   llvm-readobj -t | FileCheck -check-prefix=TMB %s
 
@@ -11,102 +11,25 @@
 
 define void @foo(i32* %ptr) nounwind ssp {
   %tmp = load i32, i32* %ptr, align 4
-  switch i32 %tmp, label %default [
-    i32 11, label %bb0
-    i32 10, label %bb1
-    i32 8, label %bb2
-    i32 4, label %bb3
-    i32 2, label %bb4
-    i32 6, label %bb5
-    i32 9, label %bb6
-    i32 15, label %bb7
-    i32 1, label %bb8
-    i32 3, label %bb9
-    i32 5, label %bb10
-    i32 30, label %bb11
-    i32 31, label %bb12
-    i32 13, label %bb13
-    i32 14, label %bb14
-    i32 20, label %bb15
-    i32 19, label %bb16
-    i32 17, label %bb17
-    i32 18, label %bb18
-    i32 21, label %bb19
-    i32 22, label %bb20
-    i32 16, label %bb21
-    i32 24, label %bb22
-    i32 25, label %bb23
-    i32 26, label %bb24
-    i32 27, label %bb25
-    i32 28, label %bb26
-    i32 23, label %bb27
-    i32 12, label %bb28
+  switch i32 %tmp, label %exit [
+    i32 0, label %bb0
+    i32 1, label %bb1
+    i32 2, label %bb2
+    i32 3, label %bb3
   ]
-
-default:
-  br label %exit
 bb0:
+  store i32 0, i32* %ptr, align 4
   br label %exit
 bb1:
+  store i32 1, i32* %ptr, align 4
   br label %exit
 bb2:
+  store i32 2, i32* %ptr, align 4
   br label %exit
 bb3:
+  store i32 3, i32* %ptr, align 4
   br label %exit
-bb4:
-  br label %exit
-bb5:
-  br label %exit
-bb6:
-  br label %exit
-bb7:
-  br label %exit
-bb8:
-  br label %exit
-bb9:
-  br label %exit
-bb10:
-  br label %exit
-bb11:
-  br label %exit
-bb12:
-  br label %exit
-bb13:
-  br label %exit
-bb14:
-  br label %exit
-bb15:
-  br label %exit
-bb16:
-  br label %exit
-bb17:
-  br label %exit
-bb18:
-  br label %exit
-bb19:
-  br label %exit
-bb20:
-  br label %exit
-bb21:
-  br label %exit
-bb22:
-  br label %exit
-bb23:
-  br label %exit
-bb24:
-  br label %exit
-bb25:
-  br label %exit
-bb26:
-  br label %exit
-bb27:
-  br label %exit
-bb28:
-  br label %exit
-
-
 exit:
-
   ret void
 }