--- a/hotspot/src/share/vm/opto/escape.hpp Thu Mar 13 16:31:32 2008 -0700
+++ b/hotspot/src/share/vm/opto/escape.hpp Fri Mar 14 15:26:33 2008 -0700
@@ -25,14 +25,15 @@
//
// 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
+// [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:
+// 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)
@@ -40,47 +41,51 @@
//
// The CG contains 3 types of edges:
//
-// - PointsTo (-P>) {LV,OF} to JO
-// - Deferred (-D>) from {LV, OF} to {LV, OF}
+// - 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.
+// 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:
+// 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
+// (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.
+// 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
+// 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
+// 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:
+// The following node types are JavaObject:
//
// top()
// Allocate
// AllocateArray
// Parm (for incoming arguments)
+// CastX2P ("unsafe" operations)
// CreateEx
// ConP
// LoadKlass
+// ThreadLocal
//
// AddP nodes are fields.
//
@@ -89,7 +94,7 @@
// source. This results in a graph with no deferred edges, only:
//
// LV -P> JO
-// OF -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
@@ -110,17 +115,18 @@
friend class ConnectionGraph;
public:
typedef enum {
- UnknownType = 0,
- JavaObject = 1,
- LocalVar = 2,
- Field = 3
+ UnknownType = 0,
+ JavaObject = 1,
+ LocalVar = 2,
+ Field = 3
} NodeType;
typedef enum {
UnknownEscape = 0,
- NoEscape = 1,
- ArgEscape = 2,
- GlobalEscape = 3
+ 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 {
@@ -140,18 +146,24 @@
NodeType _type;
EscapeState _escape;
- GrowableArray<uint>* _edges; // outgoing edges
- int _offset; // for fields
+ GrowableArray<uint>* _edges; // outgoing edges
- 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
+ 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) {}
- 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;}
@@ -182,22 +194,28 @@
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 _delayed_worklist; // Nodes to be processed before
+ // the call build_connection_graph().
+
+ VectorSet _processed; // Records which nodes have been
+ // processed.
- 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
+ bool _collecting; // Indicates whether escape information
+ // is still being collected. If false,
+ // no new nodes will be processed.
+
+ bool _has_allocations; // Indicates whether method has any
+ // non-escaping allocations.
+
+ 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) {
@@ -208,8 +226,11 @@
return _nodes->adr_at(idx);
}
+ // Add node to ConnectionGraph.
+ void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);
+
// offset of a field reference
- int type_to_offset(const Type *t);
+ int address_offset(Node* adr, PhaseTransform *phase);
// compute the escape state for arguments to a call
void process_call_arguments(CallNode *call, PhaseTransform *phase);
@@ -217,12 +238,11 @@
// 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);
+ // Populate Connection Graph with Ideal nodes.
+ void record_for_escape_analysis(Node *n, PhaseTransform *phase);
- // compute the escape state of an ideal node.
- void record_escape_work(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
@@ -241,8 +261,8 @@
// 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"
+ // 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);
@@ -262,6 +282,8 @@
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);
@@ -285,26 +307,24 @@
// 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
+ // Compute the escape information
void 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)
+ return false;
+ PointsToNode ptn = _nodes->at_grow(n->_idx);
+ return ptn.escape_state() == PointsToNode::NoEscape && ptn._scalar_replaceable;
+ }
bool hidden_alias(Node *n) {
if (_collecting)