[SelectionDAG] Expand ADD/SUBCARRY

[leonardchan]

Summary

This patch allows for expansion of ADDCARRY and SUBCARRY when the target does not support it.

[efriedma]

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3300

Are you sure this is right? The comment is correct, but there's only an overflow if the carry is set and the result is zero.

[leonardchan]

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3300

My bad, you're right. Updated.

[efriedma]

LGTM

Please run some basic sanity tests before you merge to make sure this works correctly at runtime. The code looks right, but I don't really trust that. :) If you want to test something simpler than smul.fix, might make sense to just temporarily hack legalization for addition to use this codepath, or something like that, so you can easily understand what you're actually testing.

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3300

Looks okay now.

[leonardchan]

In D61411#1487156, @efriedma wrote:

LGTM

Please run some basic sanity tests before you merge to make sure this works correctly at runtime. The code looks right, but I don't really trust that. :) If you want to test something simpler than smul.fix, might make sense to just temporarily hack legalization for addition to use this codepath, or something like that, so you can easily understand what you're actually testing.

Good thing I checked! I did as you suggested by forcing 32bit x86 to take this path and found a bunch of type mismatches. After fixing that, everything looks good for expected results. Will submit tomorrow morning if there aren't any more comments then.

[jyknight]

llvm/test/CodeGen/SPARC/addcarry.ll

2 ↗

(On Diff #197702)

SPARC is probably not a great example, because it can support ADDCARRY fine, only nobody implemented it yet (just the deprecated ADDC/ADDE). RISCV would be a better test-case, because it actually doesn't have an overflow flag at all.

[efriedma]

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3292

Looking at this again, it isn't quite right. In general, on targets where getBooleanContents does not return ZeroOrOneBooleanContent, you need to getZeroExtendInReg to convert a carry bit to 1/0.

[leonardchan]

llvm/test/CodeGen/SPARC/addcarry.ll

2 ↗

(On Diff #197702)

So I'm having trouble figuring out how to properly test this since RISCV also doesn't seem to support the MUL_LOHI ISDs and I don't know other ways to invoke usage of ISD::ADDCARRY other than through expandMUL_LOHI.

Do you think it would be fine if I also added an intrinsic like llvm.addcarry for explicitly expanding to ISD::ADDCARRY so I could test this directly?

[efriedma]

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3292

I think you need both the getZExtOrTrunc to fix the type, and the getZeroExtendInReg to fix the value. (getZeroExtendInReg just produces an ISD::AND.)

[efriedma]

llvm/test/CodeGen/SPARC/addcarry.ll

2 ↗

(On Diff #197702)

Try "llc -mtriple=riscv32 -mattr=+m"?

[leonardchan]

llvm/test/CodeGen/SPARC/addcarry.ll

2 ↗

(On Diff #197702)

This works well. Didn't know about this beforehand. Thanks.

[efriedma]

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3293

The VT argument for getZeroExtendInReg is the mask, so should be MVT::i1. The way it's written, the getZeroExtendInReg does nothing.

[leonardchan]

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3293

Updated

[efriedma]

LGTM with a minor comment.

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3312

Shouldn't matter in practice, but the second type passed to getBoolExtOrTrunc is supposed to be the type of the operation ("VT").

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

bool SelectionDAGLegalize::ExpandNode(SDNode *Node) {
   case ISD::SSUBSAT:
   case ISD::USUBSAT:
     Results.push_back(TLI.expandAddSubSat(Node, DAG));
     break;
   case ISD::SMULFIX:
   case ISD::UMULFIX:
     Results.push_back(TLI.expandFixedPointMul(Node, DAG));
     break;
+  case ISD::ADDCARRY:
+  case ISD::SUBCARRY: {
+    SDValue LHS = Node->getOperand(0);
+    SDValue RHS = Node->getOperand(1);
+    SDValue Carry = Node->getOperand(2);
+
+    bool IsAdd = Node->getOpcode() == ISD::ADDCARRY;
+
+    // Initial add of the 2 operands.
+    unsigned Op = IsAdd ? ISD::ADD : ISD::SUB;
+    EVT VT = LHS.getValueType();
+    SDValue Sum = DAG.getNode(Op, dl, VT, LHS, RHS);
+
+    // Initial check for overflow.
+    EVT CarryType = Node->getValueType(1);
+    EVT SetCCType = getSetCCResultType(Node->getValueType(0));
+    ISD::CondCode CC = IsAdd ? ISD::SETULT : ISD::SETUGT;
+    SDValue Overflow = DAG.getSetCC(dl, SetCCType, Sum, LHS, CC);
+
+    // Add of the sum and the carry.
+    SDValue CarryExt =
+        DAG.getZeroExtendInReg(DAG.getZExtOrTrunc(Carry, dl, VT), dl, MVT::i1);
+    SDValue Sum2 = DAG.getNode(Op, dl, VT, Sum, CarryExt);
+
+    // Second check for overflow. If we are adding, we can only overflow if the
+    // initial sum is all 1s ang the carry is set, resulting in a new sum of 0.
+    // If we are subtracting, we can only overflow if the initial sum is 0 and
+    // the carry is set, resulting in a new sum of all 1s.
+    SDValue Zero = DAG.getConstant(0, dl, VT);
+    SDValue Overflow2 =
+        IsAdd ? DAG.getSetCC(dl, SetCCType, Sum2, Zero, ISD::SETEQ)
+              : DAG.getSetCC(dl, SetCCType, Sum, Zero, ISD::SETEQ);
+    Overflow2 = DAG.getNode(ISD::AND, dl, SetCCType, Overflow2,
+                            DAG.getZExtOrTrunc(Carry, dl, SetCCType));
+
+    SDValue ResultCarry =
+        DAG.getNode(ISD::OR, dl, SetCCType, Overflow, Overflow2);
+
+    Results.push_back(Sum2);
+    Results.push_back(
+        DAG.getBoolExtOrTrunc(ResultCarry, dl, CarryType, CarryType));
+    break;
+  }
   case ISD::SADDO:
   case ISD::SSUBO: {
     SDValue LHS = Node->getOperand(0);
     SDValue RHS = Node->getOperand(1);
     bool IsAdd = Node->getOpcode() == ISD::SADDO;
 
     SDValue Sum = DAG.getNode(IsAdd ? ISD::ADD : ISD::SUB, dl,
                               LHS.getValueType(), LHS, RHS);

llvm/test/CodeGen/RISCV/addcarry.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=riscv32 -mattr=+m | FileCheck %s --check-prefix=RISCV32
+
+; Test ADDCARRY node expansion on a target that does not currently support ADDCARRY.
+; Signed fixed point multiplication eventually expands down to an ADDCARRY.
+
+declare  i64 @llvm.smul.fix.i64  (i64, i64, i32)
+
+define i64 @addcarry(i64 %x, i64 %y) {
+; RISCV32-LABEL: addcarry:
+; RISCV32:       # %bb.0:
+; RISCV32-NEXT:    mul a4, a0, a3
+; RISCV32-NEXT:    mulhu a5, a0, a2
+; RISCV32-NEXT:    add a4, a5, a4
+; RISCV32-NEXT:    sltu a6, a4, a5
+; RISCV32-NEXT:    mulhu a5, a0, a3
+; RISCV32-NEXT:    add a6, a5, a6
+; RISCV32-NEXT:    mulhu a5, a1, a2
+; RISCV32-NEXT:    add a7, a6, a5
+; RISCV32-NEXT:    mul a5, a1, a2
+; RISCV32-NEXT:    add a6, a4, a5
+; RISCV32-NEXT:    sltu a4, a6, a4
+; RISCV32-NEXT:    add a4, a7, a4
+; RISCV32-NEXT:    mul a5, a1, a3
+; RISCV32-NEXT:    add a5, a4, a5
+; RISCV32-NEXT:    bgez a1, .LBB0_2
+; RISCV32-NEXT:  # %bb.1:
+; RISCV32-NEXT:    sub a5, a5, a2
+; RISCV32-NEXT:  .LBB0_2:
+; RISCV32-NEXT:    bgez a3, .LBB0_4
+; RISCV32-NEXT:  # %bb.3:
+; RISCV32-NEXT:    sub a5, a5, a0
+; RISCV32-NEXT:  .LBB0_4:
+; RISCV32-NEXT:    mul a0, a0, a2
+; RISCV32-NEXT:    srli a0, a0, 2
+; RISCV32-NEXT:    slli a1, a6, 30
+; RISCV32-NEXT:    or a0, a0, a1
+; RISCV32-NEXT:    srli a1, a6, 2
+; RISCV32-NEXT:    slli a2, a5, 30
+; RISCV32-NEXT:    or a1, a1, a2
+; RISCV32-NEXT:    ret
+  %tmp = call i64 @llvm.smul.fix.i64(i64 %x, i64 %y, i32 2);
+  ret i64 %tmp;
+}