1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001 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"
30 /* Ratio of frequencies of edges so that one of more latch edges is
31 considered to belong to inner loop with same header. */
32 #define HEAVY_EDGE_RATIO 8
34 static void flow_loops_cfg_dump
PARAMS ((const struct loops
*,
36 static void flow_loop_entry_edges_find
PARAMS ((struct loop
*));
37 static void flow_loop_exit_edges_find
PARAMS ((struct loop
*));
38 static int flow_loop_nodes_find
PARAMS ((basic_block
, struct loop
*));
39 static void flow_loop_pre_header_scan
PARAMS ((struct loop
*));
40 static basic_block flow_loop_pre_header_find
PARAMS ((basic_block
,
42 static int flow_loop_level_compute
PARAMS ((struct loop
*));
43 static int flow_loops_level_compute
PARAMS ((struct loops
*));
44 static basic_block make_forwarder_block
PARAMS ((basic_block
, int, int,
46 static void canonicalize_loop_headers
PARAMS ((void));
47 static bool glb_enum_p
PARAMS ((basic_block
, void *));
48 static void redirect_edge_with_latch_update
PARAMS ((edge
, basic_block
));
49 static void flow_loop_free
PARAMS ((struct loop
*));
51 /* Dump loop related CFG information. */
54 flow_loops_cfg_dump (loops
, file
)
55 const struct loops
*loops
;
61 if (! loops
->num
|| ! file
|| ! loops
->cfg
.dom
)
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 (outer
, loop
)
99 const struct loop
*outer
;
100 const struct loop
*loop
;
102 return loop
->depth
> outer
->depth
103 && loop
->pred
[outer
->depth
] == outer
;
106 /* Dump the loop information specified by LOOP to the stream FILE
107 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
110 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
)
111 const struct loop
*loop
;
113 void (*loop_dump_aux
) PARAMS((const struct loop
*, FILE *, int));
119 if (! loop
|| ! loop
->header
)
122 fprintf (file
, ";;\n;; Loop %d:%s\n", loop
->num
,
123 loop
->invalid
? " invalid" : "");
125 fprintf (file
, ";; header %d, latch %d, pre-header %d\n",
126 loop
->header
->index
, loop
->latch
->index
,
127 loop
->pre_header
? loop
->pre_header
->index
: -1);
128 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
129 loop
->depth
, loop
->level
,
130 (long) (loop
->outer
? loop
->outer
->num
: -1));
132 if (loop
->pre_header_edges
)
133 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
134 loop
->num_pre_header_edges
, file
);
136 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
137 loop
->num_entries
, file
);
138 fprintf (file
, ";; nodes:");
139 bbs
= get_loop_body (loop
);
140 for (i
= 0; i
< loop
->num_nodes
; i
++)
141 fprintf (file
, " %d", bbs
[i
]->index
);
143 fprintf (file
, "\n");
144 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
145 loop
->num_exits
, file
);
148 loop_dump_aux (loop
, file
, verbose
);
151 /* Dump the loop information specified by LOOPS to the stream FILE,
152 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
155 flow_loops_dump (loops
, file
, loop_dump_aux
, verbose
)
156 const struct loops
*loops
;
158 void (*loop_dump_aux
) PARAMS((const struct loop
*, FILE *, int));
164 num_loops
= loops
->num
;
165 if (! num_loops
|| ! file
)
168 fprintf (file
, ";; %d loops found, %d levels\n",
169 num_loops
, loops
->levels
);
171 for (i
= 0; i
< num_loops
; i
++)
173 struct loop
*loop
= loops
->parray
[i
];
178 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
182 flow_loops_cfg_dump (loops
, file
);
185 /* Free data allocated for LOOP. */
187 flow_loop_free (loop
)
190 if (loop
->pre_header_edges
)
191 free (loop
->pre_header_edges
);
192 if (loop
->entry_edges
)
193 free (loop
->entry_edges
);
194 if (loop
->exit_edges
)
195 free (loop
->exit_edges
);
201 /* Free all the memory allocated for LOOPS. */
204 flow_loops_free (loops
)
214 /* Free the loop descriptors. */
215 for (i
= 0; i
< loops
->num
; i
++)
217 struct loop
*loop
= loops
->parray
[i
];
222 flow_loop_free (loop
);
225 free (loops
->parray
);
226 loops
->parray
= NULL
;
229 free_dominance_info (loops
->cfg
.dom
);
231 if (loops
->cfg
.dfs_order
)
232 free (loops
->cfg
.dfs_order
);
233 if (loops
->cfg
.rc_order
)
234 free (loops
->cfg
.rc_order
);
239 /* Find the entry edges into the LOOP. */
242 flow_loop_entry_edges_find (loop
)
249 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
251 if (flow_loop_outside_edge_p (loop
, e
))
258 loop
->entry_edges
= (edge
*) xmalloc (num_entries
* sizeof (edge
*));
261 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
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 (loop
)
277 basic_block node
, *bbs
;
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
= (edge
*) 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 (header
, loop
)
337 header
->loop_father
= loop
;
338 header
->loop_depth
= loop
->depth
;
340 if (loop
->latch
->loop_father
!= loop
)
342 stack
= (basic_block
*) xmalloc (n_basic_blocks
* sizeof (basic_block
));
345 stack
[sp
++] = loop
->latch
;
346 loop
->latch
->loop_father
= loop
;
347 loop
->latch
->loop_depth
= loop
->depth
;
356 for (e
= node
->pred
; e
; e
= e
->pred_next
)
358 basic_block ancestor
= e
->src
;
360 if (ancestor
!= ENTRY_BLOCK_PTR
361 && ancestor
->loop_father
!= loop
)
363 ancestor
->loop_father
= loop
;
364 ancestor
->loop_depth
= loop
->depth
;
366 stack
[sp
++] = ancestor
;
375 /* Find the root node of the loop pre-header extended basic block and
376 the edges along the trace from the root node to the loop header. */
379 flow_loop_pre_header_scan (loop
)
386 loop
->num_pre_header_edges
= 0;
387 if (loop
->num_entries
!= 1)
390 ebb
= loop
->entry_edges
[0]->src
;
391 if (ebb
== ENTRY_BLOCK_PTR
)
394 /* Count number of edges along trace from loop header to
395 root of pre-header extended basic block. Usually this is
396 only one or two edges. */
397 for (num
= 1; ebb
->pred
->src
!= ENTRY_BLOCK_PTR
&& ! ebb
->pred
->pred_next
;
399 ebb
= ebb
->pred
->src
;
401 loop
->pre_header_edges
= (edge
*) xmalloc (num
* sizeof (edge
));
402 loop
->num_pre_header_edges
= num
;
404 /* Store edges in order that they are followed. The source of the first edge
405 is the root node of the pre-header extended basic block and the
406 destination of the last last edge is the loop header. */
407 for (e
= loop
->entry_edges
[0]; num
; e
= e
->src
->pred
)
408 loop
->pre_header_edges
[--num
] = e
;
411 /* Return the block for the pre-header of the loop with header
412 HEADER where DOM specifies the dominator information. Return NULL if
413 there is no pre-header. */
416 flow_loop_pre_header_find (header
, dom
)
420 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 (e
= header
->pred
; e
; e
= e
->pred_next
)
428 basic_block node
= e
->src
;
430 if (node
!= ENTRY_BLOCK_PTR
431 && ! dominated_by_p (dom
, 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. */
448 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
452 flow_loop_tree_node_add (father
, loop
)
456 loop
->next
= father
->inner
;
457 father
->inner
= loop
;
458 loop
->outer
= father
;
460 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
;
466 /* Remove LOOP from the loop hierarchy tree. */
469 flow_loop_tree_node_remove (loop
)
472 struct loop
*prev
, *father
;
474 father
= loop
->outer
;
477 /* Remove loop from the list of sons. */
478 if (father
->inner
== loop
)
479 father
->inner
= loop
->next
;
482 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
483 prev
->next
= loop
->next
;
491 /* Helper function to compute loop nesting depth and enclosed loop level
492 for the natural loop specified by LOOP. Returns the loop level. */
495 flow_loop_level_compute (loop
)
504 /* Traverse loop tree assigning depth and computing level as the
505 maximum level of all the inner loops of this loop. The loop
506 level is equivalent to the height of the loop in the loop tree
507 and corresponds to the number of enclosed loop levels (including
509 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
511 int ilevel
= flow_loop_level_compute (inner
) + 1;
521 /* Compute the loop nesting depth and enclosed loop level for the loop
522 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
526 flow_loops_level_compute (loops
)
529 return flow_loop_level_compute (loops
->tree_root
);
532 /* Scan a single natural loop specified by LOOP collecting information
533 about it specified by FLAGS. */
536 flow_loop_scan (loops
, loop
, flags
)
541 if (flags
& LOOP_ENTRY_EDGES
)
543 /* Find edges which enter the loop header.
544 Note that the entry edges should only
545 enter the header of a natural loop. */
546 flow_loop_entry_edges_find (loop
);
549 if (flags
& LOOP_EXIT_EDGES
)
551 /* Find edges which exit the loop. */
552 flow_loop_exit_edges_find (loop
);
555 if (flags
& LOOP_PRE_HEADER
)
557 /* Look to see if the loop has a pre-header node. */
559 = flow_loop_pre_header_find (loop
->header
, loops
->cfg
.dom
);
561 /* Find the blocks within the extended basic block of
562 the loop pre-header. */
563 flow_loop_pre_header_scan (loop
);
569 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
570 #define LATCH_EDGE(E) (*(int *) (E)->aux)
572 /* Redirect edge and update latch and header info. */
574 redirect_edge_with_latch_update (e
, to
)
580 jump
= redirect_edge_and_branch_force (e
, to
);
583 alloc_aux_for_block (jump
, sizeof (int));
584 HEADER_BLOCK (jump
) = 0;
585 alloc_aux_for_edge (jump
->pred
, sizeof (int));
586 LATCH_EDGE (jump
->succ
) = LATCH_EDGE (e
);
587 LATCH_EDGE (jump
->pred
) = 0;
591 /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
592 marked as latch into entry part, analogically for REDIRECT_NONLATCH.
593 In both of these cases, ignore edge EXCEPT. If CONN_LATCH, set edge
594 between created entry part and BB as latch one. Return created entry
598 make_forwarder_block (bb
, redirect_latch
, redirect_nonlatch
, except
,
602 int redirect_nonlatch
;
606 edge e
, next_e
, fallthru
;
610 insn
= PREV_INSN (first_insn_after_basic_block_note (bb
));
612 fallthru
= split_block (bb
, insn
);
613 dummy
= fallthru
->src
;
616 bb
->aux
= xmalloc (sizeof (int));
617 HEADER_BLOCK (dummy
) = 0;
618 HEADER_BLOCK (bb
) = 1;
620 /* Redirect back edges we want to keep. */
621 for (e
= dummy
->pred
; e
; e
= next_e
)
623 next_e
= e
->pred_next
;
625 || !((redirect_latch
&& LATCH_EDGE (e
))
626 || (redirect_nonlatch
&& !LATCH_EDGE (e
))))
628 dummy
->frequency
-= EDGE_FREQUENCY (e
);
629 dummy
->count
-= e
->count
;
630 if (dummy
->frequency
< 0)
631 dummy
->frequency
= 0;
632 if (dummy
->count
< 0)
634 redirect_edge_with_latch_update (e
, bb
);
638 alloc_aux_for_edge (fallthru
, sizeof (int));
639 LATCH_EDGE (fallthru
) = conn_latch
;
644 /* Takes care of merging natural loops with shared headers. */
646 canonicalize_loop_headers ()
652 /* Compute the dominators. */
653 dom
= calculate_dominance_info (CDI_DOMINATORS
);
655 alloc_aux_for_blocks (sizeof (int));
656 alloc_aux_for_edges (sizeof (int));
658 /* Split blocks so that each loop has only single latch. */
662 int have_abnormal_edge
= 0;
664 for (e
= header
->pred
; e
; e
= e
->pred_next
)
666 basic_block latch
= e
->src
;
668 if (e
->flags
& EDGE_ABNORMAL
)
669 have_abnormal_edge
= 1;
671 if (latch
!= ENTRY_BLOCK_PTR
672 && dominated_by_p (dom
, latch
, header
))
678 if (have_abnormal_edge
)
679 HEADER_BLOCK (header
) = 0;
681 HEADER_BLOCK (header
) = num_latches
;
684 if (HEADER_BLOCK (ENTRY_BLOCK_PTR
->succ
->dest
))
688 /* We could not redirect edges freely here. On the other hand,
689 we can simply split the edge from entry block. */
690 bb
= split_edge (ENTRY_BLOCK_PTR
->succ
);
692 alloc_aux_for_edge (bb
->succ
, sizeof (int));
693 LATCH_EDGE (bb
->succ
) = 0;
694 alloc_aux_for_block (bb
, sizeof (int));
695 HEADER_BLOCK (bb
) = 0;
702 int max_freq
, is_heavy
;
705 if (!HEADER_BLOCK (header
))
708 num_latch
= HEADER_BLOCK (header
);
710 want_join_latch
= (num_latch
> 1);
712 if (!want_join_latch
)
715 /* Find a heavy edge. */
719 for (e
= header
->pred
; e
; e
= e
->pred_next
)
720 if (LATCH_EDGE (e
) &&
721 EDGE_FREQUENCY (e
) > max_freq
)
722 max_freq
= EDGE_FREQUENCY (e
);
723 for (e
= header
->pred
; e
; e
= e
->pred_next
)
724 if (LATCH_EDGE (e
) &&
725 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
738 basic_block new_header
=
739 make_forwarder_block (header
, true, true, heavy
, 0);
741 make_forwarder_block (new_header
, true, false, NULL
, 1);
744 make_forwarder_block (header
, true, false, NULL
, 1);
747 free_aux_for_blocks ();
748 free_aux_for_edges ();
749 free_dominance_info (dom
);
752 /* Find all the natural loops in the function and save in LOOPS structure and
753 recalculate loop_depth information in basic block structures. FLAGS
754 controls which loop information is collected. Return the number of natural
758 flow_loops_find (loops
, flags
)
773 /* This function cannot be repeatedly called with different
774 flags to build up the loop information. The loop tree
775 must always be built if this function is called. */
776 if (! (flags
& LOOP_TREE
))
779 memset (loops
, 0, sizeof *loops
);
781 /* Taking care of this degenerate case makes the rest of
782 this code simpler. */
783 if (n_basic_blocks
== 0)
789 /* Join loops with shared headers. */
790 canonicalize_loop_headers ();
792 /* Compute the dominators. */
793 dom
= loops
->cfg
.dom
= calculate_dominance_info (CDI_DOMINATORS
);
795 /* Count the number of loop headers. This should be the
796 same as the number of natural loops. */
797 headers
= sbitmap_alloc (last_basic_block
);
798 sbitmap_zero (headers
);
803 int more_latches
= 0;
805 header
->loop_depth
= 0;
807 /* If we have an abnormal predecessor, do not consider the
808 loop (not worth the problems). */
809 for (e
= header
->pred
; e
; e
= e
->pred_next
)
810 if (e
->flags
& EDGE_ABNORMAL
)
815 for (e
= header
->pred
; e
; e
= e
->pred_next
)
817 basic_block latch
= e
->src
;
819 if (e
->flags
& EDGE_ABNORMAL
)
822 /* Look for back edges where a predecessor is dominated
823 by this block. A natural loop has a single entry
824 node (header) that dominates all the nodes in the
825 loop. It also has single back edge to the header
826 from a latch node. */
827 if (latch
!= ENTRY_BLOCK_PTR
&& dominated_by_p (dom
, latch
, header
))
829 /* Shared headers should be eliminated by now. */
833 SET_BIT (headers
, header
->index
);
839 /* Allocate loop structures. */
840 loops
->parray
= (struct loop
**) xcalloc (num_loops
+ 1, sizeof (struct loop
*));
842 /* Dummy loop containing whole function. */
843 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
844 loops
->parray
[0]->next
= NULL
;
845 loops
->parray
[0]->inner
= NULL
;
846 loops
->parray
[0]->outer
= NULL
;
847 loops
->parray
[0]->depth
= 0;
848 loops
->parray
[0]->pred
= NULL
;
849 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
850 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
851 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
852 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
853 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
855 loops
->tree_root
= loops
->parray
[0];
857 /* Find and record information about all the natural loops
861 bb
->loop_father
= loops
->tree_root
;
865 /* Compute depth first search order of the CFG so that outer
866 natural loops will be found before inner natural loops. */
867 dfs_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
868 rc_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
869 flow_depth_first_order_compute (dfs_order
, rc_order
);
871 /* Save CFG derived information to avoid recomputing it. */
872 loops
->cfg
.dom
= dom
;
873 loops
->cfg
.dfs_order
= dfs_order
;
874 loops
->cfg
.rc_order
= rc_order
;
878 for (b
= 0; b
< n_basic_blocks
; b
++)
882 /* Search the nodes of the CFG in reverse completion order
883 so that we can find outer loops first. */
884 if (!TEST_BIT (headers
, rc_order
[b
]))
887 header
= BASIC_BLOCK (rc_order
[b
]);
889 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
891 loop
->header
= header
;
892 loop
->num
= num_loops
;
895 /* Look for the latch for this header block. */
896 for (e
= header
->pred
; e
; e
= e
->pred_next
)
898 basic_block latch
= e
->src
;
900 if (latch
!= ENTRY_BLOCK_PTR
901 && dominated_by_p (dom
, latch
, header
))
908 flow_loop_tree_node_add (header
->loop_father
, loop
);
909 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
912 sbitmap_free (headers
);
914 /* Assign the loop nesting depth and enclosed loop level for each
916 loops
->levels
= flow_loops_level_compute (loops
);
918 /* Scan the loops. */
919 for (i
= 1; i
< num_loops
; i
++)
920 flow_loop_scan (loops
, loops
->parray
[i
], flags
);
922 loops
->num
= num_loops
;
926 loops
->cfg
.dom
= NULL
;
927 free_dominance_info (dom
);
929 #ifdef ENABLE_CHECKING
931 verify_loop_structure (loops
, 0);
937 /* Update the information regarding the loops in the CFG
938 specified by LOOPS. */
941 flow_loops_update (loops
, flags
)
945 /* One day we may want to update the current loop data. For now
946 throw away the old stuff and rebuild what we need. */
948 flow_loops_free (loops
);
950 return flow_loops_find (loops
, flags
);
953 /* Return nonzero if basic block BB belongs to LOOP. */
955 flow_bb_inside_loop_p (loop
, bb
)
956 const struct loop
*loop
;
957 const basic_block bb
;
959 struct loop
*source_loop
;
961 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
964 source_loop
= bb
->loop_father
;
965 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
968 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
971 flow_loop_outside_edge_p (loop
, e
)
972 const struct loop
*loop
;
975 if (e
->dest
!= loop
->header
)
977 return !flow_bb_inside_loop_p (loop
, e
->src
);
980 /* Enumeration predicate for get_loop_body. */
982 glb_enum_p (bb
, glb_header
)
986 return bb
!= (basic_block
) glb_header
;
989 /* Gets basic blocks of a loop. */
992 const struct loop
*loop
;
994 basic_block
*tovisit
, bb
;
997 if (!loop
->num_nodes
)
1000 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
1001 tovisit
[tv
++] = loop
->header
;
1003 if (loop
->latch
== EXIT_BLOCK_PTR
)
1005 /* There may be blocks unreachable from EXIT_BLOCK. */
1006 if (loop
->num_nodes
!= n_basic_blocks
+ 2)
1010 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
1012 else if (loop
->latch
!= loop
->header
)
1014 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
1015 tovisit
+ 1, loop
->num_nodes
- 1,
1019 if (tv
!= loop
->num_nodes
)
1024 /* Adds basic block BB to LOOP. */
1026 add_bb_to_loop (bb
, loop
)
1032 bb
->loop_father
= loop
;
1033 bb
->loop_depth
= loop
->depth
;
1035 for (i
= 0; i
< loop
->depth
; i
++)
1036 loop
->pred
[i
]->num_nodes
++;
1039 /* Remove basic block BB from loops. */
1041 remove_bb_from_loops (bb
)
1045 struct loop
*loop
= bb
->loop_father
;
1048 for (i
= 0; i
< loop
->depth
; i
++)
1049 loop
->pred
[i
]->num_nodes
--;
1050 bb
->loop_father
= NULL
;
1054 /* Finds nearest common ancestor in loop tree for given loops. */
1056 find_common_loop (loop_s
, loop_d
)
1057 struct loop
*loop_s
;
1058 struct loop
*loop_d
;
1060 if (!loop_s
) return loop_d
;
1061 if (!loop_d
) return loop_s
;
1063 if (loop_s
->depth
< loop_d
->depth
)
1064 loop_d
= loop_d
->pred
[loop_s
->depth
];
1065 else if (loop_s
->depth
> loop_d
->depth
)
1066 loop_s
= loop_s
->pred
[loop_d
->depth
];
1068 while (loop_s
!= loop_d
)
1070 loop_s
= loop_s
->outer
;
1071 loop_d
= loop_d
->outer
;
1076 /* Checks that LOOPS are allright:
1077 -- sizes of loops are allright
1078 -- results of get_loop_body really belong to the loop
1079 -- loop header have just single entry edge and single latch edge
1080 -- loop latches have only single successor that is header of their loop
1083 verify_loop_structure (loops
, flags
)
1084 struct loops
*loops
;
1088 basic_block
*bbs
, bb
;
1093 sizes
= xcalloc (loops
->num
, sizeof (int));
1097 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1100 for (i
= 0; i
< loops
->num
; i
++)
1102 if (!loops
->parray
[i
])
1105 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1107 error ("Size of loop %d should be %d, not %d.",
1108 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1115 /* Check get_loop_body. */
1116 for (i
= 1; i
< loops
->num
; i
++)
1118 loop
= loops
->parray
[i
];
1121 bbs
= get_loop_body (loop
);
1123 for (j
= 0; j
< loop
->num_nodes
; j
++)
1124 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1126 error ("Bb %d do not belong to loop %d.",
1133 /* Check headers and latches. */
1134 for (i
= 1; i
< loops
->num
; i
++)
1136 loop
= loops
->parray
[i
];
1140 if ((flags
& VLS_EXPECT_PREHEADERS
)
1141 && (!loop
->header
->pred
->pred_next
1142 || loop
->header
->pred
->pred_next
->pred_next
))
1144 error ("Loop %d's header does not have exactly 2 entries.", i
);
1147 if (flags
& VLS_EXPECT_SIMPLE_LATCHES
)
1149 if (!loop
->latch
->succ
1150 || loop
->latch
->succ
->succ_next
)
1152 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1155 if (loop
->latch
->succ
->dest
!= loop
->header
)
1157 error ("Loop %d's latch does not have header as successor.", i
);
1160 if (loop
->latch
->loop_father
!= loop
)
1162 error ("Loop %d's latch does not belong directly to it.", i
);
1166 if (loop
->header
->loop_father
!= loop
)
1168 error ("Loop %d's header does not belong directly to it.", i
);
1177 /* Returns latch edge of LOOP. */
1179 loop_latch_edge (loop
)
1184 for (e
= loop
->header
->pred
; e
->src
!= loop
->latch
; e
= e
->pred_next
)
1190 /* Returns preheader edge of LOOP. */
1192 loop_preheader_edge (loop
)
1197 for (e
= loop
->header
->pred
; e
->src
== loop
->latch
; e
= e
->pred_next
)