1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005 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 2, or (at your option) any later
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
34 static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
35 static void copy_loops_to (struct loops *, struct loop **, int,
37 static void loop_redirect_edge (edge, basic_block);
38 static bool loop_delete_branch_edge (edge, int);
39 static void remove_bbs (basic_block *, int);
40 static bool rpe_enum_p (basic_block, void *);
41 static int find_path (edge, basic_block **);
42 static bool alp_enum_p (basic_block, void *);
43 static void add_loop (struct loops *, struct loop *);
44 static void fix_loop_placements (struct loops *, struct loop *);
45 static bool fix_bb_placement (struct loops *, basic_block);
46 static void fix_bb_placements (struct loops *, basic_block);
47 static void place_new_loop (struct loops *, struct loop *);
48 static void scale_loop_frequencies (struct loop *, int, int);
49 static basic_block create_preheader (struct loop *, int);
50 static void fix_irreducible_loops (basic_block);
51 static void unloop (struct loops *, struct loop *);
53 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
55 /* Splits basic block BB after INSN, returns created edge. Updates loops
58 split_loop_bb (basic_block bb, void *insn)
62 /* Split the block. */
63 e = split_block (bb, insn);
65 /* Add dest to loop. */
66 add_bb_to_loop (e->dest, e->src->loop_father);
71 /* Checks whether basic block BB is dominated by DATA. */
73 rpe_enum_p (basic_block bb, void *data)
75 return dominated_by_p (CDI_DOMINATORS, bb, data);
78 /* Remove basic blocks BBS from loop structure and dominance info,
79 and delete them afterwards. */
81 remove_bbs (basic_block *bbs, int nbbs)
85 for (i = 0; i < nbbs; i++)
87 remove_bb_from_loops (bbs[i]);
88 delete_basic_block (bbs[i]);
92 /* Find path -- i.e. the basic blocks dominated by edge E and put them
93 into array BBS, that will be allocated large enough to contain them.
94 E->dest must have exactly one predecessor for this to work (it is
95 easy to achieve and we do not put it here because we do not want to
96 alter anything by this function). The number of basic blocks in the
99 find_path (edge e, basic_block **bbs)
101 gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
103 /* Find bbs in the path. */
104 *bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
105 return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
106 n_basic_blocks, e->dest);
109 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
110 Let L be a loop to that BB belongs. Then every successor of BB must either
111 1) belong to some superloop of loop L, or
112 2) be a header of loop K such that K->outer is superloop of L
113 Returns true if we had to move BB into other loop to enforce this condition,
114 false if the placement of BB was already correct (provided that placements
115 of its successors are correct). */
117 fix_bb_placement (struct loops *loops, basic_block bb)
121 struct loop *loop = loops->tree_root, *act;
123 FOR_EACH_EDGE (e, ei, bb->succs)
125 if (e->dest == EXIT_BLOCK_PTR)
128 act = e->dest->loop_father;
129 if (act->header == e->dest)
132 if (flow_loop_nested_p (loop, act))
136 if (loop == bb->loop_father)
139 remove_bb_from_loops (bb);
140 add_bb_to_loop (bb, loop);
145 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
146 enforce condition condition stated in description of fix_bb_placement. We
147 start from basic block FROM that had some of its successors removed, so that
148 his placement no longer has to be correct, and iteratively fix placement of
149 its predecessors that may change if placement of FROM changed. Also fix
150 placement of subloops of FROM->loop_father, that might also be altered due
151 to this change; the condition for them is similar, except that instead of
152 successors we consider edges coming out of the loops. */
154 fix_bb_placements (struct loops *loops, basic_block from)
157 basic_block *queue, *qtop, *qbeg, *qend;
158 struct loop *base_loop;
161 /* We pass through blocks back-reachable from FROM, testing whether some
162 of their successors moved to outer loop. It may be necessary to
163 iterate several times, but it is finite, as we stop unless we move
164 the basic block up the loop structure. The whole story is a bit
165 more complicated due to presence of subloops, those are moved using
166 fix_loop_placement. */
168 base_loop = from->loop_father;
169 if (base_loop == loops->tree_root)
172 in_queue = sbitmap_alloc (last_basic_block);
173 sbitmap_zero (in_queue);
174 SET_BIT (in_queue, from->index);
175 /* Prevent us from going out of the base_loop. */
176 SET_BIT (in_queue, base_loop->header->index);
178 queue = xmalloc ((base_loop->num_nodes + 1) * sizeof (basic_block));
179 qtop = queue + base_loop->num_nodes + 1;
191 RESET_BIT (in_queue, from->index);
193 if (from->loop_father->header == from)
195 /* Subloop header, maybe move the loop upward. */
196 if (!fix_loop_placement (from->loop_father))
201 /* Ordinary basic block. */
202 if (!fix_bb_placement (loops, from))
206 /* Something has changed, insert predecessors into queue. */
207 FOR_EACH_EDGE (e, ei, from->preds)
209 basic_block pred = e->src;
212 if (TEST_BIT (in_queue, pred->index))
215 /* If it is subloop, then it either was not moved, or
216 the path up the loop tree from base_loop do not contain
218 nca = find_common_loop (pred->loop_father, base_loop);
219 if (pred->loop_father != base_loop
221 || nca != pred->loop_father))
222 pred = pred->loop_father->header;
223 else if (!flow_loop_nested_p (from->loop_father, pred->loop_father))
225 /* No point in processing it. */
229 if (TEST_BIT (in_queue, pred->index))
232 /* Schedule the basic block. */
237 SET_BIT (in_queue, pred->index);
244 /* Basic block from has lost one or more of its predecessors, so it might
245 mo longer be part irreducible loop. Fix it and proceed recursively
246 for its successors if needed. */
248 fix_irreducible_loops (basic_block from)
255 unsigned num_edges, i;
257 if (!(from->flags & BB_IRREDUCIBLE_LOOP))
260 on_stack = sbitmap_alloc (last_basic_block);
261 sbitmap_zero (on_stack);
262 SET_BIT (on_stack, from->index);
263 stack = xmalloc (from->loop_father->num_nodes * sizeof (basic_block));
270 bb = stack[--stack_top];
271 RESET_BIT (on_stack, bb->index);
273 FOR_EACH_EDGE (e, ei, bb->preds)
274 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
279 bb->flags &= ~BB_IRREDUCIBLE_LOOP;
280 if (bb->loop_father->header == bb)
281 edges = get_loop_exit_edges (bb->loop_father, &num_edges);
284 num_edges = EDGE_COUNT (bb->succs);
285 edges = xmalloc (num_edges * sizeof (edge));
286 FOR_EACH_EDGE (e, ei, bb->succs)
290 for (i = 0; i < num_edges; i++)
294 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
296 if (!flow_bb_inside_loop_p (from->loop_father, e->dest))
299 e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
300 if (TEST_BIT (on_stack, e->dest->index))
303 SET_BIT (on_stack, e->dest->index);
304 stack[stack_top++] = e->dest;
314 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
315 and update loop structure stored in LOOPS and dominators. Return true if
316 we were able to remove the path, false otherwise (and nothing is affected
319 remove_path (struct loops *loops, edge e)
322 basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
323 int i, nrem, n_bord_bbs, n_dom_bbs;
327 if (!loop_delete_branch_edge (e, 0))
330 /* We need to check whether basic blocks are dominated by the edge
331 e, but we only have basic block dominators. This is easy to
332 fix -- when e->dest has exactly one predecessor, this corresponds
333 to blocks dominated by e->dest, if not, split the edge. */
334 if (!single_pred_p (e->dest))
335 e = single_pred_edge (loop_split_edge_with (e, NULL_RTX));
337 /* It may happen that by removing path we remove one or more loops
338 we belong to. In this case first unloop the loops, then proceed
339 normally. We may assume that e->dest is not a header of any loop,
340 as it now has exactly one predecessor. */
341 while (e->src->loop_father->outer
342 && dominated_by_p (CDI_DOMINATORS,
343 e->src->loop_father->latch, e->dest))
344 unloop (loops, e->src->loop_father);
346 /* Identify the path. */
347 nrem = find_path (e, &rem_bbs);
350 bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
351 seen = sbitmap_alloc (last_basic_block);
354 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
355 for (i = 0; i < nrem; i++)
356 SET_BIT (seen, rem_bbs[i]->index);
357 for (i = 0; i < nrem; i++)
361 FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
362 if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
364 SET_BIT (seen, ae->dest->index);
365 bord_bbs[n_bord_bbs++] = ae->dest;
369 /* Remove the path. */
371 deleted = loop_delete_branch_edge (e, 1);
372 gcc_assert (deleted);
373 dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
375 /* Cancel loops contained in the path. */
376 for (i = 0; i < nrem; i++)
377 if (rem_bbs[i]->loop_father->header == rem_bbs[i])
378 cancel_loop_tree (loops, rem_bbs[i]->loop_father);
380 remove_bbs (rem_bbs, nrem);
383 /* Find blocks whose dominators may be affected. */
386 for (i = 0; i < n_bord_bbs; i++)
390 bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
391 if (TEST_BIT (seen, bb->index))
393 SET_BIT (seen, bb->index);
395 for (ldom = first_dom_son (CDI_DOMINATORS, bb);
397 ldom = next_dom_son (CDI_DOMINATORS, ldom))
398 if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
399 dom_bbs[n_dom_bbs++] = ldom;
404 /* Recount dominators. */
405 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
408 /* These blocks have lost some predecessor(s), thus their irreducible
409 status could be changed. */
410 for (i = 0; i < n_bord_bbs; i++)
411 fix_irreducible_loops (bord_bbs[i]);
414 /* Fix placements of basic blocks inside loops and the placement of
415 loops in the loop tree. */
416 fix_bb_placements (loops, from);
417 fix_loop_placements (loops, from->loop_father);
422 /* Predicate for enumeration in add_loop. */
424 alp_enum_p (basic_block bb, void *alp_header)
426 return bb != (basic_block) alp_header;
429 /* Given LOOP structure with filled header and latch, find the body of the
430 corresponding loop and add it to LOOPS tree. */
432 add_loop (struct loops *loops, struct loop *loop)
437 /* Add it to loop structure. */
438 place_new_loop (loops, loop);
441 /* Find its nodes. */
442 bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
443 n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,
444 bbs, n_basic_blocks, loop->header);
446 for (i = 0; i < n; i++)
447 add_bb_to_loop (bbs[i], loop);
448 add_bb_to_loop (loop->header, loop);
453 /* Multiply all frequencies in LOOP by NUM/DEN. */
455 scale_loop_frequencies (struct loop *loop, int num, int den)
459 bbs = get_loop_body (loop);
460 scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
464 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
465 latch to header and update loop tree stored in LOOPS and dominators
466 accordingly. Everything between them plus LATCH_EDGE destination must
467 be dominated by HEADER_EDGE destination, and back-reachable from
468 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
469 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
470 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
471 Returns newly created loop. */
474 loopify (struct loops *loops, edge latch_edge, edge header_edge,
475 basic_block switch_bb, edge true_edge, edge false_edge,
476 bool redirect_all_edges)
478 basic_block succ_bb = latch_edge->dest;
479 basic_block pred_bb = header_edge->src;
480 basic_block *dom_bbs, *body;
481 unsigned n_dom_bbs, i;
483 struct loop *loop = xcalloc (1, sizeof (struct loop));
484 struct loop *outer = succ_bb->loop_father->outer;
485 int freq, prob, tot_prob;
490 loop->header = header_edge->dest;
491 loop->latch = latch_edge->src;
493 freq = EDGE_FREQUENCY (header_edge);
494 cnt = header_edge->count;
495 prob = EDGE_SUCC (switch_bb, 0)->probability;
496 tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability;
500 /* Redirect edges. */
501 loop_redirect_edge (latch_edge, loop->header);
502 loop_redirect_edge (true_edge, succ_bb);
504 /* During loop versioning, one of the switch_bb edge is already properly
505 set. Do not redirect it again unless redirect_all_edges is true. */
506 if (redirect_all_edges)
508 loop_redirect_edge (header_edge, switch_bb);
509 loop_redirect_edge (false_edge, loop->header);
511 /* Update dominators. */
512 set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
513 set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
516 set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
518 /* Compute new loop. */
519 add_loop (loops, loop);
520 flow_loop_tree_node_add (outer, loop);
522 /* Add switch_bb to appropriate loop. */
523 add_bb_to_loop (switch_bb, outer);
525 /* Fix frequencies. */
526 switch_bb->frequency = freq;
527 switch_bb->count = cnt;
528 FOR_EACH_EDGE (e, ei, switch_bb->succs)
529 e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
530 scale_loop_frequencies (loop, prob, tot_prob);
531 scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
533 /* Update dominators of blocks outside of LOOP. */
534 dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
536 seen = sbitmap_alloc (last_basic_block);
538 body = get_loop_body (loop);
540 for (i = 0; i < loop->num_nodes; i++)
541 SET_BIT (seen, body[i]->index);
543 for (i = 0; i < loop->num_nodes; i++)
547 for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
549 ldom = next_dom_son (CDI_DOMINATORS, ldom))
550 if (!TEST_BIT (seen, ldom->index))
552 SET_BIT (seen, ldom->index);
553 dom_bbs[n_dom_bbs++] = ldom;
557 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
566 /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
567 the LOOP was removed. After this function, original loop latch will
568 have no successor, which caller is expected to fix somehow. */
570 unloop (struct loops *loops, struct loop *loop)
575 basic_block latch = loop->latch;
579 /* This is relatively straightforward. The dominators are unchanged, as
580 loop header dominates loop latch, so the only thing we have to care of
581 is the placement of loops and basic blocks inside the loop tree. We
582 move them all to the loop->outer, and then let fix_bb_placements do
585 body = get_loop_body (loop);
586 edges = get_loop_exit_edges (loop, &num_edges);
588 for (i = 0; i < n; i++)
589 if (body[i]->loop_father == loop)
591 remove_bb_from_loops (body[i]);
592 add_bb_to_loop (body[i], loop->outer);
599 flow_loop_tree_node_remove (ploop);
600 flow_loop_tree_node_add (loop->outer, ploop);
603 /* Remove the loop and free its data. */
604 flow_loop_tree_node_remove (loop);
605 loops->parray[loop->num] = NULL;
606 flow_loop_free (loop);
608 remove_edge (single_succ_edge (latch));
609 fix_bb_placements (loops, latch);
611 /* If the loop was inside an irreducible region, we would have to somehow
612 update the irreducible marks inside its body. While it is certainly
613 possible to do, it is a bit complicated and this situation should be
614 very rare, so we just remark all loops in this case. */
615 for (i = 0; i < num_edges; i++)
616 if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP)
619 mark_irreducible_loops (loops);
623 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
624 FATHER of LOOP such that all of the edges coming out of LOOP belong to
625 FATHER, and set it as outer loop of LOOP. Return 1 if placement of
628 fix_loop_placement (struct loop *loop)
634 struct loop *father = loop->pred[0], *act;
636 body = get_loop_body (loop);
637 for (i = 0; i < loop->num_nodes; i++)
638 FOR_EACH_EDGE (e, ei, body[i]->succs)
639 if (!flow_bb_inside_loop_p (loop, e->dest))
641 act = find_common_loop (loop, e->dest->loop_father);
642 if (flow_loop_nested_p (father, act))
647 if (father != loop->outer)
649 for (act = loop->outer; act != father; act = act->outer)
650 act->num_nodes -= loop->num_nodes;
651 flow_loop_tree_node_remove (loop);
652 flow_loop_tree_node_add (father, loop);
658 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
659 condition stated in description of fix_loop_placement holds for them.
660 It is used in case when we removed some edges coming out of LOOP, which
661 may cause the right placement of LOOP inside loop tree to change. */
663 fix_loop_placements (struct loops *loops, struct loop *loop)
670 if (!fix_loop_placement (loop))
673 /* Changing the placement of a loop in the loop tree may alter the
674 validity of condition 2) of the description of fix_bb_placement
675 for its preheader, because the successor is the header and belongs
676 to the loop. So call fix_bb_placements to fix up the placement
677 of the preheader and (possibly) of its predecessors. */
678 fix_bb_placements (loops, loop_preheader_edge (loop)->src);
683 /* Creates place for a new LOOP in LOOPS structure. */
685 place_new_loop (struct loops *loops, struct loop *loop)
688 xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));
689 loops->parray[loops->num] = loop;
691 loop->num = loops->num++;
694 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
695 created loop into LOOPS structure. */
697 duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
700 cloop = xcalloc (1, sizeof (struct loop));
701 place_new_loop (loops, cloop);
703 /* Initialize copied loop. */
704 cloop->level = loop->level;
706 /* Set it as copy of loop. */
709 /* Add it to target. */
710 flow_loop_tree_node_add (target, cloop);
715 /* Copies structure of subloops of LOOP into TARGET loop, placing
716 newly created loops into loop tree stored in LOOPS. */
718 duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)
720 struct loop *aloop, *cloop;
722 for (aloop = loop->inner; aloop; aloop = aloop->next)
724 cloop = duplicate_loop (loops, aloop, target);
725 duplicate_subloops (loops, aloop, cloop);
729 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
730 into TARGET loop, placing newly created loops into loop tree LOOPS. */
732 copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)
737 for (i = 0; i < n; i++)
739 aloop = duplicate_loop (loops, copied_loops[i], target);
740 duplicate_subloops (loops, copied_loops[i], aloop);
744 /* Redirects edge E to basic block DEST. */
746 loop_redirect_edge (edge e, basic_block dest)
751 redirect_edge_and_branch_force (e, dest);
754 /* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set,
755 just test whether it is possible to remove the edge. */
757 loop_delete_branch_edge (edge e, int really_delete)
759 basic_block src = e->src;
764 gcc_assert (EDGE_COUNT (src->succs) > 1);
766 /* Cannot handle more than two exit edges. */
767 if (EDGE_COUNT (src->succs) > 2)
769 /* And it must be just a simple branch. */
770 if (!any_condjump_p (BB_END (src)))
773 snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0);
775 if (newdest == EXIT_BLOCK_PTR)
778 /* Hopefully the above conditions should suffice. */
782 /* Redirecting behaves wrongly wrto this flag. */
783 irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
785 if (!redirect_edge_and_branch (e, newdest))
787 single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
788 single_succ_edge (src)->flags |= irr;
793 /* Check whether LOOP's body can be duplicated. */
795 can_duplicate_loop_p (struct loop *loop)
798 basic_block *bbs = get_loop_body (loop);
800 ret = can_copy_bbs_p (bbs, loop->num_nodes);
806 /* The NBBS blocks in BBS will get duplicated and the copies will be placed
807 to LOOP. Update the single_exit information in superloops of LOOP. */
810 update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
815 for (i = 0; i < nbbs; i++)
816 bbs[i]->flags |= BB_DUPLICATED;
818 for (; loop->outer; loop = loop->outer)
820 if (!loop->single_exit)
823 if (loop->single_exit->src->flags & BB_DUPLICATED)
824 loop->single_exit = NULL;
827 for (i = 0; i < nbbs; i++)
828 bbs[i]->flags &= ~BB_DUPLICATED;
831 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
832 LOOPS structure and dominators. E's destination must be LOOP header for
833 this to work, i.e. it must be entry or latch edge of this loop; these are
834 unique, as the loops must have preheaders for this function to work
835 correctly (in case E is latch, the function unrolls the loop, if E is entry
836 edge, it peels the loop). Store edges created by copying ORIG edge from
837 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
838 original LOOP body, the other copies are numbered in order given by control
839 flow through them) into TO_REMOVE array. Returns false if duplication is
842 duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
843 unsigned int ndupl, sbitmap wont_exit,
844 edge orig, edge *to_remove,
845 unsigned int *n_to_remove, int flags)
847 struct loop *target, *aloop;
848 struct loop **orig_loops;
849 unsigned n_orig_loops;
850 basic_block header = loop->header, latch = loop->latch;
851 basic_block *new_bbs, *bbs, *first_active;
852 basic_block new_bb, bb, first_active_latch = NULL;
854 edge spec_edges[2], new_spec_edges[2];
858 int is_latch = (latch == e->src);
859 int scale_act = 0, *scale_step = NULL, scale_main = 0;
860 int p, freq_in, freq_le, freq_out_orig;
861 int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
862 int add_irreducible_flag;
864 gcc_assert (e->dest == loop->header);
865 gcc_assert (ndupl > 0);
869 /* Orig must be edge out of the loop. */
870 gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
871 gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
874 bbs = get_loop_body (loop);
876 /* Check whether duplication is possible. */
877 if (!can_copy_bbs_p (bbs, loop->num_nodes))
882 new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
884 /* In case we are doing loop peeling and the loop is in the middle of
885 irreducible region, the peeled copies will be inside it too. */
886 add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
887 gcc_assert (!is_latch || !add_irreducible_flag);
889 /* Find edge from latch. */
890 latch_edge = loop_latch_edge (loop);
892 if (flags & DLTHE_FLAG_UPDATE_FREQ)
894 /* Calculate coefficients by that we have to scale frequencies
895 of duplicated loop bodies. */
896 freq_in = header->frequency;
897 freq_le = EDGE_FREQUENCY (latch_edge);
900 if (freq_in < freq_le)
902 freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
903 if (freq_out_orig > freq_in - freq_le)
904 freq_out_orig = freq_in - freq_le;
905 prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
906 prob_pass_wont_exit =
907 RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
909 scale_step = xmalloc (ndupl * sizeof (int));
911 for (i = 1; i <= ndupl; i++)
912 scale_step[i - 1] = TEST_BIT (wont_exit, i)
913 ? prob_pass_wont_exit
916 /* Complette peeling is special as the probability of exit in last
918 if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
920 int wanted_freq = EDGE_FREQUENCY (e);
922 if (wanted_freq > freq_in)
923 wanted_freq = freq_in;
925 gcc_assert (!is_latch);
926 /* First copy has frequency of incomming edge. Each subseqeuent
927 frequency should be reduced by prob_pass_wont_exit. Caller
928 should've managed the flags so all except for original loop
929 has won't exist set. */
930 scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
931 /* Now simulate the duplication adjustments and compute header
932 frequency of the last copy. */
933 for (i = 0; i < ndupl; i++)
934 wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE);
935 scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
939 prob_pass_main = TEST_BIT (wont_exit, 0)
940 ? prob_pass_wont_exit
943 scale_main = REG_BR_PROB_BASE;
944 for (i = 0; i < ndupl; i++)
947 p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
949 scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
950 scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
954 scale_main = REG_BR_PROB_BASE;
955 for (i = 0; i < ndupl; i++)
956 scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
957 scale_act = REG_BR_PROB_BASE - prob_pass_thru;
959 for (i = 0; i < ndupl; i++)
960 gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
961 gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
962 && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE);
965 /* Loop the new bbs will belong to. */
966 target = e->src->loop_father;
968 /* Original loops. */
970 for (aloop = loop->inner; aloop; aloop = aloop->next)
972 orig_loops = xcalloc (n_orig_loops, sizeof (struct loop *));
973 for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
974 orig_loops[i] = aloop;
980 first_active = xmalloc (n * sizeof (basic_block));
983 memcpy (first_active, bbs, n * sizeof (basic_block));
984 first_active_latch = latch;
987 /* Update the information about single exits. */
988 if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
989 update_single_exits_after_duplication (bbs, n, target);
991 /* Record exit edge in original loop body. */
992 if (orig && TEST_BIT (wont_exit, 0))
993 to_remove[(*n_to_remove)++] = orig;
995 spec_edges[SE_ORIG] = orig;
996 spec_edges[SE_LATCH] = latch_edge;
998 for (j = 0; j < ndupl; j++)
1001 copy_loops_to (loops, orig_loops, n_orig_loops, target);
1004 copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop);
1006 if (flags & DLTHE_RECORD_COPY_NUMBER)
1007 for (i = 0; i < n; i++)
1009 gcc_assert (!new_bbs[i]->aux);
1010 new_bbs[i]->aux = (void *)(size_t)(j + 1);
1013 /* Note whether the blocks and edges belong to an irreducible loop. */
1014 if (add_irreducible_flag)
1016 for (i = 0; i < n; i++)
1017 new_bbs[i]->flags |= BB_DUPLICATED;
1018 for (i = 0; i < n; i++)
1021 new_bb = new_bbs[i];
1022 if (new_bb->loop_father == target)
1023 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1025 FOR_EACH_EDGE (ae, ei, new_bb->succs)
1026 if ((ae->dest->flags & BB_DUPLICATED)
1027 && (ae->src->loop_father == target
1028 || ae->dest->loop_father == target))
1029 ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1031 for (i = 0; i < n; i++)
1032 new_bbs[i]->flags &= ~BB_DUPLICATED;
1035 /* Redirect the special edges. */
1038 redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1039 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1041 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
1042 latch = loop->latch = new_bbs[1];
1043 e = latch_edge = new_spec_edges[SE_LATCH];
1047 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1049 redirect_edge_and_branch_force (e, new_bbs[0]);
1050 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
1051 e = new_spec_edges[SE_LATCH];
1054 /* Record exit edge in this copy. */
1055 if (orig && TEST_BIT (wont_exit, j + 1))
1056 to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG];
1058 /* Record the first copy in the control flow order if it is not
1059 the original loop (i.e. in case of peeling). */
1060 if (!first_active_latch)
1062 memcpy (first_active, new_bbs, n * sizeof (basic_block));
1063 first_active_latch = new_bbs[1];
1066 /* Set counts and frequencies. */
1067 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1069 scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1070 scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
1076 /* Update the original loop. */
1078 set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1079 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1081 scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
1085 /* Update dominators of outer blocks if affected. */
1086 for (i = 0; i < n; i++)
1088 basic_block dominated, dom_bb, *dom_bbs;
1094 n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
1095 for (j = 0; j < n_dom_bbs; j++)
1097 dominated = dom_bbs[j];
1098 if (flow_bb_inside_loop_p (loop, dominated))
1100 dom_bb = nearest_common_dominator (
1101 CDI_DOMINATORS, first_active[i], first_active_latch);
1102 set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1106 free (first_active);
1113 /* A callback for make_forwarder block, to redirect all edges except for
1114 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1115 whether to redirect it. */
1117 static edge mfb_kj_edge;
1119 mfb_keep_just (edge e)
1121 return e != mfb_kj_edge;
1124 /* A callback for make_forwarder block, to update data structures for a basic
1125 block JUMP created by redirecting an edge (only the latch edge is being
1129 mfb_update_loops (basic_block jump)
1131 struct loop *loop = single_succ (jump)->loop_father;
1133 if (dom_computed[CDI_DOMINATORS])
1134 set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
1135 add_bb_to_loop (jump, loop);
1139 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1140 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1141 entry; otherwise we also force preheader block to have only one successor.
1142 The function also updates dominators. */
1145 create_preheader (struct loop *loop, int flags)
1149 struct loop *cloop, *ploop;
1152 bool latch_edge_was_fallthru;
1153 edge one_succ_pred = 0;
1156 cloop = loop->outer;
1158 FOR_EACH_EDGE (e, ei, loop->header->preds)
1160 if (e->src == loop->latch)
1162 irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1164 if (single_succ_p (e->src))
1167 gcc_assert (nentry);
1170 /* Get an edge that is different from the one from loop->latch
1172 e = EDGE_PRED (loop->header,
1173 EDGE_PRED (loop->header, 0)->src == loop->latch);
1175 if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src))
1179 mfb_kj_edge = loop_latch_edge (loop);
1180 latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
1181 fallthru = make_forwarder_block (loop->header, mfb_keep_just,
1183 dummy = fallthru->src;
1184 loop->header = fallthru->dest;
1186 /* The header could be a latch of some superloop(s); due to design of
1187 split_block, it would now move to fallthru->dest. */
1188 for (ploop = loop; ploop; ploop = ploop->outer)
1189 if (ploop->latch == dummy)
1190 ploop->latch = fallthru->dest;
1192 /* Try to be clever in placing the newly created preheader. The idea is to
1193 avoid breaking any "fallthruness" relationship between blocks.
1195 The preheader was created just before the header and all incoming edges
1196 to the header were redirected to the preheader, except the latch edge.
1197 So the only problematic case is when this latch edge was a fallthru
1198 edge: it is not anymore after the preheader creation so we have broken
1199 the fallthruness. We're therefore going to look for a better place. */
1200 if (latch_edge_was_fallthru)
1205 e = EDGE_PRED (dummy, 0);
1207 move_block_after (dummy, e->src);
1210 loop->header->loop_father = loop;
1211 add_bb_to_loop (dummy, cloop);
1215 dummy->flags |= BB_IRREDUCIBLE_LOOP;
1216 single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1220 fprintf (dump_file, "Created preheader block for loop %i\n",
1226 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1227 of FLAGS see create_preheader. */
1229 create_preheaders (struct loops *loops, int flags)
1232 for (i = 1; i < loops->num; i++)
1233 create_preheader (loops->parray[i], flags);
1234 loops->state |= LOOPS_HAVE_PREHEADERS;
1237 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1240 force_single_succ_latches (struct loops *loops)
1246 for (i = 1; i < loops->num; i++)
1248 loop = loops->parray[i];
1249 if (loop->latch != loop->header && single_succ_p (loop->latch))
1252 e = find_edge (loop->latch, loop->header);
1254 loop_split_edge_with (e, NULL_RTX);
1256 loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
1259 /* A quite stupid function to put INSNS on edge E. They are supposed to form
1260 just one basic block. Jumps in INSNS are not handled, so cfg do not have to
1261 be ok after this function. The created block is placed on correct place
1262 in LOOPS structure and its dominator is set. */
1264 loop_split_edge_with (edge e, rtx insns)
1266 basic_block src, dest, new_bb;
1267 struct loop *loop_c;
1272 loop_c = find_common_loop (src->loop_father, dest->loop_father);
1274 /* Create basic block for it. */
1276 new_bb = split_edge (e);
1277 add_bb_to_loop (new_bb, loop_c);
1278 new_bb->flags |= (insns ? BB_SUPERBLOCK : 0);
1281 emit_insn_after (insns, BB_END (new_bb));
1283 if (dest->loop_father->latch == src)
1284 dest->loop_father->latch = new_bb;
1289 /* Uses the natural loop discovery to recreate loop notes. */
1291 create_loop_notes (void)
1293 rtx insn, head, end;
1296 basic_block *first, *last, bb, pbb;
1297 struct loop **stack, **top;
1299 #ifdef ENABLE_CHECKING
1300 /* Verify that there really are no loop notes. */
1301 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1302 gcc_assert (!NOTE_P (insn) ||
1303 NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
1306 flow_loops_find (&loops);
1307 free_dominance_info (CDI_DOMINATORS);
1310 last = xcalloc (loops.num, sizeof (basic_block));
1314 for (loop = bb->loop_father; loop->outer; loop = loop->outer)
1315 last[loop->num] = bb;
1318 first = xcalloc (loops.num, sizeof (basic_block));
1319 stack = xcalloc (loops.num, sizeof (struct loop *));
1324 for (loop = bb->loop_father; loop->outer; loop = loop->outer)
1326 if (!first[loop->num])
1329 first[loop->num] = bb;
1332 if (bb == last[loop->num])
1334 /* Prevent loops from overlapping. */
1335 while (*--top != loop)
1336 last[(*top)->num] = EXIT_BLOCK_PTR;
1338 /* If loop starts with jump into it, place the note in
1339 front of the jump. */
1340 insn = PREV_INSN (BB_HEAD (first[loop->num]));
1342 && BARRIER_P (insn))
1343 insn = PREV_INSN (insn);
1347 && any_uncondjump_p (insn)
1348 && onlyjump_p (insn))
1350 pbb = BLOCK_FOR_INSN (insn);
1351 gcc_assert (pbb && single_succ_p (pbb));
1353 if (!flow_bb_inside_loop_p (loop, single_succ (pbb)))
1354 insn = BB_HEAD (first[loop->num]);
1357 insn = BB_HEAD (first[loop->num]);
1359 head = BB_HEAD (first[loop->num]);
1360 emit_note_before (NOTE_INSN_LOOP_BEG, insn);
1361 BB_HEAD (first[loop->num]) = head;
1363 /* Position the note correctly wrto barrier. */
1364 insn = BB_END (last[loop->num]);
1365 if (NEXT_INSN (insn)
1366 && BARRIER_P (NEXT_INSN (insn)))
1367 insn = NEXT_INSN (insn);
1369 end = BB_END (last[loop->num]);
1370 emit_note_after (NOTE_INSN_LOOP_END, insn);
1371 BB_END (last[loop->num]) = end;
1380 flow_loops_free (&loops);
1383 /* This function is called from loop_version. It splits the entry edge
1384 of the loop we want to version, adds the versioning condition, and
1385 adjust the edges to the two versions of the loop appropriately.
1386 e is an incoming edge. Returns the basic block containing the
1389 --- edge e ---- > [second_head]
1391 Split it and insert new conditional expression and adjust edges.
1393 --- edge e ---> [cond expr] ---> [first_head]
1395 +---------> [second_head]
1399 lv_adjust_loop_entry_edge (basic_block first_head,
1400 basic_block second_head,
1404 basic_block new_head = NULL;
1407 gcc_assert (e->dest == second_head);
1409 /* Split edge 'e'. This will create a new basic block, where we can
1410 insert conditional expr. */
1411 new_head = split_edge (e);
1414 lv_add_condition_to_bb (first_head, second_head, new_head,
1417 e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
1418 set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1419 set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1421 /* Adjust loop header phi nodes. */
1422 lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1427 /* Main entry point for Loop Versioning transformation.
1429 This transformation given a condition and a loop, creates
1430 -if (condition) { loop_copy1 } else { loop_copy2 },
1431 where loop_copy1 is the loop transformed in one way, and loop_copy2
1432 is the loop transformed in another way (or unchanged). 'condition'
1433 may be a run time test for things that were not resolved by static
1434 analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
1437 loop_version (struct loops *loops, struct loop * loop,
1438 void *cond_expr, basic_block *condition_bb)
1440 basic_block first_head, second_head;
1441 edge entry, latch_edge, exit, true_edge, false_edge;
1445 /* CHECKME: Loop versioning does not handle nested loop at this point. */
1449 /* Record entry and latch edges for the loop */
1450 entry = loop_preheader_edge (loop);
1451 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1452 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1454 /* Note down head of loop as first_head. */
1455 first_head = entry->dest;
1457 /* Duplicate loop. */
1458 if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1,
1459 NULL, NULL, NULL, NULL, 0))
1462 /* After duplication entry edge now points to new loop head block.
1463 Note down new head as second_head. */
1464 second_head = entry->dest;
1466 /* Split loop entry edge and insert new block with cond expr. */
1467 *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head,
1471 entry->flags |= irred_flag;
1475 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1477 extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
1478 nloop = loopify (loops,
1480 single_pred_edge (get_bb_copy (loop->header)),
1481 *condition_bb, true_edge, false_edge,
1482 false /* Do not redirect all edges. */);
1484 exit = loop->single_exit;
1486 nloop->single_exit = find_edge (get_bb_copy (exit->src), exit->dest);
1488 /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1489 lv_flush_pending_stmts (latch_edge);
1491 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
1492 extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
1493 lv_flush_pending_stmts (false_edge);
1494 /* Adjust irreducible flag. */
1497 (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
1498 loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1499 loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1500 single_pred_edge ((*condition_bb))->flags |= EDGE_IRREDUCIBLE_LOOP;
1503 /* At this point condition_bb is loop predheader with two successors,
1504 first_head and second_head. Make sure that loop predheader has only
1506 loop_split_edge_with (loop_preheader_edge (loop), NULL);
1507 loop_split_edge_with (loop_preheader_edge (nloop), NULL);
1512 /* The structure of LOOPS might have changed. Some loops might get removed
1513 (and their headers and latches were set to NULL), loop exists might get
1514 removed (thus the loop nesting may be wrong), and some blocks and edges
1515 were changed (so the information about bb --> loop mapping does not have
1516 to be correct). But still for the remaining loops the header dominates
1517 the latch, and loops did not get new subloobs (new loops might possibly
1518 get created, but we are not interested in them). Fix up the mess.
1520 If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1524 fix_loop_structure (struct loops *loops, bitmap changed_bbs)
1527 struct loop *loop, *ploop;
1530 /* Remove the old bb -> loop mapping. */
1533 bb->aux = (void *) (size_t) bb->loop_father->depth;
1534 bb->loop_father = loops->tree_root;
1537 /* Remove the dead loops from structures. */
1538 loops->tree_root->num_nodes = n_basic_blocks + 2;
1539 for (i = 1; i < loops->num; i++)
1541 loop = loops->parray[i];
1545 loop->num_nodes = 0;
1551 ploop = loop->inner;
1552 flow_loop_tree_node_remove (ploop);
1553 flow_loop_tree_node_add (loop->outer, ploop);
1556 /* Remove the loop and free its data. */
1557 flow_loop_tree_node_remove (loop);
1558 loops->parray[loop->num] = NULL;
1559 flow_loop_free (loop);
1562 /* Rescan the bodies of loops, starting from the outermost. */
1563 loop = loops->tree_root;
1571 && loop != loops->tree_root)
1573 if (loop == loops->tree_root)
1579 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
1582 /* Now fix the loop nesting. */
1583 for (i = 1; i < loops->num; i++)
1585 loop = loops->parray[i];
1589 bb = loop_preheader_edge (loop)->src;
1590 if (bb->loop_father != loop->outer)
1592 flow_loop_tree_node_remove (loop);
1593 flow_loop_tree_node_add (bb->loop_father, loop);
1597 /* Mark the blocks whose loop has changed. */
1601 && (void *) (size_t) bb->loop_father->depth != bb->aux)
1602 bitmap_set_bit (changed_bbs, bb->index);
1607 mark_single_exit_loops (loops);
1608 mark_irreducible_loops (loops);