1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
32 #include "tree-flow.h"
34 /* Ratio of frequencies of edges so that one of more latch edges is
35 considered to belong to inner loop with same header. */
36 #define HEAVY_EDGE_RATIO 8
38 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
39 #define LATCH_EDGE(E) (*(int *) (E)->aux)
41 static void flow_loops_cfg_dump (const struct loops
*, FILE *);
42 static void flow_loop_entry_edges_find (struct loop
*);
43 static void flow_loop_exit_edges_find (struct loop
*);
44 static int flow_loop_nodes_find (basic_block
, struct loop
*);
45 static void flow_loop_pre_header_scan (struct loop
*);
46 static basic_block
flow_loop_pre_header_find (basic_block
);
47 static int flow_loop_level_compute (struct loop
*);
48 static int flow_loops_level_compute (struct loops
*);
49 static void establish_preds (struct loop
*);
50 static void canonicalize_loop_headers (void);
51 static bool glb_enum_p (basic_block
, void *);
53 /* Dump loop related CFG information. */
56 flow_loops_cfg_dump (const struct loops
*loops
, FILE *file
)
61 if (! loops
->num
|| ! file
)
69 fprintf (file
, ";; %d succs { ", bb
->index
);
70 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
71 fprintf (file
, "%d ", succ
->dest
->index
);
72 fprintf (file
, "}\n");
75 /* Dump the DFS node order. */
76 if (loops
->cfg
.dfs_order
)
78 fputs (";; DFS order: ", file
);
79 for (i
= 0; i
< n_basic_blocks
; i
++)
80 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
85 /* Dump the reverse completion node order. */
86 if (loops
->cfg
.rc_order
)
88 fputs (";; RC order: ", file
);
89 for (i
= 0; i
< n_basic_blocks
; i
++)
90 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
96 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
99 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
101 return (loop
->depth
> outer
->depth
102 && loop
->pred
[outer
->depth
] == outer
);
105 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
106 loops within LOOP. */
109 superloop_at_depth (struct loop
*loop
, unsigned depth
)
111 gcc_assert (depth
<= (unsigned) loop
->depth
);
113 if (depth
== (unsigned) loop
->depth
)
116 return loop
->pred
[depth
];
119 /* Dump the loop information specified by LOOP to the stream FILE
120 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
123 flow_loop_dump (const struct loop
*loop
, FILE *file
,
124 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
130 if (! loop
|| ! loop
->header
)
133 fprintf (file
, ";;\n;; Loop %d:%s\n", loop
->num
,
134 loop
->invalid
? " invalid" : "");
136 fprintf (file
, ";; header %d, latch %d, pre-header %d\n",
137 loop
->header
->index
, loop
->latch
->index
,
138 loop
->pre_header
? loop
->pre_header
->index
: -1);
139 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
140 loop
->depth
, loop
->level
,
141 (long) (loop
->outer
? loop
->outer
->num
: -1));
143 if (loop
->pre_header_edges
)
144 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
145 loop
->num_pre_header_edges
, file
);
147 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
148 loop
->num_entries
, file
);
149 fprintf (file
, ";; nodes:");
150 bbs
= get_loop_body (loop
);
151 for (i
= 0; i
< loop
->num_nodes
; i
++)
152 fprintf (file
, " %d", bbs
[i
]->index
);
154 fprintf (file
, "\n");
155 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
156 loop
->num_exits
, file
);
159 loop_dump_aux (loop
, file
, verbose
);
162 /* Dump the loop information specified by LOOPS to the stream FILE,
163 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
166 flow_loops_dump (const struct loops
*loops
, FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
171 num_loops
= loops
->num
;
172 if (! num_loops
|| ! file
)
175 fprintf (file
, ";; %d loops found, %d levels\n",
176 num_loops
, loops
->levels
);
178 for (i
= 0; i
< num_loops
; i
++)
180 struct loop
*loop
= loops
->parray
[i
];
185 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
189 flow_loops_cfg_dump (loops
, file
);
192 /* Free data allocated for LOOP. */
194 flow_loop_free (struct loop
*loop
)
196 if (loop
->pre_header_edges
)
197 free (loop
->pre_header_edges
);
198 if (loop
->entry_edges
)
199 free (loop
->entry_edges
);
200 if (loop
->exit_edges
)
201 free (loop
->exit_edges
);
207 /* Free all the memory allocated for LOOPS. */
210 flow_loops_free (struct loops
*loops
)
216 gcc_assert (loops
->num
);
218 /* Free the loop descriptors. */
219 for (i
= 0; i
< loops
->num
; i
++)
221 struct loop
*loop
= loops
->parray
[i
];
226 flow_loop_free (loop
);
229 free (loops
->parray
);
230 loops
->parray
= NULL
;
232 if (loops
->cfg
.dfs_order
)
233 free (loops
->cfg
.dfs_order
);
234 if (loops
->cfg
.rc_order
)
235 free (loops
->cfg
.rc_order
);
240 /* Find the entry edges into the LOOP. */
243 flow_loop_entry_edges_find (struct loop
*loop
)
250 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
252 if (flow_loop_outside_edge_p (loop
, e
))
256 gcc_assert (num_entries
);
258 loop
->entry_edges
= xmalloc (num_entries
* sizeof (edge
*));
261 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
263 if (flow_loop_outside_edge_p (loop
, e
))
264 loop
->entry_edges
[num_entries
++] = e
;
267 loop
->num_entries
= num_entries
;
270 /* Find the exit edges from the LOOP. */
273 flow_loop_exit_edges_find (struct loop
*loop
)
276 basic_block node
, *bbs
;
277 unsigned num_exits
, i
;
279 loop
->exit_edges
= NULL
;
282 /* Check all nodes within the loop to see if there are any
283 successors not in the loop. Note that a node may have multiple
286 bbs
= get_loop_body (loop
);
287 for (i
= 0; i
< loop
->num_nodes
; i
++)
291 FOR_EACH_EDGE (e
, ei
, node
->succs
)
293 basic_block dest
= e
->dest
;
295 if (!flow_bb_inside_loop_p (loop
, dest
))
306 loop
->exit_edges
= xmalloc (num_exits
* sizeof (edge
*));
308 /* Store all exiting edges into an array. */
310 for (i
= 0; i
< loop
->num_nodes
; i
++)
314 FOR_EACH_EDGE (e
, ei
, node
->succs
)
316 basic_block dest
= e
->dest
;
318 if (!flow_bb_inside_loop_p (loop
, dest
))
320 e
->flags
|= EDGE_LOOP_EXIT
;
321 loop
->exit_edges
[num_exits
++] = e
;
326 loop
->num_exits
= num_exits
;
329 /* Find the nodes contained within the LOOP with header HEADER.
330 Return the number of nodes within the loop. */
333 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
339 header
->loop_father
= loop
;
340 header
->loop_depth
= loop
->depth
;
342 if (loop
->latch
->loop_father
!= loop
)
344 stack
= xmalloc (n_basic_blocks
* sizeof (basic_block
));
347 stack
[sp
++] = loop
->latch
;
348 loop
->latch
->loop_father
= loop
;
349 loop
->latch
->loop_depth
= loop
->depth
;
359 FOR_EACH_EDGE (e
, ei
, node
->preds
)
361 basic_block ancestor
= e
->src
;
363 if (ancestor
!= ENTRY_BLOCK_PTR
364 && ancestor
->loop_father
!= loop
)
366 ancestor
->loop_father
= loop
;
367 ancestor
->loop_depth
= loop
->depth
;
369 stack
[sp
++] = ancestor
;
378 /* For each loop in the lOOPS tree that has just a single exit
379 record the exit edge. */
382 mark_single_exit_loops (struct loops
*loops
)
389 for (i
= 1; i
< loops
->num
; i
++)
391 loop
= loops
->parray
[i
];
393 loop
->single_exit
= NULL
;
399 if (bb
->loop_father
== loops
->tree_root
)
401 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
403 if (e
->dest
== EXIT_BLOCK_PTR
)
406 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
409 for (loop
= bb
->loop_father
;
410 loop
!= e
->dest
->loop_father
;
413 /* If we have already seen an exit, mark this by the edge that
414 surely does not occur as any exit. */
415 if (loop
->single_exit
)
416 loop
->single_exit
= EDGE_SUCC (ENTRY_BLOCK_PTR
, 0);
418 loop
->single_exit
= e
;
423 for (i
= 1; i
< loops
->num
; i
++)
425 loop
= loops
->parray
[i
];
429 if (loop
->single_exit
== EDGE_SUCC (ENTRY_BLOCK_PTR
, 0))
430 loop
->single_exit
= NULL
;
433 loops
->state
|= LOOPS_HAVE_MARKED_SINGLE_EXITS
;
436 /* Find the root node of the loop pre-header extended basic block and
437 the edges along the trace from the root node to the loop header. */
440 flow_loop_pre_header_scan (struct loop
*loop
)
446 loop
->num_pre_header_edges
= 0;
447 if (loop
->num_entries
!= 1)
450 ebb
= loop
->entry_edges
[0]->src
;
451 if (ebb
== ENTRY_BLOCK_PTR
)
454 /* Count number of edges along trace from loop header to
455 root of pre-header extended basic block. Usually this is
456 only one or two edges. */
458 EDGE_PRED (ebb
, 0)->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (ebb
->preds
) == 1;
460 ebb
= EDGE_PRED (ebb
, 0)->src
;
462 loop
->pre_header_edges
= xmalloc (num
* sizeof (edge
));
463 loop
->num_pre_header_edges
= num
;
465 /* Store edges in order that they are followed. The source of the first edge
466 is the root node of the pre-header extended basic block and the
467 destination of the last last edge is the loop header. */
468 for (e
= loop
->entry_edges
[0]; num
; e
= EDGE_PRED (e
->src
, 0))
469 loop
->pre_header_edges
[--num
] = e
;
472 /* Return the block for the pre-header of the loop with header
473 HEADER. Return NULL if there is no pre-header. */
476 flow_loop_pre_header_find (basic_block header
)
478 basic_block pre_header
;
482 /* If block p is a predecessor of the header and is the only block
483 that the header does not dominate, then it is the pre-header. */
485 FOR_EACH_EDGE (e
, ei
, header
->preds
)
487 basic_block node
= e
->src
;
489 if (node
!= ENTRY_BLOCK_PTR
490 && ! dominated_by_p (CDI_DOMINATORS
, node
, header
))
492 if (pre_header
== NULL
)
496 /* There are multiple edges into the header from outside
497 the loop so there is no pre-header block. */
508 establish_preds (struct loop
*loop
)
510 struct loop
*ploop
, *father
= loop
->outer
;
512 loop
->depth
= father
->depth
+ 1;
515 loop
->pred
= xmalloc (sizeof (struct loop
*) * loop
->depth
);
516 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
517 loop
->pred
[father
->depth
] = father
;
519 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
520 establish_preds (ploop
);
523 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
524 added loop. If LOOP has some children, take care of that their
525 pred field will be initialized correctly. */
528 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
530 loop
->next
= father
->inner
;
531 father
->inner
= loop
;
532 loop
->outer
= father
;
534 establish_preds (loop
);
537 /* Remove LOOP from the loop hierarchy tree. */
540 flow_loop_tree_node_remove (struct loop
*loop
)
542 struct loop
*prev
, *father
;
544 father
= loop
->outer
;
547 /* Remove loop from the list of sons. */
548 if (father
->inner
== loop
)
549 father
->inner
= loop
->next
;
552 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
553 prev
->next
= loop
->next
;
561 /* Helper function to compute loop nesting depth and enclosed loop level
562 for the natural loop specified by LOOP. Returns the loop level. */
565 flow_loop_level_compute (struct loop
*loop
)
573 /* Traverse loop tree assigning depth and computing level as the
574 maximum level of all the inner loops of this loop. The loop
575 level is equivalent to the height of the loop in the loop tree
576 and corresponds to the number of enclosed loop levels (including
578 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
580 int ilevel
= flow_loop_level_compute (inner
) + 1;
590 /* Compute the loop nesting depth and enclosed loop level for the loop
591 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
595 flow_loops_level_compute (struct loops
*loops
)
597 return flow_loop_level_compute (loops
->tree_root
);
600 /* Scan a single natural loop specified by LOOP collecting information
601 about it specified by FLAGS. */
604 flow_loop_scan (struct loop
*loop
, int flags
)
606 if (flags
& LOOP_ENTRY_EDGES
)
608 /* Find edges which enter the loop header.
609 Note that the entry edges should only
610 enter the header of a natural loop. */
611 flow_loop_entry_edges_find (loop
);
614 if (flags
& LOOP_EXIT_EDGES
)
616 /* Find edges which exit the loop. */
617 flow_loop_exit_edges_find (loop
);
620 if (flags
& LOOP_PRE_HEADER
)
622 /* Look to see if the loop has a pre-header node. */
623 loop
->pre_header
= flow_loop_pre_header_find (loop
->header
);
625 /* Find the blocks within the extended basic block of
626 the loop pre-header. */
627 flow_loop_pre_header_scan (loop
);
633 /* A callback to update latch and header info for basic block JUMP created
634 by redirecting an edge. */
637 update_latch_info (basic_block jump
)
639 alloc_aux_for_block (jump
, sizeof (int));
640 HEADER_BLOCK (jump
) = 0;
641 alloc_aux_for_edge (EDGE_PRED (jump
, 0), sizeof (int));
642 LATCH_EDGE (EDGE_PRED (jump
, 0)) = 0;
643 set_immediate_dominator (CDI_DOMINATORS
, jump
, EDGE_PRED (jump
, 0)->src
);
646 /* A callback for make_forwarder block, to redirect all edges except for
647 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
648 whether to redirect it. */
650 static edge mfb_kj_edge
;
652 mfb_keep_just (edge e
)
654 return e
!= mfb_kj_edge
;
657 /* A callback for make_forwarder block, to redirect the latch edges into an
658 entry part. E is the edge for that we should decide whether to redirect
662 mfb_keep_nonlatch (edge e
)
664 return LATCH_EDGE (e
);
667 /* Takes care of merging natural loops with shared headers. */
670 canonicalize_loop_headers (void)
675 alloc_aux_for_blocks (sizeof (int));
676 alloc_aux_for_edges (sizeof (int));
678 /* Split blocks so that each loop has only single latch. */
683 int have_abnormal_edge
= 0;
685 FOR_EACH_EDGE (e
, ei
, header
->preds
)
687 basic_block latch
= e
->src
;
689 if (e
->flags
& EDGE_ABNORMAL
)
690 have_abnormal_edge
= 1;
692 if (latch
!= ENTRY_BLOCK_PTR
693 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
699 if (have_abnormal_edge
)
700 HEADER_BLOCK (header
) = 0;
702 HEADER_BLOCK (header
) = num_latches
;
705 if (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
))
709 /* We could not redirect edges freely here. On the other hand,
710 we can simply split the edge from entry block. */
711 bb
= split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0));
713 alloc_aux_for_edge (EDGE_SUCC (bb
, 0), sizeof (int));
714 LATCH_EDGE (EDGE_SUCC (bb
, 0)) = 0;
715 alloc_aux_for_block (bb
, sizeof (int));
716 HEADER_BLOCK (bb
) = 0;
721 int max_freq
, is_heavy
;
722 edge heavy
, tmp_edge
;
725 if (HEADER_BLOCK (header
) <= 1)
728 /* Find a heavy edge. */
732 FOR_EACH_EDGE (e
, ei
, header
->preds
)
733 if (LATCH_EDGE (e
) &&
734 EDGE_FREQUENCY (e
) > max_freq
)
735 max_freq
= EDGE_FREQUENCY (e
);
736 FOR_EACH_EDGE (e
, ei
, header
->preds
)
737 if (LATCH_EDGE (e
) &&
738 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
751 /* Split out the heavy edge, and create inner loop for it. */
753 tmp_edge
= make_forwarder_block (header
, mfb_keep_just
,
755 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
756 HEADER_BLOCK (tmp_edge
->dest
) = 1;
757 alloc_aux_for_edge (tmp_edge
, sizeof (int));
758 LATCH_EDGE (tmp_edge
) = 0;
759 HEADER_BLOCK (header
)--;
762 if (HEADER_BLOCK (header
) > 1)
764 /* Create a new latch block. */
765 tmp_edge
= make_forwarder_block (header
, mfb_keep_nonlatch
,
767 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
768 HEADER_BLOCK (tmp_edge
->src
) = 0;
769 HEADER_BLOCK (tmp_edge
->dest
) = 1;
770 alloc_aux_for_edge (tmp_edge
, sizeof (int));
771 LATCH_EDGE (tmp_edge
) = 1;
775 free_aux_for_blocks ();
776 free_aux_for_edges ();
778 #ifdef ENABLE_CHECKING
779 verify_dominators (CDI_DOMINATORS
);
783 /* Initialize all the parallel_p fields of the loops structure to true. */
786 initialize_loops_parallel_p (struct loops
*loops
)
790 for (i
= 0; i
< loops
->num
; i
++)
792 struct loop
*loop
= loops
->parray
[i
];
793 loop
->parallel_p
= true;
797 /* Find all the natural loops in the function and save in LOOPS structure and
798 recalculate loop_depth information in basic block structures. FLAGS
799 controls which loop information is collected. Return the number of natural
803 flow_loops_find (struct loops
*loops
, int flags
)
815 /* This function cannot be repeatedly called with different
816 flags to build up the loop information. The loop tree
817 must always be built if this function is called. */
818 gcc_assert (flags
& LOOP_TREE
);
820 memset (loops
, 0, sizeof *loops
);
822 /* Taking care of this degenerate case makes the rest of
823 this code simpler. */
824 if (n_basic_blocks
== 0)
830 /* Ensure that the dominators are computed. */
831 calculate_dominance_info (CDI_DOMINATORS
);
833 /* Join loops with shared headers. */
834 canonicalize_loop_headers ();
836 /* Count the number of loop headers. This should be the
837 same as the number of natural loops. */
838 headers
= sbitmap_alloc (last_basic_block
);
839 sbitmap_zero (headers
);
845 int more_latches
= 0;
847 header
->loop_depth
= 0;
849 /* If we have an abnormal predecessor, do not consider the
850 loop (not worth the problems). */
851 FOR_EACH_EDGE (e
, ei
, header
->preds
)
852 if (e
->flags
& EDGE_ABNORMAL
)
857 FOR_EACH_EDGE (e
, ei
, header
->preds
)
859 basic_block latch
= e
->src
;
861 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
863 /* Look for back edges where a predecessor is dominated
864 by this block. A natural loop has a single entry
865 node (header) that dominates all the nodes in the
866 loop. It also has single back edge to the header
867 from a latch node. */
868 if (latch
!= ENTRY_BLOCK_PTR
869 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
871 /* Shared headers should be eliminated by now. */
872 gcc_assert (!more_latches
);
874 SET_BIT (headers
, header
->index
);
880 /* Allocate loop structures. */
881 loops
->parray
= xcalloc (num_loops
+ 1, sizeof (struct loop
*));
883 /* Dummy loop containing whole function. */
884 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
885 loops
->parray
[0]->next
= NULL
;
886 loops
->parray
[0]->inner
= NULL
;
887 loops
->parray
[0]->outer
= NULL
;
888 loops
->parray
[0]->depth
= 0;
889 loops
->parray
[0]->pred
= NULL
;
890 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
891 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
892 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
893 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
894 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
896 loops
->tree_root
= loops
->parray
[0];
898 /* Find and record information about all the natural loops
902 bb
->loop_father
= loops
->tree_root
;
906 /* Compute depth first search order of the CFG so that outer
907 natural loops will be found before inner natural loops. */
908 dfs_order
= xmalloc (n_basic_blocks
* sizeof (int));
909 rc_order
= xmalloc (n_basic_blocks
* sizeof (int));
910 flow_depth_first_order_compute (dfs_order
, rc_order
);
912 /* Save CFG derived information to avoid recomputing it. */
913 loops
->cfg
.dfs_order
= dfs_order
;
914 loops
->cfg
.rc_order
= rc_order
;
918 for (b
= 0; b
< n_basic_blocks
; b
++)
923 /* Search the nodes of the CFG in reverse completion order
924 so that we can find outer loops first. */
925 if (!TEST_BIT (headers
, rc_order
[b
]))
928 header
= BASIC_BLOCK (rc_order
[b
]);
930 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
932 loop
->header
= header
;
933 loop
->num
= num_loops
;
936 /* Look for the latch for this header block. */
937 FOR_EACH_EDGE (e
, ei
, header
->preds
)
939 basic_block latch
= e
->src
;
941 if (latch
!= ENTRY_BLOCK_PTR
942 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
949 flow_loop_tree_node_add (header
->loop_father
, loop
);
950 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
953 /* Assign the loop nesting depth and enclosed loop level for each
955 loops
->levels
= flow_loops_level_compute (loops
);
957 /* Scan the loops. */
958 for (i
= 1; i
< num_loops
; i
++)
959 flow_loop_scan (loops
->parray
[i
], flags
);
961 loops
->num
= num_loops
;
962 initialize_loops_parallel_p (loops
);
965 sbitmap_free (headers
);
968 #ifdef ENABLE_CHECKING
970 verify_loop_structure (loops
);
976 /* Return nonzero if basic block BB belongs to LOOP. */
978 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
980 struct loop
*source_loop
;
982 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
985 source_loop
= bb
->loop_father
;
986 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
989 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
992 flow_loop_outside_edge_p (const struct loop
*loop
, edge e
)
994 gcc_assert (e
->dest
== loop
->header
);
995 return !flow_bb_inside_loop_p (loop
, e
->src
);
998 /* Enumeration predicate for get_loop_body. */
1000 glb_enum_p (basic_block bb
, void *glb_header
)
1002 return bb
!= (basic_block
) glb_header
;
1005 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
1006 order against direction of edges from latch. Specially, if
1007 header != latch, latch is the 1-st block. */
1009 get_loop_body (const struct loop
*loop
)
1011 basic_block
*tovisit
, bb
;
1014 gcc_assert (loop
->num_nodes
);
1016 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1017 tovisit
[tv
++] = loop
->header
;
1019 if (loop
->latch
== EXIT_BLOCK_PTR
)
1021 /* There may be blocks unreachable from EXIT_BLOCK. */
1022 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
+ 2);
1025 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
1027 else if (loop
->latch
!= loop
->header
)
1029 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
1030 tovisit
+ 1, loop
->num_nodes
- 1,
1034 gcc_assert (tv
== loop
->num_nodes
);
1038 /* Fills dominance descendants inside LOOP of the basic block BB into
1039 array TOVISIT from index *TV. */
1042 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
1043 basic_block
*tovisit
, int *tv
)
1045 basic_block son
, postpone
= NULL
;
1047 tovisit
[(*tv
)++] = bb
;
1048 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1050 son
= next_dom_son (CDI_DOMINATORS
, son
))
1052 if (!flow_bb_inside_loop_p (loop
, son
))
1055 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
1060 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
1064 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
1067 /* Gets body of a LOOP (that must be different from the outermost loop)
1068 sorted by dominance relation. Additionally, if a basic block s dominates
1069 the latch, then only blocks dominated by s are be after it. */
1072 get_loop_body_in_dom_order (const struct loop
*loop
)
1074 basic_block
*tovisit
;
1077 gcc_assert (loop
->num_nodes
);
1079 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1081 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1084 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
1086 gcc_assert (tv
== (int) loop
->num_nodes
);
1091 /* Get body of a LOOP in breadth first sort order. */
1094 get_loop_body_in_bfs_order (const struct loop
*loop
)
1096 basic_block
*blocks
;
1100 unsigned int vc
= 1;
1102 gcc_assert (loop
->num_nodes
);
1103 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1105 blocks
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1106 visited
= BITMAP_XMALLOC ();
1109 while (i
< loop
->num_nodes
)
1114 if (!bitmap_bit_p (visited
, bb
->index
))
1116 /* This basic block is now visited */
1117 bitmap_set_bit (visited
, bb
->index
);
1121 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1123 if (flow_bb_inside_loop_p (loop
, e
->dest
))
1125 if (!bitmap_bit_p (visited
, e
->dest
->index
))
1127 bitmap_set_bit (visited
, e
->dest
->index
);
1128 blocks
[i
++] = e
->dest
;
1133 gcc_assert (i
>= vc
);
1138 BITMAP_XFREE (visited
);
1142 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1144 get_loop_exit_edges (const struct loop
*loop
, unsigned int *n_edges
)
1151 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1153 body
= get_loop_body (loop
);
1155 for (i
= 0; i
< loop
->num_nodes
; i
++)
1156 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1157 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1159 edges
= xmalloc (n
* sizeof (edge
));
1162 for (i
= 0; i
< loop
->num_nodes
; i
++)
1163 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1164 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1171 /* Counts the number of conditional branches inside LOOP. */
1174 num_loop_branches (const struct loop
*loop
)
1179 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1181 body
= get_loop_body (loop
);
1183 for (i
= 0; i
< loop
->num_nodes
; i
++)
1184 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1191 /* Adds basic block BB to LOOP. */
1193 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1197 bb
->loop_father
= loop
;
1198 bb
->loop_depth
= loop
->depth
;
1200 for (i
= 0; i
< loop
->depth
; i
++)
1201 loop
->pred
[i
]->num_nodes
++;
1204 /* Remove basic block BB from loops. */
1206 remove_bb_from_loops (basic_block bb
)
1209 struct loop
*loop
= bb
->loop_father
;
1212 for (i
= 0; i
< loop
->depth
; i
++)
1213 loop
->pred
[i
]->num_nodes
--;
1214 bb
->loop_father
= NULL
;
1218 /* Finds nearest common ancestor in loop tree for given loops. */
1220 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1222 if (!loop_s
) return loop_d
;
1223 if (!loop_d
) return loop_s
;
1225 if (loop_s
->depth
< loop_d
->depth
)
1226 loop_d
= loop_d
->pred
[loop_s
->depth
];
1227 else if (loop_s
->depth
> loop_d
->depth
)
1228 loop_s
= loop_s
->pred
[loop_d
->depth
];
1230 while (loop_s
!= loop_d
)
1232 loop_s
= loop_s
->outer
;
1233 loop_d
= loop_d
->outer
;
1238 /* Cancels the LOOP; it must be innermost one. */
1240 cancel_loop (struct loops
*loops
, struct loop
*loop
)
1245 gcc_assert (!loop
->inner
);
1247 /* Move blocks up one level (they should be removed as soon as possible). */
1248 bbs
= get_loop_body (loop
);
1249 for (i
= 0; i
< loop
->num_nodes
; i
++)
1250 bbs
[i
]->loop_father
= loop
->outer
;
1252 /* Remove the loop from structure. */
1253 flow_loop_tree_node_remove (loop
);
1255 /* Remove loop from loops array. */
1256 loops
->parray
[loop
->num
] = NULL
;
1258 /* Free loop data. */
1259 flow_loop_free (loop
);
1262 /* Cancels LOOP and all its subloops. */
1264 cancel_loop_tree (struct loops
*loops
, struct loop
*loop
)
1267 cancel_loop_tree (loops
, loop
->inner
);
1268 cancel_loop (loops
, loop
);
1271 /* Checks that LOOPS are all right:
1272 -- sizes of loops are all right
1273 -- results of get_loop_body really belong to the loop
1274 -- loop header have just single entry edge and single latch edge
1275 -- loop latches have only single successor that is header of their loop
1276 -- irreducible loops are correctly marked
1279 verify_loop_structure (struct loops
*loops
)
1281 unsigned *sizes
, i
, j
;
1283 basic_block
*bbs
, bb
;
1289 sizes
= xcalloc (loops
->num
, sizeof (int));
1293 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1296 for (i
= 0; i
< loops
->num
; i
++)
1298 if (!loops
->parray
[i
])
1301 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1303 error ("Size of loop %d should be %d, not %d.",
1304 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1309 /* Check get_loop_body. */
1310 for (i
= 1; i
< loops
->num
; i
++)
1312 loop
= loops
->parray
[i
];
1315 bbs
= get_loop_body (loop
);
1317 for (j
= 0; j
< loop
->num_nodes
; j
++)
1318 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1320 error ("Bb %d do not belong to loop %d.",
1327 /* Check headers and latches. */
1328 for (i
= 1; i
< loops
->num
; i
++)
1330 loop
= loops
->parray
[i
];
1334 if ((loops
->state
& LOOPS_HAVE_PREHEADERS
)
1335 && EDGE_COUNT (loop
->header
->preds
) != 2)
1337 error ("Loop %d's header does not have exactly 2 entries.", i
);
1340 if (loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1342 if (EDGE_COUNT (loop
->latch
->succs
) != 1)
1344 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1347 if (EDGE_SUCC (loop
->latch
, 0)->dest
!= loop
->header
)
1349 error ("Loop %d's latch does not have header as successor.", i
);
1352 if (loop
->latch
->loop_father
!= loop
)
1354 error ("Loop %d's latch does not belong directly to it.", i
);
1358 if (loop
->header
->loop_father
!= loop
)
1360 error ("Loop %d's header does not belong directly to it.", i
);
1363 if ((loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1364 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1366 error ("Loop %d's latch is marked as part of irreducible region.", i
);
1371 /* Check irreducible loops. */
1372 if (loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1374 /* Record old info. */
1375 irreds
= sbitmap_alloc (last_basic_block
);
1379 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1380 SET_BIT (irreds
, bb
->index
);
1382 RESET_BIT (irreds
, bb
->index
);
1383 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1384 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1385 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1389 mark_irreducible_loops (loops
);
1396 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1397 && !TEST_BIT (irreds
, bb
->index
))
1399 error ("Basic block %d should be marked irreducible.", bb
->index
);
1402 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1403 && TEST_BIT (irreds
, bb
->index
))
1405 error ("Basic block %d should not be marked irreducible.", bb
->index
);
1408 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1410 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1411 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1413 error ("Edge from %d to %d should be marked irreducible.",
1414 e
->src
->index
, e
->dest
->index
);
1417 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1418 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1420 error ("Edge from %d to %d should not be marked irreducible.",
1421 e
->src
->index
, e
->dest
->index
);
1424 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1430 /* Check the single_exit. */
1431 if (loops
->state
& LOOPS_HAVE_MARKED_SINGLE_EXITS
)
1433 memset (sizes
, 0, sizeof (unsigned) * loops
->num
);
1437 if (bb
->loop_father
== loops
->tree_root
)
1439 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1441 if (e
->dest
== EXIT_BLOCK_PTR
)
1444 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1447 for (loop
= bb
->loop_father
;
1448 loop
!= e
->dest
->loop_father
;
1452 if (loop
->single_exit
1453 && loop
->single_exit
!= e
)
1455 error ("Wrong single exit %d->%d recorded for loop %d.",
1456 loop
->single_exit
->src
->index
,
1457 loop
->single_exit
->dest
->index
,
1459 error ("Right exit is %d->%d.",
1460 e
->src
->index
, e
->dest
->index
);
1467 for (i
= 1; i
< loops
->num
; i
++)
1469 loop
= loops
->parray
[i
];
1474 && !loop
->single_exit
)
1476 error ("Single exit not recorded for loop %d.", loop
->num
);
1481 && loop
->single_exit
)
1483 error ("Loop %d should not have single exit (%d -> %d).",
1485 loop
->single_exit
->src
->index
,
1486 loop
->single_exit
->dest
->index
);
1497 /* Returns latch edge of LOOP. */
1499 loop_latch_edge (const struct loop
*loop
)
1504 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1505 if (e
->src
== loop
->latch
)
1511 /* Returns preheader edge of LOOP. */
1513 loop_preheader_edge (const struct loop
*loop
)
1518 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1519 if (e
->src
!= loop
->latch
)