< prev index next >

src/hotspot/share/opto/loopPredicate.cpp

Print this page




  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "opto/loopnode.hpp"
  27 #include "opto/addnode.hpp"
  28 #include "opto/callnode.hpp"
  29 #include "opto/connode.hpp"
  30 #include "opto/convertnode.hpp"
  31 #include "opto/loopnode.hpp"
  32 #include "opto/matcher.hpp"
  33 #include "opto/mulnode.hpp"
  34 #include "opto/opaquenode.hpp"
  35 #include "opto/rootnode.hpp"
  36 #include "opto/subnode.hpp"


  37 
  38 /*
  39  * The general idea of Loop Predication is to insert a predicate on the entry
  40  * path to a loop, and raise a uncommon trap if the check of the condition fails.
  41  * The condition checks are promoted from inside the loop body, and thus
  42  * the checks inside the loop could be eliminated. Currently, loop predication
  43  * optimization has been applied to remove array range check and loop invariant
  44  * checks (such as null checks).
  45 */
  46 
  47 //-------------------------------register_control-------------------------
  48 void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {
  49   assert(n->is_CFG(), "must be control node");
  50   _igvn.register_new_node_with_optimizer(n);
  51   loop->_body.push(n);
  52   set_loop(n, loop);
  53   // When called from beautify_loops() idom is not constructed yet.
  54   if (_idom != NULL) {
  55     set_idom(n, pred, dom_depth(pred));
  56   }


 301 
 302 // Clone loop predicates to cloned loops (peeled, unswitched, split_if).
 303 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry,
 304                                                 bool clone_limit_check,
 305                                                 PhaseIdealLoop* loop_phase,
 306                                                 PhaseIterGVN* igvn) {
 307 #ifdef ASSERT
 308   if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) {
 309     if (new_entry != NULL)
 310       new_entry->dump();
 311     assert(false, "not IfTrue, IfFalse, Region or SafePoint");
 312   }
 313 #endif
 314   // Search original predicates
 315   Node* entry = old_entry;
 316   ProjNode* limit_check_proj = NULL;
 317   limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 318   if (limit_check_proj != NULL) {
 319     entry = entry->in(0)->in(0);
 320   }








 321   if (UseLoopPredicate) {
 322     ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);

 323     if (predicate_proj != NULL) { // right pattern that can be used by loop predication
 324       // clone predicate
 325       new_entry = clone_predicate(predicate_proj, new_entry,
 326                                   Deoptimization::Reason_predicate,
 327                                   loop_phase, igvn);
 328       assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate");
 329       if (TraceLoopPredicate) {
 330         tty->print("Loop Predicate cloned: ");
 331         debug_only( new_entry->in(0)->dump(); )
 332       }
 333     }










 334   }
 335   if (limit_check_proj != NULL && clone_limit_check) {
 336     // Clone loop limit check last to insert it before loop.
 337     // Don't clone a limit check which was already finalized
 338     // for this counted loop (only one limit check is needed).
 339     new_entry = clone_predicate(limit_check_proj, new_entry,
 340                                 Deoptimization::Reason_loop_limit_check,
 341                                 loop_phase, igvn);
 342     assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check");
 343     if (TraceLoopLimitCheck) {
 344       tty->print("Loop Limit Check cloned: ");
 345       debug_only( new_entry->in(0)->dump(); )
 346     }
 347   }
 348   return new_entry;
 349 }
 350 
 351 //--------------------------skip_loop_predicates------------------------------
 352 // Skip related predicates.
 353 Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) {
 354   Node* predicate = NULL;
 355   predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 356   if (predicate != NULL) {
 357     entry = entry->in(0)->in(0);
 358   }
 359   if (UseLoopPredicate) {
 360     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 361     if (predicate != NULL) { // right pattern that can be used by loop predication
 362       IfNode* iff = entry->in(0)->as_If();
 363       ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
 364       Node* rgn = uncommon_proj->unique_ctrl_out();
 365       assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
 366       entry = entry->in(0)->in(0);
 367       while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
 368         uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
 369         if (uncommon_proj->unique_ctrl_out() != rgn)
 370           break;
 371         entry = entry->in(0)->in(0);
 372       }



















 373     }
 374   }
 375   return entry;
 376 }
 377 
 378 //--------------------------find_predicate_insertion_point-------------------
 379 // Find a good location to insert a predicate
 380 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
 381   if (start_c == NULL || !start_c->is_Proj())
 382     return NULL;
 383   if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {
 384     return start_c->as_Proj();
 385   }
 386   return NULL;
 387 }
 388 
 389 //--------------------------find_predicate------------------------------------
 390 // Find a predicate
 391 Node* PhaseIdealLoop::find_predicate(Node* entry) {
 392   Node* predicate = NULL;
 393   predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 394   if (predicate != NULL) { // right pattern that can be used by loop predication
 395     return entry;
 396   }
 397   if (UseLoopPredicate) {
 398     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 399     if (predicate != NULL) { // right pattern that can be used by loop predication
 400       return entry;
 401     }
 402   }






 403   return NULL;
 404 }
 405 
 406 //------------------------------Invariance-----------------------------------
 407 // Helper class for loop_predication_impl to compute invariance on the fly and
 408 // clone invariants.
 409 class Invariance : public StackObj {
 410   VectorSet _visited, _invariant;
 411   Node_Stack _stack;
 412   VectorSet _clone_visited;
 413   Node_List _old_new; // map of old to new (clone)
 414   IdealLoopTree* _lpt;
 415   PhaseIdealLoop* _phase;
 416 
 417   // Helper function to set up the invariance for invariance computation
 418   // If n is a known invariant, set up directly. Otherwise, look up the
 419   // the possibility to push n onto the stack for further processing.
 420   void visit(Node* use, Node* n) {
 421     if (_lpt->is_invariant(n)) { // known invariant
 422       _invariant.set(n->_idx);


 749   CmpNode* cmp = NULL;
 750   if (overflow) {
 751     // Integer expressions may overflow, do long comparison
 752     range = new ConvI2LNode(range);
 753     register_new_node(range, ctrl);
 754     cmp = new CmpULNode(max_idx_expr, range);
 755   } else {
 756     cmp = new CmpUNode(max_idx_expr, range);
 757   }
 758   register_new_node(cmp, ctrl);
 759   BoolNode* bol = new BoolNode(cmp, BoolTest::lt);
 760   register_new_node(bol, ctrl);
 761 
 762   if (TraceLoopPredicate) {
 763     predString->print_cr("<u range");
 764     tty->print("%s", predString->as_string());
 765   }
 766   return bol;
 767 }
 768 
 769 // After pre/main/post loops are created, we'll put a copy of some
 770 // range checks between the pre and main loop to validate the initial
 771 // value of the induction variable for the main loop. Make a copy of
 772 // the predicates here with an opaque node as a place holder for the
 773 // initial value.
 774 ProjNode* PhaseIdealLoop::insert_skeleton_predicate(IfNode* iff, IdealLoopTree *loop,
 775                                                     ProjNode* proj, ProjNode *predicate_proj,
 776                                                     ProjNode* upper_bound_proj,
 777                                                     int scale, Node* offset,
 778                                                     Node* init, Node* limit, jint stride,
 779                                                     Node* rng, bool &overflow) {
 780   assert(proj->_con && predicate_proj->_con, "not a range check?");
 781   Node* opaque_init = new Opaque1Node(C, init);
 782   register_new_node(opaque_init, upper_bound_proj);
 783   BoolNode* bol = rc_predicate(loop, upper_bound_proj, scale, offset, opaque_init, limit, stride, rng, (stride > 0) != (scale > 0), overflow);
 784   Node* opaque_bol = new Opaque4Node(C, bol, _igvn.intcon(1)); // This will go away once loop opts are over
 785   register_new_node(opaque_bol, upper_bound_proj);
 786   ProjNode* new_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, overflow ? Op_If : iff->Opcode());
 787   _igvn.replace_input_of(new_proj->in(0), 1, opaque_bol);
 788   assert(opaque_init->outcnt() > 0, "should be used");
 789   return new_proj;
 790 }
 791 
 792 //------------------------------ loop_predication_impl--------------------------
 793 // Insert loop predicates for null checks and range checks
 794 bool PhaseIdealLoop::loop_predication_impl(IdealLoopTree *loop) {
 795   if (!UseLoopPredicate) return false;
 796 
 797   if (!loop->_head->is_Loop()) {
 798     // Could be a simple region when irreducible loops are present.
 799     return false;
 800   }
 801   LoopNode* head = loop->_head->as_Loop();
 802 
 803   if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
 804     // do nothing for infinite loops
 805     return false;
 806   }
 807 
 808   if (head->is_OuterStripMinedLoop()) {
 809     return false;




























 810   }
 811 
 812   CountedLoopNode *cl = NULL;
 813   if (head->is_valid_counted_loop()) {
 814     cl = head->as_CountedLoop();
 815     // do nothing for iteration-splitted loops
 816     if (!cl->is_normal_loop()) return false;
 817     // Avoid RCE if Counted loop's test is '!='.
 818     BoolTest::mask bt = cl->loopexit()->test_trip();
 819     if (bt != BoolTest::lt && bt != BoolTest::gt)
 820       cl = NULL;
 821   }
 822 
 823   Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
 824   ProjNode *predicate_proj = NULL;
 825   // Loop limit check predicate should be near the loop.
 826   predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 827   if (predicate_proj != NULL)
 828     entry = predicate_proj->in(0)->in(0);
 829   predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 830   if (!predicate_proj) {
 831 #ifndef PRODUCT
 832     if (TraceLoopPredicate) {
 833       tty->print("missing predicate:");
 834       loop->dump_head();
 835       head->dump(1);
 836     }
 837 #endif
 838     return false;
 839   }
 840   ConNode* zero = _igvn.intcon(0);
 841   set_ctrl(zero, C->root());

 842 
 843   ResourceArea *area = Thread::current()->resource_area();
 844   Invariance invar(area, loop);







 845 
 846   // Create list of if-projs such that a newer proj dominates all older
 847   // projs in the list, and they all dominate loop->tail()
 848   Node_List if_proj_list(area);
 849   Node *current_proj = loop->tail(); //start from tail
 850   while (current_proj != head) {
 851     if (loop == get_loop(current_proj) && // still in the loop ?
 852         current_proj->is_Proj()        && // is a projection  ?
 853         (current_proj->in(0)->Opcode() == Op_If ||
 854          current_proj->in(0)->Opcode() == Op_RangeCheck)) { // is a if projection ?
 855       if_proj_list.push(current_proj);






































 856     }
 857     current_proj = idom(current_proj);



 858   }




















































































































 859 
 860   bool hoisted = false; // true if at least one proj is promoted
 861   while (if_proj_list.size() > 0) {
 862     // Following are changed to nonnull when a predicate can be hoisted
 863     ProjNode* new_predicate_proj = NULL;
 864 
 865     ProjNode* proj = if_proj_list.pop()->as_Proj();
 866     IfNode*   iff  = proj->in(0)->as_If();
 867 
 868     if (!proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {
 869       if (loop->is_loop_exit(iff)) {
 870         // stop processing the remaining projs in the list because the execution of them
 871         // depends on the condition of "iff" (iff->in(1)).








 872         break;






 873       } else {
 874         // Both arms are inside the loop. There are two cases:
 875         // (1) there is one backward branch. In this case, any remaining proj
 876         //     in the if_proj list post-dominates "iff". So, the condition of "iff"
 877         //     does not determine the execution the remining projs directly, and we
 878         //     can safely continue.
 879         // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj"
 880         //     does not dominate loop->tail(), so it can not be in the if_proj list.
 881         continue;
 882       }
 883     }









 884 







 885     Node*     test = iff->in(1);
 886     if (!test->is_Bool()){ //Conv2B, ...
 887       continue;
 888     }
 889     BoolNode* bol = test->as_Bool();
 890     if (invar.is_invariant(bol)) {
 891       // Invariant test
 892       new_predicate_proj = create_new_if_for_predicate(predicate_proj, NULL,
 893                                                        Deoptimization::Reason_predicate,
 894                                                        iff->Opcode());
 895       Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0);
 896       BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool();
 897 
 898       // Negate test if necessary
 899       bool negated = false;
 900       if (proj->_con != predicate_proj->_con) {
 901         new_predicate_bol = new BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate());
 902         register_new_node(new_predicate_bol, ctrl);
 903         negated = true;
 904       }
 905       IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If();
 906       _igvn.hash_delete(new_predicate_iff);
 907       new_predicate_iff->set_req(1, new_predicate_bol);
 908 #ifndef PRODUCT
 909       if (TraceLoopPredicate) {
 910         tty->print("Predicate invariant if%s: %d ", negated ? " negated" : "", new_predicate_iff->_idx);
 911         loop->dump_head();
 912       } else if (TraceLoopOpts) {
 913         tty->print("Predicate IC ");


 942       // Perform cloning to keep Invariance state correct since the
 943       // late schedule will place invariant things in the loop.
 944       Node *ctrl = predicate_proj->in(0)->as_If()->in(0);
 945       rng = invar.clone(rng, ctrl);
 946       if (offset && offset != zero) {
 947         assert(invar.is_invariant(offset), "offset must be loop invariant");
 948         offset = invar.clone(offset, ctrl);
 949       }
 950       // If predicate expressions may overflow in the integer range, longs are used.
 951       bool overflow = false;
 952 
 953       // Test the lower bound
 954       BoolNode* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false, overflow);
 955       // Negate test if necessary
 956       bool negated = false;
 957       if (proj->_con != predicate_proj->_con) {
 958         lower_bound_bol = new BoolNode(lower_bound_bol->in(1), lower_bound_bol->_test.negate());
 959         register_new_node(lower_bound_bol, ctrl);
 960         negated = true;
 961       }
 962       ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, overflow ? Op_If : iff->Opcode());
 963       IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If();
 964       _igvn.hash_delete(lower_bound_iff);
 965       lower_bound_iff->set_req(1, lower_bound_bol);
 966       if (TraceLoopPredicate) tty->print_cr("lower bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx);
 967 
 968       // Test the upper bound
 969       BoolNode* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true, overflow);
 970       negated = false;
 971       if (proj->_con != predicate_proj->_con) {
 972         upper_bound_bol = new BoolNode(upper_bound_bol->in(1), upper_bound_bol->_test.negate());
 973         register_new_node(upper_bound_bol, ctrl);
 974         negated = true;
 975       }
 976       ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, overflow ? Op_If : iff->Opcode());
 977       assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate");
 978       IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If();
 979       _igvn.hash_delete(upper_bound_iff);
 980       upper_bound_iff->set_req(1, upper_bound_bol);
 981       if (TraceLoopPredicate) tty->print_cr("upper bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx);
 982 
 983       // Fall through into rest of the clean up code which will move
 984       // any dependent nodes onto the upper bound test.
 985       new_predicate_proj = upper_bound_proj;
 986 
 987       if (iff->is_RangeCheck()) {
 988         new_predicate_proj = insert_skeleton_predicate(iff, loop, proj, predicate_proj, upper_bound_proj, scale, offset, init, limit, stride, rng, overflow);
 989       }
 990 
 991 #ifndef PRODUCT
 992       if (TraceLoopOpts && !TraceLoopPredicate) {
 993         tty->print("Predicate RC ");
 994         loop->dump_head();
 995       }
 996 #endif
 997     } else {
 998       // Loop variant check (for example, range check in non-counted loop)
 999       // with uncommon trap.
1000       continue;
1001     }
1002     assert(new_predicate_proj != NULL, "sanity");
1003     // Success - attach condition (new_predicate_bol) to predicate if
1004     invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate
1005 
1006     // Eliminate the old If in the loop body
1007     dominated_by( new_predicate_proj, iff, proj->_con != new_predicate_proj->_con );
1008 
1009     hoisted = true;
1010     C->set_major_progress();






























































































































































1011   } // end while






























1012 
1013 #ifndef PRODUCT
1014   // report that the loop predication has been actually performed
1015   // for this loop
1016   if (TraceLoopPredicate && hoisted) {
1017     tty->print("Loop Predication Performed:");
1018     loop->dump_head();
1019   }
1020 #endif
1021 
1022   head->verify_strip_mined(1);
1023 
1024   return hoisted;
1025 }
1026 
1027 //------------------------------loop_predication--------------------------------
1028 // driver routine for loop predication optimization
1029 bool IdealLoopTree::loop_predication( PhaseIdealLoop *phase) {
1030   bool hoisted = false;
1031   // Recursively promote predicates


  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "opto/loopnode.hpp"
  27 #include "opto/addnode.hpp"
  28 #include "opto/callnode.hpp"
  29 #include "opto/connode.hpp"
  30 #include "opto/convertnode.hpp"
  31 #include "opto/loopnode.hpp"
  32 #include "opto/matcher.hpp"
  33 #include "opto/mulnode.hpp"
  34 #include "opto/opaquenode.hpp"
  35 #include "opto/rootnode.hpp"
  36 #include "opto/subnode.hpp"
  37 #include <fenv.h>
  38 #include <math.h>
  39 
  40 /*
  41  * The general idea of Loop Predication is to insert a predicate on the entry
  42  * path to a loop, and raise a uncommon trap if the check of the condition fails.
  43  * The condition checks are promoted from inside the loop body, and thus
  44  * the checks inside the loop could be eliminated. Currently, loop predication
  45  * optimization has been applied to remove array range check and loop invariant
  46  * checks (such as null checks).
  47 */
  48 
  49 //-------------------------------register_control-------------------------
  50 void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {
  51   assert(n->is_CFG(), "must be control node");
  52   _igvn.register_new_node_with_optimizer(n);
  53   loop->_body.push(n);
  54   set_loop(n, loop);
  55   // When called from beautify_loops() idom is not constructed yet.
  56   if (_idom != NULL) {
  57     set_idom(n, pred, dom_depth(pred));
  58   }


 303 
 304 // Clone loop predicates to cloned loops (peeled, unswitched, split_if).
 305 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry,
 306                                                 bool clone_limit_check,
 307                                                 PhaseIdealLoop* loop_phase,
 308                                                 PhaseIterGVN* igvn) {
 309 #ifdef ASSERT
 310   if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) {
 311     if (new_entry != NULL)
 312       new_entry->dump();
 313     assert(false, "not IfTrue, IfFalse, Region or SafePoint");
 314   }
 315 #endif
 316   // Search original predicates
 317   Node* entry = old_entry;
 318   ProjNode* limit_check_proj = NULL;
 319   limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 320   if (limit_check_proj != NULL) {
 321     entry = entry->in(0)->in(0);
 322   }
 323   ProjNode* profile_predicate_proj = NULL;
 324   ProjNode* predicate_proj = NULL;
 325   if (UseProfiledLoopPredicate) {
 326     profile_predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
 327     if (profile_predicate_proj != NULL) {
 328       entry = skip_loop_predicates(entry);
 329     }
 330   }
 331   if (UseLoopPredicate) {
 332     predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 333   }
 334   if (predicate_proj != NULL) { // right pattern that can be used by loop predication
 335     // clone predicate
 336     new_entry = clone_predicate(predicate_proj, new_entry,
 337                                 Deoptimization::Reason_predicate,
 338                                 loop_phase, igvn);
 339     assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate");
 340     if (TraceLoopPredicate) {
 341       tty->print("Loop Predicate cloned: ");
 342       debug_only( new_entry->in(0)->dump(); );
 343     }
 344   }
 345   if (profile_predicate_proj != NULL) { // right pattern that can be used by loop predication
 346     // clone predicate
 347     new_entry = clone_predicate(profile_predicate_proj, new_entry,
 348                                 Deoptimization::Reason_profile_predicate,
 349                                 loop_phase, igvn);
 350     assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate");
 351     if (TraceLoopPredicate) {
 352       tty->print("Loop Predicate cloned: ");
 353       debug_only( new_entry->in(0)->dump(); );
 354     }
 355   }
 356   if (limit_check_proj != NULL && clone_limit_check) {
 357     // Clone loop limit check last to insert it before loop.
 358     // Don't clone a limit check which was already finalized
 359     // for this counted loop (only one limit check is needed).
 360     new_entry = clone_predicate(limit_check_proj, new_entry,
 361                                 Deoptimization::Reason_loop_limit_check,
 362                                 loop_phase, igvn);
 363     assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check");
 364     if (TraceLoopLimitCheck) {
 365       tty->print("Loop Limit Check cloned: ");
 366       debug_only( new_entry->in(0)->dump(); )
 367     }
 368   }
 369   return new_entry;
 370 }
 371 
 372 //--------------------------skip_loop_predicates------------------------------
 373 // Skip related predicates.
 374 Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) {








 375   IfNode* iff = entry->in(0)->as_If();
 376   ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
 377   Node* rgn = uncommon_proj->unique_ctrl_out();
 378   assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
 379   entry = entry->in(0)->in(0);
 380   while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
 381     uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
 382     if (uncommon_proj->unique_ctrl_out() != rgn)
 383       break;
 384     entry = entry->in(0)->in(0);
 385   }
 386   return entry;
 387 }
 388 
 389 Node* PhaseIdealLoop::skip_all_loop_predicates(Node* entry) {
 390   Node* predicate = NULL;
 391   predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 392   if (predicate != NULL) {
 393     entry = entry->in(0)->in(0);
 394   }
 395   if (UseProfiledLoopPredicate) {
 396     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
 397     if (predicate != NULL) { // right pattern that can be used by loop predication
 398       entry = skip_loop_predicates(entry);
 399     }
 400   }
 401   if (UseLoopPredicate) {
 402     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 403     if (predicate != NULL) { // right pattern that can be used by loop predication
 404       entry = skip_loop_predicates(entry);
 405     }
 406   }
 407   return entry;
 408 }
 409 
 410 //--------------------------find_predicate_insertion_point-------------------
 411 // Find a good location to insert a predicate
 412 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
 413   if (start_c == NULL || !start_c->is_Proj())
 414     return NULL;
 415   if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {
 416     return start_c->as_Proj();
 417   }
 418   return NULL;
 419 }
 420 
 421 //--------------------------find_predicate------------------------------------
 422 // Find a predicate
 423 Node* PhaseIdealLoop::find_predicate(Node* entry) {
 424   Node* predicate = NULL;
 425   predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
 426   if (predicate != NULL) { // right pattern that can be used by loop predication
 427     return entry;
 428   }
 429   if (UseLoopPredicate) {
 430     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 431     if (predicate != NULL) { // right pattern that can be used by loop predication
 432       return entry;
 433     }
 434   }
 435   if (UseProfiledLoopPredicate) {
 436     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
 437     if (predicate != NULL) { // right pattern that can be used by loop predication
 438       return entry;
 439     }
 440   }
 441   return NULL;
 442 }
 443 
 444 //------------------------------Invariance-----------------------------------
 445 // Helper class for loop_predication_impl to compute invariance on the fly and
 446 // clone invariants.
 447 class Invariance : public StackObj {
 448   VectorSet _visited, _invariant;
 449   Node_Stack _stack;
 450   VectorSet _clone_visited;
 451   Node_List _old_new; // map of old to new (clone)
 452   IdealLoopTree* _lpt;
 453   PhaseIdealLoop* _phase;
 454 
 455   // Helper function to set up the invariance for invariance computation
 456   // If n is a known invariant, set up directly. Otherwise, look up the
 457   // the possibility to push n onto the stack for further processing.
 458   void visit(Node* use, Node* n) {
 459     if (_lpt->is_invariant(n)) { // known invariant
 460       _invariant.set(n->_idx);


 787   CmpNode* cmp = NULL;
 788   if (overflow) {
 789     // Integer expressions may overflow, do long comparison
 790     range = new ConvI2LNode(range);
 791     register_new_node(range, ctrl);
 792     cmp = new CmpULNode(max_idx_expr, range);
 793   } else {
 794     cmp = new CmpUNode(max_idx_expr, range);
 795   }
 796   register_new_node(cmp, ctrl);
 797   BoolNode* bol = new BoolNode(cmp, BoolTest::lt);
 798   register_new_node(bol, ctrl);
 799 
 800   if (TraceLoopPredicate) {
 801     predString->print_cr("<u range");
 802     tty->print("%s", predString->as_string());
 803   }
 804   return bol;
 805 }
 806 
 807 // Should loop predication look not only in the path from tail to head
 808 // but also in branches of the loop body?
 809 bool PhaseIdealLoop::loop_predication_should_follow_branches(IdealLoopTree *loop, ProjNode *predicate_proj, float& loop_trip_cnt) {
 810   if (!UseProfiledLoopPredicate) {


























 811     return false;
 812   }

 813 
 814   if (predicate_proj == NULL) {

 815     return false;
 816   }
 817 
 818   LoopNode* head = loop->_head->as_Loop();
 819   bool follow_branches = true;
 820   IdealLoopTree* l = loop->_child;
 821   // For leaf loops and loops with a single inner loop
 822   while (l != NULL && follow_branches) {
 823     IdealLoopTree* child = l;
 824     if (child->_child != NULL &&
 825         child->_head->is_OuterStripMinedLoop()) {
 826       assert(child->_child->_next == NULL, "only one inner loop for strip mined loop");
 827       assert(child->_child->_head->is_CountedLoop() && child->_child->_head->as_CountedLoop()->is_strip_mined(), "inner loop should be strip mined");
 828       child = child->_child;
 829     }
 830     if (child->_child != NULL || child->_irreducible) {
 831       follow_branches = false;
 832     }
 833     l = l->_next;
 834   }
 835   if (follow_branches) {
 836     loop->compute_profile_trip_cnt(this);
 837     if (head->is_profile_trip_failed()) {
 838       follow_branches = false;
 839     } else {
 840       loop_trip_cnt = head->profile_trip_cnt();
 841       if (head->is_CountedLoop()) {
 842         CountedLoopNode* cl = head->as_CountedLoop();
 843         if (cl->phi() != NULL) {
 844           const TypeInt* t = _igvn.type(cl->phi())->is_int();
 845           float worst_case_trip_cnt = ((float)t->_hi - t->_lo) / ABS(cl->stride_con());
 846           if (worst_case_trip_cnt < loop_trip_cnt) {
 847             loop_trip_cnt = worst_case_trip_cnt;
 848           }










 849         }














 850       }


 851     }
 852   }
 853   return follow_branches;
 854 }
 855 
 856 // Compute probability of reaching some CFG node from a fixed
 857 // dominating CFG node
 858 class PathFrequency {
 859 private:
 860   Node* _dom; // frequencies are computed relative to this node
 861   Node_Stack _stack;
 862   GrowableArray<float> _freqs_stack; // keep track of intermediate result at regions
 863   GrowableArray<float> _freqs; // cache frequencies
 864   PhaseIdealLoop* _phase;
 865 
 866 public:
 867   PathFrequency(Node* dom, PhaseIdealLoop* phase)
 868     : _dom(dom), _stack(0), _phase(phase) {
 869   }
 870 
 871   float to(Node* n) {
 872     // post order walk on the CFG graph from n to _dom
 873     fesetround(FE_TOWARDZERO); // make sure rounding doesn't push frequency above 1
 874     IdealLoopTree* loop = _phase->get_loop(_dom);
 875     Node* c = n;
 876     for (;;) {
 877       assert(_phase->get_loop(c) == loop, "have to be in the same loop");
 878       if (c == _dom || _freqs.at_grow(c->_idx, -1) >= 0) {
 879         float f = c == _dom ? 1 : _freqs.at(c->_idx);
 880         Node* prev = c;
 881         while (_stack.size() > 0 && prev == c) {
 882           Node* n = _stack.node();
 883           if (!n->is_Region()) {
 884             if (_phase->get_loop(n) != _phase->get_loop(n->in(0))) {
 885               // Found an inner loop: compute frequency of reaching this
 886               // exit from the loop head by looking at the number of
 887               // times each loop exit was taken
 888               IdealLoopTree* inner_loop = _phase->get_loop(n->in(0));
 889               LoopNode* inner_head = inner_loop->_head->as_Loop();
 890               assert(_phase->get_loop(n) == loop, "only 1 inner loop");
 891               if (inner_head->is_OuterStripMinedLoop()) {
 892                 inner_head->verify_strip_mined(1);
 893                 if (n->in(0) == inner_head->in(LoopNode::LoopBackControl)->in(0)) {
 894                   n = n->in(0)->in(0)->in(0);
 895                 }
 896                 inner_loop = inner_loop->_child;
 897                 inner_head = inner_loop->_head->as_Loop();
 898                 inner_head->verify_strip_mined(1);
 899               }
 900               fesetround(FE_UPWARD);  // make sure rounding doesn't push frequency above 1
 901               float loop_exit_cnt = 0.0f;
 902               for (uint i = 0; i < inner_loop->_body.size(); i++) {
 903                 Node *n = inner_loop->_body[i];
 904                 float c = inner_loop->compute_profile_trip_cnt_helper(n);
 905                 loop_exit_cnt += c;
 906               }
 907               fesetround(FE_TOWARDZERO);
 908               float cnt = -1;
 909               if (n->in(0)->is_If()) {
 910                 IfNode* iff = n->in(0)->as_If();
 911                 float p = n->in(0)->as_If()->_prob;
 912                 if (n->Opcode() == Op_IfFalse) {
 913                   p = 1 - p;
 914                 }
 915                 if (p > PROB_MIN) {
 916                   cnt = p * iff->_fcnt;
 917                 } else {
 918                   cnt = 0;
 919                 }
 920               } else {
 921                 assert(n->in(0)->is_Jump(), "unsupported node kind");
 922                 JumpNode* jmp = n->in(0)->as_Jump();
 923                 float p = n->in(0)->as_Jump()->_probs[n->as_JumpProj()->_con];
 924                 cnt = p * jmp->_fcnt;
 925               }
 926               float this_exit_f = cnt > 0 ? cnt / loop_exit_cnt : 0;
 927               assert(this_exit_f <= 1 && this_exit_f >= 0, "Incorrect frequency");
 928               f = f * this_exit_f;
 929               assert(f <= 1 && f >= 0, "Incorrect frequency");
 930             } else {
 931               float p = -1;
 932               if (n->in(0)->is_If()) {
 933                 p = n->in(0)->as_If()->_prob;
 934                 if (n->Opcode() == Op_IfFalse) {
 935                   p = 1 - p;
 936                 }
 937               } else {
 938                 assert(n->in(0)->is_Jump(), "unsupported node kind");
 939                 p = n->in(0)->as_Jump()->_probs[n->as_JumpProj()->_con];
 940               }
 941               f = f * p;
 942               assert(f <= 1 && f >= 0, "Incorrect frequency");
 943             }
 944             _freqs.at_put_grow(n->_idx, (float)f, -1);
 945             _stack.pop();
 946           } else {
 947             float prev_f = _freqs_stack.pop();
 948             float new_f = f;
 949             f = new_f + prev_f;
 950             assert(f <= 1 && f >= 0, "Incorrect frequency");
 951             uint i = _stack.index();
 952             if (i < n->req()) {
 953               c = n->in(i);
 954               _stack.set_index(i+1);
 955               _freqs_stack.push(f);
 956             } else {
 957               _freqs.at_put_grow(n->_idx, f, -1);
 958               _stack.pop();
 959             }
 960           }
 961         }
 962         if (_stack.size() == 0) {
 963           fesetround(FE_TONEAREST);
 964           assert(f >= 0 && f <= 1, "should have been computed");
 965           return f;
 966         }
 967       } else if (c->is_Loop()) {
 968         ShouldNotReachHere();
 969         c = c->in(LoopNode::EntryControl);
 970       } else if (c->is_Region()) {
 971         _freqs_stack.push(0);
 972         _stack.push(c, 2);
 973         c = c->in(1);
 974       } else {
 975         if (c->is_IfProj()) {
 976           IfNode* iff = c->in(0)->as_If();
 977           if (iff->_prob == PROB_UNKNOWN) {
 978             // assume never taken
 979             _freqs.at_put_grow(c->_idx, 0, -1);
 980           } else if (_phase->get_loop(c) != _phase->get_loop(iff)) {
 981             if (iff->_fcnt == COUNT_UNKNOWN) {
 982               // assume never taken
 983               _freqs.at_put_grow(c->_idx, 0, -1);
 984             } else {
 985               // skip over loop
 986               _stack.push(c, 1);
 987               c = _phase->get_loop(c->in(0))->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
 988             }
 989           } else {
 990             _stack.push(c, 1);
 991             c = iff;
 992           }
 993         } else if (c->is_JumpProj()) {
 994           JumpNode* jmp = c->in(0)->as_Jump();
 995           if (_phase->get_loop(c) != _phase->get_loop(jmp)) {
 996             if (jmp->_fcnt == COUNT_UNKNOWN) {
 997               // assume never taken
 998               _freqs.at_put_grow(c->_idx, 0, -1);
 999             } else {
1000               // skip over loop
1001               _stack.push(c, 1);
1002               c = _phase->get_loop(c->in(0))->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
1003             }
1004           } else {
1005             _stack.push(c, 1);
1006             c = jmp;
1007           }
1008         } else if (c->Opcode() == Op_CatchProj &&
1009                    c->in(0)->Opcode() == Op_Catch &&
1010                    c->in(0)->in(0)->is_Proj() &&
1011                    c->in(0)->in(0)->in(0)->is_Call()) {
1012           // assume exceptions are never thrown
1013           uint con = c->as_Proj()->_con;
1014           if (con == CatchProjNode::fall_through_index) {
1015             Node* call = c->in(0)->in(0)->in(0)->in(0);
1016             if (_phase->get_loop(call) != _phase->get_loop(c)) {
1017               _freqs.at_put_grow(c->_idx, 0, -1);
1018             } else {
1019               c = call;
1020             }
1021           } else {
1022             assert(con >= CatchProjNode::catch_all_index, "what else?");
1023             _freqs.at_put_grow(c->_idx, 0, -1);
1024           }
1025         } else if (c->unique_ctrl_out() == NULL && !c->is_If() && !c->is_Jump()) {
1026           ShouldNotReachHere();
1027         } else {
1028           c = c->in(0);
1029         }
1030       }
1031     }
1032     ShouldNotReachHere();
1033     return -1;
1034   }
1035 };
1036 
1037 void PhaseIdealLoop::loop_predication_follow_branches(Node *n, IdealLoopTree *loop, float loop_trip_cnt,
1038                                                       PathFrequency& pf, Node_Stack& stack, VectorSet& seen,
1039                                                       Node_List& if_proj_list) {
1040   assert(n->is_Region(), "start from a region");
1041   Node* tail = loop->tail();
1042   stack.push(n, 1);
1043   do {
1044     Node* c = stack.node();
1045     assert(c->is_Region() || c->is_IfProj(), "only region here");
1046     uint i = stack.index();
1047     
1048     if (i < c->req()) {
1049       stack.set_index(i+1);
1050       Node* in = c->in(i);
1051       while (!is_dominator(in, tail) && !seen.test_set(in->_idx)) {
1052         IdealLoopTree* in_loop = get_loop(in);
1053         if (in_loop != loop) {
1054           in = in_loop->_head->in(LoopNode::EntryControl);
1055         } else if (in->is_Region()) {
1056           stack.push(in, 1);
1057           break;
1058         } else if (in->is_IfProj() &&
1059                    in->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {
1060           if (pf.to(in) * loop_trip_cnt >= 1) {
1061             stack.push(in, 1);
1062           }
1063           in = in->in(0);
1064         } else {
1065           in = in->in(0);







1066         }
1067       }
1068     } else {
1069       if (c->is_IfProj()) {
1070         if_proj_list.push(c);
1071       }
1072       stack.pop();
1073     }
1074 
1075   } while (stack.size() > 0);
1076 }
1077 
1078 
1079 bool PhaseIdealLoop::loop_predication_impl_helper(IdealLoopTree *loop, ProjNode* proj, ProjNode *predicate_proj,
1080                                                   CountedLoopNode *cl, ConNode* zero, Invariance& invar,
1081                                                   Deoptimization::DeoptReason reason) {
1082   // Following are changed to nonnull when a predicate can be hoisted
1083   ProjNode* new_predicate_proj = NULL;
1084   IfNode*   iff  = proj->in(0)->as_If();
1085   Node*     test = iff->in(1);
1086   if (!test->is_Bool()){ //Conv2B, ...
1087     return false;
1088   }
1089   BoolNode* bol = test->as_Bool();
1090   if (invar.is_invariant(bol)) {
1091     // Invariant test
1092     new_predicate_proj = create_new_if_for_predicate(predicate_proj, NULL,
1093                                                      reason,
1094                                                      iff->Opcode());
1095     Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0);
1096     BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool();
1097 
1098     // Negate test if necessary
1099     bool negated = false;
1100     if (proj->_con != predicate_proj->_con) {
1101       new_predicate_bol = new BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate());
1102       register_new_node(new_predicate_bol, ctrl);
1103       negated = true;
1104     }
1105     IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If();
1106     _igvn.hash_delete(new_predicate_iff);
1107     new_predicate_iff->set_req(1, new_predicate_bol);
1108 #ifndef PRODUCT
1109     if (TraceLoopPredicate) {
1110       tty->print("Predicate invariant if%s: %d ", negated ? " negated" : "", new_predicate_iff->_idx);
1111       loop->dump_head();
1112     } else if (TraceLoopOpts) {
1113       tty->print("Predicate IC ");


1142     // Perform cloning to keep Invariance state correct since the
1143     // late schedule will place invariant things in the loop.
1144     Node *ctrl = predicate_proj->in(0)->as_If()->in(0);
1145     rng = invar.clone(rng, ctrl);
1146     if (offset && offset != zero) {
1147       assert(invar.is_invariant(offset), "offset must be loop invariant");
1148       offset = invar.clone(offset, ctrl);
1149     }
1150     // If predicate expressions may overflow in the integer range, longs are used.
1151     bool overflow = false;
1152 
1153     // Test the lower bound
1154     BoolNode* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false, overflow);
1155     // Negate test if necessary
1156     bool negated = false;
1157     if (proj->_con != predicate_proj->_con) {
1158       lower_bound_bol = new BoolNode(lower_bound_bol->in(1), lower_bound_bol->_test.negate());
1159       register_new_node(lower_bound_bol, ctrl);
1160       negated = true;
1161     }
1162     ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, reason, overflow ? Op_If : iff->Opcode());
1163     IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If();
1164     _igvn.hash_delete(lower_bound_iff);
1165     lower_bound_iff->set_req(1, lower_bound_bol);
1166     if (TraceLoopPredicate) tty->print_cr("lower bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx);
1167 
1168     // Test the upper bound
1169     BoolNode* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true, overflow);
1170     negated = false;
1171     if (proj->_con != predicate_proj->_con) {
1172       upper_bound_bol = new BoolNode(upper_bound_bol->in(1), upper_bound_bol->_test.negate());
1173       register_new_node(upper_bound_bol, ctrl);
1174       negated = true;
1175     }
1176     ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, reason, overflow ? Op_If : iff->Opcode());
1177     assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate");
1178     IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If();
1179     _igvn.hash_delete(upper_bound_iff);
1180     upper_bound_iff->set_req(1, upper_bound_bol);
1181     if (TraceLoopPredicate) tty->print_cr("upper bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx);
1182 
1183     // Fall through into rest of the clean up code which will move
1184     // any dependent nodes onto the upper bound test.
1185     new_predicate_proj = upper_bound_proj;
1186 
1187     if (iff->is_RangeCheck()) {
1188       new_predicate_proj = insert_skeleton_predicate(iff, loop, proj, predicate_proj, upper_bound_proj, scale, offset, init, limit, stride, rng, overflow, reason);
1189     }
1190 
1191 #ifndef PRODUCT
1192     if (TraceLoopOpts && !TraceLoopPredicate) {
1193       tty->print("Predicate RC ");
1194       loop->dump_head();
1195     }
1196 #endif
1197   } else {
1198     // Loop variant check (for example, range check in non-counted loop)
1199     // with uncommon trap.
1200     return false;
1201   }
1202   assert(new_predicate_proj != NULL, "sanity");
1203   // Success - attach condition (new_predicate_bol) to predicate if
1204   invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate
1205 
1206   // Eliminate the old If in the loop body
1207   dominated_by( new_predicate_proj, iff, proj->_con != new_predicate_proj->_con );
1208 

1209   C->set_major_progress();
1210   return true;
1211 }
1212 
1213 
1214 // After pre/main/post loops are created, we'll put a copy of some
1215 // range checks between the pre and main loop to validate the initial
1216 // value of the induction variable for the main loop. Make a copy of
1217 // the predicates here with an opaque node as a place holder for the
1218 // initial value.
1219 ProjNode* PhaseIdealLoop::insert_skeleton_predicate(IfNode* iff, IdealLoopTree *loop,
1220                                                     ProjNode* proj, ProjNode *predicate_proj,
1221                                                     ProjNode* upper_bound_proj,
1222                                                     int scale, Node* offset,
1223                                                     Node* init, Node* limit, jint stride,
1224                                                     Node* rng, bool &overflow,
1225                                                     Deoptimization::DeoptReason reason) {
1226   assert(proj->_con && predicate_proj->_con, "not a range check?");
1227   Node* opaque_init = new Opaque1Node(C, init);
1228   register_new_node(opaque_init, upper_bound_proj);
1229   BoolNode* bol = rc_predicate(loop, upper_bound_proj, scale, offset, opaque_init, limit, stride, rng, (stride > 0) != (scale > 0), overflow);
1230   Node* opaque_bol = new Opaque4Node(C, bol, _igvn.intcon(1)); // This will go away once loop opts are over
1231   register_new_node(opaque_bol, upper_bound_proj);
1232   ProjNode* new_proj = create_new_if_for_predicate(predicate_proj, NULL, reason, overflow ? Op_If : iff->Opcode());
1233   _igvn.replace_input_of(new_proj->in(0), 1, opaque_bol);
1234   assert(opaque_init->outcnt() > 0, "should be used");
1235   return new_proj;
1236 }
1237 
1238 //------------------------------ loop_predication_impl--------------------------
1239 // Insert loop predicates for null checks and range checks
1240 bool PhaseIdealLoop::loop_predication_impl(IdealLoopTree *loop) {
1241   if (!UseLoopPredicate) return false;
1242 
1243   if (!loop->_head->is_Loop()) {
1244     // Could be a simple region when irreducible loops are present.
1245     return false;
1246   }
1247   LoopNode* head = loop->_head->as_Loop();
1248 
1249   if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
1250     // do nothing for infinite loops
1251     return false;
1252   }
1253 
1254   if (head->is_OuterStripMinedLoop()) {
1255     return false;
1256   }
1257 
1258   CountedLoopNode *cl = NULL;
1259   if (head->is_valid_counted_loop()) {
1260     cl = head->as_CountedLoop();
1261     // do nothing for iteration-splitted loops
1262     if (!cl->is_normal_loop()) return false;
1263     // Avoid RCE if Counted loop's test is '!='.
1264     BoolTest::mask bt = cl->loopexit()->test_trip();
1265     if (bt != BoolTest::lt && bt != BoolTest::gt)
1266       cl = NULL;
1267   }
1268 
1269   Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
1270   ProjNode *loop_limit_proj = NULL;
1271   ProjNode *predicate_proj = NULL;
1272   ProjNode *profile_predicate_proj = NULL;
1273   // Loop limit check predicate should be near the loop.
1274   loop_limit_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1275   if (loop_limit_proj != NULL) {
1276     entry = loop_limit_proj->in(0)->in(0);
1277   }
1278   bool has_profile_predicates = false;
1279   profile_predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
1280   if (profile_predicate_proj != NULL) {
1281     Node* n = skip_loop_predicates(entry);
1282     // Check if predicates were already added to the profile predicate
1283     // block
1284     if (n != entry->in(0)->in(0)) {
1285       has_profile_predicates = true;
1286     }
1287     entry = n;
1288   }
1289   predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1290 
1291   float loop_trip_cnt = -1;
1292   bool follow_branches = loop_predication_should_follow_branches(loop, profile_predicate_proj, loop_trip_cnt);
1293   assert(!follow_branches || loop_trip_cnt >= 0, "negative trip count?");
1294 
1295   if (predicate_proj == NULL && !follow_branches) {
1296 #ifndef PRODUCT
1297     if (TraceLoopPredicate) {
1298       tty->print("missing predicate:");
1299       loop->dump_head();
1300       head->dump(1);
1301     }
1302 #endif
1303     return false;
1304   }
1305   ConNode* zero = _igvn.intcon(0);
1306   set_ctrl(zero, C->root());
1307 
1308   ResourceArea *area = Thread::current()->resource_area();
1309   Invariance invar(area, loop);
1310 
1311   // Create list of if-projs such that a newer proj dominates all older
1312   // projs in the list, and they all dominate loop->tail()
1313   Node_List if_proj_list(area);
1314   Node_List regions(area);
1315   Node *current_proj = loop->tail(); //start from tail
1316 
1317 
1318   Node_List controls(area);
1319   while (current_proj != head) {
1320     if (loop == get_loop(current_proj) && // still in the loop ?
1321         current_proj->is_Proj()        && // is a projection  ?
1322         (current_proj->in(0)->Opcode() == Op_If ||
1323          current_proj->in(0)->Opcode() == Op_RangeCheck)) { // is a if projection ?
1324       if_proj_list.push(current_proj);
1325     }
1326     if (follow_branches &&
1327         current_proj->Opcode() == Op_Region &&
1328         loop == get_loop(current_proj)) {
1329       regions.push(current_proj);
1330     }
1331     current_proj = idom(current_proj);
1332   }
1333 
1334   bool hoisted = false; // true if at least one proj is promoted
1335 
1336   if (!has_profile_predicates) {
1337     while (if_proj_list.size() > 0) {
1338       Node* n = if_proj_list.pop();
1339 
1340       ProjNode* proj = n->as_Proj();
1341       IfNode*   iff  = proj->in(0)->as_If();
1342 
1343       CallStaticJavaNode* call = proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none);
1344       if (call == NULL) {
1345         if (loop->is_loop_exit(iff)) {
1346           // stop processing the remaining projs in the list because the execution of them
1347           // depends on the condition of "iff" (iff->in(1)).
1348           break;
1349         } else {
1350           // Both arms are inside the loop. There are two cases:
1351           // (1) there is one backward branch. In this case, any remaining proj
1352           //     in the if_proj list post-dominates "iff". So, the condition of "iff"
1353           //     does not determine the execution the remining projs directly, and we
1354           //     can safely continue.
1355           // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj"
1356           //     does not dominate loop->tail(), so it can not be in the if_proj list.
1357           continue;
1358         }
1359       }
1360       Deoptimization::DeoptReason reason = Deoptimization::trap_request_reason(call->uncommon_trap_request());
1361       if (reason == Deoptimization::Reason_predicate) {
1362         break;
1363       }
1364 
1365       if (predicate_proj != NULL) {
1366         hoisted = loop_predication_impl_helper(loop, proj, predicate_proj, cl, zero, invar, Deoptimization::Reason_predicate) | hoisted;
1367       }
1368     } // end while
1369   }
1370 
1371   Node_List if_proj_list_freq(area);
1372   if (follow_branches) {
1373     PathFrequency pf(loop->_head, this);
1374 
1375     // Some projections were skipped by regular predicates because of
1376     // an early loop exit. Try them with profile data.
1377     while (if_proj_list.size() > 0) {
1378       Node* proj = if_proj_list.pop();
1379       float f = pf.to(proj);
1380       if (proj->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none) &&
1381           f * loop_trip_cnt >= 1) {
1382         hoisted = loop_predication_impl_helper(loop, proj->as_Proj(), profile_predicate_proj, cl, zero, invar, Deoptimization::Reason_profile_predicate) | hoisted;
1383       }
1384     }
1385 
1386     // And look into all branches
1387     Node_Stack stack(0);
1388     VectorSet seen(Thread::current()->resource_area());
1389     while (regions.size() > 0) {
1390       Node* c = regions.pop();
1391       loop_predication_follow_branches(c, loop, loop_trip_cnt, pf, stack, seen, if_proj_list_freq);
1392     }
1393 
1394     for (uint i = 0; i < if_proj_list_freq.size(); i++) {
1395       ProjNode* proj = if_proj_list_freq.at(i)->as_Proj();
1396       hoisted = loop_predication_impl_helper(loop, proj, profile_predicate_proj, cl, zero, invar, Deoptimization::Reason_profile_predicate) | hoisted;
1397     }
1398   }
1399 
1400 #ifndef PRODUCT
1401   // report that the loop predication has been actually performed
1402   // for this loop
1403   if (TraceLoopPredicate && hoisted) {
1404     tty->print("Loop Predication Performed:");
1405     loop->dump_head();
1406   }
1407 #endif
1408 
1409   head->verify_strip_mined(1);
1410 
1411   return hoisted;
1412 }
1413 
1414 //------------------------------loop_predication--------------------------------
1415 // driver routine for loop predication optimization
1416 bool IdealLoopTree::loop_predication( PhaseIdealLoop *phase) {
1417   bool hoisted = false;
1418   // Recursively promote predicates
< prev index next >