1 /* Control flow graph analysis code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains various simple utilities to analyze the CFG. */
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
28 #include "insn-config.h"
33 /* Store the data structures necessary for depth-first search. */
34 struct depth_first_search_dsS {
35 /* stack for backtracking during the algorithm */
38 /* number of edges in the stack. That is, positions 0, ..., sp-1
42 /* record of basic blocks already seen by depth-first search */
43 sbitmap visited_blocks;
45 typedef struct depth_first_search_dsS *depth_first_search_ds;
47 static void flow_dfs_compute_reverse_init
48 PARAMS ((depth_first_search_ds));
49 static void flow_dfs_compute_reverse_add_bb
50 PARAMS ((depth_first_search_ds, basic_block));
51 static basic_block flow_dfs_compute_reverse_execute
52 PARAMS ((depth_first_search_ds));
53 static void flow_dfs_compute_reverse_finish
54 PARAMS ((depth_first_search_ds));
55 static void remove_fake_successors PARAMS ((basic_block));
56 static bool need_fake_edge_p PARAMS ((rtx));
57 static bool flow_active_insn_p PARAMS ((rtx));
59 /* Like active_insn_p, except keep the return value clobber around
63 flow_active_insn_p (insn)
66 if (active_insn_p (insn))
69 /* A clobber of the function return value exists for buggy
70 programs that fail to return a value. Its effect is to
71 keep the return value from being live across the entire
72 function. If we allow it to be skipped, we introduce the
73 possibility for register livetime aborts. */
74 if (GET_CODE (PATTERN (insn)) == CLOBBER
75 && GET_CODE (XEXP (PATTERN (insn), 0)) == REG
76 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
82 /* Return true if the block has no effect and only forwards control flow to
83 its single destination. */
86 forwarder_block_p (bb)
91 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
92 || !bb->succ || bb->succ->succ_next)
95 for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
96 if (INSN_P (insn) && flow_active_insn_p (insn))
99 return (!INSN_P (insn)
100 || (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn))
101 || !flow_active_insn_p (insn));
104 /* Return nonzero if we can reach target from src by falling through. */
107 can_fallthru (src, target)
108 basic_block src, target;
111 rtx insn2 = target->head;
113 if (src->next_bb != target)
116 if (!active_insn_p (insn2))
117 insn2 = next_active_insn (insn2);
119 /* ??? Later we may add code to move jump tables offline. */
120 return next_active_insn (insn) == insn2;
123 /* Mark the back edges in DFS traversal.
124 Return nonzero if a loop (natural or otherwise) is present.
125 Inspired by Depth_First_Search_PP described in:
127 Advanced Compiler Design and Implementation
129 Morgan Kaufmann, 1997
131 and heavily borrowed from flow_depth_first_order_compute. */
134 mark_dfs_back_edges ()
145 /* Allocate the preorder and postorder number arrays. */
146 pre = (int *) xcalloc (last_basic_block, sizeof (int));
147 post = (int *) xcalloc (last_basic_block, sizeof (int));
149 /* Allocate stack for back-tracking up CFG. */
150 stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
153 /* Allocate bitmap to track nodes that have been visited. */
154 visited = sbitmap_alloc (last_basic_block);
156 /* None of the nodes in the CFG have been visited yet. */
157 sbitmap_zero (visited);
159 /* Push the first edge on to the stack. */
160 stack[sp++] = ENTRY_BLOCK_PTR->succ;
168 /* Look at the edge on the top of the stack. */
172 e->flags &= ~EDGE_DFS_BACK;
174 /* Check if the edge destination has been visited yet. */
175 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
177 /* Mark that we have visited the destination. */
178 SET_BIT (visited, dest->index);
180 pre[dest->index] = prenum++;
183 /* Since the DEST node has been visited for the first
184 time, check its successors. */
185 stack[sp++] = dest->succ;
188 post[dest->index] = postnum++;
192 if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
193 && pre[src->index] >= pre[dest->index]
194 && post[dest->index] == 0)
195 e->flags |= EDGE_DFS_BACK, found = true;
197 if (! e->succ_next && src != ENTRY_BLOCK_PTR)
198 post[src->index] = postnum++;
201 stack[sp - 1] = e->succ_next;
210 sbitmap_free (visited);
215 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
218 set_edge_can_fallthru_flag ()
226 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
227 for (e = bb->succ; e; e = e->succ_next)
228 if (e->flags & EDGE_FALLTHRU)
229 e->flags |= EDGE_CAN_FALLTHRU;
231 /* If the BB ends with an invertable condjump all (2) edges are
232 CAN_FALLTHRU edges. */
233 if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
235 if (!any_condjump_p (bb->end))
237 if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0))
239 invert_jump (bb->end, JUMP_LABEL (bb->end), 0);
240 bb->succ->flags |= EDGE_CAN_FALLTHRU;
241 bb->succ->succ_next->flags |= EDGE_CAN_FALLTHRU;
245 /* Return true if we need to add fake edge to exit.
246 Helper function for the flow_call_edges_add. */
249 need_fake_edge_p (insn)
255 if ((GET_CODE (insn) == CALL_INSN
256 && !SIBLING_CALL_P (insn)
257 && !find_reg_note (insn, REG_NORETURN, NULL)
258 && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
259 && !CONST_OR_PURE_CALL_P (insn)))
262 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
263 && MEM_VOLATILE_P (PATTERN (insn)))
264 || (GET_CODE (PATTERN (insn)) == PARALLEL
265 && asm_noperands (insn) != -1
266 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
267 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
270 /* Add fake edges to the function exit for any non constant and non noreturn
271 calls, volatile inline assembly in the bitmap of blocks specified by
272 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
275 The goal is to expose cases in which entering a basic block does not imply
276 that all subsequent instructions must be executed. */
279 flow_call_edges_add (blocks)
283 int blocks_split = 0;
284 int last_bb = last_basic_block;
285 bool check_last_block = false;
287 if (n_basic_blocks == 0)
291 check_last_block = true;
293 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
295 /* In the last basic block, before epilogue generation, there will be
296 a fallthru edge to EXIT. Special care is required if the last insn
297 of the last basic block is a call because make_edge folds duplicate
298 edges, which would result in the fallthru edge also being marked
299 fake, which would result in the fallthru edge being removed by
300 remove_fake_edges, which would result in an invalid CFG.
302 Moreover, we can't elide the outgoing fake edge, since the block
303 profiler needs to take this into account in order to solve the minimal
304 spanning tree in the case that the call doesn't return.
306 Handle this by adding a dummy instruction in a new last basic block. */
307 if (check_last_block)
309 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
312 /* Back up past insns that must be kept in the same block as a call. */
313 while (insn != bb->head
314 && keep_with_call_p (insn))
315 insn = PREV_INSN (insn);
317 if (need_fake_edge_p (insn))
321 for (e = bb->succ; e; e = e->succ_next)
322 if (e->dest == EXIT_BLOCK_PTR)
325 insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
326 commit_edge_insertions ();
330 /* Now add fake edges to the function exit for any non constant
331 calls since there is no way that we can determine if they will
334 for (i = 0; i < last_bb; i++)
336 basic_block bb = BASIC_BLOCK (i);
343 if (blocks && !TEST_BIT (blocks, i))
346 for (insn = bb->end; ; insn = prev_insn)
348 prev_insn = PREV_INSN (insn);
349 if (need_fake_edge_p (insn))
352 rtx split_at_insn = insn;
354 /* Don't split the block between a call and an insn that should
355 remain in the same block as the call. */
356 if (GET_CODE (insn) == CALL_INSN)
357 while (split_at_insn != bb->end
358 && keep_with_call_p (NEXT_INSN (split_at_insn)))
359 split_at_insn = NEXT_INSN (split_at_insn);
361 /* The handling above of the final block before the epilogue
362 should be enough to verify that there is no edge to the exit
363 block in CFG already. Calling make_edge in such case would
364 cause us to mark that edge as fake and remove it later. */
366 #ifdef ENABLE_CHECKING
367 if (split_at_insn == bb->end)
368 for (e = bb->succ; e; e = e->succ_next)
369 if (e->dest == EXIT_BLOCK_PTR)
373 /* Note that the following may create a new basic block
374 and renumber the existing basic blocks. */
375 if (split_at_insn != bb->end)
377 e = split_block (bb, split_at_insn);
382 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
385 if (insn == bb->head)
396 /* Find unreachable blocks. An unreachable block will have 0 in
397 the reachable bit in block->flags. A nonzero value indicates the
398 block is reachable. */
401 find_unreachable_blocks ()
404 basic_block *tos, *worklist, bb;
407 (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
409 /* Clear all the reachability flags. */
412 bb->flags &= ~BB_REACHABLE;
414 /* Add our starting points to the worklist. Almost always there will
415 be only one. It isn't inconceivable that we might one day directly
416 support Fortran alternate entry points. */
418 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
422 /* Mark the block reachable. */
423 e->dest->flags |= BB_REACHABLE;
426 /* Iterate: find everything reachable from what we've already seen. */
428 while (tos != worklist)
430 basic_block b = *--tos;
432 for (e = b->succ; e; e = e->succ_next)
433 if (!(e->dest->flags & BB_REACHABLE))
436 e->dest->flags |= BB_REACHABLE;
443 /* Functions to access an edge list with a vector representation.
444 Enough data is kept such that given an index number, the
445 pred and succ that edge represents can be determined, or
446 given a pred and a succ, its index number can be returned.
447 This allows algorithms which consume a lot of memory to
448 represent the normally full matrix of edge (pred,succ) with a
449 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
450 wasted space in the client code due to sparse flow graphs. */
452 /* This functions initializes the edge list. Basically the entire
453 flowgraph is processed, and all edges are assigned a number,
454 and the data structure is filled in. */
459 struct edge_list *elist;
465 block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
469 /* Determine the number of edges in the flow graph by counting successor
470 edges on each basic block. */
471 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
473 for (e = bb->succ; e; e = e->succ_next)
477 elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
478 elist->num_blocks = block_count;
479 elist->num_edges = num_edges;
480 elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
484 /* Follow successors of blocks, and register these edges. */
485 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
486 for (e = bb->succ; e; e = e->succ_next)
487 elist->index_to_edge[num_edges++] = e;
492 /* This function free's memory associated with an edge list. */
495 free_edge_list (elist)
496 struct edge_list *elist;
500 free (elist->index_to_edge);
505 /* This function provides debug output showing an edge list. */
508 print_edge_list (f, elist)
510 struct edge_list *elist;
514 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
515 elist->num_blocks - 2, elist->num_edges);
517 for (x = 0; x < elist->num_edges; x++)
519 fprintf (f, " %-4d - edge(", x);
520 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
521 fprintf (f, "entry,");
523 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
525 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
526 fprintf (f, "exit)\n");
528 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
532 /* This function provides an internal consistency check of an edge list,
533 verifying that all edges are present, and that there are no
537 verify_edge_list (f, elist)
539 struct edge_list *elist;
541 int pred, succ, index;
543 basic_block bb, p, s;
545 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
547 for (e = bb->succ; e; e = e->succ_next)
549 pred = e->src->index;
550 succ = e->dest->index;
551 index = EDGE_INDEX (elist, e->src, e->dest);
552 if (index == EDGE_INDEX_NO_EDGE)
554 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
558 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
559 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
560 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
561 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
562 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
563 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
567 /* We've verified that all the edges are in the list, now lets make sure
568 there are no spurious edges in the list. */
570 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
571 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
575 for (e = p->succ; e; e = e->succ_next)
582 for (e = s->pred; e; e = e->pred_next)
589 if (EDGE_INDEX (elist, p, s)
590 == EDGE_INDEX_NO_EDGE && found_edge != 0)
591 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
593 if (EDGE_INDEX (elist, p, s)
594 != EDGE_INDEX_NO_EDGE && found_edge == 0)
595 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
596 p->index, s->index, EDGE_INDEX (elist, p, s));
600 /* This routine will determine what, if any, edge there is between
601 a specified predecessor and successor. */
604 find_edge_index (edge_list, pred, succ)
605 struct edge_list *edge_list;
606 basic_block pred, succ;
610 for (x = 0; x < NUM_EDGES (edge_list); x++)
611 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
612 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
615 return (EDGE_INDEX_NO_EDGE);
618 /* Dump the list of basic blocks in the bitmap NODES. */
621 flow_nodes_print (str, nodes, file)
631 fprintf (file, "%s { ", str);
632 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
636 /* Dump the list of edges in the array EDGE_LIST. */
639 flow_edge_list_print (str, edge_list, num_edges, file)
641 const edge *edge_list;
650 fprintf (file, "%s { ", str);
651 for (i = 0; i < num_edges; i++)
652 fprintf (file, "%d->%d ", edge_list[i]->src->index,
653 edge_list[i]->dest->index);
659 /* This routine will remove any fake successor edges for a basic block.
660 When the edge is removed, it is also removed from whatever predecessor
664 remove_fake_successors (bb)
669 for (e = bb->succ; e;)
674 if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
679 /* This routine will remove all fake edges from the flow graph. If
680 we remove all fake successors, it will automatically remove all
681 fake predecessors. */
688 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
689 remove_fake_successors (bb);
692 /* This function will add a fake edge between any block which has no
693 successors, and the exit block. Some data flow equations require these
697 add_noreturn_fake_exit_edges ()
702 if (bb->succ == NULL)
703 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
706 /* This function adds a fake edge between any infinite loops to the
707 exit block. Some optimizations require a path from each node to
710 See also Morgan, Figure 3.10, pp. 82-83.
712 The current implementation is ugly, not attempting to minimize the
713 number of inserted fake edges. To reduce the number of fake edges
714 to insert, add fake edges from _innermost_ loops containing only
715 nodes not reachable from the exit block. */
718 connect_infinite_loops_to_exit ()
720 basic_block unvisited_block;
721 struct depth_first_search_dsS dfs_ds;
723 /* Perform depth-first search in the reverse graph to find nodes
724 reachable from the exit block. */
725 flow_dfs_compute_reverse_init (&dfs_ds);
726 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
728 /* Repeatedly add fake edges, updating the unreachable nodes. */
731 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
732 if (!unvisited_block)
735 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
736 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
739 flow_dfs_compute_reverse_finish (&dfs_ds);
743 /* Compute reverse top sort order */
746 flow_reverse_top_sort_order_compute (rts_order)
754 /* Allocate stack for back-tracking up CFG. */
755 stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
758 /* Allocate bitmap to track nodes that have been visited. */
759 visited = sbitmap_alloc (last_basic_block);
761 /* None of the nodes in the CFG have been visited yet. */
762 sbitmap_zero (visited);
764 /* Push the first edge on to the stack. */
765 stack[sp++] = ENTRY_BLOCK_PTR->succ;
773 /* Look at the edge on the top of the stack. */
778 /* Check if the edge destination has been visited yet. */
779 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
781 /* Mark that we have visited the destination. */
782 SET_BIT (visited, dest->index);
785 /* Since the DEST node has been visited for the first
786 time, check its successors. */
787 stack[sp++] = dest->succ;
789 rts_order[postnum++] = dest->index;
793 if (! e->succ_next && src != ENTRY_BLOCK_PTR)
794 rts_order[postnum++] = src->index;
797 stack[sp - 1] = e->succ_next;
804 sbitmap_free (visited);
807 /* Compute the depth first search order and store in the array
808 DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
809 RC_ORDER is nonzero, return the reverse completion number for each
810 node. Returns the number of nodes visited. A depth first search
811 tries to get as far away from the starting point as quickly as
815 flow_depth_first_order_compute (dfs_order, rc_order)
822 int rcnum = n_basic_blocks - 1;
825 /* Allocate stack for back-tracking up CFG. */
826 stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
829 /* Allocate bitmap to track nodes that have been visited. */
830 visited = sbitmap_alloc (last_basic_block);
832 /* None of the nodes in the CFG have been visited yet. */
833 sbitmap_zero (visited);
835 /* Push the first edge on to the stack. */
836 stack[sp++] = ENTRY_BLOCK_PTR->succ;
844 /* Look at the edge on the top of the stack. */
849 /* Check if the edge destination has been visited yet. */
850 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
852 /* Mark that we have visited the destination. */
853 SET_BIT (visited, dest->index);
856 dfs_order[dfsnum] = dest->index;
861 /* Since the DEST node has been visited for the first
862 time, check its successors. */
863 stack[sp++] = dest->succ;
865 /* There are no successors for the DEST node so assign
866 its reverse completion number. */
867 rc_order[rcnum--] = dest->index;
871 if (! e->succ_next && src != ENTRY_BLOCK_PTR
873 /* There are no more successors for the SRC node
874 so assign its reverse completion number. */
875 rc_order[rcnum--] = src->index;
878 stack[sp - 1] = e->succ_next;
885 sbitmap_free (visited);
887 /* The number of nodes visited should not be greater than
889 if (dfsnum > n_basic_blocks)
892 /* There are some nodes left in the CFG that are unreachable. */
893 if (dfsnum < n_basic_blocks)
902 struct dfst_node **node;
903 struct dfst_node *up;
906 /* Compute a preorder transversal ordering such that a sub-tree which
907 is the source of a cross edge appears before the sub-tree which is
908 the destination of the cross edge. This allows for easy detection
909 of all the entry blocks for a loop.
911 The ordering is compute by:
913 1) Generating a depth first spanning tree.
915 2) Walking the resulting tree from right to left. */
918 flow_preorder_transversal_compute (pot_order)
927 struct dfst_node *node;
928 struct dfst_node *dfst;
931 /* Allocate stack for back-tracking up CFG. */
932 stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
935 /* Allocate the tree. */
936 dfst = (struct dfst_node *) xcalloc (last_basic_block,
937 sizeof (struct dfst_node));
942 for (e = bb->succ; e; e = e->succ_next)
947 ? (struct dfst_node **) xcalloc (max_successors,
948 sizeof (struct dfst_node *))
952 /* Allocate bitmap to track nodes that have been visited. */
953 visited = sbitmap_alloc (last_basic_block);
955 /* None of the nodes in the CFG have been visited yet. */
956 sbitmap_zero (visited);
958 /* Push the first edge on to the stack. */
959 stack[sp++] = ENTRY_BLOCK_PTR->succ;
966 /* Look at the edge on the top of the stack. */
971 /* Check if the edge destination has been visited yet. */
972 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
974 /* Mark that we have visited the destination. */
975 SET_BIT (visited, dest->index);
977 /* Add the destination to the preorder tree. */
978 if (src != ENTRY_BLOCK_PTR)
980 dfst[src->index].node[dfst[src->index].nnodes++]
981 = &dfst[dest->index];
982 dfst[dest->index].up = &dfst[src->index];
986 /* Since the DEST node has been visited for the first
987 time, check its successors. */
988 stack[sp++] = dest->succ;
991 else if (e->succ_next)
992 stack[sp - 1] = e->succ_next;
998 sbitmap_free (visited);
1000 /* Record the preorder transversal order by
1001 walking the tree from right to left. */
1004 node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
1011 node = node->node[--node->nnodes];
1012 pot_order[i++] = node - dfst;
1018 /* Free the tree. */
1020 for (i = 0; i < last_basic_block; i++)
1022 free (dfst[i].node);
1027 /* Compute the depth first search order on the _reverse_ graph and
1028 store in the array DFS_ORDER, marking the nodes visited in VISITED.
1029 Returns the number of nodes visited.
1031 The computation is split into three pieces:
1033 flow_dfs_compute_reverse_init () creates the necessary data
1036 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1037 structures. The block will start the search.
1039 flow_dfs_compute_reverse_execute () continues (or starts) the
1040 search using the block on the top of the stack, stopping when the
1043 flow_dfs_compute_reverse_finish () destroys the necessary data
1046 Thus, the user will probably call ..._init(), call ..._add_bb() to
1047 add a beginning basic block to the stack, call ..._execute(),
1048 possibly add another bb to the stack and again call ..._execute(),
1049 ..., and finally call _finish(). */
1051 /* Initialize the data structures used for depth-first search on the
1052 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1053 added to the basic block stack. DATA is the current depth-first
1054 search context. If INITIALIZE_STACK is nonzero, there is an
1055 element on the stack. */
1058 flow_dfs_compute_reverse_init (data)
1059 depth_first_search_ds data;
1061 /* Allocate stack for back-tracking up CFG. */
1062 data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
1063 * sizeof (basic_block));
1066 /* Allocate bitmap to track nodes that have been visited. */
1067 data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1069 /* None of the nodes in the CFG have been visited yet. */
1070 sbitmap_zero (data->visited_blocks);
1075 /* Add the specified basic block to the top of the dfs data
1076 structures. When the search continues, it will start at the
1080 flow_dfs_compute_reverse_add_bb (data, bb)
1081 depth_first_search_ds data;
1084 data->stack[data->sp++] = bb;
1085 SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
1088 /* Continue the depth-first search through the reverse graph starting with the
1089 block at the stack's top and ending when the stack is empty. Visited nodes
1090 are marked. Returns an unvisited basic block, or NULL if there is none
1094 flow_dfs_compute_reverse_execute (data)
1095 depth_first_search_ds data;
1100 while (data->sp > 0)
1102 bb = data->stack[--data->sp];
1104 /* Perform depth-first search on adjacent vertices. */
1105 for (e = bb->pred; e; e = e->pred_next)
1106 if (!TEST_BIT (data->visited_blocks,
1107 e->src->index - (INVALID_BLOCK + 1)))
1108 flow_dfs_compute_reverse_add_bb (data, e->src);
1111 /* Determine if there are unvisited basic blocks. */
1112 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
1113 if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
1119 /* Destroy the data structures needed for depth-first search on the
1123 flow_dfs_compute_reverse_finish (data)
1124 depth_first_search_ds data;
1127 sbitmap_free (data->visited_blocks);
1130 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1131 if REVERSE, go against direction of edges. Returns number of blocks
1132 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1134 dfs_enumerate_from (bb, reverse, predicate, rslt, rslt_max, data)
1137 bool (*predicate) (basic_block, void *);
1142 basic_block *st, lbb;
1145 st = xcalloc (rslt_max, sizeof (basic_block));
1146 rslt[tv++] = st[sp++] = bb;
1147 bb->flags |= BB_VISITED;
1154 for (e = lbb->pred; e; e = e->pred_next)
1155 if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
1159 rslt[tv++] = st[sp++] = e->src;
1160 e->src->flags |= BB_VISITED;
1165 for (e = lbb->succ; e; e = e->succ_next)
1166 if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
1170 rslt[tv++] = st[sp++] = e->dest;
1171 e->dest->flags |= BB_VISITED;
1176 for (sp = 0; sp < tv; sp++)
1177 rslt[sp]->flags &= ~BB_VISITED;