1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2013 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"
31 /* Store the data structures necessary for depth-first search. */
32 struct depth_first_search_dsS
{
33 /* stack for backtracking during the algorithm */
36 /* number of edges in the stack. That is, positions 0, ..., sp-1
40 /* record of basic blocks already seen by depth-first search */
41 sbitmap visited_blocks
;
43 typedef struct depth_first_search_dsS
*depth_first_search_ds
;
45 static void flow_dfs_compute_reverse_init (depth_first_search_ds
);
46 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds
,
48 static basic_block
flow_dfs_compute_reverse_execute (depth_first_search_ds
,
50 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
);
52 /* Mark the back edges in DFS traversal.
53 Return nonzero if a loop (natural or otherwise) is present.
54 Inspired by Depth_First_Search_PP described in:
56 Advanced Compiler Design and Implementation
60 and heavily borrowed from pre_and_rev_post_order_compute. */
63 mark_dfs_back_edges (void)
74 /* Allocate the preorder and postorder number arrays. */
75 pre
= XCNEWVEC (int, last_basic_block
);
76 post
= XCNEWVEC (int, last_basic_block
);
78 /* Allocate stack for back-tracking up CFG. */
79 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
82 /* Allocate bitmap to track nodes that have been visited. */
83 visited
= sbitmap_alloc (last_basic_block
);
85 /* None of the nodes in the CFG have been visited yet. */
86 bitmap_clear (visited
);
88 /* Push the first edge on to the stack. */
89 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
97 /* Look at the edge on the top of the stack. */
99 src
= ei_edge (ei
)->src
;
100 dest
= ei_edge (ei
)->dest
;
101 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
103 /* Check if the edge destination has been visited yet. */
104 if (dest
!= EXIT_BLOCK_PTR
&& ! bitmap_bit_p (visited
, dest
->index
))
106 /* Mark that we have visited the destination. */
107 bitmap_set_bit (visited
, dest
->index
);
109 pre
[dest
->index
] = prenum
++;
110 if (EDGE_COUNT (dest
->succs
) > 0)
112 /* Since the DEST node has been visited for the first
113 time, check its successors. */
114 stack
[sp
++] = ei_start (dest
->succs
);
117 post
[dest
->index
] = postnum
++;
121 if (dest
!= EXIT_BLOCK_PTR
&& src
!= ENTRY_BLOCK_PTR
122 && pre
[src
->index
] >= pre
[dest
->index
]
123 && post
[dest
->index
] == 0)
124 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
126 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
127 post
[src
->index
] = postnum
++;
129 if (!ei_one_before_end_p (ei
))
130 ei_next (&stack
[sp
- 1]);
139 sbitmap_free (visited
);
144 /* Find unreachable blocks. An unreachable block will have 0 in
145 the reachable bit in block->flags. A nonzero value indicates the
146 block is reachable. */
149 find_unreachable_blocks (void)
153 basic_block
*tos
, *worklist
, bb
;
155 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
157 /* Clear all the reachability flags. */
160 bb
->flags
&= ~BB_REACHABLE
;
162 /* Add our starting points to the worklist. Almost always there will
163 be only one. It isn't inconceivable that we might one day directly
164 support Fortran alternate entry points. */
166 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
170 /* Mark the block reachable. */
171 e
->dest
->flags
|= BB_REACHABLE
;
174 /* Iterate: find everything reachable from what we've already seen. */
176 while (tos
!= worklist
)
178 basic_block b
= *--tos
;
180 FOR_EACH_EDGE (e
, ei
, b
->succs
)
182 basic_block dest
= e
->dest
;
184 if (!(dest
->flags
& BB_REACHABLE
))
187 dest
->flags
|= BB_REACHABLE
;
195 /* Functions to access an edge list with a vector representation.
196 Enough data is kept such that given an index number, the
197 pred and succ that edge represents can be determined, or
198 given a pred and a succ, its index number can be returned.
199 This allows algorithms which consume a lot of memory to
200 represent the normally full matrix of edge (pred,succ) with a
201 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
202 wasted space in the client code due to sparse flow graphs. */
204 /* This functions initializes the edge list. Basically the entire
205 flowgraph is processed, and all edges are assigned a number,
206 and the data structure is filled in. */
209 create_edge_list (void)
211 struct edge_list
*elist
;
217 /* Determine the number of edges in the flow graph by counting successor
218 edges on each basic block. */
220 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
222 num_edges
+= EDGE_COUNT (bb
->succs
);
225 elist
= XNEW (struct edge_list
);
226 elist
->num_edges
= num_edges
;
227 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
231 /* Follow successors of blocks, and register these edges. */
232 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
233 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
234 elist
->index_to_edge
[num_edges
++] = e
;
239 /* This function free's memory associated with an edge list. */
242 free_edge_list (struct edge_list
*elist
)
246 free (elist
->index_to_edge
);
251 /* This function provides debug output showing an edge list. */
254 print_edge_list (FILE *f
, struct edge_list
*elist
)
258 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
259 n_basic_blocks
, elist
->num_edges
);
261 for (x
= 0; x
< elist
->num_edges
; x
++)
263 fprintf (f
, " %-4d - edge(", x
);
264 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR
)
265 fprintf (f
, "entry,");
267 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
269 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR
)
270 fprintf (f
, "exit)\n");
272 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
276 /* This function provides an internal consistency check of an edge list,
277 verifying that all edges are present, and that there are no
281 verify_edge_list (FILE *f
, struct edge_list
*elist
)
283 int pred
, succ
, index
;
285 basic_block bb
, p
, s
;
288 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
290 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
292 pred
= e
->src
->index
;
293 succ
= e
->dest
->index
;
294 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
295 if (index
== EDGE_INDEX_NO_EDGE
)
297 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
301 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
302 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
303 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
304 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
305 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
306 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
310 /* We've verified that all the edges are in the list, now lets make sure
311 there are no spurious edges in the list. This is an expensive check! */
313 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
314 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
318 FOR_EACH_EDGE (e
, ei
, p
->succs
)
325 FOR_EACH_EDGE (e
, ei
, s
->preds
)
332 if (EDGE_INDEX (elist
, p
, s
)
333 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
334 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
336 if (EDGE_INDEX (elist
, p
, s
)
337 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
338 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
339 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
344 /* Functions to compute control dependences. */
346 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
348 control_dependences::set_control_dependence_map_bit (basic_block bb
,
351 if (bb
== ENTRY_BLOCK_PTR
)
353 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
354 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
357 /* Clear all control dependences for block BB. */
359 control_dependences::clear_control_dependence_bitmap (basic_block bb
)
361 bitmap_clear (control_dependence_map
[bb
->index
]);
364 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
365 This function is necessary because some blocks have negative numbers. */
367 static inline basic_block
368 find_pdom (basic_block block
)
370 gcc_assert (block
!= ENTRY_BLOCK_PTR
);
372 if (block
== EXIT_BLOCK_PTR
)
373 return EXIT_BLOCK_PTR
;
376 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
378 return EXIT_BLOCK_PTR
;
383 /* Determine all blocks' control dependences on the given edge with edge_list
384 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
387 control_dependences::find_control_dependence (int edge_index
)
389 basic_block current_block
;
390 basic_block ending_block
;
392 gcc_assert (INDEX_EDGE_PRED_BB (m_el
, edge_index
) != EXIT_BLOCK_PTR
);
394 if (INDEX_EDGE_PRED_BB (m_el
, edge_index
) == ENTRY_BLOCK_PTR
)
395 ending_block
= single_succ (ENTRY_BLOCK_PTR
);
397 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (m_el
, edge_index
));
399 for (current_block
= INDEX_EDGE_SUCC_BB (m_el
, edge_index
);
400 current_block
!= ending_block
&& current_block
!= EXIT_BLOCK_PTR
;
401 current_block
= find_pdom (current_block
))
403 edge e
= INDEX_EDGE (m_el
, edge_index
);
405 /* For abnormal edges, we don't make current_block control
406 dependent because instructions that throw are always necessary
408 if (e
->flags
& EDGE_ABNORMAL
)
411 set_control_dependence_map_bit (current_block
, edge_index
);
415 /* Record all blocks' control dependences on all edges in the edge
416 list EL, ala Morgan, Section 3.6. */
418 control_dependences::control_dependences (struct edge_list
*edges
)
421 timevar_push (TV_CONTROL_DEPENDENCES
);
422 control_dependence_map
.create (last_basic_block
);
423 for (int i
= 0; i
< last_basic_block
; ++i
)
424 control_dependence_map
.quick_push (BITMAP_ALLOC (NULL
));
425 for (int i
= 0; i
< NUM_EDGES (m_el
); ++i
)
426 find_control_dependence (i
);
427 timevar_pop (TV_CONTROL_DEPENDENCES
);
430 /* Free control dependences and the associated edge list. */
432 control_dependences::~control_dependences ()
434 for (unsigned i
= 0; i
< control_dependence_map
.length (); ++i
)
435 BITMAP_FREE (control_dependence_map
[i
]);
436 control_dependence_map
.release ();
437 free_edge_list (m_el
);
440 /* Returns the bitmap of edges the basic-block I is dependent on. */
443 control_dependences::get_edges_dependent_on (int i
)
445 return control_dependence_map
[i
];
448 /* Returns the edge with index I from the edge list. */
451 control_dependences::get_edge (int i
)
453 return INDEX_EDGE (m_el
, i
);
457 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
458 If no such edge exists, return NULL. */
461 find_edge (basic_block pred
, basic_block succ
)
466 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
468 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
474 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
482 /* This routine will determine what, if any, edge there is between
483 a specified predecessor and successor. */
486 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
490 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
491 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
492 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
495 return (EDGE_INDEX_NO_EDGE
);
498 /* This routine will remove any fake predecessor edges for a basic block.
499 When the edge is removed, it is also removed from whatever successor
503 remove_fake_predecessors (basic_block bb
)
508 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
510 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
517 /* This routine will remove all fake edges from the flow graph. If
518 we remove all fake successors, it will automatically remove all
519 fake predecessors. */
522 remove_fake_edges (void)
526 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
527 remove_fake_predecessors (bb
);
530 /* This routine will remove all fake edges to the EXIT_BLOCK. */
533 remove_fake_exit_edges (void)
535 remove_fake_predecessors (EXIT_BLOCK_PTR
);
539 /* This function will add a fake edge between any block which has no
540 successors, and the exit block. Some data flow equations require these
544 add_noreturn_fake_exit_edges (void)
549 if (EDGE_COUNT (bb
->succs
) == 0)
550 make_single_succ_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
553 /* This function adds a fake edge between any infinite loops to the
554 exit block. Some optimizations require a path from each node to
557 See also Morgan, Figure 3.10, pp. 82-83.
559 The current implementation is ugly, not attempting to minimize the
560 number of inserted fake edges. To reduce the number of fake edges
561 to insert, add fake edges from _innermost_ loops containing only
562 nodes not reachable from the exit block. */
565 connect_infinite_loops_to_exit (void)
567 basic_block unvisited_block
= EXIT_BLOCK_PTR
;
568 basic_block deadend_block
;
569 struct depth_first_search_dsS dfs_ds
;
571 /* Perform depth-first search in the reverse graph to find nodes
572 reachable from the exit block. */
573 flow_dfs_compute_reverse_init (&dfs_ds
);
574 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR
);
576 /* Repeatedly add fake edges, updating the unreachable nodes. */
579 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
581 if (!unvisited_block
)
584 deadend_block
= dfs_find_deadend (unvisited_block
);
585 make_edge (deadend_block
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
586 flow_dfs_compute_reverse_add_bb (&dfs_ds
, deadend_block
);
589 flow_dfs_compute_reverse_finish (&dfs_ds
);
593 /* Compute reverse top sort order. This is computing a post order
594 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
595 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
596 true, unreachable blocks are deleted. */
599 post_order_compute (int *post_order
, bool include_entry_exit
,
600 bool delete_unreachable
)
602 edge_iterator
*stack
;
604 int post_order_num
= 0;
608 if (include_entry_exit
)
609 post_order
[post_order_num
++] = EXIT_BLOCK
;
611 /* Allocate stack for back-tracking up CFG. */
612 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
615 /* Allocate bitmap to track nodes that have been visited. */
616 visited
= sbitmap_alloc (last_basic_block
);
618 /* None of the nodes in the CFG have been visited yet. */
619 bitmap_clear (visited
);
621 /* Push the first edge on to the stack. */
622 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR
->succs
);
630 /* Look at the edge on the top of the stack. */
632 src
= ei_edge (ei
)->src
;
633 dest
= ei_edge (ei
)->dest
;
635 /* Check if the edge destination has been visited yet. */
636 if (dest
!= EXIT_BLOCK_PTR
&& ! bitmap_bit_p (visited
, dest
->index
))
638 /* Mark that we have visited the destination. */
639 bitmap_set_bit (visited
, dest
->index
);
641 if (EDGE_COUNT (dest
->succs
) > 0)
642 /* Since the DEST node has been visited for the first
643 time, check its successors. */
644 stack
[sp
++] = ei_start (dest
->succs
);
646 post_order
[post_order_num
++] = dest
->index
;
650 if (ei_one_before_end_p (ei
) && src
!= ENTRY_BLOCK_PTR
)
651 post_order
[post_order_num
++] = src
->index
;
653 if (!ei_one_before_end_p (ei
))
654 ei_next (&stack
[sp
- 1]);
660 if (include_entry_exit
)
662 post_order
[post_order_num
++] = ENTRY_BLOCK
;
663 count
= post_order_num
;
666 count
= post_order_num
+ 2;
668 /* Delete the unreachable blocks if some were found and we are
669 supposed to do it. */
670 if (delete_unreachable
&& (count
!= n_basic_blocks
))
674 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
676 next_bb
= b
->next_bb
;
678 if (!(bitmap_bit_p (visited
, b
->index
)))
679 delete_basic_block (b
);
682 tidy_fallthru_edges ();
686 sbitmap_free (visited
);
687 return post_order_num
;
691 /* Helper routine for inverted_post_order_compute
692 flow_dfs_compute_reverse_execute, and the reverse-CFG
693 deapth first search in dominance.c.
694 BB has to belong to a region of CFG
695 unreachable by inverted traversal from the exit.
696 i.e. there's no control flow path from ENTRY to EXIT
697 that contains this BB.
698 This can happen in two cases - if there's an infinite loop
699 or if there's a block that has no successor
700 (call to a function with no return).
701 Some RTL passes deal with this condition by
702 calling connect_infinite_loops_to_exit () and/or
703 add_noreturn_fake_exit_edges ().
704 However, those methods involve modifying the CFG itself
705 which may not be desirable.
706 Hence, we deal with the infinite loop/no return cases
707 by identifying a unique basic block that can reach all blocks
708 in such a region by inverted traversal.
709 This function returns a basic block that guarantees
710 that all blocks in the region are reachable
711 by starting an inverted traversal from the returned block. */
714 dfs_find_deadend (basic_block bb
)
716 bitmap visited
= BITMAP_ALLOC (NULL
);
720 if (EDGE_COUNT (bb
->succs
) == 0
721 || ! bitmap_set_bit (visited
, bb
->index
))
723 BITMAP_FREE (visited
);
727 bb
= EDGE_SUCC (bb
, 0)->dest
;
734 /* Compute the reverse top sort order of the inverted CFG
735 i.e. starting from the exit block and following the edges backward
736 (from successors to predecessors).
737 This ordering can be used for forward dataflow problems among others.
739 This function assumes that all blocks in the CFG are reachable
740 from the ENTRY (but not necessarily from EXIT).
742 If there's an infinite loop,
743 a simple inverted traversal starting from the blocks
744 with no successors can't visit all blocks.
745 To solve this problem, we first do inverted traversal
746 starting from the blocks with no successor.
747 And if there's any block left that's not visited by the regular
748 inverted traversal from EXIT,
749 those blocks are in such problematic region.
750 Among those, we find one block that has
751 any visited predecessor (which is an entry into such a region),
752 and start looking for a "dead end" from that block
753 and do another inverted traversal from that block. */
756 inverted_post_order_compute (int *post_order
)
759 edge_iterator
*stack
;
761 int post_order_num
= 0;
764 /* Allocate stack for back-tracking up CFG. */
765 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
768 /* Allocate bitmap to track nodes that have been visited. */
769 visited
= sbitmap_alloc (last_basic_block
);
771 /* None of the nodes in the CFG have been visited yet. */
772 bitmap_clear (visited
);
774 /* Put all blocks that have no successor into the initial work list. */
776 if (EDGE_COUNT (bb
->succs
) == 0)
778 /* Push the initial edge on to the stack. */
779 if (EDGE_COUNT (bb
->preds
) > 0)
781 stack
[sp
++] = ei_start (bb
->preds
);
782 bitmap_set_bit (visited
, bb
->index
);
788 bool has_unvisited_bb
= false;
790 /* The inverted traversal loop. */
796 /* Look at the edge on the top of the stack. */
798 bb
= ei_edge (ei
)->dest
;
799 pred
= ei_edge (ei
)->src
;
801 /* Check if the predecessor has been visited yet. */
802 if (! bitmap_bit_p (visited
, pred
->index
))
804 /* Mark that we have visited the destination. */
805 bitmap_set_bit (visited
, pred
->index
);
807 if (EDGE_COUNT (pred
->preds
) > 0)
808 /* Since the predecessor node has been visited for the first
809 time, check its predecessors. */
810 stack
[sp
++] = ei_start (pred
->preds
);
812 post_order
[post_order_num
++] = pred
->index
;
816 if (bb
!= EXIT_BLOCK_PTR
&& ei_one_before_end_p (ei
))
817 post_order
[post_order_num
++] = bb
->index
;
819 if (!ei_one_before_end_p (ei
))
820 ei_next (&stack
[sp
- 1]);
826 /* Detect any infinite loop and activate the kludge.
827 Note that this doesn't check EXIT_BLOCK itself
828 since EXIT_BLOCK is always added after the outer do-while loop. */
829 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
830 if (!bitmap_bit_p (visited
, bb
->index
))
832 has_unvisited_bb
= true;
834 if (EDGE_COUNT (bb
->preds
) > 0)
838 basic_block visited_pred
= NULL
;
840 /* Find an already visited predecessor. */
841 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
843 if (bitmap_bit_p (visited
, e
->src
->index
))
844 visited_pred
= e
->src
;
849 basic_block be
= dfs_find_deadend (bb
);
850 gcc_assert (be
!= NULL
);
851 bitmap_set_bit (visited
, be
->index
);
852 stack
[sp
++] = ei_start (be
->preds
);
858 if (has_unvisited_bb
&& sp
== 0)
860 /* No blocks are reachable from EXIT at all.
861 Find a dead-end from the ENTRY, and restart the iteration. */
862 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR
);
863 gcc_assert (be
!= NULL
);
864 bitmap_set_bit (visited
, be
->index
);
865 stack
[sp
++] = ei_start (be
->preds
);
868 /* The only case the below while fires is
869 when there's an infinite loop. */
873 /* EXIT_BLOCK is always included. */
874 post_order
[post_order_num
++] = EXIT_BLOCK
;
877 sbitmap_free (visited
);
878 return post_order_num
;
881 /* Compute the depth first search order of FN and store in the array
882 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
883 reverse completion number for each node. Returns the number of nodes
884 visited. A depth first search tries to get as far away from the starting
885 point as quickly as possible.
887 In case the function has unreachable blocks the number of nodes
888 visited does not include them.
890 pre_order is a really a preorder numbering of the graph.
891 rev_post_order is really a reverse postorder numbering of the graph. */
894 pre_and_rev_post_order_compute_fn (struct function
*fn
,
895 int *pre_order
, int *rev_post_order
,
896 bool include_entry_exit
)
898 edge_iterator
*stack
;
900 int pre_order_num
= 0;
901 int rev_post_order_num
= n_basic_blocks
- 1;
904 /* Allocate stack for back-tracking up CFG. */
905 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
+ 1);
908 if (include_entry_exit
)
911 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
914 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
917 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
919 /* Allocate bitmap to track nodes that have been visited. */
920 visited
= sbitmap_alloc (last_basic_block
);
922 /* None of the nodes in the CFG have been visited yet. */
923 bitmap_clear (visited
);
925 /* Push the first edge on to the stack. */
926 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FUNCTION (fn
)->succs
);
934 /* Look at the edge on the top of the stack. */
936 src
= ei_edge (ei
)->src
;
937 dest
= ei_edge (ei
)->dest
;
939 /* Check if the edge destination has been visited yet. */
940 if (dest
!= EXIT_BLOCK_PTR_FOR_FUNCTION (fn
)
941 && ! bitmap_bit_p (visited
, dest
->index
))
943 /* Mark that we have visited the destination. */
944 bitmap_set_bit (visited
, dest
->index
);
947 pre_order
[pre_order_num
] = dest
->index
;
951 if (EDGE_COUNT (dest
->succs
) > 0)
952 /* Since the DEST node has been visited for the first
953 time, check its successors. */
954 stack
[sp
++] = ei_start (dest
->succs
);
955 else if (rev_post_order
)
956 /* There are no successors for the DEST node so assign
957 its reverse completion number. */
958 rev_post_order
[rev_post_order_num
--] = dest
->index
;
962 if (ei_one_before_end_p (ei
)
963 && src
!= ENTRY_BLOCK_PTR_FOR_FUNCTION (fn
)
965 /* There are no more successors for the SRC node
966 so assign its reverse completion number. */
967 rev_post_order
[rev_post_order_num
--] = src
->index
;
969 if (!ei_one_before_end_p (ei
))
970 ei_next (&stack
[sp
- 1]);
977 sbitmap_free (visited
);
979 if (include_entry_exit
)
982 pre_order
[pre_order_num
] = EXIT_BLOCK
;
985 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
988 return pre_order_num
;
991 /* Like pre_and_rev_post_order_compute_fn but operating on the
992 current function and asserting that all nodes were visited. */
995 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
996 bool include_entry_exit
)
999 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1000 include_entry_exit
);
1001 if (include_entry_exit
)
1002 /* The number of nodes visited should be the number of blocks. */
1003 gcc_assert (pre_order_num
== n_basic_blocks
);
1005 /* The number of nodes visited should be the number of blocks minus
1006 the entry and exit blocks which are not visited here. */
1007 gcc_assert (pre_order_num
== n_basic_blocks
- NUM_FIXED_BLOCKS
);
1009 return pre_order_num
;
1012 /* Compute the depth first search order on the _reverse_ graph and
1013 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1014 Returns the number of nodes visited.
1016 The computation is split into three pieces:
1018 flow_dfs_compute_reverse_init () creates the necessary data
1021 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1022 structures. The block will start the search.
1024 flow_dfs_compute_reverse_execute () continues (or starts) the
1025 search using the block on the top of the stack, stopping when the
1028 flow_dfs_compute_reverse_finish () destroys the necessary data
1031 Thus, the user will probably call ..._init(), call ..._add_bb() to
1032 add a beginning basic block to the stack, call ..._execute(),
1033 possibly add another bb to the stack and again call ..._execute(),
1034 ..., and finally call _finish(). */
1036 /* Initialize the data structures used for depth-first search on the
1037 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1038 added to the basic block stack. DATA is the current depth-first
1039 search context. If INITIALIZE_STACK is nonzero, there is an
1040 element on the stack. */
1043 flow_dfs_compute_reverse_init (depth_first_search_ds data
)
1045 /* Allocate stack for back-tracking up CFG. */
1046 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks
);
1049 /* Allocate bitmap to track nodes that have been visited. */
1050 data
->visited_blocks
= sbitmap_alloc (last_basic_block
);
1052 /* None of the nodes in the CFG have been visited yet. */
1053 bitmap_clear (data
->visited_blocks
);
1058 /* Add the specified basic block to the top of the dfs data
1059 structures. When the search continues, it will start at the
1063 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data
, basic_block bb
)
1065 data
->stack
[data
->sp
++] = bb
;
1066 bitmap_set_bit (data
->visited_blocks
, bb
->index
);
1069 /* Continue the depth-first search through the reverse graph starting with the
1070 block at the stack's top and ending when the stack is empty. Visited nodes
1071 are marked. Returns an unvisited basic block, or NULL if there is none
1075 flow_dfs_compute_reverse_execute (depth_first_search_ds data
,
1076 basic_block last_unvisited
)
1082 while (data
->sp
> 0)
1084 bb
= data
->stack
[--data
->sp
];
1086 /* Perform depth-first search on adjacent vertices. */
1087 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1088 if (!bitmap_bit_p (data
->visited_blocks
, e
->src
->index
))
1089 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1092 /* Determine if there are unvisited basic blocks. */
1093 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1094 if (!bitmap_bit_p (data
->visited_blocks
, bb
->index
))
1100 /* Destroy the data structures needed for depth-first search on the
1104 flow_dfs_compute_reverse_finish (depth_first_search_ds data
)
1107 sbitmap_free (data
->visited_blocks
);
1110 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1111 if REVERSE, go against direction of edges. Returns number of blocks
1112 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1114 dfs_enumerate_from (basic_block bb
, int reverse
,
1115 bool (*predicate
) (const_basic_block
, const void *),
1116 basic_block
*rslt
, int rslt_max
, const void *data
)
1118 basic_block
*st
, lbb
;
1122 /* A bitmap to keep track of visited blocks. Allocating it each time
1123 this function is called is not possible, since dfs_enumerate_from
1124 is often used on small (almost) disjoint parts of cfg (bodies of
1125 loops), and allocating a large sbitmap would lead to quadratic
1127 static sbitmap visited
;
1128 static unsigned v_size
;
1130 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1131 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1132 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1134 /* Resize the VISITED sbitmap if necessary. */
1135 size
= last_basic_block
;
1142 visited
= sbitmap_alloc (size
);
1143 bitmap_clear (visited
);
1146 else if (v_size
< size
)
1148 /* Ensure that we increase the size of the sbitmap exponentially. */
1149 if (2 * v_size
> size
)
1152 visited
= sbitmap_resize (visited
, size
, 0);
1156 st
= XNEWVEC (basic_block
, rslt_max
);
1157 rslt
[tv
++] = st
[sp
++] = bb
;
1166 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1167 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1169 gcc_assert (tv
!= rslt_max
);
1170 rslt
[tv
++] = st
[sp
++] = e
->src
;
1171 MARK_VISITED (e
->src
);
1176 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1177 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1179 gcc_assert (tv
!= rslt_max
);
1180 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1181 MARK_VISITED (e
->dest
);
1186 for (sp
= 0; sp
< tv
; sp
++)
1187 UNMARK_VISITED (rslt
[sp
]);
1190 #undef UNMARK_VISITED
1195 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1197 This algorithm can be found in Timothy Harvey's PhD thesis, at
1198 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1199 dominance algorithms.
1201 First, we identify each join point, j (any node with more than one
1202 incoming edge is a join point).
1204 We then examine each predecessor, p, of j and walk up the dominator tree
1207 We stop the walk when we reach j's immediate dominator - j is in the
1208 dominance frontier of each of the nodes in the walk, except for j's
1209 immediate dominator. Intuitively, all of the rest of j's dominators are
1210 shared by j's predecessors as well.
1211 Since they dominate j, they will not have j in their dominance frontiers.
1213 The number of nodes touched by this algorithm is equal to the size
1214 of the dominance frontiers, no more, no less.
1219 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1226 if (EDGE_COUNT (b
->preds
) >= 2)
1228 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1230 basic_block runner
= p
->src
;
1232 if (runner
== ENTRY_BLOCK_PTR
)
1235 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1236 while (runner
!= domsb
)
1238 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1241 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1251 compute_dominance_frontiers (bitmap_head
*frontiers
)
1253 timevar_push (TV_DOM_FRONTIERS
);
1255 compute_dominance_frontiers_1 (frontiers
);
1257 timevar_pop (TV_DOM_FRONTIERS
);
1260 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1261 return a bitmap with all the blocks in the iterated dominance
1262 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1263 frontier information as returned by compute_dominance_frontiers.
1265 The resulting set of blocks are the potential sites where PHI nodes
1266 are needed. The caller is responsible for freeing the memory
1267 allocated for the return value. */
1270 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1273 unsigned bb_index
, i
;
1274 vec
<int> work_stack
;
1275 bitmap phi_insertion_points
;
1277 /* Each block can appear at most twice on the work-stack. */
1278 work_stack
.create (2 * n_basic_blocks
);
1279 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1281 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1282 vec::quick_push here for speed. This is safe because we know that
1283 the number of definition blocks is no greater than the number of
1284 basic blocks, which is the initial capacity of WORK_STACK. */
1285 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1286 work_stack
.quick_push (bb_index
);
1288 /* Pop a block off the worklist, add every block that appears in
1289 the original block's DF that we have not already processed to
1290 the worklist. Iterate until the worklist is empty. Blocks
1291 which are added to the worklist are potential sites for
1293 while (work_stack
.length () > 0)
1295 bb_index
= work_stack
.pop ();
1297 /* Since the registration of NEW -> OLD name mappings is done
1298 separately from the call to update_ssa, when updating the SSA
1299 form, the basic blocks where new and/or old names are defined
1300 may have disappeared by CFG cleanup calls. In this case,
1301 we may pull a non-existing block from the work stack. */
1302 gcc_checking_assert (bb_index
< (unsigned) last_basic_block
);
1304 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1307 work_stack
.quick_push (i
);
1308 bitmap_set_bit (phi_insertion_points
, i
);
1312 work_stack
.release ();
1314 return phi_insertion_points
;
1317 /* Intersection and union of preds/succs for sbitmap based data flow
1318 solvers. All four functions defined below take the same arguments:
1319 B is the basic block to perform the operation for. DST is the
1320 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1321 last_basic_block so that it can be indexed with basic block indices.
1322 DST may be (but does not have to be) SRC[B->index]. */
1324 /* Set the bitmap DST to the intersection of SRC of successors of
1328 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1330 unsigned int set_size
= dst
->size
;
1334 gcc_assert (!dst
->popcount
);
1336 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1338 e
= EDGE_SUCC (b
, ix
);
1339 if (e
->dest
== EXIT_BLOCK_PTR
)
1342 bitmap_copy (dst
, src
[e
->dest
->index
]);
1349 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1352 SBITMAP_ELT_TYPE
*p
, *r
;
1354 e
= EDGE_SUCC (b
, ix
);
1355 if (e
->dest
== EXIT_BLOCK_PTR
)
1358 p
= src
[e
->dest
->index
]->elms
;
1360 for (i
= 0; i
< set_size
; i
++)
1365 /* Set the bitmap DST to the intersection of SRC of predecessors of
1369 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1371 unsigned int set_size
= dst
->size
;
1375 gcc_assert (!dst
->popcount
);
1377 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1379 e
= EDGE_PRED (b
, ix
);
1380 if (e
->src
== ENTRY_BLOCK_PTR
)
1383 bitmap_copy (dst
, src
[e
->src
->index
]);
1390 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1393 SBITMAP_ELT_TYPE
*p
, *r
;
1395 e
= EDGE_PRED (b
, ix
);
1396 if (e
->src
== ENTRY_BLOCK_PTR
)
1399 p
= src
[e
->src
->index
]->elms
;
1401 for (i
= 0; i
< set_size
; i
++)
1406 /* Set the bitmap DST to the union of SRC of successors of
1410 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1412 unsigned int set_size
= dst
->size
;
1416 gcc_assert (!dst
->popcount
);
1418 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1420 e
= EDGE_SUCC (b
, ix
);
1421 if (e
->dest
== EXIT_BLOCK_PTR
)
1424 bitmap_copy (dst
, src
[e
->dest
->index
]);
1428 if (ix
== EDGE_COUNT (b
->succs
))
1431 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1434 SBITMAP_ELT_TYPE
*p
, *r
;
1436 e
= EDGE_SUCC (b
, ix
);
1437 if (e
->dest
== EXIT_BLOCK_PTR
)
1440 p
= src
[e
->dest
->index
]->elms
;
1442 for (i
= 0; i
< set_size
; i
++)
1447 /* Set the bitmap DST to the union of SRC of predecessors of
1451 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1453 unsigned int set_size
= dst
->size
;
1457 gcc_assert (!dst
->popcount
);
1459 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1461 e
= EDGE_PRED (b
, ix
);
1462 if (e
->src
== ENTRY_BLOCK_PTR
)
1465 bitmap_copy (dst
, src
[e
->src
->index
]);
1469 if (ix
== EDGE_COUNT (b
->preds
))
1472 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1475 SBITMAP_ELT_TYPE
*p
, *r
;
1477 e
= EDGE_PRED (b
, ix
);
1478 if (e
->src
== ENTRY_BLOCK_PTR
)
1481 p
= src
[e
->src
->index
]->elms
;
1483 for (i
= 0; i
< set_size
; i
++)
1488 /* Returns the list of basic blocks in the function in an order that guarantees
1489 that if a block X has just a single predecessor Y, then Y is after X in the
1493 single_pred_before_succ_order (void)
1496 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks
);
1497 unsigned n
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
1499 sbitmap visited
= sbitmap_alloc (last_basic_block
);
1501 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1502 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1504 bitmap_clear (visited
);
1506 MARK_VISITED (ENTRY_BLOCK_PTR
);
1512 /* Walk the predecessors of x as long as they have precisely one
1513 predecessor and add them to the list, so that they get stored
1516 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1517 y
= single_pred (y
))
1519 for (y
= x
, i
= n
- np
;
1520 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1521 y
= single_pred (y
), i
++)
1529 gcc_assert (i
== n
- 1);
1533 sbitmap_free (visited
);
1534 gcc_assert (n
== 0);