[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

1328

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

11

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

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;
 
     TargetLowering::ConstraintType
     getConstraintType(StringRef Constraint) const override;
     std::pair<unsigned, const TargetRegisterClass *>
     getRegForInlineAsmConstraint(const TargetRegisterInfo *TRI,
                                  StringRef Constraint, MVT VT) const override;
 

lib/Target/MSP430/MSP430ISelLowering.cpp

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);
 }
 
+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);
+}
+
+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)
+      return SDValue();
+
+    // 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
+    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);
+  }
+
+  return genConstMult(Op->getOperand(0), C->getZExtValue(), DL, VT,
+                      getScalarShiftAmountTy(DAG.getDataLayout(), VT), DAG);
+}
+
 /// 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 {

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