1 /*
   2  * Copyright 1997-2009 Sun Microsystems, Inc.  All Rights Reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  20  * CA 95054 USA or visit www.sun.com if you need additional information or
  21  * have any questions.
  22  *
  23  */
  24 
  25 // Portions of code courtesy of Clifford Click
  26 
  27 // Optimization - Graph Style
  28 
  29 #include "incls/_precompiled.incl"
  30 #include "incls/_callnode.cpp.incl"
  31 
  32 //=============================================================================
  33 uint StartNode::size_of() const { return sizeof(*this); }
  34 uint StartNode::cmp( const Node &n ) const
  35 { return _domain == ((StartNode&)n)._domain; }
  36 const Type *StartNode::bottom_type() const { return _domain; }
  37 const Type *StartNode::Value(PhaseTransform *phase) const { return _domain; }
  38 #ifndef PRODUCT
  39 void StartNode::dump_spec(outputStream *st) const { st->print(" #"); _domain->dump_on(st);}
  40 #endif
  41 
  42 //------------------------------Ideal------------------------------------------
  43 Node *StartNode::Ideal(PhaseGVN *phase, bool can_reshape){
  44   return remove_dead_region(phase, can_reshape) ? this : NULL;
  45 }
  46 
  47 //------------------------------calling_convention-----------------------------
  48 void StartNode::calling_convention( BasicType* sig_bt, VMRegPair *parm_regs, uint argcnt ) const {
  49   Matcher::calling_convention( sig_bt, parm_regs, argcnt, false );
  50 }
  51 
  52 //------------------------------Registers--------------------------------------
  53 const RegMask &StartNode::in_RegMask(uint) const {
  54   return RegMask::Empty;
  55 }
  56 
  57 //------------------------------match------------------------------------------
  58 // Construct projections for incoming parameters, and their RegMask info
  59 Node *StartNode::match( const ProjNode *proj, const Matcher *match ) {
  60   switch (proj->_con) {
  61   case TypeFunc::Control:
  62   case TypeFunc::I_O:
  63   case TypeFunc::Memory:
  64     return new (match->C, 1) MachProjNode(this,proj->_con,RegMask::Empty,MachProjNode::unmatched_proj);
  65   case TypeFunc::FramePtr:
  66     return new (match->C, 1) MachProjNode(this,proj->_con,Matcher::c_frame_ptr_mask, Op_RegP);
  67   case TypeFunc::ReturnAdr:
  68     return new (match->C, 1) MachProjNode(this,proj->_con,match->_return_addr_mask,Op_RegP);
  69   case TypeFunc::Parms:
  70   default: {
  71       uint parm_num = proj->_con - TypeFunc::Parms;
  72       const Type *t = _domain->field_at(proj->_con);
  73       if (t->base() == Type::Half)  // 2nd half of Longs and Doubles
  74         return new (match->C, 1) ConNode(Type::TOP);
  75       uint ideal_reg = Matcher::base2reg[t->base()];
  76       RegMask &rm = match->_calling_convention_mask[parm_num];
  77       return new (match->C, 1) MachProjNode(this,proj->_con,rm,ideal_reg);
  78     }
  79   }
  80   return NULL;
  81 }
  82 
  83 //------------------------------StartOSRNode----------------------------------
  84 // The method start node for an on stack replacement adapter
  85 
  86 //------------------------------osr_domain-----------------------------
  87 const TypeTuple *StartOSRNode::osr_domain() {
  88   const Type **fields = TypeTuple::fields(2);
  89   fields[TypeFunc::Parms+0] = TypeRawPtr::BOTTOM;  // address of osr buffer
  90 
  91   return TypeTuple::make(TypeFunc::Parms+1, fields);
  92 }
  93 
  94 //=============================================================================
  95 const char * const ParmNode::names[TypeFunc::Parms+1] = {
  96   "Control", "I_O", "Memory", "FramePtr", "ReturnAdr", "Parms"
  97 };
  98 
  99 #ifndef PRODUCT
 100 void ParmNode::dump_spec(outputStream *st) const {
 101   if( _con < TypeFunc::Parms ) {
 102     st->print(names[_con]);
 103   } else {
 104     st->print("Parm%d: ",_con-TypeFunc::Parms);
 105     // Verbose and WizardMode dump bottom_type for all nodes
 106     if( !Verbose && !WizardMode )   bottom_type()->dump_on(st);
 107   }
 108 }
 109 #endif
 110 
 111 uint ParmNode::ideal_reg() const {
 112   switch( _con ) {
 113   case TypeFunc::Control  : // fall through
 114   case TypeFunc::I_O      : // fall through
 115   case TypeFunc::Memory   : return 0;
 116   case TypeFunc::FramePtr : // fall through
 117   case TypeFunc::ReturnAdr: return Op_RegP;
 118   default                 : assert( _con > TypeFunc::Parms, "" );
 119     // fall through
 120   case TypeFunc::Parms    : {
 121     // Type of argument being passed
 122     const Type *t = in(0)->as_Start()->_domain->field_at(_con);
 123     return Matcher::base2reg[t->base()];
 124   }
 125   }
 126   ShouldNotReachHere();
 127   return 0;
 128 }
 129 
 130 //=============================================================================
 131 ReturnNode::ReturnNode(uint edges, Node *cntrl, Node *i_o, Node *memory, Node *frameptr, Node *retadr ) : Node(edges) {
 132   init_req(TypeFunc::Control,cntrl);
 133   init_req(TypeFunc::I_O,i_o);
 134   init_req(TypeFunc::Memory,memory);
 135   init_req(TypeFunc::FramePtr,frameptr);
 136   init_req(TypeFunc::ReturnAdr,retadr);
 137 }
 138 
 139 Node *ReturnNode::Ideal(PhaseGVN *phase, bool can_reshape){
 140   return remove_dead_region(phase, can_reshape) ? this : NULL;
 141 }
 142 
 143 const Type *ReturnNode::Value( PhaseTransform *phase ) const {
 144   return ( phase->type(in(TypeFunc::Control)) == Type::TOP)
 145     ? Type::TOP
 146     : Type::BOTTOM;
 147 }
 148 
 149 // Do we Match on this edge index or not?  No edges on return nodes
 150 uint ReturnNode::match_edge(uint idx) const {
 151   return 0;
 152 }
 153 
 154 
 155 #ifndef PRODUCT
 156 void ReturnNode::dump_req() const {
 157   // Dump the required inputs, enclosed in '(' and ')'
 158   uint i;                       // Exit value of loop
 159   for( i=0; i<req(); i++ ) {    // For all required inputs
 160     if( i == TypeFunc::Parms ) tty->print("returns");
 161     if( in(i) ) tty->print("%c%d ", Compile::current()->node_arena()->contains(in(i)) ? ' ' : 'o', in(i)->_idx);
 162     else tty->print("_ ");
 163   }
 164 }
 165 #endif
 166 
 167 //=============================================================================
 168 RethrowNode::RethrowNode(
 169   Node* cntrl,
 170   Node* i_o,
 171   Node* memory,
 172   Node* frameptr,
 173   Node* ret_adr,
 174   Node* exception
 175 ) : Node(TypeFunc::Parms + 1) {
 176   init_req(TypeFunc::Control  , cntrl    );
 177   init_req(TypeFunc::I_O      , i_o      );
 178   init_req(TypeFunc::Memory   , memory   );
 179   init_req(TypeFunc::FramePtr , frameptr );
 180   init_req(TypeFunc::ReturnAdr, ret_adr);
 181   init_req(TypeFunc::Parms    , exception);
 182 }
 183 
 184 Node *RethrowNode::Ideal(PhaseGVN *phase, bool can_reshape){
 185   return remove_dead_region(phase, can_reshape) ? this : NULL;
 186 }
 187 
 188 const Type *RethrowNode::Value( PhaseTransform *phase ) const {
 189   return (phase->type(in(TypeFunc::Control)) == Type::TOP)
 190     ? Type::TOP
 191     : Type::BOTTOM;
 192 }
 193 
 194 uint RethrowNode::match_edge(uint idx) const {
 195   return 0;
 196 }
 197 
 198 #ifndef PRODUCT
 199 void RethrowNode::dump_req() const {
 200   // Dump the required inputs, enclosed in '(' and ')'
 201   uint i;                       // Exit value of loop
 202   for( i=0; i<req(); i++ ) {    // For all required inputs
 203     if( i == TypeFunc::Parms ) tty->print("exception");
 204     if( in(i) ) tty->print("%c%d ", Compile::current()->node_arena()->contains(in(i)) ? ' ' : 'o', in(i)->_idx);
 205     else tty->print("_ ");
 206   }
 207 }
 208 #endif
 209 
 210 //=============================================================================
 211 // Do we Match on this edge index or not?  Match only target address & method
 212 uint TailCallNode::match_edge(uint idx) const {
 213   return TypeFunc::Parms <= idx  &&  idx <= TypeFunc::Parms+1;
 214 }
 215 
 216 //=============================================================================
 217 // Do we Match on this edge index or not?  Match only target address & oop
 218 uint TailJumpNode::match_edge(uint idx) const {
 219   return TypeFunc::Parms <= idx  &&  idx <= TypeFunc::Parms+1;
 220 }
 221 
 222 //=============================================================================
 223 JVMState::JVMState(ciMethod* method, JVMState* caller) {
 224   assert(method != NULL, "must be valid call site");
 225   _method = method;
 226   _reexecute = Reexecute_Undefined;
 227   debug_only(_bci = -99);  // random garbage value
 228   debug_only(_map = (SafePointNode*)-1);
 229   _caller = caller;
 230   _depth  = 1 + (caller == NULL ? 0 : caller->depth());
 231   _locoff = TypeFunc::Parms;
 232   _stkoff = _locoff + _method->max_locals();
 233   _monoff = _stkoff + _method->max_stack();
 234   _scloff = _monoff;
 235   _endoff = _monoff;
 236   _sp = 0;
 237 }
 238 JVMState::JVMState(int stack_size) {
 239   _method = NULL;
 240   _bci = InvocationEntryBci;
 241   _reexecute = Reexecute_Undefined;
 242   debug_only(_map = (SafePointNode*)-1);
 243   _caller = NULL;
 244   _depth  = 1;
 245   _locoff = TypeFunc::Parms;
 246   _stkoff = _locoff;
 247   _monoff = _stkoff + stack_size;
 248   _scloff = _monoff;
 249   _endoff = _monoff;
 250   _sp = 0;
 251 }
 252 
 253 //--------------------------------of_depth-------------------------------------
 254 JVMState* JVMState::of_depth(int d) const {
 255   const JVMState* jvmp = this;
 256   assert(0 < d && (uint)d <= depth(), "oob");
 257   for (int skip = depth() - d; skip > 0; skip--) {
 258     jvmp = jvmp->caller();
 259   }
 260   assert(jvmp->depth() == (uint)d, "found the right one");
 261   return (JVMState*)jvmp;
 262 }
 263 
 264 //-----------------------------same_calls_as-----------------------------------
 265 bool JVMState::same_calls_as(const JVMState* that) const {
 266   if (this == that)                    return true;
 267   if (this->depth() != that->depth())  return false;
 268   const JVMState* p = this;
 269   const JVMState* q = that;
 270   for (;;) {
 271     if (p->_method != q->_method)    return false;
 272     if (p->_method == NULL)          return true;   // bci is irrelevant
 273     if (p->_bci    != q->_bci)       return false;
 274     if (p->_reexecute != q->_reexecute)  return false;
 275     p = p->caller();
 276     q = q->caller();
 277     if (p == q)                      return true;
 278     assert(p != NULL && q != NULL, "depth check ensures we don't run off end");
 279   }
 280 }
 281 
 282 //------------------------------debug_start------------------------------------
 283 uint JVMState::debug_start()  const {
 284   debug_only(JVMState* jvmroot = of_depth(1));
 285   assert(jvmroot->locoff() <= this->locoff(), "youngest JVMState must be last");
 286   return of_depth(1)->locoff();
 287 }
 288 
 289 //-------------------------------debug_end-------------------------------------
 290 uint JVMState::debug_end() const {
 291   debug_only(JVMState* jvmroot = of_depth(1));
 292   assert(jvmroot->endoff() <= this->endoff(), "youngest JVMState must be last");
 293   return endoff();
 294 }
 295 
 296 //------------------------------debug_depth------------------------------------
 297 uint JVMState::debug_depth() const {
 298   uint total = 0;
 299   for (const JVMState* jvmp = this; jvmp != NULL; jvmp = jvmp->caller()) {
 300     total += jvmp->debug_size();
 301   }
 302   return total;
 303 }
 304 
 305 #ifndef PRODUCT
 306 
 307 //------------------------------format_helper----------------------------------
 308 // Given an allocation (a Chaitin object) and a Node decide if the Node carries
 309 // any defined value or not.  If it does, print out the register or constant.
 310 static void format_helper( PhaseRegAlloc *regalloc, outputStream* st, Node *n, const char *msg, uint i, GrowableArray<SafePointScalarObjectNode*> *scobjs ) {
 311   if (n == NULL) { st->print(" NULL"); return; }
 312   if (n->is_SafePointScalarObject()) {
 313     // Scalar replacement.
 314     SafePointScalarObjectNode* spobj = n->as_SafePointScalarObject();
 315     scobjs->append_if_missing(spobj);
 316     int sco_n = scobjs->find(spobj);
 317     assert(sco_n >= 0, "");
 318     st->print(" %s%d]=#ScObj" INT32_FORMAT, msg, i, sco_n);
 319     return;
 320   }
 321   if( OptoReg::is_valid(regalloc->get_reg_first(n))) { // Check for undefined
 322     char buf[50];
 323     regalloc->dump_register(n,buf);
 324     st->print(" %s%d]=%s",msg,i,buf);
 325   } else {                      // No register, but might be constant
 326     const Type *t = n->bottom_type();
 327     switch (t->base()) {
 328     case Type::Int:
 329       st->print(" %s%d]=#"INT32_FORMAT,msg,i,t->is_int()->get_con());
 330       break;
 331     case Type::AnyPtr:
 332       assert( t == TypePtr::NULL_PTR, "" );
 333       st->print(" %s%d]=#NULL",msg,i);
 334       break;
 335     case Type::AryPtr:
 336     case Type::KlassPtr:
 337     case Type::InstPtr:
 338       st->print(" %s%d]=#Ptr" INTPTR_FORMAT,msg,i,t->isa_oopptr()->const_oop());
 339       break;
 340     case Type::NarrowOop:
 341       st->print(" %s%d]=#Ptr" INTPTR_FORMAT,msg,i,t->make_ptr()->isa_oopptr()->const_oop());
 342       break;
 343     case Type::RawPtr:
 344       st->print(" %s%d]=#Raw" INTPTR_FORMAT,msg,i,t->is_rawptr());
 345       break;
 346     case Type::DoubleCon:
 347       st->print(" %s%d]=#%fD",msg,i,t->is_double_constant()->_d);
 348       break;
 349     case Type::FloatCon:
 350       st->print(" %s%d]=#%fF",msg,i,t->is_float_constant()->_f);
 351       break;
 352     case Type::Long:
 353       st->print(" %s%d]=#"INT64_FORMAT,msg,i,t->is_long()->get_con());
 354       break;
 355     case Type::Half:
 356     case Type::Top:
 357       st->print(" %s%d]=_",msg,i);
 358       break;
 359     default: ShouldNotReachHere();
 360     }
 361   }
 362 }
 363 
 364 //------------------------------format-----------------------------------------
 365 void JVMState::format(PhaseRegAlloc *regalloc, const Node *n, outputStream* st) const {
 366   st->print("        #");
 367   if( _method ) {
 368     _method->print_short_name(st);
 369     st->print(" @ bci:%d ",_bci);
 370   } else {
 371     st->print_cr(" runtime stub ");
 372     return;
 373   }
 374   if (n->is_MachSafePoint()) {
 375     GrowableArray<SafePointScalarObjectNode*> scobjs;
 376     MachSafePointNode *mcall = n->as_MachSafePoint();
 377     uint i;
 378     // Print locals
 379     for( i = 0; i < (uint)loc_size(); i++ )
 380       format_helper( regalloc, st, mcall->local(this, i), "L[", i, &scobjs );
 381     // Print stack
 382     for (i = 0; i < (uint)stk_size(); i++) {
 383       if ((uint)(_stkoff + i) >= mcall->len())
 384         st->print(" oob ");
 385       else
 386        format_helper( regalloc, st, mcall->stack(this, i), "STK[", i, &scobjs );
 387     }
 388     for (i = 0; (int)i < nof_monitors(); i++) {
 389       Node *box = mcall->monitor_box(this, i);
 390       Node *obj = mcall->monitor_obj(this, i);
 391       if ( OptoReg::is_valid(regalloc->get_reg_first(box)) ) {
 392         while( !box->is_BoxLock() )  box = box->in(1);
 393         format_helper( regalloc, st, box, "MON-BOX[", i, &scobjs );
 394       } else {
 395         OptoReg::Name box_reg = BoxLockNode::stack_slot(box);
 396         st->print(" MON-BOX%d=%s+%d",
 397                    i,
 398                    OptoReg::regname(OptoReg::c_frame_pointer),
 399                    regalloc->reg2offset(box_reg));
 400       }
 401       const char* obj_msg = "MON-OBJ[";
 402       if (EliminateLocks) {
 403         while( !box->is_BoxLock() )  box = box->in(1);
 404         if (box->as_BoxLock()->is_eliminated())
 405           obj_msg = "MON-OBJ(LOCK ELIMINATED)[";
 406       }
 407       format_helper( regalloc, st, obj, obj_msg, i, &scobjs );
 408     }
 409 
 410     for (i = 0; i < (uint)scobjs.length(); i++) {
 411       // Scalar replaced objects.
 412       st->print_cr("");
 413       st->print("        # ScObj" INT32_FORMAT " ", i);
 414       SafePointScalarObjectNode* spobj = scobjs.at(i);
 415       ciKlass* cik = spobj->bottom_type()->is_oopptr()->klass();
 416       assert(cik->is_instance_klass() ||
 417              cik->is_array_klass(), "Not supported allocation.");
 418       ciInstanceKlass *iklass = NULL;
 419       if (cik->is_instance_klass()) {
 420         cik->print_name_on(st);
 421         iklass = cik->as_instance_klass();
 422       } else if (cik->is_type_array_klass()) {
 423         cik->as_array_klass()->base_element_type()->print_name_on(st);
 424         st->print("[%d]", spobj->n_fields());
 425       } else if (cik->is_obj_array_klass()) {
 426         ciKlass* cie = cik->as_obj_array_klass()->base_element_klass();
 427         if (cie->is_instance_klass()) {
 428           cie->print_name_on(st);
 429         } else if (cie->is_type_array_klass()) {
 430           cie->as_array_klass()->base_element_type()->print_name_on(st);
 431         } else {
 432           ShouldNotReachHere();
 433         }
 434         st->print("[%d]", spobj->n_fields());
 435         int ndim = cik->as_array_klass()->dimension() - 1;
 436         while (ndim-- > 0) {
 437           st->print("[]");
 438         }
 439       }
 440       st->print("={");
 441       uint nf = spobj->n_fields();
 442       if (nf > 0) {
 443         uint first_ind = spobj->first_index();
 444         Node* fld_node = mcall->in(first_ind);
 445         ciField* cifield;
 446         if (iklass != NULL) {
 447           st->print(" [");
 448           cifield = iklass->nonstatic_field_at(0);
 449           cifield->print_name_on(st);
 450           format_helper( regalloc, st, fld_node, ":", 0, &scobjs );
 451         } else {
 452           format_helper( regalloc, st, fld_node, "[", 0, &scobjs );
 453         }
 454         for (uint j = 1; j < nf; j++) {
 455           fld_node = mcall->in(first_ind+j);
 456           if (iklass != NULL) {
 457             st->print(", [");
 458             cifield = iklass->nonstatic_field_at(j);
 459             cifield->print_name_on(st);
 460             format_helper( regalloc, st, fld_node, ":", j, &scobjs );
 461           } else {
 462             format_helper( regalloc, st, fld_node, ", [", j, &scobjs );
 463           }
 464         }
 465       }
 466       st->print(" }");
 467     }
 468   }
 469   st->print_cr("");
 470   if (caller() != NULL)  caller()->format(regalloc, n, st);
 471 }
 472 
 473 
 474 void JVMState::dump_spec(outputStream *st) const {
 475   if (_method != NULL) {
 476     bool printed = false;
 477     if (!Verbose) {
 478       // The JVMS dumps make really, really long lines.
 479       // Take out the most boring parts, which are the package prefixes.
 480       char buf[500];
 481       stringStream namest(buf, sizeof(buf));
 482       _method->print_short_name(&namest);
 483       if (namest.count() < sizeof(buf)) {
 484         const char* name = namest.base();
 485         if (name[0] == ' ')  ++name;
 486         const char* endcn = strchr(name, ':');  // end of class name
 487         if (endcn == NULL)  endcn = strchr(name, '(');
 488         if (endcn == NULL)  endcn = name + strlen(name);
 489         while (endcn > name && endcn[-1] != '.' && endcn[-1] != '/')
 490           --endcn;
 491         st->print(" %s", endcn);
 492         printed = true;
 493       }
 494     }
 495     if (!printed)
 496       _method->print_short_name(st);
 497     st->print(" @ bci:%d",_bci);
 498     if(_reexecute == Reexecute_True)
 499       st->print(" reexecute");
 500   } else {
 501     st->print(" runtime stub");
 502   }
 503   if (caller() != NULL)  caller()->dump_spec(st);
 504 }
 505 
 506 
 507 void JVMState::dump_on(outputStream* st) const {
 508   if (_map && !((uintptr_t)_map & 1)) {
 509     if (_map->len() > _map->req()) {  // _map->has_exceptions()
 510       Node* ex = _map->in(_map->req());  // _map->next_exception()
 511       // skip the first one; it's already being printed
 512       while (ex != NULL && ex->len() > ex->req()) {
 513         ex = ex->in(ex->req());  // ex->next_exception()
 514         ex->dump(1);
 515       }
 516     }
 517     _map->dump(2);
 518   }
 519   st->print("JVMS depth=%d loc=%d stk=%d mon=%d scalar=%d end=%d mondepth=%d sp=%d bci=%d reexecute=%s method=",
 520              depth(), locoff(), stkoff(), monoff(), scloff(), endoff(), monitor_depth(), sp(), bci(), should_reexecute()?"true":"false");
 521   if (_method == NULL) {
 522     st->print_cr("(none)");
 523   } else {
 524     _method->print_name(st);
 525     st->cr();
 526     if (bci() >= 0 && bci() < _method->code_size()) {
 527       st->print("    bc: ");
 528       _method->print_codes_on(bci(), bci()+1, st);
 529     }
 530   }
 531   if (caller() != NULL) {
 532     caller()->dump_on(st);
 533   }
 534 }
 535 
 536 // Extra way to dump a jvms from the debugger,
 537 // to avoid a bug with C++ member function calls.
 538 void dump_jvms(JVMState* jvms) {
 539   jvms->dump();
 540 }
 541 #endif
 542 
 543 //--------------------------clone_shallow--------------------------------------
 544 JVMState* JVMState::clone_shallow(Compile* C) const {
 545   JVMState* n = has_method() ? new (C) JVMState(_method, _caller) : new (C) JVMState(0);
 546   n->set_bci(_bci);
 547   n->_reexecute = _reexecute;
 548   n->set_locoff(_locoff);
 549   n->set_stkoff(_stkoff);
 550   n->set_monoff(_monoff);
 551   n->set_scloff(_scloff);
 552   n->set_endoff(_endoff);
 553   n->set_sp(_sp);
 554   n->set_map(_map);
 555   return n;
 556 }
 557 
 558 //---------------------------clone_deep----------------------------------------
 559 JVMState* JVMState::clone_deep(Compile* C) const {
 560   JVMState* n = clone_shallow(C);
 561   for (JVMState* p = n; p->_caller != NULL; p = p->_caller) {
 562     p->_caller = p->_caller->clone_shallow(C);
 563   }
 564   assert(n->depth() == depth(), "sanity");
 565   assert(n->debug_depth() == debug_depth(), "sanity");
 566   return n;
 567 }
 568 
 569 //=============================================================================
 570 uint CallNode::cmp( const Node &n ) const
 571 { return _tf == ((CallNode&)n)._tf && _jvms == ((CallNode&)n)._jvms; }
 572 #ifndef PRODUCT
 573 void CallNode::dump_req() const {
 574   // Dump the required inputs, enclosed in '(' and ')'
 575   uint i;                       // Exit value of loop
 576   for( i=0; i<req(); i++ ) {    // For all required inputs
 577     if( i == TypeFunc::Parms ) tty->print("(");
 578     if( in(i) ) tty->print("%c%d ", Compile::current()->node_arena()->contains(in(i)) ? ' ' : 'o', in(i)->_idx);
 579     else tty->print("_ ");
 580   }
 581   tty->print(")");
 582 }
 583 
 584 void CallNode::dump_spec(outputStream *st) const {
 585   st->print(" ");
 586   tf()->dump_on(st);
 587   if (_cnt != COUNT_UNKNOWN)  st->print(" C=%f",_cnt);
 588   if (jvms() != NULL)  jvms()->dump_spec(st);
 589 }
 590 #endif
 591 
 592 const Type *CallNode::bottom_type() const { return tf()->range(); }
 593 const Type *CallNode::Value(PhaseTransform *phase) const {
 594   if (phase->type(in(0)) == Type::TOP)  return Type::TOP;
 595   return tf()->range();
 596 }
 597 
 598 //------------------------------calling_convention-----------------------------
 599 void CallNode::calling_convention( BasicType* sig_bt, VMRegPair *parm_regs, uint argcnt ) const {
 600   // Use the standard compiler calling convention
 601   Matcher::calling_convention( sig_bt, parm_regs, argcnt, true );
 602 }
 603 
 604 
 605 //------------------------------match------------------------------------------
 606 // Construct projections for control, I/O, memory-fields, ..., and
 607 // return result(s) along with their RegMask info
 608 Node *CallNode::match( const ProjNode *proj, const Matcher *match ) {
 609   switch (proj->_con) {
 610   case TypeFunc::Control:
 611   case TypeFunc::I_O:
 612   case TypeFunc::Memory:
 613     return new (match->C, 1) MachProjNode(this,proj->_con,RegMask::Empty,MachProjNode::unmatched_proj);
 614 
 615   case TypeFunc::Parms+1:       // For LONG & DOUBLE returns
 616     assert(tf()->_range->field_at(TypeFunc::Parms+1) == Type::HALF, "");
 617     // 2nd half of doubles and longs
 618     return new (match->C, 1) MachProjNode(this,proj->_con, RegMask::Empty, (uint)OptoReg::Bad);
 619 
 620   case TypeFunc::Parms: {       // Normal returns
 621     uint ideal_reg = Matcher::base2reg[tf()->range()->field_at(TypeFunc::Parms)->base()];
 622     OptoRegPair regs = is_CallRuntime()
 623       ? match->c_return_value(ideal_reg,true)  // Calls into C runtime
 624       : match->  return_value(ideal_reg,true); // Calls into compiled Java code
 625     RegMask rm = RegMask(regs.first());
 626     if( OptoReg::is_valid(regs.second()) )
 627       rm.Insert( regs.second() );
 628     return new (match->C, 1) MachProjNode(this,proj->_con,rm,ideal_reg);
 629   }
 630 
 631   case TypeFunc::ReturnAdr:
 632   case TypeFunc::FramePtr:
 633   default:
 634     ShouldNotReachHere();
 635   }
 636   return NULL;
 637 }
 638 
 639 // Do we Match on this edge index or not?  Match no edges
 640 uint CallNode::match_edge(uint idx) const {
 641   return 0;
 642 }
 643 
 644 //
 645 // Determine whether the call could modify the field of the specified
 646 // instance at the specified offset.
 647 //
 648 bool CallNode::may_modify(const TypePtr *addr_t, PhaseTransform *phase) {
 649   const TypeOopPtr *adrInst_t  = addr_t->isa_oopptr();
 650 
 651   // If not an OopPtr or not an instance type, assume the worst.
 652   // Note: currently this method is called only for instance types.
 653   if (adrInst_t == NULL || !adrInst_t->is_known_instance()) {
 654     return true;
 655   }
 656   // The instance_id is set only for scalar-replaceable allocations which
 657   // are not passed as arguments according to Escape Analysis.
 658   return false;
 659 }
 660 
 661 // Does this call have a direct reference to n other than debug information?
 662 bool CallNode::has_non_debug_use(Node *n) {
 663   const TypeTuple * d = tf()->domain();
 664   for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
 665     Node *arg = in(i);
 666     if (arg == n) {
 667       return true;
 668     }
 669   }
 670   return false;
 671 }
 672 
 673 // Returns the unique CheckCastPP of a call
 674 // or 'this' if there are several CheckCastPP
 675 // or returns NULL if there is no one.
 676 Node *CallNode::result_cast() {
 677   Node *cast = NULL;
 678 
 679   Node *p = proj_out(TypeFunc::Parms);
 680   if (p == NULL)
 681     return NULL;
 682 
 683   for (DUIterator_Fast imax, i = p->fast_outs(imax); i < imax; i++) {
 684     Node *use = p->fast_out(i);
 685     if (use->is_CheckCastPP()) {
 686       if (cast != NULL) {
 687         return this;  // more than 1 CheckCastPP
 688       }
 689       cast = use;
 690     }
 691   }
 692   return cast;
 693 }
 694 
 695 
 696 //=============================================================================
 697 uint CallJavaNode::size_of() const { return sizeof(*this); }
 698 uint CallJavaNode::cmp( const Node &n ) const {
 699   CallJavaNode &call = (CallJavaNode&)n;
 700   return CallNode::cmp(call) && _method == call._method;
 701 }
 702 #ifndef PRODUCT
 703 void CallJavaNode::dump_spec(outputStream *st) const {
 704   if( _method ) _method->print_short_name(st);
 705   CallNode::dump_spec(st);
 706 }
 707 #endif
 708 
 709 //=============================================================================
 710 uint CallStaticJavaNode::size_of() const { return sizeof(*this); }
 711 uint CallStaticJavaNode::cmp( const Node &n ) const {
 712   CallStaticJavaNode &call = (CallStaticJavaNode&)n;
 713   return CallJavaNode::cmp(call);
 714 }
 715 
 716 //----------------------------uncommon_trap_request----------------------------
 717 // If this is an uncommon trap, return the request code, else zero.
 718 int CallStaticJavaNode::uncommon_trap_request() const {
 719   if (_name != NULL && !strcmp(_name, "uncommon_trap")) {
 720     return extract_uncommon_trap_request(this);
 721   }
 722   return 0;
 723 }
 724 int CallStaticJavaNode::extract_uncommon_trap_request(const Node* call) {
 725 #ifndef PRODUCT
 726   if (!(call->req() > TypeFunc::Parms &&
 727         call->in(TypeFunc::Parms) != NULL &&
 728         call->in(TypeFunc::Parms)->is_Con())) {
 729     assert(_in_dump_cnt != 0, "OK if dumping");
 730     tty->print("[bad uncommon trap]");
 731     return 0;
 732   }
 733 #endif
 734   return call->in(TypeFunc::Parms)->bottom_type()->is_int()->get_con();
 735 }
 736 
 737 #ifndef PRODUCT
 738 void CallStaticJavaNode::dump_spec(outputStream *st) const {
 739   st->print("# Static ");
 740   if (_name != NULL) {
 741     st->print("%s", _name);
 742     int trap_req = uncommon_trap_request();
 743     if (trap_req != 0) {
 744       char buf[100];
 745       st->print("(%s)",
 746                  Deoptimization::format_trap_request(buf, sizeof(buf),
 747                                                      trap_req));
 748     }
 749     st->print(" ");
 750   }
 751   CallJavaNode::dump_spec(st);
 752 }
 753 #endif
 754 
 755 //=============================================================================
 756 uint CallDynamicJavaNode::size_of() const { return sizeof(*this); }
 757 uint CallDynamicJavaNode::cmp( const Node &n ) const {
 758   CallDynamicJavaNode &call = (CallDynamicJavaNode&)n;
 759   return CallJavaNode::cmp(call);
 760 }
 761 #ifndef PRODUCT
 762 void CallDynamicJavaNode::dump_spec(outputStream *st) const {
 763   st->print("# Dynamic ");
 764   CallJavaNode::dump_spec(st);
 765 }
 766 #endif
 767 
 768 //=============================================================================
 769 uint CallRuntimeNode::size_of() const { return sizeof(*this); }
 770 uint CallRuntimeNode::cmp( const Node &n ) const {
 771   CallRuntimeNode &call = (CallRuntimeNode&)n;
 772   return CallNode::cmp(call) && !strcmp(_name,call._name);
 773 }
 774 #ifndef PRODUCT
 775 void CallRuntimeNode::dump_spec(outputStream *st) const {
 776   st->print("# ");
 777   st->print(_name);
 778   CallNode::dump_spec(st);
 779 }
 780 #endif
 781 
 782 //------------------------------calling_convention-----------------------------
 783 void CallRuntimeNode::calling_convention( BasicType* sig_bt, VMRegPair *parm_regs, uint argcnt ) const {
 784   Matcher::c_calling_convention( sig_bt, parm_regs, argcnt );
 785 }
 786 
 787 //=============================================================================
 788 //------------------------------calling_convention-----------------------------
 789 
 790 
 791 //=============================================================================
 792 #ifndef PRODUCT
 793 void CallLeafNode::dump_spec(outputStream *st) const {
 794   st->print("# ");
 795   st->print(_name);
 796   CallNode::dump_spec(st);
 797 }
 798 #endif
 799 
 800 //=============================================================================
 801 
 802 void SafePointNode::set_local(JVMState* jvms, uint idx, Node *c) {
 803   assert(verify_jvms(jvms), "jvms must match");
 804   int loc = jvms->locoff() + idx;
 805   if (in(loc)->is_top() && idx > 0 && !c->is_top() ) {
 806     // If current local idx is top then local idx - 1 could
 807     // be a long/double that needs to be killed since top could
 808     // represent the 2nd half ofthe long/double.
 809     uint ideal = in(loc -1)->ideal_reg();
 810     if (ideal == Op_RegD || ideal == Op_RegL) {
 811       // set other (low index) half to top
 812       set_req(loc - 1, in(loc));
 813     }
 814   }
 815   set_req(loc, c);
 816 }
 817 
 818 uint SafePointNode::size_of() const { return sizeof(*this); }
 819 uint SafePointNode::cmp( const Node &n ) const {
 820   return (&n == this);          // Always fail except on self
 821 }
 822 
 823 //-------------------------set_next_exception----------------------------------
 824 void SafePointNode::set_next_exception(SafePointNode* n) {
 825   assert(n == NULL || n->Opcode() == Op_SafePoint, "correct value for next_exception");
 826   if (len() == req()) {
 827     if (n != NULL)  add_prec(n);
 828   } else {
 829     set_prec(req(), n);
 830   }
 831 }
 832 
 833 
 834 //----------------------------next_exception-----------------------------------
 835 SafePointNode* SafePointNode::next_exception() const {
 836   if (len() == req()) {
 837     return NULL;
 838   } else {
 839     Node* n = in(req());
 840     assert(n == NULL || n->Opcode() == Op_SafePoint, "no other uses of prec edges");
 841     return (SafePointNode*) n;
 842   }
 843 }
 844 
 845 
 846 //------------------------------Ideal------------------------------------------
 847 // Skip over any collapsed Regions
 848 Node *SafePointNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 849   return remove_dead_region(phase, can_reshape) ? this : NULL;
 850 }
 851 
 852 //------------------------------Identity---------------------------------------
 853 // Remove obviously duplicate safepoints
 854 Node *SafePointNode::Identity( PhaseTransform *phase ) {
 855 
 856   // If you have back to back safepoints, remove one
 857   if( in(TypeFunc::Control)->is_SafePoint() )
 858     return in(TypeFunc::Control);
 859 
 860   if( in(0)->is_Proj() ) {
 861     Node *n0 = in(0)->in(0);
 862     // Check if he is a call projection (except Leaf Call)
 863     if( n0->is_Catch() ) {
 864       n0 = n0->in(0)->in(0);
 865       assert( n0->is_Call(), "expect a call here" );
 866     }
 867     if( n0->is_Call() && n0->as_Call()->guaranteed_safepoint() ) {
 868       // Useless Safepoint, so remove it
 869       return in(TypeFunc::Control);
 870     }
 871   }
 872 
 873   return this;
 874 }
 875 
 876 //------------------------------Value------------------------------------------
 877 const Type *SafePointNode::Value( PhaseTransform *phase ) const {
 878   if( phase->type(in(0)) == Type::TOP ) return Type::TOP;
 879   if( phase->eqv( in(0), this ) ) return Type::TOP; // Dead infinite loop
 880   return Type::CONTROL;
 881 }
 882 
 883 #ifndef PRODUCT
 884 void SafePointNode::dump_spec(outputStream *st) const {
 885   st->print(" SafePoint ");
 886 }
 887 #endif
 888 
 889 const RegMask &SafePointNode::in_RegMask(uint idx) const {
 890   if( idx < TypeFunc::Parms ) return RegMask::Empty;
 891   // Values outside the domain represent debug info
 892   return *(Compile::current()->matcher()->idealreg2debugmask[in(idx)->ideal_reg()]);
 893 }
 894 const RegMask &SafePointNode::out_RegMask() const {
 895   return RegMask::Empty;
 896 }
 897 
 898 
 899 void SafePointNode::grow_stack(JVMState* jvms, uint grow_by) {
 900   assert((int)grow_by > 0, "sanity");
 901   int monoff = jvms->monoff();
 902   int scloff = jvms->scloff();
 903   int endoff = jvms->endoff();
 904   assert(endoff == (int)req(), "no other states or debug info after me");
 905   Node* top = Compile::current()->top();
 906   for (uint i = 0; i < grow_by; i++) {
 907     ins_req(monoff, top);
 908   }
 909   jvms->set_monoff(monoff + grow_by);
 910   jvms->set_scloff(scloff + grow_by);
 911   jvms->set_endoff(endoff + grow_by);
 912 }
 913 
 914 void SafePointNode::push_monitor(const FastLockNode *lock) {
 915   // Add a LockNode, which points to both the original BoxLockNode (the
 916   // stack space for the monitor) and the Object being locked.
 917   const int MonitorEdges = 2;
 918   assert(JVMState::logMonitorEdges == exact_log2(MonitorEdges), "correct MonitorEdges");
 919   assert(req() == jvms()->endoff(), "correct sizing");
 920   int nextmon = jvms()->scloff();
 921   if (GenerateSynchronizationCode) {
 922     add_req(lock->box_node());
 923     add_req(lock->obj_node());
 924   } else {
 925     Node* top = Compile::current()->top();
 926     add_req(top);
 927     add_req(top);
 928   }
 929   jvms()->set_scloff(nextmon+MonitorEdges);
 930   jvms()->set_endoff(req());
 931 }
 932 
 933 void SafePointNode::pop_monitor() {
 934   // Delete last monitor from debug info
 935   debug_only(int num_before_pop = jvms()->nof_monitors());
 936   const int MonitorEdges = (1<<JVMState::logMonitorEdges);
 937   int scloff = jvms()->scloff();
 938   int endoff = jvms()->endoff();
 939   int new_scloff = scloff - MonitorEdges;
 940   int new_endoff = endoff - MonitorEdges;
 941   jvms()->set_scloff(new_scloff);
 942   jvms()->set_endoff(new_endoff);
 943   while (scloff > new_scloff)  del_req(--scloff);
 944   assert(jvms()->nof_monitors() == num_before_pop-1, "");
 945 }
 946 
 947 Node *SafePointNode::peek_monitor_box() const {
 948   int mon = jvms()->nof_monitors() - 1;
 949   assert(mon >= 0, "most have a monitor");
 950   return monitor_box(jvms(), mon);
 951 }
 952 
 953 Node *SafePointNode::peek_monitor_obj() const {
 954   int mon = jvms()->nof_monitors() - 1;
 955   assert(mon >= 0, "most have a monitor");
 956   return monitor_obj(jvms(), mon);
 957 }
 958 
 959 // Do we Match on this edge index or not?  Match no edges
 960 uint SafePointNode::match_edge(uint idx) const {
 961   if( !needs_polling_address_input() )
 962     return 0;
 963 
 964   return (TypeFunc::Parms == idx);
 965 }
 966 
 967 //==============  SafePointScalarObjectNode  ==============
 968 
 969 SafePointScalarObjectNode::SafePointScalarObjectNode(const TypeOopPtr* tp,
 970 #ifdef ASSERT
 971                                                      AllocateNode* alloc,
 972 #endif
 973                                                      uint first_index,
 974                                                      uint n_fields) :
 975   TypeNode(tp, 1), // 1 control input -- seems required.  Get from root.
 976 #ifdef ASSERT
 977   _alloc(alloc),
 978 #endif
 979   _first_index(first_index),
 980   _n_fields(n_fields)
 981 {
 982   init_class_id(Class_SafePointScalarObject);
 983 }
 984 
 985 bool SafePointScalarObjectNode::pinned() const { return true; }
 986 bool SafePointScalarObjectNode::depends_only_on_test() const { return false; }
 987 
 988 uint SafePointScalarObjectNode::ideal_reg() const {
 989   return 0; // No matching to machine instruction
 990 }
 991 
 992 const RegMask &SafePointScalarObjectNode::in_RegMask(uint idx) const {
 993   return *(Compile::current()->matcher()->idealreg2debugmask[in(idx)->ideal_reg()]);
 994 }
 995 
 996 const RegMask &SafePointScalarObjectNode::out_RegMask() const {
 997   return RegMask::Empty;
 998 }
 999 
1000 uint SafePointScalarObjectNode::match_edge(uint idx) const {
1001   return 0;
1002 }
1003 
1004 SafePointScalarObjectNode*
1005 SafePointScalarObjectNode::clone(int jvms_adj, Dict* sosn_map) const {
1006   void* cached = (*sosn_map)[(void*)this];
1007   if (cached != NULL) {
1008     return (SafePointScalarObjectNode*)cached;
1009   }
1010   Compile* C = Compile::current();
1011   SafePointScalarObjectNode* res = (SafePointScalarObjectNode*)Node::clone();
1012   res->_first_index += jvms_adj;
1013   sosn_map->Insert((void*)this, (void*)res);
1014   return res;
1015 }
1016 
1017 
1018 #ifndef PRODUCT
1019 void SafePointScalarObjectNode::dump_spec(outputStream *st) const {
1020   st->print(" # fields@[%d..%d]", first_index(),
1021              first_index() + n_fields() - 1);
1022 }
1023 
1024 #endif
1025 
1026 //=============================================================================
1027 uint AllocateNode::size_of() const { return sizeof(*this); }
1028 
1029 AllocateNode::AllocateNode(Compile* C, const TypeFunc *atype,
1030                            Node *ctrl, Node *mem, Node *abio,
1031                            Node *size, Node *klass_node, Node *initial_test)
1032   : CallNode(atype, NULL, TypeRawPtr::BOTTOM)
1033 {
1034   init_class_id(Class_Allocate);
1035   init_flags(Flag_is_macro);
1036   _is_scalar_replaceable = false;
1037   Node *topnode = C->top();
1038 
1039   init_req( TypeFunc::Control  , ctrl );
1040   init_req( TypeFunc::I_O      , abio );
1041   init_req( TypeFunc::Memory   , mem );
1042   init_req( TypeFunc::ReturnAdr, topnode );
1043   init_req( TypeFunc::FramePtr , topnode );
1044   init_req( AllocSize          , size);
1045   init_req( KlassNode          , klass_node);
1046   init_req( InitialTest        , initial_test);
1047   init_req( ALength            , topnode);
1048   C->add_macro_node(this);
1049 }
1050 
1051 //=============================================================================
1052 uint AllocateArrayNode::size_of() const { return sizeof(*this); }
1053 
1054 Node* AllocateArrayNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1055   if (remove_dead_region(phase, can_reshape))  return this;
1056 
1057   const Type* type = phase->type(Ideal_length());
1058   if (type->isa_int() && type->is_int()->_hi < 0) {
1059     if (can_reshape) {
1060       PhaseIterGVN *igvn = phase->is_IterGVN();
1061       // Unreachable fall through path (negative array length),
1062       // the allocation can only throw so disconnect it.
1063       Node* proj = proj_out(TypeFunc::Control);
1064       Node* catchproj = NULL;
1065       if (proj != NULL) {
1066         for (DUIterator_Fast imax, i = proj->fast_outs(imax); i < imax; i++) {
1067           Node *cn = proj->fast_out(i);
1068           if (cn->is_Catch()) {
1069             catchproj = cn->as_Multi()->proj_out(CatchProjNode::fall_through_index);
1070             break;
1071           }
1072         }
1073       }
1074       if (catchproj != NULL && catchproj->outcnt() > 0 &&
1075           (catchproj->outcnt() > 1 ||
1076            catchproj->unique_out()->Opcode() != Op_Halt)) {
1077         assert(catchproj->is_CatchProj(), "must be a CatchProjNode");
1078         Node* nproj = catchproj->clone();
1079         igvn->register_new_node_with_optimizer(nproj);
1080 
1081         Node *frame = new (phase->C, 1) ParmNode( phase->C->start(), TypeFunc::FramePtr );
1082         frame = phase->transform(frame);
1083         // Halt & Catch Fire
1084         Node *halt = new (phase->C, TypeFunc::Parms) HaltNode( nproj, frame );
1085         phase->C->root()->add_req(halt);
1086         phase->transform(halt);
1087 
1088         igvn->replace_node(catchproj, phase->C->top());
1089         return this;
1090       }
1091     } else {
1092       // Can't correct it during regular GVN so register for IGVN
1093       phase->C->record_for_igvn(this);
1094     }
1095   }
1096   return NULL;
1097 }
1098 
1099 // Retrieve the length from the AllocateArrayNode. Narrow the type with a
1100 // CastII, if appropriate.  If we are not allowed to create new nodes, and
1101 // a CastII is appropriate, return NULL.
1102 Node *AllocateArrayNode::make_ideal_length(const TypeOopPtr* oop_type, PhaseTransform *phase, bool allow_new_nodes) {
1103   Node *length = in(AllocateNode::ALength);
1104   assert(length != NULL, "length is not null");
1105 
1106   const TypeInt* length_type = phase->find_int_type(length);
1107   const TypeAryPtr* ary_type = oop_type->isa_aryptr();
1108 
1109   if (ary_type != NULL && length_type != NULL) {
1110     const TypeInt* narrow_length_type = ary_type->narrow_size_type(length_type);
1111     if (narrow_length_type != length_type) {
1112       // Assert one of:
1113       //   - the narrow_length is 0
1114       //   - the narrow_length is not wider than length
1115       assert(narrow_length_type == TypeInt::ZERO ||
1116              (narrow_length_type->_hi <= length_type->_hi &&
1117               narrow_length_type->_lo >= length_type->_lo),
1118              "narrow type must be narrower than length type");
1119 
1120       // Return NULL if new nodes are not allowed
1121       if (!allow_new_nodes) return NULL;
1122       // Create a cast which is control dependent on the initialization to
1123       // propagate the fact that the array length must be positive.
1124       length = new (phase->C, 2) CastIINode(length, narrow_length_type);
1125       length->set_req(0, initialization()->proj_out(0));
1126     }
1127   }
1128 
1129   return length;
1130 }
1131 
1132 //=============================================================================
1133 uint LockNode::size_of() const { return sizeof(*this); }
1134 
1135 // Redundant lock elimination
1136 //
1137 // There are various patterns of locking where we release and
1138 // immediately reacquire a lock in a piece of code where no operations
1139 // occur in between that would be observable.  In those cases we can
1140 // skip releasing and reacquiring the lock without violating any
1141 // fairness requirements.  Doing this around a loop could cause a lock
1142 // to be held for a very long time so we concentrate on non-looping
1143 // control flow.  We also require that the operations are fully
1144 // redundant meaning that we don't introduce new lock operations on
1145 // some paths so to be able to eliminate it on others ala PRE.  This
1146 // would probably require some more extensive graph manipulation to
1147 // guarantee that the memory edges were all handled correctly.
1148 //
1149 // Assuming p is a simple predicate which can't trap in any way and s
1150 // is a synchronized method consider this code:
1151 //
1152 //   s();
1153 //   if (p)
1154 //     s();
1155 //   else
1156 //     s();
1157 //   s();
1158 //
1159 // 1. The unlocks of the first call to s can be eliminated if the
1160 // locks inside the then and else branches are eliminated.
1161 //
1162 // 2. The unlocks of the then and else branches can be eliminated if
1163 // the lock of the final call to s is eliminated.
1164 //
1165 // Either of these cases subsumes the simple case of sequential control flow
1166 //
1167 // Addtionally we can eliminate versions without the else case:
1168 //
1169 //   s();
1170 //   if (p)
1171 //     s();
1172 //   s();
1173 //
1174 // 3. In this case we eliminate the unlock of the first s, the lock
1175 // and unlock in the then case and the lock in the final s.
1176 //
1177 // Note also that in all these cases the then/else pieces don't have
1178 // to be trivial as long as they begin and end with synchronization
1179 // operations.
1180 //
1181 //   s();
1182 //   if (p)
1183 //     s();
1184 //     f();
1185 //     s();
1186 //   s();
1187 //
1188 // The code will work properly for this case, leaving in the unlock
1189 // before the call to f and the relock after it.
1190 //
1191 // A potentially interesting case which isn't handled here is when the
1192 // locking is partially redundant.
1193 //
1194 //   s();
1195 //   if (p)
1196 //     s();
1197 //
1198 // This could be eliminated putting unlocking on the else case and
1199 // eliminating the first unlock and the lock in the then side.
1200 // Alternatively the unlock could be moved out of the then side so it
1201 // was after the merge and the first unlock and second lock
1202 // eliminated.  This might require less manipulation of the memory
1203 // state to get correct.
1204 //
1205 // Additionally we might allow work between a unlock and lock before
1206 // giving up eliminating the locks.  The current code disallows any
1207 // conditional control flow between these operations.  A formulation
1208 // similar to partial redundancy elimination computing the
1209 // availability of unlocking and the anticipatability of locking at a
1210 // program point would allow detection of fully redundant locking with
1211 // some amount of work in between.  I'm not sure how often I really
1212 // think that would occur though.  Most of the cases I've seen
1213 // indicate it's likely non-trivial work would occur in between.
1214 // There may be other more complicated constructs where we could
1215 // eliminate locking but I haven't seen any others appear as hot or
1216 // interesting.
1217 //
1218 // Locking and unlocking have a canonical form in ideal that looks
1219 // roughly like this:
1220 //
1221 //              <obj>
1222 //                | \\------+
1223 //                |  \       \
1224 //                | BoxLock   \
1225 //                |  |   |     \
1226 //                |  |    \     \
1227 //                |  |   FastLock
1228 //                |  |   /
1229 //                |  |  /
1230 //                |  |  |
1231 //
1232 //               Lock
1233 //                |
1234 //            Proj #0
1235 //                |
1236 //            MembarAcquire
1237 //                |
1238 //            Proj #0
1239 //
1240 //            MembarRelease
1241 //                |
1242 //            Proj #0
1243 //                |
1244 //              Unlock
1245 //                |
1246 //            Proj #0
1247 //
1248 //
1249 // This code proceeds by processing Lock nodes during PhaseIterGVN
1250 // and searching back through its control for the proper code
1251 // patterns.  Once it finds a set of lock and unlock operations to
1252 // eliminate they are marked as eliminatable which causes the
1253 // expansion of the Lock and Unlock macro nodes to make the operation a NOP
1254 //
1255 //=============================================================================
1256 
1257 //
1258 // Utility function to skip over uninteresting control nodes.  Nodes skipped are:
1259 //   - copy regions.  (These may not have been optimized away yet.)
1260 //   - eliminated locking nodes
1261 //
1262 static Node *next_control(Node *ctrl) {
1263   if (ctrl == NULL)
1264     return NULL;
1265   while (1) {
1266     if (ctrl->is_Region()) {
1267       RegionNode *r = ctrl->as_Region();
1268       Node *n = r->is_copy();
1269       if (n == NULL)
1270         break;  // hit a region, return it
1271       else
1272         ctrl = n;
1273     } else if (ctrl->is_Proj()) {
1274       Node *in0 = ctrl->in(0);
1275       if (in0->is_AbstractLock() && in0->as_AbstractLock()->is_eliminated()) {
1276         ctrl = in0->in(0);
1277       } else {
1278         break;
1279       }
1280     } else {
1281       break; // found an interesting control
1282     }
1283   }
1284   return ctrl;
1285 }
1286 //
1287 // Given a control, see if it's the control projection of an Unlock which
1288 // operating on the same object as lock.
1289 //
1290 bool AbstractLockNode::find_matching_unlock(const Node* ctrl, LockNode* lock,
1291                                             GrowableArray<AbstractLockNode*> &lock_ops) {
1292   ProjNode *ctrl_proj = (ctrl->is_Proj()) ? ctrl->as_Proj() : NULL;
1293   if (ctrl_proj != NULL && ctrl_proj->_con == TypeFunc::Control) {
1294     Node *n = ctrl_proj->in(0);
1295     if (n != NULL && n->is_Unlock()) {
1296       UnlockNode *unlock = n->as_Unlock();
1297       if ((lock->obj_node() == unlock->obj_node()) &&
1298           (lock->box_node() == unlock->box_node()) && !unlock->is_eliminated()) {
1299         lock_ops.append(unlock);
1300         return true;
1301       }
1302     }
1303   }
1304   return false;
1305 }
1306 
1307 //
1308 // Find the lock matching an unlock.  Returns null if a safepoint
1309 // or complicated control is encountered first.
1310 LockNode *AbstractLockNode::find_matching_lock(UnlockNode* unlock) {
1311   LockNode *lock_result = NULL;
1312   // find the matching lock, or an intervening safepoint
1313   Node *ctrl = next_control(unlock->in(0));
1314   while (1) {
1315     assert(ctrl != NULL, "invalid control graph");
1316     assert(!ctrl->is_Start(), "missing lock for unlock");
1317     if (ctrl->is_top()) break;  // dead control path
1318     if (ctrl->is_Proj()) ctrl = ctrl->in(0);
1319     if (ctrl->is_SafePoint()) {
1320         break;  // found a safepoint (may be the lock we are searching for)
1321     } else if (ctrl->is_Region()) {
1322       // Check for a simple diamond pattern.  Punt on anything more complicated
1323       if (ctrl->req() == 3 && ctrl->in(1) != NULL && ctrl->in(2) != NULL) {
1324         Node *in1 = next_control(ctrl->in(1));
1325         Node *in2 = next_control(ctrl->in(2));
1326         if (((in1->is_IfTrue() && in2->is_IfFalse()) ||
1327              (in2->is_IfTrue() && in1->is_IfFalse())) && (in1->in(0) == in2->in(0))) {
1328           ctrl = next_control(in1->in(0)->in(0));
1329         } else {
1330           break;
1331         }
1332       } else {
1333         break;
1334       }
1335     } else {
1336       ctrl = next_control(ctrl->in(0));  // keep searching
1337     }
1338   }
1339   if (ctrl->is_Lock()) {
1340     LockNode *lock = ctrl->as_Lock();
1341     if ((lock->obj_node() == unlock->obj_node()) &&
1342             (lock->box_node() == unlock->box_node())) {
1343       lock_result = lock;
1344     }
1345   }
1346   return lock_result;
1347 }
1348 
1349 // This code corresponds to case 3 above.
1350 
1351 bool AbstractLockNode::find_lock_and_unlock_through_if(Node* node, LockNode* lock,
1352                                                        GrowableArray<AbstractLockNode*> &lock_ops) {
1353   Node* if_node = node->in(0);
1354   bool  if_true = node->is_IfTrue();
1355 
1356   if (if_node->is_If() && if_node->outcnt() == 2 && (if_true || node->is_IfFalse())) {
1357     Node *lock_ctrl = next_control(if_node->in(0));
1358     if (find_matching_unlock(lock_ctrl, lock, lock_ops)) {
1359       Node* lock1_node = NULL;
1360       ProjNode* proj = if_node->as_If()->proj_out(!if_true);
1361       if (if_true) {
1362         if (proj->is_IfFalse() && proj->outcnt() == 1) {
1363           lock1_node = proj->unique_out();
1364         }
1365       } else {
1366         if (proj->is_IfTrue() && proj->outcnt() == 1) {
1367           lock1_node = proj->unique_out();
1368         }
1369       }
1370       if (lock1_node != NULL && lock1_node->is_Lock()) {
1371         LockNode *lock1 = lock1_node->as_Lock();
1372         if ((lock->obj_node() == lock1->obj_node()) &&
1373             (lock->box_node() == lock1->box_node()) && !lock1->is_eliminated()) {
1374           lock_ops.append(lock1);
1375           return true;
1376         }
1377       }
1378     }
1379   }
1380 
1381   lock_ops.trunc_to(0);
1382   return false;
1383 }
1384 
1385 bool AbstractLockNode::find_unlocks_for_region(const RegionNode* region, LockNode* lock,
1386                                GrowableArray<AbstractLockNode*> &lock_ops) {
1387   // check each control merging at this point for a matching unlock.
1388   // in(0) should be self edge so skip it.
1389   for (int i = 1; i < (int)region->req(); i++) {
1390     Node *in_node = next_control(region->in(i));
1391     if (in_node != NULL) {
1392       if (find_matching_unlock(in_node, lock, lock_ops)) {
1393         // found a match so keep on checking.
1394         continue;
1395       } else if (find_lock_and_unlock_through_if(in_node, lock, lock_ops)) {
1396         continue;
1397       }
1398 
1399       // If we fall through to here then it was some kind of node we
1400       // don't understand or there wasn't a matching unlock, so give
1401       // up trying to merge locks.
1402       lock_ops.trunc_to(0);
1403       return false;
1404     }
1405   }
1406   return true;
1407 
1408 }
1409 
1410 #ifndef PRODUCT
1411 //
1412 // Create a counter which counts the number of times this lock is acquired
1413 //
1414 void AbstractLockNode::create_lock_counter(JVMState* state) {
1415   _counter = OptoRuntime::new_named_counter(state, NamedCounter::LockCounter);
1416 }
1417 #endif
1418 
1419 void AbstractLockNode::set_eliminated() {
1420   _eliminate = true;
1421 #ifndef PRODUCT
1422   if (_counter) {
1423     // Update the counter to indicate that this lock was eliminated.
1424     // The counter update code will stay around even though the
1425     // optimizer will eliminate the lock operation itself.
1426     _counter->set_tag(NamedCounter::EliminatedLockCounter);
1427   }
1428 #endif
1429 }
1430 
1431 //=============================================================================
1432 Node *LockNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1433 
1434   // perform any generic optimizations first (returns 'this' or NULL)
1435   Node *result = SafePointNode::Ideal(phase, can_reshape);
1436 
1437   // Now see if we can optimize away this lock.  We don't actually
1438   // remove the locking here, we simply set the _eliminate flag which
1439   // prevents macro expansion from expanding the lock.  Since we don't
1440   // modify the graph, the value returned from this function is the
1441   // one computed above.
1442   if (result == NULL && can_reshape && EliminateLocks && !is_eliminated()) {
1443     //
1444     // If we are locking an unescaped object, the lock/unlock is unnecessary
1445     //
1446     ConnectionGraph *cgr = phase->C->congraph();
1447     PointsToNode::EscapeState es = PointsToNode::GlobalEscape;
1448     if (cgr != NULL)
1449       es = cgr->escape_state(obj_node(), phase);
1450     if (es != PointsToNode::UnknownEscape && es != PointsToNode::GlobalEscape) {
1451       // Mark it eliminated to update any counters
1452       this->set_eliminated();
1453       return result;
1454     }
1455 
1456     //
1457     // Try lock coarsening
1458     //
1459     PhaseIterGVN* iter = phase->is_IterGVN();
1460     if (iter != NULL) {
1461 
1462       GrowableArray<AbstractLockNode*>   lock_ops;
1463 
1464       Node *ctrl = next_control(in(0));
1465 
1466       // now search back for a matching Unlock
1467       if (find_matching_unlock(ctrl, this, lock_ops)) {
1468         // found an unlock directly preceding this lock.  This is the
1469         // case of single unlock directly control dependent on a
1470         // single lock which is the trivial version of case 1 or 2.
1471       } else if (ctrl->is_Region() ) {
1472         if (find_unlocks_for_region(ctrl->as_Region(), this, lock_ops)) {
1473         // found lock preceded by multiple unlocks along all paths
1474         // joining at this point which is case 3 in description above.
1475         }
1476       } else {
1477         // see if this lock comes from either half of an if and the
1478         // predecessors merges unlocks and the other half of the if
1479         // performs a lock.
1480         if (find_lock_and_unlock_through_if(ctrl, this, lock_ops)) {
1481           // found unlock splitting to an if with locks on both branches.
1482         }
1483       }
1484 
1485       if (lock_ops.length() > 0) {
1486         // add ourselves to the list of locks to be eliminated.
1487         lock_ops.append(this);
1488 
1489   #ifndef PRODUCT
1490         if (PrintEliminateLocks) {
1491           int locks = 0;
1492           int unlocks = 0;
1493           for (int i = 0; i < lock_ops.length(); i++) {
1494             AbstractLockNode* lock = lock_ops.at(i);
1495             if (lock->Opcode() == Op_Lock)
1496               locks++;
1497             else
1498               unlocks++;
1499             if (Verbose) {
1500               lock->dump(1);
1501             }
1502           }
1503           tty->print_cr("***Eliminated %d unlocks and %d locks", unlocks, locks);
1504         }
1505   #endif
1506 
1507         // for each of the identified locks, mark them
1508         // as eliminatable
1509         for (int i = 0; i < lock_ops.length(); i++) {
1510           AbstractLockNode* lock = lock_ops.at(i);
1511 
1512           // Mark it eliminated to update any counters
1513           lock->set_eliminated();
1514           lock->set_coarsened();
1515         }
1516       } else if (result != NULL && ctrl->is_Region() &&
1517                  iter->_worklist.member(ctrl)) {
1518         // We weren't able to find any opportunities but the region this
1519         // lock is control dependent on hasn't been processed yet so put
1520         // this lock back on the worklist so we can check again once any
1521         // region simplification has occurred.
1522         iter->_worklist.push(this);
1523       }
1524     }
1525   }
1526 
1527   return result;
1528 }
1529 
1530 //=============================================================================
1531 uint UnlockNode::size_of() const { return sizeof(*this); }
1532 
1533 //=============================================================================
1534 Node *UnlockNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1535 
1536   // perform any generic optimizations first (returns 'this' or NULL)
1537   Node * result = SafePointNode::Ideal(phase, can_reshape);
1538 
1539   // Now see if we can optimize away this unlock.  We don't actually
1540   // remove the unlocking here, we simply set the _eliminate flag which
1541   // prevents macro expansion from expanding the unlock.  Since we don't
1542   // modify the graph, the value returned from this function is the
1543   // one computed above.
1544   // Escape state is defined after Parse phase.
1545   if (result == NULL && can_reshape && EliminateLocks && !is_eliminated()) {
1546     //
1547     // If we are unlocking an unescaped object, the lock/unlock is unnecessary.
1548     //
1549     ConnectionGraph *cgr = phase->C->congraph();
1550     PointsToNode::EscapeState es = PointsToNode::GlobalEscape;
1551     if (cgr != NULL)
1552       es = cgr->escape_state(obj_node(), phase);
1553     if (es != PointsToNode::UnknownEscape && es != PointsToNode::GlobalEscape) {
1554       // Mark it eliminated to update any counters
1555       this->set_eliminated();
1556     }
1557   }
1558   return result;
1559 }