[m-dev.] for design review: accurate GC for MLDS back-end

[Fergus Henderson]

I've been thinking about doing accurate GC for the MLDS back-end,
and I've sketched out some design documentation.
Here it is... comments welcome.

%-----------------------------------------------------------------------------%
%
% SUMMARY
%
% This module is an MLDS-to-MLDS transformation that transforms the
% MLDS code to add the information needed to do accurate GC
% when compiling to C (or to assembler).
%
% Basically what we do is to put all all local variables that might
% contain pointers in structs, with one struct for each stack frame,
% and chain these structs together.  At GC time, we traverse the chain
% of structs.  This allows us to accurately scan the C stack.
%
%-----------------------------------------------------------------------------%
%
% DETAILED DESCRIPTION
%
% For each function, we generate a struct for that function.
% Each such struct starts with a sub-struct containing a couple of
% fixed fields, which allow the GC to traverse the chain:
%
%	struct <function_name>_pointers {
%		struct MR_StackChain fixed_fields;
%		...
%	};
%
% The fixed fields are as follows:
%
%	struct MR_StackChain {
%		struct MR_StackChain *caller;
%		void (*traverse_frame)(void *this_frame);
%	};
%		
% The prev field holds a link to the entry for this function's caller.
% The traverse_frame field is the address of a function to
% trace everything pointed to by this stack frame.
%
% To ensure that we don't try to traverse uninitialized fields,
% we zero-initialize each struct before inserting it into the chain.
%
% Each function gets an extra parameter `stack_chain' which
% points to the caller's struct.
%
% As an optimization, we don't bother allocating a struct for
% functions that don't have any variables that might contain pointers.
% We also don't bother allocating a struct for leaf functions that
% don't contain any functions calls or memory allocations.
% (XXX These optimizations are not yet implemented.)
%
%-----------------------------------------------------------------------------%
%
% EXAMPLE
%
% If we have a function
%
%	RetType
%	foo(Arg1Type arg1, Arg2Type arg2, ...)
%	{
%		Local1Type local1;
%		Local1Type local2;
%		...
%		local1 = MR_new_object(...);
%		...
%		bar(arg1, arg2, local1, &local2);
%		...
%	}
%
% where say Arg1Type and Local1Type are types that might contain pointers,
% but Arg2Type and Local2Type won't, then we would transform it as follows:
%
%	struct foo_frame {
%		MR_StackChain fixed_fields;
%		Arg1Type arg1;
%		Local1Type arg1;
%		...
%	};
%
%	static void
%	foo_traverse_frame(void *this_frame) {
%		struct foo_frame *frame = (struct foo_frame *)this_frame;
%		MR_GC_TRAVERSE(<type_info for type of arg1>, &frame->arg1);
%		MR_GC_TRAVERSE(<type_info for type of local1>, &frame->local1);
%		...
%	}
%
%	RetType
%	foo(struct MR_StackChain *stack_chain,
%		Arg1Type arg1, Arg2Type arg2, ...)
%	{
%		struct foo_frame this_frame;
%		Local1Type local2;
%		
%		/* copy any pointer arguments into the struct */
%		this_frame.fixed_fields.arg1 = arg1;
%		/* zero-initialize any local variables*/
%		this_frame.fixed_fields.local1 = 0;
%		this_frame.fixed_fields.prev = stack_chain;
%		this_frame.fixed_fields.traverse_frame = foo_traverse_frame;
%
%		...
%		local1 = MR_new_object(&this_frame, ...);
%		...
%		bar(&this_frame, this_frame.arg1, arg2,
%			this_frame.local1, &local2);
%		...
%	}
%
% The code in the Mercury runtime to traverse the stack frames would
% then look something like this:
%
%	void MR_traverse_stack(struct MR_StackChain *stack_chain) {
%		struct MR_StackChain *frame;
%		for (frame = stack_chain; frame != NULL; frame = frame->prev) {
%			(*frame->traverse_frame)(frame);
%		}
%	}
%

One difficulty with this design that I've spotted so far is that computing
type_infos may be difficult in an MLDS->MLDS transformation.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  | "... it seems to me that 15 years of
The University of Melbourne         | email is plenty for one lifetime."
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- Prof. Donald E. Knuth
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------