[m-rev.] for review: Enable non-tail-call warnings for mutually-recursive code

[Zoltan Somogyi]

On Tue, 28 Mar 2017 14:28:53 +1100, Paul Bone <paul at bone.id.au> wrote:
>  :- type dependency_info(T)
>      --->    dependency_info(
>                  dep_graph           :: dependency_graph(T),
>                  dep_arcs            :: dependency_arcs(T),
> -                dep_bottom_up_sccs  :: bottom_up_dependency_sccs(T)
> +                dep_bottom_up_sccs  :: bottom_up_dependency_sccs(T),
> +                % This is seldom used so it is lazy.
> +                dep_scc_map         :: lazy(map(T, set(T)))
>              ).

Don't add this as an extra field. Just add a predicate of function that,
when given either the whole dependency_info or just its dep_bottom_up_sccs
field, gives you back the map(T, set(T)). Doing this all at once requires
one traversal of the SCC list *total*; your solution requires one partial
traversal *per procedure*. Since an average partial traversal will traverse
half the list, with N procedures, this does N/2 times as much work.

> --- a/compiler/handle_options.m
> +++ b/compiler/handle_options.m
> @@ -1,7 +1,8 @@
>  %---------------------------------------------------------------------------%
>  % vim: ft=mercury ts=4 sw=4 et
>  %---------------------------------------------------------------------------%
> -% Copyright (C) 1994-2014 The University of Melbourne.
> +% Copyright (C) 1994-2012 The University of Melbourne.
> +% Copyright (C) 2013-2014, 2017 The Mercury Team.
>  % This file may only be copied under the terms of the GNU General

There were commits in this file in 2015 and 2016 as well.
This is why we either need a commit hook, or just stop caring about
updating the years.

> -    (
> -        WarnNonTailRec = no
> -    ;
> -        WarnNonTailRec = yes,
> +    option_implies(warn_non_tail_recursion, warn_non_tail_recursion_self,
> +        bool(yes), !Globals),
> +    globals.lookup_bool_option(!.Globals, warn_non_tail_recursion_self,
> +        WarnNonTailRecSelf),
> +    ( if
> +        WarnNonTailRecSelf = yes
> +    then
>          globals.lookup_bool_option(!.Globals, pessimize_tailcalls,
>              PessimizeTailCalls),
>          globals.lookup_bool_option(!.Globals, optimize_tailcalls,
> @@ -2217,6 +2219,8 @@ convert_options_to_globals(OptionTable0, OpMode, Target,
>          else
>              true
>          )
> +    else
> +        true
>      ),

I think changing the switch to an if-then-else is a backwards step.

> --- a/compiler/mark_tail_calls.m
> +++ b/compiler/mark_tail_calls.m
> @@ -2,6 +2,7 @@
>  % vim: ft=mercury ts=4 sw=4 et
>  %---------------------------------------------------------------------------%
>  % Copyright (C) 2001-2008, 2010-2012 The University of Melbourne.
> +% Copyright (C) 2017 The Mercury Team.

This file was also updated in 2014, 2015 and 2016 (not 2013).

>  % This file may only be copied under the terms of the GNU General
>  % Public License - see the file COPYING in the Mercury distribution.
>  %---------------------------------------------------------------------------%
> @@ -106,6 +107,17 @@
>      prog_context::in, warning_or_error::in,
>      list(error_spec)::in, list(error_spec)::out) is det.
>  
> +    % add_message_for_nontail_mutual_recursive_call(SimpleCallId, ProcId,
> +    %    WarnOrError, Context, !Specs):
> +    %
> +    % Add an error_spec to !Specs reporting that the mutually recursive call
> +    % inside the procedure described by SimpleCallId and ProcId at Context
> +    % is not *tail* recursive. Set its severity based on WarnOrError.
> +    %
> +:- pred add_message_for_nontail_mutual_recursive_call(simple_call_id::in,
> +    proc_id::in, simple_call_id::in, warning_or_error::in, prog_context::in,
> +    list(error_spec)::in, list(error_spec)::out) is det.

The comment has *one* SimpleCallId, the type signature has *two*.

> +    % maybe_warn_non_tail_rec_call(MaybeRequireTailrecPragma,
> +    %   WarnNonTailRecOpt) = MaybeRequireTailrec.
> +    %
> +    % Combine the require tail recursion pragma and the command line options
> +    % to determine if we should generate tail recursion warnings.
> +    %
> +:- func maybe_warn_non_tail_rec_call(maybe(require_tail_recursion),
> +    warn_non_tail_rec_calls_opt) = maybe_warn_non_tail_rec_call.
> +
> +maybe_warn_non_tail_rec_call(no, do_not_warn_non_tail_rec_calls_opt) =
> +    do_not_warn_non_tail_rec_calls.
> +maybe_warn_non_tail_rec_call(no, warn_non_tail_rec_calls_self_opt) =
> +    warn_non_tail_rec_calls(we_warning, only_self_recursion_must_be_tail).
> +maybe_warn_non_tail_rec_call(no, warn_non_tail_rec_calls_self_and_mut_opt) =
> +    warn_non_tail_rec_calls(we_warning,
> +        both_self_and_mutual_recursion_must_be_tail).
> +maybe_warn_non_tail_rec_call(yes(suppress_tailrec_warnings(_Context)), _) =
> +    do_not_warn_non_tail_rec_calls.
> +maybe_warn_non_tail_rec_call(
> +        yes(enable_tailrec_warnings(WoE, Type, _Context)), _) =
> +    warn_non_tail_rec_calls(WoE, Type).
> +

I don't like this code, but I will propose a fix post-commit.

> +    (
> +        MaybeDepInfo = yes(DepInfo),
> +        SCC = dependency_info_get_this_scc(DepInfo, proc(PredId, ProcId))
> +    ;
> +        MaybeDepInfo = no,
> +        unexpected($file, $pred, "Expected dependency information")
> +    ),

This wouldn't be needed if mercury_compile_llds_back_end.m computed
the mapping from proc_ids to SCCs, and passed it down to here.
It would also avoid a lot of wasted, repeated traversals of the list of SCCs.

> @@ -289,18 +352,19 @@ mark_tail_rec_calls_in_proc_for_llds_code_gen(ModuleInfo, PredId, ProcId,
>  
>  :- type warn_non_tail_rec_calls_opt
>      --->    do_not_warn_non_tail_rec_calls_opt
> -    ;       warn_non_tail_rec_calls_opt.
> +    ;       warn_non_tail_rec_calls_self_opt
> +    ;       warn_non_tail_rec_calls_self_and_mut_opt.

I think having two separate flags, one for self and one for mutual
recursion, would be cleaner.
 
> @@ -579,6 +615,8 @@ mark_tail_rec_calls_in_goal(Goal0, Goal, AtTail0, AtTail, !Info) :-
>      (
>          ( GoalExpr0 = call_foreign_proc(_, _, _, _, _, _, _)
>          ; GoalExpr0 = generic_call(_, _, _, _, _)
> +        % Note: we don't give tailcall warnings for negated goals, maybe we
> +        % should?
>          ; GoalExpr0 = negation(_)
>          ),

I don't think so. Any code in a negated scope *has* to be followed by the execution
of target language code that switches failure to success and vice versa, so any calls
in such scopes *inherently* cannot be tail recursive.

> +                maybe_report_nontail_recursive_call(CurProcId, CalleePredId,
> +                    SelfRecursion, Context, AtTail0, !Info)

Don't pass CurProcId here; let maybe_report_nontail_recursive_call get it from !.Info.
Passing it separately just invites bugs from misuse.

> +    (
> +        SelfOrMutRec = call_is_self_rec,
> +        add_message_for_nontail_recursive_call(CallerId, CallerProcId,
> +            Context, WarnOrError, Specs0, Specs)
> +    ;
> +        SelfOrMutRec = call_is_mutual_rec,
> +        module_info_pred_info(!.Info ^ mtc_module, CalleePredId,
> +            CalleePredInfo),
> +        CalleePredOrFunc = pred_info_is_pred_or_func(CalleePredInfo),
> +        CalleeName = qualified(pred_info_module(CalleePredInfo),
> +            pred_info_name(CalleePredInfo)),
> +        CalleeArity = pred_info_orig_arity(CalleePredInfo),
> +        CalleeId = simple_call_id(CalleePredOrFunc, CalleeName, CalleeArity),
> +        add_message_for_nontail_mutual_recursive_call(CallerId,
> +            CallerProcId, CalleeId, WarnOrError, Context, Specs0, Specs)
> +    ),
>      !Info ^ mtc_error_specs := Specs.

If one arm of this switch calls add_message_for_nontail_mutual_recursive_call,
then the name of the predicates called in the other arms *has* to include "self".
  
> --- a/compiler/mercury_compile_llds_back_end.m
> +++ b/compiler/mercury_compile_llds_back_end.m
> @@ -134,6 +134,10 @@ llds_backend_pass(!HLDS, !:GlobalData, LLDS, !DumpInfo, !IO) :-
>      map_args_to_regs(Verbose, Stats, !HLDS, !IO),
>      maybe_dump_hlds(!.HLDS, 305, "args_to_regs", !DumpInfo, !IO),
>  
> +    % The mark_tail_calls pass requires dependency information.  Generate
> +    % that now.
> +    module_info_rebuild_dependency_info(!HLDS, _),

Get the proc_id to scc map computed here.

> @@ -170,6 +171,7 @@
>      ;       warn_smart_recompilation
>      ;       warn_undefined_options_variables
>      ;       warn_non_tail_recursion
> +    ;       warn_non_tail_recursion_self

I would have three options here:

warn_non_tail_recursion_self,
warn_non_tail_recursion_mutual,
and warn_non_tail_recursion.

The first two would be plain boolean options, and the rest of the compiler
would only use those two. The third would be a special option,
and would simply set the two others. I think this approach of having
two separate independent options, and a master switch that sets them both,
is cleaner than having two independently settable options that have
overlapping effects. What, after all, should the compiler do in your design
if --warn-non-tail-recursion is set but --warn-non-tail-recursion-self is not?

You can go ahead and commit. If you want, I will address the above comments
after you do.

Zoltan.