[m-rev.] for review: self-tail-calls in MLDS code generator

[Peter Wang]

On Sat, 05 Aug 2017 13:43:14 +0200 (CEST), "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> Implement self-tail-call optimization in the MLDS code generator.
> 
> This is a step towards implementing not just self- but also mutual
> tail recursion in the MLDS code generator.
> 

> diff --git a/compiler/mark_tail_calls.m b/compiler/mark_tail_calls.m
> index 102e9c6..96c356f 100644
> --- a/compiler/mark_tail_calls.m
> +++ b/compiler/mark_tail_calls.m
> @@ -97,6 +108,47 @@
>  
>  %---------------------------------------------------------------------------%
>  %
> +% These types and predicates are exported for ml_proc_gen.m and ml_call_gen.m.
> +% ml_proc_gen.m sets up the warning parameters, and ml_call_gen.m uses them
> +% when it finds that it even though mark_tail_calls.m has marked a call
> +% as a tail call, it cannot actual implement that call as a tail call.
> +%

Fix that sentence.

> +%---------------------------------------------------------------------------%
> +%
>  % These predicates are exported for ml_tailcall.m; see above for the reason.
>  %
>  
> @@ -122,16 +174,29 @@
>      proc_id::in, simple_call_id::in, warning_or_error::in, prog_context::in,
>      list(error_spec)::in, list(error_spec)::out) is det.
>  
> -    % add_message_for_no_tail_or_nontail_recursive_calls(SimpleCallId, Context,
> -    %   !Specs):
> +    % Have we found any recursive call been found so far?

Fix that sentence.

>      %
> -    % Add warning to !Specs reporting that the procedure described by
> +    % We use this to generate warnings about pragmas that intend to control
> +    % how recursive calls that are not *tail* recursive should be treated,
> +    % when the procedure they are about contains no recursive calls at all,
> +    % either self-recursive or (if we have SCC information) mutually recursive.
> +    %
> +:- type found_any_rec_calls
> +    --->    not_found_any_rec_calls
> +    ;       found_any_rec_calls.
> +
> +    % maybe_report_no_tail_or_nontail_recursive_calls(PredInfo, ProcInfo
> +    %   FoundAnyRecCalls, Context, !Specs):
> +    %
> +    % If FoundAnyRecCalls = not_found_any_rec_calls but ProcInfo
> +    % say the procedure has a pragma about tail recursive calls on it,

says

> +    % then add a message to !Specs reporting that the procedure described by
>      % SimpleCallId contains no recursive calls at all, tail-recursive or

> @@ -857,13 +908,33 @@ mark_tail_rec_calls_in_goal(Goal0, Goal, AtTail0, AtTail, !Info) :-
>          GoalExpr = conj(ConjType, Goals),
>          Goal = hlds_goal(GoalExpr, GoalInfo0)
>      ;
> -        GoalExpr0 = disj(Disjs0),
> -        project_seen_later_rec_call(AtTail0, SeenLaterRecCall0),
> -        list.map_foldl2(mark_tail_rec_calls_in_disj(AtTail0), Disjs0, Disjs,
> -            SeenLaterRecCall0, SeenLaterRecCall, !Info),
> -        AtTail = not_at_tail(SeenLaterRecCall),
> -        GoalExpr = disj(Disjs),
> -        Goal = hlds_goal(GoalExpr, GoalInfo0)
> +        GoalExpr0 = disj(Disjuncts0),
> +        ( if list.split_last(Disjuncts0, NonLastDisjuncts0, LastDisjunct0) then
> +            % If the disjunction is in tail position, then it is possible
> +            % for a goal inside the last disjunct to be a tail call.
> +            mark_tail_rec_calls_in_goal(LastDisjunct0, LastDisjunct,
> +                AtTail0, LastAtTail, !Info),
> +            % Even if the disjunction as a whole is in tail position,
> +            % a goal inside a nonlast disjunct cannot be a tail call,
> +            % because if it fails, its execution will be followed
> +            % by backtracking to later disjuncts.
> +            project_seen_later_rec_call(LastAtTail, SeenLaterRecCall0),
> +            NonLastAtTail0 = not_at_tail(SeenLaterRecCall0),
> +            list.map_foldl2(
> +                mark_tail_rec_calls_in_nonlast_disjunct(NonLastAtTail0),
> +                NonLastDisjuncts0, NonLastDisjuncts,
> +                SeenLaterRecCall0, SeenLaterRecCall, !Info),
> +            AtTail = not_at_tail(SeenLaterRecCall),
> +            GoalExpr = disj(NonLastDisjuncts ++ [LastDisjunct]),
> +            Goal = hlds_goal(GoalExpr, GoalInfo0)
> +        else
> +            % There are no disjuncts. Any goals before the disjunct

disjunction

> +            % will be followed by disj([]), which is `fail', so they cannot
> +            % be tail calls.
> +            project_seen_later_rec_call(AtTail0, SeenLaterRecCall),
> +            AtTail = not_at_tail(SeenLaterRecCall),
> +            Goal = Goal0
> +        )
>      ;
>          GoalExpr0 = switch(Var, CanFail, Cases0),
>          project_seen_later_rec_call(AtTail0, SeenLaterRecCall0),

> diff --git a/compiler/ml_optimize.m b/compiler/ml_optimize.m
> index 5c19ae8..a8b63d2 100644
> --- a/compiler/ml_optimize.m
> +++ b/compiler/ml_optimize.m
> @@ -35,9 +35,61 @@
>  :- import_module libs.
>  :- import_module libs.globals.
>  :- import_module ml_backend.mlds.
> +:- import_module parse_tree.
> +:- import_module parse_tree.prog_data.
> +
> +:- import_module list.
>  
>  :- pred mlds_optimize(globals::in, mlds::in, mlds::out) is det.
>  
> +    % XXX Temporarily exported to ml_call_gen.m. When tail recursion
> +    % optimization is moved completely into the code generator,
> +    % this whole predicate will be moved to ml_call_gen.m.
> +    %
> +    % Assign the given list of rvals (the actual parameter) to the given list
> +    % of mlds_arguments (the formal parameter). This is used as part of tail
> +    % recursion optimization (see above).
> +    %
> +    % For each actual parameter that differs from its corresponding formal
> +    % parameter, we declare a temporary variable to hold the next value
> +    % of the formal parameter, and assign it the value of the actual parameter.
> +    % Once this has been done for all parameters, we then assign each formal
> +    % parameter its next value. The code we generate looks like this:
> +    %
> +    %   % These are returned in TempDefns.
> +    %   SomeType new_value_of_arg1;
> +    %   SomeType new_value_of_arg3;
> +    %   SomeType new_value_of_arg3;
> +    %
> +    %   % These are returned in InitStmts.
> +    %   new_value_of_arg1 = <the a new value of parameter 1>
> +    %   new_value_of_arg2 = <the a new value of parameter 2>
> +    %   new_value_of_arg3 = <the a new value of parameter 3>

the a

That looks fine, otherwise.

Peter