[TargetLowering] Simplify expansion of S{ADD,SUB}O

[rogfer01]

Summary

ISD::SADDO uses the suggested sequence described in the section §2.4 of the RISCV Spec v2.2. ISD::SSUBO uses the dual approach but checking for positive.

[rogfer01]

Ping?

[efriedma]

It would probably make sense to change SelectionDAGLegalize::ExpandNode to use this lowering for SADDO/SSUBO, instead of making this target-specific. The target-independent version uses approximately the same operations anyway, just in a less efficient way.

The lowering for UADDO/USUBO appears to be essentially identical to the lowering in SelectionDAGLegalize::ExpandNode, so there isn't really any point.

lib/Target/RISCV/RISCVISelLowering.cpp

553

The XOR here is a bit weird; could you just use SETGE instead?

[rogfer01]

Thanks for the review @efriedma

I'll look into making this target-independent.

[lenary]

@rogfer01 have you managed to implement this in a target-independent way?

[rogfer01]

ChangeLog:

• Remove RISC-V dependent expansions
• Simplify current target-independent expansion of S{ADD,SUB}O. Not considering U{ADD,SUB}O anymore.
• Update tests that saw codegen changes after this

For now marking this as WIP because I want to test this some more.

Also test CodeGen/AMDGPU/saddo.ll needs updating but I'm rather clueless when it comes to that target.

[RKSimon]

In D47927#1612416, @rogfer01 wrote:

Also test CodeGen/AMDGPU/saddo.ll needs updating but I'm rather clueless when it comes to that target.

I've committed rL367698 - you should be able to use the update script now

[efriedma]

The changes for vector arithmetic look nice.

llvm/test/CodeGen/RISCV/arith-with-overflow.ll

34 ↗

(On Diff #213056)

It's probably worth adding a testcase where the i1 result is used as the operand to a branch, to show we correctly fold the xor into the branch. (See also https://bugs.llvm.org/show_bug.cgi?id=42876 .)

[rogfer01]

I've committed rL367698 - you should be able to use the update script now

Thanks @RKSimon I'll update this change shortly.

[rogfer01]

ChangeLog:

• Update AMDGPU test.
• Add RISC-V tests to show that we fold the xor in the branch.

[RKSimon]

The X86 changes LGTM - does anyone else have any comments?

[RKSimon]

one minor - @efriedma / @lebedev.ri anything to add?

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

6494 ↗

(On Diff #213359)

Not sure if its necessary, but you could merge the comments and just have:

SDValue ConditionRHS = DAG.getSetCC(dl, OType, RHS, Zero, IsAdd ? ISD::SETLT : ISD::SETGT);

[lebedev.ri]

Correct in general case:

----------------------------------------
Name: sadd
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = add i8 %LHS, %RHS
  %ResultLowerThanLHS = icmp slt i8 %v0, %LHS
  %ConditionRHS = icmp slt i8 %RHS, 0
  %v1 = xor i1 %ConditionRHS, %ResultLowerThanLHS

Done: 1
Optimization is correct!

----------------------------------------
Name: ssub
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = sub i8 %LHS, %RHS
  %ResultLowerThanLHS = icmp slt i8 %v0, %LHS
  %ConditionRHS = icmp sgt i8 %RHS, 0
  %v1 = xor i1 %ConditionRHS, %ResultLowerThanLHS

Done: 1
Optimization is correct!

Invalid for undef:

----------------------------------------
Name: sadd
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = add i8 %LHS, %RHS
  %ResultLowerThanLHS = icmp slt i8 %v0, %LHS
  %ConditionRHS = icmp slt i8 %RHS, 0
  %v1 = xor i1 %ConditionRHS, %ResultLowerThanLHS

ERROR: Value mismatch for i1 %v1

Example:
i8 %LHS = #x00 (0)
i8 %RHS = undef
{i8, i1} %t = { #x00 (0), #x0 (0) }     [based on undef value]
i8 %v0 = undef
i1 %ResultLowerThanLHS = undef
i1 %ConditionRHS = undef
Source value: #x0 (0)
Target value: #x1 (1)


----------------------------------------
Name: ssub
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = sub i8 %LHS, %RHS
  %ResultLowerThanLHS = icmp slt i8 %v0, %LHS
  %ConditionRHS = icmp sgt i8 %RHS, 0
  %v1 = xor i1 %ConditionRHS, %ResultLowerThanLHS

ERROR: Value mismatch for i1 %v1

Example:
i8 %LHS = undef
i8 %RHS = #x00 (0)
{i8, i1} %t = { #x00 (0), #x0 (0) }     [based on undef value]
i8 %v0 = undef
i1 %ResultLowerThanLHS = undef
i1 %ConditionRHS = #x0 (0)
Source value: #x0 (0)
Target value: #x1 (1)

[lebedev.ri]

Though the current expansion is just as incorrect for undef:

----------------------------------------
Name: sadd
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = add i8 %LHS, %RHS
  %LHSSign = icmp sge i8 %LHS, 0
  %RHSSign = icmp sge i8 %RHS, 0
  %SignsMatch = icmp eq i1 %LHSSign, %RHSSign
  %SumSign = icmp sge i8 %v0, 0
  %SumSignNE = icmp ne i1 %LHSSign, %SumSign
  %v1 = and i1 %SignsMatch, %SumSignNE

Done: 1
Optimization is correct!

----------------------------------------
Name: ssub
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = sub i8 %LHS, %RHS
  %LHSSign = icmp sge i8 %LHS, 0
  %RHSSign = icmp sge i8 %RHS, 0
  %SignsMatch = icmp ne i1 %LHSSign, %RHSSign
  %SumSign = icmp sge i8 %v0, 0
  %SumSignNE = icmp ne i1 %LHSSign, %SumSign
  %v1 = and i1 %SignsMatch, %SumSignNE

Done: 1
Optimization is correct!

----------------------------------------
Name: sadd
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = sadd_overflow i8 %LHS, %RHS
  %v0 = add i8 %LHS, %RHS
  %LHSSign = icmp sge i8 %LHS, 0
  %RHSSign = icmp sge i8 %RHS, 0
  %SignsMatch = icmp eq i1 %LHSSign, %RHSSign
  %SumSign = icmp sge i8 %v0, 0
  %SumSignNE = icmp ne i1 %LHSSign, %SumSign
  %v1 = and i1 %SignsMatch, %SumSignNE

ERROR: Value mismatch for i1 %v1

Example:
i8 %LHS = #x00 (0)
i8 %RHS = undef
{i8, i1} %t = { #x00 (0), #x0 (0) }     [based on undef value]
i8 %v0 = undef
i1 %LHSSign = #x1 (1)
i1 %RHSSign = undef
i1 %SignsMatch = undef
i1 %SumSign = undef
i1 %SumSignNE = undef
Source value: #x0 (0)
Target value: #x1 (1)


----------------------------------------
Name: ssub
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = extractvalue {i8, i1} %t, 0
  %v1 = extractvalue {i8, i1} %t, 1
=>
  %t = ssub_overflow i8 %LHS, %RHS
  %v0 = sub i8 %LHS, %RHS
  %LHSSign = icmp sge i8 %LHS, 0
  %RHSSign = icmp sge i8 %RHS, 0
  %SignsMatch = icmp ne i1 %LHSSign, %RHSSign
  %SumSign = icmp sge i8 %v0, 0
  %SumSignNE = icmp ne i1 %LHSSign, %SumSign
  %v1 = and i1 %SignsMatch, %SumSignNE

ERROR: Value mismatch for i1 %v1

Example:
i8 %LHS = undef
i8 %RHS = #x00 (0)
{i8, i1} %t = { #x00 (0), #x0 (0) }     [based on undef value]
i8 %v0 = undef
i1 %LHSSign = undef
i1 %RHSSign = #x1 (1)
i1 %SignsMatch = undef
i1 %SumSign = undef
i1 %SumSignNE = undef
Source value: #x0 (0)
Target value: #x1 (1)

So LG i guess..

[lebedev.ri]

Hmm, while there, just to point out the obvious, the another approach here would be to teach DAGCombine/TargetLowering::SimplifySetCC() about these folds.
That is explicitly one of a few valid reasons to add optimizations into backend 'instead' of middle-end.

[rogfer01]

ChangeLog:

• Combine if-else logic.
• Adjust subtraction comment to is (non-zero) positive to avoid ambiguity.

[rogfer01]

In D47927#1621986, @lebedev.ri wrote:

Hmm, while there, just to point out the obvious, the another approach here would be to teach DAGCombine/TargetLowering::SimplifySetCC() about these folds.
That is explicitly one of a few valid reasons to add optimizations into backend 'instead' of middle-end.

Sorry, I'm not sure to understand your comment: do you mean, as an alternative, SimplifySetCC can be extended to simplify the original overflow detection?

[lebedev.ri]

In D47927#1622433, @rogfer01 wrote:

In D47927#1621986, @lebedev.ri wrote:

Hmm, while there, just to point out the obvious, the another approach here would be to teach DAGCombine/TargetLowering::SimplifySetCC() about these folds.
That is explicitly one of a few valid reasons to add optimizations into backend 'instead' of middle-end.

Sorry, I'm not sure to understand your comment: do you mean, as an alternative, SimplifySetCC can be extended to simplify the original overflow detection?

Yes

[rogfer01]

In D47927#1622957, @lebedev.ri wrote:

Yes

Thanks for the clarification Roman.

unless there is a lot of interest from others on landing this, I'll look into your suggestion first.

[nikic]

IMHO this should land as-is, and setcc folds can be implemented additionally if there are other places where they would be useful. My rationale would be that it is better to directly perform a simpler lowering than a complex lowering that then gets optimized. (Basically: If you can reduce the size of the implementing code and get a better result, then I think we should always be doing that.)

[rogfer01]

ChangeLog:

• Refresh RISC-V and X86 tests

[rogfer01]

In D47927#1652507, @nikic wrote:

IMHO this should land as-is, and setcc folds can be implemented additionally if there are other places where they would be useful. My rationale would be that it is better to directly perform a simpler lowering than a complex lowering that then gets optimized. (Basically: If you can reduce the size of the implementing code and get a better result, then I think we should always be doing that.)

Hi @nikic, thanks for your comments. It also makes sense to me to do this.

If there aren't any further comments I pland to land this in the next days.

lib/Target/RISCV/RISCVISelLowering.h

private:
   SDValue lowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerBlockAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerConstantPool(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerExternalSymbol(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerSELECT(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerVASTART(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerUADDSUBO(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerSADDSUBO(SDValue Op, SelectionDAG &DAG) const;
 
   bool IsEligibleForTailCallOptimization(CCState &CCInfo,
     CallLoweringInfo &CLI, MachineFunction &MF,
     const SmallVector<CCValAssign, 16> &ArgLocs) const;
 };
 }
 
 #endif

lib/Target/RISCV/RISCVISelLowering.cpp

RISCVTargetLowering::RISCVTargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::VASTART, MVT::Other, Custom);
   setOperationAction(ISD::VAARG, MVT::Other, Expand);
   setOperationAction(ISD::VACOPY, MVT::Other, Expand);
   setOperationAction(ISD::VAEND, MVT::Other, Expand);
 
   for (auto VT : {MVT::i1, MVT::i8, MVT::i16})
     setOperationAction(ISD::SIGN_EXTEND_INREG, VT, Expand);
 
+  setOperationAction(ISD::UADDO, XLenVT, Custom);
+  setOperationAction(ISD::USUBO, XLenVT, Custom);
+
+  setOperationAction(ISD::SADDO, XLenVT, Custom);
+  setOperationAction(ISD::SSUBO, XLenVT, Custom);
+
   if (!Subtarget.hasStdExtM()) {
     setOperationAction(ISD::MUL, XLenVT, Expand);
     setOperationAction(ISD::MULHS, XLenVT, Expand);
     setOperationAction(ISD::MULHU, XLenVT, Expand);
     setOperationAction(ISD::SDIV, XLenVT, Expand);
     setOperationAction(ISD::UDIV, XLenVT, Expand);
     setOperationAction(ISD::SREM, XLenVT, Expand);
     setOperationAction(ISD::UREM, XLenVT, Expand);
SDValue RISCVTargetLowering::LowerOperation(SDValue Op,
   case ISD::SELECT:
     return lowerSELECT(Op, DAG);
   case ISD::VASTART:
     return lowerVASTART(Op, DAG);
   case ISD::FRAMEADDR:
     return LowerFRAMEADDR(Op, DAG);
   case ISD::RETURNADDR:
     return LowerRETURNADDR(Op, DAG);
+  case ISD::UADDO:
+  case ISD::USUBO:
+    return LowerUADDSUBO(Op, DAG);
+  case ISD::SADDO:
+  case ISD::SSUBO:
+    return LowerSADDSUBO(Op, DAG);
   }
 }
 
 SDValue RISCVTargetLowering::lowerGlobalAddress(SDValue Op,
                                                 SelectionDAG &DAG) const {
   SDLoc DL(Op);
   EVT Ty = Op.getValueType();
   GlobalAddressSDNode *N = cast<GlobalAddressSDNode>(Op);
SDValue RISCVTargetLowering::LowerRETURNADDR(SDValue Op,
   }
 
   // Return the value of the return address register, marking it an implicit
   // live-in.
   unsigned Reg = MF.addLiveIn(RI.getRARegister(), getRegClassFor(XLenVT));
   return DAG.getCopyFromReg(DAG.getEntryNode(), DL, Reg, XLenVT);
 }
 
+SDValue RISCVTargetLowering::LowerUADDSUBO(SDValue Op,
+                                           SelectionDAG &DAG) const {
+  MVT XLenVT = Subtarget.getXLenVT();
+
+  SDNode *N = Op.getNode();
+
+  SDValue LHS = Op.getOperand(0);
+  SDValue RHS = Op.getOperand(1);
+
+  SDLoc DL(Op);
+
+  SDValue Result;
+  SDValue Overflow;
+
+  if (Op.getOpcode() == ISD::UADDO) {
+    Result = DAG.getNode(ISD::ADD, DL, XLenVT, LHS, RHS);
+    // There is overflow if (X + Y) < X (or Y, but no need to check both)
+    Overflow = DAG.getSetCC(DL, XLenVT, Result, LHS, ISD::SETULT);
+  } else if (Op.getOpcode() == ISD::USUBO) {
+    // There is overflow in  X - Y if X < Y
+    Result = DAG.getNode(ISD::SUB, DL, XLenVT, LHS, RHS);
+    Overflow = DAG.getSetCC(DL, XLenVT, LHS, RHS, ISD::SETULT);
+  } else
+    llvm_unreachable("Invalid opcode");
+
+  return DAG.getNode(ISD::MERGE_VALUES, DL, N->getVTList(), Result, Overflow);
+}
+
+SDValue RISCVTargetLowering::LowerSADDSUBO(SDValue Op,
+                                           SelectionDAG &DAG) const {
+  MVT XLenVT = Subtarget.getXLenVT();
+
+  SDNode *N = Op.getNode();
+
+  SDValue LHS = Op.getOperand(0);
+  SDValue RHS = Op.getOperand(1);
+
+  SDLoc DL(Op);
+
+  SDValue Result;
+  SDValue Overflow;
+
+  if (Op.getOpcode() == ISD::SADDO) {
+    Result = DAG.getNode(ISD::ADD, DL, XLenVT, LHS, RHS);
+    SDValue NegativeRHS = DAG.getSetCC(
+        DL, XLenVT, RHS, DAG.getConstant(0, DL, XLenVT), ISD::SETLT); // RHS < 0
+    SDValue ResultLowerThanLHS =
+        DAG.getSetCC(DL, XLenVT, Result, LHS, ISD::SETLT); // LHS + RHS < LHS
+    // The add should be less than one of the operands (LHS) if and only if the
+    // other operand (RHS) is negative, otherwise there will be overflow.
+    Overflow =
+        DAG.getNode(ISD::XOR, DL, XLenVT, NegativeRHS, ResultLowerThanLHS);
+  } else if (Op.getOpcode() == ISD::SSUBO) {
+    Result = DAG.getNode(ISD::SUB, DL, XLenVT, LHS, RHS);
+    SDValue PositiveRHS = DAG.getNode(
+        ISD::XOR, DL, XLenVT,
+        DAG.getSetCC(DL, XLenVT, RHS, DAG.getConstant(0, DL, XLenVT),
+                     ISD::SETLT),        // 0 < RHS
+        DAG.getConstant(1, DL, XLenVT)); // 0 >= RHS
+    // The sub should be less than one of the operands (LHS) if and only if the
+    // other operand (RHS) is positive, otherwise there will be overflow.
+    SDValue ResultLowerThanLHS =
+        DAG.getSetCC(DL, XLenVT, Result, LHS, ISD::SETLT); // LHS - RHS < LHS
+    Overflow =
+        DAG.getNode(ISD::XOR, DL, XLenVT, PositiveRHS, ResultLowerThanLHS);
+  } else
+    llvm_unreachable("Invalid opcode");
+
+  return DAG.getNode(ISD::MERGE_VALUES, DL, N->getVTList(), Result, Overflow);
+}
+
 static MachineBasicBlock *emitSplitF64Pseudo(MachineInstr &MI,
                                              MachineBasicBlock *BB) {
   assert(MI.getOpcode() == RISCV::SplitF64Pseudo && "Unexpected instruction");
 
   MachineFunction &MF = *BB->getParent();
   DebugLoc DL = MI.getDebugLoc();
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
   const TargetRegisterInfo *RI = MF.getSubtarget().getRegisterInfo();

test/CodeGen/RISCV/overflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
 ; RUN:   | FileCheck -check-prefix=RV32I %s
 
 declare {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)
 declare {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)
 declare {i32, i1} @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)
 declare {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)
 
 define i1 @sadd(i32 %a, i32 %b, i32* %c) {
 ; RV32I-LABEL: sadd:
 ; RV32I:       # %bb.0: # %entry
 ; RV32I-NEXT:    add a3, a0, a1
 ; RV32I-NEXT:    sw a3, 0(a2)
-; RV32I-NEXT:    addi a2, zero, -1
-; RV32I-NEXT:    slt a1, a2, a1
-; RV32I-NEXT:    slt a0, a2, a0
-; RV32I-NEXT:    slt a2, a2, a3
-; RV32I-NEXT:    xor a2, a0, a2
-; RV32I-NEXT:    xor a0, a0, a1
-; RV32I-NEXT:    seqz a0, a0
-; RV32I-NEXT:    snez a1, a2
-; RV32I-NEXT:    and a0, a0, a1
+; RV32I-NEXT:    slt a0, a3, a0
+; RV32I-NEXT:    slti a1, a1, 0
+; RV32I-NEXT:    xor a0, a1, a0
 ; RV32I-NEXT:    ret
 entry:
   %x = call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)
   %calc = extractvalue {i32, i1} %x, 0
   %ovf = extractvalue {i32, i1} %x, 1
   store i32 %calc, i32* %c
   ret i1 %ovf
 }
 
 define i1 @ssub(i32 %a, i32 %b, i32* %c) {
 ; RV32I-LABEL: ssub:
 ; RV32I:       # %bb.0: # %entry
 ; RV32I-NEXT:    sub a3, a0, a1
 ; RV32I-NEXT:    sw a3, 0(a2)
-; RV32I-NEXT:    addi a2, zero, -1
-; RV32I-NEXT:    slt a1, a2, a1
-; RV32I-NEXT:    slt a0, a2, a0
-; RV32I-NEXT:    slt a2, a2, a3
-; RV32I-NEXT:    xor a2, a0, a2
-; RV32I-NEXT:    xor a0, a0, a1
-; RV32I-NEXT:    snez a0, a0
-; RV32I-NEXT:    snez a1, a2
-; RV32I-NEXT:    and a0, a0, a1
+; RV32I-NEXT:    slt a0, a3, a0
+; RV32I-NEXT:    slti a1, a1, 0
+; RV32I-NEXT:    xor a0, a1, a0
+; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    ret
 entry:
   %x = call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)
   %calc = extractvalue {i32, i1} %x, 0
   %ovf = extractvalue {i32, i1} %x, 1
   store i32 %calc, i32* %c
   ret i1 %ovf
 }
entry:
   %ovf = extractvalue {i32, i1} %x, 1
   store i32 %calc, i32* %c
   ret i1 %ovf
 }
 
 define i1 @usub(i32 %a, i32 %b, i32* %c) {
 ; RV32I-LABEL: usub:
 ; RV32I:       # %bb.0: # %entry
-; RV32I-NEXT:    sub a1, a0, a1
-; RV32I-NEXT:    sw a1, 0(a2)
+; RV32I-NEXT:    sub a3, a0, a1
+; RV32I-NEXT:    sw a3, 0(a2)
 ; RV32I-NEXT:    sltu a0, a0, a1
 ; RV32I-NEXT:    ret
 entry:
   %x = call {i32, i1} @llvm.usub.with.overflow.i32(i32 %a, i32 %b)
   %calc = extractvalue {i32, i1} %x, 0
   %ovf = extractvalue {i32, i1} %x, 1
   store i32 %calc, i32* %c
   ret i1 %ovf
 }