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 (succ
= bb
->succ
; succ
; succ
= succ
->succ_next
)
70 fprintf (file
, "%d ", succ
->dest
->index
);
71 fprintf (file
, "}\n");
74 /* Dump the DFS node order. */
75 if (loops
->cfg
.dfs_order
)
77 fputs (";; DFS order: ", file
);
78 for (i
= 0; i
< n_basic_blocks
; i
++)
79 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
84 /* Dump the reverse completion node order. */
85 if (loops
->cfg
.rc_order
)
87 fputs (";; RC order: ", file
);
88 for (i
= 0; i
< n_basic_blocks
; i
++)
89 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
95 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
98 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
100 return (loop
->depth
> outer
->depth
101 && loop
->pred
[outer
->depth
] == outer
);
104 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
105 loops within LOOP. */
108 superloop_at_depth (struct loop
*loop
, unsigned depth
)
110 if (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
)
219 /* Free the loop descriptors. */
220 for (i
= 0; i
< loops
->num
; i
++)
222 struct loop
*loop
= loops
->parray
[i
];
227 flow_loop_free (loop
);
230 free (loops
->parray
);
231 loops
->parray
= NULL
;
233 if (loops
->cfg
.dfs_order
)
234 free (loops
->cfg
.dfs_order
);
235 if (loops
->cfg
.rc_order
)
236 free (loops
->cfg
.rc_order
);
241 /* Find the entry edges into the LOOP. */
244 flow_loop_entry_edges_find (struct loop
*loop
)
250 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
252 if (flow_loop_outside_edge_p (loop
, e
))
259 loop
->entry_edges
= xmalloc (num_entries
* sizeof (edge
*));
262 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
264 if (flow_loop_outside_edge_p (loop
, e
))
265 loop
->entry_edges
[num_entries
++] = e
;
268 loop
->num_entries
= num_entries
;
271 /* Find the exit edges from the LOOP. */
274 flow_loop_exit_edges_find (struct loop
*loop
)
277 basic_block node
, *bbs
;
278 unsigned num_exits
, i
;
280 loop
->exit_edges
= NULL
;
283 /* Check all nodes within the loop to see if there are any
284 successors not in the loop. Note that a node may have multiple
287 bbs
= get_loop_body (loop
);
288 for (i
= 0; i
< loop
->num_nodes
; i
++)
291 for (e
= node
->succ
; e
; e
= e
->succ_next
)
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
++)
313 for (e
= node
->succ
; e
; e
= e
->succ_next
)
315 basic_block dest
= e
->dest
;
317 if (!flow_bb_inside_loop_p (loop
, dest
))
318 loop
->exit_edges
[num_exits
++] = e
;
322 loop
->num_exits
= num_exits
;
325 /* Find the nodes contained within the LOOP with header HEADER.
326 Return the number of nodes within the loop. */
329 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
335 header
->loop_father
= loop
;
336 header
->loop_depth
= loop
->depth
;
338 if (loop
->latch
->loop_father
!= loop
)
340 stack
= xmalloc (n_basic_blocks
* sizeof (basic_block
));
343 stack
[sp
++] = loop
->latch
;
344 loop
->latch
->loop_father
= loop
;
345 loop
->latch
->loop_depth
= loop
->depth
;
354 for (e
= node
->pred
; e
; e
= e
->pred_next
)
356 basic_block ancestor
= e
->src
;
358 if (ancestor
!= ENTRY_BLOCK_PTR
359 && ancestor
->loop_father
!= loop
)
361 ancestor
->loop_father
= loop
;
362 ancestor
->loop_depth
= loop
->depth
;
364 stack
[sp
++] = ancestor
;
373 /* For each loop in the lOOPS tree that has just a single exit
374 record the exit edge. */
377 mark_single_exit_loops (struct loops
*loops
)
384 for (i
= 1; i
< loops
->num
; i
++)
386 loop
= loops
->parray
[i
];
388 loop
->single_exit
= NULL
;
393 if (bb
->loop_father
== loops
->tree_root
)
395 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
397 if (e
->dest
== EXIT_BLOCK_PTR
)
400 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
403 for (loop
= bb
->loop_father
;
404 loop
!= e
->dest
->loop_father
;
407 /* If we have already seen an exit, mark this by the edge that
408 surely does not occur as any exit. */
409 if (loop
->single_exit
)
410 loop
->single_exit
= ENTRY_BLOCK_PTR
->succ
;
412 loop
->single_exit
= e
;
417 for (i
= 1; i
< loops
->num
; i
++)
419 loop
= loops
->parray
[i
];
423 if (loop
->single_exit
== ENTRY_BLOCK_PTR
->succ
)
424 loop
->single_exit
= NULL
;
427 loops
->state
|= LOOPS_HAVE_MARKED_SINGLE_EXITS
;
430 /* Find the root node of the loop pre-header extended basic block and
431 the edges along the trace from the root node to the loop header. */
434 flow_loop_pre_header_scan (struct loop
*loop
)
440 loop
->num_pre_header_edges
= 0;
441 if (loop
->num_entries
!= 1)
444 ebb
= loop
->entry_edges
[0]->src
;
445 if (ebb
== ENTRY_BLOCK_PTR
)
448 /* Count number of edges along trace from loop header to
449 root of pre-header extended basic block. Usually this is
450 only one or two edges. */
451 for (num
= 1; ebb
->pred
->src
!= ENTRY_BLOCK_PTR
&& ! ebb
->pred
->pred_next
;
453 ebb
= ebb
->pred
->src
;
455 loop
->pre_header_edges
= xmalloc (num
* sizeof (edge
));
456 loop
->num_pre_header_edges
= num
;
458 /* Store edges in order that they are followed. The source of the first edge
459 is the root node of the pre-header extended basic block and the
460 destination of the last last edge is the loop header. */
461 for (e
= loop
->entry_edges
[0]; num
; e
= e
->src
->pred
)
462 loop
->pre_header_edges
[--num
] = e
;
465 /* Return the block for the pre-header of the loop with header
466 HEADER. Return NULL if there is no pre-header. */
469 flow_loop_pre_header_find (basic_block header
)
471 basic_block pre_header
;
474 /* If block p is a predecessor of the header and is the only block
475 that the header does not dominate, then it is the pre-header. */
477 for (e
= header
->pred
; e
; e
= e
->pred_next
)
479 basic_block node
= e
->src
;
481 if (node
!= ENTRY_BLOCK_PTR
482 && ! dominated_by_p (CDI_DOMINATORS
, node
, header
))
484 if (pre_header
== NULL
)
488 /* There are multiple edges into the header from outside
489 the loop so there is no pre-header block. */
500 establish_preds (struct loop
*loop
)
502 struct loop
*ploop
, *father
= loop
->outer
;
504 loop
->depth
= father
->depth
+ 1;
507 loop
->pred
= xmalloc (sizeof (struct loop
*) * loop
->depth
);
508 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
509 loop
->pred
[father
->depth
] = father
;
511 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
512 establish_preds (ploop
);
515 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
516 added loop. If LOOP has some children, take care of that their
517 pred field will be initialized correctly. */
520 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
522 loop
->next
= father
->inner
;
523 father
->inner
= loop
;
524 loop
->outer
= father
;
526 establish_preds (loop
);
529 /* Remove LOOP from the loop hierarchy tree. */
532 flow_loop_tree_node_remove (struct loop
*loop
)
534 struct loop
*prev
, *father
;
536 father
= loop
->outer
;
539 /* Remove loop from the list of sons. */
540 if (father
->inner
== loop
)
541 father
->inner
= loop
->next
;
544 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
545 prev
->next
= loop
->next
;
553 /* Helper function to compute loop nesting depth and enclosed loop level
554 for the natural loop specified by LOOP. Returns the loop level. */
557 flow_loop_level_compute (struct loop
*loop
)
565 /* Traverse loop tree assigning depth and computing level as the
566 maximum level of all the inner loops of this loop. The loop
567 level is equivalent to the height of the loop in the loop tree
568 and corresponds to the number of enclosed loop levels (including
570 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
572 int ilevel
= flow_loop_level_compute (inner
) + 1;
582 /* Compute the loop nesting depth and enclosed loop level for the loop
583 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
587 flow_loops_level_compute (struct loops
*loops
)
589 return flow_loop_level_compute (loops
->tree_root
);
592 /* Scan a single natural loop specified by LOOP collecting information
593 about it specified by FLAGS. */
596 flow_loop_scan (struct loop
*loop
, int flags
)
598 if (flags
& LOOP_ENTRY_EDGES
)
600 /* Find edges which enter the loop header.
601 Note that the entry edges should only
602 enter the header of a natural loop. */
603 flow_loop_entry_edges_find (loop
);
606 if (flags
& LOOP_EXIT_EDGES
)
608 /* Find edges which exit the loop. */
609 flow_loop_exit_edges_find (loop
);
612 if (flags
& LOOP_PRE_HEADER
)
614 /* Look to see if the loop has a pre-header node. */
615 loop
->pre_header
= flow_loop_pre_header_find (loop
->header
);
617 /* Find the blocks within the extended basic block of
618 the loop pre-header. */
619 flow_loop_pre_header_scan (loop
);
625 /* A callback to update latch and header info for basic block JUMP created
626 by redirecting an edge. */
629 update_latch_info (basic_block jump
)
631 alloc_aux_for_block (jump
, sizeof (int));
632 HEADER_BLOCK (jump
) = 0;
633 alloc_aux_for_edge (jump
->pred
, sizeof (int));
634 LATCH_EDGE (jump
->pred
) = 0;
635 set_immediate_dominator (CDI_DOMINATORS
, jump
, jump
->pred
->src
);
638 /* A callback for make_forwarder block, to redirect all edges except for
639 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
640 whether to redirect it. */
642 static edge mfb_kj_edge
;
644 mfb_keep_just (edge e
)
646 return e
!= mfb_kj_edge
;
649 /* A callback for make_forwarder block, to redirect the latch edges into an
650 entry part. E is the edge for that we should decide whether to redirect
654 mfb_keep_nonlatch (edge e
)
656 return LATCH_EDGE (e
);
659 /* Takes care of merging natural loops with shared headers. */
662 canonicalize_loop_headers (void)
667 alloc_aux_for_blocks (sizeof (int));
668 alloc_aux_for_edges (sizeof (int));
670 /* Split blocks so that each loop has only single latch. */
674 int have_abnormal_edge
= 0;
676 for (e
= header
->pred
; e
; e
= e
->pred_next
)
678 basic_block latch
= e
->src
;
680 if (e
->flags
& EDGE_ABNORMAL
)
681 have_abnormal_edge
= 1;
683 if (latch
!= ENTRY_BLOCK_PTR
684 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
690 if (have_abnormal_edge
)
691 HEADER_BLOCK (header
) = 0;
693 HEADER_BLOCK (header
) = num_latches
;
696 if (HEADER_BLOCK (ENTRY_BLOCK_PTR
->succ
->dest
))
700 /* We could not redirect edges freely here. On the other hand,
701 we can simply split the edge from entry block. */
702 bb
= split_edge (ENTRY_BLOCK_PTR
->succ
);
704 alloc_aux_for_edge (bb
->succ
, sizeof (int));
705 LATCH_EDGE (bb
->succ
) = 0;
706 alloc_aux_for_block (bb
, sizeof (int));
707 HEADER_BLOCK (bb
) = 0;
712 int max_freq
, is_heavy
;
713 edge heavy
, tmp_edge
;
715 if (HEADER_BLOCK (header
) <= 1)
718 /* Find a heavy edge. */
722 for (e
= header
->pred
; e
; e
= e
->pred_next
)
723 if (LATCH_EDGE (e
) &&
724 EDGE_FREQUENCY (e
) > max_freq
)
725 max_freq
= EDGE_FREQUENCY (e
);
726 for (e
= header
->pred
; e
; e
= e
->pred_next
)
727 if (LATCH_EDGE (e
) &&
728 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
741 /* Split out the heavy edge, and create inner loop for it. */
743 tmp_edge
= make_forwarder_block (header
, mfb_keep_just
,
745 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
746 HEADER_BLOCK (tmp_edge
->dest
) = 1;
747 alloc_aux_for_edge (tmp_edge
, sizeof (int));
748 LATCH_EDGE (tmp_edge
) = 0;
749 HEADER_BLOCK (header
)--;
752 if (HEADER_BLOCK (header
) > 1)
754 /* Create a new latch block. */
755 tmp_edge
= make_forwarder_block (header
, mfb_keep_nonlatch
,
757 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
758 HEADER_BLOCK (tmp_edge
->src
) = 0;
759 HEADER_BLOCK (tmp_edge
->dest
) = 1;
760 alloc_aux_for_edge (tmp_edge
, sizeof (int));
761 LATCH_EDGE (tmp_edge
) = 1;
765 free_aux_for_blocks ();
766 free_aux_for_edges ();
768 #ifdef ENABLE_CHECKING
769 verify_dominators (CDI_DOMINATORS
);
773 /* Find all the natural loops in the function and save in LOOPS structure and
774 recalculate loop_depth information in basic block structures. FLAGS
775 controls which loop information is collected. Return the number of natural
779 flow_loops_find (struct loops
*loops
, int flags
)
791 /* This function cannot be repeatedly called with different
792 flags to build up the loop information. The loop tree
793 must always be built if this function is called. */
794 if (! (flags
& LOOP_TREE
))
797 memset (loops
, 0, sizeof *loops
);
799 /* Taking care of this degenerate case makes the rest of
800 this code simpler. */
801 if (n_basic_blocks
== 0)
807 /* Ensure that the dominators are computed. */
808 calculate_dominance_info (CDI_DOMINATORS
);
810 /* Join loops with shared headers. */
811 canonicalize_loop_headers ();
813 /* Count the number of loop headers. This should be the
814 same as the number of natural loops. */
815 headers
= sbitmap_alloc (last_basic_block
);
816 sbitmap_zero (headers
);
821 int more_latches
= 0;
823 header
->loop_depth
= 0;
825 /* If we have an abnormal predecessor, do not consider the
826 loop (not worth the problems). */
827 for (e
= header
->pred
; e
; e
= e
->pred_next
)
828 if (e
->flags
& EDGE_ABNORMAL
)
833 for (e
= header
->pred
; e
; e
= e
->pred_next
)
835 basic_block latch
= e
->src
;
837 if (e
->flags
& EDGE_ABNORMAL
)
840 /* Look for back edges where a predecessor is dominated
841 by this block. A natural loop has a single entry
842 node (header) that dominates all the nodes in the
843 loop. It also has single back edge to the header
844 from a latch node. */
845 if (latch
!= ENTRY_BLOCK_PTR
846 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
848 /* Shared headers should be eliminated by now. */
852 SET_BIT (headers
, header
->index
);
858 /* Allocate loop structures. */
859 loops
->parray
= xcalloc (num_loops
+ 1, sizeof (struct loop
*));
861 /* Dummy loop containing whole function. */
862 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
863 loops
->parray
[0]->next
= NULL
;
864 loops
->parray
[0]->inner
= NULL
;
865 loops
->parray
[0]->outer
= NULL
;
866 loops
->parray
[0]->depth
= 0;
867 loops
->parray
[0]->pred
= NULL
;
868 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
869 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
870 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
871 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
872 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
874 loops
->tree_root
= loops
->parray
[0];
876 /* Find and record information about all the natural loops
880 bb
->loop_father
= loops
->tree_root
;
884 /* Compute depth first search order of the CFG so that outer
885 natural loops will be found before inner natural loops. */
886 dfs_order
= xmalloc (n_basic_blocks
* sizeof (int));
887 rc_order
= xmalloc (n_basic_blocks
* sizeof (int));
888 flow_depth_first_order_compute (dfs_order
, rc_order
);
890 /* Save CFG derived information to avoid recomputing it. */
891 loops
->cfg
.dfs_order
= dfs_order
;
892 loops
->cfg
.rc_order
= rc_order
;
896 for (b
= 0; b
< n_basic_blocks
; b
++)
900 /* Search the nodes of the CFG in reverse completion order
901 so that we can find outer loops first. */
902 if (!TEST_BIT (headers
, rc_order
[b
]))
905 header
= BASIC_BLOCK (rc_order
[b
]);
907 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
909 loop
->header
= header
;
910 loop
->num
= num_loops
;
913 /* Look for the latch for this header block. */
914 for (e
= header
->pred
; e
; e
= e
->pred_next
)
916 basic_block latch
= e
->src
;
918 if (latch
!= ENTRY_BLOCK_PTR
919 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
926 flow_loop_tree_node_add (header
->loop_father
, loop
);
927 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
930 /* Assign the loop nesting depth and enclosed loop level for each
932 loops
->levels
= flow_loops_level_compute (loops
);
934 /* Scan the loops. */
935 for (i
= 1; i
< num_loops
; i
++)
936 flow_loop_scan (loops
->parray
[i
], flags
);
938 loops
->num
= num_loops
;
941 sbitmap_free (headers
);
944 #ifdef ENABLE_CHECKING
946 verify_loop_structure (loops
);
952 /* Update the information regarding the loops in the CFG
953 specified by LOOPS. */
956 flow_loops_update (struct loops
*loops
, int flags
)
958 /* One day we may want to update the current loop data. For now
959 throw away the old stuff and rebuild what we need. */
961 flow_loops_free (loops
);
963 return flow_loops_find (loops
, flags
);
966 /* Return nonzero if basic block BB belongs to LOOP. */
968 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
970 struct loop
*source_loop
;
972 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
975 source_loop
= bb
->loop_father
;
976 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
979 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
982 flow_loop_outside_edge_p (const struct loop
*loop
, edge e
)
984 if (e
->dest
!= loop
->header
)
986 return !flow_bb_inside_loop_p (loop
, e
->src
);
989 /* Enumeration predicate for get_loop_body. */
991 glb_enum_p (basic_block bb
, void *glb_header
)
993 return bb
!= (basic_block
) glb_header
;
996 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
997 order against direction of edges from latch. Specially, if
998 header != latch, latch is the 1-st block. */
1000 get_loop_body (const struct loop
*loop
)
1002 basic_block
*tovisit
, bb
;
1005 if (!loop
->num_nodes
)
1008 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1009 tovisit
[tv
++] = loop
->header
;
1011 if (loop
->latch
== EXIT_BLOCK_PTR
)
1013 /* There may be blocks unreachable from EXIT_BLOCK. */
1014 if (loop
->num_nodes
!= (unsigned) n_basic_blocks
+ 2)
1018 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
1020 else if (loop
->latch
!= loop
->header
)
1022 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
1023 tovisit
+ 1, loop
->num_nodes
- 1,
1027 if (tv
!= loop
->num_nodes
)
1032 /* Fills dominance descendants inside LOOP of the basic block BB into
1033 array TOVISIT from index *TV. */
1036 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
1037 basic_block
*tovisit
, int *tv
)
1039 basic_block son
, postpone
= NULL
;
1041 tovisit
[(*tv
)++] = bb
;
1042 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1044 son
= next_dom_son (CDI_DOMINATORS
, son
))
1046 if (!flow_bb_inside_loop_p (loop
, son
))
1049 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
1054 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
1058 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
1061 /* Gets body of a LOOP (that must be different from the outermost loop)
1062 sorted by dominance relation. Additionally, if a basic block s dominates
1063 the latch, then only blocks dominated by s are be after it. */
1066 get_loop_body_in_dom_order (const struct loop
*loop
)
1068 basic_block
*tovisit
;
1071 if (!loop
->num_nodes
)
1074 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1076 if (loop
->latch
== EXIT_BLOCK_PTR
)
1080 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
1082 if (tv
!= (int) loop
->num_nodes
)
1088 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1090 get_loop_exit_edges (const struct loop
*loop
, unsigned int *n_edges
)
1096 if (loop
->latch
== EXIT_BLOCK_PTR
)
1099 body
= get_loop_body (loop
);
1101 for (i
= 0; i
< loop
->num_nodes
; i
++)
1102 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
1103 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1105 edges
= xmalloc (n
* sizeof (edge
));
1108 for (i
= 0; i
< loop
->num_nodes
; i
++)
1109 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
1110 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1117 /* Counts the number of conditional branches inside LOOP. */
1120 num_loop_branches (const struct loop
*loop
)
1125 if (loop
->latch
== EXIT_BLOCK_PTR
)
1128 body
= get_loop_body (loop
);
1130 for (i
= 0; i
< loop
->num_nodes
; i
++)
1131 if (body
[i
]->succ
&& body
[i
]->succ
->succ_next
)
1138 /* Adds basic block BB to LOOP. */
1140 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1144 bb
->loop_father
= loop
;
1145 bb
->loop_depth
= loop
->depth
;
1147 for (i
= 0; i
< loop
->depth
; i
++)
1148 loop
->pred
[i
]->num_nodes
++;
1151 /* Remove basic block BB from loops. */
1153 remove_bb_from_loops (basic_block bb
)
1156 struct loop
*loop
= bb
->loop_father
;
1159 for (i
= 0; i
< loop
->depth
; i
++)
1160 loop
->pred
[i
]->num_nodes
--;
1161 bb
->loop_father
= NULL
;
1165 /* Finds nearest common ancestor in loop tree for given loops. */
1167 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1169 if (!loop_s
) return loop_d
;
1170 if (!loop_d
) return loop_s
;
1172 if (loop_s
->depth
< loop_d
->depth
)
1173 loop_d
= loop_d
->pred
[loop_s
->depth
];
1174 else if (loop_s
->depth
> loop_d
->depth
)
1175 loop_s
= loop_s
->pred
[loop_d
->depth
];
1177 while (loop_s
!= loop_d
)
1179 loop_s
= loop_s
->outer
;
1180 loop_d
= loop_d
->outer
;
1185 /* Cancels the LOOP; it must be innermost one. */
1187 cancel_loop (struct loops
*loops
, struct loop
*loop
)
1195 /* Move blocks up one level (they should be removed as soon as possible). */
1196 bbs
= get_loop_body (loop
);
1197 for (i
= 0; i
< loop
->num_nodes
; i
++)
1198 bbs
[i
]->loop_father
= loop
->outer
;
1200 /* Remove the loop from structure. */
1201 flow_loop_tree_node_remove (loop
);
1203 /* Remove loop from loops array. */
1204 loops
->parray
[loop
->num
] = NULL
;
1206 /* Free loop data. */
1207 flow_loop_free (loop
);
1210 /* Cancels LOOP and all its subloops. */
1212 cancel_loop_tree (struct loops
*loops
, struct loop
*loop
)
1215 cancel_loop_tree (loops
, loop
->inner
);
1216 cancel_loop (loops
, loop
);
1219 /* Checks that LOOPS are all right:
1220 -- sizes of loops are all right
1221 -- results of get_loop_body really belong to the loop
1222 -- loop header have just single entry edge and single latch edge
1223 -- loop latches have only single successor that is header of their loop
1224 -- irreducible loops are correctly marked
1227 verify_loop_structure (struct loops
*loops
)
1229 unsigned *sizes
, i
, j
;
1231 basic_block
*bbs
, bb
;
1237 sizes
= xcalloc (loops
->num
, sizeof (int));
1241 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1244 for (i
= 0; i
< loops
->num
; i
++)
1246 if (!loops
->parray
[i
])
1249 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1251 error ("Size of loop %d should be %d, not %d.",
1252 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1257 /* Check get_loop_body. */
1258 for (i
= 1; i
< loops
->num
; i
++)
1260 loop
= loops
->parray
[i
];
1263 bbs
= get_loop_body (loop
);
1265 for (j
= 0; j
< loop
->num_nodes
; j
++)
1266 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1268 error ("Bb %d do not belong to loop %d.",
1275 /* Check headers and latches. */
1276 for (i
= 1; i
< loops
->num
; i
++)
1278 loop
= loops
->parray
[i
];
1282 if ((loops
->state
& LOOPS_HAVE_PREHEADERS
)
1283 && (!loop
->header
->pred
->pred_next
1284 || loop
->header
->pred
->pred_next
->pred_next
))
1286 error ("Loop %d's header does not have exactly 2 entries.", i
);
1289 if (loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1291 if (!loop
->latch
->succ
1292 || loop
->latch
->succ
->succ_next
)
1294 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1297 if (loop
->latch
->succ
->dest
!= loop
->header
)
1299 error ("Loop %d's latch does not have header as successor.", i
);
1302 if (loop
->latch
->loop_father
!= loop
)
1304 error ("Loop %d's latch does not belong directly to it.", i
);
1308 if (loop
->header
->loop_father
!= loop
)
1310 error ("Loop %d's header does not belong directly to it.", i
);
1313 if ((loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1314 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1316 error ("Loop %d's latch is marked as part of irreducible region.", i
);
1321 /* Check irreducible loops. */
1322 if (loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1324 /* Record old info. */
1325 irreds
= sbitmap_alloc (last_basic_block
);
1328 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1329 SET_BIT (irreds
, bb
->index
);
1331 RESET_BIT (irreds
, bb
->index
);
1332 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1333 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1334 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1338 mark_irreducible_loops (loops
);
1343 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1344 && !TEST_BIT (irreds
, bb
->index
))
1346 error ("Basic block %d should be marked irreducible.", bb
->index
);
1349 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1350 && TEST_BIT (irreds
, bb
->index
))
1352 error ("Basic block %d should not be marked irreducible.", bb
->index
);
1355 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1357 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1358 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1360 error ("Edge from %d to %d should be marked irreducible.",
1361 e
->src
->index
, e
->dest
->index
);
1364 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1365 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1367 error ("Edge from %d to %d should not be marked irreducible.",
1368 e
->src
->index
, e
->dest
->index
);
1371 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1377 /* Check the single_exit. */
1378 if (loops
->state
& LOOPS_HAVE_MARKED_SINGLE_EXITS
)
1380 memset (sizes
, 0, sizeof (unsigned) * loops
->num
);
1383 if (bb
->loop_father
== loops
->tree_root
)
1385 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1387 if (e
->dest
== EXIT_BLOCK_PTR
)
1390 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1393 for (loop
= bb
->loop_father
;
1394 loop
!= e
->dest
->loop_father
;
1398 if (loop
->single_exit
1399 && loop
->single_exit
!= e
)
1401 error ("Wrong single exit %d->%d recorded for loop %d.",
1402 loop
->single_exit
->src
->index
,
1403 loop
->single_exit
->dest
->index
,
1405 error ("Right exit is %d->%d.",
1406 e
->src
->index
, e
->dest
->index
);
1413 for (i
= 1; i
< loops
->num
; i
++)
1415 loop
= loops
->parray
[i
];
1420 && !loop
->single_exit
)
1422 error ("Single exit not recorded for loop %d.", loop
->num
);
1427 && loop
->single_exit
)
1429 error ("Loop %d should not have single exit (%d -> %d).",
1431 loop
->single_exit
->src
->index
,
1432 loop
->single_exit
->dest
->index
);
1444 /* Returns latch edge of LOOP. */
1446 loop_latch_edge (const struct loop
*loop
)
1450 for (e
= loop
->header
->pred
; e
->src
!= loop
->latch
; e
= e
->pred_next
)
1456 /* Returns preheader edge of LOOP. */
1458 loop_preheader_edge (const struct loop
*loop
)
1462 for (e
= loop
->header
->pred
; e
->src
== loop
->latch
; e
= e
->pred_next
)