204 next = parent_ctl->in(0)->in(0)->in(0);
205 } else {
206 // Check if parent control has a single projection (this
207 // control is the only possible successor of the parent
208 // control). If so, we can try to move the node above the
209 // parent control.
210 int nb_ctl_proj = 0;
211 for (DUIterator_Fast imax, i = parent_ctl->fast_outs(imax); i < imax; i++) {
212 Node *p = parent_ctl->fast_out(i);
213 if (p->is_Proj() && p->is_CFG()) {
214 nb_ctl_proj++;
215 if (nb_ctl_proj > 1) {
216 break;
217 }
218 }
219 }
220
221 if (nb_ctl_proj > 1) {
222 break;
223 }
224 assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call() ||
225 BarrierSet::barrier_set()->barrier_set_c2()->is_gc_barrier_node(parent_ctl), "unexpected node");
226 assert(idom(ctl) == parent_ctl, "strange");
227 next = idom(parent_ctl);
228 }
229 } else {
230 next = idom(ctl);
231 }
232 if (next->is_Root() || next->is_Start() || dom_depth(next) < min_dom_depth) {
233 break;
234 }
235 ctl = next;
236 }
237
238 if (ctl != n->in(0)) {
239 _igvn.replace_input_of(n, 0, ctl);
240 _igvn.hash_insert(n);
241 }
242
243 return ctl;
244 }
245
5048 return;
5049 }
5050
5051 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
5052 // is an exception edge, parsing doesn't set has_loops().
5053 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
5054 // No loops after all
5055 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
5056
5057 // There should always be an outer loop containing the Root and Return nodes.
5058 // If not, we have a degenerate empty program. Bail out in this case.
5059 if (!has_node(C->root())) {
5060 if (!_verify_only) {
5061 C->clear_major_progress();
5062 assert(false, "empty program detected during loop optimization");
5063 C->record_method_not_compilable("empty program detected during loop optimization");
5064 }
5065 return;
5066 }
5067
5068 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
5069 // Nothing to do, so get out
5070 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5071 !_verify_only && !bs->is_gc_specific_loop_opts_pass(_mode);
5072 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5073 bool strip_mined_loops_expanded = bs->strip_mined_loops_expanded(_mode);
5074 if (stop_early && !do_expensive_nodes) {
5075 return;
5076 }
5077
5078 // Set loop nesting depth
5079 _ltree_root->set_nest( 0 );
5080
5081 // Split shared headers and insert loop landing pads.
5082 // Do not bother doing this on the Root loop of course.
5083 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5084 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5085 if( _ltree_root->_child->beautify_loops( this ) ) {
5086 // Re-build loop tree!
5087 _ltree_root->_child = nullptr;
5088 _loop_or_ctrl.clear();
5089 reallocate_preorders();
5090 build_loop_tree();
5091 // Check for bailout, and return
5092 if (C->failing()) {
5093 return;
5130
5131 // Walk the DATA nodes and place into loops. Find earliest control
5132 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5133 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5134 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5135
5136 // Allocate stack with enough space to avoid frequent realloc
5137 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5138 Node_Stack nstack(stack_size);
5139
5140 visited.clear();
5141 Node_List worklist;
5142 // Don't need C->root() on worklist since
5143 // it will be processed among C->top() inputs
5144 worklist.push(C->top());
5145 visited.set(C->top()->_idx); // Set C->top() as visited now
5146 build_loop_early( visited, worklist, nstack );
5147
5148 // Given early legal placement, try finding counted loops. This placement
5149 // is good enough to discover most loop invariants.
5150 if (!_verify_me && !_verify_only && !strip_mined_loops_expanded) {
5151 _ltree_root->counted_loop( this );
5152 }
5153
5154 // Find latest loop placement. Find ideal loop placement.
5155 visited.clear();
5156 init_dom_lca_tags();
5157 // Need C->root() on worklist when processing outs
5158 worklist.push(C->root());
5159 NOT_PRODUCT( C->verify_graph_edges(); )
5160 worklist.push(C->top());
5161 build_loop_late( visited, worklist, nstack );
5162 if (C->failing()) { return; }
5163
5164 if (_verify_only) {
5165 C->restore_major_progress(old_progress);
5166 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5167 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5168 return;
5169 }
5170
5215 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5216 IdealLoopTree* lpt = iter.current();
5217 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5218 lpt->compute_trip_count(this, T_INT);
5219 if (!lpt->do_one_iteration_loop(this) &&
5220 !lpt->do_remove_empty_loop(this)) {
5221 AutoNodeBudget node_budget(this);
5222 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5223 lpt->policy_maximally_unroll(this)) {
5224 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5225 do_maximally_unroll(lpt, worklist);
5226 }
5227 }
5228 }
5229 }
5230
5231 C->restore_major_progress(old_progress);
5232 return;
5233 }
5234
5235 if (bs->optimize_loops(this, _mode, visited, nstack, worklist)) {
5236 return;
5237 }
5238
5239 if (ReassociateInvariants && !C->major_progress()) {
5240 // Reassociate invariants and prep for split_thru_phi
5241 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5242 IdealLoopTree* lpt = iter.current();
5243 if (!lpt->is_loop()) {
5244 continue;
5245 }
5246 Node* head = lpt->_head;
5247 if (!lpt->is_innermost()) continue;
5248
5249 // check for vectorized loops, any reassociation of invariants was already done
5250 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5251 continue;
5252 } else {
5253 AutoNodeBudget node_budget(this);
5254 lpt->reassociate_invariants(this);
5255 }
5256 // Because RCE opportunities can be masked by split_thru_phi,
5257 // look for RCE candidates and inhibit split_thru_phi
5258 // on just their loop-phi's for this pass of loop opts
6905 }
6906 // Find least loop nesting depth
6907 legal = idom(legal); // Bump up the IDOM tree
6908 // Check for lower nesting depth
6909 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6910 least = legal;
6911 }
6912 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6913
6914 if (least != early) {
6915 // Move the node above predicates as far up as possible so a
6916 // following pass of Loop Predication doesn't hoist a predicate
6917 // that depends on it above that node.
6918 const PredicateIterator predicate_iterator(least);
6919 DominatedPredicates dominated_predicates(early, least, this);
6920 predicate_iterator.for_each(dominated_predicates);
6921 least = dominated_predicates.earliest_dominated_predicate_entry();
6922 }
6923 // Try not to place code on a loop entry projection
6924 // which can inhibit range check elimination.
6925 if (least != early && !BarrierSet::barrier_set()->barrier_set_c2()->is_gc_specific_loop_opts_pass(_mode)) {
6926 Node* ctrl_out = least->unique_ctrl_out_or_null();
6927 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6928 least == ctrl_out->in(LoopNode::EntryControl) &&
6929 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6930 Node* least_dom = idom(least);
6931 if (get_loop(least_dom)->is_member(get_loop(least))) {
6932 least = least_dom;
6933 }
6934 }
6935 }
6936 // Don't extend live ranges of raw oops
6937 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6938 !n->bottom_type()->isa_rawptr()) {
6939 least = early;
6940 }
6941
6942 #ifdef ASSERT
6943 // Broken part of VerifyLoopOptimizations (F)
6944 // Reason:
6945 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|
204 next = parent_ctl->in(0)->in(0)->in(0);
205 } else {
206 // Check if parent control has a single projection (this
207 // control is the only possible successor of the parent
208 // control). If so, we can try to move the node above the
209 // parent control.
210 int nb_ctl_proj = 0;
211 for (DUIterator_Fast imax, i = parent_ctl->fast_outs(imax); i < imax; i++) {
212 Node *p = parent_ctl->fast_out(i);
213 if (p->is_Proj() && p->is_CFG()) {
214 nb_ctl_proj++;
215 if (nb_ctl_proj > 1) {
216 break;
217 }
218 }
219 }
220
221 if (nb_ctl_proj > 1) {
222 break;
223 }
224 assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call(), "unexpected node");
225 assert(idom(ctl) == parent_ctl, "strange");
226 next = idom(parent_ctl);
227 }
228 } else {
229 next = idom(ctl);
230 }
231 if (next->is_Root() || next->is_Start() || dom_depth(next) < min_dom_depth) {
232 break;
233 }
234 ctl = next;
235 }
236
237 if (ctl != n->in(0)) {
238 _igvn.replace_input_of(n, 0, ctl);
239 _igvn.hash_insert(n);
240 }
241
242 return ctl;
243 }
244
5047 return;
5048 }
5049
5050 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
5051 // is an exception edge, parsing doesn't set has_loops().
5052 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
5053 // No loops after all
5054 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
5055
5056 // There should always be an outer loop containing the Root and Return nodes.
5057 // If not, we have a degenerate empty program. Bail out in this case.
5058 if (!has_node(C->root())) {
5059 if (!_verify_only) {
5060 C->clear_major_progress();
5061 assert(false, "empty program detected during loop optimization");
5062 C->record_method_not_compilable("empty program detected during loop optimization");
5063 }
5064 return;
5065 }
5066
5067 // Nothing to do, so get out
5068 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5069 !_verify_only;
5070 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5071 if (stop_early && !do_expensive_nodes) {
5072 return;
5073 }
5074
5075 // Set loop nesting depth
5076 _ltree_root->set_nest( 0 );
5077
5078 // Split shared headers and insert loop landing pads.
5079 // Do not bother doing this on the Root loop of course.
5080 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5081 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5082 if( _ltree_root->_child->beautify_loops( this ) ) {
5083 // Re-build loop tree!
5084 _ltree_root->_child = nullptr;
5085 _loop_or_ctrl.clear();
5086 reallocate_preorders();
5087 build_loop_tree();
5088 // Check for bailout, and return
5089 if (C->failing()) {
5090 return;
5127
5128 // Walk the DATA nodes and place into loops. Find earliest control
5129 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5130 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5131 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5132
5133 // Allocate stack with enough space to avoid frequent realloc
5134 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5135 Node_Stack nstack(stack_size);
5136
5137 visited.clear();
5138 Node_List worklist;
5139 // Don't need C->root() on worklist since
5140 // it will be processed among C->top() inputs
5141 worklist.push(C->top());
5142 visited.set(C->top()->_idx); // Set C->top() as visited now
5143 build_loop_early( visited, worklist, nstack );
5144
5145 // Given early legal placement, try finding counted loops. This placement
5146 // is good enough to discover most loop invariants.
5147 if (!_verify_me && !_verify_only) {
5148 _ltree_root->counted_loop( this );
5149 }
5150
5151 // Find latest loop placement. Find ideal loop placement.
5152 visited.clear();
5153 init_dom_lca_tags();
5154 // Need C->root() on worklist when processing outs
5155 worklist.push(C->root());
5156 NOT_PRODUCT( C->verify_graph_edges(); )
5157 worklist.push(C->top());
5158 build_loop_late( visited, worklist, nstack );
5159 if (C->failing()) { return; }
5160
5161 if (_verify_only) {
5162 C->restore_major_progress(old_progress);
5163 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5164 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5165 return;
5166 }
5167
5212 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5213 IdealLoopTree* lpt = iter.current();
5214 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5215 lpt->compute_trip_count(this, T_INT);
5216 if (!lpt->do_one_iteration_loop(this) &&
5217 !lpt->do_remove_empty_loop(this)) {
5218 AutoNodeBudget node_budget(this);
5219 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5220 lpt->policy_maximally_unroll(this)) {
5221 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5222 do_maximally_unroll(lpt, worklist);
5223 }
5224 }
5225 }
5226 }
5227
5228 C->restore_major_progress(old_progress);
5229 return;
5230 }
5231
5232 if (ReassociateInvariants && !C->major_progress()) {
5233 // Reassociate invariants and prep for split_thru_phi
5234 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5235 IdealLoopTree* lpt = iter.current();
5236 if (!lpt->is_loop()) {
5237 continue;
5238 }
5239 Node* head = lpt->_head;
5240 if (!lpt->is_innermost()) continue;
5241
5242 // check for vectorized loops, any reassociation of invariants was already done
5243 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5244 continue;
5245 } else {
5246 AutoNodeBudget node_budget(this);
5247 lpt->reassociate_invariants(this);
5248 }
5249 // Because RCE opportunities can be masked by split_thru_phi,
5250 // look for RCE candidates and inhibit split_thru_phi
5251 // on just their loop-phi's for this pass of loop opts
6898 }
6899 // Find least loop nesting depth
6900 legal = idom(legal); // Bump up the IDOM tree
6901 // Check for lower nesting depth
6902 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6903 least = legal;
6904 }
6905 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6906
6907 if (least != early) {
6908 // Move the node above predicates as far up as possible so a
6909 // following pass of Loop Predication doesn't hoist a predicate
6910 // that depends on it above that node.
6911 const PredicateIterator predicate_iterator(least);
6912 DominatedPredicates dominated_predicates(early, least, this);
6913 predicate_iterator.for_each(dominated_predicates);
6914 least = dominated_predicates.earliest_dominated_predicate_entry();
6915 }
6916 // Try not to place code on a loop entry projection
6917 // which can inhibit range check elimination.
6918 if (least != early) {
6919 Node* ctrl_out = least->unique_ctrl_out_or_null();
6920 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6921 least == ctrl_out->in(LoopNode::EntryControl) &&
6922 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6923 Node* least_dom = idom(least);
6924 if (get_loop(least_dom)->is_member(get_loop(least))) {
6925 least = least_dom;
6926 }
6927 }
6928 }
6929 // Don't extend live ranges of raw oops
6930 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6931 !n->bottom_type()->isa_rawptr()) {
6932 least = early;
6933 }
6934
6935 #ifdef ASSERT
6936 // Broken part of VerifyLoopOptimizations (F)
6937 // Reason:
6938 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|