/* Tail call optimization on trees.
- Copyright (C) 2003-2013 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 "gimplify.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
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;
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;
/* 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;
}
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. */
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);
+ add_phi_arg (gsi.phi (), phi_arg, e, UNKNOWN_LOCATION);
}
/* Creates a GIMPLE statement which computes the operation specified by
tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
tree result = make_temp_ssa_name (ret_type, NULL, label);
- gimple stmt;
+ gassign *stmt;
if (POINTER_TYPE_P (ret_type))
{
}
if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
&& code != POINTER_PLUS_EXPR)
- stmt = gimple_build_assign_with_ops (code, result, acc, op1);
+ stmt = gimple_build_assign (result, code, acc, op1);
else
{
tree tem;
update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
gimple_stmt_iterator gsi)
{
- gimple stmt;
- tree var = copy_ssa_name (acc, NULL);
+ 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, var, acc, op1);
+ stmt = gimple_build_assign (var, code, acc, op1);
else
{
tree rhs = fold_convert (TREE_TYPE (acc),
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);
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));
- gsi_next (&gsi);
+ gsi_next (&gpi);
}
/* Update the values of accumulators. */
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 ");
ret_type = sizetype;
tree tmp = make_temp_ssa_name (ret_type, NULL, label);
- gimple phi;
+ gphi *phi;
phi = create_phi_node (tmp, bb);
/* RET_TYPE can be a float when -ffast-maths is enabled. */
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);
{
tree name = ssa_default_def (cfun, param);
tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
- gimple phi;
+ gphi *phi;
set_ssa_default_def (cfun, param, new_name);
phi = create_phi_node (name, first);
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)
{
/* We may have created new loops. Make them magically appear. */
- if (current_loops)
- loops_state_set (LOOPS_NEED_FIXUP);
+ loops_state_set (LOOPS_NEED_FIXUP);
free_dominance_info (CDI_DOMINATORS);
}
return 0;
}
-static unsigned int
-execute_tail_recursion (void)
-{
- return tree_optimize_tail_calls_1 (false);
-}
-
static bool
gate_tail_calls (void)
{
GIMPLE_PASS, /* type */
"tailr", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
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 */
+ 0, /* todo_flags_finish */
};
class pass_tail_recursion : public gimple_opt_pass
/* opt_pass methods: */
opt_pass * clone () { return new pass_tail_recursion (m_ctxt); }
- bool gate () { return gate_tail_calls (); }
- unsigned int execute () { return execute_tail_recursion (); }
+ virtual bool gate (function *) { return gate_tail_calls (); }
+ virtual unsigned int execute (function *)
+ {
+ return tree_optimize_tail_calls_1 (false);
+ }
}; // class pass_tail_recursion
GIMPLE_PASS, /* type */
"tailc", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
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 */
+ 0, /* todo_flags_finish */
};
class pass_tail_calls : public gimple_opt_pass
{}
/* opt_pass methods: */
- bool gate () { return gate_tail_calls (); }
- unsigned int execute () { return execute_tail_calls (); }
+ virtual bool gate (function *) { return gate_tail_calls (); }
+ virtual unsigned int execute (function *) { return execute_tail_calls (); }
}; // class pass_tail_calls