Index: include/llvm/CodeGen/SelectionDAG.h =================================================================== --- include/llvm/CodeGen/SelectionDAG.h +++ include/llvm/CodeGen/SelectionDAG.h @@ -917,6 +917,12 @@ LHS, RHS, True, False, getCondCode(Cond)); } + /// Creates a node for multiplication by a constant using a sequence of bit + /// shifts, ADDs and SUBs. For some constants may produce a very long + /// sequences. + SDValue getMulByConstant(SDValue X, uint64_t C, const SDLoc &DL, EVT VT, + EVT ShiftTy); + /// VAArg produces a result and token chain, and takes a pointer /// and a source value as input. SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, Index: lib/CodeGen/SelectionDAG/SelectionDAG.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -6125,6 +6125,45 @@ return SDValue(N, 0); } +SDValue SelectionDAG::getMulByConstant(SDValue X, uint64_t C, const SDLoc &DL, + EVT VT, EVT ShiftTy) { + assert(VT.getSizeInBits() <= 64 && "Unsupported value size"); + + // Clear the upper (64 - VT.sizeInBits) bits. + C &= ((uint64_t)-1) >> (64 - VT.getSizeInBits()); + + // Return 0. + if (C == 0) + return getConstant(0, DL, VT); + + // Return x. + if (C == 1) + return X; + + // If c is power of 2, return (shl x, log2(c)). + if (isPowerOf2_64(C)) + return getNode(ISD::SHL, DL, VT, X, getConstant(Log2_64(C), DL, ShiftTy)); + + unsigned Log2Ceil = Log2_64_Ceil(C); + uint64_t Floor = 1LL << Log2_64(C); + uint64_t Ceil = Log2Ceil == 64 ? 0LL : 1LL << Log2Ceil; + + // If |c - floor_c| <= |c - ceil_c|, + // where floor_c = pow(2, floor(log2(c))) and ceil_c = pow(2, ceil(log2(c))), + // return (add constMult(x, floor_c), constMult(x, c - floor_c)). + if (C - Floor <= Ceil - C) { + SDValue Op0 = getMulByConstant(X, Floor, DL, VT, ShiftTy); + SDValue Op1 = getMulByConstant(X, C - Floor, DL, VT, ShiftTy); + return getNode(ISD::ADD, DL, VT, Op0, Op1); + } + + // If |c - floor_c| > |c - ceil_c|, + // return (sub constMult(x, ceil_c), constMult(x, ceil_c - c)). + SDValue Op0 = getMulByConstant(X, Ceil, DL, VT, ShiftTy); + SDValue Op1 = getMulByConstant(X, Ceil - C, DL, VT, ShiftTy); + return getNode(ISD::SUB, DL, VT, Op0, Op1); +} + SDValue SelectionDAG::getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue SV, unsigned Align) { SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) }; Index: lib/Target/MSP430/MSP430ISelLowering.h =================================================================== --- lib/Target/MSP430/MSP430ISelLowering.h +++ lib/Target/MSP430/MSP430ISelLowering.h @@ -95,7 +95,9 @@ SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const; SDValue LowerVASTART(SDValue Op, SelectionDAG &DAG) const; SDValue LowerJumpTable(SDValue Op, SelectionDAG &DAG) const; + SDValue LowerMUL(SDValue Op, SelectionDAG &DAG) const; SDValue getReturnAddressFrameIndex(SelectionDAG &DAG) const; + SDValue PromoteMULi8(SDValue Op, SelectionDAG &DAG) const; TargetLowering::ConstraintType getConstraintType(StringRef Constraint) const override; Index: lib/Target/MSP430/MSP430ISelLowering.cpp =================================================================== --- lib/Target/MSP430/MSP430ISelLowering.cpp +++ lib/Target/MSP430/MSP430ISelLowering.cpp @@ -38,6 +38,15 @@ #define DEBUG_TYPE "msp430-lower" +// Limit on number of instructions the lowered multiplication may have before a +// call to the library function should be generated instead. +static cl::opt ConstantMulThreshold( + "msp430-constant-mul-threshold", cl::Hidden, + cl::desc( + "Maximum number of instructions to generate when lowering constant " + "multiplication instead of calling a library function [default=10]"), + cl::init(10)); + MSP430TargetLowering::MSP430TargetLowering(const TargetMachine &TM, const MSP430Subtarget &STI) : TargetLowering(TM) { @@ -112,13 +121,12 @@ setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1, Expand); - // FIXME: Implement efficiently multiplication by a constant - setOperationAction(ISD::MUL, MVT::i8, Promote); + setOperationAction(ISD::MUL, MVT::i8, Custom); setOperationAction(ISD::MULHS, MVT::i8, Promote); setOperationAction(ISD::MULHU, MVT::i8, Promote); setOperationAction(ISD::SMUL_LOHI, MVT::i8, Promote); setOperationAction(ISD::UMUL_LOHI, MVT::i8, Promote); - setOperationAction(ISD::MUL, MVT::i16, LibCall); + setOperationAction(ISD::MUL, MVT::i16, Custom); setOperationAction(ISD::MULHS, MVT::i16, Expand); setOperationAction(ISD::MULHU, MVT::i16, Expand); setOperationAction(ISD::SMUL_LOHI, MVT::i16, Expand); @@ -342,6 +350,7 @@ case ISD::FRAMEADDR: return LowerFRAMEADDR(Op, DAG); case ISD::VASTART: return LowerVASTART(Op, DAG); case ISD::JumpTable: return LowerJumpTable(Op, DAG); + case ISD::MUL: return LowerMUL(Op, DAG); default: llvm_unreachable("unimplemented operand"); } @@ -1298,6 +1307,60 @@ return DAG.getNode(MSP430ISD::Wrapper, SDLoc(JT), PtrVT, Result); } +SDValue MSP430TargetLowering::LowerMUL(SDValue Op, SelectionDAG &DAG) const { + EVT VT = Op->getValueType(0); + if (VT != MVT::i8 && VT != MVT::i16) + return SDValue(); + + SDLoc DL(Op); + + ConstantSDNode *C = dyn_cast(Op->getOperand(1)); + if (!C) { + if (VT == MVT::i8) { + // If the argument is i8 and is not a constant, we need to promote the mul + // to i16, because we don't have a libcall for i8 + return PromoteMULi8(Op, DAG); + } + return SDValue(); + } + + // Estimate the number of operations required to multiply by this constant + uint64_t MulAmt = C->getZExtValue(); + unsigned NumberOfOps = 0; + while (MulAmt > 0) { + if (MulAmt % 2 == 1) { + NumberOfOps += 1; + int Z = 2 - (MulAmt % 4); + MulAmt -= Z; + } + NumberOfOps += 1; + MulAmt >>= 1; + } + + if (NumberOfOps > ConstantMulThreshold) { + if (VT == MVT::i8) + return PromoteMULi8(Op, DAG); + return SDValue(); + } + + return DAG.getMulByConstant(Op->getOperand(0), C->getZExtValue(), DL, VT, + getScalarShiftAmountTy(DAG.getDataLayout(), VT)); +} + +SDValue MSP430TargetLowering::PromoteMULi8(SDValue Op, + SelectionDAG &DAG) const { + EVT VT = Op->getValueType(0); + assert((VT == MVT::i8) && "Unexpected value type"); + assert((Op->getOpcode() == ISD::MUL) && "Unexpected opcode"); + + SDLoc DL(Op); + SDValue Tmp1, Tmp2; + Tmp1 = DAG.getNode(ISD::ANY_EXTEND, DL, MVT::i16, Op->getOperand(0)); + Tmp2 = DAG.getNode(ISD::ANY_EXTEND, DL, MVT::i16, Op->getOperand(1)); + Tmp1 = DAG.getNode(ISD::MUL, DL, MVT::i16, Tmp1, Tmp2); + return DAG.getNode(ISD::TRUNCATE, DL, MVT::i8, Tmp1); +} + /// getPostIndexedAddressParts - returns true by value, base pointer and /// offset pointer and addressing mode by reference if this node can be /// combined with a load / store to form a post-indexed load / store. Index: lib/Target/Mips/MipsSEISelLowering.cpp =================================================================== --- lib/Target/Mips/MipsSEISelLowering.cpp +++ lib/Target/Mips/MipsSEISelLowering.cpp @@ -701,44 +701,6 @@ return SDValue(); } -static SDValue genConstMult(SDValue X, uint64_t C, const SDLoc &DL, EVT VT, - EVT ShiftTy, SelectionDAG &DAG) { - // Clear the upper (64 - VT.sizeInBits) bits. - C &= ((uint64_t)-1) >> (64 - VT.getSizeInBits()); - - // Return 0. - if (C == 0) - return DAG.getConstant(0, DL, VT); - - // Return x. - if (C == 1) - return X; - - // If c is power of 2, return (shl x, log2(c)). - if (isPowerOf2_64(C)) - return DAG.getNode(ISD::SHL, DL, VT, X, - DAG.getConstant(Log2_64(C), DL, ShiftTy)); - - unsigned Log2Ceil = Log2_64_Ceil(C); - uint64_t Floor = 1LL << Log2_64(C); - uint64_t Ceil = Log2Ceil == 64 ? 0LL : 1LL << Log2Ceil; - - // If |c - floor_c| <= |c - ceil_c|, - // where floor_c = pow(2, floor(log2(c))) and ceil_c = pow(2, ceil(log2(c))), - // return (add constMult(x, floor_c), constMult(x, c - floor_c)). - if (C - Floor <= Ceil - C) { - SDValue Op0 = genConstMult(X, Floor, DL, VT, ShiftTy, DAG); - SDValue Op1 = genConstMult(X, C - Floor, DL, VT, ShiftTy, DAG); - return DAG.getNode(ISD::ADD, DL, VT, Op0, Op1); - } - - // If |c - floor_c| > |c - ceil_c|, - // return (sub constMult(x, ceil_c), constMult(x, ceil_c - c)). - SDValue Op0 = genConstMult(X, Ceil, DL, VT, ShiftTy, DAG); - SDValue Op1 = genConstMult(X, Ceil - C, DL, VT, ShiftTy, DAG); - return DAG.getNode(ISD::SUB, DL, VT, Op0, Op1); -} - static SDValue performMULCombine(SDNode *N, SelectionDAG &DAG, const TargetLowering::DAGCombinerInfo &DCI, const MipsSETargetLowering *TL) { @@ -746,9 +708,9 @@ if (ConstantSDNode *C = dyn_cast(N->getOperand(1))) if (!VT.isVector()) - return genConstMult(N->getOperand(0), C->getZExtValue(), SDLoc(N), VT, - TL->getScalarShiftAmountTy(DAG.getDataLayout(), VT), - DAG); + return DAG.getMulByConstant( + N->getOperand(0), C->getZExtValue(), SDLoc(N), VT, + TL->getScalarShiftAmountTy(DAG.getDataLayout(), VT)); return SDValue(N, 0); } Index: test/CodeGen/MSP430/jumptable.ll =================================================================== --- test/CodeGen/MSP430/jumptable.ll +++ test/CodeGen/MSP430/jumptable.ll @@ -11,9 +11,8 @@ %i.addr = alloca i16, align 2 store i16 %i, i16* %i.addr, align 2 %0 = load i16, i16* %i.addr, align 2 -; CHECK: mov.w #2, r13 -; CHECK: call #__mspabi_mpyi -; CHECK: br .LJTI0_0(r12) +; CHECK: rla.w [[REG:r[0-9]+]] +; CHECK: br .LJTI0_0([[REG]]) switch i16 %0, label %sw.default [ i16 0, label %sw.bb i16 1, label %sw.bb1 Index: test/CodeGen/MSP430/mul-by-constant.ll =================================================================== --- /dev/null +++ test/CodeGen/MSP430/mul-by-constant.ll @@ -0,0 +1,67 @@ +; RUN: llc < %s | FileCheck %s + +target triple = "msp430-none-elf" + +; CHECK-LABEL: foo16 +; CHECK: rla.w +; CHECK: add.w +define zeroext i16 @foo16(i16) local_unnamed_addr { + %2 = mul i16 %0, 3 + ret i16 %2 +} + +; CHECK-LABEL: bar16 +; CHECK: rla.w +; CHECK: rla.w +; CHECK: rla.w +; CHECK: sub.w +define zeroext i16 @bar16(i16) local_unnamed_addr { + %2 = mul i16 %0, 7 + ret i16 %2 +} + +; CHECK-LABEL: foo8 +; CHECK: rla.b +; CHECK: add.b +define zeroext i8 @foo8(i8) local_unnamed_addr { + %2 = mul i8 %0, 3 + ret i8 %2 +} + +; CHECK-LABEL: bar8 +; CHECK: rla.b +; CHECK: rla.b +; CHECK: rla.b +; CHECK: sub.b +define zeroext i8 @bar8(i8) local_unnamed_addr { + %2 = mul i8 %0, 7 + ret i8 %2 +} + +; CHECK-LABEL: large16 +; CHECK: call #__mspabi_mpyi +define zeroext i16 @large16(i16) local_unnamed_addr { + %2 = mul i16 %0, 85 + ret i16 %2 +} + +; CHECK-LABEL: large8 +; CHECK: call #__mspabi_mpyi +define zeroext i8 @large8(i8) local_unnamed_addr { + %2 = mul i8 %0, 85 + ret i8 %2 +} + +; CHECK-LABEL: small16 +; CHECK: rla.w +define zeroext i16 @small16(i16) local_unnamed_addr { + %2 = mul i16 %0, 127 + ret i16 %2 +} + +; CHECK-LABEL: small8 +; CHECK: rla.b +define zeroext i8 @small8(i8) local_unnamed_addr { + %2 = mul i8 %0, 127 + ret i8 %2 +}