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

[Peter Ross]

On Tue, Nov 27, 2001 at 12:14:39AM +1100, Fergus Henderson wrote:
> Branches: main
> Estimated hours taken: 16
> 
> Preliminary steps towards support for accurate GC
> in the MLDS->C back-end.
> 
> compiler/ml_elim_nested.m:
> 	Add support for a new pass that puts local
> 	variables that might contain pointers into
> 	a struct, and chains these structs together.
> 	
> compiler/mercury_compile.m:
> 	Invoke the new pass (if `--gc accurate').
> 
> runtime/mercury.h:
> runtime/mercury.c:
> 	Declare the `stack_chain' global variable that
> 	points to the head of the chain.
> 
> Workspace: /home/earth/fjh/ws-earth3/mercury
> Index: compiler/ml_elim_nested.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/ml_elim_nested.m,v
> retrieving revision 1.43
> diff -u -d -r1.43 ml_elim_nested.m
> --- compiler/ml_elim_nested.m	24 Oct 2001 05:44:01 -0000	1.43
> +++ compiler/ml_elim_nested.m	26 Nov 2001 13:03:53 -0000
> @@ -8,7 +8,24 @@
>  % Main author: fjh
>  
>  % This module is an MLDS-to-MLDS transformation
> -% that eliminates nested functions.
> +% that has two functions:
> +% (1) eliminating nested functions
> +% (2) putting local variables that might contain pointers into
> +%     structs, and chaining these structs together,
> +%     for use with accurate garbage collection.
> +%
> +% The two transformations are quite similar,
> +% so they're both handled by the same code;
> +% a flag is passed to say which transformation
> +% should be done.
> +
> +% XXX Would it be possible to do both in a single pass?
> +
> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +% (1) eliminating nested functions
> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
>  
>  % Note that this module does not attempt to handle arbitrary MLDS
>  % as input; it will only work with the output of the current MLDS
> @@ -112,6 +129,163 @@
>  % ml_code_gen puts in calls to the nested functions.
>  
>  %-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +% (2) accurate GC
> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +%
> +% SUMMARY
> +%
> +% This 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 *prev;
> +%		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.
> +%
> +% 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.


> +% As an optimization, we ought to not bother allocating a struct for
> +% functions that don't have any variables that might contain pointers.
> +% We also ought to not 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 might contain pointers,
> +% but Arg2Type and Local2Type don't, then we would transform it as follows:
> +%
> +%	struct foo_frame {
> +%		MR_StackChain fixed_fields;
> +%		Arg1Type arg1;
> +%		Local1Type arg1;
> +%		...
> +%	};
> +%
Here you call this foo_frame but according to the previous naming scheme
it is foo_pointers.

> +%	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;
and you have forgotten the this_frame qualifier for the result of the
MR_new_object.

> +% Alternatively, if we were passing stack_chain as an argument,
> +% rather than treating it as a global variable, then the generated
> +% code for foo() would look like this:
> +%
> +%	RetType
> +%	foo(struct MR_StackChain *stack_chain,
> +%		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;
> +%
> +%		...
> +%		local1 = MR_new_object(&this_frame, ...);
> +%		...
> +%		bar(&this_frame, this_frame.arg1, arg2,
> +%			this_frame.local1, &local2);
> +%		...
> +%		/* no need to explicitly unchain the stack frame here */
> +%	}
> +%
Same problems.

> +% The code in the Mercury runtime to traverse the stack frames would
> +% look something like this:
> +%
> +%	void
> +%	MR_traverse_stack(struct MR_StackChain *stack_chain)
> +%	{
> +%		while (stack_chain != NULL) {
> +%			(*stack_chain->traverse)(stack_chain);
> +%			stack_chain = stack_chain->prev;
> +%		}
> +%	}
> +%

> @@ -238,47 +433,85 @@
>  			% really a big problem, since the code
>  			% that generates these arguments needs them.
>  			%
> -			( InsertedEnv = yes ->
> +			(
> +				Action = hoist_nested_funcs,
> +				InsertedEnv = no
> +			->
> +				FuncBody = FuncBody1,
> +				HoistedDefns = HoistedDefns0
> +			;
>  				%
>  				% 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?

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.

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

>  				%
> +				% Insert code to unlink this stack frame
> +				% before doing any tail calls or returning
> +				% from the function, either explicitly
> +				% or implicitly.
> +				%
> +					% add unlink statements before
> +					% any explicit returns or tail calls
> +				( Action = chain_gc_stack_frames ->
> +					add_unchain_stack_to_statement(
> +						FuncBody1, FuncBody2,
> +						ElimInfo, _ElimInfo)
> +				;
> +					FuncBody2 = FuncBody1
> +				),
> +					% add a final unlink statement
> +					% at the end of the function,
> +					% if needed.  This is only needed if
> +					% the function has no return values --
> +					% if there is a return value, then the
> +					% function must exit with an explicit
> +					% return statement.
> +				(
> +					Action = chain_gc_stack_frames,
> +					RetValues = []
> +				->
> +					UnchainFrame = [ml_gen_unchain_frame(
> +						Context, ElimInfo)]
> +				;
> +					UnchainFrame = []
> +				),
> +
> +				%
>  				% insert the definition and
>  				% initialization of the environment
>  				% struct variable at the start of the
> -				% top-level function's body
> +				% top-level function's body,
> +				% and append the final unlink statement
> +				% (if any) at the end
>  				%
>  				FuncBody = ml_block(EnvDecls,
> -					list__append(
> -						[InitEnv | CodeToCopyArgs], 
> -						[FuncBody1]), Context),
> +						InitEnv ++ CodeToCopyArgs ++
> +						[FuncBody2] ++ UnchainFrame,
> +						Context),
>  				%
> -				% insert the environment struct type
> -				% at the start of the list of hoisted definitions
> +				% insert the environment struct type at
> +				% the start of the list of hoisted definitions
>  				% (preceding the previously nested functions
>  				% and static constants in HoistedDefns0),
>  				%
>  				HoistedDefns = [EnvTypeDefn | HoistedDefns0]
> -			;
> -				FuncBody = FuncBody1,
> -				HoistedDefns = HoistedDefns0
>  			)
>  		),
>  		DefnBody = mlds__function(PredProcId, Params,
>  			defined_here(FuncBody), Attributes),
>  		Defn = mlds__defn(Name, Context, Flags, DefnBody),
> -		FlatDefns = list__append(HoistedDefns, [Defn])
> +		Defns = list__append(HoistedDefns, [Defn])
>  	;
>  		% leave definitions of things other than functions unchanged
> -		FlatDefns = [Defn0]
> +		Defns = [Defn0]
>  	).
>  
>  	%

> @@ -361,17 +598,20 @@
>  	%	struct <EnvClassName> *env_ptr;
>  	%	env_ptr = &env;
>  	%
> -:- pred ml_create_env(mlds__class_name, list(mlds__defn), mlds__context,
> +:- pred ml_create_env(action, mlds__class_name, list(mlds__defn), mlds__context,
>  		mlds_module_name, globals, mlds__defn, mlds__type,
> -		list(mlds__defn), mlds__statement).
> -:- mode ml_create_env(in, in, in, in, in, out, out, out, out) is det.
> +		list(mlds__defn), list(mlds__statement)).
> +:- mode ml_create_env(in, in, in, in, in, in, out, out, out, out) is det.
>  
> -ml_create_env(EnvClassName, LocalVars, Context, ModuleName, Globals,
> +ml_create_env(Action, EnvClassName, LocalVars, Context, ModuleName, Globals,
>  		EnvTypeDefn, EnvTypeName, EnvDecls, InitEnv) :-
>  	%
>  	% 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.

> @@ -390,7 +630,57 @@
>  		EnvTypeKind),
>  	EnvTypeEntityName = type(EnvClassName, 0),
>  	EnvTypeFlags = env_type_decl_flags,
> -	Fields = list__map(convert_local_to_field, LocalVars),
> +	Fields0 = list__map(convert_local_to_field, LocalVars),
> +
> +	( Action = chain_gc_stack_frames ->
> +		%
> +		% insert the fixed fields:
> +		%	void *prev;
> +		%	void (*trace)(...);
> +		%
> +		PrevFieldName = data(var(var_name("prev", no))),
> +		PrevFieldFlags = ml_gen_public_field_decl_flags,
> +		PrevFieldType = mlds__generic_env_ptr_type,
> +		PrevFieldDefnBody = mlds__data(PrevFieldType, no_initializer),
> +		PrevFieldDecl = mlds__defn(PrevFieldName, Context,
> +				PrevFieldFlags, PrevFieldDefnBody),
> +
> +		TraceFieldName = data(var(var_name("trace", no))),
> +		TraceFieldFlags = ml_gen_public_field_decl_flags,
> +		TraceFieldType = mlds__generic_type, % XXX
> +		TraceFieldDefnBody = mlds__data(TraceFieldType, no_initializer),
> +		TraceFieldDecl = mlds__defn(TraceFieldName, Context,
> +				TraceFieldFlags, TraceFieldDefnBody),
> +
> +		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.

> +		%
> +		% 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?  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.

> +		%
> +		% Generate code to set the global stack chain
> +		% to point to the current environment.
> +		%	 stack_chain = env_ptr;
> +		%
> +		EnvPtrTypeName = ml_make_env_ptr_type(Globals, EnvTypeName),
> +		EnvPtr = lval(var(qual(ModuleName,
> +				mlds__var_name("env_ptr", no)),
> +			EnvPtrTypeName)),
> +		AssignToStackChain = assign(StackChain, EnvPtr),
> +		LinkStackChain = [mlds__statement(atomic(AssignToStackChain),
> +			Context)]
> +	;
> +		Fields = Fields0,
> +		EnvInitializer = no_initializer,
> +		LinkStackChain = []
> +	),
> +
>  	Imports = [],
>  	Ctors = [], % mlds_to_il.m will add an empty constructor if needed
>  	Interfaces = [],
> @@ -623,25 +916,27 @@
>  
>  	% Compute the name to use for the environment struct
>  	% for the specified function.
> -:- func ml_env_name(mlds__entity_name) = mlds__class_name.
> +:- func ml_env_name(mlds__entity_name, action) = mlds__class_name.
>  
> -ml_env_name(type(_, _)) = _ :-
> +ml_env_name(type(_, _), _) = _ :-
>  	error("ml_env_name: expected function, got type").
> -ml_env_name(data(_)) = _ :-
> +ml_env_name(data(_), _) = _ :-
>  	error("ml_env_name: expected function, got data").
> -ml_env_name(function(PredLabel, ProcId, MaybeSeqNum, _PredId)) = ClassName :-
> +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?

> @@ -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, ie add local_data which might contain a pointer.

> +:- pred ml_should_add_local_data(elim_info, mlds__var_name, mlds__type,
> +		mlds__defns, mlds__statements).
> +:- mode ml_should_add_local_data(in, in, in, in, in) is semidet.
> +
> +ml_should_add_local_data(ElimInfo, VarName, Type,
> +		FollowingDefns, FollowingStatements) :-
> +	Action = ElimInfo ^ action,
> +	(
> +		Action = chain_gc_stack_frames,
> +		ml_type_might_contain_pointers(Type) = yes
> +	;
> +		Action = hoist_nested_funcs,
> +		ml_need_to_hoist(ElimInfo ^ module_name, VarName,
> +			FollowingDefns, FollowingStatements)
> +	).
> +
>  	%
>  	% This checks for a nested function definition
>  	% or static initializer that references the variable.

> @@ -955,6 +1267,59 @@
>  		initializer_contains_var(Initializer, QualVarName)
>  	).
>  
> +	% Return `yes' if the type needs to be traced by
> +	% the accurate garbage collector, i.e. if it might
> +	% contain pointers.
> +	%
> +	% It's always safe to return `yes' here, so if in doubt, we do.
> +	%
> +	% For floats, we can return `no' even though they might
> +	% get boxed in some circumstances, because if they are
> +	% boxed then they will be represented as mlds__generic_type.
> +	%
> +	% 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.

> +:- func ml_type_might_contain_pointers(mlds__type) = bool.
> +
> +ml_type_might_contain_pointers(mercury_type(_Type, TypeCategory, _)) =
> +	ml_type_category_might_contain_pointers(TypeCategory).
> +ml_type_might_contain_pointers(mercury_array_type(_)) = yes.
> +ml_type_might_contain_pointers(mlds__native_int_type) = no.
> +ml_type_might_contain_pointers(mlds__native_float_type) = no.
> +ml_type_might_contain_pointers(mlds__native_bool_type) = no.
> +ml_type_might_contain_pointers(mlds__native_char_type) = no.
> +ml_type_might_contain_pointers(mlds__foreign_type(_, _)) = yes.
> +ml_type_might_contain_pointers(mlds__class_type(_, _, Category)) =
> +	(if Category = mlds__enum then no else yes).
> +ml_type_might_contain_pointers(mlds__ptr_type(_)) = yes.
> +ml_type_might_contain_pointers(mlds__array_type(_)) = yes.
> +ml_type_might_contain_pointers(mlds__func_type(_)) = no.
> +ml_type_might_contain_pointers(mlds__generic_type) = yes.
> +ml_type_might_contain_pointers(mlds__generic_env_ptr_type) = yes.
> +ml_type_might_contain_pointers(mlds__pseudo_type_info_type) = yes.
> +ml_type_might_contain_pointers(mlds__cont_type(_)) = no. 
> +ml_type_might_contain_pointers(mlds__commit_type) = no.
> +ml_type_might_contain_pointers(mlds__rtti_type(_)) = yes.
> +ml_type_might_contain_pointers(mlds__unknown_type) = yes.
> +
> +:- func ml_type_category_might_contain_pointers(builtin_type) = bool.
> +ml_type_category_might_contain_pointers(int_type) = no.
> +ml_type_category_might_contain_pointers(char_type) = no.
> +ml_type_category_might_contain_pointers(str_type) = yes.
> +ml_type_category_might_contain_pointers(float_type) = no.
> +ml_type_category_might_contain_pointers(pred_type) = yes.
> +ml_type_category_might_contain_pointers(tuple_type) = yes.
> +ml_type_category_might_contain_pointers(enum_type) = no.
> +ml_type_category_might_contain_pointers(polymorphic_type) = yes.
> +ml_type_category_might_contain_pointers(user_type) = yes.
> +

> Index: runtime/mercury.c
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/runtime/mercury.c,v
> retrieving revision 1.25
> diff -u -d -r1.25 mercury.c
> --- runtime/mercury.c	31 May 2001 06:00:10 -0000	1.25
> +++ runtime/mercury.c	8 Nov 2001 16:16:54 -0000
> @@ -26,6 +26,8 @@
>  ** Variable definitions
>  */
>  
> +void *mercury__private_builtin____stack_chain;
> +
>  MR_Word mercury__private_builtin__dummy_var;
>  
>  /*---------------------------------------------------------------------------*/
> Index: runtime/mercury.h
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/runtime/mercury.h,v
> retrieving revision 1.41
> diff -u -d -r1.41 mercury.h
> --- runtime/mercury.h	22 Nov 2001 16:22:29 -0000	1.41
> +++ runtime/mercury.h	26 Nov 2001 13:06:12 -0000
> @@ -273,10 +273,23 @@
>  typedef struct MR_FO_PseudoTypeInfo_Struct19 MR_FO_PseudoTypeInfo_Struct19;
>  typedef struct MR_FO_PseudoTypeInfo_Struct20 MR_FO_PseudoTypeInfo_Struct20;
>  
> +/* The chain of stack frames, used for accurate GC. */
> +struct MR_StackChain {
> +	struct MR_StackChain *prev;
> +	void (*trace)(void *this_frame);
> +};
> +
>  /*---------------------------------------------------------------------------*/
>  /*
>  ** 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;
>  

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