[m-rev.] for review: extend mutual tail rec optimization to functions
jfischer at opturion.com
Wed Sep 13 14:09:25 AEST 2017
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.
> 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.
> 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.
> 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
> + % 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.
More information about the reviews