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 }