--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/share/vm/opto/escape.hpp Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,319 @@
+/*
+ * Copyright 2005-2006 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 (value returned from callnodes including allocations)
+// CheckCastPP
+//
+// 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 note types are JavaObject:
+//
+// top()
+// Allocate
+// AllocateArray
+// Parm (for incoming arguments)
+// CreateEx
+// ConP
+// LoadKlass
+//
+// 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
+// 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,
+ ArgEscape = 2,
+ GlobalEscape = 3
+ } 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
+ int _offset; // for fields
+
+ bool _unique_type; // For allocated objects, this node may be a unique type
+public:
+ Node* _node; // Ideal node corresponding to this PointsTo node
+ int _inputs_processed; // the number of Phi inputs that have been processed so far
+ bool _hidden_alias; // this node is an argument to a function which may return it
+ // creating a hidden alias
+
+
+ PointsToNode(): _offset(-1), _type(UnknownType), _escape(UnknownEscape), _edges(NULL), _node(NULL), _inputs_processed(0), _hidden_alias(false), _unique_type(true) {}
+
+ 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;
+ // type of outgoing edge "e"
+ EdgeType edge_type(uint e) const;
+ // 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() const;
+#endif
+
+};
+
+class ConnectionGraph: public ResourceObj {
+private:
+ enum {
+ INITIAL_NODE_COUNT = 100 // initial size of _nodes array
+ };
+
+
+ GrowableArray<PointsToNode>* _nodes; // connection graph nodes Indexed by ideal
+ // node index
+ Unique_Node_List _deferred; // Phi's to be processed after parsing
+ 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
+ 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) {
+ if ((uint)_nodes->length() <= idx) {
+ // expand _nodes array
+ PointsToNode dummy = _nodes->at_grow(idx);
+ }
+ return _nodes->adr_at(idx);
+ }
+
+ // offset of a field reference
+ int type_to_offset(const Type *t);
+
+ // 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);
+
+ // compute the escape state of a Phi. This may be called multiple
+ // times as new inputs are added to the Phi.
+ void process_phi_escape(PhiNode *phi, PhaseTransform *phase);
+
+ // compute the escape state of an ideal node.
+ void record_escape_work(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);
+
+ 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);
+ // 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);
+
+ // bypass any casts and return the node they refer to
+ Node * skip_casts(Node *n);
+
+ // Get Compile object for current compilation.
+ Compile *C() const { return _compile; }
+
+public:
+ ConnectionGraph(Compile *C);
+
+ // record a Phi for later processing.
+ void record_for_escape_analysis(Node *n);
+
+ // process a node and fill in its connection graph node
+ void record_escape(Node *n, PhaseTransform *phase);
+
+ // All nodes have been recorded, compute the escape information
+ void compute_escape();
+
+ // escape state of a node
+ PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase);
+
+ bool hidden_alias(Node *n) {
+ if (_collecting)
+ return true;
+ PointsToNode ptn = _nodes->at_grow(n->_idx);
+ return (ptn.escape_state() != PointsToNode::NoEscape) || ptn._hidden_alias;
+ }
+
+#ifndef PRODUCT
+ void dump();
+#endif
+};