5036 return;
5037 }
5038
5039 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
5040 // is an exception edge, parsing doesn't set has_loops().
5041 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
5042 // No loops after all
5043 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
5044
5045 // There should always be an outer loop containing the Root and Return nodes.
5046 // If not, we have a degenerate empty program. Bail out in this case.
5047 if (!has_node(C->root())) {
5048 if (!_verify_only) {
5049 C->clear_major_progress();
5050 assert(false, "empty program detected during loop optimization");
5051 C->record_method_not_compilable("empty program detected during loop optimization");
5052 }
5053 return;
5054 }
5055
5056 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
5057 // Nothing to do, so get out
5058 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5059 !_verify_only && !bs->is_gc_specific_loop_opts_pass(_mode);
5060 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5061 bool strip_mined_loops_expanded = bs->strip_mined_loops_expanded(_mode);
5062 if (stop_early && !do_expensive_nodes) {
5063 return;
5064 }
5065
5066 // Set loop nesting depth
5067 _ltree_root->set_nest( 0 );
5068
5069 // Split shared headers and insert loop landing pads.
5070 // Do not bother doing this on the Root loop of course.
5071 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5072 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5073 if( _ltree_root->_child->beautify_loops( this ) ) {
5074 // Re-build loop tree!
5075 _ltree_root->_child = nullptr;
5076 _loop_or_ctrl.clear();
5077 reallocate_preorders();
5078 build_loop_tree();
5079 // Check for bailout, and return
5080 if (C->failing()) {
5081 return;
5118
5119 // Walk the DATA nodes and place into loops. Find earliest control
5120 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5121 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5122 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5123
5124 // Allocate stack with enough space to avoid frequent realloc
5125 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5126 Node_Stack nstack(stack_size);
5127
5128 visited.clear();
5129 Node_List worklist;
5130 // Don't need C->root() on worklist since
5131 // it will be processed among C->top() inputs
5132 worklist.push(C->top());
5133 visited.set(C->top()->_idx); // Set C->top() as visited now
5134 build_loop_early( visited, worklist, nstack );
5135
5136 // Given early legal placement, try finding counted loops. This placement
5137 // is good enough to discover most loop invariants.
5138 if (!_verify_me && !_verify_only && !strip_mined_loops_expanded) {
5139 _ltree_root->counted_loop( this );
5140 }
5141
5142 // Find latest loop placement. Find ideal loop placement.
5143 visited.clear();
5144 init_dom_lca_tags();
5145 // Need C->root() on worklist when processing outs
5146 worklist.push(C->root());
5147 NOT_PRODUCT( C->verify_graph_edges(); )
5148 worklist.push(C->top());
5149 build_loop_late( visited, worklist, nstack );
5150 if (C->failing()) { return; }
5151
5152 if (_verify_only) {
5153 C->restore_major_progress(old_progress);
5154 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5155 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5156 return;
5157 }
5158
5203 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5204 IdealLoopTree* lpt = iter.current();
5205 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5206 lpt->compute_trip_count(this, T_INT);
5207 if (!lpt->do_one_iteration_loop(this) &&
5208 !lpt->do_remove_empty_loop(this)) {
5209 AutoNodeBudget node_budget(this);
5210 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5211 lpt->policy_maximally_unroll(this)) {
5212 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5213 do_maximally_unroll(lpt, worklist);
5214 }
5215 }
5216 }
5217 }
5218
5219 C->restore_major_progress(old_progress);
5220 return;
5221 }
5222
5223 if (bs->optimize_loops(this, _mode, visited, nstack, worklist)) {
5224 return;
5225 }
5226
5227 if (ReassociateInvariants && !C->major_progress()) {
5228 // Reassociate invariants and prep for split_thru_phi
5229 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5230 IdealLoopTree* lpt = iter.current();
5231 if (!lpt->is_loop()) {
5232 continue;
5233 }
5234 Node* head = lpt->_head;
5235 if (!lpt->is_innermost()) continue;
5236
5237 // check for vectorized loops, any reassociation of invariants was already done
5238 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5239 continue;
5240 } else {
5241 AutoNodeBudget node_budget(this);
5242 lpt->reassociate_invariants(this);
5243 }
5244 // Because RCE opportunities can be masked by split_thru_phi,
5245 // look for RCE candidates and inhibit split_thru_phi
5246 // on just their loop-phi's for this pass of loop opts
6893 }
6894 // Find least loop nesting depth
6895 legal = idom(legal); // Bump up the IDOM tree
6896 // Check for lower nesting depth
6897 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6898 least = legal;
6899 }
6900 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6901
6902 if (least != early) {
6903 // Move the node above predicates as far up as possible so a
6904 // following pass of Loop Predication doesn't hoist a predicate
6905 // that depends on it above that node.
6906 const PredicateIterator predicate_iterator(least);
6907 DominatedPredicates dominated_predicates(early, least, this);
6908 predicate_iterator.for_each(dominated_predicates);
6909 least = dominated_predicates.earliest_dominated_predicate_entry();
6910 }
6911 // Try not to place code on a loop entry projection
6912 // which can inhibit range check elimination.
6913 if (least != early && !BarrierSet::barrier_set()->barrier_set_c2()->is_gc_specific_loop_opts_pass(_mode)) {
6914 Node* ctrl_out = least->unique_ctrl_out_or_null();
6915 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6916 least == ctrl_out->in(LoopNode::EntryControl) &&
6917 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6918 Node* least_dom = idom(least);
6919 if (get_loop(least_dom)->is_member(get_loop(least))) {
6920 least = least_dom;
6921 }
6922 }
6923 }
6924 // Don't extend live ranges of raw oops
6925 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6926 !n->bottom_type()->isa_rawptr()) {
6927 least = early;
6928 }
6929
6930 #ifdef ASSERT
6931 // Broken part of VerifyLoopOptimizations (F)
6932 // Reason:
6933 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|
5036 return;
5037 }
5038
5039 // Verify that the has_loops() flag set at parse time is consistent with the just built loop tree. When the back edge
5040 // is an exception edge, parsing doesn't set has_loops().
5041 assert(_ltree_root->_child == nullptr || C->has_loops() || C->has_exception_backedge(), "parsing found no loops but there are some");
5042 // No loops after all
5043 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
5044
5045 // There should always be an outer loop containing the Root and Return nodes.
5046 // If not, we have a degenerate empty program. Bail out in this case.
5047 if (!has_node(C->root())) {
5048 if (!_verify_only) {
5049 C->clear_major_progress();
5050 assert(false, "empty program detected during loop optimization");
5051 C->record_method_not_compilable("empty program detected during loop optimization");
5052 }
5053 return;
5054 }
5055
5056 // Nothing to do, so get out
5057 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !do_max_unroll && !_verify_me &&
5058 !_verify_only;
5059 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
5060 if (stop_early && !do_expensive_nodes) {
5061 return;
5062 }
5063
5064 // Set loop nesting depth
5065 _ltree_root->set_nest( 0 );
5066
5067 // Split shared headers and insert loop landing pads.
5068 // Do not bother doing this on the Root loop of course.
5069 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
5070 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
5071 if( _ltree_root->_child->beautify_loops( this ) ) {
5072 // Re-build loop tree!
5073 _ltree_root->_child = nullptr;
5074 _loop_or_ctrl.clear();
5075 reallocate_preorders();
5076 build_loop_tree();
5077 // Check for bailout, and return
5078 if (C->failing()) {
5079 return;
5116
5117 // Walk the DATA nodes and place into loops. Find earliest control
5118 // node. For CFG nodes, the _loop_or_ctrl array starts out and remains
5119 // holding the associated IdealLoopTree pointer. For DATA nodes, the
5120 // _loop_or_ctrl array holds the earliest legal controlling CFG node.
5121
5122 // Allocate stack with enough space to avoid frequent realloc
5123 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
5124 Node_Stack nstack(stack_size);
5125
5126 visited.clear();
5127 Node_List worklist;
5128 // Don't need C->root() on worklist since
5129 // it will be processed among C->top() inputs
5130 worklist.push(C->top());
5131 visited.set(C->top()->_idx); // Set C->top() as visited now
5132 build_loop_early( visited, worklist, nstack );
5133
5134 // Given early legal placement, try finding counted loops. This placement
5135 // is good enough to discover most loop invariants.
5136 if (!_verify_me && !_verify_only) {
5137 _ltree_root->counted_loop( this );
5138 }
5139
5140 // Find latest loop placement. Find ideal loop placement.
5141 visited.clear();
5142 init_dom_lca_tags();
5143 // Need C->root() on worklist when processing outs
5144 worklist.push(C->root());
5145 NOT_PRODUCT( C->verify_graph_edges(); )
5146 worklist.push(C->top());
5147 build_loop_late( visited, worklist, nstack );
5148 if (C->failing()) { return; }
5149
5150 if (_verify_only) {
5151 C->restore_major_progress(old_progress);
5152 assert(C->unique() == unique, "verification _mode made Nodes? ? ?");
5153 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
5154 return;
5155 }
5156
5201 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5202 IdealLoopTree* lpt = iter.current();
5203 if (lpt->is_innermost() && lpt->_allow_optimizations && !lpt->_has_call && lpt->is_counted()) {
5204 lpt->compute_trip_count(this, T_INT);
5205 if (!lpt->do_one_iteration_loop(this) &&
5206 !lpt->do_remove_empty_loop(this)) {
5207 AutoNodeBudget node_budget(this);
5208 if (lpt->_head->as_CountedLoop()->is_normal_loop() &&
5209 lpt->policy_maximally_unroll(this)) {
5210 memset( worklist.adr(), 0, worklist.max()*sizeof(Node*) );
5211 do_maximally_unroll(lpt, worklist);
5212 }
5213 }
5214 }
5215 }
5216
5217 C->restore_major_progress(old_progress);
5218 return;
5219 }
5220
5221 if (ReassociateInvariants && !C->major_progress()) {
5222 // Reassociate invariants and prep for split_thru_phi
5223 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
5224 IdealLoopTree* lpt = iter.current();
5225 if (!lpt->is_loop()) {
5226 continue;
5227 }
5228 Node* head = lpt->_head;
5229 if (!lpt->is_innermost()) continue;
5230
5231 // check for vectorized loops, any reassociation of invariants was already done
5232 if (head->is_CountedLoop() && head->as_CountedLoop()->is_unroll_only()) {
5233 continue;
5234 } else {
5235 AutoNodeBudget node_budget(this);
5236 lpt->reassociate_invariants(this);
5237 }
5238 // Because RCE opportunities can be masked by split_thru_phi,
5239 // look for RCE candidates and inhibit split_thru_phi
5240 // on just their loop-phi's for this pass of loop opts
6887 }
6888 // Find least loop nesting depth
6889 legal = idom(legal); // Bump up the IDOM tree
6890 // Check for lower nesting depth
6891 if( get_loop(legal)->_nest < get_loop(least)->_nest )
6892 least = legal;
6893 }
6894 assert(early == legal || legal != C->root(), "bad dominance of inputs");
6895
6896 if (least != early) {
6897 // Move the node above predicates as far up as possible so a
6898 // following pass of Loop Predication doesn't hoist a predicate
6899 // that depends on it above that node.
6900 const PredicateIterator predicate_iterator(least);
6901 DominatedPredicates dominated_predicates(early, least, this);
6902 predicate_iterator.for_each(dominated_predicates);
6903 least = dominated_predicates.earliest_dominated_predicate_entry();
6904 }
6905 // Try not to place code on a loop entry projection
6906 // which can inhibit range check elimination.
6907 if (least != early) {
6908 Node* ctrl_out = least->unique_ctrl_out_or_null();
6909 if (ctrl_out != nullptr && ctrl_out->is_Loop() &&
6910 least == ctrl_out->in(LoopNode::EntryControl) &&
6911 (ctrl_out->is_CountedLoop() || ctrl_out->is_OuterStripMinedLoop())) {
6912 Node* least_dom = idom(least);
6913 if (get_loop(least_dom)->is_member(get_loop(least))) {
6914 least = least_dom;
6915 }
6916 }
6917 }
6918 // Don't extend live ranges of raw oops
6919 if (least != early && n->is_ConstraintCast() && n->in(1)->bottom_type()->isa_rawptr() &&
6920 !n->bottom_type()->isa_rawptr()) {
6921 least = early;
6922 }
6923
6924 #ifdef ASSERT
6925 // Broken part of VerifyLoopOptimizations (F)
6926 // Reason:
6927 // _verify_me->get_ctrl_no_update(n) seems to return wrong result
|