[mips] Always check that `shift and add` optimization is efficient

[atanasyan]

Summary

The D45316 introduced the shouldTransformMulToShiftsAddsSubs function to check that breaking down constant multiplications into a series of shifts, adds, and subs is efficient. Unfortunately, this function does not check maximum number of steps on all paths of the algorithm. This patch fixes this bug.

Fix for PR41929.

[atanasyan]

• Make the code more compact
• Remove magical constant from the loop condition

[mstojanovic]

llvm/lib/Target/Mips/MipsSEISelLowering.cpp

780–781

You could also move this as the first thing in the while block which removes the Steps <= MaxSteps check.

[atanasyan]

• Simplify the loop condition

[Petar.Avramovic]

LGTM.

llvm/lib/Target/Mips/MipsSEISelLowering.cpp

722–746

This comment can be misleading. The number is approximately equal to the minimal number of powers of two that constant can be broken down to by adding or subtracting them.

[sdardis]

I've raised some points inline, I think (a) is most relevant to this patch but shouldn't stop it going forward but should be addressed quickly, (b) and (c) could be noted as TODO:s.

llvm/lib/Target/Mips/MipsSEISelLowering.cpp

723–736

Looking at this and the original version, some things come to mind:

a) MaxSteps needs to consider the VT of the constant for the target. I.E. for a 32 bit multiplication on a N32/N64 target the maximum number of steps is incorrect. I believe the calculation of the maximum number of steps needs to consider the case of <=i32 and >i32 && <=i64 cases for natively supported types.

I would suggest looking at starting with the maximum number of steps as equal to the number of cycles that it takes to perform a constant materialization sequence worst case, then applying a "legalization penalty" to the number of steps if the type of the operands is not natively supported.

b) This optimization can occur before type legalization, it may be worth considering restricting this optimization to after type legalization so that there is no fudge on the legalization penalty of an illegal type for some constant value (lines 771-780).

c) This optimization should be account for -Os, -Oz, as the optimization can increase code size.

[atanasyan]

• Add TODO comment

[atanasyan]

In D62166#1511162, @sdardis wrote:

I've raised some points inline, I think (a) is most relevant to this patch but shouldn't stop it going forward but should be addressed quickly, (b) and (c) could be noted as TODO:s.

Thanks. I will implement it.

[sdardis]

LGTM.

[atanasyan]

Thanks for review.

llvm/lib/Target/Mips/MipsSEISelLowering.cpp

static SDValue performORCombine(SDNode *N, SelectionDAG &DAG,
 
   return SDValue();
 }
 
 static bool shouldTransformMulToShiftsAddsSubs(APInt C, EVT VT,
                                                SelectionDAG &DAG,
                                                const MipsSubtarget &Subtarget) {
   // Estimate the number of operations the below transform will turn a
-  // constant multiply into. The number is approximately how many powers
-  // of two summed together that the constant can be broken down into.
+  // constant multiply into. The number is approximately equal to the minimal
+  // number of powers of two that constant can be broken down to by adding
+  // or subtracting them.
+  //
+  // If we have taken more than 12[1] / 8[2] steps to attempt the
+  // optimization for a native sized value, it is more than likely that this
+  // optimization will make things worse.
+  //
+  // [1] MIPS64 requires 6 instructions at most to materialize any constant,
+  //     multiplication requires at least 4 cycles, but another cycle (or two)
+  //     to retrieve the result from the HI/LO registers.
+  //
+  // [2] For MIPS32, more than 8 steps is expensive as the constant could be
+  //     materialized in 2 instructions, multiplication requires at least 4
+  //     cycles, but another cycle (or two) to retrieve the result from the
+  //     HI/LO registers.
+  //
+  // TODO:
+  // - MaxSteps needs to consider the `VT` of the constant for the current
+  //   target.
+  // - Consider to perform this optimization after type legalization.
+  //   That allows to remove a workaround for types not supported natively.
+  // - Take in account `-Os, -Oz` flags because this optimization
+  //   increases code size.
+  unsigned MaxSteps = Subtarget.isABI_O32() ? 8 : 12;
 
   SmallVector<APInt, 16> WorkStack(1, C);
   unsigned Steps = 0;
   unsigned BitWidth = C.getBitWidth();
 
   while (!WorkStack.empty()) {
     APInt Val = WorkStack.pop_back_val();
 
     if (Val == 0 || Val == 1)
       continue;
 
+    if (Steps >= MaxSteps)
+      return false;
+
     if (Val.isPowerOf2()) {
       ++Steps;
       continue;
     }
 
     APInt Floor = APInt(BitWidth, 1) << Val.logBase2();
     APInt Ceil = Val.isNegative() ? APInt(BitWidth, 0)
                                   : APInt(BitWidth, 1) << C.ceilLogBase2();
-
     if ((Val - Floor).ule(Ceil - Val)) {
       WorkStack.push_back(Floor);
       WorkStack.push_back(Val - Floor);
-      ++Steps;
-      continue;
-    }
-
+    } else {
       WorkStack.push_back(Ceil);
       WorkStack.push_back(Ceil - Val);
-    ++Steps;
-
-    // If we have taken more than 12[1] / 8[2] steps to attempt the
-    // optimization for a native sized value, it is more than likely that this
-    // optimization will make things worse.
-    //
-    // [1] MIPS64 requires 6 instructions at most to materialize any constant,
-    //     multiplication requires at least 4 cycles, but another cycle (or two)
-    //     to retrieve the result from the HI/LO registers.
-    //
-    // [2] For MIPS32, more than 8 steps is expensive as the constant could be
-    //     materialized in 2 instructions, multiplication requires at least 4
-    //     cycles, but another cycle (or two) to retrieve the result from the
-    //     HI/LO registers.
-
-    if (Steps > 12 && (Subtarget.isABI_N32() || Subtarget.isABI_N64()))
-      return false;
+    }
 
-    if (Steps > 8 && Subtarget.isABI_O32())
-      return false;
+    ++Steps;
   }
 
   // If the value being multiplied is not supported natively, we have to pay
   // an additional legalization cost, conservatively assume an increase in the
   // cost of 3 instructions per step. This values for this heuristic were
   // determined experimentally.
   unsigned RegisterSize = DAG.getTargetLoweringInfo()
                               .getRegisterType(*DAG.getContext(), VT)
                               .getSizeInBits();
   Steps *= (VT.getSizeInBits() != RegisterSize) * 3;
   if (Steps > 27)
     return false;

llvm/test/CodeGen/Mips/const-mult.ll

 entry:
   %mul = mul nsw i128 %a, 170141183460469231731687303715884105723
   ret i128 %mul
 }
 
 define i32 @mul42949673_32(i32 %a) {
 ; MIPS32-LABEL: mul42949673_32:
 ; MIPS32:       # %bb.0:
-; MIPS32-NEXT:    sll $1, $4, 3
-; MIPS32-NEXT:    addu $1, $1, $4
-; MIPS32-NEXT:    sll $2, $4, 5
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 10
-; MIPS32-NEXT:    subu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 13
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 15
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 20
-; MIPS32-NEXT:    subu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 25
-; MIPS32-NEXT:    sll $3, $4, 23
-; MIPS32-NEXT:    addu $1, $3, $1
+; MIPS32-NEXT:    lui $1, 655
+; MIPS32-NEXT:    ori $1, $1, 23593
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $2, $2, $1
+; MIPS32-NEXT:    mul $2, $4, $1
 ;
 ; MIPS64-LABEL: mul42949673_32:
 ; MIPS64:       # %bb.0:
-; MIPS64-NEXT:    sll $1, $4, 0
-; MIPS64-NEXT:    sll $2, $1, 3
-; MIPS64-NEXT:    addu $2, $2, $1
-; MIPS64-NEXT:    sll $3, $1, 5
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 10
-; MIPS64-NEXT:    subu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 13
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 15
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 20
-; MIPS64-NEXT:    subu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 25
-; MIPS64-NEXT:    sll $1, $1, 23
-; MIPS64-NEXT:    addu $1, $1, $2
+; MIPS64-NEXT:    lui $1, 655
+; MIPS64-NEXT:    ori $1, $1, 23593
+; MIPS64-NEXT:    sll $2, $4, 0
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    addu $2, $3, $1
+; MIPS64-NEXT:    mul $2, $2, $1
   %b = mul i32 %a, 42949673
   ret i32 %b
 }
 
 define i64 @mul42949673_64(i64 %a) {
 ; MIPS32-LABEL: mul42949673_64:
 ; MIPS32:       # %bb.0: # %entry
 ; MIPS32-NEXT:    lui $1, 655
 ; MIPS32-NEXT:    ori $1, $1, 23593
 ; MIPS32-NEXT:    multu $4, $1
 ; MIPS32-NEXT:    mflo $2
-; MIPS32-NEXT:    mfhi $1
-; MIPS32-NEXT:    sll $3, $5, 3
-; MIPS32-NEXT:    addu $3, $3, $5
-; MIPS32-NEXT:    sll $4, $5, 5
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 10
-; MIPS32-NEXT:    subu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 13
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 15
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 20
-; MIPS32-NEXT:    subu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 25
-; MIPS32-NEXT:    sll $5, $5, 23
-; MIPS32-NEXT:    addu $3, $5, $3
-; MIPS32-NEXT:    addu $3, $4, $3
+; MIPS32-NEXT:    mfhi $3
+; MIPS32-NEXT:    mul $1, $5, $1
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $3, $1, $3
+; MIPS32-NEXT:    addu $3, $3, $1
 ;
 ; MIPS64-LABEL: mul42949673_64:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    dsll $1, $4, 3
-; MIPS64-NEXT:    daddu $1, $1, $4
-; MIPS64-NEXT:    dsll $2, $4, 5
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 10
-; MIPS64-NEXT:    dsubu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 13
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 15
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 20
-; MIPS64-NEXT:    dsubu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 25
-; MIPS64-NEXT:    dsll $3, $4, 23
-; MIPS64-NEXT:    daddu $1, $3, $1
+; MIPS64-NEXT:    lui $1, 655
+; MIPS64-NEXT:    ori $1, $1, 23593
+; MIPS64-NEXT:    dmult $4, $1
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    daddu $2, $2, $1
+; MIPS64-NEXT:    mflo $2
 entry:
   %b = mul i64 %a, 42949673
   ret i64 %b
 }
 
 define i32 @mul22224078_32(i32 %a) {
 ; MIPS32-LABEL: mul22224078_32:
 ; MIPS32:       # %bb.0: # %entry
-; MIPS32-NEXT:    sll $1, $4, 1
-; MIPS32-NEXT:    sll $2, $4, 4
-; MIPS32-NEXT:    subu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 6
-; MIPS32-NEXT:    subu $1, $1, $2
-; MIPS32-NEXT:    sll $2, $4, 8
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 10
-; MIPS32-NEXT:    subu $1, $1, $2
-; MIPS32-NEXT:    sll $2, $4, 13
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 16
-; MIPS32-NEXT:    subu $1, $1, $2
-; MIPS32-NEXT:    sll $2, $4, 24
-; MIPS32-NEXT:    sll $3, $4, 22
-; MIPS32-NEXT:    sll $5, $4, 20
-; MIPS32-NEXT:    sll $4, $4, 18
-; MIPS32-NEXT:    addu $1, $4, $1
-; MIPS32-NEXT:    addu $1, $5, $1
-; MIPS32-NEXT:    addu $1, $3, $1
+; MIPS32-NEXT:    lui $1, 339
+; MIPS32-NEXT:    ori $1, $1, 7374
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $2, $2, $1
+; MIPS32-NEXT:    mul $2, $4, $1
 ;
 ; MIPS64-LABEL: mul22224078_32:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    sll $1, $4, 0
-; MIPS64-NEXT:    sll $2, $1, 1
-; MIPS64-NEXT:    sll $3, $1, 4
-; MIPS64-NEXT:    subu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 6
-; MIPS64-NEXT:    subu $2, $2, $3
-; MIPS64-NEXT:    sll $3, $1, 8
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 10
-; MIPS64-NEXT:    subu $2, $2, $3
-; MIPS64-NEXT:    sll $3, $1, 13
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 16
-; MIPS64-NEXT:    subu $2, $2, $3
-; MIPS64-NEXT:    sll $3, $1, 24
-; MIPS64-NEXT:    sll $4, $1, 22
-; MIPS64-NEXT:    sll $5, $1, 20
-; MIPS64-NEXT:    sll $1, $1, 18
-; MIPS64-NEXT:    addu $1, $1, $2
-; MIPS64-NEXT:    addu $1, $5, $1
-; MIPS64-NEXT:    addu $1, $4, $1
+; MIPS64-NEXT:    lui $1, 339
+; MIPS64-NEXT:    ori $1, $1, 7374
+; MIPS64-NEXT:    sll $2, $4, 0
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    addu $2, $3, $1
+; MIPS64-NEXT:    mul $2, $2, $1
 entry:
   %b = mul i32 %a, 22224078
   ret i32 %b
 }
 
 define i64 @mul22224078_64(i64 %a) {
 ; MIPS32-LABEL: mul22224078_64:
 ; MIPS32:       # %bb.0: # %entry
 ; MIPS32-NEXT:    lui $1, 339
 ; MIPS32-NEXT:    ori $1, $1, 7374
 ; MIPS32-NEXT:    multu $4, $1
 ; MIPS32-NEXT:    mflo $2
-; MIPS32-NEXT:    mfhi $1
-; MIPS32-NEXT:    sll $3, $5, 1
-; MIPS32-NEXT:    sll $4, $5, 4
-; MIPS32-NEXT:    subu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 6
-; MIPS32-NEXT:    subu $3, $3, $4
-; MIPS32-NEXT:    sll $4, $5, 8
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 10
-; MIPS32-NEXT:    subu $3, $3, $4
-; MIPS32-NEXT:    sll $4, $5, 13
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 16
-; MIPS32-NEXT:    subu $3, $3, $4
-; MIPS32-NEXT:    sll $4, $5, 24
-; MIPS32-NEXT:    sll $6, $5, 22
-; MIPS32-NEXT:    sll $7, $5, 20
-; MIPS32-NEXT:    sll $5, $5, 18
-; MIPS32-NEXT:    addu $3, $5, $3
-; MIPS32-NEXT:    addu $3, $7, $3
-; MIPS32-NEXT:    addu $3, $6, $3
-; MIPS32-NEXT:    addu $3, $4, $3
+; MIPS32-NEXT:    mfhi $3
+; MIPS32-NEXT:    mul $1, $5, $1
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $3, $1, $3
+; MIPS32-NEXT:    addu $3, $3, $1
 ;
 ; MIPS64-LABEL: mul22224078_64:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    dsll $1, $4, 1
-; MIPS64-NEXT:    dsll $2, $4, 4
-; MIPS64-NEXT:    dsubu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 6
-; MIPS64-NEXT:    dsubu $1, $1, $2
-; MIPS64-NEXT:    dsll $2, $4, 8
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 10
-; MIPS64-NEXT:    dsubu $1, $1, $2
-; MIPS64-NEXT:    dsll $2, $4, 13
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 16
-; MIPS64-NEXT:    dsubu $1, $1, $2
-; MIPS64-NEXT:    dsll $2, $4, 24
-; MIPS64-NEXT:    dsll $3, $4, 22
-; MIPS64-NEXT:    dsll $5, $4, 20
-; MIPS64-NEXT:    dsll $4, $4, 18
-; MIPS64-NEXT:    daddu $1, $4, $1
-; MIPS64-NEXT:    daddu $1, $5, $1
-; MIPS64-NEXT:    daddu $1, $3, $1
+; MIPS64-NEXT:    lui $1, 339
+; MIPS64-NEXT:    ori $1, $1, 7374
+; MIPS64-NEXT:    dmult $4, $1
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    daddu $2, $2, $1
+; MIPS64-NEXT:    mflo $2
 entry:
   %b = mul i64 %a, 22224078
   ret i64 %b
 }
 
 define i32 @mul22245375_32(i32 %a) {
 ; MIPS32-LABEL: mul22245375_32:
 ; MIPS32:       # %bb.0: # %entry
-; MIPS32-NEXT:    sll $1, $4, 12
-; MIPS32-NEXT:    addu $1, $1, $4
-; MIPS32-NEXT:    sll $2, $4, 15
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 18
-; MIPS32-NEXT:    subu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 20
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 22
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 24
+; MIPS32-NEXT:    lui $1, 339
+; MIPS32-NEXT:    ori $1, $1, 28671
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $2, $2, $1
+; MIPS32-NEXT:    mul $2, $4, $1
 ;
 ; MIPS64-LABEL: mul22245375_32:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    sll $1, $4, 0
-; MIPS64-NEXT:    sll $2, $1, 12
-; MIPS64-NEXT:    addu $2, $2, $1
-; MIPS64-NEXT:    sll $3, $1, 15
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 18
-; MIPS64-NEXT:    subu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 20
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 22
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $1, $1, 24
+; MIPS64-NEXT:    lui $1, 339
+; MIPS64-NEXT:    ori $1, $1, 28671
+; MIPS64-NEXT:    sll $2, $4, 0
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    addu $2, $1, $2
+; MIPS64-NEXT:    mul $2, $2, $1
 entry:
   %b = mul i32 %a, 22245375
   ret i32 %b
 }
 
 define i64 @mul22245375_64(i64 %a) {
 ; MIPS32-LABEL: mul22245375_64:
 ; MIPS32:       # %bb.0: # %entry
 ; MIPS32-NEXT:    lui $1, 339
 ; MIPS32-NEXT:    ori $1, $1, 28671
 ; MIPS32-NEXT:    multu $4, $1
 ; MIPS32-NEXT:    mflo $2
-; MIPS32-NEXT:    mfhi $1
-; MIPS32-NEXT:    sll $3, $5, 12
-; MIPS32-NEXT:    addu $3, $3, $5
-; MIPS32-NEXT:    sll $4, $5, 15
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 18
-; MIPS32-NEXT:    subu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 20
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 22
-; MIPS32-NEXT:    addu $3, $4, $3
-; MIPS32-NEXT:    sll $4, $5, 24
-; MIPS32-NEXT:    addu $3, $4, $3
+; MIPS32-NEXT:    mfhi $3
+; MIPS32-NEXT:    mul $1, $5, $1
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $3, $1, $3
+; MIPS32-NEXT:    addu $3, $3, $1
 ;
 ; MIPS64-LABEL: mul22245375_64:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    dsll $1, $4, 12
-; MIPS64-NEXT:    daddu $1, $1, $4
-; MIPS64-NEXT:    dsll $2, $4, 15
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 18
-; MIPS64-NEXT:    dsubu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 20
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 22
-; MIPS64-NEXT:    daddu $1, $2, $1
-; MIPS64-NEXT:    dsll $2, $4, 24
+; MIPS64-NEXT:    lui $1, 339
+; MIPS64-NEXT:    ori $1, $1, 28671
+; MIPS64-NEXT:    dmult $4, $1
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    daddu $2, $2, $1
+; MIPS64-NEXT:    mflo $2
 entry:
   %b = mul i64 %a, 22245375
   ret i64 %b
 }
 
 define i32 @mul25165824_32(i32 %a) {
 ; MIPS32-LABEL: mul25165824_32:
 ; MIPS32:       # %bb.0: # %entry
-; MIPS32-NEXT:    sll $1, $4, 12
-; MIPS32-NEXT:    addu $1, $1, $4
-; MIPS32-NEXT:    sll $2, $4, 15
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 18
-; MIPS32-NEXT:    subu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 20
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 22
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 24
+; MIPS32-NEXT:    lui $1, 339
+; MIPS32-NEXT:    ori $1, $1, 28671
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $2, $2, $1
+; MIPS32-NEXT:    mul $2, $4, $1
 ;
 ; MIPS64-LABEL: mul25165824_32:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    sll $1, $4, 0
-; MIPS64-NEXT:    sll $2, $1, 12
-; MIPS64-NEXT:    addu $2, $2, $1
-; MIPS64-NEXT:    sll $3, $1, 15
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 18
-; MIPS64-NEXT:    subu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 20
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 22
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $1, $1, 24
+; MIPS64-NEXT:    lui $1, 339
+; MIPS64-NEXT:    ori $1, $1, 28671
+; MIPS64-NEXT:    sll $2, $4, 0
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    addu $2, $1, $2
+; MIPS64-NEXT:    mul $2, $2, $1
 entry:
   %b = mul i32 %a, 22245375
   ret i32 %b
 }
 
 define i64 @mul25165824_64(i64 %a) {
 ; MIPS32-LABEL: mul25165824_64:
 ; MIPS32:       # %bb.0: # %entry

 entry:
   %b = mul i64 %a, 25165824
   ret i64 %b
 }
 
 define i32 @mul33554432_32(i32 %a) {
 ; MIPS32-LABEL: mul33554432_32:
 ; MIPS32:       # %bb.0: # %entry
-; MIPS32-NEXT:    sll $1, $4, 12
-; MIPS32-NEXT:    addu $1, $1, $4
-; MIPS32-NEXT:    sll $2, $4, 15
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 18
-; MIPS32-NEXT:    subu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 20
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 22
-; MIPS32-NEXT:    addu $1, $2, $1
-; MIPS32-NEXT:    sll $2, $4, 24
+; MIPS32-NEXT:    lui $1, 339
+; MIPS32-NEXT:    ori $1, $1, 28671
 ; MIPS32-NEXT:    jr $ra
-; MIPS32-NEXT:    addu $2, $2, $1
+; MIPS32-NEXT:    mul $2, $4, $1
 ;
 ; MIPS64-LABEL: mul33554432_32:
 ; MIPS64:       # %bb.0: # %entry
-; MIPS64-NEXT:    sll $1, $4, 0
-; MIPS64-NEXT:    sll $2, $1, 12
-; MIPS64-NEXT:    addu $2, $2, $1
-; MIPS64-NEXT:    sll $3, $1, 15
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 18
-; MIPS64-NEXT:    subu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 20
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $3, $1, 22
-; MIPS64-NEXT:    addu $2, $3, $2
-; MIPS64-NEXT:    sll $1, $1, 24
+; MIPS64-NEXT:    lui $1, 339
+; MIPS64-NEXT:    ori $1, $1, 28671
+; MIPS64-NEXT:    sll $2, $4, 0
 ; MIPS64-NEXT:    jr $ra
-; MIPS64-NEXT:    addu $2, $1, $2
+; MIPS64-NEXT:    mul $2, $2, $1
 entry:
   %b = mul i32 %a, 22245375
   ret i32 %b
 }
 
 define i64 @mul33554432_64(i64 %a) {
 ; MIPS32-LABEL: mul33554432_64:
 ; MIPS32:       # %bb.0: # %entry