Mercurial > hg > truffle
view src/share/vm/opto/escape.hpp @ 15583:d331b7c3d7c4
[single-pass-iter] start of evolution towards a node iterator less memory-hungry
author | Miguel Garcia <miguel.m.garcia@oracle.com> |
---|---|
date | Fri, 09 May 2014 16:22:54 +0200 |
parents | 7eca5de9e0b6 |
children | 90297adbda9d |
line wrap: on
line source
/* * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #ifndef SHARE_VM_OPTO_ESCAPE_HPP #define SHARE_VM_OPTO_ESCAPE_HPP #include "opto/addnode.hpp" #include "opto/node.hpp" #include "utilities/growableArray.hpp" // // Adaptation for C2 of the escape analysis algorithm described in: // // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, // Vugranam C. Sreedhar, Sam Midkiff, // "Escape Analysis for Java", Procedings of ACM SIGPLAN // OOPSLA Conference, November 1, 1999 // // The flow-insensitive analysis described in the paper has been implemented. // // The analysis requires construction of a "connection graph" (CG) for // the method being analyzed. The nodes of the connection graph are: // // - Java objects (JO) // - Local variables (LV) // - Fields of an object (OF), these also include array elements // // The CG contains 3 types of edges: // // - PointsTo (-P>) {LV, OF} to JO // - Deferred (-D>) from {LV, OF} to {LV, OF} // - Field (-F>) from JO to OF // // The following utility functions is used by the algorithm: // // PointsTo(n) - n is any CG node, it returns the set of JO that n could // point to. // // The algorithm describes how to construct the connection graph // in the following 4 cases: // // Case Edges Created // // (1) p = new T() LV -P> JO // (2) p = q LV -D> LV // (3) p.f = q JO -F> OF, OF -D> LV // (4) p = q.f JO -F> OF, LV -D> OF // // In all these cases, p and q are local variables. For static field // references, we can construct a local variable containing a reference // to the static memory. // // C2 does not have local variables. However for the purposes of constructing // the connection graph, the following IR nodes are treated as local variables: // Phi (pointer values) // LoadP, LoadN // Proj#5 (value returned from callnodes including allocations) // CheckCastPP, CastPP // // The LoadP, Proj and CheckCastPP behave like variables assigned to only once. // Only a Phi can have multiple assignments. Each input to a Phi is treated // as an assignment to it. // // The following node types are JavaObject: // // phantom_object (general globally escaped object) // Allocate // AllocateArray // Parm (for incoming arguments) // CastX2P ("unsafe" operations) // CreateEx // ConP // LoadKlass // ThreadLocal // CallStaticJava (which returns Object) // // AddP nodes are fields. // // After building the graph, a pass is made over the nodes, deleting deferred // nodes and copying the edges from the target of the deferred edge to the // source. This results in a graph with no deferred edges, only: // // LV -P> JO // OF -P> JO (the object whose oop is stored in the field) // JO -F> OF // // Then, for each node which is GlobalEscape, anything it could point to // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything // it could point to is marked ArgEscape. // class Compile; class Node; class CallNode; class PhiNode; class PhaseTransform; class PointsToNode; class Type; class TypePtr; class VectorSet; class JavaObjectNode; class LocalVarNode; class FieldNode; class ArraycopyNode; // ConnectionGraph nodes class PointsToNode : public ResourceObj { GrowableArray<PointsToNode*> _edges; // List of nodes this node points to GrowableArray<PointsToNode*> _uses; // List of nodes which point to this node const u1 _type; // NodeType u1 _flags; // NodeFlags u1 _escape; // EscapeState of object u1 _fields_escape; // EscapeState of object's fields Node* const _node; // Ideal node corresponding to this PointsTo node. const int _idx; // Cached ideal node's _idx public: typedef enum { UnknownType = 0, JavaObject = 1, LocalVar = 2, Field = 3, Arraycopy = 4 } NodeType; typedef enum { UnknownEscape = 0, NoEscape = 1, // An object does not escape method or thread and it is // not passed to call. It could be replaced with scalar. ArgEscape = 2, // An object does not escape method or thread but it is // passed as argument to call or referenced by argument // and it does not escape during call. GlobalEscape = 3 // An object escapes the method or thread. } EscapeState; typedef enum { ScalarReplaceable = 1, // Not escaped object could be replaced with scalar PointsToUnknown = 2, // Has edge to phantom_object ArraycopySrc = 4, // Has edge from Arraycopy node ArraycopyDst = 8 // Has edge to Arraycopy node } NodeFlags; PointsToNode(Compile *C, Node* n, EscapeState es, NodeType type): _edges(C->comp_arena(), 2, 0, NULL), _uses (C->comp_arena(), 2, 0, NULL), _node(n), _idx(n->_idx), _type((u1)type), _escape((u1)es), _fields_escape((u1)es), _flags(ScalarReplaceable) { assert(n != NULL && es != UnknownEscape, "sanity"); } Node* ideal_node() const { return _node; } int idx() const { return _idx; } bool is_JavaObject() const { return _type == (u1)JavaObject; } bool is_LocalVar() const { return _type == (u1)LocalVar; } bool is_Field() const { return _type == (u1)Field; } bool is_Arraycopy() const { return _type == (u1)Arraycopy; } JavaObjectNode* as_JavaObject() { assert(is_JavaObject(),""); return (JavaObjectNode*)this; } LocalVarNode* as_LocalVar() { assert(is_LocalVar(),""); return (LocalVarNode*)this; } FieldNode* as_Field() { assert(is_Field(),""); return (FieldNode*)this; } ArraycopyNode* as_Arraycopy() { assert(is_Arraycopy(),""); return (ArraycopyNode*)this; } EscapeState escape_state() const { return (EscapeState)_escape; } void set_escape_state(EscapeState state) { _escape = (u1)state; } EscapeState fields_escape_state() const { return (EscapeState)_fields_escape; } void set_fields_escape_state(EscapeState state) { _fields_escape = (u1)state; } bool has_unknown_ptr() const { return (_flags & PointsToUnknown) != 0; } void set_has_unknown_ptr() { _flags |= PointsToUnknown; } bool arraycopy_src() const { return (_flags & ArraycopySrc) != 0; } void set_arraycopy_src() { _flags |= ArraycopySrc; } bool arraycopy_dst() const { return (_flags & ArraycopyDst) != 0; } void set_arraycopy_dst() { _flags |= ArraycopyDst; } bool scalar_replaceable() const { return (_flags & ScalarReplaceable) != 0;} void set_scalar_replaceable(bool v) { if (v) _flags |= ScalarReplaceable; else _flags &= ~ScalarReplaceable; } int edge_count() const { return _edges.length(); } PointsToNode* edge(int e) const { return _edges.at(e); } bool add_edge(PointsToNode* edge) { return _edges.append_if_missing(edge); } int use_count() const { return _uses.length(); } PointsToNode* use(int e) const { return _uses.at(e); } bool add_use(PointsToNode* use) { return _uses.append_if_missing(use); } // Mark base edge use to distinguish from stored value edge. bool add_base_use(FieldNode* use) { return _uses.append_if_missing((PointsToNode*)((intptr_t)use + 1)); } static bool is_base_use(PointsToNode* use) { return (((intptr_t)use) & 1); } static PointsToNode* get_use_node(PointsToNode* use) { return (PointsToNode*)(((intptr_t)use) & ~1); } // Return true if this node points to specified node or nodes it points to. bool points_to(JavaObjectNode* ptn) const; // Return true if this node points only to non-escaping allocations. bool non_escaping_allocation(); // Return true if one node points to an other. bool meet(PointsToNode* ptn); #ifndef PRODUCT NodeType node_type() const { return (NodeType)_type;} void dump(bool print_state=true) const; #endif }; class LocalVarNode: public PointsToNode { public: LocalVarNode(Compile *C, Node* n, EscapeState es): PointsToNode(C, n, es, LocalVar) {} }; class JavaObjectNode: public PointsToNode { public: JavaObjectNode(Compile *C, Node* n, EscapeState es): PointsToNode(C, n, es, JavaObject) { if (es > NoEscape) set_scalar_replaceable(false); } }; class FieldNode: public PointsToNode { GrowableArray<PointsToNode*> _bases; // List of JavaObject nodes which point to this node const int _offset; // Field's offset. const bool _is_oop; // Field points to object bool _has_unknown_base; // Has phantom_object base public: FieldNode(Compile *C, Node* n, EscapeState es, int offs, bool is_oop): PointsToNode(C, n, es, Field), _offset(offs), _is_oop(is_oop), _has_unknown_base(false) {} int offset() const { return _offset;} bool is_oop() const { return _is_oop;} bool has_unknown_base() const { return _has_unknown_base; } void set_has_unknown_base() { _has_unknown_base = true; } int base_count() const { return _bases.length(); } PointsToNode* base(int e) const { return _bases.at(e); } bool add_base(PointsToNode* base) { return _bases.append_if_missing(base); } #ifdef ASSERT // Return true if bases points to this java object. bool has_base(JavaObjectNode* ptn) const; #endif }; class ArraycopyNode: public PointsToNode { public: ArraycopyNode(Compile *C, Node* n, EscapeState es): PointsToNode(C, n, es, Arraycopy) {} }; // Iterators for PointsTo node's edges: // for (EdgeIterator i(n); i.has_next(); i.next()) { // PointsToNode* u = i.get(); class PointsToIterator: public StackObj { protected: const PointsToNode* node; const int cnt; int i; public: inline PointsToIterator(const PointsToNode* n, int cnt) : node(n), cnt(cnt), i(0) { } inline bool has_next() const { return i < cnt; } inline void next() { i++; } PointsToNode* get() const { ShouldNotCallThis(); return NULL; } }; class EdgeIterator: public PointsToIterator { public: inline EdgeIterator(const PointsToNode* n) : PointsToIterator(n, n->edge_count()) { } inline PointsToNode* get() const { return node->edge(i); } }; class UseIterator: public PointsToIterator { public: inline UseIterator(const PointsToNode* n) : PointsToIterator(n, n->use_count()) { } inline PointsToNode* get() const { return node->use(i); } }; class BaseIterator: public PointsToIterator { public: inline BaseIterator(const FieldNode* n) : PointsToIterator(n, n->base_count()) { } inline PointsToNode* get() const { return ((PointsToNode*)node)->as_Field()->base(i); } }; class ConnectionGraph: public ResourceObj { private: GrowableArray<PointsToNode*> _nodes; // Map from ideal nodes to // ConnectionGraph nodes. GrowableArray<PointsToNode*> _worklist; // Nodes to be processed bool _collecting; // Indicates whether escape information // is still being collected. If false, // no new nodes will be processed. bool _verify; // verify graph JavaObjectNode* phantom_obj; // Unknown object JavaObjectNode* null_obj; Node* _pcmp_neq; // ConI(#CC_GT) Node* _pcmp_eq; // ConI(#CC_EQ) Compile* _compile; // Compile object for current compilation PhaseIterGVN* _igvn; // Value numbering Unique_Node_List ideal_nodes; // Used by CG construction and types splitting. // Address of an element in _nodes. Used when the element is to be modified PointsToNode* ptnode_adr(int idx) const { // There should be no new ideal nodes during ConnectionGraph build, // growableArray::at() will throw assert otherwise. return _nodes.at(idx); } uint nodes_size() const { return _nodes.length(); } // Add nodes to ConnectionGraph. void add_local_var(Node* n, PointsToNode::EscapeState es); void add_java_object(Node* n, PointsToNode::EscapeState es); void add_field(Node* n, PointsToNode::EscapeState es, int offset); void add_arraycopy(Node* n, PointsToNode::EscapeState es, PointsToNode* src, PointsToNode* dst); // Compute the escape state for arguments to a call. void process_call_arguments(CallNode *call); // Add PointsToNode node corresponding to a call void add_call_node(CallNode* call); // Map ideal node to existing PointsTo node (usually phantom_object). void map_ideal_node(Node *n, PointsToNode* ptn) { assert(ptn != NULL, "only existing PointsTo node"); _nodes.at_put(n->_idx, ptn); } // Utility function for nodes that load an object void add_objload_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist); // Create PointsToNode node and add it to Connection Graph. void add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist); // Add final simple edges to graph. void add_final_edges(Node *n); // Finish Graph construction. bool complete_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist, GrowableArray<JavaObjectNode*>& non_escaped_worklist, GrowableArray<JavaObjectNode*>& java_objects_worklist, GrowableArray<FieldNode*>& oop_fields_worklist); #ifdef ASSERT void verify_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist, GrowableArray<JavaObjectNode*>& non_escaped_worklist, GrowableArray<JavaObjectNode*>& java_objects_worklist, GrowableArray<Node*>& addp_worklist); #endif // Add all references to this JavaObject node. int add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist); // Put node on worklist if it is (or was) not there. void add_to_worklist(PointsToNode* pt) { _worklist.push(pt); return; } // Put on worklist all uses of this node. void add_uses_to_worklist(PointsToNode* pt) { for (UseIterator i(pt); i.has_next(); i.next()) _worklist.push(i.get()); } // Put on worklist all field's uses and related field nodes. void add_field_uses_to_worklist(FieldNode* field); // Put on worklist all related field nodes. void add_fields_to_worklist(FieldNode* field, PointsToNode* base); // Find fields which have unknown value. int find_field_value(FieldNode* field); // Find fields initializing values for allocations. int find_init_values(JavaObjectNode* ptn, PointsToNode* init_val, PhaseTransform* phase); // Set the escape state of an object and its fields. void set_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) { // Don't change non-escaping state of NULL pointer. if (ptn != null_obj) { if (ptn->escape_state() < esc) ptn->set_escape_state(esc); if (ptn->fields_escape_state() < esc) ptn->set_fields_escape_state(esc); } } void set_fields_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc) { // Don't change non-escaping state of NULL pointer. if (ptn != null_obj) { if (ptn->fields_escape_state() < esc) ptn->set_fields_escape_state(esc); } } // Propagate GlobalEscape and ArgEscape escape states to all nodes // and check that we still have non-escaping java objects. bool find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist, GrowableArray<JavaObjectNode*>& non_escaped_worklist); // Adjust scalar_replaceable state after Connection Graph is built. void adjust_scalar_replaceable_state(JavaObjectNode* jobj); // Optimize ideal graph. void optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist, GrowableArray<Node*>& storestore_worklist); // Optimize objects compare. Node* optimize_ptr_compare(Node* n); // Returns unique corresponding java object or NULL. JavaObjectNode* unique_java_object(Node *n); // Add an edge of the specified type pointing to the specified target. bool add_edge(PointsToNode* from, PointsToNode* to) { assert(!from->is_Field() || from->as_Field()->is_oop(), "sanity"); if (to == phantom_obj) { if (from->has_unknown_ptr()) { return false; // already points to phantom_obj } from->set_has_unknown_ptr(); } bool is_new = from->add_edge(to); assert(to != phantom_obj || is_new, "sanity"); if (is_new) { // New edge? assert(!_verify, "graph is incomplete"); is_new = to->add_use(from); assert(is_new, "use should be also new"); } return is_new; } // Add an edge from Field node to its base and back. bool add_base(FieldNode* from, PointsToNode* to) { assert(!to->is_Arraycopy(), "sanity"); if (to == phantom_obj) { if (from->has_unknown_base()) { return false; // already has phantom_obj base } from->set_has_unknown_base(); } bool is_new = from->add_base(to); assert(to != phantom_obj || is_new, "sanity"); if (is_new) { // New edge? assert(!_verify, "graph is incomplete"); if (to == null_obj) return is_new; // Don't add fields to NULL pointer. if (to->is_JavaObject()) { is_new = to->add_edge(from); } else { is_new = to->add_base_use(from); } assert(is_new, "use should be also new"); } return is_new; } // Add LocalVar node and edge if possible void add_local_var_and_edge(Node* n, PointsToNode::EscapeState es, Node* to, Unique_Node_List *delayed_worklist) { PointsToNode* ptn = ptnode_adr(to->_idx); if (delayed_worklist != NULL) { // First iteration of CG construction add_local_var(n, es); if (ptn == NULL) { delayed_worklist->push(n); return; // Process it later. } } else { assert(ptn != NULL, "node should be registered"); } add_edge(ptnode_adr(n->_idx), ptn); } // Helper functions bool is_oop_field(Node* n, int offset, bool* unsafe); static Node* get_addp_base(Node *addp); static Node* find_second_addp(Node* addp, Node* n); // offset of a field reference int address_offset(Node* adr, PhaseTransform *phase); // Propagate unique types created for unescaped allocated objects // through the graph void split_unique_types(GrowableArray<Node *> &alloc_worklist); // Helper methods for unique types split. bool split_AddP(Node *addp, Node *base); PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, bool &new_created); PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist); void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis); Node* find_inst_mem(Node* mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist); Node* step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop); GrowableArray<MergeMemNode*> _mergemem_worklist; // List of all MergeMem nodes Node_Array _node_map; // used for bookeeping during type splitting // Used for the following purposes: // Memory Phi - most recent unique Phi split out // from this Phi // MemNode - new memory input for this node // ChecCastPP - allocation that this is a cast of // allocation - CheckCastPP of the allocation // manage entries in _node_map void set_map(Node* from, Node* to) { ideal_nodes.push(from); _node_map.map(from->_idx, to); } Node* get_map(int idx) { return _node_map[idx]; } PhiNode* get_map_phi(int idx) { Node* phi = _node_map[idx]; return (phi == NULL) ? NULL : phi->as_Phi(); } // Notify optimizer that a node has been modified void record_for_optimizer(Node *n) { _igvn->_worklist.push(n); _igvn->add_users_to_worklist(n); } // Compute the escape information bool compute_escape(); public: ConnectionGraph(Compile *C, PhaseIterGVN *igvn); // Check for non-escaping candidates static bool has_candidates(Compile *C); // Perform escape analysis static void do_analysis(Compile *C, PhaseIterGVN *igvn); bool not_global_escape(Node *n); #ifndef PRODUCT void dump(GrowableArray<PointsToNode*>& ptnodes_worklist); #endif }; #endif // SHARE_VM_OPTO_ESCAPE_HPP