src/hotspot/share/opto/loopopts.cpp
changeset 48145 f913f6dba2d3
parent 48135 feea6d82adc2
child 48309 1a0499fd252e
equal deleted inserted replaced
48144:364207a23251 48145:f913f6dba2d3
    24 
    24 
    25 #include "precompiled.hpp"
    25 #include "precompiled.hpp"
    26 #include "memory/allocation.inline.hpp"
    26 #include "memory/allocation.inline.hpp"
    27 #include "memory/resourceArea.hpp"
    27 #include "memory/resourceArea.hpp"
    28 #include "opto/addnode.hpp"
    28 #include "opto/addnode.hpp"
       
    29 #include "opto/callnode.hpp"
    29 #include "opto/castnode.hpp"
    30 #include "opto/castnode.hpp"
    30 #include "opto/connode.hpp"
    31 #include "opto/connode.hpp"
    31 #include "opto/castnode.hpp"
    32 #include "opto/castnode.hpp"
    32 #include "opto/divnode.hpp"
    33 #include "opto/divnode.hpp"
    33 #include "opto/loopnode.hpp"
    34 #include "opto/loopnode.hpp"
   304       // This allows us to split-up address expressions.
   305       // This allows us to split-up address expressions.
   305       if (m->is_AddP() &&
   306       if (m->is_AddP() &&
   306           get_ctrl(m->in(2)) != n_ctrl &&
   307           get_ctrl(m->in(2)) != n_ctrl &&
   307           get_ctrl(m->in(3)) != n_ctrl) {
   308           get_ctrl(m->in(3)) != n_ctrl) {
   308         // Move the AddP up to dominating point
   309         // Move the AddP up to dominating point
   309         set_ctrl_and_loop(m, find_non_split_ctrl(idom(n_ctrl)));
   310         Node* c = find_non_split_ctrl(idom(n_ctrl));
       
   311         if (c->is_OuterStripMinedLoop()) {
       
   312           c->as_Loop()->verify_strip_mined(1);
       
   313           c = c->in(LoopNode::EntryControl);
       
   314         }
       
   315         set_ctrl_and_loop(m, c);
   310         continue;
   316         continue;
   311       }
   317       }
   312       return NULL;
   318       return NULL;
   313     }
   319     }
   314     assert(m->is_Phi() || is_dominator(get_ctrl(m), n_ctrl), "m has strange control");
   320     assert(m->is_Phi() || is_dominator(get_ctrl(m), n_ctrl), "m has strange control");
   748         }
   754         }
   749       }
   755       }
   750       if (ctrl_ok) {
   756       if (ctrl_ok) {
   751         // move the Store
   757         // move the Store
   752         _igvn.replace_input_of(mem, LoopNode::LoopBackControl, mem);
   758         _igvn.replace_input_of(mem, LoopNode::LoopBackControl, mem);
   753         _igvn.replace_input_of(n, 0, n_loop->_head->in(LoopNode::EntryControl));
   759         _igvn.replace_input_of(n, 0, n_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl));
   754         _igvn.replace_input_of(n, MemNode::Memory, mem->in(LoopNode::EntryControl));
   760         _igvn.replace_input_of(n, MemNode::Memory, mem->in(LoopNode::EntryControl));
   755         // Disconnect the phi now. An empty phi can confuse other
   761         // Disconnect the phi now. An empty phi can confuse other
   756         // optimizations in this pass of loop opts.
   762         // optimizations in this pass of loop opts.
   757         _igvn.replace_node(mem, mem->in(LoopNode::EntryControl));
   763         _igvn.replace_node(mem, mem->in(LoopNode::EntryControl));
   758         n_loop->_body.yank(mem);
   764         n_loop->_body.yank(mem);
   759 
   765 
   760         IdealLoopTree* new_loop = get_loop(n->in(0));
       
   761         set_ctrl_and_loop(n, n->in(0));
   766         set_ctrl_and_loop(n, n->in(0));
   762 
   767 
   763         return n;
   768         return n;
   764       }
   769       }
   765     }
   770     }
   838             if (n_loop->is_member(get_loop(lca))) {
   843             if (n_loop->is_member(get_loop(lca))) {
   839               // LCA is in the loop - bail out
   844               // LCA is in the loop - bail out
   840               _igvn.replace_node(hook, n);
   845               _igvn.replace_node(hook, n);
   841               return;
   846               return;
   842             }
   847             }
       
   848 #ifdef ASSERT
       
   849             if (n_loop->_head->is_Loop() && n_loop->_head->as_Loop()->is_strip_mined()) {
       
   850               assert(n_loop->_head->Opcode() == Op_CountedLoop, "outer loop is a strip mined");
       
   851               n_loop->_head->as_Loop()->verify_strip_mined(1);
       
   852               Node* outer = n_loop->_head->as_CountedLoop()->outer_loop();
       
   853               IdealLoopTree* outer_loop = get_loop(outer);
       
   854               assert(n_loop->_parent == outer_loop, "broken loop tree");
       
   855               assert(get_loop(lca) == outer_loop, "safepoint in outer loop consume all memory state");
       
   856             }
       
   857 #endif
   843 
   858 
   844             // Move store out of the loop
   859             // Move store out of the loop
   845             _igvn.replace_node(hook, n->in(MemNode::Memory));
   860             _igvn.replace_node(hook, n->in(MemNode::Memory));
   846             _igvn.replace_input_of(n, 0, lca);
   861             _igvn.replace_input_of(n, 0, lca);
   847             set_ctrl_and_loop(n, lca);
   862             set_ctrl_and_loop(n, lca);
  1014 // For inner loop uses move it to the preheader area.
  1029 // For inner loop uses move it to the preheader area.
  1015 Node *PhaseIdealLoop::place_near_use( Node *useblock ) const {
  1030 Node *PhaseIdealLoop::place_near_use( Node *useblock ) const {
  1016   IdealLoopTree *u_loop = get_loop( useblock );
  1031   IdealLoopTree *u_loop = get_loop( useblock );
  1017   return (u_loop->_irreducible || u_loop->_child)
  1032   return (u_loop->_irreducible || u_loop->_child)
  1018     ? useblock
  1033     ? useblock
  1019     : u_loop->_head->in(LoopNode::EntryControl);
  1034     : u_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
  1020 }
  1035 }
  1021 
  1036 
  1022 
  1037 
  1023 bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) {
  1038 bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) {
  1024   if (!n->is_If()) {
  1039   if (!n->is_If()) {
  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
  1595 //      pre-main-post loop sequence.
  1856 //      pre-main-post loop sequence.
  1596 //   When nonnull, the clone and original are side-by-side, both are
  1857 //   When nonnull, the clone and original are side-by-side, both are
  1597 //      dominated by the side_by_side_idom node.  Used in construction of
  1858 //      dominated by the side_by_side_idom node.  Used in construction of
  1598 //      unswitched loops.
  1859 //      unswitched loops.
  1599 void PhaseIdealLoop::clone_loop( IdealLoopTree *loop, Node_List &old_new, int dd,
  1860 void PhaseIdealLoop::clone_loop( IdealLoopTree *loop, Node_List &old_new, int dd,
  1600                                  Node* side_by_side_idom) {
  1861                                 CloneLoopMode mode, Node* side_by_side_idom) {
       
  1862 
       
  1863   LoopNode* head = loop->_head->as_Loop();
       
  1864   head->verify_strip_mined(1);
  1601 
  1865 
  1602   if (C->do_vector_loop() && PrintOpto) {
  1866   if (C->do_vector_loop() && PrintOpto) {
  1603     const char* mname = C->method()->name()->as_quoted_ascii();
  1867     const char* mname = C->method()->name()->as_quoted_ascii();
  1604     if (mname != NULL) {
  1868     if (mname != NULL) {
  1605       tty->print("PhaseIdealLoop::clone_loop: for vectorize method %s\n", mname);
  1869       tty->print("PhaseIdealLoop::clone_loop: for vectorize method %s\n", mname);
  1628       cm.verify_insert_and_clone(old, nnn, cm.clone_idx());
  1892       cm.verify_insert_and_clone(old, nnn, cm.clone_idx());
  1629     }
  1893     }
  1630     _igvn.register_new_node_with_optimizer(nnn);
  1894     _igvn.register_new_node_with_optimizer(nnn);
  1631   }
  1895   }
  1632 
  1896 
       
  1897   IdealLoopTree* outer_loop = (head->is_strip_mined() && mode != IgnoreStripMined) ? get_loop(head->as_CountedLoop()->outer_loop()) : loop;
  1633 
  1898 
  1634   // Step 2: Fix the edges in the new body.  If the old input is outside the
  1899   // Step 2: Fix the edges in the new body.  If the old input is outside the
  1635   // loop use it.  If the old input is INside the loop, use the corresponding
  1900   // loop use it.  If the old input is INside the loop, use the corresponding
  1636   // new node instead.
  1901   // new node instead.
  1637   for( i = 0; i < loop->_body.size(); i++ ) {
  1902   for( i = 0; i < loop->_body.size(); i++ ) {
  1639     Node *nnn = old_new[old->_idx];
  1904     Node *nnn = old_new[old->_idx];
  1640     // Fix CFG/Loop controlling the new node
  1905     // Fix CFG/Loop controlling the new node
  1641     if (has_ctrl(old)) {
  1906     if (has_ctrl(old)) {
  1642       set_ctrl(nnn, old_new[get_ctrl(old)->_idx]);
  1907       set_ctrl(nnn, old_new[get_ctrl(old)->_idx]);
  1643     } else {
  1908     } else {
  1644       set_loop(nnn, loop->_parent);
  1909       set_loop(nnn, outer_loop->_parent);
  1645       if (old->outcnt() > 0) {
  1910       if (old->outcnt() > 0) {
  1646         set_idom( nnn, old_new[idom(old)->_idx], dd );
  1911         set_idom( nnn, old_new[idom(old)->_idx], dd );
  1647       }
  1912       }
  1648     }
  1913     }
  1649     // Correct edges to the new node
  1914     // Correct edges to the new node
  1655             nnn->set_req(j, old_new[n->_idx]);
  1920             nnn->set_req(j, old_new[n->_idx]);
  1656         }
  1921         }
  1657     }
  1922     }
  1658     _igvn.hash_find_insert(nnn);
  1923     _igvn.hash_find_insert(nnn);
  1659   }
  1924   }
  1660   Node *newhead = old_new[loop->_head->_idx];
  1925 
  1661   set_idom(newhead, newhead->in(LoopNode::EntryControl), dd);
  1926   ResourceArea *area = Thread::current()->resource_area();
  1662 
  1927   Node_List extra_data_nodes(area);
       
  1928   clone_outer_loop(head, mode, loop, outer_loop, dd, old_new, extra_data_nodes);
  1663 
  1929 
  1664   // Step 3: Now fix control uses.  Loop varying control uses have already
  1930   // Step 3: Now fix control uses.  Loop varying control uses have already
  1665   // been fixed up (as part of all input edges in Step 2).  Loop invariant
  1931   // been fixed up (as part of all input edges in Step 2).  Loop invariant
  1666   // control uses must be either an IfFalse or an IfTrue.  Make a merge
  1932   // control uses must be either an IfFalse or an IfTrue.  Make a merge
  1667   // point to merge the old and new IfFalse/IfTrue nodes; make the use
  1933   // point to merge the old and new IfFalse/IfTrue nodes; make the use
  1668   // refer to this.
  1934   // refer to this.
  1669   ResourceArea *area = Thread::current()->resource_area();
       
  1670   Node_List worklist(area);
  1935   Node_List worklist(area);
  1671   uint new_counter = C->unique();
  1936   uint new_counter = C->unique();
  1672   for( i = 0; i < loop->_body.size(); i++ ) {
  1937   for( i = 0; i < loop->_body.size(); i++ ) {
  1673     Node* old = loop->_body.at(i);
  1938     Node* old = loop->_body.at(i);
  1674     if( !old->is_CFG() ) continue;
  1939     if( !old->is_CFG() ) continue;
  1675     Node* nnn = old_new[old->_idx];
       
  1676 
  1940 
  1677     // Copy uses to a worklist, so I can munge the def-use info
  1941     // Copy uses to a worklist, so I can munge the def-use info
  1678     // with impunity.
  1942     // with impunity.
  1679     for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
  1943     for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
  1680       worklist.push(old->fast_out(j));
  1944       worklist.push(old->fast_out(j));
  1684       if (!has_node(use))  continue; // Ignore dead nodes
  1948       if (!has_node(use))  continue; // Ignore dead nodes
  1685       IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
  1949       IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
  1686       if( !loop->is_member( use_loop ) && use->is_CFG() ) {
  1950       if( !loop->is_member( use_loop ) && use->is_CFG() ) {
  1687         // Both OLD and USE are CFG nodes here.
  1951         // Both OLD and USE are CFG nodes here.
  1688         assert( use->is_Proj(), "" );
  1952         assert( use->is_Proj(), "" );
       
  1953         Node* nnn = old_new[old->_idx];
       
  1954 
       
  1955         Node* newuse = NULL;
       
  1956         if (head->is_strip_mined() && mode != IgnoreStripMined) {
       
  1957           CountedLoopNode* cl = head->as_CountedLoop();
       
  1958           CountedLoopEndNode* cle = cl->loopexit();
       
  1959           Node* cle_out = cle->proj_out(false);
       
  1960           if (use == cle_out) {
       
  1961             IfNode* le = cl->outer_loop_end();
       
  1962             use = le->proj_out(false);
       
  1963             use_loop = get_loop(use);
       
  1964             if (mode == CloneIncludesStripMined) {
       
  1965               nnn = old_new[le->_idx];
       
  1966             } else {
       
  1967               newuse = old_new[cle_out->_idx];
       
  1968             }
       
  1969           }
       
  1970         }
       
  1971         if (newuse == NULL) {
       
  1972           newuse = use->clone();
       
  1973         }
  1689 
  1974 
  1690         // Clone the loop exit control projection
  1975         // Clone the loop exit control projection
  1691         Node *newuse = use->clone();
       
  1692         if (C->do_vector_loop()) {
  1976         if (C->do_vector_loop()) {
  1693           cm.verify_insert_and_clone(use, newuse, cm.clone_idx());
  1977           cm.verify_insert_and_clone(use, newuse, cm.clone_idx());
  1694         }
  1978         }
  1695         newuse->set_req(0,nnn);
  1979         newuse->set_req(0,nnn);
  1696         _igvn.register_new_node_with_optimizer(newuse);
  1980         _igvn.register_new_node_with_optimizer(newuse);
  1720           }
  2004           }
  1721           for( uint k = 1; k < useuse->req(); k++ ) {
  2005           for( uint k = 1; k < useuse->req(); k++ ) {
  1722             if( useuse->in(k) == use ) {
  2006             if( useuse->in(k) == use ) {
  1723               useuse->set_req(k, r);
  2007               useuse->set_req(k, r);
  1724               uses_found++;
  2008               uses_found++;
       
  2009               if (useuse->is_Loop() && k == LoopNode::EntryControl) {
       
  2010                 assert(dom_depth(useuse) > dd_r , "");
       
  2011                 set_idom(useuse, r, dom_depth(useuse));
       
  2012               }
  1725             }
  2013             }
  1726           }
  2014           }
  1727           l -= uses_found;    // we deleted 1 or more copies of this edge
  2015           l -= uses_found;    // we deleted 1 or more copies of this edge
  1728         }
  2016         }
  1729 
  2017 
  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
  2954     set_ctrl(n, new_head);
  3132     set_ctrl(n, new_head);
  2955   }
  3133   }
  2956 
  3134 
  2957   assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
  3135   assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
  2958 
  3136 
  2959   clone_loop( loop, old_new, dd );
  3137   clone_loop(loop, old_new, dd, IgnoreStripMined);
  2960 
  3138 
  2961   const uint clone_exit_idx = 1;
  3139   const uint clone_exit_idx = 1;
  2962   const uint orig_exit_idx  = 2;
  3140   const uint orig_exit_idx  = 2;
  2963   assert(is_valid_clone_loop_form( loop, peel_list, orig_exit_idx, clone_exit_idx ), "bad clone loop");
  3141   assert(is_valid_clone_loop_form( loop, peel_list, orig_exit_idx, clone_exit_idx ), "bad clone loop");
  2964 
  3142