CbC/CbC_gcc: gcc/cfganal.c comparison

comparison gcc/cfganal.c @ 0:a06113de4d67

first commit

author	kent <kent@cr.ie.u-ryukyu.ac.jp>
date	Fri, 17 Jul 2009 14:47:48 +0900
parents
children	77e2b8dfacca

comparison

equal deleted inserted replaced

--1:000000000000
+:a06113de4d67
+/* 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
+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 "toplev.h"
+#include "tm_p.h"
+#include "vec.h"
+#include "vecprim.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.  */
+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.  */
+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 *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_bit_p (frontiers[runner->index], b->index))
+		    break;
+		  bitmap_set_bit (frontiers[runner->index],
+				  b->index);
+		  runner = get_immediate_dominator (CDI_DOMINATORS,
+						    runner);
+		}
+	    }
+	}
+}
+}
+void
+compute_dominance_frontiers (bitmap *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 *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;
+}

Mercurial > hg > CbC > CbC_gcc

comparison gcc/cfganal.c @ 0:a06113de4d67