108 bool IdealLoopTree::policy_unswitching(PhaseIdealLoop* phase) const {
109 if (!LoopUnswitching) {
110 return false;
111 }
112 if (!_head->is_Loop()) {
113 return false;
114 }
115
116 // If nodes are depleted, some transform has miscalculated its needs.
117 assert(!phase->exceeding_node_budget(), "sanity");
118
119 // check for vectorized loops, any unswitching was already applied
120 if (_head->is_CountedLoop() && _head->as_CountedLoop()->is_unroll_only()) {
121 return false;
122 }
123
124 LoopNode* head = _head->as_Loop();
125 if (head->unswitch_count() + 1 > head->unswitch_max()) {
126 return false;
127 }
128 if (phase->find_unswitch_candidate(this) == nullptr) {
129 return false;
130 }
131
132 // Too speculative if running low on nodes.
133 return phase->may_require_nodes(est_loop_clone_sz(2));
134 }
135
136 // Find an invariant test in the loop body that does not exit the loop. If multiple tests are found, we pick the first
137 // one in the loop body. Return the "unswitch candidate" If to apply Loop Unswitching on.
138 IfNode* PhaseIdealLoop::find_unswitch_candidate(const IdealLoopTree* loop) const {
139 LoopNode* head = loop->_head->as_Loop();
140 IfNode* unswitch_candidate = nullptr;
141 Node* n = head->in(LoopNode::LoopBackControl);
142 while (n != head) {
143 Node* n_dom = idom(n);
144 if (n->is_Region()) {
145 if (n_dom->is_If()) {
146 IfNode* iff = n_dom->as_If();
147 if (iff->in(1)->is_Bool()) {
148 BoolNode* bol = iff->in(1)->as_Bool();
149 if (bol->in(1)->is_Cmp()) {
150 // If condition is invariant and not a loop exit,
151 // then found reason to unswitch.
152 if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
153 assert(iff->Opcode() == Op_If || iff->is_RangeCheck() || iff->is_BaseCountedLoopEnd(), "valid ifs");
154 unswitch_candidate = iff;
155 }
156 }
157 }
158 }
159 }
160 n = n_dom;
161 }
162 return unswitch_candidate;
163 }
164
165 // LoopSelector is used for loop multiversioning and unswitching. This class creates an If node (i.e. loop selector)
166 // that selects if the true-path-loop or the false-path-loop should be executed at runtime.
167 class LoopSelector : public StackObj {
168 // Cached fields for construction.
169 PhaseIdealLoop* const _phase;
170 IdealLoopTree* const _outer_loop;
171 Node* const _original_loop_entry;
172 const uint _dom_depth; // of original_loop_entry
173
174 // Constructed selector if with its projections.
175 IfNode* const _selector;
176 IfTrueNode* const _true_path_loop_proj;
177 IfFalseNode* const _false_path_loop_proj;
178
179 enum PathToLoop { TRUE_PATH, FALSE_PATH };
180
181 public:
182 // For multiversioning: create a new selector (multiversion_if) from a bol condition.
183 LoopSelector(IdealLoopTree* loop, Node* bol, float prob, float fcnt)
184 : _phase(loop->_phase),
185 _outer_loop(loop->skip_strip_mined()->_parent),
186 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
187 _dom_depth(_phase->dom_depth(_original_loop_entry)),
188 _selector(create_multiversioning_if(bol, prob, fcnt)), // multiversioning
189 _true_path_loop_proj(create_proj_to_loop(TRUE_PATH)->as_IfTrue()),
190 _false_path_loop_proj(create_proj_to_loop(FALSE_PATH)->as_IfFalse()) {
191 }
192
193 // For unswitching: create an unswitching if before the loop, from a pre-existing
194 // unswitching_candidate inside the loop.
195 LoopSelector(IdealLoopTree* loop, IfNode* unswitch_candidate)
196 : _phase(loop->_phase),
197 _outer_loop(loop->skip_strip_mined()->_parent),
198 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
199 _dom_depth(_phase->dom_depth(_original_loop_entry)),
200 _selector(create_unswitching_if(unswitch_candidate)), // unswitching
201 _true_path_loop_proj(create_proj_to_loop(TRUE_PATH)->as_IfTrue()),
202 _false_path_loop_proj(create_proj_to_loop(FALSE_PATH)->as_IfFalse()) {
203 }
204 NONCOPYABLE(LoopSelector);
205
206 IfNode* create_multiversioning_if(Node* bol, float prob, float fcnt) {
207 _phase->igvn().rehash_node_delayed(_original_loop_entry);
208 IfNode* selector_if = new IfNode(_original_loop_entry, bol, prob, fcnt);
209 _phase->register_node(selector_if, _outer_loop, _original_loop_entry, _dom_depth);
210 return selector_if;
211 }
212
213 IfNode* create_unswitching_if(IfNode* unswitch_candidate) {
214 _phase->igvn().rehash_node_delayed(_original_loop_entry);
215 BoolNode* unswitch_candidate_bool = unswitch_candidate->in(1)->as_Bool();
216 IfNode* selector_if = IfNode::make_with_same_profile(unswitch_candidate, _original_loop_entry,
217 unswitch_candidate_bool);
218 _phase->register_node(selector_if, _outer_loop, _original_loop_entry, _dom_depth);
219 return selector_if;
220 }
221
222 private:
223 IfProjNode* create_proj_to_loop(const PathToLoop path_to_loop) {
224 IfProjNode* proj_to_loop;
225 if (path_to_loop == TRUE_PATH) {
226 proj_to_loop = new IfTrueNode(_selector);
227 } else {
228 proj_to_loop = new IfFalseNode(_selector);
229 }
230 _phase->register_node(proj_to_loop, _outer_loop, _selector, _dom_depth);
231 return proj_to_loop;
232 }
233
234 public:
235 IfNode* selector() const {
236 return _selector;
237 }
238
239 IfTrueNode* true_path_loop_proj() const {
240 return _true_path_loop_proj;
241 }
242
243 IfFalseNode* false_path_loop_proj() const {
244 return _false_path_loop_proj;
245 }
246 };
247
248 // This class creates an If node (i.e. loop selector) that selects if the true-path-loop or the false-path-loop should be
249 // executed at runtime. This is done by finding an invariant and non-loop-exiting unswitch candidate If node (guaranteed
250 // to exist at this point) to perform Loop Unswitching on.
251 class UnswitchedLoopSelector : public StackObj {
252 IfNode* const _unswitch_candidate;
253 const LoopSelector _loop_selector;
254
255 public:
256 UnswitchedLoopSelector(IdealLoopTree* loop)
257 : _unswitch_candidate(find_unswitch_candidate(loop)),
258 _loop_selector(loop, _unswitch_candidate) {}
259 NONCOPYABLE(UnswitchedLoopSelector);
260
261 private:
262 static IfNode* find_unswitch_candidate(IdealLoopTree* loop) {
263 IfNode* unswitch_candidate = loop->_phase->find_unswitch_candidate(loop);
264 assert(unswitch_candidate != nullptr, "guaranteed to exist by policy_unswitching");
265 assert(loop->_phase->is_member(loop, unswitch_candidate), "must be inside original loop");
266 return unswitch_candidate;
267 }
268
269 public:
270 IfNode* unswitch_candidate() const {
271 return _unswitch_candidate;
272 }
273
274 const LoopSelector& loop_selector() const {
275 return _loop_selector;
276 }
277 };
278
279 // Class to unswitch the original loop and create Predicates at the new unswitched loop versions. The newly cloned loop
280 // becomes the false-path-loop while original loop becomes the true-path-loop.
281 class OriginalLoop : public StackObj {
282 LoopNode* const _loop_head;
283 LoopNode* const _outer_loop_head; // OuterStripMinedLoopNode if loop strip mined, else just the loop head.
284 IdealLoopTree* const _loop;
285 Node_List& _old_new;
286 PhaseIdealLoop* const _phase;
287
288 public:
289 OriginalLoop(IdealLoopTree* loop, Node_List& old_new)
290 : _loop_head(loop->_head->as_Loop()),
291 _outer_loop_head(loop->_head->as_Loop()->skip_strip_mined()),
292 _loop(loop),
293 _old_new(old_new),
294 _phase(loop->_phase) {}
295 NONCOPYABLE(OriginalLoop);
296
297 // Unswitch the original loop on the invariant loop selector by creating a true-path-loop and a false-path-loop.
298 // Remove the unswitch candidate If from both unswitched loop versions which are now covered by the loop selector If.
299 void unswitch(const UnswitchedLoopSelector& unswitched_loop_selector) {
300 multiversion(unswitched_loop_selector.loop_selector());
301 remove_unswitch_candidate_from_loops(unswitched_loop_selector);
302 }
303
304 // Multiversion the original loop. The loop selector if selects between the original loop (true-path-loop), and
305 // a copy of it (false-path-loop).
306 void multiversion(const LoopSelector& loop_selector) {
307 const uint first_false_path_loop_node_index = _phase->C->unique();
308 clone_loop(loop_selector);
309
310 move_parse_and_template_assertion_predicates_to_unswitched_loops(loop_selector,
311 first_false_path_loop_node_index);
312 DEBUG_ONLY(verify_loop_versions(_loop->_head->as_Loop(), loop_selector);)
313
314 _phase->recompute_dom_depth();
315 }
316
317 private:
318 void clone_loop(const LoopSelector& loop_selector) {
319 _phase->clone_loop(_loop, _old_new, _phase->dom_depth(_outer_loop_head),
320 PhaseIdealLoop::CloneIncludesStripMined, loop_selector.selector());
321 fix_loop_entries(loop_selector);
346 #ifdef ASSERT
347 void verify_loop_versions(LoopNode* true_path_loop_head,
348 const LoopSelector& loop_selector) const {
349 verify_loop_version(true_path_loop_head,
350 loop_selector.true_path_loop_proj());
351 verify_loop_version(old_to_new(true_path_loop_head)->as_Loop(),
352 loop_selector.false_path_loop_proj());
353 }
354
355 static void verify_loop_version(LoopNode* loop_head, IfProjNode* loop_selector_if_proj) {
356 Node* entry = loop_head->skip_strip_mined()->in(LoopNode::EntryControl);
357 const Predicates predicates(entry);
358 // When skipping all predicates, we should end up at 'loop_selector_if_proj'.
359 assert(loop_selector_if_proj == predicates.entry(), "should end up at loop selector If");
360 }
361 #endif // ASSERT
362
363 Node* old_to_new(const Node* old) const {
364 return _old_new[old->_idx];
365 }
366
367 // Remove the unswitch candidate If nodes in both unswitched loop versions which are now dominated by the loop selector
368 // If node. Keep the true-path-path in the true-path-loop and the false-path-path in the false-path-loop by setting
369 // the bool input accordingly. The unswitch candidate If nodes are folded in the next IGVN round.
370 void remove_unswitch_candidate_from_loops(const UnswitchedLoopSelector& unswitched_loop_selector) {
371 const LoopSelector& loop_selector = unswitched_loop_selector.loop_selector();;
372 IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
373 _phase->igvn().rehash_node_delayed(unswitch_candidate);
374 _phase->dominated_by(loop_selector.true_path_loop_proj(), unswitch_candidate);
375
376 IfNode* unswitch_candidate_clone = _old_new[unswitch_candidate->_idx]->as_If();
377 _phase->igvn().rehash_node_delayed(unswitch_candidate_clone);
378 _phase->dominated_by(loop_selector.false_path_loop_proj(), unswitch_candidate_clone);
379 }
380 };
381
382 // See comments below file header for more information about Loop Unswitching.
383 void PhaseIdealLoop::do_unswitching(IdealLoopTree* loop, Node_List& old_new) {
384 assert(LoopUnswitching, "LoopUnswitching must be enabled");
385
386 LoopNode* original_head = loop->_head->as_Loop();
387 if (has_control_dependencies_from_predicates(original_head)) {
388 NOT_PRODUCT(trace_loop_unswitching_impossible(original_head);)
389 return;
390 }
391
392 NOT_PRODUCT(trace_loop_unswitching_count(loop, original_head);)
393 C->print_method(PHASE_BEFORE_LOOP_UNSWITCHING, 4, original_head);
394
395 revert_to_normal_loop(original_head);
396
397 const UnswitchedLoopSelector unswitched_loop_selector(loop);
398 OriginalLoop original_loop(loop, old_new);
399 original_loop.unswitch(unswitched_loop_selector);
400
401 hoist_invariant_check_casts(loop, old_new, unswitched_loop_selector);
402 add_unswitched_loop_version_bodies_to_igvn(loop, old_new);
403
404 LoopNode* new_head = old_new[original_head->_idx]->as_Loop();
405 increment_unswitch_counts(original_head, new_head);
406
407 NOT_PRODUCT(trace_loop_unswitching_result(unswitched_loop_selector, original_head, new_head);)
408 C->print_method(PHASE_AFTER_LOOP_UNSWITCHING, 4, new_head);
409 C->set_major_progress();
410 }
411
412 void PhaseIdealLoop::do_multiversioning(IdealLoopTree* lpt, Node_List& old_new) {
413 #ifndef PRODUCT
414 if (TraceLoopOpts || TraceLoopMultiversioning) {
415 tty->print("Multiversion ");
416 lpt->dump_head();
417 }
418 #endif
419 assert(LoopMultiversioning, "LoopMultiversioning must be enabled");
420
421 CountedLoopNode* original_head = lpt->_head->as_CountedLoop();
422 C->print_method(PHASE_BEFORE_LOOP_MULTIVERSIONING, 4, original_head);
423
424 Node* one = _igvn.intcon(1);
425 set_ctrl(one, C->root());
426 Node* opaque = new OpaqueMultiversioningNode(C, one);
427 set_ctrl(opaque, C->root());
594 }
595 return false;
596 }
597
598 #ifndef PRODUCT
599 void PhaseIdealLoop::trace_loop_unswitching_impossible(const LoopNode* original_head) {
600 if (TraceLoopUnswitching) {
601 tty->print_cr("Loop Unswitching \"%d %s\" not possible due to control dependencies",
602 original_head->_idx, original_head->Name());
603 }
604 }
605
606 void PhaseIdealLoop::trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head) {
607 if (TraceLoopOpts) {
608 tty->print("Unswitch %d ", original_head->unswitch_count() + 1);
609 loop->dump_head();
610 }
611 }
612
613 void PhaseIdealLoop::trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
614 const LoopNode* original_head, const LoopNode* new_head) {
615 if (TraceLoopUnswitching) {
616 IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
617 IfNode* loop_selector = unswitched_loop_selector.loop_selector().selector();
618 tty->print_cr("Loop Unswitching:");
619 tty->print_cr("- Unswitch-Candidate-If: %d %s", unswitch_candidate->_idx, unswitch_candidate->Name());
620 tty->print_cr("- Loop-Selector-If: %d %s", loop_selector->_idx, loop_selector->Name());
621 tty->print_cr("- True-Path-Loop (=Orig): %d %s", original_head->_idx, original_head->Name());
622 tty->print_cr("- False-Path-Loop (=Clone): %d %s", new_head->_idx, new_head->Name());
623 }
624 }
625
626 void PhaseIdealLoop::trace_loop_multiversioning_result(const LoopSelector& loop_selector,
627 const LoopNode* original_head, const LoopNode* new_head) {
628 if (TraceLoopMultiversioning) {
629 IfNode* selector_if = loop_selector.selector();
630 tty->print_cr("Loop Multiversioning:");
631 tty->print_cr("- Loop-Selector-If: %d %s", selector_if->_idx, selector_if->Name());
632 tty->print_cr("- True-Path-Loop (=Orig / Fast): %d %s", original_head->_idx, original_head->Name());
633 tty->print_cr("- False-Path-Loop (=Clone / Slow): %d %s", new_head->_idx, new_head->Name());
634 }
635 }
636 #endif
637
638 // When unswitching a counted loop, we need to convert it back to a normal loop since it's not a proper pre, main or,
639 // post loop anymore after loop unswitching. We also lose the multiversion structure, with access to the multiversion_if.
640 void PhaseIdealLoop::revert_to_normal_loop(const LoopNode* loop_head) {
641 CountedLoopNode* cl = loop_head->isa_CountedLoop();
642 if (cl == nullptr) { return; }
643 if (!cl->is_normal_loop()) { cl->set_normal_loop(); }
644 if (cl->is_multiversion()) { cl->set_no_multiversion(); }
645 }
646
647 // Hoist invariant CheckCastPPNodes out of each unswitched loop version to the appropriate loop selector If projection.
648 void PhaseIdealLoop::hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
649 const UnswitchedLoopSelector& unswitched_loop_selector) {
650 IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
651 IfNode* loop_selector = unswitched_loop_selector.loop_selector().selector();
652 ResourceMark rm;
653 GrowableArray<CheckCastPPNode*> loop_invariant_check_casts;
654 for (DUIterator_Fast imax, i = unswitch_candidate->fast_outs(imax); i < imax; i++) {
655 IfProjNode* proj = unswitch_candidate->fast_out(i)->as_IfProj();
656 // Copy to a worklist for easier manipulation
657 for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
658 CheckCastPPNode* check_cast = proj->fast_out(j)->isa_CheckCastPP();
659 if (check_cast != nullptr && loop->is_invariant(check_cast->in(1))) {
660 loop_invariant_check_casts.push(check_cast);
661 }
662 }
663 IfProjNode* loop_selector_if_proj = loop_selector->proj_out(proj->_con)->as_IfProj();
664 while (loop_invariant_check_casts.length() > 0) {
665 CheckCastPPNode* cast = loop_invariant_check_casts.pop();
666 Node* cast_clone = cast->clone();
667 cast_clone->set_req(0, loop_selector_if_proj);
668 _igvn.replace_input_of(cast, 1, cast_clone);
669 register_new_node(cast_clone, loop_selector_if_proj);
670 // Same for the clone
671 Node* use_clone = old_new[cast->_idx];
672 _igvn.replace_input_of(use_clone, 1, cast_clone);
673 }
674 }
675 }
676
677 // Enable more optimizations possibilities in the next IGVN round.
678 void PhaseIdealLoop::add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new) {
679 loop->record_for_igvn();
680 for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
681 Node* n = loop->_body[i];
682 Node* n_clone = old_new[n->_idx];
683 _igvn._worklist.push(n_clone);
684 }
685 }
686
687 void PhaseIdealLoop::increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head) {
688 const int unswitch_count = original_head->unswitch_count() + 1;
689 original_head->set_unswitch_count(unswitch_count);
690 new_head->set_unswitch_count(unswitch_count);
691 }
692
|
108 bool IdealLoopTree::policy_unswitching(PhaseIdealLoop* phase) const {
109 if (!LoopUnswitching) {
110 return false;
111 }
112 if (!_head->is_Loop()) {
113 return false;
114 }
115
116 // If nodes are depleted, some transform has miscalculated its needs.
117 assert(!phase->exceeding_node_budget(), "sanity");
118
119 // check for vectorized loops, any unswitching was already applied
120 if (_head->is_CountedLoop() && _head->as_CountedLoop()->is_unroll_only()) {
121 return false;
122 }
123
124 LoopNode* head = _head->as_Loop();
125 if (head->unswitch_count() + 1 > head->unswitch_max()) {
126 return false;
127 }
128
129 if (head->is_flat_arrays()) {
130 return false;
131 }
132
133 if (no_unswitch_candidate()) {
134 return false;
135 }
136
137 // Too speculative if running low on nodes.
138 return phase->may_require_nodes(est_loop_clone_sz(2));
139 }
140
141 // Check the absence of any If node that can be used for Loop Unswitching. In that case, no Loop Unswitching can be done.
142 bool IdealLoopTree::no_unswitch_candidate() const {
143 ResourceMark rm;
144 Node_List dont_care;
145 return _phase->find_unswitch_candidates(this, dont_care) == nullptr;
146 }
147
148 // Find an invariant test in the loop body that does not exit the loop. If multiple tests are found, we pick the first
149 // one in the loop body as "unswitch candidate" to apply Loop Unswitching on.
150 // Depending on whether we find such a candidate and if we do, whether it's a flat array check, we do the following:
151 // (1) Candidate is not a flat array check:
152 // Return the unique unswitch candidate.
153 // (2) Candidate is a flat array check:
154 // Collect all remaining non-loop-exiting flat array checks in the loop body in the provided 'flat_array_checks'
155 // list in order to create an unswitched loop version without any flat array checks and a version with checks
156 // (i.e. same as original loop). Return the initially found candidate which could be unique if no further flat array
157 // checks are found.
158 // (3) No candidate is initially found:
159 // As in (2), we collect all non-loop-exiting flat array checks in the loop body in the provided 'flat_array_checks'
160 // list. Pick the first collected flat array check as unswitch candidate, which could be unique, and return it (a).
161 // If there are no flat array checks, we cannot apply Loop Unswitching (b).
162 //
163 // Note that for both (2) and (3a), if there are multiple flat array checks, then the candidate's FlatArrayCheckNode is
164 // later updated in Loop Unswitching to perform a flat array check on all collected flat array checks.
165 IfNode* PhaseIdealLoop::find_unswitch_candidates(const IdealLoopTree* loop, Node_List& flat_array_checks) const {
166 IfNode* unswitch_candidate = find_unswitch_candidate_from_idoms(loop);
167 if (unswitch_candidate != nullptr && !unswitch_candidate->is_flat_array_check(&_igvn)) {
168 // Case (1)
169 return unswitch_candidate;
170 }
171
172 collect_flat_array_checks(loop, flat_array_checks);
173 if (unswitch_candidate != nullptr) {
174 // Case (2)
175 assert(unswitch_candidate->is_flat_array_check(&_igvn), "is a flat array check");
176 return unswitch_candidate;
177 } else if (flat_array_checks.size() > 0) {
178 // Case (3a): Pick first one found as candidate (there could be multiple).
179 return flat_array_checks[0]->as_If();
180 }
181
182 // Case (3b): No suitable unswitch candidate found.
183 return nullptr;
184 }
185
186 // Find an unswitch candidate by following the idom chain from the loop back edge.
187 IfNode* PhaseIdealLoop::find_unswitch_candidate_from_idoms(const IdealLoopTree* loop) const {
188 LoopNode* head = loop->_head->as_Loop();
189 IfNode* unswitch_candidate = nullptr;
190 Node* n = head->in(LoopNode::LoopBackControl);
191 while (n != head) {
192 Node* n_dom = idom(n);
193 if (n->is_Region()) {
194 if (n_dom->is_If()) {
195 IfNode* iff = n_dom->as_If();
196 if (iff->in(1)->is_Bool()) {
197 BoolNode* bol = iff->in(1)->as_Bool();
198 if (bol->in(1)->is_Cmp()) {
199 // If condition is invariant and not a loop exit,
200 // then found reason to unswitch.
201 if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
202 assert(iff->Opcode() == Op_If || iff->is_RangeCheck() || iff->is_BaseCountedLoopEnd(), "valid ifs");
203 unswitch_candidate = iff;
204 }
205 }
206 }
207 }
208 }
209 n = n_dom;
210 }
211 return unswitch_candidate;
212 }
213
214 // Collect all flat array checks in the provided 'flat_array_checks' list.
215 void PhaseIdealLoop::collect_flat_array_checks(const IdealLoopTree* loop, Node_List& flat_array_checks) const {
216 assert(flat_array_checks.size() == 0, "should be empty initially");
217 for (uint i = 0; i < loop->_body.size(); i++) {
218 Node* next = loop->_body.at(i);
219 if (next->is_If() && next->as_If()->is_flat_array_check(&_igvn) && loop->is_invariant(next->in(1)) &&
220 !loop->is_loop_exit(next)) {
221 flat_array_checks.push(next);
222 }
223 }
224 }
225
226 // This class represents an "unswitch candidate" which is an If that can be used to perform Loop Unswitching on. If the
227 // candidate is a flat array check candidate, then we also collect all remaining non-loop-exiting flat array checks.
228 // These are candidates as well. We want to get rid of all these flat array checks in the true-path-loop for the
229 // following reason:
230 //
231 // FlatArrayCheckNodes are used with array accesses to switch between a flat and a non-flat array access. We want
232 // the performance impact on non-flat array accesses to be as small as possible. We therefore create the following
233 // loops in Loop Unswitching:
234 // - True-path-loop: We remove all non-loop-exiting flat array checks to get a loop with only non-flat array accesses
235 // (i.e. a fast path loop).
236 // - False-path-loop: We keep all flat array checks in this loop (i.e. a slow path loop).
237 class UnswitchCandidate : public StackObj {
238 PhaseIdealLoop* const _phase;
239 const Node_List& _old_new;
240 Node* const _original_loop_entry;
241 // If _candidate is a flat array check, this list contains all non-loop-exiting flat array checks in the loop body.
242 Node_List _flat_array_check_candidates;
243 IfNode* const _candidate;
244
245 public:
246 UnswitchCandidate(IdealLoopTree* loop, const Node_List& old_new)
247 : _phase(loop->_phase),
248 _old_new(old_new),
249 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
250 _flat_array_check_candidates(),
251 _candidate(find_unswitch_candidate(loop)) {}
252 NONCOPYABLE(UnswitchCandidate);
253
254 IfNode* find_unswitch_candidate(IdealLoopTree* loop) {
255 IfNode* unswitch_candidate = _phase->find_unswitch_candidates(loop, _flat_array_check_candidates);
256 assert(unswitch_candidate != nullptr, "guaranteed to exist by policy_unswitching");
257 assert(_phase->is_member(loop, unswitch_candidate), "must be inside original loop");
258 return unswitch_candidate;
259 }
260
261 IfNode* candidate() const {
262 return _candidate;
263 }
264
265 // Is the candidate a flat array check and are there other flat array checks as well?
266 bool has_multiple_flat_array_check_candidates() const {
267 return _flat_array_check_candidates.size() > 1;
268 }
269
270 // Remove all candidates from the true-path-loop which are now dominated by the loop selector
271 // (i.e. 'true_path_loop_proj'). The removed candidates are folded in the next IGVN round.
272 void update_in_true_path_loop(IfTrueNode* true_path_loop_proj) const {
273 remove_from_loop(true_path_loop_proj, _candidate);
274 if (has_multiple_flat_array_check_candidates()) {
275 remove_flat_array_checks(true_path_loop_proj);
276 }
277 }
278
279 // Remove a unique candidate from the false-path-loop which is now dominated by the loop selector
280 // (i.e. 'false_path_loop_proj'). The removed candidate is folded in the next IGVN round. If there are multiple
281 // candidates (i.e. flat array checks), then we leave them in the false-path-loop and only mark the loop such that it
282 // is not unswitched anymore in later loop opts rounds.
283 void update_in_false_path_loop(IfFalseNode* false_path_loop_proj, LoopNode* false_path_loop) const {
284 if (has_multiple_flat_array_check_candidates()) {
285 // Leave the flat array checks in the false-path-loop and prevent it from being unswitched again based on these
286 // checks.
287 false_path_loop->mark_flat_arrays();
288 } else {
289 remove_from_loop(false_path_loop_proj, _old_new[_candidate->_idx]->as_If());
290 }
291 }
292
293 private:
294 void remove_from_loop(IfProjNode* dominating_proj, IfNode* candidate) const {
295 _phase->igvn().rehash_node_delayed(candidate);
296 _phase->dominated_by(dominating_proj, candidate);
297 }
298
299 void remove_flat_array_checks(IfProjNode* dominating_proj) const {
300 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
301 IfNode* flat_array_check = _flat_array_check_candidates.at(i)->as_If();
302 _phase->igvn().rehash_node_delayed(flat_array_check);
303 _phase->dominated_by(dominating_proj, flat_array_check);
304 }
305 }
306
307 public:
308 // Merge all flat array checks into a single new BoolNode and return it.
309 BoolNode* merge_flat_array_checks() const {
310 assert(has_multiple_flat_array_check_candidates(), "must have multiple flat array checks to merge");
311 assert(_candidate->in(1)->as_Bool()->_test._test == BoolTest::ne, "IfTrue proj must point to flat array");
312 BoolNode* merged_flat_array_check_bool = create_bool_node();
313 create_flat_array_check_node(merged_flat_array_check_bool);
314 return merged_flat_array_check_bool;
315 }
316
317 private:
318 BoolNode* create_bool_node() const {
319 BoolNode* merged_flat_array_check_bool = _candidate->in(1)->clone()->as_Bool();
320 _phase->register_new_node(merged_flat_array_check_bool, _original_loop_entry);
321 return merged_flat_array_check_bool;
322 }
323
324 void create_flat_array_check_node(BoolNode* merged_flat_array_check_bool) const {
325 FlatArrayCheckNode* cloned_flat_array_check = merged_flat_array_check_bool->in(1)->clone()->as_FlatArrayCheck();
326 _phase->register_new_node(cloned_flat_array_check, _original_loop_entry);
327 merged_flat_array_check_bool->set_req(1, cloned_flat_array_check);
328 set_flat_array_check_inputs(cloned_flat_array_check);
329 }
330
331 // Combine all checks into a single one that fails if one array is flat.
332 void set_flat_array_check_inputs(FlatArrayCheckNode* cloned_flat_array_check) const {
333 uint total = FlatArrayCheckNode::ArrayOrKlass;
334 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
335 Node* flat_array_check = _flat_array_check_candidates.at(i)->in(1)->in(1);
336 total += flat_array_check->req() - FlatArrayCheckNode::ArrayOrKlass;
337 }
338 cloned_flat_array_check->add_req_batch(_phase->C->top(), total - cloned_flat_array_check->req());
339 uint k = FlatArrayCheckNode::ArrayOrKlass;
340 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
341 Node* flat_array_check = _flat_array_check_candidates.at(i)->in(1)->in(1);
342 for (uint j = FlatArrayCheckNode::ArrayOrKlass; j < flat_array_check->req(); j++) {
343 cloned_flat_array_check->set_req(k, flat_array_check->in(j));
344 k++;
345 }
346 }
347 assert(k == total, "missed some checks?");
348 }
349
350 public:
351 #ifndef PRODUCT
352 void trace_flat_array_checks() const {
353 if (has_multiple_flat_array_check_candidates()) {
354 tty->print_cr("- Unswitched and Merged Flat Array Checks:");
355 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
356 Node* unswitch_iff = _flat_array_check_candidates.at(i);
357 Node* cloned_unswitch_iff = _old_new[unswitch_iff->_idx];
358 assert(cloned_unswitch_iff != nullptr, "must exist");
359 tty->print_cr(" - %d %s -> %d %s", unswitch_iff->_idx, unswitch_iff->Name(),
360 cloned_unswitch_iff->_idx, cloned_unswitch_iff->Name());
361 }
362 }
363 }
364 #endif // NOT PRODUCT
365 };
366
367 // LoopSelector is used for loop multiversioning and unswitching. This class creates an If node (i.e. loop selector)
368 // that selects if the true-path-loop or the false-path-loop should be executed at runtime.
369 class LoopSelector : public StackObj {
370 // Cached fields for construction.
371 PhaseIdealLoop* const _phase;
372 IdealLoopTree* const _outer_loop;
373 Node* const _original_loop_entry;
374 const uint _dom_depth; // of original_loop_entry
375
376 // Constructed selector if with its projections.
377 IfNode* const _selector;
378 IfTrueNode* const _true_path_loop_proj;
379 IfFalseNode* const _false_path_loop_proj;
380
381 enum PathToLoop {
382 TRUE_PATH, FALSE_PATH
383 };
384
385 public:
386 // For multiversioning: create a new selector (multiversion_if) from a bol condition.
387 LoopSelector(IdealLoopTree* loop, Node* bol, float prob, float fcnt)
388 : _phase(loop->_phase),
389 _outer_loop(loop->skip_strip_mined()->_parent),
390 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
391 _dom_depth(_phase->dom_depth(_original_loop_entry)),
392 _selector(create_multiversioning_if(bol, prob, fcnt)), // multiversioning
393 _true_path_loop_proj(create_proj_to_loop(TRUE_PATH)->as_IfTrue()),
394 _false_path_loop_proj(create_proj_to_loop(FALSE_PATH)->as_IfFalse()) {
395 }
396
397 // For unswitching: create an unswitching if before the loop, from a pre-existing
398 // unswitching_candidate inside the loop.
399 LoopSelector(IdealLoopTree* loop, const UnswitchCandidate& unswitch_candidate)
400 : _phase(loop->_phase),
401 _outer_loop(loop->skip_strip_mined()->_parent),
402 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
403 _dom_depth(_phase->dom_depth(_original_loop_entry)),
404 _selector(create_unswitching_if(unswitch_candidate)), // unswitching
405 _true_path_loop_proj(create_proj_to_loop(TRUE_PATH)->as_IfTrue()),
406 _false_path_loop_proj(create_proj_to_loop(FALSE_PATH)->as_IfFalse()) {
407 }
408 NONCOPYABLE(LoopSelector);
409
410 private:
411 IfNode* create_multiversioning_if(Node* bol, float prob, float fcnt) {
412 _phase->igvn().rehash_node_delayed(_original_loop_entry);
413 IfNode* selector_if = new IfNode(_original_loop_entry, bol, prob, fcnt);
414 _phase->register_node(selector_if, _outer_loop, _original_loop_entry, _dom_depth);
415 return selector_if;
416 }
417
418 IfNode* create_unswitching_if(const UnswitchCandidate& unswitch_candidate) {
419 const uint dom_depth = _phase->dom_depth(_original_loop_entry);
420 _phase->igvn().rehash_node_delayed(_original_loop_entry);
421 IfNode* unswitch_candidate_if = unswitch_candidate.candidate();
422 BoolNode* selector_bool;
423 if (unswitch_candidate.has_multiple_flat_array_check_candidates()) {
424 selector_bool = unswitch_candidate.merge_flat_array_checks();
425 } else {
426 selector_bool = unswitch_candidate_if->in(1)->as_Bool();
427 }
428 IfNode* selector_if = IfNode::make_with_same_profile(unswitch_candidate_if, _original_loop_entry, selector_bool);
429 _phase->register_node(selector_if, _outer_loop, _original_loop_entry, dom_depth);
430 return selector_if;
431 }
432
433 IfProjNode* create_proj_to_loop(const PathToLoop path_to_loop) {
434 IfProjNode* proj_to_loop;
435 if (path_to_loop == TRUE_PATH) {
436 proj_to_loop = new IfTrueNode(_selector);
437 } else {
438 proj_to_loop = new IfFalseNode(_selector);
439 }
440 _phase->register_node(proj_to_loop, _outer_loop, _selector, _dom_depth);
441 return proj_to_loop;
442 }
443
444 public:
445 IfNode* selector() const {
446 return _selector;
447 }
448
449 IfTrueNode* true_path_loop_proj() const {
450 return _true_path_loop_proj;
451 }
452
453 IfFalseNode* false_path_loop_proj() const {
454 return _false_path_loop_proj;
455 }
456 };
457
458 // This class creates an If node (i.e. loop selector) that selects if the true-path-loop or the false-path-loop should be
459 // executed at runtime. This is done by finding an invariant and non-loop-exiting unswitch candidate If node (guaranteed
460 // to exist at this point) to perform Loop Unswitching on.
461 class UnswitchedLoopSelector : public StackObj {
462 const UnswitchCandidate& _unswitch_candidate;
463 const LoopSelector _loop_selector;
464
465 public:
466 UnswitchedLoopSelector(IdealLoopTree* loop, const UnswitchCandidate& unswitch_candidate)
467 : _unswitch_candidate(unswitch_candidate),
468 _loop_selector(loop, _unswitch_candidate) {}
469 NONCOPYABLE(UnswitchedLoopSelector);
470
471 IfNode* selector_if() const {
472 return _loop_selector.selector();
473 }
474
475 const LoopSelector& loop_selector() const {
476 return _loop_selector;
477 }
478 };
479
480 // Class to unswitch the original loop and create Predicates at the new unswitched loop versions. The newly cloned loop
481 // becomes the false-path-loop while original loop becomes the true-path-loop.
482 class OriginalLoop : public StackObj {
483 LoopNode* const _loop_head;
484 LoopNode* const _outer_loop_head; // OuterStripMinedLoopNode if loop strip mined, else just the loop head.
485 IdealLoopTree* const _loop;
486 Node_List& _old_new;
487 PhaseIdealLoop* const _phase;
488
489 public:
490 OriginalLoop(IdealLoopTree* loop, Node_List& old_new)
491 : _loop_head(loop->_head->as_Loop()),
492 _outer_loop_head(loop->_head->as_Loop()->skip_strip_mined()),
493 _loop(loop),
494 _old_new(old_new),
495 _phase(loop->_phase) {}
496 NONCOPYABLE(OriginalLoop);
497
498 // Unswitch the original loop on the invariant loop selector by creating a true-path-loop and a false-path-loop.
499 // Remove the unswitch candidate If from both unswitched loop versions which are now covered by the loop selector If.
500 void unswitch(const UnswitchedLoopSelector& unswitched_loop_selector) {
501 multiversion(unswitched_loop_selector.loop_selector());
502 }
503
504 // Multiversion the original loop. The loop selector if selects between the original loop (true-path-loop), and
505 // a copy of it (false-path-loop).
506 void multiversion(const LoopSelector& loop_selector) {
507 const uint first_false_path_loop_node_index = _phase->C->unique();
508 clone_loop(loop_selector);
509
510 move_parse_and_template_assertion_predicates_to_unswitched_loops(loop_selector,
511 first_false_path_loop_node_index);
512 DEBUG_ONLY(verify_loop_versions(_loop->_head->as_Loop(), loop_selector);)
513
514 _phase->recompute_dom_depth();
515 }
516
517 private:
518 void clone_loop(const LoopSelector& loop_selector) {
519 _phase->clone_loop(_loop, _old_new, _phase->dom_depth(_outer_loop_head),
520 PhaseIdealLoop::CloneIncludesStripMined, loop_selector.selector());
521 fix_loop_entries(loop_selector);
546 #ifdef ASSERT
547 void verify_loop_versions(LoopNode* true_path_loop_head,
548 const LoopSelector& loop_selector) const {
549 verify_loop_version(true_path_loop_head,
550 loop_selector.true_path_loop_proj());
551 verify_loop_version(old_to_new(true_path_loop_head)->as_Loop(),
552 loop_selector.false_path_loop_proj());
553 }
554
555 static void verify_loop_version(LoopNode* loop_head, IfProjNode* loop_selector_if_proj) {
556 Node* entry = loop_head->skip_strip_mined()->in(LoopNode::EntryControl);
557 const Predicates predicates(entry);
558 // When skipping all predicates, we should end up at 'loop_selector_if_proj'.
559 assert(loop_selector_if_proj == predicates.entry(), "should end up at loop selector If");
560 }
561 #endif // ASSERT
562
563 Node* old_to_new(const Node* old) const {
564 return _old_new[old->_idx];
565 }
566 };
567
568 // See comments below file header for more information about Loop Unswitching.
569 void PhaseIdealLoop::do_unswitching(IdealLoopTree* loop, Node_List& old_new) {
570 assert(LoopUnswitching, "LoopUnswitching must be enabled");
571
572 LoopNode* original_head = loop->_head->as_Loop();
573 if (has_control_dependencies_from_predicates(original_head)) {
574 NOT_PRODUCT(trace_loop_unswitching_impossible(original_head);)
575 return;
576 }
577
578 NOT_PRODUCT(trace_loop_unswitching_count(loop, original_head);)
579 C->print_method(PHASE_BEFORE_LOOP_UNSWITCHING, 4, original_head);
580
581 revert_to_normal_loop(original_head);
582
583 const UnswitchCandidate unswitch_candidate(loop, old_new);
584 const UnswitchedLoopSelector unswitched_loop_selector(loop, unswitch_candidate);
585 OriginalLoop original_loop(loop, old_new);
586 original_loop.unswitch(unswitched_loop_selector);
587
588 unswitch_candidate.update_in_true_path_loop(unswitched_loop_selector.loop_selector().true_path_loop_proj());
589 unswitch_candidate.update_in_false_path_loop(unswitched_loop_selector.loop_selector().false_path_loop_proj(),
590 old_new[original_head->_idx]->as_Loop());
591 hoist_invariant_check_casts(loop, old_new, unswitch_candidate, unswitched_loop_selector.selector_if());
592 add_unswitched_loop_version_bodies_to_igvn(loop, old_new);
593
594 LoopNode* new_head = old_new[original_head->_idx]->as_Loop();
595 increment_unswitch_counts(original_head, new_head);
596
597 NOT_PRODUCT(trace_loop_unswitching_result(unswitched_loop_selector, unswitch_candidate, original_head, new_head);)
598 C->print_method(PHASE_AFTER_LOOP_UNSWITCHING, 4, new_head);
599 C->set_major_progress();
600 }
601
602 void PhaseIdealLoop::do_multiversioning(IdealLoopTree* lpt, Node_List& old_new) {
603 #ifndef PRODUCT
604 if (TraceLoopOpts || TraceLoopMultiversioning) {
605 tty->print("Multiversion ");
606 lpt->dump_head();
607 }
608 #endif
609 assert(LoopMultiversioning, "LoopMultiversioning must be enabled");
610
611 CountedLoopNode* original_head = lpt->_head->as_CountedLoop();
612 C->print_method(PHASE_BEFORE_LOOP_MULTIVERSIONING, 4, original_head);
613
614 Node* one = _igvn.intcon(1);
615 set_ctrl(one, C->root());
616 Node* opaque = new OpaqueMultiversioningNode(C, one);
617 set_ctrl(opaque, C->root());
784 }
785 return false;
786 }
787
788 #ifndef PRODUCT
789 void PhaseIdealLoop::trace_loop_unswitching_impossible(const LoopNode* original_head) {
790 if (TraceLoopUnswitching) {
791 tty->print_cr("Loop Unswitching \"%d %s\" not possible due to control dependencies",
792 original_head->_idx, original_head->Name());
793 }
794 }
795
796 void PhaseIdealLoop::trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head) {
797 if (TraceLoopOpts) {
798 tty->print("Unswitch %d ", original_head->unswitch_count() + 1);
799 loop->dump_head();
800 }
801 }
802
803 void PhaseIdealLoop::trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
804 const UnswitchCandidate& unswitch_candidate,
805 const LoopNode* original_head, const LoopNode* new_head) {
806 if (TraceLoopUnswitching) {
807 IfNode* unswitch_candidate_if = unswitch_candidate.candidate();
808 IfNode* loop_selector = unswitched_loop_selector.selector_if();
809 tty->print_cr("Loop Unswitching:");
810 tty->print_cr("- Unswitch-Candidate-If: %d %s", unswitch_candidate_if->_idx, unswitch_candidate_if->Name());
811 tty->print_cr("- Loop-Selector-If: %d %s", loop_selector->_idx, loop_selector->Name());
812 tty->print_cr("- True-Path-Loop (=Orig): %d %s", original_head->_idx, original_head->Name());
813 tty->print_cr("- False-Path-Loop (=Clone): %d %s", new_head->_idx, new_head->Name());
814 unswitch_candidate.trace_flat_array_checks();
815 }
816 }
817
818 void PhaseIdealLoop::trace_loop_multiversioning_result(const LoopSelector& loop_selector,
819 const LoopNode* original_head, const LoopNode* new_head) {
820 if (TraceLoopMultiversioning) {
821 IfNode* selector_if = loop_selector.selector();
822 tty->print_cr("Loop Multiversioning:");
823 tty->print_cr("- Loop-Selector-If: %d %s", selector_if->_idx, selector_if->Name());
824 tty->print_cr("- True-Path-Loop (=Orig / Fast): %d %s", original_head->_idx, original_head->Name());
825 tty->print_cr("- False-Path-Loop (=Clone / Slow): %d %s", new_head->_idx, new_head->Name());
826 }
827 }
828 #endif
829
830 // When unswitching a counted loop, we need to convert it back to a normal loop since it's not a proper pre, main or,
831 // post loop anymore after loop unswitching. We also lose the multiversion structure, with access to the multiversion_if.
832 void PhaseIdealLoop::revert_to_normal_loop(const LoopNode* loop_head) {
833 CountedLoopNode* cl = loop_head->isa_CountedLoop();
834 if (cl == nullptr) { return; }
835 if (!cl->is_normal_loop()) { cl->set_normal_loop(); }
836 if (cl->is_multiversion()) { cl->set_no_multiversion(); }
837 }
838
839 // Hoist invariant CheckCastPPNodes out of each unswitched loop version to the appropriate loop selector If projection.
840 void PhaseIdealLoop::hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
841 const UnswitchCandidate& unswitch_candidate,
842 const IfNode* loop_selector) {
843 ResourceMark rm;
844 GrowableArray<CheckCastPPNode*> loop_invariant_check_casts;
845 const IfNode* unswitch_candidate_if = unswitch_candidate.candidate();
846 for (DUIterator_Fast imax, i = unswitch_candidate_if->fast_outs(imax); i < imax; i++) {
847 IfProjNode* proj = unswitch_candidate_if->fast_out(i)->as_IfProj();
848 // Copy to a worklist for easier manipulation
849 for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
850 CheckCastPPNode* check_cast = proj->fast_out(j)->isa_CheckCastPP();
851 if (check_cast != nullptr && loop->is_invariant(check_cast->in(1))) {
852 loop_invariant_check_casts.push(check_cast);
853 }
854 }
855 IfProjNode* loop_selector_if_proj = loop_selector->proj_out(proj->_con)->as_IfProj();
856 while (loop_invariant_check_casts.length() > 0) {
857 CheckCastPPNode* cast = loop_invariant_check_casts.pop();
858 Node* cast_clone = cast->clone();
859 cast_clone->set_req(0, loop_selector_if_proj);
860 _igvn.replace_input_of(cast, 1, cast_clone);
861 register_new_node(cast_clone, loop_selector_if_proj);
862 // Same for the false-path-loop if there are not multiple flat array checks (in that case we leave the
863 // false-path-loop unchanged).
864 if (!unswitch_candidate.has_multiple_flat_array_check_candidates()) {
865 Node* use_clone = old_new[cast->_idx];
866 _igvn.replace_input_of(use_clone, 1, cast_clone);
867 }
868 }
869 }
870 }
871
872 // Enable more optimizations possibilities in the next IGVN round.
873 void PhaseIdealLoop::add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new) {
874 loop->record_for_igvn();
875 for (int i = loop->_body.size() - 1; i >= 0; i--) {
876 Node* n = loop->_body[i];
877 Node* n_clone = old_new[n->_idx];
878 _igvn._worklist.push(n_clone);
879 }
880 }
881
882 void PhaseIdealLoop::increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head) {
883 const int unswitch_count = original_head->unswitch_count() + 1;
884 original_head->set_unswitch_count(unswitch_count);
885 new_head->set_unswitch_count(unswitch_count);
886 }
|