[m-dev.] for review: MLDS code generator design

[Fergus Henderson]

On 06-Aug-1999, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> > > I don't think the XXX is warranted at all. At the point just before <Then>,
> > > you can clobber (set to NULL) all variables only needed in the Else path,
> > > and vice versa.
> > 
> > Sure, but doing that is a bit tricky.  Not very tricky, I agree,
> > but nevertheless this is something I will leave out of version 0.1
> > (implementing switches, negations, etc. is more important than
> > getting perfect GC...) so for now I'll leave the XXX there.
> 
> In that case, you should also add a similar comment to disjunctions; when you
> fail out of a disjunct, you want to clobber all variables that were needed
> only in that disjunct.

I'm assuming that it is the responsibility of the target language
implementation to do whatever is needed to avoid having the GC trace
variables which have gone out of scope, if liveness-accurate GC is
desired.  (See below for rationale.)
That means that here in the MLDS code generator I just need to cover the cases
where a straight-forward liveness calculation on the generated MLDS does not
match up with the desired result of a straight-forward liveness calculation
on the HLDS.  That is, the MLDS code generator must generate code to clobber
variables which are no longer live according to a straight-forward liveness
calculation on the HLDS but which have not gone out of scope in the
generated MLDS, as is the case for variables in the `else' of a
nondet if-then-else once the `then' has been entered.

Disjunctions are a somewhat different case, because for disjunctions the
variables in question have gone out of scope in the generated MLDS code
once you've left that disjunct.  Since the notion of liveness in the HLDS
matches with that of liveness in the MLDS for this case, ensuring
liveness-accurate GC (if that is desired) is the MLDS back-end's problem.

The rataionale for leaving most of the responsibility for liveness-accurate
GC up to the MLDS back-end is as follows: at very least I need the target
language implementation's _cooperation_, since if the MLDS code generator
inserts statements to clobber variables that are no longer live, then an
uncooperative target language implementation could just optimize them away,
since they are assignments to dead variables.  Given this need for the MLDS
target back-end's cooperation, it makes sense to assign as much of the
responsibily for this task as is possible to the MLDS target back-end,
to keep the front-end simple and to keep the responsibility for this task
in one place.

However, in the case of nondet if-then-else, I can't just leave it to the
MLDS target back-end, because that would require assuming an unreasonably
smart liveness calculation in the MLDS target back-end.

Have a look at the code transformation in question:

%	/*
%       ** XXX The following transformation does not do as good a job of GC
%       **     as it could.  Ideally we ought to ensure that stuff used only
%       **     in the `Else' part will be reclaimed if a GC occurs during
%       **     the `Then' part.  But that is a bit tricky to achieve.
%       */
%
%       model_non cond:
%               <(Cond -> Then ; Else)>
%       ===>
%       {
%               bool succeeded;
%
%               void then_func() {
%                       succeeded = TRUE;
%                       <Then>
%               }
%
%               succeeded = FALSE;
%               <Cond && then_func()>
%               if (!succeeded) {
%                       <Else>
%               }
%	}

Here the MLDS code generator knows that as soon as the `then_func'
is entered, the variables used only in the `<Else>' will not be needed.
However, for the target language implementation to figure that out
would require significant cleverness in analyzing this code.
In general target language implementations are not going to possess
such cleverness, so we'd better handle it in the MLDS code generator.

These are subtle points, so I'll try to document them in the source code.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------