Index: include/llvm/CodeGen/TargetLowering.h =================================================================== --- include/llvm/CodeGen/TargetLowering.h +++ include/llvm/CodeGen/TargetLowering.h @@ -3702,6 +3702,9 @@ SDValue N1, ISD::CondCode Cond, DAGCombinerInfo &DCI, const SDLoc &DL) const; + + SDValue BuildUREMEqFold(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond, + DAGCombinerInfo &DCI, const SDLoc &DL) const; }; /// Given an LLVM IR type and return type attributes, compute the return value Index: lib/CodeGen/SelectionDAG/TargetLowering.cpp =================================================================== --- lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -2774,6 +2774,18 @@ return V; } + // Fold remainder of division by a a constant + if (N0.getOpcode() == ISD::UREM && N0.hasOneUse() && + (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { + AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes(); + + // When division is cheap or optimizing for minimum size, + // fall through to DIVREM creation by skipping this fold. + if (!isIntDivCheap(VT, Attr) && !Attr.hasFnAttribute(Attribute::MinSize)) + if (SDValue Folded = BuildUREMEqFold(VT, N0, N1, Cond, DCI, dl)) + return Folded; + } + // Fold away ALL boolean setcc's. SDValue Temp; if (N0.getValueType().getScalarType() == MVT::i1 && foldBooleans) { @@ -3743,6 +3755,81 @@ return DAG.getSelect(dl, VT, IsOne, N0, Q); } +/// Given an ISD::UREM used only by an ISD::SETEQ or ISD::SETNE +/// where the divisor is constant and the comparison target is zero, +/// return a DAG expression that will generate the same comparison result +/// using only multiplications, additions and shifts/rotations. +/// Ref: "Hacker's Delight" 10-17. +SDValue TargetLowering::BuildUREMEqFold(EVT VT, SDValue REMNode, + SDValue CompNode, ISD::CondCode Cond, + DAGCombinerInfo &DCI, + const SDLoc &DL) const { + // fold (seteq/ne (urem N, D), 0) -> (setule/gte (rotr (mul N, P), K), Q) + // - D must be constant with D = D0 * 2^K where D0 is odd + // - P is the multiplicative inverse of D0 modulo 2^W + // - Q = floor((2^W - 1) / D0) + // where W is the width of the common type of N and D + SelectionDAG &DAG = DCI.DAG; + EVT REMVT = REMNode->getValueType(0); + bool IsEq = (Cond == ISD::SETEQ); + + assert((Cond == ISD::SETEQ || Cond == ISD::SETNE) && + "Only applicable for (in)equality comparisons."); + + if (!isTypeLegal(REMVT)) + return SDValue(); + + // TODO: Add non-uniform constant support + ConstantSDNode *Divisor = isConstOrConstSplat(REMNode->getOperand(1)); + ConstantSDNode *CompTarget = isConstOrConstSplat(CompNode); + if (!Divisor || !CompTarget || Divisor->isNullValue() || + !CompTarget->isNullValue()) + return SDValue(); + + APInt D = Divisor->getAPIntValue(); + + // REM by a power of two is better represented by an AND mask + if (D.isPowerOf2()) + return SDValue(); + + // Decompose D into D0 * 2^K + unsigned K = D.countTrailingZeros(); + bool DivisorIsEven = (K != 0); + APInt D0 = D.lshr(K); + + // P = inv(D0, 2^W) + // 2^W requires W + 1 bits, so we have to extend and then truncate + unsigned W = D.getBitWidth(); + APInt P = D0.zext(W + 1) + .multiplicativeInverse(APInt::getHighBitsSet(W + 1, 1)) + .trunc(W); + + // Q = floor((2^W - 1) / D0) + APInt Q = APInt::getAllOnesValue(W).udiv(D0); + + SDValue PVal = DAG.getConstant(P, DL, REMVT); + SDValue QVal = DAG.getConstant(Q, DL, REMVT); + // (mul N, P) + SDValue Op1 = DAG.getNode(ISD::MUL, DL, REMVT, REMNode->getOperand(0), PVal); + // Will change in the signed case + SDValue Op2 = QVal; + + // Rotate right only if D was even + if (DivisorIsEven) { + SDValue ShAmt = + DAG.getConstant(K, DL, getShiftAmountTy(REMVT, DAG.getDataLayout())); + SDNodeFlags Flags; + Flags.setExact(true); + // UREM: (rotr (mul N, P), K) + // SREM: (rotr (add (mul N, P), Q'), K) + Op1 = DAG.getNode(ISD::ROTR, DL, REMVT, Op1, ShAmt, Flags); + } + + // UREM: (setule/setugt (rotr (mul N, P), K), Q) + Op1 = DAG.getSetCC(DL, VT, Op1, Op2, (IsEq ? ISD::SETULE : ISD::SETUGT)); + return Op1; +} + bool TargetLowering:: verifyReturnAddressArgumentIsConstant(SDValue Op, SelectionDAG &DAG) const { if (!isa(Op.getOperand(0))) { Index: test/CodeGen/X86/jump_sign.ll =================================================================== --- test/CodeGen/X86/jump_sign.ll +++ test/CodeGen/X86/jump_sign.ll @@ -236,13 +236,11 @@ ; CHECK-NEXT: jne .LBB12_8 ; CHECK-NEXT: # %bb.4: # %if.end29 ; CHECK-NEXT: movzwl (%eax), %eax -; CHECK-NEXT: movzwl %ax, %eax -; CHECK-NEXT: imull $52429, %eax, %ecx # imm = 0xCCCD -; CHECK-NEXT: shrl $19, %ecx -; CHECK-NEXT: addl %ecx, %ecx -; CHECK-NEXT: leal (%ecx,%ecx,4), %ecx -; CHECK-NEXT: cmpw %cx, %ax -; CHECK-NEXT: jne .LBB12_5 +; CHECK-NEXT: imull $-13107, %eax, %eax +; CHECK-NEXT: rorw $1, %ax +; CHECK-NEXT: movzwl %ax, %eax +; CHECK-NEXT: cmpl $13108, %eax +; CHECK-NEXT: jae .LBB12_5 ; CHECK-NEXT: .LBB12_8: # %if.then44 ; CHECK-NEXT: xorl %eax, %eax ; CHECK-NEXT: testb %al, %al Index: test/CodeGen/X86/urem-seteq-optsize.ll =================================================================== --- test/CodeGen/X86/urem-seteq-optsize.ll +++ test/CodeGen/X86/urem-seteq-optsize.ll @@ -48,15 +48,10 @@ define i32 @test_optsize(i32 %X) optsize nounwind readnone { ; X86-LABEL: test_optsize: ; X86: # %bb.0: -; X86-NEXT: movl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl $-858993459, %edx # imm = 0xCCCCCCCD -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: mull %edx -; X86-NEXT: shrl $2, %edx -; X86-NEXT: leal (%edx,%edx,4), %eax -; X86-NEXT: cmpl %eax, %ecx +; X86-NEXT: imull $-858993459, {{[0-9]+}}(%esp), %eax # imm = 0xCCCCCCCD +; X86-NEXT: cmpl $858993460, %eax # imm = 0x33333334 ; X86-NEXT: movl $42, %eax -; X86-NEXT: je .LBB1_2 +; X86-NEXT: jb .LBB1_2 ; X86-NEXT: # %bb.1: ; X86-NEXT: movl $-10, %eax ; X86-NEXT: .LBB1_2: @@ -64,15 +59,11 @@ ; ; X64-LABEL: test_optsize: ; X64: # %bb.0: -; X64-NEXT: movl %edi, %eax -; X64-NEXT: movl $3435973837, %ecx # imm = 0xCCCCCCCD -; X64-NEXT: imulq %rax, %rcx -; X64-NEXT: shrq $34, %rcx -; X64-NEXT: leal (%rcx,%rcx,4), %eax -; X64-NEXT: cmpl %eax, %edi +; X64-NEXT: imull $-858993459, %edi, %eax # imm = 0xCCCCCCCD +; X64-NEXT: cmpl $858993460, %eax # imm = 0x33333334 ; X64-NEXT: movl $42, %ecx ; X64-NEXT: movl $-10, %eax -; X64-NEXT: cmovel %ecx, %eax +; X64-NEXT: cmovbl %ecx, %eax ; X64-NEXT: retq %rem = urem i32 %X, 5 %cmp = icmp eq i32 %rem, 0 Index: test/CodeGen/X86/urem-seteq.ll =================================================================== --- test/CodeGen/X86/urem-seteq.ll +++ test/CodeGen/X86/urem-seteq.ll @@ -10,27 +10,18 @@ define i32 @test_urem_odd(i32 %X) nounwind readnone { ; X86-LABEL: test_urem_odd: ; X86: # %bb.0: -; X86-NEXT: movl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl $-858993459, %edx # imm = 0xCCCCCCCD -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: mull %edx -; X86-NEXT: shrl $2, %edx -; X86-NEXT: leal (%edx,%edx,4), %edx +; X86-NEXT: imull $-858993459, {{[0-9]+}}(%esp), %ecx # imm = 0xCCCCCCCD ; X86-NEXT: xorl %eax, %eax -; X86-NEXT: cmpl %edx, %ecx -; X86-NEXT: sete %al +; X86-NEXT: cmpl $858993460, %ecx # imm = 0x33333334 +; X86-NEXT: setb %al ; X86-NEXT: retl ; ; X64-LABEL: test_urem_odd: ; X64: # %bb.0: -; X64-NEXT: movl %edi, %eax -; X64-NEXT: movl $3435973837, %ecx # imm = 0xCCCCCCCD -; X64-NEXT: imulq %rax, %rcx -; X64-NEXT: shrq $34, %rcx -; X64-NEXT: leal (%rcx,%rcx,4), %ecx +; X64-NEXT: imull $-858993459, %edi, %ecx # imm = 0xCCCCCCCD ; X64-NEXT: xorl %eax, %eax -; X64-NEXT: cmpl %ecx, %edi -; X64-NEXT: sete %al +; X64-NEXT: cmpl $858993460, %ecx # imm = 0x33333334 +; X64-NEXT: setb %al ; X64-NEXT: retq %urem = urem i32 %X, 5 %cmp = icmp eq i32 %urem, 0 @@ -42,27 +33,18 @@ define i32 @test_urem_odd_bit30(i32 %X) nounwind readnone { ; X86-LABEL: test_urem_odd_bit30: ; X86: # %bb.0: -; X86-NEXT: movl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl $-11, %edx -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: mull %edx -; X86-NEXT: shrl $30, %edx -; X86-NEXT: imull $1073741827, %edx, %edx # imm = 0x40000003 +; X86-NEXT: imull $1789569707, {{[0-9]+}}(%esp), %ecx # imm = 0x6AAAAAAB ; X86-NEXT: xorl %eax, %eax -; X86-NEXT: cmpl %edx, %ecx -; X86-NEXT: sete %al +; X86-NEXT: cmpl $4, %ecx +; X86-NEXT: setb %al ; X86-NEXT: retl ; ; X64-LABEL: test_urem_odd_bit30: ; X64: # %bb.0: -; X64-NEXT: movl %edi, %eax -; X64-NEXT: movl $4294967285, %ecx # imm = 0xFFFFFFF5 -; X64-NEXT: imulq %rax, %rcx -; X64-NEXT: shrq $62, %rcx -; X64-NEXT: imull $1073741827, %ecx, %ecx # imm = 0x40000003 +; X64-NEXT: imull $1789569707, %edi, %ecx # imm = 0x6AAAAAAB ; X64-NEXT: xorl %eax, %eax -; X64-NEXT: cmpl %ecx, %edi -; X64-NEXT: sete %al +; X64-NEXT: cmpl $4, %ecx +; X64-NEXT: setb %al ; X64-NEXT: retq %urem = urem i32 %X, 1073741827 %cmp = icmp eq i32 %urem, 0 @@ -74,28 +56,18 @@ define i32 @test_urem_odd_bit31(i32 %X) nounwind readnone { ; X86-LABEL: test_urem_odd_bit31: ; X86: # %bb.0: -; X86-NEXT: movl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl $1073741823, %edx # imm = 0x3FFFFFFF -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: mull %edx -; X86-NEXT: shrl $29, %edx -; X86-NEXT: imull $-2147483645, %edx, %edx # imm = 0x80000003 +; X86-NEXT: imull $715827883, {{[0-9]+}}(%esp), %ecx # imm = 0x2AAAAAAB ; X86-NEXT: xorl %eax, %eax -; X86-NEXT: cmpl %edx, %ecx -; X86-NEXT: sete %al +; X86-NEXT: cmpl $2, %ecx +; X86-NEXT: setb %al ; X86-NEXT: retl ; ; X64-LABEL: test_urem_odd_bit31: ; X64: # %bb.0: -; X64-NEXT: movl %edi, %eax -; X64-NEXT: movq %rax, %rcx -; X64-NEXT: shlq $30, %rcx -; X64-NEXT: subq %rax, %rcx -; X64-NEXT: shrq $61, %rcx -; X64-NEXT: imull $-2147483645, %ecx, %ecx # imm = 0x80000003 +; X64-NEXT: imull $715827883, %edi, %ecx # imm = 0x2AAAAAAB ; X64-NEXT: xorl %eax, %eax -; X64-NEXT: cmpl %ecx, %edi -; X64-NEXT: sete %al +; X64-NEXT: cmpl $2, %ecx +; X64-NEXT: setb %al ; X64-NEXT: retq %urem = urem i32 %X, 2147483651 %cmp = icmp eq i32 %urem, 0 @@ -112,35 +84,23 @@ define i16 @test_urem_even(i16 %X) nounwind readnone { ; X86-LABEL: test_urem_even: ; X86: # %bb.0: -; X86-NEXT: movzwl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: shrl %eax -; X86-NEXT: imull $18725, %eax, %eax # imm = 0x4925 -; X86-NEXT: shrl $17, %eax -; X86-NEXT: movl %eax, %edx -; X86-NEXT: shll $4, %edx -; X86-NEXT: subl %eax, %edx -; X86-NEXT: subl %eax, %edx +; X86-NEXT: imull $28087, {{[0-9]+}}(%esp), %eax # imm = 0x6DB7 +; X86-NEXT: rorw $1, %ax +; X86-NEXT: movzwl %ax, %ecx ; X86-NEXT: xorl %eax, %eax -; X86-NEXT: cmpw %dx, %cx -; X86-NEXT: setne %al +; X86-NEXT: cmpl $9362, %ecx # imm = 0x2492 +; X86-NEXT: seta %al ; X86-NEXT: # kill: def $ax killed $ax killed $eax ; X86-NEXT: retl ; ; X64-LABEL: test_urem_even: ; X64: # %bb.0: -; X64-NEXT: movzwl %di, %ecx -; X64-NEXT: movl %ecx, %eax -; X64-NEXT: shrl %eax -; X64-NEXT: imull $18725, %eax, %eax # imm = 0x4925 -; X64-NEXT: shrl $17, %eax -; X64-NEXT: movl %eax, %edx -; X64-NEXT: shll $4, %edx -; X64-NEXT: subl %eax, %edx -; X64-NEXT: subl %eax, %edx +; X64-NEXT: imull $28087, %edi, %eax # imm = 0x6DB7 +; X64-NEXT: rorw $1, %ax +; X64-NEXT: movzwl %ax, %ecx ; X64-NEXT: xorl %eax, %eax -; X64-NEXT: cmpw %dx, %cx -; X64-NEXT: setne %al +; X64-NEXT: cmpl $9362, %ecx # imm = 0x2492 +; X64-NEXT: seta %al ; X64-NEXT: # kill: def $ax killed $ax killed $eax ; X64-NEXT: retq %urem = urem i16 %X, 14 @@ -153,27 +113,20 @@ define i32 @test_urem_even_bit30(i32 %X) nounwind readnone { ; X86-LABEL: test_urem_even_bit30: ; X86: # %bb.0: -; X86-NEXT: movl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl $-415, %edx # imm = 0xFE61 -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: mull %edx -; X86-NEXT: shrl $30, %edx -; X86-NEXT: imull $1073741928, %edx, %edx # imm = 0x40000068 +; X86-NEXT: imull $-51622203, {{[0-9]+}}(%esp), %ecx # imm = 0xFCEC4EC5 +; X86-NEXT: rorl $3, %ecx ; X86-NEXT: xorl %eax, %eax -; X86-NEXT: cmpl %edx, %ecx -; X86-NEXT: sete %al +; X86-NEXT: cmpl $32, %ecx +; X86-NEXT: setb %al ; X86-NEXT: retl ; ; X64-LABEL: test_urem_even_bit30: ; X64: # %bb.0: -; X64-NEXT: movl %edi, %eax -; X64-NEXT: movl $4294966881, %ecx # imm = 0xFFFFFE61 -; X64-NEXT: imulq %rax, %rcx -; X64-NEXT: shrq $62, %rcx -; X64-NEXT: imull $1073741928, %ecx, %ecx # imm = 0x40000068 +; X64-NEXT: imull $-51622203, %edi, %ecx # imm = 0xFCEC4EC5 +; X64-NEXT: rorl $3, %ecx ; X64-NEXT: xorl %eax, %eax -; X64-NEXT: cmpl %ecx, %edi -; X64-NEXT: sete %al +; X64-NEXT: cmpl $32, %ecx +; X64-NEXT: setb %al ; X64-NEXT: retq %urem = urem i32 %X, 1073741928 %cmp = icmp eq i32 %urem, 0 @@ -185,26 +138,20 @@ define i32 @test_urem_even_bit31(i32 %X) nounwind readnone { ; X86-LABEL: test_urem_even_bit31: ; X86: # %bb.0: -; X86-NEXT: movl {{[0-9]+}}(%esp), %ecx -; X86-NEXT: movl $2147483547, %edx # imm = 0x7FFFFF9B -; X86-NEXT: movl %ecx, %eax -; X86-NEXT: mull %edx -; X86-NEXT: shrl $30, %edx -; X86-NEXT: imull $-2147483546, %edx, %edx # imm = 0x80000066 +; X86-NEXT: imull $-1157956869, {{[0-9]+}}(%esp), %ecx # imm = 0xBAFAFAFB +; X86-NEXT: rorl $1, %ecx ; X86-NEXT: xorl %eax, %eax -; X86-NEXT: cmpl %edx, %ecx -; X86-NEXT: sete %al +; X86-NEXT: cmpl $4, %ecx +; X86-NEXT: setb %al ; X86-NEXT: retl ; ; X64-LABEL: test_urem_even_bit31: ; X64: # %bb.0: -; X64-NEXT: movl %edi, %eax -; X64-NEXT: imulq $2147483547, %rax, %rax # imm = 0x7FFFFF9B -; X64-NEXT: shrq $62, %rax -; X64-NEXT: imull $-2147483546, %eax, %ecx # imm = 0x80000066 +; X64-NEXT: imull $-1157956869, %edi, %ecx # imm = 0xBAFAFAFB +; X64-NEXT: rorl $1, %ecx ; X64-NEXT: xorl %eax, %eax -; X64-NEXT: cmpl %ecx, %edi -; X64-NEXT: sete %al +; X64-NEXT: cmpl $4, %ecx +; X64-NEXT: setb %al ; X64-NEXT: retq %urem = urem i32 %X, 2147483750 %cmp = icmp eq i32 %urem, 0