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 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
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
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
22 /* This file contains various simple utilities to analyze the CFG. */
25 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
36 /* Store the data structures necessary for depth-first search. */
37 struct depth_first_search_dsS {
38 /* stack for backtracking during the algorithm */
41 /* number of edges in the stack. That is, positions 0, ..., sp-1
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,
53 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
55 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
56 static bool flow_active_insn_p (rtx);
58 /* Like active_insn_p, except keep the return value clobber around
62 flow_active_insn_p (rtx insn)
64 if (active_insn_p (insn))
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 livetime aborts. */
72 if (GET_CODE (PATTERN (insn)) == CLOBBER
73 && REG_P (XEXP (PATTERN (insn), 0))
74 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
80 /* Return true if the block has no effect and only forwards control flow to
81 its single destination. */
84 forwarder_block_p (basic_block bb)
88 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
89 || EDGE_COUNT (bb->succs) != 1)
92 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
93 if (INSN_P (insn) && flow_active_insn_p (insn))
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. */
104 can_fallthru (basic_block src, basic_block target)
106 rtx insn = BB_END (src);
111 if (target == EXIT_BLOCK_PTR)
113 if (src->next_bb != target)
115 FOR_EACH_EDGE (e, ei, src->succs)
116 if (e->dest == EXIT_BLOCK_PTR
117 && e->flags & EDGE_FALLTHRU)
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. */
132 could_fall_through (basic_block src, basic_block target)
137 if (target == EXIT_BLOCK_PTR)
139 FOR_EACH_EDGE (e, ei, src->succs)
140 if (e->dest == EXIT_BLOCK_PTR
141 && e->flags & EDGE_FALLTHRU)
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
152 Morgan Kaufmann, 1997
154 and heavily borrowed from flow_depth_first_order_compute. */
157 mark_dfs_back_edges (void)
159 edge_iterator *stack;
168 /* Allocate the preorder and postorder number arrays. */
169 pre = xcalloc (last_basic_block, sizeof (int));
170 post = xcalloc (last_basic_block, sizeof (int));
172 /* Allocate stack for back-tracking up CFG. */
173 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
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);
191 /* Look at the edge on the top of the stack. */
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);
211 post[dest->index] = postnum++;
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]);
233 sbitmap_free (visited);
238 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
241 set_edge_can_fallthru_flag (void)
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)
263 if (!any_condjump_p (BB_END (bb)))
265 if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
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. */
278 find_unreachable_blocks (void)
282 basic_block *tos, *worklist, bb;
284 tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
286 /* Clear all the reachability flags. */
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)
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)
310 if (!(e->dest->flags & BB_REACHABLE))
313 e->dest->flags |= BB_REACHABLE;
320 /* Functions to access an edge list with a vector representation.
321 Enough data is kept such that given an index number, the
322 pred and succ that edge represents can be determined, or
323 given a pred and a succ, its index number can be returned.
324 This allows algorithms which consume a lot of memory to
325 represent the normally full matrix of edge (pred,succ) with a
326 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
327 wasted space in the client code due to sparse flow graphs. */
329 /* This functions initializes the edge list. Basically the entire
330 flowgraph is processed, and all edges are assigned a number,
331 and the data structure is filled in. */
334 create_edge_list (void)
336 struct edge_list *elist;
343 block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
347 /* Determine the number of edges in the flow graph by counting successor
348 edges on each basic block. */
349 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
351 num_edges += EDGE_COUNT (bb->succs);
354 elist = xmalloc (sizeof (struct edge_list));
355 elist->num_blocks = block_count;
356 elist->num_edges = num_edges;
357 elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
361 /* Follow successors of blocks, and register these edges. */
362 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
363 FOR_EACH_EDGE (e, ei, bb->succs)
364 elist->index_to_edge[num_edges++] = e;
369 /* This function free's memory associated with an edge list. */
372 free_edge_list (struct edge_list *elist)
376 free (elist->index_to_edge);
381 /* This function provides debug output showing an edge list. */
384 print_edge_list (FILE *f, struct edge_list *elist)
388 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
389 elist->num_blocks - 2, elist->num_edges);
391 for (x = 0; x < elist->num_edges; x++)
393 fprintf (f, " %-4d - edge(", x);
394 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
395 fprintf (f, "entry,");
397 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
399 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
400 fprintf (f, "exit)\n");
402 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
406 /* This function provides an internal consistency check of an edge list,
407 verifying that all edges are present, and that there are no
411 verify_edge_list (FILE *f, struct edge_list *elist)
413 int pred, succ, index;
415 basic_block bb, p, s;
418 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
420 FOR_EACH_EDGE (e, ei, bb->succs)
422 pred = e->src->index;
423 succ = e->dest->index;
424 index = EDGE_INDEX (elist, e->src, e->dest);
425 if (index == EDGE_INDEX_NO_EDGE)
427 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
431 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
432 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
433 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
434 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
435 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
436 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
440 /* We've verified that all the edges are in the list, now lets make sure
441 there are no spurious edges in the list. */
443 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
444 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
448 FOR_EACH_EDGE (e, ei, p->succs)
455 FOR_EACH_EDGE (e, ei, s->preds)
462 if (EDGE_INDEX (elist, p, s)
463 == EDGE_INDEX_NO_EDGE && found_edge != 0)
464 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
466 if (EDGE_INDEX (elist, p, s)
467 != EDGE_INDEX_NO_EDGE && found_edge == 0)
468 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
469 p->index, s->index, EDGE_INDEX (elist, p, s));
473 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
474 If no such edge exists, return NULL. */
477 find_edge (basic_block pred, basic_block succ)
482 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
484 FOR_EACH_EDGE (e, ei, pred->succs)
490 FOR_EACH_EDGE (e, ei, succ->preds)
498 /* This routine will determine what, if any, edge there is between
499 a specified predecessor and successor. */
502 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
506 for (x = 0; x < NUM_EDGES (edge_list); x++)
507 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
508 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
511 return (EDGE_INDEX_NO_EDGE);
514 /* Dump the list of basic blocks in the bitmap NODES. */
517 flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
524 fprintf (file, "%s { ", str);
525 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
529 /* Dump the list of edges in the array EDGE_LIST. */
532 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
539 fprintf (file, "%s { ", str);
540 for (i = 0; i < num_edges; i++)
541 fprintf (file, "%d->%d ", edge_list[i]->src->index,
542 edge_list[i]->dest->index);
548 /* This routine will remove any fake predecessor edges for a basic block.
549 When the edge is removed, it is also removed from whatever successor
553 remove_fake_predecessors (basic_block bb)
558 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
560 if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
567 /* This routine will remove all fake edges from the flow graph. If
568 we remove all fake successors, it will automatically remove all
569 fake predecessors. */
572 remove_fake_edges (void)
576 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
577 remove_fake_predecessors (bb);
580 /* This routine will remove all fake edges to the EXIT_BLOCK. */
583 remove_fake_exit_edges (void)
585 remove_fake_predecessors (EXIT_BLOCK_PTR);
589 /* This function will add a fake edge between any block which has no
590 successors, and the exit block. Some data flow equations require these
594 add_noreturn_fake_exit_edges (void)
599 if (EDGE_COUNT (bb->succs) == 0)
600 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
603 /* This function adds a fake edge between any infinite loops to the
604 exit block. Some optimizations require a path from each node to
607 See also Morgan, Figure 3.10, pp. 82-83.
609 The current implementation is ugly, not attempting to minimize the
610 number of inserted fake edges. To reduce the number of fake edges
611 to insert, add fake edges from _innermost_ loops containing only
612 nodes not reachable from the exit block. */
615 connect_infinite_loops_to_exit (void)
617 basic_block unvisited_block = EXIT_BLOCK_PTR;
618 struct depth_first_search_dsS dfs_ds;
620 /* Perform depth-first search in the reverse graph to find nodes
621 reachable from the exit block. */
622 flow_dfs_compute_reverse_init (&dfs_ds);
623 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
625 /* Repeatedly add fake edges, updating the unreachable nodes. */
628 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
630 if (!unvisited_block)
633 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
634 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
637 flow_dfs_compute_reverse_finish (&dfs_ds);
641 /* Compute reverse top sort order. */
644 flow_reverse_top_sort_order_compute (int *rts_order)
646 edge_iterator *stack;
651 /* Allocate stack for back-tracking up CFG. */
652 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
655 /* Allocate bitmap to track nodes that have been visited. */
656 visited = sbitmap_alloc (last_basic_block);
658 /* None of the nodes in the CFG have been visited yet. */
659 sbitmap_zero (visited);
661 /* Push the first edge on to the stack. */
662 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
670 /* Look at the edge on the top of the stack. */
672 src = ei_edge (ei)->src;
673 dest = ei_edge (ei)->dest;
675 /* Check if the edge destination has been visited yet. */
676 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
678 /* Mark that we have visited the destination. */
679 SET_BIT (visited, dest->index);
681 if (EDGE_COUNT (dest->succs) > 0)
682 /* Since the DEST node has been visited for the first
683 time, check its successors. */
684 stack[sp++] = ei_start (dest->succs);
686 rts_order[postnum++] = dest->index;
690 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
691 rts_order[postnum++] = src->index;
693 if (!ei_one_before_end_p (ei))
694 ei_next (&stack[sp - 1]);
701 sbitmap_free (visited);
704 /* Compute the depth first search order and store in the array
705 DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
706 RC_ORDER is nonzero, return the reverse completion number for each
707 node. Returns the number of nodes visited. A depth first search
708 tries to get as far away from the starting point as quickly as
712 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
714 edge_iterator *stack;
717 int rcnum = n_basic_blocks - 1;
720 /* Allocate stack for back-tracking up CFG. */
721 stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
724 /* Allocate bitmap to track nodes that have been visited. */
725 visited = sbitmap_alloc (last_basic_block);
727 /* None of the nodes in the CFG have been visited yet. */
728 sbitmap_zero (visited);
730 /* Push the first edge on to the stack. */
731 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
739 /* Look at the edge on the top of the stack. */
741 src = ei_edge (ei)->src;
742 dest = ei_edge (ei)->dest;
744 /* Check if the edge destination has been visited yet. */
745 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
747 /* Mark that we have visited the destination. */
748 SET_BIT (visited, dest->index);
751 dfs_order[dfsnum] = dest->index;
755 if (EDGE_COUNT (dest->succs) > 0)
756 /* Since the DEST node has been visited for the first
757 time, check its successors. */
758 stack[sp++] = ei_start (dest->succs);
760 /* There are no successors for the DEST node so assign
761 its reverse completion number. */
762 rc_order[rcnum--] = dest->index;
766 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
768 /* There are no more successors for the SRC node
769 so assign its reverse completion number. */
770 rc_order[rcnum--] = src->index;
772 if (!ei_one_before_end_p (ei))
773 ei_next (&stack[sp - 1]);
780 sbitmap_free (visited);
782 /* The number of nodes visited should be the number of blocks. */
783 gcc_assert (dfsnum == n_basic_blocks);
788 /* Compute the depth first search order on the _reverse_ graph and
789 store in the array DFS_ORDER, marking the nodes visited in VISITED.
790 Returns the number of nodes visited.
792 The computation is split into three pieces:
794 flow_dfs_compute_reverse_init () creates the necessary data
797 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
798 structures. The block will start the search.
800 flow_dfs_compute_reverse_execute () continues (or starts) the
801 search using the block on the top of the stack, stopping when the
804 flow_dfs_compute_reverse_finish () destroys the necessary data
807 Thus, the user will probably call ..._init(), call ..._add_bb() to
808 add a beginning basic block to the stack, call ..._execute(),
809 possibly add another bb to the stack and again call ..._execute(),
810 ..., and finally call _finish(). */
812 /* Initialize the data structures used for depth-first search on the
813 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
814 added to the basic block stack. DATA is the current depth-first
815 search context. If INITIALIZE_STACK is nonzero, there is an
816 element on the stack. */
819 flow_dfs_compute_reverse_init (depth_first_search_ds data)
821 /* Allocate stack for back-tracking up CFG. */
822 data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
823 * sizeof (basic_block));
826 /* Allocate bitmap to track nodes that have been visited. */
827 data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
829 /* None of the nodes in the CFG have been visited yet. */
830 sbitmap_zero (data->visited_blocks);
835 /* Add the specified basic block to the top of the dfs data
836 structures. When the search continues, it will start at the
840 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
842 data->stack[data->sp++] = bb;
843 SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
846 /* Continue the depth-first search through the reverse graph starting with the
847 block at the stack's top and ending when the stack is empty. Visited nodes
848 are marked. Returns an unvisited basic block, or NULL if there is none
852 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
853 basic_block last_unvisited)
861 bb = data->stack[--data->sp];
863 /* Perform depth-first search on adjacent vertices. */
864 FOR_EACH_EDGE (e, ei, bb->preds)
865 if (!TEST_BIT (data->visited_blocks,
866 e->src->index - (INVALID_BLOCK + 1)))
867 flow_dfs_compute_reverse_add_bb (data, e->src);
870 /* Determine if there are unvisited basic blocks. */
871 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
872 if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
878 /* Destroy the data structures needed for depth-first search on the
882 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
885 sbitmap_free (data->visited_blocks);
888 /* Performs dfs search from BB over vertices satisfying PREDICATE;
889 if REVERSE, go against direction of edges. Returns number of blocks
890 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
892 dfs_enumerate_from (basic_block bb, int reverse,
893 bool (*predicate) (basic_block, void *),
894 basic_block *rslt, int rslt_max, void *data)
896 basic_block *st, lbb;
899 st = xcalloc (rslt_max, sizeof (basic_block));
900 rslt[tv++] = st[sp++] = bb;
901 bb->flags |= BB_VISITED;
909 FOR_EACH_EDGE (e, ei, lbb->preds)
910 if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
912 gcc_assert (tv != rslt_max);
913 rslt[tv++] = st[sp++] = e->src;
914 e->src->flags |= BB_VISITED;
919 FOR_EACH_EDGE (e, ei, lbb->succs)
920 if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
922 gcc_assert (tv != rslt_max);
923 rslt[tv++] = st[sp++] = e->dest;
924 e->dest->flags |= BB_VISITED;
929 for (sp = 0; sp < tv; sp++)
930 rslt[sp]->flags &= ~BB_VISITED;
935 /* Computing the Dominance Frontier:
937 As described in Morgan, section 3.5, this may be done simply by
938 walking the dominator tree bottom-up, computing the frontier for
939 the children before the parent. When considering a block B,
942 (1) A flow graph edge leaving B that does not lead to a child
943 of B in the dominator tree must be a block that is either equal
944 to B or not dominated by B. Such blocks belong in the frontier
947 (2) Consider a block X in the frontier of one of the children C
948 of B. If X is not equal to B and is not dominated by B, it
949 is in the frontier of B. */
952 compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
958 SET_BIT (done, bb->index);
960 /* Do the frontier of the children first. Not all children in the
961 dominator tree (blocks dominated by this one) are children in the
962 CFG, so check all blocks. */
963 for (c = first_dom_son (CDI_DOMINATORS, bb);
965 c = next_dom_son (CDI_DOMINATORS, c))
967 if (! TEST_BIT (done, c->index))
968 compute_dominance_frontiers_1 (frontiers, c, done);
971 /* Find blocks conforming to rule (1) above. */
972 FOR_EACH_EDGE (e, ei, bb->succs)
974 if (e->dest == EXIT_BLOCK_PTR)
976 if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
977 bitmap_set_bit (frontiers[bb->index], e->dest->index);
980 /* Find blocks conforming to rule (2). */
981 for (c = first_dom_son (CDI_DOMINATORS, bb);
983 c = next_dom_son (CDI_DOMINATORS, c))
988 EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
990 if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
991 bitmap_set_bit (frontiers[bb->index], x);
998 compute_dominance_frontiers (bitmap *frontiers)
1000 sbitmap done = sbitmap_alloc (last_basic_block);
1002 timevar_push (TV_DOM_FRONTIERS);
1004 sbitmap_zero (done);
1006 compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done);
1008 sbitmap_free (done);
1010 timevar_pop (TV_DOM_FRONTIERS);