1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This file contains various simple utilities to analyze the CFG. */
24 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
38 /* Store the data structures necessary for depth-first search. */
39 struct depth_first_search_dsS
{
40 /* stack for backtracking during the algorithm */
43 /* number of edges in the stack. That is, positions 0, ..., sp-1
47 /* record of basic blocks already seen by depth-first search */
48 sbitmap visited_blocks
;
50 typedef struct depth_first_search_dsS
*depth_first_search_ds
;
52 static void flow_dfs_compute_reverse_init (depth_first_search_ds
);
53 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds
,
55 static basic_block
flow_dfs_compute_reverse_execute (depth_first_search_ds
,
57 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
);
58 static bool flow_active_insn_p (const_rtx
);
60 /* Like active_insn_p, except keep the return value clobber around
64 flow_active_insn_p (const_rtx insn
)
66 if (active_insn_p (insn
))
69 /* A clobber of the function return value exists for buggy
70 programs that fail to return a value. Its effect is to
71 keep the return value from being live across the entire
72 function. If we allow it to be skipped, we introduce the
73 possibility for register lifetime confusion. */
74 if (GET_CODE (PATTERN (insn
)) == CLOBBER
75 && REG_P (XEXP (PATTERN (insn
), 0))
76 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
82 /* Return true if the block has no effect and only forwards control flow to
83 its single destination. */
86 forwarder_block_p (const_basic_block bb
)
90 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
91 || !single_succ_p (bb
))
94 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
95 if (INSN_P (insn
) && flow_active_insn_p (insn
))
98 return (!INSN_P (insn
)
99 || (JUMP_P (insn
) && simplejump_p (insn
))
100 || !flow_active_insn_p (insn
));
103 /* Return nonzero if we can reach target from src by falling through. */
106 can_fallthru (basic_block src
, basic_block target
)
108 rtx insn
= BB_END (src
);
113 if (target
== EXIT_BLOCK_PTR
)
115 if (src
->next_bb
!= target
)
117 FOR_EACH_EDGE (e
, ei
, src
->succs
)
118 if (e
->dest
== EXIT_BLOCK_PTR
119 && e
->flags
& EDGE_FALLTHRU
)
122 insn2
= BB_HEAD (target
);
123 if (insn2
&& !active_insn_p (insn2
))
124 insn2
= next_active_insn (insn2
);
126 /* ??? Later we may add code to move jump tables offline. */
127 return next_active_insn (insn
) == insn2
;
130 /* Return nonzero if we could reach target from src by falling through,
131 if the target was made adjacent. If we already have a fall-through
132 edge to the exit block, we can't do that. */
134 could_fall_through (basic_block src
, basic_block target
)
139 if (target
== EXIT_BLOCK_PTR
)
141 FOR_EACH_EDGE (e
, ei
, src
->succs
)
142 if (e
->dest
== EXIT_BLOCK_PTR
143 && e
->flags
& EDGE_FALLTHRU
)
148 /* Mark the back edges in DFS traversal.
149 Return nonzero if a loop (natural or otherwise) is present.
150 Inspired by Depth_First_Search_PP described in:
152 Advanced Compiler Design and Implementation
154 Morgan Kaufmann, 1997
156 and heavily borrowed from pre_and_rev_post_order_compute. */
159 mark_dfs_back_edges (void)
161 edge_iterator
*stack
;
170 /* Allocate the preorder and postorder number arrays. */
171 pre
= XCNEWVEC (int, last_basic_block
);
172 post
= XCNEWVEC (int, last_basic_block
);
174 /* Allocate stack for back-tracking up CFG. */
175 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
178 /* Allocate bitmap to track nodes that have been visited. */
179 visited
= sbitmap_alloc (last_basic_block
);
181 /* None of the nodes in the CFG have been visited yet. */
182 sbitmap_zero (visited
);
184 /* Push the first edge on to the stack. */
185 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
193 /* Look at the edge on the top of the stack. */
195 src
= ei_edge (ei
)->src
;
196 dest
= ei_edge (ei
)->dest
;
197 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
199 /* Check if the edge destination has been visited yet. */
200 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
202 /* Mark that we have visited the destination. */
203 SET_BIT (visited
, dest
->index
);
205 pre
[dest
->index
] = prenum
++;
206 if (EDGE_COUNT (dest
->succs
) > 0)
208 /* Since the DEST node has been visited for the first
209 time, check its successors. */
210 stack
[sp
++] = ei_start (dest
->succs
);
213 post
[dest
->index
] = postnum
++;
217 if (dest
!= EXIT_BLOCK_PTR
&& src
!= ENTRY_BLOCK_PTR
218 && pre
[src
->index
] >= pre
[dest
->index
]
219 && post
[dest
->index
] == 0)
220 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
222 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
223 post
[src
->index
] = postnum
++;
225 if (!ei_one_before_end_p (ei
))
226 ei_next (&stack
[sp
- 1]);
235 sbitmap_free (visited
);
240 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
243 set_edge_can_fallthru_flag (void)
252 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
254 e
->flags
&= ~EDGE_CAN_FALLTHRU
;
256 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
257 if (e
->flags
& EDGE_FALLTHRU
)
258 e
->flags
|= EDGE_CAN_FALLTHRU
;
261 /* If the BB ends with an invertible condjump all (2) edges are
262 CAN_FALLTHRU edges. */
263 if (EDGE_COUNT (bb
->succs
) != 2)
265 if (!any_condjump_p (BB_END (bb
)))
267 if (!invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0))
269 invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0);
270 EDGE_SUCC (bb
, 0)->flags
|= EDGE_CAN_FALLTHRU
;
271 EDGE_SUCC (bb
, 1)->flags
|= EDGE_CAN_FALLTHRU
;
275 /* Find unreachable blocks. An unreachable block will have 0 in
276 the reachable bit in block->flags. A nonzero value indicates the
277 block is reachable. */
280 find_unreachable_blocks (void)
284 basic_block
*tos
, *worklist
, bb
;
286 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
288 /* Clear all the reachability flags. */
291 bb
->flags
&= ~BB_REACHABLE
;
293 /* Add our starting points to the worklist. Almost always there will
294 be only one. It isn't inconceivable that we might one day directly
295 support Fortran alternate entry points. */
297 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
301 /* Mark the block reachable. */
302 e
->dest
->flags
|= BB_REACHABLE
;
305 /* Iterate: find everything reachable from what we've already seen. */
307 while (tos
!= worklist
)
309 basic_block b
= *--tos
;
311 FOR_EACH_EDGE (e
, ei
, b
->succs
)
313 basic_block dest
= e
->dest
;
315 if (!(dest
->flags
& BB_REACHABLE
))
318 dest
->flags
|= BB_REACHABLE
;
326 /* Functions to access an edge list with a vector representation.
327 Enough data is kept such that given an index number, the
328 pred and succ that edge represents can be determined, or
329 given a pred and a succ, its index number can be returned.
330 This allows algorithms which consume a lot of memory to
331 represent the normally full matrix of edge (pred,succ) with a
332 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
333 wasted space in the client code due to sparse flow graphs. */
335 /* This functions initializes the edge list. Basically the entire
336 flowgraph is processed, and all edges are assigned a number,
337 and the data structure is filled in. */
340 create_edge_list (void)
342 struct edge_list
*elist
;
349 block_count
= n_basic_blocks
; /* Include the entry and exit blocks. */
353 /* Determine the number of edges in the flow graph by counting successor
354 edges on each basic block. */
355 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
357 num_edges
+= EDGE_COUNT (bb
->succs
);
360 elist
= XNEW (struct edge_list
);
361 elist
->num_blocks
= block_count
;
362 elist
->num_edges
= num_edges
;
363 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
367 /* Follow successors of blocks, and register these edges. */
368 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
369 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
370 elist
->index_to_edge
[num_edges
++] = e
;
375 /* This function free's memory associated with an edge list. */
378 free_edge_list (struct edge_list
*elist
)
382 free (elist
->index_to_edge
);
387 /* This function provides debug output showing an edge list. */
390 print_edge_list (FILE *f
, struct edge_list
*elist
)
394 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
395 elist
->num_blocks
, elist
->num_edges
);
397 for (x
= 0; x
< elist
->num_edges
; x
++)
399 fprintf (f
, " %-4d - edge(", x
);
400 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR
)
401 fprintf (f
, "entry,");
403 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
405 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR
)
406 fprintf (f
, "exit)\n");
408 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
412 /* This function provides an internal consistency check of an edge list,
413 verifying that all edges are present, and that there are no
417 verify_edge_list (FILE *f
, struct edge_list
*elist
)
419 int pred
, succ
, index
;
421 basic_block bb
, p
, s
;
424 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
426 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
428 pred
= e
->src
->index
;
429 succ
= e
->dest
->index
;
430 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
431 if (index
== EDGE_INDEX_NO_EDGE
)
433 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
437 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
438 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
439 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
440 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
441 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
442 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
446 /* We've verified that all the edges are in the list, now lets make sure
447 there are no spurious edges in the list. */
449 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
450 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
454 FOR_EACH_EDGE (e
, ei
, p
->succs
)
461 FOR_EACH_EDGE (e
, ei
, s
->preds
)
468 if (EDGE_INDEX (elist
, p
, s
)
469 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
470 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
472 if (EDGE_INDEX (elist
, p
, s
)
473 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
474 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
475 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
479 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
480 If no such edge exists, return NULL. */
483 find_edge (basic_block pred
, basic_block succ
)
488 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
490 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
496 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
504 /* This routine will determine what, if any, edge there is between
505 a specified predecessor and successor. */
508 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
512 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
513 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
514 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
517 return (EDGE_INDEX_NO_EDGE
);
520 /* Dump the list of basic blocks in the bitmap NODES. */
523 flow_nodes_print (const char *str
, const_sbitmap nodes
, FILE *file
)
525 unsigned int node
= 0;
526 sbitmap_iterator sbi
;
531 fprintf (file
, "%s { ", str
);
532 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, sbi
)
533 fprintf (file
, "%d ", node
);
537 /* Dump the list of edges in the array EDGE_LIST. */
540 flow_edge_list_print (const char *str
, const edge
*edge_list
, int num_edges
, FILE *file
)
547 fprintf (file
, "%s { ", str
);
548 for (i
= 0; i
< num_edges
; i
++)
549 fprintf (file
, "%d->%d ", edge_list
[i
]->src
->index
,
550 edge_list
[i
]->dest
->index
);
556 /* This routine will remove any fake predecessor edges for a basic block.
557 When the edge is removed, it is also removed from whatever successor
561 remove_fake_predecessors (basic_block bb
)
566 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
568 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
575 /* This routine will remove all fake edges from the flow graph. If
576 we remove all fake successors, it will automatically remove all
577 fake predecessors. */
580 remove_fake_edges (void)
584 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
585 remove_fake_predecessors (bb
);
588 /* This routine will remove all fake edges to the EXIT_BLOCK. */
591 remove_fake_exit_edges (void)
593 remove_fake_predecessors (EXIT_BLOCK_PTR
);
597 /* This function will add a fake edge between any block which has no
598 successors, and the exit block. Some data flow equations require these
602 add_noreturn_fake_exit_edges (void)
607 if (EDGE_COUNT (bb
->succs
) == 0)
608 make_single_succ_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
611 /* This function adds a fake edge between any infinite loops to the
612 exit block. Some optimizations require a path from each node to
615 See also Morgan, Figure 3.10, pp. 82-83.
617 The current implementation is ugly, not attempting to minimize the
618 number of inserted fake edges. To reduce the number of fake edges
619 to insert, add fake edges from _innermost_ loops containing only
620 nodes not reachable from the exit block. */
623 connect_infinite_loops_to_exit (void)
625 basic_block unvisited_block
= EXIT_BLOCK_PTR
;
626 struct depth_first_search_dsS dfs_ds
;
628 /* Perform depth-first search in the reverse graph to find nodes
629 reachable from the exit block. */
630 flow_dfs_compute_reverse_init (&dfs_ds
);
631 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR
);
633 /* Repeatedly add fake edges, updating the unreachable nodes. */
636 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
638 if (!unvisited_block
)
641 make_edge (unvisited_block
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
642 flow_dfs_compute_reverse_add_bb (&dfs_ds
, unvisited_block
);
645 flow_dfs_compute_reverse_finish (&dfs_ds
);
649 /* Compute reverse top sort order. This is computing a post order
650 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then then
651 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
652 true, unreachable blocks are deleted. */
655 post_order_compute (int *post_order
, bool include_entry_exit
,
656 bool delete_unreachable
)
658 edge_iterator
*stack
;
660 int post_order_num
= 0;
664 if (include_entry_exit
)
665 post_order
[post_order_num
++] = EXIT_BLOCK
;
667 /* Allocate stack for back-tracking up CFG. */
668 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
671 /* Allocate bitmap to track nodes that have been visited. */
672 visited
= sbitmap_alloc (last_basic_block
);
674 /* None of the nodes in the CFG have been visited yet. */
675 sbitmap_zero (visited
);
677 /* Push the first edge on to the stack. */
678 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
686 /* Look at the edge on the top of the stack. */
688 src
= ei_edge (ei
)->src
;
689 dest
= ei_edge (ei
)->dest
;
691 /* Check if the edge destination has been visited yet. */
692 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
694 /* Mark that we have visited the destination. */
695 SET_BIT (visited
, dest
->index
);
697 if (EDGE_COUNT (dest
->succs
) > 0)
698 /* Since the DEST node has been visited for the first
699 time, check its successors. */
700 stack
[sp
++] = ei_start (dest
->succs
);
702 post_order
[post_order_num
++] = dest
->index
;
706 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
707 post_order
[post_order_num
++] = src
->index
;
709 if (!ei_one_before_end_p (ei
))
710 ei_next (&stack
[sp
- 1]);
716 if (include_entry_exit
)
718 post_order
[post_order_num
++] = ENTRY_BLOCK
;
719 count
= post_order_num
;
722 count
= post_order_num
+ 2;
724 /* Delete the unreachable blocks if some were found and we are
725 supposed to do it. */
726 if (delete_unreachable
&& (count
!= n_basic_blocks
))
730 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
732 next_bb
= b
->next_bb
;
734 if (!(TEST_BIT (visited
, b
->index
)))
735 delete_basic_block (b
);
738 tidy_fallthru_edges ();
742 sbitmap_free (visited
);
743 return post_order_num
;
747 /* Helper routine for inverted_post_order_compute.
748 BB has to belong to a region of CFG
749 unreachable by inverted traversal from the exit.
750 i.e. there's no control flow path from ENTRY to EXIT
751 that contains this BB.
752 This can happen in two cases - if there's an infinite loop
753 or if there's a block that has no successor
754 (call to a function with no return).
755 Some RTL passes deal with this condition by
756 calling connect_infinite_loops_to_exit () and/or
757 add_noreturn_fake_exit_edges ().
758 However, those methods involve modifying the CFG itself
759 which may not be desirable.
760 Hence, we deal with the infinite loop/no return cases
761 by identifying a unique basic block that can reach all blocks
762 in such a region by inverted traversal.
763 This function returns a basic block that guarantees
764 that all blocks in the region are reachable
765 by starting an inverted traversal from the returned block. */
768 dfs_find_deadend (basic_block bb
)
770 sbitmap visited
= sbitmap_alloc (last_basic_block
);
771 sbitmap_zero (visited
);
775 SET_BIT (visited
, bb
->index
);
776 if (EDGE_COUNT (bb
->succs
) == 0
777 || TEST_BIT (visited
, EDGE_SUCC (bb
, 0)->dest
->index
))
779 sbitmap_free (visited
);
783 bb
= EDGE_SUCC (bb
, 0)->dest
;
790 /* Compute the reverse top sort order of the inverted CFG
791 i.e. starting from the exit block and following the edges backward
792 (from successors to predecessors).
793 This ordering can be used for forward dataflow problems among others.
795 This function assumes that all blocks in the CFG are reachable
796 from the ENTRY (but not necessarily from EXIT).
798 If there's an infinite loop,
799 a simple inverted traversal starting from the blocks
800 with no successors can't visit all blocks.
801 To solve this problem, we first do inverted traversal
802 starting from the blocks with no successor.
803 And if there's any block left that's not visited by the regular
804 inverted traversal from EXIT,
805 those blocks are in such problematic region.
806 Among those, we find one block that has
807 any visited predecessor (which is an entry into such a region),
808 and start looking for a "dead end" from that block
809 and do another inverted traversal from that block. */
812 inverted_post_order_compute (int *post_order
)
815 edge_iterator
*stack
;
817 int post_order_num
= 0;
820 /* Allocate stack for back-tracking up CFG. */
821 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
824 /* Allocate bitmap to track nodes that have been visited. */
825 visited
= sbitmap_alloc (last_basic_block
);
827 /* None of the nodes in the CFG have been visited yet. */
828 sbitmap_zero (visited
);
830 /* Put all blocks that have no successor into the initial work list. */
831 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
832 if (EDGE_COUNT (bb
->succs
) == 0)
834 /* Push the initial edge on to the stack. */
835 if (EDGE_COUNT (bb
->preds
) > 0)
837 stack
[sp
++] = ei_start (bb
->preds
);
838 SET_BIT (visited
, bb
->index
);
844 bool has_unvisited_bb
= false;
846 /* The inverted traversal loop. */
852 /* Look at the edge on the top of the stack. */
854 bb
= ei_edge (ei
)->dest
;
855 pred
= ei_edge (ei
)->src
;
857 /* Check if the predecessor has been visited yet. */
858 if (! TEST_BIT (visited
, pred
->index
))
860 /* Mark that we have visited the destination. */
861 SET_BIT (visited
, pred
->index
);
863 if (EDGE_COUNT (pred
->preds
) > 0)
864 /* Since the predecessor node has been visited for the first
865 time, check its predecessors. */
866 stack
[sp
++] = ei_start (pred
->preds
);
868 post_order
[post_order_num
++] = pred
->index
;
872 if (bb
!= EXIT_BLOCK_PTR
&& ei_one_before_end_p (ei
))
873 post_order
[post_order_num
++] = bb
->index
;
875 if (!ei_one_before_end_p (ei
))
876 ei_next (&stack
[sp
- 1]);
882 /* Detect any infinite loop and activate the kludge.
883 Note that this doesn't check EXIT_BLOCK itself
884 since EXIT_BLOCK is always added after the outer do-while loop. */
885 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
886 if (!TEST_BIT (visited
, bb
->index
))
888 has_unvisited_bb
= true;
890 if (EDGE_COUNT (bb
->preds
) > 0)
894 basic_block visited_pred
= NULL
;
896 /* Find an already visited predecessor. */
897 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
899 if (TEST_BIT (visited
, e
->src
->index
))
900 visited_pred
= e
->src
;
905 basic_block be
= dfs_find_deadend (bb
);
906 gcc_assert (be
!= NULL
);
907 SET_BIT (visited
, be
->index
);
908 stack
[sp
++] = ei_start (be
->preds
);
914 if (has_unvisited_bb
&& sp
== 0)
916 /* No blocks are reachable from EXIT at all.
917 Find a dead-end from the ENTRY, and restart the iteration. */
918 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR
);
919 gcc_assert (be
!= NULL
);
920 SET_BIT (visited
, be
->index
);
921 stack
[sp
++] = ei_start (be
->preds
);
924 /* The only case the below while fires is
925 when there's an infinite loop. */
929 /* EXIT_BLOCK is always included. */
930 post_order
[post_order_num
++] = EXIT_BLOCK
;
933 sbitmap_free (visited
);
934 return post_order_num
;
937 /* Compute the depth first search order and store in the array
938 PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
939 REV_POST_ORDER is nonzero, return the reverse completion number for each
940 node. Returns the number of nodes visited. A depth first search
941 tries to get as far away from the starting point as quickly as
944 pre_order is a really a preorder numbering of the graph.
945 rev_post_order is really a reverse postorder numbering of the graph.
949 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
950 bool include_entry_exit
)
952 edge_iterator
*stack
;
954 int pre_order_num
= 0;
955 int rev_post_order_num
= n_basic_blocks
- 1;
958 /* Allocate stack for back-tracking up CFG. */
959 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
962 if (include_entry_exit
)
965 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
968 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
971 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
973 /* Allocate bitmap to track nodes that have been visited. */
974 visited
= sbitmap_alloc (last_basic_block
);
976 /* None of the nodes in the CFG have been visited yet. */
977 sbitmap_zero (visited
);
979 /* Push the first edge on to the stack. */
980 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
988 /* Look at the edge on the top of the stack. */
990 src
= ei_edge (ei
)->src
;
991 dest
= ei_edge (ei
)->dest
;
993 /* Check if the edge destination has been visited yet. */
994 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
996 /* Mark that we have visited the destination. */
997 SET_BIT (visited
, dest
->index
);
1000 pre_order
[pre_order_num
] = dest
->index
;
1004 if (EDGE_COUNT (dest
->succs
) > 0)
1005 /* Since the DEST node has been visited for the first
1006 time, check its successors. */
1007 stack
[sp
++] = ei_start (dest
->succs
);
1008 else if (rev_post_order
)
1009 /* There are no successors for the DEST node so assign
1010 its reverse completion number. */
1011 rev_post_order
[rev_post_order_num
--] = dest
->index
;
1015 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
1017 /* There are no more successors for the SRC node
1018 so assign its reverse completion number. */
1019 rev_post_order
[rev_post_order_num
--] = src
->index
;
1021 if (!ei_one_before_end_p (ei
))
1022 ei_next (&stack
[sp
- 1]);
1029 sbitmap_free (visited
);
1031 if (include_entry_exit
)
1034 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1037 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
1038 /* The number of nodes visited should be the number of blocks. */
1039 gcc_assert (pre_order_num
== n_basic_blocks
);
1042 /* The number of nodes visited should be the number of blocks minus
1043 the entry and exit blocks which are not visited here. */
1044 gcc_assert (pre_order_num
== n_basic_blocks
- NUM_FIXED_BLOCKS
);
1046 return pre_order_num
;
1049 /* Compute the depth first search order on the _reverse_ graph and
1050 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1051 Returns the number of nodes visited.
1053 The computation is split into three pieces:
1055 flow_dfs_compute_reverse_init () creates the necessary data
1058 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1059 structures. The block will start the search.
1061 flow_dfs_compute_reverse_execute () continues (or starts) the
1062 search using the block on the top of the stack, stopping when the
1065 flow_dfs_compute_reverse_finish () destroys the necessary data
1068 Thus, the user will probably call ..._init(), call ..._add_bb() to
1069 add a beginning basic block to the stack, call ..._execute(),
1070 possibly add another bb to the stack and again call ..._execute(),
1071 ..., and finally call _finish(). */
1073 /* Initialize the data structures used for depth-first search on the
1074 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1075 added to the basic block stack. DATA is the current depth-first
1076 search context. If INITIALIZE_STACK is nonzero, there is an
1077 element on the stack. */
1080 flow_dfs_compute_reverse_init (depth_first_search_ds data
)
1082 /* Allocate stack for back-tracking up CFG. */
1083 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks
);
1086 /* Allocate bitmap to track nodes that have been visited. */
1087 data
->visited_blocks
= sbitmap_alloc (last_basic_block
);
1089 /* None of the nodes in the CFG have been visited yet. */
1090 sbitmap_zero (data
->visited_blocks
);
1095 /* Add the specified basic block to the top of the dfs data
1096 structures. When the search continues, it will start at the
1100 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data
, basic_block bb
)
1102 data
->stack
[data
->sp
++] = bb
;
1103 SET_BIT (data
->visited_blocks
, bb
->index
);
1106 /* Continue the depth-first search through the reverse graph starting with the
1107 block at the stack's top and ending when the stack is empty. Visited nodes
1108 are marked. Returns an unvisited basic block, or NULL if there is none
1112 flow_dfs_compute_reverse_execute (depth_first_search_ds data
,
1113 basic_block last_unvisited
)
1119 while (data
->sp
> 0)
1121 bb
= data
->stack
[--data
->sp
];
1123 /* Perform depth-first search on adjacent vertices. */
1124 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1125 if (!TEST_BIT (data
->visited_blocks
, e
->src
->index
))
1126 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1129 /* Determine if there are unvisited basic blocks. */
1130 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1131 if (!TEST_BIT (data
->visited_blocks
, bb
->index
))
1137 /* Destroy the data structures needed for depth-first search on the
1141 flow_dfs_compute_reverse_finish (depth_first_search_ds data
)
1144 sbitmap_free (data
->visited_blocks
);
1147 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1148 if REVERSE, go against direction of edges. Returns number of blocks
1149 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1151 dfs_enumerate_from (basic_block bb
, int reverse
,
1152 bool (*predicate
) (const_basic_block
, const void *),
1153 basic_block
*rslt
, int rslt_max
, const void *data
)
1155 basic_block
*st
, lbb
;
1159 /* A bitmap to keep track of visited blocks. Allocating it each time
1160 this function is called is not possible, since dfs_enumerate_from
1161 is often used on small (almost) disjoint parts of cfg (bodies of
1162 loops), and allocating a large sbitmap would lead to quadratic
1164 static sbitmap visited
;
1165 static unsigned v_size
;
1167 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
1168 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
1169 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
1171 /* Resize the VISITED sbitmap if necessary. */
1172 size
= last_basic_block
;
1179 visited
= sbitmap_alloc (size
);
1180 sbitmap_zero (visited
);
1183 else if (v_size
< size
)
1185 /* Ensure that we increase the size of the sbitmap exponentially. */
1186 if (2 * v_size
> size
)
1189 visited
= sbitmap_resize (visited
, size
, 0);
1193 st
= XCNEWVEC (basic_block
, rslt_max
);
1194 rslt
[tv
++] = st
[sp
++] = bb
;
1203 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1204 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1206 gcc_assert (tv
!= rslt_max
);
1207 rslt
[tv
++] = st
[sp
++] = e
->src
;
1208 MARK_VISITED (e
->src
);
1213 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1214 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1216 gcc_assert (tv
!= rslt_max
);
1217 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1218 MARK_VISITED (e
->dest
);
1223 for (sp
= 0; sp
< tv
; sp
++)
1224 UNMARK_VISITED (rslt
[sp
]);
1227 #undef UNMARK_VISITED
1232 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1234 This algorithm can be found in Timothy Harvey's PhD thesis, at
1235 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1236 dominance algorithms.
1238 First, we identify each join point, j (any node with more than one
1239 incoming edge is a join point).
1241 We then examine each predecessor, p, of j and walk up the dominator tree
1244 We stop the walk when we reach j's immediate dominator - j is in the
1245 dominance frontier of each of the nodes in the walk, except for j's
1246 immediate dominator. Intuitively, all of the rest of j's dominators are
1247 shared by j's predecessors as well.
1248 Since they dominate j, they will not have j in their dominance frontiers.
1250 The number of nodes touched by this algorithm is equal to the size
1251 of the dominance frontiers, no more, no less.
1256 compute_dominance_frontiers_1 (bitmap
*frontiers
)
1263 if (EDGE_COUNT (b
->preds
) >= 2)
1265 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1267 basic_block runner
= p
->src
;
1269 if (runner
== ENTRY_BLOCK_PTR
)
1272 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1273 while (runner
!= domsb
)
1275 if (bitmap_bit_p (frontiers
[runner
->index
], b
->index
))
1277 bitmap_set_bit (frontiers
[runner
->index
],
1279 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1289 compute_dominance_frontiers (bitmap
*frontiers
)
1291 timevar_push (TV_DOM_FRONTIERS
);
1293 compute_dominance_frontiers_1 (frontiers
);
1295 timevar_pop (TV_DOM_FRONTIERS
);
1298 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1299 return a bitmap with all the blocks in the iterated dominance
1300 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1301 frontier information as returned by compute_dominance_frontiers.
1303 The resulting set of blocks are the potential sites where PHI nodes
1304 are needed. The caller is responsible for freeing the memory
1305 allocated for the return value. */
1308 compute_idf (bitmap def_blocks
, bitmap
*dfs
)
1311 unsigned bb_index
, i
;
1312 VEC(int,heap
) *work_stack
;
1313 bitmap phi_insertion_points
;
1315 work_stack
= VEC_alloc (int, heap
, n_basic_blocks
);
1316 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1318 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1319 VEC_quick_push here for speed. This is safe because we know that
1320 the number of definition blocks is no greater than the number of
1321 basic blocks, which is the initial capacity of WORK_STACK. */
1322 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1323 VEC_quick_push (int, work_stack
, bb_index
);
1325 /* Pop a block off the worklist, add every block that appears in
1326 the original block's DF that we have not already processed to
1327 the worklist. Iterate until the worklist is empty. Blocks
1328 which are added to the worklist are potential sites for
1330 while (VEC_length (int, work_stack
) > 0)
1332 bb_index
= VEC_pop (int, work_stack
);
1334 /* Since the registration of NEW -> OLD name mappings is done
1335 separately from the call to update_ssa, when updating the SSA
1336 form, the basic blocks where new and/or old names are defined
1337 may have disappeared by CFG cleanup calls. In this case,
1338 we may pull a non-existing block from the work stack. */
1339 gcc_assert (bb_index
< (unsigned) last_basic_block
);
1341 EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs
[bb_index
], phi_insertion_points
,
1344 /* Use a safe push because if there is a definition of VAR
1345 in every basic block, then WORK_STACK may eventually have
1346 more than N_BASIC_BLOCK entries. */
1347 VEC_safe_push (int, heap
, work_stack
, i
);
1348 bitmap_set_bit (phi_insertion_points
, i
);
1352 VEC_free (int, heap
, work_stack
);
1354 return phi_insertion_points
;