This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Make tail-call work on SSA form
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at redhat dot com
- Date: Sun, 16 Nov 2003 23:32:12 +0100
- Subject: [tree-ssa] Make tail-call work on SSA form
Hi,
this patch updates tail recursion pass to work on SSA. This makes it possible
to be run after dominator optimizations and dead code removal so we catch some
extra cases (testcases present in GCC boostrap caught by abort() in sibcall.c
attached)
The patch also removes the pass ordering problem from by sibcall.c replacement
patch so I hope updated version will be easier to review as this patch is
really blocking me.
Bootstrapped/regtested i386 and x86_64
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-tail" } */
int
t(int a)
{
if (a)
return t(a-1);
else
return 0;
}
/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail"} } */
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-tail" } */
int
t(char *a)
{
static char p[100];
if (a)
return t(p);
else
return 0;
}
/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail"} } */
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-tail" } */
int
t(int a)
{
int r;
if (a)
r = t(a-1);
else
return 0;
if (r)
r=r;
return r;
}
/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tail"} } */
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-tail" } */
int
t(int a)
{
int r;
if (a&1)
r = t(a-1);
else if (a)
r = t(a-2);
else
return 0;
if (r)
r=r;
return r;
}
/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 2 "tail"} } */
2003-11-16 Jan Hubicka <jh@suse.cz>
* tree-dump.c (dump_files): Reorder tail calls.
* tree-optimize.c (optimize_function_tree): Likewise
* tree-tailcall.c (optimize_tail_call, eliminate_tail_call): Remove variable tmpvars;
update SSA.
(suitable_for_tail_opt_p): Do not give up because of static variables.
(find_tail_calls): Track return values in SSA graph.
* tree.c (make-phi_node): Do not create new SSA name when operand already is.
* tree.h (enum tree_dump_index): Reorder tail call.
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.49
diff -c -3 -p -r1.6.2.49 tree-dump.c
*** tree-dump.c 11 Nov 2003 18:04:46 -0000 1.6.2.49
--- tree-dump.c 16 Nov 2003 22:12:46 -0000
*************** static struct dump_file_info dump_files[
*** 657,663 ****
{".lower", "tree-lower", 0, 0},
{".cfg", "tree-cfg", 0, 0},
{".dot", "tree-dot", 0, 0},
- {".tail", "tree-tail", 0, 0},
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
{".ssa1", "tree-ssa1", 0, 0},
--- 657,662 ----
*************** static struct dump_file_info dump_files[
*** 665,670 ****
--- 664,670 ----
{".dom1", "tree-dom1", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
{".dce1", "tree-dce1", 0, 0},
+ {".tail", "tree-tail", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
{".ssa3", "tree-ssa3", 0, 0},
{".ccp", "tree-ccp", 0, 0},
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.71
diff -c -3 -p -r1.1.4.71 tree-optimize.c
*** tree-optimize.c 12 Nov 2003 22:06:26 -0000 1.1.4.71
--- tree-optimize.c 16 Nov 2003 22:12:46 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 78,86 ****
/* Find all the variables referenced in the function. */
find_referenced_vars (fndecl);
- /* Eliminate tail recursion calls. */
- tree_optimize_tail_calls ();
-
/* Compute aliasing information for all the variables referenced in
the function. */
compute_may_aliases (fndecl);
--- 78,83 ----
*************** optimize_function_tree (tree fndecl, tre
*** 119,124 ****
--- 116,124 ----
dead pointer assignments taking the address of local variables. */
if (flag_tree_dce)
tree_ssa_dce (fndecl, TDI_dce_1);
+
+ /* Eliminate tail recursion calls. */
+ tree_optimize_tail_calls ();
/* The must-alias pass removes the aliasing and addressability bits
from variables that used to have their address taken. */
Index: tree-tailcall.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-tailcall.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 tree-tailcall.c
*** tree-tailcall.c 11 Nov 2003 18:04:47 -0000 1.1.2.6
--- tree-tailcall.c 16 Nov 2003 22:12:46 -0000
*************** struct tailcall
*** 57,64 ****
};
static bool suitable_for_tail_opt_p (void);
! static bool optimize_tail_call (struct tailcall *, tree *);
! static void eliminate_tail_call (struct tailcall *, tree);
static void find_tail_calls (basic_block, struct tailcall *, struct tailcall **);
/* Returns false when the function is not suitable for tail call optimization
--- 57,64 ----
};
static bool suitable_for_tail_opt_p (void);
! static bool optimize_tail_call (struct tailcall *, bool *);
! static void eliminate_tail_call (struct tailcall *);
static void find_tail_calls (basic_block, struct tailcall *, struct tailcall **);
/* Returns false when the function is not suitable for tail call optimization
*************** suitable_for_tail_opt_p (void)
*** 80,85 ****
--- 80,86 ----
tree var = VARRAY_TREE (referenced_vars, i);
if (decl_function_context (var) == current_function_decl
+ && !TREE_STATIC (var)
&& TREE_ADDRESSABLE (var))
return false;
}
*************** find_tail_calls (basic_block bb, struct
*** 99,104 ****
--- 100,106 ----
bool seen_return = false, found = false, tail_recursion = false;
struct tailcall *nw;
edge e;
+ tree old_ret_variable = act->ret_variable;
if (bb->succ->succ_next)
return;
*************** find_tail_calls (basic_block bb, struct
*** 182,189 ****
predecessors. */
if (!found)
{
! for (e = bb->pred; e; e = e->pred_next)
! find_tail_calls (e->src, act, ret);
}
if (seen_return)
--- 184,208 ----
predecessors. */
if (!found)
{
! tree phi;
!
! for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! if (PHI_RESULT (phi) == act->ret_variable)
! break;
! if (phi)
! {
! int phi_num_args = PHI_NUM_ARGS (phi);
! int i;
!
! for (i = 0; i < phi_num_args; i++)
! {
! act->ret_variable = PHI_ARG_DEF (phi, i);
! find_tail_calls (PHI_ARG_EDGE (phi, i)->src, act, ret);
! }
! }
! else
! for (e = bb->pred; e; e = e->pred_next)
! find_tail_calls (e->src, act, ret);
}
if (seen_return)
*************** find_tail_calls (basic_block bb, struct
*** 192,214 ****
act->ret_variable = NULL_TREE;
act->return_block = NULL;
}
}
/* Eliminates tail call described by T. TMP_VARS is a list of
temporary variables used to copy the function arguments. */
static void
! eliminate_tail_call (struct tailcall *t, tree tmp_vars)
{
! tree param, stmt, args, tmp_var;
basic_block bb;
stmt = bsi_stmt (t->call_bsi);
bb = t->call_block;
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Eliminated tail call in bb %d : ", bb->index);
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
--- 211,236 ----
act->ret_variable = NULL_TREE;
act->return_block = NULL;
}
+ act->ret_variable = old_ret_variable;
}
/* Eliminates tail call described by T. TMP_VARS is a list of
temporary variables used to copy the function arguments. */
static void
! eliminate_tail_call (struct tailcall *t)
{
! tree param, stmt, args;
basic_block bb;
+ edge e;
+ tree phi;
stmt = bsi_stmt (t->call_bsi);
bb = t->call_block;
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Eliminated tail recursion in bb %d : ", bb->index);
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
*************** eliminate_tail_call (struct tailcall *t,
*** 216,254 ****
if (TREE_CODE (stmt) == MODIFY_EXPR)
stmt = TREE_OPERAND (stmt, 1);
- /* Copy the args if needed. */
- for (param = DECL_ARGUMENTS (current_function_decl),
- args = TREE_OPERAND (stmt, 1),
- tmp_var = tmp_vars;
- param;
- param = TREE_CHAIN (param),
- args = TREE_CHAIN (args),
- tmp_var = TREE_CHAIN (tmp_var))
- if (param != TREE_VALUE (args)
- /* If the parameter is unused, it was not scanned in
- find_referenced_vars, so we don't want to introduce
- it here. Additionally, it would obviously be
- useless anyway. */
- && var_ann (param))
- bsi_insert_before (&t->call_bsi,
- build (MODIFY_EXPR, TREE_TYPE (param),
- TREE_VALUE (tmp_var),
- unshare_expr (TREE_VALUE (args))),
- BSI_SAME_STMT);
- for (param = DECL_ARGUMENTS (current_function_decl),
- args = TREE_OPERAND (stmt, 1),
- tmp_var = tmp_vars;
- param;
- param = TREE_CHAIN (param),
- args = TREE_CHAIN (args),
- tmp_var = TREE_CHAIN (tmp_var))
- if (param != TREE_VALUE (args)
- && var_ann (param))
- bsi_insert_before (&t->call_bsi,
- build (MODIFY_EXPR, TREE_TYPE (param),
- param, TREE_VALUE (tmp_var)),
- BSI_SAME_STMT);
-
/* Replace the call by jump to the start of function. */
if (t->return_block == bb)
{
--- 238,243 ----
*************** eliminate_tail_call (struct tailcall *t,
*** 257,296 ****
}
bsi_remove (&t->call_bsi);
! if (!redirect_edge_and_branch (t->call_block->succ,
! ENTRY_BLOCK_PTR->succ->dest))
abort ();
}
! /* Optimizes the tailcall described by T. *TMP_VARS is set to a list of
! temporary variables used to copy the function arguments the first time
! they are needed. Returns true if cfg is changed. */
static bool
! optimize_tail_call (struct tailcall *t, tree *tmp_vars)
{
! tree tmp_var, param;
!
! /* Nothing to do unless it is tail recursion. */
! if (!t->tail_recursion)
! return false;
!
! if (!*tmp_vars)
{
! /* Prepare the temporary variables. */
! for (param = DECL_ARGUMENTS (current_function_decl);
! param;
! param = TREE_CHAIN (param))
{
! tmp_var = create_tmp_var (TREE_TYPE (param), "tailtmp");
! add_referenced_tmp_var (tmp_var);
! *tmp_vars = tree_cons (NULL_TREE, tmp_var, *tmp_vars);
}
- *tmp_vars = nreverse (*tmp_vars);
- }
! eliminate_tail_call (t, *tmp_vars);
! return true;
}
/* Optimizes tail calls in the function, turning the tail recursion
--- 246,316 ----
}
bsi_remove (&t->call_bsi);
! e = redirect_edge_and_branch (t->call_block->succ,
! ENTRY_BLOCK_PTR->succ->dest);
! if (!e)
abort ();
+ /* We expect that each PHI node on first basic block represent an argument.
+ Add proper entries. */
+ for (phi = phi_nodes (ENTRY_BLOCK_PTR->succ->dest); phi;
+ phi = TREE_CHAIN (phi))
+ {
+ for (param = DECL_ARGUMENTS (current_function_decl),
+ args = TREE_OPERAND (stmt, 1);
+ param;
+ param = TREE_CHAIN (param),
+ args = TREE_CHAIN (args))
+ if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
+ break;
+ if (!param)
+ abort ();
+ add_phi_arg (&phi, TREE_VALUE (args), e);
+ }
}
! /* Optimizes the tailcall described by T. First time we optimize tail
! call, we need to create PHI nodes for arguments. This is indicated
! by PHIS_CONSTRUCTED. */
static bool
! optimize_tail_call (struct tailcall *t, bool *phis_constructed)
{
! if (t->tail_recursion)
{
! basic_block first = ENTRY_BLOCK_PTR->succ->dest;
! tree param;
!
! if (!*phis_constructed)
{
! /* Ensure that there is only one predecestor of the block. */
! if (first->pred->pred_next)
! first = split_edge (ENTRY_BLOCK_PTR->succ);
! /* Copy the args if needed. */
! for (param = DECL_ARGUMENTS (current_function_decl);
! param;
! param = TREE_CHAIN (param))
! if (var_ann (param)
! /* Also parameters that are only defined but never used need not
! be copied. */
! && (var_ann (param)->default_def
! && TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
! {
! tree name = var_ann (param)->default_def;
! tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
! tree phi;
!
! var_ann (param)->default_def = new_name;
! phi = create_phi_node (name, first);
! SSA_NAME_DEF_STMT (name) = phi;
! add_phi_arg (&phi, new_name, first->pred);
! }
! *phis_constructed = true;
}
! eliminate_tail_call (t);
! return true;
! }
! return false;
}
/* Optimizes tail calls in the function, turning the tail recursion
*************** void
*** 300,306 ****
tree_optimize_tail_calls (void)
{
edge e;
! tree tmp_vars = NULL_TREE;
struct tailcall common, *tailcalls = NULL, *next;
bool changed = false;
--- 320,326 ----
tree_optimize_tail_calls (void)
{
edge e;
! bool phis_constructed = false;
struct tailcall common, *tailcalls = NULL, *next;
bool changed = false;
*************** tree_optimize_tail_calls (void)
*** 323,329 ****
for (; tailcalls; tailcalls = next)
{
next = tailcalls->next;
! changed |= optimize_tail_call (tailcalls, &tmp_vars);
free (tailcalls);
}
--- 343,349 ----
for (; tailcalls; tailcalls = next)
{
next = tailcalls->next;
! changed |= optimize_tail_call (tailcalls, &phis_constructed);
free (tailcalls);
}
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.263.2.68
diff -c -3 -p -r1.263.2.68 tree.c
*** tree.c 14 Nov 2003 08:16:56 -0000 1.263.2.68
--- tree.c 16 Nov 2003 22:12:46 -0000
*************** make_phi_node (tree var, int len)
*** 5168,5174 ****
TREE_SET_CODE (phi, PHI_NODE);
PHI_NUM_ARGS (phi) = 0;
PHI_ARG_CAPACITY (phi) = len;
! PHI_RESULT (phi) = make_ssa_name (var, phi);
return phi;
}
--- 5168,5177 ----
TREE_SET_CODE (phi, PHI_NODE);
PHI_NUM_ARGS (phi) = 0;
PHI_ARG_CAPACITY (phi) = len;
! if (TREE_CODE (var) == SSA_NAME)
! PHI_RESULT (phi) = var;
! else
! PHI_RESULT (phi) = make_ssa_name (var, phi);
return phi;
}
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.126
diff -c -3 -p -r1.342.2.126 tree.h
*** tree.h 16 Nov 2003 08:24:02 -0000 1.342.2.126
--- tree.h 16 Nov 2003 22:12:47 -0000
*************** enum tree_dump_index
*** 3536,3542 ****
TDI_cfg, /* dump the flowgraph for each function. */
TDI_dot, /* create a dot graph file for each
function's flowgraph. */
- TDI_tail, /* dump after tail recursion elimination */
TDI_pta, /* dump points-to information for each
function. */
TDI_alias, /* dump aliasing information. */
--- 3536,3541 ----
*************** enum tree_dump_index
*** 3548,3553 ****
--- 3547,3553 ----
TDI_dom_1,
TDI_ssa_2,
TDI_dce_1,
+ TDI_tail, /* dump after tail recursion elimination */
TDI_mustalias,
TDI_ssa_3,
TDI_ccp,