[m-rev.] for review: reassign.m

[Fergus Henderson]

On 08-Nov-2001, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> compiler/reassign.m:
> 	The new module that does the work.
> 
> compiler/optimize.m:
> 	Invoke the new module if the optimization is enabled. Invoke it after
> 	most other optimizations have been run, since they may create more
> 	opportunities for it.
> 
> compiler/option.m:
> 	Add a new option to control whether the new optimization is enabled.
> 	Turn on the new optimization at optimization level 3.
> 
> doc/user_guidex.texi:
> 	Document the new option.

s/guidex/guide/

The new module should be documented in notes/compiler_design.html.

> Index: compiler/reassign.m
...
> +% File: reassign.m
> +%
> +% Author: zs.
> +%
> +% This module implements an LLDS->LLDS transformation that optimizes
> +% instruction sequences such as the following extract from tree234__search:

It would help to start off the description of what this module does with
a summary similar to the description you put in the user guide.

The documentation should also make it clear that calls, labels, etc.
are conservatively assumed to clobber everything,
i.e. that it only works over extended basic blocks.

> +remove_reassign_loop([], _, _, RevInstrs, RevInstrs).
> +remove_reassign_loop([Instr0 | Instrs0], KnownContentsMap0, DepLvalMap0,
> +		RevInstrs0, RevInstrs) :-
...
> +		Uinstr0 = assign(Target, Source),
> +		(
> +			map__search(KnownContentsMap0, Target, KnownContents),
> +			KnownContents = Source
> +		->
> +			RevInstrs1 = RevInstrs0,
> +			KnownContentsMap = KnownContentsMap0,
> +			DepLvalMap = DepLvalMap0

A brief comment here would help.

> +	;
> +		Uinstr0 = reset_ticket(_, _),
> +		RevInstrs1 = [Instr0 | RevInstrs0],
> +		KnownContentsMap = KnownContentsMap0,
> +		DepLvalMap = DepLvalMap0

That's a bug.  You need to reset the maps to empty here.

> +	;
> +		Uinstr0 = init_sync_term(Target, _),
> +		RevInstrs1 = [Instr0 | RevInstrs0],
> +		clobber_dependents(Target, KnownContentsMap0, KnownContentsMap,
> +			DepLvalMap0, DepLvalMap)
> +	;
> +		Uinstr0 = fork(_, _, _),
> +		RevInstrs1 = [Instr0 | RevInstrs0],
> +		KnownContentsMap = KnownContentsMap0,
> +		DepLvalMap = DepLvalMap0
> +	;
> +		Uinstr0 = join_and_terminate(Target),
> +		RevInstrs1 = [Instr0 | RevInstrs0],
> +		clobber_dependents(Target, KnownContentsMap0, KnownContentsMap,
> +			DepLvalMap0, DepLvalMap)
> +	;
> +		Uinstr0 = join_and_continue(Target, _),
> +		RevInstrs1 = [Instr0 | RevInstrs0],
> +		clobber_dependents(Target, KnownContentsMap0, KnownContentsMap,
> +			DepLvalMap0, DepLvalMap)

I think you also need to reset the maps to empty here for
join_and_continue.  The other thread may have updated the stack.

For fork and join_and_terminate, I don't think it matters what you do,
but for consistency with the treatment of `goto' and `computed_goto'
you should probably reset the maps to empty.


> +		% LLDS code can refer to arbitrary locations on the stack
> +		% or in the heap with mem_ref lvals. Since we don't keep track
> +		% of which locations have their addresses taken, on any
> +		% assignment through a mem_ref lval we throw way the known
> +		% contents map. This is a conservative approximation of the
> +		% desired behaviour, which would invalidate only the entries
> +		% of lvals that may be referred to via this mem_ref.

This optimization is relying on there being no assignments via pointers
that happen to be aliased to other pointers, except for mem_ref lvals,
isn't it? 

Otherwise it might wrongly assume that a value remained unchanged
when the value had actually been modified via a different pointer
that happened to point to the same address.

AFAIK there is no documented invariant that LLDS code
not have any pointer aliasing except via mem_ref lvals.

Which would mean that either (a) this optimization is buggy
or (b) we need to document the new invariant, and check that
all the existing places which produce LLDS code satisfy it,
and make sure that it continues to hold.

I suspect that (b) would be difficult.

For example, what about code like this?

	redoip(curfr) = label1;
	redoip(maxfr) = label2;
	redoip(curfr) = label1; /* redundant? */

Wouldn't this optimization assume that curfr and maxfr don't alias,
and thus optimize away the "redundant" second assignment to redoip(curfr)?

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------