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 "common/common-target.h"
#include "ipa-utils.h"
#include "tree-ssa-live.h"

Include dependency graph for tree-tailcall.cc:

Data Structures
struct	tailcall

Enumerations
enum	par { FAIL , OK , TRY_MOVE }

Functions
static bool	suitable_for_tail_opt_p (void)
static bool	suitable_for_tail_call_opt_p (void)
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 void	find_tail_calls (basic_block bb, struct tailcall **ret)
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)
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)

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()

static 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, ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_phis(), gphi_iterator::phi(), PHI_RESULT, and UNKNOWN_LOCATION.

Referenced by adjust_accumulator_values().

adjust_accumulator_values()

static 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(), ggc_alloc(), GSI_SAME_STMT, integer_onep(), m_acc, NULL, and update_accumulator_with_ops().

Referenced by eliminate_tail_call().

adjust_return_value()

static 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(), bb_seq(), error_mark_node, gcc_assert, ggc_alloc(), 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()

static 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, ggc_alloc(), 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()

static 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, ggc_alloc(), 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()

static 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, count, EDGE_COUNT, gcc_assert, single_succ_p(), and basic_block_def::succs.

Referenced by eliminate_tail_call().

eliminate_tail_call()

static 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_count::apply_scale(), bitmap_bit_p, tailcall::call_gsi, cfun, count, current_function_decl, DECL_ARGUMENTS, DECL_CHAIN, decrease_profile(), dump_file, dump_flags, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, gcc_assert, ggc_alloc(), gimple_bb(), gimple_build_nop(), gimple_call_arg(), gimple_call_lhs(), gimple_location(), gsi_bb(), gsi_last_bb(), gsi_next(), gsi_prev(), gsi_remove(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, is_gimple_call(), tailcall::mult, NULL, NULL_TREE, PENDING_STMT, PHI_RESULT, print_gimple_stmt(), redirect_edge_and_branch(), release_defs(), single_succ(), single_succ_edge(), SSA_NAME_DEF_STMT, SSA_NAME_VAR, tailr_arg_needs_copy, TDF_DETAILS, TDF_SLIM, and TREE_CODE.

Referenced by optimize_tail_call().

execute_tail_calls()

static unsigned int execute_tail_calls ( void )

static

References tree_optimize_tail_calls_1().

find_tail_calls()

static void find_tail_calls ( basic_block bb, struct tailcall ** ret )

static

Finds tailcalls falling into basic block BB. The list of found tailcalls is
added to the start of RET.   

References a, auto_var_in_fn_p(), BITMAP_ALLOC, bitmap_bit_p, BITMAP_FREE, bitmap_set_bit, call_may_clobber_ref_p(), cfun, compute_live_vars(), current_function_decl, DECL_ARGUMENTS, DECL_CHAIN, DECL_RESULT, DECL_UID, FAIL, find_tail_calls(), fndecl_built_in_p(), fold_build2, fold_convert, FOR_EACH_EDGE, FOR_EACH_LOCAL_DECL, FOR_EACH_VEC_ELT, hash_map< KeyId, Value, Traits >::get(), ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_arg(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_num_args(), gimple_clobber_p(), gimple_has_volatile_ops(), gimple_num_ops(), gimple_op(), 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(), i, independent_of_stmt_p(), is_empty_type(), is_gimple_assign(), is_gimple_call(), is_gimple_debug(), is_gimple_reg(), is_gimple_reg_type(), live_vars, live_vars_at_stmt(), live_vars_vec, may_be_aliased(), NULL, NULL_TREE, POINTER_TYPE_P, basic_block_def::preds, process_assignment(), propagate_through_phis(), hash_map< KeyId, Value, Traits >::put(), recursive_call_p(), ref_maybe_used_by_stmt_p(), single_succ(), single_succ_edge(), single_succ_p(), ssa_default_def(), SSA_NAME_VERSION, stmt_can_throw_external(), stmt_could_throw_p(), tailcall::tail_recursion, tailr_arg_needs_copy, TREE_CODE, TREE_TYPE, TRY_MOVE, useless_type_conversion_p(), and VAR_P.

Referenced by find_tail_calls(), and tree_optimize_tail_calls_1().

gate_tail_calls()

static bool gate_tail_calls ( void )

static

References dbg_cnt(), and ggc_alloc().

independent_of_stmt_p()

static 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, expr, FOR_EACH_EDGE, gcc_assert, ggc_alloc(), 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_succ(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, and TREE_CODE.

Referenced by find_tail_calls(), and process_assignment().

make_pass_tail_calls()

gimple_opt_pass * make_pass_tail_calls

(

gcc::context *

ctxt

)

References ggc_alloc().

make_pass_tail_recursion()

gimple_opt_pass * make_pass_tail_recursion

(

gcc::context *

ctxt

)

References ggc_alloc().

optimize_tail_call()

static 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 tailcall::call_gsi, cfun, dump_file, dump_flags, eliminate_tail_call(), ggc_alloc(), gimple_call_set_tail(), gsi_bb(), gsi_stmt(), print_gimple_stmt(), tailcall::tail_recursion, and TDF_DETAILS.

Referenced by tree_optimize_tail_calls_1().

process_assignment()

static 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, FLOAT_TYPE_P, fold_build1, get_gimple_rhs_class(), ggc_alloc(), 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()

static 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().

suitable_for_tail_call_opt_p()

static bool suitable_for_tail_call_opt_p ( void )

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.   

References cfun, current_function_decl, current_function_has_exception_handlers(), DECL_ARGUMENTS, DECL_CHAIN, ggc_alloc(), global_options, TREE_ADDRESSABLE, and UI_SJLJ.

Referenced by tree_optimize_tail_calls_1().

suitable_for_tail_opt_p()

static bool suitable_for_tail_opt_p ( void )

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).   

References cfun.

Referenced by tree_optimize_tail_calls_1().

tree_optimize_tail_calls_1()

static unsigned int tree_optimize_tail_calls_1 ( bool opt_tailcalls )

static

Optimizes tail calls in the function, turning the tail recursion
into iteration.   

References a_acc, add_loop(), add_phi_arg(), adjust_return_value(), 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(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, EXPR_LOCATION, find_tail_calls(), FOR_EACH_EDGE, free(), free_dominance_info(), ggc_alloc(), gimple_seq_empty_p(), gsi_last_bb(), live_vars, live_vars_vec, loops_for_fn(), m_acc, make_ssa_name(), mark_virtual_operands_for_renaming(), loop::next, tailcall::next, NULL, NULL_TREE, optimize_tail_call(), phi_nodes(), POINTER_TYPE_P, set_ssa_default_def(), single_pred_edge(), single_pred_p(), single_succ(), single_succ_edge(), sizetype, split_edge(), ssa_default_def(), SSA_NAME_DEF_STMT, suitable_for_tail_call_opt_p(), suitable_for_tail_opt_p(), tailr_arg_needs_copy, TODO_cleanup_cfg, TODO_update_ssa_only_virtuals, and TREE_TYPE.

Referenced by execute_tail_calls().

update_accumulator_with_ops()

static 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(), ggc_alloc(), 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().