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