1 /* Loop manipulation code for GNU compiler.
2 Copyright (C) 2002, 2003 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 struct loop
* duplicate_loop (struct loops
*, struct loop
*,
34 static void duplicate_subloops (struct loops
*, struct loop
*, struct loop
*);
35 static void copy_loops_to (struct loops
*, struct loop
**, int,
37 static void loop_redirect_edge (edge
, basic_block
);
38 static bool loop_delete_branch_edge (edge
, int);
39 static void remove_bbs (basic_block
*, int);
40 static bool rpe_enum_p (basic_block
, void *);
41 static int find_path (edge
, basic_block
**);
42 static bool alp_enum_p (basic_block
, void *);
43 static void add_loop (struct loops
*, struct loop
*);
44 static void fix_loop_placements (struct loop
*);
45 static bool fix_bb_placement (struct loops
*, basic_block
);
46 static void fix_bb_placements (struct loops
*, basic_block
);
47 static void place_new_loop (struct loops
*, struct loop
*);
48 static void scale_loop_frequencies (struct loop
*, int, int);
49 static void scale_bbs_frequencies (basic_block
*, int, int, int);
50 static basic_block
create_preheader (struct loop
*, int);
51 static void fix_irreducible_loops (basic_block
);
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
);
67 add_to_dominance_info (CDI_DOMINATORS
, e
->dest
);
68 redirect_immediate_dominators (CDI_DOMINATORS
, e
->src
, e
->dest
);
69 set_immediate_dominator (CDI_DOMINATORS
, e
->dest
, e
->src
);
74 /* Checks whether basic block BB is dominated by DATA. */
76 rpe_enum_p (basic_block bb
, void *data
)
78 return dominated_by_p (CDI_DOMINATORS
, bb
, data
);
81 /* Remove basic blocks BBS from loop structure and dominance info,
82 and delete them afterwards. */
84 remove_bbs (basic_block
*bbs
, int nbbs
)
88 for (i
= 0; i
< nbbs
; i
++)
90 remove_bb_from_loops (bbs
[i
]);
91 delete_from_dominance_info (CDI_DOMINATORS
, bbs
[i
]);
92 delete_block (bbs
[i
]);
96 /* Find path -- i.e. the basic blocks dominated by edge E and put them
97 into array BBS, that will be allocated large enough to contain them.
98 E->dest must have exactly one predecessor for this to work (it is
99 easy to achieve and we do not put it here because we do not want to
100 alter anything by this function). The number of basic blocks in the
103 find_path (edge e
, basic_block
**bbs
)
105 if (e
->dest
->pred
->pred_next
)
108 /* Find bbs in the path. */
109 *bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
110 return dfs_enumerate_from (e
->dest
, 0, rpe_enum_p
, *bbs
,
111 n_basic_blocks
, e
->dest
);
114 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
115 Let L be a loop to that BB belongs. Then every successor of BB must either
116 1) belong to some superloop of loop L, or
117 2) be a header of loop K such that K->outer is superloop of L
118 Returns true if we had to move BB into other loop to enforce this condition,
119 false if the placement of BB was already correct (provided that placements
120 of its successors are correct). */
122 fix_bb_placement (struct loops
*loops
, basic_block bb
)
125 struct loop
*loop
= loops
->tree_root
, *act
;
127 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
129 if (e
->dest
== EXIT_BLOCK_PTR
)
132 act
= e
->dest
->loop_father
;
133 if (act
->header
== e
->dest
)
136 if (flow_loop_nested_p (loop
, act
))
140 if (loop
== bb
->loop_father
)
143 remove_bb_from_loops (bb
);
144 add_bb_to_loop (bb
, loop
);
149 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
150 enforce condition condition stated in description of fix_bb_placement. We
151 start from basic block FROM that had some of its successors removed, so that
152 his placement no longer has to be correct, and iteratively fix placement of
153 its predecessors that may change if placement of FROM changed. Also fix
154 placement of subloops of FROM->loop_father, that might also be altered due
155 to this change; the condition for them is similar, except that instead of
156 successors we consider edges coming out of the loops. */
158 fix_bb_placements (struct loops
*loops
, basic_block from
)
161 basic_block
*queue
, *qtop
, *qbeg
, *qend
;
162 struct loop
*base_loop
;
165 /* We pass through blocks back-reachable from FROM, testing whether some
166 of their successors moved to outer loop. It may be necessary to
167 iterate several times, but it is finite, as we stop unless we move
168 the basic block up the loop structure. The whole story is a bit
169 more complicated due to presence of subloops, those are moved using
170 fix_loop_placement. */
172 base_loop
= from
->loop_father
;
173 if (base_loop
== loops
->tree_root
)
176 in_queue
= sbitmap_alloc (last_basic_block
);
177 sbitmap_zero (in_queue
);
178 SET_BIT (in_queue
, from
->index
);
179 /* Prevent us from going out of the base_loop. */
180 SET_BIT (in_queue
, base_loop
->header
->index
);
182 queue
= xmalloc ((base_loop
->num_nodes
+ 1) * sizeof (basic_block
));
183 qtop
= queue
+ base_loop
->num_nodes
+ 1;
194 RESET_BIT (in_queue
, from
->index
);
196 if (from
->loop_father
->header
== from
)
198 /* Subloop header, maybe move the loop upward. */
199 if (!fix_loop_placement (from
->loop_father
))
204 /* Ordinary basic block. */
205 if (!fix_bb_placement (loops
, from
))
209 /* Something has changed, insert predecessors into queue. */
210 for (e
= from
->pred
; e
; e
= e
->pred_next
)
212 basic_block pred
= e
->src
;
215 if (TEST_BIT (in_queue
, pred
->index
))
218 /* If it is subloop, then it either was not moved, or
219 the path up the loop tree from base_loop do not contain
221 nca
= find_common_loop (pred
->loop_father
, base_loop
);
222 if (pred
->loop_father
!= base_loop
224 || nca
!= pred
->loop_father
))
225 pred
= pred
->loop_father
->header
;
226 else if (!flow_loop_nested_p (from
->loop_father
, pred
->loop_father
))
228 /* No point in processing it. */
232 if (TEST_BIT (in_queue
, pred
->index
))
235 /* Schedule the basic block. */
240 SET_BIT (in_queue
, pred
->index
);
247 /* Basic block from has lost one or more of its predecessors, so it might
248 mo longer be part irreducible loop. Fix it and proceed recursively
249 for its successors if needed. */
251 fix_irreducible_loops (basic_block from
)
260 if (!(from
->flags
& BB_IRREDUCIBLE_LOOP
))
263 on_stack
= sbitmap_alloc (last_basic_block
);
264 sbitmap_zero (on_stack
);
265 SET_BIT (on_stack
, from
->index
);
266 stack
= xmalloc (from
->loop_father
->num_nodes
* sizeof (basic_block
));
272 bb
= stack
[--stack_top
];
273 RESET_BIT (on_stack
, bb
->index
);
275 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
276 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
281 bb
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
282 if (bb
->loop_father
->header
== bb
)
283 edges
= get_loop_exit_edges (bb
->loop_father
, &n_edges
);
287 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
289 edges
= xmalloc (n_edges
* sizeof (edge
));
291 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
292 edges
[n_edges
++] = e
;
295 for (i
= 0; i
< n_edges
; i
++)
299 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
301 if (!flow_bb_inside_loop_p (from
->loop_father
, e
->dest
))
304 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
305 if (TEST_BIT (on_stack
, e
->dest
->index
))
308 SET_BIT (on_stack
, e
->dest
->index
);
309 stack
[stack_top
++] = e
->dest
;
319 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
320 and update loop structure stored in LOOPS and dominators. Return true if
321 we were able to remove the path, false otherwise (and nothing is affected
324 remove_path (struct loops
*loops
, edge e
)
327 basic_block
*rem_bbs
, *bord_bbs
, *dom_bbs
, from
, bb
;
328 int i
, nrem
, n_bord_bbs
, n_dom_bbs
;
331 if (!loop_delete_branch_edge (e
, 0))
334 /* We need to check whether basic blocks are dominated by the edge
335 e, but we only have basic block dominators. This is easy to
336 fix -- when e->dest has exactly one predecessor, this corresponds
337 to blocks dominated by e->dest, if not, split the edge. */
338 if (e
->dest
->pred
->pred_next
)
339 e
= loop_split_edge_with (e
, NULL_RTX
)->pred
;
341 /* It may happen that by removing path we remove one or more loops
342 we belong to. In this case first unloop the loops, then proceed
343 normally. We may assume that e->dest is not a header of any loop,
344 as it now has exactly one predecessor. */
345 while (e
->src
->loop_father
->outer
346 && dominated_by_p (CDI_DOMINATORS
,
347 e
->src
->loop_father
->latch
, e
->dest
))
348 unloop (loops
, e
->src
->loop_father
);
350 /* Identify the path. */
351 nrem
= find_path (e
, &rem_bbs
);
354 bord_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
355 seen
= sbitmap_alloc (last_basic_block
);
358 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
359 for (i
= 0; i
< nrem
; i
++)
360 SET_BIT (seen
, rem_bbs
[i
]->index
);
361 for (i
= 0; i
< nrem
; i
++)
364 for (ae
= rem_bbs
[i
]->succ
; ae
; ae
= ae
->succ_next
)
365 if (ae
->dest
!= EXIT_BLOCK_PTR
&& !TEST_BIT (seen
, ae
->dest
->index
))
367 SET_BIT (seen
, ae
->dest
->index
);
368 bord_bbs
[n_bord_bbs
++] = ae
->dest
;
372 /* Remove the path. */
374 if (!loop_delete_branch_edge (e
, 1))
376 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
378 /* Cancel loops contained in the path. */
379 for (i
= 0; i
< nrem
; i
++)
380 if (rem_bbs
[i
]->loop_father
->header
== rem_bbs
[i
])
381 cancel_loop_tree (loops
, rem_bbs
[i
]->loop_father
);
383 remove_bbs (rem_bbs
, nrem
);
386 /* Find blocks whose dominators may be affected. */
389 for (i
= 0; i
< n_bord_bbs
; i
++)
393 bb
= get_immediate_dominator (CDI_DOMINATORS
, bord_bbs
[i
]);
394 if (TEST_BIT (seen
, bb
->index
))
396 SET_BIT (seen
, bb
->index
);
398 for (ldom
= first_dom_son (CDI_DOMINATORS
, bb
);
400 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
401 if (!dominated_by_p (CDI_DOMINATORS
, from
, ldom
))
402 dom_bbs
[n_dom_bbs
++] = ldom
;
407 /* Recount dominators. */
408 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
411 /* These blocks have lost some predecessor(s), thus their irreducible
412 status could be changed. */
413 for (i
= 0; i
< n_bord_bbs
; i
++)
414 fix_irreducible_loops (bord_bbs
[i
]);
417 /* Fix placements of basic blocks inside loops and the placement of
418 loops in the loop tree. */
419 fix_bb_placements (loops
, from
);
420 fix_loop_placements (from
->loop_father
);
425 /* Predicate for enumeration in add_loop. */
427 alp_enum_p (basic_block bb
, void *alp_header
)
429 return bb
!= (basic_block
) alp_header
;
432 /* Given LOOP structure with filled header and latch, find the body of the
433 corresponding loop and add it to LOOPS tree. */
435 add_loop (struct loops
*loops
, struct loop
*loop
)
440 /* Add it to loop structure. */
441 place_new_loop (loops
, loop
);
444 /* Find its nodes. */
445 bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
446 n
= dfs_enumerate_from (loop
->latch
, 1, alp_enum_p
,
447 bbs
, n_basic_blocks
, loop
->header
);
449 for (i
= 0; i
< n
; i
++)
450 add_bb_to_loop (bbs
[i
], loop
);
451 add_bb_to_loop (loop
->header
, loop
);
456 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
459 scale_bbs_frequencies (basic_block
*bbs
, int nbbs
, int num
, int den
)
464 for (i
= 0; i
< nbbs
; i
++)
466 bbs
[i
]->frequency
= (bbs
[i
]->frequency
* num
) / den
;
467 bbs
[i
]->count
= (bbs
[i
]->count
* num
) / den
;
468 for (e
= bbs
[i
]->succ
; e
; e
= e
->succ_next
)
469 e
->count
= (e
->count
* num
) /den
;
473 /* Multiply all frequencies in LOOP by NUM/DEN. */
475 scale_loop_frequencies (struct loop
*loop
, int num
, int den
)
479 bbs
= get_loop_body (loop
);
480 scale_bbs_frequencies (bbs
, loop
->num_nodes
, num
, den
);
484 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
485 latch to header and update loop tree stored in LOOPS and dominators
486 accordingly. Everything between them plus LATCH_EDGE destination must
487 be dominated by HEADER_EDGE destination, and back-reachable from
488 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
489 SWITCH_BB->succ to original destination of LATCH_EDGE and
490 SWITCH_BB->succ->succ_next to original destination of HEADER_EDGE.
491 Returns newly created loop. */
493 loopify (struct loops
*loops
, edge latch_edge
, edge header_edge
, basic_block switch_bb
)
495 basic_block succ_bb
= latch_edge
->dest
;
496 basic_block pred_bb
= header_edge
->src
;
497 basic_block
*dom_bbs
, *body
;
498 unsigned n_dom_bbs
, i
;
500 struct loop
*loop
= xcalloc (1, sizeof (struct loop
));
501 struct loop
*outer
= succ_bb
->loop_father
->outer
;
502 int freq
, prob
, tot_prob
;
506 loop
->header
= header_edge
->dest
;
507 loop
->latch
= latch_edge
->src
;
509 freq
= EDGE_FREQUENCY (header_edge
);
510 cnt
= header_edge
->count
;
511 prob
= switch_bb
->succ
->probability
;
512 tot_prob
= prob
+ switch_bb
->succ
->succ_next
->probability
;
516 /* Redirect edges. */
517 loop_redirect_edge (latch_edge
, loop
->header
);
518 loop_redirect_edge (header_edge
, switch_bb
);
519 loop_redirect_edge (switch_bb
->succ
->succ_next
, loop
->header
);
520 loop_redirect_edge (switch_bb
->succ
, succ_bb
);
522 /* Update dominators. */
523 set_immediate_dominator (CDI_DOMINATORS
, switch_bb
, pred_bb
);
524 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
, switch_bb
);
525 set_immediate_dominator (CDI_DOMINATORS
, succ_bb
, switch_bb
);
527 /* Compute new loop. */
528 add_loop (loops
, loop
);
529 flow_loop_tree_node_add (outer
, loop
);
531 /* Add switch_bb to appropriate loop. */
532 add_bb_to_loop (switch_bb
, outer
);
534 /* Fix frequencies. */
535 switch_bb
->frequency
= freq
;
536 switch_bb
->count
= cnt
;
537 for (e
= switch_bb
->succ
; e
; e
= e
->succ_next
)
538 e
->count
= (switch_bb
->count
* e
->probability
) / REG_BR_PROB_BASE
;
539 scale_loop_frequencies (loop
, prob
, tot_prob
);
540 scale_loop_frequencies (succ_bb
->loop_father
, tot_prob
- prob
, tot_prob
);
542 /* Update dominators of blocks outside of LOOP. */
543 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
545 seen
= sbitmap_alloc (last_basic_block
);
547 body
= get_loop_body (loop
);
549 for (i
= 0; i
< loop
->num_nodes
; i
++)
550 SET_BIT (seen
, body
[i
]->index
);
552 for (i
= 0; i
< loop
->num_nodes
; i
++)
556 for (ldom
= first_dom_son (CDI_DOMINATORS
, body
[i
]);
558 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
559 if (!TEST_BIT (seen
, ldom
->index
))
561 SET_BIT (seen
, ldom
->index
);
562 dom_bbs
[n_dom_bbs
++] = ldom
;
566 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
575 /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
576 the LOOP was removed. After this function, original loop latch will
577 have no successor, which caller is expected to fix somehow. */
579 unloop (struct loops
*loops
, struct loop
*loop
)
584 basic_block latch
= loop
->latch
;
588 /* This is relatively straightforward. The dominators are unchanged, as
589 loop header dominates loop latch, so the only thing we have to care of
590 is the placement of loops and basic blocks inside the loop tree. We
591 move them all to the loop->outer, and then let fix_bb_placements do
594 body
= get_loop_body (loop
);
595 edges
= get_loop_exit_edges (loop
, &n_edges
);
597 for (i
= 0; i
< n
; i
++)
598 if (body
[i
]->loop_father
== loop
)
600 remove_bb_from_loops (body
[i
]);
601 add_bb_to_loop (body
[i
], loop
->outer
);
608 flow_loop_tree_node_remove (ploop
);
609 flow_loop_tree_node_add (loop
->outer
, ploop
);
612 /* Remove the loop and free its data. */
613 flow_loop_tree_node_remove (loop
);
614 loops
->parray
[loop
->num
] = NULL
;
615 flow_loop_free (loop
);
617 remove_edge (latch
->succ
);
618 fix_bb_placements (loops
, latch
);
620 /* If the loop was inside an irreducible region, we would have to somehow
621 update the irreducible marks inside its body. While it is certainly
622 possible to do, it is a bit complicated and this situation should be
623 very rare, so we just remark all loops in this case. */
624 for (i
= 0; i
< n_edges
; i
++)
625 if (edges
[i
]->flags
& EDGE_IRREDUCIBLE_LOOP
)
628 mark_irreducible_loops (loops
);
632 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
633 FATHER of LOOP such that all of the edges coming out of LOOP belong to
634 FATHER, and set it as outer loop of LOOP. Return 1 if placement of
637 fix_loop_placement (struct loop
*loop
)
642 struct loop
*father
= loop
->pred
[0], *act
;
644 body
= get_loop_body (loop
);
645 for (i
= 0; i
< loop
->num_nodes
; i
++)
646 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
647 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
649 act
= find_common_loop (loop
, e
->dest
->loop_father
);
650 if (flow_loop_nested_p (father
, act
))
655 if (father
!= loop
->outer
)
657 for (act
= loop
->outer
; act
!= father
; act
= act
->outer
)
658 act
->num_nodes
-= loop
->num_nodes
;
659 flow_loop_tree_node_remove (loop
);
660 flow_loop_tree_node_add (father
, loop
);
666 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
667 condition stated in description of fix_loop_placement holds for them.
668 It is used in case when we removed some edges coming out of LOOP, which
669 may cause the right placement of LOOP inside loop tree to change. */
671 fix_loop_placements (struct loop
*loop
)
678 if (!fix_loop_placement (loop
))
684 /* Creates place for a new LOOP in LOOPS structure. */
686 place_new_loop (struct loops
*loops
, struct loop
*loop
)
689 xrealloc (loops
->parray
, (loops
->num
+ 1) * sizeof (struct loop
*));
690 loops
->parray
[loops
->num
] = loop
;
692 loop
->num
= loops
->num
++;
695 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
696 created loop into LOOPS structure. */
698 duplicate_loop (struct loops
*loops
, struct loop
*loop
, struct loop
*target
)
701 cloop
= xcalloc (1, sizeof (struct loop
));
702 place_new_loop (loops
, cloop
);
704 /* Initialize copied loop. */
705 cloop
->level
= loop
->level
;
707 /* Set it as copy of loop. */
710 /* Add it to target. */
711 flow_loop_tree_node_add (target
, cloop
);
716 /* Copies structure of subloops of LOOP into TARGET loop, placing
717 newly created loops into loop tree stored in LOOPS. */
719 duplicate_subloops (struct loops
*loops
, struct loop
*loop
, struct loop
*target
)
721 struct loop
*aloop
, *cloop
;
723 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
725 cloop
= duplicate_loop (loops
, aloop
, target
);
726 duplicate_subloops (loops
, aloop
, cloop
);
730 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
731 into TARGET loop, placing newly created loops into loop tree LOOPS. */
733 copy_loops_to (struct loops
*loops
, struct loop
**copied_loops
, int n
, struct loop
*target
)
738 for (i
= 0; i
< n
; i
++)
740 aloop
= duplicate_loop (loops
, copied_loops
[i
], target
);
741 duplicate_subloops (loops
, copied_loops
[i
], aloop
);
745 /* Redirects edge E to basic block DEST. */
747 loop_redirect_edge (edge e
, basic_block dest
)
752 redirect_edge_and_branch_force (e
, dest
);
755 /* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set,
756 just test whether it is possible to remove the edge. */
758 loop_delete_branch_edge (edge e
, int really_delete
)
760 basic_block src
= e
->src
;
764 if (src
->succ
->succ_next
)
768 /* Cannot handle more than two exit edges. */
769 if (src
->succ
->succ_next
->succ_next
)
771 /* And it must be just a simple branch. */
772 if (!any_condjump_p (BB_END (src
)))
775 snd
= e
== src
->succ
? src
->succ
->succ_next
: src
->succ
;
777 if (newdest
== EXIT_BLOCK_PTR
)
780 /* Hopefully the above conditions should suffice. */
784 /* Redirecting behaves wrongly wrto this flag. */
785 irr
= snd
->flags
& EDGE_IRREDUCIBLE_LOOP
;
787 if (!redirect_edge_and_branch (e
, newdest
))
789 src
->succ
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
790 src
->succ
->flags
|= irr
;
796 /* Cannot happen -- we are using this only to remove an edge
801 return false; /* To avoid warning, cannot get here. */
804 /* Check whether LOOP's body can be duplicated. */
806 can_duplicate_loop_p (struct loop
*loop
)
809 basic_block
*bbs
= get_loop_body (loop
);
811 ret
= can_copy_bbs_p (bbs
, loop
->num_nodes
);
817 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
819 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
820 LOOPS structure and dominators. E's destination must be LOOP header for
821 this to work, i.e. it must be entry or latch edge of this loop; these are
822 unique, as the loops must have preheaders for this function to work
823 correctly (in case E is latch, the function unrolls the loop, if E is entry
824 edge, it peels the loop). Store edges created by copying ORIG edge from
825 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
826 original LOOP body, the other copies are numbered in order given by control
827 flow through them) into TO_REMOVE array. Returns false if duplication is
830 duplicate_loop_to_header_edge (struct loop
*loop
, edge e
, struct loops
*loops
,
831 unsigned int ndupl
, sbitmap wont_exit
,
832 edge orig
, edge
*to_remove
,
833 unsigned int *n_to_remove
, int flags
)
835 struct loop
*target
, *aloop
;
836 struct loop
**orig_loops
;
837 unsigned n_orig_loops
;
838 basic_block header
= loop
->header
, latch
= loop
->latch
;
839 basic_block
*new_bbs
, *bbs
, *first_active
;
840 basic_block new_bb
, bb
, first_active_latch
= NULL
;
842 edge spec_edges
[2], new_spec_edges
[2];
846 int is_latch
= (latch
== e
->src
);
847 int scale_act
= 0, *scale_step
= NULL
, scale_main
= 0;
848 int p
, freq_in
, freq_le
, freq_out_orig
;
849 int prob_pass_thru
, prob_pass_wont_exit
, prob_pass_main
;
850 int add_irreducible_flag
;
852 if (e
->dest
!= loop
->header
)
859 /* Orig must be edge out of the loop. */
860 if (!flow_bb_inside_loop_p (loop
, orig
->src
))
862 if (flow_bb_inside_loop_p (loop
, orig
->dest
))
866 bbs
= get_loop_body (loop
);
868 /* Check whether duplication is possible. */
869 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
874 new_bbs
= xmalloc (sizeof (basic_block
) * loop
->num_nodes
);
876 /* In case we are doing loop peeling and the loop is in the middle of
877 irreducible region, the peeled copies will be inside it too. */
878 add_irreducible_flag
= e
->flags
& EDGE_IRREDUCIBLE_LOOP
;
879 if (is_latch
&& add_irreducible_flag
)
882 /* Find edge from latch. */
883 latch_edge
= loop_latch_edge (loop
);
885 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
887 /* Calculate coefficients by that we have to scale frequencies
888 of duplicated loop bodies. */
889 freq_in
= header
->frequency
;
890 freq_le
= EDGE_FREQUENCY (latch_edge
);
893 if (freq_in
< freq_le
)
895 freq_out_orig
= orig
? EDGE_FREQUENCY (orig
) : freq_in
- freq_le
;
896 if (freq_out_orig
> freq_in
- freq_le
)
897 freq_out_orig
= freq_in
- freq_le
;
898 prob_pass_thru
= RDIV (REG_BR_PROB_BASE
* freq_le
, freq_in
);
899 prob_pass_wont_exit
=
900 RDIV (REG_BR_PROB_BASE
* (freq_le
+ freq_out_orig
), freq_in
);
902 scale_step
= xmalloc (ndupl
* sizeof (int));
904 for (i
= 1; i
<= ndupl
; i
++)
905 scale_step
[i
- 1] = TEST_BIT (wont_exit
, i
)
906 ? prob_pass_wont_exit
911 prob_pass_main
= TEST_BIT (wont_exit
, 0)
912 ? prob_pass_wont_exit
915 scale_main
= REG_BR_PROB_BASE
;
916 for (i
= 0; i
< ndupl
; i
++)
919 p
= RDIV (p
* scale_step
[i
], REG_BR_PROB_BASE
);
921 scale_main
= RDIV (REG_BR_PROB_BASE
* REG_BR_PROB_BASE
, scale_main
);
922 scale_act
= RDIV (scale_main
* prob_pass_main
, REG_BR_PROB_BASE
);
926 scale_main
= REG_BR_PROB_BASE
;
927 for (i
= 0; i
< ndupl
; i
++)
928 scale_main
= RDIV (scale_main
* scale_step
[i
], REG_BR_PROB_BASE
);
929 scale_act
= REG_BR_PROB_BASE
- prob_pass_thru
;
931 for (i
= 0; i
< ndupl
; i
++)
932 if (scale_step
[i
] < 0 || scale_step
[i
] > REG_BR_PROB_BASE
)
934 if (scale_main
< 0 || scale_main
> REG_BR_PROB_BASE
935 || scale_act
< 0 || scale_act
> REG_BR_PROB_BASE
)
939 /* Loop the new bbs will belong to. */
940 target
= e
->src
->loop_father
;
942 /* Original loops. */
944 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
946 orig_loops
= xcalloc (n_orig_loops
, sizeof (struct loop
*));
947 for (aloop
= loop
->inner
, i
= 0; aloop
; aloop
= aloop
->next
, i
++)
948 orig_loops
[i
] = aloop
;
954 first_active
= xmalloc (n
* sizeof (basic_block
));
957 memcpy (first_active
, bbs
, n
* sizeof (basic_block
));
958 first_active_latch
= latch
;
961 /* Record exit edge in original loop body. */
962 if (orig
&& TEST_BIT (wont_exit
, 0))
963 to_remove
[(*n_to_remove
)++] = orig
;
965 spec_edges
[SE_ORIG
] = orig
;
966 spec_edges
[SE_LATCH
] = latch_edge
;
968 for (j
= 0; j
< ndupl
; j
++)
971 copy_loops_to (loops
, orig_loops
, n_orig_loops
, target
);
974 copy_bbs (bbs
, n
, new_bbs
, spec_edges
, 2, new_spec_edges
, loop
);
976 /* Note whether the blocks and edges belong to an irreducible loop. */
977 if (add_irreducible_flag
)
979 for (i
= 0; i
< n
; i
++)
980 new_bbs
[i
]->rbi
->duplicated
= 1;
981 for (i
= 0; i
< n
; i
++)
984 if (new_bb
->loop_father
== target
)
985 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
987 for (ae
= new_bb
->succ
; ae
; ae
= ae
->succ_next
)
988 if (ae
->dest
->rbi
->duplicated
989 && (ae
->src
->loop_father
== target
990 || ae
->dest
->loop_father
== target
))
991 ae
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
993 for (i
= 0; i
< n
; i
++)
994 new_bbs
[i
]->rbi
->duplicated
= 0;
997 /* Redirect the special edges. */
1000 redirect_edge_and_branch_force (latch_edge
, new_bbs
[0]);
1001 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1003 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], latch
);
1004 latch
= loop
->latch
= new_bbs
[1];
1005 e
= latch_edge
= new_spec_edges
[SE_LATCH
];
1009 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1011 redirect_edge_and_branch_force (e
, new_bbs
[0]);
1012 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], e
->src
);
1013 e
= new_spec_edges
[SE_LATCH
];
1016 /* Record exit edge in this copy. */
1017 if (orig
&& TEST_BIT (wont_exit
, j
+ 1))
1018 to_remove
[(*n_to_remove
)++] = new_spec_edges
[SE_ORIG
];
1020 /* Record the first copy in the control flow order if it is not
1021 the original loop (i.e. in case of peeling). */
1022 if (!first_active_latch
)
1024 memcpy (first_active
, new_bbs
, n
* sizeof (basic_block
));
1025 first_active_latch
= new_bbs
[1];
1028 /* Set counts and frequencies. */
1029 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1031 scale_bbs_frequencies (new_bbs
, n
, scale_act
, REG_BR_PROB_BASE
);
1032 scale_act
= RDIV (scale_act
* scale_step
[j
], REG_BR_PROB_BASE
);
1038 /* Update the original loop. */
1040 set_immediate_dominator (CDI_DOMINATORS
, e
->dest
, e
->src
);
1041 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1043 scale_bbs_frequencies (bbs
, n
, scale_main
, REG_BR_PROB_BASE
);
1047 /* Update dominators of outer blocks if affected. */
1048 for (i
= 0; i
< n
; i
++)
1050 basic_block dominated
, dom_bb
, *dom_bbs
;
1054 n_dom_bbs
= get_dominated_by (CDI_DOMINATORS
, bb
, &dom_bbs
);
1055 for (j
= 0; j
< n_dom_bbs
; j
++)
1057 dominated
= dom_bbs
[j
];
1058 if (flow_bb_inside_loop_p (loop
, dominated
))
1060 dom_bb
= nearest_common_dominator (
1061 CDI_DOMINATORS
, first_active
[i
], first_active_latch
);
1062 set_immediate_dominator (CDI_DOMINATORS
, dominated
, dom_bb
);
1066 free (first_active
);
1073 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1074 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1075 entry; otherwise we also force preheader block to have only one successor.
1076 The function also updates dominators stored in DOM. */
1078 create_preheader (struct loop
*loop
, int flags
)
1082 basic_block jump
, src
= 0;
1083 struct loop
*cloop
, *ploop
;
1087 cloop
= loop
->outer
;
1089 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
1091 if (e
->src
== loop
->latch
)
1099 for (e
= loop
->header
->pred
; e
->src
== loop
->latch
; e
= e
->pred_next
);
1100 if (!(flags
& CP_SIMPLE_PREHEADERS
)
1101 || !e
->src
->succ
->succ_next
)
1105 insn
= first_insn_after_basic_block_note (loop
->header
);
1107 insn
= PREV_INSN (insn
);
1109 insn
= get_last_insn ();
1110 if (insn
== BB_END (loop
->header
))
1112 /* Split_block would not split block after its end. */
1113 emit_note_after (NOTE_INSN_DELETED
, insn
);
1115 fallthru
= split_block (loop
->header
, insn
);
1116 dummy
= fallthru
->src
;
1117 loop
->header
= fallthru
->dest
;
1119 /* The header could be a latch of some superloop(s); due to design of
1120 split_block, it would now move to fallthru->dest. */
1121 for (ploop
= loop
; ploop
; ploop
= ploop
->outer
)
1122 if (ploop
->latch
== dummy
)
1123 ploop
->latch
= fallthru
->dest
;
1125 add_to_dominance_info (CDI_DOMINATORS
, fallthru
->dest
);
1127 /* Redirect edges. */
1128 for (e
= dummy
->pred
; e
; e
= e
->pred_next
)
1131 if (src
== loop
->latch
)
1137 dummy
->frequency
-= EDGE_FREQUENCY (e
);
1138 dummy
->count
-= e
->count
;
1139 fallthru
->count
-= e
->count
;
1140 jump
= redirect_edge_and_branch_force (e
, loop
->header
);
1143 add_to_dominance_info (CDI_DOMINATORS
, jump
);
1144 set_immediate_dominator (CDI_DOMINATORS
, jump
, src
);
1145 add_bb_to_loop (jump
, loop
);
1149 /* Update structures. */
1150 redirect_immediate_dominators (CDI_DOMINATORS
, dummy
, loop
->header
);
1151 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
, dummy
);
1152 loop
->header
->loop_father
= loop
;
1153 add_bb_to_loop (dummy
, cloop
);
1155 fprintf (rtl_dump_file
, "Created preheader block for loop %i\n",
1161 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1162 of FLAGS see create_preheader. */
1164 create_preheaders (struct loops
*loops
, int flags
)
1167 for (i
= 1; i
< loops
->num
; i
++)
1168 create_preheader (loops
->parray
[i
], flags
);
1169 loops
->state
|= LOOPS_HAVE_PREHEADERS
;
1172 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1175 force_single_succ_latches (struct loops
*loops
)
1181 for (i
= 1; i
< loops
->num
; i
++)
1183 loop
= loops
->parray
[i
];
1184 if (loop
->latch
!= loop
->header
1185 && !loop
->latch
->succ
->succ_next
)
1188 for (e
= loop
->header
->pred
; e
->src
!= loop
->latch
; e
= e
->pred_next
)
1191 loop_split_edge_with (e
, NULL_RTX
);
1193 loops
->state
|= LOOPS_HAVE_SIMPLE_LATCHES
;
1196 /* A quite stupid function to put INSNS on edge E. They are supposed to form
1197 just one basic block. Jumps in INSNS are not handled, so cfg do not have to
1198 be ok after this function. The created block is placed on correct place
1199 in LOOPS structure and its dominator is set. */
1201 loop_split_edge_with (edge e
, rtx insns
)
1203 basic_block src
, dest
, new_bb
;
1204 struct loop
*loop_c
;
1210 loop_c
= find_common_loop (src
->loop_father
, dest
->loop_father
);
1212 /* Create basic block for it. */
1214 new_bb
= split_edge (e
);
1215 add_to_dominance_info (CDI_DOMINATORS
, new_bb
);
1216 add_bb_to_loop (new_bb
, loop_c
);
1217 new_bb
->flags
= insns
? BB_SUPERBLOCK
: 0;
1219 new_e
= new_bb
->succ
;
1220 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1222 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1223 new_e
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1227 emit_insn_after (insns
, BB_END (new_bb
));
1229 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, src
);
1230 set_immediate_dominator (CDI_DOMINATORS
, dest
,
1231 recount_dominator (CDI_DOMINATORS
, dest
));
1233 if (dest
->loop_father
->latch
== src
)
1234 dest
->loop_father
->latch
= new_bb
;