src/share/vm/opto/loopnode.cpp

Print this page
rev 4773 : 8005849: JEP 167: Event-Based JVM Tracing
Reviewed-by: acorn, coleenp, sla
Contributed-by: Karen Kinnear <karen.kinnear@oracle.com>, Bengt Rutisson <bengt.rutisson@oracle.com>, Calvin Cheung <calvin.cheung@oracle.com>, Erik Gahlin <erik.gahlin@oracle.com>, Erik Helin <erik.helin@oracle.com>, Jesper Wilhelmsson <jesper.wilhelmsson@oracle.com>, Keith McGuigan <keith.mcguigan@oracle.com>, Mattias Tobiasson <mattias.tobiasson@oracle.com>, Markus Gronlund <markus.gronlund@oracle.com>, Mikael Auno <mikael.auno@oracle.com>, Nils Eliasson <nils.eliasson@oracle.com>, Nils Loodin <nils.loodin@oracle.com>, Rickard Backman <rickard.backman@oracle.com>, Staffan Larsen <staffan.larsen@oracle.com>, Stefan Karlsson <stefan.karlsson@oracle.com>, Yekaterina Kantserova <yekaterina.kantserova@oracle.com>
   1 /*
   2  * Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  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  *


 423     return false; // Bail out
 424   }
 425 
 426   const TypeInt* init_t = gvn->type(init_trip)->is_int();
 427   const TypeInt* limit_t = gvn->type(limit)->is_int();
 428 
 429   if (stride_con > 0) {
 430     jlong init_p = (jlong)init_t->_lo + stride_con;
 431     if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
 432       return false; // cyclic loop or this loop trips only once
 433   } else {
 434     jlong init_p = (jlong)init_t->_hi + stride_con;
 435     if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
 436       return false; // cyclic loop or this loop trips only once
 437   }
 438 
 439   // =================================================
 440   // ---- SUCCESS!   Found A Trip-Counted Loop!  -----
 441   //
 442   assert(x->Opcode() == Op_Loop, "regular loops only");
 443   C->print_method("Before CountedLoop", 3);
 444 
 445   Node *hook = new (C) Node(6);
 446 
 447   if (LoopLimitCheck) {
 448 
 449   // ===================================================
 450   // Generate loop limit check to avoid integer overflow
 451   // in cases like next (cyclic loops):
 452   //
 453   // for (i=0; i <= max_jint; i++) {}
 454   // for (i=0; i <  max_jint; i+=2) {}
 455   //
 456   //
 457   // Limit check predicate depends on the loop test:
 458   //
 459   // for(;i != limit; i++)       --> limit <= (max_jint)
 460   // for(;i <  limit; i+=stride) --> limit <= (max_jint - stride + 1)
 461   // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride    )
 462   //
 463 


 774     lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
 775     if (loop->_safepts != NULL) {
 776       loop->_safepts->yank(sfpt2);
 777     }
 778   }
 779 
 780   // Free up intermediate goo
 781   _igvn.remove_dead_node(hook);
 782 
 783 #ifdef ASSERT
 784   assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
 785   assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
 786 #endif
 787 #ifndef PRODUCT
 788   if (TraceLoopOpts) {
 789     tty->print("Counted      ");
 790     loop->dump_head();
 791   }
 792 #endif
 793 
 794   C->print_method("After CountedLoop", 3);
 795 
 796   return true;
 797 }
 798 
 799 //----------------------exact_limit-------------------------------------------
 800 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
 801   assert(loop->_head->is_CountedLoop(), "");
 802   CountedLoopNode *cl = loop->_head->as_CountedLoop();
 803   assert(cl->is_valid_counted_loop(), "");
 804 
 805   if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 ||
 806       cl->limit()->Opcode() == Op_LoopLimit) {
 807     // Old code has exact limit (it could be incorrect in case of int overflow).
 808     // Loop limit is exact with stride == 1. And loop may already have exact limit.
 809     return cl->limit();
 810   }
 811   Node *limit = NULL;
 812 #ifdef ASSERT
 813   BoolTest::mask bt = cl->loopexit()->test_trip();
 814   assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");


2147       C->clear_major_progress();
2148       C->record_method_not_compilable("empty program detected during loop optimization");
2149     }
2150     return;
2151   }
2152 
2153   // Nothing to do, so get out
2154   bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2155   bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2156   if (stop_early && !do_expensive_nodes) {
2157     _igvn.optimize();           // Cleanup NeverBranches
2158     return;
2159   }
2160 
2161   // Set loop nesting depth
2162   _ltree_root->set_nest( 0 );
2163 
2164   // Split shared headers and insert loop landing pads.
2165   // Do not bother doing this on the Root loop of course.
2166   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2167     C->print_method("Before beautify loops", 3);
2168     if( _ltree_root->_child->beautify_loops( this ) ) {
2169       // Re-build loop tree!
2170       _ltree_root->_child = NULL;
2171       _nodes.clear();
2172       reallocate_preorders();
2173       build_loop_tree();
2174       // Check for bailout, and return
2175       if (C->failing()) {
2176         return;
2177       }
2178       // Reset loop nesting depth
2179       _ltree_root->set_nest( 0 );
2180 
2181       C->print_method("After beautify loops", 3);
2182     }
2183   }
2184 
2185   // Build Dominators for elision of NULL checks & loop finding.
2186   // Since nodes do not have a slot for immediate dominator, make
2187   // a persistent side array for that info indexed on node->_idx.
2188   _idom_size = C->unique();
2189   _idom      = NEW_RESOURCE_ARRAY( Node*, _idom_size );
2190   _dom_depth = NEW_RESOURCE_ARRAY( uint,  _idom_size );
2191   _dom_stk   = NULL; // Allocated on demand in recompute_dom_depth
2192   memset( _dom_depth, 0, _idom_size * sizeof(uint) );
2193 
2194   Dominators();
2195 
2196   if (!_verify_only) {
2197     // As a side effect, Dominators removed any unreachable CFG paths
2198     // into RegionNodes.  It doesn't do this test against Root, so
2199     // we do it here.
2200     for( uint i = 1; i < C->root()->req(); i++ ) {
2201       if( !_nodes[C->root()->in(i)->_idx] ) {    // Dead path into Root?


   1 /*
   2  * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  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  *


 423     return false; // Bail out
 424   }
 425 
 426   const TypeInt* init_t = gvn->type(init_trip)->is_int();
 427   const TypeInt* limit_t = gvn->type(limit)->is_int();
 428 
 429   if (stride_con > 0) {
 430     jlong init_p = (jlong)init_t->_lo + stride_con;
 431     if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)
 432       return false; // cyclic loop or this loop trips only once
 433   } else {
 434     jlong init_p = (jlong)init_t->_hi + stride_con;
 435     if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)
 436       return false; // cyclic loop or this loop trips only once
 437   }
 438 
 439   // =================================================
 440   // ---- SUCCESS!   Found A Trip-Counted Loop!  -----
 441   //
 442   assert(x->Opcode() == Op_Loop, "regular loops only");
 443   C->print_method(PHASE_BEFORE_CLOOPS, 3);
 444 
 445   Node *hook = new (C) Node(6);
 446 
 447   if (LoopLimitCheck) {
 448 
 449   // ===================================================
 450   // Generate loop limit check to avoid integer overflow
 451   // in cases like next (cyclic loops):
 452   //
 453   // for (i=0; i <= max_jint; i++) {}
 454   // for (i=0; i <  max_jint; i+=2) {}
 455   //
 456   //
 457   // Limit check predicate depends on the loop test:
 458   //
 459   // for(;i != limit; i++)       --> limit <= (max_jint)
 460   // for(;i <  limit; i+=stride) --> limit <= (max_jint - stride + 1)
 461   // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride    )
 462   //
 463 


 774     lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));
 775     if (loop->_safepts != NULL) {
 776       loop->_safepts->yank(sfpt2);
 777     }
 778   }
 779 
 780   // Free up intermediate goo
 781   _igvn.remove_dead_node(hook);
 782 
 783 #ifdef ASSERT
 784   assert(l->is_valid_counted_loop(), "counted loop shape is messed up");
 785   assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" );
 786 #endif
 787 #ifndef PRODUCT
 788   if (TraceLoopOpts) {
 789     tty->print("Counted      ");
 790     loop->dump_head();
 791   }
 792 #endif
 793 
 794   C->print_method(PHASE_AFTER_CLOOPS, 3);
 795 
 796   return true;
 797 }
 798 
 799 //----------------------exact_limit-------------------------------------------
 800 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) {
 801   assert(loop->_head->is_CountedLoop(), "");
 802   CountedLoopNode *cl = loop->_head->as_CountedLoop();
 803   assert(cl->is_valid_counted_loop(), "");
 804 
 805   if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 ||
 806       cl->limit()->Opcode() == Op_LoopLimit) {
 807     // Old code has exact limit (it could be incorrect in case of int overflow).
 808     // Loop limit is exact with stride == 1. And loop may already have exact limit.
 809     return cl->limit();
 810   }
 811   Node *limit = NULL;
 812 #ifdef ASSERT
 813   BoolTest::mask bt = cl->loopexit()->test_trip();
 814   assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");


2147       C->clear_major_progress();
2148       C->record_method_not_compilable("empty program detected during loop optimization");
2149     }
2150     return;
2151   }
2152 
2153   // Nothing to do, so get out
2154   bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2155   bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2156   if (stop_early && !do_expensive_nodes) {
2157     _igvn.optimize();           // Cleanup NeverBranches
2158     return;
2159   }
2160 
2161   // Set loop nesting depth
2162   _ltree_root->set_nest( 0 );
2163 
2164   // Split shared headers and insert loop landing pads.
2165   // Do not bother doing this on the Root loop of course.
2166   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2167     C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2168     if( _ltree_root->_child->beautify_loops( this ) ) {
2169       // Re-build loop tree!
2170       _ltree_root->_child = NULL;
2171       _nodes.clear();
2172       reallocate_preorders();
2173       build_loop_tree();
2174       // Check for bailout, and return
2175       if (C->failing()) {
2176         return;
2177       }
2178       // Reset loop nesting depth
2179       _ltree_root->set_nest( 0 );
2180 
2181       C->print_method(PHASE_AFTER_BEAUTIFY_LOOPS, 3);
2182     }
2183   }
2184 
2185   // Build Dominators for elision of NULL checks & loop finding.
2186   // Since nodes do not have a slot for immediate dominator, make
2187   // a persistent side array for that info indexed on node->_idx.
2188   _idom_size = C->unique();
2189   _idom      = NEW_RESOURCE_ARRAY( Node*, _idom_size );
2190   _dom_depth = NEW_RESOURCE_ARRAY( uint,  _idom_size );
2191   _dom_stk   = NULL; // Allocated on demand in recompute_dom_depth
2192   memset( _dom_depth, 0, _idom_size * sizeof(uint) );
2193 
2194   Dominators();
2195 
2196   if (!_verify_only) {
2197     // As a side effect, Dominators removed any unreachable CFG paths
2198     // into RegionNodes.  It doesn't do this test against Root, so
2199     // we do it here.
2200     for( uint i = 1; i < C->root()->req(); i++ ) {
2201       if( !_nodes[C->root()->in(i)->_idx] ) {    // Dead path into Root?