tree-tailcall.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "ssa.h"
#include "cgraph.h"
#include "gimple-pretty-print.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
#include "except.h"
#include "tree-eh.h"
#include "dbgcnt.h"
#include "cfgloop.h"
#include "intl.h"
#include "common/common-target.h"
#include "ipa-utils.h"
#include "tree-ssa-live.h"
#include "diagnostic-core.h"
#include "gimple-range.h"
#include "alloc-pool.h"
#include "sreal.h"
#include "symbol-summary.h"
#include "ipa-cp.h"
#include "ipa-prop.h"
#include "attribs.h"
#include "asan.h"

Include dependency graph for tree-tailcall.cc:

Data Structures
struct	tailcall

Enumerations
enum	par { FAIL , OK , TRY_MOVE }

Functions
static void	maybe_error_musttail (gcall *call, const char *err, bool)
static bool	suitable_for_tail_opt_p (gcall *call, bool diag_musttail)
static bool	suitable_for_tail_call_opt_p (gcall *call, bool diag_musttail)
static edge	single_non_eh_succ_edge (basic_block bb)
static tree	independent_of_stmt_p (tree expr, gimple *at, gimple_stmt_iterator gsi, bitmap to_move)
static par	process_assignment (gassign *stmt, gimple_stmt_iterator call, tree *m, tree *a, tree *ass_var, bitmap to_move)
static tree	propagate_through_phis (tree var, edge e)
static bool	empty_eh_cleanup (basic_block bb, int *eh_has_tsan_func_exit, int cnt)
static void	find_tail_calls (basic_block bb, struct tailcall **ret, bool only_musttail, bool &opt_tailcalls, bool diag_musttail, int &retry_tsan_func_exit)
static void	add_successor_phi_arg (edge e, tree var, tree phi_arg)
static tree	adjust_return_value_with_ops (enum tree_code code, const char *label, tree acc, tree op1, gimple_stmt_iterator gsi)
static tree	update_accumulator_with_ops (enum tree_code code, tree acc, tree op1, gimple_stmt_iterator gsi)
static void	adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
static void	adjust_return_value (basic_block bb, tree m, tree a)
static void	decrease_profile (basic_block bb, profile_count count)
static void	eliminate_tail_call (struct tailcall *t, class loop *&new_loop)
static bool	optimize_tail_call (struct tailcall *t, bool opt_tailcalls, class loop *&new_loop)
static tree	create_tailcall_accumulator (const char *label, basic_block bb, tree init)
static unsigned int	tree_optimize_tail_calls_1 (bool opt_tailcalls, bool only_musttail, bool diag_musttail)
static bool	gate_tail_calls (void)
static unsigned int	execute_tail_calls (void)
gimple_opt_pass *	make_pass_tail_recursion (gcc::context *ctxt)
gimple_opt_pass *	make_pass_tail_calls (gcc::context *ctxt)
gimple_opt_pass *	make_pass_musttail (gcc::context *ctxt)

Variables
static tree	m_acc
static tree	a_acc
static bitmap	tailr_arg_needs_copy
static live_vars_map *	live_vars
static vec< bitmap_head >	live_vars_vec

Enumeration Type Documentation

par

enum par

Enumerator
FAIL
OK
TRY_MOVE

Function Documentation

add_successor_phi_arg()

void add_successor_phi_arg ( edge e, tree var, tree phi_arg )

static

Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E.   

References add_phi_arg(), gcc_assert, gsi_end_p(), gsi_next(), gsi_start_phis(), gphi_iterator::phi(), PHI_RESULT, and UNKNOWN_LOCATION.

Referenced by adjust_accumulator_values().

adjust_accumulator_values()

void adjust_accumulator_values ( gimple_stmt_iterator gsi, tree m, tree a, edge back )

static

Adjust the accumulator values according to A and M after GSI, and update
the phi nodes on edge BACK.   

References a, a_acc, add_successor_phi_arg(), adjust_return_value_with_ops(), force_gimple_operand_gsi(), GSI_SAME_STMT, integer_onep(), m_acc, NULL, and update_accumulator_with_ops().

Referenced by eliminate_tail_call().

adjust_return_value()

void adjust_return_value ( basic_block bb, tree m, tree a )

static

Adjust value of the return at the end of BB according to M and A
accumulators.   

References a, a_acc, adjust_return_value_with_ops(), as_a(), bb_seq(), error_mark_node, gcc_assert, gimple_return_retval(), gimple_return_set_retval(), gimple_seq_last_stmt(), gsi_last_bb(), m_acc, and update_stmt().

Referenced by tree_optimize_tail_calls_1().

adjust_return_value_with_ops()

tree adjust_return_value_with_ops ( enum tree_code code, const char * label, tree acc, tree op1, gimple_stmt_iterator gsi )

static

Creates a GIMPLE statement which computes the operation specified by
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.   

References current_function_decl, DECL_RESULT, fold_build2, fold_convert, force_gimple_operand_gsi(), gcc_assert, gimple_build_assign(), gsi_insert_before(), GSI_NEW_STMT, GSI_SAME_STMT, make_temp_ssa_name(), NULL, POINTER_TYPE_P, sizetype, TREE_TYPE, and types_compatible_p().

Referenced by adjust_accumulator_values(), and adjust_return_value().

create_tailcall_accumulator()

tree create_tailcall_accumulator ( const char * label, basic_block bb, tree init )

static

Creates a tail-call accumulator of the same type as the return type of the
current function.  LABEL is the name used to creating the temporary
variable for the accumulator.  The accumulator will be inserted in the
phis of a basic block BB with single predecessor with an initial value
INIT converted to the current function return type.   

References add_phi_arg(), create_phi_node(), current_function_decl, DECL_RESULT, make_temp_ssa_name(), NULL, PHI_RESULT, POINTER_TYPE_P, single_pred_edge(), sizetype, TREE_TYPE, and UNKNOWN_LOCATION.

Referenced by tree_optimize_tail_calls_1().

decrease_profile()

void decrease_profile ( basic_block bb, profile_count count )

static

Subtract COUNT and FREQUENCY from the basic block and it's
outgoing edge.   

References basic_block_def::count, and count.

Referenced by eliminate_tail_call().

eliminate_tail_call()

void eliminate_tail_call ( struct tailcall * t, class loop *& new_loop )

static

Eliminates tail call described by T.  TMP_VARS is a list of
temporary variables used to copy the function arguments.
Allocates *NEW_LOOP if not already done and initializes it.   

References tailcall::add, add_phi_arg(), adjust_accumulator_values(), alloc_loop(), profile_probability::always(), as_a(), bitmap_bit_p, tailcall::call_gsi, cfun, count, create_tmp_var, current_function_decl, DECL_ARGUMENTS, DECL_CHAIN, decrease_profile(), dump_file, dump_flags, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, loop::finite_p, g, gcc_assert, get_base_address(), gimple_bb(), gimple_build_assign(), gimple_build_nop(), gimple_call_arg(), gimple_call_lhs(), gimple_call_noreturn_p(), gimple_location(), gsi_bb(), gsi_insert_before(), gsi_last_bb(), gsi_next(), gsi_prev(), gsi_remove(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), loop::header, i, basic_block_def::index, is_gimple_call(), is_gimple_reg_type(), make_edge(), tailcall::mult, NULL, NULL_TREE, PENDING_STMT, gphi_iterator::phi(), PHI_RESULT, print_gimple_stmt(), redirect_edge_and_branch(), release_defs(), single_non_eh_succ_edge(), single_succ(), SSA_NAME_DEF_STMT, SSA_NAME_VAR, tailr_arg_needs_copy, TDF_DETAILS, TDF_SLIM, TREE_CODE, and TREE_TYPE.

Referenced by optimize_tail_call().

empty_eh_cleanup()

bool empty_eh_cleanup ( basic_block bb, int * eh_has_tsan_func_exit, int cnt )

static

Return true if there is no real work performed in the exception
path starting at BB and it will in the end result in external exception.
Search at most CNT basic blocks (so that we don't need to do trivial
loop discovery).   

References cfun, EDGE_COUNT, empty_eh_cleanup(), g, gimple_call_builtin_p(), gimple_clobber_p(), gsi_after_labels(), gsi_end_p(), gsi_next(), gsi_stmt(), is_gimple_debug(), is_gimple_resx(), sanitize_flags_p(), SANITIZE_THREAD, single_succ(), single_succ_p(), stmt_can_throw_external(), and basic_block_def::succs.

Referenced by empty_eh_cleanup(), and find_tail_calls().

execute_tail_calls()

unsigned int execute_tail_calls ( void )

static

References tree_optimize_tail_calls_1().

find_tail_calls()

void find_tail_calls ( basic_block bb, struct tailcall ** ret, bool only_musttail, bool & opt_tailcalls, bool diag_musttail, int & retry_tsan_func_exit )

static

Finds tailcalls falling into basic block BB.  The list of found tailcalls is
added to the start of RET.  When ONLY_MUSTTAIL is set only handle musttail.
Update OPT_TAILCALLS as output parameter.  If DIAG_MUSTTAIL, diagnose
failures for musttail calls.  RETRY_TSAN_FUNC_EXIT is initially 0 and
in that case the last call is attempted to be tail called, including
__tsan_func_exit with -fsanitize=thread.  It is set to -1 if we
detect __tsan_func_exit call and in that case tree_optimize_tail_calls_1
will retry with it set to 1 (regardless of whether turning the
__tsan_func_exit was successfully detected as tail call or not) and that
will allow turning musttail calls before that call into tail calls as well
by adding __tsan_func_exit call before the call.   

References _, a, tailcall::add, as_a(), auto_var_in_fn_p(), BITMAP_ALLOC, bitmap_bit_p, BITMAP_FREE, bitmap_set_bit, tailcall::call_gsi, call_may_clobber_ref_p(), cfun, compute_live_vars(), current_function_decl, DECL_ARGUMENTS, DECL_ARTIFICIAL, DECL_CHAIN, DECL_NAME, DECL_RESULT, DECL_UID, dump_file, EDGE_COUNT, empty_eh_cleanup(), ERF_RETURN_ARG_MASK, ERF_RETURNS_ARG, FAIL, find_tail_calls(), fndecl_built_in_p(), fold_build2, fold_convert, FOR_EACH_EDGE, FOR_EACH_LOCAL_DECL, FOR_EACH_VEC_ELT, g, gimple_assign_lhs(), gimple_assign_rhs1(), gimple_bb(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_call_fntype(), gimple_call_internal_p(), gimple_call_lhs(), gimple_call_must_tail_p(), gimple_call_noreturn_p(), gimple_call_num_args(), gimple_call_return_flags(), gimple_clobber_p(), gimple_has_volatile_ops(), gimple_location(), gimple_num_ops(), gimple_op(), gimple_phi_arg_def_from_edge(), gimple_range_type(), gimple_references_memory_p(), gimple_return_retval(), gsi_end_p(), gsi_for_stmt(), gsi_last_bb(), gsi_move_before(), gsi_next(), gsi_prev(), gsi_start_bb(), gsi_stmt(), has_abnormal_or_eh_outgoing_edge_p(), tailcall::has_tsan_func_exit, i, independent_of_stmt_p(), basic_block_def::index, INTEGRAL_TYPE_P, ipa_return_value_range(), is_empty_type(), is_gimple_assign(), is_gimple_call(), is_gimple_debug(), is_gimple_reg(), is_gimple_reg_type(), is_gimple_variable(), live_vars, live_vars_at_stmt(), live_vars_vec, may_be_aliased(), maybe_error_musttail(), tailcall::mult, tailcall::next, NULL, NULL_TREE, operand_equal_p(), POINTER_TYPE_P, basic_block_def::preds, print_gimple_stmt(), process_assignment(), propagate_through_phis(), recursive_call_p(), ref_maybe_used_by_stmt_p(), sanitize_flags_p(), SANITIZE_THREAD, SCALAR_FLOAT_TYPE_P, single_non_eh_succ_edge(), single_succ_p(), value_range::singleton_p(), ssa_default_def(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, stmt_can_throw_external(), stmt_could_throw_p(), basic_block_def::succs, suitable_for_tail_call_opt_p(), suitable_for_tail_opt_p(), suppress_warning(), tailcall::tail_recursion, tailr_arg_needs_copy, TREE_ADDRESSABLE, TREE_CODE, TREE_THIS_VOLATILE, TREE_TYPE, TRY_MOVE, useless_type_conversion_p(), VAR_P, VOID_TYPE_P, warning_at(), and warning_suppressed_p().

Referenced by find_tail_calls(), and tree_optimize_tail_calls_1().

gate_tail_calls()

bool gate_tail_calls ( void )

static

References dbg_cnt().

independent_of_stmt_p()

tree independent_of_stmt_p ( tree expr, gimple * at, gimple_stmt_iterator gsi, bitmap to_move )

static

Checks whether the expression EXPR in stmt AT is independent of the
statement pointed to by GSI (in a sense that we already know EXPR's value
at GSI).  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 GSI.   

References basic_block_def::aux, bitmap_bit_p, FOR_EACH_EDGE, gcc_assert, gimple_bb(), gsi_end_p(), gsi_next(), gsi_stmt(), is_gimple_min_invariant(), NULL, NULL_TREE, PHI_ARG_DEF_FROM_EDGE, basic_block_def::preds, single_non_eh_succ_edge(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, and TREE_CODE.

Referenced by find_tail_calls(), and process_assignment().

make_pass_musttail()

gimple_opt_pass * make_pass_musttail

(

gcc::context *

ctxt

)

make_pass_tail_calls()

gimple_opt_pass * make_pass_tail_calls

(

gcc::context *

ctxt

)

make_pass_tail_recursion()

gimple_opt_pass * make_pass_tail_recursion

(

gcc::context *

ctxt

)

maybe_error_musttail()

void maybe_error_musttail ( gcall * call, const char * err, bool diag_musttail )

static

Report an error for failing to tail convert must call CALL
with error message ERR. Also clear the flag to prevent further
errors.   

References dump_file, dump_flags, error_at(), gimple_call_must_tail_p(), gimple_call_set_must_tail(), gimple_call_set_tail(), gimple_location(), print_gimple_stmt(), TDF_DETAILS, and TDF_SLIM.

Referenced by find_tail_calls(), suitable_for_tail_call_opt_p(), suitable_for_tail_opt_p(), and tree_optimize_tail_calls_1().

optimize_tail_call()

bool optimize_tail_call ( struct tailcall * t, bool opt_tailcalls, class loop *& new_loop )

static

Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
mark the tailcalls for the sibcall optimization.   

References as_a(), builtin_decl_implicit(), tailcall::call_gsi, cfun, dump_file, dump_flags, eliminate_tail_call(), g, gimple_build_call(), gimple_call_set_tail(), gimple_set_location(), gsi_bb(), gsi_insert_before(), GSI_SAME_STMT, gsi_stmt(), tailcall::has_tsan_func_exit, print_gimple_stmt(), tailcall::tail_recursion, and TDF_DETAILS.

Referenced by tree_optimize_tail_calls_1().

process_assignment()

par process_assignment ( gassign * stmt, gimple_stmt_iterator call, tree * m, tree * a, tree * ass_var, bitmap to_move )

static

Simulates the effect of an assignment STMT on the return value of the tail
recursive CALL passed in ASS_VAR.  M and A are the multiplicative and the
additive factor for the real return value.   

References a, build_minus_one_cst(), current_function_decl, DECL_RESULT, FAIL, FIXED_POINT_TYPE_P, FLOAT_TYPE_P, fold_build1, get_gimple_rhs_class(), gimple_assign_cast_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, GIMPLE_SINGLE_RHS, GIMPLE_UNARY_RHS, independent_of_stmt_p(), INTEGRAL_TYPE_P, NULL_TREE, OK, TREE_TYPE, TRY_MOVE, type_has_mode_precision_p(), and TYPE_MODE.

Referenced by find_tail_calls().

propagate_through_phis()

tree propagate_through_phis ( tree var, edge e )

static

Propagate VAR through phis on edge E.   

References gsi_end_p(), gsi_next(), gsi_start_phis(), gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, and PHI_RESULT.

Referenced by find_tail_calls().

single_non_eh_succ_edge()

edge single_non_eh_succ_edge ( basic_block bb )

static

Return single successor edge ignoring EDGE_EH edges.   

References FOR_EACH_EDGE, gcc_assert, NULL, and basic_block_def::succs.

Referenced by eliminate_tail_call(), find_tail_calls(), and independent_of_stmt_p().

suitable_for_tail_call_opt_p()

bool suitable_for_tail_call_opt_p ( gcall * call, bool diag_musttail )

static

Returns false when the function is not suitable for tail call optimization
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. CALL is call to report error for.   

References _, auto_var_in_fn_p(), cfun, current_function_decl, current_function_has_exception_handlers(), DECL_ARTIFICIAL, DECL_NAME, get_base_address(), gimple_call_arg(), gimple_call_must_tail_p(), gimple_call_num_args(), gimple_location(), global_options, i, maybe_error_musttail(), POINTER_TYPE_P, suppress_warning(), TREE_CODE, TREE_OPERAND, TREE_TYPE, UI_SJLJ, and warning_at().

Referenced by find_tail_calls().

suitable_for_tail_opt_p()

bool suitable_for_tail_opt_p ( gcall * call, bool diag_musttail )

static

Returns false when the function is not suitable for tail call optimization
from some reason (e.g. if it takes variable number of arguments). CALL
is call to report for.   

References _, cfun, and maybe_error_musttail().

Referenced by find_tail_calls().

tree_optimize_tail_calls_1()

unsigned int tree_optimize_tail_calls_1 ( bool opt_tailcalls, bool only_musttail, bool diag_musttail )

static

Optimizes tail calls in the function, turning the tail recursion
into iteration.  When ONLY_MUSTTAIL is true only optimize musttail
marked calls.  When DIAG_MUSTTAIL, diagnose if musttail calls can't
be tail call optimized.   

References _, a, a_acc, add_loop(), add_phi_arg(), adjust_return_value(), as_a(), bitmap_bit_p, BITMAP_FREE, build_one_cst(), build_zero_cst(), CDI_DOMINATORS, cfun, changed, create_phi_node(), create_tailcall_accumulator(), current_function_decl, DECL_ARGUMENTS, DECL_CHAIN, DECL_RESULT, destroy_live_vars(), EDGE_COUNT, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, EXPR_LOCATION, find_tail_calls(), FOR_EACH_BB_FN, FOR_EACH_EDGE, free(), free_dominance_info(), gimple_call_must_tail_p(), gimple_call_noreturn_p(), gimple_seq_empty_p(), gsi_last_bb(), gsi_stmt(), is_gimple_call(), is_gimple_reg_type(), last_nondebug_stmt(), live_vars, live_vars_vec, loops_for_fn(), m_acc, make_ssa_name(), mark_virtual_operands_for_renaming(), maybe_error_musttail(), loop::next, tailcall::next, NULL, NULL_TREE, optimize_tail_call(), phi_nodes(), POINTER_TYPE_P, safe_is_a(), set_ssa_default_def(), single_pred_edge(), single_pred_p(), single_succ(), single_succ_edge(), single_succ_p(), sizetype, split_edge(), ssa_default_def(), SSA_NAME_DEF_STMT, basic_block_def::succs, tailr_arg_needs_copy, TODO_cleanup_cfg, TODO_update_ssa_only_virtuals, and TREE_TYPE.

Referenced by execute_tail_calls().

update_accumulator_with_ops()

tree update_accumulator_with_ops ( enum tree_code code, tree acc, tree op1, gimple_stmt_iterator gsi )

static

Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
the computation specified by CODE and OP1 and insert the statement
at the position specified by GSI as a new statement.  Returns new SSA name
of updated accumulator.   

References copy_ssa_name(), fold_build2, fold_convert, force_gimple_operand_gsi(), gimple_build_assign(), GSI_CONTINUE_LINKING, gsi_insert_after(), GSI_NEW_STMT, NULL, TREE_TYPE, and types_compatible_p().

Referenced by adjust_accumulator_values().

Variable Documentation

a_acc

tree a_acc

static

Referenced by adjust_accumulator_values(), adjust_return_value(), and tree_optimize_tail_calls_1().

live_vars

live_vars_map* live_vars

static

Argument for compute_live_vars/live_vars_at_stmt and what compute_live_vars
returns.  Computed lazily, but just once for the function.   

Referenced by find_tail_calls(), and tree_optimize_tail_calls_1().

live_vars_vec

vec<bitmap_head> live_vars_vec

static

Referenced by find_tail_calls(), and tree_optimize_tail_calls_1().

m_acc

tree m_acc

static

The variables holding the value of multiplicative and additive
accumulator.   

Referenced by adjust_accumulator_values(), adjust_return_value(), and tree_optimize_tail_calls_1().

tailr_arg_needs_copy

bitmap tailr_arg_needs_copy

static

Bitmap with a bit for each function parameter which is set to true if we
have to copy the parameter for conversion of tail-recursive calls.   

Referenced by eliminate_tail_call(), find_tail_calls(), and tree_optimize_tail_calls_1().