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 /* Returns true if the exit values of all loop phi nodes can be
 194    determined easily (i.e. that connect_loop_phis can determine them).  */
 195
 196 static bool
 197 easy_exit_values (struct loop *loop)
 198 {
 199   edge exit = single_exit (loop);
 200   edge latch = loop_latch_edge (loop);
 201   gphi_iterator psi;
 202
 203   /* Currently we regard the exit values as easy if they are the same
 204      as the value over the backedge.  Which is the case if the definition
 205      of the backedge value dominates the exit edge.  */
 206   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
 207     {
 208       gphi *phi = psi.phi ();
 209       tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
 210       basic_block bb;
 211       if (TREE_CODE (next) == SSA_NAME
 212           && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
 213           && !dominated_by_p (CDI_DOMINATORS, exit->src, bb))
 214         return false;
 215     }
 216
 217   return true;
 218 }
 219
 220 /* This function updates the SSA form after connect_loops made a new
 221    edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
 222    conditional).  I.e. the second loop can now be entered either
 223    via the original entry or via NEW_E, so the entry values of LOOP2
 224    phi nodes are either the original ones or those at the exit
 225    of LOOP1.  Insert new phi nodes in LOOP2 pre-header reflecting
 226    this.  The loops need to fulfill easy_exit_values().  */
 227
 228 static void
 229 connect_loop_phis (struct loop *loop1, struct loop *loop2, edge new_e)
 230 {
 231   basic_block rest = loop_preheader_edge (loop2)->src;
 232   gcc_assert (new_e->dest == rest);
 233   edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
 234
 235   edge firste = loop_preheader_edge (loop1);
 236   edge seconde = loop_preheader_edge (loop2);
 237   edge firstn = loop_latch_edge (loop1);
 238   gphi_iterator psi_first, psi_second;
 239   for (psi_first = gsi_start_phis (loop1->header),
 240        psi_second = gsi_start_phis (loop2->header);
 241        !gsi_end_p (psi_first);
 242        gsi_next (&psi_first), gsi_next (&psi_second))
 243     {
 244       tree init, next, new_init;
 245       use_operand_p op;
 246       gphi *phi_first = psi_first.phi ();
 247       gphi *phi_second = psi_second.phi ();
 248
 249       init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
 250       next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
 251       op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
 252       gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
 253
 254       /* Prefer using original variable as a base for the new ssa name.
 255          This is necessary for virtual ops, and useful in order to avoid
 256          losing debug info for real ops.  */
 257       if (TREE_CODE (next) == SSA_NAME
 258           && useless_type_conversion_p (TREE_TYPE (next),
 259                                         TREE_TYPE (init)))
 260         new_init = copy_ssa_name (next);
 261       else if (TREE_CODE (init) == SSA_NAME
 262                && useless_type_conversion_p (TREE_TYPE (init),
 263                                              TREE_TYPE (next)))
 264         new_init = copy_ssa_name (init);
 265       else if (useless_type_conversion_p (TREE_TYPE (next),
 266                                           TREE_TYPE (init)))
 267         new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
 268                                        "unrinittmp");
 269       else
 270         new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
 271                                        "unrinittmp");
 272
 273       gphi * newphi = create_phi_node (new_init, rest);
 274       add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
 275       add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
 276       SET_USE (op, new_init);
 277     }
 278 }
 279
 280 /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
 281    they are still equivalent and placed in two arms of a diamond, like so:
 282
 283                .------if (cond)------.
 284                v                     v
 285              pre1                   pre2
 286               |                      |
 287         .--->h1                     h2<----.
 288         |     |                      |     |
 289         |    ex1---.            .---ex2    |
 290         |    /     |            |     \    |
 291         '---l1     X            |     l2---'
 292                    |            |
 293                    |            |
 294                    '--->join<---'
 295
 296    This function transforms the program such that LOOP1 is conditionally
 297    falling through to LOOP2, or skipping it.  This is done by splitting
 298    the ex1->join edge at X in the diagram above, and inserting a condition
 299    whose one arm goes to pre2, resulting in this situation:
 300
 301                .------if (cond)------.
 302                v                     v
 303              pre1       .---------->pre2
 304               |         |            |
 305         .--->h1         |           h2<----.
 306         |     |         |            |     |
 307         |    ex1---.    |       .---ex2    |
 308         |    /     v    |       |     \    |
 309         '---l1   skip---'       |     l2---'
 310                    |            |
 311                    |            |
 312                    '--->join<---'
 313
 314
 315    The condition used is the exit condition of LOOP1, which effectively means
 316    that when the first loop exits (for whatever reason) but the real original
 317    exit expression is still false the second loop will be entered.
 318    The function returns the new edge cond->pre2.
 319
 320    This doesn't update the SSA form, see connect_loop_phis for that.  */
 321
 322 static edge
 323 connect_loops (struct loop *loop1, struct loop *loop2)
 324 {
 325   edge exit = single_exit (loop1);
 326   basic_block skip_bb = split_edge (exit);
 327   gcond *skip_stmt;
 328   gimple_stmt_iterator gsi;
 329   edge new_e, skip_e;
 330
 331   gimple *stmt = last_stmt (exit->src);
 332   skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
 333                                  gimple_cond_lhs (stmt),
 334                                  gimple_cond_rhs (stmt),
 335                                  NULL_TREE, NULL_TREE);
 336   gsi = gsi_last_bb (skip_bb);
 337   gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
 338
 339   skip_e = EDGE_SUCC (skip_bb, 0);
 340   skip_e->flags &= ~EDGE_FALLTHRU;
 341   new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
 342   if (exit->flags & EDGE_TRUE_VALUE)
 343     {
 344       skip_e->flags |= EDGE_TRUE_VALUE;
 345       new_e->flags |= EDGE_FALSE_VALUE;
 346     }
 347   else
 348     {
 349       skip_e->flags |= EDGE_FALSE_VALUE;
 350       new_e->flags |= EDGE_TRUE_VALUE;
 351     }
 352
 353   new_e->count = skip_bb->count;
 354   new_e->probability = PROB_LIKELY;
 355   new_e->count = apply_probability (skip_e->count, PROB_LIKELY);
 356   skip_e->count -= new_e->count;
 357   skip_e->probability = inverse_probability (PROB_LIKELY);
 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       enddiff = gimple_build (stmts, NEGATE_EXPR, sizetype, enddiff);
 437       newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
 438                                TREE_TYPE (guard_init),
 439                                guard_init, enddiff);
 440     }
 441   else
 442     newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
 443                              guard_init, enddiff);
 444
 445   /* Depending on the direction of the IVs the new bound for the first
 446      loop is the minimum or maximum of old bound and border.
 447      Also, if the guard condition isn't strictly less or greater,
 448      we need to adjust the bound.  */
 449   int addbound = 0;
 450   enum tree_code minmax;
 451   if (niter->cmp == LT_EXPR)
 452     {
 453       /* GT and LE are the same, inverted.  */
 454       if (guard_code == GT_EXPR || guard_code == LE_EXPR)
 455         addbound = -1;
 456       minmax = MIN_EXPR;
 457     }
 458   else
 459     {
 460       gcc_assert (niter->cmp == GT_EXPR);
 461       if (guard_code == GE_EXPR || guard_code == LT_EXPR)
 462         addbound = 1;
 463       minmax = MAX_EXPR;
 464     }
 465
 466   if (addbound)
 467     {
 468       tree type2 = TREE_TYPE (newbound);
 469       if (POINTER_TYPE_P (type2))
 470         type2 = sizetype;
 471       newbound = gimple_build (stmts,
 472                                POINTER_TYPE_P (TREE_TYPE (newbound))
 473                                ? POINTER_PLUS_EXPR : PLUS_EXPR,
 474                                TREE_TYPE (newbound),
 475                                newbound,
 476                                build_int_cst (type2, addbound));
 477     }
 478
 479   tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
 480                               border, newbound);
 481   return newend;
 482 }
 483
 484 /* Checks if LOOP contains an conditional block whose condition
 485    depends on which side in the iteration space it is, and if so
 486    splits the iteration space into two loops.  Returns true if the
 487    loop was split.  NITER must contain the iteration descriptor for the
 488    single exit of LOOP.  */
 489
 490 static bool
 491 split_loop (struct loop *loop1, struct tree_niter_desc *niter)
 492 {
 493   basic_block *bbs;
 494   unsigned i;
 495   bool changed = false;
 496   tree guard_iv;
 497   tree border;
 498   affine_iv iv;
 499
 500   bbs = get_loop_body (loop1);
 501
 502   /* Find a splitting opportunity.  */
 503   for (i = 0; i < loop1->num_nodes; i++)
 504     if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
 505       {
 506         /* Handling opposite steps is not implemented yet.  Neither
 507            is handling different step sizes.  */
 508         if ((tree_int_cst_sign_bit (iv.step)
 509              != tree_int_cst_sign_bit (niter->control.step))
 510             || !tree_int_cst_equal (iv.step, niter->control.step))
 511           continue;
 512
 513         /* Find a loop PHI node that defines guard_iv directly,
 514            or create one doing that.  */
 515         gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
 516         if (!phi)
 517           continue;
 518         gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i]));
 519         tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
 520                                                  loop_preheader_edge (loop1));
 521         enum tree_code guard_code = gimple_cond_code (guard_stmt);
 522
 523         /* Loop splitting is implemented by versioning the loop, placing
 524            the new loop after the old loop, make the first loop iterate
 525            as long as the conditional stays true (or false) and let the
 526            second (new) loop handle the rest of the iterations.
 527
 528            First we need to determine if the condition will start being true
 529            or false in the first loop.  */
 530         bool initial_true;
 531         switch (guard_code)
 532           {
 533             case LT_EXPR:
 534             case LE_EXPR:
 535               initial_true = !tree_int_cst_sign_bit (iv.step);
 536               break;
 537             case GT_EXPR:
 538             case GE_EXPR:
 539               initial_true = tree_int_cst_sign_bit (iv.step);
 540               break;
 541             default:
 542               gcc_unreachable ();
 543           }
 544
 545         /* Build a condition that will skip the first loop when the
 546            guard condition won't ever be true (or false).  */
 547         gimple_seq stmts2;
 548         border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
 549         if (stmts2)
 550           gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
 551                                             stmts2);
 552         tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
 553         if (!initial_true)
 554           cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
 555
 556         /* Now version the loop, placing loop2 after loop1 connecting
 557            them, and fix up SSA form for that.  */
 558         initialize_original_copy_tables ();
 559         basic_block cond_bb;
 560         struct loop *loop2 = loop_version (loop1, cond, &cond_bb,
 561                                            REG_BR_PROB_BASE, REG_BR_PROB_BASE,
 562                                            REG_BR_PROB_BASE, true);
 563         gcc_assert (loop2);
 564         update_ssa (TODO_update_ssa);
 565
 566         edge new_e = connect_loops (loop1, loop2);
 567         connect_loop_phis (loop1, loop2, new_e);
 568
 569         /* The iterations of the second loop is now already
 570            exactly those that the first loop didn't do, but the
 571            iteration space of the first loop is still the original one.
 572            Compute the new bound for the guarding IV and patch the
 573            loop exit to use it instead of original IV and bound.  */
 574         gimple_seq stmts = NULL;
 575         tree newend = compute_new_first_bound (&stmts, niter, border,
 576                                                guard_code, guard_init);
 577         if (stmts)
 578           gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
 579                                             stmts);
 580         tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
 581         patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
 582
 583         /* Finally patch out the two copies of the condition to be always
 584            true/false (or opposite).  */
 585         gcond *force_true = as_a<gcond *> (last_stmt (bbs[i]));
 586         gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i])));
 587         if (!initial_true)
 588           std::swap (force_true, force_false);
 589         gimple_cond_make_true (force_true);
 590         gimple_cond_make_false (force_false);
 591         update_stmt (force_true);
 592         update_stmt (force_false);
 593
 594         free_original_copy_tables ();
 595
 596         /* We destroyed LCSSA form above.  Eventually we might be able
 597            to fix it on the fly, for now simply punt and use the helper.  */
 598         rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
 599
 600         changed = true;
 601         if (dump_file && (dump_flags & TDF_DETAILS))
 602           fprintf (dump_file, ";; Loop split.\n");
 603
 604         /* Only deal with the first opportunity.  */
 605         break;
 606       }
 607
 608   free (bbs);
 609   return changed;
 610 }
 611
 612 /* Main entry point.  Perform loop splitting on all suitable loops.  */
 613
 614 static unsigned int
 615 tree_ssa_split_loops (void)
 616 {
 617   struct loop *loop;
 618   bool changed = false;
 619
 620   gcc_assert (scev_initialized_p ());
 621   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
 622     loop->aux = NULL;
 623
 624   /* Go through all loops starting from innermost.  */
 625   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 626     {
 627       struct tree_niter_desc niter;
 628       if (loop->aux)
 629         {
 630           /* If any of our inner loops was split, don't split us,
 631              and mark our containing loop as having had splits as well.  */
 632           loop_outer (loop)->aux = loop;
 633           continue;
 634         }
 635
 636       if (single_exit (loop)
 637           /* ??? We could handle non-empty latches when we split
 638              the latch edge (not the exit edge), and put the new
 639              exit condition in the new block.  OTOH this executes some
 640              code unconditionally that might have been skipped by the
 641              original exit before.  */
 642           && empty_block_p (loop->latch)
 643           && !optimize_loop_for_size_p (loop)
 644           && easy_exit_values (loop)
 645           && number_of_iterations_exit (loop, single_exit (loop), &niter,
 646                                         false, true)
 647           && niter.cmp != ERROR_MARK
 648           /* We can't yet handle loops controlled by a != predicate.  */
 649           && niter.cmp != NE_EXPR)
 650         {
 651           if (split_loop (loop, &niter))
 652             {
 653               /* Mark our containing loop as having had some split inner
 654                  loops.  */
 655               loop_outer (loop)->aux = loop;
 656               changed = true;
 657             }
 658         }
 659     }
 660
 661   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
 662     loop->aux = NULL;
 663
 664   if (changed)
 665     return TODO_cleanup_cfg;
 666   return 0;
 667 }
 668
 669 /* Loop splitting pass.  */
 670
 671 namespace {
 672
 673 const pass_data pass_data_loop_split =
 674 {
 675   GIMPLE_PASS, /* type */
 676   "lsplit", /* name */
 677   OPTGROUP_LOOP, /* optinfo_flags */
 678   TV_LOOP_SPLIT, /* tv_id */
 679   PROP_cfg, /* properties_required */
 680   0, /* properties_provided */
 681   0, /* properties_destroyed */
 682   0, /* todo_flags_start */
 683   0, /* todo_flags_finish */
 684 };
 685
 686 class pass_loop_split : public gimple_opt_pass
 687 {
 688 public:
 689   pass_loop_split (gcc::context *ctxt)
 690     : gimple_opt_pass (pass_data_loop_split, ctxt)
 691   {}
 692
 693   /* opt_pass methods: */
 694   virtual bool gate (function *) { return flag_split_loops != 0; }
 695   virtual unsigned int execute (function *);
 696
 697 }; // class pass_loop_split
 698
 699 unsigned int
 700 pass_loop_split::execute (function *fun)
 701 {
 702   if (number_of_loops (fun) <= 1)
 703     return 0;
 704
 705   return tree_ssa_split_loops ();
 706 }
 707
 708 } // anon namespace
 709
 710 gimple_opt_pass *
 711 make_pass_loop_split (gcc::context *ctxt)
 712 {
 713   return new pass_loop_split (ctxt);
 714 }