gcc/tree-ssa-loop-split.c

   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 }