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]

[patch] Scev based final value replacement


Hello,

on loops like

for (i = 0; i < 100; i++)
  {
    x = 3 * i + 8;
    something;
  }

use (x);

it is usually a win to replace this by

for (i = 0; i < 100; i++)
  {
    x = 3 * i + 8;
    something;
  }
 use (308);

Ivopts already sometimes perform this optimization, but not very
reliably (they only do that when it helps with optimization of the
induction variables inside the loop).  For example if the variable
x must be preserved, ivopts will not bother with replacing its final
value.

This patch adds a simple pass that performs this optimization,
using the data obtained from scev analysis.

Bootstrapped & regtested on i686 and ia64.

Zdenek

	* timevar.def (TV_SCEV_CONST): New timevar.
	* tree-flow.h (fold_stmt_inplace): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_scev_cprop.
	* tree-pass.h (pass_scev_cprop): Declare.
	* tree-scalar-evolution.c (replace_uses_by, scev_const_prop): New
	functions.
	* tree-scalar-evolution.h (scev_const_prop): Declare.
	* tree-ssa-ccp.c (fold_stmt_inplace): New function.
	* tree-ssa-loop.c (gate_scev_const_prop, pass_scev_cprop):
	New.

Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.46
diff -c -3 -p -r1.46 timevar.def
*** timevar.def	13 Apr 2005 04:29:37 -0000	1.46
--- timevar.def	13 May 2005 21:04:29 -0000
*************** DEFTIMEVAR (TV_TREE_LOOP	     , "tree lo
*** 95,100 ****
--- 95,101 ----
  DEFTIMEVAR (TV_TREE_LOOP_BOUNDS	     , "tree record loop bounds")
  DEFTIMEVAR (TV_LIM                   , "loop invariant motion")
  DEFTIMEVAR (TV_TREE_LOOP_IVCANON     , "tree canonical iv creation")
+ DEFTIMEVAR (TV_SCEV_CONST            , "scev constant propagation")
  DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH    , "tree loop unswitching")
  DEFTIMEVAR (TV_COMPLETE_UNROLL       , "complete unrolling")
  DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree loop vectorization")
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.103
diff -c -3 -p -r2.103 tree-flow.h
*** tree-flow.h	8 May 2005 15:07:22 -0000	2.103
--- tree-flow.h	13 May 2005 21:04:29 -0000
*************** void set_current_def (tree, tree);
*** 628,633 ****
--- 628,634 ----
  
  /* In tree-ssa-ccp.c  */
  bool fold_stmt (tree *);
+ bool fold_stmt_inplace (tree);
  tree widen_bitfield (tree, tree, tree);
  
  /* In tree-vrp.c  */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.90
diff -c -3 -p -r2.90 tree-optimize.c
*** tree-optimize.c	11 May 2005 02:24:42 -0000	2.90
--- tree-optimize.c	13 May 2005 21:04:29 -0000
*************** init_tree_optimization_passes (void)
*** 438,443 ****
--- 438,444 ----
    NEXT_PASS (pass_copy_prop);
    NEXT_PASS (pass_lim);
    NEXT_PASS (pass_unswitch);
+   NEXT_PASS (pass_scev_cprop);
    NEXT_PASS (pass_record_bounds);
    NEXT_PASS (pass_linear_transform);
    NEXT_PASS (pass_iv_canon);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.33
diff -c -3 -p -r2.33 tree-pass.h
*** tree-pass.h	21 Apr 2005 13:18:23 -0000	2.33
--- tree-pass.h	13 May 2005 21:04:29 -0000
*************** extern struct tree_opt_pass pass_loop_in
*** 172,177 ****
--- 172,178 ----
  extern struct tree_opt_pass pass_lim;
  extern struct tree_opt_pass pass_unswitch;
  extern struct tree_opt_pass pass_iv_canon;
+ extern struct tree_opt_pass pass_scev_cprop;
  extern struct tree_opt_pass pass_record_bounds;
  extern struct tree_opt_pass pass_if_conversion;
  extern struct tree_opt_pass pass_vectorize;
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.23
diff -c -3 -p -r2.23 tree-scalar-evolution.c
*** tree-scalar-evolution.c	2 May 2005 08:56:52 -0000	2.23
--- tree-scalar-evolution.c	13 May 2005 21:04:29 -0000
*************** scev_finalize (void)
*** 2626,2628 ****
--- 2626,2720 ----
    BITMAP_FREE (already_instantiated);
  }
  
+ /* Replaces all uses of NAME by VAL.  */
+ 
+ static void
+ replace_uses_by (tree name, tree val)
+ {
+   imm_use_iterator imm_iter;
+   use_operand_p use;
+   tree stmt;
+ 
+   FOR_EACH_IMM_USE_SAFE (use, imm_iter, name)
+     {
+       stmt = USE_STMT (use);
+ 
+       SET_USE (use, val);
+ 
+       if (TREE_CODE (stmt) != PHI_NODE)
+ 	{
+ 	  fold_stmt_inplace (stmt);
+ 	  update_stmt (stmt);
+ 	}
+     }
+ }
+ 
+ /* Replace ssa names for that scev can prove they are constant by the
+    appropriate constants.  Most importantly, this takes care of final
+    value replacement.
+    
+    We only consider SSA names defined by phi nodes; rest is left to the
+    ordinary constant propagation pass.  */
+ 
+ void
+ scev_const_prop (void)
+ {
+   basic_block bb;
+   tree name, phi, type, ev;
+   struct loop *loop;
+   bitmap ssa_names_to_remove = NULL;
+ 
+   if (!current_loops)
+     return;
+ 
+   FOR_EACH_BB (bb)
+     {
+       loop = bb->loop_father;
+ 
+       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ 	{
+ 	  name = PHI_RESULT (phi);
+ 
+ 	  if (!is_gimple_reg (name))
+ 	    continue;
+ 
+ 	  type = TREE_TYPE (name);
+ 
+ 	  if (!POINTER_TYPE_P (type)
+ 	      && !INTEGRAL_TYPE_P (type))
+ 	    continue;
+ 
+ 	  ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
+ 	  if (!is_gimple_min_invariant (ev)
+ 	      || !may_propagate_copy (name, ev))
+ 	    continue;
+ 
+ 	  /* Replace the uses of the name.  */
+ 	  replace_uses_by (name, ev);
+ 
+ 	  if (!ssa_names_to_remove)
+ 	    ssa_names_to_remove = BITMAP_ALLOC (NULL);
+ 	  bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
+ 	}
+     }
+ 
+   /* Remove the ssa names that were replaced by constants.  We do not remove them
+      directly in the previous cycle, since this invalidates scev cache.  */
+   if (ssa_names_to_remove)
+     {
+       bitmap_iterator bi;
+       unsigned i;
+ 
+       EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
+ 	{
+ 	  name = ssa_name (i);
+ 	  phi = SSA_NAME_DEF_STMT (name);
+ 
+ 	  gcc_assert (TREE_CODE (phi) == PHI_NODE);
+ 	  remove_phi_node (phi, NULL);
+ 	}
+ 
+       BITMAP_FREE (ssa_names_to_remove);
+       scev_reset ();
+     }
+ }
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.h,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-scalar-evolution.h
*** tree-scalar-evolution.h	9 May 2005 16:26:17 -0000	2.5
--- tree-scalar-evolution.h	13 May 2005 21:04:29 -0000
*************** extern tree instantiate_parameters (stru
*** 33,37 ****
--- 33,38 ----
  extern void gather_stats_on_scev_database (void);
  extern void scev_analysis (void);
  extern bool simple_iv (struct loop *, tree, tree, tree *, tree *, bool);
+ void scev_const_prop (void);
  
  #endif  /* GCC_TREE_SCALAR_EVOLUTION_H  */
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.70
diff -c -3 -p -r2.70 tree-ssa-ccp.c
*** tree-ssa-ccp.c	8 May 2005 21:22:20 -0000	2.70
--- tree-ssa-ccp.c	13 May 2005 21:04:29 -0000
*************** fold_stmt (tree *stmt_p)
*** 2308,2313 ****
--- 2311,2342 ----
    return changed;
  }
  
+ /* Perform the minimal folding on statement STMT.  Only operations like
+    *&x created by constant propagation are handled.  The statement cannot
+    be replaced with a new one.  */
+ 
+ bool
+ fold_stmt_inplace (tree stmt)
+ {
+   tree old_stmt = stmt, rhs, new_rhs;
+   bool changed = false;
+ 
+   walk_tree (&stmt, fold_stmt_r, &changed, NULL);
+   gcc_assert (stmt == old_stmt);
+ 
+   rhs = get_rhs (stmt);
+   if (!rhs || rhs == stmt)
+     return changed;
+ 
+   new_rhs = fold (rhs);
+   if (new_rhs == rhs)
+     return changed;
+ 
+   changed |= set_rhs (&stmt, new_rhs);
+   gcc_assert (stmt == old_stmt);
+ 
+   return changed;
+ }
  
  /* Convert EXPR into a GIMPLE value suitable for substitution on the
     RHS of an assignment.  Insert the necessary statements before
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.29
diff -c -3 -p -r2.29 tree-ssa-loop.c
*** tree-ssa-loop.c	6 May 2005 21:11:29 -0000	2.29
--- tree-ssa-loop.c	13 May 2005 21:04:29 -0000
*************** struct tree_opt_pass pass_iv_canon =
*** 286,291 ****
--- 286,316 ----
    0					/* letter */
  };
  
+ /* Propagation of constants using scev.  */
+ 
+ static bool
+ gate_scev_const_prop (void)
+ {
+   return true;
+ }
+ 
+ struct tree_opt_pass pass_scev_cprop =
+ {
+   "sccp",				/* name */
+   gate_scev_const_prop,			/* gate */
+   scev_const_prop,	       		/* execute */
+   NULL,					/* sub */
+   NULL,					/* next */
+   0,					/* static_pass_number */
+   TV_SCEV_CONST,	  		/* tv_id */
+   PROP_cfg | PROP_ssa,			/* properties_required */
+   0,					/* properties_provided */
+   0,					/* properties_destroyed */
+   0,					/* todo_flags_start */
+   TODO_dump_func,			/* todo_flags_finish */
+   0					/* letter */
+ };
+ 
  /* Record bounds on numbers of iterations of loops.  */
  
  static void


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