1567 for (DUIterator j = use->outs(); use->has_out(j); j++) |
1582 for (DUIterator j = use->outs(); use->has_out(j); j++) |
1568 sink_use(use->out(j), post_loop); |
1583 sink_use(use->out(j), post_loop); |
1569 } |
1584 } |
1570 } |
1585 } |
1571 |
1586 |
|
1587 void PhaseIdealLoop::clone_loop_handle_data_uses(Node* old, Node_List &old_new, |
|
1588 IdealLoopTree* loop, IdealLoopTree* outer_loop, |
|
1589 Node_List*& split_if_set, Node_List*& split_bool_set, |
|
1590 Node_List*& split_cex_set, Node_List& worklist, |
|
1591 uint new_counter, CloneLoopMode mode) { |
|
1592 Node* nnn = old_new[old->_idx]; |
|
1593 // Copy uses to a worklist, so I can munge the def-use info |
|
1594 // with impunity. |
|
1595 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++) |
|
1596 worklist.push(old->fast_out(j)); |
|
1597 |
|
1598 while( worklist.size() ) { |
|
1599 Node *use = worklist.pop(); |
|
1600 if (!has_node(use)) continue; // Ignore dead nodes |
|
1601 if (use->in(0) == C->top()) continue; |
|
1602 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use ); |
|
1603 // Check for data-use outside of loop - at least one of OLD or USE |
|
1604 // must not be a CFG node. |
|
1605 #ifdef ASSERT |
|
1606 if (loop->_head->as_Loop()->is_strip_mined() && outer_loop->is_member(use_loop) && !loop->is_member(use_loop) && old_new[use->_idx] == NULL) { |
|
1607 Node* sfpt = loop->_head->as_CountedLoop()->outer_safepoint(); |
|
1608 assert(mode == ControlAroundStripMined && use == sfpt, "missed a node"); |
|
1609 } |
|
1610 #endif |
|
1611 if (!loop->is_member(use_loop) && !outer_loop->is_member(use_loop) && (!old->is_CFG() || !use->is_CFG())) { |
|
1612 |
|
1613 // If the Data use is an IF, that means we have an IF outside of the |
|
1614 // loop that is switching on a condition that is set inside of the |
|
1615 // loop. Happens if people set a loop-exit flag; then test the flag |
|
1616 // in the loop to break the loop, then test is again outside of the |
|
1617 // loop to determine which way the loop exited. |
|
1618 // Loop predicate If node connects to Bool node through Opaque1 node. |
|
1619 if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use) || use->Opcode() == Op_Opaque4) { |
|
1620 // Since this code is highly unlikely, we lazily build the worklist |
|
1621 // of such Nodes to go split. |
|
1622 if (!split_if_set) { |
|
1623 ResourceArea *area = Thread::current()->resource_area(); |
|
1624 split_if_set = new Node_List(area); |
|
1625 } |
|
1626 split_if_set->push(use); |
|
1627 } |
|
1628 if (use->is_Bool()) { |
|
1629 if (!split_bool_set) { |
|
1630 ResourceArea *area = Thread::current()->resource_area(); |
|
1631 split_bool_set = new Node_List(area); |
|
1632 } |
|
1633 split_bool_set->push(use); |
|
1634 } |
|
1635 if (use->Opcode() == Op_CreateEx) { |
|
1636 if (!split_cex_set) { |
|
1637 ResourceArea *area = Thread::current()->resource_area(); |
|
1638 split_cex_set = new Node_List(area); |
|
1639 } |
|
1640 split_cex_set->push(use); |
|
1641 } |
|
1642 |
|
1643 |
|
1644 // Get "block" use is in |
|
1645 uint idx = 0; |
|
1646 while( use->in(idx) != old ) idx++; |
|
1647 Node *prev = use->is_CFG() ? use : get_ctrl(use); |
|
1648 assert(!loop->is_member(get_loop(prev)) && !outer_loop->is_member(get_loop(prev)), "" ); |
|
1649 Node *cfg = prev->_idx >= new_counter |
|
1650 ? prev->in(2) |
|
1651 : idom(prev); |
|
1652 if( use->is_Phi() ) // Phi use is in prior block |
|
1653 cfg = prev->in(idx); // NOT in block of Phi itself |
|
1654 if (cfg->is_top()) { // Use is dead? |
|
1655 _igvn.replace_input_of(use, idx, C->top()); |
|
1656 continue; |
|
1657 } |
|
1658 |
|
1659 while(!outer_loop->is_member(get_loop(cfg))) { |
|
1660 prev = cfg; |
|
1661 cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg); |
|
1662 } |
|
1663 // If the use occurs after merging several exits from the loop, then |
|
1664 // old value must have dominated all those exits. Since the same old |
|
1665 // value was used on all those exits we did not need a Phi at this |
|
1666 // merge point. NOW we do need a Phi here. Each loop exit value |
|
1667 // is now merged with the peeled body exit; each exit gets its own |
|
1668 // private Phi and those Phis need to be merged here. |
|
1669 Node *phi; |
|
1670 if( prev->is_Region() ) { |
|
1671 if( idx == 0 ) { // Updating control edge? |
|
1672 phi = prev; // Just use existing control |
|
1673 } else { // Else need a new Phi |
|
1674 phi = PhiNode::make( prev, old ); |
|
1675 // Now recursively fix up the new uses of old! |
|
1676 for( uint i = 1; i < prev->req(); i++ ) { |
|
1677 worklist.push(phi); // Onto worklist once for each 'old' input |
|
1678 } |
|
1679 } |
|
1680 } else { |
|
1681 // Get new RegionNode merging old and new loop exits |
|
1682 prev = old_new[prev->_idx]; |
|
1683 assert( prev, "just made this in step 7" ); |
|
1684 if( idx == 0) { // Updating control edge? |
|
1685 phi = prev; // Just use existing control |
|
1686 } else { // Else need a new Phi |
|
1687 // Make a new Phi merging data values properly |
|
1688 phi = PhiNode::make( prev, old ); |
|
1689 phi->set_req( 1, nnn ); |
|
1690 } |
|
1691 } |
|
1692 // If inserting a new Phi, check for prior hits |
|
1693 if( idx != 0 ) { |
|
1694 Node *hit = _igvn.hash_find_insert(phi); |
|
1695 if( hit == NULL ) { |
|
1696 _igvn.register_new_node_with_optimizer(phi); // Register new phi |
|
1697 } else { // or |
|
1698 // Remove the new phi from the graph and use the hit |
|
1699 _igvn.remove_dead_node(phi); |
|
1700 phi = hit; // Use existing phi |
|
1701 } |
|
1702 set_ctrl(phi, prev); |
|
1703 } |
|
1704 // Make 'use' use the Phi instead of the old loop body exit value |
|
1705 _igvn.replace_input_of(use, idx, phi); |
|
1706 if( use->_idx >= new_counter ) { // If updating new phis |
|
1707 // Not needed for correctness, but prevents a weak assert |
|
1708 // in AddPNode from tripping (when we end up with different |
|
1709 // base & derived Phis that will become the same after |
|
1710 // IGVN does CSE). |
|
1711 Node *hit = _igvn.hash_find_insert(use); |
|
1712 if( hit ) // Go ahead and re-hash for hits. |
|
1713 _igvn.replace_node( use, hit ); |
|
1714 } |
|
1715 |
|
1716 // If 'use' was in the loop-exit block, it now needs to be sunk |
|
1717 // below the post-loop merge point. |
|
1718 sink_use( use, prev ); |
|
1719 } |
|
1720 } |
|
1721 } |
|
1722 |
|
1723 void PhaseIdealLoop::clone_outer_loop(LoopNode* head, CloneLoopMode mode, IdealLoopTree *loop, |
|
1724 IdealLoopTree* outer_loop, int dd, Node_List &old_new, |
|
1725 Node_List& extra_data_nodes) { |
|
1726 if (head->is_strip_mined() && mode != IgnoreStripMined) { |
|
1727 CountedLoopNode* cl = head->as_CountedLoop(); |
|
1728 Node* l = cl->outer_loop(); |
|
1729 Node* tail = cl->outer_loop_tail(); |
|
1730 IfNode* le = cl->outer_loop_end(); |
|
1731 Node* sfpt = cl->outer_safepoint(); |
|
1732 CountedLoopEndNode* cle = cl->loopexit(); |
|
1733 CountedLoopNode* new_cl = old_new[cl->_idx]->as_CountedLoop(); |
|
1734 CountedLoopEndNode* new_cle = new_cl->as_CountedLoop()->loopexit(); |
|
1735 Node* cle_out = cle->proj_out(false); |
|
1736 |
|
1737 Node* new_sfpt = NULL; |
|
1738 Node* new_cle_out = cle_out->clone(); |
|
1739 old_new.map(cle_out->_idx, new_cle_out); |
|
1740 if (mode == CloneIncludesStripMined) { |
|
1741 // clone outer loop body |
|
1742 Node* new_l = l->clone(); |
|
1743 Node* new_tail = tail->clone(); |
|
1744 IfNode* new_le = le->clone()->as_If(); |
|
1745 new_sfpt = sfpt->clone(); |
|
1746 |
|
1747 set_loop(new_l, outer_loop->_parent); |
|
1748 set_idom(new_l, new_l->in(LoopNode::EntryControl), dd); |
|
1749 set_loop(new_cle_out, outer_loop->_parent); |
|
1750 set_idom(new_cle_out, new_cle, dd); |
|
1751 set_loop(new_sfpt, outer_loop->_parent); |
|
1752 set_idom(new_sfpt, new_cle_out, dd); |
|
1753 set_loop(new_le, outer_loop->_parent); |
|
1754 set_idom(new_le, new_sfpt, dd); |
|
1755 set_loop(new_tail, outer_loop->_parent); |
|
1756 set_idom(new_tail, new_le, dd); |
|
1757 set_idom(new_cl, new_l, dd); |
|
1758 |
|
1759 old_new.map(l->_idx, new_l); |
|
1760 old_new.map(tail->_idx, new_tail); |
|
1761 old_new.map(le->_idx, new_le); |
|
1762 old_new.map(sfpt->_idx, new_sfpt); |
|
1763 |
|
1764 new_l->set_req(LoopNode::LoopBackControl, new_tail); |
|
1765 new_l->set_req(0, new_l); |
|
1766 new_tail->set_req(0, new_le); |
|
1767 new_le->set_req(0, new_sfpt); |
|
1768 new_sfpt->set_req(0, new_cle_out); |
|
1769 new_cle_out->set_req(0, new_cle); |
|
1770 new_cl->set_req(LoopNode::EntryControl, new_l); |
|
1771 |
|
1772 _igvn.register_new_node_with_optimizer(new_l); |
|
1773 _igvn.register_new_node_with_optimizer(new_tail); |
|
1774 _igvn.register_new_node_with_optimizer(new_le); |
|
1775 } else { |
|
1776 Node *newhead = old_new[loop->_head->_idx]; |
|
1777 newhead->as_Loop()->clear_strip_mined(); |
|
1778 _igvn.replace_input_of(newhead, LoopNode::EntryControl, newhead->in(LoopNode::EntryControl)->in(LoopNode::EntryControl)); |
|
1779 set_idom(newhead, newhead->in(LoopNode::EntryControl), dd); |
|
1780 } |
|
1781 // Look at data node that were assigned a control in the outer |
|
1782 // loop: they are kept in the outer loop by the safepoint so start |
|
1783 // from the safepoint node's inputs. |
|
1784 IdealLoopTree* outer_loop = get_loop(l); |
|
1785 Node_Stack stack(2); |
|
1786 stack.push(sfpt, 1); |
|
1787 uint new_counter = C->unique(); |
|
1788 while (stack.size() > 0) { |
|
1789 Node* n = stack.node(); |
|
1790 uint i = stack.index(); |
|
1791 while (i < n->req() && |
|
1792 (n->in(i) == NULL || |
|
1793 !has_ctrl(n->in(i)) || |
|
1794 get_loop(get_ctrl(n->in(i))) != outer_loop || |
|
1795 (old_new[n->in(i)->_idx] != NULL && old_new[n->in(i)->_idx]->_idx >= new_counter))) { |
|
1796 i++; |
|
1797 } |
|
1798 if (i < n->req()) { |
|
1799 stack.set_index(i+1); |
|
1800 stack.push(n->in(i), 0); |
|
1801 } else { |
|
1802 assert(old_new[n->_idx] == NULL || n == sfpt || old_new[n->_idx]->_idx < new_counter, "no clone yet"); |
|
1803 Node* m = n == sfpt ? new_sfpt : n->clone(); |
|
1804 if (m != NULL) { |
|
1805 for (uint i = 0; i < n->req(); i++) { |
|
1806 if (m->in(i) != NULL && old_new[m->in(i)->_idx] != NULL) { |
|
1807 m->set_req(i, old_new[m->in(i)->_idx]); |
|
1808 } |
|
1809 } |
|
1810 } else { |
|
1811 assert(n == sfpt && mode != CloneIncludesStripMined, "where's the safepoint clone?"); |
|
1812 } |
|
1813 if (n != sfpt) { |
|
1814 extra_data_nodes.push(n); |
|
1815 _igvn.register_new_node_with_optimizer(m); |
|
1816 assert(get_ctrl(n) == cle_out, "what other control?"); |
|
1817 set_ctrl(m, new_cle_out); |
|
1818 old_new.map(n->_idx, m); |
|
1819 } |
|
1820 stack.pop(); |
|
1821 } |
|
1822 } |
|
1823 if (mode == CloneIncludesStripMined) { |
|
1824 _igvn.register_new_node_with_optimizer(new_sfpt); |
|
1825 _igvn.register_new_node_with_optimizer(new_cle_out); |
|
1826 } |
|
1827 } else { |
|
1828 Node *newhead = old_new[loop->_head->_idx]; |
|
1829 set_idom(newhead, newhead->in(LoopNode::EntryControl), dd); |
|
1830 } |
|
1831 } |
|
1832 |
1572 //------------------------------clone_loop------------------------------------- |
1833 //------------------------------clone_loop------------------------------------- |
1573 // |
1834 // |
1574 // C L O N E A L O O P B O D Y |
1835 // C L O N E A L O O P B O D Y |
1575 // |
1836 // |
1576 // This is the basic building block of the loop optimizations. It clones an |
1837 // This is the basic building block of the loop optimizations. It clones an |
1743 Node_List *split_if_set = NULL; |
2031 Node_List *split_if_set = NULL; |
1744 Node_List *split_bool_set = NULL; |
2032 Node_List *split_bool_set = NULL; |
1745 Node_List *split_cex_set = NULL; |
2033 Node_List *split_cex_set = NULL; |
1746 for( i = 0; i < loop->_body.size(); i++ ) { |
2034 for( i = 0; i < loop->_body.size(); i++ ) { |
1747 Node* old = loop->_body.at(i); |
2035 Node* old = loop->_body.at(i); |
1748 Node* nnn = old_new[old->_idx]; |
2036 clone_loop_handle_data_uses(old, old_new, loop, outer_loop, split_if_set, |
1749 // Copy uses to a worklist, so I can munge the def-use info |
2037 split_bool_set, split_cex_set, worklist, new_counter, |
1750 // with impunity. |
2038 mode); |
1751 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++) |
2039 } |
1752 worklist.push(old->fast_out(j)); |
2040 |
1753 |
2041 for (i = 0; i < extra_data_nodes.size(); i++) { |
1754 while( worklist.size() ) { |
2042 Node* old = extra_data_nodes.at(i); |
1755 Node *use = worklist.pop(); |
2043 clone_loop_handle_data_uses(old, old_new, loop, outer_loop, split_if_set, |
1756 if (!has_node(use)) continue; // Ignore dead nodes |
2044 split_bool_set, split_cex_set, worklist, new_counter, |
1757 if (use->in(0) == C->top()) continue; |
2045 mode); |
1758 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use ); |
|
1759 // Check for data-use outside of loop - at least one of OLD or USE |
|
1760 // must not be a CFG node. |
|
1761 if( !loop->is_member( use_loop ) && (!old->is_CFG() || !use->is_CFG())) { |
|
1762 |
|
1763 // If the Data use is an IF, that means we have an IF outside of the |
|
1764 // loop that is switching on a condition that is set inside of the |
|
1765 // loop. Happens if people set a loop-exit flag; then test the flag |
|
1766 // in the loop to break the loop, then test is again outside of the |
|
1767 // loop to determine which way the loop exited. |
|
1768 // Loop predicate If node connects to Bool node through Opaque1 node. |
|
1769 if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use) || use->Opcode() == Op_Opaque4) { |
|
1770 // Since this code is highly unlikely, we lazily build the worklist |
|
1771 // of such Nodes to go split. |
|
1772 if (!split_if_set) { |
|
1773 split_if_set = new Node_List(area); |
|
1774 } |
|
1775 split_if_set->push(use); |
|
1776 } |
|
1777 if (use->is_Bool()) { |
|
1778 if (!split_bool_set) { |
|
1779 split_bool_set = new Node_List(area); |
|
1780 } |
|
1781 split_bool_set->push(use); |
|
1782 } |
|
1783 if (use->Opcode() == Op_CreateEx) { |
|
1784 if (!split_cex_set) { |
|
1785 split_cex_set = new Node_List(area); |
|
1786 } |
|
1787 split_cex_set->push(use); |
|
1788 } |
|
1789 |
|
1790 |
|
1791 // Get "block" use is in |
|
1792 uint idx = 0; |
|
1793 while( use->in(idx) != old ) idx++; |
|
1794 Node *prev = use->is_CFG() ? use : get_ctrl(use); |
|
1795 assert( !loop->is_member( get_loop( prev ) ), "" ); |
|
1796 Node *cfg = prev->_idx >= new_counter |
|
1797 ? prev->in(2) |
|
1798 : idom(prev); |
|
1799 if( use->is_Phi() ) // Phi use is in prior block |
|
1800 cfg = prev->in(idx); // NOT in block of Phi itself |
|
1801 if (cfg->is_top()) { // Use is dead? |
|
1802 _igvn.replace_input_of(use, idx, C->top()); |
|
1803 continue; |
|
1804 } |
|
1805 |
|
1806 while( !loop->is_member( get_loop( cfg ) ) ) { |
|
1807 prev = cfg; |
|
1808 cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg); |
|
1809 } |
|
1810 // If the use occurs after merging several exits from the loop, then |
|
1811 // old value must have dominated all those exits. Since the same old |
|
1812 // value was used on all those exits we did not need a Phi at this |
|
1813 // merge point. NOW we do need a Phi here. Each loop exit value |
|
1814 // is now merged with the peeled body exit; each exit gets its own |
|
1815 // private Phi and those Phis need to be merged here. |
|
1816 Node *phi; |
|
1817 if( prev->is_Region() ) { |
|
1818 if( idx == 0 ) { // Updating control edge? |
|
1819 phi = prev; // Just use existing control |
|
1820 } else { // Else need a new Phi |
|
1821 phi = PhiNode::make( prev, old ); |
|
1822 // Now recursively fix up the new uses of old! |
|
1823 for( uint i = 1; i < prev->req(); i++ ) { |
|
1824 worklist.push(phi); // Onto worklist once for each 'old' input |
|
1825 } |
|
1826 } |
|
1827 } else { |
|
1828 // Get new RegionNode merging old and new loop exits |
|
1829 prev = old_new[prev->_idx]; |
|
1830 assert( prev, "just made this in step 7" ); |
|
1831 if( idx == 0 ) { // Updating control edge? |
|
1832 phi = prev; // Just use existing control |
|
1833 } else { // Else need a new Phi |
|
1834 // Make a new Phi merging data values properly |
|
1835 phi = PhiNode::make( prev, old ); |
|
1836 phi->set_req( 1, nnn ); |
|
1837 } |
|
1838 } |
|
1839 // If inserting a new Phi, check for prior hits |
|
1840 if( idx != 0 ) { |
|
1841 Node *hit = _igvn.hash_find_insert(phi); |
|
1842 if( hit == NULL ) { |
|
1843 _igvn.register_new_node_with_optimizer(phi); // Register new phi |
|
1844 } else { // or |
|
1845 // Remove the new phi from the graph and use the hit |
|
1846 _igvn.remove_dead_node(phi); |
|
1847 phi = hit; // Use existing phi |
|
1848 } |
|
1849 set_ctrl(phi, prev); |
|
1850 } |
|
1851 // Make 'use' use the Phi instead of the old loop body exit value |
|
1852 _igvn.replace_input_of(use, idx, phi); |
|
1853 if( use->_idx >= new_counter ) { // If updating new phis |
|
1854 // Not needed for correctness, but prevents a weak assert |
|
1855 // in AddPNode from tripping (when we end up with different |
|
1856 // base & derived Phis that will become the same after |
|
1857 // IGVN does CSE). |
|
1858 Node *hit = _igvn.hash_find_insert(use); |
|
1859 if( hit ) // Go ahead and re-hash for hits. |
|
1860 _igvn.replace_node( use, hit ); |
|
1861 } |
|
1862 |
|
1863 // If 'use' was in the loop-exit block, it now needs to be sunk |
|
1864 // below the post-loop merge point. |
|
1865 sink_use( use, prev ); |
|
1866 } |
|
1867 } |
|
1868 } |
2046 } |
1869 |
2047 |
1870 // Check for IFs that need splitting/cloning. Happens if an IF outside of |
2048 // Check for IFs that need splitting/cloning. Happens if an IF outside of |
1871 // the loop uses a condition set in the loop. The original IF probably |
2049 // the loop uses a condition set in the loop. The original IF probably |
1872 // takes control from one or more OLD Regions (which in turn get from NEW |
2050 // takes control from one or more OLD Regions (which in turn get from NEW |