[DAGCombine][PowerPC] Convert negated abs to trivial arithmetic ops

[lkail]

Summary

This patch converts 0 - abs(x) to Y = sra (X, size(X)-1); sub (Y, xor (X, Y)) for better codegen.

[steven.zhang]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9348

Should we fold it into sub (0, ABS()) if ABS is legal ? And how about the VSELECT ? And it also surprise me that, there isn't pattern here for the ABS(). If it has, your code might merge with that one.

[RKSimon]

llvm/test/CodeGen/PowerPC/select.ll

133 ↗

(On Diff #304038)

Commit these new tests to trunk with current codegen then rebase this patch to show the codegen diff?

[spatel]

Note that we are planning to canonicalize IR to the abs() intrinsic - D87188.
Assuming that comes through relatively soon (cc @nikic), should we hold off adding what would probably become dead code in the backend?

[steven.zhang]

In D91120#2391105, @spatel wrote:

Note that we are planning to canonicalize IR to the abs() intrinsic - D87188.
Assuming that comes through relatively soon (cc @nikic), should we hold off adding what would probably become dead code in the backend?

That is good news. But we still need to combine the sub(0, abs) to sradi/xor/sub as it saves one instruction.
What we have now with D87188:

0:	76 fe 64 7c 	sradi   r4,r3,63
4:	14 22 63 7c 	add     r3,r3,r4
8:	78 22 63 7c 	xor     r3,r3,r4
c:	d0 00 63 7c 	neg     r3,r3

And it can be improved to:

0:	76 fe 60 7c 	sradi   r0,r3,63
4:	78 02 63 7c 	xor     r3,r3,r0
8:	50 00 63 7c 	subf    r3,r3,r0

[lkail]

In D91120#2391105, @spatel wrote:

Note that we are planning to canonicalize IR to the abs() intrinsic - D87188.
Assuming that comes through relatively soon (cc @nikic), should we hold off adding what would probably become dead code in the backend?

Thanks for the info. Let me apply D87188 and see what will be going on. After D87188 is landed, I'll update the patch accordingly if necessary.

[lkail]

Pre-committed test case and rebased.

[spatel]

It seems strange that we would need to add a TLI hook to avoid regressing a target that has abs/nabs support in the ISA.
If I'm seeing it correctly, SystemZ relies on ISD::ABS being expanded and then pattern-matching the expansion back to lpgr for example. Could we change that target to declare ISD::ABS as legal and adjust the tablegen matching for it?

[uweigand]

In D91120#2399776, @spatel wrote:

It seems strange that we would need to add a TLI hook to avoid regressing a target that has abs/nabs support in the ISA.
If I'm seeing it correctly, SystemZ relies on ISD::ABS being expanded and then pattern-matching the expansion back to lpgr for example. Could we change that target to declare ISD::ABS as legal and adjust the tablegen matching for it?

That SystemZ code pre-dates the existence of the common ISD::ABS code by four years or so. I guess now that common code support ISD::ABS, we can change our back-end to use it instead of our own. @jonpa , can you have a look?

[jonpa]

In D91120#2399901, @uweigand wrote:

In D91120#2399776, @spatel wrote:

It seems strange that we would need to add a TLI hook to avoid regressing a target that has abs/nabs support in the ISA.
If I'm seeing it correctly, SystemZ relies on ISD::ABS being expanded and then pattern-matching the expansion back to lpgr for example. Could we change that target to declare ISD::ABS as legal and adjust the tablegen matching for it?

That SystemZ code pre-dates the existence of the common ISD::ABS code by four years or so. I guess now that common code support ISD::ABS, we can change our back-end to use it instead of our own. @jonpa , can you have a look?

Yes, this seems to work: https://reviews.llvm.org/D91697. The new TLI hook is then not needed...

[spatel]

In D91120#2402335, @jonpa wrote:

Yes, this seems to work: https://reviews.llvm.org/D91697. The new TLI hook is then not needed...

Nice - thank you for the fast fix!

[lkail]

Removed the hook and added test cases for other arch.

[steven.zhang]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3221

Hmm, it looks strange to me that we have to add these two ops into worklist manual. Isn't it added into worklist automatically as far as the parent node (SUB) returned ? Please correct me if I misunderstand this.

[lkail]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3221

Good catch. I think the combine loop is supposed to add direct child nodes to the worklist. Since AddToWorklist uniques nodes added, I think it's also ok to call it manually. Another question arises, can we always rely on the behavior of the combine loop adding direct child node to the worklist automatically.

[RKSimon]

Please can you rebase after rG9374e7b1781f00 ?

[lkail]

Rebased on Simon's commit.

[RKSimon]

LGTM

[lkail]

Removed parent revision, since this patch doesn't rely on opt's abs canonicalization.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (DAG.MaskedValueIsZero(N1, ~APInt::getSignMask(BitWidth))) {
       // N1 is either 0 or the minimum signed value. If the sub is NSW, then
       // N1 must be 0 because negating the minimum signed value is undefined.
       if (N->getFlags().hasNoSignedWrap())
         return N0;
 
       // 0 - X --> X if X is 0 or the minimum signed value.
       return N1;
     }
+
+    // Convert 0 - abs(x) -> Y = sra (X, size(X)-1); sub (Y, xor (X, Y)).
+    if (N1->getOpcode() == ISD::ABS &&
+        !TLI.isOperationLegalOrCustom(ISD::ABS, VT)) {
+      SDValue X = N1->getOperand(0);
+      SDValue Shift =
+          DAG.getNode(ISD::SRA, DL, VT, X,
+                      DAG.getConstant(BitWidth - 1, DL, getShiftAmountTy(VT)));
+      SDValue Xor = DAG.getNode(ISD::XOR, DL, VT, X, Shift);
+      AddToWorklist(Shift.getNode());
+      AddToWorklist(Xor.getNode());
+      return DAG.getNode(ISD::SUB, DL, VT, Shift, Xor);
+    }
   }
 
   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1)
   if (isAllOnesOrAllOnesSplat(N0))
     return DAG.getNode(ISD::XOR, DL, VT, N1, N0);
 
   // fold (A - (0-B)) -> A+B
   if (N1.getOpcode() == ISD::SUB && isNullOrNullSplat(N1.getOperand(0)))
if (N0.getOpcode() == ISD::SETCC) {
     }
 
     if (TLI.isOperationLegal(ISD::SELECT_CC, VT) ||
         (!LegalOperations &&
          TLI.isOperationLegalOrCustom(ISD::SELECT_CC, VT))) {
       // Any flags available in a select/setcc fold will be on the setcc as they
       // migrated from fcmp
       Flags = N0.getNode()->getFlags();
       SDValue SelectNode = DAG.getNode(ISD::SELECT_CC, DL, VT, Cond0, Cond1, N1,
                                        N2, N0.getOperand(2));
       SelectNode->setFlags(Flags);
       return SelectNode;
     }
 
     return SimplifySelect(DL, N0, N1, N2);
   }
 

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_abs(i64 %x) {
 ; CHECK-LABEL: neg_abs:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    cmp x0, #0 // =0
-; CHECK-NEXT:    cneg x8, x0, mi
-; CHECK-NEXT:    neg x0, x8
+; CHECK-NEXT:    asr x8, x0, #63
+; CHECK-NEXT:    eor x9, x0, x8
+; CHECK-NEXT:    sub x0, x8, x9
 ; CHECK-NEXT:    ret
   %abs = tail call i64 @llvm.abs.i64(i64 %x, i1 true)
   %neg = sub nsw i64 0, %abs
   ret i64 %neg
 }

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

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -ppc-asm-full-reg-names -verify-machineinstrs \
 ; RUN:   -mtriple=powerpc64le-linux-gnu < %s | FileCheck \
 ; RUN:   -check-prefix=CHECK-LE %s
 
 declare i64 @llvm.abs.i64(i64, i1 immarg)
 
 define i64@neg_abs(i64 %x) {
 ; CHECK-LE-LABEL: neg_abs:
 ; CHECK-LE:       # %bb.0:
 ; CHECK-LE-NEXT:    sradi r4, r3, 63
-; CHECK-LE-NEXT:    add r3, r3, r4
 ; CHECK-LE-NEXT:    xor r3, r3, r4
-; CHECK-LE-NEXT:    neg r3, r3
+; CHECK-LE-NEXT:    sub r3, r4, r3
 ; CHECK-LE-NEXT:    blr
   %abs = tail call i64 @llvm.abs.i64(i64 %x, i1 true)
   %neg = sub nsw i64 0, %abs
   ret i64 %neg
 }

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

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -verify-machineinstrs -mtriple=riscv32-unknown-unknown | FileCheck %s --check-prefix=RV32
 ; RUN: llc < %s -verify-machineinstrs -mtriple=riscv64-unknown-unknown | FileCheck %s --check-prefix=RV64
 
 declare i32 @llvm.abs.i32(i32, i1 immarg)
 declare i64 @llvm.abs.i64(i64, i1 immarg)
 
 define i32 @neg_abs32(i32 %x) {
 ; RV32-LABEL: neg_abs32:
 ; RV32:       # %bb.0:
 ; RV32-NEXT:    srai a1, a0, 31
-; RV32-NEXT:    add a0, a0, a1
 ; RV32-NEXT:    xor a0, a0, a1
-; RV32-NEXT:    neg a0, a0
+; RV32-NEXT:    sub a0, a1, a0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: neg_abs32:
 ; RV64:       # %bb.0:
-; RV64-NEXT:    sext.w a1, a0
-; RV64-NEXT:    srai a1, a1, 63
-; RV64-NEXT:    add a0, a0, a1
+; RV64-NEXT:    sraiw a1, a0, 31
 ; RV64-NEXT:    xor a0, a0, a1
-; RV64-NEXT:    negw a0, a0
+; RV64-NEXT:    subw a0, a1, a0
 ; RV64-NEXT:    ret
   %abs = tail call i32 @llvm.abs.i32(i32 %x, i1 true)
   %neg = sub nsw i32 0, %abs
   ret i32 %neg
 }
 
 define i64 @neg_abs64(i64 %x) {
 ; RV32-LABEL: neg_abs64:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    bgez a1, .LBB1_2
-; RV32-NEXT:  # %bb.1:
-; RV32-NEXT:    snez a2, a0
-; RV32-NEXT:    add a1, a1, a2
-; RV32-NEXT:    neg a1, a1
-; RV32-NEXT:    neg a0, a0
-; RV32-NEXT:  .LBB1_2:
-; RV32-NEXT:    snez a2, a0
-; RV32-NEXT:    add a1, a1, a2
-; RV32-NEXT:    neg a1, a1
-; RV32-NEXT:    neg a0, a0
+; RV32-NEXT:    srai a2, a1, 31
+; RV32-NEXT:    xor a0, a0, a2
+; RV32-NEXT:    sltu a3, a2, a0
+; RV32-NEXT:    xor a1, a1, a2
+; RV32-NEXT:    sub a1, a2, a1
+; RV32-NEXT:    sub a1, a1, a3
+; RV32-NEXT:    sub a0, a2, a0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: neg_abs64:
 ; RV64:       # %bb.0:
 ; RV64-NEXT:    srai a1, a0, 63
-; RV64-NEXT:    add a0, a0, a1
 ; RV64-NEXT:    xor a0, a0, a1
-; RV64-NEXT:    neg a0, a0
+; RV64-NEXT:    sub a0, a1, a0
 ; RV64-NEXT:    ret
   %abs = tail call i64 @llvm.abs.i64(i64 %x, i1 true)
   %neg = sub nsw i64 0, %abs
   ret i64 %neg
 }