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

[benshi001]

Summary

Transform (add (shl x, c0), c1) ->
          (add (shl (add x, c1>>c0), c0), c1-(c1>>c0<<c0)),
if c1>>c0 and c1-(c1>>c0<<c0) are simm12, while c1 is not.

Or transform (add (shl x, c0), c1) ->
             (shl (add x, c1>>c0), c0),
if c1-(c1>>c0<<c0) is zero, and c1>>c0 is simm12 while c1 is not.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

6477

I think you can drop this if, getNode will see the constant is 0 and not produce an ADD node.

6483–6484

Just drop this comment. It's already above transformAddImmMulImm.

6484

This comment is already above transformAddImmShlImm, we don't need to repeat it.

[benshi001]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

6454

This comment also repeated before the definition of transformAddShlImm, and should also be dropped.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

6468

I think you need to abort if C0 is greater than VT.getSizeInBits() - 1.

[benshi001]

ping ... Any concerns about this patch ?

[asb]

I'm getting a warning when building this (with clang 12.0.1):

/home/asb/llvm-project/llvm/lib/Target/RISCV/RISCVISelLowering.cpp:6490:20: warning: comparison of integers of different signs: 'int64_t' (aka 'long') and 'unsigned long' [-Wsign-compare]
  if (C0 < 1 || C0 > VT.getSizeInBits() - 1 || isInt<12>(C1) ||

[benshi001]

In D111117#3103171, @asb wrote:

I'm getting a warning when building this (with clang 12.0.1):

/home/asb/llvm-project/llvm/lib/Target/RISCV/RISCVISelLowering.cpp:6490:20: warning: comparison of integers of different signs: 'int64_t' (aka 'long') and 'unsigned long' [-Wsign-compare]
  if (C0 < 1 || C0 > VT.getSizeInBits() - 1 || isInt<12>(C1) ||

I have fixed in the newest patch.

[asb]

I'm seeing some code size regressions on this patch - specifically, cases where a reg-reg add is replaced with an addi -256 (which isn't compressible). e.g. 20050121-1.c from the GCC torture suite (-O1, rv32imafdc).

[benshi001]

In D111117#3111631, @asb wrote:

I'm seeing some code size regressions on this patch - specifically, cases where a reg-reg add is replaced with an addi -256 (which isn't compressible). e.g. 20050121-1.c from the GCC torture suite (-O1, rv32imafdc).

Thanks for your patient and careful test, I will made a new patch for SHL related optimization after a careful check.

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

if (SDValue Result = combineSelectAndUse(N, N0, N1, DAG, AllOnes))
     return Result;
   if (SDValue Result = combineSelectAndUse(N, N1, N0, DAG, AllOnes))
     return Result;
   return SDValue();
 }
 
 // Transform (add (mul x, c0), c1) ->
 //           (add (mul (add x, c1/c0), c0), c1%c0).
-// if c1/c0 and c1%c0 are simm12, while c1 is not.
+// if c1/c0 and c1%c0 are simm12, while c1 is not. A special corner case
+// should also be excluded is when c0*(c1/c0) is simm12, which will lead
+// to an infinite loop in DAGCombine.
 // Or transform (add (mul x, c0), c1) ->
 //              (mul (add x, c1/c0), c0).
 // if c1%c0 is zero, and c1/c0 is simm12 while c1 is not.
 static SDValue transformAddImmMulImm(SDNode *N, SelectionDAG &DAG,
                                      const RISCVSubtarget &Subtarget) {
   // Skip for vector types and larger types.
   EVT VT = N->getValueType(0);
   if (VT.isVector() || VT.getSizeInBits() > Subtarget.getXLen())
     return SDValue();
   // The first operand node must be a MUL and has no other use.
   SDValue N0 = N->getOperand(0);
   if (!N0->hasOneUse() || N0->getOpcode() != ISD::MUL)
     return SDValue();
   // Check if c0 and c1 match above conditions.
   auto *N0C = dyn_cast<ConstantSDNode>(N0->getOperand(1));
   auto *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1));
   if (!N0C || !N1C)
     return SDValue();
   int64_t C0 = N0C->getSExtValue();
   int64_t C1 = N1C->getSExtValue();
   if (C0 == -1 || C0 == 0 || C0 == 1 || (C1 / C0) == 0 || isInt<12>(C1) ||
-      !isInt<12>(C1 % C0) || !isInt<12>(C1 / C0))
-    return SDValue();
-  // If C0 * (C1 / C0) is a 12-bit integer, this transform will be reversed.
-  if (isInt<12>(C0 * (C1 / C0)))
+      !isInt<12>(C1 % C0) || !isInt<12>(C1 / C0) || isInt<12>(C0 * (C1 / C0)))
     return SDValue();
   // Build new nodes (add (mul (add x, c1/c0), c0), c1%c0).
   SDLoc DL(N);
   SDValue New0 = DAG.getNode(ISD::ADD, DL, VT, N0->getOperand(0),
                              DAG.getConstant(C1 / C0, DL, VT));
   SDValue New1 =
       DAG.getNode(ISD::MUL, DL, VT, New0, DAG.getConstant(C0, DL, VT));
   if ((C1 % C0) == 0)
     return New1;
   return DAG.getNode(ISD::ADD, DL, VT, New1, DAG.getConstant(C1 % C0, DL, VT));
 }
 
+// Transform (add (shl x, c0), c1) ->
+//           (add (shl (add x, c1>>c0), c0), c1-(c1>>c0<<c0)),
+// if c1>>c0 and c1-(c1>>c0<<c0) are simm12, while c1 is not. A special corner
+// should also be excluded is when c1>>c0<<c0 is simm12, which will lead
+// to an infinite loop in DAGCombine.
+// Or transform (add (shl x, c0), c1) ->
+//              (shl (add x, c1>>c0), c0),
+// if c1-(c1>>c0<<c0) is zero, and c1>>c0 is simm12 while c1 is not.
+static SDValue transformAddImmShlImm(SDNode *N, SelectionDAG &DAG,
+                                     const RISCVSubtarget &Subtarget) {
+  // Skip for vector types and larger types.
+  EVT VT = N->getValueType(0);
+  if (VT.isVector() || VT.getSizeInBits() > Subtarget.getXLen())
+    return SDValue();
+  // The first operand node must be a SHL and has no other use.
+  SDValue N0 = N->getOperand(0);
+  if (!N0->hasOneUse() || N0->getOpcode() != ISD::SHL)
+    return SDValue();
+  // Check if c0 and c1 match above conditions.
+  auto *N0C = dyn_cast<ConstantSDNode>(N0->getOperand(1));
+  auto *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1));
+  if (!N0C || !N1C)
+    return SDValue();
+  int64_t C0 = N0C->getSExtValue();
+  int64_t C1 = N1C->getSExtValue();
+  if (C0 < 1 || C0 > (int64_t)(VT.getSizeInBits() - 1) || isInt<12>(C1) ||
+      (C1 >> C0) == 0 || !isInt<12>(C1 >> C0) || isInt<12>(C1 >> C0 << C0) ||
+      !isInt<12>(C1 - (C1 >> C0 << C0)))
+    return SDValue();
+  // Build new nodes.
+  SDLoc DL(N);
+  SDValue New0 = DAG.getNode(ISD::ADD, DL, VT, N0->getOperand(0),
+                             DAG.getConstant(C1 >> C0, DL, VT));
+  SDValue New1 =
+      DAG.getNode(ISD::SHL, DL, VT, New0, DAG.getConstant(C0, DL, VT));
+  return DAG.getNode(ISD::ADD, DL, VT, New1,
+                     DAG.getConstant(C1 - (C1 >> C0 << C0), DL, VT));
+}
+
 static SDValue performADDCombine(SDNode *N, SelectionDAG &DAG,
                                  const RISCVSubtarget &Subtarget) {
-  // Transform (add (mul x, c0), c1) ->
-  //           (add (mul (add x, c1/c0), c0), c1%c0).
-  // if c1/c0 and c1%c0 are simm12, while c1 is not.
-  // Or transform (add (mul x, c0), c1) ->
-  //              (mul (add x, c1/c0), c0).
-  // if c1%c0 is zero, and c1/c0 is simm12 while c1 is not.
+  if (SDValue V = transformAddImmShlImm(N, DAG, Subtarget))
+    return V;
   if (SDValue V = transformAddImmMulImm(N, DAG, Subtarget))
     return V;
-  // Fold (add (shl x, c0), (shl y, c1)) ->
-  //      (SLLI (SH*ADD x, y), c0), if c1-c0 equals to [1|2|3].
   if (SDValue V = transformAddShlImm(N, DAG, Subtarget))
     return V;
   // fold (add (select lhs, rhs, cc, 0, y), x) ->
   //      (select lhs, rhs, cc, x, (add x, y))
   return combineSelectAndUseCommutative(N, DAG, /*AllOnes*/ false);
 }
 
 static SDValue performSUBCombine(SDNode *N, SelectionDAG &DAG) {

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

; RV64I-NEXT:    ret
   %tmp0 = shl i64 %x, 5
   %tmp1 = add i64 %tmp0, 101024
   ret i64 %tmp1
 }
 
 define i32 @shl5_add47968_a(i32 %x) {
 ; RV32I-LABEL: shl5_add47968_a:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 1499
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 12
-; RV32I-NEXT:    addi a1, a1, -1184
-; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_add47968_a:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, 1499
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 12
-; RV64I-NEXT:    addiw a1, a1, -1184
-; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, 47968
   ret i32 %tmp1
 }
 
 define signext i32 @shl5_add47968_b(i32 signext %x) {
 ; RV32I-LABEL: shl5_add47968_b:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 1499
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 12
-; RV32I-NEXT:    addi a1, a1, -1184
-; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_add47968_b:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, 1499
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 12
-; RV64I-NEXT:    addiw a1, a1, -1184
-; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, 47968
   ret i32 %tmp1
 }
 
 define i64 @shl5_add47968_c(i64 %x) {
 ; RV32I-LABEL: shl5_add47968_c:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    srli a2, a0, 27
 ; RV32I-NEXT:    slli a1, a1, 5
 ; RV32I-NEXT:    or a1, a1, a2
 ; RV32I-NEXT:    slli a2, a0, 5
 ; RV32I-NEXT:    lui a0, 12
 ; RV32I-NEXT:    addi a0, a0, -1184
 ; RV32I-NEXT:    add a0, a2, a0
 ; RV32I-NEXT:    sltu a2, a0, a2
 ; RV32I-NEXT:    add a1, a1, a2
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_add47968_c:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, 1499
 ; RV64I-NEXT:    slli a0, a0, 5
-; RV64I-NEXT:    lui a1, 12
-; RV64I-NEXT:    addiw a1, a1, -1184
-; RV64I-NEXT:    add a0, a0, a1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i64 %x, 5
   %tmp1 = add i64 %tmp0, 47968
   ret i64 %tmp1
 }
 
 define i32 @shl5_add47969_a(i32 %x) {
 ; RV32I-LABEL: shl5_add47969_a:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 1499
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 12
-; RV32I-NEXT:    addi a1, a1, -1183
-; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ori a0, a0, 1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_add47969_a:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, 1499
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 12
-; RV64I-NEXT:    addiw a1, a1, -1183
-; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ori a0, a0, 1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, 47969
   ret i32 %tmp1
 }
 
 define signext i32 @shl5_add47969_b(i32 signext %x) {
 ; RV32I-LABEL: shl5_add47969_b:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, 1499
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 12
-; RV32I-NEXT:    addi a1, a1, -1183
-; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ori a0, a0, 1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_add47969_b:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, 1499
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 12
-; RV64I-NEXT:    addiw a1, a1, -1183
-; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ori a0, a0, 1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, 47969
   ret i32 %tmp1
 }
 
 define i64 @shl5_add47969_c(i64 %x) {
 ; RV32I-LABEL: shl5_add47969_c:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    srli a2, a0, 27
 ; RV32I-NEXT:    slli a1, a1, 5
 ; RV32I-NEXT:    or a1, a1, a2
 ; RV32I-NEXT:    slli a2, a0, 5
 ; RV32I-NEXT:    lui a0, 12
 ; RV32I-NEXT:    addi a0, a0, -1183
 ; RV32I-NEXT:    add a0, a2, a0
 ; RV32I-NEXT:    sltu a2, a0, a2
 ; RV32I-NEXT:    add a1, a1, a2
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_add47969_c:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, 1499
 ; RV64I-NEXT:    slli a0, a0, 5
-; RV64I-NEXT:    lui a1, 12
-; RV64I-NEXT:    addiw a1, a1, -1183
-; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ori a0, a0, 1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i64 %x, 5
   %tmp1 = add i64 %tmp0, 47969
   ret i64 %tmp1
 }
 
 define i32 @shl5_sub47968_a(i32 %x) {
 ; RV32I-LABEL: shl5_sub47968_a:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -1499
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 1048564
-; RV32I-NEXT:    addi a1, a1, 1184
-; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_sub47968_a:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, -1499
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 1048564
-; RV64I-NEXT:    addiw a1, a1, 1184
-; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, -47968
   ret i32 %tmp1
 }
 
 define signext i32 @shl5_sub47968_b(i32 signext %x) {
 ; RV32I-LABEL: shl5_sub47968_b:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -1499
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 1048564
-; RV32I-NEXT:    addi a1, a1, 1184
-; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_sub47968_b:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, -1499
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 1048564
-; RV64I-NEXT:    addiw a1, a1, 1184
-; RV64I-NEXT:    addw a0, a0, a1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, -47968
   ret i32 %tmp1
 }
 
 define i64 @shl5_sub47968_c(i64 %x) {
 ; RV32I-LABEL: shl5_sub47968_c:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    srli a2, a0, 27
 ; RV32I-NEXT:    slli a1, a1, 5
 ; RV32I-NEXT:    or a1, a1, a2
 ; RV32I-NEXT:    slli a2, a0, 5
 ; RV32I-NEXT:    lui a0, 1048564
 ; RV32I-NEXT:    addi a0, a0, 1184
 ; RV32I-NEXT:    add a0, a2, a0
 ; RV32I-NEXT:    sltu a2, a0, a2
 ; RV32I-NEXT:    add a1, a1, a2
 ; RV32I-NEXT:    addi a1, a1, -1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_sub47968_c:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, -1499
 ; RV64I-NEXT:    slli a0, a0, 5
-; RV64I-NEXT:    lui a1, 1048564
-; RV64I-NEXT:    addiw a1, a1, 1184
-; RV64I-NEXT:    add a0, a0, a1
 ; RV64I-NEXT:    ret
   %tmp0 = shl i64 %x, 5
   %tmp1 = add i64 %tmp0, -47968
   ret i64 %tmp1
 }
 
 define i32 @shl5_sub47969_a(i32 %x) {
 ; RV32I-LABEL: shl5_sub47969_a:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -1500
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 1048564
-; RV32I-NEXT:    addi a1, a1, 1183
-; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ori a0, a0, 31
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_sub47969_a:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, -1500
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 1048564
-; RV64I-NEXT:    addiw a1, a1, 1183
-; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ori a0, a0, 31
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, -47969
   ret i32 %tmp1
 }
 
 define signext i32 @shl5_sub47969_b(i32 signext %x) {
 ; RV32I-LABEL: shl5_sub47969_b:
 ; RV32I:       # %bb.0:
+; RV32I-NEXT:    addi a0, a0, -1500
 ; RV32I-NEXT:    slli a0, a0, 5
-; RV32I-NEXT:    lui a1, 1048564
-; RV32I-NEXT:    addi a1, a1, 1183
-; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ori a0, a0, 31
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_sub47969_b:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addiw a0, a0, -1500
 ; RV64I-NEXT:    slliw a0, a0, 5
-; RV64I-NEXT:    lui a1, 1048564
-; RV64I-NEXT:    addiw a1, a1, 1183
-; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ori a0, a0, 31
 ; RV64I-NEXT:    ret
   %tmp0 = shl i32 %x, 5
   %tmp1 = add i32 %tmp0, -47969
   ret i32 %tmp1
 }
 
 define i64 @shl5_sub47969_c(i64 %x) {
 ; RV32I-LABEL: shl5_sub47969_c:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    srli a2, a0, 27
 ; RV32I-NEXT:    slli a1, a1, 5
 ; RV32I-NEXT:    or a1, a1, a2
 ; RV32I-NEXT:    slli a2, a0, 5
 ; RV32I-NEXT:    lui a0, 1048564
 ; RV32I-NEXT:    addi a0, a0, 1183
 ; RV32I-NEXT:    add a0, a2, a0
 ; RV32I-NEXT:    sltu a2, a0, a2
 ; RV32I-NEXT:    add a1, a1, a2
 ; RV32I-NEXT:    addi a1, a1, -1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: shl5_sub47969_c:
 ; RV64I:       # %bb.0:
+; RV64I-NEXT:    addi a0, a0, -1500
 ; RV64I-NEXT:    slli a0, a0, 5
-; RV64I-NEXT:    lui a1, 1048564
-; RV64I-NEXT:    addiw a1, a1, 1183
-; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ori a0, a0, 31
 ; RV64I-NEXT:    ret
   %tmp0 = shl i64 %x, 5
   %tmp1 = add i64 %tmp0, -47969
   ret i64 %tmp1
 }