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"
38 static void flow_loops_cfg_dump (FILE *);
39 static void establish_preds (struct loop
*);
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 return (loop
->depth
> outer
->depth
69 && loop
->pred
[outer
->depth
] == outer
);
72 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
76 superloop_at_depth (struct loop
*loop
, unsigned depth
)
78 gcc_assert (depth
<= (unsigned) loop
->depth
);
80 if (depth
== (unsigned) loop
->depth
)
83 return loop
->pred
[depth
];
86 /* Returns the list of the latch edges of LOOP. */
88 static VEC (edge
, heap
) *
89 get_loop_latch_edges (const struct loop
*loop
)
93 VEC (edge
, heap
) *ret
= NULL
;
95 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
97 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
98 VEC_safe_push (edge
, heap
, ret
, e
);
104 /* Dump the loop information specified by LOOP to the stream FILE
105 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
108 flow_loop_dump (const struct loop
*loop
, FILE *file
,
109 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
114 VEC (edge
, heap
) *latches
;
117 if (! loop
|| ! loop
->header
)
120 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
122 fprintf (file
, ";; header %d, ", loop
->header
->index
);
124 fprintf (file
, "latch %d\n", loop
->latch
->index
);
127 fprintf (file
, "multiple latches:");
128 latches
= get_loop_latch_edges (loop
);
129 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
130 fprintf (file
, " %d", e
->src
->index
);
131 VEC_free (edge
, heap
, latches
);
132 fprintf (file
, "\n");
135 fprintf (file
, ";; depth %d, outer %ld\n",
136 loop
->depth
, (long) (loop
->outer
? loop
->outer
->num
: -1));
138 fprintf (file
, ";; nodes:");
139 bbs
= get_loop_body (loop
);
140 for (i
= 0; i
< loop
->num_nodes
; i
++)
141 fprintf (file
, " %d", bbs
[i
]->index
);
143 fprintf (file
, "\n");
146 loop_dump_aux (loop
, file
, verbose
);
149 /* Dump the loop information about loops to the stream FILE,
150 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
153 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
158 if (!current_loops
|| ! file
)
161 fprintf (file
, ";; %d loops found\n", number_of_loops ());
163 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
165 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
169 flow_loops_cfg_dump (file
);
172 /* Free data allocated for LOOP. */
174 flow_loop_free (struct loop
*loop
)
176 struct loop_exit
*exit
, *next
;
181 /* Break the list of the loop exit records. They will be freed when the
182 corresponding edge is rescanned or removed, and this avoids
183 accessing the (already released) head of the list stored in the
185 for (exit
= loop
->exits
.next
; exit
!= &loop
->exits
; exit
= next
)
195 /* Free all the memory allocated for LOOPS. */
198 flow_loops_free (struct loops
*loops
)
205 /* Free the loop descriptors. */
206 for (i
= 0; VEC_iterate (loop_p
, loops
->larray
, i
, loop
); i
++)
211 flow_loop_free (loop
);
214 VEC_free (loop_p
, heap
, loops
->larray
);
215 loops
->larray
= NULL
;
219 /* Find the nodes contained within the LOOP with header HEADER.
220 Return the number of nodes within the loop. */
223 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
225 VEC (basic_block
, heap
) *stack
= NULL
;
228 edge_iterator latch_ei
;
230 header
->loop_father
= loop
;
231 header
->loop_depth
= loop
->depth
;
233 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
235 if (latch
->src
->loop_father
== loop
236 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
240 VEC_safe_push (basic_block
, heap
, stack
, latch
->src
);
241 latch
->src
->loop_father
= loop
;
242 latch
->src
->loop_depth
= loop
->depth
;
244 while (!VEC_empty (basic_block
, stack
))
250 node
= VEC_pop (basic_block
, stack
);
252 FOR_EACH_EDGE (e
, ei
, node
->preds
)
254 basic_block ancestor
= e
->src
;
256 if (ancestor
->loop_father
!= loop
)
258 ancestor
->loop_father
= loop
;
259 ancestor
->loop_depth
= loop
->depth
;
261 VEC_safe_push (basic_block
, heap
, stack
, ancestor
);
266 VEC_free (basic_block
, heap
, stack
);
272 establish_preds (struct loop
*loop
)
274 struct loop
*ploop
, *father
= loop
->outer
;
276 loop
->depth
= father
->depth
+ 1;
278 /* Remember the current loop depth if it is the largest seen so far. */
279 cfun
->max_loop_depth
= MAX (cfun
->max_loop_depth
, loop
->depth
);
283 loop
->pred
= XNEWVEC (struct loop
*, loop
->depth
);
284 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
285 loop
->pred
[father
->depth
] = father
;
287 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
288 establish_preds (ploop
);
291 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
292 added loop. If LOOP has some children, take care of that their
293 pred field will be initialized correctly. */
296 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
298 loop
->next
= father
->inner
;
299 father
->inner
= loop
;
300 loop
->outer
= father
;
302 establish_preds (loop
);
305 /* Remove LOOP from the loop hierarchy tree. */
308 flow_loop_tree_node_remove (struct loop
*loop
)
310 struct loop
*prev
, *father
;
312 father
= loop
->outer
;
315 /* Remove loop from the list of sons. */
316 if (father
->inner
== loop
)
317 father
->inner
= loop
->next
;
320 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
321 prev
->next
= loop
->next
;
329 /* Allocates and returns new loop structure. */
334 struct loop
*loop
= XCNEW (struct loop
);
336 loop
->exits
.next
= loop
->exits
.prev
= &loop
->exits
;
340 /* Find all the natural loops in the function and save in LOOPS structure and
341 recalculate loop_depth information in basic block structures.
342 Return the number of natural loops found. */
345 flow_loops_find (struct loops
*loops
)
357 memset (loops
, 0, sizeof *loops
);
359 /* We are going to recount the maximum loop depth,
360 so throw away the last count. */
361 cfun
->max_loop_depth
= 0;
363 /* Taking care of this degenerate case makes the rest of
364 this code simpler. */
365 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
371 /* Ensure that the dominators are computed. */
372 calculate_dominance_info (CDI_DOMINATORS
);
374 /* Count the number of loop headers. This should be the
375 same as the number of natural loops. */
376 headers
= sbitmap_alloc (last_basic_block
);
377 sbitmap_zero (headers
);
384 header
->loop_depth
= 0;
386 /* If we have an abnormal predecessor, do not consider the
387 loop (not worth the problems). */
388 FOR_EACH_EDGE (e
, ei
, header
->preds
)
389 if (e
->flags
& EDGE_ABNORMAL
)
394 FOR_EACH_EDGE (e
, ei
, header
->preds
)
396 basic_block latch
= e
->src
;
398 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
400 /* Look for back edges where a predecessor is dominated
401 by this block. A natural loop has a single entry
402 node (header) that dominates all the nodes in the
403 loop. It also has single back edge to the header
404 from a latch node. */
405 if (latch
!= ENTRY_BLOCK_PTR
406 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
408 /* Shared headers should be eliminated by now. */
409 SET_BIT (headers
, header
->index
);
415 /* Allocate loop structures. */
416 loops
->larray
= VEC_alloc (loop_p
, heap
, num_loops
+ 1);
418 /* Dummy loop containing whole function. */
419 root
= alloc_loop ();
420 root
->num_nodes
= n_basic_blocks
;
421 root
->latch
= EXIT_BLOCK_PTR
;
422 root
->header
= ENTRY_BLOCK_PTR
;
423 ENTRY_BLOCK_PTR
->loop_father
= root
;
424 EXIT_BLOCK_PTR
->loop_father
= root
;
426 VEC_quick_push (loop_p
, loops
->larray
, root
);
427 loops
->tree_root
= root
;
429 /* Find and record information about all the natural loops
432 bb
->loop_father
= loops
->tree_root
;
436 /* Compute depth first search order of the CFG so that outer
437 natural loops will be found before inner natural loops. */
438 dfs_order
= XNEWVEC (int, n_basic_blocks
);
439 rc_order
= XNEWVEC (int, n_basic_blocks
);
440 pre_and_rev_post_order_compute (dfs_order
, rc_order
, false);
444 for (b
= 0; b
< n_basic_blocks
- NUM_FIXED_BLOCKS
; b
++)
449 /* Search the nodes of the CFG in reverse completion order
450 so that we can find outer loops first. */
451 if (!TEST_BIT (headers
, rc_order
[b
]))
454 header
= BASIC_BLOCK (rc_order
[b
]);
456 loop
= alloc_loop ();
457 VEC_quick_push (loop_p
, loops
->larray
, loop
);
459 loop
->header
= header
;
460 loop
->num
= num_loops
;
463 flow_loop_tree_node_add (header
->loop_father
, loop
);
464 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
466 /* Look for the latch for this header block, if it has just a
468 FOR_EACH_EDGE (e
, ei
, header
->preds
)
470 basic_block latch
= e
->src
;
472 if (flow_bb_inside_loop_p (loop
, latch
))
474 if (loop
->latch
!= NULL
)
476 /* More than one latch edge. */
489 sbitmap_free (headers
);
493 return VEC_length (loop_p
, loops
->larray
);
496 /* Ratio of frequencies of edges so that one of more latch edges is
497 considered to belong to inner loop with same header. */
498 #define HEAVY_EDGE_RATIO 8
500 /* Minimum number of samples for that we apply
501 find_subloop_latch_edge_by_profile heuristics. */
502 #define HEAVY_EDGE_MIN_SAMPLES 10
504 /* If the profile info is available, finds an edge in LATCHES that much more
505 frequent than the remaining edges. Returns such an edge, or NULL if we do
508 We do not use guessed profile here, only the measured one. The guessed
509 profile is usually too flat and unreliable for this (and it is mostly based
510 on the loop structure of the program, so it does not make much sense to
511 derive the loop structure from it). */
514 find_subloop_latch_edge_by_profile (VEC (edge
, heap
) *latches
)
518 gcov_type mcount
= 0, tcount
= 0;
520 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
522 if (e
->count
> mcount
)
530 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
531 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
536 "Found latch edge %d -> %d using profile information.\n",
537 me
->src
->index
, me
->dest
->index
);
541 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
542 on the structure of induction variables. Returns this edge, or NULL if we
545 We are quite conservative, and look just for an obvious simple innermost
546 loop (which is the case where we would lose the most performance by not
547 disambiguating the loop). More precisely, we look for the following
548 situation: The source of the chosen latch edge dominates sources of all
549 the other latch edges. Additionally, the header does not contain a phi node
550 such that the argument from the chosen edge is equal to the argument from
554 find_subloop_latch_edge_by_ivs (struct loop
*loop
, VEC (edge
, heap
) *latches
)
556 edge e
, latch
= VEC_index (edge
, latches
, 0);
561 /* Find the candidate for the latch edge. */
562 for (i
= 1; VEC_iterate (edge
, latches
, i
, e
); i
++)
563 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
566 /* Verify that it dominates all the latch edges. */
567 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
568 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
571 /* Check for a phi node that would deny that this is a latch edge of
573 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
575 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
577 /* Ignore the values that are not changed inside the subloop. */
578 if (TREE_CODE (lop
) != SSA_NAME
579 || SSA_NAME_DEF_STMT (lop
) == phi
)
581 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (lop
));
582 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
585 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
587 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
593 "Found latch edge %d -> %d using iv structure.\n",
594 latch
->src
->index
, latch
->dest
->index
);
598 /* If we can determine that one of the several latch edges of LOOP behaves
599 as a latch edge of a separate subloop, returns this edge. Otherwise
603 find_subloop_latch_edge (struct loop
*loop
)
605 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
608 if (VEC_length (edge
, latches
) > 1)
610 latch
= find_subloop_latch_edge_by_profile (latches
);
613 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
614 should use cfghook for this, but it is hard to imagine it would
615 be useful elsewhere. */
616 && current_ir_type () == IR_GIMPLE
)
617 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
620 VEC_free (edge
, heap
, latches
);
624 /* Callback for make_forwarder_block. Returns true if the edge E is marked
625 in the set MFB_REIS_SET. */
627 static struct pointer_set_t
*mfb_reis_set
;
629 mfb_redirect_edges_in_set (edge e
)
631 return pointer_set_contains (mfb_reis_set
, e
);
634 /* Creates a subloop of LOOP with latch edge LATCH. */
637 form_subloop (struct loop
*loop
, edge latch
)
641 struct loop
*new_loop
;
643 mfb_reis_set
= pointer_set_create ();
644 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
647 pointer_set_insert (mfb_reis_set
, e
);
649 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
651 pointer_set_destroy (mfb_reis_set
);
653 loop
->header
= new_entry
->src
;
655 /* Find the blocks and subloops that belong to the new loop, and add it to
656 the appropriate place in the loop tree. */
657 new_loop
= alloc_loop ();
658 new_loop
->header
= new_entry
->dest
;
659 new_loop
->latch
= latch
->src
;
660 add_loop (new_loop
, loop
);
663 /* Make all the latch edges of LOOP to go to a single forwarder block --
664 a new latch of LOOP. */
667 merge_latch_edges (struct loop
*loop
)
669 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
673 gcc_assert (VEC_length (edge
, latches
) > 0);
675 if (VEC_length (edge
, latches
) == 1)
676 loop
->latch
= VEC_index (edge
, latches
, 0)->src
;
680 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
682 mfb_reis_set
= pointer_set_create ();
683 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
684 pointer_set_insert (mfb_reis_set
, e
);
685 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
687 pointer_set_destroy (mfb_reis_set
);
689 loop
->header
= latch
->dest
;
690 loop
->latch
= latch
->src
;
693 VEC_free (edge
, heap
, latches
);
696 /* LOOP may have several latch edges. Transform it into (possibly several)
697 loops with single latch edge. */
700 disambiguate_multiple_latches (struct loop
*loop
)
704 /* We eliminate the multiple latches by splitting the header to the forwarder
705 block F and the rest R, and redirecting the edges. There are two cases:
707 1) If there is a latch edge E that corresponds to a subloop (we guess
708 that based on profile -- if it is taken much more often than the
709 remaining edges; and on trees, using the information about induction
710 variables of the loops), we redirect E to R, all the remaining edges to
711 F, then rescan the loops and try again for the outer loop.
712 2) If there is no such edge, we redirect all latch edges to F, and the
713 entry edges to R, thus making F the single latch of the loop. */
716 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
719 /* During latch merging, we may need to redirect the entry edges to a new
720 block. This would cause problems if the entry edge was the one from the
721 entry block. To avoid having to handle this case specially, split
723 e
= find_edge (ENTRY_BLOCK_PTR
, loop
->header
);
729 e
= find_subloop_latch_edge (loop
);
733 form_subloop (loop
, e
);
736 merge_latch_edges (loop
);
739 /* Split loops with multiple latch edges. */
742 disambiguate_loops_with_multiple_latches (void)
747 FOR_EACH_LOOP (li
, loop
, 0)
750 disambiguate_multiple_latches (loop
);
754 /* Return nonzero if basic block BB belongs to LOOP. */
756 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
758 struct loop
*source_loop
;
760 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
763 source_loop
= bb
->loop_father
;
764 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
767 /* Enumeration predicate for get_loop_body_with_size. */
769 glb_enum_p (basic_block bb
, void *glb_loop
)
771 struct loop
*loop
= glb_loop
;
772 return (bb
!= loop
->header
773 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
776 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
777 order against direction of edges from latch. Specially, if
778 header != latch, latch is the 1-st block. LOOP cannot be the fake
779 loop tree root, and its size must be at most MAX_SIZE. The blocks
780 in the LOOP body are stored to BODY, and the size of the LOOP is
784 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
787 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
788 body
, max_size
, (void *) loop
);
791 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
792 order against direction of edges from latch. Specially, if
793 header != latch, latch is the 1-st block. */
796 get_loop_body (const struct loop
*loop
)
798 basic_block
*body
, bb
;
801 gcc_assert (loop
->num_nodes
);
803 body
= XCNEWVEC (basic_block
, loop
->num_nodes
);
805 if (loop
->latch
== EXIT_BLOCK_PTR
)
807 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
808 special-case the fake loop that contains the whole function. */
809 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
);
810 body
[tv
++] = loop
->header
;
811 body
[tv
++] = EXIT_BLOCK_PTR
;
816 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
818 gcc_assert (tv
== loop
->num_nodes
);
822 /* Fills dominance descendants inside LOOP of the basic block BB into
823 array TOVISIT from index *TV. */
826 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
827 basic_block
*tovisit
, int *tv
)
829 basic_block son
, postpone
= NULL
;
831 tovisit
[(*tv
)++] = bb
;
832 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
834 son
= next_dom_son (CDI_DOMINATORS
, son
))
836 if (!flow_bb_inside_loop_p (loop
, son
))
839 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
844 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
848 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
851 /* Gets body of a LOOP (that must be different from the outermost loop)
852 sorted by dominance relation. Additionally, if a basic block s dominates
853 the latch, then only blocks dominated by s are be after it. */
856 get_loop_body_in_dom_order (const struct loop
*loop
)
858 basic_block
*tovisit
;
861 gcc_assert (loop
->num_nodes
);
863 tovisit
= XCNEWVEC (basic_block
, loop
->num_nodes
);
865 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
868 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
870 gcc_assert (tv
== (int) loop
->num_nodes
);
875 /* Get body of a LOOP in breadth first sort order. */
878 get_loop_body_in_bfs_order (const struct loop
*loop
)
886 gcc_assert (loop
->num_nodes
);
887 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
889 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
890 visited
= BITMAP_ALLOC (NULL
);
893 while (i
< loop
->num_nodes
)
898 if (!bitmap_bit_p (visited
, bb
->index
))
900 /* This basic block is now visited */
901 bitmap_set_bit (visited
, bb
->index
);
905 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
907 if (flow_bb_inside_loop_p (loop
, e
->dest
))
909 if (!bitmap_bit_p (visited
, e
->dest
->index
))
911 bitmap_set_bit (visited
, e
->dest
->index
);
912 blocks
[i
++] = e
->dest
;
917 gcc_assert (i
>= vc
);
922 BITMAP_FREE (visited
);
926 /* Hash function for struct loop_exit. */
929 loop_exit_hash (const void *ex
)
931 struct loop_exit
*exit
= (struct loop_exit
*) ex
;
933 return htab_hash_pointer (exit
->e
);
936 /* Equality function for struct loop_exit. Compares with edge. */
939 loop_exit_eq (const void *ex
, const void *e
)
941 struct loop_exit
*exit
= (struct loop_exit
*) ex
;
946 /* Frees the list of loop exit descriptions EX. */
949 loop_exit_free (void *ex
)
951 struct loop_exit
*exit
= (struct loop_exit
*) ex
, *next
;
953 for (; exit
; exit
= next
)
957 exit
->next
->prev
= exit
->prev
;
958 exit
->prev
->next
= exit
->next
;
964 /* Returns the list of records for E as an exit of a loop. */
966 static struct loop_exit
*
967 get_exit_descriptions (edge e
)
969 return htab_find_with_hash (current_loops
->exits
, e
,
970 htab_hash_pointer (e
));
973 /* Updates the lists of loop exits in that E appears.
974 If REMOVED is true, E is being removed, and we
975 just remove it from the lists of exits.
976 If NEW_EDGE is true and E is not a loop exit, we
977 do not try to remove it from loop exit lists. */
980 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
983 struct loop_exit
*exits
= NULL
, *exit
;
984 struct loop
*aloop
, *cloop
;
986 if ((current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
) == 0)
990 && e
->src
->loop_father
!= NULL
991 && e
->dest
->loop_father
!= NULL
992 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
994 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
995 for (aloop
= e
->src
->loop_father
;
997 aloop
= aloop
->outer
)
999 exit
= XNEW (struct loop_exit
);
1002 exit
->next
= aloop
->exits
.next
;
1003 exit
->prev
= &aloop
->exits
;
1004 exit
->next
->prev
= exit
;
1005 exit
->prev
->next
= exit
;
1007 exit
->next_e
= exits
;
1012 if (!exits
&& new_edge
)
1015 slot
= htab_find_slot_with_hash (current_loops
->exits
, e
,
1016 htab_hash_pointer (e
),
1017 exits
? INSERT
: NO_INSERT
);
1024 loop_exit_free (*slot
);
1028 htab_clear_slot (current_loops
->exits
, slot
);
1031 /* For each loop, record list of exit edges, and start maintaining these
1035 record_loop_exits (void)
1041 if (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
)
1043 current_loops
->state
|= LOOPS_HAVE_RECORDED_EXITS
;
1045 gcc_assert (current_loops
->exits
== NULL
);
1046 current_loops
->exits
= htab_create (2 * number_of_loops (),
1053 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1055 rescan_loop_exit (e
, true, false);
1060 /* Dumps information about the exit in *SLOT to FILE.
1061 Callback for htab_traverse. */
1064 dump_recorded_exit (void **slot
, void *file
)
1066 struct loop_exit
*exit
= *slot
;
1070 for (; exit
!= NULL
; exit
= exit
->next_e
)
1073 fprintf (file
, "Edge %d->%d exits %u loops\n",
1074 e
->src
->index
, e
->dest
->index
, n
);
1079 /* Dumps the recorded exits of loops to FILE. */
1081 extern void dump_recorded_exits (FILE *);
1083 dump_recorded_exits (FILE *file
)
1085 if (!current_loops
->exits
)
1087 htab_traverse (current_loops
->exits
, dump_recorded_exit
, file
);
1090 /* Releases lists of loop exits. */
1093 release_recorded_exits (void)
1095 gcc_assert (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
);
1096 htab_delete (current_loops
->exits
);
1097 current_loops
->exits
= NULL
;
1098 current_loops
->state
&= ~LOOPS_HAVE_RECORDED_EXITS
;
1101 /* Returns the list of the exit edges of a LOOP. */
1104 get_loop_exit_edges (const struct loop
*loop
)
1106 VEC (edge
, heap
) *edges
= NULL
;
1111 struct loop_exit
*exit
;
1113 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1115 /* If we maintain the lists of exits, use them. Otherwise we must
1116 scan the body of the loop. */
1117 if (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
)
1119 for (exit
= loop
->exits
.next
; exit
->e
; exit
= exit
->next
)
1120 VEC_safe_push (edge
, heap
, edges
, exit
->e
);
1124 body
= get_loop_body (loop
);
1125 for (i
= 0; i
< loop
->num_nodes
; i
++)
1126 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1128 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1129 VEC_safe_push (edge
, heap
, edges
, e
);
1137 /* Counts the number of conditional branches inside LOOP. */
1140 num_loop_branches (const struct loop
*loop
)
1145 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1147 body
= get_loop_body (loop
);
1149 for (i
= 0; i
< loop
->num_nodes
; i
++)
1150 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1157 /* Adds basic block BB to LOOP. */
1159 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1165 gcc_assert (bb
->loop_father
== NULL
);
1166 bb
->loop_father
= loop
;
1167 bb
->loop_depth
= loop
->depth
;
1169 for (i
= 0; i
< loop
->depth
; i
++)
1170 loop
->pred
[i
]->num_nodes
++;
1172 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1174 rescan_loop_exit (e
, true, false);
1176 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1178 rescan_loop_exit (e
, true, false);
1182 /* Remove basic block BB from loops. */
1184 remove_bb_from_loops (basic_block bb
)
1187 struct loop
*loop
= bb
->loop_father
;
1191 gcc_assert (loop
!= NULL
);
1193 for (i
= 0; i
< loop
->depth
; i
++)
1194 loop
->pred
[i
]->num_nodes
--;
1195 bb
->loop_father
= NULL
;
1198 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1200 rescan_loop_exit (e
, false, true);
1202 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1204 rescan_loop_exit (e
, false, true);
1208 /* Finds nearest common ancestor in loop tree for given loops. */
1210 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1212 if (!loop_s
) return loop_d
;
1213 if (!loop_d
) return loop_s
;
1215 if (loop_s
->depth
< loop_d
->depth
)
1216 loop_d
= loop_d
->pred
[loop_s
->depth
];
1217 else if (loop_s
->depth
> loop_d
->depth
)
1218 loop_s
= loop_s
->pred
[loop_d
->depth
];
1220 while (loop_s
!= loop_d
)
1222 loop_s
= loop_s
->outer
;
1223 loop_d
= loop_d
->outer
;
1228 /* Removes LOOP from structures and frees its data. */
1231 delete_loop (struct loop
*loop
)
1233 /* Remove the loop from structure. */
1234 flow_loop_tree_node_remove (loop
);
1236 /* Remove loop from loops array. */
1237 VEC_replace (loop_p
, current_loops
->larray
, loop
->num
, NULL
);
1239 /* Free loop data. */
1240 flow_loop_free (loop
);
1243 /* Cancels the LOOP; it must be innermost one. */
1246 cancel_loop (struct loop
*loop
)
1251 gcc_assert (!loop
->inner
);
1253 /* Move blocks up one level (they should be removed as soon as possible). */
1254 bbs
= get_loop_body (loop
);
1255 for (i
= 0; i
< loop
->num_nodes
; i
++)
1256 bbs
[i
]->loop_father
= loop
->outer
;
1261 /* Cancels LOOP and all its subloops. */
1263 cancel_loop_tree (struct loop
*loop
)
1266 cancel_loop_tree (loop
->inner
);
1270 /* Checks that information about loops is correct
1271 -- sizes of loops are all right
1272 -- results of get_loop_body really belong to the loop
1273 -- loop header have just single entry edge and single latch edge
1274 -- loop latches have only single successor that is header of their loop
1275 -- irreducible loops are correctly marked
1278 verify_loop_structure (void)
1280 unsigned *sizes
, i
, j
;
1282 basic_block
*bbs
, bb
;
1286 unsigned num
= number_of_loops ();
1288 struct loop_exit
*exit
, *mexit
;
1291 sizes
= XCNEWVEC (unsigned, num
);
1295 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1298 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
1302 if (loop
->num_nodes
!= sizes
[i
])
1304 error ("size of loop %d should be %d, not %d",
1305 i
, sizes
[i
], loop
->num_nodes
);
1310 /* Check get_loop_body. */
1311 FOR_EACH_LOOP (li
, loop
, 0)
1313 bbs
= get_loop_body (loop
);
1315 for (j
= 0; j
< loop
->num_nodes
; j
++)
1316 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1318 error ("bb %d do not belong to loop %d",
1319 bbs
[j
]->index
, loop
->num
);
1325 /* Check headers and latches. */
1326 FOR_EACH_LOOP (li
, loop
, 0)
1330 if ((current_loops
->state
& LOOPS_HAVE_PREHEADERS
)
1331 && EDGE_COUNT (loop
->header
->preds
) != 2)
1333 error ("loop %d's header does not have exactly 2 entries", i
);
1336 if (current_loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1338 if (!single_succ_p (loop
->latch
))
1340 error ("loop %d's latch does not have exactly 1 successor", i
);
1343 if (single_succ (loop
->latch
) != loop
->header
)
1345 error ("loop %d's latch does not have header as successor", i
);
1348 if (loop
->latch
->loop_father
!= loop
)
1350 error ("loop %d's latch does not belong directly to it", i
);
1354 if (loop
->header
->loop_father
!= loop
)
1356 error ("loop %d's header does not belong directly to it", i
);
1359 if ((current_loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1360 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1362 error ("loop %d's latch is marked as part of irreducible region", i
);
1367 /* Check irreducible loops. */
1368 if (current_loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1370 /* Record old info. */
1371 irreds
= sbitmap_alloc (last_basic_block
);
1375 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1376 SET_BIT (irreds
, bb
->index
);
1378 RESET_BIT (irreds
, bb
->index
);
1379 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1380 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1381 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1385 mark_irreducible_loops ();
1392 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1393 && !TEST_BIT (irreds
, bb
->index
))
1395 error ("basic block %d should be marked irreducible", bb
->index
);
1398 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1399 && TEST_BIT (irreds
, bb
->index
))
1401 error ("basic block %d should not be marked irreducible", bb
->index
);
1404 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1406 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1407 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1409 error ("edge from %d to %d should be marked irreducible",
1410 e
->src
->index
, e
->dest
->index
);
1413 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1414 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1416 error ("edge from %d to %d should not be marked irreducible",
1417 e
->src
->index
, e
->dest
->index
);
1420 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1426 /* Check the recorded loop exits. */
1427 FOR_EACH_LOOP (li
, loop
, 0)
1429 if (loop
->exits
.e
!= NULL
)
1431 error ("corrupted head of the exits list of loop %d",
1437 /* Check that the list forms a cycle, and all elements except
1438 for the head are nonnull. */
1439 for (mexit
= &loop
->exits
, exit
= mexit
->next
, i
= 0;
1440 exit
->e
&& exit
!= mexit
;
1444 mexit
= mexit
->next
;
1447 if (exit
!= &loop
->exits
)
1449 error ("corrupted exits list of loop %d", loop
->num
);
1454 if ((current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
) == 0)
1456 if (loop
->exits
.next
!= &loop
->exits
)
1458 error ("nonempty exits list of loop %d, but exits are not recorded",
1465 if (current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
)
1467 unsigned n_exits
= 0, eloops
;
1469 memset (sizes
, 0, sizeof (unsigned) * num
);
1473 if (bb
->loop_father
== current_loops
->tree_root
)
1475 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1477 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1481 exit
= get_exit_descriptions (e
);
1484 error ("Exit %d->%d not recorded",
1485 e
->src
->index
, e
->dest
->index
);
1489 for (; exit
; exit
= exit
->next_e
)
1492 for (loop
= bb
->loop_father
;
1493 loop
!= e
->dest
->loop_father
;
1502 error ("Wrong list of exited loops for edge %d->%d",
1503 e
->src
->index
, e
->dest
->index
);
1509 if (n_exits
!= htab_elements (current_loops
->exits
))
1511 error ("Too many loop exits recorded");
1515 FOR_EACH_LOOP (li
, loop
, 0)
1518 for (exit
= loop
->exits
.next
; exit
->e
; exit
= exit
->next
)
1520 if (eloops
!= sizes
[loop
->num
])
1522 error ("%d exits recorded for loop %d (having %d exits)",
1523 eloops
, loop
->num
, sizes
[loop
->num
]);
1534 /* Returns latch edge of LOOP. */
1536 loop_latch_edge (const struct loop
*loop
)
1538 return find_edge (loop
->latch
, loop
->header
);
1541 /* Returns preheader edge of LOOP. */
1543 loop_preheader_edge (const struct loop
*loop
)
1548 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1549 if (e
->src
!= loop
->latch
)
1555 /* Returns true if E is an exit of LOOP. */
1558 loop_exit_edge_p (const struct loop
*loop
, edge e
)
1560 return (flow_bb_inside_loop_p (loop
, e
->src
)
1561 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1564 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1565 or more than one exit. If loops do not have the exits recorded, NULL
1566 is returned always. */
1569 single_exit (const struct loop
*loop
)
1571 struct loop_exit
*exit
= loop
->exits
.next
;
1573 if ((current_loops
->state
& LOOPS_HAVE_RECORDED_EXITS
) == 0)
1576 if (exit
->e
&& exit
->next
== &loop
->exits
)