Daily bump.
[official-gcc.git] / gcc / cfganal.c
blobcec5abe30f96d2dc2a63c8fe295142ef992a6ff9
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
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 noreturn block and
586 infinite loops to the exit block. Some optimizations require a path
587 from each node to 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 /* First add fake exits to noreturn blocks, this is required to
600 discover only truly infinite loops below. */
601 add_noreturn_fake_exit_edges ();
603 /* Perform depth-first search in the reverse graph to find nodes
604 reachable from the exit block. */
605 depth_first_search dfs;
606 dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
608 /* Repeatedly add fake edges, updating the unreachable nodes. */
609 basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
610 while (1)
612 unvisited_block = dfs.execute (unvisited_block);
613 if (!unvisited_block)
614 break;
616 basic_block deadend_block = dfs_find_deadend (unvisited_block);
617 edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun),
618 EDGE_FAKE);
619 e->probability = profile_probability::never ();
620 dfs.add_bb (deadend_block);
624 /* Compute reverse top sort order. This is computing a post order
625 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
626 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
627 true, unreachable blocks are deleted. */
630 post_order_compute (int *post_order, bool include_entry_exit,
631 bool delete_unreachable)
633 int post_order_num = 0;
634 int count;
636 if (include_entry_exit)
637 post_order[post_order_num++] = EXIT_BLOCK;
639 /* Allocate stack for back-tracking up CFG. */
640 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
642 /* Allocate bitmap to track nodes that have been visited. */
643 auto_sbitmap visited (last_basic_block_for_fn (cfun));
645 /* None of the nodes in the CFG have been visited yet. */
646 bitmap_clear (visited);
648 /* Push the first edge on to the stack. */
649 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
651 while (!stack.is_empty ())
653 basic_block src;
654 basic_block dest;
656 /* Look at the edge on the top of the stack. */
657 edge_iterator ei = stack.last ();
658 src = ei_edge (ei)->src;
659 dest = ei_edge (ei)->dest;
661 /* Check if the edge destination has been visited yet. */
662 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
663 && ! bitmap_bit_p (visited, dest->index))
665 /* Mark that we have visited the destination. */
666 bitmap_set_bit (visited, dest->index);
668 if (EDGE_COUNT (dest->succs) > 0)
669 /* Since the DEST node has been visited for the first
670 time, check its successors. */
671 stack.quick_push (ei_start (dest->succs));
672 else
673 post_order[post_order_num++] = dest->index;
675 else
677 if (ei_one_before_end_p (ei)
678 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
679 post_order[post_order_num++] = src->index;
681 if (!ei_one_before_end_p (ei))
682 ei_next (&stack.last ());
683 else
684 stack.pop ();
688 if (include_entry_exit)
690 post_order[post_order_num++] = ENTRY_BLOCK;
691 count = post_order_num;
693 else
694 count = post_order_num + 2;
696 /* Delete the unreachable blocks if some were found and we are
697 supposed to do it. */
698 if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
700 basic_block b;
701 basic_block next_bb;
702 for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
703 != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
705 next_bb = b->next_bb;
707 if (!(bitmap_bit_p (visited, b->index)))
708 delete_basic_block (b);
711 tidy_fallthru_edges ();
714 return post_order_num;
718 /* Helper routine for inverted_post_order_compute
719 flow_dfs_compute_reverse_execute, and the reverse-CFG
720 deapth first search in dominance.c.
721 BB has to belong to a region of CFG
722 unreachable by inverted traversal from the exit.
723 i.e. there's no control flow path from ENTRY to EXIT
724 that contains this BB.
725 This can happen in two cases - if there's an infinite loop
726 or if there's a block that has no successor
727 (call to a function with no return).
728 Some RTL passes deal with this condition by
729 calling connect_infinite_loops_to_exit () and/or
730 add_noreturn_fake_exit_edges ().
731 However, those methods involve modifying the CFG itself
732 which may not be desirable.
733 Hence, we deal with the infinite loop/no return cases
734 by identifying a unique basic block that can reach all blocks
735 in such a region by inverted traversal.
736 This function returns a basic block that guarantees
737 that all blocks in the region are reachable
738 by starting an inverted traversal from the returned block. */
740 basic_block
741 dfs_find_deadend (basic_block bb)
743 auto_bitmap visited;
744 basic_block next = bb;
746 for (;;)
748 if (EDGE_COUNT (next->succs) == 0)
749 return next;
751 if (! bitmap_set_bit (visited, next->index))
752 return bb;
754 bb = next;
755 /* If we are in an analyzed cycle make sure to try exiting it.
756 Note this is a heuristic only and expected to work when loop
757 fixup is needed as well. */
758 if (! bb->loop_father
759 || ! loop_outer (bb->loop_father))
760 next = EDGE_SUCC (bb, 0)->dest;
761 else
763 edge_iterator ei;
764 edge e;
765 FOR_EACH_EDGE (e, ei, bb->succs)
766 if (loop_exit_edge_p (bb->loop_father, e))
767 break;
768 next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
772 gcc_unreachable ();
776 /* Compute the reverse top sort order of the inverted CFG
777 i.e. starting from the exit block and following the edges backward
778 (from successors to predecessors).
779 This ordering can be used for forward dataflow problems among others.
781 Optionally if START_POINTS is specified, start from exit block and all
782 basic blocks in START_POINTS. This is used by CD-DCE.
784 This function assumes that all blocks in the CFG are reachable
785 from the ENTRY (but not necessarily from EXIT).
787 If there's an infinite loop,
788 a simple inverted traversal starting from the blocks
789 with no successors can't visit all blocks.
790 To solve this problem, we first do inverted traversal
791 starting from the blocks with no successor.
792 And if there's any block left that's not visited by the regular
793 inverted traversal from EXIT,
794 those blocks are in such problematic region.
795 Among those, we find one block that has
796 any visited predecessor (which is an entry into such a region),
797 and start looking for a "dead end" from that block
798 and do another inverted traversal from that block. */
800 void
801 inverted_post_order_compute (vec<int> *post_order,
802 sbitmap *start_points)
804 basic_block bb;
805 post_order->reserve_exact (n_basic_blocks_for_fn (cfun));
807 if (flag_checking)
808 verify_no_unreachable_blocks ();
810 /* Allocate stack for back-tracking up CFG. */
811 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
813 /* Allocate bitmap to track nodes that have been visited. */
814 auto_sbitmap visited (last_basic_block_for_fn (cfun));
816 /* None of the nodes in the CFG have been visited yet. */
817 bitmap_clear (visited);
819 if (start_points)
821 FOR_ALL_BB_FN (bb, cfun)
822 if (bitmap_bit_p (*start_points, bb->index)
823 && EDGE_COUNT (bb->preds) > 0)
825 stack.quick_push (ei_start (bb->preds));
826 bitmap_set_bit (visited, bb->index);
828 if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
830 stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds));
831 bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
834 else
835 /* Put all blocks that have no successor into the initial work list. */
836 FOR_ALL_BB_FN (bb, cfun)
837 if (EDGE_COUNT (bb->succs) == 0)
839 /* Push the initial edge on to the stack. */
840 if (EDGE_COUNT (bb->preds) > 0)
842 stack.quick_push (ei_start (bb->preds));
843 bitmap_set_bit (visited, bb->index);
849 bool has_unvisited_bb = false;
851 /* The inverted traversal loop. */
852 while (!stack.is_empty ())
854 edge_iterator ei;
855 basic_block pred;
857 /* Look at the edge on the top of the stack. */
858 ei = stack.last ();
859 bb = ei_edge (ei)->dest;
860 pred = ei_edge (ei)->src;
862 /* Check if the predecessor has been visited yet. */
863 if (! bitmap_bit_p (visited, pred->index))
865 /* Mark that we have visited the destination. */
866 bitmap_set_bit (visited, pred->index);
868 if (EDGE_COUNT (pred->preds) > 0)
869 /* Since the predecessor node has been visited for the first
870 time, check its predecessors. */
871 stack.quick_push (ei_start (pred->preds));
872 else
873 post_order->quick_push (pred->index);
875 else
877 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
878 && ei_one_before_end_p (ei))
879 post_order->quick_push (bb->index);
881 if (!ei_one_before_end_p (ei))
882 ei_next (&stack.last ());
883 else
884 stack.pop ();
888 /* Detect any infinite loop and activate the kludge.
889 Note that this doesn't check EXIT_BLOCK itself
890 since EXIT_BLOCK is always added after the outer do-while loop. */
891 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
892 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
893 if (!bitmap_bit_p (visited, bb->index))
895 has_unvisited_bb = true;
897 if (EDGE_COUNT (bb->preds) > 0)
899 edge_iterator ei;
900 edge e;
901 basic_block visited_pred = NULL;
903 /* Find an already visited predecessor. */
904 FOR_EACH_EDGE (e, ei, bb->preds)
906 if (bitmap_bit_p (visited, e->src->index))
907 visited_pred = e->src;
910 if (visited_pred)
912 basic_block be = dfs_find_deadend (bb);
913 gcc_assert (be != NULL);
914 bitmap_set_bit (visited, be->index);
915 stack.quick_push (ei_start (be->preds));
916 break;
921 if (has_unvisited_bb && stack.is_empty ())
923 /* No blocks are reachable from EXIT at all.
924 Find a dead-end from the ENTRY, and restart the iteration. */
925 basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
926 gcc_assert (be != NULL);
927 bitmap_set_bit (visited, be->index);
928 stack.quick_push (ei_start (be->preds));
931 /* The only case the below while fires is
932 when there's an infinite loop. */
934 while (!stack.is_empty ());
936 /* EXIT_BLOCK is always included. */
937 post_order->quick_push (EXIT_BLOCK);
940 /* Compute the depth first search order of FN and store in the array
941 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
942 reverse completion number for each node. Returns the number of nodes
943 visited. A depth first search tries to get as far away from the starting
944 point as quickly as possible.
946 In case the function has unreachable blocks the number of nodes
947 visited does not include them.
949 pre_order is a really a preorder numbering of the graph.
950 rev_post_order is really a reverse postorder numbering of the graph. */
953 pre_and_rev_post_order_compute_fn (struct function *fn,
954 int *pre_order, int *rev_post_order,
955 bool include_entry_exit)
957 int pre_order_num = 0;
958 int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
960 /* Allocate stack for back-tracking up CFG. */
961 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1);
963 if (include_entry_exit)
965 if (pre_order)
966 pre_order[pre_order_num] = ENTRY_BLOCK;
967 pre_order_num++;
968 if (rev_post_order)
969 rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
971 else
972 rev_post_order_num -= NUM_FIXED_BLOCKS;
974 /* BB flag to track nodes that have been visited. */
975 auto_bb_flag visited (fn);
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 && ! (dest->flags & visited))
994 /* Mark that we have visited the destination. */
995 dest->flags |= visited;
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 /* Clear the temporarily allocated flag. */
1037 if (!rev_post_order)
1038 rev_post_order = pre_order;
1039 for (int i = 0; i < pre_order_num; ++i)
1040 BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags &= ~visited;
1042 return pre_order_num;
1045 /* Like pre_and_rev_post_order_compute_fn but operating on the
1046 current function and asserting that all nodes were visited. */
1049 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
1050 bool include_entry_exit)
1052 int pre_order_num
1053 = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
1054 include_entry_exit);
1055 if (include_entry_exit)
1056 /* The number of nodes visited should be the number of blocks. */
1057 gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun));
1058 else
1059 /* The number of nodes visited should be the number of blocks minus
1060 the entry and exit blocks which are not visited here. */
1061 gcc_assert (pre_order_num
1062 == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
1064 return pre_order_num;
1068 /* Per basic-block data for rev_post_order_and_mark_dfs_back_seme,
1069 element of a sparsely populated array indexed by basic-block number. */
1070 typedef auto_vec<int, 2> scc_exit_vec_t;
1071 struct rpoamdbs_bb_data {
1072 int depth;
1073 int bb_to_pre;
1074 /* The basic-block index of the SCC entry of the block visited first
1075 (the SCC leader). */
1076 int scc;
1077 /* The index into the RPO array where the blocks SCC entries end
1078 (only valid for the SCC leader). */
1079 int scc_end;
1080 /* The indexes of the exits destinations of this SCC (only valid
1081 for the SCC leader). Initialized upon discovery of SCC leaders. */
1082 scc_exit_vec_t scc_exits;
1085 /* Tag H as a header of B, weaving H and its loop header list into the
1086 current loop header list of B. */
1088 static void
1089 tag_header (int b, int h, rpoamdbs_bb_data *bb_data)
1091 if (h == -1 || b == h)
1092 return;
1093 int cur1 = b;
1094 int cur2 = h;
1095 while (bb_data[cur1].scc != -1)
1097 int ih = bb_data[cur1].scc;
1098 if (ih == cur2)
1099 return;
1100 if (bb_data[ih].depth < bb_data[cur2].depth)
1102 bb_data[cur1].scc = cur2;
1103 cur1 = cur2;
1104 cur2 = ih;
1106 else
1107 cur1 = ih;
1109 bb_data[cur1].scc = cur2;
1112 /* Comparator for a sort of two edges destinations E1 and E2 after their index
1113 in the PRE array as specified by BB_TO_PRE. */
1115 static int
1116 cmp_edge_dest_pre (const void *e1_, const void *e2_, void *data_)
1118 const int *e1 = (const int *)e1_;
1119 const int *e2 = (const int *)e2_;
1120 rpoamdbs_bb_data *bb_data = (rpoamdbs_bb_data *)data_;
1121 return (bb_data[*e1].bb_to_pre - bb_data[*e2].bb_to_pre);
1124 /* Compute the reverse completion number of a depth first search
1125 on the SEME region denoted by the ENTRY edge and the EXIT_BBS set of
1126 exit block indexes and store it in the array REV_POST_ORDER.
1127 Also sets the EDGE_DFS_BACK edge flags according to this visitation
1128 order.
1129 Returns the number of nodes visited.
1131 In case the function has unreachable blocks the number of nodes
1132 visited does not include them.
1134 If FOR_ITERATION is true then compute an RPO where SCCs form a
1135 contiguous region in the RPO array.
1136 *TOPLEVEL_SCC_EXTENTS if not NULL is filled with pairs of
1137 *REV_POST_ORDER indexes denoting extents of the toplevel SCCs in
1138 this region. */
1141 rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry,
1142 bitmap exit_bbs, bool for_iteration,
1143 int *rev_post_order,
1144 vec<std::pair<int, int> >
1145 *toplevel_scc_extents)
1147 int rev_post_order_num = 0;
1149 /* BB flag to track nodes that have been visited. */
1150 auto_bb_flag visited (fn);
1152 /* Lazily initialized per-BB data for the two DFS walks below. */
1153 rpoamdbs_bb_data *bb_data
1154 = XNEWVEC (rpoamdbs_bb_data, last_basic_block_for_fn (fn));
1156 /* First DFS walk, loop discovery according to
1157 A New Algorithm for Identifying Loops in Decompilation
1158 by Tao Wei, Jian Mao, Wei Zou and You Chen of the Institute of
1159 Computer Science and Technology of the Peking University. */
1160 auto_vec<edge_iterator, 20> ei_stack (n_basic_blocks_for_fn (fn) + 1);
1161 auto_bb_flag is_header (fn);
1162 int depth = 1;
1163 unsigned n_sccs = 0;
1165 basic_block dest = entry->dest;
1166 edge_iterator ei;
1167 int pre_num = 0;
1169 /* DFS process DEST. */
1170 find_loops:
1171 bb_data[dest->index].bb_to_pre = pre_num++;
1172 bb_data[dest->index].depth = depth;
1173 bb_data[dest->index].scc = -1;
1174 depth++;
1175 gcc_assert ((dest->flags & (is_header|visited)) == 0);
1176 dest->flags |= visited;
1177 ei = ei_start (dest->succs);
1178 while (!ei_end_p (ei))
1180 ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
1181 if (bitmap_bit_p (exit_bbs, ei_edge (ei)->dest->index))
1183 else if (!(ei_edge (ei)->dest->flags & visited))
1185 ei_stack.quick_push (ei);
1186 dest = ei_edge (ei)->dest;
1187 /* DFS recurse on DEST. */
1188 goto find_loops;
1190 ret_from_find_loops:
1191 /* Return point of DFS recursion. */
1192 ei = ei_stack.pop ();
1193 dest = ei_edge (ei)->src;
1194 int header = bb_data[ei_edge (ei)->dest->index].scc;
1195 tag_header (dest->index, header, bb_data);
1196 depth = bb_data[dest->index].depth + 1;
1198 else
1200 if (bb_data[ei_edge (ei)->dest->index].depth > 0) /* on the stack */
1202 ei_edge (ei)->flags |= EDGE_DFS_BACK;
1203 n_sccs++;
1204 ei_edge (ei)->dest->flags |= is_header;
1205 ::new (&bb_data[ei_edge (ei)->dest->index].scc_exits)
1206 auto_vec<int, 2> ();
1207 tag_header (dest->index, ei_edge (ei)->dest->index, bb_data);
1209 else if (bb_data[ei_edge (ei)->dest->index].scc == -1)
1211 else
1213 int header = bb_data[ei_edge (ei)->dest->index].scc;
1214 if (bb_data[header].depth > 0)
1215 tag_header (dest->index, header, bb_data);
1216 else
1218 /* A re-entry into an existing loop. */
1219 /* ??? Need to mark is_header? */
1220 while (bb_data[header].scc != -1)
1222 header = bb_data[header].scc;
1223 if (bb_data[header].depth > 0)
1225 tag_header (dest->index, header, bb_data);
1226 break;
1232 ei_next (&ei);
1234 rev_post_order[rev_post_order_num++] = dest->index;
1235 /* not on the stack anymore */
1236 bb_data[dest->index].depth = -bb_data[dest->index].depth;
1237 if (!ei_stack.is_empty ())
1238 /* Return from DFS recursion. */
1239 goto ret_from_find_loops;
1241 /* Optimize for no SCCs found or !for_iteration. */
1242 if (n_sccs == 0 || !for_iteration)
1244 /* Clear the temporarily allocated flags. */
1245 for (int i = 0; i < rev_post_order_num; ++i)
1246 BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags
1247 &= ~(is_header|visited);
1248 /* And swap elements. */
1249 for (int i = 0; i < rev_post_order_num/2; ++i)
1250 std::swap (rev_post_order[i], rev_post_order[rev_post_order_num-i-1]);
1251 XDELETEVEC (bb_data);
1253 return rev_post_order_num;
1256 /* Next find SCC exits, clear the visited flag and compute an upper bound
1257 for the edge stack below. */
1258 unsigned edge_count = 0;
1259 for (int i = 0; i < rev_post_order_num; ++i)
1261 int bb = rev_post_order[i];
1262 BASIC_BLOCK_FOR_FN (fn, bb)->flags &= ~visited;
1263 edge e;
1264 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (fn, bb)->succs)
1266 if (bitmap_bit_p (exit_bbs, e->dest->index))
1267 continue;
1268 edge_count++;
1269 /* if e is an exit from e->src, record it for
1270 bb_data[e->src].scc. */
1271 int src_scc = e->src->index;
1272 if (!(e->src->flags & is_header))
1273 src_scc = bb_data[src_scc].scc;
1274 if (src_scc == -1)
1275 continue;
1276 int dest_scc = e->dest->index;
1277 if (!(e->dest->flags & is_header))
1278 dest_scc = bb_data[dest_scc].scc;
1279 if (src_scc == dest_scc)
1280 continue;
1281 /* When dest_scc is nested insde src_scc it's not an
1282 exit. */
1283 int tem_dest_scc = dest_scc;
1284 unsigned dest_scc_depth = 0;
1285 while (tem_dest_scc != -1)
1287 dest_scc_depth++;
1288 if ((tem_dest_scc = bb_data[tem_dest_scc].scc) == src_scc)
1289 break;
1291 if (tem_dest_scc != -1)
1292 continue;
1293 /* When src_scc is nested inside dest_scc record an
1294 exit from the outermost SCC this edge exits. */
1295 int tem_src_scc = src_scc;
1296 unsigned src_scc_depth = 0;
1297 while (tem_src_scc != -1)
1299 if (bb_data[tem_src_scc].scc == dest_scc)
1301 edge_count++;
1302 bb_data[tem_src_scc].scc_exits.safe_push (e->dest->index);
1303 break;
1305 tem_src_scc = bb_data[tem_src_scc].scc;
1306 src_scc_depth++;
1308 /* Else find the outermost SCC this edge exits (exits
1309 from the inner SCCs are not important for the DFS
1310 walk adjustment). Do so by computing the common
1311 ancestor SCC where the immediate child it to the source
1312 SCC is the exited SCC. */
1313 if (tem_src_scc == -1)
1315 edge_count++;
1316 while (src_scc_depth > dest_scc_depth)
1318 src_scc = bb_data[src_scc].scc;
1319 src_scc_depth--;
1321 while (dest_scc_depth > src_scc_depth)
1323 dest_scc = bb_data[dest_scc].scc;
1324 dest_scc_depth--;
1326 while (bb_data[src_scc].scc != bb_data[dest_scc].scc)
1328 src_scc = bb_data[src_scc].scc;
1329 dest_scc = bb_data[dest_scc].scc;
1331 bb_data[src_scc].scc_exits.safe_push (e->dest->index);
1336 /* Now the second DFS walk to compute a RPO where the extent of SCCs
1337 is minimized thus SCC members are adjacent in the RPO array.
1338 This is done by performing a DFS walk computing RPO with first visiting
1339 extra direct edges from SCC entry to its exits.
1340 That simulates a DFS walk over the graph with SCCs collapsed and
1341 walking the SCCs themselves only when all outgoing edges from the
1342 SCCs have been visited.
1343 SCC_END[scc-header-index] is the position in the RPO array of the
1344 last member of the SCC. */
1345 auto_vec<std::pair<basic_block, basic_block>, 20> estack (edge_count + 1);
1346 int idx = rev_post_order_num;
1347 basic_block edest;
1348 dest = entry->dest;
1350 /* DFS process DEST. */
1351 dfs_rpo:
1352 gcc_checking_assert ((dest->flags & visited) == 0);
1353 /* Verify we enter SCCs through the same header and SCC nesting appears
1354 the same. */
1355 gcc_assert (bb_data[dest->index].scc == -1
1356 || (BASIC_BLOCK_FOR_FN (fn, bb_data[dest->index].scc)->flags
1357 & visited));
1358 dest->flags |= visited;
1359 bb_data[dest->index].scc_end = -1;
1360 if ((dest->flags & is_header)
1361 && !bb_data[dest->index].scc_exits.is_empty ())
1363 /* Push the all SCC exits as outgoing edges from its header to
1364 be visited first.
1365 To process exits in the same relative order as in the first
1366 DFS walk sort them after their destination PRE order index. */
1367 gcc_sort_r (&bb_data[dest->index].scc_exits[0],
1368 bb_data[dest->index].scc_exits.length (),
1369 sizeof (int), cmp_edge_dest_pre, bb_data);
1370 /* Process edges in reverse to match previous DFS walk order. */
1371 for (int i = bb_data[dest->index].scc_exits.length () - 1; i >= 0; --i)
1372 estack.quick_push (std::make_pair
1373 (dest, BASIC_BLOCK_FOR_FN (fn, bb_data[dest->index].scc_exits[i])));
1375 else
1377 if (dest->flags & is_header)
1378 bb_data[dest->index].scc_end = idx - 1;
1379 /* Push the edge vector in reverse to match the iteration order
1380 from the DFS walk above. */
1381 for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
1382 if (!bitmap_bit_p (exit_bbs, EDGE_SUCC (dest, i)->dest->index))
1383 estack.quick_push (std::make_pair (dest,
1384 EDGE_SUCC (dest, i)->dest));
1386 while (!estack.is_empty ()
1387 && estack.last ().first == dest)
1389 edest = estack.last ().second;
1390 if (!(edest->flags & visited))
1392 dest = edest;
1393 /* DFS recurse on DEST. */
1394 goto dfs_rpo;
1396 ret_from_dfs_rpo:
1397 /* Return point of DFS recursion. */
1398 dest = estack.last ().first;
1400 estack.pop ();
1401 /* If we processed all SCC exits from DEST mark the SCC end
1402 since all RPO entries up to DEST itself will now belong
1403 to its SCC. The special-case of no SCC exits is already
1404 dealt with above. */
1405 if (dest->flags & is_header
1406 /* When the last exit edge was processed mark the SCC end
1407 and push the regular edges. */
1408 && bb_data[dest->index].scc_end == -1
1409 && (estack.is_empty ()
1410 || estack.last ().first != dest))
1412 bb_data[dest->index].scc_end = idx - 1;
1413 /* Push the edge vector in reverse to match the iteration order
1414 from the DFS walk above. */
1415 for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
1416 if (!bitmap_bit_p (exit_bbs, EDGE_SUCC (dest, i)->dest->index))
1417 estack.quick_push (std::make_pair (dest,
1418 EDGE_SUCC (dest, i)->dest));
1421 rev_post_order[--idx] = dest->index;
1422 if (!estack.is_empty ())
1423 /* Return from DFS recursion. */
1424 goto ret_from_dfs_rpo;
1426 /* Each SCC extends are from the position of the header inside
1427 the RPO array up to RPO array index scc_end[header-index]. */
1428 if (toplevel_scc_extents)
1429 for (int i = 0; i < rev_post_order_num; i++)
1431 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rev_post_order[i]);
1432 if (bb->flags & is_header)
1434 toplevel_scc_extents->safe_push
1435 (std::make_pair (i, bb_data[bb->index].scc_end));
1436 i = bb_data[bb->index].scc_end;
1440 /* Clear the temporarily allocated flags and free memory. */
1441 for (int i = 0; i < rev_post_order_num; ++i)
1443 basic_block bb = BASIC_BLOCK_FOR_FN (fn, rev_post_order[i]);
1444 if (bb->flags & is_header)
1445 bb_data[bb->index].scc_exits.~scc_exit_vec_t ();
1446 bb->flags &= ~(visited|is_header);
1449 XDELETEVEC (bb_data);
1451 return rev_post_order_num;
1456 /* Compute the depth first search order on the _reverse_ graph and
1457 store it in the array DFS_ORDER, marking the nodes visited in VISITED.
1458 Returns the number of nodes visited.
1460 The computation is split into three pieces:
1462 flow_dfs_compute_reverse_init () creates the necessary data
1463 structures.
1465 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1466 structures. The block will start the search.
1468 flow_dfs_compute_reverse_execute () continues (or starts) the
1469 search using the block on the top of the stack, stopping when the
1470 stack is empty.
1472 flow_dfs_compute_reverse_finish () destroys the necessary data
1473 structures.
1475 Thus, the user will probably call ..._init(), call ..._add_bb() to
1476 add a beginning basic block to the stack, call ..._execute(),
1477 possibly add another bb to the stack and again call ..._execute(),
1478 ..., and finally call _finish(). */
1480 /* Initialize the data structures used for depth-first search on the
1481 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1482 added to the basic block stack. DATA is the current depth-first
1483 search context. If INITIALIZE_STACK is nonzero, there is an
1484 element on the stack. */
1486 depth_first_search::depth_first_search () :
1487 m_stack (n_basic_blocks_for_fn (cfun)),
1488 m_visited_blocks (last_basic_block_for_fn (cfun))
1490 bitmap_clear (m_visited_blocks);
1493 /* Add the specified basic block to the top of the dfs data
1494 structures. When the search continues, it will start at the
1495 block. */
1497 void
1498 depth_first_search::add_bb (basic_block bb)
1500 m_stack.quick_push (bb);
1501 bitmap_set_bit (m_visited_blocks, bb->index);
1504 /* Continue the depth-first search through the reverse graph starting with the
1505 block at the stack's top and ending when the stack is empty. Visited nodes
1506 are marked. Returns an unvisited basic block, or NULL if there is none
1507 available. */
1509 basic_block
1510 depth_first_search::execute (basic_block last_unvisited)
1512 basic_block bb;
1513 edge e;
1514 edge_iterator ei;
1516 while (!m_stack.is_empty ())
1518 bb = m_stack.pop ();
1520 /* Perform depth-first search on adjacent vertices. */
1521 FOR_EACH_EDGE (e, ei, bb->preds)
1522 if (!bitmap_bit_p (m_visited_blocks, e->src->index))
1523 add_bb (e->src);
1526 /* Determine if there are unvisited basic blocks. */
1527 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1528 if (!bitmap_bit_p (m_visited_blocks, bb->index))
1529 return bb;
1531 return NULL;
1534 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1535 if REVERSE, go against direction of edges. Returns number of blocks
1536 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1538 dfs_enumerate_from (basic_block bb, int reverse,
1539 bool (*predicate) (const_basic_block, const void *),
1540 basic_block *rslt, int rslt_max, const void *data)
1542 basic_block *st, lbb;
1543 int sp = 0, tv = 0;
1545 auto_bb_flag visited (cfun);
1547 #define MARK_VISITED(BB) ((BB)->flags |= visited)
1548 #define UNMARK_VISITED(BB) ((BB)->flags &= ~visited)
1549 #define VISITED_P(BB) (((BB)->flags & visited) != 0)
1551 st = XNEWVEC (basic_block, rslt_max);
1552 rslt[tv++] = st[sp++] = bb;
1553 MARK_VISITED (bb);
1554 while (sp)
1556 edge e;
1557 edge_iterator ei;
1558 lbb = st[--sp];
1559 if (reverse)
1561 FOR_EACH_EDGE (e, ei, lbb->preds)
1562 if (!VISITED_P (e->src) && predicate (e->src, data))
1564 gcc_assert (tv != rslt_max);
1565 rslt[tv++] = st[sp++] = e->src;
1566 MARK_VISITED (e->src);
1569 else
1571 FOR_EACH_EDGE (e, ei, lbb->succs)
1572 if (!VISITED_P (e->dest) && predicate (e->dest, data))
1574 gcc_assert (tv != rslt_max);
1575 rslt[tv++] = st[sp++] = e->dest;
1576 MARK_VISITED (e->dest);
1580 free (st);
1581 for (sp = 0; sp < tv; sp++)
1582 UNMARK_VISITED (rslt[sp]);
1583 return tv;
1584 #undef MARK_VISITED
1585 #undef UNMARK_VISITED
1586 #undef VISITED_P
1590 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1592 This algorithm can be found in Timothy Harvey's PhD thesis, at
1593 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1594 dominance algorithms.
1596 First, we identify each join point, j (any node with more than one
1597 incoming edge is a join point).
1599 We then examine each predecessor, p, of j and walk up the dominator tree
1600 starting at p.
1602 We stop the walk when we reach j's immediate dominator - j is in the
1603 dominance frontier of each of the nodes in the walk, except for j's
1604 immediate dominator. Intuitively, all of the rest of j's dominators are
1605 shared by j's predecessors as well.
1606 Since they dominate j, they will not have j in their dominance frontiers.
1608 The number of nodes touched by this algorithm is equal to the size
1609 of the dominance frontiers, no more, no less.
1612 void
1613 compute_dominance_frontiers (bitmap_head *frontiers)
1615 timevar_push (TV_DOM_FRONTIERS);
1617 edge p;
1618 edge_iterator ei;
1619 basic_block b;
1620 FOR_EACH_BB_FN (b, cfun)
1622 if (EDGE_COUNT (b->preds) >= 2)
1624 basic_block domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1625 FOR_EACH_EDGE (p, ei, b->preds)
1627 basic_block runner = p->src;
1628 if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1629 continue;
1631 while (runner != domsb)
1633 if (!bitmap_set_bit (&frontiers[runner->index], b->index))
1634 break;
1635 runner = get_immediate_dominator (CDI_DOMINATORS, runner);
1641 timevar_pop (TV_DOM_FRONTIERS);
1644 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1645 return a bitmap with all the blocks in the iterated dominance
1646 frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1647 frontier information as returned by compute_dominance_frontiers.
1649 The resulting set of blocks are the potential sites where PHI nodes
1650 are needed. The caller is responsible for freeing the memory
1651 allocated for the return value. */
1653 bitmap
1654 compute_idf (bitmap def_blocks, bitmap_head *dfs)
1656 bitmap_iterator bi;
1657 unsigned bb_index, i;
1658 bitmap phi_insertion_points;
1660 phi_insertion_points = BITMAP_ALLOC (NULL);
1662 /* Seed the work set with all the blocks in DEF_BLOCKS. */
1663 auto_bitmap work_set;
1664 bitmap_copy (work_set, def_blocks);
1665 bitmap_tree_view (work_set);
1667 /* Pop a block off the workset, add every block that appears in
1668 the original block's DF that we have not already processed to
1669 the workset. Iterate until the workset is empty. Blocks
1670 which are added to the workset are potential sites for
1671 PHI nodes. */
1672 while (!bitmap_empty_p (work_set))
1674 /* The dominance frontier of a block is blocks after it so iterating
1675 on earlier blocks first is better.
1676 ??? Basic blocks are by no means guaranteed to be ordered in
1677 optimal order for this iteration. */
1678 bb_index = bitmap_first_set_bit (work_set);
1679 bitmap_clear_bit (work_set, bb_index);
1681 /* Since the registration of NEW -> OLD name mappings is done
1682 separately from the call to update_ssa, when updating the SSA
1683 form, the basic blocks where new and/or old names are defined
1684 may have disappeared by CFG cleanup calls. In this case,
1685 we may pull a non-existing block from the work stack. */
1686 gcc_checking_assert (bb_index
1687 < (unsigned) last_basic_block_for_fn (cfun));
1689 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
1690 0, i, bi)
1692 bitmap_set_bit (work_set, i);
1693 bitmap_set_bit (phi_insertion_points, i);
1697 return phi_insertion_points;
1700 /* Intersection and union of preds/succs for sbitmap based data flow
1701 solvers. All four functions defined below take the same arguments:
1702 B is the basic block to perform the operation for. DST is the
1703 target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1704 last_basic_block so that it can be indexed with basic block indices.
1705 DST may be (but does not have to be) SRC[B->index]. */
1707 /* Set the bitmap DST to the intersection of SRC of successors of
1708 basic block B. */
1710 void
1711 bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1713 unsigned int set_size = dst->size;
1714 edge e;
1715 unsigned ix;
1717 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1719 e = EDGE_SUCC (b, ix);
1720 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1721 continue;
1723 bitmap_copy (dst, src[e->dest->index]);
1724 break;
1727 if (e == 0)
1728 bitmap_ones (dst);
1729 else
1730 for (++ix; ix < EDGE_COUNT (b->succs); ix++)
1732 unsigned int i;
1733 SBITMAP_ELT_TYPE *p, *r;
1735 e = EDGE_SUCC (b, ix);
1736 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1737 continue;
1739 p = src[e->dest->index]->elms;
1740 r = dst->elms;
1741 for (i = 0; i < set_size; i++)
1742 *r++ &= *p++;
1746 /* Set the bitmap DST to the intersection of SRC of predecessors of
1747 basic block B. */
1749 void
1750 bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1752 unsigned int set_size = dst->size;
1753 edge e;
1754 unsigned ix;
1756 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1758 e = EDGE_PRED (b, ix);
1759 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1760 continue;
1762 bitmap_copy (dst, src[e->src->index]);
1763 break;
1766 if (e == 0)
1767 bitmap_ones (dst);
1768 else
1769 for (++ix; ix < EDGE_COUNT (b->preds); ix++)
1771 unsigned int i;
1772 SBITMAP_ELT_TYPE *p, *r;
1774 e = EDGE_PRED (b, ix);
1775 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1776 continue;
1778 p = src[e->src->index]->elms;
1779 r = dst->elms;
1780 for (i = 0; i < set_size; i++)
1781 *r++ &= *p++;
1785 /* Set the bitmap DST to the union of SRC of successors of
1786 basic block B. */
1788 void
1789 bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1791 unsigned int set_size = dst->size;
1792 edge e;
1793 unsigned ix;
1795 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1797 e = EDGE_SUCC (b, ix);
1798 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1799 continue;
1801 bitmap_copy (dst, src[e->dest->index]);
1802 break;
1805 if (ix == EDGE_COUNT (b->succs))
1806 bitmap_clear (dst);
1807 else
1808 for (ix++; ix < EDGE_COUNT (b->succs); ix++)
1810 unsigned int i;
1811 SBITMAP_ELT_TYPE *p, *r;
1813 e = EDGE_SUCC (b, ix);
1814 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1815 continue;
1817 p = src[e->dest->index]->elms;
1818 r = dst->elms;
1819 for (i = 0; i < set_size; i++)
1820 *r++ |= *p++;
1824 /* Set the bitmap DST to the union of SRC of predecessors of
1825 basic block B. */
1827 void
1828 bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1830 unsigned int set_size = dst->size;
1831 edge e;
1832 unsigned ix;
1834 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1836 e = EDGE_PRED (b, ix);
1837 if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun))
1838 continue;
1840 bitmap_copy (dst, src[e->src->index]);
1841 break;
1844 if (ix == EDGE_COUNT (b->preds))
1845 bitmap_clear (dst);
1846 else
1847 for (ix++; ix < EDGE_COUNT (b->preds); ix++)
1849 unsigned int i;
1850 SBITMAP_ELT_TYPE *p, *r;
1852 e = EDGE_PRED (b, ix);
1853 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1854 continue;
1856 p = src[e->src->index]->elms;
1857 r = dst->elms;
1858 for (i = 0; i < set_size; i++)
1859 *r++ |= *p++;
1863 /* Returns the list of basic blocks in the function in an order that guarantees
1864 that if a block X has just a single predecessor Y, then Y is after X in the
1865 ordering. */
1867 basic_block *
1868 single_pred_before_succ_order (void)
1870 basic_block x, y;
1871 basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1872 unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1873 unsigned np, i;
1874 auto_sbitmap visited (last_basic_block_for_fn (cfun));
1876 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1877 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1879 bitmap_clear (visited);
1881 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1882 FOR_EACH_BB_FN (x, cfun)
1884 if (VISITED_P (x))
1885 continue;
1887 /* Walk the predecessors of x as long as they have precisely one
1888 predecessor and add them to the list, so that they get stored
1889 after x. */
1890 for (y = x, np = 1;
1891 single_pred_p (y) && !VISITED_P (single_pred (y));
1892 y = single_pred (y))
1893 np++;
1894 for (y = x, i = n - np;
1895 single_pred_p (y) && !VISITED_P (single_pred (y));
1896 y = single_pred (y), i++)
1898 order[i] = y;
1899 MARK_VISITED (y);
1901 order[i] = y;
1902 MARK_VISITED (y);
1904 gcc_assert (i == n - 1);
1905 n -= np;
1908 gcc_assert (n == 0);
1909 return order;
1911 #undef MARK_VISITED
1912 #undef VISITED_P
1915 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1916 return that edge. Otherwise return NULL.
1918 When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
1919 as executable. */
1921 edge
1922 single_pred_edge_ignoring_loop_edges (basic_block bb,
1923 bool ignore_not_executable)
1925 edge retval = NULL;
1926 edge e;
1927 edge_iterator ei;
1929 FOR_EACH_EDGE (e, ei, bb->preds)
1931 /* A loop back edge can be identified by the destination of
1932 the edge dominating the source of the edge. */
1933 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1934 continue;
1936 /* We can safely ignore edges that are not executable. */
1937 if (ignore_not_executable
1938 && (e->flags & EDGE_EXECUTABLE) == 0)
1939 continue;
1941 /* If we have already seen a non-loop edge, then we must have
1942 multiple incoming non-loop edges and thus we return NULL. */
1943 if (retval)
1944 return NULL;
1946 /* This is the first non-loop incoming edge we have found. Record
1947 it. */
1948 retval = e;
1951 return retval;