OSDN Git Service

66214d7fec623710118a73faa9a4ebee4b1cd63d
[pf3gnuchains/gcc-fork.git] / gcc / cfganal.c
1 /* Control flow graph analysis code for GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This file contains various simple utilities to analyze the CFG.  */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "obstack.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
31 #include "recog.h"
32 #include "toplev.h"
33 #include "tm_p.h"
34 #include "timevar.h"
35
36 /* Store the data structures necessary for depth-first search.  */
37 struct depth_first_search_dsS {
38   /* stack for backtracking during the algorithm */
39   basic_block *stack;
40
41   /* number of edges in the stack.  That is, positions 0, ..., sp-1
42      have edges.  */
43   unsigned int sp;
44
45   /* record of basic blocks already seen by depth-first search */
46   sbitmap visited_blocks;
47 };
48 typedef struct depth_first_search_dsS *depth_first_search_ds;
49
50 static void flow_dfs_compute_reverse_init (depth_first_search_ds);
51 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
52                                              basic_block);
53 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
54                                                      basic_block);
55 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
56 static bool flow_active_insn_p (const_rtx);
57 \f
58 /* Like active_insn_p, except keep the return value clobber around
59    even after reload.  */
60
61 static bool
62 flow_active_insn_p (const_rtx insn)
63 {
64   if (active_insn_p (insn))
65     return true;
66
67   /* A clobber of the function return value exists for buggy
68      programs that fail to return a value.  Its effect is to
69      keep the return value from being live across the entire
70      function.  If we allow it to be skipped, we introduce the
71      possibility for register lifetime confusion.  */
72   if (GET_CODE (PATTERN (insn)) == CLOBBER
73       && REG_P (XEXP (PATTERN (insn), 0))
74       && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
75     return true;
76
77   return false;
78 }
79
80 /* Return true if the block has no effect and only forwards control flow to
81    its single destination.  */
82
83 bool
84 forwarder_block_p (const_basic_block bb)
85 {
86   rtx insn;
87
88   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
89       || !single_succ_p (bb))
90     return false;
91
92   for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
93     if (INSN_P (insn) && flow_active_insn_p (insn))
94       return false;
95
96   return (!INSN_P (insn)
97           || (JUMP_P (insn) && simplejump_p (insn))
98           || !flow_active_insn_p (insn));
99 }
100
101 /* Return nonzero if we can reach target from src by falling through.  */
102
103 bool
104 can_fallthru (basic_block src, basic_block target)
105 {
106   rtx insn = BB_END (src);
107   rtx insn2;
108   edge e;
109   edge_iterator ei;
110
111   if (target == EXIT_BLOCK_PTR)
112     return true;
113   if (src->next_bb != target)
114     return 0;
115   FOR_EACH_EDGE (e, ei, src->succs)
116     if (e->dest == EXIT_BLOCK_PTR
117         && e->flags & EDGE_FALLTHRU)
118       return 0;
119
120   insn2 = BB_HEAD (target);
121   if (insn2 && !active_insn_p (insn2))
122     insn2 = next_active_insn (insn2);
123
124   /* ??? Later we may add code to move jump tables offline.  */
125   return next_active_insn (insn) == insn2;
126 }
127
128 /* Return nonzero if we could reach target from src by falling through,
129    if the target was made adjacent.  If we already have a fall-through
130    edge to the exit block, we can't do that.  */
131 bool
132 could_fall_through (basic_block src, basic_block target)
133 {
134   edge e;
135   edge_iterator ei;
136
137   if (target == EXIT_BLOCK_PTR)
138     return true;
139   FOR_EACH_EDGE (e, ei, src->succs)
140     if (e->dest == EXIT_BLOCK_PTR
141         && e->flags & EDGE_FALLTHRU)
142       return 0;
143   return true;
144 }
145 \f
146 /* Mark the back edges in DFS traversal.
147    Return nonzero if a loop (natural or otherwise) is present.
148    Inspired by Depth_First_Search_PP described in:
149
150      Advanced Compiler Design and Implementation
151      Steven Muchnick
152      Morgan Kaufmann, 1997
153
154    and heavily borrowed from pre_and_rev_post_order_compute.  */
155
156 bool
157 mark_dfs_back_edges (void)
158 {
159   edge_iterator *stack;
160   int *pre;
161   int *post;
162   int sp;
163   int prenum = 1;
164   int postnum = 1;
165   sbitmap visited;
166   bool found = false;
167
168   /* Allocate the preorder and postorder number arrays.  */
169   pre = XCNEWVEC (int, last_basic_block);
170   post = XCNEWVEC (int, last_basic_block);
171
172   /* Allocate stack for back-tracking up CFG.  */
173   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
174   sp = 0;
175
176   /* Allocate bitmap to track nodes that have been visited.  */
177   visited = sbitmap_alloc (last_basic_block);
178
179   /* None of the nodes in the CFG have been visited yet.  */
180   sbitmap_zero (visited);
181
182   /* Push the first edge on to the stack.  */
183   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
184
185   while (sp)
186     {
187       edge_iterator ei;
188       basic_block src;
189       basic_block dest;
190
191       /* Look at the edge on the top of the stack.  */
192       ei = stack[sp - 1];
193       src = ei_edge (ei)->src;
194       dest = ei_edge (ei)->dest;
195       ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
196
197       /* Check if the edge destination has been visited yet.  */
198       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
199         {
200           /* Mark that we have visited the destination.  */
201           SET_BIT (visited, dest->index);
202
203           pre[dest->index] = prenum++;
204           if (EDGE_COUNT (dest->succs) > 0)
205             {
206               /* Since the DEST node has been visited for the first
207                  time, check its successors.  */
208               stack[sp++] = ei_start (dest->succs);
209             }
210           else
211             post[dest->index] = postnum++;
212         }
213       else
214         {
215           if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
216               && pre[src->index] >= pre[dest->index]
217               && post[dest->index] == 0)
218             ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
219
220           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
221             post[src->index] = postnum++;
222
223           if (!ei_one_before_end_p (ei))
224             ei_next (&stack[sp - 1]);
225           else
226             sp--;
227         }
228     }
229
230   free (pre);
231   free (post);
232   free (stack);
233   sbitmap_free (visited);
234
235   return found;
236 }
237
238 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */
239
240 void
241 set_edge_can_fallthru_flag (void)
242 {
243   basic_block bb;
244
245   FOR_EACH_BB (bb)
246     {
247       edge e;
248       edge_iterator ei;
249
250       FOR_EACH_EDGE (e, ei, bb->succs)
251         {
252           e->flags &= ~EDGE_CAN_FALLTHRU;
253
254           /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
255           if (e->flags & EDGE_FALLTHRU)
256             e->flags |= EDGE_CAN_FALLTHRU;
257         }
258
259       /* If the BB ends with an invertible condjump all (2) edges are
260          CAN_FALLTHRU edges.  */
261       if (EDGE_COUNT (bb->succs) != 2)
262         continue;
263       if (!any_condjump_p (BB_END (bb)))
264         continue;
265       if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
266         continue;
267       invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
268       EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
269       EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
270     }
271 }
272
273 /* Find unreachable blocks.  An unreachable block will have 0 in
274    the reachable bit in block->flags.  A nonzero value indicates the
275    block is reachable.  */
276
277 void
278 find_unreachable_blocks (void)
279 {
280   edge e;
281   edge_iterator ei;
282   basic_block *tos, *worklist, bb;
283
284   tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
285
286   /* Clear all the reachability flags.  */
287
288   FOR_EACH_BB (bb)
289     bb->flags &= ~BB_REACHABLE;
290
291   /* Add our starting points to the worklist.  Almost always there will
292      be only one.  It isn't inconceivable that we might one day directly
293      support Fortran alternate entry points.  */
294
295   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
296     {
297       *tos++ = e->dest;
298
299       /* Mark the block reachable.  */
300       e->dest->flags |= BB_REACHABLE;
301     }
302
303   /* Iterate: find everything reachable from what we've already seen.  */
304
305   while (tos != worklist)
306     {
307       basic_block b = *--tos;
308
309       FOR_EACH_EDGE (e, ei, b->succs)
310         {
311           basic_block dest = e->dest;
312
313           if (!(dest->flags & BB_REACHABLE))
314             {
315               *tos++ = dest;
316               dest->flags |= BB_REACHABLE;
317             }
318         }
319     }
320
321   free (worklist);
322 }
323 \f
324 /* Functions to access an edge list with a vector representation.
325    Enough data is kept such that given an index number, the
326    pred and succ that edge represents can be determined, or
327    given a pred and a succ, its index number can be returned.
328    This allows algorithms which consume a lot of memory to
329    represent the normally full matrix of edge (pred,succ) with a
330    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
331    wasted space in the client code due to sparse flow graphs.  */
332
333 /* This functions initializes the edge list. Basically the entire
334    flowgraph is processed, and all edges are assigned a number,
335    and the data structure is filled in.  */
336
337 struct edge_list *
338 create_edge_list (void)
339 {
340   struct edge_list *elist;
341   edge e;
342   int num_edges;
343   int block_count;
344   basic_block bb;
345   edge_iterator ei;
346
347   block_count = n_basic_blocks; /* Include the entry and exit blocks.  */
348
349   num_edges = 0;
350
351   /* Determine the number of edges in the flow graph by counting successor
352      edges on each basic block.  */
353   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
354     {
355       num_edges += EDGE_COUNT (bb->succs);
356     }
357
358   elist = XNEW (struct edge_list);
359   elist->num_blocks = block_count;
360   elist->num_edges = num_edges;
361   elist->index_to_edge = XNEWVEC (edge, num_edges);
362
363   num_edges = 0;
364
365   /* Follow successors of blocks, and register these edges.  */
366   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
367     FOR_EACH_EDGE (e, ei, bb->succs)
368       elist->index_to_edge[num_edges++] = e;
369
370   return elist;
371 }
372
373 /* This function free's memory associated with an edge list.  */
374
375 void
376 free_edge_list (struct edge_list *elist)
377 {
378   if (elist)
379     {
380       free (elist->index_to_edge);
381       free (elist);
382     }
383 }
384
385 /* This function provides debug output showing an edge list.  */
386
387 void
388 print_edge_list (FILE *f, struct edge_list *elist)
389 {
390   int x;
391
392   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
393            elist->num_blocks, elist->num_edges);
394
395   for (x = 0; x < elist->num_edges; x++)
396     {
397       fprintf (f, " %-4d - edge(", x);
398       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
399         fprintf (f, "entry,");
400       else
401         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
402
403       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
404         fprintf (f, "exit)\n");
405       else
406         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
407     }
408 }
409
410 /* This function provides an internal consistency check of an edge list,
411    verifying that all edges are present, and that there are no
412    extra edges.  */
413
414 void
415 verify_edge_list (FILE *f, struct edge_list *elist)
416 {
417   int pred, succ, index;
418   edge e;
419   basic_block bb, p, s;
420   edge_iterator ei;
421
422   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
423     {
424       FOR_EACH_EDGE (e, ei, bb->succs)
425         {
426           pred = e->src->index;
427           succ = e->dest->index;
428           index = EDGE_INDEX (elist, e->src, e->dest);
429           if (index == EDGE_INDEX_NO_EDGE)
430             {
431               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
432               continue;
433             }
434
435           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
436             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
437                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
438           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
439             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
440                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
441         }
442     }
443
444   /* We've verified that all the edges are in the list, now lets make sure
445      there are no spurious edges in the list.  */
446
447   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
448     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
449       {
450         int found_edge = 0;
451
452         FOR_EACH_EDGE (e, ei, p->succs)
453           if (e->dest == s)
454             {
455               found_edge = 1;
456               break;
457             }
458
459         FOR_EACH_EDGE (e, ei, s->preds)
460           if (e->src == p)
461             {
462               found_edge = 1;
463               break;
464             }
465
466         if (EDGE_INDEX (elist, p, s)
467             == EDGE_INDEX_NO_EDGE && found_edge != 0)
468           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
469                    p->index, s->index);
470         if (EDGE_INDEX (elist, p, s)
471             != EDGE_INDEX_NO_EDGE && found_edge == 0)
472           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
473                    p->index, s->index, EDGE_INDEX (elist, p, s));
474       }
475 }
476
477 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
478    If no such edge exists, return NULL.  */
479
480 edge
481 find_edge (basic_block pred, basic_block succ)
482 {
483   edge e;
484   edge_iterator ei;
485
486   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
487     {
488       FOR_EACH_EDGE (e, ei, pred->succs)
489         if (e->dest == succ)
490           return e;
491     }
492   else
493     {
494       FOR_EACH_EDGE (e, ei, succ->preds)
495         if (e->src == pred)
496           return e;
497     }
498
499   return NULL;
500 }
501
502 /* This routine will determine what, if any, edge there is between
503    a specified predecessor and successor.  */
504
505 int
506 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
507 {
508   int x;
509
510   for (x = 0; x < NUM_EDGES (edge_list); x++)
511     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
512         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
513       return x;
514
515   return (EDGE_INDEX_NO_EDGE);
516 }
517
518 /* Dump the list of basic blocks in the bitmap NODES.  */
519
520 void
521 flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
522 {
523   unsigned int node = 0;
524   sbitmap_iterator sbi;
525
526   if (! nodes)
527     return;
528
529   fprintf (file, "%s { ", str);
530   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
531     fprintf (file, "%d ", node);
532   fputs ("}\n", file);
533 }
534
535 /* Dump the list of edges in the array EDGE_LIST.  */
536
537 void
538 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
539 {
540   int i;
541
542   if (! edge_list)
543     return;
544
545   fprintf (file, "%s { ", str);
546   for (i = 0; i < num_edges; i++)
547     fprintf (file, "%d->%d ", edge_list[i]->src->index,
548              edge_list[i]->dest->index);
549
550   fputs ("}\n", file);
551 }
552
553 \f
554 /* This routine will remove any fake predecessor edges for a basic block.
555    When the edge is removed, it is also removed from whatever successor
556    list it is in.  */
557
558 static void
559 remove_fake_predecessors (basic_block bb)
560 {
561   edge e;
562   edge_iterator ei;
563
564   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
565     {
566       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
567         remove_edge (e);
568       else
569         ei_next (&ei);
570     }
571 }
572
573 /* This routine will remove all fake edges from the flow graph.  If
574    we remove all fake successors, it will automatically remove all
575    fake predecessors.  */
576
577 void
578 remove_fake_edges (void)
579 {
580   basic_block bb;
581
582   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
583     remove_fake_predecessors (bb);
584 }
585
586 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
587
588 void
589 remove_fake_exit_edges (void)
590 {
591   remove_fake_predecessors (EXIT_BLOCK_PTR);
592 }
593
594
595 /* This function will add a fake edge between any block which has no
596    successors, and the exit block. Some data flow equations require these
597    edges to exist.  */
598
599 void
600 add_noreturn_fake_exit_edges (void)
601 {
602   basic_block bb;
603
604   FOR_EACH_BB (bb)
605     if (EDGE_COUNT (bb->succs) == 0)
606       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
607 }
608
609 /* This function adds a fake edge between any infinite loops to the
610    exit block.  Some optimizations require a path from each node to
611    the exit node.
612
613    See also Morgan, Figure 3.10, pp. 82-83.
614
615    The current implementation is ugly, not attempting to minimize the
616    number of inserted fake edges.  To reduce the number of fake edges
617    to insert, add fake edges from _innermost_ loops containing only
618    nodes not reachable from the exit block.  */
619
620 void
621 connect_infinite_loops_to_exit (void)
622 {
623   basic_block unvisited_block = EXIT_BLOCK_PTR;
624   struct depth_first_search_dsS dfs_ds;
625
626   /* Perform depth-first search in the reverse graph to find nodes
627      reachable from the exit block.  */
628   flow_dfs_compute_reverse_init (&dfs_ds);
629   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
630
631   /* Repeatedly add fake edges, updating the unreachable nodes.  */
632   while (1)
633     {
634       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
635                                                           unvisited_block);
636       if (!unvisited_block)
637         break;
638
639       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
640       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
641     }
642
643   flow_dfs_compute_reverse_finish (&dfs_ds);
644   return;
645 }
646 \f
647 /* Compute reverse top sort order.  This is computing a post order
648    numbering of the graph.  If INCLUDE_ENTRY_EXIT is true, then then
649    ENTRY_BLOCK and EXIT_BLOCK are included.  If DELETE_UNREACHABLE is
650    true, unreachable blocks are deleted.  */
651
652 int
653 post_order_compute (int *post_order, bool include_entry_exit, 
654                     bool delete_unreachable)
655 {
656   edge_iterator *stack;
657   int sp;
658   int post_order_num = 0;
659   sbitmap visited;
660   int count;
661
662   if (include_entry_exit)
663     post_order[post_order_num++] = EXIT_BLOCK;
664
665   /* Allocate stack for back-tracking up CFG.  */
666   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
667   sp = 0;
668
669   /* Allocate bitmap to track nodes that have been visited.  */
670   visited = sbitmap_alloc (last_basic_block);
671
672   /* None of the nodes in the CFG have been visited yet.  */
673   sbitmap_zero (visited);
674
675   /* Push the first edge on to the stack.  */
676   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
677
678   while (sp)
679     {
680       edge_iterator ei;
681       basic_block src;
682       basic_block dest;
683
684       /* Look at the edge on the top of the stack.  */
685       ei = stack[sp - 1];
686       src = ei_edge (ei)->src;
687       dest = ei_edge (ei)->dest;
688
689       /* Check if the edge destination has been visited yet.  */
690       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
691         {
692           /* Mark that we have visited the destination.  */
693           SET_BIT (visited, dest->index);
694
695           if (EDGE_COUNT (dest->succs) > 0)
696             /* Since the DEST node has been visited for the first
697                time, check its successors.  */
698             stack[sp++] = ei_start (dest->succs);
699           else
700             post_order[post_order_num++] = dest->index;
701         }
702       else
703         {
704           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
705             post_order[post_order_num++] = src->index;
706
707           if (!ei_one_before_end_p (ei))
708             ei_next (&stack[sp - 1]);
709           else
710             sp--;
711         }
712     }
713
714   if (include_entry_exit)
715     {
716       post_order[post_order_num++] = ENTRY_BLOCK;
717       count = post_order_num;
718     }
719   else 
720     count = post_order_num + 2;
721   
722   /* Delete the unreachable blocks if some were found and we are
723      supposed to do it.  */
724   if (delete_unreachable && (count != n_basic_blocks))
725     {
726       basic_block b;
727       basic_block next_bb;
728       for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
729         {
730           next_bb = b->next_bb;
731           
732           if (!(TEST_BIT (visited, b->index)))
733             delete_basic_block (b);
734         }
735       
736       tidy_fallthru_edges ();
737     }
738
739   free (stack);
740   sbitmap_free (visited);
741   return post_order_num;
742 }
743
744
745 /* Helper routine for inverted_post_order_compute. 
746    BB has to belong to a region of CFG
747    unreachable by inverted traversal from the exit.
748    i.e. there's no control flow path from ENTRY to EXIT
749    that contains this BB.
750    This can happen in two cases - if there's an infinite loop
751    or if there's a block that has no successor
752    (call to a function with no return).
753    Some RTL passes deal with this condition by 
754    calling connect_infinite_loops_to_exit () and/or 
755    add_noreturn_fake_exit_edges ().
756    However, those methods involve modifying the CFG itself
757    which may not be desirable.
758    Hence, we deal with the infinite loop/no return cases
759    by identifying a unique basic block that can reach all blocks
760    in such a region by inverted traversal.
761    This function returns a basic block that guarantees
762    that all blocks in the region are reachable
763    by starting an inverted traversal from the returned block.  */
764
765 static basic_block
766 dfs_find_deadend (basic_block bb)
767 {
768   sbitmap visited = sbitmap_alloc (last_basic_block);
769   sbitmap_zero (visited);
770
771   for (;;)
772     {
773       SET_BIT (visited, bb->index);
774       if (EDGE_COUNT (bb->succs) == 0
775           || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
776         {
777           sbitmap_free (visited);
778           return bb;
779         }
780
781       bb = EDGE_SUCC (bb, 0)->dest;
782     }
783
784   gcc_unreachable ();
785 }
786
787
788 /* Compute the reverse top sort order of the inverted CFG
789    i.e. starting from the exit block and following the edges backward
790    (from successors to predecessors).
791    This ordering can be used for forward dataflow problems among others.
792
793    This function assumes that all blocks in the CFG are reachable
794    from the ENTRY (but not necessarily from EXIT).
795
796    If there's an infinite loop,
797    a simple inverted traversal starting from the blocks
798    with no successors can't visit all blocks.
799    To solve this problem, we first do inverted traversal
800    starting from the blocks with no successor.
801    And if there's any block left that's not visited by the regular 
802    inverted traversal from EXIT,
803    those blocks are in such problematic region.
804    Among those, we find one block that has 
805    any visited predecessor (which is an entry into such a region),
806    and start looking for a "dead end" from that block 
807    and do another inverted traversal from that block.  */
808
809 int
810 inverted_post_order_compute (int *post_order)
811 {
812   basic_block bb;
813   edge_iterator *stack;
814   int sp;
815   int post_order_num = 0;
816   sbitmap visited;
817
818   /* Allocate stack for back-tracking up CFG.  */
819   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
820   sp = 0;
821
822   /* Allocate bitmap to track nodes that have been visited.  */
823   visited = sbitmap_alloc (last_basic_block);
824
825   /* None of the nodes in the CFG have been visited yet.  */
826   sbitmap_zero (visited);
827
828   /* Put all blocks that have no successor into the initial work list.  */
829   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
830     if (EDGE_COUNT (bb->succs) == 0)
831       {
832         /* Push the initial edge on to the stack.  */
833         if (EDGE_COUNT (bb->preds) > 0) 
834           {
835             stack[sp++] = ei_start (bb->preds);
836             SET_BIT (visited, bb->index);
837           }
838       }
839
840   do 
841     {
842       bool has_unvisited_bb = false;
843
844       /* The inverted traversal loop. */
845       while (sp)
846         {
847           edge_iterator ei;
848           basic_block pred;
849
850           /* Look at the edge on the top of the stack.  */
851           ei = stack[sp - 1];
852           bb = ei_edge (ei)->dest;
853           pred = ei_edge (ei)->src;
854
855           /* Check if the predecessor has been visited yet.  */
856           if (! TEST_BIT (visited, pred->index))
857             {
858               /* Mark that we have visited the destination.  */
859               SET_BIT (visited, pred->index);
860
861               if (EDGE_COUNT (pred->preds) > 0)
862                 /* Since the predecessor node has been visited for the first
863                    time, check its predecessors.  */
864                 stack[sp++] = ei_start (pred->preds);
865               else
866                 post_order[post_order_num++] = pred->index;
867             }
868           else
869             {
870               if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
871                 post_order[post_order_num++] = bb->index;
872
873               if (!ei_one_before_end_p (ei))
874                 ei_next (&stack[sp - 1]);
875               else
876                 sp--;
877             }
878         }
879
880       /* Detect any infinite loop and activate the kludge. 
881          Note that this doesn't check EXIT_BLOCK itself
882          since EXIT_BLOCK is always added after the outer do-while loop.  */
883       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
884         if (!TEST_BIT (visited, bb->index))
885           {
886             has_unvisited_bb = true;
887
888             if (EDGE_COUNT (bb->preds) > 0)
889               {
890                 edge_iterator ei;
891                 edge e;
892                 basic_block visited_pred = NULL;
893
894                 /* Find an already visited predecessor.  */
895                 FOR_EACH_EDGE (e, ei, bb->preds)
896                   {
897                     if (TEST_BIT (visited, e->src->index))
898                       visited_pred = e->src;
899                   }
900
901                 if (visited_pred)
902                   {
903                     basic_block be = dfs_find_deadend (bb);
904                     gcc_assert (be != NULL);
905                     SET_BIT (visited, be->index);
906                     stack[sp++] = ei_start (be->preds);
907                     break;
908                   }
909               }
910           }
911
912       if (has_unvisited_bb && sp == 0)
913         {
914           /* No blocks are reachable from EXIT at all. 
915              Find a dead-end from the ENTRY, and restart the iteration. */
916           basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
917           gcc_assert (be != NULL);
918           SET_BIT (visited, be->index);
919           stack[sp++] = ei_start (be->preds);
920         }
921
922       /* The only case the below while fires is 
923          when there's an infinite loop.  */
924     }
925   while (sp);
926
927   /* EXIT_BLOCK is always included.  */
928   post_order[post_order_num++] = EXIT_BLOCK;
929
930   free (stack);
931   sbitmap_free (visited);
932   return post_order_num;
933 }
934
935 /* Compute the depth first search order and store in the array
936   PRE_ORDER if nonzero, marking the nodes visited in VISITED.  If
937   REV_POST_ORDER is nonzero, return the reverse completion number for each
938   node.  Returns the number of nodes visited.  A depth first search
939   tries to get as far away from the starting point as quickly as
940   possible. 
941
942   pre_order is a really a preorder numbering of the graph.
943   rev_post_order is really a reverse postorder numbering of the graph.
944  */
945
946 int
947 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, 
948                                 bool include_entry_exit)
949 {
950   edge_iterator *stack;
951   int sp;
952   int pre_order_num = 0;
953   int rev_post_order_num = n_basic_blocks - 1;
954   sbitmap visited;
955
956   /* Allocate stack for back-tracking up CFG.  */
957   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
958   sp = 0;
959
960   if (include_entry_exit)
961     {
962       if (pre_order)
963         pre_order[pre_order_num] = ENTRY_BLOCK;
964       pre_order_num++;
965       if (rev_post_order)
966         rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
967     }
968   else 
969     rev_post_order_num -= NUM_FIXED_BLOCKS;
970
971   /* Allocate bitmap to track nodes that have been visited.  */
972   visited = sbitmap_alloc (last_basic_block);
973
974   /* None of the nodes in the CFG have been visited yet.  */
975   sbitmap_zero (visited);
976
977   /* Push the first edge on to the stack.  */
978   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
979
980   while (sp)
981     {
982       edge_iterator ei;
983       basic_block src;
984       basic_block dest;
985
986       /* Look at the edge on the top of the stack.  */
987       ei = stack[sp - 1];
988       src = ei_edge (ei)->src;
989       dest = ei_edge (ei)->dest;
990
991       /* Check if the edge destination has been visited yet.  */
992       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
993         {
994           /* Mark that we have visited the destination.  */
995           SET_BIT (visited, dest->index);
996
997           if (pre_order)
998             pre_order[pre_order_num] = dest->index;
999
1000           pre_order_num++;
1001
1002           if (EDGE_COUNT (dest->succs) > 0)
1003             /* Since the DEST node has been visited for the first
1004                time, check its successors.  */
1005             stack[sp++] = ei_start (dest->succs);
1006           else if (rev_post_order)
1007             /* There are no successors for the DEST node so assign
1008                its reverse completion number.  */
1009             rev_post_order[rev_post_order_num--] = dest->index;
1010         }
1011       else
1012         {
1013           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
1014               && rev_post_order)
1015             /* There are no more successors for the SRC node
1016                so assign its reverse completion number.  */
1017             rev_post_order[rev_post_order_num--] = src->index;
1018
1019           if (!ei_one_before_end_p (ei))
1020             ei_next (&stack[sp - 1]);
1021           else
1022             sp--;
1023         }
1024     }
1025
1026   free (stack);
1027   sbitmap_free (visited);
1028
1029   if (include_entry_exit)
1030     {
1031       if (pre_order)
1032         pre_order[pre_order_num] = EXIT_BLOCK;
1033       pre_order_num++;
1034       if (rev_post_order)
1035         rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
1036       /* The number of nodes visited should be the number of blocks.  */
1037       gcc_assert (pre_order_num == n_basic_blocks);
1038     }
1039   else
1040     /* The number of nodes visited should be the number of blocks minus
1041        the entry and exit blocks which are not visited here.  */
1042     gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
1043
1044   return pre_order_num;
1045 }
1046
1047 /* Compute the depth first search order on the _reverse_ graph and
1048    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1049    Returns the number of nodes visited.
1050
1051    The computation is split into three pieces:
1052
1053    flow_dfs_compute_reverse_init () creates the necessary data
1054    structures.
1055
1056    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1057    structures.  The block will start the search.
1058
1059    flow_dfs_compute_reverse_execute () continues (or starts) the
1060    search using the block on the top of the stack, stopping when the
1061    stack is empty.
1062
1063    flow_dfs_compute_reverse_finish () destroys the necessary data
1064    structures.
1065
1066    Thus, the user will probably call ..._init(), call ..._add_bb() to
1067    add a beginning basic block to the stack, call ..._execute(),
1068    possibly add another bb to the stack and again call ..._execute(),
1069    ..., and finally call _finish().  */
1070
1071 /* Initialize the data structures used for depth-first search on the
1072    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1073    added to the basic block stack.  DATA is the current depth-first
1074    search context.  If INITIALIZE_STACK is nonzero, there is an
1075    element on the stack.  */
1076
1077 static void
1078 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1079 {
1080   /* Allocate stack for back-tracking up CFG.  */
1081   data->stack = XNEWVEC (basic_block, n_basic_blocks);
1082   data->sp = 0;
1083
1084   /* Allocate bitmap to track nodes that have been visited.  */
1085   data->visited_blocks = sbitmap_alloc (last_basic_block);
1086
1087   /* None of the nodes in the CFG have been visited yet.  */
1088   sbitmap_zero (data->visited_blocks);
1089
1090   return;
1091 }
1092
1093 /* Add the specified basic block to the top of the dfs data
1094    structures.  When the search continues, it will start at the
1095    block.  */
1096
1097 static void
1098 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1099 {
1100   data->stack[data->sp++] = bb;
1101   SET_BIT (data->visited_blocks, bb->index);
1102 }
1103
1104 /* Continue the depth-first search through the reverse graph starting with the
1105    block at the stack's top and ending when the stack is empty.  Visited nodes
1106    are marked.  Returns an unvisited basic block, or NULL if there is none
1107    available.  */
1108
1109 static basic_block
1110 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
1111                                   basic_block last_unvisited)
1112 {
1113   basic_block bb;
1114   edge e;
1115   edge_iterator ei;
1116
1117   while (data->sp > 0)
1118     {
1119       bb = data->stack[--data->sp];
1120
1121       /* Perform depth-first search on adjacent vertices.  */
1122       FOR_EACH_EDGE (e, ei, bb->preds)
1123         if (!TEST_BIT (data->visited_blocks, e->src->index))
1124           flow_dfs_compute_reverse_add_bb (data, e->src);
1125     }
1126
1127   /* Determine if there are unvisited basic blocks.  */
1128   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1129     if (!TEST_BIT (data->visited_blocks, bb->index))
1130       return bb;
1131
1132   return NULL;
1133 }
1134
1135 /* Destroy the data structures needed for depth-first search on the
1136    reverse graph.  */
1137
1138 static void
1139 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1140 {
1141   free (data->stack);
1142   sbitmap_free (data->visited_blocks);
1143 }
1144
1145 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1146    if REVERSE, go against direction of edges.  Returns number of blocks
1147    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
1148 int
1149 dfs_enumerate_from (basic_block bb, int reverse,
1150                     bool (*predicate) (const_basic_block, const void *),
1151                     basic_block *rslt, int rslt_max, const void *data)
1152 {
1153   basic_block *st, lbb;
1154   int sp = 0, tv = 0;
1155   unsigned size;
1156
1157   /* A bitmap to keep track of visited blocks.  Allocating it each time
1158      this function is called is not possible, since dfs_enumerate_from
1159      is often used on small (almost) disjoint parts of cfg (bodies of
1160      loops), and allocating a large sbitmap would lead to quadratic
1161      behavior.  */
1162   static sbitmap visited;
1163   static unsigned v_size;
1164
1165 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index)) 
1166 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index)) 
1167 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index)) 
1168
1169   /* Resize the VISITED sbitmap if necessary.  */
1170   size = last_basic_block; 
1171   if (size < 10)
1172     size = 10;
1173
1174   if (!visited)
1175     {
1176
1177       visited = sbitmap_alloc (size);
1178       sbitmap_zero (visited);
1179       v_size = size;
1180     }
1181   else if (v_size < size)
1182     {
1183       /* Ensure that we increase the size of the sbitmap exponentially.  */
1184       if (2 * v_size > size)
1185         size = 2 * v_size;
1186
1187       visited = sbitmap_resize (visited, size, 0);
1188       v_size = size;
1189     }
1190
1191   st = XCNEWVEC (basic_block, rslt_max);
1192   rslt[tv++] = st[sp++] = bb;
1193   MARK_VISITED (bb);
1194   while (sp)
1195     {
1196       edge e;
1197       edge_iterator ei;
1198       lbb = st[--sp];
1199       if (reverse)
1200         {
1201           FOR_EACH_EDGE (e, ei, lbb->preds)
1202             if (!VISITED_P (e->src) && predicate (e->src, data))
1203               {
1204                 gcc_assert (tv != rslt_max);
1205                 rslt[tv++] = st[sp++] = e->src;
1206                 MARK_VISITED (e->src);
1207               }
1208         }
1209       else
1210         {
1211           FOR_EACH_EDGE (e, ei, lbb->succs)
1212             if (!VISITED_P (e->dest) && predicate (e->dest, data))
1213               {
1214                 gcc_assert (tv != rslt_max);
1215                 rslt[tv++] = st[sp++] = e->dest;
1216                 MARK_VISITED (e->dest);
1217               }
1218         }
1219     }
1220   free (st);
1221   for (sp = 0; sp < tv; sp++)
1222     UNMARK_VISITED (rslt[sp]);
1223   return tv;
1224 #undef MARK_VISITED
1225 #undef UNMARK_VISITED
1226 #undef VISITED_P
1227 }
1228
1229
1230 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1231
1232    This algorithm can be found in Timothy Harvey's PhD thesis, at
1233    http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1234    dominance algorithms.
1235
1236    First, we identify each join point, j (any node with more than one
1237    incoming edge is a join point).
1238
1239    We then examine each predecessor, p, of j and walk up the dominator tree
1240    starting at p.
1241
1242    We stop the walk when we reach j's immediate dominator - j is in the
1243    dominance frontier of each of  the nodes in the walk, except for j's
1244    immediate dominator. Intuitively, all of the rest of j's dominators are
1245    shared by j's predecessors as well.
1246    Since they dominate j, they will not have j in their dominance frontiers.
1247
1248    The number of nodes touched by this algorithm is equal to the size
1249    of the dominance frontiers, no more, no less.
1250 */
1251
1252
1253 static void
1254 compute_dominance_frontiers_1 (bitmap *frontiers)
1255 {
1256   edge p;
1257   edge_iterator ei;
1258   basic_block b;
1259   FOR_EACH_BB (b)
1260     {
1261       if (EDGE_COUNT (b->preds) >= 2)
1262         {
1263           FOR_EACH_EDGE (p, ei, b->preds)
1264             {
1265               basic_block runner = p->src;
1266               basic_block domsb;
1267               if (runner == ENTRY_BLOCK_PTR)
1268                 continue;
1269
1270               domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1271               while (runner != domsb)
1272                 {
1273                   if (bitmap_bit_p (frontiers[runner->index], b->index))
1274                     break;
1275                   bitmap_set_bit (frontiers[runner->index],
1276                                   b->index);
1277                   runner = get_immediate_dominator (CDI_DOMINATORS,
1278                                                     runner);
1279                 }
1280             }
1281         }
1282     }
1283 }
1284
1285
1286 void
1287 compute_dominance_frontiers (bitmap *frontiers)
1288 {
1289   timevar_push (TV_DOM_FRONTIERS);
1290
1291   compute_dominance_frontiers_1 (frontiers);
1292
1293   timevar_pop (TV_DOM_FRONTIERS);
1294 }