[MSP430] Implement multiplication by a constant

[pftbest]

Summary

The algorithm is borrowed from the Mips backend.

This also makes jumptables more efficient, they no longer require
a libcall.

[hfinkel]

The algorithm is borrowed from the Mips backend.

This looks like target-independent code, and if multiple backends will be using it, please turn it into a target-independent utility, and use that function from both backends, or make it part of the default lowering.

[pftbest]

This looks like target-independent code

You are right, genConstMult function is target-independent.

make it part of the default lowering

I don't think that would work, because we use this function differently.
Mips is calling it from DAGCombine, but MSP430 needs it for lowering.

please turn it into a target-independent utility

Can you please suggest where can I put this function? I've never heard about target-independent utilities.

[efriedma]

Can you please suggest where can I put this function? I've never heard about target-independent utilities.

For this particular function, if you just want to share the code between MSP430 and MIPS, probably makes sense to stick it into the SelectionDAG class

The alternative would be to make this a target-independent lowering in LegalizeDAG.

---

Do you need to worry about codesize here? Lowering something like "a * 0x3333" to an inline sequence like this is going to generate a lot of code.

[pftbest]

Do you need to worry about codesize here? Lowering something like "a * 0x3333" to an inline sequence like this is going to generate a lot of code.

The a * 0x3333 generates the following sequence (the register allocation is not very good in this case):

; BB#0:
	mov.b	r12, r13
	rla.b	r13
	add.b	r13, r12
	rla.b	r13
	rla.b	r13
	rla.b	r13
	mov.b	r13, r14
	sub.b	r12, r14
	rla.b	r13
	rla.b	r13
	sub.b	r14, r13
	mov.w	r13, r12
	ret

It is 24 bytes in size and takes only 12 cycles, which is both smaller and faster than a library call.
If we have the hardware multiplier, then a library function is 20 bytes in size (+4 bytes per call), and takes 20 cycles to execute (including interrupts disabling).
But if we don't have a hardware multiplier, the library function is 70 bytes in size and i don't know how much slower.

We can provide an option like Lanai did ("lanai-constant-mul-threshold"), to limit the number of operations, but I think it would only be useful if we have a hardware multiplier.

[efriedma]

That looks like the code for "a * 0x33", not "a * 0x3333"... but I see your point.

[pftbest]

@efriedma
Good catch, I accidentally used i8 type instead of i16 and didn't notice, sorry.
The correct code is rather large indeed (27 ops), so I'll add the option, and set the default limit to 12.

; BB#0:
	mov.w	r12, r13
	rla.w	r12
	add.w	r12, r13
	rla.w	r12
	rla.w	r12
	rla.w	r12
	mov.w	r12, r14
	sub.w	r13, r14
	rla.w	r12
	rla.w	r12
	mov.w	r12, r13
	sub.w	r14, r13
	rla.w	r12
	rla.w	r12
	mov.w	r12, r14
	sub.w	r13, r14
	rla.w	r12
	rla.w	r12
	mov.w	r12, r13
	sub.w	r14, r13
	rla.w	r12
	rla.w	r12
	mov.w	r12, r14
	sub.w	r13, r14
	rla.w	r12
	rla.w	r12
	sub.w	r14, r12
	ret

[pftbest]

Moved the algorithm into SelectionDAG
Added an option to limit the number of operations

[pftbest]

Fixed an issue with i8 not being promoted to i16 in case we fall back
to libcall.

Added more tests.

[pftbest]

ping

[pftbest]

ping

[pftbest]

ping, please review

[efriedma]

I'm not really the best person to review this (since I'm not really that familiar with either MIPS or MSP430), but I can provide some more comments.

lib/Target/MSP430/MSP430ISelLowering.cpp

1337

I'm not sure this algorithm is right? In any case, it's a lot different from what getMulByConstant is actually doing, so needs a lot of comments.

test/CodeGen/MSP430/mul-by-constant.ll

10

A testcase for some negative numbers would make sense. (e.g. x*-3 should lower to something like x - (x << 2)).

include/llvm/CodeGen/SelectionDAG.h

#endif
   /// just have an ISD::CondCode instead of an SDValue.
   ///
   SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
                       SDValue False, ISD::CondCode Cond) {
     return getNode(ISD::SELECT_CC, DL, True.getValueType(),
                    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,
                    SDValue SV, unsigned Align);
 
   /// Gets a node for an atomic cmpxchg op. There are two
   /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
   /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

assert(N->getIndex().getValueType().getVectorNumElements() ==
              N->getValue().getValueType().getVectorNumElements() &&
          "Vector width mismatch between index and data");
 
   CSEMap.InsertNode(N, IP);
   InsertNode(N);
   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) };
   return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
 }
 
 SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
                               ArrayRef<SDUse> Ops) {

lib/Target/MSP430/MSP430ISelLowering.h

public:
     SDValue LowerBR_CC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSETCC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSIGN_EXTEND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
     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;
     std::pair<unsigned, const TargetRegisterClass *>
     getRegForInlineAsmConstraint(const TargetRegisterInfo *TRI,
                                  StringRef Constraint, MVT VT) const override;
 
     /// isTruncateFree - Return true if it's free to truncate a value of type

lib/Target/MSP430/MSP430ISelLowering.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #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<unsigned> 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) {
 
   // Set up the register classes.
   addRegisterClass(MVT::i8,  &MSP430::GR8RegClass);
   addRegisterClass(MVT::i16, &MSP430::GR16RegClass);
 
MSP430TargetLowering::MSP430TargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::SHL_PARTS,        MVT::i16,   Expand);
   setOperationAction(ISD::SRL_PARTS,        MVT::i8,    Expand);
   setOperationAction(ISD::SRL_PARTS,        MVT::i16,   Expand);
   setOperationAction(ISD::SRA_PARTS,        MVT::i8,    Expand);
   setOperationAction(ISD::SRA_PARTS,        MVT::i16,   Expand);
 
   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);
   setOperationAction(ISD::UMUL_LOHI,        MVT::i16,   Expand);
 
   setOperationAction(ISD::UDIV,             MVT::i8,    Promote);
   setOperationAction(ISD::UDIVREM,          MVT::i8,    Promote);
   setOperationAction(ISD::UREM,             MVT::i8,    Promote);
SDValue MSP430TargetLowering::LowerOperation(SDValue Op,
   case ISD::SETCC:            return LowerSETCC(Op, DAG);
   case ISD::BR_CC:            return LowerBR_CC(Op, DAG);
   case ISD::SELECT_CC:        return LowerSELECT_CC(Op, DAG);
   case ISD::SIGN_EXTEND:      return LowerSIGN_EXTEND(Op, DAG);
   case ISD::RETURNADDR:       return LowerRETURNADDR(Op, DAG);
   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");
   }
 }
 
 //===----------------------------------------------------------------------===//
 //                       MSP430 Inline Assembly Support
 //===----------------------------------------------------------------------===//

 SDValue MSP430TargetLowering::LowerJumpTable(SDValue Op,
                                              SelectionDAG &DAG) const {
     JumpTableSDNode *JT = cast<JumpTableSDNode>(Op);
     auto PtrVT = getPointerTy(DAG.getDataLayout());
     SDValue Result = DAG.getTargetJumpTable(JT->getIndex(), PtrVT);
     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<ConstantSDNode>(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.
 bool MSP430TargetLowering::getPostIndexedAddressParts(SDNode *N, SDNode *Op,
                                                       SDValue &Base,
                                                       SDValue &Offset,
                                                       ISD::MemIndexedMode &AM,
                                                       SelectionDAG &DAG) const {

lib/Target/Mips/MipsSEISelLowering.cpp

if (Op0->getOpcode() == ISD::AND && Op1->getOpcode() == ISD::AND) {
 
     // Transform the DAG into an equivalent VSELECT.
     return DAG.getNode(ISD::VSELECT, SDLoc(N), Ty, Cond, IfSet, IfClr);
   }
 
   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) {
   EVT VT = N->getValueType(0);
 
   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(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);
 }
 
 static SDValue performDSPShiftCombine(unsigned Opc, SDNode *N, EVT Ty,
                                       SelectionDAG &DAG,
                                       const MipsSubtarget &Subtarget) {
   // See if this is a vector splat immediate node.

test/CodeGen/MSP430/jumptable.ll

 ; RUN: llc < %s | FileCheck %s
 
 target datalayout = "e-p:16:16:16-i8:8:8-i16:16:16-i32:16:32-n8:16"
 target triple = "msp430---elf"
 
 ; Function Attrs: nounwind
 define i16 @test(i16 %i) #0 {
 entry:
 ; CHECK-LABEL: test:
   %retval = alloca i16, align 2
   %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
     i16 2, label %sw.bb2
     i16 3, label %sw.bb3
   ]
 
 sw.bb:                                            ; preds = %entry

test/CodeGen/MSP430/mul-by-constant.ll

+; 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
+}