1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
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"
31 #include "diagnostic-core.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_alloc_cleared_loop ();
339 loop
->exits
= ggc_alloc_cleared_loop_exit ();
340 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
341 loop
->can_be_parallel
= false;
346 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
347 (including the root of the loop tree). */
350 init_loops_structure (struct loops
*loops
, unsigned num_loops
)
354 memset (loops
, 0, sizeof *loops
);
355 loops
->larray
= VEC_alloc (loop_p
, gc
, num_loops
);
357 /* Dummy loop containing whole function. */
358 root
= alloc_loop ();
359 root
->num_nodes
= n_basic_blocks
;
360 root
->latch
= EXIT_BLOCK_PTR
;
361 root
->header
= ENTRY_BLOCK_PTR
;
362 ENTRY_BLOCK_PTR
->loop_father
= root
;
363 EXIT_BLOCK_PTR
->loop_father
= root
;
365 VEC_quick_push (loop_p
, loops
->larray
, root
);
366 loops
->tree_root
= root
;
369 /* Find all the natural loops in the function and save in LOOPS structure and
370 recalculate loop_depth information in basic block structures.
371 Return the number of natural loops found. */
374 flow_loops_find (struct loops
*loops
)
385 /* Ensure that the dominators are computed. */
386 calculate_dominance_info (CDI_DOMINATORS
);
388 /* Taking care of this degenerate case makes the rest of
389 this code simpler. */
390 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
392 init_loops_structure (loops
, 1);
399 /* Count the number of loop headers. This should be the
400 same as the number of natural loops. */
401 headers
= sbitmap_alloc (last_basic_block
);
402 sbitmap_zero (headers
);
409 header
->loop_depth
= 0;
411 /* If we have an abnormal predecessor, do not consider the
412 loop (not worth the problems). */
413 FOR_EACH_EDGE (e
, ei
, header
->preds
)
414 if (e
->flags
& EDGE_ABNORMAL
)
419 FOR_EACH_EDGE (e
, ei
, header
->preds
)
421 basic_block latch
= e
->src
;
423 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
425 /* Look for back edges where a predecessor is dominated
426 by this block. A natural loop has a single entry
427 node (header) that dominates all the nodes in the
428 loop. It also has single back edge to the header
429 from a latch node. */
430 if (latch
!= ENTRY_BLOCK_PTR
431 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
433 /* Shared headers should be eliminated by now. */
434 SET_BIT (headers
, header
->index
);
440 /* Allocate loop structures. */
441 init_loops_structure (loops
, num_loops
+ 1);
443 /* Find and record information about all the natural loops
446 bb
->loop_father
= loops
->tree_root
;
450 /* Compute depth first search order of the CFG so that outer
451 natural loops will be found before inner natural loops. */
452 dfs_order
= XNEWVEC (int, n_basic_blocks
);
453 rc_order
= XNEWVEC (int, n_basic_blocks
);
454 pre_and_rev_post_order_compute (dfs_order
, rc_order
, false);
458 for (b
= 0; b
< n_basic_blocks
- NUM_FIXED_BLOCKS
; b
++)
463 /* Search the nodes of the CFG in reverse completion order
464 so that we can find outer loops first. */
465 if (!TEST_BIT (headers
, rc_order
[b
]))
468 header
= BASIC_BLOCK (rc_order
[b
]);
470 loop
= alloc_loop ();
471 VEC_quick_push (loop_p
, loops
->larray
, loop
);
473 loop
->header
= header
;
474 loop
->num
= num_loops
;
477 flow_loop_tree_node_add (header
->loop_father
, loop
);
478 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
480 /* Look for the latch for this header block, if it has just a
482 FOR_EACH_EDGE (e
, ei
, header
->preds
)
484 basic_block latch
= e
->src
;
486 if (flow_bb_inside_loop_p (loop
, latch
))
488 if (loop
->latch
!= NULL
)
490 /* More than one latch edge. */
503 sbitmap_free (headers
);
506 return VEC_length (loop_p
, loops
->larray
);
509 /* Ratio of frequencies of edges so that one of more latch edges is
510 considered to belong to inner loop with same header. */
511 #define HEAVY_EDGE_RATIO 8
513 /* Minimum number of samples for that we apply
514 find_subloop_latch_edge_by_profile heuristics. */
515 #define HEAVY_EDGE_MIN_SAMPLES 10
517 /* If the profile info is available, finds an edge in LATCHES that much more
518 frequent than the remaining edges. Returns such an edge, or NULL if we do
521 We do not use guessed profile here, only the measured one. The guessed
522 profile is usually too flat and unreliable for this (and it is mostly based
523 on the loop structure of the program, so it does not make much sense to
524 derive the loop structure from it). */
527 find_subloop_latch_edge_by_profile (VEC (edge
, heap
) *latches
)
531 gcov_type mcount
= 0, tcount
= 0;
533 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
535 if (e
->count
> mcount
)
543 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
544 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
549 "Found latch edge %d -> %d using profile information.\n",
550 me
->src
->index
, me
->dest
->index
);
554 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
555 on the structure of induction variables. Returns this edge, or NULL if we
558 We are quite conservative, and look just for an obvious simple innermost
559 loop (which is the case where we would lose the most performance by not
560 disambiguating the loop). More precisely, we look for the following
561 situation: The source of the chosen latch edge dominates sources of all
562 the other latch edges. Additionally, the header does not contain a phi node
563 such that the argument from the chosen edge is equal to the argument from
567 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, VEC (edge
, heap
) *latches
)
569 edge e
, latch
= VEC_index (edge
, latches
, 0);
572 gimple_stmt_iterator psi
;
576 /* Find the candidate for the latch edge. */
577 for (i
= 1; VEC_iterate (edge
, latches
, i
, e
); i
++)
578 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
581 /* Verify that it dominates all the latch edges. */
582 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
583 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
586 /* Check for a phi node that would deny that this is a latch edge of
588 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
590 phi
= gsi_stmt (psi
);
591 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
593 /* Ignore the values that are not changed inside the subloop. */
594 if (TREE_CODE (lop
) != SSA_NAME
595 || SSA_NAME_DEF_STMT (lop
) == phi
)
597 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
598 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
601 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
603 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
609 "Found latch edge %d -> %d using iv structure.\n",
610 latch
->src
->index
, latch
->dest
->index
);
614 /* If we can determine that one of the several latch edges of LOOP behaves
615 as a latch edge of a separate subloop, returns this edge. Otherwise
619 find_subloop_latch_edge (struct loop
*loop
)
621 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
624 if (VEC_length (edge
, latches
) > 1)
626 latch
= find_subloop_latch_edge_by_profile (latches
);
629 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
630 should use cfghook for this, but it is hard to imagine it would
631 be useful elsewhere. */
632 && current_ir_type () == IR_GIMPLE
)
633 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
636 VEC_free (edge
, heap
, latches
);
640 /* Callback for make_forwarder_block. Returns true if the edge E is marked
641 in the set MFB_REIS_SET. */
643 static struct pointer_set_t
*mfb_reis_set
;
645 mfb_redirect_edges_in_set (edge e
)
647 return pointer_set_contains (mfb_reis_set
, e
);
650 /* Creates a subloop of LOOP with latch edge LATCH. */
653 form_subloop (struct loop
*loop
, edge latch
)
657 struct loop
*new_loop
;
659 mfb_reis_set
= pointer_set_create ();
660 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
663 pointer_set_insert (mfb_reis_set
, e
);
665 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
667 pointer_set_destroy (mfb_reis_set
);
669 loop
->header
= new_entry
->src
;
671 /* Find the blocks and subloops that belong to the new loop, and add it to
672 the appropriate place in the loop tree. */
673 new_loop
= alloc_loop ();
674 new_loop
->header
= new_entry
->dest
;
675 new_loop
->latch
= latch
->src
;
676 add_loop (new_loop
, loop
);
679 /* Make all the latch edges of LOOP to go to a single forwarder block --
680 a new latch of LOOP. */
683 merge_latch_edges (struct loop
*loop
)
685 VEC (edge
, heap
) *latches
= get_loop_latch_edges (loop
);
689 gcc_assert (VEC_length (edge
, latches
) > 0);
691 if (VEC_length (edge
, latches
) == 1)
692 loop
->latch
= VEC_index (edge
, latches
, 0)->src
;
696 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
698 mfb_reis_set
= pointer_set_create ();
699 for (i
= 0; VEC_iterate (edge
, latches
, i
, e
); i
++)
700 pointer_set_insert (mfb_reis_set
, e
);
701 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
703 pointer_set_destroy (mfb_reis_set
);
705 loop
->header
= latch
->dest
;
706 loop
->latch
= latch
->src
;
709 VEC_free (edge
, heap
, latches
);
712 /* LOOP may have several latch edges. Transform it into (possibly several)
713 loops with single latch edge. */
716 disambiguate_multiple_latches (struct loop
*loop
)
720 /* We eliminate the multiple latches by splitting the header to the forwarder
721 block F and the rest R, and redirecting the edges. There are two cases:
723 1) If there is a latch edge E that corresponds to a subloop (we guess
724 that based on profile -- if it is taken much more often than the
725 remaining edges; and on trees, using the information about induction
726 variables of the loops), we redirect E to R, all the remaining edges to
727 F, then rescan the loops and try again for the outer loop.
728 2) If there is no such edge, we redirect all latch edges to F, and the
729 entry edges to R, thus making F the single latch of the loop. */
732 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
735 /* During latch merging, we may need to redirect the entry edges to a new
736 block. This would cause problems if the entry edge was the one from the
737 entry block. To avoid having to handle this case specially, split
739 e
= find_edge (ENTRY_BLOCK_PTR
, loop
->header
);
745 e
= find_subloop_latch_edge (loop
);
749 form_subloop (loop
, e
);
752 merge_latch_edges (loop
);
755 /* Split loops with multiple latch edges. */
758 disambiguate_loops_with_multiple_latches (void)
763 FOR_EACH_LOOP (li
, loop
, 0)
766 disambiguate_multiple_latches (loop
);
770 /* Return nonzero if basic block BB belongs to LOOP. */
772 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
774 struct loop
*source_loop
;
776 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
779 source_loop
= bb
->loop_father
;
780 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
783 /* Enumeration predicate for get_loop_body_with_size. */
785 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
787 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
788 return (bb
!= loop
->header
789 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
792 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
793 order against direction of edges from latch. Specially, if
794 header != latch, latch is the 1-st block. LOOP cannot be the fake
795 loop tree root, and its size must be at most MAX_SIZE. The blocks
796 in the LOOP body are stored to BODY, and the size of the LOOP is
800 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
803 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
804 body
, max_size
, loop
);
807 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
808 order against direction of edges from latch. Specially, if
809 header != latch, latch is the 1-st block. */
812 get_loop_body (const struct loop
*loop
)
814 basic_block
*body
, bb
;
817 gcc_assert (loop
->num_nodes
);
819 body
= XCNEWVEC (basic_block
, loop
->num_nodes
);
821 if (loop
->latch
== EXIT_BLOCK_PTR
)
823 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
824 special-case the fake loop that contains the whole function. */
825 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
);
826 body
[tv
++] = loop
->header
;
827 body
[tv
++] = EXIT_BLOCK_PTR
;
832 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
834 gcc_assert (tv
== loop
->num_nodes
);
838 /* Fills dominance descendants inside LOOP of the basic block BB into
839 array TOVISIT from index *TV. */
842 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
843 basic_block
*tovisit
, int *tv
)
845 basic_block son
, postpone
= NULL
;
847 tovisit
[(*tv
)++] = bb
;
848 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
850 son
= next_dom_son (CDI_DOMINATORS
, son
))
852 if (!flow_bb_inside_loop_p (loop
, son
))
855 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
860 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
864 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
867 /* Gets body of a LOOP (that must be different from the outermost loop)
868 sorted by dominance relation. Additionally, if a basic block s dominates
869 the latch, then only blocks dominated by s are be after it. */
872 get_loop_body_in_dom_order (const struct loop
*loop
)
874 basic_block
*tovisit
;
877 gcc_assert (loop
->num_nodes
);
879 tovisit
= XCNEWVEC (basic_block
, loop
->num_nodes
);
881 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
884 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
886 gcc_assert (tv
== (int) loop
->num_nodes
);
891 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
894 get_loop_body_in_custom_order (const struct loop
*loop
,
895 int (*bb_comparator
) (const void *, const void *))
897 basic_block
*bbs
= get_loop_body (loop
);
899 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
904 /* Get body of a LOOP in breadth first sort order. */
907 get_loop_body_in_bfs_order (const struct loop
*loop
)
915 gcc_assert (loop
->num_nodes
);
916 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
918 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
919 visited
= BITMAP_ALLOC (NULL
);
922 while (i
< loop
->num_nodes
)
927 if (!bitmap_bit_p (visited
, bb
->index
))
929 /* This basic block is now visited */
930 bitmap_set_bit (visited
, bb
->index
);
934 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
936 if (flow_bb_inside_loop_p (loop
, e
->dest
))
938 if (!bitmap_bit_p (visited
, e
->dest
->index
))
940 bitmap_set_bit (visited
, e
->dest
->index
);
941 blocks
[i
++] = e
->dest
;
946 gcc_assert (i
>= vc
);
951 BITMAP_FREE (visited
);
955 /* Hash function for struct loop_exit. */
958 loop_exit_hash (const void *ex
)
960 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
962 return htab_hash_pointer (exit
->e
);
965 /* Equality function for struct loop_exit. Compares with edge. */
968 loop_exit_eq (const void *ex
, const void *e
)
970 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
975 /* Frees the list of loop exit descriptions EX. */
978 loop_exit_free (void *ex
)
980 struct loop_exit
*exit
= (struct loop_exit
*) ex
, *next
;
982 for (; exit
; exit
= next
)
986 exit
->next
->prev
= exit
->prev
;
987 exit
->prev
->next
= exit
->next
;
993 /* Returns the list of records for E as an exit of a loop. */
995 static struct loop_exit
*
996 get_exit_descriptions (edge e
)
998 return (struct loop_exit
*) htab_find_with_hash (current_loops
->exits
, e
,
999 htab_hash_pointer (e
));
1002 /* Updates the lists of loop exits in that E appears.
1003 If REMOVED is true, E is being removed, and we
1004 just remove it from the lists of exits.
1005 If NEW_EDGE is true and E is not a loop exit, we
1006 do not try to remove it from loop exit lists. */
1009 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1012 struct loop_exit
*exits
= NULL
, *exit
;
1013 struct loop
*aloop
, *cloop
;
1015 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1019 && e
->src
->loop_father
!= NULL
1020 && e
->dest
->loop_father
!= NULL
1021 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1023 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1024 for (aloop
= e
->src
->loop_father
;
1026 aloop
= loop_outer (aloop
))
1028 exit
= ggc_alloc_loop_exit ();
1031 exit
->next
= aloop
->exits
->next
;
1032 exit
->prev
= aloop
->exits
;
1033 exit
->next
->prev
= exit
;
1034 exit
->prev
->next
= exit
;
1036 exit
->next_e
= exits
;
1041 if (!exits
&& new_edge
)
1044 slot
= htab_find_slot_with_hash (current_loops
->exits
, e
,
1045 htab_hash_pointer (e
),
1046 exits
? INSERT
: NO_INSERT
);
1053 loop_exit_free (*slot
);
1057 htab_clear_slot (current_loops
->exits
, slot
);
1060 /* For each loop, record list of exit edges, and start maintaining these
1064 record_loop_exits (void)
1073 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1075 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1077 gcc_assert (current_loops
->exits
== NULL
);
1078 current_loops
->exits
= htab_create_ggc (2 * number_of_loops (),
1079 loop_exit_hash
, loop_exit_eq
,
1084 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1086 rescan_loop_exit (e
, true, false);
1091 /* Dumps information about the exit in *SLOT to FILE.
1092 Callback for htab_traverse. */
1095 dump_recorded_exit (void **slot
, void *file
)
1097 struct loop_exit
*exit
= (struct loop_exit
*) *slot
;
1101 for (; exit
!= NULL
; exit
= exit
->next_e
)
1104 fprintf ((FILE*) file
, "Edge %d->%d exits %u loops\n",
1105 e
->src
->index
, e
->dest
->index
, n
);
1110 /* Dumps the recorded exits of loops to FILE. */
1112 extern void dump_recorded_exits (FILE *);
1114 dump_recorded_exits (FILE *file
)
1116 if (!current_loops
->exits
)
1118 htab_traverse (current_loops
->exits
, dump_recorded_exit
, file
);
1121 /* Releases lists of loop exits. */
1124 release_recorded_exits (void)
1126 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
));
1127 htab_delete (current_loops
->exits
);
1128 current_loops
->exits
= NULL
;
1129 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS
);
1132 /* Returns the list of the exit edges of a LOOP. */
1135 get_loop_exit_edges (const struct loop
*loop
)
1137 VEC (edge
, heap
) *edges
= NULL
;
1142 struct loop_exit
*exit
;
1144 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1146 /* If we maintain the lists of exits, use them. Otherwise we must
1147 scan the body of the loop. */
1148 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1150 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1151 VEC_safe_push (edge
, heap
, edges
, exit
->e
);
1155 body
= get_loop_body (loop
);
1156 for (i
= 0; i
< loop
->num_nodes
; i
++)
1157 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1159 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1160 VEC_safe_push (edge
, heap
, edges
, e
);
1168 /* Counts the number of conditional branches inside LOOP. */
1171 num_loop_branches (const struct loop
*loop
)
1176 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1178 body
= get_loop_body (loop
);
1180 for (i
= 0; i
< loop
->num_nodes
; i
++)
1181 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1188 /* Adds basic block BB to LOOP. */
1190 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1197 gcc_assert (bb
->loop_father
== NULL
);
1198 bb
->loop_father
= loop
;
1199 bb
->loop_depth
= loop_depth (loop
);
1201 for (i
= 0; VEC_iterate (loop_p
, loop
->superloops
, i
, ploop
); i
++)
1204 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1206 rescan_loop_exit (e
, true, false);
1208 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1210 rescan_loop_exit (e
, true, false);
1214 /* Remove basic block BB from loops. */
1216 remove_bb_from_loops (basic_block bb
)
1219 struct loop
*loop
= bb
->loop_father
;
1224 gcc_assert (loop
!= NULL
);
1226 for (i
= 0; VEC_iterate (loop_p
, loop
->superloops
, i
, ploop
); i
++)
1228 bb
->loop_father
= NULL
;
1231 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1233 rescan_loop_exit (e
, false, true);
1235 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1237 rescan_loop_exit (e
, false, true);
1241 /* Finds nearest common ancestor in loop tree for given loops. */
1243 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1245 unsigned sdepth
, ddepth
;
1247 if (!loop_s
) return loop_d
;
1248 if (!loop_d
) return loop_s
;
1250 sdepth
= loop_depth (loop_s
);
1251 ddepth
= loop_depth (loop_d
);
1253 if (sdepth
< ddepth
)
1254 loop_d
= VEC_index (loop_p
, loop_d
->superloops
, sdepth
);
1255 else if (sdepth
> ddepth
)
1256 loop_s
= VEC_index (loop_p
, loop_s
->superloops
, ddepth
);
1258 while (loop_s
!= loop_d
)
1260 loop_s
= loop_outer (loop_s
);
1261 loop_d
= loop_outer (loop_d
);
1266 /* Removes LOOP from structures and frees its data. */
1269 delete_loop (struct loop
*loop
)
1271 /* Remove the loop from structure. */
1272 flow_loop_tree_node_remove (loop
);
1274 /* Remove loop from loops array. */
1275 VEC_replace (loop_p
, current_loops
->larray
, loop
->num
, NULL
);
1277 /* Free loop data. */
1278 flow_loop_free (loop
);
1281 /* Cancels the LOOP; it must be innermost one. */
1284 cancel_loop (struct loop
*loop
)
1288 struct loop
*outer
= loop_outer (loop
);
1290 gcc_assert (!loop
->inner
);
1292 /* Move blocks up one level (they should be removed as soon as possible). */
1293 bbs
= get_loop_body (loop
);
1294 for (i
= 0; i
< loop
->num_nodes
; i
++)
1295 bbs
[i
]->loop_father
= outer
;
1300 /* Cancels LOOP and all its subloops. */
1302 cancel_loop_tree (struct loop
*loop
)
1305 cancel_loop_tree (loop
->inner
);
1309 /* Checks that information about loops is correct
1310 -- sizes of loops are all right
1311 -- results of get_loop_body really belong to the loop
1312 -- loop header have just single entry edge and single latch edge
1313 -- loop latches have only single successor that is header of their loop
1314 -- irreducible loops are correctly marked
1317 verify_loop_structure (void)
1319 unsigned *sizes
, i
, j
;
1321 basic_block
*bbs
, bb
;
1325 unsigned num
= number_of_loops ();
1327 struct loop_exit
*exit
, *mexit
;
1330 sizes
= XCNEWVEC (unsigned, num
);
1334 for (loop
= bb
->loop_father
; loop
; loop
= loop_outer (loop
))
1337 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
1341 if (loop
->num_nodes
!= sizes
[i
])
1343 error ("size of loop %d should be %d, not %d",
1344 i
, sizes
[i
], loop
->num_nodes
);
1349 /* Check get_loop_body. */
1350 FOR_EACH_LOOP (li
, loop
, 0)
1352 bbs
= get_loop_body (loop
);
1354 for (j
= 0; j
< loop
->num_nodes
; j
++)
1355 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1357 error ("bb %d do not belong to loop %d",
1358 bbs
[j
]->index
, loop
->num
);
1364 /* Check headers and latches. */
1365 FOR_EACH_LOOP (li
, loop
, 0)
1369 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1370 && EDGE_COUNT (loop
->header
->preds
) != 2)
1372 error ("loop %d's header does not have exactly 2 entries", i
);
1375 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1377 if (!single_succ_p (loop
->latch
))
1379 error ("loop %d's latch does not have exactly 1 successor", i
);
1382 if (single_succ (loop
->latch
) != loop
->header
)
1384 error ("loop %d's latch does not have header as successor", i
);
1387 if (loop
->latch
->loop_father
!= loop
)
1389 error ("loop %d's latch does not belong directly to it", i
);
1393 if (loop
->header
->loop_father
!= loop
)
1395 error ("loop %d's header does not belong directly to it", i
);
1398 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1399 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1401 error ("loop %d's latch is marked as part of irreducible region", i
);
1406 /* Check irreducible loops. */
1407 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1409 /* Record old info. */
1410 irreds
= sbitmap_alloc (last_basic_block
);
1414 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1415 SET_BIT (irreds
, bb
->index
);
1417 RESET_BIT (irreds
, bb
->index
);
1418 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1419 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1420 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1424 mark_irreducible_loops ();
1431 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1432 && !TEST_BIT (irreds
, bb
->index
))
1434 error ("basic block %d should be marked irreducible", bb
->index
);
1437 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1438 && TEST_BIT (irreds
, bb
->index
))
1440 error ("basic block %d should not be marked irreducible", bb
->index
);
1443 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1445 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1446 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1448 error ("edge from %d to %d should be marked irreducible",
1449 e
->src
->index
, e
->dest
->index
);
1452 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1453 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1455 error ("edge from %d to %d should not be marked irreducible",
1456 e
->src
->index
, e
->dest
->index
);
1459 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1465 /* Check the recorded loop exits. */
1466 FOR_EACH_LOOP (li
, loop
, 0)
1468 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1470 error ("corrupted head of the exits list of loop %d",
1476 /* Check that the list forms a cycle, and all elements except
1477 for the head are nonnull. */
1478 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1479 exit
->e
&& exit
!= mexit
;
1483 mexit
= mexit
->next
;
1486 if (exit
!= loop
->exits
)
1488 error ("corrupted exits list of loop %d", loop
->num
);
1493 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1495 if (loop
->exits
->next
!= loop
->exits
)
1497 error ("nonempty exits list of loop %d, but exits are not recorded",
1504 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1506 unsigned n_exits
= 0, eloops
;
1508 memset (sizes
, 0, sizeof (unsigned) * num
);
1512 if (bb
->loop_father
== current_loops
->tree_root
)
1514 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1516 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1520 exit
= get_exit_descriptions (e
);
1523 error ("Exit %d->%d not recorded",
1524 e
->src
->index
, e
->dest
->index
);
1528 for (; exit
; exit
= exit
->next_e
)
1531 for (loop
= bb
->loop_father
;
1532 loop
!= e
->dest
->loop_father
;
1533 loop
= loop_outer (loop
))
1541 error ("Wrong list of exited loops for edge %d->%d",
1542 e
->src
->index
, e
->dest
->index
);
1548 if (n_exits
!= htab_elements (current_loops
->exits
))
1550 error ("Too many loop exits recorded");
1554 FOR_EACH_LOOP (li
, loop
, 0)
1557 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1559 if (eloops
!= sizes
[loop
->num
])
1561 error ("%d exits recorded for loop %d (having %d exits)",
1562 eloops
, loop
->num
, sizes
[loop
->num
]);
1573 /* Returns latch edge of LOOP. */
1575 loop_latch_edge (const struct loop
*loop
)
1577 return find_edge (loop
->latch
, loop
->header
);
1580 /* Returns preheader edge of LOOP. */
1582 loop_preheader_edge (const struct loop
*loop
)
1587 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1589 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1590 if (e
->src
!= loop
->latch
)
1596 /* Returns true if E is an exit of LOOP. */
1599 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1601 return (flow_bb_inside_loop_p (loop
, e
->src
)
1602 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1605 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1606 or more than one exit. If loops do not have the exits recorded, NULL
1607 is returned always. */
1610 single_exit (const struct loop
*loop
)
1612 struct loop_exit
*exit
= loop
->exits
->next
;
1614 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1617 if (exit
->e
&& exit
->next
== loop
->exits
)
1623 /* Returns true when BB has an edge exiting LOOP. */
1626 is_loop_exit (struct loop
*loop
, basic_block bb
)
1631 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1632 if (loop_exit_edge_p (loop
, e
))