1 ; This tests the advanced lowering of switch statements. The advanced lowering 2 ; uses jump tables, range tests and binary search. 3 4 ; RUN: %p2i -i %s --target=x8632 --filetype=obj --disassemble --args -O2 \ 5 ; RUN: | FileCheck %s --check-prefix=CHECK --check-prefix=X8632 6 ; RUN: %p2i -i %s --target=x8664 --filetype=obj --disassemble --args -O2 \ 7 ; RUN: | FileCheck %s --check-prefix=CHECK --check-prefix=X8664 8 9 ; RUN: %if --need=target_MIPS32 --need=allow_dump \ 10 ; RUN: --command %p2i --filetype=asm --assemble --disassemble --target \ 11 ; RUN: mips32 -i %s --args -O2 -allow-externally-defined-symbols \ 12 ; RUN: | %if --need=target_MIPS32 --need=allow_dump \ 13 ; RUN: --command FileCheck --check-prefix MIPS32 %s 14 15 ; Dense but non-continuous ranges should be converted into a jump table. 16 define internal i32 @testJumpTable(i32 %a) { 17 entry: 18 switch i32 %a, label %sw.default [ 19 i32 91, label %sw.default 20 i32 92, label %sw.bb1 21 i32 93, label %sw.default 22 i32 99, label %sw.bb1 23 i32 98, label %sw.default 24 i32 96, label %sw.bb1 25 i32 97, label %sw.epilog 26 ] 27 28 sw.default: 29 %add = add i32 %a, 27 30 br label %sw.epilog 31 32 sw.bb1: 33 %tmp = add i32 %a, 16 34 br label %sw.epilog 35 36 sw.epilog: 37 %result.1 = phi i32 [ %add, %sw.default ], [ %tmp, %sw.bb1 ], [ 17, %entry ] 38 ret i32 %result.1 39 } 40 ; CHECK-LABEL: testJumpTable 41 ; CHECK: sub [[IND:[^,]+]],0x5b 42 ; CHECK-NEXT: cmp [[IND]],0x8 43 ; CHECK-NEXT: ja 44 ; X8632-NEXT: mov [[TARGET:.*]],DWORD PTR {{\[}}[[IND]]*4+0x0] {{[0-9a-f]+}}: R_386_32 .{{.*}}testJumpTable$jumptable 45 ; X8632-NEXT: jmp [[TARGET]] 46 ; X8664-NEXT: mov {{.}}[[TARGET:.*]],DWORD PTR {{\[}}[[IND]]*4+0x0] {{[0-9a-f]+}}: R_X86_64_32S .{{.*}}testJumpTable$jumptable 47 ; X8664-NEXT: jmp {{.}}[[TARGET]] 48 ; Note: x86-32 may do "mov eax, [...]; jmp eax", whereas x86-64 may do 49 ; "mov eax, [...]; jmp rax", so we assume the all characters except the first 50 ; one in the register name will match. 51 52 ; MIPS32-LABEL: testJumpTable 53 ; MIPS32: move [[REG1:.*]],{{.*}} 54 ; MIPS32: li [[REG2:.*]],91 55 ; MIPS32: beq [[REG1]],[[REG2]],6c <.LtestJumpTable$sw.default> 56 ; MIPS32: nop 57 ; MIPS32: li [[REG2:.*]],92 58 ; MIPS32: beq [[REG1]],[[REG2]],78 <.LtestJumpTable$sw.bb1> 59 ; MIPS32: nop 60 ; MIPS32: li [[REG2:.*]],93 61 ; MIPS32: beq [[REG1]],[[REG2]],6c <.LtestJumpTable$sw.default> 62 ; MIPS32: nop 63 ; MIPS32: li [[REG2:.*]],99 64 ; MIPS32: beq [[REG1]],[[REG2]],78 <.LtestJumpTable$sw.bb1> 65 ; MIPS32: nop 66 ; MIPS32: li [[REG2:.*]],98 67 ; MIPS32: beq [[REG1]],[[REG2]],6c <.LtestJumpTable$sw.default> 68 ; MIPS32: nop 69 ; MIPS32: li [[REG2:.*]],96 70 ; MIPS32: beq [[REG1]],[[REG2]],78 <.LtestJumpTable$sw.bb1> 71 ; MIPS32: nop 72 ; MIPS32: li [[REG2:.*]],97 73 ; MIPS32: beq [[REG1]],[[REG2]],60 <.LtestJumpTable$split_entry_sw.epilog_0> 74 ; MIPS32: nop 75 ; MIPS32: b 6c <.LtestJumpTable$sw.default> 76 ; MIPS32: nop 77 78 ; Continuous ranges which map to the same target should be grouped and 79 ; efficiently tested. 80 define internal i32 @testRangeTest() { 81 entry: 82 switch i32 10, label %sw.default [ 83 i32 0, label %sw.epilog 84 i32 1, label %sw.epilog 85 i32 2, label %sw.epilog 86 i32 3, label %sw.epilog 87 i32 10, label %sw.bb1 88 i32 11, label %sw.bb1 89 i32 12, label %sw.bb1 90 i32 13, label %sw.bb1 91 ] 92 93 sw.default: 94 br label %sw.epilog 95 96 sw.bb1: 97 br label %sw.epilog 98 99 sw.epilog: 100 %result.1 = phi i32 [ 23, %sw.default ], [ 42, %sw.bb1 ], [ 17, %entry ], [ 17, %entry ], [ 17, %entry ], [ 17, %entry ] 101 ret i32 %result.1 102 } 103 ; CHECK-LABEL: testRangeTest 104 ; CHECK: cmp {{.*}},0x3 105 ; CHECK-NEXT: jbe 106 ; CHECK: sub [[REG:[^,]*]],0xa 107 ; CHECK-NEXT: cmp [[REG]],0x3 108 ; CHECK-NEXT: jbe 109 ; CHECK-NEXT: jmp 110 111 ; MIPS32-LABEL: testRangeTest 112 ; MIPS32: li [[REG1:.*]],10 113 ; MIPS32: li [[REG2:.*]],0 114 ; MIPS32: beq [[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0> 115 ; MIPS32: nop 116 ; MIPS32: li [[REG2:.*]],1 117 ; MIPS32: beq [[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0> 118 ; MIPS32: nop 119 ; MIPS32: li [[REG2:.*]],2 120 ; MIPS32: beq [[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0> 121 ; MIPS32: nop 122 ; MIPS32: li [[REG2:.*]],3 123 ; MIPS32: beq [[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0> 124 ; MIPS32: nop 125 ; MIPS32: li [[REG2:.*]],10 126 ; MIPS32: beq [[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2> 127 ; MIPS32: nop 128 ; MIPS32: li [[REG2:.*]],11 129 ; MIPS32: beq [[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2> 130 ; MIPS32: nop 131 ; MIPS32: li [[REG2:.*]],12 132 ; MIPS32: beq [[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2> 133 ; MIPS32: nop 134 ; MIPS32: li [[REG2:.*]],13 135 ; MIPS32: beq [[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2> 136 ; MIPS32: nop 137 ; MIPS32: b 108 <.LtestRangeTest$split_sw.default_sw.epilog_1> 138 ; MIPS32: nop 139 140 ; Sparse cases should be searched with a binary search. 141 define internal i32 @testBinarySearch() { 142 entry: 143 switch i32 10, label %sw.default [ 144 i32 0, label %sw.epilog 145 i32 10, label %sw.epilog 146 i32 20, label %sw.bb1 147 i32 30, label %sw.bb1 148 ] 149 150 sw.default: 151 br label %sw.epilog 152 153 sw.bb1: 154 br label %sw.epilog 155 156 sw.epilog: 157 %result.1 = phi i32 [ 23, %sw.default ], [ 42, %sw.bb1 ], [ 17, %entry ], [ 17, %entry ] 158 ret i32 %result.1 159 } 160 ; CHECK-LABEL: testBinarySearch 161 ; CHECK: cmp {{.*}},0x14 162 ; CHECK-NEXT: jb 163 ; CHECK-NEXT: je 164 ; CHECK-NEXT: cmp {{.*}},0x1e 165 ; CHECK-NEXT: je 166 ; CHECK-NEXT: jmp 167 ; CHECK-NEXT: cmp {{.*}},0x0 168 ; CHECK-NEXT: je 169 ; CHECK-NEXT: cmp {{.*}},0xa 170 ; CHECK-NEXT: je 171 ; CHECK-NEXT: jmp 172 173 ; MIPS32-LABEL: testBinarySearch 174 ; MIPS32: li [[REG1:.*]],10 175 ; MIPS32: li [[REG2:.*]],0 176 ; MIPS32: beq [[REG1]],[[REG2]],174 <.LtestBinarySearch$split_entry_sw.epilog_0> 177 ; MIPS32: nop 178 ; MIPS32: li [[REG2:.*]],10 179 ; MIPS32: beq [[REG1]],[[REG2]],174 <.LtestBinarySearch$split_entry_sw.epilog_0> 180 ; MIPS32: nop 181 ; MIPS32: li [[REG2:.*]],20 182 ; MIPS32: beq [[REG1]],[[REG2]],15c <.LtestBinarySearch$split_sw.bb1_sw.epilog_2> 183 ; MIPS32: nop 184 ; MIPS32: li [[REG2:.*]],30 185 ; MIPS32: beq [[REG1]],[[REG2]],15c <.LtestBinarySearch$split_sw.bb1_sw.epilog_2> 186 ; MIPS32: nop 187 ; MIPS32: b 168 <.LtestBinarySearch$split_sw.default_sw.epilog_1> 188 ; MIPS32: nop 189 190 ; 64-bit switches where the cases are all 32-bit values should be reduced to a 191 ; 32-bit switch after checking the top byte is 0. 192 define internal i32 @testSwitchSmall64(i64 %a) { 193 entry: 194 switch i64 %a, label %sw.default [ 195 i64 123, label %return 196 i64 234, label %sw.bb1 197 i64 345, label %sw.bb2 198 i64 456, label %sw.bb3 199 ] 200 201 sw.bb1: 202 br label %return 203 204 sw.bb2: 205 br label %return 206 207 sw.bb3: 208 br label %return 209 210 sw.default: 211 br label %return 212 213 return: 214 %retval.0 = phi i32 [ 5, %sw.default ], [ 4, %sw.bb3 ], [ 3, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %entry ] 215 ret i32 %retval.0 216 } 217 ; CHECK-LABEL: testSwitchSmall64 218 ; X8632: cmp {{.*}},0x0 219 ; X8632-NEXT: jne 220 ; X8632-NEXT: cmp {{.*}},0x159 221 ; X8632-NEXT: jb 222 ; X8632-NEXT: je 223 ; X8632-NEXT: cmp {{.*}},0x1c8 224 ; X8632-NEXT: je 225 ; X8632-NEXT: jmp 226 ; X8632-NEXT: cmp {{.*}},0x7b 227 ; X8632-NEXT: je 228 ; X8632-NEXT: cmp {{.*}},0xea 229 ; X8632-NEXT: je 230 231 ; MIPS32-LABEL: testSwitchSmall64 232 ; MIPS32: li [[REG:.*]],0 233 ; MIPS32: bne {{.*}},[[REG]],198 <.LtestSwitchSmall64$local$__0> 234 ; MIPS32: nop 235 ; MIPS32: li [[REG:.*]],123 236 ; MIPS32: beq {{.*}},[[REG]],210 <.LtestSwitchSmall64$split_entry_return_0> 237 ; MIPS32: nop 238 239 ; Test for correct 64-bit lowering. 240 ; TODO(ascull): this should generate better code like the 32-bit version 241 define internal i32 @testSwitch64(i64 %a) { 242 entry: 243 switch i64 %a, label %sw.default [ 244 i64 123, label %return 245 i64 234, label %sw.bb1 246 i64 345, label %sw.bb2 247 i64 78187493520, label %sw.bb3 248 ] 249 250 sw.bb1: 251 br label %return 252 253 sw.bb2: 254 br label %return 255 256 sw.bb3: 257 br label %return 258 259 sw.default: 260 br label %return 261 262 return: 263 %retval.0 = phi i32 [ 5, %sw.default ], [ 4, %sw.bb3 ], [ 3, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %entry ] 264 ret i32 %retval.0 265 } 266 ; CHECK-LABEL: testSwitch64 267 ; X8632: cmp {{.*}},0x7b 268 ; X8632-NEXT: jne 269 ; X8632-NEXT: cmp {{.*}},0x0 270 ; X8632-NEXT: je 271 ; X8632: cmp {{.*}},0xea 272 ; X8632-NEXT: jne 273 ; X8632-NEXT: cmp {{.*}},0x0 274 ; X8632-NEXT: je 275 ; X8632: cmp {{.*}},0x159 276 ; X8632-NEXT: jne 277 ; X8632-NEXT: cmp {{.*}},0x0 278 ; X8632-NEXT: je 279 ; X8632: cmp {{.*}},0x34567890 280 ; X8632-NEXT: jne 281 ; X8632-NEXT: cmp {{.*}},0x12 282 ; X8632-NEXT: je 283 284 ; MIPS32-LABEL: testSwitch64 285 ; MIPS32: li [[REG:.*]],0 286 ; MIPS32: bne {{.*}},[[REG]],238 <.LtestSwitch64$local$__0> 287 ; MIPS32: nop 288 ; MIPS32: li [[REG:.*]],123 289 ; MIPS32: beq {{.*}},[[REG]],2b4 <.LtestSwitch64$split_entry_return_0> 290 ; MIPS32: nop 291 292 ; Test for correct 64-bit jump table with UINT64_MAX as one of the values. 293 define internal i32 @testJumpTable64(i64 %a) { 294 entry: 295 switch i64 %a, label %sw.default [ 296 i64 -6, label %return 297 i64 -4, label %sw.bb1 298 i64 -3, label %sw.bb2 299 i64 -1, label %sw.bb3 300 ] 301 302 sw.bb1: 303 br label %return 304 305 sw.bb2: 306 br label %return 307 308 sw.bb3: 309 br label %return 310 311 sw.default: 312 br label %return 313 314 return: 315 %retval.0 = phi i32 [ 5, %sw.default ], [ 4, %sw.bb3 ], [ 3, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %entry ] 316 ret i32 %retval.0 317 } 318 319 ; TODO(ascull): this should generate a jump table. For now, just make sure it 320 ; doesn't crash the compiler. 321 ; CHECK-LABEL: testJumpTable64 322
