[mercury-users] Automatic Recognition of Uniqueness

[Fergus Henderson]

On 09-Sep-1998, Ralph Becket <rwab1 at cam.sri.com> wrote:
> It occurs to me (speaking as a non-compiler writer) that under certain
> conditions it should be possible to spot when particular structures
> are uniquely referenced: that is, they are used exactly once.  If you
> can do this, then update-in-place becomes a possibility.  For example,
> arrays are often quite handy things for graph algorithms which are
> also often deterministic.  You could probably do some nifty
> intra-module optimisation like this.
> 
> Or is this what people mean by compile-time garbage collection?

Yes, that's basically what people usually mean by compile-time garbage
collection.

> Anyway, is it reasonable to expect a compiler to do uniqueness
> analysis and, if so, is there a plan to add it to the compiler?

The Mercury compiler already does quite a bit of that sort of uniqueness
analysis.  See the "unique modes" section of the Mercury reference manual
for details.  The ideas on which Mercury's uniqueness analysis are based
are described in a bit more detail in my honours report, which is available
via the `papers' section of the Mercury home page.

However, the current implementation has a few limitations in this area.
It doesn't handle `ui' modes properly, and it also doesn't actually
take advantage of the analysis to do update-in-place for user-defined
data structures (though it *does* do update-in-place for builtin types
such as arrays).

Andrew Bromage has been working on fixing the limitations in the analysis
and Simon Taylor has been working on getting the compiler to take advantage
of it to do update-in-place for user-defined data structures.  These changes
are nearly ready, I believe, but they won't make it into release 0.8.

Cheers,
	Fergus.

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