Line data Source code
1 : /* Loop manipulation code for GNU compiler.
2 : Copyright (C) 2002-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 under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : 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 "rtl.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "cfghooks.h"
28 : #include "cfganal.h"
29 : #include "cfgloop.h"
30 : #include "gimple-iterator.h"
31 : #include "gimplify-me.h"
32 : #include "tree-ssa-loop-manip.h"
33 : #include "dumpfile.h"
34 : #include "sreal.h"
35 : #include "tree-cfg.h"
36 : #include "tree-pass.h"
37 :
38 : static void copy_loops_to (class loop **, int,
39 : class loop *);
40 : static void loop_redirect_edge (edge, basic_block);
41 : static void remove_bbs (basic_block *, int);
42 : static bool rpe_enum_p (const_basic_block, const void *);
43 : static int find_path (edge, basic_block **);
44 : static void fix_loop_placements (class loop *, bool *, bitmap);
45 : static bool fix_bb_placement (basic_block);
46 : static void fix_bb_placements (basic_block, bool *, bitmap);
47 :
48 : /* Checks whether basic block BB is dominated by DATA. */
49 : static bool
50 458662 : rpe_enum_p (const_basic_block bb, const void *data)
51 : {
52 458662 : return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data);
53 : }
54 :
55 : /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
56 :
57 : static void
58 458664 : remove_bbs (basic_block *bbs, int nbbs)
59 : {
60 458664 : int i;
61 :
62 917328 : for (i = 0; i < nbbs; i++)
63 458664 : delete_basic_block (bbs[i]);
64 458664 : }
65 :
66 : /* Find path -- i.e. the basic blocks dominated by edge E and put them
67 : into array BBS, that will be allocated large enough to contain them.
68 : E->dest must have exactly one predecessor for this to work (it is
69 : easy to achieve and we do not put it here because we do not want to
70 : alter anything by this function). The number of basic blocks in the
71 : path is returned. */
72 : static int
73 458664 : find_path (edge e, basic_block **bbs)
74 : {
75 458664 : gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
76 :
77 : /* Find bbs in the path. */
78 458664 : *bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
79 458664 : return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
80 458664 : n_basic_blocks_for_fn (cfun), e->dest);
81 : }
82 :
83 : /* Fix placement of basic block BB inside loop hierarchy --
84 : Let L be a loop to that BB belongs. Then every successor of BB must either
85 : 1) belong to some superloop of loop L, or
86 : 2) be a header of loop K such that K->outer is superloop of L
87 : Returns true if we had to move BB into other loop to enforce this condition,
88 : false if the placement of BB was already correct (provided that placements
89 : of its successors are correct). */
90 : static bool
91 264446 : fix_bb_placement (basic_block bb)
92 : {
93 264446 : edge e;
94 264446 : edge_iterator ei;
95 264446 : class loop *loop = current_loops->tree_root, *act;
96 :
97 544610 : FOR_EACH_EDGE (e, ei, bb->succs)
98 : {
99 280164 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
100 0 : continue;
101 :
102 280164 : act = e->dest->loop_father;
103 280164 : if (act->header == e->dest)
104 314 : act = loop_outer (act);
105 :
106 280164 : if (flow_loop_nested_p (loop, act))
107 280164 : loop = act;
108 : }
109 :
110 264446 : if (loop == bb->loop_father)
111 : return false;
112 :
113 59969 : remove_bb_from_loops (bb);
114 59969 : add_bb_to_loop (bb, loop);
115 :
116 59969 : return true;
117 : }
118 :
119 : /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
120 : of LOOP to that leads at least one exit edge of LOOP, and set it
121 : as the immediate superloop of LOOP. Return true if the immediate superloop
122 : of LOOP changed.
123 :
124 : IRRED_INVALIDATED is set to true if a change in the loop structures might
125 : invalidate the information about irreducible regions. */
126 :
127 : static bool
128 253670 : fix_loop_placement (class loop *loop, bool *irred_invalidated,
129 : bitmap loop_closed_ssa_invalidated)
130 : {
131 253670 : unsigned i;
132 253670 : edge e;
133 253670 : auto_vec<edge> exits = get_loop_exit_edges (loop);
134 253670 : class loop *father = current_loops->tree_root, *act;
135 253670 : bool ret = false;
136 :
137 1714505 : FOR_EACH_VEC_ELT (exits, i, e)
138 : {
139 1460835 : act = find_common_loop (loop, e->dest->loop_father);
140 1460835 : if (flow_loop_nested_p (father, act))
141 84649 : father = act;
142 : }
143 :
144 253670 : if (father != loop_outer (loop))
145 : {
146 897 : for (act = loop_outer (loop); act != father; act = loop_outer (act))
147 583 : act->num_nodes -= loop->num_nodes;
148 314 : flow_loop_tree_node_remove (loop);
149 314 : flow_loop_tree_node_add (father, loop);
150 :
151 : /* The exit edges of LOOP no longer exits its original immediate
152 : superloops; remove them from the appropriate exit lists. */
153 973 : FOR_EACH_VEC_ELT (exits, i, e)
154 : {
155 : /* We may need to recompute irreducible loops. */
156 345 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
157 0 : *irred_invalidated = true;
158 345 : rescan_loop_exit (e, false, false);
159 : }
160 : /* Any LC SSA PHIs on e->dest might now be on the wrong edge
161 : if their defs were in a former outer loop. Also all uses
162 : in the original inner loop of defs in the outer loop(s) now
163 : require LC PHI nodes. */
164 314 : if (loop_closed_ssa_invalidated)
165 : {
166 13 : basic_block *bbs = get_loop_body (loop);
167 107 : for (unsigned i = 0; i < loop->num_nodes; ++i)
168 81 : bitmap_set_bit (loop_closed_ssa_invalidated, bbs[i]->index);
169 13 : free (bbs);
170 : }
171 :
172 : ret = true;
173 : }
174 :
175 253670 : return ret;
176 253670 : }
177 :
178 : /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
179 : enforce condition stated in description of fix_bb_placement. We
180 : start from basic block FROM that had some of its successors removed, so that
181 : his placement no longer has to be correct, and iteratively fix placement of
182 : its predecessors that may change if placement of FROM changed. Also fix
183 : placement of subloops of FROM->loop_father, that might also be altered due
184 : to this change; the condition for them is similar, except that instead of
185 : successors we consider edges coming out of the loops.
186 :
187 : If the changes may invalidate the information about irreducible regions,
188 : IRRED_INVALIDATED is set to true.
189 :
190 : If LOOP_CLOSED_SSA_INVLIDATED is non-zero then all basic blocks with
191 : changed loop_father are collected there. */
192 :
193 : static void
194 605192 : fix_bb_placements (basic_block from,
195 : bool *irred_invalidated,
196 : bitmap loop_closed_ssa_invalidated)
197 : {
198 605192 : basic_block *queue, *qtop, *qbeg, *qend;
199 605192 : class loop *base_loop, *target_loop;
200 605192 : edge e;
201 :
202 : /* We pass through blocks back-reachable from FROM, testing whether some
203 : of their successors moved to outer loop. It may be necessary to
204 : iterate several times, but it is finite, as we stop unless we move
205 : the basic block up the loop structure. The whole story is a bit
206 : more complicated due to presence of subloops, those are moved using
207 : fix_loop_placement. */
208 :
209 605192 : base_loop = from->loop_father;
210 : /* If we are already in the outermost loop, the basic blocks cannot be moved
211 : outside of it. If FROM is the header of the base loop, it cannot be moved
212 : outside of it, either. In both cases, we can end now. */
213 605192 : if (base_loop == current_loops->tree_root
214 245462 : || from == base_loop->header)
215 405845 : return;
216 :
217 199347 : auto_sbitmap in_queue (last_basic_block_for_fn (cfun));
218 199347 : bitmap_clear (in_queue);
219 199347 : bitmap_set_bit (in_queue, from->index);
220 : /* Prevent us from going out of the base_loop. */
221 199347 : bitmap_set_bit (in_queue, base_loop->header->index);
222 :
223 199347 : queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);
224 199347 : qtop = queue + base_loop->num_nodes + 1;
225 199347 : qbeg = queue;
226 199347 : qend = queue + 1;
227 199347 : *qbeg = from;
228 :
229 464429 : while (qbeg != qend)
230 : {
231 265082 : edge_iterator ei;
232 265082 : from = *qbeg;
233 265082 : qbeg++;
234 265082 : if (qbeg == qtop)
235 0 : qbeg = queue;
236 265082 : bitmap_clear_bit (in_queue, from->index);
237 :
238 265082 : if (from->loop_father->header == from)
239 : {
240 : /* Subloop header, maybe move the loop upward. */
241 636 : if (!fix_loop_placement (from->loop_father, irred_invalidated,
242 : loop_closed_ssa_invalidated))
243 204805 : continue;
244 308 : target_loop = loop_outer (from->loop_father);
245 : }
246 : else
247 : {
248 : /* Ordinary basic block. */
249 264446 : if (!fix_bb_placement (from))
250 204477 : continue;
251 59969 : target_loop = from->loop_father;
252 59969 : if (loop_closed_ssa_invalidated)
253 21574 : bitmap_set_bit (loop_closed_ssa_invalidated, from->index);
254 : }
255 :
256 92947 : FOR_EACH_EDGE (e, ei, from->succs)
257 : {
258 32670 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
259 1 : *irred_invalidated = true;
260 : }
261 :
262 : /* Something has changed, insert predecessors into queue. */
263 126967 : FOR_EACH_EDGE (e, ei, from->preds)
264 : {
265 66690 : basic_block pred = e->src;
266 66690 : class loop *nca;
267 :
268 66690 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
269 0 : *irred_invalidated = true;
270 :
271 66690 : if (bitmap_bit_p (in_queue, pred->index))
272 955 : continue;
273 :
274 : /* If it is subloop, then it either was not moved, or
275 : the path up the loop tree from base_loop do not contain
276 : it. */
277 65735 : nca = find_common_loop (pred->loop_father, base_loop);
278 65735 : if (pred->loop_father != base_loop
279 636 : && (nca == base_loop
280 308 : || nca != pred->loop_father))
281 636 : pred = pred->loop_father->header;
282 65099 : else if (!flow_loop_nested_p (target_loop, pred->loop_father))
283 : {
284 : /* If PRED is already higher in the loop hierarchy than the
285 : TARGET_LOOP to that we moved FROM, the change of the position
286 : of FROM does not affect the position of PRED, so there is no
287 : point in processing it. */
288 0 : continue;
289 : }
290 :
291 65735 : if (bitmap_bit_p (in_queue, pred->index))
292 0 : continue;
293 :
294 : /* Schedule the basic block. */
295 65735 : *qend = pred;
296 65735 : qend++;
297 65735 : if (qend == qtop)
298 0 : qend = queue;
299 65735 : bitmap_set_bit (in_queue, pred->index);
300 : }
301 : }
302 199347 : free (queue);
303 199347 : }
304 :
305 : /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
306 : and update loop structures and dominators. Return true if we were able
307 : to remove the path, false otherwise (and nothing is affected then). */
308 : bool
309 458664 : remove_path (edge e, bool *irred_invalidated,
310 : bitmap loop_closed_ssa_invalidated)
311 : {
312 458664 : edge ae;
313 458664 : basic_block *rem_bbs, *bord_bbs, from, bb;
314 458664 : vec<basic_block> dom_bbs;
315 458664 : int i, nrem, n_bord_bbs;
316 458664 : bool local_irred_invalidated = false;
317 458664 : edge_iterator ei;
318 458664 : class loop *l, *f;
319 :
320 458664 : if (! irred_invalidated)
321 151774 : irred_invalidated = &local_irred_invalidated;
322 :
323 458664 : if (!can_remove_branch_p (e))
324 : return false;
325 :
326 : /* Keep track of whether we need to update information about irreducible
327 : regions. This is the case if the removed area is a part of the
328 : irreducible region, or if the set of basic blocks that belong to a loop
329 : that is inside an irreducible region is changed, or if such a loop is
330 : removed. */
331 458664 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
332 219 : *irred_invalidated = true;
333 :
334 : /* We need to check whether basic blocks are dominated by the edge
335 : e, but we only have basic block dominators. This is easy to
336 : fix -- when e->dest has exactly one predecessor, this corresponds
337 : to blocks dominated by e->dest, if not, split the edge. */
338 458664 : if (!single_pred_p (e->dest))
339 458662 : e = single_pred_edge (split_edge (e));
340 :
341 : /* It may happen that by removing path we remove one or more loops
342 : we belong to. In this case first unloop the loops, then proceed
343 : normally. We may assume that e->dest is not a header of any loop,
344 : as it now has exactly one predecessor. */
345 771904 : for (l = e->src->loop_father; loop_outer (l); l = f)
346 : {
347 313240 : f = loop_outer (l);
348 313240 : if (dominated_by_p (CDI_DOMINATORS, l->latch, e->dest))
349 2 : unloop (l, irred_invalidated, loop_closed_ssa_invalidated);
350 : }
351 :
352 : /* Identify the path. */
353 458664 : nrem = find_path (e, &rem_bbs);
354 :
355 458664 : n_bord_bbs = 0;
356 458664 : bord_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
357 458664 : auto_sbitmap seen (last_basic_block_for_fn (cfun));
358 458664 : bitmap_clear (seen);
359 :
360 : /* Find "border" hexes -- i.e. those with predecessor in removed path. */
361 1375992 : for (i = 0; i < nrem; i++)
362 458664 : bitmap_set_bit (seen, rem_bbs[i]->index);
363 458664 : if (!*irred_invalidated)
364 1375174 : FOR_EACH_EDGE (ae, ei, e->src->succs)
365 458436 : if (ae != e && ae->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
366 458436 : && !bitmap_bit_p (seen, ae->dest->index)
367 1375274 : && ae->flags & EDGE_IRREDUCIBLE_LOOP)
368 : {
369 100 : *irred_invalidated = true;
370 100 : break;
371 : }
372 :
373 917328 : for (i = 0; i < nrem; i++)
374 : {
375 917326 : FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
376 458662 : if (ae->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
377 458662 : && !bitmap_bit_p (seen, ae->dest->index))
378 : {
379 458662 : bitmap_set_bit (seen, ae->dest->index);
380 458662 : bord_bbs[n_bord_bbs++] = ae->dest;
381 :
382 458662 : if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
383 219 : *irred_invalidated = true;
384 : }
385 : }
386 :
387 : /* Remove the path. */
388 458664 : from = e->src;
389 458664 : remove_branch (e);
390 458664 : dom_bbs.create (0);
391 :
392 : /* Cancel loops contained in the path. */
393 917328 : for (i = 0; i < nrem; i++)
394 458664 : if (rem_bbs[i]->loop_father->header == rem_bbs[i])
395 0 : cancel_loop_tree (rem_bbs[i]->loop_father);
396 :
397 458664 : remove_bbs (rem_bbs, nrem);
398 458664 : free (rem_bbs);
399 :
400 : /* Find blocks whose dominators may be affected. */
401 458664 : bitmap_clear (seen);
402 1375990 : for (i = 0; i < n_bord_bbs; i++)
403 : {
404 458662 : basic_block ldom;
405 :
406 458662 : bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
407 458662 : if (bitmap_bit_p (seen, bb->index))
408 0 : continue;
409 458662 : bitmap_set_bit (seen, bb->index);
410 :
411 458662 : for (ldom = first_dom_son (CDI_DOMINATORS, bb);
412 1502772 : ldom;
413 1044110 : ldom = next_dom_son (CDI_DOMINATORS, ldom))
414 1044110 : if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
415 882751 : dom_bbs.safe_push (ldom);
416 : }
417 :
418 : /* Recount dominators. */
419 458664 : iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);
420 458664 : dom_bbs.release ();
421 458664 : free (bord_bbs);
422 :
423 : /* Fix placements of basic blocks inside loops and the placement of
424 : loops in the loop tree. */
425 458664 : fix_bb_placements (from, irred_invalidated, loop_closed_ssa_invalidated);
426 458664 : fix_loop_placements (from->loop_father, irred_invalidated,
427 : loop_closed_ssa_invalidated);
428 :
429 458664 : if (local_irred_invalidated
430 458664 : && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
431 288 : mark_irreducible_loops ();
432 :
433 458664 : return true;
434 458664 : }
435 :
436 : /* Creates place for a new LOOP in loops structure of FN. */
437 :
438 : void
439 811113 : place_new_loop (struct function *fn, class loop *loop)
440 : {
441 811113 : loop->num = number_of_loops (fn);
442 811113 : vec_safe_push (loops_for_fn (fn)->larray, loop);
443 811113 : }
444 :
445 : /* Given LOOP structure with filled header and latch, find the body of the
446 : corresponding loop and add it to loops tree. Insert the LOOP as a son of
447 : outer. */
448 :
449 : void
450 112959 : add_loop (class loop *loop, class loop *outer)
451 : {
452 112959 : basic_block *bbs;
453 112959 : int i, n;
454 112959 : class loop *subloop;
455 112959 : edge e;
456 112959 : edge_iterator ei;
457 :
458 : /* Add it to loop structure. */
459 112959 : place_new_loop (cfun, loop);
460 112959 : flow_loop_tree_node_add (outer, loop);
461 :
462 : /* Find its nodes. */
463 112959 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
464 112959 : n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
465 :
466 797598 : for (i = 0; i < n; i++)
467 : {
468 684639 : if (bbs[i]->loop_father == outer)
469 : {
470 476529 : remove_bb_from_loops (bbs[i]);
471 476529 : add_bb_to_loop (bbs[i], loop);
472 476529 : continue;
473 : }
474 :
475 208110 : loop->num_nodes++;
476 :
477 : /* If we find a direct subloop of OUTER, move it to LOOP. */
478 208110 : subloop = bbs[i]->loop_father;
479 208110 : if (loop_outer (subloop) == outer
480 208110 : && subloop->header == bbs[i])
481 : {
482 19180 : flow_loop_tree_node_remove (subloop);
483 19180 : flow_loop_tree_node_add (loop, subloop);
484 : }
485 : }
486 :
487 : /* Update the information about loop exit edges. */
488 797598 : for (i = 0; i < n; i++)
489 : {
490 1678730 : FOR_EACH_EDGE (e, ei, bbs[i]->succs)
491 : {
492 994091 : rescan_loop_exit (e, false, false);
493 : }
494 : }
495 :
496 112959 : free (bbs);
497 112959 : }
498 :
499 : /* Scale profile of loop by P. */
500 :
501 : void
502 264082 : scale_loop_frequencies (class loop *loop, profile_probability p)
503 : {
504 264082 : basic_block *bbs;
505 :
506 264082 : bbs = get_loop_body (loop);
507 264082 : scale_bbs_frequencies (bbs, loop->num_nodes, p);
508 264082 : free (bbs);
509 264082 : }
510 :
511 : /* Scales the frequencies of all basic blocks in LOOP that are strictly
512 : dominated by BB by NUM/DEN. */
513 :
514 : void
515 38640 : scale_dominated_blocks_in_loop (class loop *loop, basic_block bb,
516 : profile_count num, profile_count den)
517 : {
518 38640 : basic_block son;
519 :
520 38640 : if (!den.nonzero_p () && !(num == profile_count::zero ()))
521 0 : return;
522 38640 : auto_vec <basic_block, 8> worklist;
523 38640 : worklist.safe_push (bb);
524 :
525 314172 : while (!worklist.is_empty ())
526 198252 : for (son = first_dom_son (CDI_DOMINATORS, worklist.pop ());
527 395795 : son;
528 197543 : son = next_dom_son (CDI_DOMINATORS, son))
529 : {
530 197543 : if (!flow_bb_inside_loop_p (loop, son))
531 37931 : continue;
532 159612 : son->count = son->count.apply_scale (num, den);
533 159612 : worklist.safe_push (son);
534 : }
535 38640 : }
536 :
537 : /* Return exit that suitable for update when loop iterations
538 : changed. */
539 :
540 : static edge
541 115233 : loop_exit_for_scaling (class loop *loop)
542 : {
543 115233 : edge exit_edge = single_exit (loop);
544 115233 : if (!exit_edge)
545 : {
546 8873 : auto_vec<edge> exits = get_loop_exit_edges (loop);
547 8873 : exit_edge = single_likely_exit (loop, exits);
548 8873 : }
549 115233 : return exit_edge;
550 : }
551 :
552 : /* Assume that loop's entry count and profile up to a given EXIT_EDGE is
553 : consistent. Update exit probability so loop exists with PROFILE_COUNT
554 : and rescale profile of basic blocks inside loop dominated by EXIT_EDGE->src.
555 :
556 : This is useful after number of iteraitons of loop has changed.
557 : If EXIT_EDGE is NULL, the function will try to identify suitable exit.
558 : If DESIRED_COUNT is NULL, loop entry count will be used.
559 : In consistent profile usually loop exists as many times as it is entred.
560 :
561 : Return updated exit if successful and NULL otherwise. */
562 :
563 : edge
564 145262 : update_loop_exit_probability_scale_dom_bbs (class loop *loop,
565 : edge exit_edge,
566 : profile_count desired_count)
567 : {
568 145262 : if (!exit_edge)
569 3120 : exit_edge = loop_exit_for_scaling (loop);
570 3120 : if (!exit_edge)
571 : {
572 2336 : if (dump_file && (dump_flags & TDF_DETAILS))
573 : {
574 275 : fprintf (dump_file, ";; Not updating exit probability of loop %i;"
575 : " it has no single exit\n",
576 : loop->num);
577 : }
578 : return NULL;
579 : }
580 : /* If exit is inside another loop, adjusting its probability will also
581 : adjust number of the inner loop iterations. Just do noting for now. */
582 142926 : if (!just_once_each_iteration_p (loop, exit_edge->src))
583 : {
584 14 : if (dump_file && (dump_flags & TDF_DETAILS))
585 : {
586 0 : fprintf (dump_file, ";; Not updating exit probability of loop %i;"
587 : " exit is inside inner loop\n",
588 : loop->num);
589 : }
590 : return NULL;
591 : }
592 : /* Normal loops exit as many times as they are entered. */
593 142912 : if (!desired_count.initialized_p ())
594 1646 : desired_count = loop_count_in (loop);
595 : /* See if everything is already perfect. */
596 142912 : if (desired_count == exit_edge->count ())
597 6734 : return exit_edge;
598 136178 : profile_count old_exit_count = exit_edge->count ();
599 : /* See if update is possible.
600 : Avoid turning probability to 0 or 1 just trying to reach impossible
601 : value.
602 :
603 : Natural profile update after some loop will happily scale header count to
604 : be less than count of entering the loop. This is bad idea and they should
605 : special case maybe_flat_loop_profile.
606 :
607 : It may also happen that the source basic block of the exit edge is
608 : inside in-loop condition:
609 :
610 : +-> header
611 : | |
612 : | B1
613 : | / \
614 : | | B2--exit_edge-->
615 : | \ /
616 : | B3
617 : +__/
618 :
619 : If B2 count is smaller than desired exit edge count
620 : the profile was inconsistent with the newly discovered upper bound.
621 : Probability of edge B1->B2 is too low. We do not attempt to fix
622 : that (as it is hard in general). */
623 136178 : if (desired_count > exit_edge->src->count
624 136178 : && exit_edge->src->count.differs_from_p (desired_count))
625 : {
626 446 : if (dump_file)
627 : {
628 7 : fprintf (dump_file, ";; Source bb of loop %i has count ",
629 : loop->num);
630 7 : exit_edge->src->count.dump (dump_file, cfun);
631 7 : fprintf (dump_file,
632 : " which is smaller then desired count of exiting loop ");
633 7 : desired_count.dump (dump_file, cfun);
634 7 : fprintf (dump_file, ". Profile update is impossible.\n");
635 : }
636 : /* Drop quality of probability since we know it likely
637 : bad. */
638 446 : exit_edge->probability = exit_edge->probability.guessed ();
639 446 : return NULL;
640 : }
641 135732 : if (!exit_edge->src->count.nonzero_p ())
642 : {
643 1 : if (dump_file)
644 : {
645 0 : fprintf (dump_file, ";; Not updating exit edge probability"
646 : " in loop %i since profile is zero ",
647 : loop->num);
648 : }
649 : return NULL;
650 : }
651 135731 : set_edge_probability_and_rescale_others
652 135731 : (exit_edge, desired_count.probability_in (exit_edge->src->count));
653 : /* Rescale the remaining edge probabilities and see if there is only
654 : one. */
655 135731 : edge other_edge = NULL;
656 135731 : bool found = false;
657 135731 : edge e;
658 135731 : edge_iterator ei;
659 407193 : FOR_EACH_EDGE (e, ei, exit_edge->src->succs)
660 271474 : if (!(e->flags & EDGE_FAKE)
661 271474 : && !loop_exit_edge_p (loop, e))
662 : {
663 135743 : if (found)
664 : {
665 : other_edge = NULL;
666 : break;
667 : }
668 : other_edge = e;
669 : found = true;
670 : }
671 : /* If there is only loop latch after other edge,
672 : update its profile. This is tiny bit more precise
673 : than scaling. */
674 135731 : if (other_edge && other_edge->dest == loop->latch)
675 : {
676 97922 : if (single_pred_p (loop->latch))
677 97922 : loop->latch->count = loop->latch->count
678 97922 : + old_exit_count - exit_edge->count ();
679 : }
680 : else
681 : /* If there are multiple blocks, just scale. */
682 75618 : scale_dominated_blocks_in_loop (loop, exit_edge->src,
683 75618 : exit_edge->src->count - exit_edge->count (),
684 37809 : exit_edge->src->count - old_exit_count);
685 : return exit_edge;
686 : }
687 :
688 : /* Scale profile in LOOP by P.
689 : If ITERATION_BOUND is not -1, scale even further if loop is predicted
690 : to iterate too many times.
691 : Before calling this function, preheader block profile should be already
692 : scaled to final count. This is necessary because loop iterations are
693 : determined by comparing header edge count to latch edge count and thus
694 : they need to be scaled synchronously. */
695 :
696 : void
697 296803 : scale_loop_profile (class loop *loop, profile_probability p,
698 : gcov_type iteration_bound)
699 : {
700 296803 : if (!(p == profile_probability::always ()))
701 : {
702 79753 : if (dump_file && (dump_flags & TDF_DETAILS))
703 : {
704 11529 : fprintf (dump_file, ";; Scaling loop %i with scale ",
705 : loop->num);
706 11529 : p.dump (dump_file);
707 11529 : fprintf (dump_file, "\n");
708 : }
709 :
710 : /* Scale the probabilities. */
711 79753 : scale_loop_frequencies (loop, p);
712 : }
713 :
714 296803 : if (iteration_bound == -1)
715 184690 : return;
716 :
717 245008 : sreal iterations;
718 245008 : if (!expected_loop_iterations_by_profile (loop, &iterations))
719 : return;
720 :
721 244318 : if (dump_file && (dump_flags & TDF_DETAILS))
722 : {
723 16147 : fprintf (dump_file,
724 : ";; Guessed iterations of loop %i is %f. New upper bound %i.\n",
725 : loop->num,
726 : iterations.to_double (),
727 : (int)iteration_bound);
728 : }
729 :
730 : /* See if loop is predicted to iterate too many times. */
731 244318 : if (iterations <= (sreal)iteration_bound)
732 : return;
733 :
734 112113 : profile_count count_in = loop_count_in (loop);
735 :
736 : /* Now scale the loop body so header count is
737 : count_in * (iteration_bound + 1) */
738 112113 : profile_probability scale_prob
739 112113 : = (count_in * (iteration_bound + 1)).probability_in (loop->header->count);
740 112113 : if (dump_file && (dump_flags & TDF_DETAILS))
741 : {
742 11111 : fprintf (dump_file, ";; Scaling loop %i with scale ",
743 : loop->num);
744 11111 : scale_prob.dump (dump_file);
745 11111 : fprintf (dump_file, " to reach upper bound %i\n",
746 : (int)iteration_bound);
747 : }
748 : /* Finally attempt to fix exit edge probability. */
749 112113 : edge exit_edge = loop_exit_for_scaling (loop);
750 :
751 : /* In a consistent profile unadjusted_exit_count should be same as count_in,
752 : however to preserve as much of the original info, avoid recomputing
753 : it. */
754 112113 : profile_count unadjusted_exit_count = profile_count::uninitialized ();
755 112113 : if (exit_edge)
756 109777 : unadjusted_exit_count = exit_edge->count ();
757 112113 : scale_loop_frequencies (loop, scale_prob);
758 112113 : update_loop_exit_probability_scale_dom_bbs (loop, exit_edge,
759 : unadjusted_exit_count);
760 : }
761 :
762 : /* Recompute dominance information for basic blocks outside LOOP. */
763 :
764 : static void
765 72036 : update_dominators_in_loop (class loop *loop)
766 : {
767 72036 : vec<basic_block> dom_bbs = vNULL;
768 72036 : basic_block *body;
769 72036 : unsigned i;
770 :
771 72036 : auto_sbitmap seen (last_basic_block_for_fn (cfun));
772 72036 : bitmap_clear (seen);
773 72036 : body = get_loop_body (loop);
774 :
775 516696 : for (i = 0; i < loop->num_nodes; i++)
776 372624 : bitmap_set_bit (seen, body[i]->index);
777 :
778 444660 : for (i = 0; i < loop->num_nodes; i++)
779 : {
780 372624 : basic_block ldom;
781 :
782 372624 : for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
783 706665 : ldom;
784 334041 : ldom = next_dom_son (CDI_DOMINATORS, ldom))
785 334041 : if (!bitmap_bit_p (seen, ldom->index))
786 : {
787 33453 : bitmap_set_bit (seen, ldom->index);
788 33453 : dom_bbs.safe_push (ldom);
789 : }
790 : }
791 :
792 72036 : iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
793 72036 : free (body);
794 72036 : dom_bbs.release ();
795 72036 : }
796 :
797 : /* Creates an if region as shown above. CONDITION is used to create
798 : the test for the if.
799 :
800 : |
801 : | ------------- -------------
802 : | | pred_bb | | pred_bb |
803 : | ------------- -------------
804 : | | |
805 : | | | ENTRY_EDGE
806 : | | ENTRY_EDGE V
807 : | | ====> -------------
808 : | | | cond_bb |
809 : | | | CONDITION |
810 : | | -------------
811 : | V / \
812 : | ------------- e_false / \ e_true
813 : | | succ_bb | V V
814 : | ------------- ----------- -----------
815 : | | false_bb | | true_bb |
816 : | ----------- -----------
817 : | \ /
818 : | \ /
819 : | V V
820 : | -------------
821 : | | join_bb |
822 : | -------------
823 : | | exit_edge (result)
824 : | V
825 : | -----------
826 : | | succ_bb |
827 : | -----------
828 : |
829 : */
830 :
831 : edge
832 202 : create_empty_if_region_on_edge (edge entry_edge, tree condition)
833 : {
834 :
835 202 : basic_block cond_bb, true_bb, false_bb, join_bb;
836 202 : edge e_true, e_false, exit_edge;
837 202 : gcond *cond_stmt;
838 202 : tree simple_cond;
839 202 : gimple_stmt_iterator gsi;
840 :
841 202 : cond_bb = split_edge (entry_edge);
842 :
843 : /* Insert condition in cond_bb. */
844 202 : gsi = gsi_last_bb (cond_bb);
845 202 : simple_cond =
846 202 : force_gimple_operand_gsi (&gsi, condition, true, NULL,
847 : false, GSI_NEW_STMT);
848 202 : cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);
849 202 : gsi = gsi_last_bb (cond_bb);
850 202 : gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
851 :
852 202 : join_bb = split_edge (single_succ_edge (cond_bb));
853 :
854 202 : e_true = single_succ_edge (cond_bb);
855 202 : true_bb = split_edge (e_true);
856 :
857 202 : e_false = make_edge (cond_bb, join_bb, 0);
858 202 : false_bb = split_edge (e_false);
859 :
860 202 : e_true->flags &= ~EDGE_FALLTHRU;
861 202 : e_true->flags |= EDGE_TRUE_VALUE;
862 202 : e_false->flags &= ~EDGE_FALLTHRU;
863 202 : e_false->flags |= EDGE_FALSE_VALUE;
864 :
865 202 : set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);
866 202 : set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);
867 202 : set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);
868 202 : set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
869 :
870 202 : exit_edge = single_succ_edge (join_bb);
871 :
872 202 : if (single_pred_p (exit_edge->dest))
873 202 : set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);
874 :
875 202 : return exit_edge;
876 : }
877 :
878 : /* create_empty_loop_on_edge
879 : |
880 : | - pred_bb - ------ pred_bb ------
881 : | | | | iv0 = initial_value |
882 : | -----|----- ---------|-----------
883 : | | ______ | entry_edge
884 : | | entry_edge / | |
885 : | | ====> | -V---V- loop_header -------------
886 : | V | | iv_before = phi (iv0, iv_after) |
887 : | - succ_bb - | ---|-----------------------------
888 : | | | | |
889 : | ----------- | ---V--- loop_body ---------------
890 : | | | iv_after = iv_before + stride |
891 : | | | if (iv_before < upper_bound) |
892 : | | ---|--------------\--------------
893 : | | | \ exit_e
894 : | | V \
895 : | | - loop_latch - V- succ_bb -
896 : | | | | | |
897 : | | /------------- -----------
898 : | \ ___ /
899 :
900 : Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
901 : that is used before the increment of IV. IV_BEFORE should be used for
902 : adding code to the body that uses the IV. OUTER is the outer loop in
903 : which the new loop should be inserted.
904 :
905 : Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
906 : inserted on the loop entry edge. This implies that this function
907 : should be used only when the UPPER_BOUND expression is a loop
908 : invariant. */
909 :
910 : class loop *
911 504 : create_empty_loop_on_edge (edge entry_edge,
912 : tree initial_value,
913 : tree stride, tree upper_bound,
914 : tree iv,
915 : tree *iv_before,
916 : tree *iv_after,
917 : class loop *outer)
918 : {
919 504 : basic_block loop_header, loop_latch, succ_bb, pred_bb;
920 504 : class loop *loop;
921 504 : gimple_stmt_iterator gsi;
922 504 : gimple_seq stmts;
923 504 : gcond *cond_expr;
924 504 : tree exit_test;
925 504 : edge exit_e;
926 :
927 504 : gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
928 :
929 : /* Create header, latch and wire up the loop. */
930 504 : pred_bb = entry_edge->src;
931 504 : loop_header = split_edge (entry_edge);
932 504 : loop_latch = split_edge (single_succ_edge (loop_header));
933 504 : succ_bb = single_succ (loop_latch);
934 504 : make_edge (loop_header, succ_bb, 0);
935 504 : redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);
936 :
937 : /* Set immediate dominator information. */
938 504 : set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);
939 504 : set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);
940 504 : set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);
941 :
942 : /* Initialize a loop structure and put it in a loop hierarchy. */
943 504 : loop = alloc_loop ();
944 504 : loop->header = loop_header;
945 504 : loop->latch = loop_latch;
946 504 : add_loop (loop, outer);
947 :
948 : /* TODO: Fix counts. */
949 504 : scale_loop_frequencies (loop, profile_probability::even ());
950 :
951 : /* Update dominators. */
952 504 : update_dominators_in_loop (loop);
953 :
954 : /* Modify edge flags. */
955 504 : exit_e = single_exit (loop);
956 504 : exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
957 504 : single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
958 :
959 : /* Construct IV code in loop. */
960 504 : initial_value = force_gimple_operand (initial_value, &stmts, true, iv);
961 504 : if (stmts)
962 : {
963 17 : gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
964 17 : gsi_commit_edge_inserts ();
965 : }
966 :
967 504 : upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL);
968 504 : if (stmts)
969 : {
970 161 : gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
971 161 : gsi_commit_edge_inserts ();
972 : }
973 :
974 504 : gsi = gsi_last_bb (loop_header);
975 504 : create_iv (initial_value, PLUS_EXPR, stride, iv, loop, &gsi, false,
976 : iv_before, iv_after);
977 :
978 : /* Insert loop exit condition. */
979 504 : cond_expr = gimple_build_cond
980 504 : (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE);
981 :
982 504 : exit_test = gimple_cond_lhs (cond_expr);
983 504 : exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
984 : false, GSI_NEW_STMT);
985 504 : gimple_cond_set_lhs (cond_expr, exit_test);
986 504 : gsi = gsi_last_bb (exit_e->src);
987 504 : gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT);
988 :
989 504 : split_block_after_labels (loop_header);
990 :
991 504 : return loop;
992 : }
993 :
994 : /* Remove the latch edge of a LOOP and update loops to indicate that
995 : the LOOP was removed. After this function, original loop latch will
996 : have no successor, which caller is expected to fix somehow.
997 :
998 : If this may cause the information about irreducible regions to become
999 : invalid, IRRED_INVALIDATED is set to true.
1000 :
1001 : LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store
1002 : basic blocks that had non-trivial update on their loop_father.*/
1003 :
1004 : void
1005 146522 : unloop (class loop *loop, bool *irred_invalidated,
1006 : bitmap loop_closed_ssa_invalidated)
1007 : {
1008 146522 : basic_block *body;
1009 146522 : class loop *ploop;
1010 146522 : unsigned i, n;
1011 146522 : basic_block latch = loop->latch;
1012 146522 : bool dummy = false;
1013 :
1014 146522 : if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
1015 29 : *irred_invalidated = true;
1016 :
1017 : /* This is relatively straightforward. The dominators are unchanged, as
1018 : loop header dominates loop latch, so the only thing we have to care of
1019 : is the placement of loops and basic blocks inside the loop tree. We
1020 : move them all to the loop->outer, and then let fix_bb_placements do
1021 : its work. */
1022 :
1023 146522 : body = get_loop_body (loop);
1024 146522 : n = loop->num_nodes;
1025 584566 : for (i = 0; i < n; i++)
1026 438044 : if (body[i]->loop_father == loop)
1027 : {
1028 432486 : remove_bb_from_loops (body[i]);
1029 432486 : add_bb_to_loop (body[i], loop_outer (loop));
1030 : }
1031 146522 : free (body);
1032 :
1033 148119 : while (loop->inner)
1034 : {
1035 1597 : ploop = loop->inner;
1036 1597 : flow_loop_tree_node_remove (ploop);
1037 1597 : flow_loop_tree_node_add (loop_outer (loop), ploop);
1038 : }
1039 :
1040 : /* Remove the loop and free its data. */
1041 146522 : delete_loop (loop);
1042 :
1043 146522 : remove_edge (single_succ_edge (latch));
1044 :
1045 : /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
1046 : there is an irreducible region inside the cancelled loop, the flags will
1047 : be still correct. */
1048 146522 : fix_bb_placements (latch, &dummy, loop_closed_ssa_invalidated);
1049 146522 : }
1050 :
1051 : /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
1052 : condition stated in description of fix_loop_placement holds for them.
1053 : It is used in case when we removed some edges coming out of LOOP, which
1054 : may cause the right placement of LOOP inside loop tree to change.
1055 :
1056 : IRRED_INVALIDATED is set to true if a change in the loop structures might
1057 : invalidate the information about irreducible regions. */
1058 :
1059 : static void
1060 458664 : fix_loop_placements (class loop *loop, bool *irred_invalidated,
1061 : bitmap loop_closed_ssa_invalidated)
1062 : {
1063 458664 : if (!loop_outer (loop))
1064 251704 : return;
1065 :
1066 206960 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1067 206960 : unsigned i;
1068 206960 : edge e;
1069 :
1070 : /* We might need to only re-parent an outer loop, but as the constraint
1071 : is that we removed an exit from LOOP, we have a limit for what level
1072 : of outer loop we eventually have to re-parent to. */
1073 206960 : class loop *outermost = loop;
1074 1517649 : FOR_EACH_VEC_ELT (exits, i, e)
1075 1103729 : outermost = find_common_loop (outermost, e->dest->loop_father);
1076 :
1077 : class loop *outer;
1078 253076 : while (loop_outer (loop))
1079 : {
1080 253034 : outer = loop_outer (loop);
1081 253034 : if (fix_loop_placement (loop, irred_invalidated,
1082 : loop_closed_ssa_invalidated))
1083 : /* Changing the placement of a loop in the loop tree may alter the
1084 : validity of condition 2) of the description of fix_bb_placement
1085 : for its preheader, because the successor is the header and belongs
1086 : to the loop. So call fix_bb_placements to fix up the placement
1087 : of the preheader and (possibly) of its predecessors. */
1088 6 : fix_bb_placements (loop_preheader_edge (loop)->src,
1089 : irred_invalidated, loop_closed_ssa_invalidated);
1090 253034 : loop = outer;
1091 253034 : if (outer == outermost)
1092 : break;
1093 : }
1094 206960 : }
1095 :
1096 : /* Duplicate loop bounds and other information we store about
1097 : the loop into its duplicate. */
1098 :
1099 : void
1100 695995 : copy_loop_info (class loop *loop, class loop *target)
1101 : {
1102 695995 : gcc_checking_assert (!target->any_upper_bound && !target->any_estimate);
1103 695995 : target->any_upper_bound = loop->any_upper_bound;
1104 695995 : target->nb_iterations_upper_bound = loop->nb_iterations_upper_bound;
1105 695995 : target->any_likely_upper_bound = loop->any_likely_upper_bound;
1106 695995 : target->nb_iterations_likely_upper_bound
1107 695995 : = loop->nb_iterations_likely_upper_bound;
1108 695995 : target->any_estimate = loop->any_estimate;
1109 695995 : target->nb_iterations_estimate = loop->nb_iterations_estimate;
1110 695995 : target->estimate_state = loop->estimate_state;
1111 695995 : target->safelen = loop->safelen;
1112 695995 : target->simdlen = loop->simdlen;
1113 695995 : target->constraints = loop->constraints;
1114 695995 : target->can_be_parallel = loop->can_be_parallel;
1115 695995 : target->warned_aggressive_loop_optimizations
1116 695995 : |= loop->warned_aggressive_loop_optimizations;
1117 695995 : target->dont_vectorize = loop->dont_vectorize;
1118 695995 : target->force_vectorize = loop->force_vectorize;
1119 695995 : target->in_oacc_kernels_region = loop->in_oacc_kernels_region;
1120 695995 : target->finite_p = loop->finite_p;
1121 695995 : target->unroll = loop->unroll;
1122 695995 : target->owned_clique = loop->owned_clique;
1123 695995 : }
1124 :
1125 : /* Copies copy of LOOP as subloop of TARGET loop, placing newly
1126 : created loop into loops structure. If AFTER is non-null
1127 : the new loop is added at AFTER->next, otherwise in front of TARGETs
1128 : sibling list. */
1129 : class loop *
1130 41497 : duplicate_loop (class loop *loop, class loop *target, class loop *after)
1131 : {
1132 41497 : class loop *cloop;
1133 41497 : cloop = alloc_loop ();
1134 41497 : place_new_loop (cfun, cloop);
1135 :
1136 41497 : copy_loop_info (loop, cloop);
1137 :
1138 : /* Mark the new loop as copy of LOOP. */
1139 41497 : set_loop_copy (loop, cloop);
1140 :
1141 : /* Add it to target. */
1142 41497 : flow_loop_tree_node_add (target, cloop, after);
1143 :
1144 41497 : return cloop;
1145 : }
1146 :
1147 : /* Copies structure of subloops of LOOP into TARGET loop, placing
1148 : newly created loops into loop tree at the end of TARGETs sibling
1149 : list in the original order. */
1150 : void
1151 41497 : duplicate_subloops (class loop *loop, class loop *target)
1152 : {
1153 41497 : class loop *aloop, *cloop, *tail;
1154 :
1155 41497 : for (tail = target->inner; tail && tail->next; tail = tail->next)
1156 : ;
1157 42931 : for (aloop = loop->inner; aloop; aloop = aloop->next)
1158 : {
1159 1434 : cloop = duplicate_loop (aloop, target, tail);
1160 1434 : tail = cloop;
1161 1434 : gcc_assert(!tail->next);
1162 1434 : duplicate_subloops (aloop, cloop);
1163 : }
1164 41497 : }
1165 :
1166 : /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
1167 : into TARGET loop, placing newly created loops into loop tree adding
1168 : them to TARGETs sibling list at the end in order. */
1169 : static void
1170 576515 : copy_loops_to (class loop **copied_loops, int n, class loop *target)
1171 : {
1172 576515 : class loop *aloop, *tail;
1173 576515 : int i;
1174 :
1175 13122651 : for (tail = target->inner; tail && tail->next; tail = tail->next)
1176 : ;
1177 581146 : for (i = 0; i < n; i++)
1178 : {
1179 4631 : aloop = duplicate_loop (copied_loops[i], target, tail);
1180 4631 : tail = aloop;
1181 4631 : gcc_assert(!tail->next);
1182 4631 : duplicate_subloops (copied_loops[i], aloop);
1183 : }
1184 576515 : }
1185 :
1186 : /* Redirects edge E to basic block DEST. */
1187 : static void
1188 35766 : loop_redirect_edge (edge e, basic_block dest)
1189 : {
1190 0 : if (e->dest == dest)
1191 : return;
1192 :
1193 35766 : redirect_edge_and_branch_force (e, dest);
1194 : }
1195 :
1196 : /* Check whether LOOP's body can be duplicated. */
1197 : bool
1198 530176 : can_duplicate_loop_p (const class loop *loop)
1199 : {
1200 530176 : int ret;
1201 530176 : basic_block *bbs = get_loop_body (loop);
1202 :
1203 530176 : ret = can_copy_bbs_p (bbs, loop->num_nodes);
1204 530176 : free (bbs);
1205 :
1206 530176 : return ret;
1207 : }
1208 :
1209 : /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
1210 : loop structure and dominators (order of inner subloops is retained).
1211 : E's destination must be LOOP header for this to work, i.e. it must be entry
1212 : or latch edge of this loop; these are unique, as the loops must have
1213 : preheaders for this function to work correctly (in case E is latch, the
1214 : function unrolls the loop, if E is entry edge, it peels the loop). Store
1215 : edges created by copying ORIG edge from copies corresponding to set bits in
1216 : WONT_EXIT bitmap (bit 0 corresponds to original LOOP body, the other copies
1217 : are numbered in order given by control flow through them) into TO_REMOVE
1218 : array. Returns false if duplication is
1219 : impossible. */
1220 :
1221 : bool
1222 271542 : duplicate_loop_body_to_header_edge (class loop *loop, edge e,
1223 : unsigned int ndupl, sbitmap wont_exit,
1224 : edge orig, vec<edge> *to_remove, int flags)
1225 : {
1226 271542 : class loop *target, *aloop;
1227 271542 : class loop **orig_loops;
1228 271542 : unsigned n_orig_loops;
1229 271542 : basic_block header = loop->header, latch = loop->latch;
1230 271542 : basic_block *new_bbs, *bbs, *first_active;
1231 271542 : basic_block new_bb, bb, first_active_latch = NULL;
1232 271542 : edge ae, latch_edge;
1233 271542 : edge spec_edges[2], new_spec_edges[2];
1234 271542 : const int SE_LATCH = 0;
1235 271542 : const int SE_ORIG = 1;
1236 271542 : unsigned i, j, n;
1237 271542 : int is_latch = (latch == e->src);
1238 271542 : profile_probability *scale_step = NULL;
1239 271542 : profile_probability scale_main = profile_probability::always ();
1240 271542 : profile_probability scale_act = profile_probability::always ();
1241 271542 : profile_count after_exit_num = profile_count::zero (),
1242 271542 : after_exit_den = profile_count::zero ();
1243 271542 : bool scale_after_exit = false;
1244 271542 : int add_irreducible_flag;
1245 271542 : basic_block place_after;
1246 271542 : bitmap bbs_to_scale = NULL;
1247 271542 : bitmap_iterator bi;
1248 :
1249 271542 : gcc_assert (e->dest == loop->header);
1250 271542 : gcc_assert (ndupl > 0);
1251 :
1252 271542 : if (orig)
1253 : {
1254 : /* Orig must be edge out of the loop. */
1255 224551 : gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
1256 224551 : gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
1257 : }
1258 :
1259 271542 : n = loop->num_nodes;
1260 271542 : bbs = get_loop_body_in_dom_order (loop);
1261 271542 : gcc_assert (bbs[0] == loop->header);
1262 271542 : gcc_assert (bbs[n - 1] == loop->latch);
1263 :
1264 : /* Check whether duplication is possible. */
1265 271542 : if (!can_copy_bbs_p (bbs, loop->num_nodes))
1266 : {
1267 17 : free (bbs);
1268 17 : return false;
1269 : }
1270 271525 : new_bbs = XNEWVEC (basic_block, loop->num_nodes);
1271 :
1272 : /* In case we are doing loop peeling and the loop is in the middle of
1273 : irreducible region, the peeled copies will be inside it too. */
1274 271525 : add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
1275 271525 : gcc_assert (!is_latch || !add_irreducible_flag);
1276 :
1277 : /* Find edge from latch. */
1278 271525 : latch_edge = loop_latch_edge (loop);
1279 :
1280 271525 : if (flags & DLTHE_FLAG_UPDATE_FREQ)
1281 : {
1282 : /* Calculate coefficients by that we have to scale counts
1283 : of duplicated loop bodies. */
1284 235759 : profile_count count_in = header->count;
1285 235759 : profile_count count_le = latch_edge->count ();
1286 235759 : profile_count count_out_orig = orig ? orig->count () : count_in - count_le;
1287 235759 : profile_probability prob_pass_thru = count_le.probability_in (count_in);
1288 235759 : profile_count new_count_le = count_le + count_out_orig;
1289 :
1290 224545 : if (orig && orig->probability.initialized_p ()
1291 460304 : && !(orig->probability == profile_probability::always ()))
1292 : {
1293 : /* The blocks that are dominated by a removed exit edge ORIG have
1294 : frequencies scaled by this. */
1295 224410 : if (orig->count ().initialized_p ())
1296 : {
1297 224410 : after_exit_num = orig->src->count;
1298 224410 : after_exit_den = after_exit_num - orig->count ();
1299 224410 : scale_after_exit = true;
1300 : }
1301 224410 : bbs_to_scale = BITMAP_ALLOC (NULL);
1302 805478 : for (i = 0; i < n; i++)
1303 : {
1304 581068 : if (bbs[i] != orig->src
1305 581068 : && dominated_by_p (CDI_DOMINATORS, bbs[i], orig->src))
1306 272040 : bitmap_set_bit (bbs_to_scale, i);
1307 : }
1308 : /* Since we will scale up all basic blocks dominated by orig, exits
1309 : will become more likely; compensate for that. */
1310 224410 : if (after_exit_den.nonzero_p ())
1311 : {
1312 223762 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1313 967406 : for (edge ex : exits)
1314 296120 : if (ex != orig
1315 296120 : && dominated_by_p (CDI_DOMINATORS, ex->src, orig->src))
1316 44342 : new_count_le -= ex->count ().apply_scale (after_exit_num
1317 : - after_exit_den,
1318 22171 : after_exit_den);
1319 223762 : }
1320 : }
1321 235759 : profile_probability prob_pass_wont_exit =
1322 235759 : new_count_le.probability_in (count_in);
1323 : /* If profile count is 0, the probability will be uninitialized.
1324 : We can set probability to any initialized value to avoid
1325 : precision loss. If profile is sane, all counts will be 0 anyway. */
1326 235759 : if (!count_in.nonzero_p ())
1327 : {
1328 549 : prob_pass_thru
1329 549 : = profile_probability::always ().apply_scale (1, 2);
1330 549 : prob_pass_wont_exit
1331 549 : = profile_probability::always ().apply_scale (1, 2);
1332 : }
1333 :
1334 235759 : scale_step = XNEWVEC (profile_probability, ndupl);
1335 :
1336 776508 : for (i = 1; i <= ndupl; i++)
1337 1081498 : scale_step[i - 1] = bitmap_bit_p (wont_exit, i)
1338 540749 : ? prob_pass_wont_exit
1339 : : prob_pass_thru;
1340 :
1341 : /* Complete peeling is special as the probability of exit in last
1342 : copy becomes 1. */
1343 471432 : if (!count_in.nonzero_p ())
1344 : ;
1345 235210 : else if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
1346 : {
1347 114812 : profile_count wanted_count = e->count ();
1348 :
1349 114812 : gcc_assert (!is_latch);
1350 : /* First copy has count of incoming edge. Each subsequent
1351 : count should be reduced by prob_pass_wont_exit. Caller
1352 : should've managed the flags so all except for original loop
1353 : has won't exist set. */
1354 114812 : scale_act = wanted_count.probability_in (count_in);
1355 :
1356 : /* Now simulate the duplication adjustments and compute header
1357 : frequency of the last copy. */
1358 476831 : for (i = 0; i < ndupl; i++)
1359 362019 : wanted_count = wanted_count.apply_probability (scale_step [i]);
1360 114812 : scale_main = wanted_count.probability_in (count_in);
1361 : }
1362 : /* Here we insert loop bodies inside the loop itself (for loop unrolling).
1363 : First iteration will be original loop followed by duplicated bodies.
1364 : It is necessary to scale down the original so we get right overall
1365 : number of iterations. */
1366 120398 : else if (is_latch)
1367 : {
1368 52515 : profile_probability prob_pass_main = bitmap_bit_p (wont_exit, 0)
1369 52515 : ? prob_pass_wont_exit
1370 : : prob_pass_thru;
1371 52515 : if (!(flags & DLTHE_FLAG_FLAT_PROFILE))
1372 : {
1373 21959 : profile_probability p = prob_pass_main;
1374 21959 : profile_count scale_main_den = count_in;
1375 87170 : for (i = 0; i < ndupl; i++)
1376 : {
1377 65211 : scale_main_den += count_in.apply_probability (p);
1378 65211 : p = p * scale_step[i];
1379 : }
1380 : /* If original loop is executed COUNT_IN times, the unrolled
1381 : loop will account SCALE_MAIN_DEN times. */
1382 21959 : scale_main = count_in.probability_in (scale_main_den);
1383 : }
1384 : else
1385 : scale_main = profile_probability::always ();
1386 52515 : scale_act = scale_main * prob_pass_main;
1387 : }
1388 : else
1389 : {
1390 67883 : profile_count preheader_count = e->count ();
1391 138519 : for (i = 0; i < ndupl; i++)
1392 70636 : scale_main = scale_main * scale_step[i];
1393 67883 : scale_act = preheader_count.probability_in (count_in);
1394 : }
1395 : }
1396 :
1397 : /* Loop the new bbs will belong to. */
1398 271525 : target = e->src->loop_father;
1399 :
1400 : /* Original loops. */
1401 271525 : n_orig_loops = 0;
1402 275381 : for (aloop = loop->inner; aloop; aloop = aloop->next)
1403 3856 : n_orig_loops++;
1404 271525 : orig_loops = XNEWVEC (class loop *, n_orig_loops);
1405 275381 : for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
1406 3856 : orig_loops[i] = aloop;
1407 :
1408 271525 : set_loop_copy (loop, target);
1409 :
1410 271525 : first_active = XNEWVEC (basic_block, n);
1411 271525 : if (is_latch)
1412 : {
1413 52651 : memcpy (first_active, bbs, n * sizeof (basic_block));
1414 52651 : first_active_latch = latch;
1415 : }
1416 :
1417 271525 : spec_edges[SE_ORIG] = orig;
1418 271525 : spec_edges[SE_LATCH] = latch_edge;
1419 :
1420 271525 : place_after = e->src;
1421 :
1422 848040 : for (j = 0; j < ndupl; j++)
1423 : {
1424 : /* Copy loops. */
1425 576515 : copy_loops_to (orig_loops, n_orig_loops, target);
1426 :
1427 : /* Copy bbs. */
1428 576515 : copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
1429 : place_after, true);
1430 576515 : place_after = new_spec_edges[SE_LATCH]->src;
1431 :
1432 576515 : if (flags & DLTHE_RECORD_COPY_NUMBER)
1433 366532 : for (i = 0; i < n; i++)
1434 : {
1435 258760 : gcc_assert (!new_bbs[i]->aux);
1436 258760 : new_bbs[i]->aux = (void *)(size_t)(j + 1);
1437 : }
1438 :
1439 : /* Note whether the blocks and edges belong to an irreducible loop. */
1440 576515 : if (add_irreducible_flag)
1441 : {
1442 1046 : for (i = 0; i < n; i++)
1443 780 : new_bbs[i]->flags |= BB_DUPLICATED;
1444 1046 : for (i = 0; i < n; i++)
1445 : {
1446 780 : edge_iterator ei;
1447 780 : new_bb = new_bbs[i];
1448 780 : if (new_bb->loop_father == target)
1449 766 : new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1450 :
1451 2045 : FOR_EACH_EDGE (ae, ei, new_bb->succs)
1452 1265 : if ((ae->dest->flags & BB_DUPLICATED)
1453 804 : && (ae->src->loop_father == target
1454 21 : || ae->dest->loop_father == target))
1455 790 : ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1456 : }
1457 1046 : for (i = 0; i < n; i++)
1458 780 : new_bbs[i]->flags &= ~BB_DUPLICATED;
1459 : }
1460 :
1461 : /* Redirect the special edges. */
1462 576515 : if (is_latch)
1463 : {
1464 107385 : redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1465 107385 : redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1466 : loop->header);
1467 107385 : set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
1468 107385 : latch = loop->latch = new_bbs[n - 1];
1469 107385 : e = latch_edge = new_spec_edges[SE_LATCH];
1470 : }
1471 : else
1472 : {
1473 469130 : redirect_edge_and_branch_force (e, new_bbs[0]);
1474 469130 : redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1475 : loop->header);
1476 469130 : set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
1477 469130 : e = new_spec_edges[SE_LATCH];
1478 : }
1479 :
1480 : /* Record exit edge in this copy. */
1481 576515 : if (orig && bitmap_bit_p (wont_exit, j + 1))
1482 : {
1483 406166 : if (to_remove)
1484 406166 : to_remove->safe_push (new_spec_edges[SE_ORIG]);
1485 406166 : force_edge_cold (new_spec_edges[SE_ORIG], true);
1486 :
1487 : /* Scale the frequencies of the blocks dominated by the exit. */
1488 406166 : if (bbs_to_scale && scale_after_exit)
1489 : {
1490 928348 : EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1491 522510 : scale_bbs_frequencies_profile_count (new_bbs + i, 1, after_exit_num,
1492 : after_exit_den);
1493 : }
1494 : }
1495 :
1496 : /* Record the first copy in the control flow order if it is not
1497 : the original loop (i.e. in case of peeling). */
1498 576515 : if (!first_active_latch)
1499 : {
1500 218874 : memcpy (first_active, new_bbs, n * sizeof (basic_block));
1501 218874 : first_active_latch = new_bbs[n - 1];
1502 : }
1503 :
1504 : /* Set counts and frequencies. */
1505 576515 : if (flags & DLTHE_FLAG_UPDATE_FREQ)
1506 : {
1507 540749 : scale_bbs_frequencies (new_bbs, n, scale_act);
1508 540749 : scale_act = scale_act * scale_step[j];
1509 : }
1510 : }
1511 271525 : free (new_bbs);
1512 271525 : free (orig_loops);
1513 :
1514 : /* Record the exit edge in the original loop body, and update the frequencies. */
1515 496070 : if (orig && bitmap_bit_p (wont_exit, 0))
1516 : {
1517 51667 : if (to_remove)
1518 51667 : to_remove->safe_push (orig);
1519 51667 : force_edge_cold (orig, true);
1520 :
1521 : /* Scale the frequencies of the blocks dominated by the exit. */
1522 51667 : if (bbs_to_scale && scale_after_exit)
1523 : {
1524 103259 : EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1525 51640 : scale_bbs_frequencies_profile_count (bbs + i, 1, after_exit_num,
1526 : after_exit_den);
1527 : }
1528 : }
1529 :
1530 : /* Update the original loop. */
1531 271525 : if (!is_latch)
1532 218874 : set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1533 271525 : if (flags & DLTHE_FLAG_UPDATE_FREQ)
1534 : {
1535 235759 : scale_bbs_frequencies (bbs, n, scale_main);
1536 235759 : free (scale_step);
1537 : }
1538 :
1539 : /* Update dominators of outer blocks if affected. */
1540 1070887 : for (i = 0; i < n; i++)
1541 : {
1542 799362 : basic_block dominated, dom_bb;
1543 799362 : unsigned j;
1544 :
1545 799362 : bb = bbs[i];
1546 :
1547 799362 : auto_vec<basic_block> dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
1548 2877836 : FOR_EACH_VEC_ELT (dom_bbs, j, dominated)
1549 : {
1550 796430 : if (flow_bb_inside_loop_p (loop, dominated))
1551 580488 : continue;
1552 431884 : dom_bb = nearest_common_dominator (
1553 215942 : CDI_DOMINATORS, first_active[i], first_active_latch);
1554 215942 : set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1555 : }
1556 799362 : }
1557 271525 : free (first_active);
1558 :
1559 271525 : free (bbs);
1560 271525 : BITMAP_FREE (bbs_to_scale);
1561 :
1562 271525 : return true;
1563 : }
1564 :
1565 : /* A callback for make_forwarder block, to redirect all edges except for
1566 : OTHER(DATA) to the entry part. E is the edge for that we should decide
1567 : whether to redirect it. */
1568 :
1569 : bool
1570 89255 : mfb_keep_just (edge e, void *data)
1571 : {
1572 89255 : edge other = (edge)data;
1573 89255 : return e != other;
1574 : }
1575 :
1576 : /* True when a candidate preheader BLOCK has predecessors from LOOP. */
1577 :
1578 : static bool
1579 35 : has_preds_from_loop (basic_block block, class loop *loop)
1580 : {
1581 35 : edge e;
1582 35 : edge_iterator ei;
1583 :
1584 76 : FOR_EACH_EDGE (e, ei, block->preds)
1585 41 : if (e->src->loop_father == loop)
1586 : return true;
1587 : return false;
1588 : }
1589 :
1590 : /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1591 : CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1592 : entry; otherwise we also force preheader block to have only one successor.
1593 : When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
1594 : to be a fallthru predecessor to the loop header and to have only
1595 : predecessors from outside of the loop.
1596 : The function also updates dominators. */
1597 :
1598 : basic_block
1599 18848502 : create_preheader (class loop *loop, int flags)
1600 : {
1601 18848502 : edge e;
1602 18848502 : basic_block dummy;
1603 18848502 : int nentry = 0;
1604 18848502 : bool irred = false;
1605 18848502 : bool latch_edge_was_fallthru;
1606 18848502 : edge one_succ_pred = NULL, single_entry = NULL;
1607 18848502 : edge_iterator ei;
1608 :
1609 56578044 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1610 : {
1611 37729542 : if (e->src == loop->latch)
1612 18848502 : continue;
1613 18881040 : irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1614 18881040 : nentry++;
1615 18881040 : single_entry = e;
1616 53187285 : if (single_succ_p (e->src))
1617 15457743 : one_succ_pred = e;
1618 : }
1619 18848502 : gcc_assert (nentry);
1620 18848502 : if (nentry == 1)
1621 : {
1622 18824268 : bool need_forwarder_block = false;
1623 :
1624 : /* We do not allow entry block to be the loop preheader, since we
1625 : cannot emit code there. */
1626 18824268 : if (single_entry->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1627 : need_forwarder_block = true;
1628 : else
1629 : {
1630 : /* If we want simple preheaders, also force the preheader to have
1631 : just a single successor and a normal edge. */
1632 18821132 : if ((flags & CP_SIMPLE_PREHEADERS)
1633 18821132 : && ((single_entry->flags & EDGE_COMPLEX)
1634 18795982 : || !single_succ_p (single_entry->src)
1635 : /* We document LOOPS_HAVE_PREHEADERS as to forming a
1636 : natural place to move code outside of the loop, so it
1637 : should not end with a control instruction. */
1638 : /* ??? This, and below JUMP_P check needs to be a new
1639 : CFG hook. */
1640 15447316 : || (cfun->curr_properties & PROP_gimple
1641 29392314 : && !gsi_end_p (gsi_last_bb (single_entry->src))
1642 9596121 : && stmt_ends_bb_p (*gsi_last_bb (single_entry->src)))))
1643 : need_forwarder_block = true;
1644 : /* If we want fallthru preheaders, also create forwarder block when
1645 : preheader ends with a jump or has predecessors from loop. */
1646 15447316 : else if ((flags & CP_FALLTHRU_PREHEADERS)
1647 15447316 : && (JUMP_P (BB_END (single_entry->src))
1648 35 : || has_preds_from_loop (single_entry->src, loop)))
1649 : need_forwarder_block = true;
1650 : }
1651 : if (! need_forwarder_block)
1652 : return NULL;
1653 : }
1654 :
1655 3401198 : edge latch;
1656 3401198 : latch = loop_latch_edge (loop);
1657 3401198 : latch_edge_was_fallthru = (latch->flags & EDGE_FALLTHRU) != 0;
1658 3401198 : if (nentry == 1
1659 3376964 : && ((flags & CP_FALLTHRU_PREHEADERS) == 0
1660 22 : || (single_entry->flags & EDGE_CROSSING) == 0))
1661 3376964 : dummy = split_edge (single_entry);
1662 : else
1663 : {
1664 24234 : edge fallthru = make_forwarder_block (loop->header, mfb_keep_just, latch);
1665 24234 : dummy = fallthru->src;
1666 24234 : loop->header = fallthru->dest;
1667 : }
1668 :
1669 : /* Try to be clever in placing the newly created preheader. The idea is to
1670 : avoid breaking any "fallthruness" relationship between blocks.
1671 :
1672 : The preheader was created just before the header and all incoming edges
1673 : to the header were redirected to the preheader, except the latch edge.
1674 : So the only problematic case is when this latch edge was a fallthru
1675 : edge: it is not anymore after the preheader creation so we have broken
1676 : the fallthruness. We're therefore going to look for a better place. */
1677 3401198 : if (latch_edge_was_fallthru)
1678 : {
1679 1459168 : if (one_succ_pred)
1680 : e = one_succ_pred;
1681 : else
1682 1453837 : e = EDGE_PRED (dummy, 0);
1683 :
1684 1459168 : move_block_after (dummy, e->src);
1685 : }
1686 :
1687 3401198 : if (irred)
1688 : {
1689 4593 : dummy->flags |= BB_IRREDUCIBLE_LOOP;
1690 4593 : single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1691 : }
1692 :
1693 3401198 : if (dump_file)
1694 122 : fprintf (dump_file, "Created preheader block for loop %i\n",
1695 : loop->num);
1696 :
1697 3401198 : if (flags & CP_FALLTHRU_PREHEADERS)
1698 29 : gcc_assert ((single_succ_edge (dummy)->flags & EDGE_FALLTHRU)
1699 : && !JUMP_P (BB_END (dummy)));
1700 :
1701 : return dummy;
1702 : }
1703 :
1704 : /* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */
1705 :
1706 : void
1707 32124141 : create_preheaders (int flags)
1708 : {
1709 32124141 : if (!current_loops)
1710 : return;
1711 :
1712 115219718 : for (auto loop : loops_list (cfun, 0))
1713 18847295 : create_preheader (loop, flags);
1714 32124141 : loops_state_set (LOOPS_HAVE_PREHEADERS);
1715 : }
1716 :
1717 : /* Forces all loop latches to have only single successor. */
1718 :
1719 : void
1720 29555429 : force_single_succ_latches (void)
1721 : {
1722 29555429 : edge e;
1723 :
1724 106850046 : for (auto loop : loops_list (cfun, 0))
1725 : {
1726 18183759 : if (loop->latch != loop->header && single_succ_p (loop->latch))
1727 12842373 : continue;
1728 :
1729 5341386 : e = find_edge (loop->latch, loop->header);
1730 5341386 : gcc_checking_assert (e != NULL);
1731 :
1732 5341386 : split_edge (e);
1733 29555429 : }
1734 29555429 : loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES);
1735 29555429 : }
1736 :
1737 : /* This function is called from loop_version. It splits the entry edge
1738 : of the loop we want to version, adds the versioning condition, and
1739 : adjust the edges to the two versions of the loop appropriately.
1740 : e is an incoming edge. Returns the basic block containing the
1741 : condition.
1742 :
1743 : --- edge e ---- > [second_head]
1744 :
1745 : Split it and insert new conditional expression and adjust edges.
1746 :
1747 : --- edge e ---> [cond expr] ---> [first_head]
1748 : |
1749 : +---------> [second_head]
1750 :
1751 : THEN_PROB is the probability of then branch of the condition.
1752 : ELSE_PROB is the probability of else branch. Note that they may be both
1753 : REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED or
1754 : IFN_LOOP_DIST_ALIAS. */
1755 :
1756 : static basic_block
1757 35766 : lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head,
1758 : edge e, void *cond_expr,
1759 : profile_probability then_prob,
1760 : profile_probability else_prob)
1761 : {
1762 35766 : basic_block new_head = NULL;
1763 35766 : edge e1;
1764 :
1765 35766 : gcc_assert (e->dest == second_head);
1766 :
1767 : /* Split edge 'e'. This will create a new basic block, where we can
1768 : insert conditional expr. */
1769 35766 : new_head = split_edge (e);
1770 :
1771 35766 : lv_add_condition_to_bb (first_head, second_head, new_head,
1772 : cond_expr);
1773 :
1774 : /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */
1775 35766 : e = single_succ_edge (new_head);
1776 35766 : e1 = make_edge (new_head, first_head,
1777 35766 : current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0);
1778 35766 : e1->probability = then_prob;
1779 35766 : e->probability = else_prob;
1780 :
1781 35766 : set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1782 35766 : set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1783 :
1784 : /* Adjust loop header phi nodes. */
1785 35766 : lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1786 :
1787 35766 : return new_head;
1788 : }
1789 :
1790 : /* Main entry point for Loop Versioning transformation.
1791 :
1792 : This transformation given a condition and a loop, creates
1793 : -if (condition) { loop_copy1 } else { loop_copy2 },
1794 : where loop_copy1 is the loop transformed in one way, and loop_copy2
1795 : is the loop transformed in another way (or unchanged). COND_EXPR
1796 : may be a run time test for things that were not resolved by static
1797 : analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1798 :
1799 : If non-NULL, CONDITION_BB is set to the basic block containing the
1800 : condition.
1801 :
1802 : THEN_PROB is the probability of the then edge of the if. THEN_SCALE
1803 : is the ratio by that the frequencies in the original loop should
1804 : be scaled. ELSE_SCALE is the ratio by that the frequencies in the
1805 : new loop should be scaled.
1806 :
1807 : If PLACE_AFTER is true, we place the new loop after LOOP in the
1808 : instruction stream, otherwise it is placed before LOOP. */
1809 :
1810 : class loop *
1811 35776 : loop_version (class loop *loop,
1812 : void *cond_expr, basic_block *condition_bb,
1813 : profile_probability then_prob, profile_probability else_prob,
1814 : profile_probability then_scale, profile_probability else_scale,
1815 : bool place_after)
1816 : {
1817 35776 : basic_block first_head, second_head;
1818 35776 : edge entry, latch_edge;
1819 35776 : int irred_flag;
1820 35776 : class loop *nloop;
1821 35776 : basic_block cond_bb;
1822 :
1823 : /* Record entry and latch edges for the loop */
1824 35776 : entry = loop_preheader_edge (loop);
1825 35776 : irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1826 35776 : entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1827 :
1828 : /* Note down head of loop as first_head. */
1829 35776 : first_head = entry->dest;
1830 :
1831 : /* 1) Duplicate loop on the entry edge. */
1832 35776 : if (!cfg_hook_duplicate_loop_body_to_header_edge (loop, entry, 1, NULL, NULL,
1833 : NULL, 0))
1834 : {
1835 10 : entry->flags |= irred_flag;
1836 10 : return NULL;
1837 : }
1838 :
1839 : /* 2) loopify the duplicated new loop. */
1840 35766 : latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1841 35766 : nloop = alloc_loop ();
1842 35766 : class loop *outer = loop_outer (latch_edge->dest->loop_father);
1843 35766 : edge new_header_edge = single_pred_edge (get_bb_copy (loop->header));
1844 35766 : nloop->header = new_header_edge->dest;
1845 35766 : nloop->latch = latch_edge->src;
1846 35766 : loop_redirect_edge (latch_edge, nloop->header);
1847 :
1848 : /* Compute new loop. */
1849 35766 : add_loop (nloop, outer);
1850 35766 : copy_loop_info (loop, nloop);
1851 35766 : set_loop_copy (loop, nloop);
1852 :
1853 : /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1854 35766 : lv_flush_pending_stmts (latch_edge);
1855 :
1856 : /* After duplication entry edge now points to new loop head block.
1857 : Note down new head as second_head. */
1858 35766 : second_head = entry->dest;
1859 :
1860 : /* 3) Split loop entry edge and insert new block with cond expr. */
1861 35766 : cond_bb = lv_adjust_loop_entry_edge (first_head, second_head,
1862 : entry, cond_expr, then_prob, else_prob);
1863 35766 : if (condition_bb)
1864 31411 : *condition_bb = cond_bb;
1865 :
1866 35766 : if (!cond_bb)
1867 : {
1868 0 : entry->flags |= irred_flag;
1869 0 : return NULL;
1870 : }
1871 :
1872 : /* Add cond_bb to appropriate loop. */
1873 35766 : if (cond_bb->loop_father)
1874 35766 : remove_bb_from_loops (cond_bb);
1875 35766 : add_bb_to_loop (cond_bb, outer);
1876 :
1877 : /* 4) Scale the original loop and new loop frequency. */
1878 35766 : scale_loop_frequencies (loop, then_scale);
1879 35766 : scale_loop_frequencies (nloop, else_scale);
1880 35766 : update_dominators_in_loop (loop);
1881 35766 : update_dominators_in_loop (nloop);
1882 :
1883 : /* Adjust irreducible flag. */
1884 35766 : if (irred_flag)
1885 : {
1886 49 : cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
1887 49 : loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1888 49 : loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1889 49 : single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
1890 : }
1891 :
1892 35766 : if (place_after)
1893 : {
1894 33349 : basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
1895 33349 : unsigned i;
1896 :
1897 33349 : after = loop->latch;
1898 :
1899 197698 : for (i = 0; i < nloop->num_nodes; i++)
1900 : {
1901 164349 : move_block_after (bbs[i], after);
1902 164349 : after = bbs[i];
1903 : }
1904 33349 : free (bbs);
1905 : }
1906 :
1907 : /* At this point condition_bb is loop preheader with two successors,
1908 : first_head and second_head. Make sure that loop preheader has only
1909 : one successor. */
1910 35766 : split_edge (loop_preheader_edge (loop));
1911 35766 : split_edge (loop_preheader_edge (nloop));
1912 :
1913 35766 : return nloop;
1914 : }
|
