OSDN Git Service

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