4980 return;
4981 }
4982
4983 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
4984 // is an exception edge, parsing doesn't set has_loops().
4985 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
4986 // No loops after all
4987 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
4988
4989 // There should always be an outer loop containing the Root and Return nodes.
4990 // If not, we have a degenerate empty program. Bail out in this case.
4991 if (!has_node(C->root())) {
4992 if (!_verify_only) {
4993 C->clear_major_progress();
4994 assert(false, "empty program detected during loop optimization");
4995 C->record_method_not_compilable("empty program detected during loop optimization");
4996 }
4997 return;
4998 }
4999
5000 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
5001 // Nothing to do, so get out
5002 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5003 !_verify_only && !bs->is_gc_specific_loop_opts_pass(_mode);
5004 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5005 bool strip_mined_loops_expanded = bs->strip_mined_loops_expanded(_mode);
5006 if (stop_early && !do_expensive_nodes) {
5007 return;
5008 }
5009
5010 // Set loop nesting depth
5011 _ltree_root->set_nest( 0 );
5012
5013 // Split shared headers and insert loop landing pads.
5014 // Do not bother doing this on the Root loop of course.
5015 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5016 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5017 if( _ltree_root->_child->beautify_loops( this ) ) {
5018 // Re-build loop tree!
5019 _ltree_root->_child = nullptr;
5020 _loop_or_ctrl.clear();
5021 reallocate_preorders();
5022 build_loop_tree();
5023 // Check for bailout, and return
5024 if (C->failing()) {
5025 return;
5062
5063 // Walk the DATA nodes and place into loops. Find earliest control
5064 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5065 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5066 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5067
5068 // Allocate stack with enough space to avoid frequent realloc
5069 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5070 Node_Stack nstack(stack_size);
5071
5072 visited.clear();
5073 Node_List worklist;
5074 // Don't need C->root() on worklist since
5075 // it will be processed among C->top() inputs
5076 worklist.push(C->top());
5077 visited.set(C->top()->_idx); // Set C->top() as visited now
5078 build_loop_early( visited, worklist, nstack );
5079
5080 // Given early legal placement, try finding counted loops. This placement
5081 // is good enough to discover most loop invariants.
5082 if (!_verify_me && !_verify_only && !strip_mined_loops_expanded) {
5083 _ltree_root->counted_loop( this );
5084 }
5085
5086 // Find latest loop placement. Find ideal loop placement.
5087 visited.clear();
5088 init_dom_lca_tags();
5089 // Need C->root() on worklist when processing outs
5090 worklist.push(C->root());
5091 NOT_PRODUCT( C->verify_graph_edges(); )
5092 worklist.push(C->top());
5093 build_loop_late( visited, worklist, nstack );
5094 if (C->failing()) { return; }
5095
5096 if (_verify_only) {
5097 C->restore_major_progress(old_progress);
5098 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5099 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5100 return;
5101 }
5102
5147 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5148 IdealLoopTree* lpt = iter.current();
5149 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5150 lpt->compute_trip_count(this, T_INT);
5151 if (!lpt->do_one_iteration_loop(this) &&
5152 !lpt->do_remove_empty_loop(this)) {
5153 AutoNodeBudget node_budget(this);
5154 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5155 lpt->policy_maximally_unroll(this)) {
5156 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5157 do_maximally_unroll(lpt, worklist);
5158 }
5159 }
5160 }
5161 }
5162
5163 C->restore_major_progress(old_progress);
5164 return;
5165 }
5166
5167 if (bs->optimize_loops(this, _mode, visited, nstack, worklist)) {
5168 return;
5169 }
5170
5171 if (ReassociateInvariants && !C->major_progress()) {
5172 // Reassociate invariants and prep for split_thru_phi
5173 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5174 IdealLoopTree* lpt = iter.current();
5175 if (!lpt->is_loop()) {
5176 continue;
5177 }
5178 Node* head = lpt->_head;
5179 if (!lpt->is_innermost()) continue;
5180
5181 // check for vectorized loops, any reassociation of invariants was already done
5182 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5183 continue;
5184 } else {
5185 AutoNodeBudget node_budget(this);
5186 lpt->reassociate_invariants(this);
5187 }
5188 // Because RCE opportunities can be masked by split_thru_phi,
5189 // look for RCE candidates and inhibit split_thru_phi
5190 // on just their loop-phi's for this pass of loop opts
6837 }
6838 // Find least loop nesting depth
6839 legal = idom(legal); // Bump up the IDOM tree
6840 // Check for lower nesting depth
6841 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6842 least = legal;
6843 }
6844 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6845
6846 if (least != early) {
6847 // Move the node above predicates as far up as possible so a
6848 // following pass of Loop Predication doesn't hoist a predicate
6849 // that depends on it above that node.
6850 const PredicateIterator predicate_iterator(least);
6851 DominatedPredicates dominated_predicates(early, least, this);
6852 predicate_iterator.for_each(dominated_predicates);
6853 least = dominated_predicates.earliest_dominated_predicate_entry();
6854 }
6855 // Try not to place code on a loop entry projection
6856 // which can inhibit range check elimination.
6857 if (least != early && !BarrierSet::barrier_set()->barrier_set_c2()->is_gc_specific_loop_opts_pass(_mode)) {
6858 Node* ctrl_out = least->unique_ctrl_out_or_null();
6859 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6860 least == ctrl_out->in(LoopNode::EntryControl) &&
6861 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6862 Node* least_dom = idom(least);
6863 if (get_loop(least_dom)->is_member(get_loop(least))) {
6864 least = least_dom;
6865 }
6866 }
6867 }
6868 // Don't extend live ranges of raw oops
6869 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6870 !n->bottom_type()->isa_rawptr()) {
6871 least = early;
6872 }
6873
6874 #ifdef ASSERT
6875 // Broken part of VerifyLoopOptimizations (F)
6876 // Reason:
6877 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|
4980 return;
4981 }
4982
4983 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
4984 // is an exception edge, parsing doesn't set has_loops().
4985 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
4986 // No loops after all
4987 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
4988
4989 // There should always be an outer loop containing the Root and Return nodes.
4990 // If not, we have a degenerate empty program. Bail out in this case.
4991 if (!has_node(C->root())) {
4992 if (!_verify_only) {
4993 C->clear_major_progress();
4994 assert(false, "empty program detected during loop optimization");
4995 C->record_method_not_compilable("empty program detected during loop optimization");
4996 }
4997 return;
4998 }
4999
5000 // Nothing to do, so get out
5001 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5002 !_verify_only;
5003 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5004 if (stop_early && !do_expensive_nodes) {
5005 return;
5006 }
5007
5008 // Set loop nesting depth
5009 _ltree_root->set_nest( 0 );
5010
5011 // Split shared headers and insert loop landing pads.
5012 // Do not bother doing this on the Root loop of course.
5013 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5014 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5015 if( _ltree_root->_child->beautify_loops( this ) ) {
5016 // Re-build loop tree!
5017 _ltree_root->_child = nullptr;
5018 _loop_or_ctrl.clear();
5019 reallocate_preorders();
5020 build_loop_tree();
5021 // Check for bailout, and return
5022 if (C->failing()) {
5023 return;
5060
5061 // Walk the DATA nodes and place into loops. Find earliest control
5062 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5063 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5064 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5065
5066 // Allocate stack with enough space to avoid frequent realloc
5067 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5068 Node_Stack nstack(stack_size);
5069
5070 visited.clear();
5071 Node_List worklist;
5072 // Don't need C->root() on worklist since
5073 // it will be processed among C->top() inputs
5074 worklist.push(C->top());
5075 visited.set(C->top()->_idx); // Set C->top() as visited now
5076 build_loop_early( visited, worklist, nstack );
5077
5078 // Given early legal placement, try finding counted loops. This placement
5079 // is good enough to discover most loop invariants.
5080 if (!_verify_me && !_verify_only) {
5081 _ltree_root->counted_loop( this );
5082 }
5083
5084 // Find latest loop placement. Find ideal loop placement.
5085 visited.clear();
5086 init_dom_lca_tags();
5087 // Need C->root() on worklist when processing outs
5088 worklist.push(C->root());
5089 NOT_PRODUCT( C->verify_graph_edges(); )
5090 worklist.push(C->top());
5091 build_loop_late( visited, worklist, nstack );
5092 if (C->failing()) { return; }
5093
5094 if (_verify_only) {
5095 C->restore_major_progress(old_progress);
5096 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5097 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5098 return;
5099 }
5100
5145 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5146 IdealLoopTree* lpt = iter.current();
5147 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5148 lpt->compute_trip_count(this, T_INT);
5149 if (!lpt->do_one_iteration_loop(this) &&
5150 !lpt->do_remove_empty_loop(this)) {
5151 AutoNodeBudget node_budget(this);
5152 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5153 lpt->policy_maximally_unroll(this)) {
5154 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5155 do_maximally_unroll(lpt, worklist);
5156 }
5157 }
5158 }
5159 }
5160
5161 C->restore_major_progress(old_progress);
5162 return;
5163 }
5164
5165 if (ReassociateInvariants && !C->major_progress()) {
5166 // Reassociate invariants and prep for split_thru_phi
5167 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5168 IdealLoopTree* lpt = iter.current();
5169 if (!lpt->is_loop()) {
5170 continue;
5171 }
5172 Node* head = lpt->_head;
5173 if (!lpt->is_innermost()) continue;
5174
5175 // check for vectorized loops, any reassociation of invariants was already done
5176 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5177 continue;
5178 } else {
5179 AutoNodeBudget node_budget(this);
5180 lpt->reassociate_invariants(this);
5181 }
5182 // Because RCE opportunities can be masked by split_thru_phi,
5183 // look for RCE candidates and inhibit split_thru_phi
5184 // on just their loop-phi's for this pass of loop opts
6831 }
6832 // Find least loop nesting depth
6833 legal = idom(legal); // Bump up the IDOM tree
6834 // Check for lower nesting depth
6835 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6836 least = legal;
6837 }
6838 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6839
6840 if (least != early) {
6841 // Move the node above predicates as far up as possible so a
6842 // following pass of Loop Predication doesn't hoist a predicate
6843 // that depends on it above that node.
6844 const PredicateIterator predicate_iterator(least);
6845 DominatedPredicates dominated_predicates(early, least, this);
6846 predicate_iterator.for_each(dominated_predicates);
6847 least = dominated_predicates.earliest_dominated_predicate_entry();
6848 }
6849 // Try not to place code on a loop entry projection
6850 // which can inhibit range check elimination.
6851 if (least != early) {
6852 Node* ctrl_out = least->unique_ctrl_out_or_null();
6853 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6854 least == ctrl_out->in(LoopNode::EntryControl) &&
6855 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6856 Node* least_dom = idom(least);
6857 if (get_loop(least_dom)->is_member(get_loop(least))) {
6858 least = least_dom;
6859 }
6860 }
6861 }
6862 // Don't extend live ranges of raw oops
6863 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6864 !n->bottom_type()->isa_rawptr()) {
6865 least = early;
6866 }
6867
6868 #ifdef ASSERT
6869 // Broken part of VerifyLoopOptimizations (F)
6870 // Reason:
6871 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|