1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002, 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
29 #include "cfglayout.h"
32 static void duplicate_subloops (struct loops
*, struct loop
*, struct loop
*);
33 static void copy_loops_to (struct loops
*, struct loop
**, int,
35 static void loop_redirect_edge (edge
, basic_block
);
36 static bool loop_delete_branch_edge (edge
, int);
37 static void remove_bbs (basic_block
*, int);
38 static bool rpe_enum_p (basic_block
, void *);
39 static int find_path (edge
, basic_block
**);
40 static bool alp_enum_p (basic_block
, void *);
41 static void add_loop (struct loops
*, struct loop
*);
42 static void fix_loop_placements (struct loops
*, struct loop
*);
43 static bool fix_bb_placement (struct loops
*, basic_block
);
44 static void fix_bb_placements (struct loops
*, basic_block
);
45 static void place_new_loop (struct loops
*, struct loop
*);
46 static void scale_loop_frequencies (struct loop
*, int, int);
47 static void scale_bbs_frequencies (basic_block
*, int, int, int);
48 static basic_block
create_preheader (struct loop
*, int);
49 static void fix_irreducible_loops (basic_block
);
51 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
53 /* Splits basic block BB after INSN, returns created edge. Updates loops
56 split_loop_bb (basic_block bb
, rtx insn
)
60 /* Split the block. */
61 e
= split_block (bb
, insn
);
63 /* Add dest to loop. */
64 add_bb_to_loop (e
->dest
, e
->src
->loop_father
);
69 /* Checks whether basic block BB is dominated by DATA. */
71 rpe_enum_p (basic_block bb
, void *data
)
73 return dominated_by_p (CDI_DOMINATORS
, bb
, data
);
76 /* Remove basic blocks BBS from loop structure and dominance info,
77 and delete them afterwards. */
79 remove_bbs (basic_block
*bbs
, int nbbs
)
83 for (i
= 0; i
< nbbs
; i
++)
85 remove_bb_from_loops (bbs
[i
]);
86 delete_basic_block (bbs
[i
]);
90 /* Find path -- i.e. the basic blocks dominated by edge E and put them
91 into array BBS, that will be allocated large enough to contain them.
92 E->dest must have exactly one predecessor for this to work (it is
93 easy to achieve and we do not put it here because we do not want to
94 alter anything by this function). The number of basic blocks in the
97 find_path (edge e
, basic_block
**bbs
)
99 gcc_assert (EDGE_COUNT (e
->dest
->preds
) <= 1);
101 /* Find bbs in the path. */
102 *bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
103 return dfs_enumerate_from (e
->dest
, 0, rpe_enum_p
, *bbs
,
104 n_basic_blocks
, e
->dest
);
107 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
108 Let L be a loop to that BB belongs. Then every successor of BB must either
109 1) belong to some superloop of loop L, or
110 2) be a header of loop K such that K->outer is superloop of L
111 Returns true if we had to move BB into other loop to enforce this condition,
112 false if the placement of BB was already correct (provided that placements
113 of its successors are correct). */
115 fix_bb_placement (struct loops
*loops
, basic_block bb
)
119 struct loop
*loop
= loops
->tree_root
, *act
;
121 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
123 if (e
->dest
== EXIT_BLOCK_PTR
)
126 act
= e
->dest
->loop_father
;
127 if (act
->header
== e
->dest
)
130 if (flow_loop_nested_p (loop
, act
))
134 if (loop
== bb
->loop_father
)
137 remove_bb_from_loops (bb
);
138 add_bb_to_loop (bb
, loop
);
143 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
144 enforce condition condition stated in description of fix_bb_placement. We
145 start from basic block FROM that had some of its successors removed, so that
146 his placement no longer has to be correct, and iteratively fix placement of
147 its predecessors that may change if placement of FROM changed. Also fix
148 placement of subloops of FROM->loop_father, that might also be altered due
149 to this change; the condition for them is similar, except that instead of
150 successors we consider edges coming out of the loops. */
152 fix_bb_placements (struct loops
*loops
, basic_block from
)
155 basic_block
*queue
, *qtop
, *qbeg
, *qend
;
156 struct loop
*base_loop
;
159 /* We pass through blocks back-reachable from FROM, testing whether some
160 of their successors moved to outer loop. It may be necessary to
161 iterate several times, but it is finite, as we stop unless we move
162 the basic block up the loop structure. The whole story is a bit
163 more complicated due to presence of subloops, those are moved using
164 fix_loop_placement. */
166 base_loop
= from
->loop_father
;
167 if (base_loop
== loops
->tree_root
)
170 in_queue
= sbitmap_alloc (last_basic_block
);
171 sbitmap_zero (in_queue
);
172 SET_BIT (in_queue
, from
->index
);
173 /* Prevent us from going out of the base_loop. */
174 SET_BIT (in_queue
, base_loop
->header
->index
);
176 queue
= xmalloc ((base_loop
->num_nodes
+ 1) * sizeof (basic_block
));
177 qtop
= queue
+ base_loop
->num_nodes
+ 1;
189 RESET_BIT (in_queue
, from
->index
);
191 if (from
->loop_father
->header
== from
)
193 /* Subloop header, maybe move the loop upward. */
194 if (!fix_loop_placement (from
->loop_father
))
199 /* Ordinary basic block. */
200 if (!fix_bb_placement (loops
, from
))
204 /* Something has changed, insert predecessors into queue. */
205 FOR_EACH_EDGE (e
, ei
, from
->preds
)
207 basic_block pred
= e
->src
;
210 if (TEST_BIT (in_queue
, pred
->index
))
213 /* If it is subloop, then it either was not moved, or
214 the path up the loop tree from base_loop do not contain
216 nca
= find_common_loop (pred
->loop_father
, base_loop
);
217 if (pred
->loop_father
!= base_loop
219 || nca
!= pred
->loop_father
))
220 pred
= pred
->loop_father
->header
;
221 else if (!flow_loop_nested_p (from
->loop_father
, pred
->loop_father
))
223 /* No point in processing it. */
227 if (TEST_BIT (in_queue
, pred
->index
))
230 /* Schedule the basic block. */
235 SET_BIT (in_queue
, pred
->index
);
242 /* Basic block from has lost one or more of its predecessors, so it might
243 mo longer be part irreducible loop. Fix it and proceed recursively
244 for its successors if needed. */
246 fix_irreducible_loops (basic_block from
)
255 if (!(from
->flags
& BB_IRREDUCIBLE_LOOP
))
258 on_stack
= sbitmap_alloc (last_basic_block
);
259 sbitmap_zero (on_stack
);
260 SET_BIT (on_stack
, from
->index
);
261 stack
= xmalloc (from
->loop_father
->num_nodes
* sizeof (basic_block
));
268 bb
= stack
[--stack_top
];
269 RESET_BIT (on_stack
, bb
->index
);
271 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
273 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
, &n_edges
);
284 n_edges
= EDGE_COUNT (bb
->succs
);
285 edges
= xmalloc (n_edges
* sizeof (edge
));
286 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
288 /* FIXME: Don't use private iterator. */
293 for (i
= 0; i
< n_edges
; i
++)
297 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
299 if (!flow_bb_inside_loop_p (from
->loop_father
, e
->dest
))
302 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
303 if (TEST_BIT (on_stack
, e
->dest
->index
))
306 SET_BIT (on_stack
, e
->dest
->index
);
307 stack
[stack_top
++] = e
->dest
;
317 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
318 and update loop structure stored in LOOPS and dominators. Return true if
319 we were able to remove the path, false otherwise (and nothing is affected
322 remove_path (struct loops
*loops
, edge e
)
325 basic_block
*rem_bbs
, *bord_bbs
, *dom_bbs
, from
, bb
;
326 int i
, nrem
, n_bord_bbs
, n_dom_bbs
;
330 if (!loop_delete_branch_edge (e
, 0))
333 /* We need to check whether basic blocks are dominated by the edge
334 e, but we only have basic block dominators. This is easy to
335 fix -- when e->dest has exactly one predecessor, this corresponds
336 to blocks dominated by e->dest, if not, split the edge. */
337 if (EDGE_COUNT (e
->dest
->preds
) > 1)
338 e
= EDGE_PRED (loop_split_edge_with (e
, NULL_RTX
), 0);
340 /* It may happen that by removing path we remove one or more loops
341 we belong to. In this case first unloop the loops, then proceed
342 normally. We may assume that e->dest is not a header of any loop,
343 as it now has exactly one predecessor. */
344 while (e
->src
->loop_father
->outer
345 && dominated_by_p (CDI_DOMINATORS
,
346 e
->src
->loop_father
->latch
, e
->dest
))
347 unloop (loops
, e
->src
->loop_father
);
349 /* Identify the path. */
350 nrem
= find_path (e
, &rem_bbs
);
353 bord_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
354 seen
= sbitmap_alloc (last_basic_block
);
357 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
358 for (i
= 0; i
< nrem
; i
++)
359 SET_BIT (seen
, rem_bbs
[i
]->index
);
360 for (i
= 0; i
< nrem
; i
++)
364 FOR_EACH_EDGE (ae
, ei
, rem_bbs
[i
]->succs
)
366 if (ae
->dest
!= EXIT_BLOCK_PTR
&& !TEST_BIT (seen
, ae
->dest
->index
))
368 SET_BIT (seen
, ae
->dest
->index
);
369 bord_bbs
[n_bord_bbs
++] = ae
->dest
;
374 /* Remove the path. */
376 deleted
= loop_delete_branch_edge (e
, 1);
377 gcc_assert (deleted
);
378 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
380 /* Cancel loops contained in the path. */
381 for (i
= 0; i
< nrem
; i
++)
382 if (rem_bbs
[i
]->loop_father
->header
== rem_bbs
[i
])
383 cancel_loop_tree (loops
, rem_bbs
[i
]->loop_father
);
385 remove_bbs (rem_bbs
, nrem
);
388 /* Find blocks whose dominators may be affected. */
391 for (i
= 0; i
< n_bord_bbs
; i
++)
395 bb
= get_immediate_dominator (CDI_DOMINATORS
, bord_bbs
[i
]);
396 if (TEST_BIT (seen
, bb
->index
))
398 SET_BIT (seen
, bb
->index
);
400 for (ldom
= first_dom_son (CDI_DOMINATORS
, bb
);
402 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
403 if (!dominated_by_p (CDI_DOMINATORS
, from
, ldom
))
404 dom_bbs
[n_dom_bbs
++] = ldom
;
409 /* Recount dominators. */
410 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
413 /* These blocks have lost some predecessor(s), thus their irreducible
414 status could be changed. */
415 for (i
= 0; i
< n_bord_bbs
; i
++)
416 fix_irreducible_loops (bord_bbs
[i
]);
419 /* Fix placements of basic blocks inside loops and the placement of
420 loops in the loop tree. */
421 fix_bb_placements (loops
, from
);
422 fix_loop_placements (loops
, from
->loop_father
);
427 /* Predicate for enumeration in add_loop. */
429 alp_enum_p (basic_block bb
, void *alp_header
)
431 return bb
!= (basic_block
) alp_header
;
434 /* Given LOOP structure with filled header and latch, find the body of the
435 corresponding loop and add it to LOOPS tree. */
437 add_loop (struct loops
*loops
, struct loop
*loop
)
442 /* Add it to loop structure. */
443 place_new_loop (loops
, loop
);
446 /* Find its nodes. */
447 bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
448 n
= dfs_enumerate_from (loop
->latch
, 1, alp_enum_p
,
449 bbs
, n_basic_blocks
, loop
->header
);
451 for (i
= 0; i
< n
; i
++)
452 add_bb_to_loop (bbs
[i
], loop
);
453 add_bb_to_loop (loop
->header
, loop
);
458 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
461 scale_bbs_frequencies (basic_block
*bbs
, int nbbs
, int num
, int den
)
466 for (i
= 0; i
< nbbs
; i
++)
469 bbs
[i
]->frequency
= (bbs
[i
]->frequency
* num
) / den
;
470 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
471 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
473 e
->count
= (e
->count
* num
) /den
;
478 /* Multiply all frequencies in LOOP by NUM/DEN. */
480 scale_loop_frequencies (struct loop
*loop
, int num
, int den
)
484 bbs
= get_loop_body (loop
);
485 scale_bbs_frequencies (bbs
, loop
->num_nodes
, num
, den
);
489 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
490 latch to header and update loop tree stored in LOOPS and dominators
491 accordingly. Everything between them plus LATCH_EDGE destination must
492 be dominated by HEADER_EDGE destination, and back-reachable from
493 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
494 FALLTHRU_EDGE (SWITCH_BB) to original destination of HEADER_EDGE and
495 BRANCH_EDGE (SWITCH_BB) to original destination of LATCH_EDGE.
496 Returns newly created loop. */
499 loopify (struct loops
*loops
, edge latch_edge
, edge header_edge
,
500 basic_block switch_bb
)
502 basic_block succ_bb
= latch_edge
->dest
;
503 basic_block pred_bb
= header_edge
->src
;
504 basic_block
*dom_bbs
, *body
;
505 unsigned n_dom_bbs
, i
;
507 struct loop
*loop
= xcalloc (1, sizeof (struct loop
));
508 struct loop
*outer
= succ_bb
->loop_father
->outer
;
509 int freq
, prob
, tot_prob
;
514 loop
->header
= header_edge
->dest
;
515 loop
->latch
= latch_edge
->src
;
517 freq
= EDGE_FREQUENCY (header_edge
);
518 cnt
= header_edge
->count
;
519 prob
= EDGE_SUCC (switch_bb
, 0)->probability
;
520 tot_prob
= prob
+ EDGE_SUCC (switch_bb
, 1)->probability
;
524 /* Redirect edges. */
525 loop_redirect_edge (latch_edge
, loop
->header
);
526 loop_redirect_edge (BRANCH_EDGE (switch_bb
), succ_bb
);
528 loop_redirect_edge (header_edge
, switch_bb
);
529 loop_redirect_edge (FALLTHRU_EDGE (switch_bb
), loop
->header
);
531 /* Update dominators. */
532 set_immediate_dominator (CDI_DOMINATORS
, switch_bb
, pred_bb
);
533 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
, switch_bb
);
535 set_immediate_dominator (CDI_DOMINATORS
, succ_bb
, switch_bb
);
537 /* Compute new loop. */
538 add_loop (loops
, loop
);
539 flow_loop_tree_node_add (outer
, loop
);
541 /* Add switch_bb to appropriate loop. */
542 add_bb_to_loop (switch_bb
, outer
);
544 /* Fix frequencies. */
545 switch_bb
->frequency
= freq
;
546 switch_bb
->count
= cnt
;
547 FOR_EACH_EDGE (e
, ei
, switch_bb
->succs
)
549 e
->count
= (switch_bb
->count
* e
->probability
) / REG_BR_PROB_BASE
;
551 scale_loop_frequencies (loop
, prob
, tot_prob
);
552 scale_loop_frequencies (succ_bb
->loop_father
, tot_prob
- prob
, tot_prob
);
554 /* Update dominators of blocks outside of LOOP. */
555 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
557 seen
= sbitmap_alloc (last_basic_block
);
559 body
= get_loop_body (loop
);
561 for (i
= 0; i
< loop
->num_nodes
; i
++)
562 SET_BIT (seen
, body
[i
]->index
);
564 for (i
= 0; i
< loop
->num_nodes
; i
++)
568 for (ldom
= first_dom_son (CDI_DOMINATORS
, body
[i
]);
570 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
571 if (!TEST_BIT (seen
, ldom
->index
))
573 SET_BIT (seen
, ldom
->index
);
574 dom_bbs
[n_dom_bbs
++] = ldom
;
578 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
587 /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
588 the LOOP was removed. After this function, original loop latch will
589 have no successor, which caller is expected to fix somehow. */
591 unloop (struct loops
*loops
, struct loop
*loop
)
596 basic_block latch
= loop
->latch
;
600 /* This is relatively straightforward. The dominators are unchanged, as
601 loop header dominates loop latch, so the only thing we have to care of
602 is the placement of loops and basic blocks inside the loop tree. We
603 move them all to the loop->outer, and then let fix_bb_placements do
606 body
= get_loop_body (loop
);
607 edges
= get_loop_exit_edges (loop
, &n_edges
);
609 for (i
= 0; i
< n
; i
++)
610 if (body
[i
]->loop_father
== loop
)
612 remove_bb_from_loops (body
[i
]);
613 add_bb_to_loop (body
[i
], loop
->outer
);
620 flow_loop_tree_node_remove (ploop
);
621 flow_loop_tree_node_add (loop
->outer
, ploop
);
624 /* Remove the loop and free its data. */
625 flow_loop_tree_node_remove (loop
);
626 loops
->parray
[loop
->num
] = NULL
;
627 flow_loop_free (loop
);
629 remove_edge (EDGE_SUCC (latch
, 0));
630 fix_bb_placements (loops
, latch
);
632 /* If the loop was inside an irreducible region, we would have to somehow
633 update the irreducible marks inside its body. While it is certainly
634 possible to do, it is a bit complicated and this situation should be
635 very rare, so we just remark all loops in this case. */
636 for (i
= 0; i
< n_edges
; i
++)
637 if (edges
[i
]->flags
& EDGE_IRREDUCIBLE_LOOP
)
640 mark_irreducible_loops (loops
);
644 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
645 FATHER of LOOP such that all of the edges coming out of LOOP belong to
646 FATHER, and set it as outer loop of LOOP. Return 1 if placement of
649 fix_loop_placement (struct loop
*loop
)
655 struct loop
*father
= loop
->pred
[0], *act
;
657 body
= get_loop_body (loop
);
658 for (i
= 0; i
< loop
->num_nodes
; i
++)
659 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
661 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
663 act
= find_common_loop (loop
, e
->dest
->loop_father
);
664 if (flow_loop_nested_p (father
, act
))
670 if (father
!= loop
->outer
)
672 for (act
= loop
->outer
; act
!= father
; act
= act
->outer
)
673 act
->num_nodes
-= loop
->num_nodes
;
674 flow_loop_tree_node_remove (loop
);
675 flow_loop_tree_node_add (father
, loop
);
681 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
682 condition stated in description of fix_loop_placement holds for them.
683 It is used in case when we removed some edges coming out of LOOP, which
684 may cause the right placement of LOOP inside loop tree to change. */
686 fix_loop_placements (struct loops
*loops
, struct loop
*loop
)
693 if (!fix_loop_placement (loop
))
696 /* Changing the placement of a loop in the loop tree may alter the
697 validity of condition 2) of the description of fix_bb_placement
698 for its preheader, because the successor is the header and belongs
699 to the loop. So call fix_bb_placements to fix up the placement
700 of the preheader and (possibly) of its predecessors. */
701 fix_bb_placements (loops
, loop_preheader_edge (loop
)->src
);
706 /* Creates place for a new LOOP in LOOPS structure. */
708 place_new_loop (struct loops
*loops
, struct loop
*loop
)
711 xrealloc (loops
->parray
, (loops
->num
+ 1) * sizeof (struct loop
*));
712 loops
->parray
[loops
->num
] = loop
;
714 loop
->num
= loops
->num
++;
717 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
718 created loop into LOOPS structure. */
720 duplicate_loop (struct loops
*loops
, struct loop
*loop
, struct loop
*target
)
723 cloop
= xcalloc (1, sizeof (struct loop
));
724 place_new_loop (loops
, cloop
);
726 /* Initialize copied loop. */
727 cloop
->level
= loop
->level
;
729 /* Set it as copy of loop. */
732 /* Add it to target. */
733 flow_loop_tree_node_add (target
, cloop
);
738 /* Copies structure of subloops of LOOP into TARGET loop, placing
739 newly created loops into loop tree stored in LOOPS. */
741 duplicate_subloops (struct loops
*loops
, struct loop
*loop
, struct loop
*target
)
743 struct loop
*aloop
, *cloop
;
745 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
747 cloop
= duplicate_loop (loops
, aloop
, target
);
748 duplicate_subloops (loops
, aloop
, cloop
);
752 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
753 into TARGET loop, placing newly created loops into loop tree LOOPS. */
755 copy_loops_to (struct loops
*loops
, struct loop
**copied_loops
, int n
, struct loop
*target
)
760 for (i
= 0; i
< n
; i
++)
762 aloop
= duplicate_loop (loops
, copied_loops
[i
], target
);
763 duplicate_subloops (loops
, copied_loops
[i
], aloop
);
767 /* Redirects edge E to basic block DEST. */
769 loop_redirect_edge (edge e
, basic_block dest
)
774 redirect_edge_and_branch_force (e
, dest
);
777 /* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set,
778 just test whether it is possible to remove the edge. */
780 loop_delete_branch_edge (edge e
, int really_delete
)
782 basic_block src
= e
->src
;
787 gcc_assert (EDGE_COUNT (src
->succs
) > 1);
789 /* Cannot handle more than two exit edges. */
790 if (EDGE_COUNT (src
->succs
) > 2)
792 /* And it must be just a simple branch. */
793 if (!any_condjump_p (BB_END (src
)))
796 snd
= e
== EDGE_SUCC (src
, 0) ? EDGE_SUCC (src
, 1) : EDGE_SUCC (src
, 0);
798 if (newdest
== EXIT_BLOCK_PTR
)
801 /* Hopefully the above conditions should suffice. */
805 /* Redirecting behaves wrongly wrto this flag. */
806 irr
= snd
->flags
& EDGE_IRREDUCIBLE_LOOP
;
808 if (!redirect_edge_and_branch (e
, newdest
))
810 EDGE_SUCC (src
, 0)->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
811 EDGE_SUCC (src
, 0)->flags
|= irr
;
816 /* Check whether LOOP's body can be duplicated. */
818 can_duplicate_loop_p (struct loop
*loop
)
821 basic_block
*bbs
= get_loop_body (loop
);
823 ret
= can_copy_bbs_p (bbs
, loop
->num_nodes
);
829 /* The NBBS blocks in BBS will get duplicated and the copies will be placed
830 to LOOP. Update the single_exit information in superloops of LOOP. */
833 update_single_exits_after_duplication (basic_block
*bbs
, unsigned nbbs
,
838 for (i
= 0; i
< nbbs
; i
++)
839 bbs
[i
]->rbi
->duplicated
= 1;
841 for (; loop
->outer
; loop
= loop
->outer
)
843 if (!loop
->single_exit
)
846 if (loop
->single_exit
->src
->rbi
->duplicated
)
847 loop
->single_exit
= NULL
;
850 for (i
= 0; i
< nbbs
; i
++)
851 bbs
[i
]->rbi
->duplicated
= 0;
855 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
856 LOOPS structure and dominators. E's destination must be LOOP header for
857 this to work, i.e. it must be entry or latch edge of this loop; these are
858 unique, as the loops must have preheaders for this function to work
859 correctly (in case E is latch, the function unrolls the loop, if E is entry
860 edge, it peels the loop). Store edges created by copying ORIG edge from
861 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
862 original LOOP body, the other copies are numbered in order given by control
863 flow through them) into TO_REMOVE array. Returns false if duplication is
866 duplicate_loop_to_header_edge (struct loop
*loop
, edge e
, struct loops
*loops
,
867 unsigned int ndupl
, sbitmap wont_exit
,
868 edge orig
, edge
*to_remove
,
869 unsigned int *n_to_remove
, int flags
)
871 struct loop
*target
, *aloop
;
872 struct loop
**orig_loops
;
873 unsigned n_orig_loops
;
874 basic_block header
= loop
->header
, latch
= loop
->latch
;
875 basic_block
*new_bbs
, *bbs
, *first_active
;
876 basic_block new_bb
, bb
, first_active_latch
= NULL
;
878 edge spec_edges
[2], new_spec_edges
[2];
882 int is_latch
= (latch
== e
->src
);
883 int scale_act
= 0, *scale_step
= NULL
, scale_main
= 0;
884 int p
, freq_in
, freq_le
, freq_out_orig
;
885 int prob_pass_thru
, prob_pass_wont_exit
, prob_pass_main
;
886 int add_irreducible_flag
;
888 gcc_assert (e
->dest
== loop
->header
);
889 gcc_assert (ndupl
> 0);
893 /* Orig must be edge out of the loop. */
894 gcc_assert (flow_bb_inside_loop_p (loop
, orig
->src
));
895 gcc_assert (!flow_bb_inside_loop_p (loop
, orig
->dest
));
898 bbs
= get_loop_body (loop
);
900 /* Check whether duplication is possible. */
901 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
906 new_bbs
= xmalloc (sizeof (basic_block
) * loop
->num_nodes
);
908 /* In case we are doing loop peeling and the loop is in the middle of
909 irreducible region, the peeled copies will be inside it too. */
910 add_irreducible_flag
= e
->flags
& EDGE_IRREDUCIBLE_LOOP
;
911 gcc_assert (!is_latch
|| !add_irreducible_flag
);
913 /* Find edge from latch. */
914 latch_edge
= loop_latch_edge (loop
);
916 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
918 /* Calculate coefficients by that we have to scale frequencies
919 of duplicated loop bodies. */
920 freq_in
= header
->frequency
;
921 freq_le
= EDGE_FREQUENCY (latch_edge
);
924 if (freq_in
< freq_le
)
926 freq_out_orig
= orig
? EDGE_FREQUENCY (orig
) : freq_in
- freq_le
;
927 if (freq_out_orig
> freq_in
- freq_le
)
928 freq_out_orig
= freq_in
- freq_le
;
929 prob_pass_thru
= RDIV (REG_BR_PROB_BASE
* freq_le
, freq_in
);
930 prob_pass_wont_exit
=
931 RDIV (REG_BR_PROB_BASE
* (freq_le
+ freq_out_orig
), freq_in
);
933 scale_step
= xmalloc (ndupl
* sizeof (int));
935 for (i
= 1; i
<= ndupl
; i
++)
936 scale_step
[i
- 1] = TEST_BIT (wont_exit
, i
)
937 ? prob_pass_wont_exit
942 prob_pass_main
= TEST_BIT (wont_exit
, 0)
943 ? prob_pass_wont_exit
946 scale_main
= REG_BR_PROB_BASE
;
947 for (i
= 0; i
< ndupl
; i
++)
950 p
= RDIV (p
* scale_step
[i
], REG_BR_PROB_BASE
);
952 scale_main
= RDIV (REG_BR_PROB_BASE
* REG_BR_PROB_BASE
, scale_main
);
953 scale_act
= RDIV (scale_main
* prob_pass_main
, REG_BR_PROB_BASE
);
957 scale_main
= REG_BR_PROB_BASE
;
958 for (i
= 0; i
< ndupl
; i
++)
959 scale_main
= RDIV (scale_main
* scale_step
[i
], REG_BR_PROB_BASE
);
960 scale_act
= REG_BR_PROB_BASE
- prob_pass_thru
;
962 for (i
= 0; i
< ndupl
; i
++)
963 gcc_assert (scale_step
[i
] >= 0 && scale_step
[i
] <= REG_BR_PROB_BASE
);
964 gcc_assert (scale_main
>= 0 && scale_main
<= REG_BR_PROB_BASE
965 && scale_act
>= 0 && scale_act
<= REG_BR_PROB_BASE
);
968 /* Loop the new bbs will belong to. */
969 target
= e
->src
->loop_father
;
971 /* Original loops. */
973 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
975 orig_loops
= xcalloc (n_orig_loops
, sizeof (struct loop
*));
976 for (aloop
= loop
->inner
, i
= 0; aloop
; aloop
= aloop
->next
, i
++)
977 orig_loops
[i
] = aloop
;
983 first_active
= xmalloc (n
* sizeof (basic_block
));
986 memcpy (first_active
, bbs
, n
* sizeof (basic_block
));
987 first_active_latch
= latch
;
990 /* Update the information about single exits. */
991 if (loops
->state
& LOOPS_HAVE_MARKED_SINGLE_EXITS
)
992 update_single_exits_after_duplication (bbs
, n
, target
);
994 /* Record exit edge in original loop body. */
995 if (orig
&& TEST_BIT (wont_exit
, 0))
996 to_remove
[(*n_to_remove
)++] = orig
;
998 spec_edges
[SE_ORIG
] = orig
;
999 spec_edges
[SE_LATCH
] = latch_edge
;
1001 for (j
= 0; j
< ndupl
; j
++)
1004 copy_loops_to (loops
, orig_loops
, n_orig_loops
, target
);
1007 copy_bbs (bbs
, n
, new_bbs
, spec_edges
, 2, new_spec_edges
, loop
);
1009 for (i
= 0; i
< n
; i
++)
1010 new_bbs
[i
]->rbi
->copy_number
= j
+ 1;
1012 /* Note whether the blocks and edges belong to an irreducible loop. */
1013 if (add_irreducible_flag
)
1015 for (i
= 0; i
< n
; i
++)
1016 new_bbs
[i
]->rbi
->duplicated
= 1;
1017 for (i
= 0; i
< n
; i
++)
1020 new_bb
= new_bbs
[i
];
1021 if (new_bb
->loop_father
== target
)
1022 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1024 FOR_EACH_EDGE (ae
, ei
, new_bb
->succs
)
1026 if (ae
->dest
->rbi
->duplicated
1027 && (ae
->src
->loop_father
== target
1028 || ae
->dest
->loop_father
== target
))
1029 ae
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1032 for (i
= 0; i
< n
; i
++)
1033 new_bbs
[i
]->rbi
->duplicated
= 0;
1036 /* Redirect the special edges. */
1039 redirect_edge_and_branch_force (latch_edge
, new_bbs
[0]);
1040 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1042 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], latch
);
1043 latch
= loop
->latch
= new_bbs
[1];
1044 e
= latch_edge
= new_spec_edges
[SE_LATCH
];
1048 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1050 redirect_edge_and_branch_force (e
, new_bbs
[0]);
1051 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], e
->src
);
1052 e
= new_spec_edges
[SE_LATCH
];
1055 /* Record exit edge in this copy. */
1056 if (orig
&& TEST_BIT (wont_exit
, j
+ 1))
1057 to_remove
[(*n_to_remove
)++] = new_spec_edges
[SE_ORIG
];
1059 /* Record the first copy in the control flow order if it is not
1060 the original loop (i.e. in case of peeling). */
1061 if (!first_active_latch
)
1063 memcpy (first_active
, new_bbs
, n
* sizeof (basic_block
));
1064 first_active_latch
= new_bbs
[1];
1067 /* Set counts and frequencies. */
1068 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1070 scale_bbs_frequencies (new_bbs
, n
, scale_act
, REG_BR_PROB_BASE
);
1071 scale_act
= RDIV (scale_act
* scale_step
[j
], REG_BR_PROB_BASE
);
1077 /* Update the original loop. */
1079 set_immediate_dominator (CDI_DOMINATORS
, e
->dest
, e
->src
);
1080 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1082 scale_bbs_frequencies (bbs
, n
, scale_main
, REG_BR_PROB_BASE
);
1086 /* Update dominators of outer blocks if affected. */
1087 for (i
= 0; i
< n
; i
++)
1089 basic_block dominated
, dom_bb
, *dom_bbs
;
1093 bb
->rbi
->copy_number
= 0;
1095 n_dom_bbs
= get_dominated_by (CDI_DOMINATORS
, bb
, &dom_bbs
);
1096 for (j
= 0; j
< n_dom_bbs
; j
++)
1098 dominated
= dom_bbs
[j
];
1099 if (flow_bb_inside_loop_p (loop
, dominated
))
1101 dom_bb
= nearest_common_dominator (
1102 CDI_DOMINATORS
, first_active
[i
], first_active_latch
);
1103 set_immediate_dominator (CDI_DOMINATORS
, dominated
, dom_bb
);
1107 free (first_active
);
1114 /* A callback for make_forwarder block, to redirect all edges except for
1115 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1116 whether to redirect it. */
1118 static edge mfb_kj_edge
;
1120 mfb_keep_just (edge e
)
1122 return e
!= mfb_kj_edge
;
1125 /* A callback for make_forwarder block, to update data structures for a basic
1126 block JUMP created by redirecting an edge (only the latch edge is being
1130 mfb_update_loops (basic_block jump
)
1132 struct loop
*loop
= EDGE_SUCC (jump
, 0)->dest
->loop_father
;
1134 if (dom_computed
[CDI_DOMINATORS
])
1135 set_immediate_dominator (CDI_DOMINATORS
, jump
, EDGE_PRED (jump
, 0)->src
);
1136 add_bb_to_loop (jump
, loop
);
1140 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1141 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1142 entry; otherwise we also force preheader block to have only one successor.
1143 The function also updates dominators. */
1146 create_preheader (struct loop
*loop
, int flags
)
1150 struct loop
*cloop
, *ploop
;
1155 cloop
= loop
->outer
;
1157 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1159 if (e
->src
== loop
->latch
)
1161 irred
|= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
1165 gcc_assert (nentry
);
1168 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1170 if (e
->src
!= loop
->latch
)
1173 if (!(flags
& CP_SIMPLE_PREHEADERS
) || EDGE_COUNT (e
->src
->succs
) == 1)
1177 mfb_kj_edge
= loop_latch_edge (loop
);
1178 fallthru
= make_forwarder_block (loop
->header
, mfb_keep_just
,
1180 dummy
= fallthru
->src
;
1181 loop
->header
= fallthru
->dest
;
1183 /* The header could be a latch of some superloop(s); due to design of
1184 split_block, it would now move to fallthru->dest. */
1185 for (ploop
= loop
; ploop
; ploop
= ploop
->outer
)
1186 if (ploop
->latch
== dummy
)
1187 ploop
->latch
= fallthru
->dest
;
1189 /* Reorganize blocks so that the preheader is not stuck in the middle of the
1191 FOR_EACH_EDGE (e
, ei
, dummy
->preds
)
1193 if (e
->src
!= loop
->latch
)
1196 move_block_after (dummy
, e
->src
);
1198 loop
->header
->loop_father
= loop
;
1199 add_bb_to_loop (dummy
, cloop
);
1203 dummy
->flags
|= BB_IRREDUCIBLE_LOOP
;
1204 EDGE_SUCC (dummy
, 0)->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1208 fprintf (dump_file
, "Created preheader block for loop %i\n",
1214 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1215 of FLAGS see create_preheader. */
1217 create_preheaders (struct loops
*loops
, int flags
)
1220 for (i
= 1; i
< loops
->num
; i
++)
1221 create_preheader (loops
->parray
[i
], flags
);
1222 loops
->state
|= LOOPS_HAVE_PREHEADERS
;
1225 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1228 force_single_succ_latches (struct loops
*loops
)
1234 for (i
= 1; i
< loops
->num
; i
++)
1237 loop
= loops
->parray
[i
];
1238 if (loop
->latch
!= loop
->header
&& EDGE_COUNT (loop
->latch
->succs
) == 1)
1241 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1243 if (e
->src
== loop
->latch
)
1247 loop_split_edge_with (e
, NULL_RTX
);
1249 loops
->state
|= LOOPS_HAVE_SIMPLE_LATCHES
;
1252 /* A quite stupid function to put INSNS on edge E. They are supposed to form
1253 just one basic block. Jumps in INSNS are not handled, so cfg do not have to
1254 be ok after this function. The created block is placed on correct place
1255 in LOOPS structure and its dominator is set. */
1257 loop_split_edge_with (edge e
, rtx insns
)
1259 basic_block src
, dest
, new_bb
;
1260 struct loop
*loop_c
;
1266 loop_c
= find_common_loop (src
->loop_father
, dest
->loop_father
);
1268 /* Create basic block for it. */
1270 new_bb
= split_edge (e
);
1271 add_bb_to_loop (new_bb
, loop_c
);
1272 new_bb
->flags
= insns
? BB_SUPERBLOCK
: 0;
1274 new_e
= EDGE_SUCC (new_bb
, 0);
1275 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1277 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1278 new_e
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1282 emit_insn_after (insns
, BB_END (new_bb
));
1284 if (dest
->loop_father
->latch
== src
)
1285 dest
->loop_father
->latch
= new_bb
;
1290 /* Uses the natural loop discovery to recreate loop notes. */
1292 create_loop_notes (void)
1294 rtx insn
, head
, end
;
1297 basic_block
*first
, *last
, bb
, pbb
;
1298 struct loop
**stack
, **top
;
1300 #ifdef ENABLE_CHECKING
1301 /* Verify that there really are no loop notes. */
1302 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1303 gcc_assert (!NOTE_P (insn
) ||
1304 NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
);
1307 flow_loops_find (&loops
, LOOP_TREE
);
1308 free_dominance_info (CDI_DOMINATORS
);
1311 last
= xcalloc (loops
.num
, sizeof (basic_block
));
1315 for (loop
= bb
->loop_father
; loop
->outer
; loop
= loop
->outer
)
1316 last
[loop
->num
] = bb
;
1319 first
= xcalloc (loops
.num
, sizeof (basic_block
));
1320 stack
= xcalloc (loops
.num
, sizeof (struct loop
*));
1325 for (loop
= bb
->loop_father
; loop
->outer
; loop
= loop
->outer
)
1327 if (!first
[loop
->num
])
1330 first
[loop
->num
] = bb
;
1333 if (bb
== last
[loop
->num
])
1335 /* Prevent loops from overlapping. */
1336 while (*--top
!= loop
)
1337 last
[(*top
)->num
] = EXIT_BLOCK_PTR
;
1339 /* If loop starts with jump into it, place the note in
1340 front of the jump. */
1341 insn
= PREV_INSN (BB_HEAD (first
[loop
->num
]));
1343 && BARRIER_P (insn
))
1344 insn
= PREV_INSN (insn
);
1348 && any_uncondjump_p (insn
)
1349 && onlyjump_p (insn
))
1351 pbb
= BLOCK_FOR_INSN (insn
);
1352 gcc_assert (pbb
&& EDGE_COUNT (pbb
->succs
) == 1);
1354 if (!flow_bb_inside_loop_p (loop
, EDGE_SUCC (pbb
, 0)->dest
))
1355 insn
= BB_HEAD (first
[loop
->num
]);
1358 insn
= BB_HEAD (first
[loop
->num
]);
1360 head
= BB_HEAD (first
[loop
->num
]);
1361 emit_note_before (NOTE_INSN_LOOP_BEG
, insn
);
1362 BB_HEAD (first
[loop
->num
]) = head
;
1364 /* Position the note correctly wrto barrier. */
1365 insn
= BB_END (last
[loop
->num
]);
1366 if (NEXT_INSN (insn
)
1367 && BARRIER_P (NEXT_INSN (insn
)))
1368 insn
= NEXT_INSN (insn
);
1370 end
= BB_END (last
[loop
->num
]);
1371 emit_note_after (NOTE_INSN_LOOP_END
, insn
);
1372 BB_END (last
[loop
->num
]) = end
;
1381 flow_loops_free (&loops
);