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.  

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

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