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
)
68 fprintf (file
, ";; %d succs { ", bb
->index
);
69 FOR_EACH_EDGE (succ
, bb
->succs
)
71 fprintf (file
, "%d ", succ
->dest
->index
);
74 fprintf (file
, "}\n");
77 /* Dump the DFS node order. */
78 if (loops
->cfg
.dfs_order
)
80 fputs (";; DFS order: ", file
);
81 for (i
= 0; i
< n_basic_blocks
; i
++)
82 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
87 /* Dump the reverse completion node order. */
88 if (loops
->cfg
.rc_order
)
90 fputs (";; RC order: ", file
);
91 for (i
= 0; i
< n_basic_blocks
; i
++)
92 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
98 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
101 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
103 return (loop
->depth
> outer
->depth
104 && loop
->pred
[outer
->depth
] == outer
);
107 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
108 loops within LOOP. */
111 superloop_at_depth (struct loop
*loop
, unsigned depth
)
113 if (depth
> (unsigned) loop
->depth
)
116 if (depth
== (unsigned) loop
->depth
)
119 return loop
->pred
[depth
];
122 /* Dump the loop information specified by LOOP to the stream FILE
123 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
126 flow_loop_dump (const struct loop
*loop
, FILE *file
,
127 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
133 if (! loop
|| ! loop
->header
)
136 fprintf (file
, ";;\n;; Loop %d:%s\n", loop
->num
,
137 loop
->invalid
? " invalid" : "");
139 fprintf (file
, ";; header %d, latch %d, pre-header %d\n",
140 loop
->header
->index
, loop
->latch
->index
,
141 loop
->pre_header
? loop
->pre_header
->index
: -1);
142 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
143 loop
->depth
, loop
->level
,
144 (long) (loop
->outer
? loop
->outer
->num
: -1));
146 if (loop
->pre_header_edges
)
147 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
148 loop
->num_pre_header_edges
, file
);
150 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
151 loop
->num_entries
, file
);
152 fprintf (file
, ";; nodes:");
153 bbs
= get_loop_body (loop
);
154 for (i
= 0; i
< loop
->num_nodes
; i
++)
155 fprintf (file
, " %d", bbs
[i
]->index
);
157 fprintf (file
, "\n");
158 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
159 loop
->num_exits
, file
);
162 loop_dump_aux (loop
, file
, verbose
);
165 /* Dump the loop information specified by LOOPS to the stream FILE,
166 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
169 flow_loops_dump (const struct loops
*loops
, FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
174 num_loops
= loops
->num
;
175 if (! num_loops
|| ! file
)
178 fprintf (file
, ";; %d loops found, %d levels\n",
179 num_loops
, loops
->levels
);
181 for (i
= 0; i
< num_loops
; i
++)
183 struct loop
*loop
= loops
->parray
[i
];
188 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
192 flow_loops_cfg_dump (loops
, file
);
195 /* Free data allocated for LOOP. */
197 flow_loop_free (struct loop
*loop
)
199 if (loop
->pre_header_edges
)
200 free (loop
->pre_header_edges
);
201 if (loop
->entry_edges
)
202 free (loop
->entry_edges
);
203 if (loop
->exit_edges
)
204 free (loop
->exit_edges
);
210 /* Free all the memory allocated for LOOPS. */
213 flow_loops_free (struct loops
*loops
)
222 /* Free the loop descriptors. */
223 for (i
= 0; i
< loops
->num
; i
++)
225 struct loop
*loop
= loops
->parray
[i
];
230 flow_loop_free (loop
);
233 free (loops
->parray
);
234 loops
->parray
= NULL
;
236 if (loops
->cfg
.dfs_order
)
237 free (loops
->cfg
.dfs_order
);
238 if (loops
->cfg
.rc_order
)
239 free (loops
->cfg
.rc_order
);
244 /* Find the entry edges into the LOOP. */
247 flow_loop_entry_edges_find (struct loop
*loop
)
253 FOR_EACH_EDGE (e
, loop
->header
->preds
)
255 if (flow_loop_outside_edge_p (loop
, e
))
263 loop
->entry_edges
= xmalloc (num_entries
* sizeof (edge
*));
266 FOR_EACH_EDGE (e
, loop
->header
->preds
)
268 if (flow_loop_outside_edge_p (loop
, e
))
269 loop
->entry_edges
[num_entries
++] = e
;
273 loop
->num_entries
= num_entries
;
276 /* Find the exit edges from the LOOP. */
279 flow_loop_exit_edges_find (struct loop
*loop
)
282 basic_block node
, *bbs
;
283 unsigned num_exits
, i
;
285 loop
->exit_edges
= NULL
;
288 /* Check all nodes within the loop to see if there are any
289 successors not in the loop. Note that a node may have multiple
292 bbs
= get_loop_body (loop
);
293 for (i
= 0; i
< loop
->num_nodes
; i
++)
297 FOR_EACH_EDGE (e
, node
->succs
)
299 basic_block dest
= e
->dest
;
301 if (!flow_bb_inside_loop_p (loop
, dest
))
313 loop
->exit_edges
= xmalloc (num_exits
* sizeof (edge
*));
315 /* Store all exiting edges into an array. */
317 for (i
= 0; i
< loop
->num_nodes
; i
++)
320 FOR_EACH_EDGE (e
, node
->succs
)
322 basic_block dest
= e
->dest
;
324 if (!flow_bb_inside_loop_p (loop
, dest
))
325 loop
->exit_edges
[num_exits
++] = e
;
330 loop
->num_exits
= num_exits
;
333 /* Find the nodes contained within the LOOP with header HEADER.
334 Return the number of nodes within the loop. */
337 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
343 header
->loop_father
= loop
;
344 header
->loop_depth
= loop
->depth
;
346 if (loop
->latch
->loop_father
!= loop
)
348 stack
= xmalloc (n_basic_blocks
* sizeof (basic_block
));
351 stack
[sp
++] = loop
->latch
;
352 loop
->latch
->loop_father
= loop
;
353 loop
->latch
->loop_depth
= loop
->depth
;
362 FOR_EACH_EDGE (e
, node
->preds
)
364 basic_block ancestor
= e
->src
;
366 if (ancestor
!= ENTRY_BLOCK_PTR
367 && ancestor
->loop_father
!= loop
)
369 ancestor
->loop_father
= loop
;
370 ancestor
->loop_depth
= loop
->depth
;
372 stack
[sp
++] = ancestor
;
382 /* Find the root node of the loop pre-header extended basic block and
383 the edges along the trace from the root node to the loop header. */
386 flow_loop_pre_header_scan (struct loop
*loop
)
392 loop
->num_pre_header_edges
= 0;
393 if (loop
->num_entries
!= 1)
396 ebb
= loop
->entry_edges
[0]->src
;
397 if (ebb
== ENTRY_BLOCK_PTR
)
400 /* Count number of edges along trace from loop header to
401 root of pre-header extended basic block. Usually this is
402 only one or two edges. */
404 EDGE_PRED (ebb
, 0)->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (ebb
->preds
) == 1;
406 ebb
= EDGE_PRED (ebb
, 0)->src
;
408 loop
->pre_header_edges
= xmalloc (num
* sizeof (edge
));
409 loop
->num_pre_header_edges
= num
;
411 /* Store edges in order that they are followed. The source of the first edge
412 is the root node of the pre-header extended basic block and the
413 destination of the last last edge is the loop header. */
414 for (e
= loop
->entry_edges
[0]; num
; e
= EDGE_PRED (e
->src
, 0))
415 loop
->pre_header_edges
[--num
] = e
;
418 /* Return the block for the pre-header of the loop with header
419 HEADER. Return NULL if there is no pre-header. */
422 flow_loop_pre_header_find (basic_block header
)
424 basic_block pre_header
;
427 /* If block p is a predecessor of the header and is the only block
428 that the header does not dominate, then it is the pre-header. */
430 FOR_EACH_EDGE (e
, header
->preds
)
432 basic_block node
= e
->src
;
434 if (node
!= ENTRY_BLOCK_PTR
435 && ! dominated_by_p (CDI_DOMINATORS
, node
, header
))
437 if (pre_header
== NULL
)
441 /* There are multiple edges into the header from outside
442 the loop so there is no pre-header block. */
454 establish_preds (struct loop
*loop
)
456 struct loop
*ploop
, *father
= loop
->outer
;
458 loop
->depth
= father
->depth
+ 1;
461 loop
->pred
= xmalloc (sizeof (struct loop
*) * loop
->depth
);
462 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
463 loop
->pred
[father
->depth
] = father
;
465 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
466 establish_preds (ploop
);
469 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
470 added loop. If LOOP has some children, take care of that their
471 pred field will be initialized correctly. */
474 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
476 loop
->next
= father
->inner
;
477 father
->inner
= loop
;
478 loop
->outer
= father
;
480 establish_preds (loop
);
483 /* Remove LOOP from the loop hierarchy tree. */
486 flow_loop_tree_node_remove (struct loop
*loop
)
488 struct loop
*prev
, *father
;
490 father
= loop
->outer
;
493 /* Remove loop from the list of sons. */
494 if (father
->inner
== loop
)
495 father
->inner
= loop
->next
;
498 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
499 prev
->next
= loop
->next
;
507 /* Helper function to compute loop nesting depth and enclosed loop level
508 for the natural loop specified by LOOP. Returns the loop level. */
511 flow_loop_level_compute (struct loop
*loop
)
519 /* Traverse loop tree assigning depth and computing level as the
520 maximum level of all the inner loops of this loop. The loop
521 level is equivalent to the height of the loop in the loop tree
522 and corresponds to the number of enclosed loop levels (including
524 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
526 int ilevel
= flow_loop_level_compute (inner
) + 1;
536 /* Compute the loop nesting depth and enclosed loop level for the loop
537 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
541 flow_loops_level_compute (struct loops
*loops
)
543 return flow_loop_level_compute (loops
->tree_root
);
546 /* Scan a single natural loop specified by LOOP collecting information
547 about it specified by FLAGS. */
550 flow_loop_scan (struct loop
*loop
, int flags
)
552 if (flags
& LOOP_ENTRY_EDGES
)
554 /* Find edges which enter the loop header.
555 Note that the entry edges should only
556 enter the header of a natural loop. */
557 flow_loop_entry_edges_find (loop
);
560 if (flags
& LOOP_EXIT_EDGES
)
562 /* Find edges which exit the loop. */
563 flow_loop_exit_edges_find (loop
);
566 if (flags
& LOOP_PRE_HEADER
)
568 /* Look to see if the loop has a pre-header node. */
569 loop
->pre_header
= flow_loop_pre_header_find (loop
->header
);
571 /* Find the blocks within the extended basic block of
572 the loop pre-header. */
573 flow_loop_pre_header_scan (loop
);
579 /* A callback to update latch and header info for basic block JUMP created
580 by redirecting an edge. */
583 update_latch_info (basic_block jump
)
585 alloc_aux_for_block (jump
, sizeof (int));
586 HEADER_BLOCK (jump
) = 0;
587 alloc_aux_for_edge (EDGE_PRED (jump
, 0), sizeof (int));
588 LATCH_EDGE (EDGE_PRED (jump
, 0)) = 0;
589 set_immediate_dominator (CDI_DOMINATORS
, jump
, EDGE_PRED (jump
, 0)->src
);
592 /* A callback for make_forwarder block, to redirect all edges except for
593 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
594 whether to redirect it. */
596 static edge mfb_kj_edge
;
598 mfb_keep_just (edge e
)
600 return e
!= mfb_kj_edge
;
603 /* A callback for make_forwarder block, to redirect the latch edges into an
604 entry part. E is the edge for that we should decide whether to redirect
608 mfb_keep_nonlatch (edge e
)
610 return LATCH_EDGE (e
);
613 /* Takes care of merging natural loops with shared headers. */
616 canonicalize_loop_headers (void)
621 alloc_aux_for_blocks (sizeof (int));
622 alloc_aux_for_edges (sizeof (int));
624 /* Split blocks so that each loop has only single latch. */
628 int have_abnormal_edge
= 0;
630 FOR_EACH_EDGE (e
, header
->preds
)
632 basic_block latch
= e
->src
;
634 if (e
->flags
& EDGE_ABNORMAL
)
635 have_abnormal_edge
= 1;
637 if (latch
!= ENTRY_BLOCK_PTR
638 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
646 if (have_abnormal_edge
)
647 HEADER_BLOCK (header
) = 0;
649 HEADER_BLOCK (header
) = num_latches
;
652 if (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
))
656 /* We could not redirect edges freely here. On the other hand,
657 we can simply split the edge from entry block. */
658 bb
= split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR
, 0));
660 alloc_aux_for_edge (EDGE_SUCC (bb
, 0), sizeof (int));
661 LATCH_EDGE (EDGE_SUCC (bb
, 0)) = 0;
662 alloc_aux_for_block (bb
, sizeof (int));
663 HEADER_BLOCK (bb
) = 0;
668 int max_freq
, is_heavy
;
669 edge heavy
, tmp_edge
;
671 if (HEADER_BLOCK (header
) <= 1)
674 /* Find a heavy edge. */
679 FOR_EACH_EDGE (e
, header
->preds
)
681 if (LATCH_EDGE (e
) &&
682 EDGE_FREQUENCY (e
) > max_freq
)
683 max_freq
= EDGE_FREQUENCY (e
);
687 FOR_EACH_EDGE (e
, header
->preds
)
689 if (LATCH_EDGE (e
) &&
690 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
705 /* Split out the heavy edge, and create inner loop for it. */
707 tmp_edge
= make_forwarder_block (header
, mfb_keep_just
,
709 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
710 HEADER_BLOCK (tmp_edge
->dest
) = 1;
711 alloc_aux_for_edge (tmp_edge
, sizeof (int));
712 LATCH_EDGE (tmp_edge
) = 0;
713 HEADER_BLOCK (header
)--;
716 if (HEADER_BLOCK (header
) > 1)
718 /* Create a new latch block. */
719 tmp_edge
= make_forwarder_block (header
, mfb_keep_nonlatch
,
721 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
722 HEADER_BLOCK (tmp_edge
->src
) = 0;
723 HEADER_BLOCK (tmp_edge
->dest
) = 1;
724 alloc_aux_for_edge (tmp_edge
, sizeof (int));
725 LATCH_EDGE (tmp_edge
) = 1;
729 free_aux_for_blocks ();
730 free_aux_for_edges ();
732 #ifdef ENABLE_CHECKING
733 verify_dominators (CDI_DOMINATORS
);
737 /* Find all the natural loops in the function and save in LOOPS structure and
738 recalculate loop_depth information in basic block structures. FLAGS
739 controls which loop information is collected. Return the number of natural
743 flow_loops_find (struct loops
*loops
, int flags
)
755 /* This function cannot be repeatedly called with different
756 flags to build up the loop information. The loop tree
757 must always be built if this function is called. */
758 if (! (flags
& LOOP_TREE
))
761 memset (loops
, 0, sizeof *loops
);
763 /* Taking care of this degenerate case makes the rest of
764 this code simpler. */
765 if (n_basic_blocks
== 0)
771 /* Ensure that the dominators are computed. */
772 calculate_dominance_info (CDI_DOMINATORS
);
774 /* Join loops with shared headers. */
775 canonicalize_loop_headers ();
777 /* Count the number of loop headers. This should be the
778 same as the number of natural loops. */
779 headers
= sbitmap_alloc (last_basic_block
);
780 sbitmap_zero (headers
);
785 int more_latches
= 0;
787 header
->loop_depth
= 0;
789 /* If we have an abnormal predecessor, do not consider the
790 loop (not worth the problems). */
791 FOR_EACH_EDGE (e
, header
->preds
)
793 if (e
->flags
& EDGE_ABNORMAL
)
801 FOR_EACH_EDGE (e
, header
->preds
)
803 basic_block latch
= e
->src
;
805 if (e
->flags
& EDGE_ABNORMAL
)
808 /* Look for back edges where a predecessor is dominated
809 by this block. A natural loop has a single entry
810 node (header) that dominates all the nodes in the
811 loop. It also has single back edge to the header
812 from a latch node. */
813 if (latch
!= ENTRY_BLOCK_PTR
814 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
816 /* Shared headers should be eliminated by now. */
820 SET_BIT (headers
, header
->index
);
827 /* Allocate loop structures. */
828 loops
->parray
= xcalloc (num_loops
+ 1, sizeof (struct loop
*));
830 /* Dummy loop containing whole function. */
831 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
832 loops
->parray
[0]->next
= NULL
;
833 loops
->parray
[0]->inner
= NULL
;
834 loops
->parray
[0]->outer
= NULL
;
835 loops
->parray
[0]->depth
= 0;
836 loops
->parray
[0]->pred
= NULL
;
837 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
838 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
839 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
840 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
841 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
843 loops
->tree_root
= loops
->parray
[0];
845 /* Find and record information about all the natural loops
849 bb
->loop_father
= loops
->tree_root
;
853 /* Compute depth first search order of the CFG so that outer
854 natural loops will be found before inner natural loops. */
855 dfs_order
= xmalloc (n_basic_blocks
* sizeof (int));
856 rc_order
= xmalloc (n_basic_blocks
* sizeof (int));
857 flow_depth_first_order_compute (dfs_order
, rc_order
);
859 /* Save CFG derived information to avoid recomputing it. */
860 loops
->cfg
.dfs_order
= dfs_order
;
861 loops
->cfg
.rc_order
= rc_order
;
865 for (b
= 0; b
< n_basic_blocks
; b
++)
869 /* Search the nodes of the CFG in reverse completion order
870 so that we can find outer loops first. */
871 if (!TEST_BIT (headers
, rc_order
[b
]))
874 header
= BASIC_BLOCK (rc_order
[b
]);
876 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
878 loop
->header
= header
;
879 loop
->num
= num_loops
;
882 /* Look for the latch for this header block. */
883 FOR_EACH_EDGE (e
, header
->preds
)
885 basic_block latch
= e
->src
;
887 if (latch
!= ENTRY_BLOCK_PTR
888 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
896 flow_loop_tree_node_add (header
->loop_father
, loop
);
897 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
900 /* Assign the loop nesting depth and enclosed loop level for each
902 loops
->levels
= flow_loops_level_compute (loops
);
904 /* Scan the loops. */
905 for (i
= 1; i
< num_loops
; i
++)
906 flow_loop_scan (loops
->parray
[i
], flags
);
908 loops
->num
= num_loops
;
911 sbitmap_free (headers
);
914 #ifdef ENABLE_CHECKING
916 verify_loop_structure (loops
);
922 /* Update the information regarding the loops in the CFG
923 specified by LOOPS. */
926 flow_loops_update (struct loops
*loops
, int flags
)
928 /* One day we may want to update the current loop data. For now
929 throw away the old stuff and rebuild what we need. */
931 flow_loops_free (loops
);
933 return flow_loops_find (loops
, flags
);
936 /* Return nonzero if basic block BB belongs to LOOP. */
938 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
940 struct loop
*source_loop
;
942 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
945 source_loop
= bb
->loop_father
;
946 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
949 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
952 flow_loop_outside_edge_p (const struct loop
*loop
, edge e
)
954 if (e
->dest
!= loop
->header
)
956 return !flow_bb_inside_loop_p (loop
, e
->src
);
959 /* Enumeration predicate for get_loop_body. */
961 glb_enum_p (basic_block bb
, void *glb_header
)
963 return bb
!= (basic_block
) glb_header
;
966 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
967 order against direction of edges from latch. Specially, if
968 header != latch, latch is the 1-st block. */
970 get_loop_body (const struct loop
*loop
)
972 basic_block
*tovisit
, bb
;
975 if (!loop
->num_nodes
)
978 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
979 tovisit
[tv
++] = loop
->header
;
981 if (loop
->latch
== EXIT_BLOCK_PTR
)
983 /* There may be blocks unreachable from EXIT_BLOCK. */
984 if (loop
->num_nodes
!= (unsigned) n_basic_blocks
+ 2)
988 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
990 else if (loop
->latch
!= loop
->header
)
992 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
993 tovisit
+ 1, loop
->num_nodes
- 1,
997 if (tv
!= loop
->num_nodes
)
1002 /* Fills dominance descendants inside LOOP of the basic block BB into
1003 array TOVISIT from index *TV. */
1006 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
1007 basic_block
*tovisit
, int *tv
)
1009 basic_block son
, postpone
= NULL
;
1011 tovisit
[(*tv
)++] = bb
;
1012 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1014 son
= next_dom_son (CDI_DOMINATORS
, son
))
1016 if (!flow_bb_inside_loop_p (loop
, son
))
1019 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
1024 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
1028 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
1031 /* Gets body of a LOOP (that must be different from the outermost loop)
1032 sorted by dominance relation. Additionally, if a basic block s dominates
1033 the latch, then only blocks dominated by s are be after it. */
1036 get_loop_body_in_dom_order (const struct loop
*loop
)
1038 basic_block
*tovisit
;
1041 if (!loop
->num_nodes
)
1044 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1046 if (loop
->latch
== EXIT_BLOCK_PTR
)
1050 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
1052 if (tv
!= (int) loop
->num_nodes
)
1058 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1060 get_loop_exit_edges (const struct loop
*loop
, unsigned int *n_edges
)
1066 if (loop
->latch
== EXIT_BLOCK_PTR
)
1069 body
= get_loop_body (loop
);
1071 for (i
= 0; i
< loop
->num_nodes
; i
++)
1072 FOR_EACH_EDGE (e
, body
[i
]->succs
)
1074 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1078 edges
= xmalloc (n
* sizeof (edge
));
1081 for (i
= 0; i
< loop
->num_nodes
; i
++)
1082 FOR_EACH_EDGE (e
, body
[i
]->succs
)
1084 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1093 /* Counts the number of conditional branches inside LOOP. */
1096 num_loop_branches (const struct loop
*loop
)
1101 if (loop
->latch
== EXIT_BLOCK_PTR
)
1104 body
= get_loop_body (loop
);
1106 for (i
= 0; i
< loop
->num_nodes
; i
++)
1107 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1114 /* Adds basic block BB to LOOP. */
1116 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1120 bb
->loop_father
= loop
;
1121 bb
->loop_depth
= loop
->depth
;
1123 for (i
= 0; i
< loop
->depth
; i
++)
1124 loop
->pred
[i
]->num_nodes
++;
1127 /* Remove basic block BB from loops. */
1129 remove_bb_from_loops (basic_block bb
)
1132 struct loop
*loop
= bb
->loop_father
;
1135 for (i
= 0; i
< loop
->depth
; i
++)
1136 loop
->pred
[i
]->num_nodes
--;
1137 bb
->loop_father
= NULL
;
1141 /* Finds nearest common ancestor in loop tree for given loops. */
1143 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1145 if (!loop_s
) return loop_d
;
1146 if (!loop_d
) return loop_s
;
1148 if (loop_s
->depth
< loop_d
->depth
)
1149 loop_d
= loop_d
->pred
[loop_s
->depth
];
1150 else if (loop_s
->depth
> loop_d
->depth
)
1151 loop_s
= loop_s
->pred
[loop_d
->depth
];
1153 while (loop_s
!= loop_d
)
1155 loop_s
= loop_s
->outer
;
1156 loop_d
= loop_d
->outer
;
1161 /* Cancels the LOOP; it must be innermost one. */
1163 cancel_loop (struct loops
*loops
, struct loop
*loop
)
1171 /* Move blocks up one level (they should be removed as soon as possible). */
1172 bbs
= get_loop_body (loop
);
1173 for (i
= 0; i
< loop
->num_nodes
; i
++)
1174 bbs
[i
]->loop_father
= loop
->outer
;
1176 /* Remove the loop from structure. */
1177 flow_loop_tree_node_remove (loop
);
1179 /* Remove loop from loops array. */
1180 loops
->parray
[loop
->num
] = NULL
;
1182 /* Free loop data. */
1183 flow_loop_free (loop
);
1186 /* Cancels LOOP and all its subloops. */
1188 cancel_loop_tree (struct loops
*loops
, struct loop
*loop
)
1191 cancel_loop_tree (loops
, loop
->inner
);
1192 cancel_loop (loops
, loop
);
1195 /* Checks that LOOPS are all right:
1196 -- sizes of loops are all right
1197 -- results of get_loop_body really belong to the loop
1198 -- loop header have just single entry edge and single latch edge
1199 -- loop latches have only single successor that is header of their loop
1200 -- irreducible loops are correctly marked
1203 verify_loop_structure (struct loops
*loops
)
1205 unsigned *sizes
, i
, j
;
1207 basic_block
*bbs
, bb
;
1213 sizes
= xcalloc (loops
->num
, sizeof (int));
1217 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1220 for (i
= 0; i
< loops
->num
; i
++)
1222 if (!loops
->parray
[i
])
1225 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1227 error ("Size of loop %d should be %d, not %d.",
1228 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1235 /* Check get_loop_body. */
1236 for (i
= 1; i
< loops
->num
; i
++)
1238 loop
= loops
->parray
[i
];
1241 bbs
= get_loop_body (loop
);
1243 for (j
= 0; j
< loop
->num_nodes
; j
++)
1244 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1246 error ("Bb %d do not belong to loop %d.",
1253 /* Check headers and latches. */
1254 for (i
= 1; i
< loops
->num
; i
++)
1256 loop
= loops
->parray
[i
];
1260 if ((loops
->state
& LOOPS_HAVE_PREHEADERS
)
1261 && EDGE_COUNT (loop
->header
->preds
) != 2)
1263 error ("Loop %d's header does not have exactly 2 entries.", i
);
1266 if (loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1268 if (EDGE_COUNT (loop
->latch
->succs
) != 1)
1270 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1273 if (EDGE_SUCC (loop
->latch
, 0)->dest
!= loop
->header
)
1275 error ("Loop %d's latch does not have header as successor.", i
);
1278 if (loop
->latch
->loop_father
!= loop
)
1280 error ("Loop %d's latch does not belong directly to it.", i
);
1284 if (loop
->header
->loop_father
!= loop
)
1286 error ("Loop %d's header does not belong directly to it.", i
);
1289 if ((loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1290 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1292 error ("Loop %d's latch is marked as part of irreducible region.", i
);
1297 /* Check irreducible loops. */
1298 if (loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1300 /* Record old info. */
1301 irreds
= sbitmap_alloc (last_basic_block
);
1304 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1305 SET_BIT (irreds
, bb
->index
);
1307 RESET_BIT (irreds
, bb
->index
);
1308 FOR_EACH_EDGE (e
, bb
->succs
)
1310 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1311 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1317 mark_irreducible_loops (loops
);
1322 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1323 && !TEST_BIT (irreds
, bb
->index
))
1325 error ("Basic block %d should be marked irreducible.", bb
->index
);
1328 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1329 && TEST_BIT (irreds
, bb
->index
))
1331 error ("Basic block %d should not be marked irreducible.", bb
->index
);
1334 FOR_EACH_EDGE (e
, bb
->succs
)
1336 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1337 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1339 error ("Edge from %d to %d should be marked irreducible.",
1340 e
->src
->index
, e
->dest
->index
);
1343 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1344 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1346 error ("Edge from %d to %d should not be marked irreducible.",
1347 e
->src
->index
, e
->dest
->index
);
1350 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1361 /* Returns latch edge of LOOP. */
1363 loop_latch_edge (const struct loop
*loop
)
1367 FOR_EACH_EDGE (e
, loop
->header
->preds
)
1369 if (e
->src
== loop
->latch
)
1377 /* Returns preheader edge of LOOP. */
1379 loop_preheader_edge (const struct loop
*loop
)
1383 FOR_EACH_EDGE (e
, loop
->header
->preds
)
1385 if (e
->src
!= loop
->latch
)