[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 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

What about vector types?

1886 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

Should LSHR be SHL?

[ebevhan]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

540 ↗

(On Diff #168899)

Oh, whoops. Yes, it should be SHL.

[leonardchan]

lib/CodeGen/TargetLoweringBase.cpp

1883 ↗

(On Diff #168899)

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 ↗

(On Diff #169145)

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 ↗

(On Diff #169145)

Seems like this snuck in.

lib/CodeGen/SelectionDAG/LegalizeTypes.h

418 ↗

(On Diff #169145)

Should be named SADDSAT.

lib/CodeGen/TargetLoweringBase.cpp

1883 ↗

(On Diff #168899)

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 ↗

(On Diff #168899)

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 ↗

(On Diff #169303)

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 ↗

(On Diff #169303)

What about vector types?

[bjope]

lib/CodeGen/TargetLoweringBase.cpp

1890 ↗

(On Diff #169303)

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 ↗

(On Diff #169303)

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 ↗

(On Diff #169506)

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 ↗

(On Diff #169506)

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

[craig.topper]

test/CodeGen/X86/sadd_sat.ll

2 ↗

(On Diff #169506)

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

[craig.topper]

test/CodeGen/X86/sadd_sat.ll

2 ↗

(On Diff #169506)

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

[leonardchan]

test/CodeGen/X86/sadd_sat.ll

2 ↗

(On Diff #169506)

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)

llvm/trunk/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,

llvm/trunk/include/llvm/CodeGen/TargetLowering.h

public:
 
   /// Get a pointer to vector element \p Idx located in memory for a vector of
   /// type \p VecVT starting at a base address of \p VecPtr. If \p Idx is out of
   /// bounds the returned pointer is unspecified, but will be within the vector
   /// bounds.
   SDValue getVectorElementPointer(SelectionDAG &DAG, SDValue VecPtr, EVT VecVT,
                                   SDValue Index) const;
 
+  /// Method for building the DAG expansion of ISD::SADDSAT. This method accepts
+  /// integers or vectors of integers as its arguments.
+  SDValue getExpandedSignedSaturationAddition(SDNode *Node,
+                                              SelectionDAG &DAG) const;
+
   //===--------------------------------------------------------------------===//
   // Instruction Emitting Hooks
   //
 
   /// This method should be implemented by targets that mark instructions with
   /// the 'usesCustomInserter' flag.  These instructions are special in various
   /// ways, which require special support to insert.  The specified MachineInstr
   /// is created but not inserted into any basic blocks, and this method is

llvm/trunk/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, Commutative]>;
+
 //===------------------------- 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>]>;

llvm/trunk/include/llvm/Target/TargetSelectionDAG.td

def smin       : SDNode<"ISD::SMIN"      , SDTIntBinOp,
                                   [SDNPCommutative, SDNPAssociative]>;
 def smax       : SDNode<"ISD::SMAX"      , SDTIntBinOp,
                                   [SDNPCommutative, SDNPAssociative]>;
 def umin       : SDNode<"ISD::UMIN"      , SDTIntBinOp,
                                   [SDNPCommutative, SDNPAssociative]>;
 def umax       : SDNode<"ISD::UMAX"      , SDTIntBinOp,
                                   [SDNPCommutative, SDNPAssociative]>;
 
+def saddsat    : SDNode<"ISD::SADDSAT"   , SDTIntBinOp, [SDNPCommutative]>;
+
 def sext_inreg : SDNode<"ISD::SIGN_EXTEND_INREG", SDTExtInreg>;
 def sext_invec : SDNode<"ISD::SIGN_EXTEND_VECTOR_INREG", SDTExtInvec>;
 def zext_invec : SDNode<"ISD::ZERO_EXTEND_VECTOR_INREG", SDTExtInvec>;
 
 def abs        : SDNode<"ISD::ABS"        , SDTIntUnaryOp>;
 def bitreverse : SDNode<"ISD::BITREVERSE" , SDTIntUnaryOp>;
 def bswap      : SDNode<"ISD::BSWAP"      , SDTIntUnaryOp>;
 def ctlz       : SDNode<"ISD::CTLZ"       , SDTIntUnaryOp>;

llvm/trunk/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);

llvm/trunk/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);
+  SDValue Op2Promoted = GetPromotedInteger(Op2);
+
+  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_SADDSAT(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_SADDSAT(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.

llvm/trunk/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_SADDSAT           (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);
 

llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
   case ISD::ZERO_EXTEND_VECTOR_INREG:
   case ISD::SMIN:
   case ISD::SMAX:
   case ISD::UMIN:
   case ISD::UMAX:
   case ISD::SMUL_LOHI:
   case ISD::UMUL_LOHI:
   case ISD::FCANONICALIZE:
+  case ISD::SADDSAT:
     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
     break;
   case ISD::FP_ROUND_INREG:
     Action = TLI.getOperationAction(Node->getOpcode(),
                cast<VTSDNode>(Node->getOperand(1))->getVT());
     break;
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:

llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

#endif
   case ISD::FMAXNUM:
   case ISD::FMINNAN:
   case ISD::FMAXNAN:
   case ISD::SMIN:
   case ISD::SMAX:
   case ISD::UMIN:
   case ISD::UMAX:
 
+  case ISD::SADDSAT:
+
   case ISD::FPOW:
   case ISD::FREM:
   case ISD::FSUB:
   case ISD::MUL:
   case ISD::OR:
   case ISD::SDIV:
   case ISD::SREM:
   case ISD::SUB:
#endif
   case ISD::SRL:
   case ISD::UREM:
   case ISD::SREM:
   case ISD::FREM:
   case ISD::SMIN:
   case ISD::SMAX:
   case ISD::UMIN:
   case ISD::UMAX:
+  case ISD::SADDSAT:
     SplitVecRes_BinOp(N, Lo, Hi);
     break;
   case ISD::FMA:
     SplitVecRes_TernaryOp(N, Lo, Hi);
     break;
   case ISD::STRICT_FADD:
   case ISD::STRICT_FSUB:
   case ISD::STRICT_FMUL:

llvm/trunk/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;

llvm/trunk/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";

llvm/trunk/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (C->isNullValue() && CC == ISD::SETEQ) {
       SDValue Clz = DAG.getNode(ISD::CTLZ, dl, VT, Zext);
       SDValue Scc = DAG.getNode(ISD::SRL, dl, VT, Clz,
                                 DAG.getConstant(Log2b, dl, MVT::i32));
       return DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Scc);
     }
   }
   return SDValue();
 }
+
+SDValue
+TargetLowering::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 integers. Vector of int arguments should "
+         "already be unrolled.");
+  assert(RHS.getValueType().isScalarInteger() &&
+         "Expected operands to be integers. Vector of int arguments should "
+         "already be unrolled.");
+  assert(LHS.getValueType() == RHS.getValueType() &&
+         "Expected both operands of SADDSAT to be the same type");
+
+  unsigned BitWidth = LHS.getValueSizeInBits();
+  EVT ResultType = LHS.getValueType();
+  EVT BoolVT =
+      getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), ResultType);
+  SDValue Result =
+      DAG.getNode(ISD::SADDO, dl, DAG.getVTList(ResultType, BoolVT), LHS, RHS);
+  SDValue Sum = Result.getValue(0);
+  SDValue Overflow = Result.getValue(1);
+
+  // SatMax -> Overflow && Sum < 0
+  // SatMin -> Overflow && Sum > 0
+  SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
+
+  SDValue SumNeg = DAG.getSetCC(dl, BoolVT, Sum, Zero, ISD::SETLT);
+  APInt MinVal = APInt::getSignedMinValue(BitWidth);
+  APInt MaxVal = APInt::getSignedMaxValue(BitWidth);
+  SDValue SatMin = DAG.getConstant(MinVal, dl, ResultType);
+  SDValue SatMax = DAG.getConstant(MaxVal, dl, ResultType);
+
+  Result = DAG.getSelect(dl, ResultType, SumNeg, SatMax, SatMin);
+  return DAG.getSelect(dl, ResultType, Overflow, Result, Sum);
+}

llvm/trunk/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);

llvm/trunk/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()->isIntOrIntVectorTy(),
+           "first operand of sadd_sat must be an int type or vector of ints");
+    Assert(Op2->getType()->isIntOrIntVectorTy(),
+           "second operand of sadd_sat must be an int type or vector of ints");
+    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) {

llvm/trunk/test/CodeGen/X86/sadd_sat.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mcpu=generic -mtriple=x86_64-linux | FileCheck %s
+; RUN: llc < %s -mcpu=generic -mtriple=i686 -mattr=cmov | 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)
+declare  <4 x i32> @llvm.sadd.sat.v4i32(<4 x i32>, <4 x i32>)
+
+define i32 @func(i32 %x, i32 %y) {
+; CHECK-LABEL: func:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    movl %edi, %ecx
+; CHECK-NEXT:    addl %esi, %ecx
+; CHECK-NEXT:    setns %al
+; CHECK-NEXT:    addl $2147483647, %eax # imm = 0x7FFFFFFF
+; CHECK-NEXT:    addl %esi, %edi
+; CHECK-NEXT:    cmovnol %edi, %eax
+; CHECK-NEXT:    retq
+;
+; CHECK32-LABEL: func:
+; CHECK32:       # %bb.0:
+; CHECK32-NEXT:    pushl %esi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 8
+; CHECK32-NEXT:    .cfi_offset %esi, -8
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; CHECK32-NEXT:    xorl %ecx, %ecx
+; CHECK32-NEXT:    movl %eax, %esi
+; CHECK32-NEXT:    addl %edx, %esi
+; CHECK32-NEXT:    setns %cl
+; CHECK32-NEXT:    addl $2147483647, %ecx # imm = 0x7FFFFFFF
+; CHECK32-NEXT:    addl %edx, %eax
+; CHECK32-NEXT:    cmovol %ecx, %eax
+; CHECK32-NEXT:    popl %esi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 4
+; CHECK32-NEXT:    retl
+  %tmp = call i32 @llvm.sadd.sat.i32(i32 %x, i32 %y);
+  ret i32 %tmp;
+}
+
+define i64 @func2(i64 %x, i64 %y) {
+; CHECK-LABEL: func2:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    addq %rsi, %rax
+; CHECK-NEXT:    setns %cl
+; CHECK-NEXT:    movabsq $9223372036854775807, %rax # imm = 0x7FFFFFFFFFFFFFFF
+; CHECK-NEXT:    addq %rcx, %rax
+; CHECK-NEXT:    addq %rsi, %rdi
+; CHECK-NEXT:    cmovnoq %rdi, %rax
+; CHECK-NEXT:    retq
+;
+; CHECK32-LABEL: func2:
+; CHECK32:       # %bb.0:
+; CHECK32-NEXT:    pushl %ebp
+; CHECK32-NEXT:    .cfi_def_cfa_offset 8
+; CHECK32-NEXT:    pushl %ebx
+; CHECK32-NEXT:    .cfi_def_cfa_offset 12
+; CHECK32-NEXT:    pushl %edi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 16
+; CHECK32-NEXT:    pushl %esi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 20
+; CHECK32-NEXT:    .cfi_offset %esi, -20
+; CHECK32-NEXT:    .cfi_offset %edi, -16
+; CHECK32-NEXT:    .cfi_offset %ebx, -12
+; CHECK32-NEXT:    .cfi_offset %ebp, -8
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %esi
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %edi
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %ebx
+; CHECK32-NEXT:    addl {{[0-9]+}}(%esp), %edi
+; CHECK32-NEXT:    movl %ebx, %ebp
+; CHECK32-NEXT:    adcl %esi, %ebp
+; CHECK32-NEXT:    movl %ebp, %eax
+; CHECK32-NEXT:    sarl $31, %eax
+; CHECK32-NEXT:    xorl %ecx, %ecx
+; CHECK32-NEXT:    testl %ebp, %ebp
+; CHECK32-NEXT:    setns %cl
+; CHECK32-NEXT:    movl %ecx, %edx
+; CHECK32-NEXT:    addl $2147483647, %edx # imm = 0x7FFFFFFF
+; CHECK32-NEXT:    testl %ebx, %ebx
+; CHECK32-NEXT:    setns %bl
+; CHECK32-NEXT:    cmpb %cl, %bl
+; CHECK32-NEXT:    setne %cl
+; CHECK32-NEXT:    testl %esi, %esi
+; CHECK32-NEXT:    setns %ch
+; CHECK32-NEXT:    cmpb %ch, %bl
+; CHECK32-NEXT:    sete %ch
+; CHECK32-NEXT:    testb %cl, %ch
+; CHECK32-NEXT:    cmovel %ebp, %edx
+; CHECK32-NEXT:    cmovel %edi, %eax
+; CHECK32-NEXT:    popl %esi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 16
+; CHECK32-NEXT:    popl %edi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 12
+; CHECK32-NEXT:    popl %ebx
+; CHECK32-NEXT:    .cfi_def_cfa_offset 8
+; CHECK32-NEXT:    popl %ebp
+; CHECK32-NEXT:    .cfi_def_cfa_offset 4
+; CHECK32-NEXT:    retl
+  %tmp = call i64 @llvm.sadd.sat.i64(i64 %x, i64 %y);
+  ret i64 %tmp;
+}
+
+define i4 @func3(i4 %x, i4 %y) {
+; CHECK-LABEL: func3:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movl %edi, %eax
+; CHECK-NEXT:    shlb $4, %sil
+; CHECK-NEXT:    shlb $4, %al
+; CHECK-NEXT:    movl %eax, %ecx
+; CHECK-NEXT:    addb %sil, %cl
+; CHECK-NEXT:    setns %cl
+; CHECK-NEXT:    addb %sil, %al
+; CHECK-NEXT:    jno .LBB2_2
+; CHECK-NEXT:  # %bb.1:
+; CHECK-NEXT:    addb $127, %cl
+; CHECK-NEXT:    movl %ecx, %eax
+; CHECK-NEXT:  .LBB2_2:
+; CHECK-NEXT:    sarb $4, %al
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
+; CHECK-NEXT:    retq
+;
+; CHECK32-LABEL: func3:
+; CHECK32:       # %bb.0:
+; CHECK32-NEXT:    movb {{[0-9]+}}(%esp), %al
+; CHECK32-NEXT:    movb {{[0-9]+}}(%esp), %dl
+; CHECK32-NEXT:    shlb $4, %dl
+; CHECK32-NEXT:    shlb $4, %al
+; CHECK32-NEXT:    movl %eax, %ecx
+; CHECK32-NEXT:    addb %dl, %cl
+; CHECK32-NEXT:    setns %cl
+; CHECK32-NEXT:    addb %dl, %al
+; CHECK32-NEXT:    jno .LBB2_2
+; CHECK32-NEXT:  # %bb.1:
+; CHECK32-NEXT:    addb $127, %cl
+; CHECK32-NEXT:    movl %ecx, %eax
+; CHECK32-NEXT:  .LBB2_2:
+; CHECK32-NEXT:    sarb $4, %al
+; CHECK32-NEXT:    retl
+  %tmp = call i4 @llvm.sadd.sat.i4(i4 %x, i4 %y);
+  ret i4 %tmp;
+}
+
+define <4 x i32> @vec(<4 x i32> %x, <4 x i32> %y) {
+; CHECK-LABEL: vec:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm1[1,1,2,3]
+; CHECK-NEXT:    movd %xmm2, %ecx
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,2,3]
+; CHECK-NEXT:    movd %xmm2, %r8d
+; CHECK-NEXT:    xorl %edx, %edx
+; CHECK-NEXT:    movl %r8d, %esi
+; CHECK-NEXT:    addl %ecx, %esi
+; CHECK-NEXT:    setns %dl
+; CHECK-NEXT:    addl $2147483647, %edx # imm = 0x7FFFFFFF
+; CHECK-NEXT:    addl %ecx, %r8d
+; CHECK-NEXT:    cmovol %edx, %r8d
+; CHECK-NEXT:    movd %xmm1, %edx
+; CHECK-NEXT:    movd %xmm0, %ecx
+; CHECK-NEXT:    xorl %esi, %esi
+; CHECK-NEXT:    movl %ecx, %edi
+; CHECK-NEXT:    addl %edx, %edi
+; CHECK-NEXT:    setns %sil
+; CHECK-NEXT:    addl $2147483647, %esi # imm = 0x7FFFFFFF
+; CHECK-NEXT:    addl %edx, %ecx
+; CHECK-NEXT:    cmovol %esi, %ecx
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm1[2,3,0,1]
+; CHECK-NEXT:    movd %xmm2, %edx
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[2,3,0,1]
+; CHECK-NEXT:    movd %xmm2, %eax
+; CHECK-NEXT:    xorl %edi, %edi
+; CHECK-NEXT:    movl %eax, %esi
+; CHECK-NEXT:    addl %edx, %esi
+; CHECK-NEXT:    setns %dil
+; CHECK-NEXT:    addl $2147483647, %edi # imm = 0x7FFFFFFF
+; CHECK-NEXT:    addl %edx, %eax
+; CHECK-NEXT:    cmovol %edi, %eax
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[3,1,2,3]
+; CHECK-NEXT:    movd %xmm1, %r9d
+; CHECK-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[3,1,2,3]
+; CHECK-NEXT:    movd %xmm0, %edx
+; CHECK-NEXT:    xorl %edi, %edi
+; CHECK-NEXT:    movl %edx, %esi
+; CHECK-NEXT:    addl %r9d, %esi
+; CHECK-NEXT:    setns %dil
+; CHECK-NEXT:    addl $2147483647, %edi # imm = 0x7FFFFFFF
+; CHECK-NEXT:    addl %r9d, %edx
+; CHECK-NEXT:    cmovol %edi, %edx
+; CHECK-NEXT:    movd %edx, %xmm0
+; CHECK-NEXT:    movd %eax, %xmm1
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
+; CHECK-NEXT:    movd %ecx, %xmm0
+; CHECK-NEXT:    movd %r8d, %xmm2
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm2[0],xmm0[1],xmm2[1]
+; CHECK-NEXT:    punpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; CHECK-NEXT:    retq
+;
+; CHECK32-LABEL: vec:
+; CHECK32:       # %bb.0:
+; CHECK32-NEXT:    pushl %ebp
+; CHECK32-NEXT:    .cfi_def_cfa_offset 8
+; CHECK32-NEXT:    pushl %ebx
+; CHECK32-NEXT:    .cfi_def_cfa_offset 12
+; CHECK32-NEXT:    pushl %edi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 16
+; CHECK32-NEXT:    pushl %esi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 20
+; CHECK32-NEXT:    .cfi_offset %esi, -20
+; CHECK32-NEXT:    .cfi_offset %edi, -16
+; CHECK32-NEXT:    .cfi_offset %ebx, -12
+; CHECK32-NEXT:    .cfi_offset %ebp, -8
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; CHECK32-NEXT:    xorl %eax, %eax
+; CHECK32-NEXT:    movl %ecx, %esi
+; CHECK32-NEXT:    addl %edx, %esi
+; CHECK32-NEXT:    setns %al
+; CHECK32-NEXT:    addl $2147483647, %eax # imm = 0x7FFFFFFF
+; CHECK32-NEXT:    addl %edx, %ecx
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; CHECK32-NEXT:    cmovol %eax, %ecx
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %esi
+; CHECK32-NEXT:    xorl %eax, %eax
+; CHECK32-NEXT:    movl %edx, %edi
+; CHECK32-NEXT:    addl %esi, %edi
+; CHECK32-NEXT:    setns %al
+; CHECK32-NEXT:    addl $2147483647, %eax # imm = 0x7FFFFFFF
+; CHECK32-NEXT:    addl %esi, %edx
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %esi
+; CHECK32-NEXT:    cmovol %eax, %edx
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %edi
+; CHECK32-NEXT:    xorl %eax, %eax
+; CHECK32-NEXT:    movl %esi, %ebx
+; CHECK32-NEXT:    addl %edi, %ebx
+; CHECK32-NEXT:    setns %al
+; CHECK32-NEXT:    addl $2147483647, %eax # imm = 0x7FFFFFFF
+; CHECK32-NEXT:    addl %edi, %esi
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %edi
+; CHECK32-NEXT:    cmovol %eax, %esi
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK32-NEXT:    xorl %ebx, %ebx
+; CHECK32-NEXT:    movl %edi, %ebp
+; CHECK32-NEXT:    addl %eax, %ebp
+; CHECK32-NEXT:    setns %bl
+; CHECK32-NEXT:    addl $2147483647, %ebx # imm = 0x7FFFFFFF
+; CHECK32-NEXT:    addl %eax, %edi
+; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK32-NEXT:    cmovol %ebx, %edi
+; CHECK32-NEXT:    movl %ecx, 12(%eax)
+; CHECK32-NEXT:    movl %edx, 8(%eax)
+; CHECK32-NEXT:    movl %esi, 4(%eax)
+; CHECK32-NEXT:    movl %edi, (%eax)
+; CHECK32-NEXT:    popl %esi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 16
+; CHECK32-NEXT:    popl %edi
+; CHECK32-NEXT:    .cfi_def_cfa_offset 12
+; CHECK32-NEXT:    popl %ebx
+; CHECK32-NEXT:    .cfi_def_cfa_offset 8
+; CHECK32-NEXT:    popl %ebp
+; CHECK32-NEXT:    .cfi_def_cfa_offset 4
+; CHECK32-NEXT:    retl $4
+  %tmp = call <4 x i32> @llvm.sadd.sat.v4i32(<4 x i32> %x, <4 x i32> %y);
+  ret <4 x i32> %tmp;
+}