1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005 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"
29 #include "basic-block.h"
34 #include "tree-flow.h"
36 /* Ratio of frequencies of edges so that one of more latch edges is
37 considered to belong to inner loop with same header. */
38 #define HEAVY_EDGE_RATIO 8
40 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
41 #define LATCH_EDGE(E) (*(int *) (E)->aux)
43 static void flow_loops_cfg_dump (const struct loops
*, FILE *);
44 static int flow_loop_level_compute (struct loop
*);
45 static void flow_loops_level_compute (struct loops
*);
46 static void establish_preds (struct loop
*);
47 static void canonicalize_loop_headers (void);
48 static bool glb_enum_p (basic_block
, void *);
50 /* Dump loop related CFG information. */
53 flow_loops_cfg_dump (const struct loops
*loops
, FILE *file
)
58 if (! loops
->num
|| ! file
)
66 fprintf (file
, ";; %d succs { ", bb
->index
);
67 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
68 fprintf (file
, "%d ", succ
->dest
->index
);
69 fprintf (file
, "}\n");
72 /* Dump the DFS node order. */
73 if (loops
->cfg
.dfs_order
)
75 fputs (";; DFS order: ", file
);
76 for (i
= 0; i
< n_basic_blocks
; i
++)
77 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
82 /* Dump the reverse completion node order. */
83 if (loops
->cfg
.rc_order
)
85 fputs (";; RC order: ", file
);
86 for (i
= 0; i
< n_basic_blocks
; i
++)
87 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
93 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
96 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
98 return (loop
->depth
> outer
->depth
99 && loop
->pred
[outer
->depth
] == outer
);
102 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
103 loops within LOOP. */
106 superloop_at_depth (struct loop
*loop
, unsigned depth
)
108 gcc_assert (depth
<= (unsigned) loop
->depth
);
110 if (depth
== (unsigned) loop
->depth
)
113 return loop
->pred
[depth
];
116 /* Dump the loop information specified by LOOP to the stream FILE
117 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
120 flow_loop_dump (const struct loop
*loop
, FILE *file
,
121 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
127 if (! loop
|| ! loop
->header
)
130 fprintf (file
, ";;\n;; Loop %d:%s\n", loop
->num
,
131 loop
->invalid
? " invalid" : "");
133 fprintf (file
, ";; header %d, latch %d\n",
134 loop
->header
->index
, loop
->latch
->index
);
135 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
136 loop
->depth
, loop
->level
,
137 (long) (loop
->outer
? loop
->outer
->num
: -1));
139 fprintf (file
, ";; nodes:");
140 bbs
= get_loop_body (loop
);
141 for (i
= 0; i
< loop
->num_nodes
; i
++)
142 fprintf (file
, " %d", bbs
[i
]->index
);
144 fprintf (file
, "\n");
147 loop_dump_aux (loop
, file
, verbose
);
150 /* Dump the loop information specified by LOOPS to the stream FILE,
151 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
154 flow_loops_dump (const struct loops
*loops
, FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
159 num_loops
= loops
->num
;
160 if (! num_loops
|| ! file
)
163 fprintf (file
, ";; %d loops found\n", num_loops
);
165 for (i
= 0; i
< num_loops
; i
++)
167 struct loop
*loop
= loops
->parray
[i
];
172 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
176 flow_loops_cfg_dump (loops
, file
);
179 /* Free data allocated for LOOP. */
181 flow_loop_free (struct loop
*loop
)
188 /* Free all the memory allocated for LOOPS. */
191 flow_loops_free (struct loops
*loops
)
197 gcc_assert (loops
->num
);
199 /* Free the loop descriptors. */
200 for (i
= 0; i
< loops
->num
; i
++)
202 struct loop
*loop
= loops
->parray
[i
];
207 flow_loop_free (loop
);
210 free (loops
->parray
);
211 loops
->parray
= NULL
;
213 if (loops
->cfg
.dfs_order
)
214 free (loops
->cfg
.dfs_order
);
215 if (loops
->cfg
.rc_order
)
216 free (loops
->cfg
.rc_order
);
221 /* Find the nodes contained within the LOOP with header HEADER.
222 Return the number of nodes within the loop. */
225 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
231 header
->loop_father
= loop
;
232 header
->loop_depth
= loop
->depth
;
234 if (loop
->latch
->loop_father
!= loop
)
236 stack
= xmalloc (n_basic_blocks
* sizeof (basic_block
));
239 stack
[sp
++] = loop
->latch
;
240 loop
->latch
->loop_father
= loop
;
241 loop
->latch
->loop_depth
= loop
->depth
;
251 FOR_EACH_EDGE (e
, ei
, node
->preds
)
253 basic_block ancestor
= e
->src
;
255 if (ancestor
!= ENTRY_BLOCK_PTR
256 && ancestor
->loop_father
!= loop
)
258 ancestor
->loop_father
= loop
;
259 ancestor
->loop_depth
= loop
->depth
;
261 stack
[sp
++] = ancestor
;
270 /* For each loop in the lOOPS tree that has just a single exit
271 record the exit edge. */
274 mark_single_exit_loops (struct loops
*loops
)
281 for (i
= 1; i
< loops
->num
; i
++)
283 loop
= loops
->parray
[i
];
285 loop
->single_exit
= NULL
;
291 if (bb
->loop_father
== loops
->tree_root
)
293 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
295 if (e
->dest
== EXIT_BLOCK_PTR
)
298 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
301 for (loop
= bb
->loop_father
;
302 loop
!= e
->dest
->loop_father
;
305 /* If we have already seen an exit, mark this by the edge that
306 surely does not occur as any exit. */
307 if (loop
->single_exit
)
308 loop
->single_exit
= single_succ_edge (ENTRY_BLOCK_PTR
);
310 loop
->single_exit
= e
;
315 for (i
= 1; i
< loops
->num
; i
++)
317 loop
= loops
->parray
[i
];
321 if (loop
->single_exit
== single_succ_edge (ENTRY_BLOCK_PTR
))
322 loop
->single_exit
= NULL
;
325 loops
->state
|= LOOPS_HAVE_MARKED_SINGLE_EXITS
;
329 establish_preds (struct loop
*loop
)
331 struct loop
*ploop
, *father
= loop
->outer
;
333 loop
->depth
= father
->depth
+ 1;
335 /* Remember the current loop depth if it is the largest seen so far. */
336 cfun
->max_loop_depth
= MAX (cfun
->max_loop_depth
, loop
->depth
);
340 loop
->pred
= xmalloc (sizeof (struct loop
*) * loop
->depth
);
341 memcpy (loop
->pred
, father
->pred
, sizeof (struct loop
*) * father
->depth
);
342 loop
->pred
[father
->depth
] = father
;
344 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
345 establish_preds (ploop
);
348 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
349 added loop. If LOOP has some children, take care of that their
350 pred field will be initialized correctly. */
353 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
355 loop
->next
= father
->inner
;
356 father
->inner
= loop
;
357 loop
->outer
= father
;
359 establish_preds (loop
);
362 /* Remove LOOP from the loop hierarchy tree. */
365 flow_loop_tree_node_remove (struct loop
*loop
)
367 struct loop
*prev
, *father
;
369 father
= loop
->outer
;
372 /* Remove loop from the list of sons. */
373 if (father
->inner
== loop
)
374 father
->inner
= loop
->next
;
377 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
);
378 prev
->next
= loop
->next
;
386 /* Helper function to compute loop nesting depth and enclosed loop level
387 for the natural loop specified by LOOP. Returns the loop level. */
390 flow_loop_level_compute (struct loop
*loop
)
398 /* Traverse loop tree assigning depth and computing level as the
399 maximum level of all the inner loops of this loop. The loop
400 level is equivalent to the height of the loop in the loop tree
401 and corresponds to the number of enclosed loop levels (including
403 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
405 int ilevel
= flow_loop_level_compute (inner
) + 1;
415 /* Compute the loop nesting depth and enclosed loop level for the loop
416 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
420 flow_loops_level_compute (struct loops
*loops
)
422 flow_loop_level_compute (loops
->tree_root
);
425 /* A callback to update latch and header info for basic block JUMP created
426 by redirecting an edge. */
429 update_latch_info (basic_block jump
)
431 alloc_aux_for_block (jump
, sizeof (int));
432 HEADER_BLOCK (jump
) = 0;
433 alloc_aux_for_edge (single_pred_edge (jump
), sizeof (int));
434 LATCH_EDGE (single_pred_edge (jump
)) = 0;
435 set_immediate_dominator (CDI_DOMINATORS
, jump
, single_pred (jump
));
438 /* A callback for make_forwarder block, to redirect all edges except for
439 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
440 whether to redirect it. */
442 static edge mfb_kj_edge
;
444 mfb_keep_just (edge e
)
446 return e
!= mfb_kj_edge
;
449 /* A callback for make_forwarder block, to redirect the latch edges into an
450 entry part. E is the edge for that we should decide whether to redirect
454 mfb_keep_nonlatch (edge e
)
456 return LATCH_EDGE (e
);
459 /* Takes care of merging natural loops with shared headers. */
462 canonicalize_loop_headers (void)
467 alloc_aux_for_blocks (sizeof (int));
468 alloc_aux_for_edges (sizeof (int));
470 /* Split blocks so that each loop has only single latch. */
475 int have_abnormal_edge
= 0;
477 FOR_EACH_EDGE (e
, ei
, header
->preds
)
479 basic_block latch
= e
->src
;
481 if (e
->flags
& EDGE_ABNORMAL
)
482 have_abnormal_edge
= 1;
484 if (latch
!= ENTRY_BLOCK_PTR
485 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
491 if (have_abnormal_edge
)
492 HEADER_BLOCK (header
) = 0;
494 HEADER_BLOCK (header
) = num_latches
;
497 if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR
)))
501 /* We could not redirect edges freely here. On the other hand,
502 we can simply split the edge from entry block. */
503 bb
= split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
505 alloc_aux_for_edge (single_succ_edge (bb
), sizeof (int));
506 LATCH_EDGE (single_succ_edge (bb
)) = 0;
507 alloc_aux_for_block (bb
, sizeof (int));
508 HEADER_BLOCK (bb
) = 0;
513 int max_freq
, is_heavy
;
514 edge heavy
, tmp_edge
;
517 if (HEADER_BLOCK (header
) <= 1)
520 /* Find a heavy edge. */
524 FOR_EACH_EDGE (e
, ei
, header
->preds
)
525 if (LATCH_EDGE (e
) &&
526 EDGE_FREQUENCY (e
) > max_freq
)
527 max_freq
= EDGE_FREQUENCY (e
);
528 FOR_EACH_EDGE (e
, ei
, header
->preds
)
529 if (LATCH_EDGE (e
) &&
530 EDGE_FREQUENCY (e
) >= max_freq
/ HEAVY_EDGE_RATIO
)
543 /* Split out the heavy edge, and create inner loop for it. */
545 tmp_edge
= make_forwarder_block (header
, mfb_keep_just
,
547 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
548 HEADER_BLOCK (tmp_edge
->dest
) = 1;
549 alloc_aux_for_edge (tmp_edge
, sizeof (int));
550 LATCH_EDGE (tmp_edge
) = 0;
551 HEADER_BLOCK (header
)--;
554 if (HEADER_BLOCK (header
) > 1)
556 /* Create a new latch block. */
557 tmp_edge
= make_forwarder_block (header
, mfb_keep_nonlatch
,
559 alloc_aux_for_block (tmp_edge
->dest
, sizeof (int));
560 HEADER_BLOCK (tmp_edge
->src
) = 0;
561 HEADER_BLOCK (tmp_edge
->dest
) = 1;
562 alloc_aux_for_edge (tmp_edge
, sizeof (int));
563 LATCH_EDGE (tmp_edge
) = 1;
567 free_aux_for_blocks ();
568 free_aux_for_edges ();
570 #ifdef ENABLE_CHECKING
571 verify_dominators (CDI_DOMINATORS
);
575 /* Initialize all the parallel_p fields of the loops structure to true. */
578 initialize_loops_parallel_p (struct loops
*loops
)
582 for (i
= 0; i
< loops
->num
; i
++)
584 struct loop
*loop
= loops
->parray
[i
];
585 loop
->parallel_p
= true;
589 /* Find all the natural loops in the function and save in LOOPS structure and
590 recalculate loop_depth information in basic block structures.
591 Return the number of natural loops found. */
594 flow_loops_find (struct loops
*loops
)
605 memset (loops
, 0, sizeof *loops
);
607 /* We are going to recount the maximum loop depth,
608 so throw away the last count. */
609 cfun
->max_loop_depth
= 0;
611 /* Taking care of this degenerate case makes the rest of
612 this code simpler. */
613 if (n_basic_blocks
== 0)
619 /* Ensure that the dominators are computed. */
620 calculate_dominance_info (CDI_DOMINATORS
);
622 /* Join loops with shared headers. */
623 canonicalize_loop_headers ();
625 /* Count the number of loop headers. This should be the
626 same as the number of natural loops. */
627 headers
= sbitmap_alloc (last_basic_block
);
628 sbitmap_zero (headers
);
634 int more_latches
= 0;
636 header
->loop_depth
= 0;
638 /* If we have an abnormal predecessor, do not consider the
639 loop (not worth the problems). */
640 FOR_EACH_EDGE (e
, ei
, header
->preds
)
641 if (e
->flags
& EDGE_ABNORMAL
)
646 FOR_EACH_EDGE (e
, ei
, header
->preds
)
648 basic_block latch
= e
->src
;
650 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
652 /* Look for back edges where a predecessor is dominated
653 by this block. A natural loop has a single entry
654 node (header) that dominates all the nodes in the
655 loop. It also has single back edge to the header
656 from a latch node. */
657 if (latch
!= ENTRY_BLOCK_PTR
658 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
660 /* Shared headers should be eliminated by now. */
661 gcc_assert (!more_latches
);
663 SET_BIT (headers
, header
->index
);
669 /* Allocate loop structures. */
670 loops
->parray
= xcalloc (num_loops
+ 1, sizeof (struct loop
*));
672 /* Dummy loop containing whole function. */
673 loops
->parray
[0] = xcalloc (1, sizeof (struct loop
));
674 loops
->parray
[0]->next
= NULL
;
675 loops
->parray
[0]->inner
= NULL
;
676 loops
->parray
[0]->outer
= NULL
;
677 loops
->parray
[0]->depth
= 0;
678 loops
->parray
[0]->pred
= NULL
;
679 loops
->parray
[0]->num_nodes
= n_basic_blocks
+ 2;
680 loops
->parray
[0]->latch
= EXIT_BLOCK_PTR
;
681 loops
->parray
[0]->header
= ENTRY_BLOCK_PTR
;
682 ENTRY_BLOCK_PTR
->loop_father
= loops
->parray
[0];
683 EXIT_BLOCK_PTR
->loop_father
= loops
->parray
[0];
685 loops
->tree_root
= loops
->parray
[0];
687 /* Find and record information about all the natural loops
691 bb
->loop_father
= loops
->tree_root
;
695 /* Compute depth first search order of the CFG so that outer
696 natural loops will be found before inner natural loops. */
697 dfs_order
= xmalloc (n_basic_blocks
* sizeof (int));
698 rc_order
= xmalloc (n_basic_blocks
* sizeof (int));
699 flow_depth_first_order_compute (dfs_order
, rc_order
);
701 /* Save CFG derived information to avoid recomputing it. */
702 loops
->cfg
.dfs_order
= dfs_order
;
703 loops
->cfg
.rc_order
= rc_order
;
707 for (b
= 0; b
< n_basic_blocks
; b
++)
712 /* Search the nodes of the CFG in reverse completion order
713 so that we can find outer loops first. */
714 if (!TEST_BIT (headers
, rc_order
[b
]))
717 header
= BASIC_BLOCK (rc_order
[b
]);
719 loop
= loops
->parray
[num_loops
] = xcalloc (1, sizeof (struct loop
));
721 loop
->header
= header
;
722 loop
->num
= num_loops
;
725 /* Look for the latch for this header block. */
726 FOR_EACH_EDGE (e
, ei
, header
->preds
)
728 basic_block latch
= e
->src
;
730 if (latch
!= ENTRY_BLOCK_PTR
731 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
738 flow_loop_tree_node_add (header
->loop_father
, loop
);
739 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
742 /* Assign the loop nesting depth and enclosed loop level for each
744 flow_loops_level_compute (loops
);
746 loops
->num
= num_loops
;
747 initialize_loops_parallel_p (loops
);
750 sbitmap_free (headers
);
753 #ifdef ENABLE_CHECKING
755 verify_loop_structure (loops
);
761 /* Return nonzero if basic block BB belongs to LOOP. */
763 flow_bb_inside_loop_p (const struct loop
*loop
, const basic_block bb
)
765 struct loop
*source_loop
;
767 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
770 source_loop
= bb
->loop_father
;
771 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
774 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
777 flow_loop_outside_edge_p (const struct loop
*loop
, edge e
)
779 gcc_assert (e
->dest
== loop
->header
);
780 return !flow_bb_inside_loop_p (loop
, e
->src
);
783 /* Enumeration predicate for get_loop_body. */
785 glb_enum_p (basic_block bb
, void *glb_header
)
787 return bb
!= (basic_block
) glb_header
;
790 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
791 order against direction of edges from latch. Specially, if
792 header != latch, latch is the 1-st block. */
794 get_loop_body (const struct loop
*loop
)
796 basic_block
*tovisit
, bb
;
799 gcc_assert (loop
->num_nodes
);
801 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
802 tovisit
[tv
++] = loop
->header
;
804 if (loop
->latch
== EXIT_BLOCK_PTR
)
806 /* There may be blocks unreachable from EXIT_BLOCK. */
807 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
+ 2);
810 tovisit
[tv
++] = EXIT_BLOCK_PTR
;
812 else if (loop
->latch
!= loop
->header
)
814 tv
= dfs_enumerate_from (loop
->latch
, 1, glb_enum_p
,
815 tovisit
+ 1, loop
->num_nodes
- 1,
819 gcc_assert (tv
== loop
->num_nodes
);
823 /* Fills dominance descendants inside LOOP of the basic block BB into
824 array TOVISIT from index *TV. */
827 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
828 basic_block
*tovisit
, int *tv
)
830 basic_block son
, postpone
= NULL
;
832 tovisit
[(*tv
)++] = bb
;
833 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
835 son
= next_dom_son (CDI_DOMINATORS
, son
))
837 if (!flow_bb_inside_loop_p (loop
, son
))
840 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
845 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
849 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
852 /* Gets body of a LOOP (that must be different from the outermost loop)
853 sorted by dominance relation. Additionally, if a basic block s dominates
854 the latch, then only blocks dominated by s are be after it. */
857 get_loop_body_in_dom_order (const struct loop
*loop
)
859 basic_block
*tovisit
;
862 gcc_assert (loop
->num_nodes
);
864 tovisit
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
866 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
869 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
871 gcc_assert (tv
== (int) loop
->num_nodes
);
876 /* Get body of a LOOP in breadth first sort order. */
879 get_loop_body_in_bfs_order (const struct loop
*loop
)
887 gcc_assert (loop
->num_nodes
);
888 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
890 blocks
= xcalloc (loop
->num_nodes
, sizeof (basic_block
));
891 visited
= BITMAP_ALLOC (NULL
);
894 while (i
< loop
->num_nodes
)
899 if (!bitmap_bit_p (visited
, bb
->index
))
901 /* This basic block is now visited */
902 bitmap_set_bit (visited
, bb
->index
);
906 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
908 if (flow_bb_inside_loop_p (loop
, e
->dest
))
910 if (!bitmap_bit_p (visited
, e
->dest
->index
))
912 bitmap_set_bit (visited
, e
->dest
->index
);
913 blocks
[i
++] = e
->dest
;
918 gcc_assert (i
>= vc
);
923 BITMAP_FREE (visited
);
927 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
929 get_loop_exit_edges (const struct loop
*loop
, unsigned int *n_edges
)
936 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
938 body
= get_loop_body (loop
);
940 for (i
= 0; i
< loop
->num_nodes
; i
++)
941 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
942 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
944 edges
= xmalloc (n
* sizeof (edge
));
947 for (i
= 0; i
< loop
->num_nodes
; i
++)
948 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
949 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
956 /* Counts the number of conditional branches inside LOOP. */
959 num_loop_branches (const struct loop
*loop
)
964 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
966 body
= get_loop_body (loop
);
968 for (i
= 0; i
< loop
->num_nodes
; i
++)
969 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
976 /* Adds basic block BB to LOOP. */
978 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
982 bb
->loop_father
= loop
;
983 bb
->loop_depth
= loop
->depth
;
985 for (i
= 0; i
< loop
->depth
; i
++)
986 loop
->pred
[i
]->num_nodes
++;
989 /* Remove basic block BB from loops. */
991 remove_bb_from_loops (basic_block bb
)
994 struct loop
*loop
= bb
->loop_father
;
997 for (i
= 0; i
< loop
->depth
; i
++)
998 loop
->pred
[i
]->num_nodes
--;
999 bb
->loop_father
= NULL
;
1003 /* Finds nearest common ancestor in loop tree for given loops. */
1005 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1007 if (!loop_s
) return loop_d
;
1008 if (!loop_d
) return loop_s
;
1010 if (loop_s
->depth
< loop_d
->depth
)
1011 loop_d
= loop_d
->pred
[loop_s
->depth
];
1012 else if (loop_s
->depth
> loop_d
->depth
)
1013 loop_s
= loop_s
->pred
[loop_d
->depth
];
1015 while (loop_s
!= loop_d
)
1017 loop_s
= loop_s
->outer
;
1018 loop_d
= loop_d
->outer
;
1023 /* Cancels the LOOP; it must be innermost one. */
1025 cancel_loop (struct loops
*loops
, struct loop
*loop
)
1030 gcc_assert (!loop
->inner
);
1032 /* Move blocks up one level (they should be removed as soon as possible). */
1033 bbs
= get_loop_body (loop
);
1034 for (i
= 0; i
< loop
->num_nodes
; i
++)
1035 bbs
[i
]->loop_father
= loop
->outer
;
1037 /* Remove the loop from structure. */
1038 flow_loop_tree_node_remove (loop
);
1040 /* Remove loop from loops array. */
1041 loops
->parray
[loop
->num
] = NULL
;
1043 /* Free loop data. */
1044 flow_loop_free (loop
);
1047 /* Cancels LOOP and all its subloops. */
1049 cancel_loop_tree (struct loops
*loops
, struct loop
*loop
)
1052 cancel_loop_tree (loops
, loop
->inner
);
1053 cancel_loop (loops
, loop
);
1056 /* Checks that LOOPS are all right:
1057 -- sizes of loops are all right
1058 -- results of get_loop_body really belong to the loop
1059 -- loop header have just single entry edge and single latch edge
1060 -- loop latches have only single successor that is header of their loop
1061 -- irreducible loops are correctly marked
1064 verify_loop_structure (struct loops
*loops
)
1066 unsigned *sizes
, i
, j
;
1068 basic_block
*bbs
, bb
;
1074 sizes
= xcalloc (loops
->num
, sizeof (int));
1078 for (loop
= bb
->loop_father
; loop
; loop
= loop
->outer
)
1081 for (i
= 0; i
< loops
->num
; i
++)
1083 if (!loops
->parray
[i
])
1086 if (loops
->parray
[i
]->num_nodes
!= sizes
[i
])
1088 error ("Size of loop %d should be %d, not %d.",
1089 i
, sizes
[i
], loops
->parray
[i
]->num_nodes
);
1094 /* Check get_loop_body. */
1095 for (i
= 1; i
< loops
->num
; i
++)
1097 loop
= loops
->parray
[i
];
1100 bbs
= get_loop_body (loop
);
1102 for (j
= 0; j
< loop
->num_nodes
; j
++)
1103 if (!flow_bb_inside_loop_p (loop
, bbs
[j
]))
1105 error ("Bb %d do not belong to loop %d.",
1112 /* Check headers and latches. */
1113 for (i
= 1; i
< loops
->num
; i
++)
1115 loop
= loops
->parray
[i
];
1119 if ((loops
->state
& LOOPS_HAVE_PREHEADERS
)
1120 && EDGE_COUNT (loop
->header
->preds
) != 2)
1122 error ("Loop %d's header does not have exactly 2 entries.", i
);
1125 if (loops
->state
& LOOPS_HAVE_SIMPLE_LATCHES
)
1127 if (!single_succ_p (loop
->latch
))
1129 error ("Loop %d's latch does not have exactly 1 successor.", i
);
1132 if (single_succ (loop
->latch
) != loop
->header
)
1134 error ("Loop %d's latch does not have header as successor.", i
);
1137 if (loop
->latch
->loop_father
!= loop
)
1139 error ("Loop %d's latch does not belong directly to it.", i
);
1143 if (loop
->header
->loop_father
!= loop
)
1145 error ("Loop %d's header does not belong directly to it.", i
);
1148 if ((loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1149 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1151 error ("Loop %d's latch is marked as part of irreducible region.", i
);
1156 /* Check irreducible loops. */
1157 if (loops
->state
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1159 /* Record old info. */
1160 irreds
= sbitmap_alloc (last_basic_block
);
1164 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1165 SET_BIT (irreds
, bb
->index
);
1167 RESET_BIT (irreds
, bb
->index
);
1168 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1169 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1170 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1174 mark_irreducible_loops (loops
);
1181 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1182 && !TEST_BIT (irreds
, bb
->index
))
1184 error ("Basic block %d should be marked irreducible.", bb
->index
);
1187 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1188 && TEST_BIT (irreds
, bb
->index
))
1190 error ("Basic block %d should not be marked irreducible.", bb
->index
);
1193 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1195 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1196 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1198 error ("Edge from %d to %d should be marked irreducible.",
1199 e
->src
->index
, e
->dest
->index
);
1202 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1203 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1205 error ("Edge from %d to %d should not be marked irreducible.",
1206 e
->src
->index
, e
->dest
->index
);
1209 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1215 /* Check the single_exit. */
1216 if (loops
->state
& LOOPS_HAVE_MARKED_SINGLE_EXITS
)
1218 memset (sizes
, 0, sizeof (unsigned) * loops
->num
);
1222 if (bb
->loop_father
== loops
->tree_root
)
1224 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1226 if (e
->dest
== EXIT_BLOCK_PTR
)
1229 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1232 for (loop
= bb
->loop_father
;
1233 loop
!= e
->dest
->loop_father
;
1237 if (loop
->single_exit
1238 && loop
->single_exit
!= e
)
1240 error ("Wrong single exit %d->%d recorded for loop %d.",
1241 loop
->single_exit
->src
->index
,
1242 loop
->single_exit
->dest
->index
,
1244 error ("Right exit is %d->%d.",
1245 e
->src
->index
, e
->dest
->index
);
1252 for (i
= 1; i
< loops
->num
; i
++)
1254 loop
= loops
->parray
[i
];
1259 && !loop
->single_exit
)
1261 error ("Single exit not recorded for loop %d.", loop
->num
);
1266 && loop
->single_exit
)
1268 error ("Loop %d should not have single exit (%d -> %d).",
1270 loop
->single_exit
->src
->index
,
1271 loop
->single_exit
->dest
->index
);
1282 /* Returns latch edge of LOOP. */
1284 loop_latch_edge (const struct loop
*loop
)
1286 return find_edge (loop
->latch
, loop
->header
);
1289 /* Returns preheader edge of LOOP. */
1291 loop_preheader_edge (const struct loop
*loop
)
1296 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1297 if (e
->src
!= loop
->latch
)
1303 /* Returns true if E is an exit of LOOP. */
1306 loop_exit_edge_p (const struct loop
*loop
, edge e
)
1308 return (flow_bb_inside_loop_p (loop
, e
->src
)
1309 && !flow_bb_inside_loop_p (loop
, e
->dest
));