Daily bump.
[official-gcc.git] / gcc / cfganal.c
blob66214d7fec623710118a73faa9a4ebee4b1cd63d
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.
5 This file is part of GCC.
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.
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.
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/>. */
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"
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;
41 /* number of edges in the stack. That is, positions 0, ..., sp-1
42 have edges. */
43 unsigned int sp;
45 /* record of basic blocks already seen by depth-first search */
46 sbitmap visited_blocks;
48 typedef struct depth_first_search_dsS *depth_first_search_ds;
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);
58 /* Like active_insn_p, except keep the return value clobber around
59 even after reload. */
61 static bool
62 flow_active_insn_p (const_rtx insn)
64 if (active_insn_p (insn))
65 return true;
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;
77 return false;
80 /* Return true if the block has no effect and only forwards control flow to
81 its single destination. */
83 bool
84 forwarder_block_p (const_basic_block bb)
86 rtx insn;
88 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
89 || !single_succ_p (bb))
90 return false;
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;
96 return (!INSN_P (insn)
97 || (JUMP_P (insn) && simplejump_p (insn))
98 || !flow_active_insn_p (insn));
101 /* Return nonzero if we can reach target from src by falling through. */
103 bool
104 can_fallthru (basic_block src, basic_block target)
106 rtx insn = BB_END (src);
107 rtx insn2;
108 edge e;
109 edge_iterator ei;
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;
120 insn2 = BB_HEAD (target);
121 if (insn2 && !active_insn_p (insn2))
122 insn2 = next_active_insn (insn2);
124 /* ??? Later we may add code to move jump tables offline. */
125 return next_active_insn (insn) == insn2;
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)
134 edge e;
135 edge_iterator ei;
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;
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:
150 Advanced Compiler Design and Implementation
151 Steven Muchnick
152 Morgan Kaufmann, 1997
154 and heavily borrowed from pre_and_rev_post_order_compute. */
156 bool
157 mark_dfs_back_edges (void)
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;
168 /* Allocate the preorder and postorder number arrays. */
169 pre = XCNEWVEC (int, last_basic_block);
170 post = XCNEWVEC (int, last_basic_block);
172 /* Allocate stack for back-tracking up CFG. */
173 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
174 sp = 0;
176 /* Allocate bitmap to track nodes that have been visited. */
177 visited = sbitmap_alloc (last_basic_block);
179 /* None of the nodes in the CFG have been visited yet. */
180 sbitmap_zero (visited);
182 /* Push the first edge on to the stack. */
183 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
185 while (sp)
187 edge_iterator ei;
188 basic_block src;
189 basic_block dest;
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;
197 /* Check if the edge destination has been visited yet. */
198 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
200 /* Mark that we have visited the destination. */
201 SET_BIT (visited, dest->index);
203 pre[dest->index] = prenum++;
204 if (EDGE_COUNT (dest->succs) > 0)
206 /* Since the DEST node has been visited for the first
207 time, check its successors. */
208 stack[sp++] = ei_start (dest->succs);
210 else
211 post[dest->index] = postnum++;
213 else
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;
220 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
221 post[src->index] = postnum++;
223 if (!ei_one_before_end_p (ei))
224 ei_next (&stack[sp - 1]);
225 else
226 sp--;
230 free (pre);
231 free (post);
232 free (stack);
233 sbitmap_free (visited);
235 return found;
238 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
240 void
241 set_edge_can_fallthru_flag (void)
243 basic_block bb;
245 FOR_EACH_BB (bb)
247 edge e;
248 edge_iterator ei;
250 FOR_EACH_EDGE (e, ei, bb->succs)
252 e->flags &= ~EDGE_CAN_FALLTHRU;
254 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
255 if (e->flags & EDGE_FALLTHRU)
256 e->flags |= EDGE_CAN_FALLTHRU;
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;
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. */
277 void
278 find_unreachable_blocks (void)
280 edge e;
281 edge_iterator ei;
282 basic_block *tos, *worklist, bb;
284 tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
286 /* Clear all the reachability flags. */
288 FOR_EACH_BB (bb)
289 bb->flags &= ~BB_REACHABLE;
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. */
295 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
297 *tos++ = e->dest;
299 /* Mark the block reachable. */
300 e->dest->flags |= BB_REACHABLE;
303 /* Iterate: find everything reachable from what we've already seen. */
305 while (tos != worklist)
307 basic_block b = *--tos;
309 FOR_EACH_EDGE (e, ei, b->succs)
311 basic_block dest = e->dest;
313 if (!(dest->flags & BB_REACHABLE))
315 *tos++ = dest;
316 dest->flags |= BB_REACHABLE;
321 free (worklist);
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. */
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. */
337 struct edge_list *
338 create_edge_list (void)
340 struct edge_list *elist;
341 edge e;
342 int num_edges;
343 int block_count;
344 basic_block bb;
345 edge_iterator ei;
347 block_count = n_basic_blocks; /* Include the entry and exit blocks. */
349 num_edges = 0;
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)
355 num_edges += EDGE_COUNT (bb->succs);
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);
363 num_edges = 0;
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;
370 return elist;
373 /* This function free's memory associated with an edge list. */
375 void
376 free_edge_list (struct edge_list *elist)
378 if (elist)
380 free (elist->index_to_edge);
381 free (elist);
385 /* This function provides debug output showing an edge list. */
387 void
388 print_edge_list (FILE *f, struct edge_list *elist)
390 int x;
392 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
393 elist->num_blocks, elist->num_edges);
395 for (x = 0; x < elist->num_edges; x++)
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);
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);
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. */
414 void
415 verify_edge_list (FILE *f, struct edge_list *elist)
417 int pred, succ, index;
418 edge e;
419 basic_block bb, p, s;
420 edge_iterator ei;
422 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
424 FOR_EACH_EDGE (e, ei, bb->succs)
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)
431 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
432 continue;
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);
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. */
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)
450 int found_edge = 0;
452 FOR_EACH_EDGE (e, ei, p->succs)
453 if (e->dest == s)
455 found_edge = 1;
456 break;
459 FOR_EACH_EDGE (e, ei, s->preds)
460 if (e->src == p)
462 found_edge = 1;
463 break;
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));
477 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
478 If no such edge exists, return NULL. */
480 edge
481 find_edge (basic_block pred, basic_block succ)
483 edge e;
484 edge_iterator ei;
486 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
488 FOR_EACH_EDGE (e, ei, pred->succs)
489 if (e->dest == succ)
490 return e;
492 else
494 FOR_EACH_EDGE (e, ei, succ->preds)
495 if (e->src == pred)
496 return e;
499 return NULL;
502 /* This routine will determine what, if any, edge there is between
503 a specified predecessor and successor. */
506 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
508 int x;
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;
515 return (EDGE_INDEX_NO_EDGE);
518 /* Dump the list of basic blocks in the bitmap NODES. */
520 void
521 flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
523 unsigned int node = 0;
524 sbitmap_iterator sbi;
526 if (! nodes)
527 return;
529 fprintf (file, "%s { ", str);
530 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
531 fprintf (file, "%d ", node);
532 fputs ("}\n", file);
535 /* Dump the list of edges in the array EDGE_LIST. */
537 void
538 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
540 int i;
542 if (! edge_list)
543 return;
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);
550 fputs ("}\n", file);
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. */
558 static void
559 remove_fake_predecessors (basic_block bb)
561 edge e;
562 edge_iterator ei;
564 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
566 if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
567 remove_edge (e);
568 else
569 ei_next (&ei);
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. */
577 void
578 remove_fake_edges (void)
580 basic_block bb;
582 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
583 remove_fake_predecessors (bb);
586 /* This routine will remove all fake edges to the EXIT_BLOCK. */
588 void
589 remove_fake_exit_edges (void)
591 remove_fake_predecessors (EXIT_BLOCK_PTR);
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. */
599 void
600 add_noreturn_fake_exit_edges (void)
602 basic_block bb;
604 FOR_EACH_BB (bb)
605 if (EDGE_COUNT (bb->succs) == 0)
606 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
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.
613 See also Morgan, Figure 3.10, pp. 82-83.
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. */
620 void
621 connect_infinite_loops_to_exit (void)
623 basic_block unvisited_block = EXIT_BLOCK_PTR;
624 struct depth_first_search_dsS dfs_ds;
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);
631 /* Repeatedly add fake edges, updating the unreachable nodes. */
632 while (1)
634 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
635 unvisited_block);
636 if (!unvisited_block)
637 break;
639 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
640 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
643 flow_dfs_compute_reverse_finish (&dfs_ds);
644 return;
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. */
653 post_order_compute (int *post_order, bool include_entry_exit,
654 bool delete_unreachable)
656 edge_iterator *stack;
657 int sp;
658 int post_order_num = 0;
659 sbitmap visited;
660 int count;
662 if (include_entry_exit)
663 post_order[post_order_num++] = EXIT_BLOCK;
665 /* Allocate stack for back-tracking up CFG. */
666 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
667 sp = 0;
669 /* Allocate bitmap to track nodes that have been visited. */
670 visited = sbitmap_alloc (last_basic_block);
672 /* None of the nodes in the CFG have been visited yet. */
673 sbitmap_zero (visited);
675 /* Push the first edge on to the stack. */
676 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
678 while (sp)
680 edge_iterator ei;
681 basic_block src;
682 basic_block dest;
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;
689 /* Check if the edge destination has been visited yet. */
690 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
692 /* Mark that we have visited the destination. */
693 SET_BIT (visited, dest->index);
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;
702 else
704 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
705 post_order[post_order_num++] = src->index;
707 if (!ei_one_before_end_p (ei))
708 ei_next (&stack[sp - 1]);
709 else
710 sp--;
714 if (include_entry_exit)
716 post_order[post_order_num++] = ENTRY_BLOCK;
717 count = post_order_num;
719 else
720 count = post_order_num + 2;
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))
726 basic_block b;
727 basic_block next_bb;
728 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
730 next_bb = b->next_bb;
732 if (!(TEST_BIT (visited, b->index)))
733 delete_basic_block (b);
736 tidy_fallthru_edges ();
739 free (stack);
740 sbitmap_free (visited);
741 return post_order_num;
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. */
765 static basic_block
766 dfs_find_deadend (basic_block bb)
768 sbitmap visited = sbitmap_alloc (last_basic_block);
769 sbitmap_zero (visited);
771 for (;;)
773 SET_BIT (visited, bb->index);
774 if (EDGE_COUNT (bb->succs) == 0
775 || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
777 sbitmap_free (visited);
778 return bb;
781 bb = EDGE_SUCC (bb, 0)->dest;
784 gcc_unreachable ();
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.
793 This function assumes that all blocks in the CFG are reachable
794 from the ENTRY (but not necessarily from EXIT).
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. */
810 inverted_post_order_compute (int *post_order)
812 basic_block bb;
813 edge_iterator *stack;
814 int sp;
815 int post_order_num = 0;
816 sbitmap visited;
818 /* Allocate stack for back-tracking up CFG. */
819 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
820 sp = 0;
822 /* Allocate bitmap to track nodes that have been visited. */
823 visited = sbitmap_alloc (last_basic_block);
825 /* None of the nodes in the CFG have been visited yet. */
826 sbitmap_zero (visited);
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)
832 /* Push the initial edge on to the stack. */
833 if (EDGE_COUNT (bb->preds) > 0)
835 stack[sp++] = ei_start (bb->preds);
836 SET_BIT (visited, bb->index);
842 bool has_unvisited_bb = false;
844 /* The inverted traversal loop. */
845 while (sp)
847 edge_iterator ei;
848 basic_block pred;
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;
855 /* Check if the predecessor has been visited yet. */
856 if (! TEST_BIT (visited, pred->index))
858 /* Mark that we have visited the destination. */
859 SET_BIT (visited, pred->index);
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;
868 else
870 if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
871 post_order[post_order_num++] = bb->index;
873 if (!ei_one_before_end_p (ei))
874 ei_next (&stack[sp - 1]);
875 else
876 sp--;
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))
886 has_unvisited_bb = true;
888 if (EDGE_COUNT (bb->preds) > 0)
890 edge_iterator ei;
891 edge e;
892 basic_block visited_pred = NULL;
894 /* Find an already visited predecessor. */
895 FOR_EACH_EDGE (e, ei, bb->preds)
897 if (TEST_BIT (visited, e->src->index))
898 visited_pred = e->src;
901 if (visited_pred)
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;
912 if (has_unvisited_bb && sp == 0)
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);
922 /* The only case the below while fires is
923 when there's an infinite loop. */
925 while (sp);
927 /* EXIT_BLOCK is always included. */
928 post_order[post_order_num++] = EXIT_BLOCK;
930 free (stack);
931 sbitmap_free (visited);
932 return post_order_num;
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.
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.
947 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
948 bool include_entry_exit)
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;
956 /* Allocate stack for back-tracking up CFG. */
957 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
958 sp = 0;
960 if (include_entry_exit)
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;
968 else
969 rev_post_order_num -= NUM_FIXED_BLOCKS;
971 /* Allocate bitmap to track nodes that have been visited. */
972 visited = sbitmap_alloc (last_basic_block);
974 /* None of the nodes in the CFG have been visited yet. */
975 sbitmap_zero (visited);
977 /* Push the first edge on to the stack. */
978 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
980 while (sp)
982 edge_iterator ei;
983 basic_block src;
984 basic_block dest;
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;
991 /* Check if the edge destination has been visited yet. */
992 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
994 /* Mark that we have visited the destination. */
995 SET_BIT (visited, dest->index);
997 if (pre_order)
998 pre_order[pre_order_num] = dest->index;
1000 pre_order_num++;
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;
1011 else
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;
1019 if (!ei_one_before_end_p (ei))
1020 ei_next (&stack[sp - 1]);
1021 else
1022 sp--;
1026 free (stack);
1027 sbitmap_free (visited);
1029 if (include_entry_exit)
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);
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);
1044 return pre_order_num;
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.
1051 The computation is split into three pieces:
1053 flow_dfs_compute_reverse_init () creates the necessary data
1054 structures.
1056 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1057 structures. The block will start the search.
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.
1063 flow_dfs_compute_reverse_finish () destroys the necessary data
1064 structures.
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(). */
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. */
1077 static void
1078 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1080 /* Allocate stack for back-tracking up CFG. */
1081 data->stack = XNEWVEC (basic_block, n_basic_blocks);
1082 data->sp = 0;
1084 /* Allocate bitmap to track nodes that have been visited. */
1085 data->visited_blocks = sbitmap_alloc (last_basic_block);
1087 /* None of the nodes in the CFG have been visited yet. */
1088 sbitmap_zero (data->visited_blocks);
1090 return;
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. */
1097 static void
1098 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1100 data->stack[data->sp++] = bb;
1101 SET_BIT (data->visited_blocks, bb->index);
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. */
1109 static basic_block
1110 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
1111 basic_block last_unvisited)
1113 basic_block bb;
1114 edge e;
1115 edge_iterator ei;
1117 while (data->sp > 0)
1119 bb = data->stack[--data->sp];
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);
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;
1132 return NULL;
1135 /* Destroy the data structures needed for depth-first search on the
1136 reverse graph. */
1138 static void
1139 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1141 free (data->stack);
1142 sbitmap_free (data->visited_blocks);
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. */
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)
1153 basic_block *st, lbb;
1154 int sp = 0, tv = 0;
1155 unsigned size;
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;
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))
1169 /* Resize the VISITED sbitmap if necessary. */
1170 size = last_basic_block;
1171 if (size < 10)
1172 size = 10;
1174 if (!visited)
1177 visited = sbitmap_alloc (size);
1178 sbitmap_zero (visited);
1179 v_size = size;
1181 else if (v_size < size)
1183 /* Ensure that we increase the size of the sbitmap exponentially. */
1184 if (2 * v_size > size)
1185 size = 2 * v_size;
1187 visited = sbitmap_resize (visited, size, 0);
1188 v_size = size;
1191 st = XCNEWVEC (basic_block, rslt_max);
1192 rslt[tv++] = st[sp++] = bb;
1193 MARK_VISITED (bb);
1194 while (sp)
1196 edge e;
1197 edge_iterator ei;
1198 lbb = st[--sp];
1199 if (reverse)
1201 FOR_EACH_EDGE (e, ei, lbb->preds)
1202 if (!VISITED_P (e->src) && predicate (e->src, data))
1204 gcc_assert (tv != rslt_max);
1205 rslt[tv++] = st[sp++] = e->src;
1206 MARK_VISITED (e->src);
1209 else
1211 FOR_EACH_EDGE (e, ei, lbb->succs)
1212 if (!VISITED_P (e->dest) && predicate (e->dest, data))
1214 gcc_assert (tv != rslt_max);
1215 rslt[tv++] = st[sp++] = e->dest;
1216 MARK_VISITED (e->dest);
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
1230 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
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.
1236 First, we identify each join point, j (any node with more than one
1237 incoming edge is a join point).
1239 We then examine each predecessor, p, of j and walk up the dominator tree
1240 starting at p.
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.
1248 The number of nodes touched by this algorithm is equal to the size
1249 of the dominance frontiers, no more, no less.
1253 static void
1254 compute_dominance_frontiers_1 (bitmap *frontiers)
1256 edge p;
1257 edge_iterator ei;
1258 basic_block b;
1259 FOR_EACH_BB (b)
1261 if (EDGE_COUNT (b->preds) >= 2)
1263 FOR_EACH_EDGE (p, ei, b->preds)
1265 basic_block runner = p->src;
1266 basic_block domsb;
1267 if (runner == ENTRY_BLOCK_PTR)
1268 continue;
1270 domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1271 while (runner != domsb)
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);
1286 void
1287 compute_dominance_frontiers (bitmap *frontiers)
1289 timevar_push (TV_DOM_FRONTIERS);
1291 compute_dominance_frontiers_1 (frontiers);
1293 timevar_pop (TV_DOM_FRONTIERS);