[autovect] Update the chrec_unify patch

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

Hi, 

Some time ago Dan has asked why we don't optimise some code after his
aggressive PRE pass.  The answer was that PRE introduced wrap around
variables.  I don't know how often the optimization passes that occur
before the scev analyzer introduce wrap around vars, but the number of
cases that the following patch catches is quite important: during a
single bootstrap stage, there were 338 occurences in the .ivopts
dumps, ie. when bootstrapping with BOOT_CFLAGS="-O2
-fdump-tree-ivopts-details".

The previous patch that I sent to gcc-patches for solving this problem
was corrupting the ivopts pass.  For solving this interaction, scev
analyzer transforms the code as follows: given "x" a peeled evolution
that can be unified as in the code

 z = loop-phi (1, z + 1)
 x = loop-phi (0, z)

we generate a new induction variable "y" and set "x = y":

 y = loop-phi (0, y + 1)
 x = y

ivopts will naturally select a single iv, and a single loop phi node
will be kept in the loop, while previously the evolution for "x =
loop-phi (0, z)" would have been unknown, leading to two loop phi
nodes in the loop.

Bootstrapped and tested on i686.  Applied to autovect-branch.

Index: ChangeLog.autovect
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.autovect,v
retrieving revision 1.1.2.22
diff -d -u -p -r1.1.2.22 ChangeLog.autovect
--- ChangeLog.autovect	13 Jan 2005 14:45:08 -0000	1.1.2.22
+++ ChangeLog.autovect	13 Jan 2005 18:07:18 -0000
@@ -1,5 +1,16 @@
 2005-01-13  Sebastian Pop  <pop@cri.ensmp.fr>
 
+	* tree-scalar-evolution.c (already_unified): New bitmap.
+	(follow_ssa_edge): Include a comment for the return value.
+	(unify_peeled_chrec): New function...
+	(analyze_evolution_in_loop): ... called from here.
+	(scev_initialize): Initialize already_unified.
+	(scev_finalize): Free already_unified.
+	* tree-ssa-loop-ivopts.c (find_bivs): Allow the scev analyzer
+	to remove or add loop phi nodes in the analyzed loop.
+
+2005-01-13  Sebastian Pop  <pop@cri.ensmp.fr>
+
 	* tree-data-ref.c (analyze_subscript_affine_affine): Clarify
 	function's comment.  Include a FIXME note for the symbolic case.
 	(analyze_siv_subscript, analyze_miv_subscript): Ensure that no 
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.10.2.1
diff -d -u -p -r2.10.2.1 tree-scalar-evolution.c
--- tree-scalar-evolution.c	14 Dec 2004 08:45:48 -0000	2.10.2.1
+++ tree-scalar-evolution.c	13 Jan 2005 18:07:18 -0000
@@ -284,6 +284,7 @@ tree chrec_dont_know;
 tree chrec_known;
 
 static bitmap already_instantiated;
+static bitmap already_unified;
 
 static htab_t scalar_evolution_info;
 
@@ -1395,7 +1396,8 @@ follow_ssa_edge_inner_loop_phi (struct l
 }
 
 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
-   path that is analyzed on the return walk.  */
+   path that is analyzed on the return walk.  Returns true when the
+   halting_phi can be reached by following the ssa chains.  */
 
 static bool
 follow_ssa_edge (struct loop *loop, 
@@ -1457,6 +1459,108 @@ follow_ssa_edge (struct loop *loop, 
 
 
 
+/* A is the initial condition and B is the update edge of
+   LOOP_PHI_NODE, and consequently they are either scalars or symbolic
+   names.  The function returns chrec_dont_know if the unify operation
+   fails, otherwise returns the unification of the scalar value A to
+   the beginning of the scalar evolution B.  For example, it is
+   possible to unify 0 with {1, +, 1}_3, into {0, +, 1}_3.  */
+
+static tree
+unify_peeled_chrec (tree loop_phi_node, tree a, tree b)
+{
+  tree chrec_b, extrapolate, difference, type;
+  struct loop *loop = loop_containing_stmt (loop_phi_node);
+
+  if (a == NULL_TREE 
+      || b == NULL_TREE || TREE_CODE (b) != SSA_NAME
+      || bitmap_bit_p (already_unified, SSA_NAME_VERSION (b)))
+    return chrec_dont_know;
+
+  if (TREE_CODE (a) == SSA_NAME)
+    {
+      tree chrec_a;
+
+      if (bitmap_bit_p (already_unified, SSA_NAME_VERSION (a)))
+	return chrec_dont_know;
+
+      bitmap_set_bit (already_unified, SSA_NAME_VERSION (a));
+      chrec_a = instantiate_parameters (loop, analyze_scalar_evolution (loop, a));
+      bitmap_clear_bit (already_unified, SSA_NAME_VERSION (a));
+      a = chrec_a;
+    }
+  
+  if (TREE_CODE (a) != INTEGER_CST)
+    /* FIXME: The multivariate case is not handled yet.  */
+    return chrec_dont_know;
+
+  bitmap_set_bit (already_unified, SSA_NAME_VERSION (b));
+  chrec_b = instantiate_parameters (loop, analyze_scalar_evolution (loop, b));
+  bitmap_clear_bit (already_unified, SSA_NAME_VERSION (b));
+  
+  if (chrec_b == NULL_TREE 
+      || TREE_CODE (chrec_b) != POLYNOMIAL_CHREC
+      || TREE_CODE (CHREC_LEFT (chrec_b)) != INTEGER_CST
+      || TREE_CODE (CHREC_RIGHT (chrec_b)) != INTEGER_CST)
+    return chrec_dont_know;
+
+  type = chrec_type (chrec_b);
+  a = fold_convert (type, a);
+
+  extrapolate = fold (build2 (MINUS_EXPR, type, CHREC_LEFT (chrec_b),
+			      CHREC_RIGHT (chrec_b)));
+  difference = fold (build2 (MINUS_EXPR, integer_type_node, a, extrapolate));
+
+  if (integer_zerop (difference))
+    {
+      /* Because ivopts is disturbed by not seeing a real induction
+	 variable, we generate the code here, as illustrated by the
+	 following example: suppose that we start with the following
+	 code, where "x" is the peeled evolution that can be unified.
+
+	 x = loop-phi (0, z)
+	 z = loop-phi (1, z + 1)
+	 
+	 Then we would like to express "x" independently of "z" such
+	 that ivopts is not disturbed by seeing ghost evolutions like
+	 {0, +, 1} for "x".  For this we generate a new induction
+	 variable "y" as in the following code:
+	 
+	 y = loop-phi (0, y + 1)
+	 x = y 
+
+	 finally, return the unified chrec: {0, +, 1} for "x".  */
+      tree stmt, var;
+      block_stmt_iterator incr_at;
+      basic_block bb;
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "UNIFIED_one_more\n");
+
+      incr_at = bsi_last (EDGE_PRED (loop->latch, 0)->src);
+      create_iv (a, CHREC_RIGHT (chrec_b), NULL, loop, &incr_at, false, &var, 
+		 NULL);
+
+      stmt = build2 (MODIFY_EXPR, void_type_node, PHI_RESULT (loop_phi_node), 
+		     var);
+
+      bb = bb_for_stmt (loop_phi_node);
+      incr_at = bsi_start (bb);
+      bsi_insert_after (&incr_at, stmt, BSI_NEW_STMT);
+      SSA_NAME_DEF_STMT (PHI_RESULT (loop_phi_node)) = stmt;
+      /* Prevent the ssa name defined by the loop_phi_node from being
+	 removed.  */
+      SET_PHI_RESULT (loop_phi_node, NULL);
+      remove_phi_node (loop_phi_node, NULL_TREE, bb);
+
+      return build_polynomial_chrec (CHREC_VARIABLE (chrec_b), 
+				     a,
+				     CHREC_RIGHT (chrec_b));
+    }
+
+  return chrec_dont_know;
+}
+
 /* Given a LOOP_PHI_NODE, this function determines the evolution
    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
 
@@ -1499,14 +1603,17 @@ analyze_evolution_in_loop (tree loop_phi
       else
 	res = false;
 	      
-      /* When it is impossible to go back on the same
-	 loop_phi_node by following the ssa edges, the
-	 evolution is represented by a peeled chrec, i.e. the
-	 first iteration, EV_FN has the value INIT_COND, then
-	 all the other iterations it has the value of ARG.  
-	 For the moment, PEELED_CHREC nodes are not built.  */
-      if (!res)
-	ev_fn = chrec_dont_know;
+      /* When it is impossible to go back on the same loop_phi_node by
+	 following the ssa edges, the evolution can be represented by
+	 a peeled chrec, i.e. the first iteration, EV_FN has the value
+	 INIT_COND, then all the other iterations it has the value of
+	 ARG.  For the moment, PEELED_CHREC nodes are not built.  We
+	 try to produce a simple chrec by unifying the initial value
+	 to the rest of the evolution function.  This is possible when
+	 for example we have to unify 0 with {1, +, 1}_3, that gives
+	 the simple chrec {0, +, 1}_3.  */
+      if (res == false)
+	ev_fn = unify_peeled_chrec (loop_phi_node, init_cond, arg);
       
       /* When there are multiple back edges of the loop (which in fact never
 	 happens currently, but nevertheless), merge their evolutions.  */
@@ -2387,6 +2494,7 @@ scev_initialize (struct loops *loops)
   scalar_evolution_info = htab_create (100, hash_scev_info,
 				       eq_scev_info, del_scev_info);
   already_instantiated = BITMAP_XMALLOC ();
+  already_unified = BITMAP_XMALLOC ();
   
   initialize_scalar_evolutions_analyzer ();
 
@@ -2482,5 +2590,6 @@ scev_finalize (void)
 {
   htab_delete (scalar_evolution_info);
   BITMAP_XFREE (already_instantiated);
+  BITMAP_XFREE (already_unified);
 }
 
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.27.2.1
diff -d -u -p -r2.27.2.1 tree-ssa-loop-ivopts.c
--- tree-ssa-loop-ivopts.c	14 Dec 2004 08:45:58 -0000	2.27.2.1
+++ tree-ssa-loop-ivopts.c	13 Jan 2005 18:07:18 -0000
@@ -858,6 +858,25 @@ find_bivs (struct ivopts_data *data)
   tree phi, step, type, base;
   bool found = false;
   struct loop *loop = data->current_loop;
+  int i;
+  VEC (tree) *loop_phis;
+
+  /* For allowing scev to remove some loop phi nodes in
+     unify_peeled_chrec, we have to compute the scev information
+     before assuming that each phi node is an induction variable.  */
+  loop_phis = VEC_alloc (tree, 2);
+  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+    {
+      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
+	continue;
+
+      VEC_safe_push (tree, loop_phis, phi);
+    }
+
+  for (i = 0; VEC_iterate(tree, loop_phis, i, phi); i++)
+    determine_biv_step (phi);
+  
+  VEC_free (tree, loop_phis);
 
   for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
     {