189 iftrue_op != Op_IfFalse)
190 // I have a weird back-control. Probably the loop-exit test is in
191 // the middle of the loop and I am looking at some trailing control-flow
192 // merge point. To fix this I would have to partially peel the loop.
193 return false; // Obscure back-control
194
195 // Get boolean guarding loop-back test
196 Node *iff = iftrue->in(0);
197 if (get_loop(iff) != loop || !iff->in(1)->is_Bool())
198 return false;
199 BoolNode *test = iff->in(1)->as_Bool();
200 BoolTest::mask bt = test->_test._test;
201 float cl_prob = iff->as_If()->_prob;
202 if (iftrue_op == Op_IfFalse) {
203 bt = BoolTest(bt).negate();
204 cl_prob = 1.0 - cl_prob;
205 }
206 // Get backedge compare
207 Node *cmp = test->in(1);
208 int cmp_op = cmp->Opcode();
209 if( cmp_op != Op_CmpI )
210 return false; // Avoid pointer & float compares
211
212 // Find the trip-counter increment & limit. Limit must be loop invariant.
213 Node *incr = cmp->in(1);
214 Node *limit = cmp->in(2);
215
216 // ---------
217 // need 'loop()' test to tell if limit is loop invariant
218 // ---------
219
220 if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?
221 Node *tmp = incr; // Then reverse order into the CmpI
222 incr = limit;
223 limit = tmp;
224 bt = BoolTest(bt).commute(); // And commute the exit test
225 }
226 if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant
227 return false;
228 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
229 return false;
242 Node* trunc1 = NULL;
243 Node* trunc2 = NULL;
244 const TypeInt* iv_trunc_t = NULL;
245 if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {
246 return false; // Funny increment opcode
247 }
248 assert(incr->Opcode() == Op_AddI, "wrong increment code");
249
250 // Get merge point
251 Node *xphi = incr->in(1);
252 Node *stride = incr->in(2);
253 if (!stride->is_Con()) { // Oops, swap these
254 if (!xphi->is_Con()) // Is the other guy a constant?
255 return false; // Nope, unknown stride, bail out
256 Node *tmp = xphi; // 'incr' is commutative, so ok to swap
257 xphi = stride;
258 stride = tmp;
259 }
260 // Stride must be constant
261 int stride_con = stride->get_int();
262 assert(stride_con != 0, "missed some peephole opt");
263
264 if (!xphi->is_Phi())
265 return false; // Too much math on the trip counter
266 if (phi_incr != NULL && phi_incr != xphi)
267 return false;
268 PhiNode *phi = xphi->as_Phi();
269
270 // Phi must be of loop header; backedge must wrap to increment
271 if (phi->region() != x)
272 return false;
273 if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr ||
274 trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) {
275 return false;
276 }
277 Node *init_trip = phi->in(LoopNode::EntryControl);
278
279 // If iv trunc type is smaller than int, check for possible wrap.
280 if (!TypeInt::INT->higher_equal(iv_trunc_t)) {
281 assert(trunc1 != NULL, "must have found some truncation");
282
302 } else if (stride_con < 0) {
303 if (iv_trunc_t->_lo - phi_ft->_lo > stride_con ||
304 iv_trunc_t->_hi < phi_ft->_hi) {
305 return false; // truncation may occur
306 }
307 }
308 // No possibility of wrap so truncation can be discarded
309 // Promote iv type to Int
310 } else {
311 assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int");
312 }
313
314 // If the condition is inverted and we will be rolling
315 // through MININT to MAXINT, then bail out.
316 if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!
317 // Odd stride
318 bt == BoolTest::ne && stride_con != 1 && stride_con != -1 ||
319 // Count down loop rolls through MAXINT
320 (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 ||
321 // Count up loop rolls through MININT
322 (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0 ) {
323 return false; // Bail out
324 }
325
326 const TypeInt* init_t = gvn->type(init_trip)->is_int();
327 const TypeInt* limit_t = gvn->type(limit)->is_int();
328
329 if (stride_con > 0) {
330 long init_p = (long)init_t->_lo + stride_con;
331 if (init_p > (long)max_jint || init_p > (long)limit_t->_hi)
332 return false; // cyclic loop or this loop trips only once
333 } else {
334 long init_p = (long)init_t->_hi + stride_con;
335 if (init_p < (long)min_jint || init_p < (long)limit_t->_lo)
336 return false; // cyclic loop or this loop trips only once
337 }
338
339 // =================================================
340 // ---- SUCCESS! Found A Trip-Counted Loop! -----
341 //
342 assert(x->Opcode() == Op_Loop, "regular loops only");
343 C->print_method("Before CountedLoop", 3);
344 #ifndef PRODUCT
345 if (TraceLoopOpts) {
346 tty->print("Counted ");
347 loop->dump_head();
348 }
349 #endif
350 // If compare points to incr, we are ok. Otherwise the compare
351 // can directly point to the phi; in this case adjust the compare so that
352 // it points to the incr by adjusting the limit.
353 if (cmp->in(1) == phi || cmp->in(2) == phi)
354 limit = gvn->transform(new (C, 3) AddINode(limit,stride));
355
356 // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.
357 // Final value for iterator should be: trip_count * stride + init_trip.
358 Node *one_p = gvn->intcon( 1);
359 Node *one_m = gvn->intcon(-1);
360
361 Node *trip_count = NULL;
362 Node *hook = new (C, 6) Node(6);
363 switch( bt ) {
364 case BoolTest::eq:
365 ShouldNotReachHere();
366 case BoolTest::ne: // Ahh, the case we desire
367 if (stride_con == 1)
368 trip_count = gvn->transform(new (C, 3) SubINode(limit,init_trip));
369 else if (stride_con == -1)
370 trip_count = gvn->transform(new (C, 3) SubINode(init_trip,limit));
371 else
372 ShouldNotReachHere();
373 set_subtree_ctrl(trip_count);
374 //_loop.map(trip_count->_idx,loop(limit));
375 break;
376 case BoolTest::le: // Maybe convert to '<' case
377 limit = gvn->transform(new (C, 3) AddINode(limit,one_p));
378 set_subtree_ctrl( limit );
379 hook->init_req(4, limit);
380
381 bt = BoolTest::lt;
382 // Make the new limit be in the same loop nest as the old limit
424 hook->init_req(1, bias);
425
426 Node *bias1 = gvn->transform(new (C, 3) AddINode(bias,one_p));
427 set_subtree_ctrl( bias1 );
428 hook->init_req(2, bias1);
429
430 trip_count = gvn->transform(new (C, 3) DivINode(0,bias1,stride));
431 set_subtree_ctrl( trip_count );
432 hook->init_req(3, trip_count);
433 break;
434 }
435 } // switch( bt )
436
437 Node *span = gvn->transform(new (C, 3) MulINode(trip_count,stride));
438 set_subtree_ctrl( span );
439 hook->init_req(5, span);
440
441 limit = gvn->transform(new (C, 3) AddINode(span,init_trip));
442 set_subtree_ctrl( limit );
443
444 // Check for SafePoint on backedge and remove
445 Node *sfpt = x->in(LoopNode::LoopBackControl);
446 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
447 lazy_replace( sfpt, iftrue );
448 loop->_tail = iftrue;
449 }
450
451 // Build a canonical trip test.
452 // Clone code, as old values may be in use.
453 Node* nphi = PhiNode::make(x, init_trip, TypeInt::INT);
454 nphi = _igvn.register_new_node_with_optimizer(nphi);
455 set_ctrl(nphi, get_ctrl(phi));
456
457 incr = incr->clone();
458 incr->set_req(1,nphi);
459 incr->set_req(2,stride);
460 incr = _igvn.register_new_node_with_optimizer(incr);
461 set_early_ctrl( incr );
462
463 nphi->set_req(LoopNode::LoopBackControl, incr);
514 assert(iff->outcnt() == 0, "should be dead now");
515 lazy_replace( iff, le ); // fix 'get_ctrl'
516
517 // Now setup a new CountedLoopNode to replace the existing LoopNode
518 CountedLoopNode *l = new (C, 3) CountedLoopNode(init_control, back_control);
519 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve
520 // The following assert is approximately true, and defines the intention
521 // of can_be_counted_loop. It fails, however, because phase->type
522 // is not yet initialized for this loop and its parts.
523 //assert(l->can_be_counted_loop(this), "sanity");
524 _igvn.register_new_node_with_optimizer(l);
525 set_loop(l, loop);
526 loop->_head = l;
527 // Fix all data nodes placed at the old loop head.
528 // Uses the lazy-update mechanism of 'get_ctrl'.
529 lazy_replace( x, l );
530 set_idom(l, init_control, dom_depth(x));
531
532 // Check for immediately preceding SafePoint and remove
533 Node *sfpt2 = le->in(0);
534 if( sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2))
535 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
536
537 // Free up intermediate goo
538 _igvn.remove_dead_node(hook);
539
540 #ifdef ASSERT
541 assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
542 assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
543 #endif
544
545 C->print_method("After CountedLoop", 3);
546
547 return true;
548 }
549
550
551 //------------------------------Ideal------------------------------------------
552 // Return a node which is more "ideal" than the current node.
553 // Attempt to convert into a counted-loop.
554 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
555 if (!can_be_counted_loop(phase)) {
556 phase->C->set_major_progress();
557 }
558 return RegionNode::Ideal(phase, can_reshape);
559 }
560
561
562 //=============================================================================
563 //------------------------------Ideal------------------------------------------
564 // Return a node which is more "ideal" than the current node.
565 // Attempt to convert into a counted-loop.
566 Node *CountedLoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
567 return RegionNode::Ideal(phase, can_reshape);
568 }
569
570 //------------------------------dump_spec--------------------------------------
571 // Dump special per-node info
572 #ifndef PRODUCT
573 void CountedLoopNode::dump_spec(outputStream *st) const {
574 LoopNode::dump_spec(st);
575 if( stride_is_con() ) {
576 st->print("stride: %d ",stride_con());
577 } else {
578 st->print("stride: not constant ");
579 }
580 if( is_pre_loop () ) st->print("pre of N%d" , _main_idx );
581 if( is_main_loop() ) st->print("main of N%d", _idx );
582 if( is_post_loop() ) st->print("post of N%d", _main_idx );
583 }
584 #endif
585
586 //=============================================================================
587 int CountedLoopEndNode::stride_con() const {
588 return stride()->bottom_type()->is_int()->get_con();
589 }
590
591
592 //----------------------match_incr_with_optional_truncation--------------------
593 // Match increment with optional truncation:
594 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
595 // Return NULL for failure. Success returns the increment node.
596 Node* CountedLoopNode::match_incr_with_optional_truncation(
597 Node* expr, Node** trunc1, Node** trunc2, const TypeInt** trunc_type) {
598 // Quick cutouts:
599 if (expr == NULL || expr->req() != 3) return false;
600
601 Node *t1 = NULL;
602 Node *t2 = NULL;
603 const TypeInt* trunc_t = TypeInt::INT;
604 Node* n1 = expr;
605 int n1op = n1->Opcode();
606
607 // Try to strip (n1 & M) or (n1 << N >> N) from n1.
608 if (n1op == Op_AndI &&
609 n1->in(2)->is_Con() &&
610 n1->in(2)->bottom_type()->is_int()->get_con() == 0x7fff) {
611 // %%% This check should match any mask of 2**K-1.
853 igvn.register_new_node_with_optimizer(landing_pad, _head);
854 // Insert landing pad into the header
855 _head->add_req(landing_pad);
856 }
857
858 //------------------------------split_outer_loop-------------------------------
859 // Split out the outermost loop from this shared header.
860 void IdealLoopTree::split_outer_loop( PhaseIdealLoop *phase ) {
861 PhaseIterGVN &igvn = phase->_igvn;
862
863 // Find index of outermost loop; it should also be my tail.
864 uint outer_idx = 1;
865 while( _head->in(outer_idx) != _tail ) outer_idx++;
866
867 // Make a LoopNode for the outermost loop.
868 Node *ctl = _head->in(LoopNode::EntryControl);
869 Node *outer = new (phase->C, 3) LoopNode( ctl, _head->in(outer_idx) );
870 outer = igvn.register_new_node_with_optimizer(outer, _head);
871 phase->set_created_loop_node();
872
873 Node* pred = phase->clone_loop_predicates(ctl, outer);
874 // Outermost loop falls into '_head' loop
875 _head->set_req(LoopNode::EntryControl, pred);
876 _head->del_req(outer_idx);
877 // Split all the Phis up between '_head' loop and 'outer' loop.
878 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
879 Node *out = _head->fast_out(j);
880 if( out->is_Phi() ) {
881 PhiNode *old_phi = out->as_Phi();
882 assert( old_phi->region() == _head, "" );
883 Node *phi = PhiNode::make_blank(outer, old_phi);
884 phi->init_req(LoopNode::EntryControl, old_phi->in(LoopNode::EntryControl));
885 phi->init_req(LoopNode::LoopBackControl, old_phi->in(outer_idx));
886 phi = igvn.register_new_node_with_optimizer(phi, old_phi);
887 // Make old Phi point to new Phi on the fall-in path
888 igvn.hash_delete(old_phi);
889 old_phi->set_req(LoopNode::EntryControl, phi);
890 old_phi->del_req(outer_idx);
891 igvn._worklist.push(old_phi);
892 }
893 }
1423 for (; n != _head; n = phase->idom(n)) {
1424 if (n->Opcode() == Op_SafePoint && phase->get_loop(n) == this &&
1425 phase->is_deleteable_safept(n))
1426 phase->lazy_replace(n,n->in(TypeFunc::Control));
1427 }
1428 }
1429
1430 // Recursively
1431 if (_child) _child->counted_loop( phase );
1432 if (_next) _next ->counted_loop( phase );
1433 }
1434
1435 #ifndef PRODUCT
1436 //------------------------------dump_head--------------------------------------
1437 // Dump 1 liner for loop header info
1438 void IdealLoopTree::dump_head( ) const {
1439 for (uint i=0; i<_nest; i++)
1440 tty->print(" ");
1441 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
1442 if (_irreducible) tty->print(" IRREDUCIBLE");
1443 if (UseLoopPredicate) {
1444 Node* entry = PhaseIdealLoop::find_predicate_insertion_point(_head->in(LoopNode::EntryControl),
1445 Deoptimization::Reason_predicate);
1446 if (entry != NULL) {
1447 tty->print(" predicated");
1448 }
1449 }
1450 if (_head->is_CountedLoop()) {
1451 CountedLoopNode *cl = _head->as_CountedLoop();
1452 tty->print(" counted");
1453
1454 Node* init_n = cl->init_trip();
1455 if (init_n != NULL && init_n->is_Con())
1456 tty->print(" [%d,", cl->init_trip()->get_int());
1457 else
1458 tty->print(" [int,");
1459 Node* limit_n = cl->limit();
1460 if (limit_n != NULL && limit_n->is_Con())
1461 tty->print("%d),", cl->limit()->get_int());
1462 else
1463 tty->print("int),");
1464 int stride_con = cl->stride_con();
1465 if (stride_con > 0) tty->print("+");
1511 log->tail("loop");
1512 if( loop->_next ) log_loop_tree(root, loop->_next, log);
1513 }
1514 }
1515
1516 //---------------------collect_potentially_useful_predicates-----------------------
1517 // Helper function to collect potentially useful predicates to prevent them from
1518 // being eliminated by PhaseIdealLoop::eliminate_useless_predicates
1519 void PhaseIdealLoop::collect_potentially_useful_predicates(
1520 IdealLoopTree * loop, Unique_Node_List &useful_predicates) {
1521 if (loop->_child) { // child
1522 collect_potentially_useful_predicates(loop->_child, useful_predicates);
1523 }
1524
1525 // self (only loops that we can apply loop predication may use their predicates)
1526 if (loop->_head->is_Loop() &&
1527 !loop->_irreducible &&
1528 !loop->tail()->is_top()) {
1529 LoopNode* lpn = loop->_head->as_Loop();
1530 Node* entry = lpn->in(LoopNode::EntryControl);
1531 Node* predicate_proj = find_predicate(entry);
1532 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication
1533 assert(entry->in(0)->in(1)->in(1)->Opcode() == Op_Opaque1, "must be");
1534 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1535 }
1536 }
1537
1538 if (loop->_next) { // sibling
1539 collect_potentially_useful_predicates(loop->_next, useful_predicates);
1540 }
1541 }
1542
1543 //------------------------eliminate_useless_predicates-----------------------------
1544 // Eliminate all inserted predicates if they could not be used by loop predication.
1545 void PhaseIdealLoop::eliminate_useless_predicates() {
1546 if (C->predicate_count() == 0)
1547 return; // no predicate left
1548
1549 Unique_Node_List useful_predicates; // to store useful predicates
1550 if (C->has_loops()) {
1551 collect_potentially_useful_predicates(_ltree_root->_child, useful_predicates);
1552 }
1553
1554 for (int i = C->predicate_count(); i > 0; i--) {
1555 Node * n = C->predicate_opaque1_node(i-1);
1556 assert(n->Opcode() == Op_Opaque1, "must be");
1557 if (!useful_predicates.member(n)) { // not in the useful list
1558 _igvn.replace_node(n, n->in(1));
1559 }
1560 }
1561 }
1562
1563 //=============================================================================
1564 //----------------------------build_and_optimize-------------------------------
1714 visited.Clear();
1715 init_dom_lca_tags();
1716 // Need C->root() on worklist when processing outs
1717 worklist.push( C->root() );
1718 NOT_PRODUCT( C->verify_graph_edges(); )
1719 worklist.push( C->top() );
1720 build_loop_late( visited, worklist, nstack );
1721
1722 if (_verify_only) {
1723 // restore major progress flag
1724 for (int i = 0; i < old_progress; i++)
1725 C->set_major_progress();
1726 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
1727 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
1728 return;
1729 }
1730
1731 // Some parser-inserted loop predicates could never be used by loop
1732 // predication or they were moved away from loop during some optimizations.
1733 // For example, peeling. Eliminate them before next loop optimizations.
1734 if (UseLoopPredicate) {
1735 eliminate_useless_predicates();
1736 }
1737
1738 // clear out the dead code
1739 while(_deadlist.size()) {
1740 _igvn.remove_globally_dead_node(_deadlist.pop());
1741 }
1742
1743 #ifndef PRODUCT
1744 C->verify_graph_edges();
1745 if (_verify_me) { // Nested verify pass?
1746 // Check to see if the verify mode is broken
1747 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
1748 return;
1749 }
1750 if(VerifyLoopOptimizations) verify();
1751 if(TraceLoopOpts && C->has_loops()) {
1752 _ltree_root->dump();
1753 }
1754 #endif
|
189 iftrue_op != Op_IfFalse)
190 // I have a weird back-control. Probably the loop-exit test is in
191 // the middle of the loop and I am looking at some trailing control-flow
192 // merge point. To fix this I would have to partially peel the loop.
193 return false; // Obscure back-control
194
195 // Get boolean guarding loop-back test
196 Node *iff = iftrue->in(0);
197 if (get_loop(iff) != loop || !iff->in(1)->is_Bool())
198 return false;
199 BoolNode *test = iff->in(1)->as_Bool();
200 BoolTest::mask bt = test->_test._test;
201 float cl_prob = iff->as_If()->_prob;
202 if (iftrue_op == Op_IfFalse) {
203 bt = BoolTest(bt).negate();
204 cl_prob = 1.0 - cl_prob;
205 }
206 // Get backedge compare
207 Node *cmp = test->in(1);
208 int cmp_op = cmp->Opcode();
209 if (cmp_op != Op_CmpI)
210 return false; // Avoid pointer & float compares
211
212 // Find the trip-counter increment & limit. Limit must be loop invariant.
213 Node *incr = cmp->in(1);
214 Node *limit = cmp->in(2);
215
216 // ---------
217 // need 'loop()' test to tell if limit is loop invariant
218 // ---------
219
220 if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?
221 Node *tmp = incr; // Then reverse order into the CmpI
222 incr = limit;
223 limit = tmp;
224 bt = BoolTest(bt).commute(); // And commute the exit test
225 }
226 if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant
227 return false;
228 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
229 return false;
242 Node* trunc1 = NULL;
243 Node* trunc2 = NULL;
244 const TypeInt* iv_trunc_t = NULL;
245 if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {
246 return false; // Funny increment opcode
247 }
248 assert(incr->Opcode() == Op_AddI, "wrong increment code");
249
250 // Get merge point
251 Node *xphi = incr->in(1);
252 Node *stride = incr->in(2);
253 if (!stride->is_Con()) { // Oops, swap these
254 if (!xphi->is_Con()) // Is the other guy a constant?
255 return false; // Nope, unknown stride, bail out
256 Node *tmp = xphi; // 'incr' is commutative, so ok to swap
257 xphi = stride;
258 stride = tmp;
259 }
260 // Stride must be constant
261 int stride_con = stride->get_int();
262 if (stride_con == 0)
263 return false; // missed some peephole opt
264
265 if (!xphi->is_Phi())
266 return false; // Too much math on the trip counter
267 if (phi_incr != NULL && phi_incr != xphi)
268 return false;
269 PhiNode *phi = xphi->as_Phi();
270
271 // Phi must be of loop header; backedge must wrap to increment
272 if (phi->region() != x)
273 return false;
274 if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr ||
275 trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) {
276 return false;
277 }
278 Node *init_trip = phi->in(LoopNode::EntryControl);
279
280 // If iv trunc type is smaller than int, check for possible wrap.
281 if (!TypeInt::INT->higher_equal(iv_trunc_t)) {
282 assert(trunc1 != NULL, "must have found some truncation");
283
303 } else if (stride_con < 0) {
304 if (iv_trunc_t->_lo - phi_ft->_lo > stride_con ||
305 iv_trunc_t->_hi < phi_ft->_hi) {
306 return false; // truncation may occur
307 }
308 }
309 // No possibility of wrap so truncation can be discarded
310 // Promote iv type to Int
311 } else {
312 assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int");
313 }
314
315 // If the condition is inverted and we will be rolling
316 // through MININT to MAXINT, then bail out.
317 if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!
318 // Odd stride
319 bt == BoolTest::ne && stride_con != 1 && stride_con != -1 ||
320 // Count down loop rolls through MAXINT
321 (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 ||
322 // Count up loop rolls through MININT
323 (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0) {
324 return false; // Bail out
325 }
326
327 const TypeInt* init_t = gvn->type(init_trip)->is_int();
328 const TypeInt* limit_t = gvn->type(limit)->is_int();
329
330 if (stride_con > 0) {
331 long init_p = (long)init_t->_lo + stride_con;
332 if (init_p > (long)max_jint || init_p > (long)limit_t->_hi)
333 return false; // cyclic loop or this loop trips only once
334 } else {
335 long init_p = (long)init_t->_hi + stride_con;
336 if (init_p < (long)min_jint || init_p < (long)limit_t->_lo)
337 return false; // cyclic loop or this loop trips only once
338 }
339
340 // =================================================
341 // ---- SUCCESS! Found A Trip-Counted Loop! -----
342 //
343 assert(x->Opcode() == Op_Loop, "regular loops only");
344 C->print_method("Before CountedLoop", 3);
345
346 Node *hook = new (C, 6) Node(6);
347
348 if (LoopLimitCheck) {
349
350 // ===================================================
351 // Generate loop limit check to avoid integer overflow
352 // in cases like next (cyclic loops):
353 //
354 // for (i=0; i <= max_jint; i++) {}
355 // for (i=0; i < max_jint; i+=2) {}
356 //
357 //
358 // Limit check predicate depends on the loop test:
359 //
360 // for(;i != limit; i++) --> limit <= (max_jint)
361 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
362 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
363 //
364
365 // Check if limit is excluded to do more precise int overflow check.
366 bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge);
367 int stride_m = stride_con - (incl_limit ? 0 : (stride_con > 0 ? 1 : -1));
368
369 // If compare points directly to the phi we need to adjust
370 // the compare so that it points to the incr. Limit have
371 // to be adjusted to keep trip count the same and the
372 // adjusted limit should be checked for int overflow.
373 if (phi_incr != NULL) {
374 stride_m += stride_con;
375 }
376
377 if (limit->is_Con()) {
378 int limit_con = limit->get_int();
379 if ((stride_con > 0 && limit_con > (max_jint - stride_m)) ||
380 (stride_con < 0 && limit_con < (min_jint - stride_m))) {
381 // Bailout: it could be integer overflow.
382 return false;
383 }
384 } else if ((stride_con > 0 && limit_t->_hi <= (max_jint - stride_m)) ||
385 (stride_con < 0 && limit_t->_lo >= (min_jint - stride_m))) {
386 // Limit's type may satisfy the condition, for example,
387 // when it is an array length.
388 } else {
389 // Generate loop's limit check.
390 // Loop limit check predicate should be near the loop.
391 ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);
392 if (!limit_check_proj) {
393 // The limit check predicate is not generated if this method trapped here before.
394 #ifdef ASSERT
395 if (TraceLoopLimitCheck) {
396 tty->print("missing loop limit check:");
397 loop->dump_head();
398 x->dump(1);
399 }
400 #endif
401 return false;
402 }
403
404 IfNode* check_iff = limit_check_proj->in(0)->as_If();
405 Node* cmp_limit;
406 Node* bol;
407
408 if (stride_con > 0) {
409 cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(max_jint - stride_m));
410 bol = new (C, 2) BoolNode(cmp_limit, BoolTest::le);
411 } else {
412 cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(min_jint - stride_m));
413 bol = new (C, 2) BoolNode(cmp_limit, BoolTest::ge);
414 }
415 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
416 bol = _igvn.register_new_node_with_optimizer(bol);
417 set_subtree_ctrl(bol);
418
419 // Replace condition in original predicate but preserve Opaque node
420 // so that previous predicates could be found.
421 assert(check_iff->in(1)->Opcode() == Op_Conv2B &&
422 check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");
423 Node* opq = check_iff->in(1)->in(1);
424 _igvn.hash_delete(opq);
425 opq->set_req(1, bol);
426 // Update ctrl.
427 set_ctrl(opq, check_iff->in(0));
428 set_ctrl(check_iff->in(1), check_iff->in(0));
429
430 #ifndef PRODUCT
431 // report that the loop predication has been actually performed
432 // for this loop
433 if (TraceLoopLimitCheck) {
434 tty->print_cr("Counted Loop Limit Check generated:");
435 debug_only( bol->dump(2); )
436 }
437 #endif
438 }
439
440 if (phi_incr != NULL) {
441 // If compare points directly to the phi we need to adjust
442 // the compare so that it points to the incr. Limit have
443 // to be adjusted to keep trip count the same and we
444 // should avoid int overflow.
445 //
446 // i = init; do {} while(i++ < limit);
447 // is converted to
448 // i = init; do {} while(++i < limit+1);
449 //
450 limit = gvn->transform(new (C, 3) AddINode(limit, stride));
451 }
452
453 // Now we need to canonicalize loop condition.
454 if (bt == BoolTest::ne) {
455 assert(stride_con == 1 || stride_con == -1, "simple increment only");
456 bt = (stride_con > 0) ? BoolTest::lt : BoolTest::gt;
457 }
458
459 if (incl_limit) {
460 // The limit check guaranties that 'limit <= (max_jint - stride)' so
461 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
462 //
463 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
464 limit = gvn->transform(new (C, 3) AddINode(limit, one));
465 if (bt == BoolTest::le)
466 bt = BoolTest::lt;
467 else if (bt == BoolTest::ge)
468 bt = BoolTest::gt;
469 else
470 ShouldNotReachHere();
471 }
472 set_subtree_ctrl( limit );
473
474 } else { // LoopLimitCheck
475
476 // If compare points to incr, we are ok. Otherwise the compare
477 // can directly point to the phi; in this case adjust the compare so that
478 // it points to the incr by adjusting the limit.
479 if (cmp->in(1) == phi || cmp->in(2) == phi)
480 limit = gvn->transform(new (C, 3) AddINode(limit,stride));
481
482 // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.
483 // Final value for iterator should be: trip_count * stride + init_trip.
484 Node *one_p = gvn->intcon( 1);
485 Node *one_m = gvn->intcon(-1);
486
487 Node *trip_count = NULL;
488 switch( bt ) {
489 case BoolTest::eq:
490 ShouldNotReachHere();
491 case BoolTest::ne: // Ahh, the case we desire
492 if (stride_con == 1)
493 trip_count = gvn->transform(new (C, 3) SubINode(limit,init_trip));
494 else if (stride_con == -1)
495 trip_count = gvn->transform(new (C, 3) SubINode(init_trip,limit));
496 else
497 ShouldNotReachHere();
498 set_subtree_ctrl(trip_count);
499 //_loop.map(trip_count->_idx,loop(limit));
500 break;
501 case BoolTest::le: // Maybe convert to '<' case
502 limit = gvn->transform(new (C, 3) AddINode(limit,one_p));
503 set_subtree_ctrl( limit );
504 hook->init_req(4, limit);
505
506 bt = BoolTest::lt;
507 // Make the new limit be in the same loop nest as the old limit
549 hook->init_req(1, bias);
550
551 Node *bias1 = gvn->transform(new (C, 3) AddINode(bias,one_p));
552 set_subtree_ctrl( bias1 );
553 hook->init_req(2, bias1);
554
555 trip_count = gvn->transform(new (C, 3) DivINode(0,bias1,stride));
556 set_subtree_ctrl( trip_count );
557 hook->init_req(3, trip_count);
558 break;
559 }
560 } // switch( bt )
561
562 Node *span = gvn->transform(new (C, 3) MulINode(trip_count,stride));
563 set_subtree_ctrl( span );
564 hook->init_req(5, span);
565
566 limit = gvn->transform(new (C, 3) AddINode(span,init_trip));
567 set_subtree_ctrl( limit );
568
569 } // LoopLimitCheck
570
571 // Check for SafePoint on backedge and remove
572 Node *sfpt = x->in(LoopNode::LoopBackControl);
573 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
574 lazy_replace( sfpt, iftrue );
575 loop->_tail = iftrue;
576 }
577
578 // Build a canonical trip test.
579 // Clone code, as old values may be in use.
580 Node* nphi = PhiNode::make(x, init_trip, TypeInt::INT);
581 nphi = _igvn.register_new_node_with_optimizer(nphi);
582 set_ctrl(nphi, get_ctrl(phi));
583
584 incr = incr->clone();
585 incr->set_req(1,nphi);
586 incr->set_req(2,stride);
587 incr = _igvn.register_new_node_with_optimizer(incr);
588 set_early_ctrl( incr );
589
590 nphi->set_req(LoopNode::LoopBackControl, incr);
641 assert(iff->outcnt() == 0, "should be dead now");
642 lazy_replace( iff, le ); // fix 'get_ctrl'
643
644 // Now setup a new CountedLoopNode to replace the existing LoopNode
645 CountedLoopNode *l = new (C, 3) CountedLoopNode(init_control, back_control);
646 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve
647 // The following assert is approximately true, and defines the intention
648 // of can_be_counted_loop. It fails, however, because phase->type
649 // is not yet initialized for this loop and its parts.
650 //assert(l->can_be_counted_loop(this), "sanity");
651 _igvn.register_new_node_with_optimizer(l);
652 set_loop(l, loop);
653 loop->_head = l;
654 // Fix all data nodes placed at the old loop head.
655 // Uses the lazy-update mechanism of 'get_ctrl'.
656 lazy_replace( x, l );
657 set_idom(l, init_control, dom_depth(x));
658
659 // Check for immediately preceding SafePoint and remove
660 Node *sfpt2 = le->in(0);
661 if (sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2))
662 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
663
664 // Free up intermediate goo
665 _igvn.remove_dead_node(hook);
666
667 #ifdef ASSERT
668 assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
669 assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
670 #endif
671 #ifndef PRODUCT
672 if (TraceLoopOpts) {
673 tty->print("Counted ");
674 loop->dump_head();
675 }
676 #endif
677
678 C->print_method("After CountedLoop", 3);
679
680 return true;
681 }
682
683 //----------------------exact_limit-------------------------------------------
684 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
685 assert(loop->_head->is_CountedLoop(), "");
686 CountedLoopNode *cl = loop->_head->as_CountedLoop();
687
688 if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 ||
689 cl->limit()->Opcode() == Op_LoopLimit) {
690 // Old code has exact limit (it could be incorrect in case of int overflow).
691 // Loop limit is exact with stride == 1. And loop may already have exact limit.
692 return cl->limit();
693 }
694 Node *limit = NULL;
695 #ifdef ASSERT
696 BoolTest::mask bt = cl->loopexit()->test_trip();
697 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
698 #endif
699 if (cl->has_exact_trip_count()) {
700 // Simple case: loop has constant boundaries.
701 // Use longs to avoid integer overflow.
702 int stride_con = cl->stride_con();
703 long init_con = cl->init_trip()->get_int();
704 long limit_con = cl->limit()->get_int();
705 julong trip_cnt = cl->trip_count();
706 long final_con = init_con + trip_cnt*stride_con;
707 final_con -= stride_con;
708 int final_int = (int)final_con;
709 // The final value should be in integer range since the loop
710 // is counted and the limit was checked for overflow.
711 assert(final_con == (long)final_int, "final value should be integer");
712 limit = _igvn.intcon(final_int);
713 } else {
714 // Create new LoopLimit node to get exact limit (final iv value).
715 limit = new (C, 4) LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride());
716 register_new_node(limit, cl->in(LoopNode::EntryControl));
717 }
718 assert(limit != NULL, "sanity");
719 return limit;
720 }
721
722 //------------------------------Ideal------------------------------------------
723 // Return a node which is more "ideal" than the current node.
724 // Attempt to convert into a counted-loop.
725 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
726 if (!can_be_counted_loop(phase)) {
727 phase->C->set_major_progress();
728 }
729 return RegionNode::Ideal(phase, can_reshape);
730 }
731
732
733 //=============================================================================
734 //------------------------------Ideal------------------------------------------
735 // Return a node which is more "ideal" than the current node.
736 // Attempt to convert into a counted-loop.
737 Node *CountedLoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
738 return RegionNode::Ideal(phase, can_reshape);
739 }
740
741 //------------------------------dump_spec--------------------------------------
742 // Dump special per-node info
743 #ifndef PRODUCT
744 void CountedLoopNode::dump_spec(outputStream *st) const {
745 LoopNode::dump_spec(st);
746 if (stride_is_con()) {
747 st->print("stride: %d ",stride_con());
748 }
749 if (is_pre_loop ()) st->print("pre of N%d" , _main_idx);
750 if (is_main_loop()) st->print("main of N%d", _idx);
751 if (is_post_loop()) st->print("post of N%d", _main_idx);
752 }
753 #endif
754
755 //=============================================================================
756 int CountedLoopEndNode::stride_con() const {
757 return stride()->bottom_type()->is_int()->get_con();
758 }
759
760 //=============================================================================
761 //------------------------------Value-----------------------------------------
762 const Type *LoopLimitNode::Value( PhaseTransform *phase ) const {
763 const Type* init_t = phase->type(in(Init));
764 const Type* limit_t = phase->type(in(Limit));
765 const Type* stride_t = phase->type(in(Stride));
766 // Either input is TOP ==> the result is TOP
767 if (init_t == Type::TOP) return Type::TOP;
768 if (limit_t == Type::TOP) return Type::TOP;
769 if (stride_t == Type::TOP) return Type::TOP;
770
771 int stride_con = stride_t->is_int()->get_con();
772 if (stride_con == 1)
773 return NULL; // Identity
774
775 if (init_t->is_int()->is_con() && limit_t->is_int()->is_con()) {
776 // Use longs to avoid integer overflow.
777 long init_con = init_t->is_int()->get_con();
778 long limit_con = limit_t->is_int()->get_con();
779 int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
780 long trip_count = (limit_con - init_con + stride_m)/stride_con;
781 long final_con = init_con + stride_con*trip_count;
782 int final_int = (int)final_con;
783 // The final value should be in integer range since the loop
784 // is counted and the limit was checked for overflow.
785 assert(final_con == (long)final_int, "final value should be integer");
786 return TypeInt::make(final_int);
787 }
788
789 return bottom_type(); // TypeInt::INT
790 }
791
792 //------------------------------Ideal------------------------------------------
793 // Return a node which is more "ideal" than the current node.
794 Node *LoopLimitNode::Ideal(PhaseGVN *phase, bool can_reshape) {
795 if (phase->type(in(Init)) == Type::TOP ||
796 phase->type(in(Limit)) == Type::TOP ||
797 phase->type(in(Stride)) == Type::TOP)
798 return NULL; // Dead
799
800 int stride_con = phase->type(in(Stride))->is_int()->get_con();
801 if (stride_con == 1)
802 return NULL; // Identity
803
804 if (in(Init)->is_Con() && in(Limit)->is_Con())
805 return NULL; // Value
806
807 // Delay following optimizations until all loop optimizations
808 // done to keep Ideal graph simple.
809 if (!can_reshape || phase->C->major_progress())
810 return NULL;
811
812 const TypeInt* init_t = phase->type(in(Init) )->is_int();
813 const TypeInt* limit_t = phase->type(in(Limit))->is_int();
814 int stride_p;
815 long lim, ini;
816 julong max;
817 if (stride_con > 0) {
818 stride_p = stride_con;
819 lim = limit_t->_hi;
820 ini = init_t->_lo;
821 max = (julong)max_jint;
822 } else {
823 stride_p = -stride_con;
824 lim = init_t->_hi;
825 ini = limit_t->_lo;
826 max = (julong)min_jint;
827 }
828 julong range = lim - ini + stride_p;
829 if (range <= max) {
830 // Convert to integer expression if it is not overflow.
831 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
832 Node *range = phase->transform(new (phase->C, 3) SubINode(in(Limit), in(Init)));
833 Node *bias = phase->transform(new (phase->C, 3) AddINode(range, stride_m));
834 Node *trip = phase->transform(new (phase->C, 3) DivINode(0, bias, in(Stride)));
835 Node *span = phase->transform(new (phase->C, 3) MulINode(trip, in(Stride)));
836 return new (phase->C, 3) AddINode(span, in(Init)); // exact limit
837 }
838
839 if (is_power_of_2(stride_p) || // divisor is 2^n
840 !Matcher::has_match_rule(Op_LoopLimit)) { // or no specialized Mach node?
841 // Convert to long expression to avoid integer overflow
842 // and let igvn optimizer convert this division.
843 //
844 Node* init = phase->transform( new (phase->C, 2) ConvI2LNode(in(Init)));
845 Node* limit = phase->transform( new (phase->C, 2) ConvI2LNode(in(Limit)));
846 Node* stride = phase->longcon(stride_con);
847 Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1));
848
849 Node *range = phase->transform(new (phase->C, 3) SubLNode(limit, init));
850 Node *bias = phase->transform(new (phase->C, 3) AddLNode(range, stride_m));
851 Node *trip = phase->transform(new (phase->C, 3) DivLNode(0, bias, stride));
852 Node *span = phase->transform(new (phase->C, 3) MulLNode(trip, stride));
853 Node *exact = phase->transform(new (phase->C, 3) AddLNode(span, init));
854 return new (phase->C, 2) ConvL2INode(exact); // exact limit
855 }
856
857 return NULL; // No progress
858 }
859
860 //------------------------------Identity---------------------------------------
861 // If stride == 1 return limit node.
862 Node *LoopLimitNode::Identity( PhaseTransform *phase ) {
863 int stride_con = phase->type(in(Stride))->is_int()->get_con();
864 if (stride_con == 1 || stride_con == -1)
865 return in(Limit);
866 return this;
867 }
868
869 //=============================================================================
870 //----------------------match_incr_with_optional_truncation--------------------
871 // Match increment with optional truncation:
872 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
873 // Return NULL for failure. Success returns the increment node.
874 Node* CountedLoopNode::match_incr_with_optional_truncation(
875 Node* expr, Node** trunc1, Node** trunc2, const TypeInt** trunc_type) {
876 // Quick cutouts:
877 if (expr == NULL || expr->req() != 3) return false;
878
879 Node *t1 = NULL;
880 Node *t2 = NULL;
881 const TypeInt* trunc_t = TypeInt::INT;
882 Node* n1 = expr;
883 int n1op = n1->Opcode();
884
885 // Try to strip (n1 & M) or (n1 << N >> N) from n1.
886 if (n1op == Op_AndI &&
887 n1->in(2)->is_Con() &&
888 n1->in(2)->bottom_type()->is_int()->get_con() == 0x7fff) {
889 // %%% This check should match any mask of 2**K-1.
1131 igvn.register_new_node_with_optimizer(landing_pad, _head);
1132 // Insert landing pad into the header
1133 _head->add_req(landing_pad);
1134 }
1135
1136 //------------------------------split_outer_loop-------------------------------
1137 // Split out the outermost loop from this shared header.
1138 void IdealLoopTree::split_outer_loop( PhaseIdealLoop *phase ) {
1139 PhaseIterGVN &igvn = phase->_igvn;
1140
1141 // Find index of outermost loop; it should also be my tail.
1142 uint outer_idx = 1;
1143 while( _head->in(outer_idx) != _tail ) outer_idx++;
1144
1145 // Make a LoopNode for the outermost loop.
1146 Node *ctl = _head->in(LoopNode::EntryControl);
1147 Node *outer = new (phase->C, 3) LoopNode( ctl, _head->in(outer_idx) );
1148 outer = igvn.register_new_node_with_optimizer(outer, _head);
1149 phase->set_created_loop_node();
1150
1151 Node* pred = phase->clone_loop_predicates(ctl, outer, true);
1152 // Outermost loop falls into '_head' loop
1153 _head->set_req(LoopNode::EntryControl, pred);
1154 _head->del_req(outer_idx);
1155 // Split all the Phis up between '_head' loop and 'outer' loop.
1156 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1157 Node *out = _head->fast_out(j);
1158 if( out->is_Phi() ) {
1159 PhiNode *old_phi = out->as_Phi();
1160 assert( old_phi->region() == _head, "" );
1161 Node *phi = PhiNode::make_blank(outer, old_phi);
1162 phi->init_req(LoopNode::EntryControl, old_phi->in(LoopNode::EntryControl));
1163 phi->init_req(LoopNode::LoopBackControl, old_phi->in(outer_idx));
1164 phi = igvn.register_new_node_with_optimizer(phi, old_phi);
1165 // Make old Phi point to new Phi on the fall-in path
1166 igvn.hash_delete(old_phi);
1167 old_phi->set_req(LoopNode::EntryControl, phi);
1168 old_phi->del_req(outer_idx);
1169 igvn._worklist.push(old_phi);
1170 }
1171 }
1701 for (; n != _head; n = phase->idom(n)) {
1702 if (n->Opcode() == Op_SafePoint && phase->get_loop(n) == this &&
1703 phase->is_deleteable_safept(n))
1704 phase->lazy_replace(n,n->in(TypeFunc::Control));
1705 }
1706 }
1707
1708 // Recursively
1709 if (_child) _child->counted_loop( phase );
1710 if (_next) _next ->counted_loop( phase );
1711 }
1712
1713 #ifndef PRODUCT
1714 //------------------------------dump_head--------------------------------------
1715 // Dump 1 liner for loop header info
1716 void IdealLoopTree::dump_head( ) const {
1717 for (uint i=0; i<_nest; i++)
1718 tty->print(" ");
1719 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
1720 if (_irreducible) tty->print(" IRREDUCIBLE");
1721 Node* entry = _head->in(LoopNode::EntryControl);
1722 if (LoopLimitCheck) {
1723 Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1724 if (predicate != NULL ) {
1725 tty->print(" limit_check");
1726 entry = entry->in(0)->in(0);
1727 }
1728 }
1729 if (UseLoopPredicate) {
1730 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1731 if (entry != NULL) {
1732 tty->print(" predicated");
1733 }
1734 }
1735 if (_head->is_CountedLoop()) {
1736 CountedLoopNode *cl = _head->as_CountedLoop();
1737 tty->print(" counted");
1738
1739 Node* init_n = cl->init_trip();
1740 if (init_n != NULL && init_n->is_Con())
1741 tty->print(" [%d,", cl->init_trip()->get_int());
1742 else
1743 tty->print(" [int,");
1744 Node* limit_n = cl->limit();
1745 if (limit_n != NULL && limit_n->is_Con())
1746 tty->print("%d),", cl->limit()->get_int());
1747 else
1748 tty->print("int),");
1749 int stride_con = cl->stride_con();
1750 if (stride_con > 0) tty->print("+");
1796 log->tail("loop");
1797 if( loop->_next ) log_loop_tree(root, loop->_next, log);
1798 }
1799 }
1800
1801 //---------------------collect_potentially_useful_predicates-----------------------
1802 // Helper function to collect potentially useful predicates to prevent them from
1803 // being eliminated by PhaseIdealLoop::eliminate_useless_predicates
1804 void PhaseIdealLoop::collect_potentially_useful_predicates(
1805 IdealLoopTree * loop, Unique_Node_List &useful_predicates) {
1806 if (loop->_child) { // child
1807 collect_potentially_useful_predicates(loop->_child, useful_predicates);
1808 }
1809
1810 // self (only loops that we can apply loop predication may use their predicates)
1811 if (loop->_head->is_Loop() &&
1812 !loop->_irreducible &&
1813 !loop->tail()->is_top()) {
1814 LoopNode* lpn = loop->_head->as_Loop();
1815 Node* entry = lpn->in(LoopNode::EntryControl);
1816 Node* predicate_proj = find_predicate(entry); // loop_limit_check first
1817 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication
1818 assert(entry->in(0)->in(1)->in(1)->Opcode() == Op_Opaque1, "must be");
1819 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1820 entry = entry->in(0)->in(0);
1821 }
1822 predicate_proj = find_predicate(entry); // Predicate
1823 if (predicate_proj != NULL ) {
1824 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1825 }
1826 }
1827
1828 if (loop->_next) { // sibling
1829 collect_potentially_useful_predicates(loop->_next, useful_predicates);
1830 }
1831 }
1832
1833 //------------------------eliminate_useless_predicates-----------------------------
1834 // Eliminate all inserted predicates if they could not be used by loop predication.
1835 // Note: it will also eliminates loop limits check predicate since it also uses
1836 // Opaque1 node (see Parse::add_predicate()).
1837 void PhaseIdealLoop::eliminate_useless_predicates() {
1838 if (C->predicate_count() == 0)
1839 return; // no predicate left
1840
1841 Unique_Node_List useful_predicates; // to store useful predicates
1842 if (C->has_loops()) {
1843 collect_potentially_useful_predicates(_ltree_root->_child, useful_predicates);
1844 }
1845
1846 for (int i = C->predicate_count(); i > 0; i--) {
1847 Node * n = C->predicate_opaque1_node(i-1);
1848 assert(n->Opcode() == Op_Opaque1, "must be");
1849 if (!useful_predicates.member(n)) { // not in the useful list
1850 _igvn.replace_node(n, n->in(1));
1851 }
1852 }
1853 }
1854
1855 //=============================================================================
1856 //----------------------------build_and_optimize-------------------------------
2006 visited.Clear();
2007 init_dom_lca_tags();
2008 // Need C->root() on worklist when processing outs
2009 worklist.push( C->root() );
2010 NOT_PRODUCT( C->verify_graph_edges(); )
2011 worklist.push( C->top() );
2012 build_loop_late( visited, worklist, nstack );
2013
2014 if (_verify_only) {
2015 // restore major progress flag
2016 for (int i = 0; i < old_progress; i++)
2017 C->set_major_progress();
2018 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2019 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2020 return;
2021 }
2022
2023 // Some parser-inserted loop predicates could never be used by loop
2024 // predication or they were moved away from loop during some optimizations.
2025 // For example, peeling. Eliminate them before next loop optimizations.
2026 if (UseLoopPredicate || LoopLimitCheck) {
2027 eliminate_useless_predicates();
2028 }
2029
2030 // clear out the dead code
2031 while(_deadlist.size()) {
2032 _igvn.remove_globally_dead_node(_deadlist.pop());
2033 }
2034
2035 #ifndef PRODUCT
2036 C->verify_graph_edges();
2037 if (_verify_me) { // Nested verify pass?
2038 // Check to see if the verify mode is broken
2039 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2040 return;
2041 }
2042 if(VerifyLoopOptimizations) verify();
2043 if(TraceLoopOpts && C->has_loops()) {
2044 _ltree_root->dump();
2045 }
2046 #endif
|