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"
33 #include "tree-flow.h"
35 static void copy_loops_to (struct loop **, int,
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 *);
44 static void unloop (struct loop *, bool *);
46 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
48 /* Checks whether basic block BB is dominated by DATA. */
50 rpe_enum_p (const_basic_block bb, const void *data)
52 return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data);
55 /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
58 remove_bbs (basic_block *bbs, int nbbs)
62 for (i = 0; i < nbbs; i++)
63 delete_basic_block (bbs[i]);
66 /* Find path -- i.e. the basic blocks dominated by edge E and put them
67 into array BBS, that will be allocated large enough to contain them.
68 E->dest must have exactly one predecessor for this to work (it is
69 easy to achieve and we do not put it here because we do not want to
70 alter anything by this function). The number of basic blocks in the
73 find_path (edge e, basic_block **bbs)
75 gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
77 /* Find bbs in the path. */
78 *bbs = XCNEWVEC (basic_block, n_basic_blocks);
79 return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
80 n_basic_blocks, e->dest);
83 /* Fix placement of basic block BB inside loop hierarchy --
84 Let L be a loop to that BB belongs. Then every successor of BB must either
85 1) belong to some superloop of loop L, or
86 2) be a header of loop K such that K->outer is superloop of L
87 Returns true if we had to move BB into other loop to enforce this condition,
88 false if the placement of BB was already correct (provided that placements
89 of its successors are correct). */
91 fix_bb_placement (basic_block bb)
95 struct loop *loop = current_loops->tree_root, *act;
97 FOR_EACH_EDGE (e, ei, bb->succs)
99 if (e->dest == EXIT_BLOCK_PTR)
102 act = e->dest->loop_father;
103 if (act->header == e->dest)
104 act = loop_outer (act);
106 if (flow_loop_nested_p (loop, act))
110 if (loop == bb->loop_father)
113 remove_bb_from_loops (bb);
114 add_bb_to_loop (bb, loop);
119 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
120 of LOOP to that leads at least one exit edge of LOOP, and set it
121 as the immediate superloop of LOOP. Return true if the immediate superloop
125 fix_loop_placement (struct loop *loop)
129 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
130 struct loop *father = current_loops->tree_root, *act;
133 FOR_EACH_VEC_ELT (edge, exits, i, e)
135 act = find_common_loop (loop, e->dest->loop_father);
136 if (flow_loop_nested_p (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 (edge, exits, i, e)
150 rescan_loop_exit (e, false, false);
155 VEC_free (edge, heap, exits);
159 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
160 enforce condition condition stated in description of fix_bb_placement. We
161 start from basic block FROM that had some of its successors removed, so that
162 his placement no longer has to be correct, and iteratively fix placement of
163 its predecessors that may change if placement of FROM changed. Also fix
164 placement of subloops of FROM->loop_father, that might also be altered due
165 to this change; the condition for them is similar, except that instead of
166 successors we consider edges coming out of the loops.
168 If the changes may invalidate the information about irreducible regions,
169 IRRED_INVALIDATED is set to true. */
172 fix_bb_placements (basic_block from,
173 bool *irred_invalidated)
176 basic_block *queue, *qtop, *qbeg, *qend;
177 struct loop *base_loop, *target_loop;
180 /* We pass through blocks back-reachable from FROM, testing whether some
181 of their successors moved to outer loop. It may be necessary to
182 iterate several times, but it is finite, as we stop unless we move
183 the basic block up the loop structure. The whole story is a bit
184 more complicated due to presence of subloops, those are moved using
185 fix_loop_placement. */
187 base_loop = from->loop_father;
188 if (base_loop == current_loops->tree_root)
191 in_queue = sbitmap_alloc (last_basic_block);
192 sbitmap_zero (in_queue);
193 SET_BIT (in_queue, from->index);
194 /* Prevent us from going out of the base_loop. */
195 SET_BIT (in_queue, base_loop->header->index);
197 queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);
198 qtop = queue + base_loop->num_nodes + 1;
210 RESET_BIT (in_queue, from->index);
212 if (from->loop_father->header == from)
214 /* Subloop header, maybe move the loop upward. */
215 if (!fix_loop_placement (from->loop_father))
217 target_loop = loop_outer (from->loop_father);
221 /* Ordinary basic block. */
222 if (!fix_bb_placement (from))
224 target_loop = from->loop_father;
227 FOR_EACH_EDGE (e, ei, from->succs)
229 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
230 *irred_invalidated = true;
233 /* Something has changed, insert predecessors into queue. */
234 FOR_EACH_EDGE (e, ei, from->preds)
236 basic_block pred = e->src;
239 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
240 *irred_invalidated = true;
242 if (TEST_BIT (in_queue, pred->index))
245 /* If it is subloop, then it either was not moved, or
246 the path up the loop tree from base_loop do not contain
248 nca = find_common_loop (pred->loop_father, base_loop);
249 if (pred->loop_father != base_loop
251 || nca != pred->loop_father))
252 pred = pred->loop_father->header;
253 else if (!flow_loop_nested_p (target_loop, pred->loop_father))
255 /* If PRED is already higher in the loop hierarchy than the
256 TARGET_LOOP to that we moved FROM, the change of the position
257 of FROM does not affect the position of PRED, so there is no
258 point in processing it. */
262 if (TEST_BIT (in_queue, pred->index))
265 /* Schedule the basic block. */
270 SET_BIT (in_queue, pred->index);
277 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
278 and update loop structures and dominators. Return true if we were able
279 to remove the path, false otherwise (and nothing is affected then). */
284 basic_block *rem_bbs, *bord_bbs, from, bb;
285 VEC (basic_block, heap) *dom_bbs;
286 int i, nrem, n_bord_bbs;
288 bool irred_invalidated = false;
290 if (!can_remove_branch_p (e))
293 /* Keep track of whether we need to update information about irreducible
294 regions. This is the case if the removed area is a part of the
295 irreducible region, or if the set of basic blocks that belong to a loop
296 that is inside an irreducible region is changed, or if such a loop is
298 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
299 irred_invalidated = true;
301 /* We need to check whether basic blocks are dominated by the edge
302 e, but we only have basic block dominators. This is easy to
303 fix -- when e->dest has exactly one predecessor, this corresponds
304 to blocks dominated by e->dest, if not, split the edge. */
305 if (!single_pred_p (e->dest))
306 e = single_pred_edge (split_edge (e));
308 /* It may happen that by removing path we remove one or more loops
309 we belong to. In this case first unloop the loops, then proceed
310 normally. We may assume that e->dest is not a header of any loop,
311 as it now has exactly one predecessor. */
312 while (loop_outer (e->src->loop_father)
313 && dominated_by_p (CDI_DOMINATORS,
314 e->src->loop_father->latch, e->dest))
315 unloop (e->src->loop_father, &irred_invalidated);
317 /* Identify the path. */
318 nrem = find_path (e, &rem_bbs);
321 bord_bbs = XCNEWVEC (basic_block, n_basic_blocks);
322 seen = sbitmap_alloc (last_basic_block);
325 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
326 for (i = 0; i < nrem; i++)
327 SET_BIT (seen, rem_bbs[i]->index);
328 for (i = 0; i < nrem; i++)
332 FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
333 if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
335 SET_BIT (seen, ae->dest->index);
336 bord_bbs[n_bord_bbs++] = ae->dest;
338 if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
339 irred_invalidated = true;
343 /* Remove the path. */
348 /* Cancel loops contained in the path. */
349 for (i = 0; i < nrem; i++)
350 if (rem_bbs[i]->loop_father->header == rem_bbs[i])
351 cancel_loop_tree (rem_bbs[i]->loop_father);
353 remove_bbs (rem_bbs, nrem);
356 /* Find blocks whose dominators may be affected. */
358 for (i = 0; i < n_bord_bbs; i++)
362 bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
363 if (TEST_BIT (seen, bb->index))
365 SET_BIT (seen, bb->index);
367 for (ldom = first_dom_son (CDI_DOMINATORS, bb);
369 ldom = next_dom_son (CDI_DOMINATORS, ldom))
370 if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
371 VEC_safe_push (basic_block, heap, dom_bbs, ldom);
376 /* Recount dominators. */
377 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);
378 VEC_free (basic_block, heap, dom_bbs);
381 /* Fix placements of basic blocks inside loops and the placement of
382 loops in the loop tree. */
383 fix_bb_placements (from, &irred_invalidated);
384 fix_loop_placements (from->loop_father, &irred_invalidated);
386 if (irred_invalidated
387 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
388 mark_irreducible_loops ();
393 /* Creates place for a new LOOP in loops structure. */
396 place_new_loop (struct loop *loop)
398 loop->num = number_of_loops ();
399 VEC_safe_push (loop_p, gc, current_loops->larray, loop);
402 /* Given LOOP structure with filled header and latch, find the body of the
403 corresponding loop and add it to loops tree. Insert the LOOP as a son of
407 add_loop (struct loop *loop, struct loop *outer)
411 struct loop *subloop;
415 /* Add it to loop structure. */
416 place_new_loop (loop);
417 flow_loop_tree_node_add (outer, loop);
419 /* Find its nodes. */
420 bbs = XNEWVEC (basic_block, n_basic_blocks);
421 n = get_loop_body_with_size (loop, bbs, n_basic_blocks);
423 for (i = 0; i < n; i++)
425 if (bbs[i]->loop_father == outer)
427 remove_bb_from_loops (bbs[i]);
428 add_bb_to_loop (bbs[i], loop);
434 /* If we find a direct subloop of OUTER, move it to LOOP. */
435 subloop = bbs[i]->loop_father;
436 if (loop_outer (subloop) == outer
437 && subloop->header == bbs[i])
439 flow_loop_tree_node_remove (subloop);
440 flow_loop_tree_node_add (loop, subloop);
444 /* Update the information about loop exit edges. */
445 for (i = 0; i < n; i++)
447 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
449 rescan_loop_exit (e, false, false);
456 /* Multiply all frequencies in LOOP by NUM/DEN. */
458 scale_loop_frequencies (struct loop *loop, int num, int den)
462 bbs = get_loop_body (loop);
463 scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
467 /* Recompute dominance information for basic blocks outside LOOP. */
470 update_dominators_in_loop (struct loop *loop)
472 VEC (basic_block, heap) *dom_bbs = NULL;
477 seen = sbitmap_alloc (last_basic_block);
479 body = get_loop_body (loop);
481 for (i = 0; i < loop->num_nodes; i++)
482 SET_BIT (seen, body[i]->index);
484 for (i = 0; i < loop->num_nodes; i++)
488 for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
490 ldom = next_dom_son (CDI_DOMINATORS, ldom))
491 if (!TEST_BIT (seen, ldom->index))
493 SET_BIT (seen, ldom->index);
494 VEC_safe_push (basic_block, heap, dom_bbs, ldom);
498 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
501 VEC_free (basic_block, heap, dom_bbs);
504 /* Creates an if region as shown above. CONDITION is used to create
508 | ------------- -------------
509 | | pred_bb | | pred_bb |
510 | ------------- -------------
514 | | ====> -------------
519 | ------------- e_false / \ e_true
521 | ------------- ----------- -----------
522 | | false_bb | | true_bb |
523 | ----------- -----------
530 | | exit_edge (result)
539 create_empty_if_region_on_edge (edge entry_edge, tree condition)
542 basic_block cond_bb, true_bb, false_bb, join_bb;
543 edge e_true, e_false, exit_edge;
546 gimple_stmt_iterator gsi;
548 cond_bb = split_edge (entry_edge);
550 /* Insert condition in cond_bb. */
551 gsi = gsi_last_bb (cond_bb);
553 force_gimple_operand_gsi (&gsi, condition, true, NULL,
554 false, GSI_NEW_STMT);
555 cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);
556 gsi = gsi_last_bb (cond_bb);
557 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
559 join_bb = split_edge (single_succ_edge (cond_bb));
561 e_true = single_succ_edge (cond_bb);
562 true_bb = split_edge (e_true);
564 e_false = make_edge (cond_bb, join_bb, 0);
565 false_bb = split_edge (e_false);
567 e_true->flags &= ~EDGE_FALLTHRU;
568 e_true->flags |= EDGE_TRUE_VALUE;
569 e_false->flags &= ~EDGE_FALLTHRU;
570 e_false->flags |= EDGE_FALSE_VALUE;
572 set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);
573 set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);
574 set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);
575 set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
577 exit_edge = single_succ_edge (join_bb);
579 if (single_pred_p (exit_edge->dest))
580 set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);
585 /* create_empty_loop_on_edge
587 | - pred_bb - ------ pred_bb ------
588 | | | | iv0 = initial_value |
589 | -----|----- ---------|-----------
590 | | ______ | entry_edge
592 | | ====> | -V---V- loop_header -------------
593 | V | | iv_before = phi (iv0, iv_after) |
594 | - succ_bb - | ---|-----------------------------
596 | ----------- | ---V--- loop_body ---------------
597 | | | iv_after = iv_before + stride |
598 | | | if (iv_before < upper_bound) |
599 | | ---|--------------\--------------
602 | | - loop_latch - V- succ_bb -
604 | | /------------- -----------
607 Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
608 that is used before the increment of IV. IV_BEFORE should be used for
609 adding code to the body that uses the IV. OUTER is the outer loop in
610 which the new loop should be inserted.
612 Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
613 inserted on the loop entry edge. This implies that this function
614 should be used only when the UPPER_BOUND expression is a loop
618 create_empty_loop_on_edge (edge entry_edge,
620 tree stride, tree upper_bound,
626 basic_block loop_header, loop_latch, succ_bb, pred_bb;
628 gimple_stmt_iterator gsi;
635 gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
637 /* Create header, latch and wire up the loop. */
638 pred_bb = entry_edge->src;
639 loop_header = split_edge (entry_edge);
640 loop_latch = split_edge (single_succ_edge (loop_header));
641 succ_bb = single_succ (loop_latch);
642 make_edge (loop_header, succ_bb, 0);
643 redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);
645 /* Set immediate dominator information. */
646 set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);
647 set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);
648 set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);
650 /* Initialize a loop structure and put it in a loop hierarchy. */
651 loop = alloc_loop ();
652 loop->header = loop_header;
653 loop->latch = loop_latch;
654 add_loop (loop, outer);
656 /* TODO: Fix frequencies and counts. */
657 prob = REG_BR_PROB_BASE / 2;
659 scale_loop_frequencies (loop, REG_BR_PROB_BASE - prob, REG_BR_PROB_BASE);
661 /* Update dominators. */
662 update_dominators_in_loop (loop);
664 /* Modify edge flags. */
665 exit_e = single_exit (loop);
666 exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
667 single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
669 /* Construct IV code in loop. */
670 initial_value = force_gimple_operand (initial_value, &stmts, true, iv);
673 gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
674 gsi_commit_edge_inserts ();
677 upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL);
680 gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
681 gsi_commit_edge_inserts ();
684 gsi = gsi_last_bb (loop_header);
685 create_iv (initial_value, stride, iv, loop, &gsi, false,
686 iv_before, iv_after);
688 /* Insert loop exit condition. */
689 cond_expr = gimple_build_cond
690 (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE);
692 exit_test = gimple_cond_lhs (cond_expr);
693 exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
694 false, GSI_NEW_STMT);
695 gimple_cond_set_lhs (cond_expr, exit_test);
696 gsi = gsi_last_bb (exit_e->src);
697 gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT);
699 split_block_after_labels (loop_header);
704 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
705 latch to header and update loop tree and dominators
706 accordingly. Everything between them plus LATCH_EDGE destination must
707 be dominated by HEADER_EDGE destination, and back-reachable from
708 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
709 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
710 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
711 Returns the newly created loop. Frequencies and counts in the new loop
712 are scaled by FALSE_SCALE and in the old one by TRUE_SCALE. */
715 loopify (edge latch_edge, edge header_edge,
716 basic_block switch_bb, edge true_edge, edge false_edge,
717 bool redirect_all_edges, unsigned true_scale, unsigned false_scale)
719 basic_block succ_bb = latch_edge->dest;
720 basic_block pred_bb = header_edge->src;
721 struct loop *loop = alloc_loop ();
722 struct loop *outer = loop_outer (succ_bb->loop_father);
728 loop->header = header_edge->dest;
729 loop->latch = latch_edge->src;
731 freq = EDGE_FREQUENCY (header_edge);
732 cnt = header_edge->count;
734 /* Redirect edges. */
735 loop_redirect_edge (latch_edge, loop->header);
736 loop_redirect_edge (true_edge, succ_bb);
738 /* During loop versioning, one of the switch_bb edge is already properly
739 set. Do not redirect it again unless redirect_all_edges is true. */
740 if (redirect_all_edges)
742 loop_redirect_edge (header_edge, switch_bb);
743 loop_redirect_edge (false_edge, loop->header);
745 /* Update dominators. */
746 set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
747 set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
750 set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
752 /* Compute new loop. */
753 add_loop (loop, outer);
755 /* Add switch_bb to appropriate loop. */
756 if (switch_bb->loop_father)
757 remove_bb_from_loops (switch_bb);
758 add_bb_to_loop (switch_bb, outer);
760 /* Fix frequencies. */
761 if (redirect_all_edges)
763 switch_bb->frequency = freq;
764 switch_bb->count = cnt;
765 FOR_EACH_EDGE (e, ei, switch_bb->succs)
767 e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
770 scale_loop_frequencies (loop, false_scale, REG_BR_PROB_BASE);
771 scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE);
772 update_dominators_in_loop (loop);
777 /* Remove the latch edge of a LOOP and update loops to indicate that
778 the LOOP was removed. After this function, original loop latch will
779 have no successor, which caller is expected to fix somehow.
781 If this may cause the information about irreducible regions to become
782 invalid, IRRED_INVALIDATED is set to true. */
785 unloop (struct loop *loop, bool *irred_invalidated)
790 basic_block latch = loop->latch;
793 if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
794 *irred_invalidated = true;
796 /* This is relatively straightforward. The dominators are unchanged, as
797 loop header dominates loop latch, so the only thing we have to care of
798 is the placement of loops and basic blocks inside the loop tree. We
799 move them all to the loop->outer, and then let fix_bb_placements do
802 body = get_loop_body (loop);
804 for (i = 0; i < n; i++)
805 if (body[i]->loop_father == loop)
807 remove_bb_from_loops (body[i]);
808 add_bb_to_loop (body[i], loop_outer (loop));
815 flow_loop_tree_node_remove (ploop);
816 flow_loop_tree_node_add (loop_outer (loop), ploop);
819 /* Remove the loop and free its data. */
822 remove_edge (single_succ_edge (latch));
824 /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
825 there is an irreducible region inside the cancelled loop, the flags will
827 fix_bb_placements (latch, &dummy);
830 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
831 condition stated in description of fix_loop_placement holds for them.
832 It is used in case when we removed some edges coming out of LOOP, which
833 may cause the right placement of LOOP inside loop tree to change.
835 IRRED_INVALIDATED is set to true if a change in the loop structures might
836 invalidate the information about irreducible regions. */
839 fix_loop_placements (struct loop *loop, bool *irred_invalidated)
843 while (loop_outer (loop))
845 outer = loop_outer (loop);
846 if (!fix_loop_placement (loop))
849 /* Changing the placement of a loop in the loop tree may alter the
850 validity of condition 2) of the description of fix_bb_placement
851 for its preheader, because the successor is the header and belongs
852 to the loop. So call fix_bb_placements to fix up the placement
853 of the preheader and (possibly) of its predecessors. */
854 fix_bb_placements (loop_preheader_edge (loop)->src,
860 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
861 created loop into loops structure. */
863 duplicate_loop (struct loop *loop, struct loop *target)
866 cloop = alloc_loop ();
867 place_new_loop (cloop);
869 /* Mark the new loop as copy of LOOP. */
870 set_loop_copy (loop, cloop);
872 /* Add it to target. */
873 flow_loop_tree_node_add (target, cloop);
878 /* Copies structure of subloops of LOOP into TARGET loop, placing
879 newly created loops into loop tree. */
881 duplicate_subloops (struct loop *loop, struct loop *target)
883 struct loop *aloop, *cloop;
885 for (aloop = loop->inner; aloop; aloop = aloop->next)
887 cloop = duplicate_loop (aloop, target);
888 duplicate_subloops (aloop, cloop);
892 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
893 into TARGET loop, placing newly created loops into loop tree. */
895 copy_loops_to (struct loop **copied_loops, int n, struct loop *target)
900 for (i = 0; i < n; i++)
902 aloop = duplicate_loop (copied_loops[i], target);
903 duplicate_subloops (copied_loops[i], aloop);
907 /* Redirects edge E to basic block DEST. */
909 loop_redirect_edge (edge e, basic_block dest)
914 redirect_edge_and_branch_force (e, dest);
917 /* Check whether LOOP's body can be duplicated. */
919 can_duplicate_loop_p (const struct loop *loop)
922 basic_block *bbs = get_loop_body (loop);
924 ret = can_copy_bbs_p (bbs, loop->num_nodes);
930 /* Sets probability and count of edge E to zero. The probability and count
931 is redistributed evenly to the remaining edges coming from E->src. */
934 set_zero_probability (edge e)
936 basic_block bb = e->src;
938 edge ae, last = NULL;
939 unsigned n = EDGE_COUNT (bb->succs);
940 gcov_type cnt = e->count, cnt1;
941 unsigned prob = e->probability, prob1;
944 cnt1 = cnt / (n - 1);
945 prob1 = prob / (n - 1);
947 FOR_EACH_EDGE (ae, ei, bb->succs)
952 ae->probability += prob1;
957 /* Move the rest to one of the edges. */
958 last->probability += prob % (n - 1);
959 last->count += cnt % (n - 1);
965 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
966 loop structure and dominators. E's destination must be LOOP header for
967 this to work, i.e. it must be entry or latch edge of this loop; these are
968 unique, as the loops must have preheaders for this function to work
969 correctly (in case E is latch, the function unrolls the loop, if E is entry
970 edge, it peels the loop). Store edges created by copying ORIG edge from
971 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
972 original LOOP body, the other copies are numbered in order given by control
973 flow through them) into TO_REMOVE array. Returns false if duplication is
977 duplicate_loop_to_header_edge (struct loop *loop, edge e,
978 unsigned int ndupl, sbitmap wont_exit,
979 edge orig, VEC (edge, heap) **to_remove,
982 struct loop *target, *aloop;
983 struct loop **orig_loops;
984 unsigned n_orig_loops;
985 basic_block header = loop->header, latch = loop->latch;
986 basic_block *new_bbs, *bbs, *first_active;
987 basic_block new_bb, bb, first_active_latch = NULL;
989 edge spec_edges[2], new_spec_edges[2];
993 int is_latch = (latch == e->src);
994 int scale_act = 0, *scale_step = NULL, scale_main = 0;
995 int scale_after_exit = 0;
996 int p, freq_in, freq_le, freq_out_orig;
997 int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
998 int add_irreducible_flag;
999 basic_block place_after;
1000 bitmap bbs_to_scale = NULL;
1003 gcc_assert (e->dest == loop->header);
1004 gcc_assert (ndupl > 0);
1008 /* Orig must be edge out of the loop. */
1009 gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
1010 gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
1013 n = loop->num_nodes;
1014 bbs = get_loop_body_in_dom_order (loop);
1015 gcc_assert (bbs[0] == loop->header);
1016 gcc_assert (bbs[n - 1] == loop->latch);
1018 /* Check whether duplication is possible. */
1019 if (!can_copy_bbs_p (bbs, loop->num_nodes))
1024 new_bbs = XNEWVEC (basic_block, loop->num_nodes);
1026 /* In case we are doing loop peeling and the loop is in the middle of
1027 irreducible region, the peeled copies will be inside it too. */
1028 add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
1029 gcc_assert (!is_latch || !add_irreducible_flag);
1031 /* Find edge from latch. */
1032 latch_edge = loop_latch_edge (loop);
1034 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1036 /* Calculate coefficients by that we have to scale frequencies
1037 of duplicated loop bodies. */
1038 freq_in = header->frequency;
1039 freq_le = EDGE_FREQUENCY (latch_edge);
1042 if (freq_in < freq_le)
1044 freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
1045 if (freq_out_orig > freq_in - freq_le)
1046 freq_out_orig = freq_in - freq_le;
1047 prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
1048 prob_pass_wont_exit =
1049 RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
1052 && REG_BR_PROB_BASE - orig->probability != 0)
1054 /* The blocks that are dominated by a removed exit edge ORIG have
1055 frequencies scaled by this. */
1056 scale_after_exit = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE,
1057 REG_BR_PROB_BASE - orig->probability);
1058 bbs_to_scale = BITMAP_ALLOC (NULL);
1059 for (i = 0; i < n; i++)
1061 if (bbs[i] != orig->src
1062 && dominated_by_p (CDI_DOMINATORS, bbs[i], orig->src))
1063 bitmap_set_bit (bbs_to_scale, i);
1067 scale_step = XNEWVEC (int, ndupl);
1069 for (i = 1; i <= ndupl; i++)
1070 scale_step[i - 1] = TEST_BIT (wont_exit, i)
1071 ? prob_pass_wont_exit
1074 /* Complete peeling is special as the probability of exit in last
1076 if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
1078 int wanted_freq = EDGE_FREQUENCY (e);
1080 if (wanted_freq > freq_in)
1081 wanted_freq = freq_in;
1083 gcc_assert (!is_latch);
1084 /* First copy has frequency of incoming edge. Each subsequent
1085 frequency should be reduced by prob_pass_wont_exit. Caller
1086 should've managed the flags so all except for original loop
1087 has won't exist set. */
1088 scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
1089 /* Now simulate the duplication adjustments and compute header
1090 frequency of the last copy. */
1091 for (i = 0; i < ndupl; i++)
1092 wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE);
1093 scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
1097 prob_pass_main = TEST_BIT (wont_exit, 0)
1098 ? prob_pass_wont_exit
1101 scale_main = REG_BR_PROB_BASE;
1102 for (i = 0; i < ndupl; i++)
1105 p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
1107 scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
1108 scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
1112 scale_main = REG_BR_PROB_BASE;
1113 for (i = 0; i < ndupl; i++)
1114 scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
1115 scale_act = REG_BR_PROB_BASE - prob_pass_thru;
1117 for (i = 0; i < ndupl; i++)
1118 gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
1119 gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
1120 && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE);
1123 /* Loop the new bbs will belong to. */
1124 target = e->src->loop_father;
1126 /* Original loops. */
1128 for (aloop = loop->inner; aloop; aloop = aloop->next)
1130 orig_loops = XCNEWVEC (struct loop *, n_orig_loops);
1131 for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
1132 orig_loops[i] = aloop;
1134 set_loop_copy (loop, target);
1136 first_active = XNEWVEC (basic_block, n);
1139 memcpy (first_active, bbs, n * sizeof (basic_block));
1140 first_active_latch = latch;
1143 spec_edges[SE_ORIG] = orig;
1144 spec_edges[SE_LATCH] = latch_edge;
1146 place_after = e->src;
1147 for (j = 0; j < ndupl; j++)
1150 copy_loops_to (orig_loops, n_orig_loops, target);
1153 copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
1155 place_after = new_spec_edges[SE_LATCH]->src;
1157 if (flags & DLTHE_RECORD_COPY_NUMBER)
1158 for (i = 0; i < n; i++)
1160 gcc_assert (!new_bbs[i]->aux);
1161 new_bbs[i]->aux = (void *)(size_t)(j + 1);
1164 /* Note whether the blocks and edges belong to an irreducible loop. */
1165 if (add_irreducible_flag)
1167 for (i = 0; i < n; i++)
1168 new_bbs[i]->flags |= BB_DUPLICATED;
1169 for (i = 0; i < n; i++)
1172 new_bb = new_bbs[i];
1173 if (new_bb->loop_father == target)
1174 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1176 FOR_EACH_EDGE (ae, ei, new_bb->succs)
1177 if ((ae->dest->flags & BB_DUPLICATED)
1178 && (ae->src->loop_father == target
1179 || ae->dest->loop_father == target))
1180 ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1182 for (i = 0; i < n; i++)
1183 new_bbs[i]->flags &= ~BB_DUPLICATED;
1186 /* Redirect the special edges. */
1189 redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1190 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1192 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
1193 latch = loop->latch = new_bbs[n - 1];
1194 e = latch_edge = new_spec_edges[SE_LATCH];
1198 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1200 redirect_edge_and_branch_force (e, new_bbs[0]);
1201 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
1202 e = new_spec_edges[SE_LATCH];
1205 /* Record exit edge in this copy. */
1206 if (orig && TEST_BIT (wont_exit, j + 1))
1209 VEC_safe_push (edge, heap, *to_remove, new_spec_edges[SE_ORIG]);
1210 set_zero_probability (new_spec_edges[SE_ORIG]);
1212 /* Scale the frequencies of the blocks dominated by the exit. */
1215 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1217 scale_bbs_frequencies_int (new_bbs + i, 1, scale_after_exit,
1223 /* Record the first copy in the control flow order if it is not
1224 the original loop (i.e. in case of peeling). */
1225 if (!first_active_latch)
1227 memcpy (first_active, new_bbs, n * sizeof (basic_block));
1228 first_active_latch = new_bbs[n - 1];
1231 /* Set counts and frequencies. */
1232 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1234 scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1235 scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
1241 /* Record the exit edge in the original loop body, and update the frequencies. */
1242 if (orig && TEST_BIT (wont_exit, 0))
1245 VEC_safe_push (edge, heap, *to_remove, orig);
1246 set_zero_probability (orig);
1248 /* Scale the frequencies of the blocks dominated by the exit. */
1251 EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
1253 scale_bbs_frequencies_int (bbs + i, 1, scale_after_exit,
1259 /* Update the original loop. */
1261 set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1262 if (flags & DLTHE_FLAG_UPDATE_FREQ)
1264 scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
1268 /* Update dominators of outer blocks if affected. */
1269 for (i = 0; i < n; i++)
1271 basic_block dominated, dom_bb;
1272 VEC (basic_block, heap) *dom_bbs;
1278 dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
1279 FOR_EACH_VEC_ELT (basic_block, dom_bbs, j, dominated)
1281 if (flow_bb_inside_loop_p (loop, dominated))
1283 dom_bb = nearest_common_dominator (
1284 CDI_DOMINATORS, first_active[i], first_active_latch);
1285 set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1287 VEC_free (basic_block, heap, dom_bbs);
1289 free (first_active);
1292 BITMAP_FREE (bbs_to_scale);
1297 /* A callback for make_forwarder block, to redirect all edges except for
1298 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1299 whether to redirect it. */
1303 mfb_keep_just (edge e)
1305 return e != mfb_kj_edge;
1308 /* True when a candidate preheader BLOCK has predecessors from LOOP. */
1311 has_preds_from_loop (basic_block block, struct loop *loop)
1316 FOR_EACH_EDGE (e, ei, block->preds)
1317 if (e->src->loop_father == loop)
1322 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1323 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1324 entry; otherwise we also force preheader block to have only one successor.
1325 When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
1326 to be a fallthru predecessor to the loop header and to have only
1327 predecessors from outside of the loop.
1328 The function also updates dominators. */
1331 create_preheader (struct loop *loop, int flags)
1337 bool latch_edge_was_fallthru;
1338 edge one_succ_pred = NULL, single_entry = NULL;
1341 FOR_EACH_EDGE (e, ei, loop->header->preds)
1343 if (e->src == loop->latch)
1345 irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1348 if (single_succ_p (e->src))
1351 gcc_assert (nentry);
1354 bool need_forwarder_block = false;
1356 /* We do not allow entry block to be the loop preheader, since we
1357 cannot emit code there. */
1358 if (single_entry->src == ENTRY_BLOCK_PTR)
1359 need_forwarder_block = true;
1362 /* If we want simple preheaders, also force the preheader to have
1363 just a single successor. */
1364 if ((flags & CP_SIMPLE_PREHEADERS)
1365 && !single_succ_p (single_entry->src))
1366 need_forwarder_block = true;
1367 /* If we want fallthru preheaders, also create forwarder block when
1368 preheader ends with a jump or has predecessors from loop. */
1369 else if ((flags & CP_FALLTHRU_PREHEADERS)
1370 && (JUMP_P (BB_END (single_entry->src))
1371 || has_preds_from_loop (single_entry->src, loop)))
1372 need_forwarder_block = true;
1374 if (! need_forwarder_block)
1378 mfb_kj_edge = loop_latch_edge (loop);
1379 latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
1380 fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL);
1381 dummy = fallthru->src;
1382 loop->header = fallthru->dest;
1384 /* Try to be clever in placing the newly created preheader. The idea is to
1385 avoid breaking any "fallthruness" relationship between blocks.
1387 The preheader was created just before the header and all incoming edges
1388 to the header were redirected to the preheader, except the latch edge.
1389 So the only problematic case is when this latch edge was a fallthru
1390 edge: it is not anymore after the preheader creation so we have broken
1391 the fallthruness. We're therefore going to look for a better place. */
1392 if (latch_edge_was_fallthru)
1397 e = EDGE_PRED (dummy, 0);
1399 move_block_after (dummy, e->src);
1404 dummy->flags |= BB_IRREDUCIBLE_LOOP;
1405 single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1409 fprintf (dump_file, "Created preheader block for loop %i\n",
1412 if (flags & CP_FALLTHRU_PREHEADERS)
1413 gcc_assert ((single_succ_edge (dummy)->flags & EDGE_FALLTHRU)
1414 && !JUMP_P (BB_END (dummy)));
1419 /* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */
1422 create_preheaders (int flags)
1430 FOR_EACH_LOOP (li, loop, 0)
1431 create_preheader (loop, flags);
1432 loops_state_set (LOOPS_HAVE_PREHEADERS);
1435 /* Forces all loop latches to have only single successor. */
1438 force_single_succ_latches (void)
1444 FOR_EACH_LOOP (li, loop, 0)
1446 if (loop->latch != loop->header && single_succ_p (loop->latch))
1449 e = find_edge (loop->latch, loop->header);
1453 loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES);
1456 /* This function is called from loop_version. It splits the entry edge
1457 of the loop we want to version, adds the versioning condition, and
1458 adjust the edges to the two versions of the loop appropriately.
1459 e is an incoming edge. Returns the basic block containing the
1462 --- edge e ---- > [second_head]
1464 Split it and insert new conditional expression and adjust edges.
1466 --- edge e ---> [cond expr] ---> [first_head]
1468 +---------> [second_head]
1470 THEN_PROB is the probability of then branch of the condition. */
1473 lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head,
1474 edge e, void *cond_expr, unsigned then_prob)
1476 basic_block new_head = NULL;
1479 gcc_assert (e->dest == second_head);
1481 /* Split edge 'e'. This will create a new basic block, where we can
1482 insert conditional expr. */
1483 new_head = split_edge (e);
1485 lv_add_condition_to_bb (first_head, second_head, new_head,
1488 /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */
1489 e = single_succ_edge (new_head);
1490 e1 = make_edge (new_head, first_head,
1491 current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0);
1492 e1->probability = then_prob;
1493 e->probability = REG_BR_PROB_BASE - then_prob;
1494 e1->count = RDIV (e->count * e1->probability, REG_BR_PROB_BASE);
1495 e->count = RDIV (e->count * e->probability, REG_BR_PROB_BASE);
1497 set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1498 set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1500 /* Adjust loop header phi nodes. */
1501 lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1506 /* Main entry point for Loop Versioning transformation.
1508 This transformation given a condition and a loop, creates
1509 -if (condition) { loop_copy1 } else { loop_copy2 },
1510 where loop_copy1 is the loop transformed in one way, and loop_copy2
1511 is the loop transformed in another way (or unchanged). 'condition'
1512 may be a run time test for things that were not resolved by static
1513 analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1515 THEN_PROB is the probability of the then edge of the if. THEN_SCALE
1516 is the ratio by that the frequencies in the original loop should
1517 be scaled. ELSE_SCALE is the ratio by that the frequencies in the
1518 new loop should be scaled.
1520 If PLACE_AFTER is true, we place the new loop after LOOP in the
1521 instruction stream, otherwise it is placed before LOOP. */
1524 loop_version (struct loop *loop,
1525 void *cond_expr, basic_block *condition_bb,
1526 unsigned then_prob, unsigned then_scale, unsigned else_scale,
1529 basic_block first_head, second_head;
1530 edge entry, latch_edge, true_edge, false_edge;
1533 basic_block cond_bb;
1535 /* Record entry and latch edges for the loop */
1536 entry = loop_preheader_edge (loop);
1537 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1538 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1540 /* Note down head of loop as first_head. */
1541 first_head = entry->dest;
1543 /* Duplicate loop. */
1544 if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, 1,
1545 NULL, NULL, NULL, 0))
1547 entry->flags |= irred_flag;
1551 /* After duplication entry edge now points to new loop head block.
1552 Note down new head as second_head. */
1553 second_head = entry->dest;
1555 /* Split loop entry edge and insert new block with cond expr. */
1556 cond_bb = lv_adjust_loop_entry_edge (first_head, second_head,
1557 entry, cond_expr, then_prob);
1559 *condition_bb = cond_bb;
1563 entry->flags |= irred_flag;
1567 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1569 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1570 nloop = loopify (latch_edge,
1571 single_pred_edge (get_bb_copy (loop->header)),
1572 cond_bb, true_edge, false_edge,
1573 false /* Do not redirect all edges. */,
1574 then_scale, else_scale);
1576 /* loopify redirected latch_edge. Update its PENDING_STMTS. */
1577 lv_flush_pending_stmts (latch_edge);
1579 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
1580 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1581 lv_flush_pending_stmts (false_edge);
1582 /* Adjust irreducible flag. */
1585 cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
1586 loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1587 loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1588 single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
1593 basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
1596 after = loop->latch;
1598 for (i = 0; i < nloop->num_nodes; i++)
1600 move_block_after (bbs[i], after);
1606 /* At this point condition_bb is loop preheader with two successors,
1607 first_head and second_head. Make sure that loop preheader has only
1609 split_edge (loop_preheader_edge (loop));
1610 split_edge (loop_preheader_edge (nloop));
1615 /* The structure of loops might have changed. Some loops might get removed
1616 (and their headers and latches were set to NULL), loop exists might get
1617 removed (thus the loop nesting may be wrong), and some blocks and edges
1618 were changed (so the information about bb --> loop mapping does not have
1619 to be correct). But still for the remaining loops the header dominates
1620 the latch, and loops did not get new subloops (new loops might possibly
1621 get created, but we are not interested in them). Fix up the mess.
1623 If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1627 fix_loop_structure (bitmap changed_bbs)
1630 struct loop *loop, *ploop;
1632 bool record_exits = false;
1633 struct loop **superloop = XNEWVEC (struct loop *, number_of_loops ());
1635 /* Remove the old bb -> loop mapping. Remember the depth of the blocks in
1636 the loop hierarchy, so that we can recognize blocks whose loop nesting
1637 relationship has changed. */
1641 bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
1642 bb->loop_father = current_loops->tree_root;
1645 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1647 release_recorded_exits ();
1648 record_exits = true;
1651 /* Remove the dead loops from structures. We start from the innermost
1652 loops, so that when we remove the loops, we know that the loops inside
1653 are preserved, and do not waste time relinking loops that will be
1655 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1662 ploop = loop->inner;
1663 flow_loop_tree_node_remove (ploop);
1664 flow_loop_tree_node_add (loop_outer (loop), ploop);
1667 /* Remove the loop and free its data. */
1671 /* Rescan the bodies of loops, starting from the outermost ones. We assume
1672 that no optimization interchanges the order of the loops, i.e., it cannot
1673 happen that L1 was superloop of L2 before and it is subloop of L2 now
1674 (without explicitly updating loop information). At the same time, we also
1675 determine the new loop structure. */
1676 current_loops->tree_root->num_nodes = n_basic_blocks;
1677 FOR_EACH_LOOP (li, loop, 0)
1679 superloop[loop->num] = loop->header->loop_father;
1680 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
1683 /* Now fix the loop nesting. */
1684 FOR_EACH_LOOP (li, loop, 0)
1686 ploop = superloop[loop->num];
1687 if (ploop != loop_outer (loop))
1689 flow_loop_tree_node_remove (loop);
1690 flow_loop_tree_node_add (ploop, loop);
1695 /* Mark the blocks whose loop has changed. */
1700 if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
1701 bitmap_set_bit (changed_bbs, bb->index);
1707 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
1708 create_preheaders (CP_SIMPLE_PREHEADERS);
1710 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1711 force_single_succ_latches ();
1713 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1714 mark_irreducible_loops ();
1717 record_loop_exits ();
1719 #ifdef ENABLE_CHECKING
1720 verify_loop_structure ();