Daily bump.
[official-gcc.git] / gcc / cfganal.c
blob7cecd984a02ab5ff0546d8de454323b4827aab5a
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 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
22 /* This file contains various simple utilities to analyze the CFG. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "rtl.h"
28 #include "obstack.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "insn-config.h"
32 #include "recog.h"
33 #include "toplev.h"
34 #include "tm_p.h"
35 #include "timevar.h"
37 /* Store the data structures necessary for depth-first search. */
38 struct depth_first_search_dsS {
39 /* stack for backtracking during the algorithm */
40 basic_block *stack;
42 /* number of edges in the stack. That is, positions 0, ..., sp-1
43 have edges. */
44 unsigned int sp;
46 /* record of basic blocks already seen by depth-first search */
47 sbitmap visited_blocks;
49 typedef struct depth_first_search_dsS *depth_first_search_ds;
51 static void flow_dfs_compute_reverse_init (depth_first_search_ds);
52 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
53 basic_block);
54 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
55 basic_block);
56 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
57 static bool flow_active_insn_p (rtx);
59 /* Like active_insn_p, except keep the return value clobber around
60 even after reload. */
62 static bool
63 flow_active_insn_p (rtx insn)
65 if (active_insn_p (insn))
66 return true;
68 /* A clobber of the function return value exists for buggy
69 programs that fail to return a value. Its effect is to
70 keep the return value from being live across the entire
71 function. If we allow it to be skipped, we introduce the
72 possibility for register livetime aborts. */
73 if (GET_CODE (PATTERN (insn)) == CLOBBER
74 && REG_P (XEXP (PATTERN (insn), 0))
75 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
76 return true;
78 return false;
81 /* Return true if the block has no effect and only forwards control flow to
82 its single destination. */
84 bool
85 forwarder_block_p (basic_block bb)
87 rtx insn;
89 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
90 || !single_succ_p (bb))
91 return false;
93 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
94 if (INSN_P (insn) && flow_active_insn_p (insn))
95 return false;
97 return (!INSN_P (insn)
98 || (JUMP_P (insn) && simplejump_p (insn))
99 || !flow_active_insn_p (insn));
102 /* Return nonzero if we can reach target from src by falling through. */
104 bool
105 can_fallthru (basic_block src, basic_block target)
107 rtx insn = BB_END (src);
108 rtx insn2;
109 edge e;
110 edge_iterator ei;
112 if (target == EXIT_BLOCK_PTR)
113 return true;
114 if (src->next_bb != target)
115 return 0;
116 FOR_EACH_EDGE (e, ei, src->succs)
117 if (e->dest == EXIT_BLOCK_PTR
118 && e->flags & EDGE_FALLTHRU)
119 return 0;
121 insn2 = BB_HEAD (target);
122 if (insn2 && !active_insn_p (insn2))
123 insn2 = next_active_insn (insn2);
125 /* ??? Later we may add code to move jump tables offline. */
126 return next_active_insn (insn) == insn2;
129 /* Return nonzero if we could reach target from src by falling through,
130 if the target was made adjacent. If we already have a fall-through
131 edge to the exit block, we can't do that. */
132 bool
133 could_fall_through (basic_block src, basic_block target)
135 edge e;
136 edge_iterator ei;
138 if (target == EXIT_BLOCK_PTR)
139 return true;
140 FOR_EACH_EDGE (e, ei, src->succs)
141 if (e->dest == EXIT_BLOCK_PTR
142 && e->flags & EDGE_FALLTHRU)
143 return 0;
144 return true;
147 /* Mark the back edges in DFS traversal.
148 Return nonzero if a loop (natural or otherwise) is present.
149 Inspired by Depth_First_Search_PP described in:
151 Advanced Compiler Design and Implementation
152 Steven Muchnick
153 Morgan Kaufmann, 1997
155 and heavily borrowed from flow_depth_first_order_compute. */
157 bool
158 mark_dfs_back_edges (void)
160 edge_iterator *stack;
161 int *pre;
162 int *post;
163 int sp;
164 int prenum = 1;
165 int postnum = 1;
166 sbitmap visited;
167 bool found = false;
169 /* Allocate the preorder and postorder number arrays. */
170 pre = xcalloc (last_basic_block, sizeof (int));
171 post = xcalloc (last_basic_block, sizeof (int));
173 /* Allocate stack for back-tracking up CFG. */
174 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
175 sp = 0;
177 /* Allocate bitmap to track nodes that have been visited. */
178 visited = sbitmap_alloc (last_basic_block);
180 /* None of the nodes in the CFG have been visited yet. */
181 sbitmap_zero (visited);
183 /* Push the first edge on to the stack. */
184 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
186 while (sp)
188 edge_iterator ei;
189 basic_block src;
190 basic_block dest;
192 /* Look at the edge on the top of the stack. */
193 ei = stack[sp - 1];
194 src = ei_edge (ei)->src;
195 dest = ei_edge (ei)->dest;
196 ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
198 /* Check if the edge destination has been visited yet. */
199 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
201 /* Mark that we have visited the destination. */
202 SET_BIT (visited, dest->index);
204 pre[dest->index] = prenum++;
205 if (EDGE_COUNT (dest->succs) > 0)
207 /* Since the DEST node has been visited for the first
208 time, check its successors. */
209 stack[sp++] = ei_start (dest->succs);
211 else
212 post[dest->index] = postnum++;
214 else
216 if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
217 && pre[src->index] >= pre[dest->index]
218 && post[dest->index] == 0)
219 ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
221 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
222 post[src->index] = postnum++;
224 if (!ei_one_before_end_p (ei))
225 ei_next (&stack[sp - 1]);
226 else
227 sp--;
231 free (pre);
232 free (post);
233 free (stack);
234 sbitmap_free (visited);
236 return found;
239 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
241 void
242 set_edge_can_fallthru_flag (void)
244 basic_block bb;
246 FOR_EACH_BB (bb)
248 edge e;
249 edge_iterator ei;
251 FOR_EACH_EDGE (e, ei, bb->succs)
253 e->flags &= ~EDGE_CAN_FALLTHRU;
255 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
256 if (e->flags & EDGE_FALLTHRU)
257 e->flags |= EDGE_CAN_FALLTHRU;
260 /* If the BB ends with an invertible condjump all (2) edges are
261 CAN_FALLTHRU edges. */
262 if (EDGE_COUNT (bb->succs) != 2)
263 continue;
264 if (!any_condjump_p (BB_END (bb)))
265 continue;
266 if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
267 continue;
268 invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
269 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
270 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
274 /* Find unreachable blocks. An unreachable block will have 0 in
275 the reachable bit in block->flags. A nonzero value indicates the
276 block is reachable. */
278 void
279 find_unreachable_blocks (void)
281 edge e;
282 edge_iterator ei;
283 basic_block *tos, *worklist, bb;
285 tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
287 /* Clear all the reachability flags. */
289 FOR_EACH_BB (bb)
290 bb->flags &= ~BB_REACHABLE;
292 /* Add our starting points to the worklist. Almost always there will
293 be only one. It isn't inconceivable that we might one day directly
294 support Fortran alternate entry points. */
296 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
298 *tos++ = e->dest;
300 /* Mark the block reachable. */
301 e->dest->flags |= BB_REACHABLE;
304 /* Iterate: find everything reachable from what we've already seen. */
306 while (tos != worklist)
308 basic_block b = *--tos;
310 FOR_EACH_EDGE (e, ei, b->succs)
312 basic_block dest = e->dest;
314 if (!(dest->flags & BB_REACHABLE))
316 *tos++ = dest;
317 dest->flags |= BB_REACHABLE;
322 free (worklist);
325 /* Functions to access an edge list with a vector representation.
326 Enough data is kept such that given an index number, the
327 pred and succ that edge represents can be determined, or
328 given a pred and a succ, its index number can be returned.
329 This allows algorithms which consume a lot of memory to
330 represent the normally full matrix of edge (pred,succ) with a
331 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
332 wasted space in the client code due to sparse flow graphs. */
334 /* This functions initializes the edge list. Basically the entire
335 flowgraph is processed, and all edges are assigned a number,
336 and the data structure is filled in. */
338 struct edge_list *
339 create_edge_list (void)
341 struct edge_list *elist;
342 edge e;
343 int num_edges;
344 int block_count;
345 basic_block bb;
346 edge_iterator ei;
348 block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
350 num_edges = 0;
352 /* Determine the number of edges in the flow graph by counting successor
353 edges on each basic block. */
354 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
356 num_edges += EDGE_COUNT (bb->succs);
359 elist = xmalloc (sizeof (struct edge_list));
360 elist->num_blocks = block_count;
361 elist->num_edges = num_edges;
362 elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
364 num_edges = 0;
366 /* Follow successors of blocks, and register these edges. */
367 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
368 FOR_EACH_EDGE (e, ei, bb->succs)
369 elist->index_to_edge[num_edges++] = e;
371 return elist;
374 /* This function free's memory associated with an edge list. */
376 void
377 free_edge_list (struct edge_list *elist)
379 if (elist)
381 free (elist->index_to_edge);
382 free (elist);
386 /* This function provides debug output showing an edge list. */
388 void
389 print_edge_list (FILE *f, struct edge_list *elist)
391 int x;
393 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
394 elist->num_blocks - 2, elist->num_edges);
396 for (x = 0; x < elist->num_edges; x++)
398 fprintf (f, " %-4d - edge(", x);
399 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
400 fprintf (f, "entry,");
401 else
402 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
404 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
405 fprintf (f, "exit)\n");
406 else
407 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
411 /* This function provides an internal consistency check of an edge list,
412 verifying that all edges are present, and that there are no
413 extra edges. */
415 void
416 verify_edge_list (FILE *f, struct edge_list *elist)
418 int pred, succ, index;
419 edge e;
420 basic_block bb, p, s;
421 edge_iterator ei;
423 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
425 FOR_EACH_EDGE (e, ei, bb->succs)
427 pred = e->src->index;
428 succ = e->dest->index;
429 index = EDGE_INDEX (elist, e->src, e->dest);
430 if (index == EDGE_INDEX_NO_EDGE)
432 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
433 continue;
436 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
437 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
438 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
439 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
440 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
441 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
445 /* We've verified that all the edges are in the list, now lets make sure
446 there are no spurious edges in the list. */
448 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
449 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
451 int found_edge = 0;
453 FOR_EACH_EDGE (e, ei, p->succs)
454 if (e->dest == s)
456 found_edge = 1;
457 break;
460 FOR_EACH_EDGE (e, ei, s->preds)
461 if (e->src == p)
463 found_edge = 1;
464 break;
467 if (EDGE_INDEX (elist, p, s)
468 == EDGE_INDEX_NO_EDGE && found_edge != 0)
469 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
470 p->index, s->index);
471 if (EDGE_INDEX (elist, p, s)
472 != EDGE_INDEX_NO_EDGE && found_edge == 0)
473 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
474 p->index, s->index, EDGE_INDEX (elist, p, s));
478 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
479 If no such edge exists, return NULL. */
481 edge
482 find_edge (basic_block pred, basic_block succ)
484 edge e;
485 edge_iterator ei;
487 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
489 FOR_EACH_EDGE (e, ei, pred->succs)
490 if (e->dest == succ)
491 return e;
493 else
495 FOR_EACH_EDGE (e, ei, succ->preds)
496 if (e->src == pred)
497 return e;
500 return NULL;
503 /* This routine will determine what, if any, edge there is between
504 a specified predecessor and successor. */
507 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
509 int x;
511 for (x = 0; x < NUM_EDGES (edge_list); x++)
512 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
513 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
514 return x;
516 return (EDGE_INDEX_NO_EDGE);
519 /* Dump the list of basic blocks in the bitmap NODES. */
521 void
522 flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
524 int node;
526 if (! nodes)
527 return;
529 fprintf (file, "%s { ", str);
530 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
531 fputs ("}\n", file);
534 /* Dump the list of edges in the array EDGE_LIST. */
536 void
537 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
539 int i;
541 if (! edge_list)
542 return;
544 fprintf (file, "%s { ", str);
545 for (i = 0; i < num_edges; i++)
546 fprintf (file, "%d->%d ", edge_list[i]->src->index,
547 edge_list[i]->dest->index);
549 fputs ("}\n", file);
553 /* This routine will remove any fake predecessor edges for a basic block.
554 When the edge is removed, it is also removed from whatever successor
555 list it is in. */
557 static void
558 remove_fake_predecessors (basic_block bb)
560 edge e;
561 edge_iterator ei;
563 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
565 if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
566 remove_edge (e);
567 else
568 ei_next (&ei);
572 /* This routine will remove all fake edges from the flow graph. If
573 we remove all fake successors, it will automatically remove all
574 fake predecessors. */
576 void
577 remove_fake_edges (void)
579 basic_block bb;
581 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
582 remove_fake_predecessors (bb);
585 /* This routine will remove all fake edges to the EXIT_BLOCK. */
587 void
588 remove_fake_exit_edges (void)
590 remove_fake_predecessors (EXIT_BLOCK_PTR);
594 /* This function will add a fake edge between any block which has no
595 successors, and the exit block. Some data flow equations require these
596 edges to exist. */
598 void
599 add_noreturn_fake_exit_edges (void)
601 basic_block bb;
603 FOR_EACH_BB (bb)
604 if (EDGE_COUNT (bb->succs) == 0)
605 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
608 /* This function adds a fake edge between any infinite loops to the
609 exit block. Some optimizations require a path from each node to
610 the exit node.
612 See also Morgan, Figure 3.10, pp. 82-83.
614 The current implementation is ugly, not attempting to minimize the
615 number of inserted fake edges. To reduce the number of fake edges
616 to insert, add fake edges from _innermost_ loops containing only
617 nodes not reachable from the exit block. */
619 void
620 connect_infinite_loops_to_exit (void)
622 basic_block unvisited_block = EXIT_BLOCK_PTR;
623 struct depth_first_search_dsS dfs_ds;
625 /* Perform depth-first search in the reverse graph to find nodes
626 reachable from the exit block. */
627 flow_dfs_compute_reverse_init (&dfs_ds);
628 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
630 /* Repeatedly add fake edges, updating the unreachable nodes. */
631 while (1)
633 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
634 unvisited_block);
635 if (!unvisited_block)
636 break;
638 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
639 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
642 flow_dfs_compute_reverse_finish (&dfs_ds);
643 return;
646 /* Compute reverse top sort order. */
648 void
649 flow_reverse_top_sort_order_compute (int *rts_order)
651 edge_iterator *stack;
652 int sp;
653 int postnum = 0;
654 sbitmap visited;
656 /* Allocate stack for back-tracking up CFG. */
657 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
658 sp = 0;
660 /* Allocate bitmap to track nodes that have been visited. */
661 visited = sbitmap_alloc (last_basic_block);
663 /* None of the nodes in the CFG have been visited yet. */
664 sbitmap_zero (visited);
666 /* Push the first edge on to the stack. */
667 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
669 while (sp)
671 edge_iterator ei;
672 basic_block src;
673 basic_block dest;
675 /* Look at the edge on the top of the stack. */
676 ei = stack[sp - 1];
677 src = ei_edge (ei)->src;
678 dest = ei_edge (ei)->dest;
680 /* Check if the edge destination has been visited yet. */
681 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
683 /* Mark that we have visited the destination. */
684 SET_BIT (visited, dest->index);
686 if (EDGE_COUNT (dest->succs) > 0)
687 /* Since the DEST node has been visited for the first
688 time, check its successors. */
689 stack[sp++] = ei_start (dest->succs);
690 else
691 rts_order[postnum++] = dest->index;
693 else
695 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
696 rts_order[postnum++] = src->index;
698 if (!ei_one_before_end_p (ei))
699 ei_next (&stack[sp - 1]);
700 else
701 sp--;
705 free (stack);
706 sbitmap_free (visited);
709 /* Compute the depth first search order and store in the array
710 DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
711 RC_ORDER is nonzero, return the reverse completion number for each
712 node. Returns the number of nodes visited. A depth first search
713 tries to get as far away from the starting point as quickly as
714 possible. */
717 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
719 edge_iterator *stack;
720 int sp;
721 int dfsnum = 0;
722 int rcnum = n_basic_blocks - 1;
723 sbitmap visited;
725 /* Allocate stack for back-tracking up CFG. */
726 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
727 sp = 0;
729 /* Allocate bitmap to track nodes that have been visited. */
730 visited = sbitmap_alloc (last_basic_block);
732 /* None of the nodes in the CFG have been visited yet. */
733 sbitmap_zero (visited);
735 /* Push the first edge on to the stack. */
736 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
738 while (sp)
740 edge_iterator ei;
741 basic_block src;
742 basic_block dest;
744 /* Look at the edge on the top of the stack. */
745 ei = stack[sp - 1];
746 src = ei_edge (ei)->src;
747 dest = ei_edge (ei)->dest;
749 /* Check if the edge destination has been visited yet. */
750 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
752 /* Mark that we have visited the destination. */
753 SET_BIT (visited, dest->index);
755 if (dfs_order)
756 dfs_order[dfsnum] = dest->index;
758 dfsnum++;
760 if (EDGE_COUNT (dest->succs) > 0)
761 /* Since the DEST node has been visited for the first
762 time, check its successors. */
763 stack[sp++] = ei_start (dest->succs);
764 else if (rc_order)
765 /* There are no successors for the DEST node so assign
766 its reverse completion number. */
767 rc_order[rcnum--] = dest->index;
769 else
771 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
772 && rc_order)
773 /* There are no more successors for the SRC node
774 so assign its reverse completion number. */
775 rc_order[rcnum--] = src->index;
777 if (!ei_one_before_end_p (ei))
778 ei_next (&stack[sp - 1]);
779 else
780 sp--;
784 free (stack);
785 sbitmap_free (visited);
787 /* The number of nodes visited should be the number of blocks. */
788 gcc_assert (dfsnum == n_basic_blocks);
790 return dfsnum;
793 /* Compute the depth first search order on the _reverse_ graph and
794 store in the array DFS_ORDER, marking the nodes visited in VISITED.
795 Returns the number of nodes visited.
797 The computation is split into three pieces:
799 flow_dfs_compute_reverse_init () creates the necessary data
800 structures.
802 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
803 structures. The block will start the search.
805 flow_dfs_compute_reverse_execute () continues (or starts) the
806 search using the block on the top of the stack, stopping when the
807 stack is empty.
809 flow_dfs_compute_reverse_finish () destroys the necessary data
810 structures.
812 Thus, the user will probably call ..._init(), call ..._add_bb() to
813 add a beginning basic block to the stack, call ..._execute(),
814 possibly add another bb to the stack and again call ..._execute(),
815 ..., and finally call _finish(). */
817 /* Initialize the data structures used for depth-first search on the
818 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
819 added to the basic block stack. DATA is the current depth-first
820 search context. If INITIALIZE_STACK is nonzero, there is an
821 element on the stack. */
823 static void
824 flow_dfs_compute_reverse_init (depth_first_search_ds data)
826 /* Allocate stack for back-tracking up CFG. */
827 data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
828 * sizeof (basic_block));
829 data->sp = 0;
831 /* Allocate bitmap to track nodes that have been visited. */
832 data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
834 /* None of the nodes in the CFG have been visited yet. */
835 sbitmap_zero (data->visited_blocks);
837 return;
840 /* Add the specified basic block to the top of the dfs data
841 structures. When the search continues, it will start at the
842 block. */
844 static void
845 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
847 data->stack[data->sp++] = bb;
848 SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
851 /* Continue the depth-first search through the reverse graph starting with the
852 block at the stack's top and ending when the stack is empty. Visited nodes
853 are marked. Returns an unvisited basic block, or NULL if there is none
854 available. */
856 static basic_block
857 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
858 basic_block last_unvisited)
860 basic_block bb;
861 edge e;
862 edge_iterator ei;
864 while (data->sp > 0)
866 bb = data->stack[--data->sp];
868 /* Perform depth-first search on adjacent vertices. */
869 FOR_EACH_EDGE (e, ei, bb->preds)
870 if (!TEST_BIT (data->visited_blocks,
871 e->src->index - (INVALID_BLOCK + 1)))
872 flow_dfs_compute_reverse_add_bb (data, e->src);
875 /* Determine if there are unvisited basic blocks. */
876 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
877 if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
878 return bb;
880 return NULL;
883 /* Destroy the data structures needed for depth-first search on the
884 reverse graph. */
886 static void
887 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
889 free (data->stack);
890 sbitmap_free (data->visited_blocks);
893 /* Performs dfs search from BB over vertices satisfying PREDICATE;
894 if REVERSE, go against direction of edges. Returns number of blocks
895 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
897 dfs_enumerate_from (basic_block bb, int reverse,
898 bool (*predicate) (basic_block, void *),
899 basic_block *rslt, int rslt_max, void *data)
901 basic_block *st, lbb;
902 int sp = 0, tv = 0;
904 st = xcalloc (rslt_max, sizeof (basic_block));
905 rslt[tv++] = st[sp++] = bb;
906 bb->flags |= BB_VISITED;
907 while (sp)
909 edge e;
910 edge_iterator ei;
911 lbb = st[--sp];
912 if (reverse)
914 FOR_EACH_EDGE (e, ei, lbb->preds)
915 if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
917 gcc_assert (tv != rslt_max);
918 rslt[tv++] = st[sp++] = e->src;
919 e->src->flags |= BB_VISITED;
922 else
924 FOR_EACH_EDGE (e, ei, lbb->succs)
925 if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
927 gcc_assert (tv != rslt_max);
928 rslt[tv++] = st[sp++] = e->dest;
929 e->dest->flags |= BB_VISITED;
933 free (st);
934 for (sp = 0; sp < tv; sp++)
935 rslt[sp]->flags &= ~BB_VISITED;
936 return tv;
940 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
942 This algorithm can be found in Timothy Harvey's PhD thesis, at
943 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
944 dominance algorithms.
946 First, we identify each join point, j (any node with more than one
947 incoming edge is a join point).
949 We then examine each predecessor, p, of j and walk up the dominator tree
950 starting at p.
952 We stop the walk when we reach j's immediate dominator - j is in the
953 dominance frontier of each of the nodes in the walk, except for j's
954 immediate dominator. Intuitively, all of the rest of j's dominators are
955 shared by j's predecessors as well.
956 Since they dominate j, they will not have j in their dominance frontiers.
958 The number of nodes touched by this algorithm is equal to the size
959 of the dominance frontiers, no more, no less.
963 static void
964 compute_dominance_frontiers_1 (bitmap *frontiers)
966 edge p;
967 edge_iterator ei;
968 basic_block b;
969 FOR_EACH_BB (b)
971 if (EDGE_COUNT (b->preds) >= 2)
973 FOR_EACH_EDGE (p, ei, b->preds)
975 basic_block runner = p->src;
976 basic_block domsb;
977 if (runner == ENTRY_BLOCK_PTR)
978 continue;
980 domsb = get_immediate_dominator (CDI_DOMINATORS, b);
981 while (runner != domsb)
983 bitmap_set_bit (frontiers[runner->index],
984 b->index);
985 runner = get_immediate_dominator (CDI_DOMINATORS,
986 runner);
994 void
995 compute_dominance_frontiers (bitmap *frontiers)
997 timevar_push (TV_DOM_FRONTIERS);
999 compute_dominance_frontiers_1 (frontiers);
1001 timevar_pop (TV_DOM_FRONTIERS);