| /* |
| * Copyright 2005-2008 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| * CA 95054 USA or visit www.sun.com if you need additional information or |
| * have any questions. |
| * |
| */ |
| |
| // |
| // 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 |
| // 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: |
| // |
| // top() |
| // Allocate |
| // AllocateArray |
| // Parm (for incoming arguments) |
| // CastX2P ("unsafe" operations) |
| // CreateEx |
| // ConP |
| // LoadKlass |
| // ThreadLocal |
| // |
| // 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, // A scalar replaceable object with unique type. |
| ArgEscape = 2, // An object passed as argument or referenced by |
| // argument (and not globally escape during call). |
| GlobalEscape = 3 // An object escapes the method and 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 |
| |
| public: |
| 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 _hidden_alias; // This node is an argument to a function. |
| // which may return it creating a hidden alias. |
| |
| PointsToNode(): |
| _type(UnknownType), |
| _escape(UnknownEscape), |
| _edges(NULL), |
| _node(NULL), |
| _offset(-1), |
| _scalar_replaceable(true), |
| _hidden_alias(false) {} |
| |
| |
| EscapeState escape_state() const { return _escape; } |
| NodeType node_type() const { return _type;} |
| int offset() { return _offset;} |
| |
| 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; |
| } |
| |
| // 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(). |
| |
| 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. |
| |
| 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) |
| uint _noop_null; // ConN(#NULL) |
| |
| Compile * _compile; // Compile object for current compilation |
| |
| // 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(); } |
| |
| // 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".) |
| void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase); |
| |
| // 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 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 |
| void 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); |
| Node *find_mem(Node *mem, int alias_idx, 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); } |
| void set_map_phi(int idx, PhiNode *p) { _node_map.map(idx, (Node *) p); } |
| 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 |
| // Node: This assumes that escape analysis is run before |
| // PhaseIterGVN creation |
| void record_for_optimizer(Node *n) { |
| _compile->record_for_igvn(n); |
| } |
| |
| // Set the escape state of a node |
| void set_escape_state(uint ni, PointsToNode::EscapeState es); |
| |
| public: |
| ConnectionGraph(Compile *C); |
| |
| // Check for non-escaping candidates |
| static bool has_candidates(Compile *C); |
| |
| // Compute the escape information |
| bool compute_escape(); |
| |
| // escape state of a node |
| PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase); |
| // other information we have collected |
| bool is_scalar_replaceable(Node *n) { |
| if (_collecting || (n->_idx >= nodes_size())) |
| return false; |
| PointsToNode* ptn = ptnode_adr(n->_idx); |
| return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable; |
| } |
| |
| bool hidden_alias(Node *n) { |
| if (_collecting || (n->_idx >= nodes_size())) |
| return true; |
| PointsToNode* ptn = ptnode_adr(n->_idx); |
| return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias; |
| } |
| |
| #ifndef PRODUCT |
| void dump(); |
| #endif |
| }; |