60 "P", // PointsToEdge |
60 "P", // PointsToEdge |
61 "D", // DeferredEdge |
61 "D", // DeferredEdge |
62 "F" // FieldEdge |
62 "F" // FieldEdge |
63 }; |
63 }; |
64 |
64 |
65 void PointsToNode::dump() const { |
65 void PointsToNode::dump(bool print_state) const { |
66 NodeType nt = node_type(); |
66 NodeType nt = node_type(); |
67 EscapeState es = escape_state(); |
67 tty->print("%s ", node_type_names[(int) nt]); |
68 tty->print("%s %s %s [[", node_type_names[(int) nt], esc_names[(int) es], _scalar_replaceable ? "" : "NSR"); |
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("[["); |
69 for (uint i = 0; i < edge_count(); i++) { |
73 for (uint i = 0; i < edge_count(); i++) { |
70 tty->print(" %d%s", edge_target(i), edge_type_suffix[(int) edge_type(i)]); |
74 tty->print(" %d%s", edge_target(i), edge_type_suffix[(int) edge_type(i)]); |
71 } |
75 } |
72 tty->print("]] "); |
76 tty->print("]] "); |
73 if (_node == NULL) |
77 if (_node == NULL) |
82 _processed(C->comp_arena()), |
86 _processed(C->comp_arena()), |
83 _collecting(true), |
87 _collecting(true), |
84 _compile(C), |
88 _compile(C), |
85 _node_map(C->comp_arena()) { |
89 _node_map(C->comp_arena()) { |
86 |
90 |
87 _phantom_object = C->top()->_idx; |
91 _phantom_object = C->top()->_idx, |
88 PointsToNode *phn = ptnode_adr(_phantom_object); |
92 add_node(C->top(), PointsToNode::JavaObject, PointsToNode::GlobalEscape,true); |
89 phn->_node = C->top(); |
93 |
90 phn->set_node_type(PointsToNode::JavaObject); |
94 // Add ConP(#NULL) and ConN(#NULL) nodes. |
91 phn->set_escape_state(PointsToNode::GlobalEscape); |
95 PhaseGVN* igvn = C->initial_gvn(); |
|
96 Node* oop_null = igvn->zerocon(T_OBJECT); |
|
97 _oop_null = oop_null->_idx; |
|
98 assert(_oop_null < C->unique(), "should be created already"); |
|
99 add_node(oop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true); |
|
100 |
|
101 if (UseCompressedOops) { |
|
102 Node* noop_null = igvn->zerocon(T_NARROWOOP); |
|
103 _noop_null = noop_null->_idx; |
|
104 assert(_noop_null < C->unique(), "should be created already"); |
|
105 add_node(noop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true); |
|
106 } |
92 } |
107 } |
93 |
108 |
94 void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) { |
109 void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) { |
95 PointsToNode *f = ptnode_adr(from_i); |
110 PointsToNode *f = ptnode_adr(from_i); |
96 PointsToNode *t = ptnode_adr(to_i); |
111 PointsToNode *t = ptnode_adr(to_i); |
498 // for the instance type |
513 // for the instance type |
499 int alias_idx = _compile->get_alias_index(tinst); |
514 int alias_idx = _compile->get_alias_index(tinst); |
500 igvn->set_type(addp, tinst); |
515 igvn->set_type(addp, tinst); |
501 // record the allocation in the node map |
516 // record the allocation in the node map |
502 set_map(addp->_idx, get_map(base->_idx)); |
517 set_map(addp->_idx, get_map(base->_idx)); |
503 // if the Address input is not the appropriate instance type |
518 |
504 // (due to intervening casts,) insert a cast |
519 // Set addp's Base and Address to 'base'. |
505 Node *adr = addp->in(AddPNode::Address); |
520 Node *abase = addp->in(AddPNode::Base); |
506 const TypeOopPtr *atype = igvn->type(adr)->isa_oopptr(); |
521 Node *adr = addp->in(AddPNode::Address); |
507 if (atype != NULL && atype->instance_id() != inst_id) { |
522 if (adr->is_Proj() && adr->in(0)->is_Allocate() && |
508 assert(!atype->is_known_instance(), "no conflicting instances"); |
523 adr->in(0)->_idx == (uint)inst_id) { |
509 const TypeOopPtr *new_atype = base_t->add_offset(atype->offset())->isa_oopptr(); |
524 // Skip AddP cases #3 and #5. |
510 Node *acast = new (_compile, 2) CastPPNode(adr, new_atype); |
525 } else { |
511 acast->set_req(0, adr->in(0)); |
526 assert(!abase->is_top(), "sanity"); // AddP case #3 |
512 igvn->set_type(acast, new_atype); |
527 if (abase != base) { |
513 record_for_optimizer(acast); |
528 igvn->hash_delete(addp); |
514 Node *bcast = acast; |
529 addp->set_req(AddPNode::Base, base); |
515 Node *abase = addp->in(AddPNode::Base); |
530 if (abase == adr) { |
516 if (abase != adr) { |
531 addp->set_req(AddPNode::Address, base); |
517 bcast = new (_compile, 2) CastPPNode(abase, base_t); |
532 } else { |
518 bcast->set_req(0, abase->in(0)); |
533 // AddP case #4 (adr is array's element offset AddP node) |
519 igvn->set_type(bcast, base_t); |
534 #ifdef ASSERT |
520 record_for_optimizer(bcast); |
535 const TypeOopPtr *atype = igvn->type(adr)->isa_oopptr(); |
521 } |
536 assert(adr->is_AddP() && atype != NULL && |
522 igvn->hash_delete(addp); |
537 atype->instance_id() == inst_id, "array's element offset should be processed first"); |
523 addp->set_req(AddPNode::Base, bcast); |
538 #endif |
524 addp->set_req(AddPNode::Address, acast); |
539 } |
525 igvn->hash_insert(addp); |
540 igvn->hash_insert(addp); |
|
541 } |
526 } |
542 } |
527 // Put on IGVN worklist since at least addp's type was changed above. |
543 // Put on IGVN worklist since at least addp's type was changed above. |
528 record_for_optimizer(addp); |
544 record_for_optimizer(addp); |
529 } |
545 } |
530 |
546 |
658 if (orig_mem == NULL) |
674 if (orig_mem == NULL) |
659 return orig_mem; |
675 return orig_mem; |
660 Compile* C = phase->C; |
676 Compile* C = phase->C; |
661 const TypeOopPtr *tinst = C->get_adr_type(alias_idx)->isa_oopptr(); |
677 const TypeOopPtr *tinst = C->get_adr_type(alias_idx)->isa_oopptr(); |
662 bool is_instance = (tinst != NULL) && tinst->is_known_instance(); |
678 bool is_instance = (tinst != NULL) && tinst->is_known_instance(); |
|
679 Node *start_mem = C->start()->proj_out(TypeFunc::Memory); |
663 Node *prev = NULL; |
680 Node *prev = NULL; |
664 Node *result = orig_mem; |
681 Node *result = orig_mem; |
665 while (prev != result) { |
682 while (prev != result) { |
666 prev = result; |
683 prev = result; |
|
684 if (result == start_mem) |
|
685 break; // hit one of our sentinals |
667 if (result->is_Mem()) { |
686 if (result->is_Mem()) { |
668 MemNode *mem = result->as_Mem(); |
687 const Type *at = phase->type(result->in(MemNode::Address)); |
669 const Type *at = phase->type(mem->in(MemNode::Address)); |
|
670 if (at != Type::TOP) { |
688 if (at != Type::TOP) { |
671 assert (at->isa_ptr() != NULL, "pointer type required."); |
689 assert (at->isa_ptr() != NULL, "pointer type required."); |
672 int idx = C->get_alias_index(at->is_ptr()); |
690 int idx = C->get_alias_index(at->is_ptr()); |
673 if (idx == alias_idx) |
691 if (idx == alias_idx) |
674 break; |
692 break; |
675 } |
693 } |
676 result = mem->in(MemNode::Memory); |
694 result = result->in(MemNode::Memory); |
677 } |
695 } |
678 if (!is_instance) |
696 if (!is_instance) |
679 continue; // don't search further for non-instance types |
697 continue; // don't search further for non-instance types |
680 // skip over a call which does not affect this memory slice |
698 // skip over a call which does not affect this memory slice |
681 if (result->is_Proj() && result->as_Proj()->_con == TypeFunc::Memory) { |
699 if (result->is_Proj() && result->as_Proj()->_con == TypeFunc::Memory) { |
682 Node *proj_in = result->in(0); |
700 Node *proj_in = result->in(0); |
683 if (proj_in->is_Call()) { |
701 if (proj_in->is_Allocate() && proj_in->_idx == (uint)tinst->instance_id()) { |
|
702 break; // hit one of our sentinals |
|
703 } else if (proj_in->is_Call()) { |
684 CallNode *call = proj_in->as_Call(); |
704 CallNode *call = proj_in->as_Call(); |
685 if (!call->may_modify(tinst, phase)) { |
705 if (!call->may_modify(tinst, phase)) { |
686 result = call->in(TypeFunc::Memory); |
706 result = call->in(TypeFunc::Memory); |
687 } |
707 } |
688 } else if (proj_in->is_Initialize()) { |
708 } else if (proj_in->is_Initialize()) { |
1004 memnode_worklist.append_if_missing(use); |
1024 memnode_worklist.append_if_missing(use); |
1005 } else if (use->is_Initialize()) { |
1025 } else if (use->is_Initialize()) { |
1006 memnode_worklist.append_if_missing(use); |
1026 memnode_worklist.append_if_missing(use); |
1007 } else if (use->is_MergeMem()) { |
1027 } else if (use->is_MergeMem()) { |
1008 mergemem_worklist.append_if_missing(use); |
1028 mergemem_worklist.append_if_missing(use); |
1009 } else if (use->is_Call() && tinst != NULL) { |
1029 } else if (use->is_SafePoint() && tinst != NULL) { |
1010 // Look for MergeMem nodes for calls which reference unique allocation |
1030 // Look for MergeMem nodes for calls which reference unique allocation |
1011 // (through CheckCastPP nodes) even for debug info. |
1031 // (through CheckCastPP nodes) even for debug info. |
1012 Node* m = use->in(TypeFunc::Memory); |
1032 Node* m = use->in(TypeFunc::Memory); |
1013 uint iid = tinst->instance_id(); |
1033 uint iid = tinst->instance_id(); |
1014 while (m->is_Proj() && m->in(0)->is_Call() && |
1034 while (m->is_Proj() && m->in(0)->is_SafePoint() && |
1015 m->in(0) != use && !m->in(0)->_idx != iid) { |
1035 m->in(0) != use && !m->in(0)->_idx != iid) { |
1016 m = m->in(0)->in(TypeFunc::Memory); |
1036 m = m->in(0)->in(TypeFunc::Memory); |
1017 } |
1037 } |
1018 if (m->is_MergeMem()) { |
1038 if (m->is_MergeMem()) { |
1019 mergemem_worklist.append_if_missing(m); |
1039 mergemem_worklist.append_if_missing(m); |
1346 PointsToNode::NodeType nt = ptn->node_type(); |
1366 PointsToNode::NodeType nt = ptn->node_type(); |
1347 if (nt == PointsToNode::LocalVar || nt == PointsToNode::Field) { |
1367 if (nt == PointsToNode::LocalVar || nt == PointsToNode::Field) { |
1348 remove_deferred(ni, &deferred_edges, &visited); |
1368 remove_deferred(ni, &deferred_edges, &visited); |
1349 Node *n = ptn->_node; |
1369 Node *n = ptn->_node; |
1350 if (n->is_AddP()) { |
1370 if (n->is_AddP()) { |
1351 // If this AddP computes an address which may point to more that one |
1371 // Search for objects which are not scalar replaceable. |
1352 // object or more then one field (array's element), nothing the address |
1372 // Mark their escape state as ArgEscape to propagate the state |
1353 // points to can be scalar replaceable. |
1373 // to referenced objects. |
|
1374 // Note: currently there are no difference in compiler optimizations |
|
1375 // for ArgEscape objects and NoEscape objects which are not |
|
1376 // scalar replaceable. |
|
1377 |
|
1378 int offset = ptn->offset(); |
1354 Node *base = get_addp_base(n); |
1379 Node *base = get_addp_base(n); |
1355 ptset.Clear(); |
1380 ptset.Clear(); |
1356 PointsTo(ptset, base, igvn); |
1381 PointsTo(ptset, base, igvn); |
1357 if (ptset.Size() > 1 || |
1382 int ptset_size = ptset.Size(); |
1358 (ptset.Size() != 0 && ptn->offset() == Type::OffsetBot)) { |
1383 |
|
1384 // Check if a field's initializing value is recorded and add |
|
1385 // a corresponding NULL field's value if it is not recorded. |
|
1386 // Connection Graph does not record a default initialization by NULL |
|
1387 // captured by Initialize node. |
|
1388 // |
|
1389 // Note: it will disable scalar replacement in some cases: |
|
1390 // |
|
1391 // Point p[] = new Point[1]; |
|
1392 // p[0] = new Point(); // Will be not scalar replaced |
|
1393 // |
|
1394 // but it will save us from incorrect optimizations in next cases: |
|
1395 // |
|
1396 // Point p[] = new Point[1]; |
|
1397 // if ( x ) p[0] = new Point(); // Will be not scalar replaced |
|
1398 // |
|
1399 // Without a control flow analysis we can't distinguish above cases. |
|
1400 // |
|
1401 if (offset != Type::OffsetBot && ptset_size == 1) { |
|
1402 uint elem = ptset.getelem(); // Allocation node's index |
|
1403 // It does not matter if it is not Allocation node since |
|
1404 // only non-escaping allocations are scalar replaced. |
|
1405 if (ptnode_adr(elem)->_node->is_Allocate() && |
|
1406 ptnode_adr(elem)->escape_state() == PointsToNode::NoEscape) { |
|
1407 AllocateNode* alloc = ptnode_adr(elem)->_node->as_Allocate(); |
|
1408 InitializeNode* ini = alloc->initialization(); |
|
1409 Node* value = NULL; |
|
1410 if (ini != NULL) { |
|
1411 BasicType ft = UseCompressedOops ? T_NARROWOOP : T_OBJECT; |
|
1412 Node* store = ini->find_captured_store(offset, type2aelembytes(ft), igvn); |
|
1413 if (store != NULL && store->is_Store()) |
|
1414 value = store->in(MemNode::ValueIn); |
|
1415 } |
|
1416 if (value == NULL || value != ptnode_adr(value->_idx)->_node) { |
|
1417 // A field's initializing value was not recorded. Add NULL. |
|
1418 uint null_idx = UseCompressedOops ? _noop_null : _oop_null; |
|
1419 add_pointsto_edge(ni, null_idx); |
|
1420 } |
|
1421 } |
|
1422 } |
|
1423 |
|
1424 // An object is not scalar replaceable if the field which may point |
|
1425 // to it has unknown offset (unknown element of an array of objects). |
|
1426 // |
|
1427 if (offset == Type::OffsetBot) { |
|
1428 uint e_cnt = ptn->edge_count(); |
|
1429 for (uint ei = 0; ei < e_cnt; ei++) { |
|
1430 uint npi = ptn->edge_target(ei); |
|
1431 set_escape_state(npi, PointsToNode::ArgEscape); |
|
1432 ptnode_adr(npi)->_scalar_replaceable = false; |
|
1433 } |
|
1434 } |
|
1435 |
|
1436 // Currently an object is not scalar replaceable if a LoadStore node |
|
1437 // access its field since the field value is unknown after it. |
|
1438 // |
|
1439 bool has_LoadStore = false; |
|
1440 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { |
|
1441 Node *use = n->fast_out(i); |
|
1442 if (use->is_LoadStore()) { |
|
1443 has_LoadStore = true; |
|
1444 break; |
|
1445 } |
|
1446 } |
|
1447 // An object is not scalar replaceable if the address points |
|
1448 // to unknown field (unknown element for arrays, offset is OffsetBot). |
|
1449 // |
|
1450 // Or the address may point to more then one object. This may produce |
|
1451 // the false positive result (set scalar_replaceable to false) |
|
1452 // since the flow-insensitive escape analysis can't separate |
|
1453 // the case when stores overwrite the field's value from the case |
|
1454 // when stores happened on different control branches. |
|
1455 // |
|
1456 if (ptset_size > 1 || ptset_size != 0 && |
|
1457 (has_LoadStore || offset == Type::OffsetBot)) { |
1359 for( VectorSetI j(&ptset); j.test(); ++j ) { |
1458 for( VectorSetI j(&ptset); j.test(); ++j ) { |
|
1459 set_escape_state(j.elem, PointsToNode::ArgEscape); |
1360 ptnode_adr(j.elem)->_scalar_replaceable = false; |
1460 ptnode_adr(j.elem)->_scalar_replaceable = false; |
1361 } |
1461 } |
1362 } |
1462 } |
1363 } |
1463 } |
1364 } |
1464 } |
2211 for (uint li = ni; li < size; li++) { |
2313 for (uint li = ni; li < size; li++) { |
2212 PointsToNode *ptn_loc = ptnode_adr(li); |
2314 PointsToNode *ptn_loc = ptnode_adr(li); |
2213 PointsToNode::NodeType ptn_loc_type = ptn_loc->node_type(); |
2315 PointsToNode::NodeType ptn_loc_type = ptn_loc->node_type(); |
2214 if ( ptn_loc_type == PointsToNode::LocalVar && ptn_loc->_node != NULL && |
2316 if ( ptn_loc_type == PointsToNode::LocalVar && ptn_loc->_node != NULL && |
2215 ptn_loc->edge_count() == 1 && ptn_loc->edge_target(0) == ni ) { |
2317 ptn_loc->edge_count() == 1 && ptn_loc->edge_target(0) == ni ) { |
2216 tty->print("%6d LocalVar [[%d]]", li, ni); |
2318 ptnode_adr(li)->dump(false); |
2217 ptnode_adr(li)->_node->dump(); |
|
2218 } |
2319 } |
2219 } |
2320 } |
2220 if (Verbose) { |
2321 if (Verbose) { |
2221 // Print all fields which reference this allocation |
2322 // Print all fields which reference this allocation |
2222 for (uint i = 0; i < ptn->edge_count(); i++) { |
2323 for (uint i = 0; i < ptn->edge_count(); i++) { |
2223 uint ei = ptn->edge_target(i); |
2324 uint ei = ptn->edge_target(i); |
2224 tty->print("%6d Field [[%d]]", ei, ni); |
2325 ptnode_adr(ei)->dump(false); |
2225 ptnode_adr(ei)->_node->dump(); |
|
2226 } |
2326 } |
2227 } |
2327 } |
2228 tty->cr(); |
2328 tty->cr(); |
2229 } |
2329 } |
2230 } |
2330 } |