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
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 // top()
88 // Allocate
89 // AllocateArray
90 // Parm (for incoming arguments)
91 // CastX2P ("unsafe" operations)
92 // CreateEx
93 // ConP
94 // LoadKlass
95 // ThreadLocal
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
104 // OF -P> JO (the object whose oop is stored in the field)
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 {
125 UnknownType = 0,
126 JavaObject = 1,
127 LocalVar = 2,
128 Field = 3
129 } NodeType;
130
131 typedef enum {
132 UnknownEscape = 0,
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.
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;
156 GrowableArray<uint>* _edges; // outgoing edges
157
158 public:
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.
164
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) {}
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(); }
188
189 // node index of target of outgoing edge "e"
190 uint edge_target(uint e) const {
191 assert(_edges != NULL, "valid edge index");
192 return (_edges->at(e) >> EdgeShift);
216
217 Unique_Node_List _delayed_worklist; // Nodes to be processed before
218 // the call build_connection_graph().
219
220 GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes
221
222 VectorSet _processed; // Records which nodes have been
223 // processed.
224
225 bool _collecting; // Indicates whether escape information
226 // is still being collected. If false,
227 // no new nodes will be processed.
228
229 bool _progress; // Indicates whether new Graph's edges
230 // were created.
231
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.
236 uint _oop_null; // ConP(#NULL)
237 uint _noop_null; // ConN(#NULL)
238
239 Compile * _compile; // Compile object for current compilation
240 PhaseIterGVN * _igvn; // Value numbering
241
242 // Address of an element in _nodes. Used when the element is to be modified
243 PointsToNode *ptnode_adr(uint idx) const {
244 // There should be no new ideal nodes during ConnectionGraph build,
245 // growableArray::adr_at() will throw assert otherwise.
246 return _nodes.adr_at(idx);
247 }
248 uint nodes_size() const { return _nodes.length(); }
249
250 // Add node to ConnectionGraph.
251 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);
252
253 // offset of a field reference
254 int address_offset(Node* adr, PhaseTransform *phase);
255
256 // compute the escape state for arguments to a call
257 void process_call_arguments(CallNode *call, PhaseTransform *phase);
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) {
336 _igvn->_worklist.push(n);
337 }
338
339 // Set the escape state of a node
340 void set_escape_state(uint ni, PointsToNode::EscapeState es);
341
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();
347
348 public:
349 ConnectionGraph(Compile *C, PhaseIterGVN *igvn);
350
351 // Check for non-escaping candidates
352 static bool has_candidates(Compile *C);
353
354 // Perform escape analysis
355 static void do_analysis(Compile *C, PhaseIterGVN *igvn);
356
357 // escape state of a node
358 PointsToNode::EscapeState escape_state(Node *n);
359
360 // other information we have collected
361 bool is_scalar_replaceable(Node *n) {
362 if (_collecting || (n->_idx >= nodes_size()))
363 return false;
364 PointsToNode* ptn = ptnode_adr(n->_idx);
365 return ptn->escape_state() == PointsToNode::NoEscape && ptn->_scalar_replaceable;
366 }
367
368 bool hidden_alias(Node *n) {
369 if (_collecting || (n->_idx >= nodes_size()))
370 return true;
371 PointsToNode* ptn = ptnode_adr(n->_idx);
372 return (ptn->escape_state() != PointsToNode::NoEscape) || ptn->_hidden_alias;
373 }
374
375 #ifndef PRODUCT
376 void dump();
377 #endif
378 };
379
380 #endif // SHARE_VM_OPTO_ESCAPE_HPP
|
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 //
112
113 class Compile;
114 class Node;
115 class CallNode;
116 class PhiNode;
117 class PhaseTransform;
118 class Type;
119 class TypePtr;
120 class VectorSet;
121
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;
131
132 typedef enum {
133 UnknownEscape = 0,
134 NoEscape = 1, // A scalar replaceable object with unique type.
135 ControlEscape = 2, // Complex control flow or some limitations do not
136 // allow scalar replacement of not escaping object.
137 ArgEscape = 3, // An object passed as argument or referenced by
138 // argument (and not globally escape during call).
139 GlobalEscape = 4 // An object escapes the method and thread.
140 } EscapeState;
141
142 typedef enum {
143 UnknownEdge = 0,
144 PointsToEdge = 1,
145 DeferredEdge = 2,
146 FieldEdge = 3
147 } EdgeType;
148
149 private:
150 enum {
151 EdgeMask = 3,
152 EdgeShift = 2,
153
154 INITIAL_EDGE_COUNT = 4
155 };
156
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
163 public:
164 PointsToNode():
165 _type(UnknownType),
166 _escape(UnknownEscape),
167 _edges(NULL),
168 _node(NULL),
169 _offset(-1) {}
170
171
172 EscapeState escape_state() const { return _escape; }
173 NodeType node_type() const { return _type;}
174 int offset() { return _offset;}
175
176 void set_offset(int offs) { _offset = offs;}
177 void set_escape_state(EscapeState state) { _escape = state; }
178 void set_node_type(NodeType ntype) {
179 assert(_type == UnknownType || _type == ntype, "Can't change node type");
180 _type = ntype;
181 }
182
183 // count of outgoing edges
184 uint edge_count() const { return (_edges == NULL) ? 0 : _edges->length(); }
185
186 // node index of target of outgoing edge "e"
187 uint edge_target(uint e) const {
188 assert(_edges != NULL, "valid edge index");
189 return (_edges->at(e) >> EdgeShift);
213
214 Unique_Node_List _delayed_worklist; // Nodes to be processed before
215 // the call build_connection_graph().
216
217 GrowableArray<MergeMemNode *> _mergemem_worklist; // List of all MergeMem nodes
218
219 VectorSet _processed; // Records which nodes have been
220 // processed.
221
222 bool _collecting; // Indicates whether escape information
223 // is still being collected. If false,
224 // no new nodes will be processed.
225
226 bool _progress; // Indicates whether new Graph's edges
227 // were created.
228
229 uint _phantom_object; // Index of globally escaping object
230 // that pointer values loaded from
231 // a field which has not been set
232 // are assumed to point to.
233 uint _oop_null; // ConP(#NULL)->_idx
234 uint _noop_null; // ConN(#NULL)->_idx
235
236 Compile * _compile; // Compile object for current compilation
237 PhaseIterGVN * _igvn; // Value numbering
238
239 // Address of an element in _nodes. Used when the element is to be modified
240 PointsToNode *ptnode_adr(uint idx) const {
241 // There should be no new ideal nodes during ConnectionGraph build,
242 // growableArray::adr_at() will throw assert otherwise.
243 return _nodes.adr_at(idx);
244 }
245 uint nodes_size() const { return _nodes.length(); }
246
247 // Add node to ConnectionGraph.
248 void add_node(Node *n, PointsToNode::NodeType nt, PointsToNode::EscapeState es, bool done);
249
250 // offset of a field reference
251 int address_offset(Node* adr, PhaseTransform *phase);
252
253 // compute the escape state for arguments to a call
254 void process_call_arguments(CallNode *call, PhaseTransform *phase);
319 void split_unique_types(GrowableArray<Node *> &alloc_worklist);
320
321 // manage entries in _node_map
322 void set_map(int idx, Node *n) { _node_map.map(idx, n); }
323 Node *get_map(int idx) { return _node_map[idx]; }
324 PhiNode *get_map_phi(int idx) {
325 Node *phi = _node_map[idx];
326 return (phi == NULL) ? NULL : phi->as_Phi();
327 }
328
329 // Notify optimizer that a node has been modified
330 // Node: This assumes that escape analysis is run before
331 // PhaseIterGVN creation
332 void record_for_optimizer(Node *n) {
333 _igvn->_worklist.push(n);
334 }
335
336 // Set the escape state of a node
337 void set_escape_state(uint ni, PointsToNode::EscapeState es);
338
339 // Find fields initializing values for allocations.
340 void find_init_values(Node* n, VectorSet* visited, PhaseTransform* phase);
341
342 // Adjust escape state after Connection Graph is built.
343 void adjust_escape_state(Node* n);
344
345 // Propagate escape states to referenced nodes.
346 bool propagate_escape_state(GrowableArray<int>* cg_worklist,
347 GrowableArray<uint>* worklist,
348 PointsToNode::EscapeState esc_state);
349
350 // Compute the escape information
351 bool compute_escape();
352
353 public:
354 ConnectionGraph(Compile *C, PhaseIterGVN *igvn);
355
356 // Check for non-escaping candidates
357 static bool has_candidates(Compile *C);
358
359 // Perform escape analysis
360 static void do_analysis(Compile *C, PhaseIterGVN *igvn);
361
362 // escape state of a node
363 PointsToNode::EscapeState escape_state(Node *n);
364
365 #ifndef PRODUCT
366 void dump();
367 #endif
368 };
369
370 #endif // SHARE_VM_OPTO_ESCAPE_HPP
|