426
427 const TypeInt* init_t = gvn->type(init_trip)->is_int();
428 const TypeInt* limit_t = gvn->type(limit)->is_int();
429
430 if (stride_con > 0) {
431 jlong init_p = (jlong)init_t->_lo + stride_con;
432 if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
433 return false; // cyclic loop or this loop trips only once
434 } else {
435 jlong init_p = (jlong)init_t->_hi + stride_con;
436 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
437 return false; // cyclic loop or this loop trips only once
438 }
439
440 // =================================================
441 // ---- SUCCESS! Found A Trip-Counted Loop! -----
442 //
443 assert(x->Opcode() == Op_Loop, "regular loops only");
444 C->print_method(PHASE_BEFORE_CLOOPS, 3);
445
446 Node *hook = new (C) Node(6);
447
448 if (LoopLimitCheck) {
449
450 // ===================================================
451 // Generate loop limit check to avoid integer overflow
452 // in cases like next (cyclic loops):
453 //
454 // for (i=0; i <= max_jint; i++) {}
455 // for (i=0; i < max_jint; i+=2) {}
456 //
457 //
458 // Limit check predicate depends on the loop test:
459 //
460 // for(;i != limit; i++) --> limit <= (max_jint)
461 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
462 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
463 //
464
465 // Check if limit is excluded to do more precise int overflow check.
466 bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge);
489 // Generate loop's limit check.
490 // Loop limit check predicate should be near the loop.
491 ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);
492 if (!limit_check_proj) {
493 // The limit check predicate is not generated if this method trapped here before.
494 #ifdef ASSERT
495 if (TraceLoopLimitCheck) {
496 tty->print("missing loop limit check:");
497 loop->dump_head();
498 x->dump(1);
499 }
500 #endif
501 return false;
502 }
503
504 IfNode* check_iff = limit_check_proj->in(0)->as_If();
505 Node* cmp_limit;
506 Node* bol;
507
508 if (stride_con > 0) {
509 cmp_limit = new (C) CmpINode(limit, _igvn.intcon(max_jint - stride_m));
510 bol = new (C) BoolNode(cmp_limit, BoolTest::le);
511 } else {
512 cmp_limit = new (C) CmpINode(limit, _igvn.intcon(min_jint - stride_m));
513 bol = new (C) BoolNode(cmp_limit, BoolTest::ge);
514 }
515 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
516 bol = _igvn.register_new_node_with_optimizer(bol);
517 set_subtree_ctrl(bol);
518
519 // Replace condition in original predicate but preserve Opaque node
520 // so that previous predicates could be found.
521 assert(check_iff->in(1)->Opcode() == Op_Conv2B &&
522 check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");
523 Node* opq = check_iff->in(1)->in(1);
524 _igvn.hash_delete(opq);
525 opq->set_req(1, bol);
526 // Update ctrl.
527 set_ctrl(opq, check_iff->in(0));
528 set_ctrl(check_iff->in(1), check_iff->in(0));
529
530 #ifndef PRODUCT
531 // report that the loop predication has been actually performed
532 // for this loop
533 if (TraceLoopLimitCheck) {
534 tty->print_cr("Counted Loop Limit Check generated:");
535 debug_only( bol->dump(2); )
536 }
537 #endif
538 }
539
540 if (phi_incr != NULL) {
541 // If compare points directly to the phi we need to adjust
542 // the compare so that it points to the incr. Limit have
543 // to be adjusted to keep trip count the same and we
544 // should avoid int overflow.
545 //
546 // i = init; do {} while(i++ < limit);
547 // is converted to
548 // i = init; do {} while(++i < limit+1);
549 //
550 limit = gvn->transform(new (C) AddINode(limit, stride));
551 }
552
553 // Now we need to canonicalize loop condition.
554 if (bt == BoolTest::ne) {
555 assert(stride_con == 1 || stride_con == -1, "simple increment only");
556 // 'ne' can be replaced with 'lt' only when init < limit.
557 if (stride_con > 0 && init_t->_hi < limit_t->_lo)
558 bt = BoolTest::lt;
559 // 'ne' can be replaced with 'gt' only when init > limit.
560 if (stride_con < 0 && init_t->_lo > limit_t->_hi)
561 bt = BoolTest::gt;
562 }
563
564 if (incl_limit) {
565 // The limit check guaranties that 'limit <= (max_jint - stride)' so
566 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
567 //
568 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
569 limit = gvn->transform(new (C) AddINode(limit, one));
570 if (bt == BoolTest::le)
571 bt = BoolTest::lt;
572 else if (bt == BoolTest::ge)
573 bt = BoolTest::gt;
574 else
575 ShouldNotReachHere();
576 }
577 set_subtree_ctrl( limit );
578
579 } else { // LoopLimitCheck
580
581 // If compare points to incr, we are ok. Otherwise the compare
582 // can directly point to the phi; in this case adjust the compare so that
583 // it points to the incr by adjusting the limit.
584 if (cmp->in(1) == phi || cmp->in(2) == phi)
585 limit = gvn->transform(new (C) AddINode(limit,stride));
586
587 // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.
588 // Final value for iterator should be: trip_count * stride + init_trip.
589 Node *one_p = gvn->intcon( 1);
590 Node *one_m = gvn->intcon(-1);
591
592 Node *trip_count = NULL;
593 switch( bt ) {
594 case BoolTest::eq:
595 ShouldNotReachHere();
596 case BoolTest::ne: // Ahh, the case we desire
597 if (stride_con == 1)
598 trip_count = gvn->transform(new (C) SubINode(limit,init_trip));
599 else if (stride_con == -1)
600 trip_count = gvn->transform(new (C) SubINode(init_trip,limit));
601 else
602 ShouldNotReachHere();
603 set_subtree_ctrl(trip_count);
604 //_loop.map(trip_count->_idx,loop(limit));
605 break;
606 case BoolTest::le: // Maybe convert to '<' case
607 limit = gvn->transform(new (C) AddINode(limit,one_p));
608 set_subtree_ctrl( limit );
609 hook->init_req(4, limit);
610
611 bt = BoolTest::lt;
612 // Make the new limit be in the same loop nest as the old limit
613 //_loop.map(limit->_idx,limit_loop);
614 // Fall into next case
615 case BoolTest::lt: { // Maybe convert to '!=' case
616 if (stride_con < 0) // Count down loop rolls through MAXINT
617 ShouldNotReachHere();
618 Node *range = gvn->transform(new (C) SubINode(limit,init_trip));
619 set_subtree_ctrl( range );
620 hook->init_req(0, range);
621
622 Node *bias = gvn->transform(new (C) AddINode(range,stride));
623 set_subtree_ctrl( bias );
624 hook->init_req(1, bias);
625
626 Node *bias1 = gvn->transform(new (C) AddINode(bias,one_m));
627 set_subtree_ctrl( bias1 );
628 hook->init_req(2, bias1);
629
630 trip_count = gvn->transform(new (C) DivINode(0,bias1,stride));
631 set_subtree_ctrl( trip_count );
632 hook->init_req(3, trip_count);
633 break;
634 }
635
636 case BoolTest::ge: // Maybe convert to '>' case
637 limit = gvn->transform(new (C) AddINode(limit,one_m));
638 set_subtree_ctrl( limit );
639 hook->init_req(4 ,limit);
640
641 bt = BoolTest::gt;
642 // Make the new limit be in the same loop nest as the old limit
643 //_loop.map(limit->_idx,limit_loop);
644 // Fall into next case
645 case BoolTest::gt: { // Maybe convert to '!=' case
646 if (stride_con > 0) // count up loop rolls through MININT
647 ShouldNotReachHere();
648 Node *range = gvn->transform(new (C) SubINode(limit,init_trip));
649 set_subtree_ctrl( range );
650 hook->init_req(0, range);
651
652 Node *bias = gvn->transform(new (C) AddINode(range,stride));
653 set_subtree_ctrl( bias );
654 hook->init_req(1, bias);
655
656 Node *bias1 = gvn->transform(new (C) AddINode(bias,one_p));
657 set_subtree_ctrl( bias1 );
658 hook->init_req(2, bias1);
659
660 trip_count = gvn->transform(new (C) DivINode(0,bias1,stride));
661 set_subtree_ctrl( trip_count );
662 hook->init_req(3, trip_count);
663 break;
664 }
665 } // switch( bt )
666
667 Node *span = gvn->transform(new (C) MulINode(trip_count,stride));
668 set_subtree_ctrl( span );
669 hook->init_req(5, span);
670
671 limit = gvn->transform(new (C) AddINode(span,init_trip));
672 set_subtree_ctrl( limit );
673
674 } // LoopLimitCheck
675
676 // Check for SafePoint on backedge and remove
677 Node *sfpt = x->in(LoopNode::LoopBackControl);
678 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
679 lazy_replace( sfpt, iftrue );
680 if (loop->_safepts != NULL) {
681 loop->_safepts->yank(sfpt);
682 }
683 loop->_tail = iftrue;
684 }
685
686 // Build a canonical trip test.
687 // Clone code, as old values may be in use.
688 incr = incr->clone();
689 incr->set_req(1,phi);
690 incr->set_req(2,stride);
691 incr = _igvn.register_new_node_with_optimizer(incr);
700 Node* nphi = PhiNode::make(phi->in(0), phi->in(LoopNode::EntryControl), TypeInt::INT);
701 nphi->set_req(LoopNode::LoopBackControl, phi->in(LoopNode::LoopBackControl));
702 nphi = _igvn.register_new_node_with_optimizer(nphi);
703 set_ctrl(nphi, get_ctrl(phi));
704 _igvn.replace_node(phi, nphi);
705 phi = nphi->as_Phi();
706 }
707 cmp = cmp->clone();
708 cmp->set_req(1,incr);
709 cmp->set_req(2,limit);
710 cmp = _igvn.register_new_node_with_optimizer(cmp);
711 set_ctrl(cmp, iff->in(0));
712
713 test = test->clone()->as_Bool();
714 (*(BoolTest*)&test->_test)._test = bt;
715 test->set_req(1,cmp);
716 _igvn.register_new_node_with_optimizer(test);
717 set_ctrl(test, iff->in(0));
718
719 // Replace the old IfNode with a new LoopEndNode
720 Node *lex = _igvn.register_new_node_with_optimizer(new (C) CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt ));
721 IfNode *le = lex->as_If();
722 uint dd = dom_depth(iff);
723 set_idom(le, le->in(0), dd); // Update dominance for loop exit
724 set_loop(le, loop);
725
726 // Get the loop-exit control
727 Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue));
728
729 // Need to swap loop-exit and loop-back control?
730 if (iftrue_op == Op_IfFalse) {
731 Node *ift2=_igvn.register_new_node_with_optimizer(new (C) IfTrueNode (le));
732 Node *iff2=_igvn.register_new_node_with_optimizer(new (C) IfFalseNode(le));
733
734 loop->_tail = back_control = ift2;
735 set_loop(ift2, loop);
736 set_loop(iff2, get_loop(iffalse));
737
738 // Lazy update of 'get_ctrl' mechanism.
739 lazy_replace_proj( iffalse, iff2 );
740 lazy_replace_proj( iftrue, ift2 );
741
742 // Swap names
743 iffalse = iff2;
744 iftrue = ift2;
745 } else {
746 _igvn.hash_delete(iffalse);
747 _igvn.hash_delete(iftrue);
748 iffalse->set_req_X( 0, le, &_igvn );
749 iftrue ->set_req_X( 0, le, &_igvn );
750 }
751
752 set_idom(iftrue, le, dd+1);
753 set_idom(iffalse, le, dd+1);
754 assert(iff->outcnt() == 0, "should be dead now");
755 lazy_replace( iff, le ); // fix 'get_ctrl'
756
757 // Now setup a new CountedLoopNode to replace the existing LoopNode
758 CountedLoopNode *l = new (C) CountedLoopNode(init_control, back_control);
759 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve
760 // The following assert is approximately true, and defines the intention
761 // of can_be_counted_loop. It fails, however, because phase->type
762 // is not yet initialized for this loop and its parts.
763 //assert(l->can_be_counted_loop(this), "sanity");
764 _igvn.register_new_node_with_optimizer(l);
765 set_loop(l, loop);
766 loop->_head = l;
767 // Fix all data nodes placed at the old loop head.
768 // Uses the lazy-update mechanism of 'get_ctrl'.
769 lazy_replace( x, l );
770 set_idom(l, init_control, dom_depth(x));
771
772 // Check for immediately preceding SafePoint and remove
773 Node *sfpt2 = le->in(0);
774 if (sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2)) {
775 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
776 if (loop->_safepts != NULL) {
777 loop->_safepts->yank(sfpt2);
778 }
812 Node *limit = NULL;
813 #ifdef ASSERT
814 BoolTest::mask bt = cl->loopexit()->test_trip();
815 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
816 #endif
817 if (cl->has_exact_trip_count()) {
818 // Simple case: loop has constant boundaries.
819 // Use jlongs to avoid integer overflow.
820 int stride_con = cl->stride_con();
821 jlong init_con = cl->init_trip()->get_int();
822 jlong limit_con = cl->limit()->get_int();
823 julong trip_cnt = cl->trip_count();
824 jlong final_con = init_con + trip_cnt*stride_con;
825 int final_int = (int)final_con;
826 // The final value should be in integer range since the loop
827 // is counted and the limit was checked for overflow.
828 assert(final_con == (jlong)final_int, "final value should be integer");
829 limit = _igvn.intcon(final_int);
830 } else {
831 // Create new LoopLimit node to get exact limit (final iv value).
832 limit = new (C) LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride());
833 register_new_node(limit, cl->in(LoopNode::EntryControl));
834 }
835 assert(limit != NULL, "sanity");
836 return limit;
837 }
838
839 //------------------------------Ideal------------------------------------------
840 // Return a node which is more "ideal" than the current node.
841 // Attempt to convert into a counted-loop.
842 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
843 if (!can_be_counted_loop(phase)) {
844 phase->C->set_major_progress();
845 }
846 return RegionNode::Ideal(phase, can_reshape);
847 }
848
849
850 //=============================================================================
851 //------------------------------Ideal------------------------------------------
852 // Return a node which is more "ideal" than the current node.
929 const TypeInt* init_t = phase->type(in(Init) )->is_int();
930 const TypeInt* limit_t = phase->type(in(Limit))->is_int();
931 int stride_p;
932 jlong lim, ini;
933 julong max;
934 if (stride_con > 0) {
935 stride_p = stride_con;
936 lim = limit_t->_hi;
937 ini = init_t->_lo;
938 max = (julong)max_jint;
939 } else {
940 stride_p = -stride_con;
941 lim = init_t->_hi;
942 ini = limit_t->_lo;
943 max = (julong)min_jint;
944 }
945 julong range = lim - ini + stride_p;
946 if (range <= max) {
947 // Convert to integer expression if it is not overflow.
948 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
949 Node *range = phase->transform(new (phase->C) SubINode(in(Limit), in(Init)));
950 Node *bias = phase->transform(new (phase->C) AddINode(range, stride_m));
951 Node *trip = phase->transform(new (phase->C) DivINode(0, bias, in(Stride)));
952 Node *span = phase->transform(new (phase->C) MulINode(trip, in(Stride)));
953 return new (phase->C) AddINode(span, in(Init)); // exact limit
954 }
955
956 if (is_power_of_2(stride_p) || // divisor is 2^n
957 !Matcher::has_match_rule(Op_LoopLimit)) { // or no specialized Mach node?
958 // Convert to long expression to avoid integer overflow
959 // and let igvn optimizer convert this division.
960 //
961 Node* init = phase->transform( new (phase->C) ConvI2LNode(in(Init)));
962 Node* limit = phase->transform( new (phase->C) ConvI2LNode(in(Limit)));
963 Node* stride = phase->longcon(stride_con);
964 Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1));
965
966 Node *range = phase->transform(new (phase->C) SubLNode(limit, init));
967 Node *bias = phase->transform(new (phase->C) AddLNode(range, stride_m));
968 Node *span;
969 if (stride_con > 0 && is_power_of_2(stride_p)) {
970 // bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride)
971 // and avoid generating rounding for division. Zero trip guard should
972 // guarantee that init < limit but sometimes the guard is missing and
973 // we can get situation when init > limit. Note, for the empty loop
974 // optimization zero trip guard is generated explicitly which leaves
975 // only RCE predicate where exact limit is used and the predicate
976 // will simply fail forcing recompilation.
977 Node* neg_stride = phase->longcon(-stride_con);
978 span = phase->transform(new (phase->C) AndLNode(bias, neg_stride));
979 } else {
980 Node *trip = phase->transform(new (phase->C) DivLNode(0, bias, stride));
981 span = phase->transform(new (phase->C) MulLNode(trip, stride));
982 }
983 // Convert back to int
984 Node *span_int = phase->transform(new (phase->C) ConvL2INode(span));
985 return new (phase->C) AddINode(span_int, in(Init)); // exact limit
986 }
987
988 return NULL; // No progress
989 }
990
991 //------------------------------Identity---------------------------------------
992 // If stride == 1 return limit node.
993 Node *LoopLimitNode::Identity( PhaseTransform *phase ) {
994 int stride_con = phase->type(in(Stride))->is_int()->get_con();
995 if (stride_con == 1 || stride_con == -1)
996 return in(Limit);
997 return this;
998 }
999
1000 //=============================================================================
1001 //----------------------match_incr_with_optional_truncation--------------------
1002 // Match increment with optional truncation:
1003 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
1004 // Return NULL for failure. Success returns the increment node.
1005 Node* CountedLoopNode::match_incr_with_optional_truncation(
1171
1172 //------------------------------set_nest---------------------------------------
1173 // Set loop tree nesting depth. Accumulate _has_call bits.
1174 int IdealLoopTree::set_nest( uint depth ) {
1175 _nest = depth;
1176 int bits = _has_call;
1177 if( _child ) bits |= _child->set_nest(depth+1);
1178 if( bits ) _has_call = 1;
1179 if( _next ) bits |= _next ->set_nest(depth );
1180 return bits;
1181 }
1182
1183 //------------------------------split_fall_in----------------------------------
1184 // Split out multiple fall-in edges from the loop header. Move them to a
1185 // private RegionNode before the loop. This becomes the loop landing pad.
1186 void IdealLoopTree::split_fall_in( PhaseIdealLoop *phase, int fall_in_cnt ) {
1187 PhaseIterGVN &igvn = phase->_igvn;
1188 uint i;
1189
1190 // Make a new RegionNode to be the landing pad.
1191 Node *landing_pad = new (phase->C) RegionNode( fall_in_cnt+1 );
1192 phase->set_loop(landing_pad,_parent);
1193 // Gather all the fall-in control paths into the landing pad
1194 uint icnt = fall_in_cnt;
1195 uint oreq = _head->req();
1196 for( i = oreq-1; i>0; i-- )
1197 if( !phase->is_member( this, _head->in(i) ) )
1198 landing_pad->set_req(icnt--,_head->in(i));
1199
1200 // Peel off PhiNode edges as well
1201 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1202 Node *oj = _head->fast_out(j);
1203 if( oj->is_Phi() ) {
1204 PhiNode* old_phi = oj->as_Phi();
1205 assert( old_phi->region() == _head, "" );
1206 igvn.hash_delete(old_phi); // Yank from hash before hacking edges
1207 Node *p = PhiNode::make_blank(landing_pad, old_phi);
1208 uint icnt = fall_in_cnt;
1209 for( i = oreq-1; i>0; i-- ) {
1210 if( !phase->is_member( this, _head->in(i) ) ) {
1211 p->init_req(icnt--, old_phi->in(i));
1257 _head->del_req(i);
1258 }
1259 }
1260 // Transform landing pad
1261 igvn.register_new_node_with_optimizer(landing_pad, _head);
1262 // Insert landing pad into the header
1263 _head->add_req(landing_pad);
1264 }
1265
1266 //------------------------------split_outer_loop-------------------------------
1267 // Split out the outermost loop from this shared header.
1268 void IdealLoopTree::split_outer_loop( PhaseIdealLoop *phase ) {
1269 PhaseIterGVN &igvn = phase->_igvn;
1270
1271 // Find index of outermost loop; it should also be my tail.
1272 uint outer_idx = 1;
1273 while( _head->in(outer_idx) != _tail ) outer_idx++;
1274
1275 // Make a LoopNode for the outermost loop.
1276 Node *ctl = _head->in(LoopNode::EntryControl);
1277 Node *outer = new (phase->C) LoopNode( ctl, _head->in(outer_idx) );
1278 outer = igvn.register_new_node_with_optimizer(outer, _head);
1279 phase->set_created_loop_node();
1280
1281 // Outermost loop falls into '_head' loop
1282 _head->set_req(LoopNode::EntryControl, outer);
1283 _head->del_req(outer_idx);
1284 // Split all the Phis up between '_head' loop and 'outer' loop.
1285 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1286 Node *out = _head->fast_out(j);
1287 if( out->is_Phi() ) {
1288 PhiNode *old_phi = out->as_Phi();
1289 assert( old_phi->region() == _head, "" );
1290 Node *phi = PhiNode::make_blank(outer, old_phi);
1291 phi->init_req(LoopNode::EntryControl, old_phi->in(LoopNode::EntryControl));
1292 phi->init_req(LoopNode::LoopBackControl, old_phi->in(outer_idx));
1293 phi = igvn.register_new_node_with_optimizer(phi, old_phi);
1294 // Make old Phi point to new Phi on the fall-in path
1295 igvn.replace_input_of(old_phi, LoopNode::EntryControl, phi);
1296 old_phi->del_req(outer_idx);
1297 }
1371 if( cnt > hotcnt ) { // Grab hottest path
1372 warmcnt = hotcnt;
1373 hotcnt = cnt;
1374 hot_idx = i;
1375 } else if( cnt > warmcnt ) { // And 2nd hottest path
1376 warmcnt = cnt;
1377 }
1378 }
1379
1380 // See if the hottest backedge is worthy of being an inner loop
1381 // by being much hotter than the next hottest backedge.
1382 if( hotcnt <= 0.0001 ||
1383 hotcnt < 2.0*warmcnt ) hot_idx = 0;// No hot backedge
1384
1385 // Peel out the backedges into a private merge point; peel
1386 // them all except optionally hot_idx.
1387 PhaseIterGVN &igvn = phase->_igvn;
1388
1389 Node *hot_tail = NULL;
1390 // Make a Region for the merge point
1391 Node *r = new (phase->C) RegionNode(1);
1392 for( i = 2; i < _head->req(); i++ ) {
1393 if( i != hot_idx )
1394 r->add_req( _head->in(i) );
1395 else hot_tail = _head->in(i);
1396 }
1397 igvn.register_new_node_with_optimizer(r, _head);
1398 // Plug region into end of loop _head, followed by hot_tail
1399 while( _head->req() > 3 ) _head->del_req( _head->req()-1 );
1400 _head->set_req(2, r);
1401 if( hot_idx ) _head->add_req(hot_tail);
1402
1403 // Split all the Phis up between '_head' loop and the Region 'r'
1404 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1405 Node *out = _head->fast_out(j);
1406 if( out->is_Phi() ) {
1407 PhiNode* n = out->as_Phi();
1408 igvn.hash_delete(n); // Delete from hash before hacking edges
1409 Node *hot_phi = NULL;
1410 Node *phi = new (phase->C) PhiNode(r, n->type(), n->adr_type());
1411 // Check all inputs for the ones to peel out
1412 uint j = 1;
1413 for( uint i = 2; i < n->req(); i++ ) {
1414 if( i != hot_idx )
1415 phi->set_req( j++, n->in(i) );
1416 else hot_phi = n->in(i);
1417 }
1418 // Register the phi but do not transform until whole place transforms
1419 igvn.register_new_node_with_optimizer(phi, n);
1420 // Add the merge phi to the old Phi
1421 while( n->req() > 3 ) n->del_req( n->req()-1 );
1422 n->set_req(2, phi);
1423 if( hot_idx ) n->add_req(hot_phi);
1424 }
1425 }
1426
1427
1428 // Insert a new IdealLoopTree inserted below me. Turn it into a clone
1429 // of self loop tree. Turn self into a loop headed by _head and with
1430 // tail being the new merge point.
1512 assert( phase->is_member( this, _head->in(2) ), "right edge is loop" );
1513
1514 // If I am a shared header (multiple backedges), peel off the many
1515 // backedges into a private merge point and use the merge point as
1516 // the one true backedge.
1517 if( _head->req() > 3 ) {
1518 // Merge the many backedges into a single backedge but leave
1519 // the hottest backedge as separate edge for the following peel.
1520 merge_many_backedges( phase );
1521 result = true;
1522 }
1523
1524 // If I have one hot backedge, peel off myself loop.
1525 // I better be the outermost loop.
1526 if (_head->req() > 3 && !_irreducible) {
1527 split_outer_loop( phase );
1528 result = true;
1529
1530 } else if (!_head->is_Loop() && !_irreducible) {
1531 // Make a new LoopNode to replace the old loop head
1532 Node *l = new (phase->C) LoopNode( _head->in(1), _head->in(2) );
1533 l = igvn.register_new_node_with_optimizer(l, _head);
1534 phase->set_created_loop_node();
1535 // Go ahead and replace _head
1536 phase->_igvn.replace_node( _head, l );
1537 _head = l;
1538 phase->set_loop(_head, this);
1539 }
1540
1541 // Now recursively beautify nested loops
1542 if( _child ) result |= _child->beautify_loops( phase );
1543 if( _next ) result |= _next ->beautify_loops( phase );
1544 return result;
1545 }
1546
1547 //------------------------------allpaths_check_safepts----------------------------
1548 // Allpaths backwards scan from loop tail, terminating each path at first safepoint
1549 // encountered. Helper for check_safepts.
1550 void IdealLoopTree::allpaths_check_safepts(VectorSet &visited, Node_List &stack) {
1551 assert(stack.size() == 0, "empty stack");
1552 stack.push(_tail);
1754 // GCD for the loop. Then all possible IVs are simple multiples of
1755 // the GCD. In practice, this will cover very few extra loops.
1756 // Instead we require 'stride_con2' to be a multiple of 'stride_con',
1757 // where +/-1 is the common case, but other integer multiples are
1758 // also easy to handle.
1759 int ratio_con = stride_con2/stride_con;
1760
1761 if ((ratio_con * stride_con) == stride_con2) { // Check for exact
1762 #ifndef PRODUCT
1763 if (TraceLoopOpts) {
1764 tty->print("Parallel IV: %d ", phi2->_idx);
1765 loop->dump_head();
1766 }
1767 #endif
1768 // Convert to using the trip counter. The parallel induction
1769 // variable differs from the trip counter by a loop-invariant
1770 // amount, the difference between their respective initial values.
1771 // It is scaled by the 'ratio_con'.
1772 Node* ratio = _igvn.intcon(ratio_con);
1773 set_ctrl(ratio, C->root());
1774 Node* ratio_init = new (C) MulINode(init, ratio);
1775 _igvn.register_new_node_with_optimizer(ratio_init, init);
1776 set_early_ctrl(ratio_init);
1777 Node* diff = new (C) SubINode(init2, ratio_init);
1778 _igvn.register_new_node_with_optimizer(diff, init2);
1779 set_early_ctrl(diff);
1780 Node* ratio_idx = new (C) MulINode(phi, ratio);
1781 _igvn.register_new_node_with_optimizer(ratio_idx, phi);
1782 set_ctrl(ratio_idx, cl);
1783 Node* add = new (C) AddINode(ratio_idx, diff);
1784 _igvn.register_new_node_with_optimizer(add);
1785 set_ctrl(add, cl);
1786 _igvn.replace_node( phi2, add );
1787 // Sometimes an induction variable is unused
1788 if (add->outcnt() == 0) {
1789 _igvn.remove_dead_node(add);
1790 }
1791 --i; // deleted this phi; rescan starting with next position
1792 continue;
1793 }
1794 }
1795 }
1796
1797 //------------------------------counted_loop-----------------------------------
1798 // Convert to counted loops where possible
1799 void IdealLoopTree::counted_loop( PhaseIdealLoop *phase ) {
1800
1801 // For grins, set the inner-loop flag here
1802 if (!_child) {
1803 if (_head->is_Loop()) _head->as_Loop()->set_inner_loop();
2871 // at most 1 level.
2872 while( l && l->_head == m ) // Successor heads loop?
2873 l = l->_parent; // Move up 1 for me
2874 // If this loop is not properly parented, then this loop
2875 // has no exit path out, i.e. its an infinite loop.
2876 if( !l ) {
2877 // Make loop "reachable" from root so the CFG is reachable. Basically
2878 // insert a bogus loop exit that is never taken. 'm', the loop head,
2879 // points to 'n', one (of possibly many) fall-in paths. There may be
2880 // many backedges as well.
2881
2882 // Here I set the loop to be the root loop. I could have, after
2883 // inserting a bogus loop exit, restarted the recursion and found my
2884 // new loop exit. This would make the infinite loop a first-class
2885 // loop and it would then get properly optimized. What's the use of
2886 // optimizing an infinite loop?
2887 l = _ltree_root; // Oops, found infinite loop
2888
2889 if (!_verify_only) {
2890 // Insert the NeverBranch between 'm' and it's control user.
2891 NeverBranchNode *iff = new (C) NeverBranchNode( m );
2892 _igvn.register_new_node_with_optimizer(iff);
2893 set_loop(iff, l);
2894 Node *if_t = new (C) CProjNode( iff, 0 );
2895 _igvn.register_new_node_with_optimizer(if_t);
2896 set_loop(if_t, l);
2897
2898 Node* cfg = NULL; // Find the One True Control User of m
2899 for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) {
2900 Node* x = m->fast_out(j);
2901 if (x->is_CFG() && x != m && x != iff)
2902 { cfg = x; break; }
2903 }
2904 assert(cfg != NULL, "must find the control user of m");
2905 uint k = 0; // Probably cfg->in(0)
2906 while( cfg->in(k) != m ) k++; // But check incase cfg is a Region
2907 cfg->set_req( k, if_t ); // Now point to NeverBranch
2908
2909 // Now create the never-taken loop exit
2910 Node *if_f = new (C) CProjNode( iff, 1 );
2911 _igvn.register_new_node_with_optimizer(if_f);
2912 set_loop(if_f, l);
2913 // Find frame ptr for Halt. Relies on the optimizer
2914 // V-N'ing. Easier and quicker than searching through
2915 // the program structure.
2916 Node *frame = new (C) ParmNode( C->start(), TypeFunc::FramePtr );
2917 _igvn.register_new_node_with_optimizer(frame);
2918 // Halt & Catch Fire
2919 Node *halt = new (C) HaltNode( if_f, frame );
2920 _igvn.register_new_node_with_optimizer(halt);
2921 set_loop(halt, l);
2922 C->root()->add_req(halt);
2923 }
2924 set_loop(C->root(), _ltree_root);
2925 }
2926 }
2927 // Weeny check for irreducible. This child was already visited (this
2928 // IS the post-work phase). Is this child's loop header post-visited
2929 // as well? If so, then I found another entry into the loop.
2930 if (!_verify_only) {
2931 while( is_postvisited(l->_head) ) {
2932 // found irreducible
2933 l->_irreducible = 1; // = true
2934 l = l->_parent;
2935 _has_irreducible_loops = true;
2936 // Check for bad CFG here to prevent crash, and bailout of compile
2937 if (l == NULL) {
2938 C->record_method_not_compilable("unhandled CFG detected during loop optimization");
2939 return pre_order;
|
426
427 const TypeInt* init_t = gvn->type(init_trip)->is_int();
428 const TypeInt* limit_t = gvn->type(limit)->is_int();
429
430 if (stride_con > 0) {
431 jlong init_p = (jlong)init_t->_lo + stride_con;
432 if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
433 return false; // cyclic loop or this loop trips only once
434 } else {
435 jlong init_p = (jlong)init_t->_hi + stride_con;
436 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
437 return false; // cyclic loop or this loop trips only once
438 }
439
440 // =================================================
441 // ---- SUCCESS! Found A Trip-Counted Loop! -----
442 //
443 assert(x->Opcode() == Op_Loop, "regular loops only");
444 C->print_method(PHASE_BEFORE_CLOOPS, 3);
445
446 Node *hook = new Node(6);
447
448 if (LoopLimitCheck) {
449
450 // ===================================================
451 // Generate loop limit check to avoid integer overflow
452 // in cases like next (cyclic loops):
453 //
454 // for (i=0; i <= max_jint; i++) {}
455 // for (i=0; i < max_jint; i+=2) {}
456 //
457 //
458 // Limit check predicate depends on the loop test:
459 //
460 // for(;i != limit; i++) --> limit <= (max_jint)
461 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
462 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
463 //
464
465 // Check if limit is excluded to do more precise int overflow check.
466 bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge);
489 // Generate loop's limit check.
490 // Loop limit check predicate should be near the loop.
491 ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);
492 if (!limit_check_proj) {
493 // The limit check predicate is not generated if this method trapped here before.
494 #ifdef ASSERT
495 if (TraceLoopLimitCheck) {
496 tty->print("missing loop limit check:");
497 loop->dump_head();
498 x->dump(1);
499 }
500 #endif
501 return false;
502 }
503
504 IfNode* check_iff = limit_check_proj->in(0)->as_If();
505 Node* cmp_limit;
506 Node* bol;
507
508 if (stride_con > 0) {
509 cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
510 bol = new BoolNode(cmp_limit, BoolTest::le);
511 } else {
512 cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
513 bol = new BoolNode(cmp_limit, BoolTest::ge);
514 }
515 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
516 bol = _igvn.register_new_node_with_optimizer(bol);
517 set_subtree_ctrl(bol);
518
519 // Replace condition in original predicate but preserve Opaque node
520 // so that previous predicates could be found.
521 assert(check_iff->in(1)->Opcode() == Op_Conv2B &&
522 check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");
523 Node* opq = check_iff->in(1)->in(1);
524 _igvn.hash_delete(opq);
525 opq->set_req(1, bol);
526 // Update ctrl.
527 set_ctrl(opq, check_iff->in(0));
528 set_ctrl(check_iff->in(1), check_iff->in(0));
529
530 #ifndef PRODUCT
531 // report that the loop predication has been actually performed
532 // for this loop
533 if (TraceLoopLimitCheck) {
534 tty->print_cr("Counted Loop Limit Check generated:");
535 debug_only( bol->dump(2); )
536 }
537 #endif
538 }
539
540 if (phi_incr != NULL) {
541 // If compare points directly to the phi we need to adjust
542 // the compare so that it points to the incr. Limit have
543 // to be adjusted to keep trip count the same and we
544 // should avoid int overflow.
545 //
546 // i = init; do {} while(i++ < limit);
547 // is converted to
548 // i = init; do {} while(++i < limit+1);
549 //
550 limit = gvn->transform(new AddINode(limit, stride));
551 }
552
553 // Now we need to canonicalize loop condition.
554 if (bt == BoolTest::ne) {
555 assert(stride_con == 1 || stride_con == -1, "simple increment only");
556 // 'ne' can be replaced with 'lt' only when init < limit.
557 if (stride_con > 0 && init_t->_hi < limit_t->_lo)
558 bt = BoolTest::lt;
559 // 'ne' can be replaced with 'gt' only when init > limit.
560 if (stride_con < 0 && init_t->_lo > limit_t->_hi)
561 bt = BoolTest::gt;
562 }
563
564 if (incl_limit) {
565 // The limit check guaranties that 'limit <= (max_jint - stride)' so
566 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
567 //
568 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
569 limit = gvn->transform(new AddINode(limit, one));
570 if (bt == BoolTest::le)
571 bt = BoolTest::lt;
572 else if (bt == BoolTest::ge)
573 bt = BoolTest::gt;
574 else
575 ShouldNotReachHere();
576 }
577 set_subtree_ctrl( limit );
578
579 } else { // LoopLimitCheck
580
581 // If compare points to incr, we are ok. Otherwise the compare
582 // can directly point to the phi; in this case adjust the compare so that
583 // it points to the incr by adjusting the limit.
584 if (cmp->in(1) == phi || cmp->in(2) == phi)
585 limit = gvn->transform(new AddINode(limit,stride));
586
587 // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.
588 // Final value for iterator should be: trip_count * stride + init_trip.
589 Node *one_p = gvn->intcon( 1);
590 Node *one_m = gvn->intcon(-1);
591
592 Node *trip_count = NULL;
593 switch( bt ) {
594 case BoolTest::eq:
595 ShouldNotReachHere();
596 case BoolTest::ne: // Ahh, the case we desire
597 if (stride_con == 1)
598 trip_count = gvn->transform(new SubINode(limit,init_trip));
599 else if (stride_con == -1)
600 trip_count = gvn->transform(new SubINode(init_trip,limit));
601 else
602 ShouldNotReachHere();
603 set_subtree_ctrl(trip_count);
604 //_loop.map(trip_count->_idx,loop(limit));
605 break;
606 case BoolTest::le: // Maybe convert to '<' case
607 limit = gvn->transform(new AddINode(limit,one_p));
608 set_subtree_ctrl( limit );
609 hook->init_req(4, limit);
610
611 bt = BoolTest::lt;
612 // Make the new limit be in the same loop nest as the old limit
613 //_loop.map(limit->_idx,limit_loop);
614 // Fall into next case
615 case BoolTest::lt: { // Maybe convert to '!=' case
616 if (stride_con < 0) // Count down loop rolls through MAXINT
617 ShouldNotReachHere();
618 Node *range = gvn->transform(new SubINode(limit,init_trip));
619 set_subtree_ctrl( range );
620 hook->init_req(0, range);
621
622 Node *bias = gvn->transform(new AddINode(range,stride));
623 set_subtree_ctrl( bias );
624 hook->init_req(1, bias);
625
626 Node *bias1 = gvn->transform(new AddINode(bias,one_m));
627 set_subtree_ctrl( bias1 );
628 hook->init_req(2, bias1);
629
630 trip_count = gvn->transform(new DivINode(0,bias1,stride));
631 set_subtree_ctrl( trip_count );
632 hook->init_req(3, trip_count);
633 break;
634 }
635
636 case BoolTest::ge: // Maybe convert to '>' case
637 limit = gvn->transform(new AddINode(limit,one_m));
638 set_subtree_ctrl( limit );
639 hook->init_req(4 ,limit);
640
641 bt = BoolTest::gt;
642 // Make the new limit be in the same loop nest as the old limit
643 //_loop.map(limit->_idx,limit_loop);
644 // Fall into next case
645 case BoolTest::gt: { // Maybe convert to '!=' case
646 if (stride_con > 0) // count up loop rolls through MININT
647 ShouldNotReachHere();
648 Node *range = gvn->transform(new SubINode(limit,init_trip));
649 set_subtree_ctrl( range );
650 hook->init_req(0, range);
651
652 Node *bias = gvn->transform(new AddINode(range,stride));
653 set_subtree_ctrl( bias );
654 hook->init_req(1, bias);
655
656 Node *bias1 = gvn->transform(new AddINode(bias,one_p));
657 set_subtree_ctrl( bias1 );
658 hook->init_req(2, bias1);
659
660 trip_count = gvn->transform(new DivINode(0,bias1,stride));
661 set_subtree_ctrl( trip_count );
662 hook->init_req(3, trip_count);
663 break;
664 }
665 } // switch( bt )
666
667 Node *span = gvn->transform(new MulINode(trip_count,stride));
668 set_subtree_ctrl( span );
669 hook->init_req(5, span);
670
671 limit = gvn->transform(new AddINode(span,init_trip));
672 set_subtree_ctrl( limit );
673
674 } // LoopLimitCheck
675
676 // Check for SafePoint on backedge and remove
677 Node *sfpt = x->in(LoopNode::LoopBackControl);
678 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
679 lazy_replace( sfpt, iftrue );
680 if (loop->_safepts != NULL) {
681 loop->_safepts->yank(sfpt);
682 }
683 loop->_tail = iftrue;
684 }
685
686 // Build a canonical trip test.
687 // Clone code, as old values may be in use.
688 incr = incr->clone();
689 incr->set_req(1,phi);
690 incr->set_req(2,stride);
691 incr = _igvn.register_new_node_with_optimizer(incr);
700 Node* nphi = PhiNode::make(phi->in(0), phi->in(LoopNode::EntryControl), TypeInt::INT);
701 nphi->set_req(LoopNode::LoopBackControl, phi->in(LoopNode::LoopBackControl));
702 nphi = _igvn.register_new_node_with_optimizer(nphi);
703 set_ctrl(nphi, get_ctrl(phi));
704 _igvn.replace_node(phi, nphi);
705 phi = nphi->as_Phi();
706 }
707 cmp = cmp->clone();
708 cmp->set_req(1,incr);
709 cmp->set_req(2,limit);
710 cmp = _igvn.register_new_node_with_optimizer(cmp);
711 set_ctrl(cmp, iff->in(0));
712
713 test = test->clone()->as_Bool();
714 (*(BoolTest*)&test->_test)._test = bt;
715 test->set_req(1,cmp);
716 _igvn.register_new_node_with_optimizer(test);
717 set_ctrl(test, iff->in(0));
718
719 // Replace the old IfNode with a new LoopEndNode
720 Node *lex = _igvn.register_new_node_with_optimizer(new CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt ));
721 IfNode *le = lex->as_If();
722 uint dd = dom_depth(iff);
723 set_idom(le, le->in(0), dd); // Update dominance for loop exit
724 set_loop(le, loop);
725
726 // Get the loop-exit control
727 Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue));
728
729 // Need to swap loop-exit and loop-back control?
730 if (iftrue_op == Op_IfFalse) {
731 Node *ift2=_igvn.register_new_node_with_optimizer(new IfTrueNode (le));
732 Node *iff2=_igvn.register_new_node_with_optimizer(new IfFalseNode(le));
733
734 loop->_tail = back_control = ift2;
735 set_loop(ift2, loop);
736 set_loop(iff2, get_loop(iffalse));
737
738 // Lazy update of 'get_ctrl' mechanism.
739 lazy_replace_proj( iffalse, iff2 );
740 lazy_replace_proj( iftrue, ift2 );
741
742 // Swap names
743 iffalse = iff2;
744 iftrue = ift2;
745 } else {
746 _igvn.hash_delete(iffalse);
747 _igvn.hash_delete(iftrue);
748 iffalse->set_req_X( 0, le, &_igvn );
749 iftrue ->set_req_X( 0, le, &_igvn );
750 }
751
752 set_idom(iftrue, le, dd+1);
753 set_idom(iffalse, le, dd+1);
754 assert(iff->outcnt() == 0, "should be dead now");
755 lazy_replace( iff, le ); // fix 'get_ctrl'
756
757 // Now setup a new CountedLoopNode to replace the existing LoopNode
758 CountedLoopNode *l = new CountedLoopNode(init_control, back_control);
759 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve
760 // The following assert is approximately true, and defines the intention
761 // of can_be_counted_loop. It fails, however, because phase->type
762 // is not yet initialized for this loop and its parts.
763 //assert(l->can_be_counted_loop(this), "sanity");
764 _igvn.register_new_node_with_optimizer(l);
765 set_loop(l, loop);
766 loop->_head = l;
767 // Fix all data nodes placed at the old loop head.
768 // Uses the lazy-update mechanism of 'get_ctrl'.
769 lazy_replace( x, l );
770 set_idom(l, init_control, dom_depth(x));
771
772 // Check for immediately preceding SafePoint and remove
773 Node *sfpt2 = le->in(0);
774 if (sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2)) {
775 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
776 if (loop->_safepts != NULL) {
777 loop->_safepts->yank(sfpt2);
778 }
812 Node *limit = NULL;
813 #ifdef ASSERT
814 BoolTest::mask bt = cl->loopexit()->test_trip();
815 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
816 #endif
817 if (cl->has_exact_trip_count()) {
818 // Simple case: loop has constant boundaries.
819 // Use jlongs to avoid integer overflow.
820 int stride_con = cl->stride_con();
821 jlong init_con = cl->init_trip()->get_int();
822 jlong limit_con = cl->limit()->get_int();
823 julong trip_cnt = cl->trip_count();
824 jlong final_con = init_con + trip_cnt*stride_con;
825 int final_int = (int)final_con;
826 // The final value should be in integer range since the loop
827 // is counted and the limit was checked for overflow.
828 assert(final_con == (jlong)final_int, "final value should be integer");
829 limit = _igvn.intcon(final_int);
830 } else {
831 // Create new LoopLimit node to get exact limit (final iv value).
832 limit = new LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride());
833 register_new_node(limit, cl->in(LoopNode::EntryControl));
834 }
835 assert(limit != NULL, "sanity");
836 return limit;
837 }
838
839 //------------------------------Ideal------------------------------------------
840 // Return a node which is more "ideal" than the current node.
841 // Attempt to convert into a counted-loop.
842 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
843 if (!can_be_counted_loop(phase)) {
844 phase->C->set_major_progress();
845 }
846 return RegionNode::Ideal(phase, can_reshape);
847 }
848
849
850 //=============================================================================
851 //------------------------------Ideal------------------------------------------
852 // Return a node which is more "ideal" than the current node.
929 const TypeInt* init_t = phase->type(in(Init) )->is_int();
930 const TypeInt* limit_t = phase->type(in(Limit))->is_int();
931 int stride_p;
932 jlong lim, ini;
933 julong max;
934 if (stride_con > 0) {
935 stride_p = stride_con;
936 lim = limit_t->_hi;
937 ini = init_t->_lo;
938 max = (julong)max_jint;
939 } else {
940 stride_p = -stride_con;
941 lim = init_t->_hi;
942 ini = limit_t->_lo;
943 max = (julong)min_jint;
944 }
945 julong range = lim - ini + stride_p;
946 if (range <= max) {
947 // Convert to integer expression if it is not overflow.
948 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
949 Node *range = phase->transform(new SubINode(in(Limit), in(Init)));
950 Node *bias = phase->transform(new AddINode(range, stride_m));
951 Node *trip = phase->transform(new DivINode(0, bias, in(Stride)));
952 Node *span = phase->transform(new MulINode(trip, in(Stride)));
953 return new AddINode(span, in(Init)); // exact limit
954 }
955
956 if (is_power_of_2(stride_p) || // divisor is 2^n
957 !Matcher::has_match_rule(Op_LoopLimit)) { // or no specialized Mach node?
958 // Convert to long expression to avoid integer overflow
959 // and let igvn optimizer convert this division.
960 //
961 Node* init = phase->transform( new ConvI2LNode(in(Init)));
962 Node* limit = phase->transform( new ConvI2LNode(in(Limit)));
963 Node* stride = phase->longcon(stride_con);
964 Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1));
965
966 Node *range = phase->transform(new SubLNode(limit, init));
967 Node *bias = phase->transform(new AddLNode(range, stride_m));
968 Node *span;
969 if (stride_con > 0 && is_power_of_2(stride_p)) {
970 // bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride)
971 // and avoid generating rounding for division. Zero trip guard should
972 // guarantee that init < limit but sometimes the guard is missing and
973 // we can get situation when init > limit. Note, for the empty loop
974 // optimization zero trip guard is generated explicitly which leaves
975 // only RCE predicate where exact limit is used and the predicate
976 // will simply fail forcing recompilation.
977 Node* neg_stride = phase->longcon(-stride_con);
978 span = phase->transform(new AndLNode(bias, neg_stride));
979 } else {
980 Node *trip = phase->transform(new DivLNode(0, bias, stride));
981 span = phase->transform(new MulLNode(trip, stride));
982 }
983 // Convert back to int
984 Node *span_int = phase->transform(new ConvL2INode(span));
985 return new AddINode(span_int, in(Init)); // exact limit
986 }
987
988 return NULL; // No progress
989 }
990
991 //------------------------------Identity---------------------------------------
992 // If stride == 1 return limit node.
993 Node *LoopLimitNode::Identity( PhaseTransform *phase ) {
994 int stride_con = phase->type(in(Stride))->is_int()->get_con();
995 if (stride_con == 1 || stride_con == -1)
996 return in(Limit);
997 return this;
998 }
999
1000 //=============================================================================
1001 //----------------------match_incr_with_optional_truncation--------------------
1002 // Match increment with optional truncation:
1003 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
1004 // Return NULL for failure. Success returns the increment node.
1005 Node* CountedLoopNode::match_incr_with_optional_truncation(
1171
1172 //------------------------------set_nest---------------------------------------
1173 // Set loop tree nesting depth. Accumulate _has_call bits.
1174 int IdealLoopTree::set_nest( uint depth ) {
1175 _nest = depth;
1176 int bits = _has_call;
1177 if( _child ) bits |= _child->set_nest(depth+1);
1178 if( bits ) _has_call = 1;
1179 if( _next ) bits |= _next ->set_nest(depth );
1180 return bits;
1181 }
1182
1183 //------------------------------split_fall_in----------------------------------
1184 // Split out multiple fall-in edges from the loop header. Move them to a
1185 // private RegionNode before the loop. This becomes the loop landing pad.
1186 void IdealLoopTree::split_fall_in( PhaseIdealLoop *phase, int fall_in_cnt ) {
1187 PhaseIterGVN &igvn = phase->_igvn;
1188 uint i;
1189
1190 // Make a new RegionNode to be the landing pad.
1191 Node *landing_pad = new RegionNode( fall_in_cnt+1 );
1192 phase->set_loop(landing_pad,_parent);
1193 // Gather all the fall-in control paths into the landing pad
1194 uint icnt = fall_in_cnt;
1195 uint oreq = _head->req();
1196 for( i = oreq-1; i>0; i-- )
1197 if( !phase->is_member( this, _head->in(i) ) )
1198 landing_pad->set_req(icnt--,_head->in(i));
1199
1200 // Peel off PhiNode edges as well
1201 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1202 Node *oj = _head->fast_out(j);
1203 if( oj->is_Phi() ) {
1204 PhiNode* old_phi = oj->as_Phi();
1205 assert( old_phi->region() == _head, "" );
1206 igvn.hash_delete(old_phi); // Yank from hash before hacking edges
1207 Node *p = PhiNode::make_blank(landing_pad, old_phi);
1208 uint icnt = fall_in_cnt;
1209 for( i = oreq-1; i>0; i-- ) {
1210 if( !phase->is_member( this, _head->in(i) ) ) {
1211 p->init_req(icnt--, old_phi->in(i));
1257 _head->del_req(i);
1258 }
1259 }
1260 // Transform landing pad
1261 igvn.register_new_node_with_optimizer(landing_pad, _head);
1262 // Insert landing pad into the header
1263 _head->add_req(landing_pad);
1264 }
1265
1266 //------------------------------split_outer_loop-------------------------------
1267 // Split out the outermost loop from this shared header.
1268 void IdealLoopTree::split_outer_loop( PhaseIdealLoop *phase ) {
1269 PhaseIterGVN &igvn = phase->_igvn;
1270
1271 // Find index of outermost loop; it should also be my tail.
1272 uint outer_idx = 1;
1273 while( _head->in(outer_idx) != _tail ) outer_idx++;
1274
1275 // Make a LoopNode for the outermost loop.
1276 Node *ctl = _head->in(LoopNode::EntryControl);
1277 Node *outer = new LoopNode( ctl, _head->in(outer_idx) );
1278 outer = igvn.register_new_node_with_optimizer(outer, _head);
1279 phase->set_created_loop_node();
1280
1281 // Outermost loop falls into '_head' loop
1282 _head->set_req(LoopNode::EntryControl, outer);
1283 _head->del_req(outer_idx);
1284 // Split all the Phis up between '_head' loop and 'outer' loop.
1285 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1286 Node *out = _head->fast_out(j);
1287 if( out->is_Phi() ) {
1288 PhiNode *old_phi = out->as_Phi();
1289 assert( old_phi->region() == _head, "" );
1290 Node *phi = PhiNode::make_blank(outer, old_phi);
1291 phi->init_req(LoopNode::EntryControl, old_phi->in(LoopNode::EntryControl));
1292 phi->init_req(LoopNode::LoopBackControl, old_phi->in(outer_idx));
1293 phi = igvn.register_new_node_with_optimizer(phi, old_phi);
1294 // Make old Phi point to new Phi on the fall-in path
1295 igvn.replace_input_of(old_phi, LoopNode::EntryControl, phi);
1296 old_phi->del_req(outer_idx);
1297 }
1371 if( cnt > hotcnt ) { // Grab hottest path
1372 warmcnt = hotcnt;
1373 hotcnt = cnt;
1374 hot_idx = i;
1375 } else if( cnt > warmcnt ) { // And 2nd hottest path
1376 warmcnt = cnt;
1377 }
1378 }
1379
1380 // See if the hottest backedge is worthy of being an inner loop
1381 // by being much hotter than the next hottest backedge.
1382 if( hotcnt <= 0.0001 ||
1383 hotcnt < 2.0*warmcnt ) hot_idx = 0;// No hot backedge
1384
1385 // Peel out the backedges into a private merge point; peel
1386 // them all except optionally hot_idx.
1387 PhaseIterGVN &igvn = phase->_igvn;
1388
1389 Node *hot_tail = NULL;
1390 // Make a Region for the merge point
1391 Node *r = new RegionNode(1);
1392 for( i = 2; i < _head->req(); i++ ) {
1393 if( i != hot_idx )
1394 r->add_req( _head->in(i) );
1395 else hot_tail = _head->in(i);
1396 }
1397 igvn.register_new_node_with_optimizer(r, _head);
1398 // Plug region into end of loop _head, followed by hot_tail
1399 while( _head->req() > 3 ) _head->del_req( _head->req()-1 );
1400 _head->set_req(2, r);
1401 if( hot_idx ) _head->add_req(hot_tail);
1402
1403 // Split all the Phis up between '_head' loop and the Region 'r'
1404 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) {
1405 Node *out = _head->fast_out(j);
1406 if( out->is_Phi() ) {
1407 PhiNode* n = out->as_Phi();
1408 igvn.hash_delete(n); // Delete from hash before hacking edges
1409 Node *hot_phi = NULL;
1410 Node *phi = new PhiNode(r, n->type(), n->adr_type());
1411 // Check all inputs for the ones to peel out
1412 uint j = 1;
1413 for( uint i = 2; i < n->req(); i++ ) {
1414 if( i != hot_idx )
1415 phi->set_req( j++, n->in(i) );
1416 else hot_phi = n->in(i);
1417 }
1418 // Register the phi but do not transform until whole place transforms
1419 igvn.register_new_node_with_optimizer(phi, n);
1420 // Add the merge phi to the old Phi
1421 while( n->req() > 3 ) n->del_req( n->req()-1 );
1422 n->set_req(2, phi);
1423 if( hot_idx ) n->add_req(hot_phi);
1424 }
1425 }
1426
1427
1428 // Insert a new IdealLoopTree inserted below me. Turn it into a clone
1429 // of self loop tree. Turn self into a loop headed by _head and with
1430 // tail being the new merge point.
1512 assert( phase->is_member( this, _head->in(2) ), "right edge is loop" );
1513
1514 // If I am a shared header (multiple backedges), peel off the many
1515 // backedges into a private merge point and use the merge point as
1516 // the one true backedge.
1517 if( _head->req() > 3 ) {
1518 // Merge the many backedges into a single backedge but leave
1519 // the hottest backedge as separate edge for the following peel.
1520 merge_many_backedges( phase );
1521 result = true;
1522 }
1523
1524 // If I have one hot backedge, peel off myself loop.
1525 // I better be the outermost loop.
1526 if (_head->req() > 3 && !_irreducible) {
1527 split_outer_loop( phase );
1528 result = true;
1529
1530 } else if (!_head->is_Loop() && !_irreducible) {
1531 // Make a new LoopNode to replace the old loop head
1532 Node *l = new LoopNode( _head->in(1), _head->in(2) );
1533 l = igvn.register_new_node_with_optimizer(l, _head);
1534 phase->set_created_loop_node();
1535 // Go ahead and replace _head
1536 phase->_igvn.replace_node( _head, l );
1537 _head = l;
1538 phase->set_loop(_head, this);
1539 }
1540
1541 // Now recursively beautify nested loops
1542 if( _child ) result |= _child->beautify_loops( phase );
1543 if( _next ) result |= _next ->beautify_loops( phase );
1544 return result;
1545 }
1546
1547 //------------------------------allpaths_check_safepts----------------------------
1548 // Allpaths backwards scan from loop tail, terminating each path at first safepoint
1549 // encountered. Helper for check_safepts.
1550 void IdealLoopTree::allpaths_check_safepts(VectorSet &visited, Node_List &stack) {
1551 assert(stack.size() == 0, "empty stack");
1552 stack.push(_tail);
1754 // GCD for the loop. Then all possible IVs are simple multiples of
1755 // the GCD. In practice, this will cover very few extra loops.
1756 // Instead we require 'stride_con2' to be a multiple of 'stride_con',
1757 // where +/-1 is the common case, but other integer multiples are
1758 // also easy to handle.
1759 int ratio_con = stride_con2/stride_con;
1760
1761 if ((ratio_con * stride_con) == stride_con2) { // Check for exact
1762 #ifndef PRODUCT
1763 if (TraceLoopOpts) {
1764 tty->print("Parallel IV: %d ", phi2->_idx);
1765 loop->dump_head();
1766 }
1767 #endif
1768 // Convert to using the trip counter. The parallel induction
1769 // variable differs from the trip counter by a loop-invariant
1770 // amount, the difference between their respective initial values.
1771 // It is scaled by the 'ratio_con'.
1772 Node* ratio = _igvn.intcon(ratio_con);
1773 set_ctrl(ratio, C->root());
1774 Node* ratio_init = new MulINode(init, ratio);
1775 _igvn.register_new_node_with_optimizer(ratio_init, init);
1776 set_early_ctrl(ratio_init);
1777 Node* diff = new SubINode(init2, ratio_init);
1778 _igvn.register_new_node_with_optimizer(diff, init2);
1779 set_early_ctrl(diff);
1780 Node* ratio_idx = new MulINode(phi, ratio);
1781 _igvn.register_new_node_with_optimizer(ratio_idx, phi);
1782 set_ctrl(ratio_idx, cl);
1783 Node* add = new AddINode(ratio_idx, diff);
1784 _igvn.register_new_node_with_optimizer(add);
1785 set_ctrl(add, cl);
1786 _igvn.replace_node( phi2, add );
1787 // Sometimes an induction variable is unused
1788 if (add->outcnt() == 0) {
1789 _igvn.remove_dead_node(add);
1790 }
1791 --i; // deleted this phi; rescan starting with next position
1792 continue;
1793 }
1794 }
1795 }
1796
1797 //------------------------------counted_loop-----------------------------------
1798 // Convert to counted loops where possible
1799 void IdealLoopTree::counted_loop( PhaseIdealLoop *phase ) {
1800
1801 // For grins, set the inner-loop flag here
1802 if (!_child) {
1803 if (_head->is_Loop()) _head->as_Loop()->set_inner_loop();
2871 // at most 1 level.
2872 while( l && l->_head == m ) // Successor heads loop?
2873 l = l->_parent; // Move up 1 for me
2874 // If this loop is not properly parented, then this loop
2875 // has no exit path out, i.e. its an infinite loop.
2876 if( !l ) {
2877 // Make loop "reachable" from root so the CFG is reachable. Basically
2878 // insert a bogus loop exit that is never taken. 'm', the loop head,
2879 // points to 'n', one (of possibly many) fall-in paths. There may be
2880 // many backedges as well.
2881
2882 // Here I set the loop to be the root loop. I could have, after
2883 // inserting a bogus loop exit, restarted the recursion and found my
2884 // new loop exit. This would make the infinite loop a first-class
2885 // loop and it would then get properly optimized. What's the use of
2886 // optimizing an infinite loop?
2887 l = _ltree_root; // Oops, found infinite loop
2888
2889 if (!_verify_only) {
2890 // Insert the NeverBranch between 'm' and it's control user.
2891 NeverBranchNode *iff = new NeverBranchNode( m );
2892 _igvn.register_new_node_with_optimizer(iff);
2893 set_loop(iff, l);
2894 Node *if_t = new CProjNode( iff, 0 );
2895 _igvn.register_new_node_with_optimizer(if_t);
2896 set_loop(if_t, l);
2897
2898 Node* cfg = NULL; // Find the One True Control User of m
2899 for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) {
2900 Node* x = m->fast_out(j);
2901 if (x->is_CFG() && x != m && x != iff)
2902 { cfg = x; break; }
2903 }
2904 assert(cfg != NULL, "must find the control user of m");
2905 uint k = 0; // Probably cfg->in(0)
2906 while( cfg->in(k) != m ) k++; // But check incase cfg is a Region
2907 cfg->set_req( k, if_t ); // Now point to NeverBranch
2908
2909 // Now create the never-taken loop exit
2910 Node *if_f = new CProjNode( iff, 1 );
2911 _igvn.register_new_node_with_optimizer(if_f);
2912 set_loop(if_f, l);
2913 // Find frame ptr for Halt. Relies on the optimizer
2914 // V-N'ing. Easier and quicker than searching through
2915 // the program structure.
2916 Node *frame = new ParmNode( C->start(), TypeFunc::FramePtr );
2917 _igvn.register_new_node_with_optimizer(frame);
2918 // Halt & Catch Fire
2919 Node *halt = new HaltNode( if_f, frame );
2920 _igvn.register_new_node_with_optimizer(halt);
2921 set_loop(halt, l);
2922 C->root()->add_req(halt);
2923 }
2924 set_loop(C->root(), _ltree_root);
2925 }
2926 }
2927 // Weeny check for irreducible. This child was already visited (this
2928 // IS the post-work phase). Is this child's loop header post-visited
2929 // as well? If so, then I found another entry into the loop.
2930 if (!_verify_only) {
2931 while( is_postvisited(l->_head) ) {
2932 // found irreducible
2933 l->_irreducible = 1; // = true
2934 l = l->_parent;
2935 _has_irreducible_loops = true;
2936 // Check for bad CFG here to prevent crash, and bailout of compile
2937 if (l == NULL) {
2938 C->record_method_not_compilable("unhandled CFG detected during loop optimization");
2939 return pre_order;
|