gcc/tree-ssa-loop-split.c

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