Mercurial > hg > truffle

comparison src/share/vm/opto/loopTransform.cpp @ 2383:9dc311b8473e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7008866: Missing loop predicate for loop with multiple entries Summary: Add predicates when loop head bytecode is parsed instead of when back branch bytecode is parsed. Reviewed-by: never
author kvn
date Mon, 21 Mar 2011 11:28:14 -0700
parents f95d63e2154a
children 1927db75dd85
comparison
equal deleted inserted replaced
2382:3ef1a1866a60 2383:9dc311b8473e
203 } else { 203 } else {
204 addx = new (phase->C, 3) AddINode(x, inv); 204 addx = new (phase->C, 3) AddINode(x, inv);
205 } 205 }
206 phase->register_new_node(addx, phase->get_ctrl(x)); 206 phase->register_new_node(addx, phase->get_ctrl(x));
207 phase->_igvn.replace_node(n1, addx); 207 phase->_igvn.replace_node(n1, addx);
208 assert(phase->get_loop(phase->get_ctrl(n1)) == this, "");
209 _body.yank(n1);
208 return addx; 210 return addx;
209 } 211 }
210 212
211 //---------------------reassociate_invariants----------------------------- 213 //---------------------reassociate_invariants-----------------------------
212 // Reassociate invariant expressions: 214 // Reassociate invariant expressions:
305 // Peeling a 'main' loop in a pre/main/post situation obfuscates the 307 // Peeling a 'main' loop in a pre/main/post situation obfuscates the
306 // 'pre' loop from the main and the 'pre' can no longer have it's 308 // 'pre' loop from the main and the 'pre' can no longer have it's
307 // iterations adjusted. Therefore, we need to declare this loop as 309 // iterations adjusted. Therefore, we need to declare this loop as
308 // no longer a 'main' loop; it will need new pre and post loops before 310 // no longer a 'main' loop; it will need new pre and post loops before
309 // we can do further RCE. 311 // we can do further RCE.
312 #ifndef PRODUCT
313 if (TraceLoopOpts) {
314 tty->print("Peel ");
315 loop->dump_head();
316 }
317 #endif
310 Node *h = loop->_head; 318 Node *h = loop->_head;
311 if( h->is_CountedLoop() ) { 319 if (h->is_CountedLoop()) {
312 CountedLoopNode *cl = h->as_CountedLoop(); 320 CountedLoopNode *cl = h->as_CountedLoop();
313 assert(cl->trip_count() > 0, "peeling a fully unrolled loop"); 321 assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
314 cl->set_trip_count(cl->trip_count() - 1); 322 cl->set_trip_count(cl->trip_count() - 1);
315 if( cl->is_main_loop() ) { 323 if (cl->is_main_loop()) {
316 cl->set_normal_loop(); 324 cl->set_normal_loop();
317 #ifndef PRODUCT 325 #ifndef PRODUCT
318 if( PrintOpto && VerifyLoopOptimizations ) { 326 if (PrintOpto && VerifyLoopOptimizations) {
319 tty->print("Peeling a 'main' loop; resetting to 'normal' "); 327 tty->print("Peeling a 'main' loop; resetting to 'normal' ");
320 loop->dump_head(); 328 loop->dump_head();
321 } 329 }
322 #endif 330 #endif
323 } 331 }
643 // Insert pre and post loops. If peel_only is set, the pre-loop can not have 651 // Insert pre and post loops. If peel_only is set, the pre-loop can not have
644 // more iterations added. It acts as a 'peel' only, no lower-bound RCE, no 652 // more iterations added. It acts as a 'peel' only, no lower-bound RCE, no
645 // alignment. Useful to unroll loops that do no array accesses. 653 // alignment. Useful to unroll loops that do no array accesses.
646 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) { 654 void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
647 655
656 #ifndef PRODUCT
657 if (TraceLoopOpts) {
658 if (peel_only)
659 tty->print("PeelMainPost ");
660 else
661 tty->print("PreMainPost ");
662 loop->dump_head();
663 }
664 #endif
648 C->set_major_progress(); 665 C->set_major_progress();
649 666
650 // Find common pieces of the loop being guarded with pre & post loops 667 // Find common pieces of the loop being guarded with pre & post loops
651 CountedLoopNode *main_head = loop->_head->as_CountedLoop(); 668 CountedLoopNode *main_head = loop->_head->as_CountedLoop();
652 assert( main_head->is_normal_loop(), "" ); 669 assert( main_head->is_normal_loop(), "" );
895 912
896 913
897 //------------------------------do_unroll-------------------------------------- 914 //------------------------------do_unroll--------------------------------------
898 // Unroll the loop body one step - make each trip do 2 iterations. 915 // Unroll the loop body one step - make each trip do 2 iterations.
899 void PhaseIdealLoop::do_unroll( IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip ) { 916 void PhaseIdealLoop::do_unroll( IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip ) {
900 assert( LoopUnrollLimit, "" ); 917 assert(LoopUnrollLimit, "");
918 CountedLoopNode *loop_head = loop->_head->as_CountedLoop();
919 CountedLoopEndNode *loop_end = loop_head->loopexit();
920 assert(loop_end, "");
901 #ifndef PRODUCT 921 #ifndef PRODUCT
902 if( PrintOpto && VerifyLoopOptimizations ) { 922 if (PrintOpto && VerifyLoopOptimizations) {
903 tty->print("Unrolling "); 923 tty->print("Unrolling ");
904 loop->dump_head(); 924 loop->dump_head();
925 } else if (TraceLoopOpts) {
926 tty->print("Unroll %d ", loop_head->unrolled_count()*2);
927 loop->dump_head();
905 } 928 }
906 #endif 929 #endif
907 CountedLoopNode *loop_head = loop->_head->as_CountedLoop();
908 CountedLoopEndNode *loop_end = loop_head->loopexit();
909 assert( loop_end, "" );
910 930
911 // Remember loop node count before unrolling to detect 931 // Remember loop node count before unrolling to detect
912 // if rounds of unroll,optimize are making progress 932 // if rounds of unroll,optimize are making progress
913 loop_head->set_node_count_before_unroll(loop->_body.size()); 933 loop_head->set_node_count_before_unroll(loop->_body.size());
914 934
915 Node *ctrl = loop_head->in(LoopNode::EntryControl); 935 Node *ctrl = loop_head->in(LoopNode::EntryControl);
916 Node *limit = loop_head->limit(); 936 Node *limit = loop_head->limit();
917 Node *init = loop_head->init_trip(); 937 Node *init = loop_head->init_trip();
918 Node *strid = loop_head->stride(); 938 Node *stride = loop_head->stride();
919 939
920 Node *opaq = NULL; 940 Node *opaq = NULL;
921 if( adjust_min_trip ) { // If not maximally unrolling, need adjustment 941 if( adjust_min_trip ) { // If not maximally unrolling, need adjustment
922 assert( loop_head->is_main_loop(), "" ); 942 assert( loop_head->is_main_loop(), "" );
923 assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" ); 943 assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" );
953 // CountedLoop this is exact (stride divides limit-init exactly). 973 // CountedLoop this is exact (stride divides limit-init exactly).
954 // We are going to double the loop body, so we want to knock off any 974 // We are going to double the loop body, so we want to knock off any
955 // odd iteration: (trip_cnt & ~1). Then back compute a new limit. 975 // odd iteration: (trip_cnt & ~1). Then back compute a new limit.
956 Node *span = new (C, 3) SubINode( limit, init ); 976 Node *span = new (C, 3) SubINode( limit, init );
957 register_new_node( span, ctrl ); 977 register_new_node( span, ctrl );
958 Node *trip = new (C, 3) DivINode( 0, span, strid ); 978 Node *trip = new (C, 3) DivINode( 0, span, stride );
959 register_new_node( trip, ctrl ); 979 register_new_node( trip, ctrl );
960 Node *mtwo = _igvn.intcon(-2); 980 Node *mtwo = _igvn.intcon(-2);
961 set_ctrl(mtwo, C->root()); 981 set_ctrl(mtwo, C->root());
962 Node *rond = new (C, 3) AndINode( trip, mtwo ); 982 Node *rond = new (C, 3) AndINode( trip, mtwo );
963 register_new_node( rond, ctrl ); 983 register_new_node( rond, ctrl );
964 Node *spn2 = new (C, 3) MulINode( rond, strid ); 984 Node *spn2 = new (C, 3) MulINode( rond, stride );
965 register_new_node( spn2, ctrl ); 985 register_new_node( spn2, ctrl );
966 Node *lim2 = new (C, 3) AddINode( spn2, init ); 986 Node *lim2 = new (C, 3) AddINode( spn2, init );
967 register_new_node( lim2, ctrl ); 987 register_new_node( lim2, ctrl );
968 988
969 // Hammer in the new limit 989 // Hammer in the new limit
1038 1058
1039 //------------------------------do_maximally_unroll---------------------------- 1059 //------------------------------do_maximally_unroll----------------------------
1040 1060
1041 void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) { 1061 void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) {
1042 CountedLoopNode *cl = loop->_head->as_CountedLoop(); 1062 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1043 assert( cl->trip_count() > 0, ""); 1063 assert(cl->trip_count() > 0, "");
1064 #ifndef PRODUCT
1065 if (TraceLoopOpts) {
1066 tty->print("MaxUnroll %d ", cl->trip_count());
1067 loop->dump_head();
1068 }
1069 #endif
1044 1070
1045 // If loop is tripping an odd number of times, peel odd iteration 1071 // If loop is tripping an odd number of times, peel odd iteration
1046 if( (cl->trip_count() & 1) == 1 ) { 1072 if ((cl->trip_count() & 1) == 1) {
1047 do_peeling( loop, old_new ); 1073 do_peeling(loop, old_new);
1048 } 1074 }
1049 1075
1050 // Now its tripping an even number of times remaining. Double loop body. 1076 // Now its tripping an even number of times remaining. Double loop body.
1051 // Do not adjust pre-guards; they are not needed and do not exist. 1077 // Do not adjust pre-guards; they are not needed and do not exist.
1052 if( cl->trip_count() > 0 ) { 1078 if (cl->trip_count() > 0) {
1053 do_unroll( loop, old_new, false ); 1079 do_unroll(loop, old_new, false);
1054 } 1080 }
1055 } 1081 }
1056 1082
1057 //------------------------------dominates_backedge--------------------------------- 1083 //------------------------------dominates_backedge---------------------------------
1058 // Returns true if ctrl is executed on every complete iteration 1084 // Returns true if ctrl is executed on every complete iteration
1225 1251
1226 //------------------------------do_range_check--------------------------------- 1252 //------------------------------do_range_check---------------------------------
1227 // Eliminate range-checks and other trip-counter vs loop-invariant tests. 1253 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
1228 void PhaseIdealLoop::do_range_check( IdealLoopTree *loop, Node_List &old_new ) { 1254 void PhaseIdealLoop::do_range_check( IdealLoopTree *loop, Node_List &old_new ) {
1229 #ifndef PRODUCT 1255 #ifndef PRODUCT
1230 if( PrintOpto && VerifyLoopOptimizations ) { 1256 if (PrintOpto && VerifyLoopOptimizations) {
1231 tty->print("Range Check Elimination "); 1257 tty->print("Range Check Elimination ");
1232 loop->dump_head(); 1258 loop->dump_head();
1259 } else if (TraceLoopOpts) {
1260 tty->print("RangeCheck ");
1261 loop->dump_head();
1233 } 1262 }
1234 #endif 1263 #endif
1235 assert( RangeCheckElimination, "" ); 1264 assert(RangeCheckElimination, "");
1236 CountedLoopNode *cl = loop->_head->as_CountedLoop(); 1265 CountedLoopNode *cl = loop->_head->as_CountedLoop();
1237 assert( cl->is_main_loop(), "" ); 1266 assert(cl->is_main_loop(), "");
1267
1268 // protect against stride not being a constant
1269 if (!cl->stride_is_con())
1270 return;
1238 1271
1239 // Find the trip counter; we are iteration splitting based on it 1272 // Find the trip counter; we are iteration splitting based on it
1240 Node *trip_counter = cl->phi(); 1273 Node *trip_counter = cl->phi();
1241 // Find the main loop limit; we will trim it's iterations 1274 // Find the main loop limit; we will trim it's iterations
1242 // to not ever trip end tests 1275 // to not ever trip end tests
1243 Node *main_limit = cl->limit(); 1276 Node *main_limit = cl->limit();
1277
1278 // Need to find the main-loop zero-trip guard
1279 Node *ctrl = cl->in(LoopNode::EntryControl);
1280 assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
1281 Node *iffm = ctrl->in(0);
1282 assert(iffm->Opcode() == Op_If, "");
1283 Node *bolzm = iffm->in(1);
1284 assert(bolzm->Opcode() == Op_Bool, "");
1285 Node *cmpzm = bolzm->in(1);
1286 assert(cmpzm->is_Cmp(), "");
1287 Node *opqzm = cmpzm->in(2);
1288 // Can not optimize a loop if pre-loop Opaque1 node is optimized
1289 // away and then another round of loop opts attempted.
1290 if (opqzm->Opcode() != Op_Opaque1)
1291 return;
1292 assert(opqzm->in(1) == main_limit, "do not understand situation");
1293
1244 // Find the pre-loop limit; we will expand it's iterations to 1294 // Find the pre-loop limit; we will expand it's iterations to
1245 // not ever trip low tests. 1295 // not ever trip low tests.
1246 Node *ctrl = cl->in(LoopNode::EntryControl);
1247 assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" );
1248 Node *iffm = ctrl->in(0);
1249 assert( iffm->Opcode() == Op_If, "" );
1250 Node *p_f = iffm->in(0); 1296 Node *p_f = iffm->in(0);
1251 assert( p_f->Opcode() == Op_IfFalse, "" ); 1297 assert(p_f->Opcode() == Op_IfFalse, "");
1252 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd(); 1298 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
1253 assert( pre_end->loopnode()->is_pre_loop(), "" ); 1299 assert(pre_end->loopnode()->is_pre_loop(), "");
1254 Node *pre_opaq1 = pre_end->limit(); 1300 Node *pre_opaq1 = pre_end->limit();
1255 // Occasionally it's possible for a pre-loop Opaque1 node to be 1301 // Occasionally it's possible for a pre-loop Opaque1 node to be
1256 // optimized away and then another round of loop opts attempted. 1302 // optimized away and then another round of loop opts attempted.
1257 // We can not optimize this particular loop in that case. 1303 // We can not optimize this particular loop in that case.
1258 if( pre_opaq1->Opcode() != Op_Opaque1 ) 1304 if (pre_opaq1->Opcode() != Op_Opaque1)
1259 return; 1305 return;
1260 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1; 1306 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
1261 Node *pre_limit = pre_opaq->in(1); 1307 Node *pre_limit = pre_opaq->in(1);
1262 1308
1263 // Where do we put new limit calculations 1309 // Where do we put new limit calculations
1264 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl); 1310 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
1265 1311
1266 // Ensure the original loop limit is available from the 1312 // Ensure the original loop limit is available from the
1267 // pre-loop Opaque1 node. 1313 // pre-loop Opaque1 node.
1268 Node *orig_limit = pre_opaq->original_loop_limit(); 1314 Node *orig_limit = pre_opaq->original_loop_limit();
1269 if( orig_limit == NULL || _igvn.type(orig_limit) == Type::TOP ) 1315 if (orig_limit == NULL || _igvn.type(orig_limit) == Type::TOP)
1270 return; 1316 return;
1271 1317
1272 // Need to find the main-loop zero-trip guard
1273 Node *bolzm = iffm->in(1);
1274 assert( bolzm->Opcode() == Op_Bool, "" );
1275 Node *cmpzm = bolzm->in(1);
1276 assert( cmpzm->is_Cmp(), "" );
1277 Node *opqzm = cmpzm->in(2);
1278 if( opqzm->Opcode() != Op_Opaque1 )
1279 return;
1280 assert( opqzm->in(1) == main_limit, "do not understand situation" );
1281
1282 // Must know if its a count-up or count-down loop 1318 // Must know if its a count-up or count-down loop
1283 1319
1284 // protect against stride not being a constant
1285 if ( !cl->stride_is_con() ) {
1286 return;
1287 }
1288 int stride_con = cl->stride_con(); 1320 int stride_con = cl->stride_con();
1289 Node *zero = _igvn.intcon(0); 1321 Node *zero = _igvn.intcon(0);
1290 Node *one = _igvn.intcon(1); 1322 Node *one = _igvn.intcon(1);
1291 set_ctrl(zero, C->root()); 1323 set_ctrl(zero, C->root());
1292 set_ctrl(one, C->root()); 1324 set_ctrl(one, C->root());
1564 // Micro-benchmark spamming. Policy is to always remove empty loops. 1596 // Micro-benchmark spamming. Policy is to always remove empty loops.
1565 // The 'DO' part is to replace the trip counter with the value it will 1597 // The 'DO' part is to replace the trip counter with the value it will
1566 // have on the last iteration. This will break the loop. 1598 // have on the last iteration. This will break the loop.
1567 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) { 1599 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) {
1568 // Minimum size must be empty loop 1600 // Minimum size must be empty loop
1569 if( _body.size() > 7/*number of nodes in an empty loop*/ ) return false; 1601 if (_body.size() > 7/*number of nodes in an empty loop*/)
1570 1602 return false;
1571 if( !_head->is_CountedLoop() ) return false; // Dead loop 1603
1604 if (!_head->is_CountedLoop())
1605 return false; // Dead loop
1572 CountedLoopNode *cl = _head->as_CountedLoop(); 1606 CountedLoopNode *cl = _head->as_CountedLoop();
1573 if( !cl->loopexit() ) return false; // Malformed loop 1607 if (!cl->loopexit())
1574 if( !phase->is_member(this,phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue)) ) ) 1608 return false; // Malformed loop
1609 if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
1575 return false; // Infinite loop 1610 return false; // Infinite loop
1576 #ifndef PRODUCT 1611 #ifndef PRODUCT
1577 if( PrintOpto ) 1612 if (PrintOpto) {
1578 tty->print_cr("Removing empty loop"); 1613 tty->print("Removing empty loop");
1614 this->dump_head();
1615 } else if (TraceLoopOpts) {
1616 tty->print("Empty ");
1617 this->dump_head();
1618 }
1579 #endif 1619 #endif
1580 #ifdef ASSERT 1620 #ifdef ASSERT
1581 // Ensure only one phi which is the iv. 1621 // Ensure only one phi which is the iv.
1582 Node* iv = NULL; 1622 Node* iv = NULL;
1583 for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) { 1623 for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) {
1718 1758
1719 //============================================================================= 1759 //=============================================================================
1720 //------------------------------iteration_split-------------------------------- 1760 //------------------------------iteration_split--------------------------------
1721 bool IdealLoopTree::iteration_split( PhaseIdealLoop *phase, Node_List &old_new ) { 1761 bool IdealLoopTree::iteration_split( PhaseIdealLoop *phase, Node_List &old_new ) {
1722 // Recursively iteration split nested loops 1762 // Recursively iteration split nested loops
1723 if( _child && !_child->iteration_split( phase, old_new )) 1763 if (_child && !_child->iteration_split(phase, old_new))
1724 return false; 1764 return false;
1725 1765
1726 // Clean out prior deadwood 1766 // Clean out prior deadwood
1727 DCE_loop_body(); 1767 DCE_loop_body();
1728 1768
1729 1769
1730 // Look for loop-exit tests with my 50/50 guesses from the Parsing stage. 1770 // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
1731 // Replace with a 1-in-10 exit guess. 1771 // Replace with a 1-in-10 exit guess.
1732 if( _parent /*not the root loop*/ && 1772 if (_parent /*not the root loop*/ &&
1733 !_irreducible && 1773 !_irreducible &&
1734 // Also ignore the occasional dead backedge 1774 // Also ignore the occasional dead backedge
1735 !tail()->is_top() ) { 1775 !tail()->is_top()) {
1736 adjust_loop_exit_prob(phase); 1776 adjust_loop_exit_prob(phase);
1737 } 1777 }
1738 1778
1739
1740 // Gate unrolling, RCE and peeling efforts. 1779 // Gate unrolling, RCE and peeling efforts.
1741 if( !_child && // If not an inner loop, do not split 1780 if (!_child && // If not an inner loop, do not split
1742 !_irreducible && 1781 !_irreducible &&
1743 _allow_optimizations && 1782 _allow_optimizations &&
1744 !tail()->is_top() ) { // Also ignore the occasional dead backedge 1783 !tail()->is_top()) { // Also ignore the occasional dead backedge
1745 if (!_has_call) { 1784 if (!_has_call) {
1746 if (!iteration_split_impl( phase, old_new )) { 1785 if (!iteration_split_impl(phase, old_new)) {
1747 return false; 1786 return false;
1748 } 1787 }
1749 } else if (policy_unswitching(phase)) { 1788 } else if (policy_unswitching(phase)) {
1750 phase->do_unswitching(this, old_new); 1789 phase->do_unswitching(this, old_new);
1751 } 1790 }
1752 } 1791 }
1753 1792
1754 // Minor offset re-organization to remove loop-fallout uses of 1793 // Minor offset re-organization to remove loop-fallout uses of
1755 // trip counter. 1794 // trip counter when there was no major reshaping.
1756 if( _head->is_CountedLoop() ) phase->reorg_offsets( this ); 1795 phase->reorg_offsets(this);
1757 if( _next && !_next->iteration_split( phase, old_new )) 1796
1797 if (_next && !_next->iteration_split(phase, old_new))
1758 return false; 1798 return false;
1759 return true; 1799 return true;
1760 } 1800 }
1761 1801
1762 //-------------------------------is_uncommon_trap_proj---------------------------- 1802 //-------------------------------is_uncommon_trap_proj----------------------------
1763 // Return true if proj is the form of "proj->[region->..]call_uct" 1803 // Return true if proj is the form of "proj->[region->..]call_uct"
1764 bool PhaseIdealLoop::is_uncommon_trap_proj(ProjNode* proj, bool must_reason_predicate) { 1804 bool PhaseIdealLoop::is_uncommon_trap_proj(ProjNode* proj, Deoptimization::DeoptReason reason) {
1765 int path_limit = 10; 1805 int path_limit = 10;
1766 assert(proj, "invalid argument"); 1806 assert(proj, "invalid argument");
1767 Node* out = proj; 1807 Node* out = proj;
1768 for (int ct = 0; ct < path_limit; ct++) { 1808 for (int ct = 0; ct < path_limit; ct++) {
1769 out = out->unique_ctrl_out(); 1809 out = out->unique_ctrl_out();
1770 if (out == NULL || out->is_Root() || out->is_Start()) 1810 if (out == NULL || out->is_Root() || out->is_Start())
1771 return false; 1811 return false;
1772 if (out->is_CallStaticJava()) { 1812 if (out->is_CallStaticJava()) {
1773 int req = out->as_CallStaticJava()->uncommon_trap_request(); 1813 int req = out->as_CallStaticJava()->uncommon_trap_request();
1774 if (req != 0) { 1814 if (req != 0) {
1775 Deoptimization::DeoptReason reason = Deoptimization::trap_request_reason(req); 1815 Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
1776 if (!must_reason_predicate || reason == Deoptimization::Reason_predicate){ 1816 if (trap_reason == reason || reason == Deoptimization::Reason_none) {
1777 return true; 1817 return true;
1778 } 1818 }
1779 } 1819 }
1780 return false; // don't do further after call 1820 return false; // don't do further after call
1781 } 1821 }
1788 // | 1828 // |
1789 // V 1829 // V
1790 // other_proj->[region->..]call_uct" 1830 // other_proj->[region->..]call_uct"
1791 // 1831 //
1792 // "must_reason_predicate" means the uct reason must be Reason_predicate 1832 // "must_reason_predicate" means the uct reason must be Reason_predicate
1793 bool PhaseIdealLoop::is_uncommon_trap_if_pattern(ProjNode *proj, bool must_reason_predicate) { 1833 bool PhaseIdealLoop::is_uncommon_trap_if_pattern(ProjNode *proj, Deoptimization::DeoptReason reason) {
1794 Node *in0 = proj->in(0); 1834 Node *in0 = proj->in(0);
1795 if (!in0->is_If()) return false; 1835 if (!in0->is_If()) return false;
1796 // Variation of a dead If node. 1836 // Variation of a dead If node.
1797 if (in0->outcnt() < 2) return false; 1837 if (in0->outcnt() < 2) return false;
1798 IfNode* iff = in0->as_If(); 1838 IfNode* iff = in0->as_If();
1799 1839
1800 // we need "If(Conv2B(Opaque1(...)))" pattern for must_reason_predicate 1840 // we need "If(Conv2B(Opaque1(...)))" pattern for reason_predicate
1801 if (must_reason_predicate) { 1841 if (reason != Deoptimization::Reason_none) {
1802 if (iff->in(1)->Opcode() != Op_Conv2B || 1842 if (iff->in(1)->Opcode() != Op_Conv2B ||
1803 iff->in(1)->in(1)->Opcode() != Op_Opaque1) { 1843 iff->in(1)->in(1)->Opcode() != Op_Opaque1) {
1804 return false; 1844 return false;
1805 } 1845 }
1806 } 1846 }
1807 1847
1808 ProjNode* other_proj = iff->proj_out(1-proj->_con)->as_Proj(); 1848 ProjNode* other_proj = iff->proj_out(1-proj->_con)->as_Proj();
1809 return is_uncommon_trap_proj(other_proj, must_reason_predicate); 1849 return is_uncommon_trap_proj(other_proj, reason);
1850 }
1851
1852 //-------------------------------register_control-------------------------
1853 void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {
1854 assert(n->is_CFG(), "must be control node");
1855 _igvn.register_new_node_with_optimizer(n);
1856 loop->_body.push(n);
1857 set_loop(n, loop);
1858 // When called from beautify_loops() idom is not constructed yet.
1859 if (_idom != NULL) {
1860 set_idom(n, pred, dom_depth(pred));
1861 }
1810 } 1862 }
1811 1863
1812 //------------------------------create_new_if_for_predicate------------------------ 1864 //------------------------------create_new_if_for_predicate------------------------
1813 // create a new if above the uct_if_pattern for the predicate to be promoted. 1865 // create a new if above the uct_if_pattern for the predicate to be promoted.
1814 // 1866 //
1841 // uncommon_trap 1893 // uncommon_trap
1842 // 1894 //
1843 // 1895 //
1844 // We will create a region to guard the uct call if there is no one there. 1896 // We will create a region to guard the uct call if there is no one there.
1845 // The true projecttion (if_cont) of the new_iff is returned. 1897 // The true projecttion (if_cont) of the new_iff is returned.
1846 ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj) { 1898 // This code is also used to clone predicates to clonned loops.
1847 assert(is_uncommon_trap_if_pattern(cont_proj, true), "must be a uct if pattern!"); 1899 ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
1900 Deoptimization::DeoptReason reason) {
1901 assert(is_uncommon_trap_if_pattern(cont_proj, reason), "must be a uct if pattern!");
1848 IfNode* iff = cont_proj->in(0)->as_If(); 1902 IfNode* iff = cont_proj->in(0)->as_If();
1849 1903
1850 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con); 1904 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
1851 Node *rgn = uncommon_proj->unique_ctrl_out(); 1905 Node *rgn = uncommon_proj->unique_ctrl_out();
1852 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); 1906 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
1853 1907
1854 if (!rgn->is_Region()) { // create a region to guard the call 1908 if (!rgn->is_Region()) { // create a region to guard the call
1855 assert(rgn->is_Call(), "must be call uct"); 1909 assert(rgn->is_Call(), "must be call uct");
1856 CallNode* call = rgn->as_Call(); 1910 CallNode* call = rgn->as_Call();
1911 IdealLoopTree* loop = get_loop(call);
1857 rgn = new (C, 1) RegionNode(1); 1912 rgn = new (C, 1) RegionNode(1);
1858 _igvn.set_type(rgn, rgn->bottom_type());
1859 rgn->add_req(uncommon_proj); 1913 rgn->add_req(uncommon_proj);
1860 set_idom(rgn, idom(uncommon_proj), dom_depth(uncommon_proj)+1); 1914 register_control(rgn, loop, uncommon_proj);
1861 _igvn.hash_delete(call); 1915 _igvn.hash_delete(call);
1862 call->set_req(0, rgn); 1916 call->set_req(0, rgn);
1863 } 1917 // When called from beautify_loops() idom is not constructed yet.
1864 1918 if (_idom != NULL) {
1919 set_idom(call, rgn, dom_depth(rgn));
1920 }
1921 }
1922
1923 Node* entry = iff->in(0);
1924 if (new_entry != NULL) {
1925 // Clonning the predicate to new location.
1926 entry = new_entry;
1927 }
1865 // Create new_iff 1928 // Create new_iff
1866 uint iffdd = dom_depth(iff); 1929 IdealLoopTree* lp = get_loop(entry);
1867 IdealLoopTree* lp = get_loop(iff); 1930 IfNode *new_iff = new (C, 2) IfNode(entry, NULL, iff->_prob, iff->_fcnt);
1868 IfNode *new_iff = new (C, 2) IfNode(iff->in(0), NULL, iff->_prob, iff->_fcnt); 1931 register_control(new_iff, lp, entry);
1869 register_node(new_iff, lp, idom(iff), iffdd);
1870 Node *if_cont = new (C, 1) IfTrueNode(new_iff); 1932 Node *if_cont = new (C, 1) IfTrueNode(new_iff);
1871 Node *if_uct = new (C, 1) IfFalseNode(new_iff); 1933 Node *if_uct = new (C, 1) IfFalseNode(new_iff);
1872 if (cont_proj->is_IfFalse()) { 1934 if (cont_proj->is_IfFalse()) {
1873 // Swap 1935 // Swap
1874 Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp; 1936 Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp;
1875 } 1937 }
1876 register_node(if_cont, lp, new_iff, iffdd); 1938 register_control(if_cont, lp, new_iff);
1877 register_node(if_uct, get_loop(rgn), new_iff, iffdd); 1939 register_control(if_uct, get_loop(rgn), new_iff);
1878
1879 // if_cont to iff
1880 _igvn.hash_delete(iff);
1881 iff->set_req(0, if_cont);
1882 set_idom(iff, if_cont, dom_depth(iff));
1883 1940
1884 // if_uct to rgn 1941 // if_uct to rgn
1885 _igvn.hash_delete(rgn); 1942 _igvn.hash_delete(rgn);
1886 rgn->add_req(if_uct); 1943 rgn->add_req(if_uct);
1887 Node* ridom = idom(rgn); 1944 // When called from beautify_loops() idom is not constructed yet.
1888 Node* nrdom = dom_lca(ridom, new_iff); 1945 if (_idom != NULL) {
1889 set_idom(rgn, nrdom, dom_depth(rgn)); 1946 Node* ridom = idom(rgn);
1890 1947 Node* nrdom = dom_lca(ridom, new_iff);
1948 set_idom(rgn, nrdom, dom_depth(rgn));
1949 }
1891 // rgn must have no phis 1950 // rgn must have no phis
1892 assert(!rgn->as_Region()->has_phi(), "region must have no phis"); 1951 assert(!rgn->as_Region()->has_phi(), "region must have no phis");
1893 1952
1953 if (new_entry == NULL) {
1954 // Attach if_cont to iff
1955 _igvn.hash_delete(iff);
1956 iff->set_req(0, if_cont);
1957 if (_idom != NULL) {
1958 set_idom(iff, if_cont, dom_depth(iff));
1959 }
1960 }
1894 return if_cont->as_Proj(); 1961 return if_cont->as_Proj();
1895 } 1962 }
1896 1963
1897 //------------------------------find_predicate_insertion_point-------------------------- 1964 //--------------------------find_predicate_insertion_point-------------------
1898 // Find a good location to insert a predicate 1965 // Find a good location to insert a predicate
1899 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c) { 1966 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
1900 if (start_c == C->root() || !start_c->is_Proj()) 1967 if (start_c == NULL || !start_c->is_Proj())
1901 return NULL; 1968 return NULL;
1902 if (is_uncommon_trap_if_pattern(start_c->as_Proj(), true/*Reason_Predicate*/)) { 1969 if (is_uncommon_trap_if_pattern(start_c->as_Proj(), reason)) {
1903 return start_c->as_Proj(); 1970 return start_c->as_Proj();
1971 }
1972 return NULL;
1973 }
1974
1975 //--------------------------find_predicate------------------------------------
1976 // Find a predicate
1977 Node* PhaseIdealLoop::find_predicate(Node* entry) {
1978 Node* predicate = NULL;
1979 if (UseLoopPredicate) {
1980 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1981 if (predicate != NULL) { // right pattern that can be used by loop predication
1982 assert(entry->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be");
1983 return entry;
1984 }
1904 } 1985 }
1905 return NULL; 1986 return NULL;
1906 } 1987 }
1907 1988
1908 //------------------------------Invariance----------------------------------- 1989 //------------------------------Invariance-----------------------------------
2149 if (!loop->_head->is_Loop()) { 2230 if (!loop->_head->is_Loop()) {
2150 // Could be a simple region when irreducible loops are present. 2231 // Could be a simple region when irreducible loops are present.
2151 return false; 2232 return false;
2152 } 2233 }
2153 2234
2235 if (loop->_head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
2236 // do nothing for infinite loops
2237 return false;
2238 }
2239
2154 CountedLoopNode *cl = NULL; 2240 CountedLoopNode *cl = NULL;
2155 if (loop->_head->is_CountedLoop()) { 2241 if (loop->_head->is_CountedLoop()) {
2156 cl = loop->_head->as_CountedLoop(); 2242 cl = loop->_head->as_CountedLoop();
2157 // do nothing for iteration-splitted loops 2243 // do nothing for iteration-splitted loops
2158 if (!cl->is_normal_loop()) return false; 2244 if (!cl->is_normal_loop()) return false;
2159 } 2245 }
2160 2246
2161 // Too many traps seen?
2162 bool tmt = C->too_many_traps(C->method(), 0, Deoptimization::Reason_predicate);
2163 int tc = C->trap_count(Deoptimization::Reason_predicate);
2164 if (tmt || tc > 0) {
2165 if (TraceLoopPredicate) {
2166 tty->print_cr("too many predicate traps: %d", tc);
2167 C->method()->print(); // which method has too many predicate traps
2168 tty->print_cr("");
2169 }
2170 return false;
2171 }
2172
2173 LoopNode *lpn = loop->_head->as_Loop(); 2247 LoopNode *lpn = loop->_head->as_Loop();
2174 Node* entry = lpn->in(LoopNode::EntryControl); 2248 Node* entry = lpn->in(LoopNode::EntryControl);
2175 2249
2176 ProjNode *predicate_proj = find_predicate_insertion_point(entry); 2250 ProjNode *predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2177 if (!predicate_proj){ 2251 if (!predicate_proj) {
2178 #ifndef PRODUCT 2252 #ifndef PRODUCT
2179 if (TraceLoopPredicate) { 2253 if (TraceLoopPredicate) {
2180 tty->print("missing predicate:"); 2254 tty->print("missing predicate:");
2181 loop->dump_head(); 2255 loop->dump_head();
2256 lpn->dump(1);
2182 } 2257 }
2183 #endif 2258 #endif
2184 return false; 2259 return false;
2185 } 2260 }
2186
2187 ConNode* zero = _igvn.intcon(0); 2261 ConNode* zero = _igvn.intcon(0);
2188 set_ctrl(zero, C->root()); 2262 set_ctrl(zero, C->root());
2189 Node *cond_false = new (C, 2) Conv2BNode(zero);
2190 register_new_node(cond_false, C->root());
2191 ConNode* one = _igvn.intcon(1);
2192 set_ctrl(one, C->root());
2193 Node *cond_true = new (C, 2) Conv2BNode(one);
2194 register_new_node(cond_true, C->root());
2195 2263
2196 ResourceArea *area = Thread::current()->resource_area(); 2264 ResourceArea *area = Thread::current()->resource_area();
2197 Invariance invar(area, loop); 2265 Invariance invar(area, loop);
2198 2266
2199 // Create list of if-projs such that a newer proj dominates all older 2267 // Create list of if-projs such that a newer proj dominates all older
2216 ProjNode* new_predicate_proj = NULL; 2284 ProjNode* new_predicate_proj = NULL;
2217 2285
2218 ProjNode* proj = if_proj_list.pop()->as_Proj(); 2286 ProjNode* proj = if_proj_list.pop()->as_Proj();
2219 IfNode* iff = proj->in(0)->as_If(); 2287 IfNode* iff = proj->in(0)->as_If();
2220 2288
2221 if (!is_uncommon_trap_if_pattern(proj)) { 2289 if (!is_uncommon_trap_if_pattern(proj, Deoptimization::Reason_none)) {
2222 if (loop->is_loop_exit(iff)) { 2290 if (loop->is_loop_exit(iff)) {
2223 // stop processing the remaining projs in the list because the execution of them 2291 // stop processing the remaining projs in the list because the execution of them
2224 // depends on the condition of "iff" (iff->in(1)). 2292 // depends on the condition of "iff" (iff->in(1)).
2225 break; 2293 break;
2226 } else { 2294 } else {
2240 continue; 2308 continue;
2241 } 2309 }
2242 BoolNode* bol = test->as_Bool(); 2310 BoolNode* bol = test->as_Bool();
2243 if (invar.is_invariant(bol)) { 2311 if (invar.is_invariant(bol)) {
2244 // Invariant test 2312 // Invariant test
2245 new_predicate_proj = create_new_if_for_predicate(predicate_proj); 2313 new_predicate_proj = create_new_if_for_predicate(predicate_proj, NULL,
2314 Deoptimization::Reason_predicate);
2246 Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0); 2315 Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0);
2247 BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool(); 2316 BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool();
2248 2317
2249 // Negate test if necessary 2318 // Negate test if necessary
2250 bool negated = false; 2319 bool negated = false;
2254 negated = true; 2323 negated = true;
2255 } 2324 }
2256 IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If(); 2325 IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If();
2257 _igvn.hash_delete(new_predicate_iff); 2326 _igvn.hash_delete(new_predicate_iff);
2258 new_predicate_iff->set_req(1, new_predicate_bol); 2327 new_predicate_iff->set_req(1, new_predicate_bol);
2259 if (TraceLoopPredicate) tty->print_cr("invariant if%s: %d", negated ? " negated" : "", new_predicate_iff->_idx); 2328 #ifndef PRODUCT
2260 2329 if (TraceLoopPredicate) {
2330 tty->print("Predicate invariant if%s: %d ", negated ? " negated" : "", new_predicate_iff->_idx);
2331 loop->dump_head();
2332 } else if (TraceLoopOpts) {
2333 tty->print("Predicate IC ");
2334 loop->dump_head();
2335 }
2336 #endif
2261 } else if (cl != NULL && loop->is_range_check_if(iff, this, invar)) { 2337 } else if (cl != NULL && loop->is_range_check_if(iff, this, invar)) {
2262 assert(proj->_con == predicate_proj->_con, "must match"); 2338 assert(proj->_con == predicate_proj->_con, "must match");
2263 2339
2264 // Range check for counted loops 2340 // Range check for counted loops
2265 const Node* cmp = bol->in(1)->as_Cmp(); 2341 const Node* cmp = bol->in(1)->as_Cmp();
2279 2355
2280 // Build if's for the upper and lower bound tests. The 2356 // Build if's for the upper and lower bound tests. The
2281 // lower_bound test will dominate the upper bound test and all 2357 // lower_bound test will dominate the upper bound test and all
2282 // cloned or created nodes will use the lower bound test as 2358 // cloned or created nodes will use the lower bound test as
2283 // their declared control. 2359 // their declared control.
2284 ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj); 2360 ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate);
2285 ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj); 2361 ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate);
2286 assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate"); 2362 assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate");
2287 Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0); 2363 Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0);
2288 2364
2289 // Perform cloning to keep Invariance state correct since the 2365 // Perform cloning to keep Invariance state correct since the
2290 // late schedule will place invariant things in the loop. 2366 // late schedule will place invariant things in the loop.
2309 if (TraceLoopPredicate) tty->print_cr("upper bound check if: %d", lower_bound_iff->_idx); 2385 if (TraceLoopPredicate) tty->print_cr("upper bound check if: %d", lower_bound_iff->_idx);
2310 2386
2311 // Fall through into rest of the clean up code which will move 2387 // Fall through into rest of the clean up code which will move
2312 // any dependent nodes onto the upper bound test. 2388 // any dependent nodes onto the upper bound test.
2313 new_predicate_proj = upper_bound_proj; 2389 new_predicate_proj = upper_bound_proj;
2390
2391 #ifndef PRODUCT
2392 if (TraceLoopOpts && !TraceLoopPredicate) {
2393 tty->print("Predicate RC ");
2394 loop->dump_head();
2395 }
2396 #endif
2314 } else { 2397 } else {
2315 // The other proj of the "iff" is a uncommon trap projection, and we can assume 2398 // Loop variant check (for example, range check in non-counted loop)
2316 // the other proj will not be executed ("executed" means uct raised). 2399 // with uncommon trap.
2317 continue; 2400 continue;
2318 } 2401 }
2319 2402 assert(new_predicate_proj != NULL, "sanity");
2320 // Success - attach condition (new_predicate_bol) to predicate if 2403 // Success - attach condition (new_predicate_bol) to predicate if
2321 invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate 2404 invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate
2322 2405
2323 // Eliminate the old if in the loop body 2406 // Eliminate the old If in the loop body
2324 _igvn.hash_delete(iff); 2407 dominated_by( new_predicate_proj, iff, proj->_con != new_predicate_proj->_con );
2325 iff->set_req(1, proj->is_IfFalse() ? cond_false : cond_true);
2326
2327 Node* ctrl = new_predicate_proj; // new control
2328 ProjNode* dp = proj; // old control
2329 assert(get_loop(dp) == loop, "guaranteed at the time of collecting proj");
2330 // Find nodes (depends only on the test) off the surviving projection;
2331 // move them outside the loop with the control of proj_clone
2332 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
2333 Node* cd = dp->fast_out(i); // Control-dependent node
2334 if (cd->depends_only_on_test()) {
2335 assert(cd->in(0) == dp, "");
2336 _igvn.hash_delete(cd);
2337 cd->set_req(0, ctrl); // ctrl, not NULL
2338 set_early_ctrl(cd);
2339 _igvn._worklist.push(cd);
2340 IdealLoopTree *new_loop = get_loop(get_ctrl(cd));
2341 if (new_loop != loop) {
2342 if (!loop->_child) loop->_body.yank(cd);
2343 if (!new_loop->_child ) new_loop->_body.push(cd);
2344 }
2345 --i;
2346 --imax;
2347 }
2348 }
2349 2408
2350 hoisted = true; 2409 hoisted = true;
2351 C->set_major_progress(); 2410 C->set_major_progress();
2352 } // end while 2411 } // end while
2353 2412