OSDN Git Service

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