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
, bb
->succ
, ix
)
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 if (depth
> (unsigned) loop
->depth
)
114 if (depth
== (unsigned) loop
->depth
)
117 return loop
->pred
[depth
];
120 /* Dump the loop information specified by LOOP to the stream FILE
121 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
124 flow_loop_dump (const struct loop
*loop
, FILE *file
,
125 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
131 if (! loop
|| ! loop
->header
)
134 fprintf (file
, ";;\n;; Loop %d:%s\n", loop
->num
,
135 loop
->invalid
? " invalid" : "");
137 fprintf (file
, ";; header %d, latch %d, pre-header %d\n",
138 loop
->header
->index
, loop
->latch
->index
,
139 loop
->pre_header
? loop
->pre_header
->index
: -1);
140 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
141 loop
->depth
, loop
->level
,
142 (long) (loop
->outer
? loop
->outer
->num
: -1));
144 if (loop
->pre_header_edges
)
145 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
146 loop
->num_pre_header_edges
, file
);
148 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
149 loop
->num_entries
, file
);
150 fprintf (file
, ";; nodes:");
151 bbs
= get_loop_body (loop
);
152 for (i
= 0; i
< loop
->num_nodes
; i
++)
153 fprintf (file
, " %d", bbs
[i
]->index
);
155 fprintf (file
, "\n");
156 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
157 loop
->num_exits
, file
);
160 loop_dump_aux (loop
, file
, verbose
);
163 /* Dump the loop information specified by LOOPS to the stream FILE,
164 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
167 flow_loops_dump (const struct loops
*loops
, FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
172 num_loops
= loops
->num
;
173 if (! num_loops
|| ! file
)
176 fprintf (file
, ";; %d loops found, %d levels\n",
177 num_loops
, loops
->levels
);
179 for (i
= 0; i
< num_loops
; i
++)
181 struct loop
*loop
= loops
->parray
[i
];
186 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
190 flow_loops_cfg_dump (loops
, file
);
193 /* Free data allocated for LOOP. */
195 flow_loop_free (struct loop
*loop
)
197 if (loop
->pre_header_edges
)
198 free (loop
->pre_header_edges
);
199 if (loop
->entry_edges
)
200 free (loop
->entry_edges
);
201 if (loop
->exit_edges
)
202 free (loop
->exit_edges
);
208 /* Free all the memory allocated for LOOPS. */
211 flow_loops_free (struct loops
*loops
)
220 /* Free the loop descriptors. */
221 for (i
= 0; i
< loops
->num
; i
++)
223 struct loop
*loop
= loops
->parray
[i
];
228 flow_loop_free (loop
);
231 free (loops
->parray
);
232 loops
->parray
= NULL
;
234 if (loops
->cfg
.dfs_order
)
235 free (loops
->cfg
.dfs_order
);
236 if (loops
->cfg
.rc_order
)
237 free (loops
->cfg
.rc_order
);
242 /* Find the entry edges into the LOOP. */
245 flow_loop_entry_edges_find (struct loop
*loop
)
252 FOR_EACH_EDGE (e
, loop
->header
->pred
, ix
)
254 if (flow_loop_outside_edge_p (loop
, e
))
261 loop
->entry_edges
= xmalloc (num_entries
* sizeof (edge
*));
264 FOR_EACH_EDGE (e
, loop
->header
->pred
, ix
)
266 if (flow_loop_outside_edge_p (loop
, e
))
267 loop
->entry_edges
[num_entries
++] = e
;
270 loop
->num_entries
= num_entries
;
273 /* Find the exit edges from the LOOP. */
276 flow_loop_exit_edges_find (struct loop
*loop
)
279 basic_block node
, *bbs
;
280 unsigned num_exits
, i
, ix
;
282 loop
->exit_edges
= NULL
;
285 /* Check all nodes within the loop to see if there are any
286 successors not in the loop. Note that a node may have multiple
289 bbs
= get_loop_body (loop
);
290 for (i
= 0; i
< loop
->num_nodes
; i
++)
294 FOR_EACH_EDGE (e
, node
->succ
, ix
)
296 basic_block dest
= e
->dest
;
298 if (!flow_bb_inside_loop_p (loop
, dest
))
309 loop
->exit_edges
= xmalloc (num_exits
* sizeof (edge
*));
311 /* Store all exiting edges into an array. */
313 for (i
= 0; i
< loop
->num_nodes
; i
++)
316 FOR_EACH_EDGE (e
, node
->succ
, ix
)
318 basic_block dest
= e
->dest
;
320 if (!flow_bb_inside_loop_p (loop
, dest
))
321 loop
->exit_edges
[num_exits
++] = e
;
325 loop
->num_exits
= num_exits
;
328 /* Find the nodes contained within the LOOP with header HEADER.
329 Return the number of nodes within the loop. */
332 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
338 header
->loop_father
= loop
;
339 header
->loop_depth
= loop
->depth
;
341 if (loop
->latch
->loop_father
!= loop
)
343 stack
= xmalloc (n_basic_blocks
* sizeof (basic_block
));
346 stack
[sp
++] = loop
->latch
;
347 loop
->latch
->loop_father
= loop
;
348 loop
->latch
->loop_depth
= loop
->depth
;
358 FOR_EACH_EDGE (e
, node
->pred
, ix
)
360 basic_block ancestor
= e
->src
;
362 if (ancestor
!= ENTRY_BLOCK_PTR
363 && ancestor
->loop_father
!= loop
)
365 ancestor
->loop_father
= loop
;
366 ancestor
->loop_depth
= loop
->depth
;
368 stack
[sp
++] = ancestor
;
377 /* Find the root node of the loop pre-header extended basic block and
378 the edges along the trace from the root node to the loop header. */
381 flow_loop_pre_header_scan (struct loop
*loop
)
387 loop
->num_pre_header_edges
= 0;
388 if (loop
->num_entries
!= 1)
391 ebb
= loop
->entry_edges
[0]->src
;
392 if (ebb
== ENTRY_BLOCK_PTR
)
395 /* Count number of edges along trace from loop header to
396 root of pre-header extended basic block. Usually this is
397 only one or two edges. */
399 EDGE_0 (ebb
->pred
)->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (ebb
->pred
) == 1;
401 ebb
= EDGE_0 (ebb
->pred
)->src
;
403 loop
->pre_header_edges
= xmalloc (num
* sizeof (edge
));
404 loop
->num_pre_header_edges
= num
;
406 /* Store edges in order that they are followed. The source of the first edge
407 is the root node of the pre-header extended basic block and the
408 destination of the last last edge is the loop header. */
409 for (e
= loop
->entry_edges
[0]; num
; e
= e
->src
->pred
)
410 loop
->pre_header_edges
[--num
] = e
;
413 /* Return the block for the pre-header of the loop with header
414 HEADER. Return NULL if there is no pre-header. */
417 flow_loop_pre_header_find (basic_block header
)
419 basic_block pre_header
;
423 /* If block p is a predecessor of the header and is the only block
424 that the header does not dominate, then it is the pre-header. */
426 FOR_EACH_EDGE (e
, header
->pred
, ix
)
428 basic_block node
= e
->src
;
430 if (node
!= ENTRY_BLOCK_PTR
431 && ! dominated_by_p (CDI_DOMINATORS
, node
, header
))
433 if (pre_header
== NULL
)
437 /* There are multiple edges into the header from outside
438 the loop so there is no pre-header block. */
449 establish_preds (struct loop
*loop
)
451 struct loop
*ploop
, *father
= loop
->outer
;
453 loop
->depth
= father
->depth
+ 1;
456 loop
->pred
= xmalloc (sizeof (struct loop
*) * loop
->depth
);
457 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
458 loop
->pred
[father
->depth
] = father
;
460 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
461 establish_preds (ploop
);
464 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
465 added loop. If LOOP has some children, take care of that their
466 pred field will be initialized correctly. */
469 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
471 loop
->next
= father
->inner
;
472 father
->inner
= loop
;
473 loop
->outer
= father
;
475 establish_preds (loop
);
478 /* Remove LOOP from the loop hierarchy tree. */
481 flow_loop_tree_node_remove (struct loop
*loop
)
483 struct loop
*prev
, *father
;
485 father
= loop
->outer
;
488 /* Remove loop from the list of sons. */
489 if (father
->inner
== loop
)
490 father
->inner
= loop
->next
;
493 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
494 prev
->next
= loop
->next
;
502 /* Helper function to compute loop nesting depth and enclosed loop level
503 for the natural loop specified by LOOP. Returns the loop level. */
506 flow_loop_level_compute (struct loop
*loop
)
514 /* Traverse loop tree assigning depth and computing level as the
515 maximum level of all the inner loops of this loop. The loop
516 level is equivalent to the height of the loop in the loop tree
517 and corresponds to the number of enclosed loop levels (including
519 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
521 int ilevel
= flow_loop_level_compute (inner
) + 1;
531 /* Compute the loop nesting depth and enclosed loop level for the loop
532 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
536 flow_loops_level_compute (struct loops
*loops
)
538 return flow_loop_level_compute (loops
->tree_root
);
541 /* Scan a single natural loop specified by LOOP collecting information
542 about it specified by FLAGS. */
545 flow_loop_scan (struct loop
*loop
, int flags
)
547 if (flags
& LOOP_ENTRY_EDGES
)
549 /* Find edges which enter the loop header.
550 Note that the entry edges should only
551 enter the header of a natural loop. */
552 flow_loop_entry_edges_find (loop
);
555 if (flags
& LOOP_EXIT_EDGES
)
557 /* Find edges which exit the loop. */
558 flow_loop_exit_edges_find (loop
);
561 if (flags
& LOOP_PRE_HEADER
)
563 /* Look to see if the loop has a pre-header node. */
564 loop
->pre_header
= flow_loop_pre_header_find (loop
->header
);
566 /* Find the blocks within the extended basic block of
567 the loop pre-header. */
568 flow_loop_pre_header_scan (loop
);
574 /* A callback to update latch and header info for basic block JUMP created
575 by redirecting an edge. */
578 update_latch_info (basic_block jump
)
580 alloc_aux_for_block (jump
, sizeof (int));
581 HEADER_BLOCK (jump
) = 0;
582 alloc_aux_for_edge (EDGE_0 (jump
->pred
), sizeof (int));
583 LATCH_EDGE (EDGE_0 (jump
->pred
)) = 0;
586 /* A callback for make_forwarder block, to redirect all edges except for
587 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
588 whether to redirect it. */
590 static edge mfb_kj_edge
;
592 mfb_keep_just (edge e
)
594 return e
!= mfb_kj_edge
;
597 /* A callback for make_forwarder block, to redirect the latch edges into an
598 entry part. E is the edge for that we should decide whether to redirect
602 mfb_keep_nonlatch (edge e
)
604 return LATCH_EDGE (e
);
607 /* Takes care of merging natural loops with shared headers. */
610 canonicalize_loop_headers (void)
616 /* Compute the dominators. */
617 calculate_dominance_info (CDI_DOMINATORS
);
619 alloc_aux_for_blocks (sizeof (int));
620 alloc_aux_for_edges (sizeof (int));
622 /* Split blocks so that each loop has only single latch. */
626 int have_abnormal_edge
= 0;
628 FOR_EACH_EDGE (e
, header
->pred
, ix
)
630 basic_block latch
= e
->src
;
632 if (e
->flags
& EDGE_ABNORMAL
)
633 have_abnormal_edge
= 1;
635 if (latch
!= ENTRY_BLOCK_PTR
636 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
642 if (have_abnormal_edge
)
643 HEADER_BLOCK (header
) = 0;
645 HEADER_BLOCK (header
) = num_latches
;
648 free_dominance_info (CDI_DOMINATORS
);
650 if (HEADER_BLOCK (EDGE_0 (ENTRY_BLOCK_PTR
->succ
)->dest
))
654 /* We could not redirect edges freely here. On the other hand,
655 we can simply split the edge from entry block. */
656 bb
= split_edge (EDGE_0 (ENTRY_BLOCK_PTR
->succ
));
658 alloc_aux_for_edge (EDGE_0 (bb
->succ
), sizeof (int));
659 LATCH_EDGE (EDGE_0 (bb
->succ
)) = 0;
660 alloc_aux_for_block (bb
, sizeof (int));
661 HEADER_BLOCK (bb
) = 0;
666 int max_freq
, is_heavy
;
667 edge heavy
, tmp_edge
;
669 if (HEADER_BLOCK (header
) <= 1)
672 /* Find a heavy edge. */
677 FOR_EACH_EDGE (e
, header
->pred
, ix
)
678 if (LATCH_EDGE (e
) &&
679 EDGE_FREQUENCY (e
) > max_freq
)
680 max_freq
= EDGE_FREQUENCY (e
);
682 FOR_EACH_EDGE (e
, header
->pred
, ix
)
683 if (LATCH_EDGE (e
) &&
684 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
697 /* Split out the heavy edge, and create inner loop for it. */
699 tmp_edge
= make_forwarder_block (header
, mfb_keep_just
,
701 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
702 HEADER_BLOCK (tmp_edge
->dest
) = 1;
703 alloc_aux_for_edge (tmp_edge
, sizeof (int));
704 LATCH_EDGE (tmp_edge
) = 0;
705 HEADER_BLOCK (header
)--;
708 if (HEADER_BLOCK (header
) > 1)
710 /* Create a new latch block. */
711 tmp_edge
= make_forwarder_block (header
, mfb_keep_nonlatch
,
713 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
714 HEADER_BLOCK (tmp_edge
->src
) = 0;
715 HEADER_BLOCK (tmp_edge
->dest
) = 1;
716 alloc_aux_for_edge (tmp_edge
, sizeof (int));
717 LATCH_EDGE (tmp_edge
) = 1;
721 free_aux_for_blocks ();
722 free_aux_for_edges ();
725 /* Find all the natural loops in the function and save in LOOPS structure and
726 recalculate loop_depth information in basic block structures. FLAGS
727 controls which loop information is collected. Return the number of natural
731 flow_loops_find (struct loops
*loops
, int flags
)
744 /* This function cannot be repeatedly called with different
745 flags to build up the loop information. The loop tree
746 must always be built if this function is called. */
747 if (! (flags
& LOOP_TREE
))
750 memset (loops
, 0, sizeof *loops
);
752 /* Taking care of this degenerate case makes the rest of
753 this code simpler. */
754 if (n_basic_blocks
== 0)
760 /* Join loops with shared headers. */
761 canonicalize_loop_headers ();
763 /* Compute the dominators. */
764 calculate_dominance_info (CDI_DOMINATORS
);
766 /* Count the number of loop headers. This should be the
767 same as the number of natural loops. */
768 headers
= sbitmap_alloc (last_basic_block
);
769 sbitmap_zero (headers
);
774 int more_latches
= 0;
776 header
->loop_depth
= 0;
778 /* If we have an abnormal predecessor, do not consider the
779 loop (not worth the problems). */
780 FOR_EACH_EDGE (e
, header
->pred
, ix
)
781 if (e
->flags
& EDGE_ABNORMAL
)
786 FOR_EACH_EDGE (e
, header
->pred
, ix
)
788 basic_block latch
= e
->src
;
790 if (e
->flags
& EDGE_ABNORMAL
)
793 /* Look for back edges where a predecessor is dominated
794 by this block. A natural loop has a single entry
795 node (header) that dominates all the nodes in the
796 loop. It also has single back edge to the header
797 from a latch node. */
798 if (latch
!= ENTRY_BLOCK_PTR
799 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
801 /* Shared headers should be eliminated by now. */
805 SET_BIT (headers
, header
->index
);
811 /* Allocate loop structures. */
812 loops
->parray
= xcalloc (num_loops
+ 1, sizeof (struct loop
*));
814 /* Dummy loop containing whole function. */
815 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
816 loops
->parray
[0]->next
= NULL
;
817 loops
->parray
[0]->inner
= NULL
;
818 loops
->parray
[0]->outer
= NULL
;
819 loops
->parray
[0]->depth
= 0;
820 loops
->parray
[0]->pred
= NULL
;
821 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
822 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
823 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
824 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
825 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
827 loops
->tree_root
= loops
->parray
[0];
829 /* Find and record information about all the natural loops
833 bb
->loop_father
= loops
->tree_root
;
837 /* Compute depth first search order of the CFG so that outer
838 natural loops will be found before inner natural loops. */
839 dfs_order
= xmalloc (n_basic_blocks
* sizeof (int));
840 rc_order
= xmalloc (n_basic_blocks
* sizeof (int));
841 flow_depth_first_order_compute (dfs_order
, rc_order
);
843 /* Save CFG derived information to avoid recomputing it. */
844 loops
->cfg
.dfs_order
= dfs_order
;
845 loops
->cfg
.rc_order
= rc_order
;
849 for (b
= 0; b
< n_basic_blocks
; b
++)
853 /* Search the nodes of the CFG in reverse completion order
854 so that we can find outer loops first. */
855 if (!TEST_BIT (headers
, rc_order
[b
]))
858 header
= BASIC_BLOCK (rc_order
[b
]);
860 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
862 loop
->header
= header
;
863 loop
->num
= num_loops
;
866 /* Look for the latch for this header block. */
867 FOR_EACH_EDGE (e
, header
->pred
, ix
)
869 basic_block latch
= e
->src
;
871 if (latch
!= ENTRY_BLOCK_PTR
872 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
879 flow_loop_tree_node_add (header
->loop_father
, loop
);
880 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
883 /* Assign the loop nesting depth and enclosed loop level for each
885 loops
->levels
= flow_loops_level_compute (loops
);
887 /* Scan the loops. */
888 for (i
= 1; i
< num_loops
; i
++)
889 flow_loop_scan (loops
->parray
[i
], flags
);
891 loops
->num
= num_loops
;
895 free_dominance_info (CDI_DOMINATORS
);
898 sbitmap_free (headers
);
901 #ifdef ENABLE_CHECKING
903 verify_loop_structure (loops
);
909 /* Update the information regarding the loops in the CFG
910 specified by LOOPS. */
913 flow_loops_update (struct loops
*loops
, int flags
)
915 /* One day we may want to update the current loop data. For now
916 throw away the old stuff and rebuild what we need. */
918 flow_loops_free (loops
);
920 return flow_loops_find (loops
, flags
);
923 /* Return nonzero if basic block BB belongs to LOOP. */
925 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
927 struct loop
*source_loop
;
929 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
932 source_loop
= bb
->loop_father
;
933 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
936 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
939 flow_loop_outside_edge_p (const struct loop
*loop
, edge e
)
941 if (e
->dest
!= loop
->header
)
943 return !flow_bb_inside_loop_p (loop
, e
->src
);
946 /* Enumeration predicate for get_loop_body. */
948 glb_enum_p (basic_block bb
, void *glb_header
)
950 return bb
!= (basic_block
) glb_header
;
953 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
954 order against direction of edges from latch. Specially, if
955 header != latch, latch is the 1-st block. */
957 get_loop_body (const struct loop
*loop
)
959 basic_block
*tovisit
, bb
;
962 if (!loop
->num_nodes
)
965 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
966 tovisit
[tv
++] = loop
->header
;
968 if (loop
->latch
== EXIT_BLOCK_PTR
)
970 /* There may be blocks unreachable from EXIT_BLOCK. */
971 if (loop
->num_nodes
!= (unsigned) n_basic_blocks
+ 2)
975 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
977 else if (loop
->latch
!= loop
->header
)
979 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
980 tovisit
+ 1, loop
->num_nodes
- 1,
984 if (tv
!= loop
->num_nodes
)
989 /* Fills dominance descendants inside LOOP of the basic block BB into
990 array TOVISIT from index *TV. */
993 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
994 basic_block
*tovisit
, int *tv
)
996 basic_block son
, postpone
= NULL
;
998 tovisit
[(*tv
)++] = bb
;
999 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1001 son
= next_dom_son (CDI_DOMINATORS
, son
))
1003 if (!flow_bb_inside_loop_p (loop
, son
))
1006 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
1011 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
1015 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
1018 /* Gets body of a LOOP (that must be different from the outermost loop)
1019 sorted by dominance relation. Additionally, if a basic block s dominates
1020 the latch, then only blocks dominated by s are be after it. */
1023 get_loop_body_in_dom_order (const struct loop
*loop
)
1025 basic_block
*tovisit
;
1028 if (!loop
->num_nodes
)
1031 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1033 if (loop
->latch
== EXIT_BLOCK_PTR
)
1037 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
1039 if (tv
!= (int) loop
->num_nodes
)
1045 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1047 get_loop_exit_edges (const struct loop
*loop
, unsigned int *n_edges
)
1054 if (loop
->latch
== EXIT_BLOCK_PTR
)
1057 body
= get_loop_body (loop
);
1059 for (i
= 0; i
< loop
->num_nodes
; i
++)
1060 FOR_EACH_EDGE (e
, body
[i
]->succ
, ix
)
1061 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1063 edges
= xmalloc (n
* sizeof (edge
));
1066 for (i
= 0; i
< loop
->num_nodes
; i
++)
1067 FOR_EACH_EDGE (e
, body
[i
]->succ
, ix
)
1068 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1075 /* Counts the number of conditional branches inside LOOP. */
1078 num_loop_branches (const struct loop
*loop
)
1083 if (loop
->latch
== EXIT_BLOCK_PTR
)
1086 body
= get_loop_body (loop
);
1088 for (i
= 0; i
< loop
->num_nodes
; i
++)
1089 if (EDGE_COUNT (body
[i
]->succ
) >= 2)
1096 /* Adds basic block BB to LOOP. */
1098 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1102 bb
->loop_father
= loop
;
1103 bb
->loop_depth
= loop
->depth
;
1105 for (i
= 0; i
< loop
->depth
; i
++)
1106 loop
->pred
[i
]->num_nodes
++;
1109 /* Remove basic block BB from loops. */
1111 remove_bb_from_loops (basic_block bb
)
1114 struct loop
*loop
= bb
->loop_father
;
1117 for (i
= 0; i
< loop
->depth
; i
++)
1118 loop
->pred
[i
]->num_nodes
--;
1119 bb
->loop_father
= NULL
;
1123 /* Finds nearest common ancestor in loop tree for given loops. */
1125 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1127 if (!loop_s
) return loop_d
;
1128 if (!loop_d
) return loop_s
;
1130 if (loop_s
->depth
< loop_d
->depth
)
1131 loop_d
= loop_d
->pred
[loop_s
->depth
];
1132 else if (loop_s
->depth
> loop_d
->depth
)
1133 loop_s
= loop_s
->pred
[loop_d
->depth
];
1135 while (loop_s
!= loop_d
)
1137 loop_s
= loop_s
->outer
;
1138 loop_d
= loop_d
->outer
;
1143 /* Cancels the LOOP; it must be innermost one. */
1145 cancel_loop (struct loops
*loops
, struct loop
*loop
)
1153 /* Move blocks up one level (they should be removed as soon as possible). */
1154 bbs
= get_loop_body (loop
);
1155 for (i
= 0; i
< loop
->num_nodes
; i
++)
1156 bbs
[i
]->loop_father
= loop
->outer
;
1158 /* Remove the loop from structure. */
1159 flow_loop_tree_node_remove (loop
);
1161 /* Remove loop from loops array. */
1162 loops
->parray
[loop
->num
] = NULL
;
1164 /* Free loop data. */
1165 flow_loop_free (loop
);
1168 /* Cancels LOOP and all its subloops. */
1170 cancel_loop_tree (struct loops
*loops
, struct loop
*loop
)
1173 cancel_loop_tree (loops
, loop
->inner
);
1174 cancel_loop (loops
, loop
);
1177 /* Checks that LOOPS are all right:
1178 -- sizes of loops are all right
1179 -- results of get_loop_body really belong to the loop
1180 -- loop header have just single entry edge and single latch edge
1181 -- loop latches have only single successor that is header of their loop
1182 -- irreducible loops are correctly marked
1185 verify_loop_structure (struct loops
*loops
)
1187 unsigned *sizes
, i
, j
;
1189 basic_block
*bbs
, bb
;
1196 sizes
= xcalloc (loops
->num
, sizeof (int));
1200 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1203 for (i
= 0; i
< loops
->num
; i
++)
1205 if (!loops
->parray
[i
])
1208 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1210 error ("Size of loop %d should be %d, not %d.",
1211 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1218 /* Check get_loop_body. */
1219 for (i
= 1; i
< loops
->num
; i
++)
1221 loop
= loops
->parray
[i
];
1224 bbs
= get_loop_body (loop
);
1226 for (j
= 0; j
< loop
->num_nodes
; j
++)
1227 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1229 error ("Bb %d do not belong to loop %d.",
1236 /* Check headers and latches. */
1237 for (i
= 1; i
< loops
->num
; i
++)
1239 loop
= loops
->parray
[i
];
1243 if ((loops
->state
& LOOPS_HAVE_PREHEADERS
)
1244 && EDGE_COUNT (loop
->header
->pred
) != 2)
1246 error ("Loop %d's header does not have exactly 2 entries.", i
);
1249 if (loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1251 if (EDGE_COUNT (loop
->latch
->succ
) != 1)
1253 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1256 if (EDGE_0 (loop
->latch
->succ
)->dest
!= loop
->header
)
1258 error ("Loop %d's latch does not have header as successor.", i
);
1261 if (loop
->latch
->loop_father
!= loop
)
1263 error ("Loop %d's latch does not belong directly to it.", i
);
1267 if (loop
->header
->loop_father
!= loop
)
1269 error ("Loop %d's header does not belong directly to it.", i
);
1272 if ((loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1273 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1275 error ("Loop %d's latch is marked as part of irreducible region.", i
);
1280 /* Check irreducible loops. */
1281 if (loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1283 /* Record old info. */
1284 irreds
= sbitmap_alloc (last_basic_block
);
1287 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1288 SET_BIT (irreds
, bb
->index
);
1290 RESET_BIT (irreds
, bb
->index
);
1291 FOR_EACH_EDGE (e
, bb
->succ
, ix
)
1292 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1293 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1297 mark_irreducible_loops (loops
);
1302 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1303 && !TEST_BIT (irreds
, bb
->index
))
1305 error ("Basic block %d should be marked irreducible.", bb
->index
);
1308 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1309 && TEST_BIT (irreds
, bb
->index
))
1311 error ("Basic block %d should not be marked irreducible.", bb
->index
);
1314 FOR_EACH_EDGE (e
, bb
->succ
, ix
)
1316 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1317 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1319 error ("Edge from %d to %d should be marked irreducible.",
1320 e
->src
->index
, e
->dest
->index
);
1323 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1324 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1326 error ("Edge from %d to %d should not be marked irreducible.",
1327 e
->src
->index
, e
->dest
->index
);
1330 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1340 /* Returns latch edge of LOOP. */
1342 loop_latch_edge (const struct loop
*loop
)
1347 FOR_EACH_EDGE (e
, loop
->header
->pred
, ix
)
1348 if (e
->src
== loop
->latch
)
1354 /* Returns preheader edge of LOOP. */
1356 loop_preheader_edge (const struct loop
*loop
)
1361 FOR_EACH_EDGE (e
, loop
->header
->pred
, ix
)
1362 if (e
->src
!= loop
->latch
)