Index: lib/CodeGen/SelectionDAG/DAGCombiner.cpp =================================================================== --- lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -462,6 +462,7 @@ SDValue VecIn2, unsigned LeftIdx); SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast); + SDValue foldRedundantShiftedMasks(SDNode *N); /// Walk up chain skipping non-aliasing memory nodes, /// looking for aliasing nodes and adding them to the Aliases vector. void GatherAllAliases(SDNode *N, SDValue OriginalChain, @@ -4315,6 +4316,11 @@ ConstantSDNode *N1C = isConstOrConstSplat(N1); if (N0C && N1C && !N1C->isOpaque()) return DAG.FoldConstantArithmetic(ISD::AND, SDLoc(N), VT, N0C, N1C); + + if (N1C && !VT.isVector()) { + if (SDValue R = foldRedundantShiftedMasks(N)) + return R; + } // canonicalize constant to RHS if (DAG.isConstantIntBuildVectorOrConstantInt(N0) && !DAG.isConstantIntBuildVectorOrConstantInt(N1)) @@ -6057,6 +6063,116 @@ return SDValue(); } +// fold expressions x1 and x2 alike: +// x1 = ( and, x, 0x00FF ) +// x2 = (( shl x, 8 ) and 0xFF00 ) +// into +// x2 = shl x1, 8 ; reuse the computation of x1 +SDValue DAGCombiner::foldRedundantShiftedMasks(SDNode *AND) { + // 1st we check for the desired structure + if (!AND || AND->getOpcode() != ISD::AND) + return SDValue(); + + const SDValue &SHIFT = AND->getOperand(0); + if ((SHIFT.getNumOperands() != 2) || (!SHIFT.hasOneUse())) + return SDValue(); + + unsigned N0Opcode = SHIFT.getOpcode(); + switch (N0Opcode) { + case ISD::SHL: + case ISD::SRA: + case ISD::SRL: + case ISD::ROTR: + case ISD::ROTL: + break; + default: + return SDValue(); + } + + const ConstantSDNode *ShiftAmount = + dyn_cast(SHIFT.getOperand(1)); + if (!ShiftAmount) + return SDValue(); + + const APInt &ShiftValue = ShiftAmount->getAPIntValue(); + const ConstantSDNode *Mask = dyn_cast(AND->getOperand(1)); + if (!Mask) + return SDValue(); + + const APInt &MaskValue = Mask->getAPIntValue(); + SDValue MASKED = SHIFT.getOperand(0); + if (MASKED.getValueType().isVector() || !MASKED->hasNUsesOfValue(2, 0)) + return SDValue(); + + // MASKED has 2 uses and 1 is the shift operation + for (SDNode *OtherUser : MASKED->uses()) { + if (OtherUser == SHIFT.getNode()) + continue; + + if (OtherUser->getOpcode() != ISD::AND || + OtherUser->getValueType(0).isVector()) + return SDValue(); + + ConstantSDNode *OtherMask = + dyn_cast(OtherUser->getOperand(1)); + + if (!OtherMask) + continue; + + const APInt &OtherMaskValue = OtherMask->getAPIntValue(); + + if (OtherMaskValue.getBitWidth() != MaskValue.getBitWidth()) + return SDValue(); + + // 2nd we check if the mask / shifted mask combine + switch (N0Opcode) { + case ISD::SHL: + if (!(OtherMaskValue.shl(ShiftValue) == MaskValue || + MaskValue.lshr(ShiftValue) == OtherMaskValue)) + return SDValue(); + break; + case ISD::SRA: + if (!(OtherMaskValue.ashr(ShiftValue) == MaskValue)) + return SDValue(); + break; + case ISD::SRL: + if (!(OtherMaskValue.lshr(ShiftValue) == MaskValue || + MaskValue.shl(ShiftValue) == OtherMaskValue)) + return SDValue(); + break; + case ISD::ROTR: + if (!(OtherMaskValue.rotr(ShiftValue) == MaskValue)) + return SDValue(); + break; + case ISD::ROTL: + if (!(OtherMaskValue.rotl(ShiftValue) == MaskValue)) + return SDValue(); + break; + default: + return SDValue(); + } + // 3rd we do a transformation + LLVM_DEBUG( + dbgs() << "\tValue being masked and shift-masked: "; MASKED.dump(); + dbgs() << "t\tApplied mask: 0x" << OtherMaskValue.toString(16, false) + << " : "; + OtherUser->dump(); + dbgs() << "\tShifted by: " << ShiftValue.getZExtValue() << " : "; + SHIFT.dump(); dbgs() << "\t\tAnd masked by: 0x" + << MaskValue.toString(16, false) << " : "; + AND->dump(); dbgs() << "\tReusing the value of: "; OtherUser->dump();); + + SDValue ShiftTheAND(OtherUser, 0); + const SDLoc DL(SHIFT); + EVT VT = AND->getValueType(0); + SDValue NewShift = + DAG.getNode(N0Opcode, DL, VT, ShiftTheAND, SHIFT.getOperand(1)); + AddToWorklist(OtherUser); + return NewShift; + } + return SDValue(); +} + SDValue DAGCombiner::visitSHL(SDNode *N) { SDValue N0 = N->getOperand(0); SDValue N1 = N->getOperand(1); Index: test/CodeGen/AArch64/FoldRedundantShiftedMasking.ll =================================================================== --- /dev/null +++ test/CodeGen/AArch64/FoldRedundantShiftedMasking.ll @@ -0,0 +1,96 @@ +; RUN: llc -march=aarch64 %s -o - | FileCheck %s + +define i32 @ror(i32 %a) { +entry: + %m2 = and i32 %a, 3855 + %shl = shl i32 %a, 24 + %shr = lshr i32 %a, 8 + %or = or i32 %shl, %shr + %m1 = and i32 %or, 251658255 + %or2 = or i32 %m1, %m2 + ret i32 %or2 +} +; CHECK-LABEL: ror +; CHECK: mov [[R1:w[0-9]]], #3855 +; CHECK-NEXT: and [[R2:w[0-9]]], w0, [[R1]] +; CHECK-NEXT: orr [[R3:w[0-9]]], [[R1]], [[R1]], ror #8 + +define i32 @shl(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 172 + %2 = shl i32 %0, 8 + %3 = and i32 %2, 44032 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL:shl: +; CHECK: mov w8, #172 +; CHECK-NEXT: and w8, w0, w8 +; CHECK-NEXT: orr w0, w8, w8, lsl #8 + +define i32 @lshr(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 44032 + %2 = lshr i32 %0, 8 + %3 = and i32 %2, 172 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL:lshr: +; CHECK: mov w8, #44032 +; CHECK-NEXT: and w8, w0, w8 +; CHECK-NEXT: orr w0, w8, w8, lsr #8 + +define i32 @ashr(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 44032 + %2 = ashr i32 %0, 8 + %3 = and i32 %2, 172 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL:ashr: +; CHECK: mov w8, #44032 +; CHECK-NEXT: and w8, w0, w8 +; CHECK-NEXT: orr w0, w8, w8, lsr #8 + + +define i32 @shl_nogood(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 172 + %2 = shl i32 %0, %1 + %3 = and i32 %2, 44032 + %4 = or i32 %1, %3 + ret i32 %4 +} + +; CHECK-LABEL:shl_nogood: +; CHECK: sxth w8, w0 +; CHECK-NEXT: mov w9, #172 +; CHECK-NEXT: and w9, w8, w9 +; CHECK-NEXT: lsl w8, w8, w9 +; CHECK-NEXT: mov w10, #44032 +; CHECK-NEXT: and w8, w8, w10 +; CHECK-NEXT: orr w0, w9, w8 +; CHECK-NEXT: ret + +define i32 @shl_nogood2(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 172 + %2 = shl i32 %0, 8 + %3 = and i32 %2, %0 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL:shl_nogood2: +; CHECK: sxth w8, w0 +; CHECK-NEXT: mov w9, #172 +; CHECK-NEXT: and w9, w8, w9 +; CHECK-NEXT: and w8, w8, w8, lsl #8 +; CHECK-NEXT: orr w0, w9, w8 +; CHECK-NEXT: ret Index: test/CodeGen/ARM/FoldRedundantShiftedMasking.ll =================================================================== --- /dev/null +++ test/CodeGen/ARM/FoldRedundantShiftedMasking.ll @@ -0,0 +1,96 @@ +target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" +target triple = "armv4t-arm-none-eabi" + +; RUN: llc -march=arm < %s | FileCheck %s + +define i32 @ror(i32 %a) { +entry: + %m2 = and i32 %a, 3855 + %shl = shl i32 %a, 24 + %shr = lshr i32 %a, 8 + %or = or i32 %shl, %shr + %m1 = and i32 %or, 251658255 + %or2 = or i32 %m1, %m2 + ret i32 %or2 +} +; CHECK-LABEL: ror +; CHECK: mov [[R1:r[0-9]]], #15 +; CHECK-NEXT: orr [[R2:r[0-9]]], [[R1]], #3840 +; CHECK-NEXT: and [[R3:r[0-9]]], r0, [[R1]] +; CHECK-NEXT: orr [[R4:r[0-9]]], [[R3]], [[R3]], ror #8 + +define i32 @shl(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 172 + %2 = shl i32 %0, 8 + %3 = and i32 %2, 44032 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL: shl: +; CHECK: and r0, r0, #172 +; CHECK-NEXT: orr r0, r0, r0, lsl #8 + +define i32 @lshr(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 44032 + %2 = lshr i32 %0, 8 + %3 = and i32 %2, 172 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL: lshr: +; CHECK: and r0, r0, #44032 +; CHECK-NEXT: orr r0, r0, r0, lsr #8 + +define i32 @ashr(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 44032 + %2 = ashr i32 %0, 8 + %3 = and i32 %2, 172 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL: ashr: +; CHECK: and r0, r0, #44032 +; CHECK-NEXT: orr r0, r0, r0, lsr #8 + +define i32 @shl_nogood(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 172 + %2 = shl i32 %0, %1 + %3 = and i32 %2, 44032 + %4 = or i32 %1, %3 + ret i32 %4 +} + +; CHECK-LABEL:shl_nogood: +; CHECK: lsl r0, r0, #16 +; CHECK-NEXT: mov r1, #172 +; CHECK-NEXT: and r1, r1, r0, asr #16 +; CHECK-NEXT: asr r0, r0, #16 +; CHECK-NEXT: mov r2, #44032 +; CHECK-NEXT: and r0, r2, r0, lsl r1 +; CHECK-NEXT: orr r0, r1, r0 + +define i32 @shl_nogood2(i16 %a) { +entry: + %0 = sext i16 %a to i32 + %1 = and i32 %0, 172 + %2 = shl i32 %0, 8 + %3 = and i32 %2, %0 + %4 = or i32 %1, %3 + ret i32 %4 +} +; CHECK-LABEL:shl_nogood2: +; CHECK: lsl r0, r0, #16 +; CHECK-NEXT: mov r1, #172 +; CHECK-NEXT: asr r2, r0, #16 +; CHECK-NEXT: and r1, r1, r0, asr #16 +; CHECK-NEXT: lsl r2, r2, #8 +; CHECK-NEXT: and r0, r2, r0, asr #16 +; CHECK-NEXT: orr r0, r1, r0 Index: test/CodeGen/X86/FoldRedundantShiftedMasking.roll.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/FoldRedundantShiftedMasking.roll.ll @@ -0,0 +1,18 @@ +; RUN: llc -march=x86-64 %s -o - | FileCheck %s + +define i32 @roll(i32 %a) { +entry: + %m2 = and i32 %a, 3855 + %shl = shl i32 %a, 24 + %shr = lshr i32 %a, 8 + %or = or i32 %shl, %shr + %m1 = and i32 %or, 251658255 + %or2 = or i32 %m1, %m2 + ret i32 %or2 +} + +; CHECK-LABEL: roll: +; CHECK: andl $3855, %edi +; CHECK-NEXT: movl %edi, %eax +; CHECK-NEXT: roll $24, %eax +; CHECK-NEXT: orl %edi, %eax Index: test/CodeGen/X86/pr32329.ll =================================================================== --- test/CodeGen/X86/pr32329.ll +++ test/CodeGen/X86/pr32329.ll @@ -29,18 +29,18 @@ ; X86-NEXT: .cfi_offset %edi, -16 ; X86-NEXT: .cfi_offset %ebx, -12 ; X86-NEXT: .cfi_offset %ebp, -8 -; X86-NEXT: movl obj, %edx ; X86-NEXT: movsbl var_27, %eax ; X86-NEXT: movzwl var_2, %esi ; X86-NEXT: movl var_310, %ecx ; X86-NEXT: imull %eax, %ecx ; X86-NEXT: addl var_24, %ecx -; X86-NEXT: andl $4194303, %edx # imm = 0x3FFFFF -; X86-NEXT: leal (%edx,%edx), %ebx -; X86-NEXT: subl %eax, %ebx -; X86-NEXT: movl %ebx, %edi -; X86-NEXT: subl %esi, %edi -; X86-NEXT: imull %edi, %ecx +; X86-NEXT: movl $4194303, %edi # imm = 0x3FFFFF +; X86-NEXT: andl obj, %edi +; X86-NEXT: leal (%edi,%edi), %edx +; X86-NEXT: subl %eax, %edx +; X86-NEXT: movl %edx, %ebx +; X86-NEXT: subl %esi, %ebx +; X86-NEXT: imull %ebx, %ecx ; X86-NEXT: addl $-1437483407, %ecx # imm = 0xAA51BE71 ; X86-NEXT: movl $9, %esi ; X86-NEXT: xorl %ebp, %ebp @@ -50,12 +50,12 @@ ; X86-NEXT: cmovnel %esi, %ebp ; X86-NEXT: movl $0, %ecx ; X86-NEXT: cmovnel %ecx, %esi -; X86-NEXT: cmpl %edx, %edi +; X86-NEXT: cmpl %edi, %ebx ; X86-NEXT: movl %ebp, var_50+4 ; X86-NEXT: movl %esi, var_50 ; X86-NEXT: setge var_205 -; X86-NEXT: imull %eax, %ebx -; X86-NEXT: movb %bl, var_218 +; X86-NEXT: imull %eax, %edx +; X86-NEXT: movb %dl, var_218 ; X86-NEXT: popl %esi ; X86-NEXT: .cfi_def_cfa_offset 16 ; X86-NEXT: popl %edi @@ -68,24 +68,24 @@ ; ; X64-LABEL: foo: ; X64: # %bb.0: # %entry -; X64-NEXT: movl {{.*}}(%rip), %eax ; X64-NEXT: movsbl {{.*}}(%rip), %r9d ; X64-NEXT: movzwl {{.*}}(%rip), %r8d ; X64-NEXT: movl {{.*}}(%rip), %ecx ; X64-NEXT: imull %r9d, %ecx ; X64-NEXT: addl {{.*}}(%rip), %ecx -; X64-NEXT: andl $4194303, %eax # imm = 0x3FFFFF -; X64-NEXT: leal (%rax,%rax), %edi +; X64-NEXT: movl $4194303, %esi +; X64-NEXT: andl obj(%rip), %esi +; X64-NEXT: leal (%rsi,%rsi), %edi ; X64-NEXT: subl %r9d, %edi -; X64-NEXT: movl %edi, %esi -; X64-NEXT: subl %r8d, %esi -; X64-NEXT: imull %esi, %ecx +; X64-NEXT: movl %edi, %edx +; X64-NEXT: subl %r8d, %edx +; X64-NEXT: imull %edx, %ecx ; X64-NEXT: addl $-1437483407, %ecx # imm = 0xAA51BE71 -; X64-NEXT: movl $9, %edx +; X64-NEXT: movl $9, %eax ; X64-NEXT: # kill: def $cl killed $cl killed $ecx -; X64-NEXT: shlq %cl, %rdx -; X64-NEXT: movq %rdx, {{.*}}(%rip) -; X64-NEXT: cmpl %eax, %esi +; X64-NEXT: shlq %cl, %rax +; X64-NEXT: movq %rax, {{.*}}(%rip) +; X64-NEXT: cmpl %esi, %edx ; X64-NEXT: setge {{.*}}(%rip) ; X64-NEXT: imull %r9d, %edi ; X64-NEXT: movb %dil, {{.*}}(%rip)