[m-dev.] for review: cache references to free(alias) variables in the code generator

[David Matthew Overton]

On Wed, Aug 19, 1998 at 04:24:25PM EST, Zoltan Somogyi wrote:
> 
> > Implement caching of references to free variables in the code generator.
> > E.g. after unification 
> > 
> > 	Y = f(X)
> > 
> > if Y is live, we don't need to keep a reference to X, we just need
> > to remember that the X is located in the first field of Y.
> 
> Do you have a test case that shows that this scheme yields better code?

No, not yet.  This is because the only place where partially
instantiated data structures are currently constructed is in the LCO
transformation.  In this case, the references are needed straight away
as arguments for a call so caching doesn't buy you anything.

Caching has been implemented because I think it will help produce
better code in the future when the mode checker is allowed to schedule
partial constructions.  Here's a small example:

	...
	Z = foo(Y),
	Y = bar(X),
	X = 42,
	...

Without caching of references, whenever you do a construction you
create references for all uninstatiated fields.  This would result in
code something like:

	incr_hp(r1, 1);	/* allocate Z */
	r2 = &field(r1, 0);
	incr_hp(r3, 1);	/* allocate Y */
	*r2 = r3;
	r4 = &field(r3, 0);
	*r4 = 42;

However, with caching of references, the code produced would be more
like:

	incr_hp(r1, 1);	/* allocate Z */
	incr_hp(r2, 1);	/* allocate Y */
	field(r1, 0) = r2;
	field(r2, 0) = 42;

Arguably, you could re-order the conjuction in an earlier pass to
remove the need for caching references.  (Peephole optimisation could
also improve the above example a bit.)  However, it was a fairly simple
change to the code generator so I thought it was probably worth
implementing.  It will mean that earlier passes don't need to be quite
so concerned about the order of constructions.

> 
> > +       % code_exprn__uncache_references(Vars, Code, ExprnInfo0, ExprnInfo)
> > +       %       Output Code to produce references to any variables that 
> > +       %       are cached as references to fields of variables in Vars.
> > +       %       Update the references in the ExprnInfo to show that
> > +       %       these references have been evaluated.
> > +:- pred code_exprn__uncache_references(set(var), code_tree,
> > +               exprn_info, exprn_info).
> > +:- mode code_exprn__uncache_references(in, out, in, out) is det.
> 
> What does "Output Code to produce references" mean?

How about: "Output Code to place references in registers for any
variables that ..."

> 
> > +%      Locations where the value needs to be placed.  Each lval in a
> > +%      set(lval) should point to the same place.  The bool is yes if the
> > +%      value is already in this location, otherwise it is no.
> > +:- type var_refs == set(pair(bool, var_ref_stat)).
> 
> I don't know what this means. What lval in what set(lval)?

Sorry, this comment now applies to the `evaled' constructor of
`var_ref_stat' (below).

> 
> Since I don't know the semantics of this key data structure, I can't evaluate
> the correctness of several predicates in the change.
> 
> > +:- type var_ref_stat
> > +	--->	evaled(set(lval))
> > +	;	cached(
> > +			var,	% Var where this reference occurs.
> > +			tag,	% Tag to use for dereferencing Var.
> > +			int	% Field number of reference.
> > +		).
> > +	%;	list(set(rval)).	% AAA  A linked list of references.
> 
> The last line should be deleted or fixed (you don't want `list'
> to be the third alternative in the type).

Actually, I do.  The commented-out line is part of my next change
which is to allow linked lists of references for the case where the
exact number of references to a variable is unknown.   Perhaps a less
confusing constructor name would be better?

> 
> >  code_exprn__filter_out_reg_depending_refs(Refs0, Vars, Refs) :-
> >  	set__to_sorted_list(Refs0, RefList0),
> >  	list__map(lambda([Ref0::in, Ref::out] is det,
> > -		(
> > -			Ref0 = Placed - Lvals0,
> > +		( Ref0 = Placed - evaled(Lvals0),
> >  			set__to_sorted_list(Lvals0, LvalList0),
> >  			list__filter(lambda([Lval::in] is semidet,
> >  				\+ code_exprn__lval_depends_on_reg(Lval, Vars)),
> >  				LvalList0, LvalList),
> >  			set__list_to_set(LvalList, Lvals),
> > -			Ref = Placed - Lvals
> > +			Ref = Placed - evaled(Lvals)
> > +		; Ref0 = _ - cached(_, _, _),
> > +			Ref = Ref0
> >  		)), RefList0, RefList),
> >  	set__list_to_set(RefList, Refs).
> 
> Why is it ok to ignore the possibility that the cached ref is to a variable
> that is stored in an Lval for which \+ lval_depends_on_reg may fail?

References can only be cached to fields of live variables.  At the
point where this predicate is called, all live variables have been
saved on the stack.

[...]
> > @@ -1259,24 +1312,39 @@
> >  	{ map__lookup(Vars0, Var, var_info(Refs0, Stat)) },
> >  
> >  	% Remove an lval from the set and recursively call place_var.
> > -	( { get_next_ref_to_place(Refs0, Lvals, Refs1) } ->
> > -		{ code_exprn__remove_lval_references(Refs1, Lvals, Refs2) },
> > -		{ set__insert(Refs2, yes - Lvals, Refs) },
> > -		{ map__det_update(Vars0, Var, var_info(Refs, Stat), Vars) },
> > +	( { get_next_ref_to_place(Refs0, RefStat, Refs1) } ->
> > +		( { RefStat = evaled(Lvals) },
> > +			{ code_exprn__remove_lval_references(Refs1, Lvals,
> > +				Refs2) },
> > +			{ code_exprn__select_lval(Lvals, Lval) },
> > +			{ Location = mem_ref(lval(Lval)) },
> > +			{ Code0 = empty }
> > +		; { RefStat = cached(LVar, Tag, FieldNum) },
> > +			% There is no need to evaluate the ref, so leave it
> > +			% cached and place the value of Var directly into
> > +			% the cached location.
> > +			code_exprn__produce_var(LVar, Rval, Code0),
> > +			{ Location = field(yes(Tag), Rval,
> > +				const(int_const(FieldNum))) },
> > +			{ Refs2 = Refs1 }
> > +		),
> > +		code_exprn__get_vars(Vars1),
> > +		{ set__insert(Refs2, yes - RefStat, Refs) },
> > +		{ map__det_update(Vars1, Var, var_info(Refs, Stat), Vars) },
> >  		code_exprn__set_vars(Vars),
> > -		{ code_exprn__select_lval(Lvals, Lval) },
> > -		code_exprn__place_var(Var, mem_ref(lval(Lval)), Code)
> > +		code_exprn__place_var(Var, Location, Code1),
> > +		{ Code = tree(Code0, Code1) }
> >  	;
> >  		{ Code = empty }
> >  	).
> 
> I don't understand what this predicate, place_var_in_references, is supposed
> to do. The comment about "no need to evaluate the ref" (what ref?) is followed
> by code that does evaluation, which is especially confusing.

What I mean here is that, e.g., instead of producing:
	r4 = &field(mktag(0), r3, 0);
	*r4 = 42;
You can just do:
	field(mktag(0), r3, 0) = 42;

You don't need to produce an explicit reference to Var, which means
that in exprn_info, the reference to Var can remain as
cached(Lvar, Tag, FieldNum) instead of being changed to evaled(...).

I'll improve the comment here and the comment for the predicate.

> 
> Why is the call to place_var instead of place_var_in_references?

place_var places the variable in the given location and then
recursively calls place_var_in_references for any remaining
references.  This design should probably be simplified -- I'll see
what I can do.

[...]

> > +:- pred code_exprn__uncache_reference(var, var, code_tree,
> > +		exprn_info, exprn_info).
> > +:- mode code_exprn__uncache_reference(in, in, out, in, out) is det.
> > +
> > +code_exprn__uncache_reference(Var, Lvar, Code) -->
> > +	code_exprn__get_vars(VarMap0),
> > +	{ map__lookup(VarMap0, Var, var_info(Refs0, Stat)) },
> > +
> > +	% Removed the cached references from the var_info.
> > +	{ set__to_sorted_list(Refs0, RefsList0) },
> > +	{ list__filter(lambda([RefStat::in] is semidet, 
> > +		RefStat = _ - cached(Lvar, _, _)), RefsList0, CachedRefs,
> > +		RefsList1) },
> > +	{ set__sorted_list_to_set(RefsList1, Refs1) },
> > +	{ map__det_update(VarMap0, Var, var_info(Refs1, Stat), Vars1) },
> > +	code_exprn__set_vars(Vars1),
> > +
> > +	tree__construct(code_exprn__uncache_reference_2(Lvar, Var), CachedRefs,
> > +		Code).
> 
> I don't see how this works.

The cached references of Var that refer to Lvar are removed from the
var_info and then added back in one by one as evaled references.  I'll
improve the comment.

[...]

> 
> > +:- pred code_exprn__uncache_reference_in_lval(var, tag, int, lval,
> > +		code_tree, exprn_info, exprn_info).
> > +:- mode code_exprn__uncache_reference_in_lval(in, in, in, in, out, in, out)
> > +		is det.
> > +
> > +code_exprn__uncache_reference_in_lval(Lvar, Tag, FieldNum, Lval, Code) -->
> > +	code_exprn__produce_var(Lvar, Rval, Code0),
> > +	{ Code1 = node([assign(Lval,
> > +		mem_addr(heap_ref(Rval, Tag, FieldNum))) -
> > +		"place reference"]) },
> > +	{ Code = tree(Code0, Code1) }.
> 
> Can't you hoist produce_var out of the loop driven by tree__construct?

Yes.  I'll do that.

[...]

> 
> >  	% note: we must be careful to apply deaths before births
> >  	{ goal_info_get_post_deaths(GoalInfo, PostDeaths) },
> > +	code_info__uncache_references(PostDeaths, Code),
> >  	code_info__rem_forward_live_vars(PostDeaths),
> >  	code_info__make_vars_forward_dead(PostDeaths),
> >  	{ goal_info_get_post_births(GoalInfo, PostBirths) },
> 
> Why do you uncache references only for post-deaths, and not also for
> pre-deaths in pre_goal_update?

Hmm, I think I probably should.

[...]
> 
> I would like to see another diff.

I'll make these changes and then post one.  Do you want a diff
relative to the current diff or relative to the repository?


David
-- 
David Overton
MEngSc Student                       Email: dmo at cs.mu.oz.au     
Department of Computer Science       Web: http://www.cs.mu.oz.au/~dmo
The University of Melbourne          Phone: +61 3 9344 9159