56 //=============================================================================
57 //------------------------------dump_spec--------------------------------------
58 // Dump special per-node info
59 #ifndef PRODUCT
60 void LoopNode::dump_spec(outputStream *st) const {
61 if (is_inner_loop()) st->print( "inner " );
62 if (is_partial_peel_loop()) st->print( "partial_peel " );
63 if (partial_peel_has_failed()) st->print( "partial_peel_failed " );
64 }
65 #endif
66
67 //------------------------------is_valid_counted_loop-------------------------
68 bool LoopNode::is_valid_counted_loop() const {
69 if (is_CountedLoop()) {
70 CountedLoopNode* l = as_CountedLoop();
71 CountedLoopEndNode* le = l->loopexit();
72 if (le != NULL &&
73 le->proj_out(1 /* true */) == l->in(LoopNode::LoopBackControl)) {
74 Node* phi = l->phi();
75 Node* exit = le->proj_out(0 /* false */);
76 if (exit != NULL && exit->Opcode() == Op_IfFalse &&
77 phi != NULL && phi->is_Phi() &&
78 phi->in(LoopNode::LoopBackControl) == l->incr() &&
79 le->loopnode() == l && le->stride_is_con()) {
80 return true;
81 }
82 }
83 }
84 return false;
85 }
86
87 //------------------------------get_early_ctrl---------------------------------
88 // Compute earliest legal control
89 Node *PhaseIdealLoop::get_early_ctrl( Node *n ) {
90 assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" );
91 uint i;
92 Node *early;
93 if (n->in(0) && !n->is_expensive()) {
94 early = n->in(0);
95 if (!early->is_CFG()) // Might be a non-CFG multi-def
96 early = get_ctrl(early); // So treat input as a straight data input
262 }
263
264 //------------------------------is_counted_loop--------------------------------
265 bool PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) {
266 PhaseGVN *gvn = &_igvn;
267
268 // Counted loop head must be a good RegionNode with only 3 not NULL
269 // control input edges: Self, Entry, LoopBack.
270 if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {
271 return false;
272 }
273 Node *init_control = x->in(LoopNode::EntryControl);
274 Node *back_control = x->in(LoopNode::LoopBackControl);
275 if (init_control == NULL || back_control == NULL) // Partially dead
276 return false;
277 // Must also check for TOP when looking for a dead loop
278 if (init_control->is_top() || back_control->is_top())
279 return false;
280
281 // Allow funny placement of Safepoint
282 if (back_control->Opcode() == Op_SafePoint)
283 back_control = back_control->in(TypeFunc::Control);
284
285 // Controlling test for loop
286 Node *iftrue = back_control;
287 uint iftrue_op = iftrue->Opcode();
288 if (iftrue_op != Op_IfTrue &&
289 iftrue_op != Op_IfFalse)
290 // I have a weird back-control. Probably the loop-exit test is in
291 // the middle of the loop and I am looking at some trailing control-flow
292 // merge point. To fix this I would have to partially peel the loop.
293 return false; // Obscure back-control
294
295 // Get boolean guarding loop-back test
296 Node *iff = iftrue->in(0);
297 if (get_loop(iff) != loop || !iff->in(1)->is_Bool())
298 return false;
299 BoolNode *test = iff->in(1)->as_Bool();
300 BoolTest::mask bt = test->_test._test;
301 float cl_prob = iff->as_If()->_prob;
302 if (iftrue_op == Op_IfFalse) {
303 bt = BoolTest(bt).negate();
304 cl_prob = 1.0 - cl_prob;
305 }
306 // Get backedge compare
307 Node *cmp = test->in(1);
308 int cmp_op = cmp->Opcode();
309 if (cmp_op != Op_CmpI)
310 return false; // Avoid pointer & float compares
311
312 // Find the trip-counter increment & limit. Limit must be loop invariant.
313 Node *incr = cmp->in(1);
314 Node *limit = cmp->in(2);
315
316 // ---------
317 // need 'loop()' test to tell if limit is loop invariant
318 // ---------
319
320 if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?
321 Node *tmp = incr; // Then reverse order into the CmpI
322 incr = limit;
323 limit = tmp;
324 bt = BoolTest(bt).commute(); // And commute the exit test
325 }
326 if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant
327 return false;
328 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
329 return false;
330
331 Node* phi_incr = NULL;
332 // Trip-counter increment must be commutative & associative.
333 if (incr->Opcode() == Op_CastII) {
334 incr = incr->in(1);
335 }
336 if (incr->is_Phi()) {
337 if (incr->as_Phi()->region() != x || incr->req() != 3)
338 return false; // Not simple trip counter expression
339 phi_incr = incr;
340 incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi
341 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
342 return false;
343 }
344
345 Node* trunc1 = NULL;
346 Node* trunc2 = NULL;
347 const TypeInt* iv_trunc_t = NULL;
348 if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {
349 return false; // Funny increment opcode
350 }
351 assert(incr->Opcode() == Op_AddI, "wrong increment code");
352
353 // Get merge point
354 Node *xphi = incr->in(1);
355 Node *stride = incr->in(2);
356 if (!stride->is_Con()) { // Oops, swap these
357 if (!xphi->is_Con()) // Is the other guy a constant?
358 return false; // Nope, unknown stride, bail out
359 Node *tmp = xphi; // 'incr' is commutative, so ok to swap
360 xphi = stride;
361 stride = tmp;
362 }
363 if (xphi->Opcode() == Op_CastII) {
364 xphi = xphi->in(1);
365 }
366 // Stride must be constant
367 int stride_con = stride->get_int();
368 if (stride_con == 0)
369 return false; // missed some peephole opt
370
371 if (!xphi->is_Phi())
372 return false; // Too much math on the trip counter
373 if (phi_incr != NULL && phi_incr != xphi)
374 return false;
375 PhiNode *phi = xphi->as_Phi();
376
377 // Phi must be of loop header; backedge must wrap to increment
378 if (phi->region() != x)
379 return false;
380 if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr ||
381 trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) {
382 return false;
383 }
442 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
443 return false; // cyclic loop or this loop trips only once
444 }
445
446 if (phi_incr != NULL) {
447 // check if there is a possiblity of IV overflowing after the first increment
448 if (stride_con > 0) {
449 if (init_t->_hi > max_jint - stride_con) {
450 return false;
451 }
452 } else {
453 if (init_t->_lo < min_jint - stride_con) {
454 return false;
455 }
456 }
457 }
458
459 // =================================================
460 // ---- SUCCESS! Found A Trip-Counted Loop! -----
461 //
462 assert(x->Opcode() == Op_Loop, "regular loops only");
463 C->print_method(PHASE_BEFORE_CLOOPS, 3);
464
465 Node *hook = new Node(6);
466
467 // ===================================================
468 // Generate loop limit check to avoid integer overflow
469 // in cases like next (cyclic loops):
470 //
471 // for (i=0; i <= max_jint; i++) {}
472 // for (i=0; i < max_jint; i+=2) {}
473 //
474 //
475 // Limit check predicate depends on the loop test:
476 //
477 // for(;i != limit; i++) --> limit <= (max_jint)
478 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
479 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
480 //
481
482 // Check if limit is excluded to do more precise int overflow check.
518 return false;
519 }
520
521 IfNode* check_iff = limit_check_proj->in(0)->as_If();
522 Node* cmp_limit;
523 Node* bol;
524
525 if (stride_con > 0) {
526 cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
527 bol = new BoolNode(cmp_limit, BoolTest::le);
528 } else {
529 cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
530 bol = new BoolNode(cmp_limit, BoolTest::ge);
531 }
532 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
533 bol = _igvn.register_new_node_with_optimizer(bol);
534 set_subtree_ctrl(bol);
535
536 // Replace condition in original predicate but preserve Opaque node
537 // so that previous predicates could be found.
538 assert(check_iff->in(1)->Opcode() == Op_Conv2B &&
539 check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");
540 Node* opq = check_iff->in(1)->in(1);
541 _igvn.replace_input_of(opq, 1, bol);
542 // Update ctrl.
543 set_ctrl(opq, check_iff->in(0));
544 set_ctrl(check_iff->in(1), check_iff->in(0));
545
546 #ifndef PRODUCT
547 // report that the loop predication has been actually performed
548 // for this loop
549 if (TraceLoopLimitCheck) {
550 tty->print_cr("Counted Loop Limit Check generated:");
551 debug_only( bol->dump(2); )
552 }
553 #endif
554 }
555
556 if (phi_incr != NULL) {
557 // If compare points directly to the phi we need to adjust
558 // the compare so that it points to the incr. Limit have
559 // to be adjusted to keep trip count the same and we
578 }
579
580 if (incl_limit) {
581 // The limit check guaranties that 'limit <= (max_jint - stride)' so
582 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
583 //
584 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
585 limit = gvn->transform(new AddINode(limit, one));
586 if (bt == BoolTest::le)
587 bt = BoolTest::lt;
588 else if (bt == BoolTest::ge)
589 bt = BoolTest::gt;
590 else
591 ShouldNotReachHere();
592 }
593 set_subtree_ctrl( limit );
594
595 if (!UseCountedLoopSafepoints) {
596 // Check for SafePoint on backedge and remove
597 Node *sfpt = x->in(LoopNode::LoopBackControl);
598 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
599 lazy_replace( sfpt, iftrue );
600 if (loop->_safepts != NULL) {
601 loop->_safepts->yank(sfpt);
602 }
603 loop->_tail = iftrue;
604 }
605 }
606
607 // Build a canonical trip test.
608 // Clone code, as old values may be in use.
609 incr = incr->clone();
610 incr->set_req(1,phi);
611 incr->set_req(2,stride);
612 incr = _igvn.register_new_node_with_optimizer(incr);
613 set_early_ctrl( incr );
614 _igvn.rehash_node_delayed(phi);
615 phi->set_req_X( LoopNode::LoopBackControl, incr, &_igvn );
616
617 // If phi type is more restrictive than Int, raise to
618 // Int to prevent (almost) infinite recursion in igvn
628 cmp = cmp->clone();
629 cmp->set_req(1,incr);
630 cmp->set_req(2,limit);
631 cmp = _igvn.register_new_node_with_optimizer(cmp);
632 set_ctrl(cmp, iff->in(0));
633
634 test = test->clone()->as_Bool();
635 (*(BoolTest*)&test->_test)._test = bt;
636 test->set_req(1,cmp);
637 _igvn.register_new_node_with_optimizer(test);
638 set_ctrl(test, iff->in(0));
639
640 // Replace the old IfNode with a new LoopEndNode
641 Node *lex = _igvn.register_new_node_with_optimizer(new CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt ));
642 IfNode *le = lex->as_If();
643 uint dd = dom_depth(iff);
644 set_idom(le, le->in(0), dd); // Update dominance for loop exit
645 set_loop(le, loop);
646
647 // Get the loop-exit control
648 Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue));
649
650 // Need to swap loop-exit and loop-back control?
651 if (iftrue_op == Op_IfFalse) {
652 Node *ift2=_igvn.register_new_node_with_optimizer(new IfTrueNode (le));
653 Node *iff2=_igvn.register_new_node_with_optimizer(new IfFalseNode(le));
654
655 loop->_tail = back_control = ift2;
656 set_loop(ift2, loop);
657 set_loop(iff2, get_loop(iffalse));
658
659 // Lazy update of 'get_ctrl' mechanism.
660 lazy_replace(iffalse, iff2);
661 lazy_replace(iftrue, ift2);
662
663 // Swap names
664 iffalse = iff2;
665 iftrue = ift2;
666 } else {
667 _igvn.rehash_node_delayed(iffalse);
668 _igvn.rehash_node_delayed(iftrue);
669 iffalse->set_req_X( 0, le, &_igvn );
670 iftrue ->set_req_X( 0, le, &_igvn );
671 }
676 lazy_replace( iff, le ); // fix 'get_ctrl'
677
678 // Now setup a new CountedLoopNode to replace the existing LoopNode
679 CountedLoopNode *l = new CountedLoopNode(init_control, back_control);
680 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve
681 // The following assert is approximately true, and defines the intention
682 // of can_be_counted_loop. It fails, however, because phase->type
683 // is not yet initialized for this loop and its parts.
684 //assert(l->can_be_counted_loop(this), "sanity");
685 _igvn.register_new_node_with_optimizer(l);
686 set_loop(l, loop);
687 loop->_head = l;
688 // Fix all data nodes placed at the old loop head.
689 // Uses the lazy-update mechanism of 'get_ctrl'.
690 lazy_replace( x, l );
691 set_idom(l, init_control, dom_depth(x));
692
693 if (!UseCountedLoopSafepoints) {
694 // Check for immediately preceding SafePoint and remove
695 Node *sfpt2 = le->in(0);
696 if (sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2)) {
697 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
698 if (loop->_safepts != NULL) {
699 loop->_safepts->yank(sfpt2);
700 }
701 }
702 }
703
704 // Free up intermediate goo
705 _igvn.remove_dead_node(hook);
706
707 #ifdef ASSERT
708 assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
709 assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
710 #endif
711 #ifndef PRODUCT
712 if (TraceLoopOpts) {
713 tty->print("Counted ");
714 loop->dump_head();
715 }
716 #endif
717
718 C->print_method(PHASE_AFTER_CLOOPS, 3);
719
720 // Capture bounds of the loop in the induction variable Phi before
721 // subsequent transformation (iteration splitting) obscures the
722 // bounds
723 l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
724
725 return true;
726 }
727
728 //----------------------exact_limit-------------------------------------------
729 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
730 assert(loop->_head->is_CountedLoop(), "");
731 CountedLoopNode *cl = loop->_head->as_CountedLoop();
732 assert(cl->is_valid_counted_loop(), "");
733
734 if (ABS(cl->stride_con()) == 1 ||
735 cl->limit()->Opcode() == Op_LoopLimit) {
736 // Old code has exact limit (it could be incorrect in case of int overflow).
737 // Loop limit is exact with stride == 1. And loop may already have exact limit.
738 return cl->limit();
739 }
740 Node *limit = NULL;
741 #ifdef ASSERT
742 BoolTest::mask bt = cl->loopexit()->test_trip();
743 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
744 #endif
745 if (cl->has_exact_trip_count()) {
746 // Simple case: loop has constant boundaries.
747 // Use jlongs to avoid integer overflow.
748 int stride_con = cl->stride_con();
749 jlong init_con = cl->init_trip()->get_int();
750 jlong limit_con = cl->limit()->get_int();
751 julong trip_cnt = cl->trip_count();
752 jlong final_con = init_con + trip_cnt*stride_con;
753 int final_int = (int)final_con;
754 // The final value should be in integer range since the loop
755 // is counted and the limit was checked for overflow.
865 ini = init_t->_lo;
866 max = (julong)max_jint;
867 } else {
868 stride_p = -stride_con;
869 lim = init_t->_hi;
870 ini = limit_t->_lo;
871 max = (julong)min_jint;
872 }
873 julong range = lim - ini + stride_p;
874 if (range <= max) {
875 // Convert to integer expression if it is not overflow.
876 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
877 Node *range = phase->transform(new SubINode(in(Limit), in(Init)));
878 Node *bias = phase->transform(new AddINode(range, stride_m));
879 Node *trip = phase->transform(new DivINode(0, bias, in(Stride)));
880 Node *span = phase->transform(new MulINode(trip, in(Stride)));
881 return new AddINode(span, in(Init)); // exact limit
882 }
883
884 if (is_power_of_2(stride_p) || // divisor is 2^n
885 !Matcher::has_match_rule(Op_LoopLimit)) { // or no specialized Mach node?
886 // Convert to long expression to avoid integer overflow
887 // and let igvn optimizer convert this division.
888 //
889 Node* init = phase->transform( new ConvI2LNode(in(Init)));
890 Node* limit = phase->transform( new ConvI2LNode(in(Limit)));
891 Node* stride = phase->longcon(stride_con);
892 Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1));
893
894 Node *range = phase->transform(new SubLNode(limit, init));
895 Node *bias = phase->transform(new AddLNode(range, stride_m));
896 Node *span;
897 if (stride_con > 0 && is_power_of_2(stride_p)) {
898 // bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride)
899 // and avoid generating rounding for division. Zero trip guard should
900 // guarantee that init < limit but sometimes the guard is missing and
901 // we can get situation when init > limit. Note, for the empty loop
902 // optimization zero trip guard is generated explicitly which leaves
903 // only RCE predicate where exact limit is used and the predicate
904 // will simply fail forcing recompilation.
905 Node* neg_stride = phase->longcon(-stride_con);
922 int stride_con = phase->type(in(Stride))->is_int()->get_con();
923 if (stride_con == 1 || stride_con == -1)
924 return in(Limit);
925 return this;
926 }
927
928 //=============================================================================
929 //----------------------match_incr_with_optional_truncation--------------------
930 // Match increment with optional truncation:
931 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
932 // Return NULL for failure. Success returns the increment node.
933 Node* CountedLoopNode::match_incr_with_optional_truncation(
934 Node* expr, Node** trunc1, Node** trunc2, const TypeInt** trunc_type) {
935 // Quick cutouts:
936 if (expr == NULL || expr->req() != 3) return NULL;
937
938 Node *t1 = NULL;
939 Node *t2 = NULL;
940 const TypeInt* trunc_t = TypeInt::INT;
941 Node* n1 = expr;
942 int n1op = n1->Opcode();
943
944 // Try to strip (n1 & M) or (n1 << N >> N) from n1.
945 if (n1op == Op_AndI &&
946 n1->in(2)->is_Con() &&
947 n1->in(2)->bottom_type()->is_int()->get_con() == 0x7fff) {
948 // %%% This check should match any mask of 2**K-1.
949 t1 = n1;
950 n1 = t1->in(1);
951 n1op = n1->Opcode();
952 trunc_t = TypeInt::CHAR;
953 } else if (n1op == Op_RShiftI &&
954 n1->in(1) != NULL &&
955 n1->in(1)->Opcode() == Op_LShiftI &&
956 n1->in(2) == n1->in(1)->in(2) &&
957 n1->in(2)->is_Con()) {
958 jint shift = n1->in(2)->bottom_type()->is_int()->get_con();
959 // %%% This check should match any shift in [1..31].
960 if (shift == 16 || shift == 8) {
961 t1 = n1;
962 t2 = t1->in(1);
963 n1 = t2->in(1);
964 n1op = n1->Opcode();
965 if (shift == 16) {
966 trunc_t = TypeInt::SHORT;
967 } else if (shift == 8) {
968 trunc_t = TypeInt::BYTE;
969 }
970 }
971 }
972
973 // If (maybe after stripping) it is an AddI, we won:
974 if (n1op == Op_AddI) {
975 *trunc1 = t1;
976 *trunc2 = t2;
977 *trunc_type = trunc_t;
978 return n1;
979 }
980
981 // failed
982 return NULL;
983 }
984
985
986 //------------------------------filtered_type--------------------------------
987 // Return a type based on condition control flow
988 // A successful return will be a type that is restricted due
989 // to a series of dominating if-tests, such as:
990 // if (i < 10) {
991 // if (i > 0) {
992 // here: "i" type is [1..10)
993 // }
994 // }
1031 }
1032 return n_t;
1033 }
1034
1035
1036 //------------------------------filtered_type_from_dominators--------------------------------
1037 // Return a possibly more restrictive type for val based on condition control flow of dominators
1038 const TypeInt* PhaseIdealLoop::filtered_type_from_dominators( Node* val, Node *use_ctrl) {
1039 if (val->is_Con()) {
1040 return val->bottom_type()->is_int();
1041 }
1042 uint if_limit = 10; // Max number of dominating if's visited
1043 const TypeInt* rtn_t = NULL;
1044
1045 if (use_ctrl && use_ctrl != C->top()) {
1046 Node* val_ctrl = get_ctrl(val);
1047 uint val_dom_depth = dom_depth(val_ctrl);
1048 Node* pred = use_ctrl;
1049 uint if_cnt = 0;
1050 while (if_cnt < if_limit) {
1051 if ((pred->Opcode() == Op_IfTrue || pred->Opcode() == Op_IfFalse)) {
1052 if_cnt++;
1053 const TypeInt* if_t = IfNode::filtered_int_type(&_igvn, val, pred);
1054 if (if_t != NULL) {
1055 if (rtn_t == NULL) {
1056 rtn_t = if_t;
1057 } else {
1058 rtn_t = rtn_t->join(if_t)->is_int();
1059 }
1060 }
1061 }
1062 pred = idom(pred);
1063 if (pred == NULL || pred == C->top()) {
1064 break;
1065 }
1066 // Stop if going beyond definition block of val
1067 if (dom_depth(pred) < val_dom_depth) {
1068 break;
1069 }
1070 }
1071 }
1226 }
1227 }
1228
1229 // Use the new loop head instead of the old shared one
1230 _head = outer;
1231 phase->set_loop(_head, this);
1232 }
1233
1234 //------------------------------fix_parent-------------------------------------
1235 static void fix_parent( IdealLoopTree *loop, IdealLoopTree *parent ) {
1236 loop->_parent = parent;
1237 if( loop->_child ) fix_parent( loop->_child, loop );
1238 if( loop->_next ) fix_parent( loop->_next , parent );
1239 }
1240
1241 //------------------------------estimate_path_freq-----------------------------
1242 static float estimate_path_freq( Node *n ) {
1243 // Try to extract some path frequency info
1244 IfNode *iff;
1245 for( int i = 0; i < 50; i++ ) { // Skip through a bunch of uncommon tests
1246 uint nop = n->Opcode();
1247 if( nop == Op_SafePoint ) { // Skip any safepoint
1248 n = n->in(0);
1249 continue;
1250 }
1251 if( nop == Op_CatchProj ) { // Get count from a prior call
1252 // Assume call does not always throw exceptions: means the call-site
1253 // count is also the frequency of the fall-through path.
1254 assert( n->is_CatchProj(), "" );
1255 if( ((CatchProjNode*)n)->_con != CatchProjNode::fall_through_index )
1256 return 0.0f; // Assume call exception path is rare
1257 Node *call = n->in(0)->in(0)->in(0);
1258 assert( call->is_Call(), "expect a call here" );
1259 const JVMState *jvms = ((CallNode*)call)->jvms();
1260 ciMethodData* methodData = jvms->method()->method_data();
1261 if (!methodData->is_mature()) return 0.0f; // No call-site data
1262 ciProfileData* data = methodData->bci_to_data(jvms->bci());
1263 if ((data == NULL) || !data->is_CounterData()) {
1264 // no call profile available, try call's control input
1265 n = n->in(0);
1266 continue;
1267 }
1268 return data->as_CounterData()->count()/FreqCountInvocations;
1269 }
1270 // See if there's a gating IF test
1271 Node *n_c = n->in(0);
1272 if( !n_c->is_If() ) break; // No estimate available
1273 iff = n_c->as_If();
1274 if( iff->_fcnt != COUNT_UNKNOWN ) // Have a valid count?
1275 // Compute how much count comes on this path
1276 return ((nop == Op_IfTrue) ? iff->_prob : 1.0f - iff->_prob) * iff->_fcnt;
1277 // Have no count info. Skip dull uncommon-trap like branches.
1278 if( (nop == Op_IfTrue && iff->_prob < PROB_LIKELY_MAG(5)) ||
1279 (nop == Op_IfFalse && iff->_prob > PROB_UNLIKELY_MAG(5)) )
1280 break;
1281 // Skip through never-taken branch; look for a real loop exit.
1282 n = iff->in(0);
1283 }
1284 return 0.0f; // No estimate available
1285 }
1286
1287 //------------------------------merge_many_backedges---------------------------
1288 // Merge all the backedges from the shared header into a private Region.
1289 // Feed that region as the one backedge to this loop.
1290 void IdealLoopTree::merge_many_backedges( PhaseIdealLoop *phase ) {
1291 uint i;
1292
1293 // Scan for the top 2 hottest backedges
1294 float hotcnt = 0.0f;
1295 float warmcnt = 0.0f;
1296 uint hot_idx = 0;
1297 // Loop starts at 2 because slot 1 is the fall-in path
1298 for( i = 2; i < _head->req(); i++ ) {
1299 float cnt = estimate_path_freq(_head->in(i));
1469 }
1470
1471 // Now recursively beautify nested loops
1472 if( _child ) result |= _child->beautify_loops( phase );
1473 if( _next ) result |= _next ->beautify_loops( phase );
1474 return result;
1475 }
1476
1477 //------------------------------allpaths_check_safepts----------------------------
1478 // Allpaths backwards scan from loop tail, terminating each path at first safepoint
1479 // encountered. Helper for check_safepts.
1480 void IdealLoopTree::allpaths_check_safepts(VectorSet &visited, Node_List &stack) {
1481 assert(stack.size() == 0, "empty stack");
1482 stack.push(_tail);
1483 visited.Clear();
1484 visited.set(_tail->_idx);
1485 while (stack.size() > 0) {
1486 Node* n = stack.pop();
1487 if (n->is_Call() && n->as_Call()->guaranteed_safepoint()) {
1488 // Terminate this path
1489 } else if (n->Opcode() == Op_SafePoint) {
1490 if (_phase->get_loop(n) != this) {
1491 if (_required_safept == NULL) _required_safept = new Node_List();
1492 _required_safept->push(n); // save the one closest to the tail
1493 }
1494 // Terminate this path
1495 } else {
1496 uint start = n->is_Region() ? 1 : 0;
1497 uint end = n->is_Region() && !n->is_Loop() ? n->req() : start + 1;
1498 for (uint i = start; i < end; i++) {
1499 Node* in = n->in(i);
1500 assert(in->is_CFG(), "must be");
1501 if (!visited.test_set(in->_idx) && is_member(_phase->get_loop(in))) {
1502 stack.push(in);
1503 }
1504 }
1505 }
1506 }
1507 }
1508
1509 //------------------------------check_safepts----------------------------
1559 // the idom path (which is rare), scans all predecessor control paths
1560 // from the tail to the head, terminating a path when a call or sfpt
1561 // is encountered, to find the ncsfpt's that are closest to the tail.
1562 //
1563 void IdealLoopTree::check_safepts(VectorSet &visited, Node_List &stack) {
1564 // Bottom up traversal
1565 IdealLoopTree* ch = _child;
1566 if (_child) _child->check_safepts(visited, stack);
1567 if (_next) _next ->check_safepts(visited, stack);
1568
1569 if (!_head->is_CountedLoop() && !_has_sfpt && _parent != NULL && !_irreducible) {
1570 bool has_call = false; // call on dom-path
1571 bool has_local_ncsfpt = false; // ncsfpt on dom-path at this loop depth
1572 Node* nonlocal_ncsfpt = NULL; // ncsfpt on dom-path at a deeper depth
1573 // Scan the dom-path nodes from tail to head
1574 for (Node* n = tail(); n != _head; n = _phase->idom(n)) {
1575 if (n->is_Call() && n->as_Call()->guaranteed_safepoint()) {
1576 has_call = true;
1577 _has_sfpt = 1; // Then no need for a safept!
1578 break;
1579 } else if (n->Opcode() == Op_SafePoint) {
1580 if (_phase->get_loop(n) == this) {
1581 has_local_ncsfpt = true;
1582 break;
1583 }
1584 if (nonlocal_ncsfpt == NULL) {
1585 nonlocal_ncsfpt = n; // save the one closest to the tail
1586 }
1587 } else {
1588 IdealLoopTree* nlpt = _phase->get_loop(n);
1589 if (this != nlpt) {
1590 // If at an inner loop tail, see if the inner loop has already
1591 // recorded seeing a call on the dom-path (and stop.) If not,
1592 // jump to the head of the inner loop.
1593 assert(is_member(nlpt), "nested loop");
1594 Node* tail = nlpt->_tail;
1595 if (tail->in(0)->is_If()) tail = tail->in(0);
1596 if (n == tail) {
1597 // If inner loop has call on dom-path, so does outer loop
1598 if (nlpt->_has_sfpt) {
1599 has_call = true;
1608 }
1609 }
1610 // Record safept's that this loop needs preserved when an
1611 // inner loop attempts to delete it's safepoints.
1612 if (_child != NULL && !has_call && !has_local_ncsfpt) {
1613 if (nonlocal_ncsfpt != NULL) {
1614 if (_required_safept == NULL) _required_safept = new Node_List();
1615 _required_safept->push(nonlocal_ncsfpt);
1616 } else {
1617 // Failed to find a suitable safept on the dom-path. Now use
1618 // an all paths walk from tail to head, looking for safepoints to preserve.
1619 allpaths_check_safepts(visited, stack);
1620 }
1621 }
1622 }
1623 }
1624
1625 //---------------------------is_deleteable_safept----------------------------
1626 // Is safept not required by an outer loop?
1627 bool PhaseIdealLoop::is_deleteable_safept(Node* sfpt) {
1628 assert(sfpt->Opcode() == Op_SafePoint, "");
1629 IdealLoopTree* lp = get_loop(sfpt)->_parent;
1630 while (lp != NULL) {
1631 Node_List* sfpts = lp->_required_safept;
1632 if (sfpts != NULL) {
1633 for (uint i = 0; i < sfpts->size(); i++) {
1634 if (sfpt == sfpts->at(i))
1635 return false;
1636 }
1637 }
1638 lp = lp->_parent;
1639 }
1640 return true;
1641 }
1642
1643 //---------------------------replace_parallel_iv-------------------------------
1644 // Replace parallel induction variable (parallel to trip counter)
1645 void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) {
1646 assert(loop->_head->is_CountedLoop(), "");
1647 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1648 if (!cl->is_valid_counted_loop())
1650 Node *incr = cl->incr();
1651 if (incr == NULL)
1652 return; // Dead loop?
1653 Node *init = cl->init_trip();
1654 Node *phi = cl->phi();
1655 int stride_con = cl->stride_con();
1656
1657 // Visit all children, looking for Phis
1658 for (DUIterator i = cl->outs(); cl->has_out(i); i++) {
1659 Node *out = cl->out(i);
1660 // Look for other phis (secondary IVs). Skip dead ones
1661 if (!out->is_Phi() || out == phi || !has_node(out))
1662 continue;
1663 PhiNode* phi2 = out->as_Phi();
1664 Node *incr2 = phi2->in( LoopNode::LoopBackControl );
1665 // Look for induction variables of the form: X += constant
1666 if (phi2->region() != loop->_head ||
1667 incr2->req() != 3 ||
1668 incr2->in(1) != phi2 ||
1669 incr2 == incr ||
1670 incr2->Opcode() != Op_AddI ||
1671 !incr2->in(2)->is_Con())
1672 continue;
1673
1674 // Check for parallel induction variable (parallel to trip counter)
1675 // via an affine function. In particular, count-down loops with
1676 // count-up array indices are common. We only RCE references off
1677 // the trip-counter, so we need to convert all these to trip-counter
1678 // expressions.
1679 Node *init2 = phi2->in( LoopNode::EntryControl );
1680 int stride_con2 = incr2->in(2)->get_int();
1681
1682 // The general case here gets a little tricky. We want to find the
1683 // GCD of all possible parallel IV's and make a new IV using this
1684 // GCD for the loop. Then all possible IVs are simple multiples of
1685 // the GCD. In practice, this will cover very few extra loops.
1686 // Instead we require 'stride_con2' to be a multiple of 'stride_con',
1687 // where +/-1 is the common case, but other integer multiples are
1688 // also easy to handle.
1689 int ratio_con = stride_con2/stride_con;
1690
1712 set_ctrl(ratio_idx, cl);
1713 Node* add = new AddINode(ratio_idx, diff);
1714 _igvn.register_new_node_with_optimizer(add);
1715 set_ctrl(add, cl);
1716 _igvn.replace_node( phi2, add );
1717 // Sometimes an induction variable is unused
1718 if (add->outcnt() == 0) {
1719 _igvn.remove_dead_node(add);
1720 }
1721 --i; // deleted this phi; rescan starting with next position
1722 continue;
1723 }
1724 }
1725 }
1726
1727 void IdealLoopTree::remove_safepoints(PhaseIdealLoop* phase, bool keep_one) {
1728 Node* keep = NULL;
1729 if (keep_one) {
1730 // Look for a safepoint on the idom-path.
1731 for (Node* i = tail(); i != _head; i = phase->idom(i)) {
1732 if (i->Opcode() == Op_SafePoint && phase->get_loop(i) == this) {
1733 keep = i;
1734 break; // Found one
1735 }
1736 }
1737 }
1738
1739 // Don't remove any safepoints if it is requested to keep a single safepoint and
1740 // no safepoint was found on idom-path. It is not safe to remove any safepoint
1741 // in this case since there's no safepoint dominating all paths in the loop body.
1742 bool prune = !keep_one || keep != NULL;
1743
1744 // Delete other safepoints in this loop.
1745 Node_List* sfpts = _safepts;
1746 if (prune && sfpts != NULL) {
1747 assert(keep == NULL || keep->Opcode() == Op_SafePoint, "not safepoint");
1748 for (uint i = 0; i < sfpts->size(); i++) {
1749 Node* n = sfpts->at(i);
1750 assert(phase->get_loop(n) == this, "");
1751 if (n != keep && phase->is_deleteable_safept(n)) {
1752 phase->lazy_replace(n, n->in(TypeFunc::Control));
1753 }
1754 }
1755 }
1756 }
1757
1758 //------------------------------counted_loop-----------------------------------
1759 // Convert to counted loops where possible
1760 void IdealLoopTree::counted_loop( PhaseIdealLoop *phase ) {
1761
1762 // For grins, set the inner-loop flag here
1763 if (!_child) {
1764 if (_head->is_Loop()) _head->as_Loop()->set_inner_loop();
1765 }
1766
1767 if (_head->is_CountedLoop() ||
1890 }
1891 }
1892
1893 //---------------------collect_potentially_useful_predicates-----------------------
1894 // Helper function to collect potentially useful predicates to prevent them from
1895 // being eliminated by PhaseIdealLoop::eliminate_useless_predicates
1896 void PhaseIdealLoop::collect_potentially_useful_predicates(
1897 IdealLoopTree * loop, Unique_Node_List &useful_predicates) {
1898 if (loop->_child) { // child
1899 collect_potentially_useful_predicates(loop->_child, useful_predicates);
1900 }
1901
1902 // self (only loops that we can apply loop predication may use their predicates)
1903 if (loop->_head->is_Loop() &&
1904 !loop->_irreducible &&
1905 !loop->tail()->is_top()) {
1906 LoopNode* lpn = loop->_head->as_Loop();
1907 Node* entry = lpn->in(LoopNode::EntryControl);
1908 Node* predicate_proj = find_predicate(entry); // loop_limit_check first
1909 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication
1910 assert(entry->in(0)->in(1)->in(1)->Opcode() == Op_Opaque1, "must be");
1911 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1912 entry = entry->in(0)->in(0);
1913 }
1914 predicate_proj = find_predicate(entry); // Predicate
1915 if (predicate_proj != NULL ) {
1916 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1917 }
1918 }
1919
1920 if (loop->_next) { // sibling
1921 collect_potentially_useful_predicates(loop->_next, useful_predicates);
1922 }
1923 }
1924
1925 //------------------------eliminate_useless_predicates-----------------------------
1926 // Eliminate all inserted predicates if they could not be used by loop predication.
1927 // Note: it will also eliminates loop limits check predicate since it also uses
1928 // Opaque1 node (see Parse::add_predicate()).
1929 void PhaseIdealLoop::eliminate_useless_predicates() {
1930 if (C->predicate_count() == 0)
1931 return; // no predicate left
1932
1933 Unique_Node_List useful_predicates; // to store useful predicates
1934 if (C->has_loops()) {
1935 collect_potentially_useful_predicates(_ltree_root->_child, useful_predicates);
1936 }
1937
1938 for (int i = C->predicate_count(); i > 0; i--) {
1939 Node * n = C->predicate_opaque1_node(i-1);
1940 assert(n->Opcode() == Op_Opaque1, "must be");
1941 if (!useful_predicates.member(n)) { // not in the useful list
1942 _igvn.replace_node(n, n->in(1));
1943 }
1944 }
1945 }
1946
1947 //------------------------process_expensive_nodes-----------------------------
1948 // Expensive nodes have their control input set to prevent the GVN
1949 // from commoning them and as a result forcing the resulting node to
1950 // be in a more frequent path. Use CFG information here, to change the
1951 // control inputs so that some expensive nodes can be commoned while
1952 // not executed more frequently.
1953 bool PhaseIdealLoop::process_expensive_nodes() {
1954 assert(OptimizeExpensiveOps, "optimization off?");
1955
1956 // Sort nodes to bring similar nodes together
1957 C->sort_expensive_nodes();
1958
1959 bool progress = false;
1960
2538 // Move (*nn) to (*pp)
2539 IdealLoopTree *hit = *nn;
2540 *nn = hit->_next;
2541 hit->_next = loop;
2542 *pp = loop;
2543 loop = hit;
2544 // Now try again to verify
2545 }
2546
2547 assert( _head == loop->_head , "mismatched loop head" );
2548 Node *tail = _tail; // Inline a non-updating version of
2549 while( !tail->in(0) ) // the 'tail()' call.
2550 tail = tail->in(1);
2551 assert( tail == loop->_tail, "mismatched loop tail" );
2552
2553 // Counted loops that are guarded should be able to find their guards
2554 if( _head->is_CountedLoop() && _head->as_CountedLoop()->is_main_loop() ) {
2555 CountedLoopNode *cl = _head->as_CountedLoop();
2556 Node *init = cl->init_trip();
2557 Node *ctrl = cl->in(LoopNode::EntryControl);
2558 assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" );
2559 Node *iff = ctrl->in(0);
2560 assert( iff->Opcode() == Op_If, "" );
2561 Node *bol = iff->in(1);
2562 assert( bol->Opcode() == Op_Bool, "" );
2563 Node *cmp = bol->in(1);
2564 assert( cmp->Opcode() == Op_CmpI, "" );
2565 Node *add = cmp->in(1);
2566 Node *opaq;
2567 if( add->Opcode() == Op_Opaque1 ) {
2568 opaq = add;
2569 } else {
2570 assert( add->Opcode() == Op_AddI || add->Opcode() == Op_ConI , "" );
2571 assert( add == init, "" );
2572 opaq = cmp->in(2);
2573 }
2574 assert( opaq->Opcode() == Op_Opaque1, "" );
2575
2576 }
2577
2578 if (_child != NULL) _child->verify_tree(loop->_child, this);
2579 if (_next != NULL) _next ->verify_tree(loop->_next, parent);
2580 // Innermost loops need to verify loop bodies,
2581 // but only if no 'major_progress'
2582 int fail = 0;
2583 if (!Compile::current()->major_progress() && _child == NULL) {
2584 for( uint i = 0; i < _body.size(); i++ ) {
2585 Node *n = _body.at(i);
2586 if (n->outcnt() == 0) continue; // Ignore dead
2587 uint j;
2588 for( j = 0; j < loop->_body.size(); j++ )
2589 if( loop->_body.at(j) == n )
2590 break;
2591 if( j == loop->_body.size() ) { // Not found in loop body
2592 // Last ditch effort to avoid assertion: Its possible that we
2593 // have some users (so outcnt not zero) but are still dead.
2594 // Try to find from root.
2948 l->_next = p->_child; // Put self on parents 'next child'
2949 p->_child = l; // Make self as first child of parent
2950 l = p; // Now walk up the parent chain
2951 p = l->_parent;
2952 }
2953 } else {
2954 // Note that it is possible for a LoopNode to reach here, if the
2955 // backedge has been made unreachable (hence the LoopNode no longer
2956 // denotes a Loop, and will eventually be removed).
2957
2958 // Record tightest enclosing loop for self. Mark as post-visited.
2959 set_loop(n, innermost);
2960 // Also record has_call flag early on
2961 if( innermost ) {
2962 if( n->is_Call() && !n->is_CallLeaf() && !n->is_macro() ) {
2963 // Do not count uncommon calls
2964 if( !n->is_CallStaticJava() || !n->as_CallStaticJava()->_name ) {
2965 Node *iff = n->in(0)->in(0);
2966 // No any calls for vectorized loops.
2967 if( UseSuperWord || !iff->is_If() ||
2968 (n->in(0)->Opcode() == Op_IfFalse &&
2969 (1.0 - iff->as_If()->_prob) >= 0.01) ||
2970 (iff->as_If()->_prob >= 0.01) )
2971 innermost->_has_call = 1;
2972 }
2973 } else if( n->is_Allocate() && n->as_Allocate()->_is_scalar_replaceable ) {
2974 // Disable loop optimizations if the loop has a scalar replaceable
2975 // allocation. This disabling may cause a potential performance lost
2976 // if the allocation is not eliminated for some reason.
2977 innermost->_allow_optimizations = false;
2978 innermost->_has_call = 1; // = true
2979 } else if (n->Opcode() == Op_SafePoint) {
2980 // Record all safepoints in this loop.
2981 if (innermost->_safepts == NULL) innermost->_safepts = new Node_List();
2982 innermost->_safepts->push(n);
2983 }
2984 }
2985 }
2986
2987 // Flag as post-visited now
2988 set_postvisited(n);
2989 return pre_order;
2990 }
2991
2992
2993 //------------------------------build_loop_early-------------------------------
2994 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2995 // First pass computes the earliest controlling node possible. This is the
2996 // controlling input with the deepest dominating depth.
2997 void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
2998 while (worklist.size() != 0) {
2999 // Use local variables nstack_top_n & nstack_top_i to cache values
3009 if (i == 0) { // Pre-process the node.
3010 if( has_node(n) && // Have either loop or control already?
3011 !has_ctrl(n) ) { // Have loop picked out already?
3012 // During "merge_many_backedges" we fold up several nested loops
3013 // into a single loop. This makes the members of the original
3014 // loop bodies pointing to dead loops; they need to move up
3015 // to the new UNION'd larger loop. I set the _head field of these
3016 // dead loops to NULL and the _parent field points to the owning
3017 // loop. Shades of UNION-FIND algorithm.
3018 IdealLoopTree *ilt;
3019 while( !(ilt = get_loop(n))->_head ) {
3020 // Normally I would use a set_loop here. But in this one special
3021 // case, it is legal (and expected) to change what loop a Node
3022 // belongs to.
3023 _nodes.map(n->_idx, (Node*)(ilt->_parent) );
3024 }
3025 // Remove safepoints ONLY if I've already seen I don't need one.
3026 // (the old code here would yank a 2nd safepoint after seeing a
3027 // first one, even though the 1st did not dominate in the loop body
3028 // and thus could be avoided indefinitely)
3029 if( !_verify_only && !_verify_me && ilt->_has_sfpt && n->Opcode() == Op_SafePoint &&
3030 is_deleteable_safept(n)) {
3031 Node *in = n->in(TypeFunc::Control);
3032 lazy_replace(n,in); // Pull safepoint now
3033 if (ilt->_safepts != NULL) {
3034 ilt->_safepts->yank(n);
3035 }
3036 // Carry on with the recursion "as if" we are walking
3037 // only the control input
3038 if( !visited.test_set( in->_idx ) ) {
3039 worklist.push(in); // Visit this guy later, using worklist
3040 }
3041 // Get next node from nstack:
3042 // - skip n's inputs processing by setting i > cnt;
3043 // - we also will not call set_early_ctrl(n) since
3044 // has_node(n) == true (see the condition above).
3045 i = cnt + 1;
3046 }
3047 }
3048 } // if (i == 0)
3049
3218 Node* ctrl = cl->in(LoopNode::EntryControl);
3219 if (ctrl == NULL || (!ctrl->is_IfTrue() && !ctrl->is_IfFalse())) {
3220 return false;
3221 }
3222 Node* iffm = ctrl->in(0);
3223 if (iffm == NULL || !iffm->is_If()) {
3224 return false;
3225 }
3226 Node* bolzm = iffm->in(1);
3227 if (bolzm == NULL || !bolzm->is_Bool()) {
3228 return false;
3229 }
3230 Node* cmpzm = bolzm->in(1);
3231 if (cmpzm == NULL || !cmpzm->is_Cmp()) {
3232 return false;
3233 }
3234 // compares can get conditionally flipped
3235 bool found_opaque = false;
3236 for (uint i = 1; i < cmpzm->req(); i++) {
3237 Node* opnd = cmpzm->in(i);
3238 if (opnd && opnd->Opcode() == Op_Opaque1) {
3239 found_opaque = true;
3240 break;
3241 }
3242 }
3243 if (!found_opaque) {
3244 return false;
3245 }
3246 return true;
3247 }
3248
3249 //------------------------------get_late_ctrl----------------------------------
3250 // Compute latest legal control.
3251 Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
3252 assert(early != NULL, "early control should not be NULL");
3253
3254 Node* LCA = compute_lca_of_uses(n, early);
3255 #ifdef ASSERT
3256 if (LCA == C->root() && LCA != early) {
3257 // def doesn't dominate uses so print some useful debugging output
3258 compute_lca_of_uses(n, early, true);
3442 if (nstack.is_empty()) {
3443 // Finished all nodes on stack.
3444 // Process next node on the worklist.
3445 break;
3446 }
3447 // Get saved parent node and next use's index. Visit the rest of uses.
3448 n = nstack.node();
3449 cnt = n->outcnt();
3450 i = nstack.index();
3451 nstack.pop();
3452 }
3453 }
3454 }
3455 }
3456
3457 //------------------------------build_loop_late_post---------------------------
3458 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
3459 // Second pass finds latest legal placement, and ideal loop placement.
3460 void PhaseIdealLoop::build_loop_late_post( Node *n ) {
3461
3462 if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
3463 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops.
3464 }
3465
3466 #ifdef ASSERT
3467 if (_verify_only && !n->is_CFG()) {
3468 // Check def-use domination.
3469 compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
3470 }
3471 #endif
3472
3473 // CFG and pinned nodes already handled
3474 if( n->in(0) ) {
3475 if( n->in(0)->is_top() ) return; // Dead?
3476
3477 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
3478 // _must_ be pinned (they have to observe their control edge of course).
3479 // Unlike Stores (which modify an unallocable resource, the memory
3480 // state), Mods/Loads can float around. So free them up.
3481 bool pinned = true;
3482 switch( n->Opcode() ) {
3483 case Op_DivI:
3484 case Op_DivF:
3485 case Op_DivD:
3486 case Op_ModI:
3487 case Op_ModF:
3488 case Op_ModD:
3489 case Op_LoadB: // Same with Loads; they can sink
3490 case Op_LoadUB: // during loop optimizations.
3491 case Op_LoadUS:
3492 case Op_LoadD:
3493 case Op_LoadF:
3494 case Op_LoadI:
3495 case Op_LoadKlass:
3496 case Op_LoadNKlass:
3497 case Op_LoadL:
3498 case Op_LoadS:
3499 case Op_LoadP:
3500 case Op_LoadN:
3501 case Op_LoadRange:
3502 case Op_LoadD_unaligned:
3503 case Op_LoadL_unaligned:
3504 case Op_StrComp: // Does a bunch of load-like effects
3505 case Op_StrEquals:
3506 case Op_StrIndexOf:
3507 case Op_StrIndexOfChar:
3508 case Op_AryEq:
3509 case Op_HasNegatives:
3510 pinned = false;
3511 }
3512 if( pinned ) {
3513 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
3514 if( !chosen_loop->_child ) // Inner loop?
3515 chosen_loop->_body.push(n); // Collect inner loops
3516 return;
3517 }
3518 } else { // No slot zero
3519 if( n->is_CFG() ) { // CFG with no slot 0 is dead
3520 _nodes.map(n->_idx,0); // No block setting, it's globally dead
3521 return;
3522 }
3523 assert(!n->is_CFG() || n->outcnt() == 0, "");
3524 }
3525
3526 // Do I have a "safe range" I can select over?
3527 Node *early = get_ctrl(n);// Early location already computed
3528
3529 // Compute latest point this Node can go
|
56 //=============================================================================
57 //------------------------------dump_spec--------------------------------------
58 // Dump special per-node info
59 #ifndef PRODUCT
60 void LoopNode::dump_spec(outputStream *st) const {
61 if (is_inner_loop()) st->print( "inner " );
62 if (is_partial_peel_loop()) st->print( "partial_peel " );
63 if (partial_peel_has_failed()) st->print( "partial_peel_failed " );
64 }
65 #endif
66
67 //------------------------------is_valid_counted_loop-------------------------
68 bool LoopNode::is_valid_counted_loop() const {
69 if (is_CountedLoop()) {
70 CountedLoopNode* l = as_CountedLoop();
71 CountedLoopEndNode* le = l->loopexit();
72 if (le != NULL &&
73 le->proj_out(1 /* true */) == l->in(LoopNode::LoopBackControl)) {
74 Node* phi = l->phi();
75 Node* exit = le->proj_out(0 /* false */);
76 if (exit != NULL && exit->Opcode() == Opcodes::Op_IfFalse &&
77 phi != NULL && phi->is_Phi() &&
78 phi->in(LoopNode::LoopBackControl) == l->incr() &&
79 le->loopnode() == l && le->stride_is_con()) {
80 return true;
81 }
82 }
83 }
84 return false;
85 }
86
87 //------------------------------get_early_ctrl---------------------------------
88 // Compute earliest legal control
89 Node *PhaseIdealLoop::get_early_ctrl( Node *n ) {
90 assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" );
91 uint i;
92 Node *early;
93 if (n->in(0) && !n->is_expensive()) {
94 early = n->in(0);
95 if (!early->is_CFG()) // Might be a non-CFG multi-def
96 early = get_ctrl(early); // So treat input as a straight data input
262 }
263
264 //------------------------------is_counted_loop--------------------------------
265 bool PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) {
266 PhaseGVN *gvn = &_igvn;
267
268 // Counted loop head must be a good RegionNode with only 3 not NULL
269 // control input edges: Self, Entry, LoopBack.
270 if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {
271 return false;
272 }
273 Node *init_control = x->in(LoopNode::EntryControl);
274 Node *back_control = x->in(LoopNode::LoopBackControl);
275 if (init_control == NULL || back_control == NULL) // Partially dead
276 return false;
277 // Must also check for TOP when looking for a dead loop
278 if (init_control->is_top() || back_control->is_top())
279 return false;
280
281 // Allow funny placement of Safepoint
282 if (back_control->Opcode() == Opcodes::Op_SafePoint)
283 back_control = back_control->in(TypeFunc::Control);
284
285 // Controlling test for loop
286 Node *iftrue = back_control;
287 Opcodes iftrue_op = iftrue->Opcode();
288 if (iftrue_op != Opcodes::Op_IfTrue &&
289 iftrue_op != Opcodes::Op_IfFalse)
290 // I have a weird back-control. Probably the loop-exit test is in
291 // the middle of the loop and I am looking at some trailing control-flow
292 // merge point. To fix this I would have to partially peel the loop.
293 return false; // Obscure back-control
294
295 // Get boolean guarding loop-back test
296 Node *iff = iftrue->in(0);
297 if (get_loop(iff) != loop || !iff->in(1)->is_Bool())
298 return false;
299 BoolNode *test = iff->in(1)->as_Bool();
300 BoolTest::mask bt = test->_test._test;
301 float cl_prob = iff->as_If()->_prob;
302 if (iftrue_op == Opcodes::Op_IfFalse) {
303 bt = BoolTest(bt).negate();
304 cl_prob = 1.0 - cl_prob;
305 }
306 // Get backedge compare
307 Node *cmp = test->in(1);
308 Opcodes cmp_op = cmp->Opcode();
309 if (cmp_op != Opcodes::Op_CmpI)
310 return false; // Avoid pointer & float compares
311
312 // Find the trip-counter increment & limit. Limit must be loop invariant.
313 Node *incr = cmp->in(1);
314 Node *limit = cmp->in(2);
315
316 // ---------
317 // need 'loop()' test to tell if limit is loop invariant
318 // ---------
319
320 if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?
321 Node *tmp = incr; // Then reverse order into the CmpI
322 incr = limit;
323 limit = tmp;
324 bt = BoolTest(bt).commute(); // And commute the exit test
325 }
326 if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant
327 return false;
328 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
329 return false;
330
331 Node* phi_incr = NULL;
332 // Trip-counter increment must be commutative & associative.
333 if (incr->Opcode() == Opcodes::Op_CastII) {
334 incr = incr->in(1);
335 }
336 if (incr->is_Phi()) {
337 if (incr->as_Phi()->region() != x || incr->req() != 3)
338 return false; // Not simple trip counter expression
339 phi_incr = incr;
340 incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi
341 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant
342 return false;
343 }
344
345 Node* trunc1 = NULL;
346 Node* trunc2 = NULL;
347 const TypeInt* iv_trunc_t = NULL;
348 if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {
349 return false; // Funny increment opcode
350 }
351 assert(incr->Opcode() == Opcodes::Op_AddI, "wrong increment code");
352
353 // Get merge point
354 Node *xphi = incr->in(1);
355 Node *stride = incr->in(2);
356 if (!stride->is_Con()) { // Oops, swap these
357 if (!xphi->is_Con()) // Is the other guy a constant?
358 return false; // Nope, unknown stride, bail out
359 Node *tmp = xphi; // 'incr' is commutative, so ok to swap
360 xphi = stride;
361 stride = tmp;
362 }
363 if (xphi->Opcode() == Opcodes::Op_CastII) {
364 xphi = xphi->in(1);
365 }
366 // Stride must be constant
367 int stride_con = stride->get_int();
368 if (stride_con == 0)
369 return false; // missed some peephole opt
370
371 if (!xphi->is_Phi())
372 return false; // Too much math on the trip counter
373 if (phi_incr != NULL && phi_incr != xphi)
374 return false;
375 PhiNode *phi = xphi->as_Phi();
376
377 // Phi must be of loop header; backedge must wrap to increment
378 if (phi->region() != x)
379 return false;
380 if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr ||
381 trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) {
382 return false;
383 }
442 if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
443 return false; // cyclic loop or this loop trips only once
444 }
445
446 if (phi_incr != NULL) {
447 // check if there is a possiblity of IV overflowing after the first increment
448 if (stride_con > 0) {
449 if (init_t->_hi > max_jint - stride_con) {
450 return false;
451 }
452 } else {
453 if (init_t->_lo < min_jint - stride_con) {
454 return false;
455 }
456 }
457 }
458
459 // =================================================
460 // ---- SUCCESS! Found A Trip-Counted Loop! -----
461 //
462 assert(x->Opcode() == Opcodes::Op_Loop, "regular loops only");
463 C->print_method(PHASE_BEFORE_CLOOPS, 3);
464
465 Node *hook = new Node(6);
466
467 // ===================================================
468 // Generate loop limit check to avoid integer overflow
469 // in cases like next (cyclic loops):
470 //
471 // for (i=0; i <= max_jint; i++) {}
472 // for (i=0; i < max_jint; i+=2) {}
473 //
474 //
475 // Limit check predicate depends on the loop test:
476 //
477 // for(;i != limit; i++) --> limit <= (max_jint)
478 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
479 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
480 //
481
482 // Check if limit is excluded to do more precise int overflow check.
518 return false;
519 }
520
521 IfNode* check_iff = limit_check_proj->in(0)->as_If();
522 Node* cmp_limit;
523 Node* bol;
524
525 if (stride_con > 0) {
526 cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
527 bol = new BoolNode(cmp_limit, BoolTest::le);
528 } else {
529 cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
530 bol = new BoolNode(cmp_limit, BoolTest::ge);
531 }
532 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
533 bol = _igvn.register_new_node_with_optimizer(bol);
534 set_subtree_ctrl(bol);
535
536 // Replace condition in original predicate but preserve Opaque node
537 // so that previous predicates could be found.
538 assert(check_iff->in(1)->Opcode() == Opcodes::Op_Conv2B &&
539 check_iff->in(1)->in(1)->Opcode() == Opcodes::Op_Opaque1, "");
540 Node* opq = check_iff->in(1)->in(1);
541 _igvn.replace_input_of(opq, 1, bol);
542 // Update ctrl.
543 set_ctrl(opq, check_iff->in(0));
544 set_ctrl(check_iff->in(1), check_iff->in(0));
545
546 #ifndef PRODUCT
547 // report that the loop predication has been actually performed
548 // for this loop
549 if (TraceLoopLimitCheck) {
550 tty->print_cr("Counted Loop Limit Check generated:");
551 debug_only( bol->dump(2); )
552 }
553 #endif
554 }
555
556 if (phi_incr != NULL) {
557 // If compare points directly to the phi we need to adjust
558 // the compare so that it points to the incr. Limit have
559 // to be adjusted to keep trip count the same and we
578 }
579
580 if (incl_limit) {
581 // The limit check guaranties that 'limit <= (max_jint - stride)' so
582 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
583 //
584 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
585 limit = gvn->transform(new AddINode(limit, one));
586 if (bt == BoolTest::le)
587 bt = BoolTest::lt;
588 else if (bt == BoolTest::ge)
589 bt = BoolTest::gt;
590 else
591 ShouldNotReachHere();
592 }
593 set_subtree_ctrl( limit );
594
595 if (!UseCountedLoopSafepoints) {
596 // Check for SafePoint on backedge and remove
597 Node *sfpt = x->in(LoopNode::LoopBackControl);
598 if (sfpt->Opcode() == Opcodes::Op_SafePoint && is_deleteable_safept(sfpt)) {
599 lazy_replace( sfpt, iftrue );
600 if (loop->_safepts != NULL) {
601 loop->_safepts->yank(sfpt);
602 }
603 loop->_tail = iftrue;
604 }
605 }
606
607 // Build a canonical trip test.
608 // Clone code, as old values may be in use.
609 incr = incr->clone();
610 incr->set_req(1,phi);
611 incr->set_req(2,stride);
612 incr = _igvn.register_new_node_with_optimizer(incr);
613 set_early_ctrl( incr );
614 _igvn.rehash_node_delayed(phi);
615 phi->set_req_X( LoopNode::LoopBackControl, incr, &_igvn );
616
617 // If phi type is more restrictive than Int, raise to
618 // Int to prevent (almost) infinite recursion in igvn
628 cmp = cmp->clone();
629 cmp->set_req(1,incr);
630 cmp->set_req(2,limit);
631 cmp = _igvn.register_new_node_with_optimizer(cmp);
632 set_ctrl(cmp, iff->in(0));
633
634 test = test->clone()->as_Bool();
635 (*(BoolTest*)&test->_test)._test = bt;
636 test->set_req(1,cmp);
637 _igvn.register_new_node_with_optimizer(test);
638 set_ctrl(test, iff->in(0));
639
640 // Replace the old IfNode with a new LoopEndNode
641 Node *lex = _igvn.register_new_node_with_optimizer(new CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt ));
642 IfNode *le = lex->as_If();
643 uint dd = dom_depth(iff);
644 set_idom(le, le->in(0), dd); // Update dominance for loop exit
645 set_loop(le, loop);
646
647 // Get the loop-exit control
648 Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Opcodes::Op_IfTrue));
649
650 // Need to swap loop-exit and loop-back control?
651 if (iftrue_op == Opcodes::Op_IfFalse) {
652 Node *ift2=_igvn.register_new_node_with_optimizer(new IfTrueNode (le));
653 Node *iff2=_igvn.register_new_node_with_optimizer(new IfFalseNode(le));
654
655 loop->_tail = back_control = ift2;
656 set_loop(ift2, loop);
657 set_loop(iff2, get_loop(iffalse));
658
659 // Lazy update of 'get_ctrl' mechanism.
660 lazy_replace(iffalse, iff2);
661 lazy_replace(iftrue, ift2);
662
663 // Swap names
664 iffalse = iff2;
665 iftrue = ift2;
666 } else {
667 _igvn.rehash_node_delayed(iffalse);
668 _igvn.rehash_node_delayed(iftrue);
669 iffalse->set_req_X( 0, le, &_igvn );
670 iftrue ->set_req_X( 0, le, &_igvn );
671 }
676 lazy_replace( iff, le ); // fix 'get_ctrl'
677
678 // Now setup a new CountedLoopNode to replace the existing LoopNode
679 CountedLoopNode *l = new CountedLoopNode(init_control, back_control);
680 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve
681 // The following assert is approximately true, and defines the intention
682 // of can_be_counted_loop. It fails, however, because phase->type
683 // is not yet initialized for this loop and its parts.
684 //assert(l->can_be_counted_loop(this), "sanity");
685 _igvn.register_new_node_with_optimizer(l);
686 set_loop(l, loop);
687 loop->_head = l;
688 // Fix all data nodes placed at the old loop head.
689 // Uses the lazy-update mechanism of 'get_ctrl'.
690 lazy_replace( x, l );
691 set_idom(l, init_control, dom_depth(x));
692
693 if (!UseCountedLoopSafepoints) {
694 // Check for immediately preceding SafePoint and remove
695 Node *sfpt2 = le->in(0);
696 if (sfpt2->Opcode() == Opcodes::Op_SafePoint && is_deleteable_safept(sfpt2)) {
697 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
698 if (loop->_safepts != NULL) {
699 loop->_safepts->yank(sfpt2);
700 }
701 }
702 }
703
704 // Free up intermediate goo
705 _igvn.remove_dead_node(hook);
706
707 #ifdef ASSERT
708 assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
709 assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
710 #endif
711 #ifndef PRODUCT
712 if (TraceLoopOpts) {
713 tty->print("Counted ");
714 loop->dump_head();
715 }
716 #endif
717
718 C->print_method(PHASE_AFTER_CLOOPS, 3);
719
720 // Capture bounds of the loop in the induction variable Phi before
721 // subsequent transformation (iteration splitting) obscures the
722 // bounds
723 l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
724
725 return true;
726 }
727
728 //----------------------exact_limit-------------------------------------------
729 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
730 assert(loop->_head->is_CountedLoop(), "");
731 CountedLoopNode *cl = loop->_head->as_CountedLoop();
732 assert(cl->is_valid_counted_loop(), "");
733
734 if (ABS(cl->stride_con()) == 1 ||
735 cl->limit()->Opcode() == Opcodes::Op_LoopLimit) {
736 // Old code has exact limit (it could be incorrect in case of int overflow).
737 // Loop limit is exact with stride == 1. And loop may already have exact limit.
738 return cl->limit();
739 }
740 Node *limit = NULL;
741 #ifdef ASSERT
742 BoolTest::mask bt = cl->loopexit()->test_trip();
743 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
744 #endif
745 if (cl->has_exact_trip_count()) {
746 // Simple case: loop has constant boundaries.
747 // Use jlongs to avoid integer overflow.
748 int stride_con = cl->stride_con();
749 jlong init_con = cl->init_trip()->get_int();
750 jlong limit_con = cl->limit()->get_int();
751 julong trip_cnt = cl->trip_count();
752 jlong final_con = init_con + trip_cnt*stride_con;
753 int final_int = (int)final_con;
754 // The final value should be in integer range since the loop
755 // is counted and the limit was checked for overflow.
865 ini = init_t->_lo;
866 max = (julong)max_jint;
867 } else {
868 stride_p = -stride_con;
869 lim = init_t->_hi;
870 ini = limit_t->_lo;
871 max = (julong)min_jint;
872 }
873 julong range = lim - ini + stride_p;
874 if (range <= max) {
875 // Convert to integer expression if it is not overflow.
876 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1));
877 Node *range = phase->transform(new SubINode(in(Limit), in(Init)));
878 Node *bias = phase->transform(new AddINode(range, stride_m));
879 Node *trip = phase->transform(new DivINode(0, bias, in(Stride)));
880 Node *span = phase->transform(new MulINode(trip, in(Stride)));
881 return new AddINode(span, in(Init)); // exact limit
882 }
883
884 if (is_power_of_2(stride_p) || // divisor is 2^n
885 !Matcher::has_match_rule(Opcodes::Op_LoopLimit)) { // or no specialized Mach node?
886 // Convert to long expression to avoid integer overflow
887 // and let igvn optimizer convert this division.
888 //
889 Node* init = phase->transform( new ConvI2LNode(in(Init)));
890 Node* limit = phase->transform( new ConvI2LNode(in(Limit)));
891 Node* stride = phase->longcon(stride_con);
892 Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1));
893
894 Node *range = phase->transform(new SubLNode(limit, init));
895 Node *bias = phase->transform(new AddLNode(range, stride_m));
896 Node *span;
897 if (stride_con > 0 && is_power_of_2(stride_p)) {
898 // bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride)
899 // and avoid generating rounding for division. Zero trip guard should
900 // guarantee that init < limit but sometimes the guard is missing and
901 // we can get situation when init > limit. Note, for the empty loop
902 // optimization zero trip guard is generated explicitly which leaves
903 // only RCE predicate where exact limit is used and the predicate
904 // will simply fail forcing recompilation.
905 Node* neg_stride = phase->longcon(-stride_con);
922 int stride_con = phase->type(in(Stride))->is_int()->get_con();
923 if (stride_con == 1 || stride_con == -1)
924 return in(Limit);
925 return this;
926 }
927
928 //=============================================================================
929 //----------------------match_incr_with_optional_truncation--------------------
930 // Match increment with optional truncation:
931 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
932 // Return NULL for failure. Success returns the increment node.
933 Node* CountedLoopNode::match_incr_with_optional_truncation(
934 Node* expr, Node** trunc1, Node** trunc2, const TypeInt** trunc_type) {
935 // Quick cutouts:
936 if (expr == NULL || expr->req() != 3) return NULL;
937
938 Node *t1 = NULL;
939 Node *t2 = NULL;
940 const TypeInt* trunc_t = TypeInt::INT;
941 Node* n1 = expr;
942 Opcodes n1op = n1->Opcode();
943
944 // Try to strip (n1 & M) or (n1 << N >> N) from n1.
945 if (n1op == Opcodes::Op_AndI &&
946 n1->in(2)->is_Con() &&
947 n1->in(2)->bottom_type()->is_int()->get_con() == 0x7fff) {
948 // %%% This check should match any mask of 2**K-1.
949 t1 = n1;
950 n1 = t1->in(1);
951 n1op = n1->Opcode();
952 trunc_t = TypeInt::CHAR;
953 } else if (n1op == Opcodes::Op_RShiftI &&
954 n1->in(1) != NULL &&
955 n1->in(1)->Opcode() == Opcodes::Op_LShiftI &&
956 n1->in(2) == n1->in(1)->in(2) &&
957 n1->in(2)->is_Con()) {
958 jint shift = n1->in(2)->bottom_type()->is_int()->get_con();
959 // %%% This check should match any shift in [1..31].
960 if (shift == 16 || shift == 8) {
961 t1 = n1;
962 t2 = t1->in(1);
963 n1 = t2->in(1);
964 n1op = n1->Opcode();
965 if (shift == 16) {
966 trunc_t = TypeInt::SHORT;
967 } else if (shift == 8) {
968 trunc_t = TypeInt::BYTE;
969 }
970 }
971 }
972
973 // If (maybe after stripping) it is an AddI, we won:
974 if (n1op == Opcodes::Op_AddI) {
975 *trunc1 = t1;
976 *trunc2 = t2;
977 *trunc_type = trunc_t;
978 return n1;
979 }
980
981 // failed
982 return NULL;
983 }
984
985
986 //------------------------------filtered_type--------------------------------
987 // Return a type based on condition control flow
988 // A successful return will be a type that is restricted due
989 // to a series of dominating if-tests, such as:
990 // if (i < 10) {
991 // if (i > 0) {
992 // here: "i" type is [1..10)
993 // }
994 // }
1031 }
1032 return n_t;
1033 }
1034
1035
1036 //------------------------------filtered_type_from_dominators--------------------------------
1037 // Return a possibly more restrictive type for val based on condition control flow of dominators
1038 const TypeInt* PhaseIdealLoop::filtered_type_from_dominators( Node* val, Node *use_ctrl) {
1039 if (val->is_Con()) {
1040 return val->bottom_type()->is_int();
1041 }
1042 uint if_limit = 10; // Max number of dominating if's visited
1043 const TypeInt* rtn_t = NULL;
1044
1045 if (use_ctrl && use_ctrl != C->top()) {
1046 Node* val_ctrl = get_ctrl(val);
1047 uint val_dom_depth = dom_depth(val_ctrl);
1048 Node* pred = use_ctrl;
1049 uint if_cnt = 0;
1050 while (if_cnt < if_limit) {
1051 if ((pred->Opcode() == Opcodes::Op_IfTrue || pred->Opcode() == Opcodes::Op_IfFalse)) {
1052 if_cnt++;
1053 const TypeInt* if_t = IfNode::filtered_int_type(&_igvn, val, pred);
1054 if (if_t != NULL) {
1055 if (rtn_t == NULL) {
1056 rtn_t = if_t;
1057 } else {
1058 rtn_t = rtn_t->join(if_t)->is_int();
1059 }
1060 }
1061 }
1062 pred = idom(pred);
1063 if (pred == NULL || pred == C->top()) {
1064 break;
1065 }
1066 // Stop if going beyond definition block of val
1067 if (dom_depth(pred) < val_dom_depth) {
1068 break;
1069 }
1070 }
1071 }
1226 }
1227 }
1228
1229 // Use the new loop head instead of the old shared one
1230 _head = outer;
1231 phase->set_loop(_head, this);
1232 }
1233
1234 //------------------------------fix_parent-------------------------------------
1235 static void fix_parent( IdealLoopTree *loop, IdealLoopTree *parent ) {
1236 loop->_parent = parent;
1237 if( loop->_child ) fix_parent( loop->_child, loop );
1238 if( loop->_next ) fix_parent( loop->_next , parent );
1239 }
1240
1241 //------------------------------estimate_path_freq-----------------------------
1242 static float estimate_path_freq( Node *n ) {
1243 // Try to extract some path frequency info
1244 IfNode *iff;
1245 for( int i = 0; i < 50; i++ ) { // Skip through a bunch of uncommon tests
1246 Opcodes nop = n->Opcode();
1247 if( nop == Opcodes::Op_SafePoint ) { // Skip any safepoint
1248 n = n->in(0);
1249 continue;
1250 }
1251 if( nop == Opcodes::Op_CatchProj ) { // Get count from a prior call
1252 // Assume call does not always throw exceptions: means the call-site
1253 // count is also the frequency of the fall-through path.
1254 assert( n->is_CatchProj(), "" );
1255 if( ((CatchProjNode*)n)->_con != CatchProjNode::fall_through_index )
1256 return 0.0f; // Assume call exception path is rare
1257 Node *call = n->in(0)->in(0)->in(0);
1258 assert( call->is_Call(), "expect a call here" );
1259 const JVMState *jvms = ((CallNode*)call)->jvms();
1260 ciMethodData* methodData = jvms->method()->method_data();
1261 if (!methodData->is_mature()) return 0.0f; // No call-site data
1262 ciProfileData* data = methodData->bci_to_data(jvms->bci());
1263 if ((data == NULL) || !data->is_CounterData()) {
1264 // no call profile available, try call's control input
1265 n = n->in(0);
1266 continue;
1267 }
1268 return data->as_CounterData()->count()/FreqCountInvocations;
1269 }
1270 // See if there's a gating IF test
1271 Node *n_c = n->in(0);
1272 if( !n_c->is_If() ) break; // No estimate available
1273 iff = n_c->as_If();
1274 if( iff->_fcnt != COUNT_UNKNOWN ) // Have a valid count?
1275 // Compute how much count comes on this path
1276 return ((nop == Opcodes::Op_IfTrue) ? iff->_prob : 1.0f - iff->_prob) * iff->_fcnt;
1277 // Have no count info. Skip dull uncommon-trap like branches.
1278 if( (nop == Opcodes::Op_IfTrue && iff->_prob < PROB_LIKELY_MAG(5)) ||
1279 (nop == Opcodes::Op_IfFalse && iff->_prob > PROB_UNLIKELY_MAG(5)) )
1280 break;
1281 // Skip through never-taken branch; look for a real loop exit.
1282 n = iff->in(0);
1283 }
1284 return 0.0f; // No estimate available
1285 }
1286
1287 //------------------------------merge_many_backedges---------------------------
1288 // Merge all the backedges from the shared header into a private Region.
1289 // Feed that region as the one backedge to this loop.
1290 void IdealLoopTree::merge_many_backedges( PhaseIdealLoop *phase ) {
1291 uint i;
1292
1293 // Scan for the top 2 hottest backedges
1294 float hotcnt = 0.0f;
1295 float warmcnt = 0.0f;
1296 uint hot_idx = 0;
1297 // Loop starts at 2 because slot 1 is the fall-in path
1298 for( i = 2; i < _head->req(); i++ ) {
1299 float cnt = estimate_path_freq(_head->in(i));
1469 }
1470
1471 // Now recursively beautify nested loops
1472 if( _child ) result |= _child->beautify_loops( phase );
1473 if( _next ) result |= _next ->beautify_loops( phase );
1474 return result;
1475 }
1476
1477 //------------------------------allpaths_check_safepts----------------------------
1478 // Allpaths backwards scan from loop tail, terminating each path at first safepoint
1479 // encountered. Helper for check_safepts.
1480 void IdealLoopTree::allpaths_check_safepts(VectorSet &visited, Node_List &stack) {
1481 assert(stack.size() == 0, "empty stack");
1482 stack.push(_tail);
1483 visited.Clear();
1484 visited.set(_tail->_idx);
1485 while (stack.size() > 0) {
1486 Node* n = stack.pop();
1487 if (n->is_Call() && n->as_Call()->guaranteed_safepoint()) {
1488 // Terminate this path
1489 } else if (n->Opcode() == Opcodes::Op_SafePoint) {
1490 if (_phase->get_loop(n) != this) {
1491 if (_required_safept == NULL) _required_safept = new Node_List();
1492 _required_safept->push(n); // save the one closest to the tail
1493 }
1494 // Terminate this path
1495 } else {
1496 uint start = n->is_Region() ? 1 : 0;
1497 uint end = n->is_Region() && !n->is_Loop() ? n->req() : start + 1;
1498 for (uint i = start; i < end; i++) {
1499 Node* in = n->in(i);
1500 assert(in->is_CFG(), "must be");
1501 if (!visited.test_set(in->_idx) && is_member(_phase->get_loop(in))) {
1502 stack.push(in);
1503 }
1504 }
1505 }
1506 }
1507 }
1508
1509 //------------------------------check_safepts----------------------------
1559 // the idom path (which is rare), scans all predecessor control paths
1560 // from the tail to the head, terminating a path when a call or sfpt
1561 // is encountered, to find the ncsfpt's that are closest to the tail.
1562 //
1563 void IdealLoopTree::check_safepts(VectorSet &visited, Node_List &stack) {
1564 // Bottom up traversal
1565 IdealLoopTree* ch = _child;
1566 if (_child) _child->check_safepts(visited, stack);
1567 if (_next) _next ->check_safepts(visited, stack);
1568
1569 if (!_head->is_CountedLoop() && !_has_sfpt && _parent != NULL && !_irreducible) {
1570 bool has_call = false; // call on dom-path
1571 bool has_local_ncsfpt = false; // ncsfpt on dom-path at this loop depth
1572 Node* nonlocal_ncsfpt = NULL; // ncsfpt on dom-path at a deeper depth
1573 // Scan the dom-path nodes from tail to head
1574 for (Node* n = tail(); n != _head; n = _phase->idom(n)) {
1575 if (n->is_Call() && n->as_Call()->guaranteed_safepoint()) {
1576 has_call = true;
1577 _has_sfpt = 1; // Then no need for a safept!
1578 break;
1579 } else if (n->Opcode() == Opcodes::Op_SafePoint) {
1580 if (_phase->get_loop(n) == this) {
1581 has_local_ncsfpt = true;
1582 break;
1583 }
1584 if (nonlocal_ncsfpt == NULL) {
1585 nonlocal_ncsfpt = n; // save the one closest to the tail
1586 }
1587 } else {
1588 IdealLoopTree* nlpt = _phase->get_loop(n);
1589 if (this != nlpt) {
1590 // If at an inner loop tail, see if the inner loop has already
1591 // recorded seeing a call on the dom-path (and stop.) If not,
1592 // jump to the head of the inner loop.
1593 assert(is_member(nlpt), "nested loop");
1594 Node* tail = nlpt->_tail;
1595 if (tail->in(0)->is_If()) tail = tail->in(0);
1596 if (n == tail) {
1597 // If inner loop has call on dom-path, so does outer loop
1598 if (nlpt->_has_sfpt) {
1599 has_call = true;
1608 }
1609 }
1610 // Record safept's that this loop needs preserved when an
1611 // inner loop attempts to delete it's safepoints.
1612 if (_child != NULL && !has_call && !has_local_ncsfpt) {
1613 if (nonlocal_ncsfpt != NULL) {
1614 if (_required_safept == NULL) _required_safept = new Node_List();
1615 _required_safept->push(nonlocal_ncsfpt);
1616 } else {
1617 // Failed to find a suitable safept on the dom-path. Now use
1618 // an all paths walk from tail to head, looking for safepoints to preserve.
1619 allpaths_check_safepts(visited, stack);
1620 }
1621 }
1622 }
1623 }
1624
1625 //---------------------------is_deleteable_safept----------------------------
1626 // Is safept not required by an outer loop?
1627 bool PhaseIdealLoop::is_deleteable_safept(Node* sfpt) {
1628 assert(sfpt->Opcode() == Opcodes::Op_SafePoint, "");
1629 IdealLoopTree* lp = get_loop(sfpt)->_parent;
1630 while (lp != NULL) {
1631 Node_List* sfpts = lp->_required_safept;
1632 if (sfpts != NULL) {
1633 for (uint i = 0; i < sfpts->size(); i++) {
1634 if (sfpt == sfpts->at(i))
1635 return false;
1636 }
1637 }
1638 lp = lp->_parent;
1639 }
1640 return true;
1641 }
1642
1643 //---------------------------replace_parallel_iv-------------------------------
1644 // Replace parallel induction variable (parallel to trip counter)
1645 void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) {
1646 assert(loop->_head->is_CountedLoop(), "");
1647 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1648 if (!cl->is_valid_counted_loop())
1650 Node *incr = cl->incr();
1651 if (incr == NULL)
1652 return; // Dead loop?
1653 Node *init = cl->init_trip();
1654 Node *phi = cl->phi();
1655 int stride_con = cl->stride_con();
1656
1657 // Visit all children, looking for Phis
1658 for (DUIterator i = cl->outs(); cl->has_out(i); i++) {
1659 Node *out = cl->out(i);
1660 // Look for other phis (secondary IVs). Skip dead ones
1661 if (!out->is_Phi() || out == phi || !has_node(out))
1662 continue;
1663 PhiNode* phi2 = out->as_Phi();
1664 Node *incr2 = phi2->in( LoopNode::LoopBackControl );
1665 // Look for induction variables of the form: X += constant
1666 if (phi2->region() != loop->_head ||
1667 incr2->req() != 3 ||
1668 incr2->in(1) != phi2 ||
1669 incr2 == incr ||
1670 incr2->Opcode() != Opcodes::Op_AddI ||
1671 !incr2->in(2)->is_Con())
1672 continue;
1673
1674 // Check for parallel induction variable (parallel to trip counter)
1675 // via an affine function. In particular, count-down loops with
1676 // count-up array indices are common. We only RCE references off
1677 // the trip-counter, so we need to convert all these to trip-counter
1678 // expressions.
1679 Node *init2 = phi2->in( LoopNode::EntryControl );
1680 int stride_con2 = incr2->in(2)->get_int();
1681
1682 // The general case here gets a little tricky. We want to find the
1683 // GCD of all possible parallel IV's and make a new IV using this
1684 // GCD for the loop. Then all possible IVs are simple multiples of
1685 // the GCD. In practice, this will cover very few extra loops.
1686 // Instead we require 'stride_con2' to be a multiple of 'stride_con',
1687 // where +/-1 is the common case, but other integer multiples are
1688 // also easy to handle.
1689 int ratio_con = stride_con2/stride_con;
1690
1712 set_ctrl(ratio_idx, cl);
1713 Node* add = new AddINode(ratio_idx, diff);
1714 _igvn.register_new_node_with_optimizer(add);
1715 set_ctrl(add, cl);
1716 _igvn.replace_node( phi2, add );
1717 // Sometimes an induction variable is unused
1718 if (add->outcnt() == 0) {
1719 _igvn.remove_dead_node(add);
1720 }
1721 --i; // deleted this phi; rescan starting with next position
1722 continue;
1723 }
1724 }
1725 }
1726
1727 void IdealLoopTree::remove_safepoints(PhaseIdealLoop* phase, bool keep_one) {
1728 Node* keep = NULL;
1729 if (keep_one) {
1730 // Look for a safepoint on the idom-path.
1731 for (Node* i = tail(); i != _head; i = phase->idom(i)) {
1732 if (i->Opcode() == Opcodes::Op_SafePoint && phase->get_loop(i) == this) {
1733 keep = i;
1734 break; // Found one
1735 }
1736 }
1737 }
1738
1739 // Don't remove any safepoints if it is requested to keep a single safepoint and
1740 // no safepoint was found on idom-path. It is not safe to remove any safepoint
1741 // in this case since there's no safepoint dominating all paths in the loop body.
1742 bool prune = !keep_one || keep != NULL;
1743
1744 // Delete other safepoints in this loop.
1745 Node_List* sfpts = _safepts;
1746 if (prune && sfpts != NULL) {
1747 assert(keep == NULL || keep->Opcode() == Opcodes::Op_SafePoint, "not safepoint");
1748 for (uint i = 0; i < sfpts->size(); i++) {
1749 Node* n = sfpts->at(i);
1750 assert(phase->get_loop(n) == this, "");
1751 if (n != keep && phase->is_deleteable_safept(n)) {
1752 phase->lazy_replace(n, n->in(TypeFunc::Control));
1753 }
1754 }
1755 }
1756 }
1757
1758 //------------------------------counted_loop-----------------------------------
1759 // Convert to counted loops where possible
1760 void IdealLoopTree::counted_loop( PhaseIdealLoop *phase ) {
1761
1762 // For grins, set the inner-loop flag here
1763 if (!_child) {
1764 if (_head->is_Loop()) _head->as_Loop()->set_inner_loop();
1765 }
1766
1767 if (_head->is_CountedLoop() ||
1890 }
1891 }
1892
1893 //---------------------collect_potentially_useful_predicates-----------------------
1894 // Helper function to collect potentially useful predicates to prevent them from
1895 // being eliminated by PhaseIdealLoop::eliminate_useless_predicates
1896 void PhaseIdealLoop::collect_potentially_useful_predicates(
1897 IdealLoopTree * loop, Unique_Node_List &useful_predicates) {
1898 if (loop->_child) { // child
1899 collect_potentially_useful_predicates(loop->_child, useful_predicates);
1900 }
1901
1902 // self (only loops that we can apply loop predication may use their predicates)
1903 if (loop->_head->is_Loop() &&
1904 !loop->_irreducible &&
1905 !loop->tail()->is_top()) {
1906 LoopNode* lpn = loop->_head->as_Loop();
1907 Node* entry = lpn->in(LoopNode::EntryControl);
1908 Node* predicate_proj = find_predicate(entry); // loop_limit_check first
1909 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication
1910 assert(entry->in(0)->in(1)->in(1)->Opcode() == Opcodes::Op_Opaque1, "must be");
1911 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1912 entry = entry->in(0)->in(0);
1913 }
1914 predicate_proj = find_predicate(entry); // Predicate
1915 if (predicate_proj != NULL ) {
1916 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one
1917 }
1918 }
1919
1920 if (loop->_next) { // sibling
1921 collect_potentially_useful_predicates(loop->_next, useful_predicates);
1922 }
1923 }
1924
1925 //------------------------eliminate_useless_predicates-----------------------------
1926 // Eliminate all inserted predicates if they could not be used by loop predication.
1927 // Note: it will also eliminates loop limits check predicate since it also uses
1928 // Opaque1 node (see Parse::add_predicate()).
1929 void PhaseIdealLoop::eliminate_useless_predicates() {
1930 if (C->predicate_count() == 0)
1931 return; // no predicate left
1932
1933 Unique_Node_List useful_predicates; // to store useful predicates
1934 if (C->has_loops()) {
1935 collect_potentially_useful_predicates(_ltree_root->_child, useful_predicates);
1936 }
1937
1938 for (int i = C->predicate_count(); i > 0; i--) {
1939 Node * n = C->predicate_opaque1_node(i-1);
1940 assert(n->Opcode() == Opcodes::Op_Opaque1, "must be");
1941 if (!useful_predicates.member(n)) { // not in the useful list
1942 _igvn.replace_node(n, n->in(1));
1943 }
1944 }
1945 }
1946
1947 //------------------------process_expensive_nodes-----------------------------
1948 // Expensive nodes have their control input set to prevent the GVN
1949 // from commoning them and as a result forcing the resulting node to
1950 // be in a more frequent path. Use CFG information here, to change the
1951 // control inputs so that some expensive nodes can be commoned while
1952 // not executed more frequently.
1953 bool PhaseIdealLoop::process_expensive_nodes() {
1954 assert(OptimizeExpensiveOps, "optimization off?");
1955
1956 // Sort nodes to bring similar nodes together
1957 C->sort_expensive_nodes();
1958
1959 bool progress = false;
1960
2538 // Move (*nn) to (*pp)
2539 IdealLoopTree *hit = *nn;
2540 *nn = hit->_next;
2541 hit->_next = loop;
2542 *pp = loop;
2543 loop = hit;
2544 // Now try again to verify
2545 }
2546
2547 assert( _head == loop->_head , "mismatched loop head" );
2548 Node *tail = _tail; // Inline a non-updating version of
2549 while( !tail->in(0) ) // the 'tail()' call.
2550 tail = tail->in(1);
2551 assert( tail == loop->_tail, "mismatched loop tail" );
2552
2553 // Counted loops that are guarded should be able to find their guards
2554 if( _head->is_CountedLoop() && _head->as_CountedLoop()->is_main_loop() ) {
2555 CountedLoopNode *cl = _head->as_CountedLoop();
2556 Node *init = cl->init_trip();
2557 Node *ctrl = cl->in(LoopNode::EntryControl);
2558 assert( ctrl->Opcode() == Opcodes::Op_IfTrue || ctrl->Opcode() == Opcodes::Op_IfFalse, "" );
2559 Node *iff = ctrl->in(0);
2560 assert( iff->Opcode() == Opcodes::Op_If, "" );
2561 Node *bol = iff->in(1);
2562 assert( bol->Opcode() == Opcodes::Op_Bool, "" );
2563 Node *cmp = bol->in(1);
2564 assert( cmp->Opcode() == Opcodes::Op_CmpI, "" );
2565 Node *add = cmp->in(1);
2566 Node *opaq;
2567 if( add->Opcode() == Opcodes::Op_Opaque1 ) {
2568 opaq = add;
2569 } else {
2570 assert( add->Opcode() == Opcodes::Op_AddI || add->Opcode() == Opcodes::Op_ConI , "" );
2571 assert( add == init, "" );
2572 opaq = cmp->in(2);
2573 }
2574 assert( opaq->Opcode() == Opcodes::Op_Opaque1, "" );
2575
2576 }
2577
2578 if (_child != NULL) _child->verify_tree(loop->_child, this);
2579 if (_next != NULL) _next ->verify_tree(loop->_next, parent);
2580 // Innermost loops need to verify loop bodies,
2581 // but only if no 'major_progress'
2582 int fail = 0;
2583 if (!Compile::current()->major_progress() && _child == NULL) {
2584 for( uint i = 0; i < _body.size(); i++ ) {
2585 Node *n = _body.at(i);
2586 if (n->outcnt() == 0) continue; // Ignore dead
2587 uint j;
2588 for( j = 0; j < loop->_body.size(); j++ )
2589 if( loop->_body.at(j) == n )
2590 break;
2591 if( j == loop->_body.size() ) { // Not found in loop body
2592 // Last ditch effort to avoid assertion: Its possible that we
2593 // have some users (so outcnt not zero) but are still dead.
2594 // Try to find from root.
2948 l->_next = p->_child; // Put self on parents 'next child'
2949 p->_child = l; // Make self as first child of parent
2950 l = p; // Now walk up the parent chain
2951 p = l->_parent;
2952 }
2953 } else {
2954 // Note that it is possible for a LoopNode to reach here, if the
2955 // backedge has been made unreachable (hence the LoopNode no longer
2956 // denotes a Loop, and will eventually be removed).
2957
2958 // Record tightest enclosing loop for self. Mark as post-visited.
2959 set_loop(n, innermost);
2960 // Also record has_call flag early on
2961 if( innermost ) {
2962 if( n->is_Call() && !n->is_CallLeaf() && !n->is_macro() ) {
2963 // Do not count uncommon calls
2964 if( !n->is_CallStaticJava() || !n->as_CallStaticJava()->_name ) {
2965 Node *iff = n->in(0)->in(0);
2966 // No any calls for vectorized loops.
2967 if( UseSuperWord || !iff->is_If() ||
2968 (n->in(0)->Opcode() == Opcodes::Op_IfFalse &&
2969 (1.0 - iff->as_If()->_prob) >= 0.01) ||
2970 (iff->as_If()->_prob >= 0.01) )
2971 innermost->_has_call = 1;
2972 }
2973 } else if( n->is_Allocate() && n->as_Allocate()->_is_scalar_replaceable ) {
2974 // Disable loop optimizations if the loop has a scalar replaceable
2975 // allocation. This disabling may cause a potential performance lost
2976 // if the allocation is not eliminated for some reason.
2977 innermost->_allow_optimizations = false;
2978 innermost->_has_call = 1; // = true
2979 } else if (n->Opcode() == Opcodes::Op_SafePoint) {
2980 // Record all safepoints in this loop.
2981 if (innermost->_safepts == NULL) innermost->_safepts = new Node_List();
2982 innermost->_safepts->push(n);
2983 }
2984 }
2985 }
2986
2987 // Flag as post-visited now
2988 set_postvisited(n);
2989 return pre_order;
2990 }
2991
2992
2993 //------------------------------build_loop_early-------------------------------
2994 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
2995 // First pass computes the earliest controlling node possible. This is the
2996 // controlling input with the deepest dominating depth.
2997 void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
2998 while (worklist.size() != 0) {
2999 // Use local variables nstack_top_n & nstack_top_i to cache values
3009 if (i == 0) { // Pre-process the node.
3010 if( has_node(n) && // Have either loop or control already?
3011 !has_ctrl(n) ) { // Have loop picked out already?
3012 // During "merge_many_backedges" we fold up several nested loops
3013 // into a single loop. This makes the members of the original
3014 // loop bodies pointing to dead loops; they need to move up
3015 // to the new UNION'd larger loop. I set the _head field of these
3016 // dead loops to NULL and the _parent field points to the owning
3017 // loop. Shades of UNION-FIND algorithm.
3018 IdealLoopTree *ilt;
3019 while( !(ilt = get_loop(n))->_head ) {
3020 // Normally I would use a set_loop here. But in this one special
3021 // case, it is legal (and expected) to change what loop a Node
3022 // belongs to.
3023 _nodes.map(n->_idx, (Node*)(ilt->_parent) );
3024 }
3025 // Remove safepoints ONLY if I've already seen I don't need one.
3026 // (the old code here would yank a 2nd safepoint after seeing a
3027 // first one, even though the 1st did not dominate in the loop body
3028 // and thus could be avoided indefinitely)
3029 if( !_verify_only && !_verify_me && ilt->_has_sfpt && n->Opcode() == Opcodes::Op_SafePoint &&
3030 is_deleteable_safept(n)) {
3031 Node *in = n->in(TypeFunc::Control);
3032 lazy_replace(n,in); // Pull safepoint now
3033 if (ilt->_safepts != NULL) {
3034 ilt->_safepts->yank(n);
3035 }
3036 // Carry on with the recursion "as if" we are walking
3037 // only the control input
3038 if( !visited.test_set( in->_idx ) ) {
3039 worklist.push(in); // Visit this guy later, using worklist
3040 }
3041 // Get next node from nstack:
3042 // - skip n's inputs processing by setting i > cnt;
3043 // - we also will not call set_early_ctrl(n) since
3044 // has_node(n) == true (see the condition above).
3045 i = cnt + 1;
3046 }
3047 }
3048 } // if (i == 0)
3049
3218 Node* ctrl = cl->in(LoopNode::EntryControl);
3219 if (ctrl == NULL || (!ctrl->is_IfTrue() && !ctrl->is_IfFalse())) {
3220 return false;
3221 }
3222 Node* iffm = ctrl->in(0);
3223 if (iffm == NULL || !iffm->is_If()) {
3224 return false;
3225 }
3226 Node* bolzm = iffm->in(1);
3227 if (bolzm == NULL || !bolzm->is_Bool()) {
3228 return false;
3229 }
3230 Node* cmpzm = bolzm->in(1);
3231 if (cmpzm == NULL || !cmpzm->is_Cmp()) {
3232 return false;
3233 }
3234 // compares can get conditionally flipped
3235 bool found_opaque = false;
3236 for (uint i = 1; i < cmpzm->req(); i++) {
3237 Node* opnd = cmpzm->in(i);
3238 if (opnd && opnd->Opcode() == Opcodes::Op_Opaque1) {
3239 found_opaque = true;
3240 break;
3241 }
3242 }
3243 if (!found_opaque) {
3244 return false;
3245 }
3246 return true;
3247 }
3248
3249 //------------------------------get_late_ctrl----------------------------------
3250 // Compute latest legal control.
3251 Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) {
3252 assert(early != NULL, "early control should not be NULL");
3253
3254 Node* LCA = compute_lca_of_uses(n, early);
3255 #ifdef ASSERT
3256 if (LCA == C->root() && LCA != early) {
3257 // def doesn't dominate uses so print some useful debugging output
3258 compute_lca_of_uses(n, early, true);
3442 if (nstack.is_empty()) {
3443 // Finished all nodes on stack.
3444 // Process next node on the worklist.
3445 break;
3446 }
3447 // Get saved parent node and next use's index. Visit the rest of uses.
3448 n = nstack.node();
3449 cnt = n->outcnt();
3450 i = nstack.index();
3451 nstack.pop();
3452 }
3453 }
3454 }
3455 }
3456
3457 //------------------------------build_loop_late_post---------------------------
3458 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
3459 // Second pass finds latest legal placement, and ideal loop placement.
3460 void PhaseIdealLoop::build_loop_late_post( Node *n ) {
3461
3462 if (n->req() == 2 && (n->Opcode() == Opcodes::Op_ConvI2L || n->Opcode() == Opcodes::Op_CastII) && !C->major_progress() && !_verify_only) {
3463 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops.
3464 }
3465
3466 #ifdef ASSERT
3467 if (_verify_only && !n->is_CFG()) {
3468 // Check def-use domination.
3469 compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
3470 }
3471 #endif
3472
3473 // CFG and pinned nodes already handled
3474 if( n->in(0) ) {
3475 if( n->in(0)->is_top() ) return; // Dead?
3476
3477 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
3478 // _must_ be pinned (they have to observe their control edge of course).
3479 // Unlike Stores (which modify an unallocable resource, the memory
3480 // state), Mods/Loads can float around. So free them up.
3481 bool pinned = true;
3482 switch( n->Opcode() ) {
3483 case Opcodes::Op_DivI:
3484 case Opcodes::Op_DivF:
3485 case Opcodes::Op_DivD:
3486 case Opcodes::Op_ModI:
3487 case Opcodes::Op_ModF:
3488 case Opcodes::Op_ModD:
3489 case Opcodes::Op_LoadB: // Same with Loads; they can sink
3490 case Opcodes::Op_LoadUB: // during loop optimizations.
3491 case Opcodes::Op_LoadUS:
3492 case Opcodes::Op_LoadD:
3493 case Opcodes::Op_LoadF:
3494 case Opcodes::Op_LoadI:
3495 case Opcodes::Op_LoadKlass:
3496 case Opcodes::Op_LoadNKlass:
3497 case Opcodes::Op_LoadL:
3498 case Opcodes::Op_LoadS:
3499 case Opcodes::Op_LoadP:
3500 case Opcodes::Op_LoadN:
3501 case Opcodes::Op_LoadRange:
3502 case Opcodes::Op_LoadD_unaligned:
3503 case Opcodes::Op_LoadL_unaligned:
3504 case Opcodes::Op_StrComp: // Does a bunch of load-like effects
3505 case Opcodes::Op_StrEquals:
3506 case Opcodes::Op_StrIndexOf:
3507 case Opcodes::Op_StrIndexOfChar:
3508 case Opcodes::Op_AryEq:
3509 case Opcodes::Op_HasNegatives:
3510 pinned = false;
3511 }
3512 if( pinned ) {
3513 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
3514 if( !chosen_loop->_child ) // Inner loop?
3515 chosen_loop->_body.push(n); // Collect inner loops
3516 return;
3517 }
3518 } else { // No slot zero
3519 if( n->is_CFG() ) { // CFG with no slot 0 is dead
3520 _nodes.map(n->_idx,0); // No block setting, it's globally dead
3521 return;
3522 }
3523 assert(!n->is_CFG() || n->outcnt() == 0, "");
3524 }
3525
3526 // Do I have a "safe range" I can select over?
3527 Node *early = get_ctrl(n);// Early location already computed
3528
3529 // Compute latest point this Node can go
|