< prev index next >

src/share/vm/opto/loopTransform.cpp

Print this page


   1 /*
   2  * Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


  53     return iff->raw_out(0);
  54   if( !is_member(phase->get_loop( iff->raw_out(1) )) )
  55     return iff->raw_out(1);
  56   return NULL;
  57 }
  58 
  59 
  60 //=============================================================================
  61 
  62 
  63 //------------------------------record_for_igvn----------------------------
  64 // Put loop body on igvn work list
  65 void IdealLoopTree::record_for_igvn() {
  66   for( uint i = 0; i < _body.size(); i++ ) {
  67     Node *n = _body.at(i);
  68     _phase->_igvn._worklist.push(n);
  69   }
  70 }
  71 
  72 //------------------------------compute_exact_trip_count-----------------------
  73 // Compute loop exact trip count if possible. Do not recalculate trip count for
  74 // split loops (pre-main-post) which have their limits and inits behind Opaque node.
  75 void IdealLoopTree::compute_exact_trip_count( PhaseIdealLoop *phase ) {
  76   if (!_head->as_Loop()->is_valid_counted_loop()) {
  77     return;
  78   }
  79   CountedLoopNode* cl = _head->as_CountedLoop();
  80   // Trip count may become nonexact for iteration split loops since
  81   // RCE modifies limits. Note, _trip_count value is not reset since
  82   // it is used to limit unrolling of main loop.
  83   cl->set_nonexact_trip_count();
  84 
  85   // Loop's test should be part of loop.
  86   if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
  87     return; // Infinite loop
  88 
  89 #ifdef ASSERT
  90   BoolTest::mask bt = cl->loopexit()->test_trip();
  91   assert(bt == BoolTest::lt || bt == BoolTest::gt ||
  92          bt == BoolTest::ne, "canonical test is expected");
  93 #endif
  94 
  95   Node* init_n = cl->init_trip();
  96   Node* limit_n = cl->limit();
  97   if (init_n  != NULL &&  init_n->is_Con() &&
  98       limit_n != NULL && limit_n->is_Con()) {
  99     // Use longs to avoid integer overflow.
 100     int stride_con  = cl->stride_con();
 101     jlong init_con   = cl->init_trip()->get_int();
 102     jlong limit_con  = cl->limit()->get_int();
 103     int stride_m    = stride_con - (stride_con > 0 ? 1 : -1);
 104     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
 105     if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {

 106       // Set exact trip count.
 107       cl->set_exact_trip_count((uint)trip_count);




 108     }
 109   }
 110 }
 111 
 112 //------------------------------compute_profile_trip_cnt----------------------------
 113 // Compute loop trip count from profile data as
 114 //    (backedge_count + loop_exit_count) / loop_exit_count
 115 void IdealLoopTree::compute_profile_trip_cnt( PhaseIdealLoop *phase ) {
 116   if (!_head->is_CountedLoop()) {
 117     return;
 118   }
 119   CountedLoopNode* head = _head->as_CountedLoop();
 120   if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
 121     return; // Already computed
 122   }
 123   float trip_cnt = (float)max_jint; // default is big
 124 
 125   Node* back = head->in(LoopNode::LoopBackControl);
 126   while (back != head) {
 127     if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&


1288 
1289   // Now force out all loop-invariant dominating tests.  The optimizer
1290   // finds some, but we _know_ they are all useless.
1291   peeled_dom_test_elim(loop, old_new);
1292   loop->record_for_igvn();
1293 }
1294 
1295 
1296 //------------------------------insert_post_loop-------------------------------
1297 // Insert post loops.  Add a post loop to the given loop passed.
1298 Node *PhaseIdealLoop::insert_post_loop(IdealLoopTree *loop, Node_List &old_new,
1299                                        CountedLoopNode *main_head, CountedLoopEndNode *main_end,
1300                                        Node *incr, Node *limit, CountedLoopNode *&post_head) {
1301 
1302   //------------------------------
1303   // Step A: Create a new post-Loop.
1304   Node* main_exit = main_end->proj_out(false);
1305   assert(main_exit->Opcode() == Op_IfFalse, "");
1306   int dd_main_exit = dom_depth(main_exit);
1307 
1308   // Step A1: Clone the loop body of main.  The clone becomes the vector post-loop.
1309   // The main loop pre-header illegally has 2 control users (old & new loops).
1310   clone_loop(loop, old_new, dd_main_exit);
1311   assert(old_new[main_end->_idx]->Opcode() == Op_CountedLoopEnd, "");
1312   post_head = old_new[main_head->_idx]->as_CountedLoop();
1313   post_head->set_normal_loop();
1314   post_head->set_post_loop(main_head);
1315 
1316   // Reduce the post-loop trip count.
1317   CountedLoopEndNode* post_end = old_new[main_end->_idx]->as_CountedLoopEnd();
1318   post_end->_prob = PROB_FAIR;
1319 
1320   // Build the main-loop normal exit.
1321   IfFalseNode *new_main_exit = new IfFalseNode(main_end);
1322   _igvn.register_new_node_with_optimizer(new_main_exit);
1323   set_idom(new_main_exit, main_end, dd_main_exit);
1324   set_loop(new_main_exit, loop->_parent);
1325 
1326   // Step A2: Build a zero-trip guard for the post-loop.  After leaving the
1327   // main-loop, the post-loop may not execute at all.  We 'opaque' the incr
1328   // (the previous loop trip-counter exit value) because we will be changing


2078   Node *zero = _igvn.intcon(0);
2079   Node *one  = _igvn.intcon(1);
2080   // Use symmetrical int range [-max_jint,max_jint]
2081   Node *mini = _igvn.intcon(-max_jint);
2082   set_ctrl(zero, C->root());
2083   set_ctrl(one,  C->root());
2084   set_ctrl(mini, C->root());
2085 
2086   // Range checks that do not dominate the loop backedge (ie.
2087   // conditionally executed) can lengthen the pre loop limit beyond
2088   // the original loop limit. To prevent this, the pre limit is
2089   // (for stride > 0) MINed with the original loop limit (MAXed
2090   // stride < 0) when some range_check (rc) is conditionally
2091   // executed.
2092   bool conditional_rc = false;
2093 
2094   // Count number of range checks and reduce by load range limits, if zero,
2095   // the loop is in canonical form to multiversion.
2096   closed_range_checks = 0;
2097 
2098   // Check loop body for tests of trip-counter plus loop-invariant vs
2099   // loop-invariant.
2100   for( uint i = 0; i < loop->_body.size(); i++ ) {
2101     Node *iff = loop->_body[i];
2102     if (iff->Opcode() == Op_If ||
2103         iff->Opcode() == Op_RangeCheck) { // Test?
2104       // Test is an IfNode, has 2 projections.  If BOTH are in the loop
2105       // we need loop unswitching instead of iteration splitting.
2106       closed_range_checks++;
2107       Node *exit = loop->is_loop_exit(iff);
2108       if( !exit ) continue;
2109       int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
2110 
2111       // Get boolean condition to test
2112       Node *i1 = iff->in(1);
2113       if( !i1->is_Bool() ) continue;
2114       BoolNode *bol = i1->as_Bool();
2115       BoolTest b_test = bol->_test;
2116       // Flip sense of test if exit condition is flipped
2117       if( flip )
2118         b_test = b_test.negate();
2119 


2281   // The OpaqueNode is unshared by design
2282   assert( opqzm->outcnt() == 1, "cannot hack shared node" );
2283   _igvn.replace_input_of(opqzm, 1, main_limit);
2284 
2285   return closed_range_checks;
2286 }
2287 
2288 //------------------------------has_range_checks-------------------------------
2289 // Check to see if RCE cleaned the current loop of range-checks.
2290 void PhaseIdealLoop::has_range_checks(IdealLoopTree *loop) {
2291   assert(RangeCheckElimination, "");
2292 
2293   // skip if not a counted loop
2294   if (!loop->is_counted()) return;
2295 
2296   CountedLoopNode *cl = loop->_head->as_CountedLoop();
2297 
2298   // skip this loop if it is already checked
2299   if (cl->has_been_range_checked()) return;
2300 
2301   // Now check for existance of range checks
2302   for (uint i = 0; i < loop->_body.size(); i++) {
2303     Node *iff = loop->_body[i];
2304     int iff_opc = iff->Opcode();
2305     if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2306       cl->mark_has_range_checks();
2307       break;
2308     }
2309   }
2310   cl->set_has_been_range_checked();
2311 }
2312 
2313 //-------------------------multi_version_post_loops----------------------------
2314 // Check the range checks that remain, if simple, use the bounds to guard
2315 // which version to a post loop we execute, one with range checks or one without
2316 bool PhaseIdealLoop::multi_version_post_loops(IdealLoopTree *rce_loop, IdealLoopTree *legacy_loop) {
2317   bool multi_version_succeeded = false;
2318   assert(RangeCheckElimination, "");
2319   CountedLoopNode *legacy_cl = legacy_loop->_head->as_CountedLoop();
2320   assert(legacy_cl->is_post_loop(), "");
2321 
2322   // Check for existance of range checks using the unique instance to make a guard with
2323   Unique_Node_List worklist;
2324   for (uint i = 0; i < legacy_loop->_body.size(); i++) {
2325     Node *iff = legacy_loop->_body[i];
2326     int iff_opc = iff->Opcode();
2327     if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2328       worklist.push(iff);
2329     }
2330   }
2331 
2332   // Find RCE'd post loop so that we can stage its guard.
2333   if (!is_canonical_loop_entry(legacy_cl)) return multi_version_succeeded;
2334   Node* ctrl = legacy_cl->in(LoopNode::EntryControl);
2335   Node* iffm = ctrl->in(0);
2336 
2337   // Now we test that both the post loops are connected
2338   Node* post_loop_region = iffm->in(0);
2339   if (post_loop_region == NULL) return multi_version_succeeded;
2340   if (!post_loop_region->is_Region()) return multi_version_succeeded;
2341   Node* covering_region = post_loop_region->in(RegionNode::Control+1);
2342   if (covering_region == NULL) return multi_version_succeeded;


2405   if (last_min && multi_version_succeeded) {
2406     Node *cur_min = new MinINode(last_min, limit);
2407     _igvn.register_new_node_with_optimizer(cur_min);
2408     Node *cmp_node = rce_loop_end->cmp_node();
2409     _igvn.replace_input_of(cmp_node, 2, cur_min);
2410     set_idom(cmp_node, cur_min, dom_depth(ctrl));
2411     set_ctrl(cur_min, ctrl);
2412     set_loop(cur_min, rce_loop->_parent);
2413 
2414     legacy_cl->mark_is_multiversioned();
2415     rce_cl->mark_is_multiversioned();
2416     multi_version_succeeded = true;
2417 
2418     C->set_major_progress();
2419   }
2420 
2421   return multi_version_succeeded;
2422 }
2423 
2424 //-------------------------poison_rce_post_loop--------------------------------
2425 // Causes the rce'd post loop to be optimized away if multiverioning fails
2426 void PhaseIdealLoop::poison_rce_post_loop(IdealLoopTree *rce_loop) {
2427   CountedLoopNode *rce_cl = rce_loop->_head->as_CountedLoop();
2428   Node* ctrl = rce_cl->in(LoopNode::EntryControl);
2429   if (ctrl->is_IfTrue() || ctrl->is_IfFalse()) {
2430     Node* iffm = ctrl->in(0);
2431     if (iffm->is_If()) {
2432       Node* cur_bool = iffm->in(1);
2433       if (cur_bool->is_Bool()) {
2434         Node* cur_cmp = cur_bool->in(1);
2435         if (cur_cmp->is_Cmp()) {
2436           BoolTest::mask new_test = BoolTest::gt;
2437           BoolNode *new_bool = new BoolNode(cur_cmp, new_test);
2438           _igvn.replace_node(cur_bool, new_bool);
2439           _igvn._worklist.push(new_bool);
2440           Node* left_op = cur_cmp->in(1);
2441           _igvn.replace_input_of(cur_cmp, 2, left_op);
2442           C->set_major_progress();
2443         }
2444       }
2445     }


2693     this->dump_head();
2694   }
2695 #endif
2696 
2697   Node *init_n = cl->init_trip();
2698 #ifdef ASSERT
2699   // Loop boundaries should be constant since trip count is exact.
2700   assert(init_n->get_int() + cl->stride_con() >= cl->limit()->get_int(), "should be one iteration");
2701 #endif
2702   // Replace the phi at loop head with the value of the init_trip.
2703   // Then the CountedLoopEnd will collapse (backedge will not be taken)
2704   // and all loop-invariant uses of the exit values will be correct.
2705   phase->_igvn.replace_node(cl->phi(), cl->init_trip());
2706   phase->C->set_major_progress();
2707   return true;
2708 }
2709 
2710 //=============================================================================
2711 //------------------------------iteration_split_impl---------------------------
2712 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) {
2713   // Compute exact loop trip count if possible.
2714   compute_exact_trip_count(phase);
2715 
2716   // Convert one iteration loop into normal code.
2717   if (policy_do_one_iteration_loop(phase))
2718     return true;
2719 
2720   // Check and remove empty loops (spam micro-benchmarks)
2721   if (policy_do_remove_empty_loop(phase))
2722     return true;  // Here we removed an empty loop
2723 
2724   bool should_peel = policy_peeling(phase); // Should we peel?
2725 
2726   bool should_unswitch = policy_unswitching(phase);
2727 
2728   // Non-counted loops may be peeled; exactly 1 iteration is peeled.
2729   // This removes loop-invariant tests (usually null checks).
2730   if (!_head->is_CountedLoop()) { // Non-counted loop
2731     if (PartialPeelLoop && phase->partial_peel(this, old_new)) {
2732       // Partial peel succeeded so terminate this round of loop opts
2733       return false;
2734     }


   1 /*
   2  * Copyright (c) 2000, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


  53     return iff->raw_out(0);
  54   if( !is_member(phase->get_loop( iff->raw_out(1) )) )
  55     return iff->raw_out(1);
  56   return NULL;
  57 }
  58 
  59 
  60 //=============================================================================
  61 
  62 
  63 //------------------------------record_for_igvn----------------------------
  64 // Put loop body on igvn work list
  65 void IdealLoopTree::record_for_igvn() {
  66   for( uint i = 0; i < _body.size(); i++ ) {
  67     Node *n = _body.at(i);
  68     _phase->_igvn._worklist.push(n);
  69   }
  70 }
  71 
  72 //------------------------------compute_exact_trip_count-----------------------
  73 // Compute loop trip count if possible. Do not recalculate trip count for
  74 // split loops (pre-main-post) which have their limits and inits behind Opaque node.
  75 void IdealLoopTree::compute_trip_count(PhaseIdealLoop* phase) {
  76   if (!_head->as_Loop()->is_valid_counted_loop()) {
  77     return;
  78   }
  79   CountedLoopNode* cl = _head->as_CountedLoop();
  80   // Trip count may become nonexact for iteration split loops since
  81   // RCE modifies limits. Note, _trip_count value is not reset since
  82   // it is used to limit unrolling of main loop.
  83   cl->set_nonexact_trip_count();
  84 
  85   // Loop's test should be part of loop.
  86   if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
  87     return; // Infinite loop
  88 
  89 #ifdef ASSERT
  90   BoolTest::mask bt = cl->loopexit()->test_trip();
  91   assert(bt == BoolTest::lt || bt == BoolTest::gt ||
  92          bt == BoolTest::ne, "canonical test is expected");
  93 #endif
  94 
  95   Node* init_n = cl->init_trip();
  96   Node* limit_n = cl->limit();
  97   if (init_n != NULL && limit_n != NULL) {

  98     // Use longs to avoid integer overflow.
  99     int stride_con = cl->stride_con();
 100     jlong init_con = phase->_igvn.type(init_n)->is_int()->_lo;
 101     jlong limit_con = phase->_igvn.type(limit_n)->is_int()->_hi;
 102     int stride_m   = stride_con - (stride_con > 0 ? 1 : -1);
 103     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
 104     if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
 105       if (init_n->is_Con() && limit_n->is_Con()) {
 106         // Set exact trip count.
 107         cl->set_exact_trip_count((uint)trip_count);
 108       } else if (cl->is_normal_loop() && cl->unrolled_count() == 1) {
 109         // Set maximum trip count before unrolling.
 110         cl->set_trip_count((uint)trip_count);
 111       }
 112     }
 113   }
 114 }
 115 
 116 //------------------------------compute_profile_trip_cnt----------------------------
 117 // Compute loop trip count from profile data as
 118 //    (backedge_count + loop_exit_count) / loop_exit_count
 119 void IdealLoopTree::compute_profile_trip_cnt( PhaseIdealLoop *phase ) {
 120   if (!_head->is_CountedLoop()) {
 121     return;
 122   }
 123   CountedLoopNode* head = _head->as_CountedLoop();
 124   if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
 125     return; // Already computed
 126   }
 127   float trip_cnt = (float)max_jint; // default is big
 128 
 129   Node* back = head->in(LoopNode::LoopBackControl);
 130   while (back != head) {
 131     if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&


1292 
1293   // Now force out all loop-invariant dominating tests.  The optimizer
1294   // finds some, but we _know_ they are all useless.
1295   peeled_dom_test_elim(loop, old_new);
1296   loop->record_for_igvn();
1297 }
1298 
1299 
1300 //------------------------------insert_post_loop-------------------------------
1301 // Insert post loops.  Add a post loop to the given loop passed.
1302 Node *PhaseIdealLoop::insert_post_loop(IdealLoopTree *loop, Node_List &old_new,
1303                                        CountedLoopNode *main_head, CountedLoopEndNode *main_end,
1304                                        Node *incr, Node *limit, CountedLoopNode *&post_head) {
1305 
1306   //------------------------------
1307   // Step A: Create a new post-Loop.
1308   Node* main_exit = main_end->proj_out(false);
1309   assert(main_exit->Opcode() == Op_IfFalse, "");
1310   int dd_main_exit = dom_depth(main_exit);
1311 
1312   // Step A1: Clone the loop body of main. The clone becomes the post-loop.
1313   // The main loop pre-header illegally has 2 control users (old & new loops).
1314   clone_loop(loop, old_new, dd_main_exit);
1315   assert(old_new[main_end->_idx]->Opcode() == Op_CountedLoopEnd, "");
1316   post_head = old_new[main_head->_idx]->as_CountedLoop();
1317   post_head->set_normal_loop();
1318   post_head->set_post_loop(main_head);
1319 
1320   // Reduce the post-loop trip count.
1321   CountedLoopEndNode* post_end = old_new[main_end->_idx]->as_CountedLoopEnd();
1322   post_end->_prob = PROB_FAIR;
1323 
1324   // Build the main-loop normal exit.
1325   IfFalseNode *new_main_exit = new IfFalseNode(main_end);
1326   _igvn.register_new_node_with_optimizer(new_main_exit);
1327   set_idom(new_main_exit, main_end, dd_main_exit);
1328   set_loop(new_main_exit, loop->_parent);
1329 
1330   // Step A2: Build a zero-trip guard for the post-loop.  After leaving the
1331   // main-loop, the post-loop may not execute at all.  We 'opaque' the incr
1332   // (the previous loop trip-counter exit value) because we will be changing


2082   Node *zero = _igvn.intcon(0);
2083   Node *one  = _igvn.intcon(1);
2084   // Use symmetrical int range [-max_jint,max_jint]
2085   Node *mini = _igvn.intcon(-max_jint);
2086   set_ctrl(zero, C->root());
2087   set_ctrl(one,  C->root());
2088   set_ctrl(mini, C->root());
2089 
2090   // Range checks that do not dominate the loop backedge (ie.
2091   // conditionally executed) can lengthen the pre loop limit beyond
2092   // the original loop limit. To prevent this, the pre limit is
2093   // (for stride > 0) MINed with the original loop limit (MAXed
2094   // stride < 0) when some range_check (rc) is conditionally
2095   // executed.
2096   bool conditional_rc = false;
2097 
2098   // Count number of range checks and reduce by load range limits, if zero,
2099   // the loop is in canonical form to multiversion.
2100   closed_range_checks = 0;
2101 
2102   // Check loop body for tests of trip-counter plus loop-invariant vs loop-variant.

2103   for( uint i = 0; i < loop->_body.size(); i++ ) {
2104     Node *iff = loop->_body[i];
2105     if (iff->Opcode() == Op_If ||
2106         iff->Opcode() == Op_RangeCheck) { // Test?
2107       // Test is an IfNode, has 2 projections.  If BOTH are in the loop
2108       // we need loop unswitching instead of iteration splitting.
2109       closed_range_checks++;
2110       Node *exit = loop->is_loop_exit(iff);
2111       if( !exit ) continue;
2112       int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
2113 
2114       // Get boolean condition to test
2115       Node *i1 = iff->in(1);
2116       if( !i1->is_Bool() ) continue;
2117       BoolNode *bol = i1->as_Bool();
2118       BoolTest b_test = bol->_test;
2119       // Flip sense of test if exit condition is flipped
2120       if( flip )
2121         b_test = b_test.negate();
2122 


2284   // The OpaqueNode is unshared by design
2285   assert( opqzm->outcnt() == 1, "cannot hack shared node" );
2286   _igvn.replace_input_of(opqzm, 1, main_limit);
2287 
2288   return closed_range_checks;
2289 }
2290 
2291 //------------------------------has_range_checks-------------------------------
2292 // Check to see if RCE cleaned the current loop of range-checks.
2293 void PhaseIdealLoop::has_range_checks(IdealLoopTree *loop) {
2294   assert(RangeCheckElimination, "");
2295 
2296   // skip if not a counted loop
2297   if (!loop->is_counted()) return;
2298 
2299   CountedLoopNode *cl = loop->_head->as_CountedLoop();
2300 
2301   // skip this loop if it is already checked
2302   if (cl->has_been_range_checked()) return;
2303 
2304   // Now check for existence of range checks
2305   for (uint i = 0; i < loop->_body.size(); i++) {
2306     Node *iff = loop->_body[i];
2307     int iff_opc = iff->Opcode();
2308     if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2309       cl->mark_has_range_checks();
2310       break;
2311     }
2312   }
2313   cl->set_has_been_range_checked();
2314 }
2315 
2316 //-------------------------multi_version_post_loops----------------------------
2317 // Check the range checks that remain, if simple, use the bounds to guard
2318 // which version to a post loop we execute, one with range checks or one without
2319 bool PhaseIdealLoop::multi_version_post_loops(IdealLoopTree *rce_loop, IdealLoopTree *legacy_loop) {
2320   bool multi_version_succeeded = false;
2321   assert(RangeCheckElimination, "");
2322   CountedLoopNode *legacy_cl = legacy_loop->_head->as_CountedLoop();
2323   assert(legacy_cl->is_post_loop(), "");
2324 
2325   // Check for existence of range checks using the unique instance to make a guard with
2326   Unique_Node_List worklist;
2327   for (uint i = 0; i < legacy_loop->_body.size(); i++) {
2328     Node *iff = legacy_loop->_body[i];
2329     int iff_opc = iff->Opcode();
2330     if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2331       worklist.push(iff);
2332     }
2333   }
2334 
2335   // Find RCE'd post loop so that we can stage its guard.
2336   if (!is_canonical_loop_entry(legacy_cl)) return multi_version_succeeded;
2337   Node* ctrl = legacy_cl->in(LoopNode::EntryControl);
2338   Node* iffm = ctrl->in(0);
2339 
2340   // Now we test that both the post loops are connected
2341   Node* post_loop_region = iffm->in(0);
2342   if (post_loop_region == NULL) return multi_version_succeeded;
2343   if (!post_loop_region->is_Region()) return multi_version_succeeded;
2344   Node* covering_region = post_loop_region->in(RegionNode::Control+1);
2345   if (covering_region == NULL) return multi_version_succeeded;


2408   if (last_min && multi_version_succeeded) {
2409     Node *cur_min = new MinINode(last_min, limit);
2410     _igvn.register_new_node_with_optimizer(cur_min);
2411     Node *cmp_node = rce_loop_end->cmp_node();
2412     _igvn.replace_input_of(cmp_node, 2, cur_min);
2413     set_idom(cmp_node, cur_min, dom_depth(ctrl));
2414     set_ctrl(cur_min, ctrl);
2415     set_loop(cur_min, rce_loop->_parent);
2416 
2417     legacy_cl->mark_is_multiversioned();
2418     rce_cl->mark_is_multiversioned();
2419     multi_version_succeeded = true;
2420 
2421     C->set_major_progress();
2422   }
2423 
2424   return multi_version_succeeded;
2425 }
2426 
2427 //-------------------------poison_rce_post_loop--------------------------------
2428 // Causes the rce'd post loop to be optimized away if multiversioning fails
2429 void PhaseIdealLoop::poison_rce_post_loop(IdealLoopTree *rce_loop) {
2430   CountedLoopNode *rce_cl = rce_loop->_head->as_CountedLoop();
2431   Node* ctrl = rce_cl->in(LoopNode::EntryControl);
2432   if (ctrl->is_IfTrue() || ctrl->is_IfFalse()) {
2433     Node* iffm = ctrl->in(0);
2434     if (iffm->is_If()) {
2435       Node* cur_bool = iffm->in(1);
2436       if (cur_bool->is_Bool()) {
2437         Node* cur_cmp = cur_bool->in(1);
2438         if (cur_cmp->is_Cmp()) {
2439           BoolTest::mask new_test = BoolTest::gt;
2440           BoolNode *new_bool = new BoolNode(cur_cmp, new_test);
2441           _igvn.replace_node(cur_bool, new_bool);
2442           _igvn._worklist.push(new_bool);
2443           Node* left_op = cur_cmp->in(1);
2444           _igvn.replace_input_of(cur_cmp, 2, left_op);
2445           C->set_major_progress();
2446         }
2447       }
2448     }


2696     this->dump_head();
2697   }
2698 #endif
2699 
2700   Node *init_n = cl->init_trip();
2701 #ifdef ASSERT
2702   // Loop boundaries should be constant since trip count is exact.
2703   assert(init_n->get_int() + cl->stride_con() >= cl->limit()->get_int(), "should be one iteration");
2704 #endif
2705   // Replace the phi at loop head with the value of the init_trip.
2706   // Then the CountedLoopEnd will collapse (backedge will not be taken)
2707   // and all loop-invariant uses of the exit values will be correct.
2708   phase->_igvn.replace_node(cl->phi(), cl->init_trip());
2709   phase->C->set_major_progress();
2710   return true;
2711 }
2712 
2713 //=============================================================================
2714 //------------------------------iteration_split_impl---------------------------
2715 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) {
2716   // Compute loop trip count if possible.
2717   compute_trip_count(phase);
2718 
2719   // Convert one iteration loop into normal code.
2720   if (policy_do_one_iteration_loop(phase))
2721     return true;
2722 
2723   // Check and remove empty loops (spam micro-benchmarks)
2724   if (policy_do_remove_empty_loop(phase))
2725     return true;  // Here we removed an empty loop
2726 
2727   bool should_peel = policy_peeling(phase); // Should we peel?
2728 
2729   bool should_unswitch = policy_unswitching(phase);
2730 
2731   // Non-counted loops may be peeled; exactly 1 iteration is peeled.
2732   // This removes loop-invariant tests (usually null checks).
2733   if (!_head->is_CountedLoop()) { // Non-counted loop
2734     if (PartialPeelLoop && phase->partial_peel(this, old_new)) {
2735       // Partial peel succeeded so terminate this round of loop opts
2736       return false;
2737     }


< prev index next >