[PATCH]: Fix latent bug in tailcall

[Daniel Berlin <dberlin at dberlin dot org>]

This patch fixes a latent bug in tree-tailcall where it did not update
the virtual ssa form for non-call clobbered virtual operands, even when
there were live on entry virtual operands that needed updating.

The attached testcase will fail, but *only* in conjunction with an
improved load PRE patch that i will submit later today.

However, being a bugfix, i am submitting this patch separately, and will
just throw the testcase in compile/torture.

Bootstrapped and regtested on i686-pc-linux-gnu.

Okay for mainline?

--Dan

2006-01-31  Zdenek Dvorak <dvorakz@suse.cz>
            Daniel Berlin  <dberlin@dberlin.org>

        * tree-tailcall.c (arg_needs_copy_p): New function.
        (eliminate_tail_call): Use arg_needs_copy_p.
        (tree_optimize_tail_calls_1): Ditto. Also call add_virtual_phis.
        (add_virtual_phis): New function.

2006-01-31  Zdenek Dvorak <dvorakz@suse.cz>
	    Daniel Berlin  <dberlin@dberlin.org>

	* tree-tailcall.c (arg_needs_copy_p): New function.
	(eliminate_tail_call): Use arg_needs_copy_p.
	(tree_optimize_tail_calls_1): Ditto. Also call add_virtual_phis.
	(add_virtual_phis): New function.
Index: tree-tailcall.c
===================================================================
--- tree-tailcall.c	(revision 110438)
+++ tree-tailcall.c	(working copy)
@@ -690,6 +690,25 @@ decrease_profile (basic_block bb, gcov_t
     e->count = 0;
 }
 
+/* Returns true if argument PARAM of the tail recursive call needs to be copied
+   when the call is eliminated.  */
+
+static bool
+arg_needs_copy_p (tree param)
+{
+  tree def;
+
+  if (!is_gimple_reg (param) || !var_ann (param))
+    return false;
+		
+  /* Parameters that are only defined but never used need not be copied.  */
+  def = default_def (param);
+  if (!def || TREE_CODE (def) != SSA_NAME)
+    return false;
+
+  return true;
+}
+
 /* Eliminates tail call described by T.  TMP_VARS is a list of
    temporary variables used to copy the function arguments.  */
 
@@ -701,9 +720,6 @@ eliminate_tail_call (struct tailcall *t)
   edge e;
   tree phi;
   block_stmt_iterator bsi;
-  use_operand_p mayuse;
-  def_operand_p maydef;
-  ssa_op_iter iter;
   tree orig_stmt;
 
   stmt = orig_stmt = bsi_stmt (t->call_bsi);
@@ -751,65 +767,21 @@ eliminate_tail_call (struct tailcall *t)
   gcc_assert (e);
   PENDING_STMT (e) = NULL_TREE;
 
-  /* Add phi node entries for arguments.  Not every PHI node corresponds to
-     a function argument (there may be PHI nodes for virtual definitions of the
-     eliminated calls), so we search for a PHI corresponding to each argument
-     rather than searching for which argument a PHI node corresponds to.  */
-  
+  /* Add phi node entries for arguments.  The ordering of the phi nodes should
+     be the same as the ordering of the arguments.  */
   for (param = DECL_ARGUMENTS (current_function_decl),
-       args = TREE_OPERAND (stmt, 1);
+       args = TREE_OPERAND (stmt, 1),
+       phi = phi_nodes (first);
        param;
        param = TREE_CHAIN (param),
        args = TREE_CHAIN (args))
     {
-      
-      for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
-	if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
-	  break;
-
-      /* The phi node indeed does not have to be there, in case the operand is
-	 invariant in the function.  */
-      if (!phi)
+      if (!arg_needs_copy_p (param))
 	continue;
+      gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
 
       add_phi_arg (phi, TREE_VALUE (args), e);
-    }
-
-  /* Add phi nodes for the call clobbered variables.  */
-  FOR_EACH_SSA_MAYDEF_OPERAND (maydef, mayuse, orig_stmt, iter)
-    {
-      param = SSA_NAME_VAR (DEF_FROM_PTR (maydef));
-      for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
-	if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
-	  break;
-
-      if (!phi)
-	{
-	  tree name = default_def (param);
-	  tree new_name;
-
-	  if (!name)
-	    {
-	      /* It may happen that the tag does not have a default_def in case
-		 when all uses of it are dominated by a MUST_DEF.  This however
-		 means that it is not necessary to add a phi node for this
-		 tag.  */
-	      continue;
-	    }
-	  new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
-
-	  set_default_def (param, new_name);
-	  phi = create_phi_node (name, first);
-	  SSA_NAME_DEF_STMT (name) = phi;
-	  add_phi_arg (phi, new_name, single_succ_edge (ENTRY_BLOCK_PTR));
-
-	  /* For all calls the same set of variables should be clobbered.  This
-	     means that there always should be the appropriate phi node except
-	     for the first time we eliminate the call.  */
-	  gcc_assert (EDGE_COUNT (first->preds) <= 2);
-	}
-
-      add_phi_arg (phi, USE_FROM_PTR (mayuse), e);
+      phi = PHI_CHAIN (phi);
     }
 
   /* Update the values of accumulators.  */
@@ -829,6 +801,38 @@ eliminate_tail_call (struct tailcall *t)
   release_defs (call);
 }
 
+/* Add phi nodes for the virtual operands defined in the function to the
+   header of the loop created by tail recursion elimination.
+
+   Originally, we used to add phi nodes only for call clobbered variables,
+   as the value of the non-call clobbered ones obviously cannot be used
+   or changed within the recursive call.  However, the local variables
+   from multiple calls now share the same location, so the virtual ssa form
+   requires us to say that the location dies on further iterations of the loop,
+   which requires adding phi nodes.
+*/
+static void
+add_virtual_phis (void)
+{
+  referenced_var_iterator rvi;
+  tree var;
+
+  /* The problematic part is that there is no way how to know what
+     to put into phi nodes (there in fact does not have to be such
+     ssa name available).  A solution would be to have an artificial
+     use/kill for all virtual operands in EXIT node.  Unless we have
+     this, we cannot do much better than to rebuild the ssa form for
+     possibly affected virtual ssa names from scratch.  */
+
+  FOR_EACH_REFERENCED_VAR (var, rvi)
+    {
+      if (!is_gimple_reg (var) && default_def (var) != NULL_TREE)
+	mark_sym_for_renaming (var);
+    }
+
+  update_ssa (TODO_update_ssa_only_virtuals);
+}
+
 /* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
    mark the tailcalls for the sibcall optimization.  */
 
@@ -897,7 +901,6 @@ tree_optimize_tail_calls_1 (bool opt_tai
 
       if (!phis_constructed)
 	{
-	  tree name;
 	  /* Ensure that there is only one predecessor of the block.  */
 	  if (!single_pred_p (first))
 	    first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
@@ -906,21 +909,17 @@ tree_optimize_tail_calls_1 (bool opt_tai
 	  for (param = DECL_ARGUMENTS (current_function_decl);
 	       param;
 	       param = TREE_CHAIN (param))
-	    if (is_gimple_reg (param)
-		&& var_ann (param)
-		/* Also parameters that are only defined but never used need not
-		   be copied.  */
-		&& ((name = default_def (param))
-		    && TREE_CODE (name) == SSA_NAME))
-	    {
-	      tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
-	      tree phi;
-
-	      set_default_def (param, new_name);
-	      phi = create_phi_node (name, first);
-	      SSA_NAME_DEF_STMT (name) = phi;
-	      add_phi_arg (phi, new_name, single_pred_edge (first));
-	    }
+	    if (arg_needs_copy_p (param))
+	      {
+		tree name = default_def (param);
+		tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
+		tree phi;
+
+		set_default_def (param, new_name);
+		phi = create_phi_node (name, first);
+		SSA_NAME_DEF_STMT (name) = phi;
+		add_phi_arg (phi, new_name, single_pred_edge (first));
+	      }
 	  phis_constructed = true;
 	}
 
@@ -957,6 +956,14 @@ tree_optimize_tail_calls_1 (bool opt_tai
 	}
     }
 
+
+  if (phis_constructed)
+    {
+      /* Reverse the order of the phi nodes, so that it matches the order
+	 of operands of the function, as assumed by eliminate_tail_call.  */
+      set_phi_nodes (first, phi_reverse (phi_nodes (first)));
+    }
+
   for (; tailcalls; tailcalls = next)
     {
       next = tailcalls->next;
@@ -982,6 +989,9 @@ tree_optimize_tail_calls_1 (bool opt_tai
       free_dominance_info (CDI_DOMINATORS);
       cleanup_tree_cfg ();
     }
+
+  if (phis_constructed)
+    add_virtual_phis ();
 }
 
 static void

typedef unsigned int size_t;
typedef const struct objc_selector
{
  void *sel_id;
}
 *SEL;
typedef struct objc_object
{
}
 *id;
typedef struct objc_class *Class;
struct objc_class
{
  struct sarray *dtable;
};
typedef size_t sidx;
struct soffset
{
  unsigned int boffset:(sizeof (size_t) * 8) / 2;
  unsigned int eoffset:(sizeof (size_t) * 8) / 2;
};
union sofftype
{
  struct soffset off;
  sidx idx;
};
struct sarray
{
  size_t capacity;
};
static __inline__ unsigned int
soffset_decode (sidx indx)
{
  union sofftype x;
  x.idx = indx;
  return x.off.eoffset + (x.off.boffset * (1 << 5));
}
static __inline__ void *
sarray_get_safe (struct sarray *array, sidx indx)
{
  if (soffset_decode (indx) < array->capacity)
    return (void *)sarray_get (array, indx);
}
void *
get_imp (Class class, SEL sel)
{
  void *res = sarray_get_safe (class->dtable, (size_t) sel->sel_id);
  if (res == 0)
    {
	{
	  res = get_imp (class, sel);
	}
    }
}