1; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py 2; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=40 -switch-peel-threshold=101 -verify-machineinstrs | FileCheck %s 3; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 -jump-table-density=40 -verify-machineinstrs | FileCheck --check-prefix=NOOPT %s 4 5declare void @g(i32) 6 7; Should be lowered as a jump table, both with and without optimization. 8define void @basic(i32 %x) { 9; CHECK-LABEL: basic: 10; CHECK: # %bb.0: # %entry 11; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 12; CHECK-NEXT: decl %edi 13; CHECK-NEXT: cmpl $4, %edi 14; CHECK-NEXT: ja .LBB0_4 15; CHECK-NEXT: # %bb.1: # %entry 16; CHECK-NEXT: jmpq *.LJTI0_0(,%rdi,8) 17; CHECK-NEXT: .LBB0_3: # %bb2 18; CHECK-NEXT: movl $1, %edi 19; CHECK-NEXT: jmp g@PLT # TAILCALL 20; CHECK-NEXT: .LBB0_2: # %bb0 21; CHECK-NEXT: xorl %edi, %edi 22; CHECK-NEXT: jmp g@PLT # TAILCALL 23; CHECK-NEXT: .LBB0_4: # %return 24; CHECK-NEXT: retq 25; 26; NOOPT-LABEL: basic: 27; NOOPT: # %bb.0: # %entry 28; NOOPT-NEXT: pushq %rax 29; NOOPT-NEXT: .cfi_def_cfa_offset 16 30; NOOPT-NEXT: movl %edi, %eax 31; NOOPT-NEXT: decl %eax 32; NOOPT-NEXT: movl %eax, %ecx 33; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill 34; NOOPT-NEXT: subl $4, %eax 35; NOOPT-NEXT: ja .LBB0_4 36; NOOPT-NEXT: # %bb.5: # %entry 37; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload 38; NOOPT-NEXT: movq .LJTI0_0(,%rax,8), %rax 39; NOOPT-NEXT: jmpq *%rax 40; NOOPT-NEXT: .LBB0_1: # %bb0 41; NOOPT-NEXT: xorl %edi, %edi 42; NOOPT-NEXT: callq g@PLT 43; NOOPT-NEXT: jmp .LBB0_4 44; NOOPT-NEXT: .LBB0_2: # %bb1 45; NOOPT-NEXT: movl $1, %edi 46; NOOPT-NEXT: callq g@PLT 47; NOOPT-NEXT: jmp .LBB0_4 48; NOOPT-NEXT: .LBB0_3: # %bb2 49; NOOPT-NEXT: movl $1, %edi 50; NOOPT-NEXT: callq g@PLT 51; NOOPT-NEXT: .LBB0_4: # %return 52; NOOPT-NEXT: popq %rax 53; NOOPT-NEXT: .cfi_def_cfa_offset 8 54; NOOPT-NEXT: retq 55entry: 56 switch i32 %x, label %return [ 57 i32 3, label %bb0 58 i32 1, label %bb1 59 i32 4, label %bb1 60 i32 5, label %bb2 61 ] 62bb0: tail call void @g(i32 0) br label %return 63bb1: tail call void @g(i32 1) br label %return 64bb2: tail call void @g(i32 1) br label %return 65return: ret void 66} 67 68; Should never be lowered as a jump table because of the attribute 69define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" { 70; CHECK-LABEL: basic_nojumptable: 71; CHECK: # %bb.0: # %entry 72; CHECK-NEXT: cmpl $3, %edi 73; CHECK-NEXT: jg .LBB1_4 74; CHECK-NEXT: # %bb.1: # %entry 75; CHECK-NEXT: cmpl $1, %edi 76; CHECK-NEXT: je .LBB1_7 77; CHECK-NEXT: # %bb.2: # %entry 78; CHECK-NEXT: cmpl $3, %edi 79; CHECK-NEXT: jne .LBB1_6 80; CHECK-NEXT: # %bb.3: # %bb0 81; CHECK-NEXT: xorl %edi, %edi 82; CHECK-NEXT: jmp g@PLT # TAILCALL 83; CHECK-NEXT: .LBB1_4: # %entry 84; CHECK-NEXT: cmpl $4, %edi 85; CHECK-NEXT: je .LBB1_7 86; CHECK-NEXT: # %bb.5: # %entry 87; CHECK-NEXT: cmpl $5, %edi 88; CHECK-NEXT: jne .LBB1_6 89; CHECK-NEXT: .LBB1_7: # %bb2 90; CHECK-NEXT: movl $1, %edi 91; CHECK-NEXT: jmp g@PLT # TAILCALL 92; CHECK-NEXT: .LBB1_6: # %return 93; CHECK-NEXT: retq 94; 95; NOOPT-LABEL: basic_nojumptable: 96; NOOPT: # %bb.0: # %entry 97; NOOPT-NEXT: pushq %rax 98; NOOPT-NEXT: .cfi_def_cfa_offset 16 99; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 100; NOOPT-NEXT: subl $1, %edi 101; NOOPT-NEXT: je .LBB1_2 102; NOOPT-NEXT: jmp .LBB1_5 103; NOOPT-NEXT: .LBB1_5: # %entry 104; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 105; NOOPT-NEXT: subl $3, %eax 106; NOOPT-NEXT: je .LBB1_1 107; NOOPT-NEXT: jmp .LBB1_6 108; NOOPT-NEXT: .LBB1_6: # %entry 109; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 110; NOOPT-NEXT: subl $4, %eax 111; NOOPT-NEXT: je .LBB1_2 112; NOOPT-NEXT: jmp .LBB1_7 113; NOOPT-NEXT: .LBB1_7: # %entry 114; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 115; NOOPT-NEXT: subl $5, %eax 116; NOOPT-NEXT: je .LBB1_3 117; NOOPT-NEXT: jmp .LBB1_4 118; NOOPT-NEXT: .LBB1_1: # %bb0 119; NOOPT-NEXT: xorl %edi, %edi 120; NOOPT-NEXT: callq g@PLT 121; NOOPT-NEXT: jmp .LBB1_4 122; NOOPT-NEXT: .LBB1_2: # %bb1 123; NOOPT-NEXT: movl $1, %edi 124; NOOPT-NEXT: callq g@PLT 125; NOOPT-NEXT: jmp .LBB1_4 126; NOOPT-NEXT: .LBB1_3: # %bb2 127; NOOPT-NEXT: movl $1, %edi 128; NOOPT-NEXT: callq g@PLT 129; NOOPT-NEXT: .LBB1_4: # %return 130; NOOPT-NEXT: popq %rax 131; NOOPT-NEXT: .cfi_def_cfa_offset 8 132; NOOPT-NEXT: retq 133entry: 134 switch i32 %x, label %return [ 135 i32 3, label %bb0 136 i32 1, label %bb1 137 i32 4, label %bb1 138 i32 5, label %bb2 139 ] 140bb0: tail call void @g(i32 0) br label %return 141bb1: tail call void @g(i32 1) br label %return 142bb2: tail call void @g(i32 1) br label %return 143return: ret void 144} 145 146; Should be lowered as a jump table because of the attribute 147define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" { 148; CHECK-LABEL: basic_nojumptable_false: 149; CHECK: # %bb.0: # %entry 150; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 151; CHECK-NEXT: decl %edi 152; CHECK-NEXT: cmpl $4, %edi 153; CHECK-NEXT: ja .LBB2_4 154; CHECK-NEXT: # %bb.1: # %entry 155; CHECK-NEXT: jmpq *.LJTI2_0(,%rdi,8) 156; CHECK-NEXT: .LBB2_3: # %bb2 157; CHECK-NEXT: movl $1, %edi 158; CHECK-NEXT: jmp g@PLT # TAILCALL 159; CHECK-NEXT: .LBB2_2: # %bb0 160; CHECK-NEXT: xorl %edi, %edi 161; CHECK-NEXT: jmp g@PLT # TAILCALL 162; CHECK-NEXT: .LBB2_4: # %return 163; CHECK-NEXT: retq 164; 165; NOOPT-LABEL: basic_nojumptable_false: 166; NOOPT: # %bb.0: # %entry 167; NOOPT-NEXT: pushq %rax 168; NOOPT-NEXT: .cfi_def_cfa_offset 16 169; NOOPT-NEXT: movl %edi, %eax 170; NOOPT-NEXT: decl %eax 171; NOOPT-NEXT: movl %eax, %ecx 172; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill 173; NOOPT-NEXT: subl $4, %eax 174; NOOPT-NEXT: ja .LBB2_4 175; NOOPT-NEXT: # %bb.5: # %entry 176; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload 177; NOOPT-NEXT: movq .LJTI2_0(,%rax,8), %rax 178; NOOPT-NEXT: jmpq *%rax 179; NOOPT-NEXT: .LBB2_1: # %bb0 180; NOOPT-NEXT: xorl %edi, %edi 181; NOOPT-NEXT: callq g@PLT 182; NOOPT-NEXT: jmp .LBB2_4 183; NOOPT-NEXT: .LBB2_2: # %bb1 184; NOOPT-NEXT: movl $1, %edi 185; NOOPT-NEXT: callq g@PLT 186; NOOPT-NEXT: jmp .LBB2_4 187; NOOPT-NEXT: .LBB2_3: # %bb2 188; NOOPT-NEXT: movl $1, %edi 189; NOOPT-NEXT: callq g@PLT 190; NOOPT-NEXT: .LBB2_4: # %return 191; NOOPT-NEXT: popq %rax 192; NOOPT-NEXT: .cfi_def_cfa_offset 8 193; NOOPT-NEXT: retq 194entry: 195 switch i32 %x, label %return [ 196 i32 3, label %bb0 197 i32 1, label %bb1 198 i32 4, label %bb1 199 i32 5, label %bb2 200 ] 201bb0: tail call void @g(i32 0) br label %return 202bb1: tail call void @g(i32 1) br label %return 203bb2: tail call void @g(i32 1) br label %return 204return: ret void 205} 206 207 208; Should be lowered to two range checks. 209; We do this even at -O0, because it's cheap and makes codegen faster. 210define void @simple_ranges(i32 %x) { 211; CHECK-LABEL: simple_ranges: 212; CHECK: # %bb.0: # %entry 213; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 214; CHECK-NEXT: leal -100(%rdi), %eax 215; CHECK-NEXT: cmpl $4, %eax 216; CHECK-NEXT: jb .LBB3_3 217; CHECK-NEXT: # %bb.1: # %entry 218; CHECK-NEXT: cmpl $3, %edi 219; CHECK-NEXT: ja .LBB3_4 220; CHECK-NEXT: # %bb.2: # %bb0 221; CHECK-NEXT: xorl %edi, %edi 222; CHECK-NEXT: jmp g@PLT # TAILCALL 223; CHECK-NEXT: .LBB3_3: # %bb1 224; CHECK-NEXT: movl $1, %edi 225; CHECK-NEXT: jmp g@PLT # TAILCALL 226; CHECK-NEXT: .LBB3_4: # %return 227; CHECK-NEXT: retq 228; 229; NOOPT-LABEL: simple_ranges: 230; NOOPT: # %bb.0: # %entry 231; NOOPT-NEXT: pushq %rax 232; NOOPT-NEXT: .cfi_def_cfa_offset 16 233; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 234; NOOPT-NEXT: subl $4, %edi 235; NOOPT-NEXT: jb .LBB3_1 236; NOOPT-NEXT: jmp .LBB3_4 237; NOOPT-NEXT: .LBB3_4: # %entry 238; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 239; NOOPT-NEXT: addl $-100, %eax 240; NOOPT-NEXT: subl $4, %eax 241; NOOPT-NEXT: jb .LBB3_2 242; NOOPT-NEXT: jmp .LBB3_3 243; NOOPT-NEXT: .LBB3_1: # %bb0 244; NOOPT-NEXT: xorl %edi, %edi 245; NOOPT-NEXT: callq g@PLT 246; NOOPT-NEXT: jmp .LBB3_3 247; NOOPT-NEXT: .LBB3_2: # %bb1 248; NOOPT-NEXT: movl $1, %edi 249; NOOPT-NEXT: callq g@PLT 250; NOOPT-NEXT: .LBB3_3: # %return 251; NOOPT-NEXT: popq %rax 252; NOOPT-NEXT: .cfi_def_cfa_offset 8 253; NOOPT-NEXT: retq 254entry: 255 switch i32 %x, label %return [ 256 i32 0, label %bb0 257 i32 1, label %bb0 258 i32 2, label %bb0 259 i32 3, label %bb0 260 i32 100, label %bb1 261 i32 101, label %bb1 262 i32 102, label %bb1 263 i32 103, label %bb1 264 ] 265bb0: tail call void @g(i32 0) br label %return 266bb1: tail call void @g(i32 1) br label %return 267return: ret void 268} 269 270 271; Cases 0-5 could be lowered with two bit tests, 272; but with 6-8, the whole switch is suitable for a jump table. 273define void @jt_is_better(i32 %x) { 274; CHECK-LABEL: jt_is_better: 275; CHECK: # %bb.0: # %entry 276; CHECK-NEXT: cmpl $8, %edi 277; CHECK-NEXT: ja .LBB4_7 278; CHECK-NEXT: # %bb.1: # %entry 279; CHECK-NEXT: movl %edi, %eax 280; CHECK-NEXT: jmpq *.LJTI4_0(,%rax,8) 281; CHECK-NEXT: .LBB4_2: # %bb0 282; CHECK-NEXT: xorl %edi, %edi 283; CHECK-NEXT: jmp g@PLT # TAILCALL 284; CHECK-NEXT: .LBB4_3: # %bb1 285; CHECK-NEXT: movl $1, %edi 286; CHECK-NEXT: jmp g@PLT # TAILCALL 287; CHECK-NEXT: .LBB4_5: # %bb3 288; CHECK-NEXT: movl $3, %edi 289; CHECK-NEXT: jmp g@PLT # TAILCALL 290; CHECK-NEXT: .LBB4_4: # %bb2 291; CHECK-NEXT: movl $2, %edi 292; CHECK-NEXT: jmp g@PLT # TAILCALL 293; CHECK-NEXT: .LBB4_6: # %bb4 294; CHECK-NEXT: movl $4, %edi 295; CHECK-NEXT: jmp g@PLT # TAILCALL 296; CHECK-NEXT: .LBB4_7: # %return 297; CHECK-NEXT: retq 298; 299; NOOPT-LABEL: jt_is_better: 300; NOOPT: # %bb.0: # %entry 301; NOOPT-NEXT: pushq %rax 302; NOOPT-NEXT: .cfi_def_cfa_offset 16 303; NOOPT-NEXT: movl %edi, %eax 304; NOOPT-NEXT: # kill: def $rax killed $eax 305; NOOPT-NEXT: movq %rax, (%rsp) # 8-byte Spill 306; NOOPT-NEXT: subl $8, %edi 307; NOOPT-NEXT: ja .LBB4_6 308; NOOPT-NEXT: # %bb.7: # %entry 309; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload 310; NOOPT-NEXT: movq .LJTI4_0(,%rax,8), %rax 311; NOOPT-NEXT: jmpq *%rax 312; NOOPT-NEXT: .LBB4_1: # %bb0 313; NOOPT-NEXT: xorl %edi, %edi 314; NOOPT-NEXT: callq g@PLT 315; NOOPT-NEXT: jmp .LBB4_6 316; NOOPT-NEXT: .LBB4_2: # %bb1 317; NOOPT-NEXT: movl $1, %edi 318; NOOPT-NEXT: callq g@PLT 319; NOOPT-NEXT: jmp .LBB4_6 320; NOOPT-NEXT: .LBB4_3: # %bb2 321; NOOPT-NEXT: movl $2, %edi 322; NOOPT-NEXT: callq g@PLT 323; NOOPT-NEXT: jmp .LBB4_6 324; NOOPT-NEXT: .LBB4_4: # %bb3 325; NOOPT-NEXT: movl $3, %edi 326; NOOPT-NEXT: callq g@PLT 327; NOOPT-NEXT: jmp .LBB4_6 328; NOOPT-NEXT: .LBB4_5: # %bb4 329; NOOPT-NEXT: movl $4, %edi 330; NOOPT-NEXT: callq g@PLT 331; NOOPT-NEXT: .LBB4_6: # %return 332; NOOPT-NEXT: popq %rax 333; NOOPT-NEXT: .cfi_def_cfa_offset 8 334; NOOPT-NEXT: retq 335entry: 336 switch i32 %x, label %return [ 337 i32 0, label %bb0 338 i32 2, label %bb0 339 i32 4, label %bb0 340 i32 1, label %bb1 341 i32 3, label %bb1 342 i32 5, label %bb1 343 344 i32 6, label %bb2 345 i32 7, label %bb3 346 i32 8, label %bb4 347 ] 348bb0: tail call void @g(i32 0) br label %return 349bb1: tail call void @g(i32 1) br label %return 350bb2: tail call void @g(i32 2) br label %return 351bb3: tail call void @g(i32 3) br label %return 352bb4: tail call void @g(i32 4) br label %return 353return: ret void 354} 355 356 357; This could be lowered as a jump table, but bit tests is more efficient. 358; The bit test on 2,5,8 is unnecessary as all cases cover the rage [0, 8]. 359; The range check guarantees that cases other than 0,3,6 and 1,4,7 must be 360; in 2,5,8. 361define void @bt_is_better(i32 %x) { 362; CHECK-LABEL: bt_is_better: 363; CHECK: # %bb.0: # %entry 364; CHECK-NEXT: cmpl $8, %edi 365; CHECK-NEXT: ja .LBB5_4 366; CHECK-NEXT: # %bb.1: # %entry 367; CHECK-NEXT: movl $73, %eax 368; CHECK-NEXT: btl %edi, %eax 369; CHECK-NEXT: jb .LBB5_5 370; CHECK-NEXT: # %bb.2: # %entry 371; CHECK-NEXT: movl $146, %eax 372; CHECK-NEXT: btl %edi, %eax 373; CHECK-NEXT: jae .LBB5_3 374; CHECK-NEXT: # %bb.6: # %bb1 375; CHECK-NEXT: movl $1, %edi 376; CHECK-NEXT: jmp g@PLT # TAILCALL 377; CHECK-NEXT: .LBB5_5: # %bb0 378; CHECK-NEXT: xorl %edi, %edi 379; CHECK-NEXT: jmp g@PLT # TAILCALL 380; CHECK-NEXT: .LBB5_3: # %bb2 381; CHECK-NEXT: movl $2, %edi 382; CHECK-NEXT: jmp g@PLT # TAILCALL 383; CHECK-NEXT: .LBB5_4: # %return 384; CHECK-NEXT: retq 385; 386; NOOPT-LABEL: bt_is_better: 387; NOOPT: # %bb.0: # %entry 388; NOOPT-NEXT: pushq %rax 389; NOOPT-NEXT: .cfi_def_cfa_offset 16 390; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 391; NOOPT-NEXT: testl %edi, %edi 392; NOOPT-NEXT: je .LBB5_1 393; NOOPT-NEXT: jmp .LBB5_5 394; NOOPT-NEXT: .LBB5_5: # %entry 395; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 396; NOOPT-NEXT: subl $1, %eax 397; NOOPT-NEXT: je .LBB5_2 398; NOOPT-NEXT: jmp .LBB5_6 399; NOOPT-NEXT: .LBB5_6: # %entry 400; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 401; NOOPT-NEXT: subl $2, %eax 402; NOOPT-NEXT: je .LBB5_3 403; NOOPT-NEXT: jmp .LBB5_7 404; NOOPT-NEXT: .LBB5_7: # %entry 405; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 406; NOOPT-NEXT: subl $3, %eax 407; NOOPT-NEXT: je .LBB5_1 408; NOOPT-NEXT: jmp .LBB5_8 409; NOOPT-NEXT: .LBB5_8: # %entry 410; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 411; NOOPT-NEXT: subl $4, %eax 412; NOOPT-NEXT: je .LBB5_2 413; NOOPT-NEXT: jmp .LBB5_9 414; NOOPT-NEXT: .LBB5_9: # %entry 415; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 416; NOOPT-NEXT: subl $5, %eax 417; NOOPT-NEXT: je .LBB5_3 418; NOOPT-NEXT: jmp .LBB5_10 419; NOOPT-NEXT: .LBB5_10: # %entry 420; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 421; NOOPT-NEXT: subl $6, %eax 422; NOOPT-NEXT: je .LBB5_1 423; NOOPT-NEXT: jmp .LBB5_11 424; NOOPT-NEXT: .LBB5_11: # %entry 425; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 426; NOOPT-NEXT: subl $7, %eax 427; NOOPT-NEXT: je .LBB5_2 428; NOOPT-NEXT: jmp .LBB5_12 429; NOOPT-NEXT: .LBB5_12: # %entry 430; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 431; NOOPT-NEXT: subl $8, %eax 432; NOOPT-NEXT: je .LBB5_3 433; NOOPT-NEXT: jmp .LBB5_4 434; NOOPT-NEXT: .LBB5_1: # %bb0 435; NOOPT-NEXT: xorl %edi, %edi 436; NOOPT-NEXT: callq g@PLT 437; NOOPT-NEXT: jmp .LBB5_4 438; NOOPT-NEXT: .LBB5_2: # %bb1 439; NOOPT-NEXT: movl $1, %edi 440; NOOPT-NEXT: callq g@PLT 441; NOOPT-NEXT: jmp .LBB5_4 442; NOOPT-NEXT: .LBB5_3: # %bb2 443; NOOPT-NEXT: movl $2, %edi 444; NOOPT-NEXT: callq g@PLT 445; NOOPT-NEXT: .LBB5_4: # %return 446; NOOPT-NEXT: popq %rax 447; NOOPT-NEXT: .cfi_def_cfa_offset 8 448; NOOPT-NEXT: retq 449entry: 450 switch i32 %x, label %return [ 451 i32 0, label %bb0 452 i32 3, label %bb0 453 i32 6, label %bb0 454 i32 1, label %bb1 455 i32 4, label %bb1 456 i32 7, label %bb1 457 i32 2, label %bb2 458 i32 5, label %bb2 459 i32 8, label %bb2 460 ] 461bb0: tail call void @g(i32 0) br label %return 462bb1: tail call void @g(i32 1) br label %return 463bb2: tail call void @g(i32 2) br label %return 464return: ret void 465} 466 467; This will also be lowered as bit test, but as the range [0,8] is not fully 468; covered (5 missing), the default statement can be jumped to and we end up 469; with one more branch. 470define void @bt_is_better2(i32 %x) { 471; CHECK-LABEL: bt_is_better2: 472; CHECK: # %bb.0: # %entry 473; CHECK-NEXT: cmpl $8, %edi 474; CHECK-NEXT: ja .LBB6_7 475; CHECK-NEXT: # %bb.1: # %entry 476; CHECK-NEXT: movl $73, %eax 477; CHECK-NEXT: btl %edi, %eax 478; CHECK-NEXT: jb .LBB6_5 479; CHECK-NEXT: # %bb.2: # %entry 480; CHECK-NEXT: movl $146, %eax 481; CHECK-NEXT: btl %edi, %eax 482; CHECK-NEXT: jae .LBB6_3 483; CHECK-NEXT: # %bb.6: # %bb1 484; CHECK-NEXT: movl $1, %edi 485; CHECK-NEXT: jmp g@PLT # TAILCALL 486; CHECK-NEXT: .LBB6_5: # %bb0 487; CHECK-NEXT: xorl %edi, %edi 488; CHECK-NEXT: jmp g@PLT # TAILCALL 489; CHECK-NEXT: .LBB6_3: # %entry 490; CHECK-NEXT: movl $260, %eax # imm = 0x104 491; CHECK-NEXT: btl %edi, %eax 492; CHECK-NEXT: jae .LBB6_7 493; CHECK-NEXT: # %bb.4: # %bb2 494; CHECK-NEXT: movl $2, %edi 495; CHECK-NEXT: jmp g@PLT # TAILCALL 496; CHECK-NEXT: .LBB6_7: # %return 497; CHECK-NEXT: retq 498; 499; NOOPT-LABEL: bt_is_better2: 500; NOOPT: # %bb.0: # %entry 501; NOOPT-NEXT: pushq %rax 502; NOOPT-NEXT: .cfi_def_cfa_offset 16 503; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 504; NOOPT-NEXT: testl %edi, %edi 505; NOOPT-NEXT: je .LBB6_1 506; NOOPT-NEXT: jmp .LBB6_5 507; NOOPT-NEXT: .LBB6_5: # %entry 508; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 509; NOOPT-NEXT: subl $1, %eax 510; NOOPT-NEXT: je .LBB6_2 511; NOOPT-NEXT: jmp .LBB6_6 512; NOOPT-NEXT: .LBB6_6: # %entry 513; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 514; NOOPT-NEXT: subl $2, %eax 515; NOOPT-NEXT: je .LBB6_3 516; NOOPT-NEXT: jmp .LBB6_7 517; NOOPT-NEXT: .LBB6_7: # %entry 518; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 519; NOOPT-NEXT: subl $3, %eax 520; NOOPT-NEXT: je .LBB6_1 521; NOOPT-NEXT: jmp .LBB6_8 522; NOOPT-NEXT: .LBB6_8: # %entry 523; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 524; NOOPT-NEXT: subl $4, %eax 525; NOOPT-NEXT: je .LBB6_2 526; NOOPT-NEXT: jmp .LBB6_9 527; NOOPT-NEXT: .LBB6_9: # %entry 528; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 529; NOOPT-NEXT: subl $6, %eax 530; NOOPT-NEXT: je .LBB6_1 531; NOOPT-NEXT: jmp .LBB6_10 532; NOOPT-NEXT: .LBB6_10: # %entry 533; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 534; NOOPT-NEXT: subl $7, %eax 535; NOOPT-NEXT: je .LBB6_2 536; NOOPT-NEXT: jmp .LBB6_11 537; NOOPT-NEXT: .LBB6_11: # %entry 538; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 539; NOOPT-NEXT: subl $8, %eax 540; NOOPT-NEXT: je .LBB6_3 541; NOOPT-NEXT: jmp .LBB6_4 542; NOOPT-NEXT: .LBB6_1: # %bb0 543; NOOPT-NEXT: xorl %edi, %edi 544; NOOPT-NEXT: callq g@PLT 545; NOOPT-NEXT: jmp .LBB6_4 546; NOOPT-NEXT: .LBB6_2: # %bb1 547; NOOPT-NEXT: movl $1, %edi 548; NOOPT-NEXT: callq g@PLT 549; NOOPT-NEXT: jmp .LBB6_4 550; NOOPT-NEXT: .LBB6_3: # %bb2 551; NOOPT-NEXT: movl $2, %edi 552; NOOPT-NEXT: callq g@PLT 553; NOOPT-NEXT: .LBB6_4: # %return 554; NOOPT-NEXT: popq %rax 555; NOOPT-NEXT: .cfi_def_cfa_offset 8 556; NOOPT-NEXT: retq 557entry: 558 switch i32 %x, label %return [ 559 i32 0, label %bb0 560 i32 3, label %bb0 561 i32 6, label %bb0 562 i32 1, label %bb1 563 i32 4, label %bb1 564 i32 7, label %bb1 565 i32 2, label %bb2 566 i32 8, label %bb2 567 ] 568bb0: tail call void @g(i32 0) br label %return 569bb1: tail call void @g(i32 1) br label %return 570bb2: tail call void @g(i32 2) br label %return 571return: ret void 572} 573 574define void @bt_is_better3(i32 %x) { 575; CHECK-LABEL: bt_is_better3: 576; CHECK: # %bb.0: # %entry 577; CHECK-NEXT: cmpl $18, %edi 578; CHECK-NEXT: ja .LBB7_7 579; CHECK-NEXT: # %bb.1: # %entry 580; CHECK-NEXT: movl $74752, %eax # imm = 0x12400 581; CHECK-NEXT: btl %edi, %eax 582; CHECK-NEXT: jb .LBB7_5 583; CHECK-NEXT: # %bb.2: # %entry 584; CHECK-NEXT: movl $149504, %eax # imm = 0x24800 585; CHECK-NEXT: btl %edi, %eax 586; CHECK-NEXT: jae .LBB7_3 587; CHECK-NEXT: # %bb.6: # %bb1 588; CHECK-NEXT: movl $1, %edi 589; CHECK-NEXT: jmp g@PLT # TAILCALL 590; CHECK-NEXT: .LBB7_5: # %bb0 591; CHECK-NEXT: xorl %edi, %edi 592; CHECK-NEXT: jmp g@PLT # TAILCALL 593; CHECK-NEXT: .LBB7_3: # %entry 594; CHECK-NEXT: movl $266240, %eax # imm = 0x41000 595; CHECK-NEXT: btl %edi, %eax 596; CHECK-NEXT: jae .LBB7_7 597; CHECK-NEXT: # %bb.4: # %bb2 598; CHECK-NEXT: movl $2, %edi 599; CHECK-NEXT: jmp g@PLT # TAILCALL 600; CHECK-NEXT: .LBB7_7: # %return 601; CHECK-NEXT: retq 602; 603; NOOPT-LABEL: bt_is_better3: 604; NOOPT: # %bb.0: # %entry 605; NOOPT-NEXT: pushq %rax 606; NOOPT-NEXT: .cfi_def_cfa_offset 16 607; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 608; NOOPT-NEXT: subl $10, %edi 609; NOOPT-NEXT: je .LBB7_1 610; NOOPT-NEXT: jmp .LBB7_5 611; NOOPT-NEXT: .LBB7_5: # %entry 612; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 613; NOOPT-NEXT: subl $11, %eax 614; NOOPT-NEXT: je .LBB7_2 615; NOOPT-NEXT: jmp .LBB7_6 616; NOOPT-NEXT: .LBB7_6: # %entry 617; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 618; NOOPT-NEXT: subl $12, %eax 619; NOOPT-NEXT: je .LBB7_3 620; NOOPT-NEXT: jmp .LBB7_7 621; NOOPT-NEXT: .LBB7_7: # %entry 622; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 623; NOOPT-NEXT: subl $13, %eax 624; NOOPT-NEXT: je .LBB7_1 625; NOOPT-NEXT: jmp .LBB7_8 626; NOOPT-NEXT: .LBB7_8: # %entry 627; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 628; NOOPT-NEXT: subl $14, %eax 629; NOOPT-NEXT: je .LBB7_2 630; NOOPT-NEXT: jmp .LBB7_9 631; NOOPT-NEXT: .LBB7_9: # %entry 632; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 633; NOOPT-NEXT: subl $16, %eax 634; NOOPT-NEXT: je .LBB7_1 635; NOOPT-NEXT: jmp .LBB7_10 636; NOOPT-NEXT: .LBB7_10: # %entry 637; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 638; NOOPT-NEXT: subl $17, %eax 639; NOOPT-NEXT: je .LBB7_2 640; NOOPT-NEXT: jmp .LBB7_11 641; NOOPT-NEXT: .LBB7_11: # %entry 642; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 643; NOOPT-NEXT: subl $18, %eax 644; NOOPT-NEXT: je .LBB7_3 645; NOOPT-NEXT: jmp .LBB7_4 646; NOOPT-NEXT: .LBB7_1: # %bb0 647; NOOPT-NEXT: xorl %edi, %edi 648; NOOPT-NEXT: callq g@PLT 649; NOOPT-NEXT: jmp .LBB7_4 650; NOOPT-NEXT: .LBB7_2: # %bb1 651; NOOPT-NEXT: movl $1, %edi 652; NOOPT-NEXT: callq g@PLT 653; NOOPT-NEXT: jmp .LBB7_4 654; NOOPT-NEXT: .LBB7_3: # %bb2 655; NOOPT-NEXT: movl $2, %edi 656; NOOPT-NEXT: callq g@PLT 657; NOOPT-NEXT: .LBB7_4: # %return 658; NOOPT-NEXT: popq %rax 659; NOOPT-NEXT: .cfi_def_cfa_offset 8 660; NOOPT-NEXT: retq 661entry: 662 switch i32 %x, label %return [ 663 i32 10, label %bb0 664 i32 13, label %bb0 665 i32 16, label %bb0 666 i32 11, label %bb1 667 i32 14, label %bb1 668 i32 17, label %bb1 669 i32 12, label %bb2 670 i32 18, label %bb2 671 ] 672bb0: tail call void @g(i32 0) br label %return 673bb1: tail call void @g(i32 1) br label %return 674bb2: tail call void @g(i32 2) br label %return 675return: ret void 676 677; We don't have to subtract 10 from the case value to let the range become 678; [0, 8], as each value in the range [10, 18] can be represented by bits in a 679; word. Then we still need a branch to jump to the default statement for the 680; range [0, 10). 681; 74752 = 2^10 + 2^13 + 2^16 682; 149504 = 2^11 + 2^14 + 2^17 683; 266240 = 2^12 + 2^15 + 2^18 684} 685 686 687; Should pivot around 400 for two subtrees of equal size. 688define void @optimal_pivot1(i32 %x) { 689; CHECK-LABEL: optimal_pivot1: 690; CHECK: # %bb.0: # %entry 691; CHECK-NEXT: cmpl $399, %edi # imm = 0x18F 692; CHECK-NEXT: jg .LBB8_5 693; CHECK-NEXT: # %bb.1: # %entry 694; CHECK-NEXT: cmpl $100, %edi 695; CHECK-NEXT: je .LBB8_8 696; CHECK-NEXT: # %bb.2: # %entry 697; CHECK-NEXT: cmpl $200, %edi 698; CHECK-NEXT: je .LBB8_9 699; CHECK-NEXT: # %bb.3: # %entry 700; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C 701; CHECK-NEXT: je .LBB8_8 702; CHECK-NEXT: .LBB8_4: # %return 703; CHECK-NEXT: retq 704; CHECK-NEXT: .LBB8_5: # %entry 705; CHECK-NEXT: cmpl $400, %edi # imm = 0x190 706; CHECK-NEXT: je .LBB8_9 707; CHECK-NEXT: # %bb.6: # %entry 708; CHECK-NEXT: cmpl $600, %edi # imm = 0x258 709; CHECK-NEXT: je .LBB8_9 710; CHECK-NEXT: # %bb.7: # %entry 711; CHECK-NEXT: cmpl $500, %edi # imm = 0x1F4 712; CHECK-NEXT: jne .LBB8_4 713; CHECK-NEXT: .LBB8_8: # %bb0 714; CHECK-NEXT: xorl %edi, %edi 715; CHECK-NEXT: jmp g@PLT # TAILCALL 716; CHECK-NEXT: .LBB8_9: # %bb1 717; CHECK-NEXT: movl $1, %edi 718; CHECK-NEXT: jmp g@PLT # TAILCALL 719; 720; NOOPT-LABEL: optimal_pivot1: 721; NOOPT: # %bb.0: # %entry 722; NOOPT-NEXT: pushq %rax 723; NOOPT-NEXT: .cfi_def_cfa_offset 16 724; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 725; NOOPT-NEXT: subl $100, %edi 726; NOOPT-NEXT: je .LBB8_1 727; NOOPT-NEXT: jmp .LBB8_4 728; NOOPT-NEXT: .LBB8_4: # %entry 729; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 730; NOOPT-NEXT: subl $200, %eax 731; NOOPT-NEXT: je .LBB8_2 732; NOOPT-NEXT: jmp .LBB8_5 733; NOOPT-NEXT: .LBB8_5: # %entry 734; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 735; NOOPT-NEXT: subl $300, %eax # imm = 0x12C 736; NOOPT-NEXT: je .LBB8_1 737; NOOPT-NEXT: jmp .LBB8_6 738; NOOPT-NEXT: .LBB8_6: # %entry 739; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 740; NOOPT-NEXT: subl $400, %eax # imm = 0x190 741; NOOPT-NEXT: je .LBB8_2 742; NOOPT-NEXT: jmp .LBB8_7 743; NOOPT-NEXT: .LBB8_7: # %entry 744; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 745; NOOPT-NEXT: subl $500, %eax # imm = 0x1F4 746; NOOPT-NEXT: je .LBB8_1 747; NOOPT-NEXT: jmp .LBB8_8 748; NOOPT-NEXT: .LBB8_8: # %entry 749; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 750; NOOPT-NEXT: subl $600, %eax # imm = 0x258 751; NOOPT-NEXT: je .LBB8_2 752; NOOPT-NEXT: jmp .LBB8_3 753; NOOPT-NEXT: .LBB8_1: # %bb0 754; NOOPT-NEXT: xorl %edi, %edi 755; NOOPT-NEXT: callq g@PLT 756; NOOPT-NEXT: jmp .LBB8_3 757; NOOPT-NEXT: .LBB8_2: # %bb1 758; NOOPT-NEXT: movl $1, %edi 759; NOOPT-NEXT: callq g@PLT 760; NOOPT-NEXT: .LBB8_3: # %return 761; NOOPT-NEXT: popq %rax 762; NOOPT-NEXT: .cfi_def_cfa_offset 8 763; NOOPT-NEXT: retq 764entry: 765 switch i32 %x, label %return [ 766 i32 100, label %bb0 767 i32 200, label %bb1 768 i32 300, label %bb0 769 i32 400, label %bb1 770 i32 500, label %bb0 771 i32 600, label %bb1 772 773 ] 774bb0: tail call void @g(i32 0) br label %return 775bb1: tail call void @g(i32 1) br label %return 776return: ret void 777} 778 779 780; Should pivot around 300 for two subtrees with two jump tables each. 781define void @optimal_pivot2(i32 %x) { 782; CHECK-LABEL: optimal_pivot2: 783; CHECK: # %bb.0: # %entry 784; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 785; CHECK-NEXT: cmpl $299, %edi # imm = 0x12B 786; CHECK-NEXT: jg .LBB9_4 787; CHECK-NEXT: # %bb.1: # %entry 788; CHECK-NEXT: leal -100(%rdi), %eax 789; CHECK-NEXT: cmpl $3, %eax 790; CHECK-NEXT: jbe .LBB9_12 791; CHECK-NEXT: # %bb.2: # %entry 792; CHECK-NEXT: addl $-200, %edi 793; CHECK-NEXT: cmpl $3, %edi 794; CHECK-NEXT: ja .LBB9_11 795; CHECK-NEXT: # %bb.3: # %entry 796; CHECK-NEXT: jmpq *.LJTI9_1(,%rdi,8) 797; CHECK-NEXT: .LBB9_4: # %entry 798; CHECK-NEXT: leal -300(%rdi), %eax 799; CHECK-NEXT: cmpl $3, %eax 800; CHECK-NEXT: jbe .LBB9_13 801; CHECK-NEXT: # %bb.5: # %entry 802; CHECK-NEXT: addl $-400, %edi # imm = 0xFE70 803; CHECK-NEXT: cmpl $3, %edi 804; CHECK-NEXT: ja .LBB9_11 805; CHECK-NEXT: # %bb.6: # %entry 806; CHECK-NEXT: jmpq *.LJTI9_3(,%rdi,8) 807; CHECK-NEXT: .LBB9_12: # %entry 808; CHECK-NEXT: jmpq *.LJTI9_0(,%rax,8) 809; CHECK-NEXT: .LBB9_13: # %entry 810; CHECK-NEXT: jmpq *.LJTI9_2(,%rax,8) 811; CHECK-NEXT: .LBB9_7: # %bb0 812; CHECK-NEXT: xorl %edi, %edi 813; CHECK-NEXT: jmp g@PLT # TAILCALL 814; CHECK-NEXT: .LBB9_9: # %bb2 815; CHECK-NEXT: movl $2, %edi 816; CHECK-NEXT: jmp g@PLT # TAILCALL 817; CHECK-NEXT: .LBB9_10: # %bb3 818; CHECK-NEXT: movl $3, %edi 819; CHECK-NEXT: jmp g@PLT # TAILCALL 820; CHECK-NEXT: .LBB9_8: # %bb1 821; CHECK-NEXT: movl $1, %edi 822; CHECK-NEXT: jmp g@PLT # TAILCALL 823; CHECK-NEXT: .LBB9_11: # %return 824; CHECK-NEXT: retq 825; 826; NOOPT-LABEL: optimal_pivot2: 827; NOOPT: # %bb.0: # %entry 828; NOOPT-NEXT: pushq %rax 829; NOOPT-NEXT: .cfi_def_cfa_offset 16 830; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 831; NOOPT-NEXT: subl $100, %edi 832; NOOPT-NEXT: je .LBB9_1 833; NOOPT-NEXT: jmp .LBB9_6 834; NOOPT-NEXT: .LBB9_6: # %entry 835; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 836; NOOPT-NEXT: subl $101, %eax 837; NOOPT-NEXT: je .LBB9_2 838; NOOPT-NEXT: jmp .LBB9_7 839; NOOPT-NEXT: .LBB9_7: # %entry 840; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 841; NOOPT-NEXT: subl $102, %eax 842; NOOPT-NEXT: je .LBB9_3 843; NOOPT-NEXT: jmp .LBB9_8 844; NOOPT-NEXT: .LBB9_8: # %entry 845; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 846; NOOPT-NEXT: subl $103, %eax 847; NOOPT-NEXT: je .LBB9_4 848; NOOPT-NEXT: jmp .LBB9_9 849; NOOPT-NEXT: .LBB9_9: # %entry 850; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 851; NOOPT-NEXT: subl $200, %eax 852; NOOPT-NEXT: je .LBB9_1 853; NOOPT-NEXT: jmp .LBB9_10 854; NOOPT-NEXT: .LBB9_10: # %entry 855; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 856; NOOPT-NEXT: subl $201, %eax 857; NOOPT-NEXT: je .LBB9_2 858; NOOPT-NEXT: jmp .LBB9_11 859; NOOPT-NEXT: .LBB9_11: # %entry 860; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 861; NOOPT-NEXT: subl $202, %eax 862; NOOPT-NEXT: je .LBB9_3 863; NOOPT-NEXT: jmp .LBB9_12 864; NOOPT-NEXT: .LBB9_12: # %entry 865; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 866; NOOPT-NEXT: subl $203, %eax 867; NOOPT-NEXT: je .LBB9_4 868; NOOPT-NEXT: jmp .LBB9_13 869; NOOPT-NEXT: .LBB9_13: # %entry 870; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 871; NOOPT-NEXT: subl $300, %eax # imm = 0x12C 872; NOOPT-NEXT: je .LBB9_1 873; NOOPT-NEXT: jmp .LBB9_14 874; NOOPT-NEXT: .LBB9_14: # %entry 875; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 876; NOOPT-NEXT: subl $301, %eax # imm = 0x12D 877; NOOPT-NEXT: je .LBB9_2 878; NOOPT-NEXT: jmp .LBB9_15 879; NOOPT-NEXT: .LBB9_15: # %entry 880; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 881; NOOPT-NEXT: subl $302, %eax # imm = 0x12E 882; NOOPT-NEXT: je .LBB9_3 883; NOOPT-NEXT: jmp .LBB9_16 884; NOOPT-NEXT: .LBB9_16: # %entry 885; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 886; NOOPT-NEXT: subl $303, %eax # imm = 0x12F 887; NOOPT-NEXT: je .LBB9_4 888; NOOPT-NEXT: jmp .LBB9_17 889; NOOPT-NEXT: .LBB9_17: # %entry 890; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 891; NOOPT-NEXT: subl $400, %eax # imm = 0x190 892; NOOPT-NEXT: je .LBB9_1 893; NOOPT-NEXT: jmp .LBB9_18 894; NOOPT-NEXT: .LBB9_18: # %entry 895; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 896; NOOPT-NEXT: subl $401, %eax # imm = 0x191 897; NOOPT-NEXT: je .LBB9_2 898; NOOPT-NEXT: jmp .LBB9_19 899; NOOPT-NEXT: .LBB9_19: # %entry 900; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 901; NOOPT-NEXT: subl $402, %eax # imm = 0x192 902; NOOPT-NEXT: je .LBB9_3 903; NOOPT-NEXT: jmp .LBB9_20 904; NOOPT-NEXT: .LBB9_20: # %entry 905; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 906; NOOPT-NEXT: subl $403, %eax # imm = 0x193 907; NOOPT-NEXT: je .LBB9_4 908; NOOPT-NEXT: jmp .LBB9_5 909; NOOPT-NEXT: .LBB9_1: # %bb0 910; NOOPT-NEXT: xorl %edi, %edi 911; NOOPT-NEXT: callq g@PLT 912; NOOPT-NEXT: jmp .LBB9_5 913; NOOPT-NEXT: .LBB9_2: # %bb1 914; NOOPT-NEXT: movl $1, %edi 915; NOOPT-NEXT: callq g@PLT 916; NOOPT-NEXT: jmp .LBB9_5 917; NOOPT-NEXT: .LBB9_3: # %bb2 918; NOOPT-NEXT: movl $2, %edi 919; NOOPT-NEXT: callq g@PLT 920; NOOPT-NEXT: jmp .LBB9_5 921; NOOPT-NEXT: .LBB9_4: # %bb3 922; NOOPT-NEXT: movl $3, %edi 923; NOOPT-NEXT: callq g@PLT 924; NOOPT-NEXT: .LBB9_5: # %return 925; NOOPT-NEXT: popq %rax 926; NOOPT-NEXT: .cfi_def_cfa_offset 8 927; NOOPT-NEXT: retq 928entry: 929 switch i32 %x, label %return [ 930 i32 100, label %bb0 i32 101, label %bb1 i32 102, label %bb2 i32 103, label %bb3 931 i32 200, label %bb0 i32 201, label %bb1 i32 202, label %bb2 i32 203, label %bb3 932 i32 300, label %bb0 i32 301, label %bb1 i32 302, label %bb2 i32 303, label %bb3 933 i32 400, label %bb0 i32 401, label %bb1 i32 402, label %bb2 i32 403, label %bb3 934 935 ] 936bb0: tail call void @g(i32 0) br label %return 937bb1: tail call void @g(i32 1) br label %return 938bb2: tail call void @g(i32 2) br label %return 939bb3: tail call void @g(i32 3) br label %return 940return: ret void 941} 942 943 944; Splitting in the largest gap (between 6 and 12) would yield suboptimal result. 945; Expecting a jump table from 5 to 15. 946; At -O0, we don't build jump tables for only parts of a switch. 947define void @optimal_jump_table1(i32 %x) { 948; CHECK-LABEL: optimal_jump_table1: 949; CHECK: # %bb.0: # %entry 950; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 951; CHECK-NEXT: leal -5(%rdi), %eax 952; CHECK-NEXT: cmpl $10, %eax 953; CHECK-NEXT: ja .LBB10_1 954; CHECK-NEXT: # %bb.9: # %entry 955; CHECK-NEXT: jmpq *.LJTI10_0(,%rax,8) 956; CHECK-NEXT: .LBB10_3: # %bb1 957; CHECK-NEXT: movl $1, %edi 958; CHECK-NEXT: jmp g@PLT # TAILCALL 959; CHECK-NEXT: .LBB10_1: # %entry 960; CHECK-NEXT: testl %edi, %edi 961; CHECK-NEXT: jne .LBB10_8 962; CHECK-NEXT: # %bb.2: # %bb0 963; CHECK-NEXT: xorl %edi, %edi 964; CHECK-NEXT: jmp g@PLT # TAILCALL 965; CHECK-NEXT: .LBB10_8: # %return 966; CHECK-NEXT: retq 967; CHECK-NEXT: .LBB10_7: # %bb5 968; CHECK-NEXT: movl $5, %edi 969; CHECK-NEXT: jmp g@PLT # TAILCALL 970; CHECK-NEXT: .LBB10_5: # %bb3 971; CHECK-NEXT: movl $3, %edi 972; CHECK-NEXT: jmp g@PLT # TAILCALL 973; CHECK-NEXT: .LBB10_4: # %bb2 974; CHECK-NEXT: movl $2, %edi 975; CHECK-NEXT: jmp g@PLT # TAILCALL 976; CHECK-NEXT: .LBB10_6: # %bb4 977; CHECK-NEXT: movl $4, %edi 978; CHECK-NEXT: jmp g@PLT # TAILCALL 979; 980; NOOPT-LABEL: optimal_jump_table1: 981; NOOPT: # %bb.0: # %entry 982; NOOPT-NEXT: pushq %rax 983; NOOPT-NEXT: .cfi_def_cfa_offset 16 984; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 985; NOOPT-NEXT: testl %edi, %edi 986; NOOPT-NEXT: je .LBB10_1 987; NOOPT-NEXT: jmp .LBB10_8 988; NOOPT-NEXT: .LBB10_8: # %entry 989; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 990; NOOPT-NEXT: subl $5, %eax 991; NOOPT-NEXT: je .LBB10_2 992; NOOPT-NEXT: jmp .LBB10_9 993; NOOPT-NEXT: .LBB10_9: # %entry 994; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 995; NOOPT-NEXT: subl $6, %eax 996; NOOPT-NEXT: je .LBB10_3 997; NOOPT-NEXT: jmp .LBB10_10 998; NOOPT-NEXT: .LBB10_10: # %entry 999; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1000; NOOPT-NEXT: subl $12, %eax 1001; NOOPT-NEXT: je .LBB10_4 1002; NOOPT-NEXT: jmp .LBB10_11 1003; NOOPT-NEXT: .LBB10_11: # %entry 1004; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1005; NOOPT-NEXT: subl $13, %eax 1006; NOOPT-NEXT: je .LBB10_5 1007; NOOPT-NEXT: jmp .LBB10_12 1008; NOOPT-NEXT: .LBB10_12: # %entry 1009; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1010; NOOPT-NEXT: subl $15, %eax 1011; NOOPT-NEXT: je .LBB10_6 1012; NOOPT-NEXT: jmp .LBB10_7 1013; NOOPT-NEXT: .LBB10_1: # %bb0 1014; NOOPT-NEXT: xorl %edi, %edi 1015; NOOPT-NEXT: callq g@PLT 1016; NOOPT-NEXT: jmp .LBB10_7 1017; NOOPT-NEXT: .LBB10_2: # %bb1 1018; NOOPT-NEXT: movl $1, %edi 1019; NOOPT-NEXT: callq g@PLT 1020; NOOPT-NEXT: jmp .LBB10_7 1021; NOOPT-NEXT: .LBB10_3: # %bb2 1022; NOOPT-NEXT: movl $2, %edi 1023; NOOPT-NEXT: callq g@PLT 1024; NOOPT-NEXT: jmp .LBB10_7 1025; NOOPT-NEXT: .LBB10_4: # %bb3 1026; NOOPT-NEXT: movl $3, %edi 1027; NOOPT-NEXT: callq g@PLT 1028; NOOPT-NEXT: jmp .LBB10_7 1029; NOOPT-NEXT: .LBB10_5: # %bb4 1030; NOOPT-NEXT: movl $4, %edi 1031; NOOPT-NEXT: callq g@PLT 1032; NOOPT-NEXT: jmp .LBB10_7 1033; NOOPT-NEXT: .LBB10_6: # %bb5 1034; NOOPT-NEXT: movl $5, %edi 1035; NOOPT-NEXT: callq g@PLT 1036; NOOPT-NEXT: .LBB10_7: # %return 1037; NOOPT-NEXT: popq %rax 1038; NOOPT-NEXT: .cfi_def_cfa_offset 8 1039; NOOPT-NEXT: retq 1040entry: 1041 switch i32 %x, label %return [ 1042 i32 0, label %bb0 1043 i32 5, label %bb1 1044 i32 6, label %bb2 1045 i32 12, label %bb3 1046 i32 13, label %bb4 1047 i32 15, label %bb5 1048 ] 1049bb0: tail call void @g(i32 0) br label %return 1050bb1: tail call void @g(i32 1) br label %return 1051bb2: tail call void @g(i32 2) br label %return 1052bb3: tail call void @g(i32 3) br label %return 1053bb4: tail call void @g(i32 4) br label %return 1054bb5: tail call void @g(i32 5) br label %return 1055return: ret void 1056} 1057 1058 1059; Partitioning the cases to the minimum number of dense sets is not good enough. 1060; This can be partitioned as {0,1,2,9},{14,15} or {0,1,2},{9,14,15}. The former 1061; should be preferred. Expecting a table from 0-9. 1062define void @optimal_jump_table2(i32 %x) { 1063; CHECK-LABEL: optimal_jump_table2: 1064; CHECK: # %bb.0: # %entry 1065; CHECK-NEXT: cmpl $9, %edi 1066; CHECK-NEXT: ja .LBB11_1 1067; CHECK-NEXT: # %bb.10: # %entry 1068; CHECK-NEXT: movl %edi, %eax 1069; CHECK-NEXT: jmpq *.LJTI11_0(,%rax,8) 1070; CHECK-NEXT: .LBB11_4: # %bb0 1071; CHECK-NEXT: xorl %edi, %edi 1072; CHECK-NEXT: jmp g@PLT # TAILCALL 1073; CHECK-NEXT: .LBB11_1: # %entry 1074; CHECK-NEXT: cmpl $14, %edi 1075; CHECK-NEXT: je .LBB11_8 1076; CHECK-NEXT: # %bb.2: # %entry 1077; CHECK-NEXT: cmpl $15, %edi 1078; CHECK-NEXT: jne .LBB11_9 1079; CHECK-NEXT: # %bb.3: # %bb5 1080; CHECK-NEXT: movl $5, %edi 1081; CHECK-NEXT: jmp g@PLT # TAILCALL 1082; CHECK-NEXT: .LBB11_9: # %return 1083; CHECK-NEXT: retq 1084; CHECK-NEXT: .LBB11_7: # %bb3 1085; CHECK-NEXT: movl $3, %edi 1086; CHECK-NEXT: jmp g@PLT # TAILCALL 1087; CHECK-NEXT: .LBB11_5: # %bb1 1088; CHECK-NEXT: movl $1, %edi 1089; CHECK-NEXT: jmp g@PLT # TAILCALL 1090; CHECK-NEXT: .LBB11_6: # %bb2 1091; CHECK-NEXT: movl $2, %edi 1092; CHECK-NEXT: jmp g@PLT # TAILCALL 1093; CHECK-NEXT: .LBB11_8: # %bb4 1094; CHECK-NEXT: movl $4, %edi 1095; CHECK-NEXT: jmp g@PLT # TAILCALL 1096; 1097; NOOPT-LABEL: optimal_jump_table2: 1098; NOOPT: # %bb.0: # %entry 1099; NOOPT-NEXT: pushq %rax 1100; NOOPT-NEXT: .cfi_def_cfa_offset 16 1101; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1102; NOOPT-NEXT: testl %edi, %edi 1103; NOOPT-NEXT: je .LBB11_1 1104; NOOPT-NEXT: jmp .LBB11_8 1105; NOOPT-NEXT: .LBB11_8: # %entry 1106; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1107; NOOPT-NEXT: subl $1, %eax 1108; NOOPT-NEXT: je .LBB11_2 1109; NOOPT-NEXT: jmp .LBB11_9 1110; NOOPT-NEXT: .LBB11_9: # %entry 1111; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1112; NOOPT-NEXT: subl $2, %eax 1113; NOOPT-NEXT: je .LBB11_3 1114; NOOPT-NEXT: jmp .LBB11_10 1115; NOOPT-NEXT: .LBB11_10: # %entry 1116; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1117; NOOPT-NEXT: subl $9, %eax 1118; NOOPT-NEXT: je .LBB11_4 1119; NOOPT-NEXT: jmp .LBB11_11 1120; NOOPT-NEXT: .LBB11_11: # %entry 1121; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1122; NOOPT-NEXT: subl $14, %eax 1123; NOOPT-NEXT: je .LBB11_5 1124; NOOPT-NEXT: jmp .LBB11_12 1125; NOOPT-NEXT: .LBB11_12: # %entry 1126; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1127; NOOPT-NEXT: subl $15, %eax 1128; NOOPT-NEXT: je .LBB11_6 1129; NOOPT-NEXT: jmp .LBB11_7 1130; NOOPT-NEXT: .LBB11_1: # %bb0 1131; NOOPT-NEXT: xorl %edi, %edi 1132; NOOPT-NEXT: callq g@PLT 1133; NOOPT-NEXT: jmp .LBB11_7 1134; NOOPT-NEXT: .LBB11_2: # %bb1 1135; NOOPT-NEXT: movl $1, %edi 1136; NOOPT-NEXT: callq g@PLT 1137; NOOPT-NEXT: jmp .LBB11_7 1138; NOOPT-NEXT: .LBB11_3: # %bb2 1139; NOOPT-NEXT: movl $2, %edi 1140; NOOPT-NEXT: callq g@PLT 1141; NOOPT-NEXT: jmp .LBB11_7 1142; NOOPT-NEXT: .LBB11_4: # %bb3 1143; NOOPT-NEXT: movl $3, %edi 1144; NOOPT-NEXT: callq g@PLT 1145; NOOPT-NEXT: jmp .LBB11_7 1146; NOOPT-NEXT: .LBB11_5: # %bb4 1147; NOOPT-NEXT: movl $4, %edi 1148; NOOPT-NEXT: callq g@PLT 1149; NOOPT-NEXT: jmp .LBB11_7 1150; NOOPT-NEXT: .LBB11_6: # %bb5 1151; NOOPT-NEXT: movl $5, %edi 1152; NOOPT-NEXT: callq g@PLT 1153; NOOPT-NEXT: .LBB11_7: # %return 1154; NOOPT-NEXT: popq %rax 1155; NOOPT-NEXT: .cfi_def_cfa_offset 8 1156; NOOPT-NEXT: retq 1157entry: 1158 switch i32 %x, label %return [ 1159 i32 0, label %bb0 1160 i32 1, label %bb1 1161 i32 2, label %bb2 1162 i32 9, label %bb3 1163 i32 14, label %bb4 1164 i32 15, label %bb5 1165 ] 1166bb0: tail call void @g(i32 0) br label %return 1167bb1: tail call void @g(i32 1) br label %return 1168bb2: tail call void @g(i32 2) br label %return 1169bb3: tail call void @g(i32 3) br label %return 1170bb4: tail call void @g(i32 4) br label %return 1171bb5: tail call void @g(i32 5) br label %return 1172return: ret void 1173} 1174 1175 1176; Splitting to maximize left-right density sum and gap size would split this 1177; between 3 and 10, and then between 20 and 25. It's better to build a table 1178; from 1-20. 1179define void @optimal_jump_table3(i32 %x) { 1180; CHECK-LABEL: optimal_jump_table3: 1181; CHECK: # %bb.0: # %entry 1182; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 1183; CHECK-NEXT: leal -1(%rdi), %eax 1184; CHECK-NEXT: cmpl $19, %eax 1185; CHECK-NEXT: ja .LBB12_1 1186; CHECK-NEXT: # %bb.3: # %entry 1187; CHECK-NEXT: jmpq *.LJTI12_0(,%rax,8) 1188; CHECK-NEXT: .LBB12_4: # %bb0 1189; CHECK-NEXT: xorl %edi, %edi 1190; CHECK-NEXT: jmp g@PLT # TAILCALL 1191; CHECK-NEXT: .LBB12_6: # %bb2 1192; CHECK-NEXT: movl $2, %edi 1193; CHECK-NEXT: jmp g@PLT # TAILCALL 1194; CHECK-NEXT: .LBB12_5: # %bb1 1195; CHECK-NEXT: movl $1, %edi 1196; CHECK-NEXT: jmp g@PLT # TAILCALL 1197; CHECK-NEXT: .LBB12_7: # %bb3 1198; CHECK-NEXT: movl $3, %edi 1199; CHECK-NEXT: jmp g@PLT # TAILCALL 1200; CHECK-NEXT: .LBB12_1: # %entry 1201; CHECK-NEXT: cmpl $25, %edi 1202; CHECK-NEXT: jne .LBB12_8 1203; CHECK-NEXT: # %bb.2: # %bb4 1204; CHECK-NEXT: movl $4, %edi 1205; CHECK-NEXT: jmp g@PLT # TAILCALL 1206; CHECK-NEXT: .LBB12_8: # %return 1207; CHECK-NEXT: retq 1208; 1209; NOOPT-LABEL: optimal_jump_table3: 1210; NOOPT: # %bb.0: # %entry 1211; NOOPT-NEXT: pushq %rax 1212; NOOPT-NEXT: .cfi_def_cfa_offset 16 1213; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1214; NOOPT-NEXT: subl $1, %edi 1215; NOOPT-NEXT: je .LBB12_1 1216; NOOPT-NEXT: jmp .LBB12_7 1217; NOOPT-NEXT: .LBB12_7: # %entry 1218; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1219; NOOPT-NEXT: subl $2, %eax 1220; NOOPT-NEXT: je .LBB12_2 1221; NOOPT-NEXT: jmp .LBB12_8 1222; NOOPT-NEXT: .LBB12_8: # %entry 1223; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1224; NOOPT-NEXT: subl $3, %eax 1225; NOOPT-NEXT: je .LBB12_3 1226; NOOPT-NEXT: jmp .LBB12_9 1227; NOOPT-NEXT: .LBB12_9: # %entry 1228; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1229; NOOPT-NEXT: subl $10, %eax 1230; NOOPT-NEXT: je .LBB12_4 1231; NOOPT-NEXT: jmp .LBB12_10 1232; NOOPT-NEXT: .LBB12_10: # %entry 1233; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1234; NOOPT-NEXT: subl $13, %eax 1235; NOOPT-NEXT: je .LBB12_1 1236; NOOPT-NEXT: jmp .LBB12_11 1237; NOOPT-NEXT: .LBB12_11: # %entry 1238; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1239; NOOPT-NEXT: subl $14, %eax 1240; NOOPT-NEXT: je .LBB12_2 1241; NOOPT-NEXT: jmp .LBB12_12 1242; NOOPT-NEXT: .LBB12_12: # %entry 1243; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1244; NOOPT-NEXT: subl $15, %eax 1245; NOOPT-NEXT: je .LBB12_3 1246; NOOPT-NEXT: jmp .LBB12_13 1247; NOOPT-NEXT: .LBB12_13: # %entry 1248; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1249; NOOPT-NEXT: subl $20, %eax 1250; NOOPT-NEXT: je .LBB12_4 1251; NOOPT-NEXT: jmp .LBB12_14 1252; NOOPT-NEXT: .LBB12_14: # %entry 1253; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1254; NOOPT-NEXT: subl $25, %eax 1255; NOOPT-NEXT: je .LBB12_5 1256; NOOPT-NEXT: jmp .LBB12_6 1257; NOOPT-NEXT: .LBB12_1: # %bb0 1258; NOOPT-NEXT: xorl %edi, %edi 1259; NOOPT-NEXT: callq g@PLT 1260; NOOPT-NEXT: jmp .LBB12_6 1261; NOOPT-NEXT: .LBB12_2: # %bb1 1262; NOOPT-NEXT: movl $1, %edi 1263; NOOPT-NEXT: callq g@PLT 1264; NOOPT-NEXT: jmp .LBB12_6 1265; NOOPT-NEXT: .LBB12_3: # %bb2 1266; NOOPT-NEXT: movl $2, %edi 1267; NOOPT-NEXT: callq g@PLT 1268; NOOPT-NEXT: jmp .LBB12_6 1269; NOOPT-NEXT: .LBB12_4: # %bb3 1270; NOOPT-NEXT: movl $3, %edi 1271; NOOPT-NEXT: callq g@PLT 1272; NOOPT-NEXT: jmp .LBB12_6 1273; NOOPT-NEXT: .LBB12_5: # %bb4 1274; NOOPT-NEXT: movl $4, %edi 1275; NOOPT-NEXT: callq g@PLT 1276; NOOPT-NEXT: .LBB12_6: # %return 1277; NOOPT-NEXT: popq %rax 1278; NOOPT-NEXT: .cfi_def_cfa_offset 8 1279; NOOPT-NEXT: retq 1280entry: 1281 switch i32 %x, label %return [ 1282 i32 1, label %bb0 1283 i32 2, label %bb1 1284 i32 3, label %bb2 1285 i32 10, label %bb3 1286 i32 13, label %bb0 1287 i32 14, label %bb1 1288 i32 15, label %bb2 1289 i32 20, label %bb3 1290 i32 25, label %bb4 1291 ] 1292bb0: tail call void @g(i32 0) br label %return 1293bb1: tail call void @g(i32 1) br label %return 1294bb2: tail call void @g(i32 2) br label %return 1295bb3: tail call void @g(i32 3) br label %return 1296bb4: tail call void @g(i32 4) br label %return 1297return: ret void 1298} 1299 1300%struct.S = type { ptr, i32 } 1301 1302; This will be lowered to a comparison with 4 and then bit tests. Make sure 1303; that the phi node in %header gets a value from the comparison block. 1304define void @phi_node_trouble(ptr %s) { 1305; CHECK-LABEL: phi_node_trouble: 1306; CHECK: # %bb.0: # %entry 1307; CHECK-NEXT: .p2align 4 1308; CHECK-NEXT: .LBB13_1: # %header 1309; CHECK-NEXT: # =>This Inner Loop Header: Depth=1 1310; CHECK-NEXT: testq %rdi, %rdi 1311; CHECK-NEXT: je .LBB13_5 1312; CHECK-NEXT: # %bb.2: # %loop 1313; CHECK-NEXT: # in Loop: Header=BB13_1 Depth=1 1314; CHECK-NEXT: movq (%rdi), %rdi 1315; CHECK-NEXT: movl 8(%rdi), %eax 1316; CHECK-NEXT: cmpl $4, %eax 1317; CHECK-NEXT: je .LBB13_1 1318; CHECK-NEXT: # %bb.3: # %loop 1319; CHECK-NEXT: addl $-25, %eax 1320; CHECK-NEXT: cmpl $44, %eax 1321; CHECK-NEXT: ja .LBB13_5 1322; CHECK-NEXT: # %bb.4: # %loop 1323; CHECK-NEXT: movabsq $17592186046465, %rcx # imm = 0x100000000801 1324; CHECK-NEXT: btq %rax, %rcx 1325; CHECK-NEXT: .LBB13_5: # %exit2 1326; CHECK-NEXT: retq 1327; 1328; NOOPT-LABEL: phi_node_trouble: 1329; NOOPT: # %bb.0: # %entry 1330; NOOPT-NEXT: movq %rdi, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill 1331; NOOPT-NEXT: jmp .LBB13_1 1332; NOOPT-NEXT: .LBB13_1: # %header 1333; NOOPT-NEXT: # =>This Inner Loop Header: Depth=1 1334; NOOPT-NEXT: movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload 1335; NOOPT-NEXT: movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill 1336; NOOPT-NEXT: cmpq $0, %rax 1337; NOOPT-NEXT: je .LBB13_3 1338; NOOPT-NEXT: # %bb.2: # %loop 1339; NOOPT-NEXT: # in Loop: Header=BB13_1 Depth=1 1340; NOOPT-NEXT: movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload 1341; NOOPT-NEXT: movq (%rax), %rax 1342; NOOPT-NEXT: movl 8(%rax), %ecx 1343; NOOPT-NEXT: movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1344; NOOPT-NEXT: subl $4, %ecx 1345; NOOPT-NEXT: movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill 1346; NOOPT-NEXT: je .LBB13_1 1347; NOOPT-NEXT: jmp .LBB13_5 1348; NOOPT-NEXT: .LBB13_5: # %loop 1349; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1350; NOOPT-NEXT: subl $25, %eax 1351; NOOPT-NEXT: je .LBB13_4 1352; NOOPT-NEXT: jmp .LBB13_6 1353; NOOPT-NEXT: .LBB13_6: # %loop 1354; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1355; NOOPT-NEXT: subl $36, %eax 1356; NOOPT-NEXT: je .LBB13_4 1357; NOOPT-NEXT: jmp .LBB13_7 1358; NOOPT-NEXT: .LBB13_7: # %loop 1359; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1360; NOOPT-NEXT: subl $69, %eax 1361; NOOPT-NEXT: je .LBB13_4 1362; NOOPT-NEXT: jmp .LBB13_3 1363; NOOPT-NEXT: .LBB13_3: # %exit 1364; NOOPT-NEXT: retq 1365; NOOPT-NEXT: .LBB13_4: # %exit2 1366; NOOPT-NEXT: retq 1367entry: 1368 br label %header 1369header: 1370 %ptr = phi ptr [ %s, %entry ], [ %next, %loop ] 1371 %bool = icmp eq ptr %ptr, null 1372 br i1 %bool, label %exit, label %loop 1373loop: 1374 %next = load ptr, ptr %ptr 1375 %xptr = getelementptr inbounds %struct.S, ptr %next, i64 0, i32 1 1376 %x = load i32, ptr %xptr 1377 switch i32 %x, label %exit [ 1378 i32 4, label %header 1379 i32 36, label %exit2 1380 i32 69, label %exit2 1381 i32 25, label %exit2 1382 ] 1383exit: 1384 ret void 1385exit2: 1386 ret void 1387} 1388 1389 1390; Branch directly to the default. 1391; (In optimized builds the switch is removed earlier.) 1392define void @default_only(i32 %x) { 1393; CHECK-LABEL: default_only: 1394; CHECK: # %bb.0: # %entry 1395; CHECK-NEXT: retq 1396; 1397; NOOPT-LABEL: default_only: 1398; NOOPT: # %bb.0: # %entry 1399; NOOPT-NEXT: jmp .LBB14_2 1400; NOOPT-NEXT: .LBB14_1: # %return 1401; NOOPT-NEXT: retq 1402; NOOPT-NEXT: .LBB14_2: # %sw 1403; NOOPT-NEXT: jmp .LBB14_1 1404entry: 1405 br label %sw 1406return: 1407 ret void 1408sw: 1409 switch i32 %x, label %return [ 1410 ] 1411} 1412 1413 1414; Don't infloop on jump tables where the upper bound is the max value of the 1415; input type (in this case 127). 1416define void @int_max_table_cluster(i8 %x) { 1417; CHECK-LABEL: int_max_table_cluster: 1418; CHECK: # %bb.0: # %entry 1419; CHECK-NEXT: cmpb $-9, %dil 1420; CHECK-NEXT: ja .LBB15_4 1421; CHECK-NEXT: # %bb.1: # %entry 1422; CHECK-NEXT: movzbl %dil, %eax 1423; CHECK-NEXT: jmpq *.LJTI15_0(,%rax,8) 1424; CHECK-NEXT: .LBB15_2: # %bb0 1425; CHECK-NEXT: xorl %edi, %edi 1426; CHECK-NEXT: jmp g@PLT # TAILCALL 1427; CHECK-NEXT: .LBB15_3: # %bb3 1428; CHECK-NEXT: movl $1, %edi 1429; CHECK-NEXT: jmp g@PLT # TAILCALL 1430; CHECK-NEXT: .LBB15_4: # %return 1431; CHECK-NEXT: retq 1432; 1433; NOOPT-LABEL: int_max_table_cluster: 1434; NOOPT: # %bb.0: # %entry 1435; NOOPT-NEXT: pushq %rax 1436; NOOPT-NEXT: .cfi_def_cfa_offset 16 1437; NOOPT-NEXT: movb %dil, %al 1438; NOOPT-NEXT: addb $64, %al 1439; NOOPT-NEXT: movzbl %al, %ecx 1440; NOOPT-NEXT: # kill: def $rcx killed $ecx 1441; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill 1442; NOOPT-NEXT: subb $-65, %al 1443; NOOPT-NEXT: ja .LBB15_5 1444; NOOPT-NEXT: # %bb.6: # %entry 1445; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload 1446; NOOPT-NEXT: movq .LJTI15_0(,%rax,8), %rax 1447; NOOPT-NEXT: jmpq *%rax 1448; NOOPT-NEXT: .LBB15_1: # %bb0 1449; NOOPT-NEXT: xorl %edi, %edi 1450; NOOPT-NEXT: callq g@PLT 1451; NOOPT-NEXT: jmp .LBB15_5 1452; NOOPT-NEXT: .LBB15_2: # %bb1 1453; NOOPT-NEXT: movl $1, %edi 1454; NOOPT-NEXT: callq g@PLT 1455; NOOPT-NEXT: jmp .LBB15_5 1456; NOOPT-NEXT: .LBB15_3: # %bb2 1457; NOOPT-NEXT: movl $1, %edi 1458; NOOPT-NEXT: callq g@PLT 1459; NOOPT-NEXT: jmp .LBB15_5 1460; NOOPT-NEXT: .LBB15_4: # %bb3 1461; NOOPT-NEXT: movl $1, %edi 1462; NOOPT-NEXT: callq g@PLT 1463; NOOPT-NEXT: .LBB15_5: # %return 1464; NOOPT-NEXT: popq %rax 1465; NOOPT-NEXT: .cfi_def_cfa_offset 8 1466; NOOPT-NEXT: retq 1467entry: 1468 switch i8 %x, label %return [ 1469 i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0 1470 i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0 1471 i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0 1472 i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0 1473 i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0 1474 i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0 1475 i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0 1476 i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0 1477 i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0 1478 i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0 1479 i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0 1480 i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0 1481 i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0 1482 i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0 1483 i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0 1484 i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0 1485 i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0 1486 i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0 1487 i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0 1488 i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0 1489 i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0 1490 i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0 1491 i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0 1492 i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0 1493 i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0 1494 i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0 1495 i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0 1496 i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0 1497 i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0 1498 i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0 1499 i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0 1500 i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0 1501 i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1 1502 i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1 1503 i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1 1504 i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1 1505 i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1 1506 i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1 1507 i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1 1508 i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1 1509 i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2 1510 i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2 1511 i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2 1512 i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2 1513 i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3 1514 i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3 1515 ] 1516bb0: tail call void @g(i32 0) br label %return 1517bb1: tail call void @g(i32 1) br label %return 1518bb2: tail call void @g(i32 1) br label %return 1519bb3: tail call void @g(i32 1) br label %return 1520return: ret void 1521} 1522 1523 1524; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so 1525; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 20, 1526; but the latter set has more cases, so should be tested for earlier. The bit 1527; test on 0,3,6 is unnecessary as all cases cover the range [0, 9]. The range 1528; check guarantees that cases other than 1,4,7 and 2,5,8,9 must be in 0,3,6. 1529define void @bt_order_by_weight(i32 %x) { 1530; CHECK-LABEL: bt_order_by_weight: 1531; CHECK: # %bb.0: # %entry 1532; CHECK-NEXT: cmpl $9, %edi 1533; CHECK-NEXT: ja .LBB16_6 1534; CHECK-NEXT: # %bb.1: # %entry 1535; CHECK-NEXT: movl $146, %eax 1536; CHECK-NEXT: btl %edi, %eax 1537; CHECK-NEXT: jae .LBB16_2 1538; CHECK-NEXT: # %bb.4: # %bb1 1539; CHECK-NEXT: movl $1, %edi 1540; CHECK-NEXT: jmp g@PLT # TAILCALL 1541; CHECK-NEXT: .LBB16_2: # %entry 1542; CHECK-NEXT: movl $804, %eax # imm = 0x324 1543; CHECK-NEXT: btl %edi, %eax 1544; CHECK-NEXT: jae .LBB16_3 1545; CHECK-NEXT: # %bb.5: # %bb2 1546; CHECK-NEXT: movl $2, %edi 1547; CHECK-NEXT: jmp g@PLT # TAILCALL 1548; CHECK-NEXT: .LBB16_3: # %bb0 1549; CHECK-NEXT: xorl %edi, %edi 1550; CHECK-NEXT: jmp g@PLT # TAILCALL 1551; CHECK-NEXT: .LBB16_6: # %return 1552; CHECK-NEXT: retq 1553; 1554; NOOPT-LABEL: bt_order_by_weight: 1555; NOOPT: # %bb.0: # %entry 1556; NOOPT-NEXT: pushq %rax 1557; NOOPT-NEXT: .cfi_def_cfa_offset 16 1558; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1559; NOOPT-NEXT: testl %edi, %edi 1560; NOOPT-NEXT: je .LBB16_1 1561; NOOPT-NEXT: jmp .LBB16_5 1562; NOOPT-NEXT: .LBB16_5: # %entry 1563; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1564; NOOPT-NEXT: subl $1, %eax 1565; NOOPT-NEXT: je .LBB16_2 1566; NOOPT-NEXT: jmp .LBB16_6 1567; NOOPT-NEXT: .LBB16_6: # %entry 1568; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1569; NOOPT-NEXT: subl $2, %eax 1570; NOOPT-NEXT: je .LBB16_3 1571; NOOPT-NEXT: jmp .LBB16_7 1572; NOOPT-NEXT: .LBB16_7: # %entry 1573; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1574; NOOPT-NEXT: subl $3, %eax 1575; NOOPT-NEXT: je .LBB16_1 1576; NOOPT-NEXT: jmp .LBB16_8 1577; NOOPT-NEXT: .LBB16_8: # %entry 1578; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1579; NOOPT-NEXT: subl $4, %eax 1580; NOOPT-NEXT: je .LBB16_2 1581; NOOPT-NEXT: jmp .LBB16_9 1582; NOOPT-NEXT: .LBB16_9: # %entry 1583; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1584; NOOPT-NEXT: subl $5, %eax 1585; NOOPT-NEXT: je .LBB16_3 1586; NOOPT-NEXT: jmp .LBB16_10 1587; NOOPT-NEXT: .LBB16_10: # %entry 1588; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1589; NOOPT-NEXT: subl $6, %eax 1590; NOOPT-NEXT: je .LBB16_1 1591; NOOPT-NEXT: jmp .LBB16_11 1592; NOOPT-NEXT: .LBB16_11: # %entry 1593; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1594; NOOPT-NEXT: subl $7, %eax 1595; NOOPT-NEXT: je .LBB16_2 1596; NOOPT-NEXT: jmp .LBB16_12 1597; NOOPT-NEXT: .LBB16_12: # %entry 1598; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1599; NOOPT-NEXT: addl $-8, %eax 1600; NOOPT-NEXT: subl $2, %eax 1601; NOOPT-NEXT: jb .LBB16_3 1602; NOOPT-NEXT: jmp .LBB16_4 1603; NOOPT-NEXT: .LBB16_1: # %bb0 1604; NOOPT-NEXT: xorl %edi, %edi 1605; NOOPT-NEXT: callq g@PLT 1606; NOOPT-NEXT: jmp .LBB16_4 1607; NOOPT-NEXT: .LBB16_2: # %bb1 1608; NOOPT-NEXT: movl $1, %edi 1609; NOOPT-NEXT: callq g@PLT 1610; NOOPT-NEXT: jmp .LBB16_4 1611; NOOPT-NEXT: .LBB16_3: # %bb2 1612; NOOPT-NEXT: movl $2, %edi 1613; NOOPT-NEXT: callq g@PLT 1614; NOOPT-NEXT: .LBB16_4: # %return 1615; NOOPT-NEXT: popq %rax 1616; NOOPT-NEXT: .cfi_def_cfa_offset 8 1617; NOOPT-NEXT: retq 1618entry: 1619 switch i32 %x, label %return [ 1620 i32 0, label %bb0 1621 i32 3, label %bb0 1622 i32 6, label %bb0 1623 i32 1, label %bb1 1624 i32 4, label %bb1 1625 i32 7, label %bb1 1626 i32 2, label %bb2 1627 i32 5, label %bb2 1628 i32 8, label %bb2 1629 i32 9, label %bb2 1630 ], !prof !1 1631bb0: tail call void @g(i32 0) br label %return 1632bb1: tail call void @g(i32 1) br label %return 1633bb2: tail call void @g(i32 2) br label %return 1634return: ret void 1635} 1636 1637!1 = !{!"branch_weights", 1638 ; Default: 1639 i32 1, 1640 ; Cases 0,3,6: 1641 i32 0, i32 0, i32 20, 1642 ; Cases 1,4,7: 1643 i32 4294967295, i32 2, i32 4294967295, 1644 ; Cases 2,5,8,9: 1645 i32 0, i32 0, i32 0, i32 20} 1646 1647 1648; Case 200 has the highest weight and should come first. 100 and 300 have the 1649; same weight, but 300 goes to the 'next' block, so should be last. 1650define void @order_by_weight_and_fallthrough(i32 %x) { 1651; CHECK-LABEL: order_by_weight_and_fallthrough: 1652; CHECK: # %bb.0: # %entry 1653; CHECK-NEXT: cmpl $200, %edi 1654; CHECK-NEXT: jne .LBB17_1 1655; CHECK-NEXT: .LBB17_3: # %bb0 1656; CHECK-NEXT: xorl %edi, %edi 1657; CHECK-NEXT: jmp g@PLT # TAILCALL 1658; CHECK-NEXT: .LBB17_1: # %entry 1659; CHECK-NEXT: cmpl $100, %edi 1660; CHECK-NEXT: je .LBB17_4 1661; CHECK-NEXT: # %bb.2: # %entry 1662; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C 1663; CHECK-NEXT: je .LBB17_3 1664; CHECK-NEXT: # %bb.5: # %return 1665; CHECK-NEXT: retq 1666; CHECK-NEXT: .LBB17_4: # %bb1 1667; CHECK-NEXT: movl $1, %edi 1668; CHECK-NEXT: jmp g@PLT # TAILCALL 1669; 1670; NOOPT-LABEL: order_by_weight_and_fallthrough: 1671; NOOPT: # %bb.0: # %entry 1672; NOOPT-NEXT: pushq %rax 1673; NOOPT-NEXT: .cfi_def_cfa_offset 16 1674; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1675; NOOPT-NEXT: subl $100, %edi 1676; NOOPT-NEXT: je .LBB17_2 1677; NOOPT-NEXT: jmp .LBB17_4 1678; NOOPT-NEXT: .LBB17_4: # %entry 1679; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1680; NOOPT-NEXT: subl $200, %eax 1681; NOOPT-NEXT: je .LBB17_1 1682; NOOPT-NEXT: jmp .LBB17_5 1683; NOOPT-NEXT: .LBB17_5: # %entry 1684; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1685; NOOPT-NEXT: subl $300, %eax # imm = 0x12C 1686; NOOPT-NEXT: jne .LBB17_3 1687; NOOPT-NEXT: jmp .LBB17_1 1688; NOOPT-NEXT: .LBB17_1: # %bb0 1689; NOOPT-NEXT: xorl %edi, %edi 1690; NOOPT-NEXT: callq g@PLT 1691; NOOPT-NEXT: jmp .LBB17_3 1692; NOOPT-NEXT: .LBB17_2: # %bb1 1693; NOOPT-NEXT: movl $1, %edi 1694; NOOPT-NEXT: callq g@PLT 1695; NOOPT-NEXT: .LBB17_3: # %return 1696; NOOPT-NEXT: popq %rax 1697; NOOPT-NEXT: .cfi_def_cfa_offset 8 1698; NOOPT-NEXT: retq 1699entry: 1700 switch i32 %x, label %return [ 1701 i32 100, label %bb1 1702 i32 200, label %bb0 1703 i32 300, label %bb0 1704 ], !prof !2 1705bb0: tail call void @g(i32 0) br label %return 1706bb1: tail call void @g(i32 1) br label %return 1707return: ret void 1708} 1709 1710!2 = !{!"branch_weights", 1711 ; Default: 1712 i32 1, 1713 ; Case 100: 1714 i32 10, 1715 ; Case 200: 1716 i32 1000, 1717 ; Case 300: 1718 i32 10} 1719 1720 1721; Make sure to pick a pivot in the middle also with zero-weight cases. 1722define void @zero_weight_tree(i32 %x) { 1723; CHECK-LABEL: zero_weight_tree: 1724; CHECK: # %bb.0: # %entry 1725; CHECK-NEXT: cmpl $29, %edi 1726; CHECK-NEXT: jg .LBB18_5 1727; CHECK-NEXT: # %bb.1: # %entry 1728; CHECK-NEXT: testl %edi, %edi 1729; CHECK-NEXT: jne .LBB18_2 1730; CHECK-NEXT: # %bb.9: # %bb0 1731; CHECK-NEXT: xorl %edi, %edi 1732; CHECK-NEXT: jmp g@PLT # TAILCALL 1733; CHECK-NEXT: .LBB18_5: # %entry 1734; CHECK-NEXT: cmpl $50, %edi 1735; CHECK-NEXT: jne .LBB18_6 1736; CHECK-NEXT: # %bb.12: # %bb5 1737; CHECK-NEXT: movl $5, %edi 1738; CHECK-NEXT: jmp g@PLT # TAILCALL 1739; CHECK-NEXT: .LBB18_2: # %entry 1740; CHECK-NEXT: cmpl $10, %edi 1741; CHECK-NEXT: je .LBB18_10 1742; CHECK-NEXT: # %bb.3: # %entry 1743; CHECK-NEXT: cmpl $20, %edi 1744; CHECK-NEXT: jne .LBB18_13 1745; CHECK-NEXT: # %bb.4: # %bb2 1746; CHECK-NEXT: movl $2, %edi 1747; CHECK-NEXT: jmp g@PLT # TAILCALL 1748; CHECK-NEXT: .LBB18_6: # %entry 1749; CHECK-NEXT: cmpl $30, %edi 1750; CHECK-NEXT: je .LBB18_11 1751; CHECK-NEXT: # %bb.7: # %entry 1752; CHECK-NEXT: cmpl $40, %edi 1753; CHECK-NEXT: je .LBB18_8 1754; CHECK-NEXT: .LBB18_13: # %return 1755; CHECK-NEXT: retq 1756; CHECK-NEXT: .LBB18_10: # %bb1 1757; CHECK-NEXT: movl $1, %edi 1758; CHECK-NEXT: jmp g@PLT # TAILCALL 1759; CHECK-NEXT: .LBB18_11: # %bb3 1760; CHECK-NEXT: movl $3, %edi 1761; CHECK-NEXT: jmp g@PLT # TAILCALL 1762; CHECK-NEXT: .LBB18_8: # %bb4 1763; CHECK-NEXT: movl $4, %edi 1764; CHECK-NEXT: jmp g@PLT # TAILCALL 1765; 1766; NOOPT-LABEL: zero_weight_tree: 1767; NOOPT: # %bb.0: # %entry 1768; NOOPT-NEXT: pushq %rax 1769; NOOPT-NEXT: .cfi_def_cfa_offset 16 1770; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1771; NOOPT-NEXT: testl %edi, %edi 1772; NOOPT-NEXT: je .LBB18_1 1773; NOOPT-NEXT: jmp .LBB18_8 1774; NOOPT-NEXT: .LBB18_8: # %entry 1775; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1776; NOOPT-NEXT: subl $10, %eax 1777; NOOPT-NEXT: je .LBB18_2 1778; NOOPT-NEXT: jmp .LBB18_9 1779; NOOPT-NEXT: .LBB18_9: # %entry 1780; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1781; NOOPT-NEXT: subl $20, %eax 1782; NOOPT-NEXT: je .LBB18_3 1783; NOOPT-NEXT: jmp .LBB18_10 1784; NOOPT-NEXT: .LBB18_10: # %entry 1785; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1786; NOOPT-NEXT: subl $30, %eax 1787; NOOPT-NEXT: je .LBB18_4 1788; NOOPT-NEXT: jmp .LBB18_11 1789; NOOPT-NEXT: .LBB18_11: # %entry 1790; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1791; NOOPT-NEXT: subl $40, %eax 1792; NOOPT-NEXT: je .LBB18_5 1793; NOOPT-NEXT: jmp .LBB18_12 1794; NOOPT-NEXT: .LBB18_12: # %entry 1795; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1796; NOOPT-NEXT: subl $50, %eax 1797; NOOPT-NEXT: je .LBB18_6 1798; NOOPT-NEXT: jmp .LBB18_7 1799; NOOPT-NEXT: .LBB18_1: # %bb0 1800; NOOPT-NEXT: xorl %edi, %edi 1801; NOOPT-NEXT: callq g@PLT 1802; NOOPT-NEXT: jmp .LBB18_7 1803; NOOPT-NEXT: .LBB18_2: # %bb1 1804; NOOPT-NEXT: movl $1, %edi 1805; NOOPT-NEXT: callq g@PLT 1806; NOOPT-NEXT: jmp .LBB18_7 1807; NOOPT-NEXT: .LBB18_3: # %bb2 1808; NOOPT-NEXT: movl $2, %edi 1809; NOOPT-NEXT: callq g@PLT 1810; NOOPT-NEXT: jmp .LBB18_7 1811; NOOPT-NEXT: .LBB18_4: # %bb3 1812; NOOPT-NEXT: movl $3, %edi 1813; NOOPT-NEXT: callq g@PLT 1814; NOOPT-NEXT: jmp .LBB18_7 1815; NOOPT-NEXT: .LBB18_5: # %bb4 1816; NOOPT-NEXT: movl $4, %edi 1817; NOOPT-NEXT: callq g@PLT 1818; NOOPT-NEXT: jmp .LBB18_7 1819; NOOPT-NEXT: .LBB18_6: # %bb5 1820; NOOPT-NEXT: movl $5, %edi 1821; NOOPT-NEXT: callq g@PLT 1822; NOOPT-NEXT: .LBB18_7: # %return 1823; NOOPT-NEXT: popq %rax 1824; NOOPT-NEXT: .cfi_def_cfa_offset 8 1825; NOOPT-NEXT: retq 1826entry: 1827 switch i32 %x, label %return [ 1828 i32 0, label %bb0 1829 i32 10, label %bb1 1830 i32 20, label %bb2 1831 i32 30, label %bb3 1832 i32 40, label %bb4 1833 i32 50, label %bb5 1834 ], !prof !3 1835bb0: tail call void @g(i32 0) br label %return 1836bb1: tail call void @g(i32 1) br label %return 1837bb2: tail call void @g(i32 2) br label %return 1838bb3: tail call void @g(i32 3) br label %return 1839bb4: tail call void @g(i32 4) br label %return 1840bb5: tail call void @g(i32 5) br label %return 1841return: ret void 1842} 1843 1844!3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10} 1845 1846 1847; Without branch probabilities, the pivot would be 40, since that would yield 1848; equal-sized sub-trees. When taking weights into account, case 70 becomes the 1849; pivot. Since there is room for 3 cases in a leaf, cases 50 and 60 are also 1850; included in the right-hand side because that doesn't reduce their rank. 1851define void @left_leaning_weight_balanced_tree(i32 %x) { 1852; CHECK-LABEL: left_leaning_weight_balanced_tree: 1853; CHECK: # %bb.0: # %entry 1854; CHECK-NEXT: cmpl $49, %edi 1855; CHECK-NEXT: jle .LBB19_1 1856; CHECK-NEXT: # %bb.11: # %entry 1857; CHECK-NEXT: cmpl $70, %edi 1858; CHECK-NEXT: jne .LBB19_12 1859; CHECK-NEXT: .LBB19_14: # %bb6 1860; CHECK-NEXT: movl $6, %edi 1861; CHECK-NEXT: jmp g@PLT # TAILCALL 1862; CHECK-NEXT: .LBB19_1: # %entry 1863; CHECK-NEXT: cmpl $9, %edi 1864; CHECK-NEXT: jg .LBB19_4 1865; CHECK-NEXT: # %bb.2: # %entry 1866; CHECK-NEXT: testl %edi, %edi 1867; CHECK-NEXT: jne .LBB19_18 1868; CHECK-NEXT: # %bb.3: # %bb0 1869; CHECK-NEXT: xorl %edi, %edi 1870; CHECK-NEXT: jmp g@PLT # TAILCALL 1871; CHECK-NEXT: .LBB19_4: # %entry 1872; CHECK-NEXT: cmpl $29, %edi 1873; CHECK-NEXT: jg .LBB19_8 1874; CHECK-NEXT: # %bb.5: # %entry 1875; CHECK-NEXT: cmpl $10, %edi 1876; CHECK-NEXT: je .LBB19_15 1877; CHECK-NEXT: # %bb.6: # %entry 1878; CHECK-NEXT: cmpl $20, %edi 1879; CHECK-NEXT: jne .LBB19_18 1880; CHECK-NEXT: # %bb.7: # %bb2 1881; CHECK-NEXT: movl $2, %edi 1882; CHECK-NEXT: jmp g@PLT # TAILCALL 1883; CHECK-NEXT: .LBB19_12: # %entry 1884; CHECK-NEXT: cmpl $50, %edi 1885; CHECK-NEXT: je .LBB19_17 1886; CHECK-NEXT: # %bb.13: # %entry 1887; CHECK-NEXT: cmpl $60, %edi 1888; CHECK-NEXT: je .LBB19_14 1889; CHECK-NEXT: jmp .LBB19_18 1890; CHECK-NEXT: .LBB19_8: # %entry 1891; CHECK-NEXT: cmpl $30, %edi 1892; CHECK-NEXT: je .LBB19_16 1893; CHECK-NEXT: # %bb.9: # %entry 1894; CHECK-NEXT: cmpl $40, %edi 1895; CHECK-NEXT: jne .LBB19_18 1896; CHECK-NEXT: # %bb.10: # %bb4 1897; CHECK-NEXT: movl $4, %edi 1898; CHECK-NEXT: jmp g@PLT # TAILCALL 1899; CHECK-NEXT: .LBB19_15: # %bb1 1900; CHECK-NEXT: movl $1, %edi 1901; CHECK-NEXT: jmp g@PLT # TAILCALL 1902; CHECK-NEXT: .LBB19_16: # %bb3 1903; CHECK-NEXT: movl $3, %edi 1904; CHECK-NEXT: jmp g@PLT # TAILCALL 1905; CHECK-NEXT: .LBB19_18: # %return 1906; CHECK-NEXT: retq 1907; CHECK-NEXT: .LBB19_17: # %bb5 1908; CHECK-NEXT: movl $5, %edi 1909; CHECK-NEXT: jmp g@PLT # TAILCALL 1910; 1911; NOOPT-LABEL: left_leaning_weight_balanced_tree: 1912; NOOPT: # %bb.0: # %entry 1913; NOOPT-NEXT: pushq %rax 1914; NOOPT-NEXT: .cfi_def_cfa_offset 16 1915; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 1916; NOOPT-NEXT: testl %edi, %edi 1917; NOOPT-NEXT: je .LBB19_1 1918; NOOPT-NEXT: jmp .LBB19_9 1919; NOOPT-NEXT: .LBB19_9: # %entry 1920; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1921; NOOPT-NEXT: subl $10, %eax 1922; NOOPT-NEXT: je .LBB19_2 1923; NOOPT-NEXT: jmp .LBB19_10 1924; NOOPT-NEXT: .LBB19_10: # %entry 1925; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1926; NOOPT-NEXT: subl $20, %eax 1927; NOOPT-NEXT: je .LBB19_3 1928; NOOPT-NEXT: jmp .LBB19_11 1929; NOOPT-NEXT: .LBB19_11: # %entry 1930; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1931; NOOPT-NEXT: subl $30, %eax 1932; NOOPT-NEXT: je .LBB19_4 1933; NOOPT-NEXT: jmp .LBB19_12 1934; NOOPT-NEXT: .LBB19_12: # %entry 1935; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1936; NOOPT-NEXT: subl $40, %eax 1937; NOOPT-NEXT: je .LBB19_5 1938; NOOPT-NEXT: jmp .LBB19_13 1939; NOOPT-NEXT: .LBB19_13: # %entry 1940; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1941; NOOPT-NEXT: subl $50, %eax 1942; NOOPT-NEXT: je .LBB19_6 1943; NOOPT-NEXT: jmp .LBB19_14 1944; NOOPT-NEXT: .LBB19_14: # %entry 1945; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1946; NOOPT-NEXT: subl $60, %eax 1947; NOOPT-NEXT: je .LBB19_7 1948; NOOPT-NEXT: jmp .LBB19_15 1949; NOOPT-NEXT: .LBB19_15: # %entry 1950; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 1951; NOOPT-NEXT: subl $70, %eax 1952; NOOPT-NEXT: je .LBB19_7 1953; NOOPT-NEXT: jmp .LBB19_8 1954; NOOPT-NEXT: .LBB19_1: # %bb0 1955; NOOPT-NEXT: xorl %edi, %edi 1956; NOOPT-NEXT: callq g@PLT 1957; NOOPT-NEXT: jmp .LBB19_8 1958; NOOPT-NEXT: .LBB19_2: # %bb1 1959; NOOPT-NEXT: movl $1, %edi 1960; NOOPT-NEXT: callq g@PLT 1961; NOOPT-NEXT: jmp .LBB19_8 1962; NOOPT-NEXT: .LBB19_3: # %bb2 1963; NOOPT-NEXT: movl $2, %edi 1964; NOOPT-NEXT: callq g@PLT 1965; NOOPT-NEXT: jmp .LBB19_8 1966; NOOPT-NEXT: .LBB19_4: # %bb3 1967; NOOPT-NEXT: movl $3, %edi 1968; NOOPT-NEXT: callq g@PLT 1969; NOOPT-NEXT: jmp .LBB19_8 1970; NOOPT-NEXT: .LBB19_5: # %bb4 1971; NOOPT-NEXT: movl $4, %edi 1972; NOOPT-NEXT: callq g@PLT 1973; NOOPT-NEXT: jmp .LBB19_8 1974; NOOPT-NEXT: .LBB19_6: # %bb5 1975; NOOPT-NEXT: movl $5, %edi 1976; NOOPT-NEXT: callq g@PLT 1977; NOOPT-NEXT: jmp .LBB19_8 1978; NOOPT-NEXT: .LBB19_7: # %bb6 1979; NOOPT-NEXT: movl $6, %edi 1980; NOOPT-NEXT: callq g@PLT 1981; NOOPT-NEXT: .LBB19_8: # %return 1982; NOOPT-NEXT: popq %rax 1983; NOOPT-NEXT: .cfi_def_cfa_offset 8 1984; NOOPT-NEXT: retq 1985entry: 1986 switch i32 %x, label %return [ 1987 i32 0, label %bb0 1988 i32 10, label %bb1 1989 i32 20, label %bb2 1990 i32 30, label %bb3 1991 i32 40, label %bb4 1992 i32 50, label %bb5 1993 i32 60, label %bb6 1994 i32 70, label %bb6 1995 ], !prof !4 1996bb0: tail call void @g(i32 0) br label %return 1997bb1: tail call void @g(i32 1) br label %return 1998bb2: tail call void @g(i32 2) br label %return 1999bb3: tail call void @g(i32 3) br label %return 2000bb4: tail call void @g(i32 4) br label %return 2001bb5: tail call void @g(i32 5) br label %return 2002bb6: tail call void @g(i32 6) br label %return 2003bb7: tail call void @g(i32 7) br label %return 2004return: ret void 2005} 2006 2007!4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1000} 2008 2009 2010; Same as the previous test, except case 50 has higher rank to the left than it 2011; would have on the right. Case 60 would have the same rank on both sides, so is 2012; moved into the leaf. 2013define void @left_leaning_weight_balanced_tree2(i32 %x) { 2014; CHECK-LABEL: left_leaning_weight_balanced_tree2: 2015; CHECK: # %bb.0: # %entry 2016; CHECK-NEXT: cmpl $59, %edi 2017; CHECK-NEXT: jle .LBB20_1 2018; CHECK-NEXT: # %bb.10: # %entry 2019; CHECK-NEXT: cmpl $70, %edi 2020; CHECK-NEXT: jne .LBB20_11 2021; CHECK-NEXT: .LBB20_12: # %bb6 2022; CHECK-NEXT: movl $6, %edi 2023; CHECK-NEXT: jmp g@PLT # TAILCALL 2024; CHECK-NEXT: .LBB20_1: # %entry 2025; CHECK-NEXT: cmpl $29, %edi 2026; CHECK-NEXT: jle .LBB20_2 2027; CHECK-NEXT: # %bb.6: # %entry 2028; CHECK-NEXT: cmpl $50, %edi 2029; CHECK-NEXT: jne .LBB20_7 2030; CHECK-NEXT: # %bb.16: # %bb5 2031; CHECK-NEXT: movl $5, %edi 2032; CHECK-NEXT: jmp g@PLT # TAILCALL 2033; CHECK-NEXT: .LBB20_11: # %entry 2034; CHECK-NEXT: cmpl $60, %edi 2035; CHECK-NEXT: je .LBB20_12 2036; CHECK-NEXT: jmp .LBB20_17 2037; CHECK-NEXT: .LBB20_2: # %entry 2038; CHECK-NEXT: testl %edi, %edi 2039; CHECK-NEXT: jne .LBB20_3 2040; CHECK-NEXT: # %bb.13: # %bb0 2041; CHECK-NEXT: xorl %edi, %edi 2042; CHECK-NEXT: jmp g@PLT # TAILCALL 2043; CHECK-NEXT: .LBB20_3: # %entry 2044; CHECK-NEXT: cmpl $10, %edi 2045; CHECK-NEXT: je .LBB20_14 2046; CHECK-NEXT: # %bb.4: # %entry 2047; CHECK-NEXT: cmpl $20, %edi 2048; CHECK-NEXT: jne .LBB20_17 2049; CHECK-NEXT: # %bb.5: # %bb2 2050; CHECK-NEXT: movl $2, %edi 2051; CHECK-NEXT: jmp g@PLT # TAILCALL 2052; CHECK-NEXT: .LBB20_7: # %entry 2053; CHECK-NEXT: cmpl $30, %edi 2054; CHECK-NEXT: je .LBB20_15 2055; CHECK-NEXT: # %bb.8: # %entry 2056; CHECK-NEXT: cmpl $40, %edi 2057; CHECK-NEXT: jne .LBB20_17 2058; CHECK-NEXT: # %bb.9: # %bb4 2059; CHECK-NEXT: movl $4, %edi 2060; CHECK-NEXT: jmp g@PLT # TAILCALL 2061; CHECK-NEXT: .LBB20_14: # %bb1 2062; CHECK-NEXT: movl $1, %edi 2063; CHECK-NEXT: jmp g@PLT # TAILCALL 2064; CHECK-NEXT: .LBB20_15: # %bb3 2065; CHECK-NEXT: movl $3, %edi 2066; CHECK-NEXT: jmp g@PLT # TAILCALL 2067; CHECK-NEXT: .LBB20_17: # %return 2068; CHECK-NEXT: retq 2069; 2070; NOOPT-LABEL: left_leaning_weight_balanced_tree2: 2071; NOOPT: # %bb.0: # %entry 2072; NOOPT-NEXT: pushq %rax 2073; NOOPT-NEXT: .cfi_def_cfa_offset 16 2074; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2075; NOOPT-NEXT: testl %edi, %edi 2076; NOOPT-NEXT: je .LBB20_1 2077; NOOPT-NEXT: jmp .LBB20_9 2078; NOOPT-NEXT: .LBB20_9: # %entry 2079; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2080; NOOPT-NEXT: subl $10, %eax 2081; NOOPT-NEXT: je .LBB20_2 2082; NOOPT-NEXT: jmp .LBB20_10 2083; NOOPT-NEXT: .LBB20_10: # %entry 2084; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2085; NOOPT-NEXT: subl $20, %eax 2086; NOOPT-NEXT: je .LBB20_3 2087; NOOPT-NEXT: jmp .LBB20_11 2088; NOOPT-NEXT: .LBB20_11: # %entry 2089; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2090; NOOPT-NEXT: subl $30, %eax 2091; NOOPT-NEXT: je .LBB20_4 2092; NOOPT-NEXT: jmp .LBB20_12 2093; NOOPT-NEXT: .LBB20_12: # %entry 2094; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2095; NOOPT-NEXT: subl $40, %eax 2096; NOOPT-NEXT: je .LBB20_5 2097; NOOPT-NEXT: jmp .LBB20_13 2098; NOOPT-NEXT: .LBB20_13: # %entry 2099; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2100; NOOPT-NEXT: subl $50, %eax 2101; NOOPT-NEXT: je .LBB20_6 2102; NOOPT-NEXT: jmp .LBB20_14 2103; NOOPT-NEXT: .LBB20_14: # %entry 2104; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2105; NOOPT-NEXT: subl $60, %eax 2106; NOOPT-NEXT: je .LBB20_7 2107; NOOPT-NEXT: jmp .LBB20_15 2108; NOOPT-NEXT: .LBB20_15: # %entry 2109; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2110; NOOPT-NEXT: subl $70, %eax 2111; NOOPT-NEXT: je .LBB20_7 2112; NOOPT-NEXT: jmp .LBB20_8 2113; NOOPT-NEXT: .LBB20_1: # %bb0 2114; NOOPT-NEXT: xorl %edi, %edi 2115; NOOPT-NEXT: callq g@PLT 2116; NOOPT-NEXT: jmp .LBB20_8 2117; NOOPT-NEXT: .LBB20_2: # %bb1 2118; NOOPT-NEXT: movl $1, %edi 2119; NOOPT-NEXT: callq g@PLT 2120; NOOPT-NEXT: jmp .LBB20_8 2121; NOOPT-NEXT: .LBB20_3: # %bb2 2122; NOOPT-NEXT: movl $2, %edi 2123; NOOPT-NEXT: callq g@PLT 2124; NOOPT-NEXT: jmp .LBB20_8 2125; NOOPT-NEXT: .LBB20_4: # %bb3 2126; NOOPT-NEXT: movl $3, %edi 2127; NOOPT-NEXT: callq g@PLT 2128; NOOPT-NEXT: jmp .LBB20_8 2129; NOOPT-NEXT: .LBB20_5: # %bb4 2130; NOOPT-NEXT: movl $4, %edi 2131; NOOPT-NEXT: callq g@PLT 2132; NOOPT-NEXT: jmp .LBB20_8 2133; NOOPT-NEXT: .LBB20_6: # %bb5 2134; NOOPT-NEXT: movl $5, %edi 2135; NOOPT-NEXT: callq g@PLT 2136; NOOPT-NEXT: jmp .LBB20_8 2137; NOOPT-NEXT: .LBB20_7: # %bb6 2138; NOOPT-NEXT: movl $6, %edi 2139; NOOPT-NEXT: callq g@PLT 2140; NOOPT-NEXT: .LBB20_8: # %return 2141; NOOPT-NEXT: popq %rax 2142; NOOPT-NEXT: .cfi_def_cfa_offset 8 2143; NOOPT-NEXT: retq 2144entry: 2145 switch i32 %x, label %return [ 2146 i32 0, label %bb0 2147 i32 10, label %bb1 2148 i32 20, label %bb2 2149 i32 30, label %bb3 2150 i32 40, label %bb4 2151 i32 50, label %bb5 2152 i32 60, label %bb6 2153 i32 70, label %bb6 2154 ], !prof !5 2155bb0: tail call void @g(i32 0) br label %return 2156bb1: tail call void @g(i32 1) br label %return 2157bb2: tail call void @g(i32 2) br label %return 2158bb3: tail call void @g(i32 3) br label %return 2159bb4: tail call void @g(i32 4) br label %return 2160bb5: tail call void @g(i32 5) br label %return 2161bb6: tail call void @g(i32 6) br label %return 2162bb7: tail call void @g(i32 7) br label %return 2163return: ret void 2164} 2165 2166!5 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 90, i32 70, i32 1000} 2167 2168 2169; Analogous to left_leaning_weight_balanced_tree. 2170define void @right_leaning_weight_balanced_tree(i32 %x) { 2171; CHECK-LABEL: right_leaning_weight_balanced_tree: 2172; CHECK: # %bb.0: # %entry 2173; CHECK-NEXT: cmpl $19, %edi 2174; CHECK-NEXT: jg .LBB21_4 2175; CHECK-NEXT: # %bb.1: # %entry 2176; CHECK-NEXT: testl %edi, %edi 2177; CHECK-NEXT: jne .LBB21_2 2178; CHECK-NEXT: # %bb.13: # %bb0 2179; CHECK-NEXT: xorl %edi, %edi 2180; CHECK-NEXT: jmp g@PLT # TAILCALL 2181; CHECK-NEXT: .LBB21_4: # %entry 2182; CHECK-NEXT: cmpl $49, %edi 2183; CHECK-NEXT: jle .LBB21_5 2184; CHECK-NEXT: # %bb.9: # %entry 2185; CHECK-NEXT: cmpl $70, %edi 2186; CHECK-NEXT: jne .LBB21_10 2187; CHECK-NEXT: .LBB21_12: # %bb6 2188; CHECK-NEXT: movl $6, %edi 2189; CHECK-NEXT: jmp g@PLT # TAILCALL 2190; CHECK-NEXT: .LBB21_5: # %entry 2191; CHECK-NEXT: cmpl $20, %edi 2192; CHECK-NEXT: je .LBB21_14 2193; CHECK-NEXT: # %bb.6: # %entry 2194; CHECK-NEXT: cmpl $30, %edi 2195; CHECK-NEXT: je .LBB21_15 2196; CHECK-NEXT: # %bb.7: # %entry 2197; CHECK-NEXT: cmpl $40, %edi 2198; CHECK-NEXT: jne .LBB21_17 2199; CHECK-NEXT: # %bb.8: # %bb4 2200; CHECK-NEXT: movl $4, %edi 2201; CHECK-NEXT: jmp g@PLT # TAILCALL 2202; CHECK-NEXT: .LBB21_10: # %entry 2203; CHECK-NEXT: cmpl $50, %edi 2204; CHECK-NEXT: je .LBB21_16 2205; CHECK-NEXT: # %bb.11: # %entry 2206; CHECK-NEXT: cmpl $60, %edi 2207; CHECK-NEXT: je .LBB21_12 2208; CHECK-NEXT: jmp .LBB21_17 2209; CHECK-NEXT: .LBB21_14: # %bb2 2210; CHECK-NEXT: movl $2, %edi 2211; CHECK-NEXT: jmp g@PLT # TAILCALL 2212; CHECK-NEXT: .LBB21_15: # %bb3 2213; CHECK-NEXT: movl $3, %edi 2214; CHECK-NEXT: jmp g@PLT # TAILCALL 2215; CHECK-NEXT: .LBB21_2: # %entry 2216; CHECK-NEXT: cmpl $10, %edi 2217; CHECK-NEXT: jne .LBB21_17 2218; CHECK-NEXT: # %bb.3: # %bb1 2219; CHECK-NEXT: movl $1, %edi 2220; CHECK-NEXT: jmp g@PLT # TAILCALL 2221; CHECK-NEXT: .LBB21_17: # %return 2222; CHECK-NEXT: retq 2223; CHECK-NEXT: .LBB21_16: # %bb5 2224; CHECK-NEXT: movl $5, %edi 2225; CHECK-NEXT: jmp g@PLT # TAILCALL 2226; 2227; NOOPT-LABEL: right_leaning_weight_balanced_tree: 2228; NOOPT: # %bb.0: # %entry 2229; NOOPT-NEXT: pushq %rax 2230; NOOPT-NEXT: .cfi_def_cfa_offset 16 2231; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2232; NOOPT-NEXT: testl %edi, %edi 2233; NOOPT-NEXT: je .LBB21_1 2234; NOOPT-NEXT: jmp .LBB21_9 2235; NOOPT-NEXT: .LBB21_9: # %entry 2236; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2237; NOOPT-NEXT: subl $10, %eax 2238; NOOPT-NEXT: je .LBB21_2 2239; NOOPT-NEXT: jmp .LBB21_10 2240; NOOPT-NEXT: .LBB21_10: # %entry 2241; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2242; NOOPT-NEXT: subl $20, %eax 2243; NOOPT-NEXT: je .LBB21_3 2244; NOOPT-NEXT: jmp .LBB21_11 2245; NOOPT-NEXT: .LBB21_11: # %entry 2246; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2247; NOOPT-NEXT: subl $30, %eax 2248; NOOPT-NEXT: je .LBB21_4 2249; NOOPT-NEXT: jmp .LBB21_12 2250; NOOPT-NEXT: .LBB21_12: # %entry 2251; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2252; NOOPT-NEXT: subl $40, %eax 2253; NOOPT-NEXT: je .LBB21_5 2254; NOOPT-NEXT: jmp .LBB21_13 2255; NOOPT-NEXT: .LBB21_13: # %entry 2256; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2257; NOOPT-NEXT: subl $50, %eax 2258; NOOPT-NEXT: je .LBB21_6 2259; NOOPT-NEXT: jmp .LBB21_14 2260; NOOPT-NEXT: .LBB21_14: # %entry 2261; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2262; NOOPT-NEXT: subl $60, %eax 2263; NOOPT-NEXT: je .LBB21_7 2264; NOOPT-NEXT: jmp .LBB21_15 2265; NOOPT-NEXT: .LBB21_15: # %entry 2266; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2267; NOOPT-NEXT: subl $70, %eax 2268; NOOPT-NEXT: je .LBB21_7 2269; NOOPT-NEXT: jmp .LBB21_8 2270; NOOPT-NEXT: .LBB21_1: # %bb0 2271; NOOPT-NEXT: xorl %edi, %edi 2272; NOOPT-NEXT: callq g@PLT 2273; NOOPT-NEXT: jmp .LBB21_8 2274; NOOPT-NEXT: .LBB21_2: # %bb1 2275; NOOPT-NEXT: movl $1, %edi 2276; NOOPT-NEXT: callq g@PLT 2277; NOOPT-NEXT: jmp .LBB21_8 2278; NOOPT-NEXT: .LBB21_3: # %bb2 2279; NOOPT-NEXT: movl $2, %edi 2280; NOOPT-NEXT: callq g@PLT 2281; NOOPT-NEXT: jmp .LBB21_8 2282; NOOPT-NEXT: .LBB21_4: # %bb3 2283; NOOPT-NEXT: movl $3, %edi 2284; NOOPT-NEXT: callq g@PLT 2285; NOOPT-NEXT: jmp .LBB21_8 2286; NOOPT-NEXT: .LBB21_5: # %bb4 2287; NOOPT-NEXT: movl $4, %edi 2288; NOOPT-NEXT: callq g@PLT 2289; NOOPT-NEXT: jmp .LBB21_8 2290; NOOPT-NEXT: .LBB21_6: # %bb5 2291; NOOPT-NEXT: movl $5, %edi 2292; NOOPT-NEXT: callq g@PLT 2293; NOOPT-NEXT: jmp .LBB21_8 2294; NOOPT-NEXT: .LBB21_7: # %bb6 2295; NOOPT-NEXT: movl $6, %edi 2296; NOOPT-NEXT: callq g@PLT 2297; NOOPT-NEXT: .LBB21_8: # %return 2298; NOOPT-NEXT: popq %rax 2299; NOOPT-NEXT: .cfi_def_cfa_offset 8 2300; NOOPT-NEXT: retq 2301entry: 2302 switch i32 %x, label %return [ 2303 i32 0, label %bb0 2304 i32 10, label %bb1 2305 i32 20, label %bb2 2306 i32 30, label %bb3 2307 i32 40, label %bb4 2308 i32 50, label %bb5 2309 i32 60, label %bb6 2310 i32 70, label %bb6 2311 ], !prof !6 2312bb0: tail call void @g(i32 0) br label %return 2313bb1: tail call void @g(i32 1) br label %return 2314bb2: tail call void @g(i32 2) br label %return 2315bb3: tail call void @g(i32 3) br label %return 2316bb4: tail call void @g(i32 4) br label %return 2317bb5: tail call void @g(i32 5) br label %return 2318bb6: tail call void @g(i32 6) br label %return 2319bb7: tail call void @g(i32 7) br label %return 2320return: ret void 2321} 2322 2323!6 = !{!"branch_weights", i32 1, i32 1000, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 10} 2324 2325 2326; If the tree were balanced based on number of clusters, {0-3,100} would go on 2327; the left and {200,300} on the right. However, the jump table weights as much 2328; as its components, so 100 is selected as the pivot. 2329define void @jump_table_affects_balance(i32 %x) { 2330; CHECK-LABEL: jump_table_affects_balance: 2331; CHECK: # %bb.0: # %entry 2332; CHECK-NEXT: cmpl $99, %edi 2333; CHECK-NEXT: jg .LBB22_3 2334; CHECK-NEXT: # %bb.1: # %entry 2335; CHECK-NEXT: cmpl $3, %edi 2336; CHECK-NEXT: ja .LBB22_10 2337; CHECK-NEXT: # %bb.2: # %entry 2338; CHECK-NEXT: movl %edi, %eax 2339; CHECK-NEXT: jmpq *.LJTI22_0(,%rax,8) 2340; CHECK-NEXT: .LBB22_9: # %bb3 2341; CHECK-NEXT: movl $3, %edi 2342; CHECK-NEXT: jmp g@PLT # TAILCALL 2343; CHECK-NEXT: .LBB22_3: # %entry 2344; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C 2345; CHECK-NEXT: je .LBB22_8 2346; CHECK-NEXT: # %bb.4: # %entry 2347; CHECK-NEXT: cmpl $200, %edi 2348; CHECK-NEXT: je .LBB22_7 2349; CHECK-NEXT: # %bb.5: # %entry 2350; CHECK-NEXT: cmpl $100, %edi 2351; CHECK-NEXT: jne .LBB22_10 2352; CHECK-NEXT: .LBB22_6: # %bb0 2353; CHECK-NEXT: xorl %edi, %edi 2354; CHECK-NEXT: jmp g@PLT # TAILCALL 2355; CHECK-NEXT: .LBB22_8: # %bb2 2356; CHECK-NEXT: movl $2, %edi 2357; CHECK-NEXT: jmp g@PLT # TAILCALL 2358; CHECK-NEXT: .LBB22_7: # %bb1 2359; CHECK-NEXT: movl $1, %edi 2360; CHECK-NEXT: jmp g@PLT # TAILCALL 2361; CHECK-NEXT: .LBB22_10: # %return 2362; CHECK-NEXT: retq 2363; 2364; NOOPT-LABEL: jump_table_affects_balance: 2365; NOOPT: # %bb.0: # %entry 2366; NOOPT-NEXT: pushq %rax 2367; NOOPT-NEXT: .cfi_def_cfa_offset 16 2368; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2369; NOOPT-NEXT: testl %edi, %edi 2370; NOOPT-NEXT: je .LBB22_1 2371; NOOPT-NEXT: jmp .LBB22_6 2372; NOOPT-NEXT: .LBB22_6: # %entry 2373; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2374; NOOPT-NEXT: subl $1, %eax 2375; NOOPT-NEXT: je .LBB22_2 2376; NOOPT-NEXT: jmp .LBB22_7 2377; NOOPT-NEXT: .LBB22_7: # %entry 2378; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2379; NOOPT-NEXT: subl $2, %eax 2380; NOOPT-NEXT: je .LBB22_3 2381; NOOPT-NEXT: jmp .LBB22_8 2382; NOOPT-NEXT: .LBB22_8: # %entry 2383; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2384; NOOPT-NEXT: subl $3, %eax 2385; NOOPT-NEXT: je .LBB22_4 2386; NOOPT-NEXT: jmp .LBB22_9 2387; NOOPT-NEXT: .LBB22_9: # %entry 2388; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2389; NOOPT-NEXT: subl $100, %eax 2390; NOOPT-NEXT: je .LBB22_1 2391; NOOPT-NEXT: jmp .LBB22_10 2392; NOOPT-NEXT: .LBB22_10: # %entry 2393; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2394; NOOPT-NEXT: subl $200, %eax 2395; NOOPT-NEXT: je .LBB22_2 2396; NOOPT-NEXT: jmp .LBB22_11 2397; NOOPT-NEXT: .LBB22_11: # %entry 2398; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2399; NOOPT-NEXT: subl $300, %eax # imm = 0x12C 2400; NOOPT-NEXT: je .LBB22_3 2401; NOOPT-NEXT: jmp .LBB22_5 2402; NOOPT-NEXT: .LBB22_1: # %bb0 2403; NOOPT-NEXT: xorl %edi, %edi 2404; NOOPT-NEXT: callq g@PLT 2405; NOOPT-NEXT: jmp .LBB22_5 2406; NOOPT-NEXT: .LBB22_2: # %bb1 2407; NOOPT-NEXT: movl $1, %edi 2408; NOOPT-NEXT: callq g@PLT 2409; NOOPT-NEXT: jmp .LBB22_5 2410; NOOPT-NEXT: .LBB22_3: # %bb2 2411; NOOPT-NEXT: movl $2, %edi 2412; NOOPT-NEXT: callq g@PLT 2413; NOOPT-NEXT: jmp .LBB22_5 2414; NOOPT-NEXT: .LBB22_4: # %bb3 2415; NOOPT-NEXT: movl $3, %edi 2416; NOOPT-NEXT: callq g@PLT 2417; NOOPT-NEXT: .LBB22_5: # %return 2418; NOOPT-NEXT: popq %rax 2419; NOOPT-NEXT: .cfi_def_cfa_offset 8 2420; NOOPT-NEXT: retq 2421entry: 2422 switch i32 %x, label %return [ 2423 ; Jump table: 2424 i32 0, label %bb0 2425 i32 1, label %bb1 2426 i32 2, label %bb2 2427 i32 3, label %bb3 2428 2429 i32 100, label %bb0 2430 i32 200, label %bb1 2431 i32 300, label %bb2 2432 ] 2433bb0: tail call void @g(i32 0) br label %return 2434bb1: tail call void @g(i32 1) br label %return 2435bb2: tail call void @g(i32 2) br label %return 2436bb3: tail call void @g(i32 3) br label %return 2437return: ret void 2438} 2439 2440 2441; Don't assert due to truncating the bitwidth (64) to i4 when checking 2442; that the bit-test range fits in a word. 2443define void @pr23738(i4 %x) { 2444; CHECK-LABEL: pr23738: 2445; CHECK: # %bb.0: # %entry 2446; CHECK-NEXT: movl %edi, %eax 2447; CHECK-NEXT: andb $15, %al 2448; CHECK-NEXT: cmpb $11, %al 2449; CHECK-NEXT: ja .LBB23_2 2450; CHECK-NEXT: # %bb.1: # %entry 2451; CHECK-NEXT: andl $15, %edi 2452; CHECK-NEXT: movl $2051, %eax # imm = 0x803 2453; CHECK-NEXT: btl %edi, %eax 2454; CHECK-NEXT: jae .LBB23_2 2455; CHECK-NEXT: # %bb.3: # %bb1 2456; CHECK-NEXT: movl $1, %edi 2457; CHECK-NEXT: jmp g@PLT # TAILCALL 2458; CHECK-NEXT: .LBB23_2: # %bb0 2459; CHECK-NEXT: xorl %edi, %edi 2460; CHECK-NEXT: jmp g@PLT # TAILCALL 2461; 2462; NOOPT-LABEL: pr23738: 2463; NOOPT: # %bb.0: # %entry 2464; NOOPT-NEXT: pushq %rax 2465; NOOPT-NEXT: .cfi_def_cfa_offset 16 2466; NOOPT-NEXT: movb %dil, %al 2467; NOOPT-NEXT: movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill 2468; NOOPT-NEXT: andb $15, %al 2469; NOOPT-NEXT: subb $11, %al 2470; NOOPT-NEXT: je .LBB23_2 2471; NOOPT-NEXT: jmp .LBB23_4 2472; NOOPT-NEXT: .LBB23_4: # %entry 2473; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload 2474; NOOPT-NEXT: andb $15, %al 2475; NOOPT-NEXT: subb $2, %al 2476; NOOPT-NEXT: jb .LBB23_2 2477; NOOPT-NEXT: jmp .LBB23_1 2478; NOOPT-NEXT: .LBB23_1: # %bb0 2479; NOOPT-NEXT: xorl %edi, %edi 2480; NOOPT-NEXT: callq g@PLT 2481; NOOPT-NEXT: jmp .LBB23_3 2482; NOOPT-NEXT: .LBB23_2: # %bb1 2483; NOOPT-NEXT: movl $1, %edi 2484; NOOPT-NEXT: callq g@PLT 2485; NOOPT-NEXT: .LBB23_3: # %return 2486; NOOPT-NEXT: popq %rax 2487; NOOPT-NEXT: .cfi_def_cfa_offset 8 2488; NOOPT-NEXT: retq 2489entry: 2490 switch i4 %x, label %bb0 [ 2491 i4 0, label %bb1 2492 i4 1, label %bb1 2493 i4 -5, label %bb1 2494 ] 2495bb0: tail call void @g(i32 0) br label %return 2496bb1: tail call void @g(i32 1) br label %return 2497return: ret void 2498} 2499 2500 2501; The switch is lowered with bit tests. Since the case range is contiguous, the 2502; second bit test is redundant and can be skipped. Check that we don't update 2503; the phi node with an incoming value from the MBB of the skipped bit test 2504; (-verify-machine-instrs cathces this). 2505define i32 @pr27135(i32 %i) { 2506; CHECK-LABEL: pr27135: 2507; CHECK: # %bb.0: # %entry 2508; CHECK-NEXT: xorl %eax, %eax 2509; CHECK-NEXT: testb %al, %al 2510; CHECK-NEXT: jne .LBB24_5 2511; CHECK-NEXT: # %bb.1: # %sw 2512; CHECK-NEXT: movl $1, %eax 2513; CHECK-NEXT: addl $-96, %edi 2514; CHECK-NEXT: cmpl $5, %edi 2515; CHECK-NEXT: jbe .LBB24_2 2516; CHECK-NEXT: .LBB24_5: # %end 2517; CHECK-NEXT: retq 2518; CHECK-NEXT: .LBB24_2: # %sw 2519; CHECK-NEXT: movl $19, %eax 2520; CHECK-NEXT: btl %edi, %eax 2521; CHECK-NEXT: jae .LBB24_3 2522; CHECK-NEXT: # %bb.4: # %sw.bb2 2523; CHECK-NEXT: .LBB24_3: # %sw.bb 2524; 2525; NOOPT-LABEL: pr27135: 2526; NOOPT: # %bb.0: # %entry 2527; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2528; NOOPT-NEXT: xorl %eax, %eax 2529; NOOPT-NEXT: # implicit-def: $cl 2530; NOOPT-NEXT: testb $1, %cl 2531; NOOPT-NEXT: movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2532; NOOPT-NEXT: jne .LBB24_1 2533; NOOPT-NEXT: jmp .LBB24_4 2534; NOOPT-NEXT: .LBB24_1: # %sw 2535; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2536; NOOPT-NEXT: movl $1, %ecx 2537; NOOPT-NEXT: movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2538; NOOPT-NEXT: addl $-96, %eax 2539; NOOPT-NEXT: subl $2, %eax 2540; NOOPT-NEXT: jb .LBB24_3 2541; NOOPT-NEXT: jmp .LBB24_5 2542; NOOPT-NEXT: .LBB24_5: # %sw 2543; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2544; NOOPT-NEXT: addl $-98, %eax 2545; NOOPT-NEXT: subl $2, %eax 2546; NOOPT-NEXT: jb .LBB24_2 2547; NOOPT-NEXT: jmp .LBB24_6 2548; NOOPT-NEXT: .LBB24_6: # %sw 2549; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2550; NOOPT-NEXT: subl $100, %eax 2551; NOOPT-NEXT: je .LBB24_3 2552; NOOPT-NEXT: jmp .LBB24_7 2553; NOOPT-NEXT: .LBB24_7: # %sw 2554; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2555; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %ecx # 4-byte Reload 2556; NOOPT-NEXT: subl $101, %ecx 2557; NOOPT-NEXT: movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill 2558; NOOPT-NEXT: jne .LBB24_4 2559; NOOPT-NEXT: jmp .LBB24_2 2560; NOOPT-NEXT: .LBB24_2: # %sw.bb 2561; NOOPT-NEXT: .LBB24_3: # %sw.bb2 2562; NOOPT-NEXT: .LBB24_4: # %end 2563; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload 2564; NOOPT-NEXT: retq 2565entry: 2566 br i1 poison, label %sw, label %end 2567sw: 2568 switch i32 %i, label %end [ 2569 i32 99, label %sw.bb 2570 i32 98, label %sw.bb 2571 i32 101, label %sw.bb 2572 i32 97, label %sw.bb2 2573 i32 96, label %sw.bb2 2574 i32 100, label %sw.bb2 2575 ] 2576sw.bb: 2577 unreachable 2578sw.bb2: 2579 unreachable 2580end: 2581 %p = phi i32 [ 1, %sw ], [ 0, %entry ] 2582 ret i32 %p 2583} 2584 2585 2586; Since the default is unreachable, either cluster will be reached. 2587; Only one comparison should be emitted. 2588define void @range_with_unreachable_fallthrough(i32 %i) { 2589; CHECK-LABEL: range_with_unreachable_fallthrough: 2590; CHECK: # %bb.0: # %entry 2591; CHECK-NEXT: addl $-4, %edi 2592; CHECK-NEXT: cmpl $3, %edi 2593; CHECK-NEXT: jae .LBB25_1 2594; CHECK-NEXT: # %bb.2: # %bb2 2595; CHECK-NEXT: movl $1, %edi 2596; CHECK-NEXT: jmp g@PLT # TAILCALL 2597; CHECK-NEXT: .LBB25_1: # %bb1 2598; CHECK-NEXT: xorl %edi, %edi 2599; CHECK-NEXT: jmp g@PLT # TAILCALL 2600; 2601; NOOPT-LABEL: range_with_unreachable_fallthrough: 2602; NOOPT: # %bb.0: # %entry 2603; NOOPT-NEXT: pushq %rax 2604; NOOPT-NEXT: .cfi_def_cfa_offset 16 2605; NOOPT-NEXT: movl %edi, %eax 2606; NOOPT-NEXT: decl %eax 2607; NOOPT-NEXT: subl $3, %eax 2608; NOOPT-NEXT: jb .LBB25_1 2609; NOOPT-NEXT: jmp .LBB25_5 2610; NOOPT-NEXT: .LBB25_5: # %entry 2611; NOOPT-NEXT: jmp .LBB25_2 2612; NOOPT-NEXT: .LBB25_1: # %bb1 2613; NOOPT-NEXT: xorl %edi, %edi 2614; NOOPT-NEXT: callq g@PLT 2615; NOOPT-NEXT: jmp .LBB25_4 2616; NOOPT-NEXT: .LBB25_2: # %bb2 2617; NOOPT-NEXT: movl $1, %edi 2618; NOOPT-NEXT: callq g@PLT 2619; NOOPT-NEXT: jmp .LBB25_4 2620; NOOPT-NEXT: # %bb.3: # %default 2621; NOOPT-NEXT: .cfi_def_cfa_offset 8 2622; NOOPT-NEXT: .LBB25_4: # %return 2623; NOOPT-NEXT: .cfi_def_cfa_offset 16 2624; NOOPT-NEXT: popq %rax 2625; NOOPT-NEXT: .cfi_def_cfa_offset 8 2626; NOOPT-NEXT: retq 2627entry: 2628 switch i32 %i, label %default [ 2629 i32 1, label %bb1 2630 i32 2, label %bb1 2631 i32 3, label %bb1 2632 i32 4, label %bb2 2633 i32 5, label %bb2 2634 i32 6, label %bb2 2635 ] 2636bb1: tail call void @g(i32 0) br label %return 2637bb2: tail call void @g(i32 1) br label %return 2638default: unreachable 2639 2640return: 2641 ret void 2642} 2643 2644 2645; A switch over a small type (i8) should be extended to avoid truncation 2646; instructions. 2647define void @switch_i8(i32 %a) { 2648; CHECK-LABEL: switch_i8: 2649; CHECK: # %bb.0: 2650; CHECK-NEXT: # kill: def $edi killed $edi def $rdi 2651; CHECK-NEXT: andl $127, %edi 2652; CHECK-NEXT: leal -1(%rdi), %eax 2653; CHECK-NEXT: cmpl $8, %eax 2654; CHECK-NEXT: ja .LBB26_1 2655; CHECK-NEXT: # %bb.10: 2656; CHECK-NEXT: jmpq *.LJTI26_0(,%rax,8) 2657; CHECK-NEXT: .LBB26_4: # %bb0 2658; CHECK-NEXT: xorl %edi, %edi 2659; CHECK-NEXT: jmp g@PLT # TAILCALL 2660; CHECK-NEXT: .LBB26_1: 2661; CHECK-NEXT: cmpl $13, %edi 2662; CHECK-NEXT: je .LBB26_8 2663; CHECK-NEXT: # %bb.2: 2664; CHECK-NEXT: cmpl $42, %edi 2665; CHECK-NEXT: jne .LBB26_9 2666; CHECK-NEXT: # %bb.3: # %bb5 2667; CHECK-NEXT: movl $5, %edi 2668; CHECK-NEXT: jmp g@PLT # TAILCALL 2669; CHECK-NEXT: .LBB26_9: # %return 2670; CHECK-NEXT: retq 2671; CHECK-NEXT: .LBB26_7: # %bb3 2672; CHECK-NEXT: movl $3, %edi 2673; CHECK-NEXT: jmp g@PLT # TAILCALL 2674; CHECK-NEXT: .LBB26_5: # %bb1 2675; CHECK-NEXT: movl $1, %edi 2676; CHECK-NEXT: jmp g@PLT # TAILCALL 2677; CHECK-NEXT: .LBB26_6: # %bb2 2678; CHECK-NEXT: movl $2, %edi 2679; CHECK-NEXT: jmp g@PLT # TAILCALL 2680; CHECK-NEXT: .LBB26_8: # %bb4 2681; CHECK-NEXT: movl $4, %edi 2682; CHECK-NEXT: jmp g@PLT # TAILCALL 2683; 2684; NOOPT-LABEL: switch_i8: 2685; NOOPT: # %bb.0: 2686; NOOPT-NEXT: pushq %rax 2687; NOOPT-NEXT: .cfi_def_cfa_offset 16 2688; NOOPT-NEXT: movb %dil, %al 2689; NOOPT-NEXT: andb $127, %al 2690; NOOPT-NEXT: movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill 2691; NOOPT-NEXT: subb $1, %al 2692; NOOPT-NEXT: je .LBB26_1 2693; NOOPT-NEXT: jmp .LBB26_8 2694; NOOPT-NEXT: .LBB26_8: 2695; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload 2696; NOOPT-NEXT: subb $3, %al 2697; NOOPT-NEXT: je .LBB26_2 2698; NOOPT-NEXT: jmp .LBB26_9 2699; NOOPT-NEXT: .LBB26_9: 2700; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload 2701; NOOPT-NEXT: subb $7, %al 2702; NOOPT-NEXT: je .LBB26_3 2703; NOOPT-NEXT: jmp .LBB26_10 2704; NOOPT-NEXT: .LBB26_10: 2705; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload 2706; NOOPT-NEXT: subb $9, %al 2707; NOOPT-NEXT: je .LBB26_4 2708; NOOPT-NEXT: jmp .LBB26_11 2709; NOOPT-NEXT: .LBB26_11: 2710; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload 2711; NOOPT-NEXT: subb $13, %al 2712; NOOPT-NEXT: je .LBB26_5 2713; NOOPT-NEXT: jmp .LBB26_12 2714; NOOPT-NEXT: .LBB26_12: 2715; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload 2716; NOOPT-NEXT: subb $42, %al 2717; NOOPT-NEXT: je .LBB26_6 2718; NOOPT-NEXT: jmp .LBB26_7 2719; NOOPT-NEXT: .LBB26_1: # %bb0 2720; NOOPT-NEXT: xorl %edi, %edi 2721; NOOPT-NEXT: callq g@PLT 2722; NOOPT-NEXT: jmp .LBB26_7 2723; NOOPT-NEXT: .LBB26_2: # %bb1 2724; NOOPT-NEXT: movl $1, %edi 2725; NOOPT-NEXT: callq g@PLT 2726; NOOPT-NEXT: jmp .LBB26_7 2727; NOOPT-NEXT: .LBB26_3: # %bb2 2728; NOOPT-NEXT: movl $2, %edi 2729; NOOPT-NEXT: callq g@PLT 2730; NOOPT-NEXT: jmp .LBB26_7 2731; NOOPT-NEXT: .LBB26_4: # %bb3 2732; NOOPT-NEXT: movl $3, %edi 2733; NOOPT-NEXT: callq g@PLT 2734; NOOPT-NEXT: jmp .LBB26_7 2735; NOOPT-NEXT: .LBB26_5: # %bb4 2736; NOOPT-NEXT: movl $4, %edi 2737; NOOPT-NEXT: callq g@PLT 2738; NOOPT-NEXT: jmp .LBB26_7 2739; NOOPT-NEXT: .LBB26_6: # %bb5 2740; NOOPT-NEXT: movl $5, %edi 2741; NOOPT-NEXT: callq g@PLT 2742; NOOPT-NEXT: .LBB26_7: # %return 2743; NOOPT-NEXT: popq %rax 2744; NOOPT-NEXT: .cfi_def_cfa_offset 8 2745; NOOPT-NEXT: retq 2746 %and = and i32 %a, 127 2747 %trunc = trunc i32 %and to i8 2748 switch i8 %trunc, label %return [ 2749 i8 1, label %bb0 2750 i8 3, label %bb1 2751 i8 7, label %bb2 2752 i8 9, label %bb3 2753 i8 13, label %bb4 2754 i8 42, label %bb5 2755 ] 2756bb0: tail call void @g(i32 0) br label %return 2757bb1: tail call void @g(i32 1) br label %return 2758bb2: tail call void @g(i32 2) br label %return 2759bb3: tail call void @g(i32 3) br label %return 2760bb4: tail call void @g(i32 4) br label %return 2761bb5: tail call void @g(i32 5) br label %return 2762return: 2763 ret void 2764} 2765