Mercurial > hg > truffle
annotate src/share/vm/opto/escape.hpp @ 2645:b2c1e959be46
Clean up around BlockBegin / StdEntry.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 11 May 2011 14:34:29 +0200 |
parents | 3763ca6579b7 |
children | 59e515ee9354 |
rev | line source |
---|---|
0 | 1 /* |
2249 | 2 * Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1101
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1101
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1101
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
1972 | 25 #ifndef SHARE_VM_OPTO_ESCAPE_HPP |
26 #define SHARE_VM_OPTO_ESCAPE_HPP | |
27 | |
28 #include "opto/addnode.hpp" | |
29 #include "opto/node.hpp" | |
30 #include "utilities/growableArray.hpp" | |
31 | |
0 | 32 // |
33 // Adaptation for C2 of the escape analysis algorithm described in: | |
34 // | |
65 | 35 // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano, |
36 // Vugranam C. Sreedhar, Sam Midkiff, | |
37 // "Escape Analysis for Java", Procedings of ACM SIGPLAN | |
38 // OOPSLA Conference, November 1, 1999 | |
0 | 39 // |
40 // The flow-insensitive analysis described in the paper has been implemented. | |
41 // | |
65 | 42 // The analysis requires construction of a "connection graph" (CG) for |
43 // the method being analyzed. The nodes of the connection graph are: | |
0 | 44 // |
45 // - Java objects (JO) | |
46 // - Local variables (LV) | |
47 // - Fields of an object (OF), these also include array elements | |
48 // | |
49 // The CG contains 3 types of edges: | |
50 // | |
65 | 51 // - PointsTo (-P>) {LV, OF} to JO |
52 // - Deferred (-D>) from {LV, OF} to {LV, OF} | |
0 | 53 // - Field (-F>) from JO to OF |
54 // | |
55 // The following utility functions is used by the algorithm: | |
56 // | |
65 | 57 // PointsTo(n) - n is any CG node, it returns the set of JO that n could |
58 // point to. | |
0 | 59 // |
65 | 60 // The algorithm describes how to construct the connection graph |
61 // in the following 4 cases: | |
0 | 62 // |
63 // Case Edges Created | |
64 // | |
65 | 65 // (1) p = new T() LV -P> JO |
66 // (2) p = q LV -D> LV | |
67 // (3) p.f = q JO -F> OF, OF -D> LV | |
68 // (4) p = q.f JO -F> OF, LV -D> OF | |
0 | 69 // |
65 | 70 // In all these cases, p and q are local variables. For static field |
71 // references, we can construct a local variable containing a reference | |
72 // to the static memory. | |
0 | 73 // |
74 // C2 does not have local variables. However for the purposes of constructing | |
75 // the connection graph, the following IR nodes are treated as local variables: | |
76 // Phi (pointer values) | |
77 // LoadP | |
65 | 78 // Proj#5 (value returned from callnodes including allocations) |
79 // CheckCastPP, CastPP | |
0 | 80 // |
65 | 81 // The LoadP, Proj and CheckCastPP behave like variables assigned to only once. |
82 // Only a Phi can have multiple assignments. Each input to a Phi is treated | |
0 | 83 // as an assignment to it. |
84 // | |
65 | 85 // The following node types are JavaObject: |
0 | 86 // |
87 // top() | |
88 // Allocate | |
89 // AllocateArray | |
90 // Parm (for incoming arguments) | |
65 | 91 // CastX2P ("unsafe" operations) |
0 | 92 // CreateEx |
93 // ConP | |
94 // LoadKlass | |
65 | 95 // ThreadLocal |
0 | 96 // |
97 // AddP nodes are fields. | |
98 // | |
99 // After building the graph, a pass is made over the nodes, deleting deferred | |
100 // nodes and copying the edges from the target of the deferred edge to the | |
101 // source. This results in a graph with no deferred edges, only: | |
102 // | |
103 // LV -P> JO | |
65 | 104 // OF -P> JO (the object whose oop is stored in the field) |
0 | 105 // JO -F> OF |
106 // | |
107 // Then, for each node which is GlobalEscape, anything it could point to | |
108 // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything | |
109 // it could point to is marked ArgEscape. | |
110 // | |
111 | |
112 class Compile; | |
113 class Node; | |
114 class CallNode; | |
115 class PhiNode; | |
116 class PhaseTransform; | |
117 class Type; | |
118 class TypePtr; | |
119 class VectorSet; | |
120 | |
121 class PointsToNode { | |
122 friend class ConnectionGraph; | |
123 public: | |
124 typedef enum { | |
65 | 125 UnknownType = 0, |
126 JavaObject = 1, | |
127 LocalVar = 2, | |
128 Field = 3 | |
0 | 129 } NodeType; |
130 | |
131 typedef enum { | |
132 UnknownEscape = 0, | |
65 | 133 NoEscape = 1, // A scalar replaceable object with unique type. |
134 ArgEscape = 2, // An object passed as argument or referenced by | |
135 // argument (and not globally escape during call). | |
136 GlobalEscape = 3 // An object escapes the method and thread. | |
0 | 137 } EscapeState; |
138 | |
139 typedef enum { | |
140 UnknownEdge = 0, | |
141 PointsToEdge = 1, | |
142 DeferredEdge = 2, | |
143 FieldEdge = 3 | |
144 } EdgeType; | |
145 | |
146 private: | |
147 enum { | |
148 EdgeMask = 3, | |
149 EdgeShift = 2, | |
150 | |
151 INITIAL_EDGE_COUNT = 4 | |
152 }; | |
153 | |
154 NodeType _type; | |
155 EscapeState _escape; | |
65 | 156 GrowableArray<uint>* _edges; // outgoing edges |
0 | 157 |
158 public: | |
65 | 159 Node* _node; // Ideal node corresponding to this PointsTo node. |
160 int _offset; // Object fields offsets. | |
161 bool _scalar_replaceable;// Not escaped object could be replaced with scalar | |
162 bool _hidden_alias; // This node is an argument to a function. | |
163 // which may return it creating a hidden alias. | |
0 | 164 |
65 | 165 PointsToNode(): |
166 _type(UnknownType), | |
167 _escape(UnknownEscape), | |
168 _edges(NULL), | |
169 _node(NULL), | |
170 _offset(-1), | |
171 _scalar_replaceable(true), | |
172 _hidden_alias(false) {} | |
0 | 173 |
174 | |
175 EscapeState escape_state() const { return _escape; } | |
176 NodeType node_type() const { return _type;} | |
177 int offset() { return _offset;} | |
178 | |
179 void set_offset(int offs) { _offset = offs;} | |
180 void set_escape_state(EscapeState state) { _escape = state; } | |
181 void set_node_type(NodeType ntype) { | |
182 assert(_type == UnknownType || _type == ntype, "Can't change node type"); | |
183 _type = ntype; | |
184 } | |
185 | |
186 // count of outgoing edges | |
187 uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); } | |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
188 |
0 | 189 // node index of target of outgoing edge "e" |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
190 uint edge_target(uint e) const { |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
191 assert(_edges != NULL, "valid edge index"); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
192 return (_edges->at(e) >> EdgeShift); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
193 } |
0 | 194 // type of outgoing edge "e" |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
195 EdgeType edge_type(uint e) const { |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
196 assert(_edges != NULL, "valid edge index"); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
197 return (EdgeType) (_edges->at(e) & EdgeMask); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
198 } |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
199 |
0 | 200 // add a edge of the specified type pointing to the specified target |
201 void add_edge(uint targIdx, EdgeType et); | |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
202 |
0 | 203 // remove an edge of the specified type pointing to the specified target |
204 void remove_edge(uint targIdx, EdgeType et); | |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
205 |
0 | 206 #ifndef PRODUCT |
253
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
245
diff
changeset
|
207 void dump(bool print_state=true) const; |
0 | 208 #endif |
209 | |
210 }; | |
211 | |
212 class ConnectionGraph: public ResourceObj { | |
213 private: | |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
214 GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed |
65 | 215 // by ideal node index. |
0 | 216 |
65 | 217 Unique_Node_List _delayed_worklist; // Nodes to be processed before |
218 // the call build_connection_graph(). | |
219 | |
1100
f96a1a986f7b
6895383: JCK test throws NPE for method compiled with Escape Analysis
kvn
parents:
293
diff
changeset
|
220 GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes |
f96a1a986f7b
6895383: JCK test throws NPE for method compiled with Escape Analysis
kvn
parents:
293
diff
changeset
|
221 |
65 | 222 VectorSet _processed; // Records which nodes have been |
223 // processed. | |
0 | 224 |
65 | 225 bool _collecting; // Indicates whether escape information |
226 // is still being collected. If false, | |
227 // no new nodes will be processed. | |
228 | |
1921 | 229 bool _progress; // Indicates whether new Graph's edges |
230 // were created. | |
231 | |
65 | 232 uint _phantom_object; // Index of globally escaping object |
233 // that pointer values loaded from | |
234 // a field which has not been set | |
235 // are assumed to point to. | |
253
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
245
diff
changeset
|
236 uint _oop_null; // ConP(#NULL) |
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
245
diff
changeset
|
237 uint _noop_null; // ConN(#NULL) |
65 | 238 |
239 Compile * _compile; // Compile object for current compilation | |
1634
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
240 PhaseIterGVN * _igvn; // Value numbering |
0 | 241 |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
242 // Address of an element in _nodes. Used when the element is to be modified |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
243 PointsToNode *ptnode_adr(uint idx) const { |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
244 // There should be no new ideal nodes during ConnectionGraph build, |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
245 // growableArray::adr_at() will throw assert otherwise. |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
246 return _nodes.adr_at(idx); |
0 | 247 } |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
248 uint nodes_size() const { return _nodes.length(); } |
0 | 249 |
65 | 250 // Add node to ConnectionGraph. |
251 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done); | |
252 | |
0 | 253 // offset of a field reference |
65 | 254 int address_offset(Node* adr, PhaseTransform *phase); |
0 | 255 |
256 // compute the escape state for arguments to a call | |
257 void process_call_arguments(CallNode *call, PhaseTransform *phase); | |
258 | |
259 // compute the escape state for the return value of a call | |
260 void process_call_result(ProjNode *resproj, PhaseTransform *phase); | |
261 | |
65 | 262 // Populate Connection Graph with Ideal nodes. |
263 void record_for_escape_analysis(Node *n, PhaseTransform *phase); | |
0 | 264 |
65 | 265 // Build Connection Graph and set nodes escape state. |
266 void build_connection_graph(Node *n, PhaseTransform *phase); | |
0 | 267 |
268 // walk the connection graph starting at the node corresponding to "n" and | |
269 // add the index of everything it could point to, to "ptset". This may cause | |
270 // Phi's encountered to get (re)processed (which requires "phase".) | |
2249 | 271 VectorSet* PointsTo(Node * n); |
272 | |
273 // Reused structures for PointsTo(). | |
274 VectorSet pt_ptset; | |
275 VectorSet pt_visited; | |
276 GrowableArray<uint> pt_worklist; | |
0 | 277 |
278 // Edge manipulation. The "from_i" and "to_i" arguments are the | |
279 // node indices of the source and destination of the edge | |
280 void add_pointsto_edge(uint from_i, uint to_i); | |
281 void add_deferred_edge(uint from_i, uint to_i); | |
282 void add_field_edge(uint from_i, uint to_i, int offs); | |
283 | |
1921 | 284 // Add an edge of the specified type pointing to the specified target. |
285 // Set _progress if new edge is added. | |
286 void add_edge(PointsToNode *f, uint to_i, PointsToNode::EdgeType et) { | |
287 uint e_cnt = f->edge_count(); | |
288 f->add_edge(to_i, et); | |
289 _progress |= (f->edge_count() != e_cnt); | |
290 } | |
0 | 291 |
292 // Add an edge to node given by "to_i" from any field of adr_i whose offset | |
293 // matches "offset" A deferred edge is added if to_i is a LocalVar, and | |
294 // a pointsto edge is added if it is a JavaObject | |
295 void add_edge_from_fields(uint adr, uint to_i, int offs); | |
296 | |
65 | 297 // Add a deferred edge from node given by "from_i" to any field |
298 // of adr_i whose offset matches "offset" | |
0 | 299 void add_deferred_edge_to_fields(uint from_i, uint adr, int offs); |
300 | |
301 | |
302 // Remove outgoing deferred edges from the node referenced by "ni". | |
303 // Any outgoing edges from the target of the deferred edge are copied | |
304 // to "ni". | |
101
a6cb86dd209b
6681577: PIT: some VM tests fails with -XX:+AggressiveOpts in 6u5p b01
kvn
parents:
65
diff
changeset
|
305 void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited); |
0 | 306 |
307 Node_Array _node_map; // used for bookeeping during type splitting | |
308 // Used for the following purposes: | |
309 // Memory Phi - most recent unique Phi split out | |
310 // from this Phi | |
311 // MemNode - new memory input for this node | |
312 // ChecCastPP - allocation that this is a cast of | |
313 // allocation - CheckCastPP of the allocation | |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
314 bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn); |
0 | 315 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created); |
316 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); | |
1101
7fee0a6cc6d4
6896727: nsk/logging/LoggingPermission/LoggingPermission/logperm002 fails with G1, EscapeAnalisys
kvn
parents:
1100
diff
changeset
|
317 void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *igvn); |
65 | 318 Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn); |
319 | |
0 | 320 // Propagate unique types created for unescaped allocated objects |
321 // through the graph | |
322 void split_unique_types(GrowableArray<Node *> &alloc_worklist); | |
323 | |
324 // manage entries in _node_map | |
325 void set_map(int idx, Node *n) { _node_map.map(idx, n); } | |
326 Node *get_map(int idx) { return _node_map[idx]; } | |
327 PhiNode *get_map_phi(int idx) { | |
328 Node *phi = _node_map[idx]; | |
329 return (phi == NULL) ? NULL : phi->as_Phi(); | |
330 } | |
331 | |
332 // Notify optimizer that a node has been modified | |
333 // Node: This assumes that escape analysis is run before | |
334 // PhaseIterGVN creation | |
335 void record_for_optimizer(Node *n) { | |
1634
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
336 _igvn->_worklist.push(n); |
0 | 337 } |
338 | |
339 // Set the escape state of a node | |
340 void set_escape_state(uint ni, PointsToNode::EscapeState es); | |
341 | |
2249 | 342 // Adjust escape state after Connection Graph is built. |
343 void adjust_escape_state(int nidx, PhaseTransform* phase); | |
344 | |
345 // Compute the escape information | |
346 bool compute_escape(); | |
1100
f96a1a986f7b
6895383: JCK test throws NPE for method compiled with Escape Analysis
kvn
parents:
293
diff
changeset
|
347 |
0 | 348 public: |
1634
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
349 ConnectionGraph(Compile *C, PhaseIterGVN *igvn); |
0 | 350 |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
351 // Check for non-escaping candidates |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
352 static bool has_candidates(Compile *C); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
353 |
1634
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
354 // Perform escape analysis |
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
355 static void do_analysis(Compile *C, PhaseIterGVN *igvn); |
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
356 |
0 | 357 // escape state of a node |
1634
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
358 PointsToNode::EscapeState escape_state(Node *n); |
60a14ad85270
6966411: escape.cpp:450 assert(base->Opcode() == Op_ConP
kvn
parents:
1552
diff
changeset
|
359 |
65 | 360 // other information we have collected |
361 bool is_scalar_replaceable(Node *n) { | |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
362 if (_collecting || (n->_idx >= nodes_size())) |
65 | 363 return false; |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
364 PointsToNode* ptn = ptnode_adr(n->_idx); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
365 return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable; |
65 | 366 } |
0 | 367 |
368 bool hidden_alias(Node *n) { | |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
369 if (_collecting || (n->_idx >= nodes_size())) |
0 | 370 return true; |
244
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
371 PointsToNode* ptn = ptnode_adr(n->_idx); |
524eca34ea76
6684714: Optimize EA Connection Graph build performance
kvn
parents:
101
diff
changeset
|
372 return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias; |
0 | 373 } |
374 | |
375 #ifndef PRODUCT | |
376 void dump(); | |
377 #endif | |
378 }; | |
1972 | 379 |
380 #endif // SHARE_VM_OPTO_ESCAPE_HPP |