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

[Paul Bone]

On Tue, Mar 28, 2017 at 08:50:56PM +1100, Zoltan Somogyi wrote:
> 
> 
> 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.

I don't see how it's a partial traversal per procedure.  Since the single
thunk is created before the HLDS->LLDS passes, and forced the first time a
predicate is processed, and cached by the lazy code. (lazy.m uses mutvars
internally to update the value once it is known).

However, you're right in that I can make it's computation and use much
clearer by explicitly computing it once (again, before the HLDS->LLDS)
passes, and passing it in to
mark_tail_rec_calls_in_{pred,proc}_for_llds_code_gen explicitly.

> > --- 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.

Agreed, I'll see what I can learn about git commit hooks.

> > --- a/compiler/mark_tail_calls.m
> > +++ b/compiler/mark_tail_calls.m
> 
> > +    % 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.

Okay, I should be finished with this file soon.

> > @@ -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.

Normally yes, however I don't intend to support creating warnings for mutual
recursion but not self recursion.  The issue is raised again below and I'll
discuss it there.

> > @@ -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.

Yes.  I guess the question is, do people who use Mercury, but don't
implement it, know this?  Many will once they give it some thought, but some
won't.  Likewise I once surprised Peter Schachte with this:

    p(X::out, Y::out) :-
        ...,
        p(Y, X).

He assumed it was tail recursive, when it isn't.  This case is more subtle,
and one that _is_ tail recursive in Prolog, but perhaps people could make
a similar error with negation.

> > --- 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?

I agree, that would be cleaner.

I picked this strategy because the tail recursion pragma cannot represent
warnings for mutually recursive calls but not self recursive calls.  And I
don't think this combination makes much sense, but if you think it's useful
I'm happy to reconsider all of: the computer options, the types within the
compiler and the tail recursion pragma.

If we don't think it'd be useful to represent mutual recursion warnings but
not self recursion warnings, then I'd prefer to leave most types, and the
pragma as is.  However I agree with you that the compiler options should be
changed as you proposed.  I don't like it that an option can be implied by
another and set by the user.

I'll fix the command line options now.

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

I've fixed the other things you mentioned and will commit soon.

Depending on your feedback, I'm happy to separately change handling the
negated goals, and allowing warnings for mutual but not self recursion.


-- 
Paul Bone
http://paul.bone.id.au