A prototype for intrinsifying Math.addExact(int, int), version 2

checked_add_prototype.ver2.patch

diff -r 6f8f439e247d src/cpu/x86/vm/x86_64.ad
--- a/src/cpu/x86/vm/x86_64.ad	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/cpu/x86/vm/x86_64.ad	Thu Jun 21 20:48:06 2012 +0800
@@ -1674,6 +1674,16 @@
   return LONG_RDX_REG_mask();
 }
 
+// Register for AddI projection of checkedAddI
+RegMask Matcher::checkedAddI_sum_proj_mask() {
+  return INT_RAX_REG_mask();
+}
+
+// Register for conditions projection
+RegMask Matcher::overflow_proj_mask() {
+  return INT_FLAGS_mask();
+}
+
 const RegMask Matcher::method_handle_invoke_SP_save_mask() {
   return PTR_RBP_REG_mask();
 }
@@ -4173,6 +4183,8 @@
     greater_equal(0xD, "ge");
     less_equal(0xE, "le");
     greater(0xF, "g");
+    overflow(0x0, "o");
+    no_overflow(0x1, "no");
   %}
 %}
 
@@ -4191,6 +4203,8 @@
     greater_equal(0x3, "nb");
     less_equal(0x6, "be");
     greater(0x7, "nbe");
+    overflow(0x0, "o");
+    no_overflow(0x1, "no");
   %}
 %}
 
@@ -4210,6 +4224,8 @@
     greater_equal(0x3, "nb");
     less_equal(0x6, "be");
     greater(0x7, "nbe");
+    overflow(0x0, "o");
+    no_overflow(0x1, "no");
   %}
 %}
 
@@ -4227,6 +4243,8 @@
     greater_equal(0x3, "nb");
     less_equal(0x6, "be");
     greater(0x7, "nbe");
+    overflow(0x0, "o");
+    no_overflow(0x1, "no");
   %}
 %}
 
@@ -7673,6 +7691,19 @@
   ins_pipe(ialu_reg_reg_alu0);
 %}
 
+// Integer addition with overflow checking
+instruct checkedAddI_rReg(rax_RegI rax, rRegI src, rFlagsReg cr)
+%{
+  match(CheckedAddI rax src);
+  effect(DEF cr);
+
+  format %{ "addl    $rax, $src\t# int with overflow check" %}
+  ins_encode %{
+    __ addl($rax$$Register, $src$$Register);
+  %}
+  ins_pipe(ialu_reg_reg);
+%}
+
 // Integer DIVMOD with Register, both quotient and mod results
 instruct divModI_rReg_divmod(rax_RegI rax, rdx_RegI rdx, no_rax_rdx_RegI div,
                              rFlagsReg cr)
diff -r 6f8f439e247d src/share/vm/adlc/adlparse.cpp
--- a/src/share/vm/adlc/adlparse.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/adlc/adlparse.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -3388,12 +3388,16 @@
   char *greater_equal;
   char *less_equal;
   char *greater;
+  char *overflow;
+  char *no_overflow;
   const char *equal_format = "eq";
   const char *not_equal_format = "ne";
   const char *less_format = "lt";
   const char *greater_equal_format = "ge";
   const char *less_equal_format = "le";
   const char *greater_format = "gt";
+  const char *overflow_format = "ov";
+  const char *no_overflow_format = "no";
 
   if (_curchar != '%') {
     parse_err(SYNERR, "Missing '%{' for 'cond_interface' block.\n");
@@ -3430,6 +3434,12 @@
     else if ( strcmp(field,"greater") == 0 ) {
       greater = interface_field_parse(&greater_format);
     }
+    else if ( strcmp(field,"overflow") == 0 ) {
+      overflow = interface_field_parse(&overflow_format);
+    }
+    else if ( strcmp(field,"no_overflow") == 0 ) {
+      no_overflow = interface_field_parse(&no_overflow_format);
+    }
     else {
       parse_err(SYNERR, "Expected keyword, base|index|scale|disp,  or '%}' ending interface.\n");
       return NULL;
@@ -3448,7 +3458,9 @@
                                        less,          less_format,
                                        greater_equal, greater_equal_format,
                                        less_equal,    less_equal_format,
-                                       greater,       greater_format);
+                                       greater,       greater_format,
+                                       overflow,      overflow_format,
+                                       no_overflow,   no_overflow_format);
   return inter;
 }
 
diff -r 6f8f439e247d src/share/vm/adlc/formssel.cpp
--- a/src/share/vm/adlc/formssel.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/adlc/formssel.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -2694,14 +2694,18 @@
                              const char* less,          const char* less_format,
                              const char* greater_equal, const char* greater_equal_format,
                              const char* less_equal,    const char* less_equal_format,
-                             const char* greater,       const char* greater_format)
+                             const char* greater,       const char* greater_format,
+                             const char* overflow,      const char* overflow_format,
+                             const char* no_overflow,   const char* no_overflow_format)
   : Interface("COND_INTER"),
     _equal(equal),                 _equal_format(equal_format),
     _not_equal(not_equal),         _not_equal_format(not_equal_format),
     _less(less),                   _less_format(less_format),
     _greater_equal(greater_equal), _greater_equal_format(greater_equal_format),
     _less_equal(less_equal),       _less_equal_format(less_equal_format),
-    _greater(greater),             _greater_format(greater_format) {
+    _greater(greater),             _greater_format(greater_format),
+    _overflow(overflow),           _overflow_format(overflow_format),
+    _no_overflow(no_overflow),     _no_overflow_format(no_overflow_format) {
 }
 CondInterface::~CondInterface() {
   // not owner of any character arrays
@@ -2720,6 +2724,8 @@
   if ( _greater_equal  != NULL ) fprintf(fp," greater_equal   == %s\n", _greater_equal);
   if ( _less_equal  != NULL ) fprintf(fp," less_equal  == %s\n", _less_equal);
   if ( _greater  != NULL )    fprintf(fp," greater     == %s\n", _greater);
+  if ( _overflow  != NULL )   fprintf(fp," overflow    == %s\n", _overflow);
+  if ( _no_overflow  != NULL )   fprintf(fp," no_overflow == %s\n", _no_overflow);
   // fprintf(fp,"\n");
 }
 
diff -r 6f8f439e247d src/share/vm/adlc/formssel.hpp
--- a/src/share/vm/adlc/formssel.hpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/adlc/formssel.hpp	Thu Jun 21 20:48:06 2012 +0800
@@ -786,7 +786,7 @@
 //------------------------------CondInterface----------------------------------
 class CondInterface : public Interface {
 private:
-
+// TODO fix comments of COND_INTER in *.ad files
 public:
   const char *_equal;
   const char *_not_equal;
@@ -794,12 +794,16 @@
   const char *_greater_equal;
   const char *_less_equal;
   const char *_greater;
+  const char *_overflow;
+  const char *_no_overflow;
   const char *_equal_format;
   const char *_not_equal_format;
   const char *_less_format;
   const char *_greater_equal_format;
   const char *_less_equal_format;
   const char *_greater_format;
+  const char *_overflow_format;
+  const char *_no_overflow_format;
 
   // Public Methods
   CondInterface(const char* equal,         const char* equal_format,
@@ -807,7 +811,9 @@
                 const char* less,          const char* less_format,
                 const char* greater_equal, const char* greater_equal_format,
                 const char* less_equal,    const char* less_equal_format,
-                const char* greater,       const char* greater_format);
+                const char* greater,       const char* greater_format,
+                const char* overflow,      const char* overflow_format,
+                const char* no_overflow,   const char* no_overflow_format);
   ~CondInterface();
 
   void dump();
diff -r 6f8f439e247d src/share/vm/adlc/output_h.cpp
--- a/src/share/vm/adlc/output_h.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/adlc/output_h.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -364,6 +364,8 @@
   fprintf(fp, "    else if( _c%d == BoolTest::ge ) st->print(\"%s\");\n",i,cond->_greater_equal_format);
   fprintf(fp, "    else if( _c%d == BoolTest::lt ) st->print(\"%s\");\n",i,cond->_less_format);
   fprintf(fp, "    else if( _c%d == BoolTest::gt ) st->print(\"%s\");\n",i,cond->_greater_format);
+  fprintf(fp, "    else if( _c%d == BoolTest::ov ) st->print(\"%s\");\n",i,cond->_overflow_format);
+  fprintf(fp, "    else if( _c%d == BoolTest::no ) st->print(\"%s\");\n",i,cond->_no_overflow_format);
 }
 
 // Output code that dumps constant values, increment "i" if type is constant
@@ -1178,6 +1180,8 @@
       fprintf(fp,"    case  BoolTest::ne : return not_equal();\n");
       fprintf(fp,"    case  BoolTest::le : return less_equal();\n");
       fprintf(fp,"    case  BoolTest::ge : return greater_equal();\n");
+      fprintf(fp,"    case  BoolTest::ov : return overflow();\n");
+      fprintf(fp,"    case  BoolTest::no : return no_overflow();\n");
       fprintf(fp,"    default : ShouldNotReachHere(); return 0;\n");
       fprintf(fp,"    }\n");
       fprintf(fp,"  };\n");
@@ -1343,6 +1347,14 @@
         if( greater != NULL ) {
           define_oper_interface(fp, *oper, _globalNames, "greater", greater);
         }
+        const char *overflow = cInterface->_overflow;
+        if( overflow != NULL ) {
+          define_oper_interface(fp, *oper, _globalNames, "overflow", overflow);
+        }
+        const char *no_overflow = cInterface->_no_overflow;
+        if( no_overflow != NULL ) {
+          define_oper_interface(fp, *oper, _globalNames, "no_overflow", no_overflow);
+        }
       } // end Conditional Interface
       // Check if it is a Constant Interface
       else if (oper->_interface->is_ConstInterface() != NULL ) {
diff -r 6f8f439e247d src/share/vm/opto/classes.hpp
--- a/src/share/vm/opto/classes.hpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/classes.hpp	Thu Jun 21 20:48:06 2012 +0800
@@ -60,6 +60,8 @@
 macro(Catch)
 macro(CatchProj)
 macro(CheckCastPP)
+macro(CheckedAdd)
+macro(CheckedAddI)
 macro(ClearArray)
 macro(ConstraintCast)
 macro(CMoveD)
@@ -68,6 +70,7 @@
 macro(CMoveL)
 macro(CMoveP)
 macro(CMoveN)
+macro(CmpAddI)
 macro(CmpN)
 macro(CmpD)
 macro(CmpD3)
diff -r 6f8f439e247d src/share/vm/opto/compile.cpp
--- a/src/share/vm/opto/compile.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/compile.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -2137,6 +2137,48 @@
   }
 }
 
+//-------------------------------is_checked_addi--------------------------------
+// return the AddI node if an overflowing checking pattern is found
+// Upon success return, disconnect the input edges of the intermediate nodes.
+static Node* is_checked_addi(Node* n) {
+  // Match the following pattern:
+  // Bool(lt, CmpI(AndI(XorI(x, AddI(x, y)), XorI(y, AddI(x, y))), ConI(0)))
+  // where the two AddI's are actually the same node.
+
+  BoolNode* bol = n->as_Bool();
+  if (bol->_test._test != BoolTest::lt) return NULL;
+
+  Node* cmp = bol->in(1);
+  if (cmp->Opcode() != Op_CmpI) return NULL;
+
+  Node* con = cmp->in(2);
+  if (con->Opcode() != Op_ConI ||
+      ((ConINode*) con)->type()->is_int()->get_con() != 0) return NULL;
+
+  Node* a = cmp->in(1);
+  if (a->Opcode() != Op_AndI) return NULL;
+
+  Node* xor1 = a->in(1);
+  Node* xor2 = a->in(2);
+  if (xor1->Opcode() != Op_XorI || xor2->Opcode() != Op_XorI) return NULL;
+
+  Node* x = xor1->in(1);
+  Node* y = xor2->in(1);
+
+  Node* sum = xor1->in(2);
+  if (sum->Opcode() != Op_AddI || xor2->in(2) != sum ||
+      !((sum->in(1) == x && sum->in(2) == y) ||
+        (sum->in(2) == x && sum->in(1) == y)) ) return NULL;
+
+  // found the target node. disconnect the overflow checking nodes
+  if (cmp->outcnt() <= 1)  cmp->subsume_by(NULL);
+  if (a->outcnt() <= 1)    a->subsume_by(NULL);
+  if (xor1->outcnt() <= 1) xor1->subsume_by(NULL);
+  if (xor2->outcnt() <= 1) xor2->subsume_by(NULL);
+
+  return sum;
+}
+
 //------------------------------final_graph_reshaping_impl----------------------
 // Implement items 1-5 from final_graph_reshaping below.
 static void final_graph_reshaping_impl( Node *n, Final_Reshape_Counts &frc ) {
@@ -2591,6 +2633,23 @@
     }
     break;
 
+  case Op_Bool: {
+    if (Matcher::has_match_rule(Op_CheckedAddI)) {
+      Node* sum = is_checked_addi(n);
+      if (sum) {
+        // fuse the AddI and overflow checking into a single node
+        Compile* C = Compile::current();
+        Node* cmpadd = new (C, 3) CmpAddINode(sum->in(1), sum->in(2));
+        CheckedAddINode* chkadd = CheckedAddINode::make(C, cmpadd);
+        BoolNode* bol = new (C, 2) BoolNode(chkadd->overflow_proj(), BoolTest::ov);
+        sum->subsume_by(chkadd->sum_proj());
+        n->subsume_by(bol);
+        cmpadd->subsume_by(chkadd->overflow_proj()); // TODO fix this!
+      }
+    }
+    break;
+  }
+
   case Op_LoadVector:
   case Op_StoreVector:
     break;
diff -r 6f8f439e247d src/share/vm/opto/matcher.hpp
--- a/src/share/vm/opto/matcher.hpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/matcher.hpp	Thu Jun 21 20:48:06 2012 +0800
@@ -317,6 +317,12 @@
   // Register for MODL projection of divmodL
   static RegMask modL_proj_mask();
 
+  // Register for AddI projection of checkedAddI
+  static RegMask checkedAddI_sum_proj_mask();
+
+  // Register for conditions projection
+  static RegMask overflow_proj_mask();
+
   // Use hardware DIV instruction when it is faster than
   // a code which use multiply for division by constant.
   static bool use_asm_for_ldiv_by_con( jlong divisor );
diff -r 6f8f439e247d src/share/vm/opto/subnode.cpp
--- a/src/share/vm/opto/subnode.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/subnode.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -1035,6 +1035,45 @@
 }
 
 
+//==============================================================================
+
+const Type* CmpAddINode::Value(PhaseTransform *phase) const {
+  return TypeInt::CC; // just return the worst case for now
+}
+
+CheckedAddNode::CheckedAddNode(Node* c, Node* in1, Node* in2) : MultiNode(3) {
+  init_req(0, c);
+  init_req(1, in1);
+  init_req(2, in2);
+}
+
+//-------------------------------make-------------------------------------------
+CheckedAddINode* CheckedAddINode::make(Compile* C, Node* cmpadd) {
+  Node* n = cmpadd;
+  assert(n->Opcode() == Op_CmpAddI, "only CmpAddI accepted");
+
+  CheckedAddINode* chkadd = new (C, 3) CheckedAddINode(n->in(0), n->in(1), n->in(2));
+  Node*            sproj  = new (C, 1) ProjNode(chkadd, CheckedAddNode::sum_proj_num);
+  Node*            oproj  = new (C, 1) FlagsProjNode(chkadd, CheckedAddNode::overflow_proj_num);
+  return chkadd;
+}
+
+//------------------------------match------------------------------------------
+// return result(s) along with their RegMask info
+Node* CheckedAddINode::match(const ProjNode* proj, const Matcher* match) {
+  uint ideal_reg = proj->ideal_reg();
+  RegMask rm;
+  if (proj->_con == sum_proj_num) {
+    rm = match->checkedAddI_sum_proj_mask();
+  } else {
+    assert(proj->_con == overflow_proj_num, "must be sum or overflow projection");
+    assert(ideal_reg == Op_RegFlags, "sanity");
+    rm = match->overflow_proj_mask();
+  }
+  return new (match->C, 1) MachProjNode(this, proj->_con, rm, ideal_reg);
+}
+
+
 //=============================================================================
 //------------------------------cc2logical-------------------------------------
 // Convert a condition code type to a logical type
@@ -1065,7 +1104,7 @@
 // Print special per-node info
 #ifndef PRODUCT
 void BoolTest::dump_on(outputStream *st) const {
-  const char *msg[] = {"eq","gt","??","lt","ne","le","??","ge"};
+  const char *msg[] = {"eq","gt","ov","lt","ne","le","no","ge","??"};
   st->print(msg[_test]);
 }
 #endif
diff -r 6f8f439e247d src/share/vm/opto/subnode.hpp
--- a/src/share/vm/opto/subnode.hpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/subnode.hpp	Thu Jun 21 20:48:06 2012 +0800
@@ -257,21 +257,78 @@
 };
 
 
+//------------------------------CmpAddINode-------------------------------------
+// Check the sum of two values for overflow, returning condition codes.
+class CmpAddINode : public CmpINode {
+public:
+  CmpAddINode(Node* in1, Node* in2) : CmpINode(in1, in2) {}
+  virtual int Opcode() const;
+  virtual Node* Ideal(PhaseGVN* phase, bool can_reshape) { return NULL; }
+  virtual const Type* Value(PhaseTransform* phase) const;
+};
+
+class FlagsProjNode : public ProjNode {
+public:
+  FlagsProjNode(Node* src, uint con) : ProjNode(src, con) {}
+
+  virtual bool is_CFG() const { return false; }
+  virtual const Type* bottom_type() const { return TypeInt::CC; }
+  virtual uint ideal_reg() const { return Op_RegFlags; }
+};
+
+//-----------------------------CheckedAddNode-----------------------------------
+// Addition with overflow condition
+class CheckedAddNode : public MultiNode {
+protected:
+  CheckedAddNode(Node* c, Node* in1, Node* in2);
+public:
+  enum {
+    sum_proj_num      = 0, // sum
+    overflow_proj_num = 1  // overflow condition
+  };
+  virtual int Opcode() const;
+  virtual Node* Identity(PhaseTransform* phase) { return this; }
+  virtual Node* Ideal(PhaseGVN* phase, bool can_reshape) { return NULL; }
+  virtual const Type* Value(PhaseTransform* phase) const { return bottom_type(); }
+  virtual uint hash() const { return Node::hash(); }
+  virtual bool is_CFG() const  { return false; }
+  virtual uint ideal_reg() const { return NotAMachineReg; }
+
+  ProjNode* sum_proj()      { return proj_out(sum_proj_num); }
+  ProjNode* overflow_proj() { return proj_out(overflow_proj_num); }
+};
+
+//-----------------------------CheckedAddINode----------------------------------
+// Integer addition with overflow condition
+class CheckedAddINode : public CheckedAddNode {
+public:
+  CheckedAddINode(Node* c, Node* in1, Node* in2) : CheckedAddNode(c, in1, in2) {}
+  virtual int Opcode() const;
+  virtual const Type* bottom_type() const { return TypeTuple::INT_CC_PAIR; }
+  virtual Node* match( const ProjNode *proj, const Matcher *m );
+
+  static CheckedAddINode* make(Compile* C, Node* cmpadd);
+};
+
+
 //------------------------------BoolTest---------------------------------------
 // Convert condition codes to a boolean test value (0 or -1).
 // We pick the values as 3 bits; the low order 2 bits we compare against the
 // condition codes, the high bit flips the sense of the result.
 struct BoolTest VALUE_OBJ_CLASS_SPEC {
-  enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, illegal = 8 };
+  enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, ov = 2, no = 6, illegal = 8 };
   mask _test;
   BoolTest( mask btm ) : _test(btm) {}
   const Type *cc2logical( const Type *CC ) const;
   // Commute the test.  I use a small table lookup.  The table is created as
   // a simple char array where each element is the ASCII version of a 'mask'
   // enum from above.
-  mask commute( ) const { return mask("038147858"[_test]-'0'); }
+  mask commute( ) const { return mask("036147258"[_test]-'0'); }
   mask negate( ) const { return mask(_test^4); }
-  bool is_canonical( ) const { return (_test == BoolTest::ne || _test == BoolTest::lt || _test == BoolTest::le); }
+  bool is_canonical( ) const { return (_test == BoolTest::ne ||
+                                       _test == BoolTest::lt ||
+                                       _test == BoolTest::le ||
+                                       _test == BoolTest::ov); }
 #ifndef PRODUCT
   void dump_on(outputStream *st) const;
 #endif
diff -r 6f8f439e247d src/share/vm/opto/type.cpp
--- a/src/share/vm/opto/type.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/type.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -386,6 +386,11 @@
   longpair[1] = TypeLong::LONG;
   TypeTuple::LONG_PAIR = TypeTuple::make(2, longpair);
 
+  const Type **int_cc = TypeTuple::fields(2);
+  int_cc[0] = TypeInt::INT;
+  int_cc[1] = TypeInt::CC;
+  TypeTuple::INT_CC_PAIR = TypeTuple::make(2, int_cc);
+
   _const_basic_type[T_NARROWOOP] = TypeNarrowOop::BOTTOM;
   _const_basic_type[T_BOOLEAN] = TypeInt::BOOL;
   _const_basic_type[T_CHAR]    = TypeInt::CHAR;
@@ -1618,6 +1623,7 @@
 const TypeTuple *TypeTuple::START_I2C;
 const TypeTuple *TypeTuple::INT_PAIR;
 const TypeTuple *TypeTuple::LONG_PAIR;
+const TypeTuple *TypeTuple::INT_CC_PAIR;
 
 
 //------------------------------make-------------------------------------------
diff -r 6f8f439e247d src/share/vm/opto/type.hpp
--- a/src/share/vm/opto/type.hpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/opto/type.hpp	Thu Jun 21 20:48:06 2012 +0800
@@ -549,6 +549,7 @@
   static const TypeTuple *START_I2C;
   static const TypeTuple *INT_PAIR;
   static const TypeTuple *LONG_PAIR;
+  static const TypeTuple *INT_CC_PAIR;
 #ifndef PRODUCT
   virtual void dump2( Dict &d, uint, outputStream *st  ) const; // Specialized per-Type dumping
 #endif
diff -r 6f8f439e247d src/share/vm/runtime/vmStructs.cpp
--- a/src/share/vm/runtime/vmStructs.cpp	Tue Jun 19 15:12:56 2012 -0700
+++ b/src/share/vm/runtime/vmStructs.cpp	Thu Jun 21 20:48:06 2012 +0800
@@ -1922,6 +1922,10 @@
   declare_c2_type(CmpF3Node, CmpFNode)                                    \
   declare_c2_type(CmpDNode, CmpNode)                                      \
   declare_c2_type(CmpD3Node, CmpDNode)                                    \
+  declare_c2_type(CmpAddINode, CmpINode)                                  \
+  declare_c2_type(CheckedAddNode, MultiNode)                              \
+  declare_c2_type(CheckedAddINode, CheckedAddNode)                        \
+  declare_c2_type(FlagsProjNode, ProjNode)                                \
   declare_c2_type(BoolNode, Node)                                         \
   declare_c2_type(AbsNode, Node)                                          \
   declare_c2_type(AbsINode, AbsNode)                                      \