1; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py 2; RUN: llc -mtriple=x86_64-- < %s -jump-table-density=40 -switch-peel-threshold=101 | FileCheck %s 3 4; This switch should use bit tests, and the third bit test case is just 5; testing for one possible value, so it doesn't need a bt. 6 7define void @test(ptr %l) nounwind { 8; CHECK-LABEL: test: 9; CHECK: # %bb.0: # %entry 10; CHECK-NEXT: pushq %rax 11; CHECK-NEXT: movq %rdi, (%rsp) 12; CHECK-NEXT: movsbl (%rdi), %eax 13; CHECK-NEXT: addl $-33, %eax 14; CHECK-NEXT: cmpl $61, %eax 15; CHECK-NEXT: ja .LBB0_7 16; CHECK-NEXT: # %bb.1: # %entry 17; CHECK-NEXT: movabsq $2305843009482129440, %rcx # imm = 0x2000000010000020 18; CHECK-NEXT: btq %rax, %rcx 19; CHECK-NEXT: jb .LBB0_6 20; CHECK-NEXT: # %bb.2: # %entry 21; CHECK-NEXT: movl $671088640, %ecx # imm = 0x28000000 22; CHECK-NEXT: btq %rax, %rcx 23; CHECK-NEXT: jae .LBB0_3 24; CHECK-NEXT: # %bb.5: # %sw.bb 25; CHECK-NEXT: xorl %edi, %edi 26; CHECK-NEXT: jmp .LBB0_8 27; CHECK-NEXT: .LBB0_6: # %sw.bb2 28; CHECK-NEXT: movl $1, %edi 29; CHECK-NEXT: jmp .LBB0_8 30; CHECK-NEXT: .LBB0_3: # %entry 31; CHECK-NEXT: testq %rax, %rax 32; CHECK-NEXT: jne .LBB0_7 33; CHECK-NEXT: # %bb.4: # %sw.bb4 34; CHECK-NEXT: movl $3, %edi 35; CHECK-NEXT: jmp .LBB0_8 36; CHECK-NEXT: .LBB0_7: # %sw.default 37; CHECK-NEXT: movl $97, %edi 38; CHECK-NEXT: .LBB0_8: # %sw.epilog 39; CHECK-NEXT: callq foo@PLT 40; CHECK-NEXT: popq %rax 41; CHECK-NEXT: retq 42entry: 43 %l.addr = alloca ptr, align 8 ; <ptr> [#uses=2] 44 store ptr %l, ptr %l.addr 45 %tmp = load ptr, ptr %l.addr ; <ptr> [#uses=1] 46 %tmp1 = load i8, ptr %tmp ; <i8> [#uses=1] 47 %conv = sext i8 %tmp1 to i32 ; <i32> [#uses=1] 48 switch i32 %conv, label %sw.default [ 49 i32 62, label %sw.bb 50 i32 60, label %sw.bb 51 i32 38, label %sw.bb2 52 i32 94, label %sw.bb2 53 i32 61, label %sw.bb2 54 i32 33, label %sw.bb4 55 ] 56 57sw.bb: ; preds = %entry, %entry 58 call void @foo(i32 0) 59 br label %sw.epilog 60 61sw.bb2: ; preds = %entry, %entry, %entry 62 call void @foo(i32 1) 63 br label %sw.epilog 64 65sw.bb4: ; preds = %entry 66 call void @foo(i32 3) 67 br label %sw.epilog 68 69sw.default: ; preds = %entry 70 call void @foo(i32 97) 71 br label %sw.epilog 72 73sw.epilog: ; preds = %sw.default, %sw.bb4, %sw.bb2, %sw.bb 74 ret void 75} 76 77declare void @foo(i32) 78 79; Don't zero extend the test operands to pointer type if it can be avoided. 80; rdar://8781238 81define void @test2(i32 %x) nounwind ssp { 82; CHECK-LABEL: test2: 83; CHECK: # %bb.0: # %entry 84; CHECK-NEXT: cmpl $6, %edi 85; CHECK-NEXT: ja .LBB1_2 86; CHECK-NEXT: # %bb.1: # %entry 87; CHECK-NEXT: movl $91, %eax 88; CHECK-NEXT: btl %edi, %eax 89; CHECK-NEXT: jb bar@PLT # TAILCALL 90; CHECK-NEXT: .LBB1_2: # %if.end 91; CHECK-NEXT: retq 92 93entry: 94 switch i32 %x, label %if.end [ 95 i32 6, label %if.then 96 i32 4, label %if.then 97 i32 3, label %if.then 98 i32 1, label %if.then 99 i32 0, label %if.then 100 ] 101 102if.then: ; preds = %entry, %entry, %entry, %entry, %entry 103 tail call void @bar() nounwind 104 ret void 105 106if.end: ; preds = %entry 107 ret void 108} 109 110declare void @bar() 111 112define void @test3(i32 %x) nounwind { 113; CHECK-LABEL: test3: 114; CHECK: # %bb.0: 115; CHECK-NEXT: cmpl $5, %edi 116; CHECK-NEXT: ja .LBB2_2 117; CHECK-NEXT: # %bb.1: 118; CHECK-NEXT: cmpl $4, %edi 119; CHECK-NEXT: jne bar@PLT # TAILCALL 120; CHECK-NEXT: .LBB2_2: # %if.end 121; CHECK-NEXT: retq 122 switch i32 %x, label %if.end [ 123 i32 0, label %if.then 124 i32 1, label %if.then 125 i32 2, label %if.then 126 i32 3, label %if.then 127 i32 5, label %if.then 128 ] 129if.then: 130 tail call void @bar() nounwind 131 ret void 132if.end: 133 ret void 134} 135 136; Ensure that optimizing for jump tables doesn't needlessly deteriorate the 137; created binary tree search. See PR22262. 138define void @test4(i32 %x, ptr %y) { 139; CHECK-LABEL: test4: 140; CHECK: # %bb.0: # %entry 141; CHECK-NEXT: cmpl $39, %edi 142; CHECK-NEXT: jg .LBB3_5 143; CHECK-NEXT: # %bb.1: # %entry 144; CHECK-NEXT: cmpl $10, %edi 145; CHECK-NEXT: je .LBB3_9 146; CHECK-NEXT: # %bb.2: # %entry 147; CHECK-NEXT: cmpl $20, %edi 148; CHECK-NEXT: je .LBB3_10 149; CHECK-NEXT: # %bb.3: # %entry 150; CHECK-NEXT: cmpl $30, %edi 151; CHECK-NEXT: jne .LBB3_13 152; CHECK-NEXT: # %bb.4: # %sw.bb2 153; CHECK-NEXT: movl $3, (%rsi) 154; CHECK-NEXT: retq 155; CHECK-NEXT: .LBB3_5: # %entry 156; CHECK-NEXT: cmpl $40, %edi 157; CHECK-NEXT: je .LBB3_11 158; CHECK-NEXT: # %bb.6: # %entry 159; CHECK-NEXT: cmpl $50, %edi 160; CHECK-NEXT: je .LBB3_12 161; CHECK-NEXT: # %bb.7: # %entry 162; CHECK-NEXT: cmpl $60, %edi 163; CHECK-NEXT: jne .LBB3_13 164; CHECK-NEXT: # %bb.8: # %sw.bb5 165; CHECK-NEXT: movl $6, (%rsi) 166; CHECK-NEXT: retq 167; CHECK-NEXT: .LBB3_9: # %sw.bb 168; CHECK-NEXT: movl $1, (%rsi) 169; CHECK-NEXT: retq 170; CHECK-NEXT: .LBB3_11: # %sw.bb3 171; CHECK-NEXT: movl $4, (%rsi) 172; CHECK-NEXT: retq 173; CHECK-NEXT: .LBB3_13: # %sw.default 174; CHECK-NEXT: movl $7, (%rsi) 175; CHECK-NEXT: retq 176; CHECK-NEXT: .LBB3_10: # %sw.bb1 177; CHECK-NEXT: movl $2, (%rsi) 178; CHECK-NEXT: retq 179; CHECK-NEXT: .LBB3_12: # %sw.bb4 180; CHECK-NEXT: movl $5, (%rsi) 181; CHECK-NEXT: retq 182 183entry: 184 switch i32 %x, label %sw.default [ 185 i32 10, label %sw.bb 186 i32 20, label %sw.bb1 187 i32 30, label %sw.bb2 188 i32 40, label %sw.bb3 189 i32 50, label %sw.bb4 190 i32 60, label %sw.bb5 191 ] 192sw.bb: 193 store i32 1, ptr %y 194 br label %sw.epilog 195sw.bb1: 196 store i32 2, ptr %y 197 br label %sw.epilog 198sw.bb2: 199 store i32 3, ptr %y 200 br label %sw.epilog 201sw.bb3: 202 store i32 4, ptr %y 203 br label %sw.epilog 204sw.bb4: 205 store i32 5, ptr %y 206 br label %sw.epilog 207sw.bb5: 208 store i32 6, ptr %y 209 br label %sw.epilog 210sw.default: 211 store i32 7, ptr %y 212 br label %sw.epilog 213sw.epilog: 214 ret void 215 216; The balanced binary switch here would start with a comparison against 39, but 217; it is currently starting with 29 because of the density-sum heuristic. 218} 219 220 221; Omit the range check when the default case is unreachable, see PR43129. 222declare void @g(i32) 223define void @test5(i32 %x) { 224; CHECK-LABEL: test5: 225; CHECK: # %bb.0: # %entry 226; CHECK-NEXT: pushq %rax 227; CHECK-NEXT: .cfi_def_cfa_offset 16 228; CHECK-NEXT: movl $73, %eax 229; CHECK-NEXT: btl %edi, %eax 230; CHECK-NEXT: jb .LBB4_3 231; CHECK-NEXT: # %bb.1: # %entry 232; CHECK-NEXT: movl $146, %eax 233; CHECK-NEXT: btl %edi, %eax 234; CHECK-NEXT: jae .LBB4_2 235; CHECK-NEXT: # %bb.4: # %bb1 236; CHECK-NEXT: movl $1, %edi 237; CHECK-NEXT: callq g@PLT 238; CHECK-NEXT: .LBB4_3: # %bb0 239; CHECK-NEXT: xorl %edi, %edi 240; CHECK-NEXT: callq g@PLT 241; CHECK-NEXT: .LBB4_2: # %bb2 242; CHECK-NEXT: movl $2, %edi 243; CHECK-NEXT: callq g@PLT 244 245entry: 246 switch i32 %x, label %return [ 247 ; 73 = 2^0 + 2^3 + 2^6 248 i32 0, label %bb0 249 i32 3, label %bb0 250 i32 6, label %bb0 251 252 ; 146 = 2^1 + 2^4 + 2^7 253 i32 1, label %bb1 254 i32 4, label %bb1 255 i32 7, label %bb1 256 257 i32 2, label %bb2 258 i32 5, label %bb2 259 i32 8, label %bb2 260 ] 261bb0: tail call void @g(i32 0) br label %return 262bb1: tail call void @g(i32 1) br label %return 263bb2: tail call void @g(i32 2) br label %return 264return: unreachable 265} 266