for review: mode inference bug fix

[Fergus Henderson]

Hi,

Could someone please review this one?

--------------------

Estimated hours taken: 4

Fix a bug with unique mode inference.

compiler/modes.m:
compiler/unify_proc.m:
	When doing unique mode inference, save a copy of the old
	procedure bodies, and use this to restore the old procedure
	bodies before each pass.  This avoids problems where
	modes.m was doing incorrect optimizations based on incomplete
	information obtained in passes before the fixpoint.

	Note that we already did this for ordinary mode inference, by
	copying the clauses from the clauses_info, so this was only a
	problem for unique mode inference.  But I've also changed that
	code so that doesn't copies stuff from the clauses_info before
	the first pass, since that is already done by post_typecheck.m.
	Now it only does does the copying for the second and subsequent
	passes.

tests/valid/Mmakefile:
tests/valid/uniq_mode_inf_bug.m:
	Add a test case for the above-mentioned bug.

Index: compiler/modes.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/modes.m,v
retrieving revision 1.226
diff -u -r1.226 modes.m
--- modes.m	1998/08/04 13:08:04	1.226
+++ modes.m	1998/11/10 19:11:02
@@ -351,12 +351,11 @@
 
 modecheck_to_fixpoint(PredIds, MaxIterations, WhatToCheck, ModuleInfo0,
 		ModuleInfo, UnsafeToContinue) -->
-	( { WhatToCheck = check_modes } ->
-		{ copy_module_clauses_to_procs(PredIds, ModuleInfo0,
-			ModuleInfo1) }
-	;
-		{ ModuleInfo1 = ModuleInfo0 }
-	),
+	{ ModuleInfo1 = ModuleInfo0 },
+
+	% save the old procedure bodies so that we can restore them for the
+	% next pass
+	{ module_info_preds(ModuleInfo0, OldPredTable0) },
 
 	% analyze everything which has the "can-process" flag set to `yes'
 	modecheck_pred_modes_2(PredIds, WhatToCheck, ModuleInfo1, ModuleInfo2,
@@ -364,7 +363,8 @@
 
 	% analyze the procedures whose "can-process" flag was no;
 	% those procedures were inserted into the unify requests queue.
-	modecheck_queued_procs(WhatToCheck, ModuleInfo2, ModuleInfo3, Changed2),
+	modecheck_queued_procs(WhatToCheck, OldPredTable0, ModuleInfo2,
+					OldPredTable, ModuleInfo3, Changed2),
 	io__get_exit_status(ExitStatus),
 
 	{ bool__or(Changed1, Changed2, Changed) },
@@ -387,9 +387,30 @@
 			;
 				[]
 			),
+			%
+			% Mode analysis may have modified the procedure
+			% bodies, since it does some optimizations such
+			% as deleting unreachable code.  But since we didn't
+			% reach a fixpoint yet, the mode information is not
+			% correct yet, and so those optimizations will have
+			% been done based on incomplete information, and so
+			% they may therefore produce incorrect results.
+			% Thus we need to restore the old procedure bodies.
+			%
+			( { WhatToCheck = check_modes } ->
+				% restore the proc_info goals from the
+				% clauses in the pred_info
+				{ copy_module_clauses_to_procs(PredIds,
+					ModuleInfo3, ModuleInfo4) }
+			;
+				% restore the proc_info goals from the
+				% proc_infos in the old module_info
+				{ copy_pred_bodies(OldPredTable, PredIds,
+					ModuleInfo3, ModuleInfo4) }
+			),
 			{ MaxIterations1 is MaxIterations - 1 },
 			modecheck_to_fixpoint(PredIds, MaxIterations1,
-				WhatToCheck, ModuleInfo3,
+				WhatToCheck, ModuleInfo4,
 				ModuleInfo, UnsafeToContinue)
 		)
 	).
@@ -408,6 +429,45 @@
 		MaxIterations),
 	io__format("(The current limit is %d iterations.)\n",
 		[i(MaxIterations)]).
+
+% copy_pred_bodies(OldPredTable, ProcId, ModuleInfo0, ModuleInfo):
+%	copy the procedure bodies for all procedures of the specified
+%	PredIds from OldPredTable into ModuleInfo0, giving ModuleInfo.
+:- pred copy_pred_bodies(pred_table, list(pred_id), module_info, module_info).
+:- mode copy_pred_bodies(in, in, in, out) is det.
+copy_pred_bodies(OldPredTable, PredIds, ModuleInfo0, ModuleInfo) :-
+	module_info_preds(ModuleInfo0, PredTable0),
+	list__foldl(copy_pred_body(OldPredTable), PredIds,
+		PredTable0, PredTable),
+	module_info_set_preds(ModuleInfo0, PredTable, ModuleInfo).
+
+% copy_pred_body(OldPredTable, ProcId, PredTable0, PredTable):
+%	copy the procedure bodies for all procedures of the specified
+%	PredId from OldPredTable into PredTable0, giving PredTable.
+:- pred copy_pred_body(pred_table, pred_id, pred_table, pred_table).
+:- mode copy_pred_body(in, in, in, out) is det.
+copy_pred_body(OldPredTable, PredId, PredTable0, PredTable) :-
+	map__lookup(PredTable0, PredId, PredInfo0),
+	pred_info_procedures(PredInfo0, ProcTable0),
+	map__lookup(OldPredTable, PredId, OldPredInfo),
+	pred_info_procedures(OldPredInfo, OldProcTable),
+	map__keys(OldProcTable, OldProcIds),
+	list__foldl(copy_proc_body(OldProcTable), OldProcIds,
+		ProcTable0, ProcTable),
+	pred_info_set_procedures(PredInfo0, ProcTable, PredInfo),
+	map__set(PredTable0, PredId, PredInfo, PredTable).
+
+% copy_proc_body(OldProcTable, ProcId, ProcTable0, ProcTable):
+%	copy the body of the specified ProcId from OldProcTable
+%	into ProcTable0, giving ProcTable.
+:- pred copy_proc_body(proc_table, proc_id, proc_table, proc_table).
+:- mode copy_proc_body(in, in, in, out) is det.
+copy_proc_body(OldProcTable, ProcId, ProcTable0, ProcTable) :-
+	map__lookup(OldProcTable, ProcId, OldProcInfo),
+	proc_info_goal(OldProcInfo, OldProcBody),
+	map__lookup(ProcTable0, ProcId, ProcInfo0),
+	proc_info_set_goal(ProcInfo0, OldProcBody, ProcInfo),
+	map__set(ProcTable0, ProcId, ProcInfo, ProcTable).
 
 :- pred modecheck_pred_modes_2(list(pred_id), how_to_check_goal,
 			module_info, module_info, bool, bool, int, int,
Index: compiler/unify_proc.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/unify_proc.m,v
retrieving revision 1.70
diff -u -r1.70 unify_proc.m
--- unify_proc.m	1998/08/04 02:14:17	1.70
+++ unify_proc.m	1998/11/10 19:10:00
@@ -79,11 +79,14 @@
 	% If the first argument is `unique_mode_check',
 	% then also go on and do full determinism analysis and unique mode
 	% analysis on them as well.
+	% The pred_table arguments are used to store copies of the
+	% procedure bodies before unique mode analysis, so that
+	% we can restore them before doing the next analysis pass.
 
-:- pred modecheck_queued_procs(how_to_check_goal, module_info, module_info,
-				bool,
+:- pred modecheck_queued_procs(how_to_check_goal, pred_table, module_info,
+				pred_table, module_info, bool,
 				io__state, io__state).
-:- mode modecheck_queued_procs(in, in, out, out, di, uo) is det.
+:- mode modecheck_queued_procs(in, in, in, out, out, out, di, uo) is det.
 
 	% Given the type and mode of a unification, look up the
 	% mode number for the unification proc.
@@ -298,7 +301,8 @@
 
 	% XXX these belong in modes.m
 
-modecheck_queued_procs(HowToCheckGoal, ModuleInfo0, ModuleInfo, Changed) -->
+modecheck_queued_procs(HowToCheckGoal, OldPredTable0, ModuleInfo0,
+		OldPredTable, ModuleInfo, Changed) -->
 	{ module_info_get_proc_requests(ModuleInfo0, Requests0) },
 	{ unify_proc__get_req_queue(Requests0, RequestQueue0) },
 	(
@@ -321,15 +325,18 @@
 			queued_proc_progress_message(PredProcId,
 				HowToCheckGoal, ModuleInfo1),
 			modecheck_queued_proc(HowToCheckGoal, PredProcId,
-				ModuleInfo1, ModuleInfo2, Changed1)
+				OldPredTable0, ModuleInfo1, 
+				OldPredTable2, ModuleInfo2, Changed1)
 		;
+			{ OldPredTable2 = OldPredTable0 },
 			{ ModuleInfo2 = ModuleInfo1 },
 			{ Changed1 = no }
 		),
-		modecheck_queued_procs(HowToCheckGoal, ModuleInfo2, ModuleInfo,
-			Changed2),
+		modecheck_queued_procs(HowToCheckGoal, OldPredTable2,
+			ModuleInfo2, OldPredTable, ModuleInfo, Changed2),
 		{ bool__or(Changed1, Changed2, Changed) }
 	;
+		{ OldPredTable = OldPredTable0 },
 		{ ModuleInfo = ModuleInfo0 },
 		{ Changed = no }
 	).
@@ -366,13 +373,13 @@
 		[]
 	).
 
-:- pred modecheck_queued_proc(how_to_check_goal, pred_proc_id,
-				module_info, module_info, bool,
+:- pred modecheck_queued_proc(how_to_check_goal, pred_proc_id, pred_table,
+				module_info, pred_table, module_info, bool,
 				io__state, io__state).
-:- mode modecheck_queued_proc(in, in, in, out, out, di, uo) is det.
+:- mode modecheck_queued_proc(in, in, in, in, out, out, out, di, uo) is det.
 
-modecheck_queued_proc(HowToCheckGoal, PredProcId, ModuleInfo0, ModuleInfo,
-			Changed) -->
+modecheck_queued_proc(HowToCheckGoal, PredProcId, OldPredTable0, ModuleInfo0,
+			OldPredTable, ModuleInfo, Changed) -->
 	{
 	%
 	% mark the procedure as ready to be processed
@@ -398,6 +405,7 @@
 		{ NumErrors \= 0 }
 	->
 		io__set_exit_status(1),
+		{ OldPredTable = OldPredTable0 },
 		{ ModuleInfo = ModuleInfo2 },
 		{ Changed = Changed1 }
 	;
@@ -408,15 +416,34 @@
 						ModuleInfo3, ModuleInfo4),
 			determinism_check_proc(ProcId, PredId,
 						ModuleInfo4, ModuleInfo5),
+			{ save_proc_info(ProcId, PredId, ModuleInfo5,
+				OldPredTable0, OldPredTable) },
 			unique_modes__check_proc(ProcId, PredId,
 						ModuleInfo5, ModuleInfo,
 						Changed2),
 			{ bool__or(Changed1, Changed2, Changed) }
 		;	
+			{ OldPredTable = OldPredTable0 },
 			{ ModuleInfo = ModuleInfo2 },
 			{ Changed = Changed1 }
 		)
 	).
+
+%
+% save a copy of the proc info for the specified procedure in OldProcTable0,
+% giving OldProcTable.
+%
+:- pred save_proc_info(proc_id, pred_id, module_info, pred_table, pred_table).
+:- mode save_proc_info(in, in, in, in, out) is det.
+
+save_proc_info(ProcId, PredId, ModuleInfo, OldPredTable0, OldPredTable) :-
+	module_info_pred_proc_info(ModuleInfo, PredId, ProcId,
+		_PredInfo, ProcInfo),
+	map__lookup(OldPredTable0, PredId, OldPredInfo0),
+	pred_info_procedures(OldPredInfo0, OldProcTable0),
+	map__set(OldProcTable0, ProcId, ProcInfo, OldProcTable),
+	pred_info_set_procedures(OldPredInfo0, OldProcTable, OldPredInfo),
+	map__det_update(OldPredTable0, PredId, OldPredInfo, OldPredTable).
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
Index: tests/valid/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/valid/Mmakefile,v
retrieving revision 1.29
diff -u -r1.29 Mmakefile
--- Mmakefile	1998/11/03 05:32:01	1.29
+++ Mmakefile	1998/11/10 19:26:32
@@ -102,6 +102,7 @@
 	unbound_tvar_in_lambda.m \
 	undead_proc.m \
 	uniq_unify.m \
+	uniq_mode_inf_bug.m \
 	unreachable_code.m \
 	unused_args_test2.m \
 	vn_float.m
@@ -159,6 +160,7 @@
 MCFLAGS-simplify_bug		= -O-1
 MCFLAGS-two_way_unif		= -O-1
 MCFLAGS-type_inf_ambig_test	= --infer-all
+MCFLAGS-uniq_mode_inf_bug	= --infer-all
 MCFLAGS-vn_float		= -O5
 
 # intermod_lambda.m needs inter-module optimization
Index: tests/valid/uniq_mode_inf_bug.m
===================================================================
RCS file: uniq_mode_inf_bug.m
diff -N uniq_mode_inf_bug.m
--- /dev/null	Wed Nov 11 06:21:35 1998
+++ uniq_mode_inf_bug.m	Wed Nov 11 06:17:06 1998
@@ -0,0 +1,50 @@
+%------------------------------------------------------------------------------
+%	Benchmark Program - Counting occurrences in lists
+%
+%	Author: B. Ramkumar and L. V. Kale
+%	Date: 
+%
+%	To test: run o/1.  
+%------------------------------------------------------------------------------
+% Benchmark is o(31), runs with -A1 -E256 -C128
+
+:- module occur.
+
+:- interface.
+:- import_module list.
+
+:- pred occurall(list(int), list(list(int)), list(list(int))).
+:- mode occurall(in, in, out) is nondet.
+
+:- implementation.
+
+:- import_module int.
+
+occurall([], _X, []).
+occurall([X|Y],Z, [[X,W]|V]) :-
+	occur(X,Z,W),
+	occurall(Y,Z,V).
+
+occur(_X,[],0).
+occur(X,[Y|Z],W) :-
+	(
+		count(X,Y,A),
+		occur(X,Z,B)
+	->
+		W is A + B
+	;
+		fail
+	).
+
+count(_X,[],0).
+count(X,[Y|Z],W) :-
+	( count(X,Z,W1) ->
+		addx(X,Y,W1,W)
+	;
+		fail
+	).
+
+addx(X,X,W1,W) :-
+	W is W1 + 1.
+addx(X,Y,W1,W1) :-
+	X \= Y.
-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh at 128.250.37.3        |     -- leaked Microsoft memo.