1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains various simple utilities to analyze the CFG. */
24 #include "coretypes.h"
32 /* Store the data structures necessary for depth-first search. */
33 class depth_first_search
36 depth_first_search ();
38 basic_block
execute (basic_block
);
39 void add_bb (basic_block
);
42 /* stack for backtracking during the algorithm */
43 auto_vec
<basic_block
, 20> m_stack
;
45 /* record of basic blocks already seen by depth-first search */
46 auto_sbitmap m_visited_blocks
;
50 /* Mark the back edges in DFS traversal.
51 Return nonzero if a loop (natural or otherwise) is present.
52 Inspired by Depth_First_Search_PP described in:
54 Advanced Compiler Design and Implementation
58 and heavily borrowed from pre_and_rev_post_order_compute. */
61 mark_dfs_back_edges (void)
69 /* Allocate the preorder and postorder number arrays. */
70 pre
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
71 post
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
73 /* Allocate stack for back-tracking up CFG. */
74 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
76 /* Allocate bitmap to track nodes that have been visited. */
77 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
79 /* None of the nodes in the CFG have been visited yet. */
80 bitmap_clear (visited
);
82 /* Push the first edge on to the stack. */
83 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
));
85 while (!stack
.is_empty ())
90 /* Look at the edge on the top of the stack. */
91 edge_iterator ei
= stack
.last ();
92 src
= ei_edge (ei
)->src
;
93 dest
= ei_edge (ei
)->dest
;
94 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
96 /* Check if the edge destination has been visited yet. */
97 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && ! bitmap_bit_p (visited
,
100 /* Mark that we have visited the destination. */
101 bitmap_set_bit (visited
, dest
->index
);
103 pre
[dest
->index
] = prenum
++;
104 if (EDGE_COUNT (dest
->succs
) > 0)
106 /* Since the DEST node has been visited for the first
107 time, check its successors. */
108 stack
.quick_push (ei_start (dest
->succs
));
111 post
[dest
->index
] = postnum
++;
115 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
116 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
117 && pre
[src
->index
] >= pre
[dest
->index
]
118 && post
[dest
->index
] == 0)
119 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
, found
= true;
121 if (ei_one_before_end_p (ei
)
122 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
123 post
[src
->index
] = postnum
++;
125 if (!ei_one_before_end_p (ei
))
126 ei_next (&stack
.last ());
138 /* Find unreachable blocks. An unreachable block will have 0 in
139 the reachable bit in block->flags. A nonzero value indicates the
140 block is reachable. */
143 find_unreachable_blocks (void)
147 basic_block
*tos
, *worklist
, bb
;
149 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
151 /* Clear all the reachability flags. */
153 FOR_EACH_BB_FN (bb
, cfun
)
154 bb
->flags
&= ~BB_REACHABLE
;
156 /* Add our starting points to the worklist. Almost always there will
157 be only one. It isn't inconceivable that we might one day directly
158 support Fortran alternate entry points. */
160 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
164 /* Mark the block reachable. */
165 e
->dest
->flags
|= BB_REACHABLE
;
168 /* Iterate: find everything reachable from what we've already seen. */
170 while (tos
!= worklist
)
172 basic_block b
= *--tos
;
174 FOR_EACH_EDGE (e
, ei
, b
->succs
)
176 basic_block dest
= e
->dest
;
178 if (!(dest
->flags
& BB_REACHABLE
))
181 dest
->flags
|= BB_REACHABLE
;
189 /* Verify that there are no unreachable blocks in the current function. */
192 verify_no_unreachable_blocks (void)
194 find_unreachable_blocks ();
197 FOR_EACH_BB_FN (bb
, cfun
)
198 gcc_assert ((bb
->flags
& BB_REACHABLE
) != 0);
202 /* Functions to access an edge list with a vector representation.
203 Enough data is kept such that given an index number, the
204 pred and succ that edge represents can be determined, or
205 given a pred and a succ, its index number can be returned.
206 This allows algorithms which consume a lot of memory to
207 represent the normally full matrix of edge (pred,succ) with a
208 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
209 wasted space in the client code due to sparse flow graphs. */
211 /* This functions initializes the edge list. Basically the entire
212 flowgraph is processed, and all edges are assigned a number,
213 and the data structure is filled in. */
216 create_edge_list (void)
218 struct edge_list
*elist
;
224 /* Determine the number of edges in the flow graph by counting successor
225 edges on each basic block. */
227 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
228 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
230 num_edges
+= EDGE_COUNT (bb
->succs
);
233 elist
= XNEW (struct edge_list
);
234 elist
->num_edges
= num_edges
;
235 elist
->index_to_edge
= XNEWVEC (edge
, num_edges
);
239 /* Follow successors of blocks, and register these edges. */
240 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
241 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
242 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
243 elist
->index_to_edge
[num_edges
++] = e
;
248 /* This function free's memory associated with an edge list. */
251 free_edge_list (struct edge_list
*elist
)
255 free (elist
->index_to_edge
);
260 /* This function provides debug output showing an edge list. */
263 print_edge_list (FILE *f
, struct edge_list
*elist
)
267 fprintf (f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
268 n_basic_blocks_for_fn (cfun
), elist
->num_edges
);
270 for (x
= 0; x
< elist
->num_edges
; x
++)
272 fprintf (f
, " %-4d - edge(", x
);
273 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
274 fprintf (f
, "entry,");
276 fprintf (f
, "%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
278 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR_FOR_FN (cfun
))
279 fprintf (f
, "exit)\n");
281 fprintf (f
, "%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
285 /* This function provides an internal consistency check of an edge list,
286 verifying that all edges are present, and that there are no
290 verify_edge_list (FILE *f
, struct edge_list
*elist
)
292 int pred
, succ
, index
;
294 basic_block bb
, p
, s
;
297 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
298 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
300 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
302 pred
= e
->src
->index
;
303 succ
= e
->dest
->index
;
304 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
305 if (index
== EDGE_INDEX_NO_EDGE
)
307 fprintf (f
, "*p* No index for edge from %d to %d\n", pred
, succ
);
311 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
312 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
313 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
314 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
315 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
316 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
320 /* We've verified that all the edges are in the list, now lets make sure
321 there are no spurious edges in the list. This is an expensive check! */
323 FOR_BB_BETWEEN (p
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
324 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
325 FOR_BB_BETWEEN (s
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
329 FOR_EACH_EDGE (e
, ei
, p
->succs
)
336 FOR_EACH_EDGE (e
, ei
, s
->preds
)
343 if (EDGE_INDEX (elist
, p
, s
)
344 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
345 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
347 if (EDGE_INDEX (elist
, p
, s
)
348 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
349 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
350 p
->index
, s
->index
, EDGE_INDEX (elist
, p
, s
));
355 /* Functions to compute control dependences. */
357 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
359 control_dependences::set_control_dependence_map_bit (basic_block bb
,
362 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
364 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
365 bitmap_set_bit (&control_dependence_map
[bb
->index
], edge_index
);
368 /* Clear all control dependences for block BB. */
370 control_dependences::clear_control_dependence_bitmap (basic_block bb
)
372 bitmap_clear (&control_dependence_map
[bb
->index
]);
375 /* Determine all blocks' control dependences on the given edge with edge_list
376 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
379 control_dependences::find_control_dependence (int edge_index
)
381 basic_block current_block
;
382 basic_block ending_block
;
384 gcc_assert (get_edge_src (edge_index
) != EXIT_BLOCK_PTR_FOR_FN (cfun
));
386 ending_block
= get_immediate_dominator (CDI_POST_DOMINATORS
,
387 get_edge_src (edge_index
));
389 for (current_block
= get_edge_dest (edge_index
);
390 current_block
!= ending_block
391 && current_block
!= EXIT_BLOCK_PTR_FOR_FN (cfun
);
392 current_block
= get_immediate_dominator (CDI_POST_DOMINATORS
,
394 set_control_dependence_map_bit (current_block
, edge_index
);
397 /* Record all blocks' control dependences on all edges in the edge
398 list EL, ala Morgan, Section 3.6. */
400 control_dependences::control_dependences ()
402 timevar_push (TV_CONTROL_DEPENDENCES
);
404 /* Initialize the edge list. */
407 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
408 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
409 num_edges
+= EDGE_COUNT (bb
->succs
);
410 m_el
.create (num_edges
);
413 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
414 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
415 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
417 /* For abnormal edges, we don't make current_block control
418 dependent because instructions that throw are always necessary
420 if (e
->flags
& EDGE_ABNORMAL
)
425 m_el
.quick_push (std::make_pair (e
->src
->index
, e
->dest
->index
));
428 bitmap_obstack_initialize (&m_bitmaps
);
429 control_dependence_map
.create (last_basic_block_for_fn (cfun
));
430 control_dependence_map
.quick_grow (last_basic_block_for_fn (cfun
));
431 for (int i
= 0; i
< last_basic_block_for_fn (cfun
); ++i
)
432 bitmap_initialize (&control_dependence_map
[i
], &m_bitmaps
);
433 for (int i
= 0; i
< num_edges
; ++i
)
434 find_control_dependence (i
);
436 timevar_pop (TV_CONTROL_DEPENDENCES
);
439 /* Free control dependences and the associated edge list. */
441 control_dependences::~control_dependences ()
443 control_dependence_map
.release ();
445 bitmap_obstack_release (&m_bitmaps
);
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 source with index I from the edge list. */
459 control_dependences::get_edge_src (int i
)
461 return BASIC_BLOCK_FOR_FN (cfun
, m_el
[i
].first
);
464 /* Returns the edge destination with index I from the edge list. */
467 control_dependences::get_edge_dest (int i
)
469 return BASIC_BLOCK_FOR_FN (cfun
, m_el
[i
].second
);
473 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
474 If no such edge exists, return NULL. */
477 find_edge (basic_block pred
, basic_block succ
)
482 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
484 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
490 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
498 /* This routine will determine what, if any, edge there is between
499 a specified predecessor and successor. */
502 find_edge_index (struct edge_list
*edge_list
, basic_block pred
, basic_block succ
)
506 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
507 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
508 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
511 return (EDGE_INDEX_NO_EDGE
);
514 /* This routine will remove any fake predecessor edges for a basic block.
515 When the edge is removed, it is also removed from whatever successor
519 remove_fake_predecessors (basic_block bb
)
524 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
526 if ((e
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
533 /* This routine will remove all fake edges from the flow graph. If
534 we remove all fake successors, it will automatically remove all
535 fake predecessors. */
538 remove_fake_edges (void)
542 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, NULL
, next_bb
)
543 remove_fake_predecessors (bb
);
546 /* This routine will remove all fake edges to the EXIT_BLOCK. */
549 remove_fake_exit_edges (void)
551 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun
));
555 /* This function will add a fake edge between any block which has no
556 successors, and the exit block. Some data flow equations require these
560 add_noreturn_fake_exit_edges (void)
564 FOR_EACH_BB_FN (bb
, cfun
)
565 if (EDGE_COUNT (bb
->succs
) == 0)
566 make_single_succ_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
569 /* This function adds a fake edge between any noreturn block and
570 infinite loops to the exit block. Some optimizations require a path
571 from each node to the exit node.
573 See also Morgan, Figure 3.10, pp. 82-83.
575 The current implementation is ugly, not attempting to minimize the
576 number of inserted fake edges. To reduce the number of fake edges
577 to insert, add fake edges from _innermost_ loops containing only
578 nodes not reachable from the exit block. */
581 connect_infinite_loops_to_exit (void)
583 /* First add fake exits to noreturn blocks, this is required to
584 discover only truly infinite loops below. */
585 add_noreturn_fake_exit_edges ();
587 /* Perform depth-first search in the reverse graph to find nodes
588 reachable from the exit block. */
589 depth_first_search dfs
;
590 dfs
.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
592 /* Repeatedly add fake edges, updating the unreachable nodes. */
593 basic_block unvisited_block
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
596 unvisited_block
= dfs
.execute (unvisited_block
);
597 if (!unvisited_block
)
600 basic_block deadend_block
= dfs_find_deadend (unvisited_block
);
601 edge e
= make_edge (deadend_block
, EXIT_BLOCK_PTR_FOR_FN (cfun
),
603 e
->probability
= profile_probability::never ();
604 dfs
.add_bb (deadend_block
);
608 /* Compute reverse top sort order. This is computing a post order
609 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
610 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
611 true, unreachable blocks are deleted. */
614 post_order_compute (int *post_order
, bool include_entry_exit
,
615 bool delete_unreachable
)
617 int post_order_num
= 0;
620 if (include_entry_exit
)
621 post_order
[post_order_num
++] = EXIT_BLOCK
;
623 /* Allocate stack for back-tracking up CFG. */
624 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
626 /* Allocate bitmap to track nodes that have been visited. */
627 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
629 /* None of the nodes in the CFG have been visited yet. */
630 bitmap_clear (visited
);
632 /* Push the first edge on to the stack. */
633 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
));
635 while (!stack
.is_empty ())
640 /* Look at the edge on the top of the stack. */
641 edge_iterator ei
= stack
.last ();
642 src
= ei_edge (ei
)->src
;
643 dest
= ei_edge (ei
)->dest
;
645 /* Check if the edge destination has been visited yet. */
646 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
647 && ! bitmap_bit_p (visited
, dest
->index
))
649 /* Mark that we have visited the destination. */
650 bitmap_set_bit (visited
, dest
->index
);
652 if (EDGE_COUNT (dest
->succs
) > 0)
653 /* Since the DEST node has been visited for the first
654 time, check its successors. */
655 stack
.quick_push (ei_start (dest
->succs
));
657 post_order
[post_order_num
++] = dest
->index
;
661 if (ei_one_before_end_p (ei
)
662 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
663 post_order
[post_order_num
++] = src
->index
;
665 if (!ei_one_before_end_p (ei
))
666 ei_next (&stack
.last ());
672 if (include_entry_exit
)
674 post_order
[post_order_num
++] = ENTRY_BLOCK
;
675 count
= post_order_num
;
678 count
= post_order_num
+ 2;
680 /* Delete the unreachable blocks if some were found and we are
681 supposed to do it. */
682 if (delete_unreachable
&& (count
!= n_basic_blocks_for_fn (cfun
)))
686 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
687 != EXIT_BLOCK_PTR_FOR_FN (cfun
); b
= next_bb
)
689 next_bb
= b
->next_bb
;
691 if (!(bitmap_bit_p (visited
, b
->index
)))
692 delete_basic_block (b
);
695 tidy_fallthru_edges ();
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
)
728 basic_block next
= bb
;
732 if (EDGE_COUNT (next
->succs
) == 0)
735 if (! bitmap_set_bit (visited
, next
->index
))
739 /* If we are in an analyzed cycle make sure to try exiting it.
740 Note this is a heuristic only and expected to work when loop
741 fixup is needed as well. */
742 if (! bb
->loop_father
743 || ! loop_outer (bb
->loop_father
))
744 next
= EDGE_SUCC (bb
, 0)->dest
;
749 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
750 if (loop_exit_edge_p (bb
->loop_father
, e
))
752 next
= e
? e
->dest
: EDGE_SUCC (bb
, 0)->dest
;
760 /* Compute the reverse top sort order of the inverted CFG
761 i.e. starting from the exit block and following the edges backward
762 (from successors to predecessors).
763 This ordering can be used for forward dataflow problems among others.
765 Optionally if START_POINTS is specified, start from exit block and all
766 basic blocks in START_POINTS. This is used by CD-DCE.
768 This function assumes that all blocks in the CFG are reachable
769 from the ENTRY (but not necessarily from EXIT).
771 If there's an infinite loop,
772 a simple inverted traversal starting from the blocks
773 with no successors can't visit all blocks.
774 To solve this problem, we first do inverted traversal
775 starting from the blocks with no successor.
776 And if there's any block left that's not visited by the regular
777 inverted traversal from EXIT,
778 those blocks are in such problematic region.
779 Among those, we find one block that has
780 any visited predecessor (which is an entry into such a region),
781 and start looking for a "dead end" from that block
782 and do another inverted traversal from that block. */
785 inverted_post_order_compute (vec
<int> *post_order
,
786 sbitmap
*start_points
)
789 post_order
->reserve_exact (n_basic_blocks_for_fn (cfun
));
792 verify_no_unreachable_blocks ();
794 /* Allocate stack for back-tracking up CFG. */
795 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
797 /* Allocate bitmap to track nodes that have been visited. */
798 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
800 /* None of the nodes in the CFG have been visited yet. */
801 bitmap_clear (visited
);
805 FOR_ALL_BB_FN (bb
, cfun
)
806 if (bitmap_bit_p (*start_points
, bb
->index
)
807 && EDGE_COUNT (bb
->preds
) > 0)
809 stack
.quick_push (ei_start (bb
->preds
));
810 bitmap_set_bit (visited
, bb
->index
);
812 if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
))
814 stack
.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
));
815 bitmap_set_bit (visited
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->index
);
819 /* Put all blocks that have no successor into the initial work list. */
820 FOR_ALL_BB_FN (bb
, cfun
)
821 if (EDGE_COUNT (bb
->succs
) == 0)
823 /* Push the initial edge on to the stack. */
824 if (EDGE_COUNT (bb
->preds
) > 0)
826 stack
.quick_push (ei_start (bb
->preds
));
827 bitmap_set_bit (visited
, bb
->index
);
833 bool has_unvisited_bb
= false;
835 /* The inverted traversal loop. */
836 while (!stack
.is_empty ())
841 /* Look at the edge on the top of the stack. */
843 bb
= ei_edge (ei
)->dest
;
844 pred
= ei_edge (ei
)->src
;
846 /* Check if the predecessor has been visited yet. */
847 if (! bitmap_bit_p (visited
, pred
->index
))
849 /* Mark that we have visited the destination. */
850 bitmap_set_bit (visited
, pred
->index
);
852 if (EDGE_COUNT (pred
->preds
) > 0)
853 /* Since the predecessor node has been visited for the first
854 time, check its predecessors. */
855 stack
.quick_push (ei_start (pred
->preds
));
857 post_order
->quick_push (pred
->index
);
861 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
862 && ei_one_before_end_p (ei
))
863 post_order
->quick_push (bb
->index
);
865 if (!ei_one_before_end_p (ei
))
866 ei_next (&stack
.last ());
872 /* Detect any infinite loop and activate the kludge.
873 Note that this doesn't check EXIT_BLOCK itself
874 since EXIT_BLOCK is always added after the outer do-while loop. */
875 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
876 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
877 if (!bitmap_bit_p (visited
, bb
->index
))
879 has_unvisited_bb
= true;
881 if (EDGE_COUNT (bb
->preds
) > 0)
885 basic_block visited_pred
= NULL
;
887 /* Find an already visited predecessor. */
888 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
890 if (bitmap_bit_p (visited
, e
->src
->index
))
891 visited_pred
= e
->src
;
896 basic_block be
= dfs_find_deadend (bb
);
897 gcc_assert (be
!= NULL
);
898 bitmap_set_bit (visited
, be
->index
);
899 stack
.quick_push (ei_start (be
->preds
));
905 if (has_unvisited_bb
&& stack
.is_empty ())
907 /* No blocks are reachable from EXIT at all.
908 Find a dead-end from the ENTRY, and restart the iteration. */
909 basic_block be
= dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
910 gcc_assert (be
!= NULL
);
911 bitmap_set_bit (visited
, be
->index
);
912 stack
.quick_push (ei_start (be
->preds
));
915 /* The only case the below while fires is
916 when there's an infinite loop. */
918 while (!stack
.is_empty ());
920 /* EXIT_BLOCK is always included. */
921 post_order
->quick_push (EXIT_BLOCK
);
924 /* Compute the depth first search order of FN and store in the array
925 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
926 reverse completion number for each node. Returns the number of nodes
927 visited. A depth first search tries to get as far away from the starting
928 point as quickly as possible.
930 In case the function has unreachable blocks the number of nodes
931 visited does not include them.
933 pre_order is a really a preorder numbering of the graph.
934 rev_post_order is really a reverse postorder numbering of the graph. */
937 pre_and_rev_post_order_compute_fn (struct function
*fn
,
938 int *pre_order
, int *rev_post_order
,
939 bool include_entry_exit
)
941 int pre_order_num
= 0;
942 int rev_post_order_num
= n_basic_blocks_for_fn (fn
) - 1;
944 /* Allocate stack for back-tracking up CFG. */
945 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (fn
) + 1);
947 if (include_entry_exit
)
950 pre_order
[pre_order_num
] = ENTRY_BLOCK
;
953 rev_post_order
[rev_post_order_num
--] = EXIT_BLOCK
;
956 rev_post_order_num
-= NUM_FIXED_BLOCKS
;
958 /* BB flag to track nodes that have been visited. */
959 auto_bb_flag
visited (fn
);
961 /* Push the first edge on to the stack. */
962 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
));
964 while (!stack
.is_empty ())
969 /* Look at the edge on the top of the stack. */
970 edge_iterator ei
= stack
.last ();
971 src
= ei_edge (ei
)->src
;
972 dest
= ei_edge (ei
)->dest
;
974 /* Check if the edge destination has been visited yet. */
975 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (fn
)
976 && ! (dest
->flags
& visited
))
978 /* Mark that we have visited the destination. */
979 dest
->flags
|= visited
;
982 pre_order
[pre_order_num
] = dest
->index
;
986 if (EDGE_COUNT (dest
->succs
) > 0)
987 /* Since the DEST node has been visited for the first
988 time, check its successors. */
989 stack
.quick_push (ei_start (dest
->succs
));
990 else if (rev_post_order
)
991 /* There are no successors for the DEST node so assign
992 its reverse completion number. */
993 rev_post_order
[rev_post_order_num
--] = dest
->index
;
997 if (ei_one_before_end_p (ei
)
998 && src
!= ENTRY_BLOCK_PTR_FOR_FN (fn
)
1000 /* There are no more successors for the SRC node
1001 so assign its reverse completion number. */
1002 rev_post_order
[rev_post_order_num
--] = src
->index
;
1004 if (!ei_one_before_end_p (ei
))
1005 ei_next (&stack
.last ());
1011 if (include_entry_exit
)
1014 pre_order
[pre_order_num
] = EXIT_BLOCK
;
1017 rev_post_order
[rev_post_order_num
--] = ENTRY_BLOCK
;
1020 /* Clear the temporarily allocated flag. */
1021 if (!rev_post_order
)
1022 rev_post_order
= pre_order
;
1023 for (int i
= 0; i
< pre_order_num
; ++i
)
1024 BASIC_BLOCK_FOR_FN (fn
, rev_post_order
[i
])->flags
&= ~visited
;
1026 return pre_order_num
;
1029 /* Like pre_and_rev_post_order_compute_fn but operating on the
1030 current function and asserting that all nodes were visited. */
1033 pre_and_rev_post_order_compute (int *pre_order
, int *rev_post_order
,
1034 bool include_entry_exit
)
1037 = pre_and_rev_post_order_compute_fn (cfun
, pre_order
, rev_post_order
,
1038 include_entry_exit
);
1039 if (include_entry_exit
)
1040 /* The number of nodes visited should be the number of blocks. */
1041 gcc_assert (pre_order_num
== n_basic_blocks_for_fn (cfun
));
1043 /* The number of nodes visited should be the number of blocks minus
1044 the entry and exit blocks which are not visited here. */
1045 gcc_assert (pre_order_num
1046 == (n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
));
1048 return pre_order_num
;
1052 /* Per basic-block data for rev_post_order_and_mark_dfs_back_seme,
1053 element of a sparsely populated array indexed by basic-block number. */
1054 typedef auto_vec
<int, 2> scc_exit_vec_t
;
1055 struct rpoamdbs_bb_data
{
1058 /* The basic-block index of the SCC entry of the block visited first
1059 (the SCC leader). */
1061 /* The index into the RPO array where the blocks SCC entries end
1062 (only valid for the SCC leader). */
1064 /* The indexes of the exits destinations of this SCC (only valid
1065 for the SCC leader). Initialized upon discovery of SCC leaders. */
1066 scc_exit_vec_t scc_exits
;
1069 /* Tag H as a header of B, weaving H and its loop header list into the
1070 current loop header list of B. */
1073 tag_header (int b
, int h
, rpoamdbs_bb_data
*bb_data
)
1075 if (h
== -1 || b
== h
)
1079 while (bb_data
[cur1
].scc
!= -1)
1081 int ih
= bb_data
[cur1
].scc
;
1084 if (bb_data
[ih
].depth
< bb_data
[cur2
].depth
)
1086 bb_data
[cur1
].scc
= cur2
;
1093 bb_data
[cur1
].scc
= cur2
;
1096 /* Comparator for a sort of two edges destinations E1 and E2 after their index
1097 in the PRE array as specified by BB_TO_PRE. */
1100 cmp_edge_dest_pre (const void *e1_
, const void *e2_
, void *data_
)
1102 const int *e1
= (const int *)e1_
;
1103 const int *e2
= (const int *)e2_
;
1104 rpoamdbs_bb_data
*bb_data
= (rpoamdbs_bb_data
*)data_
;
1105 return (bb_data
[*e1
].bb_to_pre
- bb_data
[*e2
].bb_to_pre
);
1108 /* Compute the reverse completion number of a depth first search
1109 on the SEME region denoted by the ENTRY edge and the EXIT_BBS set of
1110 exit block indexes and store it in the array REV_POST_ORDER.
1111 Also sets the EDGE_DFS_BACK edge flags according to this visitation
1113 Returns the number of nodes visited.
1115 In case the function has unreachable blocks the number of nodes
1116 visited does not include them.
1118 If FOR_ITERATION is true then compute an RPO where SCCs form a
1119 contiguous region in the RPO array.
1120 *TOPLEVEL_SCC_EXTENTS if not NULL is filled with pairs of
1121 *REV_POST_ORDER indexes denoting extents of the toplevel SCCs in
1125 rev_post_order_and_mark_dfs_back_seme (struct function
*fn
, edge entry
,
1126 bitmap exit_bbs
, bool for_iteration
,
1127 int *rev_post_order
,
1128 vec
<std::pair
<int, int> >
1129 *toplevel_scc_extents
)
1131 int rev_post_order_num
= 0;
1133 /* BB flag to track nodes that have been visited. */
1134 auto_bb_flag
visited (fn
);
1136 /* Lazily initialized per-BB data for the two DFS walks below. */
1137 rpoamdbs_bb_data
*bb_data
1138 = XNEWVEC (rpoamdbs_bb_data
, last_basic_block_for_fn (fn
));
1140 /* First DFS walk, loop discovery according to
1141 A New Algorithm for Identifying Loops in Decompilation
1142 by Tao Wei, Jian Mao, Wei Zou and You Chen of the Institute of
1143 Computer Science and Technology of the Peking University. */
1144 auto_vec
<edge_iterator
, 20> ei_stack (n_basic_blocks_for_fn (fn
) + 1);
1145 auto_bb_flag
is_header (fn
);
1147 unsigned n_sccs
= 0;
1149 basic_block dest
= entry
->dest
;
1153 /* DFS process DEST. */
1155 bb_data
[dest
->index
].bb_to_pre
= pre_num
++;
1156 bb_data
[dest
->index
].depth
= depth
;
1157 bb_data
[dest
->index
].scc
= -1;
1159 gcc_assert ((dest
->flags
& (is_header
|visited
)) == 0);
1160 dest
->flags
|= visited
;
1161 ei
= ei_start (dest
->succs
);
1162 while (!ei_end_p (ei
))
1164 ei_edge (ei
)->flags
&= ~EDGE_DFS_BACK
;
1165 if (bitmap_bit_p (exit_bbs
, ei_edge (ei
)->dest
->index
))
1167 else if (!(ei_edge (ei
)->dest
->flags
& visited
))
1169 ei_stack
.quick_push (ei
);
1170 dest
= ei_edge (ei
)->dest
;
1171 /* DFS recurse on DEST. */
1174 ret_from_find_loops
:
1175 /* Return point of DFS recursion. */
1176 ei
= ei_stack
.pop ();
1177 dest
= ei_edge (ei
)->src
;
1178 int header
= bb_data
[ei_edge (ei
)->dest
->index
].scc
;
1179 tag_header (dest
->index
, header
, bb_data
);
1180 depth
= bb_data
[dest
->index
].depth
+ 1;
1184 if (bb_data
[ei_edge (ei
)->dest
->index
].depth
> 0) /* on the stack */
1186 ei_edge (ei
)->flags
|= EDGE_DFS_BACK
;
1188 ei_edge (ei
)->dest
->flags
|= is_header
;
1189 ::new (&bb_data
[ei_edge (ei
)->dest
->index
].scc_exits
)
1190 auto_vec
<int, 2> ();
1191 tag_header (dest
->index
, ei_edge (ei
)->dest
->index
, bb_data
);
1193 else if (bb_data
[ei_edge (ei
)->dest
->index
].scc
== -1)
1197 int header
= bb_data
[ei_edge (ei
)->dest
->index
].scc
;
1198 if (bb_data
[header
].depth
> 0)
1199 tag_header (dest
->index
, header
, bb_data
);
1202 /* A re-entry into an existing loop. */
1203 /* ??? Need to mark is_header? */
1204 while (bb_data
[header
].scc
!= -1)
1206 header
= bb_data
[header
].scc
;
1207 if (bb_data
[header
].depth
> 0)
1209 tag_header (dest
->index
, header
, bb_data
);
1218 rev_post_order
[rev_post_order_num
++] = dest
->index
;
1219 /* not on the stack anymore */
1220 bb_data
[dest
->index
].depth
= -bb_data
[dest
->index
].depth
;
1221 if (!ei_stack
.is_empty ())
1222 /* Return from DFS recursion. */
1223 goto ret_from_find_loops
;
1225 /* Optimize for no SCCs found or !for_iteration. */
1226 if (n_sccs
== 0 || !for_iteration
)
1228 /* Clear the temporarily allocated flags. */
1229 for (int i
= 0; i
< rev_post_order_num
; ++i
)
1230 BASIC_BLOCK_FOR_FN (fn
, rev_post_order
[i
])->flags
1231 &= ~(is_header
|visited
);
1232 /* And swap elements. */
1233 for (int i
= 0; i
< rev_post_order_num
/2; ++i
)
1234 std::swap (rev_post_order
[i
], rev_post_order
[rev_post_order_num
-i
-1]);
1235 XDELETEVEC (bb_data
);
1237 return rev_post_order_num
;
1240 /* Next find SCC exits, clear the visited flag and compute an upper bound
1241 for the edge stack below. */
1242 unsigned edge_count
= 0;
1243 for (int i
= 0; i
< rev_post_order_num
; ++i
)
1245 int bb
= rev_post_order
[i
];
1246 BASIC_BLOCK_FOR_FN (fn
, bb
)->flags
&= ~visited
;
1248 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (fn
, bb
)->succs
)
1250 if (bitmap_bit_p (exit_bbs
, e
->dest
->index
))
1253 /* if e is an exit from e->src, record it for
1254 bb_data[e->src].scc. */
1255 int src_scc
= e
->src
->index
;
1256 if (!(e
->src
->flags
& is_header
))
1257 src_scc
= bb_data
[src_scc
].scc
;
1260 int dest_scc
= e
->dest
->index
;
1261 if (!(e
->dest
->flags
& is_header
))
1262 dest_scc
= bb_data
[dest_scc
].scc
;
1263 if (src_scc
== dest_scc
)
1265 /* When dest_scc is nested insde src_scc it's not an
1267 int tem_dest_scc
= dest_scc
;
1268 unsigned dest_scc_depth
= 0;
1269 while (tem_dest_scc
!= -1)
1272 if ((tem_dest_scc
= bb_data
[tem_dest_scc
].scc
) == src_scc
)
1275 if (tem_dest_scc
!= -1)
1277 /* When src_scc is nested inside dest_scc record an
1278 exit from the outermost SCC this edge exits. */
1279 int tem_src_scc
= src_scc
;
1280 unsigned src_scc_depth
= 0;
1281 while (tem_src_scc
!= -1)
1283 if (bb_data
[tem_src_scc
].scc
== dest_scc
)
1286 bb_data
[tem_src_scc
].scc_exits
.safe_push (e
->dest
->index
);
1289 tem_src_scc
= bb_data
[tem_src_scc
].scc
;
1292 /* Else find the outermost SCC this edge exits (exits
1293 from the inner SCCs are not important for the DFS
1294 walk adjustment). Do so by computing the common
1295 ancestor SCC where the immediate child it to the source
1296 SCC is the exited SCC. */
1297 if (tem_src_scc
== -1)
1300 while (src_scc_depth
> dest_scc_depth
)
1302 src_scc
= bb_data
[src_scc
].scc
;
1305 while (dest_scc_depth
> src_scc_depth
)
1307 dest_scc
= bb_data
[dest_scc
].scc
;
1310 while (bb_data
[src_scc
].scc
!= bb_data
[dest_scc
].scc
)
1312 src_scc
= bb_data
[src_scc
].scc
;
1313 dest_scc
= bb_data
[dest_scc
].scc
;
1315 bb_data
[src_scc
].scc_exits
.safe_push (e
->dest
->index
);
1320 /* Now the second DFS walk to compute a RPO where the extent of SCCs
1321 is minimized thus SCC members are adjacent in the RPO array.
1322 This is done by performing a DFS walk computing RPO with first visiting
1323 extra direct edges from SCC entry to its exits.
1324 That simulates a DFS walk over the graph with SCCs collapsed and
1325 walking the SCCs themselves only when all outgoing edges from the
1326 SCCs have been visited.
1327 SCC_END[scc-header-index] is the position in the RPO array of the
1328 last member of the SCC. */
1329 auto_vec
<std::pair
<basic_block
, basic_block
>, 20> estack (edge_count
+ 1);
1330 int idx
= rev_post_order_num
;
1334 /* DFS process DEST. */
1336 gcc_checking_assert ((dest
->flags
& visited
) == 0);
1337 /* Verify we enter SCCs through the same header and SCC nesting appears
1339 gcc_assert (bb_data
[dest
->index
].scc
== -1
1340 || (BASIC_BLOCK_FOR_FN (fn
, bb_data
[dest
->index
].scc
)->flags
1342 dest
->flags
|= visited
;
1343 bb_data
[dest
->index
].scc_end
= -1;
1344 if ((dest
->flags
& is_header
)
1345 && !bb_data
[dest
->index
].scc_exits
.is_empty ())
1347 /* Push the all SCC exits as outgoing edges from its header to
1349 To process exits in the same relative order as in the first
1350 DFS walk sort them after their destination PRE order index. */
1351 gcc_sort_r (&bb_data
[dest
->index
].scc_exits
[0],
1352 bb_data
[dest
->index
].scc_exits
.length (),
1353 sizeof (int), cmp_edge_dest_pre
, bb_data
);
1354 /* Process edges in reverse to match previous DFS walk order. */
1355 for (int i
= bb_data
[dest
->index
].scc_exits
.length () - 1; i
>= 0; --i
)
1356 estack
.quick_push (std::make_pair
1357 (dest
, BASIC_BLOCK_FOR_FN (fn
, bb_data
[dest
->index
].scc_exits
[i
])));
1361 if (dest
->flags
& is_header
)
1362 bb_data
[dest
->index
].scc_end
= idx
- 1;
1363 /* Push the edge vector in reverse to match the iteration order
1364 from the DFS walk above. */
1365 for (int i
= EDGE_COUNT (dest
->succs
) - 1; i
>= 0; --i
)
1366 if (!bitmap_bit_p (exit_bbs
, EDGE_SUCC (dest
, i
)->dest
->index
))
1367 estack
.quick_push (std::make_pair (dest
,
1368 EDGE_SUCC (dest
, i
)->dest
));
1370 while (!estack
.is_empty ()
1371 && estack
.last ().first
== dest
)
1373 edest
= estack
.last ().second
;
1374 if (!(edest
->flags
& visited
))
1377 /* DFS recurse on DEST. */
1381 /* Return point of DFS recursion. */
1382 dest
= estack
.last ().first
;
1385 /* If we processed all SCC exits from DEST mark the SCC end
1386 since all RPO entries up to DEST itself will now belong
1387 to its SCC. The special-case of no SCC exits is already
1388 dealt with above. */
1389 if (dest
->flags
& is_header
1390 /* When the last exit edge was processed mark the SCC end
1391 and push the regular edges. */
1392 && bb_data
[dest
->index
].scc_end
== -1
1393 && (estack
.is_empty ()
1394 || estack
.last ().first
!= dest
))
1396 bb_data
[dest
->index
].scc_end
= idx
- 1;
1397 /* Push the edge vector in reverse to match the iteration order
1398 from the DFS walk above. */
1399 for (int i
= EDGE_COUNT (dest
->succs
) - 1; i
>= 0; --i
)
1400 if (!bitmap_bit_p (exit_bbs
, EDGE_SUCC (dest
, i
)->dest
->index
))
1401 estack
.quick_push (std::make_pair (dest
,
1402 EDGE_SUCC (dest
, i
)->dest
));
1405 rev_post_order
[--idx
] = dest
->index
;
1406 if (!estack
.is_empty ())
1407 /* Return from DFS recursion. */
1408 goto ret_from_dfs_rpo
;
1410 /* Each SCC extends are from the position of the header inside
1411 the RPO array up to RPO array index scc_end[header-index]. */
1412 if (toplevel_scc_extents
)
1413 for (int i
= 0; i
< rev_post_order_num
; i
++)
1415 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rev_post_order
[i
]);
1416 if (bb
->flags
& is_header
)
1418 toplevel_scc_extents
->safe_push
1419 (std::make_pair (i
, bb_data
[bb
->index
].scc_end
));
1420 i
= bb_data
[bb
->index
].scc_end
;
1424 /* Clear the temporarily allocated flags and free memory. */
1425 for (int i
= 0; i
< rev_post_order_num
; ++i
)
1427 basic_block bb
= BASIC_BLOCK_FOR_FN (fn
, rev_post_order
[i
]);
1428 if (bb
->flags
& is_header
)
1429 bb_data
[bb
->index
].scc_exits
.~scc_exit_vec_t ();
1430 bb
->flags
&= ~(visited
|is_header
);
1433 XDELETEVEC (bb_data
);
1435 return rev_post_order_num
;
1440 /* Compute the depth first search order on the _reverse_ graph and
1441 store it in the array DFS_ORDER, marking the nodes visited in VISITED.
1442 Returns the number of nodes visited.
1444 The computation is split into three pieces:
1446 flow_dfs_compute_reverse_init () creates the necessary data
1449 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1450 structures. The block will start the search.
1452 flow_dfs_compute_reverse_execute () continues (or starts) the
1453 search using the block on the top of the stack, stopping when the
1456 flow_dfs_compute_reverse_finish () destroys the necessary data
1459 Thus, the user will probably call ..._init(), call ..._add_bb() to
1460 add a beginning basic block to the stack, call ..._execute(),
1461 possibly add another bb to the stack and again call ..._execute(),
1462 ..., and finally call _finish(). */
1464 /* Initialize the data structures used for depth-first search on the
1465 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1466 added to the basic block stack. DATA is the current depth-first
1467 search context. If INITIALIZE_STACK is nonzero, there is an
1468 element on the stack. */
1470 depth_first_search::depth_first_search () :
1471 m_stack (n_basic_blocks_for_fn (cfun
)),
1472 m_visited_blocks (last_basic_block_for_fn (cfun
))
1474 bitmap_clear (m_visited_blocks
);
1477 /* Add the specified basic block to the top of the dfs data
1478 structures. When the search continues, it will start at the
1482 depth_first_search::add_bb (basic_block bb
)
1484 m_stack
.quick_push (bb
);
1485 bitmap_set_bit (m_visited_blocks
, bb
->index
);
1488 /* Continue the depth-first search through the reverse graph starting with the
1489 block at the stack's top and ending when the stack is empty. Visited nodes
1490 are marked. Returns an unvisited basic block, or NULL if there is none
1494 depth_first_search::execute (basic_block last_unvisited
)
1500 while (!m_stack
.is_empty ())
1502 bb
= m_stack
.pop ();
1504 /* Perform depth-first search on adjacent vertices. */
1505 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1506 if (!bitmap_bit_p (m_visited_blocks
, e
->src
->index
))
1510 /* Determine if there are unvisited basic blocks. */
1511 FOR_BB_BETWEEN (bb
, last_unvisited
, NULL
, prev_bb
)
1512 if (!bitmap_bit_p (m_visited_blocks
, bb
->index
))
1518 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1519 if REVERSE, go against direction of edges. Returns number of blocks
1520 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1522 dfs_enumerate_from (basic_block bb
, int reverse
,
1523 bool (*predicate
) (const_basic_block
, const void *),
1524 basic_block
*rslt
, int rslt_max
, const void *data
)
1526 basic_block
*st
, lbb
;
1529 auto_bb_flag
visited (cfun
);
1531 #define MARK_VISITED(BB) ((BB)->flags |= visited)
1532 #define UNMARK_VISITED(BB) ((BB)->flags &= ~visited)
1533 #define VISITED_P(BB) (((BB)->flags & visited) != 0)
1535 st
= XNEWVEC (basic_block
, rslt_max
);
1536 rslt
[tv
++] = st
[sp
++] = bb
;
1545 FOR_EACH_EDGE (e
, ei
, lbb
->preds
)
1546 if (!VISITED_P (e
->src
) && predicate (e
->src
, data
))
1548 gcc_assert (tv
!= rslt_max
);
1549 rslt
[tv
++] = st
[sp
++] = e
->src
;
1550 MARK_VISITED (e
->src
);
1555 FOR_EACH_EDGE (e
, ei
, lbb
->succs
)
1556 if (!VISITED_P (e
->dest
) && predicate (e
->dest
, data
))
1558 gcc_assert (tv
!= rslt_max
);
1559 rslt
[tv
++] = st
[sp
++] = e
->dest
;
1560 MARK_VISITED (e
->dest
);
1565 for (sp
= 0; sp
< tv
; sp
++)
1566 UNMARK_VISITED (rslt
[sp
]);
1569 #undef UNMARK_VISITED
1574 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1576 This algorithm can be found in Timothy Harvey's PhD thesis, at
1577 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1578 dominance algorithms.
1580 First, we identify each join point, j (any node with more than one
1581 incoming edge is a join point).
1583 We then examine each predecessor, p, of j and walk up the dominator tree
1586 We stop the walk when we reach j's immediate dominator - j is in the
1587 dominance frontier of each of the nodes in the walk, except for j's
1588 immediate dominator. Intuitively, all of the rest of j's dominators are
1589 shared by j's predecessors as well.
1590 Since they dominate j, they will not have j in their dominance frontiers.
1592 The number of nodes touched by this algorithm is equal to the size
1593 of the dominance frontiers, no more, no less.
1597 compute_dominance_frontiers (bitmap_head
*frontiers
)
1599 timevar_push (TV_DOM_FRONTIERS
);
1604 FOR_EACH_BB_FN (b
, cfun
)
1606 if (EDGE_COUNT (b
->preds
) >= 2)
1608 basic_block domsb
= get_immediate_dominator (CDI_DOMINATORS
, b
);
1609 FOR_EACH_EDGE (p
, ei
, b
->preds
)
1611 basic_block runner
= p
->src
;
1612 if (runner
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1615 while (runner
!= domsb
)
1617 if (!bitmap_set_bit (&frontiers
[runner
->index
], b
->index
))
1619 runner
= get_immediate_dominator (CDI_DOMINATORS
, runner
);
1625 timevar_pop (TV_DOM_FRONTIERS
);
1628 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1629 return a bitmap with all the blocks in the iterated dominance
1630 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1631 frontier information as returned by compute_dominance_frontiers.
1633 The resulting set of blocks are the potential sites where PHI nodes
1634 are needed. The caller is responsible for freeing the memory
1635 allocated for the return value. */
1638 compute_idf (bitmap def_blocks
, bitmap_head
*dfs
)
1641 unsigned bb_index
, i
;
1642 bitmap phi_insertion_points
;
1644 phi_insertion_points
= BITMAP_ALLOC (NULL
);
1646 /* Seed the work set with all the blocks in DEF_BLOCKS. */
1647 auto_bitmap work_set
;
1648 bitmap_copy (work_set
, def_blocks
);
1649 bitmap_tree_view (work_set
);
1651 /* Pop a block off the workset, add every block that appears in
1652 the original block's DF that we have not already processed to
1653 the workset. Iterate until the workset is empty. Blocks
1654 which are added to the workset are potential sites for
1656 while (!bitmap_empty_p (work_set
))
1658 /* The dominance frontier of a block is blocks after it so iterating
1659 on earlier blocks first is better.
1660 ??? Basic blocks are by no means guaranteed to be ordered in
1661 optimal order for this iteration. */
1662 bb_index
= bitmap_first_set_bit (work_set
);
1663 bitmap_clear_bit (work_set
, bb_index
);
1665 /* Since the registration of NEW -> OLD name mappings is done
1666 separately from the call to update_ssa, when updating the SSA
1667 form, the basic blocks where new and/or old names are defined
1668 may have disappeared by CFG cleanup calls. In this case,
1669 we may pull a non-existing block from the work stack. */
1670 gcc_checking_assert (bb_index
1671 < (unsigned) last_basic_block_for_fn (cfun
));
1673 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs
[bb_index
], phi_insertion_points
,
1676 bitmap_set_bit (work_set
, i
);
1677 bitmap_set_bit (phi_insertion_points
, i
);
1681 return phi_insertion_points
;
1684 /* Intersection and union of preds/succs for sbitmap based data flow
1685 solvers. All four functions defined below take the same arguments:
1686 B is the basic block to perform the operation for. DST is the
1687 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1688 last_basic_block so that it can be indexed with basic block indices.
1689 DST may be (but does not have to be) SRC[B->index]. */
1691 /* Set the bitmap DST to the intersection of SRC of successors of
1695 bitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1697 unsigned int set_size
= dst
->size
;
1701 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1703 e
= EDGE_SUCC (b
, ix
);
1704 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1707 bitmap_copy (dst
, src
[e
->dest
->index
]);
1714 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
1717 SBITMAP_ELT_TYPE
*p
, *r
;
1719 e
= EDGE_SUCC (b
, ix
);
1720 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1723 p
= src
[e
->dest
->index
]->elms
;
1725 for (i
= 0; i
< set_size
; i
++)
1730 /* Set the bitmap DST to the intersection of SRC of predecessors of
1734 bitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1736 unsigned int set_size
= dst
->size
;
1740 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1742 e
= EDGE_PRED (b
, ix
);
1743 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1746 bitmap_copy (dst
, src
[e
->src
->index
]);
1753 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
1756 SBITMAP_ELT_TYPE
*p
, *r
;
1758 e
= EDGE_PRED (b
, ix
);
1759 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1762 p
= src
[e
->src
->index
]->elms
;
1764 for (i
= 0; i
< set_size
; i
++)
1769 /* Set the bitmap DST to the union of SRC of successors of
1773 bitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, basic_block b
)
1775 unsigned int set_size
= dst
->size
;
1779 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
1781 e
= EDGE_SUCC (b
, ix
);
1782 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1785 bitmap_copy (dst
, src
[e
->dest
->index
]);
1789 if (ix
== EDGE_COUNT (b
->succs
))
1792 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
1795 SBITMAP_ELT_TYPE
*p
, *r
;
1797 e
= EDGE_SUCC (b
, ix
);
1798 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1801 p
= src
[e
->dest
->index
]->elms
;
1803 for (i
= 0; i
< set_size
; i
++)
1808 /* Set the bitmap DST to the union of SRC of predecessors of
1812 bitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, basic_block b
)
1814 unsigned int set_size
= dst
->size
;
1818 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
1820 e
= EDGE_PRED (b
, ix
);
1821 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1824 bitmap_copy (dst
, src
[e
->src
->index
]);
1828 if (ix
== EDGE_COUNT (b
->preds
))
1831 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
1834 SBITMAP_ELT_TYPE
*p
, *r
;
1836 e
= EDGE_PRED (b
, ix
);
1837 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1840 p
= src
[e
->src
->index
]->elms
;
1842 for (i
= 0; i
< set_size
; i
++)
1847 /* Returns the list of basic blocks in the function in an order that guarantees
1848 that if a block X has just a single predecessor Y, then Y is after X in the
1852 single_pred_before_succ_order (void)
1855 basic_block
*order
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1856 unsigned n
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
1858 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
1860 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1861 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1863 bitmap_clear (visited
);
1865 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1866 FOR_EACH_BB_FN (x
, cfun
)
1871 /* Walk the predecessors of x as long as they have precisely one
1872 predecessor and add them to the list, so that they get stored
1875 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1876 y
= single_pred (y
))
1878 for (y
= x
, i
= n
- np
;
1879 single_pred_p (y
) && !VISITED_P (single_pred (y
));
1880 y
= single_pred (y
), i
++)
1888 gcc_assert (i
== n
- 1);
1892 gcc_assert (n
== 0);
1899 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1900 return that edge. Otherwise return NULL.
1902 When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
1906 single_pred_edge_ignoring_loop_edges (basic_block bb
,
1907 bool ignore_not_executable
)
1913 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1915 /* A loop back edge can be identified by the destination of
1916 the edge dominating the source of the edge. */
1917 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1920 /* We can safely ignore edges that are not executable. */
1921 if (ignore_not_executable
1922 && (e
->flags
& EDGE_EXECUTABLE
) == 0)
1925 /* If we have already seen a non-loop edge, then we must have
1926 multiple incoming non-loop edges and thus we return NULL. */
1930 /* This is the first non-loop incoming edge we have found. Record