Lines Matching refs:loop
39 // Given an IfNode, return the loop-exiting projection or NULL if both
40 // arms remain in the loop.
44 // Test is an IfNode, has 2 projections. If BOTH are in the loop
45 // we need loop unswitching instead of peeling.
58 // Put loop body on igvn work list
67 // Compute loop exact trip count if possible. Do not recalculate trip count for
76 // it is used to limit unrolling of main loop.
79 // Loop's test should be part of loop.
81 return; // Infinite loop
107 // Compute loop trip count from profile data as
136 // Now compute a loop exit count
267 // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
268 // make some loop-invariant test (usually a null-check) happen before the loop.
273 // Peeling does loop cloning which can result in O(N^2) node construction
278 while( test != _head ) { // Scan till run off top of loop
283 // Standard IF only has one input value to check for loop invariance
285 // Condition is not a member of this loop?
290 // Walk up dominators to loop _head looking for test which is
291 // executed on every path thru loop.
299 // a pre-loop which must execute at least once, we can remove all
300 // loop-invariant dominated tests in the main body.
301 void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {
305 Node *prev = loop->_head->in(LoopNode::LoopBackControl);//loop->tail();
307 while( test != loop->_head ) { // Scan till run off top of loop
313 // Condition is not a member of this loop?
314 !loop->is_member(get_loop(get_ctrl(test->in(1))))){
315 // Walk loop body looking for instances of this test
316 for( uint i = 0; i < loop->_body.size(); i++ ) {
317 Node *n = loop->_body.at(i);
318 if( n->is_If() && n->in(1) == test->in(1) /*&& n != loop->tail()->in(0)*/ ) {
319 // IfNode was dominated by version in peeled loop body
327 } // End of scan tests in loop
333 // Peel the first iteration of the given loop.
334 // Step 1: Clone the loop body. The clone becomes the peeled iteration.
335 // The pre-loop illegally has 2 control users (old & new loops).
336 // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
337 // Do this by making the old-loop fall-in edges act as if they came
338 // around the loopback from the prior iteration (follow the old-loop
340 // the pre-loop with only 1 user (the new peeled iteration), but the
341 // peeled-loop backedge has 2 users.
342 // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
350 // loop predicate
353 // loop<----+
370 // after clone loop
375 // loop predicate
381 // +---->loop clone loop<----+
410 // / loop predicate |
413 // TOP-->loop clone loop<----+ |
450 // | loop predicate
453 // | loop<----+
470 void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {
473 // Peeling a 'main' loop in a pre/main/post situation obfuscates the
474 // 'pre' loop from the main and the 'pre' can no longer have it's
475 // iterations adjusted. Therefore, we need to declare this loop as
476 // no longer a 'main' loop; it will need new pre and post loops before
481 loop->dump_head();
484 Node* head = loop->_head;
488 assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
494 tty->print("Peeling a 'main' loop; resetting to 'normal' ");
495 loop->dump_head();
502 // Step 1: Clone the loop body. The clone becomes the peeled iteration.
503 // The pre-loop illegally has 2 control users (old & new loops).
504 clone_loop( loop, old_new, dom_depth(head) );
506 // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
507 // Do this by making the old-loop fall-in edges act as if they came
508 // around the loopback from the prior iteration (follow the old-loop
510 // the pre-loop with only 1 user (the new peeled iteration), but the
511 // peeled-loop backedge has 2 users.
517 if (old->in(0) == loop->_head && old->req() == 3 && old->is_Phi()) {
519 if (!new_exit_value ) // Backedge value is ALSO loop invariant?
520 // Then loop body backedge value remains the same.
528 // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
542 // Step 4: Correct dom-depth info. Set to loop-head depth.
545 for (uint j3 = 0; j3 < loop->_body.size(); j3++) {
546 Node *old = loop->_body.at(j3);
552 // Now force out all loop-invariant dominating tests. The optimizer
554 peeled_dom_test_elim(loop,old_new);
556 loop->record_for_igvn();
559 #define EMPTY_LOOP_SIZE 7 // number of nodes in an empty loop
562 // Calculate exact loop trip count and return true if loop can be maximally
568 return false; // Malformed counted loop
577 assert(trip_count > 1, "one iteration loop should be optimized out already");
581 // Allow the unrolled mess to get larger than standard loop
582 // size. After all, it will no longer be a loop.
590 // Fully unroll a loop with few iterations regardless next
591 // conditions since following loop optimizations will split
592 // such loop anyway (pre-main-post).
608 // Do not unroll a loop with String intrinsics code.
626 #define MAX_UNROLL 16 // maximum number of unrolls for main loop
629 // Return TRUE or FALSE if the loop should be unrolled or not. Unroll if
630 // the loop is a CountedLoop and the body is small enough.
637 return false; // Malformed counted loop
640 // After split at least one iteration will be executed in pre-loop.
650 // over the expected trip count of the loop. One is subtracted
651 // from the expected trip count because the pre-loop normally
681 assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");
707 // Key test to unroll loop in CRC32 java code
721 // Do not unroll a loop with String intrinsics code.
731 // Normal case: loop too big
740 // Return TRUE or FALSE if the loop should be cache-line aligned. Gather the
742 // aligned in a loop (unless the VM guarantees mutual alignment). Note that
750 // Return TRUE or FALSE if the loop should be range-check-eliminated.
757 // changed our minds, we got no pre-loop. Either we need to
758 // make a new pre-loop, or we gotta disallow RCE.
762 // Check loop body for tests of trip-counter plus loop-invariant vs
763 // loop-invariant.
792 continue; // Both inputs are loop varying; cannot RCE
799 // Test is an IfNode, has 2 projections. If BOTH are in the loop
800 // we need loop unswitching instead of iteration splitting.
810 // Return TRUE or FALSE if the loop should NEVER be RCE'd or aligned. Useful
839 assert(clones.find(n->_idx) == NULL, "dead loop");
852 assert(clones.find(n->_idx) == NULL, "dead loop");
869 // Insert pre and post loops. If peel_only is set, the pre-loop can not have
872 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
880 loop->dump_head();
885 // Find common pieces of the loop being guarded with pre & post loops
886 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
901 // Need only 1 user of 'bol' because I will be hacking the loop bounds.
909 // Need only 1 user of 'cmp' because I will be hacking the loop bounds.
923 // Step A1: Clone the loop body. The clone becomes the post-loop. The main
924 // loop pre-header illegally has 2 control users (old & new loops).
925 clone_loop( loop, old_new, dd_main_exit );
930 // Reduce the post-loop trip count.
934 // Build the main-loop normal exit.
938 set_loop(new_main_exit, loop->_parent);
940 // Step A2: Build a zero-trip guard for the post-loop. After leaving the
941 // main-loop, the post-loop may not execute at all. We 'opaque' the incr
942 // (the main-loop trip-counter exit value) because we will be changing
956 set_loop(zer_iff, loop->_parent);
958 // Plug in the false-path, taken if we need to skip post-loop
962 // Make the true-path, must enter the post loop
966 set_loop(zer_taken, loop->_parent);
975 // Step A3: Make the fall-in values to the post-loop come from the
976 // fall-out values of the main-loop.
997 // Step B1: Clone the loop body. The clone becomes the pre-loop. The main
998 // loop pre-header illegally has 2 control users (old & new loops).
999 clone_loop( loop, old_new, dd_main_head );
1005 // Reduce the pre-loop trip count.
1008 // Find the pre-loop normal exit.
1014 set_loop(new_pre_exit, loop->_parent);
1016 // Step B2: Build a zero-trip guard for the main-loop. After leaving the
1017 // pre-loop, the main-loop may not execute at all. Later in life this
1019 // the main-loop.
1027 // Build the IfNode (assume the main-loop is executed always).
1031 set_loop(min_iff, loop->_parent);
1033 // Plug in the false-path, taken if we need to skip main-loop
1038 // Make the true-path, must enter the main loop
1042 set_loop(min_taken, loop->_parent);
1050 // Step B3: Make the fall-in values to the main-loop come from the
1051 // fall-out values of the pre-loop.
1065 // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1071 // Save the original loop limit in this Opaque1 node for
1078 // Since no other users of pre-loop compare, I can hack limit directly
1083 // Special case for not-equal loop bounds:
1084 // Change pre loop test, main loop test, and the
1085 // main loop guard test to use lt or gt depending on stride
1090 // not-equal test is kept for post loop to handle case
1096 // Modify pre loop end condition
1102 // Modify main loop guard condition
1108 // Modify main loop end condition
1116 // Flag main loop
1120 // Subtract a trip count for the pre-loop.
1129 // Now force out all loop-invariant dominating tests. The optimizer
1131 peeled_dom_test_elim(loop,old_new);
1144 // Unroll the loop body one step - make each trip do 2 iterations.
1145 void PhaseIdealLoop::do_unroll( IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip ) {
1147 CountedLoopNode *loop_head = loop->_head->as_CountedLoop();
1153 loop->dump_head();
1160 loop->dump_head();
1164 // Remember loop node count before unrolling to detect
1166 loop_head->set_node_count_before_unroll(loop->_body.size());
1186 // optimized away and then another round of loop opts attempted.
1187 // We can not optimize this particular loop in that case.
1205 // Adjust loop limit to keep valid iterations number after unroll.
1213 // Loop's limit is constant. Loop's init could be constant when pre-loop
1216 // We can keep old loop limit if iterations count stays the same:
1234 // adjustment underflows or overflows, then the main loop is skipped.
1253 // variable from previous loop to avoid using pre-incremented
1257 // zero trip guard limit will be different from loop limit.
1312 // Replace in loop test.
1330 // Step 3: Find the min-trip test guaranteed before a 'main' loop.
1343 // the main, unrolled, part of the loop will never execute as it is protected
1345 // and later determined that part of the unrolled loop was dead.
1348 // Double the count of original iterations in the unrolled loop body.
1355 // the main, unrolled, part of the loop will never execute as it is protected
1357 // and later determined that part of the unrolled loop was dead.
1360 // Double the count of original iterations in the unrolled loop body.
1367 // We are going to double the loop body, so we want to knock off any
1391 // Step 3: Find the min-trip test guaranteed before a 'main' loop.
1405 // Step 4: Clone the loop body. Move it inside the loop. This loop body
1406 // represents the odd iterations; since the loop trips an even number of
1409 clone_loop( loop, old_new, dd );
1430 loop->_head = clone_head; // New loop header
1441 // Force clone into same loop body
1442 uint max = loop->_body.size();
1444 Node *old = loop->_body.at(k);
1446 loop->_body.push(nnn);
1448 set_loop(nnn, loop);
1451 loop->record_for_igvn();
1456 void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) {
1457 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1463 loop->dump_head();
1467 // If loop is tripping an odd number of times, peel odd iteration
1469 do_peeling(loop, old_new);
1472 // Now its tripping an even number of times remaining. Double loop body.
1476 do_unroll(loop, old_new, false);
1497 // Adjust loop limit
1506 // Constrain the main loop iterations so the conditions:
1509 // the pre-loop or the post-loop until the condition holds true in the main
1510 // loop. Stride, scale, offset and limit are all loop invariant. Further,
1513 // For positive stride, the pre-loop limit always uses a MAX function
1514 // and the main loop a MIN function. For negative stride these are
1518 // pre-loop must check for underflow and the post-loop for overflow.
1519 // Negative stride*scale reverses this; pre-loop checks for overflow and
1520 // post-loop for underflow.
1527 // For main-loop compute
1535 // But it is fine since main loop will either have
1540 // For pre-loop compute
1552 // due to underflow. So we need execute pre-loop until
1576 // For negative stride*scale pre-loop checks for overflow and
1577 // post-loop for underflow.
1580 // For pre-loop compute
1604 // due to underflow. So we need execute main-loop while
1622 // But it is fine since main loop will either have
1626 // For main-loop compute
1730 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1731 void PhaseIdealLoop::do_range_check( IdealLoopTree *loop, Node_List &old_new ) {
1735 loop->dump_head();
1738 loop->dump_head();
1742 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1751 // Find the main loop limit; we will trim it's iterations
1755 // Need to find the main-loop zero-trip guard
1765 // Can not optimize a loop if zero-trip Opaque1 node is optimized
1766 // away and then another round of loop opts attempted.
1771 // Find the pre-loop limit; we will expand it's iterations to
1778 // Occasionally it's possible for a pre-loop Opaque1 node to be
1779 // optimized away and then another round of loop opts attempted.
1780 // We can not optimize this particular loop in that case.
1789 // Ensure the original loop limit is available from the
1790 // pre-loop Opaque1 node.
1795 // Must know if its a count-up or count-down loop
1806 // Range checks that do not dominate the loop backedge (ie.
1807 // conditionally executed) can lengthen the pre loop limit beyond
1808 // the original loop limit. To prevent this, the pre limit is
1809 // (for stride > 0) MINed with the original loop limit (MAXed
1814 // Check loop body for tests of trip-counter plus loop-invariant vs
1815 // loop-invariant.
1816 for( uint i = 0; i < loop->_body.size(); i++ ) {
1817 Node *iff = loop->_body[i];
1820 // Test is an IfNode, has 2 projections. If BOTH are in the loop
1821 // we need loop unswitching instead of iteration splitting.
1822 Node *exit = loop->is_loop_exit(iff);
1844 if( loop->is_member(get_loop(limit_c) ) ) {
1850 if( loop->is_member(get_loop(limit_c) ) )
1851 continue; // Both inputs are loop varying; cannot RCE
1853 // Here we know 'limit' is loop invariant
1870 if( loop->is_member( get_loop(offset_c) ) )
1871 continue; // Offset is not really loop invariant
1872 // Here we know 'offset' is loop invariant.
1887 // where scale_con, offset and limit are loop invariant. Trip_counter
1892 // Adjust pre and main loop limits to guard the correct iteration set
1898 // (0-offset)/scale could be outside of loop iterations range.
1899 conditional_rc = !loop->dominates_backedge(iff) || RangeLimitCheck;
1933 // ((MIN_INT+1)-offset)/scale could be outside of loop iterations range.
1935 // still be outside of loop range.
1936 conditional_rc = !loop->dominates_backedge(iff) || RangeLimitCheck;
1959 if( cd->is_Load() ) { // Loads can now float around in the loop
1960 // Allow the load to float around in the loop, or before it
1961 // but NOT before the pre-loop.
1972 // Update loop limits
1981 // Note:: we are making the main loop limit no longer precise;
2006 // Hacking loop bounds; need private copies of exit test
2020 // Hack the now-private loop bounds
2028 // Remove simplistic dead code from loop body
2037 // Look for loop-exit tests with the 50/50 (or worse) guesses from the parsing stage.
2082 // have on the last iteration. This will break the loop.
2084 // Minimum size must be empty loop
2089 return false; // Dead loop
2092 return false; // Malformed loop
2094 return false; // Infinite loop
2142 tty->print("Removing empty loop with%s zero trip guard", needs_guard ? "out" : "");
2151 // Peel the loop to ensure there's a zero trip guard
2156 // Replace the phi at loop head with the final value of the last
2158 // taken) and all loop-invariant uses of the exit values will be correct.
2162 // We also need to replace the original limit to collapse loop exit.
2169 // counted loop has limit check predicate.
2178 // Convert one iteration loop into normal code.
2181 return false; // Only for counted loop
2200 // Replace the phi at loop head with the value of the init_trip.
2202 // and all loop-invariant uses of the exit values will be correct.
2211 // Compute exact loop trip count if possible.
2214 // Convert one iteration loop into normal code.
2220 return true; // Here we removed an empty loop
2227 // This removes loop-invariant tests (usually null checks).
2228 if (!_head->is_CountedLoop()) { // Non-counted loop
2230 // Partial peel succeeded so terminate this round of loop opts
2250 // Compute loop trip count from profile data
2254 // to completely unroll this loop or do loop unswitching.
2263 // completely unroll this loop and it will no longer be a loop.
2277 // front for RCE, and may want to align loop refs to a cache
2278 // line. Thus we clone a full loop up front whose trip count is
2281 // The main loop will start cache-line aligned with at least 1
2285 // A post-loop will finish any odd iterations (leftover after
2295 // need a pre-loop. We may still need to peel an initial iteration but
2299 // we will not be able to later do RCE or Aligning on this loop.
2303 // we switch to the pre-/main-/post-loop model. This model also covers
2309 // Adjust the pre- and main-loop limits to let the pre and post loops run
2310 // with full checks, but the main-loop with no checks. Remove said
2315 // Double loop body for unrolling. Adjust the minimum-trip test (will do
2318 // and we'd rather unroll the post-RCE'd loop SO... do not unroll if
2323 // Adjust the pre-loop limits to align the main body
2328 } else { // Else we have an unchanged counted loop
2347 // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
2349 if (_parent /*not the root loop*/ &&
2357 if (!_child && // If not an inner loop, do not split
2370 // Minor offset re-organization to remove loop-fallout uses of
2381 // Process all the loops in the loop tree and replace any fill
2393 // Examine an inner loop looking for a a single store of an invariant
2394 // value in a unit stride loop,
2404 // Process the loop looking for stores. If there are multiple
2435 // No store in loop
2548 // No make sure all the other nodes in the loop can be handled
2581 // Make sure no unexpected values are used outside the loop
2585 // outside the loop.
2590 msg = "node is used outside loop";
2630 // Check that the body only contains a store of a loop invariant
2631 // value that is indexed by the loop phi.
2647 // Now replace the whole loop body by a call to a fill routine that
2648 // covers the same region as the loop.
2745 // Redirect the old control and memory edges that are outside the loop.
2748 // state of the loop. It's safe in this case to replace it with the
2753 // Any uses the increment outside of the loop become the loop limit.
2756 // Disconnect the head from the loop.