[m-rev.] for review: optimizing shallow traced modules

[Mark Brown]

On 04-Jul-2002, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> For review by anyone.
> 
> Zoltan.
> 
> Estimated hours taken: 8
> 
> Optimize shallow traced modules by not adding calls to MR_trace to shallow
> traced procedures which cannot be called from a deep traced environment.
> A shallow traced procedure can be optimized in this way if it is neither
> exported from its defining module nor has its address taken.
> 
> The main purpose of this optimization is not the avoidance of the cost of the
> MR_trace calls as much as it is the restoration of tail recursion optimization.
> Previosly, compiling a program in a debug grade would disable all tail

s/Previosly/Previously/

> recursion in the program (since debug grades require at least shallow tracing
> every module. This was a problem because it limited the sizes of the inputs

Unmatched ')'.

> the debugged program could process before running out of memory. As long as
> the procedures that recurse on the input are in the implementation section
> of a shallow traced module, this should no longer happen.
> 
> compiler/trace_params.m:
> 	Introduce the concept of a procedure's effective trace level. This is
> 	identical to the global trace level, except if the procedure is not
> 	exported and doesn't have its address taken, and the global trace level
> 	is shallow. In that case, we say that the procedure's effective trace
> 	level is none.
> 
> 	Computing a procedure's effective trace level requires its proc_info
> 	and its parent pred_info, so require callers to supply these as
> 	parameters.
> 
> compiler/code_info.m:
> 	Store the current pred_info as well as the current proc_info, for
> 	trace parameter lookups.
> 
> compiler/continuation_info.m:
> compiler/code_gen.m:
> 	Record the required trace parameters of a procedure in its layout
> 	structure, since it can no longer be computed from the global trace
> 	level.
> 
> compiler/stack_layout.m:
> 	Use the trace parameters in procedures' layout structures, instead of
> 	trying to compute them from the global trace level.
> 
> compiler/inlining.m:
> compiler/liveness.m:
> compiler/stack_alloc.m:
> compiler/store_alloc.m:
> compiler/trace.m:
> 	Use procedures' effective trace level instead of the global trace level
> 	where relevant.
> 
> compiler/llds.m:
> 	Record the required trace parameter of a procedure in its c_procedure
> 	representation, since it can no longer be computed from the global
> 	trace level.
> 
> compiler/optimize.m:
> compiler/jumpopt.m:
> 	Use a required trace parameter of a procedure in its c_procedure
> 	representation, since it can no longer be computed from the global
> 	trace level.
> 
> 	Delete an obsolete field.

This point applies to llds.m better than here.

> 
> compiler/compile_target_code.m:
> compiler/handle_options.m:
> compiler/llds_out.m:
> compiler/mercury_compile.m:
> 	Trivial changes to conform to updated interfaces.
> 
> tests/debugger/shallow.m:
> tests/debugger/shallow2.m:
> tests/debugger/shallow.{inp,exp*}:
> 	Divide the old test case in shallow.m in two. The top level predicates
> 	stay in shallow.m and continue to be shallow traced. The two bottom
> 	predicates move to shallow2.m and are now deep traced.
> 
> 	The new test input checks whether the debugger can walk across the
> 	stack frames of procedures in shallow traced modules whose effective
> 	trace level is "none" (such as queen/2).
> 
> Index: compiler/code_gen.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/code_gen.m,v
> retrieving revision 1.102
> diff -u -b -r1.102 code_gen.m
> --- compiler/code_gen.m	2002/04/04 06:00:08	1.102
> +++ compiler/code_gen.m	2002/06/19 16:19:32
> @@ -344,11 +346,25 @@
>  		proc_info_headvars(ProcInfo, HeadVars),
>  		proc_info_varset(ProcInfo, VarSet),
>  		proc_info_vartypes(ProcInfo, VarTypes),
> +		globals__get_trace_suppress(Globals, TraceSuppress),
> +		(
> +			eff_trace_needs_proc_body_reps(PredInfo, ProcInfo,
> +				TraceLevel, TraceSuppress) = yes
> +		->
> +			MaybeGoal = yes(Goal)
> +		;
> +			MaybeGoal = no
> +		),
> +		IsBeingTraced = bool__not(eff_trace_level_is_none(PredInfo,
> +			ProcInfo, TraceLevel)),

Or:
		IsBeingTraced = bool__not(EffTraceIsNone)

> Index: compiler/inlining.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/inlining.m,v
> retrieving revision 1.107
> diff -u -b -r1.107 inlining.m
> --- compiler/inlining.m	2002/03/28 03:43:05	1.107
> +++ compiler/inlining.m	2002/06/19 15:34:30
> @@ -855,7 +855,11 @@
>  	module_info_globals(ModuleInfo, Globals),
>  	globals__lookup_bool_option(Globals, highlevel_code, HighLevelCode), 
>  	globals__get_trace_level(Globals, TraceLevel),
> -	Tracing = bool__not(trace_level_is_none(TraceLevel)),
> +	module_info_pred_info(ModuleInfo, PredId, PredInfo),
> +	pred_info_procedures(PredInfo, Procs),
> +	map__lookup(Procs, ProcId, ProcInfo),
> +	Tracing = bool__not(
> +		eff_trace_level_is_none(PredInfo, ProcInfo, TraceLevel)),
>  	inlining__can_inline_proc(PredId, ProcId, BuiltinState,
>  		HighLevelCode, Tracing, InlinePromisedPure,
>  		CallingPredMarkers, ModuleInfo).

Could you please confirm that the following from the body of
inlining__can_inline_proc/8 is still true when talking about effective
trace level?

        % XXX:
        % If tracing is enabled, then the code generator will need to figure
        % out the locations of typeinfos inside typeclass_infos. At the moment,
        % due to a bug, the algorithm for doing this figuring can cause a
        % compiler abort if we inline calls that have typeclass constraints.

If so you should update the comment to specifically mention effective
trace level.  It would also be good to add a comment to the top of
inlining__can_inline_proc/8 to say that it expects the effective trace
level.

> Index: compiler/stack_opt.m

This isn't mentioned in the log message.

> Index: compiler/trace_params.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/trace_params.m,v
> retrieving revision 1.9
> diff -u -b -r1.9 trace_params.m
> --- compiler/trace_params.m	2002/06/05 16:41:14	1.9
> +++ compiler/trace_params.m	2002/07/04 03:59:46
> @@ -10,6 +10,23 @@
>  %
>  % This module defines the parameters of execution tracing at various trace
>  % levels and with various settings of the --suppress-trace option.
> +%
> +% Many of the functions defined in this module work not with the global trace
> +% level, but with effective trace levels.

I think it would be clearer to state that many functions in this module
convert the given (global) trace level to the effective trace level
before calculating their result.  But only after you have defined
"effective trace level".

In most cases the trace level we want
> +% to apply to a procedure (which is its effective trace level) is the same as
> +% the global trace level. However, if the global trace level is shallow, then
> +% we optimize the handling of procedures that cannot be called from deep traced
> +% contexts. If a procedure is neither exported nor has its address taken, then
> +% it can only be called from other procedures in its module. If the module is
> +% shallow traced, this guarantees that we will never get any events from the
> +% procedure, so there is no point in including any tracing code in it in the
> +% first place. We therefore make its effective trace level "none" for must
> +% purposes (the purposes whose functions test effective trace levels). Apart
> +% from avoiding the overhead of calls to MR_trace, this also allows the code
> +% generator to preserve tail recursion optimization. However, we continue to
> +% generate the data structures that enable the debugger to walk the stack for
> +% such procedures. We accomplish this by making the relevant test work on the
> +% global trace level, not effective trace levels.

I found this paragraph difficult to follow; in fact, I found the log
message much clearer (although it didn't cover everything here).  My
suggestion would be to break this into separate paragraphs which:
	- define "effective trace level", and why it exists;
	- state what kind of callers want to use the effective level
	  and what want to use the global level.

> @@ -29,21 +47,34 @@
>  :- pred convert_trace_suppress(string::in, trace_suppress_items::out)
>  	is semidet.
>  
> -	% These functions check for various properties of the trace level.
> -:- func trace_level_is_none(trace_level) = bool.
> -:- func trace_level_needs_input_vars(trace_level) = bool.
> -:- func trace_level_needs_fixed_slots(trace_level) = bool.
> -:- func trace_level_needs_from_full_slot(trace_level) = bool.
> +	% These functions check for various properties of the global
> +	% trace level.
> +:- func given_trace_level_is_none(trace_level) = bool.

I'm not sure of the need for changing this name, since the function would
work just as well with either definition of trace level.

>  :- func trace_level_allows_delay_death(trace_level) = bool.
>  :- func trace_needs_return_info(trace_level, trace_suppress_items) = bool.
> -:- func trace_needs_all_var_names(trace_level, trace_suppress_items) = bool.
> -:- func trace_needs_proc_body_reps(trace_level, trace_suppress_items) = bool.
> -:- func trace_needs_port(trace_level, trace_suppress_items, trace_port) = bool.
>  

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