[AArch64] Add `foldADCToCINC` DAG combine

[Kmeakin]

Rebase on top of https://reviews.llvm.org/rG13403a70e45b2d22878ba59fc211f8dba3a8deba

[paulwalker-arm]

It's not immediately clear to me what the advantage is to using CINC verses ADC. Sure some of the tests emit less code but for those cases it just looks like we're not making good use of xzr?

[Kmeakin]

In D123781#3475209, @paulwalker-arm wrote:

It's not immediately clear to me what the advantage is to using CINC verses ADC. Sure some of the tests emit less code but for those cases it just looks like we're not making good use of xzr?

It's true that both instructions have the same throughput and latency (on all the microarchitecures I could find the optimisation guides for), but I would argue that CSINC is a more natural/canonical way of representing this operation than ADC, which could make it easier for future optimisations to recognise it.

I'm not sure why ADC requires an extra MOV: maybe the register allocation could so with improvement?

[paulwalker-arm]

In D123781#3477558, @Kmeakin wrote:

In D123781#3475209, @paulwalker-arm wrote:

It's not immediately clear to me what the advantage is to using CINC verses ADC. Sure some of the tests emit less code but for those cases it just looks like we're not making good use of xzr?

It's true that both instructions have the same throughput and latency (on all the microarchitecures I could find the optimisation guides for), but I would argue that CSINC is a more natural/canonical way of representing this operation than ADC, which could make it easier for future optimisations to recognise it.

Fair enough, but then in D124464 you use getNodeIfExists to see if there's an existing ADC to use in place of ADCS which depending on the ordering of combines might mean we don't find a candidate because it's been converted to CINC. That said, perhaps this isn't a realistic issue and it means we avoid the poor xzr usage issue so LGTM.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

static SDValue foldOverflowCheck(SDNode *Op, SelectionDAG &DAG, bool IsAdd) {
   if (CC != (IsAdd ? AArch64CC::HS : AArch64CC::LO))
     return SDValue();
 
   return DAG.getNode(Op->getOpcode(), SDLoc(Op), Op->getVTList(),
                      Op->getOperand(0), Op->getOperand(1),
                      CsetOp.getOperand(3));
 }
 
+// (ADC x 0 cond) => (CINC x HS cond)
+static SDValue foldADCToCINC(SDNode *N, SelectionDAG &DAG) {
+  SDValue LHS = N->getOperand(0);
+  SDValue RHS = N->getOperand(1);
+  SDValue Cond = N->getOperand(2);
+
+  if (!isNullConstant(RHS))
+    return SDValue();
+
+  EVT VT = N->getValueType(0);
+  SDLoc DL(N);
+
+  // (CINC x cc cond) <=> (CSINC x x !cc cond)
+  SDValue CC = DAG.getConstant(AArch64CC::LO, DL, MVT::i32);
+  return DAG.getNode(AArch64ISD::CSINC, DL, VT, LHS, LHS, CC, Cond);
+}
+
 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;
default:
     LLVM_DEBUG(dbgs() << "Custom combining: skipping\n");
     break;
   case ISD::ADD:
   case ISD::SUB:
     return performAddSubCombine(N, DCI, DAG);
   case AArch64ISD::ANDS:
     return performFlagSettingCombine(N, DCI, ISD::AND);
   case AArch64ISD::ADC:
-    return foldOverflowCheck(N, DAG, /* IsAdd */ true);
+    if (auto R = foldOverflowCheck(N, DAG, /* IsAdd */ true))
+      return R;
+    return foldADCToCINC(N, DAG);
   case AArch64ISD::SBC:
     return foldOverflowCheck(N, DAG, /* IsAdd */ false);
   case AArch64ISD::ADCS:
     if (auto R = foldOverflowCheck(N, DAG, /* IsAdd */ true))
       return R;
     return performFlagSettingCombine(N, DCI, AArch64ISD::ADC);
   case AArch64ISD::SBCS:
     if (auto R = foldOverflowCheck(N, DAG, /* IsAdd */ false))

llvm/test/CodeGen/AArch64/adc.ll

; CHECK-BE-NEXT:    ret
 
   ret i128 %valsub
 }
 
 define i128 @test_imm(i128 %a) {
 ; CHECK-LE-LABEL: test_imm:
 ; CHECK-LE:       ; %bb.0:
 ; CHECK-LE-NEXT:    adds x0, x0, #12
-; CHECK-LE-NEXT:    adc x1, x1, xzr
+; CHECK-LE-NEXT:    cinc x1, x1, hs
 ; CHECK-LE-NEXT:    ret
 ;
 ; CHECK-BE-LABEL: test_imm:
 ; CHECK-BE:       // %bb.0:
 ; CHECK-BE-NEXT:    adds x1, x1, #12
-; CHECK-BE-NEXT:    adc x0, x0, xzr
+; CHECK-BE-NEXT:    cinc x0, x0, hs
 ; CHECK-BE-NEXT:    ret
 
   %val = add i128 %a, 12
 
   ret i128 %val
 }
 
 define i128 @test_shifted(i128 %a, i128 %b) {

llvm/test/CodeGen/AArch64/addcarry-crash.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s | FileCheck %s
 target triple = "arm64-apple-ios7.0"
 
 define i64 @foo(i64* nocapture readonly %ptr, i64 %a, i64 %b, i64 %c) local_unnamed_addr #0 {
 ; CHECK-LABEL: foo:
 ; CHECK:       ; %bb.0: ; %entry
 ; CHECK-NEXT:    ldr w8, [x0, #4]
 ; CHECK-NEXT:    lsr x9, x1, #32
 ; CHECK-NEXT:    cmn x3, x2
 ; CHECK-NEXT:    mul x8, x8, x9
-; CHECK-NEXT:    adc x0, x8, xzr
+; CHECK-NEXT:    cinc x0, x8, hs
 ; CHECK-NEXT:    ret
 entry:
   %0 = lshr i64 %a, 32
   %1 = load i64, i64* %ptr, align 8
   %2 = lshr i64 %1, 32
   %3 = mul nuw i64 %2, %0
   %4 = add i64 %c, %b
   %5 = icmp ult i64 %4, %c
   %6 = zext i1 %5 to i64
   %7 = add i64 %3, %6
   ret i64 %7
 }
 
 attributes #0 = { norecurse nounwind readonly }

llvm/test/CodeGen/AArch64/atomicrmw-O0.ll

 ; NOLSE-NEXT:    b .LBB4_1
 ; NOLSE-NEXT:  .LBB4_1: // %atomicrmw.start
 ; NOLSE-NEXT:    // =>This Loop Header: Depth=1
 ; NOLSE-NEXT:    // Child Loop BB4_2 Depth 2
 ; NOLSE-NEXT:    ldr x11, [sp, #40] // 8-byte Folded Reload
 ; NOLSE-NEXT:    ldr x8, [sp, #32] // 8-byte Folded Reload
 ; NOLSE-NEXT:    ldr x13, [sp, #24] // 8-byte Folded Reload
 ; NOLSE-NEXT:    adds x14, x8, #1
-; NOLSE-NEXT:    mov x9, xzr
-; NOLSE-NEXT:    adc x15, x11, x9
+; NOLSE-NEXT:    cinc x15, x11, hs
 ; NOLSE-NEXT:  .LBB4_2: // %atomicrmw.start
 ; NOLSE-NEXT:    // Parent Loop BB4_1 Depth=1
 ; NOLSE-NEXT:    // => This Inner Loop Header: Depth=2
 ; NOLSE-NEXT:    ldaxp x10, x9, [x13]
 ; NOLSE-NEXT:    cmp x10, x8
 ; NOLSE-NEXT:    cset w12, ne
 ; NOLSE-NEXT:    cmp x9, x11
 ; NOLSE-NEXT:    cinc w12, w12, ne

 ; LSE-NEXT:    str x9, [sp, #64] // 8-byte Folded Spill
 ; LSE-NEXT:    str x8, [sp, #72] // 8-byte Folded Spill
 ; LSE-NEXT:    b .LBB4_1
 ; LSE-NEXT:  .LBB4_1: // %atomicrmw.start
 ; LSE-NEXT:    // =>This Inner Loop Header: Depth=1
 ; LSE-NEXT:    ldr x10, [sp, #72] // 8-byte Folded Reload
 ; LSE-NEXT:    ldr x8, [sp, #64] // 8-byte Folded Reload
 ; LSE-NEXT:    ldr x9, [sp, #56] // 8-byte Folded Reload
-; LSE-NEXT:    adds x2, x8, #1
-; LSE-NEXT:    mov x11, xzr
-; LSE-NEXT:    adc x11, x10, x11
-; LSE-NEXT:    // kill: def $x2 killed $x2 def $x2_x3
-; LSE-NEXT:    mov x3, x11
 ; LSE-NEXT:    mov x0, x8
 ; LSE-NEXT:    mov x1, x10
 ; LSE-NEXT:    stp x0, x1, [sp, #8] // 16-byte Folded Spill
+; LSE-NEXT:    adds x2, x8, #1
+; LSE-NEXT:    cinc x11, x10, hs
+; LSE-NEXT:    // kill: def $x2 killed $x2 def $x2_x3
+; LSE-NEXT:    mov x3, x11
 ; LSE-NEXT:    caspal x0, x1, x2, x3, [x9]
 ; LSE-NEXT:    stp x0, x1, [sp, #24] // 16-byte Folded Spill
 ; LSE-NEXT:    mov x9, x1
 ; LSE-NEXT:    str x9, [sp, #40] // 8-byte Folded Spill
 ; LSE-NEXT:    eor x11, x9, x10
 ; LSE-NEXT:    mov x10, x0
 ; LSE-NEXT:    str x10, [sp, #48] // 8-byte Folded Spill
 ; LSE-NEXT:    eor x8, x10, x8

llvm/test/CodeGen/AArch64/icmp-shift-opt.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=arm64-eabi | FileCheck %s
 
 ; Optimize expanded SRL/SHL used as an input of
 ; SETCC comparing it with zero by removing rotation.
 ;
 ; See https://bugs.llvm.org/show_bug.cgi?id=50197
 define i128 @opt_setcc_lt_power_of_2(i128 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_lt_power_of_2:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:  .LBB0_1: // %loop
 ; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    adds x0, x0, #1
-; CHECK-NEXT:    adc x1, x1, xzr
+; CHECK-NEXT:    cinc x1, x1, hs
 ; CHECK-NEXT:    orr x8, x1, x0, lsr #60
 ; CHECK-NEXT:    cbnz x8, .LBB0_1
 ; CHECK-NEXT:  // %bb.2: // %exit
 ; CHECK-NEXT:    ret
   br label %loop
 
 loop:
   %phi.a = phi i128 [ %a, %0 ], [ %inc, %loop ]