Line data Source code
1 : /* Loop splitting.
2 : Copyright (C) 2015-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it
7 : under the terms of the GNU General Public License as published by the
8 : Free Software Foundation; either version 3, or (at your option) any
9 : later version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "tree.h"
25 : #include "gimple.h"
26 : #include "tree-pass.h"
27 : #include "ssa.h"
28 : #include "fold-const.h"
29 : #include "tree-cfg.h"
30 : #include "tree-ssa.h"
31 : #include "tree-ssa-loop-niter.h"
32 : #include "tree-ssa-loop.h"
33 : #include "tree-ssa-loop-manip.h"
34 : #include "tree-into-ssa.h"
35 : #include "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"
44 : #include "print-tree.h"
45 : #include "value-query.h"
46 : #include "sreal.h"
47 :
48 : /* This file implements two kinds of loop splitting.
49 :
50 : One transformation of loops like:
51 :
52 : for (i = 0; i < 100; i++)
53 : {
54 : if (i < 50)
55 : A;
56 : else
57 : B;
58 : }
59 :
60 : into:
61 :
62 : for (i = 0; i < 50; i++)
63 : {
64 : A;
65 : }
66 : for (; i < 100; i++)
67 : {
68 : B;
69 : }
70 :
71 : */
72 :
73 : /* Return true when BB inside LOOP is a potential iteration space
74 : split point, i.e. ends with a condition like "IV < comp", which
75 : is true on one side of the iteration space and false on the other,
76 : and the split point can be computed. If so, also return the border
77 : point in *BORDER and the comparison induction variable in IV. */
78 :
79 : static tree
80 173686 : split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv,
81 : enum tree_code *guard_code)
82 : {
83 173686 : gcond *stmt;
84 173686 : affine_iv iv2;
85 :
86 : /* BB must end in a simple conditional jump. */
87 443439 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
88 77147 : if (!stmt)
89 : return NULL_TREE;
90 :
91 77147 : enum tree_code code = gimple_cond_code (stmt);
92 :
93 77147 : if (loop_exits_from_bb_p (loop, bb))
94 : return NULL_TREE;
95 :
96 34144 : tree op0 = gimple_cond_lhs (stmt);
97 34144 : tree op1 = gimple_cond_rhs (stmt);
98 34144 : class loop *useloop = loop_containing_stmt (stmt);
99 :
100 34144 : if (!simple_iv (loop, useloop, op0, iv, false))
101 : return NULL_TREE;
102 5450 : if (!simple_iv (loop, useloop, op1, &iv2, false))
103 : return NULL_TREE;
104 :
105 : /* Make it so that the first argument of the condition is
106 : the looping one. */
107 2423 : if (!integer_zerop (iv2.step))
108 : {
109 759 : std::swap (op0, op1);
110 759 : std::swap (*iv, iv2);
111 759 : code = swap_tree_comparison (code);
112 759 : gimple_cond_set_condition (stmt, code, op0, op1);
113 759 : update_stmt (stmt);
114 : }
115 1664 : else if (integer_zerop (iv->step))
116 : return NULL_TREE;
117 1335 : if (!integer_zerop (iv2.step))
118 : return NULL_TREE;
119 1159 : if (!iv->no_overflow)
120 : return NULL_TREE;
121 :
122 : /* Only handle relational comparisons, for equality and non-equality
123 : we'd have to split the loop into two loops and a middle statement. */
124 1097 : switch (code)
125 : {
126 : case LT_EXPR:
127 : case LE_EXPR:
128 : case GT_EXPR:
129 : case GE_EXPR:
130 : break;
131 359 : case NE_EXPR:
132 359 : case EQ_EXPR:
133 : /* If the test check for first iteration, we can handle NE/EQ
134 : with only one split loop. */
135 359 : if (operand_equal_p (iv->base, iv2.base, 0))
136 : {
137 135 : if (code == EQ_EXPR)
138 101 : code = !tree_int_cst_sign_bit (iv->step) ? LE_EXPR : GE_EXPR;
139 : else
140 34 : code = !tree_int_cst_sign_bit (iv->step) ? GT_EXPR : LT_EXPR;
141 : break;
142 : }
143 : /* Similarly when the test checks for minimal or maximal
144 : value range. */
145 : else
146 : {
147 224 : value_range r (TREE_TYPE (op0));
148 224 : get_global_range_query ()->range_of_expr (r, op0, stmt);
149 224 : if (!r.varying_p () && !r.undefined_p ()
150 440 : && TREE_CODE (op1) == INTEGER_CST)
151 : {
152 101 : wide_int val = wi::to_wide (op1);
153 101 : if (known_eq (val, wi::to_wide (r.lbound ())))
154 : {
155 0 : code = (code == EQ_EXPR) ? LE_EXPR : GT_EXPR;
156 : break;
157 : }
158 101 : else if (known_eq (val, wi::to_wide (r.ubound ())))
159 : {
160 32 : code = (code == EQ_EXPR) ? GE_EXPR : LT_EXPR;
161 : break;
162 : }
163 69 : }
164 224 : }
165 : /* TODO: We can compare with exit condition; it seems that testing for
166 : last iteration is common case. */
167 192 : return NULL_TREE;
168 : default:
169 : return NULL_TREE;
170 : }
171 :
172 905 : if (dump_file && (dump_flags & TDF_DETAILS))
173 : {
174 26 : fprintf (dump_file, "Found potential split point: ");
175 26 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
176 26 : fprintf (dump_file, " { ");
177 26 : print_generic_expr (dump_file, iv->base, TDF_SLIM);
178 26 : fprintf (dump_file, " + I*");
179 26 : print_generic_expr (dump_file, iv->step, TDF_SLIM);
180 26 : fprintf (dump_file, " } %s ", get_tree_code_name (code));
181 26 : print_generic_expr (dump_file, iv2.base, TDF_SLIM);
182 26 : fprintf (dump_file, "\n");
183 : }
184 :
185 905 : *border = iv2.base;
186 905 : *guard_code = code;
187 905 : return op0;
188 : }
189 :
190 : /* Given a GUARD conditional stmt inside LOOP, which we want to make always
191 : true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
192 : (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
193 : exit test statement to loop back only if the GUARD statement will
194 : also be true/false in the next iteration. */
195 :
196 : static void
197 383 : patch_loop_exit (class loop *loop, tree_code guard_code, tree nextval,
198 : tree newbound, bool initial_true)
199 : {
200 383 : edge exit = single_exit (loop);
201 766 : gcond *stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
202 383 : gimple_cond_set_condition (stmt, guard_code, nextval, newbound);
203 383 : update_stmt (stmt);
204 :
205 383 : edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
206 :
207 383 : exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
208 383 : stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
209 :
210 383 : if (initial_true)
211 : {
212 270 : exit->flags |= EDGE_FALSE_VALUE;
213 270 : stay->flags |= EDGE_TRUE_VALUE;
214 : }
215 : else
216 : {
217 113 : exit->flags |= EDGE_TRUE_VALUE;
218 113 : stay->flags |= EDGE_FALSE_VALUE;
219 : }
220 383 : }
221 :
222 : /* Give an induction variable GUARD_IV, and its affine descriptor IV,
223 : find the loop phi node in LOOP defining it directly, or create
224 : such phi node. Return that phi node. */
225 :
226 : static gphi *
227 897 : find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/)
228 : {
229 897 : gimple *def = SSA_NAME_DEF_STMT (guard_iv);
230 897 : gphi *phi;
231 897 : if ((phi = dyn_cast <gphi *> (def))
232 383 : && gimple_bb (phi) == loop->header)
233 383 : return phi;
234 :
235 : /* XXX Create the PHI instead. */
236 : return NULL;
237 : }
238 :
239 : /* Returns true if the exit values of all loop phi nodes can be
240 : determined easily (i.e. that connect_loop_phis can determine them). */
241 :
242 : static bool
243 50744 : easy_exit_values (class loop *loop)
244 : {
245 50744 : edge exit = single_exit (loop);
246 50744 : edge latch = loop_latch_edge (loop);
247 50744 : gphi_iterator psi;
248 :
249 : /* Currently we regard the exit values as easy if they are the same
250 : as the value over the backedge. Which is the case if the definition
251 : of the backedge value dominates the exit edge. */
252 168885 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
253 : {
254 118144 : gphi *phi = psi.phi ();
255 118144 : tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
256 118144 : basic_block bb;
257 118144 : if (TREE_CODE (next) == SSA_NAME
258 117035 : && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
259 235176 : && !dominated_by_p (CDI_DOMINATORS, exit->src, bb))
260 : return false;
261 : }
262 :
263 : return true;
264 : }
265 :
266 : /* This function updates the SSA form after connect_loops made a new
267 : edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
268 : conditional). I.e. the second loop can now be entered either
269 : via the original entry or via NEW_E, so the entry values of LOOP2
270 : phi nodes are either the original ones or those at the exit
271 : of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting
272 : this. The loops need to fulfill easy_exit_values(). */
273 :
274 : static void
275 1265 : connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e)
276 : {
277 1265 : basic_block rest = loop_preheader_edge (loop2)->src;
278 1265 : gcc_assert (new_e->dest == rest);
279 1265 : edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
280 :
281 1265 : edge firste = loop_preheader_edge (loop1);
282 1265 : edge seconde = loop_preheader_edge (loop2);
283 1265 : edge firstn = loop_latch_edge (loop1);
284 1265 : gphi_iterator psi_first, psi_second;
285 1265 : for (psi_first = gsi_start_phis (loop1->header),
286 1265 : psi_second = gsi_start_phis (loop2->header);
287 5154 : !gsi_end_p (psi_first);
288 3889 : gsi_next (&psi_first), gsi_next (&psi_second))
289 : {
290 3889 : tree init, next, new_init;
291 3889 : use_operand_p op;
292 3889 : gphi *phi_first = psi_first.phi ();
293 3889 : gphi *phi_second = psi_second.phi ();
294 :
295 3889 : init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
296 3889 : next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
297 3889 : op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
298 3889 : gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
299 :
300 : /* Prefer using original variable as a base for the new ssa name.
301 : This is necessary for virtual ops, and useful in order to avoid
302 : losing debug info for real ops. */
303 3889 : if (TREE_CODE (next) == SSA_NAME
304 7708 : && useless_type_conversion_p (TREE_TYPE (next),
305 3819 : TREE_TYPE (init)))
306 3819 : new_init = copy_ssa_name (next);
307 70 : else if (TREE_CODE (init) == SSA_NAME
308 80 : && useless_type_conversion_p (TREE_TYPE (init),
309 10 : TREE_TYPE (next)))
310 10 : new_init = copy_ssa_name (init);
311 60 : else if (useless_type_conversion_p (TREE_TYPE (next),
312 60 : TREE_TYPE (init)))
313 60 : new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
314 : "unrinittmp");
315 : else
316 0 : new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
317 : "unrinittmp");
318 :
319 3889 : gphi * newphi = create_phi_node (new_init, rest);
320 3889 : add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
321 3889 : add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
322 3889 : SET_USE (op, new_init);
323 : }
324 1265 : }
325 :
326 : /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
327 : they are still equivalent and placed in two arms of a diamond, like so:
328 :
329 : .------if (cond)------.
330 : v v
331 : pre1 pre2
332 : | |
333 : .--->h1 h2<----.
334 : | | | |
335 : | ex1---. .---ex2 |
336 : | / | | \ |
337 : '---l1 X | l2---'
338 : | |
339 : | |
340 : '--->join<---'
341 :
342 : This function transforms the program such that LOOP1 is conditionally
343 : falling through to LOOP2, or skipping it. This is done by splitting
344 : the ex1->join edge at X in the diagram above, and inserting a condition
345 : whose one arm goes to pre2, resulting in this situation:
346 :
347 : .------if (cond)------.
348 : v v
349 : pre1 .---------->pre2
350 : | | |
351 : .--->h1 | h2<----.
352 : | | | | |
353 : | ex1---. | .---ex2 |
354 : | / v | | \ |
355 : '---l1 skip---' | l2---'
356 : | |
357 : | |
358 : '--->join<---'
359 :
360 :
361 : The condition used is the exit condition of LOOP1, which effectively means
362 : that when the first loop exits (for whatever reason) but the real original
363 : exit expression is still false the second loop will be entered.
364 : The function returns the new edge cond->pre2.
365 :
366 : This doesn't update the SSA form, see connect_loop_phis for that. */
367 :
368 : static edge
369 383 : connect_loops (class loop *loop1, class loop *loop2)
370 : {
371 383 : edge exit = single_exit (loop1);
372 383 : basic_block skip_bb = split_edge (exit);
373 383 : gcond *skip_stmt;
374 383 : gimple_stmt_iterator gsi;
375 383 : edge new_e, skip_e;
376 :
377 766 : gcond *stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
378 383 : skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
379 : gimple_cond_lhs (stmt),
380 : gimple_cond_rhs (stmt),
381 : NULL_TREE, NULL_TREE);
382 383 : gsi = gsi_last_bb (skip_bb);
383 383 : gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
384 :
385 383 : skip_e = EDGE_SUCC (skip_bb, 0);
386 383 : skip_e->flags &= ~EDGE_FALLTHRU;
387 383 : new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
388 383 : if (exit->flags & EDGE_TRUE_VALUE)
389 : {
390 89 : skip_e->flags |= EDGE_TRUE_VALUE;
391 89 : new_e->flags |= EDGE_FALSE_VALUE;
392 : }
393 : else
394 : {
395 294 : skip_e->flags |= EDGE_FALSE_VALUE;
396 294 : new_e->flags |= EDGE_TRUE_VALUE;
397 : }
398 :
399 383 : new_e->probability = profile_probability::very_likely ();
400 383 : skip_e->probability = new_e->probability.invert ();
401 :
402 383 : return new_e;
403 : }
404 :
405 : /* This returns the new bound for iterations given the original iteration
406 : space in NITER, an arbitrary new bound BORDER, assumed to be some
407 : comparison value with a different IV, the initial value GUARD_INIT of
408 : that other IV, and the comparison code GUARD_CODE that compares
409 : that other IV with BORDER. We return an SSA name, and place any
410 : necessary statements for that computation into *STMTS.
411 :
412 : For example for such a loop:
413 :
414 : for (i = beg, j = guard_init; i < end; i++, j++)
415 : if (j < border) // this is supposed to be true/false
416 : ...
417 :
418 : we want to return a new bound (on j) that makes the loop iterate
419 : as long as the condition j < border stays true. We also don't want
420 : to iterate more often than the original loop, so we have to introduce
421 : some cut-off as well (via min/max), effectively resulting in:
422 :
423 : newend = min (end+guard_init-beg, border)
424 : for (i = beg; j = guard_init; j < newend; i++, j++)
425 : if (j < c)
426 : ...
427 :
428 : Depending on the direction of the IVs and if the exit tests
429 : are strict or non-strict we need to use MIN or MAX,
430 : and add or subtract 1. This routine computes newend above. */
431 :
432 : static tree
433 383 : compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter,
434 : tree border,
435 : enum tree_code guard_code, tree guard_init)
436 : {
437 : /* The niter structure contains the after-increment IV, we need
438 : the loop-enter base, so subtract STEP once. */
439 383 : tree controlbase = force_gimple_operand (niter->control.base,
440 : stmts, true, NULL_TREE);
441 383 : tree controlstep = niter->control.step;
442 383 : tree enddiff;
443 383 : if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
444 : {
445 3 : controlstep = gimple_build (stmts, NEGATE_EXPR,
446 3 : TREE_TYPE (controlstep), controlstep);
447 3 : enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
448 3 : TREE_TYPE (controlbase),
449 : controlbase, controlstep);
450 : }
451 : else
452 380 : enddiff = gimple_build (stmts, MINUS_EXPR,
453 380 : TREE_TYPE (controlbase),
454 : controlbase, controlstep);
455 :
456 : /* Compute end-beg. */
457 383 : gimple_seq stmts2;
458 383 : tree end = force_gimple_operand (niter->bound, &stmts2,
459 : true, NULL_TREE);
460 383 : gimple_seq_add_seq_without_update (stmts, stmts2);
461 383 : if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
462 3 : enddiff = gimple_build (stmts, POINTER_DIFF_EXPR,
463 : ssizetype, end, enddiff);
464 : else
465 380 : enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
466 : end, enddiff);
467 :
468 : /* Compute guard_init + (end-beg). */
469 383 : tree newbound;
470 383 : if (POINTER_TYPE_P (TREE_TYPE (guard_init)))
471 : {
472 1 : enddiff = gimple_convert (stmts, sizetype, enddiff);
473 1 : newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
474 1 : TREE_TYPE (guard_init),
475 : guard_init, enddiff);
476 : }
477 : else
478 : {
479 382 : enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
480 382 : newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
481 : guard_init, enddiff);
482 : }
483 :
484 : /* Depending on the direction of the IVs the new bound for the first
485 : loop is the minimum or maximum of old bound and border.
486 : Also, if the guard condition isn't strictly less or greater,
487 : we need to adjust the bound. */
488 383 : int addbound = 0;
489 383 : enum tree_code minmax;
490 383 : if (niter->cmp == LT_EXPR)
491 : {
492 : /* GT and LE are the same, inverted. */
493 361 : if (guard_code == GT_EXPR || guard_code == LE_EXPR)
494 : addbound = -1;
495 : minmax = MIN_EXPR;
496 : }
497 : else
498 : {
499 22 : gcc_assert (niter->cmp == GT_EXPR);
500 22 : if (guard_code == GE_EXPR || guard_code == LT_EXPR)
501 : addbound = 1;
502 : minmax = MAX_EXPR;
503 : }
504 :
505 : if (addbound)
506 : {
507 292 : tree type2 = TREE_TYPE (newbound);
508 292 : if (POINTER_TYPE_P (type2))
509 0 : type2 = sizetype;
510 584 : newbound = gimple_build (stmts,
511 292 : POINTER_TYPE_P (TREE_TYPE (newbound))
512 : ? POINTER_PLUS_EXPR : PLUS_EXPR,
513 292 : TREE_TYPE (newbound),
514 : newbound,
515 292 : build_int_cst (type2, addbound));
516 : }
517 :
518 383 : tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
519 : border, newbound);
520 383 : return newend;
521 : }
522 :
523 : /* Fix the two loop's bb count after split based on the split edge probability,
524 : don't adjust the bbs dominated by the branch kept in that loop to avoid
525 : dropping 1s down. */
526 : static void
527 1265 : fix_loop_bb_probability (class loop *loop1, class loop *loop2, edge loop1_edge,
528 : edge loop2_edge)
529 : {
530 : /* Proportion first loop's bb counts except those dominated by the
531 : branch that stays true/false in the first loop, to avoid dropping
532 : 1s down. */
533 1265 : basic_block *bbs1, *bbs2;
534 1265 : bbs1 = get_loop_body (loop1);
535 1265 : unsigned j;
536 14278 : for (j = 0; j < loop1->num_nodes; j++)
537 11748 : if (bbs1[j] == loop1->latch
538 : /* Watch for case where the kept conditional arm is empty. */
539 10483 : || !single_pred_p (loop1_edge->dest)
540 21552 : || !dominated_by_p (CDI_DOMINATORS, bbs1[j], loop1_edge->dest))
541 8826 : bbs1[j]->count
542 8826 : = bbs1[j]->count.apply_probability (loop1_edge->probability);
543 1265 : free (bbs1);
544 :
545 : /* Proportion second loop's bb counts except those dominated by the
546 : opposite branch, which is kept in the second loop. */
547 1265 : basic_block bbi_copy = get_bb_copy (loop2_edge->dest);
548 1265 : bbs2 = get_loop_body (loop2);
549 12514 : for (j = 0; j < loop2->num_nodes; j++)
550 9984 : if (bbs2[j] == loop2->latch
551 : /* Watch for case where the kept conditional arm is empty. */
552 8719 : || !single_pred_p (bbi_copy)
553 14779 : || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy))
554 8708 : bbs2[j]->count
555 8708 : = bbs2[j]->count.apply_probability (loop2_edge->probability);
556 1265 : free (bbs2);
557 1265 : }
558 :
559 : /* Checks if LOOP contains an conditional block whose condition
560 : depends on which side in the iteration space it is, and if so
561 : splits the iteration space into two loops. Returns true if the
562 : loop was split. NITER must contain the iteration descriptor for the
563 : single exit of LOOP. */
564 :
565 : static bool
566 80785 : split_loop (class loop *loop1)
567 : {
568 80785 : class tree_niter_desc niter;
569 80785 : basic_block *bbs;
570 80785 : unsigned i;
571 80785 : bool changed = false;
572 80785 : tree guard_iv;
573 80785 : tree border = NULL_TREE;
574 80785 : affine_iv iv;
575 80785 : edge exit1;
576 :
577 80785 : if (!(exit1 = single_exit (loop1))
578 55419 : || EDGE_COUNT (exit1->src->succs) != 2
579 : /* ??? We could handle non-empty latches when we split the latch edge
580 : (not the exit edge), and put the new exit condition in the new block.
581 : OTOH this executes some code unconditionally that might have been
582 : skipped by the original exit before. */
583 55391 : || !empty_block_p (loop1->latch)
584 50744 : || !easy_exit_values (loop1)
585 50741 : || !number_of_iterations_exit (loop1, exit1, &niter, false, true)
586 124421 : || niter.cmp == ERROR_MARK)
587 37205 : return false;
588 43580 : if (niter.cmp == NE_EXPR)
589 : {
590 27553 : if (!niter.control.no_overflow)
591 : return false;
592 27271 : if (tree_int_cst_sign_bit (niter.control.step))
593 2687 : niter.cmp = GT_EXPR;
594 : else
595 24584 : niter.cmp = LT_EXPR;
596 : }
597 :
598 43298 : bbs = get_loop_body (loop1);
599 :
600 43298 : if (!can_copy_bbs_p (bbs, loop1->num_nodes))
601 : {
602 4 : free (bbs);
603 4 : return false;
604 : }
605 :
606 : /* Find a splitting opportunity. */
607 : enum tree_code guard_code;
608 216597 : for (i = 0; i < loop1->num_nodes; i++)
609 173686 : if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv, &guard_code)))
610 : {
611 : /* Handling opposite steps is not implemented yet. Neither
612 : is handling different step sizes. */
613 905 : if ((tree_int_cst_sign_bit (iv.step)
614 905 : != tree_int_cst_sign_bit (niter.control.step))
615 905 : || !tree_int_cst_equal (iv.step, niter.control.step))
616 522 : continue;
617 :
618 : /* Find a loop PHI node that defines guard_iv directly,
619 : or create one doing that. */
620 897 : gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
621 897 : if (!phi)
622 514 : continue;
623 383 : const tree phi_result = gimple_phi_result (phi);
624 766 : gcond *guard_stmt = as_a<gcond *> (*gsi_last_bb (bbs[i]));
625 383 : tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
626 : loop_preheader_edge (loop1));
627 :
628 : /* Loop splitting is implemented by versioning the loop, placing
629 : the new loop after the old loop, make the first loop iterate
630 : as long as the conditional stays true (or false) and let the
631 : second (new) loop handle the rest of the iterations.
632 :
633 : First we need to determine if the condition will start being true
634 : or false in the first loop. */
635 383 : bool initial_true;
636 383 : switch (guard_code)
637 : {
638 268 : case LT_EXPR:
639 268 : case LE_EXPR:
640 268 : initial_true = !tree_int_cst_sign_bit (iv.step);
641 268 : break;
642 115 : case GT_EXPR:
643 115 : case GE_EXPR:
644 115 : initial_true = tree_int_cst_sign_bit (iv.step);
645 115 : break;
646 0 : default:
647 0 : gcc_unreachable ();
648 : }
649 :
650 : /* Build a condition that will skip the first loop when the
651 : guard condition won't ever be true (or false). */
652 383 : gimple_seq stmts2;
653 383 : border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
654 383 : if (stmts2)
655 : {
656 : /* When the split condition is not always evaluated make sure
657 : to rewrite it to defined overflow. */
658 2 : if (!dominated_by_p (CDI_DOMINATORS, exit1->src, bbs[i]))
659 : {
660 2 : gimple_stmt_iterator gsi;
661 2 : gsi = gsi_start (stmts2);
662 6 : while (!gsi_end_p (gsi))
663 : {
664 4 : if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
665 2 : rewrite_to_defined_unconditional (&gsi);
666 4 : gsi_next (&gsi);
667 : }
668 : }
669 2 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
670 : stmts2);
671 : }
672 383 : tree cond = fold_build2 (guard_code, boolean_type_node,
673 : guard_init, border);
674 383 : if (!initial_true)
675 113 : cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
676 :
677 383 : edge true_edge, false_edge;
678 383 : extract_true_false_edges_from_block (bbs[i], &true_edge, &false_edge);
679 383 : edge loop1_edge = initial_true ? true_edge : false_edge;
680 383 : edge loop2_edge = initial_true ? false_edge : true_edge;
681 :
682 : /* Now version the loop, placing loop2 after loop1 connecting
683 : them, and fix up SSA form for that. */
684 383 : initialize_original_copy_tables ();
685 383 : basic_block cond_bb;
686 :
687 383 : profile_probability loop1_prob
688 383 : = integer_onep (cond) ? profile_probability::always ()
689 100 : : loop1_edge->probability;
690 : /* TODO: It is commonly a case that we know that both loops will be
691 : entered. very_likely below is the probability that second loop will
692 : be entered given by connect_loops. We should work out the common
693 : case it is always true. */
694 383 : class loop *loop2 = loop_version (loop1, cond, &cond_bb,
695 : loop1_prob,
696 : /* Pass always as we will later
697 : redirect first loop to second
698 : loop. */
699 : profile_probability::always (),
700 : profile_probability::always (),
701 : profile_probability::very_likely (),
702 : true);
703 383 : gcc_assert (loop2);
704 :
705 : /* The phi address may have changed due to being resized in
706 : loop_version (), so reobtain it. */
707 383 : phi = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_result));
708 383 : gcc_checking_assert (gimple_bb (phi) == loop1->header);
709 :
710 : /* Correct probability of edge cond_bb->preheader_of_loop2. */
711 383 : single_pred_edge
712 383 : (loop_preheader_edge (loop2)->src)->probability
713 383 : = loop1_prob.invert ();
714 :
715 383 : fix_loop_bb_probability (loop1, loop2, loop1_edge, loop2_edge);
716 :
717 383 : if (dump_file && (dump_flags & TDF_DETAILS))
718 35 : fprintf (dump_file,
719 : ";; Split loop: initial_true %s, "
720 : "loop1 count %" PRId64 ", loop2 count %" PRId64 "\n",
721 : initial_true ? "true" : "false",
722 26 : (int64_t) loop1->header->count.to_gcov_type (),
723 26 : (int64_t) loop2->header->count.to_gcov_type ());
724 :
725 : /* If conditional we split on has reliable profilea nd both
726 : preconditionals of loop1 and loop2 are constant true, we can
727 : only redistribute the iteration counts to the split loops.
728 :
729 : If the conditionals we insert before loop1 or loop2 are non-trivial
730 : they increase expected loop count, so account this accordingly.
731 : If we do not know the probability of split conditional, avoid
732 : reudcing loop estimates, since we do not really know how they are
733 : split between of the two new loops. Keep orignal estimate since
734 : it is likely better then completely dropping it.
735 :
736 : TODO: If we know that one of the new loops has constant
737 : number of iterations, we can do better. We could also update
738 : upper bounds. */
739 383 : if (loop1->any_estimate
740 383 : && wi::fits_shwi_p (loop1->nb_iterations_estimate))
741 : {
742 211 : sreal scale
743 411 : = loop1_edge->probability.reliable_p ()
744 211 : ? loop1_edge->probability.to_sreal () : (sreal)1;
745 211 : sreal scale2
746 411 : = loop2_edge->probability.reliable_p ()
747 211 : ? loop2_edge->probability.to_sreal () : (sreal)1;
748 211 : sreal div1 = loop1_prob.initialized_p ()
749 213 : ? loop1_prob.to_sreal () : (sreal)1/(sreal)2;
750 : /* +1 to get header interations rather than latch iterations and then
751 : -1 to convert back. */
752 211 : if (div1 != 0)
753 210 : loop1->nb_iterations_estimate
754 419 : = MAX ((((sreal)loop1->nb_iterations_estimate.to_shwi () + 1)
755 : * scale / div1).to_nearest_int () - 1, 0);
756 : else
757 1 : loop1->any_estimate = false;
758 211 : loop2->nb_iterations_estimate
759 211 : = MAX ((((sreal)loop2->nb_iterations_estimate.to_shwi () + 1) * scale2
760 : / profile_probability::very_likely ().to_sreal ())
761 : .to_nearest_int () - 1, 0);
762 : }
763 383 : update_loop_exit_probability_scale_dom_bbs (loop1);
764 383 : update_loop_exit_probability_scale_dom_bbs (loop2);
765 :
766 383 : edge new_e = connect_loops (loop1, loop2);
767 383 : connect_loop_phis (loop1, loop2, new_e);
768 :
769 : /* The iterations of the second loop is now already
770 : exactly those that the first loop didn't do, but the
771 : iteration space of the first loop is still the original one.
772 : Compute the new bound for the guarding IV and patch the
773 : loop exit to use it instead of original IV and bound. */
774 383 : gimple_seq stmts = NULL;
775 383 : tree newend = compute_new_first_bound (&stmts, &niter, border,
776 : guard_code, guard_init);
777 383 : if (stmts)
778 182 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
779 : stmts);
780 383 : tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
781 383 : patch_loop_exit (loop1, guard_code, guard_next, newend, initial_true);
782 :
783 : /* Finally patch out the two copies of the condition to be always
784 : true/false (or opposite). */
785 766 : gcond *force_true = as_a<gcond *> (*gsi_last_bb (bbs[i]));
786 766 : gcond *force_false = as_a<gcond *> (*gsi_last_bb (get_bb_copy (bbs[i])));
787 383 : if (!initial_true)
788 113 : std::swap (force_true, force_false);
789 383 : gimple_cond_make_true (force_true);
790 383 : gimple_cond_make_false (force_false);
791 383 : update_stmt (force_true);
792 383 : update_stmt (force_false);
793 :
794 383 : free_original_copy_tables ();
795 :
796 383 : changed = true;
797 383 : if (dump_file && (dump_flags & TDF_DETAILS))
798 26 : fprintf (dump_file, ";; Loop split.\n");
799 :
800 383 : if (dump_enabled_p ())
801 27 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, guard_stmt, "loop split\n");
802 :
803 : /* Only deal with the first opportunity. */
804 383 : break;
805 : }
806 :
807 43294 : free (bbs);
808 43294 : return changed;
809 80785 : }
810 :
811 : /* Another transformation of loops like:
812 :
813 : for (i = INIT (); CHECK (i); i = NEXT ())
814 : {
815 : if (expr (a_1, a_2, ..., a_n)) // expr is pure
816 : a_j = ...; // change at least one a_j
817 : else
818 : S; // not change any a_j
819 : }
820 :
821 : into:
822 :
823 : for (i = INIT (); CHECK (i); i = NEXT ())
824 : {
825 : if (expr (a_1, a_2, ..., a_n))
826 : a_j = ...;
827 : else
828 : {
829 : S;
830 : i = NEXT ();
831 : break;
832 : }
833 : }
834 :
835 : for (; CHECK (i); i = NEXT ())
836 : {
837 : S;
838 : }
839 :
840 : */
841 :
842 : /* Data structure to hold temporary information during loop split upon
843 : semi-invariant conditional statement. */
844 : class split_info {
845 : public:
846 : /* Array of all basic blocks in a loop, returned by get_loop_body(). */
847 : basic_block *bbs;
848 :
849 : /* All memory store/clobber statements in a loop. */
850 : auto_vec<gimple *> memory_stores;
851 :
852 : /* Whether above memory stores vector has been filled. */
853 : int need_init;
854 :
855 : /* Control dependencies of basic blocks in a loop. */
856 : auto_vec<hash_set<basic_block> *> control_deps;
857 :
858 80402 : split_info () : bbs (NULL), need_init (true) { }
859 :
860 80402 : ~split_info ()
861 : {
862 80402 : if (bbs)
863 80402 : free (bbs);
864 :
865 81070 : for (unsigned i = 0; i < control_deps.length (); i++)
866 1336 : delete control_deps[i];
867 80402 : }
868 : };
869 :
870 : /* Find all statements with memory-write effect in LOOP, including memory
871 : store and non-pure function call, and keep those in a vector. This work
872 : is only done one time, for the vector should be constant during analysis
873 : stage of semi-invariant condition. */
874 :
875 : static void
876 11089 : find_vdef_in_loop (struct loop *loop)
877 : {
878 11089 : split_info *info = (split_info *) loop->aux;
879 11089 : gphi *vphi = get_virtual_phi (loop->header);
880 :
881 : /* Indicate memory store vector has been filled. */
882 11089 : info->need_init = false;
883 :
884 : /* If loop contains memory operation, there must be a virtual PHI node in
885 : loop header basic block. */
886 11089 : if (vphi == NULL)
887 2668 : return;
888 :
889 : /* All virtual SSA names inside the loop are connected to be a cyclic
890 : graph via virtual PHI nodes. The virtual PHI node in loop header just
891 : links the first and the last virtual SSA names, by using the last as
892 : PHI operand to define the first. */
893 8484 : const edge latch = loop_latch_edge (loop);
894 8484 : const tree first = gimple_phi_result (vphi);
895 8484 : const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
896 :
897 : /* The virtual SSA cyclic graph might consist of only one SSA name, who
898 : is defined by itself.
899 :
900 : .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
901 :
902 : This means the loop contains only memory loads, so we can skip it. */
903 8484 : if (first == last)
904 : return;
905 :
906 8421 : auto_vec<gimple *> other_stores;
907 8421 : auto_vec<tree> worklist;
908 8421 : auto_bitmap visited;
909 :
910 8421 : bitmap_set_bit (visited, SSA_NAME_VERSION (first));
911 8421 : bitmap_set_bit (visited, SSA_NAME_VERSION (last));
912 8421 : worklist.safe_push (last);
913 :
914 57519 : do
915 : {
916 57519 : tree vuse = worklist.pop ();
917 57519 : gimple *stmt = SSA_NAME_DEF_STMT (vuse);
918 :
919 : /* We mark the first and last SSA names as visited at the beginning,
920 : and reversely start the process from the last SSA name towards the
921 : first, which ensures that this do-while will not touch SSA names
922 : defined outside the loop. */
923 57519 : gcc_assert (gimple_bb (stmt)
924 : && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
925 :
926 57519 : if (gimple_code (stmt) == GIMPLE_PHI)
927 : {
928 15350 : gphi *phi = as_a <gphi *> (stmt);
929 :
930 47254 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
931 : {
932 31904 : tree arg = gimple_phi_arg_def (stmt, i);
933 :
934 31904 : if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
935 20867 : worklist.safe_push (arg);
936 : }
937 : }
938 : else
939 : {
940 42169 : tree prev = gimple_vuse (stmt);
941 :
942 : /* Non-pure call statement is conservatively assumed to impact all
943 : memory locations. So place call statements ahead of other memory
944 : stores in the vector with an idea of using them as shortcut
945 : terminators to memory alias analysis. */
946 42169 : if (gimple_code (stmt) == GIMPLE_CALL)
947 14130 : info->memory_stores.safe_push (stmt);
948 : else
949 28039 : other_stores.safe_push (stmt);
950 :
951 42169 : if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
952 28231 : worklist.safe_push (prev);
953 : }
954 115038 : } while (!worklist.is_empty ());
955 :
956 8421 : info->memory_stores.safe_splice (other_stores);
957 8421 : }
958 :
959 : /* Two basic blocks have equivalent control dependency if one dominates to
960 : the other, and it is post-dominated by the latter. Given a basic block
961 : BB in LOOP, find farest equivalent dominating basic block. For BB, there
962 : is a constraint that BB does not post-dominate loop header of LOOP, this
963 : means BB is control-dependent on at least one basic block in LOOP. */
964 :
965 : static basic_block
966 1310 : get_control_equiv_head_block (struct loop *loop, basic_block bb)
967 : {
968 1379 : while (!bb->aux)
969 : {
970 781 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
971 :
972 781 : gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb));
973 :
974 781 : if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb))
975 : break;
976 :
977 : bb = dom_bb;
978 : }
979 1310 : return bb;
980 : }
981 :
982 : /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
983 : dependent on. */
984 :
985 : static hash_set<basic_block> *
986 7933 : find_control_dep_blocks (struct loop *loop, basic_block bb)
987 : {
988 : /* BB has same control dependency as loop header, then it is not control-
989 : dependent on any basic block in LOOP. */
990 7933 : if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb))
991 : return NULL;
992 :
993 1266 : basic_block equiv_head = get_control_equiv_head_block (loop, bb);
994 :
995 1266 : if (equiv_head->aux)
996 : {
997 : /* There is a basic block containing control dependency equivalent
998 : to BB. No need to recompute that, and also set this information
999 : to other equivalent basic blocks. */
1000 598 : for (; bb != equiv_head;
1001 0 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1002 0 : bb->aux = equiv_head->aux;
1003 598 : return (hash_set<basic_block> *) equiv_head->aux;
1004 : }
1005 :
1006 : /* A basic block X is control-dependent on another Y iff there exists
1007 : a path from X to Y, in which every basic block other than X and Y
1008 : is post-dominated by Y, but X is not post-dominated by Y.
1009 :
1010 : According to this rule, traverse basic blocks in the loop backwards
1011 : starting from BB, if a basic block is post-dominated by BB, extend
1012 : current post-dominating path to this block, otherwise it is another
1013 : one that BB is control-dependent on. */
1014 :
1015 668 : auto_vec<basic_block> pdom_worklist;
1016 668 : hash_set<basic_block> pdom_visited;
1017 668 : hash_set<basic_block> *dep_bbs = new hash_set<basic_block>;
1018 :
1019 668 : pdom_worklist.safe_push (equiv_head);
1020 :
1021 711 : do
1022 : {
1023 711 : basic_block pdom_bb = pdom_worklist.pop ();
1024 711 : edge_iterator ei;
1025 711 : edge e;
1026 :
1027 711 : if (pdom_visited.add (pdom_bb))
1028 0 : continue;
1029 :
1030 1460 : FOR_EACH_EDGE (e, ei, pdom_bb->preds)
1031 : {
1032 749 : basic_block pred_bb = e->src;
1033 :
1034 749 : if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb))
1035 : {
1036 705 : dep_bbs->add (pred_bb);
1037 749 : continue;
1038 : }
1039 :
1040 44 : pred_bb = get_control_equiv_head_block (loop, pred_bb);
1041 :
1042 44 : if (pdom_visited.contains (pred_bb))
1043 1 : continue;
1044 :
1045 43 : if (!pred_bb->aux)
1046 : {
1047 43 : pdom_worklist.safe_push (pred_bb);
1048 43 : continue;
1049 : }
1050 :
1051 : /* If control dependency of basic block is available, fast extend
1052 : post-dominating path using the information instead of advancing
1053 : forward step-by-step. */
1054 0 : hash_set<basic_block> *pred_dep_bbs
1055 : = (hash_set<basic_block> *) pred_bb->aux;
1056 :
1057 0 : for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin ();
1058 0 : iter != pred_dep_bbs->end (); ++iter)
1059 : {
1060 0 : basic_block pred_dep_bb = *iter;
1061 :
1062 : /* Basic blocks can either be in control dependency of BB, or
1063 : must be post-dominated by BB, if so, extend the path from
1064 : these basic blocks. */
1065 0 : if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb))
1066 0 : dep_bbs->add (pred_dep_bb);
1067 0 : else if (!pdom_visited.contains (pred_dep_bb))
1068 0 : pdom_worklist.safe_push (pred_dep_bb);
1069 : }
1070 : }
1071 1422 : } while (!pdom_worklist.is_empty ());
1072 :
1073 : /* Record computed control dependencies in loop so that we can reach them
1074 : when reclaiming resources. */
1075 668 : ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs);
1076 :
1077 : /* Associate control dependence with related equivalent basic blocks. */
1078 713 : for (equiv_head->aux = dep_bbs; bb != equiv_head;
1079 45 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1080 45 : bb->aux = dep_bbs;
1081 :
1082 668 : return dep_bbs;
1083 668 : }
1084 :
1085 : /* Forward declaration */
1086 :
1087 : static bool
1088 : stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
1089 : const_basic_block skip_head,
1090 : hash_map<gimple *, bool> &stmt_stat);
1091 :
1092 : /* Given STMT, memory load or pure call statement, check whether it is impacted
1093 : by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
1094 : trace is composed of SKIP_HEAD and those basic block dominated by it, always
1095 : corresponds to one branch of a conditional statement). If SKIP_HEAD is
1096 : NULL, all basic blocks of LOOP are checked. */
1097 :
1098 : static bool
1099 26908 : vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
1100 : const_basic_block skip_head)
1101 : {
1102 26908 : split_info *info = (split_info *) loop->aux;
1103 26908 : tree rhs = NULL_TREE;
1104 26908 : ao_ref ref;
1105 26908 : gimple *store;
1106 26908 : unsigned i;
1107 :
1108 : /* Collect memory store/clobber statements if haven't done that. */
1109 26908 : if (info->need_init)
1110 11089 : find_vdef_in_loop (loop);
1111 :
1112 26908 : if (is_gimple_assign (stmt))
1113 26699 : rhs = gimple_assign_rhs1 (stmt);
1114 :
1115 26908 : ao_ref_init (&ref, rhs);
1116 :
1117 95633 : FOR_EACH_VEC_ELT (info->memory_stores, i, store)
1118 : {
1119 : /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */
1120 72290 : if (skip_head
1121 53243 : && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head))
1122 19047 : continue;
1123 :
1124 34196 : if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
1125 11426 : return false;
1126 : }
1127 :
1128 : return true;
1129 : }
1130 :
1131 : /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
1132 : certain iteration of LOOP, check whether an SSA name (NAME) remains
1133 : unchanged in next iteration. We call this characteristic semi-
1134 : invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic
1135 : blocks and control flows in the loop will be considered. Semi-invariant
1136 : state of checked statement is cached in hash map STMT_STAT to avoid
1137 : redundant computation in possible following re-check. */
1138 :
1139 : static inline bool
1140 173253 : ssa_semi_invariant_p (struct loop *loop, tree name,
1141 : const_basic_block skip_head,
1142 : hash_map<gimple *, bool> &stmt_stat)
1143 : {
1144 173253 : gimple *def = SSA_NAME_DEF_STMT (name);
1145 173253 : const_basic_block def_bb = gimple_bb (def);
1146 :
1147 : /* An SSA name defined outside loop is definitely semi-invariant. */
1148 173253 : if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
1149 14524 : return true;
1150 :
1151 158729 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1152 : return false;
1153 :
1154 158721 : return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat);
1155 : }
1156 :
1157 : /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
1158 : semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1159 : are excluded from LOOP. */
1160 :
1161 : static bool
1162 31553 : loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi,
1163 : const_basic_block skip_head)
1164 : {
1165 31553 : const_edge latch = loop_latch_edge (loop);
1166 31553 : tree name = gimple_phi_result (loop_phi);
1167 31553 : tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch);
1168 :
1169 31553 : gcc_checking_assert (from);
1170 :
1171 : /* Loop iteration PHI node locates in loop header, and it has two source
1172 : operands, one is an initial value coming from outside the loop, the other
1173 : is a value through latch of the loop, which is derived in last iteration,
1174 : we call the latter latch value. From the PHI node to definition of latch
1175 : value, if excluding branch trace starting from SKIP_HEAD, except copy-
1176 : assignment or likewise, there is no other kind of value redefinition, SSA
1177 : name defined by the PHI node is semi-invariant.
1178 :
1179 : loop entry
1180 : | .--- latch ---.
1181 : | | |
1182 : v v |
1183 : x_1 = PHI <x_0, x_3> |
1184 : | |
1185 : v |
1186 : .------- if (cond) -------. |
1187 : | | |
1188 : | [ SKIP ] |
1189 : | | |
1190 : | x_2 = ... |
1191 : | | |
1192 : '---- T ---->.<---- F ----' |
1193 : | |
1194 : v |
1195 : x_3 = PHI <x_1, x_2> |
1196 : | |
1197 : '----------------------'
1198 :
1199 : Suppose in certain iteration, execution flow in above graph goes through
1200 : true branch, which means that one source value to define x_3 in false
1201 : branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
1202 : iterations is defined by x_3, we know that x_1 will never changed if COND
1203 : always chooses true branch from then on. */
1204 :
1205 35367 : while (from != name)
1206 : {
1207 : /* A new value comes from a CONSTANT. */
1208 34437 : if (TREE_CODE (from) != SSA_NAME)
1209 : return false;
1210 :
1211 32798 : gimple *stmt = SSA_NAME_DEF_STMT (from);
1212 32798 : const_basic_block bb = gimple_bb (stmt);
1213 :
1214 : /* A new value comes from outside the loop. */
1215 32798 : if (!bb || !flow_bb_inside_loop_p (loop, bb))
1216 40 : return false;
1217 :
1218 32758 : from = NULL_TREE;
1219 :
1220 32758 : if (gimple_code (stmt) == GIMPLE_PHI)
1221 : {
1222 7224 : gphi *phi = as_a <gphi *> (stmt);
1223 :
1224 19277 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1225 : {
1226 15463 : if (skip_head)
1227 : {
1228 14815 : const_edge e = gimple_phi_arg_edge (phi, i);
1229 :
1230 : /* Don't consider redefinitions in excluded basic blocks. */
1231 14815 : if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head))
1232 4240 : continue;
1233 : }
1234 :
1235 11223 : tree arg = gimple_phi_arg_def (phi, i);
1236 :
1237 11223 : if (!from)
1238 : from = arg;
1239 3999 : else if (!operand_equal_p (from, arg, 0))
1240 : /* There are more than one source operands that provide
1241 : different values to the SSA name, it is variant. */
1242 : return false;
1243 : }
1244 : }
1245 25534 : else if (gimple_code (stmt) == GIMPLE_ASSIGN)
1246 : {
1247 : /* For simple value copy, check its rhs instead. */
1248 25370 : if (gimple_assign_ssa_name_copy_p (stmt))
1249 0 : from = gimple_assign_rhs1 (stmt);
1250 : }
1251 :
1252 : /* Any other kind of definition is deemed to introduce a new value
1253 : to the SSA name. */
1254 29348 : if (!from)
1255 : return false;
1256 : }
1257 : return true;
1258 : }
1259 :
1260 : /* Check whether conditional predicates that BB is control-dependent on, are
1261 : semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1262 : are excluded from LOOP. Semi-invariant state of checked statement is cached
1263 : in hash map STMT_STAT. */
1264 :
1265 : static bool
1266 7933 : control_dep_semi_invariant_p (struct loop *loop, basic_block bb,
1267 : const_basic_block skip_head,
1268 : hash_map<gimple *, bool> &stmt_stat)
1269 : {
1270 7933 : hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb);
1271 :
1272 7933 : if (!dep_bbs)
1273 : return true;
1274 :
1275 1430 : for (hash_set<basic_block>::iterator iter = dep_bbs->begin ();
1276 1594 : iter != dep_bbs->end (); ++iter)
1277 : {
1278 1283 : gimple *last = *gsi_last_bb (*iter);
1279 1283 : if (!last)
1280 1119 : return false;
1281 :
1282 : /* Only check condition predicates. */
1283 1283 : if (gimple_code (last) != GIMPLE_COND
1284 1283 : && gimple_code (last) != GIMPLE_SWITCH)
1285 : return false;
1286 :
1287 1283 : if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat))
1288 : return false;
1289 : }
1290 :
1291 147 : return true;
1292 : }
1293 :
1294 : /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
1295 : semi-invariant, consequently, all its defined values are semi-invariant.
1296 : Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
1297 : Semi-invariant state of checked statement is cached in hash map
1298 : STMT_STAT. */
1299 :
1300 : static bool
1301 208935 : stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
1302 : const_basic_block skip_head,
1303 : hash_map<gimple *, bool> &stmt_stat)
1304 : {
1305 208935 : bool existed;
1306 208935 : bool &invar = stmt_stat.get_or_insert (stmt, &existed);
1307 :
1308 208935 : if (existed)
1309 883 : return invar;
1310 :
1311 : /* A statement might depend on itself, which is treated as variant. So set
1312 : state of statement under check to be variant to ensure that. */
1313 208052 : invar = false;
1314 :
1315 208052 : if (gimple_code (stmt) == GIMPLE_PHI)
1316 : {
1317 57063 : gphi *phi = as_a <gphi *> (stmt);
1318 :
1319 57063 : if (gimple_bb (stmt) == loop->header)
1320 : {
1321 : /* If the entry value is subject to abnormal coalescing
1322 : avoid the transform since we're going to duplicate the
1323 : loop header and thus likely introduce overlapping life-ranges
1324 : between the PHI def and the entry on the path when the
1325 : first loop is skipped. */
1326 31553 : tree entry_def
1327 31553 : = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1328 31553 : if (TREE_CODE (entry_def) == SSA_NAME
1329 31553 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (entry_def))
1330 : return false;
1331 31553 : invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head);
1332 31553 : return invar;
1333 : }
1334 :
1335 : /* For a loop PHI node that does not locate in loop header, it is semi-
1336 : invariant only if two conditions are met. The first is its source
1337 : values are derived from CONSTANT (including loop-invariant value), or
1338 : from SSA name defined by semi-invariant loop iteration PHI node. The
1339 : second is its source incoming edges are control-dependent on semi-
1340 : invariant conditional predicates. */
1341 25561 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1342 : {
1343 25553 : const_edge e = gimple_phi_arg_edge (phi, i);
1344 25553 : tree arg = gimple_phi_arg_def (phi, i);
1345 :
1346 25553 : if (TREE_CODE (arg) == SSA_NAME)
1347 : {
1348 25111 : if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat))
1349 : return false;
1350 :
1351 : /* If source value is defined in location from where the source
1352 : edge comes in, no need to check control dependency again
1353 : since this has been done in above SSA name check stage. */
1354 58 : if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1355 4 : continue;
1356 : }
1357 :
1358 496 : if (!control_dep_semi_invariant_p (loop, e->src, skip_head,
1359 : stmt_stat))
1360 : return false;
1361 : }
1362 : }
1363 : else
1364 : {
1365 150989 : ssa_op_iter iter;
1366 150989 : tree use;
1367 :
1368 : /* Volatile memory load or return of normal (non-const/non-pure) call
1369 : should not be treated as constant in each iteration of loop. */
1370 150989 : if (gimple_has_side_effects (stmt))
1371 143560 : return false;
1372 :
1373 : /* Check if any memory store may kill memory load at this place. */
1374 248061 : if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head))
1375 : return false;
1376 :
1377 : /* Although operand of a statement might be SSA name, CONSTANT or
1378 : VARDECL, here we only need to check SSA name operands. This is
1379 : because check on VARDECL operands, which involve memory loads,
1380 : must have been done prior to invocation of this function in
1381 : vuse_semi_invariant_p. */
1382 155571 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1383 148142 : if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat))
1384 : return false;
1385 : }
1386 :
1387 7437 : if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head,
1388 : stmt_stat))
1389 : return false;
1390 :
1391 : /* Here we SHOULD NOT use invar = true, since hash map might be changed due
1392 : to new insertion, and thus invar may point to invalid memory. */
1393 6767 : stmt_stat.put (stmt, true);
1394 6767 : return true;
1395 : }
1396 :
1397 : /* A helper function to check whether STMT is semi-invariant in LOOP. Basic
1398 : blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */
1399 :
1400 : static bool
1401 48931 : stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
1402 : const_basic_block skip_head)
1403 : {
1404 48931 : hash_map<gimple *, bool> stmt_stat;
1405 48931 : return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat);
1406 48931 : }
1407 :
1408 : /* Determine when conditional statement never transfers execution to one of its
1409 : branch, whether we can remove the branch's leading basic block (BRANCH_BB)
1410 : and those basic blocks dominated by BRANCH_BB. */
1411 :
1412 : static bool
1413 53162 : branch_removable_p (basic_block branch_bb)
1414 : {
1415 53162 : edge_iterator ei;
1416 53162 : edge e;
1417 :
1418 53162 : if (single_pred_p (branch_bb))
1419 : return true;
1420 :
1421 8356 : FOR_EACH_EDGE (e, ei, branch_bb->preds)
1422 : {
1423 8356 : if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
1424 0 : continue;
1425 :
1426 8356 : if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
1427 2942 : continue;
1428 :
1429 : /* The branch can be reached from opposite branch, or from some
1430 : statement not dominated by the conditional statement. */
1431 : return false;
1432 : }
1433 :
1434 : return true;
1435 : }
1436 :
1437 : /* Find out which branch of a conditional statement (COND) is invariant in the
1438 : execution context of LOOP. That is: once the branch is selected in certain
1439 : iteration of the loop, any operand that contributes to computation of the
1440 : conditional statement remains unchanged in all following iterations. */
1441 :
1442 : static edge
1443 136978 : get_cond_invariant_branch (struct loop *loop, gcond *cond)
1444 : {
1445 136978 : basic_block cond_bb = gimple_bb (cond);
1446 136978 : basic_block targ_bb[2];
1447 136978 : bool invar[2];
1448 136978 : unsigned invar_checks = 0;
1449 :
1450 224527 : for (unsigned i = 0; i < 2; i++)
1451 : {
1452 197946 : targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
1453 :
1454 : /* One branch directs to loop exit, no need to perform loop split upon
1455 : this conditional statement. Firstly, it is trivial if the exit branch
1456 : is semi-invariant, for the statement is just to break loop. Secondly,
1457 : if the opposite branch is semi-invariant, it means that the statement
1458 : is real loop-invariant, which is covered by loop unswitch. */
1459 197946 : if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
1460 : return NULL;
1461 : }
1462 :
1463 79743 : for (unsigned i = 0; i < 2; i++)
1464 : {
1465 53162 : invar[!i] = false;
1466 :
1467 53162 : if (!branch_removable_p (targ_bb[i]))
1468 5414 : continue;
1469 :
1470 : /* Given a semi-invariant branch, if its opposite branch dominates
1471 : loop latch, it and its following trace will only be executed in
1472 : final iteration of loop, namely it is not part of repeated body
1473 : of the loop. Similar to the above case that the branch is loop
1474 : exit, no need to split loop. */
1475 47748 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
1476 0 : continue;
1477 :
1478 47748 : invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
1479 47748 : invar_checks++;
1480 : }
1481 :
1482 : /* With both branches being invariant (handled by loop unswitch) or
1483 : variant is not what we want. */
1484 26581 : if (invar[0] ^ !invar[1])
1485 : return NULL;
1486 :
1487 : /* Found a real loop-invariant condition, do nothing. */
1488 1667 : if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
1489 : return NULL;
1490 :
1491 1428 : return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1);
1492 : }
1493 :
1494 : /* Calculate increased code size measured by estimated insn number if applying
1495 : loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */
1496 :
1497 : static int
1498 886 : compute_added_num_insns (struct loop *loop, const_edge branch_edge)
1499 : {
1500 886 : basic_block cond_bb = branch_edge->src;
1501 886 : unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge;
1502 886 : basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest;
1503 886 : basic_block *bbs = ((split_info *) loop->aux)->bbs;
1504 886 : int num = 0;
1505 :
1506 7496 : for (unsigned i = 0; i < loop->num_nodes; i++)
1507 : {
1508 : /* Do no count basic blocks only in opposite branch. */
1509 6610 : if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb))
1510 2494 : continue;
1511 :
1512 8232 : num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
1513 : }
1514 :
1515 : /* It is unnecessary to evaluate expression of the conditional statement
1516 : in new loop that contains only invariant branch. This expression should
1517 : be constant value (either true or false). Exclude code size of insns
1518 : that contribute to computation of the expression. */
1519 :
1520 886 : auto_vec<gimple *> worklist;
1521 886 : hash_set<gimple *> removed;
1522 886 : gimple *stmt = last_nondebug_stmt (cond_bb);
1523 :
1524 886 : worklist.safe_push (stmt);
1525 886 : removed.add (stmt);
1526 886 : num -= estimate_num_insns (stmt, &eni_size_weights);
1527 :
1528 1062 : do
1529 : {
1530 1062 : ssa_op_iter opnd_iter;
1531 1062 : use_operand_p opnd_p;
1532 :
1533 1062 : stmt = worklist.pop ();
1534 3202 : FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE)
1535 : {
1536 1078 : tree opnd = USE_FROM_PTR (opnd_p);
1537 :
1538 1078 : if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd))
1539 80 : continue;
1540 :
1541 1053 : gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd);
1542 1053 : use_operand_p use_p;
1543 1053 : imm_use_iterator use_iter;
1544 :
1545 1053 : if (removed.contains (opnd_stmt)
1546 1053 : || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt)))
1547 55 : continue;
1548 :
1549 2317 : FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd)
1550 : {
1551 1143 : gimple *use_stmt = USE_STMT (use_p);
1552 :
1553 1143 : if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt))
1554 : {
1555 822 : opnd_stmt = NULL;
1556 822 : break;
1557 : }
1558 998 : }
1559 :
1560 998 : if (opnd_stmt)
1561 : {
1562 176 : worklist.safe_push (opnd_stmt);
1563 176 : removed.add (opnd_stmt);
1564 176 : num -= estimate_num_insns (opnd_stmt, &eni_size_weights);
1565 : }
1566 : }
1567 2124 : } while (!worklist.is_empty ());
1568 :
1569 886 : gcc_assert (num >= 0);
1570 886 : return num;
1571 886 : }
1572 :
1573 : /* Find out loop-invariant branch of a conditional statement (COND) if it has,
1574 : and check whether it is eligible and profitable to perform loop split upon
1575 : this branch in LOOP. */
1576 :
1577 : static edge
1578 136978 : get_cond_branch_to_split_loop (struct loop *loop, gcond *cond)
1579 : {
1580 136978 : edge invar_branch = get_cond_invariant_branch (loop, cond);
1581 136978 : if (!invar_branch)
1582 : return NULL;
1583 :
1584 : /* When accurate profile information is available, and execution
1585 : frequency of the branch is too low, just let it go. */
1586 886 : profile_probability prob = invar_branch->probability;
1587 886 : if (prob.reliable_p ())
1588 : {
1589 5 : int thres = param_min_loop_cond_split_prob;
1590 :
1591 10 : if (prob < profile_probability::always ().apply_scale (thres, 100))
1592 0 : return NULL;
1593 : }
1594 :
1595 : /* Add a threshold for increased code size to disable loop split. */
1596 886 : if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns)
1597 : return NULL;
1598 :
1599 : return invar_branch;
1600 : }
1601 :
1602 : /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
1603 : conditional statement, perform loop split transformation illustrated
1604 : as the following graph.
1605 :
1606 : .-------T------ if (true) ------F------.
1607 : | .---------------. |
1608 : | | | |
1609 : v | v v
1610 : pre-header | pre-header
1611 : | .------------. | | .------------.
1612 : | | | | | | |
1613 : | v | | | v |
1614 : header | | header |
1615 : | | | | |
1616 : .--- if (cond) ---. | | .--- if (true) ---. |
1617 : | | | | | | |
1618 : invariant | | | invariant | |
1619 : | | | | | | |
1620 : '---T--->.<---F---' | | '---T--->.<---F---' |
1621 : | | / | |
1622 : stmts | / stmts |
1623 : | F T | |
1624 : / \ | / / \ |
1625 : .-------* * [ if (cond) ] .-------* * |
1626 : | | | | | |
1627 : | latch | | latch |
1628 : | | | | | |
1629 : | '------------' | '------------'
1630 : '------------------------. .-----------'
1631 : loop1 | | loop2
1632 : v v
1633 : exits
1634 :
1635 : In the graph, loop1 represents the part derived from original one, and
1636 : loop2 is duplicated using loop_version (), which corresponds to the part
1637 : of original one being splitted out. In original latch edge of loop1, we
1638 : insert a new conditional statement duplicated from the semi-invariant cond,
1639 : and one of its branch goes back to loop1 header as a latch edge, and the
1640 : other branch goes to loop2 pre-header as an entry edge. And also in loop2,
1641 : we abandon the variant branch of the conditional statement by setting a
1642 : constant bool condition, based on which branch is semi-invariant. */
1643 :
1644 : static bool
1645 882 : do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
1646 : {
1647 882 : basic_block cond_bb = invar_branch->src;
1648 882 : bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE);
1649 1764 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1650 :
1651 882 : gcc_assert (cond_bb->loop_father == loop1);
1652 :
1653 882 : if (dump_enabled_p ())
1654 252 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
1655 : "loop split on semi-invariant condition at %s branch\n",
1656 : true_invar ? "true" : "false");
1657 :
1658 882 : initialize_original_copy_tables ();
1659 :
1660 882 : struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
1661 : invar_branch->probability.invert (),
1662 : invar_branch->probability,
1663 : profile_probability::always (),
1664 : profile_probability::always (),
1665 : true);
1666 882 : if (!loop2)
1667 : {
1668 0 : free_original_copy_tables ();
1669 0 : return false;
1670 : }
1671 :
1672 882 : basic_block cond_bb_copy = get_bb_copy (cond_bb);
1673 1764 : gcond *cond_copy = as_a<gcond *> (*gsi_last_bb (cond_bb_copy));
1674 :
1675 : /* Replace the condition in loop2 with a bool constant to let PassManager
1676 : remove the variant branch after current pass completes. */
1677 882 : if (true_invar)
1678 323 : gimple_cond_make_true (cond_copy);
1679 : else
1680 559 : gimple_cond_make_false (cond_copy);
1681 :
1682 882 : update_stmt (cond_copy);
1683 :
1684 : /* Insert a new conditional statement on latch edge of loop1, its condition
1685 : is duplicated from the semi-invariant. This statement acts as a switch
1686 : to transfer execution from loop1 to loop2, when loop1 enters into
1687 : invariant state. */
1688 882 : basic_block latch_bb = split_edge (loop_latch_edge (loop1));
1689 882 : basic_block break_bb = split_edge (single_pred_edge (latch_bb));
1690 882 : gimple *break_cond = gimple_build_cond (gimple_cond_code(cond),
1691 : gimple_cond_lhs (cond),
1692 : gimple_cond_rhs (cond),
1693 : NULL_TREE, NULL_TREE);
1694 :
1695 882 : gimple_stmt_iterator gsi = gsi_last_bb (break_bb);
1696 882 : gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
1697 :
1698 882 : edge to_loop1 = single_succ_edge (break_bb);
1699 882 : edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);
1700 :
1701 882 : to_loop1->flags &= ~EDGE_FALLTHRU;
1702 882 : to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
1703 882 : to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
1704 :
1705 : /* Due to introduction of a control flow edge from loop1 latch to loop2
1706 : pre-header, we should update PHIs in loop2 to reflect this connection
1707 : between loop1 and loop2. */
1708 882 : connect_loop_phis (loop1, loop2, to_loop2);
1709 :
1710 882 : edge true_edge, false_edge, skip_edge1, skip_edge2;
1711 882 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1712 :
1713 882 : skip_edge1 = true_invar ? false_edge : true_edge;
1714 882 : skip_edge2 = true_invar ? true_edge : false_edge;
1715 882 : fix_loop_bb_probability (loop1, loop2, skip_edge1, skip_edge2);
1716 :
1717 : /* Fix first loop's exit probability after scaling. */
1718 882 : to_loop1->probability = invar_branch->probability.invert ();
1719 882 : to_loop2->probability = invar_branch->probability;
1720 :
1721 882 : free_original_copy_tables ();
1722 :
1723 882 : return true;
1724 : }
1725 :
1726 : /* Traverse all conditional statements in LOOP, to find out a good candidate
1727 : upon which we can do loop split. */
1728 :
1729 : static bool
1730 80402 : split_loop_on_cond (struct loop *loop)
1731 : {
1732 80402 : split_info *info = new split_info ();
1733 80402 : basic_block *bbs = info->bbs = get_loop_body (loop);
1734 80402 : bool do_split = false;
1735 :
1736 : /* Allocate an area to keep temporary info, and associate its address
1737 : with loop aux field. */
1738 80402 : loop->aux = info;
1739 :
1740 569000 : for (unsigned i = 0; i < loop->num_nodes; i++)
1741 488598 : bbs[i]->aux = NULL;
1742 :
1743 562895 : for (unsigned i = 0; i < loop->num_nodes; i++)
1744 : {
1745 483375 : basic_block bb = bbs[i];
1746 :
1747 : /* We only consider conditional statement, which be executed at most once
1748 : in each iteration of the loop. So skip statements in inner loops. */
1749 483375 : if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP))
1750 135937 : continue;
1751 :
1752 : /* Actually this check is not a must constraint. With it, we can ensure
1753 : conditional statement will always be executed in each iteration. */
1754 347438 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1755 119470 : continue;
1756 :
1757 455936 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1758 227968 : if (!cond)
1759 90990 : continue;
1760 :
1761 136978 : edge branch_edge = get_cond_branch_to_split_loop (loop, cond);
1762 :
1763 136978 : if (branch_edge)
1764 : {
1765 882 : do_split_loop_on_cond (loop, branch_edge);
1766 882 : do_split = true;
1767 882 : break;
1768 : }
1769 : }
1770 :
1771 80402 : delete info;
1772 80402 : loop->aux = NULL;
1773 :
1774 80402 : return do_split;
1775 : }
1776 :
1777 : /* Main entry point. Perform loop splitting on all suitable loops. */
1778 :
1779 : static unsigned int
1780 28504 : tree_ssa_split_loops (void)
1781 : {
1782 28504 : bool changed = false;
1783 :
1784 28504 : gcc_assert (scev_initialized_p ());
1785 :
1786 28504 : calculate_dominance_info (CDI_POST_DOMINATORS);
1787 :
1788 196696 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1789 111184 : loop->aux = NULL;
1790 :
1791 : /* Go through all loops starting from innermost. */
1792 168192 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1793 : {
1794 82680 : if (loop->aux)
1795 : {
1796 : /* If any of our inner loops was split, don't split us,
1797 : and mark our containing loop as having had splits as well.
1798 : This allows for delaying SSA update. */
1799 486 : loop_outer (loop)->aux = loop;
1800 486 : continue;
1801 : }
1802 :
1803 82194 : if (optimize_loop_for_size_p (loop))
1804 1409 : continue;
1805 :
1806 80785 : if (split_loop (loop) || split_loop_on_cond (loop))
1807 : {
1808 : /* Mark our containing loop as having had some split inner loops. */
1809 1265 : loop_outer (loop)->aux = loop;
1810 1265 : changed = true;
1811 : }
1812 28504 : }
1813 :
1814 198518 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1815 113006 : loop->aux = NULL;
1816 :
1817 28504 : clear_aux_for_blocks ();
1818 :
1819 28504 : free_dominance_info (CDI_POST_DOMINATORS);
1820 :
1821 28504 : if (changed)
1822 : {
1823 907 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1824 907 : return TODO_cleanup_cfg;
1825 : }
1826 : return 0;
1827 : }
1828 :
1829 : /* Loop splitting pass. */
1830 :
1831 : namespace {
1832 :
1833 : const pass_data pass_data_loop_split =
1834 : {
1835 : GIMPLE_PASS, /* type */
1836 : "lsplit", /* name */
1837 : OPTGROUP_LOOP, /* optinfo_flags */
1838 : TV_LOOP_SPLIT, /* tv_id */
1839 : PROP_cfg, /* properties_required */
1840 : 0, /* properties_provided */
1841 : 0, /* properties_destroyed */
1842 : 0, /* todo_flags_start */
1843 : 0, /* todo_flags_finish */
1844 : };
1845 :
1846 : class pass_loop_split : public gimple_opt_pass
1847 : {
1848 : public:
1849 288767 : pass_loop_split (gcc::context *ctxt)
1850 577534 : : gimple_opt_pass (pass_data_loop_split, ctxt)
1851 : {}
1852 :
1853 : /* opt_pass methods: */
1854 241715 : bool gate (function *) final override { return flag_split_loops != 0; }
1855 : unsigned int execute (function *) final override;
1856 :
1857 : }; // class pass_loop_split
1858 :
1859 : unsigned int
1860 28504 : pass_loop_split::execute (function *fun)
1861 : {
1862 57008 : if (number_of_loops (fun) <= 1)
1863 : return 0;
1864 :
1865 28504 : return tree_ssa_split_loops ();
1866 : }
1867 :
1868 : } // anon namespace
1869 :
1870 : gimple_opt_pass *
1871 288767 : make_pass_loop_split (gcc::context *ctxt)
1872 : {
1873 288767 : return new pass_loop_split (ctxt);
1874 : }
|
