117 assert(_noop_null < nodes_size(), "should be created already"); |
117 assert(_noop_null < nodes_size(), "should be created already"); |
118 add_node(noop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true); |
118 add_node(noop_null, PointsToNode::JavaObject, PointsToNode::NoEscape, true); |
119 } else { |
119 } else { |
120 _noop_null = _oop_null; // Should be initialized |
120 _noop_null = _oop_null; // Should be initialized |
121 } |
121 } |
|
122 _pcmp_neq = NULL; // Should be initialized |
|
123 _pcmp_eq = NULL; |
122 } |
124 } |
123 |
125 |
124 void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) { |
126 void ConnectionGraph::add_pointsto_edge(uint from_i, uint to_i) { |
125 PointsToNode *f = ptnode_adr(from_i); |
127 PointsToNode *f = ptnode_adr(from_i); |
126 PointsToNode *t = ptnode_adr(to_i); |
128 PointsToNode *t = ptnode_adr(to_i); |
307 deferred_edges->clear(); |
309 deferred_edges->clear(); |
308 visited->Reset(); |
310 visited->Reset(); |
309 |
311 |
310 visited->set(ni); |
312 visited->set(ni); |
311 PointsToNode *ptn = ptnode_adr(ni); |
313 PointsToNode *ptn = ptnode_adr(ni); |
|
314 if (ptn->edge_count() == 0) { |
|
315 // No deferred or pointsto edges found. Assume the value was set |
|
316 // outside this method. Add edge to phantom object. |
|
317 add_pointsto_edge(ni, _phantom_object); |
|
318 } |
312 |
319 |
313 // Mark current edges as visited and move deferred edges to separate array. |
320 // Mark current edges as visited and move deferred edges to separate array. |
314 for (uint i = 0; i < ptn->edge_count(); ) { |
321 for (uint i = 0; i < ptn->edge_count(); ) { |
315 uint t = ptn->edge_target(i); |
322 uint t = ptn->edge_target(i); |
316 #ifdef ASSERT |
323 #ifdef ASSERT |
327 } |
334 } |
328 for (int next = 0; next < deferred_edges->length(); ++next) { |
335 for (int next = 0; next < deferred_edges->length(); ++next) { |
329 uint t = deferred_edges->at(next); |
336 uint t = deferred_edges->at(next); |
330 PointsToNode *ptt = ptnode_adr(t); |
337 PointsToNode *ptt = ptnode_adr(t); |
331 uint e_cnt = ptt->edge_count(); |
338 uint e_cnt = ptt->edge_count(); |
|
339 if (e_cnt == 0) { |
|
340 // No deferred or pointsto edges found. Assume the value was set |
|
341 // outside this method. Add edge to phantom object. |
|
342 add_pointsto_edge(t, _phantom_object); |
|
343 add_pointsto_edge(ni, _phantom_object); |
|
344 } |
332 for (uint e = 0; e < e_cnt; e++) { |
345 for (uint e = 0; e < e_cnt; e++) { |
333 uint etgt = ptt->edge_target(e); |
346 uint etgt = ptt->edge_target(e); |
334 if (visited->test_set(etgt)) |
347 if (visited->test_set(etgt)) |
335 continue; |
348 continue; |
336 |
349 |
390 } |
403 } |
391 if (offset == offs || offset == Type::OffsetBot || offs == Type::OffsetBot) { |
404 if (offset == offs || offset == Type::OffsetBot || offs == Type::OffsetBot) { |
392 add_deferred_edge(from_i, fi); |
405 add_deferred_edge(from_i, fi); |
393 } |
406 } |
394 } |
407 } |
|
408 // Some fields references (AddP) may still be missing |
|
409 // until Connection Graph construction is complete. |
|
410 // For example, loads from RAW pointers with offset 0 |
|
411 // which don't have AddP. |
|
412 // A reference to phantom_object will be added if |
|
413 // a field reference is still missing after completing |
|
414 // Connection Graph (see remove_deferred()). |
395 } |
415 } |
396 |
416 |
397 // Helper functions |
417 // Helper functions |
398 |
418 |
399 static Node* get_addp_base(Node *addp) { |
419 static Node* get_addp_base(Node *addp) { |
1538 worklist_init.push(C->root()); |
1558 worklist_init.push(C->root()); |
1539 } |
1559 } |
1540 |
1560 |
1541 GrowableArray<Node*> alloc_worklist; |
1561 GrowableArray<Node*> alloc_worklist; |
1542 GrowableArray<Node*> addp_worklist; |
1562 GrowableArray<Node*> addp_worklist; |
|
1563 GrowableArray<Node*> ptr_cmp_worklist; |
1543 PhaseGVN* igvn = _igvn; |
1564 PhaseGVN* igvn = _igvn; |
1544 bool has_allocations = false; |
1565 bool has_allocations = false; |
1545 |
1566 |
1546 // Push all useful nodes onto CG list and set their type. |
1567 // Push all useful nodes onto CG list and set their type. |
1547 for( uint next = 0; next < worklist_init.size(); ++next ) { |
1568 for( uint next = 0; next < worklist_init.size(); ++next ) { |
1552 if (n->is_Allocate() || n->is_CallStaticJava() && |
1573 if (n->is_Allocate() || n->is_CallStaticJava() && |
1553 ptnode_adr(n->_idx)->node_type() == PointsToNode::JavaObject) { |
1574 ptnode_adr(n->_idx)->node_type() == PointsToNode::JavaObject) { |
1554 has_allocations = true; |
1575 has_allocations = true; |
1555 if (n->is_Allocate()) |
1576 if (n->is_Allocate()) |
1556 alloc_worklist.append(n); |
1577 alloc_worklist.append(n); |
1557 } |
1578 } else if(n->is_AddP()) { |
1558 if(n->is_AddP()) { |
|
1559 // Collect address nodes. Use them during stage 3 below |
1579 // Collect address nodes. Use them during stage 3 below |
1560 // to build initial connection graph field edges. |
1580 // to build initial connection graph field edges. |
1561 addp_worklist.append(n); |
1581 addp_worklist.append(n); |
1562 } else if (n->is_MergeMem()) { |
1582 } else if (n->is_MergeMem()) { |
1563 // Collect all MergeMem nodes to add memory slices for |
1583 // Collect all MergeMem nodes to add memory slices for |
1564 // scalar replaceable objects in split_unique_types(). |
1584 // scalar replaceable objects in split_unique_types(). |
1565 _mergemem_worklist.append(n->as_MergeMem()); |
1585 _mergemem_worklist.append(n->as_MergeMem()); |
|
1586 } else if (OptimizePtrCompare && n->is_Cmp() && |
|
1587 (n->Opcode() == Op_CmpP || n->Opcode() == Op_CmpN)) { |
|
1588 // Compare pointers nodes |
|
1589 ptr_cmp_worklist.append(n); |
1566 } |
1590 } |
1567 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { |
1591 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { |
1568 Node* m = n->fast_out(i); // Get user |
1592 Node* m = n->fast_out(i); // Get user |
1569 worklist_init.push(m); |
1593 worklist_init.push(m); |
1570 } |
1594 } |
1586 // to reduce number of iterations during stage 4 below. |
1610 // to reduce number of iterations during stage 4 below. |
1587 uint addp_length = addp_worklist.length(); |
1611 uint addp_length = addp_worklist.length(); |
1588 for( uint next = 0; next < addp_length; ++next ) { |
1612 for( uint next = 0; next < addp_length; ++next ) { |
1589 Node* n = addp_worklist.at(next); |
1613 Node* n = addp_worklist.at(next); |
1590 Node* base = get_addp_base(n); |
1614 Node* base = get_addp_base(n); |
1591 if (base->is_Proj()) |
1615 if (base->is_Proj() && base->in(0)->is_Call()) |
1592 base = base->in(0); |
1616 base = base->in(0); |
1593 PointsToNode::NodeType nt = ptnode_adr(base->_idx)->node_type(); |
1617 PointsToNode::NodeType nt = ptnode_adr(base->_idx)->node_type(); |
1594 if (nt == PointsToNode::JavaObject) { |
1618 if (nt == PointsToNode::JavaObject) { |
1595 build_connection_graph(n, igvn); |
1619 build_connection_graph(n, igvn); |
1596 } |
1620 } |
1673 int ni = cg_worklist.at(next); |
1697 int ni = cg_worklist.at(next); |
1674 PointsToNode* ptn = ptnode_adr(ni); |
1698 PointsToNode* ptn = ptnode_adr(ni); |
1675 PointsToNode::NodeType nt = ptn->node_type(); |
1699 PointsToNode::NodeType nt = ptn->node_type(); |
1676 if (nt == PointsToNode::LocalVar || nt == PointsToNode::Field) { |
1700 if (nt == PointsToNode::LocalVar || nt == PointsToNode::Field) { |
1677 remove_deferred(ni, &worklist, &visited); |
1701 remove_deferred(ni, &worklist, &visited); |
1678 Node *n = ptn->_node; |
|
1679 } |
1702 } |
1680 } |
1703 } |
1681 |
1704 |
1682 // 7. Adjust escape state of nonescaping objects. |
1705 // 7. Adjust escape state of nonescaping objects. |
1683 for (uint next = 0; next < addp_length; ++next) { |
1706 for (uint next = 0; next < addp_length; ++next) { |
1757 alock->set_eliminated(); |
1780 alock->set_eliminated(); |
1758 } |
1781 } |
1759 } |
1782 } |
1760 } |
1783 } |
1761 } |
1784 } |
|
1785 } |
|
1786 |
|
1787 if (OptimizePtrCompare && has_non_escaping_obj) { |
|
1788 // Add ConI(#CC_GT) and ConI(#CC_EQ). |
|
1789 _pcmp_neq = igvn->makecon(TypeInt::CC_GT); |
|
1790 _pcmp_eq = igvn->makecon(TypeInt::CC_EQ); |
|
1791 // Optimize objects compare. |
|
1792 while (ptr_cmp_worklist.length() != 0) { |
|
1793 Node *n = ptr_cmp_worklist.pop(); |
|
1794 Node *res = optimize_ptr_compare(n); |
|
1795 if (res != NULL) { |
|
1796 #ifndef PRODUCT |
|
1797 if (PrintOptimizePtrCompare) { |
|
1798 tty->print_cr("++++ Replaced: %d %s(%d,%d) --> %s", n->_idx, (n->Opcode() == Op_CmpP ? "CmpP" : "CmpN"), n->in(1)->_idx, n->in(2)->_idx, (res == _pcmp_eq ? "EQ" : "NotEQ")); |
|
1799 if (Verbose) { |
|
1800 n->dump(1); |
|
1801 } |
|
1802 } |
|
1803 #endif |
|
1804 _igvn->replace_node(n, res); |
|
1805 } |
|
1806 } |
|
1807 // cleanup |
|
1808 if (_pcmp_neq->outcnt() == 0) |
|
1809 igvn->hash_delete(_pcmp_neq); |
|
1810 if (_pcmp_eq->outcnt() == 0) |
|
1811 igvn->hash_delete(_pcmp_eq); |
1762 } |
1812 } |
1763 |
1813 |
1764 #ifndef PRODUCT |
1814 #ifndef PRODUCT |
1765 if (PrintEscapeAnalysis) { |
1815 if (PrintEscapeAnalysis) { |
1766 dump(); // Dump ConnectionGraph |
1816 dump(); // Dump ConnectionGraph |
2006 } |
2056 } |
2007 // Has not escaping java objects |
2057 // Has not escaping java objects |
2008 return has_java_obj && (esc_state < PointsToNode::GlobalEscape); |
2058 return has_java_obj && (esc_state < PointsToNode::GlobalEscape); |
2009 } |
2059 } |
2010 |
2060 |
|
2061 // Optimize objects compare. |
|
2062 Node* ConnectionGraph::optimize_ptr_compare(Node* n) { |
|
2063 assert(OptimizePtrCompare, "sanity"); |
|
2064 // Clone returned Set since PointsTo() returns pointer |
|
2065 // to the same structure ConnectionGraph.pt_ptset. |
|
2066 VectorSet ptset1 = *PointsTo(n->in(1)); |
|
2067 VectorSet ptset2 = *PointsTo(n->in(2)); |
|
2068 |
|
2069 // Check simple cases first. |
|
2070 if (ptset1.Size() == 1) { |
|
2071 uint pt1 = ptset1.getelem(); |
|
2072 PointsToNode* ptn1 = ptnode_adr(pt1); |
|
2073 if (ptn1->escape_state() == PointsToNode::NoEscape) { |
|
2074 if (ptset2.Size() == 1 && ptset2.getelem() == pt1) { |
|
2075 // Comparing the same not escaping object. |
|
2076 return _pcmp_eq; |
|
2077 } |
|
2078 Node* obj = ptn1->_node; |
|
2079 // Comparing not escaping allocation. |
|
2080 if ((obj->is_Allocate() || obj->is_CallStaticJava()) && |
|
2081 !ptset2.test(pt1)) { |
|
2082 return _pcmp_neq; // This includes nullness check. |
|
2083 } |
|
2084 } |
|
2085 } else if (ptset2.Size() == 1) { |
|
2086 uint pt2 = ptset2.getelem(); |
|
2087 PointsToNode* ptn2 = ptnode_adr(pt2); |
|
2088 if (ptn2->escape_state() == PointsToNode::NoEscape) { |
|
2089 Node* obj = ptn2->_node; |
|
2090 // Comparing not escaping allocation. |
|
2091 if ((obj->is_Allocate() || obj->is_CallStaticJava()) && |
|
2092 !ptset1.test(pt2)) { |
|
2093 return _pcmp_neq; // This includes nullness check. |
|
2094 } |
|
2095 } |
|
2096 } |
|
2097 |
|
2098 if (!ptset1.disjoint(ptset2)) { |
|
2099 return NULL; // Sets are not disjoint |
|
2100 } |
|
2101 |
|
2102 // Sets are disjoint. |
|
2103 bool set1_has_unknown_ptr = ptset1.test(_phantom_object) != 0; |
|
2104 bool set2_has_unknown_ptr = ptset2.test(_phantom_object) != 0; |
|
2105 bool set1_has_null_ptr = (ptset1.test(_oop_null) | ptset1.test(_noop_null)) != 0; |
|
2106 bool set2_has_null_ptr = (ptset2.test(_oop_null) | ptset2.test(_noop_null)) != 0; |
|
2107 |
|
2108 if (set1_has_unknown_ptr && set2_has_null_ptr || |
|
2109 set2_has_unknown_ptr && set1_has_null_ptr) { |
|
2110 // Check nullness of unknown object. |
|
2111 return NULL; |
|
2112 } |
|
2113 |
|
2114 // Disjointness by itself is not sufficient since |
|
2115 // alias analysis is not complete for escaped objects. |
|
2116 // Disjoint sets are definitely unrelated only when |
|
2117 // at least one set has only not escaping objects. |
|
2118 if (!set1_has_unknown_ptr && !set1_has_null_ptr) { |
|
2119 bool has_only_non_escaping_alloc = true; |
|
2120 for (VectorSetI i(&ptset1); i.test(); ++i) { |
|
2121 uint pt = i.elem; |
|
2122 PointsToNode* ptn = ptnode_adr(pt); |
|
2123 Node* obj = ptn->_node; |
|
2124 if (ptn->escape_state() != PointsToNode::NoEscape || |
|
2125 !(obj->is_Allocate() || obj->is_CallStaticJava())) { |
|
2126 has_only_non_escaping_alloc = false; |
|
2127 break; |
|
2128 } |
|
2129 } |
|
2130 if (has_only_non_escaping_alloc) { |
|
2131 return _pcmp_neq; |
|
2132 } |
|
2133 } |
|
2134 if (!set2_has_unknown_ptr && !set2_has_null_ptr) { |
|
2135 bool has_only_non_escaping_alloc = true; |
|
2136 for (VectorSetI i(&ptset2); i.test(); ++i) { |
|
2137 uint pt = i.elem; |
|
2138 PointsToNode* ptn = ptnode_adr(pt); |
|
2139 Node* obj = ptn->_node; |
|
2140 if (ptn->escape_state() != PointsToNode::NoEscape || |
|
2141 !(obj->is_Allocate() || obj->is_CallStaticJava())) { |
|
2142 has_only_non_escaping_alloc = false; |
|
2143 break; |
|
2144 } |
|
2145 } |
|
2146 if (has_only_non_escaping_alloc) { |
|
2147 return _pcmp_neq; |
|
2148 } |
|
2149 } |
|
2150 return NULL; |
|
2151 } |
|
2152 |
2011 void ConnectionGraph::process_call_arguments(CallNode *call, PhaseTransform *phase) { |
2153 void ConnectionGraph::process_call_arguments(CallNode *call, PhaseTransform *phase) { |
2012 |
2154 |
2013 switch (call->Opcode()) { |
2155 switch (call->Opcode()) { |
2014 #ifdef ASSERT |
2156 #ifdef ASSERT |
2015 case Op_Allocate: |
2157 case Op_Allocate: |
2429 // We have to assume all input parameters globally escape |
2571 // We have to assume all input parameters globally escape |
2430 // (Note: passing 'false' since _processed is already set). |
2572 // (Note: passing 'false' since _processed is already set). |
2431 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, false); |
2573 add_node(n, PointsToNode::JavaObject, PointsToNode::GlobalEscape, false); |
2432 break; |
2574 break; |
2433 } |
2575 } |
|
2576 case Op_PartialSubtypeCheck: |
|
2577 { // Produces Null or notNull and is used in CmpP. |
|
2578 add_node(n, PointsToNode::JavaObject, PointsToNode::ArgEscape, true); |
|
2579 break; |
|
2580 } |
2434 case Op_Phi: |
2581 case Op_Phi: |
2435 { |
2582 { |
2436 const Type *t = n->as_Phi()->type(); |
2583 const Type *t = n->as_Phi()->type(); |
2437 if (t->make_ptr() == NULL) { |
2584 if (t->make_ptr() == NULL) { |
2438 // nothing to do if not an oop or narrow oop |
2585 // nothing to do if not an oop or narrow oop |
2657 // For everything "adr_base" could point to, create a deferred edge from |
2805 // For everything "adr_base" could point to, create a deferred edge from |
2658 // this node to each field with the same offset. |
2806 // this node to each field with the same offset. |
2659 int offset = address_offset(adr, phase); |
2807 int offset = address_offset(adr, phase); |
2660 for( VectorSetI i(PointsTo(adr_base)); i.test(); ++i ) { |
2808 for( VectorSetI i(PointsTo(adr_base)); i.test(); ++i ) { |
2661 uint pt = i.elem; |
2809 uint pt = i.elem; |
|
2810 if (adr->is_AddP()) { |
|
2811 // Add field edge if it is missing. |
|
2812 add_field_edge(pt, adr->_idx, offset); |
|
2813 } |
2662 add_deferred_edge_to_fields(n_idx, pt, offset); |
2814 add_deferred_edge_to_fields(n_idx, pt, offset); |
2663 } |
2815 } |
2664 break; |
2816 break; |
2665 } |
2817 } |
2666 case Op_Parm: |
2818 case Op_Parm: |
2667 { |
2819 { |
2668 assert(false, "Op_Parm"); |
2820 assert(false, "Op_Parm"); |
|
2821 break; |
|
2822 } |
|
2823 case Op_PartialSubtypeCheck: |
|
2824 { |
|
2825 assert(false, "Op_PartialSubtypeCheck"); |
2669 break; |
2826 break; |
2670 } |
2827 } |
2671 case Op_Phi: |
2828 case Op_Phi: |
2672 { |
2829 { |
2673 #ifdef ASSERT |
2830 #ifdef ASSERT |
2743 #endif |
2900 #endif |
2744 |
2901 |
2745 assert(adr->is_AddP(), "expecting an AddP"); |
2902 assert(adr->is_AddP(), "expecting an AddP"); |
2746 Node *adr_base = get_addp_base(adr); |
2903 Node *adr_base = get_addp_base(adr); |
2747 Node *val = n->in(MemNode::ValueIn)->uncast(); |
2904 Node *val = n->in(MemNode::ValueIn)->uncast(); |
|
2905 int offset = address_offset(adr, phase); |
2748 // For everything "adr_base" could point to, create a deferred edge |
2906 // For everything "adr_base" could point to, create a deferred edge |
2749 // to "val" from each field with the same offset. |
2907 // to "val" from each field with the same offset. |
2750 for( VectorSetI i(PointsTo(adr_base)); i.test(); ++i ) { |
2908 for( VectorSetI i(PointsTo(adr_base)); i.test(); ++i ) { |
2751 uint pt = i.elem; |
2909 uint pt = i.elem; |
2752 add_edge_from_fields(pt, val->_idx, address_offset(adr, phase)); |
2910 // Add field edge if it is missing. |
|
2911 add_field_edge(pt, adr->_idx, offset); |
|
2912 add_edge_from_fields(pt, val->_idx, offset); |
2753 } |
2913 } |
2754 break; |
2914 break; |
2755 } |
2915 } |
2756 case Op_AryEq: |
2916 case Op_AryEq: |
2757 case Op_StrComp: |
2917 case Op_StrComp: |