Mon, 28 Nov 2011 15:46:31 -0800
7112478: after 7105605 JRuby bench_define_method_methods.rb fails with NPE
Summary: Fixed several EA issues with Connection Graph construction.
Reviewed-by: never, twisti
1 /*
2 * Copyright (c) 2005, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
25 #ifndef SHARE_VM_OPTO_ESCAPE_HPP
26 #define SHARE_VM_OPTO_ESCAPE_HPP
28 #include "opto/addnode.hpp"
29 #include "opto/node.hpp"
30 #include "utilities/growableArray.hpp"
32 //
33 // Adaptation for C2 of the escape analysis algorithm described in:
34 //
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
39 //
40 // The flow-insensitive analysis described in the paper has been implemented.
41 //
42 // The analysis requires construction of a "connection graph" (CG) for
43 // the method being analyzed. The nodes of the connection graph are:
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 //
51 // - PointsTo (-P>) {LV, OF} to JO
52 // - Deferred (-D>) from {LV, OF} to {LV, OF}
53 // - Field (-F>) from JO to OF
54 //
55 // The following utility functions is used by the algorithm:
56 //
57 // PointsTo(n) - n is any CG node, it returns the set of JO that n could
58 // point to.
59 //
60 // The algorithm describes how to construct the connection graph
61 // in the following 4 cases:
62 //
63 // Case Edges Created
64 //
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
69 //
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.
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, LoadN
78 // Proj#5 (value returned from callnodes including allocations)
79 // CheckCastPP, CastPP
80 //
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
83 // as an assignment to it.
84 //
85 // The following node types are JavaObject:
86 //
87 // phantom_object (general globally escaped object)
88 // Allocate
89 // AllocateArray
90 // Parm (for incoming arguments)
91 // CastX2P ("unsafe" operations)
92 // CreateEx
93 // ConP
94 // LoadKlass
95 // ThreadLocal
96 // CallStaticJava (which returns Object)
97 //
98 // AddP nodes are fields.
99 //
100 // After building the graph, a pass is made over the nodes, deleting deferred
101 // nodes and copying the edges from the target of the deferred edge to the
102 // source. This results in a graph with no deferred edges, only:
103 //
104 // LV -P> JO
105 // OF -P> JO (the object whose oop is stored in the field)
106 // JO -F> OF
107 //
108 // Then, for each node which is GlobalEscape, anything it could point to
109 // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything
110 // it could point to is marked ArgEscape.
111 //
113 class Compile;
114 class Node;
115 class CallNode;
116 class PhiNode;
117 class PhaseTransform;
118 class Type;
119 class TypePtr;
120 class VectorSet;
122 class PointsToNode {
123 friend class ConnectionGraph;
124 public:
125 typedef enum {
126 UnknownType = 0,
127 JavaObject = 1,
128 LocalVar = 2,
129 Field = 3
130 } NodeType;
132 typedef enum {
133 UnknownEscape = 0,
134 NoEscape = 1, // An object does not escape method or thread and it is
135 // not passed to call. It could be replaced with scalar.
136 ArgEscape = 2, // An object does not escape method or thread but it is
137 // passed as argument to call or referenced by argument
138 // and it does not escape during call.
139 GlobalEscape = 3 // An object escapes the method or thread.
140 } EscapeState;
142 typedef enum {
143 UnknownEdge = 0,
144 PointsToEdge = 1,
145 DeferredEdge = 2,
146 FieldEdge = 3
147 } EdgeType;
149 private:
150 enum {
151 EdgeMask = 3,
152 EdgeShift = 2,
154 INITIAL_EDGE_COUNT = 4
155 };
157 NodeType _type;
158 EscapeState _escape;
159 GrowableArray<uint>* _edges; // outgoing edges
160 Node* _node; // Ideal node corresponding to this PointsTo node.
161 int _offset; // Object fields offsets.
162 bool _scalar_replaceable; // Not escaped object could be replaced with scalar
163 bool _has_unknown_ptr; // Has edge to phantom_object
165 public:
166 PointsToNode():
167 _type(UnknownType),
168 _escape(UnknownEscape),
169 _edges(NULL),
170 _node(NULL),
171 _offset(-1),
172 _has_unknown_ptr(false),
173 _scalar_replaceable(true) {}
176 EscapeState escape_state() const { return _escape; }
177 NodeType node_type() const { return _type;}
178 int offset() { return _offset;}
179 bool scalar_replaceable() { return _scalar_replaceable;}
180 bool has_unknown_ptr() { return _has_unknown_ptr;}
182 void set_offset(int offs) { _offset = offs;}
183 void set_escape_state(EscapeState state) { _escape = state; }
184 void set_node_type(NodeType ntype) {
185 assert(_type == UnknownType || _type == ntype, "Can't change node type");
186 _type = ntype;
187 }
188 void set_scalar_replaceable(bool v) { _scalar_replaceable = v; }
189 void set_has_unknown_ptr() { _has_unknown_ptr = true; }
191 // count of outgoing edges
192 uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }
194 // node index of target of outgoing edge "e"
195 uint edge_target(uint e) const {
196 assert(_edges != NULL, "valid edge index");
197 return (_edges->at(e) >> EdgeShift);
198 }
199 // type of outgoing edge "e"
200 EdgeType edge_type(uint e) const {
201 assert(_edges != NULL, "valid edge index");
202 return (EdgeType) (_edges->at(e) & EdgeMask);
203 }
205 // add a edge of the specified type pointing to the specified target
206 void add_edge(uint targIdx, EdgeType et);
208 // remove an edge of the specified type pointing to the specified target
209 void remove_edge(uint targIdx, EdgeType et);
211 #ifndef PRODUCT
212 void dump(bool print_state=true) const;
213 #endif
215 };
217 class ConnectionGraph: public ResourceObj {
218 private:
219 GrowableArray<PointsToNode> _nodes; // Connection graph nodes indexed
220 // by ideal node index.
222 Unique_Node_List _delayed_worklist; // Nodes to be processed before
223 // the call build_connection_graph().
225 GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes
227 VectorSet _processed; // Records which nodes have been
228 // processed.
230 bool _collecting; // Indicates whether escape information
231 // is still being collected. If false,
232 // no new nodes will be processed.
234 bool _progress; // Indicates whether new Graph's edges
235 // were created.
237 uint _phantom_object; // Index of globally escaping object
238 // that pointer values loaded from
239 // a field which has not been set
240 // are assumed to point to.
241 uint _oop_null; // ConP(#NULL)->_idx
242 uint _noop_null; // ConN(#NULL)->_idx
243 Node* _pcmp_neq; // ConI(#CC_GT)
244 Node* _pcmp_eq; // ConI(#CC_EQ)
246 Compile * _compile; // Compile object for current compilation
247 PhaseIterGVN * _igvn; // Value numbering
249 // Address of an element in _nodes. Used when the element is to be modified
250 PointsToNode *ptnode_adr(uint idx) const {
251 // There should be no new ideal nodes during ConnectionGraph build,
252 // growableArray::adr_at() will throw assert otherwise.
253 return _nodes.adr_at(idx);
254 }
255 uint nodes_size() const { return _nodes.length(); }
257 bool is_null_ptr(uint idx) const { return (idx == _noop_null || idx == _oop_null); }
259 // Add node to ConnectionGraph.
260 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);
262 // offset of a field reference
263 int address_offset(Node* adr, PhaseTransform *phase);
265 // compute the escape state for arguments to a call
266 void process_call_arguments(CallNode *call, PhaseTransform *phase);
268 // compute the escape state for the return value of a call
269 void process_call_result(ProjNode *resproj, PhaseTransform *phase);
271 // Populate Connection Graph with Ideal nodes.
272 void record_for_escape_analysis(Node *n, PhaseTransform *phase);
274 // Build Connection Graph and set nodes escape state.
275 void build_connection_graph(Node *n, PhaseTransform *phase);
277 // walk the connection graph starting at the node corresponding to "n" and
278 // add the index of everything it could point to, to "ptset". This may cause
279 // Phi's encountered to get (re)processed (which requires "phase".)
280 VectorSet* PointsTo(Node * n);
282 // Reused structures for PointsTo().
283 VectorSet pt_ptset;
284 VectorSet pt_visited;
285 GrowableArray<uint> pt_worklist;
287 // Edge manipulation. The "from_i" and "to_i" arguments are the
288 // node indices of the source and destination of the edge
289 void add_pointsto_edge(uint from_i, uint to_i);
290 void add_deferred_edge(uint from_i, uint to_i);
291 void add_field_edge(uint from_i, uint to_i, int offs);
293 // Add an edge of the specified type pointing to the specified target.
294 // Set _progress if new edge is added.
295 void add_edge(PointsToNode *f, uint to_i, PointsToNode::EdgeType et) {
296 uint e_cnt = f->edge_count();
297 f->add_edge(to_i, et);
298 _progress |= (f->edge_count() != e_cnt);
299 }
301 // Add an edge to node given by "to_i" from any field of adr_i whose offset
302 // matches "offset" A deferred edge is added if to_i is a LocalVar, and
303 // a pointsto edge is added if it is a JavaObject
304 void add_edge_from_fields(uint adr, uint to_i, int offs);
306 // Add a deferred edge from node given by "from_i" to any field
307 // of adr_i whose offset matches "offset"
308 void add_deferred_edge_to_fields(uint from_i, uint adr, int offs);
311 // Remove outgoing deferred edges from the node referenced by "ni".
312 // Any outgoing edges from the target of the deferred edge are copied
313 // to "ni".
314 void remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited);
316 Node_Array _node_map; // used for bookeeping during type splitting
317 // Used for the following purposes:
318 // Memory Phi - most recent unique Phi split out
319 // from this Phi
320 // MemNode - new memory input for this node
321 // ChecCastPP - allocation that this is a cast of
322 // allocation - CheckCastPP of the allocation
323 bool split_AddP(Node *addp, Node *base, PhaseGVN *igvn);
324 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created);
325 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn);
326 void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *igvn);
327 Node *find_inst_mem(Node *mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn);
329 // Propagate unique types created for unescaped allocated objects
330 // through the graph
331 void split_unique_types(GrowableArray<Node *> &alloc_worklist);
333 // manage entries in _node_map
334 void set_map(int idx, Node *n) { _node_map.map(idx, n); }
335 Node *get_map(int idx) { return _node_map[idx]; }
336 PhiNode *get_map_phi(int idx) {
337 Node *phi = _node_map[idx];
338 return (phi == NULL) ? NULL : phi->as_Phi();
339 }
341 // Notify optimizer that a node has been modified
342 void record_for_optimizer(Node *n) {
343 _igvn->_worklist.push(n);
344 _igvn->add_users_to_worklist(n);
345 }
347 // Set the escape state of a node
348 void set_escape_state(uint ni, PointsToNode::EscapeState es);
350 // Find fields initializing values for allocations.
351 void find_init_values(Node* n, VectorSet* visited, PhaseTransform* phase);
353 // Adjust escape state after Connection Graph is built.
354 void adjust_escape_state(Node* n);
356 // Propagate escape states to referenced nodes.
357 bool propagate_escape_state(GrowableArray<int>* cg_worklist,
358 GrowableArray<uint>* worklist,
359 PointsToNode::EscapeState esc_state);
361 // Optimize objects compare.
362 Node* optimize_ptr_compare(Node* n);
364 // Compute the escape information
365 bool compute_escape();
367 public:
368 ConnectionGraph(Compile *C, PhaseIterGVN *igvn);
370 // Check for non-escaping candidates
371 static bool has_candidates(Compile *C);
373 // Perform escape analysis
374 static void do_analysis(Compile *C, PhaseIterGVN *igvn);
376 // escape state of a node
377 PointsToNode::EscapeState escape_state(Node *n);
379 #ifndef PRODUCT
380 void dump();
381 #endif
382 };
384 #endif // SHARE_VM_OPTO_ESCAPE_HPP