This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] Supefluous phi removal


Hello,

this patch adds cleanup of the redundant phis.  It mostly aims for
removing of degenerate phi nodes in basic blocks with just one entry
edge, but it of course catches also cases when phi nodes with more
arguments become redundant due to removal of definitions.

Bootstrapped and regtested on i686.  Compile time impact is not
measurable (within bounds of measurement error).

Zdenek

	* tree-dfa.c (free_df_for_stmt, free_df): New functions.
	(compute_immediate_uses_for_stmt): Record uses in VDEFs.
	* tree-flow.h (free_df, kill_redundant_phi_nodes): Declare.
	* tree-optimize.c (optimize_function_tree): Call
	kill_redundant_phi_nodes.
	* tree-ssa-ccp.c (finalize): Call free_df.
	* tree-ssa.c (replace_immediate_uses, raise_value,
	kill_redundant_phi_nodes): New functions.
	* testsuite/gcc.dg/tree-ssa/20030709-2.c: Update outcome.

Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.206
diff -c -3 -p -r1.1.4.206 tree-dfa.c
*** tree-dfa.c	20 Dec 2003 01:39:14 -0000	1.1.4.206
--- tree-dfa.c	5 Jan 2004 10:37:19 -0000
*************** compute_immediate_uses (int flags, bool 
*** 286,291 ****
--- 286,325 ----
      }
  }
  
+ /* Invalidates dataflow information for a statement STMT.  */
+ 
+ static void
+ free_df_for_stmt (tree stmt)
+ {
+   stmt_ann_t ann = stmt_ann (stmt);
+ 
+   if (ann)
+     ann->df = NULL;
+ }
+ 
+ /* Invalidates dataflow information.  */
+ 
+ void
+ free_df (void)
+ {
+   basic_block bb;
+   block_stmt_iterator si;
+ 
+   FOR_EACH_BB (bb)
+     {
+       tree phi;
+ 
+       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 	free_df_for_stmt (phi);
+ 
+       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+         {
+ 	  tree stmt = bsi_stmt (si);
+ 	  free_df_for_stmt (stmt);
+ 	}
+     }
+ }
+ 
  /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
     operands in phi node PHI and add a def-use edge between their
     defining statement and PHI.
*************** compute_immediate_uses_for_stmt (tree st
*** 326,331 ****
--- 360,366 ----
    size_t i;
    use_optype uses;
    vuse_optype vuses;
+   vdef_optype vdefs;
    stmt_ann_t ann;
  
    /* PHI nodes are handled elsewhere.  */
*************** compute_immediate_uses_for_stmt (tree st
*** 354,359 ****
--- 389,403 ----
        for (i = 0; i < NUM_VUSES (vuses); i++)
  	{
  	  tree vuse = VUSE_OP (vuses, i);
+ 	  tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
+ 	  if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
+ 	    add_immediate_use (imm_rdef_stmt, stmt);
+ 	}
+ 
+       vdefs = VDEF_OPS (ann);
+       for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ 	{
+ 	  tree vuse = VDEF_OP (vdefs, i);
  	  tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
  	  if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
  	    add_immediate_use (imm_rdef_stmt, stmt);
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177
diff -c -3 -p -r1.1.4.177 tree-flow.h
*** tree-flow.h	26 Dec 2003 22:38:28 -0000	1.1.4.177
--- tree-flow.h	5 Jan 2004 10:37:19 -0000
*************** extern tree *find_decl_location (tree, t
*** 459,464 ****
--- 459,465 ----
  extern void compute_may_aliases (tree);
  extern void compute_reached_uses (int);
  extern void compute_immediate_uses (int, bool (*)(tree));
+ extern void free_df (void);
  extern void compute_reaching_defs (int);
  extern void dump_alias_info (FILE *);
  extern void debug_alias_info (void);
*************** extern bool tree_ssa_useless_type_conver
*** 500,505 ****
--- 501,507 ----
  extern void verify_ssa (void);
  extern void delete_tree_ssa (void);
  extern unsigned int highest_ssa_version;
+ extern void kill_redundant_phi_nodes (void);
  
  /* In tree-ssa-pre.c  */
  extern void tree_perform_ssapre (tree, enum tree_dump_index);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.101
diff -c -3 -p -r1.1.4.101 tree-optimize.c
*** tree-optimize.c	4 Jan 2004 15:48:30 -0000	1.1.4.101
--- tree-optimize.c	5 Jan 2004 10:37:19 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 120,125 ****
--- 120,126 ----
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
  
+ 	  kill_redundant_phi_nodes ();
  #ifdef ENABLE_CHECKING
  	  verify_ssa ();
  #endif
*************** optimize_function_tree (tree fndecl, tre
*** 196,201 ****
--- 197,203 ----
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_5);
            ggc_collect ();
  
+ 	  kill_redundant_phi_nodes ();
  #ifdef ENABLE_CHECKING
  	  verify_ssa ();
  #endif
*************** optimize_function_tree (tree fndecl, tre
*** 222,227 ****
--- 224,230 ----
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_6);
  
+ 	  kill_redundant_phi_nodes ();
  #ifdef ENABLE_CHECKING
  	  verify_ssa ();
  #endif
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.128
diff -c -3 -p -r1.1.2.128 tree-ssa-ccp.c
*** tree-ssa-ccp.c	21 Dec 2003 12:24:36 -0000	1.1.2.128
--- tree-ssa-ccp.c	5 Jan 2004 10:37:19 -0000
*************** finalize (void)
*** 1171,1176 ****
--- 1171,1177 ----
    free (value_vector);
    sbitmap_free (bb_in_list);
    sbitmap_free (executable_blocks);
+   free_df ();
  }
  
  /* Is the block worklist empty.  */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.180
diff -c -3 -p -r1.1.4.180 tree-ssa.c
*** tree-ssa.c	19 Dec 2003 07:01:36 -0000	1.1.4.180
--- tree-ssa.c	5 Jan 2004 10:37:19 -0000
*************** tree_ssa_useless_type_conversion (tree e
*** 3575,3578 ****
--- 3575,3761 ----
    return false;
  }
  
+ /* Replaces immediate uses of VAR by REPL.  */
+ 
+ static void
+ replace_immediate_uses (tree var, tree repl)
+ {
+   use_optype uses;
+   vuse_optype vuses;
+   vdef_optype vdefs;
+   int i, j, n;
+   dataflow_t df;
+   tree stmt;
+ 
+   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
+   n = num_immediate_uses (df);
+ 
+   for (i = 0; i < n; i++)
+     {
+       stmt = immediate_use (df, i);
+ 
+       if (TREE_CODE (stmt) == PHI_NODE)
+ 	{
+ 	  for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
+ 	    if (PHI_ARG_DEF (stmt, j) == var)
+ 	      {
+ 		PHI_ARG_DEF (stmt, j) = repl;
+ 		if (TREE_CODE (repl) == SSA_NAME
+ 		    && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
+ 		  SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
+ 	      }
+ 
+ 	  continue;
+ 	}
+ 
+       get_stmt_operands (stmt);
+       if (is_gimple_reg (SSA_NAME_VAR (var)))
+ 	{
+ 	  uses = STMT_USE_OPS (stmt);
+ 	  for (j = 0; j < (int) NUM_USES (uses); j++)
+ 	    if (USE_OP (uses, j) == var)
+ 	      *USE_OP_PTR (uses, j) = repl;
+ 	}
+       else
+       	{
+ 	  vuses = STMT_VUSE_OPS (stmt);
+ 	  for (j = 0; j < (int) NUM_VUSES (vuses); j++)
+ 	    if (VUSE_OP (vuses, j) == var)
+ 	      *VUSE_OP_PTR (vuses, j) = repl;
+ 
+ 	  vdefs = STMT_VDEF_OPS (stmt);
+ 	  for (j = 0; j < (int) NUM_VDEFS (vdefs); j++)
+ 	    if (VDEF_OP (vdefs, j) == var)
+ 	      *VDEF_OP_PTR (vdefs, j) = repl;
+ 	}
+       modify_stmt (stmt);
+     }
+ }
+ 
+ /* Raises value of phi node PHI by joining it with VAL.  Processes immediate
+    uses of the phi recursively.  */
+ 
+ static void
+ raise_value (tree phi, tree val, tree *eq_to)
+ {
+   int i, n;
+   tree var = PHI_RESULT (phi), stmt;
+   int ver = SSA_NAME_VERSION (var);
+   dataflow_t df;
+ 
+   if (eq_to[ver] == var)
+     return;
+ 
+   switch (TREE_CODE (val))
+     {
+     case SSA_NAME:
+     case REAL_CST:
+     case COMPLEX_CST:
+       break;
+     case INTEGER_CST:
+       if (TREE_CODE (TREE_TYPE (var)) != POINTER_TYPE)
+ 	break;
+ 
+     default:
+       /* Do not propagate pointer constants.  This might require folding
+ 	 things like *&foo and rewriting the ssa, which is not worth the
+ 	 trouble.  */
+       val = var;
+     }
+ 
+   if (eq_to[ver])
+     {
+       if (operand_equal_p (eq_to[ver], val, 0))
+ 	return;
+ 
+       eq_to[ver] = var;
+     }
+   else
+     eq_to[ver] = val;
+ 
+   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
+   n = num_immediate_uses (df);
+ 
+   for (i = 0; i < n; i++)
+     {
+       stmt = immediate_use (df, i);
+ 
+       if (TREE_CODE (stmt) != PHI_NODE)
+ 	continue;
+ 
+       raise_value (stmt, eq_to[ver], eq_to);
+     }
+ }
+ 
+ /* Removes redundant phi nodes (i.e. such that all their arguments are
+    equivalent), copy propagating the results.  Just a trivial copy/const
+    propagation pass over phi nodes.
+    
+    Most importantly this kills degenerated phi nodes that are created by
+    removing an unreachable code.  */
+ 
+ void
+ kill_redundant_phi_nodes (void)
+ {
+   tree *eq_to, *def;
+   unsigned i, ver, aver;
+   basic_block bb;
+   tree phi, t, stmt, var;
+ 
+   eq_to = xcalloc (highest_ssa_version, sizeof (tree));
+   def = xcalloc (highest_ssa_version, sizeof (tree));
+   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
+ 
+   FOR_EACH_BB (bb)
+     {
+       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  var = PHI_RESULT (phi);
+ 	  ver = SSA_NAME_VERSION (var);
+ 	  def[ver] = var;
+ 
+ 	  for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ 	    {
+ 	      t = PHI_ARG_DEF (phi, i);
+ 
+ 	      if (TREE_CODE (t) != SSA_NAME)
+ 		{
+ 		  raise_value (phi, t, eq_to);
+ 		  continue;
+ 		}
+ 
+ 	      stmt = SSA_NAME_DEF_STMT (t);
+ 	      aver = SSA_NAME_VERSION (t);
+ 	      def[aver] = t;
+ 
+ 	      if (TREE_CODE (stmt) != PHI_NODE
+ 		  || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
+ 		{
+ 		  eq_to[aver] = t;
+ 		  raise_value (phi, t, eq_to);
+ 		}
+ 	    }
+ 	}
+     }
+ 
+   /* Now propagate the values.  */
+   for (i = 0; i < highest_ssa_version; i++)
+     if (eq_to[i]
+ 	&& eq_to[i] != def[i])
+       replace_immediate_uses (def[i], eq_to[i]);
+ 
+   /* And remove the dead phis.  */
+   for (i = 0; i < highest_ssa_version; i++)
+     if (eq_to[i]
+ 	&& eq_to[i] != def[i])
+       {
+ 	stmt = SSA_NAME_DEF_STMT (def[i]);
+ 	remove_phi_node (stmt, 0, bb_for_stmt (stmt));
+       }
+ 
+   free_df ();
+   free (eq_to);
+   free (def);
+ }
+ 
  #include "gt-tree-ssa.h"
Index: testsuite/gcc.dg/tree-ssa/20030709-2.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/Attic/20030709-2.c,v
retrieving revision 1.1.2.4
diff -c -3 -p -r1.1.2.4 20030709-2.c
*** testsuite/gcc.dg/tree-ssa/20030709-2.c	21 Sep 2003 22:14:30 -0000	1.1.2.4
--- testsuite/gcc.dg/tree-ssa/20030709-2.c	5 Jan 2004 10:37:20 -0000
*************** get_alias_set (t)
*** 46,51 ****
     more than, then the dominator optimizations failed.  */
  /* { dg-final { scan-tree-dump-times ".rtmem" 1 "dom2"} } */
    
! /* There should be two IF statements.  */
! /* { dg-final { scan-tree-dump-times "if " 2 "dom2"} } */
  
--- 46,51 ----
     more than, then the dominator optimizations failed.  */
  /* { dg-final { scan-tree-dump-times ".rtmem" 1 "dom2"} } */
    
! /* There should be one IF statement.  */
! /* { dg-final { scan-tree-dump-times "if " 1 "dom2"} } */
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]