gcc:
[official-gcc.git] / gcc / cfganal.c
blob3ed1c5921865375227c734c72c41bd2e88381c12
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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, 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 lifetime confusion. */
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 unsigned int node = 0;
525 sbitmap_iterator sbi;
527 if (! nodes)
528 return;
530 fprintf (file, "%s { ", str);
531 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
532 fprintf (file, "%d ", node);
533 fputs ("}\n", file);
536 /* Dump the list of edges in the array EDGE_LIST. */
538 void
539 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
541 int i;
543 if (! edge_list)
544 return;
546 fprintf (file, "%s { ", str);
547 for (i = 0; i < num_edges; i++)
548 fprintf (file, "%d->%d ", edge_list[i]->src->index,
549 edge_list[i]->dest->index);
551 fputs ("}\n", file);
555 /* This routine will remove any fake predecessor edges for a basic block.
556 When the edge is removed, it is also removed from whatever successor
557 list it is in. */
559 static void
560 remove_fake_predecessors (basic_block bb)
562 edge e;
563 edge_iterator ei;
565 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
567 if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
568 remove_edge (e);
569 else
570 ei_next (&ei);
574 /* This routine will remove all fake edges from the flow graph. If
575 we remove all fake successors, it will automatically remove all
576 fake predecessors. */
578 void
579 remove_fake_edges (void)
581 basic_block bb;
583 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
584 remove_fake_predecessors (bb);
587 /* This routine will remove all fake edges to the EXIT_BLOCK. */
589 void
590 remove_fake_exit_edges (void)
592 remove_fake_predecessors (EXIT_BLOCK_PTR);
596 /* This function will add a fake edge between any block which has no
597 successors, and the exit block. Some data flow equations require these
598 edges to exist. */
600 void
601 add_noreturn_fake_exit_edges (void)
603 basic_block bb;
605 FOR_EACH_BB (bb)
606 if (EDGE_COUNT (bb->succs) == 0)
607 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
610 /* This function adds a fake edge between any infinite loops to the
611 exit block. Some optimizations require a path from each node to
612 the exit node.
614 See also Morgan, Figure 3.10, pp. 82-83.
616 The current implementation is ugly, not attempting to minimize the
617 number of inserted fake edges. To reduce the number of fake edges
618 to insert, add fake edges from _innermost_ loops containing only
619 nodes not reachable from the exit block. */
621 void
622 connect_infinite_loops_to_exit (void)
624 basic_block unvisited_block = EXIT_BLOCK_PTR;
625 struct depth_first_search_dsS dfs_ds;
627 /* Perform depth-first search in the reverse graph to find nodes
628 reachable from the exit block. */
629 flow_dfs_compute_reverse_init (&dfs_ds);
630 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
632 /* Repeatedly add fake edges, updating the unreachable nodes. */
633 while (1)
635 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
636 unvisited_block);
637 if (!unvisited_block)
638 break;
640 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
641 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
644 flow_dfs_compute_reverse_finish (&dfs_ds);
645 return;
648 /* Compute reverse top sort order. */
650 void
651 flow_reverse_top_sort_order_compute (int *rts_order)
653 edge_iterator *stack;
654 int sp;
655 int postnum = 0;
656 sbitmap visited;
658 /* Allocate stack for back-tracking up CFG. */
659 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
660 sp = 0;
662 /* Allocate bitmap to track nodes that have been visited. */
663 visited = sbitmap_alloc (last_basic_block);
665 /* None of the nodes in the CFG have been visited yet. */
666 sbitmap_zero (visited);
668 /* Push the first edge on to the stack. */
669 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
671 while (sp)
673 edge_iterator ei;
674 basic_block src;
675 basic_block dest;
677 /* Look at the edge on the top of the stack. */
678 ei = stack[sp - 1];
679 src = ei_edge (ei)->src;
680 dest = ei_edge (ei)->dest;
682 /* Check if the edge destination has been visited yet. */
683 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
685 /* Mark that we have visited the destination. */
686 SET_BIT (visited, dest->index);
688 if (EDGE_COUNT (dest->succs) > 0)
689 /* Since the DEST node has been visited for the first
690 time, check its successors. */
691 stack[sp++] = ei_start (dest->succs);
692 else
693 rts_order[postnum++] = dest->index;
695 else
697 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
698 rts_order[postnum++] = src->index;
700 if (!ei_one_before_end_p (ei))
701 ei_next (&stack[sp - 1]);
702 else
703 sp--;
707 free (stack);
708 sbitmap_free (visited);
711 /* Compute the depth first search order and store in the array
712 DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
713 RC_ORDER is nonzero, return the reverse completion number for each
714 node. Returns the number of nodes visited. A depth first search
715 tries to get as far away from the starting point as quickly as
716 possible. */
719 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
721 edge_iterator *stack;
722 int sp;
723 int dfsnum = 0;
724 int rcnum = n_basic_blocks - 1;
725 sbitmap visited;
727 /* Allocate stack for back-tracking up CFG. */
728 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
729 sp = 0;
731 /* Allocate bitmap to track nodes that have been visited. */
732 visited = sbitmap_alloc (last_basic_block);
734 /* None of the nodes in the CFG have been visited yet. */
735 sbitmap_zero (visited);
737 /* Push the first edge on to the stack. */
738 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
740 while (sp)
742 edge_iterator ei;
743 basic_block src;
744 basic_block dest;
746 /* Look at the edge on the top of the stack. */
747 ei = stack[sp - 1];
748 src = ei_edge (ei)->src;
749 dest = ei_edge (ei)->dest;
751 /* Check if the edge destination has been visited yet. */
752 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
754 /* Mark that we have visited the destination. */
755 SET_BIT (visited, dest->index);
757 if (dfs_order)
758 dfs_order[dfsnum] = dest->index;
760 dfsnum++;
762 if (EDGE_COUNT (dest->succs) > 0)
763 /* Since the DEST node has been visited for the first
764 time, check its successors. */
765 stack[sp++] = ei_start (dest->succs);
766 else if (rc_order)
767 /* There are no successors for the DEST node so assign
768 its reverse completion number. */
769 rc_order[rcnum--] = dest->index;
771 else
773 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
774 && rc_order)
775 /* There are no more successors for the SRC node
776 so assign its reverse completion number. */
777 rc_order[rcnum--] = src->index;
779 if (!ei_one_before_end_p (ei))
780 ei_next (&stack[sp - 1]);
781 else
782 sp--;
786 free (stack);
787 sbitmap_free (visited);
789 /* The number of nodes visited should be the number of blocks. */
790 gcc_assert (dfsnum == n_basic_blocks);
792 return dfsnum;
795 /* Compute the depth first search order on the _reverse_ graph and
796 store in the array DFS_ORDER, marking the nodes visited in VISITED.
797 Returns the number of nodes visited.
799 The computation is split into three pieces:
801 flow_dfs_compute_reverse_init () creates the necessary data
802 structures.
804 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
805 structures. The block will start the search.
807 flow_dfs_compute_reverse_execute () continues (or starts) the
808 search using the block on the top of the stack, stopping when the
809 stack is empty.
811 flow_dfs_compute_reverse_finish () destroys the necessary data
812 structures.
814 Thus, the user will probably call ..._init(), call ..._add_bb() to
815 add a beginning basic block to the stack, call ..._execute(),
816 possibly add another bb to the stack and again call ..._execute(),
817 ..., and finally call _finish(). */
819 /* Initialize the data structures used for depth-first search on the
820 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
821 added to the basic block stack. DATA is the current depth-first
822 search context. If INITIALIZE_STACK is nonzero, there is an
823 element on the stack. */
825 static void
826 flow_dfs_compute_reverse_init (depth_first_search_ds data)
828 /* Allocate stack for back-tracking up CFG. */
829 data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
830 * sizeof (basic_block));
831 data->sp = 0;
833 /* Allocate bitmap to track nodes that have been visited. */
834 data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
836 /* None of the nodes in the CFG have been visited yet. */
837 sbitmap_zero (data->visited_blocks);
839 return;
842 /* Add the specified basic block to the top of the dfs data
843 structures. When the search continues, it will start at the
844 block. */
846 static void
847 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
849 data->stack[data->sp++] = bb;
850 SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
853 /* Continue the depth-first search through the reverse graph starting with the
854 block at the stack's top and ending when the stack is empty. Visited nodes
855 are marked. Returns an unvisited basic block, or NULL if there is none
856 available. */
858 static basic_block
859 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
860 basic_block last_unvisited)
862 basic_block bb;
863 edge e;
864 edge_iterator ei;
866 while (data->sp > 0)
868 bb = data->stack[--data->sp];
870 /* Perform depth-first search on adjacent vertices. */
871 FOR_EACH_EDGE (e, ei, bb->preds)
872 if (!TEST_BIT (data->visited_blocks,
873 e->src->index - (INVALID_BLOCK + 1)))
874 flow_dfs_compute_reverse_add_bb (data, e->src);
877 /* Determine if there are unvisited basic blocks. */
878 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
879 if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
880 return bb;
882 return NULL;
885 /* Destroy the data structures needed for depth-first search on the
886 reverse graph. */
888 static void
889 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
891 free (data->stack);
892 sbitmap_free (data->visited_blocks);
895 /* Performs dfs search from BB over vertices satisfying PREDICATE;
896 if REVERSE, go against direction of edges. Returns number of blocks
897 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
899 dfs_enumerate_from (basic_block bb, int reverse,
900 bool (*predicate) (basic_block, void *),
901 basic_block *rslt, int rslt_max, void *data)
903 basic_block *st, lbb;
904 int sp = 0, tv = 0;
905 unsigned size;
907 /* A bitmap to keep track of visited blocks. Allocating it each time
908 this function is called is not possible, since dfs_enumerate_from
909 is often used on small (almost) disjoint parts of cfg (bodies of
910 loops), and allocating a large sbitmap would lead to quadratic
911 behavior. */
912 static sbitmap visited;
913 static unsigned v_size;
915 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
916 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index + 2))
917 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
919 /* Resize the VISITED sbitmap if necessary. */
920 size = last_basic_block + 2;
921 if (size < 10)
922 size = 10;
924 if (!visited)
927 visited = sbitmap_alloc (size);
928 sbitmap_zero (visited);
929 v_size = size;
931 else if (v_size < size)
933 /* Ensure that we increase the size of the sbitmap exponentially. */
934 if (2 * v_size > size)
935 size = 2 * v_size;
937 visited = sbitmap_resize (visited, size, 0);
938 v_size = size;
941 st = xcalloc (rslt_max, sizeof (basic_block));
942 rslt[tv++] = st[sp++] = bb;
943 MARK_VISITED (bb);
944 while (sp)
946 edge e;
947 edge_iterator ei;
948 lbb = st[--sp];
949 if (reverse)
951 FOR_EACH_EDGE (e, ei, lbb->preds)
952 if (!VISITED_P (e->src) && predicate (e->src, data))
954 gcc_assert (tv != rslt_max);
955 rslt[tv++] = st[sp++] = e->src;
956 MARK_VISITED (e->src);
959 else
961 FOR_EACH_EDGE (e, ei, lbb->succs)
962 if (!VISITED_P (e->dest) && predicate (e->dest, data))
964 gcc_assert (tv != rslt_max);
965 rslt[tv++] = st[sp++] = e->dest;
966 MARK_VISITED (e->dest);
970 free (st);
971 for (sp = 0; sp < tv; sp++)
972 UNMARK_VISITED (rslt[sp]);
973 return tv;
974 #undef MARK_VISITED
975 #undef UNMARK_VISITED
976 #undef VISITED_P
980 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
982 This algorithm can be found in Timothy Harvey's PhD thesis, at
983 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
984 dominance algorithms.
986 First, we identify each join point, j (any node with more than one
987 incoming edge is a join point).
989 We then examine each predecessor, p, of j and walk up the dominator tree
990 starting at p.
992 We stop the walk when we reach j's immediate dominator - j is in the
993 dominance frontier of each of the nodes in the walk, except for j's
994 immediate dominator. Intuitively, all of the rest of j's dominators are
995 shared by j's predecessors as well.
996 Since they dominate j, they will not have j in their dominance frontiers.
998 The number of nodes touched by this algorithm is equal to the size
999 of the dominance frontiers, no more, no less.
1003 static void
1004 compute_dominance_frontiers_1 (bitmap *frontiers)
1006 edge p;
1007 edge_iterator ei;
1008 basic_block b;
1009 FOR_EACH_BB (b)
1011 if (EDGE_COUNT (b->preds) >= 2)
1013 FOR_EACH_EDGE (p, ei, b->preds)
1015 basic_block runner = p->src;
1016 basic_block domsb;
1017 if (runner == ENTRY_BLOCK_PTR)
1018 continue;
1020 domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1021 while (runner != domsb)
1023 bitmap_set_bit (frontiers[runner->index],
1024 b->index);
1025 runner = get_immediate_dominator (CDI_DOMINATORS,
1026 runner);
1034 void
1035 compute_dominance_frontiers (bitmap *frontiers)
1037 timevar_push (TV_DOM_FRONTIERS);
1039 compute_dominance_frontiers_1 (frontiers);
1041 timevar_pop (TV_DOM_FRONTIERS);