[m-dev.] for review: MLDS backend to do structure reuse and compile time gc

[Fergus Henderson]

On 05-Oct-2000, Peter Ross <Peter.Ross at cs.kuleuven.ac.be> wrote:
> Update the MLDS backend to handle structure reuse and compile time gc.
> Note that currently no pass on the main branch currently generates this
> information yet.
...
> mlds.m:
>     Update the assign instruction with a field that says whether or not
>     the LHS of the assigment needs to use a different tag to the RHS of
>     the assignment and what that tag is.

Why not just use different rvals, rather than different forms of
the `assign' instruction?

I think it would be much better to just generate an MLDS instruction
of the form

	assign(Lval, mkword(ml_gen_mktag(NewTag),
		binop(body, Rval, ml_gen_mktag(OldTag))))

where ml_gen_mktag/1 is defined by

	:- func ml_gen_mktag(int) = rval.
	ml_gen_mktag(Tag) = unary_op(mktag, const(int_const(Tag)).

This will also be more efficient than using MR_strip_tag,
and shouldn't be a problem, since you know what the old tag
is from the cons_id in the reuse_cell/3 constructor.
Alternatively, if for some reason you need to use strip_tag,
then you can add that as a new unary_op.

There is one problem with using `body' -- currently there is a bug in
builtin_ops.m, "body" should be a binop but currently it is listed as
a unary op.  But that should be fairly easily fixed.

Anyway, this approach of using rvals keeps the MLDS data structure
simpler, which keeps the code that traverses it simpler.

> mlds_to_c.m:
>     Handle the new form of the assign instruction.
>     Throw an error if we encounter an compile_time_gc instruction.
>     
> ml_code_util.m:
>     Add ml_gen_assign_with_tag which generates an assign instruction
>     where the lval must use the supplied tag.
> 
> ml_elim_nested.m:
> ml_optimize.m:
>     Handle the new field maybe(mlds__tag) for assign operations in the
>     MLDS.

These changes should all be unnecessary.

> +++ hlds_goal.m	2000/10/05 14:16:03
> @@ -411,6 +411,9 @@
>  	;	modes_are_ok
>  	.
>  
> +	% The cell is available for compile time garbage collected.
> +:- type can_cgc == bool.

s/The/`yes' iff the/
s/collected/collection/

This would be a good point to put a comment explaining what 
compile time garbage collection means.

>  :- type unification
>  		% A construction unification is a unification with a functor
>  		% or lambda expression which binds the LHS variable,
> @@ -477,8 +480,9 @@
>  					% e.g. [X] in the above example.
>  			list(uni_mode), % The lists of modes of the argument
>  					% sub-unifications.
> -			can_fail	% Whether or not the unification
> +			can_fail,	% Whether or not the unification
>  					% could possibly fail.
> +			can_cgc		% Can compile time GC this cell
>  		)

I suggest you append "after the deconstruction" at the end of that
comment, e.g.

			can_cgc		% Can compile time GC this cell,
					% i.e. explicitly deallocate it
					% after the deconstruction.

>  		% Y = X where the top node of Y is output,
> Index: hlds_out.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/hlds_out.m,v
> retrieving revision 1.245
> diff -u -r1.245 hlds_out.m
> --- hlds_out.m	2000/09/25 04:22:34	1.245
> +++ hlds_out.m	2000/10/05 14:16:03
> @@ -1497,7 +1497,8 @@
>  	hlds_out__write_unify_rhs_2(B, ModuleInfo, VarSet, InstVarSet,
>  		AppendVarnums, Indent, Follow, VarType, TypeQual),
>  	globals__io_lookup_string_option(dump_hlds_options, Verbose),
> -	( { string__contains_char(Verbose, 'u') } ->
> +	( { string__contains_char(Verbose, 'u') 
> +			; string__contains_char(Verbose, 'p') } ->

Fix the layout.

This change wasn't mentioned in the log message.

> +++ ml_unify_gen.m	2000/10/05 14:16:05
...
> -ml_gen_unification(deconstruct(Var, ConsId, Args, ArgModes, CanFail),
> +
> +ml_gen_unification(deconstruct(Var, ConsId, Args, ArgModes, CanFail, CanCGC),
>  		CodeModel, Context, MLDS_Decls, MLDS_Statements) -->
>  	(
>  		{ CanFail = can_fail },
>  		{ require(unify(CodeModel, model_semi),
>  			"ml_code_gen: can_fail deconstruct not semidet") },
>  		ml_gen_semi_deconstruct(Var, ConsId, Args, ArgModes, Context,
> -			MLDS_Decls, MLDS_Statements)
> +			MLDS_Decls, MLDS_Unif_Statements)
>  	;
>  		{ CanFail = cannot_fail },
>  		{ require(unify(CodeModel, model_det),
>  			"ml_code_gen: cannot_fail deconstruct not det") },
>  		ml_gen_det_deconstruct(Var, ConsId, Args, ArgModes, Context,
> -			MLDS_Decls, MLDS_Statements)
> -	).
> +			MLDS_Decls, MLDS_Unif_Statements)
> +	),
> +	(
> +		{ CanCGC = yes },
> +		ml_gen_var(Var, VarLval),
> +		{ MLDS_Stmt = atomic(compile_time_gc(VarLval)) },
> +		{ MLDS_CGC_Statements = [mlds__statement(MLDS_Stmt,
> +				mlds__make_context(Context)) ] }
> +	;
> +		{ CanCGC = no },
> +		{ MLDS_CGC_Statements = [] }
> +	),
> +	{ MLDS_Statements = MLDS_Unif_Statements `list__append`
> +			MLDS_CGC_Statements }.

The generated code here might be wrong in the case where the
unification can fail, because you deallocate the node even if the
unification fails.

At very least you should have some comments explaining why that
is correct, if it is.

> +++ mlds.m	2000/10/05 14:16:06
> @@ -821,14 +821,19 @@
>  	--->	comment(string)
>  			% Insert a comment into the output code.
>  
> -	;	assign(mlds__lval, mlds__rval)
> -			% assign(Location, Value):
> +	;	assign(mlds__lval, mlds__rval, maybe(mlds__tag))
> +			% assign(Location, Value, MaybeTag):
>  			% Assign the value specified by rval to the location
> -			% specified by lval.
> +			% specified by lval.  Possibly changing the tag
> +			% on the lval, if required.

As discussed above, I don't think this change is a good idea.

>  	%
>  	% heap management
>  	%
> +
> +	;	compile_time_gc(mlds__lval)
> +			% Compile time garbage collect the memory used
> +			% by the lval.

I suggest you add "(i.e. explicitly deallocate)" after
"compile time garbage collect".

It would probably be better to name this instruction `delete_object',
to match `new_object'.  That's about the right level of abstraction
for the MLDS, which is supposed to be a representation of an abstract
OOP language.  I know of a couple of OOP languages which have `delete',
but none which have `compile_time_gc' ;-)

Note that this is different for the MLDS than for the LLDS.
For the LLDS, we have made plenty of use of conditional compilation,
and have been happy to introduce new constructs that macro-expand to
different things depending on the setting of various configuartion
macros.  So for the LLDS it would be fine to introduce a new instruction
called `compile_time_gc', and for that emit a call to the
`MR_compile_time_GC()' macro.  But for the MLDS, I want the generated
code to be as human-readable as possible, which suggests avoiding
macros; also we want to be able to compile to languages like Java
that don't have macros.  So for the MLDS it's better to make these
decisions at MLDS generation time, rather than at MLDS->target code
conversion or at the target language's macro-expansion time.

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