[AMDGPU] simplify add x, *ext (setcc) => addc|subb x, 0, setcc

[rampitec]

Summary

This simplification allows to avoid generating v_cndmask_b32 to serialize condition code between compare and use.

[arsenm]

Why does this need to be a target combine? Can't we use the sub with overflow generic nodes?

[rampitec]

In D34300#782899, @arsenm wrote:

Why does this need to be a target combine? Can't we use the sub with overflow generic nodes?

Surprisingly ISD::ADDE and ISD::SUBE expect two operands, regardless of what is written in documentation. See for example this pattern with two inputs:

let Uses = [SCC] in { // Carry in comes from SCC
let isCommutable = 1 in {
def S_ADDC_U32 : SOP2_32 <"s_addc_u32",
  [(set i32:$sdst, (adde (i32 SSrc_b32:$src0), (i32 SSrc_b32:$src1)))]>;
} // End isCommutable = 1

So I did it the same way as ARM.

[rampitec]

Fixed typo in the test.

[arsenm]

In D34300#782902, @rampitec wrote:

In D34300#782899, @arsenm wrote:

Why does this need to be a target combine? Can't we use the sub with overflow generic nodes?

Surprisingly ISD::ADDE and ISD::SUBE expect two operands, regardless of what is written in documentation. See for example this pattern with two inputs:

let Uses = [SCC] in { // Carry in comes from SCC
let isCommutable = 1 in {
def S_ADDC_U32 : SOP2_32 <"s_addc_u32",
  [(set i32:$sdst, (adde (i32 SSrc_b32:$src0), (i32 SSrc_b32:$src1)))]>;
} // End isCommutable = 1

So I did it the same way as ARM.

I meant the other sets of add/sub nodes, like ISD::SADDO. The input is a n allocatable register bool like how the instructions work rather than a flag relying on glue like ADDE

[rampitec]

In D34300#784771, @arsenm wrote:

In D34300#782902, @rampitec wrote:

In D34300#782899, @arsenm wrote:

Why does this need to be a target combine? Can't we use the sub with overflow generic nodes?

Surprisingly ISD::ADDE and ISD::SUBE expect two operands, regardless of what is written in documentation. See for example this pattern with two inputs:

let Uses = [SCC] in { // Carry in comes from SCC
let isCommutable = 1 in {
def S_ADDC_U32 : SOP2_32 <"s_addc_u32",
  [(set i32:$sdst, (adde (i32 SSrc_b32:$src0), (i32 SSrc_b32:$src1)))]>;
} // End isCommutable = 1

So I did it the same way as ARM.

I meant the other sets of add/sub nodes, like ISD::SADDO. The input is a n allocatable register bool like how the instructions work rather than a flag relying on glue like ADDE

It produces flag, not consumes it. Also it distinguish between signed/unsigned.

[rampitec]

Removed unused variable.

[arsenm]

In D34300#784772, @rampitec wrote:

In D34300#784771, @arsenm wrote:

In D34300#782902, @rampitec wrote:

In D34300#782899, @arsenm wrote:

Why does this need to be a target combine? Can't we use the sub with overflow generic nodes?

Surprisingly ISD::ADDE and ISD::SUBE expect two operands, regardless of what is written in documentation. See for example this pattern with two inputs:

let Uses = [SCC] in { // Carry in comes from SCC
let isCommutable = 1 in {
def S_ADDC_U32 : SOP2_32 <"s_addc_u32",
  [(set i32:$sdst, (adde (i32 SSrc_b32:$src0), (i32 SSrc_b32:$src1)))]>;
} // End isCommutable = 1

So I did it the same way as ARM.

I meant the other sets of add/sub nodes, like ISD::SADDO. The input is a n allocatable register bool like how the instructions work rather than a flag relying on glue like ADDE

It produces flag, not consumes it. Also it distinguish between signed/unsigned.

I think the right one is ADDCARRY, SUBCARRY:

The use of this opcode is preferable to adde/sube if the

/// target supports it, as the carry is a regular value rather than a
/// glue, which allows further optimisation.

[rampitec]

In D34300#784872, @arsenm wrote:

In D34300#784772, @rampitec wrote:

In D34300#784771, @arsenm wrote:

In D34300#782902, @rampitec wrote:

In D34300#782899, @arsenm wrote:

Why does this need to be a target combine? Can't we use the sub with overflow generic nodes?

Surprisingly ISD::ADDE and ISD::SUBE expect two operands, regardless of what is written in documentation. See for example this pattern with two inputs:

let Uses = [SCC] in { // Carry in comes from SCC
let isCommutable = 1 in {
def S_ADDC_U32 : SOP2_32 <"s_addc_u32",
  [(set i32:$sdst, (adde (i32 SSrc_b32:$src0), (i32 SSrc_b32:$src1)))]>;
} // End isCommutable = 1

So I did it the same way as ARM.

I meant the other sets of add/sub nodes, like ISD::SADDO. The input is a n allocatable register bool like how the instructions work rather than a flag relying on glue like ADDE

It produces flag, not consumes it. Also it distinguish between signed/unsigned.

I think the right one is ADDCARRY, SUBCARRY:

The use of this opcode is preferable to adde/sube if the

/// target supports it, as the carry is a regular value rather than a
/// glue, which allows further optimisation.

It seems to be so new that I do not even see a def for them in TargTargetSelectionDAG.td. Am I missing something?

[rampitec]

In D34300#784872, @arsenm wrote:

I think the right one is ADDCARRY, SUBCARRY:

The use of this opcode is preferable to adde/sube if the

/// target supports it, as the carry is a regular value rather than a
/// glue, which allows further optimisation.

It seems to be so new that I do not even see a def for them in TargTargetSelectionDAG.td. Am I missing something?

They do not look like normal nodes. They would require custom select I guess.

[vpykhtin]

LGTM.

[rampitec]

In D34300#784879, @rampitec wrote:

In D34300#784872, @arsenm wrote:

I think the right one is ADDCARRY, SUBCARRY:

The use of this opcode is preferable to adde/sube if the

/// target supports it, as the carry is a regular value rather than a
/// glue, which allows further optimisation.

It seems to be so new that I do not even see a def for them in TargTargetSelectionDAG.td. Am I missing something?

They do not look like normal nodes. They would require custom select I guess.

Looks like I can base AMDGPUadde and AMDGPUsube on these ISD opcodes instead of AMDGPUISD though. That way we will have selection working.

[rampitec]

Switched to ISD opcodes ADDCARYY/SUBCARRY and MVT::i1 instead of MVT::Glue.

[arsenm]

lib/Target/AMDGPU/AMDGPUInstrInfo.td

186

Weird that the td generic nodes don't exist already for this. Looks like this was added only in April, so you should probably add the generic addcarry/subcarry to TargetSelectionDAG.td

lib/Target/AMDGPU/SIISelLowering.cpp

476–477

ADDCARRY/SUBCARRY should be marked as legal so more combines work on them

4869

This is likely any i1 source. We have some other intrinsics that return i1 values, so maybe a todo?

[rampitec]

lib/Target/AMDGPU/AMDGPUInstrInfo.td

186

I'm not sure really. The intent is to gradually switch from addc/subc, so probably new td defs were not assumed.
I think we need to use our nodes for now and remove it in the future. I can add todo here.

lib/Target/AMDGPU/SIISelLowering.cpp

4869

I have initially tried to use it with just any i1 input. That is worse though.
In case if we have i1 argument to a function for example we would create an extra compare if I just perform it with any i1. It looks like it is only beneficial in some cases, like setcc.

[rampitec]

Made operations legal.
Added comment.

[rampitec]

lib/Target/AMDGPU/SIISelLowering.cpp

476–477

Done, but I do not see any visible difference.

[rampitec]

lib/Target/AMDGPU/AMDGPUInstrInfo.td

186

I have created D34423 to add addcarry and subcarry nodes.
Let's see how it goes, and it will be trivial to replace what I have defined here with those if submitted. Meanwhile I guess that is not a blocker for this change.

lib/Target/AMDGPU/AMDGPUInstrInfo.td

 def AMDGPUIfBreakOp : SDTypeProfile<1, 2,
   [SDTCisVT<0, i64>, SDTCisVT<1, i1>, SDTCisVT<2, i64>]
 >;
 
 def AMDGPUElseBreakOp : SDTypeProfile<1, 2,
   [SDTCisVT<0, i64>, SDTCisVT<1, i64>, SDTCisVT<2, i64>]
 >;
 
+def AMDGPUAddeSubeOp : SDTypeProfile<2, 3,
+  [SDTCisSameAs<0, 2>, SDTCisSameAs<0, 3>, SDTCisVT<0, i32>, SDTCisVT<1, i1>, SDTCisVT<4, i1>]
+>;
+
 //===----------------------------------------------------------------------===//
 // AMDGPU DAG Nodes
 //
 
 def AMDGPUif : SDNode<"AMDGPUISD::IF", AMDGPUIfOp, [SDNPHasChain]>;
 def AMDGPUelse : SDNode<"AMDGPUISD::ELSE", AMDGPUElseOp, [SDNPHasChain]>;
 def AMDGPUloop : SDNode<"AMDGPUISD::LOOP", AMDGPULoopOp, [SDNPHasChain]>;
 

 >;
 
 // out = (src0 + src1 > 0xFFFFFFFF) ? 1 : 0
 def AMDGPUcarry : SDNode<"AMDGPUISD::CARRY", SDTIntBinOp, []>;
 
 // out = (src1 > src0) ? 1 : 0
 def AMDGPUborrow : SDNode<"AMDGPUISD::BORROW", SDTIntBinOp, []>;
 
+// TODO: remove AMDGPUadde/AMDGPUsube when ADDCARRY/SUBCARRY get their own
+// nodes in TargetSelectionDAG.td.
+def AMDGPUadde : SDNode<"ISD::ADDCARRY", AMDGPUAddeSubeOp, []>;
+
+def AMDGPUsube : SDNode<"ISD::SUBCARRY", AMDGPUAddeSubeOp, []>;
+
 def AMDGPUSetCCOp : SDTypeProfile<1, 3, [        // setcc
   SDTCisVT<0, i64>, SDTCisSameAs<1, 2>, SDTCisVT<3, OtherVT>
 ]>;
 
 def AMDGPUsetcc : SDNode<"AMDGPUISD::SETCC", AMDGPUSetCCOp>;
 
 def AMDGPUSetRegOp :  SDTypeProfile<0, 2, [
   SDTCisInt<0>, SDTCisInt<1>

lib/Target/AMDGPU/SIISelLowering.h

SDValue performIntMed3ImmCombine(SelectionDAG &DAG, const SDLoc &SL,
                                    SDValue Op0, SDValue Op1, bool Signed) const;
   SDValue performMinMaxCombine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performFMed3Combine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performCvtPkRTZCombine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performExtractVectorEltCombine(SDNode *N, DAGCombinerInfo &DCI) const;
 
   unsigned getFusedOpcode(const SelectionDAG &DAG,
                           const SDNode *N0, const SDNode *N1) const;
+  SDValue performAddCombine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performFAddCombine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performFSubCombine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performSetCCCombine(SDNode *N, DAGCombinerInfo &DCI) const;
   SDValue performCvtF32UByteNCombine(SDNode *N, DAGCombinerInfo &DCI) const;
 
   bool isLegalFlatAddressingMode(const AddrMode &AM) const;
   bool isLegalMUBUFAddressingMode(const AddrMode &AM) const;
 

lib/Target/AMDGPU/SIISelLowering.cpp

SITargetLowering::SITargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::BR_CC, MVT::i32, Expand);
   setOperationAction(ISD::BR_CC, MVT::i64, Expand);
   setOperationAction(ISD::BR_CC, MVT::f32, Expand);
   setOperationAction(ISD::BR_CC, MVT::f64, Expand);
 
   setOperationAction(ISD::UADDO, MVT::i32, Legal);
   setOperationAction(ISD::USUBO, MVT::i32, Legal);
 
+  setOperationAction(ISD::ADDCARRY, MVT::i32, Legal);
+  setOperationAction(ISD::SUBCARRY, MVT::i32, Legal);
+
   // We only support LOAD/STORE and vector manipulation ops for vectors
   // with > 4 elements.
   for (MVT VT : {MVT::v8i32, MVT::v8f32, MVT::v16i32, MVT::v16f32,
         MVT::v2i64, MVT::v2f64}) {
     for (unsigned Op = 0; Op < ISD::BUILTIN_OP_END; ++Op) {
       switch (Op) {
       case ISD::LOAD:
       case ISD::STORE:
SITargetLowering::SITargetLowering(const TargetMachine &TM,
   } else {
     setOperationAction(ISD::SELECT, MVT::v2i16, Custom);
     setOperationAction(ISD::SELECT, MVT::v2f16, Custom);
   }
 
   for (MVT VT : { MVT::v4i16, MVT::v4f16, MVT::v2i8, MVT::v4i8, MVT::v8i8 }) {
     setOperationAction(ISD::SELECT, VT, Custom);
   }
 
+  setTargetDAGCombine(ISD::ADD);
   setTargetDAGCombine(ISD::FADD);
   setTargetDAGCombine(ISD::FSUB);
   setTargetDAGCombine(ISD::FMINNUM);
   setTargetDAGCombine(ISD::FMAXNUM);
   setTargetDAGCombine(ISD::SMIN);
   setTargetDAGCombine(ISD::SMAX);
   setTargetDAGCombine(ISD::UMIN);
   setTargetDAGCombine(ISD::UMAX);
if ((Options.AllowFPOpFusion == FPOpFusion::Fast || Options.UnsafeFPMath ||
         N1->getFlags().hasUnsafeAlgebra())) &&
       isFMAFasterThanFMulAndFAdd(VT)) {
     return ISD::FMA;
   }
 
   return 0;
 }
 
+SDValue SITargetLowering::performAddCombine(SDNode *N,
+                                            DAGCombinerInfo &DCI) const {
+  SelectionDAG &DAG = DCI.DAG;
+  EVT VT = N->getValueType(0);
+
+  if (VT != MVT::i32)
+    return SDValue();
+
+  SDLoc SL(N);
+  SDValue LHS = N->getOperand(0);
+  SDValue RHS = N->getOperand(1);
+
+  // add x, zext (setcc) => addcarry x, 0, setcc
+  // add x, sext (setcc) => subcarry x, 0, setcc
+  unsigned Opc = LHS.getOpcode();
+  if (Opc == ISD::ZERO_EXTEND || Opc == ISD::SIGN_EXTEND ||
+      Opc == ISD::ANY_EXTEND)
+    std::swap(RHS, LHS);
+
+  Opc = RHS.getOpcode();
+  if (Opc == ISD::ZERO_EXTEND || Opc == ISD::SIGN_EXTEND ||
+      Opc == ISD::ANY_EXTEND) {
+    auto Cond = RHS.getOperand(0);
+    if (Cond.getOpcode() == ISD::SETCC) {
+      SDVTList VTList = DAG.getVTList(MVT::i32, MVT::i1);
+      SDValue Args[] = { LHS, DAG.getConstant(0, SL, MVT::i32), Cond };
+      Opc = (Opc == ISD::SIGN_EXTEND) ? ISD::SUBCARRY : ISD::ADDCARRY;
+      return DAG.getNode(Opc, SL, VTList, Args);
+    }
+  }
+  return SDValue();
+}
+
 SDValue SITargetLowering::performFAddCombine(SDNode *N,
                                              DAGCombinerInfo &DCI) const {
   if (DCI.getDAGCombineLevel() < AfterLegalizeDAG)
     return SDValue();
 
   SelectionDAG &DAG = DCI.DAG;
   EVT VT = N->getValueType(0);
 
SDValue SITargetLowering::performCvtF32UByteNCombine(SDNode *N,
   return SDValue();
 }
 
 SDValue SITargetLowering::PerformDAGCombine(SDNode *N,
                                             DAGCombinerInfo &DCI) const {
   switch (N->getOpcode()) {
   default:
     return AMDGPUTargetLowering::PerformDAGCombine(N, DCI);
+  case ISD::ADD:
+    return performAddCombine(N, DCI);
   case ISD::FADD:
     return performFAddCombine(N, DCI);
   case ISD::FSUB:
     return performFSubCombine(N, DCI);
   case ISD::SETCC:
     return performSetCCCombine(N, DCI);
   case ISD::FMAXNUM:
   case ISD::FMINNUM:

lib/Target/AMDGPU/VOP2Instructions.td

 defm V_CVT_PKNORM_I16_F32 : VOP2Inst <"v_cvt_pknorm_i16_f32", VOP_I32_F32_F32>;
 defm V_CVT_PKNORM_U16_F32 : VOP2Inst <"v_cvt_pknorm_u16_f32", VOP_I32_F32_F32>;
 defm V_CVT_PKRTZ_F16_F32 : VOP2Inst <"v_cvt_pkrtz_f16_f32", VOP_I32_F32_F32, AMDGPUpkrtz_f16_f32>;
 defm V_CVT_PK_U16_U32 : VOP2Inst <"v_cvt_pk_u16_u32", VOP_I32_I32_I32>;
 defm V_CVT_PK_I16_I32 : VOP2Inst <"v_cvt_pk_i16_i32", VOP_I32_I32_I32>;
 
 } // End SubtargetPredicate = isGCN
 
+def : Pat<
+    (AMDGPUadde i32:$src0, i32:$src1, i1:$src2),
+    (V_ADDC_U32_e64 $src0, $src1, $src2)
+>;
+
+def : Pat<
+    (AMDGPUsube i32:$src0, i32:$src1, i1:$src2),
+    (V_SUBB_U32_e64 $src0, $src1, $src2)
+>;
 
 // These instructions only exist on SI and CI
 let SubtargetPredicate = isSICI in {
 
 defm V_MIN_LEGACY_F32 : VOP2Inst <"v_min_legacy_f32", VOP_F32_F32_F32, AMDGPUfmin_legacy>;
 defm V_MAX_LEGACY_F32 : VOP2Inst <"v_max_legacy_f32", VOP_F32_F32_F32, AMDGPUfmax_legacy>;
 
 let isCommutable = 1 in {

test/CodeGen/AMDGPU/combine-cond-add-sub.ll

+; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
+
+; GCN-LABEL: {{^}}add1:
+; GCN: v_cmp_gt_u32_e{{32|64}} [[CC:[^,]+]], v{{[0-9]+}}, v{{[0-9]+}}
+; GCN: v_addc_u32_e{{32|64}} v{{[0-9]+}}, {{[^,]+}}, 0, v{{[0-9]+}}, [[CC]]
+; GCN-NOT: v_cndmask
+
+define amdgpu_kernel void @add1(i32 addrspace(1)* nocapture %arg) {
+bb:
+  %x = tail call i32 @llvm.amdgcn.workitem.id.x()
+  %y = tail call i32 @llvm.amdgcn.workitem.id.y()
+  %gep = getelementptr inbounds i32, i32 addrspace(1)* %arg, i32 %x
+  %v = load i32, i32 addrspace(1)* %gep, align 4
+  %cmp = icmp ugt i32 %x, %y
+  %ext = zext i1 %cmp to i32
+  %add = add i32 %v, %ext
+  store i32 %add, i32 addrspace(1)* %gep, align 4
+  ret void
+}
+
+; GCN-LABEL: {{^}}sub1:
+; GCN: v_cmp_gt_u32_e{{32|64}} [[CC:[^,]+]], v{{[0-9]+}}, v{{[0-9]+}}
+; GCN: v_subb_u32_e{{32|64}} v{{[0-9]+}}, {{[^,]+}}, v{{[0-9]+}}, 0, [[CC]]
+; GCN-NOT: v_cndmask
+
+define amdgpu_kernel void @sub1(i32 addrspace(1)* nocapture %arg) {
+bb:
+  %x = tail call i32 @llvm.amdgcn.workitem.id.x()
+  %y = tail call i32 @llvm.amdgcn.workitem.id.y()
+  %gep = getelementptr inbounds i32, i32 addrspace(1)* %arg, i32 %x
+  %v = load i32, i32 addrspace(1)* %gep, align 4
+  %cmp = icmp ugt i32 %x, %y
+  %ext = sext i1 %cmp to i32
+  %add = add i32 %v, %ext
+  store i32 %add, i32 addrspace(1)* %gep, align 4
+  ret void
+}
+
+declare i32 @llvm.amdgcn.workitem.id.x() #0
+
+declare i32 @llvm.amdgcn.workitem.id.y() #0
+
+attributes #0 = { nounwind readnone speculatable }