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, 2008, 2010
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains various simple utilities to analyze the CFG. */
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "insn-config.h"
33 #include "diagnostic-core.h"
42 /* Store the data structures necessary for depth-first search. */
43 struct depth_first_search_dsS
{
44 /* stack for backtracking during the algorithm */
47 /* number of edges in the stack. That is, positions 0, ..., sp-1
51 /* record of basic blocks already seen by depth-first search */
52 sbitmap visited_blocks
;
54 typedef struct depth_first_search_dsS
*depth_first_search_ds
;
56 static void flow_dfs_compute_reverse_init (depth_first_search_ds
);
57 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds
,
59 static basic_block
flow_dfs_compute_reverse_execute (depth_first_search_ds
,
61 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
);
62 static bool flow_active_insn_p (const_rtx
);
64 /* Like active_insn_p, except keep the return value clobber around
68 flow_active_insn_p (const_rtx insn
)
70 if (active_insn_p (insn
))
73 /* A clobber of the function return value exists for buggy
74 programs that fail to return a value. Its effect is to
75 keep the return value from being live across the entire
76 function. If we allow it to be skipped, we introduce the
77 possibility for register lifetime confusion. */
78 if (GET_CODE (PATTERN (insn
)) == CLOBBER
79 && REG_P (XEXP (PATTERN (insn
), 0))
80 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
86 /* Return true if the block has no effect and only forwards control flow to
87 its single destination. */
90 forwarder_block_p (const_basic_block bb
)
94 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
95 || !single_succ_p (bb
))
98 /* Protect loop latches, headers and preheaders. */
102 if (bb
->loop_father
->header
== bb
)
104 dest
= EDGE_SUCC (bb
, 0)->dest
;
105 if (dest
->loop_father
->header
== dest
)
109 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
110 if (INSN_P (insn
) && flow_active_insn_p (insn
))
113 return (!INSN_P (insn
)
114 || (JUMP_P (insn
) && simplejump_p (insn
))
115 || !flow_active_insn_p (insn
));
118 /* Return nonzero if we can reach target from src by falling through. */
121 can_fallthru (basic_block src
, basic_block target
)
123 rtx insn
= BB_END (src
);
128 if (target
== EXIT_BLOCK_PTR
)
130 if (src
->next_bb
!= target
)
132 FOR_EACH_EDGE (e
, ei
, src
->succs
)
133 if (e
->dest
== EXIT_BLOCK_PTR
134 && e
->flags
& EDGE_FALLTHRU
)
137 insn2
= BB_HEAD (target
);
138 if (insn2
&& !active_insn_p (insn2
))
139 insn2
= next_active_insn (insn2
);
141 /* ??? Later we may add code to move jump tables offline. */
142 return next_active_insn (insn
) == insn2
;
145 /* Return nonzero if we could reach target from src by falling through,
146 if the target was made adjacent. If we already have a fall-through
147 edge to the exit block, we can't do that. */
149 could_fall_through (basic_block src
, basic_block target
)
154 if (target
== EXIT_BLOCK_PTR
)
156 FOR_EACH_EDGE (e
, ei
, src
->succs
)
157 if (e
->dest
== EXIT_BLOCK_PTR
158 && e
->flags
& EDGE_FALLTHRU
)
163 /* Mark the back edges in DFS traversal.
164 Return nonzero if a loop (natural or otherwise) is present.
165 Inspired by Depth_First_Search_PP described in:
167 Advanced Compiler Design and Implementation
169 Morgan Kaufmann, 1997
171 and heavily borrowed from pre_and_rev_post_order_compute. */
174 mark_dfs_back_edges (void)
176 edge_iterator
*stack
;
185 /* Allocate the preorder and postorder number arrays. */
186 pre
= XCNEWVEC (int, last_basic_block
);
187 post
= XCNEWVEC (int, last_basic_block
);
189 /* Allocate stack for back-tracking up CFG. */
190 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
193 /* Allocate bitmap to track nodes that have been visited. */
194 visited
= sbitmap_alloc (last_basic_block
);
196 /* None of the nodes in the CFG have been visited yet. */
197 sbitmap_zero (visited
);
199 /* Push the first edge on to the stack. */
200 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
208 /* Look at the edge on the top of the stack. */
210 src
= ei_edge (ei
)->src
;
211 dest
= ei_edge (ei
)->dest
;
212 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
214 /* Check if the edge destination has been visited yet. */
215 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
217 /* Mark that we have visited the destination. */
218 SET_BIT (visited
, dest
->index
);
220 pre
[dest
->index
] = prenum
++;
221 if (EDGE_COUNT (dest
->succs
) > 0)
223 /* Since the DEST node has been visited for the first
224 time, check its successors. */
225 stack
[sp
++] = ei_start (dest
->succs
);
228 post
[dest
->index
] = postnum
++;
232 if (dest
!= EXIT_BLOCK_PTR
&& src
!= ENTRY_BLOCK_PTR
233 && pre
[src
->index
] >= pre
[dest
->index
]
234 && post
[dest
->index
] == 0)
235 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
237 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
238 post
[src
->index
] = postnum
++;
240 if (!ei_one_before_end_p (ei
))
241 ei_next (&stack
[sp
- 1]);
250 sbitmap_free (visited
);
255 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
258 set_edge_can_fallthru_flag (void)
267 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
269 e
->flags
&= ~EDGE_CAN_FALLTHRU
;
271 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
272 if (e
->flags
& EDGE_FALLTHRU
)
273 e
->flags
|= EDGE_CAN_FALLTHRU
;
276 /* If the BB ends with an invertible condjump all (2) edges are
277 CAN_FALLTHRU edges. */
278 if (EDGE_COUNT (bb
->succs
) != 2)
280 if (!any_condjump_p (BB_END (bb
)))
282 if (!invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0))
284 invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0);
285 EDGE_SUCC (bb
, 0)->flags
|= EDGE_CAN_FALLTHRU
;
286 EDGE_SUCC (bb
, 1)->flags
|= EDGE_CAN_FALLTHRU
;
290 /* Find unreachable blocks. An unreachable block will have 0 in
291 the reachable bit in block->flags. A nonzero value indicates the
292 block is reachable. */
295 find_unreachable_blocks (void)
299 basic_block
*tos
, *worklist
, bb
;
301 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
303 /* Clear all the reachability flags. */
306 bb
->flags
&= ~BB_REACHABLE
;
308 /* Add our starting points to the worklist. Almost always there will
309 be only one. It isn't inconceivable that we might one day directly
310 support Fortran alternate entry points. */
312 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
316 /* Mark the block reachable. */
317 e
->dest
->flags
|= BB_REACHABLE
;
320 /* Iterate: find everything reachable from what we've already seen. */
322 while (tos
!= worklist
)
324 basic_block b
= *--tos
;
326 FOR_EACH_EDGE (e
, ei
, b
->succs
)
328 basic_block dest
= e
->dest
;
330 if (!(dest
->flags
& BB_REACHABLE
))
333 dest
->flags
|= BB_REACHABLE
;
341 /* Functions to access an edge list with a vector representation.
342 Enough data is kept such that given an index number, the
343 pred and succ that edge represents can be determined, or
344 given a pred and a succ, its index number can be returned.
345 This allows algorithms which consume a lot of memory to
346 represent the normally full matrix of edge (pred,succ) with a
347 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
348 wasted space in the client code due to sparse flow graphs. */
350 /* This functions initializes the edge list. Basically the entire
351 flowgraph is processed, and all edges are assigned a number,
352 and the data structure is filled in. */
355 create_edge_list (void)
357 struct edge_list
*elist
;
364 block_count
= n_basic_blocks
; /* Include the entry and exit blocks. */
368 /* Determine the number of edges in the flow graph by counting successor
369 edges on each basic block. */
370 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
372 num_edges
+= EDGE_COUNT (bb
->succs
);
375 elist
= XNEW (struct edge_list
);
376 elist
->num_blocks
= block_count
;
377 elist
->num_edges
= num_edges
;
378 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
382 /* Follow successors of blocks, and register these edges. */
383 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
384 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
385 elist
->index_to_edge
[num_edges
++] = e
;
390 /* This function free's memory associated with an edge list. */
393 free_edge_list (struct edge_list
*elist
)
397 free (elist
->index_to_edge
);
402 /* This function provides debug output showing an edge list. */
405 print_edge_list (FILE *f
, struct edge_list
*elist
)
409 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
410 elist
->num_blocks
, elist
->num_edges
);
412 for (x
= 0; x
< elist
->num_edges
; x
++)
414 fprintf (f
, " %-4d - edge(", x
);
415 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR
)
416 fprintf (f
, "entry,");
418 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
420 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR
)
421 fprintf (f
, "exit)\n");
423 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
427 /* This function provides an internal consistency check of an edge list,
428 verifying that all edges are present, and that there are no
432 verify_edge_list (FILE *f
, struct edge_list
*elist
)
434 int pred
, succ
, index
;
436 basic_block bb
, p
, s
;
439 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
443 pred
= e
->src
->index
;
444 succ
= e
->dest
->index
;
445 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
446 if (index
== EDGE_INDEX_NO_EDGE
)
448 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
452 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
453 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
454 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
455 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
456 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
457 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
461 /* We've verified that all the edges are in the list, now lets make sure
462 there are no spurious edges in the list. */
464 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
465 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
469 FOR_EACH_EDGE (e
, ei
, p
->succs
)
476 FOR_EACH_EDGE (e
, ei
, s
->preds
)
483 if (EDGE_INDEX (elist
, p
, s
)
484 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
485 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
487 if (EDGE_INDEX (elist
, p
, s
)
488 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
489 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
490 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
494 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
495 If no such edge exists, return NULL. */
498 find_edge (basic_block pred
, basic_block succ
)
503 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
505 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
511 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
519 /* This routine will determine what, if any, edge there is between
520 a specified predecessor and successor. */
523 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
527 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
528 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
529 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
532 return (EDGE_INDEX_NO_EDGE
);
535 /* Dump the list of basic blocks in the bitmap NODES. */
538 flow_nodes_print (const char *str
, const_sbitmap nodes
, FILE *file
)
540 unsigned int node
= 0;
541 sbitmap_iterator sbi
;
546 fprintf (file
, "%s { ", str
);
547 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, sbi
)
548 fprintf (file
, "%d ", node
);
552 /* Dump the list of edges in the array EDGE_LIST. */
555 flow_edge_list_print (const char *str
, const edge
*edge_list
, int num_edges
, FILE *file
)
562 fprintf (file
, "%s { ", str
);
563 for (i
= 0; i
< num_edges
; i
++)
564 fprintf (file
, "%d->%d ", edge_list
[i
]->src
->index
,
565 edge_list
[i
]->dest
->index
);
571 /* This routine will remove any fake predecessor edges for a basic block.
572 When the edge is removed, it is also removed from whatever successor
576 remove_fake_predecessors (basic_block bb
)
581 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
583 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
590 /* This routine will remove all fake edges from the flow graph. If
591 we remove all fake successors, it will automatically remove all
592 fake predecessors. */
595 remove_fake_edges (void)
599 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
600 remove_fake_predecessors (bb
);
603 /* This routine will remove all fake edges to the EXIT_BLOCK. */
606 remove_fake_exit_edges (void)
608 remove_fake_predecessors (EXIT_BLOCK_PTR
);
612 /* This function will add a fake edge between any block which has no
613 successors, and the exit block. Some data flow equations require these
617 add_noreturn_fake_exit_edges (void)
622 if (EDGE_COUNT (bb
->succs
) == 0)
623 make_single_succ_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
626 /* This function adds a fake edge between any infinite loops to the
627 exit block. Some optimizations require a path from each node to
630 See also Morgan, Figure 3.10, pp. 82-83.
632 The current implementation is ugly, not attempting to minimize the
633 number of inserted fake edges. To reduce the number of fake edges
634 to insert, add fake edges from _innermost_ loops containing only
635 nodes not reachable from the exit block. */
638 connect_infinite_loops_to_exit (void)
640 basic_block unvisited_block
= EXIT_BLOCK_PTR
;
641 struct depth_first_search_dsS dfs_ds
;
643 /* Perform depth-first search in the reverse graph to find nodes
644 reachable from the exit block. */
645 flow_dfs_compute_reverse_init (&dfs_ds
);
646 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR
);
648 /* Repeatedly add fake edges, updating the unreachable nodes. */
651 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
653 if (!unvisited_block
)
656 make_edge (unvisited_block
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
657 flow_dfs_compute_reverse_add_bb (&dfs_ds
, unvisited_block
);
660 flow_dfs_compute_reverse_finish (&dfs_ds
);
664 /* Compute reverse top sort order. This is computing a post order
665 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
666 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
667 true, unreachable blocks are deleted. */
670 post_order_compute (int *post_order
, bool include_entry_exit
,
671 bool delete_unreachable
)
673 edge_iterator
*stack
;
675 int post_order_num
= 0;
679 if (include_entry_exit
)
680 post_order
[post_order_num
++] = EXIT_BLOCK
;
682 /* Allocate stack for back-tracking up CFG. */
683 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
686 /* Allocate bitmap to track nodes that have been visited. */
687 visited
= sbitmap_alloc (last_basic_block
);
689 /* None of the nodes in the CFG have been visited yet. */
690 sbitmap_zero (visited
);
692 /* Push the first edge on to the stack. */
693 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
701 /* Look at the edge on the top of the stack. */
703 src
= ei_edge (ei
)->src
;
704 dest
= ei_edge (ei
)->dest
;
706 /* Check if the edge destination has been visited yet. */
707 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
709 /* Mark that we have visited the destination. */
710 SET_BIT (visited
, dest
->index
);
712 if (EDGE_COUNT (dest
->succs
) > 0)
713 /* Since the DEST node has been visited for the first
714 time, check its successors. */
715 stack
[sp
++] = ei_start (dest
->succs
);
717 post_order
[post_order_num
++] = dest
->index
;
721 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
722 post_order
[post_order_num
++] = src
->index
;
724 if (!ei_one_before_end_p (ei
))
725 ei_next (&stack
[sp
- 1]);
731 if (include_entry_exit
)
733 post_order
[post_order_num
++] = ENTRY_BLOCK
;
734 count
= post_order_num
;
737 count
= post_order_num
+ 2;
739 /* Delete the unreachable blocks if some were found and we are
740 supposed to do it. */
741 if (delete_unreachable
&& (count
!= n_basic_blocks
))
745 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
747 next_bb
= b
->next_bb
;
749 if (!(TEST_BIT (visited
, b
->index
)))
750 delete_basic_block (b
);
753 tidy_fallthru_edges ();
757 sbitmap_free (visited
);
758 return post_order_num
;
762 /* Helper routine for inverted_post_order_compute.
763 BB has to belong to a region of CFG
764 unreachable by inverted traversal from the exit.
765 i.e. there's no control flow path from ENTRY to EXIT
766 that contains this BB.
767 This can happen in two cases - if there's an infinite loop
768 or if there's a block that has no successor
769 (call to a function with no return).
770 Some RTL passes deal with this condition by
771 calling connect_infinite_loops_to_exit () and/or
772 add_noreturn_fake_exit_edges ().
773 However, those methods involve modifying the CFG itself
774 which may not be desirable.
775 Hence, we deal with the infinite loop/no return cases
776 by identifying a unique basic block that can reach all blocks
777 in such a region by inverted traversal.
778 This function returns a basic block that guarantees
779 that all blocks in the region are reachable
780 by starting an inverted traversal from the returned block. */
783 dfs_find_deadend (basic_block bb
)
785 sbitmap visited
= sbitmap_alloc (last_basic_block
);
786 sbitmap_zero (visited
);
790 SET_BIT (visited
, bb
->index
);
791 if (EDGE_COUNT (bb
->succs
) == 0
792 || TEST_BIT (visited
, EDGE_SUCC (bb
, 0)->dest
->index
))
794 sbitmap_free (visited
);
798 bb
= EDGE_SUCC (bb
, 0)->dest
;
805 /* Compute the reverse top sort order of the inverted CFG
806 i.e. starting from the exit block and following the edges backward
807 (from successors to predecessors).
808 This ordering can be used for forward dataflow problems among others.
810 This function assumes that all blocks in the CFG are reachable
811 from the ENTRY (but not necessarily from EXIT).
813 If there's an infinite loop,
814 a simple inverted traversal starting from the blocks
815 with no successors can't visit all blocks.
816 To solve this problem, we first do inverted traversal
817 starting from the blocks with no successor.
818 And if there's any block left that's not visited by the regular
819 inverted traversal from EXIT,
820 those blocks are in such problematic region.
821 Among those, we find one block that has
822 any visited predecessor (which is an entry into such a region),
823 and start looking for a "dead end" from that block
824 and do another inverted traversal from that block. */
827 inverted_post_order_compute (int *post_order
)
830 edge_iterator
*stack
;
832 int post_order_num
= 0;
835 /* Allocate stack for back-tracking up CFG. */
836 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
839 /* Allocate bitmap to track nodes that have been visited. */
840 visited
= sbitmap_alloc (last_basic_block
);
842 /* None of the nodes in the CFG have been visited yet. */
843 sbitmap_zero (visited
);
845 /* Put all blocks that have no successor into the initial work list. */
846 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
847 if (EDGE_COUNT (bb
->succs
) == 0)
849 /* Push the initial edge on to the stack. */
850 if (EDGE_COUNT (bb
->preds
) > 0)
852 stack
[sp
++] = ei_start (bb
->preds
);
853 SET_BIT (visited
, bb
->index
);
859 bool has_unvisited_bb
= false;
861 /* The inverted traversal loop. */
867 /* Look at the edge on the top of the stack. */
869 bb
= ei_edge (ei
)->dest
;
870 pred
= ei_edge (ei
)->src
;
872 /* Check if the predecessor has been visited yet. */
873 if (! TEST_BIT (visited
, pred
->index
))
875 /* Mark that we have visited the destination. */
876 SET_BIT (visited
, pred
->index
);
878 if (EDGE_COUNT (pred
->preds
) > 0)
879 /* Since the predecessor node has been visited for the first
880 time, check its predecessors. */
881 stack
[sp
++] = ei_start (pred
->preds
);
883 post_order
[post_order_num
++] = pred
->index
;
887 if (bb
!= EXIT_BLOCK_PTR
&& ei_one_before_end_p (ei
))
888 post_order
[post_order_num
++] = bb
->index
;
890 if (!ei_one_before_end_p (ei
))
891 ei_next (&stack
[sp
- 1]);
897 /* Detect any infinite loop and activate the kludge.
898 Note that this doesn't check EXIT_BLOCK itself
899 since EXIT_BLOCK is always added after the outer do-while loop. */
900 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
901 if (!TEST_BIT (visited
, bb
->index
))
903 has_unvisited_bb
= true;
905 if (EDGE_COUNT (bb
->preds
) > 0)
909 basic_block visited_pred
= NULL
;
911 /* Find an already visited predecessor. */
912 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
914 if (TEST_BIT (visited
, e
->src
->index
))
915 visited_pred
= e
->src
;
920 basic_block be
= dfs_find_deadend (bb
);
921 gcc_assert (be
!= NULL
);
922 SET_BIT (visited
, be
->index
);
923 stack
[sp
++] = ei_start (be
->preds
);
929 if (has_unvisited_bb
&& sp
== 0)
931 /* No blocks are reachable from EXIT at all.
932 Find a dead-end from the ENTRY, and restart the iteration. */
933 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR
);
934 gcc_assert (be
!= NULL
);
935 SET_BIT (visited
, be
->index
);
936 stack
[sp
++] = ei_start (be
->preds
);
939 /* The only case the below while fires is
940 when there's an infinite loop. */
944 /* EXIT_BLOCK is always included. */
945 post_order
[post_order_num
++] = EXIT_BLOCK
;
948 sbitmap_free (visited
);
949 return post_order_num
;
952 /* Compute the depth first search order and store in the array
953 PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
954 REV_POST_ORDER is nonzero, return the reverse completion number for each
955 node. Returns the number of nodes visited. A depth first search
956 tries to get as far away from the starting point as quickly as
959 pre_order is a really a preorder numbering of the graph.
960 rev_post_order is really a reverse postorder numbering of the graph.
964 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
965 bool include_entry_exit
)
967 edge_iterator
*stack
;
969 int pre_order_num
= 0;
970 int rev_post_order_num
= n_basic_blocks
- 1;
973 /* Allocate stack for back-tracking up CFG. */
974 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
977 if (include_entry_exit
)
980 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
983 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
986 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
988 /* Allocate bitmap to track nodes that have been visited. */
989 visited
= sbitmap_alloc (last_basic_block
);
991 /* None of the nodes in the CFG have been visited yet. */
992 sbitmap_zero (visited
);
994 /* Push the first edge on to the stack. */
995 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
1003 /* Look at the edge on the top of the stack. */
1005 src
= ei_edge (ei
)->src
;
1006 dest
= ei_edge (ei
)->dest
;
1008 /* Check if the edge destination has been visited yet. */
1009 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
))
1011 /* Mark that we have visited the destination. */
1012 SET_BIT (visited
, dest
->index
);
1015 pre_order
[pre_order_num
] = dest
->index
;
1019 if (EDGE_COUNT (dest
->succs
) > 0)
1020 /* Since the DEST node has been visited for the first
1021 time, check its successors. */
1022 stack
[sp
++] = ei_start (dest
->succs
);
1023 else if (rev_post_order
)
1024 /* There are no successors for the DEST node so assign
1025 its reverse completion number. */
1026 rev_post_order
[rev_post_order_num
--] = dest
->index
;
1030 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
1032 /* There are no more successors for the SRC node
1033 so assign its reverse completion number. */
1034 rev_post_order
[rev_post_order_num
--] = src
->index
;
1036 if (!ei_one_before_end_p (ei
))
1037 ei_next (&stack
[sp
- 1]);
1044 sbitmap_free (visited
);
1046 if (include_entry_exit
)
1049 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1052 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
1053 /* The number of nodes visited should be the number of blocks. */
1054 gcc_assert (pre_order_num
== n_basic_blocks
);
1057 /* The number of nodes visited should be the number of blocks minus
1058 the entry and exit blocks which are not visited here. */
1059 gcc_assert (pre_order_num
== n_basic_blocks
- NUM_FIXED_BLOCKS
);
1061 return pre_order_num
;
1064 /* Compute the depth first search order on the _reverse_ graph and
1065 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1066 Returns the number of nodes visited.
1068 The computation is split into three pieces:
1070 flow_dfs_compute_reverse_init () creates the necessary data
1073 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1074 structures. The block will start the search.
1076 flow_dfs_compute_reverse_execute () continues (or starts) the
1077 search using the block on the top of the stack, stopping when the
1080 flow_dfs_compute_reverse_finish () destroys the necessary data
1083 Thus, the user will probably call ..._init(), call ..._add_bb() to
1084 add a beginning basic block to the stack, call ..._execute(),
1085 possibly add another bb to the stack and again call ..._execute(),
1086 ..., and finally call _finish(). */
1088 /* Initialize the data structures used for depth-first search on the
1089 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1090 added to the basic block stack. DATA is the current depth-first
1091 search context. If INITIALIZE_STACK is nonzero, there is an
1092 element on the stack. */
1095 flow_dfs_compute_reverse_init (depth_first_search_ds data
)
1097 /* Allocate stack for back-tracking up CFG. */
1098 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks
);
1101 /* Allocate bitmap to track nodes that have been visited. */
1102 data
->visited_blocks
= sbitmap_alloc (last_basic_block
);
1104 /* None of the nodes in the CFG have been visited yet. */
1105 sbitmap_zero (data
->visited_blocks
);
1110 /* Add the specified basic block to the top of the dfs data
1111 structures. When the search continues, it will start at the
1115 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data
, basic_block bb
)
1117 data
->stack
[data
->sp
++] = bb
;
1118 SET_BIT (data
->visited_blocks
, bb
->index
);
1121 /* Continue the depth-first search through the reverse graph starting with the
1122 block at the stack's top and ending when the stack is empty. Visited nodes
1123 are marked. Returns an unvisited basic block, or NULL if there is none
1127 flow_dfs_compute_reverse_execute (depth_first_search_ds data
,
1128 basic_block last_unvisited
)
1134 while (data
->sp
> 0)
1136 bb
= data
->stack
[--data
->sp
];
1138 /* Perform depth-first search on adjacent vertices. */
1139 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1140 if (!TEST_BIT (data
->visited_blocks
, e
->src
->index
))
1141 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1144 /* Determine if there are unvisited basic blocks. */
1145 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1146 if (!TEST_BIT (data
->visited_blocks
, bb
->index
))
1152 /* Destroy the data structures needed for depth-first search on the
1156 flow_dfs_compute_reverse_finish (depth_first_search_ds data
)
1159 sbitmap_free (data
->visited_blocks
);
1162 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1163 if REVERSE, go against direction of edges. Returns number of blocks
1164 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1166 dfs_enumerate_from (basic_block bb
, int reverse
,
1167 bool (*predicate
) (const_basic_block
, const void *),
1168 basic_block
*rslt
, int rslt_max
, const void *data
)
1170 basic_block
*st
, lbb
;
1174 /* A bitmap to keep track of visited blocks. Allocating it each time
1175 this function is called is not possible, since dfs_enumerate_from
1176 is often used on small (almost) disjoint parts of cfg (bodies of
1177 loops), and allocating a large sbitmap would lead to quadratic
1179 static sbitmap visited
;
1180 static unsigned v_size
;
1182 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
1183 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
1184 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
1186 /* Resize the VISITED sbitmap if necessary. */
1187 size
= last_basic_block
;
1194 visited
= sbitmap_alloc (size
);
1195 sbitmap_zero (visited
);
1198 else if (v_size
< size
)
1200 /* Ensure that we increase the size of the sbitmap exponentially. */
1201 if (2 * v_size
> size
)
1204 visited
= sbitmap_resize (visited
, size
, 0);
1208 st
= XCNEWVEC (basic_block
, rslt_max
);
1209 rslt
[tv
++] = st
[sp
++] = bb
;
1218 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1219 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1221 gcc_assert (tv
!= rslt_max
);
1222 rslt
[tv
++] = st
[sp
++] = e
->src
;
1223 MARK_VISITED (e
->src
);
1228 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1229 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1231 gcc_assert (tv
!= rslt_max
);
1232 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1233 MARK_VISITED (e
->dest
);
1238 for (sp
= 0; sp
< tv
; sp
++)
1239 UNMARK_VISITED (rslt
[sp
]);
1242 #undef UNMARK_VISITED
1247 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1249 This algorithm can be found in Timothy Harvey's PhD thesis, at
1250 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1251 dominance algorithms.
1253 First, we identify each join point, j (any node with more than one
1254 incoming edge is a join point).
1256 We then examine each predecessor, p, of j and walk up the dominator tree
1259 We stop the walk when we reach j's immediate dominator - j is in the
1260 dominance frontier of each of the nodes in the walk, except for j's
1261 immediate dominator. Intuitively, all of the rest of j's dominators are
1262 shared by j's predecessors as well.
1263 Since they dominate j, they will not have j in their dominance frontiers.
1265 The number of nodes touched by this algorithm is equal to the size
1266 of the dominance frontiers, no more, no less.
1271 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1278 if (EDGE_COUNT (b
->preds
) >= 2)
1280 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1282 basic_block runner
= p
->src
;
1284 if (runner
== ENTRY_BLOCK_PTR
)
1287 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1288 while (runner
!= domsb
)
1290 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1293 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1303 compute_dominance_frontiers (bitmap_head
*frontiers
)
1305 timevar_push (TV_DOM_FRONTIERS
);
1307 compute_dominance_frontiers_1 (frontiers
);
1309 timevar_pop (TV_DOM_FRONTIERS
);
1312 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1313 return a bitmap with all the blocks in the iterated dominance
1314 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1315 frontier information as returned by compute_dominance_frontiers.
1317 The resulting set of blocks are the potential sites where PHI nodes
1318 are needed. The caller is responsible for freeing the memory
1319 allocated for the return value. */
1322 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1325 unsigned bb_index
, i
;
1326 VEC(int,heap
) *work_stack
;
1327 bitmap phi_insertion_points
;
1329 work_stack
= VEC_alloc (int, heap
, n_basic_blocks
);
1330 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1332 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1333 VEC_quick_push here for speed. This is safe because we know that
1334 the number of definition blocks is no greater than the number of
1335 basic blocks, which is the initial capacity of WORK_STACK. */
1336 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1337 VEC_quick_push (int, work_stack
, bb_index
);
1339 /* Pop a block off the worklist, add every block that appears in
1340 the original block's DF that we have not already processed to
1341 the worklist. Iterate until the worklist is empty. Blocks
1342 which are added to the worklist are potential sites for
1344 while (VEC_length (int, work_stack
) > 0)
1346 bb_index
= VEC_pop (int, work_stack
);
1348 /* Since the registration of NEW -> OLD name mappings is done
1349 separately from the call to update_ssa, when updating the SSA
1350 form, the basic blocks where new and/or old names are defined
1351 may have disappeared by CFG cleanup calls. In this case,
1352 we may pull a non-existing block from the work stack. */
1353 gcc_assert (bb_index
< (unsigned) last_basic_block
);
1355 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1358 /* Use a safe push because if there is a definition of VAR
1359 in every basic block, then WORK_STACK may eventually have
1360 more than N_BASIC_BLOCK entries. */
1361 VEC_safe_push (int, heap
, work_stack
, i
);
1362 bitmap_set_bit (phi_insertion_points
, i
);
1366 VEC_free (int, heap
, work_stack
);
1368 return phi_insertion_points
;