for review: new method of handling failures, part 1 of 6

[Zoltan Somogyi]

This should be reviewed by Tom *and* by Fergus.

Note that when this change is installed, it will require the recompilation
of all workspaces. Workspaces that do not do a cvs update of this change
when it is installed (which I expect will include the entire alias branch)
will also have to adapt the steps given below.

The diffs to ite_gen.m, disj_gen.m, code_gen.m and code_info.m are
bigger than the files themselves (in the case of code_info.m at least,
that is saying something!). While I include the diffs so that you can see
what has changed, I also include the new files in their entirety.

Estimated hours taken: 240

Implement new methods of handling failures and the end points of branched
control structures.

compiler/notes/failure.html:
	Fix an omission about the handling of resume_is_known in if-then-elses.
	(This omission lead to a bug in the implementation.)

	Optimize cuts across multi goals when curfr is known to be equal
	to maxfr.

	Clarify the wording in several places.

compiler/code_info.m:
	Completely rewrite the methods for handling failure.

	Separate the fields of code_info into three classes: those which
	do not change after initialization, those which record state that
	depends on where in the HLDS goal we are, and those which contain
	persistent data such as label and cell counters.

	Rename grab_code_info and slap_code_info as remember_position
	and reset_to_position, and add a wrapper around the remembered
	code_info to make it harder to make mistakes in its use.
	(Only the location-dependent fields of the remembered code_info
	are used, but putting only them into a separate data structure would
	result in more, not less, memory being allocated.)

	Gather the predicates that deal with handling branched control
	structures into a submodule.

	Reorder the declarations and definitions of access predicates
	to conform to the new order of fields.

compiler/code_gen.m:
	Replace code_gen__generate_{det,semi,non}_goal_2 with a single
	predicate, since for most HLDS constructs the code here is the same
	anyway (the called preds check the code model when needed).

	Move classification of the various kinds of unifications to unify_gen,
	since that is where it belongs.

	Move responsibility for initializing the code generator's trace
	info to code_info.

	Move the generation of code for negations to ite_gen, since the
	handling of negations is a cut-down version of the handling of
	negations. This should make the required double maintenance easier,
	and more likely to happen.

compiler/disj_gen.m:
compiler/ite_gen.m:
	These are the two modules that handle most failures; they have
	undergone a significant rewrite. As part of this rewrite, factor
	out the remaining common code between model_non and model_{det,semi}
	goals.

compiler/unify_gen.m:
	Move classification of the various kinds of unifications here from
	code_gen. This allows us to keep several previously exported
	predicates private.

compiler/call_gen.m:
	Factor out some code that was common to ordinary calls, higher order
	calls and method calls. Move the common code that checks whether
	we are doing tracing to trace.m.

	Replace call_gen__generate_{det,semi,nondet}_builtin with a single
	predicate.

	Delete the commented out call_gen__generate_complicated_unify,
	since it will never be needed and in any case suffered from
	significant code rot.

compiler/llds.m:
	Change the mkframe instruction so that depending on one of its
	arguments, it can create either ordinary frames, or the cut-down
	frames used by the new failure handling algorithm (they have only
	three fixed fields: prevfr, redoip and redofr).

compiler/llds_out.m:
	Emit a #define MR_USE_REDOFR before including mercury_imp.h, to
	tell the runtime we are using the new failure handling scheme.
	This effectively changes the grade of the compiled module.

compiler/trace.m:
	Change the way trace info is initialized to fit in with the new
	requirements of code_info.m.

	Move the "are we tracing" check from the callers to the implementation
	of trace__prepare_for_call.

compiler/*.m:
	Minor changes in accordance with the major ones above.

compiler/options.m:
	Introduce a new option, allow_hijacks, which is set to "yes" by
	default. It is not used yet, but the idea is that when it is set to no,
	the code generator will not generate code that hijacks the nondet
	stack frame of another procedure invocation; instead, it will create
	a new temporary nondet stack frame. If the current procedure is
	model_non, it will have three fields: prevfr, redoip and redofr.
	If the current procedure is model_det or model_semi, it will have
	a fourth field that is set to the value of MR_sp. The idea is that
	the runtime system, which will be able to distinguish between
	ordinary frames (whose size is at least 5 words), 3-word and 4-word
	temporary frames, will now be able to use the redofr slots of
	all three kinds of frames and the fourth slot values of 4-word
	temporary frames as the addresses relative to which framevars
	and detstackvars respectively ought to be offset in stack layouts.

compiler/handle_options.m:
	Turn off allow_hijacks if the gc method is accurate.

runtime/mercury_stacks.h:
	Provide alternative definitions for the nondet stack handling
	macros when we are using the nondet stack handling discipline.
	Define a new macro for creating temp nondet frames.

runtime/mercury_stack_trace.[ch]:
	Add a new function to print a dump of the fixed elements nondet stack,
	for debugging my changes. (The dump does not include variable values.)

runtime/mercury_trace_internal.c:
	Add a new undocumented command "D" for dumping the nondet stack
	(users should not know about this command, since the output is
	intelligible only to implementors).

	Add a new command "toggle_echo" that can cause the debugger to echo
	all commands. When the input to the debugger is redirected, this
	echo causes the output of the session to be much more readable.

runtime/mercury_wrapper.c:
	Save the address of the artificial bottom nondet stack frame,
	so that the new function in mercury_stack_trace.c can find out
	where to stop.

runtime/mercury_engine.c:
runtime/mercury_wrapper.c:
	Put MR_STACK_TRACE_THIS_MODULE at the tops of these modules, so that
	the labels they define (e.g. do_fail and global_success) are registered
	in the label table when their module initialization functions are
	called. This is necessary for a meaningful nondet stack dump.

runtime/mercury_grade.h:
	Add a new component to the grade string that specifies whether
	the code was compiled with the old or the new method of handling
	the nondet stack. This is important, because modules compiled
	with different nondet stack handling disciplines are not compatible.
	This component depends on whether MR_USE_REDOFR is defined or not.

runtime/mercury_imp.h:
	If MR_DISABLE_REDOFR is defined, undefine off MR_USE_REDOFR before
	including mercury_grade.h. This is to allow people to continue
	working on un-updated workspaces after this change is installed;
	they should put "EXTRA_CFLAGS = -DMR_DISABLE_REDOFR" into
	Mmake.stage.params. (This way their stage1 will use the new method
	of handling failure, while their stage2 2&3 will use the old one.)

	This change should be undone once all our workspaces have switched
	over to the new failure handling method.

tools/bootcheck:
	Always copy the runtime directory, since this is required when the
	stage1 and stage2 compilers have different grades, and differences
	in failure handling methods lead to differences in grades.

	This change should be undone once all our workspaces have switched
	over to the new nondet stack method. (Until then, any bootcheck
	in a directory that has not done a cvs update of this change will fail
	if it does not copy the runtime and define MR_DISABLE_REDOFR.)

tests/hard_coded/cut_test.{m,exp}:
	A new test case to tickle the various ways of handling cuts in the
	new code generator.

tests/hard_coded/Mmakefile:
	Enable the new test case.

Zoltan.

::::::::::::::
code_info.m
::::::::::::::
%---------------------------------------------------------------------------%
% Copyright (C) 1994-1998 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.
%---------------------------------------------------------------------------%
%
% File: code_info.m
%
% Main authors: conway, zs.
%
% This file defines the code_info type and various operations on it.
% The code_info structure is the 'state' of the code generator.
%
% This file is organized into nine submodules:
%
%	- the code_info structure and its access predicates
%	- simple wrappers around access predicates
%	- handling branched control structures
%	- handling failure continuations
%	- handling liveness issues
%	- saving and restoring heap pointers, trail tickets etc
%	- interfacing to code_exprn
%	- managing the info required by garbage collection and value numbering
%	- managing stack slots
%
%---------------------------------------------------------------------------%

:- module code_info.

:- interface.

:- import_module hlds_module, hlds_pred, hlds_goal, llds, instmap, trace.
:- import_module continuation_info, prog_data, hlds_data, globals.

:- import_module bool, set, varset, list, map, term, std_util, assoc_list.

:- implementation.

:- import_module code_util, code_exprn, prog_out.
:- import_module arg_info, type_util, mode_util, options.

:- import_module set, varset, stack.
:- import_module string, require, char, bimap, tree, int.
:- import_module unsafe, io.

%---------------------------------------------------------------------------%

	% Submodule for the code_info type and its access predicates.
	%
	% This submodule has the following components:
	%
	%	declarations for exported access predicates
	%	declarations for non-exported access predicates
	%	the definition of the type and the init predicate
	%	the definition of the get access predicates
	%	the definition of the set access predicates
	%
	% Please keep the order of mention of the various fields
	% consistent in each of these five components.

:- interface.

:- type code_info.

		% Create a new code_info structure.
:- pred code_info__init(varset, set(var), stack_slots, bool, globals,
	pred_id, proc_id, proc_info, instmap, follow_vars, module_info,
	int, resume_point_info, code_info).
:- mode code_info__init(in, in, in, in, in, in, in, in, in, in, in, in,
	out, out) is det.

		% Get the globals table.
:- pred code_info__get_globals(globals, code_info, code_info).
:- mode code_info__get_globals(out, in, out) is det.

		% Get the HLDS of the entire module.
:- pred code_info__get_module_info(module_info, code_info, code_info).
:- mode code_info__get_module_info(out, in, out) is det.

		% Get the id of the predicate we are generating code for.
:- pred code_info__get_pred_id(pred_id, code_info, code_info).
:- mode code_info__get_pred_id(out, in, out) is det.

		% Get the id of the procedure we are generating code for.
:- pred code_info__get_proc_id(proc_id, code_info, code_info).
:- mode code_info__get_proc_id(out, in, out) is det.

		% Get the HLDS of the procedure we are generating code for.
:- pred code_info__get_proc_info(proc_info, code_info, code_info).
:- mode code_info__get_proc_info(out, in, out) is det.

		% Get the variables for the current procedure.
:- pred code_info__get_varset(varset, code_info, code_info).
:- mode code_info__get_varset(out, in, out) is det.

:- pred code_info__get_maybe_trace_info(maybe(trace_info),
	code_info, code_info).
:- mode code_info__get_maybe_trace_info(out, in, out) is det.

		% Get the set of currently forward-live variables.
:- pred code_info__get_forward_live_vars(set(var), code_info, code_info).
:- mode code_info__get_forward_live_vars(out, in, out) is det.

		% Set the set of currently forward-live variables.
:- pred code_info__set_forward_live_vars(set(var), code_info, code_info).
:- mode code_info__set_forward_live_vars(in, in, out) is det.

		% Get the table mapping variables to the current
		% instantiation states.
:- pred code_info__get_instmap(instmap, code_info, code_info).
:- mode code_info__get_instmap(out, in, out) is det.

		% Set the table mapping variables to the current
		% instantiation states.
:- pred code_info__set_instmap(instmap, code_info, code_info).
:- mode code_info__set_instmap(in, in, out) is det.

:- pred code_info__get_cell_count(int, code_info, code_info).
:- mode code_info__get_cell_count(out, in, out) is det.

		% Get the flag that indicates whether succip is used or not.
:- pred code_info__get_succip_used(bool, code_info, code_info).
:- mode code_info__get_succip_used(out, in, out) is det.

:- pred code_info__get_layout_info(map(label, internal_layout_info), 
	code_info, code_info).
:- mode code_info__get_layout_info(out, in, out) is det.

%---------------------------------------------------------------------------%

:- implementation.

:- pred code_info__get_var_slot_count(int, code_info, code_info).
:- mode code_info__get_var_slot_count(out, in, out) is det.

:- pred code_info__set_maybe_trace_info(maybe(trace_info),
	code_info, code_info).
:- mode code_info__set_maybe_trace_info(in, in, out) is det.

:- pred code_info__get_zombies(set(var), code_info, code_info).
:- mode code_info__get_zombies(out, in, out) is det.

:- pred code_info__set_zombies(set(var), code_info, code_info).
:- mode code_info__set_zombies(in, in, out) is det.

:- pred code_info__get_exprn_info(exprn_info, code_info, code_info).
:- mode code_info__get_exprn_info(out, in, out) is det.

:- pred code_info__set_exprn_info(exprn_info, code_info, code_info).
:- mode code_info__set_exprn_info(in, in, out) is det.

:- pred code_info__get_temps_in_use(map(lval, slot_contents),
	code_info, code_info).
:- mode code_info__get_temps_in_use(out, in, out) is det.

:- pred code_info__set_temps_in_use(map(lval, slot_contents),
	code_info, code_info).
:- mode code_info__set_temps_in_use(in, in, out) is det.

:- pred code_info__get_fail_info(fail_info, code_info, code_info).
:- mode code_info__get_fail_info(out, in, out) is det.

:- pred code_info__set_fail_info(fail_info, code_info, code_info).
:- mode code_info__set_fail_info(in, in, out) is det.

:- pred code_info__get_label_count(int, code_info, code_info).
:- mode code_info__get_label_count(out, in, out) is det.

:- pred code_info__set_label_count(int, code_info, code_info).
:- mode code_info__set_label_count(in, in, out) is det.

:- pred code_info__set_cell_count(int, code_info, code_info).
:- mode code_info__set_cell_count(in, in, out) is det.

:- pred code_info__set_succip_used(bool, code_info, code_info).
:- mode code_info__set_succip_used(in, in, out) is det.

:- pred code_info__set_layout_info(map(label, internal_layout_info), 
	code_info, code_info).
:- mode code_info__set_layout_info(in, in, out) is det.

:- pred code_info__get_max_temp_slot_count(int, code_info, code_info).
:- mode code_info__get_max_temp_slot_count(out, in, out) is det.

:- pred code_info__set_max_temp_slot_count(int, code_info, code_info).
:- mode code_info__set_max_temp_slot_count(in, in, out) is det.

:- pred code_info__get_avail_temp_slots(set(lval), code_info, code_info).
:- mode code_info__get_avail_temp_slots(out, in, out) is det.

:- pred code_info__set_avail_temp_slots(set(lval), code_info, code_info).
:- mode code_info__set_avail_temp_slots(in, in, out) is det.

%---------------------------------------------------------------------------%

	% The code_info structure has three groups of fields.
	%
	% Some fields are static; they are set when the code_info structure
	% is initialized, and never changed afterwards.
	%
	% Some fields record information about the state of the code generator
	% at a particular location in the HLDS code of the current procedure.
	% At the start of the branched control structure, the code generator
	% remembers the values of these fields, and starts generating code
	% for each branch from the same location-dependent state.
	%
	% Some fields record persistent information that does not depend
	% on a code location. Updates to these fields must remain effective
	% even when the code generator resets its location-dependent state.

:- type code_info	--->
	code_info(
		% STATIC fields
		globals,	% For the code generation options.
		module_info,	% The module_info structure - you just
				% never know when you might need it.
		pred_id,	% The id of the current predicate.
		proc_id,	% The id of the current procedure.
		proc_info,	% The proc_info for the this procedure.
		varset,		% The variables in this procedure.
		int,		% The number of stack slots allocated.
				% for storing variables.
				% (Some extra stack slots are used
				% for saving and restoring registers.)
		maybe(trace_info),
				% Information about which stack slots
				% the call sequence number and depth
				% are stored, provided tracing is
				% switched on.

		% LOCATION DEPENDENT fields
		set(var),	% Variables that are forward live
				% after this goal.
 		instmap,	% Current insts of the live variables.
		set(var),	% Zombie variables; variables that are not
				% forward live but which are protected by
				% an enclosing resume point.
		exprn_info,	% A map storing the information about
				% the status of each known variable.
				% (Known vars = forward live vars + zombies)
		map(lval, slot_contents),
				% The temp locations in use on the stack
				% and what they contain (for gc).
		fail_info,	% Information about how to manage failures.

		% PERSISTENT fields
 		int,		% Counter for the local labels used
				% by this procedure.
		int,		% Counter for cells in this proc.
		bool,		% do we need to store succip?
		map(label, internal_layout_info),
				% Information on which values
				% are live and where at which labels,
				% for tracing. Accurate gc 
		int,		% The maximum number of extra
				% temporary stackslots that have been
				% used during the procedure.
		set(lval)	% Stack variables that have been used
				% for temporaries and are now again
				% available for reuse.
	).

%---------------------------------------------------------------------------%

code_info__init(Varset, Liveness, StackSlots, SaveSuccip, Globals,
		PredId, ProcId, ProcInfo, Instmap, FollowVars,
		ModuleInfo, CellCount, ResumePoint, CodeInfo) :-
	proc_info_headvars(ProcInfo, HeadVars),
	proc_info_arg_info(ProcInfo, ArgInfos),
	assoc_list__from_corresponding_lists(HeadVars, ArgInfos, Args),
	arg_info__build_input_arg_list(Args, ArgList),
	globals__get_options(Globals, Options),
	code_exprn__init_state(ArgList, Varset, StackSlots, FollowVars,
		Options, ExprnInfo),
	stack__init(ResumePoints),
	DummyFailInfo = fail_info(ResumePoints, resume_point_unknown,
		may_be_different),
	set__init(AvailSlots),
	map__init(TempsInUse),
	set__init(Zombies),
	map__init(LayoutMap),
	code_info__max_var_slot(StackSlots, VarSlotCount0),
	proc_info_interface_code_model(ProcInfo, CodeModel),
	(
		CodeModel = model_non
	->
		VarSlotCount is VarSlotCount0 + 1
	;
		VarSlotCount = VarSlotCount0
	),
	CodeInfo0 = code_info(
		Globals,
		ModuleInfo,
		PredId,
		ProcId,
		ProcInfo,
		Varset,
		VarSlotCount,
		no,

		Liveness,
		Instmap,
		Zombies,
		ExprnInfo,
		TempsInUse,
		DummyFailInfo,		% code_info__init_fail_info
					% will override this dummy value
		0,
		CellCount,
		SaveSuccip,
		LayoutMap,
		0,
		AvailSlots
	),
	globals__get_trace_level(Globals, TraceLevel),
	code_info__init_maybe_trace_info(TraceLevel, ModuleInfo, ProcInfo,
		MaybeFailVars, CodeInfo0, CodeInfo1),
	code_info__init_fail_info(CodeModel, MaybeFailVars, ResumePoint,
		CodeInfo1, CodeInfo).

:- pred code_info__init_maybe_trace_info(trace_level, module_info, proc_info,
	maybe(set(var)), code_info, code_info).
:- mode code_info__init_maybe_trace_info(in, in, in, out, in, out) is det.

code_info__init_maybe_trace_info(TraceLevel, ModuleInfo, ProcInfo,
		MaybeFailVars) -->
	( { trace_level_trace_interface(TraceLevel, yes) } ->
		trace__setup(TraceLevel, TraceInfo),
		code_info__set_maybe_trace_info(yes(TraceInfo)),
		{ trace__fail_vars(ModuleInfo, ProcInfo, FailVars) },
		{ MaybeFailVars = yes(FailVars) }
	;
		{ MaybeFailVars = no }
	).

%---------------------------------------------------------------------------%

code_info__get_globals(SA, CI, CI) :-
	CI  = code_info(SA, _, _, _, _, _, _, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_module_info(SB, CI, CI) :-
	CI  = code_info(_, SB, _, _, _, _, _, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_pred_id(SC, CI, CI) :-
	CI  = code_info(_, _, SC, _, _, _, _, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_proc_id(SD, CI, CI) :-
	CI  = code_info(_, _, _, SD, _, _, _, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_proc_info(SE, CI, CI) :-
	CI  = code_info(_, _, _, _, SE, _, _, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_varset(SF, CI, CI) :-
	CI  = code_info(_, _, _, _, _, SF, _, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_var_slot_count(SG, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, SG, _,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_maybe_trace_info(SH, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, SH,
		_, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_forward_live_vars(LA, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		LA, _, _, _, _, _, _, _, _, _, _, _).

code_info__get_instmap(LB, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, LB, _, _, _, _, _, _, _, _, _, _).

code_info__get_zombies(LC, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, LC, _, _, _, _, _, _, _, _, _).

code_info__get_exprn_info(LD, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, LD, _, _, _, _, _, _, _, _).

code_info__get_temps_in_use(LE, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, LE, _, _, _, _, _, _, _).

code_info__get_fail_info(LF, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, LF, _, _, _, _, _, _).

code_info__get_label_count(PA, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, _, PA, _, _, _, _, _).

code_info__get_cell_count(PB, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, _, _, PB, _, _, _, _).

code_info__get_succip_used(PC, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, _, _, _, PC, _, _, _).

code_info__get_layout_info(PD, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, _, _, _, _, PD, _, _).

code_info__get_max_temp_slot_count(PE, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, _, _, _, _, _, PE, _).

code_info__get_avail_temp_slots(PF, CI, CI) :-
	CI  = code_info(_, _, _, _, _, _, _, _,
		_, _, _, _, _, _, _, _, _, _, _, PF).

%---------------------------------------------------------------------------%

code_info__set_maybe_trace_info(SH, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, _,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_forward_live_vars(LA, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		_,  LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_instmap(LB, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, _,  LC, LD, LE, LF, PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_zombies(LC, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, _,  LD, LE, LF, PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_exprn_info(LD, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, _,  LE, LF, PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_temps_in_use(LE, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, _,  LF, PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_fail_info(LF, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, _,  PA, PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_label_count(PA, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, _,  PB, PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_cell_count(PB, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, _,  PC, PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_succip_used(PC, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, _,  PD, PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_layout_info(PD, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, _,  PE, PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_max_temp_slot_count(PE, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, _,  PF),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__set_avail_temp_slots(PF, CI0, CI) :-
	CI0 = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, _ ),
	CI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

	% Submodule for simple wrappers around access predicates.

:- interface.

		% Get the hlds mapping from variables to stack slots
:- pred code_info__get_stack_slots(stack_slots, code_info, code_info).
:- mode code_info__get_stack_slots(out, in, out) is det.

		% Get the table that contains advice about where
		% variables should be put.
:- pred code_info__get_follow_vars(follow_vars, code_info, code_info).
:- mode code_info__get_follow_vars(out, in, out) is det.

		% Set the table that contains advice about where
		% variables should be put.
:- pred code_info__set_follow_vars(follow_vars, code_info, code_info).
:- mode code_info__set_follow_vars(in, in, out) is det.

	% code_info__pre_goal_update(GoalInfo, Atomic, OldCodeInfo, NewCodeInfo)
	% updates OldCodeInfo to produce NewCodeInfo with the changes
	% specified by GoalInfo.
:- pred code_info__pre_goal_update(hlds_goal_info, bool, code_info, code_info).
:- mode code_info__pre_goal_update(in, in, in, out) is det.

	% code_info__post_goal_update(GoalInfo, OldCodeInfo, NewCodeInfo)
	% updates OldCodeInfo to produce NewCodeInfo with the changes described
	% by GoalInfo.
:- pred code_info__post_goal_update(hlds_goal_info, code_info, code_info).
:- mode code_info__post_goal_update(in, in, out) is det.

	% Find out the type of the given variable.
:- pred code_info__variable_type(var, type, code_info, code_info).
:- mode code_info__variable_type(in, out, in, out) is det.

:- pred code_info__lookup_type_defn(type, hlds_type_defn,
	code_info, code_info).
:- mode code_info__lookup_type_defn(in, out, in, out) is det.

	% Given a list of type variables, find the lvals where the
	% corresponding type_infos and typeclass_infos are being stored.
:- pred code_info__find_type_infos(list(var), assoc_list(var, lval),
	code_info, code_info).
:- mode code_info__find_type_infos(in, out, in, out) is det.

	% Given a constructor id, and a variable (so that we can work out the
	% type of the constructor), determine correct tag (representation)
	% of that constructor.
:- pred code_info__cons_id_to_tag(var, cons_id, cons_tag, code_info, code_info).
:- mode code_info__cons_id_to_tag(in, in, out, in, out) is det.

	% Get the code model of the current procedure.
:- pred code_info__get_proc_model(code_model, code_info, code_info).
:- mode code_info__get_proc_model(out, in, out) is det.

:- pred code_info__get_headvars(list(var), code_info, code_info).
:- mode code_info__get_headvars(out, in, out) is det.

	% Get the call argument information for the current procedure
:- pred code_info__get_arginfo(list(arg_info), code_info, code_info).
:- mode code_info__get_arginfo(out, in, out) is det.

	% Get the call argument info for a given mode of a given predicate
:- pred code_info__get_pred_proc_arginfo(pred_id, proc_id, list(arg_info),
	code_info, code_info).
:- mode code_info__get_pred_proc_arginfo(in, in, out, in, out) is det.

:- pred code_info__variable_to_string(var, string, code_info, code_info).
:- mode code_info__variable_to_string(in, out, in, out) is det.

:- pred code_info__apply_instmap_delta(instmap_delta, code_info, code_info).
:- mode code_info__apply_instmap_delta(in, in, out) is det.

	% Create a code address which holds the address of the specified
	% procedure.
	% The fourth argument should be `no' if the the caller wants the
	% returned address to be valid from everywhere in the program.
	% If being valid from within the current procedure is enough,
	% this argument should be `yes' wrapped around the value of the
	% --procs-per-c-function option and the current procedure id.
	% Using an address that is only valid from within the current
	% procedure may make jumps more efficient.
	% XXX
:- pred code_info__make_entry_label(module_info, pred_id, proc_id, bool,
	code_addr, code_info, code_info).
:- mode code_info__make_entry_label(in, in, in, in, out, in, out) is det.

	% Generate the next local label in sequence.
:- pred code_info__get_next_label(label, code_info, code_info).
:- mode code_info__get_next_label(out, in, out) is det.

	% Generate the next cell number in sequence.
:- pred code_info__get_next_cell_number(int, code_info, code_info).
:- mode code_info__get_next_cell_number(out, in, out) is det.

:- pred code_info__succip_is_used(code_info, code_info).
:- mode code_info__succip_is_used(in, out) is det.

:- pred code_info__add_trace_layout_for_label(label, layout_label_info,
	code_info, code_info).
:- mode code_info__add_trace_layout_for_label(in, in, in, out) is det.

%---------------------------------------------------------------------------%

:- implementation.

code_info__get_stack_slots(StackSlots, CI, CI) :-
	code_info__get_exprn_info(ExprnInfo, CI, _),
	code_exprn__get_stack_slots(StackSlots, ExprnInfo, _).

code_info__get_follow_vars(FollowVars, CI, CI) :-
	code_info__get_exprn_info(ExprnInfo, CI, _),
	code_exprn__get_follow_vars(FollowVars, ExprnInfo, _).

code_info__set_follow_vars(FollowVars, CI0, CI) :-
	code_info__get_exprn_info(ExprnInfo0, CI0, _),
	code_exprn__set_follow_vars(FollowVars, ExprnInfo0, ExprnInfo),
	code_info__set_exprn_info(ExprnInfo, CI0, CI).

%-----------------------------------------------------------------------------%

	% Update the code info structure to be consistent
	% immediately prior to generating a goal
code_info__pre_goal_update(GoalInfo, Atomic) -->
	% The liveness pass puts resume_point annotations on some kinds
	% of goals. The parts of the code generator that handle those kinds
	% of goals should handle the resume point annotation as well;
	% when they do, they remove the annotation. The following code
	% is a sanity check to make sure that this has in fact been done.
	{ goal_info_get_resume_point(GoalInfo, ResumePoint) },
	(
		{ ResumePoint = no_resume_point }
	;
		{ ResumePoint = resume_point(_, _) },
		{ error("pre_goal_update with resume point") }
	),
	{ goal_info_get_follow_vars(GoalInfo, MaybeFollowVars) },
	(
		{ MaybeFollowVars = yes(FollowVars) },
		code_info__set_follow_vars(FollowVars)
	;
		{ MaybeFollowVars = no }
	),
	% note: we must be careful to apply deaths before births
	{ goal_info_get_pre_deaths(GoalInfo, PreDeaths) },
	code_info__rem_forward_live_vars(PreDeaths),
	code_info__make_vars_forward_dead(PreDeaths),
	{ goal_info_get_pre_births(GoalInfo, PreBirths) },
	code_info__add_forward_live_vars(PreBirths),
	( { Atomic = yes } ->
		{ goal_info_get_post_deaths(GoalInfo, PostDeaths) },
		code_info__rem_forward_live_vars(PostDeaths)
	;
		[]
	).

	% Update the code info structure to be consistent
	% immediately after generating a goal
code_info__post_goal_update(GoalInfo) -->
	% note: we must be careful to apply deaths before births
	{ goal_info_get_post_deaths(GoalInfo, PostDeaths) },
	code_info__rem_forward_live_vars(PostDeaths),
	code_info__make_vars_forward_dead(PostDeaths),
	{ goal_info_get_post_births(GoalInfo, PostBirths) },
	code_info__add_forward_live_vars(PostBirths),
	code_info__make_vars_forward_live(PostBirths),
	{ goal_info_get_instmap_delta(GoalInfo, InstMapDelta) },
	code_info__apply_instmap_delta(InstMapDelta).

%---------------------------------------------------------------------------%

code_info__variable_type(Var, Type) -->
	code_info__get_proc_info(ProcInfo),
	{ proc_info_vartypes(ProcInfo, VarTypes) },
	{ map__lookup(VarTypes, Var, Type) }.

code_info__lookup_type_defn(Type, TypeDefn) -->
	code_info__get_module_info(ModuleInfo),
	{ type_to_type_id(Type, TypeIdPrime, _) ->
		TypeId = TypeIdPrime
	;
		error("unknown type in code_aux__lookup_type_defn")
	},
	{ module_info_types(ModuleInfo, TypeTable) },
	{ map__lookup(TypeTable, TypeId, TypeDefn) }.

code_info__find_type_infos([], []) --> [].
code_info__find_type_infos([TVar | TVars], [TVar - Lval | Lvals]) -->
	code_info__get_proc_info(ProcInfo),
	{ proc_info_typeinfo_varmap(ProcInfo, TypeInfoMap) },
	{
		map__search(TypeInfoMap, TVar, Locn)
	->
		type_info_locn_var(Locn, Var)
	;
		error("cannot find var for type variable")
	},
	{ proc_info_stack_slots(ProcInfo, StackSlots) },
	(
		{ map__search(StackSlots, Var, Lval0) }
	->
		{ Lval = Lval0 }
	;
		code_info__variable_to_string(Var, VarString),
		{ string__format("code_info__find_type_infos: can't find lval for type_info var %s",
			[s(VarString)], ErrStr) },
		{ error(ErrStr) }
	),
	code_info__find_type_infos(TVars, Lvals).

code_info__cons_id_to_tag(Var, ConsId, ConsTag) -->
	code_info__variable_type(Var, Type),
	code_info__get_module_info(ModuleInfo),
	{ code_util__cons_id_to_tag(ConsId, Type, ModuleInfo, ConsTag) }.

%---------------------------------------------------------------------------%

code_info__get_proc_model(CodeModel) -->
	code_info__get_proc_info(ProcInfo),
	{ proc_info_interface_code_model(ProcInfo, CodeModel) }.

code_info__get_headvars(HeadVars) -->
	code_info__get_module_info(ModuleInfo),
	code_info__get_pred_id(PredId),
	code_info__get_proc_id(ProcId),
	{ module_info_preds(ModuleInfo, Preds) },
	{ map__lookup(Preds, PredId, PredInfo) },
	{ pred_info_procedures(PredInfo, Procs) },
	{ map__lookup(Procs, ProcId, ProcInfo) },
	{ proc_info_headvars(ProcInfo, HeadVars) }.

code_info__get_arginfo(ArgInfo) -->
	code_info__get_pred_id(PredId),
	code_info__get_proc_id(ProcId),
	code_info__get_pred_proc_arginfo(PredId, ProcId, ArgInfo).

code_info__get_pred_proc_arginfo(PredId, ProcId, ArgInfo) -->
	code_info__get_module_info(ModuleInfo),
	{ module_info_pred_proc_info(ModuleInfo, PredId, ProcId, _, ProcInfo) },
	{ proc_info_arg_info(ProcInfo, ArgInfo) }.

%---------------------------------------------------------------------------%

:- pred code_info__current_resume_point_vars(set(var), code_info, code_info).
:- mode code_info__current_resume_point_vars(out, in, out) is det.

code_info__current_resume_point_vars(ResumeVars) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePointStack, _, _) },
	{ stack__top_det(ResumePointStack, ResumePointInfo) },
	{ code_info__pick_first_resume_point(ResumePointInfo, ResumeMap, _) },
	{ map__keys(ResumeMap, ResumeMapVarList) },
	{ set__list_to_set(ResumeMapVarList, ResumeVars) }.

%---------------------------------------------------------------------------%

code_info__variable_to_string(Var, Name) -->
	code_info__get_varset(Varset),
	{ varset__lookup_name(Varset, Var, Name) }.

code_info__apply_instmap_delta(Delta) -->
	code_info__get_instmap(InstMap0),
	{ instmap__apply_instmap_delta(InstMap0, Delta, InstMap) },
	code_info__set_instmap(InstMap).

%---------------------------------------------------------------------------%

code_info__make_entry_label(ModuleInfo, PredId, ProcId, Immed0, PredAddress) -->
	(
		{ Immed0 = no },
		{ Immed = no }
	;
		{ Immed0 = yes },
		code_info__get_globals(Globals),
		{ globals__lookup_int_option(Globals, procs_per_c_function,
			ProcsPerFunc) },
		code_info__get_pred_id(CurPredId),
		code_info__get_proc_id(CurProcId),
		{ Immed = yes(ProcsPerFunc - proc(CurPredId, CurProcId)) }
	),
	{ code_util__make_entry_label(ModuleInfo, PredId, ProcId, Immed,
		PredAddress) }.

code_info__get_next_label(Label) -->
	code_info__get_module_info(ModuleInfo),
	code_info__get_pred_id(PredId),
	code_info__get_proc_id(ProcId),
	code_info__get_label_count(N0),
	{ N is N0 + 1 },
	code_info__set_label_count(N),
	{ code_util__make_internal_label(ModuleInfo, PredId, ProcId, N,
		Label) }.

code_info__get_next_cell_number(N) -->
	code_info__get_cell_count(N0),
	{ N is N0 + 1 },
	code_info__set_cell_count(N).

code_info__succip_is_used -->
	code_info__set_succip_used(yes).

code_info__add_trace_layout_for_label(Label, LayoutInfo) -->
	code_info__get_layout_info(Internals0),
	{ map__search(Internals0, Label, Internal0) ->
		Internal0 = internal_layout_info(Exec0, Agc),
		( Exec0 = no ->
			true
		;
			error("adding trace layout for already known label")
		),
		Internal = internal_layout_info(yes(LayoutInfo), Agc),
		map__set(Internals0, Label, Internal, Internals)
	;
		Internal = internal_layout_info(yes(LayoutInfo), no),
		map__det_insert(Internals0, Label, Internal, Internals)
	},
	code_info__set_layout_info(Internals).

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

	% Submodule for handling branched control structures.

:- interface.

:- type position_info.
:- type branch_end_info.

:- type branch_end	==	maybe(branch_end_info).

:- pred code_info__remember_position(position_info, code_info, code_info).
:- mode code_info__remember_position(out, in, out) is det.

:- pred code_info__reset_to_position(position_info, code_info, code_info).
:- mode code_info__reset_to_position(in, in, out) is det.

:- pred code_info__generate_branch_end(store_map, branch_end, branch_end,
	code_tree, code_info, code_info).
:- mode code_info__generate_branch_end(in, in, out, out, in, out) is det.

:- pred code_info__after_all_branches(store_map, branch_end,
	code_info, code_info).
:- mode code_info__after_all_branches(in, in, in, out) is det.

:- implementation.

:- type position_info
	--->	position_info(
			code_info	% The code_info at a given position
					% in the code of the procedure.
		).

:- type branch_end_info
	--->	branch_end_info(
			code_info	% The code_info at the end of a branch.
		).

code_info__remember_position(position_info(C), C, C).

code_info__reset_to_position(position_info(PosCI), CurCI, NextCI) :-
		% The static fields in PosCI and CurCI should be identical.
	PosCI  = code_info(_,  _,  _,  _,  _,  _,  _,  _, 
		LA, LB, LC, LD, LE, LF, _,  _,  _,  _,  _,  _ ),
	CurCI  = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		_,  _,  _,  _,  _,  _,  PA, PB, PC, PD, PE, PF),
	NextCI = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF).

code_info__generate_branch_end(StoreMap, MaybeEnd0, MaybeEnd, Code) -->
	code_info__get_exprn_info(Exprn0),
	{ map__to_assoc_list(StoreMap, VarLocs) },
	{ code_exprn__place_vars(VarLocs, Code, Exprn0, Exprn) },
	code_info__set_exprn_info(Exprn),
	=(EndCodeInfo1),
	{
		MaybeEnd0 = no,
		EndCodeInfo = EndCodeInfo1
	;
		MaybeEnd0 = yes(branch_end_info(EndCodeInfo0)),

			% Make sure the left context we leave the
			% branched structure with is valid for all branches.
		code_info__get_fail_info(FailInfo0, EndCodeInfo0, _),
		code_info__get_fail_info(FailInfo1, EndCodeInfo1, _),
		FailInfo0 = fail_info(_, ResumeKnown0, CurfrMaxfr0),
		FailInfo1 = fail_info(R, ResumeKnown1, CurfrMaxfr1),
		(
			ResumeKnown0 = resume_point_known,
			ResumeKnown1 = resume_point_known
		->
			ResumeKnown = resume_point_known
		;
			ResumeKnown = resume_point_unknown
		),
		(
			CurfrMaxfr0 = must_be_equal,
			CurfrMaxfr1 = must_be_equal
		->
			CurfrMaxfr = must_be_equal
		;
			CurfrMaxfr = may_be_different
		),
		FailInfo = fail_info(R, ResumeKnown, CurfrMaxfr),
		code_info__set_fail_info(FailInfo, EndCodeInfo1, EndCodeInfo)
	},
	{ MaybeEnd = yes(branch_end_info(EndCodeInfo)) }.

code_info__after_all_branches(StoreMap, MaybeEnd, CI0, CI) :-
	(
		MaybeEnd = yes(BranchEnd),
		BranchEnd = branch_end_info(BranchEndCodeInfo),
		code_info__reset_to_position(position_info(BranchEndCodeInfo),
			CI0, CI1),
		code_info__remake_with_store_map(StoreMap, CI1, CI)
	;
		MaybeEnd = no,
		error("no branches in branched control structure")
	).

	% code_info__remake_with_store_map throws away the exprn_info data
	% structure, forgetting the current locations of all variables,
	% and rebuilds it from scratch based on the given store map.
	% The new exprn_info will know about only the variables present
	% in the store map, and will believe they are where the store map
	% says they are.

:- pred code_info__remake_with_store_map(store_map, code_info, code_info).
:- mode code_info__remake_with_store_map(in, in, out) is det.

code_info__remake_with_store_map(StoreMap) -->
	{ map__to_assoc_list(StoreMap, VarLvals) },
	{ code_info__fixup_lvallist(VarLvals, VarRvals) },
	code_info__get_exprn_info(Exprn0),
	{ code_exprn__reinit_state(VarRvals, Exprn0, Exprn) },
	code_info__set_exprn_info(Exprn).

:- pred code_info__fixup_lvallist(assoc_list(var, lval), assoc_list(var, rval)).
:- mode code_info__fixup_lvallist(in, out) is det.

code_info__fixup_lvallist([], []).
code_info__fixup_lvallist([V - L | Ls], [V - lval(L) | Rs]) :-
	code_info__fixup_lvallist(Ls, Rs).

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

	% Submodule for the handling of failure continuations.

:- interface.

:- type resume_map.

:- type resume_point_info.

:- type disj_hijack_info.

	% Save the values of any stack slots we may hijack,
	% and if necessary, set the redofr slot of the top frame
	% to point to this frame.

:- pred code_info__prepare_for_disj_hijack(code_model::in,
	disj_hijack_info::out, code_tree::out,
	code_info::in, code_info::out) is det.

:- pred code_info__undo_disj_hijack(disj_hijack_info::in,
	code_tree::out, code_info::in, code_info::out) is det.

:- type ite_hijack_info.

:- pred code_info__prepare_for_ite_hijack(code_model::in,
	ite_hijack_info::out, code_tree::out,
	code_info::in, code_info::out) is det.

:- pred code_info__maybe_push_temp_frame(code_model::in, bool::in,
	ite_hijack_info::in, lval::out, code_tree::out,
	code_info::in, code_info::out) is det.

:- pred code_info__ite_enter_then(ite_hijack_info::in, lval::in,
	code_tree::out, code_tree::out, code_info::in, code_info::out) is det.

:- type simple_neg_info.

:- pred code_info__enter_simple_neg(set(var)::in, hlds_goal_info::in, 
	simple_neg_info::out, code_info::in, code_info::out) is det.

:- pred code_info__leave_simple_neg(hlds_goal_info::in, simple_neg_info::in,
	code_info::in, code_info::out) is det.

	% Put the given resume point into effect, by pushing it on to
	% the resume point stack, and if necessary overriding the redoip
	% of the top frame.

:- pred code_info__effect_resume_point(resume_point_info::in, code_model::in,
	code_tree::out, code_info::in, code_info::out) is det.

:- pred code_info__top_resume_point(resume_point_info::out,
	code_info::in, code_info::out) is det.

	% We have just left a disjunction; we don't know what address
	% the following code will need to backtrack to.

:- pred code_info__set_resume_point_to_unknown(code_info::in, code_info::out)
	is det.

	% We have just returned a model_non call; we don't know what address
	% the following code will need to backtrack to, and there may now
	% be nondet frames on top of ours that do not have their redofr slots
	% pointing to our frame.

:- pred code_info__set_resume_point_and_frame_to_unknown(code_info::in,
	code_info::out) is det.

:- pred code_info__generate_failure(code_tree::out,
	code_info::in, code_info::out) is det.

:- pred code_info__fail_if_rval_is_false(rval::in, code_tree::out,
	code_info::in, code_info::out) is det.

:- pred code_info__failure_is_direct_branch(code_addr::out,
	code_info::in, code_info::out) is semidet.

:- pred code_info__may_use_nondet_tailcall(bool::out,
	code_info::in, code_info::out) is det.

	% Materialize the given variables into registers or stack slots.

:- pred code_info__produce_vars(set(var)::in, resume_map::out,
	code_tree::out, code_info::in, code_info::out) is det.

	% Put the variables needed in enclosing failure continuations
	% into their stack slots.

:- pred code_info__flush_resume_vars_to_stack(code_tree::out,
	code_info::in, code_info::out) is det.

	% Set up the resume_point_info structure.

:- pred code_info__make_resume_point(set(var)::in, resume_locs::in,
	resume_map::in, resume_point_info::out, code_info::in, code_info::out)
	is det.

	% Generate the code for a resume point.

:- pred code_info__generate_resume_point(resume_point_info::in,
	code_tree::out, code_info::in, code_info::out) is det.

:- pred code_info__resume_point_vars(resume_point_info::in, list(var)::out)
	is det.

:- pred code_info__resume_point_stack_addr(resume_point_info::in,
	code_addr::out) is det.

	% `generate_det_pre_commit' and `generate_det_commit' should be
	% called before and after generating the code for the multi goal
	% being cut across. If the goal succeeds, the `commit' will cut
	% any choice points generated in the goal.

:- type det_commit_info.

:- pred code_info__generate_det_pre_commit(det_commit_info::out,
	code_tree::out, code_info::in, code_info::out) is det.

:- pred code_info__generate_det_commit(det_commit_info::in,
	code_tree::out, code_info::in, code_info::out) is det.

	% `generate_semi_pre_commit' and `generate_semi_commit' should be
	% called before and after generating the code for the nondet goal
	% being cut across. If the goal succeeds, the `commit' will cut
	% any choice points generated in the goal.

:- type semi_commit_info.

:- pred code_info__generate_semi_pre_commit(semi_commit_info::out,
	code_tree::out, code_info::in, code_info::out) is det.

:- pred code_info__generate_semi_commit(semi_commit_info::in,
	code_tree::out, code_info::in, code_info::out) is det.

%---------------------------------------------------------------------------%

:- implementation.

:- type resume_point_known	--->	resume_point_known
				;	resume_point_unknown.

:- type curfr_vs_maxfr		--->	must_be_equal
				;	may_be_different.

:- type resume_map		==	map(var, set(rval)).

:- type resume_point_info
	--->	orig_only(resume_map, code_addr)
	;	stack_only(resume_map, code_addr)
	;	orig_and_stack(resume_map, code_addr, resume_map, code_addr)
	;	stack_and_orig(resume_map, code_addr, resume_map, code_addr).

:- type fail_info
	--->	fail_info(
			stack(resume_point_info),
			resume_point_known,
			curfr_vs_maxfr
		).

:- type disj_hijack_info
	--->	disj_no_hijack
	;	disj_quarter_hijack
	;	disj_half_hijack(
			lval		% the stack slot in which we saved
					% the value of the hijacked redoip
		)
	;	disj_full_hijack(
			lval,		% the stack slot in which we saved
					% the value of the hijacked redoip
			lval		% the stack slot in which we saved
					% the value of the hijacked redofr
		).

:- type ite_hijack_info
	--->	ite_no_hijack(
			resume_point_known
		)
	;	ite_quarter_hijack(
			resume_point_known
		)
	;	ite_half_hijack(
			resume_point_known,
			lval		% the stack slot in which we saved
					% the value of the hijacked redoip
		)
	;	ite_full_hijack(
			resume_point_known,
			lval,		% the stack slot in which we saved
					% the value of the hijacked redoip
			lval,		% the stack slot in which we saved
					% the value of the hijacked redofr
			lval		% the stack slot in which we saved
					% the value of maxfr
		).

:- type simple_neg_info		==	fail_info.

code_info__prepare_for_disj_hijack(CodeModel, HijackInfo, Code) -->
	( { CodeModel = model_non } ->
		code_info__get_fail_info(FailInfo),
		{ FailInfo = fail_info(_, ResumeKnown, CurfrMaxfr) },
		(
			{ CurfrMaxfr = may_be_different },
			code_info__acquire_temp_slot(lval(redoip(lval(maxfr))),
				RedoipSlot),
			code_info__acquire_temp_slot(lval(redofr(lval(maxfr))),
				RedofrSlot),
			{ HijackInfo = disj_full_hijack(RedoipSlot,
				RedofrSlot) },
			{ Code = node([
				assign(RedoipSlot, lval(redoip(lval(maxfr))))
					- "prepare for full disj hijack",
				assign(RedofrSlot, lval(redofr(lval(maxfr))))
					- "prepare for full disj hijack",
				assign(redofr(lval(maxfr)), lval(curfr))
					- "prepare for full disj hijack"
			]) }
		;
			{ CurfrMaxfr = must_be_equal },
			(
				{ ResumeKnown = resume_point_unknown },
				code_info__acquire_temp_slot(
					lval(redoip(lval(curfr))), RedoipSlot),
				{ HijackInfo = disj_half_hijack(RedoipSlot) },
				{ Code = node([
					assign(RedoipSlot,
						lval(redoip(lval(curfr))))
						- "prepare for half disj hijack"
				]) }
			;
				{ ResumeKnown = resume_point_known },
				{ HijackInfo = disj_quarter_hijack },
				{ Code = empty }
			)
		)
	;
		{ HijackInfo = disj_no_hijack },
		{ Code = empty }
	).

code_info__undo_disj_hijack(HijackInfo, Code) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePoints, ResumeKnown, CurfrMaxfr) },
	(
		{ HijackInfo = disj_full_hijack(RedoipSlot, RedofrSlot) },
		{ require(unify(CurfrMaxfr, may_be_different),
			"maxfr same as curfr in disj_full_hijack") },
		{ Code = node([
			assign(redoip(lval(maxfr)), lval(RedoipSlot))
				- "restore redoip for full disj hijack",
			assign(redofr(lval(maxfr)), lval(RedofrSlot))
				- "restore redofr for full disj hijack"
		]) }
	;
		{ HijackInfo = disj_half_hijack(RedoipSlot) },
		{ require(unify(ResumeKnown, resume_point_unknown),
			"resume point known in disj_half_hijack") },
		{ require(unify(CurfrMaxfr, must_be_equal),
			"maxfr may be different from curfr in disj_half_hijack") },
		{ Code = node([
			assign(redoip(lval(curfr)), lval(RedoipSlot))
				- "restore redoip for half disj hijack"
		]) }
	;
		{ HijackInfo = disj_quarter_hijack },
		{ require(unify(ResumeKnown, resume_point_known),
			"resume point not known in disj_quarter_hijack") },
		{ require(unify(CurfrMaxfr, must_be_equal),
			"maxfr may be different from curfr in disj_quarter_hijack") },
		{ stack__top_det(ResumePoints, ResumePoint) },
		{ code_info__pick_stack_resume_point(ResumePoint,
			_, StackLabel) },
		{ LabelConst = const(code_addr_const(StackLabel)) },
		{ Code = node([
			assign(redoip(lval(curfr)), LabelConst)
				- "restore redoip for quarter disj hijack"
		]) }
	;
		{ HijackInfo = disj_no_hijack },
		{ Code = empty }
	).

code_info__prepare_for_ite_hijack(EffCodeModel, HijackInfo, Code) -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(_ResumePoints, ResumeKnown, CurfrMaxfr) },
	( { EffCodeModel = model_non } ->
		(
			{ CurfrMaxfr = may_be_different },
			code_info__acquire_temp_slot(lval(redoip(lval(maxfr))),
				RedoipSlot),
			code_info__acquire_temp_slot(lval(redofr(lval(maxfr))),
				RedofrSlot),
			code_info__acquire_temp_slot(lval(maxfr),
				MaxfrSlot),
			{ HijackInfo = ite_full_hijack(ResumeKnown,
				RedoipSlot, RedofrSlot, MaxfrSlot) },
			{ Code = node([
				assign(MaxfrSlot, lval(maxfr))
					- "prepare for full ite hijack",
				assign(RedoipSlot, lval(redoip(lval(maxfr))))
					- "prepare for full ite hijack",
				assign(RedofrSlot, lval(redofr(lval(maxfr))))
					- "prepare for full ite hijack",
				assign(redofr(lval(maxfr)), lval(curfr))
					- "prepare for full ite hijack"
			]) }
		;
			{ CurfrMaxfr = must_be_equal },
			(
				{ ResumeKnown = resume_point_unknown },
				code_info__acquire_temp_slot(
					lval(redoip(lval(curfr))), RedoipSlot),
				{ HijackInfo = ite_half_hijack(ResumeKnown,
					RedoipSlot) },
				{ Code = node([
					assign(RedoipSlot,
						lval(redoip(lval(curfr))))
						- "prepare for half ite hijack"
				]) }
			;
				{ ResumeKnown = resume_point_known },
				{ HijackInfo = ite_quarter_hijack(
					ResumeKnown) },
				{ Code = empty }
			)
		)
	;
		{ HijackInfo = ite_no_hijack(ResumeKnown) },
		{ Code = empty }
	).

code_info__maybe_push_temp_frame(EffCodeModel, CanHijack, HijackInfo,
		CutFrame, Code) -->
	( { EffCodeModel = model_non } ->
		( { HijackInfo = ite_full_hijack(_, _, _, MaxfrSlot0) } ->
			{ CutFrame = MaxfrSlot0 }
		;
			{ CutFrame = curfr }
		),
		(
			{ CanHijack = yes },
			{ Code = node([
				mkframe(temp_frame, do_fail)
					- "protect slots hijacked by ite"
			]) },
			code_info__get_fail_info(FailInfo0),
			{ FailInfo0 = fail_info(ResumePoints, ResumeKnown,
				_) },
			{ FailInfo = fail_info(ResumePoints, ResumeKnown,
				may_be_different) },
			code_info__set_fail_info(FailInfo)
		;
			{ CanHijack = no },
			{ Code = empty }
		)
	;
		{ CutFrame = maxfr },
		{ Code = empty }
	).

code_info__ite_enter_then(HijackInfo, CutFrame, ThenCode, ElseCode) -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(ResumePoints0, ResumeKnown0, CurfrMaxfr) },
	{ stack__pop_det(ResumePoints0, _, ResumePoints) },
	{
		HijackInfo = ite_full_hijack(ResumeKnown1,
			RedoipSlot, RedofrSlot, MaxfrSlot),
		ThenCode = node([
			assign(redoip(lval(MaxfrSlot)), lval(RedoipSlot))
				- "restore redoip for full ite hijack",
			assign(redofr(lval(MaxfrSlot)), lval(RedofrSlot))
				- "restore redofr for full ite hijack"
		]),
		ElseCode = node([
			assign(redoip(lval(maxfr)), lval(RedoipSlot))
				- "restore redoip for full ite hijack",
			assign(redofr(lval(maxfr)), lval(RedofrSlot))
				- "restore redofr for full ite hijack"
		])
	;
		HijackInfo = ite_half_hijack(ResumeKnown1, RedoipSlot),
		ThenCode = node([
			assign(redoip(lval(CutFrame)), lval(RedoipSlot))
				- "restore redoip for half ite hijack"
		]),
		ElseCode = ThenCode
	;
		HijackInfo = ite_quarter_hijack(ResumeKnown1),
		stack__top_det(ResumePoints, ResumePoint),
		(
			code_info__maybe_pick_stack_resume_point(ResumePoint,
				_, StackLabel)
		->
			LabelConst = const(code_addr_const(StackLabel)),
			ThenCode = node([
				assign(redoip(lval(CutFrame)), LabelConst) -
					"restore redoip for quarter ite hijack"
			])
		;
			ThenCode = empty
		),
		ElseCode = ThenCode
	;
		HijackInfo = ite_no_hijack(ResumeKnown1),
		ThenCode = empty,
		ElseCode = ThenCode
	},
	{
		ResumeKnown0 = resume_point_known,
		ResumeKnown1 = resume_point_known
	->
		ResumeKnown = resume_point_known
	;
		ResumeKnown = resume_point_unknown
	},
	{ FailInfo = fail_info(ResumePoints, ResumeKnown, CurfrMaxfr) },
	code_info__set_fail_info(FailInfo).

code_info__enter_simple_neg(ResumeVars, GoalInfo, FailInfo0) -->
	code_info__get_fail_info(FailInfo0),
		% The only reason why we push a resume point at all
		% is to protect the variables in ResumeVars from becoming
		% unknown; by including them in the domain of the resume point,
		% we guarantee that the will become zombies instead of unknown
		% if they die in the pre- or post-goal updates.
		% Therefore the only part of ResumePoint that matters
		% is the set of variables in the resume map; the other
		% parts of ResumePoint (the locations, the code address)
		% will not be referenced.
	{ set__to_sorted_list(ResumeVars, ResumeVarList) },
	{ map__init(ResumeMap0) },
	{ code_info__make_fake_resume_map(ResumeVarList,
		ResumeMap0, ResumeMap) },
	{ ResumePoint = orig_only(ResumeMap, do_redo) },
	code_info__effect_resume_point(ResumePoint, model_semi, Code),
	{ require(unify(Code, empty), "nonempty code for simple neg") },
	code_info__pre_goal_update(GoalInfo, yes).

code_info__leave_simple_neg(GoalInfo, FailInfo) -->
	code_info__post_goal_update(GoalInfo),
	code_info__set_fail_info(FailInfo).

:- pred code_info__make_fake_resume_map(list(var)::in,
	map(var, set(rval))::in, map(var, set(rval))::out) is det.

code_info__make_fake_resume_map([], ResumeMap, ResumeMap).
code_info__make_fake_resume_map([Var | Vars], ResumeMap0, ResumeMap) :-
		% a visibly fake location
	set__singleton_set(Locns, lval(reg(r, -1))),
	map__det_insert(ResumeMap0, Var, Locns, ResumeMap1),
	code_info__make_fake_resume_map(Vars, ResumeMap1, ResumeMap).

%---------------------------------------------------------------------------%

code_info__effect_resume_point(ResumePoint, CodeModel, Code) -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(ResumePoints0, _ResumeKnown, CurfrMaxfr) },

	{ stack__top(ResumePoints0, OldResumePoint) ->
		code_info__pick_first_resume_point(OldResumePoint, OldMap, _),
		code_info__pick_first_resume_point(ResumePoint, NewMap, _),
		map__keys(OldMap, OldKeys),
		map__keys(NewMap, NewKeys),
		set__list_to_set(OldKeys, OldKeySet),
		set__list_to_set(NewKeys, NewKeySet),
		require(set__subset(OldKeySet, NewKeySet),
			"non-nested resume point variable sets")
	;
		true
	},

	{ stack__push(ResumePoints0, ResumePoint, ResumePoints) },
	{ FailInfo = fail_info(ResumePoints, resume_point_known, CurfrMaxfr) },
	code_info__set_fail_info(FailInfo),
	( { CodeModel = model_non } ->
		{ code_info__pick_stack_resume_point(ResumePoint,
			_, StackLabel) },
		{ LabelConst = const(code_addr_const(StackLabel)) },
		{ Code = node([
			assign(redoip(lval(maxfr)), LabelConst)
				- "hijack redoip to effect resume point"
		]) }
	;
		{ Code = empty }
	).

%---------------------------------------------------------------------------%

code_info__top_resume_point(ResumePoint) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePoints, _, _) },
	{ stack__top_det(ResumePoints, ResumePoint) }.

code_info__set_resume_point_to_unknown -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(ResumePoints, _, CurfrMaxfr) },
	{ FailInfo = fail_info(ResumePoints, resume_point_unknown,
		CurfrMaxfr) },
	code_info__set_fail_info(FailInfo).

code_info__set_resume_point_and_frame_to_unknown -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(ResumePoints, _, _) },
	{ FailInfo = fail_info(ResumePoints, resume_point_unknown,
		may_be_different) },
	code_info__set_fail_info(FailInfo).

%---------------------------------------------------------------------------%

code_info__generate_failure(Code) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePoints, ResumeKnown, _) },
	(
		{ ResumeKnown = resume_point_known },
		{ stack__top_det(ResumePoints, TopResumePoint) },
		(
			code_info__pick_matching_resume_addr(TopResumePoint,
				FailureAddress0)
		->
			{ FailureAddress = FailureAddress0 },
			{ PlaceCode = empty }
		;
			{ code_info__pick_first_resume_point(TopResumePoint,
				Map, FailureAddress) },
			{ map__to_assoc_list(Map, AssocList) },
			code_info__remember_position(CurPos),
			code_info__place_vars(AssocList, PlaceCode),
			code_info__reset_to_position(CurPos)
		),
		{ BranchCode = node([goto(FailureAddress) - "fail"]) },
		{ Code = tree(PlaceCode, BranchCode) }
	;
		{ ResumeKnown = resume_point_unknown },
		{ Code = node([goto(do_redo) - "fail"]) }
	).

code_info__fail_if_rval_is_false(Rval0, Code) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePoints, ResumeKnown, _) },
	(
		{ ResumeKnown = resume_point_known },
		{ stack__top_det(ResumePoints, TopResumePoint) },
		(
			code_info__pick_matching_resume_addr(TopResumePoint,
				FailureAddress0)
		->
				% We branch away if the test *fails*
			{ code_util__neg_rval(Rval0, Rval) },
			{ Code = node([
				if_val(Rval, FailureAddress0) -
					"Test for failure"
			]) }
		;
			{ code_info__pick_first_resume_point(TopResumePoint,
				Map, FailureAddress) },
			{ map__to_assoc_list(Map, AssocList) },
			code_info__get_next_label(SuccessLabel),
			code_info__remember_position(CurPos),
			code_info__place_vars(AssocList, PlaceCode),
			code_info__reset_to_position(CurPos),
			{ SuccessAddress = label(SuccessLabel) },
				% We branch away if the test *fails*,
				% therefore if the test succeeds, we branch
				% around the code that moves variables to
				% their failure locations and branches away
				% to the failure continuation
			{ TestCode = node([
				if_val(Rval0, SuccessAddress) -
					"Test for failure"
			]) },
			{ TailCode = node([
				goto(FailureAddress) -
					"Goto failure",
				label(SuccessLabel) -
					"Success continuation"
			]) },
			{ Code = tree(TestCode, tree(PlaceCode, TailCode)) }
		)
	;
		{ ResumeKnown = resume_point_unknown },
			% We branch away if the test *fails*
		{ code_util__neg_rval(Rval0, Rval) },
		{ Code = node([
			if_val(Rval, do_redo) -
				"Test for failure"
		]) }
	).

%---------------------------------------------------------------------------%

code_info__failure_is_direct_branch(CodeAddr) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePoints, resume_point_known, _) },
	{ stack__top(ResumePoints, TopResumePoint) },
	code_info__pick_matching_resume_addr(TopResumePoint, CodeAddr).

code_info__may_use_nondet_tailcall(MayTailCall) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePoints, ResumeKnown, _) },
	(
		{ ResumeKnown = resume_point_known },
		{ stack__top_det(ResumePoints, TopResumePoint) },
		{ TopResumePoint = stack_only(_, do_fail) }
	->
		{ MayTailCall = yes }
	;
		{ MayTailCall = no }
	).

%---------------------------------------------------------------------------%

	% See whether the current locations of variables match the locations
	% associated with any of the options in the given failure map.
	% If yes, return the code_addr of that option.

:- pred code_info__pick_matching_resume_addr(resume_point_info::in,
	code_addr::out, code_info::in, code_info::out) is semidet.

code_info__pick_matching_resume_addr(ResumeMaps, Addr) -->
	code_info__variable_locations(Locations),
	{
		ResumeMaps = orig_only(Map1, Addr1),
		( code_info__match_resume_loc(Map1, Locations) ->
			Addr = Addr1
		;
			fail
		)
	;
		ResumeMaps = stack_only(Map1, Addr1),
		( code_info__match_resume_loc(Map1, Locations) ->
			Addr = Addr1
		;
			fail
		)
	;
		ResumeMaps = orig_and_stack(Map1, Addr1, Map2, Addr2),
		( code_info__match_resume_loc(Map1, Locations) ->
			Addr = Addr1
		; code_info__match_resume_loc(Map2, Locations) ->
			Addr = Addr2
		;
			fail
		)
	;
		ResumeMaps = stack_and_orig(Map1, Addr1, Map2, Addr2),
		( code_info__match_resume_loc(Map1, Locations) ->
			Addr = Addr1
		; code_info__match_resume_loc(Map2, Locations) ->
			Addr = Addr2
		;
			fail
		)
	}.

:- pred code_info__match_resume_loc(resume_map::in, resume_map::in) is semidet.

code_info__match_resume_loc(Map, Locations0) :-
	map__keys(Map, KeyList),
	set__list_to_set(KeyList, Keys),
	map__select(Locations0, Keys, Locations),
	map__to_assoc_list(Locations, List),
	\+ (
		list__member(Thingy, List),
		\+ (
			Thingy = Var - Actual,
			map__search(Map, Var, Rvals),
			set__subset(Rvals, Actual)
		)
	).

:- pred code_info__pick_first_resume_point(resume_point_info::in,
	resume_map::out, code_addr::out) is det.

code_info__pick_first_resume_point(orig_only(Map, Addr), Map, Addr).
code_info__pick_first_resume_point(stack_only(Map, Addr), Map, Addr).
code_info__pick_first_resume_point(orig_and_stack(Map, Addr, _, _), Map, Addr).
code_info__pick_first_resume_point(stack_and_orig(Map, Addr, _, _), Map, Addr).

:- pred code_info__pick_stack_resume_point(resume_point_info::in,
	resume_map::out, code_addr::out) is det.

code_info__pick_stack_resume_point(ResumePoint, Map, Addr) :-
	( code_info__maybe_pick_stack_resume_point(ResumePoint, Map1, Addr1) ->
		Map = Map1,
		Addr = Addr1
	;
		error("no stack resume point")
	).

:- pred code_info__maybe_pick_stack_resume_point(resume_point_info::in,
	resume_map::out, code_addr::out) is semidet.

code_info__maybe_pick_stack_resume_point(stack_only(Map, Addr), Map, Addr).
code_info__maybe_pick_stack_resume_point(orig_and_stack(_, _, Map, Addr),
	Map, Addr).
code_info__maybe_pick_stack_resume_point(stack_and_orig(Map, Addr, _, _),
	Map, Addr).

%---------------------------------------------------------------------------%

code_info__produce_vars(Vars, Map, Code) -->
	{ set__to_sorted_list(Vars, VarList) },
	code_info__produce_vars_2(VarList, Map, Code).

:- pred code_info__produce_vars_2(list(var)::in,
	map(var, set(rval))::out,
	code_tree::out, code_info::in, code_info::out) is det.

code_info__produce_vars_2([], Map, empty) -->
	{ map__init(Map) }.
code_info__produce_vars_2([V | Vs], Map, Code) -->
	code_info__produce_vars_2(Vs, Map0, Code0),
	code_info__produce_variable_in_reg_or_stack(V, Code1, Rval),
	{ set__singleton_set(Rvals, Rval) },
	{ map__set(Map0, V, Rvals, Map) },
	{ Code = tree(Code0, Code1) }.

code_info__flush_resume_vars_to_stack(Code) -->
	code_info__get_fail_info(FailInfo),
	{ FailInfo = fail_info(ResumePointStack, _, _) },
	{ stack__top_det(ResumePointStack, ResumePoint) },
	{ code_info__pick_stack_resume_point(ResumePoint, StackMap, _) },
	{ map__to_assoc_list(StackMap, StackLocs) },
	code_info__place_vars(StackLocs, Code).

%---------------------------------------------------------------------------%

:- pred code_info__init_fail_info(code_model::in, maybe(set(var))::in,
	resume_point_info::out, code_info::in, code_info::out) is det.

code_info__init_fail_info(CodeModel, MaybeFailVars, ResumePoint) -->
	(
		{ CodeModel = model_det },
		code_info__get_next_label(ResumeLabel),
		{ ResumeAddress = label(ResumeLabel) },
		{ ResumeKnown = resume_point_unknown },
		{ CurfrMaxfr = may_be_different }
	;
		{ CodeModel = model_semi },
			% The resume point for this label
			% will be part of the procedure epilog.
		code_info__get_next_label(ResumeLabel),
		{ ResumeAddress = label(ResumeLabel) },
		{ ResumeKnown = resume_point_known },
		{ CurfrMaxfr = may_be_different }
	;
		{ CodeModel = model_non },
		( { MaybeFailVars = yes(_) } ->
			code_info__get_next_label(ResumeLabel),
			{ ResumeAddress = label(ResumeLabel) }
		;
			{ ResumeAddress = do_fail }
		),
		{ ResumeKnown = resume_point_known },
		{ CurfrMaxfr = must_be_equal }
	),
	( { MaybeFailVars = yes(FailVars) } ->
		code_info__get_stack_slots(StackSlots),
		{ map__select(StackSlots, FailVars, StackMap0) },
		{ map__to_assoc_list(StackMap0, StackList0) },
		{ code_info__make_singleton_sets(StackList0, StackList) },
		{ map__from_assoc_list(StackList, StackMap) }
	;
		{ map__init(StackMap) }
	),
	{ ResumePoint = stack_only(StackMap, ResumeAddress) },
	{ stack__init(ResumeStack0) },
	{ stack__push(ResumeStack0, ResumePoint, ResumeStack) },
	{ FailInfo = fail_info(ResumeStack, ResumeKnown, CurfrMaxfr) },
	code_info__set_fail_info(FailInfo).

%---------------------------------------------------------------------------%

code_info__make_resume_point(ResumeVars, ResumeLocs, FullMap, ResumePoint) -->
	code_info__get_stack_slots(StackSlots),
	{ map__select(FullMap, ResumeVars, OrigMap) },
	(
		{ ResumeLocs = orig_only },
		code_info__get_next_label(OrigLabel),
		{ OrigAddr = label(OrigLabel) },
		{ ResumePoint = orig_only(OrigMap, OrigAddr) }
	;
		{ ResumeLocs = stack_only },
		{ map__select(StackSlots, ResumeVars, StackMap0) },
		{ map__to_assoc_list(StackMap0, StackList0) },
		{ code_info__make_singleton_sets(StackList0, StackList) },
		{ map__from_assoc_list(StackList, StackMap) },
		code_info__get_next_label(StackLabel),
		{ StackAddr = label(StackLabel) },
		{ ResumePoint = stack_only(StackMap, StackAddr) }
	;
		{ ResumeLocs = orig_and_stack },
		{ map__select(StackSlots, ResumeVars, StackMap0) },
		{ map__to_assoc_list(StackMap0, StackList0) },
		{ code_info__make_singleton_sets(StackList0, StackList) },
		{ map__from_assoc_list(StackList, StackMap) },
		code_info__get_next_label(OrigLabel),
		{ OrigAddr = label(OrigLabel) },
		code_info__get_next_label(StackLabel),
		{ StackAddr = label(StackLabel) },
		{ ResumePoint = orig_and_stack(OrigMap, OrigAddr,
			StackMap, StackAddr) }
	;
		{ ResumeLocs = stack_and_orig },
		{ map__select(StackSlots, ResumeVars, StackMap0) },
		{ map__to_assoc_list(StackMap0, StackList0) },
		{ code_info__make_singleton_sets(StackList0, StackList) },
		{ map__from_assoc_list(StackList, StackMap) },
		code_info__get_next_label(StackLabel),
		{ StackAddr = label(StackLabel) },
		code_info__get_next_label(OrigLabel),
		{ OrigAddr = label(OrigLabel) },
		{ ResumePoint = stack_and_orig(StackMap, StackAddr,
			OrigMap, OrigAddr) }
	).

:- pred code_info__make_singleton_sets(assoc_list(var, lval)::in,
	assoc_list(var, set(rval))::out) is det.

code_info__make_singleton_sets([], []).
code_info__make_singleton_sets([V - L | Rest0], [V - Rs | Rest]) :-
	set__singleton_set(Rs, lval(L)),
	code_info__make_singleton_sets(Rest0, Rest).

%---------------------------------------------------------------------------%

	% The code we generate for a resumption point looks like this:
	%
	% label(StackLabel)
	% <assume variables are where StackMap says they are>
	% <copy variables to their locations according to OrigMap>
	% label(OrigLabel)
	% <assume variables are where OrigMap says they are>
	%
	% Failures at different points may cause control to arrive at
	% the resumption point via either label, which is why the last
	% line is necessary.
	%
	% The idea is that failures from other procedures will go to
	% StackLabel, and that failures from this procedure while
	% everything is in its original place will go to OrigLabel.
	% Failures from this procedure where not everything is in its
	% original place can go to either, after moving the resume variables
	% to the places where the label expects them.
	%
	% The above layout (stack, then orig) is the most common. However,
	% liveness.m may decide that one or other of the two labels will
	% never be referred to (e.g. because there are no calls inside
	% the range of effect of the resumption point or because a call
	% follows immediately after the establishment of the resumption
	% point), or that it would be more efficient to put the two labels
	% in the other order (e.g. because the code after the resumption point
	% needs most of the variables in their stack slots).

code_info__generate_resume_point(ResumePoint, Code) -->
	(
		{ ResumePoint = orig_only(Map1, Addr1) },
		{ extract_label_from_code_addr(Addr1, Label1) },
		{ Code = node([
			label(Label1) -
				"orig only failure continuation"
		]) },
		code_info__set_var_locations(Map1)
	;
		{ ResumePoint = stack_only(Map1, Addr1) },
		{ extract_label_from_code_addr(Addr1, Label1) },
		{ Code = node([
			label(Label1) -
				"stack only failure continuation"
		]) },
		code_info__set_var_locations(Map1)
	;
		{ ResumePoint = stack_and_orig(Map1, Addr1, Map2, Addr2) },
		{ extract_label_from_code_addr(Addr1, Label1) },
		{ extract_label_from_code_addr(Addr2, Label2) },
		{ Label1Code = node([
			label(Label1) -
				"stack failure continuation before orig"
		]) },
		code_info__set_var_locations(Map1),
		{ map__to_assoc_list(Map2, AssocList2) },
		code_info__place_resume_vars(AssocList2, PlaceCode),
		{ Label2Code = node([
			label(Label2) -
				"orig failure continuation after stack"
		]) },
		code_info__set_var_locations(Map2),
		{ Code = tree(Label1Code, tree(PlaceCode, Label2Code)) }
	;
		{ ResumePoint = orig_and_stack(Map1, Addr1, Map2, Addr2) },
		{ extract_label_from_code_addr(Addr1, Label1) },
		{ extract_label_from_code_addr(Addr2, Label2) },
		{ Label1Code = node([
			label(Label1) -
				"orig failure continuation before stack"
		]) },
		code_info__set_var_locations(Map1),
		{ map__to_assoc_list(Map2, AssocList2) },
		code_info__place_resume_vars(AssocList2, PlaceCode),
		{ Label2Code = node([
			label(Label2) -
				"stack failure continuation after orig"
		]) },
		code_info__set_var_locations(Map2),
		{ Code = tree(Label1Code, tree(PlaceCode, Label2Code)) }
	).

:- pred extract_label_from_code_addr(code_addr::in, label::out) is det.

extract_label_from_code_addr(CodeAddr, Label) :-
	( CodeAddr = label(Label0) ->
		Label = Label0
	;
		error("code_info__generate_resume_setup: non-label!")
	).

:- pred code_info__place_resume_vars(assoc_list(var, set(rval))::in,
	code_tree::out, code_info::in, code_info::out) is det.

code_info__place_resume_vars([], empty) --> [].
code_info__place_resume_vars([Var - TargetSet | Rest], Code) -->
	{ set__to_sorted_list(TargetSet, Targets) },
	code_info__place_resume_var(Var, Targets, FirstCode),
	{ Code = tree(FirstCode, RestCode) },
	code_info__place_resume_vars(Rest, RestCode).

:- pred code_info__place_resume_var(var::in, list(rval)::in, code_tree::out,
	code_info::in, code_info::out) is det.

code_info__place_resume_var(_Var, [], empty) --> [].
code_info__place_resume_var(Var, [Target | Targets], Code) -->
	( { Target = lval(TargetLval) } ->
		code_info__place_var(Var, TargetLval, FirstCode)
	;
		{ error("code_info__place_resume_var: not lval") }
	),
	{ Code = tree(FirstCode, RestCode) },
	code_info__place_resume_var(Var, Targets, RestCode).

	% Reset the code generator's database of what is where.
	% Remember that the variables in the map are available in their
	% associated rvals; forget about all other variables.

:- pred code_info__set_var_locations(resume_map::in,
	code_info::in, code_info::out) is det.

code_info__set_var_locations(Map) -->
	{ map__to_assoc_list(Map, List0) },
	{ code_info__flatten_varlval_list(List0, List) },
	code_info__get_exprn_info(Exprn0),
	{ code_exprn__reinit_state(List, Exprn0, Exprn) },
	code_info__set_exprn_info(Exprn).

:- pred code_info__flatten_varlval_list(assoc_list(var, set(rval))::in,
	assoc_list(var, rval)::out) is det.

code_info__flatten_varlval_list([], []).
code_info__flatten_varlval_list([V - Rvals | Rest0], All) :-
	code_info__flatten_varlval_list(Rest0, Rest),
	set__to_sorted_list(Rvals, RvalList),
	code_info__flatten_varlval_list_2(RvalList, V, Rest1),
	list__append(Rest1, Rest, All).

:- pred code_info__flatten_varlval_list_2(list(rval)::in, var::in,
	assoc_list(var, rval)::out) is det.

code_info__flatten_varlval_list_2([], _V, []).
code_info__flatten_varlval_list_2([R | Rs], V, [V - R | Rest]) :-
	code_info__flatten_varlval_list_2(Rs, V, Rest).

code_info__resume_point_vars(ResumePoint, Vars) :-
	code_info__pick_first_resume_point(ResumePoint, ResumeMap, _),
	map__keys(ResumeMap, Vars).

code_info__resume_point_stack_addr(ResumePoint, StackAddr) :-
	code_info__pick_stack_resume_point(ResumePoint, _, StackAddr).

%---------------------------------------------------------------------------%

:- type det_commit_info
	--->	det_commit_info(
			maybe(lval),		% location of saved maxfr
			maybe(pair(lval))	% location of saved ticket
						% counter and trail pointer
		).

code_info__generate_det_pre_commit(DetCommitInfo, Code) -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(_, _, CurfrMaxfr) },
	(
		{ CurfrMaxfr = may_be_different },
		code_info__acquire_temp_slot(lval(maxfr), MaxfrSlot),
		{ SaveMaxfrCode = node([
			assign(MaxfrSlot, lval(maxfr))
				- "save the value of maxfr"
		]) },
		{ MaybeMaxfrSlot = yes(MaxfrSlot) }
	;
		{ CurfrMaxfr = must_be_equal },
		{ SaveMaxfrCode = empty },
		{ MaybeMaxfrSlot = no }
	),
	code_info__maybe_save_trail_info(MaybeTrailSlots, SaveTrailCode),
	{ DetCommitInfo = det_commit_info(MaybeMaxfrSlot, MaybeTrailSlots) },
	{ Code = tree(SaveMaxfrCode, SaveTrailCode) }.

code_info__generate_det_commit(DetCommitInfo, Code) -->
	{ DetCommitInfo = det_commit_info(MaybeMaxfrSlot, MaybeTrailSlots) },
	(
		{ MaybeMaxfrSlot = yes(MaxfrSlot) },
		{ RestoreMaxfrCode = node([
			assign(maxfr, lval(MaxfrSlot))
				- "restore the value of maxfr - perform commit"
		]) },
		code_info__release_temp_slot(MaxfrSlot)
	;
		{ MaybeMaxfrSlot = no },
		{ RestoreMaxfrCode = node([
			assign(maxfr, lval(curfr))
				- "restore the value of maxfr - perform commit"
		]) }
	),
	code_info__maybe_restore_trail_info(MaybeTrailSlots,
		CommitTrailCode, _),
	{ Code = tree(RestoreMaxfrCode, CommitTrailCode) }.

%---------------------------------------------------------------------------%

:- type semi_commit_info
	--->	semi_commit_info(
			fail_info,		% fail_info on entry
			resume_point_info,
			commit_hijack_info,
			maybe(pair(lval))	% location of saved ticket
						% counter and trail pointer
		).

:- type commit_hijack_info
	--->	commit_quarter_hijack
	;	commit_half_hijack(
			lval		% the stack slot in which we saved
					% the value of the hijacked redoip
		)
	;	commit_full_hijack(
			lval,		% the stack slot in which we saved
					% the value of the hijacked redoip
			lval,		% the stack slot in which we saved
					% the value of the hijacked redofr
			lval		% the stack slot in which we saved
					% the value of maxfr
		).

code_info__generate_semi_pre_commit(SemiCommitInfo, Code) -->
	code_info__get_fail_info(FailInfo0),
	{ FailInfo0 = fail_info(ResumePoints0, ResumeKnown, CurfrMaxfr) },
	{ stack__top_det(ResumePoints0, TopResumePoint) },
	code_info__clone_resume_point(TopResumePoint, NewResumePoint),
	{ stack__push(ResumePoints0, NewResumePoint, ResumePoints) },
	{ FailInfo = fail_info(ResumePoints, ResumeKnown, CurfrMaxfr) },
	code_info__set_fail_info(FailInfo),

	{ code_info__pick_stack_resume_point(NewResumePoint, _, StackLabel) },
	{ StackLabelConst = const(code_addr_const(StackLabel)) },
	(
		{ CurfrMaxfr = may_be_different },
		code_info__acquire_temp_slot(lval(redoip(lval(maxfr))),
			RedoipSlot),
		code_info__acquire_temp_slot(lval(redofr(lval(maxfr))),
			RedofrSlot),
		code_info__acquire_temp_slot(lval(maxfr),
			MaxfrSlot),
		{ HijackInfo = commit_full_hijack(RedoipSlot, RedofrSlot,
			MaxfrSlot) },
		{ HijackCode = node([
			assign(RedoipSlot, lval(redoip(lval(maxfr))))
				- "prepare for full commit hijack",
			assign(RedofrSlot, lval(redofr(lval(maxfr))))
				- "prepare for full commit hijack",
			assign(MaxfrSlot, lval(maxfr))
				- "prepare for full commit hijack",
			assign(redofr(lval(maxfr)), lval(curfr))
				- "hijack the redofr slot",
			assign(redoip(lval(maxfr)), StackLabelConst)
				- "hijack the redoip slot"
		]) }
	;
		{ CurfrMaxfr = must_be_equal },
		(
			{ ResumeKnown = resume_point_unknown },
			code_info__acquire_temp_slot(lval(redoip(lval(curfr))),
				RedoipSlot),
			{ HijackInfo = commit_half_hijack(RedoipSlot) },
			{ HijackCode = node([
				assign(RedoipSlot, lval(redoip(lval(curfr))))
					- "prepare for half commit hijack",
				assign(redoip(lval(curfr)), StackLabelConst)
					- "hijack the redofr slot"
			]) }
		;
			{ ResumeKnown = resume_point_known },
			{ HijackInfo = commit_quarter_hijack },
			{ HijackCode = node([
				assign(redoip(lval(curfr)), StackLabelConst)
					- "hijack the redofr slot"
			]) }
		)
	),
	code_info__maybe_save_trail_info(MaybeTrailSlots, SaveTrailCode),
	{ SemiCommitInfo = semi_commit_info(FailInfo0, NewResumePoint,
		HijackInfo, MaybeTrailSlots) },
	{ Code = tree(HijackCode, SaveTrailCode) }.

code_info__generate_semi_commit(SemiCommitInfo, Code) -->
	{ SemiCommitInfo = semi_commit_info(FailInfo, ResumePoint,
		HijackInfo, MaybeTrailSlots) },

	code_info__set_fail_info(FailInfo),
	(
		{ HijackInfo = commit_full_hijack(RedoipSlot, RedofrSlot,
			MaxfrSlot) },
		{ SuccessUndoCode = node([
			assign(maxfr, lval(MaxfrSlot))
				- "restore maxfr for full commit hijack",
			assign(redoip(lval(maxfr)), lval(RedoipSlot))
				- "restore redoip for full commit hijack",
			assign(redofr(lval(maxfr)), lval(RedofrSlot))
				- "restore redofr for full commit hijack"
		]) },
		{ FailureUndoCode = node([
			assign(redoip(lval(maxfr)), lval(RedoipSlot))
				- "restore redoip for full commit hijack",
			assign(redofr(lval(maxfr)), lval(RedofrSlot))
				- "restore redofr for full commit hijack"
		]) }
	;
		{ HijackInfo = commit_half_hijack(RedoipSlot) },
		{ SuccessUndoCode = node([
			assign(maxfr, lval(curfr))
				- "restore maxfr for half commit hijack",
			assign(redoip(lval(maxfr)), lval(RedoipSlot))
				- "restore redoip for half commit hijack"
		]) },
		{ FailureUndoCode = node([
			assign(redoip(lval(maxfr)), lval(RedoipSlot))
				- "restore redoip for half commit hijack"
		]) }
	;
		{ HijackInfo = commit_quarter_hijack },
		{ FailInfo = fail_info(ResumePoints, _, _) },
		{ stack__top_det(ResumePoints, TopResumePoint) },
		{ code_info__pick_stack_resume_point(TopResumePoint,
			_, StackLabel) },
		{ StackLabelConst = const(code_addr_const(StackLabel)) },
		{ SuccessUndoCode = node([
			assign(maxfr, lval(curfr))
				- "restore maxfr for quarter commit hijack",
			assign(redoip(lval(maxfr)), StackLabelConst)
				- "restore redoip for quarter commit hijack"
		]) },
		{ FailureUndoCode = node([
			assign(redoip(lval(maxfr)), StackLabelConst)
				- "restore redoip for quarter commit hijack"
		]) }
	),

	code_info__remember_position(AfterCommit),
	code_info__generate_resume_point(ResumePoint, ResumePointCode),
	code_info__generate_failure(FailCode),
	code_info__reset_to_position(AfterCommit),

	code_info__maybe_restore_trail_info(MaybeTrailSlots,
		CommitTrailCode, RestoreTrailCode),

	code_info__get_next_label(SuccLabel),
	{ GotoSuccLabel = node([
		goto(label(SuccLabel)) - "Jump to success continuation"
	]) },
	{ SuccLabelCode = node([
		label(SuccLabel) - "Success continuation"
	]) },
	{ SuccessCode =
		tree(SuccessUndoCode,
		     CommitTrailCode)
	},
	{ FailureCode =
		tree(ResumePointCode,
		tree(FailureUndoCode,
		tree(RestoreTrailCode,
		     FailCode)))
	},
	{ Code =
		tree(SuccessCode,
		tree(GotoSuccLabel,
		tree(FailureCode,
		     SuccLabelCode)))
	}.

%---------------------------------------------------------------------------%

:- pred code_info__maybe_save_trail_info(maybe(pair(lval))::out,
	code_tree::out, code_info::in, code_info::out) is det.

code_info__maybe_save_trail_info(MaybeTrailSlots, SaveTrailCode) -->
	code_info__get_globals(Globals),
	{ globals__lookup_bool_option(Globals, use_trail, UseTrail) },
	( { UseTrail = yes } ->
		code_info__acquire_temp_slot(ticket_counter, CounterSlot),
		code_info__acquire_temp_slot(ticket, TrailPtrSlot),
		{ MaybeTrailSlots = yes(CounterSlot - TrailPtrSlot) },
		{ SaveTrailCode = node([
			mark_ticket_stack(CounterSlot)
				- "save the ticket counter",
			store_ticket(TrailPtrSlot)
				- "save the trail pointer"
		]) }
	;
		{ MaybeTrailSlots = no },
		{ SaveTrailCode = empty }
	).

:- pred code_info__maybe_restore_trail_info(maybe(pair(lval))::in,
	code_tree::out, code_tree::out, code_info::in, code_info::out) is det.

code_info__maybe_restore_trail_info(MaybeTrailSlots,
		CommitCode, RestoreCode) -->
	(
		{ MaybeTrailSlots = no },
		{ CommitCode = empty },
		{ RestoreCode = empty }
	;
		{ MaybeTrailSlots = yes(CounterSlot - TrailPtrSlot) },
		{ CommitTrailCode = node([
			reset_ticket(lval(TrailPtrSlot), commit)
				- "discard trail entries and restore trail ptr"
		]) },
		{ RestoreTrailCode = node([
			reset_ticket(lval(TrailPtrSlot), undo)
				- "apply trail entries and restore trail ptr"
		]) },
		{ RestoreCounterCode = node([
			discard_tickets_to(lval(CounterSlot))
				- "restore the ticket counter"
		]) },
		code_info__release_temp_slot(CounterSlot),
		code_info__release_temp_slot(TrailPtrSlot),
		{ CommitCode = tree(CommitTrailCode, RestoreCounterCode) },
		{ RestoreCode = tree(RestoreTrailCode, RestoreCounterCode) }
	).

%---------------------------------------------------------------------------%

:- pred code_info__clone_resume_point(resume_point_info::in,
	resume_point_info::out, code_info::in, code_info::out) is det.

code_info__clone_resume_point(ResumePoint0, ResumePoint) -->
	(
		{ ResumePoint0 = orig_only(_, _) },
		{ error("cloning orig_only resume point") }
	;
		{ ResumePoint0 = stack_only(Map1, _) },
		code_info__get_next_label(Label1),
		{ Addr1 = label(Label1) },
		{ ResumePoint = stack_only(Map1, Addr1) }
	;
		{ ResumePoint0 = stack_and_orig(Map1, _, Map2, _) },
		code_info__get_next_label(Label1),
		{ Addr1 = label(Label1) },
		code_info__get_next_label(Label2),
		{ Addr2 = label(Label2) },
		{ ResumePoint = stack_and_orig(Map1, Addr1, Map2, Addr2) }
	;
		{ ResumePoint0 = orig_and_stack(Map1, _, Map2, _) },
		code_info__get_next_label(Label2),
		{ Addr2 = label(Label2) },
		code_info__get_next_label(Label1),
		{ Addr1 = label(Label1) },
		{ ResumePoint = stack_and_orig(Map2, Addr2, Map1, Addr1) }
	).

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

	% Submodule to deal with liveness issues.

:- interface.

:- pred code_info__get_known_variables(list(var), code_info, code_info).
:- mode code_info__get_known_variables(out, in, out) is det.

:- pred code_info__variable_is_forward_live(var, code_info, code_info).
:- mode code_info__variable_is_forward_live(in, in, out) is semidet.

:- pred code_info__make_vars_forward_dead(set(var), code_info, code_info).
:- mode code_info__make_vars_forward_dead(in, in, out) is det.

:- pred code_info__pickup_zombies(set(var), code_info, code_info).
:- mode code_info__pickup_zombies(out, in, out) is det.

%---------------------------------------------------------------------------%

:- implementation.

:- pred code_info__add_forward_live_vars(set(var), code_info, code_info).
:- mode code_info__add_forward_live_vars(in, in, out) is det.

:- pred code_info__rem_forward_live_vars(set(var), code_info, code_info).
:- mode code_info__rem_forward_live_vars(in, in, out) is det.

	% Make these variables appear magically live.
	% We don't care where they are put.

:- pred code_info__make_vars_forward_live(set(var), code_info, code_info).
:- mode code_info__make_vars_forward_live(in, in, out) is det.

code_info__get_known_variables(VarList) -->
	code_info__get_forward_live_vars(ForwardLiveVars),
	code_info__current_resume_point_vars(ResumeVars),
	{ set__union(ForwardLiveVars, ResumeVars, Vars) },
	{ set__to_sorted_list(Vars, VarList) }.

code_info__variable_is_forward_live(Var) -->
	code_info__get_forward_live_vars(Liveness),
	{ set__member(Var, Liveness) }.

code_info__add_forward_live_vars(Births) -->
	code_info__get_forward_live_vars(Liveness0),
	{ set__union(Liveness0, Births, Liveness) },
	code_info__set_forward_live_vars(Liveness).

code_info__rem_forward_live_vars(Deaths) -->
	code_info__get_forward_live_vars(Liveness0),
	{ set__difference(Liveness0, Deaths, Liveness) },
	code_info__set_forward_live_vars(Liveness).

code_info__make_vars_forward_live(Vars) -->
	code_info__get_stack_slots(StackSlots),
	code_info__get_exprn_info(Exprn0),
	{ set__to_sorted_list(Vars, VarList) },
	{ code_info__make_vars_forward_live_2(VarList, StackSlots, 1,
		Exprn0, Exprn) },
	code_info__set_exprn_info(Exprn).

:- pred code_info__make_vars_forward_live_2(list(var), stack_slots, int,
	exprn_info, exprn_info).
:- mode code_info__make_vars_forward_live_2(in, in, in, in, out) is det.

code_info__make_vars_forward_live_2([], _, _, Exprn, Exprn).
code_info__make_vars_forward_live_2([V | Vs], StackSlots, N0, Exprn0, Exprn) :-
	( map__search(StackSlots, V, Lval0) ->
		Lval = Lval0,
		N1 = N0
	;
		code_info__find_unused_reg(N0, Exprn0, N1),
		Lval = reg(r, N1)
	),
	code_exprn__maybe_set_var_location(V, Lval, Exprn0, Exprn1),
	code_info__make_vars_forward_live_2(Vs, StackSlots, N1, Exprn1, Exprn).

:- pred code_info__find_unused_reg(int, exprn_info, int).
:- mode code_info__find_unused_reg(in, in, out) is det.

code_info__find_unused_reg(N0, Exprn0, N) :-
	( code_exprn__lval_in_use(reg(r, N0), Exprn0, _) ->
		N1 is N0 + 1,
		code_info__find_unused_reg(N1, Exprn0, N)
	;
		N = N0
	).

code_info__make_vars_forward_dead(Vars0) -->
	code_info__current_resume_point_vars(ResumeVars),
	{ set__intersect(Vars0, ResumeVars, FlushVars) },
	code_info__get_zombies(Zombies0),
	{ set__union(Zombies0, FlushVars, Zombies) },
	code_info__set_zombies(Zombies),
	{ set__difference(Vars0, Zombies, Vars) },
	{ set__to_sorted_list(Vars, VarList) },
	code_info__make_vars_forward_dead_2(VarList).

:- pred code_info__make_vars_forward_dead_2(list(var), code_info, code_info).
:- mode code_info__make_vars_forward_dead_2(in, in, out) is det.

code_info__make_vars_forward_dead_2([]) --> [].
code_info__make_vars_forward_dead_2([V | Vs]) -->
	code_info__get_exprn_info(Exprn0),
	{ code_exprn__var_becomes_dead(V, Exprn0, Exprn) },
	code_info__set_exprn_info(Exprn),
	code_info__make_vars_forward_dead_2(Vs).

code_info__pickup_zombies(Zombies) -->
	code_info__get_zombies(Zombies),
	{ set__init(Empty) },
	code_info__set_zombies(Empty).

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

	% Submodule for handling the saving and restoration
	% of trail tickets, heap pointers, stack pointers etc.

:- interface.

:- pred code_info__save_hp(code_tree, lval, code_info, code_info).
:- mode code_info__save_hp(out, out, in, out) is det.

:- pred code_info__restore_hp(lval, code_tree, code_info, code_info).
:- mode code_info__restore_hp(in, out, in, out) is det.

:- pred code_info__restore_and_discard_hp(lval, code_tree,
	code_info, code_info).
:- mode code_info__restore_and_discard_hp(in, out, in, out) is det.

:- pred code_info__discard_hp(lval, code_info, code_info).
:- mode code_info__discard_hp(in, in, out) is det.

:- pred code_info__maybe_save_hp(bool, code_tree, maybe(lval),
	code_info, code_info).
:- mode code_info__maybe_save_hp(in, out, out, in, out) is det.

:- pred code_info__maybe_restore_hp(maybe(lval), code_tree,
	code_info, code_info).
:- mode code_info__maybe_restore_hp(in, out, in, out) is det.

:- pred code_info__maybe_restore_and_discard_hp(maybe(lval), code_tree,
	code_info, code_info).
:- mode code_info__maybe_restore_and_discard_hp(in, out, in, out) is det.

:- pred code_info__maybe_discard_hp(maybe(lval), code_info, code_info).
:- mode code_info__maybe_discard_hp(in, in, out) is det.

:- pred code_info__save_ticket(code_tree, lval, code_info, code_info).
:- mode code_info__save_ticket(out, out, in, out) is det.

:- pred code_info__reset_ticket(lval, reset_trail_reason, code_tree,
	code_info, code_info).
:- mode code_info__reset_ticket(in, in, out, in, out) is det.

:- pred code_info__reset_and_discard_ticket(lval, reset_trail_reason, code_tree,
	code_info, code_info).
:- mode code_info__reset_and_discard_ticket(in, in, out, in, out) is det.

	% Same as reset_and_discard_ticket, but don't release the temp slot.
	% Used for cases where the temp slot might still be needed again
	% on backtracking and thus can't be reused in the code that follows.
:- pred code_info__reset_and_pop_ticket(lval, reset_trail_reason,
	code_tree, code_info, code_info).
:- mode code_info__reset_and_pop_ticket(in, in, out, in, out) is det.

:- pred code_info__discard_ticket(lval, code_tree, code_info, code_info).
:- mode code_info__discard_ticket(in, out, in, out) is det.

:- pred code_info__maybe_save_ticket(bool, code_tree, maybe(lval),
	code_info, code_info).
:- mode code_info__maybe_save_ticket(in, out, out, in, out) is det.

:- pred code_info__maybe_reset_ticket(maybe(lval), reset_trail_reason,
	code_tree, code_info, code_info).
:- mode code_info__maybe_reset_ticket(in, in, out, in, out) is det.

:- pred code_info__maybe_reset_and_discard_ticket(maybe(lval),
	reset_trail_reason, code_tree, code_info, code_info).
:- mode code_info__maybe_reset_and_discard_ticket(in, in, out, in, out) is det.

:- pred code_info__maybe_reset_and_pop_ticket(maybe(lval),
	reset_trail_reason, code_tree, code_info, code_info).
:- mode code_info__maybe_reset_and_pop_ticket(in, in, out, in, out) is det.

:- pred code_info__maybe_discard_ticket(maybe(lval), code_tree,
	code_info, code_info).
:- mode code_info__maybe_discard_ticket(in, out, in, out) is det.

:- pred code_info__save_maxfr(lval, code_tree, code_info, code_info).
:- mode code_info__save_maxfr(out, out, in, out) is det.

%---------------------------------------------------------------------------%

:- implementation.

code_info__save_hp(Code, HpSlot) -->
	code_info__acquire_temp_slot(lval(hp), HpSlot),
	{ Code = node([mark_hp(HpSlot) - "Save heap pointer"]) }.

code_info__restore_hp(HpSlot, Code) -->
	{ Code = node([restore_hp(lval(HpSlot)) - "Restore heap pointer"]) }.

code_info__discard_hp(HpSlot) -->
	code_info__release_temp_slot(HpSlot).

code_info__restore_and_discard_hp(HpSlot, Code) -->
	{ Code = node([restore_hp(lval(HpSlot)) - "Restore heap pointer"]) },
	code_info__discard_hp(HpSlot).

code_info__maybe_save_hp(Maybe, Code, MaybeHpSlot) -->
	( { Maybe = yes } ->
		code_info__save_hp(Code, HpSlot),
		{ MaybeHpSlot = yes(HpSlot) }
	;
		{ Code = empty },
		{ MaybeHpSlot = no }
	).

code_info__maybe_restore_hp(MaybeHpSlot, Code) -->
	( { MaybeHpSlot = yes(HpSlot) } ->
		code_info__restore_hp(HpSlot, Code)
	;
		{ Code = empty }
	).

code_info__maybe_restore_and_discard_hp(MaybeHpSlot, Code) -->
	( { MaybeHpSlot = yes(HpSlot) } ->
		code_info__restore_and_discard_hp(HpSlot, Code)
	;
		{ Code = empty }
	).

code_info__maybe_discard_hp(MaybeHpSlot) -->
	( { MaybeHpSlot = yes(HpSlot) } ->
		code_info__discard_hp(HpSlot)
	;
		[]
	).

code_info__save_ticket(Code, TicketSlot) -->
	code_info__acquire_temp_slot(ticket, TicketSlot),
	{ Code = node([store_ticket(TicketSlot) - "Save trail state"]) }.

code_info__reset_ticket(TicketSlot, Reason, Code) -->
	{ Code = node([reset_ticket(lval(TicketSlot), Reason) - "Reset trail"]) }.

code_info__reset_and_discard_ticket(TicketSlot, Reason, Code) -->
	code_info__release_temp_slot(TicketSlot),
	{ Code = node([
		reset_ticket(lval(TicketSlot), Reason) - "Restore trail",
		discard_ticket - "Pop ticket stack"
	]) }.

code_info__reset_and_pop_ticket(TicketSlot, Reason, Code) -->
	{ Code = node([
		reset_ticket(lval(TicketSlot), Reason) -
			"Restore trail (but don't release this stack slot)",
		discard_ticket - "Pop ticket stack"
	]) }.

code_info__discard_ticket(TicketSlot, Code) -->
	code_info__release_temp_slot(TicketSlot),
	{ Code = node([discard_ticket - "Pop ticket stack"]) }.

code_info__maybe_save_ticket(Maybe, Code, MaybeTicketSlot) -->
	( { Maybe = yes } ->
		code_info__save_ticket(Code, TicketSlot),
		{ MaybeTicketSlot = yes(TicketSlot) }
	;
		{ Code = empty },
		{ MaybeTicketSlot = no }
	).

code_info__maybe_reset_ticket(MaybeTicketSlot, Reason, Code) -->
	( { MaybeTicketSlot = yes(TicketSlot) } ->
		code_info__reset_ticket(TicketSlot, Reason, Code)
	;
		{ Code = empty }
	).

code_info__maybe_reset_and_discard_ticket(MaybeTicketSlot, Reason, Code) -->
	( { MaybeTicketSlot = yes(TicketSlot) } ->
		code_info__reset_and_discard_ticket(TicketSlot, Reason, Code)
	;
		{ Code = empty }
	).

code_info__maybe_reset_and_pop_ticket(MaybeTicketSlot, Reason, Code) -->
	( { MaybeTicketSlot = yes(TicketSlot) } ->
		code_info__reset_and_pop_ticket(TicketSlot, Reason, Code)
	;
		{ Code = empty }
	).

code_info__maybe_discard_ticket(MaybeTicketSlot, Code) -->
	( { MaybeTicketSlot = yes(TicketSlot) } ->
		code_info__discard_ticket(TicketSlot, Code)
	;
		{ Code = empty }
	).

code_info__save_maxfr(MaxfrSlot, Code) -->
	code_info__acquire_temp_slot(lval(maxfr), MaxfrSlot),
	{ Code = node([assign(MaxfrSlot, lval(maxfr)) - "Save maxfr"]) }.

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

<the rest the new code_info.m will be in part 2>