Thu, 12 Mar 2009 18:16:36 -0700
Merge
1 /*
2 * Copyright 2005-2008 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
25 //
26 // Adaptation for C2 of the escape analysis algorithm described in:
27 //
28 // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
29 // Vugranam C. Sreedhar, Sam Midkiff,
30 // "Escape Analysis for Java", Procedings of ACM SIGPLAN
31 // OOPSLA Conference, November 1, 1999
32 //
33 // The flow-insensitive analysis described in the paper has been implemented.
34 //
35 // The analysis requires construction of a "connection graph" (CG) for
36 // the method being analyzed. The nodes of the connection graph are:
37 //
38 // - Java objects (JO)
39 // - Local variables (LV)
40 // - Fields of an object (OF), these also include array elements
41 //
42 // The CG contains 3 types of edges:
43 //
44 // - PointsTo (-P>) {LV, OF} to JO
45 // - Deferred (-D>) from {LV, OF} to {LV, OF}
46 // - Field (-F>) from JO to OF
47 //
48 // The following utility functions is used by the algorithm:
49 //
50 // PointsTo(n) - n is any CG node, it returns the set of JO that n could
51 // point to.
52 //
53 // The algorithm describes how to construct the connection graph
54 // in the following 4 cases:
55 //
56 // Case Edges Created
57 //
58 // (1) p = new T() LV -P> JO
59 // (2) p = q LV -D> LV
60 // (3) p.f = q JO -F> OF, OF -D> LV
61 // (4) p = q.f JO -F> OF, LV -D> OF
62 //
63 // In all these cases, p and q are local variables. For static field
64 // references, we can construct a local variable containing a reference
65 // to the static memory.
66 //
67 // C2 does not have local variables. However for the purposes of constructing
68 // the connection graph, the following IR nodes are treated as local variables:
69 // Phi (pointer values)
70 // LoadP
71 // Proj#5 (value returned from callnodes including allocations)
72 // CheckCastPP, CastPP
73 //
74 // The LoadP, Proj and CheckCastPP behave like variables assigned to only once.
75 // Only a Phi can have multiple assignments. Each input to a Phi is treated
76 // as an assignment to it.
77 //
78 // The following node types are JavaObject:
79 //
80 // top()
81 // Allocate
82 // AllocateArray
83 // Parm (for incoming arguments)
84 // CastX2P ("unsafe" operations)
85 // CreateEx
86 // ConP
87 // LoadKlass
88 // ThreadLocal
89 //
90 // AddP nodes are fields.
91 //
92 // After building the graph, a pass is made over the nodes, deleting deferred
93 // nodes and copying the edges from the target of the deferred edge to the
94 // source. This results in a graph with no deferred edges, only:
95 //
96 // LV -P> JO
97 // OF -P> JO (the object whose oop is stored in the field)
98 // JO -F> OF
99 //
100 // Then, for each node which is GlobalEscape, anything it could point to
101 // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything
102 // it could point to is marked ArgEscape.
103 //
105 class Compile;
106 class Node;
107 class CallNode;
108 class PhiNode;
109 class PhaseTransform;
110 class Type;
111 class TypePtr;
112 class VectorSet;
114 class PointsToNode {
115 friend class ConnectionGraph;
116 public:
117 typedef enum {
118 UnknownType = 0,
119 JavaObject = 1,
120 LocalVar = 2,
121 Field = 3
122 } NodeType;
124 typedef enum {
125 UnknownEscape = 0,
126 NoEscape = 1, // A scalar replaceable object with unique type.
127 ArgEscape = 2, // An object passed as argument or referenced by
128 // argument (and not globally escape during call).
129 GlobalEscape = 3 // An object escapes the method and thread.
130 } EscapeState;
132 typedef enum {
133 UnknownEdge = 0,
134 PointsToEdge = 1,
135 DeferredEdge = 2,
136 FieldEdge = 3
137 } EdgeType;
139 private:
140 enum {
141 EdgeMask = 3,
142 EdgeShift = 2,
144 INITIAL_EDGE_COUNT = 4
145 };
147 NodeType _type;
148 EscapeState _escape;
149 GrowableArray<uint>* _edges; // outgoing edges
151 public:
152 Node* _node; // Ideal node corresponding to this PointsTo node.
153 int _offset; // Object fields offsets.
154 bool _scalar_replaceable;// Not escaped object could be replaced with scalar
155 bool _hidden_alias; // This node is an argument to a function.
156 // which may return it creating a hidden alias.
158 PointsToNode():
159 _type(UnknownType),
160 _escape(UnknownEscape),
161 _edges(NULL),
162 _node(NULL),
163 _offset(-1),
164 _scalar_replaceable(true),
165 _hidden_alias(false) {}
168 EscapeState escape_state() const { return _escape; }
169 NodeType node_type() const { return _type;}
170 int offset() { return _offset;}
172 void set_offset(int offs) { _offset = offs;}
173 void set_escape_state(EscapeState state) { _escape = state; }
174 void set_node_type(NodeType ntype) {
175 assert(_type == UnknownType || _type == ntype, "Can't change node type");
176 _type = ntype;
177 }
179 // count of outgoing edges
180 uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }
182 // node index of target of outgoing edge "e"
183 uint edge_target(uint e) const {
184 assert(_edges != NULL, "valid edge index");
185 return (_edges->at(e) >> EdgeShift);
186 }
187 // type of outgoing edge "e"
188 EdgeType edge_type(uint e) const {
189 assert(_edges != NULL, "valid edge index");
190 return (EdgeType) (_edges->at(e) & EdgeMask);
191 }
193 // add a edge of the specified type pointing to the specified target
194 void add_edge(uint targIdx, EdgeType et);
196 // remove an edge of the specified type pointing to the specified target
197 void remove_edge(uint targIdx, EdgeType et);
199 #ifndef PRODUCT
200 void dump(bool print_state=true) const;
201 #endif
203 };
205 class ConnectionGraph: public ResourceObj {
206 private:
207 GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed
208 // by ideal node index.
210 Unique_Node_List _delayed_worklist; // Nodes to be processed before
211 // the call build_connection_graph().
213 VectorSet _processed; // Records which nodes have been
214 // processed.
216 bool _collecting; // Indicates whether escape information
217 // is still being collected. If false,
218 // no new nodes will be processed.
220 uint _phantom_object; // Index of globally escaping object
221 // that pointer values loaded from
222 // a field which has not been set
223 // are assumed to point to.
224 uint _oop_null; // ConP(#NULL)
225 uint _noop_null; // ConN(#NULL)
227 Compile * _compile; // Compile object for current compilation
229 // Address of an element in _nodes. Used when the element is to be modified
230 PointsToNode *ptnode_adr(uint idx) const {
231 // There should be no new ideal nodes during ConnectionGraph build,
232 // growableArray::adr_at() will throw assert otherwise.
233 return _nodes.adr_at(idx);
234 }
235 uint nodes_size() const { return _nodes.length(); }
237 // Add node to ConnectionGraph.
238 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);
240 // offset of a field reference
241 int address_offset(Node* adr, PhaseTransform *phase);
243 // compute the escape state for arguments to a call
244 void process_call_arguments(CallNode *call, PhaseTransform *phase);
246 // compute the escape state for the return value of a call
247 void process_call_result(ProjNode *resproj, PhaseTransform *phase);
249 // Populate Connection Graph with Ideal nodes.
250 void record_for_escape_analysis(Node *n, PhaseTransform *phase);
252 // Build Connection Graph and set nodes escape state.
253 void build_connection_graph(Node *n, PhaseTransform *phase);
255 // walk the connection graph starting at the node corresponding to "n" and
256 // add the index of everything it could point to, to "ptset". This may cause
257 // Phi's encountered to get (re)processed (which requires "phase".)
258 void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase);
260 // Edge manipulation. The "from_i" and "to_i" arguments are the
261 // node indices of the source and destination of the edge
262 void add_pointsto_edge(uint from_i, uint to_i);
263 void add_deferred_edge(uint from_i, uint to_i);
264 void add_field_edge(uint from_i, uint to_i, int offs);
267 // Add an edge to node given by "to_i" from any field of adr_i whose offset
268 // matches "offset" A deferred edge is added if to_i is a LocalVar, and
269 // a pointsto edge is added if it is a JavaObject
270 void add_edge_from_fields(uint adr, uint to_i, int offs);
272 // Add a deferred edge from node given by "from_i" to any field
273 // of adr_i whose offset matches "offset"
274 void add_deferred_edge_to_fields(uint from_i, uint adr, int offs);
277 // Remove outgoing deferred edges from the node referenced by "ni".
278 // Any outgoing edges from the target of the deferred edge are copied
279 // to "ni".
280 void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited);
282 Node_Array _node_map; // used for bookeeping during type splitting
283 // Used for the following purposes:
284 // Memory Phi - most recent unique Phi split out
285 // from this Phi
286 // MemNode - new memory input for this node
287 // ChecCastPP - allocation that this is a cast of
288 // allocation - CheckCastPP of the allocation
289 bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn);
290 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created);
291 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn);
292 Node *find_mem(Node *mem, int alias_idx, PhaseGVN *igvn);
293 Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn);
295 // Propagate unique types created for unescaped allocated objects
296 // through the graph
297 void split_unique_types(GrowableArray<Node *> &alloc_worklist);
299 // manage entries in _node_map
300 void set_map(int idx, Node *n) { _node_map.map(idx, n); }
301 void set_map_phi(int idx, PhiNode *p) { _node_map.map(idx, (Node *) p); }
302 Node *get_map(int idx) { return _node_map[idx]; }
303 PhiNode *get_map_phi(int idx) {
304 Node *phi = _node_map[idx];
305 return (phi == NULL) ? NULL : phi->as_Phi();
306 }
308 // Notify optimizer that a node has been modified
309 // Node: This assumes that escape analysis is run before
310 // PhaseIterGVN creation
311 void record_for_optimizer(Node *n) {
312 _compile->record_for_igvn(n);
313 }
315 // Set the escape state of a node
316 void set_escape_state(uint ni, PointsToNode::EscapeState es);
318 public:
319 ConnectionGraph(Compile *C);
321 // Check for non-escaping candidates
322 static bool has_candidates(Compile *C);
324 // Compute the escape information
325 bool compute_escape();
327 // escape state of a node
328 PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase);
329 // other information we have collected
330 bool is_scalar_replaceable(Node *n) {
331 if (_collecting || (n->_idx >= nodes_size()))
332 return false;
333 PointsToNode* ptn = ptnode_adr(n->_idx);
334 return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable;
335 }
337 bool hidden_alias(Node *n) {
338 if (_collecting || (n->_idx >= nodes_size()))
339 return true;
340 PointsToNode* ptn = ptnode_adr(n->_idx);
341 return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias;
342 }
344 #ifndef PRODUCT
345 void dump();
346 #endif
347 };