/* Tail call optimization on trees.
- Copyright (C) 2003 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
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. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
static bool
suitable_for_tail_opt_p (void)
{
- int i;
+ referenced_var_iterator rvi;
+ tree var;
if (current_function_stdarg)
return false;
- /* No local variable should be call-clobbered. We ignore any kind
- of memory tag, as these are not real variables. */
- for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
+ /* No local variable nor structure field should be call-clobbered. We
+ ignore any kind of memory tag, as these are not real variables. */
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = VARRAY_TREE (referenced_vars, i);
- if (decl_function_context (var) == current_function_decl
- && !TREE_STATIC (var)
- && var_ann (var)->mem_tag_kind == NOT_A_TAG
+ if (!is_global_var (var)
+ && (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG)
&& is_call_clobbered (var))
return false;
}
static bool
suitable_for_tail_call_opt_p (void)
{
+ tree param;
+
/* alloca (until we have stack slot life analysis) inhibits
sibling call optimizations, but not tail recursion. */
if (current_function_calls_alloca)
if (current_function_calls_setjmp)
return false;
+ /* ??? 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. */
+ for (param = DECL_ARGUMENTS (current_function_decl);
+ param;
+ param = TREE_CHAIN (param))
+ if (TREE_ADDRESSABLE (param))
+ return false;
+
return true;
}
/* Checks whether the expression EXPR in stmt AT is independent of the
- statement pointed by BSI (in a sense that we already know EXPR's value
+ statement pointed to by BSI (in a sense that we already know EXPR's value
at BSI). We use the fact that we are only called from the chain of
basic blocks that have only single successor. Returns the expression
containing the value of EXPR at BSI. */
{
basic_block bb, call_bb, at_bb;
edge e;
+ edge_iterator ei;
if (is_gimple_min_invariant (expr))
return expr;
/* Mark the blocks in the chain leading to the end. */
at_bb = bb_for_stmt (at);
call_bb = bb_for_stmt (bsi_stmt (bsi));
- for (bb = call_bb; bb != at_bb; bb = bb->succ->dest)
+ for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
bb->aux = &bb->aux;
bb->aux = &bb->aux;
at = SSA_NAME_DEF_STMT (expr);
bb = bb_for_stmt (at);
- /* The default defininition or defined before the chain. */
+ /* The default definition or defined before the chain. */
if (!bb || !bb->aux)
break;
break;
}
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (e->src->aux)
break;
- if (!e)
- abort ();
+ gcc_assert (e);
expr = PHI_ARG_DEF_FROM_EDGE (at, e);
+ if (TREE_CODE (expr) != SSA_NAME)
+ {
+ /* The value is a constant. */
+ break;
+ }
}
/* Unmark the blocks. */
- for (bb = call_bb; bb != at_bb; bb = bb->succ->dest)
+ for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
bb->aux = NULL;
bb->aux = NULL;
return true;
}
- if (TREE_CODE_CLASS (code) != '2')
+ if (TREE_CODE_CLASS (code) != tcc_binary)
return false;
+ /* Accumulator optimizations will reverse the order of operations.
+ We can only do that for floating-point types if we're assuming
+ that addition and multiplication are associative. */
+ if (!flag_unsafe_math_optimizations)
+ if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
+ return false;
+
/* We only handle the code like
x = call ();
basic_block abb;
stmt_ann_t ann;
- if (bb->succ->succ_next)
+ if (!single_succ_p (bb))
return;
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
- get_stmt_operands (stmt);
-
/* Check for a call. */
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
ass_var = TREE_OPERAND (stmt, 0);
call = TREE_OPERAND (stmt, 1);
+ if (TREE_CODE (call) == WITH_SIZE_EXPR)
+ call = TREE_OPERAND (call, 0);
}
else
{
if (TREE_CODE (call) == CALL_EXPR)
break;
- /* If the statement has virtual operands, fail. */
+ /* If the statement has virtual or volatile operands, fail. */
ann = stmt_ann (stmt);
- if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann))
- || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann))
- || NUM_VUSES (VUSE_OPS (ann)))
+ if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
+ || ann->has_volatile_ops)
return;
}
if (bsi_end_p (bsi))
{
+ edge_iterator ei;
/* Recurse to the predecessors. */
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
find_tail_calls (e->src, ret);
return;
param = TREE_CHAIN (param), args = TREE_CHAIN (args))
{
tree arg = TREE_VALUE (args);
- if (param != arg
- /* Make sure there are no problems with copying. Note we must
+ if (param != arg)
+ {
+ /* Make sure there are no problems with copying. The parameter
have a copyable type and the two arguments must have reasonably
equivalent types. The latter requirement could be relaxed if
we emitted a suitable type conversion statement. */
- && (!is_gimple_reg_type (TREE_TYPE (param))
+ if (!is_gimple_reg_type (TREE_TYPE (param))
|| !lang_hooks.types_compatible_p (TREE_TYPE (param),
- TREE_TYPE (arg))))
- break;
+ TREE_TYPE (arg)))
+ break;
+
+ /* The parameter should be a real operand, so that phi node
+ created for it at the start of the function has the meaning
+ of copying the value. This test implies is_gimple_reg_type
+ from the previous condition, however this one could be
+ relaxed by being more careful with copying the new value
+ of the parameter (emitting appropriate MODIFY_EXPR and
+ updating the virtual operands). */
+ if (!is_gimple_reg (param))
+ break;
+ }
}
if (!args && !param)
tail_recursion = true;
while (bsi_end_p (absi))
{
- ass_var = propagate_through_phis (ass_var, abb->succ);
- abb = abb->succ->dest;
+ ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
+ abb = single_succ (abb);
absi = bsi_start (abb);
}
var = m_acc;
else
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (MULT_EXPR, ret_type, m_acc, a));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (MULT_EXPR, ret_type, m_acc, a));
tmp = create_tmp_var (ret_type, "acc_tmp");
add_referenced_tmp_var (tmp);
else
var = a;
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (PLUS_EXPR, ret_type, a_acc, var));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (PLUS_EXPR, ret_type, a_acc, var));
var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt);
TREE_OPERAND (stmt, 0) = var;
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
if (m)
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (MULT_EXPR, ret_type, m_acc, m));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (MULT_EXPR, ret_type, m_acc, m));
var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt);
TREE_OPERAND (stmt, 0) = var;
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
if (PHI_RESULT (phi) == a_acc)
break;
- add_phi_arg (&phi, a_acc_arg, back);
+ add_phi_arg (phi, a_acc_arg, back);
}
if (m_acc)
if (PHI_RESULT (phi) == m_acc)
break;
- add_phi_arg (&phi, m_acc_arg, back);
+ add_phi_arg (phi, m_acc_arg, back);
}
}
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
block_stmt_iterator bsi = bsi_last (bb);
- if (TREE_CODE (ret_stmt) != RETURN_EXPR)
- abort ();
+ gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
ret_var = TREE_OPERAND (ret_stmt, 0);
if (!ret_var)
if (m)
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (MULT_EXPR, ret_type, m_acc, ret_var));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (MULT_EXPR, ret_type, m_acc, ret_var));
tmp = create_tmp_var (ret_type, "acc_tmp");
add_referenced_tmp_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
- bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
}
else
var = ret_var;
if (a)
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (PLUS_EXPR, ret_type, a_acc, var));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (PLUS_EXPR, ret_type, a_acc, var));
tmp = create_tmp_var (ret_type, "acc_tmp");
add_referenced_tmp_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
- bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
}
TREE_OPERAND (ret_stmt, 0) = var;
- modify_stmt (ret_stmt);
+ update_stmt (ret_stmt);
+}
+
+/* Subtract COUNT and FREQUENCY from the basic block and it's
+ outgoing edge. */
+static void
+decrease_profile (basic_block bb, gcov_type count, int frequency)
+{
+ edge e;
+ bb->count -= count;
+ if (bb->count < 0)
+ bb->count = 0;
+ bb->frequency -= frequency;
+ if (bb->frequency < 0)
+ bb->frequency = 0;
+ if (!single_succ_p (bb))
+ {
+ gcc_assert (!EDGE_COUNT (bb->succs));
+ return;
+ }
+ e = single_succ_edge (bb);
+ e->count -= count;
+ if (e->count < 0)
+ e->count = 0;
}
/* Eliminates tail call described by T. TMP_VARS is a list of
basic_block bb, first;
edge e;
tree phi;
- stmt_ann_t ann;
- v_may_def_optype v_may_defs;
- unsigned i;
+ block_stmt_iterator bsi;
+ use_operand_p mayuse;
+ def_operand_p maydef;
+ ssa_op_iter iter;
+ tree orig_stmt;
- stmt = bsi_stmt (t->call_bsi);
- get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
+ stmt = orig_stmt = bsi_stmt (t->call_bsi);
bb = t->call_block;
if (dump_file && (dump_flags & TDF_DETAILS))
if (TREE_CODE (stmt) == MODIFY_EXPR)
stmt = TREE_OPERAND (stmt, 1);
- first = ENTRY_BLOCK_PTR->succ->dest;
+ first = single_succ (ENTRY_BLOCK_PTR);
+
+ /* Remove the code after call_bsi that will become unreachable. The
+ possibly unreachable code in other blocks is removed later in
+ cfg cleanup. */
+ bsi = t->call_bsi;
+ bsi_next (&bsi);
+ while (!bsi_end_p (bsi))
+ {
+ tree t = bsi_stmt (bsi);
+ /* Do not remove the return statement, so that redirect_edge_and_branch
+ sees how the block ends. */
+ if (TREE_CODE (t) == RETURN_EXPR)
+ break;
+
+ bsi_remove (&bsi);
+ release_defs (t);
+ }
+
+ /* Number of executions of function has reduced by the tailcall. */
+ e = single_succ_edge (t->call_block);
+ decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
+ decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
+ if (e->dest != EXIT_BLOCK_PTR)
+ decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
/* Replace the call by a jump to the start of function. */
- e = redirect_edge_and_branch (t->call_block->succ, first);
- if (!e)
- abort ();
+ e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
+ gcc_assert (e);
PENDING_STMT (e) = NULL_TREE;
/* Add phi node entries for arguments. Not every PHI node corresponds to
if (!phi)
continue;
- add_phi_arg (&phi, TREE_VALUE (args), e);
+ add_phi_arg (phi, TREE_VALUE (args), e);
}
/* Add phi nodes for the call clobbered variables. */
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ FOR_EACH_SSA_MAYDEF_OPERAND (maydef, mayuse, orig_stmt, iter)
{
- param = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
+ 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 = var_ann (param)->default_def;
- tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
+ tree name = default_def (param);
+ tree new_name;
- var_ann (param)->default_def = 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, ENTRY_BLOCK_PTR->succ);
+ 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. */
- if (first->pred->pred_next->pred_next)
- abort ();
+ gcc_assert (EDGE_COUNT (first->preds) <= 2);
}
- add_phi_arg (&phi, V_MAY_DEF_OP (v_may_defs, i), e);
+ add_phi_arg (phi, USE_FROM_PTR (mayuse), e);
}
/* Update the values of accumulators. */
}
bsi_remove (&t->call_bsi);
+ release_defs (call);
}
/* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
{
tree stmt = bsi_stmt (t->call_bsi);
- if (TREE_CODE (stmt) == MODIFY_EXPR)
- stmt = TREE_OPERAND (stmt, 1);
- if (TREE_CODE (stmt) != CALL_EXPR)
- abort ();
+ stmt = get_call_expr_in (stmt);
CALL_EXPR_TAILCALL (stmt) = 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
bool phis_constructed = false;
struct tailcall *tailcalls = NULL, *act, *next;
bool changed = false;
- basic_block first = ENTRY_BLOCK_PTR->succ->dest;
+ basic_block first = single_succ (ENTRY_BLOCK_PTR);
tree stmt, param, ret_type, tmp, phi;
+ edge_iterator ei;
if (!suitable_for_tail_opt_p ())
return;
if (opt_tailcalls)
opt_tailcalls = suitable_for_tail_call_opt_p ();
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
/* Only traverse the normal exits, i.e. those that end with return
statement. */
if (!phis_constructed)
{
+ tree name;
/* Ensure that there is only one predecessor of the block. */
- if (first->pred->pred_next)
- first = split_edge (ENTRY_BLOCK_PTR->succ);
+ if (!single_pred_p (first))
+ first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
/* Copy the args if needed. */
for (param = DECL_ARGUMENTS (current_function_decl);
param;
param = TREE_CHAIN (param))
- if (var_ann (param)
+ if (is_gimple_reg (param)
+ && 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))
+ && ((name = default_def (param))
+ && TREE_CODE (name) == 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;
+ set_default_def (param, new_name);
phi = create_phi_node (name, first);
SSA_NAME_DEF_STMT (name) = phi;
- add_phi_arg (&phi, new_name, first->pred);
+ add_phi_arg (phi, new_name, single_pred_edge (first));
}
phis_constructed = true;
}
add_referenced_tmp_var (tmp);
phi = create_phi_node (tmp, first);
- add_phi_arg (&phi, fold_convert (ret_type, integer_zero_node),
- first->pred);
+ add_phi_arg (phi,
+ /* RET_TYPE can be a float when -ffast-maths is
+ enabled. */
+ fold_convert (ret_type, integer_zero_node),
+ single_pred_edge (first));
a_acc = PHI_RESULT (phi);
}
add_referenced_tmp_var (tmp);
phi = create_phi_node (tmp, first);
- add_phi_arg (&phi, fold_convert (ret_type, integer_one_node),
- first->pred);
+ add_phi_arg (phi,
+ /* RET_TYPE can be a float when -ffast-maths is
+ enabled. */
+ fold_convert (ret_type, integer_one_node),
+ single_pred_edge (first));
m_acc = PHI_RESULT (phi);
}
}
if (a_acc || m_acc)
{
/* Modify the remaining return statements. */
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
stmt = last_stmt (e->src);
NULL, /* next */
0, /* static_pass_number */
0, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
+ TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
struct tree_opt_pass pass_tail_calls =
NULL, /* next */
0, /* static_pass_number */
0, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
+ TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
OSDN Git Service
