2765 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py2; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=40 -switch-peel-threshold=101 -verify-machineinstrs | FileCheck %s3; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 -jump-table-density=40 -verify-machineinstrs | FileCheck --check-prefix=NOOPT %s4 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: # %entry11; CHECK-NEXT: # kill: def $edi killed $edi def $rdi12; CHECK-NEXT: decl %edi13; CHECK-NEXT: cmpl $4, %edi14; CHECK-NEXT: ja .LBB0_415; CHECK-NEXT: # %bb.1: # %entry16; CHECK-NEXT: jmpq *.LJTI0_0(,%rdi,8)17; CHECK-NEXT: .LBB0_3: # %bb218; CHECK-NEXT: movl $1, %edi19; CHECK-NEXT: jmp g@PLT # TAILCALL20; CHECK-NEXT: .LBB0_2: # %bb021; CHECK-NEXT: xorl %edi, %edi22; CHECK-NEXT: jmp g@PLT # TAILCALL23; CHECK-NEXT: .LBB0_4: # %return24; CHECK-NEXT: retq25;26; NOOPT-LABEL: basic:27; NOOPT: # %bb.0: # %entry28; NOOPT-NEXT: pushq %rax29; NOOPT-NEXT: .cfi_def_cfa_offset 1630; NOOPT-NEXT: movl %edi, %eax31; NOOPT-NEXT: decl %eax32; NOOPT-NEXT: movl %eax, %ecx33; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill34; NOOPT-NEXT: subl $4, %eax35; NOOPT-NEXT: ja .LBB0_436; NOOPT-NEXT: # %bb.5: # %entry37; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload38; NOOPT-NEXT: movq .LJTI0_0(,%rax,8), %rax39; NOOPT-NEXT: jmpq *%rax40; NOOPT-NEXT: .LBB0_1: # %bb041; NOOPT-NEXT: xorl %edi, %edi42; NOOPT-NEXT: callq g@PLT43; NOOPT-NEXT: jmp .LBB0_444; NOOPT-NEXT: .LBB0_2: # %bb145; NOOPT-NEXT: movl $1, %edi46; NOOPT-NEXT: callq g@PLT47; NOOPT-NEXT: jmp .LBB0_448; NOOPT-NEXT: .LBB0_3: # %bb249; NOOPT-NEXT: movl $1, %edi50; NOOPT-NEXT: callq g@PLT51; NOOPT-NEXT: .LBB0_4: # %return52; NOOPT-NEXT: popq %rax53; NOOPT-NEXT: .cfi_def_cfa_offset 854; NOOPT-NEXT: retq55entry:56 switch i32 %x, label %return [57 i32 3, label %bb058 i32 1, label %bb159 i32 4, label %bb160 i32 5, label %bb261 ]62bb0: tail call void @g(i32 0) br label %return63bb1: tail call void @g(i32 1) br label %return64bb2: tail call void @g(i32 1) br label %return65return: ret void66}67 68; Should never be lowered as a jump table because of the attribute69define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" {70; CHECK-LABEL: basic_nojumptable:71; CHECK: # %bb.0: # %entry72; CHECK-NEXT: cmpl $3, %edi73; CHECK-NEXT: jg .LBB1_474; CHECK-NEXT: # %bb.1: # %entry75; CHECK-NEXT: cmpl $1, %edi76; CHECK-NEXT: je .LBB1_777; CHECK-NEXT: # %bb.2: # %entry78; CHECK-NEXT: cmpl $3, %edi79; CHECK-NEXT: jne .LBB1_680; CHECK-NEXT: # %bb.3: # %bb081; CHECK-NEXT: xorl %edi, %edi82; CHECK-NEXT: jmp g@PLT # TAILCALL83; CHECK-NEXT: .LBB1_4: # %entry84; CHECK-NEXT: cmpl $4, %edi85; CHECK-NEXT: je .LBB1_786; CHECK-NEXT: # %bb.5: # %entry87; CHECK-NEXT: cmpl $5, %edi88; CHECK-NEXT: jne .LBB1_689; CHECK-NEXT: .LBB1_7: # %bb290; CHECK-NEXT: movl $1, %edi91; CHECK-NEXT: jmp g@PLT # TAILCALL92; CHECK-NEXT: .LBB1_6: # %return93; CHECK-NEXT: retq94;95; NOOPT-LABEL: basic_nojumptable:96; NOOPT: # %bb.0: # %entry97; NOOPT-NEXT: pushq %rax98; NOOPT-NEXT: .cfi_def_cfa_offset 1699; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill100; NOOPT-NEXT: subl $1, %edi101; NOOPT-NEXT: je .LBB1_2102; NOOPT-NEXT: jmp .LBB1_5103; NOOPT-NEXT: .LBB1_5: # %entry104; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload105; NOOPT-NEXT: subl $3, %eax106; NOOPT-NEXT: je .LBB1_1107; NOOPT-NEXT: jmp .LBB1_6108; NOOPT-NEXT: .LBB1_6: # %entry109; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload110; NOOPT-NEXT: subl $4, %eax111; NOOPT-NEXT: je .LBB1_2112; NOOPT-NEXT: jmp .LBB1_7113; NOOPT-NEXT: .LBB1_7: # %entry114; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload115; NOOPT-NEXT: subl $5, %eax116; NOOPT-NEXT: je .LBB1_3117; NOOPT-NEXT: jmp .LBB1_4118; NOOPT-NEXT: .LBB1_1: # %bb0119; NOOPT-NEXT: xorl %edi, %edi120; NOOPT-NEXT: callq g@PLT121; NOOPT-NEXT: jmp .LBB1_4122; NOOPT-NEXT: .LBB1_2: # %bb1123; NOOPT-NEXT: movl $1, %edi124; NOOPT-NEXT: callq g@PLT125; NOOPT-NEXT: jmp .LBB1_4126; NOOPT-NEXT: .LBB1_3: # %bb2127; NOOPT-NEXT: movl $1, %edi128; NOOPT-NEXT: callq g@PLT129; NOOPT-NEXT: .LBB1_4: # %return130; NOOPT-NEXT: popq %rax131; NOOPT-NEXT: .cfi_def_cfa_offset 8132; NOOPT-NEXT: retq133entry:134 switch i32 %x, label %return [135 i32 3, label %bb0136 i32 1, label %bb1137 i32 4, label %bb1138 i32 5, label %bb2139 ]140bb0: tail call void @g(i32 0) br label %return141bb1: tail call void @g(i32 1) br label %return142bb2: tail call void @g(i32 1) br label %return143return: ret void144}145 146; Should be lowered as a jump table because of the attribute147define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" {148; CHECK-LABEL: basic_nojumptable_false:149; CHECK: # %bb.0: # %entry150; CHECK-NEXT: # kill: def $edi killed $edi def $rdi151; CHECK-NEXT: decl %edi152; CHECK-NEXT: cmpl $4, %edi153; CHECK-NEXT: ja .LBB2_4154; CHECK-NEXT: # %bb.1: # %entry155; CHECK-NEXT: jmpq *.LJTI2_0(,%rdi,8)156; CHECK-NEXT: .LBB2_3: # %bb2157; CHECK-NEXT: movl $1, %edi158; CHECK-NEXT: jmp g@PLT # TAILCALL159; CHECK-NEXT: .LBB2_2: # %bb0160; CHECK-NEXT: xorl %edi, %edi161; CHECK-NEXT: jmp g@PLT # TAILCALL162; CHECK-NEXT: .LBB2_4: # %return163; CHECK-NEXT: retq164;165; NOOPT-LABEL: basic_nojumptable_false:166; NOOPT: # %bb.0: # %entry167; NOOPT-NEXT: pushq %rax168; NOOPT-NEXT: .cfi_def_cfa_offset 16169; NOOPT-NEXT: movl %edi, %eax170; NOOPT-NEXT: decl %eax171; NOOPT-NEXT: movl %eax, %ecx172; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill173; NOOPT-NEXT: subl $4, %eax174; NOOPT-NEXT: ja .LBB2_4175; NOOPT-NEXT: # %bb.5: # %entry176; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload177; NOOPT-NEXT: movq .LJTI2_0(,%rax,8), %rax178; NOOPT-NEXT: jmpq *%rax179; NOOPT-NEXT: .LBB2_1: # %bb0180; NOOPT-NEXT: xorl %edi, %edi181; NOOPT-NEXT: callq g@PLT182; NOOPT-NEXT: jmp .LBB2_4183; NOOPT-NEXT: .LBB2_2: # %bb1184; NOOPT-NEXT: movl $1, %edi185; NOOPT-NEXT: callq g@PLT186; NOOPT-NEXT: jmp .LBB2_4187; NOOPT-NEXT: .LBB2_3: # %bb2188; NOOPT-NEXT: movl $1, %edi189; NOOPT-NEXT: callq g@PLT190; NOOPT-NEXT: .LBB2_4: # %return191; NOOPT-NEXT: popq %rax192; NOOPT-NEXT: .cfi_def_cfa_offset 8193; NOOPT-NEXT: retq194entry:195 switch i32 %x, label %return [196 i32 3, label %bb0197 i32 1, label %bb1198 i32 4, label %bb1199 i32 5, label %bb2200 ]201bb0: tail call void @g(i32 0) br label %return202bb1: tail call void @g(i32 1) br label %return203bb2: tail call void @g(i32 1) br label %return204return: ret void205}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: # %entry213; CHECK-NEXT: # kill: def $edi killed $edi def $rdi214; CHECK-NEXT: leal -100(%rdi), %eax215; CHECK-NEXT: cmpl $4, %eax216; CHECK-NEXT: jb .LBB3_3217; CHECK-NEXT: # %bb.1: # %entry218; CHECK-NEXT: cmpl $3, %edi219; CHECK-NEXT: ja .LBB3_4220; CHECK-NEXT: # %bb.2: # %bb0221; CHECK-NEXT: xorl %edi, %edi222; CHECK-NEXT: jmp g@PLT # TAILCALL223; CHECK-NEXT: .LBB3_3: # %bb1224; CHECK-NEXT: movl $1, %edi225; CHECK-NEXT: jmp g@PLT # TAILCALL226; CHECK-NEXT: .LBB3_4: # %return227; CHECK-NEXT: retq228;229; NOOPT-LABEL: simple_ranges:230; NOOPT: # %bb.0: # %entry231; NOOPT-NEXT: pushq %rax232; NOOPT-NEXT: .cfi_def_cfa_offset 16233; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill234; NOOPT-NEXT: subl $4, %edi235; NOOPT-NEXT: jb .LBB3_1236; NOOPT-NEXT: jmp .LBB3_4237; NOOPT-NEXT: .LBB3_4: # %entry238; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload239; NOOPT-NEXT: addl $-100, %eax240; NOOPT-NEXT: subl $4, %eax241; NOOPT-NEXT: jb .LBB3_2242; NOOPT-NEXT: jmp .LBB3_3243; NOOPT-NEXT: .LBB3_1: # %bb0244; NOOPT-NEXT: xorl %edi, %edi245; NOOPT-NEXT: callq g@PLT246; NOOPT-NEXT: jmp .LBB3_3247; NOOPT-NEXT: .LBB3_2: # %bb1248; NOOPT-NEXT: movl $1, %edi249; NOOPT-NEXT: callq g@PLT250; NOOPT-NEXT: .LBB3_3: # %return251; NOOPT-NEXT: popq %rax252; NOOPT-NEXT: .cfi_def_cfa_offset 8253; NOOPT-NEXT: retq254entry:255 switch i32 %x, label %return [256 i32 0, label %bb0257 i32 1, label %bb0258 i32 2, label %bb0259 i32 3, label %bb0260 i32 100, label %bb1261 i32 101, label %bb1262 i32 102, label %bb1263 i32 103, label %bb1264 ]265bb0: tail call void @g(i32 0) br label %return266bb1: tail call void @g(i32 1) br label %return267return: ret void268}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: # %entry276; CHECK-NEXT: cmpl $8, %edi277; CHECK-NEXT: ja .LBB4_7278; CHECK-NEXT: # %bb.1: # %entry279; CHECK-NEXT: movl %edi, %eax280; CHECK-NEXT: jmpq *.LJTI4_0(,%rax,8)281; CHECK-NEXT: .LBB4_2: # %bb0282; CHECK-NEXT: xorl %edi, %edi283; CHECK-NEXT: jmp g@PLT # TAILCALL284; CHECK-NEXT: .LBB4_3: # %bb1285; CHECK-NEXT: movl $1, %edi286; CHECK-NEXT: jmp g@PLT # TAILCALL287; CHECK-NEXT: .LBB4_5: # %bb3288; CHECK-NEXT: movl $3, %edi289; CHECK-NEXT: jmp g@PLT # TAILCALL290; CHECK-NEXT: .LBB4_4: # %bb2291; CHECK-NEXT: movl $2, %edi292; CHECK-NEXT: jmp g@PLT # TAILCALL293; CHECK-NEXT: .LBB4_6: # %bb4294; CHECK-NEXT: movl $4, %edi295; CHECK-NEXT: jmp g@PLT # TAILCALL296; CHECK-NEXT: .LBB4_7: # %return297; CHECK-NEXT: retq298;299; NOOPT-LABEL: jt_is_better:300; NOOPT: # %bb.0: # %entry301; NOOPT-NEXT: pushq %rax302; NOOPT-NEXT: .cfi_def_cfa_offset 16303; NOOPT-NEXT: movl %edi, %eax304; NOOPT-NEXT: # kill: def $rax killed $eax305; NOOPT-NEXT: movq %rax, (%rsp) # 8-byte Spill306; NOOPT-NEXT: subl $8, %edi307; NOOPT-NEXT: ja .LBB4_6308; NOOPT-NEXT: # %bb.7: # %entry309; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload310; NOOPT-NEXT: movq .LJTI4_0(,%rax,8), %rax311; NOOPT-NEXT: jmpq *%rax312; NOOPT-NEXT: .LBB4_1: # %bb0313; NOOPT-NEXT: xorl %edi, %edi314; NOOPT-NEXT: callq g@PLT315; NOOPT-NEXT: jmp .LBB4_6316; NOOPT-NEXT: .LBB4_2: # %bb1317; NOOPT-NEXT: movl $1, %edi318; NOOPT-NEXT: callq g@PLT319; NOOPT-NEXT: jmp .LBB4_6320; NOOPT-NEXT: .LBB4_3: # %bb2321; NOOPT-NEXT: movl $2, %edi322; NOOPT-NEXT: callq g@PLT323; NOOPT-NEXT: jmp .LBB4_6324; NOOPT-NEXT: .LBB4_4: # %bb3325; NOOPT-NEXT: movl $3, %edi326; NOOPT-NEXT: callq g@PLT327; NOOPT-NEXT: jmp .LBB4_6328; NOOPT-NEXT: .LBB4_5: # %bb4329; NOOPT-NEXT: movl $4, %edi330; NOOPT-NEXT: callq g@PLT331; NOOPT-NEXT: .LBB4_6: # %return332; NOOPT-NEXT: popq %rax333; NOOPT-NEXT: .cfi_def_cfa_offset 8334; NOOPT-NEXT: retq335entry:336 switch i32 %x, label %return [337 i32 0, label %bb0338 i32 2, label %bb0339 i32 4, label %bb0340 i32 1, label %bb1341 i32 3, label %bb1342 i32 5, label %bb1343 344 i32 6, label %bb2345 i32 7, label %bb3346 i32 8, label %bb4347 ]348bb0: tail call void @g(i32 0) br label %return349bb1: tail call void @g(i32 1) br label %return350bb2: tail call void @g(i32 2) br label %return351bb3: tail call void @g(i32 3) br label %return352bb4: tail call void @g(i32 4) br label %return353return: ret void354}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 be360; in 2,5,8.361define void @bt_is_better(i32 %x) {362; CHECK-LABEL: bt_is_better:363; CHECK: # %bb.0: # %entry364; CHECK-NEXT: cmpl $8, %edi365; CHECK-NEXT: ja .LBB5_4366; CHECK-NEXT: # %bb.1: # %entry367; CHECK-NEXT: movl $73, %eax368; CHECK-NEXT: btl %edi, %eax369; CHECK-NEXT: jb .LBB5_5370; CHECK-NEXT: # %bb.2: # %entry371; CHECK-NEXT: movl $146, %eax372; CHECK-NEXT: btl %edi, %eax373; CHECK-NEXT: jae .LBB5_3374; CHECK-NEXT: # %bb.6: # %bb1375; CHECK-NEXT: movl $1, %edi376; CHECK-NEXT: jmp g@PLT # TAILCALL377; CHECK-NEXT: .LBB5_5: # %bb0378; CHECK-NEXT: xorl %edi, %edi379; CHECK-NEXT: jmp g@PLT # TAILCALL380; CHECK-NEXT: .LBB5_3: # %bb2381; CHECK-NEXT: movl $2, %edi382; CHECK-NEXT: jmp g@PLT # TAILCALL383; CHECK-NEXT: .LBB5_4: # %return384; CHECK-NEXT: retq385;386; NOOPT-LABEL: bt_is_better:387; NOOPT: # %bb.0: # %entry388; NOOPT-NEXT: pushq %rax389; NOOPT-NEXT: .cfi_def_cfa_offset 16390; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill391; NOOPT-NEXT: testl %edi, %edi392; NOOPT-NEXT: je .LBB5_1393; NOOPT-NEXT: jmp .LBB5_5394; NOOPT-NEXT: .LBB5_5: # %entry395; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload396; NOOPT-NEXT: subl $1, %eax397; NOOPT-NEXT: je .LBB5_2398; NOOPT-NEXT: jmp .LBB5_6399; NOOPT-NEXT: .LBB5_6: # %entry400; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload401; NOOPT-NEXT: subl $2, %eax402; NOOPT-NEXT: je .LBB5_3403; NOOPT-NEXT: jmp .LBB5_7404; NOOPT-NEXT: .LBB5_7: # %entry405; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload406; NOOPT-NEXT: subl $3, %eax407; NOOPT-NEXT: je .LBB5_1408; NOOPT-NEXT: jmp .LBB5_8409; NOOPT-NEXT: .LBB5_8: # %entry410; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload411; NOOPT-NEXT: subl $4, %eax412; NOOPT-NEXT: je .LBB5_2413; NOOPT-NEXT: jmp .LBB5_9414; NOOPT-NEXT: .LBB5_9: # %entry415; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload416; NOOPT-NEXT: subl $5, %eax417; NOOPT-NEXT: je .LBB5_3418; NOOPT-NEXT: jmp .LBB5_10419; NOOPT-NEXT: .LBB5_10: # %entry420; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload421; NOOPT-NEXT: subl $6, %eax422; NOOPT-NEXT: je .LBB5_1423; NOOPT-NEXT: jmp .LBB5_11424; NOOPT-NEXT: .LBB5_11: # %entry425; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload426; NOOPT-NEXT: subl $7, %eax427; NOOPT-NEXT: je .LBB5_2428; NOOPT-NEXT: jmp .LBB5_12429; NOOPT-NEXT: .LBB5_12: # %entry430; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload431; NOOPT-NEXT: subl $8, %eax432; NOOPT-NEXT: je .LBB5_3433; NOOPT-NEXT: jmp .LBB5_4434; NOOPT-NEXT: .LBB5_1: # %bb0435; NOOPT-NEXT: xorl %edi, %edi436; NOOPT-NEXT: callq g@PLT437; NOOPT-NEXT: jmp .LBB5_4438; NOOPT-NEXT: .LBB5_2: # %bb1439; NOOPT-NEXT: movl $1, %edi440; NOOPT-NEXT: callq g@PLT441; NOOPT-NEXT: jmp .LBB5_4442; NOOPT-NEXT: .LBB5_3: # %bb2443; NOOPT-NEXT: movl $2, %edi444; NOOPT-NEXT: callq g@PLT445; NOOPT-NEXT: .LBB5_4: # %return446; NOOPT-NEXT: popq %rax447; NOOPT-NEXT: .cfi_def_cfa_offset 8448; NOOPT-NEXT: retq449entry:450 switch i32 %x, label %return [451 i32 0, label %bb0452 i32 3, label %bb0453 i32 6, label %bb0454 i32 1, label %bb1455 i32 4, label %bb1456 i32 7, label %bb1457 i32 2, label %bb2458 i32 5, label %bb2459 i32 8, label %bb2460 ]461bb0: tail call void @g(i32 0) br label %return462bb1: tail call void @g(i32 1) br label %return463bb2: tail call void @g(i32 2) br label %return464return: ret void465}466 467; This will also be lowered as bit test, but as the range [0,8] is not fully468; covered (5 missing), the default statement can be jumped to and we end up469; with one more branch.470define void @bt_is_better2(i32 %x) {471; CHECK-LABEL: bt_is_better2:472; CHECK: # %bb.0: # %entry473; CHECK-NEXT: cmpl $8, %edi474; CHECK-NEXT: ja .LBB6_7475; CHECK-NEXT: # %bb.1: # %entry476; CHECK-NEXT: movl $73, %eax477; CHECK-NEXT: btl %edi, %eax478; CHECK-NEXT: jb .LBB6_5479; CHECK-NEXT: # %bb.2: # %entry480; CHECK-NEXT: movl $146, %eax481; CHECK-NEXT: btl %edi, %eax482; CHECK-NEXT: jae .LBB6_3483; CHECK-NEXT: # %bb.6: # %bb1484; CHECK-NEXT: movl $1, %edi485; CHECK-NEXT: jmp g@PLT # TAILCALL486; CHECK-NEXT: .LBB6_5: # %bb0487; CHECK-NEXT: xorl %edi, %edi488; CHECK-NEXT: jmp g@PLT # TAILCALL489; CHECK-NEXT: .LBB6_3: # %entry490; CHECK-NEXT: movl $260, %eax # imm = 0x104491; CHECK-NEXT: btl %edi, %eax492; CHECK-NEXT: jae .LBB6_7493; CHECK-NEXT: # %bb.4: # %bb2494; CHECK-NEXT: movl $2, %edi495; CHECK-NEXT: jmp g@PLT # TAILCALL496; CHECK-NEXT: .LBB6_7: # %return497; CHECK-NEXT: retq498;499; NOOPT-LABEL: bt_is_better2:500; NOOPT: # %bb.0: # %entry501; NOOPT-NEXT: pushq %rax502; NOOPT-NEXT: .cfi_def_cfa_offset 16503; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill504; NOOPT-NEXT: testl %edi, %edi505; NOOPT-NEXT: je .LBB6_1506; NOOPT-NEXT: jmp .LBB6_5507; NOOPT-NEXT: .LBB6_5: # %entry508; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload509; NOOPT-NEXT: subl $1, %eax510; NOOPT-NEXT: je .LBB6_2511; NOOPT-NEXT: jmp .LBB6_6512; NOOPT-NEXT: .LBB6_6: # %entry513; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload514; NOOPT-NEXT: subl $2, %eax515; NOOPT-NEXT: je .LBB6_3516; NOOPT-NEXT: jmp .LBB6_7517; NOOPT-NEXT: .LBB6_7: # %entry518; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload519; NOOPT-NEXT: subl $3, %eax520; NOOPT-NEXT: je .LBB6_1521; NOOPT-NEXT: jmp .LBB6_8522; NOOPT-NEXT: .LBB6_8: # %entry523; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload524; NOOPT-NEXT: subl $4, %eax525; NOOPT-NEXT: je .LBB6_2526; NOOPT-NEXT: jmp .LBB6_9527; NOOPT-NEXT: .LBB6_9: # %entry528; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload529; NOOPT-NEXT: subl $6, %eax530; NOOPT-NEXT: je .LBB6_1531; NOOPT-NEXT: jmp .LBB6_10532; NOOPT-NEXT: .LBB6_10: # %entry533; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload534; NOOPT-NEXT: subl $7, %eax535; NOOPT-NEXT: je .LBB6_2536; NOOPT-NEXT: jmp .LBB6_11537; NOOPT-NEXT: .LBB6_11: # %entry538; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload539; NOOPT-NEXT: subl $8, %eax540; NOOPT-NEXT: je .LBB6_3541; NOOPT-NEXT: jmp .LBB6_4542; NOOPT-NEXT: .LBB6_1: # %bb0543; NOOPT-NEXT: xorl %edi, %edi544; NOOPT-NEXT: callq g@PLT545; NOOPT-NEXT: jmp .LBB6_4546; NOOPT-NEXT: .LBB6_2: # %bb1547; NOOPT-NEXT: movl $1, %edi548; NOOPT-NEXT: callq g@PLT549; NOOPT-NEXT: jmp .LBB6_4550; NOOPT-NEXT: .LBB6_3: # %bb2551; NOOPT-NEXT: movl $2, %edi552; NOOPT-NEXT: callq g@PLT553; NOOPT-NEXT: .LBB6_4: # %return554; NOOPT-NEXT: popq %rax555; NOOPT-NEXT: .cfi_def_cfa_offset 8556; NOOPT-NEXT: retq557entry:558 switch i32 %x, label %return [559 i32 0, label %bb0560 i32 3, label %bb0561 i32 6, label %bb0562 i32 1, label %bb1563 i32 4, label %bb1564 i32 7, label %bb1565 i32 2, label %bb2566 i32 8, label %bb2567 ]568bb0: tail call void @g(i32 0) br label %return569bb1: tail call void @g(i32 1) br label %return570bb2: tail call void @g(i32 2) br label %return571return: ret void572}573 574define void @bt_is_better3(i32 %x) {575; CHECK-LABEL: bt_is_better3:576; CHECK: # %bb.0: # %entry577; CHECK-NEXT: cmpl $18, %edi578; CHECK-NEXT: ja .LBB7_7579; CHECK-NEXT: # %bb.1: # %entry580; CHECK-NEXT: movl $74752, %eax # imm = 0x12400581; CHECK-NEXT: btl %edi, %eax582; CHECK-NEXT: jb .LBB7_5583; CHECK-NEXT: # %bb.2: # %entry584; CHECK-NEXT: movl $149504, %eax # imm = 0x24800585; CHECK-NEXT: btl %edi, %eax586; CHECK-NEXT: jae .LBB7_3587; CHECK-NEXT: # %bb.6: # %bb1588; CHECK-NEXT: movl $1, %edi589; CHECK-NEXT: jmp g@PLT # TAILCALL590; CHECK-NEXT: .LBB7_5: # %bb0591; CHECK-NEXT: xorl %edi, %edi592; CHECK-NEXT: jmp g@PLT # TAILCALL593; CHECK-NEXT: .LBB7_3: # %entry594; CHECK-NEXT: movl $266240, %eax # imm = 0x41000595; CHECK-NEXT: btl %edi, %eax596; CHECK-NEXT: jae .LBB7_7597; CHECK-NEXT: # %bb.4: # %bb2598; CHECK-NEXT: movl $2, %edi599; CHECK-NEXT: jmp g@PLT # TAILCALL600; CHECK-NEXT: .LBB7_7: # %return601; CHECK-NEXT: retq602;603; NOOPT-LABEL: bt_is_better3:604; NOOPT: # %bb.0: # %entry605; NOOPT-NEXT: pushq %rax606; NOOPT-NEXT: .cfi_def_cfa_offset 16607; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill608; NOOPT-NEXT: subl $10, %edi609; NOOPT-NEXT: je .LBB7_1610; NOOPT-NEXT: jmp .LBB7_5611; NOOPT-NEXT: .LBB7_5: # %entry612; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload613; NOOPT-NEXT: subl $11, %eax614; NOOPT-NEXT: je .LBB7_2615; NOOPT-NEXT: jmp .LBB7_6616; NOOPT-NEXT: .LBB7_6: # %entry617; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload618; NOOPT-NEXT: subl $12, %eax619; NOOPT-NEXT: je .LBB7_3620; NOOPT-NEXT: jmp .LBB7_7621; NOOPT-NEXT: .LBB7_7: # %entry622; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload623; NOOPT-NEXT: subl $13, %eax624; NOOPT-NEXT: je .LBB7_1625; NOOPT-NEXT: jmp .LBB7_8626; NOOPT-NEXT: .LBB7_8: # %entry627; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload628; NOOPT-NEXT: subl $14, %eax629; NOOPT-NEXT: je .LBB7_2630; NOOPT-NEXT: jmp .LBB7_9631; NOOPT-NEXT: .LBB7_9: # %entry632; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload633; NOOPT-NEXT: subl $16, %eax634; NOOPT-NEXT: je .LBB7_1635; NOOPT-NEXT: jmp .LBB7_10636; NOOPT-NEXT: .LBB7_10: # %entry637; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload638; NOOPT-NEXT: subl $17, %eax639; NOOPT-NEXT: je .LBB7_2640; NOOPT-NEXT: jmp .LBB7_11641; NOOPT-NEXT: .LBB7_11: # %entry642; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload643; NOOPT-NEXT: subl $18, %eax644; NOOPT-NEXT: je .LBB7_3645; NOOPT-NEXT: jmp .LBB7_4646; NOOPT-NEXT: .LBB7_1: # %bb0647; NOOPT-NEXT: xorl %edi, %edi648; NOOPT-NEXT: callq g@PLT649; NOOPT-NEXT: jmp .LBB7_4650; NOOPT-NEXT: .LBB7_2: # %bb1651; NOOPT-NEXT: movl $1, %edi652; NOOPT-NEXT: callq g@PLT653; NOOPT-NEXT: jmp .LBB7_4654; NOOPT-NEXT: .LBB7_3: # %bb2655; NOOPT-NEXT: movl $2, %edi656; NOOPT-NEXT: callq g@PLT657; NOOPT-NEXT: .LBB7_4: # %return658; NOOPT-NEXT: popq %rax659; NOOPT-NEXT: .cfi_def_cfa_offset 8660; NOOPT-NEXT: retq661entry:662 switch i32 %x, label %return [663 i32 10, label %bb0664 i32 13, label %bb0665 i32 16, label %bb0666 i32 11, label %bb1667 i32 14, label %bb1668 i32 17, label %bb1669 i32 12, label %bb2670 i32 18, label %bb2671 ]672bb0: tail call void @g(i32 0) br label %return673bb1: tail call void @g(i32 1) br label %return674bb2: tail call void @g(i32 2) br label %return675return: ret void676 677; We don't have to subtract 10 from the case value to let the range become678; [0, 8], as each value in the range [10, 18] can be represented by bits in a679; word. Then we still need a branch to jump to the default statement for the680; range [0, 10).681; 74752 = 2^10 + 2^13 + 2^16682; 149504 = 2^11 + 2^14 + 2^17683; 266240 = 2^12 + 2^15 + 2^18684}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: # %entry691; CHECK-NEXT: cmpl $399, %edi # imm = 0x18F692; CHECK-NEXT: jg .LBB8_5693; CHECK-NEXT: # %bb.1: # %entry694; CHECK-NEXT: cmpl $100, %edi695; CHECK-NEXT: je .LBB8_8696; CHECK-NEXT: # %bb.2: # %entry697; CHECK-NEXT: cmpl $200, %edi698; CHECK-NEXT: je .LBB8_9699; CHECK-NEXT: # %bb.3: # %entry700; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C701; CHECK-NEXT: je .LBB8_8702; CHECK-NEXT: .LBB8_4: # %return703; CHECK-NEXT: retq704; CHECK-NEXT: .LBB8_5: # %entry705; CHECK-NEXT: cmpl $400, %edi # imm = 0x190706; CHECK-NEXT: je .LBB8_9707; CHECK-NEXT: # %bb.6: # %entry708; CHECK-NEXT: cmpl $600, %edi # imm = 0x258709; CHECK-NEXT: je .LBB8_9710; CHECK-NEXT: # %bb.7: # %entry711; CHECK-NEXT: cmpl $500, %edi # imm = 0x1F4712; CHECK-NEXT: jne .LBB8_4713; CHECK-NEXT: .LBB8_8: # %bb0714; CHECK-NEXT: xorl %edi, %edi715; CHECK-NEXT: jmp g@PLT # TAILCALL716; CHECK-NEXT: .LBB8_9: # %bb1717; CHECK-NEXT: movl $1, %edi718; CHECK-NEXT: jmp g@PLT # TAILCALL719;720; NOOPT-LABEL: optimal_pivot1:721; NOOPT: # %bb.0: # %entry722; NOOPT-NEXT: pushq %rax723; NOOPT-NEXT: .cfi_def_cfa_offset 16724; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill725; NOOPT-NEXT: subl $100, %edi726; NOOPT-NEXT: je .LBB8_1727; NOOPT-NEXT: jmp .LBB8_4728; NOOPT-NEXT: .LBB8_4: # %entry729; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload730; NOOPT-NEXT: subl $200, %eax731; NOOPT-NEXT: je .LBB8_2732; NOOPT-NEXT: jmp .LBB8_5733; NOOPT-NEXT: .LBB8_5: # %entry734; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload735; NOOPT-NEXT: subl $300, %eax # imm = 0x12C736; NOOPT-NEXT: je .LBB8_1737; NOOPT-NEXT: jmp .LBB8_6738; NOOPT-NEXT: .LBB8_6: # %entry739; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload740; NOOPT-NEXT: subl $400, %eax # imm = 0x190741; NOOPT-NEXT: je .LBB8_2742; NOOPT-NEXT: jmp .LBB8_7743; NOOPT-NEXT: .LBB8_7: # %entry744; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload745; NOOPT-NEXT: subl $500, %eax # imm = 0x1F4746; NOOPT-NEXT: je .LBB8_1747; NOOPT-NEXT: jmp .LBB8_8748; NOOPT-NEXT: .LBB8_8: # %entry749; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload750; NOOPT-NEXT: subl $600, %eax # imm = 0x258751; NOOPT-NEXT: je .LBB8_2752; NOOPT-NEXT: jmp .LBB8_3753; NOOPT-NEXT: .LBB8_1: # %bb0754; NOOPT-NEXT: xorl %edi, %edi755; NOOPT-NEXT: callq g@PLT756; NOOPT-NEXT: jmp .LBB8_3757; NOOPT-NEXT: .LBB8_2: # %bb1758; NOOPT-NEXT: movl $1, %edi759; NOOPT-NEXT: callq g@PLT760; NOOPT-NEXT: .LBB8_3: # %return761; NOOPT-NEXT: popq %rax762; NOOPT-NEXT: .cfi_def_cfa_offset 8763; NOOPT-NEXT: retq764entry:765 switch i32 %x, label %return [766 i32 100, label %bb0767 i32 200, label %bb1768 i32 300, label %bb0769 i32 400, label %bb1770 i32 500, label %bb0771 i32 600, label %bb1772 773 ]774bb0: tail call void @g(i32 0) br label %return775bb1: tail call void @g(i32 1) br label %return776return: ret void777}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: # %entry784; CHECK-NEXT: # kill: def $edi killed $edi def $rdi785; CHECK-NEXT: cmpl $299, %edi # imm = 0x12B786; CHECK-NEXT: jg .LBB9_4787; CHECK-NEXT: # %bb.1: # %entry788; CHECK-NEXT: leal -100(%rdi), %eax789; CHECK-NEXT: cmpl $3, %eax790; CHECK-NEXT: jbe .LBB9_12791; CHECK-NEXT: # %bb.2: # %entry792; CHECK-NEXT: addl $-200, %edi793; CHECK-NEXT: cmpl $3, %edi794; CHECK-NEXT: ja .LBB9_11795; CHECK-NEXT: # %bb.3: # %entry796; CHECK-NEXT: jmpq *.LJTI9_1(,%rdi,8)797; CHECK-NEXT: .LBB9_4: # %entry798; CHECK-NEXT: leal -300(%rdi), %eax799; CHECK-NEXT: cmpl $3, %eax800; CHECK-NEXT: jbe .LBB9_13801; CHECK-NEXT: # %bb.5: # %entry802; CHECK-NEXT: addl $-400, %edi # imm = 0xFE70803; CHECK-NEXT: cmpl $3, %edi804; CHECK-NEXT: ja .LBB9_11805; CHECK-NEXT: # %bb.6: # %entry806; CHECK-NEXT: jmpq *.LJTI9_3(,%rdi,8)807; CHECK-NEXT: .LBB9_12: # %entry808; CHECK-NEXT: jmpq *.LJTI9_0(,%rax,8)809; CHECK-NEXT: .LBB9_13: # %entry810; CHECK-NEXT: jmpq *.LJTI9_2(,%rax,8)811; CHECK-NEXT: .LBB9_7: # %bb0812; CHECK-NEXT: xorl %edi, %edi813; CHECK-NEXT: jmp g@PLT # TAILCALL814; CHECK-NEXT: .LBB9_9: # %bb2815; CHECK-NEXT: movl $2, %edi816; CHECK-NEXT: jmp g@PLT # TAILCALL817; CHECK-NEXT: .LBB9_10: # %bb3818; CHECK-NEXT: movl $3, %edi819; CHECK-NEXT: jmp g@PLT # TAILCALL820; CHECK-NEXT: .LBB9_8: # %bb1821; CHECK-NEXT: movl $1, %edi822; CHECK-NEXT: jmp g@PLT # TAILCALL823; CHECK-NEXT: .LBB9_11: # %return824; CHECK-NEXT: retq825;826; NOOPT-LABEL: optimal_pivot2:827; NOOPT: # %bb.0: # %entry828; NOOPT-NEXT: pushq %rax829; NOOPT-NEXT: .cfi_def_cfa_offset 16830; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill831; NOOPT-NEXT: subl $100, %edi832; NOOPT-NEXT: je .LBB9_1833; NOOPT-NEXT: jmp .LBB9_6834; NOOPT-NEXT: .LBB9_6: # %entry835; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload836; NOOPT-NEXT: subl $101, %eax837; NOOPT-NEXT: je .LBB9_2838; NOOPT-NEXT: jmp .LBB9_7839; NOOPT-NEXT: .LBB9_7: # %entry840; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload841; NOOPT-NEXT: subl $102, %eax842; NOOPT-NEXT: je .LBB9_3843; NOOPT-NEXT: jmp .LBB9_8844; NOOPT-NEXT: .LBB9_8: # %entry845; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload846; NOOPT-NEXT: subl $103, %eax847; NOOPT-NEXT: je .LBB9_4848; NOOPT-NEXT: jmp .LBB9_9849; NOOPT-NEXT: .LBB9_9: # %entry850; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload851; NOOPT-NEXT: subl $200, %eax852; NOOPT-NEXT: je .LBB9_1853; NOOPT-NEXT: jmp .LBB9_10854; NOOPT-NEXT: .LBB9_10: # %entry855; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload856; NOOPT-NEXT: subl $201, %eax857; NOOPT-NEXT: je .LBB9_2858; NOOPT-NEXT: jmp .LBB9_11859; NOOPT-NEXT: .LBB9_11: # %entry860; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload861; NOOPT-NEXT: subl $202, %eax862; NOOPT-NEXT: je .LBB9_3863; NOOPT-NEXT: jmp .LBB9_12864; NOOPT-NEXT: .LBB9_12: # %entry865; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload866; NOOPT-NEXT: subl $203, %eax867; NOOPT-NEXT: je .LBB9_4868; NOOPT-NEXT: jmp .LBB9_13869; NOOPT-NEXT: .LBB9_13: # %entry870; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload871; NOOPT-NEXT: subl $300, %eax # imm = 0x12C872; NOOPT-NEXT: je .LBB9_1873; NOOPT-NEXT: jmp .LBB9_14874; NOOPT-NEXT: .LBB9_14: # %entry875; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload876; NOOPT-NEXT: subl $301, %eax # imm = 0x12D877; NOOPT-NEXT: je .LBB9_2878; NOOPT-NEXT: jmp .LBB9_15879; NOOPT-NEXT: .LBB9_15: # %entry880; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload881; NOOPT-NEXT: subl $302, %eax # imm = 0x12E882; NOOPT-NEXT: je .LBB9_3883; NOOPT-NEXT: jmp .LBB9_16884; NOOPT-NEXT: .LBB9_16: # %entry885; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload886; NOOPT-NEXT: subl $303, %eax # imm = 0x12F887; NOOPT-NEXT: je .LBB9_4888; NOOPT-NEXT: jmp .LBB9_17889; NOOPT-NEXT: .LBB9_17: # %entry890; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload891; NOOPT-NEXT: subl $400, %eax # imm = 0x190892; NOOPT-NEXT: je .LBB9_1893; NOOPT-NEXT: jmp .LBB9_18894; NOOPT-NEXT: .LBB9_18: # %entry895; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload896; NOOPT-NEXT: subl $401, %eax # imm = 0x191897; NOOPT-NEXT: je .LBB9_2898; NOOPT-NEXT: jmp .LBB9_19899; NOOPT-NEXT: .LBB9_19: # %entry900; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload901; NOOPT-NEXT: subl $402, %eax # imm = 0x192902; NOOPT-NEXT: je .LBB9_3903; NOOPT-NEXT: jmp .LBB9_20904; NOOPT-NEXT: .LBB9_20: # %entry905; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload906; NOOPT-NEXT: subl $403, %eax # imm = 0x193907; NOOPT-NEXT: je .LBB9_4908; NOOPT-NEXT: jmp .LBB9_5909; NOOPT-NEXT: .LBB9_1: # %bb0910; NOOPT-NEXT: xorl %edi, %edi911; NOOPT-NEXT: callq g@PLT912; NOOPT-NEXT: jmp .LBB9_5913; NOOPT-NEXT: .LBB9_2: # %bb1914; NOOPT-NEXT: movl $1, %edi915; NOOPT-NEXT: callq g@PLT916; NOOPT-NEXT: jmp .LBB9_5917; NOOPT-NEXT: .LBB9_3: # %bb2918; NOOPT-NEXT: movl $2, %edi919; NOOPT-NEXT: callq g@PLT920; NOOPT-NEXT: jmp .LBB9_5921; NOOPT-NEXT: .LBB9_4: # %bb3922; NOOPT-NEXT: movl $3, %edi923; NOOPT-NEXT: callq g@PLT924; NOOPT-NEXT: .LBB9_5: # %return925; NOOPT-NEXT: popq %rax926; NOOPT-NEXT: .cfi_def_cfa_offset 8927; NOOPT-NEXT: retq928entry:929 switch i32 %x, label %return [930 i32 100, label %bb0 i32 101, label %bb1 i32 102, label %bb2 i32 103, label %bb3931 i32 200, label %bb0 i32 201, label %bb1 i32 202, label %bb2 i32 203, label %bb3932 i32 300, label %bb0 i32 301, label %bb1 i32 302, label %bb2 i32 303, label %bb3933 i32 400, label %bb0 i32 401, label %bb1 i32 402, label %bb2 i32 403, label %bb3934 935 ]936bb0: tail call void @g(i32 0) br label %return937bb1: tail call void @g(i32 1) br label %return938bb2: tail call void @g(i32 2) br label %return939bb3: tail call void @g(i32 3) br label %return940return: ret void941}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: # %entry950; CHECK-NEXT: # kill: def $edi killed $edi def $rdi951; CHECK-NEXT: leal -5(%rdi), %eax952; CHECK-NEXT: cmpl $10, %eax953; CHECK-NEXT: ja .LBB10_1954; CHECK-NEXT: # %bb.9: # %entry955; CHECK-NEXT: jmpq *.LJTI10_0(,%rax,8)956; CHECK-NEXT: .LBB10_3: # %bb1957; CHECK-NEXT: movl $1, %edi958; CHECK-NEXT: jmp g@PLT # TAILCALL959; CHECK-NEXT: .LBB10_1: # %entry960; CHECK-NEXT: testl %edi, %edi961; CHECK-NEXT: jne .LBB10_8962; CHECK-NEXT: # %bb.2: # %bb0963; CHECK-NEXT: xorl %edi, %edi964; CHECK-NEXT: jmp g@PLT # TAILCALL965; CHECK-NEXT: .LBB10_8: # %return966; CHECK-NEXT: retq967; CHECK-NEXT: .LBB10_7: # %bb5968; CHECK-NEXT: movl $5, %edi969; CHECK-NEXT: jmp g@PLT # TAILCALL970; CHECK-NEXT: .LBB10_5: # %bb3971; CHECK-NEXT: movl $3, %edi972; CHECK-NEXT: jmp g@PLT # TAILCALL973; CHECK-NEXT: .LBB10_4: # %bb2974; CHECK-NEXT: movl $2, %edi975; CHECK-NEXT: jmp g@PLT # TAILCALL976; CHECK-NEXT: .LBB10_6: # %bb4977; CHECK-NEXT: movl $4, %edi978; CHECK-NEXT: jmp g@PLT # TAILCALL979;980; NOOPT-LABEL: optimal_jump_table1:981; NOOPT: # %bb.0: # %entry982; NOOPT-NEXT: pushq %rax983; NOOPT-NEXT: .cfi_def_cfa_offset 16984; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill985; NOOPT-NEXT: testl %edi, %edi986; NOOPT-NEXT: je .LBB10_1987; NOOPT-NEXT: jmp .LBB10_8988; NOOPT-NEXT: .LBB10_8: # %entry989; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload990; NOOPT-NEXT: subl $5, %eax991; NOOPT-NEXT: je .LBB10_2992; NOOPT-NEXT: jmp .LBB10_9993; NOOPT-NEXT: .LBB10_9: # %entry994; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload995; NOOPT-NEXT: subl $6, %eax996; NOOPT-NEXT: je .LBB10_3997; NOOPT-NEXT: jmp .LBB10_10998; NOOPT-NEXT: .LBB10_10: # %entry999; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1000; NOOPT-NEXT: subl $12, %eax1001; NOOPT-NEXT: je .LBB10_41002; NOOPT-NEXT: jmp .LBB10_111003; NOOPT-NEXT: .LBB10_11: # %entry1004; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1005; NOOPT-NEXT: subl $13, %eax1006; NOOPT-NEXT: je .LBB10_51007; NOOPT-NEXT: jmp .LBB10_121008; NOOPT-NEXT: .LBB10_12: # %entry1009; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1010; NOOPT-NEXT: subl $15, %eax1011; NOOPT-NEXT: je .LBB10_61012; NOOPT-NEXT: jmp .LBB10_71013; NOOPT-NEXT: .LBB10_1: # %bb01014; NOOPT-NEXT: xorl %edi, %edi1015; NOOPT-NEXT: callq g@PLT1016; NOOPT-NEXT: jmp .LBB10_71017; NOOPT-NEXT: .LBB10_2: # %bb11018; NOOPT-NEXT: movl $1, %edi1019; NOOPT-NEXT: callq g@PLT1020; NOOPT-NEXT: jmp .LBB10_71021; NOOPT-NEXT: .LBB10_3: # %bb21022; NOOPT-NEXT: movl $2, %edi1023; NOOPT-NEXT: callq g@PLT1024; NOOPT-NEXT: jmp .LBB10_71025; NOOPT-NEXT: .LBB10_4: # %bb31026; NOOPT-NEXT: movl $3, %edi1027; NOOPT-NEXT: callq g@PLT1028; NOOPT-NEXT: jmp .LBB10_71029; NOOPT-NEXT: .LBB10_5: # %bb41030; NOOPT-NEXT: movl $4, %edi1031; NOOPT-NEXT: callq g@PLT1032; NOOPT-NEXT: jmp .LBB10_71033; NOOPT-NEXT: .LBB10_6: # %bb51034; NOOPT-NEXT: movl $5, %edi1035; NOOPT-NEXT: callq g@PLT1036; NOOPT-NEXT: .LBB10_7: # %return1037; NOOPT-NEXT: popq %rax1038; NOOPT-NEXT: .cfi_def_cfa_offset 81039; NOOPT-NEXT: retq1040entry:1041 switch i32 %x, label %return [1042 i32 0, label %bb01043 i32 5, label %bb11044 i32 6, label %bb21045 i32 12, label %bb31046 i32 13, label %bb41047 i32 15, label %bb51048 ]1049bb0: tail call void @g(i32 0) br label %return1050bb1: tail call void @g(i32 1) br label %return1051bb2: tail call void @g(i32 2) br label %return1052bb3: tail call void @g(i32 3) br label %return1053bb4: tail call void @g(i32 4) br label %return1054bb5: tail call void @g(i32 5) br label %return1055return: ret void1056}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 former1061; 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: # %entry1065; CHECK-NEXT: cmpl $9, %edi1066; CHECK-NEXT: ja .LBB11_11067; CHECK-NEXT: # %bb.10: # %entry1068; CHECK-NEXT: movl %edi, %eax1069; CHECK-NEXT: jmpq *.LJTI11_0(,%rax,8)1070; CHECK-NEXT: .LBB11_4: # %bb01071; CHECK-NEXT: xorl %edi, %edi1072; CHECK-NEXT: jmp g@PLT # TAILCALL1073; CHECK-NEXT: .LBB11_1: # %entry1074; CHECK-NEXT: cmpl $14, %edi1075; CHECK-NEXT: je .LBB11_81076; CHECK-NEXT: # %bb.2: # %entry1077; CHECK-NEXT: cmpl $15, %edi1078; CHECK-NEXT: jne .LBB11_91079; CHECK-NEXT: # %bb.3: # %bb51080; CHECK-NEXT: movl $5, %edi1081; CHECK-NEXT: jmp g@PLT # TAILCALL1082; CHECK-NEXT: .LBB11_9: # %return1083; CHECK-NEXT: retq1084; CHECK-NEXT: .LBB11_7: # %bb31085; CHECK-NEXT: movl $3, %edi1086; CHECK-NEXT: jmp g@PLT # TAILCALL1087; CHECK-NEXT: .LBB11_5: # %bb11088; CHECK-NEXT: movl $1, %edi1089; CHECK-NEXT: jmp g@PLT # TAILCALL1090; CHECK-NEXT: .LBB11_6: # %bb21091; CHECK-NEXT: movl $2, %edi1092; CHECK-NEXT: jmp g@PLT # TAILCALL1093; CHECK-NEXT: .LBB11_8: # %bb41094; CHECK-NEXT: movl $4, %edi1095; CHECK-NEXT: jmp g@PLT # TAILCALL1096;1097; NOOPT-LABEL: optimal_jump_table2:1098; NOOPT: # %bb.0: # %entry1099; NOOPT-NEXT: pushq %rax1100; NOOPT-NEXT: .cfi_def_cfa_offset 161101; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1102; NOOPT-NEXT: testl %edi, %edi1103; NOOPT-NEXT: je .LBB11_11104; NOOPT-NEXT: jmp .LBB11_81105; NOOPT-NEXT: .LBB11_8: # %entry1106; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1107; NOOPT-NEXT: subl $1, %eax1108; NOOPT-NEXT: je .LBB11_21109; NOOPT-NEXT: jmp .LBB11_91110; NOOPT-NEXT: .LBB11_9: # %entry1111; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1112; NOOPT-NEXT: subl $2, %eax1113; NOOPT-NEXT: je .LBB11_31114; NOOPT-NEXT: jmp .LBB11_101115; NOOPT-NEXT: .LBB11_10: # %entry1116; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1117; NOOPT-NEXT: subl $9, %eax1118; NOOPT-NEXT: je .LBB11_41119; NOOPT-NEXT: jmp .LBB11_111120; NOOPT-NEXT: .LBB11_11: # %entry1121; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1122; NOOPT-NEXT: subl $14, %eax1123; NOOPT-NEXT: je .LBB11_51124; NOOPT-NEXT: jmp .LBB11_121125; NOOPT-NEXT: .LBB11_12: # %entry1126; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1127; NOOPT-NEXT: subl $15, %eax1128; NOOPT-NEXT: je .LBB11_61129; NOOPT-NEXT: jmp .LBB11_71130; NOOPT-NEXT: .LBB11_1: # %bb01131; NOOPT-NEXT: xorl %edi, %edi1132; NOOPT-NEXT: callq g@PLT1133; NOOPT-NEXT: jmp .LBB11_71134; NOOPT-NEXT: .LBB11_2: # %bb11135; NOOPT-NEXT: movl $1, %edi1136; NOOPT-NEXT: callq g@PLT1137; NOOPT-NEXT: jmp .LBB11_71138; NOOPT-NEXT: .LBB11_3: # %bb21139; NOOPT-NEXT: movl $2, %edi1140; NOOPT-NEXT: callq g@PLT1141; NOOPT-NEXT: jmp .LBB11_71142; NOOPT-NEXT: .LBB11_4: # %bb31143; NOOPT-NEXT: movl $3, %edi1144; NOOPT-NEXT: callq g@PLT1145; NOOPT-NEXT: jmp .LBB11_71146; NOOPT-NEXT: .LBB11_5: # %bb41147; NOOPT-NEXT: movl $4, %edi1148; NOOPT-NEXT: callq g@PLT1149; NOOPT-NEXT: jmp .LBB11_71150; NOOPT-NEXT: .LBB11_6: # %bb51151; NOOPT-NEXT: movl $5, %edi1152; NOOPT-NEXT: callq g@PLT1153; NOOPT-NEXT: .LBB11_7: # %return1154; NOOPT-NEXT: popq %rax1155; NOOPT-NEXT: .cfi_def_cfa_offset 81156; NOOPT-NEXT: retq1157entry:1158 switch i32 %x, label %return [1159 i32 0, label %bb01160 i32 1, label %bb11161 i32 2, label %bb21162 i32 9, label %bb31163 i32 14, label %bb41164 i32 15, label %bb51165 ]1166bb0: tail call void @g(i32 0) br label %return1167bb1: tail call void @g(i32 1) br label %return1168bb2: tail call void @g(i32 2) br label %return1169bb3: tail call void @g(i32 3) br label %return1170bb4: tail call void @g(i32 4) br label %return1171bb5: tail call void @g(i32 5) br label %return1172return: ret void1173}1174 1175 1176; Splitting to maximize left-right density sum and gap size would split this1177; between 3 and 10, and then between 20 and 25. It's better to build a table1178; from 1-20.1179define void @optimal_jump_table3(i32 %x) {1180; CHECK-LABEL: optimal_jump_table3:1181; CHECK: # %bb.0: # %entry1182; CHECK-NEXT: # kill: def $edi killed $edi def $rdi1183; CHECK-NEXT: leal -1(%rdi), %eax1184; CHECK-NEXT: cmpl $19, %eax1185; CHECK-NEXT: ja .LBB12_11186; CHECK-NEXT: # %bb.3: # %entry1187; CHECK-NEXT: jmpq *.LJTI12_0(,%rax,8)1188; CHECK-NEXT: .LBB12_4: # %bb01189; CHECK-NEXT: xorl %edi, %edi1190; CHECK-NEXT: jmp g@PLT # TAILCALL1191; CHECK-NEXT: .LBB12_6: # %bb21192; CHECK-NEXT: movl $2, %edi1193; CHECK-NEXT: jmp g@PLT # TAILCALL1194; CHECK-NEXT: .LBB12_5: # %bb11195; CHECK-NEXT: movl $1, %edi1196; CHECK-NEXT: jmp g@PLT # TAILCALL1197; CHECK-NEXT: .LBB12_7: # %bb31198; CHECK-NEXT: movl $3, %edi1199; CHECK-NEXT: jmp g@PLT # TAILCALL1200; CHECK-NEXT: .LBB12_1: # %entry1201; CHECK-NEXT: cmpl $25, %edi1202; CHECK-NEXT: jne .LBB12_81203; CHECK-NEXT: # %bb.2: # %bb41204; CHECK-NEXT: movl $4, %edi1205; CHECK-NEXT: jmp g@PLT # TAILCALL1206; CHECK-NEXT: .LBB12_8: # %return1207; CHECK-NEXT: retq1208;1209; NOOPT-LABEL: optimal_jump_table3:1210; NOOPT: # %bb.0: # %entry1211; NOOPT-NEXT: pushq %rax1212; NOOPT-NEXT: .cfi_def_cfa_offset 161213; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1214; NOOPT-NEXT: subl $1, %edi1215; NOOPT-NEXT: je .LBB12_11216; NOOPT-NEXT: jmp .LBB12_71217; NOOPT-NEXT: .LBB12_7: # %entry1218; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1219; NOOPT-NEXT: subl $2, %eax1220; NOOPT-NEXT: je .LBB12_21221; NOOPT-NEXT: jmp .LBB12_81222; NOOPT-NEXT: .LBB12_8: # %entry1223; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1224; NOOPT-NEXT: subl $3, %eax1225; NOOPT-NEXT: je .LBB12_31226; NOOPT-NEXT: jmp .LBB12_91227; NOOPT-NEXT: .LBB12_9: # %entry1228; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1229; NOOPT-NEXT: subl $10, %eax1230; NOOPT-NEXT: je .LBB12_41231; NOOPT-NEXT: jmp .LBB12_101232; NOOPT-NEXT: .LBB12_10: # %entry1233; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1234; NOOPT-NEXT: subl $13, %eax1235; NOOPT-NEXT: je .LBB12_11236; NOOPT-NEXT: jmp .LBB12_111237; NOOPT-NEXT: .LBB12_11: # %entry1238; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1239; NOOPT-NEXT: subl $14, %eax1240; NOOPT-NEXT: je .LBB12_21241; NOOPT-NEXT: jmp .LBB12_121242; NOOPT-NEXT: .LBB12_12: # %entry1243; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1244; NOOPT-NEXT: subl $15, %eax1245; NOOPT-NEXT: je .LBB12_31246; NOOPT-NEXT: jmp .LBB12_131247; NOOPT-NEXT: .LBB12_13: # %entry1248; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1249; NOOPT-NEXT: subl $20, %eax1250; NOOPT-NEXT: je .LBB12_41251; NOOPT-NEXT: jmp .LBB12_141252; NOOPT-NEXT: .LBB12_14: # %entry1253; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1254; NOOPT-NEXT: subl $25, %eax1255; NOOPT-NEXT: je .LBB12_51256; NOOPT-NEXT: jmp .LBB12_61257; NOOPT-NEXT: .LBB12_1: # %bb01258; NOOPT-NEXT: xorl %edi, %edi1259; NOOPT-NEXT: callq g@PLT1260; NOOPT-NEXT: jmp .LBB12_61261; NOOPT-NEXT: .LBB12_2: # %bb11262; NOOPT-NEXT: movl $1, %edi1263; NOOPT-NEXT: callq g@PLT1264; NOOPT-NEXT: jmp .LBB12_61265; NOOPT-NEXT: .LBB12_3: # %bb21266; NOOPT-NEXT: movl $2, %edi1267; NOOPT-NEXT: callq g@PLT1268; NOOPT-NEXT: jmp .LBB12_61269; NOOPT-NEXT: .LBB12_4: # %bb31270; NOOPT-NEXT: movl $3, %edi1271; NOOPT-NEXT: callq g@PLT1272; NOOPT-NEXT: jmp .LBB12_61273; NOOPT-NEXT: .LBB12_5: # %bb41274; NOOPT-NEXT: movl $4, %edi1275; NOOPT-NEXT: callq g@PLT1276; NOOPT-NEXT: .LBB12_6: # %return1277; NOOPT-NEXT: popq %rax1278; NOOPT-NEXT: .cfi_def_cfa_offset 81279; NOOPT-NEXT: retq1280entry:1281 switch i32 %x, label %return [1282 i32 1, label %bb01283 i32 2, label %bb11284 i32 3, label %bb21285 i32 10, label %bb31286 i32 13, label %bb01287 i32 14, label %bb11288 i32 15, label %bb21289 i32 20, label %bb31290 i32 25, label %bb41291 ]1292bb0: tail call void @g(i32 0) br label %return1293bb1: tail call void @g(i32 1) br label %return1294bb2: tail call void @g(i32 2) br label %return1295bb3: tail call void @g(i32 3) br label %return1296bb4: tail call void @g(i32 4) br label %return1297return: ret void1298}1299 1300%struct.S = type { ptr, i32 }1301 1302; This will be lowered to a comparison with 4 and then bit tests. Make sure1303; 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: # %entry1307; CHECK-NEXT: .p2align 41308; CHECK-NEXT: .LBB13_1: # %header1309; CHECK-NEXT: # =>This Inner Loop Header: Depth=11310; CHECK-NEXT: testq %rdi, %rdi1311; CHECK-NEXT: je .LBB13_51312; CHECK-NEXT: # %bb.2: # %loop1313; CHECK-NEXT: # in Loop: Header=BB13_1 Depth=11314; CHECK-NEXT: movq (%rdi), %rdi1315; CHECK-NEXT: movl 8(%rdi), %eax1316; CHECK-NEXT: cmpl $4, %eax1317; CHECK-NEXT: je .LBB13_11318; CHECK-NEXT: # %bb.3: # %loop1319; CHECK-NEXT: addl $-25, %eax1320; CHECK-NEXT: cmpl $44, %eax1321; CHECK-NEXT: ja .LBB13_51322; CHECK-NEXT: # %bb.4: # %loop1323; CHECK-NEXT: movabsq $17592186046465, %rcx # imm = 0x1000000008011324; CHECK-NEXT: btq %rax, %rcx1325; CHECK-NEXT: .LBB13_5: # %exit21326; CHECK-NEXT: retq1327;1328; NOOPT-LABEL: phi_node_trouble:1329; NOOPT: # %bb.0: # %entry1330; NOOPT-NEXT: movq %rdi, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill1331; NOOPT-NEXT: jmp .LBB13_11332; NOOPT-NEXT: .LBB13_1: # %header1333; NOOPT-NEXT: # =>This Inner Loop Header: Depth=11334; NOOPT-NEXT: movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload1335; NOOPT-NEXT: movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill1336; NOOPT-NEXT: cmpq $0, %rax1337; NOOPT-NEXT: je .LBB13_31338; NOOPT-NEXT: # %bb.2: # %loop1339; NOOPT-NEXT: # in Loop: Header=BB13_1 Depth=11340; NOOPT-NEXT: movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload1341; NOOPT-NEXT: movq (%rax), %rax1342; NOOPT-NEXT: movl 8(%rax), %ecx1343; NOOPT-NEXT: movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1344; NOOPT-NEXT: subl $4, %ecx1345; NOOPT-NEXT: movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill1346; NOOPT-NEXT: je .LBB13_11347; NOOPT-NEXT: jmp .LBB13_51348; NOOPT-NEXT: .LBB13_5: # %loop1349; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1350; NOOPT-NEXT: subl $25, %eax1351; NOOPT-NEXT: je .LBB13_41352; NOOPT-NEXT: jmp .LBB13_61353; NOOPT-NEXT: .LBB13_6: # %loop1354; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1355; NOOPT-NEXT: subl $36, %eax1356; NOOPT-NEXT: je .LBB13_41357; NOOPT-NEXT: jmp .LBB13_71358; NOOPT-NEXT: .LBB13_7: # %loop1359; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1360; NOOPT-NEXT: subl $69, %eax1361; NOOPT-NEXT: je .LBB13_41362; NOOPT-NEXT: jmp .LBB13_31363; NOOPT-NEXT: .LBB13_3: # %exit1364; NOOPT-NEXT: retq1365; NOOPT-NEXT: .LBB13_4: # %exit21366; NOOPT-NEXT: retq1367entry:1368 br label %header1369header:1370 %ptr = phi ptr [ %s, %entry ], [ %next, %loop ]1371 %bool = icmp eq ptr %ptr, null1372 br i1 %bool, label %exit, label %loop1373loop:1374 %next = load ptr, ptr %ptr1375 %xptr = getelementptr inbounds %struct.S, ptr %next, i64 0, i32 11376 %x = load i32, ptr %xptr1377 switch i32 %x, label %exit [1378 i32 4, label %header1379 i32 36, label %exit21380 i32 69, label %exit21381 i32 25, label %exit21382 ]1383exit:1384 ret void1385exit2:1386 ret void1387}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: # %entry1395; CHECK-NEXT: retq1396;1397; NOOPT-LABEL: default_only:1398; NOOPT: # %bb.0: # %entry1399; NOOPT-NEXT: jmp .LBB14_21400; NOOPT-NEXT: .LBB14_1: # %return1401; NOOPT-NEXT: retq1402; NOOPT-NEXT: .LBB14_2: # %sw1403; NOOPT-NEXT: jmp .LBB14_11404entry:1405 br label %sw1406return:1407 ret void1408sw: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 the1415; 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: # %entry1419; CHECK-NEXT: cmpb $-9, %dil1420; CHECK-NEXT: ja .LBB15_41421; CHECK-NEXT: # %bb.1: # %entry1422; CHECK-NEXT: movzbl %dil, %eax1423; CHECK-NEXT: jmpq *.LJTI15_0(,%rax,8)1424; CHECK-NEXT: .LBB15_2: # %bb01425; CHECK-NEXT: xorl %edi, %edi1426; CHECK-NEXT: jmp g@PLT # TAILCALL1427; CHECK-NEXT: .LBB15_3: # %bb31428; CHECK-NEXT: movl $1, %edi1429; CHECK-NEXT: jmp g@PLT # TAILCALL1430; CHECK-NEXT: .LBB15_4: # %return1431; CHECK-NEXT: retq1432;1433; NOOPT-LABEL: int_max_table_cluster:1434; NOOPT: # %bb.0: # %entry1435; NOOPT-NEXT: pushq %rax1436; NOOPT-NEXT: .cfi_def_cfa_offset 161437; NOOPT-NEXT: movb %dil, %al1438; NOOPT-NEXT: addb $64, %al1439; NOOPT-NEXT: movzbl %al, %ecx1440; NOOPT-NEXT: # kill: def $rcx killed $ecx1441; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill1442; NOOPT-NEXT: subb $-65, %al1443; NOOPT-NEXT: ja .LBB15_51444; NOOPT-NEXT: # %bb.6: # %entry1445; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload1446; NOOPT-NEXT: movq .LJTI15_0(,%rax,8), %rax1447; NOOPT-NEXT: jmpq *%rax1448; NOOPT-NEXT: .LBB15_1: # %bb01449; NOOPT-NEXT: xorl %edi, %edi1450; NOOPT-NEXT: callq g@PLT1451; NOOPT-NEXT: jmp .LBB15_51452; NOOPT-NEXT: .LBB15_2: # %bb11453; NOOPT-NEXT: movl $1, %edi1454; NOOPT-NEXT: callq g@PLT1455; NOOPT-NEXT: jmp .LBB15_51456; NOOPT-NEXT: .LBB15_3: # %bb21457; NOOPT-NEXT: movl $1, %edi1458; NOOPT-NEXT: callq g@PLT1459; NOOPT-NEXT: jmp .LBB15_51460; NOOPT-NEXT: .LBB15_4: # %bb31461; NOOPT-NEXT: movl $1, %edi1462; NOOPT-NEXT: callq g@PLT1463; NOOPT-NEXT: .LBB15_5: # %return1464; NOOPT-NEXT: popq %rax1465; NOOPT-NEXT: .cfi_def_cfa_offset 81466; NOOPT-NEXT: retq1467entry:1468 switch i8 %x, label %return [1469 i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb01470 i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb01471 i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb01472 i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb01473 i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb01474 i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb01475 i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb01476 i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb01477 i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb01478 i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb01479 i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb01480 i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb01481 i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb01482 i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb01483 i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb01484 i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb01485 i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb01486 i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb01487 i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb01488 i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb01489 i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb01490 i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb01491 i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb01492 i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb01493 i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb01494 i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb01495 i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb01496 i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb01497 i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb01498 i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb01499 i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb01500 i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb01501 i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb11502 i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb11503 i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb11504 i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb11505 i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb11506 i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb11507 i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb11508 i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb11509 i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb21510 i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb21511 i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb21512 i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb21513 i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb31514 i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb31515 ]1516bb0: tail call void @g(i32 0) br label %return1517bb1: tail call void @g(i32 1) br label %return1518bb2: tail call void @g(i32 1) br label %return1519bb3: tail call void @g(i32 1) br label %return1520return: ret void1521}1522 1523 1524; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so1525; 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 bit1527; test on 0,3,6 is unnecessary as all cases cover the range [0, 9]. The range1528; 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: # %entry1532; CHECK-NEXT: cmpl $9, %edi1533; CHECK-NEXT: ja .LBB16_61534; CHECK-NEXT: # %bb.1: # %entry1535; CHECK-NEXT: movl $146, %eax1536; CHECK-NEXT: btl %edi, %eax1537; CHECK-NEXT: jae .LBB16_21538; CHECK-NEXT: # %bb.4: # %bb11539; CHECK-NEXT: movl $1, %edi1540; CHECK-NEXT: jmp g@PLT # TAILCALL1541; CHECK-NEXT: .LBB16_2: # %entry1542; CHECK-NEXT: movl $804, %eax # imm = 0x3241543; CHECK-NEXT: btl %edi, %eax1544; CHECK-NEXT: jae .LBB16_31545; CHECK-NEXT: # %bb.5: # %bb21546; CHECK-NEXT: movl $2, %edi1547; CHECK-NEXT: jmp g@PLT # TAILCALL1548; CHECK-NEXT: .LBB16_3: # %bb01549; CHECK-NEXT: xorl %edi, %edi1550; CHECK-NEXT: jmp g@PLT # TAILCALL1551; CHECK-NEXT: .LBB16_6: # %return1552; CHECK-NEXT: retq1553;1554; NOOPT-LABEL: bt_order_by_weight:1555; NOOPT: # %bb.0: # %entry1556; NOOPT-NEXT: pushq %rax1557; NOOPT-NEXT: .cfi_def_cfa_offset 161558; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1559; NOOPT-NEXT: testl %edi, %edi1560; NOOPT-NEXT: je .LBB16_11561; NOOPT-NEXT: jmp .LBB16_51562; NOOPT-NEXT: .LBB16_5: # %entry1563; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1564; NOOPT-NEXT: subl $1, %eax1565; NOOPT-NEXT: je .LBB16_21566; NOOPT-NEXT: jmp .LBB16_61567; NOOPT-NEXT: .LBB16_6: # %entry1568; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1569; NOOPT-NEXT: subl $2, %eax1570; NOOPT-NEXT: je .LBB16_31571; NOOPT-NEXT: jmp .LBB16_71572; NOOPT-NEXT: .LBB16_7: # %entry1573; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1574; NOOPT-NEXT: subl $3, %eax1575; NOOPT-NEXT: je .LBB16_11576; NOOPT-NEXT: jmp .LBB16_81577; NOOPT-NEXT: .LBB16_8: # %entry1578; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1579; NOOPT-NEXT: subl $4, %eax1580; NOOPT-NEXT: je .LBB16_21581; NOOPT-NEXT: jmp .LBB16_91582; NOOPT-NEXT: .LBB16_9: # %entry1583; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1584; NOOPT-NEXT: subl $5, %eax1585; NOOPT-NEXT: je .LBB16_31586; NOOPT-NEXT: jmp .LBB16_101587; NOOPT-NEXT: .LBB16_10: # %entry1588; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1589; NOOPT-NEXT: subl $6, %eax1590; NOOPT-NEXT: je .LBB16_11591; NOOPT-NEXT: jmp .LBB16_111592; NOOPT-NEXT: .LBB16_11: # %entry1593; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1594; NOOPT-NEXT: subl $7, %eax1595; NOOPT-NEXT: je .LBB16_21596; NOOPT-NEXT: jmp .LBB16_121597; NOOPT-NEXT: .LBB16_12: # %entry1598; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1599; NOOPT-NEXT: addl $-8, %eax1600; NOOPT-NEXT: subl $2, %eax1601; NOOPT-NEXT: jb .LBB16_31602; NOOPT-NEXT: jmp .LBB16_41603; NOOPT-NEXT: .LBB16_1: # %bb01604; NOOPT-NEXT: xorl %edi, %edi1605; NOOPT-NEXT: callq g@PLT1606; NOOPT-NEXT: jmp .LBB16_41607; NOOPT-NEXT: .LBB16_2: # %bb11608; NOOPT-NEXT: movl $1, %edi1609; NOOPT-NEXT: callq g@PLT1610; NOOPT-NEXT: jmp .LBB16_41611; NOOPT-NEXT: .LBB16_3: # %bb21612; NOOPT-NEXT: movl $2, %edi1613; NOOPT-NEXT: callq g@PLT1614; NOOPT-NEXT: .LBB16_4: # %return1615; NOOPT-NEXT: popq %rax1616; NOOPT-NEXT: .cfi_def_cfa_offset 81617; NOOPT-NEXT: retq1618entry:1619 switch i32 %x, label %return [1620 i32 0, label %bb01621 i32 3, label %bb01622 i32 6, label %bb01623 i32 1, label %bb11624 i32 4, label %bb11625 i32 7, label %bb11626 i32 2, label %bb21627 i32 5, label %bb21628 i32 8, label %bb21629 i32 9, label %bb21630 ], !prof !11631bb0: tail call void @g(i32 0) br label %return1632bb1: tail call void @g(i32 1) br label %return1633bb2: tail call void @g(i32 2) br label %return1634return: ret void1635}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 the1649; 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: # %entry1653; CHECK-NEXT: cmpl $200, %edi1654; CHECK-NEXT: jne .LBB17_11655; CHECK-NEXT: .LBB17_3: # %bb01656; CHECK-NEXT: xorl %edi, %edi1657; CHECK-NEXT: jmp g@PLT # TAILCALL1658; CHECK-NEXT: .LBB17_1: # %entry1659; CHECK-NEXT: cmpl $100, %edi1660; CHECK-NEXT: je .LBB17_41661; CHECK-NEXT: # %bb.2: # %entry1662; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C1663; CHECK-NEXT: je .LBB17_31664; CHECK-NEXT: # %bb.5: # %return1665; CHECK-NEXT: retq1666; CHECK-NEXT: .LBB17_4: # %bb11667; CHECK-NEXT: movl $1, %edi1668; CHECK-NEXT: jmp g@PLT # TAILCALL1669;1670; NOOPT-LABEL: order_by_weight_and_fallthrough:1671; NOOPT: # %bb.0: # %entry1672; NOOPT-NEXT: pushq %rax1673; NOOPT-NEXT: .cfi_def_cfa_offset 161674; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1675; NOOPT-NEXT: subl $100, %edi1676; NOOPT-NEXT: je .LBB17_21677; NOOPT-NEXT: jmp .LBB17_41678; NOOPT-NEXT: .LBB17_4: # %entry1679; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1680; NOOPT-NEXT: subl $200, %eax1681; NOOPT-NEXT: je .LBB17_11682; NOOPT-NEXT: jmp .LBB17_51683; NOOPT-NEXT: .LBB17_5: # %entry1684; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1685; NOOPT-NEXT: subl $300, %eax # imm = 0x12C1686; NOOPT-NEXT: jne .LBB17_31687; NOOPT-NEXT: jmp .LBB17_11688; NOOPT-NEXT: .LBB17_1: # %bb01689; NOOPT-NEXT: xorl %edi, %edi1690; NOOPT-NEXT: callq g@PLT1691; NOOPT-NEXT: jmp .LBB17_31692; NOOPT-NEXT: .LBB17_2: # %bb11693; NOOPT-NEXT: movl $1, %edi1694; NOOPT-NEXT: callq g@PLT1695; NOOPT-NEXT: .LBB17_3: # %return1696; NOOPT-NEXT: popq %rax1697; NOOPT-NEXT: .cfi_def_cfa_offset 81698; NOOPT-NEXT: retq1699entry:1700 switch i32 %x, label %return [1701 i32 100, label %bb11702 i32 200, label %bb01703 i32 300, label %bb01704 ], !prof !21705bb0: tail call void @g(i32 0) br label %return1706bb1: tail call void @g(i32 1) br label %return1707return: ret void1708}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: # %entry1725; CHECK-NEXT: cmpl $29, %edi1726; CHECK-NEXT: jg .LBB18_51727; CHECK-NEXT: # %bb.1: # %entry1728; CHECK-NEXT: testl %edi, %edi1729; CHECK-NEXT: jne .LBB18_21730; CHECK-NEXT: # %bb.9: # %bb01731; CHECK-NEXT: xorl %edi, %edi1732; CHECK-NEXT: jmp g@PLT # TAILCALL1733; CHECK-NEXT: .LBB18_5: # %entry1734; CHECK-NEXT: cmpl $50, %edi1735; CHECK-NEXT: jne .LBB18_61736; CHECK-NEXT: # %bb.12: # %bb51737; CHECK-NEXT: movl $5, %edi1738; CHECK-NEXT: jmp g@PLT # TAILCALL1739; CHECK-NEXT: .LBB18_2: # %entry1740; CHECK-NEXT: cmpl $10, %edi1741; CHECK-NEXT: je .LBB18_101742; CHECK-NEXT: # %bb.3: # %entry1743; CHECK-NEXT: cmpl $20, %edi1744; CHECK-NEXT: jne .LBB18_131745; CHECK-NEXT: # %bb.4: # %bb21746; CHECK-NEXT: movl $2, %edi1747; CHECK-NEXT: jmp g@PLT # TAILCALL1748; CHECK-NEXT: .LBB18_6: # %entry1749; CHECK-NEXT: cmpl $30, %edi1750; CHECK-NEXT: je .LBB18_111751; CHECK-NEXT: # %bb.7: # %entry1752; CHECK-NEXT: cmpl $40, %edi1753; CHECK-NEXT: je .LBB18_81754; CHECK-NEXT: .LBB18_13: # %return1755; CHECK-NEXT: retq1756; CHECK-NEXT: .LBB18_10: # %bb11757; CHECK-NEXT: movl $1, %edi1758; CHECK-NEXT: jmp g@PLT # TAILCALL1759; CHECK-NEXT: .LBB18_11: # %bb31760; CHECK-NEXT: movl $3, %edi1761; CHECK-NEXT: jmp g@PLT # TAILCALL1762; CHECK-NEXT: .LBB18_8: # %bb41763; CHECK-NEXT: movl $4, %edi1764; CHECK-NEXT: jmp g@PLT # TAILCALL1765;1766; NOOPT-LABEL: zero_weight_tree:1767; NOOPT: # %bb.0: # %entry1768; NOOPT-NEXT: pushq %rax1769; NOOPT-NEXT: .cfi_def_cfa_offset 161770; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1771; NOOPT-NEXT: testl %edi, %edi1772; NOOPT-NEXT: je .LBB18_11773; NOOPT-NEXT: jmp .LBB18_81774; NOOPT-NEXT: .LBB18_8: # %entry1775; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1776; NOOPT-NEXT: subl $10, %eax1777; NOOPT-NEXT: je .LBB18_21778; NOOPT-NEXT: jmp .LBB18_91779; NOOPT-NEXT: .LBB18_9: # %entry1780; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1781; NOOPT-NEXT: subl $20, %eax1782; NOOPT-NEXT: je .LBB18_31783; NOOPT-NEXT: jmp .LBB18_101784; NOOPT-NEXT: .LBB18_10: # %entry1785; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1786; NOOPT-NEXT: subl $30, %eax1787; NOOPT-NEXT: je .LBB18_41788; NOOPT-NEXT: jmp .LBB18_111789; NOOPT-NEXT: .LBB18_11: # %entry1790; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1791; NOOPT-NEXT: subl $40, %eax1792; NOOPT-NEXT: je .LBB18_51793; NOOPT-NEXT: jmp .LBB18_121794; NOOPT-NEXT: .LBB18_12: # %entry1795; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1796; NOOPT-NEXT: subl $50, %eax1797; NOOPT-NEXT: je .LBB18_61798; NOOPT-NEXT: jmp .LBB18_71799; NOOPT-NEXT: .LBB18_1: # %bb01800; NOOPT-NEXT: xorl %edi, %edi1801; NOOPT-NEXT: callq g@PLT1802; NOOPT-NEXT: jmp .LBB18_71803; NOOPT-NEXT: .LBB18_2: # %bb11804; NOOPT-NEXT: movl $1, %edi1805; NOOPT-NEXT: callq g@PLT1806; NOOPT-NEXT: jmp .LBB18_71807; NOOPT-NEXT: .LBB18_3: # %bb21808; NOOPT-NEXT: movl $2, %edi1809; NOOPT-NEXT: callq g@PLT1810; NOOPT-NEXT: jmp .LBB18_71811; NOOPT-NEXT: .LBB18_4: # %bb31812; NOOPT-NEXT: movl $3, %edi1813; NOOPT-NEXT: callq g@PLT1814; NOOPT-NEXT: jmp .LBB18_71815; NOOPT-NEXT: .LBB18_5: # %bb41816; NOOPT-NEXT: movl $4, %edi1817; NOOPT-NEXT: callq g@PLT1818; NOOPT-NEXT: jmp .LBB18_71819; NOOPT-NEXT: .LBB18_6: # %bb51820; NOOPT-NEXT: movl $5, %edi1821; NOOPT-NEXT: callq g@PLT1822; NOOPT-NEXT: .LBB18_7: # %return1823; NOOPT-NEXT: popq %rax1824; NOOPT-NEXT: .cfi_def_cfa_offset 81825; NOOPT-NEXT: retq1826entry:1827 switch i32 %x, label %return [1828 i32 0, label %bb01829 i32 10, label %bb11830 i32 20, label %bb21831 i32 30, label %bb31832 i32 40, label %bb41833 i32 50, label %bb51834 ], !prof !31835bb0: tail call void @g(i32 0) br label %return1836bb1: tail call void @g(i32 1) br label %return1837bb2: tail call void @g(i32 2) br label %return1838bb3: tail call void @g(i32 3) br label %return1839bb4: tail call void @g(i32 4) br label %return1840bb5: tail call void @g(i32 5) br label %return1841return: ret void1842}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 yield1848; equal-sized sub-trees. When taking weights into account, case 70 becomes the1849; pivot. Since there is room for 3 cases in a leaf, cases 50 and 60 are also1850; 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: # %entry1854; CHECK-NEXT: cmpl $49, %edi1855; CHECK-NEXT: jle .LBB19_11856; CHECK-NEXT: # %bb.11: # %entry1857; CHECK-NEXT: cmpl $70, %edi1858; CHECK-NEXT: jne .LBB19_121859; CHECK-NEXT: .LBB19_14: # %bb61860; CHECK-NEXT: movl $6, %edi1861; CHECK-NEXT: jmp g@PLT # TAILCALL1862; CHECK-NEXT: .LBB19_1: # %entry1863; CHECK-NEXT: cmpl $9, %edi1864; CHECK-NEXT: jg .LBB19_41865; CHECK-NEXT: # %bb.2: # %entry1866; CHECK-NEXT: testl %edi, %edi1867; CHECK-NEXT: jne .LBB19_181868; CHECK-NEXT: # %bb.3: # %bb01869; CHECK-NEXT: xorl %edi, %edi1870; CHECK-NEXT: jmp g@PLT # TAILCALL1871; CHECK-NEXT: .LBB19_4: # %entry1872; CHECK-NEXT: cmpl $29, %edi1873; CHECK-NEXT: jg .LBB19_81874; CHECK-NEXT: # %bb.5: # %entry1875; CHECK-NEXT: cmpl $10, %edi1876; CHECK-NEXT: je .LBB19_151877; CHECK-NEXT: # %bb.6: # %entry1878; CHECK-NEXT: cmpl $20, %edi1879; CHECK-NEXT: jne .LBB19_181880; CHECK-NEXT: # %bb.7: # %bb21881; CHECK-NEXT: movl $2, %edi1882; CHECK-NEXT: jmp g@PLT # TAILCALL1883; CHECK-NEXT: .LBB19_12: # %entry1884; CHECK-NEXT: cmpl $50, %edi1885; CHECK-NEXT: je .LBB19_171886; CHECK-NEXT: # %bb.13: # %entry1887; CHECK-NEXT: cmpl $60, %edi1888; CHECK-NEXT: je .LBB19_141889; CHECK-NEXT: jmp .LBB19_181890; CHECK-NEXT: .LBB19_8: # %entry1891; CHECK-NEXT: cmpl $30, %edi1892; CHECK-NEXT: je .LBB19_161893; CHECK-NEXT: # %bb.9: # %entry1894; CHECK-NEXT: cmpl $40, %edi1895; CHECK-NEXT: jne .LBB19_181896; CHECK-NEXT: # %bb.10: # %bb41897; CHECK-NEXT: movl $4, %edi1898; CHECK-NEXT: jmp g@PLT # TAILCALL1899; CHECK-NEXT: .LBB19_15: # %bb11900; CHECK-NEXT: movl $1, %edi1901; CHECK-NEXT: jmp g@PLT # TAILCALL1902; CHECK-NEXT: .LBB19_16: # %bb31903; CHECK-NEXT: movl $3, %edi1904; CHECK-NEXT: jmp g@PLT # TAILCALL1905; CHECK-NEXT: .LBB19_18: # %return1906; CHECK-NEXT: retq1907; CHECK-NEXT: .LBB19_17: # %bb51908; CHECK-NEXT: movl $5, %edi1909; CHECK-NEXT: jmp g@PLT # TAILCALL1910;1911; NOOPT-LABEL: left_leaning_weight_balanced_tree:1912; NOOPT: # %bb.0: # %entry1913; NOOPT-NEXT: pushq %rax1914; NOOPT-NEXT: .cfi_def_cfa_offset 161915; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill1916; NOOPT-NEXT: testl %edi, %edi1917; NOOPT-NEXT: je .LBB19_11918; NOOPT-NEXT: jmp .LBB19_91919; NOOPT-NEXT: .LBB19_9: # %entry1920; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1921; NOOPT-NEXT: subl $10, %eax1922; NOOPT-NEXT: je .LBB19_21923; NOOPT-NEXT: jmp .LBB19_101924; NOOPT-NEXT: .LBB19_10: # %entry1925; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1926; NOOPT-NEXT: subl $20, %eax1927; NOOPT-NEXT: je .LBB19_31928; NOOPT-NEXT: jmp .LBB19_111929; NOOPT-NEXT: .LBB19_11: # %entry1930; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1931; NOOPT-NEXT: subl $30, %eax1932; NOOPT-NEXT: je .LBB19_41933; NOOPT-NEXT: jmp .LBB19_121934; NOOPT-NEXT: .LBB19_12: # %entry1935; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1936; NOOPT-NEXT: subl $40, %eax1937; NOOPT-NEXT: je .LBB19_51938; NOOPT-NEXT: jmp .LBB19_131939; NOOPT-NEXT: .LBB19_13: # %entry1940; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1941; NOOPT-NEXT: subl $50, %eax1942; NOOPT-NEXT: je .LBB19_61943; NOOPT-NEXT: jmp .LBB19_141944; NOOPT-NEXT: .LBB19_14: # %entry1945; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1946; NOOPT-NEXT: subl $60, %eax1947; NOOPT-NEXT: je .LBB19_71948; NOOPT-NEXT: jmp .LBB19_151949; NOOPT-NEXT: .LBB19_15: # %entry1950; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload1951; NOOPT-NEXT: subl $70, %eax1952; NOOPT-NEXT: je .LBB19_71953; NOOPT-NEXT: jmp .LBB19_81954; NOOPT-NEXT: .LBB19_1: # %bb01955; NOOPT-NEXT: xorl %edi, %edi1956; NOOPT-NEXT: callq g@PLT1957; NOOPT-NEXT: jmp .LBB19_81958; NOOPT-NEXT: .LBB19_2: # %bb11959; NOOPT-NEXT: movl $1, %edi1960; NOOPT-NEXT: callq g@PLT1961; NOOPT-NEXT: jmp .LBB19_81962; NOOPT-NEXT: .LBB19_3: # %bb21963; NOOPT-NEXT: movl $2, %edi1964; NOOPT-NEXT: callq g@PLT1965; NOOPT-NEXT: jmp .LBB19_81966; NOOPT-NEXT: .LBB19_4: # %bb31967; NOOPT-NEXT: movl $3, %edi1968; NOOPT-NEXT: callq g@PLT1969; NOOPT-NEXT: jmp .LBB19_81970; NOOPT-NEXT: .LBB19_5: # %bb41971; NOOPT-NEXT: movl $4, %edi1972; NOOPT-NEXT: callq g@PLT1973; NOOPT-NEXT: jmp .LBB19_81974; NOOPT-NEXT: .LBB19_6: # %bb51975; NOOPT-NEXT: movl $5, %edi1976; NOOPT-NEXT: callq g@PLT1977; NOOPT-NEXT: jmp .LBB19_81978; NOOPT-NEXT: .LBB19_7: # %bb61979; NOOPT-NEXT: movl $6, %edi1980; NOOPT-NEXT: callq g@PLT1981; NOOPT-NEXT: .LBB19_8: # %return1982; NOOPT-NEXT: popq %rax1983; NOOPT-NEXT: .cfi_def_cfa_offset 81984; NOOPT-NEXT: retq1985entry:1986 switch i32 %x, label %return [1987 i32 0, label %bb01988 i32 10, label %bb11989 i32 20, label %bb21990 i32 30, label %bb31991 i32 40, label %bb41992 i32 50, label %bb51993 i32 60, label %bb61994 i32 70, label %bb61995 ], !prof !41996bb0: tail call void @g(i32 0) br label %return1997bb1: tail call void @g(i32 1) br label %return1998bb2: tail call void @g(i32 2) br label %return1999bb3: tail call void @g(i32 3) br label %return2000bb4: tail call void @g(i32 4) br label %return2001bb5: tail call void @g(i32 5) br label %return2002bb6: tail call void @g(i32 6) br label %return2003bb7: tail call void @g(i32 7) br label %return2004return: ret void2005}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 it2011; would have on the right. Case 60 would have the same rank on both sides, so is2012; 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: # %entry2016; CHECK-NEXT: cmpl $59, %edi2017; CHECK-NEXT: jle .LBB20_12018; CHECK-NEXT: # %bb.10: # %entry2019; CHECK-NEXT: cmpl $70, %edi2020; CHECK-NEXT: jne .LBB20_112021; CHECK-NEXT: .LBB20_12: # %bb62022; CHECK-NEXT: movl $6, %edi2023; CHECK-NEXT: jmp g@PLT # TAILCALL2024; CHECK-NEXT: .LBB20_1: # %entry2025; CHECK-NEXT: cmpl $29, %edi2026; CHECK-NEXT: jle .LBB20_22027; CHECK-NEXT: # %bb.6: # %entry2028; CHECK-NEXT: cmpl $50, %edi2029; CHECK-NEXT: jne .LBB20_72030; CHECK-NEXT: # %bb.16: # %bb52031; CHECK-NEXT: movl $5, %edi2032; CHECK-NEXT: jmp g@PLT # TAILCALL2033; CHECK-NEXT: .LBB20_11: # %entry2034; CHECK-NEXT: cmpl $60, %edi2035; CHECK-NEXT: je .LBB20_122036; CHECK-NEXT: jmp .LBB20_172037; CHECK-NEXT: .LBB20_2: # %entry2038; CHECK-NEXT: testl %edi, %edi2039; CHECK-NEXT: jne .LBB20_32040; CHECK-NEXT: # %bb.13: # %bb02041; CHECK-NEXT: xorl %edi, %edi2042; CHECK-NEXT: jmp g@PLT # TAILCALL2043; CHECK-NEXT: .LBB20_3: # %entry2044; CHECK-NEXT: cmpl $10, %edi2045; CHECK-NEXT: je .LBB20_142046; CHECK-NEXT: # %bb.4: # %entry2047; CHECK-NEXT: cmpl $20, %edi2048; CHECK-NEXT: jne .LBB20_172049; CHECK-NEXT: # %bb.5: # %bb22050; CHECK-NEXT: movl $2, %edi2051; CHECK-NEXT: jmp g@PLT # TAILCALL2052; CHECK-NEXT: .LBB20_7: # %entry2053; CHECK-NEXT: cmpl $30, %edi2054; CHECK-NEXT: je .LBB20_152055; CHECK-NEXT: # %bb.8: # %entry2056; CHECK-NEXT: cmpl $40, %edi2057; CHECK-NEXT: jne .LBB20_172058; CHECK-NEXT: # %bb.9: # %bb42059; CHECK-NEXT: movl $4, %edi2060; CHECK-NEXT: jmp g@PLT # TAILCALL2061; CHECK-NEXT: .LBB20_14: # %bb12062; CHECK-NEXT: movl $1, %edi2063; CHECK-NEXT: jmp g@PLT # TAILCALL2064; CHECK-NEXT: .LBB20_15: # %bb32065; CHECK-NEXT: movl $3, %edi2066; CHECK-NEXT: jmp g@PLT # TAILCALL2067; CHECK-NEXT: .LBB20_17: # %return2068; CHECK-NEXT: retq2069;2070; NOOPT-LABEL: left_leaning_weight_balanced_tree2:2071; NOOPT: # %bb.0: # %entry2072; NOOPT-NEXT: pushq %rax2073; NOOPT-NEXT: .cfi_def_cfa_offset 162074; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2075; NOOPT-NEXT: testl %edi, %edi2076; NOOPT-NEXT: je .LBB20_12077; NOOPT-NEXT: jmp .LBB20_92078; NOOPT-NEXT: .LBB20_9: # %entry2079; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2080; NOOPT-NEXT: subl $10, %eax2081; NOOPT-NEXT: je .LBB20_22082; NOOPT-NEXT: jmp .LBB20_102083; NOOPT-NEXT: .LBB20_10: # %entry2084; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2085; NOOPT-NEXT: subl $20, %eax2086; NOOPT-NEXT: je .LBB20_32087; NOOPT-NEXT: jmp .LBB20_112088; NOOPT-NEXT: .LBB20_11: # %entry2089; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2090; NOOPT-NEXT: subl $30, %eax2091; NOOPT-NEXT: je .LBB20_42092; NOOPT-NEXT: jmp .LBB20_122093; NOOPT-NEXT: .LBB20_12: # %entry2094; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2095; NOOPT-NEXT: subl $40, %eax2096; NOOPT-NEXT: je .LBB20_52097; NOOPT-NEXT: jmp .LBB20_132098; NOOPT-NEXT: .LBB20_13: # %entry2099; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2100; NOOPT-NEXT: subl $50, %eax2101; NOOPT-NEXT: je .LBB20_62102; NOOPT-NEXT: jmp .LBB20_142103; NOOPT-NEXT: .LBB20_14: # %entry2104; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2105; NOOPT-NEXT: subl $60, %eax2106; NOOPT-NEXT: je .LBB20_72107; NOOPT-NEXT: jmp .LBB20_152108; NOOPT-NEXT: .LBB20_15: # %entry2109; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2110; NOOPT-NEXT: subl $70, %eax2111; NOOPT-NEXT: je .LBB20_72112; NOOPT-NEXT: jmp .LBB20_82113; NOOPT-NEXT: .LBB20_1: # %bb02114; NOOPT-NEXT: xorl %edi, %edi2115; NOOPT-NEXT: callq g@PLT2116; NOOPT-NEXT: jmp .LBB20_82117; NOOPT-NEXT: .LBB20_2: # %bb12118; NOOPT-NEXT: movl $1, %edi2119; NOOPT-NEXT: callq g@PLT2120; NOOPT-NEXT: jmp .LBB20_82121; NOOPT-NEXT: .LBB20_3: # %bb22122; NOOPT-NEXT: movl $2, %edi2123; NOOPT-NEXT: callq g@PLT2124; NOOPT-NEXT: jmp .LBB20_82125; NOOPT-NEXT: .LBB20_4: # %bb32126; NOOPT-NEXT: movl $3, %edi2127; NOOPT-NEXT: callq g@PLT2128; NOOPT-NEXT: jmp .LBB20_82129; NOOPT-NEXT: .LBB20_5: # %bb42130; NOOPT-NEXT: movl $4, %edi2131; NOOPT-NEXT: callq g@PLT2132; NOOPT-NEXT: jmp .LBB20_82133; NOOPT-NEXT: .LBB20_6: # %bb52134; NOOPT-NEXT: movl $5, %edi2135; NOOPT-NEXT: callq g@PLT2136; NOOPT-NEXT: jmp .LBB20_82137; NOOPT-NEXT: .LBB20_7: # %bb62138; NOOPT-NEXT: movl $6, %edi2139; NOOPT-NEXT: callq g@PLT2140; NOOPT-NEXT: .LBB20_8: # %return2141; NOOPT-NEXT: popq %rax2142; NOOPT-NEXT: .cfi_def_cfa_offset 82143; NOOPT-NEXT: retq2144entry:2145 switch i32 %x, label %return [2146 i32 0, label %bb02147 i32 10, label %bb12148 i32 20, label %bb22149 i32 30, label %bb32150 i32 40, label %bb42151 i32 50, label %bb52152 i32 60, label %bb62153 i32 70, label %bb62154 ], !prof !52155bb0: tail call void @g(i32 0) br label %return2156bb1: tail call void @g(i32 1) br label %return2157bb2: tail call void @g(i32 2) br label %return2158bb3: tail call void @g(i32 3) br label %return2159bb4: tail call void @g(i32 4) br label %return2160bb5: tail call void @g(i32 5) br label %return2161bb6: tail call void @g(i32 6) br label %return2162bb7: tail call void @g(i32 7) br label %return2163return: ret void2164}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: # %entry2173; CHECK-NEXT: cmpl $19, %edi2174; CHECK-NEXT: jg .LBB21_42175; CHECK-NEXT: # %bb.1: # %entry2176; CHECK-NEXT: testl %edi, %edi2177; CHECK-NEXT: jne .LBB21_22178; CHECK-NEXT: # %bb.13: # %bb02179; CHECK-NEXT: xorl %edi, %edi2180; CHECK-NEXT: jmp g@PLT # TAILCALL2181; CHECK-NEXT: .LBB21_4: # %entry2182; CHECK-NEXT: cmpl $49, %edi2183; CHECK-NEXT: jle .LBB21_52184; CHECK-NEXT: # %bb.9: # %entry2185; CHECK-NEXT: cmpl $70, %edi2186; CHECK-NEXT: jne .LBB21_102187; CHECK-NEXT: .LBB21_12: # %bb62188; CHECK-NEXT: movl $6, %edi2189; CHECK-NEXT: jmp g@PLT # TAILCALL2190; CHECK-NEXT: .LBB21_5: # %entry2191; CHECK-NEXT: cmpl $20, %edi2192; CHECK-NEXT: je .LBB21_142193; CHECK-NEXT: # %bb.6: # %entry2194; CHECK-NEXT: cmpl $30, %edi2195; CHECK-NEXT: je .LBB21_152196; CHECK-NEXT: # %bb.7: # %entry2197; CHECK-NEXT: cmpl $40, %edi2198; CHECK-NEXT: jne .LBB21_172199; CHECK-NEXT: # %bb.8: # %bb42200; CHECK-NEXT: movl $4, %edi2201; CHECK-NEXT: jmp g@PLT # TAILCALL2202; CHECK-NEXT: .LBB21_10: # %entry2203; CHECK-NEXT: cmpl $50, %edi2204; CHECK-NEXT: je .LBB21_162205; CHECK-NEXT: # %bb.11: # %entry2206; CHECK-NEXT: cmpl $60, %edi2207; CHECK-NEXT: je .LBB21_122208; CHECK-NEXT: jmp .LBB21_172209; CHECK-NEXT: .LBB21_14: # %bb22210; CHECK-NEXT: movl $2, %edi2211; CHECK-NEXT: jmp g@PLT # TAILCALL2212; CHECK-NEXT: .LBB21_15: # %bb32213; CHECK-NEXT: movl $3, %edi2214; CHECK-NEXT: jmp g@PLT # TAILCALL2215; CHECK-NEXT: .LBB21_2: # %entry2216; CHECK-NEXT: cmpl $10, %edi2217; CHECK-NEXT: jne .LBB21_172218; CHECK-NEXT: # %bb.3: # %bb12219; CHECK-NEXT: movl $1, %edi2220; CHECK-NEXT: jmp g@PLT # TAILCALL2221; CHECK-NEXT: .LBB21_17: # %return2222; CHECK-NEXT: retq2223; CHECK-NEXT: .LBB21_16: # %bb52224; CHECK-NEXT: movl $5, %edi2225; CHECK-NEXT: jmp g@PLT # TAILCALL2226;2227; NOOPT-LABEL: right_leaning_weight_balanced_tree:2228; NOOPT: # %bb.0: # %entry2229; NOOPT-NEXT: pushq %rax2230; NOOPT-NEXT: .cfi_def_cfa_offset 162231; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2232; NOOPT-NEXT: testl %edi, %edi2233; NOOPT-NEXT: je .LBB21_12234; NOOPT-NEXT: jmp .LBB21_92235; NOOPT-NEXT: .LBB21_9: # %entry2236; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2237; NOOPT-NEXT: subl $10, %eax2238; NOOPT-NEXT: je .LBB21_22239; NOOPT-NEXT: jmp .LBB21_102240; NOOPT-NEXT: .LBB21_10: # %entry2241; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2242; NOOPT-NEXT: subl $20, %eax2243; NOOPT-NEXT: je .LBB21_32244; NOOPT-NEXT: jmp .LBB21_112245; NOOPT-NEXT: .LBB21_11: # %entry2246; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2247; NOOPT-NEXT: subl $30, %eax2248; NOOPT-NEXT: je .LBB21_42249; NOOPT-NEXT: jmp .LBB21_122250; NOOPT-NEXT: .LBB21_12: # %entry2251; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2252; NOOPT-NEXT: subl $40, %eax2253; NOOPT-NEXT: je .LBB21_52254; NOOPT-NEXT: jmp .LBB21_132255; NOOPT-NEXT: .LBB21_13: # %entry2256; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2257; NOOPT-NEXT: subl $50, %eax2258; NOOPT-NEXT: je .LBB21_62259; NOOPT-NEXT: jmp .LBB21_142260; NOOPT-NEXT: .LBB21_14: # %entry2261; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2262; NOOPT-NEXT: subl $60, %eax2263; NOOPT-NEXT: je .LBB21_72264; NOOPT-NEXT: jmp .LBB21_152265; NOOPT-NEXT: .LBB21_15: # %entry2266; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2267; NOOPT-NEXT: subl $70, %eax2268; NOOPT-NEXT: je .LBB21_72269; NOOPT-NEXT: jmp .LBB21_82270; NOOPT-NEXT: .LBB21_1: # %bb02271; NOOPT-NEXT: xorl %edi, %edi2272; NOOPT-NEXT: callq g@PLT2273; NOOPT-NEXT: jmp .LBB21_82274; NOOPT-NEXT: .LBB21_2: # %bb12275; NOOPT-NEXT: movl $1, %edi2276; NOOPT-NEXT: callq g@PLT2277; NOOPT-NEXT: jmp .LBB21_82278; NOOPT-NEXT: .LBB21_3: # %bb22279; NOOPT-NEXT: movl $2, %edi2280; NOOPT-NEXT: callq g@PLT2281; NOOPT-NEXT: jmp .LBB21_82282; NOOPT-NEXT: .LBB21_4: # %bb32283; NOOPT-NEXT: movl $3, %edi2284; NOOPT-NEXT: callq g@PLT2285; NOOPT-NEXT: jmp .LBB21_82286; NOOPT-NEXT: .LBB21_5: # %bb42287; NOOPT-NEXT: movl $4, %edi2288; NOOPT-NEXT: callq g@PLT2289; NOOPT-NEXT: jmp .LBB21_82290; NOOPT-NEXT: .LBB21_6: # %bb52291; NOOPT-NEXT: movl $5, %edi2292; NOOPT-NEXT: callq g@PLT2293; NOOPT-NEXT: jmp .LBB21_82294; NOOPT-NEXT: .LBB21_7: # %bb62295; NOOPT-NEXT: movl $6, %edi2296; NOOPT-NEXT: callq g@PLT2297; NOOPT-NEXT: .LBB21_8: # %return2298; NOOPT-NEXT: popq %rax2299; NOOPT-NEXT: .cfi_def_cfa_offset 82300; NOOPT-NEXT: retq2301entry:2302 switch i32 %x, label %return [2303 i32 0, label %bb02304 i32 10, label %bb12305 i32 20, label %bb22306 i32 30, label %bb32307 i32 40, label %bb42308 i32 50, label %bb52309 i32 60, label %bb62310 i32 70, label %bb62311 ], !prof !62312bb0: tail call void @g(i32 0) br label %return2313bb1: tail call void @g(i32 1) br label %return2314bb2: tail call void @g(i32 2) br label %return2315bb3: tail call void @g(i32 3) br label %return2316bb4: tail call void @g(i32 4) br label %return2317bb5: tail call void @g(i32 5) br label %return2318bb6: tail call void @g(i32 6) br label %return2319bb7: tail call void @g(i32 7) br label %return2320return: ret void2321}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 on2327; the left and {200,300} on the right. However, the jump table weights as much2328; 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: # %entry2332; CHECK-NEXT: cmpl $99, %edi2333; CHECK-NEXT: jg .LBB22_32334; CHECK-NEXT: # %bb.1: # %entry2335; CHECK-NEXT: cmpl $3, %edi2336; CHECK-NEXT: ja .LBB22_102337; CHECK-NEXT: # %bb.2: # %entry2338; CHECK-NEXT: movl %edi, %eax2339; CHECK-NEXT: jmpq *.LJTI22_0(,%rax,8)2340; CHECK-NEXT: .LBB22_9: # %bb32341; CHECK-NEXT: movl $3, %edi2342; CHECK-NEXT: jmp g@PLT # TAILCALL2343; CHECK-NEXT: .LBB22_3: # %entry2344; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C2345; CHECK-NEXT: je .LBB22_82346; CHECK-NEXT: # %bb.4: # %entry2347; CHECK-NEXT: cmpl $200, %edi2348; CHECK-NEXT: je .LBB22_72349; CHECK-NEXT: # %bb.5: # %entry2350; CHECK-NEXT: cmpl $100, %edi2351; CHECK-NEXT: jne .LBB22_102352; CHECK-NEXT: .LBB22_6: # %bb02353; CHECK-NEXT: xorl %edi, %edi2354; CHECK-NEXT: jmp g@PLT # TAILCALL2355; CHECK-NEXT: .LBB22_8: # %bb22356; CHECK-NEXT: movl $2, %edi2357; CHECK-NEXT: jmp g@PLT # TAILCALL2358; CHECK-NEXT: .LBB22_7: # %bb12359; CHECK-NEXT: movl $1, %edi2360; CHECK-NEXT: jmp g@PLT # TAILCALL2361; CHECK-NEXT: .LBB22_10: # %return2362; CHECK-NEXT: retq2363;2364; NOOPT-LABEL: jump_table_affects_balance:2365; NOOPT: # %bb.0: # %entry2366; NOOPT-NEXT: pushq %rax2367; NOOPT-NEXT: .cfi_def_cfa_offset 162368; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2369; NOOPT-NEXT: testl %edi, %edi2370; NOOPT-NEXT: je .LBB22_12371; NOOPT-NEXT: jmp .LBB22_62372; NOOPT-NEXT: .LBB22_6: # %entry2373; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2374; NOOPT-NEXT: subl $1, %eax2375; NOOPT-NEXT: je .LBB22_22376; NOOPT-NEXT: jmp .LBB22_72377; NOOPT-NEXT: .LBB22_7: # %entry2378; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2379; NOOPT-NEXT: subl $2, %eax2380; NOOPT-NEXT: je .LBB22_32381; NOOPT-NEXT: jmp .LBB22_82382; NOOPT-NEXT: .LBB22_8: # %entry2383; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2384; NOOPT-NEXT: subl $3, %eax2385; NOOPT-NEXT: je .LBB22_42386; NOOPT-NEXT: jmp .LBB22_92387; NOOPT-NEXT: .LBB22_9: # %entry2388; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2389; NOOPT-NEXT: subl $100, %eax2390; NOOPT-NEXT: je .LBB22_12391; NOOPT-NEXT: jmp .LBB22_102392; NOOPT-NEXT: .LBB22_10: # %entry2393; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2394; NOOPT-NEXT: subl $200, %eax2395; NOOPT-NEXT: je .LBB22_22396; NOOPT-NEXT: jmp .LBB22_112397; NOOPT-NEXT: .LBB22_11: # %entry2398; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2399; NOOPT-NEXT: subl $300, %eax # imm = 0x12C2400; NOOPT-NEXT: je .LBB22_32401; NOOPT-NEXT: jmp .LBB22_52402; NOOPT-NEXT: .LBB22_1: # %bb02403; NOOPT-NEXT: xorl %edi, %edi2404; NOOPT-NEXT: callq g@PLT2405; NOOPT-NEXT: jmp .LBB22_52406; NOOPT-NEXT: .LBB22_2: # %bb12407; NOOPT-NEXT: movl $1, %edi2408; NOOPT-NEXT: callq g@PLT2409; NOOPT-NEXT: jmp .LBB22_52410; NOOPT-NEXT: .LBB22_3: # %bb22411; NOOPT-NEXT: movl $2, %edi2412; NOOPT-NEXT: callq g@PLT2413; NOOPT-NEXT: jmp .LBB22_52414; NOOPT-NEXT: .LBB22_4: # %bb32415; NOOPT-NEXT: movl $3, %edi2416; NOOPT-NEXT: callq g@PLT2417; NOOPT-NEXT: .LBB22_5: # %return2418; NOOPT-NEXT: popq %rax2419; NOOPT-NEXT: .cfi_def_cfa_offset 82420; NOOPT-NEXT: retq2421entry:2422 switch i32 %x, label %return [2423 ; Jump table:2424 i32 0, label %bb02425 i32 1, label %bb12426 i32 2, label %bb22427 i32 3, label %bb32428 2429 i32 100, label %bb02430 i32 200, label %bb12431 i32 300, label %bb22432 ]2433bb0: tail call void @g(i32 0) br label %return2434bb1: tail call void @g(i32 1) br label %return2435bb2: tail call void @g(i32 2) br label %return2436bb3: tail call void @g(i32 3) br label %return2437return: ret void2438}2439 2440 2441; Don't assert due to truncating the bitwidth (64) to i4 when checking2442; that the bit-test range fits in a word.2443define void @pr23738(i4 %x) {2444; CHECK-LABEL: pr23738:2445; CHECK: # %bb.0: # %entry2446; CHECK-NEXT: movl %edi, %eax2447; CHECK-NEXT: andb $15, %al2448; CHECK-NEXT: cmpb $11, %al2449; CHECK-NEXT: ja .LBB23_22450; CHECK-NEXT: # %bb.1: # %entry2451; CHECK-NEXT: andl $15, %edi2452; CHECK-NEXT: movl $2051, %eax # imm = 0x8032453; CHECK-NEXT: btl %edi, %eax2454; CHECK-NEXT: jae .LBB23_22455; CHECK-NEXT: # %bb.3: # %bb12456; CHECK-NEXT: movl $1, %edi2457; CHECK-NEXT: jmp g@PLT # TAILCALL2458; CHECK-NEXT: .LBB23_2: # %bb02459; CHECK-NEXT: xorl %edi, %edi2460; CHECK-NEXT: jmp g@PLT # TAILCALL2461;2462; NOOPT-LABEL: pr23738:2463; NOOPT: # %bb.0: # %entry2464; NOOPT-NEXT: pushq %rax2465; NOOPT-NEXT: .cfi_def_cfa_offset 162466; NOOPT-NEXT: movb %dil, %al2467; NOOPT-NEXT: movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill2468; NOOPT-NEXT: andb $15, %al2469; NOOPT-NEXT: subb $11, %al2470; NOOPT-NEXT: je .LBB23_22471; NOOPT-NEXT: jmp .LBB23_42472; NOOPT-NEXT: .LBB23_4: # %entry2473; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload2474; NOOPT-NEXT: andb $15, %al2475; NOOPT-NEXT: subb $2, %al2476; NOOPT-NEXT: jb .LBB23_22477; NOOPT-NEXT: jmp .LBB23_12478; NOOPT-NEXT: .LBB23_1: # %bb02479; NOOPT-NEXT: xorl %edi, %edi2480; NOOPT-NEXT: callq g@PLT2481; NOOPT-NEXT: jmp .LBB23_32482; NOOPT-NEXT: .LBB23_2: # %bb12483; NOOPT-NEXT: movl $1, %edi2484; NOOPT-NEXT: callq g@PLT2485; NOOPT-NEXT: .LBB23_3: # %return2486; NOOPT-NEXT: popq %rax2487; NOOPT-NEXT: .cfi_def_cfa_offset 82488; NOOPT-NEXT: retq2489entry:2490 switch i4 %x, label %bb0 [2491 i4 0, label %bb12492 i4 1, label %bb12493 i4 -5, label %bb12494 ]2495bb0: tail call void @g(i32 0) br label %return2496bb1: tail call void @g(i32 1) br label %return2497return: ret void2498}2499 2500 2501; The switch is lowered with bit tests. Since the case range is contiguous, the2502; second bit test is redundant and can be skipped. Check that we don't update2503; the phi node with an incoming value from the MBB of the skipped bit test2504; (-verify-machine-instrs cathces this).2505define i32 @pr27135(i32 %i) {2506; CHECK-LABEL: pr27135:2507; CHECK: # %bb.0: # %entry2508; CHECK-NEXT: xorl %eax, %eax2509; CHECK-NEXT: testb %al, %al2510; CHECK-NEXT: jne .LBB24_52511; CHECK-NEXT: # %bb.1: # %sw2512; CHECK-NEXT: movl $1, %eax2513; CHECK-NEXT: addl $-96, %edi2514; CHECK-NEXT: cmpl $5, %edi2515; CHECK-NEXT: jbe .LBB24_22516; CHECK-NEXT: .LBB24_5: # %end2517; CHECK-NEXT: retq2518; CHECK-NEXT: .LBB24_2: # %sw2519; CHECK-NEXT: movl $19, %eax2520; CHECK-NEXT: btl %edi, %eax2521; CHECK-NEXT: jae .LBB24_32522; CHECK-NEXT: # %bb.4: # %sw.bb22523; CHECK-NEXT: .LBB24_3: # %sw.bb2524;2525; NOOPT-LABEL: pr27135:2526; NOOPT: # %bb.0: # %entry2527; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2528; NOOPT-NEXT: xorl %eax, %eax2529; NOOPT-NEXT: # implicit-def: $cl2530; NOOPT-NEXT: testb $1, %cl2531; NOOPT-NEXT: movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2532; NOOPT-NEXT: jne .LBB24_12533; NOOPT-NEXT: jmp .LBB24_42534; NOOPT-NEXT: .LBB24_1: # %sw2535; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2536; NOOPT-NEXT: movl $1, %ecx2537; NOOPT-NEXT: movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2538; NOOPT-NEXT: addl $-96, %eax2539; NOOPT-NEXT: subl $2, %eax2540; NOOPT-NEXT: jb .LBB24_32541; NOOPT-NEXT: jmp .LBB24_52542; NOOPT-NEXT: .LBB24_5: # %sw2543; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2544; NOOPT-NEXT: addl $-98, %eax2545; NOOPT-NEXT: subl $2, %eax2546; NOOPT-NEXT: jb .LBB24_22547; NOOPT-NEXT: jmp .LBB24_62548; NOOPT-NEXT: .LBB24_6: # %sw2549; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2550; NOOPT-NEXT: subl $100, %eax2551; NOOPT-NEXT: je .LBB24_32552; NOOPT-NEXT: jmp .LBB24_72553; NOOPT-NEXT: .LBB24_7: # %sw2554; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2555; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %ecx # 4-byte Reload2556; NOOPT-NEXT: subl $101, %ecx2557; NOOPT-NEXT: movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill2558; NOOPT-NEXT: jne .LBB24_42559; NOOPT-NEXT: jmp .LBB24_22560; NOOPT-NEXT: .LBB24_2: # %sw.bb2561; NOOPT-NEXT: .LBB24_3: # %sw.bb22562; NOOPT-NEXT: .LBB24_4: # %end2563; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload2564; NOOPT-NEXT: retq2565entry:2566 br i1 poison, label %sw, label %end2567sw:2568 switch i32 %i, label %end [2569 i32 99, label %sw.bb2570 i32 98, label %sw.bb2571 i32 101, label %sw.bb2572 i32 97, label %sw.bb22573 i32 96, label %sw.bb22574 i32 100, label %sw.bb22575 ]2576sw.bb:2577 unreachable2578sw.bb2:2579 unreachable2580end:2581 %p = phi i32 [ 1, %sw ], [ 0, %entry ]2582 ret i32 %p2583}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: # %entry2591; CHECK-NEXT: addl $-4, %edi2592; CHECK-NEXT: cmpl $3, %edi2593; CHECK-NEXT: jae .LBB25_12594; CHECK-NEXT: # %bb.2: # %bb22595; CHECK-NEXT: movl $1, %edi2596; CHECK-NEXT: jmp g@PLT # TAILCALL2597; CHECK-NEXT: .LBB25_1: # %bb12598; CHECK-NEXT: xorl %edi, %edi2599; CHECK-NEXT: jmp g@PLT # TAILCALL2600;2601; NOOPT-LABEL: range_with_unreachable_fallthrough:2602; NOOPT: # %bb.0: # %entry2603; NOOPT-NEXT: pushq %rax2604; NOOPT-NEXT: .cfi_def_cfa_offset 162605; NOOPT-NEXT: movl %edi, %eax2606; NOOPT-NEXT: decl %eax2607; NOOPT-NEXT: subl $3, %eax2608; NOOPT-NEXT: jb .LBB25_12609; NOOPT-NEXT: jmp .LBB25_52610; NOOPT-NEXT: .LBB25_5: # %entry2611; NOOPT-NEXT: jmp .LBB25_22612; NOOPT-NEXT: .LBB25_1: # %bb12613; NOOPT-NEXT: xorl %edi, %edi2614; NOOPT-NEXT: callq g@PLT2615; NOOPT-NEXT: jmp .LBB25_42616; NOOPT-NEXT: .LBB25_2: # %bb22617; NOOPT-NEXT: movl $1, %edi2618; NOOPT-NEXT: callq g@PLT2619; NOOPT-NEXT: jmp .LBB25_42620; NOOPT-NEXT: # %bb.3: # %default2621; NOOPT-NEXT: .cfi_def_cfa_offset 82622; NOOPT-NEXT: .LBB25_4: # %return2623; NOOPT-NEXT: .cfi_def_cfa_offset 162624; NOOPT-NEXT: popq %rax2625; NOOPT-NEXT: .cfi_def_cfa_offset 82626; NOOPT-NEXT: retq2627entry:2628 switch i32 %i, label %default [2629 i32 1, label %bb12630 i32 2, label %bb12631 i32 3, label %bb12632 i32 4, label %bb22633 i32 5, label %bb22634 i32 6, label %bb22635 ]2636bb1: tail call void @g(i32 0) br label %return2637bb2: tail call void @g(i32 1) br label %return2638default: unreachable2639 2640return:2641 ret void2642}2643 2644 2645; A switch over a small type (i8) should be extended to avoid truncation2646; 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 $rdi2651; CHECK-NEXT: andl $127, %edi2652; CHECK-NEXT: leal -1(%rdi), %eax2653; CHECK-NEXT: cmpl $8, %eax2654; CHECK-NEXT: ja .LBB26_12655; CHECK-NEXT: # %bb.10:2656; CHECK-NEXT: jmpq *.LJTI26_0(,%rax,8)2657; CHECK-NEXT: .LBB26_4: # %bb02658; CHECK-NEXT: xorl %edi, %edi2659; CHECK-NEXT: jmp g@PLT # TAILCALL2660; CHECK-NEXT: .LBB26_1:2661; CHECK-NEXT: cmpl $13, %edi2662; CHECK-NEXT: je .LBB26_82663; CHECK-NEXT: # %bb.2:2664; CHECK-NEXT: cmpl $42, %edi2665; CHECK-NEXT: jne .LBB26_92666; CHECK-NEXT: # %bb.3: # %bb52667; CHECK-NEXT: movl $5, %edi2668; CHECK-NEXT: jmp g@PLT # TAILCALL2669; CHECK-NEXT: .LBB26_9: # %return2670; CHECK-NEXT: retq2671; CHECK-NEXT: .LBB26_7: # %bb32672; CHECK-NEXT: movl $3, %edi2673; CHECK-NEXT: jmp g@PLT # TAILCALL2674; CHECK-NEXT: .LBB26_5: # %bb12675; CHECK-NEXT: movl $1, %edi2676; CHECK-NEXT: jmp g@PLT # TAILCALL2677; CHECK-NEXT: .LBB26_6: # %bb22678; CHECK-NEXT: movl $2, %edi2679; CHECK-NEXT: jmp g@PLT # TAILCALL2680; CHECK-NEXT: .LBB26_8: # %bb42681; CHECK-NEXT: movl $4, %edi2682; CHECK-NEXT: jmp g@PLT # TAILCALL2683;2684; NOOPT-LABEL: switch_i8:2685; NOOPT: # %bb.0:2686; NOOPT-NEXT: pushq %rax2687; NOOPT-NEXT: .cfi_def_cfa_offset 162688; NOOPT-NEXT: movb %dil, %al2689; NOOPT-NEXT: andb $127, %al2690; NOOPT-NEXT: movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill2691; NOOPT-NEXT: subb $1, %al2692; NOOPT-NEXT: je .LBB26_12693; NOOPT-NEXT: jmp .LBB26_82694; NOOPT-NEXT: .LBB26_8:2695; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload2696; NOOPT-NEXT: subb $3, %al2697; NOOPT-NEXT: je .LBB26_22698; NOOPT-NEXT: jmp .LBB26_92699; NOOPT-NEXT: .LBB26_9:2700; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload2701; NOOPT-NEXT: subb $7, %al2702; NOOPT-NEXT: je .LBB26_32703; NOOPT-NEXT: jmp .LBB26_102704; NOOPT-NEXT: .LBB26_10:2705; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload2706; NOOPT-NEXT: subb $9, %al2707; NOOPT-NEXT: je .LBB26_42708; NOOPT-NEXT: jmp .LBB26_112709; NOOPT-NEXT: .LBB26_11:2710; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload2711; NOOPT-NEXT: subb $13, %al2712; NOOPT-NEXT: je .LBB26_52713; NOOPT-NEXT: jmp .LBB26_122714; NOOPT-NEXT: .LBB26_12:2715; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload2716; NOOPT-NEXT: subb $42, %al2717; NOOPT-NEXT: je .LBB26_62718; NOOPT-NEXT: jmp .LBB26_72719; NOOPT-NEXT: .LBB26_1: # %bb02720; NOOPT-NEXT: xorl %edi, %edi2721; NOOPT-NEXT: callq g@PLT2722; NOOPT-NEXT: jmp .LBB26_72723; NOOPT-NEXT: .LBB26_2: # %bb12724; NOOPT-NEXT: movl $1, %edi2725; NOOPT-NEXT: callq g@PLT2726; NOOPT-NEXT: jmp .LBB26_72727; NOOPT-NEXT: .LBB26_3: # %bb22728; NOOPT-NEXT: movl $2, %edi2729; NOOPT-NEXT: callq g@PLT2730; NOOPT-NEXT: jmp .LBB26_72731; NOOPT-NEXT: .LBB26_4: # %bb32732; NOOPT-NEXT: movl $3, %edi2733; NOOPT-NEXT: callq g@PLT2734; NOOPT-NEXT: jmp .LBB26_72735; NOOPT-NEXT: .LBB26_5: # %bb42736; NOOPT-NEXT: movl $4, %edi2737; NOOPT-NEXT: callq g@PLT2738; NOOPT-NEXT: jmp .LBB26_72739; NOOPT-NEXT: .LBB26_6: # %bb52740; NOOPT-NEXT: movl $5, %edi2741; NOOPT-NEXT: callq g@PLT2742; NOOPT-NEXT: .LBB26_7: # %return2743; NOOPT-NEXT: popq %rax2744; NOOPT-NEXT: .cfi_def_cfa_offset 82745; NOOPT-NEXT: retq2746 %and = and i32 %a, 1272747 %trunc = trunc i32 %and to i82748 switch i8 %trunc, label %return [2749 i8 1, label %bb02750 i8 3, label %bb12751 i8 7, label %bb22752 i8 9, label %bb32753 i8 13, label %bb42754 i8 42, label %bb52755 ]2756bb0: tail call void @g(i32 0) br label %return2757bb1: tail call void @g(i32 1) br label %return2758bb2: tail call void @g(i32 2) br label %return2759bb3: tail call void @g(i32 3) br label %return2760bb4: tail call void @g(i32 4) br label %return2761bb5: tail call void @g(i32 5) br label %return2762return:2763 ret void2764}2765