Mark ChangeLog
[official-gcc.git] / gcc / cfgloop.c
blob40a6de489ccdb8bf436436436bf77adf6a7b4442
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
9 version.
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
14 for more details.
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
19 02111-1307, USA. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "function.h"
29 #include "basic-block.h"
30 #include "toplev.h"
31 #include "cfgloop.h"
32 #include "flags.h"
33 #include "tree.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 void flow_loop_entry_edges_find (struct loop *);
45 static void flow_loop_exit_edges_find (struct loop *);
46 static int flow_loop_nodes_find (basic_block, struct loop *);
47 static void flow_loop_pre_header_scan (struct loop *);
48 static basic_block flow_loop_pre_header_find (basic_block);
49 static int flow_loop_level_compute (struct loop *);
50 static void flow_loops_level_compute (struct loops *);
51 static void establish_preds (struct loop *);
52 static void canonicalize_loop_headers (void);
53 static bool glb_enum_p (basic_block, void *);
55 /* Dump loop related CFG information. */
57 static void
58 flow_loops_cfg_dump (const struct loops *loops, FILE *file)
60 int i;
61 basic_block bb;
63 if (! loops->num || ! file)
64 return;
66 FOR_EACH_BB (bb)
68 edge succ;
69 edge_iterator ei;
71 fprintf (file, ";; %d succs { ", bb->index);
72 FOR_EACH_EDGE (succ, ei, bb->succs)
73 fprintf (file, "%d ", succ->dest->index);
74 fprintf (file, "}\n");
77 /* Dump the DFS node order. */
78 if (loops->cfg.dfs_order)
80 fputs (";; DFS order: ", file);
81 for (i = 0; i < n_basic_blocks; i++)
82 fprintf (file, "%d ", loops->cfg.dfs_order[i]);
84 fputs ("\n", file);
87 /* Dump the reverse completion node order. */
88 if (loops->cfg.rc_order)
90 fputs (";; RC order: ", file);
91 for (i = 0; i < n_basic_blocks; i++)
92 fprintf (file, "%d ", loops->cfg.rc_order[i]);
94 fputs ("\n", file);
98 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
100 bool
101 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
103 return (loop->depth > outer->depth
104 && loop->pred[outer->depth] == outer);
107 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
108 loops within LOOP. */
110 struct loop *
111 superloop_at_depth (struct loop *loop, unsigned depth)
113 gcc_assert (depth <= (unsigned) loop->depth);
115 if (depth == (unsigned) loop->depth)
116 return loop;
118 return loop->pred[depth];
121 /* Dump the loop information specified by LOOP to the stream FILE
122 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
124 void
125 flow_loop_dump (const struct loop *loop, FILE *file,
126 void (*loop_dump_aux) (const struct loop *, FILE *, int),
127 int verbose)
129 basic_block *bbs;
130 unsigned i;
132 if (! loop || ! loop->header)
133 return;
135 fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
136 loop->invalid ? " invalid" : "");
138 fprintf (file, ";; header %d, latch %d, pre-header %d\n",
139 loop->header->index, loop->latch->index,
140 loop->pre_header ? loop->pre_header->index : -1);
141 fprintf (file, ";; depth %d, level %d, outer %ld\n",
142 loop->depth, loop->level,
143 (long) (loop->outer ? loop->outer->num : -1));
145 if (loop->pre_header_edges)
146 flow_edge_list_print (";; pre-header edges", loop->pre_header_edges,
147 loop->num_pre_header_edges, file);
149 flow_edge_list_print (";; entry edges", loop->entry_edges,
150 loop->num_entries, file);
151 fprintf (file, ";; nodes:");
152 bbs = get_loop_body (loop);
153 for (i = 0; i < loop->num_nodes; i++)
154 fprintf (file, " %d", bbs[i]->index);
155 free (bbs);
156 fprintf (file, "\n");
157 flow_edge_list_print (";; exit edges", loop->exit_edges,
158 loop->num_exits, file);
160 if (loop_dump_aux)
161 loop_dump_aux (loop, file, verbose);
164 /* Dump the loop information specified by LOOPS to the stream FILE,
165 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
167 void
168 flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
170 int i;
171 int num_loops;
173 num_loops = loops->num;
174 if (! num_loops || ! file)
175 return;
177 fprintf (file, ";; %d loops found\n", num_loops);
179 for (i = 0; i < num_loops; i++)
181 struct loop *loop = loops->parray[i];
183 if (!loop)
184 continue;
186 flow_loop_dump (loop, file, loop_dump_aux, verbose);
189 if (verbose)
190 flow_loops_cfg_dump (loops, file);
193 /* Free data allocated for LOOP. */
194 void
195 flow_loop_free (struct loop *loop)
197 if (loop->pre_header_edges)
198 free (loop->pre_header_edges);
199 if (loop->entry_edges)
200 free (loop->entry_edges);
201 if (loop->exit_edges)
202 free (loop->exit_edges);
203 if (loop->pred)
204 free (loop->pred);
205 free (loop);
208 /* Free all the memory allocated for LOOPS. */
210 void
211 flow_loops_free (struct loops *loops)
213 if (loops->parray)
215 unsigned i;
217 gcc_assert (loops->num);
219 /* Free the loop descriptors. */
220 for (i = 0; i < loops->num; i++)
222 struct loop *loop = loops->parray[i];
224 if (!loop)
225 continue;
227 flow_loop_free (loop);
230 free (loops->parray);
231 loops->parray = NULL;
233 if (loops->cfg.dfs_order)
234 free (loops->cfg.dfs_order);
235 if (loops->cfg.rc_order)
236 free (loops->cfg.rc_order);
241 /* Find the entry edges into the LOOP. */
243 static void
244 flow_loop_entry_edges_find (struct loop *loop)
246 edge e;
247 edge_iterator ei;
248 int num_entries;
250 num_entries = 0;
251 FOR_EACH_EDGE (e, ei, loop->header->preds)
253 if (flow_loop_outside_edge_p (loop, e))
254 num_entries++;
257 gcc_assert (num_entries);
259 loop->entry_edges = xmalloc (num_entries * sizeof (edge *));
261 num_entries = 0;
262 FOR_EACH_EDGE (e, ei, loop->header->preds)
264 if (flow_loop_outside_edge_p (loop, e))
265 loop->entry_edges[num_entries++] = e;
268 loop->num_entries = num_entries;
271 /* Find the exit edges from the LOOP. */
273 static void
274 flow_loop_exit_edges_find (struct loop *loop)
276 edge e;
277 basic_block node, *bbs;
278 unsigned num_exits, i;
280 loop->exit_edges = NULL;
281 loop->num_exits = 0;
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
285 exiting edges. */
286 num_exits = 0;
287 bbs = get_loop_body (loop);
288 for (i = 0; i < loop->num_nodes; i++)
290 edge_iterator ei;
291 node = bbs[i];
292 FOR_EACH_EDGE (e, ei, node->succs)
294 basic_block dest = e->dest;
296 if (!flow_bb_inside_loop_p (loop, dest))
297 num_exits++;
301 if (! num_exits)
303 free (bbs);
304 return;
307 loop->exit_edges = xmalloc (num_exits * sizeof (edge *));
309 /* Store all exiting edges into an array. */
310 num_exits = 0;
311 for (i = 0; i < loop->num_nodes; i++)
313 edge_iterator ei;
314 node = bbs[i];
315 FOR_EACH_EDGE (e, ei, node->succs)
317 basic_block dest = e->dest;
319 if (!flow_bb_inside_loop_p (loop, dest))
321 e->flags |= EDGE_LOOP_EXIT;
322 loop->exit_edges[num_exits++] = e;
326 free (bbs);
327 loop->num_exits = num_exits;
330 /* Find the nodes contained within the LOOP with header HEADER.
331 Return the number of nodes within the loop. */
333 static int
334 flow_loop_nodes_find (basic_block header, struct loop *loop)
336 basic_block *stack;
337 int sp;
338 int num_nodes = 1;
340 header->loop_father = loop;
341 header->loop_depth = loop->depth;
343 if (loop->latch->loop_father != loop)
345 stack = xmalloc (n_basic_blocks * sizeof (basic_block));
346 sp = 0;
347 num_nodes++;
348 stack[sp++] = loop->latch;
349 loop->latch->loop_father = loop;
350 loop->latch->loop_depth = loop->depth;
352 while (sp)
354 basic_block node;
355 edge e;
356 edge_iterator ei;
358 node = stack[--sp];
360 FOR_EACH_EDGE (e, ei, node->preds)
362 basic_block ancestor = e->src;
364 if (ancestor != ENTRY_BLOCK_PTR
365 && ancestor->loop_father != loop)
367 ancestor->loop_father = loop;
368 ancestor->loop_depth = loop->depth;
369 num_nodes++;
370 stack[sp++] = ancestor;
374 free (stack);
376 return num_nodes;
379 /* For each loop in the lOOPS tree that has just a single exit
380 record the exit edge. */
382 void
383 mark_single_exit_loops (struct loops *loops)
385 basic_block bb;
386 edge e;
387 struct loop *loop;
388 unsigned i;
390 for (i = 1; i < loops->num; i++)
392 loop = loops->parray[i];
393 if (loop)
394 loop->single_exit = NULL;
397 FOR_EACH_BB (bb)
399 edge_iterator ei;
400 if (bb->loop_father == loops->tree_root)
401 continue;
402 FOR_EACH_EDGE (e, ei, bb->succs)
404 if (e->dest == EXIT_BLOCK_PTR)
405 continue;
407 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
408 continue;
410 for (loop = bb->loop_father;
411 loop != e->dest->loop_father;
412 loop = loop->outer)
414 /* If we have already seen an exit, mark this by the edge that
415 surely does not occur as any exit. */
416 if (loop->single_exit)
417 loop->single_exit = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
418 else
419 loop->single_exit = e;
424 for (i = 1; i < loops->num; i++)
426 loop = loops->parray[i];
427 if (!loop)
428 continue;
430 if (loop->single_exit == EDGE_SUCC (ENTRY_BLOCK_PTR, 0))
431 loop->single_exit = NULL;
434 loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
437 /* Find the root node of the loop pre-header extended basic block and
438 the edges along the trace from the root node to the loop header. */
440 static void
441 flow_loop_pre_header_scan (struct loop *loop)
443 int num;
444 basic_block ebb;
445 edge e;
447 loop->num_pre_header_edges = 0;
448 if (loop->num_entries != 1)
449 return;
451 ebb = loop->entry_edges[0]->src;
452 if (ebb == ENTRY_BLOCK_PTR)
453 return;
455 /* Count number of edges along trace from loop header to
456 root of pre-header extended basic block. Usually this is
457 only one or two edges. */
458 for (num = 1;
459 EDGE_PRED (ebb, 0)->src != ENTRY_BLOCK_PTR && EDGE_COUNT (ebb->preds) == 1;
460 num++)
461 ebb = EDGE_PRED (ebb, 0)->src;
463 loop->pre_header_edges = xmalloc (num * sizeof (edge));
464 loop->num_pre_header_edges = num;
466 /* Store edges in order that they are followed. The source of the first edge
467 is the root node of the pre-header extended basic block and the
468 destination of the last last edge is the loop header. */
469 for (e = loop->entry_edges[0]; num; e = EDGE_PRED (e->src, 0))
470 loop->pre_header_edges[--num] = e;
473 /* Return the block for the pre-header of the loop with header
474 HEADER. Return NULL if there is no pre-header. */
476 static basic_block
477 flow_loop_pre_header_find (basic_block header)
479 basic_block pre_header;
480 edge e;
481 edge_iterator ei;
483 /* If block p is a predecessor of the header and is the only block
484 that the header does not dominate, then it is the pre-header. */
485 pre_header = NULL;
486 FOR_EACH_EDGE (e, ei, header->preds)
488 basic_block node = e->src;
490 if (node != ENTRY_BLOCK_PTR
491 && ! dominated_by_p (CDI_DOMINATORS, node, header))
493 if (pre_header == NULL)
494 pre_header = node;
495 else
497 /* There are multiple edges into the header from outside
498 the loop so there is no pre-header block. */
499 pre_header = NULL;
500 break;
505 return pre_header;
508 static void
509 establish_preds (struct loop *loop)
511 struct loop *ploop, *father = loop->outer;
513 loop->depth = father->depth + 1;
515 /* Remember the current loop depth if it is the largest seen so far. */
516 cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
518 if (loop->pred)
519 free (loop->pred);
520 loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
521 memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
522 loop->pred[father->depth] = father;
524 for (ploop = loop->inner; ploop; ploop = ploop->next)
525 establish_preds (ploop);
528 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
529 added loop. If LOOP has some children, take care of that their
530 pred field will be initialized correctly. */
532 void
533 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
535 loop->next = father->inner;
536 father->inner = loop;
537 loop->outer = father;
539 establish_preds (loop);
542 /* Remove LOOP from the loop hierarchy tree. */
544 void
545 flow_loop_tree_node_remove (struct loop *loop)
547 struct loop *prev, *father;
549 father = loop->outer;
550 loop->outer = NULL;
552 /* Remove loop from the list of sons. */
553 if (father->inner == loop)
554 father->inner = loop->next;
555 else
557 for (prev = father->inner; prev->next != loop; prev = prev->next);
558 prev->next = loop->next;
561 loop->depth = -1;
562 free (loop->pred);
563 loop->pred = NULL;
566 /* Helper function to compute loop nesting depth and enclosed loop level
567 for the natural loop specified by LOOP. Returns the loop level. */
569 static int
570 flow_loop_level_compute (struct loop *loop)
572 struct loop *inner;
573 int level = 1;
575 if (! loop)
576 return 0;
578 /* Traverse loop tree assigning depth and computing level as the
579 maximum level of all the inner loops of this loop. The loop
580 level is equivalent to the height of the loop in the loop tree
581 and corresponds to the number of enclosed loop levels (including
582 itself). */
583 for (inner = loop->inner; inner; inner = inner->next)
585 int ilevel = flow_loop_level_compute (inner) + 1;
587 if (ilevel > level)
588 level = ilevel;
591 loop->level = level;
592 return level;
595 /* Compute the loop nesting depth and enclosed loop level for the loop
596 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
597 level. */
599 static void
600 flow_loops_level_compute (struct loops *loops)
602 flow_loop_level_compute (loops->tree_root);
605 /* Scan a single natural loop specified by LOOP collecting information
606 about it specified by FLAGS. */
609 flow_loop_scan (struct loop *loop, int flags)
611 if (flags & LOOP_ENTRY_EDGES)
613 /* Find edges which enter the loop header.
614 Note that the entry edges should only
615 enter the header of a natural loop. */
616 flow_loop_entry_edges_find (loop);
619 if (flags & LOOP_EXIT_EDGES)
621 /* Find edges which exit the loop. */
622 flow_loop_exit_edges_find (loop);
625 if (flags & LOOP_PRE_HEADER)
627 /* Look to see if the loop has a pre-header node. */
628 loop->pre_header = flow_loop_pre_header_find (loop->header);
630 /* Find the blocks within the extended basic block of
631 the loop pre-header. */
632 flow_loop_pre_header_scan (loop);
635 return 1;
638 /* A callback to update latch and header info for basic block JUMP created
639 by redirecting an edge. */
641 static void
642 update_latch_info (basic_block jump)
644 alloc_aux_for_block (jump, sizeof (int));
645 HEADER_BLOCK (jump) = 0;
646 alloc_aux_for_edge (EDGE_PRED (jump, 0), sizeof (int));
647 LATCH_EDGE (EDGE_PRED (jump, 0)) = 0;
648 set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src);
651 /* A callback for make_forwarder block, to redirect all edges except for
652 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
653 whether to redirect it. */
655 static edge mfb_kj_edge;
656 static bool
657 mfb_keep_just (edge e)
659 return e != mfb_kj_edge;
662 /* A callback for make_forwarder block, to redirect the latch edges into an
663 entry part. E is the edge for that we should decide whether to redirect
664 it. */
666 static bool
667 mfb_keep_nonlatch (edge e)
669 return LATCH_EDGE (e);
672 /* Takes care of merging natural loops with shared headers. */
674 static void
675 canonicalize_loop_headers (void)
677 basic_block header;
678 edge e;
680 alloc_aux_for_blocks (sizeof (int));
681 alloc_aux_for_edges (sizeof (int));
683 /* Split blocks so that each loop has only single latch. */
684 FOR_EACH_BB (header)
686 edge_iterator ei;
687 int num_latches = 0;
688 int have_abnormal_edge = 0;
690 FOR_EACH_EDGE (e, ei, header->preds)
692 basic_block latch = e->src;
694 if (e->flags & EDGE_ABNORMAL)
695 have_abnormal_edge = 1;
697 if (latch != ENTRY_BLOCK_PTR
698 && dominated_by_p (CDI_DOMINATORS, latch, header))
700 num_latches++;
701 LATCH_EDGE (e) = 1;
704 if (have_abnormal_edge)
705 HEADER_BLOCK (header) = 0;
706 else
707 HEADER_BLOCK (header) = num_latches;
710 if (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest))
712 basic_block bb;
714 /* We could not redirect edges freely here. On the other hand,
715 we can simply split the edge from entry block. */
716 bb = split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
718 alloc_aux_for_edge (EDGE_SUCC (bb, 0), sizeof (int));
719 LATCH_EDGE (EDGE_SUCC (bb, 0)) = 0;
720 alloc_aux_for_block (bb, sizeof (int));
721 HEADER_BLOCK (bb) = 0;
724 FOR_EACH_BB (header)
726 int max_freq, is_heavy;
727 edge heavy, tmp_edge;
728 edge_iterator ei;
730 if (HEADER_BLOCK (header) <= 1)
731 continue;
733 /* Find a heavy edge. */
734 is_heavy = 1;
735 heavy = NULL;
736 max_freq = 0;
737 FOR_EACH_EDGE (e, ei, header->preds)
738 if (LATCH_EDGE (e) &&
739 EDGE_FREQUENCY (e) > max_freq)
740 max_freq = EDGE_FREQUENCY (e);
741 FOR_EACH_EDGE (e, ei, header->preds)
742 if (LATCH_EDGE (e) &&
743 EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
745 if (heavy)
747 is_heavy = 0;
748 break;
750 else
751 heavy = e;
754 if (is_heavy)
756 /* Split out the heavy edge, and create inner loop for it. */
757 mfb_kj_edge = heavy;
758 tmp_edge = make_forwarder_block (header, mfb_keep_just,
759 update_latch_info);
760 alloc_aux_for_block (tmp_edge->dest, sizeof (int));
761 HEADER_BLOCK (tmp_edge->dest) = 1;
762 alloc_aux_for_edge (tmp_edge, sizeof (int));
763 LATCH_EDGE (tmp_edge) = 0;
764 HEADER_BLOCK (header)--;
767 if (HEADER_BLOCK (header) > 1)
769 /* Create a new latch block. */
770 tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
771 update_latch_info);
772 alloc_aux_for_block (tmp_edge->dest, sizeof (int));
773 HEADER_BLOCK (tmp_edge->src) = 0;
774 HEADER_BLOCK (tmp_edge->dest) = 1;
775 alloc_aux_for_edge (tmp_edge, sizeof (int));
776 LATCH_EDGE (tmp_edge) = 1;
780 free_aux_for_blocks ();
781 free_aux_for_edges ();
783 #ifdef ENABLE_CHECKING
784 verify_dominators (CDI_DOMINATORS);
785 #endif
788 /* Initialize all the parallel_p fields of the loops structure to true. */
790 static void
791 initialize_loops_parallel_p (struct loops *loops)
793 unsigned int i;
795 for (i = 0; i < loops->num; i++)
797 struct loop *loop = loops->parray[i];
798 loop->parallel_p = true;
802 /* Find all the natural loops in the function and save in LOOPS structure and
803 recalculate loop_depth information in basic block structures. FLAGS
804 controls which loop information is collected. Return the number of natural
805 loops found. */
808 flow_loops_find (struct loops *loops, int flags)
810 int i;
811 int b;
812 int num_loops;
813 edge e;
814 sbitmap headers;
815 int *dfs_order;
816 int *rc_order;
817 basic_block header;
818 basic_block bb;
820 /* This function cannot be repeatedly called with different
821 flags to build up the loop information. The loop tree
822 must always be built if this function is called. */
823 gcc_assert (flags & LOOP_TREE);
825 memset (loops, 0, sizeof *loops);
827 /* We are going to recount the maximum loop depth,
828 so throw away the last count. */
829 cfun->max_loop_depth = 0;
831 /* Taking care of this degenerate case makes the rest of
832 this code simpler. */
833 if (n_basic_blocks == 0)
834 return 0;
836 dfs_order = NULL;
837 rc_order = NULL;
839 /* Ensure that the dominators are computed. */
840 calculate_dominance_info (CDI_DOMINATORS);
842 /* Join loops with shared headers. */
843 canonicalize_loop_headers ();
845 /* Count the number of loop headers. This should be the
846 same as the number of natural loops. */
847 headers = sbitmap_alloc (last_basic_block);
848 sbitmap_zero (headers);
850 num_loops = 0;
851 FOR_EACH_BB (header)
853 edge_iterator ei;
854 int more_latches = 0;
856 header->loop_depth = 0;
858 /* If we have an abnormal predecessor, do not consider the
859 loop (not worth the problems). */
860 FOR_EACH_EDGE (e, ei, header->preds)
861 if (e->flags & EDGE_ABNORMAL)
862 break;
863 if (e)
864 continue;
866 FOR_EACH_EDGE (e, ei, header->preds)
868 basic_block latch = e->src;
870 gcc_assert (!(e->flags & EDGE_ABNORMAL));
872 /* Look for back edges where a predecessor is dominated
873 by this block. A natural loop has a single entry
874 node (header) that dominates all the nodes in the
875 loop. It also has single back edge to the header
876 from a latch node. */
877 if (latch != ENTRY_BLOCK_PTR
878 && dominated_by_p (CDI_DOMINATORS, latch, header))
880 /* Shared headers should be eliminated by now. */
881 gcc_assert (!more_latches);
882 more_latches = 1;
883 SET_BIT (headers, header->index);
884 num_loops++;
889 /* Allocate loop structures. */
890 loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *));
892 /* Dummy loop containing whole function. */
893 loops->parray[0] = xcalloc (1, sizeof (struct loop));
894 loops->parray[0]->next = NULL;
895 loops->parray[0]->inner = NULL;
896 loops->parray[0]->outer = NULL;
897 loops->parray[0]->depth = 0;
898 loops->parray[0]->pred = NULL;
899 loops->parray[0]->num_nodes = n_basic_blocks + 2;
900 loops->parray[0]->latch = EXIT_BLOCK_PTR;
901 loops->parray[0]->header = ENTRY_BLOCK_PTR;
902 ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
903 EXIT_BLOCK_PTR->loop_father = loops->parray[0];
905 loops->tree_root = loops->parray[0];
907 /* Find and record information about all the natural loops
908 in the CFG. */
909 loops->num = 1;
910 FOR_EACH_BB (bb)
911 bb->loop_father = loops->tree_root;
913 if (num_loops)
915 /* Compute depth first search order of the CFG so that outer
916 natural loops will be found before inner natural loops. */
917 dfs_order = xmalloc (n_basic_blocks * sizeof (int));
918 rc_order = xmalloc (n_basic_blocks * sizeof (int));
919 flow_depth_first_order_compute (dfs_order, rc_order);
921 /* Save CFG derived information to avoid recomputing it. */
922 loops->cfg.dfs_order = dfs_order;
923 loops->cfg.rc_order = rc_order;
925 num_loops = 1;
927 for (b = 0; b < n_basic_blocks; b++)
929 struct loop *loop;
930 edge_iterator ei;
932 /* Search the nodes of the CFG in reverse completion order
933 so that we can find outer loops first. */
934 if (!TEST_BIT (headers, rc_order[b]))
935 continue;
937 header = BASIC_BLOCK (rc_order[b]);
939 loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
941 loop->header = header;
942 loop->num = num_loops;
943 num_loops++;
945 /* Look for the latch for this header block. */
946 FOR_EACH_EDGE (e, ei, header->preds)
948 basic_block latch = e->src;
950 if (latch != ENTRY_BLOCK_PTR
951 && dominated_by_p (CDI_DOMINATORS, latch, header))
953 loop->latch = latch;
954 break;
958 flow_loop_tree_node_add (header->loop_father, loop);
959 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
962 /* Assign the loop nesting depth and enclosed loop level for each
963 loop. */
964 flow_loops_level_compute (loops);
966 /* Scan the loops. */
967 for (i = 1; i < num_loops; i++)
968 flow_loop_scan (loops->parray[i], flags);
970 loops->num = num_loops;
971 initialize_loops_parallel_p (loops);
974 sbitmap_free (headers);
976 loops->state = 0;
977 #ifdef ENABLE_CHECKING
978 verify_flow_info ();
979 verify_loop_structure (loops);
980 #endif
982 return loops->num;
985 /* Return nonzero if basic block BB belongs to LOOP. */
986 bool
987 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
989 struct loop *source_loop;
991 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
992 return 0;
994 source_loop = bb->loop_father;
995 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
998 /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */
1000 bool
1001 flow_loop_outside_edge_p (const struct loop *loop, edge e)
1003 gcc_assert (e->dest == loop->header);
1004 return !flow_bb_inside_loop_p (loop, e->src);
1007 /* Enumeration predicate for get_loop_body. */
1008 static bool
1009 glb_enum_p (basic_block bb, void *glb_header)
1011 return bb != (basic_block) glb_header;
1014 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
1015 order against direction of edges from latch. Specially, if
1016 header != latch, latch is the 1-st block. */
1017 basic_block *
1018 get_loop_body (const struct loop *loop)
1020 basic_block *tovisit, bb;
1021 unsigned tv = 0;
1023 gcc_assert (loop->num_nodes);
1025 tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1026 tovisit[tv++] = loop->header;
1028 if (loop->latch == EXIT_BLOCK_PTR)
1030 /* There may be blocks unreachable from EXIT_BLOCK. */
1031 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2);
1032 FOR_EACH_BB (bb)
1033 tovisit[tv++] = bb;
1034 tovisit[tv++] = EXIT_BLOCK_PTR;
1036 else if (loop->latch != loop->header)
1038 tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
1039 tovisit + 1, loop->num_nodes - 1,
1040 loop->header) + 1;
1043 gcc_assert (tv == loop->num_nodes);
1044 return tovisit;
1047 /* Fills dominance descendants inside LOOP of the basic block BB into
1048 array TOVISIT from index *TV. */
1050 static void
1051 fill_sons_in_loop (const struct loop *loop, basic_block bb,
1052 basic_block *tovisit, int *tv)
1054 basic_block son, postpone = NULL;
1056 tovisit[(*tv)++] = bb;
1057 for (son = first_dom_son (CDI_DOMINATORS, bb);
1058 son;
1059 son = next_dom_son (CDI_DOMINATORS, son))
1061 if (!flow_bb_inside_loop_p (loop, son))
1062 continue;
1064 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
1066 postpone = son;
1067 continue;
1069 fill_sons_in_loop (loop, son, tovisit, tv);
1072 if (postpone)
1073 fill_sons_in_loop (loop, postpone, tovisit, tv);
1076 /* Gets body of a LOOP (that must be different from the outermost loop)
1077 sorted by dominance relation. Additionally, if a basic block s dominates
1078 the latch, then only blocks dominated by s are be after it. */
1080 basic_block *
1081 get_loop_body_in_dom_order (const struct loop *loop)
1083 basic_block *tovisit;
1084 int tv;
1086 gcc_assert (loop->num_nodes);
1088 tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1090 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1092 tv = 0;
1093 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
1095 gcc_assert (tv == (int) loop->num_nodes);
1097 return tovisit;
1100 /* Get body of a LOOP in breadth first sort order. */
1102 basic_block *
1103 get_loop_body_in_bfs_order (const struct loop *loop)
1105 basic_block *blocks;
1106 basic_block bb;
1107 bitmap visited;
1108 unsigned int i = 0;
1109 unsigned int vc = 1;
1111 gcc_assert (loop->num_nodes);
1112 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1114 blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
1115 visited = BITMAP_ALLOC (NULL);
1117 bb = loop->header;
1118 while (i < loop->num_nodes)
1120 edge e;
1121 edge_iterator ei;
1123 if (!bitmap_bit_p (visited, bb->index))
1125 /* This basic block is now visited */
1126 bitmap_set_bit (visited, bb->index);
1127 blocks[i++] = bb;
1130 FOR_EACH_EDGE (e, ei, bb->succs)
1132 if (flow_bb_inside_loop_p (loop, e->dest))
1134 if (!bitmap_bit_p (visited, e->dest->index))
1136 bitmap_set_bit (visited, e->dest->index);
1137 blocks[i++] = e->dest;
1142 gcc_assert (i >= vc);
1144 bb = blocks[vc++];
1147 BITMAP_FREE (visited);
1148 return blocks;
1151 /* Gets exit edges of a LOOP, returning their number in N_EDGES. */
1152 edge *
1153 get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)
1155 edge *edges, e;
1156 unsigned i, n;
1157 basic_block * body;
1158 edge_iterator ei;
1160 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1162 body = get_loop_body (loop);
1163 n = 0;
1164 for (i = 0; i < loop->num_nodes; i++)
1165 FOR_EACH_EDGE (e, ei, body[i]->succs)
1166 if (!flow_bb_inside_loop_p (loop, e->dest))
1167 n++;
1168 edges = xmalloc (n * sizeof (edge));
1169 *n_edges = n;
1170 n = 0;
1171 for (i = 0; i < loop->num_nodes; i++)
1172 FOR_EACH_EDGE (e, ei, body[i]->succs)
1173 if (!flow_bb_inside_loop_p (loop, e->dest))
1174 edges[n++] = e;
1175 free (body);
1177 return edges;
1180 /* Counts the number of conditional branches inside LOOP. */
1182 unsigned
1183 num_loop_branches (const struct loop *loop)
1185 unsigned i, n;
1186 basic_block * body;
1188 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1190 body = get_loop_body (loop);
1191 n = 0;
1192 for (i = 0; i < loop->num_nodes; i++)
1193 if (EDGE_COUNT (body[i]->succs) >= 2)
1194 n++;
1195 free (body);
1197 return n;
1200 /* Adds basic block BB to LOOP. */
1201 void
1202 add_bb_to_loop (basic_block bb, struct loop *loop)
1204 int i;
1206 bb->loop_father = loop;
1207 bb->loop_depth = loop->depth;
1208 loop->num_nodes++;
1209 for (i = 0; i < loop->depth; i++)
1210 loop->pred[i]->num_nodes++;
1213 /* Remove basic block BB from loops. */
1214 void
1215 remove_bb_from_loops (basic_block bb)
1217 int i;
1218 struct loop *loop = bb->loop_father;
1220 loop->num_nodes--;
1221 for (i = 0; i < loop->depth; i++)
1222 loop->pred[i]->num_nodes--;
1223 bb->loop_father = NULL;
1224 bb->loop_depth = 0;
1227 /* Finds nearest common ancestor in loop tree for given loops. */
1228 struct loop *
1229 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1231 if (!loop_s) return loop_d;
1232 if (!loop_d) return loop_s;
1234 if (loop_s->depth < loop_d->depth)
1235 loop_d = loop_d->pred[loop_s->depth];
1236 else if (loop_s->depth > loop_d->depth)
1237 loop_s = loop_s->pred[loop_d->depth];
1239 while (loop_s != loop_d)
1241 loop_s = loop_s->outer;
1242 loop_d = loop_d->outer;
1244 return loop_s;
1247 /* Cancels the LOOP; it must be innermost one. */
1248 void
1249 cancel_loop (struct loops *loops, struct loop *loop)
1251 basic_block *bbs;
1252 unsigned i;
1254 gcc_assert (!loop->inner);
1256 /* Move blocks up one level (they should be removed as soon as possible). */
1257 bbs = get_loop_body (loop);
1258 for (i = 0; i < loop->num_nodes; i++)
1259 bbs[i]->loop_father = loop->outer;
1261 /* Remove the loop from structure. */
1262 flow_loop_tree_node_remove (loop);
1264 /* Remove loop from loops array. */
1265 loops->parray[loop->num] = NULL;
1267 /* Free loop data. */
1268 flow_loop_free (loop);
1271 /* Cancels LOOP and all its subloops. */
1272 void
1273 cancel_loop_tree (struct loops *loops, struct loop *loop)
1275 while (loop->inner)
1276 cancel_loop_tree (loops, loop->inner);
1277 cancel_loop (loops, loop);
1280 /* Checks that LOOPS are all right:
1281 -- sizes of loops are all right
1282 -- results of get_loop_body really belong to the loop
1283 -- loop header have just single entry edge and single latch edge
1284 -- loop latches have only single successor that is header of their loop
1285 -- irreducible loops are correctly marked
1287 void
1288 verify_loop_structure (struct loops *loops)
1290 unsigned *sizes, i, j;
1291 sbitmap irreds;
1292 basic_block *bbs, bb;
1293 struct loop *loop;
1294 int err = 0;
1295 edge e;
1297 /* Check sizes. */
1298 sizes = xcalloc (loops->num, sizeof (int));
1299 sizes[0] = 2;
1301 FOR_EACH_BB (bb)
1302 for (loop = bb->loop_father; loop; loop = loop->outer)
1303 sizes[loop->num]++;
1305 for (i = 0; i < loops->num; i++)
1307 if (!loops->parray[i])
1308 continue;
1310 if (loops->parray[i]->num_nodes != sizes[i])
1312 error ("Size of loop %d should be %d, not %d.",
1313 i, sizes[i], loops->parray[i]->num_nodes);
1314 err = 1;
1318 /* Check get_loop_body. */
1319 for (i = 1; i < loops->num; i++)
1321 loop = loops->parray[i];
1322 if (!loop)
1323 continue;
1324 bbs = get_loop_body (loop);
1326 for (j = 0; j < loop->num_nodes; j++)
1327 if (!flow_bb_inside_loop_p (loop, bbs[j]))
1329 error ("Bb %d do not belong to loop %d.",
1330 bbs[j]->index, i);
1331 err = 1;
1333 free (bbs);
1336 /* Check headers and latches. */
1337 for (i = 1; i < loops->num; i++)
1339 loop = loops->parray[i];
1340 if (!loop)
1341 continue;
1343 if ((loops->state & LOOPS_HAVE_PREHEADERS)
1344 && EDGE_COUNT (loop->header->preds) != 2)
1346 error ("Loop %d's header does not have exactly 2 entries.", i);
1347 err = 1;
1349 if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1351 if (EDGE_COUNT (loop->latch->succs) != 1)
1353 error ("Loop %d's latch does not have exactly 1 successor.", i);
1354 err = 1;
1356 if (EDGE_SUCC (loop->latch, 0)->dest != loop->header)
1358 error ("Loop %d's latch does not have header as successor.", i);
1359 err = 1;
1361 if (loop->latch->loop_father != loop)
1363 error ("Loop %d's latch does not belong directly to it.", i);
1364 err = 1;
1367 if (loop->header->loop_father != loop)
1369 error ("Loop %d's header does not belong directly to it.", i);
1370 err = 1;
1372 if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1373 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1375 error ("Loop %d's latch is marked as part of irreducible region.", i);
1376 err = 1;
1380 /* Check irreducible loops. */
1381 if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1383 /* Record old info. */
1384 irreds = sbitmap_alloc (last_basic_block);
1385 FOR_EACH_BB (bb)
1387 edge_iterator ei;
1388 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1389 SET_BIT (irreds, bb->index);
1390 else
1391 RESET_BIT (irreds, bb->index);
1392 FOR_EACH_EDGE (e, ei, bb->succs)
1393 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1394 e->flags |= EDGE_ALL_FLAGS + 1;
1397 /* Recount it. */
1398 mark_irreducible_loops (loops);
1400 /* Compare. */
1401 FOR_EACH_BB (bb)
1403 edge_iterator ei;
1405 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1406 && !TEST_BIT (irreds, bb->index))
1408 error ("Basic block %d should be marked irreducible.", bb->index);
1409 err = 1;
1411 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1412 && TEST_BIT (irreds, bb->index))
1414 error ("Basic block %d should not be marked irreducible.", bb->index);
1415 err = 1;
1417 FOR_EACH_EDGE (e, ei, bb->succs)
1419 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1420 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1422 error ("Edge from %d to %d should be marked irreducible.",
1423 e->src->index, e->dest->index);
1424 err = 1;
1426 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1427 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1429 error ("Edge from %d to %d should not be marked irreducible.",
1430 e->src->index, e->dest->index);
1431 err = 1;
1433 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1436 free (irreds);
1439 /* Check the single_exit. */
1440 if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
1442 memset (sizes, 0, sizeof (unsigned) * loops->num);
1443 FOR_EACH_BB (bb)
1445 edge_iterator ei;
1446 if (bb->loop_father == loops->tree_root)
1447 continue;
1448 FOR_EACH_EDGE (e, ei, bb->succs)
1450 if (e->dest == EXIT_BLOCK_PTR)
1451 continue;
1453 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1454 continue;
1456 for (loop = bb->loop_father;
1457 loop != e->dest->loop_father;
1458 loop = loop->outer)
1460 sizes[loop->num]++;
1461 if (loop->single_exit
1462 && loop->single_exit != e)
1464 error ("Wrong single exit %d->%d recorded for loop %d.",
1465 loop->single_exit->src->index,
1466 loop->single_exit->dest->index,
1467 loop->num);
1468 error ("Right exit is %d->%d.",
1469 e->src->index, e->dest->index);
1470 err = 1;
1476 for (i = 1; i < loops->num; i++)
1478 loop = loops->parray[i];
1479 if (!loop)
1480 continue;
1482 if (sizes[i] == 1
1483 && !loop->single_exit)
1485 error ("Single exit not recorded for loop %d.", loop->num);
1486 err = 1;
1489 if (sizes[i] != 1
1490 && loop->single_exit)
1492 error ("Loop %d should not have single exit (%d -> %d).",
1493 loop->num,
1494 loop->single_exit->src->index,
1495 loop->single_exit->dest->index);
1496 err = 1;
1501 gcc_assert (!err);
1503 free (sizes);
1506 /* Returns latch edge of LOOP. */
1507 edge
1508 loop_latch_edge (const struct loop *loop)
1510 return find_edge (loop->latch, loop->header);
1513 /* Returns preheader edge of LOOP. */
1514 edge
1515 loop_preheader_edge (const struct loop *loop)
1517 edge e;
1518 edge_iterator ei;
1520 FOR_EACH_EDGE (e, ei, loop->header->preds)
1521 if (e->src != loop->latch)
1522 break;
1524 return e;