1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2017 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"
32 /* Store the data structures necessary for depth-first search. */
33 class depth_first_search
36 depth_first_search ();
38 basic_block
execute (basic_block
);
39 void add_bb (basic_block
);
42 /* stack for backtracking during the algorithm */
43 auto_vec
<basic_block
, 20> m_stack
;
45 /* record of basic blocks already seen by depth-first search */
46 auto_sbitmap m_visited_blocks
;
50 /* Mark the back edges in DFS traversal.
51 Return nonzero if a loop (natural or otherwise) is present.
52 Inspired by Depth_First_Search_PP described in:
54 Advanced Compiler Design and Implementation
58 and heavily borrowed from pre_and_rev_post_order_compute. */
61 mark_dfs_back_edges (void)
69 /* Allocate the preorder and postorder number arrays. */
70 pre
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
71 post
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
73 /* Allocate stack for back-tracking up CFG. */
74 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
76 /* Allocate bitmap to track nodes that have been visited. */
77 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
79 /* None of the nodes in the CFG have been visited yet. */
80 bitmap_clear (visited
);
82 /* Push the first edge on to the stack. */
83 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
));
85 while (!stack
.is_empty ())
90 /* Look at the edge on the top of the stack. */
91 edge_iterator ei
= stack
.last ();
92 src
= ei_edge (ei
)->src
;
93 dest
= ei_edge (ei
)->dest
;
94 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
96 /* Check if the edge destination has been visited yet. */
97 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && ! bitmap_bit_p (visited
,
100 /* Mark that we have visited the destination. */
101 bitmap_set_bit (visited
, dest
->index
);
103 pre
[dest
->index
] = prenum
++;
104 if (EDGE_COUNT (dest
->succs
) > 0)
106 /* Since the DEST node has been visited for the first
107 time, check its successors. */
108 stack
.quick_push (ei_start (dest
->succs
));
111 post
[dest
->index
] = postnum
++;
115 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
116 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
117 && pre
[src
->index
] >= pre
[dest
->index
]
118 && post
[dest
->index
] == 0)
119 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
121 if (ei_one_before_end_p (ei
)
122 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
123 post
[src
->index
] = postnum
++;
125 if (!ei_one_before_end_p (ei
))
126 ei_next (&stack
.last ());
138 /* Find unreachable blocks. An unreachable block will have 0 in
139 the reachable bit in block->flags. A nonzero value indicates the
140 block is reachable. */
143 find_unreachable_blocks (void)
147 basic_block
*tos
, *worklist
, bb
;
149 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
151 /* Clear all the reachability flags. */
153 FOR_EACH_BB_FN (bb
, cfun
)
154 bb
->flags
&= ~BB_REACHABLE
;
156 /* Add our starting points to the worklist. Almost always there will
157 be only one. It isn't inconceivable that we might one day directly
158 support Fortran alternate entry points. */
160 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
164 /* Mark the block reachable. */
165 e
->dest
->flags
|= BB_REACHABLE
;
168 /* Iterate: find everything reachable from what we've already seen. */
170 while (tos
!= worklist
)
172 basic_block b
= *--tos
;
174 FOR_EACH_EDGE (e
, ei
, b
->succs
)
176 basic_block dest
= e
->dest
;
178 if (!(dest
->flags
& BB_REACHABLE
))
181 dest
->flags
|= BB_REACHABLE
;
189 /* Verify that there are no unreachable blocks in the current function. */
192 verify_no_unreachable_blocks (void)
194 find_unreachable_blocks ();
197 FOR_EACH_BB_FN (bb
, cfun
)
198 gcc_assert ((bb
->flags
& BB_REACHABLE
) != 0);
202 /* Functions to access an edge list with a vector representation.
203 Enough data is kept such that given an index number, the
204 pred and succ that edge represents can be determined, or
205 given a pred and a succ, its index number can be returned.
206 This allows algorithms which consume a lot of memory to
207 represent the normally full matrix of edge (pred,succ) with a
208 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
209 wasted space in the client code due to sparse flow graphs. */
211 /* This functions initializes the edge list. Basically the entire
212 flowgraph is processed, and all edges are assigned a number,
213 and the data structure is filled in. */
216 create_edge_list (void)
218 struct edge_list
*elist
;
224 /* Determine the number of edges in the flow graph by counting successor
225 edges on each basic block. */
227 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
228 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
230 num_edges
+= EDGE_COUNT (bb
->succs
);
233 elist
= XNEW (struct edge_list
);
234 elist
->num_edges
= num_edges
;
235 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
239 /* Follow successors of blocks, and register these edges. */
240 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
241 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
242 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
243 elist
->index_to_edge
[num_edges
++] = e
;
248 /* This function free's memory associated with an edge list. */
251 free_edge_list (struct edge_list
*elist
)
255 free (elist
->index_to_edge
);
260 /* This function provides debug output showing an edge list. */
263 print_edge_list (FILE *f
, struct edge_list
*elist
)
267 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
268 n_basic_blocks_for_fn (cfun
), elist
->num_edges
);
270 for (x
= 0; x
< elist
->num_edges
; x
++)
272 fprintf (f
, " %-4d - edge(", x
);
273 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
274 fprintf (f
, "entry,");
276 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
278 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
279 fprintf (f
, "exit)\n");
281 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
285 /* This function provides an internal consistency check of an edge list,
286 verifying that all edges are present, and that there are no
290 verify_edge_list (FILE *f
, struct edge_list
*elist
)
292 int pred
, succ
, index
;
294 basic_block bb
, p
, s
;
297 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
298 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
300 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
302 pred
= e
->src
->index
;
303 succ
= e
->dest
->index
;
304 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
305 if (index
== EDGE_INDEX_NO_EDGE
)
307 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
311 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
312 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
313 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
314 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
315 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
316 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
320 /* We've verified that all the edges are in the list, now lets make sure
321 there are no spurious edges in the list. This is an expensive check! */
323 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
324 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
325 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
329 FOR_EACH_EDGE (e
, ei
, p
->succs
)
336 FOR_EACH_EDGE (e
, ei
, s
->preds
)
343 if (EDGE_INDEX (elist
, p
, s
)
344 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
345 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
347 if (EDGE_INDEX (elist
, p
, s
)
348 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
349 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
350 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
355 /* Functions to compute control dependences. */
357 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
359 control_dependences::set_control_dependence_map_bit (basic_block bb
,
362 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
364 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
365 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
368 /* Clear all control dependences for block BB. */
370 control_dependences::clear_control_dependence_bitmap (basic_block bb
)
372 bitmap_clear (control_dependence_map
[bb
->index
]);
375 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
376 This function is necessary because some blocks have negative numbers. */
378 static inline basic_block
379 find_pdom (basic_block block
)
381 gcc_assert (block
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
383 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
384 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
387 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
389 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
394 /* Determine all blocks' control dependences on the given edge with edge_list
395 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
398 control_dependences::find_control_dependence (int edge_index
)
400 basic_block current_block
;
401 basic_block ending_block
;
403 gcc_assert (get_edge_src (edge_index
) != EXIT_BLOCK_PTR_FOR_FN (cfun
));
405 /* For abnormal edges, we don't make current_block control
406 dependent because instructions that throw are always necessary
408 edge e
= find_edge (get_edge_src (edge_index
), get_edge_dest (edge_index
));
409 if (e
->flags
& EDGE_ABNORMAL
)
412 if (get_edge_src (edge_index
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
413 ending_block
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
415 ending_block
= find_pdom (get_edge_src (edge_index
));
417 for (current_block
= get_edge_dest (edge_index
);
418 current_block
!= ending_block
419 && current_block
!= EXIT_BLOCK_PTR_FOR_FN (cfun
);
420 current_block
= find_pdom (current_block
))
421 set_control_dependence_map_bit (current_block
, edge_index
);
424 /* Record all blocks' control dependences on all edges in the edge
425 list EL, ala Morgan, Section 3.6. */
427 control_dependences::control_dependences ()
429 timevar_push (TV_CONTROL_DEPENDENCES
);
431 /* Initialize the edge list. */
434 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
435 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
436 num_edges
+= EDGE_COUNT (bb
->succs
);
437 m_el
.create (num_edges
);
440 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
441 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
442 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
443 m_el
.quick_push (std::make_pair (e
->src
->index
, e
->dest
->index
));
445 control_dependence_map
.create (last_basic_block_for_fn (cfun
));
446 for (int i
= 0; i
< last_basic_block_for_fn (cfun
); ++i
)
447 control_dependence_map
.quick_push (BITMAP_ALLOC (NULL
));
448 for (int i
= 0; i
< num_edges
; ++i
)
449 find_control_dependence (i
);
451 timevar_pop (TV_CONTROL_DEPENDENCES
);
454 /* Free control dependences and the associated edge list. */
456 control_dependences::~control_dependences ()
458 for (unsigned i
= 0; i
< control_dependence_map
.length (); ++i
)
459 BITMAP_FREE (control_dependence_map
[i
]);
460 control_dependence_map
.release ();
464 /* Returns the bitmap of edges the basic-block I is dependent on. */
467 control_dependences::get_edges_dependent_on (int i
)
469 return control_dependence_map
[i
];
472 /* Returns the edge source with index I from the edge list. */
475 control_dependences::get_edge_src (int i
)
477 return BASIC_BLOCK_FOR_FN (cfun
, m_el
[i
].first
);
480 /* Returns the edge destination with index I from the edge list. */
483 control_dependences::get_edge_dest (int i
)
485 return BASIC_BLOCK_FOR_FN (cfun
, m_el
[i
].second
);
489 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
490 If no such edge exists, return NULL. */
493 find_edge (basic_block pred
, basic_block succ
)
498 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
500 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
506 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
514 /* This routine will determine what, if any, edge there is between
515 a specified predecessor and successor. */
518 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
522 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
523 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
524 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
527 return (EDGE_INDEX_NO_EDGE
);
530 /* This routine will remove any fake predecessor edges for a basic block.
531 When the edge is removed, it is also removed from whatever successor
535 remove_fake_predecessors (basic_block bb
)
540 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
542 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
549 /* This routine will remove all fake edges from the flow graph. If
550 we remove all fake successors, it will automatically remove all
551 fake predecessors. */
554 remove_fake_edges (void)
558 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
559 remove_fake_predecessors (bb
);
562 /* This routine will remove all fake edges to the EXIT_BLOCK. */
565 remove_fake_exit_edges (void)
567 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun
));
571 /* This function will add a fake edge between any block which has no
572 successors, and the exit block. Some data flow equations require these
576 add_noreturn_fake_exit_edges (void)
580 FOR_EACH_BB_FN (bb
, cfun
)
581 if (EDGE_COUNT (bb
->succs
) == 0)
582 make_single_succ_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
585 /* This function adds a fake edge between any infinite loops to the
586 exit block. Some optimizations require a path from each node to
589 See also Morgan, Figure 3.10, pp. 82-83.
591 The current implementation is ugly, not attempting to minimize the
592 number of inserted fake edges. To reduce the number of fake edges
593 to insert, add fake edges from _innermost_ loops containing only
594 nodes not reachable from the exit block. */
597 connect_infinite_loops_to_exit (void)
599 /* Perform depth-first search in the reverse graph to find nodes
600 reachable from the exit block. */
601 depth_first_search dfs
;
602 dfs
.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
604 /* Repeatedly add fake edges, updating the unreachable nodes. */
605 basic_block unvisited_block
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
608 unvisited_block
= dfs
.execute (unvisited_block
);
609 if (!unvisited_block
)
612 basic_block deadend_block
= dfs_find_deadend (unvisited_block
);
613 make_edge (deadend_block
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
614 dfs
.add_bb (deadend_block
);
618 /* Compute reverse top sort order. This is computing a post order
619 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
620 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
621 true, unreachable blocks are deleted. */
624 post_order_compute (int *post_order
, bool include_entry_exit
,
625 bool delete_unreachable
)
627 int post_order_num
= 0;
630 if (include_entry_exit
)
631 post_order
[post_order_num
++] = EXIT_BLOCK
;
633 /* Allocate stack for back-tracking up CFG. */
634 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
636 /* Allocate bitmap to track nodes that have been visited. */
637 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
639 /* None of the nodes in the CFG have been visited yet. */
640 bitmap_clear (visited
);
642 /* Push the first edge on to the stack. */
643 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
));
645 while (!stack
.is_empty ())
650 /* Look at the edge on the top of the stack. */
651 edge_iterator ei
= stack
.last ();
652 src
= ei_edge (ei
)->src
;
653 dest
= ei_edge (ei
)->dest
;
655 /* Check if the edge destination has been visited yet. */
656 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
657 && ! bitmap_bit_p (visited
, dest
->index
))
659 /* Mark that we have visited the destination. */
660 bitmap_set_bit (visited
, dest
->index
);
662 if (EDGE_COUNT (dest
->succs
) > 0)
663 /* Since the DEST node has been visited for the first
664 time, check its successors. */
665 stack
.quick_push (ei_start (dest
->succs
));
667 post_order
[post_order_num
++] = dest
->index
;
671 if (ei_one_before_end_p (ei
)
672 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
673 post_order
[post_order_num
++] = src
->index
;
675 if (!ei_one_before_end_p (ei
))
676 ei_next (&stack
.last ());
682 if (include_entry_exit
)
684 post_order
[post_order_num
++] = ENTRY_BLOCK
;
685 count
= post_order_num
;
688 count
= post_order_num
+ 2;
690 /* Delete the unreachable blocks if some were found and we are
691 supposed to do it. */
692 if (delete_unreachable
&& (count
!= n_basic_blocks_for_fn (cfun
)))
696 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
697 != EXIT_BLOCK_PTR_FOR_FN (cfun
); b
= next_bb
)
699 next_bb
= b
->next_bb
;
701 if (!(bitmap_bit_p (visited
, b
->index
)))
702 delete_basic_block (b
);
705 tidy_fallthru_edges ();
708 return post_order_num
;
712 /* Helper routine for inverted_post_order_compute
713 flow_dfs_compute_reverse_execute, and the reverse-CFG
714 deapth first search in dominance.c.
715 BB has to belong to a region of CFG
716 unreachable by inverted traversal from the exit.
717 i.e. there's no control flow path from ENTRY to EXIT
718 that contains this BB.
719 This can happen in two cases - if there's an infinite loop
720 or if there's a block that has no successor
721 (call to a function with no return).
722 Some RTL passes deal with this condition by
723 calling connect_infinite_loops_to_exit () and/or
724 add_noreturn_fake_exit_edges ().
725 However, those methods involve modifying the CFG itself
726 which may not be desirable.
727 Hence, we deal with the infinite loop/no return cases
728 by identifying a unique basic block that can reach all blocks
729 in such a region by inverted traversal.
730 This function returns a basic block that guarantees
731 that all blocks in the region are reachable
732 by starting an inverted traversal from the returned block. */
735 dfs_find_deadend (basic_block bb
)
737 bitmap visited
= BITMAP_ALLOC (NULL
);
741 if (EDGE_COUNT (bb
->succs
) == 0
742 || ! bitmap_set_bit (visited
, bb
->index
))
744 BITMAP_FREE (visited
);
748 /* If we are in an analyzed cycle make sure to try exiting it.
749 Note this is a heuristic only and expected to work when loop
750 fixup is needed as well. */
751 if (! bb
->loop_father
752 || ! loop_outer (bb
->loop_father
))
753 bb
= EDGE_SUCC (bb
, 0)->dest
;
758 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
759 if (loop_exit_edge_p (bb
->loop_father
, e
))
761 bb
= e
? e
->dest
: EDGE_SUCC (bb
, 0)->dest
;
769 /* Compute the reverse top sort order of the inverted CFG
770 i.e. starting from the exit block and following the edges backward
771 (from successors to predecessors).
772 This ordering can be used for forward dataflow problems among others.
774 Optionally if START_POINTS is specified, start from exit block and all
775 basic blocks in START_POINTS. This is used by CD-DCE.
777 This function assumes that all blocks in the CFG are reachable
778 from the ENTRY (but not necessarily from EXIT).
780 If there's an infinite loop,
781 a simple inverted traversal starting from the blocks
782 with no successors can't visit all blocks.
783 To solve this problem, we first do inverted traversal
784 starting from the blocks with no successor.
785 And if there's any block left that's not visited by the regular
786 inverted traversal from EXIT,
787 those blocks are in such problematic region.
788 Among those, we find one block that has
789 any visited predecessor (which is an entry into such a region),
790 and start looking for a "dead end" from that block
791 and do another inverted traversal from that block. */
794 inverted_post_order_compute (vec
<int> *post_order
,
795 sbitmap
*start_points
)
798 post_order
->reserve_exact (n_basic_blocks_for_fn (cfun
));
801 verify_no_unreachable_blocks ();
803 /* Allocate stack for back-tracking up CFG. */
804 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
806 /* Allocate bitmap to track nodes that have been visited. */
807 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
809 /* None of the nodes in the CFG have been visited yet. */
810 bitmap_clear (visited
);
814 FOR_ALL_BB_FN (bb
, cfun
)
815 if (bitmap_bit_p (*start_points
, bb
->index
)
816 && EDGE_COUNT (bb
->preds
) > 0)
818 stack
.quick_push (ei_start (bb
->preds
));
819 bitmap_set_bit (visited
, bb
->index
);
821 if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
))
823 stack
.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
));
824 bitmap_set_bit (visited
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->index
);
828 /* Put all blocks that have no successor into the initial work list. */
829 FOR_ALL_BB_FN (bb
, cfun
)
830 if (EDGE_COUNT (bb
->succs
) == 0)
832 /* Push the initial edge on to the stack. */
833 if (EDGE_COUNT (bb
->preds
) > 0)
835 stack
.quick_push (ei_start (bb
->preds
));
836 bitmap_set_bit (visited
, bb
->index
);
842 bool has_unvisited_bb
= false;
844 /* The inverted traversal loop. */
845 while (!stack
.is_empty ())
850 /* Look at the edge on the top of the stack. */
852 bb
= ei_edge (ei
)->dest
;
853 pred
= ei_edge (ei
)->src
;
855 /* Check if the predecessor has been visited yet. */
856 if (! bitmap_bit_p (visited
, pred
->index
))
858 /* Mark that we have visited the destination. */
859 bitmap_set_bit (visited
, pred
->index
);
861 if (EDGE_COUNT (pred
->preds
) > 0)
862 /* Since the predecessor node has been visited for the first
863 time, check its predecessors. */
864 stack
.quick_push (ei_start (pred
->preds
));
866 post_order
->quick_push (pred
->index
);
870 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
871 && ei_one_before_end_p (ei
))
872 post_order
->quick_push (bb
->index
);
874 if (!ei_one_before_end_p (ei
))
875 ei_next (&stack
.last ());
881 /* Detect any infinite loop and activate the kludge.
882 Note that this doesn't check EXIT_BLOCK itself
883 since EXIT_BLOCK is always added after the outer do-while loop. */
884 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
885 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
886 if (!bitmap_bit_p (visited
, bb
->index
))
888 has_unvisited_bb
= true;
890 if (EDGE_COUNT (bb
->preds
) > 0)
894 basic_block visited_pred
= NULL
;
896 /* Find an already visited predecessor. */
897 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
899 if (bitmap_bit_p (visited
, e
->src
->index
))
900 visited_pred
= e
->src
;
905 basic_block be
= dfs_find_deadend (bb
);
906 gcc_assert (be
!= NULL
);
907 bitmap_set_bit (visited
, be
->index
);
908 stack
.quick_push (ei_start (be
->preds
));
914 if (has_unvisited_bb
&& stack
.is_empty ())
916 /* No blocks are reachable from EXIT at all.
917 Find a dead-end from the ENTRY, and restart the iteration. */
918 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
919 gcc_assert (be
!= NULL
);
920 bitmap_set_bit (visited
, be
->index
);
921 stack
.quick_push (ei_start (be
->preds
));
924 /* The only case the below while fires is
925 when there's an infinite loop. */
927 while (!stack
.is_empty ());
929 /* EXIT_BLOCK is always included. */
930 post_order
->quick_push (EXIT_BLOCK
);
933 /* Compute the depth first search order of FN and store in the array
934 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
935 reverse completion number for each node. Returns the number of nodes
936 visited. A depth first search tries to get as far away from the starting
937 point as quickly as possible.
939 In case the function has unreachable blocks the number of nodes
940 visited does not include them.
942 pre_order is a really a preorder numbering of the graph.
943 rev_post_order is really a reverse postorder numbering of the graph. */
946 pre_and_rev_post_order_compute_fn (struct function
*fn
,
947 int *pre_order
, int *rev_post_order
,
948 bool include_entry_exit
)
950 int pre_order_num
= 0;
951 int rev_post_order_num
= n_basic_blocks_for_fn (cfun
) - 1;
953 /* Allocate stack for back-tracking up CFG. */
954 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
956 if (include_entry_exit
)
959 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
962 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
965 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
967 /* Allocate bitmap to track nodes that have been visited. */
968 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
970 /* None of the nodes in the CFG have been visited yet. */
971 bitmap_clear (visited
);
973 /* Push the first edge on to the stack. */
974 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
));
976 while (!stack
.is_empty ())
981 /* Look at the edge on the top of the stack. */
982 edge_iterator ei
= stack
.last ();
983 src
= ei_edge (ei
)->src
;
984 dest
= ei_edge (ei
)->dest
;
986 /* Check if the edge destination has been visited yet. */
987 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (fn
)
988 && ! bitmap_bit_p (visited
, dest
->index
))
990 /* Mark that we have visited the destination. */
991 bitmap_set_bit (visited
, dest
->index
);
994 pre_order
[pre_order_num
] = dest
->index
;
998 if (EDGE_COUNT (dest
->succs
) > 0)
999 /* Since the DEST node has been visited for the first
1000 time, check its successors. */
1001 stack
.quick_push (ei_start (dest
->succs
));
1002 else if (rev_post_order
)
1003 /* There are no successors for the DEST node so assign
1004 its reverse completion number. */
1005 rev_post_order
[rev_post_order_num
--] = dest
->index
;
1009 if (ei_one_before_end_p (ei
)
1010 && src
!= ENTRY_BLOCK_PTR_FOR_FN (fn
)
1012 /* There are no more successors for the SRC node
1013 so assign its reverse completion number. */
1014 rev_post_order
[rev_post_order_num
--] = src
->index
;
1016 if (!ei_one_before_end_p (ei
))
1017 ei_next (&stack
.last ());
1023 if (include_entry_exit
)
1026 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1029 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
1032 return pre_order_num
;
1035 /* Like pre_and_rev_post_order_compute_fn but operating on the
1036 current function and asserting that all nodes were visited. */
1039 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
1040 bool include_entry_exit
)
1043 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1044 include_entry_exit
);
1045 if (include_entry_exit
)
1046 /* The number of nodes visited should be the number of blocks. */
1047 gcc_assert (pre_order_num
== n_basic_blocks_for_fn (cfun
));
1049 /* The number of nodes visited should be the number of blocks minus
1050 the entry and exit blocks which are not visited here. */
1051 gcc_assert (pre_order_num
1052 == (n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
));
1054 return pre_order_num
;
1057 /* Compute the depth first search order on the _reverse_ graph and
1058 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1059 Returns the number of nodes visited.
1061 The computation is split into three pieces:
1063 flow_dfs_compute_reverse_init () creates the necessary data
1066 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1067 structures. The block will start the search.
1069 flow_dfs_compute_reverse_execute () continues (or starts) the
1070 search using the block on the top of the stack, stopping when the
1073 flow_dfs_compute_reverse_finish () destroys the necessary data
1076 Thus, the user will probably call ..._init(), call ..._add_bb() to
1077 add a beginning basic block to the stack, call ..._execute(),
1078 possibly add another bb to the stack and again call ..._execute(),
1079 ..., and finally call _finish(). */
1081 /* Initialize the data structures used for depth-first search on the
1082 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1083 added to the basic block stack. DATA is the current depth-first
1084 search context. If INITIALIZE_STACK is nonzero, there is an
1085 element on the stack. */
1087 depth_first_search::depth_first_search () :
1088 m_stack (n_basic_blocks_for_fn (cfun
)),
1089 m_visited_blocks (last_basic_block_for_fn (cfun
))
1091 bitmap_clear (m_visited_blocks
);
1094 /* Add the specified basic block to the top of the dfs data
1095 structures. When the search continues, it will start at the
1099 depth_first_search::add_bb (basic_block bb
)
1101 m_stack
.quick_push (bb
);
1102 bitmap_set_bit (m_visited_blocks
, bb
->index
);
1105 /* Continue the depth-first search through the reverse graph starting with the
1106 block at the stack's top and ending when the stack is empty. Visited nodes
1107 are marked. Returns an unvisited basic block, or NULL if there is none
1111 depth_first_search::execute (basic_block last_unvisited
)
1117 while (!m_stack
.is_empty ())
1119 bb
= m_stack
.pop ();
1121 /* Perform depth-first search on adjacent vertices. */
1122 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1123 if (!bitmap_bit_p (m_visited_blocks
, e
->src
->index
))
1127 /* Determine if there are unvisited basic blocks. */
1128 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1129 if (!bitmap_bit_p (m_visited_blocks
, bb
->index
))
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 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1359 e
= EDGE_SUCC (b
, ix
);
1360 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1363 bitmap_copy (dst
, src
[e
->dest
->index
]);
1370 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1373 SBITMAP_ELT_TYPE
*p
, *r
;
1375 e
= EDGE_SUCC (b
, ix
);
1376 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1379 p
= src
[e
->dest
->index
]->elms
;
1381 for (i
= 0; i
< set_size
; i
++)
1386 /* Set the bitmap DST to the intersection of SRC of predecessors of
1390 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1392 unsigned int set_size
= dst
->size
;
1396 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1398 e
= EDGE_PRED (b
, ix
);
1399 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1402 bitmap_copy (dst
, src
[e
->src
->index
]);
1409 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1412 SBITMAP_ELT_TYPE
*p
, *r
;
1414 e
= EDGE_PRED (b
, ix
);
1415 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1418 p
= src
[e
->src
->index
]->elms
;
1420 for (i
= 0; i
< set_size
; i
++)
1425 /* Set the bitmap DST to the union of SRC of successors of
1429 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1431 unsigned int set_size
= dst
->size
;
1435 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1437 e
= EDGE_SUCC (b
, ix
);
1438 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1441 bitmap_copy (dst
, src
[e
->dest
->index
]);
1445 if (ix
== EDGE_COUNT (b
->succs
))
1448 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1451 SBITMAP_ELT_TYPE
*p
, *r
;
1453 e
= EDGE_SUCC (b
, ix
);
1454 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1457 p
= src
[e
->dest
->index
]->elms
;
1459 for (i
= 0; i
< set_size
; i
++)
1464 /* Set the bitmap DST to the union of SRC of predecessors of
1468 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1470 unsigned int set_size
= dst
->size
;
1474 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1476 e
= EDGE_PRED (b
, ix
);
1477 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1480 bitmap_copy (dst
, src
[e
->src
->index
]);
1484 if (ix
== EDGE_COUNT (b
->preds
))
1487 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1490 SBITMAP_ELT_TYPE
*p
, *r
;
1492 e
= EDGE_PRED (b
, ix
);
1493 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1496 p
= src
[e
->src
->index
]->elms
;
1498 for (i
= 0; i
< set_size
; i
++)
1503 /* Returns the list of basic blocks in the function in an order that guarantees
1504 that if a block X has just a single predecessor Y, then Y is after X in the
1508 single_pred_before_succ_order (void)
1511 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1512 unsigned n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1514 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
1516 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1517 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1519 bitmap_clear (visited
);
1521 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1522 FOR_EACH_BB_FN (x
, cfun
)
1527 /* Walk the predecessors of x as long as they have precisely one
1528 predecessor and add them to the list, so that they get stored
1531 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1532 y
= single_pred (y
))
1534 for (y
= x
, i
= n
- np
;
1535 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1536 y
= single_pred (y
), i
++)
1544 gcc_assert (i
== n
- 1);
1548 gcc_assert (n
== 0);