Mercurial > hg > graal-compiler
view src/share/vm/opto/escape.hpp @ 4836:d30fa85f9994
6484965: G1: piggy-back liveness accounting phase on marking
Summary: Remove the separate counting phase of concurrent marking by tracking the amount of marked bytes and the cards spanned by marked objects in marking task/worker thread local data structures, which are updated as individual objects are marked.
Reviewed-by: brutisso, tonyp
author | johnc |
---|---|
date | Thu, 12 Jan 2012 00:06:47 -0800 |
parents | cc81b9c09bbb |
children | ee138854b3a6 |
line wrap: on
line source
/* * Copyright (c) 2005, 2011, 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 Type; class TypePtr; class VectorSet; class PointsToNode { friend class ConnectionGraph; public: typedef enum { UnknownType = 0, JavaObject = 1, LocalVar = 2, Field = 3 } 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 { UnknownEdge = 0, PointsToEdge = 1, DeferredEdge = 2, FieldEdge = 3 } EdgeType; private: enum { EdgeMask = 3, EdgeShift = 2, INITIAL_EDGE_COUNT = 4 }; NodeType _type; EscapeState _escape; GrowableArray<uint>* _edges; // outgoing edges Node* _node; // Ideal node corresponding to this PointsTo node. int _offset; // Object fields offsets. bool _scalar_replaceable; // Not escaped object could be replaced with scalar bool _has_unknown_ptr; // Has edge to phantom_object public: PointsToNode(): _type(UnknownType), _escape(UnknownEscape), _edges(NULL), _node(NULL), _offset(-1), _has_unknown_ptr(false), _scalar_replaceable(true) {} EscapeState escape_state() const { return _escape; } NodeType node_type() const { return _type;} int offset() { return _offset;} bool scalar_replaceable() { return _scalar_replaceable;} bool has_unknown_ptr() { return _has_unknown_ptr;} void set_offset(int offs) { _offset = offs;} void set_escape_state(EscapeState state) { _escape = state; } void set_node_type(NodeType ntype) { assert(_type == UnknownType || _type == ntype, "Can't change node type"); _type = ntype; } void set_scalar_replaceable(bool v) { _scalar_replaceable = v; } void set_has_unknown_ptr() { _has_unknown_ptr = true; } // count of outgoing edges uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); } // node index of target of outgoing edge "e" uint edge_target(uint e) const { assert(_edges != NULL, "valid edge index"); return (_edges->at(e) >> EdgeShift); } // type of outgoing edge "e" EdgeType edge_type(uint e) const { assert(_edges != NULL, "valid edge index"); return (EdgeType) (_edges->at(e) & EdgeMask); } // add a edge of the specified type pointing to the specified target void add_edge(uint targIdx, EdgeType et); // remove an edge of the specified type pointing to the specified target void remove_edge(uint targIdx, EdgeType et); #ifndef PRODUCT void dump(bool print_state=true) const; #endif }; class ConnectionGraph: public ResourceObj { private: GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed // by ideal node index. Unique_Node_List _delayed_worklist; // Nodes to be processed before // the call build_connection_graph(). GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes VectorSet _processed; // Records which nodes have been // processed. bool _collecting; // Indicates whether escape information // is still being collected. If false, // no new nodes will be processed. bool _progress; // Indicates whether new Graph's edges // were created. uint _phantom_object; // Index of globally escaping object // that pointer values loaded from // a field which has not been set // are assumed to point to. uint _oop_null; // ConP(#NULL)->_idx uint _noop_null; // ConN(#NULL)->_idx Node* _pcmp_neq; // ConI(#CC_GT) Node* _pcmp_eq; // ConI(#CC_EQ) Compile * _compile; // Compile object for current compilation PhaseIterGVN * _igvn; // Value numbering // Address of an element in _nodes. Used when the element is to be modified PointsToNode *ptnode_adr(uint idx) const { // There should be no new ideal nodes during ConnectionGraph build, // growableArray::adr_at() will throw assert otherwise. return _nodes.adr_at(idx); } uint nodes_size() const { return _nodes.length(); } bool is_null_ptr(uint idx) const { return (idx == _noop_null || idx == _oop_null); } // Add node to ConnectionGraph. void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); // offset of a field reference int address_offset(Node* adr, PhaseTransform *phase); // compute the escape state for arguments to a call void process_call_arguments(CallNode *call, PhaseTransform *phase); // compute the escape state for the return value of a call void process_call_result(ProjNode *resproj, PhaseTransform *phase); // Populate Connection Graph with Ideal nodes. void record_for_escape_analysis(Node *n, PhaseTransform *phase); // Build Connection Graph and set nodes escape state. void build_connection_graph(Node *n, PhaseTransform *phase); // walk the connection graph starting at the node corresponding to "n" and // add the index of everything it could point to, to "ptset". This may cause // Phi's encountered to get (re)processed (which requires "phase".) VectorSet* PointsTo(Node * n); // Reused structures for PointsTo(). VectorSet pt_ptset; VectorSet pt_visited; GrowableArray<uint> pt_worklist; // Edge manipulation. The "from_i" and "to_i" arguments are the // node indices of the source and destination of the edge void add_pointsto_edge(uint from_i, uint to_i); void add_deferred_edge(uint from_i, uint to_i); void add_field_edge(uint from_i, uint to_i, int offs); // Add an edge of the specified type pointing to the specified target. // Set _progress if new edge is added. void add_edge(PointsToNode *f, uint to_i, PointsToNode::EdgeType et) { uint e_cnt = f->edge_count(); f->add_edge(to_i, et); _progress |= (f->edge_count() != e_cnt); } // Add an edge to node given by "to_i" from any field of adr_i whose offset // matches "offset" A deferred edge is added if to_i is a LocalVar, and // a pointsto edge is added if it is a JavaObject void add_edge_from_fields(uint adr, uint to_i, int offs); // Add a deferred edge from node given by "from_i" to any field // of adr_i whose offset matches "offset" void add_deferred_edge_to_fields(uint from_i, uint adr, int offs); // Remove outgoing deferred edges from the node referenced by "ni". // Any outgoing edges from the target of the deferred edge are copied // to "ni". void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited); 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 bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn); PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created); PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *igvn); Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); // Propagate unique types created for unescaped allocated objects // through the graph void split_unique_types(GrowableArray<Node *> &alloc_worklist); // manage entries in _node_map void set_map(int idx, Node *n) { _node_map.map(idx, n); } 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); } // Set the escape state of a node void set_escape_state(uint ni, PointsToNode::EscapeState es); // Find fields initializing values for allocations. void find_init_values(Node* n, VectorSet* visited, PhaseTransform* phase); // Adjust escape state after Connection Graph is built. void adjust_escape_state(Node* n); // Propagate escape states to referenced nodes. bool propagate_escape_state(GrowableArray<int>* cg_worklist, GrowableArray<uint>* worklist, PointsToNode::EscapeState esc_state); // Optimize objects compare. Node* optimize_ptr_compare(Node* 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); // escape state of a node PointsToNode::EscapeState escape_state(Node *n); #ifndef PRODUCT void dump(); #endif }; #endif // SHARE_VM_OPTO_ESCAPE_HPP