1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003 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 /* Ratio of frequencies of edges so that one of more latch edges is
33 considered to belong to inner loop with same header. */
34 #define HEAVY_EDGE_RATIO 8
36 static void flow_loops_cfg_dump (const struct loops
*, FILE *);
37 static void flow_loop_entry_edges_find (struct loop
*);
38 static void flow_loop_exit_edges_find (struct loop
*);
39 static int flow_loop_nodes_find (basic_block
, struct loop
*);
40 static void flow_loop_pre_header_scan (struct loop
*);
41 static basic_block
flow_loop_pre_header_find (basic_block
, dominance_info
);
42 static int flow_loop_level_compute (struct loop
*);
43 static int flow_loops_level_compute (struct loops
*);
44 static void establish_preds (struct loop
*);
45 static basic_block
make_forwarder_block (basic_block
, int, int, edge
, int);
46 static void canonicalize_loop_headers (void);
47 static bool glb_enum_p (basic_block
, void *);
48 static void redirect_edge_with_latch_update (edge
, basic_block
);
50 /* Dump loop related CFG information. */
53 flow_loops_cfg_dump (const struct loops
*loops
, FILE *file
)
58 if (! loops
->num
|| ! file
|| ! loops
->cfg
.dom
)
65 fprintf (file
, ";; %d succs { ", bb
->index
);
66 for (succ
= bb
->succ
; succ
; succ
= succ
->succ_next
)
67 fprintf (file
, "%d ", succ
->dest
->index
);
68 fprintf (file
, "}\n");
71 /* Dump the DFS node order. */
72 if (loops
->cfg
.dfs_order
)
74 fputs (";; DFS order: ", file
);
75 for (i
= 0; i
< n_basic_blocks
; i
++)
76 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
81 /* Dump the reverse completion node order. */
82 if (loops
->cfg
.rc_order
)
84 fputs (";; RC order: ", file
);
85 for (i
= 0; i
< n_basic_blocks
; i
++)
86 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
92 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
95 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
97 return loop
->depth
> outer
->depth
98 && loop
->pred
[outer
->depth
] == outer
;
101 /* Dump the loop information specified by LOOP to the stream FILE
102 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
105 flow_loop_dump (const struct loop
*loop
, FILE *file
,
106 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
112 if (! loop
|| ! loop
->header
)
115 fprintf (file
, ";;\n;; Loop %d:%s\n", loop
->num
,
116 loop
->invalid
? " invalid" : "");
118 fprintf (file
, ";; header %d, latch %d, pre-header %d\n",
119 loop
->header
->index
, loop
->latch
->index
,
120 loop
->pre_header
? loop
->pre_header
->index
: -1);
121 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
122 loop
->depth
, loop
->level
,
123 (long) (loop
->outer
? loop
->outer
->num
: -1));
125 if (loop
->pre_header_edges
)
126 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
127 loop
->num_pre_header_edges
, file
);
129 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
130 loop
->num_entries
, file
);
131 fprintf (file
, ";; nodes:");
132 bbs
= get_loop_body (loop
);
133 for (i
= 0; i
< loop
->num_nodes
; i
++)
134 fprintf (file
, " %d", bbs
[i
]->index
);
136 fprintf (file
, "\n");
137 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
138 loop
->num_exits
, file
);
141 loop_dump_aux (loop
, file
, verbose
);
144 /* Dump the loop information specified by LOOPS to the stream FILE,
145 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
148 flow_loops_dump (const struct loops
*loops
, FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
153 num_loops
= loops
->num
;
154 if (! num_loops
|| ! file
)
157 fprintf (file
, ";; %d loops found, %d levels\n",
158 num_loops
, loops
->levels
);
160 for (i
= 0; i
< num_loops
; i
++)
162 struct loop
*loop
= loops
->parray
[i
];
167 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
171 flow_loops_cfg_dump (loops
, file
);
174 /* Free data allocated for LOOP. */
176 flow_loop_free (struct loop
*loop
)
178 if (loop
->pre_header_edges
)
179 free (loop
->pre_header_edges
);
180 if (loop
->entry_edges
)
181 free (loop
->entry_edges
);
182 if (loop
->exit_edges
)
183 free (loop
->exit_edges
);
189 /* Free all the memory allocated for LOOPS. */
192 flow_loops_free (struct loops
*loops
)
201 /* Free the loop descriptors. */
202 for (i
= 0; i
< loops
->num
; i
++)
204 struct loop
*loop
= loops
->parray
[i
];
209 flow_loop_free (loop
);
212 free (loops
->parray
);
213 loops
->parray
= NULL
;
216 free_dominance_info (loops
->cfg
.dom
);
218 if (loops
->cfg
.dfs_order
)
219 free (loops
->cfg
.dfs_order
);
220 if (loops
->cfg
.rc_order
)
221 free (loops
->cfg
.rc_order
);
226 /* Find the entry edges into the LOOP. */
229 flow_loop_entry_edges_find (struct loop
*loop
)
235 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
237 if (flow_loop_outside_edge_p (loop
, e
))
244 loop
->entry_edges
= xmalloc (num_entries
* sizeof (edge
*));
247 for (e
= loop
->header
->pred
; e
; e
= e
->pred_next
)
249 if (flow_loop_outside_edge_p (loop
, e
))
250 loop
->entry_edges
[num_entries
++] = e
;
253 loop
->num_entries
= num_entries
;
256 /* Find the exit edges from the LOOP. */
259 flow_loop_exit_edges_find (struct loop
*loop
)
262 basic_block node
, *bbs
;
263 unsigned num_exits
, i
;
265 loop
->exit_edges
= NULL
;
268 /* Check all nodes within the loop to see if there are any
269 successors not in the loop. Note that a node may have multiple
272 bbs
= get_loop_body (loop
);
273 for (i
= 0; i
< loop
->num_nodes
; i
++)
276 for (e
= node
->succ
; e
; e
= e
->succ_next
)
278 basic_block dest
= e
->dest
;
280 if (!flow_bb_inside_loop_p (loop
, dest
))
291 loop
->exit_edges
= xmalloc (num_exits
* sizeof (edge
*));
293 /* Store all exiting edges into an array. */
295 for (i
= 0; i
< loop
->num_nodes
; i
++)
298 for (e
= node
->succ
; e
; e
= e
->succ_next
)
300 basic_block dest
= e
->dest
;
302 if (!flow_bb_inside_loop_p (loop
, dest
))
303 loop
->exit_edges
[num_exits
++] = e
;
307 loop
->num_exits
= num_exits
;
310 /* Find the nodes contained within the LOOP with header HEADER.
311 Return the number of nodes within the loop. */
314 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
320 header
->loop_father
= loop
;
321 header
->loop_depth
= loop
->depth
;
323 if (loop
->latch
->loop_father
!= loop
)
325 stack
= xmalloc (n_basic_blocks
* sizeof (basic_block
));
328 stack
[sp
++] = loop
->latch
;
329 loop
->latch
->loop_father
= loop
;
330 loop
->latch
->loop_depth
= loop
->depth
;
339 for (e
= node
->pred
; e
; e
= e
->pred_next
)
341 basic_block ancestor
= e
->src
;
343 if (ancestor
!= ENTRY_BLOCK_PTR
344 && ancestor
->loop_father
!= loop
)
346 ancestor
->loop_father
= loop
;
347 ancestor
->loop_depth
= loop
->depth
;
349 stack
[sp
++] = ancestor
;
358 /* Find the root node of the loop pre-header extended basic block and
359 the edges along the trace from the root node to the loop header. */
362 flow_loop_pre_header_scan (struct loop
*loop
)
368 loop
->num_pre_header_edges
= 0;
369 if (loop
->num_entries
!= 1)
372 ebb
= loop
->entry_edges
[0]->src
;
373 if (ebb
== ENTRY_BLOCK_PTR
)
376 /* Count number of edges along trace from loop header to
377 root of pre-header extended basic block. Usually this is
378 only one or two edges. */
379 for (num
= 1; ebb
->pred
->src
!= ENTRY_BLOCK_PTR
&& ! ebb
->pred
->pred_next
;
381 ebb
= ebb
->pred
->src
;
383 loop
->pre_header_edges
= xmalloc (num
* sizeof (edge
));
384 loop
->num_pre_header_edges
= num
;
386 /* Store edges in order that they are followed. The source of the first edge
387 is the root node of the pre-header extended basic block and the
388 destination of the last last edge is the loop header. */
389 for (e
= loop
->entry_edges
[0]; num
; e
= e
->src
->pred
)
390 loop
->pre_header_edges
[--num
] = e
;
393 /* Return the block for the pre-header of the loop with header
394 HEADER where DOM specifies the dominator information. Return NULL if
395 there is no pre-header. */
398 flow_loop_pre_header_find (basic_block header
, dominance_info dom
)
400 basic_block pre_header
;
403 /* If block p is a predecessor of the header and is the only block
404 that the header does not dominate, then it is the pre-header. */
406 for (e
= header
->pred
; e
; e
= e
->pred_next
)
408 basic_block node
= e
->src
;
410 if (node
!= ENTRY_BLOCK_PTR
411 && ! dominated_by_p (dom
, node
, header
))
413 if (pre_header
== NULL
)
417 /* There are multiple edges into the header from outside
418 the loop so there is no pre-header block. */
429 establish_preds (struct loop
*loop
)
431 struct loop
*ploop
, *father
= loop
->outer
;
433 loop
->depth
= father
->depth
+ 1;
436 loop
->pred
= xmalloc (sizeof (struct loop
*) * loop
->depth
);
437 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
438 loop
->pred
[father
->depth
] = father
;
440 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
441 establish_preds (ploop
);
444 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
445 added loop. If LOOP has some children, take care of that their
446 pred field will be initialized correctly. */
449 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
451 loop
->next
= father
->inner
;
452 father
->inner
= loop
;
453 loop
->outer
= father
;
455 establish_preds (loop
);
458 /* Remove LOOP from the loop hierarchy tree. */
461 flow_loop_tree_node_remove (struct loop
*loop
)
463 struct loop
*prev
, *father
;
465 father
= loop
->outer
;
468 /* Remove loop from the list of sons. */
469 if (father
->inner
== loop
)
470 father
->inner
= loop
->next
;
473 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
474 prev
->next
= loop
->next
;
482 /* Helper function to compute loop nesting depth and enclosed loop level
483 for the natural loop specified by LOOP. Returns the loop level. */
486 flow_loop_level_compute (struct loop
*loop
)
494 /* Traverse loop tree assigning depth and computing level as the
495 maximum level of all the inner loops of this loop. The loop
496 level is equivalent to the height of the loop in the loop tree
497 and corresponds to the number of enclosed loop levels (including
499 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
501 int ilevel
= flow_loop_level_compute (inner
) + 1;
511 /* Compute the loop nesting depth and enclosed loop level for the loop
512 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
516 flow_loops_level_compute (struct loops
*loops
)
518 return flow_loop_level_compute (loops
->tree_root
);
521 /* Scan a single natural loop specified by LOOP collecting information
522 about it specified by FLAGS. */
525 flow_loop_scan (struct loops
*loops
, struct loop
*loop
, int flags
)
527 if (flags
& LOOP_ENTRY_EDGES
)
529 /* Find edges which enter the loop header.
530 Note that the entry edges should only
531 enter the header of a natural loop. */
532 flow_loop_entry_edges_find (loop
);
535 if (flags
& LOOP_EXIT_EDGES
)
537 /* Find edges which exit the loop. */
538 flow_loop_exit_edges_find (loop
);
541 if (flags
& LOOP_PRE_HEADER
)
543 /* Look to see if the loop has a pre-header node. */
545 = flow_loop_pre_header_find (loop
->header
, loops
->cfg
.dom
);
547 /* Find the blocks within the extended basic block of
548 the loop pre-header. */
549 flow_loop_pre_header_scan (loop
);
555 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
556 #define LATCH_EDGE(E) (*(int *) (E)->aux)
558 /* Redirect edge and update latch and header info. */
560 redirect_edge_with_latch_update (edge e
, basic_block to
)
564 jump
= redirect_edge_and_branch_force (e
, to
);
567 alloc_aux_for_block (jump
, sizeof (int));
568 HEADER_BLOCK (jump
) = 0;
569 alloc_aux_for_edge (jump
->pred
, sizeof (int));
570 LATCH_EDGE (jump
->succ
) = LATCH_EDGE (e
);
571 LATCH_EDGE (jump
->pred
) = 0;
575 /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
576 marked as latch into entry part, analogically for REDIRECT_NONLATCH.
577 In both of these cases, ignore edge EXCEPT. If CONN_LATCH, set edge
578 between created entry part and BB as latch one. Return created entry
582 make_forwarder_block (basic_block bb
, int redirect_latch
, int redirect_nonlatch
, edge except
, int conn_latch
)
584 edge e
, next_e
, fallthru
;
588 insn
= PREV_INSN (first_insn_after_basic_block_note (bb
));
590 /* For empty block split_block will return NULL. */
592 emit_note_after (NOTE_INSN_DELETED
, insn
);
594 fallthru
= split_block (bb
, insn
);
595 dummy
= fallthru
->src
;
598 bb
->aux
= xmalloc (sizeof (int));
599 HEADER_BLOCK (dummy
) = 0;
600 HEADER_BLOCK (bb
) = 1;
602 /* Redirect back edges we want to keep. */
603 for (e
= dummy
->pred
; e
; e
= next_e
)
605 next_e
= e
->pred_next
;
607 || !((redirect_latch
&& LATCH_EDGE (e
))
608 || (redirect_nonlatch
&& !LATCH_EDGE (e
))))
610 dummy
->frequency
-= EDGE_FREQUENCY (e
);
611 dummy
->count
-= e
->count
;
612 if (dummy
->frequency
< 0)
613 dummy
->frequency
= 0;
614 if (dummy
->count
< 0)
616 redirect_edge_with_latch_update (e
, bb
);
620 alloc_aux_for_edge (fallthru
, sizeof (int));
621 LATCH_EDGE (fallthru
) = conn_latch
;
626 /* Takes care of merging natural loops with shared headers. */
628 canonicalize_loop_headers (void)
634 /* Compute the dominators. */
635 dom
= calculate_dominance_info (CDI_DOMINATORS
);
637 alloc_aux_for_blocks (sizeof (int));
638 alloc_aux_for_edges (sizeof (int));
640 /* Split blocks so that each loop has only single latch. */
644 int have_abnormal_edge
= 0;
646 for (e
= header
->pred
; e
; e
= e
->pred_next
)
648 basic_block latch
= e
->src
;
650 if (e
->flags
& EDGE_ABNORMAL
)
651 have_abnormal_edge
= 1;
653 if (latch
!= ENTRY_BLOCK_PTR
654 && dominated_by_p (dom
, latch
, header
))
660 if (have_abnormal_edge
)
661 HEADER_BLOCK (header
) = 0;
663 HEADER_BLOCK (header
) = num_latches
;
666 if (HEADER_BLOCK (ENTRY_BLOCK_PTR
->succ
->dest
))
670 /* We could not redirect edges freely here. On the other hand,
671 we can simply split the edge from entry block. */
672 bb
= split_edge (ENTRY_BLOCK_PTR
->succ
);
674 alloc_aux_for_edge (bb
->succ
, sizeof (int));
675 LATCH_EDGE (bb
->succ
) = 0;
676 alloc_aux_for_block (bb
, sizeof (int));
677 HEADER_BLOCK (bb
) = 0;
684 int max_freq
, is_heavy
;
687 if (!HEADER_BLOCK (header
))
690 num_latch
= HEADER_BLOCK (header
);
692 want_join_latch
= (num_latch
> 1);
694 if (!want_join_latch
)
697 /* Find a heavy edge. */
701 for (e
= header
->pred
; e
; e
= e
->pred_next
)
702 if (LATCH_EDGE (e
) &&
703 EDGE_FREQUENCY (e
) > max_freq
)
704 max_freq
= EDGE_FREQUENCY (e
);
705 for (e
= header
->pred
; e
; e
= e
->pred_next
)
706 if (LATCH_EDGE (e
) &&
707 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
720 basic_block new_header
=
721 make_forwarder_block (header
, true, true, heavy
, 0);
723 make_forwarder_block (new_header
, true, false, NULL
, 1);
726 make_forwarder_block (header
, true, false, NULL
, 1);
729 free_aux_for_blocks ();
730 free_aux_for_edges ();
731 free_dominance_info (dom
);
734 /* Find all the natural loops in the function and save in LOOPS structure and
735 recalculate loop_depth information in basic block structures. FLAGS
736 controls which loop information is collected. Return the number of natural
740 flow_loops_find (struct loops
*loops
, int flags
)
753 /* This function cannot be repeatedly called with different
754 flags to build up the loop information. The loop tree
755 must always be built if this function is called. */
756 if (! (flags
& LOOP_TREE
))
759 memset (loops
, 0, sizeof *loops
);
761 /* Taking care of this degenerate case makes the rest of
762 this code simpler. */
763 if (n_basic_blocks
== 0)
769 /* Join loops with shared headers. */
770 canonicalize_loop_headers ();
772 /* Compute the dominators. */
773 dom
= loops
->cfg
.dom
= calculate_dominance_info (CDI_DOMINATORS
);
775 /* Count the number of loop headers. This should be the
776 same as the number of natural loops. */
777 headers
= sbitmap_alloc (last_basic_block
);
778 sbitmap_zero (headers
);
783 int more_latches
= 0;
785 header
->loop_depth
= 0;
787 /* If we have an abnormal predecessor, do not consider the
788 loop (not worth the problems). */
789 for (e
= header
->pred
; e
; e
= e
->pred_next
)
790 if (e
->flags
& EDGE_ABNORMAL
)
795 for (e
= header
->pred
; e
; e
= e
->pred_next
)
797 basic_block latch
= e
->src
;
799 if (e
->flags
& EDGE_ABNORMAL
)
802 /* Look for back edges where a predecessor is dominated
803 by this block. A natural loop has a single entry
804 node (header) that dominates all the nodes in the
805 loop. It also has single back edge to the header
806 from a latch node. */
807 if (latch
!= ENTRY_BLOCK_PTR
&& dominated_by_p (dom
, latch
, header
))
809 /* Shared headers should be eliminated by now. */
813 SET_BIT (headers
, header
->index
);
819 /* Allocate loop structures. */
820 loops
->parray
= xcalloc (num_loops
+ 1, sizeof (struct loop
*));
822 /* Dummy loop containing whole function. */
823 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
824 loops
->parray
[0]->next
= NULL
;
825 loops
->parray
[0]->inner
= NULL
;
826 loops
->parray
[0]->outer
= NULL
;
827 loops
->parray
[0]->depth
= 0;
828 loops
->parray
[0]->pred
= NULL
;
829 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
830 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
831 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
832 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
833 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
835 loops
->tree_root
= loops
->parray
[0];
837 /* Find and record information about all the natural loops
841 bb
->loop_father
= loops
->tree_root
;
845 /* Compute depth first search order of the CFG so that outer
846 natural loops will be found before inner natural loops. */
847 dfs_order
= xmalloc (n_basic_blocks
* sizeof (int));
848 rc_order
= xmalloc (n_basic_blocks
* sizeof (int));
849 flow_depth_first_order_compute (dfs_order
, rc_order
);
851 /* Save CFG derived information to avoid recomputing it. */
852 loops
->cfg
.dom
= dom
;
853 loops
->cfg
.dfs_order
= dfs_order
;
854 loops
->cfg
.rc_order
= rc_order
;
858 for (b
= 0; b
< n_basic_blocks
; b
++)
862 /* Search the nodes of the CFG in reverse completion order
863 so that we can find outer loops first. */
864 if (!TEST_BIT (headers
, rc_order
[b
]))
867 header
= BASIC_BLOCK (rc_order
[b
]);
869 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
871 loop
->header
= header
;
872 loop
->num
= num_loops
;
875 /* Look for the latch for this header block. */
876 for (e
= header
->pred
; e
; e
= e
->pred_next
)
878 basic_block latch
= e
->src
;
880 if (latch
!= ENTRY_BLOCK_PTR
881 && dominated_by_p (dom
, latch
, header
))
888 flow_loop_tree_node_add (header
->loop_father
, loop
);
889 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
892 sbitmap_free (headers
);
894 /* Assign the loop nesting depth and enclosed loop level for each
896 loops
->levels
= flow_loops_level_compute (loops
);
898 /* Scan the loops. */
899 for (i
= 1; i
< num_loops
; i
++)
900 flow_loop_scan (loops
, loops
->parray
[i
], flags
);
902 loops
->num
= num_loops
;
906 loops
->cfg
.dom
= NULL
;
907 free_dominance_info (dom
);
911 #ifdef ENABLE_CHECKING
913 verify_loop_structure (loops
);
919 /* Update the information regarding the loops in the CFG
920 specified by LOOPS. */
923 flow_loops_update (struct loops
*loops
, int flags
)
925 /* One day we may want to update the current loop data. For now
926 throw away the old stuff and rebuild what we need. */
928 flow_loops_free (loops
);
930 return flow_loops_find (loops
, flags
);
933 /* Return nonzero if basic block BB belongs to LOOP. */
935 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
937 struct loop
*source_loop
;
939 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
942 source_loop
= bb
->loop_father
;
943 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
946 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
949 flow_loop_outside_edge_p (const struct loop
*loop
, edge e
)
951 if (e
->dest
!= loop
->header
)
953 return !flow_bb_inside_loop_p (loop
, e
->src
);
956 /* Enumeration predicate for get_loop_body. */
958 glb_enum_p (basic_block bb
, void *glb_header
)
960 return bb
!= (basic_block
) glb_header
;
963 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
964 order against direction of edges from latch. Specially, if
965 header != latch, latch is the 1-st block. */
967 get_loop_body (const struct loop
*loop
)
969 basic_block
*tovisit
, bb
;
972 if (!loop
->num_nodes
)
975 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
976 tovisit
[tv
++] = loop
->header
;
978 if (loop
->latch
== EXIT_BLOCK_PTR
)
980 /* There may be blocks unreachable from EXIT_BLOCK. */
981 if (loop
->num_nodes
!= (unsigned) n_basic_blocks
+ 2)
985 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
987 else if (loop
->latch
!= loop
->header
)
989 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
990 tovisit
+ 1, loop
->num_nodes
- 1,
994 if (tv
!= loop
->num_nodes
)
999 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1001 get_loop_exit_edges (const struct loop
*loop
, unsigned int *n_edges
)
1007 if (loop
->latch
== EXIT_BLOCK_PTR
)
1010 body
= get_loop_body (loop
);
1012 for (i
= 0; i
< loop
->num_nodes
; i
++)
1013 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
1014 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1016 edges
= xmalloc (n
* sizeof (edge
));
1019 for (i
= 0; i
< loop
->num_nodes
; i
++)
1020 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
1021 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1028 /* Adds basic block BB to LOOP. */
1030 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1034 bb
->loop_father
= loop
;
1035 bb
->loop_depth
= loop
->depth
;
1037 for (i
= 0; i
< loop
->depth
; i
++)
1038 loop
->pred
[i
]->num_nodes
++;
1041 /* Remove basic block BB from loops. */
1043 remove_bb_from_loops (basic_block bb
)
1046 struct loop
*loop
= bb
->loop_father
;
1049 for (i
= 0; i
< loop
->depth
; i
++)
1050 loop
->pred
[i
]->num_nodes
--;
1051 bb
->loop_father
= NULL
;
1055 /* Finds nearest common ancestor in loop tree for given loops. */
1057 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1059 if (!loop_s
) return loop_d
;
1060 if (!loop_d
) return loop_s
;
1062 if (loop_s
->depth
< loop_d
->depth
)
1063 loop_d
= loop_d
->pred
[loop_s
->depth
];
1064 else if (loop_s
->depth
> loop_d
->depth
)
1065 loop_s
= loop_s
->pred
[loop_d
->depth
];
1067 while (loop_s
!= loop_d
)
1069 loop_s
= loop_s
->outer
;
1070 loop_d
= loop_d
->outer
;
1075 /* Cancels the LOOP; it must be innermost one. */
1077 cancel_loop (struct loops
*loops
, struct loop
*loop
)
1085 /* Move blocks up one level (they should be removed as soon as possible). */
1086 bbs
= get_loop_body (loop
);
1087 for (i
= 0; i
< loop
->num_nodes
; i
++)
1088 bbs
[i
]->loop_father
= loop
->outer
;
1090 /* Remove the loop from structure. */
1091 flow_loop_tree_node_remove (loop
);
1093 /* Remove loop from loops array. */
1094 loops
->parray
[loop
->num
] = NULL
;
1096 /* Free loop data. */
1097 flow_loop_free (loop
);
1100 /* Cancels LOOP and all its subloops. */
1102 cancel_loop_tree (struct loops
*loops
, struct loop
*loop
)
1105 cancel_loop_tree (loops
, loop
->inner
);
1106 cancel_loop (loops
, loop
);
1109 /* Checks that LOOPS are all right:
1110 -- sizes of loops are all right
1111 -- results of get_loop_body really belong to the loop
1112 -- loop header have just single entry edge and single latch edge
1113 -- loop latches have only single successor that is header of their loop
1114 -- irreducible loops are correctly marked
1117 verify_loop_structure (struct loops
*loops
)
1119 unsigned *sizes
, i
, j
;
1121 basic_block
*bbs
, bb
;
1127 sizes
= xcalloc (loops
->num
, sizeof (int));
1131 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1134 for (i
= 0; i
< loops
->num
; i
++)
1136 if (!loops
->parray
[i
])
1139 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1141 error ("Size of loop %d should be %d, not %d.",
1142 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1149 /* Check get_loop_body. */
1150 for (i
= 1; i
< loops
->num
; i
++)
1152 loop
= loops
->parray
[i
];
1155 bbs
= get_loop_body (loop
);
1157 for (j
= 0; j
< loop
->num_nodes
; j
++)
1158 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1160 error ("Bb %d do not belong to loop %d.",
1167 /* Check headers and latches. */
1168 for (i
= 1; i
< loops
->num
; i
++)
1170 loop
= loops
->parray
[i
];
1174 if ((loops
->state
& LOOPS_HAVE_PREHEADERS
)
1175 && (!loop
->header
->pred
->pred_next
1176 || loop
->header
->pred
->pred_next
->pred_next
))
1178 error ("Loop %d's header does not have exactly 2 entries.", i
);
1181 if (loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1183 if (!loop
->latch
->succ
1184 || loop
->latch
->succ
->succ_next
)
1186 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1189 if (loop
->latch
->succ
->dest
!= loop
->header
)
1191 error ("Loop %d's latch does not have header as successor.", i
);
1194 if (loop
->latch
->loop_father
!= loop
)
1196 error ("Loop %d's latch does not belong directly to it.", i
);
1200 if (loop
->header
->loop_father
!= loop
)
1202 error ("Loop %d's header does not belong directly to it.", i
);
1205 if ((loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1206 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1208 error ("Loop %d's latch is marked as part of irreducible region.", i
);
1213 /* Check irreducible loops. */
1214 if (loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1216 /* Record old info. */
1217 irreds
= sbitmap_alloc (last_basic_block
);
1220 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1221 SET_BIT (irreds
, bb
->index
);
1223 RESET_BIT (irreds
, bb
->index
);
1224 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1225 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1226 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1230 mark_irreducible_loops (loops
);
1235 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1236 && !TEST_BIT (irreds
, bb
->index
))
1238 error ("Basic block %d should be marked irreducible.", bb
->index
);
1241 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1242 && TEST_BIT (irreds
, bb
->index
))
1244 error ("Basic block %d should not be marked irreducible.", bb
->index
);
1247 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1249 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1250 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1252 error ("Edge from %d to %d should be marked irreducible.",
1253 e
->src
->index
, e
->dest
->index
);
1256 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1257 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1259 error ("Edge from %d to %d should not be marked irreducible.",
1260 e
->src
->index
, e
->dest
->index
);
1263 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1273 /* Returns latch edge of LOOP. */
1275 loop_latch_edge (const struct loop
*loop
)
1279 for (e
= loop
->header
->pred
; e
->src
!= loop
->latch
; e
= e
->pred_next
)
1285 /* Returns preheader edge of LOOP. */
1287 loop_preheader_edge (const struct loop
*loop
)
1291 for (e
= loop
->header
->pred
; e
->src
== loop
->latch
; e
= e
->pred_next
)