[AARCH64][DAGCombine] Add combine for negation of CSEL absolute value pattern.

[sunho]

Summary

Fixes https://github.com/llvm/llvm-project/issues/51558.

The changes were ported from https://reviews.llvm.org/D111858 with some differences specific to aarch64 backend.

[sunho]

Edit typos

[sunho]

Edit existing test

[dmgreen]

Hello. This sounds good. It is similar to the patch in D112204 (but I din't have any time to continue that, glad to see you looking into the same thing!)

Feel free to steal what is useful from it, if you thing the suggested simplification is a good idea.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14699

I think we might be able to generalize this a bit, possibly simplifying it in the process. If we have neg (csel x, y, cc), we can convert to csel (neg x), (neg y), cc, and providing at least one of x and y simplify it will be the same cost or cheaper (with a csneg operation).

I think that means that the condition is unimportant, and we won't need to emit the Add. It won't handle all the same patterns this does, both might be quite rare for cases that are not -abs (as llvm will have often optimized before this point already), but might be more straight forward.

17668

I think you can include this in performAddSubCombine, just with a check that the opcode is ISD::SUB in there or performCombineSubABS.

[sunho]

I like your method! It's always reducing negation or keeping the same number of negation unless x and y are both non-negative and it can account for nabs case very well. I was trying to tidy your patch a bit and add some more test cases to address the comments by david-arm and submit it here. However, one thing came to concern me.

When one of x and y are negative maximum of that integer type (e.g. -128 for int8), then folding negation can nullify signed integer overflows that would have happended if not folded. For instance, if you have -csel(-x,-y), then it will be folded to csel(x,y). If x was the negative maximum of that integer type, it would lead to singed integer overflow in the original form (-(-128)), but it will not after folded.

I'm not sure whether I can just consider this case UB and fold it. Could you give me some advice on this?

[sunho]

IIUC, if nsw flag is not specified it will wrap around, then -(-128) = -128, still yielding the same result. Even if nsw flag is specified, I can define poison value as anything I want so it's still fine?

[sunho]

https://alive2.llvm.org/ce/z/2KoTdr It always passes unless I put nsw on sub in tgt block. I guess that means it's okay.

[sunho]

Use simpler pattern based on https://reviews.llvm.org/D112204

[sunho]

Remove space.

[sunho]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14730

I've added isNegatedInteger util function as suggested by david-arm in the original patch. The util function can be used in many places across multiple backends. I can submit a follow-up patch replacing to use this function if desired.

[dmgreen]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14699

SDValues can be passed by value - they are pretty small.

14718

Could this now use: if (!isNegatedInteger(N))?

llvm/test/CodeGen/AArch64/neg-selects.ll

2

Can you pre-commit the tests and show just the differences here?

[sunho]

Sorry for the delay. I've separated commits that adds tests to https://reviews.llvm.org/D120214, and make this commit only show the difference between older version.

[dmgreen]

LGTM. Thanks.

[sunho]

Cheers! Can you commit on my behalf?

Author name: sunho
Author email: [e-mail]

[dmgreen]

Whoops. I put the wrong differential revision on that commit. Sorry about that. https://reviews.llvm.org/rGd6a9eec2382559aeae3bb87761afa1b6d351e9a5 should have pointed here instead.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

if (!isZeroDot(Dot))
     std::swap(Dot, A);
   if (!isZeroDot(Dot))
     return SDValue();
 
   return DAG.getNode(Dot.getOpcode(), SDLoc(N), VT, A, Dot.getOperand(1),
                      Dot.getOperand(2));
 }
 
+static bool isNegatedInteger(const SDValue &Op) {
+  return Op.getOpcode() == ISD::SUB && isNullConstant(Op.getOperand(0));
+}
+
+static SDValue getNegatedInteger(const SDValue &Op, SelectionDAG &DAG) {
+  SDLoc DL(Op);
+  EVT VT = Op.getValueType();
+  SDValue Zero = DAG.getConstant(0, DL, VT);
+  return DAG.getNode(ISD::SUB, DL, VT, Zero, Op);
+}
+
+// Try to fold
+//
+// (neg (csel X, Y)) -> (csel (neg X), (neg Y))
+//
+// The folding helps csel to be matched with csneg without generating
+// redundant neg instruction, which includes negation of the csel expansion
+// of abs node lowered by lowerABS.
+static SDValue performNegCSelCombine(SDNode *N, SelectionDAG &DAG) {
+  if (N->getOpcode() != ISD::SUB || !isNullConstant(N->getOperand(0)))
+    return SDValue();
+
+  SDValue CSel = N->getOperand(1);
+  if (CSel.getOpcode() != AArch64ISD::CSEL || !CSel->hasOneUse())
+    return SDValue();
+
+  SDValue N0 = CSel.getOperand(0);
+  SDValue N1 = CSel.getOperand(1);
+
+  // If both of them is not negations, it's not worth the folding as it
+  // introduces two additional negations while reducing one negation.
+  if (!isNegatedInteger(N0) && !isNegatedInteger(N1))
+    return SDValue();
+
+  SDValue N0N = getNegatedInteger(N0, DAG);
+  SDValue N1N = getNegatedInteger(N1, DAG);
+
+  SDLoc DL(N);
+  EVT VT = CSel.getValueType();
+  return DAG.getNode(AArch64ISD::CSEL, DL, VT, N0N, N1N, CSel.getOperand(2),
+                     CSel.getOperand(3));
+}
+
 // The basic add/sub long vector instructions have variants with "2" on the end
 // which act on the high-half of their inputs. They are normally matched by
 // patterns like:
 //
 // (add (zeroext (extract_high LHS)),
 //      (zeroext (extract_high RHS)))
 // -> uaddl2 vD, vN, vM
 //

 static SDValue performAddSubCombine(SDNode *N,
                                     TargetLowering::DAGCombinerInfo &DCI,
                                     SelectionDAG &DAG) {
   // Try to change sum of two reductions.
   if (SDValue Val = performUADDVCombine(N, DAG))
     return Val;
   if (SDValue Val = performAddDotCombine(N, DAG))
     return Val;
+  if (SDValue Val = performNegCSelCombine(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)) -->

 
 SDValue AArch64TargetLowering::PerformDAGCombine(SDNode *N,
                                                  DAGCombinerInfo &DCI) const {
   SelectionDAG &DAG = DCI.DAG;
   switch (N->getOpcode()) {
   default:
     LLVM_DEBUG(dbgs() << "Custom combining: skipping\n");
     break;
+
   case ISD::ADD:
   case ISD::SUB:
     return performAddSubCombine(N, DCI, DAG);
   case ISD::XOR:
     return performXorCombine(N, DAG, DCI, Subtarget);
   case ISD::MUL:
     return performMulCombine(N, DAG, DCI, Subtarget);
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:
     return performIntToFpCombine(N, DAG, Subtarget);
   case ISD::FP_TO_SINT:

llvm/test/CodeGen/AArch64/neg-abs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -verify-machineinstrs \
 ; RUN:   -mtriple=aarch64-unknown-unknown < %s | FileCheck %s
 
 declare i64 @llvm.abs.i64(i64, i1 immarg)
 
 define i64 @neg_abs64(i64 %x) {
 ; CHECK-LABEL: neg_abs64:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    cmp x0, #0
-; CHECK-NEXT:    cneg x8, x0, mi
-; CHECK-NEXT:    neg x0, x8
+; CHECK-NEXT:    cneg x0, x0, pl
 ; CHECK-NEXT:    ret
   %abs = tail call i64 @llvm.abs.i64(i64 %x, i1 true)
   %neg = sub nsw i64 0, %abs
   ret i64 %neg
 }
 
 declare i32 @llvm.abs.i32(i32, i1 immarg)
 
 define i32 @neg_abs32(i32 %x) {
 ; CHECK-LABEL: neg_abs32:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    cmp w0, #0
-; CHECK-NEXT:    cneg w8, w0, mi
-; CHECK-NEXT:    neg w0, w8
+; CHECK-NEXT:    cneg w0, w0, pl
 ; CHECK-NEXT:    ret
   %abs = tail call i32 @llvm.abs.i32(i32 %x, i1 true)
   %neg = sub nsw i32 0, %abs
   ret i32 %neg
 }
 
 declare i16 @llvm.abs.i16(i16, i1 immarg)
 

llvm/test/CodeGen/AArch64/neg-selects.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=aarch64-none-none-eabi %s -o - | FileCheck %s
+
+define i32 @neg_select_neg(i32 %a, i32 %b, i1 %bb) {
+; CHECK-LABEL: neg_select_neg:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    tst w2, #0x1
+; CHECK-NEXT:    csel w0, w0, w1, ne
+; CHECK-NEXT:    ret
+  %nega = sub i32 0, %a
+  %negb = sub i32 0, %b
+  %sel = select i1 %bb, i32 %nega, i32 %negb
+  %res = sub i32 0, %sel
+  ret i32 %res
+}
+
+define i32 @negneg_select_nega(i32 %a, i32 %b, i1 %bb) {
+; CHECK-LABEL: negneg_select_nega:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    tst w2, #0x1
+; CHECK-NEXT:    csneg w0, w1, w0, eq
+; CHECK-NEXT:    ret
+  %nega = sub i32 0, %a
+  %sel = select i1 %bb, i32 %nega, i32 %b
+  %nsel = sub i32 0, %sel
+  %res = sub i32 0, %nsel
+  ret i32 %res
+}
+
+define i32 @neg_select_nega(i32 %a, i32 %b, i1 %bb) {
+; CHECK-LABEL: neg_select_nega:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    tst w2, #0x1
+; CHECK-NEXT:    csneg w0, w0, w1, ne
+; CHECK-NEXT:    ret
+  %nega = sub i32 0, %a
+  %sel = select i1 %bb, i32 %nega, i32 %b
+  %res = sub i32 0, %sel
+  ret i32 %res
+}
+
+define i32 @neg_select_negb(i32 %a, i32 %b, i1 %bb) {
+; CHECK-LABEL: neg_select_negb:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    tst w2, #0x1
+; CHECK-NEXT:    csneg w0, w1, w0, eq
+; CHECK-NEXT:    ret
+  %negb = sub i32 0, %b
+  %sel = select i1 %bb, i32 %a, i32 %negb
+  %res = sub i32 0, %sel
+  ret i32 %res
+}
+
+define i32 @neg_select_ab(i32 %a, i32 %b, i1 %bb) {
+; CHECK-LABEL: neg_select_ab:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    tst w2, #0x1
+; CHECK-NEXT:    csel w8, w0, w1, ne
+; CHECK-NEXT:    neg w0, w8
+; CHECK-NEXT:    ret
+  %sel = select i1 %bb, i32 %a, i32 %b
+  %res = sub i32 0, %sel
+  ret i32 %res
+}
+
+define i32 @neg_select_nega_with_use(i32 %a, i32 %b, i1 %bb) {
+; CHECK-LABEL: neg_select_nega_with_use:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    tst w2, #0x1
+; CHECK-NEXT:    neg w8, w0
+; CHECK-NEXT:    csneg w9, w1, w0, eq
+; CHECK-NEXT:    sub w0, w8, w9
+; CHECK-NEXT:    ret
+  %nega = sub i32 0, %a
+  %sel = select i1 %bb, i32 %nega, i32 %b
+  %nsel = sub i32 0, %sel
+  %res = add i32 %nsel, %nega
+  ret i32 %res
+}