1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
29 #include "basic-block.h"
34 #include "tree-flow.h"
35 #include "pointer-set.h"
39 static void flow_loops_cfg_dump (FILE *);
41 /* Dump loop related CFG information. */
44 flow_loops_cfg_dump (FILE *file
)
56 fprintf (file
, ";; %d succs { ", bb
->index
);
57 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
58 fprintf (file
, "%d ", succ
->dest
->index
);
59 fprintf (file
, "}\n");
63 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
66 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
68 unsigned odepth
= loop_depth (outer
);
70 return (loop_depth (loop
) > odepth
71 && VEC_index (loop_p
, loop
->superloops
, odepth
) == outer
);
74 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
78 superloop_at_depth (struct loop
*loop
, unsigned depth
)
80 unsigned ldepth
= loop_depth (loop
);
82 gcc_assert (depth
<= ldepth
);
87 return VEC_index (loop_p
, loop
->superloops
, depth
);
90 /* Returns the list of the latch edges of LOOP. */
92 static VEC (edge
, heap
) *
93 get_loop_latch_edges (const struct loop
*loop
)
97 VEC (edge
, heap
) *ret
= NULL
;
99 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
101 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
102 VEC_safe_push (edge
, heap
, ret
, e
);
108 /* Dump the loop information specified by LOOP to the stream FILE
109 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
112 flow_loop_dump (const struct loop
*loop
, FILE *file
,
113 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
118 VEC (edge
, heap
) *latches
;
121 if (! loop
|| ! loop
->header
)
124 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
126 fprintf (file
, ";; header %d, ", loop
->header
->index
);
128 fprintf (file
, "latch %d\n", loop
->latch
->index
);
131 fprintf (file
, "multiple latches:");
132 latches
= get_loop_latch_edges (loop
);
133 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
134 fprintf (file
, " %d", e
->src
->index
);
135 VEC_free (edge
, heap
, latches
);
136 fprintf (file
, "\n");
139 fprintf (file
, ";; depth %d, outer %ld\n",
140 loop_depth (loop
), (long) (loop_outer (loop
)
141 ? loop_outer (loop
)->num
: -1));
143 fprintf (file
, ";; nodes:");
144 bbs
= get_loop_body (loop
);
145 for (i
= 0; i
< loop
->num_nodes
; i
++)
146 fprintf (file
, " %d", bbs
[i
]->index
);
148 fprintf (file
, "\n");
151 loop_dump_aux (loop
, file
, verbose
);
154 /* Dump the loop information about loops to the stream FILE,
155 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
158 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
163 if (!current_loops
|| ! file
)
166 fprintf (file
, ";; %d loops found\n", number_of_loops ());
168 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
170 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
174 flow_loops_cfg_dump (file
);
177 /* Free data allocated for LOOP. */
180 flow_loop_free (struct loop
*loop
)
182 struct loop_exit
*exit
, *next
;
184 VEC_free (loop_p
, gc
, loop
->superloops
);
186 /* Break the list of the loop exit records. They will be freed when the
187 corresponding edge is rescanned or removed, and this avoids
188 accessing the (already released) head of the list stored in the
190 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
197 ggc_free (loop
->exits
);
201 /* Free all the memory allocated for LOOPS. */
204 flow_loops_free (struct loops
*loops
)
211 /* Free the loop descriptors. */
212 for (i
= 0; VEC_iterate (loop_p
, loops
->larray
, i
, loop
); i
++)
217 flow_loop_free (loop
);
220 VEC_free (loop_p
, gc
, loops
->larray
);
224 /* Find the nodes contained within the LOOP with header HEADER.
225 Return the number of nodes within the loop. */
228 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
230 VEC (basic_block
, heap
) *stack
= NULL
;
233 edge_iterator latch_ei
;
234 unsigned depth
= loop_depth (loop
);
236 header
->loop_father
= loop
;
237 header
->loop_depth
= depth
;
239 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
241 if (latch
->src
->loop_father
== loop
242 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
246 VEC_safe_push (basic_block
, heap
, stack
, latch
->src
);
247 latch
->src
->loop_father
= loop
;
248 latch
->src
->loop_depth
= depth
;
250 while (!VEC_empty (basic_block
, stack
))
256 node
= VEC_pop (basic_block
, stack
);
258 FOR_EACH_EDGE (e
, ei
, node
->preds
)
260 basic_block ancestor
= e
->src
;
262 if (ancestor
->loop_father
!= loop
)
264 ancestor
->loop_father
= loop
;
265 ancestor
->loop_depth
= depth
;
267 VEC_safe_push (basic_block
, heap
, stack
, ancestor
);
272 VEC_free (basic_block
, heap
, stack
);
277 /* Records the vector of superloops of the loop LOOP, whose immediate
278 superloop is FATHER. */
281 establish_preds (struct loop
*loop
, struct loop
*father
)
284 unsigned depth
= loop_depth (father
) + 1;
287 /* Remember the current loop depth if it is the largest seen so far. */
288 cfun
->max_loop_depth
= MAX (cfun
->max_loop_depth
, (int) depth
);
290 VEC_truncate (loop_p
, loop
->superloops
, 0);
291 VEC_reserve (loop_p
, gc
, loop
->superloops
, depth
);
292 for (i
= 0; VEC_iterate (loop_p
, father
->superloops
, i
, ploop
); i
++)
293 VEC_quick_push (loop_p
, loop
->superloops
, ploop
);
294 VEC_quick_push (loop_p
, loop
->superloops
, father
);
296 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
297 establish_preds (ploop
, loop
);
300 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
301 added loop. If LOOP has some children, take care of that their
302 pred field will be initialized correctly. */
305 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
307 loop
->next
= father
->inner
;
308 father
->inner
= loop
;
310 establish_preds (loop
, father
);
313 /* Remove LOOP from the loop hierarchy tree. */
316 flow_loop_tree_node_remove (struct loop
*loop
)
318 struct loop
*prev
, *father
;
320 father
= loop_outer (loop
);
322 /* Remove loop from the list of sons. */
323 if (father
->inner
== loop
)
324 father
->inner
= loop
->next
;
327 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
329 prev
->next
= loop
->next
;
332 VEC_truncate (loop_p
, loop
->superloops
, 0);
335 /* Allocates and returns new loop structure. */
340 struct loop
*loop
= GGC_CNEW (struct loop
);
342 loop
->exits
= GGC_CNEW (struct loop_exit
);
343 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
348 /* Find all the natural loops in the function and save in LOOPS structure and
349 recalculate loop_depth information in basic block structures.
350 Return the number of natural loops found. */
353 flow_loops_find (struct loops
*loops
)
365 memset (loops
, 0, sizeof *loops
);
367 /* We are going to recount the maximum loop depth,
368 so throw away the last count. */
369 cfun
->max_loop_depth
= 0;
371 /* Taking care of this degenerate case makes the rest of
372 this code simpler. */
373 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
379 /* Ensure that the dominators are computed. */
380 calculate_dominance_info (CDI_DOMINATORS
);
382 /* Count the number of loop headers. This should be the
383 same as the number of natural loops. */
384 headers
= sbitmap_alloc (last_basic_block
);
385 sbitmap_zero (headers
);
392 header
->loop_depth
= 0;
394 /* If we have an abnormal predecessor, do not consider the
395 loop (not worth the problems). */
396 FOR_EACH_EDGE (e
, ei
, header
->preds
)
397 if (e
->flags
& EDGE_ABNORMAL
)
402 FOR_EACH_EDGE (e
, ei
, header
->preds
)
404 basic_block latch
= e
->src
;
406 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
408 /* Look for back edges where a predecessor is dominated
409 by this block. A natural loop has a single entry
410 node (header) that dominates all the nodes in the
411 loop. It also has single back edge to the header
412 from a latch node. */
413 if (latch
!= ENTRY_BLOCK_PTR
414 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
416 /* Shared headers should be eliminated by now. */
417 SET_BIT (headers
, header
->index
);
423 /* Allocate loop structures. */
424 loops
->larray
= VEC_alloc (loop_p
, gc
, num_loops
+ 1);
426 /* Dummy loop containing whole function. */
427 root
= alloc_loop ();
428 root
->num_nodes
= n_basic_blocks
;
429 root
->latch
= EXIT_BLOCK_PTR
;
430 root
->header
= ENTRY_BLOCK_PTR
;
431 ENTRY_BLOCK_PTR
->loop_father
= root
;
432 EXIT_BLOCK_PTR
->loop_father
= root
;
434 VEC_quick_push (loop_p
, loops
->larray
, root
);
435 loops
->tree_root
= root
;
437 /* Find and record information about all the natural loops
440 bb
->loop_father
= loops
->tree_root
;
444 /* Compute depth first search order of the CFG so that outer
445 natural loops will be found before inner natural loops. */
446 dfs_order
= XNEWVEC (int, n_basic_blocks
);
447 rc_order
= XNEWVEC (int, n_basic_blocks
);
448 pre_and_rev_post_order_compute (dfs_order
, rc_order
, false);
452 for (b
= 0; b
< n_basic_blocks
- NUM_FIXED_BLOCKS
; b
++)
457 /* Search the nodes of the CFG in reverse completion order
458 so that we can find outer loops first. */
459 if (!TEST_BIT (headers
, rc_order
[b
]))
462 header
= BASIC_BLOCK (rc_order
[b
]);
464 loop
= alloc_loop ();
465 VEC_quick_push (loop_p
, loops
->larray
, loop
);
467 loop
->header
= header
;
468 loop
->num
= num_loops
;
471 flow_loop_tree_node_add (header
->loop_father
, loop
);
472 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
474 /* Look for the latch for this header block, if it has just a
476 FOR_EACH_EDGE (e
, ei
, header
->preds
)
478 basic_block latch
= e
->src
;
480 if (flow_bb_inside_loop_p (loop
, latch
))
482 if (loop
->latch
!= NULL
)
484 /* More than one latch edge. */
497 sbitmap_free (headers
);
501 return VEC_length (loop_p
, loops
->larray
);
504 /* Ratio of frequencies of edges so that one of more latch edges is
505 considered to belong to inner loop with same header. */
506 #define HEAVY_EDGE_RATIO 8
508 /* Minimum number of samples for that we apply
509 find_subloop_latch_edge_by_profile heuristics. */
510 #define HEAVY_EDGE_MIN_SAMPLES 10
512 /* If the profile info is available, finds an edge in LATCHES that much more
513 frequent than the remaining edges. Returns such an edge, or NULL if we do
516 We do not use guessed profile here, only the measured one. The guessed
517 profile is usually too flat and unreliable for this (and it is mostly based
518 on the loop structure of the program, so it does not make much sense to
519 derive the loop structure from it). */
522 find_subloop_latch_edge_by_profile (VEC (edge
, heap
) *latches
)
526 gcov_type mcount
= 0, tcount
= 0;
528 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
530 if (e
->count
> mcount
)
538 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
539 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
544 "Found latch edge %d -> %d using profile information.\n",
545 me
->src
->index
, me
->dest
->index
);
549 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
550 on the structure of induction variables. Returns this edge, or NULL if we
553 We are quite conservative, and look just for an obvious simple innermost
554 loop (which is the case where we would lose the most performance by not
555 disambiguating the loop). More precisely, we look for the following
556 situation: The source of the chosen latch edge dominates sources of all
557 the other latch edges. Additionally, the header does not contain a phi node
558 such that the argument from the chosen edge is equal to the argument from
562 find_subloop_latch_edge_by_ivs (struct loop
*loop
, VEC (edge
, heap
) *latches
)
564 edge e
, latch
= VEC_index (edge
, latches
, 0);
569 /* Find the candidate for the latch edge. */
570 for (i
= 1; VEC_iterate (edge
, latches
, i
, e
); i
++)
571 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
574 /* Verify that it dominates all the latch edges. */
575 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
576 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
579 /* Check for a phi node that would deny that this is a latch edge of
581 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
583 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
585 /* Ignore the values that are not changed inside the subloop. */
586 if (TREE_CODE (lop
) != SSA_NAME
587 || SSA_NAME_DEF_STMT (lop
) == phi
)
589 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (lop
));
590 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
593 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
595 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
601 "Found latch edge %d -> %d using iv structure.\n",
602 latch
->src
->index
, latch
->dest
->index
);
606 /* If we can determine that one of the several latch edges of LOOP behaves
607 as a latch edge of a separate subloop, returns this edge. Otherwise
611 find_subloop_latch_edge (struct loop
*loop
)
613 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
616 if (VEC_length (edge
, latches
) > 1)
618 latch
= find_subloop_latch_edge_by_profile (latches
);
621 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
622 should use cfghook for this, but it is hard to imagine it would
623 be useful elsewhere. */
624 && current_ir_type () == IR_GIMPLE
)
625 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
628 VEC_free (edge
, heap
, latches
);
632 /* Callback for make_forwarder_block. Returns true if the edge E is marked
633 in the set MFB_REIS_SET. */
635 static struct pointer_set_t
*mfb_reis_set
;
637 mfb_redirect_edges_in_set (edge e
)
639 return pointer_set_contains (mfb_reis_set
, e
);
642 /* Creates a subloop of LOOP with latch edge LATCH. */
645 form_subloop (struct loop
*loop
, edge latch
)
649 struct loop
*new_loop
;
651 mfb_reis_set
= pointer_set_create ();
652 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
655 pointer_set_insert (mfb_reis_set
, e
);
657 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
659 pointer_set_destroy (mfb_reis_set
);
661 loop
->header
= new_entry
->src
;
663 /* Find the blocks and subloops that belong to the new loop, and add it to
664 the appropriate place in the loop tree. */
665 new_loop
= alloc_loop ();
666 new_loop
->header
= new_entry
->dest
;
667 new_loop
->latch
= latch
->src
;
668 add_loop (new_loop
, loop
);
671 /* Make all the latch edges of LOOP to go to a single forwarder block --
672 a new latch of LOOP. */
675 merge_latch_edges (struct loop
*loop
)
677 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
681 gcc_assert (VEC_length (edge
, latches
) > 0);
683 if (VEC_length (edge
, latches
) == 1)
684 loop
->latch
= VEC_index (edge
, latches
, 0)->src
;
688 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
690 mfb_reis_set
= pointer_set_create ();
691 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
692 pointer_set_insert (mfb_reis_set
, e
);
693 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
695 pointer_set_destroy (mfb_reis_set
);
697 loop
->header
= latch
->dest
;
698 loop
->latch
= latch
->src
;
701 VEC_free (edge
, heap
, latches
);
704 /* LOOP may have several latch edges. Transform it into (possibly several)
705 loops with single latch edge. */
708 disambiguate_multiple_latches (struct loop
*loop
)
712 /* We eliminate the multiple latches by splitting the header to the forwarder
713 block F and the rest R, and redirecting the edges. There are two cases:
715 1) If there is a latch edge E that corresponds to a subloop (we guess
716 that based on profile -- if it is taken much more often than the
717 remaining edges; and on trees, using the information about induction
718 variables of the loops), we redirect E to R, all the remaining edges to
719 F, then rescan the loops and try again for the outer loop.
720 2) If there is no such edge, we redirect all latch edges to F, and the
721 entry edges to R, thus making F the single latch of the loop. */
724 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
727 /* During latch merging, we may need to redirect the entry edges to a new
728 block. This would cause problems if the entry edge was the one from the
729 entry block. To avoid having to handle this case specially, split
731 e
= find_edge (ENTRY_BLOCK_PTR
, loop
->header
);
737 e
= find_subloop_latch_edge (loop
);
741 form_subloop (loop
, e
);
744 merge_latch_edges (loop
);
747 /* Split loops with multiple latch edges. */
750 disambiguate_loops_with_multiple_latches (void)
755 FOR_EACH_LOOP (li
, loop
, 0)
758 disambiguate_multiple_latches (loop
);
762 /* Return nonzero if basic block BB belongs to LOOP. */
764 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
766 struct loop
*source_loop
;
768 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
771 source_loop
= bb
->loop_father
;
772 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
775 /* Enumeration predicate for get_loop_body_with_size. */
777 glb_enum_p (basic_block bb
, void *glb_loop
)
779 struct loop
*loop
= glb_loop
;
780 return (bb
!= loop
->header
781 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
784 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
785 order against direction of edges from latch. Specially, if
786 header != latch, latch is the 1-st block. LOOP cannot be the fake
787 loop tree root, and its size must be at most MAX_SIZE. The blocks
788 in the LOOP body are stored to BODY, and the size of the LOOP is
792 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
795 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
796 body
, max_size
, (void *) loop
);
799 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
800 order against direction of edges from latch. Specially, if
801 header != latch, latch is the 1-st block. */
804 get_loop_body (const struct loop
*loop
)
806 basic_block
*body
, bb
;
809 gcc_assert (loop
->num_nodes
);
811 body
= XCNEWVEC (basic_block
, loop
->num_nodes
);
813 if (loop
->latch
== EXIT_BLOCK_PTR
)
815 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
816 special-case the fake loop that contains the whole function. */
817 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
);
818 body
[tv
++] = loop
->header
;
819 body
[tv
++] = EXIT_BLOCK_PTR
;
824 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
826 gcc_assert (tv
== loop
->num_nodes
);
830 /* Fills dominance descendants inside LOOP of the basic block BB into
831 array TOVISIT from index *TV. */
834 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
835 basic_block
*tovisit
, int *tv
)
837 basic_block son
, postpone
= NULL
;
839 tovisit
[(*tv
)++] = bb
;
840 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
842 son
= next_dom_son (CDI_DOMINATORS
, son
))
844 if (!flow_bb_inside_loop_p (loop
, son
))
847 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
852 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
856 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
859 /* Gets body of a LOOP (that must be different from the outermost loop)
860 sorted by dominance relation. Additionally, if a basic block s dominates
861 the latch, then only blocks dominated by s are be after it. */
864 get_loop_body_in_dom_order (const struct loop
*loop
)
866 basic_block
*tovisit
;
869 gcc_assert (loop
->num_nodes
);
871 tovisit
= XCNEWVEC (basic_block
, loop
->num_nodes
);
873 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
876 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
878 gcc_assert (tv
== (int) loop
->num_nodes
);
883 /* Get body of a LOOP in breadth first sort order. */
886 get_loop_body_in_bfs_order (const struct loop
*loop
)
894 gcc_assert (loop
->num_nodes
);
895 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
897 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
898 visited
= BITMAP_ALLOC (NULL
);
901 while (i
< loop
->num_nodes
)
906 if (!bitmap_bit_p (visited
, bb
->index
))
908 /* This basic block is now visited */
909 bitmap_set_bit (visited
, bb
->index
);
913 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
915 if (flow_bb_inside_loop_p (loop
, e
->dest
))
917 if (!bitmap_bit_p (visited
, e
->dest
->index
))
919 bitmap_set_bit (visited
, e
->dest
->index
);
920 blocks
[i
++] = e
->dest
;
925 gcc_assert (i
>= vc
);
930 BITMAP_FREE (visited
);
934 /* Hash function for struct loop_exit. */
937 loop_exit_hash (const void *ex
)
939 struct loop_exit
*exit
= (struct loop_exit
*) ex
;
941 return htab_hash_pointer (exit
->e
);
944 /* Equality function for struct loop_exit. Compares with edge. */
947 loop_exit_eq (const void *ex
, const void *e
)
949 struct loop_exit
*exit
= (struct loop_exit
*) ex
;
954 /* Frees the list of loop exit descriptions EX. */
957 loop_exit_free (void *ex
)
959 struct loop_exit
*exit
= (struct loop_exit
*) ex
, *next
;
961 for (; exit
; exit
= next
)
965 exit
->next
->prev
= exit
->prev
;
966 exit
->prev
->next
= exit
->next
;
972 /* Returns the list of records for E as an exit of a loop. */
974 static struct loop_exit
*
975 get_exit_descriptions (edge e
)
977 return htab_find_with_hash (current_loops
->exits
, e
,
978 htab_hash_pointer (e
));
981 /* Updates the lists of loop exits in that E appears.
982 If REMOVED is true, E is being removed, and we
983 just remove it from the lists of exits.
984 If NEW_EDGE is true and E is not a loop exit, we
985 do not try to remove it from loop exit lists. */
988 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
991 struct loop_exit
*exits
= NULL
, *exit
;
992 struct loop
*aloop
, *cloop
;
994 if ((current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
) == 0)
998 && e
->src
->loop_father
!= NULL
999 && e
->dest
->loop_father
!= NULL
1000 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1002 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1003 for (aloop
= e
->src
->loop_father
;
1005 aloop
= loop_outer (aloop
))
1007 exit
= GGC_NEW (struct loop_exit
);
1010 exit
->next
= aloop
->exits
->next
;
1011 exit
->prev
= aloop
->exits
;
1012 exit
->next
->prev
= exit
;
1013 exit
->prev
->next
= exit
;
1015 exit
->next_e
= exits
;
1020 if (!exits
&& new_edge
)
1023 slot
= htab_find_slot_with_hash (current_loops
->exits
, e
,
1024 htab_hash_pointer (e
),
1025 exits
? INSERT
: NO_INSERT
);
1032 loop_exit_free (*slot
);
1036 htab_clear_slot (current_loops
->exits
, slot
);
1039 /* For each loop, record list of exit edges, and start maintaining these
1043 record_loop_exits (void)
1052 if (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
)
1054 current_loops
->state
|= LOOPS_HAVE_RECORDED_EXITS
;
1056 gcc_assert (current_loops
->exits
== NULL
);
1057 current_loops
->exits
= htab_create_alloc (2 * number_of_loops (),
1061 ggc_calloc
, ggc_free
);
1065 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1067 rescan_loop_exit (e
, true, false);
1072 /* Dumps information about the exit in *SLOT to FILE.
1073 Callback for htab_traverse. */
1076 dump_recorded_exit (void **slot
, void *file
)
1078 struct loop_exit
*exit
= *slot
;
1082 for (; exit
!= NULL
; exit
= exit
->next_e
)
1085 fprintf (file
, "Edge %d->%d exits %u loops\n",
1086 e
->src
->index
, e
->dest
->index
, n
);
1091 /* Dumps the recorded exits of loops to FILE. */
1093 extern void dump_recorded_exits (FILE *);
1095 dump_recorded_exits (FILE *file
)
1097 if (!current_loops
->exits
)
1099 htab_traverse (current_loops
->exits
, dump_recorded_exit
, file
);
1102 /* Releases lists of loop exits. */
1105 release_recorded_exits (void)
1107 gcc_assert (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
);
1108 htab_delete (current_loops
->exits
);
1109 current_loops
->exits
= NULL
;
1110 current_loops
->state
&= ~LOOPS_HAVE_RECORDED_EXITS
;
1113 /* Returns the list of the exit edges of a LOOP. */
1116 get_loop_exit_edges (const struct loop
*loop
)
1118 VEC (edge
, heap
) *edges
= NULL
;
1123 struct loop_exit
*exit
;
1125 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1127 /* If we maintain the lists of exits, use them. Otherwise we must
1128 scan the body of the loop. */
1129 if (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
)
1131 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1132 VEC_safe_push (edge
, heap
, edges
, exit
->e
);
1136 body
= get_loop_body (loop
);
1137 for (i
= 0; i
< loop
->num_nodes
; i
++)
1138 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1140 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1141 VEC_safe_push (edge
, heap
, edges
, e
);
1149 /* Counts the number of conditional branches inside LOOP. */
1152 num_loop_branches (const struct loop
*loop
)
1157 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1159 body
= get_loop_body (loop
);
1161 for (i
= 0; i
< loop
->num_nodes
; i
++)
1162 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1169 /* Adds basic block BB to LOOP. */
1171 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1178 gcc_assert (bb
->loop_father
== NULL
);
1179 bb
->loop_father
= loop
;
1180 bb
->loop_depth
= loop_depth (loop
);
1182 for (i
= 0; VEC_iterate (loop_p
, loop
->superloops
, i
, ploop
); i
++)
1185 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1187 rescan_loop_exit (e
, true, false);
1189 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1191 rescan_loop_exit (e
, true, false);
1195 /* Remove basic block BB from loops. */
1197 remove_bb_from_loops (basic_block bb
)
1200 struct loop
*loop
= bb
->loop_father
;
1205 gcc_assert (loop
!= NULL
);
1207 for (i
= 0; VEC_iterate (loop_p
, loop
->superloops
, i
, ploop
); i
++)
1209 bb
->loop_father
= NULL
;
1212 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1214 rescan_loop_exit (e
, false, true);
1216 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1218 rescan_loop_exit (e
, false, true);
1222 /* Finds nearest common ancestor in loop tree for given loops. */
1224 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1226 unsigned sdepth
, ddepth
;
1228 if (!loop_s
) return loop_d
;
1229 if (!loop_d
) return loop_s
;
1231 sdepth
= loop_depth (loop_s
);
1232 ddepth
= loop_depth (loop_d
);
1234 if (sdepth
< ddepth
)
1235 loop_d
= VEC_index (loop_p
, loop_d
->superloops
, sdepth
);
1236 else if (sdepth
> ddepth
)
1237 loop_s
= VEC_index (loop_p
, loop_s
->superloops
, ddepth
);
1239 while (loop_s
!= loop_d
)
1241 loop_s
= loop_outer (loop_s
);
1242 loop_d
= loop_outer (loop_d
);
1247 /* Removes LOOP from structures and frees its data. */
1250 delete_loop (struct loop
*loop
)
1252 /* Remove the loop from structure. */
1253 flow_loop_tree_node_remove (loop
);
1255 /* Remove loop from loops array. */
1256 VEC_replace (loop_p
, current_loops
->larray
, loop
->num
, NULL
);
1258 /* Free loop data. */
1259 flow_loop_free (loop
);
1262 /* Cancels the LOOP; it must be innermost one. */
1265 cancel_loop (struct loop
*loop
)
1269 struct loop
*outer
= loop_outer (loop
);
1271 gcc_assert (!loop
->inner
);
1273 /* Move blocks up one level (they should be removed as soon as possible). */
1274 bbs
= get_loop_body (loop
);
1275 for (i
= 0; i
< loop
->num_nodes
; i
++)
1276 bbs
[i
]->loop_father
= outer
;
1281 /* Cancels LOOP and all its subloops. */
1283 cancel_loop_tree (struct loop
*loop
)
1286 cancel_loop_tree (loop
->inner
);
1290 /* Checks that information about loops is correct
1291 -- sizes of loops are all right
1292 -- results of get_loop_body really belong to the loop
1293 -- loop header have just single entry edge and single latch edge
1294 -- loop latches have only single successor that is header of their loop
1295 -- irreducible loops are correctly marked
1298 verify_loop_structure (void)
1300 unsigned *sizes
, i
, j
;
1302 basic_block
*bbs
, bb
;
1306 unsigned num
= number_of_loops ();
1308 struct loop_exit
*exit
, *mexit
;
1311 sizes
= XCNEWVEC (unsigned, num
);
1315 for (loop
= bb
->loop_father
; loop
; loop
= loop_outer (loop
))
1318 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
1322 if (loop
->num_nodes
!= sizes
[i
])
1324 error ("size of loop %d should be %d, not %d",
1325 i
, sizes
[i
], loop
->num_nodes
);
1330 /* Check get_loop_body. */
1331 FOR_EACH_LOOP (li
, loop
, 0)
1333 bbs
= get_loop_body (loop
);
1335 for (j
= 0; j
< loop
->num_nodes
; j
++)
1336 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1338 error ("bb %d do not belong to loop %d",
1339 bbs
[j
]->index
, loop
->num
);
1345 /* Check headers and latches. */
1346 FOR_EACH_LOOP (li
, loop
, 0)
1350 if ((current_loops
->state
& LOOPS_HAVE_PREHEADERS
)
1351 && EDGE_COUNT (loop
->header
->preds
) != 2)
1353 error ("loop %d's header does not have exactly 2 entries", i
);
1356 if (current_loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1358 if (!single_succ_p (loop
->latch
))
1360 error ("loop %d's latch does not have exactly 1 successor", i
);
1363 if (single_succ (loop
->latch
) != loop
->header
)
1365 error ("loop %d's latch does not have header as successor", i
);
1368 if (loop
->latch
->loop_father
!= loop
)
1370 error ("loop %d's latch does not belong directly to it", i
);
1374 if (loop
->header
->loop_father
!= loop
)
1376 error ("loop %d's header does not belong directly to it", i
);
1379 if ((current_loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1380 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1382 error ("loop %d's latch is marked as part of irreducible region", i
);
1387 /* Check irreducible loops. */
1388 if (current_loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1390 /* Record old info. */
1391 irreds
= sbitmap_alloc (last_basic_block
);
1395 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1396 SET_BIT (irreds
, bb
->index
);
1398 RESET_BIT (irreds
, bb
->index
);
1399 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1400 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1401 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1405 mark_irreducible_loops ();
1412 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1413 && !TEST_BIT (irreds
, bb
->index
))
1415 error ("basic block %d should be marked irreducible", bb
->index
);
1418 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1419 && TEST_BIT (irreds
, bb
->index
))
1421 error ("basic block %d should not be marked irreducible", bb
->index
);
1424 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1426 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1427 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1429 error ("edge from %d to %d should be marked irreducible",
1430 e
->src
->index
, e
->dest
->index
);
1433 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1434 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1436 error ("edge from %d to %d should not be marked irreducible",
1437 e
->src
->index
, e
->dest
->index
);
1440 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1446 /* Check the recorded loop exits. */
1447 FOR_EACH_LOOP (li
, loop
, 0)
1449 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1451 error ("corrupted head of the exits list of loop %d",
1457 /* Check that the list forms a cycle, and all elements except
1458 for the head are nonnull. */
1459 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1460 exit
->e
&& exit
!= mexit
;
1464 mexit
= mexit
->next
;
1467 if (exit
!= loop
->exits
)
1469 error ("corrupted exits list of loop %d", loop
->num
);
1474 if ((current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
) == 0)
1476 if (loop
->exits
->next
!= loop
->exits
)
1478 error ("nonempty exits list of loop %d, but exits are not recorded",
1485 if (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
)
1487 unsigned n_exits
= 0, eloops
;
1489 memset (sizes
, 0, sizeof (unsigned) * num
);
1493 if (bb
->loop_father
== current_loops
->tree_root
)
1495 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1497 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1501 exit
= get_exit_descriptions (e
);
1504 error ("Exit %d->%d not recorded",
1505 e
->src
->index
, e
->dest
->index
);
1509 for (; exit
; exit
= exit
->next_e
)
1512 for (loop
= bb
->loop_father
;
1513 loop
!= e
->dest
->loop_father
;
1514 loop
= loop_outer (loop
))
1522 error ("Wrong list of exited loops for edge %d->%d",
1523 e
->src
->index
, e
->dest
->index
);
1529 if (n_exits
!= htab_elements (current_loops
->exits
))
1531 error ("Too many loop exits recorded");
1535 FOR_EACH_LOOP (li
, loop
, 0)
1538 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1540 if (eloops
!= sizes
[loop
->num
])
1542 error ("%d exits recorded for loop %d (having %d exits)",
1543 eloops
, loop
->num
, sizes
[loop
->num
]);
1554 /* Returns latch edge of LOOP. */
1556 loop_latch_edge (const struct loop
*loop
)
1558 return find_edge (loop
->latch
, loop
->header
);
1561 /* Returns preheader edge of LOOP. */
1563 loop_preheader_edge (const struct loop
*loop
)
1568 gcc_assert ((current_loops
->state
& LOOPS_HAVE_PREHEADERS
) != 0);
1570 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1571 if (e
->src
!= loop
->latch
)
1577 /* Returns true if E is an exit of LOOP. */
1580 loop_exit_edge_p (const struct loop
*loop
, edge e
)
1582 return (flow_bb_inside_loop_p (loop
, e
->src
)
1583 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1586 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1587 or more than one exit. If loops do not have the exits recorded, NULL
1588 is returned always. */
1591 single_exit (const struct loop
*loop
)
1593 struct loop_exit
*exit
= loop
->exits
->next
;
1595 if ((current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
) == 0)
1598 if (exit
->e
&& exit
->next
== loop
->exits
)