gcc/tree-ssa-loop-split.c

   1 /* Loop splitting.
   2    Copyright (C) 2015-2017 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->count = skip_bb->count;
 357   new_e->probability = PROB_LIKELY;
 358   new_e->count = apply_probability (skip_e->count, PROB_LIKELY);
 359   skip_e->count -= new_e->count;
 360   skip_e->probability = inverse_probability (PROB_LIKELY);
 361
 362   return new_e;
 363 }
 364
 365 /* This returns the new bound for iterations given the original iteration
 366    space in NITER, an arbitrary new bound BORDER, assumed to be some
 367    comparison value with a different IV, the initial value GUARD_INIT of
 368    that other IV, and the comparison code GUARD_CODE that compares
 369    that other IV with BORDER.  We return an SSA name, and place any
 370    necessary statements for that computation into *STMTS.
 371
 372    For example for such a loop:
 373
 374      for (i = beg, j = guard_init; i < end; i++, j++)
 375        if (j < border)  // this is supposed to be true/false
 376          ...
 377
 378    we want to return a new bound (on j) that makes the loop iterate
 379    as long as the condition j < border stays true.  We also don't want
 380    to iterate more often than the original loop, so we have to introduce
 381    some cut-off as well (via min/max), effectively resulting in:
 382
 383      newend = min (end+guard_init-beg, border)
 384      for (i = beg; j = guard_init; j < newend; i++, j++)
 385        if (j < c)
 386          ...
 387
 388    Depending on the direction of the IVs and if the exit tests
 389    are strict or non-strict we need to use MIN or MAX,
 390    and add or subtract 1.  This routine computes newend above.  */
 391
 392 static tree
 393 compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter,
 394                          tree border,
 395                          enum tree_code guard_code, tree guard_init)
 396 {
 397   /* The niter structure contains the after-increment IV, we need
 398      the loop-enter base, so subtract STEP once.  */
 399   tree controlbase = force_gimple_operand (niter->control.base,
 400                                            stmts, true, NULL_TREE);
 401   tree controlstep = niter->control.step;
 402   tree enddiff;
 403   if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
 404     {
 405       controlstep = gimple_build (stmts, NEGATE_EXPR,
 406                                   TREE_TYPE (controlstep), controlstep);
 407       enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
 408                               TREE_TYPE (controlbase),
 409                               controlbase, controlstep);
 410     }
 411   else
 412     enddiff = gimple_build (stmts, MINUS_EXPR,
 413                             TREE_TYPE (controlbase),
 414                             controlbase, controlstep);
 415
 416   /* Compute end-beg.  */
 417   gimple_seq stmts2;
 418   tree end = force_gimple_operand (niter->bound, &stmts2,
 419                                         true, NULL_TREE);
 420   gimple_seq_add_seq_without_update (stmts, stmts2);
 421   if (POINTER_TYPE_P (TREE_TYPE (enddiff)))
 422     {
 423       tree tem = gimple_convert (stmts, sizetype, enddiff);
 424       tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem);
 425       enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
 426                               TREE_TYPE (enddiff),
 427                               end, tem);
 428     }
 429   else
 430     enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
 431                             end, enddiff);
 432
 433   /* Compute guard_init + (end-beg).  */
 434   tree newbound;
 435   enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
 436   if (POINTER_TYPE_P (TREE_TYPE (guard_init)))
 437     {
 438       enddiff = gimple_convert (stmts, sizetype, enddiff);
 439       enddiff = gimple_build (stmts, NEGATE_EXPR, sizetype, enddiff);
 440       newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
 441                                TREE_TYPE (guard_init),
 442                                guard_init, enddiff);
 443     }
 444   else
 445     newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
 446                              guard_init, enddiff);
 447
 448   /* Depending on the direction of the IVs the new bound for the first
 449      loop is the minimum or maximum of old bound and border.
 450      Also, if the guard condition isn't strictly less or greater,
 451      we need to adjust the bound.  */
 452   int addbound = 0;
 453   enum tree_code minmax;
 454   if (niter->cmp == LT_EXPR)
 455     {
 456       /* GT and LE are the same, inverted.  */
 457       if (guard_code == GT_EXPR || guard_code == LE_EXPR)
 458         addbound = -1;
 459       minmax = MIN_EXPR;
 460     }
 461   else
 462     {
 463       gcc_assert (niter->cmp == GT_EXPR);
 464       if (guard_code == GE_EXPR || guard_code == LT_EXPR)
 465         addbound = 1;
 466       minmax = MAX_EXPR;
 467     }
 468
 469   if (addbound)
 470     {
 471       tree type2 = TREE_TYPE (newbound);
 472       if (POINTER_TYPE_P (type2))
 473         type2 = sizetype;
 474       newbound = gimple_build (stmts,
 475                                POINTER_TYPE_P (TREE_TYPE (newbound))
 476                                ? POINTER_PLUS_EXPR : PLUS_EXPR,
 477                                TREE_TYPE (newbound),
 478                                newbound,
 479                                build_int_cst (type2, addbound));
 480     }
 481
 482   tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
 483                               border, newbound);
 484   return newend;
 485 }
 486
 487 /* Checks if LOOP contains an conditional block whose condition
 488    depends on which side in the iteration space it is, and if so
 489    splits the iteration space into two loops.  Returns true if the
 490    loop was split.  NITER must contain the iteration descriptor for the
 491    single exit of LOOP.  */
 492
 493 static bool
 494 split_loop (struct loop *loop1, struct tree_niter_desc *niter)
 495 {
 496   basic_block *bbs;
 497   unsigned i;
 498   bool changed = false;
 499   tree guard_iv;
 500   tree border = NULL_TREE;
 501   affine_iv iv;
 502
 503   bbs = get_loop_body (loop1);
 504
 505   /* Find a splitting opportunity.  */
 506   for (i = 0; i < loop1->num_nodes; i++)
 507     if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
 508       {
 509         /* Handling opposite steps is not implemented yet.  Neither
 510            is handling different step sizes.  */
 511         if ((tree_int_cst_sign_bit (iv.step)
 512              != tree_int_cst_sign_bit (niter->control.step))
 513             || !tree_int_cst_equal (iv.step, niter->control.step))
 514           continue;
 515
 516         /* Find a loop PHI node that defines guard_iv directly,
 517            or create one doing that.  */
 518         gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
 519         if (!phi)
 520           continue;
 521         gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i]));
 522         tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
 523                                                  loop_preheader_edge (loop1));
 524         enum tree_code guard_code = gimple_cond_code (guard_stmt);
 525
 526         /* Loop splitting is implemented by versioning the loop, placing
 527            the new loop after the old loop, make the first loop iterate
 528            as long as the conditional stays true (or false) and let the
 529            second (new) loop handle the rest of the iterations.
 530
 531            First we need to determine if the condition will start being true
 532            or false in the first loop.  */
 533         bool initial_true;
 534         switch (guard_code)
 535           {
 536             case LT_EXPR:
 537             case LE_EXPR:
 538               initial_true = !tree_int_cst_sign_bit (iv.step);
 539               break;
 540             case GT_EXPR:
 541             case GE_EXPR:
 542               initial_true = tree_int_cst_sign_bit (iv.step);
 543               break;
 544             default:
 545               gcc_unreachable ();
 546           }
 547
 548         /* Build a condition that will skip the first loop when the
 549            guard condition won't ever be true (or false).  */
 550         gimple_seq stmts2;
 551         border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
 552         if (stmts2)
 553           gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
 554                                             stmts2);
 555         tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
 556         if (!initial_true)
 557           cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
 558
 559         /* Now version the loop, placing loop2 after loop1 connecting
 560            them, and fix up SSA form for that.  */
 561         initialize_original_copy_tables ();
 562         basic_block cond_bb;
 563         struct loop *loop2 = loop_version (loop1, cond, &cond_bb,
 564                                            REG_BR_PROB_BASE, REG_BR_PROB_BASE,
 565                                            REG_BR_PROB_BASE, REG_BR_PROB_BASE,
 566                                            true);
 567         gcc_assert (loop2);
 568         update_ssa (TODO_update_ssa);
 569
 570         edge new_e = connect_loops (loop1, loop2);
 571         connect_loop_phis (loop1, loop2, new_e);
 572
 573         /* The iterations of the second loop is now already
 574            exactly those that the first loop didn't do, but the
 575            iteration space of the first loop is still the original one.
 576            Compute the new bound for the guarding IV and patch the
 577            loop exit to use it instead of original IV and bound.  */
 578         gimple_seq stmts = NULL;
 579         tree newend = compute_new_first_bound (&stmts, niter, border,
 580                                                guard_code, guard_init);
 581         if (stmts)
 582           gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
 583                                             stmts);
 584         tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
 585         patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
 586
 587         /* Finally patch out the two copies of the condition to be always
 588            true/false (or opposite).  */
 589         gcond *force_true = as_a<gcond *> (last_stmt (bbs[i]));
 590         gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i])));
 591         if (!initial_true)
 592           std::swap (force_true, force_false);
 593         gimple_cond_make_true (force_true);
 594         gimple_cond_make_false (force_false);
 595         update_stmt (force_true);
 596         update_stmt (force_false);
 597
 598         free_original_copy_tables ();
 599
 600         /* We destroyed LCSSA form above.  Eventually we might be able
 601            to fix it on the fly, for now simply punt and use the helper.  */
 602         rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
 603
 604         changed = true;
 605         if (dump_file && (dump_flags & TDF_DETAILS))
 606           fprintf (dump_file, ";; Loop split.\n");
 607
 608         /* Only deal with the first opportunity.  */
 609         break;
 610       }
 611
 612   free (bbs);
 613   return changed;
 614 }
 615
 616 /* Main entry point.  Perform loop splitting on all suitable loops.  */
 617
 618 static unsigned int
 619 tree_ssa_split_loops (void)
 620 {
 621   struct loop *loop;
 622   bool changed = false;
 623
 624   gcc_assert (scev_initialized_p ());
 625   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
 626     loop->aux = NULL;
 627
 628   /* Go through all loops starting from innermost.  */
 629   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 630     {
 631       struct tree_niter_desc niter;
 632       if (loop->aux)
 633         {
 634           /* If any of our inner loops was split, don't split us,
 635              and mark our containing loop as having had splits as well.  */
 636           loop_outer (loop)->aux = loop;
 637           continue;
 638         }
 639
 640       if (single_exit (loop)
 641           /* ??? We could handle non-empty latches when we split
 642              the latch edge (not the exit edge), and put the new
 643              exit condition in the new block.  OTOH this executes some
 644              code unconditionally that might have been skipped by the
 645              original exit before.  */
 646           && empty_block_p (loop->latch)
 647           && !optimize_loop_for_size_p (loop)
 648           && easy_exit_values (loop)
 649           && number_of_iterations_exit (loop, single_exit (loop), &niter,
 650                                         false, true)
 651           && niter.cmp != ERROR_MARK
 652           /* We can't yet handle loops controlled by a != predicate.  */
 653           && niter.cmp != NE_EXPR)
 654         {
 655           if (split_loop (loop, &niter))
 656             {
 657               /* Mark our containing loop as having had some split inner
 658                  loops.  */
 659               loop_outer (loop)->aux = loop;
 660               changed = true;
 661             }
 662         }
 663     }
 664
 665   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
 666     loop->aux = NULL;
 667
 668   if (changed)
 669     return TODO_cleanup_cfg;
 670   return 0;
 671 }
 672
 673 /* Loop splitting pass.  */
 674
 675 namespace {
 676
 677 const pass_data pass_data_loop_split =
 678 {
 679   GIMPLE_PASS, /* type */
 680   "lsplit", /* name */
 681   OPTGROUP_LOOP, /* optinfo_flags */
 682   TV_LOOP_SPLIT, /* tv_id */
 683   PROP_cfg, /* properties_required */
 684   0, /* properties_provided */
 685   0, /* properties_destroyed */
 686   0, /* todo_flags_start */
 687   0, /* todo_flags_finish */
 688 };
 689
 690 class pass_loop_split : public gimple_opt_pass
 691 {
 692 public:
 693   pass_loop_split (gcc::context *ctxt)
 694     : gimple_opt_pass (pass_data_loop_split, ctxt)
 695   {}
 696
 697   /* opt_pass methods: */
 698   virtual bool gate (function *) { return flag_split_loops != 0; }
 699   virtual unsigned int execute (function *);
 700
 701 }; // class pass_loop_split
 702
 703 unsigned int
 704 pass_loop_split::execute (function *fun)
 705 {
 706   if (number_of_loops (fun) <= 1)
 707     return 0;
 708
 709   return tree_ssa_split_loops ();
 710 }
 711
 712 } // anon namespace
 713
 714 gimple_opt_pass *
 715 make_pass_loop_split (gcc::context *ctxt)
 716 {
 717   return new pass_loop_split (ctxt);
 718 }