1403 log->print(" idx='%d' ", head->_idx);
1404 if (loop->_irreducible) log->print("irreducible='1' ");
1405 if (head->is_Loop()) {
1406 if (head->as_Loop()->is_inner_loop()) log->print("inner_loop='1' ");
1407 if (head->as_Loop()->is_partial_peel_loop()) log->print("partial_peel_loop='1' ");
1408 }
1409 if (head->is_CountedLoop()) {
1410 CountedLoopNode* cl = head->as_CountedLoop();
1411 if (cl->is_pre_loop()) log->print("pre_loop='%d' ", cl->main_idx());
1412 if (cl->is_main_loop()) log->print("main_loop='%d' ", cl->_idx);
1413 if (cl->is_post_loop()) log->print("post_loop='%d' ", cl->main_idx());
1414 }
1415 log->end_head();
1416 if( loop->_child ) log_loop_tree(root, loop->_child, log);
1417 log->tail("loop");
1418 if( loop->_next ) log_loop_tree(root, loop->_next, log);
1419 }
1420 }
1421
1422 //=============================================================================
1423 //------------------------------PhaseIdealLoop---------------------------------
1424 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
1425 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
1426 PhaseIdealLoop::PhaseIdealLoop( PhaseIterGVN &igvn, const PhaseIdealLoop *verify_me, bool do_split_ifs )
1427 : PhaseTransform(Ideal_Loop),
1428 _igvn(igvn),
1429 _dom_lca_tags(C->comp_arena()) {
1430 // Reset major-progress flag for the driver's heuristics
1431 C->clear_major_progress();
1432
1433 #ifndef PRODUCT
1434 // Capture for later assert
1435 uint unique = C->unique();
1436 _loop_invokes++;
1437 _loop_work += unique;
1438 #endif
1439
1440 // True if the method has at least 1 irreducible loop
1441 _has_irreducible_loops = false;
1442
1443 _created_loop_node = false;
1444
1445 Arena *a = Thread::current()->resource_area();
1446 VectorSet visited(a);
1447 // Pre-grow the mapping from Nodes to IdealLoopTrees.
1448 _nodes.map(C->unique(), NULL);
1449 memset(_nodes.adr(), 0, wordSize * C->unique());
1450
1451 // Pre-build the top-level outermost loop tree entry
1452 _ltree_root = new IdealLoopTree( this, C->root(), C->root() );
1453 // Do not need a safepoint at the top level
1454 _ltree_root->_has_sfpt = 1;
1455
1456 // Empty pre-order array
1457 allocate_preorders();
1458
1459 // Build a loop tree on the fly. Build a mapping from CFG nodes to
1460 // IdealLoopTree entries. Data nodes are NOT walked.
1461 build_loop_tree();
1462 // Check for bailout, and return
1463 if (C->failing()) {
1464 return;
1465 }
1466
1467 // No loops after all
1468 if( !_ltree_root->_child ) C->set_has_loops(false);
1469
1470 // There should always be an outer loop containing the Root and Return nodes.
1471 // If not, we have a degenerate empty program. Bail out in this case.
1472 if (!has_node(C->root())) {
1473 C->clear_major_progress();
1474 C->record_method_not_compilable("empty program detected during loop optimization");
1475 return;
1476 }
1477
1478 // Nothing to do, so get out
1479 if( !C->has_loops() && !do_split_ifs && !verify_me) {
1480 _igvn.optimize(); // Cleanup NeverBranches
1481 return;
1482 }
1483
1484 // Set loop nesting depth
1485 _ltree_root->set_nest( 0 );
1486
1487 // Split shared headers and insert loop landing pads.
1488 // Do not bother doing this on the Root loop of course.
1489 if( !verify_me && _ltree_root->_child ) {
1490 if( _ltree_root->_child->beautify_loops( this ) ) {
1491 // Re-build loop tree!
1492 _ltree_root->_child = NULL;
1493 _nodes.clear();
1494 reallocate_preorders();
1495 build_loop_tree();
1496 // Check for bailout, and return
1497 if (C->failing()) {
1498 return;
1499 }
1500 // Reset loop nesting depth
1501 _ltree_root->set_nest( 0 );
1502
1503 C->print_method("After beautify loops", 3);
1504 }
1505 }
1506
1507 // Build Dominators for elision of NULL checks & loop finding.
1508 // Since nodes do not have a slot for immediate dominator, make
1509 // a persistent side array for that info indexed on node->_idx.
1510 _idom_size = C->unique();
1511 _idom = NEW_RESOURCE_ARRAY( Node*, _idom_size );
1512 _dom_depth = NEW_RESOURCE_ARRAY( uint, _idom_size );
1513 _dom_stk = NULL; // Allocated on demand in recompute_dom_depth
1514 memset( _dom_depth, 0, _idom_size * sizeof(uint) );
1515
1516 Dominators();
1517
1518 // As a side effect, Dominators removed any unreachable CFG paths
1519 // into RegionNodes. It doesn't do this test against Root, so
1520 // we do it here.
1521 for( uint i = 1; i < C->root()->req(); i++ ) {
1522 if( !_nodes[C->root()->in(i)->_idx] ) { // Dead path into Root?
1523 _igvn.hash_delete(C->root());
1524 C->root()->del_req(i);
1525 _igvn._worklist.push(C->root());
1526 i--; // Rerun same iteration on compressed edges
1527 }
1528 }
1529
1530 // Given dominators, try to find inner loops with calls that must
1531 // always be executed (call dominates loop tail). These loops do
1532 // not need a separate safepoint.
1533 Node_List cisstack(a);
1534 _ltree_root->check_safepts(visited, cisstack);
1535
1536 // Walk the DATA nodes and place into loops. Find earliest control
1537 // node. For CFG nodes, the _nodes array starts out and remains
1538 // holding the associated IdealLoopTree pointer. For DATA nodes, the
1539 // _nodes array holds the earliest legal controlling CFG node.
1540
1541 // Allocate stack with enough space to avoid frequent realloc
1542 int stack_size = (C->unique() >> 1) + 16; // (unique>>1)+16 from Java2D stats
1543 Node_Stack nstack( a, stack_size );
1544
1545 visited.Clear();
1546 Node_List worklist(a);
1547 // Don't need C->root() on worklist since
1548 // it will be processed among C->top() inputs
1549 worklist.push( C->top() );
1550 visited.set( C->top()->_idx ); // Set C->top() as visited now
1551 build_loop_early( visited, worklist, nstack, verify_me );
1552
1553 // Given early legal placement, try finding counted loops. This placement
1554 // is good enough to discover most loop invariants.
1555 if( !verify_me )
1556 _ltree_root->counted_loop( this );
1557
1558 // Find latest loop placement. Find ideal loop placement.
1559 visited.Clear();
1560 init_dom_lca_tags();
1561 // Need C->root() on worklist when processing outs
1562 worklist.push( C->root() );
1563 NOT_PRODUCT( C->verify_graph_edges(); )
1564 worklist.push( C->top() );
1565 build_loop_late( visited, worklist, nstack, verify_me );
1566
1567 // clear out the dead code
1568 while(_deadlist.size()) {
1569 igvn.remove_globally_dead_node(_deadlist.pop());
1570 }
1571
1572 #ifndef PRODUCT
1573 C->verify_graph_edges();
1574 if( verify_me ) { // Nested verify pass?
1575 // Check to see if the verify mode is broken
1576 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
1577 return;
1578 }
1579 if( VerifyLoopOptimizations ) verify();
1580 #endif
1581
1582 if (ReassociateInvariants) {
1583 // Reassociate invariants and prep for split_thru_phi
1584 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1585 IdealLoopTree* lpt = iter.current();
1586 if (!lpt->is_counted() || !lpt->is_inner()) continue;
1587
1588 lpt->reassociate_invariants(this);
1589
1590 // Because RCE opportunities can be masked by split_thru_phi,
1591 // look for RCE candidates and inhibit split_thru_phi
1592 // on just their loop-phi's for this pass of loop opts
1593 if( SplitIfBlocks && do_split_ifs ) {
1594 if (lpt->policy_range_check(this)) {
1661
1662 if (C->log() != NULL) {
1663 log_loop_tree(_ltree_root, _ltree_root, C->log());
1664 }
1665 }
1666
1667 #ifndef PRODUCT
1668 //------------------------------print_statistics-------------------------------
1669 int PhaseIdealLoop::_loop_invokes=0;// Count of PhaseIdealLoop invokes
1670 int PhaseIdealLoop::_loop_work=0; // Sum of PhaseIdealLoop x unique
1671 void PhaseIdealLoop::print_statistics() {
1672 tty->print_cr("PhaseIdealLoop=%d, sum _unique=%d", _loop_invokes, _loop_work);
1673 }
1674
1675 //------------------------------verify-----------------------------------------
1676 // Build a verify-only PhaseIdealLoop, and see that it agrees with me.
1677 static int fail; // debug only, so its multi-thread dont care
1678 void PhaseIdealLoop::verify() const {
1679 int old_progress = C->major_progress();
1680 ResourceMark rm;
1681 PhaseIdealLoop loop_verify( _igvn, this, false );
1682 VectorSet visited(Thread::current()->resource_area());
1683
1684 fail = 0;
1685 verify_compare( C->root(), &loop_verify, visited );
1686 assert( fail == 0, "verify loops failed" );
1687 // Verify loop structure is the same
1688 _ltree_root->verify_tree(loop_verify._ltree_root, NULL);
1689 // Reset major-progress. It was cleared by creating a verify version of
1690 // PhaseIdealLoop.
1691 for( int i=0; i<old_progress; i++ )
1692 C->set_major_progress();
1693 }
1694
1695 //------------------------------verify_compare---------------------------------
1696 // Make sure me and the given PhaseIdealLoop agree on key data structures
1697 void PhaseIdealLoop::verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const {
1698 if( !n ) return;
1699 if( visited.test_set( n->_idx ) ) return;
1700 if( !_nodes[n->_idx] ) { // Unreachable
1701 assert( !loop_verify->_nodes[n->_idx], "both should be unreachable" );
2121 // is a member of some outer enclosing loop. Since there are no
2122 // shared headers (I've split them already) I only need to go up
2123 // at most 1 level.
2124 while( l && l->_head == m ) // Successor heads loop?
2125 l = l->_parent; // Move up 1 for me
2126 // If this loop is not properly parented, then this loop
2127 // has no exit path out, i.e. its an infinite loop.
2128 if( !l ) {
2129 // Make loop "reachable" from root so the CFG is reachable. Basically
2130 // insert a bogus loop exit that is never taken. 'm', the loop head,
2131 // points to 'n', one (of possibly many) fall-in paths. There may be
2132 // many backedges as well.
2133
2134 // Here I set the loop to be the root loop. I could have, after
2135 // inserting a bogus loop exit, restarted the recursion and found my
2136 // new loop exit. This would make the infinite loop a first-class
2137 // loop and it would then get properly optimized. What's the use of
2138 // optimizing an infinite loop?
2139 l = _ltree_root; // Oops, found infinite loop
2140
2141 // Insert the NeverBranch between 'm' and it's control user.
2142 NeverBranchNode *iff = new (C, 1) NeverBranchNode( m );
2143 _igvn.register_new_node_with_optimizer(iff);
2144 set_loop(iff, l);
2145 Node *if_t = new (C, 1) CProjNode( iff, 0 );
2146 _igvn.register_new_node_with_optimizer(if_t);
2147 set_loop(if_t, l);
2148
2149 Node* cfg = NULL; // Find the One True Control User of m
2150 for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) {
2151 Node* x = m->fast_out(j);
2152 if (x->is_CFG() && x != m && x != iff)
2153 { cfg = x; break; }
2154 }
2155 assert(cfg != NULL, "must find the control user of m");
2156 uint k = 0; // Probably cfg->in(0)
2157 while( cfg->in(k) != m ) k++; // But check incase cfg is a Region
2158 cfg->set_req( k, if_t ); // Now point to NeverBranch
2159
2160 // Now create the never-taken loop exit
2161 Node *if_f = new (C, 1) CProjNode( iff, 1 );
2162 _igvn.register_new_node_with_optimizer(if_f);
2163 set_loop(if_f, l);
2164 // Find frame ptr for Halt. Relies on the optimizer
2165 // V-N'ing. Easier and quicker than searching through
2166 // the program structure.
2167 Node *frame = new (C, 1) ParmNode( C->start(), TypeFunc::FramePtr );
2168 _igvn.register_new_node_with_optimizer(frame);
2169 // Halt & Catch Fire
2170 Node *halt = new (C, TypeFunc::Parms) HaltNode( if_f, frame );
2171 _igvn.register_new_node_with_optimizer(halt);
2172 set_loop(halt, l);
2173 C->root()->add_req(halt);
2174 set_loop(C->root(), _ltree_root);
2175 }
2176 }
2177 // Weeny check for irreducible. This child was already visited (this
2178 // IS the post-work phase). Is this child's loop header post-visited
2179 // as well? If so, then I found another entry into the loop.
2180 while( is_postvisited(l->_head) ) {
2181 // found irreducible
2182 l->_irreducible = 1; // = true
2183 l = l->_parent;
2184 _has_irreducible_loops = true;
2185 // Check for bad CFG here to prevent crash, and bailout of compile
2186 if (l == NULL) {
2187 C->record_method_not_compilable("unhandled CFG detected during loop optimization");
2188 return pre_order;
2189 }
2190 }
2191
2192 // This Node might be a decision point for loops. It is only if
2193 // it's children belong to several different loops. The sort call
2194 // does a trivial amount of work if there is only 1 child or all
2195 // children belong to the same loop. If however, the children
2196 // belong to different loops, the sort call will properly set the
2197 // _parent pointers to show how the loops nest.
2198 //
2199 // In any case, it returns the tightest enclosing loop.
2200 innermost = sort( l, innermost );
2201 }
2202
2203 // Def-use info will have some dead stuff; dead stuff will have no
2204 // loop decided on.
2205
2206 // Am I a loop header? If so fix up my parent's child and next ptrs.
2207 if( innermost && innermost->_head == n ) {
2208 assert( get_loop(n) == innermost, "" );
2209 IdealLoopTree *p = innermost->_parent;
2210 IdealLoopTree *l = innermost;
2236 } else if( n->is_Allocate() && n->as_Allocate()->_is_scalar_replaceable ) {
2237 // Disable loop optimizations if the loop has a scalar replaceable
2238 // allocation. This disabling may cause a potential performance lost
2239 // if the allocation is not eliminated for some reason.
2240 innermost->_allow_optimizations = false;
2241 innermost->_has_call = 1; // = true
2242 }
2243 }
2244 }
2245
2246 // Flag as post-visited now
2247 set_postvisited(n);
2248 return pre_order;
2249 }
2250
2251
2252 //------------------------------build_loop_early-------------------------------
2253 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2254 // First pass computes the earliest controlling node possible. This is the
2255 // controlling input with the deepest dominating depth.
2256 void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack, const PhaseIdealLoop *verify_me ) {
2257 while (worklist.size() != 0) {
2258 // Use local variables nstack_top_n & nstack_top_i to cache values
2259 // on nstack's top.
2260 Node *nstack_top_n = worklist.pop();
2261 uint nstack_top_i = 0;
2262 //while_nstack_nonempty:
2263 while (true) {
2264 // Get parent node and next input's index from stack's top.
2265 Node *n = nstack_top_n;
2266 uint i = nstack_top_i;
2267 uint cnt = n->req(); // Count of inputs
2268 if (i == 0) { // Pre-process the node.
2269 if( has_node(n) && // Have either loop or control already?
2270 !has_ctrl(n) ) { // Have loop picked out already?
2271 // During "merge_many_backedges" we fold up several nested loops
2272 // into a single loop. This makes the members of the original
2273 // loop bodies pointing to dead loops; they need to move up
2274 // to the new UNION'd larger loop. I set the _head field of these
2275 // dead loops to NULL and the _parent field points to the owning
2276 // loop. Shades of UNION-FIND algorithm.
2277 IdealLoopTree *ilt;
2278 while( !(ilt = get_loop(n))->_head ) {
2279 // Normally I would use a set_loop here. But in this one special
2280 // case, it is legal (and expected) to change what loop a Node
2281 // belongs to.
2282 _nodes.map(n->_idx, (Node*)(ilt->_parent) );
2283 }
2284 // Remove safepoints ONLY if I've already seen I don't need one.
2285 // (the old code here would yank a 2nd safepoint after seeing a
2286 // first one, even though the 1st did not dominate in the loop body
2287 // and thus could be avoided indefinitely)
2288 if( !verify_me && ilt->_has_sfpt && n->Opcode() == Op_SafePoint &&
2289 is_deleteable_safept(n)) {
2290 Node *in = n->in(TypeFunc::Control);
2291 lazy_replace(n,in); // Pull safepoint now
2292 // Carry on with the recursion "as if" we are walking
2293 // only the control input
2294 if( !visited.test_set( in->_idx ) ) {
2295 worklist.push(in); // Visit this guy later, using worklist
2296 }
2297 // Get next node from nstack:
2298 // - skip n's inputs processing by setting i > cnt;
2299 // - we also will not call set_early_ctrl(n) since
2300 // has_node(n) == true (see the condition above).
2301 i = cnt + 1;
2302 }
2303 }
2304 } // if (i == 0)
2305
2306 // Visit all inputs
2307 bool done = true; // Assume all n's inputs will be processed
2308 while (i < cnt) {
2391 d1 = dom_depth(n1);
2392 d2 = dom_depth(n2);
2393 }
2394 }
2395 return n1;
2396 }
2397
2398 //------------------------------compute_idom-----------------------------------
2399 // Locally compute IDOM using dom_lca call. Correct only if the incoming
2400 // IDOMs are correct.
2401 Node *PhaseIdealLoop::compute_idom( Node *region ) const {
2402 assert( region->is_Region(), "" );
2403 Node *LCA = NULL;
2404 for( uint i = 1; i < region->req(); i++ ) {
2405 if( region->in(i) != C->top() )
2406 LCA = dom_lca( LCA, region->in(i) );
2407 }
2408 return LCA;
2409 }
2410
2411 //------------------------------get_late_ctrl----------------------------------
2412 // Compute latest legal control.
2413 Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
2414 assert(early != NULL, "early control should not be NULL");
2415
2416 // Compute LCA over list of uses
2417 Node *LCA = NULL;
2418 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && LCA != early; i++) {
2419 Node* c = n->fast_out(i);
2420 if (_nodes[c->_idx] == NULL)
2421 continue; // Skip the occasional dead node
2422 if( c->is_Phi() ) { // For Phis, we must land above on the path
2423 for( uint j=1; j<c->req(); j++ ) {// For all inputs
2424 if( c->in(j) == n ) { // Found matching input?
2425 Node *use = c->in(0)->in(j);
2426 LCA = dom_lca_for_get_late_ctrl( LCA, use, n );
2427 }
2428 }
2429 } else {
2430 // For CFG data-users, use is in the block just prior
2431 Node *use = has_ctrl(c) ? get_ctrl(c) : c->in(0);
2432 LCA = dom_lca_for_get_late_ctrl( LCA, use, n );
2433 }
2434 }
2435
2436 // if this is a load, check for anti-dependent stores
2437 // We use a conservative algorithm to identify potential interfering
2438 // instructions and for rescheduling the load. The users of the memory
2439 // input of this load are examined. Any use which is not a load and is
2440 // dominated by early is considered a potentially interfering store.
2441 // This can produce false positives.
2442 if (n->is_Load() && LCA != early) {
2443 Node_List worklist;
2444
2445 Node *mem = n->in(MemNode::Memory);
2446 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
2447 Node* s = mem->fast_out(i);
2448 worklist.push(s);
2449 }
2450 while(worklist.size() != 0 && LCA != early) {
2451 Node* s = worklist.pop();
2452 if (s->is_Load()) {
2453 continue;
2454 } else if (s->is_MergeMem()) {
2455 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
2559 }
2560
2561 //------------------------------clear_dom_lca_tags------------------------------
2562 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
2563 // Intended use does not involve any growth for the array, so it could
2564 // be of fixed size.
2565 void PhaseIdealLoop::clear_dom_lca_tags() {
2566 uint limit = C->unique() + 1;
2567 _dom_lca_tags.map( limit, NULL );
2568 _dom_lca_tags.clear();
2569 #ifdef ASSERT
2570 for( uint i = 0; i < limit; ++i ) {
2571 assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
2572 }
2573 #endif // ASSERT
2574 }
2575
2576 //------------------------------build_loop_late--------------------------------
2577 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2578 // Second pass finds latest legal placement, and ideal loop placement.
2579 void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack, const PhaseIdealLoop *verify_me ) {
2580 while (worklist.size() != 0) {
2581 Node *n = worklist.pop();
2582 // Only visit once
2583 if (visited.test_set(n->_idx)) continue;
2584 uint cnt = n->outcnt();
2585 uint i = 0;
2586 while (true) {
2587 assert( _nodes[n->_idx], "no dead nodes" );
2588 // Visit all children
2589 if (i < cnt) {
2590 Node* use = n->raw_out(i);
2591 ++i;
2592 // Check for dead uses. Aggressively prune such junk. It might be
2593 // dead in the global sense, but still have local uses so I cannot
2594 // easily call 'remove_dead_node'.
2595 if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
2596 // Due to cycles, we might not hit the same fixed point in the verify
2597 // pass as we do in the regular pass. Instead, visit such phis as
2598 // simple uses of the loop head.
2599 if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
2600 if( !visited.test(use->_idx) )
2601 worklist.push(use);
2602 } else if( !visited.test_set(use->_idx) ) {
2603 nstack.push(n, i); // Save parent and next use's index.
2604 n = use; // Process all children of current use.
2605 cnt = use->outcnt();
2606 i = 0;
2607 }
2608 } else {
2609 // Do not visit around the backedge of loops via data edges.
2610 // push dead code onto a worklist
2611 _deadlist.push(use);
2612 }
2613 } else {
2614 // All of n's children have been processed, complete post-processing.
2615 build_loop_late_post(n, verify_me);
2616 if (nstack.is_empty()) {
2617 // Finished all nodes on stack.
2618 // Process next node on the worklist.
2619 break;
2620 }
2621 // Get saved parent node and next use's index. Visit the rest of uses.
2622 n = nstack.node();
2623 cnt = n->outcnt();
2624 i = nstack.index();
2625 nstack.pop();
2626 }
2627 }
2628 }
2629 }
2630
2631 //------------------------------build_loop_late_post---------------------------
2632 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2633 // Second pass finds latest legal placement, and ideal loop placement.
2634 void PhaseIdealLoop::build_loop_late_post( Node *n, const PhaseIdealLoop *verify_me ) {
2635
2636 if (n->req() == 2 && n->Opcode() == Op_ConvI2L && !C->major_progress()) {
2637 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops.
2638 }
2639
2640 // CFG and pinned nodes already handled
2641 if( n->in(0) ) {
2642 if( n->in(0)->is_top() ) return; // Dead?
2643
2644 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
2645 // _must_ be pinned (they have to observe their control edge of course).
2646 // Unlike Stores (which modify an unallocable resource, the memory
2647 // state), Mods/Loads can float around. So free them up.
2648 bool pinned = true;
2649 switch( n->Opcode() ) {
2650 case Op_DivI:
2651 case Op_DivF:
2652 case Op_DivD:
2653 case Op_ModI:
2654 case Op_ModF:
2655 case Op_ModD:
2656 case Op_LoadB: // Same with Loads; they can sink
2697 #ifdef ASSERT
2698 for (DUIterator i1 = n->outs(); n->has_out(i1); i1++) {
2699 assert( _nodes[n->out(i1)->_idx] == NULL, "all uses must also be dead");
2700 }
2701 #endif
2702 _nodes.map(n->_idx, 0); // This node is useless
2703 _deadlist.push(n);
2704 return;
2705 }
2706 assert(LCA != NULL && !LCA->is_top(), "no dead nodes");
2707
2708 Node *legal = LCA; // Walk 'legal' up the IDOM chain
2709 Node *least = legal; // Best legal position so far
2710 while( early != legal ) { // While not at earliest legal
2711 // Find least loop nesting depth
2712 legal = idom(legal); // Bump up the IDOM tree
2713 // Check for lower nesting depth
2714 if( get_loop(legal)->_nest < get_loop(least)->_nest )
2715 least = legal;
2716 }
2717
2718 // Try not to place code on a loop entry projection
2719 // which can inhibit range check elimination.
2720 if (least != early) {
2721 Node* ctrl_out = least->unique_ctrl_out();
2722 if (ctrl_out && ctrl_out->is_CountedLoop() &&
2723 least == ctrl_out->in(LoopNode::EntryControl)) {
2724 Node* least_dom = idom(least);
2725 if (get_loop(least_dom)->is_member(get_loop(least))) {
2726 least = least_dom;
2727 }
2728 }
2729 }
2730
2731 #ifdef ASSERT
2732 // If verifying, verify that 'verify_me' has a legal location
2733 // and choose it as our location.
2734 if( verify_me ) {
2735 Node *v_ctrl = verify_me->get_ctrl_no_update(n);
2736 Node *legal = LCA;
2737 while( early != legal ) { // While not at earliest legal
2738 if( legal == v_ctrl ) break; // Check for prior good location
2739 legal = idom(legal) ;// Bump up the IDOM tree
2740 }
2741 // Check for prior good location
2742 if( legal == v_ctrl ) least = legal; // Keep prior if found
2743 }
2744 #endif
2745
2746 // Assign discovered "here or above" point
2747 least = find_non_split_ctrl(least);
2748 set_ctrl(n, least);
2749
2750 // Collect inner loop bodies
2751 IdealLoopTree *chosen_loop = get_loop(least);
2752 if( !chosen_loop->_child ) // Inner loop?
2753 chosen_loop->_body.push(n);// Collect inner loops
2754 }
2755
|
1403 log->print(" idx='%d' ", head->_idx);
1404 if (loop->_irreducible) log->print("irreducible='1' ");
1405 if (head->is_Loop()) {
1406 if (head->as_Loop()->is_inner_loop()) log->print("inner_loop='1' ");
1407 if (head->as_Loop()->is_partial_peel_loop()) log->print("partial_peel_loop='1' ");
1408 }
1409 if (head->is_CountedLoop()) {
1410 CountedLoopNode* cl = head->as_CountedLoop();
1411 if (cl->is_pre_loop()) log->print("pre_loop='%d' ", cl->main_idx());
1412 if (cl->is_main_loop()) log->print("main_loop='%d' ", cl->_idx);
1413 if (cl->is_post_loop()) log->print("post_loop='%d' ", cl->main_idx());
1414 }
1415 log->end_head();
1416 if( loop->_child ) log_loop_tree(root, loop->_child, log);
1417 log->tail("loop");
1418 if( loop->_next ) log_loop_tree(root, loop->_next, log);
1419 }
1420 }
1421
1422 //=============================================================================
1423 //----------------------------build_and_optimize-------------------------------
1424 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
1425 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
1426 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs) {
1427 int old_progress = C->major_progress();
1428
1429 // Reset major-progress flag for the driver's heuristics
1430 C->clear_major_progress();
1431
1432 #ifndef PRODUCT
1433 // Capture for later assert
1434 uint unique = C->unique();
1435 _loop_invokes++;
1436 _loop_work += unique;
1437 #endif
1438
1439 // True if the method has at least 1 irreducible loop
1440 _has_irreducible_loops = false;
1441
1442 _created_loop_node = false;
1443
1444 Arena *a = Thread::current()->resource_area();
1445 VectorSet visited(a);
1446 // Pre-grow the mapping from Nodes to IdealLoopTrees.
1447 _nodes.map(C->unique(), NULL);
1448 memset(_nodes.adr(), 0, wordSize * C->unique());
1449
1450 // Pre-build the top-level outermost loop tree entry
1451 _ltree_root = new IdealLoopTree( this, C->root(), C->root() );
1452 // Do not need a safepoint at the top level
1453 _ltree_root->_has_sfpt = 1;
1454
1455 // Empty pre-order array
1456 allocate_preorders();
1457
1458 // Build a loop tree on the fly. Build a mapping from CFG nodes to
1459 // IdealLoopTree entries. Data nodes are NOT walked.
1460 build_loop_tree();
1461 // Check for bailout, and return
1462 if (C->failing()) {
1463 return;
1464 }
1465
1466 // No loops after all
1467 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
1468
1469 // There should always be an outer loop containing the Root and Return nodes.
1470 // If not, we have a degenerate empty program. Bail out in this case.
1471 if (!has_node(C->root())) {
1472 if (!_verify_only) {
1473 C->clear_major_progress();
1474 C->record_method_not_compilable("empty program detected during loop optimization");
1475 }
1476 return;
1477 }
1478
1479 // Nothing to do, so get out
1480 if( !C->has_loops() && !do_split_ifs && !_verify_me && !_verify_only ) {
1481 _igvn.optimize(); // Cleanup NeverBranches
1482 return;
1483 }
1484
1485 // Set loop nesting depth
1486 _ltree_root->set_nest( 0 );
1487
1488 // Split shared headers and insert loop landing pads.
1489 // Do not bother doing this on the Root loop of course.
1490 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
1491 if( _ltree_root->_child->beautify_loops( this ) ) {
1492 // Re-build loop tree!
1493 _ltree_root->_child = NULL;
1494 _nodes.clear();
1495 reallocate_preorders();
1496 build_loop_tree();
1497 // Check for bailout, and return
1498 if (C->failing()) {
1499 return;
1500 }
1501 // Reset loop nesting depth
1502 _ltree_root->set_nest( 0 );
1503
1504 C->print_method("After beautify loops", 3);
1505 }
1506 }
1507
1508 // Build Dominators for elision of NULL checks & loop finding.
1509 // Since nodes do not have a slot for immediate dominator, make
1510 // a persistent side array for that info indexed on node->_idx.
1511 _idom_size = C->unique();
1512 _idom = NEW_RESOURCE_ARRAY( Node*, _idom_size );
1513 _dom_depth = NEW_RESOURCE_ARRAY( uint, _idom_size );
1514 _dom_stk = NULL; // Allocated on demand in recompute_dom_depth
1515 memset( _dom_depth, 0, _idom_size * sizeof(uint) );
1516
1517 Dominators();
1518
1519 if (!_verify_only) {
1520 // As a side effect, Dominators removed any unreachable CFG paths
1521 // into RegionNodes. It doesn't do this test against Root, so
1522 // we do it here.
1523 for( uint i = 1; i < C->root()->req(); i++ ) {
1524 if( !_nodes[C->root()->in(i)->_idx] ) { // Dead path into Root?
1525 _igvn.hash_delete(C->root());
1526 C->root()->del_req(i);
1527 _igvn._worklist.push(C->root());
1528 i--; // Rerun same iteration on compressed edges
1529 }
1530 }
1531
1532 // Given dominators, try to find inner loops with calls that must
1533 // always be executed (call dominates loop tail). These loops do
1534 // not need a separate safepoint.
1535 Node_List cisstack(a);
1536 _ltree_root->check_safepts(visited, cisstack);
1537 }
1538
1539 // Walk the DATA nodes and place into loops. Find earliest control
1540 // node. For CFG nodes, the _nodes array starts out and remains
1541 // holding the associated IdealLoopTree pointer. For DATA nodes, the
1542 // _nodes array holds the earliest legal controlling CFG node.
1543
1544 // Allocate stack with enough space to avoid frequent realloc
1545 int stack_size = (C->unique() >> 1) + 16; // (unique>>1)+16 from Java2D stats
1546 Node_Stack nstack( a, stack_size );
1547
1548 visited.Clear();
1549 Node_List worklist(a);
1550 // Don't need C->root() on worklist since
1551 // it will be processed among C->top() inputs
1552 worklist.push( C->top() );
1553 visited.set( C->top()->_idx ); // Set C->top() as visited now
1554 build_loop_early( visited, worklist, nstack );
1555
1556 // Given early legal placement, try finding counted loops. This placement
1557 // is good enough to discover most loop invariants.
1558 if( !_verify_me && !_verify_only )
1559 _ltree_root->counted_loop( this );
1560
1561 // Find latest loop placement. Find ideal loop placement.
1562 visited.Clear();
1563 init_dom_lca_tags();
1564 // Need C->root() on worklist when processing outs
1565 worklist.push( C->root() );
1566 NOT_PRODUCT( C->verify_graph_edges(); )
1567 worklist.push( C->top() );
1568 build_loop_late( visited, worklist, nstack );
1569
1570 if (_verify_only) {
1571 // restore major progress flag
1572 for (int i = 0; i < old_progress; i++)
1573 C->set_major_progress();
1574 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
1575 assert(_igvn._worklist.size() == 0, "shouldn't push anything");
1576 return;
1577 }
1578
1579 // clear out the dead code
1580 while(_deadlist.size()) {
1581 _igvn.remove_globally_dead_node(_deadlist.pop());
1582 }
1583
1584 #ifndef PRODUCT
1585 C->verify_graph_edges();
1586 if( _verify_me ) { // Nested verify pass?
1587 // Check to see if the verify mode is broken
1588 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
1589 return;
1590 }
1591 if( VerifyLoopOptimizations ) verify();
1592 #endif
1593
1594 if (ReassociateInvariants) {
1595 // Reassociate invariants and prep for split_thru_phi
1596 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1597 IdealLoopTree* lpt = iter.current();
1598 if (!lpt->is_counted() || !lpt->is_inner()) continue;
1599
1600 lpt->reassociate_invariants(this);
1601
1602 // Because RCE opportunities can be masked by split_thru_phi,
1603 // look for RCE candidates and inhibit split_thru_phi
1604 // on just their loop-phi's for this pass of loop opts
1605 if( SplitIfBlocks && do_split_ifs ) {
1606 if (lpt->policy_range_check(this)) {
1673
1674 if (C->log() != NULL) {
1675 log_loop_tree(_ltree_root, _ltree_root, C->log());
1676 }
1677 }
1678
1679 #ifndef PRODUCT
1680 //------------------------------print_statistics-------------------------------
1681 int PhaseIdealLoop::_loop_invokes=0;// Count of PhaseIdealLoop invokes
1682 int PhaseIdealLoop::_loop_work=0; // Sum of PhaseIdealLoop x unique
1683 void PhaseIdealLoop::print_statistics() {
1684 tty->print_cr("PhaseIdealLoop=%d, sum _unique=%d", _loop_invokes, _loop_work);
1685 }
1686
1687 //------------------------------verify-----------------------------------------
1688 // Build a verify-only PhaseIdealLoop, and see that it agrees with me.
1689 static int fail; // debug only, so its multi-thread dont care
1690 void PhaseIdealLoop::verify() const {
1691 int old_progress = C->major_progress();
1692 ResourceMark rm;
1693 PhaseIdealLoop loop_verify( _igvn, this );
1694 VectorSet visited(Thread::current()->resource_area());
1695
1696 fail = 0;
1697 verify_compare( C->root(), &loop_verify, visited );
1698 assert( fail == 0, "verify loops failed" );
1699 // Verify loop structure is the same
1700 _ltree_root->verify_tree(loop_verify._ltree_root, NULL);
1701 // Reset major-progress. It was cleared by creating a verify version of
1702 // PhaseIdealLoop.
1703 for( int i=0; i<old_progress; i++ )
1704 C->set_major_progress();
1705 }
1706
1707 //------------------------------verify_compare---------------------------------
1708 // Make sure me and the given PhaseIdealLoop agree on key data structures
1709 void PhaseIdealLoop::verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const {
1710 if( !n ) return;
1711 if( visited.test_set( n->_idx ) ) return;
1712 if( !_nodes[n->_idx] ) { // Unreachable
1713 assert( !loop_verify->_nodes[n->_idx], "both should be unreachable" );
2133 // is a member of some outer enclosing loop. Since there are no
2134 // shared headers (I've split them already) I only need to go up
2135 // at most 1 level.
2136 while( l && l->_head == m ) // Successor heads loop?
2137 l = l->_parent; // Move up 1 for me
2138 // If this loop is not properly parented, then this loop
2139 // has no exit path out, i.e. its an infinite loop.
2140 if( !l ) {
2141 // Make loop "reachable" from root so the CFG is reachable. Basically
2142 // insert a bogus loop exit that is never taken. 'm', the loop head,
2143 // points to 'n', one (of possibly many) fall-in paths. There may be
2144 // many backedges as well.
2145
2146 // Here I set the loop to be the root loop. I could have, after
2147 // inserting a bogus loop exit, restarted the recursion and found my
2148 // new loop exit. This would make the infinite loop a first-class
2149 // loop and it would then get properly optimized. What's the use of
2150 // optimizing an infinite loop?
2151 l = _ltree_root; // Oops, found infinite loop
2152
2153 if (!_verify_only) {
2154 // Insert the NeverBranch between 'm' and it's control user.
2155 NeverBranchNode *iff = new (C, 1) NeverBranchNode( m );
2156 _igvn.register_new_node_with_optimizer(iff);
2157 set_loop(iff, l);
2158 Node *if_t = new (C, 1) CProjNode( iff, 0 );
2159 _igvn.register_new_node_with_optimizer(if_t);
2160 set_loop(if_t, l);
2161
2162 Node* cfg = NULL; // Find the One True Control User of m
2163 for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) {
2164 Node* x = m->fast_out(j);
2165 if (x->is_CFG() && x != m && x != iff)
2166 { cfg = x; break; }
2167 }
2168 assert(cfg != NULL, "must find the control user of m");
2169 uint k = 0; // Probably cfg->in(0)
2170 while( cfg->in(k) != m ) k++; // But check incase cfg is a Region
2171 cfg->set_req( k, if_t ); // Now point to NeverBranch
2172
2173 // Now create the never-taken loop exit
2174 Node *if_f = new (C, 1) CProjNode( iff, 1 );
2175 _igvn.register_new_node_with_optimizer(if_f);
2176 set_loop(if_f, l);
2177 // Find frame ptr for Halt. Relies on the optimizer
2178 // V-N'ing. Easier and quicker than searching through
2179 // the program structure.
2180 Node *frame = new (C, 1) ParmNode( C->start(), TypeFunc::FramePtr );
2181 _igvn.register_new_node_with_optimizer(frame);
2182 // Halt & Catch Fire
2183 Node *halt = new (C, TypeFunc::Parms) HaltNode( if_f, frame );
2184 _igvn.register_new_node_with_optimizer(halt);
2185 set_loop(halt, l);
2186 C->root()->add_req(halt);
2187 }
2188 set_loop(C->root(), _ltree_root);
2189 }
2190 }
2191 // Weeny check for irreducible. This child was already visited (this
2192 // IS the post-work phase). Is this child's loop header post-visited
2193 // as well? If so, then I found another entry into the loop.
2194 if (!_verify_only) {
2195 while( is_postvisited(l->_head) ) {
2196 // found irreducible
2197 l->_irreducible = 1; // = true
2198 l = l->_parent;
2199 _has_irreducible_loops = true;
2200 // Check for bad CFG here to prevent crash, and bailout of compile
2201 if (l == NULL) {
2202 C->record_method_not_compilable("unhandled CFG detected during loop optimization");
2203 return pre_order;
2204 }
2205 }
2206 }
2207
2208 // This Node might be a decision point for loops. It is only if
2209 // it's children belong to several different loops. The sort call
2210 // does a trivial amount of work if there is only 1 child or all
2211 // children belong to the same loop. If however, the children
2212 // belong to different loops, the sort call will properly set the
2213 // _parent pointers to show how the loops nest.
2214 //
2215 // In any case, it returns the tightest enclosing loop.
2216 innermost = sort( l, innermost );
2217 }
2218
2219 // Def-use info will have some dead stuff; dead stuff will have no
2220 // loop decided on.
2221
2222 // Am I a loop header? If so fix up my parent's child and next ptrs.
2223 if( innermost && innermost->_head == n ) {
2224 assert( get_loop(n) == innermost, "" );
2225 IdealLoopTree *p = innermost->_parent;
2226 IdealLoopTree *l = innermost;
2252 } else if( n->is_Allocate() && n->as_Allocate()->_is_scalar_replaceable ) {
2253 // Disable loop optimizations if the loop has a scalar replaceable
2254 // allocation. This disabling may cause a potential performance lost
2255 // if the allocation is not eliminated for some reason.
2256 innermost->_allow_optimizations = false;
2257 innermost->_has_call = 1; // = true
2258 }
2259 }
2260 }
2261
2262 // Flag as post-visited now
2263 set_postvisited(n);
2264 return pre_order;
2265 }
2266
2267
2268 //------------------------------build_loop_early-------------------------------
2269 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2270 // First pass computes the earliest controlling node possible. This is the
2271 // controlling input with the deepest dominating depth.
2272 void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
2273 while (worklist.size() != 0) {
2274 // Use local variables nstack_top_n & nstack_top_i to cache values
2275 // on nstack's top.
2276 Node *nstack_top_n = worklist.pop();
2277 uint nstack_top_i = 0;
2278 //while_nstack_nonempty:
2279 while (true) {
2280 // Get parent node and next input's index from stack's top.
2281 Node *n = nstack_top_n;
2282 uint i = nstack_top_i;
2283 uint cnt = n->req(); // Count of inputs
2284 if (i == 0) { // Pre-process the node.
2285 if( has_node(n) && // Have either loop or control already?
2286 !has_ctrl(n) ) { // Have loop picked out already?
2287 // During "merge_many_backedges" we fold up several nested loops
2288 // into a single loop. This makes the members of the original
2289 // loop bodies pointing to dead loops; they need to move up
2290 // to the new UNION'd larger loop. I set the _head field of these
2291 // dead loops to NULL and the _parent field points to the owning
2292 // loop. Shades of UNION-FIND algorithm.
2293 IdealLoopTree *ilt;
2294 while( !(ilt = get_loop(n))->_head ) {
2295 // Normally I would use a set_loop here. But in this one special
2296 // case, it is legal (and expected) to change what loop a Node
2297 // belongs to.
2298 _nodes.map(n->_idx, (Node*)(ilt->_parent) );
2299 }
2300 // Remove safepoints ONLY if I've already seen I don't need one.
2301 // (the old code here would yank a 2nd safepoint after seeing a
2302 // first one, even though the 1st did not dominate in the loop body
2303 // and thus could be avoided indefinitely)
2304 if( !_verify_only && !_verify_me && ilt->_has_sfpt && n->Opcode() == Op_SafePoint &&
2305 is_deleteable_safept(n)) {
2306 Node *in = n->in(TypeFunc::Control);
2307 lazy_replace(n,in); // Pull safepoint now
2308 // Carry on with the recursion "as if" we are walking
2309 // only the control input
2310 if( !visited.test_set( in->_idx ) ) {
2311 worklist.push(in); // Visit this guy later, using worklist
2312 }
2313 // Get next node from nstack:
2314 // - skip n's inputs processing by setting i > cnt;
2315 // - we also will not call set_early_ctrl(n) since
2316 // has_node(n) == true (see the condition above).
2317 i = cnt + 1;
2318 }
2319 }
2320 } // if (i == 0)
2321
2322 // Visit all inputs
2323 bool done = true; // Assume all n's inputs will be processed
2324 while (i < cnt) {
2407 d1 = dom_depth(n1);
2408 d2 = dom_depth(n2);
2409 }
2410 }
2411 return n1;
2412 }
2413
2414 //------------------------------compute_idom-----------------------------------
2415 // Locally compute IDOM using dom_lca call. Correct only if the incoming
2416 // IDOMs are correct.
2417 Node *PhaseIdealLoop::compute_idom( Node *region ) const {
2418 assert( region->is_Region(), "" );
2419 Node *LCA = NULL;
2420 for( uint i = 1; i < region->req(); i++ ) {
2421 if( region->in(i) != C->top() )
2422 LCA = dom_lca( LCA, region->in(i) );
2423 }
2424 return LCA;
2425 }
2426
2427 bool PhaseIdealLoop::verify_dominance(Node* n, Node* use, Node* LCA, Node* early) {
2428 bool had_error = false;
2429 #ifdef ASSERT
2430 if (early != C->root()) {
2431 // Make sure that there's a dominance path from use to LCA
2432 Node* d = use;
2433 while (d != LCA) {
2434 d = idom(d);
2435 if (d == C->root()) {
2436 tty->print_cr("*** Use %d isn't dominated by def %s", use->_idx, n->_idx);
2437 n->dump();
2438 use->dump();
2439 had_error = true;
2440 break;
2441 }
2442 }
2443 }
2444 #endif
2445 return had_error;
2446 }
2447
2448
2449 Node* PhaseIdealLoop::compute_lca_of_uses(Node* n, Node* early, bool verify) {
2450 // Compute LCA over list of uses
2451 bool had_error = false;
2452 Node *LCA = NULL;
2453 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && LCA != early; i++) {
2454 Node* c = n->fast_out(i);
2455 if (_nodes[c->_idx] == NULL)
2456 continue; // Skip the occasional dead node
2457 if( c->is_Phi() ) { // For Phis, we must land above on the path
2458 for( uint j=1; j<c->req(); j++ ) {// For all inputs
2459 if( c->in(j) == n ) { // Found matching input?
2460 Node *use = c->in(0)->in(j);
2461 if (_verify_only && use->is_top()) continue;
2462 LCA = dom_lca_for_get_late_ctrl( LCA, use, n );
2463 if (verify) had_error = verify_dominance(n, use, LCA, early) || had_error;
2464 }
2465 }
2466 } else {
2467 // For CFG data-users, use is in the block just prior
2468 Node *use = has_ctrl(c) ? get_ctrl(c) : c->in(0);
2469 LCA = dom_lca_for_get_late_ctrl( LCA, use, n );
2470 if (verify) had_error = verify_dominance(n, use, LCA, early) || had_error;
2471 }
2472 }
2473 assert(!had_error, "bad dominance");
2474 return LCA;
2475 }
2476
2477 //------------------------------get_late_ctrl----------------------------------
2478 // Compute latest legal control.
2479 Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
2480 assert(early != NULL, "early control should not be NULL");
2481
2482 Node* LCA = compute_lca_of_uses(n, early);
2483 #ifdef ASSERT
2484 if (LCA == C->root() && LCA != early) {
2485 // def doesn't dominate uses so print some useful debugging output
2486 compute_lca_of_uses(n, early, true);
2487 }
2488 #endif
2489
2490 // if this is a load, check for anti-dependent stores
2491 // We use a conservative algorithm to identify potential interfering
2492 // instructions and for rescheduling the load. The users of the memory
2493 // input of this load are examined. Any use which is not a load and is
2494 // dominated by early is considered a potentially interfering store.
2495 // This can produce false positives.
2496 if (n->is_Load() && LCA != early) {
2497 Node_List worklist;
2498
2499 Node *mem = n->in(MemNode::Memory);
2500 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
2501 Node* s = mem->fast_out(i);
2502 worklist.push(s);
2503 }
2504 while(worklist.size() != 0 && LCA != early) {
2505 Node* s = worklist.pop();
2506 if (s->is_Load()) {
2507 continue;
2508 } else if (s->is_MergeMem()) {
2509 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
2613 }
2614
2615 //------------------------------clear_dom_lca_tags------------------------------
2616 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
2617 // Intended use does not involve any growth for the array, so it could
2618 // be of fixed size.
2619 void PhaseIdealLoop::clear_dom_lca_tags() {
2620 uint limit = C->unique() + 1;
2621 _dom_lca_tags.map( limit, NULL );
2622 _dom_lca_tags.clear();
2623 #ifdef ASSERT
2624 for( uint i = 0; i < limit; ++i ) {
2625 assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
2626 }
2627 #endif // ASSERT
2628 }
2629
2630 //------------------------------build_loop_late--------------------------------
2631 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2632 // Second pass finds latest legal placement, and ideal loop placement.
2633 void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
2634 while (worklist.size() != 0) {
2635 Node *n = worklist.pop();
2636 // Only visit once
2637 if (visited.test_set(n->_idx)) continue;
2638 uint cnt = n->outcnt();
2639 uint i = 0;
2640 while (true) {
2641 assert( _nodes[n->_idx], "no dead nodes" );
2642 // Visit all children
2643 if (i < cnt) {
2644 Node* use = n->raw_out(i);
2645 ++i;
2646 // Check for dead uses. Aggressively prune such junk. It might be
2647 // dead in the global sense, but still have local uses so I cannot
2648 // easily call 'remove_dead_node'.
2649 if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
2650 // Due to cycles, we might not hit the same fixed point in the verify
2651 // pass as we do in the regular pass. Instead, visit such phis as
2652 // simple uses of the loop head.
2653 if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
2654 if( !visited.test(use->_idx) )
2655 worklist.push(use);
2656 } else if( !visited.test_set(use->_idx) ) {
2657 nstack.push(n, i); // Save parent and next use's index.
2658 n = use; // Process all children of current use.
2659 cnt = use->outcnt();
2660 i = 0;
2661 }
2662 } else {
2663 // Do not visit around the backedge of loops via data edges.
2664 // push dead code onto a worklist
2665 _deadlist.push(use);
2666 }
2667 } else {
2668 // All of n's children have been processed, complete post-processing.
2669 build_loop_late_post(n);
2670 if (nstack.is_empty()) {
2671 // Finished all nodes on stack.
2672 // Process next node on the worklist.
2673 break;
2674 }
2675 // Get saved parent node and next use's index. Visit the rest of uses.
2676 n = nstack.node();
2677 cnt = n->outcnt();
2678 i = nstack.index();
2679 nstack.pop();
2680 }
2681 }
2682 }
2683 }
2684
2685 //------------------------------build_loop_late_post---------------------------
2686 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2687 // Second pass finds latest legal placement, and ideal loop placement.
2688 void PhaseIdealLoop::build_loop_late_post( Node *n ) {
2689
2690 if (n->req() == 2 && n->Opcode() == Op_ConvI2L && !C->major_progress() && !_verify_only) {
2691 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops.
2692 }
2693
2694 // CFG and pinned nodes already handled
2695 if( n->in(0) ) {
2696 if( n->in(0)->is_top() ) return; // Dead?
2697
2698 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
2699 // _must_ be pinned (they have to observe their control edge of course).
2700 // Unlike Stores (which modify an unallocable resource, the memory
2701 // state), Mods/Loads can float around. So free them up.
2702 bool pinned = true;
2703 switch( n->Opcode() ) {
2704 case Op_DivI:
2705 case Op_DivF:
2706 case Op_DivD:
2707 case Op_ModI:
2708 case Op_ModF:
2709 case Op_ModD:
2710 case Op_LoadB: // Same with Loads; they can sink
2751 #ifdef ASSERT
2752 for (DUIterator i1 = n->outs(); n->has_out(i1); i1++) {
2753 assert( _nodes[n->out(i1)->_idx] == NULL, "all uses must also be dead");
2754 }
2755 #endif
2756 _nodes.map(n->_idx, 0); // This node is useless
2757 _deadlist.push(n);
2758 return;
2759 }
2760 assert(LCA != NULL && !LCA->is_top(), "no dead nodes");
2761
2762 Node *legal = LCA; // Walk 'legal' up the IDOM chain
2763 Node *least = legal; // Best legal position so far
2764 while( early != legal ) { // While not at earliest legal
2765 // Find least loop nesting depth
2766 legal = idom(legal); // Bump up the IDOM tree
2767 // Check for lower nesting depth
2768 if( get_loop(legal)->_nest < get_loop(least)->_nest )
2769 least = legal;
2770 }
2771 assert(early == legal || legal != C->root(), "bad dominance of inputs");
2772
2773 // Try not to place code on a loop entry projection
2774 // which can inhibit range check elimination.
2775 if (least != early) {
2776 Node* ctrl_out = least->unique_ctrl_out();
2777 if (ctrl_out && ctrl_out->is_CountedLoop() &&
2778 least == ctrl_out->in(LoopNode::EntryControl)) {
2779 Node* least_dom = idom(least);
2780 if (get_loop(least_dom)->is_member(get_loop(least))) {
2781 least = least_dom;
2782 }
2783 }
2784 }
2785
2786 #ifdef ASSERT
2787 // If verifying, verify that 'verify_me' has a legal location
2788 // and choose it as our location.
2789 if( _verify_me ) {
2790 Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
2791 Node *legal = LCA;
2792 while( early != legal ) { // While not at earliest legal
2793 if( legal == v_ctrl ) break; // Check for prior good location
2794 legal = idom(legal) ;// Bump up the IDOM tree
2795 }
2796 // Check for prior good location
2797 if( legal == v_ctrl ) least = legal; // Keep prior if found
2798 }
2799 #endif
2800
2801 // Assign discovered "here or above" point
2802 least = find_non_split_ctrl(least);
2803 set_ctrl(n, least);
2804
2805 // Collect inner loop bodies
2806 IdealLoopTree *chosen_loop = get_loop(least);
2807 if( !chosen_loop->_child ) // Inner loop?
2808 chosen_loop->_body.push(n);// Collect inner loops
2809 }
2810
|