273 // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
274 // make some loop-invariant test (usually a null-check) happen before the loop.
275 bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {
276 Node *test = ((IdealLoopTree*)this)->tail();
277 int body_size = ((IdealLoopTree*)this)->_body.size();
278 // Peeling does loop cloning which can result in O(N^2) node construction
279 if( body_size > 255 /* Prevent overflow for large body_size */
280 || (body_size * body_size + phase->C->live_nodes()) > phase->C->max_node_limit() ) {
281 return false; // too large to safely clone
282 }
283
284 // check for vectorized loops, any peeling done was already applied
285 if (_head->is_CountedLoop() && _head->as_CountedLoop()->do_unroll_only()) return false;
286
287 while( test != _head ) { // Scan till run off top of loop
288 if( test->is_If() ) { // Test?
289 Node *ctrl = phase->get_ctrl(test->in(1));
290 if (ctrl->is_top())
291 return false; // Found dead test on live IF? No peeling!
292 // Standard IF only has one input value to check for loop invariance
293 assert( test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
294 // Condition is not a member of this loop?
295 if( !is_member(phase->get_loop(ctrl)) &&
296 is_loop_exit(test) )
297 return true; // Found reason to peel!
298 }
299 // Walk up dominators to loop _head looking for test which is
300 // executed on every path thru loop.
301 test = phase->idom(test);
302 }
303 return false;
304 }
305
306 //------------------------------peeled_dom_test_elim---------------------------
307 // If we got the effect of peeling, either by actually peeling or by making
308 // a pre-loop which must execute at least once, we can remove all
309 // loop-invariant dominated tests in the main body.
310 void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {
311 bool progress = true;
312 while( progress ) {
313 progress = false; // Reset for next iteration
839 //------------------------------policy_range_check-----------------------------
840 // Return TRUE or FALSE if the loop should be range-check-eliminated.
841 // Actually we do iteration-splitting, a more powerful form of RCE.
842 bool IdealLoopTree::policy_range_check( PhaseIdealLoop *phase ) const {
843 if (!RangeCheckElimination) return false;
844
845 CountedLoopNode *cl = _head->as_CountedLoop();
846 // If we unrolled with no intention of doing RCE and we later
847 // changed our minds, we got no pre-loop. Either we need to
848 // make a new pre-loop, or we gotta disallow RCE.
849 if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
850 Node *trip_counter = cl->phi();
851
852 // check for vectorized loops, some opts are no longer needed
853 if (cl->do_unroll_only()) return false;
854
855 // Check loop body for tests of trip-counter plus loop-invariant vs
856 // loop-invariant.
857 for (uint i = 0; i < _body.size(); i++) {
858 Node *iff = _body[i];
859 if (iff->Opcode() == Op_If) { // Test?
860
861 // Comparing trip+off vs limit
862 Node *bol = iff->in(1);
863 if (bol->req() != 2) continue; // dead constant test
864 if (!bol->is_Bool()) {
865 assert(UseLoopPredicate && bol->Opcode() == Op_Conv2B, "predicate check only");
866 continue;
867 }
868 if (bol->as_Bool()->_test._test == BoolTest::ne)
869 continue; // not RC
870
871 Node *cmp = bol->in(1);
872 Node *rc_exp = cmp->in(1);
873 Node *limit = cmp->in(2);
874
875 Node *limit_c = phase->get_ctrl(limit);
876 if( limit_c == phase->C->top() )
877 return false; // Found dead test on live IF? No RCE!
878 if( is_member(phase->get_loop(limit_c) ) ) {
879 // Compare might have operands swapped; commute them
2018 Node *zero = _igvn.intcon(0);
2019 Node *one = _igvn.intcon(1);
2020 // Use symmetrical int range [-max_jint,max_jint]
2021 Node *mini = _igvn.intcon(-max_jint);
2022 set_ctrl(zero, C->root());
2023 set_ctrl(one, C->root());
2024 set_ctrl(mini, C->root());
2025
2026 // Range checks that do not dominate the loop backedge (ie.
2027 // conditionally executed) can lengthen the pre loop limit beyond
2028 // the original loop limit. To prevent this, the pre limit is
2029 // (for stride > 0) MINed with the original loop limit (MAXed
2030 // stride < 0) when some range_check (rc) is conditionally
2031 // executed.
2032 bool conditional_rc = false;
2033
2034 // Check loop body for tests of trip-counter plus loop-invariant vs
2035 // loop-invariant.
2036 for( uint i = 0; i < loop->_body.size(); i++ ) {
2037 Node *iff = loop->_body[i];
2038 if( iff->Opcode() == Op_If ) { // Test?
2039
2040 // Test is an IfNode, has 2 projections. If BOTH are in the loop
2041 // we need loop unswitching instead of iteration splitting.
2042 Node *exit = loop->is_loop_exit(iff);
2043 if( !exit ) continue;
2044 int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
2045
2046 // Get boolean condition to test
2047 Node *i1 = iff->in(1);
2048 if( !i1->is_Bool() ) continue;
2049 BoolNode *bol = i1->as_Bool();
2050 BoolTest b_test = bol->_test;
2051 // Flip sense of test if exit condition is flipped
2052 if( flip )
2053 b_test = b_test.negate();
2054
2055 // Get compare
2056 Node *cmp = bol->in(1);
2057
2058 // Look for trip_counter + offset vs limit
2059 Node *rc_exp = cmp->in(1);
|
273 // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
274 // make some loop-invariant test (usually a null-check) happen before the loop.
275 bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {
276 Node *test = ((IdealLoopTree*)this)->tail();
277 int body_size = ((IdealLoopTree*)this)->_body.size();
278 // Peeling does loop cloning which can result in O(N^2) node construction
279 if( body_size > 255 /* Prevent overflow for large body_size */
280 || (body_size * body_size + phase->C->live_nodes()) > phase->C->max_node_limit() ) {
281 return false; // too large to safely clone
282 }
283
284 // check for vectorized loops, any peeling done was already applied
285 if (_head->is_CountedLoop() && _head->as_CountedLoop()->do_unroll_only()) return false;
286
287 while( test != _head ) { // Scan till run off top of loop
288 if( test->is_If() ) { // Test?
289 Node *ctrl = phase->get_ctrl(test->in(1));
290 if (ctrl->is_top())
291 return false; // Found dead test on live IF? No peeling!
292 // Standard IF only has one input value to check for loop invariance
293 assert(test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd || test->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
294 // Condition is not a member of this loop?
295 if( !is_member(phase->get_loop(ctrl)) &&
296 is_loop_exit(test) )
297 return true; // Found reason to peel!
298 }
299 // Walk up dominators to loop _head looking for test which is
300 // executed on every path thru loop.
301 test = phase->idom(test);
302 }
303 return false;
304 }
305
306 //------------------------------peeled_dom_test_elim---------------------------
307 // If we got the effect of peeling, either by actually peeling or by making
308 // a pre-loop which must execute at least once, we can remove all
309 // loop-invariant dominated tests in the main body.
310 void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {
311 bool progress = true;
312 while( progress ) {
313 progress = false; // Reset for next iteration
839 //------------------------------policy_range_check-----------------------------
840 // Return TRUE or FALSE if the loop should be range-check-eliminated.
841 // Actually we do iteration-splitting, a more powerful form of RCE.
842 bool IdealLoopTree::policy_range_check( PhaseIdealLoop *phase ) const {
843 if (!RangeCheckElimination) return false;
844
845 CountedLoopNode *cl = _head->as_CountedLoop();
846 // If we unrolled with no intention of doing RCE and we later
847 // changed our minds, we got no pre-loop. Either we need to
848 // make a new pre-loop, or we gotta disallow RCE.
849 if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
850 Node *trip_counter = cl->phi();
851
852 // check for vectorized loops, some opts are no longer needed
853 if (cl->do_unroll_only()) return false;
854
855 // Check loop body for tests of trip-counter plus loop-invariant vs
856 // loop-invariant.
857 for (uint i = 0; i < _body.size(); i++) {
858 Node *iff = _body[i];
859 if (iff->Opcode() == Op_If ||
860 iff->Opcode() == Op_RangeCheck) { // Test?
861
862 // Comparing trip+off vs limit
863 Node *bol = iff->in(1);
864 if (bol->req() != 2) continue; // dead constant test
865 if (!bol->is_Bool()) {
866 assert(UseLoopPredicate && bol->Opcode() == Op_Conv2B, "predicate check only");
867 continue;
868 }
869 if (bol->as_Bool()->_test._test == BoolTest::ne)
870 continue; // not RC
871
872 Node *cmp = bol->in(1);
873 Node *rc_exp = cmp->in(1);
874 Node *limit = cmp->in(2);
875
876 Node *limit_c = phase->get_ctrl(limit);
877 if( limit_c == phase->C->top() )
878 return false; // Found dead test on live IF? No RCE!
879 if( is_member(phase->get_loop(limit_c) ) ) {
880 // Compare might have operands swapped; commute them
2019 Node *zero = _igvn.intcon(0);
2020 Node *one = _igvn.intcon(1);
2021 // Use symmetrical int range [-max_jint,max_jint]
2022 Node *mini = _igvn.intcon(-max_jint);
2023 set_ctrl(zero, C->root());
2024 set_ctrl(one, C->root());
2025 set_ctrl(mini, C->root());
2026
2027 // Range checks that do not dominate the loop backedge (ie.
2028 // conditionally executed) can lengthen the pre loop limit beyond
2029 // the original loop limit. To prevent this, the pre limit is
2030 // (for stride > 0) MINed with the original loop limit (MAXed
2031 // stride < 0) when some range_check (rc) is conditionally
2032 // executed.
2033 bool conditional_rc = false;
2034
2035 // Check loop body for tests of trip-counter plus loop-invariant vs
2036 // loop-invariant.
2037 for( uint i = 0; i < loop->_body.size(); i++ ) {
2038 Node *iff = loop->_body[i];
2039 if (iff->Opcode() == Op_If ||
2040 iff->Opcode() == Op_RangeCheck) { // Test?
2041 // Test is an IfNode, has 2 projections. If BOTH are in the loop
2042 // we need loop unswitching instead of iteration splitting.
2043 Node *exit = loop->is_loop_exit(iff);
2044 if( !exit ) continue;
2045 int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
2046
2047 // Get boolean condition to test
2048 Node *i1 = iff->in(1);
2049 if( !i1->is_Bool() ) continue;
2050 BoolNode *bol = i1->as_Bool();
2051 BoolTest b_test = bol->_test;
2052 // Flip sense of test if exit condition is flipped
2053 if( flip )
2054 b_test = b_test.negate();
2055
2056 // Get compare
2057 Node *cmp = bol->in(1);
2058
2059 // Look for trip_counter + offset vs limit
2060 Node *rc_exp = cmp->in(1);
|