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