[m-rev.] for review: inter-module analysis framework

[Fergus Henderson]

On 23-Aug-2002, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> On 09-Aug-2002, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> > Some preliminary comments...
> > 
> > On 09-Aug-2002, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> > > 
> > > A first implementation of the inter-module analysis framwork.
> > 
> > Rationale?
> 
> "The current inter-module analysis scheme using `.trans_opt' files
> has some major limitations. The compilation dependencies introduced
> by `.trans_opt' files are too complicated for Mmake without major
> limitations on which modules can use the contents of which `.trans_opt'
> files. Also, the `.trans_opt' file system only computes greatest fixpoints,
> which is often too weak to find opportunities for optimization.
> A better solution is to provide a library which manually handles
> the dependencies introduced by inter-module analysis, and can deal with
> the complications introduced by cyclic module dependencies."

OK, that seems reasonable.

> > > Index: analysis/mer_analysis.m
> > > ===================================================================
> > > RCS file: analysis/mer_analysis.m
> > > diff -N analysis/mer_analysis.m
> > > --- /dev/null	1 Jan 1970 00:00:00 -0000
> > > +++ analysis/mer_analysis.m	1 Aug 2002 10:24:36 -0000
> > > @@ -0,0 +1,3 @@
> > > +:- module mer_analysis.
> > > +
> > > +:- import_module analysis.
> > 
> > What's the purpose of this module?
> 
> Just to match the naming of the other libraries in the Mercury system.

Oh, you mean that this module is actually a "library", in the sense
explained in the "Libraries" chapter of the Mercury user's guide, and
the name is chosen so that it matches our library naming convention?

There should be a comment in the source code explaining this.

> > Also, the change should include design documentation somewhere.
> 
> Here it is.
> 
> analysis/README:

I'm glad I asked for that, since the design documentation here is
a huge improvement!

> DESIGN:
> [...]

What about analysis of class methods?

The analysis framework looks OK for analysis of ordinary
procedure calls, but doesn't address higher-order calls
or class method calls.

If that is intentional, then I think it is worth noting
in the design documentation.

> Each analysis is described by a call pattern type and an
> answer pattern type. Call and answer patterns must form
> a partial order, and must be convertible to strings.

I think it would be helpful to explain what "call patterns"
and "answer patterns" are supposed to represent.

> Analysis dependency checker (NYI)
> =================================
...
> If the interface of a function changes, all of its answers are
> marked as invalid,

Did you mean to say "If the *implementation* of a function changes, ..."?

If not, I don't understand what you mean, since in the presence of
Mercury-style overloading a function with a different interface is
a different function.

> For greatest fixpoint analyses, if the new answer is
> - less precise than or incomparable with the old result,
>   all users of the call pattern are marked `invalid'.
> - equal to the old result, no entries need to be marked. 
> - more precise than the old result, callers are marked
>   as `suboptimal'.
> 
> If any `suboptimal' answers are used in computing the new answer,
> or there are any `suboptimal' answers in the SCC of the analysis
> dependency graph containing the entry, the entry for the function
> is marked as `suboptimal', otherwise it is marked as `optimal'.

The algorithm here is not quite right -- it will never reach the
`optimal' fixpoint, but instead will converge on a fixpoint in
which all results are marked as `suboptimal'.  You need to
initially assume that results are optimal and then only
mark them as suboptimal if they depend on something which
has changed.  (In other words, computing optimality itself
needs to be a least fixpoint computation rather than a
greatest fixpoint computation.)

> Recompilation must proceed until there are no `invalid' or `fixpoint_invalid'
> entries. Optionally, optimization can proceed until there are no new requests
> or `suboptimal' answers.

In the case where you are proceeding until there are no new requests,
how do you ensure termination?  What requirements are there on each
compiler's analyses to ensure overall termination?

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------