[m-dev.] for review: direct retries

[Fergus Henderson]

On 20-Jan-2000, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> 
> +++ compiler/handle_options.m	2000/01/15 04:46:16
> @@ -338,6 +338,12 @@
>  		;
>  			[]
>  		),
> +
> +			% The following option allows us to perform retries
> +			% from the middle of procedure bodies without requiring
> +			% us to store everything on the nondet stack that may
> +			% be hijacked being saved on entry to every procedure.

That sentence doesn't quite make sense.

> Index: compiler/hlds_pred.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/hlds_pred.m,v
> retrieving revision 1.69
> diff -u -b -r1.69 hlds_pred.m
> --- compiler/hlds_pred.m	2000/01/13 06:15:52	1.69
> +++ compiler/hlds_pred.m	2000/01/15 04:46:17
> @@ -1488,6 +1488,18 @@
>  :- pred proc_info_set_rl_exprn_id(proc_info, rl_exprn_id, proc_info).
>  :- mode proc_info_set_rl_exprn_id(in, in, out) is det.
>  
> +:- pred proc_info_get_maxfr_slot_flag(proc_info, bool).
> +:- mode proc_info_get_maxfr_slot_flag(in, out) is det.
> +
> +:- pred proc_info_set_maxfr_slot_flag(proc_info, bool, proc_info).
> +:- mode proc_info_set_maxfr_slot_flag(in, in, out) is det.

This change is not documented in the log message.

"maxfr" is an LLDS concept.  In general, it would be
preferable if the HLDS does not depend on the LLDS.
Currently there are a few places where it does, but I
would like to eliminate them eventually; this change
adds a couple more such places.

A reasonable interim approach might be to group all the
proc_info fields related to the LLDS back-end as a single
structure that was a field of the proc_info.
However, that's probably enough work that it would be
best done as a separate change.  For now I guess I'd be
happy if you just add an XXX comment noting that this
field is only applicable for the LLDS back-end.

> +:- pred proc_info_get_call_table_tip(proc_info, maybe(prog_var)).
> +:- mode proc_info_get_call_table_tip(in, out) is det.
> +
> +:- pred proc_info_set_call_table_tip(proc_info, maybe(prog_var), proc_info).
> +:- mode proc_info_set_call_table_tip(in, in, out) is det.
...
> +			bool,		% True iff tracing is enabled, this
> +					% is a procedure that lives on the det
> +					% stack, and the code of this procedure
> +					% may create a frame on the det stack.
> +					% (Only in these circumstances do we
> +					% need to reserve a stack slot to hold
> +					% the value of maxfr at the call, for
> +					% use in implementing retry.)
> +					%
> +					% This slot is set during the live_vars
> +					% pass; it is invalid before then.
> +			maybe(prog_var)	% If the tracing is enabled and the
> +					% procedure's evaluation method is
> +					% memo, loopcheck or minimal, this
> +					% slot identifies the variable that
> +					% holds the tip of the call table;
> +					% when this variable is bound, we
> +					% must put this variable in its stack
> +					% slot, for use by the retry command.
> +					% Otherwise, this field will be set to
> +					% `no'.

It's not clear from the documentation above what you mean by
the "tip of the call table".  The log message is clear enough,
but I think the documentation here should have the same information
that is in the log message.

I'm not sure whether this field is back-end independent or not.
Certainly its documentation is not; the mention of stack slots
assumes the use of the LLDS back-end.  I think in fact it is
likely that any back-end whose debugger supports retry will
have to handle these variables specially, so it is in that sense
back-end independent (even if currently the LLDS back-end is the
only one that has a debugger, let alone a debugger that supports
retry).  If that is correct, then I think it would be nice to
change the documentation to just say that this variable must
be restored on retry, perhaps giving more information about
what happens with the LLDS back-end as an example.

It's not clear which field the comment

> +					% This slot is set during the live_vars
> +					% pass; it is invalid before then.

applies to; if it is intended to apply to the field above it,
then I suggest appending a blank line after that comment.

(Note that these comments are duplicated later on in the file,
so make sure that any changes you make here get duplicated below.)

> +++ compiler/stack_layout.m	2000/01/15 04:46:23
> @@ -21,7 +21,7 @@
>  %
>  %---------------------------------------------------------------------------%
>  %
> -% Data Stucture: stack_layouts
> +% Data Stucture: procedure ayouts

s/Stucture/Structure/
             ^

s/ayouts/layouts/
         ^

> +% The max_r_num field tells the debugger which Mercury abstract machine
> +% registers need saving in MR_trace: besides the special registers, it is
> +% the general-purpose registers rN for values of N up to and including the
> +% value of this field. Note that this field contains an upper bound; in
> +% general, there will be calls to MR_trace at which the number of the highest
> +% numbered gp registers is less than this. However, storing the upper bound
> +% gets us almost all the benefit (of not saving/restoring all the thousand gp
> +% abstract machine registers) for a small fraction of the static space cost
> +% of storing the actual number in label layout structures.

I suggest expanding out the "gp" acronym: "gp register" commonly
means "global pointer register" rather than "general purpose register",
so this acronym is potentially quite confusing.

> +% If the procedure is compiled with deep tracing, the maybe from full field
> +% will contain a negative number. If it is compiled with shallow tracing,
> +% it will contain the number of the stack slot that holds the flag that says
> +% whether this incarnation of the procedure was called from deeply traced code
> +% or not. (The determinism of the procedure decides whether the stack slot
> +% refers to a stackvar or a framevar.)
> +%
> +% If trailing is not enabled, the maybe trail field will contain a negative
> +% number. If it is enabled, it will contain number of the first of two stack
> +% slots used for recording the state of the trail on entry to the procedure.
> +% The first contains the trail pointer, the second the ticket.

I suggest you use the word "check-pointing" rather than "recording".
The reason is that we don't just record the current state of the
trail, we actually have to allocate a trail ticket (i.e. increment
the ticket counter), so that execution can backtrack to this point.

> +% Data Stucture: label ayouts

s/Stucture/Structure/
             ^

s/ayouts/layouts/
         ^

> +:- pred stack_layout__represent_eval_method(eval_method::in, int::out) is det.
> +
> +stack_layout__represent_eval_method(eval_normal,     0).
> +stack_layout__represent_eval_method(eval_loop_check, 1).
> +stack_layout__represent_eval_method(eval_memo,       2).
> +stack_layout__represent_eval_method(eval_minimal,    3).

I would have made that one a function, rather than a predicate.

> --- compiler/table_gen.m	1999/12/21 01:22:59	1.14
> +++ compiler/table_gen.m	2000/01/15 04:46:27
> @@ -252,19 +252,22 @@
>  		table_gen__create_new_det_goal(EvalMethod, OrigGoal,
>  			PredId, ProcId, HeadVars, ArgModes,
>  			VarTypes0, VarTypes, VarSet0, VarSet,
> -			TableInfo0, TableInfo, Goal)
> +			TableInfo0, TableInfo, CallTableTip, Goal),
> +		MaybeCallTableTip = yes(CallTableTip)
>  	;
>  		CodeModel = model_semi,
>  		table_gen__create_new_semi_goal(EvalMethod, OrigGoal,
>  			PredId, ProcId, HeadVars, ArgModes,
>  			VarTypes0, VarTypes, VarSet0, VarSet,
> -			TableInfo0, TableInfo, Goal)
> +			TableInfo0, TableInfo, CallTableTip, Goal),
> +		MaybeCallTableTip = yes(CallTableTip)
>  	;
>  		CodeModel = model_non,
>  		table_gen__create_new_non_goal(EvalMethod, OrigGoal,
>  			PredId, ProcId, HeadVars, ArgModes,
>  			VarTypes0, VarTypes, VarSet0, VarSet,
> -			TableInfo0, TableInfo, Goal)
> +			TableInfo0, TableInfo, CallTableTip, Goal),
> +		MaybeCallTableTip = yes(CallTableTip)
>  	),

It would be better, IMHO, to put the unification
`MaybeCallTableTip = yes(CallTableTip)' outside the switch,
rather than duplicating it three times.

> Index: compiler/trace.m
...
> +	% stage 7:	If the procedure's evaluation method is memo, loopcheck
> +	%		or minimal model, we allocate a slot to hold the

I suggest changing the comment to "If the procedure's evaluation method
uses tabling, ...".  Likewise for the same comment in a few other places.

> @@ -348,15 +422,44 @@
...
> +	{ proc_info_get_maxfr_slot_flag(ProcInfo, yes) ->
> +		MaybeMaxfrSlot = yes(NextSlotAfterTrail),
> +		( CodeModel = model_non ->
> +			MaxfrLval =  framevar(NextSlotAfterTrail)
> +		;
> +			MaxfrLval =  stackvar(NextSlotAfterTrail)
> +		),
> +		MaybeMaxfrLval = yes(MaxfrLval),
> +		NextSlotAfterMaxfr = NextSlotAfterTrail + 1
> +	;
> +		MaybeMaxfrSlot = no,
> +		MaybeMaxfrLval = no,
> +		NextSlotAfterMaxfr = NextSlotAfterTrail
> +	},
> +	{ proc_info_get_call_table_tip(ProcInfo, yes(_)) ->
> +		MaybeCallTableSlot = yes(NextSlotAfterMaxfr),
> +		( CodeModel = model_non ->
> +			CallTableLval =  framevar(NextSlotAfterMaxfr)
> +		;
> +			CallTableLval =  stackvar(NextSlotAfterMaxfr)
> +		),

That five-line code fragment is duplicated in at least two places,
probably more.  I suggest definition a function

	stackslot(CodeModel, Slot) =
		(if CodeModel = model_non then
			framevar(Slot)
		else
			stackvar(Slot)
		).

and then using that.

> Index: doc/user_guide.texi
...
> + at item fail [-NSans] [@var{num}]
> +Continues execution until it reaches a FAIL or EXCEPTION port
> +of the @var{num}'th ancestor of the call to which the current event refers.
> +The default value of @var{num} is zero,
> +which means skipping to the failure of the current call.
> +Reports an error if execution is already at the desired port,
> +or if the determinism of the selected call
> +does not guarantee that it will eventually fail.

This command is problematic because of the issue that I noted
earlier where a nondet goal may never fail, because its caller
commits to the first solution.

> @@ -384,6 +391,17 @@
>  	MR_int_least16_t	MR_sle_max_r_num;
>  	MR_int_least8_t		MR_sle_maybe_from_full;
>  	MR_int_least8_t		MR_sle_maybe_trail;
> +				/*
> +				** the eval method field is actually of type
> +				** MR_EvalMethod. We declare it as of type
> +				** MR_int_least8_t in order to make sure that
> +				** the size allocated for the field by the C
> +				** compiler matches the expectations of
> +				** stack_layout.m.
> +				*/
> +	MR_int_least8_t		MR_sle_maybe_maxfr;
> +	MR_int_least8_t		MR_sle_eval_method;

That comment should go in front of the MR_sle_eval_mothod field,
not in front of the MR_sle_maybe_maxfr field.

> +++ trace/mercury_trace.c	2000/01/15 04:45:47
...
> +/*
> +** This function figures out the state of the stacks (i.e. the values of sp,
> +** curfr and maxfr) just after entry to the procedure specified by the given
> +** ancestor level, and returns the proc layout for the specified procedure.
> +** It also

That comment is incomplete.

> +static const char *
> +MR_undo_updates_of_maxfr(const MR_Stack_Layout_Entry *level_layout,
> +	Word *sp, Word *curfr, Word **maxfr_ptr)
> +{
> +	if (MR_DETISM_DET_STACK(level_layout->MR_sle_detism)) {
> +		/*
> +		** The code of a procedure that lives on the det stack
> +		** never updates curfr, but may update maxfr by pushing
> +		** a temporary nondet frame. If it does so, and the
> +		** procedure is traced, the original value of maxfr 
> +		** will be saved in a stack slot.
> +		*/
> +
> +		if (! MR_ENTRY_LAYOUT_HAS_EXEC_TRACE(level_layout)) {
> +			return "an intervening stack frame "
> +				"has no debugging information";
> +		} else if (level_layout->MR_sle_maybe_maxfr > 0) {
> +			*maxfr_ptr = (Word *) MR_based_stackvar(sp,
> +				level_layout->MR_sle_maybe_maxfr);
> +			fprintf(stdout, "resetting maxfr to ");
> +			MR_print_nondstackptr(stdout, *maxfr_ptr);
> +			fprintf(stdout, "\n");

The debugging code there should be inside a #ifdef.

mercury_trace.h:
> +** If resetting the stacks requires discarding the stack frame of a procedure
> +** whose evaluation method is memo or loopcheck, we must also reset the call
> +** table entry for that particular call to uninitialized. There are two reasons
> +** for this. The first is that the call table entry was uninitialized at the
> +** time of the first call, so if the retried call is to what the original call

s/to what/to do what/

> +** If the fail command reaches an exception port on the selected call instead
> +** of the fail port, then the SCC cannot be made quiescent

Hmm... will this lead to problems when mixing minimal model tabling
and exceptions, even in the absence of tracing?
In fact, won't this issue also cause problems even for ordinary
(memo or loopcheck) tabling of det/semidet procedures?

[... 5 minutes later ...]
I just tested it, and yes, it does cause problems :-(

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------