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