[DAGCombiner][AArch64] Enhance to support for scalar CSINC

[Allen]

Summary

Enhance to fold csel into csinc instruction.
Fix https://github.com/llvm/llvm-project/issues/53071

[Allen]

This comment was removed by Allen.

[Allen]

reformat the code according the Pre-merge checking

[Allen]

This comment was removed by Allen.

[Allen]

fix to support the combine of long long type and
failure of Transforms/LoopVectorize/vplan-widen-select-instruction.ll

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14874

the type for AArch64CC need be MVT::i32

[spatel]

Adding some potential reviewers.

I think it would be good to add the tests with the current (baseline) CHECK lines, so it is easy to see how this patch changes existing codegen.

[spatel]

It would be good to add a link to the motivating bug in the patch description:
https://github.com/llvm/llvm-project/issues/53071

[Allen]

reformat the code according the Pre-merge checking

In D116915#3235039, @spatel wrote:

Adding some potential reviewers.

I think it would be good to add the tests with the current (baseline) CHECK lines, so it is easy to see how this patch changes existing codegen.

ok , done, related commit https://reviews.llvm.org/rGdc01fb1d726a8faad7e78cbf580300a4005c6a23

[Allen]

In D116915#3235043, @spatel wrote:

It would be good to add a link to the motivating bug in the patch description:
https://github.com/llvm/llvm-project/issues/53071

done

[dmgreen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14839

This might be easier to read as:
b + CSEL (c, 1, cc) => CSINC(b+c, b, cc)
b + CSNEG (1, c, cc) => CSINC(b-c, b, !cc)

Does the a!=0/a==0 matter? Or is it valid for all conditions?

14852

Why does this only trigger from a CopyFromReg?
Should we be checking for commutative Add operands?

14855

Should we be checking the input CC (operand 2) is NE?

It should probably be using AArch64CC::CondCode without needing to go back to ISD::CondCode, possibly using AArch64CC::getInvertedCondCode to invert the condition.

[Allen]

update according review idea

[dmgreen]

Some of the previous comments don't appear to have been addressed. Only looking for a CopyFromReg looks suspicious, and there is no testing for csneg that I can see.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14856

I don't think this will only be EQ or NE. It can be any of the predicates.

The condition code is usually obtained via static_cast<AArch64CC::CondCode>(OpCC->getZExtValue()) or something like it.

[Allen]

As all case now are csel related, so remove csneg and it will be processed in another new patch

[Allen]

update format according pre-commit

[dmgreen]

Thanks. And the CopyFromReg? This is currently converting add(csel(C, 1, cc), CopyFromReg(x)) into csinc(add(x, C), x). I'm not sure why it would be limited to a CopyFromReg. I would expect to convert any add(csel(C, 1, cc), y) (or add(y, csel(C, 1, cc)) as add is commutative).

In order to be profitable this seems to also be relying on the fact that the add(x, C) will turn into an ADDri, which wouldn't be true for all constants. It might be neutral for larger constants? It's probably worth adding a test or two.

[Allen]

1、Handle commutivity
2、prevent large const value, and add related test case

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14839

valid for all conditions, Both of them are add in test file aarch64-isel-csinc.ll

14852

Why does this only trigger from a CopyFromReg?

this may be can expand later, but now I don't have such case.

Should we be checking for commutative Add operands?

As it is already restricted scalar Integer type, I think it would be commutative add?

14855

Yes, added checking conditon. and thanks for you detail advice of using AArch64CC::getInvertedCondCode .

14856

done, delete the assert after use API static_cast<AArch64CC::CondCode>(OpCC->getZExtValue())

[Allen]

In D116915#3261832, @dmgreen wrote:

Thanks. And the CopyFromReg? This is currently converting add(csel(C, 1, cc), CopyFromReg(x)) into csinc(add(x, C), x). I'm not sure why it would be limited to a CopyFromReg. I would expect to convert any add(csel(C, 1, cc), y) (or add(y, csel(C, 1, cc)) as add is commutative).

Thanks for detail advice, I updated in three point
1、Handle commutivity
2、prevent large const value , and add related test case
3、delete the condition CopyFromReg

[dmgreen]

Thanks for the updates - a couple of last comments.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14856

I don't think it matters if the RHS has more than 1 use, it should still be OK to transform as we only use the value in another expression.

14859–14862

AArch64CC::CondCode AArch64CC = static_cast<AArch64CC::CondCode>(CSel.getConstantOperandVal(2));

[Allen]

retry the commit with condition RHS.hasOneUse()

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14856

I had delete the condition !RHS.hasOneUse(), but recently the upstream may has some regression, it doen't finish the precommit build checking. so may I need wait a moment to figure out that issue ?

14859–14862

done, thanks

[dmgreen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14856

Hmm. That sounds suspicious. What was the problem? That would usually imply an infinite loop in DAG combine, but I'm not sure how csinc(add(x, y), x, cc) could get back to add(x, csel(y, 1, cc)). Or why the uses of y matter in that case.

I was about to OK the revision, but it would be good to make sure that nothing problematic is happening.

[Allen]

Now, I can make true the x86 debian fail is brought in by other patch already submited in the upstream,
as it still have the same fail at the commit node Diff 10 403452 after rolling back the change of delete the condition !RHS.hasOneUse(),
and it is successfully at the commit node Diff 8 402198 , which has same change.

Is it reasonable?

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14856

hi, dmgreen

In fact, I can't reproduce the failure base on my local building with delete the condition !RHS.hasOneUse(), so it may be not this change cause the regression, as you can see the other person's commit don't also pass building recently.

Just to be sure, do you think it is ok to roll back the change of delete the condition !RHS.hasOneUse(), and submit it firstly ? I'll resubmit the change of delete the condition !RHS.hasOneUse() after the upstream is stable with double checking.

The building log is finally came out record in https://reviews.llvm.org/harbormaster/build/215411/, and detail info can be found in x86 debian fail
Failed Tests (9):

libarcher :: races/critical-unrelated.c
libarcher :: races/lock-nested-unrelated.c
libarcher :: races/lock-unrelated.c
libarcher :: races/parallel-simple.c
libarcher :: races/task-dependency.c
libarcher :: races/task-taskgroup-unrelated.c
libarcher :: races/task-taskwait-nested.c
libarcher :: races/task-two.c
libarcher :: task/task_late_fulfill.c

[dmgreen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14856

They sound like they should be unrelated, coming from a x86 machine. I would recommend the version without the !RHS.hasOneUse() check, unless we have some evidence that it is really this check that is breaking something. But I don't think it should do.

[Allen]

delete the check of !RHS.hasOneUse()

[dmgreen]

Looks good to me, lets give it a try. Thanks

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

static SDValue performAddUADDVCombine(SDNode *N, SelectionDAG &DAG) {
   EVT ValVT = Val1->getValueType(0);
   SDLoc DL(N);
   SDValue AddVal = DAG.getNode(ISD::ADD, DL, ValVT, Val1, Val2);
   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
                      DAG.getNode(AArch64ISD::UADDV, DL, ValVT, AddVal),
                      DAG.getConstant(0, DL, MVT::i64));
 }
 
+/// Perform the scalar expression combine in the form of:
+///   CSEL (c, 1, cc) + b => CSINC(b+c, b, cc)
+static SDValue performAddCSelIntoCSinc(SDNode *N, SelectionDAG &DAG) {
+  EVT VT = N->getValueType(0);
+  if (!VT.isScalarInteger() || N->getOpcode() != ISD::ADD)
+    return SDValue();
+
+  SDValue CSel = N->getOperand(0);
+  SDValue RHS = N->getOperand(1);
+
+  // Handle commutivity.
+  if (CSel.getOpcode() != AArch64ISD::CSEL) {
+    std::swap(CSel, RHS);
+    if (CSel.getOpcode() != AArch64ISD::CSEL) {
+      return SDValue();
+    }
+  }
+
+  if (!CSel.hasOneUse())
+    return SDValue();
+
+  AArch64CC::CondCode AArch64CC =
+      static_cast<AArch64CC::CondCode>(CSel.getConstantOperandVal(2));
+
+  // The CSEL should include a const one operand.
+  ConstantSDNode *CTVal = dyn_cast<ConstantSDNode>(CSel.getOperand(0));
+  ConstantSDNode *CFVal = dyn_cast<ConstantSDNode>(CSel.getOperand(1));
+  if (!CTVal || !CFVal || (!CTVal->isOne() && !CFVal->isOne()))
+    return SDValue();
+
+  // switch CSEL (1, c, cc)  to CSEL (c, 1, !cc)
+  if (CTVal->isOne() && !CFVal->isOne()) {
+    std::swap(CTVal, CFVal);
+    AArch64CC = AArch64CC::getInvertedCondCode(AArch64CC);
+  }
+
+  // It might be neutral for larger constants, as the immediate need to be
+  // materialized in a register.
+  APInt ADDC = CTVal->getAPIntValue();
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  if (!TLI.isLegalAddImmediate(ADDC.getSExtValue()))
+    return SDValue();
+
+  assert(CFVal->isOne() && "Unexpected constant value");
+
+  SDLoc DL(N);
+  SDValue NewNode = DAG.getNode(ISD::ADD, DL, VT, RHS, SDValue(CTVal, 0));
+  SDValue CCVal = DAG.getConstant(AArch64CC, DL, MVT::i32);
+  SDValue Cmp = CSel.getOperand(3);
+
+  return DAG.getNode(AArch64ISD::CSINC, DL, VT, NewNode, RHS, CCVal, Cmp);
+}
+
 // ADD(UDOT(zero, x, y), A) -->  UDOT(A, x, y)
 static SDValue performAddDotCombine(SDNode *N, SelectionDAG &DAG) {
   EVT VT = N->getValueType(0);
   if (N->getOpcode() != ISD::ADD)
     return SDValue();
 
   SDValue Dot = N->getOperand(0);
   SDValue A = N->getOperand(1);

 static SDValue performAddSubCombine(SDNode *N,
                                     TargetLowering::DAGCombinerInfo &DCI,
                                     SelectionDAG &DAG) {
   // Try to change sum of two reductions.
   if (SDValue Val = performAddUADDVCombine(N, DAG))
     return Val;
   if (SDValue Val = performAddDotCombine(N, DAG))
     return Val;
+  if (SDValue Val = performAddCSelIntoCSinc(N, DAG))
+    return Val;
 
   return performAddSubLongCombine(N, DCI, DAG);
 }
 
 // Massage DAGs which we can use the high-half "long" operations on into
 // something isel will recognize better. E.g.
 //
 // (aarch64_neon_umull (extract_high vec) (dupv64 scalar)) -->

llvm/test/CodeGen/AArch64/aarch64-isel-csinc-type.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=aarch64-- -o - < %s | FileCheck %s
 
 ; Verify that we can fold csneg/csel into csinc instruction.
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-gnu"
 
 ; char csinc1 (char a, char b) { return !a ? b+1 : b+3; }
 define dso_local i8 @csinc1(i8 %a, i8 %b) local_unnamed_addr #0 {
 ; CHECK-LABEL: csinc1:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    tst w0, #0xff
-; CHECK-NEXT:    mov w8, #3
-; CHECK-NEXT:    csinc w8, w8, wzr, ne
-; CHECK-NEXT:    add w0, w8, w1
+; CHECK-NEXT:    add w8, w1, #3
+; CHECK-NEXT:    csinc w0, w8, w1, ne
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i8 %a, 0
   %cond.v = select i1 %tobool.not, i8 1, i8 3
   %cond = add i8 %cond.v, %b
   ret i8 %cond
 }
 
 ; short csinc2 (short a, short b) { return !a ? b+1 : b+3; }
 define dso_local i16 @csinc2(i16 %a, i16 %b) local_unnamed_addr #0 {
 ; CHECK-LABEL: csinc2:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    tst w0, #0xffff
-; CHECK-NEXT:    mov w8, #3
-; CHECK-NEXT:    csinc w8, w8, wzr, ne
-; CHECK-NEXT:    add w0, w8, w1
+; CHECK-NEXT:    add w8, w1, #3
+; CHECK-NEXT:    csinc w0, w8, w1, ne
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i16 %a, 0
   %cond.v = select i1 %tobool.not, i16 1, i16 3
   %cond = add i16 %cond.v, %b
   ret i16 %cond
 }
 
 ; int csinc3 (int a, int b) { return !a ? b+1 : b+3; }
 define dso_local i32 @csinc3(i32 %a, i32 %b) local_unnamed_addr #0 {
 ; CHECK-LABEL: csinc3:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    cmp w0, #0
-; CHECK-NEXT:    mov w8, #3
-; CHECK-NEXT:    csinc w8, w8, wzr, ne
-; CHECK-NEXT:    add w0, w8, w1
+; CHECK-NEXT:    add w8, w1, #3
+; CHECK-NEXT:    csinc w0, w8, w1, ne
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i32 %a, 0
   %cond.v = select i1 %tobool.not, i32 1, i32 3
   %cond = add nsw i32 %cond.v, %b
   ret i32 %cond
 }
 
 ; long long csinc4 (long long a, long long b) { return !a ? b+1 : b+3; }
 define dso_local i64 @csinc4(i64 %a, i64 %b) local_unnamed_addr #0 {
 ; CHECK-LABEL: csinc4:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    cmp x0, #0
-; CHECK-NEXT:    mov w8, #3
-; CHECK-NEXT:    csinc x8, x8, xzr, ne
-; CHECK-NEXT:    add x0, x8, x1
+; CHECK-NEXT:    add x8, x1, #3
+; CHECK-NEXT:    csinc x0, x8, x1, ne
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i64 %a, 0
   %cond.v = select i1 %tobool.not, i64 1, i64 3
   %cond = add nsw i64 %cond.v, %b
   ret i64 %cond
 }

llvm/test/CodeGen/AArch64/aarch64-isel-csinc.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=aarch64-- -o - < %s | FileCheck %s
 
 ; Verify that we can fold csneg/csel into csinc instruction.
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-gnu"
 
 ; int csinc1 (int a, int b) { return !a ? b+3 : b+1; }
 define dso_local i32 @csinc1(i32 %a, i32 %b) {
 ; CHECK-LABEL: csinc1:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    cmp w0, #0
-; CHECK-NEXT:    mov w8, #3
-; CHECK-NEXT:    csinc w8, w8, wzr, eq
-; CHECK-NEXT:    add w0, w8, w1
+; CHECK-NEXT:    add w8, w1, #3
+; CHECK-NEXT:    csinc w0, w8, w1, eq
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i32 %a, 0
   %cond.v = select i1 %tobool.not, i32 3, i32 1
   %cond = add nsw i32 %cond.v, %b
   ret i32 %cond
 }
 
 ; int csinc2 (int a, int b) { return a ? b+3 : b+1; }
 define dso_local i32 @csinc2(i32 %a, i32 %b) {
 ; CHECK-LABEL: csinc2:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    cmp w0, #0
-; CHECK-NEXT:    mov w8, #3
-; CHECK-NEXT:    csinc w8, w8, wzr, ne
-; CHECK-NEXT:    add w0, w8, w1
+; CHECK-NEXT:    add w8, w1, #3
+; CHECK-NEXT:    csinc w0, w8, w1, ne
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i32 %a, 0
   %cond.v = select i1 %tobool.not, i32 1, i32 3
   %cond = add nsw i32 %cond.v, %b
   ret i32 %cond
 }
 
 ; int csinc3 (int a, int b) { return !a ? b+1 : b-3; }
 define dso_local i32 @csinc3(i32 %a, i32 %b) {
 ; CHECK-LABEL: csinc3:
 ; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    sub w8, w1, #3
 ; CHECK-NEXT:    cmp w0, #0
-; CHECK-NEXT:    mov w8, #-3
-; CHECK-NEXT:    csinc w8, w8, wzr, ne
-; CHECK-NEXT:    add w0, w8, w1
+; CHECK-NEXT:    csinc w0, w8, w1, ne
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i32 %a, 0
   %cond.v = select i1 %tobool.not, i32 1, i32 -3
   %cond = add nsw i32 %cond.v, %b
   ret i32 %cond
 }
 
 ; int csinc4 (int a, int b) { return a ? b+1 : b-3; }
 define dso_local i32 @csinc4(i32 %a, i32 %b) {
 ; CHECK-LABEL: csinc4:
 ; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    sub w8, w1, #3
 ; CHECK-NEXT:    cmp w0, #0
-; CHECK-NEXT:    mov w8, #-3
+; CHECK-NEXT:    csinc w0, w8, w1, eq
+; CHECK-NEXT:    ret
+entry:
+  %tobool.not = icmp eq i32 %a, 0
+  %cond.v = select i1 %tobool.not, i32 -3, i32 1
+  %cond = add nsw i32 %cond.v, %b
+  ret i32 %cond
+}
+
+; int csinc5 (int a, int b) { return a ? b+1 : b-4095; }
+define dso_local i32 @csinc5(i32 %a, i32 %b) {
+; CHECK-LABEL: csinc5:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    sub w8, w1, #4095
+; CHECK-NEXT:    cmp w0, #0
+; CHECK-NEXT:    csinc w0, w8, w1, eq
+; CHECK-NEXT:    ret
+entry:
+  %tobool.not = icmp eq i32 %a, 0
+  %cond.v = select i1 %tobool.not, i32 -4095, i32 1
+  %cond = add nsw i32 %cond.v, %b
+  ret i32 %cond
+}
+
+; int csinc6 (int a, int b) { return a ? b+1 : b-4096; }
+define dso_local i32 @csinc6(i32 %a, i32 %b) {
+; CHECK-LABEL: csinc6:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    sub w8, w1, #1, lsl #12 // =4096
+; CHECK-NEXT:    cmp w0, #0
+; CHECK-NEXT:    csinc w0, w8, w1, eq
+; CHECK-NEXT:    ret
+entry:
+  %tobool.not = icmp eq i32 %a, 0
+  %cond.v = select i1 %tobool.not, i32 -4096, i32 1
+  %cond = add nsw i32 %cond.v, %b
+  ret i32 %cond
+}
+
+; prevent larger constants (the add laid after csinc)
+; int csinc7 (int a, int b) { return a ? b+1 : b-4097; }
+define dso_local i32 @csinc7(i32 %a, i32 %b) {
+; CHECK-LABEL: csinc7:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    cmp w0, #0
+; CHECK-NEXT:    mov w8, #-4097
 ; CHECK-NEXT:    csinc w8, w8, wzr, eq
 ; CHECK-NEXT:    add w0, w8, w1
 ; CHECK-NEXT:    ret
 entry:
   %tobool.not = icmp eq i32 %a, 0
-  %cond.v = select i1 %tobool.not, i32 -3, i32 1
+  %cond.v = select i1 %tobool.not, i32 -4097, i32 1
   %cond = add nsw i32 %cond.v, %b
   ret i32 %cond
 }

llvm/test/CodeGen/AArch64/arm64-csel.ll

; CHECK-NEXT:    ret
   %cmp = icmp eq i64 %x, 5
   %res = select i1 %cmp, i64 1, i64 6
   ret i64 %res
 }
 
 define i16 @foo24(i8* nocapture readonly %A, i8* nocapture readonly %B) {
 ; CHECK-LABEL: foo24:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    ldrb w8, [x1]
-; CHECK-NEXT:    ldrb w9, [x0]
-; CHECK-NEXT:    cmp w8, #33
+; CHECK-NEXT:    ldrb w8, [x0]
+; CHECK-NEXT:    ldrb w9, [x1]
+; CHECK-NEXT:    cmp w8, #3
 ; CHECK-NEXT:    cset w8, hi
-; CHECK-NEXT:    cmp w9, #3
+; CHECK-NEXT:    cmp w9, #33
 ; CHECK-NEXT:    cinc w0, w8, hi
 ; CHECK-NEXT:    ret
 entry:
   %0 = load i8, i8* %A, align 1
   %cmp = icmp ugt i8 %0, 3
   %conv1 = zext i1 %cmp to i16
   %1 = load i8, i8* %B, align 1
   %cmp4 = icmp ugt i8 %1, 33