[DAGCombiner] Add target hook function to decide folding (mul (add x, c1), c2)

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

537

What about all the optimizations we have for mul by constant using SHXADD? Won't this miss out on those?

[benshi001]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

537

I do not think it will affect the optimization with SHxADD.

For the ones such as
(mul 11/13/25/41/73/37/21), (mul (3/5/9)*power_of_2), (mul power_of_2 + (2/4/8)), those are pure mul without add involved, so they won't be affected.

For the rules such as
(x + y * 4) -> (SH2ADD y, x)
(x + y * 20) -> (SH2ADD (SH2ADD x, x), y)
.......

My patch still generate better code.

c1 + x * 72 (c1 is a non-simm12 constant)

before current patch

lui Ry, higher-bits of c1
addi Ry, Ry, lower-12-bits of c1
sh3add Rz, x, x
sh3add Rz, Rz, Ry

after my patch

addi Ry, x, c1/72
sh3add Ry, Ry, Ry
sll Ry, Ry, 3

I will add those cases to the test file.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

537

Isn’t it possible for the MUL you create here to have 11/13/25/41/73/37/21 as a constant that should use SHXADD?

[benshi001]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

537

Yes, it is possible. And for mul with 11/13/25/41/73/37/21 which use shxadd, my change still generates better asm. I will add in the tests.

[benshi001]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

537

Sorry, your concern is right. I can not handle mul with 11/13/25/41/73/37/21.

[benshi001]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

537

I have skip those constants in the zba extension. And will figure out a better way for them in the future.

Thanks for your help.

[benshi001]

Is there any better way to implement this optimization other than ISelDagToDag?

1. It seems hard to calculate c1/c0 by writing TD mapping rules.

2. I also tried DAG transform in RISCVTargetLowering::ReplaceNodeResults, it is also not easy, since it involves more code about legalization.

[craig.topper]

In D107711#2934246, @benshi001 wrote:

Is there any better way to implement this optimization other than ISelDagToDag?

1. It seems hard to calculate c1/c0 by writing TD mapping rules.

2. I also tried DAG transform in RISCVTargetLowering::ReplaceNodeResults, it is also not easy, since it involves more code about legalization.

It should probably be a DAG combine and the transform that's turning (mul (add X, C1), C2) into (add (mul X, C2), C1 * C2) should ask the target if it is profitable, or at least call isLegalAddImmediate for C1*C2. @spatel or @lebedev.ri, what do you think?

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

18

#include <set>. and it should be after all llvm headers

533

Use std::array so you can use begin()/end() on the std::set.

Though you could sort the array and use std::binary_search and avoid the set completely.

[lebedev.ri]

In D107711#2934794, @craig.topper wrote:

In D107711#2934246, @benshi001 wrote:

Is there any better way to implement this optimization other than ISelDagToDag?

1. It seems hard to calculate c1/c0 by writing TD mapping rules.

2. I also tried DAG transform in RISCVTargetLowering::ReplaceNodeResults, it is also not easy, since it involves more code about legalization.

It should probably be a DAG combine and the transform that's turning (mul (add X, C1), C2) into (add (mul X, C2), C1 * C2) should ask the target if it is profitable, or at least call isLegalAddImmediate for C1*C2. @spatel or @lebedev.ri, what do you think?

Putting it into DAGCombine SGTM

[benshi001]

In D107711#2934794, @craig.topper wrote:

In D107711#2934246, @benshi001 wrote:

Is there any better way to implement this optimization other than ISelDagToDag?

1. It seems hard to calculate c1/c0 by writing TD mapping rules.

2. I also tried DAG transform in RISCVTargetLowering::ReplaceNodeResults, it is also not easy, since it involves more code about legalization.

It should probably be a DAG combine and the transform that's turning (mul (add X, C1), C2) into (add (mul X, C2), C1 * C2) should ask the target if it is profitable, or at least call isLegalAddImmediate for C1*C2. @spatel or @lebedev.ri, what do you think?

Thanks for your help! I have added a new target hook function isMulAddWithConstNotProfitable to let the DAGCombiner consult the target before combining (mul (add X, C1), C2).

This solution seems more clear. And it really improve most riscv's assembly code, except two of them, which I have made inline comments.

[benshi001]

llvm/test/CodeGen/RISCV/addimm-mulimm.ll

209

This should not be a regression, since 8 bytes are saved, and the mulw should cost no more than 3 cycles since 73 is a small integer, so does for 19/25/41/73/11/13...

209

This can be further optimized to

(SLLIW (SH1ADD a0, a0, a0), 6).

I will make another patch for this optimization.

[benshi001]

llvm/test/CodeGen/RISCV/addimm-mulimm.ll

209

The best form should be

; RV64IM-NEXT: addi a0, a0, 1000
; RV64IM-NEXT: sh1add a0, a0, a0
; RV64IM-NEXT: slliw a0, a0, 6

It can be done via new rules in RISCVInstrInfoB.td

[benshi001]

llvm/test/CodeGen/RISCV/addimm-mulimm.ll

209

I have submitted another patch to optimize that case.

https://reviews.llvm.org/D107820

[benshi001]

In this solution, this is no need to concern the impact to optimization with SHXADD.

[jrtc27]

llvm/test/CodeGen/RISCV/addimm-mulimm.ll

207–208

Why are RV32IM check lines, in a file whose name and path don't say bitmanip, mentioning bitmanip instructions?

[craig.topper]

llvm/include/llvm/CodeGen/TargetLowering.h

2089 ↗

(On Diff #365474)

Drop the "Not" and return true. Remove the ! from the caller.

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9071 ↗

(On Diff #365474)

Use cast instead of dyn_cast and drop this assert. cast asserts internally.

[benshi001]

llvm/test/CodeGen/RISCV/addimm-mulimm.ll

209

This regression will be fixed by D107708.

[lebedev.ri]

Comments need updating

[benshi001]

In D107711#2939527, @lebedev.ri wrote:

Comments need updating

I have updated the inline comments. Thank you.

[lebedev.ri]

In D107711#2939527, @lebedev.ri wrote:

Comments need updating

llvm/include/llvm/CodeGen/TargetLowering.h

2086 ↗

(On Diff #365767)

llvm/lib/Target/RISCV/RISCVISelLowering.h

467 ↗

(On Diff #365767)

[benshi001]

llvm/include/llvm/CodeGen/TargetLowering.h

2086 ↗

(On Diff #365767)

I think my origin default true is right, the default return value should not be false.

Since my hook is called as

if (AddNode.getNode()->hasOneUse() &&
    TLI.isMulAddWithConstProfitable(AddNode, ConstNode))
  return true;

So it should return default true for undetermined cases.

[benshi001]

llvm/include/llvm/CodeGen/TargetLowering.h

2086 ↗

(On Diff #365767)

Actually my previous version is isMulAddWithConstNotProfitable, which return default false, and return true for clear regression on specific targets.

Craig suggested me to remove the Not, and inverse the condition when calling.

The core issue is, the original DAGCombiner will do the folding if the AddNode has only one use, which will harm performance in some situation. And the solution is adding another check (along with the hasOneUse) to let the target prevent the transform if the target does think there is regresssion.

But if the target is also not sure, what default value should be ? And the hook name should have Not or should not have a Not ?

[jrtc27]

llvm/include/llvm/CodeGen/TargetLowering.h

2086 ↗

(On Diff #365767)

The default should be whatever makes SelectionDAG behave the same as it currently does unless the changes in behaviour turn out to be useful for the majority of targets.

TLI functions should be positive not negative; there are no hooks that have Not in them (other than when they refer to a not instruction).

I'm not sure what the issue is though? Whether you have a NotProfitable function that defaults to false or a Profitable function that defaults to true makes no semantic difference other than when the caller needs to put a ! in front of it, it's purely a stylistic issue.

[benshi001]

llvm/include/llvm/CodeGen/TargetLowering.h

2086 ↗

(On Diff #365767)

I will keep current form without Not, and still return default true to "make SelectionDAG behave the same as it currently does".

And I have improved my comments more clear as

/// Return true if it may be profitable to fold
/// (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2), and return false
/// to prevent the folding for definite regression.
/// The target should check the cost of materializing c1, c2 and c1*c2 into
/// registers. If it is not sure about some cases, a default true
/// can be returned to let the DAGCombiner decide.

[lebedev.ri]

SGTM

[benshi001]

ping ... Can this patch be approved ? It seems there is no objection on adding a hook isMulAddWithConstProfitable

[lebedev.ri]

LGTM unless other have further comments.
Thanks.

[benshi001]

In D107711#2951596, @lebedev.ri wrote:

LGTM unless other have further comments.
Thanks.

I would like to land on Sunday evening, unless there will be other objection.

[jrtc27]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

16857 ↗

(On Diff #365898)

"finds no regression" doesn't make sense to me. A regression is a bug, but if the target says it's profitable then there is no regression; a regression would be if a target said it was not profitable but it in fact was, and so the emitted code got worse. So when a target returns false, it's not that it finds a regression, because nothing has happened yet.

This also feeds into a related point. When comments in DAGCombiner talk about regressions, they generally mean "this transformation should make sense on most targets, but many of them don't enable it currently because they have patterns or custom lowering that would need to be adapted to handle it otherwise they won't match important cases any more" (with the "won't match important cases" being the regression), generally marked as TODO (all but one, with the odd-one-out still saying that something should probably be improved). This is not that case, this is just asking the target whether the transformation is profitable, simply as a "does your instruction set benefit from this transformation?".

llvm/lib/Target/RISCV/RISCVISelLowering.h

464 ↗

(On Diff #365898)

What's the point of duplicating this doxygen comment? It's just going to get outdated, and anyone who wants to know what it does (which is pretty obvious from the name) can just look at TargetLowering.h. If we copied the documentation to every override the tree would be a mess.

[benshi001]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

16857 ↗

(On Diff #365898)

Thanks. I have made the comments more clear.

llvm/lib/Target/RISCV/RISCVISelLowering.h

464 ↗

(On Diff #365898)

Thanks. I have removed the redundant comments.

[jrtc27]

llvm/include/llvm/CodeGen/TargetLowering.h

2083 ↗

(On Diff #367200)

The comment's still not great, putting grammatical issues aside. A lot of it is just explaining the basics of TLI hooks, but also is overly prescriptive with what backends should do to evaluate it (and I also don't like "to avoid definite worse code generated", often TLI hooks end up being best-effort heuristics, unable to give a definitive answer, because that might require extremely expensive whole-function checks that depend on knowing what other transformations are going to be made).

I'd just go with something like (borrowing style from surrounding examples):

Return true if it may be profitable to transform
(mul (add x, c1), c2) -> (add (mul x, c2), c1*c2).
This may not be true if c1 and c2 can be represented as immediates but c1*c2 cannot, for example.

[benshi001]

llvm/include/llvm/CodeGen/TargetLowering.h

2083 ↗

(On Diff #367200)

Thanks, I have updated the comments according to your suggested expression.

One more issue, English is not my mother language and your are appreciated to help me fix any "grammatical issues" you mentioned. ^_^

[luismarques]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9088 ↗

(On Diff #367231)

Nit: IMO, it would be more intuitive to compare the other way around, swapping the operands and changing the condition to >=.

[benshi001]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9088 ↗

(On Diff #367231)

I can swap the operands, but why changing the condition to >=, should using > be better? Since I think this should consider i64 on rv64 and i32 on rv32.

[jrtc27]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9088 ↗

(On Diff #367231)

Yes, > is correct, and I agree with Luis that this is the more natural way round to express it.

[luismarques]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9088 ↗

(On Diff #367231)

Sorry, ignore the part about the equals :) I mixed some thoughts when writing that.

[benshi001]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9088 ↗

(On Diff #367231)

Thanks. The order has been changed.

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "RISCVISelDAGToDAG.h"
 #include "MCTargetDesc/RISCVMCTargetDesc.h"
 #include "MCTargetDesc/RISCVMatInt.h"
 #include "RISCVISelLowering.h"
 #include "RISCVMachineFunctionInfo.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/IR/IntrinsicsRISCV.h"
 #include "llvm/Support/Alignment.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
if (N1C) {
           ReplaceNode(Node, SRLI);
           return;
         }
       }
     }
 
     break;
   }
+  case ISD::ADD: {
+    // Optimize (add (mul x, c0), c1) to (mul (add x, c1/c0), c0),
+    // if c1/c0 is simm12, while c1 is not, and c1%c0==0.
+    MVT VT = Node->getSimpleValueType(0);
+    // The type must be a scalar type.
+    if (VT.isVector())
+      break;
+    // The first operand node must be a MUL and has no other use.
+    SDValue N0 = Node->getOperand(0);
+    if (!N0->hasOneUse() || N0->getOpcode() != ISD::MUL)
+      break;
+    // Check c0 and c1.
+    auto *NC0 = dyn_cast<ConstantSDNode>(N0->getOperand(1));
+    if (!NC0)
+      break;
+    auto *NC1 = dyn_cast<ConstantSDNode>(Node->getOperand(1));
+    if (!NC1)
+      break;
+    int64_t C0 = NC0->getSExtValue();
+    int64_t C1 = NC1->getSExtValue();
+    // Check if c0 and c1 match the conditions mentioned above.
+    if (APInt(64, C1).isSignedIntN(12) || (C1 % C0) != 0 ||
+        !APInt(64, C1 / C0).isSignedIntN(12))
+      break;
+    // Build new nodes (mul (add x, c1/c0), c0).
+    SDLoc DL(Node);
+    SDNode *NA =
+        CurDAG->getMachineNode(RISCV::ADDI, DL, VT, N0->getOperand(0),
+                               CurDAG->getTargetConstant(C1 / C0, DL, VT));
+    SDNode *NM =
+        CurDAG->getMachineNode(RISCV::MUL, DL, VT, SDValue(NA, 0),
+                               N0->getOperand(1));
+    ReplaceNode(Node, NM);
+    return;
+  }
   case ISD::AND: {
     auto *N1C = dyn_cast<ConstantSDNode>(Node->getOperand(1));
     if (!N1C)
       break;
 
     SDValue N0 = Node->getOperand(0);
 
     bool LeftShift = N0.getOpcode() == ISD::SHL;

llvm/test/CodeGen/RISCV/addimm-mulimm.ll

; RV64IM-NEXT:    ret
   %tmp0 = add i64 %x, 8953
   %tmp1 = mul i64 %tmp0, 13
   ret i64 %tmp1
 }
 
 define i32 @add_mul_trans_accept_a0(i32 %x) {
 ; RV32IM-LABEL: add_mul_trans_accept_a0:
 ; RV32IM:       # %bb.0:
+; RV32IM-NEXT:    addi a0, a0, 1971
 ; RV32IM-NEXT:    addi a1, zero, 19
 ; RV32IM-NEXT:    mul a0, a0, a1
-; RV32IM-NEXT:    lui a1, 9
-; RV32IM-NEXT:    addi a1, a1, 585
-; RV32IM-NEXT:    add a0, a0, a1
 ; RV32IM-NEXT:    ret
 ;
 ; RV64IM-LABEL: add_mul_trans_accept_a0:
 ; RV64IM:       # %bb.0:
+; RV64IM-NEXT:    addi a0, a0, 1971
 ; RV64IM-NEXT:    addi a1, zero, 19
 ; RV64IM-NEXT:    mul a0, a0, a1
-; RV64IM-NEXT:    lui a1, 9
-; RV64IM-NEXT:    addiw a1, a1, 585
-; RV64IM-NEXT:    add a0, a0, a1
 ; RV64IM-NEXT:    ret
   %tmp0 = add i32 %x, 1971
   %tmp1 = mul i32 %tmp0, 19
   ret i32 %tmp1
 }
 
 define signext i32 @add_mul_trans_accept_a1(i32 signext %x) {
 ; RV32IM-LABEL: add_mul_trans_accept_a1:
 ; RV32IM:       # %bb.0:
+; RV32IM-NEXT:    addi a0, a0, 1971
 ; RV32IM-NEXT:    addi a1, zero, 19
 ; RV32IM-NEXT:    mul a0, a0, a1
-; RV32IM-NEXT:    lui a1, 9
-; RV32IM-NEXT:    addi a1, a1, 585
-; RV32IM-NEXT:    add a0, a0, a1
 ; RV32IM-NEXT:    ret
 ;
 ; RV64IM-LABEL: add_mul_trans_accept_a1:
 ; RV64IM:       # %bb.0:
 ; RV64IM-NEXT:    addi a1, zero, 19
 ; RV64IM-NEXT:    mul a0, a0, a1
 ; RV64IM-NEXT:    lui a1, 9
 ; RV64IM-NEXT:    addiw a1, a1, 585

 ; RV32IM-NEXT:    addi a0, a0, 585
 ; RV32IM-NEXT:    add a0, a2, a0
 ; RV32IM-NEXT:    sltu a2, a0, a2
 ; RV32IM-NEXT:    add a1, a1, a2
 ; RV32IM-NEXT:    ret
 ;
 ; RV64IM-LABEL: add_mul_trans_accept_a2:
 ; RV64IM:       # %bb.0:
+; RV64IM-NEXT:    addi a0, a0, 1971
 ; RV64IM-NEXT:    addi a1, zero, 19
 ; RV64IM-NEXT:    mul a0, a0, a1
-; RV64IM-NEXT:    lui a1, 9
-; RV64IM-NEXT:    addiw a1, a1, 585
-; RV64IM-NEXT:    add a0, a0, a1
 ; RV64IM-NEXT:    ret
   %tmp0 = add i64 %x, 1971
   %tmp1 = mul i64 %tmp0, 19
   ret i64 %tmp1
 }