1 /*
2 * Copyright (c) 2006, 2023, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/castnode.hpp"
28 #include "opto/cfgnode.hpp"
29 #include "opto/connode.hpp"
30 #include "opto/convertnode.hpp"
31 #include "opto/loopnode.hpp"
32 #include "opto/opaquenode.hpp"
33 #include "opto/predicates.hpp"
34 #include "opto/rootnode.hpp"
35
36 // Loop Unswitching is a loop optimization to move an invariant, non-loop-exiting test in the loop body before the loop.
37 // Such a test is either always true or always false in all loop iterations and could therefore only be executed once.
38 // To achieve that, we duplicate the loop and change the original and cloned loop as follows:
39 // - Original loop -> true-path-loop:
40 // The true-path of the invariant, non-loop-exiting test in the original loop
41 // is kept while the false-path is killed. We call this unswitched loop version
42 // the true-path-loop.
43 // - Cloned loop -> false-path-loop:
44 // The false-path of the invariant, non-loop-exiting test in the cloned loop
45 // is kept while the true-path is killed. We call this unswitched loop version
46 // the false-path loop.
47 //
48 // The invariant, non-loop-exiting test can now be moved before both loops (to only execute it once) and turned into a
49 // loop selector If node to select at runtime which unswitched loop version should be executed.
50 // - Loop selector true? Execute the true-path-loop.
51 // - Loop selector false? Execute the false-path-loop.
52 //
53 // Note that even though an invariant test that exits the loop could also be optimized with Loop Unswitching, it is more
54 // efficient to simply peel the loop which achieves the same result in a simpler manner (also see policy_peeling()).
55 //
56 // The following graphs summarizes the Loop Unswitching optimization.
57 // We start with the original loop:
58 //
59 // [Predicates]
60 // |
61 // Original Loop
62 // stmt1
63 // if (invariant-test)
64 // if-path
65 // else
66 // else-path
67 // stmt2
68 // Endloop
69 //
70 //
71 // which is unswitched into a true-path-loop and a false-path-loop together with a loop selector:
72 //
73 //
74 // [Initialized Assertion Predicates]
75 // |
76 // loop selector If (invariant-test)
77 // / \
78 // true? false?
79 // / \
80 // [Cloned Parse Predicates] [Cloned Parse Predicates]
81 // [Cloned Template [Cloned Template
82 // Assertion Predicates] Assertion Predicates]
83 // | |
84 // True-Path-Loop False-Path-Loop
85 // cloned stmt1 cloned stmt1
86 // cloned if-path cloned else-path
87 // cloned stmt2 cloned stmt2
88 // Endloop Endloop
89
90
91 // Return true if the loop should be unswitched or false otherwise.
92 bool IdealLoopTree::policy_unswitching(PhaseIdealLoop* phase) const {
93 if (!LoopUnswitching) {
94 return false;
95 }
96 if (!_head->is_Loop()) {
97 return false;
98 }
99
100 // If nodes are depleted, some transform has miscalculated its needs.
101 assert(!phase->exceeding_node_budget(), "sanity");
102
103 // check for vectorized loops, any unswitching was already applied
104 if (_head->is_CountedLoop() && _head->as_CountedLoop()->is_unroll_only()) {
105 return false;
106 }
107
108 LoopNode* head = _head->as_Loop();
109 if (head->unswitch_count() + 1 > head->unswitch_max()) {
110 return false;
111 }
112
113 if (head->is_flat_arrays()) {
114 return false;
115 }
116
117 if (no_unswitch_candidate()) {
118 return false;
119 }
120
121 // Too speculative if running low on nodes.
122 return phase->may_require_nodes(est_loop_clone_sz(2));
123 }
124
125 // Check the absence of any If node that can be used for Loop Unswitching. In that case, no Loop Unswitching can be done.
126 bool IdealLoopTree::no_unswitch_candidate() const {
127 ResourceMark rm;
128 Node_List dont_care;
129 return _phase->find_unswitch_candidates(this, dont_care) == nullptr;
130 }
131
132 // Find an invariant test in the loop body that does not exit the loop. If multiple tests are found, we pick the first
133 // one in the loop body as "unswitch candidate" to apply Loop Unswitching on.
134 // Depending on whether we find such a candidate and if we do, whether it's a flat array check, we do the following:
135 // (1) Candidate is not a flat array check:
136 // Return the unique unswitch candidate.
137 // (2) Candidate is a flat array check:
138 // Collect all remaining non-loop-exiting flat array checks in the loop body in the provided 'flat_array_checks'
139 // list in order to create an unswitched loop version without any flat array checks and a version with checks
140 // (i.e. same as original loop). Return the initially found candidate which could be unique if no further flat array
141 // checks are found.
142 // (3) No candidate is initially found:
143 // As in (2), we collect all non-loop-exiting flat array checks in the loop body in the provided 'flat_array_checks'
144 // list. Pick the first collected flat array check as unswitch candidate, which could be unique, and return it (a).
145 // If there are no flat array checks, we cannot apply Loop Unswitching (b).
146 //
147 // Note that for both (2) and (3a), if there are multiple flat array checks, then the candidate's FlatArrayCheckNode is
148 // later updated in Loop Unswitching to perform a flat array check on all collected flat array checks.
149 IfNode* PhaseIdealLoop::find_unswitch_candidates(const IdealLoopTree* loop, Node_List& flat_array_checks) const {
150 IfNode* unswitch_candidate = find_unswitch_candidate_from_idoms(loop);
151 if (unswitch_candidate != nullptr && !unswitch_candidate->is_flat_array_check(&_igvn)) {
152 // Case (1)
153 return unswitch_candidate;
154 }
155
156 collect_flat_array_checks(loop, flat_array_checks);
157 if (unswitch_candidate != nullptr) {
158 // Case (2)
159 assert(unswitch_candidate->is_flat_array_check(&_igvn), "is a flat array check");
160 return unswitch_candidate;
161 } else if (flat_array_checks.size() > 0) {
162 // Case (3a): Pick first one found as candidate (there could be multiple).
163 return flat_array_checks[0]->as_If();
164 }
165
166 // Case (3b): No suitable unswitch candidate found.
167 return nullptr;
168 }
169
170 // Find an unswitch candidate by following the idom chain from the loop back edge.
171 IfNode* PhaseIdealLoop::find_unswitch_candidate_from_idoms(const IdealLoopTree* loop) const {
172 LoopNode* head = loop->_head->as_Loop();
173 IfNode* unswitch_candidate = nullptr;
174 Node* n = head->in(LoopNode::LoopBackControl);
175 while (n != head) {
176 Node* n_dom = idom(n);
177 if (n->is_Region()) {
178 if (n_dom->is_If()) {
179 IfNode* iff = n_dom->as_If();
180 if (iff->in(1)->is_Bool()) {
181 BoolNode* bol = iff->in(1)->as_Bool();
182 if (bol->in(1)->is_Cmp()) {
183 // If condition is invariant and not a loop exit,
184 // then found reason to unswitch.
185 if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
186 assert(iff->Opcode() == Op_If || iff->is_RangeCheck() || iff->is_BaseCountedLoopEnd(), "valid ifs");
187 unswitch_candidate = iff;
188 }
189 }
190 }
191 }
192 }
193 n = n_dom;
194 }
195 return unswitch_candidate;
196 }
197
198 // Collect all flat array checks in the provided 'flat_array_checks' list.
199 void PhaseIdealLoop::collect_flat_array_checks(const IdealLoopTree* loop, Node_List& flat_array_checks) const {
200 assert(flat_array_checks.size() == 0, "should be empty initially");
201 for (uint i = 0; i < loop->_body.size(); i++) {
202 Node* next = loop->_body.at(i);
203 if (next->is_If() && next->as_If()->is_flat_array_check(&_igvn) && loop->is_invariant(next->in(1)) &&
204 !loop->is_loop_exit(next)) {
205 flat_array_checks.push(next);
206 }
207 }
208 }
209
210 // This class represents an "unswitch candidate" which is an If that can be used to perform Loop Unswitching on. If the
211 // candidate is a flat array check candidate, then we also collect all remaining non-loop-exiting flat array checks.
212 // These are candidates as well. We want to get rid of all these flat array checks in the true-path-loop for the
213 // following reason:
214 //
215 // FlatArrayCheckNodes are used with array accesses to switch between a flat and a non-flat array access. We want
216 // the performance impact on non-flat array accesses to be as small as possible. We therefore create the following
217 // loops in Loop Unswitching:
218 // - True-path-loop: We remove all non-loop-exiting flat array checks to get a loop with only non-flat array accesses
219 // (i.e. a fast path loop).
220 // - False-path-loop: We keep all flat array checks in this loop (i.e. a slow path loop).
221 class UnswitchCandidate : public StackObj {
222 PhaseIdealLoop* const _phase;
223 const Node_List& _old_new;
224 Node* const _original_loop_entry;
225 // If _candidate is a flat array check, this list contains all non-loop-exiting flat array checks in the loop body.
226 Node_List _flat_array_check_candidates;
227 IfNode* const _candidate;
228
229 public:
230 UnswitchCandidate(IdealLoopTree* loop, const Node_List& old_new)
231 : _phase(loop->_phase),
232 _old_new(old_new),
233 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
234 _flat_array_check_candidates(),
235 _candidate(find_unswitch_candidate(loop)) {}
236 NONCOPYABLE(UnswitchCandidate);
237
238 IfNode* find_unswitch_candidate(IdealLoopTree* loop) {
239 IfNode* unswitch_candidate = _phase->find_unswitch_candidates(loop, _flat_array_check_candidates);
240 assert(unswitch_candidate != nullptr, "guaranteed to exist by policy_unswitching");
241 assert(_phase->is_member(loop, unswitch_candidate), "must be inside original loop");
242 return unswitch_candidate;
243 }
244
245 IfNode* candidate() const {
246 return _candidate;
247 }
248
249 // Is the candidate a flat array check and are there other flat array checks as well?
250 bool has_multiple_flat_array_check_candidates() const {
251 return _flat_array_check_candidates.size() > 1;
252 }
253
254 // Remove all candidates from the true-path-loop which are now dominated by the loop selector
255 // (i.e. 'true_path_loop_proj'). The removed candidates are folded in the next IGVN round.
256 void update_in_true_path_loop(IfTrueNode* true_path_loop_proj) const {
257 remove_from_loop(true_path_loop_proj, _candidate);
258 if (has_multiple_flat_array_check_candidates()) {
259 remove_flat_array_checks(true_path_loop_proj);
260 }
261 }
262
263 // Remove a unique candidate from the false-path-loop which is now dominated by the loop selector
264 // (i.e. 'false_path_loop_proj'). The removed candidate is folded in the next IGVN round. If there are multiple
265 // candidates (i.e. flat array checks), then we leave them in the false-path-loop and only mark the loop such that it
266 // is not unswitched anymore in later loop opts rounds.
267 void update_in_false_path_loop(IfFalseNode* false_path_loop_proj, LoopNode* false_path_loop) const {
268 if (has_multiple_flat_array_check_candidates()) {
269 // Leave the flat array checks in the false-path-loop and prevent it from being unswitched again based on these
270 // checks.
271 false_path_loop->mark_flat_arrays();
272 } else {
273 remove_from_loop(false_path_loop_proj, _old_new[_candidate->_idx]->as_If());
274 }
275 }
276
277 private:
278 void remove_from_loop(IfProjNode* dominating_proj, IfNode* candidate) const {
279 _phase->igvn().rehash_node_delayed(candidate);
280 _phase->dominated_by(dominating_proj, candidate);
281 }
282
283 void remove_flat_array_checks(IfProjNode* dominating_proj) const {
284 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
285 IfNode* flat_array_check = _flat_array_check_candidates.at(i)->as_If();
286 _phase->igvn().rehash_node_delayed(flat_array_check);
287 _phase->dominated_by(dominating_proj, flat_array_check);
288 }
289 }
290
291 public:
292 // Merge all flat array checks into a single new BoolNode and return it.
293 BoolNode* merge_flat_array_checks() const {
294 assert(has_multiple_flat_array_check_candidates(), "must have multiple flat array checks to merge");
295 assert(_candidate->in(1)->as_Bool()->_test._test == BoolTest::ne, "IfTrue proj must point to flat array");
296 BoolNode* merged_flat_array_check_bool = create_bool_node();
297 create_flat_array_check_node(merged_flat_array_check_bool);
298 return merged_flat_array_check_bool;
299 }
300
301 private:
302 BoolNode* create_bool_node() const {
303 BoolNode* merged_flat_array_check_bool = _candidate->in(1)->clone()->as_Bool();
304 _phase->register_new_node(merged_flat_array_check_bool, _original_loop_entry);
305 return merged_flat_array_check_bool;
306 }
307
308 void create_flat_array_check_node(BoolNode* merged_flat_array_check_bool) const {
309 FlatArrayCheckNode* cloned_flat_array_check = merged_flat_array_check_bool->in(1)->clone()->as_FlatArrayCheck();
310 _phase->register_new_node(cloned_flat_array_check, _original_loop_entry);
311 merged_flat_array_check_bool->set_req(1, cloned_flat_array_check);
312 set_flat_array_check_inputs(cloned_flat_array_check);
313 }
314
315 // Combine all checks into a single one that fails if one array is flat.
316 void set_flat_array_check_inputs(FlatArrayCheckNode* cloned_flat_array_check) const {
317 assert(cloned_flat_array_check->req() == 3, "unexpected number of inputs for FlatArrayCheck");
318 cloned_flat_array_check->add_req_batch(_phase->C->top(), _flat_array_check_candidates.size() - 1);
319 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
320 Node* array = _flat_array_check_candidates.at(i)->in(1)->in(1)->in(FlatArrayCheckNode::ArrayOrKlass);
321 cloned_flat_array_check->set_req(FlatArrayCheckNode::ArrayOrKlass + i, array);
322 }
323 }
324
325 public:
326 #ifndef PRODUCT
327 void trace_flat_array_checks() const {
328 if (has_multiple_flat_array_check_candidates()) {
329 tty->print_cr("- Unswitched and Merged Flat Array Checks:");
330 for (uint i = 0; i < _flat_array_check_candidates.size(); i++) {
331 Node* unswitch_iff = _flat_array_check_candidates.at(i);
332 Node* cloned_unswitch_iff = _old_new[unswitch_iff->_idx];
333 assert(cloned_unswitch_iff != nullptr, "must exist");
334 tty->print_cr(" - %d %s -> %d %s", unswitch_iff->_idx, unswitch_iff->Name(),
335 cloned_unswitch_iff->_idx, cloned_unswitch_iff->Name());
336 }
337 }
338 }
339 #endif // NOT PRODUCT
340 };
341
342 // This class creates an If node (i.e. loop selector) that selects if the true-path-loop or the false-path-loop should be
343 // executed at runtime. This is done by finding an invariant and non-loop-exiting unswitch candidate If node (guaranteed
344 // to exist at this point) to perform Loop Unswitching on.
345 class UnswitchedLoopSelector : public StackObj {
346 PhaseIdealLoop* const _phase;
347 IdealLoopTree* const _outer_loop;
348 Node* const _original_loop_entry;
349 const UnswitchCandidate& _unswitch_candidate;
350 IfNode* const _selector;
351 IfTrueNode* const _true_path_loop_proj;
352 IfFalseNode* const _false_path_loop_proj;
353
354 enum PathToLoop {
355 TRUE_PATH, FALSE_PATH
356 };
357
358 public:
359 UnswitchedLoopSelector(IdealLoopTree* loop, const UnswitchCandidate& unswitch_candidate)
360 : _phase(loop->_phase),
361 _outer_loop(loop->skip_strip_mined()->_parent),
362 _original_loop_entry(loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl)),
363 _unswitch_candidate(unswitch_candidate),
364 _selector(create_selector_if()),
365 _true_path_loop_proj(create_proj_to_loop(TRUE_PATH)->as_IfTrue()),
366 _false_path_loop_proj(create_proj_to_loop(FALSE_PATH)->as_IfFalse()) {
367 }
368 NONCOPYABLE(UnswitchedLoopSelector);
369
370 private:
371 IfNode* create_selector_if() const {
372 const uint dom_depth = _phase->dom_depth(_original_loop_entry);
373 _phase->igvn().rehash_node_delayed(_original_loop_entry);
374 IfNode* unswitch_candidate_if = _unswitch_candidate.candidate();
375 BoolNode* selector_bool;
376 if (_unswitch_candidate.has_multiple_flat_array_check_candidates()) {
377 selector_bool = _unswitch_candidate.merge_flat_array_checks();
378 } else {
379 selector_bool = unswitch_candidate_if->in(1)->as_Bool();
380 }
381 IfNode* selector_if = IfNode::make_with_same_profile(unswitch_candidate_if, _original_loop_entry, selector_bool);
382 _phase->register_node(selector_if, _outer_loop, _original_loop_entry, dom_depth);
383 return selector_if;
384 }
385
386 IfProjNode* create_proj_to_loop(const PathToLoop path_to_loop) {
387 const uint dom_depth = _phase->dom_depth(_original_loop_entry);
388 IfProjNode* proj_to_loop;
389 if (path_to_loop == TRUE_PATH) {
390 proj_to_loop = new IfTrueNode(_selector);
391 } else {
392 proj_to_loop = new IfFalseNode(_selector);
393 }
394 _phase->register_node(proj_to_loop, _outer_loop, _selector, dom_depth);
395 return proj_to_loop;
396 }
397
398 public:
399 IfNode* selector() const {
400 return _selector;
401 }
402
403 IfTrueNode* true_path_loop_proj() const {
404 return _true_path_loop_proj;
405 }
406
407 IfFalseNode* false_path_loop_proj() const {
408 return _false_path_loop_proj;
409 }
410 };
411
412 // Class to unswitch the original loop and create Predicates at the new unswitched loop versions. The newly cloned loop
413 // becomes the false-path-loop while original loop becomes the true-path-loop.
414 class OriginalLoop : public StackObj {
415 LoopNode* const _loop_head; // OuterStripMinedLoopNode if loop strip mined, else just the loop head.
416 IdealLoopTree* const _loop;
417 Node_List& _old_new;
418 PhaseIdealLoop* const _phase;
419
420 public:
421 OriginalLoop(IdealLoopTree* loop, Node_List& old_new)
422 : _loop_head(loop->_head->as_Loop()->skip_strip_mined()),
423 _loop(loop),
424 _old_new(old_new),
425 _phase(loop->_phase) {}
426 NONCOPYABLE(OriginalLoop);
427
428 private:
429 void fix_loop_entries(IfProjNode* true_path_loop_entry, IfProjNode* false_path_loop_entry) {
430 _phase->replace_loop_entry(_loop_head, true_path_loop_entry);
431 LoopNode* false_path_loop_strip_mined_head = old_to_new(_loop_head)->as_Loop();
432 _phase->replace_loop_entry(false_path_loop_strip_mined_head, false_path_loop_entry);
433 }
434
435 Node* old_to_new(const Node* old) const {
436 return _old_new[old->_idx];
437 }
438
439 #ifdef ASSERT
440 void verify_unswitched_loop_versions(LoopNode* true_path_loop_head,
441 const UnswitchedLoopSelector& unswitched_loop_selector) const {
442 verify_unswitched_loop_version(true_path_loop_head, unswitched_loop_selector.true_path_loop_proj());
443 verify_unswitched_loop_version(old_to_new(true_path_loop_head)->as_Loop(),
444 unswitched_loop_selector.false_path_loop_proj());
445 }
446
447 static void verify_unswitched_loop_version(LoopNode* loop_head, IfProjNode* loop_selector_if_proj) {
448 Node* entry = loop_head->skip_strip_mined()->in(LoopNode::EntryControl);
449 const Predicates predicates(entry);
450 // When skipping all predicates, we should end up at 'loop_selector_if_proj'.
451 assert(loop_selector_if_proj == predicates.entry(), "should end up at loop selector If");
452 }
453 #endif // ASSERT
454
455 public:
456 // Unswitch the original loop on the invariant loop selector by creating a true-path-loop and a false-path-loop.
457 // Remove the unswitch candidate If from both unswitched loop versions which are now covered by the loop selector If.
458 void unswitch(const UnswitchedLoopSelector& unswitched_loop_selector) {
459 _phase->clone_loop(_loop, _old_new, _phase->dom_depth(_loop_head),
460 PhaseIdealLoop::CloneIncludesStripMined, unswitched_loop_selector.selector());
461
462 // At this point, the selector If projections are the corresponding loop entries.
463 // clone_parse_and_assertion_predicates_to_unswitched_loop() could clone additional predicates after the selector
464 // If projections. The loop entries are updated accordingly.
465 IfProjNode* true_path_loop_entry = unswitched_loop_selector.true_path_loop_proj();
466 IfProjNode* false_path_loop_entry = unswitched_loop_selector.false_path_loop_proj();
467 _phase->clone_parse_and_assertion_predicates_to_unswitched_loop(_loop, _old_new,
468 true_path_loop_entry, false_path_loop_entry);
469
470 fix_loop_entries(true_path_loop_entry, false_path_loop_entry);
471 DEBUG_ONLY(verify_unswitched_loop_versions(_loop->_head->as_Loop(), unswitched_loop_selector);)
472 _phase->recompute_dom_depth();
473 }
474 };
475
476 // See comments below file header for more information about Loop Unswitching.
477 void PhaseIdealLoop::do_unswitching(IdealLoopTree* loop, Node_List& old_new) {
478 assert(LoopUnswitching, "LoopUnswitching must be enabled");
479
480 LoopNode* original_head = loop->_head->as_Loop();
481 if (has_control_dependencies_from_predicates(original_head)) {
482 NOT_PRODUCT(trace_loop_unswitching_impossible(original_head);)
483 return;
484 }
485
486 NOT_PRODUCT(trace_loop_unswitching_count(loop, original_head);)
487 C->print_method(PHASE_BEFORE_LOOP_UNSWITCHING, 4, original_head);
488
489 revert_to_normal_loop(original_head);
490
491 const UnswitchCandidate unswitch_candidate(loop, old_new);
492 const UnswitchedLoopSelector unswitched_loop_selector(loop, unswitch_candidate);
493 OriginalLoop original_loop(loop, old_new);
494 original_loop.unswitch(unswitched_loop_selector);
495
496 unswitch_candidate.update_in_true_path_loop(unswitched_loop_selector.true_path_loop_proj());
497 unswitch_candidate.update_in_false_path_loop(unswitched_loop_selector.false_path_loop_proj(),
498 old_new[original_head->_idx]->as_Loop());
499 hoist_invariant_check_casts(loop, old_new, unswitch_candidate, unswitched_loop_selector.selector());
500 add_unswitched_loop_version_bodies_to_igvn(loop, old_new);
501
502 LoopNode* new_head = old_new[original_head->_idx]->as_Loop();
503 increment_unswitch_counts(original_head, new_head);
504
505 NOT_PRODUCT(trace_loop_unswitching_result(unswitched_loop_selector, unswitch_candidate, original_head, new_head);)
506 C->print_method(PHASE_AFTER_LOOP_UNSWITCHING, 4, new_head);
507 C->set_major_progress();
508 }
509
510 bool PhaseIdealLoop::has_control_dependencies_from_predicates(LoopNode* head) {
511 Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
512 const Predicates predicates(entry);
513 if (predicates.has_any()) {
514 assert(entry->is_IfProj(), "sanity - must be ifProj since there is at least one predicate");
515 if (entry->outcnt() > 1) {
516 // Bailout if there are predicates from which there are additional control dependencies (i.e. from loop
517 // entry 'entry') to previously partially peeled statements since this case is not handled and can lead
518 // to a wrong execution. Remove this bailout, once this is fixed.
519 return true;
520 }
521 }
522 return false;
523 }
524
525 #ifndef PRODUCT
526 void PhaseIdealLoop::trace_loop_unswitching_impossible(const LoopNode* original_head) {
527 if (TraceLoopUnswitching) {
528 tty->print_cr("Loop Unswitching \"%d %s\" not possible due to control dependencies",
529 original_head->_idx, original_head->Name());
530 }
531 }
532
533 void PhaseIdealLoop::trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head) {
534 if (TraceLoopOpts) {
535 tty->print("Unswitch %d ", original_head->unswitch_count() + 1);
536 loop->dump_head();
537 }
538 }
539
540 void PhaseIdealLoop::trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
541 const UnswitchCandidate& unswitch_candidate,
542 const LoopNode* original_head, const LoopNode* new_head) {
543 if (TraceLoopUnswitching) {
544 IfNode* unswitch_candidate_if = unswitch_candidate.candidate();
545 IfNode* loop_selector = unswitched_loop_selector.selector();
546 tty->print_cr("Loop Unswitching:");
547 tty->print_cr("- Unswitch-Candidate-If: %d %s", unswitch_candidate_if->_idx, unswitch_candidate_if->Name());
548 tty->print_cr("- Loop-Selector-If: %d %s", loop_selector->_idx, loop_selector->Name());
549 tty->print_cr("- True-Path-Loop (=Orig): %d %s", original_head->_idx, original_head->Name());
550 tty->print_cr("- False-Path-Loop (=Clone): %d %s", new_head->_idx, new_head->Name());
551 unswitch_candidate.trace_flat_array_checks();
552 }
553 }
554 #endif
555
556 // When unswitching a counted loop, we need to convert it back to a normal loop since it's not a proper pre, main or,
557 // post loop anymore after loop unswitching.
558 void PhaseIdealLoop::revert_to_normal_loop(const LoopNode* loop_head) {
559 CountedLoopNode* cl = loop_head->isa_CountedLoop();
560 if (cl != nullptr && !cl->is_normal_loop()) {
561 cl->set_normal_loop();
562 }
563 }
564
565 // Hoist invariant CheckCastPPNodes out of each unswitched loop version to the appropriate loop selector If projection.
566 void PhaseIdealLoop::hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
567 const UnswitchCandidate& unswitch_candidate,
568 const IfNode* loop_selector) {
569 ResourceMark rm;
570 GrowableArray<CheckCastPPNode*> loop_invariant_check_casts;
571 const IfNode* unswitch_candidate_if = unswitch_candidate.candidate();
572 for (DUIterator_Fast imax, i = unswitch_candidate_if->fast_outs(imax); i < imax; i++) {
573 IfProjNode* proj = unswitch_candidate_if->fast_out(i)->as_IfProj();
574 // Copy to a worklist for easier manipulation
575 for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
576 CheckCastPPNode* check_cast = proj->fast_out(j)->isa_CheckCastPP();
577 if (check_cast != nullptr && loop->is_invariant(check_cast->in(1))) {
578 loop_invariant_check_casts.push(check_cast);
579 }
580 }
581 IfProjNode* loop_selector_if_proj = loop_selector->proj_out(proj->_con)->as_IfProj();
582 while (loop_invariant_check_casts.length() > 0) {
583 CheckCastPPNode* cast = loop_invariant_check_casts.pop();
584 Node* cast_clone = cast->clone();
585 cast_clone->set_req(0, loop_selector_if_proj);
586 _igvn.replace_input_of(cast, 1, cast_clone);
587 register_new_node(cast_clone, loop_selector_if_proj);
588 // Same for the false-path-loop if there are not multiple flat array checks (in that case we leave the
589 // false-path-loop unchanged).
590 if (!unswitch_candidate.has_multiple_flat_array_check_candidates()) {
591 Node* use_clone = old_new[cast->_idx];
592 _igvn.replace_input_of(use_clone, 1, cast_clone);
593 }
594 }
595 }
596 }
597
598 // Enable more optimizations possibilities in the next IGVN round.
599 void PhaseIdealLoop::add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new) {
600 loop->record_for_igvn();
601 for (int i = loop->_body.size() - 1; i >= 0; i--) {
602 Node* n = loop->_body[i];
603 Node* n_clone = old_new[n->_idx];
604 _igvn._worklist.push(n_clone);
605 }
606 }
607
608 void PhaseIdealLoop::increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head) {
609 const int unswitch_count = original_head->unswitch_count() + 1;
610 original_head->set_unswitch_count(unswitch_count);
611 new_head->set_unswitch_count(unswitch_count);
612 }