1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2016 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"
31 /* Store the data structures necessary for depth-first search. */
32 struct depth_first_search_ds
{
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
;
44 static void flow_dfs_compute_reverse_init (depth_first_search_ds
*);
45 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds
*,
47 static basic_block
flow_dfs_compute_reverse_execute (depth_first_search_ds
*,
49 static void flow_dfs_compute_reverse_finish (depth_first_search_ds
*);
51 /* Mark the back edges in DFS traversal.
52 Return nonzero if a loop (natural or otherwise) is present.
53 Inspired by Depth_First_Search_PP described in:
55 Advanced Compiler Design and Implementation
59 and heavily borrowed from pre_and_rev_post_order_compute. */
62 mark_dfs_back_edges (void)
73 /* Allocate the preorder and postorder number arrays. */
74 pre
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
75 post
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
77 /* Allocate stack for back-tracking up CFG. */
78 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
81 /* Allocate bitmap to track nodes that have been visited. */
82 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
84 /* None of the nodes in the CFG have been visited yet. */
85 bitmap_clear (visited
);
87 /* Push the first edge on to the stack. */
88 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
96 /* Look at the edge on the top of the stack. */
98 src
= ei_edge (ei
)->src
;
99 dest
= ei_edge (ei
)->dest
;
100 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
102 /* Check if the edge destination has been visited yet. */
103 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && ! bitmap_bit_p (visited
,
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_FOR_FN (cfun
)
122 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
123 && pre
[src
->index
] >= pre
[dest
->index
]
124 && post
[dest
->index
] == 0)
125 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
127 if (ei_one_before_end_p (ei
)
128 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
129 post
[src
->index
] = postnum
++;
131 if (!ei_one_before_end_p (ei
))
132 ei_next (&stack
[sp
- 1]);
141 sbitmap_free (visited
);
146 /* Find unreachable blocks. An unreachable block will have 0 in
147 the reachable bit in block->flags. A nonzero value indicates the
148 block is reachable. */
151 find_unreachable_blocks (void)
155 basic_block
*tos
, *worklist
, bb
;
157 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
159 /* Clear all the reachability flags. */
161 FOR_EACH_BB_FN (bb
, cfun
)
162 bb
->flags
&= ~BB_REACHABLE
;
164 /* Add our starting points to the worklist. Almost always there will
165 be only one. It isn't inconceivable that we might one day directly
166 support Fortran alternate entry points. */
168 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
172 /* Mark the block reachable. */
173 e
->dest
->flags
|= BB_REACHABLE
;
176 /* Iterate: find everything reachable from what we've already seen. */
178 while (tos
!= worklist
)
180 basic_block b
= *--tos
;
182 FOR_EACH_EDGE (e
, ei
, b
->succs
)
184 basic_block dest
= e
->dest
;
186 if (!(dest
->flags
& BB_REACHABLE
))
189 dest
->flags
|= BB_REACHABLE
;
197 /* Verify that there are no unreachable blocks in the current function. */
200 verify_no_unreachable_blocks (void)
202 find_unreachable_blocks ();
205 FOR_EACH_BB_FN (bb
, cfun
)
206 gcc_assert ((bb
->flags
& BB_REACHABLE
) != 0);
210 /* Functions to access an edge list with a vector representation.
211 Enough data is kept such that given an index number, the
212 pred and succ that edge represents can be determined, or
213 given a pred and a succ, its index number can be returned.
214 This allows algorithms which consume a lot of memory to
215 represent the normally full matrix of edge (pred,succ) with a
216 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
217 wasted space in the client code due to sparse flow graphs. */
219 /* This functions initializes the edge list. Basically the entire
220 flowgraph is processed, and all edges are assigned a number,
221 and the data structure is filled in. */
224 create_edge_list (void)
226 struct edge_list
*elist
;
232 /* Determine the number of edges in the flow graph by counting successor
233 edges on each basic block. */
235 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
236 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
238 num_edges
+= EDGE_COUNT (bb
->succs
);
241 elist
= XNEW (struct edge_list
);
242 elist
->num_edges
= num_edges
;
243 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
247 /* Follow successors of blocks, and register these edges. */
248 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
249 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
250 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
251 elist
->index_to_edge
[num_edges
++] = e
;
256 /* This function free's memory associated with an edge list. */
259 free_edge_list (struct edge_list
*elist
)
263 free (elist
->index_to_edge
);
268 /* This function provides debug output showing an edge list. */
271 print_edge_list (FILE *f
, struct edge_list
*elist
)
275 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
276 n_basic_blocks_for_fn (cfun
), elist
->num_edges
);
278 for (x
= 0; x
< elist
->num_edges
; x
++)
280 fprintf (f
, " %-4d - edge(", x
);
281 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
282 fprintf (f
, "entry,");
284 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
286 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
287 fprintf (f
, "exit)\n");
289 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
293 /* This function provides an internal consistency check of an edge list,
294 verifying that all edges are present, and that there are no
298 verify_edge_list (FILE *f
, struct edge_list
*elist
)
300 int pred
, succ
, index
;
302 basic_block bb
, p
, s
;
305 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
306 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
308 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
310 pred
= e
->src
->index
;
311 succ
= e
->dest
->index
;
312 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
313 if (index
== EDGE_INDEX_NO_EDGE
)
315 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
319 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
320 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
321 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
322 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
323 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
324 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
328 /* We've verified that all the edges are in the list, now lets make sure
329 there are no spurious edges in the list. This is an expensive check! */
331 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
332 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
333 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
337 FOR_EACH_EDGE (e
, ei
, p
->succs
)
344 FOR_EACH_EDGE (e
, ei
, s
->preds
)
351 if (EDGE_INDEX (elist
, p
, s
)
352 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
353 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
355 if (EDGE_INDEX (elist
, p
, s
)
356 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
357 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
358 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
363 /* Functions to compute control dependences. */
365 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
367 control_dependences::set_control_dependence_map_bit (basic_block bb
,
370 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
372 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
373 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
376 /* Clear all control dependences for block BB. */
378 control_dependences::clear_control_dependence_bitmap (basic_block bb
)
380 bitmap_clear (control_dependence_map
[bb
->index
]);
383 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
384 This function is necessary because some blocks have negative numbers. */
386 static inline basic_block
387 find_pdom (basic_block block
)
389 gcc_assert (block
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
391 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
392 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
395 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
397 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
402 /* Determine all blocks' control dependences on the given edge with edge_list
403 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
406 control_dependences::find_control_dependence (int edge_index
)
408 basic_block current_block
;
409 basic_block ending_block
;
411 gcc_assert (INDEX_EDGE_PRED_BB (m_el
, edge_index
)
412 != EXIT_BLOCK_PTR_FOR_FN (cfun
));
414 if (INDEX_EDGE_PRED_BB (m_el
, edge_index
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
415 ending_block
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
417 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (m_el
, edge_index
));
419 for (current_block
= INDEX_EDGE_SUCC_BB (m_el
, edge_index
);
420 current_block
!= ending_block
421 && current_block
!= EXIT_BLOCK_PTR_FOR_FN (cfun
);
422 current_block
= find_pdom (current_block
))
424 edge e
= INDEX_EDGE (m_el
, edge_index
);
426 /* For abnormal edges, we don't make current_block control
427 dependent because instructions that throw are always necessary
429 if (e
->flags
& EDGE_ABNORMAL
)
432 set_control_dependence_map_bit (current_block
, edge_index
);
436 /* Record all blocks' control dependences on all edges in the edge
437 list EL, ala Morgan, Section 3.6. */
439 control_dependences::control_dependences (struct edge_list
*edges
)
442 timevar_push (TV_CONTROL_DEPENDENCES
);
443 control_dependence_map
.create (last_basic_block_for_fn (cfun
));
444 for (int i
= 0; i
< last_basic_block_for_fn (cfun
); ++i
)
445 control_dependence_map
.quick_push (BITMAP_ALLOC (NULL
));
446 for (int i
= 0; i
< NUM_EDGES (m_el
); ++i
)
447 find_control_dependence (i
);
448 timevar_pop (TV_CONTROL_DEPENDENCES
);
451 /* Free control dependences and the associated edge list. */
453 control_dependences::~control_dependences ()
455 for (unsigned i
= 0; i
< control_dependence_map
.length (); ++i
)
456 BITMAP_FREE (control_dependence_map
[i
]);
457 control_dependence_map
.release ();
458 free_edge_list (m_el
);
461 /* Returns the bitmap of edges the basic-block I is dependent on. */
464 control_dependences::get_edges_dependent_on (int i
)
466 return control_dependence_map
[i
];
469 /* Returns the edge with index I from the edge list. */
472 control_dependences::get_edge (int i
)
474 return INDEX_EDGE (m_el
, i
);
478 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
479 If no such edge exists, return NULL. */
482 find_edge (basic_block pred
, basic_block succ
)
487 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
489 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
495 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
503 /* This routine will determine what, if any, edge there is between
504 a specified predecessor and successor. */
507 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
511 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
512 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
513 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
516 return (EDGE_INDEX_NO_EDGE
);
519 /* This routine will remove any fake predecessor edges for a basic block.
520 When the edge is removed, it is also removed from whatever successor
524 remove_fake_predecessors (basic_block bb
)
529 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
531 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
538 /* This routine will remove all fake edges from the flow graph. If
539 we remove all fake successors, it will automatically remove all
540 fake predecessors. */
543 remove_fake_edges (void)
547 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
548 remove_fake_predecessors (bb
);
551 /* This routine will remove all fake edges to the EXIT_BLOCK. */
554 remove_fake_exit_edges (void)
556 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun
));
560 /* This function will add a fake edge between any block which has no
561 successors, and the exit block. Some data flow equations require these
565 add_noreturn_fake_exit_edges (void)
569 FOR_EACH_BB_FN (bb
, cfun
)
570 if (EDGE_COUNT (bb
->succs
) == 0)
571 make_single_succ_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
574 /* This function adds a fake edge between any infinite loops to the
575 exit block. Some optimizations require a path from each node to
578 See also Morgan, Figure 3.10, pp. 82-83.
580 The current implementation is ugly, not attempting to minimize the
581 number of inserted fake edges. To reduce the number of fake edges
582 to insert, add fake edges from _innermost_ loops containing only
583 nodes not reachable from the exit block. */
586 connect_infinite_loops_to_exit (void)
588 basic_block unvisited_block
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
589 basic_block deadend_block
;
590 depth_first_search_ds dfs_ds
;
592 /* Perform depth-first search in the reverse graph to find nodes
593 reachable from the exit block. */
594 flow_dfs_compute_reverse_init (&dfs_ds
);
595 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
597 /* Repeatedly add fake edges, updating the unreachable nodes. */
600 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
602 if (!unvisited_block
)
605 deadend_block
= dfs_find_deadend (unvisited_block
);
606 make_edge (deadend_block
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
607 flow_dfs_compute_reverse_add_bb (&dfs_ds
, deadend_block
);
610 flow_dfs_compute_reverse_finish (&dfs_ds
);
614 /* Compute reverse top sort order. This is computing a post order
615 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
616 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
617 true, unreachable blocks are deleted. */
620 post_order_compute (int *post_order
, bool include_entry_exit
,
621 bool delete_unreachable
)
623 edge_iterator
*stack
;
625 int post_order_num
= 0;
629 if (include_entry_exit
)
630 post_order
[post_order_num
++] = EXIT_BLOCK
;
632 /* Allocate stack for back-tracking up CFG. */
633 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
636 /* Allocate bitmap to track nodes that have been visited. */
637 visited
= sbitmap_alloc (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
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
651 /* Look at the edge on the top of the stack. */
653 src
= ei_edge (ei
)->src
;
654 dest
= ei_edge (ei
)->dest
;
656 /* Check if the edge destination has been visited yet. */
657 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
658 && ! bitmap_bit_p (visited
, dest
->index
))
660 /* Mark that we have visited the destination. */
661 bitmap_set_bit (visited
, dest
->index
);
663 if (EDGE_COUNT (dest
->succs
) > 0)
664 /* Since the DEST node has been visited for the first
665 time, check its successors. */
666 stack
[sp
++] = ei_start (dest
->succs
);
668 post_order
[post_order_num
++] = dest
->index
;
672 if (ei_one_before_end_p (ei
)
673 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
674 post_order
[post_order_num
++] = src
->index
;
676 if (!ei_one_before_end_p (ei
))
677 ei_next (&stack
[sp
- 1]);
683 if (include_entry_exit
)
685 post_order
[post_order_num
++] = ENTRY_BLOCK
;
686 count
= post_order_num
;
689 count
= post_order_num
+ 2;
691 /* Delete the unreachable blocks if some were found and we are
692 supposed to do it. */
693 if (delete_unreachable
&& (count
!= n_basic_blocks_for_fn (cfun
)))
697 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
698 != EXIT_BLOCK_PTR_FOR_FN (cfun
); b
= next_bb
)
700 next_bb
= b
->next_bb
;
702 if (!(bitmap_bit_p (visited
, b
->index
)))
703 delete_basic_block (b
);
706 tidy_fallthru_edges ();
710 sbitmap_free (visited
);
711 return post_order_num
;
715 /* Helper routine for inverted_post_order_compute
716 flow_dfs_compute_reverse_execute, and the reverse-CFG
717 deapth first search in dominance.c.
718 BB has to belong to a region of CFG
719 unreachable by inverted traversal from the exit.
720 i.e. there's no control flow path from ENTRY to EXIT
721 that contains this BB.
722 This can happen in two cases - if there's an infinite loop
723 or if there's a block that has no successor
724 (call to a function with no return).
725 Some RTL passes deal with this condition by
726 calling connect_infinite_loops_to_exit () and/or
727 add_noreturn_fake_exit_edges ().
728 However, those methods involve modifying the CFG itself
729 which may not be desirable.
730 Hence, we deal with the infinite loop/no return cases
731 by identifying a unique basic block that can reach all blocks
732 in such a region by inverted traversal.
733 This function returns a basic block that guarantees
734 that all blocks in the region are reachable
735 by starting an inverted traversal from the returned block. */
738 dfs_find_deadend (basic_block bb
)
740 bitmap visited
= BITMAP_ALLOC (NULL
);
744 if (EDGE_COUNT (bb
->succs
) == 0
745 || ! bitmap_set_bit (visited
, bb
->index
))
747 BITMAP_FREE (visited
);
751 /* If we are in an analyzed cycle make sure to try exiting it.
752 Note this is a heuristic only and expected to work when loop
753 fixup is needed as well. */
754 if (! bb
->loop_father
755 || ! loop_outer (bb
->loop_father
))
756 bb
= EDGE_SUCC (bb
, 0)->dest
;
761 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
762 if (loop_exit_edge_p (bb
->loop_father
, e
))
764 bb
= e
? e
->dest
: EDGE_SUCC (bb
, 0)->dest
;
772 /* Compute the reverse top sort order of the inverted CFG
773 i.e. starting from the exit block and following the edges backward
774 (from successors to predecessors).
775 This ordering can be used for forward dataflow problems among others.
777 Optionally if START_POINTS is specified, start from exit block and all
778 basic blocks in START_POINTS. This is used by CD-DCE.
780 This function assumes that all blocks in the CFG are reachable
781 from the ENTRY (but not necessarily from EXIT).
783 If there's an infinite loop,
784 a simple inverted traversal starting from the blocks
785 with no successors can't visit all blocks.
786 To solve this problem, we first do inverted traversal
787 starting from the blocks with no successor.
788 And if there's any block left that's not visited by the regular
789 inverted traversal from EXIT,
790 those blocks are in such problematic region.
791 Among those, we find one block that has
792 any visited predecessor (which is an entry into such a region),
793 and start looking for a "dead end" from that block
794 and do another inverted traversal from that block. */
797 inverted_post_order_compute (int *post_order
,
798 sbitmap
*start_points
)
801 edge_iterator
*stack
;
803 int post_order_num
= 0;
807 verify_no_unreachable_blocks ();
809 /* Allocate stack for back-tracking up CFG. */
810 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
813 /* Allocate bitmap to track nodes that have been visited. */
814 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
816 /* None of the nodes in the CFG have been visited yet. */
817 bitmap_clear (visited
);
821 FOR_ALL_BB_FN (bb
, cfun
)
822 if (bitmap_bit_p (*start_points
, bb
->index
)
823 && EDGE_COUNT (bb
->preds
) > 0)
825 stack
[sp
++] = ei_start (bb
->preds
);
826 bitmap_set_bit (visited
, bb
->index
);
828 if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
))
830 stack
[sp
++] = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
831 bitmap_set_bit (visited
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->index
);
835 /* Put all blocks that have no successor into the initial work list. */
836 FOR_ALL_BB_FN (bb
, cfun
)
837 if (EDGE_COUNT (bb
->succs
) == 0)
839 /* Push the initial edge on to the stack. */
840 if (EDGE_COUNT (bb
->preds
) > 0)
842 stack
[sp
++] = ei_start (bb
->preds
);
843 bitmap_set_bit (visited
, bb
->index
);
849 bool has_unvisited_bb
= false;
851 /* The inverted traversal loop. */
857 /* Look at the edge on the top of the stack. */
859 bb
= ei_edge (ei
)->dest
;
860 pred
= ei_edge (ei
)->src
;
862 /* Check if the predecessor has been visited yet. */
863 if (! bitmap_bit_p (visited
, pred
->index
))
865 /* Mark that we have visited the destination. */
866 bitmap_set_bit (visited
, pred
->index
);
868 if (EDGE_COUNT (pred
->preds
) > 0)
869 /* Since the predecessor node has been visited for the first
870 time, check its predecessors. */
871 stack
[sp
++] = ei_start (pred
->preds
);
873 post_order
[post_order_num
++] = pred
->index
;
877 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
878 && ei_one_before_end_p (ei
))
879 post_order
[post_order_num
++] = bb
->index
;
881 if (!ei_one_before_end_p (ei
))
882 ei_next (&stack
[sp
- 1]);
888 /* Detect any infinite loop and activate the kludge.
889 Note that this doesn't check EXIT_BLOCK itself
890 since EXIT_BLOCK is always added after the outer do-while loop. */
891 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
892 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
893 if (!bitmap_bit_p (visited
, bb
->index
))
895 has_unvisited_bb
= true;
897 if (EDGE_COUNT (bb
->preds
) > 0)
901 basic_block visited_pred
= NULL
;
903 /* Find an already visited predecessor. */
904 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
906 if (bitmap_bit_p (visited
, e
->src
->index
))
907 visited_pred
= e
->src
;
912 basic_block be
= dfs_find_deadend (bb
);
913 gcc_assert (be
!= NULL
);
914 bitmap_set_bit (visited
, be
->index
);
915 stack
[sp
++] = ei_start (be
->preds
);
921 if (has_unvisited_bb
&& sp
== 0)
923 /* No blocks are reachable from EXIT at all.
924 Find a dead-end from the ENTRY, and restart the iteration. */
925 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
926 gcc_assert (be
!= NULL
);
927 bitmap_set_bit (visited
, be
->index
);
928 stack
[sp
++] = ei_start (be
->preds
);
931 /* The only case the below while fires is
932 when there's an infinite loop. */
936 /* EXIT_BLOCK is always included. */
937 post_order
[post_order_num
++] = EXIT_BLOCK
;
940 sbitmap_free (visited
);
941 return post_order_num
;
944 /* Compute the depth first search order of FN and store in the array
945 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
946 reverse completion number for each node. Returns the number of nodes
947 visited. A depth first search tries to get as far away from the starting
948 point as quickly as possible.
950 In case the function has unreachable blocks the number of nodes
951 visited does not include them.
953 pre_order is a really a preorder numbering of the graph.
954 rev_post_order is really a reverse postorder numbering of the graph. */
957 pre_and_rev_post_order_compute_fn (struct function
*fn
,
958 int *pre_order
, int *rev_post_order
,
959 bool include_entry_exit
)
961 edge_iterator
*stack
;
963 int pre_order_num
= 0;
964 int rev_post_order_num
= n_basic_blocks_for_fn (cfun
) - 1;
967 /* Allocate stack for back-tracking up CFG. */
968 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
971 if (include_entry_exit
)
974 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
977 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
980 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
982 /* Allocate bitmap to track nodes that have been visited. */
983 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
985 /* None of the nodes in the CFG have been visited yet. */
986 bitmap_clear (visited
);
988 /* Push the first edge on to the stack. */
989 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
);
997 /* Look at the edge on the top of the stack. */
999 src
= ei_edge (ei
)->src
;
1000 dest
= ei_edge (ei
)->dest
;
1002 /* Check if the edge destination has been visited yet. */
1003 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (fn
)
1004 && ! bitmap_bit_p (visited
, dest
->index
))
1006 /* Mark that we have visited the destination. */
1007 bitmap_set_bit (visited
, dest
->index
);
1010 pre_order
[pre_order_num
] = dest
->index
;
1014 if (EDGE_COUNT (dest
->succs
) > 0)
1015 /* Since the DEST node has been visited for the first
1016 time, check its successors. */
1017 stack
[sp
++] = ei_start (dest
->succs
);
1018 else if (rev_post_order
)
1019 /* There are no successors for the DEST node so assign
1020 its reverse completion number. */
1021 rev_post_order
[rev_post_order_num
--] = dest
->index
;
1025 if (ei_one_before_end_p (ei
)
1026 && src
!= ENTRY_BLOCK_PTR_FOR_FN (fn
)
1028 /* There are no more successors for the SRC node
1029 so assign its reverse completion number. */
1030 rev_post_order
[rev_post_order_num
--] = src
->index
;
1032 if (!ei_one_before_end_p (ei
))
1033 ei_next (&stack
[sp
- 1]);
1040 sbitmap_free (visited
);
1042 if (include_entry_exit
)
1045 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1048 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
1051 return pre_order_num
;
1054 /* Like pre_and_rev_post_order_compute_fn but operating on the
1055 current function and asserting that all nodes were visited. */
1058 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
1059 bool include_entry_exit
)
1062 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1063 include_entry_exit
);
1064 if (include_entry_exit
)
1065 /* The number of nodes visited should be the number of blocks. */
1066 gcc_assert (pre_order_num
== n_basic_blocks_for_fn (cfun
));
1068 /* The number of nodes visited should be the number of blocks minus
1069 the entry and exit blocks which are not visited here. */
1070 gcc_assert (pre_order_num
1071 == (n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
));
1073 return pre_order_num
;
1076 /* Compute the depth first search order on the _reverse_ graph and
1077 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1078 Returns the number of nodes visited.
1080 The computation is split into three pieces:
1082 flow_dfs_compute_reverse_init () creates the necessary data
1085 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1086 structures. The block will start the search.
1088 flow_dfs_compute_reverse_execute () continues (or starts) the
1089 search using the block on the top of the stack, stopping when the
1092 flow_dfs_compute_reverse_finish () destroys the necessary data
1095 Thus, the user will probably call ..._init(), call ..._add_bb() to
1096 add a beginning basic block to the stack, call ..._execute(),
1097 possibly add another bb to the stack and again call ..._execute(),
1098 ..., and finally call _finish(). */
1100 /* Initialize the data structures used for depth-first search on the
1101 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1102 added to the basic block stack. DATA is the current depth-first
1103 search context. If INITIALIZE_STACK is nonzero, there is an
1104 element on the stack. */
1107 flow_dfs_compute_reverse_init (depth_first_search_ds
*data
)
1109 /* Allocate stack for back-tracking up CFG. */
1110 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1113 /* Allocate bitmap to track nodes that have been visited. */
1114 data
->visited_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1116 /* None of the nodes in the CFG have been visited yet. */
1117 bitmap_clear (data
->visited_blocks
);
1122 /* Add the specified basic block to the top of the dfs data
1123 structures. When the search continues, it will start at the
1127 flow_dfs_compute_reverse_add_bb (depth_first_search_ds
*data
, basic_block bb
)
1129 data
->stack
[data
->sp
++] = bb
;
1130 bitmap_set_bit (data
->visited_blocks
, bb
->index
);
1133 /* Continue the depth-first search through the reverse graph starting with the
1134 block at the stack's top and ending when the stack is empty. Visited nodes
1135 are marked. Returns an unvisited basic block, or NULL if there is none
1139 flow_dfs_compute_reverse_execute (depth_first_search_ds
*data
,
1140 basic_block last_unvisited
)
1146 while (data
->sp
> 0)
1148 bb
= data
->stack
[--data
->sp
];
1150 /* Perform depth-first search on adjacent vertices. */
1151 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1152 if (!bitmap_bit_p (data
->visited_blocks
, e
->src
->index
))
1153 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1156 /* Determine if there are unvisited basic blocks. */
1157 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1158 if (!bitmap_bit_p (data
->visited_blocks
, bb
->index
))
1164 /* Destroy the data structures needed for depth-first search on the
1168 flow_dfs_compute_reverse_finish (depth_first_search_ds
*data
)
1171 sbitmap_free (data
->visited_blocks
);
1174 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1175 if REVERSE, go against direction of edges. Returns number of blocks
1176 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1178 dfs_enumerate_from (basic_block bb
, int reverse
,
1179 bool (*predicate
) (const_basic_block
, const void *),
1180 basic_block
*rslt
, int rslt_max
, const void *data
)
1182 basic_block
*st
, lbb
;
1186 /* A bitmap to keep track of visited blocks. Allocating it each time
1187 this function is called is not possible, since dfs_enumerate_from
1188 is often used on small (almost) disjoint parts of cfg (bodies of
1189 loops), and allocating a large sbitmap would lead to quadratic
1191 static sbitmap visited
;
1192 static unsigned v_size
;
1194 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1195 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1196 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1198 /* Resize the VISITED sbitmap if necessary. */
1199 size
= last_basic_block_for_fn (cfun
);
1206 visited
= sbitmap_alloc (size
);
1207 bitmap_clear (visited
);
1210 else if (v_size
< size
)
1212 /* Ensure that we increase the size of the sbitmap exponentially. */
1213 if (2 * v_size
> size
)
1216 visited
= sbitmap_resize (visited
, size
, 0);
1220 st
= XNEWVEC (basic_block
, rslt_max
);
1221 rslt
[tv
++] = st
[sp
++] = bb
;
1230 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1231 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1233 gcc_assert (tv
!= rslt_max
);
1234 rslt
[tv
++] = st
[sp
++] = e
->src
;
1235 MARK_VISITED (e
->src
);
1240 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1241 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1243 gcc_assert (tv
!= rslt_max
);
1244 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1245 MARK_VISITED (e
->dest
);
1250 for (sp
= 0; sp
< tv
; sp
++)
1251 UNMARK_VISITED (rslt
[sp
]);
1254 #undef UNMARK_VISITED
1259 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1261 This algorithm can be found in Timothy Harvey's PhD thesis, at
1262 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1263 dominance algorithms.
1265 First, we identify each join point, j (any node with more than one
1266 incoming edge is a join point).
1268 We then examine each predecessor, p, of j and walk up the dominator tree
1271 We stop the walk when we reach j's immediate dominator - j is in the
1272 dominance frontier of each of the nodes in the walk, except for j's
1273 immediate dominator. Intuitively, all of the rest of j's dominators are
1274 shared by j's predecessors as well.
1275 Since they dominate j, they will not have j in their dominance frontiers.
1277 The number of nodes touched by this algorithm is equal to the size
1278 of the dominance frontiers, no more, no less.
1283 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1288 FOR_EACH_BB_FN (b
, cfun
)
1290 if (EDGE_COUNT (b
->preds
) >= 2)
1292 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1294 basic_block runner
= p
->src
;
1296 if (runner
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1299 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1300 while (runner
!= domsb
)
1302 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1305 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1315 compute_dominance_frontiers (bitmap_head
*frontiers
)
1317 timevar_push (TV_DOM_FRONTIERS
);
1319 compute_dominance_frontiers_1 (frontiers
);
1321 timevar_pop (TV_DOM_FRONTIERS
);
1324 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1325 return a bitmap with all the blocks in the iterated dominance
1326 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1327 frontier information as returned by compute_dominance_frontiers.
1329 The resulting set of blocks are the potential sites where PHI nodes
1330 are needed. The caller is responsible for freeing the memory
1331 allocated for the return value. */
1334 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1337 unsigned bb_index
, i
;
1338 bitmap phi_insertion_points
;
1340 /* Each block can appear at most twice on the work-stack. */
1341 auto_vec
<int> work_stack (2 * n_basic_blocks_for_fn (cfun
));
1342 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1344 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1345 vec::quick_push here for speed. This is safe because we know that
1346 the number of definition blocks is no greater than the number of
1347 basic blocks, which is the initial capacity of WORK_STACK. */
1348 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1349 work_stack
.quick_push (bb_index
);
1351 /* Pop a block off the worklist, add every block that appears in
1352 the original block's DF that we have not already processed to
1353 the worklist. Iterate until the worklist is empty. Blocks
1354 which are added to the worklist are potential sites for
1356 while (work_stack
.length () > 0)
1358 bb_index
= work_stack
.pop ();
1360 /* Since the registration of NEW -> OLD name mappings is done
1361 separately from the call to update_ssa, when updating the SSA
1362 form, the basic blocks where new and/or old names are defined
1363 may have disappeared by CFG cleanup calls. In this case,
1364 we may pull a non-existing block from the work stack. */
1365 gcc_checking_assert (bb_index
1366 < (unsigned) last_basic_block_for_fn (cfun
));
1368 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1371 work_stack
.quick_push (i
);
1372 bitmap_set_bit (phi_insertion_points
, i
);
1376 return phi_insertion_points
;
1379 /* Intersection and union of preds/succs for sbitmap based data flow
1380 solvers. All four functions defined below take the same arguments:
1381 B is the basic block to perform the operation for. DST is the
1382 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1383 last_basic_block so that it can be indexed with basic block indices.
1384 DST may be (but does not have to be) SRC[B->index]. */
1386 /* Set the bitmap DST to the intersection of SRC of successors of
1390 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1392 unsigned int set_size
= dst
->size
;
1396 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1398 e
= EDGE_SUCC (b
, ix
);
1399 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1402 bitmap_copy (dst
, src
[e
->dest
->index
]);
1409 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1412 SBITMAP_ELT_TYPE
*p
, *r
;
1414 e
= EDGE_SUCC (b
, ix
);
1415 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1418 p
= src
[e
->dest
->index
]->elms
;
1420 for (i
= 0; i
< set_size
; i
++)
1425 /* Set the bitmap DST to the intersection of SRC of predecessors of
1429 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1431 unsigned int set_size
= dst
->size
;
1435 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1437 e
= EDGE_PRED (b
, ix
);
1438 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1441 bitmap_copy (dst
, src
[e
->src
->index
]);
1448 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1451 SBITMAP_ELT_TYPE
*p
, *r
;
1453 e
= EDGE_PRED (b
, ix
);
1454 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1457 p
= src
[e
->src
->index
]->elms
;
1459 for (i
= 0; i
< set_size
; i
++)
1464 /* Set the bitmap DST to the union of SRC of successors of
1468 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1470 unsigned int set_size
= dst
->size
;
1474 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1476 e
= EDGE_SUCC (b
, ix
);
1477 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1480 bitmap_copy (dst
, src
[e
->dest
->index
]);
1484 if (ix
== EDGE_COUNT (b
->succs
))
1487 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1490 SBITMAP_ELT_TYPE
*p
, *r
;
1492 e
= EDGE_SUCC (b
, ix
);
1493 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1496 p
= src
[e
->dest
->index
]->elms
;
1498 for (i
= 0; i
< set_size
; i
++)
1503 /* Set the bitmap DST to the union of SRC of predecessors of
1507 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1509 unsigned int set_size
= dst
->size
;
1513 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1515 e
= EDGE_PRED (b
, ix
);
1516 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1519 bitmap_copy (dst
, src
[e
->src
->index
]);
1523 if (ix
== EDGE_COUNT (b
->preds
))
1526 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1529 SBITMAP_ELT_TYPE
*p
, *r
;
1531 e
= EDGE_PRED (b
, ix
);
1532 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1535 p
= src
[e
->src
->index
]->elms
;
1537 for (i
= 0; i
< set_size
; i
++)
1542 /* Returns the list of basic blocks in the function in an order that guarantees
1543 that if a block X has just a single predecessor Y, then Y is after X in the
1547 single_pred_before_succ_order (void)
1550 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1551 unsigned n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1553 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1555 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1556 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1558 bitmap_clear (visited
);
1560 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1561 FOR_EACH_BB_FN (x
, cfun
)
1566 /* Walk the predecessors of x as long as they have precisely one
1567 predecessor and add them to the list, so that they get stored
1570 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1571 y
= single_pred (y
))
1573 for (y
= x
, i
= n
- np
;
1574 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1575 y
= single_pred (y
), i
++)
1583 gcc_assert (i
== n
- 1);
1587 sbitmap_free (visited
);
1588 gcc_assert (n
== 0);