[m-rev.] for review: tail recursion and debugging

[Julien Fischer]

On Fri, 21 Nov 2008, Zoltan Somogyi wrote:

> Implement a new compiler option, --exec-trace-tail-rec, that preserves direct
> tail recursion in det and semidet procedures even when debugging is enabled.
> This should allow the debugging of programs that previously ran out of stack.
>
> The problem arose because even a directly tail-recursive call had some code
> after it: the code for the EXIT event, like this:
>
> 	p:
> 		incr_sp
> 		fill in the usual debug slots
> 		CALL EVENT
> 		...
> 		/* tail call */
> 		move arguments to registers as usual
> 		call p, return to p_ret
> 	p_ret:
> 		/* code to move output arguments to right registers is empty */
> 		EXIT EVENT
> 		decr_sp
> 		return
>
> If the new option is enabled, the compiler will now generate code like this:
>
> 	p:
> 		incr_sp
> 		fill in the usual debug slots
> 		fill in new "stack frame reuse count" slot with 0
> 		CALL EVENT
> 	p_1:
> 		...
> 		/* tail call */
> 		move arguments to registers as usual
> 		update the usual debug slots
> 		increment the "stack frame reuse count" slot
> 		TAILCALL EVENT
> 		goto p_1
>
> The new TAIL event takes place in the caller's stack frame, so that the local
> variables of the caller are available. This includes the arguments of the
> recursive call (though if they are unnamed variables, the debugger will not
> show them). The TAIL event serves as a replacement for the CALL event
> of the recursive invocation.
>
> compiler/options.m:
> 	Add the new option.
>
> compiler/handle_options.m:
> 	Handle an implications of the new option: the declarative debugger

s/implications/implication/

> 	does not (yet) understand TAIL events.
>
> compiler/mark_tail_calls.m:
> 	New module to mark directly tail recursive calls and the procedures
> 	containing them as such.
>
> compiler/hlds.m:
> compiler/notes/compiler_design.html:
> 	Mention the new module.
>
> compiler/mercury_compile.m:
> 	Invoke the new module when the new option asks us to.
>
> compiler/hlds_goal.m:
> 	Add the feature used to mark tail recursive calls for the debugger.
> 	Rename an existing feature with a similar but not identical purpose
> 	to avoid possible confusion.
>
> compiler/hlds_pred.m:
> 	Add a field to proc_infos that says whether the procedure contains
> 	tail recursive calls.
>
> 	Minor style improvements.
>
> compiler/passes_aux.m:
> 	Minor change to accommodate the needs of the new module.
>
> compiler/code_info.m:
> 	Transmit the information from mark_tail_calls to the code generator.
>
> compiler/call_gen.m:
> 	Implement the new option.
>
> compiler/trace_gen.m:
> 	Reserve the extra slot needed for the new option.
>
> 	Switch to state variable notation in the code that does the slot
> 	allocation, since this is less error-prone than the previous approach.
>
> compiler/layout.m:
> compiler/layout_out.m:
> compiler/stack_layout.m:
> 	Remember what stack slot holds the stack frame reuse counter,
> 	for transmission to the runtime system.
>
> compiler/proc_gen.m:
> 	Add the new label needed for tail recursion.
>
> 	Put the arguments of some procedures into a more logical order.
>
> compiler/deep_profiling.m:
> compiler/deforest.m:
> compiler/saved_vars.m:
> compiler/table_gen.m:
> 	Conform to the changes above.
>
> compiler/trace_params.m:
> mdbcomp/prim_data.m:
> runtime/mercury_trace_base.[ch]:
> 	Add the new event type.
>
> 	Convert mercury_trace_base.h to four-space indentation.
>
> runtime/mercury_stack_layout.h:
> 	Add a field to the execution trace information we have for each
> 	procedure that gives the number of the stack slot (if any) that holds
> 	the stack frame reuse counter. Add a macro to get the value in the
> 	counter.
>
> 	Convert this header file to four-space indentation.
>
> runtime/mercury_stack_trace.[ch]:
> 	When walking the stack, we now have to be prepared to encounter stack
> 	frames that have been reused. Modify the algorithms in this module
> 	accordingly, and modify the interfaces of the exported functions
> 	to allow the functions' callers to behave accordingly as well.
>
> 	Group the information we gather about stack frame for printing into
> 	one structure, and document it.
>
> 	Convert the header to four-space indentation.
>
> library/exception.m:
> mdbcomp/trace_counts.m:
> 	Conform to the changes above.
>
> 	In trace_counts.m, fix an apparent cut-and-paste error (that hasn't
> 	caused any test case failures yet).
>
> trace/mercury_trace.c:
> 	Modify the implementation of the "next" and "finish" commands
> 	to accommodate the possibility that the procedure at the selected
> 	depth may have had its stack frame reused. In such cases
>
> tests/debugger/tailrec1.{m,inp,exp,data}:
> 	A new test case to check the handling of tail recursive procedures.

...

> Index: runtime/mercury_stack_layout.h
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_stack_layout.h,v
> retrieving revision 1.114
> diff -u -b -r1.114 mercury_stack_layout.h
> --- runtime/mercury_stack_layout.h	18 Mar 2008 01:31:33 -0000	1.114
> +++ runtime/mercury_stack_layout.h	21 Nov 2008 02:41:18 -0000
> @@ -1,4 +1,7 @@
> /*
> +** vim: ts=4 sw=4 expandtab
> +*/
> +/*
> ** Copyright (C) 1998-2008 The University of Melbourne.
> ** This file may only be copied under the terms of the GNU Library General
> ** Public License - see the file COPYING.LIB in the Mercury distribution.
> @@ -913,6 +916,14 @@
> ** The flags field encodes boolean properties of the procedure. For now,
> ** the only property is whether the procedure has a pair of I/O state
> ** arguments.
> +**
> +XXX
> +** If the procedure contains on the nondet stack, or if it cannot create any

That first bit doesn't make sense.

> +** temporary nondet stack frames, the maybe_maxfr field will contain a negative
> +** number. If it lives on the det stack, and can create temporary nondet stack
> +** frames, it will contain the number number of the stack slot that contains the
> +** value of maxfr on entry, for use in executing the retry debugger command
> +** from the middle of the procedure.
> */
>
> #define	MR_EVAL_METHOD_MEMO_STRICT	MR_EVAL_METHOD_MEMO
> @@ -964,6 +975,7 @@
> 	MR_int_least8_t		MR_exec_maybe_call_table;
> 	MR_TraceLevelInt	MR_exec_trace_level_CAST_ME;
> 	MR_uint_least8_t	MR_exec_flags;
> +    MR_int_least8_t             MR_exec_maybe_tail_rec;
> } MR_ExecTrace;
>
> #define MR_compute_max_mr_num(max_mr_num, layout)			\

...

> Index: runtime/mercury_stack_trace.c
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_stack_trace.c,v
> retrieving revision 1.81
> diff -u -b -r1.81 mercury_stack_trace.c
> --- runtime/mercury_stack_trace.c	7 Aug 2008 01:16:19 -0000	1.81
> +++ runtime/mercury_stack_trace.c	21 Nov 2008 03:04:04 -0000

...

> @@ -1081,83 +1097,98 @@
>     ** We cannot merge two calls even to the same procedure if we are printing
>     ** trace data, since this will differ between the calls.
>     **
> -    ** Note that it is not possible for two calls to the same procedure to differ
> -    ** on whether the procedure has trace layout data or not.
> +    ** Note that it is not possible for two calls to the same procedure
> +    ** to differ on whether the procedure has trace layout data or not.
>     */
> -    must_flush = (entry_layout != prev_entry_layout) || trace_data_enabled;
> +    must_flush = (proc_layout != prev_dump_info.MR_sdi_proc_layout)
> +        || trace_data_enabled;
>
>     if (must_flush) {
>         if (! at_line_limit) {
> -            MR_dump_stack_record_flush(fp, print_stack_record);
> +            MR_dump_stack_record_flush(fp, trace_data_enabled,
> +                print_stack_record);
>         }
>
> -        prev_entry_layout = entry_layout;
> -        prev_entry_layout_count = 1;
> -        prev_entry_start_level = current_level;
> -        prev_entry_base_sp = base_sp;
> -        prev_entry_base_curfr = base_curfr;
> -        prev_entry_filename = filename;
> -        prev_entry_linenumber = linenumber;
> -        prev_entry_goal_path = MR_label_goal_path(label_layout);
> -        prev_entry_context_mismatch = MR_FALSE;
> +        prev_dump_info.MR_sdi_proc_layout = proc_layout;
> +        prev_dump_info.MR_sdi_num_frames = 1;
> +        prev_dump_info.MR_sdi_min_level = current_level;
> +        prev_dump_info.MR_sdi_max_level = current_level + reused_frames;
> +        prev_dump_info.MR_sdi_filename = filename;
> +        prev_dump_info.MR_sdi_linenumber = linenumber;
> +        prev_dump_info.MR_sdi_context_mismatch = MR_FALSE;
> +
> +        prev_dump_info.MR_sdi_base_sp = base_sp;
> +        prev_dump_info.MR_sdi_base_curfr = base_curfr;
> +        prev_dump_info.MR_sdi_goal_path = MR_label_goal_path(label_layout);
> +
>         lines_printed = 1;
>     } else {
> -        prev_entry_layout_count++;
> -        if (prev_entry_filename != filename
> -            || prev_entry_linenumber != linenumber)
> +        prev_dump_info.MR_sdi_num_frames++;
> +        prev_dump_info.MR_sdi_max_level = current_level + reused_frames;
> +        if (prev_dump_info.MR_sdi_filename != filename
> +            || prev_dump_info.MR_sdi_linenumber != linenumber)
>         {
> -            prev_entry_context_mismatch = MR_TRUE;
> +            prev_dump_info.MR_sdi_context_mismatch = MR_TRUE;
>         }
> +
>         lines_printed = 0;
>     }
>
> -    current_level++;
> +    current_level += 1 + reused_frames;
>     return lines_printed;
> }
>
> static void
> -MR_dump_stack_record_flush(FILE *fp, MR_PrintStackRecord print_stack_record)
> +MR_dump_stack_record_flush(FILE *fp, MR_bool include_trace_data,
> +    MR_PrintStackRecord print_stack_record)
> {
> -    if (prev_entry_layout != NULL) {
> -        print_stack_record(fp, prev_entry_layout,
> -            prev_entry_layout_count, prev_entry_start_level,
> -            prev_entry_base_sp, prev_entry_base_curfr,
> -            prev_entry_filename, prev_entry_linenumber,
> -            prev_entry_goal_path, prev_entry_context_mismatch);
> +    if (prev_dump_info.MR_sdi_proc_layout != NULL) {
> +        print_stack_record(fp, include_trace_data, prev_dump_info);
>     }
> }
>
> void
> -MR_dump_stack_record_print(FILE *fp, const MR_ProcLayout *proc_layout,
> -    int count, MR_Level start_level, MR_Word *base_sp, MR_Word *base_curfr,
> -    const char *filename, int linenumber, const char *goal_path,
> -    MR_bool context_mismatch)
> -{
> -    fprintf(fp, "%4" MR_INTEGER_LENGTH_MODIFIER "d ", start_level);
> -
> -    if (count > 1) {
> -        fprintf(fp, " %3d* ", count);
> -    } else if (! trace_data_enabled) {
> -        fprintf(fp, "%5s ", "");
> -    } else {
> +MR_dump_stack_record_print(FILE *fp, MR_bool include_trace_data,
> +    const MR_StackDumpInfo dump_info)
> +{
> +    MR_Level    num_levels;
> +
> +    num_levels = dump_info.MR_sdi_max_level + 1 - dump_info.MR_sdi_min_level;
> +    fprintf(fp, "%4" MR_INTEGER_LENGTH_MODIFIER "d ",
> +        dump_info.MR_sdi_min_level);
> +
>         /*
> -        ** If we are printing trace data, we need all the horizonal
> -        ** room we can get, and there will not be any repeated lines,
> -        ** so we don't reserve space for the repeat counts.
> +    ** If we are printing trace data, we need all the horizonal room

s/horizonal/horizontal/

> +    ** we can get, and there will not be any repeated lines, so we do not
> +    ** reserve space for the repeat counts.

...


That looks okay otherwise.

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------