Lines Matching refs:loop
42 // Determine if a node is Counted loop induction variable.
164 // Moving the node out of a loop on the projection of a If
165 // confuses loop predication. So once we hit a Loop in a If branch
167 // expensive nodes will notice the loop and skip over it to try to
264 bool PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) {
267 // Counted loop head must be a good RegionNode with only 3 not NULL
276 // Must also check for TOP when looking for a dead loop
284 // Controlling test for loop
289 // I have a weird back-control. Probably the loop-exit test is in
290 // the middle of the loop and I am looking at some trailing control-flow
291 // merge point. To fix this I would have to partially peel the loop.
294 // Get boolean guarding loop-back test
296 if (get_loop(iff) != loop || !iff->in(1)->is_Bool())
311 // Find the trip-counter increment & limit. Limit must be loop invariant.
316 // need 'loop()' test to tell if limit is loop invariant
319 if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?
325 if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant
327 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
337 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
370 // Phi must be of loop header; backedge must wrap to increment
416 if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!
419 // Count down loop rolls through MAXINT
421 // Count up loop rolls through MININT
432 return false; // cyclic loop or this loop trips only once
436 return false; // cyclic loop or this loop trips only once
450 // Generate loop limit check to avoid integer overflow
457 // Limit check predicate depends on the loop test:
488 // Generate loop's limit check.
489 // Loop limit check predicate should be near the loop.
495 tty->print("missing loop limit check:");
496 loop->dump_head();
530 // report that the loop predication has been actually performed
531 // for this loop
552 // Now we need to canonicalize loop condition.
603 //_loop.map(trip_count->_idx,loop(limit));
611 // Make the new limit be in the same loop nest as the old limit
615 if (stride_con < 0) // Count down loop rolls through MAXINT
641 // Make the new limit be in the same loop nest as the old limit
645 if (stride_con > 0) // count up loop rolls through MININT
679 if (loop->_safepts != NULL) {
680 loop->_safepts->yank(sfpt);
682 loop->_tail = iftrue;
722 set_idom(le, le->in(0), dd); // Update dominance for loop exit
723 set_loop(le, loop);
725 // Get the loop-exit control
728 // Need to swap loop-exit and loop-back control?
733 loop->_tail = back_control = ift2;
734 set_loop(ift2, loop);
761 // is not yet initialized for this loop and its parts.
764 set_loop(l, loop);
765 loop->_head = l;
766 // Fix all data nodes placed at the old loop head.
775 if (loop->_safepts != NULL) {
776 loop->_safepts->yank(sfpt2);
784 assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
785 assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
790 loop->dump_head();
800 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
801 assert(loop->_head->is_CountedLoop(), "");
802 CountedLoopNode *cl = loop->_head->as_CountedLoop();
808 // Loop limit is exact with stride == 1. And loop may already have exact limit.
817 // Simple case: loop has constant boundaries.
825 // The final value should be in integer range since the loop
840 // Attempt to convert into a counted-loop.
852 // Attempt to convert into a counted-loop.
899 // The final value should be in integer range since the loop
923 // Delay following optimizations until all loop optimizations
972 // we can get situation when init > limit. Note, for the empty loop
1069 // phi( , ) -- at top of loop type is [min_int..10)
1172 // Set loop tree nesting depth. Accumulate _has_call bits.
1183 // Split out multiple fall-in edges from the loop header. Move them to a
1184 // private RegionNode before the loop. This becomes the loop landing pad.
1216 // loop hackery and we need to be a little incremental
1229 // Phi is the loop limit and prevents recognizing a CountedLoop
1230 // which in turn prevents removing an empty loop.
1266 // Split out the outermost loop from this shared header.
1270 // Find index of outermost loop; it should also be my tail.
1274 // Make a LoopNode for the outermost loop.
1280 // Outermost loop falls into '_head' loop
1283 // Split all the Phis up between '_head' loop and 'outer' loop.
1299 // Use the new loop head instead of the old shared one
1305 static void fix_parent( IdealLoopTree *loop, IdealLoopTree *parent ) {
1306 loop->_parent = parent;
1307 if( loop->_child ) fix_parent( loop->_child, loop );
1308 if( loop->_next ) fix_parent( loop->_next , parent );
1351 // Skip through never-taken branch; look for a real loop exit.
1359 // Feed that region as the one backedge to this loop.
1379 // See if the hottest backedge is worthy of being an inner loop
1397 // Plug region into end of loop _head, followed by hot_tail
1402 // Split all the Phis up between '_head' loop and the Region 'r'
1428 // of self loop tree. Turn self into a loop headed by _head and with
1439 // Starting with 'ilt', look for child loop trees using the same shared
1447 break; // Still a loop
1448 if( i == _head->req() ) { // No longer a loop
1455 ilt->_head = NULL; // Flag as a loop UNIONED into parent
1459 assert( ilt->_tail == hot_tail, "expected to only find the hot inner loop here" );
1470 // Split shared headers and insert loop landing pads.
1472 // Return TRUE if loop tree is structurally changed.
1486 if( fall_in_cnt > 1 ) // Need a loop landing pad to merge fall-ins
1511 assert( phase->is_member( this, _head->in(2) ), "right edge is loop" );
1523 // If I have one hot backedge, peel off myself loop.
1524 // I better be the outermost loop.
1530 // Make a new LoopNode to replace the old loop head
1547 // Allpaths backwards scan from loop tail, terminating each path at first safepoint
1580 // executed (call dominates loop tail). These loops do not need non-call
1583 // A complication is that a safepoint in a inner loop may be needed
1584 // by an outer loop. In the following, the inner loop sees it has a
1587 // in block 2, _but_ this leaves the outer loop without a safepoint.
1605 // be protected is created for each loop. When a ncsfpt maybe deleted, it
1606 // is first looked for in the lists for the outer loops of the current loop.
1610 // B) innermost loops are okay (only an inner loop can delete
1611 // a ncsfpt needed by an outer loop)
1612 // C) a loop is immune from an inner loop deleting a safepoint
1613 // if the loop has a call on the idom-path
1614 // D) a loop is also immune if it has a ncsfpt (non-call safepoint) on the
1615 // idom-path that is not in a nested loop
1617 // loop needs to be prevented from deletion by an inner loop
1620 // 1) The first, and cheaper one, scans the loop body from
1625 // when the tail of an inner loop is encountered.
1640 bool has_local_ncsfpt = false; // ncsfpt on dom-path at this loop depth
1659 // If at an inner loop tail, see if the inner loop has already
1661 // jump to the head of the inner loop.
1662 assert(is_member(nlpt), "nested loop");
1666 // If inner loop has call on dom-path, so does outer loop
1672 // Skip to head of inner loop
1679 // Record safept's that this loop needs preserved when an
1680 // inner loop attempts to delete it's safepoints.
1695 // Is safept not required by an outer loop?
1714 void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) {
1715 assert(loop->_head->is_CountedLoop(), "");
1716 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1718 return; // skip malformed counted loop
1721 return; // Dead loop?
1735 if (phi2->region() != loop->_head ||
1753 // GCD for the loop. Then all possible IVs are simple multiples of
1764 loop->dump_head();
1768 // variable differs from the trip counter by a loop-invariant
1800 // For grins, set the inner-loop flag here
1825 // Not a counted loop.
1832 // Delete other safepoints in this loop.
1852 // Dump 1 liner for loop header info
1900 // Dump loops by loop tree
1909 static void log_loop_tree(IdealLoopTree* root, IdealLoopTree* loop, CompileLog* log) {
1910 if (loop == root) {
1911 if (loop->_child != NULL) {
1914 if( loop->_child ) log_loop_tree(root, loop->_child, log);
1916 assert(loop->_next == NULL, "what?");
1919 Node* head = loop->_head;
1920 log->begin_head("loop");
1922 if (loop->_irreducible) log->print("irreducible='1' ");
1934 if( loop->_child ) log_loop_tree(root, loop->_child, log);
1935 log->tail("loop");
1936 if( loop->_next ) log_loop_tree(root, loop->_next, log);
1944 IdealLoopTree * loop, Unique_Node_List &useful_predicates) {
1945 if (loop->_child) { // child
1946 collect_potentially_useful_predicates(loop->_child, useful_predicates);
1949 // self (only loops that we can apply loop predication may use their predicates)
1950 if (loop->_head->is_Loop() &&
1951 !loop->_irreducible &&
1952 !loop->tail()->is_top()) {
1953 LoopNode* lpn = loop->_head->as_Loop();
1956 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication
1967 if (loop->_next) { // sibling
1968 collect_potentially_useful_predicates(loop->_next, useful_predicates);
1973 // Eliminate all inserted predicates if they could not be used by loop predication.
1974 // Note: it will also eliminates loop limits check predicate since it also uses
2037 // branch. See whether we can exit the loop and move above the
2089 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
2106 // True if the method has at least 1 irreducible loop
2117 // Pre-build the top-level outermost loop tree entry
2132 // Build a loop tree on the fly. Build a mapping from CFG nodes to
2143 // There should always be an outer loop containing the Root and Return nodes.
2148 C->record_method_not_compilable("empty program detected during loop optimization");
2161 // Set loop nesting depth
2164 // Split shared headers and insert loop landing pads.
2165 // Do not bother doing this on the Root loop of course.
2169 // Re-build loop tree!
2178 // Reset loop nesting depth
2185 // Build Dominators for elision of NULL checks & loop finding.
2208 // always be executed (call dominates loop tail). These loops do
2232 // is good enough to discover most loop invariants.
2236 // Find latest loop placement. Find ideal loop placement.
2272 // Some parser-inserted loop predicates could never be used by loop
2273 // predication or they were moved away from loop during some optimizations.
2274 // For example, peeling. Eliminate them before next loop optimizations.
2312 // on just their loop-phi's for this pass of loop opts
2333 // Perform loop predication before iteration splitting
2348 // then do loop opts.
2352 // No verify after peeling! GCM has hoisted code out of the loop.
2372 // Repeat loop optimizations if new loops were seen
2377 // Keep loop predicates and perform optimizations with them
2378 // until no more loop optimizations could be done.
2379 // After that switch predicates off and do more loop optimizations.
2390 // Convert scalar to superword operations at the end of all loop opts.
2434 // Verify loop structure is the same
2456 // Check the '_nodes' block/loop structure
2458 if( has_ctrl(n) ) { // We have control; verify has loop or ctrl
2475 } else { // We have a loop
2478 tty->print("Mismatched loop setting for: ");
2530 // within the loop tree can be reordered. We attempt to deal with that by
2531 // reordering the verify's loop tree if possible.
2532 void IdealLoopTree::verify_tree(IdealLoopTree *loop, const IdealLoopTree *parent) const {
2533 assert( _parent == parent, "Badly formed loop tree" );
2536 if( _head != loop->_head ) {
2538 IdealLoopTree **pp = &loop->_parent->_child;
2539 while( *pp != loop )
2542 IdealLoopTree **nn = &loop->_next;
2549 // after a major_progress operation, so the rest of the loop
2552 assert( 0, "failed to match loop tree" );
2558 hit->_next = loop;
2559 *pp = loop;
2560 loop = hit;
2564 assert( _head == loop->_head , "mismatched loop head" );
2568 assert( tail == loop->_tail, "mismatched loop tail" );
2595 if (_child != NULL) _child->verify_tree(loop->_child, this);
2596 if (_next != NULL) _next ->verify_tree(loop->_next, parent);
2597 // Innermost loops need to verify loop bodies,
2605 for( j = 0; j < loop->_body.size(); j++ )
2606 if( loop->_body.at(j) == n )
2608 if( j == loop->_body.size() ) { // Not found in loop body
2619 for( uint i2 = 0; i2 < loop->_body.size(); i2++ ) {
2620 Node *n = loop->_body.at(i2);
2626 if( j == _body.size() ) { // Not found in loop body
2637 assert( !fail, "loop body mismatch" );
2699 // Insert 'loop' into the existing loop tree. 'innermost' is a leaf of the
2700 // loop tree, not the root.
2701 IdealLoopTree *PhaseIdealLoop::sort( IdealLoopTree *loop, IdealLoopTree *innermost ) {
2702 if( !innermost ) return loop; // New innermost loop
2704 int loop_preorder = get_preorder(loop->_head); // Cache pre-order number
2705 assert( loop_preorder, "not yet post-walked loop" );
2711 if( l == loop ) return innermost; // Already on list!
2723 get_preorder(loop->_tail) < get_preorder(l->_tail) )
2730 *pp = loop;
2732 IdealLoopTree *p = loop->_parent;
2733 loop->_parent = l; // Point me to successor
2745 // a loop backedge with that doesn't have any work on the backedge. This
2749 // I check to see if there is a backedge. Backedges define a loop! I
2754 // where control flow can choose to change loop nests. It is at this
2756 // time I can properly order the different loop nests from my children.
2761 // I need to inspect loop header pre-order numbers to properly nest my
2782 // Scan first over control projections that lead to loop headers.
2785 // Scan children's children for loop headers.
2789 // Scan over children's children to find loop
2839 // Tightest enclosing loop for this Node
2842 // For all children, see if any edge is a backedge. If so, make a loop
2843 // for it. Then find the tightest enclosing loop for the self Node.
2849 IdealLoopTree *l; // Child's loop
2857 } else { // Else found a nested loop
2858 // Insert a LoopNode to mark this loop.
2860 } // End of Else found a nested loop
2861 if( !has_loop(m) ) // If 'm' does not already have a loop set
2862 set_loop(m, l); // Set loop header to loop now
2864 } else { // Else not a nested loop
2865 if( !_nodes[m->_idx] ) continue; // Dead code has no loop
2866 l = get_loop(m); // Get previously determined loop
2867 // If successor is header of a loop (nest), move up-loop till it
2868 // is a member of some outer enclosing loop. Since there are no
2871 while( l && l->_head == m ) // Successor heads loop?
2873 // If this loop is not properly parented, then this loop
2874 // has no exit path out, i.e. its an infinite loop.
2876 // Make loop "reachable" from root so the CFG is reachable. Basically
2877 // insert a bogus loop exit that is never taken. 'm', the loop head,
2881 // Here I set the loop to be the root loop. I could have, after
2882 // inserting a bogus loop exit, restarted the recursion and found my
2883 // new loop exit. This would make the infinite loop a first-class
2884 // loop and it would then get properly optimized. What's the use of
2885 // optimizing an infinite loop?
2886 l = _ltree_root; // Oops, found infinite loop
2908 // Now create the never-taken loop exit
2927 // IS the post-work phase). Is this child's loop header post-visited
2928 // as well? If so, then I found another entry into the loop.
2937 C->record_method_not_compilable("unhandled CFG detected during loop optimization");
2946 // children belong to the same loop. If however, the children
2950 // In any case, it returns the tightest enclosing loop.
2955 // loop decided on.
2957 // Am I a loop header? If so fix up my parent's child and next ptrs.
2973 // Record tightest enclosing loop for self. Mark as post-visited.
2989 // Disable loop optimizations if the loop has a scalar replaceable
2995 // Record all safepoints in this loop.
3009 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
3025 if( has_node(n) && // Have either loop or control already?
3026 !has_ctrl(n) ) { // Have loop picked out already?
3028 // into a single loop. This makes the members of the original
3029 // loop bodies pointing to dead loops; they need to move up
3030 // to the new UNION'd larger loop. I set the _head field of these
3032 // loop. Shades of UNION-FIND algorithm.
3036 // case, it is legal (and expected) to change what loop a Node
3042 // first one, even though the 1st did not dominate in the loop body
3374 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
3375 // Second pass finds latest legal placement, and ideal loop placement.
3395 // simple uses of the loop head.
3429 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
3430 // Second pass finds latest legal placement, and ideal loop placement.
3454 case Op_LoadUB: // during loop optimizations.
3476 if( !chosen_loop->_child ) // Inner loop?
3516 // Find least loop nesting depth
3524 // Try not to place code on a loop entry projection
3556 // Collect inner loop bodies
3558 if( !chosen_loop->_child ) // Inner loop?
3654 // Dump root loop indexed by last element in PO order
3658 void PhaseIdealLoop::dump( IdealLoopTree *loop, uint idx, Node_List &rpo_list ) const {
3659 loop->dump_head();
3661 // Now scan for CFG nodes in the same loop
3666 if( get_loop(n) != loop ) { // Wrong loop nest
3667 if( get_loop(n)->_head == n && // Found nested loop?
3668 get_loop(n)->_parent == loop )
3674 for( uint x = 0; x < loop->_nest; x++ )
3706 for( uint j = 0; j < loop->_nest; j++ )
3743 // Advance to next loop tree using a preorder, left-to-right traversal.