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
);
54 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
);
55 static bool flow_active_insn_p (rtx
);
57 /* Like active_insn_p, except keep the return value clobber around
61 flow_active_insn_p (rtx insn
)
63 if (active_insn_p (insn
))
66 /* A clobber of the function return value exists for buggy
67 programs that fail to return a value. Its effect is to
68 keep the return value from being live across the entire
69 function. If we allow it to be skipped, we introduce the
70 possibility for register livetime aborts. */
71 if (GET_CODE (PATTERN (insn
)) == CLOBBER
72 && REG_P (XEXP (PATTERN (insn
), 0))
73 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
79 /* Return true if the block has no effect and only forwards control flow to
80 its single destination. */
83 forwarder_block_p (basic_block bb
)
87 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
88 || EDGE_COUNT (bb
->succs
) != 1)
91 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
92 if (INSN_P (insn
) && flow_active_insn_p (insn
))
95 return (!INSN_P (insn
)
96 || (JUMP_P (insn
) && simplejump_p (insn
))
97 || !flow_active_insn_p (insn
));
100 /* Return nonzero if we can reach target from src by falling through. */
103 can_fallthru (basic_block src
, basic_block target
)
105 rtx insn
= BB_END (src
);
110 if (target
== EXIT_BLOCK_PTR
)
112 if (src
->next_bb
!= target
)
114 FOR_EACH_EDGE (e
, ei
, src
->succs
)
115 if (e
->dest
== EXIT_BLOCK_PTR
116 && e
->flags
& EDGE_FALLTHRU
)
119 insn2
= BB_HEAD (target
);
120 if (insn2
&& !active_insn_p (insn2
))
121 insn2
= next_active_insn (insn2
);
123 /* ??? Later we may add code to move jump tables offline. */
124 return next_active_insn (insn
) == insn2
;
127 /* Return nonzero if we could reach target from src by falling through,
128 if the target was made adjacent. If we already have a fall-through
129 edge to the exit block, we can't do that. */
131 could_fall_through (basic_block src
, basic_block target
)
136 if (target
== EXIT_BLOCK_PTR
)
138 FOR_EACH_EDGE (e
, ei
, src
->succs
)
139 if (e
->dest
== EXIT_BLOCK_PTR
140 && e
->flags
& EDGE_FALLTHRU
)
145 /* Mark the back edges in DFS traversal.
146 Return nonzero if a loop (natural or otherwise) is present.
147 Inspired by Depth_First_Search_PP described in:
149 Advanced Compiler Design and Implementation
151 Morgan Kaufmann, 1997
153 and heavily borrowed from flow_depth_first_order_compute. */
156 mark_dfs_back_edges (void)
158 edge_iterator
*stack
;
167 /* Allocate the preorder and postorder number arrays. */
168 pre
= xcalloc (last_basic_block
, sizeof (int));
169 post
= xcalloc (last_basic_block
, sizeof (int));
171 /* Allocate stack for back-tracking up CFG. */
172 stack
= xmalloc ((n_basic_blocks
+ 1) * sizeof (edge_iterator
));
175 /* Allocate bitmap to track nodes that have been visited. */
176 visited
= sbitmap_alloc (last_basic_block
);
178 /* None of the nodes in the CFG have been visited yet. */
179 sbitmap_zero (visited
);
181 /* Push the first edge on to the stack. */
182 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
190 /* Look at the edge on the top of the stack. */
192 src
= ei_edge (ei
)->src
;
193 dest
= ei_edge (ei
)->dest
;
194 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
196 /* Check if the edge destination has been visited yet. */
197 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
199 /* Mark that we have visited the destination. */
200 SET_BIT (visited
, dest
->index
);
202 pre
[dest
->index
] = prenum
++;
203 if (EDGE_COUNT (dest
->succs
) > 0)
205 /* Since the DEST node has been visited for the first
206 time, check its successors. */
207 stack
[sp
++] = ei_start (dest
->succs
);
210 post
[dest
->index
] = postnum
++;
214 if (dest
!= EXIT_BLOCK_PTR
&& src
!= ENTRY_BLOCK_PTR
215 && pre
[src
->index
] >= pre
[dest
->index
]
216 && post
[dest
->index
] == 0)
217 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
219 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
220 post
[src
->index
] = postnum
++;
222 if (!ei_one_before_end_p (ei
))
223 ei_next (&stack
[sp
- 1]);
232 sbitmap_free (visited
);
237 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
240 set_edge_can_fallthru_flag (void)
249 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
251 e
->flags
&= ~EDGE_CAN_FALLTHRU
;
253 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
254 if (e
->flags
& EDGE_FALLTHRU
)
255 e
->flags
|= EDGE_CAN_FALLTHRU
;
258 /* If the BB ends with an invertible condjump all (2) edges are
259 CAN_FALLTHRU edges. */
260 if (EDGE_COUNT (bb
->succs
) != 2)
262 if (!any_condjump_p (BB_END (bb
)))
264 if (!invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0))
266 invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0);
267 EDGE_SUCC (bb
, 0)->flags
|= EDGE_CAN_FALLTHRU
;
268 EDGE_SUCC (bb
, 1)->flags
|= EDGE_CAN_FALLTHRU
;
272 /* Find unreachable blocks. An unreachable block will have 0 in
273 the reachable bit in block->flags. A nonzero value indicates the
274 block is reachable. */
277 find_unreachable_blocks (void)
281 basic_block
*tos
, *worklist
, bb
;
283 tos
= worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
285 /* Clear all the reachability flags. */
288 bb
->flags
&= ~BB_REACHABLE
;
290 /* Add our starting points to the worklist. Almost always there will
291 be only one. It isn't inconceivable that we might one day directly
292 support Fortran alternate entry points. */
294 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
298 /* Mark the block reachable. */
299 e
->dest
->flags
|= BB_REACHABLE
;
302 /* Iterate: find everything reachable from what we've already seen. */
304 while (tos
!= worklist
)
306 basic_block b
= *--tos
;
308 FOR_EACH_EDGE (e
, ei
, b
->succs
)
309 if (!(e
->dest
->flags
& BB_REACHABLE
))
312 e
->dest
->flags
|= BB_REACHABLE
;
319 /* Functions to access an edge list with a vector representation.
320 Enough data is kept such that given an index number, the
321 pred and succ that edge represents can be determined, or
322 given a pred and a succ, its index number can be returned.
323 This allows algorithms which consume a lot of memory to
324 represent the normally full matrix of edge (pred,succ) with a
325 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
326 wasted space in the client code due to sparse flow graphs. */
328 /* This functions initializes the edge list. Basically the entire
329 flowgraph is processed, and all edges are assigned a number,
330 and the data structure is filled in. */
333 create_edge_list (void)
335 struct edge_list
*elist
;
342 block_count
= n_basic_blocks
+ 2; /* Include the entry and exit blocks. */
346 /* Determine the number of edges in the flow graph by counting successor
347 edges on each basic block. */
348 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
350 num_edges
+= EDGE_COUNT (bb
->succs
);
353 elist
= xmalloc (sizeof (struct edge_list
));
354 elist
->num_blocks
= block_count
;
355 elist
->num_edges
= num_edges
;
356 elist
->index_to_edge
= xmalloc (sizeof (edge
) * num_edges
);
360 /* Follow successors of blocks, and register these edges. */
361 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
362 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
363 elist
->index_to_edge
[num_edges
++] = e
;
368 /* This function free's memory associated with an edge list. */
371 free_edge_list (struct edge_list
*elist
)
375 free (elist
->index_to_edge
);
380 /* This function provides debug output showing an edge list. */
383 print_edge_list (FILE *f
, struct edge_list
*elist
)
387 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
388 elist
->num_blocks
- 2, elist
->num_edges
);
390 for (x
= 0; x
< elist
->num_edges
; x
++)
392 fprintf (f
, " %-4d - edge(", x
);
393 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR
)
394 fprintf (f
, "entry,");
396 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
398 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR
)
399 fprintf (f
, "exit)\n");
401 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
405 /* This function provides an internal consistency check of an edge list,
406 verifying that all edges are present, and that there are no
410 verify_edge_list (FILE *f
, struct edge_list
*elist
)
412 int pred
, succ
, index
;
414 basic_block bb
, p
, s
;
417 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
419 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
421 pred
= e
->src
->index
;
422 succ
= e
->dest
->index
;
423 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
424 if (index
== EDGE_INDEX_NO_EDGE
)
426 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
430 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
431 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
432 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
433 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
434 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
435 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
439 /* We've verified that all the edges are in the list, now lets make sure
440 there are no spurious edges in the list. */
442 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
443 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
447 FOR_EACH_EDGE (e
, ei
, p
->succs
)
454 FOR_EACH_EDGE (e
, ei
, s
->preds
)
461 if (EDGE_INDEX (elist
, p
, s
)
462 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
463 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
465 if (EDGE_INDEX (elist
, p
, s
)
466 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
467 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
468 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
472 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
473 If no such edge exists, return NULL. */
476 find_edge (basic_block pred
, basic_block succ
)
481 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
483 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
489 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
497 /* This routine will determine what, if any, edge there is between
498 a specified predecessor and successor. */
501 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
505 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
506 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
507 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
510 return (EDGE_INDEX_NO_EDGE
);
513 /* Dump the list of basic blocks in the bitmap NODES. */
516 flow_nodes_print (const char *str
, const sbitmap nodes
, FILE *file
)
523 fprintf (file
, "%s { ", str
);
524 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {fprintf (file
, "%d ", node
);});
528 /* Dump the list of edges in the array EDGE_LIST. */
531 flow_edge_list_print (const char *str
, const edge
*edge_list
, int num_edges
, FILE *file
)
538 fprintf (file
, "%s { ", str
);
539 for (i
= 0; i
< num_edges
; i
++)
540 fprintf (file
, "%d->%d ", edge_list
[i
]->src
->index
,
541 edge_list
[i
]->dest
->index
);
547 /* This routine will remove any fake predecessor edges for a basic block.
548 When the edge is removed, it is also removed from whatever successor
552 remove_fake_predecessors (basic_block bb
)
557 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
559 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
566 /* This routine will remove all fake edges from the flow graph. If
567 we remove all fake successors, it will automatically remove all
568 fake predecessors. */
571 remove_fake_edges (void)
575 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
576 remove_fake_predecessors (bb
);
579 /* This routine will remove all fake edges to the EXIT_BLOCK. */
582 remove_fake_exit_edges (void)
584 remove_fake_predecessors (EXIT_BLOCK_PTR
);
588 /* This function will add a fake edge between any block which has no
589 successors, and the exit block. Some data flow equations require these
593 add_noreturn_fake_exit_edges (void)
598 if (EDGE_COUNT (bb
->succs
) == 0)
599 make_single_succ_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
602 /* This function adds a fake edge between any infinite loops to the
603 exit block. Some optimizations require a path from each node to
606 See also Morgan, Figure 3.10, pp. 82-83.
608 The current implementation is ugly, not attempting to minimize the
609 number of inserted fake edges. To reduce the number of fake edges
610 to insert, add fake edges from _innermost_ loops containing only
611 nodes not reachable from the exit block. */
614 connect_infinite_loops_to_exit (void)
616 basic_block unvisited_block
;
617 struct depth_first_search_dsS dfs_ds
;
619 /* Perform depth-first search in the reverse graph to find nodes
620 reachable from the exit block. */
621 flow_dfs_compute_reverse_init (&dfs_ds
);
622 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR
);
624 /* Repeatedly add fake edges, updating the unreachable nodes. */
627 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
);
628 if (!unvisited_block
)
631 make_edge (unvisited_block
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
632 flow_dfs_compute_reverse_add_bb (&dfs_ds
, unvisited_block
);
635 flow_dfs_compute_reverse_finish (&dfs_ds
);
639 /* Compute reverse top sort order. */
642 flow_reverse_top_sort_order_compute (int *rts_order
)
644 edge_iterator
*stack
;
649 /* Allocate stack for back-tracking up CFG. */
650 stack
= xmalloc ((n_basic_blocks
+ 1) * sizeof (edge_iterator
));
653 /* Allocate bitmap to track nodes that have been visited. */
654 visited
= sbitmap_alloc (last_basic_block
);
656 /* None of the nodes in the CFG have been visited yet. */
657 sbitmap_zero (visited
);
659 /* Push the first edge on to the stack. */
660 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
668 /* Look at the edge on the top of the stack. */
670 src
= ei_edge (ei
)->src
;
671 dest
= ei_edge (ei
)->dest
;
673 /* Check if the edge destination has been visited yet. */
674 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
676 /* Mark that we have visited the destination. */
677 SET_BIT (visited
, dest
->index
);
679 if (EDGE_COUNT (dest
->succs
) > 0)
680 /* Since the DEST node has been visited for the first
681 time, check its successors. */
682 stack
[sp
++] = ei_start (dest
->succs
);
684 rts_order
[postnum
++] = dest
->index
;
688 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
689 rts_order
[postnum
++] = src
->index
;
691 if (!ei_one_before_end_p (ei
))
692 ei_next (&stack
[sp
- 1]);
699 sbitmap_free (visited
);
702 /* Compute the depth first search order and store in the array
703 DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
704 RC_ORDER is nonzero, return the reverse completion number for each
705 node. Returns the number of nodes visited. A depth first search
706 tries to get as far away from the starting point as quickly as
710 flow_depth_first_order_compute (int *dfs_order
, int *rc_order
)
712 edge_iterator
*stack
;
715 int rcnum
= n_basic_blocks
- 1;
718 /* Allocate stack for back-tracking up CFG. */
719 stack
= xmalloc ((n_basic_blocks
+ 1) * sizeof (edge_iterator
));
722 /* Allocate bitmap to track nodes that have been visited. */
723 visited
= sbitmap_alloc (last_basic_block
);
725 /* None of the nodes in the CFG have been visited yet. */
726 sbitmap_zero (visited
);
728 /* Push the first edge on to the stack. */
729 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
737 /* Look at the edge on the top of the stack. */
739 src
= ei_edge (ei
)->src
;
740 dest
= ei_edge (ei
)->dest
;
742 /* Check if the edge destination has been visited yet. */
743 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
745 /* Mark that we have visited the destination. */
746 SET_BIT (visited
, dest
->index
);
749 dfs_order
[dfsnum
] = dest
->index
;
753 if (EDGE_COUNT (dest
->succs
) > 0)
754 /* Since the DEST node has been visited for the first
755 time, check its successors. */
756 stack
[sp
++] = ei_start (dest
->succs
);
758 /* There are no successors for the DEST node so assign
759 its reverse completion number. */
760 rc_order
[rcnum
--] = dest
->index
;
764 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
766 /* There are no more successors for the SRC node
767 so assign its reverse completion number. */
768 rc_order
[rcnum
--] = src
->index
;
770 if (!ei_one_before_end_p (ei
))
771 ei_next (&stack
[sp
- 1]);
778 sbitmap_free (visited
);
780 /* The number of nodes visited should be the number of blocks. */
781 gcc_assert (dfsnum
== n_basic_blocks
);
786 /* Compute the depth first search order on the _reverse_ graph and
787 store in the array DFS_ORDER, marking the nodes visited in VISITED.
788 Returns the number of nodes visited.
790 The computation is split into three pieces:
792 flow_dfs_compute_reverse_init () creates the necessary data
795 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
796 structures. The block will start the search.
798 flow_dfs_compute_reverse_execute () continues (or starts) the
799 search using the block on the top of the stack, stopping when the
802 flow_dfs_compute_reverse_finish () destroys the necessary data
805 Thus, the user will probably call ..._init(), call ..._add_bb() to
806 add a beginning basic block to the stack, call ..._execute(),
807 possibly add another bb to the stack and again call ..._execute(),
808 ..., and finally call _finish(). */
810 /* Initialize the data structures used for depth-first search on the
811 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
812 added to the basic block stack. DATA is the current depth-first
813 search context. If INITIALIZE_STACK is nonzero, there is an
814 element on the stack. */
817 flow_dfs_compute_reverse_init (depth_first_search_ds data
)
819 /* Allocate stack for back-tracking up CFG. */
820 data
->stack
= xmalloc ((n_basic_blocks
- (INVALID_BLOCK
+ 1))
821 * sizeof (basic_block
));
824 /* Allocate bitmap to track nodes that have been visited. */
825 data
->visited_blocks
= sbitmap_alloc (last_basic_block
- (INVALID_BLOCK
+ 1));
827 /* None of the nodes in the CFG have been visited yet. */
828 sbitmap_zero (data
->visited_blocks
);
833 /* Add the specified basic block to the top of the dfs data
834 structures. When the search continues, it will start at the
838 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data
, basic_block bb
)
840 data
->stack
[data
->sp
++] = bb
;
841 SET_BIT (data
->visited_blocks
, bb
->index
- (INVALID_BLOCK
+ 1));
844 /* Continue the depth-first search through the reverse graph starting with the
845 block at the stack's top and ending when the stack is empty. Visited nodes
846 are marked. Returns an unvisited basic block, or NULL if there is none
850 flow_dfs_compute_reverse_execute (depth_first_search_ds data
)
858 bb
= data
->stack
[--data
->sp
];
860 /* Perform depth-first search on adjacent vertices. */
861 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
862 if (!TEST_BIT (data
->visited_blocks
,
863 e
->src
->index
- (INVALID_BLOCK
+ 1)))
864 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
867 /* Determine if there are unvisited basic blocks. */
868 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR
, NULL
, prev_bb
)
869 if (!TEST_BIT (data
->visited_blocks
, bb
->index
- (INVALID_BLOCK
+ 1)))
875 /* Destroy the data structures needed for depth-first search on the
879 flow_dfs_compute_reverse_finish (depth_first_search_ds data
)
882 sbitmap_free (data
->visited_blocks
);
885 /* Performs dfs search from BB over vertices satisfying PREDICATE;
886 if REVERSE, go against direction of edges. Returns number of blocks
887 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
889 dfs_enumerate_from (basic_block bb
, int reverse
,
890 bool (*predicate
) (basic_block
, void *),
891 basic_block
*rslt
, int rslt_max
, void *data
)
893 basic_block
*st
, lbb
;
896 st
= xcalloc (rslt_max
, sizeof (basic_block
));
897 rslt
[tv
++] = st
[sp
++] = bb
;
898 bb
->flags
|= BB_VISITED
;
906 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
907 if (!(e
->src
->flags
& BB_VISITED
) && predicate (e
->src
, data
))
909 gcc_assert (tv
!= rslt_max
);
910 rslt
[tv
++] = st
[sp
++] = e
->src
;
911 e
->src
->flags
|= BB_VISITED
;
916 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
917 if (!(e
->dest
->flags
& BB_VISITED
) && predicate (e
->dest
, data
))
919 gcc_assert (tv
!= rslt_max
);
920 rslt
[tv
++] = st
[sp
++] = e
->dest
;
921 e
->dest
->flags
|= BB_VISITED
;
926 for (sp
= 0; sp
< tv
; sp
++)
927 rslt
[sp
]->flags
&= ~BB_VISITED
;
932 /* Computing the Dominance Frontier:
934 As described in Morgan, section 3.5, this may be done simply by
935 walking the dominator tree bottom-up, computing the frontier for
936 the children before the parent. When considering a block B,
939 (1) A flow graph edge leaving B that does not lead to a child
940 of B in the dominator tree must be a block that is either equal
941 to B or not dominated by B. Such blocks belong in the frontier
944 (2) Consider a block X in the frontier of one of the children C
945 of B. If X is not equal to B and is not dominated by B, it
946 is in the frontier of B. */
949 compute_dominance_frontiers_1 (bitmap
*frontiers
, basic_block bb
, sbitmap done
)
955 SET_BIT (done
, bb
->index
);
957 /* Do the frontier of the children first. Not all children in the
958 dominator tree (blocks dominated by this one) are children in the
959 CFG, so check all blocks. */
960 for (c
= first_dom_son (CDI_DOMINATORS
, bb
);
962 c
= next_dom_son (CDI_DOMINATORS
, c
))
964 if (! TEST_BIT (done
, c
->index
))
965 compute_dominance_frontiers_1 (frontiers
, c
, done
);
968 /* Find blocks conforming to rule (1) above. */
969 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
971 if (e
->dest
== EXIT_BLOCK_PTR
)
973 if (get_immediate_dominator (CDI_DOMINATORS
, e
->dest
) != bb
)
974 bitmap_set_bit (frontiers
[bb
->index
], e
->dest
->index
);
977 /* Find blocks conforming to rule (2). */
978 for (c
= first_dom_son (CDI_DOMINATORS
, bb
);
980 c
= next_dom_son (CDI_DOMINATORS
, c
))
985 EXECUTE_IF_SET_IN_BITMAP (frontiers
[c
->index
], 0, x
, bi
)
987 if (get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (x
)) != bb
)
988 bitmap_set_bit (frontiers
[bb
->index
], x
);
995 compute_dominance_frontiers (bitmap
*frontiers
)
997 sbitmap done
= sbitmap_alloc (last_basic_block
);
999 timevar_push (TV_DOM_FRONTIERS
);
1001 sbitmap_zero (done
);
1003 compute_dominance_frontiers_1 (frontiers
, EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
, done
);
1005 sbitmap_free (done
);
1007 timevar_pop (TV_DOM_FRONTIERS
);