Next stage into switch lowering refactoring

1. Fix some bugs in the jump table lowering threshold
2. Implement much better metric for optimal pivot selection
3. Tune thresholds for different lowering methods
4. Implement shift-and trick for lowering small (<machine word
length) cases with few destinations. Good testcase will follow.


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

2 files changed, 40 insertions, 18 deletions

diff --git a/test/CodeGen/Generic/2007-02-16-BranchFold.ll b/test/CodeGen/Generic/2007-02-16-BranchFold.ll
index 5f3162ea116..c3222d2a918 100644
--- a/test/CodeGen/Generic/2007-02-16-BranchFold.ll
+++ b/test/CodeGen/Generic/2007-02-16-BranchFold.ll
@@ -2,7 +2,7 @@
 ; RUN: llvm-as < %s | llc | grep jmp | wc -l | grep 0
 ; PR 1200
 
-; ModuleID = 'bugpoint.test.bc'
+; ModuleID = '<stdin>'
 target datalayout = "e-p:32:32"
 target triple = "i686-apple-darwin8"
 	%struct.FILE = type { i8*, i32, i32, i16, i16, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, %struct.__sFILEX*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 }
@@ -25,30 +25,32 @@ target triple = "i686-apple-darwin8"
 @outfile = external global %struct.FILE*		; <%struct.FILE**> [#uses=1]
 @str1 = external global [11 x i8]		; <[11 x i8]*> [#uses=1]
 
-
 declare i32 @fprintf(%struct.FILE*, i8*, ...)
 
 define i16 @main_bb_2E_i9_2E_i_2E_i932_2E_ce(%struct.list* %l_addr.01.0.i2.i.i929, %struct.operator** %tmp66.i62.i.out) {
 newFuncRoot:
 	br label %bb.i9.i.i932.ce
 
-bb36.i.i.exitStub:		; preds = %bb.i9.i.i932.ce
+NewDefault:		; preds = %LeafBlock, %LeafBlock1, %LeafBlock2, %LeafBlock3
+	br label %bb36.i.i.exitStub
+
+bb36.i.i.exitStub:		; preds = %NewDefault
 	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
 	ret i16 0
 
-bb.i14.i.exitStub:		; preds = %bb.i9.i.i932.ce
+bb.i14.i.exitStub:		; preds = %LeafBlock
 	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
 	ret i16 1
 
-bb12.i.i935.exitStub:		; preds = %bb.i9.i.i932.ce
+bb12.i.i935.exitStub:		; preds = %LeafBlock1
 	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
 	ret i16 2
 
-bb20.i.i937.exitStub:		; preds = %bb.i9.i.i932.ce
+bb20.i.i937.exitStub:		; preds = %LeafBlock2
 	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
 	ret i16 3
 
-bb28.i.i938.exitStub:		; preds = %bb.i9.i.i932.ce
+bb28.i.i938.exitStub:		; preds = %LeafBlock3
 	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
 	ret i16 4
 
@@ -61,11 +63,34 @@ bb.i9.i.i932.ce:		; preds = %newFuncRoot
 	%tmp3.i8.i = load %struct.FILE** @outfile		; <%struct.FILE*> [#uses=1]
 	%tmp5.i9.i = call i32 (%struct.FILE*, i8*, ...)* @fprintf( %struct.FILE* %tmp3.i8.i, i8* getelementptr ([11 x i8]* @str1, i32 0, i32 0), i32 %tmp2.i7.i )		; <i32> [#uses=0]
 	%tmp7.i10.i = getelementptr %struct.operator* %tmp66.i62.i, i32 0, i32 5		; <i32*> [#uses=1]
-	%tmp8.i11.i = load i32* %tmp7.i10.i		; <i32> [#uses=1]
-	switch i32 %tmp8.i11.i, label %bb36.i.i.exitStub [
-		 i32 -1, label %bb.i14.i.exitStub
-		 i32 0, label %bb12.i.i935.exitStub
-		 i32 1, label %bb20.i.i937.exitStub
-		 i32 2, label %bb28.i.i938.exitStub
-	]
+	%tmp8.i11.i = load i32* %tmp7.i10.i		; <i32> [#uses=7]
+	br label %NodeBlock5
+
+NodeBlock5:		; preds = %bb.i9.i.i932.ce
+	icmp slt i32 %tmp8.i11.i, 1		; <i1>:0 [#uses=1]
+	br i1 %0, label %NodeBlock, label %NodeBlock4
+
+NodeBlock4:		; preds = %NodeBlock5
+	icmp slt i32 %tmp8.i11.i, 2		; <i1>:1 [#uses=1]
+	br i1 %1, label %LeafBlock2, label %LeafBlock3
+
+LeafBlock3:		; preds = %NodeBlock4
+	icmp eq i32 %tmp8.i11.i, 2		; <i1>:2 [#uses=1]
+	br i1 %2, label %bb28.i.i938.exitStub, label %NewDefault
+
+LeafBlock2:		; preds = %NodeBlock4
+	icmp eq i32 %tmp8.i11.i, 1		; <i1>:3 [#uses=1]
+	br i1 %3, label %bb20.i.i937.exitStub, label %NewDefault
+
+NodeBlock:		; preds = %NodeBlock5
+	icmp slt i32 %tmp8.i11.i, 0		; <i1>:4 [#uses=1]
+	br i1 %4, label %LeafBlock, label %LeafBlock1
+
+LeafBlock1:		; preds = %NodeBlock
+	icmp eq i32 %tmp8.i11.i, 0		; <i1>:5 [#uses=1]
+	br i1 %5, label %bb12.i.i935.exitStub, label %NewDefault
+
+LeafBlock:		; preds = %NodeBlock
+	icmp eq i32 %tmp8.i11.i, -1		; <i1>:6 [#uses=1]
+	br i1 %6, label %bb.i14.i.exitStub, label %NewDefault
 }
diff --git a/test/CodeGen/Generic/switch-lower-feature.ll b/test/CodeGen/Generic/switch-lower-feature.ll
index a1345cb8716..195d2167138 100644
--- a/test/CodeGen/Generic/switch-lower-feature.ll
+++ b/test/CodeGen/Generic/switch-lower-feature.ll
@@ -1,10 +1,7 @@
 ; RUN: llvm-as < %s | llc -march=x86 -o - | grep \$7 | wc -l | grep 1 &&
 ; RUN: llvm-as < %s | llc -march=x86 -o - | grep \$6 | wc -l | grep 1 &&
 ; RUN: llvm-as < %s | llc -march=x86 -o - | grep 1024 | wc -l | grep 1 &&
-; RUN: llvm-as < %s | llc -march=x86 -o - | grep 1023 | wc -l | grep 1 &&
-; RUN: llvm-as < %s | llc -march=x86 -o - | grep jg | wc -l | grep 1 &&
-; RUN: llvm-as < %s | llc -march=x86 -o - | grep jb | wc -l | grep 1 &&
-; RUN: llvm-as < %s | llc -march=x86 -o - | grep jae | wc -l | grep 1 &&
+; RUN: llvm-as < %s | llc -march=x86 -o - | grep jb | wc -l | grep 2 &&
 ; RUN: llvm-as < %s | llc -march=x86 -o - | grep je | wc -l | grep 1
 
 define i32 @main(i32 %tmp158) {