summaryrefslogtreecommitdiff
path: root/gcc/cfganal.c
diff options
context:
space:
mode:
authorupstream source tree <ports@midipix.org>2015-03-15 20:14:05 -0400
committerupstream source tree <ports@midipix.org>2015-03-15 20:14:05 -0400
commit554fd8c5195424bdbcabf5de30fdc183aba391bd (patch)
tree976dc5ab7fddf506dadce60ae936f43f58787092 /gcc/cfganal.c
downloadcbb-gcc-4.6.4-554fd8c5195424bdbcabf5de30fdc183aba391bd.tar.bz2
cbb-gcc-4.6.4-554fd8c5195424bdbcabf5de30fdc183aba391bd.tar.xz
obtained gcc-4.6.4.tar.bz2 from upstream website;upstream
verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository.
Diffstat (limited to 'gcc/cfganal.c')
-rw-r--r--gcc/cfganal.c1359
1 files changed, 1359 insertions, 0 deletions
diff --git a/gcc/cfganal.c b/gcc/cfganal.c
new file mode 100644
index 000000000..138ae29d2
--- /dev/null
+++ b/gcc/cfganal.c
@@ -0,0 +1,1359 @@
+/* Control flow graph analysis code for GNU compiler.
+ Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+ 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2010
+ Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+/* This file contains various simple utilities to analyze the CFG. */
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "obstack.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "diagnostic-core.h"
+#include "tm_p.h"
+#include "vec.h"
+#include "vecprim.h"
+#include "bitmap.h"
+#include "sbitmap.h"
+#include "timevar.h"
+
+/* Store the data structures necessary for depth-first search. */
+struct depth_first_search_dsS {
+ /* stack for backtracking during the algorithm */
+ basic_block *stack;
+
+ /* number of edges in the stack. That is, positions 0, ..., sp-1
+ have edges. */
+ unsigned int sp;
+
+ /* record of basic blocks already seen by depth-first search */
+ sbitmap visited_blocks;
+};
+typedef struct depth_first_search_dsS *depth_first_search_ds;
+
+static void flow_dfs_compute_reverse_init (depth_first_search_ds);
+static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
+ basic_block);
+static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
+ basic_block);
+static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
+static bool flow_active_insn_p (const_rtx);
+
+/* Like active_insn_p, except keep the return value clobber around
+ even after reload. */
+
+static bool
+flow_active_insn_p (const_rtx insn)
+{
+ if (active_insn_p (insn))
+ return true;
+
+ /* A clobber of the function return value exists for buggy
+ programs that fail to return a value. Its effect is to
+ keep the return value from being live across the entire
+ function. If we allow it to be skipped, we introduce the
+ possibility for register lifetime confusion. */
+ if (GET_CODE (PATTERN (insn)) == CLOBBER
+ && REG_P (XEXP (PATTERN (insn), 0))
+ && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
+ return true;
+
+ return false;
+}
+
+/* Return true if the block has no effect and only forwards control flow to
+ its single destination. */
+
+bool
+forwarder_block_p (const_basic_block bb)
+{
+ rtx insn;
+
+ if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
+ || !single_succ_p (bb))
+ return false;
+
+ for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
+ if (INSN_P (insn) && flow_active_insn_p (insn))
+ return false;
+
+ return (!INSN_P (insn)
+ || (JUMP_P (insn) && simplejump_p (insn))
+ || !flow_active_insn_p (insn));
+}
+
+/* Return nonzero if we can reach target from src by falling through. */
+
+bool
+can_fallthru (basic_block src, basic_block target)
+{
+ rtx insn = BB_END (src);
+ rtx insn2;
+ edge e;
+ edge_iterator ei;
+
+ if (target == EXIT_BLOCK_PTR)
+ return true;
+ if (src->next_bb != target)
+ return 0;
+ FOR_EACH_EDGE (e, ei, src->succs)
+ if (e->dest == EXIT_BLOCK_PTR
+ && e->flags & EDGE_FALLTHRU)
+ return 0;
+
+ insn2 = BB_HEAD (target);
+ if (insn2 && !active_insn_p (insn2))
+ insn2 = next_active_insn (insn2);
+
+ /* ??? Later we may add code to move jump tables offline. */
+ return next_active_insn (insn) == insn2;
+}
+
+/* Return nonzero if we could reach target from src by falling through,
+ if the target was made adjacent. If we already have a fall-through
+ edge to the exit block, we can't do that. */
+bool
+could_fall_through (basic_block src, basic_block target)
+{
+ edge e;
+ edge_iterator ei;
+
+ if (target == EXIT_BLOCK_PTR)
+ return true;
+ FOR_EACH_EDGE (e, ei, src->succs)
+ if (e->dest == EXIT_BLOCK_PTR
+ && e->flags & EDGE_FALLTHRU)
+ return 0;
+ return true;
+}
+
+/* Mark the back edges in DFS traversal.
+ Return nonzero if a loop (natural or otherwise) is present.
+ Inspired by Depth_First_Search_PP described in:
+
+ Advanced Compiler Design and Implementation
+ Steven Muchnick
+ Morgan Kaufmann, 1997
+
+ and heavily borrowed from pre_and_rev_post_order_compute. */
+
+bool
+mark_dfs_back_edges (void)
+{
+ edge_iterator *stack;
+ int *pre;
+ int *post;
+ int sp;
+ int prenum = 1;
+ int postnum = 1;
+ sbitmap visited;
+ bool found = false;
+
+ /* Allocate the preorder and postorder number arrays. */
+ pre = XCNEWVEC (int, last_basic_block);
+ post = XCNEWVEC (int, last_basic_block);
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
+
+ while (sp)
+ {
+ edge_iterator ei;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
+ ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ pre[dest->index] = prenum++;
+ if (EDGE_COUNT (dest->succs) > 0)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (dest->succs);
+ }
+ else
+ post[dest->index] = postnum++;
+ }
+ else
+ {
+ if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
+ && pre[src->index] >= pre[dest->index]
+ && post[dest->index] == 0)
+ ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
+
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
+ post[src->index] = postnum++;
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
+ else
+ sp--;
+ }
+ }
+
+ free (pre);
+ free (post);
+ free (stack);
+ sbitmap_free (visited);
+
+ return found;
+}
+
+/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
+
+void
+set_edge_can_fallthru_flag (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ e->flags &= ~EDGE_CAN_FALLTHRU;
+
+ /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
+ if (e->flags & EDGE_FALLTHRU)
+ e->flags |= EDGE_CAN_FALLTHRU;
+ }
+
+ /* If the BB ends with an invertible condjump all (2) edges are
+ CAN_FALLTHRU edges. */
+ if (EDGE_COUNT (bb->succs) != 2)
+ continue;
+ if (!any_condjump_p (BB_END (bb)))
+ continue;
+ if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
+ continue;
+ invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
+ EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
+ EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
+ }
+}
+
+/* Find unreachable blocks. An unreachable block will have 0 in
+ the reachable bit in block->flags. A nonzero value indicates the
+ block is reachable. */
+
+void
+find_unreachable_blocks (void)
+{
+ edge e;
+ edge_iterator ei;
+ basic_block *tos, *worklist, bb;
+
+ tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
+
+ /* Clear all the reachability flags. */
+
+ FOR_EACH_BB (bb)
+ bb->flags &= ~BB_REACHABLE;
+
+ /* Add our starting points to the worklist. Almost always there will
+ be only one. It isn't inconceivable that we might one day directly
+ support Fortran alternate entry points. */
+
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ {
+ *tos++ = e->dest;
+
+ /* Mark the block reachable. */
+ e->dest->flags |= BB_REACHABLE;
+ }
+
+ /* Iterate: find everything reachable from what we've already seen. */
+
+ while (tos != worklist)
+ {
+ basic_block b = *--tos;
+
+ FOR_EACH_EDGE (e, ei, b->succs)
+ {
+ basic_block dest = e->dest;
+
+ if (!(dest->flags & BB_REACHABLE))
+ {
+ *tos++ = dest;
+ dest->flags |= BB_REACHABLE;
+ }
+ }
+ }
+
+ free (worklist);
+}
+
+/* Functions to access an edge list with a vector representation.
+ Enough data is kept such that given an index number, the
+ pred and succ that edge represents can be determined, or
+ given a pred and a succ, its index number can be returned.
+ This allows algorithms which consume a lot of memory to
+ represent the normally full matrix of edge (pred,succ) with a
+ single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
+ wasted space in the client code due to sparse flow graphs. */
+
+/* This functions initializes the edge list. Basically the entire
+ flowgraph is processed, and all edges are assigned a number,
+ and the data structure is filled in. */
+
+struct edge_list *
+create_edge_list (void)
+{
+ struct edge_list *elist;
+ edge e;
+ int num_edges;
+ int block_count;
+ basic_block bb;
+ edge_iterator ei;
+
+ block_count = n_basic_blocks; /* Include the entry and exit blocks. */
+
+ num_edges = 0;
+
+ /* Determine the number of edges in the flow graph by counting successor
+ edges on each basic block. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ {
+ num_edges += EDGE_COUNT (bb->succs);
+ }
+
+ elist = XNEW (struct edge_list);
+ elist->num_blocks = block_count;
+ elist->num_edges = num_edges;
+ elist->index_to_edge = XNEWVEC (edge, num_edges);
+
+ num_edges = 0;
+
+ /* Follow successors of blocks, and register these edges. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ elist->index_to_edge[num_edges++] = e;
+
+ return elist;
+}
+
+/* This function free's memory associated with an edge list. */
+
+void
+free_edge_list (struct edge_list *elist)
+{
+ if (elist)
+ {
+ free (elist->index_to_edge);
+ free (elist);
+ }
+}
+
+/* This function provides debug output showing an edge list. */
+
+DEBUG_FUNCTION void
+print_edge_list (FILE *f, struct edge_list *elist)
+{
+ int x;
+
+ fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
+ elist->num_blocks, elist->num_edges);
+
+ for (x = 0; x < elist->num_edges; x++)
+ {
+ fprintf (f, " %-4d - edge(", x);
+ if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
+ fprintf (f, "entry,");
+ else
+ fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
+
+ if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
+ fprintf (f, "exit)\n");
+ else
+ fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
+ }
+}
+
+/* This function provides an internal consistency check of an edge list,
+ verifying that all edges are present, and that there are no
+ extra edges. */
+
+DEBUG_FUNCTION void
+verify_edge_list (FILE *f, struct edge_list *elist)
+{
+ int pred, succ, index;
+ edge e;
+ basic_block bb, p, s;
+ edge_iterator ei;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ pred = e->src->index;
+ succ = e->dest->index;
+ index = EDGE_INDEX (elist, e->src, e->dest);
+ if (index == EDGE_INDEX_NO_EDGE)
+ {
+ fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
+ continue;
+ }
+
+ if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
+ fprintf (f, "*p* Pred for index %d should be %d not %d\n",
+ index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
+ if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
+ fprintf (f, "*p* Succ for index %d should be %d not %d\n",
+ index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
+ }
+ }
+
+ /* We've verified that all the edges are in the list, now lets make sure
+ there are no spurious edges in the list. */
+
+ FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ {
+ int found_edge = 0;
+
+ FOR_EACH_EDGE (e, ei, p->succs)
+ if (e->dest == s)
+ {
+ found_edge = 1;
+ break;
+ }
+
+ FOR_EACH_EDGE (e, ei, s->preds)
+ if (e->src == p)
+ {
+ found_edge = 1;
+ break;
+ }
+
+ if (EDGE_INDEX (elist, p, s)
+ == EDGE_INDEX_NO_EDGE && found_edge != 0)
+ fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
+ p->index, s->index);
+ if (EDGE_INDEX (elist, p, s)
+ != EDGE_INDEX_NO_EDGE && found_edge == 0)
+ fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
+ p->index, s->index, EDGE_INDEX (elist, p, s));
+ }
+}
+
+/* Given PRED and SUCC blocks, return the edge which connects the blocks.
+ If no such edge exists, return NULL. */
+
+edge
+find_edge (basic_block pred, basic_block succ)
+{
+ edge e;
+ edge_iterator ei;
+
+ if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
+ {
+ FOR_EACH_EDGE (e, ei, pred->succs)
+ if (e->dest == succ)
+ return e;
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, succ->preds)
+ if (e->src == pred)
+ return e;
+ }
+
+ return NULL;
+}
+
+/* This routine will determine what, if any, edge there is between
+ a specified predecessor and successor. */
+
+int
+find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
+{
+ int x;
+
+ for (x = 0; x < NUM_EDGES (edge_list); x++)
+ if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
+ && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
+ return x;
+
+ return (EDGE_INDEX_NO_EDGE);
+}
+
+/* Dump the list of basic blocks in the bitmap NODES. */
+
+void
+flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
+{
+ unsigned int node = 0;
+ sbitmap_iterator sbi;
+
+ if (! nodes)
+ return;
+
+ fprintf (file, "%s { ", str);
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
+ fprintf (file, "%d ", node);
+ fputs ("}\n", file);
+}
+
+/* Dump the list of edges in the array EDGE_LIST. */
+
+void
+flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
+{
+ int i;
+
+ if (! edge_list)
+ return;
+
+ fprintf (file, "%s { ", str);
+ for (i = 0; i < num_edges; i++)
+ fprintf (file, "%d->%d ", edge_list[i]->src->index,
+ edge_list[i]->dest->index);
+
+ fputs ("}\n", file);
+}
+
+
+/* This routine will remove any fake predecessor edges for a basic block.
+ When the edge is removed, it is also removed from whatever successor
+ list it is in. */
+
+static void
+remove_fake_predecessors (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
+ {
+ if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
+ remove_edge (e);
+ else
+ ei_next (&ei);
+ }
+}
+
+/* This routine will remove all fake edges from the flow graph. If
+ we remove all fake successors, it will automatically remove all
+ fake predecessors. */
+
+void
+remove_fake_edges (void)
+{
+ basic_block bb;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ remove_fake_predecessors (bb);
+}
+
+/* This routine will remove all fake edges to the EXIT_BLOCK. */
+
+void
+remove_fake_exit_edges (void)
+{
+ remove_fake_predecessors (EXIT_BLOCK_PTR);
+}
+
+
+/* This function will add a fake edge between any block which has no
+ successors, and the exit block. Some data flow equations require these
+ edges to exist. */
+
+void
+add_noreturn_fake_exit_edges (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ if (EDGE_COUNT (bb->succs) == 0)
+ make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+}
+
+/* This function adds a fake edge between any infinite loops to the
+ exit block. Some optimizations require a path from each node to
+ the exit node.
+
+ See also Morgan, Figure 3.10, pp. 82-83.
+
+ The current implementation is ugly, not attempting to minimize the
+ number of inserted fake edges. To reduce the number of fake edges
+ to insert, add fake edges from _innermost_ loops containing only
+ nodes not reachable from the exit block. */
+
+void
+connect_infinite_loops_to_exit (void)
+{
+ basic_block unvisited_block = EXIT_BLOCK_PTR;
+ struct depth_first_search_dsS dfs_ds;
+
+ /* Perform depth-first search in the reverse graph to find nodes
+ reachable from the exit block. */
+ flow_dfs_compute_reverse_init (&dfs_ds);
+ flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
+
+ /* Repeatedly add fake edges, updating the unreachable nodes. */
+ while (1)
+ {
+ unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
+ unvisited_block);
+ if (!unvisited_block)
+ break;
+
+ make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
+ flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
+ }
+
+ flow_dfs_compute_reverse_finish (&dfs_ds);
+ return;
+}
+
+/* Compute reverse top sort order. This is computing a post order
+ numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then then
+ ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
+ true, unreachable blocks are deleted. */
+
+int
+post_order_compute (int *post_order, bool include_entry_exit,
+ bool delete_unreachable)
+{
+ edge_iterator *stack;
+ int sp;
+ int post_order_num = 0;
+ sbitmap visited;
+ int count;
+
+ if (include_entry_exit)
+ post_order[post_order_num++] = EXIT_BLOCK;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
+
+ while (sp)
+ {
+ edge_iterator ei;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ if (EDGE_COUNT (dest->succs) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (dest->succs);
+ else
+ post_order[post_order_num++] = dest->index;
+ }
+ else
+ {
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
+ post_order[post_order_num++] = src->index;
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
+ else
+ sp--;
+ }
+ }
+
+ if (include_entry_exit)
+ {
+ post_order[post_order_num++] = ENTRY_BLOCK;
+ count = post_order_num;
+ }
+ else
+ count = post_order_num + 2;
+
+ /* Delete the unreachable blocks if some were found and we are
+ supposed to do it. */
+ if (delete_unreachable && (count != n_basic_blocks))
+ {
+ basic_block b;
+ basic_block next_bb;
+ for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
+ {
+ next_bb = b->next_bb;
+
+ if (!(TEST_BIT (visited, b->index)))
+ delete_basic_block (b);
+ }
+
+ tidy_fallthru_edges ();
+ }
+
+ free (stack);
+ sbitmap_free (visited);
+ return post_order_num;
+}
+
+
+/* Helper routine for inverted_post_order_compute.
+ BB has to belong to a region of CFG
+ unreachable by inverted traversal from the exit.
+ i.e. there's no control flow path from ENTRY to EXIT
+ that contains this BB.
+ This can happen in two cases - if there's an infinite loop
+ or if there's a block that has no successor
+ (call to a function with no return).
+ Some RTL passes deal with this condition by
+ calling connect_infinite_loops_to_exit () and/or
+ add_noreturn_fake_exit_edges ().
+ However, those methods involve modifying the CFG itself
+ which may not be desirable.
+ Hence, we deal with the infinite loop/no return cases
+ by identifying a unique basic block that can reach all blocks
+ in such a region by inverted traversal.
+ This function returns a basic block that guarantees
+ that all blocks in the region are reachable
+ by starting an inverted traversal from the returned block. */
+
+static basic_block
+dfs_find_deadend (basic_block bb)
+{
+ sbitmap visited = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (visited);
+
+ for (;;)
+ {
+ SET_BIT (visited, bb->index);
+ if (EDGE_COUNT (bb->succs) == 0
+ || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
+ {
+ sbitmap_free (visited);
+ return bb;
+ }
+
+ bb = EDGE_SUCC (bb, 0)->dest;
+ }
+
+ gcc_unreachable ();
+}
+
+
+/* Compute the reverse top sort order of the inverted CFG
+ i.e. starting from the exit block and following the edges backward
+ (from successors to predecessors).
+ This ordering can be used for forward dataflow problems among others.
+
+ This function assumes that all blocks in the CFG are reachable
+ from the ENTRY (but not necessarily from EXIT).
+
+ If there's an infinite loop,
+ a simple inverted traversal starting from the blocks
+ with no successors can't visit all blocks.
+ To solve this problem, we first do inverted traversal
+ starting from the blocks with no successor.
+ And if there's any block left that's not visited by the regular
+ inverted traversal from EXIT,
+ those blocks are in such problematic region.
+ Among those, we find one block that has
+ any visited predecessor (which is an entry into such a region),
+ and start looking for a "dead end" from that block
+ and do another inverted traversal from that block. */
+
+int
+inverted_post_order_compute (int *post_order)
+{
+ basic_block bb;
+ edge_iterator *stack;
+ int sp;
+ int post_order_num = 0;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Put all blocks that have no successor into the initial work list. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ if (EDGE_COUNT (bb->succs) == 0)
+ {
+ /* Push the initial edge on to the stack. */
+ if (EDGE_COUNT (bb->preds) > 0)
+ {
+ stack[sp++] = ei_start (bb->preds);
+ SET_BIT (visited, bb->index);
+ }
+ }
+
+ do
+ {
+ bool has_unvisited_bb = false;
+
+ /* The inverted traversal loop. */
+ while (sp)
+ {
+ edge_iterator ei;
+ basic_block pred;
+
+ /* Look at the edge on the top of the stack. */
+ ei = stack[sp - 1];
+ bb = ei_edge (ei)->dest;
+ pred = ei_edge (ei)->src;
+
+ /* Check if the predecessor has been visited yet. */
+ if (! TEST_BIT (visited, pred->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, pred->index);
+
+ if (EDGE_COUNT (pred->preds) > 0)
+ /* Since the predecessor node has been visited for the first
+ time, check its predecessors. */
+ stack[sp++] = ei_start (pred->preds);
+ else
+ post_order[post_order_num++] = pred->index;
+ }
+ else
+ {
+ if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
+ post_order[post_order_num++] = bb->index;
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
+ else
+ sp--;
+ }
+ }
+
+ /* Detect any infinite loop and activate the kludge.
+ Note that this doesn't check EXIT_BLOCK itself
+ since EXIT_BLOCK is always added after the outer do-while loop. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ if (!TEST_BIT (visited, bb->index))
+ {
+ has_unvisited_bb = true;
+
+ if (EDGE_COUNT (bb->preds) > 0)
+ {
+ edge_iterator ei;
+ edge e;
+ basic_block visited_pred = NULL;
+
+ /* Find an already visited predecessor. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (TEST_BIT (visited, e->src->index))
+ visited_pred = e->src;
+ }
+
+ if (visited_pred)
+ {
+ basic_block be = dfs_find_deadend (bb);
+ gcc_assert (be != NULL);
+ SET_BIT (visited, be->index);
+ stack[sp++] = ei_start (be->preds);
+ break;
+ }
+ }
+ }
+
+ if (has_unvisited_bb && sp == 0)
+ {
+ /* No blocks are reachable from EXIT at all.
+ Find a dead-end from the ENTRY, and restart the iteration. */
+ basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
+ gcc_assert (be != NULL);
+ SET_BIT (visited, be->index);
+ stack[sp++] = ei_start (be->preds);
+ }
+
+ /* The only case the below while fires is
+ when there's an infinite loop. */
+ }
+ while (sp);
+
+ /* EXIT_BLOCK is always included. */
+ post_order[post_order_num++] = EXIT_BLOCK;
+
+ free (stack);
+ sbitmap_free (visited);
+ return post_order_num;
+}
+
+/* Compute the depth first search order and store in the array
+ PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
+ REV_POST_ORDER is nonzero, return the reverse completion number for each
+ node. Returns the number of nodes visited. A depth first search
+ tries to get as far away from the starting point as quickly as
+ possible.
+
+ pre_order is a really a preorder numbering of the graph.
+ rev_post_order is really a reverse postorder numbering of the graph.
+ */
+
+int
+pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
+ bool include_entry_exit)
+{
+ edge_iterator *stack;
+ int sp;
+ int pre_order_num = 0;
+ int rev_post_order_num = n_basic_blocks - 1;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ sp = 0;
+
+ if (include_entry_exit)
+ {
+ if (pre_order)
+ pre_order[pre_order_num] = ENTRY_BLOCK;
+ pre_order_num++;
+ if (rev_post_order)
+ rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
+ }
+ else
+ rev_post_order_num -= NUM_FIXED_BLOCKS;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
+
+ while (sp)
+ {
+ edge_iterator ei;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ if (pre_order)
+ pre_order[pre_order_num] = dest->index;
+
+ pre_order_num++;
+
+ if (EDGE_COUNT (dest->succs) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (dest->succs);
+ else if (rev_post_order)
+ /* There are no successors for the DEST node so assign
+ its reverse completion number. */
+ rev_post_order[rev_post_order_num--] = dest->index;
+ }
+ else
+ {
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
+ && rev_post_order)
+ /* There are no more successors for the SRC node
+ so assign its reverse completion number. */
+ rev_post_order[rev_post_order_num--] = src->index;
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
+ else
+ sp--;
+ }
+ }
+
+ free (stack);
+ sbitmap_free (visited);
+
+ if (include_entry_exit)
+ {
+ if (pre_order)
+ pre_order[pre_order_num] = EXIT_BLOCK;
+ pre_order_num++;
+ if (rev_post_order)
+ rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
+ /* The number of nodes visited should be the number of blocks. */
+ gcc_assert (pre_order_num == n_basic_blocks);
+ }
+ else
+ /* The number of nodes visited should be the number of blocks minus
+ the entry and exit blocks which are not visited here. */
+ gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
+
+ return pre_order_num;
+}
+
+/* Compute the depth first search order on the _reverse_ graph and
+ store in the array DFS_ORDER, marking the nodes visited in VISITED.
+ Returns the number of nodes visited.
+
+ The computation is split into three pieces:
+
+ flow_dfs_compute_reverse_init () creates the necessary data
+ structures.
+
+ flow_dfs_compute_reverse_add_bb () adds a basic block to the data
+ structures. The block will start the search.
+
+ flow_dfs_compute_reverse_execute () continues (or starts) the
+ search using the block on the top of the stack, stopping when the
+ stack is empty.
+
+ flow_dfs_compute_reverse_finish () destroys the necessary data
+ structures.
+
+ Thus, the user will probably call ..._init(), call ..._add_bb() to
+ add a beginning basic block to the stack, call ..._execute(),
+ possibly add another bb to the stack and again call ..._execute(),
+ ..., and finally call _finish(). */
+
+/* Initialize the data structures used for depth-first search on the
+ reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
+ added to the basic block stack. DATA is the current depth-first
+ search context. If INITIALIZE_STACK is nonzero, there is an
+ element on the stack. */
+
+static void
+flow_dfs_compute_reverse_init (depth_first_search_ds data)
+{
+ /* Allocate stack for back-tracking up CFG. */
+ data->stack = XNEWVEC (basic_block, n_basic_blocks);
+ data->sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ data->visited_blocks = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (data->visited_blocks);
+
+ return;
+}
+
+/* Add the specified basic block to the top of the dfs data
+ structures. When the search continues, it will start at the
+ block. */
+
+static void
+flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
+{
+ data->stack[data->sp++] = bb;
+ SET_BIT (data->visited_blocks, bb->index);
+}
+
+/* Continue the depth-first search through the reverse graph starting with the
+ block at the stack's top and ending when the stack is empty. Visited nodes
+ are marked. Returns an unvisited basic block, or NULL if there is none
+ available. */
+
+static basic_block
+flow_dfs_compute_reverse_execute (depth_first_search_ds data,
+ basic_block last_unvisited)
+{
+ basic_block bb;
+ edge e;
+ edge_iterator ei;
+
+ while (data->sp > 0)
+ {
+ bb = data->stack[--data->sp];
+
+ /* Perform depth-first search on adjacent vertices. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!TEST_BIT (data->visited_blocks, e->src->index))
+ flow_dfs_compute_reverse_add_bb (data, e->src);
+ }
+
+ /* Determine if there are unvisited basic blocks. */
+ FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
+ if (!TEST_BIT (data->visited_blocks, bb->index))
+ return bb;
+
+ return NULL;
+}
+
+/* Destroy the data structures needed for depth-first search on the
+ reverse graph. */
+
+static void
+flow_dfs_compute_reverse_finish (depth_first_search_ds data)
+{
+ free (data->stack);
+ sbitmap_free (data->visited_blocks);
+}
+
+/* Performs dfs search from BB over vertices satisfying PREDICATE;
+ if REVERSE, go against direction of edges. Returns number of blocks
+ found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
+int
+dfs_enumerate_from (basic_block bb, int reverse,
+ bool (*predicate) (const_basic_block, const void *),
+ basic_block *rslt, int rslt_max, const void *data)
+{
+ basic_block *st, lbb;
+ int sp = 0, tv = 0;
+ unsigned size;
+
+ /* A bitmap to keep track of visited blocks. Allocating it each time
+ this function is called is not possible, since dfs_enumerate_from
+ is often used on small (almost) disjoint parts of cfg (bodies of
+ loops), and allocating a large sbitmap would lead to quadratic
+ behavior. */
+ static sbitmap visited;
+ static unsigned v_size;
+
+#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
+#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
+#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
+
+ /* Resize the VISITED sbitmap if necessary. */
+ size = last_basic_block;
+ if (size < 10)
+ size = 10;
+
+ if (!visited)
+ {
+
+ visited = sbitmap_alloc (size);
+ sbitmap_zero (visited);
+ v_size = size;
+ }
+ else if (v_size < size)
+ {
+ /* Ensure that we increase the size of the sbitmap exponentially. */
+ if (2 * v_size > size)
+ size = 2 * v_size;
+
+ visited = sbitmap_resize (visited, size, 0);
+ v_size = size;
+ }
+
+ st = XCNEWVEC (basic_block, rslt_max);
+ rslt[tv++] = st[sp++] = bb;
+ MARK_VISITED (bb);
+ while (sp)
+ {
+ edge e;
+ edge_iterator ei;
+ lbb = st[--sp];
+ if (reverse)
+ {
+ FOR_EACH_EDGE (e, ei, lbb->preds)
+ if (!VISITED_P (e->src) && predicate (e->src, data))
+ {
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->src;
+ MARK_VISITED (e->src);
+ }
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, lbb->succs)
+ if (!VISITED_P (e->dest) && predicate (e->dest, data))
+ {
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->dest;
+ MARK_VISITED (e->dest);
+ }
+ }
+ }
+ free (st);
+ for (sp = 0; sp < tv; sp++)
+ UNMARK_VISITED (rslt[sp]);
+ return tv;
+#undef MARK_VISITED
+#undef UNMARK_VISITED
+#undef VISITED_P
+}
+
+
+/* Compute dominance frontiers, ala Harvey, Ferrante, et al.
+
+ This algorithm can be found in Timothy Harvey's PhD thesis, at
+ http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
+ dominance algorithms.
+
+ First, we identify each join point, j (any node with more than one
+ incoming edge is a join point).
+
+ We then examine each predecessor, p, of j and walk up the dominator tree
+ starting at p.
+
+ We stop the walk when we reach j's immediate dominator - j is in the
+ dominance frontier of each of the nodes in the walk, except for j's
+ immediate dominator. Intuitively, all of the rest of j's dominators are
+ shared by j's predecessors as well.
+ Since they dominate j, they will not have j in their dominance frontiers.
+
+ The number of nodes touched by this algorithm is equal to the size
+ of the dominance frontiers, no more, no less.
+*/
+
+
+static void
+compute_dominance_frontiers_1 (bitmap_head *frontiers)
+{
+ edge p;
+ edge_iterator ei;
+ basic_block b;
+ FOR_EACH_BB (b)
+ {
+ if (EDGE_COUNT (b->preds) >= 2)
+ {
+ FOR_EACH_EDGE (p, ei, b->preds)
+ {
+ basic_block runner = p->src;
+ basic_block domsb;
+ if (runner == ENTRY_BLOCK_PTR)
+ continue;
+
+ domsb = get_immediate_dominator (CDI_DOMINATORS, b);
+ while (runner != domsb)
+ {
+ if (!bitmap_set_bit (&frontiers[runner->index],
+ b->index))
+ break;
+ runner = get_immediate_dominator (CDI_DOMINATORS,
+ runner);
+ }
+ }
+ }
+ }
+}
+
+
+void
+compute_dominance_frontiers (bitmap_head *frontiers)
+{
+ timevar_push (TV_DOM_FRONTIERS);
+
+ compute_dominance_frontiers_1 (frontiers);
+
+ timevar_pop (TV_DOM_FRONTIERS);
+}
+
+/* Given a set of blocks with variable definitions (DEF_BLOCKS),
+ return a bitmap with all the blocks in the iterated dominance
+ frontier of the blocks in DEF_BLOCKS. DFS contains dominance
+ frontier information as returned by compute_dominance_frontiers.
+
+ The resulting set of blocks are the potential sites where PHI nodes
+ are needed. The caller is responsible for freeing the memory
+ allocated for the return value. */
+
+bitmap
+compute_idf (bitmap def_blocks, bitmap_head *dfs)
+{
+ bitmap_iterator bi;
+ unsigned bb_index, i;
+ VEC(int,heap) *work_stack;
+ bitmap phi_insertion_points;
+
+ work_stack = VEC_alloc (int, heap, n_basic_blocks);
+ phi_insertion_points = BITMAP_ALLOC (NULL);
+
+ /* Seed the work list with all the blocks in DEF_BLOCKS. We use
+ VEC_quick_push here for speed. This is safe because we know that
+ the number of definition blocks is no greater than the number of
+ basic blocks, which is the initial capacity of WORK_STACK. */
+ EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
+ VEC_quick_push (int, work_stack, bb_index);
+
+ /* Pop a block off the worklist, add every block that appears in
+ the original block's DF that we have not already processed to
+ the worklist. Iterate until the worklist is empty. Blocks
+ which are added to the worklist are potential sites for
+ PHI nodes. */
+ while (VEC_length (int, work_stack) > 0)
+ {
+ bb_index = VEC_pop (int, work_stack);
+
+ /* Since the registration of NEW -> OLD name mappings is done
+ separately from the call to update_ssa, when updating the SSA
+ form, the basic blocks where new and/or old names are defined
+ may have disappeared by CFG cleanup calls. In this case,
+ we may pull a non-existing block from the work stack. */
+ gcc_assert (bb_index < (unsigned) last_basic_block);
+
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
+ 0, i, bi)
+ {
+ /* Use a safe push because if there is a definition of VAR
+ in every basic block, then WORK_STACK may eventually have
+ more than N_BASIC_BLOCK entries. */
+ VEC_safe_push (int, heap, work_stack, i);
+ bitmap_set_bit (phi_insertion_points, i);
+ }
+ }
+
+ VEC_free (int, heap, work_stack);
+
+ return phi_insertion_points;
+}
+
+