Add sub/mul overflow intrinsics. This currently doesn't have a

target-independent way of determining overflow on multiplication. It's very
tricky. Patch by Zoltan Varga!

llvm-svn: 60800

6 files changed, 87 insertions, 25 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index c13e84b0b36..c33a8fffea9 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -4234,7 +4234,8 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
     break;
   }
 
-  case ISD::SADDO: {
+  case ISD::SADDO:
+  case ISD::SSUBO: {
     MVT VT = Node->getValueType(0);
     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
     default: assert(0 && "This action not supported for this op yet!");
@@ -4246,7 +4247,9 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
       SDValue LHS = LegalizeOp(Node->getOperand(0));
       SDValue RHS = LegalizeOp(Node->getOperand(1));
 
-      SDValue Sum = DAG.getNode(ISD::ADD, LHS.getValueType(), LHS, RHS);
+      SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ? 
+                                ISD::ADD : ISD::SUB, LHS.getValueType(),
+                                LHS, RHS);
       MVT OType = Node->getValueType(1);
 
       SDValue Zero = DAG.getConstant(0, LHS.getValueType());
@@ -4255,16 +4258,21 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
       //   RHSSign -> RHS >= 0
       //   SumSign -> Sum >= 0
       //
+      //   Add:
       //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
+      //   Sub:
+      //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
       //
       SDValue LHSSign = DAG.getSetCC(OType, LHS, Zero, ISD::SETGE);
       SDValue RHSSign = DAG.getSetCC(OType, RHS, Zero, ISD::SETGE);
-      SDValue SignsEq = DAG.getSetCC(OType, LHSSign, RHSSign, ISD::SETEQ);
+      SDValue SignsMatch = DAG.getSetCC(OType, LHSSign, RHSSign, 
+                                        Node->getOpcode() == ISD::SADDO ? 
+                                        ISD::SETEQ : ISD::SETNE);
 
       SDValue SumSign = DAG.getSetCC(OType, Sum, Zero, ISD::SETGE);
       SDValue SumSignNE = DAG.getSetCC(OType, LHSSign, SumSign, ISD::SETNE);
 
-      SDValue Cmp = DAG.getNode(ISD::AND, OType, SignsEq, SumSignNE);
+      SDValue Cmp = DAG.getNode(ISD::AND, OType, SignsMatch, SumSignNE);
 
       MVT ValueVTs[] = { LHS.getValueType(), OType };
       SDValue Ops[] = { Sum, Cmp };
@@ -4280,7 +4288,8 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
 
     break;
   }
-  case ISD::UADDO: {
+  case ISD::UADDO:
+  case ISD::USUBO: {
     MVT VT = Node->getValueType(0);
     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
     default: assert(0 && "This action not supported for this op yet!");
@@ -4292,9 +4301,13 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
       SDValue LHS = LegalizeOp(Node->getOperand(0));
       SDValue RHS = LegalizeOp(Node->getOperand(1));
 
-      SDValue Sum = DAG.getNode(ISD::ADD, LHS.getValueType(), LHS, RHS);
+      SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::UADDO ?
+                                ISD::ADD : ISD::SUB, LHS.getValueType(),
+                                LHS, RHS);
       MVT OType = Node->getValueType(1);
-      SDValue Cmp = DAG.getSetCC(OType, Sum, LHS, ISD::SETULT);
+      SDValue Cmp = DAG.getSetCC(OType, Sum, LHS,
+                                 Node->getOpcode () == ISD::UADDO ? 
+                                 ISD::SETULT : ISD::SETUGT);
 
       MVT ValueVTs[] = { LHS.getValueType(), OType };
       SDValue Ops[] = { Sum, Cmp };
@@ -4310,6 +4323,25 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
 
     break;
   }
+  case ISD::SMULO:
+  case ISD::UMULO: {
+    MVT VT = Node->getValueType(0);
+    switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
+    default: assert(0 && "This action is not supported at all!");
+    case TargetLowering::Custom:
+      Result = TLI.LowerOperation(Op, DAG);
+      if (Result.getNode()) break;
+      // Fall Thru
+    case TargetLowering::Legal:
+      // FIXME: According to Hacker's Delight, this can be implemented in
+      // target independent lowering, but it would be inefficient, since it
+      // requires a division + a branch
+      assert(0 && "Target independent lowering is not supported for SMULO/UMULO!");	
+    break;
+    }
+    break;
+  }
+
   }
   
   assert(Result.getValueType() == Op.getValueType() &&
diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
index 62fcff392ee..10cfdc634bd 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
@@ -92,7 +92,11 @@ void DAGTypeLegalizer::PromoteIntegerResult(SDNode *N, unsigned ResNo) {
   case ISD::UREM:        Result = PromoteIntRes_UDIV(N); break;
 
   case ISD::SADDO:
-  case ISD::UADDO:       Result = PromoteIntRes_XADDO(N, ResNo); break;
+  case ISD::UADDO:
+  case ISD::SSUBO:
+  case ISD::USUBO:
+  case ISD::SMULO:
+  case ISD::UMULO:       Result = PromoteIntRes_XALUO(N, ResNo); break;
 
   case ISD::ATOMIC_LOAD_ADD_8:
   case ISD::ATOMIC_LOAD_SUB_8:
@@ -518,7 +522,7 @@ SDValue DAGTypeLegalizer::PromoteIntRes_UDIV(SDNode *N) {
   return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
 }
 
-SDValue DAGTypeLegalizer::PromoteIntRes_XADDO(SDNode *N, unsigned ResNo) {
+SDValue DAGTypeLegalizer::PromoteIntRes_XALUO(SDNode *N, unsigned ResNo) {
   assert(ResNo == 1 && "Only boolean result promotion currently supported!");
 
   // Simply change the return type of the boolean result.
diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h
index d2365d262e4..d46fccd0f84 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h
@@ -270,7 +270,7 @@ private:
   SDValue PromoteIntRes_UDIV(SDNode *N);
   SDValue PromoteIntRes_UNDEF(SDNode *N);
   SDValue PromoteIntRes_VAARG(SDNode *N);
-  SDValue PromoteIntRes_XADDO(SDNode *N, unsigned ResNo);
+  SDValue PromoteIntRes_XALUO(SDNode *N, unsigned ResNo);
 
   // Integer Operand Promotion.
   bool PromoteIntegerOperand(SDNode *N, unsigned OperandNo);
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 979dea0d7f0..bb3b42c383f 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -1511,6 +1511,10 @@ void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask,
     return;
   case ISD::SADDO:
   case ISD::UADDO:
+  case ISD::SSUBO:
+  case ISD::USUBO:
+  case ISD::SMULO:
+  case ISD::UMULO:
     if (Op.getResNo() != 1)
       return;
     // The boolean result conforms to getBooleanContents.  Fall through.
@@ -1919,6 +1923,10 @@ unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
 
   case ISD::SADDO:
   case ISD::UADDO:
+  case ISD::SSUBO:
+  case ISD::USUBO:
+  case ISD::SMULO:
+  case ISD::UMULO:
     if (Op.getResNo() != 1)
       break;
     // The boolean result conforms to getBooleanContents.  Fall through.
@@ -5216,6 +5224,10 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::ADDE:        return "adde";
   case ISD::SADDO:       return "saddo";
   case ISD::UADDO:       return "uaddo";
+  case ISD::SSUBO:       return "ssubo";
+  case ISD::USUBO:       return "usubo";
+  case ISD::SMULO:       return "smulo";
+  case ISD::UMULO:       return "umulo";
   case ISD::SUBC:        return "subc";
   case ISD::SUBE:        return "sube";
   case ISD::SHL_PARTS:   return "shl_parts";
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
index e8987c54af5..5d81d224c88 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
@@ -2968,6 +2968,23 @@ SelectionDAGLowering::implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op) {
   return 0;
 }
 
+// implVisitAluOverflow - Lower an overflow instrinsics
+const char *
+SelectionDAGLowering::implVisitAluOverflow(CallInst &I, ISD::NodeType Op) {
+    SDValue Op1 = getValue(I.getOperand(1));
+    SDValue Op2 = getValue(I.getOperand(2));
+
+    MVT ValueVTs[] = { Op1.getValueType(), MVT::i1 };
+    SDValue Ops[] = { Op1, Op2 };
+
+    SDValue Result =
+      DAG.getNode(Op,
+                  DAG.getVTList(&ValueVTs[0], 2), &Ops[0], 2);
+
+    setValue(&I, Result);
+    return 0;
+  }
+
 /// visitExp - Lower an exp intrinsic. Handles the special sequences for
 /// limited-precision mode.
 void
@@ -4097,21 +4114,17 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
   }
 
   case Intrinsic::uadd_with_overflow:
-  case Intrinsic::sadd_with_overflow: {
-    SDValue Op1 = getValue(I.getOperand(1));
-    SDValue Op2 = getValue(I.getOperand(2));
-
-    MVT ValueVTs[] = { Op1.getValueType(), MVT::i1 };
-    SDValue Ops[] = { Op1, Op2 };
-
-    SDValue Result =
-      DAG.getNode((Intrinsic == Intrinsic::sadd_with_overflow) ?
-                    ISD::SADDO : ISD::UADDO,
-                  DAG.getVTList(&ValueVTs[0], 2), &Ops[0], 2);
-
-    setValue(&I, Result);
-    return 0;
-  }
+    return implVisitAluOverflow(I, ISD::UADDO);
+  case Intrinsic::sadd_with_overflow:
+    return implVisitAluOverflow(I, ISD::SADDO);
+  case Intrinsic::usub_with_overflow:
+    return implVisitAluOverflow(I, ISD::USUBO);
+  case Intrinsic::ssub_with_overflow:
+    return implVisitAluOverflow(I, ISD::SSUBO);
+  case Intrinsic::umul_with_overflow:
+    return implVisitAluOverflow(I, ISD::UMULO);
+  case Intrinsic::smul_with_overflow:
+    return implVisitAluOverflow(I, ISD::SMULO);
 
   case Intrinsic::prefetch: {
     SDValue Ops[4];
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.h b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.h
index e614c3049d8..db70f169020 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.h
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuild.h
@@ -530,6 +530,7 @@ private:
   }
   
   const char *implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op);
+  const char *implVisitAluOverflow(CallInst &I, ISD::NodeType Op);
 };
 
 /// AddCatchInfo - Extract the personality and type infos from an eh.selector