[m-dev.] Thinking about mode analysis and uniqueness

[Ralph Becket]

Nancy Mazur, Tuesday,  7 January 2003:
> 
> Hmmm, okay, I'm starting to see the point... The main difference is that
> you want to propagate the declared uniqueness information into the
> procedure, and try to derive from this information as much valuable
> reuse information as possible. Am I correct to say that you're only
> interested in unique terms which are related to arguments that were
> declared as such? 

Pretty much.  If I only get to handle uniqueness following from
arguments that are explicitly labelled as such, then I'll be happy.  I
actually don't see why the analysis won't do slightly better (it should
also spot local opportunities for reuse), but it certainly isn't
anything like as sophisticated or general as your approach to CTGC.

> > The rule (dX, X < Y) => dY says that live values cannot include dead
> > components.
> 
> I'm still confused about your terminology. Further on you make clear
> that uX means that the outermost constructor of X is unique. 
> But the statement dY, resp. lY, means that the whole structure of Y is dead, 
> resp. alive?  Including its components? 
> Am I right? 

No: dY means there are no further live references (direct or indirect)
to Y or one of its possible aliases.  It's a necessary condition for
reuse of the top-level cell of Y.  For example, if Y = f(X), Y may die
and the f(_) cell may be reusable, but this does not mean that X is
necessarily dead.

lY is just the negation of dY.

> Hmmm, I guess I'm still wrong... 
> Sorry of being so blunt ;-) 
> But the meanings of uX, dX, and lX are still not fully clear to me as
> with respect to the components of X... 
> 
> 	dX = outermost functor of X is dead (= not used in the further
> 	     computation of the program)

That's right.

> 	dY = outermost functor of Y is dead
> 
> 	Y = f(X,Z,..) => X < Y
> 	
> 	So, outermost functor of X is dead, ie. not used.. but for
> example, Z may still be used?

If dX and X < Y then dY in this scheme.  But you're right - this doesn't
affect the liveness of Z.

> and is perhaps not dead. Oh, I see, but if
> Y would have still been in use, then so would X... 
> Okay, okay.. I got it.. sorry... You're right.. ;-) 

Phew!  You had me worried there.

> > > but I don't see
> > > how this rule will ever get applied.
> 
> this remark was because of my bad understanding of what you meant by
> dX, only the outermost functor being dead... 

Ah, right.  My fault for being unclear.

> > The point is to identify safe cells for reuse in the context of nested
> > unique values.
> 
> ... based on the uniqueness declarations provided by the programmer. 

Yes, although since the current mode inference will spot unique
arguments, the analysis should work for these cases too.

> > No, I can have a uniquely referenced value f(Y, Z) which has the unique
> > reference for Y and a shared reference for Z.
> 
> Again my confusion of what you mean by uY, i.e. the outermost functor of
> Y is unique. 

Yes.

> The point was that I didn't fully understand that you are planning to
> infer local uniqueness purely based on the declared unique modes. 
> 
> So if I'm right, it's not your primer intention to try to reuse parts and bits 
> of structures that are only declared as input for example, hence being
> considered as 'shared' ?

Yes - if the programmer asserts that something is shared at the call
site then the analysis here assumes the programmer is correct.  The
motivation here is just to get nested unique modes working.  CTGC is
more ambitious.

> > > I think you should be more specific on how the 'least upper bound' of
> > > the different elements in your domain is... because it is the least
> > > upper bound that you are computing here... 
> > 
> > I'm sorry - it may be because I've had a couple of beers, but I'm not
> > clear what you mean here!  Can you rephrase the suggestion?
> 
> Well, my terminology was a bit too technical perhaps. What I meant is
> that typically you combine the information collected for each branch of
> a disjunction, and approximate the result by one single value which is a
> correct and safe description of what happens in each of the branches. 

That sounds fair.

> In your scheme above, you say that X < Y in one branch results in X < Y
> for the whole disjunction (hmm, I now see that you wrote s < Y, was that
> the purpose?).

No, that's a typo.  What I meant to say was

		if P | sX    then (P ; Q) | sX    (and similarly for Q),
		if P | X < Y then (P ; Q) | X < Y (and similarly for Q),
		if P | X ~ Y then (P ; Q) | X ~ Y (and similarly for Q).

> In the next line you say that if one branch gices X ~ Y,
> then the whole disjunction will be X ~ Y. 
> And therefore my natural question: if one branch yields X < Y, and the
> other X ~ Y, what is the result? What is the final approximation you
> take for correct? 

Earlier today I posted a fix: < means possible use and is not a partial
order.  Consider the following:

	(
		Y = a,
		X = f(Y)
	;
		X = a,
		Y = f(X)
	;
		Y = a,
		X = Y
	)

This disjunction gives all three of X ~ Y, X < Y and Y < X.

> The analysis is not focused on declared unique terms, but is able to
> derive for itself which (parts of) input arguments become dead in the
> context of the procedure. This requires interprocedural analysis as you
> need detailed aliasing information between terms. 

Ah, I'm really just thinking of intra-procedural analysis.

> > I really don't want to reinvent the wheel, but I was under the
> > impression that your analysis was far more general and costly than what
> > I have in mind.
> 
> It is indeed. 

Right.  I wanted something that would be cheap at compile-time.  CTGC
sounds like an uber-optimization rather than something necessary to
support the language.

> It's a full interprocedural analysis, with fixpoints and the whole lot. 

Yikes!  Too costly to have turned on all the time then.

> > Definitely!  I should go and re-read your papers.  Or have you a
> > disseration I could look at?
> 
> Not yet, writing it as we speak ;-) 

Welcome to Hell!

Thanks again for the feedback.

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