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 172924 : split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv,
81 : enum tree_code *guard_code)
82 : {
83 172924 : gcond *stmt;
84 172924 : affine_iv iv2;
85 :
86 : /* BB must end in a simple conditional jump. */
87 441549 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
88 76818 : if (!stmt)
89 : return NULL_TREE;
90 :
91 76818 : enum tree_code code = gimple_cond_code (stmt);
92 :
93 76818 : if (loop_exits_from_bb_p (loop, bb))
94 : return NULL_TREE;
95 :
96 34197 : tree op0 = gimple_cond_lhs (stmt);
97 34197 : tree op1 = gimple_cond_rhs (stmt);
98 34197 : class loop *useloop = loop_containing_stmt (stmt);
99 :
100 34197 : if (!simple_iv (loop, useloop, op0, iv, false))
101 : return NULL_TREE;
102 5518 : 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 2458 : if (!integer_zerop (iv2.step))
108 : {
109 783 : std::swap (op0, op1);
110 783 : std::swap (*iv, iv2);
111 783 : code = swap_tree_comparison (code);
112 783 : gimple_cond_set_condition (stmt, code, op0, op1);
113 783 : update_stmt (stmt);
114 : }
115 1675 : else if (integer_zerop (iv->step))
116 : return NULL_TREE;
117 1354 : if (!integer_zerop (iv2.step))
118 : return NULL_TREE;
119 1150 : 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 1088 : 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 896 : if (dump_file && (dump_flags & TDF_DETAILS))
173 : {
174 25 : fprintf (dump_file, "Found potential split point: ");
175 25 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
176 25 : fprintf (dump_file, " { ");
177 25 : print_generic_expr (dump_file, iv->base, TDF_SLIM);
178 25 : fprintf (dump_file, " + I*");
179 25 : print_generic_expr (dump_file, iv->step, TDF_SLIM);
180 25 : fprintf (dump_file, " } %s ", get_tree_code_name (code));
181 25 : print_generic_expr (dump_file, iv2.base, TDF_SLIM);
182 25 : fprintf (dump_file, "\n");
183 : }
184 :
185 896 : *border = iv2.base;
186 896 : *guard_code = code;
187 896 : 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 378 : patch_loop_exit (class loop *loop, tree_code guard_code, tree nextval,
198 : tree newbound, bool initial_true)
199 : {
200 378 : edge exit = single_exit (loop);
201 756 : gcond *stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
202 378 : gimple_cond_set_condition (stmt, guard_code, nextval, newbound);
203 378 : update_stmt (stmt);
204 :
205 378 : edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
206 :
207 378 : exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
208 378 : stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
209 :
210 378 : if (initial_true)
211 : {
212 270 : exit->flags |= EDGE_FALSE_VALUE;
213 270 : stay->flags |= EDGE_TRUE_VALUE;
214 : }
215 : else
216 : {
217 108 : exit->flags |= EDGE_TRUE_VALUE;
218 108 : stay->flags |= EDGE_FALSE_VALUE;
219 : }
220 378 : }
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 888 : find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/)
228 : {
229 888 : gimple *def = SSA_NAME_DEF_STMT (guard_iv);
230 888 : gphi *phi;
231 888 : if ((phi = dyn_cast <gphi *> (def))
232 378 : && gimple_bb (phi) == loop->header)
233 378 : 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 50223 : easy_exit_values (class loop *loop)
244 : {
245 50223 : edge exit = single_exit (loop);
246 50223 : edge latch = loop_latch_edge (loop);
247 50223 : 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 167208 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
253 : {
254 116988 : gphi *phi = psi.phi ();
255 116988 : tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
256 116988 : basic_block bb;
257 116988 : if (TREE_CODE (next) == SSA_NAME
258 115886 : && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
259 232871 : && !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 1262 : connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e)
276 : {
277 1262 : basic_block rest = loop_preheader_edge (loop2)->src;
278 1262 : gcc_assert (new_e->dest == rest);
279 1262 : edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
280 :
281 1262 : edge firste = loop_preheader_edge (loop1);
282 1262 : edge seconde = loop_preheader_edge (loop2);
283 1262 : edge firstn = loop_latch_edge (loop1);
284 1262 : gphi_iterator psi_first, psi_second;
285 1262 : for (psi_first = gsi_start_phis (loop1->header),
286 1262 : psi_second = gsi_start_phis (loop2->header);
287 5148 : !gsi_end_p (psi_first);
288 3886 : gsi_next (&psi_first), gsi_next (&psi_second))
289 : {
290 3886 : tree init, next, new_init;
291 3886 : use_operand_p op;
292 3886 : gphi *phi_first = psi_first.phi ();
293 3886 : gphi *phi_second = psi_second.phi ();
294 :
295 3886 : init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
296 3886 : next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
297 3886 : op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
298 3886 : 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 3886 : if (TREE_CODE (next) == SSA_NAME
304 7702 : && useless_type_conversion_p (TREE_TYPE (next),
305 3816 : TREE_TYPE (init)))
306 3816 : 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 3886 : gphi * newphi = create_phi_node (new_init, rest);
320 3886 : add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
321 3886 : add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
322 3886 : SET_USE (op, new_init);
323 : }
324 1262 : }
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 378 : connect_loops (class loop *loop1, class loop *loop2)
370 : {
371 378 : edge exit = single_exit (loop1);
372 378 : basic_block skip_bb = split_edge (exit);
373 378 : gcond *skip_stmt;
374 378 : gimple_stmt_iterator gsi;
375 378 : edge new_e, skip_e;
376 :
377 756 : gcond *stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
378 378 : 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 378 : gsi = gsi_last_bb (skip_bb);
383 378 : gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
384 :
385 378 : skip_e = EDGE_SUCC (skip_bb, 0);
386 378 : skip_e->flags &= ~EDGE_FALLTHRU;
387 378 : new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
388 378 : 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 289 : skip_e->flags |= EDGE_FALSE_VALUE;
396 289 : new_e->flags |= EDGE_TRUE_VALUE;
397 : }
398 :
399 378 : new_e->probability = profile_probability::very_likely ();
400 378 : skip_e->probability = new_e->probability.invert ();
401 :
402 378 : 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 378 : 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 378 : tree controlbase = force_gimple_operand (niter->control.base,
440 : stmts, true, NULL_TREE);
441 378 : tree controlstep = niter->control.step;
442 378 : tree enddiff;
443 378 : 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 375 : enddiff = gimple_build (stmts, MINUS_EXPR,
453 375 : TREE_TYPE (controlbase),
454 : controlbase, controlstep);
455 :
456 : /* Compute end-beg. */
457 378 : gimple_seq stmts2;
458 378 : tree end = force_gimple_operand (niter->bound, &stmts2,
459 : true, NULL_TREE);
460 378 : gimple_seq_add_seq_without_update (stmts, stmts2);
461 378 : if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
462 3 : enddiff = gimple_build (stmts, POINTER_DIFF_EXPR,
463 : ssizetype, end, enddiff);
464 : else
465 375 : enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
466 : end, enddiff);
467 :
468 : /* Compute guard_init + (end-beg). */
469 378 : tree newbound;
470 378 : 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 377 : enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
480 377 : 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 378 : int addbound = 0;
489 378 : enum tree_code minmax;
490 378 : if (niter->cmp == LT_EXPR)
491 : {
492 : /* GT and LE are the same, inverted. */
493 356 : 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 287 : tree type2 = TREE_TYPE (newbound);
508 287 : if (POINTER_TYPE_P (type2))
509 0 : type2 = sizetype;
510 574 : newbound = gimple_build (stmts,
511 287 : POINTER_TYPE_P (TREE_TYPE (newbound))
512 : ? POINTER_PLUS_EXPR : PLUS_EXPR,
513 287 : TREE_TYPE (newbound),
514 : newbound,
515 287 : build_int_cst (type2, addbound));
516 : }
517 :
518 378 : tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
519 : border, newbound);
520 378 : 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 true branches of that loop to avoid
525 : dropping 1s down. */
526 : static void
527 1262 : fix_loop_bb_probability (class loop *loop1, class loop *loop2, edge true_edge,
528 : edge false_edge)
529 : {
530 : /* Proportion first loop's bb counts except those dominated by true
531 : branch to avoid drop 1s down. */
532 1262 : basic_block *bbs1, *bbs2;
533 1262 : bbs1 = get_loop_body (loop1);
534 1262 : unsigned j;
535 14328 : for (j = 0; j < loop1->num_nodes; j++)
536 11804 : if (bbs1[j] == loop1->latch
537 : /* Watch for case where the true conditional is empty. */
538 10542 : || !single_pred_p (true_edge->dest)
539 21952 : || !dominated_by_p (CDI_DOMINATORS, bbs1[j], true_edge->dest))
540 8642 : bbs1[j]->count
541 8642 : = bbs1[j]->count.apply_probability (true_edge->probability);
542 1262 : free (bbs1);
543 :
544 : /* Proportion second loop's bb counts except those dominated by false
545 : branch to avoid drop 1s down. */
546 1262 : basic_block bbi_copy = get_bb_copy (false_edge->dest);
547 1262 : bbs2 = get_loop_body (loop2);
548 12560 : for (j = 0; j < loop2->num_nodes; j++)
549 10036 : if (bbs2[j] == loop2->latch
550 : /* Watch for case where the flase conditional is empty. */
551 8774 : || !single_pred_p (bbi_copy)
552 14638 : || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy))
553 9011 : bbs2[j]->count
554 9011 : = bbs2[j]->count.apply_probability (true_edge->probability.invert ());
555 1262 : free (bbs2);
556 1262 : }
557 :
558 : /* Checks if LOOP contains an conditional block whose condition
559 : depends on which side in the iteration space it is, and if so
560 : splits the iteration space into two loops. Returns true if the
561 : loop was split. NITER must contain the iteration descriptor for the
562 : single exit of LOOP. */
563 :
564 : static bool
565 79759 : split_loop (class loop *loop1)
566 : {
567 79759 : class tree_niter_desc niter;
568 79759 : basic_block *bbs;
569 79759 : unsigned i;
570 79759 : bool changed = false;
571 79759 : tree guard_iv;
572 79759 : tree border = NULL_TREE;
573 79759 : affine_iv iv;
574 79759 : edge exit1;
575 :
576 79759 : if (!(exit1 = single_exit (loop1))
577 54841 : || EDGE_COUNT (exit1->src->succs) != 2
578 : /* ??? We could handle non-empty latches when we split the latch edge
579 : (not the exit edge), and put the new exit condition in the new block.
580 : OTOH this executes some code unconditionally that might have been
581 : skipped by the original exit before. */
582 54813 : || !empty_block_p (loop1->latch)
583 50223 : || !easy_exit_values (loop1)
584 50220 : || !number_of_iterations_exit (loop1, exit1, &niter, false, true)
585 123012 : || niter.cmp == ERROR_MARK)
586 36562 : return false;
587 43197 : if (niter.cmp == NE_EXPR)
588 : {
589 27421 : if (!niter.control.no_overflow)
590 : return false;
591 27135 : if (tree_int_cst_sign_bit (niter.control.step))
592 2687 : niter.cmp = GT_EXPR;
593 : else
594 24448 : niter.cmp = LT_EXPR;
595 : }
596 :
597 42911 : bbs = get_loop_body (loop1);
598 :
599 42911 : if (!can_copy_bbs_p (bbs, loop1->num_nodes))
600 : {
601 4 : free (bbs);
602 4 : return false;
603 : }
604 :
605 : /* Find a splitting opportunity. */
606 : enum tree_code guard_code;
607 215453 : for (i = 0; i < loop1->num_nodes; i++)
608 172924 : if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv, &guard_code)))
609 : {
610 : /* Handling opposite steps is not implemented yet. Neither
611 : is handling different step sizes. */
612 896 : if ((tree_int_cst_sign_bit (iv.step)
613 896 : != tree_int_cst_sign_bit (niter.control.step))
614 896 : || !tree_int_cst_equal (iv.step, niter.control.step))
615 518 : continue;
616 :
617 : /* Find a loop PHI node that defines guard_iv directly,
618 : or create one doing that. */
619 888 : gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
620 888 : if (!phi)
621 510 : continue;
622 378 : const tree phi_result = gimple_phi_result (phi);
623 756 : gcond *guard_stmt = as_a<gcond *> (*gsi_last_bb (bbs[i]));
624 378 : tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
625 : loop_preheader_edge (loop1));
626 :
627 : /* Loop splitting is implemented by versioning the loop, placing
628 : the new loop after the old loop, make the first loop iterate
629 : as long as the conditional stays true (or false) and let the
630 : second (new) loop handle the rest of the iterations.
631 :
632 : First we need to determine if the condition will start being true
633 : or false in the first loop. */
634 378 : bool initial_true;
635 378 : switch (guard_code)
636 : {
637 268 : case LT_EXPR:
638 268 : case LE_EXPR:
639 268 : initial_true = !tree_int_cst_sign_bit (iv.step);
640 268 : break;
641 110 : case GT_EXPR:
642 110 : case GE_EXPR:
643 110 : initial_true = tree_int_cst_sign_bit (iv.step);
644 110 : break;
645 0 : default:
646 0 : gcc_unreachable ();
647 : }
648 :
649 : /* Build a condition that will skip the first loop when the
650 : guard condition won't ever be true (or false). */
651 378 : gimple_seq stmts2;
652 378 : border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
653 378 : if (stmts2)
654 : {
655 : /* When the split condition is not always evaluated make sure
656 : to rewrite it to defined overflow. */
657 2 : if (!dominated_by_p (CDI_DOMINATORS, exit1->src, bbs[i]))
658 : {
659 2 : gimple_stmt_iterator gsi;
660 2 : gsi = gsi_start (stmts2);
661 6 : while (!gsi_end_p (gsi))
662 : {
663 4 : if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
664 2 : rewrite_to_defined_unconditional (&gsi);
665 4 : gsi_next (&gsi);
666 : }
667 : }
668 2 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
669 : stmts2);
670 : }
671 378 : tree cond = fold_build2 (guard_code, boolean_type_node,
672 : guard_init, border);
673 378 : if (!initial_true)
674 108 : cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
675 :
676 378 : edge true_edge, false_edge;
677 378 : extract_true_false_edges_from_block (bbs[i], &true_edge, &false_edge);
678 :
679 : /* Now version the loop, placing loop2 after loop1 connecting
680 : them, and fix up SSA form for that. */
681 378 : initialize_original_copy_tables ();
682 378 : basic_block cond_bb;
683 :
684 378 : profile_probability loop1_prob
685 378 : = integer_onep (cond) ? profile_probability::always ()
686 100 : : true_edge->probability;
687 : /* TODO: It is commonly a case that we know that both loops will be
688 : entered. very_likely below is the probability that second loop will
689 : be entered given by connect_loops. We should work out the common
690 : case it is always true. */
691 378 : class loop *loop2 = loop_version (loop1, cond, &cond_bb,
692 : loop1_prob,
693 : /* Pass always as we will later
694 : redirect first loop to second
695 : loop. */
696 : profile_probability::always (),
697 : profile_probability::always (),
698 : profile_probability::very_likely (),
699 : true);
700 378 : gcc_assert (loop2);
701 :
702 : /* The phi address may have changed due to being resized in
703 : loop_version (), so reobtain it. */
704 378 : phi = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_result));
705 378 : gcc_checking_assert (gimple_bb (phi) == loop1->header);
706 :
707 : /* Correct probability of edge cond_bb->preheader_of_loop2. */
708 378 : single_pred_edge
709 378 : (loop_preheader_edge (loop2)->src)->probability
710 378 : = loop1_prob.invert ();
711 :
712 378 : fix_loop_bb_probability (loop1, loop2, true_edge, false_edge);
713 : /* If conditional we split on has reliable profilea nd both
714 : preconditionals of loop1 and loop2 are constant true, we can
715 : only redistribute the iteration counts to the split loops.
716 :
717 : If the conditionals we insert before loop1 or loop2 are non-trivial
718 : they increase expected loop count, so account this accordingly.
719 : If we do not know the probability of split conditional, avoid
720 : reudcing loop estimates, since we do not really know how they are
721 : split between of the two new loops. Keep orignal estimate since
722 : it is likely better then completely dropping it.
723 :
724 : TODO: If we know that one of the new loops has constant
725 : number of iterations, we can do better. We could also update
726 : upper bounds. */
727 378 : if (loop1->any_estimate
728 378 : && wi::fits_shwi_p (loop1->nb_iterations_estimate))
729 : {
730 407 : sreal scale = true_edge->probability.reliable_p ()
731 207 : ? true_edge->probability.to_sreal () : (sreal)1;
732 407 : sreal scale2 = false_edge->probability.reliable_p ()
733 207 : ? false_edge->probability.to_sreal () : (sreal)1;
734 207 : sreal div1 = loop1_prob.initialized_p ()
735 209 : ? loop1_prob.to_sreal () : (sreal)1/(sreal)2;
736 : /* +1 to get header interations rather than latch iterations and then
737 : -1 to convert back. */
738 207 : if (div1 != 0)
739 206 : loop1->nb_iterations_estimate
740 411 : = MAX ((((sreal)loop1->nb_iterations_estimate.to_shwi () + 1)
741 : * scale / div1).to_nearest_int () - 1, 0);
742 : else
743 1 : loop1->any_estimate = false;
744 207 : loop2->nb_iterations_estimate
745 207 : = MAX ((((sreal)loop2->nb_iterations_estimate.to_shwi () + 1) * scale2
746 : / profile_probability::very_likely ().to_sreal ())
747 : .to_nearest_int () - 1, 0);
748 : }
749 378 : update_loop_exit_probability_scale_dom_bbs (loop1);
750 378 : update_loop_exit_probability_scale_dom_bbs (loop2);
751 :
752 378 : edge new_e = connect_loops (loop1, loop2);
753 378 : connect_loop_phis (loop1, loop2, new_e);
754 :
755 : /* The iterations of the second loop is now already
756 : exactly those that the first loop didn't do, but the
757 : iteration space of the first loop is still the original one.
758 : Compute the new bound for the guarding IV and patch the
759 : loop exit to use it instead of original IV and bound. */
760 378 : gimple_seq stmts = NULL;
761 378 : tree newend = compute_new_first_bound (&stmts, &niter, border,
762 : guard_code, guard_init);
763 378 : if (stmts)
764 181 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
765 : stmts);
766 378 : tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
767 378 : patch_loop_exit (loop1, guard_code, guard_next, newend, initial_true);
768 :
769 : /* Finally patch out the two copies of the condition to be always
770 : true/false (or opposite). */
771 756 : gcond *force_true = as_a<gcond *> (*gsi_last_bb (bbs[i]));
772 756 : gcond *force_false = as_a<gcond *> (*gsi_last_bb (get_bb_copy (bbs[i])));
773 378 : if (!initial_true)
774 108 : std::swap (force_true, force_false);
775 378 : gimple_cond_make_true (force_true);
776 378 : gimple_cond_make_false (force_false);
777 378 : update_stmt (force_true);
778 378 : update_stmt (force_false);
779 :
780 378 : free_original_copy_tables ();
781 :
782 378 : changed = true;
783 378 : if (dump_file && (dump_flags & TDF_DETAILS))
784 25 : fprintf (dump_file, ";; Loop split.\n");
785 :
786 378 : if (dump_enabled_p ())
787 26 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, guard_stmt, "loop split\n");
788 :
789 : /* Only deal with the first opportunity. */
790 378 : break;
791 : }
792 :
793 42907 : free (bbs);
794 42907 : return changed;
795 79759 : }
796 :
797 : /* Another transformation of loops like:
798 :
799 : for (i = INIT (); CHECK (i); i = NEXT ())
800 : {
801 : if (expr (a_1, a_2, ..., a_n)) // expr is pure
802 : a_j = ...; // change at least one a_j
803 : else
804 : S; // not change any a_j
805 : }
806 :
807 : into:
808 :
809 : for (i = INIT (); CHECK (i); i = NEXT ())
810 : {
811 : if (expr (a_1, a_2, ..., a_n))
812 : a_j = ...;
813 : else
814 : {
815 : S;
816 : i = NEXT ();
817 : break;
818 : }
819 : }
820 :
821 : for (; CHECK (i); i = NEXT ())
822 : {
823 : S;
824 : }
825 :
826 : */
827 :
828 : /* Data structure to hold temporary information during loop split upon
829 : semi-invariant conditional statement. */
830 : class split_info {
831 : public:
832 : /* Array of all basic blocks in a loop, returned by get_loop_body(). */
833 : basic_block *bbs;
834 :
835 : /* All memory store/clobber statements in a loop. */
836 : auto_vec<gimple *> memory_stores;
837 :
838 : /* Whether above memory stores vector has been filled. */
839 : int need_init;
840 :
841 : /* Control dependencies of basic blocks in a loop. */
842 : auto_vec<hash_set<basic_block> *> control_deps;
843 :
844 79381 : split_info () : bbs (NULL), need_init (true) { }
845 :
846 79381 : ~split_info ()
847 : {
848 79381 : if (bbs)
849 79381 : free (bbs);
850 :
851 80046 : for (unsigned i = 0; i < control_deps.length (); i++)
852 1330 : delete control_deps[i];
853 79381 : }
854 : };
855 :
856 : /* Find all statements with memory-write effect in LOOP, including memory
857 : store and non-pure function call, and keep those in a vector. This work
858 : is only done one time, for the vector should be constant during analysis
859 : stage of semi-invariant condition. */
860 :
861 : static void
862 11030 : find_vdef_in_loop (struct loop *loop)
863 : {
864 11030 : split_info *info = (split_info *) loop->aux;
865 11030 : gphi *vphi = get_virtual_phi (loop->header);
866 :
867 : /* Indicate memory store vector has been filled. */
868 11030 : info->need_init = false;
869 :
870 : /* If loop contains memory operation, there must be a virtual PHI node in
871 : loop header basic block. */
872 11030 : if (vphi == NULL)
873 2673 : return;
874 :
875 : /* All virtual SSA names inside the loop are connected to be a cyclic
876 : graph via virtual PHI nodes. The virtual PHI node in loop header just
877 : links the first and the last virtual SSA names, by using the last as
878 : PHI operand to define the first. */
879 8418 : const edge latch = loop_latch_edge (loop);
880 8418 : const tree first = gimple_phi_result (vphi);
881 8418 : const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
882 :
883 : /* The virtual SSA cyclic graph might consist of only one SSA name, who
884 : is defined by itself.
885 :
886 : .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
887 :
888 : This means the loop contains only memory loads, so we can skip it. */
889 8418 : if (first == last)
890 : return;
891 :
892 8357 : auto_vec<gimple *> other_stores;
893 8357 : auto_vec<tree> worklist;
894 8357 : auto_bitmap visited;
895 :
896 8357 : bitmap_set_bit (visited, SSA_NAME_VERSION (first));
897 8357 : bitmap_set_bit (visited, SSA_NAME_VERSION (last));
898 8357 : worklist.safe_push (last);
899 :
900 55948 : do
901 : {
902 55948 : tree vuse = worklist.pop ();
903 55948 : gimple *stmt = SSA_NAME_DEF_STMT (vuse);
904 :
905 : /* We mark the first and last SSA names as visited at the beginning,
906 : and reversely start the process from the last SSA name towards the
907 : first, which ensures that this do-while will not touch SSA names
908 : defined outside the loop. */
909 55948 : gcc_assert (gimple_bb (stmt)
910 : && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
911 :
912 55948 : if (gimple_code (stmt) == GIMPLE_PHI)
913 : {
914 15239 : gphi *phi = as_a <gphi *> (stmt);
915 :
916 46969 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
917 : {
918 31730 : tree arg = gimple_phi_arg_def (stmt, i);
919 :
920 31730 : if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
921 20794 : worklist.safe_push (arg);
922 : }
923 : }
924 : else
925 : {
926 40709 : tree prev = gimple_vuse (stmt);
927 :
928 : /* Non-pure call statement is conservatively assumed to impact all
929 : memory locations. So place call statements ahead of other memory
930 : stores in the vector with an idea of using them as shortcut
931 : terminators to memory alias analysis. */
932 40709 : if (gimple_code (stmt) == GIMPLE_CALL)
933 14121 : info->memory_stores.safe_push (stmt);
934 : else
935 26588 : other_stores.safe_push (stmt);
936 :
937 40709 : if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
938 26797 : worklist.safe_push (prev);
939 : }
940 111896 : } while (!worklist.is_empty ());
941 :
942 8357 : info->memory_stores.safe_splice (other_stores);
943 8357 : }
944 :
945 : /* Two basic blocks have equivalent control dependency if one dominates to
946 : the other, and it is post-dominated by the latter. Given a basic block
947 : BB in LOOP, find farest equivalent dominating basic block. For BB, there
948 : is a constraint that BB does not post-dominate loop header of LOOP, this
949 : means BB is control-dependent on at least one basic block in LOOP. */
950 :
951 : static basic_block
952 1300 : get_control_equiv_head_block (struct loop *loop, basic_block bb)
953 : {
954 1375 : while (!bb->aux)
955 : {
956 768 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
957 :
958 768 : gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb));
959 :
960 768 : if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb))
961 : break;
962 :
963 : bb = dom_bb;
964 : }
965 1300 : return bb;
966 : }
967 :
968 : /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
969 : dependent on. */
970 :
971 : static hash_set<basic_block> *
972 7916 : find_control_dep_blocks (struct loop *loop, basic_block bb)
973 : {
974 : /* BB has same control dependency as loop header, then it is not control-
975 : dependent on any basic block in LOOP. */
976 7916 : if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb))
977 : return NULL;
978 :
979 1272 : basic_block equiv_head = get_control_equiv_head_block (loop, bb);
980 :
981 1272 : if (equiv_head->aux)
982 : {
983 : /* There is a basic block containing control dependency equivalent
984 : to BB. No need to recompute that, and also set this information
985 : to other equivalent basic blocks. */
986 607 : for (; bb != equiv_head;
987 0 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
988 0 : bb->aux = equiv_head->aux;
989 607 : return (hash_set<basic_block> *) equiv_head->aux;
990 : }
991 :
992 : /* A basic block X is control-dependent on another Y iff there exists
993 : a path from X to Y, in which every basic block other than X and Y
994 : is post-dominated by Y, but X is not post-dominated by Y.
995 :
996 : According to this rule, traverse basic blocks in the loop backwards
997 : starting from BB, if a basic block is post-dominated by BB, extend
998 : current post-dominating path to this block, otherwise it is another
999 : one that BB is control-dependent on. */
1000 :
1001 665 : auto_vec<basic_block> pdom_worklist;
1002 665 : hash_set<basic_block> pdom_visited;
1003 665 : hash_set<basic_block> *dep_bbs = new hash_set<basic_block>;
1004 :
1005 665 : pdom_worklist.safe_push (equiv_head);
1006 :
1007 692 : do
1008 : {
1009 692 : basic_block pdom_bb = pdom_worklist.pop ();
1010 692 : edge_iterator ei;
1011 692 : edge e;
1012 :
1013 692 : if (pdom_visited.add (pdom_bb))
1014 0 : continue;
1015 :
1016 1414 : FOR_EACH_EDGE (e, ei, pdom_bb->preds)
1017 : {
1018 722 : basic_block pred_bb = e->src;
1019 :
1020 722 : if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb))
1021 : {
1022 694 : dep_bbs->add (pred_bb);
1023 722 : continue;
1024 : }
1025 :
1026 28 : pred_bb = get_control_equiv_head_block (loop, pred_bb);
1027 :
1028 28 : if (pdom_visited.contains (pred_bb))
1029 1 : continue;
1030 :
1031 27 : if (!pred_bb->aux)
1032 : {
1033 27 : pdom_worklist.safe_push (pred_bb);
1034 27 : continue;
1035 : }
1036 :
1037 : /* If control dependency of basic block is available, fast extend
1038 : post-dominating path using the information instead of advancing
1039 : forward step-by-step. */
1040 0 : hash_set<basic_block> *pred_dep_bbs
1041 : = (hash_set<basic_block> *) pred_bb->aux;
1042 :
1043 0 : for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin ();
1044 0 : iter != pred_dep_bbs->end (); ++iter)
1045 : {
1046 0 : basic_block pred_dep_bb = *iter;
1047 :
1048 : /* Basic blocks can either be in control dependency of BB, or
1049 : must be post-dominated by BB, if so, extend the path from
1050 : these basic blocks. */
1051 0 : if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb))
1052 0 : dep_bbs->add (pred_dep_bb);
1053 0 : else if (!pdom_visited.contains (pred_dep_bb))
1054 0 : pdom_worklist.safe_push (pred_dep_bb);
1055 : }
1056 : }
1057 1384 : } while (!pdom_worklist.is_empty ());
1058 :
1059 : /* Record computed control dependencies in loop so that we can reach them
1060 : when reclaiming resources. */
1061 665 : ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs);
1062 :
1063 : /* Associate control dependence with related equivalent basic blocks. */
1064 716 : for (equiv_head->aux = dep_bbs; bb != equiv_head;
1065 51 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1066 51 : bb->aux = dep_bbs;
1067 :
1068 665 : return dep_bbs;
1069 665 : }
1070 :
1071 : /* Forward declaration */
1072 :
1073 : static bool
1074 : stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
1075 : const_basic_block skip_head,
1076 : hash_map<gimple *, bool> &stmt_stat);
1077 :
1078 : /* Given STMT, memory load or pure call statement, check whether it is impacted
1079 : by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
1080 : trace is composed of SKIP_HEAD and those basic block dominated by it, always
1081 : corresponds to one branch of a conditional statement). If SKIP_HEAD is
1082 : NULL, all basic blocks of LOOP are checked. */
1083 :
1084 : static bool
1085 26653 : vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
1086 : const_basic_block skip_head)
1087 : {
1088 26653 : split_info *info = (split_info *) loop->aux;
1089 26653 : tree rhs = NULL_TREE;
1090 26653 : ao_ref ref;
1091 26653 : gimple *store;
1092 26653 : unsigned i;
1093 :
1094 : /* Collect memory store/clobber statements if haven't done that. */
1095 26653 : if (info->need_init)
1096 11030 : find_vdef_in_loop (loop);
1097 :
1098 26653 : if (is_gimple_assign (stmt))
1099 26444 : rhs = gimple_assign_rhs1 (stmt);
1100 :
1101 26653 : ao_ref_init (&ref, rhs);
1102 :
1103 92854 : FOR_EACH_VEC_ELT (info->memory_stores, i, store)
1104 : {
1105 : /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */
1106 70224 : if (skip_head
1107 50853 : && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head))
1108 19371 : continue;
1109 :
1110 31482 : if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
1111 11305 : return false;
1112 : }
1113 :
1114 : return true;
1115 : }
1116 :
1117 : /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
1118 : certain iteration of LOOP, check whether an SSA name (NAME) remains
1119 : unchanged in next iteration. We call this characteristic semi-
1120 : invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic
1121 : blocks and control flows in the loop will be considered. Semi-invariant
1122 : state of checked statement is cached in hash map STMT_STAT to avoid
1123 : redundant computation in possible following re-check. */
1124 :
1125 : static inline bool
1126 171320 : ssa_semi_invariant_p (struct loop *loop, tree name,
1127 : const_basic_block skip_head,
1128 : hash_map<gimple *, bool> &stmt_stat)
1129 : {
1130 171320 : gimple *def = SSA_NAME_DEF_STMT (name);
1131 171320 : const_basic_block def_bb = gimple_bb (def);
1132 :
1133 : /* An SSA name defined outside loop is definitely semi-invariant. */
1134 171320 : if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
1135 14503 : return true;
1136 :
1137 156817 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1138 : return false;
1139 :
1140 156809 : return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat);
1141 : }
1142 :
1143 : /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
1144 : semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1145 : are excluded from LOOP. */
1146 :
1147 : static bool
1148 31397 : loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi,
1149 : const_basic_block skip_head)
1150 : {
1151 31397 : const_edge latch = loop_latch_edge (loop);
1152 31397 : tree name = gimple_phi_result (loop_phi);
1153 31397 : tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch);
1154 :
1155 31397 : gcc_checking_assert (from);
1156 :
1157 : /* Loop iteration PHI node locates in loop header, and it has two source
1158 : operands, one is an initial value coming from outside the loop, the other
1159 : is a value through latch of the loop, which is derived in last iteration,
1160 : we call the latter latch value. From the PHI node to definition of latch
1161 : value, if excluding branch trace starting from SKIP_HEAD, except copy-
1162 : assignment or likewise, there is no other kind of value redefinition, SSA
1163 : name defined by the PHI node is semi-invariant.
1164 :
1165 : loop entry
1166 : | .--- latch ---.
1167 : | | |
1168 : v v |
1169 : x_1 = PHI <x_0, x_3> |
1170 : | |
1171 : v |
1172 : .------- if (cond) -------. |
1173 : | | |
1174 : | [ SKIP ] |
1175 : | | |
1176 : | x_2 = ... |
1177 : | | |
1178 : '---- T ---->.<---- F ----' |
1179 : | |
1180 : v |
1181 : x_3 = PHI <x_1, x_2> |
1182 : | |
1183 : '----------------------'
1184 :
1185 : Suppose in certain iteration, execution flow in above graph goes through
1186 : true branch, which means that one source value to define x_3 in false
1187 : branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
1188 : iterations is defined by x_3, we know that x_1 will never changed if COND
1189 : always chooses true branch from then on. */
1190 :
1191 35203 : while (from != name)
1192 : {
1193 : /* A new value comes from a CONSTANT. */
1194 34252 : if (TREE_CODE (from) != SSA_NAME)
1195 : return false;
1196 :
1197 32617 : gimple *stmt = SSA_NAME_DEF_STMT (from);
1198 32617 : const_basic_block bb = gimple_bb (stmt);
1199 :
1200 : /* A new value comes from outside the loop. */
1201 32617 : if (!bb || !flow_bb_inside_loop_p (loop, bb))
1202 40 : return false;
1203 :
1204 32577 : from = NULL_TREE;
1205 :
1206 32577 : if (gimple_code (stmt) == GIMPLE_PHI)
1207 : {
1208 7146 : gphi *phi = as_a <gphi *> (stmt);
1209 :
1210 19090 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1211 : {
1212 15284 : if (skip_head)
1213 : {
1214 14626 : const_edge e = gimple_phi_arg_edge (phi, i);
1215 :
1216 : /* Don't consider redefinitions in excluded basic blocks. */
1217 14626 : if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head))
1218 4213 : continue;
1219 : }
1220 :
1221 11071 : tree arg = gimple_phi_arg_def (phi, i);
1222 :
1223 11071 : if (!from)
1224 : from = arg;
1225 3925 : else if (!operand_equal_p (from, arg, 0))
1226 : /* There are more than one source operands that provide
1227 : different values to the SSA name, it is variant. */
1228 : return false;
1229 : }
1230 : }
1231 25431 : else if (gimple_code (stmt) == GIMPLE_ASSIGN)
1232 : {
1233 : /* For simple value copy, check its rhs instead. */
1234 25271 : if (gimple_assign_ssa_name_copy_p (stmt))
1235 0 : from = gimple_assign_rhs1 (stmt);
1236 : }
1237 :
1238 : /* Any other kind of definition is deemed to introduce a new value
1239 : to the SSA name. */
1240 29237 : if (!from)
1241 : return false;
1242 : }
1243 : return true;
1244 : }
1245 :
1246 : /* Check whether conditional predicates that BB is control-dependent on, are
1247 : semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
1248 : are excluded from LOOP. Semi-invariant state of checked statement is cached
1249 : in hash map STMT_STAT. */
1250 :
1251 : static bool
1252 7916 : control_dep_semi_invariant_p (struct loop *loop, basic_block bb,
1253 : const_basic_block skip_head,
1254 : hash_map<gimple *, bool> &stmt_stat)
1255 : {
1256 7916 : hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb);
1257 :
1258 7916 : if (!dep_bbs)
1259 : return true;
1260 :
1261 1430 : for (hash_set<basic_block>::iterator iter = dep_bbs->begin ();
1262 1588 : iter != dep_bbs->end (); ++iter)
1263 : {
1264 1280 : gimple *last = *gsi_last_bb (*iter);
1265 1280 : if (!last)
1266 1122 : return false;
1267 :
1268 : /* Only check condition predicates. */
1269 1280 : if (gimple_code (last) != GIMPLE_COND
1270 1280 : && gimple_code (last) != GIMPLE_SWITCH)
1271 : return false;
1272 :
1273 1280 : if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat))
1274 : return false;
1275 : }
1276 :
1277 150 : return true;
1278 : }
1279 :
1280 : /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
1281 : semi-invariant, consequently, all its defined values are semi-invariant.
1282 : Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
1283 : Semi-invariant state of checked statement is cached in hash map
1284 : STMT_STAT. */
1285 :
1286 : static bool
1287 206772 : stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
1288 : const_basic_block skip_head,
1289 : hash_map<gimple *, bool> &stmt_stat)
1290 : {
1291 206772 : bool existed;
1292 206772 : bool &invar = stmt_stat.get_or_insert (stmt, &existed);
1293 :
1294 206772 : if (existed)
1295 877 : return invar;
1296 :
1297 : /* A statement might depend on itself, which is treated as variant. So set
1298 : state of statement under check to be variant to ensure that. */
1299 205895 : invar = false;
1300 :
1301 205895 : if (gimple_code (stmt) == GIMPLE_PHI)
1302 : {
1303 56866 : gphi *phi = as_a <gphi *> (stmt);
1304 :
1305 56866 : if (gimple_bb (stmt) == loop->header)
1306 : {
1307 : /* If the entry value is subject to abnormal coalescing
1308 : avoid the transform since we're going to duplicate the
1309 : loop header and thus likely introduce overlapping life-ranges
1310 : between the PHI def and the entry on the path when the
1311 : first loop is skipped. */
1312 31397 : tree entry_def
1313 31397 : = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1314 31397 : if (TREE_CODE (entry_def) == SSA_NAME
1315 31397 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (entry_def))
1316 : return false;
1317 31397 : invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head);
1318 31397 : return invar;
1319 : }
1320 :
1321 : /* For a loop PHI node that does not locate in loop header, it is semi-
1322 : invariant only if two conditions are met. The first is its source
1323 : values are derived from CONSTANT (including loop-invariant value), or
1324 : from SSA name defined by semi-invariant loop iteration PHI node. The
1325 : second is its source incoming edges are control-dependent on semi-
1326 : invariant conditional predicates. */
1327 25514 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1328 : {
1329 25510 : const_edge e = gimple_phi_arg_edge (phi, i);
1330 25510 : tree arg = gimple_phi_arg_def (phi, i);
1331 :
1332 25510 : if (TREE_CODE (arg) == SSA_NAME)
1333 : {
1334 25060 : if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat))
1335 : return false;
1336 :
1337 : /* If source value is defined in location from where the source
1338 : edge comes in, no need to check control dependency again
1339 : since this has been done in above SSA name check stage. */
1340 58 : if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1341 4 : continue;
1342 : }
1343 :
1344 504 : if (!control_dep_semi_invariant_p (loop, e->src, skip_head,
1345 : stmt_stat))
1346 : return false;
1347 : }
1348 : }
1349 : else
1350 : {
1351 149029 : ssa_op_iter iter;
1352 149029 : tree use;
1353 :
1354 : /* Volatile memory load or return of normal (non-const/non-pure) call
1355 : should not be treated as constant in each iteration of loop. */
1356 149029 : if (gimple_has_side_effects (stmt))
1357 141621 : return false;
1358 :
1359 : /* Check if any memory store may kill memory load at this place. */
1360 244368 : if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head))
1361 : return false;
1362 :
1363 : /* Although operand of a statement might be SSA name, CONSTANT or
1364 : VARDECL, here we only need to check SSA name operands. This is
1365 : because check on VARDECL operands, which involve memory loads,
1366 : must have been done prior to invocation of this function in
1367 : vuse_semi_invariant_p. */
1368 153668 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1369 146260 : if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat))
1370 : return false;
1371 : }
1372 :
1373 7412 : if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head,
1374 : stmt_stat))
1375 : return false;
1376 :
1377 : /* Here we SHOULD NOT use invar = true, since hash map might be changed due
1378 : to new insertion, and thus invar may point to invalid memory. */
1379 6753 : stmt_stat.put (stmt, true);
1380 6753 : return true;
1381 : }
1382 :
1383 : /* A helper function to check whether STMT is semi-invariant in LOOP. Basic
1384 : blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */
1385 :
1386 : static bool
1387 48683 : stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
1388 : const_basic_block skip_head)
1389 : {
1390 48683 : hash_map<gimple *, bool> stmt_stat;
1391 48683 : return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat);
1392 48683 : }
1393 :
1394 : /* Determine when conditional statement never transfers execution to one of its
1395 : branch, whether we can remove the branch's leading basic block (BRANCH_BB)
1396 : and those basic blocks dominated by BRANCH_BB. */
1397 :
1398 : static bool
1399 52944 : branch_removable_p (basic_block branch_bb)
1400 : {
1401 52944 : edge_iterator ei;
1402 52944 : edge e;
1403 :
1404 52944 : if (single_pred_p (branch_bb))
1405 : return true;
1406 :
1407 8415 : FOR_EACH_EDGE (e, ei, branch_bb->preds)
1408 : {
1409 8415 : if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
1410 0 : continue;
1411 :
1412 8415 : if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
1413 2966 : continue;
1414 :
1415 : /* The branch can be reached from opposite branch, or from some
1416 : statement not dominated by the conditional statement. */
1417 : return false;
1418 : }
1419 :
1420 : return true;
1421 : }
1422 :
1423 : /* Find out which branch of a conditional statement (COND) is invariant in the
1424 : execution context of LOOP. That is: once the branch is selected in certain
1425 : iteration of the loop, any operand that contributes to computation of the
1426 : conditional statement remains unchanged in all following iterations. */
1427 :
1428 : static edge
1429 135396 : get_cond_invariant_branch (struct loop *loop, gcond *cond)
1430 : {
1431 135396 : basic_block cond_bb = gimple_bb (cond);
1432 135396 : basic_block targ_bb[2];
1433 135396 : bool invar[2];
1434 135396 : unsigned invar_checks = 0;
1435 :
1436 222650 : for (unsigned i = 0; i < 2; i++)
1437 : {
1438 196178 : targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
1439 :
1440 : /* One branch directs to loop exit, no need to perform loop split upon
1441 : this conditional statement. Firstly, it is trivial if the exit branch
1442 : is semi-invariant, for the statement is just to break loop. Secondly,
1443 : if the opposite branch is semi-invariant, it means that the statement
1444 : is real loop-invariant, which is covered by loop unswitch. */
1445 196178 : if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
1446 : return NULL;
1447 : }
1448 :
1449 79416 : for (unsigned i = 0; i < 2; i++)
1450 : {
1451 52944 : invar[!i] = false;
1452 :
1453 52944 : if (!branch_removable_p (targ_bb[i]))
1454 5449 : continue;
1455 :
1456 : /* Given a semi-invariant branch, if its opposite branch dominates
1457 : loop latch, it and its following trace will only be executed in
1458 : final iteration of loop, namely it is not part of repeated body
1459 : of the loop. Similar to the above case that the branch is loop
1460 : exit, no need to split loop. */
1461 47495 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
1462 0 : continue;
1463 :
1464 47495 : invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
1465 47495 : invar_checks++;
1466 : }
1467 :
1468 : /* With both branches being invariant (handled by loop unswitch) or
1469 : variant is not what we want. */
1470 26472 : if (invar[0] ^ !invar[1])
1471 : return NULL;
1472 :
1473 : /* Found a real loop-invariant condition, do nothing. */
1474 1676 : if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
1475 : return NULL;
1476 :
1477 1425 : return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1);
1478 : }
1479 :
1480 : /* Calculate increased code size measured by estimated insn number if applying
1481 : loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */
1482 :
1483 : static int
1484 888 : compute_added_num_insns (struct loop *loop, const_edge branch_edge)
1485 : {
1486 888 : basic_block cond_bb = branch_edge->src;
1487 888 : unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge;
1488 888 : basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest;
1489 888 : basic_block *bbs = ((split_info *) loop->aux)->bbs;
1490 888 : int num = 0;
1491 :
1492 7543 : for (unsigned i = 0; i < loop->num_nodes; i++)
1493 : {
1494 : /* Do no count basic blocks only in opposite branch. */
1495 6655 : if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb))
1496 2507 : continue;
1497 :
1498 8296 : num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
1499 : }
1500 :
1501 : /* It is unnecessary to evaluate expression of the conditional statement
1502 : in new loop that contains only invariant branch. This expression should
1503 : be constant value (either true or false). Exclude code size of insns
1504 : that contribute to computation of the expression. */
1505 :
1506 888 : auto_vec<gimple *> worklist;
1507 888 : hash_set<gimple *> removed;
1508 888 : gimple *stmt = last_nondebug_stmt (cond_bb);
1509 :
1510 888 : worklist.safe_push (stmt);
1511 888 : removed.add (stmt);
1512 888 : num -= estimate_num_insns (stmt, &eni_size_weights);
1513 :
1514 1062 : do
1515 : {
1516 1062 : ssa_op_iter opnd_iter;
1517 1062 : use_operand_p opnd_p;
1518 :
1519 1062 : stmt = worklist.pop ();
1520 3200 : FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE)
1521 : {
1522 1076 : tree opnd = USE_FROM_PTR (opnd_p);
1523 :
1524 1076 : if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd))
1525 80 : continue;
1526 :
1527 1051 : gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd);
1528 1051 : use_operand_p use_p;
1529 1051 : imm_use_iterator use_iter;
1530 :
1531 1051 : if (removed.contains (opnd_stmt)
1532 1051 : || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt)))
1533 55 : continue;
1534 :
1535 2294 : FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd)
1536 : {
1537 1124 : gimple *use_stmt = USE_STMT (use_p);
1538 :
1539 1124 : if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt))
1540 : {
1541 822 : opnd_stmt = NULL;
1542 822 : break;
1543 : }
1544 996 : }
1545 :
1546 996 : if (opnd_stmt)
1547 : {
1548 174 : worklist.safe_push (opnd_stmt);
1549 174 : removed.add (opnd_stmt);
1550 174 : num -= estimate_num_insns (opnd_stmt, &eni_size_weights);
1551 : }
1552 : }
1553 2124 : } while (!worklist.is_empty ());
1554 :
1555 888 : gcc_assert (num >= 0);
1556 888 : return num;
1557 888 : }
1558 :
1559 : /* Find out loop-invariant branch of a conditional statement (COND) if it has,
1560 : and check whether it is eligible and profitable to perform loop split upon
1561 : this branch in LOOP. */
1562 :
1563 : static edge
1564 135396 : get_cond_branch_to_split_loop (struct loop *loop, gcond *cond)
1565 : {
1566 135396 : edge invar_branch = get_cond_invariant_branch (loop, cond);
1567 135396 : if (!invar_branch)
1568 : return NULL;
1569 :
1570 : /* When accurate profile information is available, and execution
1571 : frequency of the branch is too low, just let it go. */
1572 888 : profile_probability prob = invar_branch->probability;
1573 888 : if (prob.reliable_p ())
1574 : {
1575 5 : int thres = param_min_loop_cond_split_prob;
1576 :
1577 10 : if (prob < profile_probability::always ().apply_scale (thres, 100))
1578 0 : return NULL;
1579 : }
1580 :
1581 : /* Add a threshold for increased code size to disable loop split. */
1582 888 : if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns)
1583 : return NULL;
1584 :
1585 : return invar_branch;
1586 : }
1587 :
1588 : /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
1589 : conditional statement, perform loop split transformation illustrated
1590 : as the following graph.
1591 :
1592 : .-------T------ if (true) ------F------.
1593 : | .---------------. |
1594 : | | | |
1595 : v | v v
1596 : pre-header | pre-header
1597 : | .------------. | | .------------.
1598 : | | | | | | |
1599 : | v | | | v |
1600 : header | | header |
1601 : | | | | |
1602 : .--- if (cond) ---. | | .--- if (true) ---. |
1603 : | | | | | | |
1604 : invariant | | | invariant | |
1605 : | | | | | | |
1606 : '---T--->.<---F---' | | '---T--->.<---F---' |
1607 : | | / | |
1608 : stmts | / stmts |
1609 : | F T | |
1610 : / \ | / / \ |
1611 : .-------* * [ if (cond) ] .-------* * |
1612 : | | | | | |
1613 : | latch | | latch |
1614 : | | | | | |
1615 : | '------------' | '------------'
1616 : '------------------------. .-----------'
1617 : loop1 | | loop2
1618 : v v
1619 : exits
1620 :
1621 : In the graph, loop1 represents the part derived from original one, and
1622 : loop2 is duplicated using loop_version (), which corresponds to the part
1623 : of original one being splitted out. In original latch edge of loop1, we
1624 : insert a new conditional statement duplicated from the semi-invariant cond,
1625 : and one of its branch goes back to loop1 header as a latch edge, and the
1626 : other branch goes to loop2 pre-header as an entry edge. And also in loop2,
1627 : we abandon the variant branch of the conditional statement by setting a
1628 : constant bool condition, based on which branch is semi-invariant. */
1629 :
1630 : static bool
1631 884 : do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
1632 : {
1633 884 : basic_block cond_bb = invar_branch->src;
1634 884 : bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE);
1635 1768 : gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
1636 :
1637 884 : gcc_assert (cond_bb->loop_father == loop1);
1638 :
1639 884 : if (dump_enabled_p ())
1640 252 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
1641 : "loop split on semi-invariant condition at %s branch\n",
1642 : true_invar ? "true" : "false");
1643 :
1644 884 : initialize_original_copy_tables ();
1645 :
1646 884 : struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
1647 : invar_branch->probability.invert (),
1648 : invar_branch->probability,
1649 : profile_probability::always (),
1650 : profile_probability::always (),
1651 : true);
1652 884 : if (!loop2)
1653 : {
1654 0 : free_original_copy_tables ();
1655 0 : return false;
1656 : }
1657 :
1658 884 : basic_block cond_bb_copy = get_bb_copy (cond_bb);
1659 1768 : gcond *cond_copy = as_a<gcond *> (*gsi_last_bb (cond_bb_copy));
1660 :
1661 : /* Replace the condition in loop2 with a bool constant to let PassManager
1662 : remove the variant branch after current pass completes. */
1663 884 : if (true_invar)
1664 330 : gimple_cond_make_true (cond_copy);
1665 : else
1666 554 : gimple_cond_make_false (cond_copy);
1667 :
1668 884 : update_stmt (cond_copy);
1669 :
1670 : /* Insert a new conditional statement on latch edge of loop1, its condition
1671 : is duplicated from the semi-invariant. This statement acts as a switch
1672 : to transfer execution from loop1 to loop2, when loop1 enters into
1673 : invariant state. */
1674 884 : basic_block latch_bb = split_edge (loop_latch_edge (loop1));
1675 884 : basic_block break_bb = split_edge (single_pred_edge (latch_bb));
1676 884 : gimple *break_cond = gimple_build_cond (gimple_cond_code(cond),
1677 : gimple_cond_lhs (cond),
1678 : gimple_cond_rhs (cond),
1679 : NULL_TREE, NULL_TREE);
1680 :
1681 884 : gimple_stmt_iterator gsi = gsi_last_bb (break_bb);
1682 884 : gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
1683 :
1684 884 : edge to_loop1 = single_succ_edge (break_bb);
1685 884 : edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);
1686 :
1687 884 : to_loop1->flags &= ~EDGE_FALLTHRU;
1688 884 : to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
1689 884 : to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
1690 :
1691 : /* Due to introduction of a control flow edge from loop1 latch to loop2
1692 : pre-header, we should update PHIs in loop2 to reflect this connection
1693 : between loop1 and loop2. */
1694 884 : connect_loop_phis (loop1, loop2, to_loop2);
1695 :
1696 884 : edge true_edge, false_edge, skip_edge1, skip_edge2;
1697 884 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1698 :
1699 884 : skip_edge1 = true_invar ? false_edge : true_edge;
1700 884 : skip_edge2 = true_invar ? true_edge : false_edge;
1701 884 : fix_loop_bb_probability (loop1, loop2, skip_edge1, skip_edge2);
1702 :
1703 : /* Fix first loop's exit probability after scaling. */
1704 884 : to_loop1->probability = invar_branch->probability.invert ();
1705 884 : to_loop2->probability = invar_branch->probability;
1706 :
1707 884 : free_original_copy_tables ();
1708 :
1709 884 : return true;
1710 : }
1711 :
1712 : /* Traverse all conditional statements in LOOP, to find out a good candidate
1713 : upon which we can do loop split. */
1714 :
1715 : static bool
1716 79381 : split_loop_on_cond (struct loop *loop)
1717 : {
1718 79381 : split_info *info = new split_info ();
1719 79381 : basic_block *bbs = info->bbs = get_loop_body (loop);
1720 79381 : bool do_split = false;
1721 :
1722 : /* Allocate an area to keep temporary info, and associate its address
1723 : with loop aux field. */
1724 79381 : loop->aux = info;
1725 :
1726 567265 : for (unsigned i = 0; i < loop->num_nodes; i++)
1727 487884 : bbs[i]->aux = NULL;
1728 :
1729 561035 : for (unsigned i = 0; i < loop->num_nodes; i++)
1730 : {
1731 482538 : basic_block bb = bbs[i];
1732 :
1733 : /* We only consider conditional statement, which be executed at most once
1734 : in each iteration of the loop. So skip statements in inner loops. */
1735 482538 : if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP))
1736 137238 : continue;
1737 :
1738 : /* Actually this check is not a must constraint. With it, we can ensure
1739 : conditional statement will always be executed in each iteration. */
1740 345300 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1741 119931 : continue;
1742 :
1743 450738 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1744 225369 : if (!cond)
1745 89973 : continue;
1746 :
1747 135396 : edge branch_edge = get_cond_branch_to_split_loop (loop, cond);
1748 :
1749 135396 : if (branch_edge)
1750 : {
1751 884 : do_split_loop_on_cond (loop, branch_edge);
1752 884 : do_split = true;
1753 884 : break;
1754 : }
1755 : }
1756 :
1757 79381 : delete info;
1758 79381 : loop->aux = NULL;
1759 :
1760 79381 : return do_split;
1761 : }
1762 :
1763 : /* Main entry point. Perform loop splitting on all suitable loops. */
1764 :
1765 : static unsigned int
1766 28039 : tree_ssa_split_loops (void)
1767 : {
1768 28039 : bool changed = false;
1769 :
1770 28039 : gcc_assert (scev_initialized_p ());
1771 :
1772 28039 : calculate_dominance_info (CDI_POST_DOMINATORS);
1773 :
1774 193811 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1775 109694 : loop->aux = NULL;
1776 :
1777 : /* Go through all loops starting from innermost. */
1778 165772 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1779 : {
1780 81655 : if (loop->aux)
1781 : {
1782 : /* If any of our inner loops was split, don't split us,
1783 : and mark our containing loop as having had splits as well.
1784 : This allows for delaying SSA update. */
1785 479 : loop_outer (loop)->aux = loop;
1786 479 : continue;
1787 : }
1788 :
1789 81176 : if (optimize_loop_for_size_p (loop))
1790 1417 : continue;
1791 :
1792 79759 : if (split_loop (loop) || split_loop_on_cond (loop))
1793 : {
1794 : /* Mark our containing loop as having had some split inner loops. */
1795 1262 : loop_outer (loop)->aux = loop;
1796 1262 : changed = true;
1797 : }
1798 28039 : }
1799 :
1800 195625 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
1801 111508 : loop->aux = NULL;
1802 :
1803 28039 : clear_aux_for_blocks ();
1804 :
1805 28039 : free_dominance_info (CDI_POST_DOMINATORS);
1806 :
1807 28039 : if (changed)
1808 : {
1809 904 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1810 904 : return TODO_cleanup_cfg;
1811 : }
1812 : return 0;
1813 : }
1814 :
1815 : /* Loop splitting pass. */
1816 :
1817 : namespace {
1818 :
1819 : const pass_data pass_data_loop_split =
1820 : {
1821 : GIMPLE_PASS, /* type */
1822 : "lsplit", /* name */
1823 : OPTGROUP_LOOP, /* optinfo_flags */
1824 : TV_LOOP_SPLIT, /* tv_id */
1825 : PROP_cfg, /* properties_required */
1826 : 0, /* properties_provided */
1827 : 0, /* properties_destroyed */
1828 : 0, /* todo_flags_start */
1829 : 0, /* todo_flags_finish */
1830 : };
1831 :
1832 : class pass_loop_split : public gimple_opt_pass
1833 : {
1834 : public:
1835 285722 : pass_loop_split (gcc::context *ctxt)
1836 571444 : : gimple_opt_pass (pass_data_loop_split, ctxt)
1837 : {}
1838 :
1839 : /* opt_pass methods: */
1840 241458 : bool gate (function *) final override { return flag_split_loops != 0; }
1841 : unsigned int execute (function *) final override;
1842 :
1843 : }; // class pass_loop_split
1844 :
1845 : unsigned int
1846 28039 : pass_loop_split::execute (function *fun)
1847 : {
1848 56078 : if (number_of_loops (fun) <= 1)
1849 : return 0;
1850 :
1851 28039 : return tree_ssa_split_loops ();
1852 : }
1853 :
1854 : } // anon namespace
1855 :
1856 : gimple_opt_pass *
1857 285722 : make_pass_loop_split (gcc::context *ctxt)
1858 : {
1859 285722 : return new pass_loop_split (ctxt);
1860 : }
|
