1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2015 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"
30 #include "hard-reg-set.h"
33 #include "dominance.h"
36 #include "basic-block.h"
41 /* Store the data structures necessary for depth-first search. */
42 struct depth_first_search_dsS
{
43 /* stack for backtracking during the algorithm */
46 /* number of edges in the stack. That is, positions 0, ..., sp-1
50 /* record of basic blocks already seen by depth-first search */
51 sbitmap visited_blocks
;
53 typedef struct depth_first_search_dsS
*depth_first_search_ds
;
55 static void flow_dfs_compute_reverse_init (depth_first_search_ds
);
56 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds
,
58 static basic_block
flow_dfs_compute_reverse_execute (depth_first_search_ds
,
60 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
);
62 /* Mark the back edges in DFS traversal.
63 Return nonzero if a loop (natural or otherwise) is present.
64 Inspired by Depth_First_Search_PP described in:
66 Advanced Compiler Design and Implementation
70 and heavily borrowed from pre_and_rev_post_order_compute. */
73 mark_dfs_back_edges (void)
84 /* Allocate the preorder and postorder number arrays. */
85 pre
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
86 post
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
88 /* Allocate stack for back-tracking up CFG. */
89 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
92 /* Allocate bitmap to track nodes that have been visited. */
93 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
95 /* None of the nodes in the CFG have been visited yet. */
96 bitmap_clear (visited
);
98 /* Push the first edge on to the stack. */
99 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
107 /* Look at the edge on the top of the stack. */
109 src
= ei_edge (ei
)->src
;
110 dest
= ei_edge (ei
)->dest
;
111 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
113 /* Check if the edge destination has been visited yet. */
114 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && ! bitmap_bit_p (visited
,
117 /* Mark that we have visited the destination. */
118 bitmap_set_bit (visited
, dest
->index
);
120 pre
[dest
->index
] = prenum
++;
121 if (EDGE_COUNT (dest
->succs
) > 0)
123 /* Since the DEST node has been visited for the first
124 time, check its successors. */
125 stack
[sp
++] = ei_start (dest
->succs
);
128 post
[dest
->index
] = postnum
++;
132 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
133 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
134 && pre
[src
->index
] >= pre
[dest
->index
]
135 && post
[dest
->index
] == 0)
136 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
138 if (ei_one_before_end_p (ei
)
139 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
140 post
[src
->index
] = postnum
++;
142 if (!ei_one_before_end_p (ei
))
143 ei_next (&stack
[sp
- 1]);
152 sbitmap_free (visited
);
157 /* Find unreachable blocks. An unreachable block will have 0 in
158 the reachable bit in block->flags. A nonzero value indicates the
159 block is reachable. */
162 find_unreachable_blocks (void)
166 basic_block
*tos
, *worklist
, bb
;
168 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
170 /* Clear all the reachability flags. */
172 FOR_EACH_BB_FN (bb
, cfun
)
173 bb
->flags
&= ~BB_REACHABLE
;
175 /* Add our starting points to the worklist. Almost always there will
176 be only one. It isn't inconceivable that we might one day directly
177 support Fortran alternate entry points. */
179 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
183 /* Mark the block reachable. */
184 e
->dest
->flags
|= BB_REACHABLE
;
187 /* Iterate: find everything reachable from what we've already seen. */
189 while (tos
!= worklist
)
191 basic_block b
= *--tos
;
193 FOR_EACH_EDGE (e
, ei
, b
->succs
)
195 basic_block dest
= e
->dest
;
197 if (!(dest
->flags
& BB_REACHABLE
))
200 dest
->flags
|= BB_REACHABLE
;
208 /* Functions to access an edge list with a vector representation.
209 Enough data is kept such that given an index number, the
210 pred and succ that edge represents can be determined, or
211 given a pred and a succ, its index number can be returned.
212 This allows algorithms which consume a lot of memory to
213 represent the normally full matrix of edge (pred,succ) with a
214 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
215 wasted space in the client code due to sparse flow graphs. */
217 /* This functions initializes the edge list. Basically the entire
218 flowgraph is processed, and all edges are assigned a number,
219 and the data structure is filled in. */
222 create_edge_list (void)
224 struct edge_list
*elist
;
230 /* Determine the number of edges in the flow graph by counting successor
231 edges on each basic block. */
233 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
234 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
236 num_edges
+= EDGE_COUNT (bb
->succs
);
239 elist
= XNEW (struct edge_list
);
240 elist
->num_edges
= num_edges
;
241 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
245 /* Follow successors of blocks, and register these edges. */
246 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
247 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
248 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
249 elist
->index_to_edge
[num_edges
++] = e
;
254 /* This function free's memory associated with an edge list. */
257 free_edge_list (struct edge_list
*elist
)
261 free (elist
->index_to_edge
);
266 /* This function provides debug output showing an edge list. */
269 print_edge_list (FILE *f
, struct edge_list
*elist
)
273 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
274 n_basic_blocks_for_fn (cfun
), elist
->num_edges
);
276 for (x
= 0; x
< elist
->num_edges
; x
++)
278 fprintf (f
, " %-4d - edge(", x
);
279 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
280 fprintf (f
, "entry,");
282 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
284 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
285 fprintf (f
, "exit)\n");
287 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
291 /* This function provides an internal consistency check of an edge list,
292 verifying that all edges are present, and that there are no
296 verify_edge_list (FILE *f
, struct edge_list
*elist
)
298 int pred
, succ
, index
;
300 basic_block bb
, p
, s
;
303 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
304 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
306 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
308 pred
= e
->src
->index
;
309 succ
= e
->dest
->index
;
310 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
311 if (index
== EDGE_INDEX_NO_EDGE
)
313 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
317 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
318 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
319 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
320 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
321 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
322 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
326 /* We've verified that all the edges are in the list, now lets make sure
327 there are no spurious edges in the list. This is an expensive check! */
329 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
330 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
331 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
335 FOR_EACH_EDGE (e
, ei
, p
->succs
)
342 FOR_EACH_EDGE (e
, ei
, s
->preds
)
349 if (EDGE_INDEX (elist
, p
, s
)
350 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
351 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
353 if (EDGE_INDEX (elist
, p
, s
)
354 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
355 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
356 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
361 /* Functions to compute control dependences. */
363 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
365 control_dependences::set_control_dependence_map_bit (basic_block bb
,
368 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
370 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
371 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
374 /* Clear all control dependences for block BB. */
376 control_dependences::clear_control_dependence_bitmap (basic_block bb
)
378 bitmap_clear (control_dependence_map
[bb
->index
]);
381 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
382 This function is necessary because some blocks have negative numbers. */
384 static inline basic_block
385 find_pdom (basic_block block
)
387 gcc_assert (block
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
389 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
390 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
393 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
395 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
400 /* Determine all blocks' control dependences on the given edge with edge_list
401 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
404 control_dependences::find_control_dependence (int edge_index
)
406 basic_block current_block
;
407 basic_block ending_block
;
409 gcc_assert (INDEX_EDGE_PRED_BB (m_el
, edge_index
)
410 != EXIT_BLOCK_PTR_FOR_FN (cfun
));
412 if (INDEX_EDGE_PRED_BB (m_el
, edge_index
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
413 ending_block
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
415 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (m_el
, edge_index
));
417 for (current_block
= INDEX_EDGE_SUCC_BB (m_el
, edge_index
);
418 current_block
!= ending_block
419 && current_block
!= EXIT_BLOCK_PTR_FOR_FN (cfun
);
420 current_block
= find_pdom (current_block
))
422 edge e
= INDEX_EDGE (m_el
, edge_index
);
424 /* For abnormal edges, we don't make current_block control
425 dependent because instructions that throw are always necessary
427 if (e
->flags
& EDGE_ABNORMAL
)
430 set_control_dependence_map_bit (current_block
, edge_index
);
434 /* Record all blocks' control dependences on all edges in the edge
435 list EL, ala Morgan, Section 3.6. */
437 control_dependences::control_dependences (struct edge_list
*edges
)
440 timevar_push (TV_CONTROL_DEPENDENCES
);
441 control_dependence_map
.create (last_basic_block_for_fn (cfun
));
442 for (int i
= 0; i
< last_basic_block_for_fn (cfun
); ++i
)
443 control_dependence_map
.quick_push (BITMAP_ALLOC (NULL
));
444 for (int i
= 0; i
< NUM_EDGES (m_el
); ++i
)
445 find_control_dependence (i
);
446 timevar_pop (TV_CONTROL_DEPENDENCES
);
449 /* Free control dependences and the associated edge list. */
451 control_dependences::~control_dependences ()
453 for (unsigned i
= 0; i
< control_dependence_map
.length (); ++i
)
454 BITMAP_FREE (control_dependence_map
[i
]);
455 control_dependence_map
.release ();
456 free_edge_list (m_el
);
459 /* Returns the bitmap of edges the basic-block I is dependent on. */
462 control_dependences::get_edges_dependent_on (int i
)
464 return control_dependence_map
[i
];
467 /* Returns the edge with index I from the edge list. */
470 control_dependences::get_edge (int i
)
472 return INDEX_EDGE (m_el
, i
);
476 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
477 If no such edge exists, return NULL. */
480 find_edge (basic_block pred
, basic_block succ
)
485 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
487 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
493 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
501 /* This routine will determine what, if any, edge there is between
502 a specified predecessor and successor. */
505 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
509 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
510 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
511 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
514 return (EDGE_INDEX_NO_EDGE
);
517 /* This routine will remove any fake predecessor edges for a basic block.
518 When the edge is removed, it is also removed from whatever successor
522 remove_fake_predecessors (basic_block bb
)
527 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
529 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
536 /* This routine will remove all fake edges from the flow graph. If
537 we remove all fake successors, it will automatically remove all
538 fake predecessors. */
541 remove_fake_edges (void)
545 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
546 remove_fake_predecessors (bb
);
549 /* This routine will remove all fake edges to the EXIT_BLOCK. */
552 remove_fake_exit_edges (void)
554 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun
));
558 /* This function will add a fake edge between any block which has no
559 successors, and the exit block. Some data flow equations require these
563 add_noreturn_fake_exit_edges (void)
567 FOR_EACH_BB_FN (bb
, cfun
)
568 if (EDGE_COUNT (bb
->succs
) == 0)
569 make_single_succ_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
572 /* This function adds a fake edge between any infinite loops to the
573 exit block. Some optimizations require a path from each node to
576 See also Morgan, Figure 3.10, pp. 82-83.
578 The current implementation is ugly, not attempting to minimize the
579 number of inserted fake edges. To reduce the number of fake edges
580 to insert, add fake edges from _innermost_ loops containing only
581 nodes not reachable from the exit block. */
584 connect_infinite_loops_to_exit (void)
586 basic_block unvisited_block
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
587 basic_block deadend_block
;
588 struct depth_first_search_dsS dfs_ds
;
590 /* Perform depth-first search in the reverse graph to find nodes
591 reachable from the exit block. */
592 flow_dfs_compute_reverse_init (&dfs_ds
);
593 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
595 /* Repeatedly add fake edges, updating the unreachable nodes. */
598 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
600 if (!unvisited_block
)
603 deadend_block
= dfs_find_deadend (unvisited_block
);
604 make_edge (deadend_block
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
605 flow_dfs_compute_reverse_add_bb (&dfs_ds
, deadend_block
);
608 flow_dfs_compute_reverse_finish (&dfs_ds
);
612 /* Compute reverse top sort order. This is computing a post order
613 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
614 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
615 true, unreachable blocks are deleted. */
618 post_order_compute (int *post_order
, bool include_entry_exit
,
619 bool delete_unreachable
)
621 edge_iterator
*stack
;
623 int post_order_num
= 0;
627 if (include_entry_exit
)
628 post_order
[post_order_num
++] = EXIT_BLOCK
;
630 /* Allocate stack for back-tracking up CFG. */
631 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
634 /* Allocate bitmap to track nodes that have been visited. */
635 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
637 /* None of the nodes in the CFG have been visited yet. */
638 bitmap_clear (visited
);
640 /* Push the first edge on to the stack. */
641 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
649 /* Look at the edge on the top of the stack. */
651 src
= ei_edge (ei
)->src
;
652 dest
= ei_edge (ei
)->dest
;
654 /* Check if the edge destination has been visited yet. */
655 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
656 && ! bitmap_bit_p (visited
, dest
->index
))
658 /* Mark that we have visited the destination. */
659 bitmap_set_bit (visited
, dest
->index
);
661 if (EDGE_COUNT (dest
->succs
) > 0)
662 /* Since the DEST node has been visited for the first
663 time, check its successors. */
664 stack
[sp
++] = ei_start (dest
->succs
);
666 post_order
[post_order_num
++] = dest
->index
;
670 if (ei_one_before_end_p (ei
)
671 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
672 post_order
[post_order_num
++] = src
->index
;
674 if (!ei_one_before_end_p (ei
))
675 ei_next (&stack
[sp
- 1]);
681 if (include_entry_exit
)
683 post_order
[post_order_num
++] = ENTRY_BLOCK
;
684 count
= post_order_num
;
687 count
= post_order_num
+ 2;
689 /* Delete the unreachable blocks if some were found and we are
690 supposed to do it. */
691 if (delete_unreachable
&& (count
!= n_basic_blocks_for_fn (cfun
)))
695 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
696 != EXIT_BLOCK_PTR_FOR_FN (cfun
); b
= next_bb
)
698 next_bb
= b
->next_bb
;
700 if (!(bitmap_bit_p (visited
, b
->index
)))
701 delete_basic_block (b
);
704 tidy_fallthru_edges ();
708 sbitmap_free (visited
);
709 return post_order_num
;
713 /* Helper routine for inverted_post_order_compute
714 flow_dfs_compute_reverse_execute, and the reverse-CFG
715 deapth first search in dominance.c.
716 BB has to belong to a region of CFG
717 unreachable by inverted traversal from the exit.
718 i.e. there's no control flow path from ENTRY to EXIT
719 that contains this BB.
720 This can happen in two cases - if there's an infinite loop
721 or if there's a block that has no successor
722 (call to a function with no return).
723 Some RTL passes deal with this condition by
724 calling connect_infinite_loops_to_exit () and/or
725 add_noreturn_fake_exit_edges ().
726 However, those methods involve modifying the CFG itself
727 which may not be desirable.
728 Hence, we deal with the infinite loop/no return cases
729 by identifying a unique basic block that can reach all blocks
730 in such a region by inverted traversal.
731 This function returns a basic block that guarantees
732 that all blocks in the region are reachable
733 by starting an inverted traversal from the returned block. */
736 dfs_find_deadend (basic_block bb
)
738 bitmap visited
= BITMAP_ALLOC (NULL
);
742 if (EDGE_COUNT (bb
->succs
) == 0
743 || ! bitmap_set_bit (visited
, bb
->index
))
745 BITMAP_FREE (visited
);
749 bb
= EDGE_SUCC (bb
, 0)->dest
;
756 /* Compute the reverse top sort order of the inverted CFG
757 i.e. starting from the exit block and following the edges backward
758 (from successors to predecessors).
759 This ordering can be used for forward dataflow problems among others.
761 This function assumes that all blocks in the CFG are reachable
762 from the ENTRY (but not necessarily from EXIT).
764 If there's an infinite loop,
765 a simple inverted traversal starting from the blocks
766 with no successors can't visit all blocks.
767 To solve this problem, we first do inverted traversal
768 starting from the blocks with no successor.
769 And if there's any block left that's not visited by the regular
770 inverted traversal from EXIT,
771 those blocks are in such problematic region.
772 Among those, we find one block that has
773 any visited predecessor (which is an entry into such a region),
774 and start looking for a "dead end" from that block
775 and do another inverted traversal from that block. */
778 inverted_post_order_compute (int *post_order
)
781 edge_iterator
*stack
;
783 int post_order_num
= 0;
786 /* Allocate stack for back-tracking up CFG. */
787 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
790 /* Allocate bitmap to track nodes that have been visited. */
791 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
793 /* None of the nodes in the CFG have been visited yet. */
794 bitmap_clear (visited
);
796 /* Put all blocks that have no successor into the initial work list. */
797 FOR_ALL_BB_FN (bb
, cfun
)
798 if (EDGE_COUNT (bb
->succs
) == 0)
800 /* Push the initial edge on to the stack. */
801 if (EDGE_COUNT (bb
->preds
) > 0)
803 stack
[sp
++] = ei_start (bb
->preds
);
804 bitmap_set_bit (visited
, bb
->index
);
810 bool has_unvisited_bb
= false;
812 /* The inverted traversal loop. */
818 /* Look at the edge on the top of the stack. */
820 bb
= ei_edge (ei
)->dest
;
821 pred
= ei_edge (ei
)->src
;
823 /* Check if the predecessor has been visited yet. */
824 if (! bitmap_bit_p (visited
, pred
->index
))
826 /* Mark that we have visited the destination. */
827 bitmap_set_bit (visited
, pred
->index
);
829 if (EDGE_COUNT (pred
->preds
) > 0)
830 /* Since the predecessor node has been visited for the first
831 time, check its predecessors. */
832 stack
[sp
++] = ei_start (pred
->preds
);
834 post_order
[post_order_num
++] = pred
->index
;
838 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
839 && ei_one_before_end_p (ei
))
840 post_order
[post_order_num
++] = bb
->index
;
842 if (!ei_one_before_end_p (ei
))
843 ei_next (&stack
[sp
- 1]);
849 /* Detect any infinite loop and activate the kludge.
850 Note that this doesn't check EXIT_BLOCK itself
851 since EXIT_BLOCK is always added after the outer do-while loop. */
852 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
853 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
854 if (!bitmap_bit_p (visited
, bb
->index
))
856 has_unvisited_bb
= true;
858 if (EDGE_COUNT (bb
->preds
) > 0)
862 basic_block visited_pred
= NULL
;
864 /* Find an already visited predecessor. */
865 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
867 if (bitmap_bit_p (visited
, e
->src
->index
))
868 visited_pred
= e
->src
;
873 basic_block be
= dfs_find_deadend (bb
);
874 gcc_assert (be
!= NULL
);
875 bitmap_set_bit (visited
, be
->index
);
876 stack
[sp
++] = ei_start (be
->preds
);
882 if (has_unvisited_bb
&& sp
== 0)
884 /* No blocks are reachable from EXIT at all.
885 Find a dead-end from the ENTRY, and restart the iteration. */
886 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
887 gcc_assert (be
!= NULL
);
888 bitmap_set_bit (visited
, be
->index
);
889 stack
[sp
++] = ei_start (be
->preds
);
892 /* The only case the below while fires is
893 when there's an infinite loop. */
897 /* EXIT_BLOCK is always included. */
898 post_order
[post_order_num
++] = EXIT_BLOCK
;
901 sbitmap_free (visited
);
902 return post_order_num
;
905 /* Compute the depth first search order of FN and store in the array
906 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
907 reverse completion number for each node. Returns the number of nodes
908 visited. A depth first search tries to get as far away from the starting
909 point as quickly as possible.
911 In case the function has unreachable blocks the number of nodes
912 visited does not include them.
914 pre_order is a really a preorder numbering of the graph.
915 rev_post_order is really a reverse postorder numbering of the graph. */
918 pre_and_rev_post_order_compute_fn (struct function
*fn
,
919 int *pre_order
, int *rev_post_order
,
920 bool include_entry_exit
)
922 edge_iterator
*stack
;
924 int pre_order_num
= 0;
925 int rev_post_order_num
= n_basic_blocks_for_fn (cfun
) - 1;
928 /* Allocate stack for back-tracking up CFG. */
929 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
932 if (include_entry_exit
)
935 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
938 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
941 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
943 /* Allocate bitmap to track nodes that have been visited. */
944 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
946 /* None of the nodes in the CFG have been visited yet. */
947 bitmap_clear (visited
);
949 /* Push the first edge on to the stack. */
950 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
);
958 /* Look at the edge on the top of the stack. */
960 src
= ei_edge (ei
)->src
;
961 dest
= ei_edge (ei
)->dest
;
963 /* Check if the edge destination has been visited yet. */
964 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (fn
)
965 && ! bitmap_bit_p (visited
, dest
->index
))
967 /* Mark that we have visited the destination. */
968 bitmap_set_bit (visited
, dest
->index
);
971 pre_order
[pre_order_num
] = dest
->index
;
975 if (EDGE_COUNT (dest
->succs
) > 0)
976 /* Since the DEST node has been visited for the first
977 time, check its successors. */
978 stack
[sp
++] = ei_start (dest
->succs
);
979 else if (rev_post_order
)
980 /* There are no successors for the DEST node so assign
981 its reverse completion number. */
982 rev_post_order
[rev_post_order_num
--] = dest
->index
;
986 if (ei_one_before_end_p (ei
)
987 && src
!= ENTRY_BLOCK_PTR_FOR_FN (fn
)
989 /* There are no more successors for the SRC node
990 so assign its reverse completion number. */
991 rev_post_order
[rev_post_order_num
--] = src
->index
;
993 if (!ei_one_before_end_p (ei
))
994 ei_next (&stack
[sp
- 1]);
1001 sbitmap_free (visited
);
1003 if (include_entry_exit
)
1006 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1009 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
1012 return pre_order_num
;
1015 /* Like pre_and_rev_post_order_compute_fn but operating on the
1016 current function and asserting that all nodes were visited. */
1019 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
1020 bool include_entry_exit
)
1023 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1024 include_entry_exit
);
1025 if (include_entry_exit
)
1026 /* The number of nodes visited should be the number of blocks. */
1027 gcc_assert (pre_order_num
== n_basic_blocks_for_fn (cfun
));
1029 /* The number of nodes visited should be the number of blocks minus
1030 the entry and exit blocks which are not visited here. */
1031 gcc_assert (pre_order_num
1032 == (n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
));
1034 return pre_order_num
;
1037 /* Compute the depth first search order on the _reverse_ graph and
1038 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1039 Returns the number of nodes visited.
1041 The computation is split into three pieces:
1043 flow_dfs_compute_reverse_init () creates the necessary data
1046 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1047 structures. The block will start the search.
1049 flow_dfs_compute_reverse_execute () continues (or starts) the
1050 search using the block on the top of the stack, stopping when the
1053 flow_dfs_compute_reverse_finish () destroys the necessary data
1056 Thus, the user will probably call ..._init(), call ..._add_bb() to
1057 add a beginning basic block to the stack, call ..._execute(),
1058 possibly add another bb to the stack and again call ..._execute(),
1059 ..., and finally call _finish(). */
1061 /* Initialize the data structures used for depth-first search on the
1062 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1063 added to the basic block stack. DATA is the current depth-first
1064 search context. If INITIALIZE_STACK is nonzero, there is an
1065 element on the stack. */
1068 flow_dfs_compute_reverse_init (depth_first_search_ds data
)
1070 /* Allocate stack for back-tracking up CFG. */
1071 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1074 /* Allocate bitmap to track nodes that have been visited. */
1075 data
->visited_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1077 /* None of the nodes in the CFG have been visited yet. */
1078 bitmap_clear (data
->visited_blocks
);
1083 /* Add the specified basic block to the top of the dfs data
1084 structures. When the search continues, it will start at the
1088 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data
, basic_block bb
)
1090 data
->stack
[data
->sp
++] = bb
;
1091 bitmap_set_bit (data
->visited_blocks
, bb
->index
);
1094 /* Continue the depth-first search through the reverse graph starting with the
1095 block at the stack's top and ending when the stack is empty. Visited nodes
1096 are marked. Returns an unvisited basic block, or NULL if there is none
1100 flow_dfs_compute_reverse_execute (depth_first_search_ds data
,
1101 basic_block last_unvisited
)
1107 while (data
->sp
> 0)
1109 bb
= data
->stack
[--data
->sp
];
1111 /* Perform depth-first search on adjacent vertices. */
1112 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1113 if (!bitmap_bit_p (data
->visited_blocks
, e
->src
->index
))
1114 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1117 /* Determine if there are unvisited basic blocks. */
1118 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1119 if (!bitmap_bit_p (data
->visited_blocks
, bb
->index
))
1125 /* Destroy the data structures needed for depth-first search on the
1129 flow_dfs_compute_reverse_finish (depth_first_search_ds data
)
1132 sbitmap_free (data
->visited_blocks
);
1135 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1136 if REVERSE, go against direction of edges. Returns number of blocks
1137 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1139 dfs_enumerate_from (basic_block bb
, int reverse
,
1140 bool (*predicate
) (const_basic_block
, const void *),
1141 basic_block
*rslt
, int rslt_max
, const void *data
)
1143 basic_block
*st
, lbb
;
1147 /* A bitmap to keep track of visited blocks. Allocating it each time
1148 this function is called is not possible, since dfs_enumerate_from
1149 is often used on small (almost) disjoint parts of cfg (bodies of
1150 loops), and allocating a large sbitmap would lead to quadratic
1152 static sbitmap visited
;
1153 static unsigned v_size
;
1155 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1156 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1157 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1159 /* Resize the VISITED sbitmap if necessary. */
1160 size
= last_basic_block_for_fn (cfun
);
1167 visited
= sbitmap_alloc (size
);
1168 bitmap_clear (visited
);
1171 else if (v_size
< size
)
1173 /* Ensure that we increase the size of the sbitmap exponentially. */
1174 if (2 * v_size
> size
)
1177 visited
= sbitmap_resize (visited
, size
, 0);
1181 st
= XNEWVEC (basic_block
, rslt_max
);
1182 rslt
[tv
++] = st
[sp
++] = bb
;
1191 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1192 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1194 gcc_assert (tv
!= rslt_max
);
1195 rslt
[tv
++] = st
[sp
++] = e
->src
;
1196 MARK_VISITED (e
->src
);
1201 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1202 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1204 gcc_assert (tv
!= rslt_max
);
1205 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1206 MARK_VISITED (e
->dest
);
1211 for (sp
= 0; sp
< tv
; sp
++)
1212 UNMARK_VISITED (rslt
[sp
]);
1215 #undef UNMARK_VISITED
1220 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1222 This algorithm can be found in Timothy Harvey's PhD thesis, at
1223 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1224 dominance algorithms.
1226 First, we identify each join point, j (any node with more than one
1227 incoming edge is a join point).
1229 We then examine each predecessor, p, of j and walk up the dominator tree
1232 We stop the walk when we reach j's immediate dominator - j is in the
1233 dominance frontier of each of the nodes in the walk, except for j's
1234 immediate dominator. Intuitively, all of the rest of j's dominators are
1235 shared by j's predecessors as well.
1236 Since they dominate j, they will not have j in their dominance frontiers.
1238 The number of nodes touched by this algorithm is equal to the size
1239 of the dominance frontiers, no more, no less.
1244 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1249 FOR_EACH_BB_FN (b
, cfun
)
1251 if (EDGE_COUNT (b
->preds
) >= 2)
1253 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1255 basic_block runner
= p
->src
;
1257 if (runner
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1260 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1261 while (runner
!= domsb
)
1263 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1266 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1276 compute_dominance_frontiers (bitmap_head
*frontiers
)
1278 timevar_push (TV_DOM_FRONTIERS
);
1280 compute_dominance_frontiers_1 (frontiers
);
1282 timevar_pop (TV_DOM_FRONTIERS
);
1285 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1286 return a bitmap with all the blocks in the iterated dominance
1287 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1288 frontier information as returned by compute_dominance_frontiers.
1290 The resulting set of blocks are the potential sites where PHI nodes
1291 are needed. The caller is responsible for freeing the memory
1292 allocated for the return value. */
1295 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1298 unsigned bb_index
, i
;
1299 bitmap phi_insertion_points
;
1301 /* Each block can appear at most twice on the work-stack. */
1302 auto_vec
<int> work_stack (2 * n_basic_blocks_for_fn (cfun
));
1303 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1305 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1306 vec::quick_push here for speed. This is safe because we know that
1307 the number of definition blocks is no greater than the number of
1308 basic blocks, which is the initial capacity of WORK_STACK. */
1309 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1310 work_stack
.quick_push (bb_index
);
1312 /* Pop a block off the worklist, add every block that appears in
1313 the original block's DF that we have not already processed to
1314 the worklist. Iterate until the worklist is empty. Blocks
1315 which are added to the worklist are potential sites for
1317 while (work_stack
.length () > 0)
1319 bb_index
= work_stack
.pop ();
1321 /* Since the registration of NEW -> OLD name mappings is done
1322 separately from the call to update_ssa, when updating the SSA
1323 form, the basic blocks where new and/or old names are defined
1324 may have disappeared by CFG cleanup calls. In this case,
1325 we may pull a non-existing block from the work stack. */
1326 gcc_checking_assert (bb_index
1327 < (unsigned) last_basic_block_for_fn (cfun
));
1329 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1332 work_stack
.quick_push (i
);
1333 bitmap_set_bit (phi_insertion_points
, i
);
1337 return phi_insertion_points
;
1340 /* Intersection and union of preds/succs for sbitmap based data flow
1341 solvers. All four functions defined below take the same arguments:
1342 B is the basic block to perform the operation for. DST is the
1343 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1344 last_basic_block so that it can be indexed with basic block indices.
1345 DST may be (but does not have to be) SRC[B->index]. */
1347 /* Set the bitmap DST to the intersection of SRC of successors of
1351 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1353 unsigned int set_size
= dst
->size
;
1357 gcc_assert (!dst
->popcount
);
1359 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1361 e
= EDGE_SUCC (b
, ix
);
1362 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1365 bitmap_copy (dst
, src
[e
->dest
->index
]);
1372 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1375 SBITMAP_ELT_TYPE
*p
, *r
;
1377 e
= EDGE_SUCC (b
, ix
);
1378 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1381 p
= src
[e
->dest
->index
]->elms
;
1383 for (i
= 0; i
< set_size
; i
++)
1388 /* Set the bitmap DST to the intersection of SRC of predecessors of
1392 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1394 unsigned int set_size
= dst
->size
;
1398 gcc_assert (!dst
->popcount
);
1400 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1402 e
= EDGE_PRED (b
, ix
);
1403 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1406 bitmap_copy (dst
, src
[e
->src
->index
]);
1413 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1416 SBITMAP_ELT_TYPE
*p
, *r
;
1418 e
= EDGE_PRED (b
, ix
);
1419 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1422 p
= src
[e
->src
->index
]->elms
;
1424 for (i
= 0; i
< set_size
; i
++)
1429 /* Set the bitmap DST to the union of SRC of successors of
1433 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1435 unsigned int set_size
= dst
->size
;
1439 gcc_assert (!dst
->popcount
);
1441 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1443 e
= EDGE_SUCC (b
, ix
);
1444 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1447 bitmap_copy (dst
, src
[e
->dest
->index
]);
1451 if (ix
== EDGE_COUNT (b
->succs
))
1454 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1457 SBITMAP_ELT_TYPE
*p
, *r
;
1459 e
= EDGE_SUCC (b
, ix
);
1460 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1463 p
= src
[e
->dest
->index
]->elms
;
1465 for (i
= 0; i
< set_size
; i
++)
1470 /* Set the bitmap DST to the union of SRC of predecessors of
1474 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1476 unsigned int set_size
= dst
->size
;
1480 gcc_assert (!dst
->popcount
);
1482 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1484 e
= EDGE_PRED (b
, ix
);
1485 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1488 bitmap_copy (dst
, src
[e
->src
->index
]);
1492 if (ix
== EDGE_COUNT (b
->preds
))
1495 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1498 SBITMAP_ELT_TYPE
*p
, *r
;
1500 e
= EDGE_PRED (b
, ix
);
1501 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1504 p
= src
[e
->src
->index
]->elms
;
1506 for (i
= 0; i
< set_size
; i
++)
1511 /* Returns the list of basic blocks in the function in an order that guarantees
1512 that if a block X has just a single predecessor Y, then Y is after X in the
1516 single_pred_before_succ_order (void)
1519 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1520 unsigned n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1522 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1524 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1525 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1527 bitmap_clear (visited
);
1529 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1530 FOR_EACH_BB_FN (x
, cfun
)
1535 /* Walk the predecessors of x as long as they have precisely one
1536 predecessor and add them to the list, so that they get stored
1539 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1540 y
= single_pred (y
))
1542 for (y
= x
, i
= n
- np
;
1543 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1544 y
= single_pred (y
), i
++)
1552 gcc_assert (i
== n
- 1);
1556 sbitmap_free (visited
);
1557 gcc_assert (n
== 0);