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