Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop-split.c
blob3f6ad04662352d682c48ec04ddd688dbc9ea8ae1
1 /* Loop splitting.
2 Copyright (C) 2015-2021 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 gimple *last;
80 gcond *stmt;
81 affine_iv iv2;
83 /* BB must end in a simple conditional jump. */
84 last = last_stmt (bb);
85 if (!last || gimple_code (last) != GIMPLE_COND)
86 return NULL_TREE;
87 stmt = as_a <gcond *> (last);
89 enum tree_code code = gimple_cond_code (stmt);
91 /* Only handle relational comparisons, for equality and non-equality
92 we'd have to split the loop into two loops and a middle statement. */
93 switch (code)
95 case LT_EXPR:
96 case LE_EXPR:
97 case GT_EXPR:
98 case GE_EXPR:
99 break;
100 default:
101 return NULL_TREE;
104 if (loop_exits_from_bb_p (loop, bb))
105 return NULL_TREE;
107 tree op0 = gimple_cond_lhs (stmt);
108 tree op1 = gimple_cond_rhs (stmt);
109 class loop *useloop = loop_containing_stmt (stmt);
111 if (!simple_iv (loop, useloop, op0, iv, false))
112 return NULL_TREE;
113 if (!simple_iv (loop, useloop, op1, &iv2, false))
114 return NULL_TREE;
116 /* Make it so that the first argument of the condition is
117 the looping one. */
118 if (!integer_zerop (iv2.step))
120 std::swap (op0, op1);
121 std::swap (*iv, iv2);
122 code = swap_tree_comparison (code);
123 gimple_cond_set_condition (stmt, code, op0, op1);
124 update_stmt (stmt);
126 else if (integer_zerop (iv->step))
127 return NULL_TREE;
128 if (!integer_zerop (iv2.step))
129 return NULL_TREE;
130 if (!iv->no_overflow)
131 return NULL_TREE;
133 if (dump_file && (dump_flags & TDF_DETAILS))
135 fprintf (dump_file, "Found potential split point: ");
136 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
137 fprintf (dump_file, " { ");
138 print_generic_expr (dump_file, iv->base, TDF_SLIM);
139 fprintf (dump_file, " + I*");
140 print_generic_expr (dump_file, iv->step, TDF_SLIM);
141 fprintf (dump_file, " } %s ", get_tree_code_name (code));
142 print_generic_expr (dump_file, iv2.base, TDF_SLIM);
143 fprintf (dump_file, "\n");
146 *border = iv2.base;
147 return op0;
150 /* Given a GUARD conditional stmt inside LOOP, which we want to make always
151 true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
152 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
153 exit test statement to loop back only if the GUARD statement will
154 also be true/false in the next iteration. */
156 static void
157 patch_loop_exit (class loop *loop, gcond *guard, tree nextval, tree newbound,
158 bool initial_true)
160 edge exit = single_exit (loop);
161 gcond *stmt = as_a <gcond *> (last_stmt (exit->src));
162 gimple_cond_set_condition (stmt, gimple_cond_code (guard),
163 nextval, newbound);
164 update_stmt (stmt);
166 edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
168 exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
169 stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
171 if (initial_true)
173 exit->flags |= EDGE_FALSE_VALUE;
174 stay->flags |= EDGE_TRUE_VALUE;
176 else
178 exit->flags |= EDGE_TRUE_VALUE;
179 stay->flags |= EDGE_FALSE_VALUE;
183 /* Give an induction variable GUARD_IV, and its affine descriptor IV,
184 find the loop phi node in LOOP defining it directly, or create
185 such phi node. Return that phi node. */
187 static gphi *
188 find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/)
190 gimple *def = SSA_NAME_DEF_STMT (guard_iv);
191 gphi *phi;
192 if ((phi = dyn_cast <gphi *> (def))
193 && gimple_bb (phi) == loop->header)
194 return phi;
196 /* XXX Create the PHI instead. */
197 return NULL;
200 /* Returns true if the exit values of all loop phi nodes can be
201 determined easily (i.e. that connect_loop_phis can determine them). */
203 static bool
204 easy_exit_values (class loop *loop)
206 edge exit = single_exit (loop);
207 edge latch = loop_latch_edge (loop);
208 gphi_iterator psi;
210 /* Currently we regard the exit values as easy if they are the same
211 as the value over the backedge. Which is the case if the definition
212 of the backedge value dominates the exit edge. */
213 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
215 gphi *phi = psi.phi ();
216 tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
217 basic_block bb;
218 if (TREE_CODE (next) == SSA_NAME
219 && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
220 && !dominated_by_p (CDI_DOMINATORS, exit->src, bb))
221 return false;
224 return true;
227 /* This function updates the SSA form after connect_loops made a new
228 edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
229 conditional). I.e. the second loop can now be entered either
230 via the original entry or via NEW_E, so the entry values of LOOP2
231 phi nodes are either the original ones or those at the exit
232 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting
233 this. The loops need to fulfill easy_exit_values(). */
235 static void
236 connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e)
238 basic_block rest = loop_preheader_edge (loop2)->src;
239 gcc_assert (new_e->dest == rest);
240 edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
242 edge firste = loop_preheader_edge (loop1);
243 edge seconde = loop_preheader_edge (loop2);
244 edge firstn = loop_latch_edge (loop1);
245 gphi_iterator psi_first, psi_second;
246 for (psi_first = gsi_start_phis (loop1->header),
247 psi_second = gsi_start_phis (loop2->header);
248 !gsi_end_p (psi_first);
249 gsi_next (&psi_first), gsi_next (&psi_second))
251 tree init, next, new_init;
252 use_operand_p op;
253 gphi *phi_first = psi_first.phi ();
254 gphi *phi_second = psi_second.phi ();
256 init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
257 next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
258 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
259 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
261 /* Prefer using original variable as a base for the new ssa name.
262 This is necessary for virtual ops, and useful in order to avoid
263 losing debug info for real ops. */
264 if (TREE_CODE (next) == SSA_NAME
265 && useless_type_conversion_p (TREE_TYPE (next),
266 TREE_TYPE (init)))
267 new_init = copy_ssa_name (next);
268 else if (TREE_CODE (init) == SSA_NAME
269 && useless_type_conversion_p (TREE_TYPE (init),
270 TREE_TYPE (next)))
271 new_init = copy_ssa_name (init);
272 else if (useless_type_conversion_p (TREE_TYPE (next),
273 TREE_TYPE (init)))
274 new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
275 "unrinittmp");
276 else
277 new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
278 "unrinittmp");
280 gphi * newphi = create_phi_node (new_init, rest);
281 add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
282 add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
283 SET_USE (op, new_init);
287 /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
288 they are still equivalent and placed in two arms of a diamond, like so:
290 .------if (cond)------.
292 pre1 pre2
294 .--->h1 h2<----.
295 | | | |
296 | ex1---. .---ex2 |
297 | / | | \ |
298 '---l1 X | l2---'
301 '--->join<---'
303 This function transforms the program such that LOOP1 is conditionally
304 falling through to LOOP2, or skipping it. This is done by splitting
305 the ex1->join edge at X in the diagram above, and inserting a condition
306 whose one arm goes to pre2, resulting in this situation:
308 .------if (cond)------.
310 pre1 .---------->pre2
311 | | |
312 .--->h1 | h2<----.
313 | | | | |
314 | ex1---. | .---ex2 |
315 | / v | | \ |
316 '---l1 skip---' | l2---'
319 '--->join<---'
322 The condition used is the exit condition of LOOP1, which effectively means
323 that when the first loop exits (for whatever reason) but the real original
324 exit expression is still false the second loop will be entered.
325 The function returns the new edge cond->pre2.
327 This doesn't update the SSA form, see connect_loop_phis for that. */
329 static edge
330 connect_loops (class loop *loop1, class loop *loop2)
332 edge exit = single_exit (loop1);
333 basic_block skip_bb = split_edge (exit);
334 gcond *skip_stmt;
335 gimple_stmt_iterator gsi;
336 edge new_e, skip_e;
338 gimple *stmt = last_stmt (exit->src);
339 skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
340 gimple_cond_lhs (stmt),
341 gimple_cond_rhs (stmt),
342 NULL_TREE, NULL_TREE);
343 gsi = gsi_last_bb (skip_bb);
344 gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
346 skip_e = EDGE_SUCC (skip_bb, 0);
347 skip_e->flags &= ~EDGE_FALLTHRU;
348 new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
349 if (exit->flags & EDGE_TRUE_VALUE)
351 skip_e->flags |= EDGE_TRUE_VALUE;
352 new_e->flags |= EDGE_FALSE_VALUE;
354 else
356 skip_e->flags |= EDGE_FALSE_VALUE;
357 new_e->flags |= EDGE_TRUE_VALUE;
360 new_e->probability = profile_probability::likely ();
361 skip_e->probability = new_e->probability.invert ();
363 return new_e;
366 /* This returns the new bound for iterations given the original iteration
367 space in NITER, an arbitrary new bound BORDER, assumed to be some
368 comparison value with a different IV, the initial value GUARD_INIT of
369 that other IV, and the comparison code GUARD_CODE that compares
370 that other IV with BORDER. We return an SSA name, and place any
371 necessary statements for that computation into *STMTS.
373 For example for such a loop:
375 for (i = beg, j = guard_init; i < end; i++, j++)
376 if (j < border) // this is supposed to be true/false
379 we want to return a new bound (on j) that makes the loop iterate
380 as long as the condition j < border stays true. We also don't want
381 to iterate more often than the original loop, so we have to introduce
382 some cut-off as well (via min/max), effectively resulting in:
384 newend = min (end+guard_init-beg, border)
385 for (i = beg; j = guard_init; j < newend; i++, j++)
386 if (j < c)
389 Depending on the direction of the IVs and if the exit tests
390 are strict or non-strict we need to use MIN or MAX,
391 and add or subtract 1. This routine computes newend above. */
393 static tree
394 compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter,
395 tree border,
396 enum tree_code guard_code, tree guard_init)
398 /* The niter structure contains the after-increment IV, we need
399 the loop-enter base, so subtract STEP once. */
400 tree controlbase = force_gimple_operand (niter->control.base,
401 stmts, true, NULL_TREE);
402 tree controlstep = niter->control.step;
403 tree enddiff;
404 if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
406 controlstep = gimple_build (stmts, NEGATE_EXPR,
407 TREE_TYPE (controlstep), controlstep);
408 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
409 TREE_TYPE (controlbase),
410 controlbase, controlstep);
412 else
413 enddiff = gimple_build (stmts, MINUS_EXPR,
414 TREE_TYPE (controlbase),
415 controlbase, controlstep);
417 /* Compute end-beg. */
418 gimple_seq stmts2;
419 tree end = force_gimple_operand (niter->bound, &stmts2,
420 true, NULL_TREE);
421 gimple_seq_add_seq_without_update (stmts, stmts2);
422 if (POINTER_TYPE_P (TREE_TYPE (enddiff)))
424 tree tem = gimple_convert (stmts, sizetype, enddiff);
425 tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem);
426 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
427 TREE_TYPE (enddiff),
428 end, tem);
430 else
431 enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
432 end, enddiff);
434 /* Compute guard_init + (end-beg). */
435 tree newbound;
436 enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
437 if (POINTER_TYPE_P (TREE_TYPE (guard_init)))
439 enddiff = gimple_convert (stmts, sizetype, enddiff);
440 newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
441 TREE_TYPE (guard_init),
442 guard_init, enddiff);
444 else
445 newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
446 guard_init, enddiff);
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)
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;
461 else
463 gcc_assert (niter->cmp == GT_EXPR);
464 if (guard_code == GE_EXPR || guard_code == LT_EXPR)
465 addbound = 1;
466 minmax = MAX_EXPR;
469 if (addbound)
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));
482 tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
483 border, newbound);
484 return newend;
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. */
493 static bool
494 split_loop (class loop *loop1)
496 class tree_niter_desc niter;
497 basic_block *bbs;
498 unsigned i;
499 bool changed = false;
500 tree guard_iv;
501 tree border = NULL_TREE;
502 affine_iv iv;
504 if (!single_exit (loop1)
505 /* ??? We could handle non-empty latches when we split the latch edge
506 (not the exit edge), and put the new exit condition in the new block.
507 OTOH this executes some code unconditionally that might have been
508 skipped by the original exit before. */
509 || !empty_block_p (loop1->latch)
510 || !easy_exit_values (loop1)
511 || !number_of_iterations_exit (loop1, single_exit (loop1), &niter,
512 false, true)
513 || niter.cmp == ERROR_MARK
514 /* We can't yet handle loops controlled by a != predicate. */
515 || niter.cmp == NE_EXPR)
516 return false;
518 bbs = get_loop_body (loop1);
520 if (!can_copy_bbs_p (bbs, loop1->num_nodes))
522 free (bbs);
523 return false;
526 /* Find a splitting opportunity. */
527 for (i = 0; i < loop1->num_nodes; i++)
528 if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
530 /* Handling opposite steps is not implemented yet. Neither
531 is handling different step sizes. */
532 if ((tree_int_cst_sign_bit (iv.step)
533 != tree_int_cst_sign_bit (niter.control.step))
534 || !tree_int_cst_equal (iv.step, niter.control.step))
535 continue;
537 /* Find a loop PHI node that defines guard_iv directly,
538 or create one doing that. */
539 gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
540 if (!phi)
541 continue;
542 gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i]));
543 tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
544 loop_preheader_edge (loop1));
545 enum tree_code guard_code = gimple_cond_code (guard_stmt);
547 /* Loop splitting is implemented by versioning the loop, placing
548 the new loop after the old loop, make the first loop iterate
549 as long as the conditional stays true (or false) and let the
550 second (new) loop handle the rest of the iterations.
552 First we need to determine if the condition will start being true
553 or false in the first loop. */
554 bool initial_true;
555 switch (guard_code)
557 case LT_EXPR:
558 case LE_EXPR:
559 initial_true = !tree_int_cst_sign_bit (iv.step);
560 break;
561 case GT_EXPR:
562 case GE_EXPR:
563 initial_true = tree_int_cst_sign_bit (iv.step);
564 break;
565 default:
566 gcc_unreachable ();
569 /* Build a condition that will skip the first loop when the
570 guard condition won't ever be true (or false). */
571 gimple_seq stmts2;
572 border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
573 if (stmts2)
574 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
575 stmts2);
576 tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
577 if (!initial_true)
578 cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
580 /* Now version the loop, placing loop2 after loop1 connecting
581 them, and fix up SSA form for that. */
582 initialize_original_copy_tables ();
583 basic_block cond_bb;
585 class loop *loop2 = loop_version (loop1, cond, &cond_bb,
586 profile_probability::always (),
587 profile_probability::always (),
588 profile_probability::always (),
589 profile_probability::always (),
590 true);
591 gcc_assert (loop2);
593 edge new_e = connect_loops (loop1, loop2);
594 connect_loop_phis (loop1, loop2, new_e);
596 /* The iterations of the second loop is now already
597 exactly those that the first loop didn't do, but the
598 iteration space of the first loop is still the original one.
599 Compute the new bound for the guarding IV and patch the
600 loop exit to use it instead of original IV and bound. */
601 gimple_seq stmts = NULL;
602 tree newend = compute_new_first_bound (&stmts, &niter, border,
603 guard_code, guard_init);
604 if (stmts)
605 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
606 stmts);
607 tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
608 patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
610 /* Finally patch out the two copies of the condition to be always
611 true/false (or opposite). */
612 gcond *force_true = as_a<gcond *> (last_stmt (bbs[i]));
613 gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i])));
614 if (!initial_true)
615 std::swap (force_true, force_false);
616 gimple_cond_make_true (force_true);
617 gimple_cond_make_false (force_false);
618 update_stmt (force_true);
619 update_stmt (force_false);
621 free_original_copy_tables ();
623 changed = true;
624 if (dump_file && (dump_flags & TDF_DETAILS))
625 fprintf (dump_file, ";; Loop split.\n");
627 if (dump_enabled_p ())
628 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, guard_stmt, "loop split\n");
630 /* Only deal with the first opportunity. */
631 break;
634 free (bbs);
635 return changed;
638 /* Another transformation of loops like:
640 for (i = INIT (); CHECK (i); i = NEXT ())
642 if (expr (a_1, a_2, ..., a_n)) // expr is pure
643 a_j = ...; // change at least one a_j
644 else
645 S; // not change any a_j
648 into:
650 for (i = INIT (); CHECK (i); i = NEXT ())
652 if (expr (a_1, a_2, ..., a_n))
653 a_j = ...;
654 else
657 i = NEXT ();
658 break;
662 for (; CHECK (i); i = NEXT ())
669 /* Data structure to hold temporary information during loop split upon
670 semi-invariant conditional statement. */
671 class split_info {
672 public:
673 /* Array of all basic blocks in a loop, returned by get_loop_body(). */
674 basic_block *bbs;
676 /* All memory store/clobber statements in a loop. */
677 auto_vec<gimple *> memory_stores;
679 /* Whether above memory stores vector has been filled. */
680 int need_init;
682 /* Control dependencies of basic blocks in a loop. */
683 auto_vec<hash_set<basic_block> *> control_deps;
685 split_info () : bbs (NULL), need_init (true) { }
687 ~split_info ()
689 if (bbs)
690 free (bbs);
692 for (unsigned i = 0; i < control_deps.length (); i++)
693 delete control_deps[i];
697 /* Find all statements with memory-write effect in LOOP, including memory
698 store and non-pure function call, and keep those in a vector. This work
699 is only done one time, for the vector should be constant during analysis
700 stage of semi-invariant condition. */
702 static void
703 find_vdef_in_loop (struct loop *loop)
705 split_info *info = (split_info *) loop->aux;
706 gphi *vphi = get_virtual_phi (loop->header);
708 /* Indicate memory store vector has been filled. */
709 info->need_init = false;
711 /* If loop contains memory operation, there must be a virtual PHI node in
712 loop header basic block. */
713 if (vphi == NULL)
714 return;
716 /* All virtual SSA names inside the loop are connected to be a cyclic
717 graph via virtual PHI nodes. The virtual PHI node in loop header just
718 links the first and the last virtual SSA names, by using the last as
719 PHI operand to define the first. */
720 const edge latch = loop_latch_edge (loop);
721 const tree first = gimple_phi_result (vphi);
722 const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
724 /* The virtual SSA cyclic graph might consist of only one SSA name, who
725 is defined by itself.
727 .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
729 This means the loop contains only memory loads, so we can skip it. */
730 if (first == last)
731 return;
733 auto_vec<gimple *> other_stores;
734 auto_vec<tree> worklist;
735 auto_bitmap visited;
737 bitmap_set_bit (visited, SSA_NAME_VERSION (first));
738 bitmap_set_bit (visited, SSA_NAME_VERSION (last));
739 worklist.safe_push (last);
743 tree vuse = worklist.pop ();
744 gimple *stmt = SSA_NAME_DEF_STMT (vuse);
746 /* We mark the first and last SSA names as visited at the beginning,
747 and reversely start the process from the last SSA name towards the
748 first, which ensures that this do-while will not touch SSA names
749 defined outside the loop. */
750 gcc_assert (gimple_bb (stmt)
751 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
753 if (gimple_code (stmt) == GIMPLE_PHI)
755 gphi *phi = as_a <gphi *> (stmt);
757 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
759 tree arg = gimple_phi_arg_def (stmt, i);
761 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
762 worklist.safe_push (arg);
765 else
767 tree prev = gimple_vuse (stmt);
769 /* Non-pure call statement is conservatively assumed to impact all
770 memory locations. So place call statements ahead of other memory
771 stores in the vector with an idea of using them as shortcut
772 terminators to memory alias analysis. */
773 if (gimple_code (stmt) == GIMPLE_CALL)
774 info->memory_stores.safe_push (stmt);
775 else
776 other_stores.safe_push (stmt);
778 if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
779 worklist.safe_push (prev);
781 } while (!worklist.is_empty ());
783 info->memory_stores.safe_splice (other_stores);
786 /* Two basic blocks have equivalent control dependency if one dominates to
787 the other, and it is post-dominated by the latter. Given a basic block
788 BB in LOOP, find farest equivalent dominating basic block. For BB, there
789 is a constraint that BB does not post-dominate loop header of LOOP, this
790 means BB is control-dependent on at least one basic block in LOOP. */
792 static basic_block
793 get_control_equiv_head_block (struct loop *loop, basic_block bb)
795 while (!bb->aux)
797 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
799 gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb));
801 if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb))
802 break;
804 bb = dom_bb;
806 return bb;
809 /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
810 dependent on. */
812 static hash_set<basic_block> *
813 find_control_dep_blocks (struct loop *loop, basic_block bb)
815 /* BB has same control dependency as loop header, then it is not control-
816 dependent on any basic block in LOOP. */
817 if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb))
818 return NULL;
820 basic_block equiv_head = get_control_equiv_head_block (loop, bb);
822 if (equiv_head->aux)
824 /* There is a basic block containing control dependency equivalent
825 to BB. No need to recompute that, and also set this information
826 to other equivalent basic blocks. */
827 for (; bb != equiv_head;
828 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
829 bb->aux = equiv_head->aux;
830 return (hash_set<basic_block> *) equiv_head->aux;
833 /* A basic block X is control-dependent on another Y iff there exists
834 a path from X to Y, in which every basic block other than X and Y
835 is post-dominated by Y, but X is not post-dominated by Y.
837 According to this rule, traverse basic blocks in the loop backwards
838 starting from BB, if a basic block is post-dominated by BB, extend
839 current post-dominating path to this block, otherwise it is another
840 one that BB is control-dependent on. */
842 auto_vec<basic_block> pdom_worklist;
843 hash_set<basic_block> pdom_visited;
844 hash_set<basic_block> *dep_bbs = new hash_set<basic_block>;
846 pdom_worklist.safe_push (equiv_head);
850 basic_block pdom_bb = pdom_worklist.pop ();
851 edge_iterator ei;
852 edge e;
854 if (pdom_visited.add (pdom_bb))
855 continue;
857 FOR_EACH_EDGE (e, ei, pdom_bb->preds)
859 basic_block pred_bb = e->src;
861 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb))
863 dep_bbs->add (pred_bb);
864 continue;
867 pred_bb = get_control_equiv_head_block (loop, pred_bb);
869 if (pdom_visited.contains (pred_bb))
870 continue;
872 if (!pred_bb->aux)
874 pdom_worklist.safe_push (pred_bb);
875 continue;
878 /* If control dependency of basic block is available, fast extend
879 post-dominating path using the information instead of advancing
880 forward step-by-step. */
881 hash_set<basic_block> *pred_dep_bbs
882 = (hash_set<basic_block> *) pred_bb->aux;
884 for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin ();
885 iter != pred_dep_bbs->end (); ++iter)
887 basic_block pred_dep_bb = *iter;
889 /* Basic blocks can either be in control dependency of BB, or
890 must be post-dominated by BB, if so, extend the path from
891 these basic blocks. */
892 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb))
893 dep_bbs->add (pred_dep_bb);
894 else if (!pdom_visited.contains (pred_dep_bb))
895 pdom_worklist.safe_push (pred_dep_bb);
898 } while (!pdom_worklist.is_empty ());
900 /* Record computed control dependencies in loop so that we can reach them
901 when reclaiming resources. */
902 ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs);
904 /* Associate control dependence with related equivalent basic blocks. */
905 for (equiv_head->aux = dep_bbs; bb != equiv_head;
906 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
907 bb->aux = dep_bbs;
909 return dep_bbs;
912 /* Forward declaration */
914 static bool
915 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
916 const_basic_block skip_head,
917 hash_map<gimple *, bool> &stmt_stat);
919 /* Given STMT, memory load or pure call statement, check whether it is impacted
920 by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
921 trace is composed of SKIP_HEAD and those basic block dominated by it, always
922 corresponds to one branch of a conditional statement). If SKIP_HEAD is
923 NULL, all basic blocks of LOOP are checked. */
925 static bool
926 vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
927 const_basic_block skip_head)
929 split_info *info = (split_info *) loop->aux;
930 tree rhs = NULL_TREE;
931 ao_ref ref;
932 gimple *store;
933 unsigned i;
935 /* Collect memory store/clobber statements if haven't done that. */
936 if (info->need_init)
937 find_vdef_in_loop (loop);
939 if (is_gimple_assign (stmt))
940 rhs = gimple_assign_rhs1 (stmt);
942 ao_ref_init (&ref, rhs);
944 FOR_EACH_VEC_ELT (info->memory_stores, i, store)
946 /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */
947 if (skip_head
948 && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head))
949 continue;
951 if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
952 return false;
955 return true;
958 /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
959 certain iteration of LOOP, check whether an SSA name (NAME) remains
960 unchanged in next iteration. We call this characteristic semi-
961 invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic
962 blocks and control flows in the loop will be considered. Semi-invariant
963 state of checked statement is cached in hash map STMT_STAT to avoid
964 redundant computation in possible following re-check. */
966 static inline bool
967 ssa_semi_invariant_p (struct loop *loop, tree name,
968 const_basic_block skip_head,
969 hash_map<gimple *, bool> &stmt_stat)
971 gimple *def = SSA_NAME_DEF_STMT (name);
972 const_basic_block def_bb = gimple_bb (def);
974 /* An SSA name defined outside loop is definitely semi-invariant. */
975 if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
976 return true;
978 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
979 return false;
981 return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat);
984 /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
985 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
986 are excluded from LOOP. */
988 static bool
989 loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi,
990 const_basic_block skip_head)
992 const_edge latch = loop_latch_edge (loop);
993 tree name = gimple_phi_result (loop_phi);
994 tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch);
996 gcc_checking_assert (from);
998 /* Loop iteration PHI node locates in loop header, and it has two source
999 operands, one is an initial value coming from outside the loop, the other
1000 is a value through latch of the loop, which is derived in last iteration,
1001 we call the latter latch value. From the PHI node to definition of latch
1002 value, if excluding branch trace starting from SKIP_HEAD, except copy-
1003 assignment or likewise, there is no other kind of value redefinition, SSA
1004 name defined by the PHI node is semi-invariant.
1006 loop entry
1007 | .--- latch ---.
1008 | | |
1009 v v |
1010 x_1 = PHI <x_0, x_3> |
1013 .------- if (cond) -------. |
1014 | | |
1015 | [ SKIP ] |
1016 | | |
1017 | x_2 = ... |
1018 | | |
1019 '---- T ---->.<---- F ----' |
1022 x_3 = PHI <x_1, x_2> |
1024 '----------------------'
1026 Suppose in certain iteration, execution flow in above graph goes through
1027 true branch, which means that one source value to define x_3 in false
1028 branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
1029 iterations is defined by x_3, we know that x_1 will never changed if COND
1030 always chooses true branch from then on. */
1032 while (from != name)
1034 /* A new value comes from a CONSTANT. */
1035 if (TREE_CODE (from) != SSA_NAME)
1036 return false;
1038 gimple *stmt = SSA_NAME_DEF_STMT (from);
1039 const_basic_block bb = gimple_bb (stmt);
1041 /* A new value comes from outside the loop. */
1042 if (!bb || !flow_bb_inside_loop_p (loop, bb))
1043 return false;
1045 from = NULL_TREE;
1047 if (gimple_code (stmt) == GIMPLE_PHI)
1049 gphi *phi = as_a <gphi *> (stmt);
1051 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1053 if (skip_head)
1055 const_edge e = gimple_phi_arg_edge (phi, i);
1057 /* Don't consider redefinitions in excluded basic blocks. */
1058 if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head))
1059 continue;
1062 tree arg = gimple_phi_arg_def (phi, i);
1064 if (!from)
1065 from = arg;
1066 else if (!operand_equal_p (from, arg, 0))
1067 /* There are more than one source operands that provide
1068 different values to the SSA name, it is variant. */
1069 return false;
1072 else if (gimple_code (stmt) == GIMPLE_ASSIGN)
1074 /* For simple value copy, check its rhs instead. */
1075 if (gimple_assign_ssa_name_copy_p (stmt))
1076 from = gimple_assign_rhs1 (stmt);
1079 /* Any other kind of definition is deemed to introduce a new value
1080 to the SSA name. */
1081 if (!from)
1082 return false;
1084 return true;
1087 /* Check whether conditional predicates that BB is control-dependent on, are
1088 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1089 are excluded from LOOP. Semi-invariant state of checked statement is cached
1090 in hash map STMT_STAT. */
1092 static bool
1093 control_dep_semi_invariant_p (struct loop *loop, basic_block bb,
1094 const_basic_block skip_head,
1095 hash_map<gimple *, bool> &stmt_stat)
1097 hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb);
1099 if (!dep_bbs)
1100 return true;
1102 for (hash_set<basic_block>::iterator iter = dep_bbs->begin ();
1103 iter != dep_bbs->end (); ++iter)
1105 gimple *last = last_stmt (*iter);
1107 if (!last)
1108 return false;
1110 /* Only check condition predicates. */
1111 if (gimple_code (last) != GIMPLE_COND
1112 && gimple_code (last) != GIMPLE_SWITCH)
1113 return false;
1115 if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat))
1116 return false;
1119 return true;
1122 /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
1123 semi-invariant, consequently, all its defined values are semi-invariant.
1124 Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
1125 Semi-invariant state of checked statement is cached in hash map
1126 STMT_STAT. */
1128 static bool
1129 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
1130 const_basic_block skip_head,
1131 hash_map<gimple *, bool> &stmt_stat)
1133 bool existed;
1134 bool &invar = stmt_stat.get_or_insert (stmt, &existed);
1136 if (existed)
1137 return invar;
1139 /* A statement might depend on itself, which is treated as variant. So set
1140 state of statement under check to be variant to ensure that. */
1141 invar = false;
1143 if (gimple_code (stmt) == GIMPLE_PHI)
1145 gphi *phi = as_a <gphi *> (stmt);
1147 if (gimple_bb (stmt) == loop->header)
1149 /* If the entry value is subject to abnormal coalescing
1150 avoid the transform since we're going to duplicate the
1151 loop header and thus likely introduce overlapping life-ranges
1152 between the PHI def and the entry on the path when the
1153 first loop is skipped. */
1154 tree entry_def
1155 = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1156 if (TREE_CODE (entry_def) == SSA_NAME
1157 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (entry_def))
1158 return false;
1159 invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head);
1160 return invar;
1163 /* For a loop PHI node that does not locate in loop header, it is semi-
1164 invariant only if two conditions are met. The first is its source
1165 values are derived from CONSTANT (including loop-invariant value), or
1166 from SSA name defined by semi-invariant loop iteration PHI node. The
1167 second is its source incoming edges are control-dependent on semi-
1168 invariant conditional predicates. */
1169 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1171 const_edge e = gimple_phi_arg_edge (phi, i);
1172 tree arg = gimple_phi_arg_def (phi, i);
1174 if (TREE_CODE (arg) == SSA_NAME)
1176 if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat))
1177 return false;
1179 /* If source value is defined in location from where the source
1180 edge comes in, no need to check control dependency again
1181 since this has been done in above SSA name check stage. */
1182 if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1183 continue;
1186 if (!control_dep_semi_invariant_p (loop, e->src, skip_head,
1187 stmt_stat))
1188 return false;
1191 else
1193 ssa_op_iter iter;
1194 tree use;
1196 /* Volatile memory load or return of normal (non-const/non-pure) call
1197 should not be treated as constant in each iteration of loop. */
1198 if (gimple_has_side_effects (stmt))
1199 return false;
1201 /* Check if any memory store may kill memory load at this place. */
1202 if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head))
1203 return false;
1205 /* Although operand of a statement might be SSA name, CONSTANT or
1206 VARDECL, here we only need to check SSA name operands. This is
1207 because check on VARDECL operands, which involve memory loads,
1208 must have been done prior to invocation of this function in
1209 vuse_semi_invariant_p. */
1210 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1211 if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat))
1212 return false;
1215 if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head,
1216 stmt_stat))
1217 return false;
1219 /* Here we SHOULD NOT use invar = true, since hash map might be changed due
1220 to new insertion, and thus invar may point to invalid memory. */
1221 stmt_stat.put (stmt, true);
1222 return true;
1225 /* A helper function to check whether STMT is semi-invariant in LOOP. Basic
1226 blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */
1228 static bool
1229 stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
1230 const_basic_block skip_head)
1232 hash_map<gimple *, bool> stmt_stat;
1233 return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat);
1236 /* Determine when conditional statement never transfers execution to one of its
1237 branch, whether we can remove the branch's leading basic block (BRANCH_BB)
1238 and those basic blocks dominated by BRANCH_BB. */
1240 static bool
1241 branch_removable_p (basic_block branch_bb)
1243 edge_iterator ei;
1244 edge e;
1246 if (single_pred_p (branch_bb))
1247 return true;
1249 FOR_EACH_EDGE (e, ei, branch_bb->preds)
1251 if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
1252 continue;
1254 if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
1255 continue;
1257 /* The branch can be reached from opposite branch, or from some
1258 statement not dominated by the conditional statement. */
1259 return false;
1262 return true;
1265 /* Find out which branch of a conditional statement (COND) is invariant in the
1266 execution context of LOOP. That is: once the branch is selected in certain
1267 iteration of the loop, any operand that contributes to computation of the
1268 conditional statement remains unchanged in all following iterations. */
1270 static edge
1271 get_cond_invariant_branch (struct loop *loop, gcond *cond)
1273 basic_block cond_bb = gimple_bb (cond);
1274 basic_block targ_bb[2];
1275 bool invar[2];
1276 unsigned invar_checks = 0;
1278 for (unsigned i = 0; i < 2; i++)
1280 targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
1282 /* One branch directs to loop exit, no need to perform loop split upon
1283 this conditional statement. Firstly, it is trivial if the exit branch
1284 is semi-invariant, for the statement is just to break loop. Secondly,
1285 if the opposite branch is semi-invariant, it means that the statement
1286 is real loop-invariant, which is covered by loop unswitch. */
1287 if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
1288 return NULL;
1291 for (unsigned i = 0; i < 2; i++)
1293 invar[!i] = false;
1295 if (!branch_removable_p (targ_bb[i]))
1296 continue;
1298 /* Given a semi-invariant branch, if its opposite branch dominates
1299 loop latch, it and its following trace will only be executed in
1300 final iteration of loop, namely it is not part of repeated body
1301 of the loop. Similar to the above case that the branch is loop
1302 exit, no need to split loop. */
1303 if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
1304 continue;
1306 invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
1307 invar_checks++;
1310 /* With both branches being invariant (handled by loop unswitch) or
1311 variant is not what we want. */
1312 if (invar[0] ^ !invar[1])
1313 return NULL;
1315 /* Found a real loop-invariant condition, do nothing. */
1316 if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
1317 return NULL;
1319 return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1);
1322 /* Calculate increased code size measured by estimated insn number if applying
1323 loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */
1325 static int
1326 compute_added_num_insns (struct loop *loop, const_edge branch_edge)
1328 basic_block cond_bb = branch_edge->src;
1329 unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge;
1330 basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest;
1331 basic_block *bbs = ((split_info *) loop->aux)->bbs;
1332 int num = 0;
1334 for (unsigned i = 0; i < loop->num_nodes; i++)
1336 /* Do no count basic blocks only in opposite branch. */
1337 if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb))
1338 continue;
1340 num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
1343 /* It is unnecessary to evaluate expression of the conditional statement
1344 in new loop that contains only invariant branch. This expression should
1345 be constant value (either true or false). Exclude code size of insns
1346 that contribute to computation of the expression. */
1348 auto_vec<gimple *> worklist;
1349 hash_set<gimple *> removed;
1350 gimple *stmt = last_stmt (cond_bb);
1352 worklist.safe_push (stmt);
1353 removed.add (stmt);
1354 num -= estimate_num_insns (stmt, &eni_size_weights);
1358 ssa_op_iter opnd_iter;
1359 use_operand_p opnd_p;
1361 stmt = worklist.pop ();
1362 FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE)
1364 tree opnd = USE_FROM_PTR (opnd_p);
1366 if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd))
1367 continue;
1369 gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd);
1370 use_operand_p use_p;
1371 imm_use_iterator use_iter;
1373 if (removed.contains (opnd_stmt)
1374 || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt)))
1375 continue;
1377 FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd)
1379 gimple *use_stmt = USE_STMT (use_p);
1381 if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt))
1383 opnd_stmt = NULL;
1384 break;
1388 if (opnd_stmt)
1390 worklist.safe_push (opnd_stmt);
1391 removed.add (opnd_stmt);
1392 num -= estimate_num_insns (opnd_stmt, &eni_size_weights);
1395 } while (!worklist.is_empty ());
1397 gcc_assert (num >= 0);
1398 return num;
1401 /* Find out loop-invariant branch of a conditional statement (COND) if it has,
1402 and check whether it is eligible and profitable to perform loop split upon
1403 this branch in LOOP. */
1405 static edge
1406 get_cond_branch_to_split_loop (struct loop *loop, gcond *cond)
1408 edge invar_branch = get_cond_invariant_branch (loop, cond);
1409 if (!invar_branch)
1410 return NULL;
1412 /* When accurate profile information is available, and execution
1413 frequency of the branch is too low, just let it go. */
1414 profile_probability prob = invar_branch->probability;
1415 if (prob.reliable_p ())
1417 int thres = param_min_loop_cond_split_prob;
1419 if (prob < profile_probability::always ().apply_scale (thres, 100))
1420 return NULL;
1423 /* Add a threshold for increased code size to disable loop split. */
1424 if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns)
1425 return NULL;
1427 return invar_branch;
1430 /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
1431 conditional statement, perform loop split transformation illustrated
1432 as the following graph.
1434 .-------T------ if (true) ------F------.
1435 | .---------------. |
1436 | | | |
1437 v | v v
1438 pre-header | pre-header
1439 | .------------. | | .------------.
1440 | | | | | | |
1441 | v | | | v |
1442 header | | header |
1443 | | | | |
1444 .--- if (cond) ---. | | .--- if (true) ---. |
1445 | | | | | | |
1446 invariant | | | invariant | |
1447 | | | | | | |
1448 '---T--->.<---F---' | | '---T--->.<---F---' |
1449 | | / | |
1450 stmts | / stmts |
1451 | F T | |
1452 / \ | / / \ |
1453 .-------* * [ if (cond) ] .-------* * |
1454 | | | | | |
1455 | latch | | latch |
1456 | | | | | |
1457 | '------------' | '------------'
1458 '------------------------. .-----------'
1459 loop1 | | loop2
1461 exits
1463 In the graph, loop1 represents the part derived from original one, and
1464 loop2 is duplicated using loop_version (), which corresponds to the part
1465 of original one being splitted out. In original latch edge of loop1, we
1466 insert a new conditional statement duplicated from the semi-invariant cond,
1467 and one of its branch goes back to loop1 header as a latch edge, and the
1468 other branch goes to loop2 pre-header as an entry edge. And also in loop2,
1469 we abandon the variant branch of the conditional statement by setting a
1470 constant bool condition, based on which branch is semi-invariant. */
1472 static bool
1473 do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
1475 basic_block cond_bb = invar_branch->src;
1476 bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE);
1477 gcond *cond = as_a <gcond *> (last_stmt (cond_bb));
1479 gcc_assert (cond_bb->loop_father == loop1);
1481 if (dump_enabled_p ())
1482 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
1483 "loop split on semi-invariant condition at %s branch\n",
1484 true_invar ? "true" : "false");
1486 initialize_original_copy_tables ();
1488 struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
1489 profile_probability::always (),
1490 profile_probability::never (),
1491 profile_probability::always (),
1492 profile_probability::always (),
1493 true);
1494 if (!loop2)
1496 free_original_copy_tables ();
1497 return false;
1500 basic_block cond_bb_copy = get_bb_copy (cond_bb);
1501 gcond *cond_copy = as_a<gcond *> (last_stmt (cond_bb_copy));
1503 /* Replace the condition in loop2 with a bool constant to let PassManager
1504 remove the variant branch after current pass completes. */
1505 if (true_invar)
1506 gimple_cond_make_true (cond_copy);
1507 else
1508 gimple_cond_make_false (cond_copy);
1510 update_stmt (cond_copy);
1512 /* Insert a new conditional statement on latch edge of loop1, its condition
1513 is duplicated from the semi-invariant. This statement acts as a switch
1514 to transfer execution from loop1 to loop2, when loop1 enters into
1515 invariant state. */
1516 basic_block latch_bb = split_edge (loop_latch_edge (loop1));
1517 basic_block break_bb = split_edge (single_pred_edge (latch_bb));
1518 gimple *break_cond = gimple_build_cond (gimple_cond_code(cond),
1519 gimple_cond_lhs (cond),
1520 gimple_cond_rhs (cond),
1521 NULL_TREE, NULL_TREE);
1523 gimple_stmt_iterator gsi = gsi_last_bb (break_bb);
1524 gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
1526 edge to_loop1 = single_succ_edge (break_bb);
1527 edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);
1529 to_loop1->flags &= ~EDGE_FALLTHRU;
1530 to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
1531 to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
1533 /* Due to introduction of a control flow edge from loop1 latch to loop2
1534 pre-header, we should update PHIs in loop2 to reflect this connection
1535 between loop1 and loop2. */
1536 connect_loop_phis (loop1, loop2, to_loop2);
1538 free_original_copy_tables ();
1540 return true;
1543 /* Traverse all conditional statements in LOOP, to find out a good candidate
1544 upon which we can do loop split. */
1546 static bool
1547 split_loop_on_cond (struct loop *loop)
1549 split_info *info = new split_info ();
1550 basic_block *bbs = info->bbs = get_loop_body (loop);
1551 bool do_split = false;
1553 /* Allocate an area to keep temporary info, and associate its address
1554 with loop aux field. */
1555 loop->aux = info;
1557 for (unsigned i = 0; i < loop->num_nodes; i++)
1558 bbs[i]->aux = NULL;
1560 for (unsigned i = 0; i < loop->num_nodes; i++)
1562 basic_block bb = bbs[i];
1564 /* We only consider conditional statement, which be executed at most once
1565 in each iteration of the loop. So skip statements in inner loops. */
1566 if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP))
1567 continue;
1569 /* Actually this check is not a must constraint. With it, we can ensure
1570 conditional statement will always be executed in each iteration. */
1571 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1572 continue;
1574 gimple *last = last_stmt (bb);
1576 if (!last || gimple_code (last) != GIMPLE_COND)
1577 continue;
1579 gcond *cond = as_a <gcond *> (last);
1580 edge branch_edge = get_cond_branch_to_split_loop (loop, cond);
1582 if (branch_edge)
1584 do_split_loop_on_cond (loop, branch_edge);
1585 do_split = true;
1586 break;
1590 delete info;
1591 loop->aux = NULL;
1593 return do_split;
1596 /* Main entry point. Perform loop splitting on all suitable loops. */
1598 static unsigned int
1599 tree_ssa_split_loops (void)
1601 bool changed = false;
1603 gcc_assert (scev_initialized_p ());
1605 calculate_dominance_info (CDI_POST_DOMINATORS);
1607 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1608 loop->aux = NULL;
1610 /* Go through all loops starting from innermost. */
1611 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1613 if (loop->aux)
1615 /* If any of our inner loops was split, don't split us,
1616 and mark our containing loop as having had splits as well. */
1617 loop_outer (loop)->aux = loop;
1618 continue;
1621 if (optimize_loop_for_size_p (loop))
1622 continue;
1624 if (split_loop (loop) || split_loop_on_cond (loop))
1626 /* Mark our containing loop as having had some split inner loops. */
1627 loop_outer (loop)->aux = loop;
1628 changed = true;
1632 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1633 loop->aux = NULL;
1635 clear_aux_for_blocks ();
1637 free_dominance_info (CDI_POST_DOMINATORS);
1639 if (changed)
1641 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1642 return TODO_cleanup_cfg;
1644 return 0;
1647 /* Loop splitting pass. */
1649 namespace {
1651 const pass_data pass_data_loop_split =
1653 GIMPLE_PASS, /* type */
1654 "lsplit", /* name */
1655 OPTGROUP_LOOP, /* optinfo_flags */
1656 TV_LOOP_SPLIT, /* tv_id */
1657 PROP_cfg, /* properties_required */
1658 0, /* properties_provided */
1659 0, /* properties_destroyed */
1660 0, /* todo_flags_start */
1661 0, /* todo_flags_finish */
1664 class pass_loop_split : public gimple_opt_pass
1666 public:
1667 pass_loop_split (gcc::context *ctxt)
1668 : gimple_opt_pass (pass_data_loop_split, ctxt)
1671 /* opt_pass methods: */
1672 virtual bool gate (function *) { return flag_split_loops != 0; }
1673 virtual unsigned int execute (function *);
1675 }; // class pass_loop_split
1677 unsigned int
1678 pass_loop_split::execute (function *fun)
1680 if (number_of_loops (fun) <= 1)
1681 return 0;
1683 return tree_ssa_split_loops ();
1686 } // anon namespace
1688 gimple_opt_pass *
1689 make_pass_loop_split (gcc::context *ctxt)
1691 return new pass_loop_split (ctxt);