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 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 loops
*, 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 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
55 /* Splits basic block BB after INSN, returns created edge. Updates loops
58 split_loop_bb (basic_block bb
, rtx insn
)
62 /* Split the block. */
63 e
= split_block (bb
, insn
);
65 /* Add dest to loop. */
66 add_bb_to_loop (e
->dest
, e
->src
->loop_father
);
71 /* Checks whether basic block BB is dominated by DATA. */
73 rpe_enum_p (basic_block bb
, void *data
)
75 return dominated_by_p (CDI_DOMINATORS
, bb
, data
);
78 /* Remove basic blocks BBS from loop structure and dominance info,
79 and delete them afterwards. */
81 remove_bbs (basic_block
*bbs
, int nbbs
)
85 for (i
= 0; i
< nbbs
; i
++)
87 remove_bb_from_loops (bbs
[i
]);
88 delete_basic_block (bbs
[i
]);
92 /* Find path -- i.e. the basic blocks dominated by edge E and put them
93 into array BBS, that will be allocated large enough to contain them.
94 E->dest must have exactly one predecessor for this to work (it is
95 easy to achieve and we do not put it here because we do not want to
96 alter anything by this function). The number of basic blocks in the
99 find_path (edge e
, basic_block
**bbs
)
101 if (e
->dest
->pred
->pred_next
)
104 /* Find bbs in the path. */
105 *bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
106 return dfs_enumerate_from (e
->dest
, 0, rpe_enum_p
, *bbs
,
107 n_basic_blocks
, e
->dest
);
110 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
111 Let L be a loop to that BB belongs. Then every successor of BB must either
112 1) belong to some superloop of loop L, or
113 2) be a header of loop K such that K->outer is superloop of L
114 Returns true if we had to move BB into other loop to enforce this condition,
115 false if the placement of BB was already correct (provided that placements
116 of its successors are correct). */
118 fix_bb_placement (struct loops
*loops
, basic_block bb
)
121 struct loop
*loop
= loops
->tree_root
, *act
;
123 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
125 if (e
->dest
== EXIT_BLOCK_PTR
)
128 act
= e
->dest
->loop_father
;
129 if (act
->header
== e
->dest
)
132 if (flow_loop_nested_p (loop
, act
))
136 if (loop
== bb
->loop_father
)
139 remove_bb_from_loops (bb
);
140 add_bb_to_loop (bb
, loop
);
145 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
146 enforce condition condition stated in description of fix_bb_placement. We
147 start from basic block FROM that had some of its successors removed, so that
148 his placement no longer has to be correct, and iteratively fix placement of
149 its predecessors that may change if placement of FROM changed. Also fix
150 placement of subloops of FROM->loop_father, that might also be altered due
151 to this change; the condition for them is similar, except that instead of
152 successors we consider edges coming out of the loops. */
154 fix_bb_placements (struct loops
*loops
, basic_block from
)
157 basic_block
*queue
, *qtop
, *qbeg
, *qend
;
158 struct loop
*base_loop
;
161 /* We pass through blocks back-reachable from FROM, testing whether some
162 of their successors moved to outer loop. It may be necessary to
163 iterate several times, but it is finite, as we stop unless we move
164 the basic block up the loop structure. The whole story is a bit
165 more complicated due to presence of subloops, those are moved using
166 fix_loop_placement. */
168 base_loop
= from
->loop_father
;
169 if (base_loop
== loops
->tree_root
)
172 in_queue
= sbitmap_alloc (last_basic_block
);
173 sbitmap_zero (in_queue
);
174 SET_BIT (in_queue
, from
->index
);
175 /* Prevent us from going out of the base_loop. */
176 SET_BIT (in_queue
, base_loop
->header
->index
);
178 queue
= xmalloc ((base_loop
->num_nodes
+ 1) * sizeof (basic_block
));
179 qtop
= queue
+ base_loop
->num_nodes
+ 1;
190 RESET_BIT (in_queue
, from
->index
);
192 if (from
->loop_father
->header
== from
)
194 /* Subloop header, maybe move the loop upward. */
195 if (!fix_loop_placement (from
->loop_father
))
200 /* Ordinary basic block. */
201 if (!fix_bb_placement (loops
, from
))
205 /* Something has changed, insert predecessors into queue. */
206 for (e
= from
->pred
; e
; e
= e
->pred_next
)
208 basic_block pred
= e
->src
;
211 if (TEST_BIT (in_queue
, pred
->index
))
214 /* If it is subloop, then it either was not moved, or
215 the path up the loop tree from base_loop do not contain
217 nca
= find_common_loop (pred
->loop_father
, base_loop
);
218 if (pred
->loop_father
!= base_loop
220 || nca
!= pred
->loop_father
))
221 pred
= pred
->loop_father
->header
;
222 else if (!flow_loop_nested_p (from
->loop_father
, pred
->loop_father
))
224 /* No point in processing it. */
228 if (TEST_BIT (in_queue
, pred
->index
))
231 /* Schedule the basic block. */
236 SET_BIT (in_queue
, pred
->index
);
243 /* Basic block from has lost one or more of its predecessors, so it might
244 mo longer be part irreducible loop. Fix it and proceed recursively
245 for its successors if needed. */
247 fix_irreducible_loops (basic_block from
)
256 if (!(from
->flags
& BB_IRREDUCIBLE_LOOP
))
259 on_stack
= sbitmap_alloc (last_basic_block
);
260 sbitmap_zero (on_stack
);
261 SET_BIT (on_stack
, from
->index
);
262 stack
= xmalloc (from
->loop_father
->num_nodes
* sizeof (basic_block
));
268 bb
= stack
[--stack_top
];
269 RESET_BIT (on_stack
, bb
->index
);
271 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
272 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
277 bb
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
278 if (bb
->loop_father
->header
== bb
)
279 edges
= get_loop_exit_edges (bb
->loop_father
, &n_edges
);
283 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
285 edges
= xmalloc (n_edges
* sizeof (edge
));
287 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
288 edges
[n_edges
++] = e
;
291 for (i
= 0; i
< n_edges
; i
++)
295 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
297 if (!flow_bb_inside_loop_p (from
->loop_father
, e
->dest
))
300 e
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
301 if (TEST_BIT (on_stack
, e
->dest
->index
))
304 SET_BIT (on_stack
, e
->dest
->index
);
305 stack
[stack_top
++] = e
->dest
;
315 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
316 and update loop structure stored in LOOPS and dominators. Return true if
317 we were able to remove the path, false otherwise (and nothing is affected
320 remove_path (struct loops
*loops
, edge e
)
323 basic_block
*rem_bbs
, *bord_bbs
, *dom_bbs
, from
, bb
;
324 int i
, nrem
, n_bord_bbs
, n_dom_bbs
;
327 if (!loop_delete_branch_edge (e
, 0))
330 /* We need to check whether basic blocks are dominated by the edge
331 e, but we only have basic block dominators. This is easy to
332 fix -- when e->dest has exactly one predecessor, this corresponds
333 to blocks dominated by e->dest, if not, split the edge. */
334 if (e
->dest
->pred
->pred_next
)
335 e
= loop_split_edge_with (e
, NULL_RTX
)->pred
;
337 /* It may happen that by removing path we remove one or more loops
338 we belong to. In this case first unloop the loops, then proceed
339 normally. We may assume that e->dest is not a header of any loop,
340 as it now has exactly one predecessor. */
341 while (e
->src
->loop_father
->outer
342 && dominated_by_p (CDI_DOMINATORS
,
343 e
->src
->loop_father
->latch
, e
->dest
))
344 unloop (loops
, e
->src
->loop_father
);
346 /* Identify the path. */
347 nrem
= find_path (e
, &rem_bbs
);
350 bord_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
351 seen
= sbitmap_alloc (last_basic_block
);
354 /* Find "border" hexes -- i.e. those with predecessor in removed path. */
355 for (i
= 0; i
< nrem
; i
++)
356 SET_BIT (seen
, rem_bbs
[i
]->index
);
357 for (i
= 0; i
< nrem
; i
++)
360 for (ae
= rem_bbs
[i
]->succ
; ae
; ae
= ae
->succ_next
)
361 if (ae
->dest
!= EXIT_BLOCK_PTR
&& !TEST_BIT (seen
, ae
->dest
->index
))
363 SET_BIT (seen
, ae
->dest
->index
);
364 bord_bbs
[n_bord_bbs
++] = ae
->dest
;
368 /* Remove the path. */
370 if (!loop_delete_branch_edge (e
, 1))
372 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
374 /* Cancel loops contained in the path. */
375 for (i
= 0; i
< nrem
; i
++)
376 if (rem_bbs
[i
]->loop_father
->header
== rem_bbs
[i
])
377 cancel_loop_tree (loops
, rem_bbs
[i
]->loop_father
);
379 remove_bbs (rem_bbs
, nrem
);
382 /* Find blocks whose dominators may be affected. */
385 for (i
= 0; i
< n_bord_bbs
; i
++)
389 bb
= get_immediate_dominator (CDI_DOMINATORS
, bord_bbs
[i
]);
390 if (TEST_BIT (seen
, bb
->index
))
392 SET_BIT (seen
, bb
->index
);
394 for (ldom
= first_dom_son (CDI_DOMINATORS
, bb
);
396 ldom
= next_dom_son (CDI_DOMINATORS
, ldom
))
397 if (!dominated_by_p (CDI_DOMINATORS
, from
, ldom
))
398 dom_bbs
[n_dom_bbs
++] = ldom
;
403 /* Recount dominators. */
404 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
407 /* These blocks have lost some predecessor(s), thus their irreducible
408 status could be changed. */
409 for (i
= 0; i
< n_bord_bbs
; i
++)
410 fix_irreducible_loops (bord_bbs
[i
]);
413 /* Fix placements of basic blocks inside loops and the placement of
414 loops in the loop tree. */
415 fix_bb_placements (loops
, from
);
416 fix_loop_placements (loops
, from
->loop_father
);
421 /* Predicate for enumeration in add_loop. */
423 alp_enum_p (basic_block bb
, void *alp_header
)
425 return bb
!= (basic_block
) alp_header
;
428 /* Given LOOP structure with filled header and latch, find the body of the
429 corresponding loop and add it to LOOPS tree. */
431 add_loop (struct loops
*loops
, struct loop
*loop
)
436 /* Add it to loop structure. */
437 place_new_loop (loops
, loop
);
440 /* Find its nodes. */
441 bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
442 n
= dfs_enumerate_from (loop
->latch
, 1, alp_enum_p
,
443 bbs
, n_basic_blocks
, loop
->header
);
445 for (i
= 0; i
< n
; i
++)
446 add_bb_to_loop (bbs
[i
], loop
);
447 add_bb_to_loop (loop
->header
, loop
);
452 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
455 scale_bbs_frequencies (basic_block
*bbs
, int nbbs
, int num
, int den
)
460 for (i
= 0; i
< nbbs
; i
++)
462 bbs
[i
]->frequency
= (bbs
[i
]->frequency
* num
) / den
;
463 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
464 for (e
= bbs
[i
]->succ
; e
; e
= e
->succ_next
)
465 e
->count
= (e
->count
* num
) /den
;
469 /* Multiply all frequencies in LOOP by NUM/DEN. */
471 scale_loop_frequencies (struct loop
*loop
, int num
, int den
)
475 bbs
= get_loop_body (loop
);
476 scale_bbs_frequencies (bbs
, loop
->num_nodes
, num
, den
);
480 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
481 latch to header and update loop tree stored in LOOPS and dominators
482 accordingly. Everything between them plus LATCH_EDGE destination must
483 be dominated by HEADER_EDGE destination, and back-reachable from
484 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
485 FALLTHRU_EDGE (SWITCH_BB) to original destination of HEADER_EDGE and
486 BRANCH_EDGE (SWITCH_BB) to original destination of LATCH_EDGE.
487 Returns newly created loop. */
490 loopify (struct loops
*loops
, edge latch_edge
, edge header_edge
,
491 basic_block switch_bb
)
493 basic_block succ_bb
= latch_edge
->dest
;
494 basic_block pred_bb
= header_edge
->src
;
495 basic_block
*dom_bbs
, *body
;
496 unsigned n_dom_bbs
, i
;
498 struct loop
*loop
= xcalloc (1, sizeof (struct loop
));
499 struct loop
*outer
= succ_bb
->loop_father
->outer
;
500 int freq
, prob
, tot_prob
;
504 loop
->header
= header_edge
->dest
;
505 loop
->latch
= latch_edge
->src
;
507 freq
= EDGE_FREQUENCY (header_edge
);
508 cnt
= header_edge
->count
;
509 prob
= switch_bb
->succ
->probability
;
510 tot_prob
= prob
+ switch_bb
->succ
->succ_next
->probability
;
514 /* Redirect edges. */
515 loop_redirect_edge (latch_edge
, loop
->header
);
516 loop_redirect_edge (BRANCH_EDGE (switch_bb
), succ_bb
);
518 loop_redirect_edge (header_edge
, switch_bb
);
519 loop_redirect_edge (FALLTHRU_EDGE (switch_bb
), loop
->header
);
521 /* Update dominators. */
522 set_immediate_dominator (CDI_DOMINATORS
, switch_bb
, pred_bb
);
523 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 loops
*loops
, struct loop
*loop
)
678 if (!fix_loop_placement (loop
))
681 /* Changing the placement of a loop in the loop tree may alter the
682 validity of condition 2) of the description of fix_bb_placement
683 for its preheader, because the successor is the header and belongs
684 to the loop. So call fix_bb_placements to fix up the placement
685 of the preheader and (possibly) of its predecessors. */
686 fix_bb_placements (loops
, loop_preheader_edge (loop
)->src
);
691 /* Creates place for a new LOOP in LOOPS structure. */
693 place_new_loop (struct loops
*loops
, struct loop
*loop
)
696 xrealloc (loops
->parray
, (loops
->num
+ 1) * sizeof (struct loop
*));
697 loops
->parray
[loops
->num
] = loop
;
699 loop
->num
= loops
->num
++;
702 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
703 created loop into LOOPS structure. */
705 duplicate_loop (struct loops
*loops
, struct loop
*loop
, struct loop
*target
)
708 cloop
= xcalloc (1, sizeof (struct loop
));
709 place_new_loop (loops
, cloop
);
711 /* Initialize copied loop. */
712 cloop
->level
= loop
->level
;
714 /* Set it as copy of loop. */
717 /* Add it to target. */
718 flow_loop_tree_node_add (target
, cloop
);
723 /* Copies structure of subloops of LOOP into TARGET loop, placing
724 newly created loops into loop tree stored in LOOPS. */
726 duplicate_subloops (struct loops
*loops
, struct loop
*loop
, struct loop
*target
)
728 struct loop
*aloop
, *cloop
;
730 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
732 cloop
= duplicate_loop (loops
, aloop
, target
);
733 duplicate_subloops (loops
, aloop
, cloop
);
737 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
738 into TARGET loop, placing newly created loops into loop tree LOOPS. */
740 copy_loops_to (struct loops
*loops
, struct loop
**copied_loops
, int n
, struct loop
*target
)
745 for (i
= 0; i
< n
; i
++)
747 aloop
= duplicate_loop (loops
, copied_loops
[i
], target
);
748 duplicate_subloops (loops
, copied_loops
[i
], aloop
);
752 /* Redirects edge E to basic block DEST. */
754 loop_redirect_edge (edge e
, basic_block dest
)
759 redirect_edge_and_branch_force (e
, dest
);
762 /* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set,
763 just test whether it is possible to remove the edge. */
765 loop_delete_branch_edge (edge e
, int really_delete
)
767 basic_block src
= e
->src
;
771 if (src
->succ
->succ_next
)
775 /* Cannot handle more than two exit edges. */
776 if (src
->succ
->succ_next
->succ_next
)
778 /* And it must be just a simple branch. */
779 if (!any_condjump_p (BB_END (src
)))
782 snd
= e
== src
->succ
? src
->succ
->succ_next
: src
->succ
;
784 if (newdest
== EXIT_BLOCK_PTR
)
787 /* Hopefully the above conditions should suffice. */
791 /* Redirecting behaves wrongly wrto this flag. */
792 irr
= snd
->flags
& EDGE_IRREDUCIBLE_LOOP
;
794 if (!redirect_edge_and_branch (e
, newdest
))
796 src
->succ
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
797 src
->succ
->flags
|= irr
;
803 /* Cannot happen -- we are using this only to remove an edge
808 return false; /* To avoid warning, cannot get here. */
811 /* Check whether LOOP's body can be duplicated. */
813 can_duplicate_loop_p (struct loop
*loop
)
816 basic_block
*bbs
= get_loop_body (loop
);
818 ret
= can_copy_bbs_p (bbs
, loop
->num_nodes
);
824 /* The NBBS blocks in BBS will get duplicated and the copies will be placed
825 to LOOP. Update the single_exit information in superloops of LOOP. */
828 update_single_exits_after_duplication (basic_block
*bbs
, unsigned nbbs
,
833 for (i
= 0; i
< nbbs
; i
++)
834 bbs
[i
]->rbi
->duplicated
= 1;
836 for (; loop
->outer
; loop
= loop
->outer
)
838 if (!loop
->single_exit
)
841 if (loop
->single_exit
->src
->rbi
->duplicated
)
842 loop
->single_exit
= NULL
;
845 for (i
= 0; i
< nbbs
; i
++)
846 bbs
[i
]->rbi
->duplicated
= 0;
850 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
851 LOOPS structure and dominators. E's destination must be LOOP header for
852 this to work, i.e. it must be entry or latch edge of this loop; these are
853 unique, as the loops must have preheaders for this function to work
854 correctly (in case E is latch, the function unrolls the loop, if E is entry
855 edge, it peels the loop). Store edges created by copying ORIG edge from
856 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
857 original LOOP body, the other copies are numbered in order given by control
858 flow through them) into TO_REMOVE array. Returns false if duplication is
861 duplicate_loop_to_header_edge (struct loop
*loop
, edge e
, struct loops
*loops
,
862 unsigned int ndupl
, sbitmap wont_exit
,
863 edge orig
, edge
*to_remove
,
864 unsigned int *n_to_remove
, int flags
)
866 struct loop
*target
, *aloop
;
867 struct loop
**orig_loops
;
868 unsigned n_orig_loops
;
869 basic_block header
= loop
->header
, latch
= loop
->latch
;
870 basic_block
*new_bbs
, *bbs
, *first_active
;
871 basic_block new_bb
, bb
, first_active_latch
= NULL
;
873 edge spec_edges
[2], new_spec_edges
[2];
877 int is_latch
= (latch
== e
->src
);
878 int scale_act
= 0, *scale_step
= NULL
, scale_main
= 0;
879 int p
, freq_in
, freq_le
, freq_out_orig
;
880 int prob_pass_thru
, prob_pass_wont_exit
, prob_pass_main
;
881 int add_irreducible_flag
;
883 if (e
->dest
!= loop
->header
)
890 /* Orig must be edge out of the loop. */
891 if (!flow_bb_inside_loop_p (loop
, orig
->src
))
893 if (flow_bb_inside_loop_p (loop
, orig
->dest
))
897 bbs
= get_loop_body (loop
);
899 /* Check whether duplication is possible. */
900 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
905 new_bbs
= xmalloc (sizeof (basic_block
) * loop
->num_nodes
);
907 /* In case we are doing loop peeling and the loop is in the middle of
908 irreducible region, the peeled copies will be inside it too. */
909 add_irreducible_flag
= e
->flags
& EDGE_IRREDUCIBLE_LOOP
;
910 if (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 if (scale_step
[i
] < 0 || scale_step
[i
] > REG_BR_PROB_BASE
)
965 if (scale_main
< 0 || scale_main
> REG_BR_PROB_BASE
966 || scale_act
< 0 || scale_act
> REG_BR_PROB_BASE
)
970 /* Loop the new bbs will belong to. */
971 target
= e
->src
->loop_father
;
973 /* Original loops. */
975 for (aloop
= loop
->inner
; aloop
; aloop
= aloop
->next
)
977 orig_loops
= xcalloc (n_orig_loops
, sizeof (struct loop
*));
978 for (aloop
= loop
->inner
, i
= 0; aloop
; aloop
= aloop
->next
, i
++)
979 orig_loops
[i
] = aloop
;
985 first_active
= xmalloc (n
* sizeof (basic_block
));
988 memcpy (first_active
, bbs
, n
* sizeof (basic_block
));
989 first_active_latch
= latch
;
992 /* Update the information about single exits. */
993 if (loops
->state
& LOOPS_HAVE_MARKED_SINGLE_EXITS
)
994 update_single_exits_after_duplication (bbs
, n
, target
);
996 /* Record exit edge in original loop body. */
997 if (orig
&& TEST_BIT (wont_exit
, 0))
998 to_remove
[(*n_to_remove
)++] = orig
;
1000 spec_edges
[SE_ORIG
] = orig
;
1001 spec_edges
[SE_LATCH
] = latch_edge
;
1003 for (j
= 0; j
< ndupl
; j
++)
1006 copy_loops_to (loops
, orig_loops
, n_orig_loops
, target
);
1009 copy_bbs (bbs
, n
, new_bbs
, spec_edges
, 2, new_spec_edges
, loop
);
1011 /* Note whether the blocks and edges belong to an irreducible loop. */
1012 if (add_irreducible_flag
)
1014 for (i
= 0; i
< n
; i
++)
1015 new_bbs
[i
]->rbi
->duplicated
= 1;
1016 for (i
= 0; i
< n
; i
++)
1018 new_bb
= new_bbs
[i
];
1019 if (new_bb
->loop_father
== target
)
1020 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1022 for (ae
= new_bb
->succ
; ae
; ae
= ae
->succ_next
)
1023 if (ae
->dest
->rbi
->duplicated
1024 && (ae
->src
->loop_father
== target
1025 || ae
->dest
->loop_father
== target
))
1026 ae
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1028 for (i
= 0; i
< n
; i
++)
1029 new_bbs
[i
]->rbi
->duplicated
= 0;
1032 /* Redirect the special edges. */
1035 redirect_edge_and_branch_force (latch_edge
, new_bbs
[0]);
1036 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1038 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], latch
);
1039 latch
= loop
->latch
= new_bbs
[1];
1040 e
= latch_edge
= new_spec_edges
[SE_LATCH
];
1044 redirect_edge_and_branch_force (new_spec_edges
[SE_LATCH
],
1046 redirect_edge_and_branch_force (e
, new_bbs
[0]);
1047 set_immediate_dominator (CDI_DOMINATORS
, new_bbs
[0], e
->src
);
1048 e
= new_spec_edges
[SE_LATCH
];
1051 /* Record exit edge in this copy. */
1052 if (orig
&& TEST_BIT (wont_exit
, j
+ 1))
1053 to_remove
[(*n_to_remove
)++] = new_spec_edges
[SE_ORIG
];
1055 /* Record the first copy in the control flow order if it is not
1056 the original loop (i.e. in case of peeling). */
1057 if (!first_active_latch
)
1059 memcpy (first_active
, new_bbs
, n
* sizeof (basic_block
));
1060 first_active_latch
= new_bbs
[1];
1063 /* Set counts and frequencies. */
1064 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1066 scale_bbs_frequencies (new_bbs
, n
, scale_act
, REG_BR_PROB_BASE
);
1067 scale_act
= RDIV (scale_act
* scale_step
[j
], REG_BR_PROB_BASE
);
1073 /* Update the original loop. */
1075 set_immediate_dominator (CDI_DOMINATORS
, e
->dest
, e
->src
);
1076 if (flags
& DLTHE_FLAG_UPDATE_FREQ
)
1078 scale_bbs_frequencies (bbs
, n
, scale_main
, REG_BR_PROB_BASE
);
1082 /* Update dominators of outer blocks if affected. */
1083 for (i
= 0; i
< n
; i
++)
1085 basic_block dominated
, dom_bb
, *dom_bbs
;
1089 n_dom_bbs
= get_dominated_by (CDI_DOMINATORS
, bb
, &dom_bbs
);
1090 for (j
= 0; j
< n_dom_bbs
; j
++)
1092 dominated
= dom_bbs
[j
];
1093 if (flow_bb_inside_loop_p (loop
, dominated
))
1095 dom_bb
= nearest_common_dominator (
1096 CDI_DOMINATORS
, first_active
[i
], first_active_latch
);
1097 set_immediate_dominator (CDI_DOMINATORS
, dominated
, dom_bb
);
1101 free (first_active
);
1108 /* A callback for make_forwarder block, to redirect all edges except for
1109 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
1110 whether to redirect it. */
1112 static edge mfb_kj_edge
;
1114 mfb_keep_just (edge e
)
1116 return e
!= mfb_kj_edge
;
1119 /* A callback for make_forwarder block, to update data structures for a basic
1120 block JUMP created by redirecting an edge (only the latch edge is being
1124 mfb_update_loops (basic_block jump
)
1126 struct loop
*loop
= jump
->succ
->dest
->loop_father
;
1128 if (dom_computed
[CDI_DOMINATORS
])
1129 set_immediate_dominator (CDI_DOMINATORS
, jump
, jump
->pred
->src
);
1130 add_bb_to_loop (jump
, loop
);
1134 /* Creates a pre-header for a LOOP. Returns newly created block. Unless
1135 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1136 entry; otherwise we also force preheader block to have only one successor.
1137 The function also updates dominators. */
1140 create_preheader (struct loop
*loop
, int flags
)
1144 struct loop
*cloop
, *ploop
;
1148 cloop
= loop
->outer
;
1150 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
1152 if (e
->src
== loop
->latch
)
1154 irred
|= (e
->flags
& EDGE_IRREDUCIBLE_LOOP
) != 0;
1161 for (e
= loop
->header
->pred
; e
->src
== loop
->latch
; e
= e
->pred_next
);
1162 if (!(flags
& CP_SIMPLE_PREHEADERS
)
1163 || !e
->src
->succ
->succ_next
)
1167 mfb_kj_edge
= loop_latch_edge (loop
);
1168 fallthru
= make_forwarder_block (loop
->header
, mfb_keep_just
,
1170 dummy
= fallthru
->src
;
1171 loop
->header
= fallthru
->dest
;
1173 /* The header could be a latch of some superloop(s); due to design of
1174 split_block, it would now move to fallthru->dest. */
1175 for (ploop
= loop
; ploop
; ploop
= ploop
->outer
)
1176 if (ploop
->latch
== dummy
)
1177 ploop
->latch
= fallthru
->dest
;
1179 /* Reorganize blocks so that the preheader is not stuck in the middle of the
1181 for (e
= dummy
->pred
; e
; e
= e
->pred_next
)
1182 if (e
->src
!= loop
->latch
)
1184 move_block_after (dummy
, e
->src
);
1186 loop
->header
->loop_father
= loop
;
1187 add_bb_to_loop (dummy
, cloop
);
1191 dummy
->flags
|= BB_IRREDUCIBLE_LOOP
;
1192 dummy
->succ
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1196 fprintf (dump_file
, "Created preheader block for loop %i\n",
1202 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1203 of FLAGS see create_preheader. */
1205 create_preheaders (struct loops
*loops
, int flags
)
1208 for (i
= 1; i
< loops
->num
; i
++)
1209 create_preheader (loops
->parray
[i
], flags
);
1210 loops
->state
|= LOOPS_HAVE_PREHEADERS
;
1213 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1216 force_single_succ_latches (struct loops
*loops
)
1222 for (i
= 1; i
< loops
->num
; i
++)
1224 loop
= loops
->parray
[i
];
1225 if (loop
->latch
!= loop
->header
1226 && !loop
->latch
->succ
->succ_next
)
1229 for (e
= loop
->header
->pred
; e
->src
!= loop
->latch
; e
= e
->pred_next
)
1232 loop_split_edge_with (e
, NULL_RTX
);
1234 loops
->state
|= LOOPS_HAVE_SIMPLE_LATCHES
;
1237 /* A quite stupid function to put INSNS on edge E. They are supposed to form
1238 just one basic block. Jumps in INSNS are not handled, so cfg do not have to
1239 be ok after this function. The created block is placed on correct place
1240 in LOOPS structure and its dominator is set. */
1242 loop_split_edge_with (edge e
, rtx insns
)
1244 basic_block src
, dest
, new_bb
;
1245 struct loop
*loop_c
;
1251 loop_c
= find_common_loop (src
->loop_father
, dest
->loop_father
);
1253 /* Create basic block for it. */
1255 new_bb
= split_edge (e
);
1256 add_bb_to_loop (new_bb
, loop_c
);
1257 new_bb
->flags
= insns
? BB_SUPERBLOCK
: 0;
1259 new_e
= new_bb
->succ
;
1260 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1262 new_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
1263 new_e
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
1267 emit_insn_after (insns
, BB_END (new_bb
));
1269 if (dest
->loop_father
->latch
== src
)
1270 dest
->loop_father
->latch
= new_bb
;
1275 /* Uses the natural loop discovery to recreate loop notes. */
1277 create_loop_notes (void)
1279 rtx insn
, head
, end
;
1282 basic_block
*first
, *last
, bb
, pbb
;
1283 struct loop
**stack
, **top
;
1285 #ifdef ENABLE_CHECKING
1286 /* Verify that there really are no loop notes. */
1287 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1289 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1293 flow_loops_find (&loops
, LOOP_TREE
);
1294 free_dominance_info (CDI_DOMINATORS
);
1297 last
= xcalloc (loops
.num
, sizeof (basic_block
));
1301 for (loop
= bb
->loop_father
; loop
->outer
; loop
= loop
->outer
)
1302 last
[loop
->num
] = bb
;
1305 first
= xcalloc (loops
.num
, sizeof (basic_block
));
1306 stack
= xcalloc (loops
.num
, sizeof (struct loop
*));
1311 for (loop
= bb
->loop_father
; loop
->outer
; loop
= loop
->outer
)
1313 if (!first
[loop
->num
])
1316 first
[loop
->num
] = bb
;
1319 if (bb
== last
[loop
->num
])
1321 /* Prevent loops from overlapping. */
1322 while (*--top
!= loop
)
1323 last
[(*top
)->num
] = EXIT_BLOCK_PTR
;
1325 /* If loop starts with jump into it, place the note in
1326 front of the jump. */
1327 insn
= PREV_INSN (BB_HEAD (first
[loop
->num
]));
1329 && BARRIER_P (insn
))
1330 insn
= PREV_INSN (insn
);
1334 && any_uncondjump_p (insn
)
1335 && onlyjump_p (insn
))
1337 pbb
= BLOCK_FOR_INSN (insn
);
1338 if (!pbb
|| !pbb
->succ
|| pbb
->succ
->succ_next
)
1341 if (!flow_bb_inside_loop_p (loop
, pbb
->succ
->dest
))
1342 insn
= BB_HEAD (first
[loop
->num
]);
1345 insn
= BB_HEAD (first
[loop
->num
]);
1347 head
= BB_HEAD (first
[loop
->num
]);
1348 emit_note_before (NOTE_INSN_LOOP_BEG
, insn
);
1349 BB_HEAD (first
[loop
->num
]) = head
;
1351 /* Position the note correctly wrto barrier. */
1352 insn
= BB_END (last
[loop
->num
]);
1353 if (NEXT_INSN (insn
)
1354 && BARRIER_P (NEXT_INSN (insn
)))
1355 insn
= NEXT_INSN (insn
);
1357 end
= BB_END (last
[loop
->num
]);
1358 emit_note_after (NOTE_INSN_LOOP_END
, insn
);
1359 BB_END (last
[loop
->num
]) = end
;
1368 flow_loops_free (&loops
);