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