1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
32 #include "tree-flow.h"
34 static void copy_loops_to (struct loop **, int,
36 static void loop_redirect_edge (edge, basic_block);
37 static void remove_bbs (basic_block *, int);
38 static bool rpe_enum_p (const_basic_block, const void *);
39 static int find_path (edge, basic_block **);
40 static void fix_loop_placements (struct loop *, bool *);
41 static bool fix_bb_placement (basic_block);
42 static void fix_bb_placements (basic_block, bool *);
43 static void unloop (struct loop *, bool *);
45 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
47 /* Checks whether basic block BB is dominated by DATA. */
49 rpe_enum_p (const_basic_block bb, const void *data)
51 return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data);
54 /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
57 remove_bbs (basic_block *bbs, int nbbs)
61 for (i = 0; i < nbbs; i++)
62 delete_basic_block (bbs[i]);
65 /* Find path -- i.e. the basic blocks dominated by edge E and put them
66 into array BBS, that will be allocated large enough to contain them.
67 E->dest must have exactly one predecessor for this to work (it is
68 easy to achieve and we do not put it here because we do not want to
69 alter anything by this function). The number of basic blocks in the
72 find_path (edge e, basic_block **bbs)
74 gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
76 /* Find bbs in the path. */
77 *bbs = XCNEWVEC (basic_block, n_basic_blocks);
78 return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
79 n_basic_blocks, e->dest);
82 /* Fix placement of basic block BB inside loop hierarchy --
83 Let L be a loop to that BB belongs. Then every successor of BB must either
84 1) belong to some superloop of loop L, or
85 2) be a header of loop K such that K->outer is superloop of L
86 Returns true if we had to move BB into other loop to enforce this condition,
87 false if the placement of BB was already correct (provided that placements
88 of its successors are correct). */
90 fix_bb_placement (basic_block bb)
94 struct loop *loop = current_loops->tree_root, *act;
96 FOR_EACH_EDGE (e, ei, bb->succs)
98 if (e->dest == EXIT_BLOCK_PTR)
101 act = e->dest->loop_father;
102 if (act->header == e->dest)
103 act = loop_outer (act);
105 if (flow_loop_nested_p (loop, act))
109 if (loop == bb->loop_father)
112 remove_bb_from_loops (bb);
113 add_bb_to_loop (bb, loop);
118 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
119 of LOOP to that leads at least one exit edge of LOOP, and set it
120 as the immediate superloop of LOOP. Return true if the immediate superloop
124 fix_loop_placement (struct loop *loop)
128 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
129 struct loop *father = current_loops->tree_root, *act;
132 FOR_EACH_VEC_ELT (edge, exits, i, e)
134 act = find_common_loop (loop, e->dest->loop_father);
135 if (flow_loop_nested_p (father, act))
139 if (father != loop_outer (loop))
141 for (act = loop_outer (loop); act != father; act = loop_outer (act))
142 act->num_nodes -= loop->num_nodes;
143 flow_loop_tree_node_remove (loop);
144 flow_loop_tree_node_add (father, loop);
146 /* The exit edges of LOOP no longer exits its original immediate
147 superloops; remove them from the appropriate exit lists. */
148 FOR_EACH_VEC_ELT (edge, exits, i, e)
149 rescan_loop_exit (e, false, false);
154 VEC_free (edge, heap, exits);
158 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
159 enforce condition condition stated in description of fix_bb_placement. We
160 start from basic block FROM that had some of its successors removed, so that
161 his placement no longer has to be correct, and iteratively fix placement of
162 its predecessors that may change if placement of FROM changed. Also fix
163 placement of subloops of FROM->loop_father, that might also be altered due
164 to this change; the condition for them is similar, except that instead of
165 successors we consider edges coming out of the loops.
167 If the changes may invalidate the information about irreducible regions,
168 IRRED_INVALIDATED is set to true. */
171 fix_bb_placements (basic_block from,
172 bool *irred_invalidated)
175 basic_block *queue, *qtop, *qbeg, *qend;
176 struct loop *base_loop, *target_loop;
179 /* We pass through blocks back-reachable from FROM, testing whether some
180 of their successors moved to outer loop. It may be necessary to
181 iterate several times, but it is finite, as we stop unless we move
182 the basic block up the loop structure. The whole story is a bit
183 more complicated due to presence of subloops, those are moved using
184 fix_loop_placement. */
186 base_loop = from->loop_father;
187 /* If we are already in the outermost loop, the basic blocks cannot be moved
188 outside of it. If FROM is the header of the base loop, it cannot be moved
189 outside of it, either. In both cases, we can end now. */
190 if (base_loop == current_loops->tree_root
191 || from == base_loop->header)
194 in_queue = sbitmap_alloc (last_basic_block);
195 sbitmap_zero (in_queue);
196 SET_BIT (in_queue, from->index);
197 /* Prevent us from going out of the base_loop. */
198 SET_BIT (in_queue, base_loop->header->index);
200 queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);
201 qtop = queue + base_loop->num_nodes + 1;
213 RESET_BIT (in_queue, from->index);
215 if (from->loop_father->header == from)
217 /* Subloop header, maybe move the loop upward. */
218 if (!fix_loop_placement (from->loop_father))
220 target_loop = loop_outer (from->loop_father);
224 /* Ordinary basic block. */
225 if (!fix_bb_placement (from))
227 target_loop = from->loop_father;
230 FOR_EACH_EDGE (e, ei, from->succs)
232 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
233 *irred_invalidated = true;
236 /* Something has changed, insert predecessors into queue. */
237 FOR_EACH_EDGE (e, ei, from->preds)
239 basic_block pred = e->src;
242 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
243 *irred_invalidated = true;
245 if (TEST_BIT (in_queue, pred->index))
248 /* If it is subloop, then it either was not moved, or
249 the path up the loop tree from base_loop do not contain
251 nca = find_common_loop (pred->loop_father, base_loop);
252 if (pred->loop_father != base_loop
254 || nca != pred->loop_father))
255 pred = pred->loop_father->header;
256 else if (!flow_loop_nested_p (target_loop, pred->loop_father))
258 /* If PRED is already higher in the loop hierarchy than the
259 TARGET_LOOP to that we moved FROM, the change of the position
260 of FROM does not affect the position of PRED, so there is no
261 point in processing it. */
265 if (TEST_BIT (in_queue, pred->index))
268 /* Schedule the basic block. */
273 SET_BIT (in_queue, pred->index);
280 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
281 and update loop structures and dominators. Return true if we were able
282 to remove the path, false otherwise (and nothing is affected then). */
287 basic_block *rem_bbs, *bord_bbs, from, bb;
288 VEC (basic_block, heap) *dom_bbs;
289 int i, nrem, n_bord_bbs;
291 bool irred_invalidated = false;
295 if (!can_remove_branch_p (e))
298 /* Keep track of whether we need to update information about irreducible
299 regions. This is the case if the removed area is a part of the
300 irreducible region, or if the set of basic blocks that belong to a loop
301 that is inside an irreducible region is changed, or if such a loop is
303 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
304 irred_invalidated = true;
306 /* We need to check whether basic blocks are dominated by the edge
307 e, but we only have basic block dominators. This is easy to
308 fix -- when e->dest has exactly one predecessor, this corresponds
309 to blocks dominated by e->dest, if not, split the edge. */
310 if (!single_pred_p (e->dest))
311 e = single_pred_edge (split_edge (e));
313 /* It may happen that by removing path we remove one or more loops
314 we belong to. In this case first unloop the loops, then proceed
315 normally. We may assume that e->dest is not a header of any loop,
316 as it now has exactly one predecessor. */
317 for (l = e->src->loop_father; loop_outer (l); l = f)
320 if (dominated_by_p (CDI_DOMINATORS, l->latch, e->dest))
321 unloop (l, &irred_invalidated);
324 /* Identify the path. */
325 nrem = find_path (e, &rem_bbs);
328 bord_bbs = XCNEWVEC (basic_block, n_basic_blocks);
329 seen = sbitmap_alloc (last_basic_block);
332 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
333 for (i = 0; i < nrem; i++)
334 SET_BIT (seen, rem_bbs[i]->index);
335 if (!irred_invalidated)
336 FOR_EACH_EDGE (ae, ei, e->src->succs)
337 if (ae != e && ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index)
338 && ae->flags & EDGE_IRREDUCIBLE_LOOP)
339 irred_invalidated = true;
340 for (i = 0; i < nrem; i++)
343 FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
344 if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
346 SET_BIT (seen, ae->dest->index);
347 bord_bbs[n_bord_bbs++] = ae->dest;
349 if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
350 irred_invalidated = true;
354 /* Remove the path. */
359 /* Cancel loops contained in the path. */
360 for (i = 0; i < nrem; i++)
361 if (rem_bbs[i]->loop_father->header == rem_bbs[i])
362 cancel_loop_tree (rem_bbs[i]->loop_father);
364 remove_bbs (rem_bbs, nrem);
367 /* Find blocks whose dominators may be affected. */
369 for (i = 0; i < n_bord_bbs; i++)
373 bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
374 if (TEST_BIT (seen, bb->index))
376 SET_BIT (seen, bb->index);
378 for (ldom = first_dom_son (CDI_DOMINATORS, bb);
380 ldom = next_dom_son (CDI_DOMINATORS, ldom))
381 if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
382 VEC_safe_push (basic_block, heap, dom_bbs, ldom);
387 /* Recount dominators. */
388 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);
389 VEC_free (basic_block, heap, dom_bbs);
392 /* Fix placements of basic blocks inside loops and the placement of
393 loops in the loop tree. */
394 fix_bb_placements (from, &irred_invalidated);
395 fix_loop_placements (from->loop_father, &irred_invalidated);
397 if (irred_invalidated
398 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
399 mark_irreducible_loops ();
404 /* Creates place for a new LOOP in loops structure. */
407 place_new_loop (struct loop *loop)
409 loop->num = number_of_loops ();
410 VEC_safe_push (loop_p, gc, current_loops->larray, loop);
413 /* Given LOOP structure with filled header and latch, find the body of the
414 corresponding loop and add it to loops tree. Insert the LOOP as a son of
418 add_loop (struct loop *loop, struct loop *outer)
422 struct loop *subloop;
426 /* Add it to loop structure. */
427 place_new_loop (loop);
428 flow_loop_tree_node_add (outer, loop);
430 /* Find its nodes. */
431 bbs = XNEWVEC (basic_block, n_basic_blocks);
432 n = get_loop_body_with_size (loop, bbs, n_basic_blocks);
434 for (i = 0; i < n; i++)
436 if (bbs[i]->loop_father == outer)
438 remove_bb_from_loops (bbs[i]);
439 add_bb_to_loop (bbs[i], loop);
445 /* If we find a direct subloop of OUTER, move it to LOOP. */
446 subloop = bbs[i]->loop_father;
447 if (loop_outer (subloop) == outer
448 && subloop->header == bbs[i])
450 flow_loop_tree_node_remove (subloop);
451 flow_loop_tree_node_add (loop, subloop);
455 /* Update the information about loop exit edges. */
456 for (i = 0; i < n; i++)
458 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
460 rescan_loop_exit (e, false, false);
467 /* Multiply all frequencies in LOOP by NUM/DEN. */
469 scale_loop_frequencies (struct loop *loop, int num, int den)
473 bbs = get_loop_body (loop);
474 scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
478 /* Recompute dominance information for basic blocks outside LOOP. */
481 update_dominators_in_loop (struct loop *loop)
483 VEC (basic_block, heap) *dom_bbs = NULL;
488 seen = sbitmap_alloc (last_basic_block);
490 body = get_loop_body (loop);
492 for (i = 0; i < loop->num_nodes; i++)
493 SET_BIT (seen, body[i]->index);
495 for (i = 0; i < loop->num_nodes; i++)
499 for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
501 ldom = next_dom_son (CDI_DOMINATORS, ldom))
502 if (!TEST_BIT (seen, ldom->index))
504 SET_BIT (seen, ldom->index);
505 VEC_safe_push (basic_block, heap, dom_bbs, ldom);
509 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
512 VEC_free (basic_block, heap, dom_bbs);
515 /* Creates an if region as shown above. CONDITION is used to create
519 | ------------- -------------
520 | | pred_bb | | pred_bb |
521 | ------------- -------------
525 | | ====> -------------
530 | ------------- e_false / \ e_true
532 | ------------- ----------- -----------
533 | | false_bb | | true_bb |
534 | ----------- -----------
541 | | exit_edge (result)
550 create_empty_if_region_on_edge (edge entry_edge, tree condition)
553 basic_block cond_bb, true_bb, false_bb, join_bb;
554 edge e_true, e_false, exit_edge;
557 gimple_stmt_iterator gsi;
559 cond_bb = split_edge (entry_edge);
561 /* Insert condition in cond_bb. */
562 gsi = gsi_last_bb (cond_bb);
564 force_gimple_operand_gsi (&gsi, condition, true, NULL,
565 false, GSI_NEW_STMT);
566 cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);
567 gsi = gsi_last_bb (cond_bb);
568 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
570 join_bb = split_edge (single_succ_edge (cond_bb));
572 e_true = single_succ_edge (cond_bb);
573 true_bb = split_edge (e_true);
575 e_false = make_edge (cond_bb, join_bb, 0);
576 false_bb = split_edge (e_false);
578 e_true->flags &= ~EDGE_FALLTHRU;
579 e_true->flags |= EDGE_TRUE_VALUE;
580 e_false->flags &= ~EDGE_FALLTHRU;
581 e_false->flags |= EDGE_FALSE_VALUE;
583 set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);
584 set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);
585 set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);
586 set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
588 exit_edge = single_succ_edge (join_bb);
590 if (single_pred_p (exit_edge->dest))
591 set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);
596 /* create_empty_loop_on_edge
598 | - pred_bb - ------ pred_bb ------
599 | | | | iv0 = initial_value |
600 | -----|----- ---------|-----------
601 | | ______ | entry_edge
603 | | ====> | -V---V- loop_header -------------
604 | V | | iv_before = phi (iv0, iv_after) |
605 | - succ_bb - | ---|-----------------------------
607 | ----------- | ---V--- loop_body ---------------
608 | | | iv_after = iv_before + stride |
609 | | | if (iv_before < upper_bound) |
610 | | ---|--------------\--------------
613 | | - loop_latch - V- succ_bb -
615 | | /------------- -----------
618 Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
619 that is used before the increment of IV. IV_BEFORE should be used for
620 adding code to the body that uses the IV. OUTER is the outer loop in
621 which the new loop should be inserted.
623 Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
624 inserted on the loop entry edge. This implies that this function
625 should be used only when the UPPER_BOUND expression is a loop
629 create_empty_loop_on_edge (edge entry_edge,
631 tree stride, tree upper_bound,
637 basic_block loop_header, loop_latch, succ_bb, pred_bb;
639 gimple_stmt_iterator gsi;
646 gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
648 /* Create header, latch and wire up the loop. */
649 pred_bb = entry_edge->src;
650 loop_header = split_edge (entry_edge);
651 loop_latch = split_edge (single_succ_edge (loop_header));
652 succ_bb = single_succ (loop_latch);
653 make_edge (loop_header, succ_bb, 0);
654 redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);
656 /* Set immediate dominator information. */
657 set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);
658 set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);
659 set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);
661 /* Initialize a loop structure and put it in a loop hierarchy. */
662 loop = alloc_loop ();
663 loop->header = loop_header;
664 loop->latch = loop_latch;
665 add_loop (loop, outer);
667 /* TODO: Fix frequencies and counts. */
668 prob = REG_BR_PROB_BASE / 2;
670 scale_loop_frequencies (loop, REG_BR_PROB_BASE - prob, REG_BR_PROB_BASE);
672 /* Update dominators. */
673 update_dominators_in_loop (loop);
675 /* Modify edge flags. */
676 exit_e = single_exit (loop);
677 exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
678 single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
680 /* Construct IV code in loop. */
681 initial_value = force_gimple_operand (initial_value, &stmts, true, iv);
684 gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
685 gsi_commit_edge_inserts ();
688 upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL);
691 gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
692 gsi_commit_edge_inserts ();
695 gsi = gsi_last_bb (loop_header);
696 create_iv (initial_value, stride, iv, loop, &gsi, false,
697 iv_before, iv_after);
699 /* Insert loop exit condition. */
700 cond_expr = gimple_build_cond
701 (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE);
703 exit_test = gimple_cond_lhs (cond_expr);
704 exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
705 false, GSI_NEW_STMT);
706 gimple_cond_set_lhs (cond_expr, exit_test);
707 gsi = gsi_last_bb (exit_e->src);
708 gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT);
710 split_block_after_labels (loop_header);
715 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
716 latch to header and update loop tree and dominators
717 accordingly. Everything between them plus LATCH_EDGE destination must
718 be dominated by HEADER_EDGE destination, and back-reachable from
719 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
720 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
721 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
722 Returns the newly created loop. Frequencies and counts in the new loop
723 are scaled by FALSE_SCALE and in the old one by TRUE_SCALE. */
726 loopify (edge latch_edge, edge header_edge,
727 basic_block switch_bb, edge true_edge, edge false_edge,
728 bool redirect_all_edges, unsigned true_scale, unsigned false_scale)
730 basic_block succ_bb = latch_edge->dest;
731 basic_block pred_bb = header_edge->src;
732 struct loop *loop = alloc_loop ();
733 struct loop *outer = loop_outer (succ_bb->loop_father);
739 loop->header = header_edge->dest;
740 loop->latch = latch_edge->src;
742 freq = EDGE_FREQUENCY (header_edge);
743 cnt = header_edge->count;
745 /* Redirect edges. */
746 loop_redirect_edge (latch_edge, loop->header);
747 loop_redirect_edge (true_edge, succ_bb);
749 /* During loop versioning, one of the switch_bb edge is already properly
750 set. Do not redirect it again unless redirect_all_edges is true. */
751 if (redirect_all_edges)
753 loop_redirect_edge (header_edge, switch_bb);
754 loop_redirect_edge (false_edge, loop->header);
756 /* Update dominators. */
757 set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
758 set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
761 set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
763 /* Compute new loop. */
764 add_loop (loop, outer);
766 /* Add switch_bb to appropriate loop. */
767 if (switch_bb->loop_father)
768 remove_bb_from_loops (switch_bb);
769 add_bb_to_loop (switch_bb, outer);
771 /* Fix frequencies. */
772 if (redirect_all_edges)
774 switch_bb->frequency = freq;
775 switch_bb->count = cnt;
776 FOR_EACH_EDGE (e, ei, switch_bb->succs)
778 e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
781 scale_loop_frequencies (loop, false_scale, REG_BR_PROB_BASE);
782 scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE);
783 update_dominators_in_loop (loop);
788 /* Remove the latch edge of a LOOP and update loops to indicate that
789 the LOOP was removed. After this function, original loop latch will
790 have no successor, which caller is expected to fix somehow.
792 If this may cause the information about irreducible regions to become
793 invalid, IRRED_INVALIDATED is set to true. */
796 unloop (struct loop *loop, bool *irred_invalidated)
801 basic_block latch = loop->latch;
804 if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
805 *irred_invalidated = true;
807 /* This is relatively straightforward. The dominators are unchanged, as
808 loop header dominates loop latch, so the only thing we have to care of
809 is the placement of loops and basic blocks inside the loop tree. We
810 move them all to the loop->outer, and then let fix_bb_placements do
813 body = get_loop_body (loop);
815 for (i = 0; i < n; i++)
816 if (body[i]->loop_father == loop)
818 remove_bb_from_loops (body[i]);
819 add_bb_to_loop (body[i], loop_outer (loop));
826 flow_loop_tree_node_remove (ploop);
827 flow_loop_tree_node_add (loop_outer (loop), ploop);
830 /* Remove the loop and free its data. */
833 remove_edge (single_succ_edge (latch));
835 /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
836 there is an irreducible region inside the cancelled loop, the flags will
838 fix_bb_placements (latch, &dummy);
841 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
842 condition stated in description of fix_loop_placement holds for them.
843 It is used in case when we removed some edges coming out of LOOP, which
844 may cause the right placement of LOOP inside loop tree to change.
846 IRRED_INVALIDATED is set to true if a change in the loop structures might
847 invalidate the information about irreducible regions. */
850 fix_loop_placements (struct loop *loop, bool *irred_invalidated)
854 while (loop_outer (loop))
856 outer = loop_outer (loop);
857 if (!fix_loop_placement (loop))
860 /* Changing the placement of a loop in the loop tree may alter the
861 validity of condition 2) of the description of fix_bb_placement
862 for its preheader, because the successor is the header and belongs
863 to the loop. So call fix_bb_placements to fix up the placement
864 of the preheader and (possibly) of its predecessors. */
865 fix_bb_placements (loop_preheader_edge (loop)->src,
871 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
872 created loop into loops structure. */
874 duplicate_loop (struct loop *loop, struct loop *target)
877 cloop = alloc_loop ();
878 place_new_loop (cloop);
880 /* Mark the new loop as copy of LOOP. */
881 set_loop_copy (loop, cloop);
883 /* Add it to target. */
884 flow_loop_tree_node_add (target, cloop);
889 /* Copies structure of subloops of LOOP into TARGET loop, placing
890 newly created loops into loop tree. */
892 duplicate_subloops (struct loop *loop, struct loop *target)
894 struct loop *aloop, *cloop;
896 for (aloop = loop->inner; aloop; aloop = aloop->next)
898 cloop = duplicate_loop (aloop, target);
899 duplicate_subloops (aloop, cloop);
903 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
904 into TARGET loop, placing newly created loops into loop tree. */
906 copy_loops_to (struct loop **copied_loops, int n, struct loop *target)
911 for (i = 0; i < n; i++)
913 aloop = duplicate_loop (copied_loops[i], target);
914 duplicate_subloops (copied_loops[i], aloop);
918 /* Redirects edge E to basic block DEST. */
920 loop_redirect_edge (edge e, basic_block dest)
925 redirect_edge_and_branch_force (e, dest);
928 /* Check whether LOOP's body can be duplicated. */
930 can_duplicate_loop_p (const struct loop *loop)
933 basic_block *bbs = get_loop_body (loop);
935 ret = can_copy_bbs_p (bbs, loop->num_nodes);
941 /* Sets probability and count of edge E to zero. The probability and count
942 is redistributed evenly to the remaining edges coming from E->src. */
945 set_zero_probability (edge e)
947 basic_block bb = e->src;
949 edge ae, last = NULL;
950 unsigned n = EDGE_COUNT (bb->succs);
951 gcov_type cnt = e->count, cnt1;
952 unsigned prob = e->probability, prob1;
955 cnt1 = cnt / (n - 1);
956 prob1 = prob / (n - 1);
958 FOR_EACH_EDGE (ae, ei, bb->succs)
963 ae->probability += prob1;
968 /* Move the rest to one of the edges. */
969 last->probability += prob % (n - 1);
970 last->count += cnt % (n - 1);
976 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
977 loop structure and dominators. E's destination must be LOOP header for
978 this to work, i.e. it must be entry or latch edge of this loop; these are
979 unique, as the loops must have preheaders for this function to work
980 correctly (in case E is latch, the function unrolls the loop, if E is entry
981 edge, it peels the loop). Store edges created by copying ORIG edge from
982 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
983 original LOOP body, the other copies are numbered in order given by control
984 flow through them) into TO_REMOVE array. Returns false if duplication is
988 duplicate_loop_to_header_edge (struct loop *loop, edge e,
989 unsigned int ndupl, sbitmap wont_exit,
990 edge orig, VEC (edge, heap) **to_remove,
993 struct loop *target, *aloop;
994 struct loop **orig_loops;
995 unsigned n_orig_loops;
996 basic_block header = loop->header, latch = loop->latch;
997 basic_block *new_bbs, *bbs, *first_active;
998 basic_block new_bb, bb, first_active_latch = NULL;
1000 edge spec_edges[2], new_spec_edges[2];
1004 int is_latch = (latch == e->src);
1005 int scale_act = 0, *scale_step = NULL, scale_main = 0;
1006 int scale_after_exit = 0;
1007 int p, freq_in, freq_le, freq_out_orig;
1008 int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
1009 int add_irreducible_flag;
1010 basic_block place_after;
1011 bitmap bbs_to_scale = NULL;
1014 gcc_assert (e->dest == loop->header);
1015 gcc_assert (ndupl > 0);
1019 /* Orig must be edge out of the loop. */
1020 gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
1021 gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
1024 n = loop->num_nodes;
1025 bbs = get_loop_body_in_dom_order (loop);
1026 gcc_assert (bbs[0] == loop->header);
1027 gcc_assert (bbs[n - 1] == loop->latch);
1029 /* Check whether duplication is possible. */
1030 if (!can_copy_bbs_p (bbs, loop->num_nodes))
1035 new_bbs = XNEWVEC (basic_block, loop->num_nodes);
1037 /* In case we are doing loop peeling and the loop is in the middle of
1038 irreducible region, the peeled copies will be inside it too. */
1039 add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
1040 gcc_assert (!is_latch || !add_irreducible_flag);
1042 /* Find edge from latch. */
1043 latch_edge = loop_latch_edge (loop);
1045 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1047 /* Calculate coefficients by that we have to scale frequencies
1048 of duplicated loop bodies. */
1049 freq_in = header->frequency;
1050 freq_le = EDGE_FREQUENCY (latch_edge);
1053 if (freq_in < freq_le)
1055 freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
1056 if (freq_out_orig > freq_in - freq_le)
1057 freq_out_orig = freq_in - freq_le;
1058 prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
1059 prob_pass_wont_exit =
1060 RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
1063 && REG_BR_PROB_BASE - orig->probability != 0)
1065 /* The blocks that are dominated by a removed exit edge ORIG have
1066 frequencies scaled by this. */
1067 scale_after_exit = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE,
1068 REG_BR_PROB_BASE - orig->probability);
1069 bbs_to_scale = BITMAP_ALLOC (NULL);
1070 for (i = 0; i < n; i++)
1072 if (bbs[i] != orig->src
1073 && dominated_by_p (CDI_DOMINATORS, bbs[i], orig->src))
1074 bitmap_set_bit (bbs_to_scale, i);
1078 scale_step = XNEWVEC (int, ndupl);
1080 for (i = 1; i <= ndupl; i++)
1081 scale_step[i - 1] = TEST_BIT (wont_exit, i)
1082 ? prob_pass_wont_exit
1085 /* Complete peeling is special as the probability of exit in last
1087 if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
1089 int wanted_freq = EDGE_FREQUENCY (e);
1091 if (wanted_freq > freq_in)
1092 wanted_freq = freq_in;
1094 gcc_assert (!is_latch);
1095 /* First copy has frequency of incoming edge. Each subsequent
1096 frequency should be reduced by prob_pass_wont_exit. Caller
1097 should've managed the flags so all except for original loop
1098 has won't exist set. */
1099 scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
1100 /* Now simulate the duplication adjustments and compute header
1101 frequency of the last copy. */
1102 for (i = 0; i < ndupl; i++)
1103 wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE);
1104 scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
1108 prob_pass_main = TEST_BIT (wont_exit, 0)
1109 ? prob_pass_wont_exit
1112 scale_main = REG_BR_PROB_BASE;
1113 for (i = 0; i < ndupl; i++)
1116 p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
1118 scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
1119 scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
1123 scale_main = REG_BR_PROB_BASE;
1124 for (i = 0; i < ndupl; i++)
1125 scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
1126 scale_act = REG_BR_PROB_BASE - prob_pass_thru;
1128 for (i = 0; i < ndupl; i++)
1129 gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
1130 gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
1131 && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE);
1134 /* Loop the new bbs will belong to. */
1135 target = e->src->loop_father;
1137 /* Original loops. */
1139 for (aloop = loop->inner; aloop; aloop = aloop->next)
1141 orig_loops = XCNEWVEC (struct loop *, n_orig_loops);
1142 for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
1143 orig_loops[i] = aloop;
1145 set_loop_copy (loop, target);
1147 first_active = XNEWVEC (basic_block, n);
1150 memcpy (first_active, bbs, n * sizeof (basic_block));
1151 first_active_latch = latch;
1154 spec_edges[SE_ORIG] = orig;
1155 spec_edges[SE_LATCH] = latch_edge;
1157 place_after = e->src;
1158 for (j = 0; j < ndupl; j++)
1161 copy_loops_to (orig_loops, n_orig_loops, target);
1164 copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
1166 place_after = new_spec_edges[SE_LATCH]->src;
1168 if (flags & DLTHE_RECORD_COPY_NUMBER)
1169 for (i = 0; i < n; i++)
1171 gcc_assert (!new_bbs[i]->aux);
1172 new_bbs[i]->aux = (void *)(size_t)(j + 1);
1175 /* Note whether the blocks and edges belong to an irreducible loop. */
1176 if (add_irreducible_flag)
1178 for (i = 0; i < n; i++)
1179 new_bbs[i]->flags |= BB_DUPLICATED;
1180 for (i = 0; i < n; i++)
1183 new_bb = new_bbs[i];
1184 if (new_bb->loop_father == target)
1185 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1187 FOR_EACH_EDGE (ae, ei, new_bb->succs)
1188 if ((ae->dest->flags & BB_DUPLICATED)
1189 && (ae->src->loop_father == target
1190 || ae->dest->loop_father == target))
1191 ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1193 for (i = 0; i < n; i++)
1194 new_bbs[i]->flags &= ~BB_DUPLICATED;
1197 /* Redirect the special edges. */
1200 redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1201 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1203 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
1204 latch = loop->latch = new_bbs[n - 1];
1205 e = latch_edge = new_spec_edges[SE_LATCH];
1209 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1211 redirect_edge_and_branch_force (e, new_bbs[0]);
1212 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
1213 e = new_spec_edges[SE_LATCH];
1216 /* Record exit edge in this copy. */
1217 if (orig && TEST_BIT (wont_exit, j + 1))
1220 VEC_safe_push (edge, heap, *to_remove, new_spec_edges[SE_ORIG]);
1221 set_zero_probability (new_spec_edges[SE_ORIG]);
1223 /* Scale the frequencies of the blocks dominated by the exit. */
1226 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1228 scale_bbs_frequencies_int (new_bbs + i, 1, scale_after_exit,
1234 /* Record the first copy in the control flow order if it is not
1235 the original loop (i.e. in case of peeling). */
1236 if (!first_active_latch)
1238 memcpy (first_active, new_bbs, n * sizeof (basic_block));
1239 first_active_latch = new_bbs[n - 1];
1242 /* Set counts and frequencies. */
1243 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1245 scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1246 scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
1252 /* Record the exit edge in the original loop body, and update the frequencies. */
1253 if (orig && TEST_BIT (wont_exit, 0))
1256 VEC_safe_push (edge, heap, *to_remove, orig);
1257 set_zero_probability (orig);
1259 /* Scale the frequencies of the blocks dominated by the exit. */
1262 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1264 scale_bbs_frequencies_int (bbs + i, 1, scale_after_exit,
1270 /* Update the original loop. */
1272 set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1273 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1275 scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
1279 /* Update dominators of outer blocks if affected. */
1280 for (i = 0; i < n; i++)
1282 basic_block dominated, dom_bb;
1283 VEC (basic_block, heap) *dom_bbs;
1289 dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
1290 FOR_EACH_VEC_ELT (basic_block, dom_bbs, j, dominated)
1292 if (flow_bb_inside_loop_p (loop, dominated))
1294 dom_bb = nearest_common_dominator (
1295 CDI_DOMINATORS, first_active[i], first_active_latch);
1296 set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1298 VEC_free (basic_block, heap, dom_bbs);
1300 free (first_active);
1303 BITMAP_FREE (bbs_to_scale);
1308 /* A callback for make_forwarder block, to redirect all edges except for
1309 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1310 whether to redirect it. */
1314 mfb_keep_just (edge e)
1316 return e != mfb_kj_edge;
1319 /* True when a candidate preheader BLOCK has predecessors from LOOP. */
1322 has_preds_from_loop (basic_block block, struct loop *loop)
1327 FOR_EACH_EDGE (e, ei, block->preds)
1328 if (e->src->loop_father == loop)
1333 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1334 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1335 entry; otherwise we also force preheader block to have only one successor.
1336 When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
1337 to be a fallthru predecessor to the loop header and to have only
1338 predecessors from outside of the loop.
1339 The function also updates dominators. */
1342 create_preheader (struct loop *loop, int flags)
1348 bool latch_edge_was_fallthru;
1349 edge one_succ_pred = NULL, single_entry = NULL;
1352 FOR_EACH_EDGE (e, ei, loop->header->preds)
1354 if (e->src == loop->latch)
1356 irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1359 if (single_succ_p (e->src))
1362 gcc_assert (nentry);
1365 bool need_forwarder_block = false;
1367 /* We do not allow entry block to be the loop preheader, since we
1368 cannot emit code there. */
1369 if (single_entry->src == ENTRY_BLOCK_PTR)
1370 need_forwarder_block = true;
1373 /* If we want simple preheaders, also force the preheader to have
1374 just a single successor. */
1375 if ((flags & CP_SIMPLE_PREHEADERS)
1376 && !single_succ_p (single_entry->src))
1377 need_forwarder_block = true;
1378 /* If we want fallthru preheaders, also create forwarder block when
1379 preheader ends with a jump or has predecessors from loop. */
1380 else if ((flags & CP_FALLTHRU_PREHEADERS)
1381 && (JUMP_P (BB_END (single_entry->src))
1382 || has_preds_from_loop (single_entry->src, loop)))
1383 need_forwarder_block = true;
1385 if (! need_forwarder_block)
1389 mfb_kj_edge = loop_latch_edge (loop);
1390 latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
1391 fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL);
1392 dummy = fallthru->src;
1393 loop->header = fallthru->dest;
1395 /* Try to be clever in placing the newly created preheader. The idea is to
1396 avoid breaking any "fallthruness" relationship between blocks.
1398 The preheader was created just before the header and all incoming edges
1399 to the header were redirected to the preheader, except the latch edge.
1400 So the only problematic case is when this latch edge was a fallthru
1401 edge: it is not anymore after the preheader creation so we have broken
1402 the fallthruness. We're therefore going to look for a better place. */
1403 if (latch_edge_was_fallthru)
1408 e = EDGE_PRED (dummy, 0);
1410 move_block_after (dummy, e->src);
1415 dummy->flags |= BB_IRREDUCIBLE_LOOP;
1416 single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1420 fprintf (dump_file, "Created preheader block for loop %i\n",
1423 if (flags & CP_FALLTHRU_PREHEADERS)
1424 gcc_assert ((single_succ_edge (dummy)->flags & EDGE_FALLTHRU)
1425 && !JUMP_P (BB_END (dummy)));
1430 /* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */
1433 create_preheaders (int flags)
1441 FOR_EACH_LOOP (li, loop, 0)
1442 create_preheader (loop, flags);
1443 loops_state_set (LOOPS_HAVE_PREHEADERS);
1446 /* Forces all loop latches to have only single successor. */
1449 force_single_succ_latches (void)
1455 FOR_EACH_LOOP (li, loop, 0)
1457 if (loop->latch != loop->header && single_succ_p (loop->latch))
1460 e = find_edge (loop->latch, loop->header);
1464 loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES);
1467 /* This function is called from loop_version. It splits the entry edge
1468 of the loop we want to version, adds the versioning condition, and
1469 adjust the edges to the two versions of the loop appropriately.
1470 e is an incoming edge. Returns the basic block containing the
1473 --- edge e ---- > [second_head]
1475 Split it and insert new conditional expression and adjust edges.
1477 --- edge e ---> [cond expr] ---> [first_head]
1479 +---------> [second_head]
1481 THEN_PROB is the probability of then branch of the condition. */
1484 lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head,
1485 edge e, void *cond_expr, unsigned then_prob)
1487 basic_block new_head = NULL;
1490 gcc_assert (e->dest == second_head);
1492 /* Split edge 'e'. This will create a new basic block, where we can
1493 insert conditional expr. */
1494 new_head = split_edge (e);
1496 lv_add_condition_to_bb (first_head, second_head, new_head,
1499 /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */
1500 e = single_succ_edge (new_head);
1501 e1 = make_edge (new_head, first_head,
1502 current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0);
1503 e1->probability = then_prob;
1504 e->probability = REG_BR_PROB_BASE - then_prob;
1505 e1->count = RDIV (e->count * e1->probability, REG_BR_PROB_BASE);
1506 e->count = RDIV (e->count * e->probability, REG_BR_PROB_BASE);
1508 set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1509 set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1511 /* Adjust loop header phi nodes. */
1512 lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1517 /* Main entry point for Loop Versioning transformation.
1519 This transformation given a condition and a loop, creates
1520 -if (condition) { loop_copy1 } else { loop_copy2 },
1521 where loop_copy1 is the loop transformed in one way, and loop_copy2
1522 is the loop transformed in another way (or unchanged). 'condition'
1523 may be a run time test for things that were not resolved by static
1524 analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1526 THEN_PROB is the probability of the then edge of the if. THEN_SCALE
1527 is the ratio by that the frequencies in the original loop should
1528 be scaled. ELSE_SCALE is the ratio by that the frequencies in the
1529 new loop should be scaled.
1531 If PLACE_AFTER is true, we place the new loop after LOOP in the
1532 instruction stream, otherwise it is placed before LOOP. */
1535 loop_version (struct loop *loop,
1536 void *cond_expr, basic_block *condition_bb,
1537 unsigned then_prob, unsigned then_scale, unsigned else_scale,
1540 basic_block first_head, second_head;
1541 edge entry, latch_edge, true_edge, false_edge;
1544 basic_block cond_bb;
1546 /* Record entry and latch edges for the loop */
1547 entry = loop_preheader_edge (loop);
1548 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1549 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1551 /* Note down head of loop as first_head. */
1552 first_head = entry->dest;
1554 /* Duplicate loop. */
1555 if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, 1,
1556 NULL, NULL, NULL, 0))
1558 entry->flags |= irred_flag;
1562 /* After duplication entry edge now points to new loop head block.
1563 Note down new head as second_head. */
1564 second_head = entry->dest;
1566 /* Split loop entry edge and insert new block with cond expr. */
1567 cond_bb = lv_adjust_loop_entry_edge (first_head, second_head,
1568 entry, cond_expr, then_prob);
1570 *condition_bb = cond_bb;
1574 entry->flags |= irred_flag;
1578 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1580 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1581 nloop = loopify (latch_edge,
1582 single_pred_edge (get_bb_copy (loop->header)),
1583 cond_bb, true_edge, false_edge,
1584 false /* Do not redirect all edges. */,
1585 then_scale, else_scale);
1587 /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1588 lv_flush_pending_stmts (latch_edge);
1590 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
1591 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1592 lv_flush_pending_stmts (false_edge);
1593 /* Adjust irreducible flag. */
1596 cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
1597 loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1598 loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1599 single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
1604 basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
1607 after = loop->latch;
1609 for (i = 0; i < nloop->num_nodes; i++)
1611 move_block_after (bbs[i], after);
1617 /* At this point condition_bb is loop preheader with two successors,
1618 first_head and second_head. Make sure that loop preheader has only
1620 split_edge (loop_preheader_edge (loop));
1621 split_edge (loop_preheader_edge (nloop));
1626 /* The structure of loops might have changed. Some loops might get removed
1627 (and their headers and latches were set to NULL), loop exists might get
1628 removed (thus the loop nesting may be wrong), and some blocks and edges
1629 were changed (so the information about bb --> loop mapping does not have
1630 to be correct). But still for the remaining loops the header dominates
1631 the latch, and loops did not get new subloops (new loops might possibly
1632 get created, but we are not interested in them). Fix up the mess.
1634 If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1638 fix_loop_structure (bitmap changed_bbs)
1641 struct loop *loop, *ploop;
1643 bool record_exits = false;
1644 struct loop **superloop = XNEWVEC (struct loop *, number_of_loops ());
1646 /* Remove the old bb -> loop mapping. Remember the depth of the blocks in
1647 the loop hierarchy, so that we can recognize blocks whose loop nesting
1648 relationship has changed. */
1652 bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
1653 bb->loop_father = current_loops->tree_root;
1656 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1658 release_recorded_exits ();
1659 record_exits = true;
1662 /* Remove the dead loops from structures. We start from the innermost
1663 loops, so that when we remove the loops, we know that the loops inside
1664 are preserved, and do not waste time relinking loops that will be
1666 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1673 ploop = loop->inner;
1674 flow_loop_tree_node_remove (ploop);
1675 flow_loop_tree_node_add (loop_outer (loop), ploop);
1678 /* Remove the loop and free its data. */
1682 /* Rescan the bodies of loops, starting from the outermost ones. We assume
1683 that no optimization interchanges the order of the loops, i.e., it cannot
1684 happen that L1 was superloop of L2 before and it is subloop of L2 now
1685 (without explicitly updating loop information). At the same time, we also
1686 determine the new loop structure. */
1687 current_loops->tree_root->num_nodes = n_basic_blocks;
1688 FOR_EACH_LOOP (li, loop, 0)
1690 superloop[loop->num] = loop->header->loop_father;
1691 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
1694 /* Now fix the loop nesting. */
1695 FOR_EACH_LOOP (li, loop, 0)
1697 ploop = superloop[loop->num];
1698 if (ploop != loop_outer (loop))
1700 flow_loop_tree_node_remove (loop);
1701 flow_loop_tree_node_add (ploop, loop);
1706 /* Mark the blocks whose loop has changed. */
1711 if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
1712 bitmap_set_bit (changed_bbs, bb->index);
1718 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
1719 create_preheaders (CP_SIMPLE_PREHEADERS);
1721 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1722 force_single_succ_latches ();
1724 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1725 mark_irreducible_loops ();
1728 record_loop_exits ();
1730 loops_state_clear (LOOPS_NEED_FIXUP);
1732 #ifdef ENABLE_CHECKING
1733 verify_loop_structure ();