[m-rev.] for review: first step towards MLDS->C accurate GC

[Fergus Henderson]

On 27-Nov-2001, Peter Ross <peter.ross at miscrit.be> wrote:
> On Tue, Nov 27, 2001 at 12:14:39AM +1100, Fergus Henderson wrote:
> > Preliminary steps towards support for accurate GC
> > in the MLDS->C back-end.
...
> > +% We need to keep a link to the topmost frame on the stack.
> > +% There's two possible ways that we could handle this.
> > +% One way is to pass it down as an parameter.
> > +% Each function would get an extra parameter `stack_chain' which
> > +% points to the caller's struct.
> > +% An alternative approach is to just have a global variable
> > +% `stack_chain' that points to the top of the stack.  We need extra code
> > +% to set this pointer when entering and returning from functions.
> > +% To make this approach thread-safe, the variable would actually
> > +% need to be thread-local rather than global.
> > +% This approach would probably work best if the variable is
> > +% a GNU C global register variable, which would make it both
> > +% efficient and thread-safe.
> > +% XXX Currently, for simplicity, we're using a global variable.
> > +%
> 
> I assume that there are no problems with exceptions.  I can't think of
> any but I am just making sure that you have thought about it.

Well, the exception handling code will need to be modified to manipulate
the stack_chain appropriately.  If `stack_chain' is a global variable,
`builtin_catch' needs to save it in a local variable before the call
to setjmp() and restore it after the longjmp(),
i.e. after setjmp() returns a non-zero value.
If it's a parameter, then `builtin_catch' needs to pass that
parameter down to the called Mercury procedures.

In general, lots of the C code in the Mercury standard library
implementation will need changing to support accurate GC. 
Anything which allocates heap or which calls Mercury code that might
allocate heap may need to be modified to ensure that any local
pointers get registered with the garbage collector.

I'm not planning to fix that just yet...

> Here you call this foo_frame but according to the previous naming scheme
> it is foo_pointers.

Fixed by s/foo_pointers/foo_frame/

> > +%	static void
> > +%	foo_traverse_frame(void *this_frame) {
> > +%		struct foo_frame *frame = (struct foo_frame *)this_frame;
> > +%		MR_GC_TRAVERSE(<TypeInfo for type of arg1>, &frame->arg1);
> > +%		MR_GC_TRAVERSE(<TypeInfo for type of local1>, &frame->local1);
> > +%		...
> > +%	}
> > +%
> > +%	RetType
> > +%	foo(Arg1Type arg1, Arg2Type arg2, ...)
> > +%	{
> > +%		struct foo_frame this_frame;
> > +%		Local1Type local2;
> > +%		
> > +%		this_frame.fixed_fields.prev = stack_chain;
> > +%		this_frame.fixed_fields.traverse_frame = foo_traverse_frame;
> > +%		this_frame.fixed_fields.arg1 = arg1;
> > +%		stack_chain = &this_frame;
> > +%
> > +%		...
> > +%		local1 = MR_new_object(...);
> > +%		...
> > +%		bar(this_frame.arg1, arg2, this_frame.local1, &local2);
> > +%		...
> > +%		stack_chain = stack_chain->prev;
> > +%	}
> > +%
> 
> Shouldn't there be a this_frame.local1 = NULL;

Yes.

Actually the code I'm currently generating looks like this:

	{
		struct foo_frame this_frame = { stack_chain };
		Local1Type local2;
		
		this_frame.fixed_fields.arg1 = arg1;
		stack_chain = &this_frame;

		...

Using an initializer like this implicitly zeros out all the
remaining fields.  I'll add some documentation to make this
clearer.

> and you have forgotten the this_frame qualifier for the result of the
> MR_new_object.

Fixed, thanks.

> >  				%
> >  				% If the function's arguments are
> > -				% referenced by nested functions, then
> > -				% we need to copy them to local
> > +				% referenced by nested functions,
> > +				% or (for accurate GC) may contain pointers,
> > +				% then we need to copy them to local
> >  				% variables in the environment
> >  				% structure.
> >  				%
> >  				ml_maybe_copy_args(Arguments, FuncBody0,
> > -					ModuleName, EnvTypeName, EnvPtrTypeName,
> > +					ElimInfo, EnvTypeName, EnvPtrTypeName,
> >  					Context, _ArgsToCopy, CodeToCopyArgs),
> >  
> 
> Will this code have problems because it is possibly executed twice?
> This could happen on the hoist_nested_funcs pass when InsertedEnv = yes
> and then it will always get called on the chain_gc_stack_frames pass.
> 
> Speaking of which does it matter what order you call these passes in?

Either way should work, I think, but the generated code would be different
in each case.

> Wait I think I can see what happens, but you say that for both passes you
> "need to copy them to local variables in the environment structure".
> However this `environment structure' is different for each pass, on one pass
> it is the environment structure and on the other pass the stack frame.

Right.

> I think you need to make this point more clear and you probably need to
> rename variables to reflect that there is more than one possible
> `environment structure'.

Talking about the "environment or frame struct" everywhere would be
rather awkward, I think, so I have just added the following comment to
the top of the file:

% The word "environment" (as in "environment struct" or "environment pointer")
% is used to refer to both the environment structs used when eliminating
% nested functions and also to the frame structs used for accurate GC.

> >  	%
> >  	% generate the following type:
> >  	%
> >  	%	struct <EnvClassName> {
> > +	%	  #ifdef ACCURATE_GC
> > +	%		struct MR_StackChain fixed_fields;
> > +	%	  #endif
> >  	%		<LocalVars>
> >  	%	};
> >  	%
> 
> A quick comment that the #ifdef is a virtual preprocessor statement in
> that the compiler does it.

You are correct, but I think this is sufficiently clear as is.
It's easy to see from reading the code that the compiler does it.
(After all, you worked it out, didn't you? ;-)

This idiom is used in comments through-out the MLDS back-end,
so if I change it here then there are another 16 places
where the same comment should also be added.

When I first started writing such comments, I thought about
adding a comment to explain the idiom.  For example,
I could add something like the following

%	/*
%	** This is a "virtual" preprocessor statement,
%	** i.e. it's handled by the Mercury compiler
%	** rather than the C compiler.
%	*/

before each such #ifdef.

However, such explanations obscure the pseudo-code that is the main
point of the comment, so I thought it was clearer to just leave them out.
The reader will soon realize what is going on.

> > +		Fields = [PrevFieldDecl, TraceFieldDecl | Fields0],
>
> Here you don't actually create a MR_StackChain structure but instead
> add the two fields of this structure to the current structure.  I would
> update the comments about the generated code to reflect this.

Good point.  I wrote the comments, describing the code I wanted to
generate, and then when I wrote the code to generate it, I took
a few short-cuts, but I failed to go back and update the comments.

> > +		%
> > +		% Set the initializer for the `prev' field
> > +		% to the global stack chain
> > +		% XXX we want to zero out the rest of the environment struct;
> > +		%     will just not mentioning the remaining fields work?
> > +		%
> > +		StackChain = ml_stack_chain_var,
> > +		EnvInitializer = init_struct([init_obj(lval(StackChain))]),
>
> Does this work?

Yes.

> I think if you want to explicitly zero it out, then you
> need to do that, after all we can't assume anything about the backend.
> I just checked the C backend and it doesn't do anything explicitly.

That's OK, the C compiler will do it.

For back-ends other than C, yes, we should explicitly zero it out.
However, this kind of accurate GC is not useful for the .NET or Java
back-ends, which already have their own GC.
Right now I'm only interested in getting it to work on the MLDS->C
back-end, and in particular with GNU C.

I've elaborated lots in the comments.

> > +ml_env_name(function(PredLabel, ProcId, MaybeSeqNum, _PredId),
> > +		Action) = ClassName :-
> > +	Base = (if Action = chain_gc_stack_frames then "locals" else "env"),
> 
> Ok you have called it pointers, frame and now locals.  Which one do you
> want it to be?

As you can see I've vacillated a bit on this one,
but I'm going to go with "frame" ;-)

> > @@ -913,10 +1209,26 @@
> >  
> >  	%
> >  	% Succeed iff we should add the definition of this variable
> > -	% to the local_data field of the ml_elim_info, meaning that
> > +	% to the local_data field of the elim_info, meaning that
> >  	% it should be added to the environment struct
> >  	% (if it's a variable) or hoisted out to the top level
> >  	% (if it's a static const).
> 
> This comment should also explain what you do when you are chaining stack
> frames

Given the earlier definition of "environment struct" to include the frame
structs used for accurate GC, the comment there is entirely correct for
that case.

> > +	% Note that with --gcc-nested-functions,
> > +	% cont_type will be a function pointer that
> > +	% may point to a trampoline function,
> > +	% which might in fact contain pointers.
> > +	% But in that case we can't trace them,
> > +	% so that combination of options isn't supported.
> > +	% XXX we should add code to handle_options to check it.
> > +	% Hence we can return `no' here for mlds__cont_type.
> 
> Add the code to handle_options.

Actually on further reflection, I realize that it doesn't
matter if we can't trace them.  I've changed the comment
to the following:

	...
	% But the pointers will only be pointers to
	% code and pointers to the stack, not pointers
	% to the heap, so we don't need to trace them
	% for accurate GC.
	% Hence we can return `no' here for mlds__cont_type.

> > +** XXX Using a global variable for this is not thread-safe.
> > +**     We should probably use a GNU C global register variable.
> > +*/
> > +extern void *mercury__private_builtin__stack_chain;
> >  
> 
> I suggest changing this code so that if someone attempts to do this the
> problem will be quickly found, and then they can correct it.
> 
> #ifdef ACCURATE_GC
>   #ifdef MR_THREAD_SAFE
>     #error "NYI"
>   #else
>     extern void *mercury__private_builtin__stack_chain;
>   #endif
> #endif

Good idea -- I'll do that.

Here's a relative diff.

diff -u compiler/ml_elim_nested.m compiler/ml_elim_nested.m
--- compiler/ml_elim_nested.m
+++ compiler/ml_elim_nested.m
@@ -18,6 +18,10 @@
 % so they're both handled by the same code;
 % a flag is passed to say which transformation
 % should be done.
+%
+% The word "environment" (as in "environment struct" or "environment pointer")
+% is used to refer to both the environment structs used when eliminating
+% nested functions and also to the frame structs used for accurate GC.
 
 % XXX Would it be possible to do both in a single pass?
 
@@ -145,6 +149,10 @@
 % and chain these structs together.  At GC time, we traverse the chain
 % of structs.  This allows us to accurately scan the C stack.
 %
+% XXX Currently the only part which is implemented is the code to chain
+%     the stack frames together; we don't yet generate the code to
+%     traverse the stack frames.  Doing that here is tricky...
+%
 %-----------------------------------------------------------------------------%
 %
 % DETAILED DESCRIPTION
@@ -153,7 +161,7 @@
 % 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 <function_name>_frame {
 %		struct MR_StackChain fixed_fields;
 %		...
 %	};
@@ -165,6 +173,10 @@
 %		void (*traverse_frame)(void *this_frame);
 %	};
 %		
+% XXX Currently, rather than using a nested structure,
+% we just put these fields directly in the <function_name>_frame struct.
+% (This turned out to be a little easier.)
+%
 % 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.
@@ -217,10 +229,14 @@
 %	struct foo_frame {
 %		MR_StackChain fixed_fields;
 %		Arg1Type arg1;
-%		Local1Type arg1;
+%		Local1Type local1;
 %		...
 %	};
 %
+%	/*
+%	** XXX Generation of the *_traverse_frame() functions is
+%	**     not yet implemented.
+%	*/
 %	static void
 %	foo_traverse_frame(void *this_frame) {
 %		struct foo_frame *frame = (struct foo_frame *)this_frame;
@@ -237,11 +253,12 @@
 %		
 %		this_frame.fixed_fields.prev = stack_chain;
 %		this_frame.fixed_fields.traverse_frame = foo_traverse_frame;
-%		this_frame.fixed_fields.arg1 = arg1;
+%		this_frame.arg1 = arg1;
+%		this_frame.local1 = NULL;
 %		stack_chain = &this_frame;
 %
 %		...
-%		local1 = MR_new_object(...);
+%		this_frame.local1 = MR_new_object(...);
 %		...
 %		bar(this_frame.arg1, arg2, this_frame.local1, &local2);
 %		...
@@ -261,10 +278,11 @@
 %		
 %		this_frame.fixed_fields.prev = stack_chain;
 %		this_frame.fixed_fields.traverse_frame = foo_traverse_frame;
-%		this_frame.fixed_fields.arg1 = arg1;
+%		this_frame.arg1 = arg1;
+%		this_frame.local1 = NULL;
 %
 %		...
-%		local1 = MR_new_object(&this_frame, ...);
+%		this_frame.local1 = MR_new_object(&this_frame, ...);
 %		...
 %		bar(&this_frame, this_frame.arg1, arg2,
 %			this_frame.local1, &local2);
@@ -272,6 +290,17 @@
 %		/* no need to explicitly unchain the stack frame here */
 %	}
 %
+% Currently, rather than initializing the fields of `this_frame'
+% using a sequence of assignment statements, we actually just use
+% an initializer:
+%		struct foo_frame this_frame = { stack_chain };
+% This implicitly zeros out the remaining fields.
+% Only the non-null fields, i.e. the arguments and the traverse_frame
+% field, need to be explicitly assigned using assignment statements.
+% XXX Currently we leave the traverse_frame field as null,
+% since the code to generate the *_traverse_frame functions is
+% not yet implemented.
+%
 % The code in the Mercury runtime to traverse the stack frames would
 % look something like this:
 %
@@ -656,9 +685,17 @@
 
 		%
 		% Set the initializer for the `prev' field
-		% to the global stack chain
-		% XXX we want to zero out the rest of the environment struct;
-		%     will just not mentioning the remaining fields work?
+		% to the global stack chain.
+		%
+		% Since there no values for the remaining fields in the
+		% initializer, this means the remaining fields will get
+		% initialized to zero (C99 6.7.8 #21).
+		%
+		% XXX This uses a non-const initializer, which is a
+		% feature that is only supported in C99 and GNU C;
+		% it won't work in C89.  We should just generate
+		% a bunch of assignments to all the fields,
+		% rather than relying on initializers like this.
 		%
 		StackChain = ml_stack_chain_var,
 		EnvInitializer = init_struct([init_obj(lval(StackChain))]),
@@ -1281,9 +1318,10 @@
 	% cont_type will be a function pointer that
 	% may point to a trampoline function,
 	% which might in fact contain pointers.
-	% But in that case we can't trace them,
-	% so that combination of options isn't supported.
-	% XXX we should add code to handle_options to check it.
+	% But the pointers will only be pointers to
+	% code and pointers to the stack, not pointers
+	% to the heap, so we don't need to trace them
+	% for accurate GC.
 	% Hence we can return `no' here for mlds__cont_type.
 
 :- func ml_type_might_contain_pointers(mlds__type) = bool.
diff -u runtime/mercury.c runtime/mercury.c
--- runtime/mercury.c
+++ runtime/mercury.c
@@ -26,7 +26,9 @@
 ** Variable definitions
 */
 
-void *mercury__private_builtin____stack_chain;
+#ifdef ACCURATE_GC
+  void *mercury__private_builtin____stack_chain;
+#endif
 
 MR_Word mercury__private_builtin__dummy_var;
 
diff -u runtime/mercury.h runtime/mercury.h
--- runtime/mercury.h
+++ runtime/mercury.h
@@ -284,12 +284,17 @@
 ** Declarations of contants and variables
 */
 
-/*
-** This points to the start of the MR_StackChain frame list.
-** XXX Using a global variable for this is not thread-safe.
-**     We should probably use a GNU C global register variable.
-*/
-extern void *mercury__private_builtin__stack_chain;
+#ifdef ACCURATE_GC
+  /*
+  ** This points to the start of the MR_StackChain frame list.
+  ** XXX Using a global variable for this is not thread-safe.
+  **     We should probably use a GNU C global register variable.
+  */
+  #ifdef MR_THREAD_SAFE
+    #error "Sorry, not supported: --high-level-code --gc accurate --thread-safe"
+  #endif
+  extern void *mercury__private_builtin__stack_chain;
+#endif
 
 /* declare MR_TypeCtorInfo_Structs for the builtin types */
 extern const MR_TypeCtorInfo_Struct

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