[m-dev.] for review: `possible' alias analysis stage

[Fergus Henderson]

On 10-Mar-2000, Nancy Mazur <Nancy.Mazur at cs.kuleuven.ac.be> wrote:
> > > Is this a rationale enough? Or should it be explained more 
> > > thoroughly? 
> > 
> > Well, the Mercury compiler is already quite capable of
> > not reusing the top-level list cell in the example above ;-)
> 
> it was a small example. 
> In attachment I've included a file that Mission Critical once gave us, 
> and for which explicit di/uo annotations are written, but for which
> our liveness analysis can automatically derive them. That wouldn't
> have been possible with the alias branch (as the alias branch 
> needs those di/uo's), and wouldn't have been possible without 
> possible aliasing information. 

The current Mercury compiler is quite capable of inferring those
di/uo's in many cases, including the example that you gave.  Indeed,
I'm pretty sure that the mode declarations in that example were originally
copied from the output of the Mercury compiler!  They look suspiciously
similar to the modes that the compiler infers, which tend to be a bit
different to the modes that a human would write by hand.

When I comment out the mode declarations in that file (except
for that for main/2), and then compile it with `--infer-all',
I get the following output:

frm_counters.m:043: Inferred :- mode doit(in, in, di, uo) is det.
frm_counters.m:059: Inferred :- mode process_counters(in, di, uo, di, uo) is det.
frm_counters.m:074: Inferred :- mode process_lines(in, in, di, uo, di, uo) is det.
frm_counters.m:088: Inferred :- mode update_errs(di, di, uo, di, uo) is det.
frm_counters.m:088: Inferred :- mode update_errs(in, di, uo, di, uo) is det.
frm_counters.m:096: Inferred :- mode process_line(in, out) is det.
frm_counters.m:107: Inferred :- mode print_counters(di, di, uo) is det.
frm_counters.m:107: Inferred :- mode print_counters(in, di, uo) is det.
frm_counters.m:133: Inferred :- mode print_one(di, di, di, di, uo) is det.
frm_counters.m:133: Inferred :- mode print_one(di, in, di, di, uo) is det.
frm_counters.m:143: Inferred :- mode update_counters(in, di, uo) is semidet.
frm_counters.m:244: Inferred :- mode prefix(in, out) is semidet.
frm_counters.m:247: Inferred :- mode suffix(in, di) is semidet.
frm_counters.m:252: Inferred :- mode sirocco(out, in, out) is semidet.
frm_counters.m:259: Inferred :- mode skip(di, in, out) is semidet.
frm_counters.m:268: Inferred :- mode brol(in, out) is semidet.
frm_counters.m:273: Inferred :- mode num_counters(out, in, out) is semidet.
frm_counters.m:281: Inferred :- mode counters(in, di, uo, in, out) is semidet.
frm_counters.m:236: Inferred :- mode analyze_line(out, di, uo, in, di) is semidet.

> Definite aliasing is (in the liveness analysis context) definitely 
> not enough for deciding whether some structures may be reused or not. 
> While there might be no definitie alias between some variable X and
> some variable Y, you cannot safely decide that one of those may be
> reused at some point. Only if you're sure that there will never ever
> be an alias between those two, you can safely make the decision. In
> order to know this 'never ever', possible aliasing information is
> needed.

That's true.  But the Mercury compiler's "uniqueness" analysis
does keep track of some degree of possible aliasing /
definite not aliasing:

	if a variable has inst `unique', it means that that
	variable definitely does not alias with anything
	(i.e. the possible alias set is empty)

	if a variable has inst `ground', it means that that
	variable might alias with anything
	(i.e. the possible alias set is the universal set)

If you're proposing that we do a more sophisticated analysis of possible
aliasing, I would like to know what benefit we will get from the
additional complication.

> > It would help more to have examples of where possible
> > aliasing information helps to reuse things that could not
> > otherwise be reused, using just the analyses that
> > Mercury compiler already performs (plus definite aliasing,
> > which is currently only supported on the `alias' branch).
> 
> with the example in the attachment, you will probably argue that
> the alias-branch does allow the reuse. But the only reason why it'll
> work on that file, is that some kind programmer provided the di/uo's.

No, as shown above, the Mercury compiler is quite capable of inferring
such modes.

Currently the compiler has only an `--infer-modes' option, not a
`--infer-uniqueness' option.  That is, currently the compiler will only infer
the modes if the programmer does not declare them; there is no option to get
the compiler to infer uniqueness if the programmer has declared the modes
using `in' or `out'.  But it would not be hard to add such an option.

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