1 /*
   2  * Copyright (c) 2005, 2012, 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 #ifndef SHARE_VM_OPTO_ESCAPE_HPP
  26 #define SHARE_VM_OPTO_ESCAPE_HPP
  27 
  28 #include "opto/addnode.hpp"
  29 #include "opto/node.hpp"
  30 #include "utilities/growableArray.hpp"
  31 
  32 //
  33 // Adaptation for C2 of the escape analysis algorithm described in:
  34 //
  35 // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
  36 //          Vugranam C. Sreedhar, Sam Midkiff,
  37 //          "Escape Analysis for Java", Procedings of ACM SIGPLAN
  38 //          OOPSLA  Conference, November 1, 1999
  39 //
  40 // The flow-insensitive analysis described in the paper has been implemented.
  41 //
  42 // The analysis requires construction of a "connection graph" (CG) for
  43 // the method being analyzed.  The nodes of the connection graph are:
  44 //
  45 //     -  Java objects (JO)
  46 //     -  Local variables (LV)
  47 //     -  Fields of an object (OF),  these also include array elements
  48 //
  49 // The CG contains 3 types of edges:
  50 //
  51 //   -  PointsTo  (-P>)    {LV, OF} to JO
  52 //   -  Deferred  (-D>)    from {LV, OF} to {LV, OF}
  53 //   -  Field     (-F>)    from JO to OF
  54 //
  55 // The following  utility functions is used by the algorithm:
  56 //
  57 //   PointsTo(n) - n is any CG node, it returns the set of JO that n could
  58 //                 point to.
  59 //
  60 // The algorithm describes how to construct the connection graph
  61 // in the following 4 cases:
  62 //
  63 //          Case                  Edges Created
  64 //
  65 // (1)   p   = new T()              LV -P> JO
  66 // (2)   p   = q                    LV -D> LV
  67 // (3)   p.f = q                    JO -F> OF,  OF -D> LV
  68 // (4)   p   = q.f                  JO -F> OF,  LV -D> OF
  69 //
  70 // In all these cases, p and q are local variables.  For static field
  71 // references, we can construct a local variable containing a reference
  72 // to the static memory.
  73 //
  74 // C2 does not have local variables.  However for the purposes of constructing
  75 // the connection graph, the following IR nodes are treated as local variables:
  76 //     Phi    (pointer values)
  77 //     LoadP, LoadN
  78 //     Proj#5 (value returned from callnodes including allocations)
  79 //     CheckCastPP, CastPP
  80 //
  81 // The LoadP, Proj and CheckCastPP behave like variables assigned to only once.
  82 // Only a Phi can have multiple assignments.  Each input to a Phi is treated
  83 // as an assignment to it.
  84 //
  85 // The following node types are JavaObject:
  86 //
  87 //     phantom_object (general globally escaped object)
  88 //     Allocate
  89 //     AllocateArray
  90 //     Parm  (for incoming arguments)
  91 //     CastX2P ("unsafe" operations)
  92 //     CreateEx
  93 //     ConP
  94 //     LoadKlass
  95 //     ThreadLocal
  96 //     CallStaticJava (which returns Object)
  97 //
  98 // AddP nodes are fields.
  99 //
 100 // After building the graph, a pass is made over the nodes, deleting deferred
 101 // nodes and copying the edges from the target of the deferred edge to the
 102 // source.  This results in a graph with no deferred edges, only:
 103 //
 104 //    LV -P> JO
 105 //    OF -P> JO (the object whose oop is stored in the field)
 106 //    JO -F> OF
 107 //
 108 // Then, for each node which is GlobalEscape, anything it could point to
 109 // is marked GlobalEscape.  Finally, for any node marked ArgEscape, anything
 110 // it could point to is marked ArgEscape.
 111 //
 112 
 113 class  Compile;
 114 class  Node;
 115 class  CallNode;
 116 class  PhiNode;
 117 class  PhaseTransform;
 118 class  PointsToNode;
 119 class  Type;
 120 class  TypePtr;
 121 class  VectorSet;
 122 
 123 class JavaObjectNode;
 124 class LocalVarNode;
 125 class FieldNode;
 126 class ArraycopyNode;
 127 
 128 class ConnectionGraph;
 129 
 130 // ConnectionGraph nodes
 131 class PointsToNode : public ResourceObj {
 132   GrowableArray<PointsToNode*> _edges; // List of nodes this node points to
 133   GrowableArray<PointsToNode*> _uses;  // List of nodes which point to this node
 134 
 135   const u1           _type;  // NodeType
 136   u1                _flags;  // NodeFlags
 137   u1               _escape;  // EscapeState of object
 138   u1        _fields_escape;  // EscapeState of object's fields
 139 
 140   Node* const        _node;  // Ideal node corresponding to this PointsTo node.
 141   const int           _idx;  // Cached ideal node's _idx
 142   const uint         _pidx;  // Index of this node
 143 
 144 public:
 145   typedef enum {
 146     UnknownType = 0,
 147     JavaObject  = 1,
 148     LocalVar    = 2,
 149     Field       = 3,
 150     Arraycopy   = 4
 151   } NodeType;
 152 
 153   typedef enum {
 154     UnknownEscape = 0,
 155     NoEscape      = 1, // An object does not escape method or thread and it is
 156                        // not passed to call. It could be replaced with scalar.
 157     ArgEscape     = 2, // An object does not escape method or thread but it is
 158                        // passed as argument to call or referenced by argument
 159                        // and it does not escape during call.
 160     GlobalEscape  = 3  // An object escapes the method or thread.
 161   } EscapeState;
 162 
 163   typedef enum {
 164     ScalarReplaceable = 1,  // Not escaped object could be replaced with scalar
 165     PointsToUnknown   = 2,  // Has edge to phantom_object
 166     ArraycopySrc      = 4,  // Has edge from Arraycopy node
 167     ArraycopyDst      = 8   // Has edge to Arraycopy node
 168   } NodeFlags;
 169 
 170 
 171   inline PointsToNode(ConnectionGraph* CG, Node* n, EscapeState es, NodeType type);
 172 
 173   uint        pidx()   const { return _pidx; }
 174 
 175   Node* ideal_node()   const { return _node; }
 176   int          idx()   const { return _idx; }
 177 
 178   bool is_JavaObject() const { return _type == (u1)JavaObject; }
 179   bool is_LocalVar()   const { return _type == (u1)LocalVar; }
 180   bool is_Field()      const { return _type == (u1)Field; }
 181   bool is_Arraycopy()  const { return _type == (u1)Arraycopy; }
 182 
 183   JavaObjectNode* as_JavaObject() { assert(is_JavaObject(),""); return (JavaObjectNode*)this; }
 184   LocalVarNode*   as_LocalVar()   { assert(is_LocalVar(),"");   return (LocalVarNode*)this; }
 185   FieldNode*      as_Field()      { assert(is_Field(),"");      return (FieldNode*)this; }
 186   ArraycopyNode*  as_Arraycopy()  { assert(is_Arraycopy(),"");  return (ArraycopyNode*)this; }
 187 
 188   EscapeState escape_state() const { return (EscapeState)_escape; }
 189   void    set_escape_state(EscapeState state) { _escape = (u1)state; }
 190 
 191   EscapeState fields_escape_state() const { return (EscapeState)_fields_escape; }
 192   void    set_fields_escape_state(EscapeState state) { _fields_escape = (u1)state; }
 193 
 194   bool     has_unknown_ptr() const { return (_flags & PointsToUnknown) != 0; }
 195   void set_has_unknown_ptr()       { _flags |= PointsToUnknown; }
 196 
 197   bool     arraycopy_src() const { return (_flags & ArraycopySrc) != 0; }
 198   void set_arraycopy_src()       { _flags |= ArraycopySrc; }
 199   bool     arraycopy_dst() const { return (_flags & ArraycopyDst) != 0; }
 200   void set_arraycopy_dst()       { _flags |= ArraycopyDst; }
 201 
 202   bool     scalar_replaceable() const { return (_flags & ScalarReplaceable) != 0;}
 203   void set_scalar_replaceable(bool v) {
 204     if (v)
 205       _flags |= ScalarReplaceable;
 206     else
 207       _flags &= ~ScalarReplaceable;
 208   }
 209 
 210   int edge_count()              const { return _edges.length(); }
 211   PointsToNode* edge(int e)     const { return _edges.at(e); }
 212   bool add_edge(PointsToNode* edge)    { return _edges.append_if_missing(edge); }
 213 
 214   int use_count()             const { return _uses.length(); }
 215   PointsToNode* use(int e)    const { return _uses.at(e); }
 216   bool add_use(PointsToNode* use)    { return _uses.append_if_missing(use); }
 217 
 218   // Mark base edge use to distinguish from stored value edge.
 219   bool add_base_use(FieldNode* use) { return _uses.append_if_missing((PointsToNode*)((intptr_t)use + 1)); }
 220   static bool is_base_use(PointsToNode* use) { return (((intptr_t)use) & 1); }
 221   static PointsToNode* get_use_node(PointsToNode* use) { return (PointsToNode*)(((intptr_t)use) & ~1); }
 222 
 223   // Return true if this node points to specified node or nodes it points to.
 224   bool points_to(JavaObjectNode* ptn) const;
 225 
 226   // Return true if this node points only to non-escaping allocations.
 227   bool non_escaping_allocation();
 228 
 229   // Return true if one node points to an other.
 230   bool meet(PointsToNode* ptn);
 231 
 232 #ifndef PRODUCT
 233   NodeType node_type() const { return (NodeType)_type;}
 234   void dump(bool print_state=true) const;
 235 #endif
 236 
 237 };
 238 
 239 class LocalVarNode: public PointsToNode {
 240 public:
 241   LocalVarNode(ConnectionGraph *CG, Node* n, EscapeState es):
 242     PointsToNode(CG, n, es, LocalVar) {}
 243 };
 244 
 245 class JavaObjectNode: public PointsToNode {
 246 public:
 247   JavaObjectNode(ConnectionGraph *CG, Node* n, EscapeState es):
 248     PointsToNode(CG, n, es, JavaObject) {
 249       if (es > NoEscape)
 250         set_scalar_replaceable(false);
 251     }
 252 };
 253 
 254 class FieldNode: public PointsToNode {
 255   GrowableArray<PointsToNode*> _bases; // List of JavaObject nodes which point to this node
 256   const int   _offset; // Field's offset.
 257   const bool  _is_oop; // Field points to object
 258         bool  _has_unknown_base; // Has phantom_object base
 259 public:
 260   FieldNode(ConnectionGraph *CG, Node* n, EscapeState es, int offs, bool is_oop):
 261     PointsToNode(CG, n, es, Field),
 262     _offset(offs), _is_oop(is_oop),
 263     _has_unknown_base(false) {}
 264 
 265   int      offset()              const { return _offset;}
 266   bool     is_oop()              const { return _is_oop;}
 267   bool     has_unknown_base()    const { return _has_unknown_base; }
 268   void set_has_unknown_base()          { _has_unknown_base = true; }
 269 
 270   int base_count()              const { return _bases.length(); }
 271   PointsToNode* base(int e)     const { return _bases.at(e); }
 272   bool add_base(PointsToNode* base)    { return _bases.append_if_missing(base); }
 273 #ifdef ASSERT
 274   // Return true if bases points to this java object.
 275   bool has_base(JavaObjectNode* ptn) const;
 276 #endif
 277 
 278 };
 279 
 280 class ArraycopyNode: public PointsToNode {
 281 public:
 282   ArraycopyNode(ConnectionGraph *CG, Node* n, EscapeState es):
 283     PointsToNode(CG, n, es, Arraycopy) {}
 284 };
 285 
 286 // Iterators for PointsTo node's edges:
 287 //   for (EdgeIterator i(n); i.has_next(); i.next()) {
 288 //     PointsToNode* u = i.get();
 289 class PointsToIterator: public StackObj {
 290 protected:
 291   const PointsToNode* node;
 292   const int cnt;
 293   int i;
 294 public:
 295   inline PointsToIterator(const PointsToNode* n, int cnt) : node(n), cnt(cnt), i(0) { }
 296   inline bool has_next() const { return i < cnt; }
 297   inline void next() { i++; }
 298   PointsToNode* get() const { ShouldNotCallThis(); return NULL; }
 299 };
 300 
 301 class EdgeIterator: public PointsToIterator {
 302 public:
 303   inline EdgeIterator(const PointsToNode* n) : PointsToIterator(n, n->edge_count()) { }
 304   inline PointsToNode* get() const { return node->edge(i); }
 305 };
 306 
 307 class UseIterator: public PointsToIterator {
 308 public:
 309   inline UseIterator(const PointsToNode* n) : PointsToIterator(n, n->use_count()) { }
 310   inline PointsToNode* get() const { return node->use(i); }
 311 };
 312 
 313 class BaseIterator: public PointsToIterator {
 314 public:
 315   inline BaseIterator(const FieldNode* n) : PointsToIterator(n, n->base_count()) { }
 316   inline PointsToNode* get() const { return ((PointsToNode*)node)->as_Field()->base(i); }
 317 };
 318 
 319 
 320 class ConnectionGraph: public ResourceObj {
 321   friend class PointsToNode;
 322 private:
 323   GrowableArray<PointsToNode*>  _nodes; // Map from ideal nodes to
 324                                         // ConnectionGraph nodes.
 325 
 326   GrowableArray<PointsToNode*>  _worklist; // Nodes to be processed
 327   VectorSet                  _in_worklist;
 328   uint                         _next_pidx;
 329 
 330   bool            _collecting; // Indicates whether escape information
 331                                // is still being collected. If false,
 332                                // no new nodes will be processed.
 333 
 334   bool               _verify;  // verify graph
 335 
 336   JavaObjectNode* phantom_obj; // Unknown object
 337   JavaObjectNode*    null_obj;
 338   Node*             _pcmp_neq; // ConI(#CC_GT)
 339   Node*              _pcmp_eq; // ConI(#CC_EQ)
 340 
 341   Compile*           _compile; // Compile object for current compilation
 342   PhaseIterGVN*         _igvn; // Value numbering
 343 
 344   Unique_Node_List ideal_nodes; // Used by CG construction and types splitting.
 345 
 346   // Address of an element in _nodes.  Used when the element is to be modified
 347   PointsToNode* ptnode_adr(int idx) const {
 348     // There should be no new ideal nodes during ConnectionGraph build,
 349     // growableArray::at() will throw assert otherwise.
 350     return _nodes.at(idx);
 351   }
 352   uint nodes_size() const { return _nodes.length(); }
 353 
 354   uint next_pidx() { return _next_pidx++; }
 355 
 356   // Add nodes to ConnectionGraph.
 357   void add_local_var(Node* n, PointsToNode::EscapeState es);
 358   void add_java_object(Node* n, PointsToNode::EscapeState es);
 359   void add_field(Node* n, PointsToNode::EscapeState es, int offset);
 360   void add_arraycopy(Node* n, PointsToNode::EscapeState es, PointsToNode* src, PointsToNode* dst);
 361 
 362   // Compute the escape state for arguments to a call.
 363   void process_call_arguments(CallNode *call);
 364 
 365   // Add PointsToNode node corresponding to a call
 366   void add_call_node(CallNode* call);
 367 
 368   // Map ideal node to existing PointsTo node (usually phantom_object).
 369   void map_ideal_node(Node *n, PointsToNode* ptn) {
 370     assert(ptn != NULL, "only existing PointsTo node");
 371     _nodes.at_put(n->_idx, ptn);
 372   }
 373 
 374   // Utility function for nodes that load an object
 375   void add_objload_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist);
 376   // Create PointsToNode node and add it to Connection Graph.
 377   void add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist);
 378 
 379   // Add final simple edges to graph.
 380   void add_final_edges(Node *n);
 381 
 382   // Finish Graph construction.
 383   bool complete_connection_graph(GrowableArray<PointsToNode*>&   ptnodes_worklist,
 384                                  GrowableArray<JavaObjectNode*>& non_escaped_worklist,
 385                                  GrowableArray<JavaObjectNode*>& java_objects_worklist,
 386                                  GrowableArray<FieldNode*>&      oop_fields_worklist);
 387 
 388 #ifdef ASSERT
 389   void verify_connection_graph(GrowableArray<PointsToNode*>&   ptnodes_worklist,
 390                                GrowableArray<JavaObjectNode*>& non_escaped_worklist,
 391                                GrowableArray<JavaObjectNode*>& java_objects_worklist,
 392                                GrowableArray<Node*>& addp_worklist);
 393 #endif
 394 
 395   // Add all references to this JavaObject node.
 396   int add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist);
 397 
 398   // Put node on worklist if it is (or was) not there.
 399   inline void add_to_worklist(PointsToNode* pt) {
 400     PointsToNode* ptf = pt;
 401     uint pidx_bias = 0;
 402     if (PointsToNode::is_base_use(pt)) {
 403       // Create a separate entry in _in_worklist for a marked base edge
 404       // because _worklist may have an entry for a normal edge pointing
 405       // to the same node. To separate them use _next_pidx as bias.
 406       ptf = PointsToNode::get_use_node(pt)->as_Field();
 407       pidx_bias = _next_pidx;
 408     }
 409     if (!_in_worklist.test_set(ptf->pidx() + pidx_bias)) {
 410       _worklist.append(pt);
 411     }
 412   }
 413 
 414   // Put on worklist all uses of this node.
 415   inline void add_uses_to_worklist(PointsToNode* pt) {
 416     for (UseIterator i(pt); i.has_next(); i.next()) {
 417       add_to_worklist(i.get());
 418     }
 419   }
 420 
 421   // Put on worklist all field's uses and related field nodes.
 422   void add_field_uses_to_worklist(FieldNode* field);
 423 
 424   // Put on worklist all related field nodes.
 425   void add_fields_to_worklist(FieldNode* field, PointsToNode* base);
 426 
 427   // Find fields which have unknown value.
 428   int find_field_value(FieldNode* field);
 429 
 430   // Find fields initializing values for allocations.
 431   int find_init_values(JavaObjectNode* ptn, PointsToNode* init_val, PhaseTransform* phase);
 432 
 433   // Set the escape state of an object and its fields.
 434   void set_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) {
 435     // Don't change non-escaping state of NULL pointer.
 436     if (ptn != null_obj) {
 437       if (ptn->escape_state() < esc)
 438         ptn->set_escape_state(esc);
 439       if (ptn->fields_escape_state() < esc)
 440         ptn->set_fields_escape_state(esc);
 441     }
 442   }
 443   void set_fields_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) {
 444     // Don't change non-escaping state of NULL pointer.
 445     if (ptn != null_obj) {
 446       if (ptn->fields_escape_state() < esc)
 447         ptn->set_fields_escape_state(esc);
 448     }
 449   }
 450 
 451   // Propagate GlobalEscape and ArgEscape escape states to all nodes
 452   // and check that we still have non-escaping java objects.
 453   bool find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist,
 454                                 GrowableArray<JavaObjectNode*>& non_escaped_worklist);
 455 
 456   // Adjust scalar_replaceable state after Connection Graph is built.
 457   void adjust_scalar_replaceable_state(JavaObjectNode* jobj);
 458 
 459   // Optimize ideal graph.
 460   void optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist,
 461                             GrowableArray<Node*>& storestore_worklist);
 462   // Optimize objects compare.
 463   Node* optimize_ptr_compare(Node* n);
 464 
 465   // Returns unique corresponding java object or NULL.
 466   JavaObjectNode* unique_java_object(Node *n);
 467 
 468   // Add an edge of the specified type pointing to the specified target.
 469   bool add_edge(PointsToNode* from, PointsToNode* to) {
 470     assert(!from->is_Field() || from->as_Field()->is_oop(), "sanity");
 471 
 472     if (to == phantom_obj) {
 473       if (from->has_unknown_ptr()) {
 474         return false; // already points to phantom_obj
 475       }
 476       from->set_has_unknown_ptr();
 477     }
 478 
 479     bool is_new = from->add_edge(to);
 480     assert(to != phantom_obj || is_new, "sanity");
 481     if (is_new) { // New edge?
 482       assert(!_verify, "graph is incomplete");
 483       is_new = to->add_use(from);
 484       assert(is_new, "use should be also new");
 485     }
 486     return is_new;
 487   }
 488 
 489   // Add an edge from Field node to its base and back.
 490   bool add_base(FieldNode* from, PointsToNode* to) {
 491     assert(!to->is_Arraycopy(), "sanity");
 492     if (to == phantom_obj) {
 493       if (from->has_unknown_base()) {
 494         return false; // already has phantom_obj base
 495       }
 496       from->set_has_unknown_base();
 497     }
 498     bool is_new = from->add_base(to);
 499     assert(to != phantom_obj || is_new, "sanity");
 500     if (is_new) {      // New edge?
 501       assert(!_verify, "graph is incomplete");
 502       if (to == null_obj)
 503         return is_new; // Don't add fields to NULL pointer.
 504       if (to->is_JavaObject()) {
 505         is_new = to->add_edge(from);
 506       } else {
 507         is_new = to->add_base_use(from);
 508       }
 509       assert(is_new, "use should be also new");
 510     }
 511     return is_new;
 512   }
 513 
 514   // Add LocalVar node and edge if possible
 515   void add_local_var_and_edge(Node* n, PointsToNode::EscapeState es, Node* to,
 516                               Unique_Node_List *delayed_worklist) {
 517     PointsToNode* ptn = ptnode_adr(to->_idx);
 518     if (delayed_worklist != NULL) { // First iteration of CG construction
 519       add_local_var(n, es);
 520       if (ptn == NULL) {
 521         delayed_worklist->push(n);
 522         return; // Process it later.
 523       }
 524     } else {
 525       assert(ptn != NULL, "node should be registered");
 526     }
 527     add_edge(ptnode_adr(n->_idx), ptn);
 528  }
 529   // Helper functions
 530   bool   is_oop_field(Node* n, int offset, bool* unsafe);
 531   Node* get_addp_base(Node *addp);
 532   static Node* find_second_addp(Node* addp, Node* n);
 533   // offset of a field reference
 534   int address_offset(Node* adr, PhaseTransform *phase);
 535 
 536 
 537   // Propagate unique types created for unescaped allocated objects
 538   // through the graph
 539   void split_unique_types(GrowableArray<Node *>  &alloc_worklist, GrowableArray<ArrayCopyNode*> &arraycopy_worklist);
 540 
 541   // Helper methods for unique types split.
 542   bool split_AddP(Node *addp, Node *base);
 543 
 544   PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist, bool &new_created);
 545   PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *>  &orig_phi_worklist);
 546 
 547   void  move_inst_mem(Node* n, GrowableArray<PhiNode *>  &orig_phis);
 548   Node* find_inst_mem(Node* mem, int alias_idx,GrowableArray<PhiNode *>  &orig_phi_worklist);
 549   Node* step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop);
 550 
 551 
 552   GrowableArray<MergeMemNode*>  _mergemem_worklist; // List of all MergeMem nodes
 553 
 554   Node_Array _node_map; // used for bookeeping during type splitting
 555                         // Used for the following purposes:
 556                         // Memory Phi    - most recent unique Phi split out
 557                         //                 from this Phi
 558                         // MemNode       - new memory input for this node
 559                         // ChecCastPP    - allocation that this is a cast of
 560                         // allocation    - CheckCastPP of the allocation
 561 
 562   // manage entries in _node_map
 563 
 564   void  set_map(Node* from, Node* to)  {
 565     ideal_nodes.push(from);
 566     _node_map.map(from->_idx, to);
 567   }
 568 
 569   Node* get_map(int idx) { return _node_map[idx]; }
 570 
 571   PhiNode* get_map_phi(int idx) {
 572     Node* phi = _node_map[idx];
 573     return (phi == NULL) ? NULL : phi->as_Phi();
 574   }
 575 
 576   // Notify optimizer that a node has been modified
 577   void record_for_optimizer(Node *n) {
 578     _igvn->_worklist.push(n);
 579     _igvn->add_users_to_worklist(n);
 580   }
 581 
 582   // Compute the escape information
 583   bool compute_escape();
 584 
 585 public:
 586   ConnectionGraph(Compile *C, PhaseIterGVN *igvn);
 587 
 588   // Check for non-escaping candidates
 589   static bool has_candidates(Compile *C);
 590 
 591   // Perform escape analysis
 592   static void do_analysis(Compile *C, PhaseIterGVN *igvn);
 593 
 594   bool not_global_escape(Node *n);
 595 
 596 #ifndef PRODUCT
 597   void dump(GrowableArray<PointsToNode*>& ptnodes_worklist);
 598 #endif
 599 };
 600 
 601 inline PointsToNode::PointsToNode(ConnectionGraph *CG, Node* n, EscapeState es, NodeType type):
 602   _edges(CG->_compile->comp_arena(), 2, 0, NULL),
 603   _uses (CG->_compile->comp_arena(), 2, 0, NULL),
 604   _node(n),
 605   _idx(n->_idx),
 606   _pidx(CG->next_pidx()),
 607   _type((u1)type),
 608   _escape((u1)es),
 609   _fields_escape((u1)es),
 610   _flags(ScalarReplaceable) {
 611   assert(n != NULL && es != UnknownEscape, "sanity");
 612 }
 613 
 614 #endif // SHARE_VM_OPTO_ESCAPE_HPP