[m-dev.] for review: rewrite of duplicate elimination.

[Tyson Dowd]

On 22-Dec-1997, Zoltan Somogyi <zs at cs.mu.oz.au> wrote:
> 
> Estimated hours taken: 20
> 
> Give duplicate code elimination more teeth in dealing with similar arguments
> of difference function symbols. For the source code
> 
> 	:- type t1	--->	f(int)
> 			;	g(int, int).
> 
> 	:- pred p1(t1::in, int::out) is det.
> 
> 	p1(f(Y), Y).
> 	p1(g(Y, _), Y).
> 
> we now generate the C code
> 
> 	Define_entry(mercury__xdup__p1_2_0);
> 		r1 = const_mask_field(r1, (Integer) 0);
> 		proceed();
> 
> thus avoiding the cost of testing the function symbol.
> 
> runtime/mercury_tags.h:
> 	Add two new macros, mask_field and const_mask_field, that behave
> 	just like field and const_field except that instead of stripping
> 	off a known tag from the pointer, they strip (mask) off an unknown
> 	tag.

s/unknown/possibly unknown/

> compiler/llds.m:
> 	Change the first argument of the lval field/3 from tag to maybe(tag).
> 
> 	Make the comments on some types more readable.
> 
> compiler/llds_out.m:
> 	If the first arg of the lval field/3 is no, emit a (const_)mask_field
> 	macro; otherwise, emit a (const_)field macro.

The maybe doesn't convey the meaning very well. I'd prefer
	:- type field_remove ---> tag(int) ; mask.
or something similar. 

Is there any need for the previous mechanism to remain? 
Once you are going to do a field, it doesn't matter what the
tag is (unless the masking operation is slower than the subtraction).
If the old mechanism is only kept for performance reasons, this should
be documented.

> %
> % dupelim.m - eliminate some duplicate code sequences.
> %

> 
> 	% cluster(Exemplar, OtherLabels) means that references to labels
> 	% in OtherLabels can be replaced with references to Exemplar
> 	% once its block has been replaced with the most specific antiunified
> 	% version of the blocks started by Exemplar and OtherLabels.
> 	% OtherLabels must be nonempty.
> :- type cluster		--->	cluster(label, list(label)).

This comment isn't clear, because you've not mentioned "antiunified"
anywhere but the log message. 

> %-----------------------------------------------------------------------------%
> 
> :- pred process_clusters(list(cluster)::in, list(label)::in, list(label)::out,
> 	block_map::in, block_map::out,
> 	map(label, label)::in, map(label, label)::out) is det.

A comment describing what the processing does would be good.

> :- pred process_elim_labels(list(label)::in, list(instruction)::in,
> 	maybe(label)::in, list(label)::in, list(label)::out, block_map::in,
> 	label::in, map(label, label)::in, map(label, label)::out,
> 	list(instruction)::out, maybe(label)::out) is det.

And here.


> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
> 
> 	% The code of this section is concerned with computing the most
> 	% specific code sequence that generalizes both input sequneces.
> 
> :- pred most_specific_instrs(list(instruction)::in, maybe(label)::in,
> 	list(instruction)::in, maybe(label)::in,
> 	list(instruction)::out, maybe(label)::out) is semidet.
> 
> most_specific_instrs(Instrs1, MaybeFallThrough1,
> 		Instrs2, MaybeFallThrough2, Instrs, MaybeFallThrough) :-
> 	(
> 		Instrs1 = [Instr1 | Tail1],
> 		Instrs2 = [Instr2 | Tail2]
> 	->
> 		Instr1 = Uinstr1 - Comment1,
> 		Instr2 = Uinstr2 - Comment2,
> 		(
> 			most_specific_instr(Uinstr1, Uinstr2, Uinstr)
> 		->
> 			( Comment1 = Comment2 ->
> 				Comment = Comment1
> 			;
> 				Comment = "unified intruction"
> 			),

Is it worth preserving the original comments as well?

> 
> :- pred most_specific_instr(instr::in, instr::in, instr::out) is semidet.

Like the other predicate Fergus mentioned, we need a good definition
of "most_specific_instr" so people adding llds instructions can attempt
to get it right without asking you to write the code for them ;-).

> :- pred most_specific_rval(rval::in, rval::in, rval::out) is semidet.

Same here.

It would also be good to have a small test case that triggers this
optimization for the test suite.

-- 
       Tyson Dowd           # If I'm unusually agressive in this email, it's
                            # probably because USENET has been down here for
     trd at cs.mu.oz.au        # over a week, and I'm missing my usual dosage
http://www.cs.mu.oz.au/~trd # of flamewars. My apologies in advance.