1/* Loop unswitching. 2 Copyright (C) 2004-2022 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 3, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "backend.h" 24#include "tree.h" 25#include "gimple.h" 26#include "tree-pass.h" 27#include "ssa.h" 28#include "fold-const.h" 29#include "gimplify.h" 30#include "tree-cfg.h" 31#include "tree-ssa.h" 32#include "tree-ssa-loop-niter.h" 33#include "tree-ssa-loop.h" 34#include "tree-into-ssa.h" 35#include "cfgloop.h" 36#include "tree-inline.h" 37#include "gimple-iterator.h" 38#include "cfghooks.h" 39#include "tree-ssa-loop-manip.h" 40#include "tree-vectorizer.h" 41 42/* This file implements the loop unswitching, i.e. transformation of loops like 43 44 while (A) 45 { 46 if (inv) 47 B; 48 49 X; 50 51 if (!inv) 52 C; 53 } 54 55 where inv is the loop invariant, into 56 57 if (inv) 58 { 59 while (A) 60 { 61 B; 62 X; 63 } 64 } 65 else 66 { 67 while (A) 68 { 69 X; 70 C; 71 } 72 } 73 74 Inv is considered invariant iff the values it compares are both invariant; 75 tree-ssa-loop-im.cc ensures that all the suitable conditions are in this 76 shape. */ 77 78static class loop *tree_unswitch_loop (class loop *, basic_block, tree); 79static bool tree_unswitch_single_loop (class loop *, int); 80static tree tree_may_unswitch_on (basic_block, class loop *); 81static bool tree_unswitch_outer_loop (class loop *); 82static edge find_loop_guard (class loop *, vec<gimple *>&); 83static bool empty_bb_without_guard_p (class loop *, basic_block, 84 vec<gimple *>&); 85static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&); 86static void hoist_guard (class loop *, edge); 87static bool check_exit_phi (class loop *); 88static tree get_vop_from_header (class loop *); 89 90/* Main entry point. Perform loop unswitching on all suitable loops. */ 91 92unsigned int 93tree_ssa_unswitch_loops (void) 94{ 95 bool changed = false; 96 97 /* Go through all loops starting from innermost. */ 98 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST)) 99 { 100 if (!loop->inner) 101 /* Unswitch innermost loop. */ 102 changed |= tree_unswitch_single_loop (loop, 0); 103 else 104 changed |= tree_unswitch_outer_loop (loop); 105 } 106 107 if (changed) 108 return TODO_cleanup_cfg; 109 return 0; 110} 111 112/* Return TRUE if an SSA_NAME maybe undefined and is therefore 113 unsuitable for unswitching. STMT is the statement we are 114 considering for unswitching and LOOP is the loop it appears in. */ 115 116static bool 117is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) 118{ 119 /* The loop header is the only block we can trivially determine that 120 will always be executed. If the comparison is in the loop 121 header, we know it's OK to unswitch on it. */ 122 if (gimple_bb (stmt) == loop->header) 123 return false; 124 125 auto_bitmap visited_ssa; 126 auto_vec<tree> worklist; 127 worklist.safe_push (name); 128 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); 129 while (!worklist.is_empty ()) 130 { 131 tree t = worklist.pop (); 132 133 /* If it's obviously undefined, avoid further computations. */ 134 if (ssa_undefined_value_p (t, true)) 135 return true; 136 137 if (ssa_defined_default_def_p (t)) 138 continue; 139 140 gimple *def = SSA_NAME_DEF_STMT (t); 141 142 /* Check that all the PHI args are fully defined. */ 143 if (gphi *phi = dyn_cast <gphi *> (def)) 144 { 145 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) 146 { 147 tree t = gimple_phi_arg_def (phi, i); 148 /* If an SSA has already been seen, it may be a loop, 149 but we can continue and ignore this use. Otherwise, 150 add the SSA_NAME to the queue and visit it later. */ 151 if (TREE_CODE (t) == SSA_NAME 152 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) 153 worklist.safe_push (t); 154 } 155 continue; 156 } 157 158 /* Uses in stmts always executed when the region header executes 159 are fine. */ 160 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def))) 161 continue; 162 163 /* Handle calls and memory loads conservatively. */ 164 if (!is_gimple_assign (def) 165 || (gimple_assign_single_p (def) 166 && gimple_vuse (def))) 167 return true; 168 169 /* Check that any SSA names used to define NAME are also fully 170 defined. */ 171 use_operand_p use_p; 172 ssa_op_iter iter; 173 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) 174 { 175 tree t = USE_FROM_PTR (use_p); 176 /* If an SSA has already been seen, it may be a loop, 177 but we can continue and ignore this use. Otherwise, 178 add the SSA_NAME to the queue and visit it later. */ 179 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) 180 worklist.safe_push (t); 181 } 182 } 183 return false; 184} 185 186/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its 187 basic blocks (for what it means see comments below). */ 188 189static tree 190tree_may_unswitch_on (basic_block bb, class loop *loop) 191{ 192 gimple *last, *def; 193 gcond *stmt; 194 tree cond, use; 195 basic_block def_bb; 196 ssa_op_iter iter; 197 198 /* BB must end in a simple conditional jump. */ 199 last = last_stmt (bb); 200 if (!last || gimple_code (last) != GIMPLE_COND) 201 return NULL_TREE; 202 stmt = as_a <gcond *> (last); 203 204 /* To keep the things simple, we do not directly remove the conditions, 205 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite 206 loop where we would unswitch again on such a condition. */ 207 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) 208 return NULL_TREE; 209 210 /* Condition must be invariant. */ 211 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 212 { 213 def = SSA_NAME_DEF_STMT (use); 214 def_bb = gimple_bb (def); 215 if (def_bb 216 && flow_bb_inside_loop_p (loop, def_bb)) 217 return NULL_TREE; 218 /* Unswitching on undefined values would introduce undefined 219 behavior that the original program might never exercise. */ 220 if (is_maybe_undefined (use, stmt, loop)) 221 return NULL_TREE; 222 } 223 224 cond = build2 (gimple_cond_code (stmt), boolean_type_node, 225 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 226 227 return cond; 228} 229 230/* Simplifies COND using checks in front of the entry of the LOOP. Just very 231 simplish (sufficient to prevent us from duplicating loop in unswitching 232 unnecessarily). */ 233 234static tree 235simplify_using_entry_checks (class loop *loop, tree cond) 236{ 237 edge e = loop_preheader_edge (loop); 238 gimple *stmt; 239 240 while (1) 241 { 242 stmt = last_stmt (e->src); 243 if (stmt 244 && gimple_code (stmt) == GIMPLE_COND 245 && gimple_cond_code (stmt) == TREE_CODE (cond) 246 && operand_equal_p (gimple_cond_lhs (stmt), 247 TREE_OPERAND (cond, 0), 0) 248 && operand_equal_p (gimple_cond_rhs (stmt), 249 TREE_OPERAND (cond, 1), 0)) 250 return (e->flags & EDGE_TRUE_VALUE 251 ? boolean_true_node 252 : boolean_false_node); 253 254 if (!single_pred_p (e->src)) 255 return cond; 256 257 e = single_pred_edge (e->src); 258 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 259 return cond; 260 } 261} 262 263/* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow 264 it to grow too much, it is too easy to create example on that the code would 265 grow exponentially. */ 266 267static bool 268tree_unswitch_single_loop (class loop *loop, int num) 269{ 270 basic_block *bbs; 271 class loop *nloop; 272 unsigned i, found; 273 tree cond = NULL_TREE; 274 gimple *stmt; 275 bool changed = false; 276 HOST_WIDE_INT iterations; 277 278 dump_user_location_t loc = find_loop_location (loop); 279 280 /* Perform initial tests if unswitch is eligible. */ 281 if (num == 0) 282 { 283 /* Do not unswitch in cold regions. */ 284 if (optimize_loop_for_size_p (loop)) 285 { 286 if (dump_enabled_p ()) 287 dump_printf_loc (MSG_NOTE, loc, 288 "Not unswitching cold loops\n"); 289 return false; 290 } 291 292 /* The loop should not be too large, to limit code growth. */ 293 if (tree_num_loop_insns (loop, &eni_size_weights) 294 > (unsigned) param_max_unswitch_insns) 295 { 296 if (dump_enabled_p ()) 297 dump_printf_loc (MSG_NOTE, loc, 298 "Not unswitching, loop too big\n"); 299 return false; 300 } 301 302 /* If the loop is not expected to iterate, there is no need 303 for unswitching. */ 304 iterations = estimated_loop_iterations_int (loop); 305 if (iterations < 0) 306 iterations = likely_max_loop_iterations_int (loop); 307 if (iterations >= 0 && iterations <= 1) 308 { 309 if (dump_enabled_p ()) 310 dump_printf_loc (MSG_NOTE, loc, 311 "Not unswitching, loop is not expected" 312 " to iterate\n"); 313 return false; 314 } 315 } 316 317 i = 0; 318 bbs = get_loop_body (loop); 319 found = loop->num_nodes; 320 321 while (1) 322 { 323 /* Find a bb to unswitch on. */ 324 for (; i < loop->num_nodes; i++) 325 if ((cond = tree_may_unswitch_on (bbs[i], loop))) 326 break; 327 328 if (i == loop->num_nodes) 329 { 330 if (dump_enabled_p () 331 && num > param_max_unswitch_level) 332 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 333 "Not unswitching anymore, hit max level\n"); 334 335 if (found == loop->num_nodes) 336 { 337 free (bbs); 338 return changed; 339 } 340 break; 341 } 342 343 cond = simplify_using_entry_checks (loop, cond); 344 stmt = last_stmt (bbs[i]); 345 if (integer_nonzerop (cond)) 346 { 347 /* Remove false path. */ 348 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), 349 boolean_true_node); 350 changed = true; 351 } 352 else if (integer_zerop (cond)) 353 { 354 /* Remove true path. */ 355 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), 356 boolean_false_node); 357 changed = true; 358 } 359 /* Do not unswitch too much. */ 360 else if (num > param_max_unswitch_level) 361 { 362 i++; 363 continue; 364 } 365 /* In nested tree_unswitch_single_loop first optimize all conditions 366 using entry checks, then discover still reachable blocks in the 367 loop and find the condition only among those still reachable bbs. */ 368 else if (num != 0) 369 { 370 if (found == loop->num_nodes) 371 found = i; 372 i++; 373 continue; 374 } 375 else 376 { 377 found = i; 378 break; 379 } 380 381 update_stmt (stmt); 382 i++; 383 } 384 385 if (num != 0) 386 { 387 basic_block *tos, *worklist; 388 389 /* When called recursively, first do a quick discovery 390 of reachable bbs after the above changes and only 391 consider conditions in still reachable bbs. */ 392 tos = worklist = XNEWVEC (basic_block, loop->num_nodes); 393 394 for (i = 0; i < loop->num_nodes; i++) 395 bbs[i]->flags &= ~BB_REACHABLE; 396 397 /* Start with marking header. */ 398 *tos++ = bbs[0]; 399 bbs[0]->flags |= BB_REACHABLE; 400 401 /* Iterate: find everything reachable from what we've already seen 402 within the same innermost loop. Don't look through false edges 403 if condition is always true or true edges if condition is 404 always false. */ 405 while (tos != worklist) 406 { 407 basic_block b = *--tos; 408 edge e; 409 edge_iterator ei; 410 int flags = 0; 411 412 if (EDGE_COUNT (b->succs) == 2) 413 { 414 gimple *stmt = last_stmt (b); 415 if (stmt 416 && gimple_code (stmt) == GIMPLE_COND) 417 { 418 gcond *cond_stmt = as_a <gcond *> (stmt); 419 if (gimple_cond_true_p (cond_stmt)) 420 flags = EDGE_FALSE_VALUE; 421 else if (gimple_cond_false_p (cond_stmt)) 422 flags = EDGE_TRUE_VALUE; 423 } 424 } 425 426 FOR_EACH_EDGE (e, ei, b->succs) 427 { 428 basic_block dest = e->dest; 429 430 if (dest->loop_father == loop 431 && !(dest->flags & BB_REACHABLE) 432 && !(e->flags & flags)) 433 { 434 *tos++ = dest; 435 dest->flags |= BB_REACHABLE; 436 } 437 } 438 } 439 440 free (worklist); 441 442 /* Find a bb to unswitch on. */ 443 for (; found < loop->num_nodes; found++) 444 if ((bbs[found]->flags & BB_REACHABLE) 445 && (cond = tree_may_unswitch_on (bbs[found], loop))) 446 break; 447 448 if (found == loop->num_nodes) 449 { 450 free (bbs); 451 return changed; 452 } 453 } 454 455 if (dump_enabled_p ()) 456 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, 457 "Unswitching loop on condition: %G\n", 458 last_stmt (bbs[found])); 459 460 initialize_original_copy_tables (); 461 /* Unswitch the loop on this condition. */ 462 nloop = tree_unswitch_loop (loop, bbs[found], cond); 463 if (!nloop) 464 { 465 free_original_copy_tables (); 466 free (bbs); 467 return changed; 468 } 469 470 /* Update the SSA form after unswitching. */ 471 update_ssa (TODO_update_ssa); 472 free_original_copy_tables (); 473 474 /* Invoke itself on modified loops. */ 475 tree_unswitch_single_loop (nloop, num + 1); 476 tree_unswitch_single_loop (loop, num + 1); 477 free (bbs); 478 return true; 479} 480 481/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support 482 unswitching of innermost loops. COND is the condition determining which 483 loop is entered -- the new loop is entered if COND is true. Returns NULL 484 if impossible, new loop otherwise. */ 485 486static class loop * 487tree_unswitch_loop (class loop *loop, 488 basic_block unswitch_on, tree cond) 489{ 490 profile_probability prob_true; 491 edge edge_true, edge_false; 492 493 /* Some sanity checking. */ 494 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); 495 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); 496 gcc_assert (loop->inner == NULL); 497 498 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); 499 prob_true = edge_true->probability; 500 return loop_version (loop, unshare_expr (cond), 501 NULL, prob_true, 502 prob_true.invert (), 503 prob_true, prob_true.invert (), 504 false); 505} 506 507/* Unswitch outer loops by hoisting invariant guard on 508 inner loop without code duplication. */ 509static bool 510tree_unswitch_outer_loop (class loop *loop) 511{ 512 edge exit, guard; 513 HOST_WIDE_INT iterations; 514 515 gcc_assert (loop->inner); 516 if (loop->inner->next) 517 return false; 518 /* Accept loops with single exit only which is not from inner loop. */ 519 exit = single_exit (loop); 520 if (!exit || exit->src->loop_father != loop) 521 return false; 522 /* Check that phi argument of exit edge is not defined inside loop. */ 523 if (!check_exit_phi (loop)) 524 return false; 525 /* If the loop is not expected to iterate, there is no need 526 for unswitching. */ 527 iterations = estimated_loop_iterations_int (loop); 528 if (iterations < 0) 529 iterations = likely_max_loop_iterations_int (loop); 530 if (iterations >= 0 && iterations <= 1) 531 { 532 if (dump_enabled_p ()) 533 dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop), 534 "Not unswitching, loop is not expected" 535 " to iterate\n"); 536 return false; 537 } 538 539 bool changed = false; 540 auto_vec<gimple *> dbg_to_reset; 541 while ((guard = find_loop_guard (loop, dbg_to_reset))) 542 { 543 if (! changed) 544 rewrite_virtuals_into_loop_closed_ssa (loop); 545 hoist_guard (loop, guard); 546 for (gimple *debug_stmt : dbg_to_reset) 547 { 548 gimple_debug_bind_reset_value (debug_stmt); 549 update_stmt (debug_stmt); 550 } 551 dbg_to_reset.truncate (0); 552 changed = true; 553 } 554 return changed; 555} 556 557/* Checks if the body of the LOOP is within an invariant guard. If this 558 is the case, returns the edge that jumps over the real body of the loop, 559 otherwise returns NULL. */ 560 561static edge 562find_loop_guard (class loop *loop, vec<gimple *> &dbg_to_reset) 563{ 564 basic_block header = loop->header; 565 edge guard_edge, te, fe; 566 basic_block *body = NULL; 567 unsigned i; 568 tree use; 569 ssa_op_iter iter; 570 571 /* We check for the following situation: 572 573 while (1) 574 { 575 [header]] 576 loop_phi_nodes; 577 something1; 578 if (cond1) 579 body; 580 nvar = phi(orig, bvar) ... for all variables changed in body; 581 [guard_end] 582 something2; 583 if (cond2) 584 break; 585 something3; 586 } 587 588 where: 589 590 1) cond1 is loop invariant 591 2) If cond1 is false, then the loop is essentially empty; i.e., 592 a) nothing in something1, something2 and something3 has side 593 effects 594 b) anything defined in something1, something2 and something3 595 is not used outside of the loop. */ 596 597 gcond *cond; 598 do 599 { 600 basic_block next = NULL; 601 if (single_succ_p (header)) 602 next = single_succ (header); 603 else 604 { 605 cond = safe_dyn_cast <gcond *> (last_stmt (header)); 606 if (! cond) 607 return NULL; 608 extract_true_false_edges_from_block (header, &te, &fe); 609 /* Make sure to skip earlier hoisted guards that are left 610 in place as if (true). */ 611 if (gimple_cond_true_p (cond)) 612 next = te->dest; 613 else if (gimple_cond_false_p (cond)) 614 next = fe->dest; 615 else 616 break; 617 } 618 /* Never traverse a backedge. */ 619 if (header->loop_father->header == next) 620 return NULL; 621 header = next; 622 } 623 while (1); 624 if (!flow_bb_inside_loop_p (loop, te->dest) 625 || !flow_bb_inside_loop_p (loop, fe->dest)) 626 return NULL; 627 628 if (just_once_each_iteration_p (loop, te->dest) 629 || (single_succ_p (te->dest) 630 && just_once_each_iteration_p (loop, single_succ (te->dest)))) 631 { 632 if (just_once_each_iteration_p (loop, fe->dest)) 633 return NULL; 634 guard_edge = te; 635 } 636 else if (just_once_each_iteration_p (loop, fe->dest) 637 || (single_succ_p (fe->dest) 638 && just_once_each_iteration_p (loop, single_succ (fe->dest)))) 639 guard_edge = fe; 640 else 641 return NULL; 642 643 dump_user_location_t loc = find_loop_location (loop); 644 645 /* Guard edge must skip inner loop. */ 646 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header, 647 guard_edge == fe ? te->dest : fe->dest)) 648 { 649 if (dump_enabled_p ()) 650 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 651 "Guard edge %d --> %d is not around the loop!\n", 652 guard_edge->src->index, guard_edge->dest->index); 653 return NULL; 654 } 655 if (guard_edge->dest == loop->latch) 656 { 657 if (dump_enabled_p ()) 658 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 659 "Guard edge destination is loop latch.\n"); 660 return NULL; 661 } 662 663 if (dump_enabled_p ()) 664 dump_printf_loc (MSG_NOTE, loc, 665 "Considering guard %d -> %d in loop %d\n", 666 guard_edge->src->index, guard_edge->dest->index, 667 loop->num); 668 /* Check if condition operands do not have definitions inside loop since 669 any bb copying is not performed. */ 670 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE) 671 { 672 gimple *def = SSA_NAME_DEF_STMT (use); 673 basic_block def_bb = gimple_bb (def); 674 if (def_bb 675 && flow_bb_inside_loop_p (loop, def_bb)) 676 { 677 if (dump_enabled_p ()) 678 dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions" 679 " inside loop\n"); 680 return NULL; 681 } 682 } 683 684 body = get_loop_body (loop); 685 for (i = 0; i < loop->num_nodes; i++) 686 { 687 basic_block bb = body[i]; 688 if (bb->loop_father != loop) 689 continue; 690 if (bb->flags & BB_IRREDUCIBLE_LOOP) 691 { 692 if (dump_enabled_p ()) 693 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 694 "Block %d is marked as irreducible in loop\n", 695 bb->index); 696 guard_edge = NULL; 697 goto end; 698 } 699 if (!empty_bb_without_guard_p (loop, bb, dbg_to_reset)) 700 { 701 if (dump_enabled_p ()) 702 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, 703 "Block %d has side effects\n", bb->index); 704 guard_edge = NULL; 705 goto end; 706 } 707 } 708 709 if (dump_enabled_p ()) 710 dump_printf_loc (MSG_NOTE, loc, 711 "suitable to hoist\n"); 712end: 713 if (body) 714 free (body); 715 return guard_edge; 716} 717 718/* Returns true if 719 1) no statement in BB has side effects 720 2) assuming that edge GUARD is always taken, all definitions in BB 721 are noy used outside of the loop. 722 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and 723 PROCESSED is a set of ssa names for that we already tested whether they 724 are invariant or not. Uses in debug stmts outside of the loop are 725 pushed to DBG_TO_RESET. */ 726 727static bool 728empty_bb_without_guard_p (class loop *loop, basic_block bb, 729 vec<gimple *> &dbg_to_reset) 730{ 731 basic_block exit_bb = single_exit (loop)->src; 732 bool may_be_used_outside = (bb == exit_bb 733 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)); 734 tree name; 735 ssa_op_iter op_iter; 736 737 /* Phi nodes do not have side effects, but their results might be used 738 outside of the loop. */ 739 if (may_be_used_outside) 740 { 741 for (gphi_iterator gsi = gsi_start_phis (bb); 742 !gsi_end_p (gsi); gsi_next (&gsi)) 743 { 744 gphi *phi = gsi.phi (); 745 name = PHI_RESULT (phi); 746 if (virtual_operand_p (name)) 747 continue; 748 749 if (used_outside_loop_p (loop, name, dbg_to_reset)) 750 return false; 751 } 752 } 753 754 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); 755 !gsi_end_p (gsi); gsi_next (&gsi)) 756 { 757 gimple *stmt = gsi_stmt (gsi); 758 if (is_gimple_debug (stmt)) 759 continue; 760 761 if (gimple_has_side_effects (stmt)) 762 return false; 763 764 if (gimple_vdef(stmt)) 765 return false; 766 767 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF) 768 { 769 if (may_be_used_outside 770 && used_outside_loop_p (loop, name, dbg_to_reset)) 771 return false; 772 } 773 } 774 return true; 775} 776 777/* Return true if NAME is used outside of LOOP. Pushes debug stmts that 778 have such uses to DBG_TO_RESET but do not consider such uses. */ 779 780static bool 781used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset) 782{ 783 imm_use_iterator it; 784 use_operand_p use; 785 786 FOR_EACH_IMM_USE_FAST (use, it, name) 787 { 788 gimple *stmt = USE_STMT (use); 789 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) 790 { 791 if (!is_gimple_debug (stmt)) 792 return true; 793 dbg_to_reset.safe_push (stmt); 794 } 795 } 796 797 return false; 798} 799 800/* Return argument for loop preheader edge in header virtual phi if any. */ 801 802static tree 803get_vop_from_header (class loop *loop) 804{ 805 for (gphi_iterator gsi = gsi_start_phis (loop->header); 806 !gsi_end_p (gsi); gsi_next (&gsi)) 807 { 808 gphi *phi = gsi.phi (); 809 if (!virtual_operand_p (gimple_phi_result (phi))) 810 continue; 811 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 812 } 813 return NULL_TREE; 814} 815 816/* Move the check of GUARD outside of LOOP. */ 817 818static void 819hoist_guard (class loop *loop, edge guard) 820{ 821 edge exit = single_exit (loop); 822 edge preh = loop_preheader_edge (loop); 823 basic_block pre_header = preh->src; 824 basic_block bb; 825 edge te, fe, e, new_edge; 826 gimple *stmt; 827 basic_block guard_bb = guard->src; 828 edge not_guard; 829 gimple_stmt_iterator gsi; 830 int flags = 0; 831 bool fix_dom_of_exit; 832 gcond *cond_stmt, *new_cond_stmt; 833 834 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest); 835 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb); 836 gsi = gsi_last_bb (guard_bb); 837 stmt = gsi_stmt (gsi); 838 gcc_assert (gimple_code (stmt) == GIMPLE_COND); 839 cond_stmt = as_a <gcond *> (stmt); 840 extract_true_false_edges_from_block (guard_bb, &te, &fe); 841 /* Insert guard to PRE_HEADER. */ 842 if (!empty_block_p (pre_header)) 843 gsi = gsi_last_bb (pre_header); 844 else 845 gsi = gsi_start_bb (pre_header); 846 /* Create copy of COND_STMT. */ 847 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt), 848 gimple_cond_lhs (cond_stmt), 849 gimple_cond_rhs (cond_stmt), 850 NULL_TREE, NULL_TREE); 851 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT); 852 /* Convert COND_STMT to true/false conditional. */ 853 if (guard == te) 854 gimple_cond_make_false (cond_stmt); 855 else 856 gimple_cond_make_true (cond_stmt); 857 update_stmt (cond_stmt); 858 /* Create new loop pre-header. */ 859 e = split_block (pre_header, last_stmt (pre_header)); 860 861 dump_user_location_t loc = find_loop_location (loop); 862 863 if (dump_enabled_p ()) 864 { 865 char buffer[64]; 866 guard->probability.dump (buffer); 867 868 dump_printf_loc (MSG_NOTE, loc, 869 "Moving guard %i->%i (prob %s) to bb %i, " 870 "new preheader is %i\n", 871 guard->src->index, guard->dest->index, 872 buffer, e->src->index, e->dest->index); 873 } 874 875 gcc_assert (loop_preheader_edge (loop)->src == e->dest); 876 877 if (guard == fe) 878 { 879 e->flags = EDGE_TRUE_VALUE; 880 flags |= EDGE_FALSE_VALUE; 881 not_guard = te; 882 } 883 else 884 { 885 e->flags = EDGE_FALSE_VALUE; 886 flags |= EDGE_TRUE_VALUE; 887 not_guard = fe; 888 } 889 new_edge = make_edge (pre_header, exit->dest, flags); 890 891 /* Determine the probability that we skip the loop. Assume that loop has 892 same average number of iterations regardless outcome of guard. */ 893 new_edge->probability = guard->probability; 894 profile_count skip_count = guard->src->count.nonzero_p () 895 ? guard->count ().apply_scale (pre_header->count, 896 guard->src->count) 897 : guard->count ().apply_probability (new_edge->probability); 898 899 if (skip_count > e->count ()) 900 { 901 fprintf (dump_file, " Capping count; expect profile inconsistency\n"); 902 skip_count = e->count (); 903 } 904 if (dump_enabled_p ()) 905 { 906 char buffer[64]; 907 new_edge->probability.dump (buffer); 908 909 dump_printf_loc (MSG_NOTE, loc, 910 "Estimated probability of skipping loop is %s\n", 911 buffer); 912 } 913 914 /* Update profile after the transform: 915 916 First decrease count of path from newly hoisted loop guard 917 to loop header... */ 918 e->probability = new_edge->probability.invert (); 919 e->dest->count = e->count (); 920 921 /* ... now update profile to represent that original guard will be optimized 922 away ... */ 923 guard->probability = profile_probability::never (); 924 not_guard->probability = profile_probability::always (); 925 926 /* ... finally scale everything in the loop except for guarded basic blocks 927 where profile does not change. */ 928 basic_block *body = get_loop_body (loop); 929 930 for (unsigned int i = 0; i < loop->num_nodes; i++) 931 { 932 basic_block bb = body[i]; 933 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest)) 934 { 935 if (dump_enabled_p ()) 936 dump_printf_loc (MSG_NOTE, loc, 937 "Scaling nonguarded BBs in loop: %i\n", 938 bb->index); 939 if (e->probability.initialized_p ()) 940 scale_bbs_frequencies (&bb, 1, e->probability); 941 } 942 } 943 944 if (fix_dom_of_exit) 945 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header); 946 /* Add NEW_ADGE argument for all phi in post-header block. */ 947 bb = exit->dest; 948 for (gphi_iterator gsi = gsi_start_phis (bb); 949 !gsi_end_p (gsi); gsi_next (&gsi)) 950 { 951 gphi *phi = gsi.phi (); 952 tree arg; 953 if (virtual_operand_p (gimple_phi_result (phi))) 954 { 955 arg = get_vop_from_header (loop); 956 if (arg == NULL_TREE) 957 /* Use exit edge argument. */ 958 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); 959 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); 960 } 961 else 962 { 963 /* Use exit edge argument. */ 964 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); 965 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); 966 } 967 } 968 969 if (dump_enabled_p ()) 970 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, 971 "Guard hoisted\n"); 972 973 free (body); 974} 975 976/* Return true if phi argument for exit edge can be used 977 for edge around loop. */ 978 979static bool 980check_exit_phi (class loop *loop) 981{ 982 edge exit = single_exit (loop); 983 basic_block pre_header = loop_preheader_edge (loop)->src; 984 985 for (gphi_iterator gsi = gsi_start_phis (exit->dest); 986 !gsi_end_p (gsi); gsi_next (&gsi)) 987 { 988 gphi *phi = gsi.phi (); 989 tree arg; 990 gimple *def; 991 basic_block def_bb; 992 if (virtual_operand_p (gimple_phi_result (phi))) 993 continue; 994 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); 995 if (TREE_CODE (arg) != SSA_NAME) 996 continue; 997 def = SSA_NAME_DEF_STMT (arg); 998 if (!def) 999 continue; 1000 def_bb = gimple_bb (def); 1001 if (!def_bb) 1002 continue; 1003 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb)) 1004 /* Definition inside loop! */ 1005 return false; 1006 /* Check loop closed phi invariant. */ 1007 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header)) 1008 return false; 1009 } 1010 return true; 1011} 1012 1013/* Loop unswitching pass. */ 1014 1015namespace { 1016 1017const pass_data pass_data_tree_unswitch = 1018{ 1019 GIMPLE_PASS, /* type */ 1020 "unswitch", /* name */ 1021 OPTGROUP_LOOP, /* optinfo_flags */ 1022 TV_TREE_LOOP_UNSWITCH, /* tv_id */ 1023 PROP_cfg, /* properties_required */ 1024 0, /* properties_provided */ 1025 0, /* properties_destroyed */ 1026 0, /* todo_flags_start */ 1027 0, /* todo_flags_finish */ 1028}; 1029 1030class pass_tree_unswitch : public gimple_opt_pass 1031{ 1032public: 1033 pass_tree_unswitch (gcc::context *ctxt) 1034 : gimple_opt_pass (pass_data_tree_unswitch, ctxt) 1035 {} 1036 1037 /* opt_pass methods: */ 1038 virtual bool gate (function *) { return flag_unswitch_loops != 0; } 1039 virtual unsigned int execute (function *); 1040 1041}; // class pass_tree_unswitch 1042 1043unsigned int 1044pass_tree_unswitch::execute (function *fun) 1045{ 1046 if (number_of_loops (fun) <= 1) 1047 return 0; 1048 1049 return tree_ssa_unswitch_loops (); 1050} 1051 1052} // anon namespace 1053 1054gimple_opt_pass * 1055make_pass_tree_unswitch (gcc::context *ctxt) 1056{ 1057 return new pass_tree_unswitch (ctxt); 1058} 1059 1060 1061