[mips] Improve code generation for constant multiplication using shifts, adds and

subs.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185011 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 103 insertions, 0 deletions

diff --git a/lib/Target/Mips/MipsSEISelLowering.cpp b/lib/Target/Mips/MipsSEISelLowering.cpp
index f640ecc..8b5a874 100644
--- a/lib/Target/Mips/MipsSEISelLowering.cpp
+++ b/lib/Target/Mips/MipsSEISelLowering.cpp
@@ -99,6 +99,7 @@ MipsSETargetLowering::MipsSETargetLowering(MipsTargetMachine &TM)
 
   setTargetDAGCombine(ISD::ADDE);
   setTargetDAGCombine(ISD::SUBE);
+  setTargetDAGCombine(ISD::MUL);
 
   computeRegisterProperties();
 }
@@ -320,6 +321,57 @@ static SDValue performSUBECombine(SDNode *N, SelectionDAG &DAG,
   return SDValue();
 }
 
+static SDValue genConstMult(SDValue X, uint64_t C, 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, 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), 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(VT), DAG);
+
+  return SDValue(N, 0);
+}
+
 static SDValue performDSPShiftCombine(unsigned Opc, SDNode *N, EVT Ty,
                                       SelectionDAG &DAG,
                                       const MipsSubtarget *Subtarget) {
@@ -432,6 +484,8 @@ MipsSETargetLowering::PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
     return performADDECombine(N, DAG, DCI, Subtarget);
   case ISD::SUBE:
     return performSUBECombine(N, DAG, DCI, Subtarget);
+  case ISD::MUL:
+    return performMULCombine(N, DAG, DCI, this);
   case ISD::SHL:
     return performSHLCombine(N, DAG, DCI, Subtarget);
   case ISD::SRA:
diff --git a/test/CodeGen/Mips/const-mult.ll b/test/CodeGen/Mips/const-mult.ll
new file mode 100644
index 0000000..d818044
--- /dev/null
+++ b/test/CodeGen/Mips/const-mult.ll
@@ -0,0 +1,49 @@
+; RUN: llc -march=mipsel < %s | FileCheck %s -check-prefix=CHECK
+; RUN: llc -march=mips64el -mcpu=mips64 < %s | FileCheck %s -check-prefix=CHECK
+; RUN: llc -march=mips64el -mcpu=mips64 < %s | FileCheck %s -check-prefix=CHECK64
+
+; CHECK: mul5_32:
+; CHECK: sll $[[R0:[0-9]+]], $4, 2
+; CHECK: addu ${{[0-9]+}}, $[[R0]], $4
+
+define i32 @mul5_32(i32 %a) {
+entry:
+  %mul = mul nsw i32 %a, 5
+  ret i32 %mul
+}
+
+; CHECK:     mul27_32:
+; CHECK-DAG: sll $[[R0:[0-9]+]], $4, 2
+; CHECK-DAG: addu $[[R1:[0-9]+]], $[[R0]], $4
+; CHECK-DAG: sll $[[R2:[0-9]+]], $4, 5
+; CHECK:     subu ${{[0-9]+}}, $[[R2]], $[[R1]]
+
+define i32 @mul27_32(i32 %a) {
+entry:
+  %mul = mul nsw i32 %a, 27
+  ret i32 %mul
+}
+
+; CHECK:     muln2147483643_32:
+; CHECK-DAG: sll $[[R0:[0-9]+]], $4, 2
+; CHECK-DAG: addu $[[R1:[0-9]+]], $[[R0]], $4
+; CHECK-DAG: sll $[[R2:[0-9]+]], $4, 31
+; CHECK:     addu ${{[0-9]+}}, $[[R2]], $[[R1]]
+
+define i32 @muln2147483643_32(i32 %a) {
+entry:
+  %mul = mul nsw i32 %a, -2147483643
+  ret i32 %mul
+}
+
+; CHECK64:     muln9223372036854775805_64:
+; CHECK64-DAG: sll $[[R0:[0-9]+]], $4, 1
+; CHECK64-DAG: addu $[[R1:[0-9]+]], $[[R0]], $4
+; CHECK64-DAG: sll $[[R2:[0-9]+]], $4, 63
+; CHECK64:     addu ${{[0-9]+}}, $[[R2]], $[[R1]]
+
+define i64 @muln9223372036854775805_64(i64 %a) {
+entry:
+  %mul = mul nsw i64 %a, -9223372036854775805
+  ret i64 %mul
+}