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"
27 #include "hard-reg-set.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 bb
= EDGE_SUCC (bb
, 0)->dest
;
758 /* Compute the reverse top sort order of the inverted CFG
759 i.e. starting from the exit block and following the edges backward
760 (from successors to predecessors).
761 This ordering can be used for forward dataflow problems among others.
763 This function assumes that all blocks in the CFG are reachable
764 from the ENTRY (but not necessarily from EXIT).
766 If there's an infinite loop,
767 a simple inverted traversal starting from the blocks
768 with no successors can't visit all blocks.
769 To solve this problem, we first do inverted traversal
770 starting from the blocks with no successor.
771 And if there's any block left that's not visited by the regular
772 inverted traversal from EXIT,
773 those blocks are in such problematic region.
774 Among those, we find one block that has
775 any visited predecessor (which is an entry into such a region),
776 and start looking for a "dead end" from that block
777 and do another inverted traversal from that block. */
780 inverted_post_order_compute (int *post_order
)
783 edge_iterator
*stack
;
785 int post_order_num
= 0;
789 verify_no_unreachable_blocks ();
792 /* Allocate stack for back-tracking up CFG. */
793 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
796 /* Allocate bitmap to track nodes that have been visited. */
797 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
799 /* None of the nodes in the CFG have been visited yet. */
800 bitmap_clear (visited
);
802 /* Put all blocks that have no successor into the initial work list. */
803 FOR_ALL_BB_FN (bb
, cfun
)
804 if (EDGE_COUNT (bb
->succs
) == 0)
806 /* Push the initial edge on to the stack. */
807 if (EDGE_COUNT (bb
->preds
) > 0)
809 stack
[sp
++] = ei_start (bb
->preds
);
810 bitmap_set_bit (visited
, bb
->index
);
816 bool has_unvisited_bb
= false;
818 /* The inverted traversal loop. */
824 /* Look at the edge on the top of the stack. */
826 bb
= ei_edge (ei
)->dest
;
827 pred
= ei_edge (ei
)->src
;
829 /* Check if the predecessor has been visited yet. */
830 if (! bitmap_bit_p (visited
, pred
->index
))
832 /* Mark that we have visited the destination. */
833 bitmap_set_bit (visited
, pred
->index
);
835 if (EDGE_COUNT (pred
->preds
) > 0)
836 /* Since the predecessor node has been visited for the first
837 time, check its predecessors. */
838 stack
[sp
++] = ei_start (pred
->preds
);
840 post_order
[post_order_num
++] = pred
->index
;
844 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
845 && ei_one_before_end_p (ei
))
846 post_order
[post_order_num
++] = bb
->index
;
848 if (!ei_one_before_end_p (ei
))
849 ei_next (&stack
[sp
- 1]);
855 /* Detect any infinite loop and activate the kludge.
856 Note that this doesn't check EXIT_BLOCK itself
857 since EXIT_BLOCK is always added after the outer do-while loop. */
858 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
859 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
860 if (!bitmap_bit_p (visited
, bb
->index
))
862 has_unvisited_bb
= true;
864 if (EDGE_COUNT (bb
->preds
) > 0)
868 basic_block visited_pred
= NULL
;
870 /* Find an already visited predecessor. */
871 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
873 if (bitmap_bit_p (visited
, e
->src
->index
))
874 visited_pred
= e
->src
;
879 basic_block be
= dfs_find_deadend (bb
);
880 gcc_assert (be
!= NULL
);
881 bitmap_set_bit (visited
, be
->index
);
882 stack
[sp
++] = ei_start (be
->preds
);
888 if (has_unvisited_bb
&& sp
== 0)
890 /* No blocks are reachable from EXIT at all.
891 Find a dead-end from the ENTRY, and restart the iteration. */
892 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
893 gcc_assert (be
!= NULL
);
894 bitmap_set_bit (visited
, be
->index
);
895 stack
[sp
++] = ei_start (be
->preds
);
898 /* The only case the below while fires is
899 when there's an infinite loop. */
903 /* EXIT_BLOCK is always included. */
904 post_order
[post_order_num
++] = EXIT_BLOCK
;
907 sbitmap_free (visited
);
908 return post_order_num
;
911 /* Compute the depth first search order of FN and store in the array
912 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
913 reverse completion number for each node. Returns the number of nodes
914 visited. A depth first search tries to get as far away from the starting
915 point as quickly as possible.
917 In case the function has unreachable blocks the number of nodes
918 visited does not include them.
920 pre_order is a really a preorder numbering of the graph.
921 rev_post_order is really a reverse postorder numbering of the graph. */
924 pre_and_rev_post_order_compute_fn (struct function
*fn
,
925 int *pre_order
, int *rev_post_order
,
926 bool include_entry_exit
)
928 edge_iterator
*stack
;
930 int pre_order_num
= 0;
931 int rev_post_order_num
= n_basic_blocks_for_fn (cfun
) - 1;
934 /* Allocate stack for back-tracking up CFG. */
935 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
938 if (include_entry_exit
)
941 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
944 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
947 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
949 /* Allocate bitmap to track nodes that have been visited. */
950 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
952 /* None of the nodes in the CFG have been visited yet. */
953 bitmap_clear (visited
);
955 /* Push the first edge on to the stack. */
956 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
);
964 /* Look at the edge on the top of the stack. */
966 src
= ei_edge (ei
)->src
;
967 dest
= ei_edge (ei
)->dest
;
969 /* Check if the edge destination has been visited yet. */
970 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (fn
)
971 && ! bitmap_bit_p (visited
, dest
->index
))
973 /* Mark that we have visited the destination. */
974 bitmap_set_bit (visited
, dest
->index
);
977 pre_order
[pre_order_num
] = dest
->index
;
981 if (EDGE_COUNT (dest
->succs
) > 0)
982 /* Since the DEST node has been visited for the first
983 time, check its successors. */
984 stack
[sp
++] = ei_start (dest
->succs
);
985 else if (rev_post_order
)
986 /* There are no successors for the DEST node so assign
987 its reverse completion number. */
988 rev_post_order
[rev_post_order_num
--] = dest
->index
;
992 if (ei_one_before_end_p (ei
)
993 && src
!= ENTRY_BLOCK_PTR_FOR_FN (fn
)
995 /* There are no more successors for the SRC node
996 so assign its reverse completion number. */
997 rev_post_order
[rev_post_order_num
--] = src
->index
;
999 if (!ei_one_before_end_p (ei
))
1000 ei_next (&stack
[sp
- 1]);
1007 sbitmap_free (visited
);
1009 if (include_entry_exit
)
1012 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1015 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
1018 return pre_order_num
;
1021 /* Like pre_and_rev_post_order_compute_fn but operating on the
1022 current function and asserting that all nodes were visited. */
1025 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
1026 bool include_entry_exit
)
1029 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1030 include_entry_exit
);
1031 if (include_entry_exit
)
1032 /* The number of nodes visited should be the number of blocks. */
1033 gcc_assert (pre_order_num
== n_basic_blocks_for_fn (cfun
));
1035 /* The number of nodes visited should be the number of blocks minus
1036 the entry and exit blocks which are not visited here. */
1037 gcc_assert (pre_order_num
1038 == (n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
));
1040 return pre_order_num
;
1043 /* Compute the depth first search order on the _reverse_ graph and
1044 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1045 Returns the number of nodes visited.
1047 The computation is split into three pieces:
1049 flow_dfs_compute_reverse_init () creates the necessary data
1052 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1053 structures. The block will start the search.
1055 flow_dfs_compute_reverse_execute () continues (or starts) the
1056 search using the block on the top of the stack, stopping when the
1059 flow_dfs_compute_reverse_finish () destroys the necessary data
1062 Thus, the user will probably call ..._init(), call ..._add_bb() to
1063 add a beginning basic block to the stack, call ..._execute(),
1064 possibly add another bb to the stack and again call ..._execute(),
1065 ..., and finally call _finish(). */
1067 /* Initialize the data structures used for depth-first search on the
1068 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1069 added to the basic block stack. DATA is the current depth-first
1070 search context. If INITIALIZE_STACK is nonzero, there is an
1071 element on the stack. */
1074 flow_dfs_compute_reverse_init (depth_first_search_ds
*data
)
1076 /* Allocate stack for back-tracking up CFG. */
1077 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1080 /* Allocate bitmap to track nodes that have been visited. */
1081 data
->visited_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1083 /* None of the nodes in the CFG have been visited yet. */
1084 bitmap_clear (data
->visited_blocks
);
1089 /* Add the specified basic block to the top of the dfs data
1090 structures. When the search continues, it will start at the
1094 flow_dfs_compute_reverse_add_bb (depth_first_search_ds
*data
, basic_block bb
)
1096 data
->stack
[data
->sp
++] = bb
;
1097 bitmap_set_bit (data
->visited_blocks
, bb
->index
);
1100 /* Continue the depth-first search through the reverse graph starting with the
1101 block at the stack's top and ending when the stack is empty. Visited nodes
1102 are marked. Returns an unvisited basic block, or NULL if there is none
1106 flow_dfs_compute_reverse_execute (depth_first_search_ds
*data
,
1107 basic_block last_unvisited
)
1113 while (data
->sp
> 0)
1115 bb
= data
->stack
[--data
->sp
];
1117 /* Perform depth-first search on adjacent vertices. */
1118 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1119 if (!bitmap_bit_p (data
->visited_blocks
, e
->src
->index
))
1120 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1123 /* Determine if there are unvisited basic blocks. */
1124 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1125 if (!bitmap_bit_p (data
->visited_blocks
, bb
->index
))
1131 /* Destroy the data structures needed for depth-first search on the
1135 flow_dfs_compute_reverse_finish (depth_first_search_ds
*data
)
1138 sbitmap_free (data
->visited_blocks
);
1141 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1142 if REVERSE, go against direction of edges. Returns number of blocks
1143 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1145 dfs_enumerate_from (basic_block bb
, int reverse
,
1146 bool (*predicate
) (const_basic_block
, const void *),
1147 basic_block
*rslt
, int rslt_max
, const void *data
)
1149 basic_block
*st
, lbb
;
1153 /* A bitmap to keep track of visited blocks. Allocating it each time
1154 this function is called is not possible, since dfs_enumerate_from
1155 is often used on small (almost) disjoint parts of cfg (bodies of
1156 loops), and allocating a large sbitmap would lead to quadratic
1158 static sbitmap visited
;
1159 static unsigned v_size
;
1161 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1162 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1163 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1165 /* Resize the VISITED sbitmap if necessary. */
1166 size
= last_basic_block_for_fn (cfun
);
1173 visited
= sbitmap_alloc (size
);
1174 bitmap_clear (visited
);
1177 else if (v_size
< size
)
1179 /* Ensure that we increase the size of the sbitmap exponentially. */
1180 if (2 * v_size
> size
)
1183 visited
= sbitmap_resize (visited
, size
, 0);
1187 st
= XNEWVEC (basic_block
, rslt_max
);
1188 rslt
[tv
++] = st
[sp
++] = bb
;
1197 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1198 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1200 gcc_assert (tv
!= rslt_max
);
1201 rslt
[tv
++] = st
[sp
++] = e
->src
;
1202 MARK_VISITED (e
->src
);
1207 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1208 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1210 gcc_assert (tv
!= rslt_max
);
1211 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1212 MARK_VISITED (e
->dest
);
1217 for (sp
= 0; sp
< tv
; sp
++)
1218 UNMARK_VISITED (rslt
[sp
]);
1221 #undef UNMARK_VISITED
1226 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1228 This algorithm can be found in Timothy Harvey's PhD thesis, at
1229 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1230 dominance algorithms.
1232 First, we identify each join point, j (any node with more than one
1233 incoming edge is a join point).
1235 We then examine each predecessor, p, of j and walk up the dominator tree
1238 We stop the walk when we reach j's immediate dominator - j is in the
1239 dominance frontier of each of the nodes in the walk, except for j's
1240 immediate dominator. Intuitively, all of the rest of j's dominators are
1241 shared by j's predecessors as well.
1242 Since they dominate j, they will not have j in their dominance frontiers.
1244 The number of nodes touched by this algorithm is equal to the size
1245 of the dominance frontiers, no more, no less.
1250 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1255 FOR_EACH_BB_FN (b
, cfun
)
1257 if (EDGE_COUNT (b
->preds
) >= 2)
1259 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1261 basic_block runner
= p
->src
;
1263 if (runner
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1266 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1267 while (runner
!= domsb
)
1269 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1272 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1282 compute_dominance_frontiers (bitmap_head
*frontiers
)
1284 timevar_push (TV_DOM_FRONTIERS
);
1286 compute_dominance_frontiers_1 (frontiers
);
1288 timevar_pop (TV_DOM_FRONTIERS
);
1291 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1292 return a bitmap with all the blocks in the iterated dominance
1293 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1294 frontier information as returned by compute_dominance_frontiers.
1296 The resulting set of blocks are the potential sites where PHI nodes
1297 are needed. The caller is responsible for freeing the memory
1298 allocated for the return value. */
1301 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1304 unsigned bb_index
, i
;
1305 bitmap phi_insertion_points
;
1307 /* Each block can appear at most twice on the work-stack. */
1308 auto_vec
<int> work_stack (2 * n_basic_blocks_for_fn (cfun
));
1309 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1311 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1312 vec::quick_push here for speed. This is safe because we know that
1313 the number of definition blocks is no greater than the number of
1314 basic blocks, which is the initial capacity of WORK_STACK. */
1315 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1316 work_stack
.quick_push (bb_index
);
1318 /* Pop a block off the worklist, add every block that appears in
1319 the original block's DF that we have not already processed to
1320 the worklist. Iterate until the worklist is empty. Blocks
1321 which are added to the worklist are potential sites for
1323 while (work_stack
.length () > 0)
1325 bb_index
= work_stack
.pop ();
1327 /* Since the registration of NEW -> OLD name mappings is done
1328 separately from the call to update_ssa, when updating the SSA
1329 form, the basic blocks where new and/or old names are defined
1330 may have disappeared by CFG cleanup calls. In this case,
1331 we may pull a non-existing block from the work stack. */
1332 gcc_checking_assert (bb_index
1333 < (unsigned) last_basic_block_for_fn (cfun
));
1335 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1338 work_stack
.quick_push (i
);
1339 bitmap_set_bit (phi_insertion_points
, i
);
1343 return phi_insertion_points
;
1346 /* Intersection and union of preds/succs for sbitmap based data flow
1347 solvers. All four functions defined below take the same arguments:
1348 B is the basic block to perform the operation for. DST is the
1349 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1350 last_basic_block so that it can be indexed with basic block indices.
1351 DST may be (but does not have to be) SRC[B->index]. */
1353 /* Set the bitmap DST to the intersection of SRC of successors of
1357 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1359 unsigned int set_size
= dst
->size
;
1363 gcc_assert (!dst
->popcount
);
1365 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1367 e
= EDGE_SUCC (b
, ix
);
1368 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1371 bitmap_copy (dst
, src
[e
->dest
->index
]);
1378 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1381 SBITMAP_ELT_TYPE
*p
, *r
;
1383 e
= EDGE_SUCC (b
, ix
);
1384 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1387 p
= src
[e
->dest
->index
]->elms
;
1389 for (i
= 0; i
< set_size
; i
++)
1394 /* Set the bitmap DST to the intersection of SRC of predecessors of
1398 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1400 unsigned int set_size
= dst
->size
;
1404 gcc_assert (!dst
->popcount
);
1406 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1408 e
= EDGE_PRED (b
, ix
);
1409 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1412 bitmap_copy (dst
, src
[e
->src
->index
]);
1419 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1422 SBITMAP_ELT_TYPE
*p
, *r
;
1424 e
= EDGE_PRED (b
, ix
);
1425 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1428 p
= src
[e
->src
->index
]->elms
;
1430 for (i
= 0; i
< set_size
; i
++)
1435 /* Set the bitmap DST to the union of SRC of successors of
1439 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1441 unsigned int set_size
= dst
->size
;
1445 gcc_assert (!dst
->popcount
);
1447 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1449 e
= EDGE_SUCC (b
, ix
);
1450 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1453 bitmap_copy (dst
, src
[e
->dest
->index
]);
1457 if (ix
== EDGE_COUNT (b
->succs
))
1460 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1463 SBITMAP_ELT_TYPE
*p
, *r
;
1465 e
= EDGE_SUCC (b
, ix
);
1466 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1469 p
= src
[e
->dest
->index
]->elms
;
1471 for (i
= 0; i
< set_size
; i
++)
1476 /* Set the bitmap DST to the union of SRC of predecessors of
1480 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1482 unsigned int set_size
= dst
->size
;
1486 gcc_assert (!dst
->popcount
);
1488 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1490 e
= EDGE_PRED (b
, ix
);
1491 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1494 bitmap_copy (dst
, src
[e
->src
->index
]);
1498 if (ix
== EDGE_COUNT (b
->preds
))
1501 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1504 SBITMAP_ELT_TYPE
*p
, *r
;
1506 e
= EDGE_PRED (b
, ix
);
1507 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1510 p
= src
[e
->src
->index
]->elms
;
1512 for (i
= 0; i
< set_size
; i
++)
1517 /* Returns the list of basic blocks in the function in an order that guarantees
1518 that if a block X has just a single predecessor Y, then Y is after X in the
1522 single_pred_before_succ_order (void)
1525 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1526 unsigned n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1528 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1530 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1531 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1533 bitmap_clear (visited
);
1535 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1536 FOR_EACH_BB_FN (x
, cfun
)
1541 /* Walk the predecessors of x as long as they have precisely one
1542 predecessor and add them to the list, so that they get stored
1545 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1546 y
= single_pred (y
))
1548 for (y
= x
, i
= n
- np
;
1549 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1550 y
= single_pred (y
), i
++)
1558 gcc_assert (i
== n
- 1);
1562 sbitmap_free (visited
);
1563 gcc_assert (n
== 0);