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

[Fergus Henderson]

On 06-Aug-1999, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> 
> > %		jmp_buf buf;
> > %		void success() {
> > %			longjmp(buf, TRUE);
> > %		}
> 
> The second arg of longjmp is an int, not a bool. It should be 1, the canonical
> non-zero value, but not via the TRUE macro.

OK.

> > % Code for conjunctions
> 
> You must also say what you do for empty conjunctions.

Shall do.

> > %	model_non goal (unoptimized)
> > %		<Goal, Goals>
> > % 	===>
> > %	{
> > %		entry_func() {
> > %			<Goal && succ_func()>;
> > %		}
> > %		succ_func() {
> > %			<Goals && SUCCEED()>;
> > %	 	}
> > %
> > %		entry_func();
> > %	}
> > %
> > %	model_non goal (optimized):
> > %		<Goal, Goals>
> > % 	===>
> > %	{
> > %	        succ_func() {
> > %			<Goals && SUCCEED()>;
> > %	        }
> > %
> > %	        <Goal && succ_func()>;
> > %	}
> 
> I don't see the point of generating the non-optimized version, and then
> optimizing it. You may as well generate the optimized version first, given
> that the code for doing so is trivial.

Yes -- that was actually my intention, I just didn't document it well.
I should have labelled those two versions "optimized for performance"
and "optimized for readability" rather than "optimized" and "unoptimized".
The idea is that there would be a compiler option for selecting whether
to optimize for performance or whether to try to generate readable code.
The advantage of the "unoptimized" one is that order of the C code
corresponds with the order of the conjuncts, whereas with the other one
they come out in reverse order.  The advantage of the "optimized" one
is performance -- generating them in reverse order makes it easier
for the C compiler to inline the nested functions.

> > %
> > % Code for disjunctions
> > %
> 
> Again you must say what you do for empty disjunctions. If I were you,
> I would treat empty and nonempty disjunctions differently, so there are
> three cases you must deal with:
> 
> 	disj([])
> 
> 	disj([Goal1, Goal2 | Goals])
> 	disj([Goal1])
> 
> The first is fail, the second and third are the nonlast and last disjunct
> cases of a non-empty disjunction.

Yes.  While writing the code to generate disjunctions, I came to the
same conclusions.  I will revise the documentation to reflect the code.

> > %	model_det goal:
> > %		<(Goal ; Goals) && SUCCEED()>
> 
> This (and others like this) would clearer if it read "model_det Goal".

OK.

> > %
> > % Code for if-then-else
> > %
> 
> I think you also need to deal with conditions that are det. Probably
> due to the extra sequencing required for ites, they are not transformed
> into conjunctions.

That's not correct -- if-then-elses with conditions that cannot fail do
get transformed into conjunctions.  See simplify.m line 882.

> > %	/*
> > %	** 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>
> > %		}
> > %	}
> 
> 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.

> Apart from these, the scheme is fine. My only other piece of advice would be
> not to use nested functions at all, and instead go straight for passing around
> pointers to blocks of variables. Do you know of any platforms on which the
> overheads of nested functions will be significantly smaller than simulating
> them ourselves?

The reason for using nested functions is mainly to keep the transformation
simple, not for efficiency.  As the comments said, a post-pass will convert
nested functions into something that the target understands and implements
efficiently.  Allowing arbitrary nesting in the MLDS makes it easy
to compile HLDS goals containing arbitrarily nested conjunctions and
disjunctions.

Furthermore, separating out way we implemented nested functions into
a separate post-pass is a good idea because will probably we need to
use a different post-pass when generating Java than the one we use when
generating C.  Java doesn't have pointers; instead of passing a pointer
to a struct and a function pointer, we'll want to pass an object containing
a virtual function.

As for the performance of nested functions versus simulating them ourselves,
I don't know what the relative performances will be,
but I would like to measure it rather than giving up entirely on the
possibility that nested functions might be more efficient.

In general compiling to nested functions gives the target compiler more
chance of optimizing things.  Compilers typically do liveness analysis
and allocate local variables with disjoint lifetimes into the same stack
slot, and if the target compiler supports nested functions then it may
well be able to do a good job of that even in the presence of nested
functions -- particularly if it inlines the calls to the nested functions.
On the other hand, compilers generally _don't_ do a good job of optimizing
structs, particularly not when the struct's address is taken.

> You must also beware of the "upward funarg" problem, which is keeping the
> address of a nested function after the stack frame that created it has
> returned. Even without higher-order code in the Mercury source being
> translated, the MLDS will create closures to support nondeterminism.

These scheme I've outlined only does two things with continuations:
it passes them as arguments, and it calls them.  They are
never returned and never stored inside heap objects or in global variables.
These conditions are sufficient to ensure that this scheme won't suffer
from that problem.

(In the case where the Mercury source code contains higher-order code,
the Mercury closures will be implemented by creating terms on the heap,
not by using nested functions.)

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