duke@435: /* kvn@2556: * Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. duke@435: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@435: * duke@435: * This code is free software; you can redistribute it and/or modify it duke@435: * under the terms of the GNU General Public License version 2 only, as duke@435: * published by the Free Software Foundation. duke@435: * duke@435: * This code is distributed in the hope that it will be useful, but WITHOUT duke@435: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@435: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@435: * version 2 for more details (a copy is included in the LICENSE file that duke@435: * accompanied this code). duke@435: * duke@435: * You should have received a copy of the GNU General Public License version duke@435: * 2 along with this work; if not, write to the Free Software Foundation, duke@435: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@435: * trims@1907: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA trims@1907: * or visit www.oracle.com if you need additional information or have any trims@1907: * questions. duke@435: * duke@435: */ duke@435: stefank@2314: #ifndef SHARE_VM_OPTO_ESCAPE_HPP stefank@2314: #define SHARE_VM_OPTO_ESCAPE_HPP stefank@2314: stefank@2314: #include "opto/addnode.hpp" stefank@2314: #include "opto/node.hpp" stefank@2314: #include "utilities/growableArray.hpp" stefank@2314: duke@435: // duke@435: // Adaptation for C2 of the escape analysis algorithm described in: duke@435: // kvn@500: // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, kvn@500: // Vugranam C. Sreedhar, Sam Midkiff, kvn@500: // "Escape Analysis for Java", Procedings of ACM SIGPLAN kvn@500: // OOPSLA Conference, November 1, 1999 duke@435: // duke@435: // The flow-insensitive analysis described in the paper has been implemented. duke@435: // kvn@500: // The analysis requires construction of a "connection graph" (CG) for kvn@500: // the method being analyzed. The nodes of the connection graph are: duke@435: // duke@435: // - Java objects (JO) duke@435: // - Local variables (LV) duke@435: // - Fields of an object (OF), these also include array elements duke@435: // duke@435: // The CG contains 3 types of edges: duke@435: // kvn@500: // - PointsTo (-P>) {LV, OF} to JO kvn@500: // - Deferred (-D>) from {LV, OF} to {LV, OF} duke@435: // - Field (-F>) from JO to OF duke@435: // duke@435: // The following utility functions is used by the algorithm: duke@435: // kvn@500: // PointsTo(n) - n is any CG node, it returns the set of JO that n could kvn@500: // point to. duke@435: // kvn@500: // The algorithm describes how to construct the connection graph kvn@500: // in the following 4 cases: duke@435: // duke@435: // Case Edges Created duke@435: // kvn@500: // (1) p = new T() LV -P> JO kvn@500: // (2) p = q LV -D> LV kvn@500: // (3) p.f = q JO -F> OF, OF -D> LV kvn@500: // (4) p = q.f JO -F> OF, LV -D> OF duke@435: // kvn@500: // In all these cases, p and q are local variables. For static field kvn@500: // references, we can construct a local variable containing a reference kvn@500: // to the static memory. duke@435: // duke@435: // C2 does not have local variables. However for the purposes of constructing duke@435: // the connection graph, the following IR nodes are treated as local variables: duke@435: // Phi (pointer values) kvn@3254: // LoadP, LoadN kvn@500: // Proj#5 (value returned from callnodes including allocations) kvn@500: // CheckCastPP, CastPP duke@435: // kvn@500: // The LoadP, Proj and CheckCastPP behave like variables assigned to only once. kvn@500: // Only a Phi can have multiple assignments. Each input to a Phi is treated duke@435: // as an assignment to it. duke@435: // kvn@500: // The following node types are JavaObject: duke@435: // kvn@3254: // phantom_object (general globally escaped object) duke@435: // Allocate duke@435: // AllocateArray duke@435: // Parm (for incoming arguments) kvn@500: // CastX2P ("unsafe" operations) duke@435: // CreateEx duke@435: // ConP duke@435: // LoadKlass kvn@500: // ThreadLocal kvn@3254: // CallStaticJava (which returns Object) duke@435: // duke@435: // AddP nodes are fields. duke@435: // duke@435: // After building the graph, a pass is made over the nodes, deleting deferred duke@435: // nodes and copying the edges from the target of the deferred edge to the duke@435: // source. This results in a graph with no deferred edges, only: duke@435: // duke@435: // LV -P> JO kvn@500: // OF -P> JO (the object whose oop is stored in the field) duke@435: // JO -F> OF duke@435: // duke@435: // Then, for each node which is GlobalEscape, anything it could point to duke@435: // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything duke@435: // it could point to is marked ArgEscape. duke@435: // duke@435: duke@435: class Compile; duke@435: class Node; duke@435: class CallNode; duke@435: class PhiNode; duke@435: class PhaseTransform; duke@435: class Type; duke@435: class TypePtr; duke@435: class VectorSet; duke@435: duke@435: class PointsToNode { duke@435: friend class ConnectionGraph; duke@435: public: duke@435: typedef enum { kvn@500: UnknownType = 0, kvn@500: JavaObject = 1, kvn@500: LocalVar = 2, kvn@500: Field = 3 duke@435: } NodeType; duke@435: duke@435: typedef enum { duke@435: UnknownEscape = 0, kvn@3254: NoEscape = 1, // An object does not escape method or thread and it is kvn@3254: // not passed to call. It could be replaced with scalar. kvn@3254: ArgEscape = 2, // An object does not escape method or thread but it is kvn@3254: // passed as argument to call or referenced by argument kvn@3254: // and it does not escape during call. kvn@3254: GlobalEscape = 3 // An object escapes the method or thread. duke@435: } EscapeState; duke@435: duke@435: typedef enum { duke@435: UnknownEdge = 0, duke@435: PointsToEdge = 1, duke@435: DeferredEdge = 2, duke@435: FieldEdge = 3 duke@435: } EdgeType; duke@435: duke@435: private: duke@435: enum { duke@435: EdgeMask = 3, duke@435: EdgeShift = 2, duke@435: duke@435: INITIAL_EDGE_COUNT = 4 duke@435: }; duke@435: duke@435: NodeType _type; duke@435: EscapeState _escape; kvn@3254: GrowableArray* _edges; // outgoing edges kvn@3254: Node* _node; // Ideal node corresponding to this PointsTo node. kvn@3254: int _offset; // Object fields offsets. kvn@3254: bool _scalar_replaceable; // Not escaped object could be replaced with scalar duke@435: duke@435: public: kvn@500: PointsToNode(): kvn@500: _type(UnknownType), kvn@500: _escape(UnknownEscape), kvn@500: _edges(NULL), kvn@500: _node(NULL), kvn@500: _offset(-1), kvn@3254: _scalar_replaceable(true) {} duke@435: duke@435: duke@435: EscapeState escape_state() const { return _escape; } duke@435: NodeType node_type() const { return _type;} duke@435: int offset() { return _offset;} kvn@3254: bool scalar_replaceable() { return _scalar_replaceable;} duke@435: duke@435: void set_offset(int offs) { _offset = offs;} duke@435: void set_escape_state(EscapeState state) { _escape = state; } duke@435: void set_node_type(NodeType ntype) { duke@435: assert(_type == UnknownType || _type == ntype, "Can't change node type"); duke@435: _type = ntype; duke@435: } kvn@3254: void set_scalar_replaceable(bool v) { _scalar_replaceable = v; } duke@435: duke@435: // count of outgoing edges duke@435: uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); } kvn@679: duke@435: // node index of target of outgoing edge "e" kvn@679: uint edge_target(uint e) const { kvn@679: assert(_edges != NULL, "valid edge index"); kvn@679: return (_edges->at(e) >> EdgeShift); kvn@679: } duke@435: // type of outgoing edge "e" kvn@679: EdgeType edge_type(uint e) const { kvn@679: assert(_edges != NULL, "valid edge index"); kvn@679: return (EdgeType) (_edges->at(e) & EdgeMask); kvn@679: } kvn@679: duke@435: // add a edge of the specified type pointing to the specified target duke@435: void add_edge(uint targIdx, EdgeType et); kvn@679: duke@435: // remove an edge of the specified type pointing to the specified target duke@435: void remove_edge(uint targIdx, EdgeType et); kvn@679: duke@435: #ifndef PRODUCT kvn@688: void dump(bool print_state=true) const; duke@435: #endif duke@435: duke@435: }; duke@435: duke@435: class ConnectionGraph: public ResourceObj { duke@435: private: kvn@679: GrowableArray _nodes; // Connection graph nodes indexed kvn@500: // by ideal node index. duke@435: kvn@500: Unique_Node_List _delayed_worklist; // Nodes to be processed before kvn@500: // the call build_connection_graph(). duke@435: kvn@1535: GrowableArray _mergemem_worklist; // List of all MergeMem nodes kvn@1535: kvn@500: VectorSet _processed; // Records which nodes have been kvn@500: // processed. kvn@500: kvn@500: bool _collecting; // Indicates whether escape information kvn@500: // is still being collected. If false, kvn@500: // no new nodes will be processed. kvn@500: kvn@2276: bool _progress; // Indicates whether new Graph's edges kvn@2276: // were created. kvn@2276: kvn@500: uint _phantom_object; // Index of globally escaping object kvn@500: // that pointer values loaded from kvn@500: // a field which has not been set kvn@500: // are assumed to point to. kvn@3254: uint _oop_null; // ConP(#NULL)->_idx kvn@3254: uint _noop_null; // ConN(#NULL)->_idx kvn@500: kvn@500: Compile * _compile; // Compile object for current compilation kvn@1989: PhaseIterGVN * _igvn; // Value numbering duke@435: kvn@679: // Address of an element in _nodes. Used when the element is to be modified kvn@679: PointsToNode *ptnode_adr(uint idx) const { kvn@679: // There should be no new ideal nodes during ConnectionGraph build, kvn@679: // growableArray::adr_at() will throw assert otherwise. kvn@679: return _nodes.adr_at(idx); duke@435: } kvn@679: uint nodes_size() const { return _nodes.length(); } duke@435: kvn@500: // Add node to ConnectionGraph. kvn@500: void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); kvn@500: duke@435: // offset of a field reference kvn@500: int address_offset(Node* adr, PhaseTransform *phase); duke@435: duke@435: // compute the escape state for arguments to a call duke@435: void process_call_arguments(CallNode *call, PhaseTransform *phase); duke@435: duke@435: // compute the escape state for the return value of a call duke@435: void process_call_result(ProjNode *resproj, PhaseTransform *phase); duke@435: kvn@500: // Populate Connection Graph with Ideal nodes. kvn@500: void record_for_escape_analysis(Node *n, PhaseTransform *phase); duke@435: kvn@500: // Build Connection Graph and set nodes escape state. kvn@500: void build_connection_graph(Node *n, PhaseTransform *phase); duke@435: duke@435: // walk the connection graph starting at the node corresponding to "n" and duke@435: // add the index of everything it could point to, to "ptset". This may cause duke@435: // Phi's encountered to get (re)processed (which requires "phase".) kvn@2556: VectorSet* PointsTo(Node * n); kvn@2556: kvn@2556: // Reused structures for PointsTo(). kvn@2556: VectorSet pt_ptset; kvn@2556: VectorSet pt_visited; kvn@2556: GrowableArray pt_worklist; duke@435: duke@435: // Edge manipulation. The "from_i" and "to_i" arguments are the duke@435: // node indices of the source and destination of the edge duke@435: void add_pointsto_edge(uint from_i, uint to_i); duke@435: void add_deferred_edge(uint from_i, uint to_i); duke@435: void add_field_edge(uint from_i, uint to_i, int offs); duke@435: kvn@2276: // Add an edge of the specified type pointing to the specified target. kvn@2276: // Set _progress if new edge is added. kvn@2276: void add_edge(PointsToNode *f, uint to_i, PointsToNode::EdgeType et) { kvn@2276: uint e_cnt = f->edge_count(); kvn@2276: f->add_edge(to_i, et); kvn@2276: _progress |= (f->edge_count() != e_cnt); kvn@2276: } duke@435: duke@435: // Add an edge to node given by "to_i" from any field of adr_i whose offset duke@435: // matches "offset" A deferred edge is added if to_i is a LocalVar, and duke@435: // a pointsto edge is added if it is a JavaObject duke@435: void add_edge_from_fields(uint adr, uint to_i, int offs); duke@435: kvn@500: // Add a deferred edge from node given by "from_i" to any field kvn@500: // of adr_i whose offset matches "offset" duke@435: void add_deferred_edge_to_fields(uint from_i, uint adr, int offs); duke@435: duke@435: duke@435: // Remove outgoing deferred edges from the node referenced by "ni". duke@435: // Any outgoing edges from the target of the deferred edge are copied duke@435: // to "ni". kvn@536: void remove_deferred(uint ni, GrowableArray* deferred_edges, VectorSet* visited); duke@435: duke@435: Node_Array _node_map; // used for bookeeping during type splitting duke@435: // Used for the following purposes: duke@435: // Memory Phi - most recent unique Phi split out duke@435: // from this Phi duke@435: // MemNode - new memory input for this node duke@435: // ChecCastPP - allocation that this is a cast of duke@435: // allocation - CheckCastPP of the allocation kvn@728: bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn); duke@435: PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray &orig_phi_worklist, PhaseGVN *igvn, bool &new_created); duke@435: PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray &orig_phi_worklist, PhaseGVN *igvn); kvn@1536: void move_inst_mem(Node* n, GrowableArray &orig_phis, PhaseGVN *igvn); kvn@500: Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray &orig_phi_worklist, PhaseGVN *igvn); kvn@500: duke@435: // Propagate unique types created for unescaped allocated objects duke@435: // through the graph duke@435: void split_unique_types(GrowableArray &alloc_worklist); duke@435: duke@435: // manage entries in _node_map duke@435: void set_map(int idx, Node *n) { _node_map.map(idx, n); } duke@435: Node *get_map(int idx) { return _node_map[idx]; } duke@435: PhiNode *get_map_phi(int idx) { duke@435: Node *phi = _node_map[idx]; duke@435: return (phi == NULL) ? NULL : phi->as_Phi(); duke@435: } duke@435: duke@435: // Notify optimizer that a node has been modified duke@435: // Node: This assumes that escape analysis is run before duke@435: // PhaseIterGVN creation duke@435: void record_for_optimizer(Node *n) { kvn@1989: _igvn->_worklist.push(n); duke@435: } duke@435: duke@435: // Set the escape state of a node duke@435: void set_escape_state(uint ni, PointsToNode::EscapeState es); duke@435: kvn@3254: // Find fields initializing values for allocations. kvn@3254: void find_init_values(Node* n, VectorSet* visited, PhaseTransform* phase); kvn@3254: kvn@2556: // Adjust escape state after Connection Graph is built. kvn@3254: void adjust_escape_state(Node* n); kvn@3254: kvn@3254: // Propagate escape states to referenced nodes. kvn@3254: bool propagate_escape_state(GrowableArray* cg_worklist, kvn@3254: GrowableArray* worklist, kvn@3254: PointsToNode::EscapeState esc_state); kvn@2556: kvn@2556: // Compute the escape information kvn@2556: bool compute_escape(); kvn@1535: duke@435: public: kvn@1989: ConnectionGraph(Compile *C, PhaseIterGVN *igvn); duke@435: kvn@679: // Check for non-escaping candidates kvn@679: static bool has_candidates(Compile *C); kvn@679: kvn@1989: // Perform escape analysis kvn@1989: static void do_analysis(Compile *C, PhaseIterGVN *igvn); kvn@1989: duke@435: // escape state of a node kvn@1989: PointsToNode::EscapeState escape_state(Node *n); kvn@1989: duke@435: #ifndef PRODUCT duke@435: void dump(); duke@435: #endif duke@435: }; stefank@2314: stefank@2314: #endif // SHARE_VM_OPTO_ESCAPE_HPP