< prev index next >

src/hotspot/share/opto/loopnode.cpp

Print this page




 307   }
 308   outer_ilt->_next = loop->_next;
 309   outer_ilt->_parent = parent;
 310   outer_ilt->_child = loop;
 311   outer_ilt->_nest = loop->_nest;
 312   loop->_parent = outer_ilt;
 313   loop->_next = NULL;
 314   loop->_nest++;
 315 
 316   set_loop(iffalse, outer_ilt);
 317   register_control(outer_le, outer_ilt, iffalse);
 318   register_control(outer_ift, outer_ilt, outer_le);
 319   set_idom(outer_iff, outer_le, dom_depth(outer_le));
 320   _igvn.register_new_node_with_optimizer(outer_l);
 321   set_loop(outer_l, outer_ilt);
 322   set_idom(outer_l, init_control, dom_depth(init_control)+1);
 323 
 324   return outer_ilt;
 325 }
 326 

























 327 //------------------------------is_counted_loop--------------------------------
 328 bool PhaseIdealLoop::is_counted_loop(Node* x, IdealLoopTree*& loop) {
 329   PhaseGVN *gvn = &_igvn;
 330 
 331   // Counted loop head must be a good RegionNode with only 3 not NULL
 332   // control input edges: Self, Entry, LoopBack.
 333   if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {
 334     return false;
 335   }
 336   Node *init_control = x->in(LoopNode::EntryControl);
 337   Node *back_control = x->in(LoopNode::LoopBackControl);
 338   if (init_control == NULL || back_control == NULL)    // Partially dead
 339     return false;
 340   // Must also check for TOP when looking for a dead loop
 341   if (init_control->is_top() || back_control->is_top())
 342     return false;
 343 
 344   // Allow funny placement of Safepoint
 345   if (back_control->Opcode() == Op_SafePoint) {
 346     if (LoopStripMiningIter != 0) {


 523       (bt == BoolTest::ne && stride_con != 1 && stride_con != -1) ||
 524       // Count down loop rolls through MAXINT
 525       ((bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0) ||
 526       // Count up loop rolls through MININT
 527       ((bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0)) {
 528     return false; // Bail out
 529   }
 530 
 531   const TypeInt* init_t = gvn->type(init_trip)->is_int();
 532 
 533   if (stride_con > 0) {
 534     jlong init_p = (jlong)init_t->_lo + stride_con;
 535     if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
 536       return false; // cyclic loop or this loop trips only once
 537   } else {
 538     jlong init_p = (jlong)init_t->_hi + stride_con;
 539     if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
 540       return false; // cyclic loop or this loop trips only once
 541   }
 542 
 543   if (phi_incr != NULL) {
 544     // check if there is a possiblity of IV overflowing after the first increment
 545     if (stride_con > 0) {
 546       if (init_t->_hi > max_jint - stride_con) {
 547         return false;
 548       }
 549     } else {
 550       if (init_t->_lo < min_jint - stride_con) {
 551         return false;
 552       }
 553     }
 554   }
 555 
 556   // =================================================
 557   // ---- SUCCESS!   Found A Trip-Counted Loop!  -----
 558   //
 559   assert(x->Opcode() == Op_Loop, "regular loops only");
 560   C->print_method(PHASE_BEFORE_CLOOPS, 3);
 561 
 562   Node *hook = new Node(6);
 563 


 614 #endif
 615       return false;
 616     }
 617 
 618     IfNode* check_iff = limit_check_proj->in(0)->as_If();
 619 
 620     if (!is_dominator(get_ctrl(limit), check_iff->in(0))) {
 621       return false;
 622     }
 623 
 624     Node* cmp_limit;
 625     Node* bol;
 626 
 627     if (stride_con > 0) {
 628       cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
 629       bol = new BoolNode(cmp_limit, BoolTest::le);
 630     } else {
 631       cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
 632       bol = new BoolNode(cmp_limit, BoolTest::ge);
 633     }
 634     cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
 635     bol = _igvn.register_new_node_with_optimizer(bol);
 636     set_subtree_ctrl(bol);
 637 
 638     // Replace condition in original predicate but preserve Opaque node
 639     // so that previous predicates could be found.
 640     assert(check_iff->in(1)->Opcode() == Op_Conv2B &&
 641            check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");
 642     Node* opq = check_iff->in(1)->in(1);
 643     _igvn.replace_input_of(opq, 1, bol);
 644     // Update ctrl.
 645     set_ctrl(opq, check_iff->in(0));
 646     set_ctrl(check_iff->in(1), check_iff->in(0));
 647 
 648 #ifndef PRODUCT
 649     // report that the loop predication has been actually performed
 650     // for this loop











 651     if (TraceLoopLimitCheck) {
 652       tty->print_cr("Counted Loop Limit Check generated:");
 653       debug_only( bol->dump(2); )

 654     }
 655 #endif






























 656   }
 657 
 658   if (phi_incr != NULL) {
 659     // If compare points directly to the phi we need to adjust
 660     // the compare so that it points to the incr. Limit have
 661     // to be adjusted to keep trip count the same and we
 662     // should avoid int overflow.
 663     //
 664     //   i = init; do {} while(i++ < limit);
 665     // is converted to
 666     //   i = init; do {} while(++i < limit+1);
 667     //
 668     limit = gvn->transform(new AddINode(limit, stride));
 669   }
 670 
 671   // Now we need to canonicalize loop condition.
 672   if (bt == BoolTest::ne) {
 673     assert(stride_con == 1 || stride_con == -1, "simple increment only");
 674     // 'ne' can be replaced with 'lt' only when init < limit.
 675     if (stride_con > 0 && init_t->_hi < limit_t->_lo)
 676       bt = BoolTest::lt;
 677     // 'ne' can be replaced with 'gt' only when init > limit.
 678     if (stride_con < 0 && init_t->_lo > limit_t->_hi)
 679       bt = BoolTest::gt;
 680   }
 681 
 682   if (incl_limit) {
 683     // The limit check guaranties that 'limit <= (max_jint - stride)' so
 684     // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
 685     //
 686     Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
 687     limit = gvn->transform(new AddINode(limit, one));
 688     if (bt == BoolTest::le)
 689       bt = BoolTest::lt;
 690     else if (bt == BoolTest::ge)
 691       bt = BoolTest::gt;
 692     else
 693       ShouldNotReachHere();
 694   }
 695   set_subtree_ctrl( limit );
 696 
 697   if (LoopStripMiningIter == 0) {
 698     // Check for SafePoint on backedge and remove
 699     Node *sfpt = x->in(LoopNode::LoopBackControl);
 700     if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
 701       lazy_replace( sfpt, iftrue );


2387 
2388   // Recursively
2389   assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2390   assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2391   if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2392   if (loop->_next)  loop->_next ->counted_loop(phase);
2393 }
2394 
2395 #ifndef PRODUCT
2396 //------------------------------dump_head--------------------------------------
2397 // Dump 1 liner for loop header info
2398 void IdealLoopTree::dump_head( ) const {
2399   for (uint i=0; i<_nest; i++)
2400     tty->print("  ");
2401   tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2402   if (_irreducible) tty->print(" IRREDUCIBLE");
2403   Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2404   Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2405   if (predicate != NULL ) {
2406     tty->print(" limit_check");
2407     entry = entry->in(0)->in(0);
2408   }
2409   if (UseLoopPredicate) {
2410     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2411     if (entry != NULL) {
2412       tty->print(" predicated");
2413       entry = PhaseIdealLoop::skip_loop_predicates(entry);
2414     }
2415   }
2416   if (UseProfiledLoopPredicate) {
2417     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2418     if (entry != NULL) {
2419       tty->print(" profile_predicated");
2420     }
2421   }
2422   if (_head->is_CountedLoop()) {
2423     CountedLoopNode *cl = _head->as_CountedLoop();
2424     tty->print(" counted");
2425 
2426     Node* init_n = cl->init_trip();
2427     if (init_n  != NULL &&  init_n->is_Con())




 307   }
 308   outer_ilt->_next = loop->_next;
 309   outer_ilt->_parent = parent;
 310   outer_ilt->_child = loop;
 311   outer_ilt->_nest = loop->_nest;
 312   loop->_parent = outer_ilt;
 313   loop->_next = NULL;
 314   loop->_nest++;
 315 
 316   set_loop(iffalse, outer_ilt);
 317   register_control(outer_le, outer_ilt, iffalse);
 318   register_control(outer_ift, outer_ilt, outer_le);
 319   set_idom(outer_iff, outer_le, dom_depth(outer_le));
 320   _igvn.register_new_node_with_optimizer(outer_l);
 321   set_loop(outer_l, outer_ilt);
 322   set_idom(outer_l, init_control, dom_depth(init_control)+1);
 323 
 324   return outer_ilt;
 325 }
 326 
 327 void PhaseIdealLoop::insert_loop_limit_check(ProjNode* limit_check_proj, Node* cmp_limit, Node* bol) {
 328   Node* new_predicate_proj = create_new_if_for_predicate(limit_check_proj, NULL,
 329                                                          Deoptimization::Reason_loop_limit_check,
 330                                                          Op_If);
 331   Node* iff = new_predicate_proj->in(0);
 332   assert(iff->Opcode() == Op_If, "bad graph shape");
 333   Node* conv = iff->in(1);
 334   assert(conv->Opcode() == Op_Conv2B, "bad graph shape");
 335   Node* opaq = conv->in(1);
 336   assert(opaq->Opcode() == Op_Opaque1, "bad graph shape");
 337   cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
 338   bol = _igvn.register_new_node_with_optimizer(bol);
 339   set_subtree_ctrl(bol);
 340   _igvn.replace_input_of(iff, 1, bol);
 341   
 342 #ifndef PRODUCT
 343   // report that the loop predication has been actually performed
 344   // for this loop
 345   if (TraceLoopLimitCheck) {
 346     tty->print_cr("Counted Loop Limit Check generated:");
 347     debug_only( bol->dump(2); )
 348   }
 349 #endif
 350 }
 351 
 352 //------------------------------is_counted_loop--------------------------------
 353 bool PhaseIdealLoop::is_counted_loop(Node* x, IdealLoopTree*& loop) {
 354   PhaseGVN *gvn = &_igvn;
 355 
 356   // Counted loop head must be a good RegionNode with only 3 not NULL
 357   // control input edges: Self, Entry, LoopBack.
 358   if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {
 359     return false;
 360   }
 361   Node *init_control = x->in(LoopNode::EntryControl);
 362   Node *back_control = x->in(LoopNode::LoopBackControl);
 363   if (init_control == NULL || back_control == NULL)    // Partially dead
 364     return false;
 365   // Must also check for TOP when looking for a dead loop
 366   if (init_control->is_top() || back_control->is_top())
 367     return false;
 368 
 369   // Allow funny placement of Safepoint
 370   if (back_control->Opcode() == Op_SafePoint) {
 371     if (LoopStripMiningIter != 0) {


 548       (bt == BoolTest::ne && stride_con != 1 && stride_con != -1) ||
 549       // Count down loop rolls through MAXINT
 550       ((bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0) ||
 551       // Count up loop rolls through MININT
 552       ((bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0)) {
 553     return false; // Bail out
 554   }
 555 
 556   const TypeInt* init_t = gvn->type(init_trip)->is_int();
 557 
 558   if (stride_con > 0) {
 559     jlong init_p = (jlong)init_t->_lo + stride_con;
 560     if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
 561       return false; // cyclic loop or this loop trips only once
 562   } else {
 563     jlong init_p = (jlong)init_t->_hi + stride_con;
 564     if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
 565       return false; // cyclic loop or this loop trips only once
 566   }
 567 
 568   if (phi_incr != NULL && bt != BoolTest::ne) {
 569     // check if there is a possiblity of IV overflowing after the first increment
 570     if (stride_con > 0) {
 571       if (init_t->_hi > max_jint - stride_con) {
 572         return false;
 573       }
 574     } else {
 575       if (init_t->_lo < min_jint - stride_con) {
 576         return false;
 577       }
 578     }
 579   }
 580 
 581   // =================================================
 582   // ---- SUCCESS!   Found A Trip-Counted Loop!  -----
 583   //
 584   assert(x->Opcode() == Op_Loop, "regular loops only");
 585   C->print_method(PHASE_BEFORE_CLOOPS, 3);
 586 
 587   Node *hook = new Node(6);
 588 


 639 #endif
 640       return false;
 641     }
 642 
 643     IfNode* check_iff = limit_check_proj->in(0)->as_If();
 644 
 645     if (!is_dominator(get_ctrl(limit), check_iff->in(0))) {
 646       return false;
 647     }
 648 
 649     Node* cmp_limit;
 650     Node* bol;
 651 
 652     if (stride_con > 0) {
 653       cmp_limit = new CmpINode(limit, _igvn.intcon(max_jint - stride_m));
 654       bol = new BoolNode(cmp_limit, BoolTest::le);
 655     } else {
 656       cmp_limit = new CmpINode(limit, _igvn.intcon(min_jint - stride_m));
 657       bol = new BoolNode(cmp_limit, BoolTest::ge);
 658     }



 659 
 660     insert_loop_limit_check(limit_check_proj, cmp_limit, bol);
 661   }







 662 
 663   // Now we need to canonicalize loop condition.
 664   if (bt == BoolTest::ne) {
 665     assert(stride_con == 1 || stride_con == -1, "simple increment only");
 666     if (stride_con > 0 && init_t->_hi < limit_t->_lo) {
 667       // 'ne' can be replaced with 'lt' only when init < limit.
 668       bt = BoolTest::lt;
 669     } else if (stride_con < 0 && init_t->_lo > limit_t->_hi) {
 670       // 'ne' can be replaced with 'gt' only when init > limit.
 671       bt = BoolTest::gt;
 672     } else {
 673       ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);
 674       if (!limit_check_proj) {
 675         // The limit check predicate is not generated if this method trapped here before.
 676 #ifdef ASSERT
 677         if (TraceLoopLimitCheck) {
 678           tty->print("missing loop limit check:");
 679           loop->dump_head();
 680           x->dump(1);
 681         }
 682 #endif
 683         return false;
 684       }
 685       IfNode* check_iff = limit_check_proj->in(0)->as_If();
 686 
 687       if (!is_dominator(get_ctrl(limit), check_iff->in(0)) ||
 688           !is_dominator(get_ctrl(init_trip), check_iff->in(0))) {
 689         return false;
 690       }
 691 
 692       Node* cmp_limit;
 693       Node* bol;
 694 
 695       if (stride_con > 0) {
 696         cmp_limit = new CmpINode(init_trip, limit);
 697         bol = new BoolNode(cmp_limit, BoolTest::lt);
 698       } else {
 699         cmp_limit = new CmpINode(init_trip, limit);
 700         bol = new BoolNode(cmp_limit, BoolTest::gt);
 701       }
 702 
 703       insert_loop_limit_check(limit_check_proj, cmp_limit, bol);
 704 
 705       if (stride_con > 0) {
 706         // 'ne' can be replaced with 'lt' only when init < limit.
 707         bt = BoolTest::lt;
 708       } else if (stride_con < 0) {
 709         // 'ne' can be replaced with 'gt' only when init > limit.
 710         bt = BoolTest::gt;
 711       }
 712     }
 713   }
 714 
 715   if (phi_incr != NULL) {
 716     // If compare points directly to the phi we need to adjust
 717     // the compare so that it points to the incr. Limit have
 718     // to be adjusted to keep trip count the same and we
 719     // should avoid int overflow.
 720     //
 721     //   i = init; do {} while(i++ < limit);
 722     // is converted to
 723     //   i = init; do {} while(++i < limit+1);
 724     //
 725     limit = gvn->transform(new AddINode(limit, stride));
 726   }
 727 











 728   if (incl_limit) {
 729     // The limit check guaranties that 'limit <= (max_jint - stride)' so
 730     // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
 731     //
 732     Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);
 733     limit = gvn->transform(new AddINode(limit, one));
 734     if (bt == BoolTest::le)
 735       bt = BoolTest::lt;
 736     else if (bt == BoolTest::ge)
 737       bt = BoolTest::gt;
 738     else
 739       ShouldNotReachHere();
 740   }
 741   set_subtree_ctrl( limit );
 742 
 743   if (LoopStripMiningIter == 0) {
 744     // Check for SafePoint on backedge and remove
 745     Node *sfpt = x->in(LoopNode::LoopBackControl);
 746     if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {
 747       lazy_replace( sfpt, iftrue );


2433 
2434   // Recursively
2435   assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2436   assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2437   if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2438   if (loop->_next)  loop->_next ->counted_loop(phase);
2439 }
2440 
2441 #ifndef PRODUCT
2442 //------------------------------dump_head--------------------------------------
2443 // Dump 1 liner for loop header info
2444 void IdealLoopTree::dump_head( ) const {
2445   for (uint i=0; i<_nest; i++)
2446     tty->print("  ");
2447   tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2448   if (_irreducible) tty->print(" IRREDUCIBLE");
2449   Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2450   Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2451   if (predicate != NULL ) {
2452     tty->print(" limit_check");
2453     entry = PhaseIdealLoop::skip_loop_predicates(entry);
2454   }
2455   if (UseLoopPredicate) {
2456     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2457     if (entry != NULL) {
2458       tty->print(" predicated");
2459       entry = PhaseIdealLoop::skip_loop_predicates(entry);
2460     }
2461   }
2462   if (UseProfiledLoopPredicate) {
2463     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2464     if (entry != NULL) {
2465       tty->print(" profile_predicated");
2466     }
2467   }
2468   if (_head->is_CountedLoop()) {
2469     CountedLoopNode *cl = _head->as_CountedLoop();
2470     tty->print(" counted");
2471 
2472     Node* init_n = cl->init_trip();
2473     if (init_n  != NULL &&  init_n->is_Con())


< prev index next >