[RISCV] optimize addition with a pair of (addi imm)

[benshi001]

Summary

For an addition with an immediate in specific ranges, a pair of
addi-addi can be generated instead of the ordinary lui-addi-add serial.

[benshi001]

for (add i32 %a, 4094), it can be simplfied to
addi a0, a0, 2047
addi a0, a0, 2047.

The original assembly is
lui a1, 1
addi a1, a1, -2
add a0, a0, a1

However, this optimization can only be performed if the value generated by lui-addi has no other use.

[benshi001]

My information,

name = Ben Shi
email = [e-mail]

[luismarques]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

85

Given that you can have an ADDI of -2048, that should be -4096, not -4095. (Please update the comment, the code and the test results accordingly).

87–88

This is a matter of style so it's not very important, but I would lean towards implementing this check with a comparison logic that matches the comment about the required range, as that would be make it easier to check at a glance.

92–93

Nitpick: make it the other way around, so that the second addi is the "smaller" one. That generated code seems more intuitive to me that way :-)

llvm/test/CodeGen/RISCV/add-imm.ll

10–26

When you have i32 and the i64 tests they should both have riscv32 and riscv64 test CHECKs. You can have operations on i64s in riscv32, they just doesn't correspond to a single native instruction. But in this case I don't see much advantage in having test variants for both types, as this optimization should be orthogonal to that. I suggest keeping one i32+i64 test (to show that it works with both types), and trimming the remaining tests down to just the i32 variant.

[benshi001]

All done. Thanks for your suggestion. ^_^

[benshi001]

Why "Harbormaster failed remote builds in B61745: Diff 273379!" ???

The "make check-all" fully passed with the new version of patch.

[benshi001]

Could you please help me review it? I have not got any suggestion for one week :)

[benshi001]

ping ...

[luismarques]

The patch seems correct to me. I'm not quite sure this is the best place to do the this transformation (guidance on that from other people would be welcome), but I don't have a better solution to propose right now. I'm going to approve this patch, but I suggest you wait a couple more days to give other people an opportunity to comment on that issue.
Regarding the tests, as a nitpicking issue, I would only suggest giving the test functions slightly more semantic names (maybe something like negative_bound_reject, etc.).

[benshi001]

Thanks. I have improved the function names according to your suggestion!

[MaskRay]

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

80

The two comments can be combined and placed under case ISD::ADD:

Optimize (add r, imm) to (addi (addi r, imm0) imm1) if applicable.

83

if (!ConstOp->hasOneUse()) is not tested.

92

Add const if applicable.

[MaskRay]

Looks great!

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

void RISCVDAGToDAGISel::Select(SDNode *Node) {
   // Instruction Selection not handled by the auto-generated tablegen selection
   // should be handled here.
   unsigned Opcode = Node->getOpcode();
   MVT XLenVT = Subtarget->getXLenVT();
   SDLoc DL(Node);
   EVT VT = Node->getValueType(0);
 
   switch (Opcode) {
+  // Optimize the node (add r, imm) to (addi (addi r, imm0) imm1)
+  // if possible.
+  case ISD::ADD: {
+    // The second operand must be an immediate.
+    if (auto *ConstOp = dyn_cast<ConstantSDNode>(Node->getOperand(1))) {
+      // The immediate operand must not have other use.
+      if (!ConstOp->hasOneUse())
+        break;
+      // The immediate must be in range [-4095,-2049] or [2048,4094].
+      int64_t ImmVal = ConstOp->getSExtValue();
+      if (ImmVal < -4095 || (-2049 < ImmVal && ImmVal < 2048) || 4094 < ImmVal)
+        break;
+      // Break the immediate to Imm0+Imm1.
+      SDLoc DL(Node);
+      EVT VT = Node->getValueType(0);
+      SDValue ImmOp0 = CurDAG->getTargetConstant(ImmVal / 2, DL, VT);
+      SDValue ImmOp1 = CurDAG->getTargetConstant(ImmVal - ImmVal / 2, DL, VT);
+      auto *NodeAddi0 = CurDAG->getMachineNode(RISCV::ADDI, DL, VT,
+                                               Node->getOperand(0), ImmOp0);
+      auto *NodeAddi1 = CurDAG->getMachineNode(RISCV::ADDI, DL, VT,
+                                               SDValue(NodeAddi0, 0), ImmOp1);
+      ReplaceNode(Node, NodeAddi1);
+      return;
+    }
+    break;
+  }
   case ISD::Constant: {
     auto ConstNode = cast<ConstantSDNode>(Node);
     if (VT == XLenVT && ConstNode->isNullValue()) {
       SDValue New = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), SDLoc(Node),
                                            RISCV::X0, XLenVT);
       ReplaceNode(Node, New.getNode());
       return;
     }

llvm/test/CodeGen/RISCV/add-imm.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
+; RUN:   | FileCheck -check-prefix=RV32I %s
+; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s \
+; RUN:   | FileCheck -check-prefix=RV64I %s
+
+; These test how the immediate in an addition is materialized.
+
+define i32 @add_0(i32 %a) nounwind {
+; RV32I-LABEL: add_0:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 2047
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_0:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, 2047
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, 2047
+  ret i32 %1
+}
+
+define i32 @add_1(i32 %a) nounwind {
+; RV32I-LABEL: add_1:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 1024
+; RV32I-NEXT:    addi a0, a0, 1024
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_1:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, 1024
+; RV64I-NEXT:    addi a0, a0, 1024
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, 2048
+  ret i32 %1
+}
+
+define i32 @add_2(i32 %a) nounwind {
+; RV32I-LABEL: add_2:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 2047
+; RV32I-NEXT:    addi a0, a0, 2047
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_2:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, 2047
+; RV64I-NEXT:    addi a0, a0, 2047
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, 4094
+  ret i32 %1
+}
+
+define i32 @add_3(i32 %a) nounwind {
+; RV32I-LABEL: add_3:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    lui a1, 1
+; RV32I-NEXT:    addi a1, a1, -1
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_3:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    lui a1, 1
+; RV64I-NEXT:    addiw a1, a1, -1
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, 4095
+  ret i32 %1
+}
+
+define i32 @add_4(i32 %a) nounwind {
+; RV32I-LABEL: add_4:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -2048
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_4:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, -2048
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, -2048
+  ret i32 %1
+}
+
+define i32 @add_5(i32 %a) nounwind {
+; RV32I-LABEL: add_5:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -1024
+; RV32I-NEXT:    addi a0, a0, -1025
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_5:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, -1024
+; RV64I-NEXT:    addi a0, a0, -1025
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, -2049
+  ret i32 %1
+}
+
+define i32 @add_6(i32 %a) nounwind {
+; RV32I-LABEL: add_6:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -2047
+; RV32I-NEXT:    addi a0, a0, -2048
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_6:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, -2047
+; RV64I-NEXT:    addi a0, a0, -2048
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, -4095
+  ret i32 %1
+}
+
+define i32 @add_7(i32 %a) nounwind {
+; RV32I-LABEL: add_7:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    lui a1, 1048575
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: add_7:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    lui a1, 1048575
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %1 = add i32 %a, -4096
+  ret i32 %1
+}