OSDN Git Service

b168b9792b8467f6b77c9bcc159cd43105aeee66
[pf3gnuchains/gcc-fork.git] / gcc / cfgloop.c
1 /* Natural loop discovery code for GNU compiler.
2    Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA.  */
20
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"
35
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
39
40 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
41 #define LATCH_EDGE(E) (*(int *) (E)->aux)
42
43 static void flow_loops_cfg_dump (const struct loops *, FILE *);
44 static void establish_preds (struct loop *);
45 static void canonicalize_loop_headers (void);
46 static bool glb_enum_p (basic_block, void *);
47 \f
48 /* Dump loop related CFG information.  */
49
50 static void
51 flow_loops_cfg_dump (const struct loops *loops, FILE *file)
52 {
53   basic_block bb;
54
55   if (! loops->num || ! file)
56     return;
57
58   FOR_EACH_BB (bb)
59     {
60       edge succ;
61       edge_iterator ei;
62
63       fprintf (file, ";; %d succs { ", bb->index);
64       FOR_EACH_EDGE (succ, ei, bb->succs)
65         fprintf (file, "%d ", succ->dest->index);
66       fprintf (file, "}\n");
67     }
68 }
69
70 /* Return nonzero if the nodes of LOOP are a subset of OUTER.  */
71
72 bool
73 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
74 {
75   return (loop->depth > outer->depth
76          && loop->pred[outer->depth] == outer);
77 }
78
79 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
80    loops within LOOP.  */
81
82 struct loop *
83 superloop_at_depth (struct loop *loop, unsigned depth)
84 {
85   gcc_assert (depth <= (unsigned) loop->depth);
86
87   if (depth == (unsigned) loop->depth)
88     return loop;
89
90   return loop->pred[depth];
91 }
92
93 /* Dump the loop information specified by LOOP to the stream FILE
94    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
95
96 void
97 flow_loop_dump (const struct loop *loop, FILE *file,
98                 void (*loop_dump_aux) (const struct loop *, FILE *, int),
99                 int verbose)
100 {
101   basic_block *bbs;
102   unsigned i;
103
104   if (! loop || ! loop->header)
105     return;
106
107   fprintf (file, ";;\n;; Loop %d\n", loop->num);
108
109   fprintf (file, ";;  header %d, latch %d\n",
110            loop->header->index, loop->latch->index);
111   fprintf (file, ";;  depth %d, outer %ld\n",
112            loop->depth, (long) (loop->outer ? loop->outer->num : -1));
113
114   fprintf (file, ";;  nodes:");
115   bbs = get_loop_body (loop);
116   for (i = 0; i < loop->num_nodes; i++)
117     fprintf (file, " %d", bbs[i]->index);
118   free (bbs);
119   fprintf (file, "\n");
120
121   if (loop_dump_aux)
122     loop_dump_aux (loop, file, verbose);
123 }
124
125 /* Dump the loop information specified by LOOPS to the stream FILE,
126    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
127
128 void
129 flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
130 {
131   int i;
132   int num_loops;
133
134   num_loops = loops->num;
135   if (! num_loops || ! file)
136     return;
137
138   fprintf (file, ";; %d loops found\n", num_loops);
139
140   for (i = 0; i < num_loops; i++)
141     {
142       struct loop *loop = loops->parray[i];
143
144       if (!loop)
145         continue;
146
147       flow_loop_dump (loop, file, loop_dump_aux, verbose);
148     }
149
150   if (verbose)
151     flow_loops_cfg_dump (loops, file);
152 }
153
154 /* Free data allocated for LOOP.  */
155 void
156 flow_loop_free (struct loop *loop)
157 {
158   if (loop->pred)
159     free (loop->pred);
160   free (loop);
161 }
162
163 /* Free all the memory allocated for LOOPS.  */
164
165 void
166 flow_loops_free (struct loops *loops)
167 {
168   if (loops->parray)
169     {
170       unsigned i;
171
172       gcc_assert (loops->num);
173
174       /* Free the loop descriptors.  */
175       for (i = 0; i < loops->num; i++)
176         {
177           struct loop *loop = loops->parray[i];
178
179           if (!loop)
180             continue;
181
182           flow_loop_free (loop);
183         }
184
185       free (loops->parray);
186       loops->parray = NULL;
187     }
188 }
189
190 /* Find the nodes contained within the LOOP with header HEADER.
191    Return the number of nodes within the loop.  */
192
193 int
194 flow_loop_nodes_find (basic_block header, struct loop *loop)
195 {
196   basic_block *stack;
197   int sp;
198   int num_nodes = 1;
199
200   header->loop_father = loop;
201   header->loop_depth = loop->depth;
202
203   if (loop->latch->loop_father != loop)
204     {
205       stack = XNEWVEC (basic_block, n_basic_blocks);
206       sp = 0;
207       num_nodes++;
208       stack[sp++] = loop->latch;
209       loop->latch->loop_father = loop;
210       loop->latch->loop_depth = loop->depth;
211
212       while (sp)
213         {
214           basic_block node;
215           edge e;
216           edge_iterator ei;
217
218           node = stack[--sp];
219
220           FOR_EACH_EDGE (e, ei, node->preds)
221             {
222               basic_block ancestor = e->src;
223
224               if (ancestor != ENTRY_BLOCK_PTR
225                   && ancestor->loop_father != loop)
226                 {
227                   ancestor->loop_father = loop;
228                   ancestor->loop_depth = loop->depth;
229                   num_nodes++;
230                   stack[sp++] = ancestor;
231                 }
232             }
233         }
234       free (stack);
235     }
236   return num_nodes;
237 }
238
239 /* For each loop in the lOOPS tree that has just a single exit
240    record the exit edge.  */
241
242 void
243 mark_single_exit_loops (struct loops *loops)
244 {
245   basic_block bb;
246   edge e;
247   struct loop *loop;
248   unsigned i;
249
250   for (i = 1; i < loops->num; i++)
251     {
252       loop = loops->parray[i];
253       if (loop)
254         set_single_exit (loop, NULL);
255     }
256
257   FOR_EACH_BB (bb)
258     {
259       edge_iterator ei;
260       if (bb->loop_father == loops->tree_root)
261         continue;
262       FOR_EACH_EDGE (e, ei, bb->succs)
263         {
264           if (e->dest == EXIT_BLOCK_PTR)
265             continue;
266
267           if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
268             continue;
269
270           for (loop = bb->loop_father;
271                loop != e->dest->loop_father;
272                loop = loop->outer)
273             {
274               /* If we have already seen an exit, mark this by the edge that
275                  surely does not occur as any exit.  */
276               if (single_exit (loop))
277                 set_single_exit (loop, single_succ_edge (ENTRY_BLOCK_PTR));
278               else
279                 set_single_exit (loop, e);
280             }
281         }
282     }
283
284   for (i = 1; i < loops->num; i++)
285     {
286       loop = loops->parray[i];
287       if (!loop)
288         continue;
289
290       if (single_exit (loop) == single_succ_edge (ENTRY_BLOCK_PTR))
291         set_single_exit (loop, NULL);
292     }
293
294   loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
295 }
296
297 static void
298 establish_preds (struct loop *loop)
299 {
300   struct loop *ploop, *father = loop->outer;
301
302   loop->depth = father->depth + 1;
303
304   /* Remember the current loop depth if it is the largest seen so far.  */
305   cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
306
307   if (loop->pred)
308     free (loop->pred);
309   loop->pred = XNEWVEC (struct loop *, loop->depth);
310   memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
311   loop->pred[father->depth] = father;
312
313   for (ploop = loop->inner; ploop; ploop = ploop->next)
314     establish_preds (ploop);
315 }
316
317 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
318    added loop.  If LOOP has some children, take care of that their
319    pred field will be initialized correctly.  */
320
321 void
322 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
323 {
324   loop->next = father->inner;
325   father->inner = loop;
326   loop->outer = father;
327
328   establish_preds (loop);
329 }
330
331 /* Remove LOOP from the loop hierarchy tree.  */
332
333 void
334 flow_loop_tree_node_remove (struct loop *loop)
335 {
336   struct loop *prev, *father;
337
338   father = loop->outer;
339   loop->outer = NULL;
340
341   /* Remove loop from the list of sons.  */
342   if (father->inner == loop)
343     father->inner = loop->next;
344   else
345     {
346       for (prev = father->inner; prev->next != loop; prev = prev->next);
347       prev->next = loop->next;
348     }
349
350   loop->depth = -1;
351   free (loop->pred);
352   loop->pred = NULL;
353 }
354
355 /* A callback to update latch and header info for basic block JUMP created
356    by redirecting an edge.  */
357
358 static void
359 update_latch_info (basic_block jump)
360 {
361   alloc_aux_for_block (jump, sizeof (int));
362   HEADER_BLOCK (jump) = 0;
363   alloc_aux_for_edge (single_pred_edge (jump), sizeof (int));
364   LATCH_EDGE (single_pred_edge (jump)) = 0;
365   set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
366 }
367
368 /* A callback for make_forwarder block, to redirect all edges except for
369    MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
370    whether to redirect it.  */
371
372 static edge mfb_kj_edge;
373 static bool
374 mfb_keep_just (edge e)
375 {
376   return e != mfb_kj_edge;
377 }
378
379 /* A callback for make_forwarder block, to redirect the latch edges into an
380    entry part.  E is the edge for that we should decide whether to redirect
381    it.  */
382
383 static bool
384 mfb_keep_nonlatch (edge e)
385 {
386   return LATCH_EDGE (e);
387 }
388
389 /* Takes care of merging natural loops with shared headers.  */
390
391 static void
392 canonicalize_loop_headers (void)
393 {
394   basic_block header;
395   edge e;
396
397   alloc_aux_for_blocks (sizeof (int));
398   alloc_aux_for_edges (sizeof (int));
399
400   /* Split blocks so that each loop has only single latch.  */
401   FOR_EACH_BB (header)
402     {
403       edge_iterator ei;
404       int num_latches = 0;
405       int have_abnormal_edge = 0;
406
407       FOR_EACH_EDGE (e, ei, header->preds)
408         {
409           basic_block latch = e->src;
410
411           if (e->flags & EDGE_ABNORMAL)
412             have_abnormal_edge = 1;
413
414           if (latch != ENTRY_BLOCK_PTR
415               && dominated_by_p (CDI_DOMINATORS, latch, header))
416             {
417               num_latches++;
418               LATCH_EDGE (e) = 1;
419             }
420         }
421       if (have_abnormal_edge)
422         HEADER_BLOCK (header) = 0;
423       else
424         HEADER_BLOCK (header) = num_latches;
425     }
426
427   if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR)))
428     {
429       basic_block bb;
430
431       /* We could not redirect edges freely here. On the other hand,
432          we can simply split the edge from entry block.  */
433       bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
434
435       alloc_aux_for_edge (single_succ_edge (bb), sizeof (int));
436       LATCH_EDGE (single_succ_edge (bb)) = 0;
437       alloc_aux_for_block (bb, sizeof (int));
438       HEADER_BLOCK (bb) = 0;
439     }
440
441   FOR_EACH_BB (header)
442     {
443       int max_freq, is_heavy;
444       edge heavy, tmp_edge;
445       edge_iterator ei;
446
447       if (HEADER_BLOCK (header) <= 1)
448         continue;
449
450       /* Find a heavy edge.  */
451       is_heavy = 1;
452       heavy = NULL;
453       max_freq = 0;
454       FOR_EACH_EDGE (e, ei, header->preds)
455         if (LATCH_EDGE (e) &&
456             EDGE_FREQUENCY (e) > max_freq)
457           max_freq = EDGE_FREQUENCY (e);
458       FOR_EACH_EDGE (e, ei, header->preds)
459         if (LATCH_EDGE (e) &&
460             EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
461           {
462             if (heavy)
463               {
464                 is_heavy = 0;
465                 break;
466               }
467             else
468               heavy = e;
469           }
470
471       if (is_heavy)
472         {
473           /* Split out the heavy edge, and create inner loop for it.  */
474           mfb_kj_edge = heavy;
475           tmp_edge = make_forwarder_block (header, mfb_keep_just,
476                                            update_latch_info);
477           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
478           HEADER_BLOCK (tmp_edge->dest) = 1;
479           alloc_aux_for_edge (tmp_edge, sizeof (int));
480           LATCH_EDGE (tmp_edge) = 0;
481           HEADER_BLOCK (header)--;
482         }
483
484       if (HEADER_BLOCK (header) > 1)
485         {
486           /* Create a new latch block.  */
487           tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
488                                            update_latch_info);
489           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
490           HEADER_BLOCK (tmp_edge->src) = 0;
491           HEADER_BLOCK (tmp_edge->dest) = 1;
492           alloc_aux_for_edge (tmp_edge, sizeof (int));
493           LATCH_EDGE (tmp_edge) = 1;
494         }
495     }
496
497   free_aux_for_blocks ();
498   free_aux_for_edges ();
499
500 #ifdef ENABLE_CHECKING
501   verify_dominators (CDI_DOMINATORS);
502 #endif
503 }
504
505 /* Initialize all the parallel_p fields of the loops structure to true.  */
506
507 static void
508 initialize_loops_parallel_p (struct loops *loops)
509 {
510   unsigned int i;
511
512   for (i = 0; i < loops->num; i++)
513     {
514       struct loop *loop = loops->parray[i];
515       loop->parallel_p = true;
516     }
517 }
518
519 /* Find all the natural loops in the function and save in LOOPS structure and
520    recalculate loop_depth information in basic block structures.
521    Return the number of natural loops found.  */
522
523 int
524 flow_loops_find (struct loops *loops)
525 {
526   int b;
527   int num_loops;
528   edge e;
529   sbitmap headers;
530   int *dfs_order;
531   int *rc_order;
532   basic_block header;
533   basic_block bb;
534
535   memset (loops, 0, sizeof *loops);
536
537   /* We are going to recount the maximum loop depth,
538      so throw away the last count.  */
539   cfun->max_loop_depth = 0;
540
541   /* Taking care of this degenerate case makes the rest of
542      this code simpler.  */
543   if (n_basic_blocks == NUM_FIXED_BLOCKS)
544     return 0;
545
546   dfs_order = NULL;
547   rc_order = NULL;
548
549   /* Ensure that the dominators are computed.  */
550   calculate_dominance_info (CDI_DOMINATORS);
551
552   /* Join loops with shared headers.  */
553   canonicalize_loop_headers ();
554
555   /* Count the number of loop headers.  This should be the
556      same as the number of natural loops.  */
557   headers = sbitmap_alloc (last_basic_block);
558   sbitmap_zero (headers);
559
560   num_loops = 0;
561   FOR_EACH_BB (header)
562     {
563       edge_iterator ei;
564       int more_latches = 0;
565
566       header->loop_depth = 0;
567
568       /* If we have an abnormal predecessor, do not consider the
569          loop (not worth the problems).  */
570       FOR_EACH_EDGE (e, ei, header->preds)
571         if (e->flags & EDGE_ABNORMAL)
572           break;
573       if (e)
574         continue;
575
576       FOR_EACH_EDGE (e, ei, header->preds)
577         {
578           basic_block latch = e->src;
579
580           gcc_assert (!(e->flags & EDGE_ABNORMAL));
581
582           /* Look for back edges where a predecessor is dominated
583              by this block.  A natural loop has a single entry
584              node (header) that dominates all the nodes in the
585              loop.  It also has single back edge to the header
586              from a latch node.  */
587           if (latch != ENTRY_BLOCK_PTR
588               && dominated_by_p (CDI_DOMINATORS, latch, header))
589             {
590               /* Shared headers should be eliminated by now.  */
591               gcc_assert (!more_latches);
592               more_latches = 1;
593               SET_BIT (headers, header->index);
594               num_loops++;
595             }
596         }
597     }
598
599   /* Allocate loop structures.  */
600   loops->parray = XCNEWVEC (struct loop *, num_loops + 1);
601
602   /* Dummy loop containing whole function.  */
603   loops->parray[0] = XCNEW (struct loop);
604   loops->parray[0]->next = NULL;
605   loops->parray[0]->inner = NULL;
606   loops->parray[0]->outer = NULL;
607   loops->parray[0]->depth = 0;
608   loops->parray[0]->pred = NULL;
609   loops->parray[0]->num_nodes = n_basic_blocks;
610   loops->parray[0]->latch = EXIT_BLOCK_PTR;
611   loops->parray[0]->header = ENTRY_BLOCK_PTR;
612   ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
613   EXIT_BLOCK_PTR->loop_father = loops->parray[0];
614
615   loops->tree_root = loops->parray[0];
616
617   /* Find and record information about all the natural loops
618      in the CFG.  */
619   loops->num = 1;
620   FOR_EACH_BB (bb)
621     bb->loop_father = loops->tree_root;
622
623   if (num_loops)
624     {
625       /* Compute depth first search order of the CFG so that outer
626          natural loops will be found before inner natural loops.  */
627       dfs_order = XNEWVEC (int, n_basic_blocks);
628       rc_order = XNEWVEC (int, n_basic_blocks);
629       pre_and_rev_post_order_compute (dfs_order, rc_order, false);
630
631       num_loops = 1;
632
633       for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
634         {
635           struct loop *loop;
636           edge_iterator ei;
637
638           /* Search the nodes of the CFG in reverse completion order
639              so that we can find outer loops first.  */
640           if (!TEST_BIT (headers, rc_order[b]))
641             continue;
642
643           header = BASIC_BLOCK (rc_order[b]);
644
645           loop = loops->parray[num_loops] = XCNEW (struct loop);
646
647           loop->header = header;
648           loop->num = num_loops;
649           num_loops++;
650
651           /* Look for the latch for this header block.  */
652           FOR_EACH_EDGE (e, ei, header->preds)
653             {
654               basic_block latch = e->src;
655
656               if (latch != ENTRY_BLOCK_PTR
657                   && dominated_by_p (CDI_DOMINATORS, latch, header))
658                 {
659                   loop->latch = latch;
660                   break;
661                 }
662             }
663
664           flow_loop_tree_node_add (header->loop_father, loop);
665           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
666         }
667
668       loops->num = num_loops;
669       initialize_loops_parallel_p (loops);
670
671       free (dfs_order);
672       free (rc_order);
673     }
674
675   sbitmap_free (headers);
676
677   loops->state = 0;
678   return loops->num;
679 }
680
681 /* Return nonzero if basic block BB belongs to LOOP.  */
682 bool
683 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
684 {
685   struct loop *source_loop;
686
687   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
688     return 0;
689
690   source_loop = bb->loop_father;
691   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
692 }
693
694 /* Enumeration predicate for get_loop_body.  */
695 static bool
696 glb_enum_p (basic_block bb, void *glb_header)
697 {
698   return bb != (basic_block) glb_header;
699 }
700
701 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
702    order against direction of edges from latch.  Specially, if
703    header != latch, latch is the 1-st block.  */
704 basic_block *
705 get_loop_body (const struct loop *loop)
706 {
707   basic_block *tovisit, bb;
708   unsigned tv = 0;
709
710   gcc_assert (loop->num_nodes);
711
712   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
713   tovisit[tv++] = loop->header;
714
715   if (loop->latch == EXIT_BLOCK_PTR)
716     {
717       /* There may be blocks unreachable from EXIT_BLOCK.  */
718       gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
719       FOR_EACH_BB (bb)
720         tovisit[tv++] = bb;
721       tovisit[tv++] = EXIT_BLOCK_PTR;
722     }
723   else if (loop->latch != loop->header)
724     {
725       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
726                                tovisit + 1, loop->num_nodes - 1,
727                                loop->header) + 1;
728     }
729
730   gcc_assert (tv == loop->num_nodes);
731   return tovisit;
732 }
733
734 /* Fills dominance descendants inside LOOP of the basic block BB into
735    array TOVISIT from index *TV.  */
736
737 static void
738 fill_sons_in_loop (const struct loop *loop, basic_block bb,
739                    basic_block *tovisit, int *tv)
740 {
741   basic_block son, postpone = NULL;
742
743   tovisit[(*tv)++] = bb;
744   for (son = first_dom_son (CDI_DOMINATORS, bb);
745        son;
746        son = next_dom_son (CDI_DOMINATORS, son))
747     {
748       if (!flow_bb_inside_loop_p (loop, son))
749         continue;
750
751       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
752         {
753           postpone = son;
754           continue;
755         }
756       fill_sons_in_loop (loop, son, tovisit, tv);
757     }
758
759   if (postpone)
760     fill_sons_in_loop (loop, postpone, tovisit, tv);
761 }
762
763 /* Gets body of a LOOP (that must be different from the outermost loop)
764    sorted by dominance relation.  Additionally, if a basic block s dominates
765    the latch, then only blocks dominated by s are be after it.  */
766
767 basic_block *
768 get_loop_body_in_dom_order (const struct loop *loop)
769 {
770   basic_block *tovisit;
771   int tv;
772
773   gcc_assert (loop->num_nodes);
774
775   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
776
777   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
778
779   tv = 0;
780   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
781
782   gcc_assert (tv == (int) loop->num_nodes);
783
784   return tovisit;
785 }
786
787 /* Get body of a LOOP in breadth first sort order.  */
788
789 basic_block *
790 get_loop_body_in_bfs_order (const struct loop *loop)
791 {
792   basic_block *blocks;
793   basic_block bb;
794   bitmap visited;
795   unsigned int i = 0;
796   unsigned int vc = 1;
797
798   gcc_assert (loop->num_nodes);
799   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
800
801   blocks = XCNEWVEC (basic_block, loop->num_nodes);
802   visited = BITMAP_ALLOC (NULL);
803
804   bb = loop->header;
805   while (i < loop->num_nodes)
806     {
807       edge e;
808       edge_iterator ei;
809
810       if (!bitmap_bit_p (visited, bb->index))
811         {
812           /* This basic block is now visited */
813           bitmap_set_bit (visited, bb->index);
814           blocks[i++] = bb;
815         }
816
817       FOR_EACH_EDGE (e, ei, bb->succs)
818         {
819           if (flow_bb_inside_loop_p (loop, e->dest))
820             {
821               if (!bitmap_bit_p (visited, e->dest->index))
822                 {
823                   bitmap_set_bit (visited, e->dest->index);
824                   blocks[i++] = e->dest;
825                 }
826             }
827         }
828
829       gcc_assert (i >= vc);
830
831       bb = blocks[vc++];
832     }
833
834   BITMAP_FREE (visited);
835   return blocks;
836 }
837
838 /* Returns the list of the exit edges of a LOOP.  */
839
840 VEC (edge, heap) *
841 get_loop_exit_edges (const struct loop *loop)
842 {
843   VEC (edge, heap) *edges = NULL;
844   edge e;
845   unsigned i;
846   basic_block *body;
847   edge_iterator ei;
848
849   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
850
851   body = get_loop_body (loop);
852   for (i = 0; i < loop->num_nodes; i++)
853     FOR_EACH_EDGE (e, ei, body[i]->succs)
854       if (!flow_bb_inside_loop_p (loop, e->dest))
855         VEC_safe_push (edge, heap, edges, e);
856   free (body);
857
858   return edges;
859 }
860
861 /* Counts the number of conditional branches inside LOOP.  */
862
863 unsigned
864 num_loop_branches (const struct loop *loop)
865 {
866   unsigned i, n;
867   basic_block * body;
868
869   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
870
871   body = get_loop_body (loop);
872   n = 0;
873   for (i = 0; i < loop->num_nodes; i++)
874     if (EDGE_COUNT (body[i]->succs) >= 2)
875       n++;
876   free (body);
877
878   return n;
879 }
880
881 /* Adds basic block BB to LOOP.  */
882 void
883 add_bb_to_loop (basic_block bb, struct loop *loop)
884 {
885    int i;
886
887    gcc_assert (bb->loop_father == NULL);
888    bb->loop_father = loop;
889    bb->loop_depth = loop->depth;
890    loop->num_nodes++;
891    for (i = 0; i < loop->depth; i++)
892      loop->pred[i]->num_nodes++;
893 }
894
895 /* Remove basic block BB from loops.  */
896 void
897 remove_bb_from_loops (basic_block bb)
898 {
899    int i;
900    struct loop *loop = bb->loop_father;
901
902    gcc_assert (loop != NULL);
903    loop->num_nodes--;
904    for (i = 0; i < loop->depth; i++)
905      loop->pred[i]->num_nodes--;
906    bb->loop_father = NULL;
907    bb->loop_depth = 0;
908 }
909
910 /* Finds nearest common ancestor in loop tree for given loops.  */
911 struct loop *
912 find_common_loop (struct loop *loop_s, struct loop *loop_d)
913 {
914   if (!loop_s) return loop_d;
915   if (!loop_d) return loop_s;
916
917   if (loop_s->depth < loop_d->depth)
918     loop_d = loop_d->pred[loop_s->depth];
919   else if (loop_s->depth > loop_d->depth)
920     loop_s = loop_s->pred[loop_d->depth];
921
922   while (loop_s != loop_d)
923     {
924       loop_s = loop_s->outer;
925       loop_d = loop_d->outer;
926     }
927   return loop_s;
928 }
929
930 /* Cancels the LOOP; it must be innermost one.  */
931
932 static void
933 cancel_loop (struct loops *loops, struct loop *loop)
934 {
935   basic_block *bbs;
936   unsigned i;
937
938   gcc_assert (!loop->inner);
939
940   /* Move blocks up one level (they should be removed as soon as possible).  */
941   bbs = get_loop_body (loop);
942   for (i = 0; i < loop->num_nodes; i++)
943     bbs[i]->loop_father = loop->outer;
944
945   /* Remove the loop from structure.  */
946   flow_loop_tree_node_remove (loop);
947
948   /* Remove loop from loops array.  */
949   loops->parray[loop->num] = NULL;
950
951   /* Free loop data.  */
952   flow_loop_free (loop);
953 }
954
955 /* Cancels LOOP and all its subloops.  */
956 void
957 cancel_loop_tree (struct loops *loops, struct loop *loop)
958 {
959   while (loop->inner)
960     cancel_loop_tree (loops, loop->inner);
961   cancel_loop (loops, loop);
962 }
963
964 /* Checks that LOOPS are all right:
965      -- sizes of loops are all right
966      -- results of get_loop_body really belong to the loop
967      -- loop header have just single entry edge and single latch edge
968      -- loop latches have only single successor that is header of their loop
969      -- irreducible loops are correctly marked
970   */
971 void
972 verify_loop_structure (struct loops *loops)
973 {
974   unsigned *sizes, i, j;
975   sbitmap irreds;
976   basic_block *bbs, bb;
977   struct loop *loop;
978   int err = 0;
979   edge e;
980
981   /* Check sizes.  */
982   sizes = XCNEWVEC (unsigned, loops->num);
983   sizes[0] = 2;
984
985   FOR_EACH_BB (bb)
986     for (loop = bb->loop_father; loop; loop = loop->outer)
987       sizes[loop->num]++;
988
989   for (i = 0; i < loops->num; i++)
990     {
991       if (!loops->parray[i])
992         continue;
993
994       if (loops->parray[i]->num_nodes != sizes[i])
995         {
996           error ("size of loop %d should be %d, not %d",
997                    i, sizes[i], loops->parray[i]->num_nodes);
998           err = 1;
999         }
1000     }
1001
1002   /* Check get_loop_body.  */
1003   for (i = 1; i < loops->num; i++)
1004     {
1005       loop = loops->parray[i];
1006       if (!loop)
1007         continue;
1008       bbs = get_loop_body (loop);
1009
1010       for (j = 0; j < loop->num_nodes; j++)
1011         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1012           {
1013             error ("bb %d do not belong to loop %d",
1014                     bbs[j]->index, i);
1015             err = 1;
1016           }
1017       free (bbs);
1018     }
1019
1020   /* Check headers and latches.  */
1021   for (i = 1; i < loops->num; i++)
1022     {
1023       loop = loops->parray[i];
1024       if (!loop)
1025         continue;
1026
1027       if ((loops->state & LOOPS_HAVE_PREHEADERS)
1028           && EDGE_COUNT (loop->header->preds) != 2)
1029         {
1030           error ("loop %d's header does not have exactly 2 entries", i);
1031           err = 1;
1032         }
1033       if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1034         {
1035           if (!single_succ_p (loop->latch))
1036             {
1037               error ("loop %d's latch does not have exactly 1 successor", i);
1038               err = 1;
1039             }
1040           if (single_succ (loop->latch) != loop->header)
1041             {
1042               error ("loop %d's latch does not have header as successor", i);
1043               err = 1;
1044             }
1045           if (loop->latch->loop_father != loop)
1046             {
1047               error ("loop %d's latch does not belong directly to it", i);
1048               err = 1;
1049             }
1050         }
1051       if (loop->header->loop_father != loop)
1052         {
1053           error ("loop %d's header does not belong directly to it", i);
1054           err = 1;
1055         }
1056       if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1057           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1058         {
1059           error ("loop %d's latch is marked as part of irreducible region", i);
1060           err = 1;
1061         }
1062     }
1063
1064   /* Check irreducible loops.  */
1065   if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1066     {
1067       /* Record old info.  */
1068       irreds = sbitmap_alloc (last_basic_block);
1069       FOR_EACH_BB (bb)
1070         {
1071           edge_iterator ei;
1072           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1073             SET_BIT (irreds, bb->index);
1074           else
1075             RESET_BIT (irreds, bb->index);
1076           FOR_EACH_EDGE (e, ei, bb->succs)
1077             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1078               e->flags |= EDGE_ALL_FLAGS + 1;
1079         }
1080
1081       /* Recount it.  */
1082       mark_irreducible_loops (loops);
1083
1084       /* Compare.  */
1085       FOR_EACH_BB (bb)
1086         {
1087           edge_iterator ei;
1088
1089           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1090               && !TEST_BIT (irreds, bb->index))
1091             {
1092               error ("basic block %d should be marked irreducible", bb->index);
1093               err = 1;
1094             }
1095           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1096               && TEST_BIT (irreds, bb->index))
1097             {
1098               error ("basic block %d should not be marked irreducible", bb->index);
1099               err = 1;
1100             }
1101           FOR_EACH_EDGE (e, ei, bb->succs)
1102             {
1103               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1104                   && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1105                 {
1106                   error ("edge from %d to %d should be marked irreducible",
1107                          e->src->index, e->dest->index);
1108                   err = 1;
1109                 }
1110               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1111                        && (e->flags & (EDGE_ALL_FLAGS + 1)))
1112                 {
1113                   error ("edge from %d to %d should not be marked irreducible",
1114                          e->src->index, e->dest->index);
1115                   err = 1;
1116                 }
1117               e->flags &= ~(EDGE_ALL_FLAGS + 1);
1118             }
1119         }
1120       free (irreds);
1121     }
1122
1123   /* Check the single_exit.  */
1124   if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
1125     {
1126       memset (sizes, 0, sizeof (unsigned) * loops->num);
1127       FOR_EACH_BB (bb)
1128         {
1129           edge_iterator ei;
1130           if (bb->loop_father == loops->tree_root)
1131             continue;
1132           FOR_EACH_EDGE (e, ei, bb->succs)
1133             {
1134               if (e->dest == EXIT_BLOCK_PTR)
1135                 continue;
1136
1137               if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1138                 continue;
1139
1140               for (loop = bb->loop_father;
1141                    loop != e->dest->loop_father;
1142                    loop = loop->outer)
1143                 {
1144                   sizes[loop->num]++;
1145                   if (single_exit (loop)
1146                       && single_exit (loop) != e)
1147                     {
1148                       error ("wrong single exit %d->%d recorded for loop %d",
1149                              single_exit (loop)->src->index,
1150                              single_exit (loop)->dest->index,
1151                              loop->num);
1152                       error ("right exit is %d->%d",
1153                              e->src->index, e->dest->index);
1154                       err = 1;
1155                     }
1156                 }
1157             }
1158         }
1159
1160       for (i = 1; i < loops->num; i++)
1161         {
1162           loop = loops->parray[i];
1163           if (!loop)
1164             continue;
1165
1166           if (sizes[i] == 1
1167               && !single_exit (loop))
1168             {
1169               error ("single exit not recorded for loop %d", loop->num);
1170               err = 1;
1171             }
1172
1173           if (sizes[i] != 1
1174               && single_exit (loop))
1175             {
1176               error ("loop %d should not have single exit (%d -> %d)",
1177                      loop->num,
1178                      single_exit (loop)->src->index,
1179                      single_exit (loop)->dest->index);
1180               err = 1;
1181             }
1182         }
1183     }
1184
1185   gcc_assert (!err);
1186
1187   free (sizes);
1188 }
1189
1190 /* Returns latch edge of LOOP.  */
1191 edge
1192 loop_latch_edge (const struct loop *loop)
1193 {
1194   return find_edge (loop->latch, loop->header);
1195 }
1196
1197 /* Returns preheader edge of LOOP.  */
1198 edge
1199 loop_preheader_edge (const struct loop *loop)
1200 {
1201   edge e;
1202   edge_iterator ei;
1203
1204   FOR_EACH_EDGE (e, ei, loop->header->preds)
1205     if (e->src != loop->latch)
1206       break;
1207
1208   return e;
1209 }
1210
1211 /* Returns true if E is an exit of LOOP.  */
1212
1213 bool
1214 loop_exit_edge_p (const struct loop *loop, edge e)
1215 {
1216   return (flow_bb_inside_loop_p (loop, e->src)
1217           && !flow_bb_inside_loop_p (loop, e->dest));
1218 }
1219
1220 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1221    or more than one exit.  */
1222
1223 edge
1224 single_exit (const struct loop *loop)
1225 {
1226   return loop->single_exit_;
1227 }
1228
1229 /* Records E as a single exit edge of LOOP.  */
1230
1231 void
1232 set_single_exit (struct loop *loop, edge e)
1233 {
1234   loop->single_exit_ = e;
1235 }