1 /*
2 * Copyright (c) 2000, 2018, 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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "compiler/compileLog.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/callnode.hpp"
30 #include "opto/castnode.hpp"
31 #include "opto/connode.hpp"
32 #include "opto/convertnode.hpp"
33 #include "opto/divnode.hpp"
34 #include "opto/loopnode.hpp"
35 #include "opto/mulnode.hpp"
36 #include "opto/movenode.hpp"
37 #include "opto/opaquenode.hpp"
38 #include "opto/rootnode.hpp"
39 #include "opto/runtime.hpp"
40 #include "opto/subnode.hpp"
41 #include "opto/superword.hpp"
42 #include "opto/vectornode.hpp"
43
44 //------------------------------is_loop_exit-----------------------------------
45 // Given an IfNode, return the loop-exiting projection or NULL if both
46 // arms remain in the loop.
47 Node *IdealLoopTree::is_loop_exit(Node *iff) const {
48 if( iff->outcnt() != 2 ) return NULL; // Ignore partially dead tests
49 PhaseIdealLoop *phase = _phase;
50 // Test is an IfNode, has 2 projections. If BOTH are in the loop
51 // we need loop unswitching instead of peeling.
52 if( !is_member(phase->get_loop( iff->raw_out(0) )) )
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 // put body of outer strip mined loop on igvn work list as well
71 if (_head->is_CountedLoop() && _head->as_Loop()->is_strip_mined()) {
72 CountedLoopNode* l = _head->as_CountedLoop();
73 Node* outer_loop = l->outer_loop();
74 assert(outer_loop != NULL, "missing piece of strip mined loop");
75 _phase->_igvn._worklist.push(outer_loop);
76 Node* outer_loop_tail = l->outer_loop_tail();
77 assert(outer_loop_tail != NULL, "missing piece of strip mined loop");
78 _phase->_igvn._worklist.push(outer_loop_tail);
79 Node* outer_loop_end = l->outer_loop_end();
80 assert(outer_loop_end != NULL, "missing piece of strip mined loop");
81 _phase->_igvn._worklist.push(outer_loop_end);
82 Node* outer_safepoint = l->outer_safepoint();
83 assert(outer_safepoint != NULL, "missing piece of strip mined loop");
84 _phase->_igvn._worklist.push(outer_safepoint);
85 Node* cle_out = _head->as_CountedLoop()->loopexit()->proj_out(false);
86 assert(cle_out != NULL, "missing piece of strip mined loop");
87 _phase->_igvn._worklist.push(cle_out);
88 }
89 }
90
91 //------------------------------compute_exact_trip_count-----------------------
92 // Compute loop trip count if possible. Do not recalculate trip count for
93 // split loops (pre-main-post) which have their limits and inits behind Opaque node.
94 void IdealLoopTree::compute_trip_count(PhaseIdealLoop* phase) {
95 if (!_head->as_Loop()->is_valid_counted_loop()) {
96 return;
97 }
98 CountedLoopNode* cl = _head->as_CountedLoop();
99 // Trip count may become nonexact for iteration split loops since
100 // RCE modifies limits. Note, _trip_count value is not reset since
101 // it is used to limit unrolling of main loop.
102 cl->set_nonexact_trip_count();
103
104 // Loop's test should be part of loop.
105 if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
106 return; // Infinite loop
107
108 #ifdef ASSERT
109 BoolTest::mask bt = cl->loopexit()->test_trip();
110 assert(bt == BoolTest::lt || bt == BoolTest::gt ||
111 bt == BoolTest::ne, "canonical test is expected");
112 #endif
113
114 Node* init_n = cl->init_trip();
115 Node* limit_n = cl->limit();
116 if (init_n != NULL && limit_n != NULL) {
117 // Use longs to avoid integer overflow.
118 int stride_con = cl->stride_con();
119 jlong init_con = phase->_igvn.type(init_n)->is_int()->_lo;
120 jlong limit_con = phase->_igvn.type(limit_n)->is_int()->_hi;
121 int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
122 jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
123 if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
124 if (init_n->is_Con() && limit_n->is_Con()) {
125 // Set exact trip count.
126 cl->set_exact_trip_count((uint)trip_count);
127 } else if (cl->unrolled_count() == 1) {
128 // Set maximum trip count before unrolling.
129 cl->set_trip_count((uint)trip_count);
130 }
131 }
132 }
133 }
134
135 //------------------------------compute_profile_trip_cnt----------------------------
136 // Compute loop trip count from profile data as
137 // (backedge_count + loop_exit_count) / loop_exit_count
138
139 float IdealLoopTree::compute_profile_trip_cnt_helper(Node* n) {
140 if (n->is_If()) {
141 IfNode *iff = n->as_If();
142 if (iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN) {
143 Node *exit = is_loop_exit(iff);
144 if (exit) {
145 float exit_prob = iff->_prob;
146 if (exit->Opcode() == Op_IfFalse) exit_prob = 1.0 - exit_prob;
147 if (exit_prob > PROB_MIN) {
148 float exit_cnt = iff->_fcnt * exit_prob;
149 return exit_cnt;
150 }
151 }
152 }
153 }
154 if (n->is_Jump()) {
155 JumpNode *jmp = n->as_Jump();
156 if (jmp->_fcnt != COUNT_UNKNOWN) {
157 float* probs = jmp->_probs;
158 float exit_prob = 0;
159 PhaseIdealLoop *phase = _phase;
160 for (DUIterator_Fast imax, i = jmp->fast_outs(imax); i < imax; i++) {
161 JumpProjNode* u = jmp->fast_out(i)->as_JumpProj();
162 if (!is_member(_phase->get_loop(u))) {
163 exit_prob += probs[u->_con];
164 }
165 }
166 return exit_prob * jmp->_fcnt;
167 }
168 }
169 return 0;
170 }
171
172 void IdealLoopTree::compute_profile_trip_cnt(PhaseIdealLoop *phase) {
173 if (!_head->is_Loop()) {
174 return;
175 }
176 LoopNode* head = _head->as_Loop();
177 if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
178 return; // Already computed
179 }
180 float trip_cnt = (float)max_jint; // default is big
181
182 Node* back = head->in(LoopNode::LoopBackControl);
183 while (back != head) {
184 if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
185 back->in(0) &&
186 back->in(0)->is_If() &&
187 back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&
188 back->in(0)->as_If()->_prob != PROB_UNKNOWN &&
189 (back->Opcode() == Op_IfTrue ? 1-back->in(0)->as_If()->_prob : back->in(0)->as_If()->_prob) > PROB_MIN) {
190 break;
191 }
192 back = phase->idom(back);
193 }
194 if (back != head) {
195 assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
196 back->in(0), "if-projection exists");
197 IfNode* back_if = back->in(0)->as_If();
198 float loop_back_cnt = back_if->_fcnt * (back->Opcode() == Op_IfTrue ? back_if->_prob : (1 - back_if->_prob));
199
200 // Now compute a loop exit count
201 float loop_exit_cnt = 0.0f;
202 if (_child == NULL) {
203 for( uint i = 0; i < _body.size(); i++ ) {
204 Node *n = _body[i];
205 loop_exit_cnt += compute_profile_trip_cnt_helper(n);
206 }
207 } else {
208 ResourceMark rm;
209 Unique_Node_List wq;
210 wq.push(back);
211 for (uint i = 0; i < wq.size(); i++) {
212 Node *n = wq.at(i);
213 assert(n->is_CFG(), "only control nodes");
214 if (n != head) {
215 if (n->is_Region()) {
216 for (uint j = 1; j < n->req(); j++) {
217 wq.push(n->in(j));
218 }
219 } else {
220 loop_exit_cnt += compute_profile_trip_cnt_helper(n);
221 wq.push(n->in(0));
222 }
223 }
224 }
225
226 }
227 if (loop_exit_cnt > 0.0f) {
228 trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;
229 } else {
230 // No exit count so use
231 trip_cnt = loop_back_cnt;
232 }
233 } else {
234 head->mark_profile_trip_failed();
235 }
236 #ifndef PRODUCT
237 if (TraceProfileTripCount) {
238 tty->print_cr("compute_profile_trip_cnt lp: %d cnt: %f\n", head->_idx, trip_cnt);
239 }
240 #endif
241 head->set_profile_trip_cnt(trip_cnt);
242 }
243
244 //---------------------is_invariant_addition-----------------------------
245 // Return nonzero index of invariant operand for an Add or Sub
246 // of (nonconstant) invariant and variant values. Helper for reassociate_invariants.
247 int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {
248 int op = n->Opcode();
249 if (op == Op_AddI || op == Op_SubI) {
250 bool in1_invar = this->is_invariant(n->in(1));
251 bool in2_invar = this->is_invariant(n->in(2));
252 if (in1_invar && !in2_invar) return 1;
253 if (!in1_invar && in2_invar) return 2;
254 }
255 return 0;
256 }
257
258 //---------------------reassociate_add_sub-----------------------------
259 // Reassociate invariant add and subtract expressions:
260 //
261 // inv1 + (x + inv2) => ( inv1 + inv2) + x
262 // (x + inv2) + inv1 => ( inv1 + inv2) + x
263 // inv1 + (x - inv2) => ( inv1 - inv2) + x
264 // inv1 - (inv2 - x) => ( inv1 - inv2) + x
265 // (x + inv2) - inv1 => (-inv1 + inv2) + x
266 // (x - inv2) + inv1 => ( inv1 - inv2) + x
267 // (x - inv2) - inv1 => (-inv1 - inv2) + x
268 // inv1 + (inv2 - x) => ( inv1 + inv2) - x
269 // inv1 - (x - inv2) => ( inv1 + inv2) - x
270 // (inv2 - x) + inv1 => ( inv1 + inv2) - x
271 // (inv2 - x) - inv1 => (-inv1 + inv2) - x
272 // inv1 - (x + inv2) => ( inv1 - inv2) - x
273 //
274 Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {
275 if ((!n1->is_Add() && !n1->is_Sub()) || n1->outcnt() == 0) return NULL;
276 if (is_invariant(n1)) return NULL;
277 int inv1_idx = is_invariant_addition(n1, phase);
278 if (!inv1_idx) return NULL;
279 // Don't mess with add of constant (igvn moves them to expression tree root.)
280 if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;
281 Node* inv1 = n1->in(inv1_idx);
282 Node* n2 = n1->in(3 - inv1_idx);
283 int inv2_idx = is_invariant_addition(n2, phase);
284 if (!inv2_idx) return NULL;
285 Node* x = n2->in(3 - inv2_idx);
286 Node* inv2 = n2->in(inv2_idx);
287
288 bool neg_x = n2->is_Sub() && inv2_idx == 1;
289 bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;
290 bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;
291 if (n1->is_Sub() && inv1_idx == 1) {
292 neg_x = !neg_x;
293 neg_inv2 = !neg_inv2;
294 }
295 Node* inv1_c = phase->get_ctrl(inv1);
296 Node* inv2_c = phase->get_ctrl(inv2);
297 Node* n_inv1;
298 if (neg_inv1) {
299 Node *zero = phase->_igvn.intcon(0);
300 phase->set_ctrl(zero, phase->C->root());
301 n_inv1 = new SubINode(zero, inv1);
302 phase->register_new_node(n_inv1, inv1_c);
303 } else {
304 n_inv1 = inv1;
305 }
306 Node* inv;
307 if (neg_inv2) {
308 inv = new SubINode(n_inv1, inv2);
309 } else {
310 inv = new AddINode(n_inv1, inv2);
311 }
312 phase->register_new_node(inv, phase->get_early_ctrl(inv));
313
314 Node* addx;
315 if (neg_x) {
316 addx = new SubINode(inv, x);
317 } else {
318 addx = new AddINode(x, inv);
319 }
320 phase->register_new_node(addx, phase->get_ctrl(x));
321 phase->_igvn.replace_node(n1, addx);
322 assert(phase->get_loop(phase->get_ctrl(n1)) == this, "");
323 _body.yank(n1);
324 return addx;
325 }
326
327 //---------------------reassociate_invariants-----------------------------
328 // Reassociate invariant expressions:
329 void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {
330 for (int i = _body.size() - 1; i >= 0; i--) {
331 Node *n = _body.at(i);
332 for (int j = 0; j < 5; j++) {
333 Node* nn = reassociate_add_sub(n, phase);
334 if (nn == NULL) break;
335 n = nn; // again
336 };
337 }
338 }
339
340 //------------------------------policy_peeling---------------------------------
341 // Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
342 // make some loop-invariant test (usually a null-check) happen before the loop.
343 bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {
344 Node *test = ((IdealLoopTree*)this)->tail();
345 int body_size = ((IdealLoopTree*)this)->_body.size();
346 // Peeling does loop cloning which can result in O(N^2) node construction
347 if( body_size > 255 /* Prevent overflow for large body_size */
348 || (body_size * body_size + phase->C->live_nodes()) > phase->C->max_node_limit() ) {
349 return false; // too large to safely clone
350 }
351
352 // check for vectorized loops, any peeling done was already applied
353 if (_head->is_CountedLoop() && _head->as_CountedLoop()->do_unroll_only()) return false;
354
355 while( test != _head ) { // Scan till run off top of loop
356 if( test->is_If() ) { // Test?
357 Node *ctrl = phase->get_ctrl(test->in(1));
358 if (ctrl->is_top())
359 return false; // Found dead test on live IF? No peeling!
360 // Standard IF only has one input value to check for loop invariance
361 assert(test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd || test->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
362 // Condition is not a member of this loop?
363 if( !is_member(phase->get_loop(ctrl)) &&
364 is_loop_exit(test) )
365 return true; // Found reason to peel!
366 }
367 // Walk up dominators to loop _head looking for test which is
368 // executed on every path thru loop.
369 test = phase->idom(test);
370 }
371 return false;
372 }
373
374 //------------------------------peeled_dom_test_elim---------------------------
375 // If we got the effect of peeling, either by actually peeling or by making
376 // a pre-loop which must execute at least once, we can remove all
377 // loop-invariant dominated tests in the main body.
378 void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {
379 bool progress = true;
380 while( progress ) {
381 progress = false; // Reset for next iteration
382 Node *prev = loop->_head->in(LoopNode::LoopBackControl);//loop->tail();
383 Node *test = prev->in(0);
384 while( test != loop->_head ) { // Scan till run off top of loop
385
386 int p_op = prev->Opcode();
387 if( (p_op == Op_IfFalse || p_op == Op_IfTrue) &&
388 test->is_If() && // Test?
389 !test->in(1)->is_Con() && // And not already obvious?
390 // Condition is not a member of this loop?
391 !loop->is_member(get_loop(get_ctrl(test->in(1))))){
392 // Walk loop body looking for instances of this test
393 for( uint i = 0; i < loop->_body.size(); i++ ) {
394 Node *n = loop->_body.at(i);
395 if( n->is_If() && n->in(1) == test->in(1) /*&& n != loop->tail()->in(0)*/ ) {
396 // IfNode was dominated by version in peeled loop body
397 progress = true;
398 dominated_by( old_new[prev->_idx], n );
399 }
400 }
401 }
402 prev = test;
403 test = idom(test);
404 } // End of scan tests in loop
405
406 } // End of while( progress )
407 }
408
409 //------------------------------do_peeling-------------------------------------
410 // Peel the first iteration of the given loop.
411 // Step 1: Clone the loop body. The clone becomes the peeled iteration.
412 // The pre-loop illegally has 2 control users (old & new loops).
413 // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
414 // Do this by making the old-loop fall-in edges act as if they came
415 // around the loopback from the prior iteration (follow the old-loop
416 // backedges) and then map to the new peeled iteration. This leaves
417 // the pre-loop with only 1 user (the new peeled iteration), but the
418 // peeled-loop backedge has 2 users.
419 // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
420 // extra backedge user.
421 //
422 // orig
423 //
424 // stmt1
425 // |
426 // v
427 // loop predicate
428 // |
429 // v
430 // loop<----+
431 // | |
432 // stmt2 |
433 // | |
434 // v |
435 // if ^
436 // / \ |
437 // / \ |
438 // v v |
439 // false true |
440 // / \ |
441 // / ----+
442 // |
443 // v
444 // exit
445 //
446 //
447 // after clone loop
448 //
449 // stmt1
450 // |
451 // v
452 // loop predicate
453 // / \
454 // clone / \ orig
455 // / \
456 // / \
457 // v v
458 // +---->loop clone loop<----+
459 // | | | |
460 // | stmt2 clone stmt2 |
461 // | | | |
462 // | v v |
463 // ^ if clone If ^
464 // | / \ / \ |
465 // | / \ / \ |
466 // | v v v v |
467 // | true false false true |
468 // | / \ / \ |
469 // +---- \ / ----+
470 // \ /
471 // 1v v2
472 // region
473 // |
474 // v
475 // exit
476 //
477 //
478 // after peel and predicate move
479 //
480 // stmt1
481 // /
482 // /
483 // clone / orig
484 // /
485 // / +----------+
486 // / | |
487 // / loop predicate |
488 // / | |
489 // v v |
490 // TOP-->loop clone loop<----+ |
491 // | | | |
492 // stmt2 clone stmt2 | |
493 // | | | ^
494 // v v | |
495 // if clone If ^ |
496 // / \ / \ | |
497 // / \ / \ | |
498 // v v v v | |
499 // true false false true | |
500 // | \ / \ | |
501 // | \ / ----+ ^
502 // | \ / |
503 // | 1v v2 |
504 // v region |
505 // | | |
506 // | v |
507 // | exit |
508 // | |
509 // +--------------->-----------------+
510 //
511 //
512 // final graph
513 //
514 // stmt1
515 // |
516 // v
517 // stmt2 clone
518 // |
519 // v
520 // if clone
521 // / |
522 // / |
523 // v v
524 // false true
525 // | |
526 // | v
527 // | loop predicate
528 // | |
529 // | v
530 // | loop<----+
531 // | | |
532 // | stmt2 |
533 // | | |
534 // | v |
535 // v if ^
536 // | / \ |
537 // | / \ |
538 // | v v |
539 // | false true |
540 // | | \ |
541 // v v --+
542 // region
543 // |
544 // v
545 // exit
546 //
547 void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {
548
549 C->set_major_progress();
550 // Peeling a 'main' loop in a pre/main/post situation obfuscates the
551 // 'pre' loop from the main and the 'pre' can no longer have its
552 // iterations adjusted. Therefore, we need to declare this loop as
553 // no longer a 'main' loop; it will need new pre and post loops before
554 // we can do further RCE.
555 #ifndef PRODUCT
556 if (TraceLoopOpts) {
557 tty->print("Peel ");
558 loop->dump_head();
559 }
560 #endif
561 LoopNode* head = loop->_head->as_Loop();
562 bool counted_loop = head->is_CountedLoop();
563 if (counted_loop) {
564 CountedLoopNode *cl = head->as_CountedLoop();
565 assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
566 cl->set_trip_count(cl->trip_count() - 1);
567 if (cl->is_main_loop()) {
568 cl->set_normal_loop();
569 #ifndef PRODUCT
570 if (PrintOpto && VerifyLoopOptimizations) {
571 tty->print("Peeling a 'main' loop; resetting to 'normal' ");
572 loop->dump_head();
573 }
574 #endif
575 }
576 }
577 Node* entry = head->in(LoopNode::EntryControl);
578
579 // Step 1: Clone the loop body. The clone becomes the peeled iteration.
580 // The pre-loop illegally has 2 control users (old & new loops).
581 clone_loop(loop, old_new, dom_depth(head->skip_strip_mined()), ControlAroundStripMined);
582
583 // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
584 // Do this by making the old-loop fall-in edges act as if they came
585 // around the loopback from the prior iteration (follow the old-loop
586 // backedges) and then map to the new peeled iteration. This leaves
587 // the pre-loop with only 1 user (the new peeled iteration), but the
588 // peeled-loop backedge has 2 users.
589 Node* new_entry = old_new[head->in(LoopNode::LoopBackControl)->_idx];
590 _igvn.hash_delete(head->skip_strip_mined());
591 head->skip_strip_mined()->set_req(LoopNode::EntryControl, new_entry);
592 for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) {
593 Node* old = head->fast_out(j);
594 if (old->in(0) == loop->_head && old->req() == 3 && old->is_Phi()) {
595 Node* new_exit_value = old_new[old->in(LoopNode::LoopBackControl)->_idx];
596 if (!new_exit_value ) // Backedge value is ALSO loop invariant?
597 // Then loop body backedge value remains the same.
598 new_exit_value = old->in(LoopNode::LoopBackControl);
599 _igvn.hash_delete(old);
600 old->set_req(LoopNode::EntryControl, new_exit_value);
601 }
602 }
603
604
605 // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
606 // extra backedge user.
607 Node* new_head = old_new[head->_idx];
608 _igvn.hash_delete(new_head);
609 new_head->set_req(LoopNode::LoopBackControl, C->top());
610 for (DUIterator_Fast j2max, j2 = new_head->fast_outs(j2max); j2 < j2max; j2++) {
611 Node* use = new_head->fast_out(j2);
612 if (use->in(0) == new_head && use->req() == 3 && use->is_Phi()) {
613 _igvn.hash_delete(use);
614 use->set_req(LoopNode::LoopBackControl, C->top());
615 }
616 }
617
618
619 // Step 4: Correct dom-depth info. Set to loop-head depth.
620 int dd = dom_depth(head);
621 set_idom(head, head->in(1), dd);
622 for (uint j3 = 0; j3 < loop->_body.size(); j3++) {
623 Node *old = loop->_body.at(j3);
624 Node *nnn = old_new[old->_idx];
625 if (!has_ctrl(nnn))
626 set_idom(nnn, idom(nnn), dd-1);
627 }
628
629 // Now force out all loop-invariant dominating tests. The optimizer
630 // finds some, but we _know_ they are all useless.
631 peeled_dom_test_elim(loop,old_new);
632
633 loop->record_for_igvn();
634 }
635
636 #define EMPTY_LOOP_SIZE 7 // number of nodes in an empty loop
637
638 //------------------------------policy_maximally_unroll------------------------
639 // Calculate exact loop trip count and return true if loop can be maximally
640 // unrolled.
641 bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const {
642 CountedLoopNode *cl = _head->as_CountedLoop();
643 assert(cl->is_normal_loop(), "");
644 if (!cl->is_valid_counted_loop())
645 return false; // Malformed counted loop
646
647 if (!cl->has_exact_trip_count()) {
648 // Trip count is not exact.
649 return false;
650 }
651
652 uint trip_count = cl->trip_count();
653 // Note, max_juint is used to indicate unknown trip count.
654 assert(trip_count > 1, "one iteration loop should be optimized out already");
655 assert(trip_count < max_juint, "exact trip_count should be less than max_uint.");
656
657 // Real policy: if we maximally unroll, does it get too big?
658 // Allow the unrolled mess to get larger than standard loop
659 // size. After all, it will no longer be a loop.
660 uint body_size = _body.size();
661 uint unroll_limit = (uint)LoopUnrollLimit * 4;
662 assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");
663 if (trip_count > unroll_limit || body_size > unroll_limit) {
664 return false;
665 }
666
667 // Fully unroll a loop with few iterations regardless next
668 // conditions since following loop optimizations will split
669 // such loop anyway (pre-main-post).
670 if (trip_count <= 3)
671 return true;
672
673 // Take into account that after unroll conjoined heads and tails will fold,
674 // otherwise policy_unroll() may allow more unrolling than max unrolling.
675 uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count;
676 uint tst_body_size = (new_body_size - EMPTY_LOOP_SIZE) / trip_count + EMPTY_LOOP_SIZE;
677 if (body_size != tst_body_size) // Check for int overflow
678 return false;
679 if (new_body_size > unroll_limit ||
680 // Unrolling can result in a large amount of node construction
681 new_body_size >= phase->C->max_node_limit() - phase->C->live_nodes()) {
682 return false;
683 }
684
685 // Do not unroll a loop with String intrinsics code.
686 // String intrinsics are large and have loops.
687 for (uint k = 0; k < _body.size(); k++) {
688 Node* n = _body.at(k);
689 switch (n->Opcode()) {
690 case Op_StrComp:
691 case Op_StrEquals:
692 case Op_StrIndexOf:
693 case Op_StrIndexOfChar:
694 case Op_EncodeISOArray:
695 case Op_AryEq:
696 case Op_HasNegatives: {
697 return false;
698 }
699 #if INCLUDE_RTM_OPT
700 case Op_FastLock:
701 case Op_FastUnlock: {
702 // Don't unroll RTM locking code because it is large.
703 if (UseRTMLocking) {
704 return false;
705 }
706 }
707 #endif
708 } // switch
709 }
710
711 return true; // Do maximally unroll
712 }
713
714
715 //------------------------------policy_unroll----------------------------------
716 // Return TRUE or FALSE if the loop should be unrolled or not. Unroll if
717 // the loop is a CountedLoop and the body is small enough.
718 bool IdealLoopTree::policy_unroll(PhaseIdealLoop *phase) {
719
720 CountedLoopNode *cl = _head->as_CountedLoop();
721 assert(cl->is_normal_loop() || cl->is_main_loop(), "");
722
723 if (!cl->is_valid_counted_loop())
724 return false; // Malformed counted loop
725
726 // Protect against over-unrolling.
727 // After split at least one iteration will be executed in pre-loop.
728 if (cl->trip_count() <= (uint)(cl->is_normal_loop() ? 2 : 1)) return false;
729
730 _local_loop_unroll_limit = LoopUnrollLimit;
731 _local_loop_unroll_factor = 4;
732 int future_unroll_ct = cl->unrolled_count() * 2;
733 if (!cl->is_vectorized_loop()) {
734 if (future_unroll_ct > LoopMaxUnroll) return false;
735 } else {
736 // obey user constraints on vector mapped loops with additional unrolling applied
737 int unroll_constraint = (cl->slp_max_unroll()) ? cl->slp_max_unroll() : 1;
738 if ((future_unroll_ct / unroll_constraint) > LoopMaxUnroll) return false;
739 }
740
741 // Check for initial stride being a small enough constant
742 if (abs(cl->stride_con()) > (1<<2)*future_unroll_ct) return false;
743
744 // Don't unroll if the next round of unrolling would push us
745 // over the expected trip count of the loop. One is subtracted
746 // from the expected trip count because the pre-loop normally
747 // executes 1 iteration.
748 if (UnrollLimitForProfileCheck > 0 &&
749 cl->profile_trip_cnt() != COUNT_UNKNOWN &&
750 future_unroll_ct > UnrollLimitForProfileCheck &&
751 (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
752 return false;
753 }
754
755 // When unroll count is greater than LoopUnrollMin, don't unroll if:
756 // the residual iterations are more than 10% of the trip count
757 // and rounds of "unroll,optimize" are not making significant progress
758 // Progress defined as current size less than 20% larger than previous size.
759 if (UseSuperWord && cl->node_count_before_unroll() > 0 &&
760 future_unroll_ct > LoopUnrollMin &&
761 (future_unroll_ct - 1) * (100 / LoopPercentProfileLimit) > cl->profile_trip_cnt() &&
762 1.2 * cl->node_count_before_unroll() < (double)_body.size()) {
763 return false;
764 }
765
766 Node *init_n = cl->init_trip();
767 Node *limit_n = cl->limit();
768 int stride_con = cl->stride_con();
769 // Non-constant bounds.
770 // Protect against over-unrolling when init or/and limit are not constant
771 // (so that trip_count's init value is maxint) but iv range is known.
772 if (init_n == NULL || !init_n->is_Con() ||
773 limit_n == NULL || !limit_n->is_Con()) {
774 Node* phi = cl->phi();
775 if (phi != NULL) {
776 assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");
777 const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();
778 int next_stride = stride_con * 2; // stride after this unroll
779 if (next_stride > 0) {
780 if (iv_type->_lo + next_stride <= iv_type->_lo || // overflow
781 iv_type->_lo + next_stride > iv_type->_hi) {
782 return false; // over-unrolling
783 }
784 } else if (next_stride < 0) {
785 if (iv_type->_hi + next_stride >= iv_type->_hi || // overflow
786 iv_type->_hi + next_stride < iv_type->_lo) {
787 return false; // over-unrolling
788 }
789 }
790 }
791 }
792
793 // After unroll limit will be adjusted: new_limit = limit-stride.
794 // Bailout if adjustment overflow.
795 const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();
796 if ((stride_con > 0 && ((limit_type->_hi - stride_con) >= limit_type->_hi)) ||
797 (stride_con < 0 && ((limit_type->_lo - stride_con) <= limit_type->_lo)))
798 return false; // overflow
799
800 // Adjust body_size to determine if we unroll or not
801 uint body_size = _body.size();
802 // Key test to unroll loop in CRC32 java code
803 int xors_in_loop = 0;
804 // Also count ModL, DivL and MulL which expand mightly
805 for (uint k = 0; k < _body.size(); k++) {
806 Node* n = _body.at(k);
807 switch (n->Opcode()) {
808 case Op_XorI: xors_in_loop++; break; // CRC32 java code
809 case Op_ModL: body_size += 30; break;
810 case Op_DivL: body_size += 30; break;
811 case Op_MulL: body_size += 10; break;
812 case Op_StrComp:
813 case Op_StrEquals:
814 case Op_StrIndexOf:
815 case Op_StrIndexOfChar:
816 case Op_EncodeISOArray:
817 case Op_AryEq:
818 case Op_HasNegatives: {
819 // Do not unroll a loop with String intrinsics code.
820 // String intrinsics are large and have loops.
821 return false;
822 }
823 #if INCLUDE_RTM_OPT
824 case Op_FastLock:
825 case Op_FastUnlock: {
826 // Don't unroll RTM locking code because it is large.
827 if (UseRTMLocking) {
828 return false;
829 }
830 }
831 #endif
832 } // switch
833 }
834
835 if (UseSuperWord) {
836 if (!cl->is_reduction_loop()) {
837 phase->mark_reductions(this);
838 }
839
840 // Only attempt slp analysis when user controls do not prohibit it
841 if (LoopMaxUnroll > _local_loop_unroll_factor) {
842 // Once policy_slp_analysis succeeds, mark the loop with the
843 // maximal unroll factor so that we minimize analysis passes
844 if (future_unroll_ct >= _local_loop_unroll_factor) {
845 policy_unroll_slp_analysis(cl, phase, future_unroll_ct);
846 }
847 }
848 }
849
850 int slp_max_unroll_factor = cl->slp_max_unroll();
851 if ((LoopMaxUnroll < slp_max_unroll_factor) && FLAG_IS_DEFAULT(LoopMaxUnroll) && UseSubwordForMaxVector) {
852 LoopMaxUnroll = slp_max_unroll_factor;
853 }
854 if (cl->has_passed_slp()) {
855 if (slp_max_unroll_factor >= future_unroll_ct) return true;
856 // Normal case: loop too big
857 return false;
858 }
859
860 // Check for being too big
861 if (body_size > (uint)_local_loop_unroll_limit) {
862 if ((UseSubwordForMaxVector || xors_in_loop >= 4) && body_size < (uint)LoopUnrollLimit * 4) return true;
863 // Normal case: loop too big
864 return false;
865 }
866
867 if (cl->do_unroll_only()) {
868 if (TraceSuperWordLoopUnrollAnalysis) {
869 tty->print_cr("policy_unroll passed vector loop(vlen=%d,factor = %d)\n", slp_max_unroll_factor, future_unroll_ct);
870 }
871 }
872
873 // Unroll once! (Each trip will soon do double iterations)
874 return true;
875 }
876
877 void IdealLoopTree::policy_unroll_slp_analysis(CountedLoopNode *cl, PhaseIdealLoop *phase, int future_unroll_ct) {
878 // Enable this functionality target by target as needed
879 if (SuperWordLoopUnrollAnalysis) {
880 if (!cl->was_slp_analyzed()) {
881 SuperWord sw(phase);
882 sw.transform_loop(this, false);
883
884 // If the loop is slp canonical analyze it
885 if (sw.early_return() == false) {
886 sw.unrolling_analysis(_local_loop_unroll_factor);
887 }
888 }
889
890 if (cl->has_passed_slp()) {
891 int slp_max_unroll_factor = cl->slp_max_unroll();
892 if (slp_max_unroll_factor >= future_unroll_ct) {
893 int new_limit = cl->node_count_before_unroll() * slp_max_unroll_factor;
894 if (new_limit > LoopUnrollLimit) {
895 if (TraceSuperWordLoopUnrollAnalysis) {
896 tty->print_cr("slp analysis unroll=%d, default limit=%d\n", new_limit, _local_loop_unroll_limit);
897 }
898 _local_loop_unroll_limit = new_limit;
899 }
900 }
901 }
902 }
903 }
904
905 //------------------------------policy_align-----------------------------------
906 // Return TRUE or FALSE if the loop should be cache-line aligned. Gather the
907 // expression that does the alignment. Note that only one array base can be
908 // aligned in a loop (unless the VM guarantees mutual alignment). Note that
909 // if we vectorize short memory ops into longer memory ops, we may want to
910 // increase alignment.
911 bool IdealLoopTree::policy_align( PhaseIdealLoop *phase ) const {
912 return false;
913 }
914
915 //------------------------------policy_range_check-----------------------------
916 // Return TRUE or FALSE if the loop should be range-check-eliminated.
917 // Actually we do iteration-splitting, a more powerful form of RCE.
918 bool IdealLoopTree::policy_range_check( PhaseIdealLoop *phase ) const {
919 if (!RangeCheckElimination) return false;
920
921 CountedLoopNode *cl = _head->as_CountedLoop();
922 // If we unrolled with no intention of doing RCE and we later
923 // changed our minds, we got no pre-loop. Either we need to
924 // make a new pre-loop, or we gotta disallow RCE.
925 if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
926 Node *trip_counter = cl->phi();
927
928 // check for vectorized loops, some opts are no longer needed
929 if (cl->do_unroll_only()) return false;
930
931 // Check loop body for tests of trip-counter plus loop-invariant vs
932 // loop-invariant.
933 for (uint i = 0; i < _body.size(); i++) {
934 Node *iff = _body[i];
935 if (iff->Opcode() == Op_If ||
936 iff->Opcode() == Op_RangeCheck) { // Test?
937
938 // Comparing trip+off vs limit
939 Node *bol = iff->in(1);
940 if (bol->req() != 2) continue; // dead constant test
941 if (!bol->is_Bool()) {
942 assert(bol->Opcode() == Op_Conv2B, "predicate check only");
943 continue;
944 }
945 if (bol->as_Bool()->_test._test == BoolTest::ne)
946 continue; // not RC
947
948 Node *cmp = bol->in(1);
949 Node *rc_exp = cmp->in(1);
950 Node *limit = cmp->in(2);
951
952 Node *limit_c = phase->get_ctrl(limit);
953 if( limit_c == phase->C->top() )
954 return false; // Found dead test on live IF? No RCE!
955 if( is_member(phase->get_loop(limit_c) ) ) {
956 // Compare might have operands swapped; commute them
957 rc_exp = cmp->in(2);
958 limit = cmp->in(1);
959 limit_c = phase->get_ctrl(limit);
960 if( is_member(phase->get_loop(limit_c) ) )
961 continue; // Both inputs are loop varying; cannot RCE
962 }
963
964 if (!phase->is_scaled_iv_plus_offset(rc_exp, trip_counter, NULL, NULL)) {
965 continue;
966 }
967 // Yeah! Found a test like 'trip+off vs limit'
968 // Test is an IfNode, has 2 projections. If BOTH are in the loop
969 // we need loop unswitching instead of iteration splitting.
970 if( is_loop_exit(iff) )
971 return true; // Found reason to split iterations
972 } // End of is IF
973 }
974
975 return false;
976 }
977
978 //------------------------------policy_peel_only-------------------------------
979 // Return TRUE or FALSE if the loop should NEVER be RCE'd or aligned. Useful
980 // for unrolling loops with NO array accesses.
981 bool IdealLoopTree::policy_peel_only( PhaseIdealLoop *phase ) const {
982 // check for vectorized loops, any peeling done was already applied
983 if (_head->is_CountedLoop() && _head->as_CountedLoop()->do_unroll_only()) return false;
984
985 for( uint i = 0; i < _body.size(); i++ )
986 if( _body[i]->is_Mem() )
987 return false;
988
989 // No memory accesses at all!
990 return true;
991 }
992
993 //------------------------------clone_up_backedge_goo--------------------------
994 // If Node n lives in the back_ctrl block and cannot float, we clone a private
995 // version of n in preheader_ctrl block and return that, otherwise return n.
996 Node *PhaseIdealLoop::clone_up_backedge_goo( Node *back_ctrl, Node *preheader_ctrl, Node *n, VectorSet &visited, Node_Stack &clones ) {
997 if( get_ctrl(n) != back_ctrl ) return n;
998
999 // Only visit once
1000 if (visited.test_set(n->_idx)) {
1001 Node *x = clones.find(n->_idx);
1002 if (x != NULL)
1003 return x;
1004 return n;
1005 }
1006
1007 Node *x = NULL; // If required, a clone of 'n'
1008 // Check for 'n' being pinned in the backedge.
1009 if( n->in(0) && n->in(0) == back_ctrl ) {
1010 assert(clones.find(n->_idx) == NULL, "dead loop");
1011 x = n->clone(); // Clone a copy of 'n' to preheader
1012 clones.push(x, n->_idx);
1013 x->set_req( 0, preheader_ctrl ); // Fix x's control input to preheader
1014 }
1015
1016 // Recursive fixup any other input edges into x.
1017 // If there are no changes we can just return 'n', otherwise
1018 // we need to clone a private copy and change it.
1019 for( uint i = 1; i < n->req(); i++ ) {
1020 Node *g = clone_up_backedge_goo( back_ctrl, preheader_ctrl, n->in(i), visited, clones );
1021 if( g != n->in(i) ) {
1022 if( !x ) {
1023 assert(clones.find(n->_idx) == NULL, "dead loop");
1024 x = n->clone();
1025 clones.push(x, n->_idx);
1026 }
1027 x->set_req(i, g);
1028 }
1029 }
1030 if( x ) { // x can legally float to pre-header location
1031 register_new_node( x, preheader_ctrl );
1032 return x;
1033 } else { // raise n to cover LCA of uses
1034 set_ctrl( n, find_non_split_ctrl(back_ctrl->in(0)) );
1035 }
1036 return n;
1037 }
1038
1039 Node* PhaseIdealLoop::cast_incr_before_loop(Node* incr, Node* ctrl, Node* loop) {
1040 Node* castii = new CastIINode(incr, TypeInt::INT, true);
1041 castii->set_req(0, ctrl);
1042 register_new_node(castii, ctrl);
1043 for (DUIterator_Fast imax, i = incr->fast_outs(imax); i < imax; i++) {
1044 Node* n = incr->fast_out(i);
1045 if (n->is_Phi() && n->in(0) == loop) {
1046 int nrep = n->replace_edge(incr, castii);
1047 return castii;
1048 }
1049 }
1050 return NULL;
1051 }
1052
1053 // Make a copy of the skeleton range check predicates before the main
1054 // loop and set the initial value of loop as input. After unrolling,
1055 // the range of values for the induction variable in the main loop can
1056 // fall outside the allowed range of values by the array access (main
1057 // loop is never executed). When that happens, range check
1058 // CastII/ConvI2L nodes cause some data paths to die. For consistency,
1059 // the control paths must die too but the range checks were removed by
1060 // predication. The range checks that we add here guarantee that they
1061 // do.
1062 void PhaseIdealLoop::duplicate_predicates_helper(Node* predicate, Node* castii, IdealLoopTree* outer_loop,
1063 LoopNode* outer_main_head, uint dd_main_head) {
1064 if (predicate != NULL) {
1065 IfNode* iff = predicate->in(0)->as_If();
1066 ProjNode* uncommon_proj = iff->proj_out(1 - predicate->as_Proj()->_con);
1067 Node* rgn = uncommon_proj->unique_ctrl_out();
1068 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
1069 assert(iff->in(1)->in(1)->Opcode() == Op_Opaque1, "unexpected predicate shape");
1070 predicate = predicate->in(0)->in(0);
1071 Node* current_proj = outer_main_head->in(LoopNode::EntryControl);
1072 Node* prev_proj = current_proj;
1073 while (predicate != NULL && predicate->is_Proj() && predicate->in(0)->is_If()) {
1074 uncommon_proj = predicate->in(0)->as_If()->proj_out(1 - predicate->as_Proj()->_con);
1075 if (uncommon_proj->unique_ctrl_out() != rgn)
1076 break;
1077 iff = predicate->in(0)->as_If();
1078 if (iff->in(1)->Opcode() == Op_Opaque4) {
1079 Node_Stack to_clone(2);
1080 to_clone.push(iff->in(1), 1);
1081 uint current = C->unique();
1082 Node* result = NULL;
1083 // Look for the opaque node to replace with the init value
1084 // and clone everything in between. We keep the Opaque4 node
1085 // so the duplicated predicates are eliminated once loop
1086 // opts are over: they are here only to keep the IR graph
1087 // consistent.
1088 do {
1089 Node* n = to_clone.node();
1090 uint i = to_clone.index();
1091 Node* m = n->in(i);
1092 int op = m->Opcode();
1093 if (m->is_Bool() ||
1094 m->is_Cmp() ||
1095 op == Op_AndL ||
1096 op == Op_OrL ||
1097 op == Op_RShiftL ||
1098 op == Op_LShiftL ||
1099 op == Op_AddL ||
1100 op == Op_AddI ||
1101 op == Op_MulL ||
1102 op == Op_MulI ||
1103 op == Op_SubL ||
1104 op == Op_SubI ||
1105 op == Op_ConvI2L) {
1106 to_clone.push(m, 1);
1107 continue;
1108 }
1109 if (op == Op_Opaque1) {
1110 if (n->_idx < current) {
1111 n = n->clone();
1112 }
1113 n->set_req(i, castii);
1114 register_new_node(n, current_proj);
1115 to_clone.set_node(n);
1116 }
1117 for (;;) {
1118 Node* cur = to_clone.node();
1119 uint j = to_clone.index();
1120 if (j+1 < cur->req()) {
1121 to_clone.set_index(j+1);
1122 break;
1123 }
1124 to_clone.pop();
1125 if (to_clone.size() == 0) {
1126 result = cur;
1127 break;
1128 }
1129 Node* next = to_clone.node();
1130 j = to_clone.index();
1131 if (cur->_idx >= current) {
1132 if (next->_idx < current) {
1133 next = next->clone();
1134 register_new_node(next, current_proj);
1135 to_clone.set_node(next);
1136 }
1137 assert(next->in(j) != cur, "input should have been cloned");
1138 next->set_req(j, cur);
1139 }
1140 }
1141 } while (result == NULL);
1142 assert(result->_idx >= current, "new node expected");
1143
1144 Node* proj = predicate->clone();
1145 Node* other_proj = uncommon_proj->clone();
1146 Node* new_iff = iff->clone();
1147 new_iff->set_req(1, result);
1148 proj->set_req(0, new_iff);
1149 other_proj->set_req(0, new_iff);
1150 Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
1151 register_new_node(frame, C->start());
1152 // It's impossible for the predicate to fail at runtime. Use
1153 // an Halt node.
1154 Node* halt = new HaltNode(other_proj, frame);
1155 C->root()->add_req(halt);
1156 new_iff->set_req(0, prev_proj);
1157
1158 register_control(new_iff, outer_loop->_parent, prev_proj);
1159 register_control(proj, outer_loop->_parent, new_iff);
1160 register_control(other_proj, _ltree_root, new_iff);
1161 register_control(halt, _ltree_root, other_proj);
1162
1163 prev_proj = proj;
1164 }
1165 predicate = predicate->in(0)->in(0);
1166 }
1167 if (prev_proj != current_proj) {
1168 _igvn.replace_input_of(outer_main_head, LoopNode::EntryControl, prev_proj);
1169 set_idom(outer_main_head, prev_proj, dd_main_head);
1170 }
1171 }
1172 }
1173
1174 void PhaseIdealLoop::duplicate_predicates(CountedLoopNode* pre_head, Node* castii, IdealLoopTree* outer_loop,
1175 LoopNode* outer_main_head, uint dd_main_head) {
1176 if (UseLoopPredicate) {
1177 Node* entry = pre_head->in(LoopNode::EntryControl);
1178 Node* predicate = NULL;
1179 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1180 if (predicate != NULL) {
1181 entry = entry->in(0)->in(0);
1182 }
1183 Node* profile_predicate = NULL;
1184 if (UseProfiledLoopPredicate) {
1185 profile_predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
1186 if (profile_predicate != NULL) {
1187 entry = skip_loop_predicates(entry);
1188 }
1189 }
1190 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1191 duplicate_predicates_helper(predicate, castii, outer_loop, outer_main_head, dd_main_head);
1192 duplicate_predicates_helper(profile_predicate, castii, outer_loop, outer_main_head, dd_main_head);
1193 }
1194 }
1195
1196 //------------------------------insert_pre_post_loops--------------------------
1197 // Insert pre and post loops. If peel_only is set, the pre-loop can not have
1198 // more iterations added. It acts as a 'peel' only, no lower-bound RCE, no
1199 // alignment. Useful to unroll loops that do no array accesses.
1200 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
1201
1202 #ifndef PRODUCT
1203 if (TraceLoopOpts) {
1204 if (peel_only)
1205 tty->print("PeelMainPost ");
1206 else
1207 tty->print("PreMainPost ");
1208 loop->dump_head();
1209 }
1210 #endif
1211 C->set_major_progress();
1212
1213 // Find common pieces of the loop being guarded with pre & post loops
1214 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1215 assert( main_head->is_normal_loop(), "" );
1216 CountedLoopEndNode *main_end = main_head->loopexit();
1217 assert( main_end->outcnt() == 2, "1 true, 1 false path only" );
1218
1219 Node *pre_header= main_head->in(LoopNode::EntryControl);
1220 Node *init = main_head->init_trip();
1221 Node *incr = main_end ->incr();
1222 Node *limit = main_end ->limit();
1223 Node *stride = main_end ->stride();
1224 Node *cmp = main_end ->cmp_node();
1225 BoolTest::mask b_test = main_end->test_trip();
1226
1227 // Need only 1 user of 'bol' because I will be hacking the loop bounds.
1228 Node *bol = main_end->in(CountedLoopEndNode::TestValue);
1229 if( bol->outcnt() != 1 ) {
1230 bol = bol->clone();
1231 register_new_node(bol,main_end->in(CountedLoopEndNode::TestControl));
1232 _igvn.replace_input_of(main_end, CountedLoopEndNode::TestValue, bol);
1233 }
1234 // Need only 1 user of 'cmp' because I will be hacking the loop bounds.
1235 if( cmp->outcnt() != 1 ) {
1236 cmp = cmp->clone();
1237 register_new_node(cmp,main_end->in(CountedLoopEndNode::TestControl));
1238 _igvn.replace_input_of(bol, 1, cmp);
1239 }
1240
1241 // Add the post loop
1242 CountedLoopNode *post_head = NULL;
1243 Node *main_exit = insert_post_loop(loop, old_new, main_head, main_end, incr, limit, post_head);
1244
1245 //------------------------------
1246 // Step B: Create Pre-Loop.
1247
1248 // Step B1: Clone the loop body. The clone becomes the pre-loop. The main
1249 // loop pre-header illegally has 2 control users (old & new loops).
1250 LoopNode* outer_main_head = main_head;
1251 IdealLoopTree* outer_loop = loop;
1252 if (main_head->is_strip_mined()) {
1253 main_head->verify_strip_mined(1);
1254 outer_main_head = main_head->outer_loop();
1255 outer_loop = loop->_parent;
1256 assert(outer_loop->_head == outer_main_head, "broken loop tree");
1257 }
1258 uint dd_main_head = dom_depth(outer_main_head);
1259 clone_loop(loop, old_new, dd_main_head, ControlAroundStripMined);
1260 CountedLoopNode* pre_head = old_new[main_head->_idx]->as_CountedLoop();
1261 CountedLoopEndNode* pre_end = old_new[main_end ->_idx]->as_CountedLoopEnd();
1262 pre_head->set_pre_loop(main_head);
1263 Node *pre_incr = old_new[incr->_idx];
1264
1265 // Reduce the pre-loop trip count.
1266 pre_end->_prob = PROB_FAIR;
1267
1268 // Find the pre-loop normal exit.
1269 Node* pre_exit = pre_end->proj_out(false);
1270 assert( pre_exit->Opcode() == Op_IfFalse, "" );
1271 IfFalseNode *new_pre_exit = new IfFalseNode(pre_end);
1272 _igvn.register_new_node_with_optimizer( new_pre_exit );
1273 set_idom(new_pre_exit, pre_end, dd_main_head);
1274 set_loop(new_pre_exit, outer_loop->_parent);
1275
1276 // Step B2: Build a zero-trip guard for the main-loop. After leaving the
1277 // pre-loop, the main-loop may not execute at all. Later in life this
1278 // zero-trip guard will become the minimum-trip guard when we unroll
1279 // the main-loop.
1280 Node *min_opaq = new Opaque1Node(C, limit);
1281 Node *min_cmp = new CmpINode( pre_incr, min_opaq );
1282 Node *min_bol = new BoolNode( min_cmp, b_test );
1283 register_new_node( min_opaq, new_pre_exit );
1284 register_new_node( min_cmp , new_pre_exit );
1285 register_new_node( min_bol , new_pre_exit );
1286
1287 // Build the IfNode (assume the main-loop is executed always).
1288 IfNode *min_iff = new IfNode( new_pre_exit, min_bol, PROB_ALWAYS, COUNT_UNKNOWN );
1289 _igvn.register_new_node_with_optimizer( min_iff );
1290 set_idom(min_iff, new_pre_exit, dd_main_head);
1291 set_loop(min_iff, outer_loop->_parent);
1292
1293 // Plug in the false-path, taken if we need to skip main-loop
1294 _igvn.hash_delete( pre_exit );
1295 pre_exit->set_req(0, min_iff);
1296 set_idom(pre_exit, min_iff, dd_main_head);
1297 set_idom(pre_exit->unique_ctrl_out(), min_iff, dd_main_head);
1298 // Make the true-path, must enter the main loop
1299 Node *min_taken = new IfTrueNode( min_iff );
1300 _igvn.register_new_node_with_optimizer( min_taken );
1301 set_idom(min_taken, min_iff, dd_main_head);
1302 set_loop(min_taken, outer_loop->_parent);
1303 // Plug in the true path
1304 _igvn.hash_delete(outer_main_head);
1305 outer_main_head->set_req(LoopNode::EntryControl, min_taken);
1306 set_idom(outer_main_head, min_taken, dd_main_head);
1307
1308 Arena *a = Thread::current()->resource_area();
1309 VectorSet visited(a);
1310 Node_Stack clones(a, main_head->back_control()->outcnt());
1311 // Step B3: Make the fall-in values to the main-loop come from the
1312 // fall-out values of the pre-loop.
1313 for (DUIterator_Fast i2max, i2 = main_head->fast_outs(i2max); i2 < i2max; i2++) {
1314 Node* main_phi = main_head->fast_out(i2);
1315 if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0 ) {
1316 Node *pre_phi = old_new[main_phi->_idx];
1317 Node *fallpre = clone_up_backedge_goo(pre_head->back_control(),
1318 main_head->skip_strip_mined()->in(LoopNode::EntryControl),
1319 pre_phi->in(LoopNode::LoopBackControl),
1320 visited, clones);
1321 _igvn.hash_delete(main_phi);
1322 main_phi->set_req( LoopNode::EntryControl, fallpre );
1323 }
1324 }
1325
1326 // Nodes inside the loop may be control dependent on a predicate
1327 // that was moved before the preloop. If the back branch of the main
1328 // or post loops becomes dead, those nodes won't be dependent on the
1329 // test that guards that loop nest anymore which could lead to an
1330 // incorrect array access because it executes independently of the
1331 // test that was guarding the loop nest. We add a special CastII on
1332 // the if branch that enters the loop, between the input induction
1333 // variable value and the induction variable Phi to preserve correct
1334 // dependencies.
1335
1336 // CastII for the main loop:
1337 Node* castii = cast_incr_before_loop( pre_incr, min_taken, main_head );
1338 assert(castii != NULL, "no castII inserted");
1339 duplicate_predicates(pre_head, castii, outer_loop, outer_main_head, dd_main_head);
1340
1341 // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1342 // RCE and alignment may change this later.
1343 Node *cmp_end = pre_end->cmp_node();
1344 assert( cmp_end->in(2) == limit, "" );
1345 Node *pre_limit = new AddINode( init, stride );
1346
1347 // Save the original loop limit in this Opaque1 node for
1348 // use by range check elimination.
1349 Node *pre_opaq = new Opaque1Node(C, pre_limit, limit);
1350
1351 register_new_node( pre_limit, pre_head->in(0) );
1352 register_new_node( pre_opaq , pre_head->in(0) );
1353
1354 // Since no other users of pre-loop compare, I can hack limit directly
1355 assert( cmp_end->outcnt() == 1, "no other users" );
1356 _igvn.hash_delete(cmp_end);
1357 cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1358
1359 // Special case for not-equal loop bounds:
1360 // Change pre loop test, main loop test, and the
1361 // main loop guard test to use lt or gt depending on stride
1362 // direction:
1363 // positive stride use <
1364 // negative stride use >
1365 //
1366 // not-equal test is kept for post loop to handle case
1367 // when init > limit when stride > 0 (and reverse).
1368
1369 if (pre_end->in(CountedLoopEndNode::TestValue)->as_Bool()->_test._test == BoolTest::ne) {
1370
1371 BoolTest::mask new_test = (main_end->stride_con() > 0) ? BoolTest::lt : BoolTest::gt;
1372 // Modify pre loop end condition
1373 Node* pre_bol = pre_end->in(CountedLoopEndNode::TestValue)->as_Bool();
1374 BoolNode* new_bol0 = new BoolNode(pre_bol->in(1), new_test);
1375 register_new_node( new_bol0, pre_head->in(0) );
1376 _igvn.replace_input_of(pre_end, CountedLoopEndNode::TestValue, new_bol0);
1377 // Modify main loop guard condition
1378 assert(min_iff->in(CountedLoopEndNode::TestValue) == min_bol, "guard okay");
1379 BoolNode* new_bol1 = new BoolNode(min_bol->in(1), new_test);
1380 register_new_node( new_bol1, new_pre_exit );
1381 _igvn.hash_delete(min_iff);
1382 min_iff->set_req(CountedLoopEndNode::TestValue, new_bol1);
1383 // Modify main loop end condition
1384 BoolNode* main_bol = main_end->in(CountedLoopEndNode::TestValue)->as_Bool();
1385 BoolNode* new_bol2 = new BoolNode(main_bol->in(1), new_test);
1386 register_new_node( new_bol2, main_end->in(CountedLoopEndNode::TestControl) );
1387 _igvn.replace_input_of(main_end, CountedLoopEndNode::TestValue, new_bol2);
1388 }
1389
1390 // Flag main loop
1391 main_head->set_main_loop();
1392 if( peel_only ) main_head->set_main_no_pre_loop();
1393
1394 // Subtract a trip count for the pre-loop.
1395 main_head->set_trip_count(main_head->trip_count() - 1);
1396
1397 // It's difficult to be precise about the trip-counts
1398 // for the pre/post loops. They are usually very short,
1399 // so guess that 4 trips is a reasonable value.
1400 post_head->set_profile_trip_cnt(4.0);
1401 pre_head->set_profile_trip_cnt(4.0);
1402
1403 // Now force out all loop-invariant dominating tests. The optimizer
1404 // finds some, but we _know_ they are all useless.
1405 peeled_dom_test_elim(loop,old_new);
1406 loop->record_for_igvn();
1407 }
1408
1409 //------------------------------insert_vector_post_loop------------------------
1410 // Insert a copy of the atomic unrolled vectorized main loop as a post loop,
1411 // unroll_policy has already informed us that more unrolling is about to happen to
1412 // the main loop. The resultant post loop will serve as a vectorized drain loop.
1413 void PhaseIdealLoop::insert_vector_post_loop(IdealLoopTree *loop, Node_List &old_new) {
1414 if (!loop->_head->is_CountedLoop()) return;
1415
1416 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1417
1418 // only process vectorized main loops
1419 if (!cl->is_vectorized_loop() || !cl->is_main_loop()) return;
1420
1421 int slp_max_unroll_factor = cl->slp_max_unroll();
1422 int cur_unroll = cl->unrolled_count();
1423
1424 if (slp_max_unroll_factor == 0) return;
1425
1426 // only process atomic unroll vector loops (not super unrolled after vectorization)
1427 if (cur_unroll != slp_max_unroll_factor) return;
1428
1429 // we only ever process this one time
1430 if (cl->has_atomic_post_loop()) return;
1431
1432 #ifndef PRODUCT
1433 if (TraceLoopOpts) {
1434 tty->print("PostVector ");
1435 loop->dump_head();
1436 }
1437 #endif
1438 C->set_major_progress();
1439
1440 // Find common pieces of the loop being guarded with pre & post loops
1441 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1442 CountedLoopEndNode *main_end = main_head->loopexit();
1443 // diagnostic to show loop end is not properly formed
1444 assert(main_end->outcnt() == 2, "1 true, 1 false path only");
1445
1446 // mark this loop as processed
1447 main_head->mark_has_atomic_post_loop();
1448
1449 Node *incr = main_end->incr();
1450 Node *limit = main_end->limit();
1451
1452 // In this case we throw away the result as we are not using it to connect anything else.
1453 CountedLoopNode *post_head = NULL;
1454 insert_post_loop(loop, old_new, main_head, main_end, incr, limit, post_head);
1455
1456 // It's difficult to be precise about the trip-counts
1457 // for post loops. They are usually very short,
1458 // so guess that unit vector trips is a reasonable value.
1459 post_head->set_profile_trip_cnt(cur_unroll);
1460
1461 // Now force out all loop-invariant dominating tests. The optimizer
1462 // finds some, but we _know_ they are all useless.
1463 peeled_dom_test_elim(loop, old_new);
1464 loop->record_for_igvn();
1465 }
1466
1467
1468 //-------------------------insert_scalar_rced_post_loop------------------------
1469 // Insert a copy of the rce'd main loop as a post loop,
1470 // We have not unrolled the main loop, so this is the right time to inject this.
1471 // Later we will examine the partner of this post loop pair which still has range checks
1472 // to see inject code which tests at runtime if the range checks are applicable.
1473 void PhaseIdealLoop::insert_scalar_rced_post_loop(IdealLoopTree *loop, Node_List &old_new) {
1474 if (!loop->_head->is_CountedLoop()) return;
1475
1476 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1477
1478 // only process RCE'd main loops
1479 if (!cl->is_main_loop() || cl->range_checks_present()) return;
1480
1481 #ifndef PRODUCT
1482 if (TraceLoopOpts) {
1483 tty->print("PostScalarRce ");
1484 loop->dump_head();
1485 }
1486 #endif
1487 C->set_major_progress();
1488
1489 // Find common pieces of the loop being guarded with pre & post loops
1490 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1491 CountedLoopEndNode *main_end = main_head->loopexit();
1492 // diagnostic to show loop end is not properly formed
1493 assert(main_end->outcnt() == 2, "1 true, 1 false path only");
1494
1495 Node *incr = main_end->incr();
1496 Node *limit = main_end->limit();
1497
1498 // In this case we throw away the result as we are not using it to connect anything else.
1499 CountedLoopNode *post_head = NULL;
1500 insert_post_loop(loop, old_new, main_head, main_end, incr, limit, post_head);
1501
1502 // It's difficult to be precise about the trip-counts
1503 // for post loops. They are usually very short,
1504 // so guess that unit vector trips is a reasonable value.
1505 post_head->set_profile_trip_cnt(4.0);
1506 post_head->set_is_rce_post_loop();
1507
1508 // Now force out all loop-invariant dominating tests. The optimizer
1509 // finds some, but we _know_ they are all useless.
1510 peeled_dom_test_elim(loop, old_new);
1511 loop->record_for_igvn();
1512 }
1513
1514
1515 //------------------------------insert_post_loop-------------------------------
1516 // Insert post loops. Add a post loop to the given loop passed.
1517 Node *PhaseIdealLoop::insert_post_loop(IdealLoopTree *loop, Node_List &old_new,
1518 CountedLoopNode *main_head, CountedLoopEndNode *main_end,
1519 Node *incr, Node *limit, CountedLoopNode *&post_head) {
1520 IfNode* outer_main_end = main_end;
1521 IdealLoopTree* outer_loop = loop;
1522 if (main_head->is_strip_mined()) {
1523 main_head->verify_strip_mined(1);
1524 outer_main_end = main_head->outer_loop_end();
1525 outer_loop = loop->_parent;
1526 assert(outer_loop->_head == main_head->in(LoopNode::EntryControl), "broken loop tree");
1527 }
1528
1529 //------------------------------
1530 // Step A: Create a new post-Loop.
1531 Node* main_exit = outer_main_end->proj_out(false);
1532 assert(main_exit->Opcode() == Op_IfFalse, "");
1533 int dd_main_exit = dom_depth(main_exit);
1534
1535 // Step A1: Clone the loop body of main. The clone becomes the post-loop.
1536 // The main loop pre-header illegally has 2 control users (old & new loops).
1537 clone_loop(loop, old_new, dd_main_exit, ControlAroundStripMined);
1538 assert(old_new[main_end->_idx]->Opcode() == Op_CountedLoopEnd, "");
1539 post_head = old_new[main_head->_idx]->as_CountedLoop();
1540 post_head->set_normal_loop();
1541 post_head->set_post_loop(main_head);
1542
1543 // Reduce the post-loop trip count.
1544 CountedLoopEndNode* post_end = old_new[main_end->_idx]->as_CountedLoopEnd();
1545 post_end->_prob = PROB_FAIR;
1546
1547 // Build the main-loop normal exit.
1548 IfFalseNode *new_main_exit = new IfFalseNode(outer_main_end);
1549 _igvn.register_new_node_with_optimizer(new_main_exit);
1550 set_idom(new_main_exit, outer_main_end, dd_main_exit);
1551 set_loop(new_main_exit, outer_loop->_parent);
1552
1553 // Step A2: Build a zero-trip guard for the post-loop. After leaving the
1554 // main-loop, the post-loop may not execute at all. We 'opaque' the incr
1555 // (the previous loop trip-counter exit value) because we will be changing
1556 // the exit value (via additional unrolling) so we cannot constant-fold away the zero
1557 // trip guard until all unrolling is done.
1558 Node *zer_opaq = new Opaque1Node(C, incr);
1559 Node *zer_cmp = new CmpINode(zer_opaq, limit);
1560 Node *zer_bol = new BoolNode(zer_cmp, main_end->test_trip());
1561 register_new_node(zer_opaq, new_main_exit);
1562 register_new_node(zer_cmp, new_main_exit);
1563 register_new_node(zer_bol, new_main_exit);
1564
1565 // Build the IfNode
1566 IfNode *zer_iff = new IfNode(new_main_exit, zer_bol, PROB_FAIR, COUNT_UNKNOWN);
1567 _igvn.register_new_node_with_optimizer(zer_iff);
1568 set_idom(zer_iff, new_main_exit, dd_main_exit);
1569 set_loop(zer_iff, outer_loop->_parent);
1570
1571 // Plug in the false-path, taken if we need to skip this post-loop
1572 _igvn.replace_input_of(main_exit, 0, zer_iff);
1573 set_idom(main_exit, zer_iff, dd_main_exit);
1574 set_idom(main_exit->unique_out(), zer_iff, dd_main_exit);
1575 // Make the true-path, must enter this post loop
1576 Node *zer_taken = new IfTrueNode(zer_iff);
1577 _igvn.register_new_node_with_optimizer(zer_taken);
1578 set_idom(zer_taken, zer_iff, dd_main_exit);
1579 set_loop(zer_taken, outer_loop->_parent);
1580 // Plug in the true path
1581 _igvn.hash_delete(post_head);
1582 post_head->set_req(LoopNode::EntryControl, zer_taken);
1583 set_idom(post_head, zer_taken, dd_main_exit);
1584
1585 Arena *a = Thread::current()->resource_area();
1586 VectorSet visited(a);
1587 Node_Stack clones(a, main_head->back_control()->outcnt());
1588 // Step A3: Make the fall-in values to the post-loop come from the
1589 // fall-out values of the main-loop.
1590 for (DUIterator_Fast imax, i = main_head->fast_outs(imax); i < imax; i++) {
1591 Node* main_phi = main_head->fast_out(i);
1592 if (main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() >0) {
1593 Node *cur_phi = old_new[main_phi->_idx];
1594 Node *fallnew = clone_up_backedge_goo(main_head->back_control(),
1595 post_head->init_control(),
1596 main_phi->in(LoopNode::LoopBackControl),
1597 visited, clones);
1598 _igvn.hash_delete(cur_phi);
1599 cur_phi->set_req(LoopNode::EntryControl, fallnew);
1600 }
1601 }
1602
1603 // CastII for the new post loop:
1604 Node* castii = cast_incr_before_loop(zer_opaq->in(1), zer_taken, post_head);
1605 assert(castii != NULL, "no castII inserted");
1606
1607 return new_main_exit;
1608 }
1609
1610 //------------------------------is_invariant-----------------------------
1611 // Return true if n is invariant
1612 bool IdealLoopTree::is_invariant(Node* n) const {
1613 Node *n_c = _phase->has_ctrl(n) ? _phase->get_ctrl(n) : n;
1614 if (n_c->is_top()) return false;
1615 return !is_member(_phase->get_loop(n_c));
1616 }
1617
1618
1619 //------------------------------do_unroll--------------------------------------
1620 // Unroll the loop body one step - make each trip do 2 iterations.
1621 void PhaseIdealLoop::do_unroll( IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip ) {
1622 assert(LoopUnrollLimit, "");
1623 CountedLoopNode *loop_head = loop->_head->as_CountedLoop();
1624 CountedLoopEndNode *loop_end = loop_head->loopexit();
1625 #ifndef PRODUCT
1626 if (PrintOpto && VerifyLoopOptimizations) {
1627 tty->print("Unrolling ");
1628 loop->dump_head();
1629 } else if (TraceLoopOpts) {
1630 if (loop_head->trip_count() < (uint)LoopUnrollLimit) {
1631 tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count());
1632 } else {
1633 tty->print("Unroll %d ", loop_head->unrolled_count()*2);
1634 }
1635 loop->dump_head();
1636 }
1637
1638 if (C->do_vector_loop() && (PrintOpto && (VerifyLoopOptimizations || TraceLoopOpts))) {
1639 Arena* arena = Thread::current()->resource_area();
1640 Node_Stack stack(arena, C->live_nodes() >> 2);
1641 Node_List rpo_list;
1642 VectorSet visited(arena);
1643 visited.set(loop_head->_idx);
1644 rpo( loop_head, stack, visited, rpo_list );
1645 dump(loop, rpo_list.size(), rpo_list );
1646 }
1647 #endif
1648
1649 // Remember loop node count before unrolling to detect
1650 // if rounds of unroll,optimize are making progress
1651 loop_head->set_node_count_before_unroll(loop->_body.size());
1652
1653 Node *ctrl = loop_head->skip_strip_mined()->in(LoopNode::EntryControl);
1654 Node *limit = loop_head->limit();
1655 Node *init = loop_head->init_trip();
1656 Node *stride = loop_head->stride();
1657
1658 Node *opaq = NULL;
1659 if (adjust_min_trip) { // If not maximally unrolling, need adjustment
1660 // Search for zero-trip guard.
1661
1662 // Check the shape of the graph at the loop entry. If an inappropriate
1663 // graph shape is encountered, the compiler bails out loop unrolling;
1664 // compilation of the method will still succeed.
1665 if (!is_canonical_loop_entry(loop_head)) {
1666 return;
1667 }
1668 opaq = loop_head->skip_predicates()->in(0)->in(1)->in(1)->in(2);
1669 // Zero-trip test uses an 'opaque' node which is not shared.
1670 assert(opaq->outcnt() == 1 && opaq->in(1) == limit, "");
1671 }
1672
1673 C->set_major_progress();
1674
1675 Node* new_limit = NULL;
1676 int stride_con = stride->get_int();
1677 int stride_p = (stride_con > 0) ? stride_con : -stride_con;
1678 uint old_trip_count = loop_head->trip_count();
1679 // Verify that unroll policy result is still valid.
1680 assert(old_trip_count > 1 &&
1681 (!adjust_min_trip || stride_p <= (1<<3)*loop_head->unrolled_count()), "sanity");
1682
1683 // Adjust loop limit to keep valid iterations number after unroll.
1684 // Use (limit - stride) instead of (((limit - init)/stride) & (-2))*stride
1685 // which may overflow.
1686 if (!adjust_min_trip) {
1687 assert(old_trip_count > 1 && (old_trip_count & 1) == 0,
1688 "odd trip count for maximally unroll");
1689 // Don't need to adjust limit for maximally unroll since trip count is even.
1690 } else if (loop_head->has_exact_trip_count() && init->is_Con()) {
1691 // Loop's limit is constant. Loop's init could be constant when pre-loop
1692 // become peeled iteration.
1693 jlong init_con = init->get_int();
1694 // We can keep old loop limit if iterations count stays the same:
1695 // old_trip_count == new_trip_count * 2
1696 // Note: since old_trip_count >= 2 then new_trip_count >= 1
1697 // so we also don't need to adjust zero trip test.
1698 jlong limit_con = limit->get_int();
1699 // (stride_con*2) not overflow since stride_con <= 8.
1700 int new_stride_con = stride_con * 2;
1701 int stride_m = new_stride_con - (stride_con > 0 ? 1 : -1);
1702 jlong trip_count = (limit_con - init_con + stride_m)/new_stride_con;
1703 // New trip count should satisfy next conditions.
1704 assert(trip_count > 0 && (julong)trip_count < (julong)max_juint/2, "sanity");
1705 uint new_trip_count = (uint)trip_count;
1706 adjust_min_trip = (old_trip_count != new_trip_count*2);
1707 }
1708
1709 if (adjust_min_trip) {
1710 // Step 2: Adjust the trip limit if it is called for.
1711 // The adjustment amount is -stride. Need to make sure if the
1712 // adjustment underflows or overflows, then the main loop is skipped.
1713 Node* cmp = loop_end->cmp_node();
1714 assert(cmp->in(2) == limit, "sanity");
1715 assert(opaq != NULL && opaq->in(1) == limit, "sanity");
1716
1717 // Verify that policy_unroll result is still valid.
1718 const TypeInt* limit_type = _igvn.type(limit)->is_int();
1719 assert(stride_con > 0 && ((limit_type->_hi - stride_con) < limit_type->_hi) ||
1720 stride_con < 0 && ((limit_type->_lo - stride_con) > limit_type->_lo), "sanity");
1721
1722 if (limit->is_Con()) {
1723 // The check in policy_unroll and the assert above guarantee
1724 // no underflow if limit is constant.
1725 new_limit = _igvn.intcon(limit->get_int() - stride_con);
1726 set_ctrl(new_limit, C->root());
1727 } else {
1728 // Limit is not constant.
1729 if (loop_head->unrolled_count() == 1) { // only for first unroll
1730 // Separate limit by Opaque node in case it is an incremented
1731 // variable from previous loop to avoid using pre-incremented
1732 // value which could increase register pressure.
1733 // Otherwise reorg_offsets() optimization will create a separate
1734 // Opaque node for each use of trip-counter and as result
1735 // zero trip guard limit will be different from loop limit.
1736 assert(has_ctrl(opaq), "should have it");
1737 Node* opaq_ctrl = get_ctrl(opaq);
1738 limit = new Opaque2Node( C, limit );
1739 register_new_node( limit, opaq_ctrl );
1740 }
1741 if ((stride_con > 0 && (java_subtract(limit_type->_lo, stride_con) < limit_type->_lo)) ||
1742 (stride_con < 0 && (java_subtract(limit_type->_hi, stride_con) > limit_type->_hi))) {
1743 // No underflow.
1744 new_limit = new SubINode(limit, stride);
1745 } else {
1746 // (limit - stride) may underflow.
1747 // Clamp the adjustment value with MININT or MAXINT:
1748 //
1749 // new_limit = limit-stride
1750 // if (stride > 0)
1751 // new_limit = (limit < new_limit) ? MININT : new_limit;
1752 // else
1753 // new_limit = (limit > new_limit) ? MAXINT : new_limit;
1754 //
1755 BoolTest::mask bt = loop_end->test_trip();
1756 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
1757 Node* adj_max = _igvn.intcon((stride_con > 0) ? min_jint : max_jint);
1758 set_ctrl(adj_max, C->root());
1759 Node* old_limit = NULL;
1760 Node* adj_limit = NULL;
1761 Node* bol = limit->is_CMove() ? limit->in(CMoveNode::Condition) : NULL;
1762 if (loop_head->unrolled_count() > 1 &&
1763 limit->is_CMove() && limit->Opcode() == Op_CMoveI &&
1764 limit->in(CMoveNode::IfTrue) == adj_max &&
1765 bol->as_Bool()->_test._test == bt &&
1766 bol->in(1)->Opcode() == Op_CmpI &&
1767 bol->in(1)->in(2) == limit->in(CMoveNode::IfFalse)) {
1768 // Loop was unrolled before.
1769 // Optimize the limit to avoid nested CMove:
1770 // use original limit as old limit.
1771 old_limit = bol->in(1)->in(1);
1772 // Adjust previous adjusted limit.
1773 adj_limit = limit->in(CMoveNode::IfFalse);
1774 adj_limit = new SubINode(adj_limit, stride);
1775 } else {
1776 old_limit = limit;
1777 adj_limit = new SubINode(limit, stride);
1778 }
1779 assert(old_limit != NULL && adj_limit != NULL, "");
1780 register_new_node( adj_limit, ctrl ); // adjust amount
1781 Node* adj_cmp = new CmpINode(old_limit, adj_limit);
1782 register_new_node( adj_cmp, ctrl );
1783 Node* adj_bool = new BoolNode(adj_cmp, bt);
1784 register_new_node( adj_bool, ctrl );
1785 new_limit = new CMoveINode(adj_bool, adj_limit, adj_max, TypeInt::INT);
1786 }
1787 register_new_node(new_limit, ctrl);
1788 }
1789 assert(new_limit != NULL, "");
1790 // Replace in loop test.
1791 assert(loop_end->in(1)->in(1) == cmp, "sanity");
1792 if (cmp->outcnt() == 1 && loop_end->in(1)->outcnt() == 1) {
1793 // Don't need to create new test since only one user.
1794 _igvn.hash_delete(cmp);
1795 cmp->set_req(2, new_limit);
1796 } else {
1797 // Create new test since it is shared.
1798 Node* ctrl2 = loop_end->in(0);
1799 Node* cmp2 = cmp->clone();
1800 cmp2->set_req(2, new_limit);
1801 register_new_node(cmp2, ctrl2);
1802 Node* bol2 = loop_end->in(1)->clone();
1803 bol2->set_req(1, cmp2);
1804 register_new_node(bol2, ctrl2);
1805 _igvn.replace_input_of(loop_end, 1, bol2);
1806 }
1807 // Step 3: Find the min-trip test guaranteed before a 'main' loop.
1808 // Make it a 1-trip test (means at least 2 trips).
1809
1810 // Guard test uses an 'opaque' node which is not shared. Hence I
1811 // can edit it's inputs directly. Hammer in the new limit for the
1812 // minimum-trip guard.
1813 assert(opaq->outcnt() == 1, "");
1814 _igvn.replace_input_of(opaq, 1, new_limit);
1815 }
1816
1817 // Adjust max trip count. The trip count is intentionally rounded
1818 // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll,
1819 // the main, unrolled, part of the loop will never execute as it is protected
1820 // by the min-trip test. See bug 4834191 for a case where we over-unrolled
1821 // and later determined that part of the unrolled loop was dead.
1822 loop_head->set_trip_count(old_trip_count / 2);
1823
1824 // Double the count of original iterations in the unrolled loop body.
1825 loop_head->double_unrolled_count();
1826
1827 // ---------
1828 // Step 4: Clone the loop body. Move it inside the loop. This loop body
1829 // represents the odd iterations; since the loop trips an even number of
1830 // times its backedge is never taken. Kill the backedge.
1831 uint dd = dom_depth(loop_head);
1832 clone_loop(loop, old_new, dd, IgnoreStripMined);
1833
1834 // Make backedges of the clone equal to backedges of the original.
1835 // Make the fall-in from the original come from the fall-out of the clone.
1836 for (DUIterator_Fast jmax, j = loop_head->fast_outs(jmax); j < jmax; j++) {
1837 Node* phi = loop_head->fast_out(j);
1838 if( phi->is_Phi() && phi->in(0) == loop_head && phi->outcnt() > 0 ) {
1839 Node *newphi = old_new[phi->_idx];
1840 _igvn.hash_delete( phi );
1841 _igvn.hash_delete( newphi );
1842
1843 phi ->set_req(LoopNode:: EntryControl, newphi->in(LoopNode::LoopBackControl));
1844 newphi->set_req(LoopNode::LoopBackControl, phi ->in(LoopNode::LoopBackControl));
1845 phi ->set_req(LoopNode::LoopBackControl, C->top());
1846 }
1847 }
1848 Node *clone_head = old_new[loop_head->_idx];
1849 _igvn.hash_delete( clone_head );
1850 loop_head ->set_req(LoopNode:: EntryControl, clone_head->in(LoopNode::LoopBackControl));
1851 clone_head->set_req(LoopNode::LoopBackControl, loop_head ->in(LoopNode::LoopBackControl));
1852 loop_head ->set_req(LoopNode::LoopBackControl, C->top());
1853 loop->_head = clone_head; // New loop header
1854
1855 set_idom(loop_head, loop_head ->in(LoopNode::EntryControl), dd);
1856 set_idom(clone_head, clone_head->in(LoopNode::EntryControl), dd);
1857
1858 // Kill the clone's backedge
1859 Node *newcle = old_new[loop_end->_idx];
1860 _igvn.hash_delete( newcle );
1861 Node *one = _igvn.intcon(1);
1862 set_ctrl(one, C->root());
1863 newcle->set_req(1, one);
1864 // Force clone into same loop body
1865 uint max = loop->_body.size();
1866 for( uint k = 0; k < max; k++ ) {
1867 Node *old = loop->_body.at(k);
1868 Node *nnn = old_new[old->_idx];
1869 loop->_body.push(nnn);
1870 if (!has_ctrl(old))
1871 set_loop(nnn, loop);
1872 }
1873
1874 loop->record_for_igvn();
1875 loop_head->clear_strip_mined();
1876
1877 #ifndef PRODUCT
1878 if (C->do_vector_loop() && (PrintOpto && (VerifyLoopOptimizations || TraceLoopOpts))) {
1879 tty->print("\nnew loop after unroll\n"); loop->dump_head();
1880 for (uint i = 0; i < loop->_body.size(); i++) {
1881 loop->_body.at(i)->dump();
1882 }
1883 if(C->clone_map().is_debug()) {
1884 tty->print("\nCloneMap\n");
1885 Dict* dict = C->clone_map().dict();
1886 DictI i(dict);
1887 tty->print_cr("Dict@%p[%d] = ", dict, dict->Size());
1888 for (int ii = 0; i.test(); ++i, ++ii) {
1889 NodeCloneInfo cl((uint64_t)dict->operator[]((void*)i._key));
1890 tty->print("%d->%d:%d,", (int)(intptr_t)i._key, cl.idx(), cl.gen());
1891 if (ii % 10 == 9) {
1892 tty->print_cr(" ");
1893 }
1894 }
1895 tty->print_cr(" ");
1896 }
1897 }
1898 #endif
1899
1900 }
1901
1902 //------------------------------do_maximally_unroll----------------------------
1903
1904 void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) {
1905 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1906 assert(cl->has_exact_trip_count(), "trip count is not exact");
1907 assert(cl->trip_count() > 0, "");
1908 #ifndef PRODUCT
1909 if (TraceLoopOpts) {
1910 tty->print("MaxUnroll %d ", cl->trip_count());
1911 loop->dump_head();
1912 }
1913 #endif
1914
1915 // If loop is tripping an odd number of times, peel odd iteration
1916 if ((cl->trip_count() & 1) == 1) {
1917 do_peeling(loop, old_new);
1918 }
1919
1920 // Now its tripping an even number of times remaining. Double loop body.
1921 // Do not adjust pre-guards; they are not needed and do not exist.
1922 if (cl->trip_count() > 0) {
1923 assert((cl->trip_count() & 1) == 0, "missed peeling");
1924 do_unroll(loop, old_new, false);
1925 }
1926 }
1927
1928 void PhaseIdealLoop::mark_reductions(IdealLoopTree *loop) {
1929 if (SuperWordReductions == false) return;
1930
1931 CountedLoopNode* loop_head = loop->_head->as_CountedLoop();
1932 if (loop_head->unrolled_count() > 1) {
1933 return;
1934 }
1935
1936 Node* trip_phi = loop_head->phi();
1937 for (DUIterator_Fast imax, i = loop_head->fast_outs(imax); i < imax; i++) {
1938 Node* phi = loop_head->fast_out(i);
1939 if (phi->is_Phi() && phi->outcnt() > 0 && phi != trip_phi) {
1940 // For definitions which are loop inclusive and not tripcounts.
1941 Node* def_node = phi->in(LoopNode::LoopBackControl);
1942
1943 if (def_node != NULL) {
1944 Node* n_ctrl = get_ctrl(def_node);
1945 if (n_ctrl != NULL && loop->is_member(get_loop(n_ctrl))) {
1946 // Now test it to see if it fits the standard pattern for a reduction operator.
1947 int opc = def_node->Opcode();
1948 if (opc != ReductionNode::opcode(opc, def_node->bottom_type()->basic_type())) {
1949 if (!def_node->is_reduction()) { // Not marked yet
1950 // To be a reduction, the arithmetic node must have the phi as input and provide a def to it
1951 bool ok = false;
1952 for (unsigned j = 1; j < def_node->req(); j++) {
1953 Node* in = def_node->in(j);
1954 if (in == phi) {
1955 ok = true;
1956 break;
1957 }
1958 }
1959
1960 // do nothing if we did not match the initial criteria
1961 if (ok == false) {
1962 continue;
1963 }
1964
1965 // The result of the reduction must not be used in the loop
1966 for (DUIterator_Fast imax, i = def_node->fast_outs(imax); i < imax && ok; i++) {
1967 Node* u = def_node->fast_out(i);
1968 if (!loop->is_member(get_loop(ctrl_or_self(u)))) {
1969 continue;
1970 }
1971 if (u == phi) {
1972 continue;
1973 }
1974 ok = false;
1975 }
1976
1977 // iff the uses conform
1978 if (ok) {
1979 def_node->add_flag(Node::Flag_is_reduction);
1980 loop_head->mark_has_reductions();
1981 }
1982 }
1983 }
1984 }
1985 }
1986 }
1987 }
1988 }
1989
1990 //------------------------------adjust_limit-----------------------------------
1991 // Helper function for add_constraint().
1992 Node* PhaseIdealLoop::adjust_limit(int stride_con, Node * scale, Node *offset, Node *rc_limit, Node *loop_limit, Node *pre_ctrl) {
1993 // Compute "I :: (limit-offset)/scale"
1994 Node *con = new SubINode(rc_limit, offset);
1995 register_new_node(con, pre_ctrl);
1996 Node *X = new DivINode(0, con, scale);
1997 register_new_node(X, pre_ctrl);
1998
1999 // Adjust loop limit
2000 loop_limit = (stride_con > 0)
2001 ? (Node*)(new MinINode(loop_limit, X))
2002 : (Node*)(new MaxINode(loop_limit, X));
2003 register_new_node(loop_limit, pre_ctrl);
2004 return loop_limit;
2005 }
2006
2007 //------------------------------add_constraint---------------------------------
2008 // Constrain the main loop iterations so the conditions:
2009 // low_limit <= scale_con * I + offset < upper_limit
2010 // always holds true. That is, either increase the number of iterations in
2011 // the pre-loop or the post-loop until the condition holds true in the main
2012 // loop. Stride, scale, offset and limit are all loop invariant. Further,
2013 // stride and scale are constants (offset and limit often are).
2014 void PhaseIdealLoop::add_constraint( int stride_con, int scale_con, Node *offset, Node *low_limit, Node *upper_limit, Node *pre_ctrl, Node **pre_limit, Node **main_limit ) {
2015 // For positive stride, the pre-loop limit always uses a MAX function
2016 // and the main loop a MIN function. For negative stride these are
2017 // reversed.
2018
2019 // Also for positive stride*scale the affine function is increasing, so the
2020 // pre-loop must check for underflow and the post-loop for overflow.
2021 // Negative stride*scale reverses this; pre-loop checks for overflow and
2022 // post-loop for underflow.
2023
2024 Node *scale = _igvn.intcon(scale_con);
2025 set_ctrl(scale, C->root());
2026
2027 if ((stride_con^scale_con) >= 0) { // Use XOR to avoid overflow
2028 // The overflow limit: scale*I+offset < upper_limit
2029 // For main-loop compute
2030 // ( if (scale > 0) /* and stride > 0 */
2031 // I < (upper_limit-offset)/scale
2032 // else /* scale < 0 and stride < 0 */
2033 // I > (upper_limit-offset)/scale
2034 // )
2035 //
2036 // (upper_limit-offset) may overflow or underflow.
2037 // But it is fine since main loop will either have
2038 // less iterations or will be skipped in such case.
2039 *main_limit = adjust_limit(stride_con, scale, offset, upper_limit, *main_limit, pre_ctrl);
2040
2041 // The underflow limit: low_limit <= scale*I+offset.
2042 // For pre-loop compute
2043 // NOT(scale*I+offset >= low_limit)
2044 // scale*I+offset < low_limit
2045 // ( if (scale > 0) /* and stride > 0 */
2046 // I < (low_limit-offset)/scale
2047 // else /* scale < 0 and stride < 0 */
2048 // I > (low_limit-offset)/scale
2049 // )
2050
2051 if (low_limit->get_int() == -max_jint) {
2052 // We need this guard when scale*pre_limit+offset >= limit
2053 // due to underflow. So we need execute pre-loop until
2054 // scale*I+offset >= min_int. But (min_int-offset) will
2055 // underflow when offset > 0 and X will be > original_limit
2056 // when stride > 0. To avoid it we replace positive offset with 0.
2057 //
2058 // Also (min_int+1 == -max_int) is used instead of min_int here
2059 // to avoid problem with scale == -1 (min_int/(-1) == min_int).
2060 Node* shift = _igvn.intcon(31);
2061 set_ctrl(shift, C->root());
2062 Node* sign = new RShiftINode(offset, shift);
2063 register_new_node(sign, pre_ctrl);
2064 offset = new AndINode(offset, sign);
2065 register_new_node(offset, pre_ctrl);
2066 } else {
2067 assert(low_limit->get_int() == 0, "wrong low limit for range check");
2068 // The only problem we have here when offset == min_int
2069 // since (0-min_int) == min_int. It may be fine for stride > 0
2070 // but for stride < 0 X will be < original_limit. To avoid it
2071 // max(pre_limit, original_limit) is used in do_range_check().
2072 }
2073 // Pass (-stride) to indicate pre_loop_cond = NOT(main_loop_cond);
2074 *pre_limit = adjust_limit((-stride_con), scale, offset, low_limit, *pre_limit, pre_ctrl);
2075
2076 } else { // stride_con*scale_con < 0
2077 // For negative stride*scale pre-loop checks for overflow and
2078 // post-loop for underflow.
2079 //
2080 // The overflow limit: scale*I+offset < upper_limit
2081 // For pre-loop compute
2082 // NOT(scale*I+offset < upper_limit)
2083 // scale*I+offset >= upper_limit
2084 // scale*I+offset+1 > upper_limit
2085 // ( if (scale < 0) /* and stride > 0 */
2086 // I < (upper_limit-(offset+1))/scale
2087 // else /* scale > 0 and stride < 0 */
2088 // I > (upper_limit-(offset+1))/scale
2089 // )
2090 //
2091 // (upper_limit-offset-1) may underflow or overflow.
2092 // To avoid it min(pre_limit, original_limit) is used
2093 // in do_range_check() for stride > 0 and max() for < 0.
2094 Node *one = _igvn.intcon(1);
2095 set_ctrl(one, C->root());
2096
2097 Node *plus_one = new AddINode(offset, one);
2098 register_new_node( plus_one, pre_ctrl );
2099 // Pass (-stride) to indicate pre_loop_cond = NOT(main_loop_cond);
2100 *pre_limit = adjust_limit((-stride_con), scale, plus_one, upper_limit, *pre_limit, pre_ctrl);
2101
2102 if (low_limit->get_int() == -max_jint) {
2103 // We need this guard when scale*main_limit+offset >= limit
2104 // due to underflow. So we need execute main-loop while
2105 // scale*I+offset+1 > min_int. But (min_int-offset-1) will
2106 // underflow when (offset+1) > 0 and X will be < main_limit
2107 // when scale < 0 (and stride > 0). To avoid it we replace
2108 // positive (offset+1) with 0.
2109 //
2110 // Also (min_int+1 == -max_int) is used instead of min_int here
2111 // to avoid problem with scale == -1 (min_int/(-1) == min_int).
2112 Node* shift = _igvn.intcon(31);
2113 set_ctrl(shift, C->root());
2114 Node* sign = new RShiftINode(plus_one, shift);
2115 register_new_node(sign, pre_ctrl);
2116 plus_one = new AndINode(plus_one, sign);
2117 register_new_node(plus_one, pre_ctrl);
2118 } else {
2119 assert(low_limit->get_int() == 0, "wrong low limit for range check");
2120 // The only problem we have here when offset == max_int
2121 // since (max_int+1) == min_int and (0-min_int) == min_int.
2122 // But it is fine since main loop will either have
2123 // less iterations or will be skipped in such case.
2124 }
2125 // The underflow limit: low_limit <= scale*I+offset.
2126 // For main-loop compute
2127 // scale*I+offset+1 > low_limit
2128 // ( if (scale < 0) /* and stride > 0 */
2129 // I < (low_limit-(offset+1))/scale
2130 // else /* scale > 0 and stride < 0 */
2131 // I > (low_limit-(offset+1))/scale
2132 // )
2133
2134 *main_limit = adjust_limit(stride_con, scale, plus_one, low_limit, *main_limit, pre_ctrl);
2135 }
2136 }
2137
2138
2139 //------------------------------is_scaled_iv---------------------------------
2140 // Return true if exp is a constant times an induction var
2141 bool PhaseIdealLoop::is_scaled_iv(Node* exp, Node* iv, int* p_scale) {
2142 if (exp == iv) {
2143 if (p_scale != NULL) {
2144 *p_scale = 1;
2145 }
2146 return true;
2147 }
2148 int opc = exp->Opcode();
2149 if (opc == Op_MulI) {
2150 if (exp->in(1) == iv && exp->in(2)->is_Con()) {
2151 if (p_scale != NULL) {
2152 *p_scale = exp->in(2)->get_int();
2153 }
2154 return true;
2155 }
2156 if (exp->in(2) == iv && exp->in(1)->is_Con()) {
2157 if (p_scale != NULL) {
2158 *p_scale = exp->in(1)->get_int();
2159 }
2160 return true;
2161 }
2162 } else if (opc == Op_LShiftI) {
2163 if (exp->in(1) == iv && exp->in(2)->is_Con()) {
2164 if (p_scale != NULL) {
2165 *p_scale = 1 << exp->in(2)->get_int();
2166 }
2167 return true;
2168 }
2169 }
2170 return false;
2171 }
2172
2173 //-----------------------------is_scaled_iv_plus_offset------------------------------
2174 // Return true if exp is a simple induction variable expression: k1*iv + (invar + k2)
2175 bool PhaseIdealLoop::is_scaled_iv_plus_offset(Node* exp, Node* iv, int* p_scale, Node** p_offset, int depth) {
2176 if (is_scaled_iv(exp, iv, p_scale)) {
2177 if (p_offset != NULL) {
2178 Node *zero = _igvn.intcon(0);
2179 set_ctrl(zero, C->root());
2180 *p_offset = zero;
2181 }
2182 return true;
2183 }
2184 int opc = exp->Opcode();
2185 if (opc == Op_AddI) {
2186 if (is_scaled_iv(exp->in(1), iv, p_scale)) {
2187 if (p_offset != NULL) {
2188 *p_offset = exp->in(2);
2189 }
2190 return true;
2191 }
2192 if (is_scaled_iv(exp->in(2), iv, p_scale)) {
2193 if (p_offset != NULL) {
2194 *p_offset = exp->in(1);
2195 }
2196 return true;
2197 }
2198 if (exp->in(2)->is_Con()) {
2199 Node* offset2 = NULL;
2200 if (depth < 2 &&
2201 is_scaled_iv_plus_offset(exp->in(1), iv, p_scale,
2202 p_offset != NULL ? &offset2 : NULL, depth+1)) {
2203 if (p_offset != NULL) {
2204 Node *ctrl_off2 = get_ctrl(offset2);
2205 Node* offset = new AddINode(offset2, exp->in(2));
2206 register_new_node(offset, ctrl_off2);
2207 *p_offset = offset;
2208 }
2209 return true;
2210 }
2211 }
2212 } else if (opc == Op_SubI) {
2213 if (is_scaled_iv(exp->in(1), iv, p_scale)) {
2214 if (p_offset != NULL) {
2215 Node *zero = _igvn.intcon(0);
2216 set_ctrl(zero, C->root());
2217 Node *ctrl_off = get_ctrl(exp->in(2));
2218 Node* offset = new SubINode(zero, exp->in(2));
2219 register_new_node(offset, ctrl_off);
2220 *p_offset = offset;
2221 }
2222 return true;
2223 }
2224 if (is_scaled_iv(exp->in(2), iv, p_scale)) {
2225 if (p_offset != NULL) {
2226 *p_scale *= -1;
2227 *p_offset = exp->in(1);
2228 }
2229 return true;
2230 }
2231 }
2232 return false;
2233 }
2234
2235 // Same as PhaseIdealLoop::duplicate_predicates() but for range checks
2236 // eliminated by iteration splitting.
2237 Node* PhaseIdealLoop::add_range_check_predicate(IdealLoopTree* loop, CountedLoopNode* cl,
2238 Node* predicate_proj, int scale_con, Node* offset,
2239 Node* limit, jint stride_con) {
2240 bool overflow = false;
2241 BoolNode* bol = rc_predicate(loop, predicate_proj, scale_con, offset, cl->init_trip(), NULL, stride_con, limit, (stride_con > 0) != (scale_con > 0), overflow);
2242 Node* opaque_bol = new Opaque4Node(C, bol, _igvn.intcon(1));
2243 register_new_node(opaque_bol, predicate_proj);
2244 IfNode* new_iff = NULL;
2245 if (overflow) {
2246 new_iff = new IfNode(predicate_proj, bol, PROB_MAX, COUNT_UNKNOWN);
2247 } else {
2248 new_iff = new RangeCheckNode(predicate_proj, bol, PROB_MAX, COUNT_UNKNOWN);
2249 }
2250 register_control(new_iff, loop->_parent, predicate_proj);
2251 Node* iffalse = new IfFalseNode(new_iff);
2252 register_control(iffalse, _ltree_root, new_iff);
2253 ProjNode* iftrue = new IfTrueNode(new_iff);
2254 register_control(iftrue, loop->_parent, new_iff);
2255 Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
2256 register_new_node(frame, C->start());
2257 Node* halt = new HaltNode(iffalse, frame);
2258 register_control(halt, _ltree_root, iffalse);
2259 C->root()->add_req(halt);
2260 return iftrue;
2261 }
2262
2263 //------------------------------do_range_check---------------------------------
2264 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
2265 int PhaseIdealLoop::do_range_check( IdealLoopTree *loop, Node_List &old_new ) {
2266 #ifndef PRODUCT
2267 if (PrintOpto && VerifyLoopOptimizations) {
2268 tty->print("Range Check Elimination ");
2269 loop->dump_head();
2270 } else if (TraceLoopOpts) {
2271 tty->print("RangeCheck ");
2272 loop->dump_head();
2273 }
2274 #endif
2275 assert(RangeCheckElimination, "");
2276 CountedLoopNode *cl = loop->_head->as_CountedLoop();
2277 // If we fail before trying to eliminate range checks, set multiversion state
2278 int closed_range_checks = 1;
2279
2280 // protect against stride not being a constant
2281 if (!cl->stride_is_con())
2282 return closed_range_checks;
2283
2284 // Find the trip counter; we are iteration splitting based on it
2285 Node *trip_counter = cl->phi();
2286 // Find the main loop limit; we will trim it's iterations
2287 // to not ever trip end tests
2288 Node *main_limit = cl->limit();
2289
2290 // Check graph shape. Cannot optimize a loop if zero-trip
2291 // Opaque1 node is optimized away and then another round
2292 // of loop opts attempted.
2293 if (!is_canonical_loop_entry(cl)) {
2294 return closed_range_checks;
2295 }
2296
2297 // Need to find the main-loop zero-trip guard
2298 Node *ctrl = cl->skip_predicates();
2299 Node *iffm = ctrl->in(0);
2300 Node *opqzm = iffm->in(1)->in(1)->in(2);
2301 assert(opqzm->in(1) == main_limit, "do not understand situation");
2302
2303 // Find the pre-loop limit; we will expand its iterations to
2304 // not ever trip low tests.
2305 Node *p_f = iffm->in(0);
2306 // pre loop may have been optimized out
2307 if (p_f->Opcode() != Op_IfFalse) {
2308 return closed_range_checks;
2309 }
2310 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
2311 assert(pre_end->loopnode()->is_pre_loop(), "");
2312 Node *pre_opaq1 = pre_end->limit();
2313 // Occasionally it's possible for a pre-loop Opaque1 node to be
2314 // optimized away and then another round of loop opts attempted.
2315 // We can not optimize this particular loop in that case.
2316 if (pre_opaq1->Opcode() != Op_Opaque1)
2317 return closed_range_checks;
2318 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
2319 Node *pre_limit = pre_opaq->in(1);
2320
2321 // Where do we put new limit calculations
2322 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
2323
2324 // Ensure the original loop limit is available from the
2325 // pre-loop Opaque1 node.
2326 Node *orig_limit = pre_opaq->original_loop_limit();
2327 if (orig_limit == NULL || _igvn.type(orig_limit) == Type::TOP)
2328 return closed_range_checks;
2329
2330 // Must know if its a count-up or count-down loop
2331
2332 int stride_con = cl->stride_con();
2333 Node *zero = _igvn.intcon(0);
2334 Node *one = _igvn.intcon(1);
2335 // Use symmetrical int range [-max_jint,max_jint]
2336 Node *mini = _igvn.intcon(-max_jint);
2337 set_ctrl(zero, C->root());
2338 set_ctrl(one, C->root());
2339 set_ctrl(mini, C->root());
2340
2341 // Range checks that do not dominate the loop backedge (ie.
2342 // conditionally executed) can lengthen the pre loop limit beyond
2343 // the original loop limit. To prevent this, the pre limit is
2344 // (for stride > 0) MINed with the original loop limit (MAXed
2345 // stride < 0) when some range_check (rc) is conditionally
2346 // executed.
2347 bool conditional_rc = false;
2348
2349 // Count number of range checks and reduce by load range limits, if zero,
2350 // the loop is in canonical form to multiversion.
2351 closed_range_checks = 0;
2352
2353 Node* predicate_proj = cl->skip_strip_mined()->in(LoopNode::EntryControl);
2354 assert(predicate_proj->is_Proj() && predicate_proj->in(0)->is_If(), "if projection only");
2355 // Check loop body for tests of trip-counter plus loop-invariant vs loop-variant.
2356 for( uint i = 0; i < loop->_body.size(); i++ ) {
2357 Node *iff = loop->_body[i];
2358 if (iff->Opcode() == Op_If ||
2359 iff->Opcode() == Op_RangeCheck) { // Test?
2360 // Test is an IfNode, has 2 projections. If BOTH are in the loop
2361 // we need loop unswitching instead of iteration splitting.
2362 closed_range_checks++;
2363 Node *exit = loop->is_loop_exit(iff);
2364 if( !exit ) continue;
2365 int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
2366
2367 // Get boolean condition to test
2368 Node *i1 = iff->in(1);
2369 if( !i1->is_Bool() ) continue;
2370 BoolNode *bol = i1->as_Bool();
2371 BoolTest b_test = bol->_test;
2372 // Flip sense of test if exit condition is flipped
2373 if( flip )
2374 b_test = b_test.negate();
2375
2376 // Get compare
2377 Node *cmp = bol->in(1);
2378
2379 // Look for trip_counter + offset vs limit
2380 Node *rc_exp = cmp->in(1);
2381 Node *limit = cmp->in(2);
2382 int scale_con= 1; // Assume trip counter not scaled
2383
2384 Node *limit_c = get_ctrl(limit);
2385 if( loop->is_member(get_loop(limit_c) ) ) {
2386 // Compare might have operands swapped; commute them
2387 b_test = b_test.commute();
2388 rc_exp = cmp->in(2);
2389 limit = cmp->in(1);
2390 limit_c = get_ctrl(limit);
2391 if( loop->is_member(get_loop(limit_c) ) )
2392 continue; // Both inputs are loop varying; cannot RCE
2393 }
2394 // Here we know 'limit' is loop invariant
2395
2396 // 'limit' maybe pinned below the zero trip test (probably from a
2397 // previous round of rce), in which case, it can't be used in the
2398 // zero trip test expression which must occur before the zero test's if.
2399 if (is_dominator(ctrl, limit_c)) {
2400 continue; // Don't rce this check but continue looking for other candidates.
2401 }
2402
2403 // Check for scaled induction variable plus an offset
2404 Node *offset = NULL;
2405
2406 if (!is_scaled_iv_plus_offset(rc_exp, trip_counter, &scale_con, &offset)) {
2407 continue;
2408 }
2409
2410 Node *offset_c = get_ctrl(offset);
2411 if( loop->is_member( get_loop(offset_c) ) )
2412 continue; // Offset is not really loop invariant
2413 // Here we know 'offset' is loop invariant.
2414
2415 // As above for the 'limit', the 'offset' maybe pinned below the
2416 // zero trip test.
2417 if (is_dominator(ctrl, offset_c)) {
2418 continue; // Don't rce this check but continue looking for other candidates.
2419 }
2420 #ifdef ASSERT
2421 if (TraceRangeLimitCheck) {
2422 tty->print_cr("RC bool node%s", flip ? " flipped:" : ":");
2423 bol->dump(2);
2424 }
2425 #endif
2426 // At this point we have the expression as:
2427 // scale_con * trip_counter + offset :: limit
2428 // where scale_con, offset and limit are loop invariant. Trip_counter
2429 // monotonically increases by stride_con, a constant. Both (or either)
2430 // stride_con and scale_con can be negative which will flip about the
2431 // sense of the test.
2432
2433 // Adjust pre and main loop limits to guard the correct iteration set
2434 if( cmp->Opcode() == Op_CmpU ) {// Unsigned compare is really 2 tests
2435 if( b_test._test == BoolTest::lt ) { // Range checks always use lt
2436 // The underflow and overflow limits: 0 <= scale*I+offset < limit
2437 add_constraint( stride_con, scale_con, offset, zero, limit, pre_ctrl, &pre_limit, &main_limit );
2438 // (0-offset)/scale could be outside of loop iterations range.
2439 conditional_rc = true;
2440 predicate_proj = add_range_check_predicate(loop, cl, predicate_proj, scale_con, offset, limit, stride_con);
2441 } else {
2442 if (PrintOpto) {
2443 tty->print_cr("missed RCE opportunity");
2444 }
2445 continue; // In release mode, ignore it
2446 }
2447 } else { // Otherwise work on normal compares
2448 switch( b_test._test ) {
2449 case BoolTest::gt:
2450 // Fall into GE case
2451 case BoolTest::ge:
2452 // Convert (I*scale+offset) >= Limit to (I*(-scale)+(-offset)) <= -Limit
2453 scale_con = -scale_con;
2454 offset = new SubINode( zero, offset );
2455 register_new_node( offset, pre_ctrl );
2456 limit = new SubINode( zero, limit );
2457 register_new_node( limit, pre_ctrl );
2458 // Fall into LE case
2459 case BoolTest::le:
2460 if (b_test._test != BoolTest::gt) {
2461 // Convert X <= Y to X < Y+1
2462 limit = new AddINode( limit, one );
2463 register_new_node( limit, pre_ctrl );
2464 }
2465 // Fall into LT case
2466 case BoolTest::lt:
2467 // The underflow and overflow limits: MIN_INT <= scale*I+offset < limit
2468 // Note: (MIN_INT+1 == -MAX_INT) is used instead of MIN_INT here
2469 // to avoid problem with scale == -1: MIN_INT/(-1) == MIN_INT.
2470 add_constraint( stride_con, scale_con, offset, mini, limit, pre_ctrl, &pre_limit, &main_limit );
2471 // ((MIN_INT+1)-offset)/scale could be outside of loop iterations range.
2472 // Note: negative offset is replaced with 0 but (MIN_INT+1)/scale could
2473 // still be outside of loop range.
2474 conditional_rc = true;
2475 break;
2476 default:
2477 if (PrintOpto) {
2478 tty->print_cr("missed RCE opportunity");
2479 }
2480 continue; // Unhandled case
2481 }
2482 }
2483
2484 // Kill the eliminated test
2485 C->set_major_progress();
2486 Node *kill_con = _igvn.intcon( 1-flip );
2487 set_ctrl(kill_con, C->root());
2488 _igvn.replace_input_of(iff, 1, kill_con);
2489 // Find surviving projection
2490 assert(iff->is_If(), "");
2491 ProjNode* dp = ((IfNode*)iff)->proj_out(1-flip);
2492 // Find loads off the surviving projection; remove their control edge
2493 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
2494 Node* cd = dp->fast_out(i); // Control-dependent node
2495 if (cd->is_Load() && cd->depends_only_on_test()) { // Loads can now float around in the loop
2496 // Allow the load to float around in the loop, or before it
2497 // but NOT before the pre-loop.
2498 _igvn.replace_input_of(cd, 0, ctrl); // ctrl, not NULL
2499 --i;
2500 --imax;
2501 }
2502 }
2503 if (limit->Opcode() == Op_LoadRange) {
2504 closed_range_checks--;
2505 }
2506
2507 } // End of is IF
2508
2509 }
2510 if (predicate_proj != cl->skip_strip_mined()->in(LoopNode::EntryControl)) {
2511 _igvn.replace_input_of(cl->skip_strip_mined(), LoopNode::EntryControl, predicate_proj);
2512 set_idom(cl->skip_strip_mined(), predicate_proj, dom_depth(cl->skip_strip_mined()));
2513 }
2514
2515 // Update loop limits
2516 if (conditional_rc) {
2517 pre_limit = (stride_con > 0) ? (Node*)new MinINode(pre_limit, orig_limit)
2518 : (Node*)new MaxINode(pre_limit, orig_limit);
2519 register_new_node(pre_limit, pre_ctrl);
2520 }
2521 _igvn.replace_input_of(pre_opaq, 1, pre_limit);
2522
2523 // Note:: we are making the main loop limit no longer precise;
2524 // need to round up based on stride.
2525 cl->set_nonexact_trip_count();
2526 Node *main_cle = cl->loopexit();
2527 Node *main_bol = main_cle->in(1);
2528 // Hacking loop bounds; need private copies of exit test
2529 if( main_bol->outcnt() > 1 ) {// BoolNode shared?
2530 main_bol = main_bol->clone();// Clone a private BoolNode
2531 register_new_node( main_bol, main_cle->in(0) );
2532 _igvn.replace_input_of(main_cle, 1, main_bol);
2533 }
2534 Node *main_cmp = main_bol->in(1);
2535 if( main_cmp->outcnt() > 1 ) { // CmpNode shared?
2536 main_cmp = main_cmp->clone();// Clone a private CmpNode
2537 register_new_node( main_cmp, main_cle->in(0) );
2538 _igvn.replace_input_of(main_bol, 1, main_cmp);
2539 }
2540 // Hack the now-private loop bounds
2541 _igvn.replace_input_of(main_cmp, 2, main_limit);
2542 // The OpaqueNode is unshared by design
2543 assert( opqzm->outcnt() == 1, "cannot hack shared node" );
2544 _igvn.replace_input_of(opqzm, 1, main_limit);
2545
2546 return closed_range_checks;
2547 }
2548
2549 //------------------------------has_range_checks-------------------------------
2550 // Check to see if RCE cleaned the current loop of range-checks.
2551 void PhaseIdealLoop::has_range_checks(IdealLoopTree *loop) {
2552 assert(RangeCheckElimination, "");
2553
2554 // skip if not a counted loop
2555 if (!loop->is_counted()) return;
2556
2557 CountedLoopNode *cl = loop->_head->as_CountedLoop();
2558
2559 // skip this loop if it is already checked
2560 if (cl->has_been_range_checked()) return;
2561
2562 // Now check for existence of range checks
2563 for (uint i = 0; i < loop->_body.size(); i++) {
2564 Node *iff = loop->_body[i];
2565 int iff_opc = iff->Opcode();
2566 if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2567 cl->mark_has_range_checks();
2568 break;
2569 }
2570 }
2571 cl->set_has_been_range_checked();
2572 }
2573
2574 //-------------------------multi_version_post_loops----------------------------
2575 // Check the range checks that remain, if simple, use the bounds to guard
2576 // which version to a post loop we execute, one with range checks or one without
2577 bool PhaseIdealLoop::multi_version_post_loops(IdealLoopTree *rce_loop, IdealLoopTree *legacy_loop) {
2578 bool multi_version_succeeded = false;
2579 assert(RangeCheckElimination, "");
2580 CountedLoopNode *legacy_cl = legacy_loop->_head->as_CountedLoop();
2581 assert(legacy_cl->is_post_loop(), "");
2582
2583 // Check for existence of range checks using the unique instance to make a guard with
2584 Unique_Node_List worklist;
2585 for (uint i = 0; i < legacy_loop->_body.size(); i++) {
2586 Node *iff = legacy_loop->_body[i];
2587 int iff_opc = iff->Opcode();
2588 if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2589 worklist.push(iff);
2590 }
2591 }
2592
2593 // Find RCE'd post loop so that we can stage its guard.
2594 if (!is_canonical_loop_entry(legacy_cl)) return multi_version_succeeded;
2595 Node* ctrl = legacy_cl->in(LoopNode::EntryControl);
2596 Node* iffm = ctrl->in(0);
2597
2598 // Now we test that both the post loops are connected
2599 Node* post_loop_region = iffm->in(0);
2600 if (post_loop_region == NULL) return multi_version_succeeded;
2601 if (!post_loop_region->is_Region()) return multi_version_succeeded;
2602 Node* covering_region = post_loop_region->in(RegionNode::Control+1);
2603 if (covering_region == NULL) return multi_version_succeeded;
2604 if (!covering_region->is_Region()) return multi_version_succeeded;
2605 Node* p_f = covering_region->in(RegionNode::Control);
2606 if (p_f == NULL) return multi_version_succeeded;
2607 if (!p_f->is_IfFalse()) return multi_version_succeeded;
2608 if (!p_f->in(0)->is_CountedLoopEnd()) return multi_version_succeeded;
2609 CountedLoopEndNode* rce_loop_end = p_f->in(0)->as_CountedLoopEnd();
2610 if (rce_loop_end == NULL) return multi_version_succeeded;
2611 CountedLoopNode* rce_cl = rce_loop_end->loopnode();
2612 if (rce_cl == NULL || !rce_cl->is_post_loop()) return multi_version_succeeded;
2613 CountedLoopNode *known_rce_cl = rce_loop->_head->as_CountedLoop();
2614 if (rce_cl != known_rce_cl) return multi_version_succeeded;
2615
2616 // Then we fetch the cover entry test
2617 ctrl = rce_cl->in(LoopNode::EntryControl);
2618 if (!ctrl->is_IfTrue() && !ctrl->is_IfFalse()) return multi_version_succeeded;
2619
2620 #ifndef PRODUCT
2621 if (TraceLoopOpts) {
2622 tty->print("PostMultiVersion\n");
2623 rce_loop->dump_head();
2624 legacy_loop->dump_head();
2625 }
2626 #endif
2627
2628 // Now fetch the limit we want to compare against
2629 Node *limit = rce_cl->limit();
2630 bool first_time = true;
2631
2632 // If we got this far, we identified the post loop which has been RCE'd and
2633 // we have a work list. Now we will try to transform the if guard to cause
2634 // the loop pair to be multi version executed with the determination left to runtime
2635 // or the optimizer if full information is known about the given arrays at compile time.
2636 Node *last_min = NULL;
2637 multi_version_succeeded = true;
2638 while (worklist.size()) {
2639 Node* rc_iffm = worklist.pop();
2640 if (rc_iffm->is_If()) {
2641 Node *rc_bolzm = rc_iffm->in(1);
2642 if (rc_bolzm->is_Bool()) {
2643 Node *rc_cmpzm = rc_bolzm->in(1);
2644 if (rc_cmpzm->is_Cmp()) {
2645 Node *rc_left = rc_cmpzm->in(2);
2646 if (rc_left->Opcode() != Op_LoadRange) {
2647 multi_version_succeeded = false;
2648 break;
2649 }
2650 if (first_time) {
2651 last_min = rc_left;
2652 first_time = false;
2653 } else {
2654 Node *cur_min = new MinINode(last_min, rc_left);
2655 last_min = cur_min;
2656 _igvn.register_new_node_with_optimizer(last_min);
2657 }
2658 }
2659 }
2660 }
2661 }
2662
2663 // All we have to do is update the limit of the rce loop
2664 // with the min of our expression and the current limit.
2665 // We will use this expression to replace the current limit.
2666 if (last_min && multi_version_succeeded) {
2667 Node *cur_min = new MinINode(last_min, limit);
2668 _igvn.register_new_node_with_optimizer(cur_min);
2669 Node *cmp_node = rce_loop_end->cmp_node();
2670 _igvn.replace_input_of(cmp_node, 2, cur_min);
2671 set_ctrl(cur_min, ctrl);
2672 set_loop(cur_min, rce_loop->_parent);
2673
2674 legacy_cl->mark_is_multiversioned();
2675 rce_cl->mark_is_multiversioned();
2676 multi_version_succeeded = true;
2677
2678 C->set_major_progress();
2679 }
2680
2681 return multi_version_succeeded;
2682 }
2683
2684 //-------------------------poison_rce_post_loop--------------------------------
2685 // Causes the rce'd post loop to be optimized away if multiversioning fails
2686 void PhaseIdealLoop::poison_rce_post_loop(IdealLoopTree *rce_loop) {
2687 CountedLoopNode *rce_cl = rce_loop->_head->as_CountedLoop();
2688 Node* ctrl = rce_cl->in(LoopNode::EntryControl);
2689 if (ctrl->is_IfTrue() || ctrl->is_IfFalse()) {
2690 Node* iffm = ctrl->in(0);
2691 if (iffm->is_If()) {
2692 Node* cur_bool = iffm->in(1);
2693 if (cur_bool->is_Bool()) {
2694 Node* cur_cmp = cur_bool->in(1);
2695 if (cur_cmp->is_Cmp()) {
2696 BoolTest::mask new_test = BoolTest::gt;
2697 BoolNode *new_bool = new BoolNode(cur_cmp, new_test);
2698 _igvn.replace_node(cur_bool, new_bool);
2699 _igvn._worklist.push(new_bool);
2700 Node* left_op = cur_cmp->in(1);
2701 _igvn.replace_input_of(cur_cmp, 2, left_op);
2702 C->set_major_progress();
2703 }
2704 }
2705 }
2706 }
2707 }
2708
2709 //------------------------------DCE_loop_body----------------------------------
2710 // Remove simplistic dead code from loop body
2711 void IdealLoopTree::DCE_loop_body() {
2712 for( uint i = 0; i < _body.size(); i++ )
2713 if( _body.at(i)->outcnt() == 0 )
2714 _body.map( i--, _body.pop() );
2715 }
2716
2717
2718 //------------------------------adjust_loop_exit_prob--------------------------
2719 // Look for loop-exit tests with the 50/50 (or worse) guesses from the parsing stage.
2720 // Replace with a 1-in-10 exit guess.
2721 void IdealLoopTree::adjust_loop_exit_prob( PhaseIdealLoop *phase ) {
2722 Node *test = tail();
2723 while( test != _head ) {
2724 uint top = test->Opcode();
2725 if( top == Op_IfTrue || top == Op_IfFalse ) {
2726 int test_con = ((ProjNode*)test)->_con;
2727 assert(top == (uint)(test_con? Op_IfTrue: Op_IfFalse), "sanity");
2728 IfNode *iff = test->in(0)->as_If();
2729 if( iff->outcnt() == 2 ) { // Ignore dead tests
2730 Node *bol = iff->in(1);
2731 if( bol && bol->req() > 1 && bol->in(1) &&
2732 ((bol->in(1)->Opcode() == Op_StorePConditional ) ||
2733 (bol->in(1)->Opcode() == Op_StoreIConditional ) ||
2734 (bol->in(1)->Opcode() == Op_StoreLConditional ) ||
2735 (bol->in(1)->Opcode() == Op_CompareAndExchangeB ) ||
2736 (bol->in(1)->Opcode() == Op_CompareAndExchangeS ) ||
2737 (bol->in(1)->Opcode() == Op_CompareAndExchangeI ) ||
2738 (bol->in(1)->Opcode() == Op_CompareAndExchangeL ) ||
2739 (bol->in(1)->Opcode() == Op_CompareAndExchangeP ) ||
2740 (bol->in(1)->Opcode() == Op_CompareAndExchangeN ) ||
2741 (bol->in(1)->Opcode() == Op_WeakCompareAndSwapB ) ||
2742 (bol->in(1)->Opcode() == Op_WeakCompareAndSwapS ) ||
2743 (bol->in(1)->Opcode() == Op_WeakCompareAndSwapI ) ||
2744 (bol->in(1)->Opcode() == Op_WeakCompareAndSwapL ) ||
2745 (bol->in(1)->Opcode() == Op_WeakCompareAndSwapP ) ||
2746 (bol->in(1)->Opcode() == Op_WeakCompareAndSwapN ) ||
2747 (bol->in(1)->Opcode() == Op_CompareAndSwapB ) ||
2748 (bol->in(1)->Opcode() == Op_CompareAndSwapS ) ||
2749 (bol->in(1)->Opcode() == Op_CompareAndSwapI ) ||
2750 (bol->in(1)->Opcode() == Op_CompareAndSwapL ) ||
2751 (bol->in(1)->Opcode() == Op_CompareAndSwapP ) ||
2752 (bol->in(1)->Opcode() == Op_CompareAndSwapN )))
2753 return; // Allocation loops RARELY take backedge
2754 // Find the OTHER exit path from the IF
2755 Node* ex = iff->proj_out(1-test_con);
2756 float p = iff->_prob;
2757 if( !phase->is_member( this, ex ) && iff->_fcnt == COUNT_UNKNOWN ) {
2758 if( top == Op_IfTrue ) {
2759 if( p < (PROB_FAIR + PROB_UNLIKELY_MAG(3))) {
2760 iff->_prob = PROB_STATIC_FREQUENT;
2761 }
2762 } else {
2763 if( p > (PROB_FAIR - PROB_UNLIKELY_MAG(3))) {
2764 iff->_prob = PROB_STATIC_INFREQUENT;
2765 }
2766 }
2767 }
2768 }
2769 }
2770 test = phase->idom(test);
2771 }
2772 }
2773
2774 #ifdef ASSERT
2775 static CountedLoopNode* locate_pre_from_main(CountedLoopNode *cl) {
2776 Node *ctrl = cl->skip_predicates();
2777 assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
2778 Node *iffm = ctrl->in(0);
2779 assert(iffm->Opcode() == Op_If, "");
2780 Node *p_f = iffm->in(0);
2781 assert(p_f->Opcode() == Op_IfFalse, "");
2782 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
2783 assert(pre_end->loopnode()->is_pre_loop(), "");
2784 return pre_end->loopnode();
2785 }
2786 #endif
2787
2788 // Remove the main and post loops and make the pre loop execute all
2789 // iterations. Useful when the pre loop is found empty.
2790 void IdealLoopTree::remove_main_post_loops(CountedLoopNode *cl, PhaseIdealLoop *phase) {
2791 CountedLoopEndNode* pre_end = cl->loopexit();
2792 Node* pre_cmp = pre_end->cmp_node();
2793 if (pre_cmp->in(2)->Opcode() != Op_Opaque1) {
2794 // Only safe to remove the main loop if the compiler optimized it
2795 // out based on an unknown number of iterations
2796 return;
2797 }
2798
2799 // Can we find the main loop?
2800 if (_next == NULL) {
2801 return;
2802 }
2803
2804 Node* next_head = _next->_head;
2805 if (!next_head->is_CountedLoop()) {
2806 return;
2807 }
2808
2809 CountedLoopNode* main_head = next_head->as_CountedLoop();
2810 if (!main_head->is_main_loop()) {
2811 return;
2812 }
2813
2814 assert(locate_pre_from_main(main_head) == cl, "bad main loop");
2815 Node* main_iff = main_head->skip_predicates()->in(0);
2816
2817 // Remove the Opaque1Node of the pre loop and make it execute all iterations
2818 phase->_igvn.replace_input_of(pre_cmp, 2, pre_cmp->in(2)->in(2));
2819 // Remove the Opaque1Node of the main loop so it can be optimized out
2820 Node* main_cmp = main_iff->in(1)->in(1);
2821 assert(main_cmp->in(2)->Opcode() == Op_Opaque1, "main loop has no opaque node?");
2822 phase->_igvn.replace_input_of(main_cmp, 2, main_cmp->in(2)->in(1));
2823 }
2824
2825 //------------------------------policy_do_remove_empty_loop--------------------
2826 // Micro-benchmark spamming. Policy is to always remove empty loops.
2827 // The 'DO' part is to replace the trip counter with the value it will
2828 // have on the last iteration. This will break the loop.
2829 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) {
2830 // Minimum size must be empty loop
2831 if (_body.size() > EMPTY_LOOP_SIZE)
2832 return false;
2833
2834 if (!_head->is_CountedLoop())
2835 return false; // Dead loop
2836 CountedLoopNode *cl = _head->as_CountedLoop();
2837 if (!cl->is_valid_counted_loop())
2838 return false; // Malformed loop
2839 if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
2840 return false; // Infinite loop
2841
2842 if (cl->is_pre_loop()) {
2843 // If the loop we are removing is a pre-loop then the main and
2844 // post loop can be removed as well
2845 remove_main_post_loops(cl, phase);
2846 }
2847
2848 #ifdef ASSERT
2849 // Ensure only one phi which is the iv.
2850 Node* iv = NULL;
2851 for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) {
2852 Node* n = cl->fast_out(i);
2853 if (n->Opcode() == Op_Phi) {
2854 assert(iv == NULL, "Too many phis" );
2855 iv = n;
2856 }
2857 }
2858 assert(iv == cl->phi(), "Wrong phi" );
2859 #endif
2860
2861 // main and post loops have explicitly created zero trip guard
2862 bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
2863 if (needs_guard) {
2864 // Skip guard if values not overlap.
2865 const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
2866 const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
2867 int stride_con = cl->stride_con();
2868 if (stride_con > 0) {
2869 needs_guard = (init_t->_hi >= limit_t->_lo);
2870 } else {
2871 needs_guard = (init_t->_lo <= limit_t->_hi);
2872 }
2873 }
2874 if (needs_guard) {
2875 // Check for an obvious zero trip guard.
2876 Node* inctrl = PhaseIdealLoop::skip_all_loop_predicates(cl->skip_predicates());
2877 if (inctrl->Opcode() == Op_IfTrue || inctrl->Opcode() == Op_IfFalse) {
2878 bool maybe_swapped = (inctrl->Opcode() == Op_IfFalse);
2879 // The test should look like just the backedge of a CountedLoop
2880 Node* iff = inctrl->in(0);
2881 if (iff->is_If()) {
2882 Node* bol = iff->in(1);
2883 if (bol->is_Bool()) {
2884 BoolTest test = bol->as_Bool()->_test;
2885 if (maybe_swapped) {
2886 test._test = test.commute();
2887 test._test = test.negate();
2888 }
2889 if (test._test == cl->loopexit()->test_trip()) {
2890 Node* cmp = bol->in(1);
2891 int init_idx = maybe_swapped ? 2 : 1;
2892 int limit_idx = maybe_swapped ? 1 : 2;
2893 if (cmp->is_Cmp() && cmp->in(init_idx) == cl->init_trip() && cmp->in(limit_idx) == cl->limit()) {
2894 needs_guard = false;
2895 }
2896 }
2897 }
2898 }
2899 }
2900 }
2901
2902 #ifndef PRODUCT
2903 if (PrintOpto) {
2904 tty->print("Removing empty loop with%s zero trip guard", needs_guard ? "out" : "");
2905 this->dump_head();
2906 } else if (TraceLoopOpts) {
2907 tty->print("Empty with%s zero trip guard ", needs_guard ? "out" : "");
2908 this->dump_head();
2909 }
2910 #endif
2911
2912 if (needs_guard) {
2913 // Peel the loop to ensure there's a zero trip guard
2914 Node_List old_new;
2915 phase->do_peeling(this, old_new);
2916 }
2917
2918 // Replace the phi at loop head with the final value of the last
2919 // iteration. Then the CountedLoopEnd will collapse (backedge never
2920 // taken) and all loop-invariant uses of the exit values will be correct.
2921 Node *phi = cl->phi();
2922 Node *exact_limit = phase->exact_limit(this);
2923 if (exact_limit != cl->limit()) {
2924 // We also need to replace the original limit to collapse loop exit.
2925 Node* cmp = cl->loopexit()->cmp_node();
2926 assert(cl->limit() == cmp->in(2), "sanity");
2927 phase->_igvn._worklist.push(cmp->in(2)); // put limit on worklist
2928 phase->_igvn.replace_input_of(cmp, 2, exact_limit); // put cmp on worklist
2929 }
2930 // Note: the final value after increment should not overflow since
2931 // counted loop has limit check predicate.
2932 Node *final = new SubINode( exact_limit, cl->stride() );
2933 phase->register_new_node(final,cl->in(LoopNode::EntryControl));
2934 phase->_igvn.replace_node(phi,final);
2935 phase->C->set_major_progress();
2936 return true;
2937 }
2938
2939 //------------------------------policy_do_one_iteration_loop-------------------
2940 // Convert one iteration loop into normal code.
2941 bool IdealLoopTree::policy_do_one_iteration_loop( PhaseIdealLoop *phase ) {
2942 if (!_head->as_Loop()->is_valid_counted_loop())
2943 return false; // Only for counted loop
2944
2945 CountedLoopNode *cl = _head->as_CountedLoop();
2946 if (!cl->has_exact_trip_count() || cl->trip_count() != 1) {
2947 return false;
2948 }
2949
2950 #ifndef PRODUCT
2951 if(TraceLoopOpts) {
2952 tty->print("OneIteration ");
2953 this->dump_head();
2954 }
2955 #endif
2956
2957 Node *init_n = cl->init_trip();
2958 #ifdef ASSERT
2959 // Loop boundaries should be constant since trip count is exact.
2960 assert(init_n->get_int() + cl->stride_con() >= cl->limit()->get_int(), "should be one iteration");
2961 #endif
2962 // Replace the phi at loop head with the value of the init_trip.
2963 // Then the CountedLoopEnd will collapse (backedge will not be taken)
2964 // and all loop-invariant uses of the exit values will be correct.
2965 phase->_igvn.replace_node(cl->phi(), cl->init_trip());
2966 phase->C->set_major_progress();
2967 return true;
2968 }
2969
2970 //=============================================================================
2971 //------------------------------iteration_split_impl---------------------------
2972 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) {
2973 // Compute loop trip count if possible.
2974 compute_trip_count(phase);
2975
2976 // Convert one iteration loop into normal code.
2977 if (policy_do_one_iteration_loop(phase))
2978 return true;
2979
2980 // Check and remove empty loops (spam micro-benchmarks)
2981 if (policy_do_remove_empty_loop(phase))
2982 return true; // Here we removed an empty loop
2983
2984 bool should_peel = policy_peeling(phase); // Should we peel?
2985
2986 bool should_unswitch = policy_unswitching(phase);
2987
2988 // Non-counted loops may be peeled; exactly 1 iteration is peeled.
2989 // This removes loop-invariant tests (usually null checks).
2990 if (!_head->is_CountedLoop()) { // Non-counted loop
2991 if (PartialPeelLoop && phase->partial_peel(this, old_new)) {
2992 // Partial peel succeeded so terminate this round of loop opts
2993 return false;
2994 }
2995 if (should_peel) { // Should we peel?
2996 if (PrintOpto) { tty->print_cr("should_peel"); }
2997 phase->do_peeling(this,old_new);
2998 } else if (should_unswitch) {
2999 phase->do_unswitching(this, old_new);
3000 }
3001 return true;
3002 }
3003 CountedLoopNode *cl = _head->as_CountedLoop();
3004
3005 if (!cl->is_valid_counted_loop()) return true; // Ignore various kinds of broken loops
3006
3007 // Do nothing special to pre- and post- loops
3008 if (cl->is_pre_loop() || cl->is_post_loop()) return true;
3009
3010 // Compute loop trip count from profile data
3011 compute_profile_trip_cnt(phase);
3012
3013 // Before attempting fancy unrolling, RCE or alignment, see if we want
3014 // to completely unroll this loop or do loop unswitching.
3015 if (cl->is_normal_loop()) {
3016 if (should_unswitch) {
3017 phase->do_unswitching(this, old_new);
3018 return true;
3019 }
3020 bool should_maximally_unroll = policy_maximally_unroll(phase);
3021 if (should_maximally_unroll) {
3022 // Here we did some unrolling and peeling. Eventually we will
3023 // completely unroll this loop and it will no longer be a loop.
3024 phase->do_maximally_unroll(this,old_new);
3025 return true;
3026 }
3027 }
3028
3029 // Skip next optimizations if running low on nodes. Note that
3030 // policy_unswitching and policy_maximally_unroll have this check.
3031 int nodes_left = phase->C->max_node_limit() - phase->C->live_nodes();
3032 if ((int)(2 * _body.size()) > nodes_left) {
3033 return true;
3034 }
3035
3036 // Counted loops may be peeled, may need some iterations run up
3037 // front for RCE, and may want to align loop refs to a cache
3038 // line. Thus we clone a full loop up front whose trip count is
3039 // at least 1 (if peeling), but may be several more.
3040
3041 // The main loop will start cache-line aligned with at least 1
3042 // iteration of the unrolled body (zero-trip test required) and
3043 // will have some range checks removed.
3044
3045 // A post-loop will finish any odd iterations (leftover after
3046 // unrolling), plus any needed for RCE purposes.
3047
3048 bool should_unroll = policy_unroll(phase);
3049
3050 bool should_rce = policy_range_check(phase);
3051
3052 bool should_align = policy_align(phase);
3053
3054 // If not RCE'ing (iteration splitting) or Aligning, then we do not
3055 // need a pre-loop. We may still need to peel an initial iteration but
3056 // we will not be needing an unknown number of pre-iterations.
3057 //
3058 // Basically, if may_rce_align reports FALSE first time through,
3059 // we will not be able to later do RCE or Aligning on this loop.
3060 bool may_rce_align = !policy_peel_only(phase) || should_rce || should_align;
3061
3062 // If we have any of these conditions (RCE, alignment, unrolling) met, then
3063 // we switch to the pre-/main-/post-loop model. This model also covers
3064 // peeling.
3065 if (should_rce || should_align || should_unroll) {
3066 if (cl->is_normal_loop()) // Convert to 'pre/main/post' loops
3067 phase->insert_pre_post_loops(this,old_new, !may_rce_align);
3068
3069 // Adjust the pre- and main-loop limits to let the pre and post loops run
3070 // with full checks, but the main-loop with no checks. Remove said
3071 // checks from the main body.
3072 if (should_rce) {
3073 if (phase->do_range_check(this, old_new) != 0) {
3074 cl->mark_has_range_checks();
3075 }
3076 } else if (PostLoopMultiversioning) {
3077 phase->has_range_checks(this);
3078 }
3079
3080 if (should_unroll && !should_peel && PostLoopMultiversioning) {
3081 // Try to setup multiversioning on main loops before they are unrolled
3082 if (cl->is_main_loop() && (cl->unrolled_count() == 1)) {
3083 phase->insert_scalar_rced_post_loop(this, old_new);
3084 }
3085 }
3086
3087 // Double loop body for unrolling. Adjust the minimum-trip test (will do
3088 // twice as many iterations as before) and the main body limit (only do
3089 // an even number of trips). If we are peeling, we might enable some RCE
3090 // and we'd rather unroll the post-RCE'd loop SO... do not unroll if
3091 // peeling.
3092 if (should_unroll && !should_peel) {
3093 if (SuperWordLoopUnrollAnalysis) {
3094 phase->insert_vector_post_loop(this, old_new);
3095 }
3096 phase->do_unroll(this, old_new, true);
3097 }
3098
3099 // Adjust the pre-loop limits to align the main body
3100 // iterations.
3101 if (should_align)
3102 Unimplemented();
3103
3104 } else { // Else we have an unchanged counted loop
3105 if (should_peel) // Might want to peel but do nothing else
3106 phase->do_peeling(this,old_new);
3107 }
3108 return true;
3109 }
3110
3111
3112 //=============================================================================
3113 //------------------------------iteration_split--------------------------------
3114 bool IdealLoopTree::iteration_split( PhaseIdealLoop *phase, Node_List &old_new ) {
3115 // Recursively iteration split nested loops
3116 if (_child && !_child->iteration_split(phase, old_new))
3117 return false;
3118
3119 // Clean out prior deadwood
3120 DCE_loop_body();
3121
3122
3123 // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
3124 // Replace with a 1-in-10 exit guess.
3125 if (_parent /*not the root loop*/ &&
3126 !_irreducible &&
3127 // Also ignore the occasional dead backedge
3128 !tail()->is_top()) {
3129 adjust_loop_exit_prob(phase);
3130 }
3131
3132 // Gate unrolling, RCE and peeling efforts.
3133 if (!_child && // If not an inner loop, do not split
3134 !_irreducible &&
3135 _allow_optimizations &&
3136 !tail()->is_top()) { // Also ignore the occasional dead backedge
3137 if (!_has_call) {
3138 if (!iteration_split_impl(phase, old_new)) {
3139 return false;
3140 }
3141 } else if (policy_unswitching(phase)) {
3142 phase->do_unswitching(this, old_new);
3143 }
3144 }
3145
3146 // Minor offset re-organization to remove loop-fallout uses of
3147 // trip counter when there was no major reshaping.
3148 phase->reorg_offsets(this);
3149
3150 if (_next && !_next->iteration_split(phase, old_new))
3151 return false;
3152 return true;
3153 }
3154
3155
3156 //=============================================================================
3157 // Process all the loops in the loop tree and replace any fill
3158 // patterns with an intrinsic version.
3159 bool PhaseIdealLoop::do_intrinsify_fill() {
3160 bool changed = false;
3161 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
3162 IdealLoopTree* lpt = iter.current();
3163 changed |= intrinsify_fill(lpt);
3164 }
3165 return changed;
3166 }
3167
3168
3169 // Examine an inner loop looking for a a single store of an invariant
3170 // value in a unit stride loop,
3171 bool PhaseIdealLoop::match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
3172 Node*& shift, Node*& con) {
3173 const char* msg = NULL;
3174 Node* msg_node = NULL;
3175
3176 store_value = NULL;
3177 con = NULL;
3178 shift = NULL;
3179
3180 // Process the loop looking for stores. If there are multiple
3181 // stores or extra control flow give at this point.
3182 CountedLoopNode* head = lpt->_head->as_CountedLoop();
3183 for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
3184 Node* n = lpt->_body.at(i);
3185 if (n->outcnt() == 0) continue; // Ignore dead
3186 if (n->is_Store()) {
3187 if (store != NULL) {
3188 msg = "multiple stores";
3189 break;
3190 }
3191 int opc = n->Opcode();
3192 if (opc == Op_StoreP || opc == Op_StoreN || opc == Op_StoreNKlass || opc == Op_StoreCM) {
3193 msg = "oop fills not handled";
3194 break;
3195 }
3196 Node* value = n->in(MemNode::ValueIn);
3197 if (!lpt->is_invariant(value)) {
3198 msg = "variant store value";
3199 } else if (!_igvn.type(n->in(MemNode::Address))->isa_aryptr()) {
3200 msg = "not array address";
3201 }
3202 store = n;
3203 store_value = value;
3204 } else if (n->is_If() && n != head->loopexit_or_null()) {
3205 msg = "extra control flow";
3206 msg_node = n;
3207 }
3208 }
3209
3210 if (store == NULL) {
3211 // No store in loop
3212 return false;
3213 }
3214
3215 if (msg == NULL && head->stride_con() != 1) {
3216 // could handle negative strides too
3217 if (head->stride_con() < 0) {
3218 msg = "negative stride";
3219 } else {
3220 msg = "non-unit stride";
3221 }
3222 }
3223
3224 if (msg == NULL && !store->in(MemNode::Address)->is_AddP()) {
3225 msg = "can't handle store address";
3226 msg_node = store->in(MemNode::Address);
3227 }
3228
3229 if (msg == NULL &&
3230 (!store->in(MemNode::Memory)->is_Phi() ||
3231 store->in(MemNode::Memory)->in(LoopNode::LoopBackControl) != store)) {
3232 msg = "store memory isn't proper phi";
3233 msg_node = store->in(MemNode::Memory);
3234 }
3235
3236 // Make sure there is an appropriate fill routine
3237 BasicType t = store->as_Mem()->memory_type();
3238 const char* fill_name;
3239 if (msg == NULL &&
3240 StubRoutines::select_fill_function(t, false, fill_name) == NULL) {
3241 msg = "unsupported store";
3242 msg_node = store;
3243 }
3244
3245 if (msg != NULL) {
3246 #ifndef PRODUCT
3247 if (TraceOptimizeFill) {
3248 tty->print_cr("not fill intrinsic candidate: %s", msg);
3249 if (msg_node != NULL) msg_node->dump();
3250 }
3251 #endif
3252 return false;
3253 }
3254
3255 // Make sure the address expression can be handled. It should be
3256 // head->phi * elsize + con. head->phi might have a ConvI2L(CastII()).
3257 Node* elements[4];
3258 Node* cast = NULL;
3259 Node* conv = NULL;
3260 bool found_index = false;
3261 int count = store->in(MemNode::Address)->as_AddP()->unpack_offsets(elements, ARRAY_SIZE(elements));
3262 for (int e = 0; e < count; e++) {
3263 Node* n = elements[e];
3264 if (n->is_Con() && con == NULL) {
3265 con = n;
3266 } else if (n->Opcode() == Op_LShiftX && shift == NULL) {
3267 Node* value = n->in(1);
3268 #ifdef _LP64
3269 if (value->Opcode() == Op_ConvI2L) {
3270 conv = value;
3271 value = value->in(1);
3272 }
3273 if (value->Opcode() == Op_CastII &&
3274 value->as_CastII()->has_range_check()) {
3275 // Skip range check dependent CastII nodes
3276 cast = value;
3277 value = value->in(1);
3278 }
3279 #endif
3280 if (value != head->phi()) {
3281 msg = "unhandled shift in address";
3282 } else {
3283 if (type2aelembytes(store->as_Mem()->memory_type(), true) != (1 << n->in(2)->get_int())) {
3284 msg = "scale doesn't match";
3285 } else {
3286 found_index = true;
3287 shift = n;
3288 }
3289 }
3290 } else if (n->Opcode() == Op_ConvI2L && conv == NULL) {
3291 conv = n;
3292 n = n->in(1);
3293 if (n->Opcode() == Op_CastII &&
3294 n->as_CastII()->has_range_check()) {
3295 // Skip range check dependent CastII nodes
3296 cast = n;
3297 n = n->in(1);
3298 }
3299 if (n == head->phi()) {
3300 found_index = true;
3301 } else {
3302 msg = "unhandled input to ConvI2L";
3303 }
3304 } else if (n == head->phi()) {
3305 // no shift, check below for allowed cases
3306 found_index = true;
3307 } else {
3308 msg = "unhandled node in address";
3309 msg_node = n;
3310 }
3311 }
3312
3313 if (count == -1) {
3314 msg = "malformed address expression";
3315 msg_node = store;
3316 }
3317
3318 if (!found_index) {
3319 msg = "missing use of index";
3320 }
3321
3322 // byte sized items won't have a shift
3323 if (msg == NULL && shift == NULL && t != T_BYTE && t != T_BOOLEAN) {
3324 msg = "can't find shift";
3325 msg_node = store;
3326 }
3327
3328 if (msg != NULL) {
3329 #ifndef PRODUCT
3330 if (TraceOptimizeFill) {
3331 tty->print_cr("not fill intrinsic: %s", msg);
3332 if (msg_node != NULL) msg_node->dump();
3333 }
3334 #endif
3335 return false;
3336 }
3337
3338 // No make sure all the other nodes in the loop can be handled
3339 VectorSet ok(Thread::current()->resource_area());
3340
3341 // store related values are ok
3342 ok.set(store->_idx);
3343 ok.set(store->in(MemNode::Memory)->_idx);
3344
3345 CountedLoopEndNode* loop_exit = head->loopexit();
3346
3347 // Loop structure is ok
3348 ok.set(head->_idx);
3349 ok.set(loop_exit->_idx);
3350 ok.set(head->phi()->_idx);
3351 ok.set(head->incr()->_idx);
3352 ok.set(loop_exit->cmp_node()->_idx);
3353 ok.set(loop_exit->in(1)->_idx);
3354
3355 // Address elements are ok
3356 if (con) ok.set(con->_idx);
3357 if (shift) ok.set(shift->_idx);
3358 if (cast) ok.set(cast->_idx);
3359 if (conv) ok.set(conv->_idx);
3360
3361 for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
3362 Node* n = lpt->_body.at(i);
3363 if (n->outcnt() == 0) continue; // Ignore dead
3364 if (ok.test(n->_idx)) continue;
3365 // Backedge projection is ok
3366 if (n->is_IfTrue() && n->in(0) == loop_exit) continue;
3367 if (!n->is_AddP()) {
3368 msg = "unhandled node";
3369 msg_node = n;
3370 break;
3371 }
3372 }
3373
3374 // Make sure no unexpected values are used outside the loop
3375 for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
3376 Node* n = lpt->_body.at(i);
3377 // These values can be replaced with other nodes if they are used
3378 // outside the loop.
3379 if (n == store || n == loop_exit || n == head->incr() || n == store->in(MemNode::Memory)) continue;
3380 for (SimpleDUIterator iter(n); iter.has_next(); iter.next()) {
3381 Node* use = iter.get();
3382 if (!lpt->_body.contains(use)) {
3383 msg = "node is used outside loop";
3384 // lpt->_body.dump();
3385 msg_node = n;
3386 break;
3387 }
3388 }
3389 }
3390
3391 #ifdef ASSERT
3392 if (TraceOptimizeFill) {
3393 if (msg != NULL) {
3394 tty->print_cr("no fill intrinsic: %s", msg);
3395 if (msg_node != NULL) msg_node->dump();
3396 } else {
3397 tty->print_cr("fill intrinsic for:");
3398 }
3399 store->dump();
3400 if (Verbose) {
3401 lpt->_body.dump();
3402 }
3403 }
3404 #endif
3405
3406 return msg == NULL;
3407 }
3408
3409
3410
3411 bool PhaseIdealLoop::intrinsify_fill(IdealLoopTree* lpt) {
3412 // Only for counted inner loops
3413 if (!lpt->is_counted() || !lpt->is_inner()) {
3414 return false;
3415 }
3416
3417 // Must have constant stride
3418 CountedLoopNode* head = lpt->_head->as_CountedLoop();
3419 if (!head->is_valid_counted_loop() || !head->is_normal_loop()) {
3420 return false;
3421 }
3422
3423 head->verify_strip_mined(1);
3424
3425 // Check that the body only contains a store of a loop invariant
3426 // value that is indexed by the loop phi.
3427 Node* store = NULL;
3428 Node* store_value = NULL;
3429 Node* shift = NULL;
3430 Node* offset = NULL;
3431 if (!match_fill_loop(lpt, store, store_value, shift, offset)) {
3432 return false;
3433 }
3434
3435 Node* exit = head->loopexit()->proj_out_or_null(0);
3436 if (exit == NULL) {
3437 return false;
3438 }
3439
3440 #ifndef PRODUCT
3441 if (TraceLoopOpts) {
3442 tty->print("ArrayFill ");
3443 lpt->dump_head();
3444 }
3445 #endif
3446
3447 // Now replace the whole loop body by a call to a fill routine that
3448 // covers the same region as the loop.
3449 Node* base = store->in(MemNode::Address)->as_AddP()->in(AddPNode::Base);
3450
3451 // Build an expression for the beginning of the copy region
3452 Node* index = head->init_trip();
3453 #ifdef _LP64
3454 index = new ConvI2LNode(index);
3455 _igvn.register_new_node_with_optimizer(index);
3456 #endif
3457 if (shift != NULL) {
3458 // byte arrays don't require a shift but others do.
3459 index = new LShiftXNode(index, shift->in(2));
3460 _igvn.register_new_node_with_optimizer(index);
3461 }
3462 index = new AddPNode(base, base, index);
3463 _igvn.register_new_node_with_optimizer(index);
3464 Node* from = new AddPNode(base, index, offset);
3465 _igvn.register_new_node_with_optimizer(from);
3466 // Compute the number of elements to copy
3467 Node* len = new SubINode(head->limit(), head->init_trip());
3468 _igvn.register_new_node_with_optimizer(len);
3469
3470 BasicType t = store->as_Mem()->memory_type();
3471 bool aligned = false;
3472 if (offset != NULL && head->init_trip()->is_Con()) {
3473 int element_size = type2aelembytes(t);
3474 aligned = (offset->find_intptr_t_type()->get_con() + head->init_trip()->get_int() * element_size) % HeapWordSize == 0;
3475 }
3476
3477 // Build a call to the fill routine
3478 const char* fill_name;
3479 address fill = StubRoutines::select_fill_function(t, aligned, fill_name);
3480 assert(fill != NULL, "what?");
3481
3482 // Convert float/double to int/long for fill routines
3483 if (t == T_FLOAT) {
3484 store_value = new MoveF2INode(store_value);
3485 _igvn.register_new_node_with_optimizer(store_value);
3486 } else if (t == T_DOUBLE) {
3487 store_value = new MoveD2LNode(store_value);
3488 _igvn.register_new_node_with_optimizer(store_value);
3489 }
3490
3491 Node* mem_phi = store->in(MemNode::Memory);
3492 Node* result_ctrl;
3493 Node* result_mem;
3494 const TypeFunc* call_type = OptoRuntime::array_fill_Type();
3495 CallLeafNode *call = new CallLeafNoFPNode(call_type, fill,
3496 fill_name, TypeAryPtr::get_array_body_type(t));
3497 uint cnt = 0;
3498 call->init_req(TypeFunc::Parms + cnt++, from);
3499 call->init_req(TypeFunc::Parms + cnt++, store_value);
3500 #ifdef _LP64
3501 len = new ConvI2LNode(len);
3502 _igvn.register_new_node_with_optimizer(len);
3503 #endif
3504 call->init_req(TypeFunc::Parms + cnt++, len);
3505 #ifdef _LP64
3506 call->init_req(TypeFunc::Parms + cnt++, C->top());
3507 #endif
3508 call->init_req(TypeFunc::Control, head->init_control());
3509 call->init_req(TypeFunc::I_O, C->top()); // Does no I/O.
3510 call->init_req(TypeFunc::Memory, mem_phi->in(LoopNode::EntryControl));
3511 call->init_req(TypeFunc::ReturnAdr, C->start()->proj_out_or_null(TypeFunc::ReturnAdr));
3512 call->init_req(TypeFunc::FramePtr, C->start()->proj_out_or_null(TypeFunc::FramePtr));
3513 _igvn.register_new_node_with_optimizer(call);
3514 result_ctrl = new ProjNode(call,TypeFunc::Control);
3515 _igvn.register_new_node_with_optimizer(result_ctrl);
3516 result_mem = new ProjNode(call,TypeFunc::Memory);
3517 _igvn.register_new_node_with_optimizer(result_mem);
3518
3519 /* Disable following optimization until proper fix (add missing checks).
3520
3521 // If this fill is tightly coupled to an allocation and overwrites
3522 // the whole body, allow it to take over the zeroing.
3523 AllocateNode* alloc = AllocateNode::Ideal_allocation(base, this);
3524 if (alloc != NULL && alloc->is_AllocateArray()) {
3525 Node* length = alloc->as_AllocateArray()->Ideal_length();
3526 if (head->limit() == length &&
3527 head->init_trip() == _igvn.intcon(0)) {
3528 if (TraceOptimizeFill) {
3529 tty->print_cr("Eliminated zeroing in allocation");
3530 }
3531 alloc->maybe_set_complete(&_igvn);
3532 } else {
3533 #ifdef ASSERT
3534 if (TraceOptimizeFill) {
3535 tty->print_cr("filling array but bounds don't match");
3536 alloc->dump();
3537 head->init_trip()->dump();
3538 head->limit()->dump();
3539 length->dump();
3540 }
3541 #endif
3542 }
3543 }
3544 */
3545
3546 if (head->is_strip_mined()) {
3547 // Inner strip mined loop goes away so get rid of outer strip
3548 // mined loop
3549 Node* outer_sfpt = head->outer_safepoint();
3550 Node* in = outer_sfpt->in(0);
3551 Node* outer_out = head->outer_loop_exit();
3552 lazy_replace(outer_out, in);
3553 _igvn.replace_input_of(outer_sfpt, 0, C->top());
3554 }
3555
3556 // Redirect the old control and memory edges that are outside the loop.
3557 // Sometimes the memory phi of the head is used as the outgoing
3558 // state of the loop. It's safe in this case to replace it with the
3559 // result_mem.
3560 _igvn.replace_node(store->in(MemNode::Memory), result_mem);
3561 lazy_replace(exit, result_ctrl);
3562 _igvn.replace_node(store, result_mem);
3563 // Any uses the increment outside of the loop become the loop limit.
3564 _igvn.replace_node(head->incr(), head->limit());
3565
3566 // Disconnect the head from the loop.
3567 for (uint i = 0; i < lpt->_body.size(); i++) {
3568 Node* n = lpt->_body.at(i);
3569 _igvn.replace_node(n, C->top());
3570 }
3571
3572 return true;
3573 }