tree-tailcall.c File Reference

Data Structures
struct	tailcall

Functions
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 **)
static bool	suitable_for_tail_call_opt_p ()
static tree	independent_of_stmt_p ()
static bool	process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, tree *a, tree *ass_var)
static tree	propagate_through_phis ()
static void	find_tail_calls ()
static void	add_successor_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 ()
static void	adjust_return_value ()
static void	decrease_profile ()
static bool	arg_needs_copy_p ()
static void	eliminate_tail_call ()
static bool	optimize_tail_call ()
static tree	create_tailcall_accumulator ()
static unsigned int	tree_optimize_tail_calls_1 ()
static unsigned int	execute_tail_recursion ()
static bool	gate_tail_calls ()
static unsigned int	execute_tail_calls ()
gimple_opt_pass *	make_pass_tail_recursion ()
gimple_opt_pass *	make_pass_tail_calls ()

Variables
static tree	m_acc
static tree	a_acc

---

Function Documentation

static void add_successor_phi_arg ( )

static

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

References add_phi_arg(), edge_def::dest, gsi_end_p(), gsi_next(), gsi_start_phis(), and gsi_stmt().

Referenced by adjust_accumulator_values().

static void adjust_accumulator_values ( )

static

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

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

Referenced by eliminate_tail_call().

static void adjust_return_value ( )

static

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

References a_acc, adjust_return_value_with_ops(), bb_seq(), 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().

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, force_gimple_operand_gsi(), gimple_build_assign_with_ops(), gsi_insert_before(), GSI_NEW_STMT, GSI_SAME_STMT, make_temp_ssa_name(), and types_compatible_p().

Referenced by adjust_accumulator_values(), and adjust_return_value().

static bool arg_needs_copy_p ( )

static

Returns true if argument PARAM of the tail recursive call needs to be copied
   when the call is eliminated.   

References cfun, is_gimple_reg(), and ssa_default_def().

Referenced by eliminate_tail_call(), and tree_optimize_tail_calls_1().

static tree create_tailcall_accumulator ( )

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, make_temp_ssa_name(), and single_pred_edge().

Referenced by tree_optimize_tail_calls_1().

static void decrease_profile ( )

static

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

References count, edge_def::count, basic_block_def::count, frequency, basic_block_def::frequency, single_succ_edge(), single_succ_p(), and basic_block_def::succs.

Referenced by eliminate_tail_call().

static void eliminate_tail_call ( struct tailcall *  )

static

Referenced by optimize_tail_call().

static void eliminate_tail_call ( )

static

Eliminates tail call described by T.  TMP_VARS is a list of
   temporary variables used to copy the function arguments.   

References tailcall::add, add_phi_arg(), adjust_accumulator_values(), arg_needs_copy_p(), tailcall::call_gsi, edge_def::count, current_function_decl, decrease_profile(), edge_def::dest, dump_file, dump_flags, first, gimple_build_nop(), gimple_call_arg(), gimple_call_lhs(), gimple_location(), gsi_bb(), gsi_end_p(), gsi_next(), gsi_remove(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, is_gimple_call(), tailcall::mult, print_gimple_stmt(), redirect_edge_and_branch(), release_defs(), single_succ(), and single_succ_edge().

static unsigned int execute_tail_calls ( )

static

References tree_optimize_tail_calls_1().

static unsigned int execute_tail_recursion ( )

static

References tree_optimize_tail_calls_1().

static void find_tail_calls ( basic_block  , struct tailcall **    )

static

Referenced by find_tail_calls(), and tree_optimize_tail_calls_1().

static void find_tail_calls ( )

static

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

References tailcall::add, auto_var_in_fn_p(), tailcall::call_gsi, call_may_clobber_ref_p(), cfun, current_function_decl, function::decl, find_tail_calls(), gimple_call_arg(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_num_args(), gimple_clobber_p(), gimple_has_volatile_ops(), gimple_references_memory_p(), gimple_return_retval(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_prev(), gsi_start_bb(), gsi_stmt(), is_gimple_call(), is_gimple_debug(), is_gimple_reg(), is_gimple_reg_type(), tailcall::mult, tailcall::next, basic_block_def::preds, process_assignment(), propagate_through_phis(), ref_maybe_used_by_stmt_p(), single_succ(), single_succ_edge(), single_succ_p(), edge_def::src, tailcall::tail_recursion, and useless_type_conversion_p().

static bool gate_tail_calls ( )

static

References dbg_cnt().

static tree independent_of_stmt_p ( )

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, gimple_bb(), gsi_end_p(), gsi_next(), gsi_stmt(), is_gimple_min_invariant(), basic_block_def::preds, single_succ(), and edge_def::src.

Referenced by process_assignment().

gimple_opt_pass* make_pass_tail_calls

(

)

gimple_opt_pass* make_pass_tail_recursion

(

)

static bool optimize_tail_call ( struct tailcall *  , bool    )

static

Referenced by tree_optimize_tail_calls_1().

static bool optimize_tail_call ( )

static

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

References tailcall::call_gsi, dump_file, dump_flags, eliminate_tail_call(), gimple_call_set_tail(), gsi_bb(), gsi_stmt(), print_gimple_stmt(), and tailcall::tail_recursion.

static bool process_assignment ( gimple  stmt, gimple_stmt_iterator  call, tree *  m, tree *  a, tree *  ass_var  )

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 build_minus_one_cst(), current_function_decl, 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, and independent_of_stmt_p().

Referenced by find_tail_calls().

static tree propagate_through_phis ( )

static

Propagate VAR through phis on edge E.   

References edge_def::dest, gsi_end_p(), gsi_next(), gsi_start_phis(), and gsi_stmt().

Referenced by find_tail_calls().

static bool suitable_for_tail_call_opt_p ( )

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).
   This test must pass in addition to suitable_for_tail_opt_p in order to make
   tail call discovery happen.   

References function::calls_alloca, function::calls_setjmp, cfun, current_function_decl, current_function_has_exception_handlers(), and UI_SJLJ.

Referenced by tree_optimize_tail_calls_1().

static bool suitable_for_tail_opt_p ( )

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, and function::stdarg.

Referenced by tree_optimize_tail_calls_1().

static unsigned int tree_optimize_tail_calls_1 ( )

static

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

References a_acc, add_phi_arg(), adjust_return_value(), arg_needs_copy_p(), CDI_DOMINATORS, cfun, changed, create_phi_node(), create_tailcall_accumulator(), current_function_decl, find_tail_calls(), first, free(), free_dominance_info(), gimple_seq_empty_p(), last_stmt(), LOOPS_NEED_FIXUP, loops_state_set(), m_acc, make_ssa_name(), mark_virtual_operands_for_renaming(), tailcall::next, optimize_tail_call(), phi_nodes(), set_ssa_default_def(), single_pred_edge(), single_pred_p(), single_succ(), single_succ_edge(), split_edge(), edge_def::src, ssa_default_def(), suitable_for_tail_call_opt_p(), and suitable_for_tail_opt_p().

Referenced by execute_tail_calls(), and execute_tail_recursion().

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(), force_gimple_operand_gsi(), gimple_build_assign_with_ops(), GSI_CONTINUE_LINKING, gsi_insert_after(), GSI_NEW_STMT, and types_compatible_p().

Referenced by adjust_accumulator_values().

---

Variable Documentation

tree a_acc

static

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

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