Daily bump.
[official-gcc.git] / gcc / cfgloopmanip.c
blob3e34aadd6911f781e558088b188f04074cccaf95
1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "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"
35 static void copy_loops_to (struct loop **, int,
36 struct loop *);
37 static void loop_redirect_edge (edge, basic_block);
38 static void remove_bbs (basic_block *, int);
39 static bool rpe_enum_p (const_basic_block, const void *);
40 static int find_path (edge, basic_block **);
41 static void fix_loop_placements (struct loop *, bool *);
42 static bool fix_bb_placement (basic_block);
43 static void fix_bb_placements (basic_block, bool *, bitmap);
45 /* Checks whether basic block BB is dominated by DATA. */
46 static bool
47 rpe_enum_p (const_basic_block bb, const void *data)
49 return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data);
52 /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
54 static void
55 remove_bbs (basic_block *bbs, int nbbs)
57 int i;
59 for (i = 0; i < nbbs; i++)
60 delete_basic_block (bbs[i]);
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. */
69 static int
70 find_path (edge e, basic_block **bbs)
72 gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
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);
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). */
87 static bool
88 fix_bb_placement (basic_block bb)
90 edge e;
91 edge_iterator ei;
92 struct loop *loop = current_loops->tree_root, *act;
94 FOR_EACH_EDGE (e, ei, bb->succs)
96 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
97 continue;
99 act = e->dest->loop_father;
100 if (act->header == e->dest)
101 act = loop_outer (act);
103 if (flow_loop_nested_p (loop, act))
104 loop = act;
107 if (loop == bb->loop_father)
108 return false;
110 remove_bb_from_loops (bb);
111 add_bb_to_loop (bb, loop);
113 return true;
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.
121 IRRED_INVALIDATED is set to true if a change in the loop structures might
122 invalidate the information about irreducible regions. */
124 static bool
125 fix_loop_placement (struct loop *loop, bool *irred_invalidated)
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;
133 FOR_EACH_VEC_ELT (exits, i, e)
135 act = find_common_loop (loop, e->dest->loop_father);
136 if (flow_loop_nested_p (father, act))
137 father = act;
140 if (father != loop_outer (loop))
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);
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)
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);
157 ret = true;
160 exits.release ();
161 return ret;
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.
173 If the changes may invalidate the information about irreducible regions,
174 IRRED_INVALIDATED is set to true.
176 If LOOP_CLOSED_SSA_INVLIDATED is non-zero then all basic blocks with
177 changed loop_father are collected there. */
179 static void
180 fix_bb_placements (basic_block from,
181 bool *irred_invalidated,
182 bitmap loop_closed_ssa_invalidated)
184 basic_block *queue, *qtop, *qbeg, *qend;
185 struct loop *base_loop, *target_loop;
186 edge e;
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. */
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;
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);
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;
215 while (qbeg != qend)
217 edge_iterator ei;
218 from = *qbeg;
219 qbeg++;
220 if (qbeg == qtop)
221 qbeg = queue;
222 bitmap_clear_bit (in_queue, from->index);
224 if (from->loop_father->header == from)
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)
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);
238 else
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);
248 FOR_EACH_EDGE (e, ei, from->succs)
250 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
251 *irred_invalidated = true;
254 /* Something has changed, insert predecessors into queue. */
255 FOR_EACH_EDGE (e, ei, from->preds)
257 basic_block pred = e->src;
258 struct loop *nca;
260 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
261 *irred_invalidated = true;
263 if (bitmap_bit_p (in_queue, pred->index))
264 continue;
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))
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;
283 if (bitmap_bit_p (in_queue, pred->index))
284 continue;
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);
294 free (queue);
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). */
300 bool
301 remove_path (edge e, bool *irred_invalidated,
302 bitmap loop_closed_ssa_invalidated)
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;
312 if (! irred_invalidated)
313 irred_invalidated = &local_irred_invalidated;
315 if (!can_remove_branch_p (e))
316 return false;
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;
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));
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)
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);
344 /* Identify the path. */
345 nrem = find_path (e, &rem_bbs);
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);
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)
361 *irred_invalidated = true;
362 break;
365 for (i = 0; i < nrem; i++)
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))
372 bitmap_set_bit (seen, ae->dest->index);
373 bord_bbs[n_bord_bbs++] = ae->dest;
375 if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
376 *irred_invalidated = true;
380 /* Remove the path. */
381 from = e->src;
382 remove_branch (e);
383 dom_bbs.create (0);
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);
390 remove_bbs (rem_bbs, nrem);
391 free (rem_bbs);
393 /* Find blocks whose dominators may be affected. */
394 bitmap_clear (seen);
395 for (i = 0; i < n_bord_bbs; i++)
397 basic_block ldom;
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);
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);
411 /* Recount dominators. */
412 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);
413 dom_bbs.release ();
414 free (bord_bbs);
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);
421 if (local_irred_invalidated
422 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
423 mark_irreducible_loops ();
425 return true;
428 /* Creates place for a new LOOP in loops structure of FN. */
430 void
431 place_new_loop (struct function *fn, struct loop *loop)
433 loop->num = number_of_loops (fn);
434 vec_safe_push (loops_for_fn (fn)->larray, loop);
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. */
441 void
442 add_loop (struct loop *loop, struct loop *outer)
444 basic_block *bbs;
445 int i, n;
446 struct loop *subloop;
447 edge e;
448 edge_iterator ei;
450 /* Add it to loop structure. */
451 place_new_loop (cfun, loop);
452 flow_loop_tree_node_add (outer, loop);
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));
458 for (i = 0; i < n; i++)
460 if (bbs[i]->loop_father == outer)
462 remove_bb_from_loops (bbs[i]);
463 add_bb_to_loop (bbs[i], loop);
464 continue;
467 loop->num_nodes++;
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])
474 flow_loop_tree_node_remove (subloop);
475 flow_loop_tree_node_add (loop, subloop);
479 /* Update the information about loop exit edges. */
480 for (i = 0; i < n; i++)
482 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
484 rescan_loop_exit (e, false, false);
488 free (bbs);
491 /* Multiply all frequencies in LOOP by NUM/DEN. */
493 void
494 scale_loop_frequencies (struct loop *loop, int num, int den)
496 basic_block *bbs;
498 bbs = get_loop_body (loop);
499 scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
500 free (bbs);
503 /* Multiply all frequencies in LOOP by SCALE/REG_BR_PROB_BASE.
504 If ITERATION_BOUND is non-zero, scale even further if loop is predicted
505 to iterate too many times. */
507 void
508 scale_loop_profile (struct loop *loop, int scale, gcov_type iteration_bound)
510 gcov_type iterations = expected_loop_iterations_unbounded (loop);
511 edge e;
512 edge_iterator ei;
514 if (dump_file && (dump_flags & TDF_DETAILS))
515 fprintf (dump_file, ";; Scaling loop %i with scale %f, "
516 "bounding iterations to %i from guessed %i\n",
517 loop->num, (double)scale / REG_BR_PROB_BASE,
518 (int)iteration_bound, (int)iterations);
520 /* See if loop is predicted to iterate too many times. */
521 if (iteration_bound && iterations > 0
522 && apply_probability (iterations, scale) > iteration_bound)
524 /* Fixing loop profile for different trip count is not trivial; the exit
525 probabilities has to be updated to match and frequencies propagated down
526 to the loop body.
528 We fully update only the simple case of loop with single exit that is
529 either from the latch or BB just before latch and leads from BB with
530 simple conditional jump. This is OK for use in vectorizer. */
531 e = single_exit (loop);
532 if (e)
534 edge other_e;
535 int freq_delta;
536 gcov_type count_delta;
538 FOR_EACH_EDGE (other_e, ei, e->src->succs)
539 if (!(other_e->flags & (EDGE_ABNORMAL | EDGE_FAKE))
540 && e != other_e)
541 break;
543 /* Probability of exit must be 1/iterations. */
544 freq_delta = EDGE_FREQUENCY (e);
545 e->probability = REG_BR_PROB_BASE / iteration_bound;
546 other_e->probability = inverse_probability (e->probability);
547 freq_delta -= EDGE_FREQUENCY (e);
549 /* Adjust counts accordingly. */
550 count_delta = e->count;
551 e->count = apply_probability (e->src->count, e->probability);
552 other_e->count = apply_probability (e->src->count, other_e->probability);
553 count_delta -= e->count;
555 /* If latch exists, change its frequency and count, since we changed
556 probability of exit. Theoretically we should update everything from
557 source of exit edge to latch, but for vectorizer this is enough. */
558 if (loop->latch
559 && loop->latch != e->src)
561 loop->latch->frequency += freq_delta;
562 if (loop->latch->frequency < 0)
563 loop->latch->frequency = 0;
564 loop->latch->count += count_delta;
565 if (loop->latch->count < 0)
566 loop->latch->count = 0;
570 /* Roughly speaking we want to reduce the loop body profile by the
571 difference of loop iterations. We however can do better if
572 we look at the actual profile, if it is available. */
573 scale = RDIV (iteration_bound * scale, iterations);
574 if (loop->header->count)
576 gcov_type count_in = 0;
578 FOR_EACH_EDGE (e, ei, loop->header->preds)
579 if (e->src != loop->latch)
580 count_in += e->count;
582 if (count_in != 0)
583 scale = GCOV_COMPUTE_SCALE (count_in * iteration_bound,
584 loop->header->count);
586 else if (loop->header->frequency)
588 int freq_in = 0;
590 FOR_EACH_EDGE (e, ei, loop->header->preds)
591 if (e->src != loop->latch)
592 freq_in += EDGE_FREQUENCY (e);
594 if (freq_in != 0)
595 scale = GCOV_COMPUTE_SCALE (freq_in * iteration_bound,
596 loop->header->frequency);
598 if (!scale)
599 scale = 1;
602 if (scale == REG_BR_PROB_BASE)
603 return;
605 /* Scale the actual probabilities. */
606 scale_loop_frequencies (loop, scale, REG_BR_PROB_BASE);
607 if (dump_file && (dump_flags & TDF_DETAILS))
608 fprintf (dump_file, ";; guessed iterations are now %i\n",
609 (int)expected_loop_iterations_unbounded (loop));
612 /* Recompute dominance information for basic blocks outside LOOP. */
614 static void
615 update_dominators_in_loop (struct loop *loop)
617 vec<basic_block> dom_bbs = vNULL;
618 basic_block *body;
619 unsigned i;
621 auto_sbitmap seen (last_basic_block_for_fn (cfun));
622 bitmap_clear (seen);
623 body = get_loop_body (loop);
625 for (i = 0; i < loop->num_nodes; i++)
626 bitmap_set_bit (seen, body[i]->index);
628 for (i = 0; i < loop->num_nodes; i++)
630 basic_block ldom;
632 for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
633 ldom;
634 ldom = next_dom_son (CDI_DOMINATORS, ldom))
635 if (!bitmap_bit_p (seen, ldom->index))
637 bitmap_set_bit (seen, ldom->index);
638 dom_bbs.safe_push (ldom);
642 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
643 free (body);
644 dom_bbs.release ();
647 /* Creates an if region as shown above. CONDITION is used to create
648 the test for the if.
651 | ------------- -------------
652 | | pred_bb | | pred_bb |
653 | ------------- -------------
654 | | |
655 | | | ENTRY_EDGE
656 | | ENTRY_EDGE V
657 | | ====> -------------
658 | | | cond_bb |
659 | | | CONDITION |
660 | | -------------
661 | V / \
662 | ------------- e_false / \ e_true
663 | | succ_bb | V V
664 | ------------- ----------- -----------
665 | | false_bb | | true_bb |
666 | ----------- -----------
667 | \ /
668 | \ /
669 | V V
670 | -------------
671 | | join_bb |
672 | -------------
673 | | exit_edge (result)
675 | -----------
676 | | succ_bb |
677 | -----------
681 edge
682 create_empty_if_region_on_edge (edge entry_edge, tree condition)
685 basic_block cond_bb, true_bb, false_bb, join_bb;
686 edge e_true, e_false, exit_edge;
687 gcond *cond_stmt;
688 tree simple_cond;
689 gimple_stmt_iterator gsi;
691 cond_bb = split_edge (entry_edge);
693 /* Insert condition in cond_bb. */
694 gsi = gsi_last_bb (cond_bb);
695 simple_cond =
696 force_gimple_operand_gsi (&gsi, condition, true, NULL,
697 false, GSI_NEW_STMT);
698 cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);
699 gsi = gsi_last_bb (cond_bb);
700 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
702 join_bb = split_edge (single_succ_edge (cond_bb));
704 e_true = single_succ_edge (cond_bb);
705 true_bb = split_edge (e_true);
707 e_false = make_edge (cond_bb, join_bb, 0);
708 false_bb = split_edge (e_false);
710 e_true->flags &= ~EDGE_FALLTHRU;
711 e_true->flags |= EDGE_TRUE_VALUE;
712 e_false->flags &= ~EDGE_FALLTHRU;
713 e_false->flags |= EDGE_FALSE_VALUE;
715 set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);
716 set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);
717 set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);
718 set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
720 exit_edge = single_succ_edge (join_bb);
722 if (single_pred_p (exit_edge->dest))
723 set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);
725 return exit_edge;
728 /* create_empty_loop_on_edge
730 | - pred_bb - ------ pred_bb ------
731 | | | | iv0 = initial_value |
732 | -----|----- ---------|-----------
733 | | ______ | entry_edge
734 | | entry_edge / | |
735 | | ====> | -V---V- loop_header -------------
736 | V | | iv_before = phi (iv0, iv_after) |
737 | - succ_bb - | ---|-----------------------------
738 | | | | |
739 | ----------- | ---V--- loop_body ---------------
740 | | | iv_after = iv_before + stride |
741 | | | if (iv_before < upper_bound) |
742 | | ---|--------------\--------------
743 | | | \ exit_e
744 | | V \
745 | | - loop_latch - V- succ_bb -
746 | | | | | |
747 | | /------------- -----------
748 | \ ___ /
750 Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
751 that is used before the increment of IV. IV_BEFORE should be used for
752 adding code to the body that uses the IV. OUTER is the outer loop in
753 which the new loop should be inserted.
755 Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
756 inserted on the loop entry edge. This implies that this function
757 should be used only when the UPPER_BOUND expression is a loop
758 invariant. */
760 struct loop *
761 create_empty_loop_on_edge (edge entry_edge,
762 tree initial_value,
763 tree stride, tree upper_bound,
764 tree iv,
765 tree *iv_before,
766 tree *iv_after,
767 struct loop *outer)
769 basic_block loop_header, loop_latch, succ_bb, pred_bb;
770 struct loop *loop;
771 gimple_stmt_iterator gsi;
772 gimple_seq stmts;
773 gcond *cond_expr;
774 tree exit_test;
775 edge exit_e;
776 int prob;
778 gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
780 /* Create header, latch and wire up the loop. */
781 pred_bb = entry_edge->src;
782 loop_header = split_edge (entry_edge);
783 loop_latch = split_edge (single_succ_edge (loop_header));
784 succ_bb = single_succ (loop_latch);
785 make_edge (loop_header, succ_bb, 0);
786 redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);
788 /* Set immediate dominator information. */
789 set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);
790 set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);
791 set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);
793 /* Initialize a loop structure and put it in a loop hierarchy. */
794 loop = alloc_loop ();
795 loop->header = loop_header;
796 loop->latch = loop_latch;
797 add_loop (loop, outer);
799 /* TODO: Fix frequencies and counts. */
800 prob = REG_BR_PROB_BASE / 2;
802 scale_loop_frequencies (loop, REG_BR_PROB_BASE - prob, REG_BR_PROB_BASE);
804 /* Update dominators. */
805 update_dominators_in_loop (loop);
807 /* Modify edge flags. */
808 exit_e = single_exit (loop);
809 exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
810 single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
812 /* Construct IV code in loop. */
813 initial_value = force_gimple_operand (initial_value, &stmts, true, iv);
814 if (stmts)
816 gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
817 gsi_commit_edge_inserts ();
820 upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL);
821 if (stmts)
823 gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
824 gsi_commit_edge_inserts ();
827 gsi = gsi_last_bb (loop_header);
828 create_iv (initial_value, stride, iv, loop, &gsi, false,
829 iv_before, iv_after);
831 /* Insert loop exit condition. */
832 cond_expr = gimple_build_cond
833 (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE);
835 exit_test = gimple_cond_lhs (cond_expr);
836 exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
837 false, GSI_NEW_STMT);
838 gimple_cond_set_lhs (cond_expr, exit_test);
839 gsi = gsi_last_bb (exit_e->src);
840 gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT);
842 split_block_after_labels (loop_header);
844 return loop;
847 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
848 latch to header and update loop tree and dominators
849 accordingly. Everything between them plus LATCH_EDGE destination must
850 be dominated by HEADER_EDGE destination, and back-reachable from
851 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
852 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
853 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
854 Returns the newly created loop. Frequencies and counts in the new loop
855 are scaled by FALSE_SCALE and in the old one by TRUE_SCALE. */
857 struct loop *
858 loopify (edge latch_edge, edge header_edge,
859 basic_block switch_bb, edge true_edge, edge false_edge,
860 bool redirect_all_edges, unsigned true_scale, unsigned false_scale)
862 basic_block succ_bb = latch_edge->dest;
863 basic_block pred_bb = header_edge->src;
864 struct loop *loop = alloc_loop ();
865 struct loop *outer = loop_outer (succ_bb->loop_father);
866 int freq;
867 gcov_type cnt;
868 edge e;
869 edge_iterator ei;
871 loop->header = header_edge->dest;
872 loop->latch = latch_edge->src;
874 freq = EDGE_FREQUENCY (header_edge);
875 cnt = header_edge->count;
877 /* Redirect edges. */
878 loop_redirect_edge (latch_edge, loop->header);
879 loop_redirect_edge (true_edge, succ_bb);
881 /* During loop versioning, one of the switch_bb edge is already properly
882 set. Do not redirect it again unless redirect_all_edges is true. */
883 if (redirect_all_edges)
885 loop_redirect_edge (header_edge, switch_bb);
886 loop_redirect_edge (false_edge, loop->header);
888 /* Update dominators. */
889 set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
890 set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
893 set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
895 /* Compute new loop. */
896 add_loop (loop, outer);
898 /* Add switch_bb to appropriate loop. */
899 if (switch_bb->loop_father)
900 remove_bb_from_loops (switch_bb);
901 add_bb_to_loop (switch_bb, outer);
903 /* Fix frequencies. */
904 if (redirect_all_edges)
906 switch_bb->frequency = freq;
907 switch_bb->count = cnt;
908 FOR_EACH_EDGE (e, ei, switch_bb->succs)
910 e->count = apply_probability (switch_bb->count, e->probability);
913 scale_loop_frequencies (loop, false_scale, REG_BR_PROB_BASE);
914 scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE);
915 update_dominators_in_loop (loop);
917 return loop;
920 /* Remove the latch edge of a LOOP and update loops to indicate that
921 the LOOP was removed. After this function, original loop latch will
922 have no successor, which caller is expected to fix somehow.
924 If this may cause the information about irreducible regions to become
925 invalid, IRRED_INVALIDATED is set to true.
927 LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store
928 basic blocks that had non-trivial update on their loop_father.*/
930 void
931 unloop (struct loop *loop, bool *irred_invalidated,
932 bitmap loop_closed_ssa_invalidated)
934 basic_block *body;
935 struct loop *ploop;
936 unsigned i, n;
937 basic_block latch = loop->latch;
938 bool dummy = false;
940 if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
941 *irred_invalidated = true;
943 /* This is relatively straightforward. The dominators are unchanged, as
944 loop header dominates loop latch, so the only thing we have to care of
945 is the placement of loops and basic blocks inside the loop tree. We
946 move them all to the loop->outer, and then let fix_bb_placements do
947 its work. */
949 body = get_loop_body (loop);
950 n = loop->num_nodes;
951 for (i = 0; i < n; i++)
952 if (body[i]->loop_father == loop)
954 remove_bb_from_loops (body[i]);
955 add_bb_to_loop (body[i], loop_outer (loop));
957 free (body);
959 while (loop->inner)
961 ploop = loop->inner;
962 flow_loop_tree_node_remove (ploop);
963 flow_loop_tree_node_add (loop_outer (loop), ploop);
966 /* Remove the loop and free its data. */
967 delete_loop (loop);
969 remove_edge (single_succ_edge (latch));
971 /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
972 there is an irreducible region inside the cancelled loop, the flags will
973 be still correct. */
974 fix_bb_placements (latch, &dummy, loop_closed_ssa_invalidated);
977 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
978 condition stated in description of fix_loop_placement holds for them.
979 It is used in case when we removed some edges coming out of LOOP, which
980 may cause the right placement of LOOP inside loop tree to change.
982 IRRED_INVALIDATED is set to true if a change in the loop structures might
983 invalidate the information about irreducible regions. */
985 static void
986 fix_loop_placements (struct loop *loop, bool *irred_invalidated)
988 struct loop *outer;
990 while (loop_outer (loop))
992 outer = loop_outer (loop);
993 if (!fix_loop_placement (loop, irred_invalidated))
994 break;
996 /* Changing the placement of a loop in the loop tree may alter the
997 validity of condition 2) of the description of fix_bb_placement
998 for its preheader, because the successor is the header and belongs
999 to the loop. So call fix_bb_placements to fix up the placement
1000 of the preheader and (possibly) of its predecessors. */
1001 fix_bb_placements (loop_preheader_edge (loop)->src,
1002 irred_invalidated, NULL);
1003 loop = outer;
1007 /* Duplicate loop bounds and other information we store about
1008 the loop into its duplicate. */
1010 void
1011 copy_loop_info (struct loop *loop, struct loop *target)
1013 gcc_checking_assert (!target->any_upper_bound && !target->any_estimate);
1014 target->any_upper_bound = loop->any_upper_bound;
1015 target->nb_iterations_upper_bound = loop->nb_iterations_upper_bound;
1016 target->any_likely_upper_bound = loop->any_likely_upper_bound;
1017 target->nb_iterations_likely_upper_bound
1018 = loop->nb_iterations_likely_upper_bound;
1019 target->any_estimate = loop->any_estimate;
1020 target->nb_iterations_estimate = loop->nb_iterations_estimate;
1021 target->estimate_state = loop->estimate_state;
1022 target->constraints = loop->constraints;
1023 target->warned_aggressive_loop_optimizations
1024 |= loop->warned_aggressive_loop_optimizations;
1025 target->in_oacc_kernels_region = loop->in_oacc_kernels_region;
1028 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
1029 created loop into loops structure. */
1030 struct loop *
1031 duplicate_loop (struct loop *loop, struct loop *target)
1033 struct loop *cloop;
1034 cloop = alloc_loop ();
1035 place_new_loop (cfun, cloop);
1037 copy_loop_info (loop, cloop);
1039 /* Mark the new loop as copy of LOOP. */
1040 set_loop_copy (loop, cloop);
1042 /* Add it to target. */
1043 flow_loop_tree_node_add (target, cloop);
1045 return cloop;
1048 /* Copies structure of subloops of LOOP into TARGET loop, placing
1049 newly created loops into loop tree. */
1050 void
1051 duplicate_subloops (struct loop *loop, struct loop *target)
1053 struct loop *aloop, *cloop;
1055 for (aloop = loop->inner; aloop; aloop = aloop->next)
1057 cloop = duplicate_loop (aloop, target);
1058 duplicate_subloops (aloop, cloop);
1062 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
1063 into TARGET loop, placing newly created loops into loop tree. */
1064 static void
1065 copy_loops_to (struct loop **copied_loops, int n, struct loop *target)
1067 struct loop *aloop;
1068 int i;
1070 for (i = 0; i < n; i++)
1072 aloop = duplicate_loop (copied_loops[i], target);
1073 duplicate_subloops (copied_loops[i], aloop);
1077 /* Redirects edge E to basic block DEST. */
1078 static void
1079 loop_redirect_edge (edge e, basic_block dest)
1081 if (e->dest == dest)
1082 return;
1084 redirect_edge_and_branch_force (e, dest);
1087 /* Check whether LOOP's body can be duplicated. */
1088 bool
1089 can_duplicate_loop_p (const struct loop *loop)
1091 int ret;
1092 basic_block *bbs = get_loop_body (loop);
1094 ret = can_copy_bbs_p (bbs, loop->num_nodes);
1095 free (bbs);
1097 return ret;
1100 /* Sets probability and count of edge E to zero. The probability and count
1101 is redistributed evenly to the remaining edges coming from E->src. */
1103 static void
1104 set_zero_probability (edge e)
1106 basic_block bb = e->src;
1107 edge_iterator ei;
1108 edge ae, last = NULL;
1109 unsigned n = EDGE_COUNT (bb->succs);
1110 gcov_type cnt = e->count, cnt1;
1111 unsigned prob = e->probability, prob1;
1113 gcc_assert (n > 1);
1114 cnt1 = cnt / (n - 1);
1115 prob1 = prob / (n - 1);
1117 FOR_EACH_EDGE (ae, ei, bb->succs)
1119 if (ae == e)
1120 continue;
1122 ae->probability += prob1;
1123 ae->count += cnt1;
1124 last = ae;
1127 /* Move the rest to one of the edges. */
1128 last->probability += prob % (n - 1);
1129 last->count += cnt % (n - 1);
1131 e->probability = 0;
1132 e->count = 0;
1135 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
1136 loop structure and dominators. E's destination must be LOOP header for
1137 this to work, i.e. it must be entry or latch edge of this loop; these are
1138 unique, as the loops must have preheaders for this function to work
1139 correctly (in case E is latch, the function unrolls the loop, if E is entry
1140 edge, it peels the loop). Store edges created by copying ORIG edge from
1141 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
1142 original LOOP body, the other copies are numbered in order given by control
1143 flow through them) into TO_REMOVE array. Returns false if duplication is
1144 impossible. */
1146 bool
1147 duplicate_loop_to_header_edge (struct loop *loop, edge e,
1148 unsigned int ndupl, sbitmap wont_exit,
1149 edge orig, vec<edge> *to_remove,
1150 int flags)
1152 struct loop *target, *aloop;
1153 struct loop **orig_loops;
1154 unsigned n_orig_loops;
1155 basic_block header = loop->header, latch = loop->latch;
1156 basic_block *new_bbs, *bbs, *first_active;
1157 basic_block new_bb, bb, first_active_latch = NULL;
1158 edge ae, latch_edge;
1159 edge spec_edges[2], new_spec_edges[2];
1160 #define SE_LATCH 0
1161 #define SE_ORIG 1
1162 unsigned i, j, n;
1163 int is_latch = (latch == e->src);
1164 int scale_act = 0, *scale_step = NULL, scale_main = 0;
1165 int scale_after_exit = 0;
1166 int p, freq_in, freq_le, freq_out_orig;
1167 int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
1168 int add_irreducible_flag;
1169 basic_block place_after;
1170 bitmap bbs_to_scale = NULL;
1171 bitmap_iterator bi;
1173 gcc_assert (e->dest == loop->header);
1174 gcc_assert (ndupl > 0);
1176 if (orig)
1178 /* Orig must be edge out of the loop. */
1179 gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
1180 gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
1183 n = loop->num_nodes;
1184 bbs = get_loop_body_in_dom_order (loop);
1185 gcc_assert (bbs[0] == loop->header);
1186 gcc_assert (bbs[n - 1] == loop->latch);
1188 /* Check whether duplication is possible. */
1189 if (!can_copy_bbs_p (bbs, loop->num_nodes))
1191 free (bbs);
1192 return false;
1194 new_bbs = XNEWVEC (basic_block, loop->num_nodes);
1196 /* In case we are doing loop peeling and the loop is in the middle of
1197 irreducible region, the peeled copies will be inside it too. */
1198 add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
1199 gcc_assert (!is_latch || !add_irreducible_flag);
1201 /* Find edge from latch. */
1202 latch_edge = loop_latch_edge (loop);
1204 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1206 /* Calculate coefficients by that we have to scale frequencies
1207 of duplicated loop bodies. */
1208 freq_in = header->frequency;
1209 freq_le = EDGE_FREQUENCY (latch_edge);
1210 if (freq_in == 0)
1211 freq_in = 1;
1212 if (freq_in < freq_le)
1213 freq_in = freq_le;
1214 freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
1215 if (freq_out_orig > freq_in - freq_le)
1216 freq_out_orig = freq_in - freq_le;
1217 prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
1218 prob_pass_wont_exit =
1219 RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
1221 if (orig
1222 && REG_BR_PROB_BASE - orig->probability != 0)
1224 /* The blocks that are dominated by a removed exit edge ORIG have
1225 frequencies scaled by this. */
1226 scale_after_exit
1227 = GCOV_COMPUTE_SCALE (REG_BR_PROB_BASE,
1228 REG_BR_PROB_BASE - orig->probability);
1229 bbs_to_scale = BITMAP_ALLOC (NULL);
1230 for (i = 0; i < n; i++)
1232 if (bbs[i] != orig->src
1233 && dominated_by_p (CDI_DOMINATORS, bbs[i], orig->src))
1234 bitmap_set_bit (bbs_to_scale, i);
1238 scale_step = XNEWVEC (int, ndupl);
1240 for (i = 1; i <= ndupl; i++)
1241 scale_step[i - 1] = bitmap_bit_p (wont_exit, i)
1242 ? prob_pass_wont_exit
1243 : prob_pass_thru;
1245 /* Complete peeling is special as the probability of exit in last
1246 copy becomes 1. */
1247 if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
1249 int wanted_freq = EDGE_FREQUENCY (e);
1251 if (wanted_freq > freq_in)
1252 wanted_freq = freq_in;
1254 gcc_assert (!is_latch);
1255 /* First copy has frequency of incoming edge. Each subsequent
1256 frequency should be reduced by prob_pass_wont_exit. Caller
1257 should've managed the flags so all except for original loop
1258 has won't exist set. */
1259 scale_act = GCOV_COMPUTE_SCALE (wanted_freq, freq_in);
1260 /* Now simulate the duplication adjustments and compute header
1261 frequency of the last copy. */
1262 for (i = 0; i < ndupl; i++)
1263 wanted_freq = combine_probabilities (wanted_freq, scale_step[i]);
1264 scale_main = GCOV_COMPUTE_SCALE (wanted_freq, freq_in);
1266 else if (is_latch)
1268 prob_pass_main = bitmap_bit_p (wont_exit, 0)
1269 ? prob_pass_wont_exit
1270 : prob_pass_thru;
1271 p = prob_pass_main;
1272 scale_main = REG_BR_PROB_BASE;
1273 for (i = 0; i < ndupl; i++)
1275 scale_main += p;
1276 p = combine_probabilities (p, scale_step[i]);
1278 scale_main = GCOV_COMPUTE_SCALE (REG_BR_PROB_BASE, scale_main);
1279 scale_act = combine_probabilities (scale_main, prob_pass_main);
1281 else
1283 int preheader_freq = EDGE_FREQUENCY (e);
1284 scale_main = REG_BR_PROB_BASE;
1285 for (i = 0; i < ndupl; i++)
1286 scale_main = combine_probabilities (scale_main, scale_step[i]);
1287 if (preheader_freq > freq_in)
1288 preheader_freq = freq_in;
1289 scale_act = GCOV_COMPUTE_SCALE (preheader_freq, freq_in);
1291 for (i = 0; i < ndupl; i++)
1292 gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
1293 gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
1294 && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE);
1297 /* Loop the new bbs will belong to. */
1298 target = e->src->loop_father;
1300 /* Original loops. */
1301 n_orig_loops = 0;
1302 for (aloop = loop->inner; aloop; aloop = aloop->next)
1303 n_orig_loops++;
1304 orig_loops = XNEWVEC (struct loop *, n_orig_loops);
1305 for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
1306 orig_loops[i] = aloop;
1308 set_loop_copy (loop, target);
1310 first_active = XNEWVEC (basic_block, n);
1311 if (is_latch)
1313 memcpy (first_active, bbs, n * sizeof (basic_block));
1314 first_active_latch = latch;
1317 spec_edges[SE_ORIG] = orig;
1318 spec_edges[SE_LATCH] = latch_edge;
1320 place_after = e->src;
1321 for (j = 0; j < ndupl; j++)
1323 /* Copy loops. */
1324 copy_loops_to (orig_loops, n_orig_loops, target);
1326 /* Copy bbs. */
1327 copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
1328 place_after, true);
1329 place_after = new_spec_edges[SE_LATCH]->src;
1331 if (flags & DLTHE_RECORD_COPY_NUMBER)
1332 for (i = 0; i < n; i++)
1334 gcc_assert (!new_bbs[i]->aux);
1335 new_bbs[i]->aux = (void *)(size_t)(j + 1);
1338 /* Note whether the blocks and edges belong to an irreducible loop. */
1339 if (add_irreducible_flag)
1341 for (i = 0; i < n; i++)
1342 new_bbs[i]->flags |= BB_DUPLICATED;
1343 for (i = 0; i < n; i++)
1345 edge_iterator ei;
1346 new_bb = new_bbs[i];
1347 if (new_bb->loop_father == target)
1348 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1350 FOR_EACH_EDGE (ae, ei, new_bb->succs)
1351 if ((ae->dest->flags & BB_DUPLICATED)
1352 && (ae->src->loop_father == target
1353 || ae->dest->loop_father == target))
1354 ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1356 for (i = 0; i < n; i++)
1357 new_bbs[i]->flags &= ~BB_DUPLICATED;
1360 /* Redirect the special edges. */
1361 if (is_latch)
1363 redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1364 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1365 loop->header);
1366 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
1367 latch = loop->latch = new_bbs[n - 1];
1368 e = latch_edge = new_spec_edges[SE_LATCH];
1370 else
1372 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1373 loop->header);
1374 redirect_edge_and_branch_force (e, new_bbs[0]);
1375 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
1376 e = new_spec_edges[SE_LATCH];
1379 /* Record exit edge in this copy. */
1380 if (orig && bitmap_bit_p (wont_exit, j + 1))
1382 if (to_remove)
1383 to_remove->safe_push (new_spec_edges[SE_ORIG]);
1384 set_zero_probability (new_spec_edges[SE_ORIG]);
1386 /* Scale the frequencies of the blocks dominated by the exit. */
1387 if (bbs_to_scale)
1389 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1391 scale_bbs_frequencies_int (new_bbs + i, 1, scale_after_exit,
1392 REG_BR_PROB_BASE);
1397 /* Record the first copy in the control flow order if it is not
1398 the original loop (i.e. in case of peeling). */
1399 if (!first_active_latch)
1401 memcpy (first_active, new_bbs, n * sizeof (basic_block));
1402 first_active_latch = new_bbs[n - 1];
1405 /* Set counts and frequencies. */
1406 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1408 scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1409 scale_act = combine_probabilities (scale_act, scale_step[j]);
1412 free (new_bbs);
1413 free (orig_loops);
1415 /* Record the exit edge in the original loop body, and update the frequencies. */
1416 if (orig && bitmap_bit_p (wont_exit, 0))
1418 if (to_remove)
1419 to_remove->safe_push (orig);
1420 set_zero_probability (orig);
1422 /* Scale the frequencies of the blocks dominated by the exit. */
1423 if (bbs_to_scale)
1425 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1427 scale_bbs_frequencies_int (bbs + i, 1, scale_after_exit,
1428 REG_BR_PROB_BASE);
1433 /* Update the original loop. */
1434 if (!is_latch)
1435 set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1436 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1438 scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
1439 free (scale_step);
1442 /* Update dominators of outer blocks if affected. */
1443 for (i = 0; i < n; i++)
1445 basic_block dominated, dom_bb;
1446 vec<basic_block> dom_bbs;
1447 unsigned j;
1449 bb = bbs[i];
1450 bb->aux = 0;
1452 dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
1453 FOR_EACH_VEC_ELT (dom_bbs, j, dominated)
1455 if (flow_bb_inside_loop_p (loop, dominated))
1456 continue;
1457 dom_bb = nearest_common_dominator (
1458 CDI_DOMINATORS, first_active[i], first_active_latch);
1459 set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1461 dom_bbs.release ();
1463 free (first_active);
1465 free (bbs);
1466 BITMAP_FREE (bbs_to_scale);
1468 return true;
1471 /* A callback for make_forwarder block, to redirect all edges except for
1472 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1473 whether to redirect it. */
1475 edge mfb_kj_edge;
1476 bool
1477 mfb_keep_just (edge e)
1479 return e != mfb_kj_edge;
1482 /* True when a candidate preheader BLOCK has predecessors from LOOP. */
1484 static bool
1485 has_preds_from_loop (basic_block block, struct loop *loop)
1487 edge e;
1488 edge_iterator ei;
1490 FOR_EACH_EDGE (e, ei, block->preds)
1491 if (e->src->loop_father == loop)
1492 return true;
1493 return false;
1496 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1497 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1498 entry; otherwise we also force preheader block to have only one successor.
1499 When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
1500 to be a fallthru predecessor to the loop header and to have only
1501 predecessors from outside of the loop.
1502 The function also updates dominators. */
1504 basic_block
1505 create_preheader (struct loop *loop, int flags)
1507 edge e;
1508 basic_block dummy;
1509 int nentry = 0;
1510 bool irred = false;
1511 bool latch_edge_was_fallthru;
1512 edge one_succ_pred = NULL, single_entry = NULL;
1513 edge_iterator ei;
1515 FOR_EACH_EDGE (e, ei, loop->header->preds)
1517 if (e->src == loop->latch)
1518 continue;
1519 irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1520 nentry++;
1521 single_entry = e;
1522 if (single_succ_p (e->src))
1523 one_succ_pred = e;
1525 gcc_assert (nentry);
1526 if (nentry == 1)
1528 bool need_forwarder_block = false;
1530 /* We do not allow entry block to be the loop preheader, since we
1531 cannot emit code there. */
1532 if (single_entry->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1533 need_forwarder_block = true;
1534 else
1536 /* If we want simple preheaders, also force the preheader to have
1537 just a single successor. */
1538 if ((flags & CP_SIMPLE_PREHEADERS)
1539 && !single_succ_p (single_entry->src))
1540 need_forwarder_block = true;
1541 /* If we want fallthru preheaders, also create forwarder block when
1542 preheader ends with a jump or has predecessors from loop. */
1543 else if ((flags & CP_FALLTHRU_PREHEADERS)
1544 && (JUMP_P (BB_END (single_entry->src))
1545 || has_preds_from_loop (single_entry->src, loop)))
1546 need_forwarder_block = true;
1548 if (! need_forwarder_block)
1549 return NULL;
1552 mfb_kj_edge = loop_latch_edge (loop);
1553 latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
1554 if (nentry == 1)
1555 dummy = split_edge (single_entry);
1556 else
1558 edge fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL);
1559 dummy = fallthru->src;
1560 loop->header = fallthru->dest;
1563 /* Try to be clever in placing the newly created preheader. The idea is to
1564 avoid breaking any "fallthruness" relationship between blocks.
1566 The preheader was created just before the header and all incoming edges
1567 to the header were redirected to the preheader, except the latch edge.
1568 So the only problematic case is when this latch edge was a fallthru
1569 edge: it is not anymore after the preheader creation so we have broken
1570 the fallthruness. We're therefore going to look for a better place. */
1571 if (latch_edge_was_fallthru)
1573 if (one_succ_pred)
1574 e = one_succ_pred;
1575 else
1576 e = EDGE_PRED (dummy, 0);
1578 move_block_after (dummy, e->src);
1581 if (irred)
1583 dummy->flags |= BB_IRREDUCIBLE_LOOP;
1584 single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1587 if (dump_file)
1588 fprintf (dump_file, "Created preheader block for loop %i\n",
1589 loop->num);
1591 if (flags & CP_FALLTHRU_PREHEADERS)
1592 gcc_assert ((single_succ_edge (dummy)->flags & EDGE_FALLTHRU)
1593 && !JUMP_P (BB_END (dummy)));
1595 return dummy;
1598 /* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */
1600 void
1601 create_preheaders (int flags)
1603 struct loop *loop;
1605 if (!current_loops)
1606 return;
1608 FOR_EACH_LOOP (loop, 0)
1609 create_preheader (loop, flags);
1610 loops_state_set (LOOPS_HAVE_PREHEADERS);
1613 /* Forces all loop latches to have only single successor. */
1615 void
1616 force_single_succ_latches (void)
1618 struct loop *loop;
1619 edge e;
1621 FOR_EACH_LOOP (loop, 0)
1623 if (loop->latch != loop->header && single_succ_p (loop->latch))
1624 continue;
1626 e = find_edge (loop->latch, loop->header);
1627 gcc_checking_assert (e != NULL);
1629 split_edge (e);
1631 loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES);
1634 /* This function is called from loop_version. It splits the entry edge
1635 of the loop we want to version, adds the versioning condition, and
1636 adjust the edges to the two versions of the loop appropriately.
1637 e is an incoming edge. Returns the basic block containing the
1638 condition.
1640 --- edge e ---- > [second_head]
1642 Split it and insert new conditional expression and adjust edges.
1644 --- edge e ---> [cond expr] ---> [first_head]
1646 +---------> [second_head]
1648 THEN_PROB is the probability of then branch of the condition.
1649 ELSE_PROB is the probability of else branch. Note that they may be both
1650 REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED. */
1652 static basic_block
1653 lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head,
1654 edge e, void *cond_expr, unsigned then_prob,
1655 unsigned else_prob)
1657 basic_block new_head = NULL;
1658 edge e1;
1660 gcc_assert (e->dest == second_head);
1662 /* Split edge 'e'. This will create a new basic block, where we can
1663 insert conditional expr. */
1664 new_head = split_edge (e);
1666 lv_add_condition_to_bb (first_head, second_head, new_head,
1667 cond_expr);
1669 /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */
1670 e = single_succ_edge (new_head);
1671 e1 = make_edge (new_head, first_head,
1672 current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0);
1673 e1->probability = then_prob;
1674 e->probability = else_prob;
1675 e1->count = apply_probability (e->count, e1->probability);
1676 e->count = apply_probability (e->count, e->probability);
1678 set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1679 set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1681 /* Adjust loop header phi nodes. */
1682 lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1684 return new_head;
1687 /* Main entry point for Loop Versioning transformation.
1689 This transformation given a condition and a loop, creates
1690 -if (condition) { loop_copy1 } else { loop_copy2 },
1691 where loop_copy1 is the loop transformed in one way, and loop_copy2
1692 is the loop transformed in another way (or unchanged). COND_EXPR
1693 may be a run time test for things that were not resolved by static
1694 analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1696 If non-NULL, CONDITION_BB is set to the basic block containing the
1697 condition.
1699 THEN_PROB is the probability of the then edge of the if. THEN_SCALE
1700 is the ratio by that the frequencies in the original loop should
1701 be scaled. ELSE_SCALE is the ratio by that the frequencies in the
1702 new loop should be scaled.
1704 If PLACE_AFTER is true, we place the new loop after LOOP in the
1705 instruction stream, otherwise it is placed before LOOP. */
1707 struct loop *
1708 loop_version (struct loop *loop,
1709 void *cond_expr, basic_block *condition_bb,
1710 unsigned then_prob, unsigned else_prob,
1711 unsigned then_scale, unsigned else_scale,
1712 bool place_after)
1714 basic_block first_head, second_head;
1715 edge entry, latch_edge, true_edge, false_edge;
1716 int irred_flag;
1717 struct loop *nloop;
1718 basic_block cond_bb;
1720 /* Record entry and latch edges for the loop */
1721 entry = loop_preheader_edge (loop);
1722 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1723 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1725 /* Note down head of loop as first_head. */
1726 first_head = entry->dest;
1728 /* Duplicate loop. */
1729 if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, 1,
1730 NULL, NULL, NULL, 0))
1732 entry->flags |= irred_flag;
1733 return NULL;
1736 /* After duplication entry edge now points to new loop head block.
1737 Note down new head as second_head. */
1738 second_head = entry->dest;
1740 /* Split loop entry edge and insert new block with cond expr. */
1741 cond_bb = lv_adjust_loop_entry_edge (first_head, second_head,
1742 entry, cond_expr, then_prob, else_prob);
1743 if (condition_bb)
1744 *condition_bb = cond_bb;
1746 if (!cond_bb)
1748 entry->flags |= irred_flag;
1749 return NULL;
1752 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1754 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1755 nloop = loopify (latch_edge,
1756 single_pred_edge (get_bb_copy (loop->header)),
1757 cond_bb, true_edge, false_edge,
1758 false /* Do not redirect all edges. */,
1759 then_scale, else_scale);
1761 copy_loop_info (loop, nloop);
1763 /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1764 lv_flush_pending_stmts (latch_edge);
1766 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
1767 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1768 lv_flush_pending_stmts (false_edge);
1769 /* Adjust irreducible flag. */
1770 if (irred_flag)
1772 cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
1773 loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1774 loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1775 single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
1778 if (place_after)
1780 basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
1781 unsigned i;
1783 after = loop->latch;
1785 for (i = 0; i < nloop->num_nodes; i++)
1787 move_block_after (bbs[i], after);
1788 after = bbs[i];
1790 free (bbs);
1793 /* At this point condition_bb is loop preheader with two successors,
1794 first_head and second_head. Make sure that loop preheader has only
1795 one successor. */
1796 split_edge (loop_preheader_edge (loop));
1797 split_edge (loop_preheader_edge (nloop));
1799 return nloop;