Daily bump.
[official-gcc.git] / gcc / cfganal.c
blob394d986c945a3d02ce8a8769859ce2ccba2c8fcb
1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987-2017 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 "backend.h"
26 #include "cfghooks.h"
27 #include "timevar.h"
28 #include "cfganal.h"
29 #include "cfgloop.h"
31 namespace {
32 /* Store the data structures necessary for depth-first search. */
33 class depth_first_search
35 public:
36 depth_first_search ();
38 basic_block execute (basic_block);
39 void add_bb (basic_block);
41 private:
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
55 Steven Muchnick
56 Morgan Kaufmann, 1997
58 and heavily borrowed from pre_and_rev_post_order_compute. */
60 bool
61 mark_dfs_back_edges (void)
63 int *pre;
64 int *post;
65 int prenum = 1;
66 int postnum = 1;
67 bool found = false;
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 ())
87 basic_block src;
88 basic_block dest;
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,
98 dest->index))
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));
110 else
111 post[dest->index] = postnum++;
113 else
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 ());
127 else
128 stack.pop ();
132 free (pre);
133 free (post);
135 return found;
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. */
142 void
143 find_unreachable_blocks (void)
145 edge e;
146 edge_iterator ei;
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)
162 *tos++ = e->dest;
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))
180 *tos++ = dest;
181 dest->flags |= BB_REACHABLE;
186 free (worklist);
189 /* Verify that there are no unreachable blocks in the current function. */
191 void
192 verify_no_unreachable_blocks (void)
194 find_unreachable_blocks ();
196 basic_block bb;
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. */
215 struct edge_list *
216 create_edge_list (void)
218 struct edge_list *elist;
219 edge e;
220 int num_edges;
221 basic_block bb;
222 edge_iterator ei;
224 /* Determine the number of edges in the flow graph by counting successor
225 edges on each basic block. */
226 num_edges = 0;
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);
237 num_edges = 0;
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;
245 return elist;
248 /* This function free's memory associated with an edge list. */
250 void
251 free_edge_list (struct edge_list *elist)
253 if (elist)
255 free (elist->index_to_edge);
256 free (elist);
260 /* This function provides debug output showing an edge list. */
262 DEBUG_FUNCTION void
263 print_edge_list (FILE *f, struct edge_list *elist)
265 int x;
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,");
275 else
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");
280 else
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
287 extra edges. */
289 DEBUG_FUNCTION void
290 verify_edge_list (FILE *f, struct edge_list *elist)
292 int pred, succ, index;
293 edge e;
294 basic_block bb, p, s;
295 edge_iterator ei;
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);
308 continue;
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)
327 int found_edge = 0;
329 FOR_EACH_EDGE (e, ei, p->succs)
330 if (e->dest == s)
332 found_edge = 1;
333 break;
336 FOR_EACH_EDGE (e, ei, s->preds)
337 if (e->src == p)
339 found_edge = 1;
340 break;
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",
346 p->index, s->index);
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. */
358 void
359 control_dependences::set_control_dependence_map_bit (basic_block bb,
360 int edge_index)
362 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
363 return;
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. */
369 void
370 control_dependences::clear_control_dependence_bitmap (basic_block bb)
372 bitmap_clear (control_dependence_map[bb->index]);
375 /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
376 This function is necessary because some blocks have negative numbers. */
378 static inline basic_block
379 find_pdom (basic_block block)
381 gcc_assert (block != ENTRY_BLOCK_PTR_FOR_FN (cfun));
383 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
384 return EXIT_BLOCK_PTR_FOR_FN (cfun);
385 else
387 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
388 if (! bb)
389 return EXIT_BLOCK_PTR_FOR_FN (cfun);
390 return bb;
394 /* Determine all blocks' control dependences on the given edge with edge_list
395 EL index EDGE_INDEX, ala Morgan, Section 3.6. */
397 void
398 control_dependences::find_control_dependence (int edge_index)
400 basic_block current_block;
401 basic_block ending_block;
403 gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun));
405 /* For abnormal edges, we don't make current_block control
406 dependent because instructions that throw are always necessary
407 anyway. */
408 edge e = find_edge (get_edge_src (edge_index), get_edge_dest (edge_index));
409 if (e->flags & EDGE_ABNORMAL)
410 return;
412 if (get_edge_src (edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
413 ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
414 else
415 ending_block = find_pdom (get_edge_src (edge_index));
417 for (current_block = get_edge_dest (edge_index);
418 current_block != ending_block
419 && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
420 current_block = find_pdom (current_block))
421 set_control_dependence_map_bit (current_block, edge_index);
424 /* Record all blocks' control dependences on all edges in the edge
425 list EL, ala Morgan, Section 3.6. */
427 control_dependences::control_dependences ()
429 timevar_push (TV_CONTROL_DEPENDENCES);
431 /* Initialize the edge list. */
432 int num_edges = 0;
433 basic_block bb;
434 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
435 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
436 num_edges += EDGE_COUNT (bb->succs);
437 m_el.create (num_edges);
438 edge e;
439 edge_iterator ei;
440 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
441 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
442 FOR_EACH_EDGE (e, ei, bb->succs)
443 m_el.quick_push (std::make_pair (e->src->index, e->dest->index));
445 control_dependence_map.create (last_basic_block_for_fn (cfun));
446 for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
447 control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
448 for (int i = 0; i < num_edges; ++i)
449 find_control_dependence (i);
451 timevar_pop (TV_CONTROL_DEPENDENCES);
454 /* Free control dependences and the associated edge list. */
456 control_dependences::~control_dependences ()
458 for (unsigned i = 0; i < control_dependence_map.length (); ++i)
459 BITMAP_FREE (control_dependence_map[i]);
460 control_dependence_map.release ();
461 m_el.release ();
464 /* Returns the bitmap of edges the basic-block I is dependent on. */
466 bitmap
467 control_dependences::get_edges_dependent_on (int i)
469 return control_dependence_map[i];
472 /* Returns the edge source with index I from the edge list. */
474 basic_block
475 control_dependences::get_edge_src (int i)
477 return BASIC_BLOCK_FOR_FN (cfun, m_el[i].first);
480 /* Returns the edge destination with index I from the edge list. */
482 basic_block
483 control_dependences::get_edge_dest (int i)
485 return BASIC_BLOCK_FOR_FN (cfun, m_el[i].second);
489 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
490 If no such edge exists, return NULL. */
492 edge
493 find_edge (basic_block pred, basic_block succ)
495 edge e;
496 edge_iterator ei;
498 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
500 FOR_EACH_EDGE (e, ei, pred->succs)
501 if (e->dest == succ)
502 return e;
504 else
506 FOR_EACH_EDGE (e, ei, succ->preds)
507 if (e->src == pred)
508 return e;
511 return NULL;
514 /* This routine will determine what, if any, edge there is between
515 a specified predecessor and successor. */
518 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
520 int x;
522 for (x = 0; x < NUM_EDGES (edge_list); x++)
523 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
524 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
525 return x;
527 return (EDGE_INDEX_NO_EDGE);
530 /* This routine will remove any fake predecessor edges for a basic block.
531 When the edge is removed, it is also removed from whatever successor
532 list it is in. */
534 static void
535 remove_fake_predecessors (basic_block bb)
537 edge e;
538 edge_iterator ei;
540 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
542 if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
543 remove_edge (e);
544 else
545 ei_next (&ei);
549 /* This routine will remove all fake edges from the flow graph. If
550 we remove all fake successors, it will automatically remove all
551 fake predecessors. */
553 void
554 remove_fake_edges (void)
556 basic_block bb;
558 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
559 remove_fake_predecessors (bb);
562 /* This routine will remove all fake edges to the EXIT_BLOCK. */
564 void
565 remove_fake_exit_edges (void)
567 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun));
571 /* This function will add a fake edge between any block which has no
572 successors, and the exit block. Some data flow equations require these
573 edges to exist. */
575 void
576 add_noreturn_fake_exit_edges (void)
578 basic_block bb;
580 FOR_EACH_BB_FN (bb, cfun)
581 if (EDGE_COUNT (bb->succs) == 0)
582 make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
585 /* This function adds a fake edge between any infinite loops to the
586 exit block. Some optimizations require a path from each node to
587 the exit node.
589 See also Morgan, Figure 3.10, pp. 82-83.
591 The current implementation is ugly, not attempting to minimize the
592 number of inserted fake edges. To reduce the number of fake edges
593 to insert, add fake edges from _innermost_ loops containing only
594 nodes not reachable from the exit block. */
596 void
597 connect_infinite_loops_to_exit (void)
599 /* Perform depth-first search in the reverse graph to find nodes
600 reachable from the exit block. */
601 depth_first_search dfs;
602 dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
604 /* Repeatedly add fake edges, updating the unreachable nodes. */
605 basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
606 while (1)
608 unvisited_block = dfs.execute (unvisited_block);
609 if (!unvisited_block)
610 break;
612 basic_block deadend_block = dfs_find_deadend (unvisited_block);
613 edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun),
614 EDGE_FAKE);
615 e->count = profile_count::zero ();
616 e->probability = profile_probability::never ();
617 dfs.add_bb (deadend_block);
621 /* Compute reverse top sort order. This is computing a post order
622 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
623 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
624 true, unreachable blocks are deleted. */
627 post_order_compute (int *post_order, bool include_entry_exit,
628 bool delete_unreachable)
630 int post_order_num = 0;
631 int count;
633 if (include_entry_exit)
634 post_order[post_order_num++] = EXIT_BLOCK;
636 /* Allocate stack for back-tracking up CFG. */
637 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
639 /* Allocate bitmap to track nodes that have been visited. */
640 auto_sbitmap visited (last_basic_block_for_fn (cfun));
642 /* None of the nodes in the CFG have been visited yet. */
643 bitmap_clear (visited);
645 /* Push the first edge on to the stack. */
646 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
648 while (!stack.is_empty ())
650 basic_block src;
651 basic_block dest;
653 /* Look at the edge on the top of the stack. */
654 edge_iterator ei = stack.last ();
655 src = ei_edge (ei)->src;
656 dest = ei_edge (ei)->dest;
658 /* Check if the edge destination has been visited yet. */
659 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
660 && ! bitmap_bit_p (visited, dest->index))
662 /* Mark that we have visited the destination. */
663 bitmap_set_bit (visited, dest->index);
665 if (EDGE_COUNT (dest->succs) > 0)
666 /* Since the DEST node has been visited for the first
667 time, check its successors. */
668 stack.quick_push (ei_start (dest->succs));
669 else
670 post_order[post_order_num++] = dest->index;
672 else
674 if (ei_one_before_end_p (ei)
675 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
676 post_order[post_order_num++] = src->index;
678 if (!ei_one_before_end_p (ei))
679 ei_next (&stack.last ());
680 else
681 stack.pop ();
685 if (include_entry_exit)
687 post_order[post_order_num++] = ENTRY_BLOCK;
688 count = post_order_num;
690 else
691 count = post_order_num + 2;
693 /* Delete the unreachable blocks if some were found and we are
694 supposed to do it. */
695 if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
697 basic_block b;
698 basic_block next_bb;
699 for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
700 != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
702 next_bb = b->next_bb;
704 if (!(bitmap_bit_p (visited, b->index)))
705 delete_basic_block (b);
708 tidy_fallthru_edges ();
711 return post_order_num;
715 /* Helper routine for inverted_post_order_compute
716 flow_dfs_compute_reverse_execute, and the reverse-CFG
717 deapth first search in dominance.c.
718 BB has to belong to a region of CFG
719 unreachable by inverted traversal from the exit.
720 i.e. there's no control flow path from ENTRY to EXIT
721 that contains this BB.
722 This can happen in two cases - if there's an infinite loop
723 or if there's a block that has no successor
724 (call to a function with no return).
725 Some RTL passes deal with this condition by
726 calling connect_infinite_loops_to_exit () and/or
727 add_noreturn_fake_exit_edges ().
728 However, those methods involve modifying the CFG itself
729 which may not be desirable.
730 Hence, we deal with the infinite loop/no return cases
731 by identifying a unique basic block that can reach all blocks
732 in such a region by inverted traversal.
733 This function returns a basic block that guarantees
734 that all blocks in the region are reachable
735 by starting an inverted traversal from the returned block. */
737 basic_block
738 dfs_find_deadend (basic_block bb)
740 auto_bitmap visited;
741 basic_block next = bb;
743 for (;;)
745 if (EDGE_COUNT (next->succs) == 0)
746 return next;
748 if (! bitmap_set_bit (visited, next->index))
749 return bb;
751 bb = next;
752 /* If we are in an analyzed cycle make sure to try exiting it.
753 Note this is a heuristic only and expected to work when loop
754 fixup is needed as well. */
755 if (! bb->loop_father
756 || ! loop_outer (bb->loop_father))
757 next = EDGE_SUCC (bb, 0)->dest;
758 else
760 edge_iterator ei;
761 edge e;
762 FOR_EACH_EDGE (e, ei, bb->succs)
763 if (loop_exit_edge_p (bb->loop_father, e))
764 break;
765 next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
769 gcc_unreachable ();
773 /* Compute the reverse top sort order of the inverted CFG
774 i.e. starting from the exit block and following the edges backward
775 (from successors to predecessors).
776 This ordering can be used for forward dataflow problems among others.
778 Optionally if START_POINTS is specified, start from exit block and all
779 basic blocks in START_POINTS. This is used by CD-DCE.
781 This function assumes that all blocks in the CFG are reachable
782 from the ENTRY (but not necessarily from EXIT).
784 If there's an infinite loop,
785 a simple inverted traversal starting from the blocks
786 with no successors can't visit all blocks.
787 To solve this problem, we first do inverted traversal
788 starting from the blocks with no successor.
789 And if there's any block left that's not visited by the regular
790 inverted traversal from EXIT,
791 those blocks are in such problematic region.
792 Among those, we find one block that has
793 any visited predecessor (which is an entry into such a region),
794 and start looking for a "dead end" from that block
795 and do another inverted traversal from that block. */
797 void
798 inverted_post_order_compute (vec<int> *post_order,
799 sbitmap *start_points)
801 basic_block bb;
802 post_order->reserve_exact (n_basic_blocks_for_fn (cfun));
804 if (flag_checking)
805 verify_no_unreachable_blocks ();
807 /* Allocate stack for back-tracking up CFG. */
808 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
810 /* Allocate bitmap to track nodes that have been visited. */
811 auto_sbitmap visited (last_basic_block_for_fn (cfun));
813 /* None of the nodes in the CFG have been visited yet. */
814 bitmap_clear (visited);
816 if (start_points)
818 FOR_ALL_BB_FN (bb, cfun)
819 if (bitmap_bit_p (*start_points, bb->index)
820 && EDGE_COUNT (bb->preds) > 0)
822 stack.quick_push (ei_start (bb->preds));
823 bitmap_set_bit (visited, bb->index);
825 if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
827 stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds));
828 bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
831 else
832 /* Put all blocks that have no successor into the initial work list. */
833 FOR_ALL_BB_FN (bb, cfun)
834 if (EDGE_COUNT (bb->succs) == 0)
836 /* Push the initial edge on to the stack. */
837 if (EDGE_COUNT (bb->preds) > 0)
839 stack.quick_push (ei_start (bb->preds));
840 bitmap_set_bit (visited, bb->index);
846 bool has_unvisited_bb = false;
848 /* The inverted traversal loop. */
849 while (!stack.is_empty ())
851 edge_iterator ei;
852 basic_block pred;
854 /* Look at the edge on the top of the stack. */
855 ei = stack.last ();
856 bb = ei_edge (ei)->dest;
857 pred = ei_edge (ei)->src;
859 /* Check if the predecessor has been visited yet. */
860 if (! bitmap_bit_p (visited, pred->index))
862 /* Mark that we have visited the destination. */
863 bitmap_set_bit (visited, pred->index);
865 if (EDGE_COUNT (pred->preds) > 0)
866 /* Since the predecessor node has been visited for the first
867 time, check its predecessors. */
868 stack.quick_push (ei_start (pred->preds));
869 else
870 post_order->quick_push (pred->index);
872 else
874 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
875 && ei_one_before_end_p (ei))
876 post_order->quick_push (bb->index);
878 if (!ei_one_before_end_p (ei))
879 ei_next (&stack.last ());
880 else
881 stack.pop ();
885 /* Detect any infinite loop and activate the kludge.
886 Note that this doesn't check EXIT_BLOCK itself
887 since EXIT_BLOCK is always added after the outer do-while loop. */
888 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
889 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
890 if (!bitmap_bit_p (visited, bb->index))
892 has_unvisited_bb = true;
894 if (EDGE_COUNT (bb->preds) > 0)
896 edge_iterator ei;
897 edge e;
898 basic_block visited_pred = NULL;
900 /* Find an already visited predecessor. */
901 FOR_EACH_EDGE (e, ei, bb->preds)
903 if (bitmap_bit_p (visited, e->src->index))
904 visited_pred = e->src;
907 if (visited_pred)
909 basic_block be = dfs_find_deadend (bb);
910 gcc_assert (be != NULL);
911 bitmap_set_bit (visited, be->index);
912 stack.quick_push (ei_start (be->preds));
913 break;
918 if (has_unvisited_bb && stack.is_empty ())
920 /* No blocks are reachable from EXIT at all.
921 Find a dead-end from the ENTRY, and restart the iteration. */
922 basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
923 gcc_assert (be != NULL);
924 bitmap_set_bit (visited, be->index);
925 stack.quick_push (ei_start (be->preds));
928 /* The only case the below while fires is
929 when there's an infinite loop. */
931 while (!stack.is_empty ());
933 /* EXIT_BLOCK is always included. */
934 post_order->quick_push (EXIT_BLOCK);
937 /* Compute the depth first search order of FN and store in the array
938 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
939 reverse completion number for each node. Returns the number of nodes
940 visited. A depth first search tries to get as far away from the starting
941 point as quickly as possible.
943 In case the function has unreachable blocks the number of nodes
944 visited does not include them.
946 pre_order is a really a preorder numbering of the graph.
947 rev_post_order is really a reverse postorder numbering of the graph. */
950 pre_and_rev_post_order_compute_fn (struct function *fn,
951 int *pre_order, int *rev_post_order,
952 bool include_entry_exit)
954 int pre_order_num = 0;
955 int rev_post_order_num = n_basic_blocks_for_fn (cfun) - 1;
957 /* Allocate stack for back-tracking up CFG. */
958 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
960 if (include_entry_exit)
962 if (pre_order)
963 pre_order[pre_order_num] = ENTRY_BLOCK;
964 pre_order_num++;
965 if (rev_post_order)
966 rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
968 else
969 rev_post_order_num -= NUM_FIXED_BLOCKS;
971 /* Allocate bitmap to track nodes that have been visited. */
972 auto_sbitmap visited (last_basic_block_for_fn (cfun));
974 /* None of the nodes in the CFG have been visited yet. */
975 bitmap_clear (visited);
977 /* Push the first edge on to the stack. */
978 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs));
980 while (!stack.is_empty ())
982 basic_block src;
983 basic_block dest;
985 /* Look at the edge on the top of the stack. */
986 edge_iterator ei = stack.last ();
987 src = ei_edge (ei)->src;
988 dest = ei_edge (ei)->dest;
990 /* Check if the edge destination has been visited yet. */
991 if (dest != EXIT_BLOCK_PTR_FOR_FN (fn)
992 && ! bitmap_bit_p (visited, dest->index))
994 /* Mark that we have visited the destination. */
995 bitmap_set_bit (visited, dest->index);
997 if (pre_order)
998 pre_order[pre_order_num] = dest->index;
1000 pre_order_num++;
1002 if (EDGE_COUNT (dest->succs) > 0)
1003 /* Since the DEST node has been visited for the first
1004 time, check its successors. */
1005 stack.quick_push (ei_start (dest->succs));
1006 else if (rev_post_order)
1007 /* There are no successors for the DEST node so assign
1008 its reverse completion number. */
1009 rev_post_order[rev_post_order_num--] = dest->index;
1011 else
1013 if (ei_one_before_end_p (ei)
1014 && src != ENTRY_BLOCK_PTR_FOR_FN (fn)
1015 && rev_post_order)
1016 /* There are no more successors for the SRC node
1017 so assign its reverse completion number. */
1018 rev_post_order[rev_post_order_num--] = src->index;
1020 if (!ei_one_before_end_p (ei))
1021 ei_next (&stack.last ());
1022 else
1023 stack.pop ();
1027 if (include_entry_exit)
1029 if (pre_order)
1030 pre_order[pre_order_num] = EXIT_BLOCK;
1031 pre_order_num++;
1032 if (rev_post_order)
1033 rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
1036 return pre_order_num;
1039 /* Like pre_and_rev_post_order_compute_fn but operating on the
1040 current function and asserting that all nodes were visited. */
1043 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
1044 bool include_entry_exit)
1046 int pre_order_num
1047 = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
1048 include_entry_exit);
1049 if (include_entry_exit)
1050 /* The number of nodes visited should be the number of blocks. */
1051 gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun));
1052 else
1053 /* The number of nodes visited should be the number of blocks minus
1054 the entry and exit blocks which are not visited here. */
1055 gcc_assert (pre_order_num
1056 == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
1058 return pre_order_num;
1061 /* Compute the depth first search order on the _reverse_ graph and
1062 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1063 Returns the number of nodes visited.
1065 The computation is split into three pieces:
1067 flow_dfs_compute_reverse_init () creates the necessary data
1068 structures.
1070 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1071 structures. The block will start the search.
1073 flow_dfs_compute_reverse_execute () continues (or starts) the
1074 search using the block on the top of the stack, stopping when the
1075 stack is empty.
1077 flow_dfs_compute_reverse_finish () destroys the necessary data
1078 structures.
1080 Thus, the user will probably call ..._init(), call ..._add_bb() to
1081 add a beginning basic block to the stack, call ..._execute(),
1082 possibly add another bb to the stack and again call ..._execute(),
1083 ..., and finally call _finish(). */
1085 /* Initialize the data structures used for depth-first search on the
1086 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1087 added to the basic block stack. DATA is the current depth-first
1088 search context. If INITIALIZE_STACK is nonzero, there is an
1089 element on the stack. */
1091 depth_first_search::depth_first_search () :
1092 m_stack (n_basic_blocks_for_fn (cfun)),
1093 m_visited_blocks (last_basic_block_for_fn (cfun))
1095 bitmap_clear (m_visited_blocks);
1098 /* Add the specified basic block to the top of the dfs data
1099 structures. When the search continues, it will start at the
1100 block. */
1102 void
1103 depth_first_search::add_bb (basic_block bb)
1105 m_stack.quick_push (bb);
1106 bitmap_set_bit (m_visited_blocks, bb->index);
1109 /* Continue the depth-first search through the reverse graph starting with the
1110 block at the stack's top and ending when the stack is empty. Visited nodes
1111 are marked. Returns an unvisited basic block, or NULL if there is none
1112 available. */
1114 basic_block
1115 depth_first_search::execute (basic_block last_unvisited)
1117 basic_block bb;
1118 edge e;
1119 edge_iterator ei;
1121 while (!m_stack.is_empty ())
1123 bb = m_stack.pop ();
1125 /* Perform depth-first search on adjacent vertices. */
1126 FOR_EACH_EDGE (e, ei, bb->preds)
1127 if (!bitmap_bit_p (m_visited_blocks, e->src->index))
1128 add_bb (e->src);
1131 /* Determine if there are unvisited basic blocks. */
1132 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1133 if (!bitmap_bit_p (m_visited_blocks, bb->index))
1134 return bb;
1136 return NULL;
1139 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1140 if REVERSE, go against direction of edges. Returns number of blocks
1141 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1143 dfs_enumerate_from (basic_block bb, int reverse,
1144 bool (*predicate) (const_basic_block, const void *),
1145 basic_block *rslt, int rslt_max, const void *data)
1147 basic_block *st, lbb;
1148 int sp = 0, tv = 0;
1149 unsigned size;
1151 /* A bitmap to keep track of visited blocks. Allocating it each time
1152 this function is called is not possible, since dfs_enumerate_from
1153 is often used on small (almost) disjoint parts of cfg (bodies of
1154 loops), and allocating a large sbitmap would lead to quadratic
1155 behavior. */
1156 static sbitmap visited;
1157 static unsigned v_size;
1159 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1160 #define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
1161 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1163 /* Resize the VISITED sbitmap if necessary. */
1164 size = last_basic_block_for_fn (cfun);
1165 if (size < 10)
1166 size = 10;
1168 if (!visited)
1171 visited = sbitmap_alloc (size);
1172 bitmap_clear (visited);
1173 v_size = size;
1175 else if (v_size < size)
1177 /* Ensure that we increase the size of the sbitmap exponentially. */
1178 if (2 * v_size > size)
1179 size = 2 * v_size;
1181 visited = sbitmap_resize (visited, size, 0);
1182 v_size = size;
1185 st = XNEWVEC (basic_block, rslt_max);
1186 rslt[tv++] = st[sp++] = bb;
1187 MARK_VISITED (bb);
1188 while (sp)
1190 edge e;
1191 edge_iterator ei;
1192 lbb = st[--sp];
1193 if (reverse)
1195 FOR_EACH_EDGE (e, ei, lbb->preds)
1196 if (!VISITED_P (e->src) && predicate (e->src, data))
1198 gcc_assert (tv != rslt_max);
1199 rslt[tv++] = st[sp++] = e->src;
1200 MARK_VISITED (e->src);
1203 else
1205 FOR_EACH_EDGE (e, ei, lbb->succs)
1206 if (!VISITED_P (e->dest) && predicate (e->dest, data))
1208 gcc_assert (tv != rslt_max);
1209 rslt[tv++] = st[sp++] = e->dest;
1210 MARK_VISITED (e->dest);
1214 free (st);
1215 for (sp = 0; sp < tv; sp++)
1216 UNMARK_VISITED (rslt[sp]);
1217 return tv;
1218 #undef MARK_VISITED
1219 #undef UNMARK_VISITED
1220 #undef VISITED_P
1224 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1226 This algorithm can be found in Timothy Harvey's PhD thesis, at
1227 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1228 dominance algorithms.
1230 First, we identify each join point, j (any node with more than one
1231 incoming edge is a join point).
1233 We then examine each predecessor, p, of j and walk up the dominator tree
1234 starting at p.
1236 We stop the walk when we reach j's immediate dominator - j is in the
1237 dominance frontier of each of the nodes in the walk, except for j's
1238 immediate dominator. Intuitively, all of the rest of j's dominators are
1239 shared by j's predecessors as well.
1240 Since they dominate j, they will not have j in their dominance frontiers.
1242 The number of nodes touched by this algorithm is equal to the size
1243 of the dominance frontiers, no more, no less.
1247 static void
1248 compute_dominance_frontiers_1 (bitmap_head *frontiers)
1250 edge p;
1251 edge_iterator ei;
1252 basic_block b;
1253 FOR_EACH_BB_FN (b, cfun)
1255 if (EDGE_COUNT (b->preds) >= 2)
1257 FOR_EACH_EDGE (p, ei, b->preds)
1259 basic_block runner = p->src;
1260 basic_block domsb;
1261 if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1262 continue;
1264 domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1265 while (runner != domsb)
1267 if (!bitmap_set_bit (&frontiers[runner->index],
1268 b->index))
1269 break;
1270 runner = get_immediate_dominator (CDI_DOMINATORS,
1271 runner);
1279 void
1280 compute_dominance_frontiers (bitmap_head *frontiers)
1282 timevar_push (TV_DOM_FRONTIERS);
1284 compute_dominance_frontiers_1 (frontiers);
1286 timevar_pop (TV_DOM_FRONTIERS);
1289 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1290 return a bitmap with all the blocks in the iterated dominance
1291 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1292 frontier information as returned by compute_dominance_frontiers.
1294 The resulting set of blocks are the potential sites where PHI nodes
1295 are needed. The caller is responsible for freeing the memory
1296 allocated for the return value. */
1298 bitmap
1299 compute_idf (bitmap def_blocks, bitmap_head *dfs)
1301 bitmap_iterator bi;
1302 unsigned bb_index, i;
1303 bitmap phi_insertion_points;
1305 /* Each block can appear at most twice on the work-stack. */
1306 auto_vec<int> work_stack (2 * n_basic_blocks_for_fn (cfun));
1307 phi_insertion_points = BITMAP_ALLOC (NULL);
1309 /* Seed the work list with all the blocks in DEF_BLOCKS. We use
1310 vec::quick_push here for speed. This is safe because we know that
1311 the number of definition blocks is no greater than the number of
1312 basic blocks, which is the initial capacity of WORK_STACK. */
1313 EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
1314 work_stack.quick_push (bb_index);
1316 /* Pop a block off the worklist, add every block that appears in
1317 the original block's DF that we have not already processed to
1318 the worklist. Iterate until the worklist is empty. Blocks
1319 which are added to the worklist are potential sites for
1320 PHI nodes. */
1321 while (work_stack.length () > 0)
1323 bb_index = work_stack.pop ();
1325 /* Since the registration of NEW -> OLD name mappings is done
1326 separately from the call to update_ssa, when updating the SSA
1327 form, the basic blocks where new and/or old names are defined
1328 may have disappeared by CFG cleanup calls. In this case,
1329 we may pull a non-existing block from the work stack. */
1330 gcc_checking_assert (bb_index
1331 < (unsigned) last_basic_block_for_fn (cfun));
1333 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
1334 0, i, bi)
1336 work_stack.quick_push (i);
1337 bitmap_set_bit (phi_insertion_points, i);
1341 return phi_insertion_points;
1344 /* Intersection and union of preds/succs for sbitmap based data flow
1345 solvers. All four functions defined below take the same arguments:
1346 B is the basic block to perform the operation for. DST is the
1347 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1348 last_basic_block so that it can be indexed with basic block indices.
1349 DST may be (but does not have to be) SRC[B->index]. */
1351 /* Set the bitmap DST to the intersection of SRC of successors of
1352 basic block B. */
1354 void
1355 bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1357 unsigned int set_size = dst->size;
1358 edge e;
1359 unsigned ix;
1361 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1363 e = EDGE_SUCC (b, ix);
1364 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1365 continue;
1367 bitmap_copy (dst, src[e->dest->index]);
1368 break;
1371 if (e == 0)
1372 bitmap_ones (dst);
1373 else
1374 for (++ix; ix < EDGE_COUNT (b->succs); ix++)
1376 unsigned int i;
1377 SBITMAP_ELT_TYPE *p, *r;
1379 e = EDGE_SUCC (b, ix);
1380 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1381 continue;
1383 p = src[e->dest->index]->elms;
1384 r = dst->elms;
1385 for (i = 0; i < set_size; i++)
1386 *r++ &= *p++;
1390 /* Set the bitmap DST to the intersection of SRC of predecessors of
1391 basic block B. */
1393 void
1394 bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1396 unsigned int set_size = dst->size;
1397 edge e;
1398 unsigned ix;
1400 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1402 e = EDGE_PRED (b, ix);
1403 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1404 continue;
1406 bitmap_copy (dst, src[e->src->index]);
1407 break;
1410 if (e == 0)
1411 bitmap_ones (dst);
1412 else
1413 for (++ix; ix < EDGE_COUNT (b->preds); ix++)
1415 unsigned int i;
1416 SBITMAP_ELT_TYPE *p, *r;
1418 e = EDGE_PRED (b, ix);
1419 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1420 continue;
1422 p = src[e->src->index]->elms;
1423 r = dst->elms;
1424 for (i = 0; i < set_size; i++)
1425 *r++ &= *p++;
1429 /* Set the bitmap DST to the union of SRC of successors of
1430 basic block B. */
1432 void
1433 bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1435 unsigned int set_size = dst->size;
1436 edge e;
1437 unsigned ix;
1439 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1441 e = EDGE_SUCC (b, ix);
1442 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1443 continue;
1445 bitmap_copy (dst, src[e->dest->index]);
1446 break;
1449 if (ix == EDGE_COUNT (b->succs))
1450 bitmap_clear (dst);
1451 else
1452 for (ix++; ix < EDGE_COUNT (b->succs); ix++)
1454 unsigned int i;
1455 SBITMAP_ELT_TYPE *p, *r;
1457 e = EDGE_SUCC (b, ix);
1458 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1459 continue;
1461 p = src[e->dest->index]->elms;
1462 r = dst->elms;
1463 for (i = 0; i < set_size; i++)
1464 *r++ |= *p++;
1468 /* Set the bitmap DST to the union of SRC of predecessors of
1469 basic block B. */
1471 void
1472 bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1474 unsigned int set_size = dst->size;
1475 edge e;
1476 unsigned ix;
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 auto_sbitmap visited (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 gcc_assert (n == 0);
1553 return order;
1555 #undef MARK_VISITED
1556 #undef VISITED_P