[m-dev.] for review: fix bug with quantification & instmap deltas

[Andrew Bromage]

G'day all.

Simon Taylor wrote:

> It was removed when Andrew changed the instmap representation
> (instmap.m revision 1.15.2.15). Unfortunately he was a bit slack
> with the log message on that change, so there isn't anything
> written down describing the reason.

Whoops, sorry about that.  It's been a while.

> I think it had something to do with the fact that with alias tracking
> a goal can update the insts of variables that are not in its nonlocal set.

That's basically it.  A goal can update the insts of variables which
"touch" (via aliasing) variables which are not in its nonlocal set.
For example:

<<
:- mode create_unique(uo).
:- mode share(in).
:- mode use_uniquely(ui).

	some [Q] (
		create_unique(Q),
		X = foo(Q),
		Y = bar(Q)
	),
	share(X),
	use_uniquely(Y)		% Mode error, since Y became partly
				% shared when X was shared.
>>

The reason why we have to perform recompute_instmap_delta (which, BTW,
you can optimise by only re-running it if necessary; the fact that the
bug hasn't shown up until now seems to indicate that it's a rare enough
occurrence that doing a full recompute of the instmap_deltas when
necessary won't cost us that much) is that under the new regime, an
instmap_delta doesn't really mean anything on its own.  It is a space-
saving device, and all you can really do with them is:

	- Create one from two instmaps (i.e. compute the "difference")
	- Apply one to an instmap
	- Miscellaneous trivial stuff like testing if an instmap_delta
	  maps a reachable instmap into an unreachable one.

This is a design decision which was justified by how complex it was
to retro-fit onto the existing compiler the maintenance of instmap_deltas
the "old way" in the presence of aliasing.  I can't go through the
details right now (and I'm not sure I can remember them all anyway), but
the other alternatives which we tried at the time involved algorithms
that generated quadratically many new inst_keys based on the original
number of inst_keys, which was causing a significant slow-down.

Cheers,
Andrew Bromage
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------