[Intrinsic] Signed Saturation Addition Intrinsic

[leonardchan]

Summary

Add an intrinsic that takes 2 integers and perform saturation addition on them.

This is a part of implementing fixed point arithmetic in clang where some of the more complex operations will be implemented as intrinsics.

[craig.topper]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

540

This doesn't seem right. Let's say the input was an i8 SATSADD that should have returned [-128,127] with no wrap around. Let's say the type to promote to i16. This becomes two sign_extend_inreg from i8 to i16 and an an i16 SATSADD, but that will only saturate when the math overflows 16 bits. So it's not longer saturating to [-128,127]. You get can [-256,254] now.

lib/CodeGen/TargetLoweringBase.cpp

1874

What about vector types?

1886

getSetCCResultType takes the type of the input to the setcc and returns the type that should be used for its output. So MVT::i1 here should LHS.getValueType()

[ebevhan]

include/llvm/CodeGen/ISDOpcodes.h

265

This is a nitpick but I think it would be better if it were named SADDSAT to match the naming of the other nodes (SADDO, SMULO for example).

include/llvm/CodeGen/TargetLowering.h

824

The thing with saturating addition (and subtraction) is that the saturation bitwidth is determined by the width of the type itself anyway, so I don't think there's a need for a hook for it.

You only need a hook if the legality needs to be predicated on something other than the result and operand type.

include/llvm/IR/Intrinsics.td

708

Same naming scheme point here, to match the overflow intrinsics it should probably be int_sadd_sat or similar.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

540

I think a more correct result could be obtained for iN to iM by doing ANY_EXTEND to iM->LSHR by M-N->SATSADD->ASHR M-N. I'm not sure if this is the best way, though.

lib/CodeGen/TargetLoweringBase.cpp

1883

Would there be a benefit to using SADDO here if it's legal? Minimum saturation occurs if Overflow && Sum > 0 and maximum saturation if Overflow && Sum < 0.

It really depends on whether or not the target can chain the operations effectively, but I suspect that most targets won't be able to keep the overflow flag alive without materializing it.

[craig.topper]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

540

Should LSHR be SHL?

[ebevhan]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

540

Oh, whoops. Yes, it should be SHL.

[leonardchan]

lib/CodeGen/TargetLoweringBase.cpp

1883

I'm running into legality issues when type expansion is involved. I was able to replace this block to use SADDO but ran into an error saying the SADDO node was not expanded when legalizing types. I'm not sure if I should call another function to "force check" expansion on my newly created SADDO node, but I couldn't find any other examples that show usage of SADDO during expansion.

Alternatively, I could move the code for expanding SADDO into its own method that I could call from here.

[ebevhan]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

550

If I understand correctly, Op1Promoted and Op2Promoted are already any-extended to the wider type: "The low bits of the promoted value corresponding to the original type are exactly equal to Op." and "The extra bits contain rubbish". So there shouldn't be a need for an explicit ANY_EXTEND after.

3008

Seems like this snuck in.

lib/CodeGen/SelectionDAG/LegalizeTypes.h

418

Should be named SADDSAT.

lib/CodeGen/TargetLoweringBase.cpp

1883

Odd... It looks to me like expanding SADDO during type legalization should work fine. I was really just curious to see if it produced better code for the legal type case than expanding outright. Maybe someone else knows more about why it doesn't want to work.

If it's just a problem during type expansion you could always check if the type is legal, and if so, use SADDO. But supporting both SADDO and the full expansion seems like overkill.

[leonardchan]

lib/CodeGen/TargetLoweringBase.cpp

1883

I don't know what happened or what got fixed, but I'm able to use SADDO now for some reason :p. And the generated code is shorter now in the tests.

[ebevhan]

Looks good to me!

Though, I just realized that I think you need to add the new node to TargetSelectionDAG.td. Unsure if it needs to be added somewhere else as well.

[bjope]

include/llvm/IR/Intrinsics.td

707

This is also Commutative afaict.

[craig.topper]

Are we not supporting vectors at all? That needs to be checked in the IR verifier if so. Though I would really like to see this for vectors since X86 has 8 and 16 bit saturating vector addition.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

554

What about vector types?

[bjope]

lib/CodeGen/TargetLoweringBase.cpp

1890

Maybe I miss something, but shouldn't it be SETGE here?
Assume that we have and SADDSAT(SignedMin, SignedMin). Then we overflow, and the result it zero. But we should still saturate to SignedMin.

[leonardchan]

In D53053#1263049, @craig.topper wrote:

Are we not supporting vectors at all? That needs to be checked in the IR verifier if so. Though I would really like to see this for vectors since X86 has 8 and 16 bit saturating vector addition.

We can add them. Not sure if what I added is the correct way they should be expanded though. I might just not be looking hard enough, but I couldn't find other examples of intrinsics that take int vector arguments and expand them.

lib/CodeGen/TargetLoweringBase.cpp

1890

You're right. It should be.

[craig.topper]

Intrinsics with vector operands are expanded in LegalizeVectorOps.cpp. Sometimes with a vectorized sequence or in the worst case by unrolling.

[leonardchan]

In D53053#1263960, @craig.topper wrote:

Intrinsics with vector operands are expanded in LegalizeVectorOps.cpp. Sometimes with a vectorized sequence or in the worst case by unrolling.

Added the appropriate case in LegalizeVectorOps. This should eventually allow the node to be unrolled in Expand, which I think does the same thing I had before in a previous diff of this patch.

[craig.topper]

lib/CodeGen/TargetLoweringBase.cpp

1895

What if we did the selects like this? Then we don't need any ANDs and we only need one setcc.

overflow ? (sum < 0 ? satmax : satmin) : sum

[craig.topper]

lib/CodeGen/TargetLoweringBase.cpp

1862

This should be in TargetLowering.cpp with expandMUL_LOHI, expandMUL, etc. Not TargetLoweringBase.

[craig.topper]

test/CodeGen/X86/sadd_sat.ll

3

Use -mtriple=i686-- not -march. And generate the checks using utils/update_llc_test_checks.py

[craig.topper]

test/CodeGen/X86/sadd_sat.ll

3

It might also be better to add -mattr=cmov on the 32-bit test

[leonardchan]

test/CodeGen/X86/sadd_sat.ll

3

This is a very nifty script!

[craig.topper]

When can we expect a signed subtraction intrinsic?

[leonardchan]

In D53053#1276254, @craig.topper wrote:

When can we expect a signed subtraction intrinsic?

Was going to work on that within the next few days. Right now I'm working on finishing up for a clang patch that uses these add intrinsics for fixed point addition.

[JosephTremoulet]

I don't see this or its unsigned counterpart added to the LangRef; is that intentional, or an oversight?

[leonardchan]

I forgot to add it but will add it on my to-do list.

[leonardchan]

@JosephTremoulet Made a patch for the documentation (https://reviews.llvm.org/D54729)

include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
     SADDO, UADDO,
 
     /// Same for subtraction.
     SSUBO, USUBO,
 
     /// Same for multiplication.
     SMULO, UMULO,
 
+    /// RESULT = SADDSAT(LHS, RHS) - Perform signed saturation addition on 2
+    /// integers with the same bit width (W). If the true value of LHS + RHS
+    /// exceeds the largest signed value that can be represented by W bits, the
+    /// resulting value is this maximum value. Otherwise, if this value is less
+    /// than the smallest signed value that can be represented by W bits, the
+    /// resulting value is this minimum value.
+    SADDSAT,
+
     /// Simple binary floating point operators.
     FADD, FSUB, FMUL, FDIV, FREM,
 
     /// Constrained versions of the binary floating point operators.
     /// These will be lowered to the simple operators before final selection.
     /// They are used to limit optimizations while the DAG is being
     /// optimized.
     STRICT_FADD, STRICT_FSUB, STRICT_FMUL, STRICT_FDIV, STRICT_FREM,

include/llvm/CodeGen/TargetLowering.h

public:
   LegalizeAction getOperationAction(unsigned Op, EVT VT) const {
     if (VT.isExtended()) return Expand;
     // If a target-specific SDNode requires legalization, require the target
     // to provide custom legalization for it.
     if (Op >= array_lengthof(OpActions[0])) return Custom;
     return OpActions[(unsigned)VT.getSimpleVT().SimpleTy][Op];
   }
 
+  /// Method for building the DAG expansion of ISD::SADDSAT.
+  SDValue getExpandedSignedSaturationAddition(SDNode *Node,
+                                              SelectionDAG &DAG) const;
+
   LegalizeAction getStrictFPOperationAction(unsigned Op, EVT VT) const {
     unsigned EqOpc;
     switch (Op) {
       default: llvm_unreachable("Unexpected FP pseudo-opcode");
       case ISD::STRICT_FADD: EqOpc = ISD::FADD; break;
       case ISD::STRICT_FSUB: EqOpc = ISD::FSUB; break;
       case ISD::STRICT_FMUL: EqOpc = ISD::FMUL; break;
       case ISD::STRICT_FDIV: EqOpc = ISD::FDIV; break;
       case ISD::STRICT_FREM: EqOpc = ISD::FREM; break;
       case ISD::STRICT_FSQRT: EqOpc = ISD::FSQRT; break;
       case ISD::STRICT_FPOW: EqOpc = ISD::FPOW; break;
       case ISD::STRICT_FPOWI: EqOpc = ISD::FPOWI; break;
       case ISD::STRICT_FMA: EqOpc = ISD::FMA; break;
       case ISD::STRICT_FSIN: EqOpc = ISD::FSIN; break;
       case ISD::STRICT_FCOS: EqOpc = ISD::FCOS; break;
       case ISD::STRICT_FEXP: EqOpc = ISD::FEXP; break;
       case ISD::STRICT_FEXP2: EqOpc = ISD::FEXP2; break;
       case ISD::STRICT_FLOG: EqOpc = ISD::FLOG; break;
       case ISD::STRICT_FLOG10: EqOpc = ISD::FLOG10; break;
       case ISD::STRICT_FLOG2: EqOpc = ISD::FLOG2; break;
       case ISD::STRICT_FRINT: EqOpc = ISD::FRINT; break;
       case ISD::STRICT_FNEARBYINT: EqOpc = ISD::FNEARBYINT; break;
     }
 
     auto Action = getOperationAction(EqOpc, VT);
 
     // We don't currently handle Custom or Promote for strict FP pseudo-ops.
     // For now, we just expand for those cases.
     if (Action != Legal)

include/llvm/IR/Intrinsics.td

 
 def int_smul_with_overflow : Intrinsic<[llvm_anyint_ty, llvm_i1_ty],
                                        [LLVMMatchType<0>, LLVMMatchType<0>],
                                        [IntrNoMem, IntrSpeculatable]>;
 def int_umul_with_overflow : Intrinsic<[llvm_anyint_ty, llvm_i1_ty],
                                        [LLVMMatchType<0>, LLVMMatchType<0>],
                                        [IntrNoMem, IntrSpeculatable]>;
 
+//===------------------------- Fixed Point Intrinsics ---------------------===//
+//
+def int_sadd_sat : Intrinsic<[llvm_anyint_ty],
+                             [LLVMMatchType<0>, LLVMMatchType<0>],
+                             [IntrNoMem, IntrSpeculatable]>;
+
 //===------------------------- Memory Use Markers -------------------------===//
 //
 def int_lifetime_start  : Intrinsic<[],
                                     [llvm_i64_ty, llvm_anyptr_ty],
                                     [IntrArgMemOnly, NoCapture<1>]>;
 def int_lifetime_end    : Intrinsic<[],
                                     [llvm_i64_ty, llvm_anyptr_ty],
                                     [IntrArgMemOnly, NoCapture<1>]>;

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

#endif
   case ISD::STRICT_FNEARBYINT:
     // These pseudo-ops get legalized as if they were their non-strict
     // equivalent.  For instance, if ISD::FSQRT is legal then ISD::STRICT_FSQRT
     // is also legal, but if ISD::FSQRT requires expansion then so does
     // ISD::STRICT_FSQRT.
     Action = TLI.getStrictFPOperationAction(Node->getOpcode(),
                                             Node->getValueType(0));
     break;
+  case ISD::SADDSAT: {
+    Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
+    break;
+  }
   case ISD::MSCATTER:
     Action = TLI.getOperationAction(Node->getOpcode(),
                     cast<MaskedScatterSDNode>(Node)->getValue().getValueType());
     break;
   case ISD::MSTORE:
     Action = TLI.getOperationAction(Node->getOpcode(),
                     cast<MaskedStoreSDNode>(Node)->getValue().getValueType());
     break;
if (TLI.isOperationLegalOrCustom(ISD::ZERO_EXTEND, VT) &&
       SDValue Shift =
           DAG.getConstant(HalfType.getSizeInBits(), dl,
                           TLI.getShiftAmountTy(HalfType, DAG.getDataLayout()));
       Hi = DAG.getNode(ISD::SHL, dl, VT, Hi, Shift);
       Results.push_back(DAG.getNode(ISD::OR, dl, VT, Lo, Hi));
     }
     break;
   }
+  case ISD::SADDSAT: {
+    Results.push_back(TLI.getExpandedSignedSaturationAddition(Node, DAG));
+    break;
+  }
   case ISD::SADDO:
   case ISD::SSUBO: {
     SDValue LHS = Node->getOperand(0);
     SDValue RHS = Node->getOperand(1);
     SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
                               ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
                               LHS, RHS);
     Results.push_back(Sum);

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

#endif
   case ISD::UADDO:
   case ISD::USUBO:       Res = PromoteIntRes_UADDSUBO(N, ResNo); break;
   case ISD::SMULO:
   case ISD::UMULO:       Res = PromoteIntRes_XMULO(N, ResNo); break;
 
   case ISD::ADDCARRY:
   case ISD::SUBCARRY:    Res = PromoteIntRes_ADDSUBCARRY(N, ResNo); break;
 
+  case ISD::SADDSAT:     Res = PromoteIntRes_SADDSAT(N); break;
+
   case ISD::ATOMIC_LOAD:
     Res = PromoteIntRes_Atomic0(cast<AtomicSDNode>(N)); break;
 
   case ISD::ATOMIC_LOAD_ADD:
   case ISD::ATOMIC_LOAD_SUB:
   case ISD::ATOMIC_LOAD_AND:
   case ISD::ATOMIC_LOAD_CLR:
   case ISD::ATOMIC_LOAD_OR:
SDValue DAGTypeLegalizer::PromoteIntRes_Overflow(SDNode *N) {
 
   // Modified the sum result - switch anything that used the old sum to use
   // the new one.
   ReplaceValueWith(SDValue(N, 0), Res);
 
   return SDValue(Res.getNode(), 1);
 }
 
+SDValue DAGTypeLegalizer::PromoteIntRes_SADDSAT(SDNode *N) {
+  // For promoting iN -> iM, this can be expanded by
+  // 1. ANY_EXTEND iN to iM
+  // 2. SHL by M-N
+  // 3. SADDSAT
+  // 4. ASHR by M-N
+  SDLoc dl(N);
+  SDValue Op1 = N->getOperand(0);
+  SDValue Op2 = N->getOperand(1);
+  unsigned OldBits = Op1.getValueSizeInBits();
+
+  SDValue Op1Promoted = GetPromotedInteger(Op1);
+  Op1Promoted =
+      DAG.getNode(ISD::ANY_EXTEND, dl, Op1Promoted.getValueType(), Op1Promoted);
+  SDValue Op2Promoted = GetPromotedInteger(Op2);
+  Op2Promoted =
+      DAG.getNode(ISD::ANY_EXTEND, dl, Op2Promoted.getValueType(), Op2Promoted);
+
+  EVT PromotedType = Op1Promoted.getValueType();
+  unsigned NewBits = Op1Promoted.getValueSizeInBits();
+  unsigned SHLAmount = NewBits - OldBits;
+  EVT SHVT = TLI.getShiftAmountTy(PromotedType, DAG.getDataLayout());
+  SDValue ShiftAmount = DAG.getConstant(SHLAmount, dl, SHVT);
+  Op1Promoted =
+      DAG.getNode(ISD::SHL, dl, PromotedType, Op1Promoted, ShiftAmount);
+  Op2Promoted =
+      DAG.getNode(ISD::SHL, dl, PromotedType, Op2Promoted, ShiftAmount);
+
+  SDValue Result =
+      DAG.getNode(ISD::SADDSAT, dl, PromotedType, Op1Promoted, Op2Promoted);
+  return DAG.getNode(ISD::SRA, dl, PromotedType, Result, ShiftAmount);
+}
+
 SDValue DAGTypeLegalizer::PromoteIntRes_SADDSUBO(SDNode *N, unsigned ResNo) {
   if (ResNo == 1)
     return PromoteIntRes_Overflow(N);
 
   // The operation overflowed iff the result in the larger type is not the
   // sign extension of its truncation to the original type.
   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
#endif
   case ISD::SRL: ExpandIntRes_Shift(N, Lo, Hi); break;
 
   case ISD::SADDO:
   case ISD::SSUBO: ExpandIntRes_SADDSUBO(N, Lo, Hi); break;
   case ISD::UADDO:
   case ISD::USUBO: ExpandIntRes_UADDSUBO(N, Lo, Hi); break;
   case ISD::UMULO:
   case ISD::SMULO: ExpandIntRes_XMULO(N, Lo, Hi); break;
+
+  case ISD::SADDSAT: ExpandIntRes_SATSADD(N, Lo, Hi); break;
   }
 
   // If Lo/Hi is null, the sub-method took care of registering results etc.
   if (Lo.getNode())
     SetExpandedInteger(SDValue(N, ResNo), Lo, Hi);
 }
 
 /// Lower an atomic node to the appropriate builtin call.
void DAGTypeLegalizer::ExpandIntRes_READCYCLECOUNTER(SDNode *N, SDValue &Lo,
   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
   SDVTList VTs = DAG.getVTList(NVT, NVT, MVT::Other);
   SDValue R = DAG.getNode(N->getOpcode(), DL, VTs, N->getOperand(0));
   Lo = R.getValue(0);
   Hi = R.getValue(1);
   ReplaceValueWith(SDValue(N, 1), R.getValue(2));
 }
 
+void DAGTypeLegalizer::ExpandIntRes_SATSADD(SDNode *N, SDValue &Lo,
+                                            SDValue &Hi) {
+  SDValue Result = TLI.getExpandedSignedSaturationAddition(N, DAG);
+  SplitInteger(Result, Lo, Hi);
+}
+
 void DAGTypeLegalizer::ExpandIntRes_SADDSUBO(SDNode *Node,
                                              SDValue &Lo, SDValue &Hi) {
   SDValue LHS = Node->getOperand(0);
   SDValue RHS = Node->getOperand(1);
   SDLoc dl(Node);
 
   // Expand the result by simply replacing it with the equivalent
   // non-overflow-checking operation.

 
 /// IntegerExpandSetCCOperands - Expand the operands of a comparison.  This code
 /// is shared among BR_CC, SELECT_CC, and SETCC handlers.
 void DAGTypeLegalizer::IntegerExpandSetCCOperands(SDValue &NewLHS,
                                                   SDValue &NewRHS,
                                                   ISD::CondCode &CCCode,
                                                   const SDLoc &dl) {
   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
+  NewLHS.dump();
   GetExpandedInteger(NewLHS, LHSLo, LHSHi);
   GetExpandedInteger(NewRHS, RHSLo, RHSHi);
 
   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
     if (RHSLo == RHSHi) {
       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) {
         if (RHSCST->isAllOnesValue()) {
           // Equality comparison to -1.

lib/CodeGen/SelectionDAG/LegalizeTypes.h

private:
   SDValue PromoteIntRes_SRA(SDNode *N);
   SDValue PromoteIntRes_SRL(SDNode *N);
   SDValue PromoteIntRes_TRUNCATE(SDNode *N);
   SDValue PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo);
   SDValue PromoteIntRes_ADDSUBCARRY(SDNode *N, unsigned ResNo);
   SDValue PromoteIntRes_UNDEF(SDNode *N);
   SDValue PromoteIntRes_VAARG(SDNode *N);
   SDValue PromoteIntRes_XMULO(SDNode *N, unsigned ResNo);
+  SDValue PromoteIntRes_SADDSAT(SDNode *N);
 
   // Integer Operand Promotion.
   bool PromoteIntegerOperand(SDNode *N, unsigned OpNo);
   SDValue PromoteIntOp_ANY_EXTEND(SDNode *N);
   SDValue PromoteIntOp_ATOMIC_STORE(AtomicSDNode *N);
   SDValue PromoteIntOp_BITCAST(SDNode *N);
   SDValue PromoteIntOp_BUILD_PAIR(SDNode *N);
   SDValue PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo);
private:
   void ExpandIntRes_UREM              (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_Shift             (SDNode *N, SDValue &Lo, SDValue &Hi);
 
   void ExpandIntRes_MINMAX            (SDNode *N, SDValue &Lo, SDValue &Hi);
 
   void ExpandIntRes_SADDSUBO          (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_UADDSUBO          (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_XMULO             (SDNode *N, SDValue &Lo, SDValue &Hi);
+  void ExpandIntRes_SATSADD           (SDNode *N, SDValue &Lo, SDValue &Hi);
 
   void ExpandIntRes_ATOMIC_LOAD       (SDNode *N, SDValue &Lo, SDValue &Hi);
 
   void ExpandShiftByConstant(SDNode *N, const APInt &Amt,
                              SDValue &Lo, SDValue &Hi);
   bool ExpandShiftWithKnownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi);
   bool ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi);
 

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

if (VT.isVector())
       CCVT = EVT::getVectorVT(*Context, CCVT, VT.getVectorNumElements());
 
     // For fshl, 0-shift returns the 1st arg (X).
     // For fshr, 0-shift returns the 2nd arg (Y).
     SDValue IsZeroShift = DAG.getSetCC(sdl, CCVT, ShAmt, Zero, ISD::SETEQ);
     setValue(&I, DAG.getSelect(sdl, VT, IsZeroShift, IsFSHL ? X : Y, Or));
     return nullptr;
   }
+  case Intrinsic::sadd_sat: {
+    SDValue Op1 = getValue(I.getArgOperand(0));
+    SDValue Op2 = getValue(I.getArgOperand(1));
+    setValue(&I, DAG.getNode(ISD::SADDSAT, sdl, Op1.getValueType(), Op1, Op2));
+    return nullptr;
+  }
   case Intrinsic::stacksave: {
     SDValue Op = getRoot();
     Res = DAG.getNode(
         ISD::STACKSAVE, sdl,
         DAG.getVTList(TLI.getPointerTy(DAG.getDataLayout()), MVT::Other), Op);
     setValue(&I, Res);
     DAG.setRoot(Res.getValue(1));
     return nullptr;

lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

#endif
   case ISD::UMULO:                      return "umulo";
   case ISD::SUBC:                       return "subc";
   case ISD::SUBE:                       return "sube";
   case ISD::SUBCARRY:                   return "subcarry";
   case ISD::SHL_PARTS:                  return "shl_parts";
   case ISD::SRA_PARTS:                  return "sra_parts";
   case ISD::SRL_PARTS:                  return "srl_parts";
 
+  case ISD::SADDSAT:                    return "saddsat";
+
   // Conversion operators.
   case ISD::SIGN_EXTEND:                return "sign_extend";
   case ISD::ZERO_EXTEND:                return "zero_extend";
   case ISD::ANY_EXTEND:                 return "any_extend";
   case ISD::SIGN_EXTEND_INREG:          return "sign_extend_inreg";
   case ISD::ANY_EXTEND_VECTOR_INREG:    return "any_extend_vector_inreg";
   case ISD::SIGN_EXTEND_VECTOR_INREG:   return "sign_extend_vector_inreg";
   case ISD::ZERO_EXTEND_VECTOR_INREG:   return "zero_extend_vector_inreg";

lib/CodeGen/TargetLoweringBase.cpp

for (MVT VT : MVT::all_valuetypes()) {
     setOperationAction(ISD::FMINNAN, VT, Expand);
     setOperationAction(ISD::FMAXNAN, VT, Expand);
     setOperationAction(ISD::FMAD, VT, Expand);
     setOperationAction(ISD::SMIN, VT, Expand);
     setOperationAction(ISD::SMAX, VT, Expand);
     setOperationAction(ISD::UMIN, VT, Expand);
     setOperationAction(ISD::UMAX, VT, Expand);
     setOperationAction(ISD::ABS, VT, Expand);
+    setOperationAction(ISD::SADDSAT, VT, Expand);
 
     // Overflow operations default to expand
     setOperationAction(ISD::SADDO, VT, Expand);
     setOperationAction(ISD::SSUBO, VT, Expand);
     setOperationAction(ISD::UADDO, VT, Expand);
     setOperationAction(ISD::USUBO, VT, Expand);
     setOperationAction(ISD::SMULO, VT, Expand);
     setOperationAction(ISD::UMULO, VT, Expand);

 int TargetLoweringBase::getDivRefinementSteps(EVT VT,
                                               MachineFunction &MF) const {
   return getOpRefinementSteps(false, VT, getRecipEstimateForFunc(MF));
 }
 
 void TargetLoweringBase::finalizeLowering(MachineFunction &MF) const {
   MF.getRegInfo().freezeReservedRegs(MF);
 }
+
+SDValue TargetLoweringBase::getExpandedSignedSaturationAddition(
+    SDNode *Node, SelectionDAG &DAG) const {
+  assert(Node->getOpcode() == ISD::SADDSAT &&
+         "Expected method to receive SADDSAT node.");
+  assert(Node->getNumOperands() == 2 &&
+         "Expected SADDSAT node to have 2 operands.");
+
+  SDLoc dl(Node);
+  SDValue LHS = Node->getOperand(0);
+  SDValue RHS = Node->getOperand(1);
+  assert(LHS.getValueType().isScalarInteger() &&
+         "Expected operands to be scalar integers in SADDSAT");
+  assert(RHS.getValueType().isScalarInteger() &&
+         "Expected operands to be scalar integers in SADDSAT");
+  unsigned BitWidth = LHS.getValueSizeInBits();
+
+  EVT ResultType = LHS.getValueType();
+  SDValue Sum = DAG.getNode(ISD::ADD, dl, ResultType, LHS, RHS);
+
+  // Compute the overflow.
+  //
+  //   SatMax -> (LHS > 0) && (RHS > 0) && (Sum < 0)
+  //   SatMin -> (LHS < 0) && (RHS < 0) && (Sum > 0)
+  //
+  SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
+  EVT BoolVT =
+      getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), MVT::i1);
+
+  SDValue LHSPos = DAG.getSetCC(dl, BoolVT, LHS, Zero, ISD::SETGT);
+  SDValue RHSPos = DAG.getSetCC(dl, BoolVT, RHS, Zero, ISD::SETGT);
+  SDValue SumPos = DAG.getSetCC(dl, BoolVT, Sum, Zero, ISD::SETGT);
+  SDValue LHSNeg = DAG.getSetCC(dl, BoolVT, LHS, Zero, ISD::SETLT);
+  SDValue RHSNeg = DAG.getSetCC(dl, BoolVT, RHS, Zero, ISD::SETLT);
+  SDValue SumNeg = DAG.getSetCC(dl, BoolVT, Sum, Zero, ISD::SETLT);
+
+  SDValue OperandsPos = DAG.getNode(ISD::AND, dl, BoolVT, LHSPos, RHSPos);
+  SDValue OperandsNeg = DAG.getNode(ISD::AND, dl, BoolVT, LHSNeg, RHSNeg);
+
+  SDValue UseSatMax = DAG.getNode(ISD::AND, dl, BoolVT, OperandsPos, SumNeg);
+  SDValue UseSatMin = DAG.getNode(ISD::AND, dl, BoolVT, OperandsNeg, SumPos);
+
+  APInt MinVal = APInt::getSignedMinValue(BitWidth);
+  APInt MaxVal = APInt::getSignedMaxValue(BitWidth);
+  SDValue SatMin = DAG.getConstant(MinVal, dl, ResultType);
+  SDValue SatMax = DAG.getConstant(MaxVal, dl, ResultType);
+
+  SDValue Result = DAG.getSelect(dl, ResultType, UseSatMax, SatMax, Sum);
+  return DAG.getSelect(dl, ResultType, UseSatMin, SatMin, Result);
+}

lib/IR/Verifier.cpp

if (CS.isCall()) {
       if (!CS.getType()->isVoidTy() && RI)
         Assert(RI->getReturnValue() == DeoptCI,
                "calls to experimental_deoptimize must be followed by a return "
                "of the value computed by experimental_deoptimize");
     }
 
     break;
   }
+  case Intrinsic::sadd_sat: {
+    Value *Op1 = CS.getArgOperand(0);
+    Value *Op2 = CS.getArgOperand(1);
+    Assert(Op1->getType()->isIntegerTy(),
+           "first operand of sadd_sat must be an int type");
+    Assert(Op2->getType()->isIntegerTy(),
+           "second operand of sadd_sat must be an int type");
+    break;
+  }
   };
 }
 
 /// Carefully grab the subprogram from a local scope.
 ///
 /// This carefully grabs the subprogram from a local scope, avoiding the
 /// built-in assertions that would typically fire.
 static DISubprogram *getSubprogram(Metadata *LocalScope) {

test/CodeGen/X86/sadd_sat.ll

+; RUN: llc < %s -mcpu=generic -mtriple=x86_64-linux | FileCheck %s
+; RUN: llc < %s -mcpu=generic -march=x86 | FileCheck %s --check-prefix=CHECK32
+
+declare  i4  @llvm.sadd.sat.i4   (i4,  i4)
+declare  i32 @llvm.sadd.sat.i32  (i32, i32)
+declare  i64 @llvm.sadd.sat.i64  (i64, i64)
+
+define i32 @func(i32 %x, i32 %y) {
+; CHECK:      func
+; CHECK:      # %bb.0:
+; CHECK-NEXT:         testl   %edi, %edi
+; CHECK-NEXT:         sets    %r8b
+; CHECK-NEXT:         setg    %cl
+; CHECK-NEXT:         testl   %esi, %esi
+; CHECK-NEXT:         sets    %dl
+; CHECK-NEXT:         setg    %al
+; CHECK-NEXT:         andb    %cl, %al
+; CHECK-NEXT:         addl    %esi, %edi
+; CHECK-NEXT:         testl   %edi, %edi
+; CHECK-NEXT:         setg    %sil
+; CHECK-NEXT:         sets    %cl
+; CHECK-NEXT:         testb   %cl, %al
+; CHECK-NEXT:         movl    $2147483647, %ecx       # imm = 0x7FFFFFFF
+; CHECK-NEXT:         cmovel  %edi, %ecx
+; CHECK-NEXT:         andb    %r8b, %dl
+; CHECK-NEXT:         testb   %sil, %dl
+; CHECK-NEXT:         movl    $-2147483648, %eax      # imm = 0x80000000
+; CHECK-NEXT:         cmovel  %ecx, %eax
+; CHECK-NEXT:         retq
+  %tmp = call i32 @llvm.sadd.sat.i32(i32 %x, i32 %y);
+  ret i32 %tmp;
+}
+
+define i64 @func2(i64 %x, i64 %y) {
+; CHECK32: func2
+; CHECK32: # %bb.0:
+; CHECK32:  pushl %ebp
+; CHECK32:  .cfi_def_cfa_offset 8
+; CHECK32:  pushl %ebx
+; CHECK32:  .cfi_def_cfa_offset 12
+; CHECK32:  pushl %edi
+; CHECK32:  .cfi_def_cfa_offset 16
+; CHECK32:  pushl %esi
+; CHECK32:  .cfi_def_cfa_offset 20
+; CHECK32:  .cfi_offset %esi, -20
+; CHECK32:  .cfi_offset %edi, -16
+; CHECK32:  .cfi_offset %ebx, -12
+; CHECK32:  .cfi_offset %ebp, -8
+; CHECK32:  movl  20(%esp), %esi
+; CHECK32:  movl  24(%esp), %edx
+; CHECK32:  movl  28(%esp), %edi
+; CHECK32:  movl  32(%esp), %eax
+; CHECK32:  movl  %edi, %ebx
+; CHECK32:  negl  %ebx
+; CHECK32:  movl  $0, %ebx
+; CHECK32:  sbbl  %eax, %ebx
+; CHECK32:  setl  %bl
+; CHECK32:  movl  %esi, %ebp
+; CHECK32:  negl  %ebp
+; CHECK32:  movl  $0, %ebp
+; CHECK32:  sbbl  %edx, %ebp
+; CHECK32:  setl  %cl
+; CHECK32:  andb  %bl, %cl
+; CHECK32:  addl  %edi, %esi
+; CHECK32:  movl  %edx, %ebx
+; CHECK32:  adcl  %eax, %ebx
+; CHECK32:  sets  %ch
+; CHECK32:  testb %ch, %cl
+; CHECK32:  movl  $2147483647, %edi       # imm = 0x7FFFFFFF
+; CHECK32:  jne .LBB1_2
+; CHECK32: # %bb.1:
+; CHECK32:  movl  %ebx, %edi
+; CHECK32: .LBB1_2:
+; CHECK32:  movl  $-1, %ebp
+; CHECK32:  jne .LBB1_4
+; CHECK32: # %bb.3:
+; CHECK32:  movl  %esi, %ebp
+; CHECK32: .LBB1_4:
+; CHECK32:  negl  %esi
+; CHECK32:  movl  $0, %ecx
+; CHECK32:  sbbl  %ebx, %ecx
+; CHECK32:  setl  %cl
+; CHECK32:  testl %eax, 24(%esp)
+; CHECK32:  sets  %dl
+; CHECK32:  testb %cl, %dl
+; CHECK32:  movl  $0, %eax
+; CHECK32:  jne .LBB1_6
+; CHECK32: # %bb.5:
+; CHECK32:  movl  %ebp, %eax
+; CHECK32: .LBB1_6:
+; CHECK32:  movl  $-2147483648, %edx      # imm = 0x80000000
+; CHECK32:  jne .LBB1_8
+; CHECK32: # %bb.7:
+; CHECK32:  movl  %edi, %edx
+; CHECK32: .LBB1_8:
+; CHECK32:  popl  %esi
+; CHECK32:  .cfi_def_cfa_offset 16
+; CHECK32:  popl  %edi
+; CHECK32:  .cfi_def_cfa_offset 12
+; CHECK32:  popl  %ebx
+; CHECK32:  .cfi_def_cfa_offset 8
+; CHECK32:  popl  %ebp
+; CHECK32:  .cfi_def_cfa_offset 4
+; CHECK32:  retl
+  %tmp = call i64 @llvm.sadd.sat.i64(i64 %x, i64 %y);
+  ret i64 %tmp;
+}
+
+define i4 @func3(i4 %x, i4 %y) {
+; CHECK: func3
+; CHECK:      # %bb.0:
+; CHECK-NEXT:         shlb    $4, %dil
+; CHECK-NEXT:         testb   %dil, %dil
+; CHECK-NEXT:         sets    %al
+; CHECK-NEXT:         setg    %cl
+; CHECK-NEXT:         shlb    $4, %sil
+; CHECK-NEXT:         testb   %sil, %sil
+; CHECK-NEXT:         sets    %r8b
+; CHECK-NEXT:         setg    %dl
+; CHECK-NEXT:         andb    %cl, %dl
+; CHECK-NEXT:         addb    %dil, %sil
+; CHECK-NEXT:         testb   %sil, %sil
+; CHECK-NEXT:         setg    %dil
+; CHECK-NEXT:         sets    %cl
+; CHECK-NEXT:         testb   %cl, %dl
+; CHECK-NEXT:         movb    $127, %dl
+; CHECK-NEXT:         jne     .LBB2_2
+; CHECK-NEXT: # %bb.1:
+; CHECK-NEXT:         movl    %esi, %edx
+; CHECK-NEXT: .LBB2_2:
+; CHECK-NEXT:         andb    %r8b, %al
+; CHECK-NEXT:         testb   %dil, %al
+; CHECK-NEXT:         movb    $-128, %al
+; CHECK-NEXT:         jne     .LBB2_4
+; CHECK-NEXT: # %bb.3:
+; CHECK-NEXT:         movl    %edx, %eax
+; CHECK-NEXT: .LBB2_4:
+; CHECK-NEXT:         sarb    $4, %al
+; CHECK-NEXT:         retq
+  %tmp = call i4 @llvm.sadd.sat.i4(i4 %x, i4 %y);
+  ret i4 %tmp;
+}