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

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.

Differential Revision: https://reviews.llvm.org/D62166

llvm-svn: 361606

1 files changed, 56 insertions, 255 deletions

diff --git a/llvm/test/CodeGen/Mips/const-mult.ll b/llvm/test/CodeGen/Mips/const-mult.ll
index cbb3c91299f..dd90971dcee 100644
--- a/llvm/test/CodeGen/Mips/const-mult.ll
+++ b/llvm/test/CodeGen/Mips/const-mult.ll
@@ -212,44 +212,18 @@ entry:
 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
 }
@@ -261,45 +235,18 @@ define i64 @mul42949673_64(i64 %a) {
 ; 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
@@ -308,54 +255,18 @@ entry:
 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
@@ -368,55 +279,18 @@ define i64 @mul22224078_64(i64 %a) {
 ; 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
@@ -425,36 +299,18 @@ entry:
 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
@@ -467,37 +323,18 @@ define i64 @mul22245375_64(i64 %a) {
 ; 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
@@ -506,36 +343,18 @@ entry:
 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
@@ -572,36 +391,18 @@ entry:
 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