1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2012 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains various simple utilities to analyze the CFG. */
24 #include "coretypes.h"
25 #include "basic-block.h"
32 /* Store the data structures necessary for depth-first search. */
33 struct depth_first_search_dsS
{
34 /* stack for backtracking during the algorithm */
37 /* number of edges in the stack. That is, positions 0, ..., sp-1
41 /* record of basic blocks already seen by depth-first search */
42 sbitmap visited_blocks
;
44 typedef struct depth_first_search_dsS
*depth_first_search_ds
;
46 static void flow_dfs_compute_reverse_init (depth_first_search_ds
);
47 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds
,
49 static basic_block
flow_dfs_compute_reverse_execute (depth_first_search_ds
,
51 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
);
53 /* Mark the back edges in DFS traversal.
54 Return nonzero if a loop (natural or otherwise) is present.
55 Inspired by Depth_First_Search_PP described in:
57 Advanced Compiler Design and Implementation
61 and heavily borrowed from pre_and_rev_post_order_compute. */
64 mark_dfs_back_edges (void)
75 /* Allocate the preorder and postorder number arrays. */
76 pre
= XCNEWVEC (int, last_basic_block
);
77 post
= XCNEWVEC (int, last_basic_block
);
79 /* Allocate stack for back-tracking up CFG. */
80 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
83 /* Allocate bitmap to track nodes that have been visited. */
84 visited
= sbitmap_alloc (last_basic_block
);
86 /* None of the nodes in the CFG have been visited yet. */
87 bitmap_clear (visited
);
89 /* Push the first edge on to the stack. */
90 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
98 /* Look at the edge on the top of the stack. */
100 src
= ei_edge (ei
)->src
;
101 dest
= ei_edge (ei
)->dest
;
102 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
104 /* Check if the edge destination has been visited yet. */
105 if (dest
!= EXIT_BLOCK_PTR
&& ! bitmap_bit_p (visited
, dest
->index
))
107 /* Mark that we have visited the destination. */
108 bitmap_set_bit (visited
, dest
->index
);
110 pre
[dest
->index
] = prenum
++;
111 if (EDGE_COUNT (dest
->succs
) > 0)
113 /* Since the DEST node has been visited for the first
114 time, check its successors. */
115 stack
[sp
++] = ei_start (dest
->succs
);
118 post
[dest
->index
] = postnum
++;
122 if (dest
!= EXIT_BLOCK_PTR
&& src
!= ENTRY_BLOCK_PTR
123 && pre
[src
->index
] >= pre
[dest
->index
]
124 && post
[dest
->index
] == 0)
125 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
127 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
128 post
[src
->index
] = postnum
++;
130 if (!ei_one_before_end_p (ei
))
131 ei_next (&stack
[sp
- 1]);
140 sbitmap_free (visited
);
145 /* Find unreachable blocks. An unreachable block will have 0 in
146 the reachable bit in block->flags. A nonzero value indicates the
147 block is reachable. */
150 find_unreachable_blocks (void)
154 basic_block
*tos
, *worklist
, bb
;
156 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
158 /* Clear all the reachability flags. */
161 bb
->flags
&= ~BB_REACHABLE
;
163 /* Add our starting points to the worklist. Almost always there will
164 be only one. It isn't inconceivable that we might one day directly
165 support Fortran alternate entry points. */
167 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
171 /* Mark the block reachable. */
172 e
->dest
->flags
|= BB_REACHABLE
;
175 /* Iterate: find everything reachable from what we've already seen. */
177 while (tos
!= worklist
)
179 basic_block b
= *--tos
;
181 FOR_EACH_EDGE (e
, ei
, b
->succs
)
183 basic_block dest
= e
->dest
;
185 if (!(dest
->flags
& BB_REACHABLE
))
188 dest
->flags
|= BB_REACHABLE
;
196 /* Functions to access an edge list with a vector representation.
197 Enough data is kept such that given an index number, the
198 pred and succ that edge represents can be determined, or
199 given a pred and a succ, its index number can be returned.
200 This allows algorithms which consume a lot of memory to
201 represent the normally full matrix of edge (pred,succ) with a
202 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
203 wasted space in the client code due to sparse flow graphs. */
205 /* This functions initializes the edge list. Basically the entire
206 flowgraph is processed, and all edges are assigned a number,
207 and the data structure is filled in. */
210 create_edge_list (void)
212 struct edge_list
*elist
;
218 /* Determine the number of edges in the flow graph by counting successor
219 edges on each basic block. */
221 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
223 num_edges
+= EDGE_COUNT (bb
->succs
);
226 elist
= XNEW (struct edge_list
);
227 elist
->num_edges
= num_edges
;
228 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
232 /* Follow successors of blocks, and register these edges. */
233 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
234 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
235 elist
->index_to_edge
[num_edges
++] = e
;
240 /* This function free's memory associated with an edge list. */
243 free_edge_list (struct edge_list
*elist
)
247 free (elist
->index_to_edge
);
252 /* This function provides debug output showing an edge list. */
255 print_edge_list (FILE *f
, struct edge_list
*elist
)
259 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
260 n_basic_blocks
, elist
->num_edges
);
262 for (x
= 0; x
< elist
->num_edges
; x
++)
264 fprintf (f
, " %-4d - edge(", x
);
265 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR
)
266 fprintf (f
, "entry,");
268 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
270 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR
)
271 fprintf (f
, "exit)\n");
273 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
277 /* This function provides an internal consistency check of an edge list,
278 verifying that all edges are present, and that there are no
282 verify_edge_list (FILE *f
, struct edge_list
*elist
)
284 int pred
, succ
, index
;
286 basic_block bb
, p
, s
;
289 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
291 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
293 pred
= e
->src
->index
;
294 succ
= e
->dest
->index
;
295 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
296 if (index
== EDGE_INDEX_NO_EDGE
)
298 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
302 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
303 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
304 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
305 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
306 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
307 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
311 /* We've verified that all the edges are in the list, now lets make sure
312 there are no spurious edges in the list. This is an expensive check! */
314 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
315 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
319 FOR_EACH_EDGE (e
, ei
, p
->succs
)
326 FOR_EACH_EDGE (e
, ei
, s
->preds
)
333 if (EDGE_INDEX (elist
, p
, s
)
334 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
335 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
337 if (EDGE_INDEX (elist
, p
, s
)
338 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
339 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
340 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
344 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
345 If no such edge exists, return NULL. */
348 find_edge (basic_block pred
, basic_block succ
)
353 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
355 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
361 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
369 /* This routine will determine what, if any, edge there is between
370 a specified predecessor and successor. */
373 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
377 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
378 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
379 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
382 return (EDGE_INDEX_NO_EDGE
);
385 /* This routine will remove any fake predecessor edges for a basic block.
386 When the edge is removed, it is also removed from whatever successor
390 remove_fake_predecessors (basic_block bb
)
395 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
397 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
404 /* This routine will remove all fake edges from the flow graph. If
405 we remove all fake successors, it will automatically remove all
406 fake predecessors. */
409 remove_fake_edges (void)
413 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
414 remove_fake_predecessors (bb
);
417 /* This routine will remove all fake edges to the EXIT_BLOCK. */
420 remove_fake_exit_edges (void)
422 remove_fake_predecessors (EXIT_BLOCK_PTR
);
426 /* This function will add a fake edge between any block which has no
427 successors, and the exit block. Some data flow equations require these
431 add_noreturn_fake_exit_edges (void)
436 if (EDGE_COUNT (bb
->succs
) == 0)
437 make_single_succ_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
440 /* This function adds a fake edge between any infinite loops to the
441 exit block. Some optimizations require a path from each node to
444 See also Morgan, Figure 3.10, pp. 82-83.
446 The current implementation is ugly, not attempting to minimize the
447 number of inserted fake edges. To reduce the number of fake edges
448 to insert, add fake edges from _innermost_ loops containing only
449 nodes not reachable from the exit block. */
452 connect_infinite_loops_to_exit (void)
454 basic_block unvisited_block
= EXIT_BLOCK_PTR
;
455 basic_block deadend_block
;
456 struct depth_first_search_dsS dfs_ds
;
458 /* Perform depth-first search in the reverse graph to find nodes
459 reachable from the exit block. */
460 flow_dfs_compute_reverse_init (&dfs_ds
);
461 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR
);
463 /* Repeatedly add fake edges, updating the unreachable nodes. */
466 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
468 if (!unvisited_block
)
471 deadend_block
= dfs_find_deadend (unvisited_block
);
472 make_edge (deadend_block
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
473 flow_dfs_compute_reverse_add_bb (&dfs_ds
, deadend_block
);
476 flow_dfs_compute_reverse_finish (&dfs_ds
);
480 /* Compute reverse top sort order. This is computing a post order
481 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
482 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
483 true, unreachable blocks are deleted. */
486 post_order_compute (int *post_order
, bool include_entry_exit
,
487 bool delete_unreachable
)
489 edge_iterator
*stack
;
491 int post_order_num
= 0;
495 if (include_entry_exit
)
496 post_order
[post_order_num
++] = EXIT_BLOCK
;
498 /* Allocate stack for back-tracking up CFG. */
499 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
502 /* Allocate bitmap to track nodes that have been visited. */
503 visited
= sbitmap_alloc (last_basic_block
);
505 /* None of the nodes in the CFG have been visited yet. */
506 bitmap_clear (visited
);
508 /* Push the first edge on to the stack. */
509 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
517 /* Look at the edge on the top of the stack. */
519 src
= ei_edge (ei
)->src
;
520 dest
= ei_edge (ei
)->dest
;
522 /* Check if the edge destination has been visited yet. */
523 if (dest
!= EXIT_BLOCK_PTR
&& ! bitmap_bit_p (visited
, dest
->index
))
525 /* Mark that we have visited the destination. */
526 bitmap_set_bit (visited
, dest
->index
);
528 if (EDGE_COUNT (dest
->succs
) > 0)
529 /* Since the DEST node has been visited for the first
530 time, check its successors. */
531 stack
[sp
++] = ei_start (dest
->succs
);
533 post_order
[post_order_num
++] = dest
->index
;
537 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
538 post_order
[post_order_num
++] = src
->index
;
540 if (!ei_one_before_end_p (ei
))
541 ei_next (&stack
[sp
- 1]);
547 if (include_entry_exit
)
549 post_order
[post_order_num
++] = ENTRY_BLOCK
;
550 count
= post_order_num
;
553 count
= post_order_num
+ 2;
555 /* Delete the unreachable blocks if some were found and we are
556 supposed to do it. */
557 if (delete_unreachable
&& (count
!= n_basic_blocks
))
561 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
563 next_bb
= b
->next_bb
;
565 if (!(bitmap_bit_p (visited
, b
->index
)))
566 delete_basic_block (b
);
569 tidy_fallthru_edges ();
573 sbitmap_free (visited
);
574 return post_order_num
;
578 /* Helper routine for inverted_post_order_compute
579 flow_dfs_compute_reverse_execute, and the reverse-CFG
580 deapth first search in dominance.c.
581 BB has to belong to a region of CFG
582 unreachable by inverted traversal from the exit.
583 i.e. there's no control flow path from ENTRY to EXIT
584 that contains this BB.
585 This can happen in two cases - if there's an infinite loop
586 or if there's a block that has no successor
587 (call to a function with no return).
588 Some RTL passes deal with this condition by
589 calling connect_infinite_loops_to_exit () and/or
590 add_noreturn_fake_exit_edges ().
591 However, those methods involve modifying the CFG itself
592 which may not be desirable.
593 Hence, we deal with the infinite loop/no return cases
594 by identifying a unique basic block that can reach all blocks
595 in such a region by inverted traversal.
596 This function returns a basic block that guarantees
597 that all blocks in the region are reachable
598 by starting an inverted traversal from the returned block. */
601 dfs_find_deadend (basic_block bb
)
603 bitmap visited
= BITMAP_ALLOC (NULL
);
607 if (EDGE_COUNT (bb
->succs
) == 0
608 || ! bitmap_set_bit (visited
, bb
->index
))
610 BITMAP_FREE (visited
);
614 bb
= EDGE_SUCC (bb
, 0)->dest
;
621 /* Compute the reverse top sort order of the inverted CFG
622 i.e. starting from the exit block and following the edges backward
623 (from successors to predecessors).
624 This ordering can be used for forward dataflow problems among others.
626 This function assumes that all blocks in the CFG are reachable
627 from the ENTRY (but not necessarily from EXIT).
629 If there's an infinite loop,
630 a simple inverted traversal starting from the blocks
631 with no successors can't visit all blocks.
632 To solve this problem, we first do inverted traversal
633 starting from the blocks with no successor.
634 And if there's any block left that's not visited by the regular
635 inverted traversal from EXIT,
636 those blocks are in such problematic region.
637 Among those, we find one block that has
638 any visited predecessor (which is an entry into such a region),
639 and start looking for a "dead end" from that block
640 and do another inverted traversal from that block. */
643 inverted_post_order_compute (int *post_order
)
646 edge_iterator
*stack
;
648 int post_order_num
= 0;
651 /* Allocate stack for back-tracking up CFG. */
652 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
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 bitmap_clear (visited
);
661 /* Put all blocks that have no successor into the initial work list. */
663 if (EDGE_COUNT (bb
->succs
) == 0)
665 /* Push the initial edge on to the stack. */
666 if (EDGE_COUNT (bb
->preds
) > 0)
668 stack
[sp
++] = ei_start (bb
->preds
);
669 bitmap_set_bit (visited
, bb
->index
);
675 bool has_unvisited_bb
= false;
677 /* The inverted traversal loop. */
683 /* Look at the edge on the top of the stack. */
685 bb
= ei_edge (ei
)->dest
;
686 pred
= ei_edge (ei
)->src
;
688 /* Check if the predecessor has been visited yet. */
689 if (! bitmap_bit_p (visited
, pred
->index
))
691 /* Mark that we have visited the destination. */
692 bitmap_set_bit (visited
, pred
->index
);
694 if (EDGE_COUNT (pred
->preds
) > 0)
695 /* Since the predecessor node has been visited for the first
696 time, check its predecessors. */
697 stack
[sp
++] = ei_start (pred
->preds
);
699 post_order
[post_order_num
++] = pred
->index
;
703 if (bb
!= EXIT_BLOCK_PTR
&& ei_one_before_end_p (ei
))
704 post_order
[post_order_num
++] = bb
->index
;
706 if (!ei_one_before_end_p (ei
))
707 ei_next (&stack
[sp
- 1]);
713 /* Detect any infinite loop and activate the kludge.
714 Note that this doesn't check EXIT_BLOCK itself
715 since EXIT_BLOCK is always added after the outer do-while loop. */
716 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
717 if (!bitmap_bit_p (visited
, bb
->index
))
719 has_unvisited_bb
= true;
721 if (EDGE_COUNT (bb
->preds
) > 0)
725 basic_block visited_pred
= NULL
;
727 /* Find an already visited predecessor. */
728 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
730 if (bitmap_bit_p (visited
, e
->src
->index
))
731 visited_pred
= e
->src
;
736 basic_block be
= dfs_find_deadend (bb
);
737 gcc_assert (be
!= NULL
);
738 bitmap_set_bit (visited
, be
->index
);
739 stack
[sp
++] = ei_start (be
->preds
);
745 if (has_unvisited_bb
&& sp
== 0)
747 /* No blocks are reachable from EXIT at all.
748 Find a dead-end from the ENTRY, and restart the iteration. */
749 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR
);
750 gcc_assert (be
!= NULL
);
751 bitmap_set_bit (visited
, be
->index
);
752 stack
[sp
++] = ei_start (be
->preds
);
755 /* The only case the below while fires is
756 when there's an infinite loop. */
760 /* EXIT_BLOCK is always included. */
761 post_order
[post_order_num
++] = EXIT_BLOCK
;
764 sbitmap_free (visited
);
765 return post_order_num
;
768 /* Compute the depth first search order and store in the array
769 PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
770 REV_POST_ORDER is nonzero, return the reverse completion number for each
771 node. Returns the number of nodes visited. A depth first search
772 tries to get as far away from the starting point as quickly as
775 pre_order is a really a preorder numbering of the graph.
776 rev_post_order is really a reverse postorder numbering of the graph.
780 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
781 bool include_entry_exit
)
783 edge_iterator
*stack
;
785 int pre_order_num
= 0;
786 int rev_post_order_num
= n_basic_blocks
- 1;
789 /* Allocate stack for back-tracking up CFG. */
790 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
793 if (include_entry_exit
)
796 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
799 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
802 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
804 /* Allocate bitmap to track nodes that have been visited. */
805 visited
= sbitmap_alloc (last_basic_block
);
807 /* None of the nodes in the CFG have been visited yet. */
808 bitmap_clear (visited
);
810 /* Push the first edge on to the stack. */
811 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
819 /* Look at the edge on the top of the stack. */
821 src
= ei_edge (ei
)->src
;
822 dest
= ei_edge (ei
)->dest
;
824 /* Check if the edge destination has been visited yet. */
825 if (dest
!= EXIT_BLOCK_PTR
&& ! bitmap_bit_p (visited
, dest
->index
))
827 /* Mark that we have visited the destination. */
828 bitmap_set_bit (visited
, dest
->index
);
831 pre_order
[pre_order_num
] = dest
->index
;
835 if (EDGE_COUNT (dest
->succs
) > 0)
836 /* Since the DEST node has been visited for the first
837 time, check its successors. */
838 stack
[sp
++] = ei_start (dest
->succs
);
839 else if (rev_post_order
)
840 /* There are no successors for the DEST node so assign
841 its reverse completion number. */
842 rev_post_order
[rev_post_order_num
--] = dest
->index
;
846 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
848 /* There are no more successors for the SRC node
849 so assign its reverse completion number. */
850 rev_post_order
[rev_post_order_num
--] = src
->index
;
852 if (!ei_one_before_end_p (ei
))
853 ei_next (&stack
[sp
- 1]);
860 sbitmap_free (visited
);
862 if (include_entry_exit
)
865 pre_order
[pre_order_num
] = EXIT_BLOCK
;
868 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
869 /* The number of nodes visited should be the number of blocks. */
870 gcc_assert (pre_order_num
== n_basic_blocks
);
873 /* The number of nodes visited should be the number of blocks minus
874 the entry and exit blocks which are not visited here. */
875 gcc_assert (pre_order_num
== n_basic_blocks
- NUM_FIXED_BLOCKS
);
877 return pre_order_num
;
880 /* Compute the depth first search order on the _reverse_ graph and
881 store in the array DFS_ORDER, marking the nodes visited in VISITED.
882 Returns the number of nodes visited.
884 The computation is split into three pieces:
886 flow_dfs_compute_reverse_init () creates the necessary data
889 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
890 structures. The block will start the search.
892 flow_dfs_compute_reverse_execute () continues (or starts) the
893 search using the block on the top of the stack, stopping when the
896 flow_dfs_compute_reverse_finish () destroys the necessary data
899 Thus, the user will probably call ..._init(), call ..._add_bb() to
900 add a beginning basic block to the stack, call ..._execute(),
901 possibly add another bb to the stack and again call ..._execute(),
902 ..., and finally call _finish(). */
904 /* Initialize the data structures used for depth-first search on the
905 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
906 added to the basic block stack. DATA is the current depth-first
907 search context. If INITIALIZE_STACK is nonzero, there is an
908 element on the stack. */
911 flow_dfs_compute_reverse_init (depth_first_search_ds data
)
913 /* Allocate stack for back-tracking up CFG. */
914 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks
);
917 /* Allocate bitmap to track nodes that have been visited. */
918 data
->visited_blocks
= sbitmap_alloc (last_basic_block
);
920 /* None of the nodes in the CFG have been visited yet. */
921 bitmap_clear (data
->visited_blocks
);
926 /* Add the specified basic block to the top of the dfs data
927 structures. When the search continues, it will start at the
931 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data
, basic_block bb
)
933 data
->stack
[data
->sp
++] = bb
;
934 bitmap_set_bit (data
->visited_blocks
, bb
->index
);
937 /* Continue the depth-first search through the reverse graph starting with the
938 block at the stack's top and ending when the stack is empty. Visited nodes
939 are marked. Returns an unvisited basic block, or NULL if there is none
943 flow_dfs_compute_reverse_execute (depth_first_search_ds data
,
944 basic_block last_unvisited
)
952 bb
= data
->stack
[--data
->sp
];
954 /* Perform depth-first search on adjacent vertices. */
955 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
956 if (!bitmap_bit_p (data
->visited_blocks
, e
->src
->index
))
957 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
960 /* Determine if there are unvisited basic blocks. */
961 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
962 if (!bitmap_bit_p (data
->visited_blocks
, bb
->index
))
968 /* Destroy the data structures needed for depth-first search on the
972 flow_dfs_compute_reverse_finish (depth_first_search_ds data
)
975 sbitmap_free (data
->visited_blocks
);
978 /* Performs dfs search from BB over vertices satisfying PREDICATE;
979 if REVERSE, go against direction of edges. Returns number of blocks
980 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
982 dfs_enumerate_from (basic_block bb
, int reverse
,
983 bool (*predicate
) (const_basic_block
, const void *),
984 basic_block
*rslt
, int rslt_max
, const void *data
)
986 basic_block
*st
, lbb
;
990 /* A bitmap to keep track of visited blocks. Allocating it each time
991 this function is called is not possible, since dfs_enumerate_from
992 is often used on small (almost) disjoint parts of cfg (bodies of
993 loops), and allocating a large sbitmap would lead to quadratic
995 static sbitmap visited
;
996 static unsigned v_size
;
998 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
999 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1000 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1002 /* Resize the VISITED sbitmap if necessary. */
1003 size
= last_basic_block
;
1010 visited
= sbitmap_alloc (size
);
1011 bitmap_clear (visited
);
1014 else if (v_size
< size
)
1016 /* Ensure that we increase the size of the sbitmap exponentially. */
1017 if (2 * v_size
> size
)
1020 visited
= sbitmap_resize (visited
, size
, 0);
1024 st
= XNEWVEC (basic_block
, rslt_max
);
1025 rslt
[tv
++] = st
[sp
++] = bb
;
1034 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1035 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1037 gcc_assert (tv
!= rslt_max
);
1038 rslt
[tv
++] = st
[sp
++] = e
->src
;
1039 MARK_VISITED (e
->src
);
1044 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1045 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1047 gcc_assert (tv
!= rslt_max
);
1048 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1049 MARK_VISITED (e
->dest
);
1054 for (sp
= 0; sp
< tv
; sp
++)
1055 UNMARK_VISITED (rslt
[sp
]);
1058 #undef UNMARK_VISITED
1063 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1065 This algorithm can be found in Timothy Harvey's PhD thesis, at
1066 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1067 dominance algorithms.
1069 First, we identify each join point, j (any node with more than one
1070 incoming edge is a join point).
1072 We then examine each predecessor, p, of j and walk up the dominator tree
1075 We stop the walk when we reach j's immediate dominator - j is in the
1076 dominance frontier of each of the nodes in the walk, except for j's
1077 immediate dominator. Intuitively, all of the rest of j's dominators are
1078 shared by j's predecessors as well.
1079 Since they dominate j, they will not have j in their dominance frontiers.
1081 The number of nodes touched by this algorithm is equal to the size
1082 of the dominance frontiers, no more, no less.
1087 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1094 if (EDGE_COUNT (b
->preds
) >= 2)
1096 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1098 basic_block runner
= p
->src
;
1100 if (runner
== ENTRY_BLOCK_PTR
)
1103 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1104 while (runner
!= domsb
)
1106 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1109 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1119 compute_dominance_frontiers (bitmap_head
*frontiers
)
1121 timevar_push (TV_DOM_FRONTIERS
);
1123 compute_dominance_frontiers_1 (frontiers
);
1125 timevar_pop (TV_DOM_FRONTIERS
);
1128 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1129 return a bitmap with all the blocks in the iterated dominance
1130 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1131 frontier information as returned by compute_dominance_frontiers.
1133 The resulting set of blocks are the potential sites where PHI nodes
1134 are needed. The caller is responsible for freeing the memory
1135 allocated for the return value. */
1138 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1141 unsigned bb_index
, i
;
1142 VEC(int,heap
) *work_stack
;
1143 bitmap phi_insertion_points
;
1145 work_stack
= VEC_alloc (int, heap
, n_basic_blocks
);
1146 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1148 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1149 VEC_quick_push here for speed. This is safe because we know that
1150 the number of definition blocks is no greater than the number of
1151 basic blocks, which is the initial capacity of WORK_STACK. */
1152 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1153 VEC_quick_push (int, work_stack
, bb_index
);
1155 /* Pop a block off the worklist, add every block that appears in
1156 the original block's DF that we have not already processed to
1157 the worklist. Iterate until the worklist is empty. Blocks
1158 which are added to the worklist are potential sites for
1160 while (VEC_length (int, work_stack
) > 0)
1162 bb_index
= VEC_pop (int, work_stack
);
1164 /* Since the registration of NEW -> OLD name mappings is done
1165 separately from the call to update_ssa, when updating the SSA
1166 form, the basic blocks where new and/or old names are defined
1167 may have disappeared by CFG cleanup calls. In this case,
1168 we may pull a non-existing block from the work stack. */
1169 gcc_assert (bb_index
< (unsigned) last_basic_block
);
1171 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1174 /* Use a safe push because if there is a definition of VAR
1175 in every basic block, then WORK_STACK may eventually have
1176 more than N_BASIC_BLOCK entries. */
1177 VEC_safe_push (int, heap
, work_stack
, i
);
1178 bitmap_set_bit (phi_insertion_points
, i
);
1182 VEC_free (int, heap
, work_stack
);
1184 return phi_insertion_points
;
1187 /* Intersection and union of preds/succs for sbitmap based data flow
1188 solvers. All four functions defined below take the same arguments:
1189 B is the basic block to perform the operation for. DST is the
1190 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1191 last_basic_block so that it can be indexed with basic block indices.
1192 DST may be (but does not have to be) SRC[B->index]. */
1194 /* Set the bitmap DST to the intersection of SRC of successors of
1198 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1200 unsigned int set_size
= dst
->size
;
1204 gcc_assert (!dst
->popcount
);
1206 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1208 e
= EDGE_SUCC (b
, ix
);
1209 if (e
->dest
== EXIT_BLOCK_PTR
)
1212 bitmap_copy (dst
, src
[e
->dest
->index
]);
1219 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1222 SBITMAP_ELT_TYPE
*p
, *r
;
1224 e
= EDGE_SUCC (b
, ix
);
1225 if (e
->dest
== EXIT_BLOCK_PTR
)
1228 p
= src
[e
->dest
->index
]->elms
;
1230 for (i
= 0; i
< set_size
; i
++)
1235 /* Set the bitmap DST to the intersection of SRC of predecessors of
1239 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1241 unsigned int set_size
= dst
->size
;
1245 gcc_assert (!dst
->popcount
);
1247 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1249 e
= EDGE_PRED (b
, ix
);
1250 if (e
->src
== ENTRY_BLOCK_PTR
)
1253 bitmap_copy (dst
, src
[e
->src
->index
]);
1260 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1263 SBITMAP_ELT_TYPE
*p
, *r
;
1265 e
= EDGE_PRED (b
, ix
);
1266 if (e
->src
== ENTRY_BLOCK_PTR
)
1269 p
= src
[e
->src
->index
]->elms
;
1271 for (i
= 0; i
< set_size
; i
++)
1276 /* Set the bitmap DST to the union of SRC of successors of
1280 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1282 unsigned int set_size
= dst
->size
;
1286 gcc_assert (!dst
->popcount
);
1288 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1290 e
= EDGE_SUCC (b
, ix
);
1291 if (e
->dest
== EXIT_BLOCK_PTR
)
1294 bitmap_copy (dst
, src
[e
->dest
->index
]);
1298 if (ix
== EDGE_COUNT (b
->succs
))
1301 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1304 SBITMAP_ELT_TYPE
*p
, *r
;
1306 e
= EDGE_SUCC (b
, ix
);
1307 if (e
->dest
== EXIT_BLOCK_PTR
)
1310 p
= src
[e
->dest
->index
]->elms
;
1312 for (i
= 0; i
< set_size
; i
++)
1317 /* Set the bitmap DST to the union of SRC of predecessors of
1321 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1323 unsigned int set_size
= dst
->size
;
1327 gcc_assert (!dst
->popcount
);
1329 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1331 e
= EDGE_PRED (b
, ix
);
1332 if (e
->src
== ENTRY_BLOCK_PTR
)
1335 bitmap_copy (dst
, src
[e
->src
->index
]);
1339 if (ix
== EDGE_COUNT (b
->preds
))
1342 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1345 SBITMAP_ELT_TYPE
*p
, *r
;
1347 e
= EDGE_PRED (b
, ix
);
1348 if (e
->src
== ENTRY_BLOCK_PTR
)
1351 p
= src
[e
->src
->index
]->elms
;
1353 for (i
= 0; i
< set_size
; i
++)