[m-dev.] diff: more bug fixes for liveness.

[Tyson Richard DOWD]

I've added some documentation to this change, describing the invariant
that accurate GC needs, and how it is achieved.

I'll commit this change very soon.

===================================================================

Estimated hours taken: 5

Fix several bugs in liveness for accurate GC. 

compiler/liveness.m:
	- Add `liveness__get_nonlocals_and_typeinfos'.
	- Call `liveness__get_nonlocals_and_typeinfos' instead of just
	  getting nonlocals. This removes a lot of repeated code (and
	  improves correctness).
	- Intersect the initially live variables with the non-locals and
	  their typeinfo vars, not just the non-locals.
	- Don't add corresponding typeinfos to the liveness after the
	  intersection (previously we did this, which "fixed" many
	  problems that doing the intersection wrong introduced, but
	  introduced a few bugs of its own).

tests/valid/Mmake:
tests/valid/agc_graph.m:
tests/valid/agc_ho_pred.m:
	Test cases for these bugs.


Index: compiler/liveness.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/liveness.m,v
retrieving revision 1.75
diff -u -r1.75 liveness.m
--- liveness.m	1997/06/23 05:32:20	1.75
+++ liveness.m	1997/07/03 04:56:05
@@ -6,7 +6,7 @@
 %
 % File: liveness.m
 %
-% Main authors: conway, zs.
+% Main authors: conway, zs, trd.
 %
 % This module traverses the goal for each procedure, and adds
 % liveness annotations to the goal_info for each sub-goal.
@@ -40,15 +40,53 @@
 % occurrence of a variable include that variable in their post-death
 % set. In branched structures, branches in which a variable is not
 % used at all include a pre-death set listing the variables that
-% have died in parallel branches. Note that when using accurate gc,
-% a variable holding a typeinfo is live while any variable described
-% (in whole or in part) by that typeinfo is live.
+% have died in parallel branches. 
 %
 % The third pass, detect_resume_points_in_goal, finds goals that
 % establish resume points and attaches to them a resume_point
 % annotation listing the variables that may be referenced by the
 % code at that resume point as well as the nature of the required
 % entry labels.
+%
+% Accurate Garbage Collection Notes:
+%
+% Note that when using accurate gc, liveness is computed slightly
+% differently. The garbage collector needs access to the typeinfo
+% variables of any variable that could be garbage collected. 
+% 
+% Hence, the invariant needed for accurate GC is:
+% 	a variable holding a typeinfo must be live at any continuation
+% 	where any variable whose type is described (in whole or in part)
+% 	by that typeinfo is live.
+%
+% Typeinfos are introduced as either one of the head variables, or a new
+% variable created by a goal in the procedure. If introduced as a head
+% variable, initial_liveness will add it to the initial live set of
+% variables -- no variable could be introduced earlier than the start of
+% the goal. If introduced by a goal in the procedure, that goal must
+% occur before any call that requires the typeinfo, so the variable will
+% be born before the continuation after the call. So the typeinfo
+% variables will always be born before any continuation where they are
+% needed.
+% 
+% A typeinfo variable becomes dead after both the following conditions
+% are true: 
+% 	(1) The typeinfo variable is not used again (when it is no
+% 	    longer part of the nonlocals)
+%	(2) No other nonlocal variable's type is described by that typeinfo
+%	    variable.
+% 
+% (1) happens without any changes to the liveness computation (it is
+%     the normal condition for variables becoming dead). This more
+%     conservative than what is required for accurate GC, but is
+%     required for code generation, so we should keep it ;-)
+% (2) is implemented by adding the typeinfo variables for the types of the
+%     nonlocals to the nonlocals for the purposes of computing liveness.
+%
+% So typeinfo variables will always be born before they are needed, and
+% die only when no other variable needing them will be live, so the
+% invariant holds.
+%
 
 %-----------------------------------------------------------------------------%
 
@@ -112,7 +150,7 @@
 		Liveness, Goal - GoalInfo) :-
 
 		% work out which variables get born in this goal
-	goal_info_get_nonlocals(GoalInfo0, NonLocals),
+	liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo0, NonLocals),
 	set__difference(NonLocals, Liveness0, NewVarsSet),
 	set__to_sorted_list(NewVarsSet, NewVarsList),
 	goal_info_get_instmap_delta(GoalInfo0, InstMapDelta),
@@ -298,24 +336,11 @@
 	set__union(Deadness0, PostDeaths0, Deadness1),
 	set__difference(Deadness1, PostBirths0, Deadness2),
 
-	goal_info_get_nonlocals(GoalInfo0, NonLocals0),
-	live_info_get_module_info(LiveInfo, ModuleInfo),
-	module_info_globals(ModuleInfo, Globals),
-	globals__get_gc_method(Globals, GCmethod),
+	liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo0, NonLocals),
 	set__init(Empty),
 	(
 		goal_is_atomic(Goal0)
 	->
-		(
-			GCmethod = accurate
-		->
-			live_info_get_proc_info(LiveInfo, ProcInfo),
-			proc_info_get_typeinfo_vars_setwise(ProcInfo,
-				NonLocals0, TypeInfoVars),
-			set__union(NonLocals0, TypeInfoVars, NonLocals)
-		;
-			NonLocals = NonLocals0
-		),
 		NewPreDeaths = Empty,
 		set__difference(NonLocals, Deadness2, NewPostDeaths),
 		set__union(Deadness2, NewPostDeaths, Deadness3),
@@ -348,14 +373,14 @@
 detect_deadness_in_goal_2(disj(Goals0, SM), GoalInfo, Deadness0,
 		LiveInfo, Deadness, disj(Goals, SM)) :-
 	set__init(Union0),
-	goal_info_get_nonlocals(GoalInfo, NonLocals),
+	liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo, NonLocals),
 	detect_deadness_in_disj(Goals0, Deadness0, NonLocals,
 		LiveInfo, Union0, Deadness, Goals).
 
 detect_deadness_in_goal_2(switch(Var, Det, Cases0, SM), GoalInfo, Deadness0,
 		LiveInfo, Deadness, switch(Var, Det, Cases, SM)) :-
 	set__init(Union0),
-	goal_info_get_nonlocals(GoalInfo, NonLocals),
+	liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo, NonLocals),
 	detect_deadness_in_cases(Var, Cases0, Deadness0, NonLocals,
 		LiveInfo, Union0, Deadness, Cases).
 
@@ -373,20 +398,7 @@
 	detect_deadness_in_goal(Cond0, DeadnessThen, LiveInfo,
 		DeadnessCond, Cond1),
 
-	goal_info_get_nonlocals(GoalInfo, NonLocals0),
-	live_info_get_module_info(LiveInfo, ModuleInfo),
-	module_info_globals(ModuleInfo, Globals),
-	globals__get_gc_method(Globals, GCmethod),
-	(
-		GCmethod = accurate
-	->
-		live_info_get_proc_info(LiveInfo, ProcInfo),
-		proc_info_get_typeinfo_vars_setwise(ProcInfo, NonLocals0, 
-			TypeInfoVars),
-		set__union(NonLocals0, TypeInfoVars, NonLocals)
-	;
-		NonLocals = NonLocals0
-	),
+	liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo, NonLocals),
 	set__union(DeadnessCond, DeadnessElse, Deadness),
 	set__intersect(Deadness, NonLocals, NonLocalDeadness),
 
@@ -799,27 +811,28 @@
 	;
 		error("initial_liveness: list length mismatch")
 	),
-		% If doing accurate garbage collection, the corresponding
-		% typeinfos need to be added to these.
 	module_info_globals(ModuleInfo, Globals),
 	globals__get_gc_method(Globals, GCmethod),
-	(
-		GCmethod = accurate
-	->
-		proc_info_get_typeinfo_vars_setwise(ProcInfo, Liveness2,
-			TypeInfoVars),
-		set__union(Liveness2, TypeInfoVars, Liveness3)
-	;
-		Liveness3 = Liveness2
-	),
+
 		% If a variable is unused in the goal, it shouldn't be
 		% in the initial liveness. (If we allowed it to start
 		% live, it wouldn't ever become dead, because it would
 		% have to be used to be killed).
-		% So we intersect the headvars with the non-locals.
+		% So we intersect the headvars with the non-locals and
+		% their typeinfo vars.
 	proc_info_goal(ProcInfo, _Goal - GoalInfo),
-	goal_info_get_nonlocals(GoalInfo, NonLocals),
-	set__intersect(Liveness3, NonLocals, Liveness).
+	goal_info_get_nonlocals(GoalInfo, NonLocals0),
+	(
+		GCmethod = accurate
+	->
+		proc_info_get_typeinfo_vars_setwise(ProcInfo, NonLocals0,
+			TypeInfoNonLocals),
+		set__union(NonLocals0, TypeInfoNonLocals, NonLocals)
+	;
+		NonLocals = NonLocals0
+	),
+	set__intersect(Liveness2, NonLocals, Liveness).
+
 
 :- pred initial_liveness_2(list(var), list(mode), list(type), module_info,
 	set(var), set(var)).
@@ -1005,5 +1018,30 @@
 :- mode live_info_get_varset(in, out) is det.
 
 live_info_get_varset(live_info(_, _, _, Varset), Varset).
+
+%-----------------------------------------------------------------------------%
+
+	% Get the nonlocals, and, if doing accurate GC, add the
+	% typeinfo vars for the nonlocals.
+
+:- pred liveness__get_nonlocals_and_typeinfos(live_info, hlds_goal_info,
+		set(var)).
+:- mode liveness__get_nonlocals_and_typeinfos(in, in, out) is det.
+liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo, 
+		NonLocals) :-
+	live_info_get_module_info(LiveInfo, ModuleInfo),
+	module_info_globals(ModuleInfo, Globals),
+	globals__get_gc_method(Globals, GCmethod),
+	goal_info_get_nonlocals(GoalInfo, NonLocals0),
+	(
+		GCmethod = accurate
+	->
+		live_info_get_proc_info(LiveInfo, ProcInfo),
+		proc_info_get_typeinfo_vars_setwise(ProcInfo, NonLocals0,
+			TypeInfoVarsNonLocals),
+		set__union(NonLocals0, TypeInfoVarsNonLocals, NonLocals)
+	;
+		NonLocals = NonLocals0
+	).
 
 %-----------------------------------------------------------------------------%
Index: tests/valid/Mmake
===================================================================
RCS file: /home/staff/zs/imp/tests/valid/Mmake,v
retrieving revision 1.43
diff -u -r1.43 Mmake
--- Mmake	1997/06/29 23:23:30	1.43
+++ Mmake	1997/07/02 05:22:26
@@ -8,6 +8,8 @@
 
 # please keep this list sorted
 SOURCES= \
+	agc_graph.m \
+	agc_ho_pred.m \
 	agc_ite.m \
 	agc_unbound_typevars.m \
 	agc_unbound_typevars2.m \
@@ -81,6 +83,8 @@
 
 # some regression tests only failed with particular options enabled
 # (please keep this list sorted)
+GRADE-agc_graph			= asm_fast.agc
+GRADE-agc_ho_pred		= asm_fast.agc
 GRADE-agc_ite			= asm_fast.agc
 GRADE-agc_unbound_typevars	= asm_fast.agc
 GRADE-agc_unbound_typevars2	= asm_fast.agc

New File: tests/valid/agc_graph.m
===================================================================
%
% Regression test.
%
% Name: agc_graph.m
%
% Description of bug:
% 	The liveness of polymorphic type variables for accurate gc
% 	wasn't being computed correctly.
% 	It was being removed from the initial_liveness for not being
% 	part of the non-locals (like an unused variable).
%
% Symptom(s) of bug:
% 	% Allocating storage locations for live vars in predicate
% 		`agc_graph:insert_node/4' mode 0
% 	Software error: variable TypeInfo_for_A (18) not found
%
% Date bug existed: 1-July-1997
%
% Author: trd
%
% Note: This code was taken from library/graph.m and simplified.
%

:- module agc_graph.

:- interface.
:- import_module std_util.

:- type graph(N, A).

:- type node(N).

:- type arc(A).

:- type graph(N)	== graph(N, unit).

:- type arc		== arc(unit).

:- pred agc_graph__insert_node(graph(N, A), N, node(N), graph(N, A)).
:- mode agc_graph__insert_node(in, in, out, out) is semidet.

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

:- implementation.

:- import_module map, int, std_util, list.
:- import_module require.

:- type graph(N, A)	--->
		graph(
			agc_graph__node_supply,
			agc_graph__arc_supply,
			map(node(N), N),
			map(arc(A), arc_info(N, A)),
			map(node(N), map(arc(A), node(N)))
		).

:- type agc_graph__node_supply	==	int.

:- type agc_graph__arc_supply	==	int.

:- type node(N)			==	int.

:- type arc(A)			==	int.

:- type arc_info(N, A)	--->	arc_info(node(N), node(N), A).

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

agc_graph__insert_node(G, NInfo, N, G) :-
	G = graph(_, _, Nodes0, _, _),

	agc_graph__get_node_supply(G, N),
	agc_graph__get_edges(G, Edges0),

	\+ map__member(Nodes0, _, NInfo),
	map__init(Edges0).

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

:- pred agc_graph__get_node_supply(graph(N, A), agc_graph__node_supply).
:- mode agc_graph__get_node_supply(in, out) is det.

agc_graph__get_node_supply(G, NS) :-
	G = graph(NS, _AS, _N, _A, _E).

:- pred agc_graph__get_edges(graph(N, A), map(node(N), map(arc(A), node(N)))).
:- mode agc_graph__get_edges(in, out) is det.

agc_graph__get_edges(G, E) :-
	G = graph(_NS, _AS, _N, _A, E).

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

New File: tests/valid/agc_ho_pred.m
===================================================================
%
% Regression test.
%
% Name: agc_ho_pred.m
%
% Description of bug:
% 	The liveness of a typeinfo variable was being computed
% 	incorrectly.
% 	This was caused because the variable TypeInfo_for_OptionType was
% 	incorrectly added to the initial_liveness. It was assumed that
% 	all type variables for the types of the input arguments would
% 	have corresponding typeinfos as input. This is incorrect, higher
% 	order preds do not have typeinfo variables as input.
%
% Symptom(s) of bug:
% 	% Generating code for predicate 
% 		`agc_ho_pred:agc_ho_pred__LambdaGoal__1/2'
% 	Software error: variable TypeInfo_for_OptionType (16) not found
% 

% This code was taken from library/getopt.m, and simplified.

:- module agc_ho_pred.
:- interface.
:- import_module bool, char, list, map, std_util.

:- type option_ops(OptionType)
	--->	option_ops(
			pred(char, OptionType),		% short_option
			pred(string, OptionType),	% long_option
			pred(OptionType, option_data)	% option_default
		)
	;	option_ops(
			pred(char, OptionType),		% short_option
			pred(string, OptionType),	% long_option
			pred(OptionType, option_data),	% option_default
			pred(OptionType, special_data,	% special option handler
				option_table(OptionType),
				maybe_option_table(OptionType))
		).

:- inst option_ops =
	bound((
		option_ops(
			pred(in, out) is semidet,	% short_option
			pred(in, out) is semidet,	% long_option
			pred(out, out) is nondet	% option_default
		)
	;	option_ops(
			pred(in, out) is semidet,	% short_option
			pred(in, out) is semidet,	% long_option
			pred(out, out) is nondet,	% option_default
			pred(in, in, in, out) is semidet% special handler
		)
	)).

:- type option_data
	--->	bool(bool)
	;	int(int)
	;	string(string)
	;	maybe_string(maybe(string))
	;	accumulating(list(string))
	;	special
	;	bool_special
	;	int_special
	;	string_special.

:- type special_data
	--->	none
	;	bool(bool)
	;	int(int)
	;	string(string).

:- type option_table(OptionType)
	==	map(OptionType, option_data).

:- type maybe_option_table(OptionType)
	--->	ok(option_table(OptionType))
	;	error(string).

:- pred agc_ho_pred__process_options(
                option_ops(OptionType)::in(option_ops),
                list(pair(OptionType, option_data))::out
	) is det.

:- implementation.

agc_ho_pred__process_options(OptionOps, Args) :-
	( 
		OptionOps = option_ops(_, _, OptionDefaultsPred)
	; 
		OptionOps = option_ops(_, _, OptionDefaultsPred, _) 
	),
        solutions(lambda([OptionDataPair::out] is nondet, (
                        OptionDataPair = Option - OptionData,
                        call(OptionDefaultsPred, Option, OptionData)
                )), OptionDefaultsList),
	Args = OptionDefaultsList.



-- 
       Tyson Dowd           # Assimilation doesn't kill people -- 
                            # resistance kills people.
     trd at cs.mu.oz.au        # 
http://www.cs.mu.oz.au/~trd # (Seen on back of Borg cube.)