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)
69 fprintf (file, ";; %d succs { ", bb->index);
70 FOR_EACH_EDGE (succ, ei, bb->succs)
71 fprintf (file, "%d ", succ->dest->index);
72 fprintf (file, "}\n");
75 /* Dump the DFS node order. */
76 if (loops->cfg.dfs_order)
78 fputs (";; DFS order: ", file);
79 for (i = 0; i < n_basic_blocks; i++)
80 fprintf (file, "%d ", loops->cfg.dfs_order[i]);
85 /* Dump the reverse completion node order. */
86 if (loops->cfg.rc_order)
88 fputs (";; RC order: ", file);
89 for (i = 0; i < n_basic_blocks; i++)
90 fprintf (file, "%d ", loops->cfg.rc_order[i]);
96 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
99 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
101 return (loop->depth > outer->depth
102 && loop->pred[outer->depth] == outer);
105 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
106 loops within LOOP. */
109 superloop_at_depth (struct loop *loop, unsigned depth)
111 gcc_assert (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)
216 gcc_assert (loops->num);
218 /* Free the loop descriptors. */
219 for (i = 0; i < loops->num; i++)
221 struct loop *loop = loops->parray[i];
226 flow_loop_free (loop);
229 free (loops->parray);
230 loops->parray = NULL;
232 if (loops->cfg.dfs_order)
233 free (loops->cfg.dfs_order);
234 if (loops->cfg.rc_order)
235 free (loops->cfg.rc_order);
240 /* Find the entry edges into the LOOP. */
243 flow_loop_entry_edges_find (struct loop *loop)
250 FOR_EACH_EDGE (e, ei, loop->header->preds)
252 if (flow_loop_outside_edge_p (loop, e))
256 gcc_assert (num_entries);
258 loop->entry_edges = xmalloc (num_entries * sizeof (edge *));
261 FOR_EACH_EDGE (e, ei, loop->header->preds)
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 (struct loop *loop)
276 basic_block node, *bbs;
277 unsigned num_exits, i;
279 loop->exit_edges = NULL;
282 /* Check all nodes within the loop to see if there are any
283 successors not in the loop. Note that a node may have multiple
286 bbs = get_loop_body (loop);
287 for (i = 0; i < loop->num_nodes; i++)
291 FOR_EACH_EDGE (e, ei, node->succs)
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++)
314 FOR_EACH_EDGE (e, ei, node->succs)
316 basic_block dest = e->dest;
318 if (!flow_bb_inside_loop_p (loop, dest))
320 e->flags |= EDGE_LOOP_EXIT;
321 loop->exit_edges[num_exits++] = e;
326 loop->num_exits = num_exits;
329 /* Find the nodes contained within the LOOP with header HEADER.
330 Return the number of nodes within the loop. */
333 flow_loop_nodes_find (basic_block header, struct loop *loop)
339 header->loop_father = loop;
340 header->loop_depth = loop->depth;
342 if (loop->latch->loop_father != loop)
344 stack = xmalloc (n_basic_blocks * sizeof (basic_block));
347 stack[sp++] = loop->latch;
348 loop->latch->loop_father = loop;
349 loop->latch->loop_depth = loop->depth;
359 FOR_EACH_EDGE (e, ei, node->preds)
361 basic_block ancestor = e->src;
363 if (ancestor != ENTRY_BLOCK_PTR
364 && ancestor->loop_father != loop)
366 ancestor->loop_father = loop;
367 ancestor->loop_depth = loop->depth;
369 stack[sp++] = ancestor;
378 /* For each loop in the lOOPS tree that has just a single exit
379 record the exit edge. */
382 mark_single_exit_loops (struct loops *loops)
389 for (i = 1; i < loops->num; i++)
391 loop = loops->parray[i];
393 loop->single_exit = NULL;
399 if (bb->loop_father == loops->tree_root)
401 FOR_EACH_EDGE (e, ei, bb->succs)
403 if (e->dest == EXIT_BLOCK_PTR)
406 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
409 for (loop = bb->loop_father;
410 loop != e->dest->loop_father;
413 /* If we have already seen an exit, mark this by the edge that
414 surely does not occur as any exit. */
415 if (loop->single_exit)
416 loop->single_exit = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
418 loop->single_exit = e;
423 for (i = 1; i < loops->num; i++)
425 loop = loops->parray[i];
429 if (loop->single_exit == EDGE_SUCC (ENTRY_BLOCK_PTR, 0))
430 loop->single_exit = NULL;
433 loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
436 /* Find the root node of the loop pre-header extended basic block and
437 the edges along the trace from the root node to the loop header. */
440 flow_loop_pre_header_scan (struct loop *loop)
446 loop->num_pre_header_edges = 0;
447 if (loop->num_entries != 1)
450 ebb = loop->entry_edges[0]->src;
451 if (ebb == ENTRY_BLOCK_PTR)
454 /* Count number of edges along trace from loop header to
455 root of pre-header extended basic block. Usually this is
456 only one or two edges. */
458 EDGE_PRED (ebb, 0)->src != ENTRY_BLOCK_PTR && EDGE_COUNT (ebb->preds) == 1;
460 ebb = EDGE_PRED (ebb, 0)->src;
462 loop->pre_header_edges = xmalloc (num * sizeof (edge));
463 loop->num_pre_header_edges = num;
465 /* Store edges in order that they are followed. The source of the first edge
466 is the root node of the pre-header extended basic block and the
467 destination of the last last edge is the loop header. */
468 for (e = loop->entry_edges[0]; num; e = EDGE_PRED (e->src, 0))
469 loop->pre_header_edges[--num] = e;
472 /* Return the block for the pre-header of the loop with header
473 HEADER. Return NULL if there is no pre-header. */
476 flow_loop_pre_header_find (basic_block header)
478 basic_block pre_header;
482 /* If block p is a predecessor of the header and is the only block
483 that the header does not dominate, then it is the pre-header. */
485 FOR_EACH_EDGE (e, ei, header->preds)
487 basic_block node = e->src;
489 if (node != ENTRY_BLOCK_PTR
490 && ! dominated_by_p (CDI_DOMINATORS, node, header))
492 if (pre_header == NULL)
496 /* There are multiple edges into the header from outside
497 the loop so there is no pre-header block. */
508 establish_preds (struct loop *loop)
510 struct loop *ploop, *father = loop->outer;
512 loop->depth = father->depth + 1;
515 loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
516 memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
517 loop->pred[father->depth] = father;
519 for (ploop = loop->inner; ploop; ploop = ploop->next)
520 establish_preds (ploop);
523 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
524 added loop. If LOOP has some children, take care of that their
525 pred field will be initialized correctly. */
528 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
530 loop->next = father->inner;
531 father->inner = loop;
532 loop->outer = father;
534 establish_preds (loop);
537 /* Remove LOOP from the loop hierarchy tree. */
540 flow_loop_tree_node_remove (struct loop *loop)
542 struct loop *prev, *father;
544 father = loop->outer;
547 /* Remove loop from the list of sons. */
548 if (father->inner == loop)
549 father->inner = loop->next;
552 for (prev = father->inner; prev->next != loop; prev = prev->next);
553 prev->next = loop->next;
561 /* Helper function to compute loop nesting depth and enclosed loop level
562 for the natural loop specified by LOOP. Returns the loop level. */
565 flow_loop_level_compute (struct loop *loop)
573 /* Traverse loop tree assigning depth and computing level as the
574 maximum level of all the inner loops of this loop. The loop
575 level is equivalent to the height of the loop in the loop tree
576 and corresponds to the number of enclosed loop levels (including
578 for (inner = loop->inner; inner; inner = inner->next)
580 int ilevel = flow_loop_level_compute (inner) + 1;
590 /* Compute the loop nesting depth and enclosed loop level for the loop
591 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
595 flow_loops_level_compute (struct loops *loops)
597 return flow_loop_level_compute (loops->tree_root);
600 /* Scan a single natural loop specified by LOOP collecting information
601 about it specified by FLAGS. */
604 flow_loop_scan (struct loop *loop, int flags)
606 if (flags & LOOP_ENTRY_EDGES)
608 /* Find edges which enter the loop header.
609 Note that the entry edges should only
610 enter the header of a natural loop. */
611 flow_loop_entry_edges_find (loop);
614 if (flags & LOOP_EXIT_EDGES)
616 /* Find edges which exit the loop. */
617 flow_loop_exit_edges_find (loop);
620 if (flags & LOOP_PRE_HEADER)
622 /* Look to see if the loop has a pre-header node. */
623 loop->pre_header = flow_loop_pre_header_find (loop->header);
625 /* Find the blocks within the extended basic block of
626 the loop pre-header. */
627 flow_loop_pre_header_scan (loop);
633 /* A callback to update latch and header info for basic block JUMP created
634 by redirecting an edge. */
637 update_latch_info (basic_block jump)
639 alloc_aux_for_block (jump, sizeof (int));
640 HEADER_BLOCK (jump) = 0;
641 alloc_aux_for_edge (EDGE_PRED (jump, 0), sizeof (int));
642 LATCH_EDGE (EDGE_PRED (jump, 0)) = 0;
643 set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src);
646 /* A callback for make_forwarder block, to redirect all edges except for
647 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
648 whether to redirect it. */
650 static edge mfb_kj_edge;
652 mfb_keep_just (edge e)
654 return e != mfb_kj_edge;
657 /* A callback for make_forwarder block, to redirect the latch edges into an
658 entry part. E is the edge for that we should decide whether to redirect
662 mfb_keep_nonlatch (edge e)
664 return LATCH_EDGE (e);
667 /* Takes care of merging natural loops with shared headers. */
670 canonicalize_loop_headers (void)
675 alloc_aux_for_blocks (sizeof (int));
676 alloc_aux_for_edges (sizeof (int));
678 /* Split blocks so that each loop has only single latch. */
683 int have_abnormal_edge = 0;
685 FOR_EACH_EDGE (e, ei, header->preds)
687 basic_block latch = e->src;
689 if (e->flags & EDGE_ABNORMAL)
690 have_abnormal_edge = 1;
692 if (latch != ENTRY_BLOCK_PTR
693 && dominated_by_p (CDI_DOMINATORS, latch, header))
699 if (have_abnormal_edge)
700 HEADER_BLOCK (header) = 0;
702 HEADER_BLOCK (header) = num_latches;
705 if (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest))
709 /* We could not redirect edges freely here. On the other hand,
710 we can simply split the edge from entry block. */
711 bb = split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
713 alloc_aux_for_edge (EDGE_SUCC (bb, 0), sizeof (int));
714 LATCH_EDGE (EDGE_SUCC (bb, 0)) = 0;
715 alloc_aux_for_block (bb, sizeof (int));
716 HEADER_BLOCK (bb) = 0;
721 int max_freq, is_heavy;
722 edge heavy, tmp_edge;
725 if (HEADER_BLOCK (header) <= 1)
728 /* Find a heavy edge. */
732 FOR_EACH_EDGE (e, ei, header->preds)
733 if (LATCH_EDGE (e) &&
734 EDGE_FREQUENCY (e) > max_freq)
735 max_freq = EDGE_FREQUENCY (e);
736 FOR_EACH_EDGE (e, ei, header->preds)
737 if (LATCH_EDGE (e) &&
738 EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
751 /* Split out the heavy edge, and create inner loop for it. */
753 tmp_edge = make_forwarder_block (header, mfb_keep_just,
755 alloc_aux_for_block (tmp_edge->dest, sizeof (int));
756 HEADER_BLOCK (tmp_edge->dest) = 1;
757 alloc_aux_for_edge (tmp_edge, sizeof (int));
758 LATCH_EDGE (tmp_edge) = 0;
759 HEADER_BLOCK (header)--;
762 if (HEADER_BLOCK (header) > 1)
764 /* Create a new latch block. */
765 tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
767 alloc_aux_for_block (tmp_edge->dest, sizeof (int));
768 HEADER_BLOCK (tmp_edge->src) = 0;
769 HEADER_BLOCK (tmp_edge->dest) = 1;
770 alloc_aux_for_edge (tmp_edge, sizeof (int));
771 LATCH_EDGE (tmp_edge) = 1;
775 free_aux_for_blocks ();
776 free_aux_for_edges ();
778 #ifdef ENABLE_CHECKING
779 verify_dominators (CDI_DOMINATORS);
783 /* Initialize all the parallel_p fields of the loops structure to true. */
786 initialize_loops_parallel_p (struct loops *loops)
790 for (i = 0; i < loops->num; i++)
792 struct loop *loop = loops->parray[i];
793 loop->parallel_p = true;
797 /* Find all the natural loops in the function and save in LOOPS structure and
798 recalculate loop_depth information in basic block structures. FLAGS
799 controls which loop information is collected. Return the number of natural
803 flow_loops_find (struct loops *loops, int flags)
815 /* This function cannot be repeatedly called with different
816 flags to build up the loop information. The loop tree
817 must always be built if this function is called. */
818 gcc_assert (flags & LOOP_TREE);
820 memset (loops, 0, sizeof *loops);
822 /* Taking care of this degenerate case makes the rest of
823 this code simpler. */
824 if (n_basic_blocks == 0)
830 /* Ensure that the dominators are computed. */
831 calculate_dominance_info (CDI_DOMINATORS);
833 /* Join loops with shared headers. */
834 canonicalize_loop_headers ();
836 /* Count the number of loop headers. This should be the
837 same as the number of natural loops. */
838 headers = sbitmap_alloc (last_basic_block);
839 sbitmap_zero (headers);
845 int more_latches = 0;
847 header->loop_depth = 0;
849 /* If we have an abnormal predecessor, do not consider the
850 loop (not worth the problems). */
851 FOR_EACH_EDGE (e, ei, header->preds)
852 if (e->flags & EDGE_ABNORMAL)
857 FOR_EACH_EDGE (e, ei, header->preds)
859 basic_block latch = e->src;
861 gcc_assert (!(e->flags & EDGE_ABNORMAL));
863 /* Look for back edges where a predecessor is dominated
864 by this block. A natural loop has a single entry
865 node (header) that dominates all the nodes in the
866 loop. It also has single back edge to the header
867 from a latch node. */
868 if (latch != ENTRY_BLOCK_PTR
869 && dominated_by_p (CDI_DOMINATORS, latch, header))
871 /* Shared headers should be eliminated by now. */
872 gcc_assert (!more_latches);
874 SET_BIT (headers, header->index);
880 /* Allocate loop structures. */
881 loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *));
883 /* Dummy loop containing whole function. */
884 loops->parray[0] = xcalloc (1, sizeof (struct loop));
885 loops->parray[0]->next = NULL;
886 loops->parray[0]->inner = NULL;
887 loops->parray[0]->outer = NULL;
888 loops->parray[0]->depth = 0;
889 loops->parray[0]->pred = NULL;
890 loops->parray[0]->num_nodes = n_basic_blocks + 2;
891 loops->parray[0]->latch = EXIT_BLOCK_PTR;
892 loops->parray[0]->header = ENTRY_BLOCK_PTR;
893 ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
894 EXIT_BLOCK_PTR->loop_father = loops->parray[0];
896 loops->tree_root = loops->parray[0];
898 /* Find and record information about all the natural loops
902 bb->loop_father = loops->tree_root;
906 /* Compute depth first search order of the CFG so that outer
907 natural loops will be found before inner natural loops. */
908 dfs_order = xmalloc (n_basic_blocks * sizeof (int));
909 rc_order = xmalloc (n_basic_blocks * sizeof (int));
910 flow_depth_first_order_compute (dfs_order, rc_order);
912 /* Save CFG derived information to avoid recomputing it. */
913 loops->cfg.dfs_order = dfs_order;
914 loops->cfg.rc_order = rc_order;
918 for (b = 0; b < n_basic_blocks; b++)
923 /* Search the nodes of the CFG in reverse completion order
924 so that we can find outer loops first. */
925 if (!TEST_BIT (headers, rc_order[b]))
928 header = BASIC_BLOCK (rc_order[b]);
930 loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
932 loop->header = header;
933 loop->num = num_loops;
936 /* Look for the latch for this header block. */
937 FOR_EACH_EDGE (e, ei, header->preds)
939 basic_block latch = e->src;
941 if (latch != ENTRY_BLOCK_PTR
942 && dominated_by_p (CDI_DOMINATORS, latch, header))
949 flow_loop_tree_node_add (header->loop_father, loop);
950 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
953 /* Assign the loop nesting depth and enclosed loop level for each
955 loops->levels = flow_loops_level_compute (loops);
957 /* Scan the loops. */
958 for (i = 1; i < num_loops; i++)
959 flow_loop_scan (loops->parray[i], flags);
961 loops->num = num_loops;
962 initialize_loops_parallel_p (loops);
965 sbitmap_free (headers);
968 #ifdef ENABLE_CHECKING
970 verify_loop_structure (loops);
976 /* Update the information regarding the loops in the CFG
977 specified by LOOPS. */
980 flow_loops_update (struct loops *loops, int flags)
982 /* One day we may want to update the current loop data. For now
983 throw away the old stuff and rebuild what we need. */
985 flow_loops_free (loops);
987 return flow_loops_find (loops, flags);
990 /* Return nonzero if basic block BB belongs to LOOP. */
992 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
994 struct loop *source_loop;
996 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
999 source_loop = bb->loop_father;
1000 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
1003 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
1006 flow_loop_outside_edge_p (const struct loop *loop, edge e)
1008 gcc_assert (e->dest == loop->header);
1009 return !flow_bb_inside_loop_p (loop, e->src);
1012 /* Enumeration predicate for get_loop_body. */
1014 glb_enum_p (basic_block bb, void *glb_header)
1016 return bb != (basic_block) glb_header;
1019 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
1020 order against direction of edges from latch. Specially, if
1021 header != latch, latch is the 1-st block. */
1023 get_loop_body (const struct loop *loop)
1025 basic_block *tovisit, bb;
1028 gcc_assert (loop->num_nodes);
1030 tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1031 tovisit[tv++] = loop->header;
1033 if (loop->latch == EXIT_BLOCK_PTR)
1035 /* There may be blocks unreachable from EXIT_BLOCK. */
1036 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2);
1039 tovisit[tv++] = EXIT_BLOCK_PTR;
1041 else if (loop->latch != loop->header)
1043 tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
1044 tovisit + 1, loop->num_nodes - 1,
1048 gcc_assert (tv == loop->num_nodes);
1052 /* Fills dominance descendants inside LOOP of the basic block BB into
1053 array TOVISIT from index *TV. */
1056 fill_sons_in_loop (const struct loop *loop, basic_block bb,
1057 basic_block *tovisit, int *tv)
1059 basic_block son, postpone = NULL;
1061 tovisit[(*tv)++] = bb;
1062 for (son = first_dom_son (CDI_DOMINATORS, bb);
1064 son = next_dom_son (CDI_DOMINATORS, son))
1066 if (!flow_bb_inside_loop_p (loop, son))
1069 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
1074 fill_sons_in_loop (loop, son, tovisit, tv);
1078 fill_sons_in_loop (loop, postpone, tovisit, tv);
1081 /* Gets body of a LOOP (that must be different from the outermost loop)
1082 sorted by dominance relation. Additionally, if a basic block s dominates
1083 the latch, then only blocks dominated by s are be after it. */
1086 get_loop_body_in_dom_order (const struct loop *loop)
1088 basic_block *tovisit;
1091 gcc_assert (loop->num_nodes);
1093 tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1095 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1098 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
1100 gcc_assert (tv == (int) loop->num_nodes);
1105 /* Get body of a LOOP in breadth first sort order. */
1108 get_loop_body_in_bfs_order (const struct loop *loop)
1110 basic_block *blocks;
1114 unsigned int vc = 1;
1116 gcc_assert (loop->num_nodes);
1117 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1119 blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
1120 visited = BITMAP_XMALLOC ();
1123 while (i < loop->num_nodes)
1128 if (!bitmap_bit_p (visited, bb->index))
1130 /* This basic block is now visited */
1131 bitmap_set_bit (visited, bb->index);
1135 FOR_EACH_EDGE (e, ei, bb->succs)
1137 if (flow_bb_inside_loop_p (loop, e->dest))
1139 if (!bitmap_bit_p (visited, e->dest->index))
1141 bitmap_set_bit (visited, e->dest->index);
1142 blocks[i++] = e->dest;
1147 gcc_assert (i >= vc);
1152 BITMAP_XFREE (visited);
1156 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1158 get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)
1165 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1167 body = get_loop_body (loop);
1169 for (i = 0; i < loop->num_nodes; i++)
1170 FOR_EACH_EDGE (e, ei, body[i]->succs)
1171 if (!flow_bb_inside_loop_p (loop, e->dest))
1173 edges = xmalloc (n * sizeof (edge));
1176 for (i = 0; i < loop->num_nodes; i++)
1177 FOR_EACH_EDGE (e, ei, body[i]->succs)
1178 if (!flow_bb_inside_loop_p (loop, e->dest))
1185 /* Counts the number of conditional branches inside LOOP. */
1188 num_loop_branches (const struct loop *loop)
1193 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1195 body = get_loop_body (loop);
1197 for (i = 0; i < loop->num_nodes; i++)
1198 if (EDGE_COUNT (body[i]->succs) >= 2)
1205 /* Adds basic block BB to LOOP. */
1207 add_bb_to_loop (basic_block bb, struct loop *loop)
1211 bb->loop_father = loop;
1212 bb->loop_depth = loop->depth;
1214 for (i = 0; i < loop->depth; i++)
1215 loop->pred[i]->num_nodes++;
1218 /* Remove basic block BB from loops. */
1220 remove_bb_from_loops (basic_block bb)
1223 struct loop *loop = bb->loop_father;
1226 for (i = 0; i < loop->depth; i++)
1227 loop->pred[i]->num_nodes--;
1228 bb->loop_father = NULL;
1232 /* Finds nearest common ancestor in loop tree for given loops. */
1234 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1236 if (!loop_s) return loop_d;
1237 if (!loop_d) return loop_s;
1239 if (loop_s->depth < loop_d->depth)
1240 loop_d = loop_d->pred[loop_s->depth];
1241 else if (loop_s->depth > loop_d->depth)
1242 loop_s = loop_s->pred[loop_d->depth];
1244 while (loop_s != loop_d)
1246 loop_s = loop_s->outer;
1247 loop_d = loop_d->outer;
1252 /* Cancels the LOOP; it must be innermost one. */
1254 cancel_loop (struct loops *loops, struct loop *loop)
1259 gcc_assert (!loop->inner);
1261 /* Move blocks up one level (they should be removed as soon as possible). */
1262 bbs = get_loop_body (loop);
1263 for (i = 0; i < loop->num_nodes; i++)
1264 bbs[i]->loop_father = loop->outer;
1266 /* Remove the loop from structure. */
1267 flow_loop_tree_node_remove (loop);
1269 /* Remove loop from loops array. */
1270 loops->parray[loop->num] = NULL;
1272 /* Free loop data. */
1273 flow_loop_free (loop);
1276 /* Cancels LOOP and all its subloops. */
1278 cancel_loop_tree (struct loops *loops, struct loop *loop)
1281 cancel_loop_tree (loops, loop->inner);
1282 cancel_loop (loops, loop);
1285 /* Checks that LOOPS are all right:
1286 -- sizes of loops are all right
1287 -- results of get_loop_body really belong to the loop
1288 -- loop header have just single entry edge and single latch edge
1289 -- loop latches have only single successor that is header of their loop
1290 -- irreducible loops are correctly marked
1293 verify_loop_structure (struct loops *loops)
1295 unsigned *sizes, i, j;
1297 basic_block *bbs, bb;
1303 sizes = xcalloc (loops->num, sizeof (int));
1307 for (loop = bb->loop_father; loop; loop = loop->outer)
1310 for (i = 0; i < loops->num; i++)
1312 if (!loops->parray[i])
1315 if (loops->parray[i]->num_nodes != sizes[i])
1317 error ("Size of loop %d should be %d, not %d.",
1318 i, sizes[i], loops->parray[i]->num_nodes);
1323 /* Check get_loop_body. */
1324 for (i = 1; i < loops->num; i++)
1326 loop = loops->parray[i];
1329 bbs = get_loop_body (loop);
1331 for (j = 0; j < loop->num_nodes; j++)
1332 if (!flow_bb_inside_loop_p (loop, bbs[j]))
1334 error ("Bb %d do not belong to loop %d.",
1341 /* Check headers and latches. */
1342 for (i = 1; i < loops->num; i++)
1344 loop = loops->parray[i];
1348 if ((loops->state & LOOPS_HAVE_PREHEADERS)
1349 && EDGE_COUNT (loop->header->preds) != 2)
1351 error ("Loop %d's header does not have exactly 2 entries.", i);
1354 if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1356 if (EDGE_COUNT (loop->latch->succs) != 1)
1358 error ("Loop %d's latch does not have exactly 1 successor.", i);
1361 if (EDGE_SUCC (loop->latch, 0)->dest != loop->header)
1363 error ("Loop %d's latch does not have header as successor.", i);
1366 if (loop->latch->loop_father != loop)
1368 error ("Loop %d's latch does not belong directly to it.", i);
1372 if (loop->header->loop_father != loop)
1374 error ("Loop %d's header does not belong directly to it.", i);
1377 if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1378 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1380 error ("Loop %d's latch is marked as part of irreducible region.", i);
1385 /* Check irreducible loops. */
1386 if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1388 /* Record old info. */
1389 irreds = sbitmap_alloc (last_basic_block);
1393 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1394 SET_BIT (irreds, bb->index);
1396 RESET_BIT (irreds, bb->index);
1397 FOR_EACH_EDGE (e, ei, bb->succs)
1398 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1399 e->flags |= EDGE_ALL_FLAGS + 1;
1403 mark_irreducible_loops (loops);
1410 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1411 && !TEST_BIT (irreds, bb->index))
1413 error ("Basic block %d should be marked irreducible.", bb->index);
1416 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1417 && TEST_BIT (irreds, bb->index))
1419 error ("Basic block %d should not be marked irreducible.", bb->index);
1422 FOR_EACH_EDGE (e, ei, bb->succs)
1424 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1425 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1427 error ("Edge from %d to %d should be marked irreducible.",
1428 e->src->index, e->dest->index);
1431 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1432 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1434 error ("Edge from %d to %d should not be marked irreducible.",
1435 e->src->index, e->dest->index);
1438 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1444 /* Check the single_exit. */
1445 if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
1447 memset (sizes, 0, sizeof (unsigned) * loops->num);
1451 if (bb->loop_father == loops->tree_root)
1453 FOR_EACH_EDGE (e, ei, bb->succs)
1455 if (e->dest == EXIT_BLOCK_PTR)
1458 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1461 for (loop = bb->loop_father;
1462 loop != e->dest->loop_father;
1466 if (loop->single_exit
1467 && loop->single_exit != e)
1469 error ("Wrong single exit %d->%d recorded for loop %d.",
1470 loop->single_exit->src->index,
1471 loop->single_exit->dest->index,
1473 error ("Right exit is %d->%d.",
1474 e->src->index, e->dest->index);
1481 for (i = 1; i < loops->num; i++)
1483 loop = loops->parray[i];
1488 && !loop->single_exit)
1490 error ("Single exit not recorded for loop %d.", loop->num);
1495 && loop->single_exit)
1497 error ("Loop %d should not have single exit (%d -> %d).",
1499 loop->single_exit->src->index,
1500 loop->single_exit->dest->index);
1511 /* Returns latch edge of LOOP. */
1513 loop_latch_edge (const struct loop *loop)
1518 FOR_EACH_EDGE (e, ei, loop->header->preds)
1519 if (e->src == loop->latch)
1525 /* Returns preheader edge of LOOP. */
1527 loop_preheader_edge (const struct loop *loop)
1532 FOR_EACH_EDGE (e, ei, loop->header->preds)
1533 if (e->src != loop->latch)