1390 // Get saved parent node and next use's index. Visit the rest of uses.
1391 n = nstack.node();
1392 cnt = n->outcnt();
1393 i = nstack.index();
1394 nstack.pop();
1395 }
1396 }
1397 }
1398
1399
1400 //=============================================================================
1401 //
1402 // C L O N E A L O O P B O D Y
1403 //
1404
1405 //------------------------------clone_iff--------------------------------------
1406 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1407 // "Nearly" because all Nodes have been cloned from the original in the loop,
1408 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1409 // through the Phi recursively, and return a Bool.
1410 BoolNode *PhaseIdealLoop::clone_iff( PhiNode *phi, IdealLoopTree *loop ) {
1411
1412 // Convert this Phi into a Phi merging Bools
1413 uint i;
1414 for( i = 1; i < phi->req(); i++ ) {
1415 Node *b = phi->in(i);
1416 if( b->is_Phi() ) {
1417 _igvn.replace_input_of(phi, i, clone_iff( b->as_Phi(), loop ));
1418 } else {
1419 assert( b->is_Bool(), "" );
1420 }
1421 }
1422
1423 Node *sample_bool = phi->in(1);
1424 Node *sample_cmp = sample_bool->in(1);
1425
1426 // Make Phis to merge the Cmp's inputs.
1427 PhiNode *phi1 = new PhiNode( phi->in(0), Type::TOP );
1428 PhiNode *phi2 = new PhiNode( phi->in(0), Type::TOP );
1429 for( i = 1; i < phi->req(); i++ ) {
1430 Node *n1 = phi->in(i)->in(1)->in(1);
1431 Node *n2 = phi->in(i)->in(1)->in(2);
1432 phi1->set_req( i, n1 );
1433 phi2->set_req( i, n2 );
1434 phi1->set_type( phi1->type()->meet_speculative(n1->bottom_type()));
1435 phi2->set_type( phi2->type()->meet_speculative(n2->bottom_type()));
1436 }
1437 // See if these Phis have been made before.
1438 // Register with optimizer
1439 Node *hit1 = _igvn.hash_find_insert(phi1);
1440 if( hit1 ) { // Hit, toss just made Phi
1441 _igvn.remove_dead_node(phi1); // Remove new phi
1442 assert( hit1->is_Phi(), "" );
1443 phi1 = (PhiNode*)hit1; // Use existing phi
1444 } else { // Miss
1445 _igvn.register_new_node_with_optimizer(phi1);
1446 }
1447 Node *hit2 = _igvn.hash_find_insert(phi2);
1448 if( hit2 ) { // Hit, toss just made Phi
1449 _igvn.remove_dead_node(phi2); // Remove new phi
1450 assert( hit2->is_Phi(), "" );
1451 phi2 = (PhiNode*)hit2; // Use existing phi
1452 } else { // Miss
1453 _igvn.register_new_node_with_optimizer(phi2);
1454 }
1455 // Register Phis with loop/block info
1456 set_ctrl(phi1, phi->in(0));
1457 set_ctrl(phi2, phi->in(0));
1458 // Make a new Cmp
1459 Node *cmp = sample_cmp->clone();
1460 cmp->set_req( 1, phi1 );
1461 cmp->set_req( 2, phi2 );
1462 _igvn.register_new_node_with_optimizer(cmp);
1463 set_ctrl(cmp, phi->in(0));
1464
1465 // Make a new Bool
1466 Node *b = sample_bool->clone();
1467 b->set_req(1,cmp);
1468 _igvn.register_new_node_with_optimizer(b);
1469 set_ctrl(b, phi->in(0));
1470
1471 assert( b->is_Bool(), "" );
1472 return (BoolNode*)b;
1473 }
1474
1475 //------------------------------clone_bool-------------------------------------
1476 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1477 // "Nearly" because all Nodes have been cloned from the original in the loop,
1478 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1479 // through the Phi recursively, and return a Bool.
1480 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) {
1481 uint i;
1482 // Convert this Phi into a Phi merging Bools
1483 for( i = 1; i < phi->req(); i++ ) {
1484 Node *b = phi->in(i);
1485 if( b->is_Phi() ) {
1486 _igvn.replace_input_of(phi, i, clone_bool( b->as_Phi(), loop ));
1487 } else {
1488 assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" );
1489 }
1490 }
1491
1492 Node *sample_cmp = phi->in(1);
1732 // Copy uses to a worklist, so I can munge the def-use info
1733 // with impunity.
1734 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1735 worklist.push(old->fast_out(j));
1736
1737 while( worklist.size() ) {
1738 Node *use = worklist.pop();
1739 if (!has_node(use)) continue; // Ignore dead nodes
1740 if (use->in(0) == C->top()) continue;
1741 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
1742 // Check for data-use outside of loop - at least one of OLD or USE
1743 // must not be a CFG node.
1744 if( !loop->is_member( use_loop ) && (!old->is_CFG() || !use->is_CFG())) {
1745
1746 // If the Data use is an IF, that means we have an IF outside of the
1747 // loop that is switching on a condition that is set inside of the
1748 // loop. Happens if people set a loop-exit flag; then test the flag
1749 // in the loop to break the loop, then test is again outside of the
1750 // loop to determine which way the loop exited.
1751 // Loop predicate If node connects to Bool node through Opaque1 node.
1752 if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use)) {
1753 // Since this code is highly unlikely, we lazily build the worklist
1754 // of such Nodes to go split.
1755 if( !split_if_set )
1756 split_if_set = new Node_List(area);
1757 split_if_set->push(use);
1758 }
1759 if( use->is_Bool() ) {
1760 if( !split_bool_set )
1761 split_bool_set = new Node_List(area);
1762 split_bool_set->push(use);
1763 }
1764 if( use->Opcode() == Op_CreateEx ) {
1765 if( !split_cex_set )
1766 split_cex_set = new Node_List(area);
1767 split_cex_set->push(use);
1768 }
1769
1770
1771 // Get "block" use is in
1772 uint idx = 0;
1773 while( use->in(idx) != old ) idx++;
1774 Node *prev = use->is_CFG() ? use : get_ctrl(use);
1775 assert( !loop->is_member( get_loop( prev ) ), "" );
1776 Node *cfg = prev->_idx >= new_counter
1777 ? prev->in(2)
1778 : idom(prev);
1779 if( use->is_Phi() ) // Phi use is in prior block
1780 cfg = prev->in(idx); // NOT in block of Phi itself
1781 if (cfg->is_top()) { // Use is dead?
1782 _igvn.replace_input_of(use, idx, C->top());
1783 continue;
1784 }
1785
1786 while( !loop->is_member( get_loop( cfg ) ) ) {
1835 // in AddPNode from tripping (when we end up with different
1836 // base & derived Phis that will become the same after
1837 // IGVN does CSE).
1838 Node *hit = _igvn.hash_find_insert(use);
1839 if( hit ) // Go ahead and re-hash for hits.
1840 _igvn.replace_node( use, hit );
1841 }
1842
1843 // If 'use' was in the loop-exit block, it now needs to be sunk
1844 // below the post-loop merge point.
1845 sink_use( use, prev );
1846 }
1847 }
1848 }
1849
1850 // Check for IFs that need splitting/cloning. Happens if an IF outside of
1851 // the loop uses a condition set in the loop. The original IF probably
1852 // takes control from one or more OLD Regions (which in turn get from NEW
1853 // Regions). In any case, there will be a set of Phis for each merge point
1854 // from the IF up to where the original BOOL def exists the loop.
1855 if( split_if_set ) {
1856 while( split_if_set->size() ) {
1857 Node *iff = split_if_set->pop();
1858 if( iff->in(1)->is_Phi() ) {
1859 BoolNode *b = clone_iff( iff->in(1)->as_Phi(), loop );
1860 _igvn.replace_input_of(iff, 1, b);
1861 }
1862 }
1863 }
1864 if( split_bool_set ) {
1865 while( split_bool_set->size() ) {
1866 Node *b = split_bool_set->pop();
1867 Node *phi = b->in(1);
1868 assert( phi->is_Phi(), "" );
1869 CmpNode *cmp = clone_bool( (PhiNode*)phi, loop );
1870 _igvn.replace_input_of(b, 1, cmp);
1871 }
1872 }
1873 if( split_cex_set ) {
1874 while( split_cex_set->size() ) {
1875 Node *b = split_cex_set->pop();
1876 assert( b->in(0)->is_Region(), "" );
1877 assert( b->in(1)->is_Phi(), "" );
1878 assert( b->in(0)->in(0) == b->in(1)->in(0), "" );
1879 split_up( b, b->in(0), NULL );
1880 }
1881 }
1882
1883 }
1884
1885
1886 //---------------------- stride_of_possible_iv -------------------------------------
1887 // Looks for an iff/bool/comp with one operand of the compare
1888 // being a cycle involving an add and a phi,
1889 // with an optional truncation (left-shift followed by a right-shift)
1890 // of the add. Returns zero if not an iv.
1891 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) {
1892 Node* trunc1 = NULL;
1893 Node* trunc2 = NULL;
1894 const TypeInt* ttype = NULL;
1895 if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) {
1896 return 0;
1897 }
1898 BoolNode* bl = iff->in(1)->as_Bool();
1899 Node* cmp = bl->in(1);
|
1390 // Get saved parent node and next use's index. Visit the rest of uses.
1391 n = nstack.node();
1392 cnt = n->outcnt();
1393 i = nstack.index();
1394 nstack.pop();
1395 }
1396 }
1397 }
1398
1399
1400 //=============================================================================
1401 //
1402 // C L O N E A L O O P B O D Y
1403 //
1404
1405 //------------------------------clone_iff--------------------------------------
1406 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1407 // "Nearly" because all Nodes have been cloned from the original in the loop,
1408 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1409 // through the Phi recursively, and return a Bool.
1410 Node* PhaseIdealLoop::clone_iff(PhiNode *phi, IdealLoopTree *loop) {
1411
1412 // Convert this Phi into a Phi merging Bools
1413 uint i;
1414 for (i = 1; i < phi->req(); i++) {
1415 Node *b = phi->in(i);
1416 if (b->is_Phi()) {
1417 _igvn.replace_input_of(phi, i, clone_iff(b->as_Phi(), loop));
1418 } else {
1419 assert(b->is_Bool() || b->Opcode() == Op_Opaque4, "");
1420 }
1421 }
1422
1423 Node* n = phi->in(1);
1424 Node* sample_opaque = NULL;
1425 Node *sample_bool = NULL;
1426 if (n->Opcode() == Op_Opaque4) {
1427 sample_opaque = n;
1428 sample_bool = n->in(1);
1429 assert(sample_bool->is_Bool(), "wrong type");
1430 } else {
1431 sample_bool = n;
1432 }
1433 Node *sample_cmp = sample_bool->in(1);
1434
1435 // Make Phis to merge the Cmp's inputs.
1436 PhiNode *phi1 = new PhiNode(phi->in(0), Type::TOP);
1437 PhiNode *phi2 = new PhiNode(phi->in(0), Type::TOP);
1438 for (i = 1; i < phi->req(); i++) {
1439 Node *n1 = sample_opaque == NULL ? phi->in(i)->in(1)->in(1) : phi->in(i)->in(1)->in(1)->in(1);
1440 Node *n2 = sample_opaque == NULL ? phi->in(i)->in(1)->in(2) : phi->in(i)->in(1)->in(1)->in(2);
1441 phi1->set_req(i, n1);
1442 phi2->set_req(i, n2);
1443 phi1->set_type(phi1->type()->meet_speculative(n1->bottom_type()));
1444 phi2->set_type(phi2->type()->meet_speculative(n2->bottom_type()));
1445 }
1446 // See if these Phis have been made before.
1447 // Register with optimizer
1448 Node *hit1 = _igvn.hash_find_insert(phi1);
1449 if (hit1) { // Hit, toss just made Phi
1450 _igvn.remove_dead_node(phi1); // Remove new phi
1451 assert(hit1->is_Phi(), "" );
1452 phi1 = (PhiNode*)hit1; // Use existing phi
1453 } else { // Miss
1454 _igvn.register_new_node_with_optimizer(phi1);
1455 }
1456 Node *hit2 = _igvn.hash_find_insert(phi2);
1457 if (hit2) { // Hit, toss just made Phi
1458 _igvn.remove_dead_node(phi2); // Remove new phi
1459 assert(hit2->is_Phi(), "" );
1460 phi2 = (PhiNode*)hit2; // Use existing phi
1461 } else { // Miss
1462 _igvn.register_new_node_with_optimizer(phi2);
1463 }
1464 // Register Phis with loop/block info
1465 set_ctrl(phi1, phi->in(0));
1466 set_ctrl(phi2, phi->in(0));
1467 // Make a new Cmp
1468 Node *cmp = sample_cmp->clone();
1469 cmp->set_req(1, phi1);
1470 cmp->set_req(2, phi2);
1471 _igvn.register_new_node_with_optimizer(cmp);
1472 set_ctrl(cmp, phi->in(0));
1473
1474 // Make a new Bool
1475 Node *b = sample_bool->clone();
1476 b->set_req(1,cmp);
1477 _igvn.register_new_node_with_optimizer(b);
1478 set_ctrl(b, phi->in(0));
1479
1480 if (sample_opaque != NULL) {
1481 Node* opaque = sample_opaque->clone();
1482 opaque->set_req(1, b);
1483 _igvn.register_new_node_with_optimizer(opaque);
1484 set_ctrl(opaque, phi->in(0));
1485 return opaque;
1486 }
1487
1488 assert(b->is_Bool(), "");
1489 return b;
1490 }
1491
1492 //------------------------------clone_bool-------------------------------------
1493 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1494 // "Nearly" because all Nodes have been cloned from the original in the loop,
1495 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1496 // through the Phi recursively, and return a Bool.
1497 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) {
1498 uint i;
1499 // Convert this Phi into a Phi merging Bools
1500 for( i = 1; i < phi->req(); i++ ) {
1501 Node *b = phi->in(i);
1502 if( b->is_Phi() ) {
1503 _igvn.replace_input_of(phi, i, clone_bool( b->as_Phi(), loop ));
1504 } else {
1505 assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" );
1506 }
1507 }
1508
1509 Node *sample_cmp = phi->in(1);
1749 // Copy uses to a worklist, so I can munge the def-use info
1750 // with impunity.
1751 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1752 worklist.push(old->fast_out(j));
1753
1754 while( worklist.size() ) {
1755 Node *use = worklist.pop();
1756 if (!has_node(use)) continue; // Ignore dead nodes
1757 if (use->in(0) == C->top()) continue;
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 ) ) ) {
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 }
1869
1870 // 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
1872 // takes control from one or more OLD Regions (which in turn get from NEW
1873 // Regions). In any case, there will be a set of Phis for each merge point
1874 // from the IF up to where the original BOOL def exists the loop.
1875 if (split_if_set) {
1876 while (split_if_set->size()) {
1877 Node *iff = split_if_set->pop();
1878 if (iff->in(1)->is_Phi()) {
1879 Node *b = clone_iff(iff->in(1)->as_Phi(), loop);
1880 _igvn.replace_input_of(iff, 1, b);
1881 }
1882 }
1883 }
1884 if (split_bool_set) {
1885 while (split_bool_set->size()) {
1886 Node *b = split_bool_set->pop();
1887 Node *phi = b->in(1);
1888 assert(phi->is_Phi(), "");
1889 CmpNode *cmp = clone_bool((PhiNode*)phi, loop);
1890 _igvn.replace_input_of(b, 1, cmp);
1891 }
1892 }
1893 if (split_cex_set) {
1894 while (split_cex_set->size()) {
1895 Node *b = split_cex_set->pop();
1896 assert(b->in(0)->is_Region(), "");
1897 assert(b->in(1)->is_Phi(), "");
1898 assert(b->in(0)->in(0) == b->in(1)->in(0), "");
1899 split_up(b, b->in(0), NULL);
1900 }
1901 }
1902
1903 }
1904
1905
1906 //---------------------- stride_of_possible_iv -------------------------------------
1907 // Looks for an iff/bool/comp with one operand of the compare
1908 // being a cycle involving an add and a phi,
1909 // with an optional truncation (left-shift followed by a right-shift)
1910 // of the add. Returns zero if not an iv.
1911 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) {
1912 Node* trunc1 = NULL;
1913 Node* trunc2 = NULL;
1914 const TypeInt* ttype = NULL;
1915 if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) {
1916 return 0;
1917 }
1918 BoolNode* bl = iff->in(1)->as_Bool();
1919 Node* cmp = bl->in(1);
|