gcc/
[official-gcc.git] / gcc / cfganal.c
bloba99fd73a79e1fb536dc3bb6f5c6b9f0489c846a6
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
9 version.
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
14 for more details.
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. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "predict.h"
26 #include "tm.h"
27 #include "hard-reg-set.h"
28 #include "function.h"
29 #include "dominance.h"
30 #include "cfg.h"
31 #include "cfganal.h"
32 #include "basic-block.h"
33 #include "bitmap.h"
34 #include "sbitmap.h"
35 #include "timevar.h"
37 /* Store the data structures necessary for depth-first search. */
38 struct depth_first_search_dsS {
39 /* stack for backtracking during the algorithm */
40 basic_block *stack;
42 /* number of edges in the stack. That is, positions 0, ..., sp-1
43 have edges. */
44 unsigned int sp;
46 /* record of basic blocks already seen by depth-first search */
47 sbitmap visited_blocks;
49 typedef struct depth_first_search_dsS *depth_first_search_ds;
51 static void flow_dfs_compute_reverse_init (depth_first_search_ds);
52 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
53 basic_block);
54 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
55 basic_block);
56 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
58 /* Mark the back edges in DFS traversal.
59 Return nonzero if a loop (natural or otherwise) is present.
60 Inspired by Depth_First_Search_PP described in:
62 Advanced Compiler Design and Implementation
63 Steven Muchnick
64 Morgan Kaufmann, 1997
66 and heavily borrowed from pre_and_rev_post_order_compute. */
68 bool
69 mark_dfs_back_edges (void)
71 edge_iterator *stack;
72 int *pre;
73 int *post;
74 int sp;
75 int prenum = 1;
76 int postnum = 1;
77 sbitmap visited;
78 bool found = false;
80 /* Allocate the preorder and postorder number arrays. */
81 pre = XCNEWVEC (int, last_basic_block_for_fn (cfun));
82 post = XCNEWVEC (int, last_basic_block_for_fn (cfun));
84 /* Allocate stack for back-tracking up CFG. */
85 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
86 sp = 0;
88 /* Allocate bitmap to track nodes that have been visited. */
89 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
91 /* None of the nodes in the CFG have been visited yet. */
92 bitmap_clear (visited);
94 /* Push the first edge on to the stack. */
95 stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
97 while (sp)
99 edge_iterator ei;
100 basic_block src;
101 basic_block dest;
103 /* Look at the edge on the top of the stack. */
104 ei = stack[sp - 1];
105 src = ei_edge (ei)->src;
106 dest = ei_edge (ei)->dest;
107 ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
109 /* Check if the edge destination has been visited yet. */
110 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && ! bitmap_bit_p (visited,
111 dest->index))
113 /* Mark that we have visited the destination. */
114 bitmap_set_bit (visited, dest->index);
116 pre[dest->index] = prenum++;
117 if (EDGE_COUNT (dest->succs) > 0)
119 /* Since the DEST node has been visited for the first
120 time, check its successors. */
121 stack[sp++] = ei_start (dest->succs);
123 else
124 post[dest->index] = postnum++;
126 else
128 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
129 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
130 && pre[src->index] >= pre[dest->index]
131 && post[dest->index] == 0)
132 ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
134 if (ei_one_before_end_p (ei)
135 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
136 post[src->index] = postnum++;
138 if (!ei_one_before_end_p (ei))
139 ei_next (&stack[sp - 1]);
140 else
141 sp--;
145 free (pre);
146 free (post);
147 free (stack);
148 sbitmap_free (visited);
150 return found;
153 /* Find unreachable blocks. An unreachable block will have 0 in
154 the reachable bit in block->flags. A nonzero value indicates the
155 block is reachable. */
157 void
158 find_unreachable_blocks (void)
160 edge e;
161 edge_iterator ei;
162 basic_block *tos, *worklist, bb;
164 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
166 /* Clear all the reachability flags. */
168 FOR_EACH_BB_FN (bb, cfun)
169 bb->flags &= ~BB_REACHABLE;
171 /* Add our starting points to the worklist. Almost always there will
172 be only one. It isn't inconceivable that we might one day directly
173 support Fortran alternate entry points. */
175 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
177 *tos++ = e->dest;
179 /* Mark the block reachable. */
180 e->dest->flags |= BB_REACHABLE;
183 /* Iterate: find everything reachable from what we've already seen. */
185 while (tos != worklist)
187 basic_block b = *--tos;
189 FOR_EACH_EDGE (e, ei, b->succs)
191 basic_block dest = e->dest;
193 if (!(dest->flags & BB_REACHABLE))
195 *tos++ = dest;
196 dest->flags |= BB_REACHABLE;
201 free (worklist);
204 /* Functions to access an edge list with a vector representation.
205 Enough data is kept such that given an index number, the
206 pred and succ that edge represents can be determined, or
207 given a pred and a succ, its index number can be returned.
208 This allows algorithms which consume a lot of memory to
209 represent the normally full matrix of edge (pred,succ) with a
210 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
211 wasted space in the client code due to sparse flow graphs. */
213 /* This functions initializes the edge list. Basically the entire
214 flowgraph is processed, and all edges are assigned a number,
215 and the data structure is filled in. */
217 struct edge_list *
218 create_edge_list (void)
220 struct edge_list *elist;
221 edge e;
222 int num_edges;
223 basic_block bb;
224 edge_iterator ei;
226 /* Determine the number of edges in the flow graph by counting successor
227 edges on each basic block. */
228 num_edges = 0;
229 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
230 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
232 num_edges += EDGE_COUNT (bb->succs);
235 elist = XNEW (struct edge_list);
236 elist->num_edges = num_edges;
237 elist->index_to_edge = XNEWVEC (edge, num_edges);
239 num_edges = 0;
241 /* Follow successors of blocks, and register these edges. */
242 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
243 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
244 FOR_EACH_EDGE (e, ei, bb->succs)
245 elist->index_to_edge[num_edges++] = e;
247 return elist;
250 /* This function free's memory associated with an edge list. */
252 void
253 free_edge_list (struct edge_list *elist)
255 if (elist)
257 free (elist->index_to_edge);
258 free (elist);
262 /* This function provides debug output showing an edge list. */
264 DEBUG_FUNCTION void
265 print_edge_list (FILE *f, struct edge_list *elist)
267 int x;
269 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
270 n_basic_blocks_for_fn (cfun), elist->num_edges);
272 for (x = 0; x < elist->num_edges; x++)
274 fprintf (f, " %-4d - edge(", x);
275 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
276 fprintf (f, "entry,");
277 else
278 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
280 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR_FOR_FN (cfun))
281 fprintf (f, "exit)\n");
282 else
283 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
287 /* This function provides an internal consistency check of an edge list,
288 verifying that all edges are present, and that there are no
289 extra edges. */
291 DEBUG_FUNCTION void
292 verify_edge_list (FILE *f, struct edge_list *elist)
294 int pred, succ, index;
295 edge e;
296 basic_block bb, p, s;
297 edge_iterator ei;
299 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
300 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
302 FOR_EACH_EDGE (e, ei, bb->succs)
304 pred = e->src->index;
305 succ = e->dest->index;
306 index = EDGE_INDEX (elist, e->src, e->dest);
307 if (index == EDGE_INDEX_NO_EDGE)
309 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
310 continue;
313 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
314 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
315 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
316 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
317 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
318 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
322 /* We've verified that all the edges are in the list, now lets make sure
323 there are no spurious edges in the list. This is an expensive check! */
325 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR_FOR_FN (cfun),
326 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
327 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
329 int found_edge = 0;
331 FOR_EACH_EDGE (e, ei, p->succs)
332 if (e->dest == s)
334 found_edge = 1;
335 break;
338 FOR_EACH_EDGE (e, ei, s->preds)
339 if (e->src == p)
341 found_edge = 1;
342 break;
345 if (EDGE_INDEX (elist, p, s)
346 == EDGE_INDEX_NO_EDGE && found_edge != 0)
347 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
348 p->index, s->index);
349 if (EDGE_INDEX (elist, p, s)
350 != EDGE_INDEX_NO_EDGE && found_edge == 0)
351 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
352 p->index, s->index, EDGE_INDEX (elist, p, s));
357 /* Functions to compute control dependences. */
359 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
360 void
361 control_dependences::set_control_dependence_map_bit (basic_block bb,
362 int edge_index)
364 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
365 return;
366 gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
367 bitmap_set_bit (control_dependence_map[bb->index], edge_index);
370 /* Clear all control dependences for block BB. */
371 void
372 control_dependences::clear_control_dependence_bitmap (basic_block bb)
374 bitmap_clear (control_dependence_map[bb->index]);
377 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
378 This function is necessary because some blocks have negative numbers. */
380 static inline basic_block
381 find_pdom (basic_block block)
383 gcc_assert (block != ENTRY_BLOCK_PTR_FOR_FN (cfun));
385 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
386 return EXIT_BLOCK_PTR_FOR_FN (cfun);
387 else
389 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
390 if (! bb)
391 return EXIT_BLOCK_PTR_FOR_FN (cfun);
392 return bb;
396 /* Determine all blocks' control dependences on the given edge with edge_list
397 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
399 void
400 control_dependences::find_control_dependence (int edge_index)
402 basic_block current_block;
403 basic_block ending_block;
405 gcc_assert (INDEX_EDGE_PRED_BB (m_el, edge_index)
406 != EXIT_BLOCK_PTR_FOR_FN (cfun));
408 if (INDEX_EDGE_PRED_BB (m_el, edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
409 ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
410 else
411 ending_block = find_pdom (INDEX_EDGE_PRED_BB (m_el, edge_index));
413 for (current_block = INDEX_EDGE_SUCC_BB (m_el, edge_index);
414 current_block != ending_block
415 && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
416 current_block = find_pdom (current_block))
418 edge e = INDEX_EDGE (m_el, edge_index);
420 /* For abnormal edges, we don't make current_block control
421 dependent because instructions that throw are always necessary
422 anyway. */
423 if (e->flags & EDGE_ABNORMAL)
424 continue;
426 set_control_dependence_map_bit (current_block, edge_index);
430 /* Record all blocks' control dependences on all edges in the edge
431 list EL, ala Morgan, Section 3.6. */
433 control_dependences::control_dependences (struct edge_list *edges)
434 : m_el (edges)
436 timevar_push (TV_CONTROL_DEPENDENCES);
437 control_dependence_map.create (last_basic_block_for_fn (cfun));
438 for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
439 control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
440 for (int i = 0; i < NUM_EDGES (m_el); ++i)
441 find_control_dependence (i);
442 timevar_pop (TV_CONTROL_DEPENDENCES);
445 /* Free control dependences and the associated edge list. */
447 control_dependences::~control_dependences ()
449 for (unsigned i = 0; i < control_dependence_map.length (); ++i)
450 BITMAP_FREE (control_dependence_map[i]);
451 control_dependence_map.release ();
452 free_edge_list (m_el);
455 /* Returns the bitmap of edges the basic-block I is dependent on. */
457 bitmap
458 control_dependences::get_edges_dependent_on (int i)
460 return control_dependence_map[i];
463 /* Returns the edge with index I from the edge list. */
465 edge
466 control_dependences::get_edge (int i)
468 return INDEX_EDGE (m_el, i);
472 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
473 If no such edge exists, return NULL. */
475 edge
476 find_edge (basic_block pred, basic_block succ)
478 edge e;
479 edge_iterator ei;
481 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
483 FOR_EACH_EDGE (e, ei, pred->succs)
484 if (e->dest == succ)
485 return e;
487 else
489 FOR_EACH_EDGE (e, ei, succ->preds)
490 if (e->src == pred)
491 return e;
494 return NULL;
497 /* This routine will determine what, if any, edge there is between
498 a specified predecessor and successor. */
501 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
503 int x;
505 for (x = 0; x < NUM_EDGES (edge_list); x++)
506 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
507 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
508 return x;
510 return (EDGE_INDEX_NO_EDGE);
513 /* This routine will remove any fake predecessor edges for a basic block.
514 When the edge is removed, it is also removed from whatever successor
515 list it is in. */
517 static void
518 remove_fake_predecessors (basic_block bb)
520 edge e;
521 edge_iterator ei;
523 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
525 if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
526 remove_edge (e);
527 else
528 ei_next (&ei);
532 /* This routine will remove all fake edges from the flow graph. If
533 we remove all fake successors, it will automatically remove all
534 fake predecessors. */
536 void
537 remove_fake_edges (void)
539 basic_block bb;
541 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
542 remove_fake_predecessors (bb);
545 /* This routine will remove all fake edges to the EXIT_BLOCK. */
547 void
548 remove_fake_exit_edges (void)
550 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun));
554 /* This function will add a fake edge between any block which has no
555 successors, and the exit block. Some data flow equations require these
556 edges to exist. */
558 void
559 add_noreturn_fake_exit_edges (void)
561 basic_block bb;
563 FOR_EACH_BB_FN (bb, cfun)
564 if (EDGE_COUNT (bb->succs) == 0)
565 make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
568 /* This function adds a fake edge between any infinite loops to the
569 exit block. Some optimizations require a path from each node to
570 the exit node.
572 See also Morgan, Figure 3.10, pp. 82-83.
574 The current implementation is ugly, not attempting to minimize the
575 number of inserted fake edges. To reduce the number of fake edges
576 to insert, add fake edges from _innermost_ loops containing only
577 nodes not reachable from the exit block. */
579 void
580 connect_infinite_loops_to_exit (void)
582 basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
583 basic_block deadend_block;
584 struct depth_first_search_dsS dfs_ds;
586 /* Perform depth-first search in the reverse graph to find nodes
587 reachable from the exit block. */
588 flow_dfs_compute_reverse_init (&dfs_ds);
589 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR_FOR_FN (cfun));
591 /* Repeatedly add fake edges, updating the unreachable nodes. */
592 while (1)
594 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
595 unvisited_block);
596 if (!unvisited_block)
597 break;
599 deadend_block = dfs_find_deadend (unvisited_block);
600 make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
601 flow_dfs_compute_reverse_add_bb (&dfs_ds, deadend_block);
604 flow_dfs_compute_reverse_finish (&dfs_ds);
605 return;
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 edge_iterator *stack;
618 int sp;
619 int post_order_num = 0;
620 sbitmap visited;
621 int count;
623 if (include_entry_exit)
624 post_order[post_order_num++] = EXIT_BLOCK;
626 /* Allocate stack for back-tracking up CFG. */
627 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
628 sp = 0;
630 /* Allocate bitmap to track nodes that have been visited. */
631 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
633 /* None of the nodes in the CFG have been visited yet. */
634 bitmap_clear (visited);
636 /* Push the first edge on to the stack. */
637 stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
639 while (sp)
641 edge_iterator ei;
642 basic_block src;
643 basic_block dest;
645 /* Look at the edge on the top of the stack. */
646 ei = stack[sp - 1];
647 src = ei_edge (ei)->src;
648 dest = ei_edge (ei)->dest;
650 /* Check if the edge destination has been visited yet. */
651 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
652 && ! bitmap_bit_p (visited, dest->index))
654 /* Mark that we have visited the destination. */
655 bitmap_set_bit (visited, dest->index);
657 if (EDGE_COUNT (dest->succs) > 0)
658 /* Since the DEST node has been visited for the first
659 time, check its successors. */
660 stack[sp++] = ei_start (dest->succs);
661 else
662 post_order[post_order_num++] = dest->index;
664 else
666 if (ei_one_before_end_p (ei)
667 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
668 post_order[post_order_num++] = src->index;
670 if (!ei_one_before_end_p (ei))
671 ei_next (&stack[sp - 1]);
672 else
673 sp--;
677 if (include_entry_exit)
679 post_order[post_order_num++] = ENTRY_BLOCK;
680 count = post_order_num;
682 else
683 count = post_order_num + 2;
685 /* Delete the unreachable blocks if some were found and we are
686 supposed to do it. */
687 if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
689 basic_block b;
690 basic_block next_bb;
691 for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
692 != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
694 next_bb = b->next_bb;
696 if (!(bitmap_bit_p (visited, b->index)))
697 delete_basic_block (b);
700 tidy_fallthru_edges ();
703 free (stack);
704 sbitmap_free (visited);
705 return post_order_num;
709 /* Helper routine for inverted_post_order_compute
710 flow_dfs_compute_reverse_execute, and the reverse-CFG
711 deapth first search in dominance.c.
712 BB has to belong to a region of CFG
713 unreachable by inverted traversal from the exit.
714 i.e. there's no control flow path from ENTRY to EXIT
715 that contains this BB.
716 This can happen in two cases - if there's an infinite loop
717 or if there's a block that has no successor
718 (call to a function with no return).
719 Some RTL passes deal with this condition by
720 calling connect_infinite_loops_to_exit () and/or
721 add_noreturn_fake_exit_edges ().
722 However, those methods involve modifying the CFG itself
723 which may not be desirable.
724 Hence, we deal with the infinite loop/no return cases
725 by identifying a unique basic block that can reach all blocks
726 in such a region by inverted traversal.
727 This function returns a basic block that guarantees
728 that all blocks in the region are reachable
729 by starting an inverted traversal from the returned block. */
731 basic_block
732 dfs_find_deadend (basic_block bb)
734 bitmap visited = BITMAP_ALLOC (NULL);
736 for (;;)
738 if (EDGE_COUNT (bb->succs) == 0
739 || ! bitmap_set_bit (visited, bb->index))
741 BITMAP_FREE (visited);
742 return bb;
745 bb = EDGE_SUCC (bb, 0)->dest;
748 gcc_unreachable ();
752 /* Compute the reverse top sort order of the inverted CFG
753 i.e. starting from the exit block and following the edges backward
754 (from successors to predecessors).
755 This ordering can be used for forward dataflow problems among others.
757 This function assumes that all blocks in the CFG are reachable
758 from the ENTRY (but not necessarily from EXIT).
760 If there's an infinite loop,
761 a simple inverted traversal starting from the blocks
762 with no successors can't visit all blocks.
763 To solve this problem, we first do inverted traversal
764 starting from the blocks with no successor.
765 And if there's any block left that's not visited by the regular
766 inverted traversal from EXIT,
767 those blocks are in such problematic region.
768 Among those, we find one block that has
769 any visited predecessor (which is an entry into such a region),
770 and start looking for a "dead end" from that block
771 and do another inverted traversal from that block. */
774 inverted_post_order_compute (int *post_order)
776 basic_block bb;
777 edge_iterator *stack;
778 int sp;
779 int post_order_num = 0;
780 sbitmap visited;
782 /* Allocate stack for back-tracking up CFG. */
783 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
784 sp = 0;
786 /* Allocate bitmap to track nodes that have been visited. */
787 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
789 /* None of the nodes in the CFG have been visited yet. */
790 bitmap_clear (visited);
792 /* Put all blocks that have no successor into the initial work list. */
793 FOR_ALL_BB_FN (bb, cfun)
794 if (EDGE_COUNT (bb->succs) == 0)
796 /* Push the initial edge on to the stack. */
797 if (EDGE_COUNT (bb->preds) > 0)
799 stack[sp++] = ei_start (bb->preds);
800 bitmap_set_bit (visited, bb->index);
806 bool has_unvisited_bb = false;
808 /* The inverted traversal loop. */
809 while (sp)
811 edge_iterator ei;
812 basic_block pred;
814 /* Look at the edge on the top of the stack. */
815 ei = stack[sp - 1];
816 bb = ei_edge (ei)->dest;
817 pred = ei_edge (ei)->src;
819 /* Check if the predecessor has been visited yet. */
820 if (! bitmap_bit_p (visited, pred->index))
822 /* Mark that we have visited the destination. */
823 bitmap_set_bit (visited, pred->index);
825 if (EDGE_COUNT (pred->preds) > 0)
826 /* Since the predecessor node has been visited for the first
827 time, check its predecessors. */
828 stack[sp++] = ei_start (pred->preds);
829 else
830 post_order[post_order_num++] = pred->index;
832 else
834 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
835 && ei_one_before_end_p (ei))
836 post_order[post_order_num++] = bb->index;
838 if (!ei_one_before_end_p (ei))
839 ei_next (&stack[sp - 1]);
840 else
841 sp--;
845 /* Detect any infinite loop and activate the kludge.
846 Note that this doesn't check EXIT_BLOCK itself
847 since EXIT_BLOCK is always added after the outer do-while loop. */
848 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
849 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
850 if (!bitmap_bit_p (visited, bb->index))
852 has_unvisited_bb = true;
854 if (EDGE_COUNT (bb->preds) > 0)
856 edge_iterator ei;
857 edge e;
858 basic_block visited_pred = NULL;
860 /* Find an already visited predecessor. */
861 FOR_EACH_EDGE (e, ei, bb->preds)
863 if (bitmap_bit_p (visited, e->src->index))
864 visited_pred = e->src;
867 if (visited_pred)
869 basic_block be = dfs_find_deadend (bb);
870 gcc_assert (be != NULL);
871 bitmap_set_bit (visited, be->index);
872 stack[sp++] = ei_start (be->preds);
873 break;
878 if (has_unvisited_bb && sp == 0)
880 /* No blocks are reachable from EXIT at all.
881 Find a dead-end from the ENTRY, and restart the iteration. */
882 basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
883 gcc_assert (be != NULL);
884 bitmap_set_bit (visited, be->index);
885 stack[sp++] = ei_start (be->preds);
888 /* The only case the below while fires is
889 when there's an infinite loop. */
891 while (sp);
893 /* EXIT_BLOCK is always included. */
894 post_order[post_order_num++] = EXIT_BLOCK;
896 free (stack);
897 sbitmap_free (visited);
898 return post_order_num;
901 /* Compute the depth first search order of FN and store in the array
902 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
903 reverse completion number for each node. Returns the number of nodes
904 visited. A depth first search tries to get as far away from the starting
905 point as quickly as possible.
907 In case the function has unreachable blocks the number of nodes
908 visited does not include them.
910 pre_order is a really a preorder numbering of the graph.
911 rev_post_order is really a reverse postorder numbering of the graph. */
914 pre_and_rev_post_order_compute_fn (struct function *fn,
915 int *pre_order, int *rev_post_order,
916 bool include_entry_exit)
918 edge_iterator *stack;
919 int sp;
920 int pre_order_num = 0;
921 int rev_post_order_num = n_basic_blocks_for_fn (cfun) - 1;
922 sbitmap visited;
924 /* Allocate stack for back-tracking up CFG. */
925 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
926 sp = 0;
928 if (include_entry_exit)
930 if (pre_order)
931 pre_order[pre_order_num] = ENTRY_BLOCK;
932 pre_order_num++;
933 if (rev_post_order)
934 rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
936 else
937 rev_post_order_num -= NUM_FIXED_BLOCKS;
939 /* Allocate bitmap to track nodes that have been visited. */
940 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
942 /* None of the nodes in the CFG have been visited yet. */
943 bitmap_clear (visited);
945 /* Push the first edge on to the stack. */
946 stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs);
948 while (sp)
950 edge_iterator ei;
951 basic_block src;
952 basic_block dest;
954 /* Look at the edge on the top of the stack. */
955 ei = stack[sp - 1];
956 src = ei_edge (ei)->src;
957 dest = ei_edge (ei)->dest;
959 /* Check if the edge destination has been visited yet. */
960 if (dest != EXIT_BLOCK_PTR_FOR_FN (fn)
961 && ! bitmap_bit_p (visited, dest->index))
963 /* Mark that we have visited the destination. */
964 bitmap_set_bit (visited, dest->index);
966 if (pre_order)
967 pre_order[pre_order_num] = dest->index;
969 pre_order_num++;
971 if (EDGE_COUNT (dest->succs) > 0)
972 /* Since the DEST node has been visited for the first
973 time, check its successors. */
974 stack[sp++] = ei_start (dest->succs);
975 else if (rev_post_order)
976 /* There are no successors for the DEST node so assign
977 its reverse completion number. */
978 rev_post_order[rev_post_order_num--] = dest->index;
980 else
982 if (ei_one_before_end_p (ei)
983 && src != ENTRY_BLOCK_PTR_FOR_FN (fn)
984 && rev_post_order)
985 /* There are no more successors for the SRC node
986 so assign its reverse completion number. */
987 rev_post_order[rev_post_order_num--] = src->index;
989 if (!ei_one_before_end_p (ei))
990 ei_next (&stack[sp - 1]);
991 else
992 sp--;
996 free (stack);
997 sbitmap_free (visited);
999 if (include_entry_exit)
1001 if (pre_order)
1002 pre_order[pre_order_num] = EXIT_BLOCK;
1003 pre_order_num++;
1004 if (rev_post_order)
1005 rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
1008 return pre_order_num;
1011 /* Like pre_and_rev_post_order_compute_fn but operating on the
1012 current function and asserting that all nodes were visited. */
1015 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
1016 bool include_entry_exit)
1018 int pre_order_num
1019 = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
1020 include_entry_exit);
1021 if (include_entry_exit)
1022 /* The number of nodes visited should be the number of blocks. */
1023 gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun));
1024 else
1025 /* The number of nodes visited should be the number of blocks minus
1026 the entry and exit blocks which are not visited here. */
1027 gcc_assert (pre_order_num
1028 == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
1030 return pre_order_num;
1033 /* Compute the depth first search order on the _reverse_ graph and
1034 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1035 Returns the number of nodes visited.
1037 The computation is split into three pieces:
1039 flow_dfs_compute_reverse_init () creates the necessary data
1040 structures.
1042 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1043 structures. The block will start the search.
1045 flow_dfs_compute_reverse_execute () continues (or starts) the
1046 search using the block on the top of the stack, stopping when the
1047 stack is empty.
1049 flow_dfs_compute_reverse_finish () destroys the necessary data
1050 structures.
1052 Thus, the user will probably call ..._init(), call ..._add_bb() to
1053 add a beginning basic block to the stack, call ..._execute(),
1054 possibly add another bb to the stack and again call ..._execute(),
1055 ..., and finally call _finish(). */
1057 /* Initialize the data structures used for depth-first search on the
1058 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1059 added to the basic block stack. DATA is the current depth-first
1060 search context. If INITIALIZE_STACK is nonzero, there is an
1061 element on the stack. */
1063 static void
1064 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1066 /* Allocate stack for back-tracking up CFG. */
1067 data->stack = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1068 data->sp = 0;
1070 /* Allocate bitmap to track nodes that have been visited. */
1071 data->visited_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
1073 /* None of the nodes in the CFG have been visited yet. */
1074 bitmap_clear (data->visited_blocks);
1076 return;
1079 /* Add the specified basic block to the top of the dfs data
1080 structures. When the search continues, it will start at the
1081 block. */
1083 static void
1084 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1086 data->stack[data->sp++] = bb;
1087 bitmap_set_bit (data->visited_blocks, bb->index);
1090 /* Continue the depth-first search through the reverse graph starting with the
1091 block at the stack's top and ending when the stack is empty. Visited nodes
1092 are marked. Returns an unvisited basic block, or NULL if there is none
1093 available. */
1095 static basic_block
1096 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
1097 basic_block last_unvisited)
1099 basic_block bb;
1100 edge e;
1101 edge_iterator ei;
1103 while (data->sp > 0)
1105 bb = data->stack[--data->sp];
1107 /* Perform depth-first search on adjacent vertices. */
1108 FOR_EACH_EDGE (e, ei, bb->preds)
1109 if (!bitmap_bit_p (data->visited_blocks, e->src->index))
1110 flow_dfs_compute_reverse_add_bb (data, e->src);
1113 /* Determine if there are unvisited basic blocks. */
1114 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1115 if (!bitmap_bit_p (data->visited_blocks, bb->index))
1116 return bb;
1118 return NULL;
1121 /* Destroy the data structures needed for depth-first search on the
1122 reverse graph. */
1124 static void
1125 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1127 free (data->stack);
1128 sbitmap_free (data->visited_blocks);
1131 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1132 if REVERSE, go against direction of edges. Returns number of blocks
1133 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1135 dfs_enumerate_from (basic_block bb, int reverse,
1136 bool (*predicate) (const_basic_block, const void *),
1137 basic_block *rslt, int rslt_max, const void *data)
1139 basic_block *st, lbb;
1140 int sp = 0, tv = 0;
1141 unsigned size;
1143 /* A bitmap to keep track of visited blocks. Allocating it each time
1144 this function is called is not possible, since dfs_enumerate_from
1145 is often used on small (almost) disjoint parts of cfg (bodies of
1146 loops), and allocating a large sbitmap would lead to quadratic
1147 behavior. */
1148 static sbitmap visited;
1149 static unsigned v_size;
1151 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1152 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1153 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1155 /* Resize the VISITED sbitmap if necessary. */
1156 size = last_basic_block_for_fn (cfun);
1157 if (size < 10)
1158 size = 10;
1160 if (!visited)
1163 visited = sbitmap_alloc (size);
1164 bitmap_clear (visited);
1165 v_size = size;
1167 else if (v_size < size)
1169 /* Ensure that we increase the size of the sbitmap exponentially. */
1170 if (2 * v_size > size)
1171 size = 2 * v_size;
1173 visited = sbitmap_resize (visited, size, 0);
1174 v_size = size;
1177 st = XNEWVEC (basic_block, rslt_max);
1178 rslt[tv++] = st[sp++] = bb;
1179 MARK_VISITED (bb);
1180 while (sp)
1182 edge e;
1183 edge_iterator ei;
1184 lbb = st[--sp];
1185 if (reverse)
1187 FOR_EACH_EDGE (e, ei, lbb->preds)
1188 if (!VISITED_P (e->src) && predicate (e->src, data))
1190 gcc_assert (tv != rslt_max);
1191 rslt[tv++] = st[sp++] = e->src;
1192 MARK_VISITED (e->src);
1195 else
1197 FOR_EACH_EDGE (e, ei, lbb->succs)
1198 if (!VISITED_P (e->dest) && predicate (e->dest, data))
1200 gcc_assert (tv != rslt_max);
1201 rslt[tv++] = st[sp++] = e->dest;
1202 MARK_VISITED (e->dest);
1206 free (st);
1207 for (sp = 0; sp < tv; sp++)
1208 UNMARK_VISITED (rslt[sp]);
1209 return tv;
1210 #undef MARK_VISITED
1211 #undef UNMARK_VISITED
1212 #undef VISITED_P
1216 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1218 This algorithm can be found in Timothy Harvey's PhD thesis, at
1219 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1220 dominance algorithms.
1222 First, we identify each join point, j (any node with more than one
1223 incoming edge is a join point).
1225 We then examine each predecessor, p, of j and walk up the dominator tree
1226 starting at p.
1228 We stop the walk when we reach j's immediate dominator - j is in the
1229 dominance frontier of each of the nodes in the walk, except for j's
1230 immediate dominator. Intuitively, all of the rest of j's dominators are
1231 shared by j's predecessors as well.
1232 Since they dominate j, they will not have j in their dominance frontiers.
1234 The number of nodes touched by this algorithm is equal to the size
1235 of the dominance frontiers, no more, no less.
1239 static void
1240 compute_dominance_frontiers_1 (bitmap_head *frontiers)
1242 edge p;
1243 edge_iterator ei;
1244 basic_block b;
1245 FOR_EACH_BB_FN (b, cfun)
1247 if (EDGE_COUNT (b->preds) >= 2)
1249 FOR_EACH_EDGE (p, ei, b->preds)
1251 basic_block runner = p->src;
1252 basic_block domsb;
1253 if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1254 continue;
1256 domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1257 while (runner != domsb)
1259 if (!bitmap_set_bit (&frontiers[runner->index],
1260 b->index))
1261 break;
1262 runner = get_immediate_dominator (CDI_DOMINATORS,
1263 runner);
1271 void
1272 compute_dominance_frontiers (bitmap_head *frontiers)
1274 timevar_push (TV_DOM_FRONTIERS);
1276 compute_dominance_frontiers_1 (frontiers);
1278 timevar_pop (TV_DOM_FRONTIERS);
1281 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1282 return a bitmap with all the blocks in the iterated dominance
1283 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1284 frontier information as returned by compute_dominance_frontiers.
1286 The resulting set of blocks are the potential sites where PHI nodes
1287 are needed. The caller is responsible for freeing the memory
1288 allocated for the return value. */
1290 bitmap
1291 compute_idf (bitmap def_blocks, bitmap_head *dfs)
1293 bitmap_iterator bi;
1294 unsigned bb_index, i;
1295 bitmap phi_insertion_points;
1297 /* Each block can appear at most twice on the work-stack. */
1298 auto_vec<int> work_stack (2 * n_basic_blocks_for_fn (cfun));
1299 phi_insertion_points = BITMAP_ALLOC (NULL);
1301 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1302 vec::quick_push here for speed. This is safe because we know that
1303 the number of definition blocks is no greater than the number of
1304 basic blocks, which is the initial capacity of WORK_STACK. */
1305 EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
1306 work_stack.quick_push (bb_index);
1308 /* Pop a block off the worklist, add every block that appears in
1309 the original block's DF that we have not already processed to
1310 the worklist. Iterate until the worklist is empty. Blocks
1311 which are added to the worklist are potential sites for
1312 PHI nodes. */
1313 while (work_stack.length () > 0)
1315 bb_index = work_stack.pop ();
1317 /* Since the registration of NEW -> OLD name mappings is done
1318 separately from the call to update_ssa, when updating the SSA
1319 form, the basic blocks where new and/or old names are defined
1320 may have disappeared by CFG cleanup calls. In this case,
1321 we may pull a non-existing block from the work stack. */
1322 gcc_checking_assert (bb_index
1323 < (unsigned) last_basic_block_for_fn (cfun));
1325 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
1326 0, i, bi)
1328 work_stack.quick_push (i);
1329 bitmap_set_bit (phi_insertion_points, i);
1333 return phi_insertion_points;
1336 /* Intersection and union of preds/succs for sbitmap based data flow
1337 solvers. All four functions defined below take the same arguments:
1338 B is the basic block to perform the operation for. DST is the
1339 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1340 last_basic_block so that it can be indexed with basic block indices.
1341 DST may be (but does not have to be) SRC[B->index]. */
1343 /* Set the bitmap DST to the intersection of SRC of successors of
1344 basic block B. */
1346 void
1347 bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1349 unsigned int set_size = dst->size;
1350 edge e;
1351 unsigned ix;
1353 gcc_assert (!dst->popcount);
1355 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1357 e = EDGE_SUCC (b, ix);
1358 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1359 continue;
1361 bitmap_copy (dst, src[e->dest->index]);
1362 break;
1365 if (e == 0)
1366 bitmap_ones (dst);
1367 else
1368 for (++ix; ix < EDGE_COUNT (b->succs); ix++)
1370 unsigned int i;
1371 SBITMAP_ELT_TYPE *p, *r;
1373 e = EDGE_SUCC (b, ix);
1374 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1375 continue;
1377 p = src[e->dest->index]->elms;
1378 r = dst->elms;
1379 for (i = 0; i < set_size; i++)
1380 *r++ &= *p++;
1384 /* Set the bitmap DST to the intersection of SRC of predecessors of
1385 basic block B. */
1387 void
1388 bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1390 unsigned int set_size = dst->size;
1391 edge e;
1392 unsigned ix;
1394 gcc_assert (!dst->popcount);
1396 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1398 e = EDGE_PRED (b, ix);
1399 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1400 continue;
1402 bitmap_copy (dst, src[e->src->index]);
1403 break;
1406 if (e == 0)
1407 bitmap_ones (dst);
1408 else
1409 for (++ix; ix < EDGE_COUNT (b->preds); ix++)
1411 unsigned int i;
1412 SBITMAP_ELT_TYPE *p, *r;
1414 e = EDGE_PRED (b, ix);
1415 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1416 continue;
1418 p = src[e->src->index]->elms;
1419 r = dst->elms;
1420 for (i = 0; i < set_size; i++)
1421 *r++ &= *p++;
1425 /* Set the bitmap DST to the union of SRC of successors of
1426 basic block B. */
1428 void
1429 bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1431 unsigned int set_size = dst->size;
1432 edge e;
1433 unsigned ix;
1435 gcc_assert (!dst->popcount);
1437 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1439 e = EDGE_SUCC (b, ix);
1440 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1441 continue;
1443 bitmap_copy (dst, src[e->dest->index]);
1444 break;
1447 if (ix == EDGE_COUNT (b->succs))
1448 bitmap_clear (dst);
1449 else
1450 for (ix++; ix < EDGE_COUNT (b->succs); ix++)
1452 unsigned int i;
1453 SBITMAP_ELT_TYPE *p, *r;
1455 e = EDGE_SUCC (b, ix);
1456 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1457 continue;
1459 p = src[e->dest->index]->elms;
1460 r = dst->elms;
1461 for (i = 0; i < set_size; i++)
1462 *r++ |= *p++;
1466 /* Set the bitmap DST to the union of SRC of predecessors of
1467 basic block B. */
1469 void
1470 bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1472 unsigned int set_size = dst->size;
1473 edge e;
1474 unsigned ix;
1476 gcc_assert (!dst->popcount);
1478 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1480 e = EDGE_PRED (b, ix);
1481 if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun))
1482 continue;
1484 bitmap_copy (dst, src[e->src->index]);
1485 break;
1488 if (ix == EDGE_COUNT (b->preds))
1489 bitmap_clear (dst);
1490 else
1491 for (ix++; ix < EDGE_COUNT (b->preds); ix++)
1493 unsigned int i;
1494 SBITMAP_ELT_TYPE *p, *r;
1496 e = EDGE_PRED (b, ix);
1497 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1498 continue;
1500 p = src[e->src->index]->elms;
1501 r = dst->elms;
1502 for (i = 0; i < set_size; i++)
1503 *r++ |= *p++;
1507 /* Returns the list of basic blocks in the function in an order that guarantees
1508 that if a block X has just a single predecessor Y, then Y is after X in the
1509 ordering. */
1511 basic_block *
1512 single_pred_before_succ_order (void)
1514 basic_block x, y;
1515 basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1516 unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1517 unsigned np, i;
1518 sbitmap visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
1520 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1521 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1523 bitmap_clear (visited);
1525 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1526 FOR_EACH_BB_FN (x, cfun)
1528 if (VISITED_P (x))
1529 continue;
1531 /* Walk the predecessors of x as long as they have precisely one
1532 predecessor and add them to the list, so that they get stored
1533 after x. */
1534 for (y = x, np = 1;
1535 single_pred_p (y) && !VISITED_P (single_pred (y));
1536 y = single_pred (y))
1537 np++;
1538 for (y = x, i = n - np;
1539 single_pred_p (y) && !VISITED_P (single_pred (y));
1540 y = single_pred (y), i++)
1542 order[i] = y;
1543 MARK_VISITED (y);
1545 order[i] = y;
1546 MARK_VISITED (y);
1548 gcc_assert (i == n - 1);
1549 n -= np;
1552 sbitmap_free (visited);
1553 gcc_assert (n == 0);
1554 return order;
1556 #undef MARK_VISITED
1557 #undef VISITED_P