[mercury-users] Automatic Recognition of Uniqueness

[Zoltan Somogyi]

> My thought was that it should be
> possible to spot when arguments with modes
> 
> 	:- pred p(..., T::in, T::out, ...) is det.
> 
> could be replaced with
> 
> 	:- pred p(..., T:di, T::uo, ...) is det.
> 
> I would have thought this was managable on an intra-module basis.

Since there may be calls from other modules which provide a non-unique
argument in the input position, *replacing* the first mode declaration
with the second cannot be done on an intra-module basis, unless predicate p
is not only local to the module but all calls to it specify a data structure
whose uniqueness does not depend on any data structure that is built up outside
this module.

Intra-module analysis *may* be able to decide that the second mode declaration
should be *added* to the first, with the unique mode being used whenever
a call specifies a unique data structure for this argument and the non-unique
mode for all other calls. However, deciding whether the expected payback in
execution time is sufficient to outweigh the fixed cost of the increase in
program size is also difficult in the absence of information about other
modules.

> Just as a matter of interest, has anybody done any analysis to see
> what proportion of code generated could benefit from destructive
> update like this?

A manual analysis of a set of programs that is large enough for a reasonably
accurate answer would be very expensive and error prone. While one can guess
based on limited samples and intuition, an accurate answer requires an
automated implementation.

Zoltan Somogyi <zs at cs.mu.OZ.AU> http://www.cs.mu.oz.au/~zs/
Department of Computer Science, University of Melbourne, AUSTRALIA