/* Tail call optimization on trees.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2003-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
+#include "stor-layout.h"
#include "tm_p.h"
-#include "basic-block.h"
+#include "predict.h"
+#include "hard-reg-set.h"
#include "function.h"
-#include "tree-flow.h"
-#include "tree-dump.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-into-ssa.h"
+#include "rtl.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
+#include "expr.h"
+#include "tree-dfa.h"
#include "gimple-pretty-print.h"
#include "except.h"
#include "tree-pass.h"
-#include "flags.h"
#include "langhooks.h"
#include "dbgcnt.h"
#include "target.h"
+#include "cfgloop.h"
#include "common/common-target.h"
+#include "cgraph.h"
+#include "ipa-utils.h"
/* 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
accumulator. */
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 **);
/* Returns false when the function is not suitable for tail call optimization
from some reason (e.g. if it takes variable number of arguments). */
return true;
}
/* Returns false when the function is not suitable for tail call optimization
- from some reason (e.g. if it takes variable number of arguments).
+ for 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
tail call discovery happen. */
additive factor for the real return value. */
static bool
-process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
+process_assignment (gassign *stmt, gimple_stmt_iterator call, tree *m,
tree *a, tree *ass_var)
{
tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
{
/* Reject a tailcall if the type conversion might need
additional code. */
- if (gimple_assign_cast_p (stmt)
- && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
- return false;
+ if (gimple_assign_cast_p (stmt))
+ {
+ if (TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
+ return false;
+
+ /* Even if the type modes are the same, if the precision of the
+ type is smaller than mode's precision,
+ reduce_to_bit_field_precision would generate additional code. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
+ && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (dest)))
+ > TYPE_PRECISION (TREE_TYPE (dest))))
+ return false;
+ }
if (src_var != *ass_var)
return false;
if (rhs_class == GIMPLE_UNARY_RHS)
;
else 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
&& (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
*ass_var = dest;
return true;
+ case POINTER_PLUS_EXPR:
+ if (op0 != *ass_var)
+ return false;
+ *a = non_ass_var;
+ *ass_var = dest;
+ return true;
+
case MULT_EXPR:
*m = non_ass_var;
*ass_var = dest;
return true;
case NEGATE_EXPR:
- if (FLOAT_TYPE_P (TREE_TYPE (op0)))
- *m = build_real (TREE_TYPE (op0), dconstm1);
- else
- *m = build_int_cst (TREE_TYPE (op0), -1);
-
+ *m = build_minus_one_cst (TREE_TYPE (op0));
*ass_var = dest;
return true;
*a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
else
{
- if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
- *m = build_real (TREE_TYPE (non_ass_var), dconstm1);
- else
- *m = build_int_cst (TREE_TYPE (non_ass_var), -1);
-
+ *m = build_minus_one_cst (TREE_TYPE (non_ass_var));
*a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
}
propagate_through_phis (tree var, edge e)
{
basic_block dest = e->dest;
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
return PHI_RESULT (phi);
}
find_tail_calls (basic_block bb, struct tailcall **ret)
{
tree ass_var = NULL_TREE, ret_var, func, param;
- gimple stmt, call = NULL;
+ gimple stmt;
+ gcall *call = NULL;
gimple_stmt_iterator gsi, agsi;
bool tail_recursion;
struct tailcall *nw;
basic_block abb;
size_t idx;
tree var;
- referenced_var_iterator rvi;
if (!single_succ_p (bb))
return;
/* Check for a call. */
if (is_gimple_call (stmt))
{
- call = stmt;
- ass_var = gimple_call_lhs (stmt);
+ call = as_a <gcall *> (stmt);
+ ass_var = gimple_call_lhs (call);
break;
}
/* We found the call, check whether it is suitable. */
tail_recursion = false;
func = gimple_call_fndecl (call);
- if (func == current_function_decl)
+ if (func
+ && !DECL_BUILT_IN (func)
+ && recursive_call_p (current_function_decl, func))
{
tree arg;
/* Make sure the tail invocation of this function does not refer
to local variables. */
- FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
+ FOR_EACH_LOCAL_DECL (cfun, idx, var)
{
if (TREE_CODE (var) != PARM_DECL
&& auto_var_in_fn_p (var, cfun->decl)
return;
/* This is a gimple assign. */
- if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
+ if (! process_assignment (as_a <gassign *> (stmt), gsi, &tmp_m,
+ &tmp_a, &ass_var))
return;
if (tmp_a)
}
/* See if this is a tail call we can handle. */
- ret_var = gimple_return_retval (stmt);
+ ret_var = gimple_return_retval (as_a <greturn *> (stmt));
/* We may proceed if there either is no return value, or the return value
is identical to the call's return. */
if (!tail_recursion && (m || a))
return;
+ /* For pointers only allow additions. */
+ if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
+ return;
+
nw = XNEW (struct tailcall);
nw->call_gsi = gsi;
static void
add_successor_phi_arg (edge e, tree var, tree phi_arg)
{
- gimple_stmt_iterator gsi;
+ gphi_iterator 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.phi ()) == var)
break;
gcc_assert (!gsi_end_p (gsi));
- add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION, NULL);
+ add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION);
}
/* Creates a GIMPLE statement which computes the operation specified by
- 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
+ CODE, ACC and OP1 to a new variable with name LABEL and inserts the
+ statement in the position specified by GSI. Returns the
tree node of the statement's result. */
static tree
{
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
- tree tmp = create_tmp_reg (ret_type, label);
- gimple stmt;
- tree result;
+ tree result = make_temp_ssa_name (ret_type, NULL, label);
+ gassign *stmt;
- add_referenced_var (tmp);
-
- if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
- stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
+ if (POINTER_TYPE_P (ret_type))
+ {
+ gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
+ code = POINTER_PLUS_EXPR;
+ }
+ if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
+ && code != POINTER_PLUS_EXPR)
+ stmt = gimple_build_assign (result, code, acc, op1);
else
{
- tree rhs = fold_convert (TREE_TYPE (acc),
- fold_build2 (code,
- TREE_TYPE (op1),
- fold_convert (TREE_TYPE (op1), acc),
- op1));
+ tree tem;
+ if (code == POINTER_PLUS_EXPR)
+ tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
+ else
+ tem = fold_build2 (code, TREE_TYPE (op1),
+ fold_convert (TREE_TYPE (op1), acc), op1);
+ tree rhs = fold_convert (ret_type, tem);
rhs = force_gimple_operand_gsi (&gsi, rhs,
- false, NULL, true, GSI_CONTINUE_LINKING);
- stmt = gimple_build_assign (NULL_TREE, rhs);
+ false, NULL, true, GSI_SAME_STMT);
+ stmt = gimple_build_assign (result, rhs);
}
- result = make_ssa_name (tmp, stmt);
- gimple_assign_set_lhs (stmt, result);
- update_stmt (stmt);
gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
return result;
}
update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
gimple_stmt_iterator gsi)
{
- gimple stmt;
- tree var;
+ gassign *stmt;
+ tree var = copy_ssa_name (acc);
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 (var, code, acc, op1);
else
{
tree rhs = fold_convert (TREE_TYPE (acc),
op1));
rhs = force_gimple_operand_gsi (&gsi, rhs,
false, NULL, false, GSI_CONTINUE_LINKING);
- stmt = gimple_build_assign (NULL_TREE, rhs);
+ stmt = gimple_build_assign (var, rhs);
}
- var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
- gimple_assign_set_lhs (stmt, var);
- update_stmt (stmt);
gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
return var;
}
adjust_return_value (basic_block bb, tree m, tree a)
{
tree retval;
- gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
+ greturn *ret_stmt = as_a <greturn *> (gimple_seq_last_stmt (bb_seq (bb)));
gimple_stmt_iterator gsi = gsi_last_bb (bb);
gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
{
tree def;
- if (!is_gimple_reg (param) || !var_ann (param))
+ if (!is_gimple_reg (param))
return false;
/* Parameters that are only defined but never used need not be copied. */
- def = gimple_default_def (cfun, param);
+ def = ssa_default_def (cfun, param);
if (!def)
return false;
size_t idx;
basic_block bb, first;
edge e;
- gimple phi;
+ gphi *phi;
+ gphi_iterator gpi;
gimple_stmt_iterator gsi;
gimple orig_stmt;
gcc_assert (is_gimple_call (stmt));
- first = single_succ (ENTRY_BLOCK_PTR);
+ first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
/* Remove the code after call_gsi that will become unreachable. The
possibly unreachable code in other blocks is removed later in
/* Number of executions of function has reduced by the tailcall. */
e = single_succ_edge (gsi_bb (t->call_gsi));
- 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 (EXIT_BLOCK_PTR_FOR_FN (cfun), e->count, EDGE_FREQUENCY (e));
+ decrease_profile (ENTRY_BLOCK_PTR_FOR_FN (cfun), e->count,
+ EDGE_FREQUENCY (e));
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
/* Replace the call by a jump to the start of function. */
/* Add phi node entries for arguments. The ordering of the phi nodes should
be the same as the ordering of the arguments. */
for (param = DECL_ARGUMENTS (current_function_decl),
- idx = 0, gsi = gsi_start_phis (first);
+ idx = 0, gpi = gsi_start_phis (first);
param;
param = DECL_CHAIN (param), idx++)
{
continue;
arg = gimple_call_arg (stmt, idx);
- phi = gsi_stmt (gsi);
+ phi = gpi.phi ();
gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
- add_phi_arg (phi, arg, e, gimple_location (stmt), gimple_block (stmt));
- gsi_next (&gsi);
+ add_phi_arg (phi, arg, e, gimple_location (stmt));
+ gsi_next (&gpi);
}
/* Update the values of accumulators. */
release_defs (call);
}
-/* Add phi nodes for the virtual operands defined in the function to the
- header of the loop created by tail recursion elimination.
-
- 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
- or changed within the recursive call. However, the local variables
- 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,
- which requires adding phi nodes.
-*/
-static void
-add_virtual_phis (void)
-{
- referenced_var_iterator rvi;
- tree var;
-
- /* 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
- ssa name available). A solution would be to have an artificial
- 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
- possibly affected virtual ssa names from scratch. */
-
- FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
- {
- if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
- mark_sym_for_renaming (var);
- }
-}
-
/* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also
mark the tailcalls for the sibcall optimization. */
if (opt_tailcalls)
{
- gimple stmt = gsi_stmt (t->call_gsi);
+ gcall *stmt = as_a <gcall *> (gsi_stmt (t->call_gsi));
gimple_call_set_tail (stmt, true);
+ cfun->tail_call_marked = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Found tail call ");
create_tailcall_accumulator (const char *label, basic_block bb, tree init)
{
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
- tree tmp = create_tmp_reg (ret_type, label);
- gimple phi;
+ if (POINTER_TYPE_P (ret_type))
+ ret_type = sizetype;
+
+ tree tmp = make_temp_ssa_name (ret_type, NULL, label);
+ gphi *phi;
- add_referenced_var (tmp);
phi = create_phi_node (tmp, bb);
/* RET_TYPE can be a float when -ffast-maths is enabled. */
add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
- UNKNOWN_LOCATION, NULL);
+ UNKNOWN_LOCATION);
return PHI_RESULT (phi);
}
bool phis_constructed = false;
struct tailcall *tailcalls = NULL, *act, *next;
bool changed = false;
- basic_block first = single_succ (ENTRY_BLOCK_PTR);
+ basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
tree param;
gimple stmt;
edge_iterator ei;
if (opt_tailcalls)
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_FOR_FN (cfun)->preds)
{
/* Only traverse the normal exits, i.e. those that end with return
statement. */
or if there are existing degenerate PHI nodes. */
if (!single_pred_p (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_FOR_FN (cfun)));
/* Copy the args if needed. */
for (param = DECL_ARGUMENTS (current_function_decl);
param = DECL_CHAIN (param))
if (arg_needs_copy_p (param))
{
- tree name = gimple_default_def (cfun, param);
+ tree name = ssa_default_def (cfun, param);
tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
- gimple phi;
+ gphi *phi;
- set_default_def (param, new_name);
+ set_ssa_default_def (cfun, 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),
- EXPR_LOCATION (param), NULL);
+ EXPR_LOCATION (param));
}
phis_constructed = true;
}
if (a_acc || m_acc)
{
/* Modify the remaining return statements. */
- FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
{
stmt = last_stmt (e->src);
}
if (changed)
- free_dominance_info (CDI_DOMINATORS);
+ {
+ /* We may have created new loops. Make them magically appear. */
+ loops_state_set (LOOPS_NEED_FIXUP);
+ free_dominance_info (CDI_DOMINATORS);
+ }
+ /* Add phi nodes for the virtual operands defined in the function to the
+ header of the loop created by tail recursion elimination. Do so
+ by triggering the SSA renamer. */
if (phis_constructed)
- add_virtual_phis ();
+ mark_virtual_operands_for_renaming (cfun);
+
if (changed)
return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
return 0;
}
-static unsigned int
-execute_tail_recursion (void)
-{
- return tree_optimize_tail_calls_1 (false);
-}
-
static bool
gate_tail_calls (void)
{
return tree_optimize_tail_calls_1 (true);
}
-struct gimple_opt_pass pass_tail_recursion =
+namespace {
+
+const pass_data pass_data_tail_recursion =
{
- {
- GIMPLE_PASS,
- "tailr", /* name */
- gate_tail_calls, /* gate */
- execute_tail_recursion, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_ssa /* todo_flags_finish */
- }
+ GIMPLE_PASS, /* type */
+ "tailr", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_NONE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
};
-struct gimple_opt_pass pass_tail_calls =
+class pass_tail_recursion : public gimple_opt_pass
{
- {
- GIMPLE_PASS,
- "tailc", /* name */
- gate_tail_calls, /* gate */
- execute_tail_calls, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_ssa /* todo_flags_finish */
- }
+public:
+ pass_tail_recursion (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_tail_recursion, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_tail_recursion (m_ctxt); }
+ virtual bool gate (function *) { return gate_tail_calls (); }
+ virtual unsigned int execute (function *)
+ {
+ return tree_optimize_tail_calls_1 (false);
+ }
+
+}; // class pass_tail_recursion
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_tail_recursion (gcc::context *ctxt)
+{
+ return new pass_tail_recursion (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_tail_calls =
+{
+ GIMPLE_PASS, /* type */
+ "tailc", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_NONE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
};
+
+class pass_tail_calls : public gimple_opt_pass
+{
+public:
+ pass_tail_calls (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_tail_calls, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return gate_tail_calls (); }
+ virtual unsigned int execute (function *) { return execute_tail_calls (); }
+
+}; // class pass_tail_calls
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_tail_calls (gcc::context *ctxt)
+{
+ return new pass_tail_calls (ctxt);
+}
projects / gcc.git / blobdiff