Re: [tree-ssa] Tail recursion optimisation

[Steven Bosscher <s dot bosscher at student dot tudelft dot nl>]

Op za 18-10-2003, om 10:55 schreef Zdenek Dvorak:
> > > here is the patch with these changes.
> > 
> > ...but you forgot the new file.
> 
> :-(  Here it is.

Thanks.

> /* Returns false when the function is not suitable for tail call optimization
>    from some reason (e.g. if it takes variable number of arguments).  */
> 
> static bool
> suitable_for_tail_opt_p ()
> {
>   int i;
> 
>   if (current_function_stdarg)
>     return false;

If the current_function calls alloca, this should also return false to
avoid stack blowups.

>   /* No local variable should have its address taken, as otherwise it might
>      be passed to the recursive call.  This of course is overly
>      conservative and should be replaced by a dataflow analysis later.  */
>   for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++)
>     {
>       tree var = VARRAY_TREE (referenced_vars, i);
> 
>       if (TREE_CODE (var) == VAR_DECL

Should also check for PARM_DECL here???

> 	  && decl_function_context (var) == current_function_decl
> 	  && TREE_ADDRESSABLE (var))
> 	return false;
>     }
> 
>   return true;
> }


> 
> /* Checks whether basic block BB ends in a tail call.  If so, BSI is set
>    to point to it.  HAS_RETURN is set to true if the call is followed by
>    return.  */
> 
> static bool
> find_tail_call_p (basic_block bb, block_stmt_iterator *bsi, bool *has_return)
> {
---- 8< ----
>   func = TREE_OPERAND (stmt, 0);
>   if (TREE_CODE (func) != ADDR_EXPR)
>     return false;
>   func = TREE_OPERAND (func, 0);
>   if (func != current_function_decl)
>     return false;

You can use get_callee_fndecl here.


>   /* Copy the args if needed.  */
>   for (param = DECL_ARGUMENTS (current_function_decl),
>        args = TREE_OPERAND (stmt, 1),
>        tmp_var = tmp_vars;
>        param;
>        param = TREE_CHAIN (param),
>        args = TREE_CHAIN (args),
>        tmp_var = TREE_CHAIN (tmp_var))
>     if (param != TREE_VALUE (args)
> 	/* If the parameter is unused, it was not scanned in
> 	   find_referenced_vars, so we don't want to introduce
> 	   it here.  Additionally, it would obviously be
> 	   useless anyway.  */
> 	&& var_ann (param))
>       bsi_insert_before (&bsi,
> 			 build (MODIFY_EXPR, TREE_TYPE (param),
> 				TREE_VALUE (tmp_var),
> 				unshare_expr (TREE_VALUE (args))),
> 			 BSI_SAME_STMT);
>   for (param = DECL_ARGUMENTS (current_function_decl),
>        args = TREE_OPERAND (stmt, 1),
>        tmp_var = tmp_vars;
>        param;
>        param = TREE_CHAIN (param),
>        args = TREE_CHAIN (args),
>        tmp_var = TREE_CHAIN (tmp_var))
>     if (param != TREE_VALUE (args)
> 	&& var_ann (param))
>       bsi_insert_before (&bsi,
> 			 build (MODIFY_EXPR, TREE_TYPE (param),
> 				param, TREE_VALUE (tmp_var)),
> 			 BSI_SAME_STMT);

Why are you copying twice here?


>   if (bsi_end_p (bsi_s) || TREE_CODE (bsi_stmt (bsi_s)) != LABEL_EXPR)
>     {
>       label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
>       DECL_ARTIFICIAL (label) = 1;
>       DECL_CONTEXT (label) = current_function_decl;
>       emit_label = true;
>     }

<grin> Yet another build_decl (LABEL_DECL, ...).  There's this function
in tree-eh.c called make_label().  It should be moved "somewhere
generic", as its comment says.  I'll make a patch.

>   else
>     {
>       label = LABEL_EXPR_LABEL (bsi_stmt (bsi_s));
>       emit_label = false;
>     }
> 
>   if (has_return)
>     bsi_remove (&bsi);
>   bsi_replace (bsi, build1 (GOTO_EXPR, void_type_node, label));
> 
>   if (emit_label)
>     {
>       /* Emit the label; do it now, since otherwise we would conflict
> 	 with bsi in case the call is the first statement of the
> 	 program.  */

Ehm, why?  I thought `bsi' would simply be updated if you put something
in front of it.

Gr.
Steven