[m-rev.] for review: heap reclamation on failure for MLDS back-end

[Peter Ross]

On Fri, Nov 23, 2001 at 02:51:55AM +1100, Fergus Henderson wrote:
> Estimated hours taken: 3
> Branches: main
> 
> Implement heap reclamation on failure for the MLDS back-end.
> 
> library/private_builtin.m:
> 	Add impure procedures for saving and restoring the heap pointer.
> 
> compiler/add_heap_ops.m:
> 	New file, similar to add_trail_ops.m.
> 	An HLDS->HLDS transformation to add heap reclamation operations.
> 
> compiler/mercury_compile.m:
> 	Call the new pass.
> 
> compiler/notes/compiler_design.html:
> 	Mention the new pass.
> 
> Workspace: /home/earth/fjh/ws-earth3/mercury
> Index: compiler/add_heap_ops.m
> ===================================================================
> RCS file: compiler/add_heap_ops.m
> diff -N compiler/add_heap_ops.m
> --- /dev/null	1 Jan 1970 00:00:00 -0000
> +++ compiler/add_heap_ops.m	22 Nov 2001 15:10:08 -0000
> @@ -0,0 +1,355 @@
> +%-----------------------------------------------------------------------------%
> +% Copyright (C) 2000-2001 The University of Melbourne.
> +% This file may only be copied under the terms of the GNU General
> +% Public License - see the file COPYING in the Mercury distribution.
> +%-----------------------------------------------------------------------------%
> +%
> +% Author: fjh.
> +%
> +% This module is an HLDS-to-HLDS transformation that inserts code to
> +% handle heap reclamation on backtracking, by saving and restoring
> +% the values of the heap pointer.
> +% The transformation involves adding calls to impure
> +% predicates defined in library/private_builtin.m, which in turn call
> +% the MR_mark_hp() and MR_restore_hp() macros defined in
> +% runtime/mercury_heap.h.
> +%
> +% This pass is currently only used for the MLDS back-end.
> +% For some reason (perhaps efficiency?? or more likely just historical?),
> +% the LLDS back-end inserts the heap operations as it is generating
> +% LLDS code, rather than via an HLDS to HLDS transformation.
> +%
> +% This module is very similar to add_trail_ops.m.
> +%
> +%-----------------------------------------------------------------------------%
> +
> +% XXX check goal_infos for correctness
> +
Have you checked the goal_infos for correctness? ;)

> +%-----------------------------------------------------------------------------%
> +
> +:- module add_heap_ops.
> +:- interface.
> +:- import_module hlds_pred, hlds_module.
> +
> +:- pred add_heap_ops(proc_info::in, module_info::in, proc_info::out) is det.
> +
> +%-----------------------------------------------------------------------------%
> +
> +:- implementation.
> +
> +:- import_module prog_data, prog_util, (inst).
> +:- import_module hlds_goal, hlds_data, quantification, modules, type_util.
> +:- import_module instmap.
> +
> +:- import_module bool, string.
> +:- import_module assoc_list, list, map, set, varset, std_util, require, term.
> +
> +
> +%
> +% As we traverse the goal, we add new variables to hold the
> +% saved values of the heap pointer.
> +% So we need to thread a varset and a vartypes mapping through,
> +% to record the names and types of the new variables.
> +%
> +% We also keep the module_info around, so that we can use
> +% the predicate table that it contains to lookup the pred_ids
> +% for the builtin procedures that we insert calls to.
> +% We do not update the module_info as we're traversing the goal.
> +%
> +
> +:- type heap_ops_info --->
> +	heap_ops_info(
> +		varset :: prog_varset,
> +		var_types :: vartypes,
> +		module_info :: module_info
> +	).
> +
> +add_heap_ops(Proc0, ModuleInfo0, Proc) :-
> +	proc_info_goal(Proc0, Goal0),
> +	proc_info_varset(Proc0, VarSet0),
> +	proc_info_vartypes(Proc0, VarTypes0),
> +	TrailOpsInfo0 = heap_ops_info(VarSet0, VarTypes0, ModuleInfo0),
> +	goal_add_heap_ops(Goal0, Goal, TrailOpsInfo0, TrailOpsInfo),
> +	TrailOpsInfo = heap_ops_info(VarSet, VarTypes, _),
> +	proc_info_set_goal(Proc0, Goal, Proc1),
> +	proc_info_set_varset(Proc1, VarSet, Proc2),
> +	proc_info_set_vartypes(Proc2, VarTypes, Proc3),
> +	% The code below does not maintain the non-local variables,
> +	% so we need to requantify.
> +	% XXX it would be more efficient to maintain them
> +	%     rather than recomputing them every time.
> +	requantify_proc(Proc3, Proc).
> +
> +:- pred goal_add_heap_ops(hlds_goal::in, hlds_goal::out,
> +		heap_ops_info::in, heap_ops_info::out) is det.


> +goal_expr_add_heap_ops(disj(Goals0, B), GoalInfo, Goal - GoalInfo) -->
> +	{ Goals0 = [_|_] },
> +
> +	{ goal_info_get_context(GoalInfo, Context) },
> +
> +	%
> +	% Save the heap pointer so that we can
> +	% restore it on back-tracking.
> +	%
> +	new_saved_hp_var(SavedHeapPointerVar),
> +	gen_mark_hp(SavedHeapPointerVar, Context, MarkHeapPointerGoal),
> +	disj_add_heap_ops(Goals0, yes, SavedHeapPointerVar, Goals),
> +	{ Goal = conj([MarkHeapPointerGoal, disj(Goals, B) - GoalInfo]) }.
> +

> +goal_expr_add_heap_ops(not(InnerGoal), OuterGoalInfo, Goal) -->
> +	%
> +	% We handle negations by converting them into if-then-elses:
> +	%	not(G)  ===>  (if G then fail else true)
> +	%
> +	{ goal_info_get_context(OuterGoalInfo, Context) },
> +	{ InnerGoal = _ - InnerGoalInfo },
> +	{ goal_info_get_determinism(InnerGoalInfo, Determinism) },
> +	{ determinism_components(Determinism, _CanFail, NumSolns) },
> +	{ true_goal(Context, True) },
> +	{ fail_goal(Context, Fail) },
> +	{ map__init(SM) },
> +	{ NumSolns = at_most_zero ->
> +		% The "then" part of the if-then-else will be unreachable,
> +		% but to preserve the invariants that the MLDS back-end
> +		% relies on, we need to make sure that it can't fail.
> +		% So we use `true' rather than `fail' for the "then" part.
> +		NewOuterGoal = if_then_else([], InnerGoal, True, True, SM)
> +	;
> +		NewOuterGoal = if_then_else([], InnerGoal, Fail, True, SM)
> +	},
> +	goal_expr_add_heap_ops(NewOuterGoal, OuterGoalInfo, Goal).

Inside the then part I think it would be better to throw an exception.
I know it should never happen, but oneday we might switch to a
non-classical logic or something.

I suggest adding a new predicate to private_builtin which takes a string and
throws it.

> +goal_expr_add_heap_ops(if_then_else(A, Cond0, Then0, Else0, E), GoalInfo,
> +		Goal - GoalInfo) -->
> +	goal_add_heap_ops(Cond0, Cond),
> +	goal_add_heap_ops(Then0, Then),
> +	goal_add_heap_ops(Else0, Else1),
> +	%
> +	% Save the heap pointer so that we can
> +	% restore it if the condition fails.
> +	%
> +	new_saved_hp_var(SavedHeapPointerVar),
> +	{ goal_info_get_context(GoalInfo, Context) },
> +	gen_mark_hp(SavedHeapPointerVar, Context, MarkHeapPointerGoal),
> +	%
> +	% Generate code to restore the heap pointer,
> +	% and insert that code at the start of the Else branch.
> +	%
> +	gen_restore_hp(SavedHeapPointerVar, Context, RestoreHeapPointerGoal),
> +	{ Else1 = _ - Else1GoalInfo },
> +	{ Else = conj([RestoreHeapPointerGoal, Else1]) - Else1GoalInfo },
> +	{ IfThenElse = if_then_else(A, Cond, Then, Else, E) - GoalInfo },
> +	{ Goal = conj([MarkHeapPointerGoal, IfThenElse]) }.
> +
Isn't it a condition of the HLDS that all the conjunctions have been
flattened?

> +goal_expr_add_heap_ops(PragmaForeign, GoalInfo, Goal) -->
> +	{ PragmaForeign = foreign_proc(_,_,_,_,_,_,Impl) },
> +	( { Impl = nondet(_,_,_,_,_,_,_,_,_) } ->
> +		% XXX Implementing heap reclamation for nondet pragma
> +		% foreign_code via transformation is difficult,
> +		% because there's nowhere in the HLDS pragma_foreign_code
> +		% goal where we can insert the heap reclamation operations.
> +		% For now, we don't support this.
> +		% Instead, we just generate a call to a procedure which
> +		% will at runtime call error/1 with an appropriate
> +		% "Sorry, not implemented" error message.
> +		ModuleInfo =^ module_info,
> +		{ goal_info_get_context(GoalInfo, Context) },
> +		{ generate_call("reclaim_heap_nondet_pragma_foreign_code",
> +			[], det, no, [], ModuleInfo, Context,
> +			SorryNotImplementedCode) },
> +		{ Goal = SorryNotImplementedCode }
> +	;
> +		{ Goal = PragmaForeign - GoalInfo }
> +	).
Do you have any plans to implement this?

> +:- pred disj_add_heap_ops(hlds_goals::in, bool::in, prog_var::in,
> +		hlds_goals::out, heap_ops_info::in, heap_ops_info::out) is det.
> +
> +disj_add_heap_ops([], _, _, []) --> [].
> +disj_add_heap_ops([Goal0 | Goals0], IsFirstBranch, 
> +		SavedHeapPointerVar, [Goal | Goals]) -->
> +	{ Goal0 = _ - GoalInfo0 },
> +	{ goal_info_get_context(GoalInfo0, Context) },
> +	%
> +	% First reset the heap pointer to
> +	% undo the effects of any earlier branches
> +	%
> +	( { IsFirstBranch = yes } ->
> +		{ UndoList = [] }
> +	;
> +		gen_restore_hp(SavedHeapPointerVar, Context,
> +			RestoreHeapPointerGoal),
> +		{ UndoList = [RestoreHeapPointerGoal] }
> +	),
> +	%
> +	% Then execute the disjunct goal
> +	%
> +	goal_add_heap_ops(Goal0, Goal1),
> +	%
> +	% Package up the stuff we built earlier.
> +	%
> +	{ Goal1 = _ - GoalInfo1 },
> +	{ conj_list_to_goal(UndoList ++ [Goal1], GoalInfo1, Goal) },
> +
> +	% Recursively handle the remaining disjuncts
> +	disj_add_heap_ops(Goals0, no, SavedHeapPointerVar, Goals).
> +
> +%-----------------------------------------------------------------------------%

> +% XXX copied from table_gen.m
> +
> +:- pred generate_call(string::in, list(prog_var)::in, determinism::in,
> +	maybe(goal_feature)::in, assoc_list(prog_var, inst)::in,
> +	module_info::in, term__context::in, hlds_goal::out) is det.
> +
I would suggest putting this into a new module then.
Maybe we need a hlds_util module?

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