i32 3, label %bb0
i32 1, label %bb1
i32 4, label %bb1
- i32 5, label %bb0
+ i32 5, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 1) br label %return
return: ret void
; Should be lowered as straight compares in -O0 mode.
; NOOPT-LABEL: basic
-; NOOPT: subl $3, %eax
-; NOOPT: je
; NOOPT: subl $1, %eax
; NOOPT: je
+; NOOPT: subl $3, %eax
+; NOOPT: je
; NOOPT: subl $4, %eax
; NOOPT: je
; NOOPT: subl $5, %eax
; CHECK: jae
; CHECK: cmpl $3
; CHECK: ja
+
+; We do this even at -O0, because it's cheap and makes codegen faster.
+; NOOPT-LABEL: simple_ranges
+; NOOPT: subl $4
+; NOOPT: jb
+; NOOPT: addl $-100
+; NOOPT: subl $4
+; NOOPT: jb
}
; NOOPT-NEXT: retq
; NOOPT: jmp .[[L]]
}
+
+
+define void @int_max_table_cluster(i8 %x) {
+entry:
+ switch i8 %x, label %return [
+ i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0
+ i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0
+ i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0
+ i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0
+ i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0
+ i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0
+ i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0
+ i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0
+ i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0
+ i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0
+ i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0
+ i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0
+ i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0
+ i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0
+ i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0
+ i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0
+ i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0
+ i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0
+ i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0
+ i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0
+ i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0
+ i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0
+ i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0
+ i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0
+ i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0
+ i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0
+ i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0
+ i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0
+ i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0
+ i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0
+ i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0
+ i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0
+ i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1
+ i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1
+ i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1
+ i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1
+ i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1
+ i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1
+ i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1
+ i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1
+ i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2
+ i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2
+ i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2
+ i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2
+ i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3
+ i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3
+ ]
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 1) br label %return
+bb3: tail call void @g(i32 1) br label %return
+return: ret void
+
+; Don't infloop on jump tables where the upper bound is the max value of the
+; input type (in this case 127).
+; CHECK-LABEL: int_max_table_cluster
+; CHECK: jmpq *.LJTI
+}
+
+
+define void @bt_order_by_weight(i32 %x) {
+entry:
+ switch i32 %x, label %return [
+ i32 0, label %bb0
+ i32 3, label %bb0
+ i32 6, label %bb0
+ i32 1, label %bb1
+ i32 4, label %bb1
+ i32 7, label %bb1
+ i32 2, label %bb2
+ i32 5, label %bb2
+ i32 8, label %bb2
+ i32 9, label %bb2
+ ], !prof !1
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 2) br label %return
+return: ret void
+
+; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so
+; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 12,
+; but the latter set has more cases, so should be tested for earlier.
+
+; CHECK-LABEL: bt_order_by_weight
+; 146 = 2^1 + 2^4 + 2^7
+; CHECK: movl $146
+; CHECK: btl
+; 292 = 2^2 + 2^5 + 2^8 + 2^9
+; CHECK: movl $804
+; CHECK: btl
+; 73 = 2^0 + 2^3 + 2^6
+; CHECK: movl $73
+; CHECK: btl
+}
+
+!1 = !{!"branch_weights",
+ ; Default:
+ i32 1,
+ ; Cases 0,3,6:
+ i32 4, i32 4, i32 4,
+ ; Cases 1,4,7:
+ i32 4294967295, i32 2, i32 4294967295,
+ ; Cases 2,5,8,9:
+ i32 3, i32 3, i32 3, i32 3}
+
+define void @order_by_weight_and_fallthrough(i32 %x) {
+entry:
+ switch i32 %x, label %return [
+ i32 100, label %bb1
+ i32 200, label %bb0
+ i32 300, label %bb0
+ ], !prof !2
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+return: ret void
+
+; Case 200 has the highest weight and should come first. 100 and 300 have the
+; same weight, but 300 goes to the 'next' block, so should be last.
+; CHECK-LABEL: order_by_weight_and_fallthrough
+; CHECK: cmpl $200
+; CHECK: cmpl $100
+; CHECK: cmpl $300
+}
+
+!2 = !{!"branch_weights",
+ ; Default:
+ i32 1,
+ ; Case 100:
+ i32 10,
+ ; Case 200:
+ i32 1000,
+ ; Case 300:
+ i32 10}
+
+
+define void @zero_weight_tree(i32 %x) {
+entry:
+ switch i32 %x, label %return [
+ i32 0, label %bb0
+ i32 10, label %bb1
+ i32 20, label %bb2
+ i32 30, label %bb3
+ i32 40, label %bb4
+ i32 50, label %bb5
+ ], !prof !3
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 2) br label %return
+bb3: tail call void @g(i32 3) br label %return
+bb4: tail call void @g(i32 4) br label %return
+bb5: tail call void @g(i32 5) br label %return
+return: ret void
+
+; Make sure to pick a pivot in the middle also with zero-weight cases.
+; CHECK-LABEL: zero_weight_tree
+; CHECK-NOT: cmpl
+; CHECK: cmpl $29
+}
+
+!3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10}
+
+
+define void @left_leaning_weight_balanced_tree(i32 %x) {
+entry:
+ switch i32 %x, label %return [
+ i32 0, label %bb0
+ i32 10, label %bb1
+ i32 20, label %bb2
+ i32 30, label %bb3
+ i32 40, label %bb4
+ i32 50, label %bb5
+ ], !prof !4
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 2) br label %return
+bb3: tail call void @g(i32 3) br label %return
+bb4: tail call void @g(i32 4) br label %return
+bb5: tail call void @g(i32 5) br label %return
+return: ret void
+
+; To balance the tree by weight, the pivot is shifted to the right, moving hot
+; cases closer to the root.
+; CHECK-LABEL: left_leaning_weight_balanced_tree
+; CHECK-NOT: cmpl
+; CHECK: cmpl $39
+}
+
+!4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 10, i32 10}
+
+
+define void @jump_table_affects_balance(i32 %x) {
+entry:
+ switch i32 %x, label %return [
+ ; Jump table:
+ i32 0, label %bb0
+ i32 1, label %bb1
+ i32 2, label %bb2
+ i32 3, label %bb3
+
+ i32 100, label %bb0
+ i32 200, label %bb1
+ i32 300, label %bb2
+ ]
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+bb2: tail call void @g(i32 2) br label %return
+bb3: tail call void @g(i32 3) br label %return
+return: ret void
+
+; CHECK-LABEL: jump_table_affects_balance
+; If the tree were balanced based on number of clusters, {0-3,100} would go on
+; the left and {200,300} on the right. However, the jump table weights as much
+; as its components, so 100 is selected as the pivot.
+; CHECK-NOT: cmpl
+; CHECK: cmpl $99
+}
+
+
+define void @pr23738(i4 %x) {
+entry:
+ switch i4 %x, label %bb0 [
+ i4 0, label %bb1
+ i4 1, label %bb1
+ i4 -5, label %bb1
+ ]
+bb0: tail call void @g(i32 0) br label %return
+bb1: tail call void @g(i32 1) br label %return
+return: ret void
+; Don't assert due to truncating the bitwidth (64) to i4 when checking
+; that the bit-test range fits in a word.
+}
projects / oota-llvm.git / blobdiff