[mem-ssa] Merge 1/4: Cosmetic DCE changes

[Diego Novillo <dnovillo at redhat dot com>]

This patch reorders the functions in tree-ssa-dce.c so that they don't
need to be forward declared.  No functional changes, but needs to be
included with the rest because it uses the new virtual operator
interface.


2006-12-06  Diego Novillo  <dnovillo@redhat.com>

	* tree-ssa-dce.c: Remove forward declarations for static
	functions.  Re-arrange functions bodies as needed.
	(find_obviously_necessary_stmts): Never mark PHI nodes as
	obviously necessary.
	(mark_operand_necessary): Remove argument PHIONLY.  Update
	users.

Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c	(revision 119149)
+++ tree-ssa-dce.c	(working copy)
@@ -112,30 +112,7 @@ static bool cfg_altered;
  EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,	\
			    (EDGE_NUMBER), (BI))

-/* Local function prototypes.  */
-static inline void set_control_dependence_map_bit (basic_block, int);
-static inline void clear_control_dependence_bitmap (basic_block);
-static void find_all_control_dependences (struct edge_list *);
-static void find_control_dependence (struct edge_list *, int);
-static inline basic_block find_pdom (basic_block);
-
-static inline void mark_stmt_necessary (tree, bool);
-static inline void mark_operand_necessary (tree, bool);
-
-static void mark_stmt_if_obviously_necessary (tree, bool);
-static void find_obviously_necessary_stmts (struct edge_list *);

-static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
-static void propagate_necessity (struct edge_list *);
-
-static void eliminate_unnecessary_stmts (void);
-static void remove_dead_phis (basic_block);
-static void remove_dead_stmt (block_stmt_iterator *, basic_block);
-
-static void print_stats (void);
-static void tree_dce_init (bool);
-static void tree_dce_done (bool);
-
/* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
static inline void
set_control_dependence_map_bit (basic_block bb, int edge_index)
@@ -153,18 +130,27 @@ clear_control_dependence_bitmap (basic_b
  bitmap_clear (control_dependence_map[bb->index]);
}

-/* Record all blocks' control dependences on all edges in the edge
-   list EL, ala Morgan, Section 3.6.  */

-static void
-find_all_control_dependences (struct edge_list *el)
+/* 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)
{
-  int i;
+  gcc_assert (block != ENTRY_BLOCK_PTR);

-  for (i = 0; i < NUM_EDGES (el); ++i)
-    find_control_dependence (el, i);
+  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.  */

@@ -197,25 +183,20 @@ find_control_dependence (struct edge_lis
    }
}

-/* 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)
+/* Record all blocks' control dependences on all edges in the edge
+   list EL, ala Morgan, Section 3.6.  */
+
+static void
+find_all_control_dependences (struct edge_list *el)
{
-  gcc_assert (block != ENTRY_BLOCK_PTR);
+  int i;

-  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;
-    }
+  for (i = 0; i < NUM_EDGES (el); ++i)
+    find_control_dependence (el, i);
}
-
+
+
#define NECESSARY(stmt)		stmt->common.asm_written_flag

/* If STMT is not already marked necessary, mark it, and add it to the
@@ -241,11 +222,11 @@ mark_stmt_necessary (tree stmt, bool add
    VEC_safe_push (tree, heap, worklist, stmt);
}

-/* Mark the statement defining operand OP as necessary.  PHIONLY is true
-   if we should only mark it necessary if it is a phi node.  */
+
+/* Mark the statement defining operand OP as necessary.  */

static inline void
-mark_operand_necessary (tree op, bool phionly)
+mark_operand_necessary (tree op)
{
  tree stmt;
  int ver;
@@ -260,15 +241,13 @@ mark_operand_necessary (tree op, bool ph
  stmt = SSA_NAME_DEF_STMT (op);
  gcc_assert (stmt);

-  if (NECESSARY (stmt)
-      || IS_EMPTY_STMT (stmt)
-      || (phionly && TREE_CODE (stmt) != PHI_NODE))
+  if (NECESSARY (stmt) || IS_EMPTY_STMT (stmt))
    return;

  NECESSARY (stmt) = 1;
  VEC_safe_push (tree, heap, worklist, stmt);
}
-
+

/* Mark STMT as necessary if it obviously is.  Add it to the worklist if
   it can make other statements necessary.
@@ -374,7 +353,38 @@ mark_stmt_if_obviously_necessary (tree s

  return;
}
-
+
+
+/* Make corresponding control dependent edges necessary.  We only
+   have to do this once for each basic block, so we clear the bitmap
+   after we're done.  */
+static void
+mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
+{
+  bitmap_iterator bi;
+  unsigned edge_number;
+
+  gcc_assert (bb != EXIT_BLOCK_PTR);
+
+  if (bb == ENTRY_BLOCK_PTR)
+    return;
+
+  EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
+    {
+      tree t;
+      basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
+
+      if (TEST_BIT (last_stmt_necessary, cd_bb->index))
+	continue;
+      SET_BIT (last_stmt_necessary, cd_bb->index);
+
+      t = last_stmt (cd_bb);
+      if (t && is_ctrl_stmt (t))
+	mark_stmt_necessary (t, true);
+    }
+}
+
+
/* Find obviously necessary statements.  These are things like most function
   calls, and stores to file level variables.

@@ -393,21 +403,9 @@ find_obviously_necessary_stmts (struct e
    {
      tree phi;

-      /* Check any PHI nodes in the block.  */
+      /* PHI nodes are never inherently necessary.  */
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-	{
-	  NECESSARY (phi) = 0;
-
-	  /* PHIs for virtual variables do not directly affect code
-	     generation and need not be considered inherently necessary
-	     regardless of the bits set in their decl.
-
-	     Thus, we only need to mark PHIs for real variables which
-	     need their result preserved as being inherently necessary.  */
-	  if (is_gimple_reg (PHI_RESULT (phi))
-	      && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
-	    mark_stmt_necessary (phi, true);
-        }
+	NECESSARY (phi) = 0;

      /* Check all statements in the block.  */
      for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
@@ -431,46 +429,19 @@ find_obviously_necessary_stmts (struct e
	}
    }
}
-
-/* Make corresponding control dependent edges necessary.  We only
-   have to do this once for each basic block, so we clear the bitmap
-   after we're done.  */
-static void
-mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
-{
-  bitmap_iterator bi;
-  unsigned edge_number;
-
-  gcc_assert (bb != EXIT_BLOCK_PTR);
-
-  if (bb == ENTRY_BLOCK_PTR)
-    return;
-
-  EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
-    {
-      tree t;
-      basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);

-      if (TEST_BIT (last_stmt_necessary, cd_bb->index))
-	continue;
-      SET_BIT (last_stmt_necessary, cd_bb->index);

-      t = last_stmt (cd_bb);
-      if (t && is_ctrl_stmt (t))
-	mark_stmt_necessary (t, true);
-    }
-}
-
-/* Propagate necessity using the operands of necessary statements.  Process
-   the uses on each statement in the worklist, and add all feeding statements
-   which contribute to the calculation of this value to the worklist.
+/* Propagate necessity using the operands of necessary statements.
+   Process the uses on each statement in the worklist, and add all
+   feeding statements which contribute to the calculation of this
+   value to the worklist. 

   In conservative mode, EL is NULL.  */

static void
propagate_necessity (struct edge_list *el)
{
-  tree i;
+  tree stmt;
  bool aggressive = (el ? true : false); 

  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -478,22 +449,22 @@ propagate_necessity (struct edge_list *e

  while (VEC_length (tree, worklist) > 0)
    {
-      /* Take `i' from worklist.  */
-      i = VEC_pop (tree, worklist);
+      /* Take STMT from worklist.  */
+      stmt = VEC_pop (tree, worklist);

      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "processing: ");
-	  print_generic_stmt (dump_file, i, TDF_SLIM);
+	  print_generic_stmt (dump_file, stmt, TDF_SLIM);
	  fprintf (dump_file, "\n");
	}

      if (aggressive)
	{
	  /* Mark the last statements of the basic blocks that the block
-	     containing `i' is control dependent on, but only if we haven't
+	     containing STMT is control dependent on, but only if we haven't
	     already done so.  */
-	  basic_block bb = bb_for_stmt (i);
+	  basic_block bb = bb_for_stmt (stmt);
	  if (bb != ENTRY_BLOCK_PTR
	      && ! TEST_BIT (visited_control_parents, bb->index))
	    {
@@ -502,7 +473,7 @@ propagate_necessity (struct edge_list *e
	    }
	}

-      if (TREE_CODE (i) == PHI_NODE)
+      if (TREE_CODE (stmt) == PHI_NODE)
	{
	  /* PHI nodes are somewhat special in that each PHI alternative has
	     data and control dependencies.  All the statements feeding the
@@ -511,18 +482,19 @@ propagate_necessity (struct edge_list *e
	     predecessor block associated with each PHI alternative as
	     necessary.  */
	  int k;
-	  for (k = 0; k < PHI_NUM_ARGS (i); k++)
+
+	  for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
            {
-	      tree arg = PHI_ARG_DEF (i, k);
+	      tree arg = PHI_ARG_DEF (stmt, k);
	      if (TREE_CODE (arg) == SSA_NAME)
-		mark_operand_necessary (arg, false);
+		mark_operand_necessary (arg);
	    }

	  if (aggressive)
	    {
-	      for (k = 0; k < PHI_NUM_ARGS (i); k++)
+	      for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
		{
-		  basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
+		  basic_block arg_bb = PHI_ARG_EDGE (stmt, k)->src;
		  if (arg_bb != ENTRY_BLOCK_PTR
		      && ! TEST_BIT (visited_control_parents, arg_bb->index))
		    {
@@ -535,131 +507,22 @@ propagate_necessity (struct edge_list *e
      else
	{
	  /* Propagate through the operands.  Examine all the USE, VUSE and
-	     V_MAY_DEF operands in this statement.  Mark all the statements 
-	     which feed this statement's uses as necessary.  */
-	  ssa_op_iter iter;
-	  tree use;
-
-	  /* The operands of V_MAY_DEF expressions are also needed as they
+	     VDEF operands in this statement.  Mark all the statements 
+	     which feed this statement's uses as necessary.  The
+	     operands of VDEF expressions are also needed as they
	     represent potential definitions that may reach this
-	     statement (V_MAY_DEF operands allow us to follow def-def 
+	     statement (VDEF operands allow us to follow def-def
	     links).  */
+	  ssa_op_iter iter;
+	  tree use;

-	  FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES)
-	    mark_operand_necessary (use, false);
-	}
-    }
-}
-
-
-/* Propagate necessity around virtual phi nodes used in kill operands.
-   The reason this isn't done during propagate_necessity is because we don't
-   want to keep phis around that are just there for must-defs, unless we
-   absolutely have to.  After we've rewritten the reaching definitions to be
-   correct in the previous part of the fixup routine, we can simply propagate
-   around the information about which of these virtual phi nodes are really
-   used, and set the NECESSARY flag accordingly.
-   Note that we do the minimum here to ensure that we keep alive the phis that
-   are actually used in the corrected SSA form.  In particular, some of these
-   phis may now have all of the same operand, and will be deleted by some
-   other pass.  */
-
-static void
-mark_really_necessary_kill_operand_phis (void)
-{
-  basic_block bb;
-  int i;
-
-  /* Seed the worklist with the new virtual phi arguments and virtual
-     uses */
-  FOR_EACH_BB (bb)
-    {
-      block_stmt_iterator bsi;
-      tree phi;
-      
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-	{
-	  if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi))
-	    {
-	      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
-		mark_operand_necessary (PHI_ARG_DEF (phi, i), true);
-	    }
-	}
-      
-      for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
-	{
-	  tree stmt = bsi_stmt (bsi);
-	
-	  if (NECESSARY (stmt))
-	    {
-	      use_operand_p use_p;
-	      ssa_op_iter iter;
-	      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
-					SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
-		{
-		  tree use = USE_FROM_PTR (use_p);
-		  mark_operand_necessary (use, true);
-		}
-	    }
+	  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
+	    mark_operand_necessary (use);
	}
    }
-  
-  /* Mark all virtual phis still in use as necessary, and all of their
-     arguments that are phis as necessary.  */
-  while (VEC_length (tree, worklist) > 0)
-    {
-      tree use = VEC_pop (tree, worklist);
-      
-      for (i = 0; i < PHI_NUM_ARGS (use); i++)
-	mark_operand_necessary (PHI_ARG_DEF (use, i), true);
-    }
}


-
-
-/* Eliminate unnecessary statements. Any instruction not marked as necessary
-   contributes nothing to the program, and can be deleted.  */
-
-static void
-eliminate_unnecessary_stmts (void)
-{
-  basic_block bb;
-  block_stmt_iterator i;
-
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "\nEliminating unnecessary statements:\n");
-  
-  clear_special_calls ();
-  FOR_EACH_BB (bb)
-    {
-      /* Remove dead PHI nodes.  */
-      remove_dead_phis (bb);
-    }
-
-  FOR_EACH_BB (bb)
-    {
-      /* Remove dead statements.  */
-      for (i = bsi_start (bb); ! bsi_end_p (i) ; )
-	{
-         tree t = bsi_stmt (i);
-
-         stats.total++;
-
-         /* If `i' is not necessary then remove it.  */
-         if (! NECESSARY (t))
-           remove_dead_stmt (&i, bb);
-         else
-           {
-             tree call = get_call_expr_in (t);
-             if (call)
-               notice_special_calls (call);
-             bsi_next (&i);
-           }
-	}
-    }
- }
-
/* Remove dead PHI nodes from block BB.  */

static void
@@ -684,7 +547,7 @@ remove_dead_phis (basic_block bb)
	      fprintf (dump_file, "\n");
	    }

-	  remove_phi_node (phi, prev);
+	  remove_phi_node (phi, prev, true);
	  stats.removed_phis++;
	  phi = next;
	}
@@ -695,7 +558,8 @@ remove_dead_phis (basic_block bb)
	}
    }
}
-
+
+
/* Remove dead statement pointed to by iterator I.  Receives the basic block BB
   containing I so that we don't have to look it up.  */

@@ -703,9 +567,6 @@ static void
remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
{
  tree t = bsi_stmt (*i);
-  def_operand_p def_p;
-
-  ssa_op_iter iter;

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
@@ -780,15 +641,54 @@ remove_dead_stmt (block_stmt_iterator *i
	}
    }
  
-  FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS)
-    {
-      tree def = DEF_FROM_PTR (def_p);
-      mark_sym_for_renaming (SSA_NAME_VAR (def));
-    }
  bsi_remove (i, true);  
  release_defs (t); 
}
-
+
+
+/* Eliminate unnecessary statements. Any instruction not marked as necessary
+   contributes nothing to the program, and can be deleted.  */
+
+static void
+eliminate_unnecessary_stmts (void)
+{
+  basic_block bb;
+  block_stmt_iterator i;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\nEliminating unnecessary statements:\n");
+
+  clear_special_calls ();
+  FOR_EACH_BB (bb)
+    {
+      /* Remove dead PHI nodes.  */
+      remove_dead_phis (bb);
+    }
+
+  FOR_EACH_BB (bb)
+    {
+      /* Remove dead statements.  */
+      for (i = bsi_start (bb); ! bsi_end_p (i) ; )
+	{
+	  tree t = bsi_stmt (i);
+
+	  stats.total++;
+
+	  /* If `i' is not necessary then remove it.  */
+	  if (! NECESSARY (t))
+	    remove_dead_stmt (&i, bb);
+	  else
+	    {
+	      tree call = get_call_expr_in (t);
+	      if (call)
+		notice_special_calls (call);
+	      bsi_next (&i);
+	    }
+	}
+    }
+}
+
+
/* Print out removed statement statistics.  */

static void
@@ -900,7 +800,6 @@ perform_tree_ssa_dce (bool aggressive)

  propagate_necessity (el);

-  mark_really_necessary_kill_operand_phis ();
  eliminate_unnecessary_stmts ();

  if (aggressive)