diff: more bug fixes for liveness.

[Tyson Richard DOWD]

Hi,

More bugs in liveness. These were caused by slightly incorrect previous
bugfixes, that interacted in interesting ways...

The good news is that the entire library can now be successfully
compiled to C in .agc grade.

Here's the fix.

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

Estimated hours taken: 4

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/02 05:25:35
@@ -112,7 +112,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 +298,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 +335,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 +360,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 +773,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 +980,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           # 
                            #  Surreal humour isn't eveyone's cup of
     trd at cs.mu.oz.au        #  fur.
http://www.cs.mu.oz.au/~trd #