#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tm_p.h"
#include "basic-block.h"
#include "function.h"
#include "gimple.h"
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
#include "tree-ssanames.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
#include "gimple-pretty-print.h"
#include "except.h"
#include "tree-pass.h"
#include "flags.h"
#include "langhooks.h"
#include "dbgcnt.h"
#include "target.h"
#include "cfgloop.h"
#include "common/common-target.h"
#include "ipa-utils.h"

Include dependency graph for tree-tailcall.c:

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.

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.

static void adjust_return_value ( )

static

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

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

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.

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.

Parameters that are only defined but never used need not be copied.

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.

RET_TYPE can be a float when -ffast-maths is enabled.

static void decrease_profile ( )

static

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

static void eliminate_tail_call ( struct tailcall * )

static

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.

 Remove the code after call_gsi that will become unreachable.  The
 possibly unreachable code in other blocks is removed later in
 cfg cleanup.

     Do not remove the return statement, so that redirect_edge_and_branch
     sees how the block ends.

 Number of executions of function has reduced by the tailcall.

 Replace the call by a jump to the start of function.

 Add phi node entries for arguments.  The ordering of the phi nodes should
 be the same as the ordering of the arguments.

 Update the values of accumulators.

     Result of the call will no longer be defined.  So adjust the
     SSA_NAME_DEF_STMT accordingly.

static unsigned int execute_tail_calls ( )

static

static unsigned int execute_tail_recursion ( )

static

static void find_tail_calls	(	basic_block	,
		struct tailcall **
	)

static

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.

     Ignore labels, returns, clobbers and debug stmts.

     Check for a call.

     If the statement references memory or volatile operands, fail.

     Recurse to the predecessors.

 If the LHS of our call is not just a simple register, we can't
 transform this into a tail or sibling call.  This situation happens,
 in (e.g.) "*p = foo()" where foo returns a struct.  In this case
 we won't have a temporary here, but we need to carry out the side
 effect anyway, so tailcall is impossible.

 ??? In some situations (when the struct is returned in memory via
 invisible argument) we could deal with this, e.g. by passing 'p'
 itself as that argument to foo, but it's too early to do this here,
 and expand_call() will not handle it anyway.  If it ever can, then
 we need to revisit this here, to allow that situation.

 We found the call, check whether it is suitable.

             Make sure there are no problems with copying.  The parameter
             have a copyable type and the two arguments must have reasonably
             equivalent types.  The latter requirement could be relaxed if
             we emitted a suitable type conversion statement.

             The parameter should be a real operand, so that phi node
             created for it at the start of the function has the meaning
             of copying the value.  This test implies is_gimple_reg_type
             from the previous condition, however this one could be
             relaxed by being more careful with copying the new value
             of the parameter (emitting appropriate GIMPLE_ASSIGN and
             updating the virtual operands).

 Make sure the tail invocation of this function does not refer
 to local variables.

 Now check the statements after the call.  None of them has virtual
 operands, so they may only depend on the call through its return
 value.  The return value should also be dependent on each of them,
 since we are running after dce.

     This is a gimple assign.

 See if this is a tail call we can handle.

 We may proceed if there either is no return value, or the return value
 is identical to the call's return.

 If this is not a tail recursive call, we cannot handle addends or
 multiplicands.

 For pointers only allow additions.

References gimple_call_lhs().

static bool gate_tail_calls ( )

static

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.

 Mark the blocks in the chain leading to the end.

     The default definition or defined before the chain.

         The value is a constant.

 Unmark the blocks.

References basic_block_def::aux, FOR_EACH_EDGE, gcc_assert, gimple_bb(), gsi_end_p(), gsi_next(), gsi_stmt(), NULL_TREE, PHI_ARG_DEF_FROM_EDGE, basic_block_def::preds, edge_def::src, SSA_NAME_DEF_STMT, and TREE_CODE.

gimple_opt_pass* make_pass_tail_calls ( )

gimple_opt_pass* make_pass_tail_recursion ( )

static bool optimize_tail_call	(	struct tailcall *	,
		bool
	)

static

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.

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.

 See if this is a simple copy operation of an SSA name to the function
 result.  In that case we may have a simple tail call.  Ignore type
 conversions that can never produce extra code between the function
 call and the function return.

     Reject a tailcall if the type conversion might need
     additional code.

     Fall through.

 Accumulator optimizations will reverse the order of operations.
 We can only do that for floating-point types if we're assuming
 that addition and multiplication are associative.

     TODO &ndash; Handle POINTER_PLUS_EXPR.

static tree propagate_through_phis ( )

static

Propagate VAR through phis on edge E.

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.

 alloca (until we have stack slot life analysis) inhibits
 sibling call optimizations, but not tail recursion.

 If we are using sjlj exceptions, we may need to add a call to
 _Unwind_SjLj_Unregister at exit of the function.  Which means
 that we cannot do any sibcall transformations.

 Any function that calls setjmp might have longjmp called from
 any called function.  ??? We really should represent this
 properly in the CFG so that this needn't be special cased.

 ??? It is OK if the argument of a function is taken in some cases,
 but not in all cases.  See PR15387 and PR19616.  Revisit for 4.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.

static unsigned int tree_optimize_tail_calls_1 ( )

static

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

Only traverse the normal exits, i.e. those that end with return
statement.

 Construct the phi nodes and accumulators if necessary.   


         Ensure that there is only one predecessor of the block
         or if there are existing degenerate PHI nodes.

         Copy the args if needed.

     When the tail call elimination using accumulators is performed,
     statements adding the accumulated value are inserted at all exits.
     This turns all other tail calls to non-tail ones.

     Modify the remaining return statements.

     We may have created new loops.  Make them magically appear.

 Add phi nodes for the virtual operands defined in the function to the
 header of the loop created by tail recursion elimination.  Do so
 by triggering the SSA renamer.

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.

Variable Documentation

tree a_acc

static

tree m_acc

static

The variables holding the value of multiplicative and additive accumulator.

Data Structures

Functions

Variables

Function Documentation

Variable Documentation