[m-rev.] for review: extend mutual tail rec optimization to functions

[Julien Fischer]

On Tue, 12 Sep 2017, Zoltan Somogyi wrote:

> For review by Julien, since this builds on a diff that he reviewed,
> so he is in the best position to understand it quickly.
>
> The attached file TSCC_PROC shows that stage2 of a bootcheck
> contains 23 optimized mutually recursive functions, as well as
> 270 optimized mutually recursive predicates.
>
> The approach implemented in this diff should work to optimize
> mutual tail recursion in Java and C# as well as C. It is not yet
> turned on for those languages, because I can't test it yet.

...

> Extend mutual tail recursion optimization to functions.

...

> compiler/ml_args_util.m:
>     When computing the information needed for tscc arguments, don't assume
>     that there are no copy-out output arguments. Instead, compute the
>     information ml_proc_gen.m needs to handle them. This means returning
>     a full function signature (including return values), the list of rvals
>     to return, and the list of pre-return assignment statements.
>
>     Simplify the code of ml_append_return_statement. Since ml_proc_gen.m
>     now computes its own return statements (based on the information mentioned
>     in the previous paragraph) back to handle just the situation it was

There are some words missing there.

>     originally designed for: simple procedure bodies that are *not* parts
>     of TSCCs. Simplify its code also by requiring its callers to give it
>     the return values as rvals, not lvals, because the callers can give it
>     the return values in this form just as easily, and it is more efficient,
>     since it lets us avoid the construction of a list.
> 
> compiler/ml_proc_gen.m:
>     Let det functions be part of TSCCs. Handle their return values as described
>     above. Handle the construction of return statements for procedure bodies
>     in TSCCs separately from return statements in standalone procedures.
> 
> compiler/ml_closure_gen.m:
>     Conform to the changes in ml_args_util.m.

> diff --git a/compiler/ml_args_util.m b/compiler/ml_args_util.m
> index 82200d7..a32f464 100644
> --- a/compiler/ml_args_util.m
> +++ b/compiler/ml_args_util.m

...

> @@ -179,30 +179,42 @@
>      % The value returned in TsccInLocalVarDefns will be a local var definition
>      % of each variable in TsccInArgs. This is used to define those variables
>      % in copies of the TSCC code that are *not* for this procedure.
> +    % (This is we ensure that each lvn_tscc_proc_input_var will be defined
> +    % by exactly one of TsccInLocalVarDefns and TsccInArgs in each copy.)
>      %
> -    % The value returned in TsccArgs is a list of all the arguments of the
> -    % procedure, both input and output, in declaration order. This will be
> -    % the argument list of the copy of the TSCC for this procedure,
> -    % and thus it will define the lvn_tscc_proc_input_vars in that copy.
> -    % (Thus the lvn_tscc_proc_input_vars will be defined by exactly one of
> -    % TsccInLocalVarDefns and TsccInArgs in each copy.)
> +    % The value returned in FuncParams will be the signature of the function.
> +    % The function's arguments will be a list of all the input arguments and
> +    % all the byref output arguments of the procedure, in declaration order;
> +    % the returns will be a list of all the copied-out output arguments,
> +    % again in declaration order, possibly preceded by a success indicator
> +    % (if the code model is model_semi). ReturnRvals will contain the
> +    % the rvals representing all the copied-out output arguments, which should
> +    % all be returned together in a retun statement. These will consist
> +    % of the copied-out output arguments' lvn_tscc_output_vars, again
> +    % possibly preceded by a success indicator.
>      %
>      % Each procedure's part in the TSCC defines local MLDS variables for each
> -    % argument, both input and output (returned in OwnLocalVarDefns), and
> -    % its code starts by copying the values of each lvn_tscc_proc_input_var
> -    % *and* lvn_tscc_output_var to the local var (from OwnLocalVarDefns)
> -    % corresponding to them. For input argument, this copies the value;
> -    % for output arguments, this copies the address where the argument's value
> -    % should be put. These assignments are returned in CopyTsccToOwnStmts.
> -    %
> -:- pred ml_gen_tscc_arg_params(module_info::in, prog_context::in,
> -    proc_id_in_tscc::in, prog_varset::in,
> +    % argument, both input and output (returned in OwnLocalVarDefns). Its code
> +    % starts by copying the values of each lvn_tscc_proc_input_var
> +    % and each byref lvn_tscc_output_var to the corresponding local var.
> +    % For input argument, this copies the value; for byref output arguments,

s/input argument/input arguments/

> +    % this copies the address where the argument's value should be put.
> +    % These assignments are returned in CopyTsccToOwnStmts. This will be
> +    % followed by the code of the procedure body, which in turn will be
> +    % followed by CopyOwnToTsccStmts, which will copy each of the procedure's
> +    % copied-out output vars (if there are any) to its corresponding
> +    % lvn_tscc_output_var. After this, a return statement constructed around
> +    % ReturnRvals will then return these (and maybe a success indication)
> +    % to the caller.

...

> diff --git a/compiler/ml_proc_gen.m b/compiler/ml_proc_gen.m
> index ae5316d..a90423e 100644
> --- a/compiler/ml_proc_gen.m
> +++ b/compiler/ml_proc_gen.m

...

> @@ -761,22 +765,47 @@ ml_gen_tscc(ModuleInfo, Target, ConstStructMap, _SCCEntryPredProcIds,
>          % hoisted-out definitions. Therefore, until we teach ml_elim_nested.m
>          % not to do that, we abandon the optimization of mutually recursive
>          % tail calls in the presence of such nested function definitions.
> +        %
> +        % Caveat 3.
> +        % The code in mark_tail_calls.m looks for tail calls by looking
> +        % at the argument lists of procedures. These argument lists treat
> +        % a variable representing the result of functions the same as
> +        % a variable representing the last argument of a predicate.
> +        % On the other hand, on the C backend, the MLDS uses two *different*
> +        % mechanisms to return these arguments; it returns function results
> +        % via return statements, while it uses pass-by-reference for all
> +        % other output arguments. Currently, ml_gen_tscc_trial handles this
> +        % by returning CanGenerateTscc = can_not_generate_code_for_tscc
> +        % if the procedures in the TSCC it is given don't all have the same
> +        % vector of return values.
> +        % XXX When a TSCC contains both predicates and functions, the two
> +        % must present different signatures to their callers *outside* the
> +        % TSCC, because those callers expect those different signatures.
> +        % However, *inside* the TSCC, we could generate code that ignores
> +        % the distinction, the obvious way of doing that being to use
> +        % the tail call version of the caling convention intended for

s/caling/calling/

> +        % predicates for all intra-TSCC tail calls. However, using different
> +        % conventions for intra- and inter-TSCC parameter passing would
> +        % complicate the code both here and in ml_args_util.m, and for now
> +        % at least, I (zs) don't see that the potential benefits justify
> +        % the costs.
> +        %

...

> @@ -997,8 +1042,9 @@ separate_mutually_recursive_procs(NoMutualTailRecProcs,
>
>                  % Argument definitions for the TSCC variables for all
>                  % the arguments of the procedure, both input and output,
> -                % in their original order.
> -                ppiai_tscc_args                 :: list(mlds_argument),
> +                % in their original order, and the types of the returned
> +                % arguments.
> +                ppiai_tscc_func_params          :: mlds_func_params,
>
>                  % The tscc variables for the input arguments of procedure i
>                  % in the TSCC will be defined
> @@ -1009,23 +1055,39 @@ separate_mutually_recursive_procs(NoMutualTailRecProcs,
>                  % - at the top of the body of the MLDS function,
>                  %   if the MLDS function is for procedure j with i != j.
>                  %
> -                % The tscc variables for the output arguments will always
> -                % be defined in the argument list of the MLDS function.
> +                % The tscc variables for the byref output arguments will

Why has tscc suddenly become lowercase here?  It was uppercase above.

> +                % always be defined in the argument list of the MLDS function.
> +                % The tscc variables for the copied-out output arguments will
> +                % always be defined at the top of the body of the MLDS
> +                % function.

The diff looks fine otherwise.

Julien.