|
0
|
1 /*
|
|
|
2 * Copyright 2005-2006 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 */
|
|
|
24
|
|
|
25 //
|
|
|
26 // Adaptation for C2 of the escape analysis algorithm described in:
|
|
|
27 //
|
|
|
28 // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, Vugranam C. Sreedhar,
|
|
|
29 // Sam Midkiff, "Escape Analysis for Java", Procedings of ACM SIGPLAN
|
|
|
30 // OOPSLA Conference, November 1, 1999
|
|
|
31 //
|
|
|
32 // The flow-insensitive analysis described in the paper has been implemented.
|
|
|
33 //
|
|
|
34 // The analysis requires construction of a "connection graph" (CG) for the method being
|
|
|
35 // analyzed. The nodes of the connection graph are:
|
|
|
36 //
|
|
|
37 // - Java objects (JO)
|
|
|
38 // - Local variables (LV)
|
|
|
39 // - Fields of an object (OF), these also include array elements
|
|
|
40 //
|
|
|
41 // The CG contains 3 types of edges:
|
|
|
42 //
|
|
|
43 // - PointsTo (-P>) {LV,OF} to JO
|
|
|
44 // - Deferred (-D>) from {LV, OF} to {LV, OF}
|
|
|
45 // - Field (-F>) from JO to OF
|
|
|
46 //
|
|
|
47 // The following utility functions is used by the algorithm:
|
|
|
48 //
|
|
|
49 // PointsTo(n) - n is any CG node, it returns the set of JO that n could
|
|
|
50 // point to.
|
|
|
51 //
|
|
|
52 // The algorithm describes how to construct the connection graph in the following 4 cases:
|
|
|
53 //
|
|
|
54 // Case Edges Created
|
|
|
55 //
|
|
|
56 // (1) p = new T() LV -P> JO
|
|
|
57 // (2) p = q LV -D> LV
|
|
|
58 // (3) p.f = q JO -F> OF, OF -D> LV
|
|
|
59 // (4) p = q.f JO -F> OF, LV -D> OF
|
|
|
60 //
|
|
|
61 // In all these cases, p and q are local variables. For static field references, we can
|
|
|
62 // construct a local variable containing a reference to the static memory.
|
|
|
63 //
|
|
|
64 // C2 does not have local variables. However for the purposes of constructing
|
|
|
65 // the connection graph, the following IR nodes are treated as local variables:
|
|
|
66 // Phi (pointer values)
|
|
|
67 // LoadP
|
|
|
68 // Proj (value returned from callnodes including allocations)
|
|
|
69 // CheckCastPP
|
|
|
70 //
|
|
|
71 // The LoadP, Proj and CheckCastPP behave like variables assigned to only once. Only
|
|
|
72 // a Phi can have multiple assignments. Each input to a Phi is treated
|
|
|
73 // as an assignment to it.
|
|
|
74 //
|
|
|
75 // The following note types are JavaObject:
|
|
|
76 //
|
|
|
77 // top()
|
|
|
78 // Allocate
|
|
|
79 // AllocateArray
|
|
|
80 // Parm (for incoming arguments)
|
|
|
81 // CreateEx
|
|
|
82 // ConP
|
|
|
83 // LoadKlass
|
|
|
84 //
|
|
|
85 // AddP nodes are fields.
|
|
|
86 //
|
|
|
87 // After building the graph, a pass is made over the nodes, deleting deferred
|
|
|
88 // nodes and copying the edges from the target of the deferred edge to the
|
|
|
89 // source. This results in a graph with no deferred edges, only:
|
|
|
90 //
|
|
|
91 // LV -P> JO
|
|
|
92 // OF -P> JO
|
|
|
93 // JO -F> OF
|
|
|
94 //
|
|
|
95 // Then, for each node which is GlobalEscape, anything it could point to
|
|
|
96 // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything
|
|
|
97 // it could point to is marked ArgEscape.
|
|
|
98 //
|
|
|
99
|
|
|
100 class Compile;
|
|
|
101 class Node;
|
|
|
102 class CallNode;
|
|
|
103 class PhiNode;
|
|
|
104 class PhaseTransform;
|
|
|
105 class Type;
|
|
|
106 class TypePtr;
|
|
|
107 class VectorSet;
|
|
|
108
|
|
|
109 class PointsToNode {
|
|
|
110 friend class ConnectionGraph;
|
|
|
111 public:
|
|
|
112 typedef enum {
|
|
|
113 UnknownType = 0,
|
|
|
114 JavaObject = 1,
|
|
|
115 LocalVar = 2,
|
|
|
116 Field = 3
|
|
|
117 } NodeType;
|
|
|
118
|
|
|
119 typedef enum {
|
|
|
120 UnknownEscape = 0,
|
|
|
121 NoEscape = 1,
|
|
|
122 ArgEscape = 2,
|
|
|
123 GlobalEscape = 3
|
|
|
124 } EscapeState;
|
|
|
125
|
|
|
126 typedef enum {
|
|
|
127 UnknownEdge = 0,
|
|
|
128 PointsToEdge = 1,
|
|
|
129 DeferredEdge = 2,
|
|
|
130 FieldEdge = 3
|
|
|
131 } EdgeType;
|
|
|
132
|
|
|
133 private:
|
|
|
134 enum {
|
|
|
135 EdgeMask = 3,
|
|
|
136 EdgeShift = 2,
|
|
|
137
|
|
|
138 INITIAL_EDGE_COUNT = 4
|
|
|
139 };
|
|
|
140
|
|
|
141 NodeType _type;
|
|
|
142 EscapeState _escape;
|
|
|
143 GrowableArray<uint>* _edges; // outgoing edges
|
|
|
144 int _offset; // for fields
|
|
|
145
|
|
|
146 bool _unique_type; // For allocated objects, this node may be a unique type
|
|
|
147 public:
|
|
|
148 Node* _node; // Ideal node corresponding to this PointsTo node
|
|
|
149 int _inputs_processed; // the number of Phi inputs that have been processed so far
|
|
|
150 bool _hidden_alias; // this node is an argument to a function which may return it
|
|
|
151 // creating a hidden alias
|
|
|
152
|
|
|
153
|
|
|
154 PointsToNode(): _offset(-1), _type(UnknownType), _escape(UnknownEscape), _edges(NULL), _node(NULL), _inputs_processed(0), _hidden_alias(false), _unique_type(true) {}
|
|
|
155
|
|
|
156 EscapeState escape_state() const { return _escape; }
|
|
|
157 NodeType node_type() const { return _type;}
|
|
|
158 int offset() { return _offset;}
|
|
|
159
|
|
|
160 void set_offset(int offs) { _offset = offs;}
|
|
|
161 void set_escape_state(EscapeState state) { _escape = state; }
|
|
|
162 void set_node_type(NodeType ntype) {
|
|
|
163 assert(_type == UnknownType || _type == ntype, "Can't change node type");
|
|
|
164 _type = ntype;
|
|
|
165 }
|
|
|
166
|
|
|
167 // count of outgoing edges
|
|
|
168 uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }
|
|
|
169 // node index of target of outgoing edge "e"
|
|
|
170 uint edge_target(uint e) const;
|
|
|
171 // type of outgoing edge "e"
|
|
|
172 EdgeType edge_type(uint e) const;
|
|
|
173 // add a edge of the specified type pointing to the specified target
|
|
|
174 void add_edge(uint targIdx, EdgeType et);
|
|
|
175 // remove an edge of the specified type pointing to the specified target
|
|
|
176 void remove_edge(uint targIdx, EdgeType et);
|
|
|
177 #ifndef PRODUCT
|
|
|
178 void dump() const;
|
|
|
179 #endif
|
|
|
180
|
|
|
181 };
|
|
|
182
|
|
|
183 class ConnectionGraph: public ResourceObj {
|
|
|
184 private:
|
|
|
185 enum {
|
|
|
186 INITIAL_NODE_COUNT = 100 // initial size of _nodes array
|
|
|
187 };
|
|
|
188
|
|
|
189
|
|
|
190 GrowableArray<PointsToNode>* _nodes; // connection graph nodes Indexed by ideal
|
|
|
191 // node index
|
|
|
192 Unique_Node_List _deferred; // Phi's to be processed after parsing
|
|
|
193 VectorSet _processed; // records which nodes have been processed
|
|
|
194 bool _collecting; // indicates whether escape information is
|
|
|
195 // still being collected. If false, no new
|
|
|
196 // nodes will be processed
|
|
|
197 uint _phantom_object; // index of globally escaping object that
|
|
|
198 // pointer values loaded from a field which
|
|
|
199 // has not been set are assumed to point to
|
|
|
200 Compile * _compile; // Compile object for current compilation
|
|
|
201
|
|
|
202 // address of an element in _nodes. Used when the element is to be modified
|
|
|
203 PointsToNode *ptnode_adr(uint idx) {
|
|
|
204 if ((uint)_nodes->length() <= idx) {
|
|
|
205 // expand _nodes array
|
|
|
206 PointsToNode dummy = _nodes->at_grow(idx);
|
|
|
207 }
|
|
|
208 return _nodes->adr_at(idx);
|
|
|
209 }
|
|
|
210
|
|
|
211 // offset of a field reference
|
|
|
212 int type_to_offset(const Type *t);
|
|
|
213
|
|
|
214 // compute the escape state for arguments to a call
|
|
|
215 void process_call_arguments(CallNode *call, PhaseTransform *phase);
|
|
|
216
|
|
|
217 // compute the escape state for the return value of a call
|
|
|
218 void process_call_result(ProjNode *resproj, PhaseTransform *phase);
|
|
|
219
|
|
|
220 // compute the escape state of a Phi. This may be called multiple
|
|
|
221 // times as new inputs are added to the Phi.
|
|
|
222 void process_phi_escape(PhiNode *phi, PhaseTransform *phase);
|
|
|
223
|
|
|
224 // compute the escape state of an ideal node.
|
|
|
225 void record_escape_work(Node *n, PhaseTransform *phase);
|
|
|
226
|
|
|
227 // walk the connection graph starting at the node corresponding to "n" and
|
|
|
228 // add the index of everything it could point to, to "ptset". This may cause
|
|
|
229 // Phi's encountered to get (re)processed (which requires "phase".)
|
|
|
230 void PointsTo(VectorSet &ptset, Node * n, PhaseTransform *phase);
|
|
|
231
|
|
|
232 // Edge manipulation. The "from_i" and "to_i" arguments are the
|
|
|
233 // node indices of the source and destination of the edge
|
|
|
234 void add_pointsto_edge(uint from_i, uint to_i);
|
|
|
235 void add_deferred_edge(uint from_i, uint to_i);
|
|
|
236 void add_field_edge(uint from_i, uint to_i, int offs);
|
|
|
237
|
|
|
238
|
|
|
239 // Add an edge to node given by "to_i" from any field of adr_i whose offset
|
|
|
240 // matches "offset" A deferred edge is added if to_i is a LocalVar, and
|
|
|
241 // a pointsto edge is added if it is a JavaObject
|
|
|
242 void add_edge_from_fields(uint adr, uint to_i, int offs);
|
|
|
243
|
|
|
244 // Add a deferred edge from node given by "from_i" to any field of adr_i whose offset
|
|
|
245 // matches "offset"
|
|
|
246 void add_deferred_edge_to_fields(uint from_i, uint adr, int offs);
|
|
|
247
|
|
|
248
|
|
|
249 // Remove outgoing deferred edges from the node referenced by "ni".
|
|
|
250 // Any outgoing edges from the target of the deferred edge are copied
|
|
|
251 // to "ni".
|
|
|
252 void remove_deferred(uint ni);
|
|
|
253
|
|
|
254 Node_Array _node_map; // used for bookeeping during type splitting
|
|
|
255 // Used for the following purposes:
|
|
|
256 // Memory Phi - most recent unique Phi split out
|
|
|
257 // from this Phi
|
|
|
258 // MemNode - new memory input for this node
|
|
|
259 // ChecCastPP - allocation that this is a cast of
|
|
|
260 // allocation - CheckCastPP of the allocation
|
|
|
261 void split_AddP(Node *addp, Node *base, PhaseGVN *igvn);
|
|
|
262 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created);
|
|
|
263 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn);
|
|
|
264 Node *find_mem(Node *mem, int alias_idx, PhaseGVN *igvn);
|
|
|
265 // Propagate unique types created for unescaped allocated objects
|
|
|
266 // through the graph
|
|
|
267 void split_unique_types(GrowableArray<Node *> &alloc_worklist);
|
|
|
268
|
|
|
269 // manage entries in _node_map
|
|
|
270 void set_map(int idx, Node *n) { _node_map.map(idx, n); }
|
|
|
271 void set_map_phi(int idx, PhiNode *p) { _node_map.map(idx, (Node *) p); }
|
|
|
272 Node *get_map(int idx) { return _node_map[idx]; }
|
|
|
273 PhiNode *get_map_phi(int idx) {
|
|
|
274 Node *phi = _node_map[idx];
|
|
|
275 return (phi == NULL) ? NULL : phi->as_Phi();
|
|
|
276 }
|
|
|
277
|
|
|
278 // Notify optimizer that a node has been modified
|
|
|
279 // Node: This assumes that escape analysis is run before
|
|
|
280 // PhaseIterGVN creation
|
|
|
281 void record_for_optimizer(Node *n) {
|
|
|
282 _compile->record_for_igvn(n);
|
|
|
283 }
|
|
|
284
|
|
|
285 // Set the escape state of a node
|
|
|
286 void set_escape_state(uint ni, PointsToNode::EscapeState es);
|
|
|
287
|
|
|
288 // bypass any casts and return the node they refer to
|
|
|
289 Node * skip_casts(Node *n);
|
|
|
290
|
|
|
291 // Get Compile object for current compilation.
|
|
|
292 Compile *C() const { return _compile; }
|
|
|
293
|
|
|
294 public:
|
|
|
295 ConnectionGraph(Compile *C);
|
|
|
296
|
|
|
297 // record a Phi for later processing.
|
|
|
298 void record_for_escape_analysis(Node *n);
|
|
|
299
|
|
|
300 // process a node and fill in its connection graph node
|
|
|
301 void record_escape(Node *n, PhaseTransform *phase);
|
|
|
302
|
|
|
303 // All nodes have been recorded, compute the escape information
|
|
|
304 void compute_escape();
|
|
|
305
|
|
|
306 // escape state of a node
|
|
|
307 PointsToNode::EscapeState escape_state(Node *n, PhaseTransform *phase);
|
|
|
308
|
|
|
309 bool hidden_alias(Node *n) {
|
|
|
310 if (_collecting)
|
|
|
311 return true;
|
|
|
312 PointsToNode ptn = _nodes->at_grow(n->_idx);
|
|
|
313 return (ptn.escape_state() != PointsToNode::NoEscape) || ptn._hidden_alias;
|
|
|
314 }
|
|
|
315
|
|
|
316 #ifndef PRODUCT
|
|
|
317 void dump();
|
|
|
318 #endif
|
|
|
319 };
|
