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