1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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 VEC_truncate (loop_p
, loop
->superloops
, 0);
288 VEC_reserve (loop_p
, gc
, loop
->superloops
, depth
);
289 for (i
= 0; VEC_iterate (loop_p
, father
->superloops
, i
, ploop
); i
++)
290 VEC_quick_push (loop_p
, loop
->superloops
, ploop
);
291 VEC_quick_push (loop_p
, loop
->superloops
, father
);
293 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
294 establish_preds (ploop
, loop
);
297 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
298 added loop. If LOOP has some children, take care of that their
299 pred field will be initialized correctly. */
302 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
304 loop
->next
= father
->inner
;
305 father
->inner
= loop
;
307 establish_preds (loop
, father
);
310 /* Remove LOOP from the loop hierarchy tree. */
313 flow_loop_tree_node_remove (struct loop
*loop
)
315 struct loop
*prev
, *father
;
317 father
= loop_outer (loop
);
319 /* Remove loop from the list of sons. */
320 if (father
->inner
== loop
)
321 father
->inner
= loop
->next
;
324 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
326 prev
->next
= loop
->next
;
329 VEC_truncate (loop_p
, loop
->superloops
, 0);
332 /* Allocates and returns new loop structure. */
337 struct loop
*loop
= GGC_CNEW (struct loop
);
339 loop
->exits
= GGC_CNEW (struct loop_exit
);
340 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
345 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
346 (including the root of the loop tree). */
349 init_loops_structure (struct loops
*loops
, unsigned num_loops
)
353 memset (loops
, 0, sizeof *loops
);
354 loops
->larray
= VEC_alloc (loop_p
, gc
, num_loops
);
356 /* Dummy loop containing whole function. */
357 root
= alloc_loop ();
358 root
->num_nodes
= n_basic_blocks
;
359 root
->latch
= EXIT_BLOCK_PTR
;
360 root
->header
= ENTRY_BLOCK_PTR
;
361 ENTRY_BLOCK_PTR
->loop_father
= root
;
362 EXIT_BLOCK_PTR
->loop_father
= root
;
364 VEC_quick_push (loop_p
, loops
->larray
, root
);
365 loops
->tree_root
= root
;
368 /* Find all the natural loops in the function and save in LOOPS structure and
369 recalculate loop_depth information in basic block structures.
370 Return the number of natural loops found. */
373 flow_loops_find (struct loops
*loops
)
384 /* Ensure that the dominators are computed. */
385 calculate_dominance_info (CDI_DOMINATORS
);
387 /* Taking care of this degenerate case makes the rest of
388 this code simpler. */
389 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
391 init_loops_structure (loops
, 1);
398 /* Count the number of loop headers. This should be the
399 same as the number of natural loops. */
400 headers
= sbitmap_alloc (last_basic_block
);
401 sbitmap_zero (headers
);
408 header
->loop_depth
= 0;
410 /* If we have an abnormal predecessor, do not consider the
411 loop (not worth the problems). */
412 FOR_EACH_EDGE (e
, ei
, header
->preds
)
413 if (e
->flags
& EDGE_ABNORMAL
)
418 FOR_EACH_EDGE (e
, ei
, header
->preds
)
420 basic_block latch
= e
->src
;
422 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
424 /* Look for back edges where a predecessor is dominated
425 by this block. A natural loop has a single entry
426 node (header) that dominates all the nodes in the
427 loop. It also has single back edge to the header
428 from a latch node. */
429 if (latch
!= ENTRY_BLOCK_PTR
430 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
432 /* Shared headers should be eliminated by now. */
433 SET_BIT (headers
, header
->index
);
439 /* Allocate loop structures. */
440 init_loops_structure (loops
, num_loops
+ 1);
442 /* Find and record information about all the natural loops
445 bb
->loop_father
= loops
->tree_root
;
449 /* Compute depth first search order of the CFG so that outer
450 natural loops will be found before inner natural loops. */
451 dfs_order
= XNEWVEC (int, n_basic_blocks
);
452 rc_order
= XNEWVEC (int, n_basic_blocks
);
453 pre_and_rev_post_order_compute (dfs_order
, rc_order
, false);
457 for (b
= 0; b
< n_basic_blocks
- NUM_FIXED_BLOCKS
; b
++)
462 /* Search the nodes of the CFG in reverse completion order
463 so that we can find outer loops first. */
464 if (!TEST_BIT (headers
, rc_order
[b
]))
467 header
= BASIC_BLOCK (rc_order
[b
]);
469 loop
= alloc_loop ();
470 VEC_quick_push (loop_p
, loops
->larray
, loop
);
472 loop
->header
= header
;
473 loop
->num
= num_loops
;
476 flow_loop_tree_node_add (header
->loop_father
, loop
);
477 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
479 /* Look for the latch for this header block, if it has just a
481 FOR_EACH_EDGE (e
, ei
, header
->preds
)
483 basic_block latch
= e
->src
;
485 if (flow_bb_inside_loop_p (loop
, latch
))
487 if (loop
->latch
!= NULL
)
489 /* More than one latch edge. */
502 sbitmap_free (headers
);
505 return VEC_length (loop_p
, loops
->larray
);
508 /* Ratio of frequencies of edges so that one of more latch edges is
509 considered to belong to inner loop with same header. */
510 #define HEAVY_EDGE_RATIO 8
512 /* Minimum number of samples for that we apply
513 find_subloop_latch_edge_by_profile heuristics. */
514 #define HEAVY_EDGE_MIN_SAMPLES 10
516 /* If the profile info is available, finds an edge in LATCHES that much more
517 frequent than the remaining edges. Returns such an edge, or NULL if we do
520 We do not use guessed profile here, only the measured one. The guessed
521 profile is usually too flat and unreliable for this (and it is mostly based
522 on the loop structure of the program, so it does not make much sense to
523 derive the loop structure from it). */
526 find_subloop_latch_edge_by_profile (VEC (edge
, heap
) *latches
)
530 gcov_type mcount
= 0, tcount
= 0;
532 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
534 if (e
->count
> mcount
)
542 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
543 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
548 "Found latch edge %d -> %d using profile information.\n",
549 me
->src
->index
, me
->dest
->index
);
553 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
554 on the structure of induction variables. Returns this edge, or NULL if we
557 We are quite conservative, and look just for an obvious simple innermost
558 loop (which is the case where we would lose the most performance by not
559 disambiguating the loop). More precisely, we look for the following
560 situation: The source of the chosen latch edge dominates sources of all
561 the other latch edges. Additionally, the header does not contain a phi node
562 such that the argument from the chosen edge is equal to the argument from
566 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, VEC (edge
, heap
) *latches
)
568 edge e
, latch
= VEC_index (edge
, latches
, 0);
571 gimple_stmt_iterator psi
;
575 /* Find the candidate for the latch edge. */
576 for (i
= 1; VEC_iterate (edge
, latches
, i
, e
); i
++)
577 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
580 /* Verify that it dominates all the latch edges. */
581 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
582 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
585 /* Check for a phi node that would deny that this is a latch edge of
587 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
589 phi
= gsi_stmt (psi
);
590 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
592 /* Ignore the values that are not changed inside the subloop. */
593 if (TREE_CODE (lop
) != SSA_NAME
594 || SSA_NAME_DEF_STMT (lop
) == phi
)
596 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
597 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
600 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
602 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
608 "Found latch edge %d -> %d using iv structure.\n",
609 latch
->src
->index
, latch
->dest
->index
);
613 /* If we can determine that one of the several latch edges of LOOP behaves
614 as a latch edge of a separate subloop, returns this edge. Otherwise
618 find_subloop_latch_edge (struct loop
*loop
)
620 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
623 if (VEC_length (edge
, latches
) > 1)
625 latch
= find_subloop_latch_edge_by_profile (latches
);
628 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
629 should use cfghook for this, but it is hard to imagine it would
630 be useful elsewhere. */
631 && current_ir_type () == IR_GIMPLE
)
632 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
635 VEC_free (edge
, heap
, latches
);
639 /* Callback for make_forwarder_block. Returns true if the edge E is marked
640 in the set MFB_REIS_SET. */
642 static struct pointer_set_t
*mfb_reis_set
;
644 mfb_redirect_edges_in_set (edge e
)
646 return pointer_set_contains (mfb_reis_set
, e
);
649 /* Creates a subloop of LOOP with latch edge LATCH. */
652 form_subloop (struct loop
*loop
, edge latch
)
656 struct loop
*new_loop
;
658 mfb_reis_set
= pointer_set_create ();
659 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
662 pointer_set_insert (mfb_reis_set
, e
);
664 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
666 pointer_set_destroy (mfb_reis_set
);
668 loop
->header
= new_entry
->src
;
670 /* Find the blocks and subloops that belong to the new loop, and add it to
671 the appropriate place in the loop tree. */
672 new_loop
= alloc_loop ();
673 new_loop
->header
= new_entry
->dest
;
674 new_loop
->latch
= latch
->src
;
675 add_loop (new_loop
, loop
);
678 /* Make all the latch edges of LOOP to go to a single forwarder block --
679 a new latch of LOOP. */
682 merge_latch_edges (struct loop
*loop
)
684 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
688 gcc_assert (VEC_length (edge
, latches
) > 0);
690 if (VEC_length (edge
, latches
) == 1)
691 loop
->latch
= VEC_index (edge
, latches
, 0)->src
;
695 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
697 mfb_reis_set
= pointer_set_create ();
698 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
699 pointer_set_insert (mfb_reis_set
, e
);
700 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
702 pointer_set_destroy (mfb_reis_set
);
704 loop
->header
= latch
->dest
;
705 loop
->latch
= latch
->src
;
708 VEC_free (edge
, heap
, latches
);
711 /* LOOP may have several latch edges. Transform it into (possibly several)
712 loops with single latch edge. */
715 disambiguate_multiple_latches (struct loop
*loop
)
719 /* We eliminate the multiple latches by splitting the header to the forwarder
720 block F and the rest R, and redirecting the edges. There are two cases:
722 1) If there is a latch edge E that corresponds to a subloop (we guess
723 that based on profile -- if it is taken much more often than the
724 remaining edges; and on trees, using the information about induction
725 variables of the loops), we redirect E to R, all the remaining edges to
726 F, then rescan the loops and try again for the outer loop.
727 2) If there is no such edge, we redirect all latch edges to F, and the
728 entry edges to R, thus making F the single latch of the loop. */
731 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
734 /* During latch merging, we may need to redirect the entry edges to a new
735 block. This would cause problems if the entry edge was the one from the
736 entry block. To avoid having to handle this case specially, split
738 e
= find_edge (ENTRY_BLOCK_PTR
, loop
->header
);
744 e
= find_subloop_latch_edge (loop
);
748 form_subloop (loop
, e
);
751 merge_latch_edges (loop
);
754 /* Split loops with multiple latch edges. */
757 disambiguate_loops_with_multiple_latches (void)
762 FOR_EACH_LOOP (li
, loop
, 0)
765 disambiguate_multiple_latches (loop
);
769 /* Return nonzero if basic block BB belongs to LOOP. */
771 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
773 struct loop
*source_loop
;
775 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
778 source_loop
= bb
->loop_father
;
779 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
782 /* Enumeration predicate for get_loop_body_with_size. */
784 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
786 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
787 return (bb
!= loop
->header
788 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
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. LOOP cannot be the fake
794 loop tree root, and its size must be at most MAX_SIZE. The blocks
795 in the LOOP body are stored to BODY, and the size of the LOOP is
799 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
802 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
803 body
, max_size
, loop
);
806 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
807 order against direction of edges from latch. Specially, if
808 header != latch, latch is the 1-st block. */
811 get_loop_body (const struct loop
*loop
)
813 basic_block
*body
, bb
;
816 gcc_assert (loop
->num_nodes
);
818 body
= XCNEWVEC (basic_block
, loop
->num_nodes
);
820 if (loop
->latch
== EXIT_BLOCK_PTR
)
822 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
823 special-case the fake loop that contains the whole function. */
824 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
);
825 body
[tv
++] = loop
->header
;
826 body
[tv
++] = EXIT_BLOCK_PTR
;
831 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
833 gcc_assert (tv
== loop
->num_nodes
);
837 /* Fills dominance descendants inside LOOP of the basic block BB into
838 array TOVISIT from index *TV. */
841 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
842 basic_block
*tovisit
, int *tv
)
844 basic_block son
, postpone
= NULL
;
846 tovisit
[(*tv
)++] = bb
;
847 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
849 son
= next_dom_son (CDI_DOMINATORS
, son
))
851 if (!flow_bb_inside_loop_p (loop
, son
))
854 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
859 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
863 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
866 /* Gets body of a LOOP (that must be different from the outermost loop)
867 sorted by dominance relation. Additionally, if a basic block s dominates
868 the latch, then only blocks dominated by s are be after it. */
871 get_loop_body_in_dom_order (const struct loop
*loop
)
873 basic_block
*tovisit
;
876 gcc_assert (loop
->num_nodes
);
878 tovisit
= XCNEWVEC (basic_block
, loop
->num_nodes
);
880 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
883 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
885 gcc_assert (tv
== (int) loop
->num_nodes
);
890 /* Get body of a LOOP in breadth first sort order. */
893 get_loop_body_in_bfs_order (const struct loop
*loop
)
901 gcc_assert (loop
->num_nodes
);
902 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
904 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
905 visited
= BITMAP_ALLOC (NULL
);
908 while (i
< loop
->num_nodes
)
913 if (!bitmap_bit_p (visited
, bb
->index
))
915 /* This basic block is now visited */
916 bitmap_set_bit (visited
, bb
->index
);
920 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
922 if (flow_bb_inside_loop_p (loop
, e
->dest
))
924 if (!bitmap_bit_p (visited
, e
->dest
->index
))
926 bitmap_set_bit (visited
, e
->dest
->index
);
927 blocks
[i
++] = e
->dest
;
932 gcc_assert (i
>= vc
);
937 BITMAP_FREE (visited
);
941 /* Hash function for struct loop_exit. */
944 loop_exit_hash (const void *ex
)
946 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
948 return htab_hash_pointer (exit
->e
);
951 /* Equality function for struct loop_exit. Compares with edge. */
954 loop_exit_eq (const void *ex
, const void *e
)
956 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
961 /* Frees the list of loop exit descriptions EX. */
964 loop_exit_free (void *ex
)
966 struct loop_exit
*exit
= (struct loop_exit
*) ex
, *next
;
968 for (; exit
; exit
= next
)
972 exit
->next
->prev
= exit
->prev
;
973 exit
->prev
->next
= exit
->next
;
979 /* Returns the list of records for E as an exit of a loop. */
981 static struct loop_exit
*
982 get_exit_descriptions (edge e
)
984 return (struct loop_exit
*) htab_find_with_hash (current_loops
->exits
, e
,
985 htab_hash_pointer (e
));
988 /* Updates the lists of loop exits in that E appears.
989 If REMOVED is true, E is being removed, and we
990 just remove it from the lists of exits.
991 If NEW_EDGE is true and E is not a loop exit, we
992 do not try to remove it from loop exit lists. */
995 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
998 struct loop_exit
*exits
= NULL
, *exit
;
999 struct loop
*aloop
, *cloop
;
1001 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1005 && e
->src
->loop_father
!= NULL
1006 && e
->dest
->loop_father
!= NULL
1007 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1009 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1010 for (aloop
= e
->src
->loop_father
;
1012 aloop
= loop_outer (aloop
))
1014 exit
= GGC_NEW (struct loop_exit
);
1017 exit
->next
= aloop
->exits
->next
;
1018 exit
->prev
= aloop
->exits
;
1019 exit
->next
->prev
= exit
;
1020 exit
->prev
->next
= exit
;
1022 exit
->next_e
= exits
;
1027 if (!exits
&& new_edge
)
1030 slot
= htab_find_slot_with_hash (current_loops
->exits
, e
,
1031 htab_hash_pointer (e
),
1032 exits
? INSERT
: NO_INSERT
);
1039 loop_exit_free (*slot
);
1043 htab_clear_slot (current_loops
->exits
, slot
);
1046 /* For each loop, record list of exit edges, and start maintaining these
1050 record_loop_exits (void)
1059 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1061 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1063 gcc_assert (current_loops
->exits
== NULL
);
1064 current_loops
->exits
= htab_create_alloc (2 * number_of_loops (),
1068 ggc_calloc
, ggc_free
);
1072 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1074 rescan_loop_exit (e
, true, false);
1079 /* Dumps information about the exit in *SLOT to FILE.
1080 Callback for htab_traverse. */
1083 dump_recorded_exit (void **slot
, void *file
)
1085 struct loop_exit
*exit
= (struct loop_exit
*) *slot
;
1089 for (; exit
!= NULL
; exit
= exit
->next_e
)
1092 fprintf ((FILE*) file
, "Edge %d->%d exits %u loops\n",
1093 e
->src
->index
, e
->dest
->index
, n
);
1098 /* Dumps the recorded exits of loops to FILE. */
1100 extern void dump_recorded_exits (FILE *);
1102 dump_recorded_exits (FILE *file
)
1104 if (!current_loops
->exits
)
1106 htab_traverse (current_loops
->exits
, dump_recorded_exit
, file
);
1109 /* Releases lists of loop exits. */
1112 release_recorded_exits (void)
1114 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
));
1115 htab_delete (current_loops
->exits
);
1116 current_loops
->exits
= NULL
;
1117 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS
);
1120 /* Returns the list of the exit edges of a LOOP. */
1123 get_loop_exit_edges (const struct loop
*loop
)
1125 VEC (edge
, heap
) *edges
= NULL
;
1130 struct loop_exit
*exit
;
1132 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1134 /* If we maintain the lists of exits, use them. Otherwise we must
1135 scan the body of the loop. */
1136 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1138 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1139 VEC_safe_push (edge
, heap
, edges
, exit
->e
);
1143 body
= get_loop_body (loop
);
1144 for (i
= 0; i
< loop
->num_nodes
; i
++)
1145 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1147 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1148 VEC_safe_push (edge
, heap
, edges
, e
);
1156 /* Counts the number of conditional branches inside LOOP. */
1159 num_loop_branches (const struct loop
*loop
)
1164 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1166 body
= get_loop_body (loop
);
1168 for (i
= 0; i
< loop
->num_nodes
; i
++)
1169 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1176 /* Adds basic block BB to LOOP. */
1178 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1185 gcc_assert (bb
->loop_father
== NULL
);
1186 bb
->loop_father
= loop
;
1187 bb
->loop_depth
= loop_depth (loop
);
1189 for (i
= 0; VEC_iterate (loop_p
, loop
->superloops
, i
, ploop
); i
++)
1192 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1194 rescan_loop_exit (e
, true, false);
1196 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1198 rescan_loop_exit (e
, true, false);
1202 /* Remove basic block BB from loops. */
1204 remove_bb_from_loops (basic_block bb
)
1207 struct loop
*loop
= bb
->loop_father
;
1212 gcc_assert (loop
!= NULL
);
1214 for (i
= 0; VEC_iterate (loop_p
, loop
->superloops
, i
, ploop
); i
++)
1216 bb
->loop_father
= NULL
;
1219 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1221 rescan_loop_exit (e
, false, true);
1223 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1225 rescan_loop_exit (e
, false, true);
1229 /* Finds nearest common ancestor in loop tree for given loops. */
1231 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1233 unsigned sdepth
, ddepth
;
1235 if (!loop_s
) return loop_d
;
1236 if (!loop_d
) return loop_s
;
1238 sdepth
= loop_depth (loop_s
);
1239 ddepth
= loop_depth (loop_d
);
1241 if (sdepth
< ddepth
)
1242 loop_d
= VEC_index (loop_p
, loop_d
->superloops
, sdepth
);
1243 else if (sdepth
> ddepth
)
1244 loop_s
= VEC_index (loop_p
, loop_s
->superloops
, ddepth
);
1246 while (loop_s
!= loop_d
)
1248 loop_s
= loop_outer (loop_s
);
1249 loop_d
= loop_outer (loop_d
);
1254 /* Removes LOOP from structures and frees its data. */
1257 delete_loop (struct loop
*loop
)
1259 /* Remove the loop from structure. */
1260 flow_loop_tree_node_remove (loop
);
1262 /* Remove loop from loops array. */
1263 VEC_replace (loop_p
, current_loops
->larray
, loop
->num
, NULL
);
1265 /* Free loop data. */
1266 flow_loop_free (loop
);
1269 /* Cancels the LOOP; it must be innermost one. */
1272 cancel_loop (struct loop
*loop
)
1276 struct loop
*outer
= loop_outer (loop
);
1278 gcc_assert (!loop
->inner
);
1280 /* Move blocks up one level (they should be removed as soon as possible). */
1281 bbs
= get_loop_body (loop
);
1282 for (i
= 0; i
< loop
->num_nodes
; i
++)
1283 bbs
[i
]->loop_father
= outer
;
1288 /* Cancels LOOP and all its subloops. */
1290 cancel_loop_tree (struct loop
*loop
)
1293 cancel_loop_tree (loop
->inner
);
1297 /* Checks that information about loops is correct
1298 -- sizes of loops are all right
1299 -- results of get_loop_body really belong to the loop
1300 -- loop header have just single entry edge and single latch edge
1301 -- loop latches have only single successor that is header of their loop
1302 -- irreducible loops are correctly marked
1305 verify_loop_structure (void)
1307 unsigned *sizes
, i
, j
;
1309 basic_block
*bbs
, bb
;
1313 unsigned num
= number_of_loops ();
1315 struct loop_exit
*exit
, *mexit
;
1318 sizes
= XCNEWVEC (unsigned, num
);
1322 for (loop
= bb
->loop_father
; loop
; loop
= loop_outer (loop
))
1325 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
1329 if (loop
->num_nodes
!= sizes
[i
])
1331 error ("size of loop %d should be %d, not %d",
1332 i
, sizes
[i
], loop
->num_nodes
);
1337 /* Check get_loop_body. */
1338 FOR_EACH_LOOP (li
, loop
, 0)
1340 bbs
= get_loop_body (loop
);
1342 for (j
= 0; j
< loop
->num_nodes
; j
++)
1343 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1345 error ("bb %d do not belong to loop %d",
1346 bbs
[j
]->index
, loop
->num
);
1352 /* Check headers and latches. */
1353 FOR_EACH_LOOP (li
, loop
, 0)
1357 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1358 && EDGE_COUNT (loop
->header
->preds
) != 2)
1360 error ("loop %d's header does not have exactly 2 entries", i
);
1363 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1365 if (!single_succ_p (loop
->latch
))
1367 error ("loop %d's latch does not have exactly 1 successor", i
);
1370 if (single_succ (loop
->latch
) != loop
->header
)
1372 error ("loop %d's latch does not have header as successor", i
);
1375 if (loop
->latch
->loop_father
!= loop
)
1377 error ("loop %d's latch does not belong directly to it", i
);
1381 if (loop
->header
->loop_father
!= loop
)
1383 error ("loop %d's header does not belong directly to it", i
);
1386 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1387 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1389 error ("loop %d's latch is marked as part of irreducible region", i
);
1394 /* Check irreducible loops. */
1395 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1397 /* Record old info. */
1398 irreds
= sbitmap_alloc (last_basic_block
);
1402 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1403 SET_BIT (irreds
, bb
->index
);
1405 RESET_BIT (irreds
, bb
->index
);
1406 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1407 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1408 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1412 mark_irreducible_loops ();
1419 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1420 && !TEST_BIT (irreds
, bb
->index
))
1422 error ("basic block %d should be marked irreducible", bb
->index
);
1425 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1426 && TEST_BIT (irreds
, bb
->index
))
1428 error ("basic block %d should not be marked irreducible", bb
->index
);
1431 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1433 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1434 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1436 error ("edge from %d to %d should be marked irreducible",
1437 e
->src
->index
, e
->dest
->index
);
1440 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1441 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1443 error ("edge from %d to %d should not be marked irreducible",
1444 e
->src
->index
, e
->dest
->index
);
1447 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1453 /* Check the recorded loop exits. */
1454 FOR_EACH_LOOP (li
, loop
, 0)
1456 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1458 error ("corrupted head of the exits list of loop %d",
1464 /* Check that the list forms a cycle, and all elements except
1465 for the head are nonnull. */
1466 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1467 exit
->e
&& exit
!= mexit
;
1471 mexit
= mexit
->next
;
1474 if (exit
!= loop
->exits
)
1476 error ("corrupted exits list of loop %d", loop
->num
);
1481 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1483 if (loop
->exits
->next
!= loop
->exits
)
1485 error ("nonempty exits list of loop %d, but exits are not recorded",
1492 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1494 unsigned n_exits
= 0, eloops
;
1496 memset (sizes
, 0, sizeof (unsigned) * num
);
1500 if (bb
->loop_father
== current_loops
->tree_root
)
1502 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1504 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1508 exit
= get_exit_descriptions (e
);
1511 error ("Exit %d->%d not recorded",
1512 e
->src
->index
, e
->dest
->index
);
1516 for (; exit
; exit
= exit
->next_e
)
1519 for (loop
= bb
->loop_father
;
1520 loop
!= e
->dest
->loop_father
;
1521 loop
= loop_outer (loop
))
1529 error ("Wrong list of exited loops for edge %d->%d",
1530 e
->src
->index
, e
->dest
->index
);
1536 if (n_exits
!= htab_elements (current_loops
->exits
))
1538 error ("Too many loop exits recorded");
1542 FOR_EACH_LOOP (li
, loop
, 0)
1545 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1547 if (eloops
!= sizes
[loop
->num
])
1549 error ("%d exits recorded for loop %d (having %d exits)",
1550 eloops
, loop
->num
, sizes
[loop
->num
]);
1561 /* Returns latch edge of LOOP. */
1563 loop_latch_edge (const struct loop
*loop
)
1565 return find_edge (loop
->latch
, loop
->header
);
1568 /* Returns preheader edge of LOOP. */
1570 loop_preheader_edge (const struct loop
*loop
)
1575 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1577 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1578 if (e
->src
!= loop
->latch
)
1584 /* Returns true if E is an exit of LOOP. */
1587 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1589 return (flow_bb_inside_loop_p (loop
, e
->src
)
1590 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1593 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1594 or more than one exit. If loops do not have the exits recorded, NULL
1595 is returned always. */
1598 single_exit (const struct loop
*loop
)
1600 struct loop_exit
*exit
= loop
->exits
->next
;
1602 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1605 if (exit
->e
&& exit
->next
== loop
->exits
)