GCC Middle and Back End API Reference
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 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)
 
static bool suitable_for_tail_opt_p (gcall *call)
 
static bool suitable_for_tail_call_opt_p (gcall *call)
 
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, bool only_musttail, bool &opt_tailcalls)
 
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_mustcall)
 
static bool gate_tail_calls (void)
 
static unsigned int execute_tail_calls (void)
 
gimple_opt_passmake_pass_tail_recursion (gcc::context *ctxt)
 
gimple_opt_passmake_pass_tail_calls (gcc::context *ctxt)
 
gimple_opt_passmake_pass_musttail (gcc::context *ctxt)
 

Variables

static tree m_acc
 
static tree a_acc
 
static bitmap tailr_arg_needs_copy
 
static live_vars_maplive_vars
 
static vec< bitmap_headlive_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, 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(), 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(), 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()

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

◆ execute_tail_calls()

static unsigned int execute_tail_calls ( void )
static

◆ find_tail_calls()

static void find_tail_calls ( basic_block bb,
struct tailcall ** ret,
bool only_musttail,
bool & opt_tailcalls )
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.   

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_CHAIN, DECL_RESULT, DECL_UID, dump_file, 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(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_arg(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_must_tail_p(), 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(), has_abnormal_or_eh_outgoing_edge_p(), i, independent_of_stmt_p(), basic_block_def::index, 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(), maybe_error_musttail(), tailcall::mult, tailcall::next, NULL, NULL_TREE, POINTER_TYPE_P, basic_block_def::preds, print_gimple_stmt(), 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(), suitable_for_tail_call_opt_p(), suitable_for_tail_opt_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().

◆ 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, 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_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()

static void maybe_error_musttail ( gcall * call,
const char * err )
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, error_at(), gimple_call_must_tail_p(), gimple_call_set_must_tail(), gimple_call_set_tail(), gimple::location, print_gimple_stmt(), and TDF_SLIM.

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

◆ 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 as_a(), tailcall::call_gsi, cfun, dump_file, dump_flags, eliminate_tail_call(), 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(), 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 ( gcall * call)
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 _, cfun, current_function_decl, current_function_has_exception_handlers(), DECL_ARGUMENTS, DECL_CHAIN, global_options, maybe_error_musttail(), TREE_ADDRESSABLE, and UI_SJLJ.

Referenced by find_tail_calls().

◆ suitable_for_tail_opt_p()

static bool suitable_for_tail_opt_p ( gcall * call)
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()

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

◆ 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

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