basic-block.h (class control_dependences): New.

2013-09-06  Richard Biener  <rguenther@suse.de>

	* basic-block.h (class control_dependences): New.
	* tree-ssa-dce.c (control_dependence_map): Remove.
	(cd): New global.
	(EXECUTE_IF_CONTROL_DEPENDENT): Remove.
	(set_control_dependence_map_bit, clear_control_dependence_bitmap,
	find_pdom, find_control_dependence, find_all_control_dependences):
	Move to cfganal.c.
	(mark_control_dependent_edges_necessary, find_obviously_necessary_stmts,
	propagate_necessity, tree_dce_init, tree_dce_done,
	perform_tree_ssa_dce): Adjust.
	* cfganal.c (set_control_dependence_map_bit,
	clear_control_dependence_bitmap, find_pdom, find_control_dependence,
	find_all_control_dependences): Move from tree-ssa-dce.c and
	implement as methods of control_dependences class.
	(control_dependences::control_dependences): New.
	(control_dependences::~control_dependences): Likewise.
	(control_dependences::get_edges_dependent_on): Likewise.
	(control_dependences::get_edge): Likewise.

From-SVN: r202309

1 files changed, 114 insertions, 0 deletions

diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index 63d17cede2b..8a04f03ea1b 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -340,6 +340,120 @@ verify_edge_list (FILE *f, struct edge_list *elist)
       }
 }
 
+
+/* Functions to compute control dependences.  */
+
+/* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
+void
+control_dependences::set_control_dependence_map_bit (basic_block bb,
+						     int edge_index)
+{
+  if (bb == ENTRY_BLOCK_PTR)
+    return;
+  gcc_assert (bb != EXIT_BLOCK_PTR);
+  bitmap_set_bit (control_dependence_map[bb->index], edge_index);
+}
+
+/* Clear all control dependences for block BB.  */
+void
+control_dependences::clear_control_dependence_bitmap (basic_block bb)
+{
+  bitmap_clear (control_dependence_map[bb->index]);
+}
+
+/* Find the immediate postdominator PDOM of the specified basic block BLOCK.
+   This function is necessary because some blocks have negative numbers.  */
+
+static inline basic_block
+find_pdom (basic_block block)
+{
+  gcc_assert (block != ENTRY_BLOCK_PTR);
+
+  if (block == EXIT_BLOCK_PTR)
+    return EXIT_BLOCK_PTR;
+  else
+    {
+      basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
+      if (! bb)
+	return EXIT_BLOCK_PTR;
+      return bb;
+    }
+}
+
+/* Determine all blocks' control dependences on the given edge with edge_list
+   EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
+
+void
+control_dependences::find_control_dependence (int edge_index)
+{
+  basic_block current_block;
+  basic_block ending_block;
+
+  gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
+
+  if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
+    ending_block = single_succ (ENTRY_BLOCK_PTR);
+  else
+    ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
+
+  for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
+       current_block != ending_block && current_block != EXIT_BLOCK_PTR;
+       current_block = find_pdom (current_block))
+    {
+      edge e = INDEX_EDGE (el, edge_index);
+
+      /* For abnormal edges, we don't make current_block control
+	 dependent because instructions that throw are always necessary
+	 anyway.  */
+      if (e->flags & EDGE_ABNORMAL)
+	continue;
+
+      set_control_dependence_map_bit (current_block, edge_index);
+    }
+}
+
+/* Record all blocks' control dependences on all edges in the edge
+   list EL, ala Morgan, Section 3.6.  */
+
+control_dependences::control_dependences (struct edge_list *edges)
+  : el (edges)
+{
+  timevar_push (TV_CONTROL_DEPENDENCES);
+  control_dependence_map.create (last_basic_block);
+  for (int i = 0; i < last_basic_block; ++i)
+    control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
+  for (int i = 0; i < NUM_EDGES (el); ++i)
+    find_control_dependence (i);
+  timevar_pop (TV_CONTROL_DEPENDENCES);
+}
+
+/* Free control dependences and the associated edge list.  */
+
+control_dependences::~control_dependences ()
+{
+  for (int i = 0; i < last_basic_block; ++i)
+    BITMAP_FREE (control_dependence_map[i]);
+  control_dependence_map.release ();
+  free_edge_list (el);
+}
+
+/* Returns the bitmap of edges the basic-block I is dependent on.  */
+
+bitmap
+control_dependences::get_edges_dependent_on (int i)
+{
+  return control_dependence_map[i];
+}
+
+/* Returns the edge with index I from the edge list.  */
+
+edge
+control_dependences::get_edge (int i)
+{
+  return INDEX_EDGE (el, i);
+}
+
+
 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
    If no such edge exists, return NULL.  */