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 }
|