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 /* Functions to access an edge list with a vector representation.
198 Enough data is kept such that given an index number, the
199 pred and succ that edge represents can be determined, or
200 given a pred and a succ, its index number can be returned.
201 This allows algorithms which consume a lot of memory to
202 represent the normally full matrix of edge (pred,succ) with a
203 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
204 wasted space in the client code due to sparse flow graphs. */
206 /* This functions initializes the edge list. Basically the entire
207 flowgraph is processed, and all edges are assigned a number,
208 and the data structure is filled in. */
211 create_edge_list (void)
213 struct edge_list
*elist
;
219 /* Determine the number of edges in the flow graph by counting successor
220 edges on each basic block. */
222 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
223 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
225 num_edges
+= EDGE_COUNT (bb
->succs
);
228 elist
= XNEW (struct edge_list
);
229 elist
->num_edges
= num_edges
;
230 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
234 /* Follow successors of blocks, and register these edges. */
235 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
236 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
237 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
238 elist
->index_to_edge
[num_edges
++] = e
;
243 /* This function free's memory associated with an edge list. */
246 free_edge_list (struct edge_list
*elist
)
250 free (elist
->index_to_edge
);
255 /* This function provides debug output showing an edge list. */
258 print_edge_list (FILE *f
, struct edge_list
*elist
)
262 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
263 n_basic_blocks_for_fn (cfun
), elist
->num_edges
);
265 for (x
= 0; x
< elist
->num_edges
; x
++)
267 fprintf (f
, " %-4d - edge(", x
);
268 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
269 fprintf (f
, "entry,");
271 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
273 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
274 fprintf (f
, "exit)\n");
276 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
280 /* This function provides an internal consistency check of an edge list,
281 verifying that all edges are present, and that there are no
285 verify_edge_list (FILE *f
, struct edge_list
*elist
)
287 int pred
, succ
, index
;
289 basic_block bb
, p
, s
;
292 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
293 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
295 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
297 pred
= e
->src
->index
;
298 succ
= e
->dest
->index
;
299 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
300 if (index
== EDGE_INDEX_NO_EDGE
)
302 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
306 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
307 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
308 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
309 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
310 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
311 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
315 /* We've verified that all the edges are in the list, now lets make sure
316 there are no spurious edges in the list. This is an expensive check! */
318 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
319 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
320 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
324 FOR_EACH_EDGE (e
, ei
, p
->succs
)
331 FOR_EACH_EDGE (e
, ei
, s
->preds
)
338 if (EDGE_INDEX (elist
, p
, s
)
339 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
340 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
342 if (EDGE_INDEX (elist
, p
, s
)
343 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
344 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
345 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
350 /* Functions to compute control dependences. */
352 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
354 control_dependences::set_control_dependence_map_bit (basic_block bb
,
357 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
359 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
360 bitmap_set_bit (control_dependence_map
[bb
->index
], edge_index
);
363 /* Clear all control dependences for block BB. */
365 control_dependences::clear_control_dependence_bitmap (basic_block bb
)
367 bitmap_clear (control_dependence_map
[bb
->index
]);
370 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
371 This function is necessary because some blocks have negative numbers. */
373 static inline basic_block
374 find_pdom (basic_block block
)
376 gcc_assert (block
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
378 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
379 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
382 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
384 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
389 /* Determine all blocks' control dependences on the given edge with edge_list
390 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
393 control_dependences::find_control_dependence (int edge_index
)
395 basic_block current_block
;
396 basic_block ending_block
;
398 gcc_assert (INDEX_EDGE_PRED_BB (m_el
, edge_index
)
399 != EXIT_BLOCK_PTR_FOR_FN (cfun
));
401 if (INDEX_EDGE_PRED_BB (m_el
, edge_index
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
402 ending_block
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
404 ending_block
= find_pdom (INDEX_EDGE_PRED_BB (m_el
, edge_index
));
406 for (current_block
= INDEX_EDGE_SUCC_BB (m_el
, edge_index
);
407 current_block
!= ending_block
408 && current_block
!= EXIT_BLOCK_PTR_FOR_FN (cfun
);
409 current_block
= find_pdom (current_block
))
411 edge e
= INDEX_EDGE (m_el
, edge_index
);
413 /* For abnormal edges, we don't make current_block control
414 dependent because instructions that throw are always necessary
416 if (e
->flags
& EDGE_ABNORMAL
)
419 set_control_dependence_map_bit (current_block
, edge_index
);
423 /* Record all blocks' control dependences on all edges in the edge
424 list EL, ala Morgan, Section 3.6. */
426 control_dependences::control_dependences (struct edge_list
*edges
)
429 timevar_push (TV_CONTROL_DEPENDENCES
);
430 control_dependence_map
.create (last_basic_block_for_fn (cfun
));
431 for (int i
= 0; i
< last_basic_block_for_fn (cfun
); ++i
)
432 control_dependence_map
.quick_push (BITMAP_ALLOC (NULL
));
433 for (int i
= 0; i
< NUM_EDGES (m_el
); ++i
)
434 find_control_dependence (i
);
435 timevar_pop (TV_CONTROL_DEPENDENCES
);
438 /* Free control dependences and the associated edge list. */
440 control_dependences::~control_dependences ()
442 for (unsigned i
= 0; i
< control_dependence_map
.length (); ++i
)
443 BITMAP_FREE (control_dependence_map
[i
]);
444 control_dependence_map
.release ();
445 free_edge_list (m_el
);
448 /* Returns the bitmap of edges the basic-block I is dependent on. */
451 control_dependences::get_edges_dependent_on (int i
)
453 return control_dependence_map
[i
];
456 /* Returns the edge with index I from the edge list. */
459 control_dependences::get_edge (int i
)
461 return INDEX_EDGE (m_el
, i
);
465 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
466 If no such edge exists, return NULL. */
469 find_edge (basic_block pred
, basic_block succ
)
474 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
476 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
482 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
490 /* This routine will determine what, if any, edge there is between
491 a specified predecessor and successor. */
494 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
498 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
499 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
500 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
503 return (EDGE_INDEX_NO_EDGE
);
506 /* This routine will remove any fake predecessor edges for a basic block.
507 When the edge is removed, it is also removed from whatever successor
511 remove_fake_predecessors (basic_block bb
)
516 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
518 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
525 /* This routine will remove all fake edges from the flow graph. If
526 we remove all fake successors, it will automatically remove all
527 fake predecessors. */
530 remove_fake_edges (void)
534 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
535 remove_fake_predecessors (bb
);
538 /* This routine will remove all fake edges to the EXIT_BLOCK. */
541 remove_fake_exit_edges (void)
543 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun
));
547 /* This function will add a fake edge between any block which has no
548 successors, and the exit block. Some data flow equations require these
552 add_noreturn_fake_exit_edges (void)
556 FOR_EACH_BB_FN (bb
, cfun
)
557 if (EDGE_COUNT (bb
->succs
) == 0)
558 make_single_succ_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
561 /* This function adds a fake edge between any infinite loops to the
562 exit block. Some optimizations require a path from each node to
565 See also Morgan, Figure 3.10, pp. 82-83.
567 The current implementation is ugly, not attempting to minimize the
568 number of inserted fake edges. To reduce the number of fake edges
569 to insert, add fake edges from _innermost_ loops containing only
570 nodes not reachable from the exit block. */
573 connect_infinite_loops_to_exit (void)
575 basic_block unvisited_block
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
576 basic_block deadend_block
;
577 depth_first_search_ds dfs_ds
;
579 /* Perform depth-first search in the reverse graph to find nodes
580 reachable from the exit block. */
581 flow_dfs_compute_reverse_init (&dfs_ds
);
582 flow_dfs_compute_reverse_add_bb (&dfs_ds
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
584 /* Repeatedly add fake edges, updating the unreachable nodes. */
587 unvisited_block
= flow_dfs_compute_reverse_execute (&dfs_ds
,
589 if (!unvisited_block
)
592 deadend_block
= dfs_find_deadend (unvisited_block
);
593 make_edge (deadend_block
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
594 flow_dfs_compute_reverse_add_bb (&dfs_ds
, deadend_block
);
597 flow_dfs_compute_reverse_finish (&dfs_ds
);
601 /* Compute reverse top sort order. This is computing a post order
602 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
603 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
604 true, unreachable blocks are deleted. */
607 post_order_compute (int *post_order
, bool include_entry_exit
,
608 bool delete_unreachable
)
610 edge_iterator
*stack
;
612 int post_order_num
= 0;
616 if (include_entry_exit
)
617 post_order
[post_order_num
++] = EXIT_BLOCK
;
619 /* Allocate stack for back-tracking up CFG. */
620 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
623 /* Allocate bitmap to track nodes that have been visited. */
624 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
626 /* None of the nodes in the CFG have been visited yet. */
627 bitmap_clear (visited
);
629 /* Push the first edge on to the stack. */
630 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
638 /* Look at the edge on the top of the stack. */
640 src
= ei_edge (ei
)->src
;
641 dest
= ei_edge (ei
)->dest
;
643 /* Check if the edge destination has been visited yet. */
644 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
645 && ! bitmap_bit_p (visited
, dest
->index
))
647 /* Mark that we have visited the destination. */
648 bitmap_set_bit (visited
, dest
->index
);
650 if (EDGE_COUNT (dest
->succs
) > 0)
651 /* Since the DEST node has been visited for the first
652 time, check its successors. */
653 stack
[sp
++] = ei_start (dest
->succs
);
655 post_order
[post_order_num
++] = dest
->index
;
659 if (ei_one_before_end_p (ei
)
660 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
661 post_order
[post_order_num
++] = src
->index
;
663 if (!ei_one_before_end_p (ei
))
664 ei_next (&stack
[sp
- 1]);
670 if (include_entry_exit
)
672 post_order
[post_order_num
++] = ENTRY_BLOCK
;
673 count
= post_order_num
;
676 count
= post_order_num
+ 2;
678 /* Delete the unreachable blocks if some were found and we are
679 supposed to do it. */
680 if (delete_unreachable
&& (count
!= n_basic_blocks_for_fn (cfun
)))
684 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
685 != EXIT_BLOCK_PTR_FOR_FN (cfun
); b
= next_bb
)
687 next_bb
= b
->next_bb
;
689 if (!(bitmap_bit_p (visited
, b
->index
)))
690 delete_basic_block (b
);
693 tidy_fallthru_edges ();
697 sbitmap_free (visited
);
698 return post_order_num
;
702 /* Helper routine for inverted_post_order_compute
703 flow_dfs_compute_reverse_execute, and the reverse-CFG
704 deapth first search in dominance.c.
705 BB has to belong to a region of CFG
706 unreachable by inverted traversal from the exit.
707 i.e. there's no control flow path from ENTRY to EXIT
708 that contains this BB.
709 This can happen in two cases - if there's an infinite loop
710 or if there's a block that has no successor
711 (call to a function with no return).
712 Some RTL passes deal with this condition by
713 calling connect_infinite_loops_to_exit () and/or
714 add_noreturn_fake_exit_edges ().
715 However, those methods involve modifying the CFG itself
716 which may not be desirable.
717 Hence, we deal with the infinite loop/no return cases
718 by identifying a unique basic block that can reach all blocks
719 in such a region by inverted traversal.
720 This function returns a basic block that guarantees
721 that all blocks in the region are reachable
722 by starting an inverted traversal from the returned block. */
725 dfs_find_deadend (basic_block bb
)
727 bitmap visited
= BITMAP_ALLOC (NULL
);
731 if (EDGE_COUNT (bb
->succs
) == 0
732 || ! bitmap_set_bit (visited
, bb
->index
))
734 BITMAP_FREE (visited
);
738 bb
= EDGE_SUCC (bb
, 0)->dest
;
745 /* Compute the reverse top sort order of the inverted CFG
746 i.e. starting from the exit block and following the edges backward
747 (from successors to predecessors).
748 This ordering can be used for forward dataflow problems among others.
750 This function assumes that all blocks in the CFG are reachable
751 from the ENTRY (but not necessarily from EXIT).
753 If there's an infinite loop,
754 a simple inverted traversal starting from the blocks
755 with no successors can't visit all blocks.
756 To solve this problem, we first do inverted traversal
757 starting from the blocks with no successor.
758 And if there's any block left that's not visited by the regular
759 inverted traversal from EXIT,
760 those blocks are in such problematic region.
761 Among those, we find one block that has
762 any visited predecessor (which is an entry into such a region),
763 and start looking for a "dead end" from that block
764 and do another inverted traversal from that block. */
767 inverted_post_order_compute (int *post_order
)
770 edge_iterator
*stack
;
772 int post_order_num
= 0;
775 /* Allocate stack for back-tracking up CFG. */
776 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
779 /* Allocate bitmap to track nodes that have been visited. */
780 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
782 /* None of the nodes in the CFG have been visited yet. */
783 bitmap_clear (visited
);
785 /* Put all blocks that have no successor into the initial work list. */
786 FOR_ALL_BB_FN (bb
, cfun
)
787 if (EDGE_COUNT (bb
->succs
) == 0)
789 /* Push the initial edge on to the stack. */
790 if (EDGE_COUNT (bb
->preds
) > 0)
792 stack
[sp
++] = ei_start (bb
->preds
);
793 bitmap_set_bit (visited
, bb
->index
);
799 bool has_unvisited_bb
= false;
801 /* The inverted traversal loop. */
807 /* Look at the edge on the top of the stack. */
809 bb
= ei_edge (ei
)->dest
;
810 pred
= ei_edge (ei
)->src
;
812 /* Check if the predecessor has been visited yet. */
813 if (! bitmap_bit_p (visited
, pred
->index
))
815 /* Mark that we have visited the destination. */
816 bitmap_set_bit (visited
, pred
->index
);
818 if (EDGE_COUNT (pred
->preds
) > 0)
819 /* Since the predecessor node has been visited for the first
820 time, check its predecessors. */
821 stack
[sp
++] = ei_start (pred
->preds
);
823 post_order
[post_order_num
++] = pred
->index
;
827 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
828 && ei_one_before_end_p (ei
))
829 post_order
[post_order_num
++] = bb
->index
;
831 if (!ei_one_before_end_p (ei
))
832 ei_next (&stack
[sp
- 1]);
838 /* Detect any infinite loop and activate the kludge.
839 Note that this doesn't check EXIT_BLOCK itself
840 since EXIT_BLOCK is always added after the outer do-while loop. */
841 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
842 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
843 if (!bitmap_bit_p (visited
, bb
->index
))
845 has_unvisited_bb
= true;
847 if (EDGE_COUNT (bb
->preds
) > 0)
851 basic_block visited_pred
= NULL
;
853 /* Find an already visited predecessor. */
854 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
856 if (bitmap_bit_p (visited
, e
->src
->index
))
857 visited_pred
= e
->src
;
862 basic_block be
= dfs_find_deadend (bb
);
863 gcc_assert (be
!= NULL
);
864 bitmap_set_bit (visited
, be
->index
);
865 stack
[sp
++] = ei_start (be
->preds
);
871 if (has_unvisited_bb
&& sp
== 0)
873 /* No blocks are reachable from EXIT at all.
874 Find a dead-end from the ENTRY, and restart the iteration. */
875 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
876 gcc_assert (be
!= NULL
);
877 bitmap_set_bit (visited
, be
->index
);
878 stack
[sp
++] = ei_start (be
->preds
);
881 /* The only case the below while fires is
882 when there's an infinite loop. */
886 /* EXIT_BLOCK is always included. */
887 post_order
[post_order_num
++] = EXIT_BLOCK
;
890 sbitmap_free (visited
);
891 return post_order_num
;
894 /* Compute the depth first search order of FN and store in the array
895 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
896 reverse completion number for each node. Returns the number of nodes
897 visited. A depth first search tries to get as far away from the starting
898 point as quickly as possible.
900 In case the function has unreachable blocks the number of nodes
901 visited does not include them.
903 pre_order is a really a preorder numbering of the graph.
904 rev_post_order is really a reverse postorder numbering of the graph. */
907 pre_and_rev_post_order_compute_fn (struct function
*fn
,
908 int *pre_order
, int *rev_post_order
,
909 bool include_entry_exit
)
911 edge_iterator
*stack
;
913 int pre_order_num
= 0;
914 int rev_post_order_num
= n_basic_blocks_for_fn (cfun
) - 1;
917 /* Allocate stack for back-tracking up CFG. */
918 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
) + 1);
921 if (include_entry_exit
)
924 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
927 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
930 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
932 /* Allocate bitmap to track nodes that have been visited. */
933 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
935 /* None of the nodes in the CFG have been visited yet. */
936 bitmap_clear (visited
);
938 /* Push the first edge on to the stack. */
939 stack
[sp
++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
);
947 /* Look at the edge on the top of the stack. */
949 src
= ei_edge (ei
)->src
;
950 dest
= ei_edge (ei
)->dest
;
952 /* Check if the edge destination has been visited yet. */
953 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (fn
)
954 && ! bitmap_bit_p (visited
, dest
->index
))
956 /* Mark that we have visited the destination. */
957 bitmap_set_bit (visited
, dest
->index
);
960 pre_order
[pre_order_num
] = dest
->index
;
964 if (EDGE_COUNT (dest
->succs
) > 0)
965 /* Since the DEST node has been visited for the first
966 time, check its successors. */
967 stack
[sp
++] = ei_start (dest
->succs
);
968 else if (rev_post_order
)
969 /* There are no successors for the DEST node so assign
970 its reverse completion number. */
971 rev_post_order
[rev_post_order_num
--] = dest
->index
;
975 if (ei_one_before_end_p (ei
)
976 && src
!= ENTRY_BLOCK_PTR_FOR_FN (fn
)
978 /* There are no more successors for the SRC node
979 so assign its reverse completion number. */
980 rev_post_order
[rev_post_order_num
--] = src
->index
;
982 if (!ei_one_before_end_p (ei
))
983 ei_next (&stack
[sp
- 1]);
990 sbitmap_free (visited
);
992 if (include_entry_exit
)
995 pre_order
[pre_order_num
] = EXIT_BLOCK
;
998 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
1001 return pre_order_num
;
1004 /* Like pre_and_rev_post_order_compute_fn but operating on the
1005 current function and asserting that all nodes were visited. */
1008 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
1009 bool include_entry_exit
)
1012 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1013 include_entry_exit
);
1014 if (include_entry_exit
)
1015 /* The number of nodes visited should be the number of blocks. */
1016 gcc_assert (pre_order_num
== n_basic_blocks_for_fn (cfun
));
1018 /* The number of nodes visited should be the number of blocks minus
1019 the entry and exit blocks which are not visited here. */
1020 gcc_assert (pre_order_num
1021 == (n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
));
1023 return pre_order_num
;
1026 /* Compute the depth first search order on the _reverse_ graph and
1027 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1028 Returns the number of nodes visited.
1030 The computation is split into three pieces:
1032 flow_dfs_compute_reverse_init () creates the necessary data
1035 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1036 structures. The block will start the search.
1038 flow_dfs_compute_reverse_execute () continues (or starts) the
1039 search using the block on the top of the stack, stopping when the
1042 flow_dfs_compute_reverse_finish () destroys the necessary data
1045 Thus, the user will probably call ..._init(), call ..._add_bb() to
1046 add a beginning basic block to the stack, call ..._execute(),
1047 possibly add another bb to the stack and again call ..._execute(),
1048 ..., and finally call _finish(). */
1050 /* Initialize the data structures used for depth-first search on the
1051 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1052 added to the basic block stack. DATA is the current depth-first
1053 search context. If INITIALIZE_STACK is nonzero, there is an
1054 element on the stack. */
1057 flow_dfs_compute_reverse_init (depth_first_search_ds
*data
)
1059 /* Allocate stack for back-tracking up CFG. */
1060 data
->stack
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1063 /* Allocate bitmap to track nodes that have been visited. */
1064 data
->visited_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1066 /* None of the nodes in the CFG have been visited yet. */
1067 bitmap_clear (data
->visited_blocks
);
1072 /* Add the specified basic block to the top of the dfs data
1073 structures. When the search continues, it will start at the
1077 flow_dfs_compute_reverse_add_bb (depth_first_search_ds
*data
, basic_block bb
)
1079 data
->stack
[data
->sp
++] = bb
;
1080 bitmap_set_bit (data
->visited_blocks
, bb
->index
);
1083 /* Continue the depth-first search through the reverse graph starting with the
1084 block at the stack's top and ending when the stack is empty. Visited nodes
1085 are marked. Returns an unvisited basic block, or NULL if there is none
1089 flow_dfs_compute_reverse_execute (depth_first_search_ds
*data
,
1090 basic_block last_unvisited
)
1096 while (data
->sp
> 0)
1098 bb
= data
->stack
[--data
->sp
];
1100 /* Perform depth-first search on adjacent vertices. */
1101 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1102 if (!bitmap_bit_p (data
->visited_blocks
, e
->src
->index
))
1103 flow_dfs_compute_reverse_add_bb (data
, e
->src
);
1106 /* Determine if there are unvisited basic blocks. */
1107 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1108 if (!bitmap_bit_p (data
->visited_blocks
, bb
->index
))
1114 /* Destroy the data structures needed for depth-first search on the
1118 flow_dfs_compute_reverse_finish (depth_first_search_ds
*data
)
1121 sbitmap_free (data
->visited_blocks
);
1124 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1125 if REVERSE, go against direction of edges. Returns number of blocks
1126 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1128 dfs_enumerate_from (basic_block bb
, int reverse
,
1129 bool (*predicate
) (const_basic_block
, const void *),
1130 basic_block
*rslt
, int rslt_max
, const void *data
)
1132 basic_block
*st
, lbb
;
1136 /* A bitmap to keep track of visited blocks. Allocating it each time
1137 this function is called is not possible, since dfs_enumerate_from
1138 is often used on small (almost) disjoint parts of cfg (bodies of
1139 loops), and allocating a large sbitmap would lead to quadratic
1141 static sbitmap visited
;
1142 static unsigned v_size
;
1144 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1145 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1146 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1148 /* Resize the VISITED sbitmap if necessary. */
1149 size
= last_basic_block_for_fn (cfun
);
1156 visited
= sbitmap_alloc (size
);
1157 bitmap_clear (visited
);
1160 else if (v_size
< size
)
1162 /* Ensure that we increase the size of the sbitmap exponentially. */
1163 if (2 * v_size
> size
)
1166 visited
= sbitmap_resize (visited
, size
, 0);
1170 st
= XNEWVEC (basic_block
, rslt_max
);
1171 rslt
[tv
++] = st
[sp
++] = bb
;
1180 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1181 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1183 gcc_assert (tv
!= rslt_max
);
1184 rslt
[tv
++] = st
[sp
++] = e
->src
;
1185 MARK_VISITED (e
->src
);
1190 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1191 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1193 gcc_assert (tv
!= rslt_max
);
1194 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1195 MARK_VISITED (e
->dest
);
1200 for (sp
= 0; sp
< tv
; sp
++)
1201 UNMARK_VISITED (rslt
[sp
]);
1204 #undef UNMARK_VISITED
1209 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1211 This algorithm can be found in Timothy Harvey's PhD thesis, at
1212 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1213 dominance algorithms.
1215 First, we identify each join point, j (any node with more than one
1216 incoming edge is a join point).
1218 We then examine each predecessor, p, of j and walk up the dominator tree
1221 We stop the walk when we reach j's immediate dominator - j is in the
1222 dominance frontier of each of the nodes in the walk, except for j's
1223 immediate dominator. Intuitively, all of the rest of j's dominators are
1224 shared by j's predecessors as well.
1225 Since they dominate j, they will not have j in their dominance frontiers.
1227 The number of nodes touched by this algorithm is equal to the size
1228 of the dominance frontiers, no more, no less.
1233 compute_dominance_frontiers_1 (bitmap_head
*frontiers
)
1238 FOR_EACH_BB_FN (b
, cfun
)
1240 if (EDGE_COUNT (b
->preds
) >= 2)
1242 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1244 basic_block runner
= p
->src
;
1246 if (runner
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1249 domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1250 while (runner
!= domsb
)
1252 if (!bitmap_set_bit (&frontiers
[runner
->index
],
1255 runner
= get_immediate_dominator (CDI_DOMINATORS
,
1265 compute_dominance_frontiers (bitmap_head
*frontiers
)
1267 timevar_push (TV_DOM_FRONTIERS
);
1269 compute_dominance_frontiers_1 (frontiers
);
1271 timevar_pop (TV_DOM_FRONTIERS
);
1274 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1275 return a bitmap with all the blocks in the iterated dominance
1276 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1277 frontier information as returned by compute_dominance_frontiers.
1279 The resulting set of blocks are the potential sites where PHI nodes
1280 are needed. The caller is responsible for freeing the memory
1281 allocated for the return value. */
1284 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1287 unsigned bb_index
, i
;
1288 bitmap phi_insertion_points
;
1290 /* Each block can appear at most twice on the work-stack. */
1291 auto_vec
<int> work_stack (2 * n_basic_blocks_for_fn (cfun
));
1292 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1294 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1295 vec::quick_push here for speed. This is safe because we know that
1296 the number of definition blocks is no greater than the number of
1297 basic blocks, which is the initial capacity of WORK_STACK. */
1298 EXECUTE_IF_SET_IN_BITMAP (def_blocks
, 0, bb_index
, bi
)
1299 work_stack
.quick_push (bb_index
);
1301 /* Pop a block off the worklist, add every block that appears in
1302 the original block's DF that we have not already processed to
1303 the worklist. Iterate until the worklist is empty. Blocks
1304 which are added to the worklist are potential sites for
1306 while (work_stack
.length () > 0)
1308 bb_index
= work_stack
.pop ();
1310 /* Since the registration of NEW -> OLD name mappings is done
1311 separately from the call to update_ssa, when updating the SSA
1312 form, the basic blocks where new and/or old names are defined
1313 may have disappeared by CFG cleanup calls. In this case,
1314 we may pull a non-existing block from the work stack. */
1315 gcc_checking_assert (bb_index
1316 < (unsigned) last_basic_block_for_fn (cfun
));
1318 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1321 work_stack
.quick_push (i
);
1322 bitmap_set_bit (phi_insertion_points
, i
);
1326 return phi_insertion_points
;
1329 /* Intersection and union of preds/succs for sbitmap based data flow
1330 solvers. All four functions defined below take the same arguments:
1331 B is the basic block to perform the operation for. DST is the
1332 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1333 last_basic_block so that it can be indexed with basic block indices.
1334 DST may be (but does not have to be) SRC[B->index]. */
1336 /* Set the bitmap DST to the intersection of SRC of successors of
1340 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1342 unsigned int set_size
= dst
->size
;
1346 gcc_assert (!dst
->popcount
);
1348 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1350 e
= EDGE_SUCC (b
, ix
);
1351 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1354 bitmap_copy (dst
, src
[e
->dest
->index
]);
1361 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1364 SBITMAP_ELT_TYPE
*p
, *r
;
1366 e
= EDGE_SUCC (b
, ix
);
1367 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1370 p
= src
[e
->dest
->index
]->elms
;
1372 for (i
= 0; i
< set_size
; i
++)
1377 /* Set the bitmap DST to the intersection of SRC of predecessors of
1381 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1383 unsigned int set_size
= dst
->size
;
1387 gcc_assert (!dst
->popcount
);
1389 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1391 e
= EDGE_PRED (b
, ix
);
1392 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1395 bitmap_copy (dst
, src
[e
->src
->index
]);
1402 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1405 SBITMAP_ELT_TYPE
*p
, *r
;
1407 e
= EDGE_PRED (b
, ix
);
1408 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1411 p
= src
[e
->src
->index
]->elms
;
1413 for (i
= 0; i
< set_size
; i
++)
1418 /* Set the bitmap DST to the union of SRC of successors of
1422 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1424 unsigned int set_size
= dst
->size
;
1428 gcc_assert (!dst
->popcount
);
1430 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1432 e
= EDGE_SUCC (b
, ix
);
1433 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1436 bitmap_copy (dst
, src
[e
->dest
->index
]);
1440 if (ix
== EDGE_COUNT (b
->succs
))
1443 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1446 SBITMAP_ELT_TYPE
*p
, *r
;
1448 e
= EDGE_SUCC (b
, ix
);
1449 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1452 p
= src
[e
->dest
->index
]->elms
;
1454 for (i
= 0; i
< set_size
; i
++)
1459 /* Set the bitmap DST to the union of SRC of predecessors of
1463 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1465 unsigned int set_size
= dst
->size
;
1469 gcc_assert (!dst
->popcount
);
1471 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1473 e
= EDGE_PRED (b
, ix
);
1474 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1477 bitmap_copy (dst
, src
[e
->src
->index
]);
1481 if (ix
== EDGE_COUNT (b
->preds
))
1484 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1487 SBITMAP_ELT_TYPE
*p
, *r
;
1489 e
= EDGE_PRED (b
, ix
);
1490 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1493 p
= src
[e
->src
->index
]->elms
;
1495 for (i
= 0; i
< set_size
; i
++)
1500 /* Returns the list of basic blocks in the function in an order that guarantees
1501 that if a block X has just a single predecessor Y, then Y is after X in the
1505 single_pred_before_succ_order (void)
1508 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1509 unsigned n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1511 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1513 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1514 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1516 bitmap_clear (visited
);
1518 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1519 FOR_EACH_BB_FN (x
, cfun
)
1524 /* Walk the predecessors of x as long as they have precisely one
1525 predecessor and add them to the list, so that they get stored
1528 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1529 y
= single_pred (y
))
1531 for (y
= x
, i
= n
- np
;
1532 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1533 y
= single_pred (y
), i
++)
1541 gcc_assert (i
== n
- 1);
1545 sbitmap_free (visited
);
1546 gcc_assert (n
== 0);