#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)
{
int i;
if (current_function_stdarg)
return false;
for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
{
tree var = VARRAY_TREE (referenced_vars, i);
if (!(TREE_STATIC (var) || DECL_EXTERNAL (var))
&& var_ann (var)->mem_tag_kind == NOT_A_TAG
&& is_call_clobbered (var))
return false;
}
return true;
}
static bool
suitable_for_tail_call_opt_p (void)
{
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;
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 = EDGE_SUCC (bb, 0)->dest)
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 = EDGE_SUCC (bb, 0)->dest)
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 (EDGE_COUNT (bb->succs) > 1)
return;
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
{
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
get_stmt_operands (stmt);
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 (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann))
|| NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann))
|| NUM_VUSES (VUSE_OPS (ann))
|| 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
&& (!is_gimple_reg_type (TREE_TYPE (param))
|| !lang_hooks.types_compatible_p (TREE_TYPE (param),
TREE_TYPE (arg))))
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, EDGE_SUCC (abb, 0));
abb = EDGE_SUCC (abb, 0)->dest;
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 = xmalloc (sizeof (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 = build (MODIFY_EXPR, ret_type, NULL_TREE,
build (MULT_EXPR, ret_type, m_acc, a));
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_after (&bsi, stmt, BSI_NEW_STMT);
}
}
else
var = a;
stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
build (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 = build (MODIFY_EXPR, ret_type, NULL_TREE,
build (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 = build (MODIFY_EXPR, ret_type, NULL_TREE,
build (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_SAME_STMT);
}
else
var = ret_var;
if (a)
{
stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
build (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_SAME_STMT);
}
TREE_OPERAND (ret_stmt, 0) = var;
modify_stmt (ret_stmt);
}
static void
eliminate_tail_call (struct tailcall *t)
{
tree param, stmt, args, rslt, call;
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;
stmt = bsi_stmt (t->call_bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
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 = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
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);
release_defs (t);
}
e = redirect_edge_and_branch (EDGE_SUCC (t->call_block, 0), first);
gcc_assert (e);
PENDING_STMT (e) = NULL_TREE;
for (param = DECL_ARGUMENTS (current_function_decl),
args = TREE_OPERAND (stmt, 1);
param;
param = TREE_CHAIN (param),
args = TREE_CHAIN (args))
{
for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi))
if (param == SSA_NAME_VAR (PHI_RESULT (phi)))
break;
if (!phi)
continue;
add_phi_arg (&phi, TREE_VALUE (args), e);
}
v_may_defs = V_MAY_DEF_OPS (ann);
for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
{
param = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
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;
if (!name)
{
continue;
}
new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
var_ann (param)->default_def = new_name;
phi = create_phi_node (name, first);
SSA_NAME_DEF_STMT (name) = phi;
add_phi_arg (&phi, new_name, EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
gcc_assert (EDGE_COUNT (first->preds) <= 2);
}
add_phi_arg (&phi, V_MAY_DEF_OP (v_may_defs, i), e);
}
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);
release_defs (call);
}
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 = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
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 (EDGE_COUNT (first->preds) > 1)
first = split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
for (param = DECL_ARGUMENTS (current_function_decl);
param;
param = TREE_CHAIN (param))
if (var_ann (param)
&& (var_ann (param)->default_def
&& TREE_CODE (var_ann (param)->default_def) == SSA_NAME))
{
tree name = var_ann (param)->default_def;
tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
tree phi;
var_ann (param)->default_def = new_name;
phi = create_phi_node (name, first);
SSA_NAME_DEF_STMT (name) = phi;
add_phi_arg (&phi, new_name, EDGE_PRED (first, 0));
}
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_tmp_var (tmp);
phi = create_phi_node (tmp, first);
add_phi_arg (&phi, build_int_cst (ret_type, 0), EDGE_PRED (first, 0));
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_tmp_var (tmp);
phi = create_phi_node (tmp, first);
add_phi_arg (&phi, build_int_cst (ret_type, 1), EDGE_PRED (first, 0));
m_acc = PHI_RESULT (phi);
}
}
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 ();
}
}
static void
execute_tail_recursion (void)
{
tree_optimize_tail_calls_1 (false);
}
static bool
gate_tail_calls (void)
{
return flag_optimize_sibling_calls != 0;
}
static void
execute_tail_calls (void)
{
tree_optimize_tail_calls_1 (true);
}
struct tree_opt_pass pass_tail_recursion =
{
"tailr",
NULL,
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
};