446 // check if there is a possiblity of IV overflowing after the first increment
447 if (stride_con > 0) {
448 if (init_t->_hi > max_jint - stride_con) {
449 return false;
450 }
451 } else {
452 if (init_t->_lo < min_jint - stride_con) {
453 return false;
454 }
455 }
456 }
457
458 // =================================================
459 // ---- SUCCESS! Found A Trip-Counted Loop! -----
460 //
461 assert(x->Opcode() == Op_Loop, "regular loops only");
462 C->print_method(PHASE_BEFORE_CLOOPS, 3);
463
464 Node *hook = new Node(6);
465
466 if (LoopLimitCheck) {
467
468 // ===================================================
469 // Generate loop limit check to avoid integer overflow
470 // in cases like next (cyclic loops):
471 //
472 // for (i=0; i <= max_jint; i++) {}
473 // for (i=0; i < max_jint; i+=2) {}
474 //
475 //
476 // Limit check predicate depends on the loop test:
477 //
478 // for(;i != limit; i++) --> limit <= (max_jint)
479 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
480 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
481 //
482
483 // Check if limit is excluded to do more precise int overflow check.
484 bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge);
485 int stride_m = stride_con - (incl_limit ? 0 : (stride_con > 0 ? 1 : -1));
486
487 // If compare points directly to the phi we need to adjust
576 // 'ne' can be replaced with 'gt' only when init > limit.
577 if (stride_con < 0 && init_t->_lo > limit_t->_hi)
578 bt = BoolTest::gt;
579 }
580
581 if (incl_limit) {
582 // The limit check guaranties that 'limit <= (max_jint - stride)' so
583 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
584 //
585 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
586 limit = gvn->transform(new AddINode(limit, one));
587 if (bt == BoolTest::le)
588 bt = BoolTest::lt;
589 else if (bt == BoolTest::ge)
590 bt = BoolTest::gt;
591 else
592 ShouldNotReachHere();
593 }
594 set_subtree_ctrl( limit );
595
596 } else { // LoopLimitCheck
597
598 // If compare points to incr, we are ok. Otherwise the compare
599 // can directly point to the phi; in this case adjust the compare so that
600 // it points to the incr by adjusting the limit.
601 if (cmp->in(1) == phi || cmp->in(2) == phi)
602 limit = gvn->transform(new AddINode(limit,stride));
603
604 // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.
605 // Final value for iterator should be: trip_count * stride + init_trip.
606 Node *one_p = gvn->intcon( 1);
607 Node *one_m = gvn->intcon(-1);
608
609 Node *trip_count = NULL;
610 switch( bt ) {
611 case BoolTest::eq:
612 ShouldNotReachHere();
613 case BoolTest::ne: // Ahh, the case we desire
614 if (stride_con == 1)
615 trip_count = gvn->transform(new SubINode(limit,init_trip));
616 else if (stride_con == -1)
617 trip_count = gvn->transform(new SubINode(init_trip,limit));
618 else
619 ShouldNotReachHere();
620 set_subtree_ctrl(trip_count);
621 //_loop.map(trip_count->_idx,loop(limit));
622 break;
623 case BoolTest::le: // Maybe convert to '<' case
624 limit = gvn->transform(new AddINode(limit,one_p));
625 set_subtree_ctrl( limit );
626 hook->init_req(4, limit);
627
628 bt = BoolTest::lt;
629 // Make the new limit be in the same loop nest as the old limit
630 //_loop.map(limit->_idx,limit_loop);
631 // Fall into next case
632 case BoolTest::lt: { // Maybe convert to '!=' case
633 if (stride_con < 0) // Count down loop rolls through MAXINT
634 ShouldNotReachHere();
635 Node *range = gvn->transform(new SubINode(limit,init_trip));
636 set_subtree_ctrl( range );
637 hook->init_req(0, range);
638
639 Node *bias = gvn->transform(new AddINode(range,stride));
640 set_subtree_ctrl( bias );
641 hook->init_req(1, bias);
642
643 Node *bias1 = gvn->transform(new AddINode(bias,one_m));
644 set_subtree_ctrl( bias1 );
645 hook->init_req(2, bias1);
646
647 trip_count = gvn->transform(new DivINode(0,bias1,stride));
648 set_subtree_ctrl( trip_count );
649 hook->init_req(3, trip_count);
650 break;
651 }
652
653 case BoolTest::ge: // Maybe convert to '>' case
654 limit = gvn->transform(new AddINode(limit,one_m));
655 set_subtree_ctrl( limit );
656 hook->init_req(4 ,limit);
657
658 bt = BoolTest::gt;
659 // Make the new limit be in the same loop nest as the old limit
660 //_loop.map(limit->_idx,limit_loop);
661 // Fall into next case
662 case BoolTest::gt: { // Maybe convert to '!=' case
663 if (stride_con > 0) // count up loop rolls through MININT
664 ShouldNotReachHere();
665 Node *range = gvn->transform(new SubINode(limit,init_trip));
666 set_subtree_ctrl( range );
667 hook->init_req(0, range);
668
669 Node *bias = gvn->transform(new AddINode(range,stride));
670 set_subtree_ctrl( bias );
671 hook->init_req(1, bias);
672
673 Node *bias1 = gvn->transform(new AddINode(bias,one_p));
674 set_subtree_ctrl( bias1 );
675 hook->init_req(2, bias1);
676
677 trip_count = gvn->transform(new DivINode(0,bias1,stride));
678 set_subtree_ctrl( trip_count );
679 hook->init_req(3, trip_count);
680 break;
681 }
682 } // switch( bt )
683
684 Node *span = gvn->transform(new MulINode(trip_count,stride));
685 set_subtree_ctrl( span );
686 hook->init_req(5, span);
687
688 limit = gvn->transform(new AddINode(span,init_trip));
689 set_subtree_ctrl( limit );
690
691 } // LoopLimitCheck
692
693 if (!UseCountedLoopSafepoints) {
694 // Check for SafePoint on backedge and remove
695 Node *sfpt = x->in(LoopNode::LoopBackControl);
696 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
697 lazy_replace( sfpt, iftrue );
698 if (loop->_safepts != NULL) {
699 loop->_safepts->yank(sfpt);
700 }
701 loop->_tail = iftrue;
702 }
703 }
704
705 // Build a canonical trip test.
706 // Clone code, as old values may be in use.
707 incr = incr->clone();
708 incr->set_req(1,phi);
709 incr->set_req(2,stride);
710 incr = _igvn.register_new_node_with_optimizer(incr);
711 set_early_ctrl( incr );
712 _igvn.rehash_node_delayed(phi);
812 loop->dump_head();
813 }
814 #endif
815
816 C->print_method(PHASE_AFTER_CLOOPS, 3);
817
818 // Capture bounds of the loop in the induction variable Phi before
819 // subsequent transformation (iteration splitting) obscures the
820 // bounds
821 l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
822
823 return true;
824 }
825
826 //----------------------exact_limit-------------------------------------------
827 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
828 assert(loop->_head->is_CountedLoop(), "");
829 CountedLoopNode *cl = loop->_head->as_CountedLoop();
830 assert(cl->is_valid_counted_loop(), "");
831
832 if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 ||
833 cl->limit()->Opcode() == Op_LoopLimit) {
834 // Old code has exact limit (it could be incorrect in case of int overflow).
835 // Loop limit is exact with stride == 1. And loop may already have exact limit.
836 return cl->limit();
837 }
838 Node *limit = NULL;
839 #ifdef ASSERT
840 BoolTest::mask bt = cl->loopexit()->test_trip();
841 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
842 #endif
843 if (cl->has_exact_trip_count()) {
844 // Simple case: loop has constant boundaries.
845 // Use jlongs to avoid integer overflow.
846 int stride_con = cl->stride_con();
847 jlong init_con = cl->init_trip()->get_int();
848 jlong limit_con = cl->limit()->get_int();
849 julong trip_cnt = cl->trip_count();
850 jlong final_con = init_con + trip_cnt*stride_con;
851 int final_int = (int)final_con;
852 // The final value should be in integer range since the loop
1880 } else if (_parent != NULL && !_irreducible) {
1881 // Not a counted loop. Keep one safepoint.
1882 bool keep_one_sfpt = true;
1883 remove_safepoints(phase, keep_one_sfpt);
1884 }
1885
1886 // Recursively
1887 if (_child) _child->counted_loop( phase );
1888 if (_next) _next ->counted_loop( phase );
1889 }
1890
1891 #ifndef PRODUCT
1892 //------------------------------dump_head--------------------------------------
1893 // Dump 1 liner for loop header info
1894 void IdealLoopTree::dump_head( ) const {
1895 for (uint i=0; i<_nest; i++)
1896 tty->print(" ");
1897 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
1898 if (_irreducible) tty->print(" IRREDUCIBLE");
1899 Node* entry = _head->in(LoopNode::EntryControl);
1900 if (LoopLimitCheck) {
1901 Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1902 if (predicate != NULL ) {
1903 tty->print(" limit_check");
1904 entry = entry->in(0)->in(0);
1905 }
1906 }
1907 if (UseLoopPredicate) {
1908 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1909 if (entry != NULL) {
1910 tty->print(" predicated");
1911 }
1912 }
1913 if (_head->is_CountedLoop()) {
1914 CountedLoopNode *cl = _head->as_CountedLoop();
1915 tty->print(" counted");
1916
1917 Node* init_n = cl->init_trip();
1918 if (init_n != NULL && init_n->is_Con())
1919 tty->print(" [%d,", cl->init_trip()->get_int());
1920 else
1921 tty->print(" [int,");
1922 Node* limit_n = cl->limit();
1923 if (limit_n != NULL && limit_n->is_Con())
1924 tty->print("%d),", cl->limit()->get_int());
1925 else
1926 tty->print("int),");
2305 while (_deadlist.size()) {
2306 _igvn.remove_globally_dead_node(_deadlist.pop());
2307 }
2308
2309 if (stop_early) {
2310 assert(do_expensive_nodes, "why are we here?");
2311 if (process_expensive_nodes()) {
2312 // If we made some progress when processing expensive nodes then
2313 // the IGVN may modify the graph in a way that will allow us to
2314 // make some more progress: we need to try processing expensive
2315 // nodes again.
2316 C->set_major_progress();
2317 }
2318 _igvn.optimize();
2319 return;
2320 }
2321
2322 // Some parser-inserted loop predicates could never be used by loop
2323 // predication or they were moved away from loop during some optimizations.
2324 // For example, peeling. Eliminate them before next loop optimizations.
2325 if (UseLoopPredicate || LoopLimitCheck) {
2326 eliminate_useless_predicates();
2327 }
2328
2329 #ifndef PRODUCT
2330 C->verify_graph_edges();
2331 if (_verify_me) { // Nested verify pass?
2332 // Check to see if the verify mode is broken
2333 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2334 return;
2335 }
2336 if(VerifyLoopOptimizations) verify();
2337 if(TraceLoopOpts && C->has_loops()) {
2338 _ltree_root->dump();
2339 }
2340 #endif
2341
2342 if (skip_loop_opts) {
2343 // restore major progress flag
2344 for (int i = 0; i < old_progress; i++) {
2345 C->set_major_progress();
|
446 // check if there is a possiblity of IV overflowing after the first increment
447 if (stride_con > 0) {
448 if (init_t->_hi > max_jint - stride_con) {
449 return false;
450 }
451 } else {
452 if (init_t->_lo < min_jint - stride_con) {
453 return false;
454 }
455 }
456 }
457
458 // =================================================
459 // ---- SUCCESS! Found A Trip-Counted Loop! -----
460 //
461 assert(x->Opcode() == Op_Loop, "regular loops only");
462 C->print_method(PHASE_BEFORE_CLOOPS, 3);
463
464 Node *hook = new Node(6);
465
466 // ===================================================
467 // Generate loop limit check to avoid integer overflow
468 // in cases like next (cyclic loops):
469 //
470 // for (i=0; i <= max_jint; i++) {}
471 // for (i=0; i < max_jint; i+=2) {}
472 //
473 //
474 // Limit check predicate depends on the loop test:
475 //
476 // for(;i != limit; i++) --> limit <= (max_jint)
477 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
478 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
479 //
480
481 // Check if limit is excluded to do more precise int overflow check.
482 bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge);
483 int stride_m = stride_con - (incl_limit ? 0 : (stride_con > 0 ? 1 : -1));
484
485 // If compare points directly to the phi we need to adjust
574 // 'ne' can be replaced with 'gt' only when init > limit.
575 if (stride_con < 0 && init_t->_lo > limit_t->_hi)
576 bt = BoolTest::gt;
577 }
578
579 if (incl_limit) {
580 // The limit check guaranties that 'limit <= (max_jint - stride)' so
581 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
582 //
583 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
584 limit = gvn->transform(new AddINode(limit, one));
585 if (bt == BoolTest::le)
586 bt = BoolTest::lt;
587 else if (bt == BoolTest::ge)
588 bt = BoolTest::gt;
589 else
590 ShouldNotReachHere();
591 }
592 set_subtree_ctrl( limit );
593
594 if (!UseCountedLoopSafepoints) {
595 // Check for SafePoint on backedge and remove
596 Node *sfpt = x->in(LoopNode::LoopBackControl);
597 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
598 lazy_replace( sfpt, iftrue );
599 if (loop->_safepts != NULL) {
600 loop->_safepts->yank(sfpt);
601 }
602 loop->_tail = iftrue;
603 }
604 }
605
606 // Build a canonical trip test.
607 // Clone code, as old values may be in use.
608 incr = incr->clone();
609 incr->set_req(1,phi);
610 incr->set_req(2,stride);
611 incr = _igvn.register_new_node_with_optimizer(incr);
612 set_early_ctrl( incr );
613 _igvn.rehash_node_delayed(phi);
713 loop->dump_head();
714 }
715 #endif
716
717 C->print_method(PHASE_AFTER_CLOOPS, 3);
718
719 // Capture bounds of the loop in the induction variable Phi before
720 // subsequent transformation (iteration splitting) obscures the
721 // bounds
722 l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
723
724 return true;
725 }
726
727 //----------------------exact_limit-------------------------------------------
728 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
729 assert(loop->_head->is_CountedLoop(), "");
730 CountedLoopNode *cl = loop->_head->as_CountedLoop();
731 assert(cl->is_valid_counted_loop(), "");
732
733 if (ABS(cl->stride_con()) == 1 ||
734 cl->limit()->Opcode() == Op_LoopLimit) {
735 // Old code has exact limit (it could be incorrect in case of int overflow).
736 // Loop limit is exact with stride == 1. And loop may already have exact limit.
737 return cl->limit();
738 }
739 Node *limit = NULL;
740 #ifdef ASSERT
741 BoolTest::mask bt = cl->loopexit()->test_trip();
742 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
743 #endif
744 if (cl->has_exact_trip_count()) {
745 // Simple case: loop has constant boundaries.
746 // Use jlongs to avoid integer overflow.
747 int stride_con = cl->stride_con();
748 jlong init_con = cl->init_trip()->get_int();
749 jlong limit_con = cl->limit()->get_int();
750 julong trip_cnt = cl->trip_count();
751 jlong final_con = init_con + trip_cnt*stride_con;
752 int final_int = (int)final_con;
753 // The final value should be in integer range since the loop
1781 } else if (_parent != NULL && !_irreducible) {
1782 // Not a counted loop. Keep one safepoint.
1783 bool keep_one_sfpt = true;
1784 remove_safepoints(phase, keep_one_sfpt);
1785 }
1786
1787 // Recursively
1788 if (_child) _child->counted_loop( phase );
1789 if (_next) _next ->counted_loop( phase );
1790 }
1791
1792 #ifndef PRODUCT
1793 //------------------------------dump_head--------------------------------------
1794 // Dump 1 liner for loop header info
1795 void IdealLoopTree::dump_head( ) const {
1796 for (uint i=0; i<_nest; i++)
1797 tty->print(" ");
1798 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
1799 if (_irreducible) tty->print(" IRREDUCIBLE");
1800 Node* entry = _head->in(LoopNode::EntryControl);
1801 Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1802 if (predicate != NULL ) {
1803 tty->print(" limit_check");
1804 entry = entry->in(0)->in(0);
1805 }
1806 if (UseLoopPredicate) {
1807 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1808 if (entry != NULL) {
1809 tty->print(" predicated");
1810 }
1811 }
1812 if (_head->is_CountedLoop()) {
1813 CountedLoopNode *cl = _head->as_CountedLoop();
1814 tty->print(" counted");
1815
1816 Node* init_n = cl->init_trip();
1817 if (init_n != NULL && init_n->is_Con())
1818 tty->print(" [%d,", cl->init_trip()->get_int());
1819 else
1820 tty->print(" [int,");
1821 Node* limit_n = cl->limit();
1822 if (limit_n != NULL && limit_n->is_Con())
1823 tty->print("%d),", cl->limit()->get_int());
1824 else
1825 tty->print("int),");
2204 while (_deadlist.size()) {
2205 _igvn.remove_globally_dead_node(_deadlist.pop());
2206 }
2207
2208 if (stop_early) {
2209 assert(do_expensive_nodes, "why are we here?");
2210 if (process_expensive_nodes()) {
2211 // If we made some progress when processing expensive nodes then
2212 // the IGVN may modify the graph in a way that will allow us to
2213 // make some more progress: we need to try processing expensive
2214 // nodes again.
2215 C->set_major_progress();
2216 }
2217 _igvn.optimize();
2218 return;
2219 }
2220
2221 // Some parser-inserted loop predicates could never be used by loop
2222 // predication or they were moved away from loop during some optimizations.
2223 // For example, peeling. Eliminate them before next loop optimizations.
2224 if (UseLoopPredicate) {
2225 eliminate_useless_predicates();
2226 }
2227
2228 #ifndef PRODUCT
2229 C->verify_graph_edges();
2230 if (_verify_me) { // Nested verify pass?
2231 // Check to see if the verify mode is broken
2232 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2233 return;
2234 }
2235 if(VerifyLoopOptimizations) verify();
2236 if(TraceLoopOpts && C->has_loops()) {
2237 _ltree_root->dump();
2238 }
2239 #endif
2240
2241 if (skip_loop_opts) {
2242 // restore major progress flag
2243 for (int i = 0; i < old_progress; i++) {
2244 C->set_major_progress();
|