1 /*
2 * Copyright (c) 2005, 2024, 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 */
24
25 #ifndef SHARE_OPTO_ESCAPE_HPP
26 #define SHARE_OPTO_ESCAPE_HPP
27
28 #include "opto/addnode.hpp"
29 #include "opto/idealGraphPrinter.hpp"
30 #include "opto/node.hpp"
31 #include "utilities/growableArray.hpp"
32
33 //
34 // Adaptation for C2 of the escape analysis algorithm described in:
35 //
36 // [Choi99] Jong-Deok Shoi, Manish Gupta, Mauricio Seffano,
37 // Vugranam C. Sreedhar, Sam Midkiff,
38 // "Escape Analysis for Java", Proceedings of ACM SIGPLAN
39 // OOPSLA Conference, November 1, 1999
40 //
41 // The flow-insensitive analysis described in the paper has been implemented.
42 //
43 // The analysis requires construction of a "connection graph" (CG) for
44 // the method being analyzed. The nodes of the connection graph are:
45 //
46 // - Java objects (JO)
47 // - Local variables (LV)
48 // - Fields of an object (OF), these also include array elements
49 //
50 // The CG contains 3 types of edges:
51 //
52 // - PointsTo (-P>) {LV, OF} to JO
53 // - Deferred (-D>) from {LV, OF} to {LV, OF}
54 // - Field (-F>) from JO to OF
55 //
56 // The following utility functions is used by the algorithm:
57 //
58 // PointsTo(n) - n is any CG node, it returns the set of JO that n could
59 // point to.
60 //
61 // The algorithm describes how to construct the connection graph
62 // in the following 4 cases:
63 //
64 // Case Edges Created
65 //
66 // (1) p = new T() LV -P> JO
67 // (2) p = q LV -D> LV
68 // (3) p.f = q JO -F> OF, OF -D> LV
69 // (4) p = q.f JO -F> OF, LV -D> OF
70 //
71 // In all these cases, p and q are local variables. For static field
72 // references, we can construct a local variable containing a reference
73 // to the static memory.
74 //
75 // C2 does not have local variables. However for the purposes of constructing
76 // the connection graph, the following IR nodes are treated as local variables:
77 // Phi (pointer values)
78 // LoadP, LoadN
79 // Proj#5 (value returned from call nodes including allocations)
80 // CheckCastPP, CastPP
81 //
82 // The LoadP, Proj and CheckCastPP behave like variables assigned to only once.
83 // Only a Phi can have multiple assignments. Each input to a Phi is treated
84 // as an assignment to it.
85 //
86 // The following node types are JavaObject:
87 //
88 // phantom_object (general globally escaped object)
89 // Allocate
90 // AllocateArray
91 // Parm (for incoming arguments)
92 // CastX2P ("unsafe" operations)
93 // CreateEx
94 // ConP
95 // LoadKlass
96 // ThreadLocal
97 // CallStaticJava (which returns Object)
98 //
99 // AddP nodes are fields.
100 //
101 // After building the graph, a pass is made over the nodes, deleting deferred
102 // nodes and copying the edges from the target of the deferred edge to the
103 // source. This results in a graph with no deferred edges, only:
104 //
105 // LV -P> JO
106 // OF -P> JO (the object whose oop is stored in the field)
107 // JO -F> OF
108 //
109 // Then, for each node which is GlobalEscape, anything it could point to
110 // is marked GlobalEscape. Finally, for any node marked ArgEscape, anything
111 // it could point to is marked ArgEscape.
112 //
113
114 class Compile;
115 class Node;
116 class AbstractLockNode;
117 class CallNode;
118 class PhiNode;
119 class PhaseTransform;
120 class PointsToNode;
121 class Type;
122 class TypePtr;
123 class VectorSet;
124
125 class JavaObjectNode;
126 class LocalVarNode;
127 class FieldNode;
128 class ArraycopyNode;
129
130 class ConnectionGraph;
131
132 // ConnectionGraph nodes
133 class PointsToNode : public ArenaObj {
134 GrowableArray<PointsToNode*> _edges; // List of nodes this node points to
135 GrowableArray<PointsToNode*> _uses; // List of nodes which point to this node
136
137 const u1 _type; // NodeType
138 u1 _flags; // NodeFlags
139 u1 _escape; // EscapeState of object
140 u1 _fields_escape; // EscapeState of object's fields
141
142 Node* const _node; // Ideal node corresponding to this PointsTo node.
143 const int _idx; // Cached ideal node's _idx
144 const uint _pidx; // Index of this node
145
146 public:
147 typedef enum {
148 UnknownType = 0,
149 JavaObject = 1,
150 LocalVar = 2,
151 Field = 3,
152 Arraycopy = 4
153 } NodeType;
154
155 typedef enum {
156 UnknownEscape = 0,
157 NoEscape = 1, // An object does not escape method or thread and it is
158 // not passed to call. It could be replaced with scalar.
159 ArgEscape = 2, // An object does not escape method or thread but it is
160 // passed as argument to call or referenced by argument
161 // and it does not escape during call.
162 GlobalEscape = 3 // An object escapes the method or thread.
163 } EscapeState;
164
165 typedef enum {
166 ScalarReplaceable = 1, // Not escaped object could be replaced with scalar
167 PointsToUnknown = 2, // Has edge to phantom_object
168 ArraycopySrc = 4, // Has edge from Arraycopy node
169 ArraycopyDst = 8 // Has edge to Arraycopy node
170 } NodeFlags;
171
172
173 inline PointsToNode(ConnectionGraph* CG, Node* n, EscapeState es, NodeType type);
174
175 uint pidx() const { return _pidx; }
176
177 Node* ideal_node() const { return _node; }
178 int idx() const { return _idx; }
179
180 bool is_JavaObject() const { return _type == (u1)JavaObject; }
181 bool is_LocalVar() const { return _type == (u1)LocalVar; }
182 bool is_Field() const { return _type == (u1)Field; }
183 bool is_Arraycopy() const { return _type == (u1)Arraycopy; }
184
185 JavaObjectNode* as_JavaObject() { assert(is_JavaObject(),""); return (JavaObjectNode*)this; }
186 LocalVarNode* as_LocalVar() { assert(is_LocalVar(),""); return (LocalVarNode*)this; }
187 FieldNode* as_Field() { assert(is_Field(),""); return (FieldNode*)this; }
188 ArraycopyNode* as_Arraycopy() { assert(is_Arraycopy(),""); return (ArraycopyNode*)this; }
189
190 EscapeState escape_state() const { return (EscapeState)_escape; }
191 void set_escape_state(EscapeState state) { _escape = (u1)state; }
192
193 EscapeState fields_escape_state() const { return (EscapeState)_fields_escape; }
194 void set_fields_escape_state(EscapeState state) { _fields_escape = (u1)state; }
195
196 bool has_unknown_ptr() const { return (_flags & PointsToUnknown) != 0; }
197 void set_has_unknown_ptr() { _flags |= PointsToUnknown; }
198
199 bool arraycopy_src() const { return (_flags & ArraycopySrc) != 0; }
200 void set_arraycopy_src() { _flags |= ArraycopySrc; }
201 bool arraycopy_dst() const { return (_flags & ArraycopyDst) != 0; }
202 void set_arraycopy_dst() { _flags |= ArraycopyDst; }
203
204 bool scalar_replaceable() const { return (_flags & ScalarReplaceable) != 0;}
205 void set_scalar_replaceable(bool set) {
206 if (set) {
207 _flags |= ScalarReplaceable;
208 } else {
209 _flags &= ~ScalarReplaceable;
210 }
211 }
212
213 int edge_count() const { return _edges.length(); }
214 PointsToNode* edge(int e) const { return _edges.at(e); }
215 bool add_edge(PointsToNode* edge) { return _edges.append_if_missing(edge); }
216
217 int use_count() const { return _uses.length(); }
218 PointsToNode* use(int e) const { return _uses.at(e); }
219 bool add_use(PointsToNode* use) { return _uses.append_if_missing(use); }
220
221 // Mark base edge use to distinguish from stored value edge.
222 bool add_base_use(FieldNode* use) { return _uses.append_if_missing((PointsToNode*)((intptr_t)use + 1)); }
223 static bool is_base_use(PointsToNode* use) { return (((intptr_t)use) & 1); }
224 static PointsToNode* get_use_node(PointsToNode* use) { return (PointsToNode*)(((intptr_t)use) & ~1); }
225
226 // Return true if this node points to specified node or nodes it points to.
227 bool points_to(JavaObjectNode* ptn) const;
228
229 // Return true if this node points only to non-escaping allocations.
230 bool non_escaping_allocation();
231
232 // Return true if one node points to an other.
233 bool meet(PointsToNode* ptn);
234
235 #ifndef PRODUCT
236 NodeType node_type() const { return (NodeType)_type;}
237 void dump(bool print_state=true, outputStream* out=tty, bool newline=true) const;
238 void dump_header(bool print_state=true, outputStream* out=tty) const;
239 const char* esc_name() const;
240 #endif
241
242 };
243
244 class LocalVarNode: public PointsToNode {
245 public:
246 LocalVarNode(ConnectionGraph *CG, Node* n, EscapeState es):
247 PointsToNode(CG, n, es, LocalVar) {}
248 };
249
250 class JavaObjectNode: public PointsToNode {
251 public:
252 JavaObjectNode(ConnectionGraph *CG, Node* n, EscapeState es):
253 PointsToNode(CG, n, es, JavaObject) {
254 if (es > NoEscape) {
255 set_scalar_replaceable(false);
256 }
257 }
258 };
259
260 class FieldNode: public PointsToNode {
261 GrowableArray<PointsToNode*> _bases; // List of JavaObject nodes which point to this node
262 const int _offset; // Field's offset.
263 const bool _is_oop; // Field points to object
264 bool _has_unknown_base; // Has phantom_object base
265 public:
266 inline FieldNode(ConnectionGraph *CG, Node* n, EscapeState es, int offs, bool is_oop);
267
268 int offset() const { return _offset;}
269 bool is_oop() const { return _is_oop;}
270 bool has_unknown_base() const { return _has_unknown_base; }
271 void set_has_unknown_base() { _has_unknown_base = true; }
272
273 int base_count() const { return _bases.length(); }
274 PointsToNode* base(int e) const { return _bases.at(e); }
275 bool add_base(PointsToNode* base) { return _bases.append_if_missing(base); }
276 #ifdef ASSERT
277 // Return true if bases points to this java object.
278 bool has_base(JavaObjectNode* ptn) const;
279 #endif
280
281 };
282
283 class ArraycopyNode: public PointsToNode {
284 public:
285 ArraycopyNode(ConnectionGraph *CG, Node* n, EscapeState es):
286 PointsToNode(CG, n, es, Arraycopy) {}
287 };
288
289 // Iterators for PointsTo node's edges:
290 // for (EdgeIterator i(n); i.has_next(); i.next()) {
291 // PointsToNode* u = i.get();
292 class PointsToIterator: public StackObj {
293 protected:
294 const PointsToNode* node;
295 const int cnt;
296 int i;
297 public:
298 inline PointsToIterator(const PointsToNode* n, int cnt) : node(n), cnt(cnt), i(0) { }
299 inline bool has_next() const { return i < cnt; }
300 inline void next() { i++; }
301 PointsToNode* get() const { ShouldNotCallThis(); return nullptr; }
302 };
303
304 class EdgeIterator: public PointsToIterator {
305 public:
306 inline EdgeIterator(const PointsToNode* n) : PointsToIterator(n, n->edge_count()) { }
307 inline PointsToNode* get() const { return node->edge(i); }
308 };
309
310 class UseIterator: public PointsToIterator {
311 public:
312 inline UseIterator(const PointsToNode* n) : PointsToIterator(n, n->use_count()) { }
313 inline PointsToNode* get() const { return node->use(i); }
314 };
315
316 class BaseIterator: public PointsToIterator {
317 public:
318 inline BaseIterator(const FieldNode* n) : PointsToIterator(n, n->base_count()) { }
319 inline PointsToNode* get() const { return ((PointsToNode*)node)->as_Field()->base(i); }
320 };
321
322
323 class ConnectionGraph: public ArenaObj {
324 friend class PointsToNode; // to access _compile
325 friend class FieldNode;
326 friend class IdealGraphPrinter;
327 private:
328 GrowableArray<PointsToNode*> _nodes; // Map from ideal nodes to
329 // ConnectionGraph nodes.
330
331 GrowableArray<PointsToNode*> _worklist; // Nodes to be processed
332 VectorSet _in_worklist;
333 uint _next_pidx;
334
335 bool _collecting; // Indicates whether escape information
336 // is still being collected. If false,
337 // no new nodes will be processed.
338
339 bool _verify; // verify graph
340
341 JavaObjectNode* null_obj;
342
343 Compile* _compile; // Compile object for current compilation
344 PhaseIterGVN* _igvn; // Value numbering
345
346 Unique_Node_List ideal_nodes; // Used by CG construction and types splitting.
347
348 int _invocation; // Current number of analysis invocation
349 int _build_iterations; // Number of iterations took to build graph
350 double _build_time; // Time (sec) took to build graph
351
352 public:
353 JavaObjectNode* phantom_obj; // Unknown object
354
355 private:
356 // Address of an element in _nodes. Used when the element is to be modified
357 PointsToNode* ptnode_adr(int idx) const {
358 // There should be no new ideal nodes during ConnectionGraph build,
359 // growableArray::at() will throw assert otherwise.
360 return _nodes.at(idx);
361 }
362 uint nodes_size() const { return _nodes.length(); }
363
364 uint next_pidx() { return _next_pidx++; }
365
366 // Add nodes to ConnectionGraph.
367 void add_local_var(Node* n, PointsToNode::EscapeState es);
368 PointsToNode* add_java_object(Node* n, PointsToNode::EscapeState es);
369 void add_field(Node* n, PointsToNode::EscapeState es, int offset);
370 void add_arraycopy(Node* n, PointsToNode::EscapeState es, PointsToNode* src, PointsToNode* dst);
371
372 // Compute the escape state for arguments to a call.
373 void process_call_arguments(CallNode *call);
374
375 // Add PointsToNode node corresponding to a call
376 void add_call_node(CallNode* call);
377
378 // Create PointsToNode node and add it to Connection Graph.
379 void add_node_to_connection_graph(Node *n, Unique_Node_List *delayed_worklist);
380
381 // Add final simple edges to graph.
382 void add_final_edges(Node *n);
383
384 // Finish Graph construction.
385 bool complete_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist,
386 GrowableArray<JavaObjectNode*>& non_escaped_worklist,
387 GrowableArray<JavaObjectNode*>& java_objects_worklist,
388 GrowableArray<FieldNode*>& oop_fields_worklist);
389
390 #ifdef ASSERT
391 void verify_connection_graph(GrowableArray<PointsToNode*>& ptnodes_worklist,
392 GrowableArray<JavaObjectNode*>& non_escaped_worklist,
393 GrowableArray<JavaObjectNode*>& java_objects_worklist,
394 GrowableArray<Node*>& addp_worklist);
395 #endif
396
397 // Add all references to this JavaObject node.
398 int add_java_object_edges(JavaObjectNode* jobj, bool populate_worklist);
399
400 // Put node on worklist if it is (or was) not there.
401 inline void add_to_worklist(PointsToNode* pt) {
402 PointsToNode* ptf = pt;
403 uint pidx_bias = 0;
404 if (PointsToNode::is_base_use(pt)) {
405 // Create a separate entry in _in_worklist for a marked base edge
406 // because _worklist may have an entry for a normal edge pointing
407 // to the same node. To separate them use _next_pidx as bias.
408 ptf = PointsToNode::get_use_node(pt)->as_Field();
409 pidx_bias = _next_pidx;
410 }
411 if (!_in_worklist.test_set(ptf->pidx() + pidx_bias)) {
412 _worklist.append(pt);
413 }
414 }
415
416 // Put on worklist all uses of this node.
417 inline void add_uses_to_worklist(PointsToNode* pt) {
418 for (UseIterator i(pt); i.has_next(); i.next()) {
419 add_to_worklist(i.get());
420 }
421 }
422
423 // Put on worklist all field's uses and related field nodes.
424 void add_field_uses_to_worklist(FieldNode* field);
425
426 // Put on worklist all related field nodes.
427 void add_fields_to_worklist(FieldNode* field, PointsToNode* base);
428
429 // Find fields which have unknown value.
430 int find_field_value(FieldNode* field);
431
432 // Find fields initializing values for allocations.
433 int find_init_values_null (JavaObjectNode* ptn, PhaseValues* phase);
434 int find_init_values_phantom(JavaObjectNode* ptn);
435
436 // Set the escape state of an object and its fields.
437 void set_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc
438 NOT_PRODUCT(COMMA const char* reason)) {
439 // Don't change non-escaping state of null pointer.
440 if (ptn != null_obj) {
441 if (ptn->escape_state() < esc) {
442 NOT_PRODUCT(trace_es_update_helper(ptn, esc, false, reason));
443 ptn->set_escape_state(esc);
444 }
445 if (ptn->fields_escape_state() < esc) {
446 NOT_PRODUCT(trace_es_update_helper(ptn, esc, true, reason));
447 ptn->set_fields_escape_state(esc);
448 }
449
450 if (esc != PointsToNode::NoEscape) {
451 ptn->set_scalar_replaceable(false);
452 }
453 }
454 }
455 void set_fields_escape_state(PointsToNode* ptn, PointsToNode::EscapeState esc
456 NOT_PRODUCT(COMMA const char* reason)) {
457 // Don't change non-escaping state of null pointer.
458 if (ptn != null_obj) {
459 if (ptn->fields_escape_state() < esc) {
460 NOT_PRODUCT(trace_es_update_helper(ptn, esc, true, reason));
461 ptn->set_fields_escape_state(esc);
462 }
463
464 if (esc != PointsToNode::NoEscape) {
465 ptn->set_scalar_replaceable(false);
466 }
467 }
468 }
469
470 // Propagate GlobalEscape and ArgEscape escape states to all nodes
471 // and check that we still have non-escaping java objects.
472 bool find_non_escaped_objects(GrowableArray<PointsToNode*>& ptnodes_worklist,
473 GrowableArray<JavaObjectNode*>& non_escaped_worklist,
474 bool print_method = true);
475
476 // Adjust scalar_replaceable state after Connection Graph is built.
477 void adjust_scalar_replaceable_state(JavaObjectNode* jobj, Unique_Node_List &reducible_merges);
478
479 // Reevaluate Phis reducible status after 'obj' became NSR.
480 void revisit_reducible_phi_status(JavaObjectNode* jobj, Unique_Node_List& reducible_merges);
481
482 // Propagate NSR (Not scalar replaceable) state.
483 void find_scalar_replaceable_allocs(GrowableArray<JavaObjectNode*>& jobj_worklist, Unique_Node_List &reducible_merges);
484
485 // Optimize ideal graph.
486 void optimize_ideal_graph(GrowableArray<Node*>& ptr_cmp_worklist,
487 GrowableArray<MemBarStoreStoreNode*>& storestore_worklist);
488 // Optimize objects compare.
489 const TypeInt* optimize_ptr_compare(Node* left, Node* right);
490
491 // Returns unique corresponding java object or null.
492 JavaObjectNode* unique_java_object(Node *n) const;
493
494 // Add an edge of the specified type pointing to the specified target.
495 bool add_edge(PointsToNode* from, PointsToNode* to) {
496 assert(!from->is_Field() || from->as_Field()->is_oop(), "sanity");
497
498 if (to == phantom_obj) {
499 if (from->has_unknown_ptr()) {
500 return false; // already points to phantom_obj
501 }
502 from->set_has_unknown_ptr();
503 }
504
505 bool is_new = from->add_edge(to);
506 assert(to != phantom_obj || is_new, "sanity");
507 if (is_new) { // New edge?
508 assert(!_verify, "graph is incomplete");
509 is_new = to->add_use(from);
510 assert(is_new, "use should be also new");
511 }
512 return is_new;
513 }
514
515 // Add an edge from Field node to its base and back.
516 bool add_base(FieldNode* from, PointsToNode* to) {
517 assert(!to->is_Arraycopy(), "sanity");
518 if (to == phantom_obj) {
519 if (from->has_unknown_base()) {
520 return false; // already has phantom_obj base
521 }
522 from->set_has_unknown_base();
523 }
524 bool is_new = from->add_base(to);
525 assert(to != phantom_obj || is_new, "sanity");
526 if (is_new) { // New edge?
527 assert(!_verify, "graph is incomplete");
528 if (to == null_obj) {
529 return is_new; // Don't add fields to null pointer.
530 }
531 if (to->is_JavaObject()) {
532 is_new = to->add_edge(from);
533 } else {
534 is_new = to->add_base_use(from);
535 }
536 assert(is_new, "use should be also new");
537 }
538 return is_new;
539 }
540
541 // Helper functions
542 bool is_oop_field(Node* n, int offset, bool* unsafe);
543 static Node* find_second_addp(Node* addp, Node* n);
544 // offset of a field reference
545 int address_offset(Node* adr, PhaseValues* phase);
546
547 bool is_captured_store_address(Node* addp);
548
549 // Propagate unique types created for non-escaped allocated objects through the graph
550 void split_unique_types(GrowableArray<Node *> &alloc_worklist,
551 GrowableArray<ArrayCopyNode*> &arraycopy_worklist,
552 GrowableArray<MergeMemNode*> &mergemem_worklist,
553 Unique_Node_List &reducible_merges);
554
555 // Helper methods for unique types split.
556 bool split_AddP(Node *addp, Node *base);
557
558 PhiNode *create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, bool &new_created);
559 PhiNode *split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, uint rec_depth);
560
561 void move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis);
562 Node* find_inst_mem(Node* mem, int alias_idx,GrowableArray<PhiNode *> &orig_phi_worklist, uint rec_depth = 0);
563 Node* step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop);
564
565 Node_Array _node_map; // used for bookkeeping during type splitting
566 // Used for the following purposes:
567 // Memory Phi - most recent unique Phi split out
568 // from this Phi
569 // MemNode - new memory input for this node
570 // CheckCastPP - allocation that this is a cast of
571 // allocation - CheckCastPP of the allocation
572 // NarrowMem - newly created projection (type includes instance_id) from projection created
573 // before EA
574
575 // manage entries in _node_map
576
577 void set_map(Node* from, Node* to) {
578 ideal_nodes.push(from);
579 _node_map.map(from->_idx, to);
580 }
581
582 Node* get_map(int idx) { return _node_map[idx]; }
583
584 PhiNode* get_map_phi(int idx) {
585 Node* phi = _node_map[idx];
586 return (phi == nullptr) ? nullptr : phi->as_Phi();
587 }
588
589 // Returns true if there is an object in the scope of sfn that does not escape globally.
590 bool has_ea_local_in_scope(SafePointNode* sfn);
591
592 bool has_arg_escape(CallJavaNode* call);
593
594 // Notify optimizer that a node has been modified
595 void record_for_optimizer(Node *n);
596
597 // Compute the escape information
598 bool compute_escape();
599
600 // -------------------------------------------
601 // Methods related to Reduce Allocation Merges
602 bool has_non_reducible_merge(FieldNode* field, Unique_Node_List& reducible_merges);
603 PhiNode* create_selector(PhiNode* ophi) const;
604 void updates_after_load_split(Node* data_phi, Node* previous_load, GrowableArray<Node *> &alloc_worklist);
605 Node* split_castpp_load_through_phi(Node* curr_addp, Node* curr_load, Node* region, GrowableArray<Node*>* bases_for_loads, GrowableArray<Node *> &alloc_worklist);
606 void reset_scalar_replaceable_entries(PhiNode* ophi);
607 bool has_reducible_merge_base(AddPNode* n, Unique_Node_List &reducible_merges);
608 Node* specialize_cmp(Node* base, Node* curr_ctrl);
609 Node* specialize_castpp(Node* castpp, Node* base, Node* current_control);
610
611 bool can_reduce_cmp(Node* n, Node* cmp) const;
612 bool has_been_reduced(PhiNode* n, SafePointNode* sfpt) const;
613 bool can_reduce_phi(PhiNode* ophi) const;
614 bool can_reduce_check_users(Node* n, uint nesting) const;
615 bool can_reduce_phi_check_inputs(PhiNode* ophi) const;
616
617 void reduce_phi_on_field_access(Node* previous_addp, GrowableArray<Node *> &alloc_worklist);
618 void reduce_phi_on_castpp_field_load(Node* castpp, GrowableArray<Node*> &alloc_worklist);
619 void reduce_phi_on_cmp(Node* cmp);
620 bool reduce_phi_on_safepoints(PhiNode* ophi);
621 bool reduce_phi_on_safepoints_helper(Node* ophi, Node* cast, Node* selector, Unique_Node_List& safepoints);
622 void reduce_phi(PhiNode* ophi, GrowableArray<Node*> &alloc_worklist);
623
624 void set_not_scalar_replaceable(PointsToNode* ptn NOT_PRODUCT(COMMA const char* reason)) const {
625 #ifndef PRODUCT
626 if (_compile->directive()->TraceEscapeAnalysisOption) {
627 assert(ptn != nullptr, "should not be null");
628 ptn->dump_header(true);
629 tty->print_cr("is NSR. %s", reason);
630 }
631 #endif
632 ptn->set_scalar_replaceable(false);
633 }
634
635 #ifndef PRODUCT
636 void trace_es_update_helper(PointsToNode* ptn, PointsToNode::EscapeState es, bool fields, const char* reason) const;
637 const char* trace_propagate_message(PointsToNode* from) const;
638 const char* trace_arg_escape_message(CallNode* call) const;
639 const char* trace_merged_message(PointsToNode* other) const;
640 #endif
641
642 public:
643 ConnectionGraph(Compile *C, PhaseIterGVN *igvn, int iteration);
644
645 // Verify that SafePointScalarMerge nodes are correctly connected
646 static void verify_ram_nodes(Compile* C, Node* root);
647
648 // Check for non-escaping candidates
649 static bool has_candidates(Compile *C);
650
651 // Perform escape analysis
652 static void do_analysis(Compile *C, PhaseIterGVN *igvn);
653
654 bool not_global_escape(Node *n);
655
656 bool can_eliminate_lock(AbstractLockNode* alock);
657
658 // To be used by, e.g., BarrierSetC2 impls
659 Node* get_addp_base(Node* addp);
660
661 // Utility function for nodes that load an object
662 void add_objload_to_connection_graph(Node* n, Unique_Node_List* delayed_worklist);
663
664 // Add LocalVar node and edge if possible
665 void add_local_var_and_edge(Node* n, PointsToNode::EscapeState es, Node* to,
666 Unique_Node_List *delayed_worklist) {
667 PointsToNode* ptn = ptnode_adr(to->_idx);
668 if (delayed_worklist != nullptr) { // First iteration of CG construction
669 add_local_var(n, es);
670 if (ptn == nullptr) {
671 delayed_worklist->push(n);
672 return; // Process it later.
673 }
674 } else {
675 assert(ptn != nullptr, "node should be registered");
676 }
677 add_edge(ptnode_adr(n->_idx), ptn);
678 }
679
680 // Map ideal node to existing PointsTo node (usually phantom_object).
681 void map_ideal_node(Node *n, PointsToNode* ptn) {
682 assert(ptn != nullptr, "only existing PointsTo node");
683 _nodes.at_put(n->_idx, ptn);
684 }
685
686 void add_to_congraph_unsafe_access(Node* n, uint opcode, Unique_Node_List* delayed_worklist);
687 bool add_final_edges_unsafe_access(Node* n, uint opcode);
688
689 #ifndef PRODUCT
690 static int _no_escape_counter;
691 static int _arg_escape_counter;
692 static int _global_escape_counter;
693 void dump(GrowableArray<PointsToNode*>& ptnodes_worklist);
694 static void print_statistics();
695 void escape_state_statistics(GrowableArray<JavaObjectNode*>& java_objects_worklist);
696 #endif
697 };
698
699 inline PointsToNode::PointsToNode(ConnectionGraph *CG, Node* n, EscapeState es, NodeType type):
700 _edges(CG->_compile->comp_arena(), 2, 0, nullptr),
701 _uses (CG->_compile->comp_arena(), 2, 0, nullptr),
702 _type((u1)type),
703 _flags(ScalarReplaceable),
704 _escape((u1)es),
705 _fields_escape((u1)es),
706 _node(n),
707 _idx(n->_idx),
708 _pidx(CG->next_pidx()) {
709 assert(n != nullptr && es != UnknownEscape, "sanity");
710 }
711
712 inline FieldNode::FieldNode(ConnectionGraph *CG, Node* n, EscapeState es, int offs, bool is_oop):
713 PointsToNode(CG, n, es, Field),
714 _bases(CG->_compile->comp_arena(), 2, 0, nullptr),
715 _offset(offs), _is_oop(is_oop),
716 _has_unknown_base(false) {
717 }
718
719 #endif // SHARE_OPTO_ESCAPE_HPP