/* Tail call optimization on trees.
|
/* Tail call optimization on trees.
|
Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify
|
GCC is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful,
|
GCC is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "function.h"
|
#include "function.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "except.h"
|
#include "except.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "dbgcnt.h"
|
#include "dbgcnt.h"
|
|
|
/* The file implements the tail recursion elimination. It is also used to
|
/* The file implements the tail recursion elimination. It is also used to
|
analyze the tail calls in general, passing the results to the rtl level
|
analyze the tail calls in general, passing the results to the rtl level
|
where they are used for sibcall optimization.
|
where they are used for sibcall optimization.
|
|
|
In addition to the standard tail recursion elimination, we handle the most
|
In addition to the standard tail recursion elimination, we handle the most
|
trivial cases of making the call tail recursive by creating accumulators.
|
trivial cases of making the call tail recursive by creating accumulators.
|
For example the following function
|
For example the following function
|
|
|
int sum (int n)
|
int sum (int n)
|
{
|
{
|
if (n > 0)
|
if (n > 0)
|
return n + sum (n - 1);
|
return n + sum (n - 1);
|
else
|
else
|
return 0;
|
return 0;
|
}
|
}
|
|
|
is transformed into
|
is transformed into
|
|
|
int sum (int n)
|
int sum (int n)
|
{
|
{
|
int acc = 0;
|
int acc = 0;
|
|
|
while (n > 0)
|
while (n > 0)
|
acc += n--;
|
acc += n--;
|
|
|
return acc;
|
return acc;
|
}
|
}
|
|
|
To do this, we maintain two accumulators (a_acc and m_acc) that indicate
|
To do this, we maintain two accumulators (a_acc and m_acc) that indicate
|
when we reach the return x statement, we should return a_acc + x * m_acc
|
when we reach the return x statement, we should return a_acc + x * m_acc
|
instead. They are initially initialized to 0 and 1, respectively,
|
instead. They are initially initialized to 0 and 1, respectively,
|
so the semantics of the function is obviously preserved. If we are
|
so the semantics of the function is obviously preserved. If we are
|
guaranteed that the value of the accumulator never change, we
|
guaranteed that the value of the accumulator never change, we
|
omit the accumulator.
|
omit the accumulator.
|
|
|
There are three cases how the function may exit. The first one is
|
There are three cases how the function may exit. The first one is
|
handled in adjust_return_value, the other two in adjust_accumulator_values
|
handled in adjust_return_value, the other two in adjust_accumulator_values
|
(the second case is actually a special case of the third one and we
|
(the second case is actually a special case of the third one and we
|
present it separately just for clarity):
|
present it separately just for clarity):
|
|
|
1) Just return x, where x is not in any of the remaining special shapes.
|
1) Just return x, where x is not in any of the remaining special shapes.
|
We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
|
We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
|
|
|
2) return f (...), where f is the current function, is rewritten in a
|
2) return f (...), where f is the current function, is rewritten in a
|
classical tail-recursion elimination way, into assignment of arguments
|
classical tail-recursion elimination way, into assignment of arguments
|
and jump to the start of the function. Values of the accumulators
|
and jump to the start of the function. Values of the accumulators
|
are unchanged.
|
are unchanged.
|
|
|
3) return a + m * f(...), where a and m do not depend on call to f.
|
3) return a + m * f(...), where a and m do not depend on call to f.
|
To preserve the semantics described before we want this to be rewritten
|
To preserve the semantics described before we want this to be rewritten
|
in such a way that we finally return
|
in such a way that we finally return
|
|
|
a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
|
a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
|
|
|
I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
|
I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
|
eliminate the tail call to f. Special cases when the value is just
|
eliminate the tail call to f. Special cases when the value is just
|
added or just multiplied are obtained by setting a = 0 or m = 1.
|
added or just multiplied are obtained by setting a = 0 or m = 1.
|
|
|
TODO -- it is possible to do similar tricks for other operations. */
|
TODO -- it is possible to do similar tricks for other operations. */
|
|
|
/* A structure that describes the tailcall. */
|
/* A structure that describes the tailcall. */
|
|
|
struct tailcall
|
struct tailcall
|
{
|
{
|
/* The iterator pointing to the call statement. */
|
/* The iterator pointing to the call statement. */
|
gimple_stmt_iterator call_gsi;
|
gimple_stmt_iterator call_gsi;
|
|
|
/* True if it is a call to the current function. */
|
/* True if it is a call to the current function. */
|
bool tail_recursion;
|
bool tail_recursion;
|
|
|
/* The return value of the caller is mult * f + add, where f is the return
|
/* The return value of the caller is mult * f + add, where f is the return
|
value of the call. */
|
value of the call. */
|
tree mult, add;
|
tree mult, add;
|
|
|
/* Next tailcall in the chain. */
|
/* Next tailcall in the chain. */
|
struct tailcall *next;
|
struct tailcall *next;
|
};
|
};
|
|
|
/* The variables holding the value of multiplicative and additive
|
/* The variables holding the value of multiplicative and additive
|
accumulator. */
|
accumulator. */
|
static tree m_acc, a_acc;
|
static tree m_acc, a_acc;
|
|
|
static bool suitable_for_tail_opt_p (void);
|
static bool suitable_for_tail_opt_p (void);
|
static bool optimize_tail_call (struct tailcall *, bool);
|
static bool optimize_tail_call (struct tailcall *, bool);
|
static void eliminate_tail_call (struct tailcall *);
|
static void eliminate_tail_call (struct tailcall *);
|
static void find_tail_calls (basic_block, struct tailcall **);
|
static void find_tail_calls (basic_block, struct tailcall **);
|
|
|
/* Returns false when the function is not suitable for tail call optimization
|
/* Returns false when the function is not suitable for tail call optimization
|
from some reason (e.g. if it takes variable number of arguments). */
|
from some reason (e.g. if it takes variable number of arguments). */
|
|
|
static bool
|
static bool
|
suitable_for_tail_opt_p (void)
|
suitable_for_tail_opt_p (void)
|
{
|
{
|
referenced_var_iterator rvi;
|
referenced_var_iterator rvi;
|
tree var;
|
tree var;
|
|
|
if (cfun->stdarg)
|
if (cfun->stdarg)
|
return false;
|
return false;
|
|
|
/* No local variable nor structure field should be call-used. */
|
/* No local variable nor structure field should be call-used. */
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
{
|
{
|
if (!is_global_var (var)
|
if (!is_global_var (var)
|
&& is_call_used (var))
|
&& is_call_used (var))
|
return false;
|
return false;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
/* Returns false when the function is not suitable for tail call optimization
|
/* Returns false when the function is not suitable for tail call optimization
|
from some reason (e.g. if it takes variable number of arguments).
|
from some reason (e.g. if it takes variable number of arguments).
|
This test must pass in addition to suitable_for_tail_opt_p in order to make
|
This test must pass in addition to suitable_for_tail_opt_p in order to make
|
tail call discovery happen. */
|
tail call discovery happen. */
|
|
|
static bool
|
static bool
|
suitable_for_tail_call_opt_p (void)
|
suitable_for_tail_call_opt_p (void)
|
{
|
{
|
tree param;
|
tree param;
|
|
|
/* alloca (until we have stack slot life analysis) inhibits
|
/* alloca (until we have stack slot life analysis) inhibits
|
sibling call optimizations, but not tail recursion. */
|
sibling call optimizations, but not tail recursion. */
|
if (cfun->calls_alloca)
|
if (cfun->calls_alloca)
|
return false;
|
return false;
|
|
|
/* If we are using sjlj exceptions, we may need to add a call to
|
/* If we are using sjlj exceptions, we may need to add a call to
|
_Unwind_SjLj_Unregister at exit of the function. Which means
|
_Unwind_SjLj_Unregister at exit of the function. Which means
|
that we cannot do any sibcall transformations. */
|
that we cannot do any sibcall transformations. */
|
if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
|
if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
|
return false;
|
return false;
|
|
|
/* Any function that calls setjmp might have longjmp called from
|
/* Any function that calls setjmp might have longjmp called from
|
any called function. ??? We really should represent this
|
any called function. ??? We really should represent this
|
properly in the CFG so that this needn't be special cased. */
|
properly in the CFG so that this needn't be special cased. */
|
if (cfun->calls_setjmp)
|
if (cfun->calls_setjmp)
|
return false;
|
return false;
|
|
|
/* ??? It is OK if the argument of a function is taken in some cases,
|
/* ??? It is OK if the argument of a function is taken in some cases,
|
but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
|
but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */
|
for (param = DECL_ARGUMENTS (current_function_decl);
|
for (param = DECL_ARGUMENTS (current_function_decl);
|
param;
|
param;
|
param = TREE_CHAIN (param))
|
param = TREE_CHAIN (param))
|
if (TREE_ADDRESSABLE (param))
|
if (TREE_ADDRESSABLE (param))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Checks whether the expression EXPR in stmt AT is independent of the
|
/* Checks whether the expression EXPR in stmt AT is independent of the
|
statement pointed to by GSI (in a sense that we already know EXPR's value
|
statement pointed to by GSI (in a sense that we already know EXPR's value
|
at GSI). We use the fact that we are only called from the chain of
|
at GSI). We use the fact that we are only called from the chain of
|
basic blocks that have only single successor. Returns the expression
|
basic blocks that have only single successor. Returns the expression
|
containing the value of EXPR at GSI. */
|
containing the value of EXPR at GSI. */
|
|
|
static tree
|
static tree
|
independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
|
independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
|
{
|
{
|
basic_block bb, call_bb, at_bb;
|
basic_block bb, call_bb, at_bb;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (is_gimple_min_invariant (expr))
|
if (is_gimple_min_invariant (expr))
|
return expr;
|
return expr;
|
|
|
if (TREE_CODE (expr) != SSA_NAME)
|
if (TREE_CODE (expr) != SSA_NAME)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
/* Mark the blocks in the chain leading to the end. */
|
/* Mark the blocks in the chain leading to the end. */
|
at_bb = gimple_bb (at);
|
at_bb = gimple_bb (at);
|
call_bb = gimple_bb (gsi_stmt (gsi));
|
call_bb = gimple_bb (gsi_stmt (gsi));
|
for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
|
for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
|
bb->aux = &bb->aux;
|
bb->aux = &bb->aux;
|
bb->aux = &bb->aux;
|
bb->aux = &bb->aux;
|
|
|
while (1)
|
while (1)
|
{
|
{
|
at = SSA_NAME_DEF_STMT (expr);
|
at = SSA_NAME_DEF_STMT (expr);
|
bb = gimple_bb (at);
|
bb = gimple_bb (at);
|
|
|
/* The default definition or defined before the chain. */
|
/* The default definition or defined before the chain. */
|
if (!bb || !bb->aux)
|
if (!bb || !bb->aux)
|
break;
|
break;
|
|
|
if (bb == call_bb)
|
if (bb == call_bb)
|
{
|
{
|
for (; !gsi_end_p (gsi); gsi_next (&gsi))
|
for (; !gsi_end_p (gsi); gsi_next (&gsi))
|
if (gsi_stmt (gsi) == at)
|
if (gsi_stmt (gsi) == at)
|
break;
|
break;
|
|
|
if (!gsi_end_p (gsi))
|
if (!gsi_end_p (gsi))
|
expr = NULL_TREE;
|
expr = NULL_TREE;
|
break;
|
break;
|
}
|
}
|
|
|
if (gimple_code (at) != GIMPLE_PHI)
|
if (gimple_code (at) != GIMPLE_PHI)
|
{
|
{
|
expr = NULL_TREE;
|
expr = NULL_TREE;
|
break;
|
break;
|
}
|
}
|
|
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
if (e->src->aux)
|
if (e->src->aux)
|
break;
|
break;
|
gcc_assert (e);
|
gcc_assert (e);
|
|
|
expr = PHI_ARG_DEF_FROM_EDGE (at, e);
|
expr = PHI_ARG_DEF_FROM_EDGE (at, e);
|
if (TREE_CODE (expr) != SSA_NAME)
|
if (TREE_CODE (expr) != SSA_NAME)
|
{
|
{
|
/* The value is a constant. */
|
/* The value is a constant. */
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
/* Unmark the blocks. */
|
/* Unmark the blocks. */
|
for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
|
for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
|
bb->aux = NULL;
|
bb->aux = NULL;
|
bb->aux = NULL;
|
bb->aux = NULL;
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
/* Simulates the effect of an assignment STMT on the return value of the tail
|
/* Simulates the effect of an assignment STMT on the return value of the tail
|
recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
|
recursive CALL passed in ASS_VAR. M and A are the multiplicative and the
|
additive factor for the real return value. */
|
additive factor for the real return value. */
|
|
|
static bool
|
static bool
|
process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
|
process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
|
tree *a, tree *ass_var)
|
tree *a, tree *ass_var)
|
{
|
{
|
tree op0, op1, non_ass_var;
|
tree op0, op1, non_ass_var;
|
tree dest = gimple_assign_lhs (stmt);
|
tree dest = gimple_assign_lhs (stmt);
|
enum tree_code code = gimple_assign_rhs_code (stmt);
|
enum tree_code code = gimple_assign_rhs_code (stmt);
|
enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
|
enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
|
tree src_var = gimple_assign_rhs1 (stmt);
|
tree src_var = gimple_assign_rhs1 (stmt);
|
|
|
/* See if this is a simple copy operation of an SSA name to the function
|
/* See if this is a simple copy operation of an SSA name to the function
|
result. In that case we may have a simple tail call. Ignore type
|
result. In that case we may have a simple tail call. Ignore type
|
conversions that can never produce extra code between the function
|
conversions that can never produce extra code between the function
|
call and the function return. */
|
call and the function return. */
|
if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
|
if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
|
&& (TREE_CODE (src_var) == SSA_NAME))
|
&& (TREE_CODE (src_var) == SSA_NAME))
|
{
|
{
|
/* Reject a tailcall if the type conversion might need
|
/* Reject a tailcall if the type conversion might need
|
additional code. */
|
additional code. */
|
if (gimple_assign_cast_p (stmt)
|
if (gimple_assign_cast_p (stmt)
|
&& TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
|
&& TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
|
return false;
|
return false;
|
|
|
if (src_var != *ass_var)
|
if (src_var != *ass_var)
|
return false;
|
return false;
|
|
|
*ass_var = dest;
|
*ass_var = dest;
|
return true;
|
return true;
|
}
|
}
|
|
|
if (rhs_class != GIMPLE_BINARY_RHS)
|
if (rhs_class != GIMPLE_BINARY_RHS)
|
return false;
|
return false;
|
|
|
/* Accumulator optimizations will reverse the order of operations.
|
/* Accumulator optimizations will reverse the order of operations.
|
We can only do that for floating-point types if we're assuming
|
We can only do that for floating-point types if we're assuming
|
that addition and multiplication are associative. */
|
that addition and multiplication are associative. */
|
if (!flag_associative_math)
|
if (!flag_associative_math)
|
if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
|
if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
|
return false;
|
return false;
|
|
|
/* We only handle the code like
|
/* We only handle the code like
|
|
|
x = call ();
|
x = call ();
|
y = m * x;
|
y = m * x;
|
z = y + a;
|
z = y + a;
|
return z;
|
return z;
|
|
|
TODO -- Extend it for cases where the linear transformation of the output
|
TODO -- Extend it for cases where the linear transformation of the output
|
is expressed in a more complicated way. */
|
is expressed in a more complicated way. */
|
|
|
op0 = gimple_assign_rhs1 (stmt);
|
op0 = gimple_assign_rhs1 (stmt);
|
op1 = gimple_assign_rhs2 (stmt);
|
op1 = gimple_assign_rhs2 (stmt);
|
|
|
if (op0 == *ass_var
|
if (op0 == *ass_var
|
&& (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
|
&& (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
|
;
|
;
|
else if (op1 == *ass_var
|
else if (op1 == *ass_var
|
&& (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
|
&& (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
|
;
|
;
|
else
|
else
|
return false;
|
return false;
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
*a = non_ass_var;
|
*a = non_ass_var;
|
*ass_var = dest;
|
*ass_var = dest;
|
return true;
|
return true;
|
|
|
case MULT_EXPR:
|
case MULT_EXPR:
|
*m = non_ass_var;
|
*m = non_ass_var;
|
*ass_var = dest;
|
*ass_var = dest;
|
return true;
|
return true;
|
|
|
/* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
|
/* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
|
POINTER_PLUS_EXPR). */
|
POINTER_PLUS_EXPR). */
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
/* Propagate VAR through phis on edge E. */
|
/* Propagate VAR through phis on edge E. */
|
|
|
static tree
|
static tree
|
propagate_through_phis (tree var, edge e)
|
propagate_through_phis (tree var, edge e)
|
{
|
{
|
basic_block dest = e->dest;
|
basic_block dest = e->dest;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
gimple phi = gsi_stmt (gsi);
|
gimple phi = gsi_stmt (gsi);
|
if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
|
if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
|
return PHI_RESULT (phi);
|
return PHI_RESULT (phi);
|
}
|
}
|
return var;
|
return var;
|
}
|
}
|
|
|
/* Finds tailcalls falling into basic block BB. The list of found tailcalls is
|
/* Finds tailcalls falling into basic block BB. The list of found tailcalls is
|
added to the start of RET. */
|
added to the start of RET. */
|
|
|
static void
|
static void
|
find_tail_calls (basic_block bb, struct tailcall **ret)
|
find_tail_calls (basic_block bb, struct tailcall **ret)
|
{
|
{
|
tree ass_var = NULL_TREE, ret_var, func, param;
|
tree ass_var = NULL_TREE, ret_var, func, param;
|
gimple stmt, call = NULL;
|
gimple stmt, call = NULL;
|
gimple_stmt_iterator gsi, agsi;
|
gimple_stmt_iterator gsi, agsi;
|
bool tail_recursion;
|
bool tail_recursion;
|
struct tailcall *nw;
|
struct tailcall *nw;
|
edge e;
|
edge e;
|
tree m, a;
|
tree m, a;
|
basic_block abb;
|
basic_block abb;
|
size_t idx;
|
size_t idx;
|
tree var;
|
tree var;
|
referenced_var_iterator rvi;
|
referenced_var_iterator rvi;
|
|
|
if (!single_succ_p (bb))
|
if (!single_succ_p (bb))
|
return;
|
return;
|
|
|
for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
|
for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
|
{
|
{
|
stmt = gsi_stmt (gsi);
|
stmt = gsi_stmt (gsi);
|
|
|
/* Ignore labels. */
|
/* Ignore labels. */
|
if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt))
|
if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt))
|
continue;
|
continue;
|
|
|
/* Check for a call. */
|
/* Check for a call. */
|
if (is_gimple_call (stmt))
|
if (is_gimple_call (stmt))
|
{
|
{
|
call = stmt;
|
call = stmt;
|
ass_var = gimple_call_lhs (stmt);
|
ass_var = gimple_call_lhs (stmt);
|
break;
|
break;
|
}
|
}
|
|
|
/* If the statement references memory or volatile operands, fail. */
|
/* If the statement references memory or volatile operands, fail. */
|
if (gimple_references_memory_p (stmt)
|
if (gimple_references_memory_p (stmt)
|
|| gimple_has_volatile_ops (stmt))
|
|| gimple_has_volatile_ops (stmt))
|
return;
|
return;
|
}
|
}
|
|
|
if (gsi_end_p (gsi))
|
if (gsi_end_p (gsi))
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
/* Recurse to the predecessors. */
|
/* Recurse to the predecessors. */
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
find_tail_calls (e->src, ret);
|
find_tail_calls (e->src, ret);
|
|
|
return;
|
return;
|
}
|
}
|
|
|
/* If the LHS of our call is not just a simple register, we can't
|
/* If the LHS of our call is not just a simple register, we can't
|
transform this into a tail or sibling call. This situation happens,
|
transform this into a tail or sibling call. This situation happens,
|
in (e.g.) "*p = foo()" where foo returns a struct. In this case
|
in (e.g.) "*p = foo()" where foo returns a struct. In this case
|
we won't have a temporary here, but we need to carry out the side
|
we won't have a temporary here, but we need to carry out the side
|
effect anyway, so tailcall is impossible.
|
effect anyway, so tailcall is impossible.
|
|
|
??? In some situations (when the struct is returned in memory via
|
??? In some situations (when the struct is returned in memory via
|
invisible argument) we could deal with this, e.g. by passing 'p'
|
invisible argument) we could deal with this, e.g. by passing 'p'
|
itself as that argument to foo, but it's too early to do this here,
|
itself as that argument to foo, but it's too early to do this here,
|
and expand_call() will not handle it anyway. If it ever can, then
|
and expand_call() will not handle it anyway. If it ever can, then
|
we need to revisit this here, to allow that situation. */
|
we need to revisit this here, to allow that situation. */
|
if (ass_var && !is_gimple_reg (ass_var))
|
if (ass_var && !is_gimple_reg (ass_var))
|
return;
|
return;
|
|
|
/* We found the call, check whether it is suitable. */
|
/* We found the call, check whether it is suitable. */
|
tail_recursion = false;
|
tail_recursion = false;
|
func = gimple_call_fndecl (call);
|
func = gimple_call_fndecl (call);
|
if (func == current_function_decl)
|
if (func == current_function_decl)
|
{
|
{
|
tree arg;
|
tree arg;
|
for (param = DECL_ARGUMENTS (func), idx = 0;
|
for (param = DECL_ARGUMENTS (func), idx = 0;
|
param && idx < gimple_call_num_args (call);
|
param && idx < gimple_call_num_args (call);
|
param = TREE_CHAIN (param), idx ++)
|
param = TREE_CHAIN (param), idx ++)
|
{
|
{
|
arg = gimple_call_arg (call, idx);
|
arg = gimple_call_arg (call, idx);
|
if (param != arg)
|
if (param != arg)
|
{
|
{
|
/* Make sure there are no problems with copying. The parameter
|
/* Make sure there are no problems with copying. The parameter
|
have a copyable type and the two arguments must have reasonably
|
have a copyable type and the two arguments must have reasonably
|
equivalent types. The latter requirement could be relaxed if
|
equivalent types. The latter requirement could be relaxed if
|
we emitted a suitable type conversion statement. */
|
we emitted a suitable type conversion statement. */
|
if (!is_gimple_reg_type (TREE_TYPE (param))
|
if (!is_gimple_reg_type (TREE_TYPE (param))
|
|| !useless_type_conversion_p (TREE_TYPE (param),
|
|| !useless_type_conversion_p (TREE_TYPE (param),
|
TREE_TYPE (arg)))
|
TREE_TYPE (arg)))
|
break;
|
break;
|
|
|
/* The parameter should be a real operand, so that phi node
|
/* The parameter should be a real operand, so that phi node
|
created for it at the start of the function has the meaning
|
created for it at the start of the function has the meaning
|
of copying the value. This test implies is_gimple_reg_type
|
of copying the value. This test implies is_gimple_reg_type
|
from the previous condition, however this one could be
|
from the previous condition, however this one could be
|
relaxed by being more careful with copying the new value
|
relaxed by being more careful with copying the new value
|
of the parameter (emitting appropriate GIMPLE_ASSIGN and
|
of the parameter (emitting appropriate GIMPLE_ASSIGN and
|
updating the virtual operands). */
|
updating the virtual operands). */
|
if (!is_gimple_reg (param))
|
if (!is_gimple_reg (param))
|
break;
|
break;
|
}
|
}
|
}
|
}
|
if (idx == gimple_call_num_args (call) && !param)
|
if (idx == gimple_call_num_args (call) && !param)
|
tail_recursion = true;
|
tail_recursion = true;
|
}
|
}
|
|
|
/* Make sure the tail invocation of this function does not refer
|
/* Make sure the tail invocation of this function does not refer
|
to local variables. */
|
to local variables. */
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
{
|
{
|
if (TREE_CODE (var) != PARM_DECL
|
if (TREE_CODE (var) != PARM_DECL
|
&& auto_var_in_fn_p (var, cfun->decl)
|
&& auto_var_in_fn_p (var, cfun->decl)
|
&& ref_maybe_used_by_stmt_p (call, var))
|
&& ref_maybe_used_by_stmt_p (call, var))
|
return;
|
return;
|
}
|
}
|
|
|
/* Now check the statements after the call. None of them has virtual
|
/* Now check the statements after the call. None of them has virtual
|
operands, so they may only depend on the call through its return
|
operands, so they may only depend on the call through its return
|
value. The return value should also be dependent on each of them,
|
value. The return value should also be dependent on each of them,
|
since we are running after dce. */
|
since we are running after dce. */
|
m = NULL_TREE;
|
m = NULL_TREE;
|
a = NULL_TREE;
|
a = NULL_TREE;
|
|
|
abb = bb;
|
abb = bb;
|
agsi = gsi;
|
agsi = gsi;
|
while (1)
|
while (1)
|
{
|
{
|
tree tmp_a = NULL_TREE;
|
tree tmp_a = NULL_TREE;
|
tree tmp_m = NULL_TREE;
|
tree tmp_m = NULL_TREE;
|
gsi_next (&agsi);
|
gsi_next (&agsi);
|
|
|
while (gsi_end_p (agsi))
|
while (gsi_end_p (agsi))
|
{
|
{
|
ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
|
ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
|
abb = single_succ (abb);
|
abb = single_succ (abb);
|
agsi = gsi_start_bb (abb);
|
agsi = gsi_start_bb (abb);
|
}
|
}
|
|
|
stmt = gsi_stmt (agsi);
|
stmt = gsi_stmt (agsi);
|
|
|
if (gimple_code (stmt) == GIMPLE_LABEL)
|
if (gimple_code (stmt) == GIMPLE_LABEL)
|
continue;
|
continue;
|
|
|
if (gimple_code (stmt) == GIMPLE_RETURN)
|
if (gimple_code (stmt) == GIMPLE_RETURN)
|
break;
|
break;
|
|
|
if (is_gimple_debug (stmt))
|
if (is_gimple_debug (stmt))
|
continue;
|
continue;
|
|
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
return;
|
return;
|
|
|
/* This is a gimple assign. */
|
/* This is a gimple assign. */
|
if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
|
if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
|
return;
|
return;
|
|
|
if (tmp_a)
|
if (tmp_a)
|
{
|
{
|
if (a)
|
if (a)
|
a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a);
|
a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a);
|
else
|
else
|
a = tmp_a;
|
a = tmp_a;
|
}
|
}
|
if (tmp_m)
|
if (tmp_m)
|
{
|
{
|
if (m)
|
if (m)
|
m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m);
|
m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m);
|
else
|
else
|
m = tmp_m;
|
m = tmp_m;
|
|
|
if (a)
|
if (a)
|
a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m);
|
a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m);
|
}
|
}
|
}
|
}
|
|
|
/* See if this is a tail call we can handle. */
|
/* See if this is a tail call we can handle. */
|
ret_var = gimple_return_retval (stmt);
|
ret_var = gimple_return_retval (stmt);
|
|
|
/* We may proceed if there either is no return value, or the return value
|
/* We may proceed if there either is no return value, or the return value
|
is identical to the call's return. */
|
is identical to the call's return. */
|
if (ret_var
|
if (ret_var
|
&& (ret_var != ass_var))
|
&& (ret_var != ass_var))
|
return;
|
return;
|
|
|
/* If this is not a tail recursive call, we cannot handle addends or
|
/* If this is not a tail recursive call, we cannot handle addends or
|
multiplicands. */
|
multiplicands. */
|
if (!tail_recursion && (m || a))
|
if (!tail_recursion && (m || a))
|
return;
|
return;
|
|
|
nw = XNEW (struct tailcall);
|
nw = XNEW (struct tailcall);
|
|
|
nw->call_gsi = gsi;
|
nw->call_gsi = gsi;
|
|
|
nw->tail_recursion = tail_recursion;
|
nw->tail_recursion = tail_recursion;
|
|
|
nw->mult = m;
|
nw->mult = m;
|
nw->add = a;
|
nw->add = a;
|
|
|
nw->next = *ret;
|
nw->next = *ret;
|
*ret = nw;
|
*ret = nw;
|
}
|
}
|
|
|
/* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
|
/* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */
|
|
|
static void
|
static void
|
add_successor_phi_arg (edge e, tree var, tree phi_arg)
|
add_successor_phi_arg (edge e, tree var, tree phi_arg)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
if (PHI_RESULT (gsi_stmt (gsi)) == var)
|
if (PHI_RESULT (gsi_stmt (gsi)) == var)
|
break;
|
break;
|
|
|
gcc_assert (!gsi_end_p (gsi));
|
gcc_assert (!gsi_end_p (gsi));
|
add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
|
add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
|
}
|
}
|
|
|
/* Creates a GIMPLE statement which computes the operation specified by
|
/* Creates a GIMPLE statement which computes the operation specified by
|
CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
|
CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
|
statement in the position specified by GSI and UPDATE. Returns the
|
statement in the position specified by GSI and UPDATE. Returns the
|
tree node of the statement's result. */
|
tree node of the statement's result. */
|
|
|
static tree
|
static tree
|
adjust_return_value_with_ops (enum tree_code code, const char *label,
|
adjust_return_value_with_ops (enum tree_code code, const char *label,
|
tree acc, tree op1, gimple_stmt_iterator gsi)
|
tree acc, tree op1, gimple_stmt_iterator gsi)
|
{
|
{
|
|
|
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
|
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
|
tree tmp = create_tmp_var (ret_type, label);
|
tree tmp = create_tmp_var (ret_type, label);
|
gimple stmt;
|
gimple stmt;
|
tree result;
|
tree result;
|
|
|
if (TREE_CODE (ret_type) == COMPLEX_TYPE
|
if (TREE_CODE (ret_type) == COMPLEX_TYPE
|
|| TREE_CODE (ret_type) == VECTOR_TYPE)
|
|| TREE_CODE (ret_type) == VECTOR_TYPE)
|
DECL_GIMPLE_REG_P (tmp) = 1;
|
DECL_GIMPLE_REG_P (tmp) = 1;
|
add_referenced_var (tmp);
|
add_referenced_var (tmp);
|
|
|
if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
|
if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
|
stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
|
stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
|
else
|
else
|
{
|
{
|
tree rhs = fold_convert (TREE_TYPE (acc),
|
tree rhs = fold_convert (TREE_TYPE (acc),
|
fold_build2 (code,
|
fold_build2 (code,
|
TREE_TYPE (op1),
|
TREE_TYPE (op1),
|
fold_convert (TREE_TYPE (op1), acc),
|
fold_convert (TREE_TYPE (op1), acc),
|
op1));
|
op1));
|
rhs = force_gimple_operand_gsi (&gsi, rhs,
|
rhs = force_gimple_operand_gsi (&gsi, rhs,
|
false, NULL, true, GSI_CONTINUE_LINKING);
|
false, NULL, true, GSI_CONTINUE_LINKING);
|
stmt = gimple_build_assign (NULL_TREE, rhs);
|
stmt = gimple_build_assign (NULL_TREE, rhs);
|
}
|
}
|
|
|
result = make_ssa_name (tmp, stmt);
|
result = make_ssa_name (tmp, stmt);
|
gimple_assign_set_lhs (stmt, result);
|
gimple_assign_set_lhs (stmt, result);
|
update_stmt (stmt);
|
update_stmt (stmt);
|
gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
|
gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
|
return result;
|
return result;
|
}
|
}
|
|
|
/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
|
/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
|
the computation specified by CODE and OP1 and insert the statement
|
the computation specified by CODE and OP1 and insert the statement
|
at the position specified by GSI as a new statement. Returns new SSA name
|
at the position specified by GSI as a new statement. Returns new SSA name
|
of updated accumulator. */
|
of updated accumulator. */
|
|
|
static tree
|
static tree
|
update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
|
update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
|
gimple_stmt_iterator gsi)
|
gimple_stmt_iterator gsi)
|
{
|
{
|
gimple stmt;
|
gimple stmt;
|
tree var;
|
tree var;
|
if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
|
if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
|
stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1);
|
stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1);
|
else
|
else
|
{
|
{
|
tree rhs = fold_convert (TREE_TYPE (acc),
|
tree rhs = fold_convert (TREE_TYPE (acc),
|
fold_build2 (code,
|
fold_build2 (code,
|
TREE_TYPE (op1),
|
TREE_TYPE (op1),
|
fold_convert (TREE_TYPE (op1), acc),
|
fold_convert (TREE_TYPE (op1), acc),
|
op1));
|
op1));
|
rhs = force_gimple_operand_gsi (&gsi, rhs,
|
rhs = force_gimple_operand_gsi (&gsi, rhs,
|
false, NULL, false, GSI_CONTINUE_LINKING);
|
false, NULL, false, GSI_CONTINUE_LINKING);
|
stmt = gimple_build_assign (NULL_TREE, rhs);
|
stmt = gimple_build_assign (NULL_TREE, rhs);
|
}
|
}
|
var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
|
var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
|
gimple_assign_set_lhs (stmt, var);
|
gimple_assign_set_lhs (stmt, var);
|
update_stmt (stmt);
|
update_stmt (stmt);
|
gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
return var;
|
return var;
|
}
|
}
|
|
|
/* Adjust the accumulator values according to A and M after GSI, and update
|
/* Adjust the accumulator values according to A and M after GSI, and update
|
the phi nodes on edge BACK. */
|
the phi nodes on edge BACK. */
|
|
|
static void
|
static void
|
adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
|
adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
|
{
|
{
|
tree var, a_acc_arg, m_acc_arg;
|
tree var, a_acc_arg, m_acc_arg;
|
|
|
if (m)
|
if (m)
|
m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
|
m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
|
if (a)
|
if (a)
|
a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
|
a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
|
|
|
a_acc_arg = a_acc;
|
a_acc_arg = a_acc;
|
m_acc_arg = m_acc;
|
m_acc_arg = m_acc;
|
if (a)
|
if (a)
|
{
|
{
|
if (m_acc)
|
if (m_acc)
|
{
|
{
|
if (integer_onep (a))
|
if (integer_onep (a))
|
var = m_acc;
|
var = m_acc;
|
else
|
else
|
var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
|
var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
|
a, gsi);
|
a, gsi);
|
}
|
}
|
else
|
else
|
var = a;
|
var = a;
|
|
|
a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
|
a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
|
}
|
}
|
|
|
if (m)
|
if (m)
|
m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
|
m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
|
|
|
if (a_acc)
|
if (a_acc)
|
add_successor_phi_arg (back, a_acc, a_acc_arg);
|
add_successor_phi_arg (back, a_acc, a_acc_arg);
|
|
|
if (m_acc)
|
if (m_acc)
|
add_successor_phi_arg (back, m_acc, m_acc_arg);
|
add_successor_phi_arg (back, m_acc, m_acc_arg);
|
}
|
}
|
|
|
/* Adjust value of the return at the end of BB according to M and A
|
/* Adjust value of the return at the end of BB according to M and A
|
accumulators. */
|
accumulators. */
|
|
|
static void
|
static void
|
adjust_return_value (basic_block bb, tree m, tree a)
|
adjust_return_value (basic_block bb, tree m, tree a)
|
{
|
{
|
tree retval;
|
tree retval;
|
gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
|
gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
|
gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
|
|
gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
|
gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
|
|
|
retval = gimple_return_retval (ret_stmt);
|
retval = gimple_return_retval (ret_stmt);
|
if (!retval || retval == error_mark_node)
|
if (!retval || retval == error_mark_node)
|
return;
|
return;
|
|
|
if (m)
|
if (m)
|
retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
|
retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
|
gsi);
|
gsi);
|
if (a)
|
if (a)
|
retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
|
retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
|
gsi);
|
gsi);
|
gimple_return_set_retval (ret_stmt, retval);
|
gimple_return_set_retval (ret_stmt, retval);
|
update_stmt (ret_stmt);
|
update_stmt (ret_stmt);
|
}
|
}
|
|
|
/* Subtract COUNT and FREQUENCY from the basic block and it's
|
/* Subtract COUNT and FREQUENCY from the basic block and it's
|
outgoing edge. */
|
outgoing edge. */
|
static void
|
static void
|
decrease_profile (basic_block bb, gcov_type count, int frequency)
|
decrease_profile (basic_block bb, gcov_type count, int frequency)
|
{
|
{
|
edge e;
|
edge e;
|
bb->count -= count;
|
bb->count -= count;
|
if (bb->count < 0)
|
if (bb->count < 0)
|
bb->count = 0;
|
bb->count = 0;
|
bb->frequency -= frequency;
|
bb->frequency -= frequency;
|
if (bb->frequency < 0)
|
if (bb->frequency < 0)
|
bb->frequency = 0;
|
bb->frequency = 0;
|
if (!single_succ_p (bb))
|
if (!single_succ_p (bb))
|
{
|
{
|
gcc_assert (!EDGE_COUNT (bb->succs));
|
gcc_assert (!EDGE_COUNT (bb->succs));
|
return;
|
return;
|
}
|
}
|
e = single_succ_edge (bb);
|
e = single_succ_edge (bb);
|
e->count -= count;
|
e->count -= count;
|
if (e->count < 0)
|
if (e->count < 0)
|
e->count = 0;
|
e->count = 0;
|
}
|
}
|
|
|
/* Returns true if argument PARAM of the tail recursive call needs to be copied
|
/* Returns true if argument PARAM of the tail recursive call needs to be copied
|
when the call is eliminated. */
|
when the call is eliminated. */
|
|
|
static bool
|
static bool
|
arg_needs_copy_p (tree param)
|
arg_needs_copy_p (tree param)
|
{
|
{
|
tree def;
|
tree def;
|
|
|
if (!is_gimple_reg (param) || !var_ann (param))
|
if (!is_gimple_reg (param) || !var_ann (param))
|
return false;
|
return false;
|
|
|
/* Parameters that are only defined but never used need not be copied. */
|
/* Parameters that are only defined but never used need not be copied. */
|
def = gimple_default_def (cfun, param);
|
def = gimple_default_def (cfun, param);
|
if (!def)
|
if (!def)
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Eliminates tail call described by T. TMP_VARS is a list of
|
/* Eliminates tail call described by T. TMP_VARS is a list of
|
temporary variables used to copy the function arguments. */
|
temporary variables used to copy the function arguments. */
|
|
|
static void
|
static void
|
eliminate_tail_call (struct tailcall *t)
|
eliminate_tail_call (struct tailcall *t)
|
{
|
{
|
tree param, rslt;
|
tree param, rslt;
|
gimple stmt, call;
|
gimple stmt, call;
|
tree arg;
|
tree arg;
|
size_t idx;
|
size_t idx;
|
basic_block bb, first;
|
basic_block bb, first;
|
edge e;
|
edge e;
|
gimple phi;
|
gimple phi;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
gimple orig_stmt;
|
gimple orig_stmt;
|
|
|
stmt = orig_stmt = gsi_stmt (t->call_gsi);
|
stmt = orig_stmt = gsi_stmt (t->call_gsi);
|
bb = gsi_bb (t->call_gsi);
|
bb = gsi_bb (t->call_gsi);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
|
fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
|
bb->index);
|
bb->index);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
gcc_assert (is_gimple_call (stmt));
|
gcc_assert (is_gimple_call (stmt));
|
|
|
first = single_succ (ENTRY_BLOCK_PTR);
|
first = single_succ (ENTRY_BLOCK_PTR);
|
|
|
/* Remove the code after call_gsi that will become unreachable. The
|
/* Remove the code after call_gsi that will become unreachable. The
|
possibly unreachable code in other blocks is removed later in
|
possibly unreachable code in other blocks is removed later in
|
cfg cleanup. */
|
cfg cleanup. */
|
gsi = t->call_gsi;
|
gsi = t->call_gsi;
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
while (!gsi_end_p (gsi))
|
while (!gsi_end_p (gsi))
|
{
|
{
|
gimple t = gsi_stmt (gsi);
|
gimple t = gsi_stmt (gsi);
|
/* Do not remove the return statement, so that redirect_edge_and_branch
|
/* Do not remove the return statement, so that redirect_edge_and_branch
|
sees how the block ends. */
|
sees how the block ends. */
|
if (gimple_code (t) == GIMPLE_RETURN)
|
if (gimple_code (t) == GIMPLE_RETURN)
|
break;
|
break;
|
|
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
release_defs (t);
|
release_defs (t);
|
}
|
}
|
|
|
/* Number of executions of function has reduced by the tailcall. */
|
/* Number of executions of function has reduced by the tailcall. */
|
e = single_succ_edge (gsi_bb (t->call_gsi));
|
e = single_succ_edge (gsi_bb (t->call_gsi));
|
decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
|
decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
|
decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
|
decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
|
if (e->dest != EXIT_BLOCK_PTR)
|
if (e->dest != EXIT_BLOCK_PTR)
|
decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
|
decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
|
|
|
/* Replace the call by a jump to the start of function. */
|
/* Replace the call by a jump to the start of function. */
|
e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
|
e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
|
first);
|
first);
|
gcc_assert (e);
|
gcc_assert (e);
|
PENDING_STMT (e) = NULL;
|
PENDING_STMT (e) = NULL;
|
|
|
/* Add phi node entries for arguments. The ordering of the phi nodes should
|
/* Add phi node entries for arguments. The ordering of the phi nodes should
|
be the same as the ordering of the arguments. */
|
be the same as the ordering of the arguments. */
|
for (param = DECL_ARGUMENTS (current_function_decl),
|
for (param = DECL_ARGUMENTS (current_function_decl),
|
idx = 0, gsi = gsi_start_phis (first);
|
idx = 0, gsi = gsi_start_phis (first);
|
param;
|
param;
|
param = TREE_CHAIN (param), idx++)
|
param = TREE_CHAIN (param), idx++)
|
{
|
{
|
if (!arg_needs_copy_p (param))
|
if (!arg_needs_copy_p (param))
|
continue;
|
continue;
|
|
|
arg = gimple_call_arg (stmt, idx);
|
arg = gimple_call_arg (stmt, idx);
|
phi = gsi_stmt (gsi);
|
phi = gsi_stmt (gsi);
|
gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
|
gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
|
|
|
add_phi_arg (phi, arg, e, gimple_location (stmt));
|
add_phi_arg (phi, arg, e, gimple_location (stmt));
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
}
|
}
|
|
|
/* Update the values of accumulators. */
|
/* Update the values of accumulators. */
|
adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
|
adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
|
|
|
call = gsi_stmt (t->call_gsi);
|
call = gsi_stmt (t->call_gsi);
|
rslt = gimple_call_lhs (call);
|
rslt = gimple_call_lhs (call);
|
if (rslt != NULL_TREE)
|
if (rslt != NULL_TREE)
|
{
|
{
|
/* Result of the call will no longer be defined. So adjust the
|
/* Result of the call will no longer be defined. So adjust the
|
SSA_NAME_DEF_STMT accordingly. */
|
SSA_NAME_DEF_STMT accordingly. */
|
SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
|
SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
|
}
|
}
|
|
|
gsi_remove (&t->call_gsi, true);
|
gsi_remove (&t->call_gsi, true);
|
release_defs (call);
|
release_defs (call);
|
}
|
}
|
|
|
/* Add phi nodes for the virtual operands defined in the function to the
|
/* Add phi nodes for the virtual operands defined in the function to the
|
header of the loop created by tail recursion elimination.
|
header of the loop created by tail recursion elimination.
|
|
|
Originally, we used to add phi nodes only for call clobbered variables,
|
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
|
as the value of the non-call clobbered ones obviously cannot be used
|
or changed within the recursive call. However, the local variables
|
or changed within the recursive call. However, the local variables
|
from multiple calls now share the same location, so the virtual ssa form
|
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,
|
requires us to say that the location dies on further iterations of the loop,
|
which requires adding phi nodes.
|
which requires adding phi nodes.
|
*/
|
*/
|
static void
|
static void
|
add_virtual_phis (void)
|
add_virtual_phis (void)
|
{
|
{
|
referenced_var_iterator rvi;
|
referenced_var_iterator rvi;
|
tree var;
|
tree var;
|
|
|
/* The problematic part is that there is no way how to know what
|
/* 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
|
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
|
ssa name available). A solution would be to have an artificial
|
use/kill for all virtual operands in EXIT node. Unless we have
|
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
|
this, we cannot do much better than to rebuild the ssa form for
|
possibly affected virtual ssa names from scratch. */
|
possibly affected virtual ssa names from scratch. */
|
|
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
{
|
{
|
if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
|
if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
|
mark_sym_for_renaming (var);
|
mark_sym_for_renaming (var);
|
}
|
}
|
}
|
}
|
|
|
/* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
|
/* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
|
mark the tailcalls for the sibcall optimization. */
|
mark the tailcalls for the sibcall optimization. */
|
|
|
static bool
|
static bool
|
optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
|
optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
|
{
|
{
|
if (t->tail_recursion)
|
if (t->tail_recursion)
|
{
|
{
|
eliminate_tail_call (t);
|
eliminate_tail_call (t);
|
return true;
|
return true;
|
}
|
}
|
|
|
if (opt_tailcalls)
|
if (opt_tailcalls)
|
{
|
{
|
gimple stmt = gsi_stmt (t->call_gsi);
|
gimple stmt = gsi_stmt (t->call_gsi);
|
|
|
gimple_call_set_tail (stmt, true);
|
gimple_call_set_tail (stmt, true);
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Found tail call ");
|
fprintf (dump_file, "Found tail call ");
|
print_gimple_stmt (dump_file, stmt, 0, dump_flags);
|
print_gimple_stmt (dump_file, stmt, 0, dump_flags);
|
fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
|
fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
|
}
|
}
|
}
|
}
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Creates a tail-call accumulator of the same type as the return type of the
|
/* Creates a tail-call accumulator of the same type as the return type of the
|
current function. LABEL is the name used to creating the temporary
|
current function. LABEL is the name used to creating the temporary
|
variable for the accumulator. The accumulator will be inserted in the
|
variable for the accumulator. The accumulator will be inserted in the
|
phis of a basic block BB with single predecessor with an initial value
|
phis of a basic block BB with single predecessor with an initial value
|
INIT converted to the current function return type. */
|
INIT converted to the current function return type. */
|
|
|
static tree
|
static tree
|
create_tailcall_accumulator (const char *label, basic_block bb, tree init)
|
create_tailcall_accumulator (const char *label, basic_block bb, tree init)
|
{
|
{
|
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
|
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
|
tree tmp = create_tmp_var (ret_type, label);
|
tree tmp = create_tmp_var (ret_type, label);
|
gimple phi;
|
gimple phi;
|
|
|
if (TREE_CODE (ret_type) == COMPLEX_TYPE
|
if (TREE_CODE (ret_type) == COMPLEX_TYPE
|
|| TREE_CODE (ret_type) == VECTOR_TYPE)
|
|| TREE_CODE (ret_type) == VECTOR_TYPE)
|
DECL_GIMPLE_REG_P (tmp) = 1;
|
DECL_GIMPLE_REG_P (tmp) = 1;
|
add_referenced_var (tmp);
|
add_referenced_var (tmp);
|
phi = create_phi_node (tmp, bb);
|
phi = create_phi_node (tmp, bb);
|
/* RET_TYPE can be a float when -ffast-maths is enabled. */
|
/* RET_TYPE can be a float when -ffast-maths is enabled. */
|
add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
|
add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
|
UNKNOWN_LOCATION);
|
UNKNOWN_LOCATION);
|
return PHI_RESULT (phi);
|
return PHI_RESULT (phi);
|
}
|
}
|
|
|
/* Optimizes tail calls in the function, turning the tail recursion
|
/* Optimizes tail calls in the function, turning the tail recursion
|
into iteration. */
|
into iteration. */
|
|
|
static unsigned int
|
static unsigned int
|
tree_optimize_tail_calls_1 (bool opt_tailcalls)
|
tree_optimize_tail_calls_1 (bool opt_tailcalls)
|
{
|
{
|
edge e;
|
edge e;
|
bool phis_constructed = false;
|
bool phis_constructed = false;
|
struct tailcall *tailcalls = NULL, *act, *next;
|
struct tailcall *tailcalls = NULL, *act, *next;
|
bool changed = false;
|
bool changed = false;
|
basic_block first = single_succ (ENTRY_BLOCK_PTR);
|
basic_block first = single_succ (ENTRY_BLOCK_PTR);
|
tree param;
|
tree param;
|
gimple stmt;
|
gimple stmt;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (!suitable_for_tail_opt_p ())
|
if (!suitable_for_tail_opt_p ())
|
return 0;
|
return 0;
|
if (opt_tailcalls)
|
if (opt_tailcalls)
|
opt_tailcalls = suitable_for_tail_call_opt_p ();
|
opt_tailcalls = suitable_for_tail_call_opt_p ();
|
|
|
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
{
|
{
|
/* Only traverse the normal exits, i.e. those that end with return
|
/* Only traverse the normal exits, i.e. those that end with return
|
statement. */
|
statement. */
|
stmt = last_stmt (e->src);
|
stmt = last_stmt (e->src);
|
|
|
if (stmt
|
if (stmt
|
&& gimple_code (stmt) == GIMPLE_RETURN)
|
&& gimple_code (stmt) == GIMPLE_RETURN)
|
find_tail_calls (e->src, &tailcalls);
|
find_tail_calls (e->src, &tailcalls);
|
}
|
}
|
|
|
/* Construct the phi nodes and accumulators if necessary. */
|
/* Construct the phi nodes and accumulators if necessary. */
|
a_acc = m_acc = NULL_TREE;
|
a_acc = m_acc = NULL_TREE;
|
for (act = tailcalls; act; act = act->next)
|
for (act = tailcalls; act; act = act->next)
|
{
|
{
|
if (!act->tail_recursion)
|
if (!act->tail_recursion)
|
continue;
|
continue;
|
|
|
if (!phis_constructed)
|
if (!phis_constructed)
|
{
|
{
|
/* Ensure that there is only one predecessor of the block
|
/* Ensure that there is only one predecessor of the block
|
or if there are existing degenerate PHI nodes. */
|
or if there are existing degenerate PHI nodes. */
|
if (!single_pred_p (first)
|
if (!single_pred_p (first)
|
|| !gimple_seq_empty_p (phi_nodes (first)))
|
|| !gimple_seq_empty_p (phi_nodes (first)))
|
first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
|
first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
|
|
|
/* Copy the args if needed. */
|
/* Copy the args if needed. */
|
for (param = DECL_ARGUMENTS (current_function_decl);
|
for (param = DECL_ARGUMENTS (current_function_decl);
|
param;
|
param;
|
param = TREE_CHAIN (param))
|
param = TREE_CHAIN (param))
|
if (arg_needs_copy_p (param))
|
if (arg_needs_copy_p (param))
|
{
|
{
|
tree name = gimple_default_def (cfun, param);
|
tree name = gimple_default_def (cfun, param);
|
tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
|
tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
|
gimple phi;
|
gimple phi;
|
|
|
set_default_def (param, new_name);
|
set_default_def (param, new_name);
|
phi = create_phi_node (name, first);
|
phi = create_phi_node (name, first);
|
SSA_NAME_DEF_STMT (name) = phi;
|
SSA_NAME_DEF_STMT (name) = phi;
|
add_phi_arg (phi, new_name, single_pred_edge (first),
|
add_phi_arg (phi, new_name, single_pred_edge (first),
|
EXPR_LOCATION (param));
|
EXPR_LOCATION (param));
|
}
|
}
|
phis_constructed = true;
|
phis_constructed = true;
|
}
|
}
|
|
|
if (act->add && !a_acc)
|
if (act->add && !a_acc)
|
a_acc = create_tailcall_accumulator ("add_acc", first,
|
a_acc = create_tailcall_accumulator ("add_acc", first,
|
integer_zero_node);
|
integer_zero_node);
|
|
|
if (act->mult && !m_acc)
|
if (act->mult && !m_acc)
|
m_acc = create_tailcall_accumulator ("mult_acc", first,
|
m_acc = create_tailcall_accumulator ("mult_acc", first,
|
integer_one_node);
|
integer_one_node);
|
}
|
}
|
|
|
for (; tailcalls; tailcalls = next)
|
for (; tailcalls; tailcalls = next)
|
{
|
{
|
next = tailcalls->next;
|
next = tailcalls->next;
|
changed |= optimize_tail_call (tailcalls, opt_tailcalls);
|
changed |= optimize_tail_call (tailcalls, opt_tailcalls);
|
free (tailcalls);
|
free (tailcalls);
|
}
|
}
|
|
|
if (a_acc || m_acc)
|
if (a_acc || m_acc)
|
{
|
{
|
/* Modify the remaining return statements. */
|
/* Modify the remaining return statements. */
|
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
{
|
{
|
stmt = last_stmt (e->src);
|
stmt = last_stmt (e->src);
|
|
|
if (stmt
|
if (stmt
|
&& gimple_code (stmt) == GIMPLE_RETURN)
|
&& gimple_code (stmt) == GIMPLE_RETURN)
|
adjust_return_value (e->src, m_acc, a_acc);
|
adjust_return_value (e->src, m_acc, a_acc);
|
}
|
}
|
}
|
}
|
|
|
if (changed)
|
if (changed)
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
|
|
if (phis_constructed)
|
if (phis_constructed)
|
add_virtual_phis ();
|
add_virtual_phis ();
|
if (changed)
|
if (changed)
|
return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
|
return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
|
return 0;
|
return 0;
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
execute_tail_recursion (void)
|
execute_tail_recursion (void)
|
{
|
{
|
return tree_optimize_tail_calls_1 (false);
|
return tree_optimize_tail_calls_1 (false);
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_tail_calls (void)
|
gate_tail_calls (void)
|
{
|
{
|
return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
|
return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
execute_tail_calls (void)
|
execute_tail_calls (void)
|
{
|
{
|
return tree_optimize_tail_calls_1 (true);
|
return tree_optimize_tail_calls_1 (true);
|
}
|
}
|
|
|
struct gimple_opt_pass pass_tail_recursion =
|
struct gimple_opt_pass pass_tail_recursion =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"tailr", /* name */
|
"tailr", /* name */
|
gate_tail_calls, /* gate */
|
gate_tail_calls, /* gate */
|
execute_tail_recursion, /* execute */
|
execute_tail_recursion, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_NONE, /* tv_id */
|
TV_NONE, /* tv_id */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
struct gimple_opt_pass pass_tail_calls =
|
struct gimple_opt_pass pass_tail_calls =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"tailc", /* name */
|
"tailc", /* name */
|
gate_tail_calls, /* gate */
|
gate_tail_calls, /* gate */
|
execute_tail_calls, /* execute */
|
execute_tail_calls, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_NONE, /* tv_id */
|
TV_NONE, /* tv_id */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
