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 "common/common-target.h"
#include "ipa-utils.h"
#include "tree-ssa-live.h"
Include dependency graph for tree-tailcall.cc:

Data Structures

struct  tailcall


enum  par { FAIL , OK , TRY_MOVE }


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_passmake_pass_tail_recursion (gcc::context *ctxt)
gimple_opt_passmake_pass_tail_calls (gcc::context *ctxt)


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


Function Documentation

◆ add_successor_phi_arg()

static void add_successor_phi_arg ( edge e,
tree var,
tree phi_arg )
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 )
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 )

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

◆ find_tail_calls()

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

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

◆ update_accumulator_with_ops()

static tree update_accumulator_with_ops ( enum tree_code code,
tree acc,
tree op1,
gimple_stmt_iterator gsi )
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

◆ live_vars

live_vars_map* live_vars
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

◆ m_acc

tree m_acc
The variables holding the value of multiplicative and additive

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

◆ tailr_arg_needs_copy

bitmap tailr_arg_needs_copy
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().