1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2013 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
28 #include "diagnostic-core.h"
31 #include "tree-flow.h"
32 #include "pointer-set.h"
36 static void flow_loops_cfg_dump (FILE *);
38 /* Dump loop related CFG information. */
41 flow_loops_cfg_dump (FILE *file
)
53 fprintf (file
, ";; %d succs { ", bb
->index
);
54 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
55 fprintf (file
, "%d ", succ
->dest
->index
);
56 fprintf (file
, "}\n");
60 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
63 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
65 unsigned odepth
= loop_depth (outer
);
67 return (loop_depth (loop
) > odepth
68 && (*loop
->superloops
)[odepth
] == outer
);
71 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
75 superloop_at_depth (struct loop
*loop
, unsigned depth
)
77 unsigned ldepth
= loop_depth (loop
);
79 gcc_assert (depth
<= ldepth
);
84 return (*loop
->superloops
)[depth
];
87 /* Returns the list of the latch edges of LOOP. */
90 get_loop_latch_edges (const struct loop
*loop
)
94 vec
<edge
> ret
= vNULL
;
96 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
98 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
105 /* Dump the loop information specified by LOOP to the stream FILE
106 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
109 flow_loop_dump (const struct loop
*loop
, FILE *file
,
110 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
118 if (! loop
|| ! loop
->header
)
121 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
123 fprintf (file
, ";; header %d, ", loop
->header
->index
);
125 fprintf (file
, "latch %d\n", loop
->latch
->index
);
128 fprintf (file
, "multiple latches:");
129 latches
= get_loop_latch_edges (loop
);
130 FOR_EACH_VEC_ELT (latches
, i
, e
)
131 fprintf (file
, " %d", e
->src
->index
);
133 fprintf (file
, "\n");
136 fprintf (file
, ";; depth %d, outer %ld\n",
137 loop_depth (loop
), (long) (loop_outer (loop
)
138 ? loop_outer (loop
)->num
: -1));
140 fprintf (file
, ";; nodes:");
141 bbs
= get_loop_body (loop
);
142 for (i
= 0; i
< loop
->num_nodes
; i
++)
143 fprintf (file
, " %d", bbs
[i
]->index
);
145 fprintf (file
, "\n");
148 loop_dump_aux (loop
, file
, verbose
);
151 /* Dump the loop information about loops to the stream FILE,
152 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
155 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
160 if (!current_loops
|| ! file
)
163 fprintf (file
, ";; %d loops found\n", number_of_loops ());
165 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
167 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
171 flow_loops_cfg_dump (file
);
174 /* Free data allocated for LOOP. */
177 flow_loop_free (struct loop
*loop
)
179 struct loop_exit
*exit
, *next
;
181 vec_free (loop
->superloops
);
183 /* Break the list of the loop exit records. They will be freed when the
184 corresponding edge is rescanned or removed, and this avoids
185 accessing the (already released) head of the list stored in the
187 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
194 ggc_free (loop
->exits
);
198 /* Free all the memory allocated for LOOPS. */
201 flow_loops_free (struct loops
*loops
)
208 /* Free the loop descriptors. */
209 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
214 flow_loop_free (loop
);
217 vec_free (loops
->larray
);
221 /* Find the nodes contained within the LOOP with header HEADER.
222 Return the number of nodes within the loop. */
225 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
227 vec
<basic_block
> stack
= vNULL
;
230 edge_iterator latch_ei
;
232 header
->loop_father
= loop
;
234 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
236 if (latch
->src
->loop_father
== loop
237 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
241 stack
.safe_push (latch
->src
);
242 latch
->src
->loop_father
= loop
;
244 while (!stack
.is_empty ())
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
;
260 stack
.safe_push (ancestor
);
270 /* Records the vector of superloops of the loop LOOP, whose immediate
271 superloop is FATHER. */
274 establish_preds (struct loop
*loop
, struct loop
*father
)
277 unsigned depth
= loop_depth (father
) + 1;
280 loop
->superloops
= 0;
281 vec_alloc (loop
->superloops
, depth
);
282 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
283 loop
->superloops
->quick_push (ploop
);
284 loop
->superloops
->quick_push (father
);
286 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
287 establish_preds (ploop
, loop
);
290 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
291 added loop. If LOOP has some children, take care of that their
292 pred field will be initialized correctly. */
295 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
297 loop
->next
= father
->inner
;
298 father
->inner
= loop
;
300 establish_preds (loop
, father
);
303 /* Remove LOOP from the loop hierarchy tree. */
306 flow_loop_tree_node_remove (struct loop
*loop
)
308 struct loop
*prev
, *father
;
310 father
= loop_outer (loop
);
312 /* Remove loop from the list of sons. */
313 if (father
->inner
== loop
)
314 father
->inner
= loop
->next
;
317 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
319 prev
->next
= loop
->next
;
322 loop
->superloops
= NULL
;
325 /* Allocates and returns new loop structure. */
330 struct loop
*loop
= ggc_alloc_cleared_loop ();
332 loop
->exits
= ggc_alloc_cleared_loop_exit ();
333 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
334 loop
->can_be_parallel
= false;
339 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
340 (including the root of the loop tree). */
343 init_loops_structure (struct loops
*loops
, unsigned num_loops
)
347 memset (loops
, 0, sizeof *loops
);
348 vec_alloc (loops
->larray
, num_loops
);
350 /* Dummy loop containing whole function. */
351 root
= alloc_loop ();
352 root
->num_nodes
= n_basic_blocks
;
353 root
->latch
= EXIT_BLOCK_PTR
;
354 root
->header
= ENTRY_BLOCK_PTR
;
355 ENTRY_BLOCK_PTR
->loop_father
= root
;
356 EXIT_BLOCK_PTR
->loop_father
= root
;
358 loops
->larray
->quick_push (root
);
359 loops
->tree_root
= root
;
362 /* Find all the natural loops in the function and save in LOOPS structure and
363 recalculate loop_father information in basic block structures.
364 Return the number of natural loops found. */
367 flow_loops_find (struct loops
*loops
)
378 /* Ensure that the dominators are computed. */
379 calculate_dominance_info (CDI_DOMINATORS
);
381 /* Taking care of this degenerate case makes the rest of
382 this code simpler. */
383 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
385 init_loops_structure (loops
, 1);
392 /* Count the number of loop headers. This should be the
393 same as the number of natural loops. */
394 headers
= sbitmap_alloc (last_basic_block
);
395 bitmap_clear (headers
);
402 /* If we have an abnormal predecessor, do not consider the
403 loop (not worth the problems). */
404 if (bb_has_abnormal_pred (header
))
407 FOR_EACH_EDGE (e
, ei
, header
->preds
)
409 basic_block latch
= e
->src
;
411 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
413 /* Look for back edges where a predecessor is dominated
414 by this block. A natural loop has a single entry
415 node (header) that dominates all the nodes in the
416 loop. It also has single back edge to the header
417 from a latch node. */
418 if (latch
!= ENTRY_BLOCK_PTR
419 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
421 /* Shared headers should be eliminated by now. */
422 bitmap_set_bit (headers
, header
->index
);
428 /* Allocate loop structures. */
429 init_loops_structure (loops
, num_loops
+ 1);
431 /* Find and record information about all the natural loops
434 bb
->loop_father
= loops
->tree_root
;
438 /* Compute depth first search order of the CFG so that outer
439 natural loops will be found before inner natural loops. */
440 dfs_order
= XNEWVEC (int, n_basic_blocks
);
441 rc_order
= XNEWVEC (int, n_basic_blocks
);
442 pre_and_rev_post_order_compute (dfs_order
, rc_order
, false);
446 for (b
= 0; b
< n_basic_blocks
- NUM_FIXED_BLOCKS
; b
++)
451 /* Search the nodes of the CFG in reverse completion order
452 so that we can find outer loops first. */
453 if (!bitmap_bit_p (headers
, rc_order
[b
]))
456 header
= BASIC_BLOCK (rc_order
[b
]);
458 loop
= alloc_loop ();
459 loops
->larray
->quick_push (loop
);
461 loop
->header
= header
;
462 loop
->num
= num_loops
;
465 flow_loop_tree_node_add (header
->loop_father
, loop
);
466 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
468 /* Look for the latch for this header block, if it has just a
470 FOR_EACH_EDGE (e
, ei
, header
->preds
)
472 basic_block latch
= e
->src
;
474 if (flow_bb_inside_loop_p (loop
, latch
))
476 if (loop
->latch
!= NULL
)
478 /* More than one latch edge. */
491 sbitmap_free (headers
);
494 return loops
->larray
->length ();
497 /* Ratio of frequencies of edges so that one of more latch edges is
498 considered to belong to inner loop with same header. */
499 #define HEAVY_EDGE_RATIO 8
501 /* Minimum number of samples for that we apply
502 find_subloop_latch_edge_by_profile heuristics. */
503 #define HEAVY_EDGE_MIN_SAMPLES 10
505 /* If the profile info is available, finds an edge in LATCHES that much more
506 frequent than the remaining edges. Returns such an edge, or NULL if we do
509 We do not use guessed profile here, only the measured one. The guessed
510 profile is usually too flat and unreliable for this (and it is mostly based
511 on the loop structure of the program, so it does not make much sense to
512 derive the loop structure from it). */
515 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
519 gcov_type mcount
= 0, tcount
= 0;
521 FOR_EACH_VEC_ELT (latches
, i
, e
)
523 if (e
->count
> mcount
)
531 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
532 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
537 "Found latch edge %d -> %d using profile information.\n",
538 me
->src
->index
, me
->dest
->index
);
542 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
543 on the structure of induction variables. Returns this edge, or NULL if we
546 We are quite conservative, and look just for an obvious simple innermost
547 loop (which is the case where we would lose the most performance by not
548 disambiguating the loop). More precisely, we look for the following
549 situation: The source of the chosen latch edge dominates sources of all
550 the other latch edges. Additionally, the header does not contain a phi node
551 such that the argument from the chosen edge is equal to the argument from
555 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
557 edge e
, latch
= latches
[0];
560 gimple_stmt_iterator psi
;
564 /* Find the candidate for the latch edge. */
565 for (i
= 1; latches
.iterate (i
, &e
); i
++)
566 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
569 /* Verify that it dominates all the latch edges. */
570 FOR_EACH_VEC_ELT (latches
, i
, e
)
571 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
574 /* Check for a phi node that would deny that this is a latch edge of
576 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
578 phi
= gsi_stmt (psi
);
579 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
581 /* Ignore the values that are not changed inside the subloop. */
582 if (TREE_CODE (lop
) != SSA_NAME
583 || SSA_NAME_DEF_STMT (lop
) == phi
)
585 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
586 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
589 FOR_EACH_VEC_ELT (latches
, i
, e
)
591 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
597 "Found latch edge %d -> %d using iv structure.\n",
598 latch
->src
->index
, latch
->dest
->index
);
602 /* If we can determine that one of the several latch edges of LOOP behaves
603 as a latch edge of a separate subloop, returns this edge. Otherwise
607 find_subloop_latch_edge (struct loop
*loop
)
609 vec
<edge
> latches
= get_loop_latch_edges (loop
);
612 if (latches
.length () > 1)
614 latch
= find_subloop_latch_edge_by_profile (latches
);
617 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
618 should use cfghook for this, but it is hard to imagine it would
619 be useful elsewhere. */
620 && current_ir_type () == IR_GIMPLE
)
621 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
628 /* Callback for make_forwarder_block. Returns true if the edge E is marked
629 in the set MFB_REIS_SET. */
631 static struct pointer_set_t
*mfb_reis_set
;
633 mfb_redirect_edges_in_set (edge e
)
635 return pointer_set_contains (mfb_reis_set
, e
);
638 /* Creates a subloop of LOOP with latch edge LATCH. */
641 form_subloop (struct loop
*loop
, edge latch
)
645 struct loop
*new_loop
;
647 mfb_reis_set
= pointer_set_create ();
648 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
651 pointer_set_insert (mfb_reis_set
, e
);
653 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
655 pointer_set_destroy (mfb_reis_set
);
657 loop
->header
= new_entry
->src
;
659 /* Find the blocks and subloops that belong to the new loop, and add it to
660 the appropriate place in the loop tree. */
661 new_loop
= alloc_loop ();
662 new_loop
->header
= new_entry
->dest
;
663 new_loop
->latch
= latch
->src
;
664 add_loop (new_loop
, loop
);
667 /* Make all the latch edges of LOOP to go to a single forwarder block --
668 a new latch of LOOP. */
671 merge_latch_edges (struct loop
*loop
)
673 vec
<edge
> latches
= get_loop_latch_edges (loop
);
677 gcc_assert (latches
.length () > 0);
679 if (latches
.length () == 1)
680 loop
->latch
= latches
[0]->src
;
684 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
686 mfb_reis_set
= pointer_set_create ();
687 FOR_EACH_VEC_ELT (latches
, i
, e
)
688 pointer_set_insert (mfb_reis_set
, e
);
689 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
691 pointer_set_destroy (mfb_reis_set
);
693 loop
->header
= latch
->dest
;
694 loop
->latch
= latch
->src
;
700 /* LOOP may have several latch edges. Transform it into (possibly several)
701 loops with single latch edge. */
704 disambiguate_multiple_latches (struct loop
*loop
)
708 /* We eliminate the multiple latches by splitting the header to the forwarder
709 block F and the rest R, and redirecting the edges. There are two cases:
711 1) If there is a latch edge E that corresponds to a subloop (we guess
712 that based on profile -- if it is taken much more often than the
713 remaining edges; and on trees, using the information about induction
714 variables of the loops), we redirect E to R, all the remaining edges to
715 F, then rescan the loops and try again for the outer loop.
716 2) If there is no such edge, we redirect all latch edges to F, and the
717 entry edges to R, thus making F the single latch of the loop. */
720 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
723 /* During latch merging, we may need to redirect the entry edges to a new
724 block. This would cause problems if the entry edge was the one from the
725 entry block. To avoid having to handle this case specially, split
727 e
= find_edge (ENTRY_BLOCK_PTR
, loop
->header
);
733 e
= find_subloop_latch_edge (loop
);
737 form_subloop (loop
, e
);
740 merge_latch_edges (loop
);
743 /* Split loops with multiple latch edges. */
746 disambiguate_loops_with_multiple_latches (void)
751 FOR_EACH_LOOP (li
, loop
, 0)
754 disambiguate_multiple_latches (loop
);
758 /* Return nonzero if basic block BB belongs to LOOP. */
760 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
762 struct loop
*source_loop
;
764 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
767 source_loop
= bb
->loop_father
;
768 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
771 /* Enumeration predicate for get_loop_body_with_size. */
773 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
775 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
776 return (bb
!= loop
->header
777 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
780 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
781 order against direction of edges from latch. Specially, if
782 header != latch, latch is the 1-st block. LOOP cannot be the fake
783 loop tree root, and its size must be at most MAX_SIZE. The blocks
784 in the LOOP body are stored to BODY, and the size of the LOOP is
788 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
791 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
792 body
, max_size
, loop
);
795 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
796 order against direction of edges from latch. Specially, if
797 header != latch, latch is the 1-st block. */
800 get_loop_body (const struct loop
*loop
)
802 basic_block
*body
, bb
;
805 gcc_assert (loop
->num_nodes
);
807 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
809 if (loop
->latch
== EXIT_BLOCK_PTR
)
811 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
812 special-case the fake loop that contains the whole function. */
813 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
);
814 body
[tv
++] = loop
->header
;
815 body
[tv
++] = EXIT_BLOCK_PTR
;
820 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
822 gcc_assert (tv
== loop
->num_nodes
);
826 /* Fills dominance descendants inside LOOP of the basic block BB into
827 array TOVISIT from index *TV. */
830 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
831 basic_block
*tovisit
, int *tv
)
833 basic_block son
, postpone
= NULL
;
835 tovisit
[(*tv
)++] = bb
;
836 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
838 son
= next_dom_son (CDI_DOMINATORS
, son
))
840 if (!flow_bb_inside_loop_p (loop
, son
))
843 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
848 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
852 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
855 /* Gets body of a LOOP (that must be different from the outermost loop)
856 sorted by dominance relation. Additionally, if a basic block s dominates
857 the latch, then only blocks dominated by s are be after it. */
860 get_loop_body_in_dom_order (const struct loop
*loop
)
862 basic_block
*tovisit
;
865 gcc_assert (loop
->num_nodes
);
867 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
869 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
872 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
874 gcc_assert (tv
== (int) loop
->num_nodes
);
879 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
882 get_loop_body_in_custom_order (const struct loop
*loop
,
883 int (*bb_comparator
) (const void *, const void *))
885 basic_block
*bbs
= get_loop_body (loop
);
887 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
892 /* Get body of a LOOP in breadth first sort order. */
895 get_loop_body_in_bfs_order (const struct loop
*loop
)
903 gcc_assert (loop
->num_nodes
);
904 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
906 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
907 visited
= BITMAP_ALLOC (NULL
);
910 while (i
< loop
->num_nodes
)
915 if (bitmap_set_bit (visited
, bb
->index
))
916 /* This basic block is now visited */
919 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
921 if (flow_bb_inside_loop_p (loop
, e
->dest
))
923 if (bitmap_set_bit (visited
, e
->dest
->index
))
924 blocks
[i
++] = e
->dest
;
928 gcc_assert (i
>= vc
);
933 BITMAP_FREE (visited
);
937 /* Hash function for struct loop_exit. */
940 loop_exit_hash (const void *ex
)
942 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
944 return htab_hash_pointer (exit
->e
);
947 /* Equality function for struct loop_exit. Compares with edge. */
950 loop_exit_eq (const void *ex
, const void *e
)
952 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
957 /* Frees the list of loop exit descriptions EX. */
960 loop_exit_free (void *ex
)
962 struct loop_exit
*exit
= (struct loop_exit
*) ex
, *next
;
964 for (; exit
; exit
= next
)
968 exit
->next
->prev
= exit
->prev
;
969 exit
->prev
->next
= exit
->next
;
975 /* Returns the list of records for E as an exit of a loop. */
977 static struct loop_exit
*
978 get_exit_descriptions (edge e
)
980 return (struct loop_exit
*) htab_find_with_hash (current_loops
->exits
, e
,
981 htab_hash_pointer (e
));
984 /* Updates the lists of loop exits in that E appears.
985 If REMOVED is true, E is being removed, and we
986 just remove it from the lists of exits.
987 If NEW_EDGE is true and E is not a loop exit, we
988 do not try to remove it from loop exit lists. */
991 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
994 struct loop_exit
*exits
= NULL
, *exit
;
995 struct loop
*aloop
, *cloop
;
997 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1001 && e
->src
->loop_father
!= NULL
1002 && e
->dest
->loop_father
!= NULL
1003 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1005 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1006 for (aloop
= e
->src
->loop_father
;
1008 aloop
= loop_outer (aloop
))
1010 exit
= ggc_alloc_loop_exit ();
1013 exit
->next
= aloop
->exits
->next
;
1014 exit
->prev
= aloop
->exits
;
1015 exit
->next
->prev
= exit
;
1016 exit
->prev
->next
= exit
;
1018 exit
->next_e
= exits
;
1023 if (!exits
&& new_edge
)
1026 slot
= htab_find_slot_with_hash (current_loops
->exits
, e
,
1027 htab_hash_pointer (e
),
1028 exits
? INSERT
: NO_INSERT
);
1035 loop_exit_free (*slot
);
1039 htab_clear_slot (current_loops
->exits
, slot
);
1042 /* For each loop, record list of exit edges, and start maintaining these
1046 record_loop_exits (void)
1055 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1057 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1059 gcc_assert (current_loops
->exits
== NULL
);
1060 current_loops
->exits
= htab_create_ggc (2 * number_of_loops (),
1061 loop_exit_hash
, loop_exit_eq
,
1066 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1068 rescan_loop_exit (e
, true, false);
1073 /* Dumps information about the exit in *SLOT to FILE.
1074 Callback for htab_traverse. */
1077 dump_recorded_exit (void **slot
, void *file
)
1079 struct loop_exit
*exit
= (struct loop_exit
*) *slot
;
1083 for (; exit
!= NULL
; exit
= exit
->next_e
)
1086 fprintf ((FILE*) file
, "Edge %d->%d exits %u loops\n",
1087 e
->src
->index
, e
->dest
->index
, n
);
1092 /* Dumps the recorded exits of loops to FILE. */
1094 extern void dump_recorded_exits (FILE *);
1096 dump_recorded_exits (FILE *file
)
1098 if (!current_loops
->exits
)
1100 htab_traverse (current_loops
->exits
, dump_recorded_exit
, file
);
1103 /* Releases lists of loop exits. */
1106 release_recorded_exits (void)
1108 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
));
1109 htab_delete (current_loops
->exits
);
1110 current_loops
->exits
= NULL
;
1111 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS
);
1114 /* Returns the list of the exit edges of a LOOP. */
1117 get_loop_exit_edges (const struct loop
*loop
)
1119 vec
<edge
> edges
= vNULL
;
1124 struct loop_exit
*exit
;
1126 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1128 /* If we maintain the lists of exits, use them. Otherwise we must
1129 scan the body of the loop. */
1130 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1132 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1133 edges
.safe_push (exit
->e
);
1137 body
= get_loop_body (loop
);
1138 for (i
= 0; i
< loop
->num_nodes
; i
++)
1139 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1141 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1142 edges
.safe_push (e
);
1150 /* Counts the number of conditional branches inside LOOP. */
1153 num_loop_branches (const struct loop
*loop
)
1158 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1160 body
= get_loop_body (loop
);
1162 for (i
= 0; i
< loop
->num_nodes
; i
++)
1163 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1170 /* Adds basic block BB to LOOP. */
1172 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1179 gcc_assert (bb
->loop_father
== NULL
);
1180 bb
->loop_father
= loop
;
1182 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1185 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1187 rescan_loop_exit (e
, true, false);
1189 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1191 rescan_loop_exit (e
, true, false);
1195 /* Remove basic block BB from loops. */
1197 remove_bb_from_loops (basic_block bb
)
1200 struct loop
*loop
= bb
->loop_father
;
1205 gcc_assert (loop
!= NULL
);
1207 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1209 bb
->loop_father
= NULL
;
1211 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1213 rescan_loop_exit (e
, false, true);
1215 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1217 rescan_loop_exit (e
, false, true);
1221 /* Finds nearest common ancestor in loop tree for given loops. */
1223 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1225 unsigned sdepth
, ddepth
;
1227 if (!loop_s
) return loop_d
;
1228 if (!loop_d
) return loop_s
;
1230 sdepth
= loop_depth (loop_s
);
1231 ddepth
= loop_depth (loop_d
);
1233 if (sdepth
< ddepth
)
1234 loop_d
= (*loop_d
->superloops
)[sdepth
];
1235 else if (sdepth
> ddepth
)
1236 loop_s
= (*loop_s
->superloops
)[ddepth
];
1238 while (loop_s
!= loop_d
)
1240 loop_s
= loop_outer (loop_s
);
1241 loop_d
= loop_outer (loop_d
);
1246 /* Removes LOOP from structures and frees its data. */
1249 delete_loop (struct loop
*loop
)
1251 /* Remove the loop from structure. */
1252 flow_loop_tree_node_remove (loop
);
1254 /* Remove loop from loops array. */
1255 (*current_loops
->larray
)[loop
->num
] = NULL
;
1257 /* Free loop data. */
1258 flow_loop_free (loop
);
1261 /* Cancels the LOOP; it must be innermost one. */
1264 cancel_loop (struct loop
*loop
)
1268 struct loop
*outer
= loop_outer (loop
);
1270 gcc_assert (!loop
->inner
);
1272 /* Move blocks up one level (they should be removed as soon as possible). */
1273 bbs
= get_loop_body (loop
);
1274 for (i
= 0; i
< loop
->num_nodes
; i
++)
1275 bbs
[i
]->loop_father
= outer
;
1281 /* Cancels LOOP and all its subloops. */
1283 cancel_loop_tree (struct loop
*loop
)
1286 cancel_loop_tree (loop
->inner
);
1290 /* Checks that information about loops is correct
1291 -- sizes of loops are all right
1292 -- results of get_loop_body really belong to the loop
1293 -- loop header have just single entry edge and single latch edge
1294 -- loop latches have only single successor that is header of their loop
1295 -- irreducible loops are correctly marked
1296 -- the cached loop depth and loop father of each bb is correct
1299 verify_loop_structure (void)
1301 unsigned *sizes
, i
, j
;
1303 basic_block
*bbs
, bb
;
1307 unsigned num
= number_of_loops ();
1309 struct loop_exit
*exit
, *mexit
;
1310 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1311 sbitmap visited
= sbitmap_alloc (last_basic_block
);
1313 /* We need up-to-date dominators, compute or verify them. */
1315 calculate_dominance_info (CDI_DOMINATORS
);
1317 verify_dominators (CDI_DOMINATORS
);
1320 sizes
= XCNEWVEC (unsigned, num
);
1324 for (loop
= bb
->loop_father
; loop
; loop
= loop_outer (loop
))
1327 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
1331 if (loop
->num_nodes
!= sizes
[i
])
1333 error ("size of loop %d should be %d, not %d",
1334 i
, sizes
[i
], loop
->num_nodes
);
1339 /* Check get_loop_body. */
1340 FOR_EACH_LOOP (li
, loop
, 0)
1342 bbs
= get_loop_body (loop
);
1344 for (j
= 0; j
< loop
->num_nodes
; j
++)
1345 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1347 error ("bb %d does not belong to loop %d",
1348 bbs
[j
]->index
, loop
->num
);
1353 bitmap_clear (visited
);
1354 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1356 bbs
= get_loop_body (loop
);
1358 for (j
= 0; j
< loop
->num_nodes
; j
++)
1362 /* Ignore this block if it is in an inner loop. */
1363 if (bitmap_bit_p (visited
, bb
->index
))
1365 bitmap_set_bit (visited
, bb
->index
);
1367 if (bb
->loop_father
!= loop
)
1369 error ("bb %d has father loop %d, should be loop %d",
1370 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1377 /* Check headers and latches. */
1378 FOR_EACH_LOOP (li
, loop
, 0)
1382 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1383 && EDGE_COUNT (loop
->header
->preds
) != 2)
1385 error ("loop %d%'s header does not have exactly 2 entries", i
);
1388 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1390 if (!single_succ_p (loop
->latch
))
1392 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1395 if (single_succ (loop
->latch
) != loop
->header
)
1397 error ("loop %d%'s latch does not have header as successor", i
);
1400 if (loop
->latch
->loop_father
!= loop
)
1402 error ("loop %d%'s latch does not belong directly to it", i
);
1406 if (loop
->header
->loop_father
!= loop
)
1408 error ("loop %d%'s header does not belong directly to it", i
);
1411 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1412 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1414 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1419 /* Check irreducible loops. */
1420 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1422 /* Record old info. */
1423 irreds
= sbitmap_alloc (last_basic_block
);
1427 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1428 bitmap_set_bit (irreds
, bb
->index
);
1430 bitmap_clear_bit (irreds
, bb
->index
);
1431 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1432 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1433 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1437 mark_irreducible_loops ();
1444 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1445 && !bitmap_bit_p (irreds
, bb
->index
))
1447 error ("basic block %d should be marked irreducible", bb
->index
);
1450 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1451 && bitmap_bit_p (irreds
, bb
->index
))
1453 error ("basic block %d should not be marked irreducible", bb
->index
);
1456 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1458 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1459 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1461 error ("edge from %d to %d should be marked irreducible",
1462 e
->src
->index
, e
->dest
->index
);
1465 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1466 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1468 error ("edge from %d to %d should not be marked irreducible",
1469 e
->src
->index
, e
->dest
->index
);
1472 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1478 /* Check the recorded loop exits. */
1479 FOR_EACH_LOOP (li
, loop
, 0)
1481 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1483 error ("corrupted head of the exits list of loop %d",
1489 /* Check that the list forms a cycle, and all elements except
1490 for the head are nonnull. */
1491 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1492 exit
->e
&& exit
!= mexit
;
1496 mexit
= mexit
->next
;
1499 if (exit
!= loop
->exits
)
1501 error ("corrupted exits list of loop %d", loop
->num
);
1506 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1508 if (loop
->exits
->next
!= loop
->exits
)
1510 error ("nonempty exits list of loop %d, but exits are not recorded",
1517 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1519 unsigned n_exits
= 0, eloops
;
1521 memset (sizes
, 0, sizeof (unsigned) * num
);
1525 if (bb
->loop_father
== current_loops
->tree_root
)
1527 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1529 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1533 exit
= get_exit_descriptions (e
);
1536 error ("exit %d->%d not recorded",
1537 e
->src
->index
, e
->dest
->index
);
1541 for (; exit
; exit
= exit
->next_e
)
1544 for (loop
= bb
->loop_father
;
1545 loop
!= e
->dest
->loop_father
;
1546 loop
= loop_outer (loop
))
1554 error ("wrong list of exited loops for edge %d->%d",
1555 e
->src
->index
, e
->dest
->index
);
1561 if (n_exits
!= htab_elements (current_loops
->exits
))
1563 error ("too many loop exits recorded");
1567 FOR_EACH_LOOP (li
, loop
, 0)
1570 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1572 if (eloops
!= sizes
[loop
->num
])
1574 error ("%d exits recorded for loop %d (having %d exits)",
1575 eloops
, loop
->num
, sizes
[loop
->num
]);
1583 sbitmap_free (visited
);
1586 free_dominance_info (CDI_DOMINATORS
);
1589 /* Returns latch edge of LOOP. */
1591 loop_latch_edge (const struct loop
*loop
)
1593 return find_edge (loop
->latch
, loop
->header
);
1596 /* Returns preheader edge of LOOP. */
1598 loop_preheader_edge (const struct loop
*loop
)
1603 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1605 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1606 if (e
->src
!= loop
->latch
)
1612 /* Returns true if E is an exit of LOOP. */
1615 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1617 return (flow_bb_inside_loop_p (loop
, e
->src
)
1618 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1621 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1622 or more than one exit. If loops do not have the exits recorded, NULL
1623 is returned always. */
1626 single_exit (const struct loop
*loop
)
1628 struct loop_exit
*exit
= loop
->exits
->next
;
1630 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1633 if (exit
->e
&& exit
->next
== loop
->exits
)
1639 /* Returns true when BB has an incoming edge exiting LOOP. */
1642 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1647 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1648 if (loop_exit_edge_p (loop
, e
))
1654 /* Returns true when BB has an outgoing edge exiting LOOP. */
1657 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1662 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1663 if (loop_exit_edge_p (loop
, e
))
1669 /* Return location corresponding to the loop control condition if possible. */
1672 get_loop_location (struct loop
*loop
)
1675 struct niter_desc
*desc
= NULL
;
1678 /* For a for or while loop, we would like to return the location
1679 of the for or while statement, if possible. To do this, look
1680 for the branch guarding the loop back-edge. */
1682 /* If this is a simple loop with an in_edge, then the loop control
1683 branch is typically at the end of its source. */
1684 desc
= get_simple_loop_desc (loop
);
1687 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1689 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1690 return INSN_LOCATION (insn
);
1693 /* If loop has a single exit, then the loop control branch
1694 must be at the end of its source. */
1695 if ((exit
= single_exit (loop
)))
1697 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1699 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1700 return INSN_LOCATION (insn
);
1703 /* Next check the latch, to see if it is non-empty. */
1704 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1706 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1707 return INSN_LOCATION (insn
);
1709 /* Finally, if none of the above identifies the loop control branch,
1710 return the first location in the loop header. */
1711 FOR_BB_INSNS (loop
->header
, insn
)
1713 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1714 return INSN_LOCATION (insn
);
1716 /* If all else fails, simply return the current function location. */
1717 return DECL_SOURCE_LOCATION (current_function_decl
);