Sat, 06 Nov 2010 20:35:36 -0700
6991188: C2 Crashes while compiling method
Summary: Do several iterations to build EA Connection Graph.
Reviewed-by: never, twisti, ysr
1 /*
2 * Copyright (c) 2005, 2009, 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 #include "incls/_precompiled.incl"
26 #include "incls/_escape.cpp.incl"
28 void PointsToNode::add_edge(uint targIdx, PointsToNode::EdgeType et) {
29 uint v = (targIdx << EdgeShift) + ((uint) et);
30 if (_edges == NULL) {
31 Arena *a = Compile::current()->comp_arena();
32 _edges = new(a) GrowableArray<uint>(a, INITIAL_EDGE_COUNT, 0, 0);
33 }
34 _edges->append_if_missing(v);
35 }
37 void PointsToNode::remove_edge(uint targIdx, PointsToNode::EdgeType et) {
38 uint v = (targIdx << EdgeShift) + ((uint) et);
40 _edges->remove(v);
41 }
43 #ifndef PRODUCT
44 static const char *node_type_names[] = {
45 "UnknownType",
46 "JavaObject",
47 "LocalVar",
48 "Field"
49 };
51 static const char *esc_names[] = {
52 "UnknownEscape",
53 "NoEscape",
54 "ArgEscape",
55 "GlobalEscape"
56 };
58 static const char *edge_type_suffix[] = {
59 "?", // UnknownEdge
60 "P", // PointsToEdge
61 "D", // DeferredEdge
62 "F" // FieldEdge
63 };
65 void PointsToNode::dump(bool print_state) const {
66 NodeType nt = node_type();
67 tty->print("%s ", node_type_names[(int) nt]);
68 if (print_state) {
69 EscapeState es = escape_state();
70 tty->print("%s %s ", esc_names[(int) es], _scalar_replaceable ? "":"NSR");
71 }
72 tty->print("[[");
73 for (uint i = 0; i < edge_count(); i++) {
74 tty->print(" %d%s", edge_target(i), edge_type_suffix[(int) edge_type(i)]);
75 }
76 tty->print("]] ");
77 if (_node == NULL)
78 tty->print_cr("<null>");
79 else
80 _node->dump();
81 }
82 #endif
84 ConnectionGraph::ConnectionGraph(Compile * C, PhaseIterGVN *igvn) :
85 _nodes(C->comp_arena(), C->unique(), C->unique(), PointsToNode()),
86 _processed(C->comp_arena()),
87 _collecting(true),
88 _progress(false),
89 _compile(C),
90 _igvn(igvn),
91 _node_map(C->comp_arena()) {
93 _phantom_object = C->top()->_idx,
94 add_node(C->top(), PointsToNode::JavaObject, PointsToNode::GlobalEscape,true);
96 // Add ConP(#NULL) and ConN(#NULL) nodes.
97 Node* oop_null = igvn->zerocon(T_OBJECT);
98 _oop_null = oop_null->_idx;
99 assert(_oop_null < C->unique(), "should be created already");
100 add_node(oop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true);
102 if (UseCompressedOops) {
103 Node* noop_null = igvn->zerocon(T_NARROWOOP);
104 _noop_null = noop_null->_idx;
105 assert(_noop_null < C->unique(), "should be created already");
106 add_node(noop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true);
107 }
108 }
110 void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) {
111 PointsToNode *f = ptnode_adr(from_i);
112 PointsToNode *t = ptnode_adr(to_i);
114 assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");
115 assert(f->node_type() == PointsToNode::LocalVar || f->node_type() == PointsToNode::Field, "invalid source of PointsTo edge");
116 assert(t->node_type() == PointsToNode::JavaObject, "invalid destination of PointsTo edge");
117 add_edge(f, to_i, PointsToNode::PointsToEdge);
118 }
120 void ConnectionGraph::add_deferred_edge(uint from_i, uint to_i) {
121 PointsToNode *f = ptnode_adr(from_i);
122 PointsToNode *t = ptnode_adr(to_i);
124 assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");
125 assert(f->node_type() == PointsToNode::LocalVar || f->node_type() == PointsToNode::Field, "invalid source of Deferred edge");
126 assert(t->node_type() == PointsToNode::LocalVar || t->node_type() == PointsToNode::Field, "invalid destination of Deferred edge");
127 // don't add a self-referential edge, this can occur during removal of
128 // deferred edges
129 if (from_i != to_i)
130 add_edge(f, to_i, PointsToNode::DeferredEdge);
131 }
133 int ConnectionGraph::address_offset(Node* adr, PhaseTransform *phase) {
134 const Type *adr_type = phase->type(adr);
135 if (adr->is_AddP() && adr_type->isa_oopptr() == NULL &&
136 adr->in(AddPNode::Address)->is_Proj() &&
137 adr->in(AddPNode::Address)->in(0)->is_Allocate()) {
138 // We are computing a raw address for a store captured by an Initialize
139 // compute an appropriate address type. AddP cases #3 and #5 (see below).
140 int offs = (int)phase->find_intptr_t_con(adr->in(AddPNode::Offset), Type::OffsetBot);
141 assert(offs != Type::OffsetBot ||
142 adr->in(AddPNode::Address)->in(0)->is_AllocateArray(),
143 "offset must be a constant or it is initialization of array");
144 return offs;
145 }
146 const TypePtr *t_ptr = adr_type->isa_ptr();
147 assert(t_ptr != NULL, "must be a pointer type");
148 return t_ptr->offset();
149 }
151 void ConnectionGraph::add_field_edge(uint from_i, uint to_i, int offset) {
152 PointsToNode *f = ptnode_adr(from_i);
153 PointsToNode *t = ptnode_adr(to_i);
155 assert(f->node_type() != PointsToNode::UnknownType && t->node_type() != PointsToNode::UnknownType, "node types must be set");
156 assert(f->node_type() == PointsToNode::JavaObject, "invalid destination of Field edge");
157 assert(t->node_type() == PointsToNode::Field, "invalid destination of Field edge");
158 assert (t->offset() == -1 || t->offset() == offset, "conflicting field offsets");
159 t->set_offset(offset);
161 add_edge(f, to_i, PointsToNode::FieldEdge);
162 }
164 void ConnectionGraph::set_escape_state(uint ni, PointsToNode::EscapeState es) {
165 PointsToNode *npt = ptnode_adr(ni);
166 PointsToNode::EscapeState old_es = npt->escape_state();
167 if (es > old_es)
168 npt->set_escape_state(es);
169 }
171 void ConnectionGraph::add_node(Node *n, PointsToNode::NodeType nt,
172 PointsToNode::EscapeState es, bool done) {
173 PointsToNode* ptadr = ptnode_adr(n->_idx);
174 ptadr->_node = n;
175 ptadr->set_node_type(nt);
177 // inline set_escape_state(idx, es);
178 PointsToNode::EscapeState old_es = ptadr->escape_state();
179 if (es > old_es)
180 ptadr->set_escape_state(es);
182 if (done)
183 _processed.set(n->_idx);
184 }
186 PointsToNode::EscapeState ConnectionGraph::escape_state(Node *n) {
187 uint idx = n->_idx;
188 PointsToNode::EscapeState es;
190 // If we are still collecting or there were no non-escaping allocations
191 // we don't know the answer yet
192 if (_collecting)
193 return PointsToNode::UnknownEscape;
195 // if the node was created after the escape computation, return
196 // UnknownEscape
197 if (idx >= nodes_size())
198 return PointsToNode::UnknownEscape;
200 es = ptnode_adr(idx)->escape_state();
202 // if we have already computed a value, return it
203 if (es != PointsToNode::UnknownEscape &&
204 ptnode_adr(idx)->node_type() == PointsToNode::JavaObject)
205 return es;
207 // PointsTo() calls n->uncast() which can return a new ideal node.
208 if (n->uncast()->_idx >= nodes_size())
209 return PointsToNode::UnknownEscape;
211 PointsToNode::EscapeState orig_es = es;
213 // compute max escape state of anything this node could point to
214 VectorSet ptset(Thread::current()->resource_area());
215 PointsTo(ptset, n);
216 for(VectorSetI i(&ptset); i.test() && es != PointsToNode::GlobalEscape; ++i) {
217 uint pt = i.elem;
218 PointsToNode::EscapeState pes = ptnode_adr(pt)->escape_state();
219 if (pes > es)
220 es = pes;
221 }
222 if (orig_es != es) {
223 // cache the computed escape state
224 assert(es != PointsToNode::UnknownEscape, "should have computed an escape state");
225 ptnode_adr(idx)->set_escape_state(es);
226 } // orig_es could be PointsToNode::UnknownEscape
227 return es;
228 }
230 void ConnectionGraph::PointsTo(VectorSet &ptset, Node * n) {
231 VectorSet visited(Thread::current()->resource_area());
232 GrowableArray<uint> worklist;
234 #ifdef ASSERT
235 Node *orig_n = n;
236 #endif
238 n = n->uncast();
239 PointsToNode* npt = ptnode_adr(n->_idx);
241 // If we have a JavaObject, return just that object
242 if (npt->node_type() == PointsToNode::JavaObject) {
243 ptset.set(n->_idx);
244 return;
245 }
246 #ifdef ASSERT
247 if (npt->_node == NULL) {
248 if (orig_n != n)
249 orig_n->dump();
250 n->dump();
251 assert(npt->_node != NULL, "unregistered node");
252 }
253 #endif
254 worklist.push(n->_idx);
255 while(worklist.length() > 0) {
256 int ni = worklist.pop();
257 if (visited.test_set(ni))
258 continue;
260 PointsToNode* pn = ptnode_adr(ni);
261 // ensure that all inputs of a Phi have been processed
262 assert(!_collecting || !pn->_node->is_Phi() || _processed.test(ni),"");
264 int edges_processed = 0;
265 uint e_cnt = pn->edge_count();
266 for (uint e = 0; e < e_cnt; e++) {
267 uint etgt = pn->edge_target(e);
268 PointsToNode::EdgeType et = pn->edge_type(e);
269 if (et == PointsToNode::PointsToEdge) {
270 ptset.set(etgt);
271 edges_processed++;
272 } else if (et == PointsToNode::DeferredEdge) {
273 worklist.push(etgt);
274 edges_processed++;
275 } else {
276 assert(false,"neither PointsToEdge or DeferredEdge");
277 }
278 }
279 if (edges_processed == 0) {
280 // no deferred or pointsto edges found. Assume the value was set
281 // outside this method. Add the phantom object to the pointsto set.
282 ptset.set(_phantom_object);
283 }
284 }
285 }
287 void ConnectionGraph::remove_deferred(uint ni, GrowableArray<uint>* deferred_edges, VectorSet* visited) {
288 // This method is most expensive during ConnectionGraph construction.
289 // Reuse vectorSet and an additional growable array for deferred edges.
290 deferred_edges->clear();
291 visited->Clear();
293 visited->set(ni);
294 PointsToNode *ptn = ptnode_adr(ni);
296 // Mark current edges as visited and move deferred edges to separate array.
297 for (uint i = 0; i < ptn->edge_count(); ) {
298 uint t = ptn->edge_target(i);
299 #ifdef ASSERT
300 assert(!visited->test_set(t), "expecting no duplications");
301 #else
302 visited->set(t);
303 #endif
304 if (ptn->edge_type(i) == PointsToNode::DeferredEdge) {
305 ptn->remove_edge(t, PointsToNode::DeferredEdge);
306 deferred_edges->append(t);
307 } else {
308 i++;
309 }
310 }
311 for (int next = 0; next < deferred_edges->length(); ++next) {
312 uint t = deferred_edges->at(next);
313 PointsToNode *ptt = ptnode_adr(t);
314 uint e_cnt = ptt->edge_count();
315 for (uint e = 0; e < e_cnt; e++) {
316 uint etgt = ptt->edge_target(e);
317 if (visited->test_set(etgt))
318 continue;
320 PointsToNode::EdgeType et = ptt->edge_type(e);
321 if (et == PointsToNode::PointsToEdge) {
322 add_pointsto_edge(ni, etgt);
323 if(etgt == _phantom_object) {
324 // Special case - field set outside (globally escaping).
325 ptn->set_escape_state(PointsToNode::GlobalEscape);
326 }
327 } else if (et == PointsToNode::DeferredEdge) {
328 deferred_edges->append(etgt);
329 } else {
330 assert(false,"invalid connection graph");
331 }
332 }
333 }
334 }
337 // Add an edge to node given by "to_i" from any field of adr_i whose offset
338 // matches "offset" A deferred edge is added if to_i is a LocalVar, and
339 // a pointsto edge is added if it is a JavaObject
341 void ConnectionGraph::add_edge_from_fields(uint adr_i, uint to_i, int offs) {
342 PointsToNode* an = ptnode_adr(adr_i);
343 PointsToNode* to = ptnode_adr(to_i);
344 bool deferred = (to->node_type() == PointsToNode::LocalVar);
346 for (uint fe = 0; fe < an->edge_count(); fe++) {
347 assert(an->edge_type(fe) == PointsToNode::FieldEdge, "expecting a field edge");
348 int fi = an->edge_target(fe);
349 PointsToNode* pf = ptnode_adr(fi);
350 int po = pf->offset();
351 if (po == offs || po == Type::OffsetBot || offs == Type::OffsetBot) {
352 if (deferred)
353 add_deferred_edge(fi, to_i);
354 else
355 add_pointsto_edge(fi, to_i);
356 }
357 }
358 }
360 // Add a deferred edge from node given by "from_i" to any field of adr_i
361 // whose offset matches "offset".
362 void ConnectionGraph::add_deferred_edge_to_fields(uint from_i, uint adr_i, int offs) {
363 PointsToNode* an = ptnode_adr(adr_i);
364 for (uint fe = 0; fe < an->edge_count(); fe++) {
365 assert(an->edge_type(fe) == PointsToNode::FieldEdge, "expecting a field edge");
366 int fi = an->edge_target(fe);
367 PointsToNode* pf = ptnode_adr(fi);
368 int po = pf->offset();
369 if (pf->edge_count() == 0) {
370 // we have not seen any stores to this field, assume it was set outside this method
371 add_pointsto_edge(fi, _phantom_object);
372 }
373 if (po == offs || po == Type::OffsetBot || offs == Type::OffsetBot) {
374 add_deferred_edge(from_i, fi);
375 }
376 }
377 }
379 // Helper functions
381 static Node* get_addp_base(Node *addp) {
382 assert(addp->is_AddP(), "must be AddP");
383 //
384 // AddP cases for Base and Address inputs:
385 // case #1. Direct object's field reference:
386 // Allocate
387 // |
388 // Proj #5 ( oop result )
389 // |
390 // CheckCastPP (cast to instance type)
391 // | |
392 // AddP ( base == address )
393 //
394 // case #2. Indirect object's field reference:
395 // Phi
396 // |
397 // CastPP (cast to instance type)
398 // | |
399 // AddP ( base == address )
400 //
401 // case #3. Raw object's field reference for Initialize node:
402 // Allocate
403 // |
404 // Proj #5 ( oop result )
405 // top |
406 // \ |
407 // AddP ( base == top )
408 //
409 // case #4. Array's element reference:
410 // {CheckCastPP | CastPP}
411 // | | |
412 // | AddP ( array's element offset )
413 // | |
414 // AddP ( array's offset )
415 //
416 // case #5. Raw object's field reference for arraycopy stub call:
417 // The inline_native_clone() case when the arraycopy stub is called
418 // after the allocation before Initialize and CheckCastPP nodes.
419 // Allocate
420 // |
421 // Proj #5 ( oop result )
422 // | |
423 // AddP ( base == address )
424 //
425 // case #6. Constant Pool, ThreadLocal, CastX2P or
426 // Raw object's field reference:
427 // {ConP, ThreadLocal, CastX2P, raw Load}
428 // top |
429 // \ |
430 // AddP ( base == top )
431 //
432 // case #7. Klass's field reference.
433 // LoadKlass
434 // | |
435 // AddP ( base == address )
436 //
437 // case #8. narrow Klass's field reference.
438 // LoadNKlass
439 // |
440 // DecodeN
441 // | |
442 // AddP ( base == address )
443 //
444 Node *base = addp->in(AddPNode::Base)->uncast();
445 if (base->is_top()) { // The AddP case #3 and #6.
446 base = addp->in(AddPNode::Address)->uncast();
447 while (base->is_AddP()) {
448 // Case #6 (unsafe access) may have several chained AddP nodes.
449 assert(base->in(AddPNode::Base)->is_top(), "expected unsafe access address only");
450 base = base->in(AddPNode::Address)->uncast();
451 }
452 assert(base->Opcode() == Op_ConP || base->Opcode() == Op_ThreadLocal ||
453 base->Opcode() == Op_CastX2P || base->is_DecodeN() ||
454 (base->is_Mem() && base->bottom_type() == TypeRawPtr::NOTNULL) ||
455 (base->is_Proj() && base->in(0)->is_Allocate()), "sanity");
456 }
457 return base;
458 }
460 static Node* find_second_addp(Node* addp, Node* n) {
461 assert(addp->is_AddP() && addp->outcnt() > 0, "Don't process dead nodes");
463 Node* addp2 = addp->raw_out(0);
464 if (addp->outcnt() == 1 && addp2->is_AddP() &&
465 addp2->in(AddPNode::Base) == n &&
466 addp2->in(AddPNode::Address) == addp) {
468 assert(addp->in(AddPNode::Base) == n, "expecting the same base");
469 //
470 // Find array's offset to push it on worklist first and
471 // as result process an array's element offset first (pushed second)
472 // to avoid CastPP for the array's offset.
473 // Otherwise the inserted CastPP (LocalVar) will point to what
474 // the AddP (Field) points to. Which would be wrong since
475 // the algorithm expects the CastPP has the same point as
476 // as AddP's base CheckCastPP (LocalVar).
477 //
478 // ArrayAllocation
479 // |
480 // CheckCastPP
481 // |
482 // memProj (from ArrayAllocation CheckCastPP)
483 // | ||
484 // | || Int (element index)
485 // | || | ConI (log(element size))
486 // | || | /
487 // | || LShift
488 // | || /
489 // | AddP (array's element offset)
490 // | |
491 // | | ConI (array's offset: #12(32-bits) or #24(64-bits))
492 // | / /
493 // AddP (array's offset)
494 // |
495 // Load/Store (memory operation on array's element)
496 //
497 return addp2;
498 }
499 return NULL;
500 }
502 //
503 // Adjust the type and inputs of an AddP which computes the
504 // address of a field of an instance
505 //
506 bool ConnectionGraph::split_AddP(Node *addp, Node *base, PhaseGVN *igvn) {
507 const TypeOopPtr *base_t = igvn->type(base)->isa_oopptr();
508 assert(base_t != NULL && base_t->is_known_instance(), "expecting instance oopptr");
509 const TypeOopPtr *t = igvn->type(addp)->isa_oopptr();
510 if (t == NULL) {
511 // We are computing a raw address for a store captured by an Initialize
512 // compute an appropriate address type (cases #3 and #5).
513 assert(igvn->type(addp) == TypeRawPtr::NOTNULL, "must be raw pointer");
514 assert(addp->in(AddPNode::Address)->is_Proj(), "base of raw address must be result projection from allocation");
515 intptr_t offs = (int)igvn->find_intptr_t_con(addp->in(AddPNode::Offset), Type::OffsetBot);
516 assert(offs != Type::OffsetBot, "offset must be a constant");
517 t = base_t->add_offset(offs)->is_oopptr();
518 }
519 int inst_id = base_t->instance_id();
520 assert(!t->is_known_instance() || t->instance_id() == inst_id,
521 "old type must be non-instance or match new type");
523 // The type 't' could be subclass of 'base_t'.
524 // As result t->offset() could be large then base_t's size and it will
525 // cause the failure in add_offset() with narrow oops since TypeOopPtr()
526 // constructor verifies correctness of the offset.
527 //
528 // It could happened on subclass's branch (from the type profiling
529 // inlining) which was not eliminated during parsing since the exactness
530 // of the allocation type was not propagated to the subclass type check.
531 //
532 // Or the type 't' could be not related to 'base_t' at all.
533 // It could happened when CHA type is different from MDO type on a dead path
534 // (for example, from instanceof check) which is not collapsed during parsing.
535 //
536 // Do nothing for such AddP node and don't process its users since
537 // this code branch will go away.
538 //
539 if (!t->is_known_instance() &&
540 !base_t->klass()->is_subtype_of(t->klass())) {
541 return false; // bail out
542 }
544 const TypeOopPtr *tinst = base_t->add_offset(t->offset())->is_oopptr();
545 // Do NOT remove the next line: ensure a new alias index is allocated
546 // for the instance type. Note: C++ will not remove it since the call
547 // has side effect.
548 int alias_idx = _compile->get_alias_index(tinst);
549 igvn->set_type(addp, tinst);
550 // record the allocation in the node map
551 assert(ptnode_adr(addp->_idx)->_node != NULL, "should be registered");
552 set_map(addp->_idx, get_map(base->_idx));
554 // Set addp's Base and Address to 'base'.
555 Node *abase = addp->in(AddPNode::Base);
556 Node *adr = addp->in(AddPNode::Address);
557 if (adr->is_Proj() && adr->in(0)->is_Allocate() &&
558 adr->in(0)->_idx == (uint)inst_id) {
559 // Skip AddP cases #3 and #5.
560 } else {
561 assert(!abase->is_top(), "sanity"); // AddP case #3
562 if (abase != base) {
563 igvn->hash_delete(addp);
564 addp->set_req(AddPNode::Base, base);
565 if (abase == adr) {
566 addp->set_req(AddPNode::Address, base);
567 } else {
568 // AddP case #4 (adr is array's element offset AddP node)
569 #ifdef ASSERT
570 const TypeOopPtr *atype = igvn->type(adr)->isa_oopptr();
571 assert(adr->is_AddP() && atype != NULL &&
572 atype->instance_id() == inst_id, "array's element offset should be processed first");
573 #endif
574 }
575 igvn->hash_insert(addp);
576 }
577 }
578 // Put on IGVN worklist since at least addp's type was changed above.
579 record_for_optimizer(addp);
580 return true;
581 }
583 //
584 // Create a new version of orig_phi if necessary. Returns either the newly
585 // created phi or an existing phi. Sets create_new to indicate wheter a new
586 // phi was created. Cache the last newly created phi in the node map.
587 //
588 PhiNode *ConnectionGraph::create_split_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn, bool &new_created) {
589 Compile *C = _compile;
590 new_created = false;
591 int phi_alias_idx = C->get_alias_index(orig_phi->adr_type());
592 // nothing to do if orig_phi is bottom memory or matches alias_idx
593 if (phi_alias_idx == alias_idx) {
594 return orig_phi;
595 }
596 // Have we recently created a Phi for this alias index?
597 PhiNode *result = get_map_phi(orig_phi->_idx);
598 if (result != NULL && C->get_alias_index(result->adr_type()) == alias_idx) {
599 return result;
600 }
601 // Previous check may fail when the same wide memory Phi was split into Phis
602 // for different memory slices. Search all Phis for this region.
603 if (result != NULL) {
604 Node* region = orig_phi->in(0);
605 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
606 Node* phi = region->fast_out(i);
607 if (phi->is_Phi() &&
608 C->get_alias_index(phi->as_Phi()->adr_type()) == alias_idx) {
609 assert(phi->_idx >= nodes_size(), "only new Phi per instance memory slice");
610 return phi->as_Phi();
611 }
612 }
613 }
614 if ((int)C->unique() + 2*NodeLimitFudgeFactor > MaxNodeLimit) {
615 if (C->do_escape_analysis() == true && !C->failing()) {
616 // Retry compilation without escape analysis.
617 // If this is the first failure, the sentinel string will "stick"
618 // to the Compile object, and the C2Compiler will see it and retry.
619 C->record_failure(C2Compiler::retry_no_escape_analysis());
620 }
621 return NULL;
622 }
623 orig_phi_worklist.append_if_missing(orig_phi);
624 const TypePtr *atype = C->get_adr_type(alias_idx);
625 result = PhiNode::make(orig_phi->in(0), NULL, Type::MEMORY, atype);
626 C->copy_node_notes_to(result, orig_phi);
627 igvn->set_type(result, result->bottom_type());
628 record_for_optimizer(result);
630 debug_only(Node* pn = ptnode_adr(orig_phi->_idx)->_node;)
631 assert(pn == NULL || pn == orig_phi, "wrong node");
632 set_map(orig_phi->_idx, result);
633 ptnode_adr(orig_phi->_idx)->_node = orig_phi;
635 new_created = true;
636 return result;
637 }
639 //
640 // Return a new version of Memory Phi "orig_phi" with the inputs having the
641 // specified alias index.
642 //
643 PhiNode *ConnectionGraph::split_memory_phi(PhiNode *orig_phi, int alias_idx, GrowableArray<PhiNode *> &orig_phi_worklist, PhaseGVN *igvn) {
645 assert(alias_idx != Compile::AliasIdxBot, "can't split out bottom memory");
646 Compile *C = _compile;
647 bool new_phi_created;
648 PhiNode *result = create_split_phi(orig_phi, alias_idx, orig_phi_worklist, igvn, new_phi_created);
649 if (!new_phi_created) {
650 return result;
651 }
653 GrowableArray<PhiNode *> phi_list;
654 GrowableArray<uint> cur_input;
656 PhiNode *phi = orig_phi;
657 uint idx = 1;
658 bool finished = false;
659 while(!finished) {
660 while (idx < phi->req()) {
661 Node *mem = find_inst_mem(phi->in(idx), alias_idx, orig_phi_worklist, igvn);
662 if (mem != NULL && mem->is_Phi()) {
663 PhiNode *newphi = create_split_phi(mem->as_Phi(), alias_idx, orig_phi_worklist, igvn, new_phi_created);
664 if (new_phi_created) {
665 // found an phi for which we created a new split, push current one on worklist and begin
666 // processing new one
667 phi_list.push(phi);
668 cur_input.push(idx);
669 phi = mem->as_Phi();
670 result = newphi;
671 idx = 1;
672 continue;
673 } else {
674 mem = newphi;
675 }
676 }
677 if (C->failing()) {
678 return NULL;
679 }
680 result->set_req(idx++, mem);
681 }
682 #ifdef ASSERT
683 // verify that the new Phi has an input for each input of the original
684 assert( phi->req() == result->req(), "must have same number of inputs.");
685 assert( result->in(0) != NULL && result->in(0) == phi->in(0), "regions must match");
686 #endif
687 // Check if all new phi's inputs have specified alias index.
688 // Otherwise use old phi.
689 for (uint i = 1; i < phi->req(); i++) {
690 Node* in = result->in(i);
691 assert((phi->in(i) == NULL) == (in == NULL), "inputs must correspond.");
692 }
693 // we have finished processing a Phi, see if there are any more to do
694 finished = (phi_list.length() == 0 );
695 if (!finished) {
696 phi = phi_list.pop();
697 idx = cur_input.pop();
698 PhiNode *prev_result = get_map_phi(phi->_idx);
699 prev_result->set_req(idx++, result);
700 result = prev_result;
701 }
702 }
703 return result;
704 }
707 //
708 // The next methods are derived from methods in MemNode.
709 //
710 static Node *step_through_mergemem(MergeMemNode *mmem, int alias_idx, const TypeOopPtr *toop) {
711 Node *mem = mmem;
712 // TypeOopPtr::NOTNULL+any is an OOP with unknown offset - generally
713 // means an array I have not precisely typed yet. Do not do any
714 // alias stuff with it any time soon.
715 if( toop->base() != Type::AnyPtr &&
716 !(toop->klass() != NULL &&
717 toop->klass()->is_java_lang_Object() &&
718 toop->offset() == Type::OffsetBot) ) {
719 mem = mmem->memory_at(alias_idx);
720 // Update input if it is progress over what we have now
721 }
722 return mem;
723 }
725 //
726 // Move memory users to their memory slices.
727 //
728 void ConnectionGraph::move_inst_mem(Node* n, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *igvn) {
729 Compile* C = _compile;
731 const TypePtr* tp = igvn->type(n->in(MemNode::Address))->isa_ptr();
732 assert(tp != NULL, "ptr type");
733 int alias_idx = C->get_alias_index(tp);
734 int general_idx = C->get_general_index(alias_idx);
736 // Move users first
737 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
738 Node* use = n->fast_out(i);
739 if (use->is_MergeMem()) {
740 MergeMemNode* mmem = use->as_MergeMem();
741 assert(n == mmem->memory_at(alias_idx), "should be on instance memory slice");
742 if (n != mmem->memory_at(general_idx) || alias_idx == general_idx) {
743 continue; // Nothing to do
744 }
745 // Replace previous general reference to mem node.
746 uint orig_uniq = C->unique();
747 Node* m = find_inst_mem(n, general_idx, orig_phis, igvn);
748 assert(orig_uniq == C->unique(), "no new nodes");
749 mmem->set_memory_at(general_idx, m);
750 --imax;
751 --i;
752 } else if (use->is_MemBar()) {
753 assert(!use->is_Initialize(), "initializing stores should not be moved");
754 if (use->req() > MemBarNode::Precedent &&
755 use->in(MemBarNode::Precedent) == n) {
756 // Don't move related membars.
757 record_for_optimizer(use);
758 continue;
759 }
760 tp = use->as_MemBar()->adr_type()->isa_ptr();
761 if (tp != NULL && C->get_alias_index(tp) == alias_idx ||
762 alias_idx == general_idx) {
763 continue; // Nothing to do
764 }
765 // Move to general memory slice.
766 uint orig_uniq = C->unique();
767 Node* m = find_inst_mem(n, general_idx, orig_phis, igvn);
768 assert(orig_uniq == C->unique(), "no new nodes");
769 igvn->hash_delete(use);
770 imax -= use->replace_edge(n, m);
771 igvn->hash_insert(use);
772 record_for_optimizer(use);
773 --i;
774 #ifdef ASSERT
775 } else if (use->is_Mem()) {
776 if (use->Opcode() == Op_StoreCM && use->in(MemNode::OopStore) == n) {
777 // Don't move related cardmark.
778 continue;
779 }
780 // Memory nodes should have new memory input.
781 tp = igvn->type(use->in(MemNode::Address))->isa_ptr();
782 assert(tp != NULL, "ptr type");
783 int idx = C->get_alias_index(tp);
784 assert(get_map(use->_idx) != NULL || idx == alias_idx,
785 "Following memory nodes should have new memory input or be on the same memory slice");
786 } else if (use->is_Phi()) {
787 // Phi nodes should be split and moved already.
788 tp = use->as_Phi()->adr_type()->isa_ptr();
789 assert(tp != NULL, "ptr type");
790 int idx = C->get_alias_index(tp);
791 assert(idx == alias_idx, "Following Phi nodes should be on the same memory slice");
792 } else {
793 use->dump();
794 assert(false, "should not be here");
795 #endif
796 }
797 }
798 }
800 //
801 // Search memory chain of "mem" to find a MemNode whose address
802 // is the specified alias index.
803 //
804 Node* ConnectionGraph::find_inst_mem(Node *orig_mem, int alias_idx, GrowableArray<PhiNode *> &orig_phis, PhaseGVN *phase) {
805 if (orig_mem == NULL)
806 return orig_mem;
807 Compile* C = phase->C;
808 const TypeOopPtr *toop = C->get_adr_type(alias_idx)->isa_oopptr();
809 bool is_instance = (toop != NULL) && toop->is_known_instance();
810 Node *start_mem = C->start()->proj_out(TypeFunc::Memory);
811 Node *prev = NULL;
812 Node *result = orig_mem;
813 while (prev != result) {
814 prev = result;
815 if (result == start_mem)
816 break; // hit one of our sentinels
817 if (result->is_Mem()) {
818 const Type *at = phase->type(result->in(MemNode::Address));
819 if (at != Type::TOP) {
820 assert (at->isa_ptr() != NULL, "pointer type required.");
821 int idx = C->get_alias_index(at->is_ptr());
822 if (idx == alias_idx)
823 break;
824 }
825 result = result->in(MemNode::Memory);
826 }
827 if (!is_instance)
828 continue; // don't search further for non-instance types
829 // skip over a call which does not affect this memory slice
830 if (result->is_Proj() && result->as_Proj()->_con == TypeFunc::Memory) {
831 Node *proj_in = result->in(0);
832 if (proj_in->is_Allocate() && proj_in->_idx == (uint)toop->instance_id()) {
833 break; // hit one of our sentinels
834 } else if (proj_in->is_Call()) {
835 CallNode *call = proj_in->as_Call();
836 if (!call->may_modify(toop, phase)) {
837 result = call->in(TypeFunc::Memory);
838 }
839 } else if (proj_in->is_Initialize()) {
840 AllocateNode* alloc = proj_in->as_Initialize()->allocation();
841 // Stop if this is the initialization for the object instance which
842 // which contains this memory slice, otherwise skip over it.
843 if (alloc == NULL || alloc->_idx != (uint)toop->instance_id()) {
844 result = proj_in->in(TypeFunc::Memory);
845 }
846 } else if (proj_in->is_MemBar()) {
847 result = proj_in->in(TypeFunc::Memory);
848 }
849 } else if (result->is_MergeMem()) {
850 MergeMemNode *mmem = result->as_MergeMem();
851 result = step_through_mergemem(mmem, alias_idx, toop);
852 if (result == mmem->base_memory()) {
853 // Didn't find instance memory, search through general slice recursively.
854 result = mmem->memory_at(C->get_general_index(alias_idx));
855 result = find_inst_mem(result, alias_idx, orig_phis, phase);
856 if (C->failing()) {
857 return NULL;
858 }
859 mmem->set_memory_at(alias_idx, result);
860 }
861 } else if (result->is_Phi() &&
862 C->get_alias_index(result->as_Phi()->adr_type()) != alias_idx) {
863 Node *un = result->as_Phi()->unique_input(phase);
864 if (un != NULL) {
865 orig_phis.append_if_missing(result->as_Phi());
866 result = un;
867 } else {
868 break;
869 }
870 } else if (result->is_ClearArray()) {
871 if (!ClearArrayNode::step_through(&result, (uint)toop->instance_id(), phase)) {
872 // Can not bypass initialization of the instance
873 // we are looking for.
874 break;
875 }
876 // Otherwise skip it (the call updated 'result' value).
877 } else if (result->Opcode() == Op_SCMemProj) {
878 assert(result->in(0)->is_LoadStore(), "sanity");
879 const Type *at = phase->type(result->in(0)->in(MemNode::Address));
880 if (at != Type::TOP) {
881 assert (at->isa_ptr() != NULL, "pointer type required.");
882 int idx = C->get_alias_index(at->is_ptr());
883 assert(idx != alias_idx, "Object is not scalar replaceable if a LoadStore node access its field");
884 break;
885 }
886 result = result->in(0)->in(MemNode::Memory);
887 }
888 }
889 if (result->is_Phi()) {
890 PhiNode *mphi = result->as_Phi();
891 assert(mphi->bottom_type() == Type::MEMORY, "memory phi required");
892 const TypePtr *t = mphi->adr_type();
893 if (C->get_alias_index(t) != alias_idx) {
894 // Create a new Phi with the specified alias index type.
895 result = split_memory_phi(mphi, alias_idx, orig_phis, phase);
896 } else if (!is_instance) {
897 // Push all non-instance Phis on the orig_phis worklist to update inputs
898 // during Phase 4 if needed.
899 orig_phis.append_if_missing(mphi);
900 }
901 }
902 // the result is either MemNode, PhiNode, InitializeNode.
903 return result;
904 }
906 //
907 // Convert the types of unescaped object to instance types where possible,
908 // propagate the new type information through the graph, and update memory
909 // edges and MergeMem inputs to reflect the new type.
910 //
911 // We start with allocations (and calls which may be allocations) on alloc_worklist.
912 // The processing is done in 4 phases:
913 //
914 // Phase 1: Process possible allocations from alloc_worklist. Create instance
915 // types for the CheckCastPP for allocations where possible.
916 // Propagate the the new types through users as follows:
917 // casts and Phi: push users on alloc_worklist
918 // AddP: cast Base and Address inputs to the instance type
919 // push any AddP users on alloc_worklist and push any memnode
920 // users onto memnode_worklist.
921 // Phase 2: Process MemNode's from memnode_worklist. compute new address type and
922 // search the Memory chain for a store with the appropriate type
923 // address type. If a Phi is found, create a new version with
924 // the appropriate memory slices from each of the Phi inputs.
925 // For stores, process the users as follows:
926 // MemNode: push on memnode_worklist
927 // MergeMem: push on mergemem_worklist
928 // Phase 3: Process MergeMem nodes from mergemem_worklist. Walk each memory slice
929 // moving the first node encountered of each instance type to the
930 // the input corresponding to its alias index.
931 // appropriate memory slice.
932 // Phase 4: Update the inputs of non-instance memory Phis and the Memory input of memnodes.
933 //
934 // In the following example, the CheckCastPP nodes are the cast of allocation
935 // results and the allocation of node 29 is unescaped and eligible to be an
936 // instance type.
937 //
938 // We start with:
939 //
940 // 7 Parm #memory
941 // 10 ConI "12"
942 // 19 CheckCastPP "Foo"
943 // 20 AddP _ 19 19 10 Foo+12 alias_index=4
944 // 29 CheckCastPP "Foo"
945 // 30 AddP _ 29 29 10 Foo+12 alias_index=4
946 //
947 // 40 StoreP 25 7 20 ... alias_index=4
948 // 50 StoreP 35 40 30 ... alias_index=4
949 // 60 StoreP 45 50 20 ... alias_index=4
950 // 70 LoadP _ 60 30 ... alias_index=4
951 // 80 Phi 75 50 60 Memory alias_index=4
952 // 90 LoadP _ 80 30 ... alias_index=4
953 // 100 LoadP _ 80 20 ... alias_index=4
954 //
955 //
956 // Phase 1 creates an instance type for node 29 assigning it an instance id of 24
957 // and creating a new alias index for node 30. This gives:
958 //
959 // 7 Parm #memory
960 // 10 ConI "12"
961 // 19 CheckCastPP "Foo"
962 // 20 AddP _ 19 19 10 Foo+12 alias_index=4
963 // 29 CheckCastPP "Foo" iid=24
964 // 30 AddP _ 29 29 10 Foo+12 alias_index=6 iid=24
965 //
966 // 40 StoreP 25 7 20 ... alias_index=4
967 // 50 StoreP 35 40 30 ... alias_index=6
968 // 60 StoreP 45 50 20 ... alias_index=4
969 // 70 LoadP _ 60 30 ... alias_index=6
970 // 80 Phi 75 50 60 Memory alias_index=4
971 // 90 LoadP _ 80 30 ... alias_index=6
972 // 100 LoadP _ 80 20 ... alias_index=4
973 //
974 // In phase 2, new memory inputs are computed for the loads and stores,
975 // And a new version of the phi is created. In phase 4, the inputs to
976 // node 80 are updated and then the memory nodes are updated with the
977 // values computed in phase 2. This results in:
978 //
979 // 7 Parm #memory
980 // 10 ConI "12"
981 // 19 CheckCastPP "Foo"
982 // 20 AddP _ 19 19 10 Foo+12 alias_index=4
983 // 29 CheckCastPP "Foo" iid=24
984 // 30 AddP _ 29 29 10 Foo+12 alias_index=6 iid=24
985 //
986 // 40 StoreP 25 7 20 ... alias_index=4
987 // 50 StoreP 35 7 30 ... alias_index=6
988 // 60 StoreP 45 40 20 ... alias_index=4
989 // 70 LoadP _ 50 30 ... alias_index=6
990 // 80 Phi 75 40 60 Memory alias_index=4
991 // 120 Phi 75 50 50 Memory alias_index=6
992 // 90 LoadP _ 120 30 ... alias_index=6
993 // 100 LoadP _ 80 20 ... alias_index=4
994 //
995 void ConnectionGraph::split_unique_types(GrowableArray<Node *> &alloc_worklist) {
996 GrowableArray<Node *> memnode_worklist;
997 GrowableArray<PhiNode *> orig_phis;
999 PhaseIterGVN *igvn = _igvn;
1000 uint new_index_start = (uint) _compile->num_alias_types();
1001 Arena* arena = Thread::current()->resource_area();
1002 VectorSet visited(arena);
1003 VectorSet ptset(arena);
1006 // Phase 1: Process possible allocations from alloc_worklist.
1007 // Create instance types for the CheckCastPP for allocations where possible.
1008 //
1009 // (Note: don't forget to change the order of the second AddP node on
1010 // the alloc_worklist if the order of the worklist processing is changed,
1011 // see the comment in find_second_addp().)
1012 //
1013 while (alloc_worklist.length() != 0) {
1014 Node *n = alloc_worklist.pop();
1015 uint ni = n->_idx;
1016 const TypeOopPtr* tinst = NULL;
1017 if (n->is_Call()) {
1018 CallNode *alloc = n->as_Call();
1019 // copy escape information to call node
1020 PointsToNode* ptn = ptnode_adr(alloc->_idx);
1021 PointsToNode::EscapeState es = escape_state(alloc);
1022 // We have an allocation or call which returns a Java object,
1023 // see if it is unescaped.
1024 if (es != PointsToNode::NoEscape || !ptn->_scalar_replaceable)
1025 continue;
1027 // Find CheckCastPP for the allocate or for the return value of a call
1028 n = alloc->result_cast();
1029 if (n == NULL) { // No uses except Initialize node
1030 if (alloc->is_Allocate()) {
1031 // Set the scalar_replaceable flag for allocation
1032 // so it could be eliminated if it has no uses.
1033 alloc->as_Allocate()->_is_scalar_replaceable = true;
1034 }
1035 continue;
1036 }
1037 if (!n->is_CheckCastPP()) { // not unique CheckCastPP.
1038 assert(!alloc->is_Allocate(), "allocation should have unique type");
1039 continue;
1040 }
1042 // The inline code for Object.clone() casts the allocation result to
1043 // java.lang.Object and then to the actual type of the allocated
1044 // object. Detect this case and use the second cast.
1045 // Also detect j.l.reflect.Array.newInstance(jobject, jint) case when
1046 // the allocation result is cast to java.lang.Object and then
1047 // to the actual Array type.
1048 if (alloc->is_Allocate() && n->as_Type()->type() == TypeInstPtr::NOTNULL
1049 && (alloc->is_AllocateArray() ||
1050 igvn->type(alloc->in(AllocateNode::KlassNode)) != TypeKlassPtr::OBJECT)) {
1051 Node *cast2 = NULL;
1052 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1053 Node *use = n->fast_out(i);
1054 if (use->is_CheckCastPP()) {
1055 cast2 = use;
1056 break;
1057 }
1058 }
1059 if (cast2 != NULL) {
1060 n = cast2;
1061 } else {
1062 // Non-scalar replaceable if the allocation type is unknown statically
1063 // (reflection allocation), the object can't be restored during
1064 // deoptimization without precise type.
1065 continue;
1066 }
1067 }
1068 if (alloc->is_Allocate()) {
1069 // Set the scalar_replaceable flag for allocation
1070 // so it could be eliminated.
1071 alloc->as_Allocate()->_is_scalar_replaceable = true;
1072 }
1073 set_escape_state(n->_idx, es);
1074 // in order for an object to be scalar-replaceable, it must be:
1075 // - a direct allocation (not a call returning an object)
1076 // - non-escaping
1077 // - eligible to be a unique type
1078 // - not determined to be ineligible by escape analysis
1079 assert(ptnode_adr(alloc->_idx)->_node != NULL &&
1080 ptnode_adr(n->_idx)->_node != NULL, "should be registered");
1081 set_map(alloc->_idx, n);
1082 set_map(n->_idx, alloc);
1083 const TypeOopPtr *t = igvn->type(n)->isa_oopptr();
1084 if (t == NULL)
1085 continue; // not a TypeInstPtr
1086 tinst = t->cast_to_exactness(true)->is_oopptr()->cast_to_instance_id(ni);
1087 igvn->hash_delete(n);
1088 igvn->set_type(n, tinst);
1089 n->raise_bottom_type(tinst);
1090 igvn->hash_insert(n);
1091 record_for_optimizer(n);
1092 if (alloc->is_Allocate() && ptn->_scalar_replaceable &&
1093 (t->isa_instptr() || t->isa_aryptr())) {
1095 // First, put on the worklist all Field edges from Connection Graph
1096 // which is more accurate then putting immediate users from Ideal Graph.
1097 for (uint e = 0; e < ptn->edge_count(); e++) {
1098 Node *use = ptnode_adr(ptn->edge_target(e))->_node;
1099 assert(ptn->edge_type(e) == PointsToNode::FieldEdge && use->is_AddP(),
1100 "only AddP nodes are Field edges in CG");
1101 if (use->outcnt() > 0) { // Don't process dead nodes
1102 Node* addp2 = find_second_addp(use, use->in(AddPNode::Base));
1103 if (addp2 != NULL) {
1104 assert(alloc->is_AllocateArray(),"array allocation was expected");
1105 alloc_worklist.append_if_missing(addp2);
1106 }
1107 alloc_worklist.append_if_missing(use);
1108 }
1109 }
1111 // An allocation may have an Initialize which has raw stores. Scan
1112 // the users of the raw allocation result and push AddP users
1113 // on alloc_worklist.
1114 Node *raw_result = alloc->proj_out(TypeFunc::Parms);
1115 assert (raw_result != NULL, "must have an allocation result");
1116 for (DUIterator_Fast imax, i = raw_result->fast_outs(imax); i < imax; i++) {
1117 Node *use = raw_result->fast_out(i);
1118 if (use->is_AddP() && use->outcnt() > 0) { // Don't process dead nodes
1119 Node* addp2 = find_second_addp(use, raw_result);
1120 if (addp2 != NULL) {
1121 assert(alloc->is_AllocateArray(),"array allocation was expected");
1122 alloc_worklist.append_if_missing(addp2);
1123 }
1124 alloc_worklist.append_if_missing(use);
1125 } else if (use->is_MemBar()) {
1126 memnode_worklist.append_if_missing(use);
1127 }
1128 }
1129 }
1130 } else if (n->is_AddP()) {
1131 ptset.Clear();
1132 PointsTo(ptset, get_addp_base(n));
1133 assert(ptset.Size() == 1, "AddP address is unique");
1134 uint elem = ptset.getelem(); // Allocation node's index
1135 if (elem == _phantom_object) {
1136 assert(false, "escaped allocation");
1137 continue; // Assume the value was set outside this method.
1138 }
1139 Node *base = get_map(elem); // CheckCastPP node
1140 if (!split_AddP(n, base, igvn)) continue; // wrong type from dead path
1141 tinst = igvn->type(base)->isa_oopptr();
1142 } else if (n->is_Phi() ||
1143 n->is_CheckCastPP() ||
1144 n->is_EncodeP() ||
1145 n->is_DecodeN() ||
1146 (n->is_ConstraintCast() && n->Opcode() == Op_CastPP)) {
1147 if (visited.test_set(n->_idx)) {
1148 assert(n->is_Phi(), "loops only through Phi's");
1149 continue; // already processed
1150 }
1151 ptset.Clear();
1152 PointsTo(ptset, n);
1153 if (ptset.Size() == 1) {
1154 uint elem = ptset.getelem(); // Allocation node's index
1155 if (elem == _phantom_object) {
1156 assert(false, "escaped allocation");
1157 continue; // Assume the value was set outside this method.
1158 }
1159 Node *val = get_map(elem); // CheckCastPP node
1160 TypeNode *tn = n->as_Type();
1161 tinst = igvn->type(val)->isa_oopptr();
1162 assert(tinst != NULL && tinst->is_known_instance() &&
1163 (uint)tinst->instance_id() == elem , "instance type expected.");
1165 const Type *tn_type = igvn->type(tn);
1166 const TypeOopPtr *tn_t;
1167 if (tn_type->isa_narrowoop()) {
1168 tn_t = tn_type->make_ptr()->isa_oopptr();
1169 } else {
1170 tn_t = tn_type->isa_oopptr();
1171 }
1173 if (tn_t != NULL && tinst->klass()->is_subtype_of(tn_t->klass())) {
1174 if (tn_type->isa_narrowoop()) {
1175 tn_type = tinst->make_narrowoop();
1176 } else {
1177 tn_type = tinst;
1178 }
1179 igvn->hash_delete(tn);
1180 igvn->set_type(tn, tn_type);
1181 tn->set_type(tn_type);
1182 igvn->hash_insert(tn);
1183 record_for_optimizer(n);
1184 } else {
1185 assert(tn_type == TypePtr::NULL_PTR ||
1186 tn_t != NULL && !tinst->klass()->is_subtype_of(tn_t->klass()),
1187 "unexpected type");
1188 continue; // Skip dead path with different type
1189 }
1190 }
1191 } else {
1192 debug_only(n->dump();)
1193 assert(false, "EA: unexpected node");
1194 continue;
1195 }
1196 // push allocation's users on appropriate worklist
1197 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1198 Node *use = n->fast_out(i);
1199 if(use->is_Mem() && use->in(MemNode::Address) == n) {
1200 // Load/store to instance's field
1201 memnode_worklist.append_if_missing(use);
1202 } else if (use->is_MemBar()) {
1203 memnode_worklist.append_if_missing(use);
1204 } else if (use->is_AddP() && use->outcnt() > 0) { // No dead nodes
1205 Node* addp2 = find_second_addp(use, n);
1206 if (addp2 != NULL) {
1207 alloc_worklist.append_if_missing(addp2);
1208 }
1209 alloc_worklist.append_if_missing(use);
1210 } else if (use->is_Phi() ||
1211 use->is_CheckCastPP() ||
1212 use->is_EncodeP() ||
1213 use->is_DecodeN() ||
1214 (use->is_ConstraintCast() && use->Opcode() == Op_CastPP)) {
1215 alloc_worklist.append_if_missing(use);
1216 #ifdef ASSERT
1217 } else if (use->is_Mem()) {
1218 assert(use->in(MemNode::Address) != n, "EA: missing allocation reference path");
1219 } else if (use->is_MergeMem()) {
1220 assert(_mergemem_worklist.contains(use->as_MergeMem()), "EA: missing MergeMem node in the worklist");
1221 } else if (use->is_SafePoint()) {
1222 // Look for MergeMem nodes for calls which reference unique allocation
1223 // (through CheckCastPP nodes) even for debug info.
1224 Node* m = use->in(TypeFunc::Memory);
1225 if (m->is_MergeMem()) {
1226 assert(_mergemem_worklist.contains(m->as_MergeMem()), "EA: missing MergeMem node in the worklist");
1227 }
1228 } else {
1229 uint op = use->Opcode();
1230 if (!(op == Op_CmpP || op == Op_Conv2B ||
1231 op == Op_CastP2X || op == Op_StoreCM ||
1232 op == Op_FastLock || op == Op_AryEq || op == Op_StrComp ||
1233 op == Op_StrEquals || op == Op_StrIndexOf)) {
1234 n->dump();
1235 use->dump();
1236 assert(false, "EA: missing allocation reference path");
1237 }
1238 #endif
1239 }
1240 }
1242 }
1243 // New alias types were created in split_AddP().
1244 uint new_index_end = (uint) _compile->num_alias_types();
1246 // Phase 2: Process MemNode's from memnode_worklist. compute new address type and
1247 // compute new values for Memory inputs (the Memory inputs are not
1248 // actually updated until phase 4.)
1249 if (memnode_worklist.length() == 0)
1250 return; // nothing to do
1252 while (memnode_worklist.length() != 0) {
1253 Node *n = memnode_worklist.pop();
1254 if (visited.test_set(n->_idx))
1255 continue;
1256 if (n->is_Phi() || n->is_ClearArray()) {
1257 // we don't need to do anything, but the users must be pushed
1258 } else if (n->is_MemBar()) { // Initialize, MemBar nodes
1259 // we don't need to do anything, but the users must be pushed
1260 n = n->as_MemBar()->proj_out(TypeFunc::Memory);
1261 if (n == NULL)
1262 continue;
1263 } else {
1264 assert(n->is_Mem(), "memory node required.");
1265 Node *addr = n->in(MemNode::Address);
1266 const Type *addr_t = igvn->type(addr);
1267 if (addr_t == Type::TOP)
1268 continue;
1269 assert (addr_t->isa_ptr() != NULL, "pointer type required.");
1270 int alias_idx = _compile->get_alias_index(addr_t->is_ptr());
1271 assert ((uint)alias_idx < new_index_end, "wrong alias index");
1272 Node *mem = find_inst_mem(n->in(MemNode::Memory), alias_idx, orig_phis, igvn);
1273 if (_compile->failing()) {
1274 return;
1275 }
1276 if (mem != n->in(MemNode::Memory)) {
1277 // We delay the memory edge update since we need old one in
1278 // MergeMem code below when instances memory slices are separated.
1279 debug_only(Node* pn = ptnode_adr(n->_idx)->_node;)
1280 assert(pn == NULL || pn == n, "wrong node");
1281 set_map(n->_idx, mem);
1282 ptnode_adr(n->_idx)->_node = n;
1283 }
1284 if (n->is_Load()) {
1285 continue; // don't push users
1286 } else if (n->is_LoadStore()) {
1287 // get the memory projection
1288 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1289 Node *use = n->fast_out(i);
1290 if (use->Opcode() == Op_SCMemProj) {
1291 n = use;
1292 break;
1293 }
1294 }
1295 assert(n->Opcode() == Op_SCMemProj, "memory projection required");
1296 }
1297 }
1298 // push user on appropriate worklist
1299 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1300 Node *use = n->fast_out(i);
1301 if (use->is_Phi() || use->is_ClearArray()) {
1302 memnode_worklist.append_if_missing(use);
1303 } else if(use->is_Mem() && use->in(MemNode::Memory) == n) {
1304 if (use->Opcode() == Op_StoreCM) // Ignore cardmark stores
1305 continue;
1306 memnode_worklist.append_if_missing(use);
1307 } else if (use->is_MemBar()) {
1308 memnode_worklist.append_if_missing(use);
1309 #ifdef ASSERT
1310 } else if(use->is_Mem()) {
1311 assert(use->in(MemNode::Memory) != n, "EA: missing memory path");
1312 } else if (use->is_MergeMem()) {
1313 assert(_mergemem_worklist.contains(use->as_MergeMem()), "EA: missing MergeMem node in the worklist");
1314 } else {
1315 uint op = use->Opcode();
1316 if (!(op == Op_StoreCM ||
1317 (op == Op_CallLeaf && use->as_CallLeaf()->_name != NULL &&
1318 strcmp(use->as_CallLeaf()->_name, "g1_wb_pre") == 0) ||
1319 op == Op_AryEq || op == Op_StrComp ||
1320 op == Op_StrEquals || op == Op_StrIndexOf)) {
1321 n->dump();
1322 use->dump();
1323 assert(false, "EA: missing memory path");
1324 }
1325 #endif
1326 }
1327 }
1328 }
1330 // Phase 3: Process MergeMem nodes from mergemem_worklist.
1331 // Walk each memory slice moving the first node encountered of each
1332 // instance type to the the input corresponding to its alias index.
1333 uint length = _mergemem_worklist.length();
1334 for( uint next = 0; next < length; ++next ) {
1335 MergeMemNode* nmm = _mergemem_worklist.at(next);
1336 assert(!visited.test_set(nmm->_idx), "should not be visited before");
1337 // Note: we don't want to use MergeMemStream here because we only want to
1338 // scan inputs which exist at the start, not ones we add during processing.
1339 // Note 2: MergeMem may already contains instance memory slices added
1340 // during find_inst_mem() call when memory nodes were processed above.
1341 igvn->hash_delete(nmm);
1342 uint nslices = nmm->req();
1343 for (uint i = Compile::AliasIdxRaw+1; i < nslices; i++) {
1344 Node* mem = nmm->in(i);
1345 Node* cur = NULL;
1346 if (mem == NULL || mem->is_top())
1347 continue;
1348 // First, update mergemem by moving memory nodes to corresponding slices
1349 // if their type became more precise since this mergemem was created.
1350 while (mem->is_Mem()) {
1351 const Type *at = igvn->type(mem->in(MemNode::Address));
1352 if (at != Type::TOP) {
1353 assert (at->isa_ptr() != NULL, "pointer type required.");
1354 uint idx = (uint)_compile->get_alias_index(at->is_ptr());
1355 if (idx == i) {
1356 if (cur == NULL)
1357 cur = mem;
1358 } else {
1359 if (idx >= nmm->req() || nmm->is_empty_memory(nmm->in(idx))) {
1360 nmm->set_memory_at(idx, mem);
1361 }
1362 }
1363 }
1364 mem = mem->in(MemNode::Memory);
1365 }
1366 nmm->set_memory_at(i, (cur != NULL) ? cur : mem);
1367 // Find any instance of the current type if we haven't encountered
1368 // already a memory slice of the instance along the memory chain.
1369 for (uint ni = new_index_start; ni < new_index_end; ni++) {
1370 if((uint)_compile->get_general_index(ni) == i) {
1371 Node *m = (ni >= nmm->req()) ? nmm->empty_memory() : nmm->in(ni);
1372 if (nmm->is_empty_memory(m)) {
1373 Node* result = find_inst_mem(mem, ni, orig_phis, igvn);
1374 if (_compile->failing()) {
1375 return;
1376 }
1377 nmm->set_memory_at(ni, result);
1378 }
1379 }
1380 }
1381 }
1382 // Find the rest of instances values
1383 for (uint ni = new_index_start; ni < new_index_end; ni++) {
1384 const TypeOopPtr *tinst = _compile->get_adr_type(ni)->isa_oopptr();
1385 Node* result = step_through_mergemem(nmm, ni, tinst);
1386 if (result == nmm->base_memory()) {
1387 // Didn't find instance memory, search through general slice recursively.
1388 result = nmm->memory_at(_compile->get_general_index(ni));
1389 result = find_inst_mem(result, ni, orig_phis, igvn);
1390 if (_compile->failing()) {
1391 return;
1392 }
1393 nmm->set_memory_at(ni, result);
1394 }
1395 }
1396 igvn->hash_insert(nmm);
1397 record_for_optimizer(nmm);
1398 }
1400 // Phase 4: Update the inputs of non-instance memory Phis and
1401 // the Memory input of memnodes
1402 // First update the inputs of any non-instance Phi's from
1403 // which we split out an instance Phi. Note we don't have
1404 // to recursively process Phi's encounted on the input memory
1405 // chains as is done in split_memory_phi() since they will
1406 // also be processed here.
1407 for (int j = 0; j < orig_phis.length(); j++) {
1408 PhiNode *phi = orig_phis.at(j);
1409 int alias_idx = _compile->get_alias_index(phi->adr_type());
1410 igvn->hash_delete(phi);
1411 for (uint i = 1; i < phi->req(); i++) {
1412 Node *mem = phi->in(i);
1413 Node *new_mem = find_inst_mem(mem, alias_idx, orig_phis, igvn);
1414 if (_compile->failing()) {
1415 return;
1416 }
1417 if (mem != new_mem) {
1418 phi->set_req(i, new_mem);
1419 }
1420 }
1421 igvn->hash_insert(phi);
1422 record_for_optimizer(phi);
1423 }
1425 // Update the memory inputs of MemNodes with the value we computed
1426 // in Phase 2 and move stores memory users to corresponding memory slices.
1427 #ifdef ASSERT
1428 visited.Clear();
1429 Node_Stack old_mems(arena, _compile->unique() >> 2);
1430 #endif
1431 for (uint i = 0; i < nodes_size(); i++) {
1432 Node *nmem = get_map(i);
1433 if (nmem != NULL) {
1434 Node *n = ptnode_adr(i)->_node;
1435 assert(n != NULL, "sanity");
1436 if (n->is_Mem()) {
1437 #ifdef ASSERT
1438 Node* old_mem = n->in(MemNode::Memory);
1439 if (!visited.test_set(old_mem->_idx)) {
1440 old_mems.push(old_mem, old_mem->outcnt());
1441 }
1442 #endif
1443 assert(n->in(MemNode::Memory) != nmem, "sanity");
1444 if (!n->is_Load()) {
1445 // Move memory users of a store first.
1446 move_inst_mem(n, orig_phis, igvn);
1447 }
1448 // Now update memory input
1449 igvn->hash_delete(n);
1450 n->set_req(MemNode::Memory, nmem);
1451 igvn->hash_insert(n);
1452 record_for_optimizer(n);
1453 } else {
1454 assert(n->is_Allocate() || n->is_CheckCastPP() ||
1455 n->is_AddP() || n->is_Phi(), "unknown node used for set_map()");
1456 }
1457 }
1458 }
1459 #ifdef ASSERT
1460 // Verify that memory was split correctly
1461 while (old_mems.is_nonempty()) {
1462 Node* old_mem = old_mems.node();
1463 uint old_cnt = old_mems.index();
1464 old_mems.pop();
1465 assert(old_cnt = old_mem->outcnt(), "old mem could be lost");
1466 }
1467 #endif
1468 }
1470 bool ConnectionGraph::has_candidates(Compile *C) {
1471 // EA brings benefits only when the code has allocations and/or locks which
1472 // are represented by ideal Macro nodes.
1473 int cnt = C->macro_count();
1474 for( int i=0; i < cnt; i++ ) {
1475 Node *n = C->macro_node(i);
1476 if ( n->is_Allocate() )
1477 return true;
1478 if( n->is_Lock() ) {
1479 Node* obj = n->as_Lock()->obj_node()->uncast();
1480 if( !(obj->is_Parm() || obj->is_Con()) )
1481 return true;
1482 }
1483 }
1484 return false;
1485 }
1487 void ConnectionGraph::do_analysis(Compile *C, PhaseIterGVN *igvn) {
1488 // Add ConP#NULL and ConN#NULL nodes before ConnectionGraph construction
1489 // to create space for them in ConnectionGraph::_nodes[].
1490 Node* oop_null = igvn->zerocon(T_OBJECT);
1491 Node* noop_null = igvn->zerocon(T_NARROWOOP);
1493 ConnectionGraph* congraph = new(C->comp_arena()) ConnectionGraph(C, igvn);
1494 // Perform escape analysis
1495 if (congraph->compute_escape()) {
1496 // There are non escaping objects.
1497 C->set_congraph(congraph);
1498 }
1500 // Cleanup.
1501 if (oop_null->outcnt() == 0)
1502 igvn->hash_delete(oop_null);
1503 if (noop_null->outcnt() == 0)
1504 igvn->hash_delete(noop_null);
1505 }
1507 bool ConnectionGraph::compute_escape() {
1508 Compile* C = _compile;
1510 // 1. Populate Connection Graph (CG) with Ideal nodes.
1512 Unique_Node_List worklist_init;
1513 worklist_init.map(C->unique(), NULL); // preallocate space
1515 // Initialize worklist
1516 if (C->root() != NULL) {
1517 worklist_init.push(C->root());
1518 }
1520 GrowableArray<int> cg_worklist;
1521 PhaseGVN* igvn = _igvn;
1522 bool has_allocations = false;
1524 // Push all useful nodes onto CG list and set their type.
1525 for( uint next = 0; next < worklist_init.size(); ++next ) {
1526 Node* n = worklist_init.at(next);
1527 record_for_escape_analysis(n, igvn);
1528 // Only allocations and java static calls results are checked
1529 // for an escape status. See process_call_result() below.
1530 if (n->is_Allocate() || n->is_CallStaticJava() &&
1531 ptnode_adr(n->_idx)->node_type() == PointsToNode::JavaObject) {
1532 has_allocations = true;
1533 }
1534 if(n->is_AddP()) {
1535 // Collect address nodes. Use them during stage 3 below
1536 // to build initial connection graph field edges.
1537 cg_worklist.append(n->_idx);
1538 } else if (n->is_MergeMem()) {
1539 // Collect all MergeMem nodes to add memory slices for
1540 // scalar replaceable objects in split_unique_types().
1541 _mergemem_worklist.append(n->as_MergeMem());
1542 }
1543 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1544 Node* m = n->fast_out(i); // Get user
1545 worklist_init.push(m);
1546 }
1547 }
1549 if (!has_allocations) {
1550 _collecting = false;
1551 return false; // Nothing to do.
1552 }
1554 // 2. First pass to create simple CG edges (doesn't require to walk CG).
1555 uint delayed_size = _delayed_worklist.size();
1556 for( uint next = 0; next < delayed_size; ++next ) {
1557 Node* n = _delayed_worklist.at(next);
1558 build_connection_graph(n, igvn);
1559 }
1561 // 3. Pass to create initial fields edges (JavaObject -F-> AddP)
1562 // to reduce number of iterations during stage 4 below.
1563 uint cg_length = cg_worklist.length();
1564 for( uint next = 0; next < cg_length; ++next ) {
1565 int ni = cg_worklist.at(next);
1566 Node* n = ptnode_adr(ni)->_node;
1567 Node* base = get_addp_base(n);
1568 if (base->is_Proj())
1569 base = base->in(0);
1570 PointsToNode::NodeType nt = ptnode_adr(base->_idx)->node_type();
1571 if (nt == PointsToNode::JavaObject) {
1572 build_connection_graph(n, igvn);
1573 }
1574 }
1576 cg_worklist.clear();
1577 cg_worklist.append(_phantom_object);
1578 GrowableArray<uint> worklist;
1580 // 4. Build Connection Graph which need
1581 // to walk the connection graph.
1582 _progress = false;
1583 for (uint ni = 0; ni < nodes_size(); ni++) {
1584 PointsToNode* ptn = ptnode_adr(ni);
1585 Node *n = ptn->_node;
1586 if (n != NULL) { // Call, AddP, LoadP, StoreP
1587 build_connection_graph(n, igvn);
1588 if (ptn->node_type() != PointsToNode::UnknownType)
1589 cg_worklist.append(n->_idx); // Collect CG nodes
1590 if (!_processed.test(n->_idx))
1591 worklist.append(n->_idx); // Collect C/A/L/S nodes
1592 }
1593 }
1595 // After IGVN user nodes may have smaller _idx than
1596 // their inputs so they will be processed first in
1597 // previous loop. Because of that not all Graph
1598 // edges will be created. Walk over interesting
1599 // nodes again until no new edges are created.
1600 //
1601 // Normally only 1-3 passes needed to build
1602 // Connection Graph depending on graph complexity.
1603 // Set limit to 10 to catch situation when something
1604 // did go wrong and recompile the method without EA.
1606 #define CG_BUILD_ITER_LIMIT 10
1608 uint length = worklist.length();
1609 int iterations = 0;
1610 while(_progress && (iterations++ < CG_BUILD_ITER_LIMIT)) {
1611 _progress = false;
1612 for( uint next = 0; next < length; ++next ) {
1613 int ni = worklist.at(next);
1614 PointsToNode* ptn = ptnode_adr(ni);
1615 Node* n = ptn->_node;
1616 assert(n != NULL, "should be known node");
1617 build_connection_graph(n, igvn);
1618 }
1619 }
1620 if (iterations >= CG_BUILD_ITER_LIMIT) {
1621 assert(iterations < CG_BUILD_ITER_LIMIT,
1622 err_msg("infinite EA connection graph build with %d nodes and worklist size %d",
1623 nodes_size(), length));
1624 // Possible infinite build_connection_graph loop,
1625 // retry compilation without escape analysis.
1626 C->record_failure(C2Compiler::retry_no_escape_analysis());
1627 _collecting = false;
1628 return false;
1629 }
1630 #undef CG_BUILD_ITER_LIMIT
1632 Arena* arena = Thread::current()->resource_area();
1633 VectorSet ptset(arena);
1634 VectorSet visited(arena);
1635 worklist.clear();
1637 // 5. Remove deferred edges from the graph and adjust
1638 // escape state of nonescaping objects.
1639 cg_length = cg_worklist.length();
1640 for( uint next = 0; next < cg_length; ++next ) {
1641 int ni = cg_worklist.at(next);
1642 PointsToNode* ptn = ptnode_adr(ni);
1643 PointsToNode::NodeType nt = ptn->node_type();
1644 if (nt == PointsToNode::LocalVar || nt == PointsToNode::Field) {
1645 remove_deferred(ni, &worklist, &visited);
1646 Node *n = ptn->_node;
1647 if (n->is_AddP()) {
1648 // Search for objects which are not scalar replaceable
1649 // and adjust their escape state.
1650 verify_escape_state(ni, ptset, igvn);
1651 }
1652 }
1653 }
1655 // 6. Propagate escape states.
1656 worklist.clear();
1657 bool has_non_escaping_obj = false;
1659 // push all GlobalEscape nodes on the worklist
1660 for( uint next = 0; next < cg_length; ++next ) {
1661 int nk = cg_worklist.at(next);
1662 if (ptnode_adr(nk)->escape_state() == PointsToNode::GlobalEscape)
1663 worklist.push(nk);
1664 }
1665 // mark all nodes reachable from GlobalEscape nodes
1666 while(worklist.length() > 0) {
1667 PointsToNode* ptn = ptnode_adr(worklist.pop());
1668 uint e_cnt = ptn->edge_count();
1669 for (uint ei = 0; ei < e_cnt; ei++) {
1670 uint npi = ptn->edge_target(ei);
1671 PointsToNode *np = ptnode_adr(npi);
1672 if (np->escape_state() < PointsToNode::GlobalEscape) {
1673 np->set_escape_state(PointsToNode::GlobalEscape);
1674 worklist.push(npi);
1675 }
1676 }
1677 }
1679 // push all ArgEscape nodes on the worklist
1680 for( uint next = 0; next < cg_length; ++next ) {
1681 int nk = cg_worklist.at(next);
1682 if (ptnode_adr(nk)->escape_state() == PointsToNode::ArgEscape)
1683 worklist.push(nk);
1684 }
1685 // mark all nodes reachable from ArgEscape nodes
1686 while(worklist.length() > 0) {
1687 PointsToNode* ptn = ptnode_adr(worklist.pop());
1688 if (ptn->node_type() == PointsToNode::JavaObject)
1689 has_non_escaping_obj = true; // Non GlobalEscape
1690 uint e_cnt = ptn->edge_count();
1691 for (uint ei = 0; ei < e_cnt; ei++) {
1692 uint npi = ptn->edge_target(ei);
1693 PointsToNode *np = ptnode_adr(npi);
1694 if (np->escape_state() < PointsToNode::ArgEscape) {
1695 np->set_escape_state(PointsToNode::ArgEscape);
1696 worklist.push(npi);
1697 }
1698 }
1699 }
1701 GrowableArray<Node*> alloc_worklist;
1703 // push all NoEscape nodes on the worklist
1704 for( uint next = 0; next < cg_length; ++next ) {
1705 int nk = cg_worklist.at(next);
1706 if (ptnode_adr(nk)->escape_state() == PointsToNode::NoEscape)
1707 worklist.push(nk);
1708 }
1709 // mark all nodes reachable from NoEscape nodes
1710 while(worklist.length() > 0) {
1711 PointsToNode* ptn = ptnode_adr(worklist.pop());
1712 if (ptn->node_type() == PointsToNode::JavaObject)
1713 has_non_escaping_obj = true; // Non GlobalEscape
1714 Node* n = ptn->_node;
1715 if (n->is_Allocate() && ptn->_scalar_replaceable ) {
1716 // Push scalar replaceable allocations on alloc_worklist
1717 // for processing in split_unique_types().
1718 alloc_worklist.append(n);
1719 }
1720 uint e_cnt = ptn->edge_count();
1721 for (uint ei = 0; ei < e_cnt; ei++) {
1722 uint npi = ptn->edge_target(ei);
1723 PointsToNode *np = ptnode_adr(npi);
1724 if (np->escape_state() < PointsToNode::NoEscape) {
1725 np->set_escape_state(PointsToNode::NoEscape);
1726 worklist.push(npi);
1727 }
1728 }
1729 }
1731 _collecting = false;
1732 assert(C->unique() == nodes_size(), "there should be no new ideal nodes during ConnectionGraph build");
1734 #ifndef PRODUCT
1735 if (PrintEscapeAnalysis) {
1736 dump(); // Dump ConnectionGraph
1737 }
1738 #endif
1740 bool has_scalar_replaceable_candidates = alloc_worklist.length() > 0;
1741 if ( has_scalar_replaceable_candidates &&
1742 C->AliasLevel() >= 3 && EliminateAllocations ) {
1744 // Now use the escape information to create unique types for
1745 // scalar replaceable objects.
1746 split_unique_types(alloc_worklist);
1748 if (C->failing()) return false;
1750 C->print_method("After Escape Analysis", 2);
1752 #ifdef ASSERT
1753 } else if (Verbose && (PrintEscapeAnalysis || PrintEliminateAllocations)) {
1754 tty->print("=== No allocations eliminated for ");
1755 C->method()->print_short_name();
1756 if(!EliminateAllocations) {
1757 tty->print(" since EliminateAllocations is off ===");
1758 } else if(!has_scalar_replaceable_candidates) {
1759 tty->print(" since there are no scalar replaceable candidates ===");
1760 } else if(C->AliasLevel() < 3) {
1761 tty->print(" since AliasLevel < 3 ===");
1762 }
1763 tty->cr();
1764 #endif
1765 }
1766 return has_non_escaping_obj;
1767 }
1769 // Search for objects which are not scalar replaceable.
1770 void ConnectionGraph::verify_escape_state(int nidx, VectorSet& ptset, PhaseTransform* phase) {
1771 PointsToNode* ptn = ptnode_adr(nidx);
1772 Node* n = ptn->_node;
1773 assert(n->is_AddP(), "Should be called for AddP nodes only");
1774 // Search for objects which are not scalar replaceable.
1775 // Mark their escape state as ArgEscape to propagate the state
1776 // to referenced objects.
1777 // Note: currently there are no difference in compiler optimizations
1778 // for ArgEscape objects and NoEscape objects which are not
1779 // scalar replaceable.
1781 Compile* C = _compile;
1783 int offset = ptn->offset();
1784 Node* base = get_addp_base(n);
1785 ptset.Clear();
1786 PointsTo(ptset, base);
1787 int ptset_size = ptset.Size();
1789 // Check if a oop field's initializing value is recorded and add
1790 // a corresponding NULL field's value if it is not recorded.
1791 // Connection Graph does not record a default initialization by NULL
1792 // captured by Initialize node.
1793 //
1794 // Note: it will disable scalar replacement in some cases:
1795 //
1796 // Point p[] = new Point[1];
1797 // p[0] = new Point(); // Will be not scalar replaced
1798 //
1799 // but it will save us from incorrect optimizations in next cases:
1800 //
1801 // Point p[] = new Point[1];
1802 // if ( x ) p[0] = new Point(); // Will be not scalar replaced
1803 //
1804 // Do a simple control flow analysis to distinguish above cases.
1805 //
1806 if (offset != Type::OffsetBot && ptset_size == 1) {
1807 uint elem = ptset.getelem(); // Allocation node's index
1808 // It does not matter if it is not Allocation node since
1809 // only non-escaping allocations are scalar replaced.
1810 if (ptnode_adr(elem)->_node->is_Allocate() &&
1811 ptnode_adr(elem)->escape_state() == PointsToNode::NoEscape) {
1812 AllocateNode* alloc = ptnode_adr(elem)->_node->as_Allocate();
1813 InitializeNode* ini = alloc->initialization();
1815 // Check only oop fields.
1816 const Type* adr_type = n->as_AddP()->bottom_type();
1817 BasicType basic_field_type = T_INT;
1818 if (adr_type->isa_instptr()) {
1819 ciField* field = C->alias_type(adr_type->isa_instptr())->field();
1820 if (field != NULL) {
1821 basic_field_type = field->layout_type();
1822 } else {
1823 // Ignore non field load (for example, klass load)
1824 }
1825 } else if (adr_type->isa_aryptr()) {
1826 const Type* elemtype = adr_type->isa_aryptr()->elem();
1827 basic_field_type = elemtype->array_element_basic_type();
1828 } else {
1829 // Raw pointers are used for initializing stores so skip it.
1830 assert(adr_type->isa_rawptr() && base->is_Proj() &&
1831 (base->in(0) == alloc),"unexpected pointer type");
1832 }
1833 if (basic_field_type == T_OBJECT ||
1834 basic_field_type == T_NARROWOOP ||
1835 basic_field_type == T_ARRAY) {
1836 Node* value = NULL;
1837 if (ini != NULL) {
1838 BasicType ft = UseCompressedOops ? T_NARROWOOP : T_OBJECT;
1839 Node* store = ini->find_captured_store(offset, type2aelembytes(ft), phase);
1840 if (store != NULL && store->is_Store()) {
1841 value = store->in(MemNode::ValueIn);
1842 } else if (ptn->edge_count() > 0) { // Are there oop stores?
1843 // Check for a store which follows allocation without branches.
1844 // For example, a volatile field store is not collected
1845 // by Initialize node. TODO: it would be nice to use idom() here.
1846 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1847 store = n->fast_out(i);
1848 if (store->is_Store() && store->in(0) != NULL) {
1849 Node* ctrl = store->in(0);
1850 while(!(ctrl == ini || ctrl == alloc || ctrl == NULL ||
1851 ctrl == C->root() || ctrl == C->top() || ctrl->is_Region() ||
1852 ctrl->is_IfTrue() || ctrl->is_IfFalse())) {
1853 ctrl = ctrl->in(0);
1854 }
1855 if (ctrl == ini || ctrl == alloc) {
1856 value = store->in(MemNode::ValueIn);
1857 break;
1858 }
1859 }
1860 }
1861 }
1862 }
1863 if (value == NULL || value != ptnode_adr(value->_idx)->_node) {
1864 // A field's initializing value was not recorded. Add NULL.
1865 uint null_idx = UseCompressedOops ? _noop_null : _oop_null;
1866 add_pointsto_edge(nidx, null_idx);
1867 }
1868 }
1869 }
1870 }
1872 // An object is not scalar replaceable if the field which may point
1873 // to it has unknown offset (unknown element of an array of objects).
1874 //
1875 if (offset == Type::OffsetBot) {
1876 uint e_cnt = ptn->edge_count();
1877 for (uint ei = 0; ei < e_cnt; ei++) {
1878 uint npi = ptn->edge_target(ei);
1879 set_escape_state(npi, PointsToNode::ArgEscape);
1880 ptnode_adr(npi)->_scalar_replaceable = false;
1881 }
1882 }
1884 // Currently an object is not scalar replaceable if a LoadStore node
1885 // access its field since the field value is unknown after it.
1886 //
1887 bool has_LoadStore = false;
1888 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1889 Node *use = n->fast_out(i);
1890 if (use->is_LoadStore()) {
1891 has_LoadStore = true;
1892 break;
1893 }
1894 }
1895 // An object is not scalar replaceable if the address points
1896 // to unknown field (unknown element for arrays, offset is OffsetBot).
1897 //
1898 // Or the address may point to more then one object. This may produce
1899 // the false positive result (set scalar_replaceable to false)
1900 // since the flow-insensitive escape analysis can't separate
1901 // the case when stores overwrite the field's value from the case
1902 // when stores happened on different control branches.
1903 //
1904 if (ptset_size > 1 || ptset_size != 0 &&
1905 (has_LoadStore || offset == Type::OffsetBot)) {
1906 for( VectorSetI j(&ptset); j.test(); ++j ) {
1907 set_escape_state(j.elem, PointsToNode::ArgEscape);
1908 ptnode_adr(j.elem)->_scalar_replaceable = false;
1909 }
1910 }
1911 }
1913 void ConnectionGraph::process_call_arguments(CallNode *call, PhaseTransform *phase) {
1915 switch (call->Opcode()) {
1916 #ifdef ASSERT
1917 case Op_Allocate:
1918 case Op_AllocateArray:
1919 case Op_Lock:
1920 case Op_Unlock:
1921 assert(false, "should be done already");
1922 break;
1923 #endif
1924 case Op_CallLeaf:
1925 case Op_CallLeafNoFP:
1926 {
1927 // Stub calls, objects do not escape but they are not scale replaceable.
1928 // Adjust escape state for outgoing arguments.
1929 const TypeTuple * d = call->tf()->domain();
1930 VectorSet ptset(Thread::current()->resource_area());
1931 for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
1932 const Type* at = d->field_at(i);
1933 Node *arg = call->in(i)->uncast();
1934 const Type *aat = phase->type(arg);
1935 if (!arg->is_top() && at->isa_ptr() && aat->isa_ptr() &&
1936 ptnode_adr(arg->_idx)->escape_state() < PointsToNode::ArgEscape) {
1938 assert(aat == Type::TOP || aat == TypePtr::NULL_PTR ||
1939 aat->isa_ptr() != NULL, "expecting an Ptr");
1940 #ifdef ASSERT
1941 if (!(call->Opcode() == Op_CallLeafNoFP &&
1942 call->as_CallLeaf()->_name != NULL &&
1943 (strstr(call->as_CallLeaf()->_name, "arraycopy") != 0) ||
1944 call->as_CallLeaf()->_name != NULL &&
1945 (strcmp(call->as_CallLeaf()->_name, "g1_wb_pre") == 0 ||
1946 strcmp(call->as_CallLeaf()->_name, "g1_wb_post") == 0 ))
1947 ) {
1948 call->dump();
1949 assert(false, "EA: unexpected CallLeaf");
1950 }
1951 #endif
1952 set_escape_state(arg->_idx, PointsToNode::ArgEscape);
1953 if (arg->is_AddP()) {
1954 //
1955 // The inline_native_clone() case when the arraycopy stub is called
1956 // after the allocation before Initialize and CheckCastPP nodes.
1957 //
1958 // Set AddP's base (Allocate) as not scalar replaceable since
1959 // pointer to the base (with offset) is passed as argument.
1960 //
1961 arg = get_addp_base(arg);
1962 }
1963 ptset.Clear();
1964 PointsTo(ptset, arg);
1965 for( VectorSetI j(&ptset); j.test(); ++j ) {
1966 uint pt = j.elem;
1967 set_escape_state(pt, PointsToNode::ArgEscape);
1968 }
1969 }
1970 }
1971 break;
1972 }
1974 case Op_CallStaticJava:
1975 // For a static call, we know exactly what method is being called.
1976 // Use bytecode estimator to record the call's escape affects
1977 {
1978 ciMethod *meth = call->as_CallJava()->method();
1979 BCEscapeAnalyzer *call_analyzer = (meth !=NULL) ? meth->get_bcea() : NULL;
1980 // fall-through if not a Java method or no analyzer information
1981 if (call_analyzer != NULL) {
1982 const TypeTuple * d = call->tf()->domain();
1983 VectorSet ptset(Thread::current()->resource_area());
1984 bool copy_dependencies = false;
1985 for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
1986 const Type* at = d->field_at(i);
1987 int k = i - TypeFunc::Parms;
1988 Node *arg = call->in(i)->uncast();
1990 if (at->isa_oopptr() != NULL &&
1991 ptnode_adr(arg->_idx)->escape_state() < PointsToNode::GlobalEscape) {
1993 bool global_escapes = false;
1994 bool fields_escapes = false;
1995 if (!call_analyzer->is_arg_stack(k)) {
1996 // The argument global escapes, mark everything it could point to
1997 set_escape_state(arg->_idx, PointsToNode::GlobalEscape);
1998 global_escapes = true;
1999 } else {
2000 if (!call_analyzer->is_arg_local(k)) {
2001 // The argument itself doesn't escape, but any fields might
2002 fields_escapes = true;
2003 }
2004 set_escape_state(arg->_idx, PointsToNode::ArgEscape);
2005 copy_dependencies = true;
2006 }
2008 ptset.Clear();
2009 PointsTo(ptset, arg);
2010 for( VectorSetI j(&ptset); j.test(); ++j ) {
2011 uint pt = j.elem;
2012 if (global_escapes) {
2013 //The argument global escapes, mark everything it could point to
2014 set_escape_state(pt, PointsToNode::GlobalEscape);
2015 } else {
2016 if (fields_escapes) {
2017 // The argument itself doesn't escape, but any fields might
2018 add_edge_from_fields(pt, _phantom_object, Type::OffsetBot);
2019 }
2020 set_escape_state(pt, PointsToNode::ArgEscape);
2021 }
2022 }
2023 }
2024 }
2025 if (copy_dependencies)
2026 call_analyzer->copy_dependencies(_compile->dependencies());
2027 break;
2028 }
2029 }
2031 default:
2032 // Fall-through here if not a Java method or no analyzer information
2033 // or some other type of call, assume the worst case: all arguments
2034 // globally escape.
2035 {
2036 // adjust escape state for outgoing arguments
2037 const TypeTuple * d = call->tf()->domain();
2038 VectorSet ptset(Thread::current()->resource_area());
2039 for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
2040 const Type* at = d->field_at(i);
2041 if (at->isa_oopptr() != NULL) {
2042 Node *arg = call->in(i)->uncast();
2043 set_escape_state(arg->_idx, PointsToNode::GlobalEscape);
2044 ptset.Clear();
2045 PointsTo(ptset, arg);
2046 for( VectorSetI j(&ptset); j.test(); ++j ) {
2047 uint pt = j.elem;
2048 set_escape_state(pt, PointsToNode::GlobalEscape);
2049 }
2050 }
2051 }
2052 }
2053 }
2054 }
2055 void ConnectionGraph::process_call_result(ProjNode *resproj, PhaseTransform *phase) {
2056 CallNode *call = resproj->in(0)->as_Call();
2057 uint call_idx = call->_idx;
2058 uint resproj_idx = resproj->_idx;
2060 switch (call->Opcode()) {
2061 case Op_Allocate:
2062 {
2063 Node *k = call->in(AllocateNode::KlassNode);
2064 const TypeKlassPtr *kt = k->bottom_type()->isa_klassptr();
2065 assert(kt != NULL, "TypeKlassPtr required.");
2066 ciKlass* cik = kt->klass();
2068 PointsToNode::EscapeState es;
2069 uint edge_to;
2070 if (cik->is_subclass_of(_compile->env()->Thread_klass()) ||
2071 !cik->is_instance_klass() || // StressReflectiveCode
2072 cik->as_instance_klass()->has_finalizer()) {
2073 es = PointsToNode::GlobalEscape;
2074 edge_to = _phantom_object; // Could not be worse
2075 } else {
2076 es = PointsToNode::NoEscape;
2077 edge_to = call_idx;
2078 }
2079 set_escape_state(call_idx, es);
2080 add_pointsto_edge(resproj_idx, edge_to);
2081 _processed.set(resproj_idx);
2082 break;
2083 }
2085 case Op_AllocateArray:
2086 {
2088 Node *k = call->in(AllocateNode::KlassNode);
2089 const TypeKlassPtr *kt = k->bottom_type()->isa_klassptr();
2090 assert(kt != NULL, "TypeKlassPtr required.");
2091 ciKlass* cik = kt->klass();
2093 PointsToNode::EscapeState es;
2094 uint edge_to;
2095 if (!cik->is_array_klass()) { // StressReflectiveCode
2096 es = PointsToNode::GlobalEscape;
2097 edge_to = _phantom_object;
2098 } else {
2099 es = PointsToNode::NoEscape;
2100 edge_to = call_idx;
2101 int length = call->in(AllocateNode::ALength)->find_int_con(-1);
2102 if (length < 0 || length > EliminateAllocationArraySizeLimit) {
2103 // Not scalar replaceable if the length is not constant or too big.
2104 ptnode_adr(call_idx)->_scalar_replaceable = false;
2105 }
2106 }
2107 set_escape_state(call_idx, es);
2108 add_pointsto_edge(resproj_idx, edge_to);
2109 _processed.set(resproj_idx);
2110 break;
2111 }
2113 case Op_CallStaticJava:
2114 // For a static call, we know exactly what method is being called.
2115 // Use bytecode estimator to record whether the call's return value escapes
2116 {
2117 bool done = true;
2118 const TypeTuple *r = call->tf()->range();
2119 const Type* ret_type = NULL;
2121 if (r->cnt() > TypeFunc::Parms)
2122 ret_type = r->field_at(TypeFunc::Parms);
2124 // Note: we use isa_ptr() instead of isa_oopptr() here because the
2125 // _multianewarray functions return a TypeRawPtr.
2126 if (ret_type == NULL || ret_type->isa_ptr() == NULL) {
2127 _processed.set(resproj_idx);
2128 break; // doesn't return a pointer type
2129 }
2130 ciMethod *meth = call->as_CallJava()->method();
2131 const TypeTuple * d = call->tf()->domain();
2132 if (meth == NULL) {
2133 // not a Java method, assume global escape
2134 set_escape_state(call_idx, PointsToNode::GlobalEscape);
2135 add_pointsto_edge(resproj_idx, _phantom_object);
2136 } else {
2137 BCEscapeAnalyzer *call_analyzer = meth->get_bcea();
2138 bool copy_dependencies = false;
2140 if (call_analyzer->is_return_allocated()) {
2141 // Returns a newly allocated unescaped object, simply
2142 // update dependency information.
2143 // Mark it as NoEscape so that objects referenced by
2144 // it's fields will be marked as NoEscape at least.
2145 set_escape_state(call_idx, PointsToNode::NoEscape);
2146 add_pointsto_edge(resproj_idx, call_idx);
2147 copy_dependencies = true;
2148 } else if (call_analyzer->is_return_local()) {
2149 // determine whether any arguments are returned
2150 set_escape_state(call_idx, PointsToNode::NoEscape);
2151 bool ret_arg = false;
2152 for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
2153 const Type* at = d->field_at(i);
2155 if (at->isa_oopptr() != NULL) {
2156 Node *arg = call->in(i)->uncast();
2158 if (call_analyzer->is_arg_returned(i - TypeFunc::Parms)) {
2159 ret_arg = true;
2160 PointsToNode *arg_esp = ptnode_adr(arg->_idx);
2161 if (arg_esp->node_type() == PointsToNode::UnknownType)
2162 done = false;
2163 else if (arg_esp->node_type() == PointsToNode::JavaObject)
2164 add_pointsto_edge(resproj_idx, arg->_idx);
2165 else
2166 add_deferred_edge(resproj_idx, arg->_idx);
2167 arg_esp->_hidden_alias = true;
2168 }
2169 }
2170 }
2171 if (done && !ret_arg) {
2172 // Returns unknown object.
2173 set_escape_state(call_idx, PointsToNode::GlobalEscape);
2174 add_pointsto_edge(resproj_idx, _phantom_object);
2175 }
2176 copy_dependencies = true;
2177 } else {
2178 set_escape_state(call_idx, PointsToNode::GlobalEscape);
2179 add_pointsto_edge(resproj_idx, _phantom_object);
2180 for (uint i = TypeFunc::Parms; i < d->cnt(); i++) {
2181 const Type* at = d->field_at(i);
2182 if (at->isa_oopptr() != NULL) {
2183 Node *arg = call->in(i)->uncast();
2184 PointsToNode *arg_esp = ptnode_adr(arg->_idx);
2185 arg_esp->_hidden_alias = true;
2186 }
2187 }
2188 }
2189 if (copy_dependencies)
2190 call_analyzer->copy_dependencies(_compile->dependencies());
2191 }
2192 if (done)
2193 _processed.set(resproj_idx);
2194 break;
2195 }
2197 default:
2198 // Some other type of call, assume the worst case that the
2199 // returned value, if any, globally escapes.
2200 {
2201 const TypeTuple *r = call->tf()->range();
2202 if (r->cnt() > TypeFunc::Parms) {
2203 const Type* ret_type = r->field_at(TypeFunc::Parms);
2205 // Note: we use isa_ptr() instead of isa_oopptr() here because the
2206 // _multianewarray functions return a TypeRawPtr.
2207 if (ret_type->isa_ptr() != NULL) {
2208 set_escape_state(call_idx, PointsToNode::GlobalEscape);
2209 add_pointsto_edge(resproj_idx, _phantom_object);
2210 }
2211 }
2212 _processed.set(resproj_idx);
2213 }
2214 }
2215 }
2217 // Populate Connection Graph with Ideal nodes and create simple
2218 // connection graph edges (do not need to check the node_type of inputs
2219 // or to call PointsTo() to walk the connection graph).
2220 void ConnectionGraph::record_for_escape_analysis(Node *n, PhaseTransform *phase) {
2221 if (_processed.test(n->_idx))
2222 return; // No need to redefine node's state.
2224 if (n->is_Call()) {
2225 // Arguments to allocation and locking don't escape.
2226 if (n->is_Allocate()) {
2227 add_node(n, PointsToNode::JavaObject, PointsToNode::UnknownEscape, true);
2228 record_for_optimizer(n);
2229 } else if (n->is_Lock() || n->is_Unlock()) {
2230 // Put Lock and Unlock nodes on IGVN worklist to process them during
2231 // the first IGVN optimization when escape information is still available.
2232 record_for_optimizer(n);
2233 _processed.set(n->_idx);
2234 } else {
2235 // Don't mark as processed since call's arguments have to be processed.
2236 PointsToNode::NodeType nt = PointsToNode::UnknownType;
2237 PointsToNode::EscapeState es = PointsToNode::UnknownEscape;
2239 // Check if a call returns an object.
2240 const TypeTuple *r = n->as_Call()->tf()->range();
2241 if (r->cnt() > TypeFunc::Parms &&
2242 r->field_at(TypeFunc::Parms)->isa_ptr() &&
2243 n->as_Call()->proj_out(TypeFunc::Parms) != NULL) {
2244 nt = PointsToNode::JavaObject;
2245 if (!n->is_CallStaticJava()) {
2246 // Since the called mathod is statically unknown assume
2247 // the worst case that the returned value globally escapes.
2248 es = PointsToNode::GlobalEscape;
2249 }
2250 }
2251 add_node(n, nt, es, false);
2252 }
2253 return;
2254 }
2256 // Using isa_ptr() instead of isa_oopptr() for LoadP and Phi because
2257 // ThreadLocal has RawPrt type.
2258 switch (n->Opcode()) {
2259 case Op_AddP:
2260 {
2261 add_node(n, PointsToNode::Field, PointsToNode::UnknownEscape, false);
2262 break;
2263 }
2264 case Op_CastX2P:
2265 { // "Unsafe" memory access.
2266 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, true);
2267 break;
2268 }
2269 case Op_CastPP:
2270 case Op_CheckCastPP:
2271 case Op_EncodeP:
2272 case Op_DecodeN:
2273 {
2274 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false);
2275 int ti = n->in(1)->_idx;
2276 PointsToNode::NodeType nt = ptnode_adr(ti)->node_type();
2277 if (nt == PointsToNode::UnknownType) {
2278 _delayed_worklist.push(n); // Process it later.
2279 break;
2280 } else if (nt == PointsToNode::JavaObject) {
2281 add_pointsto_edge(n->_idx, ti);
2282 } else {
2283 add_deferred_edge(n->_idx, ti);
2284 }
2285 _processed.set(n->_idx);
2286 break;
2287 }
2288 case Op_ConP:
2289 {
2290 // assume all pointer constants globally escape except for null
2291 PointsToNode::EscapeState es;
2292 if (phase->type(n) == TypePtr::NULL_PTR)
2293 es = PointsToNode::NoEscape;
2294 else
2295 es = PointsToNode::GlobalEscape;
2297 add_node(n, PointsToNode::JavaObject, es, true);
2298 break;
2299 }
2300 case Op_ConN:
2301 {
2302 // assume all narrow oop constants globally escape except for null
2303 PointsToNode::EscapeState es;
2304 if (phase->type(n) == TypeNarrowOop::NULL_PTR)
2305 es = PointsToNode::NoEscape;
2306 else
2307 es = PointsToNode::GlobalEscape;
2309 add_node(n, PointsToNode::JavaObject, es, true);
2310 break;
2311 }
2312 case Op_CreateEx:
2313 {
2314 // assume that all exception objects globally escape
2315 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, true);
2316 break;
2317 }
2318 case Op_LoadKlass:
2319 case Op_LoadNKlass:
2320 {
2321 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, true);
2322 break;
2323 }
2324 case Op_LoadP:
2325 case Op_LoadN:
2326 {
2327 const Type *t = phase->type(n);
2328 if (t->make_ptr() == NULL) {
2329 _processed.set(n->_idx);
2330 return;
2331 }
2332 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false);
2333 break;
2334 }
2335 case Op_Parm:
2336 {
2337 _processed.set(n->_idx); // No need to redefine it state.
2338 uint con = n->as_Proj()->_con;
2339 if (con < TypeFunc::Parms)
2340 return;
2341 const Type *t = n->in(0)->as_Start()->_domain->field_at(con);
2342 if (t->isa_ptr() == NULL)
2343 return;
2344 // We have to assume all input parameters globally escape
2345 // (Note: passing 'false' since _processed is already set).
2346 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, false);
2347 break;
2348 }
2349 case Op_Phi:
2350 {
2351 const Type *t = n->as_Phi()->type();
2352 if (t->make_ptr() == NULL) {
2353 // nothing to do if not an oop or narrow oop
2354 _processed.set(n->_idx);
2355 return;
2356 }
2357 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false);
2358 uint i;
2359 for (i = 1; i < n->req() ; i++) {
2360 Node* in = n->in(i);
2361 if (in == NULL)
2362 continue; // ignore NULL
2363 in = in->uncast();
2364 if (in->is_top() || in == n)
2365 continue; // ignore top or inputs which go back this node
2366 int ti = in->_idx;
2367 PointsToNode::NodeType nt = ptnode_adr(ti)->node_type();
2368 if (nt == PointsToNode::UnknownType) {
2369 break;
2370 } else if (nt == PointsToNode::JavaObject) {
2371 add_pointsto_edge(n->_idx, ti);
2372 } else {
2373 add_deferred_edge(n->_idx, ti);
2374 }
2375 }
2376 if (i >= n->req())
2377 _processed.set(n->_idx);
2378 else
2379 _delayed_worklist.push(n);
2380 break;
2381 }
2382 case Op_Proj:
2383 {
2384 // we are only interested in the oop result projection from a call
2385 if (n->as_Proj()->_con == TypeFunc::Parms && n->in(0)->is_Call() ) {
2386 const TypeTuple *r = n->in(0)->as_Call()->tf()->range();
2387 assert(r->cnt() > TypeFunc::Parms, "sanity");
2388 if (r->field_at(TypeFunc::Parms)->isa_ptr() != NULL) {
2389 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false);
2390 int ti = n->in(0)->_idx;
2391 // The call may not be registered yet (since not all its inputs are registered)
2392 // if this is the projection from backbranch edge of Phi.
2393 if (ptnode_adr(ti)->node_type() != PointsToNode::UnknownType) {
2394 process_call_result(n->as_Proj(), phase);
2395 }
2396 if (!_processed.test(n->_idx)) {
2397 // The call's result may need to be processed later if the call
2398 // returns it's argument and the argument is not processed yet.
2399 _delayed_worklist.push(n);
2400 }
2401 break;
2402 }
2403 }
2404 _processed.set(n->_idx);
2405 break;
2406 }
2407 case Op_Return:
2408 {
2409 if( n->req() > TypeFunc::Parms &&
2410 phase->type(n->in(TypeFunc::Parms))->isa_oopptr() ) {
2411 // Treat Return value as LocalVar with GlobalEscape escape state.
2412 add_node(n, PointsToNode::LocalVar, PointsToNode::GlobalEscape, false);
2413 int ti = n->in(TypeFunc::Parms)->_idx;
2414 PointsToNode::NodeType nt = ptnode_adr(ti)->node_type();
2415 if (nt == PointsToNode::UnknownType) {
2416 _delayed_worklist.push(n); // Process it later.
2417 break;
2418 } else if (nt == PointsToNode::JavaObject) {
2419 add_pointsto_edge(n->_idx, ti);
2420 } else {
2421 add_deferred_edge(n->_idx, ti);
2422 }
2423 }
2424 _processed.set(n->_idx);
2425 break;
2426 }
2427 case Op_StoreP:
2428 case Op_StoreN:
2429 {
2430 const Type *adr_type = phase->type(n->in(MemNode::Address));
2431 adr_type = adr_type->make_ptr();
2432 if (adr_type->isa_oopptr()) {
2433 add_node(n, PointsToNode::UnknownType, PointsToNode::UnknownEscape, false);
2434 } else {
2435 Node* adr = n->in(MemNode::Address);
2436 if (adr->is_AddP() && phase->type(adr) == TypeRawPtr::NOTNULL &&
2437 adr->in(AddPNode::Address)->is_Proj() &&
2438 adr->in(AddPNode::Address)->in(0)->is_Allocate()) {
2439 add_node(n, PointsToNode::UnknownType, PointsToNode::UnknownEscape, false);
2440 // We are computing a raw address for a store captured
2441 // by an Initialize compute an appropriate address type.
2442 int offs = (int)phase->find_intptr_t_con(adr->in(AddPNode::Offset), Type::OffsetBot);
2443 assert(offs != Type::OffsetBot, "offset must be a constant");
2444 } else {
2445 _processed.set(n->_idx);
2446 return;
2447 }
2448 }
2449 break;
2450 }
2451 case Op_StorePConditional:
2452 case Op_CompareAndSwapP:
2453 case Op_CompareAndSwapN:
2454 {
2455 const Type *adr_type = phase->type(n->in(MemNode::Address));
2456 adr_type = adr_type->make_ptr();
2457 if (adr_type->isa_oopptr()) {
2458 add_node(n, PointsToNode::UnknownType, PointsToNode::UnknownEscape, false);
2459 } else {
2460 _processed.set(n->_idx);
2461 return;
2462 }
2463 break;
2464 }
2465 case Op_AryEq:
2466 case Op_StrComp:
2467 case Op_StrEquals:
2468 case Op_StrIndexOf:
2469 {
2470 // char[] arrays passed to string intrinsics are not scalar replaceable.
2471 add_node(n, PointsToNode::UnknownType, PointsToNode::UnknownEscape, false);
2472 break;
2473 }
2474 case Op_ThreadLocal:
2475 {
2476 add_node(n, PointsToNode::JavaObject, PointsToNode::ArgEscape, true);
2477 break;
2478 }
2479 default:
2480 ;
2481 // nothing to do
2482 }
2483 return;
2484 }
2486 void ConnectionGraph::build_connection_graph(Node *n, PhaseTransform *phase) {
2487 uint n_idx = n->_idx;
2488 assert(ptnode_adr(n_idx)->_node != NULL, "node should be registered");
2490 // Don't set processed bit for AddP, LoadP, StoreP since
2491 // they may need more then one pass to process.
2492 // Also don't mark as processed Call nodes since their
2493 // arguments may need more then one pass to process.
2494 if (_processed.test(n_idx))
2495 return; // No need to redefine node's state.
2497 if (n->is_Call()) {
2498 CallNode *call = n->as_Call();
2499 process_call_arguments(call, phase);
2500 return;
2501 }
2503 switch (n->Opcode()) {
2504 case Op_AddP:
2505 {
2506 Node *base = get_addp_base(n);
2507 // Create a field edge to this node from everything base could point to.
2508 VectorSet ptset(Thread::current()->resource_area());
2509 PointsTo(ptset, base);
2510 for( VectorSetI i(&ptset); i.test(); ++i ) {
2511 uint pt = i.elem;
2512 add_field_edge(pt, n_idx, address_offset(n, phase));
2513 }
2514 break;
2515 }
2516 case Op_CastX2P:
2517 {
2518 assert(false, "Op_CastX2P");
2519 break;
2520 }
2521 case Op_CastPP:
2522 case Op_CheckCastPP:
2523 case Op_EncodeP:
2524 case Op_DecodeN:
2525 {
2526 int ti = n->in(1)->_idx;
2527 assert(ptnode_adr(ti)->node_type() != PointsToNode::UnknownType, "all nodes should be registered");
2528 if (ptnode_adr(ti)->node_type() == PointsToNode::JavaObject) {
2529 add_pointsto_edge(n_idx, ti);
2530 } else {
2531 add_deferred_edge(n_idx, ti);
2532 }
2533 _processed.set(n_idx);
2534 break;
2535 }
2536 case Op_ConP:
2537 {
2538 assert(false, "Op_ConP");
2539 break;
2540 }
2541 case Op_ConN:
2542 {
2543 assert(false, "Op_ConN");
2544 break;
2545 }
2546 case Op_CreateEx:
2547 {
2548 assert(false, "Op_CreateEx");
2549 break;
2550 }
2551 case Op_LoadKlass:
2552 case Op_LoadNKlass:
2553 {
2554 assert(false, "Op_LoadKlass");
2555 break;
2556 }
2557 case Op_LoadP:
2558 case Op_LoadN:
2559 {
2560 const Type *t = phase->type(n);
2561 #ifdef ASSERT
2562 if (t->make_ptr() == NULL)
2563 assert(false, "Op_LoadP");
2564 #endif
2566 Node* adr = n->in(MemNode::Address)->uncast();
2567 Node* adr_base;
2568 if (adr->is_AddP()) {
2569 adr_base = get_addp_base(adr);
2570 } else {
2571 adr_base = adr;
2572 }
2574 // For everything "adr_base" could point to, create a deferred edge from
2575 // this node to each field with the same offset.
2576 VectorSet ptset(Thread::current()->resource_area());
2577 PointsTo(ptset, adr_base);
2578 int offset = address_offset(adr, phase);
2579 for( VectorSetI i(&ptset); i.test(); ++i ) {
2580 uint pt = i.elem;
2581 add_deferred_edge_to_fields(n_idx, pt, offset);
2582 }
2583 break;
2584 }
2585 case Op_Parm:
2586 {
2587 assert(false, "Op_Parm");
2588 break;
2589 }
2590 case Op_Phi:
2591 {
2592 #ifdef ASSERT
2593 const Type *t = n->as_Phi()->type();
2594 if (t->make_ptr() == NULL)
2595 assert(false, "Op_Phi");
2596 #endif
2597 for (uint i = 1; i < n->req() ; i++) {
2598 Node* in = n->in(i);
2599 if (in == NULL)
2600 continue; // ignore NULL
2601 in = in->uncast();
2602 if (in->is_top() || in == n)
2603 continue; // ignore top or inputs which go back this node
2604 int ti = in->_idx;
2605 PointsToNode::NodeType nt = ptnode_adr(ti)->node_type();
2606 assert(nt != PointsToNode::UnknownType, "all nodes should be known");
2607 if (nt == PointsToNode::JavaObject) {
2608 add_pointsto_edge(n_idx, ti);
2609 } else {
2610 add_deferred_edge(n_idx, ti);
2611 }
2612 }
2613 _processed.set(n_idx);
2614 break;
2615 }
2616 case Op_Proj:
2617 {
2618 // we are only interested in the oop result projection from a call
2619 if (n->as_Proj()->_con == TypeFunc::Parms && n->in(0)->is_Call() ) {
2620 assert(ptnode_adr(n->in(0)->_idx)->node_type() != PointsToNode::UnknownType,
2621 "all nodes should be registered");
2622 const TypeTuple *r = n->in(0)->as_Call()->tf()->range();
2623 assert(r->cnt() > TypeFunc::Parms, "sanity");
2624 if (r->field_at(TypeFunc::Parms)->isa_ptr() != NULL) {
2625 process_call_result(n->as_Proj(), phase);
2626 assert(_processed.test(n_idx), "all call results should be processed");
2627 break;
2628 }
2629 }
2630 assert(false, "Op_Proj");
2631 break;
2632 }
2633 case Op_Return:
2634 {
2635 #ifdef ASSERT
2636 if( n->req() <= TypeFunc::Parms ||
2637 !phase->type(n->in(TypeFunc::Parms))->isa_oopptr() ) {
2638 assert(false, "Op_Return");
2639 }
2640 #endif
2641 int ti = n->in(TypeFunc::Parms)->_idx;
2642 assert(ptnode_adr(ti)->node_type() != PointsToNode::UnknownType, "node should be registered");
2643 if (ptnode_adr(ti)->node_type() == PointsToNode::JavaObject) {
2644 add_pointsto_edge(n_idx, ti);
2645 } else {
2646 add_deferred_edge(n_idx, ti);
2647 }
2648 _processed.set(n_idx);
2649 break;
2650 }
2651 case Op_StoreP:
2652 case Op_StoreN:
2653 case Op_StorePConditional:
2654 case Op_CompareAndSwapP:
2655 case Op_CompareAndSwapN:
2656 {
2657 Node *adr = n->in(MemNode::Address);
2658 const Type *adr_type = phase->type(adr)->make_ptr();
2659 #ifdef ASSERT
2660 if (!adr_type->isa_oopptr())
2661 assert(phase->type(adr) == TypeRawPtr::NOTNULL, "Op_StoreP");
2662 #endif
2664 assert(adr->is_AddP(), "expecting an AddP");
2665 Node *adr_base = get_addp_base(adr);
2666 Node *val = n->in(MemNode::ValueIn)->uncast();
2667 // For everything "adr_base" could point to, create a deferred edge
2668 // to "val" from each field with the same offset.
2669 VectorSet ptset(Thread::current()->resource_area());
2670 PointsTo(ptset, adr_base);
2671 for( VectorSetI i(&ptset); i.test(); ++i ) {
2672 uint pt = i.elem;
2673 add_edge_from_fields(pt, val->_idx, address_offset(adr, phase));
2674 }
2675 break;
2676 }
2677 case Op_AryEq:
2678 case Op_StrComp:
2679 case Op_StrEquals:
2680 case Op_StrIndexOf:
2681 {
2682 // char[] arrays passed to string intrinsic do not escape but
2683 // they are not scalar replaceable. Adjust escape state for them.
2684 // Start from in(2) edge since in(1) is memory edge.
2685 for (uint i = 2; i < n->req(); i++) {
2686 Node* adr = n->in(i)->uncast();
2687 const Type *at = phase->type(adr);
2688 if (!adr->is_top() && at->isa_ptr()) {
2689 assert(at == Type::TOP || at == TypePtr::NULL_PTR ||
2690 at->isa_ptr() != NULL, "expecting an Ptr");
2691 if (adr->is_AddP()) {
2692 adr = get_addp_base(adr);
2693 }
2694 // Mark as ArgEscape everything "adr" could point to.
2695 set_escape_state(adr->_idx, PointsToNode::ArgEscape);
2696 }
2697 }
2698 _processed.set(n_idx);
2699 break;
2700 }
2701 case Op_ThreadLocal:
2702 {
2703 assert(false, "Op_ThreadLocal");
2704 break;
2705 }
2706 default:
2707 // This method should be called only for EA specific nodes.
2708 ShouldNotReachHere();
2709 }
2710 }
2712 #ifndef PRODUCT
2713 void ConnectionGraph::dump() {
2714 bool first = true;
2716 uint size = nodes_size();
2717 for (uint ni = 0; ni < size; ni++) {
2718 PointsToNode *ptn = ptnode_adr(ni);
2719 PointsToNode::NodeType ptn_type = ptn->node_type();
2721 if (ptn_type != PointsToNode::JavaObject || ptn->_node == NULL)
2722 continue;
2723 PointsToNode::EscapeState es = escape_state(ptn->_node);
2724 if (ptn->_node->is_Allocate() && (es == PointsToNode::NoEscape || Verbose)) {
2725 if (first) {
2726 tty->cr();
2727 tty->print("======== Connection graph for ");
2728 _compile->method()->print_short_name();
2729 tty->cr();
2730 first = false;
2731 }
2732 tty->print("%6d ", ni);
2733 ptn->dump();
2734 // Print all locals which reference this allocation
2735 for (uint li = ni; li < size; li++) {
2736 PointsToNode *ptn_loc = ptnode_adr(li);
2737 PointsToNode::NodeType ptn_loc_type = ptn_loc->node_type();
2738 if ( ptn_loc_type == PointsToNode::LocalVar && ptn_loc->_node != NULL &&
2739 ptn_loc->edge_count() == 1 && ptn_loc->edge_target(0) == ni ) {
2740 ptnode_adr(li)->dump(false);
2741 }
2742 }
2743 if (Verbose) {
2744 // Print all fields which reference this allocation
2745 for (uint i = 0; i < ptn->edge_count(); i++) {
2746 uint ei = ptn->edge_target(i);
2747 ptnode_adr(ei)->dump(false);
2748 }
2749 }
2750 tty->cr();
2751 }
2752 }
2753 }
2754 #endif