1 /*
2 * Copyright (c) 2006, 2025, 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 "memory/allocation.inline.hpp"
26 #include "opto/castnode.hpp"
27 #include "opto/cfgnode.hpp"
28 #include "opto/connode.hpp"
29 #include "opto/convertnode.hpp"
30 #include "opto/loopnode.hpp"
31 #include "opto/opaquenode.hpp"
32 #include "opto/predicates.hpp"
33 #include "opto/rootnode.hpp"
34
35 // Multiversioning:
36 // A loop is cloned, and a selector If decides which loop is taken at run-time: the true-path-loop (original) or the
37 // false-path-loop (cloned).
38 //
39 // Use-cases:
40 // - Speculative compilation:
41 // The selector If checks some assumptions which allow stronger optimization in the true-path-loop. If the assumptions
42 // do not hold, we can still execute in the false-path-loop, although with fewer optimizations.
43 // See: PhaseIdealLoop::maybe_multiversion_for_auto_vectorization_runtime_checks
44 // PhaseIdealLoop::create_new_if_for_multiversion
45 //
46 // - Unswitching:
47 // The selector If has the same (loop invariant) condition as some unswitching candidate If inside the loop. This
48 // allows us to constant-fold the unswitching candidate If to true in the true-path-loop and to false in the
49 // false-path-loop, thus eliminating the unswitching candidate If from the loop.
50 //
51 //
52 // Loop Unswitching is a loop optimization to move an invariant, non-loop-exiting test in the loop body before the loop.
53 // Such a test is either always true or always false in all loop iterations and could therefore only be executed once.
54 // To achieve that, we duplicate the loop and change the original and cloned loop as follows:
55 // - Original loop -> true-path-loop:
56 // The true-path of the invariant, non-loop-exiting test in the original loop
57 // is kept while the false-path is killed. We call this unswitched loop version
58 // the true-path-loop.
59 // - Cloned loop -> false-path-loop:
60 // The false-path of the invariant, non-loop-exiting test in the cloned loop
61 // is kept while the true-path is killed. We call this unswitched loop version
62 // the false-path loop.
63 //
64 // The invariant, non-loop-exiting test can now be moved before both loops (to only execute it once) and turned into a
65 // loop selector If node to select at runtime which unswitched loop version should be executed.
66 // - Loop selector true? Execute the true-path-loop.
67 // - Loop selector false? Execute the false-path-loop.
68 //
69 // Note that even though an invariant test that exits the loop could also be optimized with Loop Unswitching, it is more
70 // efficient to simply peel the loop which achieves the same result in a simpler manner (also see policy_peeling()).
71 //
72 // The following graphs summarizes the Loop Unswitching optimization.
73 // We start with the original loop:
74 //
75 // [Predicates]
76 // |
77 // Original Loop
78 // stmt1
79 // if (invariant-test)
80 // if-path
81 // else
82 // else-path
83 // stmt2
84 // Endloop
85 //
86 //
87 // which is unswitched into a true-path-loop and a false-path-loop together with a loop selector:
88 //
89 //
90 // [Initialized Assertion Predicates]
91 // |
92 // loop selector If (invariant-test)
93 // / \
94 // true? false?
95 // / \
96 // [Cloned Parse Predicates] [Cloned Parse Predicates]
97 // [Cloned Template [Cloned Template
98 // Assertion Predicates] Assertion Predicates]
99 // | |
100 // True-Path-Loop False-Path-Loop
101 // cloned stmt1 cloned stmt1
102 // cloned if-path cloned else-path
103 // cloned stmt2 cloned stmt2
104 // Endloop Endloop
105
106
107 // Return true if the loop should be unswitched or false otherwise.
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);
322 }
323
324 void fix_loop_entries(const LoopSelector& loop_selector) const {
325 _phase->replace_loop_entry(_outer_loop_head, loop_selector.true_path_loop_proj());
326 LoopNode* false_path_loop_strip_mined_head = old_to_new(_outer_loop_head)->as_Loop();
327 _phase->replace_loop_entry(false_path_loop_strip_mined_head,
328 loop_selector.false_path_loop_proj());
329 }
330
331 // Moves the Parse And Template Assertion Predicates to the true and false path loop. They are inserted between the
332 // loop heads and the loop selector If projections. The old Parse and Template Assertion Predicates before
333 // the unswitched loop selector are killed.
334 void move_parse_and_template_assertion_predicates_to_unswitched_loops(
335 const LoopSelector& loop_selector, const uint first_false_path_loop_node_index) const {
336 const NodeInOriginalLoopBody node_in_true_path_loop_body(first_false_path_loop_node_index, _old_new);
337 const NodeInClonedLoopBody node_in_false_path_loop_body(first_false_path_loop_node_index);
338 CloneUnswitchedLoopPredicatesVisitor
339 clone_unswitched_loop_predicates_visitor(_loop_head, old_to_new(_loop_head)->as_Loop(), node_in_true_path_loop_body,
340 node_in_false_path_loop_body, _phase);
341 Node* source_loop_entry = loop_selector.selector()->in(0);
342 PredicateIterator predicate_iterator(source_loop_entry);
343 predicate_iterator.for_each(clone_unswitched_loop_predicates_visitor);
344 }
345
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());
428 _igvn.register_new_node_with_optimizer(opaque);
429 _igvn.set_type(opaque, TypeInt::BOOL);
430
431 const LoopSelector loop_selector(lpt, opaque, PROB_LIKELY_MAG(3), COUNT_UNKNOWN);
432 OriginalLoop original_loop(lpt, old_new);
433 original_loop.multiversion(loop_selector);
434
435 add_unswitched_loop_version_bodies_to_igvn(lpt, old_new);
436
437 CountedLoopNode* new_head = old_new[original_head->_idx]->as_CountedLoop();
438 original_head->set_multiversion_fast_loop();
439 new_head->set_multiversion_delayed_slow_loop();
440
441 NOT_PRODUCT(trace_loop_multiversioning_result(loop_selector, original_head, new_head);)
442 C->print_method(PHASE_AFTER_LOOP_MULTIVERSIONING, 4, new_head);
443 C->set_major_progress();
444 }
445
446 // Create a new if in the multiversioning pattern, adding an additional condition for the
447 // multiversioning fast-loop.
448 //
449 // Before:
450 // entry opaque
451 // | |
452 // multiversion_if
453 // | |
454 // +----------------+ +---------------+
455 // | |
456 // multiversion_fast_proj multiversion_slow_proj
457 // |
458 // +--------+
459 // |
460 // slow_path
461 //
462 //
463 // After:
464 // entry opaque <-- to be replaced by caller
465 // | |
466 // new_if
467 // | |
468 // | +-----------------------------+
469 // | |
470 // new_if_true opaque new_if_false
471 // | | |
472 // multiversion_if |
473 // | | |
474 // +----------------+ +---------------+ |
475 // | | |
476 // multiversion_fast_proj new_multiversion_slow_proj |
477 // | |
478 // +------+ |
479 // | |
480 // region
481 // |
482 // slow_path
483 //
484 IfTrueNode* PhaseIdealLoop::create_new_if_for_multiversion(IfTrueNode* multiversioning_fast_proj) {
485 // Give all nodes in the old sub-graph a name.
486 IfNode* multiversion_if = multiversioning_fast_proj->in(0)->as_If();
487 Node* entry = multiversion_if->in(0);
488 OpaqueMultiversioningNode* opaque = multiversion_if->in(1)->as_OpaqueMultiversioning();
489 IfFalseNode* multiversion_slow_proj = multiversion_if->proj_out(0)->as_IfFalse();
490 Node* slow_path = multiversion_slow_proj->unique_ctrl_out();
491
492 // The slow_loop may still be delayed, and waiting for runtime-checks to be added to the
493 // multiversion_if. Now that we have at least one condition for the multiversioning,
494 // we should resume optimizations for the slow loop.
495 opaque->notify_slow_loop_that_it_can_resume_optimizations();
496
497 // Create new_if with its projections.
498 IfNode* new_if = IfNode::make_with_same_profile(multiversion_if, entry, opaque);
499 IdealLoopTree* lp = get_loop(entry);
500 register_control(new_if, lp, entry);
501
502 IfTrueNode* new_if_true = new IfTrueNode(new_if);
503 IfFalseNode* new_if_false = new IfFalseNode(new_if);
504 register_control(new_if_true, lp, new_if);
505 register_control(new_if_false, lp, new_if);
506
507 // Hook new_if_true into multiversion_if.
508 _igvn.replace_input_of(multiversion_if, 0, new_if_true);
509
510 // Clone multiversion_slow_path - this allows us to easily carry the dependencies to
511 // the new region below.
512 IfFalseNode* new_multiversion_slow_proj = multiversion_slow_proj->clone()->as_IfFalse();
513 register_control(new_multiversion_slow_proj, lp, multiversion_if);
514
515 // Create new Region.
516 RegionNode* region = new RegionNode(1);
517 region->add_req(new_multiversion_slow_proj);
518 region->add_req(new_if_false);
519 register_control(region, lp, new_multiversion_slow_proj);
520
521 // Hook region into slow_path, in stead of the multiversion_slow_proj.
522 // This also moves all other dependencies of the multiversion_slow_proj to the region.
523 _igvn.replace_node(multiversion_slow_proj, region);
524
525 return new_if_true;
526 }
527
528 OpaqueMultiversioningNode* find_multiversion_opaque_from_multiversion_if_false(Node* maybe_multiversion_if_false) {
529 IfFalseNode* multiversion_if_false = maybe_multiversion_if_false->isa_IfFalse();
530 if (multiversion_if_false == nullptr) { return nullptr; }
531 IfNode* multiversion_if = multiversion_if_false->in(0)->isa_If();
532 if (multiversion_if == nullptr) { return nullptr; }
533 return multiversion_if->in(1)->isa_OpaqueMultiversioning();
534 }
535
536 bool PhaseIdealLoop::try_resume_optimizations_for_delayed_slow_loop(IdealLoopTree* lpt) {
537 CountedLoopNode* cl = lpt->_head->as_CountedLoop();
538 assert(cl->is_multiversion_delayed_slow_loop(), "must currently be delayed");
539
540 // Find multiversion_if.
541 Node* entry = cl->skip_strip_mined()->in(LoopNode::EntryControl);
542 const Predicates predicates(entry);
543
544 Node* slow_path = predicates.entry();
545
546 // Find opaque.
547 OpaqueMultiversioningNode* opaque = nullptr;
548 if (slow_path->is_Region()) {
549 for (uint i = 1; i < slow_path->req(); i++) {
550 Node* n = slow_path->in(i);
551 opaque = find_multiversion_opaque_from_multiversion_if_false(n);
552 if (opaque != nullptr) { break; }
553 }
554 } else {
555 opaque = find_multiversion_opaque_from_multiversion_if_false(slow_path);
556 }
557 assert(opaque != nullptr, "must have found multiversion opaque node");
558 if (opaque == nullptr) { return false; }
559
560 // We may still be delayed, if there were not yet any runtime-checks added
561 // for the multiversioning. We may never add any, and then this loop would
562 // fold away. So we wait until some runtime-checks are added, then we know
563 // that this loop will be reachable and it is worth optimizing further.
564 if (opaque->is_delayed_slow_loop()) { return false; }
565
566 // Clear away the "delayed" status, i.e. resume optimizations.
567 cl->set_no_multiversion();
568 cl->set_multiversion_slow_loop();
569 #ifndef PRODUCT
570 if (TraceLoopOpts) {
571 tty->print("Resume Optimizations ");
572 lpt->dump_head();
573 }
574 #endif
575 return true;
576 }
577
578 bool PhaseIdealLoop::has_control_dependencies_from_predicates(LoopNode* head) {
579 Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
580 const Predicates predicates(entry);
581 if (predicates.has_any()) {
582 assert(entry->is_IfProj(), "sanity - must be ifProj since there is at least one predicate");
583 if (entry->outcnt() > 1) {
584 // Bailout if there are predicates from which there are additional control dependencies (i.e. from loop
585 // entry 'entry') to previously partially peeled statements since this case is not handled and can lead
586 // to a wrong execution. Remove this bailout, once this is fixed.
587 return true;
588 }
589 }
590 return false;
591 }
592
593 #ifndef PRODUCT
594 void PhaseIdealLoop::trace_loop_unswitching_impossible(const LoopNode* original_head) {
595 if (TraceLoopUnswitching) {
596 tty->print_cr("Loop Unswitching \"%d %s\" not possible due to control dependencies",
597 original_head->_idx, original_head->Name());
598 }
599 }
600
601 void PhaseIdealLoop::trace_loop_unswitching_count(IdealLoopTree* loop, LoopNode* original_head) {
602 if (TraceLoopOpts) {
603 tty->print("Unswitch %d ", original_head->unswitch_count() + 1);
604 loop->dump_head();
605 }
606 }
607
608 void PhaseIdealLoop::trace_loop_unswitching_result(const UnswitchedLoopSelector& unswitched_loop_selector,
609 const LoopNode* original_head, const LoopNode* new_head) {
610 if (TraceLoopUnswitching) {
611 IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
612 IfNode* loop_selector = unswitched_loop_selector.loop_selector().selector();
613 tty->print_cr("Loop Unswitching:");
614 tty->print_cr("- Unswitch-Candidate-If: %d %s", unswitch_candidate->_idx, unswitch_candidate->Name());
615 tty->print_cr("- Loop-Selector-If: %d %s", loop_selector->_idx, loop_selector->Name());
616 tty->print_cr("- True-Path-Loop (=Orig): %d %s", original_head->_idx, original_head->Name());
617 tty->print_cr("- False-Path-Loop (=Clone): %d %s", new_head->_idx, new_head->Name());
618 }
619 }
620
621 void PhaseIdealLoop::trace_loop_multiversioning_result(const LoopSelector& loop_selector,
622 const LoopNode* original_head, const LoopNode* new_head) {
623 if (TraceLoopMultiversioning) {
624 IfNode* selector_if = loop_selector.selector();
625 tty->print_cr("Loop Multiversioning:");
626 tty->print_cr("- Loop-Selector-If: %d %s", selector_if->_idx, selector_if->Name());
627 tty->print_cr("- True-Path-Loop (=Orig / Fast): %d %s", original_head->_idx, original_head->Name());
628 tty->print_cr("- False-Path-Loop (=Clone / Slow): %d %s", new_head->_idx, new_head->Name());
629 }
630 }
631 #endif
632
633 // When unswitching a counted loop, we need to convert it back to a normal loop since it's not a proper pre, main or,
634 // post loop anymore after loop unswitching. We also lose the multiversion structure, with access to the multiversion_if.
635 void PhaseIdealLoop::revert_to_normal_loop(const LoopNode* loop_head) {
636 CountedLoopNode* cl = loop_head->isa_CountedLoop();
637 if (cl == nullptr) { return; }
638 if (!cl->is_normal_loop()) { cl->set_normal_loop(); }
639 if (cl->is_multiversion()) { cl->set_no_multiversion(); }
640 }
641
642 // Hoist invariant CheckCastPPNodes out of each unswitched loop version to the appropriate loop selector If projection.
643 void PhaseIdealLoop::hoist_invariant_check_casts(const IdealLoopTree* loop, const Node_List& old_new,
644 const UnswitchedLoopSelector& unswitched_loop_selector) {
645 IfNode* unswitch_candidate = unswitched_loop_selector.unswitch_candidate();
646 IfNode* loop_selector = unswitched_loop_selector.loop_selector().selector();
647 ResourceMark rm;
648 GrowableArray<CheckCastPPNode*> loop_invariant_check_casts;
649 for (DUIterator_Fast imax, i = unswitch_candidate->fast_outs(imax); i < imax; i++) {
650 IfProjNode* proj = unswitch_candidate->fast_out(i)->as_IfProj();
651 // Copy to a worklist for easier manipulation
652 for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
653 CheckCastPPNode* check_cast = proj->fast_out(j)->isa_CheckCastPP();
654 if (check_cast != nullptr && loop->is_invariant(check_cast->in(1))) {
655 loop_invariant_check_casts.push(check_cast);
656 }
657 }
658 IfProjNode* loop_selector_if_proj = loop_selector->proj_out(proj->_con)->as_IfProj();
659 while (loop_invariant_check_casts.length() > 0) {
660 CheckCastPPNode* cast = loop_invariant_check_casts.pop();
661 Node* cast_clone = cast->clone();
662 cast_clone->set_req(0, loop_selector_if_proj);
663 _igvn.replace_input_of(cast, 1, cast_clone);
664 register_new_node(cast_clone, loop_selector_if_proj);
665 // Same for the clone
666 Node* use_clone = old_new[cast->_idx];
667 _igvn.replace_input_of(use_clone, 1, cast_clone);
668 }
669 }
670 }
671
672 // Enable more optimizations possibilities in the next IGVN round.
673 void PhaseIdealLoop::add_unswitched_loop_version_bodies_to_igvn(IdealLoopTree* loop, const Node_List& old_new) {
674 loop->record_for_igvn();
675 for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
676 Node* n = loop->_body[i];
677 Node* n_clone = old_new[n->_idx];
678 _igvn._worklist.push(n_clone);
679 }
680 }
681
682 void PhaseIdealLoop::increment_unswitch_counts(LoopNode* original_head, LoopNode* new_head) {
683 const int unswitch_count = original_head->unswitch_count() + 1;
684 original_head->set_unswitch_count(unswitch_count);
685 new_head->set_unswitch_count(unswitch_count);
686 }
687