[RISCV] Optimize (add (shl x, c0), (shl y, c1))

[benshi001]

Summary

Optimize (add (shl x, c0), (shl y, c1)) to

(SLLI (SHxADD y, x), c0) if applicable.

[benshi001]

The reason I write both AddShlShl_1A and def AddShlShl_1B, is that add is not commutative in PatFrag.

[jrtc27]

llvm/lib/Target/RISCV/RISCVInstrInfoB.td

215 ↗

(On Diff #372366)

This should just be a templated class that takes the +/- 1/2/3 as an argument rather than copy-pasting the same thing 6 times. Though the number of patterns and special cases for all the bitmanip stuff seems to be getting rather crazy; is there an end in sight?

[craig.topper]

In D109729#2998731, @benshi001 wrote:

The reason I write both AddShlShl_1A and def AddShlShl_1B, is that add is not commutative in PatFrag.

You should write that as a comment in the code.

[craig.topper]

In D109729#2998734, @craig.topper wrote:

In D109729#2998731, @benshi001 wrote:

The reason I write both AddShlShl_1A and def AddShlShl_1B, is that add is not commutative in PatFrag.

You should write that as a comment in the code.

Actually it's worse than that. Tablegen does know the pattern is commutable and will call you predicate function twice. But one of the calls will be wrong. I hope it is guaranteed that the correct check always happens first. There is a feature to make this work. It involves setting "let PredicateCodeUsesOperands = 1;" on the PatFrag. Only AMDGPU uses it. You should look up the patch that added it.

[benshi001]

Using let PredicateCodeUsesOperands = 1 makes code more boring and complex. So I have resorted to using DAG2GAG selection which looks more clear.

[craig.topper]

In D109729#2998980, @benshi001 wrote:

Using let PredicateCodeUsesOperands = 1 makes code more boring and complex. So I have resorted to using DAG2GAG selection which looks more clear.

I'm not sure what you mean by boring here. Can you share one of the PatFrags using that feature?

[benshi001]

In D109729#2998986, @craig.topper wrote:

In D109729#2998980, @benshi001 wrote:

Using let PredicateCodeUsesOperands = 1 makes code more boring and complex. So I have resorted to using DAG2GAG selection which looks more clear.

I'm not sure what you mean by boring here. Can you share one of the PatFrags using that feature?

I mean the similar code is copied 6 times which is boring, and it becomes more complex than I expected. and I think using DAG2DAG is more clear.

[benshi001]

In D109729#2998986, @craig.topper wrote:

In D109729#2998980, @benshi001 wrote:

Using let PredicateCodeUsesOperands = 1 makes code more boring and complex. So I have resorted to using DAG2GAG selection which looks more clear.

I'm not sure what you mean by boring here. Can you share one of the PatFrags using that feature?

Using let PredicateCodeUsesOperands = 1 also needs implementing let GISelPredicateCode = [{...}], otherwise the TableGen will failed.

such as

def patfrags_test_pat : PatFrags<
  (ops node:$x, node:$y, node:$z),
  [ (xor (add node:$x, node:$y), node:$z),
    (xor (sub node:$x, node:$y), node:$z)
  ], [{ return foo(); }]> {
  let GISelPredicateCode = [{
    return doesComplexCheck(MI);
  }];

  let PredicateCodeUsesOperands = 1;
}

That make the code becomes more redundant and complex.

[craig.topper]

In D109729#2998987, @benshi001 wrote:

In D109729#2998986, @craig.topper wrote:

In D109729#2998980, @benshi001 wrote:

Using let PredicateCodeUsesOperands = 1 makes code more boring and complex. So I have resorted to using DAG2GAG selection which looks more clear.

I'm not sure what you mean by boring here. Can you share one of the PatFrags using that feature?

I mean the similar code is copied 6 times which is boring, and it becomes more complex than I expected. and I think using DAG2DAG is more clear.

The PredicateCodeUsesOperands feature should only require 3 PatFrags that look like this, but I can't get it to compile.

let PredicateCodeUsesOperands = 1 in
def AddShlShl_1A : PatFrag<(ops node:$A, node:$B, node:$C, node:$D),
                           (add (shl node:$A, node:$B),
                                (shl node:$C, node:$D)), [{
  SDValue N0 = Operands[0], N1 = Operands[1];
  if (!N0.hasOneUse() || !N1.hasOneUse())
    return false;
  auto *N0C = cast<ConstantSDNode>(N0.getOperand(1));
  auto *N1C = cast<ConstantSDNode>(N1.getOperand(1));
  uint64_t C0 = N0C->getZExtValue(), C1 = N1C->getZExtValue();
  return C0 == C1 + 1;                                                                                                                                                       
}]>;

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

539

vevtor->vector

540

The VT.getSizeInBits() > Subtarget->getXLen() should never fail. If the VT is scalar it must be XLenVT.

584

There's already a DL in the top of this function.

[craig.topper]

I'm inclined to prefer D108916 over this.

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

if (N1C) {
           ReplaceNode(Node, SRLI);
           return;
         }
       }
     }
 
     break;
   }
+
+  // Optimize (add (shl x, c0), (shl y, c1)) ->
+  //          (SLLI (SH*ADD y, x), c0), if c1-c0 equals to [1|2|3].
+  case ISD::ADD: {
+    // Perform this optimization only in the zba extension.
+    if (!Subtarget->hasStdExtZba())
+      break;
+
+    // Skip for vector types.
+    if (VT.isVector())
+      break;
+
+    // The two operand nodes must be SHL and have no other use.
+    SDValue N0 = Node->getOperand(0);
+    SDValue N1 = Node->getOperand(1);
+    if (N0.getOpcode() != ISD::SHL || N1.getOpcode() != ISD::SHL ||
+        !N0.hasOneUse() || !N1.hasOneUse())
+      break;
+
+    // Check c0 and c1.
+    auto *NC0 = dyn_cast<ConstantSDNode>(N0->getOperand(1));
+    auto *NC1 = dyn_cast<ConstantSDNode>(N1->getOperand(1));
+    if (!NC0 || !NC1)
+      break;
+    int64_t C0 = NC0->getSExtValue();
+    int64_t C1 = NC1->getSExtValue();
+    if (C0 <= 0 || C1 <= 0 || C0 >= Subtarget->getXLen() ||
+        C1 >= Subtarget->getXLen())
+      break;
+    int64_t Bits = std::min(C0, C1);
+    int64_t Diff = std::max(C0, C1) - Bits;
+
+    // Select SH1ADD/SH2ADD/SH3ADD or skip.
+    unsigned Opc;
+    if (Diff == 1)
+      Opc = RISCV::SH1ADD;
+    else if (Diff == 2)
+      Opc = RISCV::SH2ADD;
+    else if (Diff == 3)
+      Opc = RISCV::SH3ADD;
+    else
+      break;
+
+    // Build machine nodes and replace SDNodes.
+    SDValue NS = (C0 < C1) ? N0->getOperand(0) : N1->getOperand(0);
+    SDValue NL = (C0 > C1) ? N0->getOperand(0) : N1->getOperand(0);
+    SDNode *NAD = CurDAG->getMachineNode(Opc, DL, VT, NL, NS);
+    SDNode *NSH =
+        CurDAG->getMachineNode(RISCV::SLLI, DL, VT, SDValue(NAD, 0),
+                               CurDAG->getTargetConstant(Bits, DL, VT));
+    ReplaceNode(Node, NSH);
+    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/rv32zba.ll

 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    slli a0, a0, 5
 ; RV32I-NEXT:    slli a1, a1, 6
 ; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32B-LABEL: addshl_5_6:
 ; RV32B:       # %bb.0:
+; RV32B-NEXT:    sh1add a0, a1, a0
 ; RV32B-NEXT:    slli a0, a0, 5
-; RV32B-NEXT:    slli a1, a1, 6
-; RV32B-NEXT:    add a0, a0, a1
 ; RV32B-NEXT:    ret
 ;
 ; RV32ZBA-LABEL: addshl_5_6:
 ; RV32ZBA:       # %bb.0:
+; RV32ZBA-NEXT:    sh1add a0, a1, a0
 ; RV32ZBA-NEXT:    slli a0, a0, 5
-; RV32ZBA-NEXT:    slli a1, a1, 6
-; RV32ZBA-NEXT:    add a0, a0, a1
 ; RV32ZBA-NEXT:    ret
   %c = shl i32 %a, 5
   %d = shl i32 %b, 6
   %e = add i32 %c, %d
   ret i32 %e
 }
 
 define i32 @addshl_5_7(i32 %a, i32 %b) {
 ; RV32I-LABEL: addshl_5_7:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    slli a0, a0, 5
 ; RV32I-NEXT:    slli a1, a1, 7
 ; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32B-LABEL: addshl_5_7:
 ; RV32B:       # %bb.0:
+; RV32B-NEXT:    sh2add a0, a1, a0
 ; RV32B-NEXT:    slli a0, a0, 5
-; RV32B-NEXT:    slli a1, a1, 7
-; RV32B-NEXT:    add a0, a0, a1
 ; RV32B-NEXT:    ret
 ;
 ; RV32ZBA-LABEL: addshl_5_7:
 ; RV32ZBA:       # %bb.0:
+; RV32ZBA-NEXT:    sh2add a0, a1, a0
 ; RV32ZBA-NEXT:    slli a0, a0, 5
-; RV32ZBA-NEXT:    slli a1, a1, 7
-; RV32ZBA-NEXT:    add a0, a0, a1
 ; RV32ZBA-NEXT:    ret
   %c = shl i32 %a, 5
   %d = shl i32 %b, 7
   %e = add i32 %c, %d
   ret i32 %e
 }
 
 define i32 @addshl_5_8(i32 %a, i32 %b) {
 ; RV32I-LABEL: addshl_5_8:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    slli a0, a0, 5
 ; RV32I-NEXT:    slli a1, a1, 8
 ; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV32B-LABEL: addshl_5_8:
 ; RV32B:       # %bb.0:
+; RV32B-NEXT:    sh3add a0, a1, a0
 ; RV32B-NEXT:    slli a0, a0, 5
-; RV32B-NEXT:    slli a1, a1, 8
-; RV32B-NEXT:    add a0, a0, a1
 ; RV32B-NEXT:    ret
 ;
 ; RV32ZBA-LABEL: addshl_5_8:
 ; RV32ZBA:       # %bb.0:
+; RV32ZBA-NEXT:    sh3add a0, a1, a0
 ; RV32ZBA-NEXT:    slli a0, a0, 5
-; RV32ZBA-NEXT:    slli a1, a1, 8
-; RV32ZBA-NEXT:    add a0, a0, a1
 ; RV32ZBA-NEXT:    ret
   %c = shl i32 %a, 5
   %d = shl i32 %b, 8
   %e = add i32 %c, %d
   ret i32 %e
 }

llvm/test/CodeGen/RISCV/rv64zba.ll

 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slliw a0, a0, 5
 ; RV64I-NEXT:    slliw a1, a1, 6
 ; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64B-LABEL: addshl32_5_6:
 ; RV64B:       # %bb.0:
+; RV64B-NEXT:    sh1add a0, a1, a0
 ; RV64B-NEXT:    slliw a0, a0, 5
-; RV64B-NEXT:    slliw a1, a1, 6
-; RV64B-NEXT:    addw a0, a0, a1
 ; RV64B-NEXT:    ret
 ;
 ; RV64ZBA-LABEL: addshl32_5_6:
 ; RV64ZBA:       # %bb.0:
+; RV64ZBA-NEXT:    sh1add a0, a1, a0
 ; RV64ZBA-NEXT:    slliw a0, a0, 5
-; RV64ZBA-NEXT:    slliw a1, a1, 6
-; RV64ZBA-NEXT:    addw a0, a0, a1
 ; RV64ZBA-NEXT:    ret
   %c = shl i32 %a, 5
   %d = shl i32 %b, 6
   %e = add i32 %c, %d
   ret i32 %e
 }
 
 define i64 @addshl64_5_6(i64 %a, i64 %b) {
 ; RV64I-LABEL: addshl64_5_6:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slli a0, a0, 5
 ; RV64I-NEXT:    slli a1, a1, 6
 ; RV64I-NEXT:    add a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64B-LABEL: addshl64_5_6:
 ; RV64B:       # %bb.0:
+; RV64B-NEXT:    sh1add a0, a1, a0
 ; RV64B-NEXT:    slli a0, a0, 5
-; RV64B-NEXT:    slli a1, a1, 6
-; RV64B-NEXT:    add a0, a0, a1
 ; RV64B-NEXT:    ret
 ;
 ; RV64ZBA-LABEL: addshl64_5_6:
 ; RV64ZBA:       # %bb.0:
+; RV64ZBA-NEXT:    sh1add a0, a1, a0
 ; RV64ZBA-NEXT:    slli a0, a0, 5
-; RV64ZBA-NEXT:    slli a1, a1, 6
-; RV64ZBA-NEXT:    add a0, a0, a1
 ; RV64ZBA-NEXT:    ret
   %c = shl i64 %a, 5
   %d = shl i64 %b, 6
   %e = add i64 %c, %d
   ret i64 %e
 }
 
 define signext i32 @addshl32_5_7(i32 signext %a, i32 signext %b) {
 ; RV64I-LABEL: addshl32_5_7:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slliw a0, a0, 5
 ; RV64I-NEXT:    slliw a1, a1, 7
 ; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64B-LABEL: addshl32_5_7:
 ; RV64B:       # %bb.0:
+; RV64B-NEXT:    sh2add a0, a1, a0
 ; RV64B-NEXT:    slliw a0, a0, 5
-; RV64B-NEXT:    slliw a1, a1, 7
-; RV64B-NEXT:    addw a0, a0, a1
 ; RV64B-NEXT:    ret
 ;
 ; RV64ZBA-LABEL: addshl32_5_7:
 ; RV64ZBA:       # %bb.0:
+; RV64ZBA-NEXT:    sh2add a0, a1, a0
 ; RV64ZBA-NEXT:    slliw a0, a0, 5
-; RV64ZBA-NEXT:    slliw a1, a1, 7
-; RV64ZBA-NEXT:    addw a0, a0, a1
 ; RV64ZBA-NEXT:    ret
   %c = shl i32 %a, 5
   %d = shl i32 %b, 7
   %e = add i32 %c, %d
   ret i32 %e
 }
 
 define i64 @addshl64_5_7(i64 %a, i64 %b) {
 ; RV64I-LABEL: addshl64_5_7:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slli a0, a0, 5
 ; RV64I-NEXT:    slli a1, a1, 7
 ; RV64I-NEXT:    add a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64B-LABEL: addshl64_5_7:
 ; RV64B:       # %bb.0:
+; RV64B-NEXT:    sh2add a0, a1, a0
 ; RV64B-NEXT:    slli a0, a0, 5
-; RV64B-NEXT:    slli a1, a1, 7
-; RV64B-NEXT:    add a0, a0, a1
 ; RV64B-NEXT:    ret
 ;
 ; RV64ZBA-LABEL: addshl64_5_7:
 ; RV64ZBA:       # %bb.0:
+; RV64ZBA-NEXT:    sh2add a0, a1, a0
 ; RV64ZBA-NEXT:    slli a0, a0, 5
-; RV64ZBA-NEXT:    slli a1, a1, 7
-; RV64ZBA-NEXT:    add a0, a0, a1
 ; RV64ZBA-NEXT:    ret
   %c = shl i64 %a, 5
   %d = shl i64 %b, 7
   %e = add i64 %c, %d
   ret i64 %e
 }
 
 define signext i32 @addshl32_5_8(i32 signext %a, i32 signext %b) {
 ; RV64I-LABEL: addshl32_5_8:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slliw a0, a0, 5
 ; RV64I-NEXT:    slliw a1, a1, 8
 ; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64B-LABEL: addshl32_5_8:
 ; RV64B:       # %bb.0:
+; RV64B-NEXT:    sh3add a0, a1, a0
 ; RV64B-NEXT:    slliw a0, a0, 5
-; RV64B-NEXT:    slliw a1, a1, 8
-; RV64B-NEXT:    addw a0, a0, a1
 ; RV64B-NEXT:    ret
 ;
 ; RV64ZBA-LABEL: addshl32_5_8:
 ; RV64ZBA:       # %bb.0:
+; RV64ZBA-NEXT:    sh3add a0, a1, a0
 ; RV64ZBA-NEXT:    slliw a0, a0, 5
-; RV64ZBA-NEXT:    slliw a1, a1, 8
-; RV64ZBA-NEXT:    addw a0, a0, a1
 ; RV64ZBA-NEXT:    ret
   %c = shl i32 %a, 5
   %d = shl i32 %b, 8
   %e = add i32 %c, %d
   ret i32 %e
 }
 
 define i64 @addshl64_5_8(i64 %a, i64 %b) {
 ; RV64I-LABEL: addshl64_5_8:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slli a0, a0, 5
 ; RV64I-NEXT:    slli a1, a1, 8
 ; RV64I-NEXT:    add a0, a0, a1
 ; RV64I-NEXT:    ret
 ;
 ; RV64B-LABEL: addshl64_5_8:
 ; RV64B:       # %bb.0:
+; RV64B-NEXT:    sh3add a0, a1, a0
 ; RV64B-NEXT:    slli a0, a0, 5
-; RV64B-NEXT:    slli a1, a1, 8
-; RV64B-NEXT:    add a0, a0, a1
 ; RV64B-NEXT:    ret
 ;
 ; RV64ZBA-LABEL: addshl64_5_8:
 ; RV64ZBA:       # %bb.0:
+; RV64ZBA-NEXT:    sh3add a0, a1, a0
 ; RV64ZBA-NEXT:    slli a0, a0, 5
-; RV64ZBA-NEXT:    slli a1, a1, 8
-; RV64ZBA-NEXT:    add a0, a0, a1
 ; RV64ZBA-NEXT:    ret
   %c = shl i64 %a, 5
   %d = shl i64 %b, 8
   %e = add i64 %c, %d
   ret i64 %e
 }