This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Tail recursion optimisation
Hello,
> > > I wonder if we should move the setting of current_function_stdarg
> > > from assign_parms to allocate_struct_function.
> > >
> > > As far as the rest, I'd like to see
> > >
> > > (1) This in a new file. Say tree-tailcall.c.
> > > (2) The function not being named recursion specific, say,
> > > tree_optimize_tail_calls.
> > > (3) This monster function broken up a bit.
> >
> > here is the patch with these changes.
>
> ...but you forgot the new file.
:-( Here it is.
Zdenek
/* Tail calls optimization on trees.
Copyright (C) 2003 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "function.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "diagnostic.h"
/* Dump files and flags. */
static FILE *dump_file; /* CFG dump file. */
static int dump_flags; /* CFG dump flags. */
static bool suitable_for_tail_opt_p (void);
static void bb_optimize_tail_calls (basic_block, tree *);
static bool find_tail_call_p (basic_block, block_stmt_iterator *, bool *);
static void eliminate_tail_call (block_stmt_iterator, bool, tree);
/* Returns false when the function is not suitable for tail call optimization
from some reason (e.g. if it takes variable number of arguments). */
static bool
suitable_for_tail_opt_p ()
{
int i;
if (current_function_stdarg)
return false;
/* No local variable should have its address taken, as otherwise it might
be passed to the recursive call. This of course is overly
conservative and should be replaced by a dataflow analysis later. */
for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
{
tree var = VARRAY_TREE (referenced_vars, i);
if (TREE_CODE (var) == VAR_DECL
&& decl_function_context (var) == current_function_decl
&& TREE_ADDRESSABLE (var))
return false;
}
return true;
}
/* Checks whether basic block BB ends in a tail call. If so, BSI is set
to point to it. HAS_RETURN is set to true if the call is followed by
return. */
static bool
find_tail_call_p (basic_block bb, block_stmt_iterator *bsi, bool *has_return)
{
tree ret_var, ass_var, stmt, func, param, args;
if (bb->succ->succ_next)
return false;
*bsi = bsi_last (bb);
if (bsi_end_p (*bsi))
return false;
stmt = bsi_stmt (*bsi);
*has_return = TREE_CODE (stmt) == RETURN_EXPR;
if (*has_return)
{
ret_var = TREE_OPERAND (stmt, 0);
if (ret_var && TREE_CODE (ret_var) == MODIFY_EXPR)
ret_var = TREE_OPERAND (ret_var, 1);
bsi_prev (bsi);
}
else
ret_var = NULL_TREE;
if (bsi_end_p (*bsi))
return false;
stmt = bsi_stmt (*bsi);
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
ass_var = TREE_OPERAND (stmt, 0);
stmt = TREE_OPERAND (stmt, 1);
}
else
ass_var = NULL_TREE;
if (ass_var != ret_var)
return false;
if (TREE_CODE (stmt) != CALL_EXPR)
return false;
func = TREE_OPERAND (stmt, 0);
if (TREE_CODE (func) != ADDR_EXPR)
return false;
func = TREE_OPERAND (func, 0);
if (func != current_function_decl)
return false;
for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (stmt, 1);
param && args;
param = TREE_CHAIN (param), args = TREE_CHAIN (args))
if (param != TREE_VALUE (args)
/* Make sure there are no problems with copying. */
&& !is_gimple_reg_type (TREE_TYPE (param)))
return false;
if (args || param)
return false;
return true;
}
/* Eliminates tail call pointed by BSI. HAS_RETURN is true if we also should
remove the return statement following the call. TMP_VARS is a list of
temporary variables used to copy the function arguments. */
static void
eliminate_tail_call (block_stmt_iterator bsi, bool has_return, tree tmp_vars)
{
tree param, stmt, args, tmp_var, label;
block_stmt_iterator bsi_s;
bool emit_label;
basic_block bb;
stmt = bsi_stmt (bsi);
bb = bb_for_stmt (stmt);
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");
}
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 (&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 (&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. */
bsi_s = bsi_start (ENTRY_BLOCK_PTR->succ->dest);
if (bsi_end_p (bsi_s) || TREE_CODE (bsi_stmt (bsi_s)) != LABEL_EXPR)
{
label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
DECL_ARTIFICIAL (label) = 1;
DECL_CONTEXT (label) = current_function_decl;
emit_label = true;
}
else
{
label = LABEL_EXPR_LABEL (bsi_stmt (bsi_s));
emit_label = false;
}
if (has_return)
bsi_remove (&bsi);
bsi_replace (bsi, build1 (GOTO_EXPR, void_type_node, label));
if (emit_label)
{
/* Emit the label; do it now, since otherwise we would conflict
with bsi in case the call is the first statement of the
program. */
bsi_s = bsi_start (ENTRY_BLOCK_PTR->succ->dest);
bsi_insert_before (&bsi_s,
build1 (LABEL_EXPR, void_type_node, label),
BSI_NEW_STMT);
}
/* Update the cfg. */
remove_edge (bb->succ);
make_edge (bb, ENTRY_BLOCK_PTR->succ->dest, 0);
}
/* Optimizes tail calls in the basic block BB. *TMP_VARS is set to a list of
temporary variables used to copy the function arguments the first time
they are needed. */
static void
bb_optimize_tail_calls (basic_block bb, tree *tmp_vars)
{
block_stmt_iterator bsi;
bool has_return;
tree tmp_var, param;
/* Find the tail call. Again, this should be more involved, catching
the cases when the call and return are not in the same block. */
if (!find_tail_call_p (bb, &bsi, &has_return))
return;
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 (bsi, has_return, *tmp_vars);
}
/* Optimizes tail calls in the function, turning the tail recursion
into iteration. */
void
tree_optimize_tail_calls ()
{
edge e, next;
tree tmp_vars = NULL_TREE;
if (!suitable_for_tail_opt_p ())
return;
dump_file = dump_begin (TDI_tail, &dump_flags);
for (e = EXIT_BLOCK_PTR->pred; e; e = next)
{
next = e->pred_next;
bb_optimize_tail_calls (e->src, &tmp_vars);
}
if (dump_file)
{
dump_function_to_file (current_function_decl, dump_file, dump_flags);
dump_end (TDI_tail, dump_file);
}
}