[m-rev.] For review: --inline-linear-tail-rec-sccs

[Zoltan Somogyi]

On Thu, 23 Mar 2017 13:43:41 +1100, Paul Bone <paul at bone.id.au> wrote:
> I'd like to update my patch to be compatible with your changes.  Is that
> okay? would I be stepping on your toes some more?

I have just committed a diff addressing your review comments.
The ball is now in your court.

> > > > -    module_info_ensure_dependency_info(!ModuleInfo, DepInfo),
> > > > -    PredProcs = dependency_info_get_condensed_bottom_up_sccs(DepInfo),
> > > > -    set.init(InlinedProcs0),
> > > > -    do_inlining(PredProcs, NeededMap, Params, InlinedProcs0, !ModuleInfo),
> > > > +    % Build the call graph and extract the list of SCC. We process
> > > > +    % SCCs bottom up, so that if a caller wants to inline a callee
> > > > +    % in a lower SCC, it gets the *already optimized* version of the callee.
> > > > +    % If LinearTailRec = no, we don't try to do anything special about
> > > > +    % calls where the callee is in the *same* SCC as the caller.
> > > 
> > > List of SCCs
> > 
> > What correction are you proposing? *Everything* is in the list of SCCs.
> 
> Sorry.  s/list of SCC/list of SCCs/

That would have been easier to see if you put the comment immediately
below the line that it applied to.

> I think there are a few options.
> 
>     1 Keep it as it is.
>     2 Relax it:
>         + With a command line option to relax it, at least this allows
>           testing.  This could also be a threshold measured in the number of
>           tail calls.
>     3 Compare the size increase:
>         + Witn an option to enable it / set a threshold.
>     4 Leave it for a general solution that estimates the increase in code
>       size.
> 
> 2 seems easy, and might be as good as 3.  I'm not sure about 4 yet because I
> havn't yet tried to think of what a general SCC-aware inlining
> analysis/algorithm might look like.

I will do 2.
 
> > > I also wonder how useful it would be to relax this.  If only some of the
> > > tail calls are mutual calls.
> > > 
> > >     p :-
> > >         q.
> > >     q :-
> > >         (
> > >             r
> > >         ;
> > >             r,  % non-tail call.
> > >             ...
> > >         ).
> > >     r :-
> > >         p.
> > > 
> > > Inlining r into the tail recursive call site in q.  and q into p will result
> > > in constant stack space _if_ the first branch is executed.  If the first
> > > branch _is_ executed more often then this could be a good optimisation, if
> > > it isn't I don't think it would be a sagnificant pesimisation.  I guess the
> > > real question is would it be an optimisation enough of the time ti make
> > > writing the optimisation worth-while.
> > 
> > If you mean to imply that all the calls above are tail recursive with the
> > one marked exception, then code like that *will* be transformed,
> > because each procedure in the SCC has exactly one *tail* call
> > to another member of the SCC.
> 
> I see that now.  Because the second call to r is not in the TSCC.  Thanks.
> 
> > > You should update the copyright information on each of the files you touch.
> > > Copyright (C) 2017 The Mercury Team
> > 
> > With CVS, we had a pre commit hook to do this automatically.
> > Can someone who knows git better than me create something similar?
> 
> That's probably Peter W. or I.  It's not something I've looked before.  Has
> anyone who is reading this done this before?
> 
> > > > diff --git a/doc/user_guide.texi b/doc/user_guide.texi
> > > > index bb94558..e990a8d 100644
> > > > --- a/doc/user_guide.texi
> > > > +++ b/doc/user_guide.texi
> > > > @@ -8770,6 +8770,14 @@ containing more than @var{threshold} variables. Procedures
> > > >  containing large numbers of variables can cause
> > > >  slow compilation.
> > > >  
> > > > + at item --inline-linear-tail-rec-sccs @var{threshold}
> > > > + at findex --inline-linear-tail-rec-sccs
> > > > +Given a set of mutually recursive procedures (an SCC, or strongly
> > > > +connected component, of the call graph) in which each procedure
> > > > +contains exactly one call to a procedure in the SCC and
> > > > +that call is a tail call, inline the callee at every one of those
> > > > +call sites.
> > > > +
> > > 
> > > In this and maybe the --help text.  It'd be good to tell users what this
> > > means to them.  Eg: it reduces mutual recursion to self tail recursion,
> > > which the MLDS can optimize directly into a loop.
> > > 
> > > 
> > > There's only a couple of things I'd like changed before you commit it.
> > 
> > I committed it on tuesday, after warning on monday that I was going to do so.
> > 
> > If you have a suggestion for the extra text, post it as a diff for review.
> 
> Okay.

My diff contains a first crack at this.

Zoltan.