454 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py2; RUN: llc < %s -mtriple=i686-linux-gnu | FileCheck %s --check-prefixes=X863; RUN: llc < %s -mtriple=x86_64-linux-gnu | FileCheck %s --check-prefixes=X644 5; fold (shl (zext (lshr (A, X))), X) -> (zext (shl (lshr (A, X)), X))6 7; Canolicalize the sequence shl/zext/lshr performing the zeroextend8; as the last instruction of the sequence.9; This will help DAGCombiner to identify and then fold the sequence10; of shifts into a single AND.11; This transformation is profitable if the shift amounts are the same12; and if there is only one use of the zext.13 14define i16 @fun1(i8 zeroext %v) {15; X86-LABEL: fun1:16; X86: # %bb.0: # %entry17; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax18; X86-NEXT: andl $-16, %eax19; X86-NEXT: # kill: def $ax killed $ax killed $eax20; X86-NEXT: retl21;22; X64-LABEL: fun1:23; X64: # %bb.0: # %entry24; X64-NEXT: movl %edi, %eax25; X64-NEXT: andl $-16, %eax26; X64-NEXT: # kill: def $ax killed $ax killed $eax27; X64-NEXT: retq28entry:29 %shr = lshr i8 %v, 430 %ext = zext i8 %shr to i1631 %shl = shl i16 %ext, 432 ret i16 %shl33}34 35define i32 @fun2(i8 zeroext %v) {36; X86-LABEL: fun2:37; X86: # %bb.0: # %entry38; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax39; X86-NEXT: andl $-16, %eax40; X86-NEXT: retl41;42; X64-LABEL: fun2:43; X64: # %bb.0: # %entry44; X64-NEXT: movl %edi, %eax45; X64-NEXT: andl $-16, %eax46; X64-NEXT: retq47entry:48 %shr = lshr i8 %v, 449 %ext = zext i8 %shr to i3250 %shl = shl i32 %ext, 451 ret i32 %shl52}53 54define i32 @fun3(i16 zeroext %v) {55; X86-LABEL: fun3:56; X86: # %bb.0: # %entry57; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax58; X86-NEXT: andl $-16, %eax59; X86-NEXT: retl60;61; X64-LABEL: fun3:62; X64: # %bb.0: # %entry63; X64-NEXT: movl %edi, %eax64; X64-NEXT: andl $-16, %eax65; X64-NEXT: retq66entry:67 %shr = lshr i16 %v, 468 %ext = zext i16 %shr to i3269 %shl = shl i32 %ext, 470 ret i32 %shl71}72 73define i64 @fun4(i8 zeroext %v) {74; X86-LABEL: fun4:75; X86: # %bb.0: # %entry76; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax77; X86-NEXT: andl $-16, %eax78; X86-NEXT: xorl %edx, %edx79; X86-NEXT: retl80;81; X64-LABEL: fun4:82; X64: # %bb.0: # %entry83; X64-NEXT: movl %edi, %eax84; X64-NEXT: andl $-16, %eax85; X64-NEXT: retq86entry:87 %shr = lshr i8 %v, 488 %ext = zext i8 %shr to i6489 %shl = shl i64 %ext, 490 ret i64 %shl91}92 93define i64 @fun5(i16 zeroext %v) {94; X86-LABEL: fun5:95; X86: # %bb.0: # %entry96; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax97; X86-NEXT: andl $-16, %eax98; X86-NEXT: xorl %edx, %edx99; X86-NEXT: retl100;101; X64-LABEL: fun5:102; X64: # %bb.0: # %entry103; X64-NEXT: movl %edi, %eax104; X64-NEXT: andl $-16, %eax105; X64-NEXT: retq106entry:107 %shr = lshr i16 %v, 4108 %ext = zext i16 %shr to i64109 %shl = shl i64 %ext, 4110 ret i64 %shl111}112 113define i64 @fun6(i32 zeroext %v) {114; X86-LABEL: fun6:115; X86: # %bb.0: # %entry116; X86-NEXT: movl {{[0-9]+}}(%esp), %eax117; X86-NEXT: andl $-16, %eax118; X86-NEXT: xorl %edx, %edx119; X86-NEXT: retl120;121; X64-LABEL: fun6:122; X64: # %bb.0: # %entry123; X64-NEXT: movl %edi, %eax124; X64-NEXT: andl $-16, %eax125; X64-NEXT: retq126entry:127 %shr = lshr i32 %v, 4128 %ext = zext i32 %shr to i64129 %shl = shl i64 %ext, 4130 ret i64 %shl131}132 133; Don't fold the pattern if we use arithmetic shifts.134 135define i64 @fun7(i8 zeroext %v) {136; X86-LABEL: fun7:137; X86: # %bb.0: # %entry138; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax139; X86-NEXT: sarb $4, %al140; X86-NEXT: movzbl %al, %eax141; X86-NEXT: shll $4, %eax142; X86-NEXT: xorl %edx, %edx143; X86-NEXT: retl144;145; X64-LABEL: fun7:146; X64: # %bb.0: # %entry147; X64-NEXT: sarb $4, %dil148; X64-NEXT: movzbl %dil, %eax149; X64-NEXT: shll $4, %eax150; X64-NEXT: retq151entry:152 %shr = ashr i8 %v, 4153 %ext = zext i8 %shr to i64154 %shl = shl i64 %ext, 4155 ret i64 %shl156}157 158define i64 @fun8(i16 zeroext %v) {159; X86-LABEL: fun8:160; X86: # %bb.0: # %entry161; X86-NEXT: movswl {{[0-9]+}}(%esp), %eax162; X86-NEXT: andl $1048560, %eax # imm = 0xFFFF0163; X86-NEXT: xorl %edx, %edx164; X86-NEXT: retl165;166; X64-LABEL: fun8:167; X64: # %bb.0: # %entry168; X64-NEXT: movswl %di, %eax169; X64-NEXT: andl $1048560, %eax # imm = 0xFFFF0170; X64-NEXT: retq171entry:172 %shr = ashr i16 %v, 4173 %ext = zext i16 %shr to i64174 %shl = shl i64 %ext, 4175 ret i64 %shl176}177 178define i64 @fun9(i32 zeroext %v) {179; X86-LABEL: fun9:180; X86: # %bb.0: # %entry181; X86-NEXT: movl {{[0-9]+}}(%esp), %eax182; X86-NEXT: movl %eax, %edx183; X86-NEXT: sarl $4, %edx184; X86-NEXT: andl $-16, %eax185; X86-NEXT: shrl $28, %edx186; X86-NEXT: retl187;188; X64-LABEL: fun9:189; X64: # %bb.0: # %entry190; X64-NEXT: movl %edi, %eax191; X64-NEXT: sarl $4, %eax192; X64-NEXT: shlq $4, %rax193; X64-NEXT: retq194entry:195 %shr = ashr i32 %v, 4196 %ext = zext i32 %shr to i64197 %shl = shl i64 %ext, 4198 ret i64 %shl199}200 201; Don't fold the pattern if there is more than one use of the202; operand in input to the shift left.203 204define i64 @fun10(i8 zeroext %v) {205; X86-LABEL: fun10:206; X86: # %bb.0: # %entry207; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax208; X86-NEXT: shrb $4, %al209; X86-NEXT: movzbl %al, %ecx210; X86-NEXT: movl %ecx, %eax211; X86-NEXT: shll $4, %eax212; X86-NEXT: orl %ecx, %eax213; X86-NEXT: xorl %edx, %edx214; X86-NEXT: retl215;216; X64-LABEL: fun10:217; X64: # %bb.0: # %entry218; X64-NEXT: # kill: def $edi killed $edi def $rdi219; X64-NEXT: movl %edi, %eax220; X64-NEXT: shrb $4, %al221; X64-NEXT: movzbl %al, %eax222; X64-NEXT: andl $-16, %edi223; X64-NEXT: orq %rdi, %rax224; X64-NEXT: retq225entry:226 %shr = lshr i8 %v, 4227 %ext = zext i8 %shr to i64228 %shl = shl i64 %ext, 4229 %add = add i64 %shl, %ext230 ret i64 %add231}232 233define i64 @fun11(i16 zeroext %v) {234; X86-LABEL: fun11:235; X86: # %bb.0: # %entry236; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax237; X86-NEXT: movl %eax, %ecx238; X86-NEXT: shrl $4, %ecx239; X86-NEXT: andl $-16, %eax240; X86-NEXT: addl %ecx, %eax241; X86-NEXT: xorl %edx, %edx242; X86-NEXT: retl243;244; X64-LABEL: fun11:245; X64: # %bb.0: # %entry246; X64-NEXT: # kill: def $edi killed $edi def $rdi247; X64-NEXT: movl %edi, %eax248; X64-NEXT: shrl $4, %eax249; X64-NEXT: andl $-16, %edi250; X64-NEXT: addq %rdi, %rax251; X64-NEXT: retq252entry:253 %shr = lshr i16 %v, 4254 %ext = zext i16 %shr to i64255 %shl = shl i64 %ext, 4256 %add = add i64 %shl, %ext257 ret i64 %add258}259 260define i64 @fun12(i32 zeroext %v) {261; X86-LABEL: fun12:262; X86: # %bb.0: # %entry263; X86-NEXT: movl {{[0-9]+}}(%esp), %eax264; X86-NEXT: movl %eax, %ecx265; X86-NEXT: shrl $4, %ecx266; X86-NEXT: andl $-16, %eax267; X86-NEXT: xorl %edx, %edx268; X86-NEXT: addl %ecx, %eax269; X86-NEXT: setb %dl270; X86-NEXT: retl271;272; X64-LABEL: fun12:273; X64: # %bb.0: # %entry274; X64-NEXT: # kill: def $edi killed $edi def $rdi275; X64-NEXT: movl %edi, %eax276; X64-NEXT: shrl $4, %eax277; X64-NEXT: andl $-16, %edi278; X64-NEXT: addq %rdi, %rax279; X64-NEXT: retq280entry:281 %shr = lshr i32 %v, 4282 %ext = zext i32 %shr to i64283 %shl = shl i64 %ext, 4284 %add = add i64 %shl, %ext285 ret i64 %add286}287 288; PR17380289; Make sure that the combined dags are legal if we run the DAGCombiner after290; Legalization took place. The add instruction is redundant and increases by291; one the number of uses of the zext. This prevents the transformation from292; firing before dags are legalized and optimized.293; Once the add is removed, the number of uses becomes one and therefore the294; dags are canonicalized. After Legalization, we need to make sure that the295; valuetype for the shift count is legal.296; Verify also that we correctly fold the shl-shr sequence into an297; AND with bitmask.298 299define void @g(i32 %a) nounwind {300; X86-LABEL: g:301; X86: # %bb.0:302; X86-NEXT: subl $12, %esp303; X86-NEXT: movl {{[0-9]+}}(%esp), %eax304; X86-NEXT: andl $-4, %eax305; X86-NEXT: subl $8, %esp306; X86-NEXT: pushl $0307; X86-NEXT: pushl %eax308; X86-NEXT: calll f309; X86-NEXT: addl $28, %esp310; X86-NEXT: retl311;312; X64-LABEL: g:313; X64: # %bb.0:314; X64-NEXT: # kill: def $edi killed $edi def $rdi315; X64-NEXT: andl $-4, %edi316; X64-NEXT: jmp f # TAILCALL317 %b = lshr i32 %a, 2318 %c = zext i32 %b to i64319 %d = add i64 %c, 1320 %e = shl i64 %c, 2321 tail call void @f(i64 %e)322 ret void323}324 325define i32 @shift_zext_shl(i8 zeroext %x) {326; X86-LABEL: shift_zext_shl:327; X86: # %bb.0:328; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax329; X86-NEXT: andl $64, %eax330; X86-NEXT: shll $9, %eax331; X86-NEXT: retl332;333; X64-LABEL: shift_zext_shl:334; X64: # %bb.0:335; X64-NEXT: movl %edi, %eax336; X64-NEXT: andl $64, %eax337; X64-NEXT: shll $9, %eax338; X64-NEXT: retq339 %a = and i8 %x, 64340 %b = zext i8 %a to i16341 %c = shl i16 %b, 9342 %d = zext i16 %c to i32343 ret i32 %d344}345 346define i32 @shift_zext_shl2(i8 zeroext %x) {347; X86-LABEL: shift_zext_shl2:348; X86: # %bb.0:349; X86-NEXT: movzbl {{[0-9]+}}(%esp), %eax350; X86-NEXT: andl $64, %eax351; X86-NEXT: shll $9, %eax352; X86-NEXT: retl353;354; X64-LABEL: shift_zext_shl2:355; X64: # %bb.0:356; X64-NEXT: movl %edi, %eax357; X64-NEXT: andl $64, %eax358; X64-NEXT: shll $9, %eax359; X64-NEXT: retq360 %a = and i8 %x, 64361 %b = zext i8 %a to i32362 %c = shl i32 %b, 9363 ret i32 %c364}365 366define <4 x i32> @shift_zext_shl_vec(<4 x i8> %x) nounwind {367; X86-LABEL: shift_zext_shl_vec:368; X86: # %bb.0:369; X86-NEXT: pushl %edi370; X86-NEXT: pushl %esi371; X86-NEXT: movl {{[0-9]+}}(%esp), %eax372; X86-NEXT: movzbl {{[0-9]+}}(%esp), %edi373; X86-NEXT: movzbl {{[0-9]+}}(%esp), %esi374; X86-NEXT: movzbl {{[0-9]+}}(%esp), %edx375; X86-NEXT: movzbl {{[0-9]+}}(%esp), %ecx376; X86-NEXT: andl $64, %ecx377; X86-NEXT: shll $9, %ecx378; X86-NEXT: andl $63, %edx379; X86-NEXT: shll $8, %edx380; X86-NEXT: andl $31, %esi381; X86-NEXT: shll $7, %esi382; X86-NEXT: andl $23, %edi383; X86-NEXT: shll $6, %edi384; X86-NEXT: movl %edi, 12(%eax)385; X86-NEXT: movl %esi, 8(%eax)386; X86-NEXT: movl %edx, 4(%eax)387; X86-NEXT: movl %ecx, (%eax)388; X86-NEXT: popl %esi389; X86-NEXT: popl %edi390; X86-NEXT: retl $4391;392; X64-LABEL: shift_zext_shl_vec:393; X64: # %bb.0:394; X64-NEXT: pand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0395; X64-NEXT: pxor %xmm1, %xmm1396; X64-NEXT: punpcklbw {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3],xmm0[4],xmm1[4],xmm0[5],xmm1[5],xmm0[6],xmm1[6],xmm0[7],xmm1[7]397; X64-NEXT: pmullw {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0 # [512,256,128,64,u,u,u,u]398; X64-NEXT: punpcklwd {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3]399; X64-NEXT: retq400 %a = and <4 x i8> %x, <i8 64, i8 63, i8 31, i8 23>401 %b = zext <4 x i8> %a to <4 x i16>402 %c = shl <4 x i16> %b, <i16 9, i16 8, i16 7, i16 6>403 %d = zext <4 x i16> %c to <4 x i32>404 ret <4 x i32> %d405}406 407define <4 x i32> @shift_zext_shl2_vec(<4 x i8> %x) nounwind {408; X86-LABEL: shift_zext_shl2_vec:409; X86: # %bb.0:410; X86-NEXT: pushl %edi411; X86-NEXT: pushl %esi412; X86-NEXT: movl {{[0-9]+}}(%esp), %eax413; X86-NEXT: movzbl {{[0-9]+}}(%esp), %ecx414; X86-NEXT: movzbl {{[0-9]+}}(%esp), %edx415; X86-NEXT: movzbl {{[0-9]+}}(%esp), %esi416; X86-NEXT: movzbl {{[0-9]+}}(%esp), %edi417; X86-NEXT: andl $23, %edi418; X86-NEXT: andl $31, %esi419; X86-NEXT: andl $63, %edx420; X86-NEXT: andl $64, %ecx421; X86-NEXT: shll $9, %ecx422; X86-NEXT: shll $8, %edx423; X86-NEXT: shll $7, %esi424; X86-NEXT: shll $6, %edi425; X86-NEXT: movl %edi, 12(%eax)426; X86-NEXT: movl %esi, 8(%eax)427; X86-NEXT: movl %edx, 4(%eax)428; X86-NEXT: movl %ecx, (%eax)429; X86-NEXT: popl %esi430; X86-NEXT: popl %edi431; X86-NEXT: retl $4432;433; X64-LABEL: shift_zext_shl2_vec:434; X64: # %bb.0:435; X64-NEXT: pand {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0436; X64-NEXT: pxor %xmm1, %xmm1437; X64-NEXT: punpcklbw {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3],xmm0[4],xmm1[4],xmm0[5],xmm1[5],xmm0[6],xmm1[6],xmm0[7],xmm1[7]438; X64-NEXT: punpcklwd {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3]439; X64-NEXT: pshufd {{.*#+}} xmm1 = xmm0[1,1,3,3]440; X64-NEXT: pmuludq {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm0 # [512,256,128,64]441; X64-NEXT: pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]442; X64-NEXT: pmuludq {{\.?LCPI[0-9]+_[0-9]+}}(%rip), %xmm1 # [256,u,64,u]443; X64-NEXT: pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]444; X64-NEXT: punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]445; X64-NEXT: retq446 %a = and <4 x i8> %x, <i8 64, i8 63, i8 31, i8 23>447 %b = zext <4 x i8> %a to <4 x i32>448 %c = shl <4 x i32> %b, <i32 9, i32 8, i32 7, i32 6>449 ret <4 x i32> %c450}451 452declare dso_local void @f(i64)453 454