#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"
#include "except.h"
#include "tree-pass.h"
#include "flags.h"
#include "langhooks.h"
struct tailcall
{
basic_block call_block;
block_stmt_iterator call_bsi;
bool tail_recursion;
tree mult, add;
struct tailcall *next;
};
static tree m_acc, a_acc;
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 **);
static bool
suitable_for_tail_opt_p (void)
{
referenced_var_iterator rvi;
tree var;
if (current_function_stdarg)
return false;
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (!is_global_var (var)
&& (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG)
&& is_call_clobbered (var))
return false;
}
return true;
}
static bool
suitable_for_tail_call_opt_p (void)
{
tree param;
if (current_function_calls_alloca)
return false;
if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
return false;
if (current_function_calls_setjmp)
return false;
for (param = DECL_ARGUMENTS (current_function_decl);
param;
param = TREE_CHAIN (param))
if (TREE_ADDRESSABLE (param))
return false;
return true;
}
static tree
independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi)
{
basic_block bb, call_bb, at_bb;
edge e;
edge_iterator ei;
if (is_gimple_min_invariant (expr))
return expr;
if (TREE_CODE (expr) != SSA_NAME)
return NULL_TREE;
at_bb = bb_for_stmt (at);
call_bb = bb_for_stmt (bsi_stmt (bsi));
for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
bb->aux = &bb->aux;
bb->aux = &bb->aux;
while (1)
{
at = SSA_NAME_DEF_STMT (expr);
bb = bb_for_stmt (at);
if (!bb || !bb->aux)
break;
if (bb == call_bb)
{
for (; !bsi_end_p (bsi); bsi_next (&bsi))
if (bsi_stmt (bsi) == at)
break;
if (!bsi_end_p (bsi))
expr = NULL_TREE;
break;
}
if (TREE_CODE (at) != PHI_NODE)
{
expr = NULL_TREE;
break;
}
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->src->aux)
break;
gcc_assert (e);
expr = PHI_ARG_DEF_FROM_EDGE (at, e);
if (TREE_CODE (expr) != SSA_NAME)
{
break;
}
}
for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
bb->aux = NULL;
bb->aux = NULL;
return expr;
}
static bool
process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m,
tree *a, tree *ass_var)
{
tree op0, op1, non_ass_var;
tree dest = TREE_OPERAND (ass, 0);
tree src = TREE_OPERAND (ass, 1);
enum tree_code code = TREE_CODE (src);
tree src_var = src;
STRIP_NOPS (src_var);
if (TREE_CODE (src_var) == SSA_NAME)
{
if (src_var != *ass_var)
return false;
*ass_var = dest;
return true;
}
if (TREE_CODE_CLASS (code) != tcc_binary)
return false;
if (!flag_unsafe_math_optimizations)
if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
return false;
op0 = TREE_OPERAND (src, 0);
op1 = TREE_OPERAND (src, 1);
if (op0 == *ass_var
&& (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
;
else if (op1 == *ass_var
&& (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
;
else
return false;
switch (code)
{
case PLUS_EXPR:
if (*a)
return false;
*a = non_ass_var;
*ass_var = dest;
return true;
case MULT_EXPR:
if (*a || *m)
return false;
*m = non_ass_var;
*ass_var = dest;
return true;
default:
return false;
}
}
static tree
propagate_through_phis (tree var, edge e)
{
basic_block dest = e->dest;
tree phi;
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
return PHI_RESULT (phi);
return var;
}
static void
find_tail_calls (basic_block bb, struct tailcall **ret)
{
tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE;
block_stmt_iterator bsi, absi;
bool tail_recursion;
struct tailcall *nw;
edge e;
tree m, a;
basic_block abb;
stmt_ann_t ann;
if (!single_succ_p (bb))
return;
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
{
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
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
{
ass_var = NULL_TREE;
call = stmt;
}
if (TREE_CODE (call) == CALL_EXPR)
break;
ann = stmt_ann (stmt);
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;
FOR_EACH_EDGE (e, ei, bb->preds)
find_tail_calls (e->src, ret);
return;
}
tail_recursion = false;
func = get_callee_fndecl (call);
if (func == current_function_decl)
{
for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1);
param && args;
param = TREE_CHAIN (param), args = TREE_CHAIN (args))
{
tree arg = TREE_VALUE (args);
if (param != arg)
{
if (!is_gimple_reg_type (TREE_TYPE (param))
|| !lang_hooks.types_compatible_p (TREE_TYPE (param),
TREE_TYPE (arg)))
break;
if (!is_gimple_reg (param))
break;
}
}
if (!args && !param)
tail_recursion = true;
}
m = NULL_TREE;
a = NULL_TREE;
abb = bb;
absi = bsi;
while (1)
{
bsi_next (&absi);
while (bsi_end_p (absi))
{
ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
abb = single_succ (abb);
absi = bsi_start (abb);
}
stmt = bsi_stmt (absi);
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
if (TREE_CODE (stmt) == RETURN_EXPR)
break;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return;
if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var))
return;
}
ret_var = TREE_OPERAND (stmt, 0);
if (ret_var
&& TREE_CODE (ret_var) == MODIFY_EXPR)
{
tree ret_op = TREE_OPERAND (ret_var, 1);
STRIP_NOPS (ret_op);
if (!tail_recursion
&& TREE_CODE (ret_op) != SSA_NAME)
return;
if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var))
return;
ret_var = TREE_OPERAND (ret_var, 0);
}
if (ret_var
&& (ret_var != ass_var))
return;
if (!tail_recursion && (m || a))
return;
nw = XNEW (struct tailcall);
nw->call_block = bb;
nw->call_bsi = bsi;
nw->tail_recursion = tail_recursion;
nw->mult = m;
nw->add = a;
nw->next = *ret;
*ret = nw;
}
static void
adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back)
{
tree stmt, var, phi, tmp;
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
tree a_acc_arg = a_acc, m_acc_arg = m_acc;
if (a)
{
if (m_acc)
{
if (integer_onep (a))
var = m_acc;
else
{
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_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
}
}
else
var = a;
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);
a_acc_arg = var;
}
if (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);
m_acc_arg = var;
}
if (a_acc)
{
for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
if (PHI_RESULT (phi) == a_acc)
break;
add_phi_arg (phi, a_acc_arg, back);
}
if (m_acc)
{
for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi))
if (PHI_RESULT (phi) == m_acc)
break;
add_phi_arg (phi, m_acc_arg, back);
}
}
static void
adjust_return_value (basic_block bb, tree m, tree a)
{
tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp;
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
block_stmt_iterator bsi = bsi_last (bb);
gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR);
ret_var = TREE_OPERAND (ret_stmt, 0);
if (!ret_var)
return;
if (TREE_CODE (ret_var) == MODIFY_EXPR)
{
ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt);
bsi_replace (&bsi, ret_var, true);
SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var;
ret_var = TREE_OPERAND (ret_var, 0);
ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var);
bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT);
}
if (m)
{
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_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
}
else
var = ret_var;
if (a)
{
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_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
}
TREE_OPERAND (ret_stmt, 0) = var;
update_stmt (ret_stmt);
}
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;
}
static bool
arg_needs_copy_p (tree param)
{
tree def;
if (!is_gimple_reg (param) || !var_ann (param))
return false;
def = default_def (param);
if (!def)
return false;
return true;
}
static void
eliminate_tail_call (struct tailcall *t)
{
tree param, stmt, args, rslt, call;
basic_block bb, first;
edge e;
tree phi;
block_stmt_iterator bsi;
tree orig_stmt;
stmt = orig_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");
}
if (TREE_CODE (stmt) == MODIFY_EXPR)
stmt = TREE_OPERAND (stmt, 1);
first = single_succ (ENTRY_BLOCK_PTR);
bsi = t->call_bsi;
bsi_next (&bsi);
while (!bsi_end_p (bsi))
{
tree t = bsi_stmt (bsi);
if (TREE_CODE (t) == RETURN_EXPR)
break;
bsi_remove (&bsi, true);
release_defs (t);
}
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));
e = redirect_edge_and_branch (single_succ_edge (t->call_block), first);
gcc_assert (e);
PENDING_STMT (e) = NULL_TREE;
for (param = DECL_ARGUMENTS (current_function_decl),
args = TREE_OPERAND (stmt, 1),
phi = phi_nodes (first);
param;
param = TREE_CHAIN (param),
args = TREE_CHAIN (args))
{
if (!arg_needs_copy_p (param))
continue;
gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
add_phi_arg (phi, TREE_VALUE (args), e);
phi = PHI_CHAIN (phi);
}
adjust_accumulator_values (t->call_bsi, t->mult, t->add, e);
call = bsi_stmt (t->call_bsi);
if (TREE_CODE (call) == MODIFY_EXPR)
{
rslt = TREE_OPERAND (call, 0);
SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
}
bsi_remove (&t->call_bsi, true);
release_defs (call);
}
static void
add_virtual_phis (void)
{
referenced_var_iterator rvi;
tree var;
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (!is_gimple_reg (var) && default_def (var) != NULL_TREE)
mark_sym_for_renaming (var);
}
update_ssa (TODO_update_ssa_only_virtuals);
}
static bool
optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
{
if (t->tail_recursion)
{
eliminate_tail_call (t);
return true;
}
if (opt_tailcalls)
{
tree stmt = bsi_stmt (t->call_bsi);
stmt = get_call_expr_in (stmt);
CALL_EXPR_TAILCALL (stmt) = 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Found tail call ");
print_generic_expr (dump_file, stmt, dump_flags);
fprintf (dump_file, " in bb %i\n", t->call_block->index);
}
}
return false;
}
static void
tree_optimize_tail_calls_1 (bool opt_tailcalls)
{
edge e;
bool phis_constructed = false;
struct tailcall *tailcalls = NULL, *act, *next;
bool changed = false;
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_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
stmt = last_stmt (e->src);
if (stmt
&& TREE_CODE (stmt) == RETURN_EXPR)
find_tail_calls (e->src, &tailcalls);
}
a_acc = m_acc = NULL_TREE;
for (act = tailcalls; act; act = act->next)
{
if (!act->tail_recursion)
continue;
if (!phis_constructed)
{
if (!single_pred_p (first))
first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
for (param = DECL_ARGUMENTS (current_function_decl);
param;
param = TREE_CHAIN (param))
if (arg_needs_copy_p (param))
{
tree name = default_def (param);
tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
tree phi;
set_default_def (param, new_name);
phi = create_phi_node (name, first);
SSA_NAME_DEF_STMT (name) = phi;
add_phi_arg (phi, new_name, single_pred_edge (first));
}
phis_constructed = true;
}
if (act->add && !a_acc)
{
ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
tmp = create_tmp_var (ret_type, "add_acc");
add_referenced_var (tmp);
phi = create_phi_node (tmp, first);
add_phi_arg (phi,
fold_convert (ret_type, integer_zero_node),
single_pred_edge (first));
a_acc = PHI_RESULT (phi);
}
if (act->mult && !m_acc)
{
ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
tmp = create_tmp_var (ret_type, "mult_acc");
add_referenced_var (tmp);
phi = create_phi_node (tmp, first);
add_phi_arg (phi,
fold_convert (ret_type, integer_one_node),
single_pred_edge (first));
m_acc = PHI_RESULT (phi);
}
}
if (phis_constructed)
{
set_phi_nodes (first, phi_reverse (phi_nodes (first)));
}
for (; tailcalls; tailcalls = next)
{
next = tailcalls->next;
changed |= optimize_tail_call (tailcalls, opt_tailcalls);
free (tailcalls);
}
if (a_acc || m_acc)
{
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
stmt = last_stmt (e->src);
if (stmt
&& TREE_CODE (stmt) == RETURN_EXPR)
adjust_return_value (e->src, m_acc, a_acc);
}
}
if (changed)
{
free_dominance_info (CDI_DOMINATORS);
cleanup_tree_cfg ();
}
if (phis_constructed)
add_virtual_phis ();
}
static unsigned int
execute_tail_recursion (void)
{
tree_optimize_tail_calls_1 (false);
return 0;
}
static bool
gate_tail_calls (void)
{
return flag_optimize_sibling_calls != 0;
}
static unsigned int
execute_tail_calls (void)
{
tree_optimize_tail_calls_1 (true);
return 0;
}
struct tree_opt_pass pass_tail_recursion =
{
"tailr",
gate_tail_calls,
execute_tail_recursion,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_verify_ssa,
0
};
struct tree_opt_pass pass_tail_calls =
{
"tailc",
gate_tail_calls,
execute_tail_calls,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_verify_ssa,
0
};