1 /* Loop splitting. 2 Copyright (C) 2015-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along 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 "tree-cfg.h" 30 #include "tree-ssa.h" 31 #include "tree-ssa-loop-niter.h" 32 #include "tree-ssa-loop.h" 33 #include "tree-ssa-loop-manip.h" 34 #include "tree-into-ssa.h" 35 #include "cfgloop.h" 36 #include "tree-scalar-evolution.h" 37 #include "gimple-iterator.h" 38 #include "gimple-pretty-print.h" 39 #include "cfghooks.h" 40 #include "gimple-fold.h" 41 #include "gimplify-me.h" 42 43 /* This file implements loop splitting, i.e. transformation of loops like 44 45 for (i = 0; i < 100; i++) 46 { 47 if (i < 50) 48 A; 49 else 50 B; 51 } 52 53 into: 54 55 for (i = 0; i < 50; i++) 56 { 57 A; 58 } 59 for (; i < 100; i++) 60 { 61 B; 62 } 63 64 */ 65 66 /* Return true when BB inside LOOP is a potential iteration space 67 split point, i.e. ends with a condition like "IV < comp", which 68 is true on one side of the iteration space and false on the other, 69 and the split point can be computed. If so, also return the border 70 point in *BORDER and the comparison induction variable in IV. */ 71 72 static tree 73 split_at_bb_p (struct loop *loop, basic_block bb, tree *border, affine_iv *iv) 74 { 75 gimple *last; 76 gcond *stmt; 77 affine_iv iv2; 78 79 /* BB must end in a simple conditional jump. */ 80 last = last_stmt (bb); 81 if (!last || gimple_code (last) != GIMPLE_COND) 82 return NULL_TREE; 83 stmt = as_a <gcond *> (last); 84 85 enum tree_code code = gimple_cond_code (stmt); 86 87 /* Only handle relational comparisons, for equality and non-equality 88 we'd have to split the loop into two loops and a middle statement. */ 89 switch (code) 90 { 91 case LT_EXPR: 92 case LE_EXPR: 93 case GT_EXPR: 94 case GE_EXPR: 95 break; 96 default: 97 return NULL_TREE; 98 } 99 100 if (loop_exits_from_bb_p (loop, bb)) 101 return NULL_TREE; 102 103 tree op0 = gimple_cond_lhs (stmt); 104 tree op1 = gimple_cond_rhs (stmt); 105 struct loop *useloop = loop_containing_stmt (stmt); 106 107 if (!simple_iv (loop, useloop, op0, iv, false)) 108 return NULL_TREE; 109 if (!simple_iv (loop, useloop, op1, &iv2, false)) 110 return NULL_TREE; 111 112 /* Make it so that the first argument of the condition is 113 the looping one. */ 114 if (!integer_zerop (iv2.step)) 115 { 116 std::swap (op0, op1); 117 std::swap (*iv, iv2); 118 code = swap_tree_comparison (code); 119 gimple_cond_set_condition (stmt, code, op0, op1); 120 update_stmt (stmt); 121 } 122 else if (integer_zerop (iv->step)) 123 return NULL_TREE; 124 if (!integer_zerop (iv2.step)) 125 return NULL_TREE; 126 if (!iv->no_overflow) 127 return NULL_TREE; 128 129 if (dump_file && (dump_flags & TDF_DETAILS)) 130 { 131 fprintf (dump_file, "Found potential split point: "); 132 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 133 fprintf (dump_file, " { "); 134 print_generic_expr (dump_file, iv->base, TDF_SLIM); 135 fprintf (dump_file, " + I*"); 136 print_generic_expr (dump_file, iv->step, TDF_SLIM); 137 fprintf (dump_file, " } %s ", get_tree_code_name (code)); 138 print_generic_expr (dump_file, iv2.base, TDF_SLIM); 139 fprintf (dump_file, "\n"); 140 } 141 142 *border = iv2.base; 143 return op0; 144 } 145 146 /* Given a GUARD conditional stmt inside LOOP, which we want to make always 147 true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL 148 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop 149 exit test statement to loop back only if the GUARD statement will 150 also be true/false in the next iteration. */ 151 152 static void 153 patch_loop_exit (struct loop *loop, gcond *guard, tree nextval, tree newbound, 154 bool initial_true) 155 { 156 edge exit = single_exit (loop); 157 gcond *stmt = as_a <gcond *> (last_stmt (exit->src)); 158 gimple_cond_set_condition (stmt, gimple_cond_code (guard), 159 nextval, newbound); 160 update_stmt (stmt); 161 162 edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit); 163 164 exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 165 stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 166 167 if (initial_true) 168 { 169 exit->flags |= EDGE_FALSE_VALUE; 170 stay->flags |= EDGE_TRUE_VALUE; 171 } 172 else 173 { 174 exit->flags |= EDGE_TRUE_VALUE; 175 stay->flags |= EDGE_FALSE_VALUE; 176 } 177 } 178 179 /* Give an induction variable GUARD_IV, and its affine descriptor IV, 180 find the loop phi node in LOOP defining it directly, or create 181 such phi node. Return that phi node. */ 182 183 static gphi * 184 find_or_create_guard_phi (struct loop *loop, tree guard_iv, affine_iv * /*iv*/) 185 { 186 gimple *def = SSA_NAME_DEF_STMT (guard_iv); 187 gphi *phi; 188 if ((phi = dyn_cast <gphi *> (def)) 189 && gimple_bb (phi) == loop->header) 190 return phi; 191 192 /* XXX Create the PHI instead. */ 193 return NULL; 194 } 195 196 /* Returns true if the exit values of all loop phi nodes can be 197 determined easily (i.e. that connect_loop_phis can determine them). */ 198 199 static bool 200 easy_exit_values (struct loop *loop) 201 { 202 edge exit = single_exit (loop); 203 edge latch = loop_latch_edge (loop); 204 gphi_iterator psi; 205 206 /* Currently we regard the exit values as easy if they are the same 207 as the value over the backedge. Which is the case if the definition 208 of the backedge value dominates the exit edge. */ 209 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) 210 { 211 gphi *phi = psi.phi (); 212 tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch); 213 basic_block bb; 214 if (TREE_CODE (next) == SSA_NAME 215 && (bb = gimple_bb (SSA_NAME_DEF_STMT (next))) 216 && !dominated_by_p (CDI_DOMINATORS, exit->src, bb)) 217 return false; 218 } 219 220 return true; 221 } 222 223 /* This function updates the SSA form after connect_loops made a new 224 edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate 225 conditional). I.e. the second loop can now be entered either 226 via the original entry or via NEW_E, so the entry values of LOOP2 227 phi nodes are either the original ones or those at the exit 228 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting 229 this. The loops need to fulfill easy_exit_values(). */ 230 231 static void 232 connect_loop_phis (struct loop *loop1, struct loop *loop2, edge new_e) 233 { 234 basic_block rest = loop_preheader_edge (loop2)->src; 235 gcc_assert (new_e->dest == rest); 236 edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e); 237 238 edge firste = loop_preheader_edge (loop1); 239 edge seconde = loop_preheader_edge (loop2); 240 edge firstn = loop_latch_edge (loop1); 241 gphi_iterator psi_first, psi_second; 242 for (psi_first = gsi_start_phis (loop1->header), 243 psi_second = gsi_start_phis (loop2->header); 244 !gsi_end_p (psi_first); 245 gsi_next (&psi_first), gsi_next (&psi_second)) 246 { 247 tree init, next, new_init; 248 use_operand_p op; 249 gphi *phi_first = psi_first.phi (); 250 gphi *phi_second = psi_second.phi (); 251 252 init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste); 253 next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn); 254 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde); 255 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); 256 257 /* Prefer using original variable as a base for the new ssa name. 258 This is necessary for virtual ops, and useful in order to avoid 259 losing debug info for real ops. */ 260 if (TREE_CODE (next) == SSA_NAME 261 && useless_type_conversion_p (TREE_TYPE (next), 262 TREE_TYPE (init))) 263 new_init = copy_ssa_name (next); 264 else if (TREE_CODE (init) == SSA_NAME 265 && useless_type_conversion_p (TREE_TYPE (init), 266 TREE_TYPE (next))) 267 new_init = copy_ssa_name (init); 268 else if (useless_type_conversion_p (TREE_TYPE (next), 269 TREE_TYPE (init))) 270 new_init = make_temp_ssa_name (TREE_TYPE (next), NULL, 271 "unrinittmp"); 272 else 273 new_init = make_temp_ssa_name (TREE_TYPE (init), NULL, 274 "unrinittmp"); 275 276 gphi * newphi = create_phi_node (new_init, rest); 277 add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION); 278 add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION); 279 SET_USE (op, new_init); 280 } 281 } 282 283 /* The two loops LOOP1 and LOOP2 were just created by loop versioning, 284 they are still equivalent and placed in two arms of a diamond, like so: 285 286 .------if (cond)------. 287 v v 288 pre1 pre2 289 | | 290 .--->h1 h2<----. 291 | | | | 292 | ex1---. .---ex2 | 293 | / | | \ | 294 '---l1 X | l2---' 295 | | 296 | | 297 '--->join<---' 298 299 This function transforms the program such that LOOP1 is conditionally 300 falling through to LOOP2, or skipping it. This is done by splitting 301 the ex1->join edge at X in the diagram above, and inserting a condition 302 whose one arm goes to pre2, resulting in this situation: 303 304 .------if (cond)------. 305 v v 306 pre1 .---------->pre2 307 | | | 308 .--->h1 | h2<----. 309 | | | | | 310 | ex1---. | .---ex2 | 311 | / v | | \ | 312 '---l1 skip---' | l2---' 313 | | 314 | | 315 '--->join<---' 316 317 318 The condition used is the exit condition of LOOP1, which effectively means 319 that when the first loop exits (for whatever reason) but the real original 320 exit expression is still false the second loop will be entered. 321 The function returns the new edge cond->pre2. 322 323 This doesn't update the SSA form, see connect_loop_phis for that. */ 324 325 static edge 326 connect_loops (struct loop *loop1, struct loop *loop2) 327 { 328 edge exit = single_exit (loop1); 329 basic_block skip_bb = split_edge (exit); 330 gcond *skip_stmt; 331 gimple_stmt_iterator gsi; 332 edge new_e, skip_e; 333 334 gimple *stmt = last_stmt (exit->src); 335 skip_stmt = gimple_build_cond (gimple_cond_code (stmt), 336 gimple_cond_lhs (stmt), 337 gimple_cond_rhs (stmt), 338 NULL_TREE, NULL_TREE); 339 gsi = gsi_last_bb (skip_bb); 340 gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT); 341 342 skip_e = EDGE_SUCC (skip_bb, 0); 343 skip_e->flags &= ~EDGE_FALLTHRU; 344 new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0); 345 if (exit->flags & EDGE_TRUE_VALUE) 346 { 347 skip_e->flags |= EDGE_TRUE_VALUE; 348 new_e->flags |= EDGE_FALSE_VALUE; 349 } 350 else 351 { 352 skip_e->flags |= EDGE_FALSE_VALUE; 353 new_e->flags |= EDGE_TRUE_VALUE; 354 } 355 356 new_e->probability = profile_probability::likely (); 357 skip_e->probability = new_e->probability.invert (); 358 359 return new_e; 360 } 361 362 /* This returns the new bound for iterations given the original iteration 363 space in NITER, an arbitrary new bound BORDER, assumed to be some 364 comparison value with a different IV, the initial value GUARD_INIT of 365 that other IV, and the comparison code GUARD_CODE that compares 366 that other IV with BORDER. We return an SSA name, and place any 367 necessary statements for that computation into *STMTS. 368 369 For example for such a loop: 370 371 for (i = beg, j = guard_init; i < end; i++, j++) 372 if (j < border) // this is supposed to be true/false 373 ... 374 375 we want to return a new bound (on j) that makes the loop iterate 376 as long as the condition j < border stays true. We also don't want 377 to iterate more often than the original loop, so we have to introduce 378 some cut-off as well (via min/max), effectively resulting in: 379 380 newend = min (end+guard_init-beg, border) 381 for (i = beg; j = guard_init; j < newend; i++, j++) 382 if (j < c) 383 ... 384 385 Depending on the direction of the IVs and if the exit tests 386 are strict or non-strict we need to use MIN or MAX, 387 and add or subtract 1. This routine computes newend above. */ 388 389 static tree 390 compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter, 391 tree border, 392 enum tree_code guard_code, tree guard_init) 393 { 394 /* The niter structure contains the after-increment IV, we need 395 the loop-enter base, so subtract STEP once. */ 396 tree controlbase = force_gimple_operand (niter->control.base, 397 stmts, true, NULL_TREE); 398 tree controlstep = niter->control.step; 399 tree enddiff; 400 if (POINTER_TYPE_P (TREE_TYPE (controlbase))) 401 { 402 controlstep = gimple_build (stmts, NEGATE_EXPR, 403 TREE_TYPE (controlstep), controlstep); 404 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR, 405 TREE_TYPE (controlbase), 406 controlbase, controlstep); 407 } 408 else 409 enddiff = gimple_build (stmts, MINUS_EXPR, 410 TREE_TYPE (controlbase), 411 controlbase, controlstep); 412 413 /* Compute end-beg. */ 414 gimple_seq stmts2; 415 tree end = force_gimple_operand (niter->bound, &stmts2, 416 true, NULL_TREE); 417 gimple_seq_add_seq_without_update (stmts, stmts2); 418 if (POINTER_TYPE_P (TREE_TYPE (enddiff))) 419 { 420 tree tem = gimple_convert (stmts, sizetype, enddiff); 421 tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem); 422 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR, 423 TREE_TYPE (enddiff), 424 end, tem); 425 } 426 else 427 enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff), 428 end, enddiff); 429 430 /* Compute guard_init + (end-beg). */ 431 tree newbound; 432 enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff); 433 if (POINTER_TYPE_P (TREE_TYPE (guard_init))) 434 { 435 enddiff = gimple_convert (stmts, sizetype, enddiff); 436 newbound = gimple_build (stmts, POINTER_PLUS_EXPR, 437 TREE_TYPE (guard_init), 438 guard_init, enddiff); 439 } 440 else 441 newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init), 442 guard_init, enddiff); 443 444 /* Depending on the direction of the IVs the new bound for the first 445 loop is the minimum or maximum of old bound and border. 446 Also, if the guard condition isn't strictly less or greater, 447 we need to adjust the bound. */ 448 int addbound = 0; 449 enum tree_code minmax; 450 if (niter->cmp == LT_EXPR) 451 { 452 /* GT and LE are the same, inverted. */ 453 if (guard_code == GT_EXPR || guard_code == LE_EXPR) 454 addbound = -1; 455 minmax = MIN_EXPR; 456 } 457 else 458 { 459 gcc_assert (niter->cmp == GT_EXPR); 460 if (guard_code == GE_EXPR || guard_code == LT_EXPR) 461 addbound = 1; 462 minmax = MAX_EXPR; 463 } 464 465 if (addbound) 466 { 467 tree type2 = TREE_TYPE (newbound); 468 if (POINTER_TYPE_P (type2)) 469 type2 = sizetype; 470 newbound = gimple_build (stmts, 471 POINTER_TYPE_P (TREE_TYPE (newbound)) 472 ? POINTER_PLUS_EXPR : PLUS_EXPR, 473 TREE_TYPE (newbound), 474 newbound, 475 build_int_cst (type2, addbound)); 476 } 477 478 tree newend = gimple_build (stmts, minmax, TREE_TYPE (border), 479 border, newbound); 480 return newend; 481 } 482 483 /* Checks if LOOP contains an conditional block whose condition 484 depends on which side in the iteration space it is, and if so 485 splits the iteration space into two loops. Returns true if the 486 loop was split. NITER must contain the iteration descriptor for the 487 single exit of LOOP. */ 488 489 static bool 490 split_loop (struct loop *loop1, struct tree_niter_desc *niter) 491 { 492 basic_block *bbs; 493 unsigned i; 494 bool changed = false; 495 tree guard_iv; 496 tree border = NULL_TREE; 497 affine_iv iv; 498 499 bbs = get_loop_body (loop1); 500 501 /* Find a splitting opportunity. */ 502 for (i = 0; i < loop1->num_nodes; i++) 503 if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv))) 504 { 505 /* Handling opposite steps is not implemented yet. Neither 506 is handling different step sizes. */ 507 if ((tree_int_cst_sign_bit (iv.step) 508 != tree_int_cst_sign_bit (niter->control.step)) 509 || !tree_int_cst_equal (iv.step, niter->control.step)) 510 continue; 511 512 /* Find a loop PHI node that defines guard_iv directly, 513 or create one doing that. */ 514 gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv); 515 if (!phi) 516 continue; 517 gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i])); 518 tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi, 519 loop_preheader_edge (loop1)); 520 enum tree_code guard_code = gimple_cond_code (guard_stmt); 521 522 /* Loop splitting is implemented by versioning the loop, placing 523 the new loop after the old loop, make the first loop iterate 524 as long as the conditional stays true (or false) and let the 525 second (new) loop handle the rest of the iterations. 526 527 First we need to determine if the condition will start being true 528 or false in the first loop. */ 529 bool initial_true; 530 switch (guard_code) 531 { 532 case LT_EXPR: 533 case LE_EXPR: 534 initial_true = !tree_int_cst_sign_bit (iv.step); 535 break; 536 case GT_EXPR: 537 case GE_EXPR: 538 initial_true = tree_int_cst_sign_bit (iv.step); 539 break; 540 default: 541 gcc_unreachable (); 542 } 543 544 /* Build a condition that will skip the first loop when the 545 guard condition won't ever be true (or false). */ 546 gimple_seq stmts2; 547 border = force_gimple_operand (border, &stmts2, true, NULL_TREE); 548 if (stmts2) 549 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), 550 stmts2); 551 tree cond = build2 (guard_code, boolean_type_node, guard_init, border); 552 if (!initial_true) 553 cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); 554 555 /* Now version the loop, placing loop2 after loop1 connecting 556 them, and fix up SSA form for that. */ 557 initialize_original_copy_tables (); 558 basic_block cond_bb; 559 560 struct loop *loop2 = loop_version (loop1, cond, &cond_bb, 561 profile_probability::always (), 562 profile_probability::always (), 563 profile_probability::always (), 564 profile_probability::always (), 565 true); 566 gcc_assert (loop2); 567 update_ssa (TODO_update_ssa); 568 569 edge new_e = connect_loops (loop1, loop2); 570 connect_loop_phis (loop1, loop2, new_e); 571 572 /* The iterations of the second loop is now already 573 exactly those that the first loop didn't do, but the 574 iteration space of the first loop is still the original one. 575 Compute the new bound for the guarding IV and patch the 576 loop exit to use it instead of original IV and bound. */ 577 gimple_seq stmts = NULL; 578 tree newend = compute_new_first_bound (&stmts, niter, border, 579 guard_code, guard_init); 580 if (stmts) 581 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), 582 stmts); 583 tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); 584 patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true); 585 586 /* Finally patch out the two copies of the condition to be always 587 true/false (or opposite). */ 588 gcond *force_true = as_a<gcond *> (last_stmt (bbs[i])); 589 gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i]))); 590 if (!initial_true) 591 std::swap (force_true, force_false); 592 gimple_cond_make_true (force_true); 593 gimple_cond_make_false (force_false); 594 update_stmt (force_true); 595 update_stmt (force_false); 596 597 free_original_copy_tables (); 598 599 /* We destroyed LCSSA form above. Eventually we might be able 600 to fix it on the fly, for now simply punt and use the helper. */ 601 rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1); 602 603 changed = true; 604 if (dump_file && (dump_flags & TDF_DETAILS)) 605 fprintf (dump_file, ";; Loop split.\n"); 606 607 /* Only deal with the first opportunity. */ 608 break; 609 } 610 611 free (bbs); 612 return changed; 613 } 614 615 /* Main entry point. Perform loop splitting on all suitable loops. */ 616 617 static unsigned int 618 tree_ssa_split_loops (void) 619 { 620 struct loop *loop; 621 bool changed = false; 622 623 gcc_assert (scev_initialized_p ()); 624 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) 625 loop->aux = NULL; 626 627 /* Go through all loops starting from innermost. */ 628 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) 629 { 630 struct tree_niter_desc niter; 631 if (loop->aux) 632 { 633 /* If any of our inner loops was split, don't split us, 634 and mark our containing loop as having had splits as well. */ 635 loop_outer (loop)->aux = loop; 636 continue; 637 } 638 639 if (single_exit (loop) 640 /* ??? We could handle non-empty latches when we split 641 the latch edge (not the exit edge), and put the new 642 exit condition in the new block. OTOH this executes some 643 code unconditionally that might have been skipped by the 644 original exit before. */ 645 && empty_block_p (loop->latch) 646 && !optimize_loop_for_size_p (loop) 647 && easy_exit_values (loop) 648 && number_of_iterations_exit (loop, single_exit (loop), &niter, 649 false, true) 650 && niter.cmp != ERROR_MARK 651 /* We can't yet handle loops controlled by a != predicate. */ 652 && niter.cmp != NE_EXPR) 653 { 654 if (split_loop (loop, &niter)) 655 { 656 /* Mark our containing loop as having had some split inner 657 loops. */ 658 loop_outer (loop)->aux = loop; 659 changed = true; 660 } 661 } 662 } 663 664 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) 665 loop->aux = NULL; 666 667 if (changed) 668 return TODO_cleanup_cfg; 669 return 0; 670 } 671 672 /* Loop splitting pass. */ 673 674 namespace { 675 676 const pass_data pass_data_loop_split = 677 { 678 GIMPLE_PASS, /* type */ 679 "lsplit", /* name */ 680 OPTGROUP_LOOP, /* optinfo_flags */ 681 TV_LOOP_SPLIT, /* tv_id */ 682 PROP_cfg, /* properties_required */ 683 0, /* properties_provided */ 684 0, /* properties_destroyed */ 685 0, /* todo_flags_start */ 686 0, /* todo_flags_finish */ 687 }; 688 689 class pass_loop_split : public gimple_opt_pass 690 { 691 public: 692 pass_loop_split (gcc::context *ctxt) 693 : gimple_opt_pass (pass_data_loop_split, ctxt) 694 {} 695 696 /* opt_pass methods: */ 697 virtual bool gate (function *) { return flag_split_loops != 0; } 698 virtual unsigned int execute (function *); 699 700 }; // class pass_loop_split 701 702 unsigned int 703 pass_loop_split::execute (function *fun) 704 { 705 if (number_of_loops (fun) <= 1) 706 return 0; 707 708 return tree_ssa_split_loops (); 709 } 710 711 } // anon namespace 712 713 gimple_opt_pass * 714 make_pass_loop_split (gcc::context *ctxt) 715 { 716 return new pass_loop_split (ctxt); 717 } 718