1418 log->tail("loop"); |
1418 log->tail("loop"); |
1419 if( loop->_next ) log_loop_tree(root, loop->_next, log); |
1419 if( loop->_next ) log_loop_tree(root, loop->_next, log); |
1420 } |
1420 } |
1421 } |
1421 } |
1422 |
1422 |
|
1423 //---------------------collect_potentially_useful_predicates----------------------- |
|
1424 // Helper function to collect potentially useful predicates to prevent them from |
|
1425 // being eliminated by PhaseIdealLoop::eliminate_useless_predicates |
|
1426 void PhaseIdealLoop::collect_potentially_useful_predicates( |
|
1427 IdealLoopTree * loop, Unique_Node_List &useful_predicates) { |
|
1428 if (loop->_child) { // child |
|
1429 collect_potentially_useful_predicates(loop->_child, useful_predicates); |
|
1430 } |
|
1431 |
|
1432 // self (only loops that we can apply loop predication may use their predicates) |
|
1433 if (loop->_head->is_Loop() && |
|
1434 !loop->_irreducible && |
|
1435 !loop->tail()->is_top()) { |
|
1436 LoopNode *lpn = loop->_head->as_Loop(); |
|
1437 Node* entry = lpn->in(LoopNode::EntryControl); |
|
1438 ProjNode *predicate_proj = find_predicate_insertion_point(entry); |
|
1439 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication |
|
1440 assert(entry->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be"); |
|
1441 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one |
|
1442 } |
|
1443 } |
|
1444 |
|
1445 if ( loop->_next ) { // sibling |
|
1446 collect_potentially_useful_predicates(loop->_next, useful_predicates); |
|
1447 } |
|
1448 } |
|
1449 |
|
1450 //------------------------eliminate_useless_predicates----------------------------- |
|
1451 // Eliminate all inserted predicates if they could not be used by loop predication. |
|
1452 void PhaseIdealLoop::eliminate_useless_predicates() { |
|
1453 if (C->predicate_count() == 0) return; // no predicate left |
|
1454 |
|
1455 Unique_Node_List useful_predicates; // to store useful predicates |
|
1456 if (C->has_loops()) { |
|
1457 collect_potentially_useful_predicates(_ltree_root->_child, useful_predicates); |
|
1458 } |
|
1459 |
|
1460 for (int i = C->predicate_count(); i > 0; i--) { |
|
1461 Node * n = C->predicate_opaque1_node(i-1); |
|
1462 assert(n->Opcode() == Op_Opaque1, "must be"); |
|
1463 if (!useful_predicates.member(n)) { // not in the useful list |
|
1464 _igvn.replace_node(n, n->in(1)); |
|
1465 } |
|
1466 } |
|
1467 } |
|
1468 |
1423 //============================================================================= |
1469 //============================================================================= |
1424 //----------------------------build_and_optimize------------------------------- |
1470 //----------------------------build_and_optimize------------------------------- |
1425 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to |
1471 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to |
1426 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups. |
1472 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups. |
1427 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs) { |
1473 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs, bool do_loop_pred) { |
1428 int old_progress = C->major_progress(); |
1474 int old_progress = C->major_progress(); |
1429 |
1475 |
1430 // Reset major-progress flag for the driver's heuristics |
1476 // Reset major-progress flag for the driver's heuristics |
1431 C->clear_major_progress(); |
1477 C->clear_major_progress(); |
1432 |
1478 |
1575 assert(C->unique() == unique, "verification mode made Nodes? ? ?"); |
1621 assert(C->unique() == unique, "verification mode made Nodes? ? ?"); |
1576 assert(_igvn._worklist.size() == 0, "shouldn't push anything"); |
1622 assert(_igvn._worklist.size() == 0, "shouldn't push anything"); |
1577 return; |
1623 return; |
1578 } |
1624 } |
1579 |
1625 |
|
1626 // some parser-inserted loop predicates could never be used by loop |
|
1627 // predication. Eliminate them before loop optimization |
|
1628 if (UseLoopPredicate) { |
|
1629 eliminate_useless_predicates(); |
|
1630 } |
|
1631 |
1580 // clear out the dead code |
1632 // clear out the dead code |
1581 while(_deadlist.size()) { |
1633 while(_deadlist.size()) { |
1582 _igvn.remove_globally_dead_node(_deadlist.pop()); |
1634 _igvn.remove_globally_dead_node(_deadlist.pop()); |
1583 } |
1635 } |
1584 |
1636 |
1601 lpt->reassociate_invariants(this); |
1653 lpt->reassociate_invariants(this); |
1602 |
1654 |
1603 // Because RCE opportunities can be masked by split_thru_phi, |
1655 // Because RCE opportunities can be masked by split_thru_phi, |
1604 // look for RCE candidates and inhibit split_thru_phi |
1656 // look for RCE candidates and inhibit split_thru_phi |
1605 // on just their loop-phi's for this pass of loop opts |
1657 // on just their loop-phi's for this pass of loop opts |
1606 if( SplitIfBlocks && do_split_ifs ) { |
1658 if (SplitIfBlocks && do_split_ifs) { |
1607 if (lpt->policy_range_check(this)) { |
1659 if (lpt->policy_range_check(this)) { |
1608 lpt->_rce_candidate = 1; // = true |
1660 lpt->_rce_candidate = 1; // = true |
1609 } |
1661 } |
1610 } |
1662 } |
1611 } |
1663 } |
1617 visited.Clear(); |
1669 visited.Clear(); |
1618 split_if_with_blocks( visited, nstack ); |
1670 split_if_with_blocks( visited, nstack ); |
1619 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); ); |
1671 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); ); |
1620 } |
1672 } |
1621 |
1673 |
|
1674 // Perform loop predication before iteration splitting |
|
1675 if (do_loop_pred && C->has_loops() && !C->major_progress()) { |
|
1676 _ltree_root->_child->loop_predication(this); |
|
1677 } |
|
1678 |
1622 // Perform iteration-splitting on inner loops. Split iterations to avoid |
1679 // Perform iteration-splitting on inner loops. Split iterations to avoid |
1623 // range checks or one-shot null checks. |
1680 // range checks or one-shot null checks. |
1624 |
1681 |
1625 // If split-if's didn't hack the graph too bad (no CFG changes) |
1682 // If split-if's didn't hack the graph too bad (no CFG changes) |
1626 // then do loop opts. |
1683 // then do loop opts. |
1627 if( C->has_loops() && !C->major_progress() ) { |
1684 if (C->has_loops() && !C->major_progress()) { |
1628 memset( worklist.adr(), 0, worklist.Size()*sizeof(Node*) ); |
1685 memset( worklist.adr(), 0, worklist.Size()*sizeof(Node*) ); |
1629 _ltree_root->_child->iteration_split( this, worklist ); |
1686 _ltree_root->_child->iteration_split( this, worklist ); |
1630 // No verify after peeling! GCM has hoisted code out of the loop. |
1687 // No verify after peeling! GCM has hoisted code out of the loop. |
1631 // After peeling, the hoisted code could sink inside the peeled area. |
1688 // After peeling, the hoisted code could sink inside the peeled area. |
1632 // The peeling code does not try to recompute the best location for |
1689 // The peeling code does not try to recompute the best location for |
1634 // complain about it. |
1691 // complain about it. |
1635 } |
1692 } |
1636 // Do verify graph edges in any case |
1693 // Do verify graph edges in any case |
1637 NOT_PRODUCT( C->verify_graph_edges(); ); |
1694 NOT_PRODUCT( C->verify_graph_edges(); ); |
1638 |
1695 |
1639 if( !do_split_ifs ) { |
1696 if (!do_split_ifs) { |
1640 // We saw major progress in Split-If to get here. We forced a |
1697 // We saw major progress in Split-If to get here. We forced a |
1641 // pass with unrolling and not split-if, however more split-if's |
1698 // pass with unrolling and not split-if, however more split-if's |
1642 // might make progress. If the unrolling didn't make progress |
1699 // might make progress. If the unrolling didn't make progress |
1643 // then the major-progress flag got cleared and we won't try |
1700 // then the major-progress flag got cleared and we won't try |
1644 // another round of Split-If. In particular the ever-common |
1701 // another round of Split-If. In particular the ever-common |
2761 assert(LCA != NULL && !LCA->is_top(), "no dead nodes"); |
2818 assert(LCA != NULL && !LCA->is_top(), "no dead nodes"); |
2762 |
2819 |
2763 Node *legal = LCA; // Walk 'legal' up the IDOM chain |
2820 Node *legal = LCA; // Walk 'legal' up the IDOM chain |
2764 Node *least = legal; // Best legal position so far |
2821 Node *least = legal; // Best legal position so far |
2765 while( early != legal ) { // While not at earliest legal |
2822 while( early != legal ) { // While not at earliest legal |
|
2823 #ifdef ASSERT |
|
2824 if (legal->is_Start() && !early->is_Root()) { |
|
2825 // Bad graph. Print idom path and fail. |
|
2826 tty->print_cr( "Bad graph detected in build_loop_late"); |
|
2827 tty->print("n: ");n->dump(); tty->cr(); |
|
2828 tty->print("early: ");early->dump(); tty->cr(); |
|
2829 int ct = 0; |
|
2830 Node *dbg_legal = LCA; |
|
2831 while(!dbg_legal->is_Start() && ct < 100) { |
|
2832 tty->print("idom[%d] ",ct); dbg_legal->dump(); tty->cr(); |
|
2833 ct++; |
|
2834 dbg_legal = idom(dbg_legal); |
|
2835 } |
|
2836 assert(false, "Bad graph detected in build_loop_late"); |
|
2837 } |
|
2838 #endif |
2766 // Find least loop nesting depth |
2839 // Find least loop nesting depth |
2767 legal = idom(legal); // Bump up the IDOM tree |
2840 legal = idom(legal); // Bump up the IDOM tree |
2768 // Check for lower nesting depth |
2841 // Check for lower nesting depth |
2769 if( get_loop(legal)->_nest < get_loop(least)->_nest ) |
2842 if( get_loop(legal)->_nest < get_loop(least)->_nest ) |
2770 least = legal; |
2843 least = legal; |