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. 16define internal i32 @testJumpTable(i32 %a) { 17entry: 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 28sw.default: 29 %add = add i32 %a, 27 30 br label %sw.epilog 31 32sw.bb1: 33 %tmp = add i32 %a, 16 34 br label %sw.epilog 35 36sw.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. 80define internal i32 @testRangeTest() { 81entry: 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 93sw.default: 94 br label %sw.epilog 95 96sw.bb1: 97 br label %sw.epilog 98 99sw.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. 141define internal i32 @testBinarySearch() { 142entry: 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 150sw.default: 151 br label %sw.epilog 152 153sw.bb1: 154 br label %sw.epilog 155 156sw.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. 192define internal i32 @testSwitchSmall64(i64 %a) { 193entry: 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 201sw.bb1: 202 br label %return 203 204sw.bb2: 205 br label %return 206 207sw.bb3: 208 br label %return 209 210sw.default: 211 br label %return 212 213return: 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 241define internal i32 @testSwitch64(i64 %a) { 242entry: 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 250sw.bb1: 251 br label %return 252 253sw.bb2: 254 br label %return 255 256sw.bb3: 257 br label %return 258 259sw.default: 260 br label %return 261 262return: 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. 293define internal i32 @testJumpTable64(i64 %a) { 294entry: 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 302sw.bb1: 303 br label %return 304 305sw.bb2: 306 br label %return 307 308sw.bb3: 309 br label %return 310 311sw.default: 312 br label %return 313 314return: 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