1 /*
   2  * Copyright (c) 2005, 2018, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "ci/bcEscapeAnalyzer.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "gc/shared/barrierSet.hpp"
  29 #include "gc/shared/c2/barrierSetC2.hpp"
  30 #include "libadt/vectset.hpp"
  31 #include "memory/allocation.hpp"
  32 #include "memory/resourceArea.hpp"
  33 #include "opto/c2compiler.hpp"
  34 #include "opto/arraycopynode.hpp"
  35 #include "opto/callnode.hpp"
  36 #include "opto/cfgnode.hpp"
  37 #include "opto/compile.hpp"
  38 #include "opto/escape.hpp"
  39 #include "opto/phaseX.hpp"
  40 #include "opto/movenode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "utilities/macros.hpp"
  43 
  44 ConnectionGraph::ConnectionGraph(Compile * C, PhaseIterGVN *igvn) :
  45   _nodes(C->comp_arena(), C->unique(), C->unique(), NULL),
  46   _in_worklist(C->comp_arena()),
  47   _next_pidx(0),
  48   _collecting(true),
  49   _verify(false),
  50   _compile(C),
  51   _igvn(igvn),
  52   _node_map(C->comp_arena()) {
  53   // Add unknown java object.
  54   add_java_object(C->top(), PointsToNode::GlobalEscape);
  55   phantom_obj = ptnode_adr(C->top()->_idx)->as_JavaObject();
  56   // Add ConP(#NULL) and ConN(#NULL) nodes.
  57   Node* oop_null = igvn->zerocon(T_OBJECT);
  58   assert(oop_null->_idx < nodes_size(), "should be created already");
  59   add_java_object(oop_null, PointsToNode::NoEscape);
  60   null_obj = ptnode_adr(oop_null->_idx)->as_JavaObject();
  61   if (UseCompressedOops) {
  62     Node* noop_null = igvn->zerocon(T_NARROWOOP);
  63     assert(noop_null->_idx < nodes_size(), "should be created already");
  64     map_ideal_node(noop_null, null_obj);
  65   }
  66   _pcmp_neq = NULL; // Should be initialized
  67   _pcmp_eq  = NULL;
  68 }
  69 
  70 bool ConnectionGraph::has_candidates(Compile *C) {
  71   // EA brings benefits only when the code has allocations and/or locks which
  72   // are represented by ideal Macro nodes.
  73   int cnt = C->macro_count();
  74   for (int i = 0; i < cnt; i++) {
  75     Node *n = C->macro_node(i);
  76     if (n->is_Allocate())
  77       return true;
  78     if (n->is_Lock()) {
  79       Node* obj = n->as_Lock()->obj_node()->uncast();
  80       if (!(obj->is_Parm() || obj->is_Con()))
  81         return true;
  82     }
  83     if (n->is_CallStaticJava() &&
  84         n->as_CallStaticJava()->is_boxing_method()) {
  85       return true;
  86     }
  87   }
  88   return false;
  89 }
  90 
  91 void ConnectionGraph::do_analysis(Compile *C, PhaseIterGVN *igvn) {
  92   Compile::TracePhase tp("escapeAnalysis", &Phase::timers[Phase::_t_escapeAnalysis]);
  93   ResourceMark rm;
  94 
  95   // Add ConP#NULL and ConN#NULL nodes before ConnectionGraph construction
  96   // to create space for them in ConnectionGraph::_nodes[].
  97   Node* oop_null = igvn->zerocon(T_OBJECT);
  98   Node* noop_null = igvn->zerocon(T_NARROWOOP);
  99   ConnectionGraph* congraph = new(C->comp_arena()) ConnectionGraph(C, igvn);
 100   // Perform escape analysis
 101   if (congraph->compute_escape()) {
 102     // There are non escaping objects.
 103     C->set_congraph(congraph);
 104   }
 105   // Cleanup.
 106   if (oop_null->outcnt() == 0)
 107     igvn->hash_delete(oop_null);
 108   if (noop_null->outcnt() == 0)
 109     igvn->hash_delete(noop_null);
 110 }
 111 
 112 bool ConnectionGraph::compute_escape() {
 113   Compile* C = _compile;
 114   PhaseGVN* igvn = _igvn;
 115 
 116   // Worklists used by EA.
 117   Unique_Node_List delayed_worklist;
 118   GrowableArray<Node*> alloc_worklist;
 119   GrowableArray<Node*> ptr_cmp_worklist;
 120   GrowableArray<Node*> storestore_worklist;
 121   GrowableArray<ArrayCopyNode*> arraycopy_worklist;
 122   GrowableArray<PointsToNode*>   ptnodes_worklist;
 123   GrowableArray<JavaObjectNode*> java_objects_worklist;
 124   GrowableArray<JavaObjectNode*> non_escaped_worklist;
 125   GrowableArray<FieldNode*>      oop_fields_worklist;
 126   DEBUG_ONLY( GrowableArray<Node*> addp_worklist; )
 127 
 128   { Compile::TracePhase tp("connectionGraph", &Phase::timers[Phase::_t_connectionGraph]);
 129 
 130   // 1. Populate Connection Graph (CG) with PointsTo nodes.
 131   ideal_nodes.map(C->live_nodes(), NULL);  // preallocate space
 132   // Initialize worklist
 133   if (C->root() != NULL) {
 134     ideal_nodes.push(C->root());
 135   }
 136   // Processed ideal nodes are unique on ideal_nodes list
 137   // but several ideal nodes are mapped to the phantom_obj.
 138   // To avoid duplicated entries on the following worklists
 139   // add the phantom_obj only once to them.
 140   ptnodes_worklist.append(phantom_obj);
 141   java_objects_worklist.append(phantom_obj);
 142   for( uint next = 0; next < ideal_nodes.size(); ++next ) {
 143     Node* n = ideal_nodes.at(next);
 144     if ((n->Opcode() == Op_LoadX || n->Opcode() == Op_StoreX) &&
 145         !n->in(MemNode::Address)->is_AddP() &&
 146         _igvn->type(n->in(MemNode::Address))->isa_oopptr()) {
 147       // Load/Store at mark work address is at offset 0 so has no AddP which confuses EA
 148       Node* addp = new AddPNode(n->in(MemNode::Address), n->in(MemNode::Address), _igvn->MakeConX(0));
 149       _igvn->register_new_node_with_optimizer(addp);
 150       _igvn->replace_input_of(n, MemNode::Address, addp);
 151       ideal_nodes.push(addp);
 152       _nodes.at_put_grow(addp->_idx, NULL, NULL);
 153     }
 154     // Create PointsTo nodes and add them to Connection Graph. Called
 155     // only once per ideal node since ideal_nodes is Unique_Node list.
 156     add_node_to_connection_graph(n, &delayed_worklist);
 157     PointsToNode* ptn = ptnode_adr(n->_idx);
 158     if (ptn != NULL && ptn != phantom_obj) {
 159       ptnodes_worklist.append(ptn);
 160       if (ptn->is_JavaObject()) {
 161         java_objects_worklist.append(ptn->as_JavaObject());
 162         if ((n->is_Allocate() || n->is_CallStaticJava()) &&
 163             (ptn->escape_state() < PointsToNode::GlobalEscape)) {
 164           // Only allocations and java static calls results are interesting.
 165           non_escaped_worklist.append(ptn->as_JavaObject());
 166         }
 167       } else if (ptn->is_Field() && ptn->as_Field()->is_oop()) {
 168         oop_fields_worklist.append(ptn->as_Field());
 169       }
 170     }
 171     if (n->is_MergeMem()) {
 172       // Collect all MergeMem nodes to add memory slices for
 173       // scalar replaceable objects in split_unique_types().
 174       _mergemem_worklist.append(n->as_MergeMem());
 175     } else if (OptimizePtrCompare && n->is_Cmp() &&
 176                ((n->Opcode() == Op_CmpP && !(((CmpPNode*)n)->has_perturbed_operand() != NULL)) ||
 177                  n->Opcode() == Op_CmpN)) {
 178       // Collect compare pointers nodes.
 179       ptr_cmp_worklist.append(n);
 180     } else if (n->is_MemBarStoreStore()) {
 181       // Collect all MemBarStoreStore nodes so that depending on the
 182       // escape status of the associated Allocate node some of them
 183       // may be eliminated.
 184       storestore_worklist.append(n);
 185     } else if (n->is_MemBar() && (n->Opcode() == Op_MemBarRelease) &&
 186                (n->req() > MemBarNode::Precedent)) {
 187       record_for_optimizer(n);
 188 #ifdef ASSERT
 189     } else if (n->is_AddP()) {
 190       // Collect address nodes for graph verification.
 191       addp_worklist.append(n);
 192 #endif
 193     } else if (n->is_ArrayCopy()) {
 194       // Keep a list of ArrayCopy nodes so if one of its input is non
 195       // escaping, we can record a unique type
 196       arraycopy_worklist.append(n->as_ArrayCopy());
 197     }
 198     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
 199       Node* m = n->fast_out(i);   // Get user
 200       ideal_nodes.push(m);
 201     }
 202   }
 203   if (non_escaped_worklist.length() == 0) {
 204     _collecting = false;
 205     return false; // Nothing to do.
 206   }
 207   // Add final simple edges to graph.
 208   while(delayed_worklist.size() > 0) {
 209     Node* n = delayed_worklist.pop();
 210     add_final_edges(n);
 211   }
 212   int ptnodes_length = ptnodes_worklist.length();
 213 
 214 #ifdef ASSERT
 215   if (VerifyConnectionGraph) {
 216     // Verify that no new simple edges could be created and all
 217     // local vars has edges.
 218     _verify = true;
 219     for (int next = 0; next < ptnodes_length; ++next) {
 220       PointsToNode* ptn = ptnodes_worklist.at(next);
 221       add_final_edges(ptn->ideal_node());
 222       if (ptn->is_LocalVar() && ptn->edge_count() == 0) {
 223         ptn->dump();
 224         assert(ptn->as_LocalVar()->edge_count() > 0, "sanity");
 225       }
 226     }
 227     _verify = false;
 228   }
 229 #endif
 230   // Bytecode analyzer BCEscapeAnalyzer, used for Call nodes
 231   // processing, calls to CI to resolve symbols (types, fields, methods)
 232   // referenced in bytecode. During symbol resolution VM may throw
 233   // an exception which CI cleans and converts to compilation failure.
 234   if (C->failing())  return false;
 235 
 236   // 2. Finish Graph construction by propagating references to all
 237   //    java objects through graph.
 238   if (!complete_connection_graph(ptnodes_worklist, non_escaped_worklist,
 239                                  java_objects_worklist, oop_fields_worklist)) {
 240     // All objects escaped or hit time or iterations limits.
 241     _collecting = false;
 242     return false;
 243   }
 244 
 245   // 3. Adjust scalar_replaceable state of nonescaping objects and push
 246   //    scalar replaceable allocations on alloc_worklist for processing
 247   //    in split_unique_types().
 248   int non_escaped_length = non_escaped_worklist.length();
 249   for (int next = 0; next < non_escaped_length; next++) {
 250     JavaObjectNode* ptn = non_escaped_worklist.at(next);
 251     bool noescape = (ptn->escape_state() == PointsToNode::NoEscape);
 252     Node* n = ptn->ideal_node();
 253     if (n->is_Allocate()) {
 254       n->as_Allocate()->_is_non_escaping = noescape;
 255     }
 256     if (n->is_CallStaticJava()) {
 257       n->as_CallStaticJava()->_is_non_escaping = noescape;
 258     }
 259     if (noescape && ptn->scalar_replaceable()) {
 260       adjust_scalar_replaceable_state(ptn);
 261       if (ptn->scalar_replaceable()) {
 262         alloc_worklist.append(ptn->ideal_node());
 263       }
 264     }
 265   }
 266 
 267 #ifdef ASSERT
 268   if (VerifyConnectionGraph) {
 269     // Verify that graph is complete - no new edges could be added or needed.
 270     verify_connection_graph(ptnodes_worklist, non_escaped_worklist,
 271                             java_objects_worklist, addp_worklist);
 272   }
 273   assert(C->unique() == nodes_size(), "no new ideal nodes should be added during ConnectionGraph build");
 274   assert(null_obj->escape_state() == PointsToNode::NoEscape &&
 275          null_obj->edge_count() == 0 &&
 276          !null_obj->arraycopy_src() &&
 277          !null_obj->arraycopy_dst(), "sanity");
 278 #endif
 279 
 280   _collecting = false;
 281 
 282   } // TracePhase t3("connectionGraph")
 283 
 284   // 4. Optimize ideal graph based on EA information.
 285   bool has_non_escaping_obj = (non_escaped_worklist.length() > 0);
 286   if (has_non_escaping_obj) {
 287     optimize_ideal_graph(ptr_cmp_worklist, storestore_worklist);
 288   }
 289 
 290 #ifndef PRODUCT
 291   if (PrintEscapeAnalysis) {
 292     dump(ptnodes_worklist); // Dump ConnectionGraph
 293   }
 294 #endif
 295 
 296   bool has_scalar_replaceable_candidates = (alloc_worklist.length() > 0);
 297 #ifdef ASSERT
 298   if (VerifyConnectionGraph) {
 299     int alloc_length = alloc_worklist.length();
 300     for (int next = 0; next < alloc_length; ++next) {
 301       Node* n = alloc_worklist.at(next);
 302       PointsToNode* ptn = ptnode_adr(n->_idx);
 303       assert(ptn->escape_state() == PointsToNode::NoEscape && ptn->scalar_replaceable(), "sanity");
 304     }
 305   }
 306 #endif
 307 
 308   // 5. Separate memory graph for scalar replaceable allcations.
 309   if (has_scalar_replaceable_candidates &&
 310       C->AliasLevel() >= 3 && EliminateAllocations) {
 311     // Now use the escape information to create unique types for
 312     // scalar replaceable objects.
 313     split_unique_types(alloc_worklist, arraycopy_worklist);
 314     if (C->failing())  return false;
 315     C->print_method(PHASE_AFTER_EA, 2);
 316 
 317 #ifdef ASSERT
 318   } else if (Verbose && (PrintEscapeAnalysis || PrintEliminateAllocations)) {
 319     tty->print("=== No allocations eliminated for ");
 320     C->method()->print_short_name();
 321     if(!EliminateAllocations) {
 322       tty->print(" since EliminateAllocations is off ===");
 323     } else if(!has_scalar_replaceable_candidates) {
 324       tty->print(" since there are no scalar replaceable candidates ===");
 325     } else if(C->AliasLevel() < 3) {
 326       tty->print(" since AliasLevel < 3 ===");
 327     }
 328     tty->cr();
 329 #endif
 330   }
 331   return has_non_escaping_obj;
 332 }
 333 
 334 // Utility function for nodes that load an object
 335 void ConnectionGraph::add_objload_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist) {
 336   // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because
 337   // ThreadLocal has RawPtr type.
 338   const Type* t = _igvn->type(n);
 339   if (t->make_ptr() != NULL) {
 340     Node* adr = n->in(MemNode::Address);
 341 #ifdef ASSERT
 342     if (!adr->is_AddP()) {
 343       assert(_igvn->type(adr)->isa_rawptr(), "sanity");
 344     } else {
 345       assert((ptnode_adr(adr->_idx) == NULL ||
 346               ptnode_adr(adr->_idx)->as_Field()->is_oop()), "sanity");
 347     }
 348 #endif
 349     add_local_var_and_edge(n, PointsToNode::NoEscape,
 350                            adr, delayed_worklist);
 351   }
 352 }
 353 
 354 // Populate Connection Graph with PointsTo nodes and create simple
 355 // connection graph edges.
 356 void ConnectionGraph::add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist) {
 357   assert(!_verify, "this method should not be called for verification");
 358   PhaseGVN* igvn = _igvn;
 359   uint n_idx = n->_idx;
 360   PointsToNode* n_ptn = ptnode_adr(n_idx);
 361   if (n_ptn != NULL)
 362     return; // No need to redefine PointsTo node during first iteration.
 363 
 364   if (n->is_Call()) {
 365     // Arguments to allocation and locking don't escape.
 366     if (n->is_AbstractLock()) {
 367       // Put Lock and Unlock nodes on IGVN worklist to process them during
 368       // first IGVN optimization when escape information is still available.
 369       record_for_optimizer(n);
 370     } else if (n->is_Allocate()) {
 371       add_call_node(n->as_Call());
 372       record_for_optimizer(n);
 373     } else {
 374       if (n->is_CallStaticJava()) {
 375         const char* name = n->as_CallStaticJava()->_name;
 376         if (name != NULL && strcmp(name, "uncommon_trap") == 0)
 377           return; // Skip uncommon traps
 378       }
 379       // Don't mark as processed since call's arguments have to be processed.
 380       delayed_worklist->push(n);
 381       // Check if a call returns an object.
 382       if ((n->as_Call()->returns_pointer() &&
 383            n->as_Call()->proj_out_or_null(TypeFunc::Parms) != NULL) ||
 384           (n->is_CallStaticJava() &&
 385            n->as_CallStaticJava()->is_boxing_method())) {
 386         add_call_node(n->as_Call());
 387       } else if (n->as_Call()->tf()->returns_value_type_as_fields()) {
 388         bool returns_oop = false;
 389         for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !returns_oop; i++) {
 390           ProjNode* pn = n->fast_out(i)->as_Proj();
 391           if (pn->_con >= TypeFunc::Parms && pn->bottom_type()->isa_ptr()) {
 392             returns_oop = true;
 393           }
 394         }
 395         if (returns_oop) {
 396           add_call_node(n->as_Call());
 397         }
 398       }
 399     }
 400     return;
 401   }
 402   // Put this check here to process call arguments since some call nodes
 403   // point to phantom_obj.
 404   if (n_ptn == phantom_obj || n_ptn == null_obj)
 405     return; // Skip predefined nodes.
 406 
 407   int opcode = n->Opcode();
 408   bool gc_handled = BarrierSet::barrier_set()->barrier_set_c2()->escape_add_to_con_graph(this, igvn, delayed_worklist, n, opcode);
 409   if (gc_handled) {
 410     return; // Ignore node if already handled by GC.
 411   }
 412   switch (opcode) {
 413     case Op_AddP: {
 414       Node* base = get_addp_base(n);
 415       PointsToNode* ptn_base = ptnode_adr(base->_idx);
 416       // Field nodes are created for all field types. They are used in
 417       // adjust_scalar_replaceable_state() and split_unique_types().
 418       // Note, non-oop fields will have only base edges in Connection
 419       // Graph because such fields are not used for oop loads and stores.
 420       int offset = address_offset(n, igvn);
 421       add_field(n, PointsToNode::NoEscape, offset);
 422       if (ptn_base == NULL) {
 423         delayed_worklist->push(n); // Process it later.
 424       } else {
 425         n_ptn = ptnode_adr(n_idx);
 426         add_base(n_ptn->as_Field(), ptn_base);
 427       }
 428       break;
 429     }
 430     case Op_CastX2P: {
 431       map_ideal_node(n, phantom_obj);
 432       break;
 433     }
 434     case Op_CastPP:
 435     case Op_CheckCastPP:
 436     case Op_EncodeP:
 437     case Op_DecodeN:
 438     case Op_EncodePKlass:
 439     case Op_DecodeNKlass: {
 440       add_local_var_and_edge(n, PointsToNode::NoEscape,
 441                              n->in(1), delayed_worklist);
 442       break;
 443     }
 444     case Op_CMoveP: {
 445       add_local_var(n, PointsToNode::NoEscape);
 446       // Do not add edges during first iteration because some could be
 447       // not defined yet.
 448       delayed_worklist->push(n);
 449       break;
 450     }
 451     case Op_ConP:
 452     case Op_ConN:
 453     case Op_ConNKlass: {
 454       // assume all oop constants globally escape except for null
 455       PointsToNode::EscapeState es;
 456       const Type* t = igvn->type(n);
 457       if (t == TypePtr::NULL_PTR || t == TypeNarrowOop::NULL_PTR) {
 458         es = PointsToNode::NoEscape;
 459       } else {
 460         es = PointsToNode::GlobalEscape;
 461       }
 462       add_java_object(n, es);
 463       break;
 464     }
 465     case Op_CreateEx: {
 466       // assume that all exception objects globally escape
 467       map_ideal_node(n, phantom_obj);
 468       break;
 469     }
 470     case Op_LoadKlass:
 471     case Op_LoadNKlass: {
 472       // Unknown class is loaded
 473       map_ideal_node(n, phantom_obj);
 474       break;
 475     }
 476     case Op_LoadP:
 477     case Op_LoadN:
 478     case Op_LoadPLocked: {
 479       add_objload_to_connection_graph(n, delayed_worklist);
 480       break;
 481     }
 482     case Op_Parm: {
 483       map_ideal_node(n, phantom_obj);
 484       break;
 485     }
 486     case Op_PartialSubtypeCheck: {
 487       // Produces Null or notNull and is used in only in CmpP so
 488       // phantom_obj could be used.
 489       map_ideal_node(n, phantom_obj); // Result is unknown
 490       break;
 491     }
 492     case Op_Phi: {
 493       // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because
 494       // ThreadLocal has RawPtr type.
 495       const Type* t = n->as_Phi()->type();
 496       if (t->make_ptr() != NULL) {
 497         add_local_var(n, PointsToNode::NoEscape);
 498         // Do not add edges during first iteration because some could be
 499         // not defined yet.
 500         delayed_worklist->push(n);
 501       }
 502       break;
 503     }
 504     case Op_Proj: {
 505       // we are only interested in the oop result projection from a call
 506       if (n->as_Proj()->_con >= TypeFunc::Parms && n->in(0)->is_Call() &&
 507           (n->in(0)->as_Call()->returns_pointer() || n->bottom_type()->isa_ptr())) {
 508         assert((n->as_Proj()->_con == TypeFunc::Parms && n->in(0)->as_Call()->returns_pointer()) ||
 509                n->in(0)->as_Call()->tf()->returns_value_type_as_fields(), "what kind of oop return is it?");
 510         add_local_var_and_edge(n, PointsToNode::NoEscape,
 511                                n->in(0), delayed_worklist);
 512       }
 513       break;
 514     }
 515     case Op_Rethrow: // Exception object escapes
 516     case Op_Return: {
 517       if (n->req() > TypeFunc::Parms &&
 518           igvn->type(n->in(TypeFunc::Parms))->isa_oopptr()) {
 519         // Treat Return value as LocalVar with GlobalEscape escape state.
 520         add_local_var_and_edge(n, PointsToNode::GlobalEscape,
 521                                n->in(TypeFunc::Parms), delayed_worklist);
 522       }
 523       break;
 524     }
 525     case Op_CompareAndExchangeP:
 526     case Op_CompareAndExchangeN:
 527     case Op_GetAndSetP:
 528     case Op_GetAndSetN: {
 529       add_objload_to_connection_graph(n, delayed_worklist);
 530       // fallthrough
 531     }
 532     case Op_StoreP:
 533     case Op_StoreN:
 534     case Op_StoreNKlass:
 535     case Op_StorePConditional:
 536     case Op_WeakCompareAndSwapP:
 537     case Op_WeakCompareAndSwapN:
 538     case Op_CompareAndSwapP:
 539     case Op_CompareAndSwapN: {
 540       add_to_congraph_unsafe_access(n, opcode, delayed_worklist);
 541       break;
 542     }
 543     case Op_AryEq:
 544     case Op_HasNegatives:
 545     case Op_StrComp:
 546     case Op_StrEquals:
 547     case Op_StrIndexOf:
 548     case Op_StrIndexOfChar:
 549     case Op_StrInflatedCopy:
 550     case Op_StrCompressedCopy:
 551     case Op_EncodeISOArray: {
 552       add_local_var(n, PointsToNode::ArgEscape);
 553       delayed_worklist->push(n); // Process it later.
 554       break;
 555     }
 556     case Op_ThreadLocal: {
 557       add_java_object(n, PointsToNode::ArgEscape);
 558       break;
 559     }
 560     default:
 561       ; // Do nothing for nodes not related to EA.
 562   }
 563   return;
 564 }
 565 
 566 #ifdef ASSERT
 567 #define ELSE_FAIL(name)                               \
 568       /* Should not be called for not pointer type. */  \
 569       n->dump(1);                                       \
 570       assert(false, name);                              \
 571       break;
 572 #else
 573 #define ELSE_FAIL(name) \
 574       break;
 575 #endif
 576 
 577 // Add final simple edges to graph.
 578 void ConnectionGraph::add_final_edges(Node *n) {
 579   PointsToNode* n_ptn = ptnode_adr(n->_idx);
 580 #ifdef ASSERT
 581   if (_verify && n_ptn->is_JavaObject())
 582     return; // This method does not change graph for JavaObject.
 583 #endif
 584 
 585   if (n->is_Call()) {
 586     process_call_arguments(n->as_Call());
 587     return;
 588   }
 589   assert(n->is_Store() || n->is_LoadStore() ||
 590          (n_ptn != NULL) && (n_ptn->ideal_node() != NULL),
 591          "node should be registered already");
 592   int opcode = n->Opcode();
 593   bool gc_handled = BarrierSet::barrier_set()->barrier_set_c2()->escape_add_final_edges(this, _igvn, n, opcode);
 594   if (gc_handled) {
 595     return; // Ignore node if already handled by GC.
 596   }
 597   switch (opcode) {
 598     case Op_AddP: {
 599       Node* base = get_addp_base(n);
 600       PointsToNode* ptn_base = ptnode_adr(base->_idx);
 601       assert(ptn_base != NULL, "field's base should be registered");
 602       add_base(n_ptn->as_Field(), ptn_base);
 603       break;
 604     }
 605     case Op_CastPP:
 606     case Op_CheckCastPP:
 607     case Op_EncodeP:
 608     case Op_DecodeN:
 609     case Op_EncodePKlass:
 610     case Op_DecodeNKlass: {
 611       add_local_var_and_edge(n, PointsToNode::NoEscape,
 612                              n->in(1), NULL);
 613       break;
 614     }
 615     case Op_CMoveP: {
 616       for (uint i = CMoveNode::IfFalse; i < n->req(); i++) {
 617         Node* in = n->in(i);
 618         if (in == NULL)
 619           continue;  // ignore NULL
 620         Node* uncast_in = in->uncast();
 621         if (uncast_in->is_top() || uncast_in == n)
 622           continue;  // ignore top or inputs which go back this node
 623         PointsToNode* ptn = ptnode_adr(in->_idx);
 624         assert(ptn != NULL, "node should be registered");
 625         add_edge(n_ptn, ptn);
 626       }
 627       break;
 628     }
 629     case Op_LoadP:
 630     case Op_LoadN:
 631     case Op_LoadPLocked: {
 632       // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because
 633       // ThreadLocal has RawPtr type.
 634       const Type* t = _igvn->type(n);
 635       if (t->make_ptr() != NULL) {
 636         Node* adr = n->in(MemNode::Address);
 637         add_local_var_and_edge(n, PointsToNode::NoEscape, adr, NULL);
 638         break;
 639       }
 640       ELSE_FAIL("Op_LoadP");
 641     }
 642     case Op_Phi: {
 643       // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because
 644       // ThreadLocal has RawPtr type.
 645       const Type* t = n->as_Phi()->type();
 646       if (t->make_ptr() != NULL) {
 647         for (uint i = 1; i < n->req(); i++) {
 648           Node* in = n->in(i);
 649           if (in == NULL)
 650             continue;  // ignore NULL
 651           Node* uncast_in = in->uncast();
 652           if (uncast_in->is_top() || uncast_in == n)
 653             continue;  // ignore top or inputs which go back this node
 654           PointsToNode* ptn = ptnode_adr(in->_idx);
 655           assert(ptn != NULL, "node should be registered");
 656           add_edge(n_ptn, ptn);
 657         }
 658         break;
 659       }
 660       ELSE_FAIL("Op_Phi");
 661     }
 662     case Op_Proj: {
 663       // we are only interested in the oop result projection from a call
 664       if (n->as_Proj()->_con >= TypeFunc::Parms && n->in(0)->is_Call() &&
 665           (n->in(0)->as_Call()->returns_pointer()|| n->bottom_type()->isa_ptr())) {
 666         assert((n->as_Proj()->_con == TypeFunc::Parms && n->in(0)->as_Call()->returns_pointer()) ||
 667                n->in(0)->as_Call()->tf()->returns_value_type_as_fields(), "what kind of oop return is it?");
 668         add_local_var_and_edge(n, PointsToNode::NoEscape, n->in(0), NULL);
 669         break;
 670       }
 671       ELSE_FAIL("Op_Proj");
 672     }
 673     case Op_Rethrow: // Exception object escapes
 674     case Op_Return: {
 675       if (n->req() > TypeFunc::Parms &&
 676           _igvn->type(n->in(TypeFunc::Parms))->isa_oopptr()) {
 677         // Treat Return value as LocalVar with GlobalEscape escape state.
 678         add_local_var_and_edge(n, PointsToNode::GlobalEscape,
 679                                n->in(TypeFunc::Parms), NULL);
 680         break;
 681       }
 682       ELSE_FAIL("Op_Return");
 683     }
 684     case Op_StoreP:
 685     case Op_StoreN:
 686     case Op_StoreNKlass:
 687     case Op_StorePConditional:
 688     case Op_CompareAndExchangeP:
 689     case Op_CompareAndExchangeN:
 690     case Op_CompareAndSwapP:
 691     case Op_CompareAndSwapN:
 692     case Op_WeakCompareAndSwapP:
 693     case Op_WeakCompareAndSwapN:
 694     case Op_GetAndSetP:
 695     case Op_GetAndSetN: {
 696       if (add_final_edges_unsafe_access(n, opcode)) {
 697         break;
 698       }
 699       ELSE_FAIL("Op_StoreP");
 700     }
 701     case Op_AryEq:
 702     case Op_HasNegatives:
 703     case Op_StrComp:
 704     case Op_StrEquals:
 705     case Op_StrIndexOf:
 706     case Op_StrIndexOfChar:
 707     case Op_StrInflatedCopy:
 708     case Op_StrCompressedCopy:
 709     case Op_EncodeISOArray: {
 710       // char[]/byte[] arrays passed to string intrinsic do not escape but
 711       // they are not scalar replaceable. Adjust escape state for them.
 712       // Start from in(2) edge since in(1) is memory edge.
 713       for (uint i = 2; i < n->req(); i++) {
 714         Node* adr = n->in(i);
 715         const Type* at = _igvn->type(adr);
 716         if (!adr->is_top() && at->isa_ptr()) {
 717           assert(at == Type::TOP || at == TypePtr::NULL_PTR ||
 718                  at->isa_ptr() != NULL, "expecting a pointer");
 719           if (adr->is_AddP()) {
 720             adr = get_addp_base(adr);
 721           }
 722           PointsToNode* ptn = ptnode_adr(adr->_idx);
 723           assert(ptn != NULL, "node should be registered");
 724           add_edge(n_ptn, ptn);
 725         }
 726       }
 727       break;
 728     }
 729     default: {
 730       // This method should be called only for EA specific nodes which may
 731       // miss some edges when they were created.
 732 #ifdef ASSERT
 733       n->dump(1);
 734 #endif
 735       guarantee(false, "unknown node");
 736     }
 737   }
 738   return;
 739 }
 740 
 741 void ConnectionGraph::add_to_congraph_unsafe_access(Node* n, uint opcode, Unique_Node_List* delayed_worklist) {
 742   Node* adr = n->in(MemNode::Address);
 743   const Type* adr_type = _igvn->type(adr);
 744   adr_type = adr_type->make_ptr();
 745   if (adr_type == NULL) {
 746     return; // skip dead nodes
 747   }
 748   if (adr_type->isa_oopptr()
 749       || ((opcode == Op_StoreP || opcode == Op_StoreN || opcode == Op_StoreNKlass)
 750           && adr_type == TypeRawPtr::NOTNULL
 751           && adr->in(AddPNode::Address)->is_Proj()
 752           && adr->in(AddPNode::Address)->in(0)->is_Allocate())) {
 753     delayed_worklist->push(n); // Process it later.
 754 #ifdef ASSERT
 755     assert (adr->is_AddP(), "expecting an AddP");
 756     if (adr_type == TypeRawPtr::NOTNULL) {
 757       // Verify a raw address for a store captured by Initialize node.
 758       int offs = (int) _igvn->find_intptr_t_con(adr->in(AddPNode::Offset), Type::OffsetBot);
 759       assert(offs != Type::OffsetBot, "offset must be a constant");
 760     }
 761 #endif
 762   } else {
 763     // Ignore copy the displaced header to the BoxNode (OSR compilation).
 764     if (adr->is_BoxLock()) {
 765       return;
 766     }
 767     // Stored value escapes in unsafe access.
 768     if ((opcode == Op_StoreP) && adr_type->isa_rawptr()) {
 769       delayed_worklist->push(n); // Process unsafe access later.
 770       return;
 771     }
 772 #ifdef ASSERT
 773     n->dump(1);
 774     assert(false, "not unsafe");
 775 #endif
 776   }
 777 }
 778 
 779 bool ConnectionGraph::add_final_edges_unsafe_access(Node* n, uint opcode) {
 780   Node* adr = n->in(MemNode::Address);
 781   const Type *adr_type = _igvn->type(adr);
 782   adr_type = adr_type->make_ptr();
 783 #ifdef ASSERT
 784   if (adr_type == NULL) {
 785     n->dump(1);
 786     assert(adr_type != NULL, "dead node should not be on list");
 787     return true;
 788   }
 789 #endif
 790 
 791   if (opcode == Op_GetAndSetP || opcode == Op_GetAndSetN ||
 792       opcode == Op_CompareAndExchangeN || opcode == Op_CompareAndExchangeP) {
 793     add_local_var_and_edge(n, PointsToNode::NoEscape, adr, NULL);
 794   }
 795 
 796   if (adr_type->isa_oopptr()
 797       || ((opcode == Op_StoreP || opcode == Op_StoreN || opcode == Op_StoreNKlass)
 798            && adr_type == TypeRawPtr::NOTNULL
 799            && adr->in(AddPNode::Address)->is_Proj()
 800            && adr->in(AddPNode::Address)->in(0)->is_Allocate())) {
 801     // Point Address to Value
 802     PointsToNode* adr_ptn = ptnode_adr(adr->_idx);
 803     assert(adr_ptn != NULL &&
 804            adr_ptn->as_Field()->is_oop(), "node should be registered");
 805     Node* val = n->in(MemNode::ValueIn);
 806     PointsToNode* ptn = ptnode_adr(val->_idx);
 807     assert(ptn != NULL, "node should be registered");
 808     add_edge(adr_ptn, ptn);
 809     return true;
 810   } else if ((opcode == Op_StoreP) && adr_type->isa_rawptr()) {
 811     // Stored value escapes in unsafe access.
 812     Node* val = n->in(MemNode::ValueIn);
 813     PointsToNode* ptn = ptnode_adr(val->_idx);
 814     assert(ptn != NULL, "node should be registered");
 815     set_escape_state(ptn, PointsToNode::GlobalEscape);
 816     // Add edge to object for unsafe access with offset.
 817     PointsToNode* adr_ptn = ptnode_adr(adr->_idx);
 818     assert(adr_ptn != NULL, "node should be registered");
 819     if (adr_ptn->is_Field()) {
 820       assert(adr_ptn->as_Field()->is_oop(), "should be oop field");
 821       add_edge(adr_ptn, ptn);
 822     }
 823     return true;
 824   }
 825   return false;
 826 }
 827 
 828 void ConnectionGraph::add_call_node(CallNode* call) {
 829   assert(call->returns_pointer() || call->tf()->returns_value_type_as_fields(), "only for call which returns pointer");
 830   uint call_idx = call->_idx;
 831   if (call->is_Allocate()) {
 832     Node* k = call->in(AllocateNode::KlassNode);
 833     const TypeKlassPtr* kt = k->bottom_type()->isa_klassptr();
 834     assert(kt != NULL, "TypeKlassPtr  required.");
 835     ciKlass* cik = kt->klass();
 836     PointsToNode::EscapeState es = PointsToNode::NoEscape;
 837     bool scalar_replaceable = true;
 838     if (call->is_AllocateArray()) {
 839       if (!cik->is_array_klass()) { // StressReflectiveCode
 840         es = PointsToNode::GlobalEscape;
 841       } else {
 842         int length = call->in(AllocateNode::ALength)->find_int_con(-1);
 843         if (length < 0 || length > EliminateAllocationArraySizeLimit) {
 844           // Not scalar replaceable if the length is not constant or too big.
 845           scalar_replaceable = false;
 846         }
 847       }
 848     } else {  // Allocate instance
 849       if (cik->is_subclass_of(_compile->env()->Thread_klass()) ||
 850           cik->is_subclass_of(_compile->env()->Reference_klass()) ||
 851          !cik->is_instance_klass() || // StressReflectiveCode
 852          !cik->as_instance_klass()->can_be_instantiated() ||
 853           cik->as_instance_klass()->has_finalizer()) {
 854         es = PointsToNode::GlobalEscape;
 855       }
 856     }
 857     add_java_object(call, es);
 858     PointsToNode* ptn = ptnode_adr(call_idx);
 859     if (!scalar_replaceable && ptn->scalar_replaceable()) {
 860       ptn->set_scalar_replaceable(false);
 861     }
 862   } else if (call->is_CallStaticJava()) {
 863     // Call nodes could be different types:
 864     //
 865     // 1. CallDynamicJavaNode (what happened during call is unknown):
 866     //
 867     //    - mapped to GlobalEscape JavaObject node if oop is returned;
 868     //
 869     //    - all oop arguments are escaping globally;
 870     //
 871     // 2. CallStaticJavaNode (execute bytecode analysis if possible):
 872     //
 873     //    - the same as CallDynamicJavaNode if can't do bytecode analysis;
 874     //
 875     //    - mapped to GlobalEscape JavaObject node if unknown oop is returned;
 876     //    - mapped to NoEscape JavaObject node if non-escaping object allocated
 877     //      during call is returned;
 878     //    - mapped to ArgEscape LocalVar node pointed to object arguments
 879     //      which are returned and does not escape during call;
 880     //
 881     //    - oop arguments escaping status is defined by bytecode analysis;
 882     //
 883     // For a static call, we know exactly what method is being called.
 884     // Use bytecode estimator to record whether the call's return value escapes.
 885     ciMethod* meth = call->as_CallJava()->method();
 886     if (meth == NULL) {
 887       const char* name = call->as_CallStaticJava()->_name;
 888       assert(strncmp(name, "_multianewarray", 15) == 0, "TODO: add failed case check");
 889       // Returns a newly allocated unescaped object.
 890       add_java_object(call, PointsToNode::NoEscape);
 891       ptnode_adr(call_idx)->set_scalar_replaceable(false);
 892     } else if (meth->is_boxing_method()) {
 893       // Returns boxing object
 894       PointsToNode::EscapeState es;
 895       vmIntrinsics::ID intr = meth->intrinsic_id();
 896       if (intr == vmIntrinsics::_floatValue || intr == vmIntrinsics::_doubleValue) {
 897         // It does not escape if object is always allocated.
 898         es = PointsToNode::NoEscape;
 899       } else {
 900         // It escapes globally if object could be loaded from cache.
 901         es = PointsToNode::GlobalEscape;
 902       }
 903       add_java_object(call, es);
 904     } else {
 905       BCEscapeAnalyzer* call_analyzer = meth->get_bcea();
 906       call_analyzer->copy_dependencies(_compile->dependencies());
 907       if (call_analyzer->is_return_allocated()) {
 908         // Returns a newly allocated unescaped object, simply
 909         // update dependency information.
 910         // Mark it as NoEscape so that objects referenced by
 911         // it's fields will be marked as NoEscape at least.
 912         add_java_object(call, PointsToNode::NoEscape);
 913         ptnode_adr(call_idx)->set_scalar_replaceable(false);
 914       } else {
 915         // Determine whether any arguments are returned.
 916         const TypeTuple* d = call->tf()->domain_cc();
 917         bool ret_arg = false;
 918         for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
 919           if (d->field_at(i)->isa_ptr() != NULL &&
 920               call_analyzer->is_arg_returned(i - TypeFunc::Parms)) {
 921             ret_arg = true;
 922             break;
 923           }
 924         }
 925         if (ret_arg) {
 926           add_local_var(call, PointsToNode::ArgEscape);
 927         } else {
 928           // Returns unknown object.
 929           map_ideal_node(call, phantom_obj);
 930         }
 931       }
 932     }
 933   } else {
 934     // An other type of call, assume the worst case:
 935     // returned value is unknown and globally escapes.
 936     assert(call->Opcode() == Op_CallDynamicJava, "add failed case check");
 937     map_ideal_node(call, phantom_obj);
 938   }
 939 }
 940 
 941 void ConnectionGraph::process_call_arguments(CallNode *call) {
 942     bool is_arraycopy = false;
 943     switch (call->Opcode()) {
 944 #ifdef ASSERT
 945     case Op_Allocate:
 946     case Op_AllocateArray:
 947     case Op_Lock:
 948     case Op_Unlock:
 949       assert(false, "should be done already");
 950       break;
 951 #endif
 952     case Op_ArrayCopy:
 953     case Op_CallLeafNoFP:
 954       // Most array copies are ArrayCopy nodes at this point but there
 955       // are still a few direct calls to the copy subroutines (See
 956       // PhaseStringOpts::copy_string())
 957       is_arraycopy = (call->Opcode() == Op_ArrayCopy) ||
 958         call->as_CallLeaf()->is_call_to_arraycopystub();
 959       // fall through
 960     case Op_CallLeaf: {
 961       // Stub calls, objects do not escape but they are not scale replaceable.
 962       // Adjust escape state for outgoing arguments.
 963       const TypeTuple * d = call->tf()->domain_sig();
 964       bool src_has_oops = false;
 965       for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
 966         const Type* at = d->field_at(i);
 967         Node *arg = call->in(i);
 968         if (arg == NULL) {
 969           continue;
 970         }
 971         const Type *aat = _igvn->type(arg);
 972         if (arg->is_top() || !at->isa_ptr() || !aat->isa_ptr())
 973           continue;
 974         if (arg->is_AddP()) {
 975           //
 976           // The inline_native_clone() case when the arraycopy stub is called
 977           // after the allocation before Initialize and CheckCastPP nodes.
 978           // Or normal arraycopy for object arrays case.
 979           //
 980           // Set AddP's base (Allocate) as not scalar replaceable since
 981           // pointer to the base (with offset) is passed as argument.
 982           //
 983           arg = get_addp_base(arg);
 984         }
 985         PointsToNode* arg_ptn = ptnode_adr(arg->_idx);
 986         assert(arg_ptn != NULL, "should be registered");
 987         PointsToNode::EscapeState arg_esc = arg_ptn->escape_state();
 988         if (is_arraycopy || arg_esc < PointsToNode::ArgEscape) {
 989           assert(aat == Type::TOP || aat == TypePtr::NULL_PTR ||
 990                  aat->isa_ptr() != NULL, "expecting an Ptr");
 991           bool arg_has_oops = aat->isa_oopptr() &&
 992                               (aat->isa_oopptr()->klass() == NULL || aat->isa_instptr() ||
 993                                (aat->isa_aryptr() && aat->isa_aryptr()->klass()->is_obj_array_klass()) ||
 994                                (aat->isa_aryptr() && aat->isa_aryptr()->elem() != NULL &&
 995                                 aat->isa_aryptr()->elem()->isa_valuetype() &&
 996                                 aat->isa_aryptr()->elem()->value_klass()->contains_oops()));
 997           if (i == TypeFunc::Parms) {
 998             src_has_oops = arg_has_oops;
 999           }
1000           //
1001           // src or dst could be j.l.Object when other is basic type array:
1002           //
1003           //   arraycopy(char[],0,Object*,0,size);
1004           //   arraycopy(Object*,0,char[],0,size);
1005           //
1006           // Don't add edges in such cases.
1007           //
1008           bool arg_is_arraycopy_dest = src_has_oops && is_arraycopy &&
1009                                        arg_has_oops && (i > TypeFunc::Parms);
1010 #ifdef ASSERT
1011           if (!(is_arraycopy ||
1012                 BarrierSet::barrier_set()->barrier_set_c2()->is_gc_barrier_node(call) ||
1013                 (call->as_CallLeaf()->_name != NULL &&
1014                  (strcmp(call->as_CallLeaf()->_name, "updateBytesCRC32") == 0 ||
1015                   strcmp(call->as_CallLeaf()->_name, "updateBytesCRC32C") == 0 ||
1016                   strcmp(call->as_CallLeaf()->_name, "updateBytesAdler32") == 0 ||
1017                   strcmp(call->as_CallLeaf()->_name, "aescrypt_encryptBlock") == 0 ||
1018                   strcmp(call->as_CallLeaf()->_name, "aescrypt_decryptBlock") == 0 ||
1019                   strcmp(call->as_CallLeaf()->_name, "cipherBlockChaining_encryptAESCrypt") == 0 ||
1020                   strcmp(call->as_CallLeaf()->_name, "cipherBlockChaining_decryptAESCrypt") == 0 ||
1021                   strcmp(call->as_CallLeaf()->_name, "counterMode_AESCrypt") == 0 ||
1022                   strcmp(call->as_CallLeaf()->_name, "ghash_processBlocks") == 0 ||
1023                   strcmp(call->as_CallLeaf()->_name, "encodeBlock") == 0 ||
1024                   strcmp(call->as_CallLeaf()->_name, "sha1_implCompress") == 0 ||
1025                   strcmp(call->as_CallLeaf()->_name, "sha1_implCompressMB") == 0 ||
1026                   strcmp(call->as_CallLeaf()->_name, "sha256_implCompress") == 0 ||
1027                   strcmp(call->as_CallLeaf()->_name, "sha256_implCompressMB") == 0 ||
1028                   strcmp(call->as_CallLeaf()->_name, "sha512_implCompress") == 0 ||
1029                   strcmp(call->as_CallLeaf()->_name, "sha512_implCompressMB") == 0 ||
1030                   strcmp(call->as_CallLeaf()->_name, "multiplyToLen") == 0 ||
1031                   strcmp(call->as_CallLeaf()->_name, "squareToLen") == 0 ||
1032                   strcmp(call->as_CallLeaf()->_name, "mulAdd") == 0 ||
1033                   strcmp(call->as_CallLeaf()->_name, "montgomery_multiply") == 0 ||
1034                   strcmp(call->as_CallLeaf()->_name, "montgomery_square") == 0 ||
1035                   strcmp(call->as_CallLeaf()->_name, "vectorizedMismatch") == 0 ||
1036                   strcmp(call->as_CallLeaf()->_name, "load_unknown_value") == 0 ||
1037                   strcmp(call->as_CallLeaf()->_name, "store_unknown_value") == 0)
1038                  ))) {
1039             call->dump();
1040             fatal("EA unexpected CallLeaf %s", call->as_CallLeaf()->_name);
1041           }
1042 #endif
1043           // Always process arraycopy's destination object since
1044           // we need to add all possible edges to references in
1045           // source object.
1046           if (arg_esc >= PointsToNode::ArgEscape &&
1047               !arg_is_arraycopy_dest) {
1048             continue;
1049           }
1050           PointsToNode::EscapeState es = PointsToNode::ArgEscape;
1051           if (call->is_ArrayCopy()) {
1052             ArrayCopyNode* ac = call->as_ArrayCopy();
1053             if (ac->is_clonebasic() ||
1054                 ac->is_arraycopy_validated() ||
1055                 ac->is_copyof_validated() ||
1056                 ac->is_copyofrange_validated()) {
1057               es = PointsToNode::NoEscape;
1058             }
1059           }
1060           set_escape_state(arg_ptn, es);
1061           if (arg_is_arraycopy_dest) {
1062             Node* src = call->in(TypeFunc::Parms);
1063             if (src->is_AddP()) {
1064               src = get_addp_base(src);
1065             }
1066             PointsToNode* src_ptn = ptnode_adr(src->_idx);
1067             assert(src_ptn != NULL, "should be registered");
1068             if (arg_ptn != src_ptn) {
1069               // Special arraycopy edge:
1070               // A destination object's field can't have the source object
1071               // as base since objects escape states are not related.
1072               // Only escape state of destination object's fields affects
1073               // escape state of fields in source object.
1074               add_arraycopy(call, es, src_ptn, arg_ptn);
1075             }
1076           }
1077         }
1078       }
1079       break;
1080     }
1081     case Op_CallStaticJava: {
1082       // For a static call, we know exactly what method is being called.
1083       // Use bytecode estimator to record the call's escape affects
1084 #ifdef ASSERT
1085       const char* name = call->as_CallStaticJava()->_name;
1086       assert((name == NULL || strcmp(name, "uncommon_trap") != 0), "normal calls only");
1087 #endif
1088       ciMethod* meth = call->as_CallJava()->method();
1089       if ((meth != NULL) && meth->is_boxing_method()) {
1090         break; // Boxing methods do not modify any oops.
1091       }
1092       BCEscapeAnalyzer* call_analyzer = (meth !=NULL) ? meth->get_bcea() : NULL;
1093       // fall-through if not a Java method or no analyzer information
1094       if (call_analyzer != NULL) {
1095         PointsToNode* call_ptn = ptnode_adr(call->_idx);
1096         const TypeTuple* d = call->tf()->domain_cc();
1097         for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
1098           const Type* at = d->field_at(i);
1099           int k = i - TypeFunc::Parms;
1100           Node* arg = call->in(i);
1101           PointsToNode* arg_ptn = ptnode_adr(arg->_idx);
1102           if (at->isa_ptr() != NULL &&
1103               call_analyzer->is_arg_returned(k)) {
1104             // The call returns arguments.
1105             if (call_ptn != NULL) { // Is call's result used?
1106               assert(call_ptn->is_LocalVar(), "node should be registered");
1107               assert(arg_ptn != NULL, "node should be registered");
1108               add_edge(call_ptn, arg_ptn);
1109             }
1110           }
1111           if (at->isa_oopptr() != NULL &&
1112               arg_ptn->escape_state() < PointsToNode::GlobalEscape) {
1113             if (!call_analyzer->is_arg_stack(k)) {
1114               // The argument global escapes
1115               set_escape_state(arg_ptn, PointsToNode::GlobalEscape);
1116             } else {
1117               set_escape_state(arg_ptn, PointsToNode::ArgEscape);
1118               if (!call_analyzer->is_arg_local(k)) {
1119                 // The argument itself doesn't escape, but any fields might
1120                 set_fields_escape_state(arg_ptn, PointsToNode::GlobalEscape);
1121               }
1122             }
1123           }
1124         }
1125         if (call_ptn != NULL && call_ptn->is_LocalVar()) {
1126           // The call returns arguments.
1127           assert(call_ptn->edge_count() > 0, "sanity");
1128           if (!call_analyzer->is_return_local()) {
1129             // Returns also unknown object.
1130             add_edge(call_ptn, phantom_obj);
1131           }
1132         }
1133         break;
1134       }
1135     }
1136     default: {
1137       // Fall-through here if not a Java method or no analyzer information
1138       // or some other type of call, assume the worst case: all arguments
1139       // globally escape.
1140       const TypeTuple* d = call->tf()->domain_cc();
1141       for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
1142         const Type* at = d->field_at(i);
1143         if (at->isa_oopptr() != NULL) {
1144           Node* arg = call->in(i);
1145           if (arg->is_AddP()) {
1146             arg = get_addp_base(arg);
1147           }
1148           assert(ptnode_adr(arg->_idx) != NULL, "should be defined already");
1149           set_escape_state(ptnode_adr(arg->_idx), PointsToNode::GlobalEscape);
1150         }
1151       }
1152     }
1153   }
1154 }
1155 
1156 
1157 // Finish Graph construction.
1158 bool ConnectionGraph::complete_connection_graph(
1159                          GrowableArray<PointsToNode*>&   ptnodes_worklist,
1160                          GrowableArray<JavaObjectNode*>& non_escaped_worklist,
1161                          GrowableArray<JavaObjectNode*>& java_objects_worklist,
1162                          GrowableArray<FieldNode*>&      oop_fields_worklist) {
1163   // Normally only 1-3 passes needed to build Connection Graph depending
1164   // on graph complexity. Observed 8 passes in jvm2008 compiler.compiler.
1165   // Set limit to 20 to catch situation when something did go wrong and
1166   // bailout Escape Analysis.
1167   // Also limit build time to 20 sec (60 in debug VM), EscapeAnalysisTimeout flag.
1168 #define CG_BUILD_ITER_LIMIT 20
1169 
1170   // Propagate GlobalEscape and ArgEscape escape states and check that
1171   // we still have non-escaping objects. The method pushs on _worklist
1172   // Field nodes which reference phantom_object.
1173   if (!find_non_escaped_objects(ptnodes_worklist, non_escaped_worklist)) {
1174     return false; // Nothing to do.
1175   }
1176   // Now propagate references to all JavaObject nodes.
1177   int java_objects_length = java_objects_worklist.length();
1178   elapsedTimer time;
1179   bool timeout = false;
1180   int new_edges = 1;
1181   int iterations = 0;
1182   do {
1183     while ((new_edges > 0) &&
1184            (iterations++ < CG_BUILD_ITER_LIMIT)) {
1185       double start_time = time.seconds();
1186       time.start();
1187       new_edges = 0;
1188       // Propagate references to phantom_object for nodes pushed on _worklist
1189       // by find_non_escaped_objects() and find_field_value().
1190       new_edges += add_java_object_edges(phantom_obj, false);
1191       for (int next = 0; next < java_objects_length; ++next) {
1192         JavaObjectNode* ptn = java_objects_worklist.at(next);
1193         new_edges += add_java_object_edges(ptn, true);
1194 
1195 #define SAMPLE_SIZE 4
1196         if ((next % SAMPLE_SIZE) == 0) {
1197           // Each 4 iterations calculate how much time it will take
1198           // to complete graph construction.
1199           time.stop();
1200           // Poll for requests from shutdown mechanism to quiesce compiler
1201           // because Connection graph construction may take long time.
1202           CompileBroker::maybe_block();
1203           double stop_time = time.seconds();
1204           double time_per_iter = (stop_time - start_time) / (double)SAMPLE_SIZE;
1205           double time_until_end = time_per_iter * (double)(java_objects_length - next);
1206           if ((start_time + time_until_end) >= EscapeAnalysisTimeout) {
1207             timeout = true;
1208             break; // Timeout
1209           }
1210           start_time = stop_time;
1211           time.start();
1212         }
1213 #undef SAMPLE_SIZE
1214 
1215       }
1216       if (timeout) break;
1217       if (new_edges > 0) {
1218         // Update escape states on each iteration if graph was updated.
1219         if (!find_non_escaped_objects(ptnodes_worklist, non_escaped_worklist)) {
1220           return false; // Nothing to do.
1221         }
1222       }
1223       time.stop();
1224       if (time.seconds() >= EscapeAnalysisTimeout) {
1225         timeout = true;
1226         break;
1227       }
1228     }
1229     if ((iterations < CG_BUILD_ITER_LIMIT) && !timeout) {
1230       time.start();
1231       // Find fields which have unknown value.
1232       int fields_length = oop_fields_worklist.length();
1233       for (int next = 0; next < fields_length; next++) {
1234         FieldNode* field = oop_fields_worklist.at(next);
1235         if (field->edge_count() == 0) {
1236           new_edges += find_field_value(field);
1237           // This code may added new edges to phantom_object.
1238           // Need an other cycle to propagate references to phantom_object.
1239         }
1240       }
1241       time.stop();
1242       if (time.seconds() >= EscapeAnalysisTimeout) {
1243         timeout = true;
1244         break;
1245       }
1246     } else {
1247       new_edges = 0; // Bailout
1248     }
1249   } while (new_edges > 0);
1250 
1251   // Bailout if passed limits.
1252   if ((iterations >= CG_BUILD_ITER_LIMIT) || timeout) {
1253     Compile* C = _compile;
1254     if (C->log() != NULL) {
1255       C->log()->begin_elem("connectionGraph_bailout reason='reached ");
1256       C->log()->text("%s", timeout ? "time" : "iterations");
1257       C->log()->end_elem(" limit'");
1258     }
1259     assert(ExitEscapeAnalysisOnTimeout, "infinite EA connection graph build (%f sec, %d iterations) with %d nodes and worklist size %d",
1260            time.seconds(), iterations, nodes_size(), ptnodes_worklist.length());
1261     // Possible infinite build_connection_graph loop,
1262     // bailout (no changes to ideal graph were made).
1263     return false;
1264   }
1265 #ifdef ASSERT
1266   if (Verbose && PrintEscapeAnalysis) {
1267     tty->print_cr("EA: %d iterations to build connection graph with %d nodes and worklist size %d",
1268                   iterations, nodes_size(), ptnodes_worklist.length());
1269   }
1270 #endif
1271 
1272 #undef CG_BUILD_ITER_LIMIT
1273 
1274   // Find fields initialized by NULL for non-escaping Allocations.
1275   int non_escaped_length = non_escaped_worklist.length();
1276   for (int next = 0; next < non_escaped_length; next++) {
1277     JavaObjectNode* ptn = non_escaped_worklist.at(next);
1278     PointsToNode::EscapeState es = ptn->escape_state();
1279     assert(es <= PointsToNode::ArgEscape, "sanity");
1280     if (es == PointsToNode::NoEscape) {
1281       if (find_init_values(ptn, null_obj, _igvn) > 0) {
1282         // Adding references to NULL object does not change escape states
1283         // since it does not escape. Also no fields are added to NULL object.
1284         add_java_object_edges(null_obj, false);
1285       }
1286     }
1287     Node* n = ptn->ideal_node();
1288     if (n->is_Allocate()) {
1289       // The object allocated by this Allocate node will never be
1290       // seen by an other thread. Mark it so that when it is
1291       // expanded no MemBarStoreStore is added.
1292       InitializeNode* ini = n->as_Allocate()->initialization();
1293       if (ini != NULL)
1294         ini->set_does_not_escape();
1295     }
1296   }
1297   return true; // Finished graph construction.
1298 }
1299 
1300 // Propagate GlobalEscape and ArgEscape escape states to all nodes
1301 // and check that we still have non-escaping java objects.
1302 bool ConnectionGraph::find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist,
1303                                                GrowableArray<JavaObjectNode*>& non_escaped_worklist) {
1304   GrowableArray<PointsToNode*> escape_worklist;
1305   // First, put all nodes with GlobalEscape and ArgEscape states on worklist.
1306   int ptnodes_length = ptnodes_worklist.length();
1307   for (int next = 0; next < ptnodes_length; ++next) {
1308     PointsToNode* ptn = ptnodes_worklist.at(next);
1309     if (ptn->escape_state() >= PointsToNode::ArgEscape ||
1310         ptn->fields_escape_state() >= PointsToNode::ArgEscape) {
1311       escape_worklist.push(ptn);
1312     }
1313   }
1314   // Set escape states to referenced nodes (edges list).
1315   while (escape_worklist.length() > 0) {
1316     PointsToNode* ptn = escape_worklist.pop();
1317     PointsToNode::EscapeState es  = ptn->escape_state();
1318     PointsToNode::EscapeState field_es = ptn->fields_escape_state();
1319     if (ptn->is_Field() && ptn->as_Field()->is_oop() &&
1320         es >= PointsToNode::ArgEscape) {
1321       // GlobalEscape or ArgEscape state of field means it has unknown value.
1322       if (add_edge(ptn, phantom_obj)) {
1323         // New edge was added
1324         add_field_uses_to_worklist(ptn->as_Field());
1325       }
1326     }
1327     for (EdgeIterator i(ptn); i.has_next(); i.next()) {
1328       PointsToNode* e = i.get();
1329       if (e->is_Arraycopy()) {
1330         assert(ptn->arraycopy_dst(), "sanity");
1331         // Propagate only fields escape state through arraycopy edge.
1332         if (e->fields_escape_state() < field_es) {
1333           set_fields_escape_state(e, field_es);
1334           escape_worklist.push(e);
1335         }
1336       } else if (es >= field_es) {
1337         // fields_escape_state is also set to 'es' if it is less than 'es'.
1338         if (e->escape_state() < es) {
1339           set_escape_state(e, es);
1340           escape_worklist.push(e);
1341         }
1342       } else {
1343         // Propagate field escape state.
1344         bool es_changed = false;
1345         if (e->fields_escape_state() < field_es) {
1346           set_fields_escape_state(e, field_es);
1347           es_changed = true;
1348         }
1349         if ((e->escape_state() < field_es) &&
1350             e->is_Field() && ptn->is_JavaObject() &&
1351             e->as_Field()->is_oop()) {
1352           // Change escape state of referenced fields.
1353           set_escape_state(e, field_es);
1354           es_changed = true;
1355         } else if (e->escape_state() < es) {
1356           set_escape_state(e, es);
1357           es_changed = true;
1358         }
1359         if (es_changed) {
1360           escape_worklist.push(e);
1361         }
1362       }
1363     }
1364   }
1365   // Remove escaped objects from non_escaped list.
1366   for (int next = non_escaped_worklist.length()-1; next >= 0 ; --next) {
1367     JavaObjectNode* ptn = non_escaped_worklist.at(next);
1368     if (ptn->escape_state() >= PointsToNode::GlobalEscape) {
1369       non_escaped_worklist.delete_at(next);
1370     }
1371     if (ptn->escape_state() == PointsToNode::NoEscape) {
1372       // Find fields in non-escaped allocations which have unknown value.
1373       find_init_values(ptn, phantom_obj, NULL);
1374     }
1375   }
1376   return (non_escaped_worklist.length() > 0);
1377 }
1378 
1379 // Add all references to JavaObject node by walking over all uses.
1380 int ConnectionGraph::add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist) {
1381   int new_edges = 0;
1382   if (populate_worklist) {
1383     // Populate _worklist by uses of jobj's uses.
1384     for (UseIterator i(jobj); i.has_next(); i.next()) {
1385       PointsToNode* use = i.get();
1386       if (use->is_Arraycopy())
1387         continue;
1388       add_uses_to_worklist(use);
1389       if (use->is_Field() && use->as_Field()->is_oop()) {
1390         // Put on worklist all field's uses (loads) and
1391         // related field nodes (same base and offset).
1392         add_field_uses_to_worklist(use->as_Field());
1393       }
1394     }
1395   }
1396   for (int l = 0; l < _worklist.length(); l++) {
1397     PointsToNode* use = _worklist.at(l);
1398     if (PointsToNode::is_base_use(use)) {
1399       // Add reference from jobj to field and from field to jobj (field's base).
1400       use = PointsToNode::get_use_node(use)->as_Field();
1401       if (add_base(use->as_Field(), jobj)) {
1402         new_edges++;
1403       }
1404       continue;
1405     }
1406     assert(!use->is_JavaObject(), "sanity");
1407     if (use->is_Arraycopy()) {
1408       if (jobj == null_obj) // NULL object does not have field edges
1409         continue;
1410       // Added edge from Arraycopy node to arraycopy's source java object
1411       if (add_edge(use, jobj)) {
1412         jobj->set_arraycopy_src();
1413         new_edges++;
1414       }
1415       // and stop here.
1416       continue;
1417     }
1418     if (!add_edge(use, jobj))
1419       continue; // No new edge added, there was such edge already.
1420     new_edges++;
1421     if (use->is_LocalVar()) {
1422       add_uses_to_worklist(use);
1423       if (use->arraycopy_dst()) {
1424         for (EdgeIterator i(use); i.has_next(); i.next()) {
1425           PointsToNode* e = i.get();
1426           if (e->is_Arraycopy()) {
1427             if (jobj == null_obj) // NULL object does not have field edges
1428               continue;
1429             // Add edge from arraycopy's destination java object to Arraycopy node.
1430             if (add_edge(jobj, e)) {
1431               new_edges++;
1432               jobj->set_arraycopy_dst();
1433             }
1434           }
1435         }
1436       }
1437     } else {
1438       // Added new edge to stored in field values.
1439       // Put on worklist all field's uses (loads) and
1440       // related field nodes (same base and offset).
1441       add_field_uses_to_worklist(use->as_Field());
1442     }
1443   }
1444   _worklist.clear();
1445   _in_worklist.Reset();
1446   return new_edges;
1447 }
1448 
1449 // Put on worklist all related field nodes.
1450 void ConnectionGraph::add_field_uses_to_worklist(FieldNode* field) {
1451   assert(field->is_oop(), "sanity");
1452   int offset = field->offset();
1453   add_uses_to_worklist(field);
1454   // Loop over all bases of this field and push on worklist Field nodes
1455   // with the same offset and base (since they may reference the same field).
1456   for (BaseIterator i(field); i.has_next(); i.next()) {
1457     PointsToNode* base = i.get();
1458     add_fields_to_worklist(field, base);
1459     // Check if the base was source object of arraycopy and go over arraycopy's
1460     // destination objects since values stored to a field of source object are
1461     // accessable by uses (loads) of fields of destination objects.
1462     if (base->arraycopy_src()) {
1463       for (UseIterator j(base); j.has_next(); j.next()) {
1464         PointsToNode* arycp = j.get();
1465         if (arycp->is_Arraycopy()) {
1466           for (UseIterator k(arycp); k.has_next(); k.next()) {
1467             PointsToNode* abase = k.get();
1468             if (abase->arraycopy_dst() && abase != base) {
1469               // Look for the same arraycopy reference.
1470               add_fields_to_worklist(field, abase);
1471             }
1472           }
1473         }
1474       }
1475     }
1476   }
1477 }
1478 
1479 // Put on worklist all related field nodes.
1480 void ConnectionGraph::add_fields_to_worklist(FieldNode* field, PointsToNode* base) {
1481   int offset = field->offset();
1482   if (base->is_LocalVar()) {
1483     for (UseIterator j(base); j.has_next(); j.next()) {
1484       PointsToNode* f = j.get();
1485       if (PointsToNode::is_base_use(f)) { // Field
1486         f = PointsToNode::get_use_node(f);
1487         if (f == field || !f->as_Field()->is_oop())
1488           continue;
1489         int offs = f->as_Field()->offset();
1490         if (offs == offset || offset == Type::OffsetBot || offs == Type::OffsetBot) {
1491           add_to_worklist(f);
1492         }
1493       }
1494     }
1495   } else {
1496     assert(base->is_JavaObject(), "sanity");
1497     if (// Skip phantom_object since it is only used to indicate that
1498         // this field's content globally escapes.
1499         (base != phantom_obj) &&
1500         // NULL object node does not have fields.
1501         (base != null_obj)) {
1502       for (EdgeIterator i(base); i.has_next(); i.next()) {
1503         PointsToNode* f = i.get();
1504         // Skip arraycopy edge since store to destination object field
1505         // does not update value in source object field.
1506         if (f->is_Arraycopy()) {
1507           assert(base->arraycopy_dst(), "sanity");
1508           continue;
1509         }
1510         if (f == field || !f->as_Field()->is_oop())
1511           continue;
1512         int offs = f->as_Field()->offset();
1513         if (offs == offset || offset == Type::OffsetBot || offs == Type::OffsetBot) {
1514           add_to_worklist(f);
1515         }
1516       }
1517     }
1518   }
1519 }
1520 
1521 // Find fields which have unknown value.
1522 int ConnectionGraph::find_field_value(FieldNode* field) {
1523   // Escaped fields should have init value already.
1524   assert(field->escape_state() == PointsToNode::NoEscape, "sanity");
1525   int new_edges = 0;
1526   for (BaseIterator i(field); i.has_next(); i.next()) {
1527     PointsToNode* base = i.get();
1528     if (base->is_JavaObject()) {
1529       // Skip Allocate's fields which will be processed later.
1530       if (base->ideal_node()->is_Allocate())
1531         return 0;
1532       assert(base == null_obj, "only NULL ptr base expected here");
1533     }
1534   }
1535   if (add_edge(field, phantom_obj)) {
1536     // New edge was added
1537     new_edges++;
1538     add_field_uses_to_worklist(field);
1539   }
1540   return new_edges;
1541 }
1542 
1543 // Find fields initializing values for allocations.
1544 int ConnectionGraph::find_init_values(JavaObjectNode* pta, PointsToNode* init_val, PhaseTransform* phase) {
1545   assert(pta->escape_state() == PointsToNode::NoEscape, "Not escaped Allocate nodes only");
1546   int new_edges = 0;
1547   Node* alloc = pta->ideal_node();
1548   if (init_val == phantom_obj) {
1549     // Do nothing for Allocate nodes since its fields values are
1550     // "known" unless they are initialized by arraycopy/clone.
1551     if (alloc->is_Allocate() && !pta->arraycopy_dst())
1552       return 0;
1553     assert(pta->arraycopy_dst() || alloc->as_CallStaticJava(), "sanity");
1554 #ifdef ASSERT
1555     if (!pta->arraycopy_dst() && alloc->as_CallStaticJava()->method() == NULL) {
1556       const char* name = alloc->as_CallStaticJava()->_name;
1557       assert(strncmp(name, "_multianewarray", 15) == 0, "sanity");
1558     }
1559 #endif
1560     // Non-escaped allocation returned from Java or runtime call have
1561     // unknown values in fields.
1562     for (EdgeIterator i(pta); i.has_next(); i.next()) {
1563       PointsToNode* field = i.get();
1564       if (field->is_Field() && field->as_Field()->is_oop()) {
1565         if (add_edge(field, phantom_obj)) {
1566           // New edge was added
1567           new_edges++;
1568           add_field_uses_to_worklist(field->as_Field());
1569         }
1570       }
1571     }
1572     return new_edges;
1573   }
1574   assert(init_val == null_obj, "sanity");
1575   // Do nothing for Call nodes since its fields values are unknown.
1576   if (!alloc->is_Allocate())
1577     return 0;
1578 
1579   InitializeNode* ini = alloc->as_Allocate()->initialization();
1580   bool visited_bottom_offset = false;
1581   GrowableArray<int> offsets_worklist;
1582 
1583   // Check if an oop field's initializing value is recorded and add
1584   // a corresponding NULL if field's value if it is not recorded.
1585   // Connection Graph does not record a default initialization by NULL
1586   // captured by Initialize node.
1587   //
1588   for (EdgeIterator i(pta); i.has_next(); i.next()) {
1589     PointsToNode* field = i.get(); // Field (AddP)
1590     if (!field->is_Field() || !field->as_Field()->is_oop())
1591       continue; // Not oop field
1592     int offset = field->as_Field()->offset();
1593     if (offset == Type::OffsetBot) {
1594       if (!visited_bottom_offset) {
1595         // OffsetBot is used to reference array's element,
1596         // always add reference to NULL to all Field nodes since we don't
1597         // known which element is referenced.
1598         if (add_edge(field, null_obj)) {
1599           // New edge was added
1600           new_edges++;
1601           add_field_uses_to_worklist(field->as_Field());
1602           visited_bottom_offset = true;
1603         }
1604       }
1605     } else {
1606       // Check only oop fields.
1607       const Type* adr_type = field->ideal_node()->as_AddP()->bottom_type();
1608       if (adr_type->isa_rawptr()) {
1609 #ifdef ASSERT
1610         // Raw pointers are used for initializing stores so skip it
1611         // since it should be recorded already
1612         Node* base = get_addp_base(field->ideal_node());
1613         assert(adr_type->isa_rawptr() && base->is_Proj() &&
1614                (base->in(0) == alloc),"unexpected pointer type");
1615 #endif
1616         continue;
1617       }
1618       if (!offsets_worklist.contains(offset)) {
1619         offsets_worklist.append(offset);
1620         Node* value = NULL;
1621         if (ini != NULL) {
1622           // StoreP::memory_type() == T_ADDRESS
1623           BasicType ft = UseCompressedOops ? T_NARROWOOP : T_ADDRESS;
1624           Node* store = ini->find_captured_store(offset, type2aelembytes(ft, true), phase);
1625           // Make sure initializing store has the same type as this AddP.
1626           // This AddP may reference non existing field because it is on a
1627           // dead branch of bimorphic call which is not eliminated yet.
1628           if (store != NULL && store->is_Store() &&
1629               store->as_Store()->memory_type() == ft) {
1630             value = store->in(MemNode::ValueIn);
1631 #ifdef ASSERT
1632             if (VerifyConnectionGraph) {
1633               // Verify that AddP already points to all objects the value points to.
1634               PointsToNode* val = ptnode_adr(value->_idx);
1635               assert((val != NULL), "should be processed already");
1636               PointsToNode* missed_obj = NULL;
1637               if (val->is_JavaObject()) {
1638                 if (!field->points_to(val->as_JavaObject())) {
1639                   missed_obj = val;
1640                 }
1641               } else {
1642                 if (!val->is_LocalVar() || (val->edge_count() == 0)) {
1643                   tty->print_cr("----------init store has invalid value -----");
1644                   store->dump();
1645                   val->dump();
1646                   assert(val->is_LocalVar() && (val->edge_count() > 0), "should be processed already");
1647                 }
1648                 for (EdgeIterator j(val); j.has_next(); j.next()) {
1649                   PointsToNode* obj = j.get();
1650                   if (obj->is_JavaObject()) {
1651                     if (!field->points_to(obj->as_JavaObject())) {
1652                       missed_obj = obj;
1653                       break;
1654                     }
1655                   }
1656                 }
1657               }
1658               if (missed_obj != NULL) {
1659                 tty->print_cr("----------field---------------------------------");
1660                 field->dump();
1661                 tty->print_cr("----------missed reference to object------------");
1662                 missed_obj->dump();
1663                 tty->print_cr("----------object referenced by init store-------");
1664                 store->dump();
1665                 val->dump();
1666                 assert(!field->points_to(missed_obj->as_JavaObject()), "missed JavaObject reference");
1667               }
1668             }
1669 #endif
1670           } else {
1671             // There could be initializing stores which follow allocation.
1672             // For example, a volatile field store is not collected
1673             // by Initialize node.
1674             //
1675             // Need to check for dependent loads to separate such stores from
1676             // stores which follow loads. For now, add initial value NULL so
1677             // that compare pointers optimization works correctly.
1678           }
1679         }
1680         if (value == NULL) {
1681           // A field's initializing value was not recorded. Add NULL.
1682           if (add_edge(field, null_obj)) {
1683             // New edge was added
1684             new_edges++;
1685             add_field_uses_to_worklist(field->as_Field());
1686           }
1687         }
1688       }
1689     }
1690   }
1691   return new_edges;
1692 }
1693 
1694 // Adjust scalar_replaceable state after Connection Graph is built.
1695 void ConnectionGraph::adjust_scalar_replaceable_state(JavaObjectNode* jobj) {
1696   // Search for non-escaping objects which are not scalar replaceable
1697   // and mark them to propagate the state to referenced objects.
1698 
1699   // 1. An object is not scalar replaceable if the field into which it is
1700   // stored has unknown offset (stored into unknown element of an array).
1701   //
1702   for (UseIterator i(jobj); i.has_next(); i.next()) {
1703     PointsToNode* use = i.get();
1704     if (use->is_Arraycopy()) {
1705       continue;
1706     }
1707     if (use->is_Field()) {
1708       FieldNode* field = use->as_Field();
1709       assert(field->is_oop() && field->scalar_replaceable(), "sanity");
1710       if (field->offset() == Type::OffsetBot) {
1711         jobj->set_scalar_replaceable(false);
1712         return;
1713       }
1714       // 2. An object is not scalar replaceable if the field into which it is
1715       // stored has multiple bases one of which is null.
1716       if (field->base_count() > 1) {
1717         for (BaseIterator i(field); i.has_next(); i.next()) {
1718           PointsToNode* base = i.get();
1719           if (base == null_obj) {
1720             jobj->set_scalar_replaceable(false);
1721             return;
1722           }
1723         }
1724       }
1725     }
1726     assert(use->is_Field() || use->is_LocalVar(), "sanity");
1727     // 3. An object is not scalar replaceable if it is merged with other objects.
1728     for (EdgeIterator j(use); j.has_next(); j.next()) {
1729       PointsToNode* ptn = j.get();
1730       if (ptn->is_JavaObject() && ptn != jobj) {
1731         // Mark all objects.
1732         jobj->set_scalar_replaceable(false);
1733         ptn->set_scalar_replaceable(false);
1734       }
1735     }
1736     if (!jobj->scalar_replaceable()) {
1737       return;
1738     }
1739   }
1740 
1741   for (EdgeIterator j(jobj); j.has_next(); j.next()) {
1742     if (j.get()->is_Arraycopy()) {
1743       continue;
1744     }
1745 
1746     // Non-escaping object node should point only to field nodes.
1747     FieldNode* field = j.get()->as_Field();
1748     int offset = field->as_Field()->offset();
1749 
1750     // 4. An object is not scalar replaceable if it has a field with unknown
1751     // offset (array's element is accessed in loop).
1752     if (offset == Type::OffsetBot) {
1753       jobj->set_scalar_replaceable(false);
1754       return;
1755     }
1756     // 5. Currently an object is not scalar replaceable if a LoadStore node
1757     // access its field since the field value is unknown after it.
1758     //
1759     Node* n = field->ideal_node();
1760 
1761     // Test for an unsafe access that was parsed as maybe off heap
1762     // (with a CheckCastPP to raw memory).
1763     assert(n->is_AddP(), "expect an address computation");
1764     if (n->in(AddPNode::Base)->is_top() &&
1765         n->in(AddPNode::Address)->Opcode() == Op_CheckCastPP) {
1766       assert(n->in(AddPNode::Address)->bottom_type()->isa_rawptr(), "raw address so raw cast expected");
1767       assert(_igvn->type(n->in(AddPNode::Address)->in(1))->isa_oopptr(), "cast pattern at unsafe access expected");
1768       jobj->set_scalar_replaceable(false);
1769       return;
1770     }
1771 
1772     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1773       Node* u = n->fast_out(i);
1774       if (u->is_LoadStore() || (u->is_Mem() && u->as_Mem()->is_mismatched_access())) {
1775         jobj->set_scalar_replaceable(false);
1776         return;
1777       }
1778     }
1779 
1780     // 6. Or the address may point to more then one object. This may produce
1781     // the false positive result (set not scalar replaceable)
1782     // since the flow-insensitive escape analysis can't separate
1783     // the case when stores overwrite the field's value from the case
1784     // when stores happened on different control branches.
1785     //
1786     // Note: it will disable scalar replacement in some cases:
1787     //
1788     //    Point p[] = new Point[1];
1789     //    p[0] = new Point(); // Will be not scalar replaced
1790     //
1791     // but it will save us from incorrect optimizations in next cases:
1792     //
1793     //    Point p[] = new Point[1];
1794     //    if ( x ) p[0] = new Point(); // Will be not scalar replaced
1795     //
1796     if (field->base_count() > 1) {
1797       for (BaseIterator i(field); i.has_next(); i.next()) {
1798         PointsToNode* base = i.get();
1799         // Don't take into account LocalVar nodes which
1800         // may point to only one object which should be also
1801         // this field's base by now.
1802         if (base->is_JavaObject() && base != jobj) {
1803           // Mark all bases.
1804           jobj->set_scalar_replaceable(false);
1805           base->set_scalar_replaceable(false);
1806         }
1807       }
1808     }
1809   }
1810 }
1811 
1812 #ifdef ASSERT
1813 void ConnectionGraph::verify_connection_graph(
1814                          GrowableArray<PointsToNode*>&   ptnodes_worklist,
1815                          GrowableArray<JavaObjectNode*>& non_escaped_worklist,
1816                          GrowableArray<JavaObjectNode*>& java_objects_worklist,
1817                          GrowableArray<Node*>& addp_worklist) {
1818   // Verify that graph is complete - no new edges could be added.
1819   int java_objects_length = java_objects_worklist.length();
1820   int non_escaped_length  = non_escaped_worklist.length();
1821   int new_edges = 0;
1822   for (int next = 0; next < java_objects_length; ++next) {
1823     JavaObjectNode* ptn = java_objects_worklist.at(next);
1824     new_edges += add_java_object_edges(ptn, true);
1825   }
1826   assert(new_edges == 0, "graph was not complete");
1827   // Verify that escape state is final.
1828   int length = non_escaped_worklist.length();
1829   find_non_escaped_objects(ptnodes_worklist, non_escaped_worklist);
1830   assert((non_escaped_length == non_escaped_worklist.length()) &&
1831          (non_escaped_length == length) &&
1832          (_worklist.length() == 0), "escape state was not final");
1833 
1834   // Verify fields information.
1835   int addp_length = addp_worklist.length();
1836   for (int next = 0; next < addp_length; ++next ) {
1837     Node* n = addp_worklist.at(next);
1838     FieldNode* field = ptnode_adr(n->_idx)->as_Field();
1839     if (field->is_oop()) {
1840       // Verify that field has all bases
1841       Node* base = get_addp_base(n);
1842       PointsToNode* ptn = ptnode_adr(base->_idx);
1843       if (ptn->is_JavaObject()) {
1844         assert(field->has_base(ptn->as_JavaObject()), "sanity");
1845       } else {
1846         assert(ptn->is_LocalVar(), "sanity");
1847         for (EdgeIterator i(ptn); i.has_next(); i.next()) {
1848           PointsToNode* e = i.get();
1849           if (e->is_JavaObject()) {
1850             assert(field->has_base(e->as_JavaObject()), "sanity");
1851           }
1852         }
1853       }
1854       // Verify that all fields have initializing values.
1855       if (field->edge_count() == 0) {
1856         tty->print_cr("----------field does not have references----------");
1857         field->dump();
1858         for (BaseIterator i(field); i.has_next(); i.next()) {
1859           PointsToNode* base = i.get();
1860           tty->print_cr("----------field has next base---------------------");
1861           base->dump();
1862           if (base->is_JavaObject() && (base != phantom_obj) && (base != null_obj)) {
1863             tty->print_cr("----------base has fields-------------------------");
1864             for (EdgeIterator j(base); j.has_next(); j.next()) {
1865               j.get()->dump();
1866             }
1867             tty->print_cr("----------base has references---------------------");
1868             for (UseIterator j(base); j.has_next(); j.next()) {
1869               j.get()->dump();
1870             }
1871           }
1872         }
1873         for (UseIterator i(field); i.has_next(); i.next()) {
1874           i.get()->dump();
1875         }
1876         assert(field->edge_count() > 0, "sanity");
1877       }
1878     }
1879   }
1880 }
1881 #endif
1882 
1883 // Optimize ideal graph.
1884 void ConnectionGraph::optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist,
1885                                            GrowableArray<Node*>& storestore_worklist) {
1886   Compile* C = _compile;
1887   PhaseIterGVN* igvn = _igvn;
1888   if (EliminateLocks) {
1889     // Mark locks before changing ideal graph.
1890     int cnt = C->macro_count();
1891     for( int i=0; i < cnt; i++ ) {
1892       Node *n = C->macro_node(i);
1893       if (n->is_AbstractLock()) { // Lock and Unlock nodes
1894         AbstractLockNode* alock = n->as_AbstractLock();
1895         if (!alock->is_non_esc_obj()) {
1896           if (not_global_escape(alock->obj_node())) {
1897             assert(!alock->is_eliminated() || alock->is_coarsened(), "sanity");
1898             // The lock could be marked eliminated by lock coarsening
1899             // code during first IGVN before EA. Replace coarsened flag
1900             // to eliminate all associated locks/unlocks.
1901 #ifdef ASSERT
1902             alock->log_lock_optimization(C, "eliminate_lock_set_non_esc3");
1903 #endif
1904             alock->set_non_esc_obj();
1905           }
1906         }
1907       }
1908     }
1909   }
1910 
1911   if (OptimizePtrCompare) {
1912     // Add ConI(#CC_GT) and ConI(#CC_EQ).
1913     _pcmp_neq = igvn->makecon(TypeInt::CC_GT);
1914     _pcmp_eq = igvn->makecon(TypeInt::CC_EQ);
1915     // Optimize objects compare.
1916     while (ptr_cmp_worklist.length() != 0) {
1917       Node *n = ptr_cmp_worklist.pop();
1918       Node *res = optimize_ptr_compare(n);
1919       if (res != NULL) {
1920 #ifndef PRODUCT
1921         if (PrintOptimizePtrCompare) {
1922           tty->print_cr("++++ Replaced: %d %s(%d,%d) --> %s", n->_idx, (n->Opcode() == Op_CmpP ? "CmpP" : "CmpN"), n->in(1)->_idx, n->in(2)->_idx, (res == _pcmp_eq ? "EQ" : "NotEQ"));
1923           if (Verbose) {
1924             n->dump(1);
1925           }
1926         }
1927 #endif
1928         igvn->replace_node(n, res);
1929       }
1930     }
1931     // cleanup
1932     if (_pcmp_neq->outcnt() == 0)
1933       igvn->hash_delete(_pcmp_neq);
1934     if (_pcmp_eq->outcnt()  == 0)
1935       igvn->hash_delete(_pcmp_eq);
1936   }
1937 
1938   // For MemBarStoreStore nodes added in library_call.cpp, check
1939   // escape status of associated AllocateNode and optimize out
1940   // MemBarStoreStore node if the allocated object never escapes.
1941   while (storestore_worklist.length() != 0) {
1942     Node *n = storestore_worklist.pop();
1943     MemBarStoreStoreNode *storestore = n ->as_MemBarStoreStore();
1944     Node *alloc = storestore->in(MemBarNode::Precedent)->in(0);
1945     assert (alloc->is_Allocate(), "storestore should point to AllocateNode");
1946     if (not_global_escape(alloc)) {
1947       MemBarNode* mb = MemBarNode::make(C, Op_MemBarCPUOrder, Compile::AliasIdxBot);
1948       mb->init_req(TypeFunc::Memory, storestore->in(TypeFunc::Memory));
1949       mb->init_req(TypeFunc::Control, storestore->in(TypeFunc::Control));
1950       igvn->register_new_node_with_optimizer(mb);
1951       igvn->replace_node(storestore, mb);
1952     }
1953   }
1954 }
1955 
1956 // Optimize objects compare.
1957 Node* ConnectionGraph::optimize_ptr_compare(Node* n) {
1958   assert(OptimizePtrCompare, "sanity");
1959   PointsToNode* ptn1 = ptnode_adr(n->in(1)->_idx);
1960   PointsToNode* ptn2 = ptnode_adr(n->in(2)->_idx);
1961   JavaObjectNode* jobj1 = unique_java_object(n->in(1));
1962   JavaObjectNode* jobj2 = unique_java_object(n->in(2));
1963   assert(ptn1->is_JavaObject() || ptn1->is_LocalVar(), "sanity");
1964   assert(ptn2->is_JavaObject() || ptn2->is_LocalVar(), "sanity");
1965 
1966   // Check simple cases first.
1967   if (jobj1 != NULL) {
1968     if (jobj1->escape_state() == PointsToNode::NoEscape) {
1969       if (jobj1 == jobj2) {
1970         // Comparing the same not escaping object.
1971         return _pcmp_eq;
1972       }
1973       Node* obj = jobj1->ideal_node();
1974       // Comparing not escaping allocation.
1975       if ((obj->is_Allocate() || obj->is_CallStaticJava()) &&
1976           !ptn2->points_to(jobj1)) {
1977         return _pcmp_neq; // This includes nullness check.
1978       }
1979     }
1980   }
1981   if (jobj2 != NULL) {
1982     if (jobj2->escape_state() == PointsToNode::NoEscape) {
1983       Node* obj = jobj2->ideal_node();
1984       // Comparing not escaping allocation.
1985       if ((obj->is_Allocate() || obj->is_CallStaticJava()) &&
1986           !ptn1->points_to(jobj2)) {
1987         return _pcmp_neq; // This includes nullness check.
1988       }
1989     }
1990   }
1991   if (jobj1 != NULL && jobj1 != phantom_obj &&
1992       jobj2 != NULL && jobj2 != phantom_obj &&
1993       jobj1->ideal_node()->is_Con() &&
1994       jobj2->ideal_node()->is_Con()) {
1995     // Klass or String constants compare. Need to be careful with
1996     // compressed pointers - compare types of ConN and ConP instead of nodes.
1997     const Type* t1 = jobj1->ideal_node()->get_ptr_type();
1998     const Type* t2 = jobj2->ideal_node()->get_ptr_type();
1999     if (t1->make_ptr() == t2->make_ptr()) {
2000       return _pcmp_eq;
2001     } else {
2002       return _pcmp_neq;
2003     }
2004   }
2005   if (ptn1->meet(ptn2)) {
2006     return NULL; // Sets are not disjoint
2007   }
2008 
2009   // Sets are disjoint.
2010   bool set1_has_unknown_ptr = ptn1->points_to(phantom_obj);
2011   bool set2_has_unknown_ptr = ptn2->points_to(phantom_obj);
2012   bool set1_has_null_ptr    = ptn1->points_to(null_obj);
2013   bool set2_has_null_ptr    = ptn2->points_to(null_obj);
2014   if ((set1_has_unknown_ptr && set2_has_null_ptr) ||
2015       (set2_has_unknown_ptr && set1_has_null_ptr)) {
2016     // Check nullness of unknown object.
2017     return NULL;
2018   }
2019 
2020   // Disjointness by itself is not sufficient since
2021   // alias analysis is not complete for escaped objects.
2022   // Disjoint sets are definitely unrelated only when
2023   // at least one set has only not escaping allocations.
2024   if (!set1_has_unknown_ptr && !set1_has_null_ptr) {
2025     if (ptn1->non_escaping_allocation()) {
2026       return _pcmp_neq;
2027     }
2028   }
2029   if (!set2_has_unknown_ptr && !set2_has_null_ptr) {
2030     if (ptn2->non_escaping_allocation()) {
2031       return _pcmp_neq;
2032     }
2033   }
2034   return NULL;
2035 }
2036 
2037 // Connection Graph constuction functions.
2038 
2039 void ConnectionGraph::add_local_var(Node *n, PointsToNode::EscapeState es) {
2040   PointsToNode* ptadr = _nodes.at(n->_idx);
2041   if (ptadr != NULL) {
2042     assert(ptadr->is_LocalVar() && ptadr->ideal_node() == n, "sanity");
2043     return;
2044   }
2045   Compile* C = _compile;
2046   ptadr = new (C->comp_arena()) LocalVarNode(this, n, es);
2047   _nodes.at_put(n->_idx, ptadr);
2048 }
2049 
2050 void ConnectionGraph::add_java_object(Node *n, PointsToNode::EscapeState es) {
2051   PointsToNode* ptadr = _nodes.at(n->_idx);
2052   if (ptadr != NULL) {
2053     assert(ptadr->is_JavaObject() && ptadr->ideal_node() == n, "sanity");
2054     return;
2055   }
2056   Compile* C = _compile;
2057   ptadr = new (C->comp_arena()) JavaObjectNode(this, n, es);
2058   _nodes.at_put(n->_idx, ptadr);
2059 }
2060 
2061 void ConnectionGraph::add_field(Node *n, PointsToNode::EscapeState es, int offset) {
2062   PointsToNode* ptadr = _nodes.at(n->_idx);
2063   if (ptadr != NULL) {
2064     assert(ptadr->is_Field() && ptadr->ideal_node() == n, "sanity");
2065     return;
2066   }
2067   bool unsafe = false;
2068   bool is_oop = is_oop_field(n, offset, &unsafe);
2069   if (unsafe) {
2070     es = PointsToNode::GlobalEscape;
2071   }
2072   Compile* C = _compile;
2073   FieldNode* field = new (C->comp_arena()) FieldNode(this, n, es, offset, is_oop);
2074   _nodes.at_put(n->_idx, field);
2075 }
2076 
2077 void ConnectionGraph::add_arraycopy(Node *n, PointsToNode::EscapeState es,
2078                                     PointsToNode* src, PointsToNode* dst) {
2079   assert(!src->is_Field() && !dst->is_Field(), "only for JavaObject and LocalVar");
2080   assert((src != null_obj) && (dst != null_obj), "not for ConP NULL");
2081   PointsToNode* ptadr = _nodes.at(n->_idx);
2082   if (ptadr != NULL) {
2083     assert(ptadr->is_Arraycopy() && ptadr->ideal_node() == n, "sanity");
2084     return;
2085   }
2086   Compile* C = _compile;
2087   ptadr = new (C->comp_arena()) ArraycopyNode(this, n, es);
2088   _nodes.at_put(n->_idx, ptadr);
2089   // Add edge from arraycopy node to source object.
2090   (void)add_edge(ptadr, src);
2091   src->set_arraycopy_src();
2092   // Add edge from destination object to arraycopy node.
2093   (void)add_edge(dst, ptadr);
2094   dst->set_arraycopy_dst();
2095 }
2096 
2097 bool ConnectionGraph::is_oop_field(Node* n, int offset, bool* unsafe) {
2098   const Type* adr_type = n->as_AddP()->bottom_type();
2099   int field_offset = adr_type->isa_aryptr() ? adr_type->isa_aryptr()->field_offset().get() : Type::OffsetBot;
2100   BasicType bt = T_INT;
2101   if (offset == Type::OffsetBot && field_offset == Type::OffsetBot) {
2102     // Check only oop fields.
2103     if (!adr_type->isa_aryptr() ||
2104         (adr_type->isa_aryptr()->klass() == NULL) ||
2105          adr_type->isa_aryptr()->klass()->is_obj_array_klass()) {
2106       // OffsetBot is used to reference array's element. Ignore first AddP.
2107       if (find_second_addp(n, n->in(AddPNode::Base)) == NULL) {
2108         bt = T_OBJECT;
2109       }
2110     }
2111   } else if (offset != oopDesc::klass_offset_in_bytes()) {
2112     if (adr_type->isa_instptr()) {
2113       ciField* field = _compile->alias_type(adr_type->is_ptr())->field();
2114       if (field != NULL) {
2115         bt = field->layout_type();
2116       } else {
2117         // Check for unsafe oop field access
2118         if (n->has_out_with(Op_StoreP, Op_LoadP, Op_StoreN, Op_LoadN) ||
2119             n->has_out_with(Op_GetAndSetP, Op_GetAndSetN, Op_CompareAndExchangeP, Op_CompareAndExchangeN) ||
2120             n->has_out_with(Op_CompareAndSwapP, Op_CompareAndSwapN, Op_WeakCompareAndSwapP, Op_WeakCompareAndSwapN) ||
2121             BarrierSet::barrier_set()->barrier_set_c2()->escape_has_out_with_unsafe_object(n)) {
2122           bt = T_OBJECT;
2123           (*unsafe) = true;
2124         }
2125       }
2126     } else if (adr_type->isa_aryptr()) {
2127       if (offset == arrayOopDesc::length_offset_in_bytes()) {
2128         // Ignore array length load.
2129       } else if (find_second_addp(n, n->in(AddPNode::Base)) != NULL) {
2130         // Ignore first AddP.
2131       } else {
2132         const Type* elemtype = adr_type->isa_aryptr()->elem();
2133         if (elemtype->isa_valuetype() && field_offset != Type::OffsetBot) {
2134           ciValueKlass* vk = elemtype->value_klass();
2135           field_offset += vk->first_field_offset();
2136           bt = vk->get_field_by_offset(field_offset, false)->layout_type();
2137         } else {
2138           bt = elemtype->array_element_basic_type();
2139         }
2140       }
2141     } else if (adr_type->isa_rawptr() || adr_type->isa_klassptr()) {
2142       // Allocation initialization, ThreadLocal field access, unsafe access
2143       if (n->has_out_with(Op_StoreP, Op_LoadP, Op_StoreN, Op_LoadN) ||
2144           n->has_out_with(Op_GetAndSetP, Op_GetAndSetN, Op_CompareAndExchangeP, Op_CompareAndExchangeN) ||
2145           n->has_out_with(Op_CompareAndSwapP, Op_CompareAndSwapN, Op_WeakCompareAndSwapP, Op_WeakCompareAndSwapN) ||
2146           BarrierSet::barrier_set()->barrier_set_c2()->escape_has_out_with_unsafe_object(n)) {
2147         bt = T_OBJECT;
2148       }
2149     }
2150   }
2151   return (bt == T_OBJECT || bt == T_VALUETYPE || bt == T_NARROWOOP || bt == T_ARRAY);
2152 }
2153 
2154 // Returns unique pointed java object or NULL.
2155 JavaObjectNode* ConnectionGraph::unique_java_object(Node *n) {
2156   assert(!_collecting, "should not call when constructed graph");
2157   // If the node was created after the escape computation we can't answer.
2158   uint idx = n->_idx;
2159   if (idx >= nodes_size()) {
2160     return NULL;
2161   }
2162   PointsToNode* ptn = ptnode_adr(idx);
2163   if (ptn->is_JavaObject()) {
2164     return ptn->as_JavaObject();
2165   }
2166   assert(ptn->is_LocalVar(), "sanity");
2167   // Check all java objects it points to.
2168   JavaObjectNode* jobj = NULL;
2169   for (EdgeIterator i(ptn); i.has_next(); i.next()) {
2170     PointsToNode* e = i.get();
2171     if (e->is_JavaObject()) {
2172       if (jobj == NULL) {
2173         jobj = e->as_JavaObject();
2174       } else if (jobj != e) {
2175         return NULL;
2176       }
2177     }
2178   }
2179   return jobj;
2180 }
2181 
2182 // Return true if this node points only to non-escaping allocations.
2183 bool PointsToNode::non_escaping_allocation() {
2184   if (is_JavaObject()) {
2185     Node* n = ideal_node();
2186     if (n->is_Allocate() || n->is_CallStaticJava()) {
2187       return (escape_state() == PointsToNode::NoEscape);
2188     } else {
2189       return false;
2190     }
2191   }
2192   assert(is_LocalVar(), "sanity");
2193   // Check all java objects it points to.
2194   for (EdgeIterator i(this); i.has_next(); i.next()) {
2195     PointsToNode* e = i.get();
2196     if (e->is_JavaObject()) {
2197       Node* n = e->ideal_node();
2198       if ((e->escape_state() != PointsToNode::NoEscape) ||
2199           !(n->is_Allocate() || n->is_CallStaticJava())) {
2200         return false;
2201       }
2202     }
2203   }
2204   return true;
2205 }
2206 
2207 // Return true if we know the node does not escape globally.
2208 bool ConnectionGraph::not_global_escape(Node *n) {
2209   assert(!_collecting, "should not call during graph construction");
2210   // If the node was created after the escape computation we can't answer.
2211   uint idx = n->_idx;
2212   if (idx >= nodes_size()) {
2213     return false;
2214   }
2215   PointsToNode* ptn = ptnode_adr(idx);
2216   PointsToNode::EscapeState es = ptn->escape_state();
2217   // If we have already computed a value, return it.
2218   if (es >= PointsToNode::GlobalEscape)
2219     return false;
2220   if (ptn->is_JavaObject()) {
2221     return true; // (es < PointsToNode::GlobalEscape);
2222   }
2223   assert(ptn->is_LocalVar(), "sanity");
2224   // Check all java objects it points to.
2225   for (EdgeIterator i(ptn); i.has_next(); i.next()) {
2226     if (i.get()->escape_state() >= PointsToNode::GlobalEscape)
2227       return false;
2228   }
2229   return true;
2230 }
2231 
2232 
2233 // Helper functions
2234 
2235 // Return true if this node points to specified node or nodes it points to.
2236 bool PointsToNode::points_to(JavaObjectNode* ptn) const {
2237   if (is_JavaObject()) {
2238     return (this == ptn);
2239   }
2240   assert(is_LocalVar() || is_Field(), "sanity");
2241   for (EdgeIterator i(this); i.has_next(); i.next()) {
2242     if (i.get() == ptn)
2243       return true;
2244   }
2245   return false;
2246 }
2247 
2248 // Return true if one node points to an other.
2249 bool PointsToNode::meet(PointsToNode* ptn) {
2250   if (this == ptn) {
2251     return true;
2252   } else if (ptn->is_JavaObject()) {
2253     return this->points_to(ptn->as_JavaObject());
2254   } else if (this->is_JavaObject()) {
2255     return ptn->points_to(this->as_JavaObject());
2256   }
2257   assert(this->is_LocalVar() && ptn->is_LocalVar(), "sanity");
2258   int ptn_count =  ptn->edge_count();
2259   for (EdgeIterator i(this); i.has_next(); i.next()) {
2260     PointsToNode* this_e = i.get();
2261     for (int j = 0; j < ptn_count; j++) {
2262       if (this_e == ptn->edge(j))
2263         return true;
2264     }
2265   }
2266   return false;
2267 }
2268 
2269 #ifdef ASSERT
2270 // Return true if bases point to this java object.
2271 bool FieldNode::has_base(JavaObjectNode* jobj) const {
2272   for (BaseIterator i(this); i.has_next(); i.next()) {
2273     if (i.get() == jobj)
2274       return true;
2275   }
2276   return false;
2277 }
2278 #endif
2279 
2280 int ConnectionGraph::address_offset(Node* adr, PhaseTransform *phase) {
2281   const Type *adr_type = phase->type(adr);
2282   if (adr->is_AddP() && adr_type->isa_oopptr() == NULL &&
2283       adr->in(AddPNode::Address)->is_Proj() &&
2284       adr->in(AddPNode::Address)->in(0)->is_Allocate()) {
2285     // We are computing a raw address for a store captured by an Initialize
2286     // compute an appropriate address type. AddP cases #3 and #5 (see below).
2287     int offs = (int)phase->find_intptr_t_con(adr->in(AddPNode::Offset), Type::OffsetBot);
2288     assert(offs != Type::OffsetBot ||
2289            adr->in(AddPNode::Address)->in(0)->is_AllocateArray(),
2290            "offset must be a constant or it is initialization of array");
2291     return offs;
2292   }
2293   return adr_type->is_ptr()->flattened_offset();
2294 }
2295 
2296 Node* ConnectionGraph::get_addp_base(Node *addp) {
2297   assert(addp->is_AddP(), "must be AddP");
2298   //
2299   // AddP cases for Base and Address inputs:
2300   // case #1. Direct object's field reference:
2301   //     Allocate
2302   //       |
2303   //     Proj #5 ( oop result )
2304   //       |
2305   //     CheckCastPP (cast to instance type)
2306   //      | |
2307   //     AddP  ( base == address )
2308   //
2309   // case #2. Indirect object's field reference:
2310   //      Phi
2311   //       |
2312   //     CastPP (cast to instance type)
2313   //      | |
2314   //     AddP  ( base == address )
2315   //
2316   // case #3. Raw object's field reference for Initialize node:
2317   //      Allocate
2318   //        |
2319   //      Proj #5 ( oop result )
2320   //  top   |
2321   //     \  |
2322   //     AddP  ( base == top )
2323   //
2324   // case #4. Array's element reference:
2325   //   {CheckCastPP | CastPP}
2326   //     |  | |
2327   //     |  AddP ( array's element offset )
2328   //     |  |
2329   //     AddP ( array's offset )
2330   //
2331   // case #5. Raw object's field reference for arraycopy stub call:
2332   //          The inline_native_clone() case when the arraycopy stub is called
2333   //          after the allocation before Initialize and CheckCastPP nodes.
2334   //      Allocate
2335   //        |
2336   //      Proj #5 ( oop result )
2337   //       | |
2338   //       AddP  ( base == address )
2339   //
2340   // case #6. Constant Pool, ThreadLocal, CastX2P or
2341   //          Raw object's field reference:
2342   //      {ConP, ThreadLocal, CastX2P, raw Load}
2343   //  top   |
2344   //     \  |
2345   //     AddP  ( base == top )
2346   //
2347   // case #7. Klass's field reference.
2348   //      LoadKlass
2349   //       | |
2350   //       AddP  ( base == address )
2351   //
2352   // case #8. narrow Klass's field reference.
2353   //      LoadNKlass
2354   //       |
2355   //      DecodeN
2356   //       | |
2357   //       AddP  ( base == address )
2358   //
2359   // case #9. Mixed unsafe access
2360   //    {instance}
2361   //        |
2362   //      CheckCastPP (raw)
2363   //  top   |
2364   //     \  |
2365   //     AddP  ( base == top )
2366   //
2367   Node *base = addp->in(AddPNode::Base);
2368   if (base->uncast()->is_top()) { // The AddP case #3 and #6 and #9.
2369     base = addp->in(AddPNode::Address);
2370     while (base->is_AddP()) {
2371       // Case #6 (unsafe access) may have several chained AddP nodes.
2372       assert(base->in(AddPNode::Base)->uncast()->is_top(), "expected unsafe access address only");
2373       base = base->in(AddPNode::Address);
2374     }
2375     if (base->Opcode() == Op_CheckCastPP &&
2376         base->bottom_type()->isa_rawptr() &&
2377         _igvn->type(base->in(1))->isa_oopptr()) {
2378       base = base->in(1); // Case #9
2379     } else {
2380       Node* uncast_base = base->uncast();
2381       int opcode = uncast_base->Opcode();
2382       assert(opcode == Op_ConP || opcode == Op_ThreadLocal ||
2383              opcode == Op_CastX2P || uncast_base->is_DecodeNarrowPtr() ||
2384              (uncast_base->is_Mem() && (uncast_base->bottom_type()->isa_rawptr() != NULL)) ||
2385              (uncast_base->is_Proj() && uncast_base->in(0)->is_Allocate()) ||
2386              BarrierSet::barrier_set()->barrier_set_c2()->escape_is_barrier_node(uncast_base), "sanity");
2387     }
2388   }
2389   return base;
2390 }
2391 
2392 Node* ConnectionGraph::find_second_addp(Node* addp, Node* n) {
2393   assert(addp->is_AddP() && addp->outcnt() > 0, "Don't process dead nodes");
2394   Node* addp2 = addp->raw_out(0);
2395   if (addp->outcnt() == 1 && addp2->is_AddP() &&
2396       addp2->in(AddPNode::Base) == n &&
2397       addp2->in(AddPNode::Address) == addp) {
2398     assert(addp->in(AddPNode::Base) == n, "expecting the same base");
2399     //
2400     // Find array's offset to push it on worklist first and
2401     // as result process an array's element offset first (pushed second)
2402     // to avoid CastPP for the array's offset.
2403     // Otherwise the inserted CastPP (LocalVar) will point to what
2404     // the AddP (Field) points to. Which would be wrong since
2405     // the algorithm expects the CastPP has the same point as
2406     // as AddP's base CheckCastPP (LocalVar).
2407     //
2408     //    ArrayAllocation
2409     //     |
2410     //    CheckCastPP
2411     //     |
2412     //    memProj (from ArrayAllocation CheckCastPP)
2413     //     |  ||
2414     //     |  ||   Int (element index)
2415     //     |  ||    |   ConI (log(element size))
2416     //     |  ||    |   /
2417     //     |  ||   LShift
2418     //     |  ||  /
2419     //     |  AddP (array's element offset)
2420     //     |  |
2421     //     |  | ConI (array's offset: #12(32-bits) or #24(64-bits))
2422     //     | / /
2423     //     AddP (array's offset)
2424     //      |
2425     //     Load/Store (memory operation on array's element)
2426     //
2427     return addp2;
2428   }
2429   return NULL;
2430 }
2431 
2432 //
2433 // Adjust the type and inputs of an AddP which computes the
2434 // address of a field of an instance
2435 //
2436 bool ConnectionGraph::split_AddP(Node *addp, Node *base) {
2437   PhaseGVN* igvn = _igvn;
2438   const TypeOopPtr *base_t = igvn->type(base)->isa_oopptr();
2439   assert(base_t != NULL && base_t->is_known_instance(), "expecting instance oopptr");
2440   const TypeOopPtr *t = igvn->type(addp)->isa_oopptr();
2441   if (t == NULL) {
2442     // We are computing a raw address for a store captured by an Initialize
2443     // compute an appropriate address type (cases #3 and #5).
2444     assert(igvn->type(addp) == TypeRawPtr::NOTNULL, "must be raw pointer");
2445     assert(addp->in(AddPNode::Address)->is_Proj(), "base of raw address must be result projection from allocation");
2446     intptr_t offs = (int)igvn->find_intptr_t_con(addp->in(AddPNode::Offset), Type::OffsetBot);
2447     assert(offs != Type::OffsetBot, "offset must be a constant");
2448     if (base_t->isa_aryptr() != NULL) {
2449       // In the case of a flattened value type array, each field has its
2450       // own slice so we need to extract the field being accessed from
2451       // the address computation
2452       t = base_t->isa_aryptr()->add_field_offset_and_offset(offs)->is_oopptr();
2453     } else {
2454       t = base_t->add_offset(offs)->is_oopptr();
2455     }
2456   }
2457   int inst_id = base_t->instance_id();
2458   assert(!t->is_known_instance() || t->instance_id() == inst_id,
2459                              "old type must be non-instance or match new type");
2460 
2461   // The type 't' could be subclass of 'base_t'.
2462   // As result t->offset() could be large then base_t's size and it will
2463   // cause the failure in add_offset() with narrow oops since TypeOopPtr()
2464   // constructor verifies correctness of the offset.
2465   //
2466   // It could happened on subclass's branch (from the type profiling
2467   // inlining) which was not eliminated during parsing since the exactness
2468   // of the allocation type was not propagated to the subclass type check.
2469   //
2470   // Or the type 't' could be not related to 'base_t' at all.
2471   // It could happen when CHA type is different from MDO type on a dead path
2472   // (for example, from instanceof check) which is not collapsed during parsing.
2473   //
2474   // Do nothing for such AddP node and don't process its users since
2475   // this code branch will go away.
2476   //
2477   if (!t->is_known_instance() &&
2478       !base_t->klass()->is_subtype_of(t->klass())) {
2479      return false; // bail out
2480   }
2481   const TypePtr* tinst = base_t->add_offset(t->offset());
2482   if (tinst->isa_aryptr() && t->isa_aryptr()) {
2483     // In the case of a flattened value type array, each field has its
2484     // own slice so we need to keep track of the field being accessed.
2485     tinst = tinst->is_aryptr()->with_field_offset(t->is_aryptr()->field_offset().get());
2486   }
2487 
2488   // Do NOT remove the next line: ensure a new alias index is allocated
2489   // for the instance type. Note: C++ will not remove it since the call
2490   // has side effect.
2491   int alias_idx = _compile->get_alias_index(tinst);
2492   igvn->set_type(addp, tinst);
2493   // record the allocation in the node map
2494   set_map(addp, get_map(base->_idx));
2495   // Set addp's Base and Address to 'base'.
2496   Node *abase = addp->in(AddPNode::Base);
2497   Node *adr   = addp->in(AddPNode::Address);
2498   if (adr->is_Proj() && adr->in(0)->is_Allocate() &&
2499       adr->in(0)->_idx == (uint)inst_id) {
2500     // Skip AddP cases #3 and #5.
2501   } else {
2502     assert(!abase->is_top(), "sanity"); // AddP case #3
2503     if (abase != base) {
2504       igvn->hash_delete(addp);
2505       addp->set_req(AddPNode::Base, base);
2506       if (abase == adr) {
2507         addp->set_req(AddPNode::Address, base);
2508       } else {
2509         // AddP case #4 (adr is array's element offset AddP node)
2510 #ifdef ASSERT
2511         const TypeOopPtr *atype = igvn->type(adr)->isa_oopptr();
2512         assert(adr->is_AddP() && atype != NULL &&
2513                atype->instance_id() == inst_id, "array's element offset should be processed first");
2514 #endif
2515       }
2516       igvn->hash_insert(addp);
2517     }
2518   }
2519   // Put on IGVN worklist since at least addp's type was changed above.
2520   record_for_optimizer(addp);
2521   return true;
2522 }
2523 
2524 //
2525 // Create a new version of orig_phi if necessary. Returns either the newly
2526 // created phi or an existing phi.  Sets create_new to indicate whether a new
2527 // phi was created.  Cache the last newly created phi in the node map.
2528 //
2529 PhiNode *ConnectionGraph::create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, bool &new_created) {
2530   Compile *C = _compile;
2531   PhaseGVN* igvn = _igvn;
2532   new_created = false;
2533   int phi_alias_idx = C->get_alias_index(orig_phi->adr_type());
2534   // nothing to do if orig_phi is bottom memory or matches alias_idx
2535   if (phi_alias_idx == alias_idx) {
2536     return orig_phi;
2537   }
2538   // Have we recently created a Phi for this alias index?
2539   PhiNode *result = get_map_phi(orig_phi->_idx);
2540   if (result != NULL && C->get_alias_index(result->adr_type()) == alias_idx) {
2541     return result;
2542   }
2543   // Previous check may fail when the same wide memory Phi was split into Phis
2544   // for different memory slices. Search all Phis for this region.
2545   if (result != NULL) {
2546     Node* region = orig_phi->in(0);
2547     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
2548       Node* phi = region->fast_out(i);
2549       if (phi->is_Phi() &&
2550           C->get_alias_index(phi->as_Phi()->adr_type()) == alias_idx) {
2551         assert(phi->_idx >= nodes_size(), "only new Phi per instance memory slice");
2552         return phi->as_Phi();
2553       }
2554     }
2555   }
2556   if (C->live_nodes() + 2*NodeLimitFudgeFactor > C->max_node_limit()) {
2557     if (C->do_escape_analysis() == true && !C->failing()) {
2558       // Retry compilation without escape analysis.
2559       // If this is the first failure, the sentinel string will "stick"
2560       // to the Compile object, and the C2Compiler will see it and retry.
2561       C->record_failure(C2Compiler::retry_no_escape_analysis());
2562     }
2563     return NULL;
2564   }
2565   orig_phi_worklist.append_if_missing(orig_phi);
2566   const TypePtr *atype = C->get_adr_type(alias_idx);
2567   result = PhiNode::make(orig_phi->in(0), NULL, Type::MEMORY, atype);
2568   C->copy_node_notes_to(result, orig_phi);
2569   igvn->set_type(result, result->bottom_type());
2570   record_for_optimizer(result);
2571   set_map(orig_phi, result);
2572   new_created = true;
2573   return result;
2574 }
2575 
2576 //
2577 // Return a new version of Memory Phi "orig_phi" with the inputs having the
2578 // specified alias index.
2579 //
2580 PhiNode *ConnectionGraph::split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist) {
2581   assert(alias_idx != Compile::AliasIdxBot, "can't split out bottom memory");
2582   Compile *C = _compile;
2583   PhaseGVN* igvn = _igvn;
2584   bool new_phi_created;
2585   PhiNode *result = create_split_phi(orig_phi, alias_idx, orig_phi_worklist, new_phi_created);
2586   if (!new_phi_created) {
2587     return result;
2588   }
2589   GrowableArray<PhiNode *>  phi_list;
2590   GrowableArray<uint>  cur_input;
2591   PhiNode *phi = orig_phi;
2592   uint idx = 1;
2593   bool finished = false;
2594   while(!finished) {
2595     while (idx < phi->req()) {
2596       Node *mem = find_inst_mem(phi->in(idx), alias_idx, orig_phi_worklist);
2597       if (mem != NULL && mem->is_Phi()) {
2598         PhiNode *newphi = create_split_phi(mem->as_Phi(), alias_idx, orig_phi_worklist, new_phi_created);
2599         if (new_phi_created) {
2600           // found an phi for which we created a new split, push current one on worklist and begin
2601           // processing new one
2602           phi_list.push(phi);
2603           cur_input.push(idx);
2604           phi = mem->as_Phi();
2605           result = newphi;
2606           idx = 1;
2607           continue;
2608         } else {
2609           mem = newphi;
2610         }
2611       }
2612       if (C->failing()) {
2613         return NULL;
2614       }
2615       result->set_req(idx++, mem);
2616     }
2617 #ifdef ASSERT
2618     // verify that the new Phi has an input for each input of the original
2619     assert( phi->req() == result->req(), "must have same number of inputs.");
2620     assert( result->in(0) != NULL && result->in(0) == phi->in(0), "regions must match");
2621 #endif
2622     // Check if all new phi's inputs have specified alias index.
2623     // Otherwise use old phi.
2624     for (uint i = 1; i < phi->req(); i++) {
2625       Node* in = result->in(i);
2626       assert((phi->in(i) == NULL) == (in == NULL), "inputs must correspond.");
2627     }
2628     // we have finished processing a Phi, see if there are any more to do
2629     finished = (phi_list.length() == 0 );
2630     if (!finished) {
2631       phi = phi_list.pop();
2632       idx = cur_input.pop();
2633       PhiNode *prev_result = get_map_phi(phi->_idx);
2634       prev_result->set_req(idx++, result);
2635       result = prev_result;
2636     }
2637   }
2638   return result;
2639 }
2640 
2641 //
2642 // The next methods are derived from methods in MemNode.
2643 //
2644 Node* ConnectionGraph::step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop) {
2645   Node *mem = mmem;
2646   // TypeOopPtr::NOTNULL+any is an OOP with unknown offset - generally
2647   // means an array I have not precisely typed yet.  Do not do any
2648   // alias stuff with it any time soon.
2649   if (toop->base() != Type::AnyPtr &&
2650       !(toop->klass() != NULL &&
2651         toop->klass()->is_java_lang_Object() &&
2652         toop->offset() == Type::OffsetBot)) {
2653     mem = mmem->memory_at(alias_idx);
2654     // Update input if it is progress over what we have now
2655   }
2656   return mem;
2657 }
2658 
2659 //
2660 // Move memory users to their memory slices.
2661 //
2662 void ConnectionGraph::move_inst_mem(Node* n, GrowableArray<PhiNode *>  &orig_phis) {
2663   Compile* C = _compile;
2664   PhaseGVN* igvn = _igvn;
2665   const TypePtr* tp = igvn->type(n->in(MemNode::Address))->isa_ptr();
2666   assert(tp != NULL, "ptr type");
2667   int alias_idx = C->get_alias_index(tp);
2668   int general_idx = C->get_general_index(alias_idx);
2669 
2670   // Move users first
2671   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2672     Node* use = n->fast_out(i);
2673     if (use->is_MergeMem()) {
2674       MergeMemNode* mmem = use->as_MergeMem();
2675       assert(n == mmem->memory_at(alias_idx), "should be on instance memory slice");
2676       if (n != mmem->memory_at(general_idx) || alias_idx == general_idx) {
2677         continue; // Nothing to do
2678       }
2679       // Replace previous general reference to mem node.
2680       uint orig_uniq = C->unique();
2681       Node* m = find_inst_mem(n, general_idx, orig_phis);
2682       assert(orig_uniq == C->unique(), "no new nodes");
2683       mmem->set_memory_at(general_idx, m);
2684       --imax;
2685       --i;
2686     } else if (use->is_MemBar()) {
2687       assert(!use->is_Initialize(), "initializing stores should not be moved");
2688       if (use->req() > MemBarNode::Precedent &&
2689           use->in(MemBarNode::Precedent) == n) {
2690         // Don't move related membars.
2691         record_for_optimizer(use);
2692         continue;
2693       }
2694       tp = use->as_MemBar()->adr_type()->isa_ptr();
2695       if ((tp != NULL && C->get_alias_index(tp) == alias_idx) ||
2696           alias_idx == general_idx) {
2697         continue; // Nothing to do
2698       }
2699       // Move to general memory slice.
2700       uint orig_uniq = C->unique();
2701       Node* m = find_inst_mem(n, general_idx, orig_phis);
2702       assert(orig_uniq == C->unique(), "no new nodes");
2703       igvn->hash_delete(use);
2704       imax -= use->replace_edge(n, m);
2705       igvn->hash_insert(use);
2706       record_for_optimizer(use);
2707       --i;
2708 #ifdef ASSERT
2709     } else if (use->is_Mem()) {
2710       if (use->Opcode() == Op_StoreCM && use->in(MemNode::OopStore) == n) {
2711         // Don't move related cardmark.
2712         continue;
2713       }
2714       // Memory nodes should have new memory input.
2715       tp = igvn->type(use->in(MemNode::Address))->isa_ptr();
2716       assert(tp != NULL, "ptr type");
2717       int idx = C->get_alias_index(tp);
2718       assert(get_map(use->_idx) != NULL || idx == alias_idx,
2719              "Following memory nodes should have new memory input or be on the same memory slice");
2720     } else if (use->is_Phi()) {
2721       // Phi nodes should be split and moved already.
2722       tp = use->as_Phi()->adr_type()->isa_ptr();
2723       assert(tp != NULL, "ptr type");
2724       int idx = C->get_alias_index(tp);
2725       assert(idx == alias_idx, "Following Phi nodes should be on the same memory slice");
2726     } else {
2727       use->dump();
2728       assert(false, "should not be here");
2729 #endif
2730     }
2731   }
2732 }
2733 
2734 //
2735 // Search memory chain of "mem" to find a MemNode whose address
2736 // is the specified alias index.
2737 //
2738 Node* ConnectionGraph::find_inst_mem(Node *orig_mem, int alias_idx, GrowableArray<PhiNode *>  &orig_phis) {
2739   if (orig_mem == NULL)
2740     return orig_mem;
2741   Compile* C = _compile;
2742   PhaseGVN* igvn = _igvn;
2743   const TypeOopPtr *toop = C->get_adr_type(alias_idx)->isa_oopptr();
2744   bool is_instance = (toop != NULL) && toop->is_known_instance();
2745   Node *start_mem = C->start()->proj_out_or_null(TypeFunc::Memory);
2746   Node *prev = NULL;
2747   Node *result = orig_mem;
2748   while (prev != result) {
2749     prev = result;
2750     if (result == start_mem)
2751       break;  // hit one of our sentinels
2752     if (result->is_Mem()) {
2753       const Type *at = igvn->type(result->in(MemNode::Address));
2754       if (at == Type::TOP)
2755         break; // Dead
2756       assert (at->isa_ptr() != NULL, "pointer type required.");
2757       int idx = C->get_alias_index(at->is_ptr());
2758       if (idx == alias_idx)
2759         break; // Found
2760       if (!is_instance && (at->isa_oopptr() == NULL ||
2761                            !at->is_oopptr()->is_known_instance())) {
2762         break; // Do not skip store to general memory slice.
2763       }
2764       result = result->in(MemNode::Memory);
2765     }
2766     if (!is_instance)
2767       continue;  // don't search further for non-instance types
2768     // skip over a call which does not affect this memory slice
2769     if (result->is_Proj() && result->as_Proj()->_con == TypeFunc::Memory) {
2770       Node *proj_in = result->in(0);
2771       if (proj_in->is_Allocate() && proj_in->_idx == (uint)toop->instance_id()) {
2772         break;  // hit one of our sentinels
2773       } else if (proj_in->is_Call()) {
2774         // ArrayCopy node processed here as well
2775         CallNode *call = proj_in->as_Call();
2776         if (!call->may_modify(toop, igvn)) {
2777           result = call->in(TypeFunc::Memory);
2778         }
2779       } else if (proj_in->is_Initialize()) {
2780         AllocateNode* alloc = proj_in->as_Initialize()->allocation();
2781         // Stop if this is the initialization for the object instance which
2782         // which contains this memory slice, otherwise skip over it.
2783         if (alloc == NULL || alloc->_idx != (uint)toop->instance_id()) {
2784           result = proj_in->in(TypeFunc::Memory);
2785         }
2786       } else if (proj_in->is_MemBar()) {
2787         if (proj_in->in(TypeFunc::Memory)->is_MergeMem() &&
2788             proj_in->in(TypeFunc::Memory)->as_MergeMem()->in(Compile::AliasIdxRaw)->is_Proj() &&
2789             proj_in->in(TypeFunc::Memory)->as_MergeMem()->in(Compile::AliasIdxRaw)->in(0)->is_ArrayCopy()) {
2790           // clone
2791           ArrayCopyNode* ac = proj_in->in(TypeFunc::Memory)->as_MergeMem()->in(Compile::AliasIdxRaw)->in(0)->as_ArrayCopy();
2792           if (ac->may_modify(toop, igvn)) {
2793             break;
2794           }
2795         }
2796         result = proj_in->in(TypeFunc::Memory);
2797       }
2798     } else if (result->is_MergeMem()) {
2799       MergeMemNode *mmem = result->as_MergeMem();
2800       result = step_through_mergemem(mmem, alias_idx, toop);
2801       if (result == mmem->base_memory()) {
2802         // Didn't find instance memory, search through general slice recursively.
2803         result = mmem->memory_at(C->get_general_index(alias_idx));
2804         result = find_inst_mem(result, alias_idx, orig_phis);
2805         if (C->failing()) {
2806           return NULL;
2807         }
2808         mmem->set_memory_at(alias_idx, result);
2809       }
2810     } else if (result->is_Phi() &&
2811                C->get_alias_index(result->as_Phi()->adr_type()) != alias_idx) {
2812       Node *un = result->as_Phi()->unique_input(igvn);
2813       if (un != NULL) {
2814         orig_phis.append_if_missing(result->as_Phi());
2815         result = un;
2816       } else {
2817         break;
2818       }
2819     } else if (result->is_ClearArray()) {
2820       if (!ClearArrayNode::step_through(&result, (uint)toop->instance_id(), igvn)) {
2821         // Can not bypass initialization of the instance
2822         // we are looking for.
2823         break;
2824       }
2825       // Otherwise skip it (the call updated 'result' value).
2826     } else if (result->Opcode() == Op_SCMemProj) {
2827       Node* mem = result->in(0);
2828       Node* adr = NULL;
2829       if (mem->is_LoadStore()) {
2830         adr = mem->in(MemNode::Address);
2831       } else {
2832         assert(mem->Opcode() == Op_EncodeISOArray ||
2833                mem->Opcode() == Op_StrCompressedCopy, "sanity");
2834         adr = mem->in(3); // Memory edge corresponds to destination array
2835       }
2836       const Type *at = igvn->type(adr);
2837       if (at != Type::TOP) {
2838         assert(at->isa_ptr() != NULL, "pointer type required.");
2839         int idx = C->get_alias_index(at->is_ptr());
2840         if (idx == alias_idx) {
2841           // Assert in debug mode
2842           assert(false, "Object is not scalar replaceable if a LoadStore node accesses its field");
2843           break; // In product mode return SCMemProj node
2844         }
2845       }
2846       result = mem->in(MemNode::Memory);
2847     } else if (result->Opcode() == Op_StrInflatedCopy) {
2848       Node* adr = result->in(3); // Memory edge corresponds to destination array
2849       const Type *at = igvn->type(adr);
2850       if (at != Type::TOP) {
2851         assert(at->isa_ptr() != NULL, "pointer type required.");
2852         int idx = C->get_alias_index(at->is_ptr());
2853         if (idx == alias_idx) {
2854           // Assert in debug mode
2855           assert(false, "Object is not scalar replaceable if a StrInflatedCopy node accesses its field");
2856           break; // In product mode return SCMemProj node
2857         }
2858       }
2859       result = result->in(MemNode::Memory);
2860     }
2861   }
2862   if (result->is_Phi()) {
2863     PhiNode *mphi = result->as_Phi();
2864     assert(mphi->bottom_type() == Type::MEMORY, "memory phi required");
2865     const TypePtr *t = mphi->adr_type();
2866     if (!is_instance) {
2867       // Push all non-instance Phis on the orig_phis worklist to update inputs
2868       // during Phase 4 if needed.
2869       orig_phis.append_if_missing(mphi);
2870     } else if (C->get_alias_index(t) != alias_idx) {
2871       // Create a new Phi with the specified alias index type.
2872       result = split_memory_phi(mphi, alias_idx, orig_phis);
2873     }
2874   }
2875   // the result is either MemNode, PhiNode, InitializeNode.
2876   return result;
2877 }
2878 
2879 //
2880 //  Convert the types of unescaped object to instance types where possible,
2881 //  propagate the new type information through the graph, and update memory
2882 //  edges and MergeMem inputs to reflect the new type.
2883 //
2884 //  We start with allocations (and calls which may be allocations)  on alloc_worklist.
2885 //  The processing is done in 4 phases:
2886 //
2887 //  Phase 1:  Process possible allocations from alloc_worklist.  Create instance
2888 //            types for the CheckCastPP for allocations where possible.
2889 //            Propagate the new types through users as follows:
2890 //               casts and Phi:  push users on alloc_worklist
2891 //               AddP:  cast Base and Address inputs to the instance type
2892 //                      push any AddP users on alloc_worklist and push any memnode
2893 //                      users onto memnode_worklist.
2894 //  Phase 2:  Process MemNode's from memnode_worklist. compute new address type and
2895 //            search the Memory chain for a store with the appropriate type
2896 //            address type.  If a Phi is found, create a new version with
2897 //            the appropriate memory slices from each of the Phi inputs.
2898 //            For stores, process the users as follows:
2899 //               MemNode:  push on memnode_worklist
2900 //               MergeMem: push on mergemem_worklist
2901 //  Phase 3:  Process MergeMem nodes from mergemem_worklist.  Walk each memory slice
2902 //            moving the first node encountered of each  instance type to the
2903 //            the input corresponding to its alias index.
2904 //            appropriate memory slice.
2905 //  Phase 4:  Update the inputs of non-instance memory Phis and the Memory input of memnodes.
2906 //
2907 // In the following example, the CheckCastPP nodes are the cast of allocation
2908 // results and the allocation of node 29 is unescaped and eligible to be an
2909 // instance type.
2910 //
2911 // We start with:
2912 //
2913 //     7 Parm #memory
2914 //    10  ConI  "12"
2915 //    19  CheckCastPP   "Foo"
2916 //    20  AddP  _ 19 19 10  Foo+12  alias_index=4
2917 //    29  CheckCastPP   "Foo"
2918 //    30  AddP  _ 29 29 10  Foo+12  alias_index=4
2919 //
2920 //    40  StoreP  25   7  20   ... alias_index=4
2921 //    50  StoreP  35  40  30   ... alias_index=4
2922 //    60  StoreP  45  50  20   ... alias_index=4
2923 //    70  LoadP    _  60  30   ... alias_index=4
2924 //    80  Phi     75  50  60   Memory alias_index=4
2925 //    90  LoadP    _  80  30   ... alias_index=4
2926 //   100  LoadP    _  80  20   ... alias_index=4
2927 //
2928 //
2929 // Phase 1 creates an instance type for node 29 assigning it an instance id of 24
2930 // and creating a new alias index for node 30.  This gives:
2931 //
2932 //     7 Parm #memory
2933 //    10  ConI  "12"
2934 //    19  CheckCastPP   "Foo"
2935 //    20  AddP  _ 19 19 10  Foo+12  alias_index=4
2936 //    29  CheckCastPP   "Foo"  iid=24
2937 //    30  AddP  _ 29 29 10  Foo+12  alias_index=6  iid=24
2938 //
2939 //    40  StoreP  25   7  20   ... alias_index=4
2940 //    50  StoreP  35  40  30   ... alias_index=6
2941 //    60  StoreP  45  50  20   ... alias_index=4
2942 //    70  LoadP    _  60  30   ... alias_index=6
2943 //    80  Phi     75  50  60   Memory alias_index=4
2944 //    90  LoadP    _  80  30   ... alias_index=6
2945 //   100  LoadP    _  80  20   ... alias_index=4
2946 //
2947 // In phase 2, new memory inputs are computed for the loads and stores,
2948 // And a new version of the phi is created.  In phase 4, the inputs to
2949 // node 80 are updated and then the memory nodes are updated with the
2950 // values computed in phase 2.  This results in:
2951 //
2952 //     7 Parm #memory
2953 //    10  ConI  "12"
2954 //    19  CheckCastPP   "Foo"
2955 //    20  AddP  _ 19 19 10  Foo+12  alias_index=4
2956 //    29  CheckCastPP   "Foo"  iid=24
2957 //    30  AddP  _ 29 29 10  Foo+12  alias_index=6  iid=24
2958 //
2959 //    40  StoreP  25  7   20   ... alias_index=4
2960 //    50  StoreP  35  7   30   ... alias_index=6
2961 //    60  StoreP  45  40  20   ... alias_index=4
2962 //    70  LoadP    _  50  30   ... alias_index=6
2963 //    80  Phi     75  40  60   Memory alias_index=4
2964 //   120  Phi     75  50  50   Memory alias_index=6
2965 //    90  LoadP    _ 120  30   ... alias_index=6
2966 //   100  LoadP    _  80  20   ... alias_index=4
2967 //
2968 void ConnectionGraph::split_unique_types(GrowableArray<Node *>  &alloc_worklist, GrowableArray<ArrayCopyNode*> &arraycopy_worklist) {
2969   GrowableArray<Node *>  memnode_worklist;
2970   GrowableArray<PhiNode *>  orig_phis;
2971   PhaseIterGVN  *igvn = _igvn;
2972   uint new_index_start = (uint) _compile->num_alias_types();
2973   Arena* arena = Thread::current()->resource_area();
2974   VectorSet visited(arena);
2975   ideal_nodes.clear(); // Reset for use with set_map/get_map.
2976   uint unique_old = _compile->unique();
2977 
2978   //  Phase 1:  Process possible allocations from alloc_worklist.
2979   //  Create instance types for the CheckCastPP for allocations where possible.
2980   //
2981   // (Note: don't forget to change the order of the second AddP node on
2982   //  the alloc_worklist if the order of the worklist processing is changed,
2983   //  see the comment in find_second_addp().)
2984   //
2985   while (alloc_worklist.length() != 0) {
2986     Node *n = alloc_worklist.pop();
2987     uint ni = n->_idx;
2988     if (n->is_Call()) {
2989       CallNode *alloc = n->as_Call();
2990       // copy escape information to call node
2991       PointsToNode* ptn = ptnode_adr(alloc->_idx);
2992       PointsToNode::EscapeState es = ptn->escape_state();
2993       // We have an allocation or call which returns a Java object,
2994       // see if it is unescaped.
2995       if (es != PointsToNode::NoEscape || !ptn->scalar_replaceable())
2996         continue;
2997       // Find CheckCastPP for the allocate or for the return value of a call
2998       n = alloc->result_cast();
2999       if (n == NULL) {            // No uses except Initialize node
3000         if (alloc->is_Allocate()) {
3001           // Set the scalar_replaceable flag for allocation
3002           // so it could be eliminated if it has no uses.
3003           alloc->as_Allocate()->_is_scalar_replaceable = true;
3004         }
3005         if (alloc->is_CallStaticJava()) {
3006           // Set the scalar_replaceable flag for boxing method
3007           // so it could be eliminated if it has no uses.
3008           alloc->as_CallStaticJava()->_is_scalar_replaceable = true;
3009         }
3010         continue;
3011       }
3012       if (!n->is_CheckCastPP()) { // not unique CheckCastPP.
3013         assert(!alloc->is_Allocate(), "allocation should have unique type");
3014         continue;
3015       }
3016 
3017       // The inline code for Object.clone() casts the allocation result to
3018       // java.lang.Object and then to the actual type of the allocated
3019       // object. Detect this case and use the second cast.
3020       // Also detect j.l.reflect.Array.newInstance(jobject, jint) case when
3021       // the allocation result is cast to java.lang.Object and then
3022       // to the actual Array type.
3023       if (alloc->is_Allocate() && n->as_Type()->type() == TypeInstPtr::NOTNULL
3024           && (alloc->is_AllocateArray() ||
3025               igvn->type(alloc->in(AllocateNode::KlassNode)) != TypeKlassPtr::OBJECT)) {
3026         Node *cast2 = NULL;
3027         for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3028           Node *use = n->fast_out(i);
3029           if (use->is_CheckCastPP()) {
3030             cast2 = use;
3031             break;
3032           }
3033         }
3034         if (cast2 != NULL) {
3035           n = cast2;
3036         } else {
3037           // Non-scalar replaceable if the allocation type is unknown statically
3038           // (reflection allocation), the object can't be restored during
3039           // deoptimization without precise type.
3040           continue;
3041         }
3042       }
3043 
3044       const TypeOopPtr *t = igvn->type(n)->isa_oopptr();
3045       if (t == NULL)
3046         continue;  // not a TypeOopPtr
3047       if (!t->klass_is_exact())
3048         continue; // not an unique type
3049 
3050       if (alloc->is_Allocate()) {
3051         // Set the scalar_replaceable flag for allocation
3052         // so it could be eliminated.
3053         alloc->as_Allocate()->_is_scalar_replaceable = true;
3054       }
3055       if (alloc->is_CallStaticJava()) {
3056         // Set the scalar_replaceable flag for boxing method
3057         // so it could be eliminated.
3058         alloc->as_CallStaticJava()->_is_scalar_replaceable = true;
3059       }
3060       set_escape_state(ptnode_adr(n->_idx), es); // CheckCastPP escape state
3061       // in order for an object to be scalar-replaceable, it must be:
3062       //   - a direct allocation (not a call returning an object)
3063       //   - non-escaping
3064       //   - eligible to be a unique type
3065       //   - not determined to be ineligible by escape analysis
3066       set_map(alloc, n);
3067       set_map(n, alloc);
3068       const TypeOopPtr* tinst = t->cast_to_instance_id(ni);
3069       igvn->hash_delete(n);
3070       igvn->set_type(n,  tinst);
3071       n->raise_bottom_type(tinst);
3072       igvn->hash_insert(n);
3073       record_for_optimizer(n);
3074       // Allocate an alias index for the header fields. Accesses to
3075       // the header emitted during macro expansion wouldn't have
3076       // correct memory state otherwise.
3077       _compile->get_alias_index(tinst->add_offset(oopDesc::mark_offset_in_bytes()));
3078       _compile->get_alias_index(tinst->add_offset(oopDesc::klass_offset_in_bytes()));
3079       if (alloc->is_Allocate() && (t->isa_instptr() || t->isa_aryptr())) {
3080 
3081         // First, put on the worklist all Field edges from Connection Graph
3082         // which is more accurate than putting immediate users from Ideal Graph.
3083         for (EdgeIterator e(ptn); e.has_next(); e.next()) {
3084           PointsToNode* tgt = e.get();
3085           if (tgt->is_Arraycopy()) {
3086             continue;
3087           }
3088           Node* use = tgt->ideal_node();
3089           assert(tgt->is_Field() && use->is_AddP(),
3090                  "only AddP nodes are Field edges in CG");
3091           if (use->outcnt() > 0) { // Don't process dead nodes
3092             Node* addp2 = find_second_addp(use, use->in(AddPNode::Base));
3093             if (addp2 != NULL) {
3094               assert(alloc->is_AllocateArray(),"array allocation was expected");
3095               alloc_worklist.append_if_missing(addp2);
3096             }
3097             alloc_worklist.append_if_missing(use);
3098           }
3099         }
3100 
3101         // An allocation may have an Initialize which has raw stores. Scan
3102         // the users of the raw allocation result and push AddP users
3103         // on alloc_worklist.
3104         Node *raw_result = alloc->proj_out_or_null(TypeFunc::Parms);
3105         assert (raw_result != NULL, "must have an allocation result");
3106         for (DUIterator_Fast imax, i = raw_result->fast_outs(imax); i < imax; i++) {
3107           Node *use = raw_result->fast_out(i);
3108           if (use->is_AddP() && use->outcnt() > 0) { // Don't process dead nodes
3109             Node* addp2 = find_second_addp(use, raw_result);
3110             if (addp2 != NULL) {
3111               assert(alloc->is_AllocateArray(),"array allocation was expected");
3112               alloc_worklist.append_if_missing(addp2);
3113             }
3114             alloc_worklist.append_if_missing(use);
3115           } else if (use->is_MemBar()) {
3116             memnode_worklist.append_if_missing(use);
3117           }
3118         }
3119       }
3120     } else if (n->is_AddP()) {
3121       JavaObjectNode* jobj = unique_java_object(get_addp_base(n));
3122       if (jobj == NULL || jobj == phantom_obj) {
3123 #ifdef ASSERT
3124         ptnode_adr(get_addp_base(n)->_idx)->dump();
3125         ptnode_adr(n->_idx)->dump();
3126         assert(jobj != NULL && jobj != phantom_obj, "escaped allocation");
3127 #endif
3128         _compile->record_failure(C2Compiler::retry_no_escape_analysis());
3129         return;
3130       }
3131       Node *base = get_map(jobj->idx());  // CheckCastPP node
3132       if (!split_AddP(n, base)) continue; // wrong type from dead path
3133     } else if (n->is_Phi() ||
3134                n->is_CheckCastPP() ||
3135                n->is_EncodeP() ||
3136                n->is_DecodeN() ||
3137                BarrierSet::barrier_set()->barrier_set_c2()->escape_is_barrier_node(n) ||
3138                (n->is_ConstraintCast() && n->Opcode() == Op_CastPP)) {
3139       if (visited.test_set(n->_idx)) {
3140         assert(n->is_Phi(), "loops only through Phi's");
3141         continue;  // already processed
3142       }
3143       JavaObjectNode* jobj = unique_java_object(n);
3144       if (jobj == NULL || jobj == phantom_obj) {
3145 #ifdef ASSERT
3146         ptnode_adr(n->_idx)->dump();
3147         assert(jobj != NULL && jobj != phantom_obj, "escaped allocation");
3148 #endif
3149         _compile->record_failure(C2Compiler::retry_no_escape_analysis());
3150         return;
3151       } else {
3152         Node *val = get_map(jobj->idx());   // CheckCastPP node
3153         TypeNode *tn = n->as_Type();
3154         const TypeOopPtr* tinst = igvn->type(val)->isa_oopptr();
3155         assert(tinst != NULL && tinst->is_known_instance() &&
3156                tinst->instance_id() == jobj->idx() , "instance type expected.");
3157 
3158         const Type *tn_type = igvn->type(tn);
3159         const TypeOopPtr *tn_t;
3160         if (tn_type->isa_narrowoop()) {
3161           tn_t = tn_type->make_ptr()->isa_oopptr();
3162         } else {
3163           tn_t = tn_type->isa_oopptr();
3164         }
3165         if (tn_t != NULL && tinst->klass()->is_subtype_of(tn_t->klass())) {
3166           if (tn_type->isa_narrowoop()) {
3167             tn_type = tinst->make_narrowoop();
3168           } else {
3169             tn_type = tinst;
3170           }
3171           igvn->hash_delete(tn);
3172           igvn->set_type(tn, tn_type);
3173           tn->set_type(tn_type);
3174           igvn->hash_insert(tn);
3175           record_for_optimizer(n);
3176         } else {
3177           assert(tn_type == TypePtr::NULL_PTR ||
3178                  tn_t != NULL && !tinst->klass()->is_subtype_of(tn_t->klass()),
3179                  "unexpected type");
3180           continue; // Skip dead path with different type
3181         }
3182       }
3183     } else {
3184       debug_only(n->dump();)
3185       assert(false, "EA: unexpected node");
3186       continue;
3187     }
3188     // push allocation's users on appropriate worklist
3189     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3190       Node *use = n->fast_out(i);
3191       if (use->is_Mem() && use->in(MemNode::Address) == n) {
3192         // Load/store to instance's field
3193         memnode_worklist.append_if_missing(use);
3194       } else if (use->is_MemBar()) {
3195         if (use->in(TypeFunc::Memory) == n) { // Ignore precedent edge
3196           memnode_worklist.append_if_missing(use);
3197         }
3198       } else if (use->is_AddP() && use->outcnt() > 0) { // No dead nodes
3199         Node* addp2 = find_second_addp(use, n);
3200         if (addp2 != NULL) {
3201           alloc_worklist.append_if_missing(addp2);
3202         }
3203         alloc_worklist.append_if_missing(use);
3204       } else if (use->is_Phi() ||
3205                  use->is_CheckCastPP() ||
3206                  use->is_EncodeNarrowPtr() ||
3207                  use->is_DecodeNarrowPtr() ||
3208                  BarrierSet::barrier_set()->barrier_set_c2()->escape_is_barrier_node(use) ||
3209                  (use->is_ConstraintCast() && use->Opcode() == Op_CastPP)) {
3210         alloc_worklist.append_if_missing(use);
3211 #ifdef ASSERT
3212       } else if (use->is_Mem()) {
3213         assert(use->in(MemNode::Address) != n, "EA: missing allocation reference path");
3214       } else if (use->is_MergeMem()) {
3215         assert(_mergemem_worklist.contains(use->as_MergeMem()), "EA: missing MergeMem node in the worklist");
3216       } else if (use->is_SafePoint()) {
3217         // Look for MergeMem nodes for calls which reference unique allocation
3218         // (through CheckCastPP nodes) even for debug info.
3219         Node* m = use->in(TypeFunc::Memory);
3220         if (m->is_MergeMem()) {
3221           assert(_mergemem_worklist.contains(m->as_MergeMem()), "EA: missing MergeMem node in the worklist");
3222         }
3223       } else if (use->Opcode() == Op_EncodeISOArray) {
3224         if (use->in(MemNode::Memory) == n || use->in(3) == n) {
3225           // EncodeISOArray overwrites destination array
3226           memnode_worklist.append_if_missing(use);
3227         }
3228       } else if (use->Opcode() == Op_Return) {
3229         assert(_compile->tf()->returns_value_type_as_fields(), "must return a value type");
3230         // Get ValueKlass by removing the tag bit from the metadata pointer
3231         Node* klass = use->in(TypeFunc::Parms);
3232         intptr_t ptr = igvn->type(klass)->isa_rawptr()->get_con();
3233         clear_nth_bit(ptr, 0);
3234         assert(Metaspace::contains((void*)ptr), "should be klass");
3235         assert(((ValueKlass*)ptr)->contains_oops(), "returned value type must contain a reference field");
3236       } else {
3237         uint op = use->Opcode();
3238         if ((op == Op_StrCompressedCopy || op == Op_StrInflatedCopy) &&
3239             (use->in(MemNode::Memory) == n)) {
3240           // They overwrite memory edge corresponding to destination array,
3241           memnode_worklist.append_if_missing(use);
3242         } else if (!(op == Op_CmpP || op == Op_Conv2B ||
3243               op == Op_CastP2X || op == Op_StoreCM ||
3244               op == Op_FastLock || op == Op_AryEq || op == Op_StrComp || op == Op_HasNegatives ||
3245               op == Op_StrCompressedCopy || op == Op_StrInflatedCopy ||
3246               op == Op_StrEquals || op == Op_StrIndexOf || op == Op_StrIndexOfChar ||
3247               BarrierSet::barrier_set()->barrier_set_c2()->is_gc_barrier_node(use) ||
3248               op == Op_ValueType)) {
3249           n->dump();
3250           use->dump();
3251           assert(false, "EA: missing allocation reference path");
3252         }
3253 #endif
3254       }
3255     }
3256 
3257   }
3258 
3259   // Go over all ArrayCopy nodes and if one of the inputs has a unique
3260   // type, record it in the ArrayCopy node so we know what memory this
3261   // node uses/modified.
3262   for (int next = 0; next < arraycopy_worklist.length(); next++) {
3263     ArrayCopyNode* ac = arraycopy_worklist.at(next);
3264     Node* dest = ac->in(ArrayCopyNode::Dest);
3265     if (dest->is_AddP()) {
3266       dest = get_addp_base(dest);
3267     }
3268     JavaObjectNode* jobj = unique_java_object(dest);
3269     if (jobj != NULL) {
3270       Node *base = get_map(jobj->idx());
3271       if (base != NULL) {
3272         const TypeOopPtr *base_t = _igvn->type(base)->isa_oopptr();
3273         ac->_dest_type = base_t;
3274       }
3275     }
3276     Node* src = ac->in(ArrayCopyNode::Src);
3277     if (src->is_AddP()) {
3278       src = get_addp_base(src);
3279     }
3280     jobj = unique_java_object(src);
3281     if (jobj != NULL) {
3282       Node* base = get_map(jobj->idx());
3283       if (base != NULL) {
3284         const TypeOopPtr *base_t = _igvn->type(base)->isa_oopptr();
3285         ac->_src_type = base_t;
3286       }
3287     }
3288   }
3289 
3290   // New alias types were created in split_AddP().
3291   uint new_index_end = (uint) _compile->num_alias_types();
3292   assert(unique_old == _compile->unique(), "there should be no new ideal nodes after Phase 1");
3293 
3294   //  Phase 2:  Process MemNode's from memnode_worklist. compute new address type and
3295   //            compute new values for Memory inputs  (the Memory inputs are not
3296   //            actually updated until phase 4.)
3297   if (memnode_worklist.length() == 0)
3298     return;  // nothing to do
3299   while (memnode_worklist.length() != 0) {
3300     Node *n = memnode_worklist.pop();
3301     if (visited.test_set(n->_idx))
3302       continue;
3303     if (n->is_Phi() || n->is_ClearArray()) {
3304       // we don't need to do anything, but the users must be pushed
3305     } else if (n->is_MemBar()) { // Initialize, MemBar nodes
3306       // we don't need to do anything, but the users must be pushed
3307       n = n->as_MemBar()->proj_out_or_null(TypeFunc::Memory);
3308       if (n == NULL)
3309         continue;
3310     } else if (n->Opcode() == Op_StrCompressedCopy ||
3311                n->Opcode() == Op_EncodeISOArray) {
3312       // get the memory projection
3313       n = n->find_out_with(Op_SCMemProj);
3314       assert(n != NULL && n->Opcode() == Op_SCMemProj, "memory projection required");
3315     } else if (n->is_CallLeaf() && n->as_CallLeaf()->_name != NULL &&
3316                strcmp(n->as_CallLeaf()->_name, "store_unknown_value") == 0) {
3317       n = n->as_CallLeaf()->proj_out(TypeFunc::Memory);
3318     } else {
3319       assert(n->is_Mem(), "memory node required.");
3320       Node *addr = n->in(MemNode::Address);
3321       const Type *addr_t = igvn->type(addr);
3322       if (addr_t == Type::TOP)
3323         continue;
3324       assert (addr_t->isa_ptr() != NULL, "pointer type required.");
3325       int alias_idx = _compile->get_alias_index(addr_t->is_ptr());
3326       assert ((uint)alias_idx < new_index_end, "wrong alias index");
3327       Node *mem = find_inst_mem(n->in(MemNode::Memory), alias_idx, orig_phis);
3328       if (_compile->failing()) {
3329         return;
3330       }
3331       if (mem != n->in(MemNode::Memory)) {
3332         // We delay the memory edge update since we need old one in
3333         // MergeMem code below when instances memory slices are separated.
3334         set_map(n, mem);
3335       }
3336       if (n->is_Load()) {
3337         continue;  // don't push users
3338       } else if (n->is_LoadStore()) {
3339         // get the memory projection
3340         n = n->find_out_with(Op_SCMemProj);
3341         assert(n != NULL && n->Opcode() == Op_SCMemProj, "memory projection required");
3342       }
3343     }
3344     // push user on appropriate worklist
3345     for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3346       Node *use = n->fast_out(i);
3347       if (use->is_Phi() || use->is_ClearArray()) {
3348         memnode_worklist.append_if_missing(use);
3349       } else if (use->is_Mem() && use->in(MemNode::Memory) == n) {
3350         if (use->Opcode() == Op_StoreCM) // Ignore cardmark stores
3351           continue;
3352         memnode_worklist.append_if_missing(use);
3353       } else if (use->is_MemBar()) {
3354         if (use->in(TypeFunc::Memory) == n) { // Ignore precedent edge
3355           memnode_worklist.append_if_missing(use);
3356         }
3357 #ifdef ASSERT
3358       } else if (use->is_Mem()) {
3359         assert(use->in(MemNode::Memory) != n, "EA: missing memory path");
3360       } else if (use->is_MergeMem()) {
3361         assert(_mergemem_worklist.contains(use->as_MergeMem()), "EA: missing MergeMem node in the worklist");
3362       } else if (use->Opcode() == Op_EncodeISOArray) {
3363         if (use->in(MemNode::Memory) == n || use->in(3) == n) {
3364           // EncodeISOArray overwrites destination array
3365           memnode_worklist.append_if_missing(use);
3366         }
3367       } else if (use->is_CallLeaf() && use->as_CallLeaf()->_name != NULL &&
3368                  strcmp(use->as_CallLeaf()->_name, "store_unknown_value") == 0) {
3369         // store_unknown_value overwrites destination array
3370         memnode_worklist.append_if_missing(use);
3371       } else {
3372         uint op = use->Opcode();
3373         if ((use->in(MemNode::Memory) == n) &&
3374             (op == Op_StrCompressedCopy || op == Op_StrInflatedCopy)) {
3375           // They overwrite memory edge corresponding to destination array,
3376           memnode_worklist.append_if_missing(use);
3377         } else if (!(BarrierSet::barrier_set()->barrier_set_c2()->is_gc_barrier_node(use) ||
3378               op == Op_AryEq || op == Op_StrComp || op == Op_HasNegatives ||
3379               op == Op_StrCompressedCopy || op == Op_StrInflatedCopy ||
3380               op == Op_StrEquals || op == Op_StrIndexOf || op == Op_StrIndexOfChar)) {
3381           n->dump();
3382           use->dump();
3383           assert(false, "EA: missing memory path");
3384         }
3385 #endif
3386       }
3387     }
3388   }
3389 
3390   //  Phase 3:  Process MergeMem nodes from mergemem_worklist.
3391   //            Walk each memory slice moving the first node encountered of each
3392   //            instance type to the input corresponding to its alias index.
3393   uint length = _mergemem_worklist.length();
3394   for( uint next = 0; next < length; ++next ) {
3395     MergeMemNode* nmm = _mergemem_worklist.at(next);
3396     assert(!visited.test_set(nmm->_idx), "should not be visited before");
3397     // Note: we don't want to use MergeMemStream here because we only want to
3398     // scan inputs which exist at the start, not ones we add during processing.
3399     // Note 2: MergeMem may already contains instance memory slices added
3400     // during find_inst_mem() call when memory nodes were processed above.
3401     igvn->hash_delete(nmm);
3402     uint nslices = MIN2(nmm->req(), new_index_start);
3403     for (uint i = Compile::AliasIdxRaw+1; i < nslices; i++) {
3404       Node* mem = nmm->in(i);
3405       Node* cur = NULL;
3406       if (mem == NULL || mem->is_top())
3407         continue;
3408       // First, update mergemem by moving memory nodes to corresponding slices
3409       // if their type became more precise since this mergemem was created.
3410       while (mem->is_Mem()) {
3411         const Type *at = igvn->type(mem->in(MemNode::Address));
3412         if (at != Type::TOP) {
3413           assert (at->isa_ptr() != NULL, "pointer type required.");
3414           uint idx = (uint)_compile->get_alias_index(at->is_ptr());
3415           if (idx == i) {
3416             if (cur == NULL)
3417               cur = mem;
3418           } else {
3419             if (idx >= nmm->req() || nmm->is_empty_memory(nmm->in(idx))) {
3420               nmm->set_memory_at(idx, mem);
3421             }
3422           }
3423         }
3424         mem = mem->in(MemNode::Memory);
3425       }
3426       nmm->set_memory_at(i, (cur != NULL) ? cur : mem);
3427       // Find any instance of the current type if we haven't encountered
3428       // already a memory slice of the instance along the memory chain.
3429       for (uint ni = new_index_start; ni < new_index_end; ni++) {
3430         if((uint)_compile->get_general_index(ni) == i) {
3431           Node *m = (ni >= nmm->req()) ? nmm->empty_memory() : nmm->in(ni);
3432           if (nmm->is_empty_memory(m)) {
3433             Node* result = find_inst_mem(mem, ni, orig_phis);
3434             if (_compile->failing()) {
3435               return;
3436             }
3437             nmm->set_memory_at(ni, result);
3438           }
3439         }
3440       }
3441     }
3442     // Find the rest of instances values
3443     for (uint ni = new_index_start; ni < new_index_end; ni++) {
3444       const TypeOopPtr *tinst = _compile->get_adr_type(ni)->isa_oopptr();
3445       Node* result = step_through_mergemem(nmm, ni, tinst);
3446       if (result == nmm->base_memory()) {
3447         // Didn't find instance memory, search through general slice recursively.
3448         result = nmm->memory_at(_compile->get_general_index(ni));
3449         result = find_inst_mem(result, ni, orig_phis);
3450         if (_compile->failing()) {
3451           return;
3452         }
3453         nmm->set_memory_at(ni, result);
3454       }
3455     }
3456     igvn->hash_insert(nmm);
3457     record_for_optimizer(nmm);
3458   }
3459 
3460   //  Phase 4:  Update the inputs of non-instance memory Phis and
3461   //            the Memory input of memnodes
3462   // First update the inputs of any non-instance Phi's from
3463   // which we split out an instance Phi.  Note we don't have
3464   // to recursively process Phi's encountered on the input memory
3465   // chains as is done in split_memory_phi() since they will
3466   // also be processed here.
3467   for (int j = 0; j < orig_phis.length(); j++) {
3468     PhiNode *phi = orig_phis.at(j);
3469     int alias_idx = _compile->get_alias_index(phi->adr_type());
3470     igvn->hash_delete(phi);
3471     for (uint i = 1; i < phi->req(); i++) {
3472       Node *mem = phi->in(i);
3473       Node *new_mem = find_inst_mem(mem, alias_idx, orig_phis);
3474       if (_compile->failing()) {
3475         return;
3476       }
3477       if (mem != new_mem) {
3478         phi->set_req(i, new_mem);
3479       }
3480     }
3481     igvn->hash_insert(phi);
3482     record_for_optimizer(phi);
3483   }
3484 
3485   // Update the memory inputs of MemNodes with the value we computed
3486   // in Phase 2 and move stores memory users to corresponding memory slices.
3487   // Disable memory split verification code until the fix for 6984348.
3488   // Currently it produces false negative results since it does not cover all cases.
3489 #if 0 // ifdef ASSERT
3490   visited.Reset();
3491   Node_Stack old_mems(arena, _compile->unique() >> 2);
3492 #endif
3493   for (uint i = 0; i < ideal_nodes.size(); i++) {
3494     Node*    n = ideal_nodes.at(i);
3495     Node* nmem = get_map(n->_idx);
3496     assert(nmem != NULL, "sanity");
3497     if (n->is_Mem()) {
3498 #if 0 // ifdef ASSERT
3499       Node* old_mem = n->in(MemNode::Memory);
3500       if (!visited.test_set(old_mem->_idx)) {
3501         old_mems.push(old_mem, old_mem->outcnt());
3502       }
3503 #endif
3504       assert(n->in(MemNode::Memory) != nmem, "sanity");
3505       if (!n->is_Load()) {
3506         // Move memory users of a store first.
3507         move_inst_mem(n, orig_phis);
3508       }
3509       // Now update memory input
3510       igvn->hash_delete(n);
3511       n->set_req(MemNode::Memory, nmem);
3512       igvn->hash_insert(n);
3513       record_for_optimizer(n);
3514     } else {
3515       assert(n->is_Allocate() || n->is_CheckCastPP() ||
3516              n->is_AddP() || n->is_Phi(), "unknown node used for set_map()");
3517     }
3518   }
3519 #if 0 // ifdef ASSERT
3520   // Verify that memory was split correctly
3521   while (old_mems.is_nonempty()) {
3522     Node* old_mem = old_mems.node();
3523     uint  old_cnt = old_mems.index();
3524     old_mems.pop();
3525     assert(old_cnt == old_mem->outcnt(), "old mem could be lost");
3526   }
3527 #endif
3528 }
3529 
3530 #ifndef PRODUCT
3531 static const char *node_type_names[] = {
3532   "UnknownType",
3533   "JavaObject",
3534   "LocalVar",
3535   "Field",
3536   "Arraycopy"
3537 };
3538 
3539 static const char *esc_names[] = {
3540   "UnknownEscape",
3541   "NoEscape",
3542   "ArgEscape",
3543   "GlobalEscape"
3544 };
3545 
3546 void PointsToNode::dump(bool print_state) const {
3547   NodeType nt = node_type();
3548   tty->print("%s ", node_type_names[(int) nt]);
3549   if (print_state) {
3550     EscapeState es = escape_state();
3551     EscapeState fields_es = fields_escape_state();
3552     tty->print("%s(%s) ", esc_names[(int)es], esc_names[(int)fields_es]);
3553     if (nt == PointsToNode::JavaObject && !this->scalar_replaceable())
3554       tty->print("NSR ");
3555   }
3556   if (is_Field()) {
3557     FieldNode* f = (FieldNode*)this;
3558     if (f->is_oop())
3559       tty->print("oop ");
3560     if (f->offset() > 0)
3561       tty->print("+%d ", f->offset());
3562     tty->print("(");
3563     for (BaseIterator i(f); i.has_next(); i.next()) {
3564       PointsToNode* b = i.get();
3565       tty->print(" %d%s", b->idx(),(b->is_JavaObject() ? "P" : ""));
3566     }
3567     tty->print(" )");
3568   }
3569   tty->print("[");
3570   for (EdgeIterator i(this); i.has_next(); i.next()) {
3571     PointsToNode* e = i.get();
3572     tty->print(" %d%s%s", e->idx(),(e->is_JavaObject() ? "P" : (e->is_Field() ? "F" : "")), e->is_Arraycopy() ? "cp" : "");
3573   }
3574   tty->print(" [");
3575   for (UseIterator i(this); i.has_next(); i.next()) {
3576     PointsToNode* u = i.get();
3577     bool is_base = false;
3578     if (PointsToNode::is_base_use(u)) {
3579       is_base = true;
3580       u = PointsToNode::get_use_node(u)->as_Field();
3581     }
3582     tty->print(" %d%s%s", u->idx(), is_base ? "b" : "", u->is_Arraycopy() ? "cp" : "");
3583   }
3584   tty->print(" ]]  ");
3585   if (_node == NULL)
3586     tty->print_cr("<null>");
3587   else
3588     _node->dump();
3589 }
3590 
3591 void ConnectionGraph::dump(GrowableArray<PointsToNode*>& ptnodes_worklist) {
3592   bool first = true;
3593   int ptnodes_length = ptnodes_worklist.length();
3594   for (int i = 0; i < ptnodes_length; i++) {
3595     PointsToNode *ptn = ptnodes_worklist.at(i);
3596     if (ptn == NULL || !ptn->is_JavaObject())
3597       continue;
3598     PointsToNode::EscapeState es = ptn->escape_state();
3599     if ((es != PointsToNode::NoEscape) && !Verbose) {
3600       continue;
3601     }
3602     Node* n = ptn->ideal_node();
3603     if (n->is_Allocate() || (n->is_CallStaticJava() &&
3604                              n->as_CallStaticJava()->is_boxing_method())) {
3605       if (first) {
3606         tty->cr();
3607         tty->print("======== Connection graph for ");
3608         _compile->method()->print_short_name();
3609         tty->cr();
3610         first = false;
3611       }
3612       ptn->dump();
3613       // Print all locals and fields which reference this allocation
3614       for (UseIterator j(ptn); j.has_next(); j.next()) {
3615         PointsToNode* use = j.get();
3616         if (use->is_LocalVar()) {
3617           use->dump(Verbose);
3618         } else if (Verbose) {
3619           use->dump();
3620         }
3621       }
3622       tty->cr();
3623     }
3624   }
3625 }
3626 #endif
3627 
3628 void ConnectionGraph::record_for_optimizer(Node *n) {
3629   _igvn->_worklist.push(n);
3630   _igvn->add_users_to_worklist(n);
3631 }