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 // ConnectionGraph nodes 129 class PointsToNode : public ResourceObj { 130 GrowableArray<PointsToNode*> _edges; // List of nodes this node points to 131 GrowableArray<PointsToNode*> _uses; // List of nodes which point to this node 132 133 const u1 _type; // NodeType 134 u1 _flags; // NodeFlags 135 u1 _escape; // EscapeState of object 136 u1 _fields_escape; // EscapeState of object's fields 137 138 Node* const _node; // Ideal node corresponding to this PointsTo node. 139 const int _idx; // Cached ideal node's _idx 140 141 public: 142 typedef enum { 143 UnknownType = 0, 144 JavaObject = 1, 145 LocalVar = 2, 146 Field = 3, 147 Arraycopy = 4 148 } NodeType; 149 150 typedef enum { 151 UnknownEscape = 0, 152 NoEscape = 1, // An object does not escape method or thread and it is 153 // not passed to call. It could be replaced with scalar. 154 ArgEscape = 2, // An object does not escape method or thread but it is 155 // passed as argument to call or referenced by argument 156 // and it does not escape during call. 157 GlobalEscape = 3 // An object escapes the method or thread. 158 } EscapeState; 159 160 typedef enum { 161 ScalarReplaceable = 1, // Not escaped object could be replaced with scalar 162 PointsToUnknown = 2, // Has edge to phantom_object 163 ArraycopySrc = 4, // Has edge from Arraycopy node 164 ArraycopyDst = 8 // Has edge to Arraycopy node 165 } NodeFlags; 166 167 168 PointsToNode(Compile *C, Node* n, EscapeState es, NodeType type): 169 _edges(C->comp_arena(), 2, 0, NULL), 170 _uses (C->comp_arena(), 2, 0, NULL), 171 _node(n), 172 _idx(n->_idx), 173 _type((u1)type), 174 _escape((u1)es), 175 _fields_escape((u1)es), 176 _flags(ScalarReplaceable) { 177 assert(n != NULL && es != UnknownEscape, "sanity"); 178 } 179 180 Node* ideal_node() const { return _node; } 181 int idx() const { return _idx; } 182 183 bool is_JavaObject() const { return _type == (u1)JavaObject; } 184 bool is_LocalVar() const { return _type == (u1)LocalVar; } 185 bool is_Field() const { return _type == (u1)Field; } 186 bool is_Arraycopy() const { return _type == (u1)Arraycopy; } 187 188 JavaObjectNode* as_JavaObject() { assert(is_JavaObject(),""); return (JavaObjectNode*)this; } 189 LocalVarNode* as_LocalVar() { assert(is_LocalVar(),""); return (LocalVarNode*)this; } 190 FieldNode* as_Field() { assert(is_Field(),""); return (FieldNode*)this; } 191 ArraycopyNode* as_Arraycopy() { assert(is_Arraycopy(),""); return (ArraycopyNode*)this; } 192 193 EscapeState escape_state() const { return (EscapeState)_escape; } 194 void set_escape_state(EscapeState state) { _escape = (u1)state; } 195 196 EscapeState fields_escape_state() const { return (EscapeState)_fields_escape; } 197 void set_fields_escape_state(EscapeState state) { _fields_escape = (u1)state; } 198 199 bool has_unknown_ptr() const { return (_flags & PointsToUnknown) != 0; } 200 void set_has_unknown_ptr() { _flags |= PointsToUnknown; } 201 202 bool arraycopy_src() const { return (_flags & ArraycopySrc) != 0; } 203 void set_arraycopy_src() { _flags |= ArraycopySrc; } 204 bool arraycopy_dst() const { return (_flags & ArraycopyDst) != 0; } 205 void set_arraycopy_dst() { _flags |= ArraycopyDst; } 206 207 bool scalar_replaceable() const { return (_flags & ScalarReplaceable) != 0;} 208 void set_scalar_replaceable(bool v) { 209 if (v) 210 _flags |= ScalarReplaceable; 211 else 212 _flags &= ~ScalarReplaceable; 213 } 214 215 int edge_count() const { return _edges.length(); } 216 PointsToNode* edge(int e) const { return _edges.at(e); } 217 bool add_edge(PointsToNode* edge) { return _edges.append_if_missing(edge); } 218 219 int use_count() const { return _uses.length(); } 220 PointsToNode* use(int e) const { return _uses.at(e); } 221 bool add_use(PointsToNode* use) { return _uses.append_if_missing(use); } 222 223 // Mark base edge use to distinguish from stored value edge. 224 bool add_base_use(FieldNode* use) { return _uses.append_if_missing((PointsToNode*)((intptr_t)use + 1)); } 225 static bool is_base_use(PointsToNode* use) { return (((intptr_t)use) & 1); } 226 static PointsToNode* get_use_node(PointsToNode* use) { return (PointsToNode*)(((intptr_t)use) & ~1); } 227 228 // Return true if this node points to specified node or nodes it points to. 229 bool points_to(JavaObjectNode* ptn) const; 230 231 // Return true if this node points only to non-escaping allocations. 232 bool non_escaping_allocation(); 233 234 // Return true if one node points to an other. 235 bool meet(PointsToNode* ptn); 236 237 #ifndef PRODUCT 238 NodeType node_type() const { return (NodeType)_type;} 239 void dump(bool print_state=true) const; 240 #endif 241 242 }; 243 244 class LocalVarNode: public PointsToNode { 245 public: 246 LocalVarNode(Compile *C, Node* n, EscapeState es): 247 PointsToNode(C, n, es, LocalVar) {} 248 }; 249 250 class JavaObjectNode: public PointsToNode { 251 public: 252 JavaObjectNode(Compile *C, Node* n, EscapeState es): 253 PointsToNode(C, n, es, JavaObject) { 254 if (es > NoEscape) 255 set_scalar_replaceable(false); 256 } 257 }; 258 259 class FieldNode: public PointsToNode { 260 GrowableArray<PointsToNode*> _bases; // List of JavaObject nodes which point to this node 261 const int _offset; // Field's offset. 262 const bool _is_oop; // Field points to object 263 bool _has_unknown_base; // Has phantom_object base 264 public: 265 FieldNode(Compile *C, Node* n, EscapeState es, int offs, bool is_oop): 266 PointsToNode(C, n, es, Field), 267 _offset(offs), _is_oop(is_oop), 268 _has_unknown_base(false) {} 269 270 int offset() const { return _offset;} 271 bool is_oop() const { return _is_oop;} 272 bool has_unknown_base() const { return _has_unknown_base; } 273 void set_has_unknown_base() { _has_unknown_base = true; } 274 275 int base_count() const { return _bases.length(); } 276 PointsToNode* base(int e) const { return _bases.at(e); } 277 bool add_base(PointsToNode* base) { return _bases.append_if_missing(base); } 278 #ifdef ASSERT 279 // Return true if bases points to this java object. 280 bool has_base(JavaObjectNode* ptn) const; 281 #endif 282 283 }; 284 285 class ArraycopyNode: public PointsToNode { 286 public: 287 ArraycopyNode(Compile *C, Node* n, EscapeState es): 288 PointsToNode(C, n, es, Arraycopy) {} 289 }; 290 291 // Iterators for PointsTo node's edges: 292 // for (EdgeIterator i(n); i.has_next(); i.next()) { 293 // PointsToNode* u = i.get(); 294 class PointsToIterator: public StackObj { 295 protected: 296 const PointsToNode* node; 297 const int cnt; 298 int i; 299 public: 300 inline PointsToIterator(const PointsToNode* n, int cnt) : node(n), cnt(cnt), i(0) { } 301 inline bool has_next() const { return i < cnt; } 302 inline void next() { i++; } 303 PointsToNode* get() const { ShouldNotCallThis(); return NULL; } 304 }; 305 306 class EdgeIterator: public PointsToIterator { 307 public: 308 inline EdgeIterator(const PointsToNode* n) : PointsToIterator(n, n->edge_count()) { } 309 inline PointsToNode* get() const { return node->edge(i); } 310 }; 311 312 class UseIterator: public PointsToIterator { 313 public: 314 inline UseIterator(const PointsToNode* n) : PointsToIterator(n, n->use_count()) { } 315 inline PointsToNode* get() const { return node->use(i); } 316 }; 317 318 class BaseIterator: public PointsToIterator { 319 public: 320 inline BaseIterator(const FieldNode* n) : PointsToIterator(n, n->base_count()) { } 321 inline PointsToNode* get() const { return ((PointsToNode*)node)->as_Field()->base(i); } 322 }; 323 324 325 class ConnectionGraph: public ResourceObj { 326 private: 327 GrowableArray<PointsToNode*> _nodes; // Map from ideal nodes to 328 // ConnectionGraph nodes. 329 330 GrowableArray<PointsToNode*> _worklist; // Nodes to be processed 331 332 bool _collecting; // Indicates whether escape information 333 // is still being collected. If false, 334 // no new nodes will be processed. 335 336 bool _verify; // verify graph 337 338 JavaObjectNode* phantom_obj; // Unknown object 339 JavaObjectNode* null_obj; 340 Node* _pcmp_neq; // ConI(#CC_GT) 341 Node* _pcmp_eq; // ConI(#CC_EQ) 342 343 Compile* _compile; // Compile object for current compilation 344 PhaseIterGVN* _igvn; // Value numbering 345 346 Unique_Node_List ideal_nodes; // Used by CG construction and types splitting. 347 348 // Address of an element in _nodes. Used when the element is to be modified 349 PointsToNode* ptnode_adr(int idx) const { 350 // There should be no new ideal nodes during ConnectionGraph build, 351 // growableArray::at() will throw assert otherwise. 352 return _nodes.at(idx); 353 } 354 uint nodes_size() const { return _nodes.length(); } 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 // Create PointsToNode node and add it to Connection Graph. 375 void add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist); 376 377 // Add final simple edges to graph. 378 void add_final_edges(Node *n); 379 380 // Finish Graph construction. 381 bool complete_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist, 382 GrowableArray<JavaObjectNode*>& non_escaped_worklist, 383 GrowableArray<JavaObjectNode*>& java_objects_worklist, 384 GrowableArray<FieldNode*>& oop_fields_worklist); 385 386 #ifdef ASSERT 387 void verify_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist, 388 GrowableArray<JavaObjectNode*>& non_escaped_worklist, 389 GrowableArray<JavaObjectNode*>& java_objects_worklist, 390 GrowableArray<Node*>& addp_worklist); 391 #endif 392 393 // Add all references to this JavaObject node. 394 int add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist); 395 396 // Put node on worklist if it is (or was) not there. 397 void add_to_worklist(PointsToNode* pt) { 398 _worklist.push(pt); 399 return; 400 } 401 402 // Put on worklist all uses of this node. 403 void add_uses_to_worklist(PointsToNode* pt) { 404 for (UseIterator i(pt); i.has_next(); i.next()) 405 _worklist.push(i.get()); 406 } 407 408 // Put on worklist all field's uses and related field nodes. 409 void add_field_uses_to_worklist(FieldNode* field); 410 411 // Put on worklist all related field nodes. 412 void add_fields_to_worklist(FieldNode* field, PointsToNode* base); 413 414 // Find fields which have unknown value. 415 int find_field_value(FieldNode* field); 416 417 // Find fields initializing values for allocations. 418 int find_init_values(JavaObjectNode* ptn, PointsToNode* init_val, PhaseTransform* phase); 419 420 // Set the escape state of an object and its fields. 421 void set_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) { 422 // Don't change non-escaping state of NULL pointer. 423 if (ptn != null_obj) { 424 if (ptn->escape_state() < esc) 425 ptn->set_escape_state(esc); 426 if (ptn->fields_escape_state() < esc) 427 ptn->set_fields_escape_state(esc); 428 } 429 } 430 void set_fields_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) { 431 // Don't change non-escaping state of NULL pointer. 432 if (ptn != null_obj) { 433 if (ptn->fields_escape_state() < esc) 434 ptn->set_fields_escape_state(esc); 435 } 436 } 437 438 // Propagate GlobalEscape and ArgEscape escape states to all nodes 439 // and check that we still have non-escaping java objects. 440 bool find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist, 441 GrowableArray<JavaObjectNode*>& non_escaped_worklist); 442 443 // Adjust scalar_replaceable state after Connection Graph is built. 444 void adjust_scalar_replaceable_state(JavaObjectNode* jobj); 445 446 // Optimize ideal graph. 447 void optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist, 448 GrowableArray<Node*>& storestore_worklist); 449 // Optimize objects compare. 450 Node* optimize_ptr_compare(Node* n); 451 452 // Returns unique corresponding java object or NULL. 453 JavaObjectNode* unique_java_object(Node *n); 454 455 // Add an edge of the specified type pointing to the specified target. 456 bool add_edge(PointsToNode* from, PointsToNode* to) { 457 assert(!from->is_Field() || from->as_Field()->is_oop(), "sanity"); 458 459 if (to == phantom_obj) { 460 if (from->has_unknown_ptr()) { 461 return false; // already points to phantom_obj 462 } 463 from->set_has_unknown_ptr(); 464 } 465 466 bool is_new = from->add_edge(to); 467 assert(to != phantom_obj || is_new, "sanity"); 468 if (is_new) { // New edge? 469 assert(!_verify, "graph is incomplete"); 470 is_new = to->add_use(from); 471 assert(is_new, "use should be also new"); 472 } 473 return is_new; 474 } 475 476 // Add an edge from Field node to its base and back. 477 bool add_base(FieldNode* from, PointsToNode* to) { 478 assert(!to->is_Arraycopy(), "sanity"); 479 if (to == phantom_obj) { 480 if (from->has_unknown_base()) { 481 return false; // already has phantom_obj base 482 } 483 from->set_has_unknown_base(); 484 } 485 bool is_new = from->add_base(to); 486 assert(to != phantom_obj || is_new, "sanity"); 487 if (is_new) { // New edge? 488 assert(!_verify, "graph is incomplete"); 489 if (to == null_obj) 490 return is_new; // Don't add fields to NULL pointer. 491 if (to->is_JavaObject()) { 492 is_new = to->add_edge(from); 493 } else { 494 is_new = to->add_base_use(from); 495 } 496 assert(is_new, "use should be also new"); 497 } 498 return is_new; 499 } 500 501 // Add LocalVar node and edge if possible 502 void add_local_var_and_edge(Node* n, PointsToNode::EscapeState es, Node* to, 503 Unique_Node_List *delayed_worklist) { 504 PointsToNode* ptn = ptnode_adr(to->_idx); 505 if (delayed_worklist != NULL) { // First iteration of CG construction 506 add_local_var(n, es); 507 if (ptn == NULL) { 508 delayed_worklist->push(n); 509 return; // Process it later. 510 } 511 } else { 512 assert(ptn != NULL, "node should be registered"); 513 } 514 add_edge(ptnode_adr(n->_idx), ptn); 515 } 516 517 // Helper functions 518 bool is_oop_field(Node* n, int offset); 519 static Node* get_addp_base(Node *addp); 520 static Node* find_second_addp(Node* addp, Node* n); 521 522 // offset of a field reference 523 int address_offset(Node* adr, PhaseTransform *phase); 524 525 526 // Propagate unique types created for unescaped allocated objects 527 // through the graph 528 void split_unique_types(GrowableArray<Node *> &alloc_worklist); 529 530 // Helper methods for unique types split. 531 bool split_AddP(Node *addp, Node *base); 532 533 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, bool &new_created); 534 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist); 535 536 void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis); 537 Node* find_inst_mem(Node* mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist); 538 Node* step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop); 539 540 541 GrowableArray<MergeMemNode*> _mergemem_worklist; // List of all MergeMem nodes 542 543 Node_Array _node_map; // used for bookeeping during type splitting 544 // Used for the following purposes: 545 // Memory Phi - most recent unique Phi split out 546 // from this Phi 547 // MemNode - new memory input for this node 548 // ChecCastPP - allocation that this is a cast of 549 // allocation - CheckCastPP of the allocation 550 551 // manage entries in _node_map 552 553 void set_map(Node* from, Node* to) { 554 ideal_nodes.push(from); 555 _node_map.map(from->_idx, to); 556 } 557 558 Node* get_map(int idx) { return _node_map[idx]; } 559 560 PhiNode* get_map_phi(int idx) { 561 Node* phi = _node_map[idx]; 562 return (phi == NULL) ? NULL : phi->as_Phi(); 563 } 564 565 // Notify optimizer that a node has been modified 566 void record_for_optimizer(Node *n) { 567 _igvn->_worklist.push(n); 568 _igvn->add_users_to_worklist(n); 569 } 570 571 // Compute the escape information 572 bool compute_escape(); 573 574 public: 575 ConnectionGraph(Compile *C, PhaseIterGVN *igvn); 576 577 // Check for non-escaping candidates 578 static bool has_candidates(Compile *C); 579 580 // Perform escape analysis 581 static void do_analysis(Compile *C, PhaseIterGVN *igvn); 582 583 bool not_global_escape(Node *n); 584 585 #ifndef PRODUCT 586 void dump(GrowableArray<PointsToNode*>& ptnodes_worklist); 587 #endif 588 }; 589 590 #endif // SHARE_VM_OPTO_ESCAPE_HPP