5007 return;
5008 }
5009
5010 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
5011 // is an exception edge, parsing doesn't set has_loops().
5012 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
5013 // No loops after all
5014 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
5015
5016 // There should always be an outer loop containing the Root and Return nodes.
5017 // If not, we have a degenerate empty program. Bail out in this case.
5018 if (!has_node(C->root())) {
5019 if (!_verify_only) {
5020 C->clear_major_progress();
5021 assert(false, "empty program detected during loop optimization");
5022 C->record_method_not_compilable("empty program detected during loop optimization");
5023 }
5024 return;
5025 }
5026
5027 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
5028 // Nothing to do, so get out
5029 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5030 !_verify_only && !bs->is_gc_specific_loop_opts_pass(_mode);
5031 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5032 bool strip_mined_loops_expanded = bs->strip_mined_loops_expanded(_mode);
5033 if (stop_early && !do_expensive_nodes) {
5034 return;
5035 }
5036
5037 // Set loop nesting depth
5038 _ltree_root->set_nest( 0 );
5039
5040 // Split shared headers and insert loop landing pads.
5041 // Do not bother doing this on the Root loop of course.
5042 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5043 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5044 if( _ltree_root->_child->beautify_loops( this ) ) {
5045 // Re-build loop tree!
5046 _ltree_root->_child = nullptr;
5047 _loop_or_ctrl.clear();
5048 reallocate_preorders();
5049 build_loop_tree();
5050 // Check for bailout, and return
5051 if (C->failing()) {
5052 return;
5089
5090 // Walk the DATA nodes and place into loops. Find earliest control
5091 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5092 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5093 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5094
5095 // Allocate stack with enough space to avoid frequent realloc
5096 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5097 Node_Stack nstack(stack_size);
5098
5099 visited.clear();
5100 Node_List worklist;
5101 // Don't need C->root() on worklist since
5102 // it will be processed among C->top() inputs
5103 worklist.push(C->top());
5104 visited.set(C->top()->_idx); // Set C->top() as visited now
5105 build_loop_early( visited, worklist, nstack );
5106
5107 // Given early legal placement, try finding counted loops. This placement
5108 // is good enough to discover most loop invariants.
5109 if (!_verify_me && !_verify_only && !strip_mined_loops_expanded) {
5110 _ltree_root->counted_loop( this );
5111 }
5112
5113 // Find latest loop placement. Find ideal loop placement.
5114 visited.clear();
5115 init_dom_lca_tags();
5116 // Need C->root() on worklist when processing outs
5117 worklist.push(C->root());
5118 NOT_PRODUCT( C->verify_graph_edges(); )
5119 worklist.push(C->top());
5120 build_loop_late( visited, worklist, nstack );
5121 if (C->failing()) { return; }
5122
5123 if (_verify_only) {
5124 C->restore_major_progress(old_progress);
5125 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5126 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5127 return;
5128 }
5129
5174 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5175 IdealLoopTree* lpt = iter.current();
5176 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5177 lpt->compute_trip_count(this, T_INT);
5178 if (!lpt->do_one_iteration_loop(this) &&
5179 !lpt->do_remove_empty_loop(this)) {
5180 AutoNodeBudget node_budget(this);
5181 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5182 lpt->policy_maximally_unroll(this)) {
5183 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5184 do_maximally_unroll(lpt, worklist);
5185 }
5186 }
5187 }
5188 }
5189
5190 C->restore_major_progress(old_progress);
5191 return;
5192 }
5193
5194 if (bs->optimize_loops(this, _mode, visited, nstack, worklist)) {
5195 return;
5196 }
5197
5198 if (ReassociateInvariants && !C->major_progress()) {
5199 // Reassociate invariants and prep for split_thru_phi
5200 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5201 IdealLoopTree* lpt = iter.current();
5202 if (!lpt->is_loop()) {
5203 continue;
5204 }
5205 Node* head = lpt->_head;
5206 if (!lpt->is_innermost()) continue;
5207
5208 // check for vectorized loops, any reassociation of invariants was already done
5209 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5210 continue;
5211 } else {
5212 AutoNodeBudget node_budget(this);
5213 lpt->reassociate_invariants(this);
5214 }
5215 // Because RCE opportunities can be masked by split_thru_phi,
5216 // look for RCE candidates and inhibit split_thru_phi
5217 // on just their loop-phi's for this pass of loop opts
6864 }
6865 // Find least loop nesting depth
6866 legal = idom(legal); // Bump up the IDOM tree
6867 // Check for lower nesting depth
6868 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6869 least = legal;
6870 }
6871 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6872
6873 if (least != early) {
6874 // Move the node above predicates as far up as possible so a
6875 // following pass of Loop Predication doesn't hoist a predicate
6876 // that depends on it above that node.
6877 const PredicateIterator predicate_iterator(least);
6878 DominatedPredicates dominated_predicates(early, least, this);
6879 predicate_iterator.for_each(dominated_predicates);
6880 least = dominated_predicates.earliest_dominated_predicate_entry();
6881 }
6882 // Try not to place code on a loop entry projection
6883 // which can inhibit range check elimination.
6884 if (least != early && !BarrierSet::barrier_set()->barrier_set_c2()->is_gc_specific_loop_opts_pass(_mode)) {
6885 Node* ctrl_out = least->unique_ctrl_out_or_null();
6886 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6887 least == ctrl_out->in(LoopNode::EntryControl) &&
6888 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6889 Node* least_dom = idom(least);
6890 if (get_loop(least_dom)->is_member(get_loop(least))) {
6891 least = least_dom;
6892 }
6893 }
6894 }
6895 // Don't extend live ranges of raw oops
6896 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6897 !n->bottom_type()->isa_rawptr()) {
6898 least = early;
6899 }
6900
6901 #ifdef ASSERT
6902 // Broken part of VerifyLoopOptimizations (F)
6903 // Reason:
6904 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|
5007 return;
5008 }
5009
5010 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
5011 // is an exception edge, parsing doesn't set has_loops().
5012 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
5013 // No loops after all
5014 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
5015
5016 // There should always be an outer loop containing the Root and Return nodes.
5017 // If not, we have a degenerate empty program. Bail out in this case.
5018 if (!has_node(C->root())) {
5019 if (!_verify_only) {
5020 C->clear_major_progress();
5021 assert(false, "empty program detected during loop optimization");
5022 C->record_method_not_compilable("empty program detected during loop optimization");
5023 }
5024 return;
5025 }
5026
5027 // Nothing to do, so get out
5028 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5029 !_verify_only;
5030 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5031 if (stop_early && !do_expensive_nodes) {
5032 return;
5033 }
5034
5035 // Set loop nesting depth
5036 _ltree_root->set_nest( 0 );
5037
5038 // Split shared headers and insert loop landing pads.
5039 // Do not bother doing this on the Root loop of course.
5040 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5041 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5042 if( _ltree_root->_child->beautify_loops( this ) ) {
5043 // Re-build loop tree!
5044 _ltree_root->_child = nullptr;
5045 _loop_or_ctrl.clear();
5046 reallocate_preorders();
5047 build_loop_tree();
5048 // Check for bailout, and return
5049 if (C->failing()) {
5050 return;
5087
5088 // Walk the DATA nodes and place into loops. Find earliest control
5089 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5090 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5091 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5092
5093 // Allocate stack with enough space to avoid frequent realloc
5094 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5095 Node_Stack nstack(stack_size);
5096
5097 visited.clear();
5098 Node_List worklist;
5099 // Don't need C->root() on worklist since
5100 // it will be processed among C->top() inputs
5101 worklist.push(C->top());
5102 visited.set(C->top()->_idx); // Set C->top() as visited now
5103 build_loop_early( visited, worklist, nstack );
5104
5105 // Given early legal placement, try finding counted loops. This placement
5106 // is good enough to discover most loop invariants.
5107 if (!_verify_me && !_verify_only) {
5108 _ltree_root->counted_loop( this );
5109 }
5110
5111 // Find latest loop placement. Find ideal loop placement.
5112 visited.clear();
5113 init_dom_lca_tags();
5114 // Need C->root() on worklist when processing outs
5115 worklist.push(C->root());
5116 NOT_PRODUCT( C->verify_graph_edges(); )
5117 worklist.push(C->top());
5118 build_loop_late( visited, worklist, nstack );
5119 if (C->failing()) { return; }
5120
5121 if (_verify_only) {
5122 C->restore_major_progress(old_progress);
5123 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5124 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5125 return;
5126 }
5127
5172 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5173 IdealLoopTree* lpt = iter.current();
5174 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5175 lpt->compute_trip_count(this, T_INT);
5176 if (!lpt->do_one_iteration_loop(this) &&
5177 !lpt->do_remove_empty_loop(this)) {
5178 AutoNodeBudget node_budget(this);
5179 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5180 lpt->policy_maximally_unroll(this)) {
5181 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5182 do_maximally_unroll(lpt, worklist);
5183 }
5184 }
5185 }
5186 }
5187
5188 C->restore_major_progress(old_progress);
5189 return;
5190 }
5191
5192 if (ReassociateInvariants && !C->major_progress()) {
5193 // Reassociate invariants and prep for split_thru_phi
5194 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5195 IdealLoopTree* lpt = iter.current();
5196 if (!lpt->is_loop()) {
5197 continue;
5198 }
5199 Node* head = lpt->_head;
5200 if (!lpt->is_innermost()) continue;
5201
5202 // check for vectorized loops, any reassociation of invariants was already done
5203 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5204 continue;
5205 } else {
5206 AutoNodeBudget node_budget(this);
5207 lpt->reassociate_invariants(this);
5208 }
5209 // Because RCE opportunities can be masked by split_thru_phi,
5210 // look for RCE candidates and inhibit split_thru_phi
5211 // on just their loop-phi's for this pass of loop opts
6858 }
6859 // Find least loop nesting depth
6860 legal = idom(legal); // Bump up the IDOM tree
6861 // Check for lower nesting depth
6862 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6863 least = legal;
6864 }
6865 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6866
6867 if (least != early) {
6868 // Move the node above predicates as far up as possible so a
6869 // following pass of Loop Predication doesn't hoist a predicate
6870 // that depends on it above that node.
6871 const PredicateIterator predicate_iterator(least);
6872 DominatedPredicates dominated_predicates(early, least, this);
6873 predicate_iterator.for_each(dominated_predicates);
6874 least = dominated_predicates.earliest_dominated_predicate_entry();
6875 }
6876 // Try not to place code on a loop entry projection
6877 // which can inhibit range check elimination.
6878 if (least != early) {
6879 Node* ctrl_out = least->unique_ctrl_out_or_null();
6880 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6881 least == ctrl_out->in(LoopNode::EntryControl) &&
6882 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6883 Node* least_dom = idom(least);
6884 if (get_loop(least_dom)->is_member(get_loop(least))) {
6885 least = least_dom;
6886 }
6887 }
6888 }
6889 // Don't extend live ranges of raw oops
6890 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6891 !n->bottom_type()->isa_rawptr()) {
6892 least = early;
6893 }
6894
6895 #ifdef ASSERT
6896 // Broken part of VerifyLoopOptimizations (F)
6897 // Reason:
6898 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|