Mercurial > hg > truffle

comparison src/share/vm/opto/escape.cpp @ 253:b0fe4deeb9fb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.") Summary: Escape Analysis fixes. Reviewed-by: never, rasbold
author kvn
date Mon, 28 Jul 2008 17:12:52 -0700
parents 02a35ad4adf8
children c3e045194476
comparison
equal deleted inserted replaced
252:be7facf71163 253:b0fe4deeb9fb
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 }
1853 } 1953 }
1854 case Op_LoadP: 1954 case Op_LoadP:
1855 case Op_LoadN: 1955 case Op_LoadN:
1856 { 1956 {
1857 const Type *t = phase->type(n); 1957 const Type *t = phase->type(n);
1858 if (!t->isa_narrowoop() && t->isa_ptr() == NULL) { 1958 if (t->make_ptr() == NULL) {
1859 _processed.set(n->_idx); 1959 _processed.set(n->_idx);
1860 return; 1960 return;
1861 } 1961 }
1862 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false); 1962 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false);
1863 break; 1963 break;
1876 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, false); 1976 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, false);
1877 break; 1977 break;
1878 } 1978 }
1879 case Op_Phi: 1979 case Op_Phi:
1880 { 1980 {
1881 if (n->as_Phi()->type()->isa_ptr() == NULL) { 1981 const Type *t = n->as_Phi()->type();
1882 // nothing to do if not an oop 1982 if (t->make_ptr() == NULL) {
1983 // nothing to do if not an oop or narrow oop
1883 _processed.set(n->_idx); 1984 _processed.set(n->_idx);
1884 return; 1985 return;
1885 } 1986 }
1886 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false); 1987 add_node(n, PointsToNode::LocalVar, PointsToNode::UnknownEscape, false);
1887 uint i; 1988 uint i;
2065 case Op_LoadP: 2166 case Op_LoadP:
2066 case Op_LoadN: 2167 case Op_LoadN:
2067 { 2168 {
2068 const Type *t = phase->type(n); 2169 const Type *t = phase->type(n);
2069 #ifdef ASSERT 2170 #ifdef ASSERT
2070 if (!t->isa_narrowoop() && t->isa_ptr() == NULL) 2171 if (t->make_ptr() == NULL)
2071 assert(false, "Op_LoadP"); 2172 assert(false, "Op_LoadP");
2072 #endif 2173 #endif
2073 2174
2074 Node* adr = n->in(MemNode::Address)->uncast(); 2175 Node* adr = n->in(MemNode::Address)->uncast();
2075 const Type *adr_type = phase->type(adr); 2176 const Type *adr_type = phase->type(adr);
2097 break; 2198 break;
2098 } 2199 }
2099 case Op_Phi: 2200 case Op_Phi:
2100 { 2201 {
2101 #ifdef ASSERT 2202 #ifdef ASSERT
2102 if (n->as_Phi()->type()->isa_ptr() == NULL) 2203 const Type *t = n->as_Phi()->type();
2204 if (t->make_ptr() == NULL)
2103 assert(false, "Op_Phi"); 2205 assert(false, "Op_Phi");
2104 #endif 2206 #endif
2105 for (uint i = 1; i < n->req() ; i++) { 2207 for (uint i = 1; i < n->req() ; i++) {
2106 Node* in = n->in(i); 2208 Node* in = n->in(i);
2107 if (in == NULL) 2209 if (in == NULL)
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 }