[PowerPC] Add ISEL patterns for Mul with Imm.

[Esme]

Summary

If the multiplicand is a constant with following formats:

1. mul with (2^N * int16_imm) -> mulli + rldicr
2. mul with (2^N + 2^M) -> rldicr + add + rldicr
3. mul with (2^N - 2^M) -> rldicr + sub + rldicr

Scenario 2 and 3 are moved to DAGCombiner D88201.

[steven.zhang]

LGTM. Thank you for doing this. I assume that you have run it with bmk to make sure that the functionality is fine.

[jsji]

Why this can NOT be done in DAGCombiner by implementing decomposeMulByConstant target hook?

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4990

Can we add comments about all these scenarios? With simple examples.

5000

exactly two bits set ? What do you mean?

[nemanjai]

In D87384#2279886, @jsji wrote:

Why this can NOT be done in DAGCombiner by implementing decomposeMulByConstant target hook?

Do you have evidence of profitability of (mul (shl %a, N) M) being preferable over (mul %a, C) on other targets? If so, I suppose extending the DAG combine that handles:

mul x, (2^N + 1) --> add (shl x, N), x
mul x, (2^N - 1) --> sub (shl x, N), x

Perhaps it wold be good to gauge interest from other RISC targets.

Scenarios 2 and 3 are quite similar to the existing DAG combine so this would be a straightforward implementation. However I am not sure how likely it is that two shifts and an add/sub are better than a multiply on other targets.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4990

I agree 100%. We should illustrate this with some example bit patterns.

5000

2^N + 2^M has exactly two bits set.

However, I don't think this is profitable as implemented. This implementation does not benefit from an ILP improvement since the instructions are dependent. What we probably want is to convert
(mul %a, (2^N + 2^M)) to (add (shl %a, N), (shl %a, M)) since that improves ILP so the total latency of the sequence is actually reduced. That would also mean that for something like this:

*res1 = a * 0x8800;
*res2 = a * 0x8080;

we only need three total shifts (we should also add that as a test case).
Similar argument applies to the subtract case below.

[Esme]

Thank you for your comments! @jsji @nemanjai

For scenarios 2 and 3, I will modified it as @nemanjai 's hint, and move it to DAGCombiner since it is really similar to existing patterns and then implement our PPCTargetLowering::decomposeMulByConstant. If other targets are interested about this, they can add conditions for this in their decomposeMulByConstant.

But for scenario 1, I am not sure if there are benefits to other targets, since it is inspired by our HW instruction MULLI. So I prefer to keep it in ISEL.

[Esme]

Keep the scenario 1 implemented in ISEL.
For scenario 2 and 3, I will post another patch to implement them in DAGCombiner.

[jsji]

I think we already have similar pattern for scenario 1 as well:

// Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
// use.

Just that (shl X,C) is not constant there..

So I would assume dealing with similar situation controlled by TLI.decomposeMulByConstantwill be easy and also no harm to other targets.
Targets can control and add this scenario in their TLI if they also want this.

BTW: looks like x86 also has imul.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4989

Maybe it would be clearer if we use DAG expression in comments.
eg: (mul X, c2 << c1) -> (rldicr (mulli X, c2 >> c1) c1)

[Esme]

Hi @jsji An infinite loop will occur if we handle the scenario 1 (mul X, c2 << c1) -> (shl (mul X, c2), c1) in DAGCombiner, because there exists a reverse conversion (shl (mul x, c1), c2) -> (mul x, c1 << c2).

[jsji]

In D87384#2289477, @Esme wrote:

Hi @jsji An infinite loop will occur if we handle the scenario 1 (mul X, c2 << c1) -> (mul (shl X, c1), c2) in DAGCombiner, because there exists a reverse conversion (mul (shl X, c1), c2) -> (mul X, c2 << c1).

Hmm.. then OK to keep this in ISEL, but please add comments about DAGcombiner prefer (mul X, c2 << c1). Thanks

[Esme]

Update comments.

[Esme]

Thank you so much for your comments. :D @jsji @nemanjai
I have post another patch D88201 to handle scenario 2 and 3 in DAGCombiner.

[Esme]

Format.

[Esme]

Looking forward to your further comments :) @jsji @nemanjai

[Esme]

ping

[jsji]

LGTM. Thanks for improving this!

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
                           getI32Imm(ME, dl) };
       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
       return;
     }
 
     // Other cases are autogenerated.
     break;
   }
+  case ISD::MUL: {
+    SDValue Op1 = N->getOperand(1);
+    if (Op1.getOpcode() != ISD::Constant || Op1.getValueType() != MVT::i64)
+      break;
+
+    int64_t Imm = cast<ConstantSDNode>(Op1)->getZExtValue();
+    unsigned Shift = countTrailingZeros<uint64_t>(Imm);
+    if (isInt<16>(Imm) || !Shift)
+      break;
+
+    // If the shifted value fits 16 bits, we can transform the multiplication to
+    // "mulli + rldicr".
+    int64_t ImmSh = Imm >> Shift;
+    if (isInt<16>(ImmSh)) {
+      uint64_t SextImm = SignExtend64(ImmSh & 0xFFFF, 16);
+      SDValue SDImm = CurDAG->getTargetConstant(SextImm, dl, MVT::i64);
+      SDNode *MulNode = CurDAG->getMachineNode(PPC::MULLI8, dl, MVT::i64,
+                                               N->getOperand(0), SDImm);
+      CurDAG->SelectNodeTo(N, PPC::RLDICR, MVT::i64, SDValue(MulNode, 0),
+                           getI32Imm(Shift, dl), getI32Imm(63 - Shift, dl));
+      return;
+    }
+    break;
+  }
   // FIXME: Remove this once the ANDI glue bug is fixed:
   case PPCISD::ANDI_rec_1_EQ_BIT:
   case PPCISD::ANDI_rec_1_GT_BIT: {
     if (!ANDIGlueBug)
       break;
 
     EVT InVT = N->getOperand(0).getValueType();
     assert((InVT == MVT::i64 || InVT == MVT::i32) &&

llvm/test/CodeGen/PowerPC/mulli.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -verify-machineinstrs -mcpu=pwr9 -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
 
 define i64 @test1(i64 %x) {
 ; CHECK-LABEL: test1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    li 4, 625
-; CHECK-NEXT:    sldi 4, 4, 36
-; CHECK-NEXT:    mulld 3, 3, 4
+; CHECK-NEXT:    mulli 3, 3, 625
+; CHECK-NEXT:    sldi 3, 3, 36
 ; CHECK-NEXT:    blr
   %y = mul i64 %x, 42949672960000
   ret i64 %y
 }
 
 define i64 @test2(i64 %x) {
 ; CHECK-LABEL: test2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    li 4, -625
-; CHECK-NEXT:    sldi 4, 4, 36
-; CHECK-NEXT:    mulld 3, 3, 4
+; CHECK-NEXT:    mulli 3, 3, -625
+; CHECK-NEXT:    sldi 3, 3, 36
 ; CHECK-NEXT:    blr
   %y = mul i64 %x, -42949672960000
   ret i64 %y
 }
 
 define i64 @test3(i64 %x) {
 ; CHECK-LABEL: test3:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    lis 4, 74
-; CHECK-NEXT:    ori 4, 4, 16384
-; CHECK-NEXT:    mulld 3, 3, 4
+; CHECK-NEXT:    mulli 3, 3, 297
+; CHECK-NEXT:    sldi 3, 3, 14
 ; CHECK-NEXT:    blr
   %y = mul i64 %x, 4866048
   ret i64 %y
 }
 
 define i64 @test4(i64 %x) {
 ; CHECK-LABEL: test4:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    lis 4, -75
-; CHECK-NEXT:    ori 4, 4, 49152
-; CHECK-NEXT:    mulld 3, 3, 4
+; CHECK-NEXT:    mulli 3, 3, -297
+; CHECK-NEXT:    sldi 3, 3, 14
 ; CHECK-NEXT:    blr
   %y = mul i64 %x, -4866048
   ret i64 %y
 }
 
 define i64 @test5(i64 %x) {
 ; CHECK-LABEL: test5:
 ; CHECK:       # %bb.0:
; CHECK-NEXT:    blr
   %y = mul i64 %x, -17179860992
   ret i64 %y
 }
 
 define i64 @test9(i64 %x) {
 ; CHECK-LABEL: test9:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    lis 4, 16
-; CHECK-NEXT:    li 5, 8193
 ; CHECK-NEXT:    ori 4, 4, 1
-; CHECK-NEXT:    sldi 5, 5, 19
 ; CHECK-NEXT:    sldi 4, 4, 12
 ; CHECK-NEXT:    mulld 4, 3, 4
-; CHECK-NEXT:    mulld 3, 3, 5
+; CHECK-NEXT:    mulli 3, 3, 8193
+; CHECK-NEXT:    sldi 3, 3, 19
 ; CHECK-NEXT:    sub 3, 4, 3
 ; CHECK-NEXT:    blr
   %y = mul i64 %x, 4294971392
   %z = mul i64 %x, 4295491584
   %res = sub i64 %y, %z
   ret i64 %res
 }