ada: Fix wrong resolution for hidden discriminant in predicate
[official-gcc.git] / gcc / tree-ssa-loop-split.cc
blobb41b5e614c2177be190fb8553d0daa6cab2a8e4b
1 /* Loop splitting.
2 Copyright (C) 2015-2023 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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 "tree-inline.h"
36 #include "tree-cfgcleanup.h"
37 #include "cfgloop.h"
38 #include "tree-scalar-evolution.h"
39 #include "gimple-iterator.h"
40 #include "gimple-pretty-print.h"
41 #include "cfghooks.h"
42 #include "gimple-fold.h"
43 #include "gimplify-me.h"
45 /* This file implements two kinds of loop splitting.
47 One transformation of loops like:
49 for (i = 0; i < 100; i++)
51 if (i < 50)
53 else
57 into:
59 for (i = 0; i < 50; i++)
63 for (; i < 100; i++)
70 /* Return true when BB inside LOOP is a potential iteration space
71 split point, i.e. ends with a condition like "IV < comp", which
72 is true on one side of the iteration space and false on the other,
73 and the split point can be computed. If so, also return the border
74 point in *BORDER and the comparison induction variable in IV. */
76 static tree
77 split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv)
79 gcond *stmt;
80 affine_iv iv2;
82 /* BB must end in a simple conditional jump. */
83 stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
84 if (!stmt)
85 return NULL_TREE;
87 enum tree_code code = gimple_cond_code (stmt);
89 /* Only handle relational comparisons, for equality and non-equality
90 we'd have to split the loop into two loops and a middle statement. */
91 switch (code)
93 case LT_EXPR:
94 case LE_EXPR:
95 case GT_EXPR:
96 case GE_EXPR:
97 break;
98 default:
99 return NULL_TREE;
102 if (loop_exits_from_bb_p (loop, bb))
103 return NULL_TREE;
105 tree op0 = gimple_cond_lhs (stmt);
106 tree op1 = gimple_cond_rhs (stmt);
107 class loop *useloop = loop_containing_stmt (stmt);
109 if (!simple_iv (loop, useloop, op0, iv, false))
110 return NULL_TREE;
111 if (!simple_iv (loop, useloop, op1, &iv2, false))
112 return NULL_TREE;
114 /* Make it so that the first argument of the condition is
115 the looping one. */
116 if (!integer_zerop (iv2.step))
118 std::swap (op0, op1);
119 std::swap (*iv, iv2);
120 code = swap_tree_comparison (code);
121 gimple_cond_set_condition (stmt, code, op0, op1);
122 update_stmt (stmt);
124 else if (integer_zerop (iv->step))
125 return NULL_TREE;
126 if (!integer_zerop (iv2.step))
127 return NULL_TREE;
128 if (!iv->no_overflow)
129 return NULL_TREE;
131 if (dump_file && (dump_flags & TDF_DETAILS))
133 fprintf (dump_file, "Found potential split point: ");
134 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
135 fprintf (dump_file, " { ");
136 print_generic_expr (dump_file, iv->base, TDF_SLIM);
137 fprintf (dump_file, " + I*");
138 print_generic_expr (dump_file, iv->step, TDF_SLIM);
139 fprintf (dump_file, " } %s ", get_tree_code_name (code));
140 print_generic_expr (dump_file, iv2.base, TDF_SLIM);
141 fprintf (dump_file, "\n");
144 *border = iv2.base;
145 return op0;
148 /* Given a GUARD conditional stmt inside LOOP, which we want to make always
149 true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
150 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
151 exit test statement to loop back only if the GUARD statement will
152 also be true/false in the next iteration. */
154 static void
155 patch_loop_exit (class loop *loop, gcond *guard, tree nextval, tree newbound,
156 bool initial_true)
158 edge exit = single_exit (loop);
159 gcond *stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
160 gimple_cond_set_condition (stmt, gimple_cond_code (guard),
161 nextval, newbound);
162 update_stmt (stmt);
164 edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
166 exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
167 stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
169 if (initial_true)
171 exit->flags |= EDGE_FALSE_VALUE;
172 stay->flags |= EDGE_TRUE_VALUE;
174 else
176 exit->flags |= EDGE_TRUE_VALUE;
177 stay->flags |= EDGE_FALSE_VALUE;
181 /* Give an induction variable GUARD_IV, and its affine descriptor IV,
182 find the loop phi node in LOOP defining it directly, or create
183 such phi node. Return that phi node. */
185 static gphi *
186 find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/)
188 gimple *def = SSA_NAME_DEF_STMT (guard_iv);
189 gphi *phi;
190 if ((phi = dyn_cast <gphi *> (def))
191 && gimple_bb (phi) == loop->header)
192 return phi;
194 /* XXX Create the PHI instead. */
195 return NULL;
198 /* Returns true if the exit values of all loop phi nodes can be
199 determined easily (i.e. that connect_loop_phis can determine them). */
201 static bool
202 easy_exit_values (class loop *loop)
204 edge exit = single_exit (loop);
205 edge latch = loop_latch_edge (loop);
206 gphi_iterator psi;
208 /* Currently we regard the exit values as easy if they are the same
209 as the value over the backedge. Which is the case if the definition
210 of the backedge value dominates the exit edge. */
211 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
213 gphi *phi = psi.phi ();
214 tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
215 basic_block bb;
216 if (TREE_CODE (next) == SSA_NAME
217 && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
218 && !dominated_by_p (CDI_DOMINATORS, exit->src, bb))
219 return false;
222 return true;
225 /* This function updates the SSA form after connect_loops made a new
226 edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
227 conditional). I.e. the second loop can now be entered either
228 via the original entry or via NEW_E, so the entry values of LOOP2
229 phi nodes are either the original ones or those at the exit
230 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting
231 this. The loops need to fulfill easy_exit_values(). */
233 static void
234 connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e)
236 basic_block rest = loop_preheader_edge (loop2)->src;
237 gcc_assert (new_e->dest == rest);
238 edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
240 edge firste = loop_preheader_edge (loop1);
241 edge seconde = loop_preheader_edge (loop2);
242 edge firstn = loop_latch_edge (loop1);
243 gphi_iterator psi_first, psi_second;
244 for (psi_first = gsi_start_phis (loop1->header),
245 psi_second = gsi_start_phis (loop2->header);
246 !gsi_end_p (psi_first);
247 gsi_next (&psi_first), gsi_next (&psi_second))
249 tree init, next, new_init;
250 use_operand_p op;
251 gphi *phi_first = psi_first.phi ();
252 gphi *phi_second = psi_second.phi ();
254 init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
255 next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
256 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
257 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
259 /* Prefer using original variable as a base for the new ssa name.
260 This is necessary for virtual ops, and useful in order to avoid
261 losing debug info for real ops. */
262 if (TREE_CODE (next) == SSA_NAME
263 && useless_type_conversion_p (TREE_TYPE (next),
264 TREE_TYPE (init)))
265 new_init = copy_ssa_name (next);
266 else if (TREE_CODE (init) == SSA_NAME
267 && useless_type_conversion_p (TREE_TYPE (init),
268 TREE_TYPE (next)))
269 new_init = copy_ssa_name (init);
270 else if (useless_type_conversion_p (TREE_TYPE (next),
271 TREE_TYPE (init)))
272 new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
273 "unrinittmp");
274 else
275 new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
276 "unrinittmp");
278 gphi * newphi = create_phi_node (new_init, rest);
279 add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
280 add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
281 SET_USE (op, new_init);
285 /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
286 they are still equivalent and placed in two arms of a diamond, like so:
288 .------if (cond)------.
290 pre1 pre2
292 .--->h1 h2<----.
293 | | | |
294 | ex1---. .---ex2 |
295 | / | | \ |
296 '---l1 X | l2---'
299 '--->join<---'
301 This function transforms the program such that LOOP1 is conditionally
302 falling through to LOOP2, or skipping it. This is done by splitting
303 the ex1->join edge at X in the diagram above, and inserting a condition
304 whose one arm goes to pre2, resulting in this situation:
306 .------if (cond)------.
308 pre1 .---------->pre2
309 | | |
310 .--->h1 | h2<----.
311 | | | | |
312 | ex1---. | .---ex2 |
313 | / v | | \ |
314 '---l1 skip---' | l2---'
317 '--->join<---'
320 The condition used is the exit condition of LOOP1, which effectively means
321 that when the first loop exits (for whatever reason) but the real original
322 exit expression is still false the second loop will be entered.
323 The function returns the new edge cond->pre2.
325 This doesn't update the SSA form, see connect_loop_phis for that. */
327 static edge
328 connect_loops (class loop *loop1, class loop *loop2)
330 edge exit = single_exit (loop1);
331 basic_block skip_bb = split_edge (exit);
332 gcond *skip_stmt;
333 gimple_stmt_iterator gsi;
334 edge new_e, skip_e;
336 gcond *stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
337 skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
338 gimple_cond_lhs (stmt),
339 gimple_cond_rhs (stmt),
340 NULL_TREE, NULL_TREE);
341 gsi = gsi_last_bb (skip_bb);
342 gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
344 skip_e = EDGE_SUCC (skip_bb, 0);
345 skip_e->flags &= ~EDGE_FALLTHRU;
346 new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
347 if (exit->flags & EDGE_TRUE_VALUE)
349 skip_e->flags |= EDGE_TRUE_VALUE;
350 new_e->flags |= EDGE_FALSE_VALUE;
352 else
354 skip_e->flags |= EDGE_FALSE_VALUE;
355 new_e->flags |= EDGE_TRUE_VALUE;
358 new_e->probability = profile_probability::likely ();
359 skip_e->probability = new_e->probability.invert ();
361 return new_e;
364 /* This returns the new bound for iterations given the original iteration
365 space in NITER, an arbitrary new bound BORDER, assumed to be some
366 comparison value with a different IV, the initial value GUARD_INIT of
367 that other IV, and the comparison code GUARD_CODE that compares
368 that other IV with BORDER. We return an SSA name, and place any
369 necessary statements for that computation into *STMTS.
371 For example for such a loop:
373 for (i = beg, j = guard_init; i < end; i++, j++)
374 if (j < border) // this is supposed to be true/false
377 we want to return a new bound (on j) that makes the loop iterate
378 as long as the condition j < border stays true. We also don't want
379 to iterate more often than the original loop, so we have to introduce
380 some cut-off as well (via min/max), effectively resulting in:
382 newend = min (end+guard_init-beg, border)
383 for (i = beg; j = guard_init; j < newend; i++, j++)
384 if (j < c)
387 Depending on the direction of the IVs and if the exit tests
388 are strict or non-strict we need to use MIN or MAX,
389 and add or subtract 1. This routine computes newend above. */
391 static tree
392 compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter,
393 tree border,
394 enum tree_code guard_code, tree guard_init)
396 /* The niter structure contains the after-increment IV, we need
397 the loop-enter base, so subtract STEP once. */
398 tree controlbase = force_gimple_operand (niter->control.base,
399 stmts, true, NULL_TREE);
400 tree controlstep = niter->control.step;
401 tree enddiff;
402 if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
404 controlstep = gimple_build (stmts, NEGATE_EXPR,
405 TREE_TYPE (controlstep), controlstep);
406 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
407 TREE_TYPE (controlbase),
408 controlbase, controlstep);
410 else
411 enddiff = gimple_build (stmts, MINUS_EXPR,
412 TREE_TYPE (controlbase),
413 controlbase, controlstep);
415 /* Compute end-beg. */
416 gimple_seq stmts2;
417 tree end = force_gimple_operand (niter->bound, &stmts2,
418 true, NULL_TREE);
419 gimple_seq_add_seq_without_update (stmts, stmts2);
420 if (POINTER_TYPE_P (TREE_TYPE (enddiff)))
422 tree tem = gimple_convert (stmts, sizetype, enddiff);
423 tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem);
424 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
425 TREE_TYPE (enddiff),
426 end, tem);
428 else
429 enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
430 end, enddiff);
432 /* Compute guard_init + (end-beg). */
433 tree newbound;
434 enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
435 if (POINTER_TYPE_P (TREE_TYPE (guard_init)))
437 enddiff = gimple_convert (stmts, sizetype, enddiff);
438 newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
439 TREE_TYPE (guard_init),
440 guard_init, enddiff);
442 else
443 newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
444 guard_init, enddiff);
446 /* Depending on the direction of the IVs the new bound for the first
447 loop is the minimum or maximum of old bound and border.
448 Also, if the guard condition isn't strictly less or greater,
449 we need to adjust the bound. */
450 int addbound = 0;
451 enum tree_code minmax;
452 if (niter->cmp == LT_EXPR)
454 /* GT and LE are the same, inverted. */
455 if (guard_code == GT_EXPR || guard_code == LE_EXPR)
456 addbound = -1;
457 minmax = MIN_EXPR;
459 else
461 gcc_assert (niter->cmp == GT_EXPR);
462 if (guard_code == GE_EXPR || guard_code == LT_EXPR)
463 addbound = 1;
464 minmax = MAX_EXPR;
467 if (addbound)
469 tree type2 = TREE_TYPE (newbound);
470 if (POINTER_TYPE_P (type2))
471 type2 = sizetype;
472 newbound = gimple_build (stmts,
473 POINTER_TYPE_P (TREE_TYPE (newbound))
474 ? POINTER_PLUS_EXPR : PLUS_EXPR,
475 TREE_TYPE (newbound),
476 newbound,
477 build_int_cst (type2, addbound));
480 tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
481 border, newbound);
482 return newend;
485 /* Fix the two loop's bb count after split based on the split edge probability,
486 don't adjust the bbs dominated by true branches of that loop to avoid
487 dropping 1s down. */
488 static void
489 fix_loop_bb_probability (class loop *loop1, class loop *loop2, edge true_edge,
490 edge false_edge)
492 /* Proportion first loop's bb counts except those dominated by true
493 branch to avoid drop 1s down. */
494 basic_block *bbs1, *bbs2;
495 bbs1 = get_loop_body (loop1);
496 unsigned j;
497 for (j = 0; j < loop1->num_nodes; j++)
498 if (bbs1[j] == loop1->latch
499 || !dominated_by_p (CDI_DOMINATORS, bbs1[j], true_edge->dest))
500 bbs1[j]->count
501 = bbs1[j]->count.apply_probability (true_edge->probability);
502 free (bbs1);
504 /* Proportion second loop's bb counts except those dominated by false
505 branch to avoid drop 1s down. */
506 basic_block bbi_copy = get_bb_copy (false_edge->dest);
507 bbs2 = get_loop_body (loop2);
508 for (j = 0; j < loop2->num_nodes; j++)
509 if (bbs2[j] == loop2->latch
510 || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy))
511 bbs2[j]->count
512 = bbs2[j]->count.apply_probability (true_edge->probability.invert ());
513 free (bbs2);
516 /* Checks if LOOP contains an conditional block whose condition
517 depends on which side in the iteration space it is, and if so
518 splits the iteration space into two loops. Returns true if the
519 loop was split. NITER must contain the iteration descriptor for the
520 single exit of LOOP. */
522 static bool
523 split_loop (class loop *loop1)
525 class tree_niter_desc niter;
526 basic_block *bbs;
527 unsigned i;
528 bool changed = false;
529 tree guard_iv;
530 tree border = NULL_TREE;
531 affine_iv iv;
532 edge exit1;
534 if (!(exit1 = single_exit (loop1))
535 || EDGE_COUNT (exit1->src->succs) != 2
536 /* ??? We could handle non-empty latches when we split the latch edge
537 (not the exit edge), and put the new exit condition in the new block.
538 OTOH this executes some code unconditionally that might have been
539 skipped by the original exit before. */
540 || !empty_block_p (loop1->latch)
541 || !easy_exit_values (loop1)
542 || !number_of_iterations_exit (loop1, exit1, &niter, false, true)
543 || niter.cmp == ERROR_MARK
544 /* We can't yet handle loops controlled by a != predicate. */
545 || niter.cmp == NE_EXPR)
546 return false;
548 bbs = get_loop_body (loop1);
550 if (!can_copy_bbs_p (bbs, loop1->num_nodes))
552 free (bbs);
553 return false;
556 /* Find a splitting opportunity. */
557 for (i = 0; i < loop1->num_nodes; i++)
558 if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
560 /* Handling opposite steps is not implemented yet. Neither
561 is handling different step sizes. */
562 if ((tree_int_cst_sign_bit (iv.step)
563 != tree_int_cst_sign_bit (niter.control.step))
564 || !tree_int_cst_equal (iv.step, niter.control.step))
565 continue;
567 /* Find a loop PHI node that defines guard_iv directly,
568 or create one doing that. */
569 gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
570 if (!phi)
571 continue;
572 gcond *guard_stmt = as_a<gcond *> (*gsi_last_bb (bbs[i]));
573 tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
574 loop_preheader_edge (loop1));
575 enum tree_code guard_code = gimple_cond_code (guard_stmt);
577 /* Loop splitting is implemented by versioning the loop, placing
578 the new loop after the old loop, make the first loop iterate
579 as long as the conditional stays true (or false) and let the
580 second (new) loop handle the rest of the iterations.
582 First we need to determine if the condition will start being true
583 or false in the first loop. */
584 bool initial_true;
585 switch (guard_code)
587 case LT_EXPR:
588 case LE_EXPR:
589 initial_true = !tree_int_cst_sign_bit (iv.step);
590 break;
591 case GT_EXPR:
592 case GE_EXPR:
593 initial_true = tree_int_cst_sign_bit (iv.step);
594 break;
595 default:
596 gcc_unreachable ();
599 /* Build a condition that will skip the first loop when the
600 guard condition won't ever be true (or false). */
601 gimple_seq stmts2;
602 border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
603 if (stmts2)
604 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
605 stmts2);
606 tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
607 if (!initial_true)
608 cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
610 edge true_edge, false_edge;
611 extract_true_false_edges_from_block (bbs[i], &true_edge, &false_edge);
613 /* Now version the loop, placing loop2 after loop1 connecting
614 them, and fix up SSA form for that. */
615 initialize_original_copy_tables ();
616 basic_block cond_bb;
618 class loop *loop2 = loop_version (loop1, cond, &cond_bb,
619 true_edge->probability,
620 true_edge->probability.invert (),
621 profile_probability::always (),
622 profile_probability::always (),
623 true);
624 gcc_assert (loop2);
626 edge new_e = connect_loops (loop1, loop2);
627 connect_loop_phis (loop1, loop2, new_e);
629 /* The iterations of the second loop is now already
630 exactly those that the first loop didn't do, but the
631 iteration space of the first loop is still the original one.
632 Compute the new bound for the guarding IV and patch the
633 loop exit to use it instead of original IV and bound. */
634 gimple_seq stmts = NULL;
635 tree newend = compute_new_first_bound (&stmts, &niter, border,
636 guard_code, guard_init);
637 if (stmts)
638 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
639 stmts);
640 tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
641 patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
643 fix_loop_bb_probability (loop1, loop2, true_edge, false_edge);
645 /* Fix first loop's exit probability after scaling. */
646 edge exit_to_latch1;
647 if (EDGE_SUCC (exit1->src, 0) == exit1)
648 exit_to_latch1 = EDGE_SUCC (exit1->src, 1);
649 else
650 exit_to_latch1 = EDGE_SUCC (exit1->src, 0);
651 exit_to_latch1->probability *= true_edge->probability;
652 exit1->probability = exit_to_latch1->probability.invert ();
654 /* Finally patch out the two copies of the condition to be always
655 true/false (or opposite). */
656 gcond *force_true = as_a<gcond *> (*gsi_last_bb (bbs[i]));
657 gcond *force_false = as_a<gcond *> (*gsi_last_bb (get_bb_copy (bbs[i])));
658 if (!initial_true)
659 std::swap (force_true, force_false);
660 gimple_cond_make_true (force_true);
661 gimple_cond_make_false (force_false);
662 update_stmt (force_true);
663 update_stmt (force_false);
665 free_original_copy_tables ();
667 changed = true;
668 if (dump_file && (dump_flags & TDF_DETAILS))
669 fprintf (dump_file, ";; Loop split.\n");
671 if (dump_enabled_p ())
672 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, guard_stmt, "loop split\n");
674 /* Only deal with the first opportunity. */
675 break;
678 free (bbs);
679 return changed;
682 /* Another transformation of loops like:
684 for (i = INIT (); CHECK (i); i = NEXT ())
686 if (expr (a_1, a_2, ..., a_n)) // expr is pure
687 a_j = ...; // change at least one a_j
688 else
689 S; // not change any a_j
692 into:
694 for (i = INIT (); CHECK (i); i = NEXT ())
696 if (expr (a_1, a_2, ..., a_n))
697 a_j = ...;
698 else
701 i = NEXT ();
702 break;
706 for (; CHECK (i); i = NEXT ())
713 /* Data structure to hold temporary information during loop split upon
714 semi-invariant conditional statement. */
715 class split_info {
716 public:
717 /* Array of all basic blocks in a loop, returned by get_loop_body(). */
718 basic_block *bbs;
720 /* All memory store/clobber statements in a loop. */
721 auto_vec<gimple *> memory_stores;
723 /* Whether above memory stores vector has been filled. */
724 int need_init;
726 /* Control dependencies of basic blocks in a loop. */
727 auto_vec<hash_set<basic_block> *> control_deps;
729 split_info () : bbs (NULL), need_init (true) { }
731 ~split_info ()
733 if (bbs)
734 free (bbs);
736 for (unsigned i = 0; i < control_deps.length (); i++)
737 delete control_deps[i];
741 /* Find all statements with memory-write effect in LOOP, including memory
742 store and non-pure function call, and keep those in a vector. This work
743 is only done one time, for the vector should be constant during analysis
744 stage of semi-invariant condition. */
746 static void
747 find_vdef_in_loop (struct loop *loop)
749 split_info *info = (split_info *) loop->aux;
750 gphi *vphi = get_virtual_phi (loop->header);
752 /* Indicate memory store vector has been filled. */
753 info->need_init = false;
755 /* If loop contains memory operation, there must be a virtual PHI node in
756 loop header basic block. */
757 if (vphi == NULL)
758 return;
760 /* All virtual SSA names inside the loop are connected to be a cyclic
761 graph via virtual PHI nodes. The virtual PHI node in loop header just
762 links the first and the last virtual SSA names, by using the last as
763 PHI operand to define the first. */
764 const edge latch = loop_latch_edge (loop);
765 const tree first = gimple_phi_result (vphi);
766 const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
768 /* The virtual SSA cyclic graph might consist of only one SSA name, who
769 is defined by itself.
771 .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
773 This means the loop contains only memory loads, so we can skip it. */
774 if (first == last)
775 return;
777 auto_vec<gimple *> other_stores;
778 auto_vec<tree> worklist;
779 auto_bitmap visited;
781 bitmap_set_bit (visited, SSA_NAME_VERSION (first));
782 bitmap_set_bit (visited, SSA_NAME_VERSION (last));
783 worklist.safe_push (last);
787 tree vuse = worklist.pop ();
788 gimple *stmt = SSA_NAME_DEF_STMT (vuse);
790 /* We mark the first and last SSA names as visited at the beginning,
791 and reversely start the process from the last SSA name towards the
792 first, which ensures that this do-while will not touch SSA names
793 defined outside the loop. */
794 gcc_assert (gimple_bb (stmt)
795 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
797 if (gimple_code (stmt) == GIMPLE_PHI)
799 gphi *phi = as_a <gphi *> (stmt);
801 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
803 tree arg = gimple_phi_arg_def (stmt, i);
805 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
806 worklist.safe_push (arg);
809 else
811 tree prev = gimple_vuse (stmt);
813 /* Non-pure call statement is conservatively assumed to impact all
814 memory locations. So place call statements ahead of other memory
815 stores in the vector with an idea of using them as shortcut
816 terminators to memory alias analysis. */
817 if (gimple_code (stmt) == GIMPLE_CALL)
818 info->memory_stores.safe_push (stmt);
819 else
820 other_stores.safe_push (stmt);
822 if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
823 worklist.safe_push (prev);
825 } while (!worklist.is_empty ());
827 info->memory_stores.safe_splice (other_stores);
830 /* Two basic blocks have equivalent control dependency if one dominates to
831 the other, and it is post-dominated by the latter. Given a basic block
832 BB in LOOP, find farest equivalent dominating basic block. For BB, there
833 is a constraint that BB does not post-dominate loop header of LOOP, this
834 means BB is control-dependent on at least one basic block in LOOP. */
836 static basic_block
837 get_control_equiv_head_block (struct loop *loop, basic_block bb)
839 while (!bb->aux)
841 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
843 gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb));
845 if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb))
846 break;
848 bb = dom_bb;
850 return bb;
853 /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
854 dependent on. */
856 static hash_set<basic_block> *
857 find_control_dep_blocks (struct loop *loop, basic_block bb)
859 /* BB has same control dependency as loop header, then it is not control-
860 dependent on any basic block in LOOP. */
861 if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb))
862 return NULL;
864 basic_block equiv_head = get_control_equiv_head_block (loop, bb);
866 if (equiv_head->aux)
868 /* There is a basic block containing control dependency equivalent
869 to BB. No need to recompute that, and also set this information
870 to other equivalent basic blocks. */
871 for (; bb != equiv_head;
872 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
873 bb->aux = equiv_head->aux;
874 return (hash_set<basic_block> *) equiv_head->aux;
877 /* A basic block X is control-dependent on another Y iff there exists
878 a path from X to Y, in which every basic block other than X and Y
879 is post-dominated by Y, but X is not post-dominated by Y.
881 According to this rule, traverse basic blocks in the loop backwards
882 starting from BB, if a basic block is post-dominated by BB, extend
883 current post-dominating path to this block, otherwise it is another
884 one that BB is control-dependent on. */
886 auto_vec<basic_block> pdom_worklist;
887 hash_set<basic_block> pdom_visited;
888 hash_set<basic_block> *dep_bbs = new hash_set<basic_block>;
890 pdom_worklist.safe_push (equiv_head);
894 basic_block pdom_bb = pdom_worklist.pop ();
895 edge_iterator ei;
896 edge e;
898 if (pdom_visited.add (pdom_bb))
899 continue;
901 FOR_EACH_EDGE (e, ei, pdom_bb->preds)
903 basic_block pred_bb = e->src;
905 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb))
907 dep_bbs->add (pred_bb);
908 continue;
911 pred_bb = get_control_equiv_head_block (loop, pred_bb);
913 if (pdom_visited.contains (pred_bb))
914 continue;
916 if (!pred_bb->aux)
918 pdom_worklist.safe_push (pred_bb);
919 continue;
922 /* If control dependency of basic block is available, fast extend
923 post-dominating path using the information instead of advancing
924 forward step-by-step. */
925 hash_set<basic_block> *pred_dep_bbs
926 = (hash_set<basic_block> *) pred_bb->aux;
928 for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin ();
929 iter != pred_dep_bbs->end (); ++iter)
931 basic_block pred_dep_bb = *iter;
933 /* Basic blocks can either be in control dependency of BB, or
934 must be post-dominated by BB, if so, extend the path from
935 these basic blocks. */
936 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb))
937 dep_bbs->add (pred_dep_bb);
938 else if (!pdom_visited.contains (pred_dep_bb))
939 pdom_worklist.safe_push (pred_dep_bb);
942 } while (!pdom_worklist.is_empty ());
944 /* Record computed control dependencies in loop so that we can reach them
945 when reclaiming resources. */
946 ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs);
948 /* Associate control dependence with related equivalent basic blocks. */
949 for (equiv_head->aux = dep_bbs; bb != equiv_head;
950 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
951 bb->aux = dep_bbs;
953 return dep_bbs;
956 /* Forward declaration */
958 static bool
959 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
960 const_basic_block skip_head,
961 hash_map<gimple *, bool> &stmt_stat);
963 /* Given STMT, memory load or pure call statement, check whether it is impacted
964 by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
965 trace is composed of SKIP_HEAD and those basic block dominated by it, always
966 corresponds to one branch of a conditional statement). If SKIP_HEAD is
967 NULL, all basic blocks of LOOP are checked. */
969 static bool
970 vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
971 const_basic_block skip_head)
973 split_info *info = (split_info *) loop->aux;
974 tree rhs = NULL_TREE;
975 ao_ref ref;
976 gimple *store;
977 unsigned i;
979 /* Collect memory store/clobber statements if haven't done that. */
980 if (info->need_init)
981 find_vdef_in_loop (loop);
983 if (is_gimple_assign (stmt))
984 rhs = gimple_assign_rhs1 (stmt);
986 ao_ref_init (&ref, rhs);
988 FOR_EACH_VEC_ELT (info->memory_stores, i, store)
990 /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */
991 if (skip_head
992 && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head))
993 continue;
995 if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
996 return false;
999 return true;
1002 /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
1003 certain iteration of LOOP, check whether an SSA name (NAME) remains
1004 unchanged in next iteration. We call this characteristic semi-
1005 invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic
1006 blocks and control flows in the loop will be considered. Semi-invariant
1007 state of checked statement is cached in hash map STMT_STAT to avoid
1008 redundant computation in possible following re-check. */
1010 static inline bool
1011 ssa_semi_invariant_p (struct loop *loop, tree name,
1012 const_basic_block skip_head,
1013 hash_map<gimple *, bool> &stmt_stat)
1015 gimple *def = SSA_NAME_DEF_STMT (name);
1016 const_basic_block def_bb = gimple_bb (def);
1018 /* An SSA name defined outside loop is definitely semi-invariant. */
1019 if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
1020 return true;
1022 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1023 return false;
1025 return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat);
1028 /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
1029 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1030 are excluded from LOOP. */
1032 static bool
1033 loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi,
1034 const_basic_block skip_head)
1036 const_edge latch = loop_latch_edge (loop);
1037 tree name = gimple_phi_result (loop_phi);
1038 tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch);
1040 gcc_checking_assert (from);
1042 /* Loop iteration PHI node locates in loop header, and it has two source
1043 operands, one is an initial value coming from outside the loop, the other
1044 is a value through latch of the loop, which is derived in last iteration,
1045 we call the latter latch value. From the PHI node to definition of latch
1046 value, if excluding branch trace starting from SKIP_HEAD, except copy-
1047 assignment or likewise, there is no other kind of value redefinition, SSA
1048 name defined by the PHI node is semi-invariant.
1050 loop entry
1051 | .--- latch ---.
1052 | | |
1053 v v |
1054 x_1 = PHI <x_0, x_3> |
1057 .------- if (cond) -------. |
1058 | | |
1059 | [ SKIP ] |
1060 | | |
1061 | x_2 = ... |
1062 | | |
1063 '---- T ---->.<---- F ----' |
1066 x_3 = PHI <x_1, x_2> |
1068 '----------------------'
1070 Suppose in certain iteration, execution flow in above graph goes through
1071 true branch, which means that one source value to define x_3 in false
1072 branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
1073 iterations is defined by x_3, we know that x_1 will never changed if COND
1074 always chooses true branch from then on. */
1076 while (from != name)
1078 /* A new value comes from a CONSTANT. */
1079 if (TREE_CODE (from) != SSA_NAME)
1080 return false;
1082 gimple *stmt = SSA_NAME_DEF_STMT (from);
1083 const_basic_block bb = gimple_bb (stmt);
1085 /* A new value comes from outside the loop. */
1086 if (!bb || !flow_bb_inside_loop_p (loop, bb))
1087 return false;
1089 from = NULL_TREE;
1091 if (gimple_code (stmt) == GIMPLE_PHI)
1093 gphi *phi = as_a <gphi *> (stmt);
1095 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1097 if (skip_head)
1099 const_edge e = gimple_phi_arg_edge (phi, i);
1101 /* Don't consider redefinitions in excluded basic blocks. */
1102 if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head))
1103 continue;
1106 tree arg = gimple_phi_arg_def (phi, i);
1108 if (!from)
1109 from = arg;
1110 else if (!operand_equal_p (from, arg, 0))
1111 /* There are more than one source operands that provide
1112 different values to the SSA name, it is variant. */
1113 return false;
1116 else if (gimple_code (stmt) == GIMPLE_ASSIGN)
1118 /* For simple value copy, check its rhs instead. */
1119 if (gimple_assign_ssa_name_copy_p (stmt))
1120 from = gimple_assign_rhs1 (stmt);
1123 /* Any other kind of definition is deemed to introduce a new value
1124 to the SSA name. */
1125 if (!from)
1126 return false;
1128 return true;
1131 /* Check whether conditional predicates that BB is control-dependent on, are
1132 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1133 are excluded from LOOP. Semi-invariant state of checked statement is cached
1134 in hash map STMT_STAT. */
1136 static bool
1137 control_dep_semi_invariant_p (struct loop *loop, basic_block bb,
1138 const_basic_block skip_head,
1139 hash_map<gimple *, bool> &stmt_stat)
1141 hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb);
1143 if (!dep_bbs)
1144 return true;
1146 for (hash_set<basic_block>::iterator iter = dep_bbs->begin ();
1147 iter != dep_bbs->end (); ++iter)
1149 gimple *last = *gsi_last_bb (*iter);
1150 if (!last)
1151 return false;
1153 /* Only check condition predicates. */
1154 if (gimple_code (last) != GIMPLE_COND
1155 && gimple_code (last) != GIMPLE_SWITCH)
1156 return false;
1158 if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat))
1159 return false;
1162 return true;
1165 /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
1166 semi-invariant, consequently, all its defined values are semi-invariant.
1167 Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
1168 Semi-invariant state of checked statement is cached in hash map
1169 STMT_STAT. */
1171 static bool
1172 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
1173 const_basic_block skip_head,
1174 hash_map<gimple *, bool> &stmt_stat)
1176 bool existed;
1177 bool &invar = stmt_stat.get_or_insert (stmt, &existed);
1179 if (existed)
1180 return invar;
1182 /* A statement might depend on itself, which is treated as variant. So set
1183 state of statement under check to be variant to ensure that. */
1184 invar = false;
1186 if (gimple_code (stmt) == GIMPLE_PHI)
1188 gphi *phi = as_a <gphi *> (stmt);
1190 if (gimple_bb (stmt) == loop->header)
1192 /* If the entry value is subject to abnormal coalescing
1193 avoid the transform since we're going to duplicate the
1194 loop header and thus likely introduce overlapping life-ranges
1195 between the PHI def and the entry on the path when the
1196 first loop is skipped. */
1197 tree entry_def
1198 = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1199 if (TREE_CODE (entry_def) == SSA_NAME
1200 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (entry_def))
1201 return false;
1202 invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head);
1203 return invar;
1206 /* For a loop PHI node that does not locate in loop header, it is semi-
1207 invariant only if two conditions are met. The first is its source
1208 values are derived from CONSTANT (including loop-invariant value), or
1209 from SSA name defined by semi-invariant loop iteration PHI node. The
1210 second is its source incoming edges are control-dependent on semi-
1211 invariant conditional predicates. */
1212 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1214 const_edge e = gimple_phi_arg_edge (phi, i);
1215 tree arg = gimple_phi_arg_def (phi, i);
1217 if (TREE_CODE (arg) == SSA_NAME)
1219 if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat))
1220 return false;
1222 /* If source value is defined in location from where the source
1223 edge comes in, no need to check control dependency again
1224 since this has been done in above SSA name check stage. */
1225 if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1226 continue;
1229 if (!control_dep_semi_invariant_p (loop, e->src, skip_head,
1230 stmt_stat))
1231 return false;
1234 else
1236 ssa_op_iter iter;
1237 tree use;
1239 /* Volatile memory load or return of normal (non-const/non-pure) call
1240 should not be treated as constant in each iteration of loop. */
1241 if (gimple_has_side_effects (stmt))
1242 return false;
1244 /* Check if any memory store may kill memory load at this place. */
1245 if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head))
1246 return false;
1248 /* Although operand of a statement might be SSA name, CONSTANT or
1249 VARDECL, here we only need to check SSA name operands. This is
1250 because check on VARDECL operands, which involve memory loads,
1251 must have been done prior to invocation of this function in
1252 vuse_semi_invariant_p. */
1253 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1254 if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat))
1255 return false;
1258 if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head,
1259 stmt_stat))
1260 return false;
1262 /* Here we SHOULD NOT use invar = true, since hash map might be changed due
1263 to new insertion, and thus invar may point to invalid memory. */
1264 stmt_stat.put (stmt, true);
1265 return true;
1268 /* A helper function to check whether STMT is semi-invariant in LOOP. Basic
1269 blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */
1271 static bool
1272 stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
1273 const_basic_block skip_head)
1275 hash_map<gimple *, bool> stmt_stat;
1276 return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat);
1279 /* Determine when conditional statement never transfers execution to one of its
1280 branch, whether we can remove the branch's leading basic block (BRANCH_BB)
1281 and those basic blocks dominated by BRANCH_BB. */
1283 static bool
1284 branch_removable_p (basic_block branch_bb)
1286 edge_iterator ei;
1287 edge e;
1289 if (single_pred_p (branch_bb))
1290 return true;
1292 FOR_EACH_EDGE (e, ei, branch_bb->preds)
1294 if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
1295 continue;
1297 if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
1298 continue;
1300 /* The branch can be reached from opposite branch, or from some
1301 statement not dominated by the conditional statement. */
1302 return false;
1305 return true;
1308 /* Find out which branch of a conditional statement (COND) is invariant in the
1309 execution context of LOOP. That is: once the branch is selected in certain
1310 iteration of the loop, any operand that contributes to computation of the
1311 conditional statement remains unchanged in all following iterations. */
1313 static edge
1314 get_cond_invariant_branch (struct loop *loop, gcond *cond)
1316 basic_block cond_bb = gimple_bb (cond);
1317 basic_block targ_bb[2];
1318 bool invar[2];
1319 unsigned invar_checks = 0;
1321 for (unsigned i = 0; i < 2; i++)
1323 targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
1325 /* One branch directs to loop exit, no need to perform loop split upon
1326 this conditional statement. Firstly, it is trivial if the exit branch
1327 is semi-invariant, for the statement is just to break loop. Secondly,
1328 if the opposite branch is semi-invariant, it means that the statement
1329 is real loop-invariant, which is covered by loop unswitch. */
1330 if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
1331 return NULL;
1334 for (unsigned i = 0; i < 2; i++)
1336 invar[!i] = false;
1338 if (!branch_removable_p (targ_bb[i]))
1339 continue;
1341 /* Given a semi-invariant branch, if its opposite branch dominates
1342 loop latch, it and its following trace will only be executed in
1343 final iteration of loop, namely it is not part of repeated body
1344 of the loop. Similar to the above case that the branch is loop
1345 exit, no need to split loop. */
1346 if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
1347 continue;
1349 invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
1350 invar_checks++;
1353 /* With both branches being invariant (handled by loop unswitch) or
1354 variant is not what we want. */
1355 if (invar[0] ^ !invar[1])
1356 return NULL;
1358 /* Found a real loop-invariant condition, do nothing. */
1359 if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
1360 return NULL;
1362 return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1);
1365 /* Calculate increased code size measured by estimated insn number if applying
1366 loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */
1368 static int
1369 compute_added_num_insns (struct loop *loop, const_edge branch_edge)
1371 basic_block cond_bb = branch_edge->src;
1372 unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge;
1373 basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest;
1374 basic_block *bbs = ((split_info *) loop->aux)->bbs;
1375 int num = 0;
1377 for (unsigned i = 0; i < loop->num_nodes; i++)
1379 /* Do no count basic blocks only in opposite branch. */
1380 if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb))
1381 continue;
1383 num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
1386 /* It is unnecessary to evaluate expression of the conditional statement
1387 in new loop that contains only invariant branch. This expression should
1388 be constant value (either true or false). Exclude code size of insns
1389 that contribute to computation of the expression. */
1391 auto_vec<gimple *> worklist;
1392 hash_set<gimple *> removed;
1393 gimple *stmt = last_nondebug_stmt (cond_bb);
1395 worklist.safe_push (stmt);
1396 removed.add (stmt);
1397 num -= estimate_num_insns (stmt, &eni_size_weights);
1401 ssa_op_iter opnd_iter;
1402 use_operand_p opnd_p;
1404 stmt = worklist.pop ();
1405 FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE)
1407 tree opnd = USE_FROM_PTR (opnd_p);
1409 if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd))
1410 continue;
1412 gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd);
1413 use_operand_p use_p;
1414 imm_use_iterator use_iter;
1416 if (removed.contains (opnd_stmt)
1417 || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt)))
1418 continue;
1420 FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd)
1422 gimple *use_stmt = USE_STMT (use_p);
1424 if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt))
1426 opnd_stmt = NULL;
1427 break;
1431 if (opnd_stmt)
1433 worklist.safe_push (opnd_stmt);
1434 removed.add (opnd_stmt);
1435 num -= estimate_num_insns (opnd_stmt, &eni_size_weights);
1438 } while (!worklist.is_empty ());
1440 gcc_assert (num >= 0);
1441 return num;
1444 /* Find out loop-invariant branch of a conditional statement (COND) if it has,
1445 and check whether it is eligible and profitable to perform loop split upon
1446 this branch in LOOP. */
1448 static edge
1449 get_cond_branch_to_split_loop (struct loop *loop, gcond *cond)
1451 edge invar_branch = get_cond_invariant_branch (loop, cond);
1452 if (!invar_branch)
1453 return NULL;
1455 /* When accurate profile information is available, and execution
1456 frequency of the branch is too low, just let it go. */
1457 profile_probability prob = invar_branch->probability;
1458 if (prob.reliable_p ())
1460 int thres = param_min_loop_cond_split_prob;
1462 if (prob < profile_probability::always ().apply_scale (thres, 100))
1463 return NULL;
1466 /* Add a threshold for increased code size to disable loop split. */
1467 if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns)
1468 return NULL;
1470 return invar_branch;
1473 /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
1474 conditional statement, perform loop split transformation illustrated
1475 as the following graph.
1477 .-------T------ if (true) ------F------.
1478 | .---------------. |
1479 | | | |
1480 v | v v
1481 pre-header | pre-header
1482 | .------------. | | .------------.
1483 | | | | | | |
1484 | v | | | v |
1485 header | | header |
1486 | | | | |
1487 .--- if (cond) ---. | | .--- if (true) ---. |
1488 | | | | | | |
1489 invariant | | | invariant | |
1490 | | | | | | |
1491 '---T--->.<---F---' | | '---T--->.<---F---' |
1492 | | / | |
1493 stmts | / stmts |
1494 | F T | |
1495 / \ | / / \ |
1496 .-------* * [ if (cond) ] .-------* * |
1497 | | | | | |
1498 | latch | | latch |
1499 | | | | | |
1500 | '------------' | '------------'
1501 '------------------------. .-----------'
1502 loop1 | | loop2
1504 exits
1506 In the graph, loop1 represents the part derived from original one, and
1507 loop2 is duplicated using loop_version (), which corresponds to the part
1508 of original one being splitted out. In original latch edge of loop1, we
1509 insert a new conditional statement duplicated from the semi-invariant cond,
1510 and one of its branch goes back to loop1 header as a latch edge, and the
1511 other branch goes to loop2 pre-header as an entry edge. And also in loop2,
1512 we abandon the variant branch of the conditional statement by setting a
1513 constant bool condition, based on which branch is semi-invariant. */
1515 static bool
1516 do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
1518 basic_block cond_bb = invar_branch->src;
1519 bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE);
1520 gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1522 gcc_assert (cond_bb->loop_father == loop1);
1524 if (dump_enabled_p ())
1525 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
1526 "loop split on semi-invariant condition at %s branch\n",
1527 true_invar ? "true" : "false");
1529 initialize_original_copy_tables ();
1531 struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
1532 invar_branch->probability.invert (),
1533 invar_branch->probability,
1534 profile_probability::always (),
1535 profile_probability::always (),
1536 true);
1537 if (!loop2)
1539 free_original_copy_tables ();
1540 return false;
1543 basic_block cond_bb_copy = get_bb_copy (cond_bb);
1544 gcond *cond_copy = as_a<gcond *> (*gsi_last_bb (cond_bb_copy));
1546 /* Replace the condition in loop2 with a bool constant to let PassManager
1547 remove the variant branch after current pass completes. */
1548 if (true_invar)
1549 gimple_cond_make_true (cond_copy);
1550 else
1551 gimple_cond_make_false (cond_copy);
1553 update_stmt (cond_copy);
1555 /* Insert a new conditional statement on latch edge of loop1, its condition
1556 is duplicated from the semi-invariant. This statement acts as a switch
1557 to transfer execution from loop1 to loop2, when loop1 enters into
1558 invariant state. */
1559 basic_block latch_bb = split_edge (loop_latch_edge (loop1));
1560 basic_block break_bb = split_edge (single_pred_edge (latch_bb));
1561 gimple *break_cond = gimple_build_cond (gimple_cond_code(cond),
1562 gimple_cond_lhs (cond),
1563 gimple_cond_rhs (cond),
1564 NULL_TREE, NULL_TREE);
1566 gimple_stmt_iterator gsi = gsi_last_bb (break_bb);
1567 gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
1569 edge to_loop1 = single_succ_edge (break_bb);
1570 edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);
1572 to_loop1->flags &= ~EDGE_FALLTHRU;
1573 to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
1574 to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
1576 /* Due to introduction of a control flow edge from loop1 latch to loop2
1577 pre-header, we should update PHIs in loop2 to reflect this connection
1578 between loop1 and loop2. */
1579 connect_loop_phis (loop1, loop2, to_loop2);
1581 edge true_edge, false_edge, skip_edge1, skip_edge2;
1582 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1584 skip_edge1 = true_invar ? false_edge : true_edge;
1585 skip_edge2 = true_invar ? true_edge : false_edge;
1586 fix_loop_bb_probability (loop1, loop2, skip_edge1, skip_edge2);
1588 /* Fix first loop's exit probability after scaling. */
1589 to_loop1->probability = invar_branch->probability.invert ();
1590 to_loop2->probability = invar_branch->probability;
1592 free_original_copy_tables ();
1594 return true;
1597 /* Traverse all conditional statements in LOOP, to find out a good candidate
1598 upon which we can do loop split. */
1600 static bool
1601 split_loop_on_cond (struct loop *loop)
1603 split_info *info = new split_info ();
1604 basic_block *bbs = info->bbs = get_loop_body (loop);
1605 bool do_split = false;
1607 /* Allocate an area to keep temporary info, and associate its address
1608 with loop aux field. */
1609 loop->aux = info;
1611 for (unsigned i = 0; i < loop->num_nodes; i++)
1612 bbs[i]->aux = NULL;
1614 for (unsigned i = 0; i < loop->num_nodes; i++)
1616 basic_block bb = bbs[i];
1618 /* We only consider conditional statement, which be executed at most once
1619 in each iteration of the loop. So skip statements in inner loops. */
1620 if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP))
1621 continue;
1623 /* Actually this check is not a must constraint. With it, we can ensure
1624 conditional statement will always be executed in each iteration. */
1625 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1626 continue;
1628 gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1629 if (!cond)
1630 continue;
1632 edge branch_edge = get_cond_branch_to_split_loop (loop, cond);
1634 if (branch_edge)
1636 do_split_loop_on_cond (loop, branch_edge);
1637 do_split = true;
1638 break;
1642 delete info;
1643 loop->aux = NULL;
1645 return do_split;
1648 /* Main entry point. Perform loop splitting on all suitable loops. */
1650 static unsigned int
1651 tree_ssa_split_loops (void)
1653 bool changed = false;
1655 gcc_assert (scev_initialized_p ());
1657 calculate_dominance_info (CDI_POST_DOMINATORS);
1659 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1660 loop->aux = NULL;
1662 /* Go through all loops starting from innermost. */
1663 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1665 if (loop->aux)
1667 /* If any of our inner loops was split, don't split us,
1668 and mark our containing loop as having had splits as well.
1669 This allows for delaying SSA update. */
1670 loop_outer (loop)->aux = loop;
1671 continue;
1674 if (optimize_loop_for_size_p (loop))
1675 continue;
1677 if (split_loop (loop) || split_loop_on_cond (loop))
1679 /* Mark our containing loop as having had some split inner loops. */
1680 loop_outer (loop)->aux = loop;
1681 changed = true;
1685 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1686 loop->aux = NULL;
1688 clear_aux_for_blocks ();
1690 free_dominance_info (CDI_POST_DOMINATORS);
1692 if (changed)
1694 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1695 return TODO_cleanup_cfg;
1697 return 0;
1700 /* Loop splitting pass. */
1702 namespace {
1704 const pass_data pass_data_loop_split =
1706 GIMPLE_PASS, /* type */
1707 "lsplit", /* name */
1708 OPTGROUP_LOOP, /* optinfo_flags */
1709 TV_LOOP_SPLIT, /* tv_id */
1710 PROP_cfg, /* properties_required */
1711 0, /* properties_provided */
1712 0, /* properties_destroyed */
1713 0, /* todo_flags_start */
1714 0, /* todo_flags_finish */
1717 class pass_loop_split : public gimple_opt_pass
1719 public:
1720 pass_loop_split (gcc::context *ctxt)
1721 : gimple_opt_pass (pass_data_loop_split, ctxt)
1724 /* opt_pass methods: */
1725 bool gate (function *) final override { return flag_split_loops != 0; }
1726 unsigned int execute (function *) final override;
1728 }; // class pass_loop_split
1730 unsigned int
1731 pass_loop_split::execute (function *fun)
1733 if (number_of_loops (fun) <= 1)
1734 return 0;
1736 return tree_ssa_split_loops ();
1739 } // anon namespace
1741 gimple_opt_pass *
1742 make_pass_loop_split (gcc::context *ctxt)
1744 return new pass_loop_split (ctxt);