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
PARAMS ((struct loops
*,
33 struct loop
*, struct loop
*));
34 static void duplicate_subloops
PARAMS ((struct loops
*, struct loop
*,
36 static void copy_loops_to
PARAMS ((struct loops
*, struct loop
**,
38 static void loop_redirect_edge
PARAMS ((edge
, basic_block
));
39 static bool loop_delete_branch_edge
PARAMS ((edge
, int));
40 static void copy_bbs
PARAMS ((basic_block
*, int, edge
,
42 struct loops
*, edge
*,
44 static void remove_bbs
PARAMS ((dominance_info
, basic_block
*,
46 static bool rpe_enum_p
PARAMS ((basic_block
, void *));
47 static int find_path
PARAMS ((edge
, dominance_info
,
49 static bool alp_enum_p
PARAMS ((basic_block
, void *));
50 static void add_loop
PARAMS ((struct loops
*, struct loop
*));
51 static void fix_loop_placements
PARAMS ((struct loop
*));
52 static bool fix_bb_placement
PARAMS ((struct loops
*, basic_block
));
53 static void fix_bb_placements
PARAMS ((struct loops
*, basic_block
));
54 static void place_new_loop
PARAMS ((struct loops
*, struct loop
*));
55 static void scale_loop_frequencies
PARAMS ((struct loop
*, int, int));
56 static void scale_bbs_frequencies
PARAMS ((basic_block
*, int, int, int));
57 static void record_exit_edges
PARAMS ((edge
, basic_block
*, int,
58 edge
*, unsigned *, int));
59 static basic_block create_preheader
PARAMS ((struct loop
*, dominance_info
,
61 static void fix_irreducible_loops
PARAMS ((basic_block
));
63 /* Splits basic block BB after INSN, returns created edge. Updates loops
66 split_loop_bb (loops
, bb
, insn
)
75 /* Split the block. */
76 e
= split_block (bb
, insn
);
78 /* Add dest to loop. */
79 add_bb_to_loop (e
->dest
, e
->src
->loop_father
);
82 add_to_dominance_info (loops
->cfg
.dom
, e
->dest
);
83 n_dom_bbs
= get_dominated_by (loops
->cfg
.dom
, e
->src
, &dom_bbs
);
84 for (i
= 0; i
< n_dom_bbs
; i
++)
85 set_immediate_dominator (loops
->cfg
.dom
, dom_bbs
[i
], e
->dest
);
87 set_immediate_dominator (loops
->cfg
.dom
, e
->dest
, e
->src
);
92 /* Checks whether basic block BB is dominated by RPE->DOM, where
93 RPE is passed through DATA. */
101 rpe_enum_p (bb
, data
)
105 struct rpe_data
*rpe
= data
;
106 return dominated_by_p (rpe
->doms
, bb
, rpe
->dom
);
109 /* Remove basic blocks BBS from loop structure and dominance info,
110 and delete them afterwards. */
112 remove_bbs (dom
, bbs
, nbbs
)
119 for (i
= 0; i
< nbbs
; i
++)
121 remove_bb_from_loops (bbs
[i
]);
122 delete_from_dominance_info (dom
, bbs
[i
]);
123 delete_block (bbs
[i
]);
127 /* Find path -- i.e. the basic blocks dominated by edge E and put them
128 into array BBS, that will be allocated large enough to contain them.
129 E->dest must have exactly one predecessor for this to work (it is
130 easy to achieve and we do not put it here because we do not want to
131 alter anything by this function). The number of basic blocks in the
134 find_path (e
, doms
, bbs
)
141 if (e
->dest
->pred
->pred_next
)
144 /* Find bbs in the path. */
147 *bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
148 return dfs_enumerate_from (e
->dest
, 0, rpe_enum_p
, *bbs
,
149 n_basic_blocks
, &rpe
);
152 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
153 Let L be a loop to that BB belongs. Then every successor of BB must either
154 1) belong to some superloop of loop L, or
155 2) be a header of loop K such that K->outer is superloop of L
156 Returns true if we had to move BB into other loop to enforce this condition,
157 false if the placement of BB was already correct (provided that placements
158 of its successors are correct). */
160 fix_bb_placement (loops
, bb
)
165 struct loop
*loop
= loops
->tree_root
, *act
;
167 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
169 if (e
->dest
== EXIT_BLOCK_PTR
)
172 act
= e
->dest
->loop_father
;
173 if (act
->header
== e
->dest
)
176 if (flow_loop_nested_p (loop
, act
))
180 if (loop
== bb
->loop_father
)
183 remove_bb_from_loops (bb
);
184 add_bb_to_loop (bb
, loop
);
189 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
190 enforce condition condition stated in description of fix_bb_placement. We
191 start from basic block FROM that had some of its successors removed, so that
192 his placement no longer has to be correct, and iteratively fix placement of
193 its predecessors that may change if placement of FROM changed. Also fix
194 placement of subloops of FROM->loop_father, that might also be altered due
195 to this change; the condition for them is simmilar, except that instead of
196 successors we consider edges coming out of the loops. */
198 fix_bb_placements (loops
, from
)
203 basic_block
*queue
, *qtop
, *qbeg
, *qend
;
204 struct loop
*base_loop
;
207 /* We pass through blocks back-reachable from FROM, testing whether some
208 of their successors moved to outer loop. It may be necessary to
209 iterate several times, but it is finite, as we stop unless we move
210 the basic block up the loop structure. The whole story is a bit
211 more complicated due to presence of subloops, those are moved using
212 fix_loop_placement. */
214 base_loop
= from
->loop_father
;
215 if (base_loop
== loops
->tree_root
)
218 in_queue
= sbitmap_alloc (last_basic_block
);
219 sbitmap_zero (in_queue
);
220 SET_BIT (in_queue
, from
->index
);
221 /* Prevent us from going out of the base_loop. */
222 SET_BIT (in_queue
, base_loop
->header
->index
);
224 queue
= xmalloc ((base_loop
->num_nodes
+ 1) * sizeof (basic_block
));
225 qtop
= queue
+ base_loop
->num_nodes
+ 1;
236 RESET_BIT (in_queue
, from
->index
);
238 if (from
->loop_father
->header
== from
)
240 /* Subloop header, maybe move the loop upward. */
241 if (!fix_loop_placement (from
->loop_father
))
246 /* Ordinary basic block. */
247 if (!fix_bb_placement (loops
, from
))
251 /* Something has changed, insert predecessors into queue. */
252 for (e
= from
->pred
; e
; e
= e
->pred_next
)
254 basic_block pred
= e
->src
;
257 if (TEST_BIT (in_queue
, pred
->index
))
260 /* If it is subloop, then it either was not moved, or
261 the path up the loop tree from base_loop do not contain
263 nca
= find_common_loop (pred
->loop_father
, base_loop
);
264 if (pred
->loop_father
!= base_loop
266 || nca
!= pred
->loop_father
))
267 pred
= pred
->loop_father
->header
;
268 else if (!flow_loop_nested_p (from
->loop_father
, pred
->loop_father
))
270 /* No point in processing it. */
274 if (TEST_BIT (in_queue
, pred
->index
))
277 /* Schedule the basic block. */
282 SET_BIT (in_queue
, pred
->index
);
289 /* Basic block from has lost one or more of its predecessors, so it might
290 mo longer be part irreducible loop. Fix it and proceed recursively
291 for its successors if needed. */
293 fix_irreducible_loops (from
)
303 if (!(from
->flags
& BB_IRREDUCIBLE_LOOP
))
306 on_stack
= sbitmap_alloc (last_basic_block
);
307 sbitmap_zero (on_stack
);
308 SET_BIT (on_stack
, from
->index
);
309 stack
= xmalloc (from
->loop_father
->num_nodes
* sizeof (basic_block
));
315 bb
= stack
[--stack_top
];
316 RESET_BIT (on_stack
, bb
->index
);
318 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
319 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
324 bb
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
325 if (bb
->loop_father
->header
== bb
)
326 edges
= get_loop_exit_edges (bb
->loop_father
, &n_edges
);
330 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
332 edges
= xmalloc (n_edges
* sizeof (edge
));
334 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
335 edges
[n_edges
++] = e
;
338 for (i
= 0; i
< n_edges
; i
++)
339 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
341 if (!flow_bb_inside_loop_p (from
->loop_father
, e
->dest
))
344 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
345 if (TEST_BIT (on_stack
, e
->dest
->index
))
348 SET_BIT (on_stack
, e
->dest
->index
);
349 stack
[stack_top
++] = e
->dest
;
358 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
359 and update loop structure stored in LOOPS and dominators. Return true if
360 we were able to remove the path, false otherwise (and nothing is affected
363 remove_path (loops
, e
)
368 basic_block
*rem_bbs
, *bord_bbs
, *dom_bbs
, from
, bb
;
369 int i
, nrem
, n_bord_bbs
, n_dom_bbs
;
372 if (!loop_delete_branch_edge (e
, 0))
375 /* We need to check whether basic blocks are dominated by the edge
376 e, but we only have basic block dominators. This is easy to
377 fix -- when e->dest has exactly one predecessor, this corresponds
378 to blocks dominated by e->dest, if not, split the edge. */
379 if (e
->dest
->pred
->pred_next
)
380 e
= loop_split_edge_with (e
, NULL_RTX
, loops
)->pred
;
382 /* It may happen that by removing path we remove one or more loops
383 we belong to. In this case first unloop the loops, then proceed
384 normally. We may assume that e->dest is not a header of any loop,
385 as it now has exactly one predecessor. */
386 while (e
->src
->loop_father
->outer
387 && dominated_by_p (loops
->cfg
.dom
,
388 e
->src
->loop_father
->latch
, e
->dest
))
389 unloop (loops
, e
->src
->loop_father
);
391 /* Identify the path. */
392 nrem
= find_path (e
, loops
->cfg
.dom
, &rem_bbs
);
395 bord_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
396 seen
= sbitmap_alloc (last_basic_block
);
399 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
400 for (i
= 0; i
< nrem
; i
++)
401 SET_BIT (seen
, rem_bbs
[i
]->index
);
402 for (i
= 0; i
< nrem
; i
++)
405 for (ae
= rem_bbs
[i
]->succ
; ae
; ae
= ae
->succ_next
)
406 if (ae
->dest
!= EXIT_BLOCK_PTR
&& !TEST_BIT (seen
, ae
->dest
->index
))
408 SET_BIT (seen
, ae
->dest
->index
);
409 bord_bbs
[n_bord_bbs
++] = ae
->dest
;
413 /* Remove the path. */
415 if (!loop_delete_branch_edge (e
, 1))
417 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
419 /* Cancel loops contained in the path. */
420 for (i
= 0; i
< nrem
; i
++)
421 if (rem_bbs
[i
]->loop_father
->header
== rem_bbs
[i
])
422 cancel_loop_tree (loops
, rem_bbs
[i
]->loop_father
);
424 remove_bbs (loops
->cfg
.dom
, rem_bbs
, nrem
);
427 /* Find blocks whose dominators may be affected. */
430 for (i
= 0; i
< n_bord_bbs
; i
++)
435 bb
= get_immediate_dominator (loops
->cfg
.dom
, bord_bbs
[i
]);
436 if (TEST_BIT (seen
, bb
->index
))
438 SET_BIT (seen
, bb
->index
);
440 nldom
= get_dominated_by (loops
->cfg
.dom
, bb
, &ldom
);
441 for (j
= 0; j
< nldom
; j
++)
442 if (!dominated_by_p (loops
->cfg
.dom
, from
, ldom
[j
]))
443 dom_bbs
[n_dom_bbs
++] = ldom
[j
];
449 /* Recount dominators. */
450 iterate_fix_dominators (loops
->cfg
.dom
, dom_bbs
, n_dom_bbs
);
453 /* These blocks have lost some predecessor(s), thus their irreducible
454 status could be changed. */
455 for (i
= 0; i
< n_bord_bbs
; i
++)
456 fix_irreducible_loops (bord_bbs
[i
]);
459 /* Fix placements of basic blocks inside loops and the placement of
460 loops in the loop tree. */
461 fix_bb_placements (loops
, from
);
462 fix_loop_placements (from
->loop_father
);
467 /* Predicate for enumeration in add_loop. */
469 alp_enum_p (bb
, alp_header
)
473 return bb
!= (basic_block
) alp_header
;
476 /* Given LOOP structure with filled header and latch, find the body of the
477 corresponding loop and add it to LOOPS tree. */
479 add_loop (loops
, loop
)
486 /* Add it to loop structure. */
487 place_new_loop (loops
, loop
);
490 /* Find its nodes. */
491 bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
492 n
= dfs_enumerate_from (loop
->latch
, 1, alp_enum_p
,
493 bbs
, n_basic_blocks
, loop
->header
);
495 for (i
= 0; i
< n
; i
++)
496 add_bb_to_loop (bbs
[i
], loop
);
497 add_bb_to_loop (loop
->header
, loop
);
502 /* Multiply all frequencies of basic blocks in array BBS of lenght NBBS
505 scale_bbs_frequencies (bbs
, nbbs
, num
, den
)
514 for (i
= 0; i
< nbbs
; i
++)
516 bbs
[i
]->frequency
= (bbs
[i
]->frequency
* num
) / den
;
517 bbs
[i
]->count
= (bbs
[i
]->count
* num
) / den
;
518 for (e
= bbs
[i
]->succ
; e
; e
= e
->succ_next
)
519 e
->count
= (e
->count
* num
) /den
;
523 /* Multiply all frequencies in LOOP by NUM/DEN. */
525 scale_loop_frequencies (loop
, num
, den
)
532 bbs
= get_loop_body (loop
);
533 scale_bbs_frequencies (bbs
, loop
->num_nodes
, num
, den
);
537 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
538 latch to header and update loop tree stored in LOOPS and dominators
539 accordingly. Everything between them plus LATCH_EDGE destination must
540 be dominated by HEADER_EDGE destination, and back-reachable from
541 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
542 SWITCH_BB->succ to original destination of LATCH_EDGE and
543 SWITCH_BB->succ->succ_next to original destination of HEADER_EDGE.
544 Returns newly created loop. */
546 loopify (loops
, latch_edge
, header_edge
, switch_bb
)
550 basic_block switch_bb
;
552 basic_block succ_bb
= latch_edge
->dest
;
553 basic_block pred_bb
= header_edge
->src
;
554 basic_block
*dom_bbs
, *body
;
555 unsigned n_dom_bbs
, i
, j
;
557 struct loop
*loop
= xcalloc (1, sizeof (struct loop
));
558 struct loop
*outer
= succ_bb
->loop_father
->outer
;
559 int freq
, prob
, tot_prob
;
563 loop
->header
= header_edge
->dest
;
564 loop
->latch
= latch_edge
->src
;
566 freq
= EDGE_FREQUENCY (header_edge
);
567 cnt
= header_edge
->count
;
568 prob
= switch_bb
->succ
->probability
;
569 tot_prob
= prob
+ switch_bb
->succ
->succ_next
->probability
;
573 /* Redirect edges. */
574 loop_redirect_edge (latch_edge
, loop
->header
);
575 loop_redirect_edge (header_edge
, switch_bb
);
576 loop_redirect_edge (switch_bb
->succ
->succ_next
, loop
->header
);
577 loop_redirect_edge (switch_bb
->succ
, succ_bb
);
579 /* Update dominators. */
580 set_immediate_dominator (loops
->cfg
.dom
, switch_bb
, pred_bb
);
581 set_immediate_dominator (loops
->cfg
.dom
, loop
->header
, switch_bb
);
582 set_immediate_dominator (loops
->cfg
.dom
, succ_bb
, switch_bb
);
584 /* Compute new loop. */
585 add_loop (loops
, loop
);
586 flow_loop_tree_node_add (outer
, loop
);
588 /* Add switch_bb to appropriate loop. */
589 add_bb_to_loop (switch_bb
, outer
);
591 /* Fix frequencies. */
592 switch_bb
->frequency
= freq
;
593 switch_bb
->count
= cnt
;
594 for (e
= switch_bb
->succ
; e
; e
= e
->succ_next
)
595 e
->count
= (switch_bb
->count
* e
->probability
) / REG_BR_PROB_BASE
;
596 scale_loop_frequencies (loop
, prob
, tot_prob
);
597 scale_loop_frequencies (succ_bb
->loop_father
, tot_prob
- prob
, tot_prob
);
599 /* Update dominators of blocks outside of LOOP. */
600 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
602 seen
= sbitmap_alloc (last_basic_block
);
604 body
= get_loop_body (loop
);
606 for (i
= 0; i
< loop
->num_nodes
; i
++)
607 SET_BIT (seen
, body
[i
]->index
);
609 for (i
= 0; i
< loop
->num_nodes
; i
++)
614 nldom
= get_dominated_by (loops
->cfg
.dom
, body
[i
], &ldom
);
615 for (j
= 0; j
< nldom
; j
++)
616 if (!TEST_BIT (seen
, ldom
[j
]->index
))
618 SET_BIT (seen
, ldom
[j
]->index
);
619 dom_bbs
[n_dom_bbs
++] = ldom
[j
];
624 iterate_fix_dominators (loops
->cfg
.dom
, dom_bbs
, n_dom_bbs
);
633 /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
634 the LOOP was removed. After this function, original loop latch will
635 have no successor, which caller is expected to fix somehow. */
644 basic_block latch
= loop
->latch
;
648 /* This is relatively straigtforward. The dominators are unchanged, as
649 loop header dominates loop latch, so the only thing we have to care of
650 is the placement of loops and basic blocks inside the loop tree. We
651 move them all to the loop->outer, and then let fix_bb_placements do
654 body
= get_loop_body (loop
);
655 edges
= get_loop_exit_edges (loop
, &n_edges
);
657 for (i
= 0; i
< n
; i
++)
658 if (body
[i
]->loop_father
== loop
)
660 remove_bb_from_loops (body
[i
]);
661 add_bb_to_loop (body
[i
], loop
->outer
);
668 flow_loop_tree_node_remove (ploop
);
669 flow_loop_tree_node_add (loop
->outer
, ploop
);
672 /* Remove the loop and free its data. */
673 flow_loop_tree_node_remove (loop
);
674 loops
->parray
[loop
->num
] = NULL
;
675 flow_loop_free (loop
);
677 remove_edge (latch
->succ
);
678 fix_bb_placements (loops
, latch
);
680 /* If the loop was inside an irreducible region, we would have to somehow
681 update the irreducible marks inside its body. While it is certainly
682 possible to do, it is a bit complicated and this situation should be
683 very rare, so we just remark all loops in this case. */
684 for (i
= 0; i
< n_edges
; i
++)
685 if (edges
[i
]->flags
& EDGE_IRREDUCIBLE_LOOP
)
688 mark_irreducible_loops (loops
);
692 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
693 FATHER of LOOP such that all of the edges comming out of LOOP belong to
694 FATHER, and set it as outer loop of LOOP. Return 1 if placement of
697 fix_loop_placement (loop
)
703 struct loop
*father
= loop
->pred
[0], *act
;
705 body
= get_loop_body (loop
);
706 for (i
= 0; i
< loop
->num_nodes
; i
++)
707 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
708 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
710 act
= find_common_loop (loop
, e
->dest
->loop_father
);
711 if (flow_loop_nested_p (father
, act
))
716 if (father
!= loop
->outer
)
718 for (act
= loop
->outer
; act
!= father
; act
= act
->outer
)
719 act
->num_nodes
-= loop
->num_nodes
;
720 flow_loop_tree_node_remove (loop
);
721 flow_loop_tree_node_add (father
, loop
);
727 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
728 condition stated in description of fix_loop_placement holds for them.
729 It is used in case when we removed some edges coming out of LOOP, which
730 may cause the right placement of LOOP inside loop tree to change. */
732 fix_loop_placements (loop
)
740 if (!fix_loop_placement (loop
))
746 /* Creates place for a new LOOP in LOOPS structure. */
748 place_new_loop (loops
, loop
)
753 xrealloc (loops
->parray
, (loops
->num
+ 1) * sizeof (struct loop
*));
754 loops
->parray
[loops
->num
] = loop
;
756 loop
->num
= loops
->num
++;
759 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
760 created loop into LOOPS structure. */
762 duplicate_loop (loops
, loop
, target
)
768 cloop
= xcalloc (1, sizeof (struct loop
));
769 place_new_loop (loops
, cloop
);
771 /* Initialize copied loop. */
772 cloop
->level
= loop
->level
;
774 /* Set it as copy of loop. */
777 /* Add it to target. */
778 flow_loop_tree_node_add (target
, cloop
);
783 /* Copies structure of subloops of LOOP into TARGET loop, placing
784 newly created loops into loop tree stored in LOOPS. */
786 duplicate_subloops (loops
, loop
, target
)
791 struct loop
*aloop
, *cloop
;
793 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
795 cloop
= duplicate_loop (loops
, aloop
, target
);
796 duplicate_subloops (loops
, aloop
, cloop
);
800 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
801 into TARGET loop, placing newly created loops into loop tree LOOPS. */
803 copy_loops_to (loops
, copied_loops
, n
, target
)
805 struct loop
**copied_loops
;
812 for (i
= 0; i
< n
; i
++)
814 aloop
= duplicate_loop (loops
, copied_loops
[i
], target
);
815 duplicate_subloops (loops
, copied_loops
[i
], aloop
);
819 /* Redirects edge E to basic block DEST. */
821 loop_redirect_edge (e
, dest
)
828 redirect_edge_and_branch_force (e
, dest
);
831 /* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set,
832 just test whether it is possible to remove the edge. */
834 loop_delete_branch_edge (e
, really_delete
)
838 basic_block src
= e
->src
;
842 if (src
->succ
->succ_next
)
846 /* Cannot handle more than two exit edges. */
847 if (src
->succ
->succ_next
->succ_next
)
849 /* And it must be just a simple branch. */
850 if (!any_condjump_p (src
->end
))
853 snd
= e
== src
->succ
? src
->succ
->succ_next
: src
->succ
;
855 if (newdest
== EXIT_BLOCK_PTR
)
858 /* Hopefully the above conditions should suffice. */
862 /* Redirecting behaves wrongly wrto this flag. */
863 irr
= snd
->flags
& EDGE_IRREDUCIBLE_LOOP
;
865 if (!redirect_edge_and_branch (e
, newdest
))
867 src
->succ
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
868 src
->succ
->flags
|= irr
;
874 /* Cannot happen -- we are using this only to remove an edge
879 return false; /* To avoid warning, cannot get here. */
882 /* Duplicates N basic blocks stored in array BBS (they form a body of
883 duplicated loop). Newly created basic blocks are placed into array NEW_BBS
884 that we allocate. Edges from basic blocks in BBS are also duplicated and
885 copies of those of them that lead into BBS are redirected to appropriate
886 newly created block. The function also assigns bbs into loops and updates
887 dominators. If ADD_IRREDUCIBLE_FLAG is set, newly created basic blocks that
888 are not members of any inner loop are marked irreducible.
890 Additionally, we perform following manipulation with edges:
891 We have two special edges given. LATCH_EDGE is the latch edge of the
892 duplicated loop and leads into its header (one of blocks in BBS);
893 it does not have neccessarily lead from one of the blocks, because
894 we may be copying the loop body several times in unrolling.
895 Edge ENTRY leads also leads to header, and it is either latch or entry
896 edge. Copy of LATCH_EDGE is redirected to header and is stored in
897 HEADER_EDGE, the ENTRY edge is redirected into copy of header and
898 returned as COPY_HEADER_EDGE. The effect is following:
899 if LATCH_EDGE == ENTRY, then the loop is unrolled by one copy,
900 HEADER_EDGE is latch of a new loop, COPY_HEADER_EDGE leads from original
901 latch source to first block in copy.
902 if LATCH_EDGE != ENTRY, then the loop is peeled by one copy,
903 HEADER_EDGE is entry edge of the loop, COPY_HEADER_EDGE leads from
904 original entry block to first block in peeled copy.
907 copy_bbs (bbs
, n
, entry
, latch_edge
, new_bbs
, loops
, header_edge
, copy_header_edge
, add_irreducible_flag
)
912 basic_block
**new_bbs
;
915 edge
*copy_header_edge
;
916 int add_irreducible_flag
;
919 basic_block bb
, new_bb
, header
= entry
->dest
, dom_bb
;
922 /* Duplicate bbs, update dominators, assign bbs to loops. */
923 (*new_bbs
) = xcalloc (n
, sizeof (basic_block
));
924 for (i
= 0; i
< n
; i
++)
928 new_bb
= (*new_bbs
)[i
] = cfg_layout_duplicate_bb (bb
, NULL
);
929 RBI (new_bb
)->duplicated
= 1;
931 add_bb_to_loop (new_bb
, bb
->loop_father
->copy
);
932 add_to_dominance_info (loops
->cfg
.dom
, new_bb
);
933 /* Possibly set header. */
934 if (bb
->loop_father
->header
== bb
&& bb
!= header
)
935 new_bb
->loop_father
->header
= new_bb
;
937 if (bb
->loop_father
->latch
== bb
&&
938 bb
->loop_father
!= header
->loop_father
)
939 new_bb
->loop_father
->latch
= new_bb
;
940 /* Take care of irreducible loops. */
941 if (add_irreducible_flag
942 && bb
->loop_father
== header
->loop_father
)
943 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
946 /* Set dominators. */
947 for (i
= 0; i
< n
; i
++)
950 new_bb
= (*new_bbs
)[i
];
953 /* For anything else than loop header, just copy it. */
954 dom_bb
= get_immediate_dominator (loops
->cfg
.dom
, bb
);
955 dom_bb
= RBI (dom_bb
)->copy
;
959 /* Copy of header is dominated by entry source. */
964 set_immediate_dominator (loops
->cfg
.dom
, new_bb
, dom_bb
);
967 /* Redirect edges. */
968 for (i
= 0; i
< n
; i
++)
971 new_bb
= (*new_bbs
)[i
];
973 for (e
= bb
->pred
; e
; e
= e_pred
)
975 basic_block src
= e
->src
;
977 e_pred
= e
->pred_next
;
979 if (!RBI (src
)->duplicated
)
982 /* Leads to copied loop and it is not latch edge, redirect it. */
984 loop_redirect_edge (e
, new_bb
);
986 if (add_irreducible_flag
987 && (bb
->loop_father
== header
->loop_father
988 || RBI (src
)->original
->loop_father
== header
->loop_father
))
989 e
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
993 /* Redirect header edge. */
994 bb
= RBI (latch_edge
->src
)->copy
;
995 for (e
= bb
->succ
; e
->dest
!= latch_edge
->dest
; e
= e
->succ_next
);
997 loop_redirect_edge (*header_edge
, header
);
999 /* Redirect entry to copy of header. */
1000 loop_redirect_edge (entry
, RBI (header
)->copy
);
1001 *copy_header_edge
= entry
;
1003 /* Clear information about duplicates. */
1004 for (i
= 0; i
< n
; i
++)
1005 RBI ((*new_bbs
)[i
])->duplicated
= 0;
1008 /* Check whether LOOP's body can be duplicated. */
1010 can_duplicate_loop_p (loop
)
1016 bbs
= get_loop_body (loop
);
1018 for (i
= 0; i
< loop
->num_nodes
; i
++)
1022 /* In case loop contains abnormal edge we can not redirect,
1023 we can't perform duplication. */
1025 for (e
= bbs
[i
]->succ
; e
; e
= e
->succ_next
)
1026 if ((e
->flags
& EDGE_ABNORMAL
)
1027 && flow_bb_inside_loop_p (loop
, e
->dest
))
1033 if (!cfg_layout_can_duplicate_bb_p (bbs
[i
]))
1044 /* Record edges, leading from NBBS basic blocks stored in BBS, that were created
1045 by copying ORIG edge (or just ORIG edge if IS_ORIG is set).
1046 If ORIG is NULL, then record all edges coming outside of BBS. Store them
1047 into TO_REMOVE array that must be large enough to hold them all; their
1048 number is returned in N_TO_REMOVE. */
1050 record_exit_edges (orig
, bbs
, nbbs
, to_remove
, n_to_remove
, is_orig
)
1055 unsigned *n_to_remove
;
1066 to_remove
[(*n_to_remove
)++] = orig
;
1070 for (e
= RBI (orig
->src
)->copy
->succ
; e
; e
= e
->succ_next
)
1071 if (e
->dest
== orig
->dest
)
1076 to_remove
[(*n_to_remove
)++] = e
;
1080 my_blocks
= sbitmap_alloc (last_basic_block
);
1081 sbitmap_zero (my_blocks
);
1082 for (i
= 0; i
< nbbs
; i
++)
1083 SET_BIT (my_blocks
, bbs
[i
]->index
);
1085 for (i
= 0; i
< nbbs
; i
++)
1086 for (e
= bbs
[i
]->succ
; e
; e
= e
->succ_next
)
1087 if (e
->dest
== EXIT_BLOCK_PTR
||
1088 !TEST_BIT (my_blocks
, e
->dest
->index
))
1089 to_remove
[(*n_to_remove
)++] = e
;
1096 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
1098 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of
1099 updating LOOPS structure and dominators. E's destination must be LOOP
1100 header for this to work, i.e. it must be entry or latch edge of this loop;
1101 these are unique, as the loops must have preheaders for this function to
1102 work correctly (in case E is latch, the function unrolls the loop, if E is
1103 entry edge, it peels the loop). Store edges created by copying ORIG edge
1104 (if NULL, then all edges leaving loop) from copies corresponding to set
1105 bits in WONT_EXIT bitmap (bit 0 corresponds to original LOOP body, the
1106 other copies are numbered in order given by control flow through them)
1107 into TO_REMOVE array. Returns false if duplication is impossible. */
1109 duplicate_loop_to_header_edge (loop
, e
, loops
, ndupl
, wont_exit
, orig
,
1110 to_remove
, n_to_remove
, flags
)
1113 struct loops
*loops
;
1118 unsigned *n_to_remove
;
1121 struct loop
*target
, *aloop
;
1122 struct loop
**orig_loops
;
1123 unsigned n_orig_loops
;
1124 basic_block header
= loop
->header
, latch
= loop
->latch
;
1125 basic_block
*new_bbs
, *bbs
, *first_active
;
1126 basic_block new_bb
, bb
, first_active_latch
= NULL
;
1127 edge ae
, latch_edge
, he
;
1129 int is_latch
= (latch
== e
->src
);
1130 int scale_act
= 0, *scale_step
= NULL
, scale_main
= 0;
1131 int p
, freq_in
, freq_le
, freq_out_orig
;
1132 int prob_pass_thru
, prob_pass_wont_exit
, prob_pass_main
;
1133 int add_irreducible_flag
;
1135 if (e
->dest
!= loop
->header
)
1142 /* Orig must be edge out of the loop. */
1143 if (!flow_bb_inside_loop_p (loop
, orig
->src
))
1145 if (flow_bb_inside_loop_p (loop
, orig
->dest
))
1149 bbs
= get_loop_body (loop
);
1151 /* Check whether duplication is possible. */
1153 for (i
= 0; i
< loop
->num_nodes
; i
++)
1155 if (!cfg_layout_can_duplicate_bb_p (bbs
[i
]))
1162 add_irreducible_flag
= !is_latch
&& (e
->flags
& EDGE_IRREDUCIBLE_LOOP
);
1164 /* Find edge from latch. */
1165 latch_edge
= loop_latch_edge (loop
);
1167 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1169 /* Calculate coefficients by that we have to scale frequencies
1170 of duplicated loop bodies. */
1171 freq_in
= header
->frequency
;
1172 freq_le
= EDGE_FREQUENCY (latch_edge
);
1175 if (freq_in
< freq_le
)
1177 freq_out_orig
= orig
? EDGE_FREQUENCY (orig
) : freq_in
- freq_le
;
1178 if (freq_out_orig
> freq_in
- freq_le
)
1179 freq_out_orig
= freq_in
- freq_le
;
1180 prob_pass_thru
= RDIV (REG_BR_PROB_BASE
* freq_le
, freq_in
);
1181 prob_pass_wont_exit
=
1182 RDIV (REG_BR_PROB_BASE
* (freq_le
+ freq_out_orig
), freq_in
);
1184 scale_step
= xmalloc (ndupl
* sizeof (int));
1186 for (i
= 1; i
<= ndupl
; i
++)
1187 scale_step
[i
- 1] = TEST_BIT (wont_exit
, i
)
1188 ? prob_pass_wont_exit
1193 prob_pass_main
= TEST_BIT (wont_exit
, 0)
1194 ? prob_pass_wont_exit
1197 scale_main
= REG_BR_PROB_BASE
;
1198 for (i
= 0; i
< ndupl
; i
++)
1201 p
= RDIV (p
* scale_step
[i
], REG_BR_PROB_BASE
);
1203 scale_main
= RDIV (REG_BR_PROB_BASE
* REG_BR_PROB_BASE
, scale_main
);
1204 scale_act
= RDIV (scale_main
* prob_pass_main
, REG_BR_PROB_BASE
);
1208 scale_main
= REG_BR_PROB_BASE
;
1209 for (i
= 0; i
< ndupl
; i
++)
1210 scale_main
= RDIV (scale_main
* scale_step
[i
], REG_BR_PROB_BASE
);
1211 scale_act
= REG_BR_PROB_BASE
- prob_pass_thru
;
1213 for (i
= 0; i
< ndupl
; i
++)
1214 if (scale_step
[i
] < 0 || scale_step
[i
] > REG_BR_PROB_BASE
)
1216 if (scale_main
< 0 || scale_main
> REG_BR_PROB_BASE
1217 || scale_act
< 0 || scale_act
> REG_BR_PROB_BASE
)
1221 /* Loop the new bbs will belong to. */
1222 target
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1224 /* Original loops. */
1226 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
1228 orig_loops
= xcalloc (n_orig_loops
, sizeof (struct loop
*));
1229 for (aloop
= loop
->inner
, i
= 0; aloop
; aloop
= aloop
->next
, i
++)
1230 orig_loops
[i
] = aloop
;
1232 loop
->copy
= target
;
1234 /* Original basic blocks. */
1235 n
= loop
->num_nodes
;
1237 first_active
= xcalloc(n
, sizeof (basic_block
));
1240 memcpy (first_active
, bbs
, n
* sizeof (basic_block
));
1241 first_active_latch
= latch
;
1244 /* Record exit edges in original loop body. */
1245 if (TEST_BIT (wont_exit
, 0))
1246 record_exit_edges (orig
, bbs
, n
, to_remove
, n_to_remove
, true);
1248 for (j
= 0; j
< ndupl
; j
++)
1251 copy_loops_to (loops
, orig_loops
, n_orig_loops
, target
);
1254 copy_bbs (bbs
, n
, e
, latch_edge
, &new_bbs
, loops
,
1255 &e
, &he
, add_irreducible_flag
);
1257 loop
->latch
= RBI (latch
)->copy
;
1259 /* Record exit edges in this copy. */
1260 if (TEST_BIT (wont_exit
, j
+ 1))
1261 record_exit_edges (orig
, new_bbs
, n
, to_remove
, n_to_remove
, false);
1263 /* Set counts and frequencies. */
1264 for (i
= 0; i
< n
; i
++)
1266 new_bb
= new_bbs
[i
];
1269 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1271 new_bb
->count
= RDIV (scale_act
* bb
->count
, REG_BR_PROB_BASE
);
1272 new_bb
->frequency
= RDIV (scale_act
* bb
->frequency
,
1277 new_bb
->count
= bb
->count
;
1278 new_bb
->frequency
= bb
->frequency
;
1281 for (ae
= new_bb
->succ
; ae
; ae
= ae
->succ_next
)
1282 ae
->count
= RDIV (new_bb
->count
* ae
->probability
,
1285 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1286 scale_act
= RDIV (scale_act
* scale_step
[j
], REG_BR_PROB_BASE
);
1288 if (!first_active_latch
)
1290 memcpy (first_active
, new_bbs
, n
* sizeof (basic_block
));
1291 first_active_latch
= RBI (latch
)->copy
;
1296 /* Original loop header is dominated by latch copy
1297 if we duplicated on its only entry edge. */
1298 if (!is_latch
&& !header
->pred
->pred_next
->pred_next
)
1299 set_immediate_dominator (loops
->cfg
.dom
, header
, RBI (latch
)->copy
);
1300 if (is_latch
&& j
== 0)
1302 /* Update edge from latch. */
1303 for (latch_edge
= RBI (header
)->copy
->pred
;
1304 latch_edge
->src
!= latch
;
1305 latch_edge
= latch_edge
->pred_next
);
1308 /* Now handle original loop. */
1310 /* Update edge counts. */
1311 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1313 for (i
= 0; i
< n
; i
++)
1316 bb
->count
= RDIV (scale_main
* bb
->count
, REG_BR_PROB_BASE
);
1317 bb
->frequency
= RDIV (scale_main
* bb
->frequency
, REG_BR_PROB_BASE
);
1318 for (ae
= bb
->succ
; ae
; ae
= ae
->succ_next
)
1319 ae
->count
= RDIV (bb
->count
* ae
->probability
, REG_BR_PROB_BASE
);
1325 /* Update dominators of other blocks if affected. */
1326 for (i
= 0; i
< n
; i
++)
1328 basic_block dominated
, dom_bb
, *dom_bbs
;
1332 n_dom_bbs
= get_dominated_by (loops
->cfg
.dom
, bb
, &dom_bbs
);
1333 for (j
= 0; j
< n_dom_bbs
; j
++)
1335 dominated
= dom_bbs
[j
];
1336 if (flow_bb_inside_loop_p (loop
, dominated
))
1338 dom_bb
= nearest_common_dominator (
1339 loops
->cfg
.dom
, first_active
[i
], first_active_latch
);
1340 set_immediate_dominator (loops
->cfg
.dom
, dominated
, dom_bb
);
1344 free (first_active
);
1351 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1352 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1353 entry; otherwise we also force preheader block to have only one successor.
1354 The function also updates dominators stored in DOM. */
1356 create_preheader (loop
, dom
, flags
)
1363 basic_block jump
, src
= 0;
1364 struct loop
*cloop
, *ploop
;
1368 cloop
= loop
->outer
;
1370 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
1372 if (e
->src
== loop
->latch
)
1380 for (e
= loop
->header
->pred
; e
->src
== loop
->latch
; e
= e
->pred_next
);
1381 if (!(flags
& CP_SIMPLE_PREHEADERS
)
1382 || !e
->src
->succ
->succ_next
)
1386 insn
= first_insn_after_basic_block_note (loop
->header
);
1388 insn
= PREV_INSN (insn
);
1390 insn
= get_last_insn ();
1391 if (insn
== loop
->header
->end
)
1393 /* Split_block would not split block after its end. */
1394 emit_note_after (NOTE_INSN_DELETED
, insn
);
1396 fallthru
= split_block (loop
->header
, insn
);
1397 dummy
= fallthru
->src
;
1398 loop
->header
= fallthru
->dest
;
1400 /* The header could be a latch of some superloop(s); due to design of
1401 split_block, it would now move to fallthru->dest. */
1402 for (ploop
= loop
; ploop
; ploop
= ploop
->outer
)
1403 if (ploop
->latch
== dummy
)
1404 ploop
->latch
= fallthru
->dest
;
1406 add_to_dominance_info (dom
, fallthru
->dest
);
1408 /* Redirect edges. */
1409 for (e
= dummy
->pred
; e
; e
= e
->pred_next
)
1412 if (src
== loop
->latch
)
1418 dummy
->frequency
-= EDGE_FREQUENCY (e
);
1419 dummy
->count
-= e
->count
;
1420 fallthru
->count
-= e
->count
;
1421 jump
= redirect_edge_and_branch_force (e
, loop
->header
);
1424 add_to_dominance_info (dom
, jump
);
1425 set_immediate_dominator (dom
, jump
, src
);
1426 add_bb_to_loop (jump
, loop
);
1430 /* Update structures. */
1431 redirect_immediate_dominators (dom
, dummy
, loop
->header
);
1432 set_immediate_dominator (dom
, loop
->header
, dummy
);
1433 loop
->header
->loop_father
= loop
;
1434 add_bb_to_loop (dummy
, cloop
);
1436 fprintf (rtl_dump_file
, "Created preheader block for loop %i\n",
1442 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1443 of FLAGS see create_preheader. */
1445 create_preheaders (loops
, flags
)
1446 struct loops
*loops
;
1450 for (i
= 1; i
< loops
->num
; i
++)
1451 create_preheader (loops
->parray
[i
], loops
->cfg
.dom
, flags
);
1452 loops
->state
|= LOOPS_HAVE_PREHEADERS
;
1455 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1458 force_single_succ_latches (loops
)
1459 struct loops
*loops
;
1465 for (i
= 1; i
< loops
->num
; i
++)
1467 loop
= loops
->parray
[i
];
1468 if (!loop
->latch
->succ
->succ_next
)
1471 for (e
= loop
->header
->pred
; e
->src
!= loop
->latch
; e
= e
->pred_next
)
1474 loop_split_edge_with (e
, NULL_RTX
, loops
);
1476 loops
->state
|= LOOPS_HAVE_SIMPLE_LATCHES
;
1479 /* A quite stupid function to put INSNS on edge E. They are supposed to form
1480 just one basic block. Jumps in INSNS are not handled, so cfg do not have to
1481 be ok after this function. The created block is placed on correct place
1482 in LOOPS structure and its dominator is set. */
1484 loop_split_edge_with (e
, insns
, loops
)
1487 struct loops
*loops
;
1489 basic_block src
, dest
, new_bb
;
1490 struct loop
*loop_c
;
1496 loop_c
= find_common_loop (src
->loop_father
, dest
->loop_father
);
1498 /* Create basic block for it. */
1500 new_bb
= create_basic_block (NULL_RTX
, NULL_RTX
, EXIT_BLOCK_PTR
->prev_bb
);
1501 add_to_dominance_info (loops
->cfg
.dom
, new_bb
);
1502 add_bb_to_loop (new_bb
, loop_c
);
1503 new_bb
->flags
= insns
? BB_SUPERBLOCK
: 0;
1505 new_e
= make_edge (new_bb
, dest
, EDGE_FALLTHRU
);
1506 new_e
->probability
= REG_BR_PROB_BASE
;
1507 new_e
->count
= e
->count
;
1508 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1510 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1511 new_e
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1514 new_bb
->count
= e
->count
;
1515 new_bb
->frequency
= EDGE_FREQUENCY (e
);
1516 redirect_edge_and_branch_force (e
, new_bb
);
1518 alloc_aux_for_block (new_bb
, sizeof (struct reorder_block_def
));
1523 insns
= get_insns ();
1525 emit_insn_after (insns
, new_bb
->end
);
1528 set_immediate_dominator (loops
->cfg
.dom
, new_bb
, src
);
1529 set_immediate_dominator (loops
->cfg
.dom
, dest
,
1530 recount_dominator (loops
->cfg
.dom
, dest
));
1532 if (dest
->loop_father
->latch
== src
)
1533 dest
->loop_father
->latch
= new_bb
;