307 }
308 outer_ilt->_next = loop->_next;
309 outer_ilt->_parent = parent;
310 outer_ilt->_child = loop;
311 outer_ilt->_nest = loop->_nest;
312 loop->_parent = outer_ilt;
313 loop->_next = NULL;
314 loop->_nest++;
315
316 set_loop(iffalse, outer_ilt);
317 register_control(outer_le, outer_ilt, iffalse);
318 register_control(outer_ift, outer_ilt, outer_le);
319 set_idom(outer_iff, outer_le, dom_depth(outer_le));
320 _igvn.register_new_node_with_optimizer(outer_l);
321 set_loop(outer_l, outer_ilt);
322 set_idom(outer_l, init_control, dom_depth(init_control)+1);
323
324 return outer_ilt;
325 }
326
327 //------------------------------is_counted_loop--------------------------------
328 bool PhaseIdealLoop::is_counted_loop(Node* x, IdealLoopTree*& loop) {
329 PhaseGVN *gvn = &_igvn;
330
331 // Counted loop head must be a good RegionNode with only 3 not NULL
332 // control input edges: Self, Entry, LoopBack.
333 if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {
334 return false;
335 }
336 Node *init_control = x->in(LoopNode::EntryControl);
337 Node *back_control = x->in(LoopNode::LoopBackControl);
338 if (init_control == NULL || back_control == NULL) // Partially dead
339 return false;
340 // Must also check for TOP when looking for a dead loop
341 if (init_control->is_top() || back_control->is_top())
342 return false;
343
344 // Allow funny placement of Safepoint
345 if (back_control->Opcode() == Op_SafePoint) {
346 if (LoopStripMiningIter != 0) {
523 (bt == BoolTest::ne && stride_con != 1 && stride_con != -1) ||
524 // Count down loop rolls through MAXINT
525 ((bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0) ||
526 // Count up loop rolls through MININT
527 ((bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0)) {
528 return false; // Bail out
529 }
530
531 const TypeInt* init_t = gvn->type(init_trip)->is_int();
532
533 if (stride_con > 0) {
534 jlong init_p = (jlong)init_t->_lo + stride_con;
535 if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
536 return false; // cyclic loop or this loop trips only once
537 } else {
538 jlong init_p = (jlong)init_t->_hi + stride_con;
539 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
540 return false; // cyclic loop or this loop trips only once
541 }
542
543 if (phi_incr != NULL) {
544 // check if there is a possiblity of IV overflowing after the first increment
545 if (stride_con > 0) {
546 if (init_t->_hi > max_jint - stride_con) {
547 return false;
548 }
549 } else {
550 if (init_t->_lo < min_jint - stride_con) {
551 return false;
552 }
553 }
554 }
555
556 // =================================================
557 // ---- SUCCESS! Found A Trip-Counted Loop! -----
558 //
559 assert(x->Opcode() == Op_Loop, "regular loops only");
560 C->print_method(PHASE_BEFORE_CLOOPS, 3);
561
562 Node *hook = new Node(6);
563
614 #endif
615 return false;
616 }
617
618 IfNode* check_iff = limit_check_proj->in(0)->as_If();
619
620 if (!is_dominator(get_ctrl(limit), check_iff->in(0))) {
621 return false;
622 }
623
624 Node* cmp_limit;
625 Node* bol;
626
627 if (stride_con > 0) {
628 cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
629 bol = new BoolNode(cmp_limit, BoolTest::le);
630 } else {
631 cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
632 bol = new BoolNode(cmp_limit, BoolTest::ge);
633 }
634 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
635 bol = _igvn.register_new_node_with_optimizer(bol);
636 set_subtree_ctrl(bol);
637
638 // Replace condition in original predicate but preserve Opaque node
639 // so that previous predicates could be found.
640 assert(check_iff->in(1)->Opcode() == Op_Conv2B &&
641 check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");
642 Node* opq = check_iff->in(1)->in(1);
643 _igvn.replace_input_of(opq, 1, bol);
644 // Update ctrl.
645 set_ctrl(opq, check_iff->in(0));
646 set_ctrl(check_iff->in(1), check_iff->in(0));
647
648 #ifndef PRODUCT
649 // report that the loop predication has been actually performed
650 // for this loop
651 if (TraceLoopLimitCheck) {
652 tty->print_cr("Counted Loop Limit Check generated:");
653 debug_only( bol->dump(2); )
654 }
655 #endif
656 }
657
658 if (phi_incr != NULL) {
659 // If compare points directly to the phi we need to adjust
660 // the compare so that it points to the incr. Limit have
661 // to be adjusted to keep trip count the same and we
662 // should avoid int overflow.
663 //
664 // i = init; do {} while(i++ < limit);
665 // is converted to
666 // i = init; do {} while(++i < limit+1);
667 //
668 limit = gvn->transform(new AddINode(limit, stride));
669 }
670
671 // Now we need to canonicalize loop condition.
672 if (bt == BoolTest::ne) {
673 assert(stride_con == 1 || stride_con == -1, "simple increment only");
674 // 'ne' can be replaced with 'lt' only when init < limit.
675 if (stride_con > 0 && init_t->_hi < limit_t->_lo)
676 bt = BoolTest::lt;
677 // 'ne' can be replaced with 'gt' only when init > limit.
678 if (stride_con < 0 && init_t->_lo > limit_t->_hi)
679 bt = BoolTest::gt;
680 }
681
682 if (incl_limit) {
683 // The limit check guaranties that 'limit <= (max_jint - stride)' so
684 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
685 //
686 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
687 limit = gvn->transform(new AddINode(limit, one));
688 if (bt == BoolTest::le)
689 bt = BoolTest::lt;
690 else if (bt == BoolTest::ge)
691 bt = BoolTest::gt;
692 else
693 ShouldNotReachHere();
694 }
695 set_subtree_ctrl( limit );
696
697 if (LoopStripMiningIter == 0) {
698 // Check for SafePoint on backedge and remove
699 Node *sfpt = x->in(LoopNode::LoopBackControl);
700 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
701 lazy_replace( sfpt, iftrue );
2387
2388 // Recursively
2389 assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2390 assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2391 if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2392 if (loop->_next) loop->_next ->counted_loop(phase);
2393 }
2394
2395 #ifndef PRODUCT
2396 //------------------------------dump_head--------------------------------------
2397 // Dump 1 liner for loop header info
2398 void IdealLoopTree::dump_head( ) const {
2399 for (uint i=0; i<_nest; i++)
2400 tty->print(" ");
2401 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2402 if (_irreducible) tty->print(" IRREDUCIBLE");
2403 Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2404 Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2405 if (predicate != NULL ) {
2406 tty->print(" limit_check");
2407 entry = entry->in(0)->in(0);
2408 }
2409 if (UseLoopPredicate) {
2410 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2411 if (entry != NULL) {
2412 tty->print(" predicated");
2413 entry = PhaseIdealLoop::skip_loop_predicates(entry);
2414 }
2415 }
2416 if (UseProfiledLoopPredicate) {
2417 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2418 if (entry != NULL) {
2419 tty->print(" profile_predicated");
2420 }
2421 }
2422 if (_head->is_CountedLoop()) {
2423 CountedLoopNode *cl = _head->as_CountedLoop();
2424 tty->print(" counted");
2425
2426 Node* init_n = cl->init_trip();
2427 if (init_n != NULL && init_n->is_Con())
|
307 }
308 outer_ilt->_next = loop->_next;
309 outer_ilt->_parent = parent;
310 outer_ilt->_child = loop;
311 outer_ilt->_nest = loop->_nest;
312 loop->_parent = outer_ilt;
313 loop->_next = NULL;
314 loop->_nest++;
315
316 set_loop(iffalse, outer_ilt);
317 register_control(outer_le, outer_ilt, iffalse);
318 register_control(outer_ift, outer_ilt, outer_le);
319 set_idom(outer_iff, outer_le, dom_depth(outer_le));
320 _igvn.register_new_node_with_optimizer(outer_l);
321 set_loop(outer_l, outer_ilt);
322 set_idom(outer_l, init_control, dom_depth(init_control)+1);
323
324 return outer_ilt;
325 }
326
327 void PhaseIdealLoop::insert_loop_limit_check(Node* init_control, Node* cmp_limit, Node* bol) {
328 Node* new_predicate_proj = create_new_if_for_predicate(init_control->as_Proj(), NULL,
329 Deoptimization::Reason_loop_limit_check,
330 Op_If);
331 Node* iff = new_predicate_proj->in(0);
332 assert(iff->Opcode() == Op_If, "bad graph shape");
333 Node* conv = iff->in(1);
334 assert(conv->Opcode() == Op_Conv2B, "bad graph shape");
335 Node* opaq = conv->in(1);
336 assert(opaq->Opcode() == Op_Opaque1, "bad graph shape");
337 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
338 bol = _igvn.register_new_node_with_optimizer(bol);
339 set_subtree_ctrl(bol);
340 _igvn.replace_input_of(iff, 1, bol);
341
342 #ifndef PRODUCT
343 // report that the loop predication has been actually performed
344 // for this loop
345 if (TraceLoopLimitCheck) {
346 tty->print_cr("Counted Loop Limit Check generated:");
347 debug_only( bol->dump(2); )
348 }
349 #endif
350 }
351
352 //------------------------------is_counted_loop--------------------------------
353 bool PhaseIdealLoop::is_counted_loop(Node* x, IdealLoopTree*& loop) {
354 PhaseGVN *gvn = &_igvn;
355
356 // Counted loop head must be a good RegionNode with only 3 not NULL
357 // control input edges: Self, Entry, LoopBack.
358 if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {
359 return false;
360 }
361 Node *init_control = x->in(LoopNode::EntryControl);
362 Node *back_control = x->in(LoopNode::LoopBackControl);
363 if (init_control == NULL || back_control == NULL) // Partially dead
364 return false;
365 // Must also check for TOP when looking for a dead loop
366 if (init_control->is_top() || back_control->is_top())
367 return false;
368
369 // Allow funny placement of Safepoint
370 if (back_control->Opcode() == Op_SafePoint) {
371 if (LoopStripMiningIter != 0) {
548 (bt == BoolTest::ne && stride_con != 1 && stride_con != -1) ||
549 // Count down loop rolls through MAXINT
550 ((bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0) ||
551 // Count up loop rolls through MININT
552 ((bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0)) {
553 return false; // Bail out
554 }
555
556 const TypeInt* init_t = gvn->type(init_trip)->is_int();
557
558 if (stride_con > 0) {
559 jlong init_p = (jlong)init_t->_lo + stride_con;
560 if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
561 return false; // cyclic loop or this loop trips only once
562 } else {
563 jlong init_p = (jlong)init_t->_hi + stride_con;
564 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
565 return false; // cyclic loop or this loop trips only once
566 }
567
568 if (phi_incr != NULL && bt != BoolTest::ne) {
569 // check if there is a possiblity of IV overflowing after the first increment
570 if (stride_con > 0) {
571 if (init_t->_hi > max_jint - stride_con) {
572 return false;
573 }
574 } else {
575 if (init_t->_lo < min_jint - stride_con) {
576 return false;
577 }
578 }
579 }
580
581 // =================================================
582 // ---- SUCCESS! Found A Trip-Counted Loop! -----
583 //
584 assert(x->Opcode() == Op_Loop, "regular loops only");
585 C->print_method(PHASE_BEFORE_CLOOPS, 3);
586
587 Node *hook = new Node(6);
588
639 #endif
640 return false;
641 }
642
643 IfNode* check_iff = limit_check_proj->in(0)->as_If();
644
645 if (!is_dominator(get_ctrl(limit), check_iff->in(0))) {
646 return false;
647 }
648
649 Node* cmp_limit;
650 Node* bol;
651
652 if (stride_con > 0) {
653 cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
654 bol = new BoolNode(cmp_limit, BoolTest::le);
655 } else {
656 cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
657 bol = new BoolNode(cmp_limit, BoolTest::ge);
658 }
659
660 insert_loop_limit_check(init_control, cmp_limit, bol);
661 }
662
663 // Now we need to canonicalize loop condition.
664 if (bt == BoolTest::ne) {
665 assert(stride_con == 1 || stride_con == -1, "simple increment only");
666 if (stride_con > 0 && init_t->_hi < limit_t->_lo) {
667 // 'ne' can be replaced with 'lt' only when init < limit.
668 bt = BoolTest::lt;
669 } else if (stride_con < 0 && init_t->_lo > limit_t->_hi) {
670 // 'ne' can be replaced with 'gt' only when init > limit.
671 bt = BoolTest::gt;
672 } else {
673 ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);
674 if (!limit_check_proj) {
675 // The limit check predicate is not generated if this method trapped here before.
676 #ifdef ASSERT
677 if (TraceLoopLimitCheck) {
678 tty->print("missing loop limit check:");
679 loop->dump_head();
680 x->dump(1);
681 }
682 #endif
683 return false;
684 }
685 IfNode* check_iff = limit_check_proj->in(0)->as_If();
686
687 if (!is_dominator(get_ctrl(limit), check_iff->in(0)) ||
688 !is_dominator(get_ctrl(init_trip), check_iff->in(0))) {
689 return false;
690 }
691
692 Node* cmp_limit;
693 Node* bol;
694
695 if (stride_con > 0) {
696 cmp_limit = new CmpINode(init_trip, limit);
697 bol = new BoolNode(cmp_limit, BoolTest::lt);
698 } else {
699 cmp_limit = new CmpINode(init_trip, limit);
700 bol = new BoolNode(cmp_limit, BoolTest::gt);
701 }
702
703 insert_loop_limit_check(init_control, cmp_limit, bol);
704
705 if (stride_con > 0) {
706 // 'ne' can be replaced with 'lt' only when init < limit.
707 bt = BoolTest::lt;
708 } else if (stride_con < 0) {
709 // 'ne' can be replaced with 'gt' only when init > limit.
710 bt = BoolTest::gt;
711 }
712 }
713 }
714
715 if (phi_incr != NULL) {
716 // If compare points directly to the phi we need to adjust
717 // the compare so that it points to the incr. Limit have
718 // to be adjusted to keep trip count the same and we
719 // should avoid int overflow.
720 //
721 // i = init; do {} while(i++ < limit);
722 // is converted to
723 // i = init; do {} while(++i < limit+1);
724 //
725 limit = gvn->transform(new AddINode(limit, stride));
726 }
727
728 if (incl_limit) {
729 // The limit check guaranties that 'limit <= (max_jint - stride)' so
730 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
731 //
732 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
733 limit = gvn->transform(new AddINode(limit, one));
734 if (bt == BoolTest::le)
735 bt = BoolTest::lt;
736 else if (bt == BoolTest::ge)
737 bt = BoolTest::gt;
738 else
739 ShouldNotReachHere();
740 }
741 set_subtree_ctrl( limit );
742
743 if (LoopStripMiningIter == 0) {
744 // Check for SafePoint on backedge and remove
745 Node *sfpt = x->in(LoopNode::LoopBackControl);
746 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
747 lazy_replace( sfpt, iftrue );
2433
2434 // Recursively
2435 assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2436 assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2437 if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2438 if (loop->_next) loop->_next ->counted_loop(phase);
2439 }
2440
2441 #ifndef PRODUCT
2442 //------------------------------dump_head--------------------------------------
2443 // Dump 1 liner for loop header info
2444 void IdealLoopTree::dump_head( ) const {
2445 for (uint i=0; i<_nest; i++)
2446 tty->print(" ");
2447 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2448 if (_irreducible) tty->print(" IRREDUCIBLE");
2449 Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2450 Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2451 if (predicate != NULL ) {
2452 tty->print(" limit_check");
2453 entry = PhaseIdealLoop::skip_loop_predicates(entry);
2454 }
2455 if (UseLoopPredicate) {
2456 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2457 if (entry != NULL) {
2458 tty->print(" predicated");
2459 entry = PhaseIdealLoop::skip_loop_predicates(entry);
2460 }
2461 }
2462 if (UseProfiledLoopPredicate) {
2463 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2464 if (entry != NULL) {
2465 tty->print(" profile_predicated");
2466 }
2467 }
2468 if (_head->is_CountedLoop()) {
2469 CountedLoopNode *cl = _head->as_CountedLoop();
2470 tty->print(" counted");
2471
2472 Node* init_n = cl->init_trip();
2473 if (init_n != NULL && init_n->is_Con())
|