[m-dev.] for review: fix the handling of unique modes in parallel conjunction

[Thomas Conway]

Hi

Since this only affects parallel conjunction, I'll commit it now, but it
still needs to be reviewed. Fergus, or someone else who is familiar with
uniqueness?

-- 
 Thomas Conway )O+     Every sword has two edges.
     Mercurian            <conway at cs.mu.oz.au>


compiler/unique_modes.m:
compiler/par_conj_gen.m:
	Fix the handling of uniqueness in parallel conjunctions so that
	variables that occur in more than one conjunct become shared.

Index: unique_modes.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/unique_modes.m,v
retrieving revision 1.56
diff -u -r1.56 unique_modes.m
--- unique_modes.m	1999/08/26 17:49:04	1.56
+++ unique_modes.m	1999/08/30 01:49:36
@@ -62,7 +62,8 @@
 :- import_module modes, prog_data, mode_errors, llds, unify_proc.
 :- import_module (inst), instmap, inst_match, inst_util.
 :- import_module term, varset.
-:- import_module int, list, map, set, std_util, require, assoc_list, string.
+:- import_module assoc_list, bag, int, list, map.
+:- import_module require, set, std_util, string.
 
 %-----------------------------------------------------------------------------%
 
@@ -264,7 +265,11 @@
 	mode_checkpoint(enter, "par_conj"),
 	{ goal_info_get_nonlocals(GoalInfo0, NonLocals) },
 	mode_info_add_live_vars(NonLocals),
-	unique_modes__check_par_conj(List0, List, InstMapList),
+		% Build a multiset of the nonlocals of the conjuncts
+		% so that we can figure out which variables must be
+		% made shared at the start of the parallel conjunction.
+	{ make_par_conj_nonlocal_multiset(List0, NonLocalsBag) },
+	unique_modes__check_par_conj(List0, NonLocalsBag, List, InstMapList),
 	instmap__unify(NonLocals, InstMapList),
 	mode_info_remove_live_vars(NonLocals),
 	mode_checkpoint(exit, "par_conj").
@@ -642,25 +647,77 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred unique_modes__check_par_conj(list(hlds_goal), list(hlds_goal),
-		list(pair(instmap, set(prog_var))), mode_info, mode_info).
-:- mode unique_modes__check_par_conj(in, out, out,
+	% make_par_conj_nonlocal_multiset builds a multiset (bag) of all
+	% the nonlocals of the conjuncts.
+:- pred make_par_conj_nonlocal_multiset(list(hlds_goal), bag(prog_var)).
+:- mode make_par_conj_nonlocal_multiset(in, out) is det.
+
+make_par_conj_nonlocal_multiset([], Empty) :-
+	bag__init(Empty).
+make_par_conj_nonlocal_multiset([G|Gs], NonLocalsMultiSet) :-
+	make_par_conj_nonlocal_multiset(Gs, NonLocalsMultiSet0),
+	unique_modes__goal_get_nonlocals(G, NonLocals),
+	set__to_sorted_list(NonLocals, NonLocalsList),
+	bag__from_list(NonLocalsList, NonLocalsMultiSet1),
+	bag__union(NonLocalsMultiSet0, NonLocalsMultiSet1, NonLocalsMultiSet).
+
+	% To unique-modecheck a parallel conjunction, we find the variables
+	% that are nonlocal to more than one conjunct and make them shared,
+	% then we unique-modecheck the conjuncts.
+	%
+	% The variables that occur in more than one conjunct must be shared
+	% because otherwise it would be possible to make them become clobbered
+	% which would introduce an implicit dependency between the conjuncts
+	% which we do not allow.
+:- pred unique_modes__check_par_conj(list(hlds_goal), bag(prog_var),
+		list(hlds_goal), list(pair(instmap, set(prog_var))),
+		mode_info, mode_info).
+:- mode unique_modes__check_par_conj(in, in, out, out,
 		mode_info_di, mode_info_uo) is det.
 
+unique_modes__check_par_conj(Goals0, NonLocalVarsBag, Goals, Instmaps) -->
+	unique_modes__check_par_conj_0(NonLocalVarsBag),
+	unique_modes__check_par_conj_1(Goals0, Goals, Instmaps).
+
+		% Figure out which variables occur in more than one
+		% conjunct and make them shared.
+:- pred unique_modes__check_par_conj_0(bag(prog_var), mode_info, mode_info).
+:- mode unique_modes__check_par_conj_0(in, mode_info_di, mode_info_uo) is det.
+
+unique_modes__check_par_conj_0(NonLocalVarsBag, ModeInfo0, ModeInfo) :-
+	bag__to_assoc_list(NonLocalVarsBag, NonLocalVarsList),
+	list__filter_map((pred(Pair::in, Var::out) is semidet :-
+		Pair = Var - Multiplicity,
+		Multiplicity > 1
+	), NonLocalVarsList, SharedList),
+	mode_info_dcg_get_instmap(InstMap0, ModeInfo0, ModeInfo1),
+	instmap__lookup_vars(SharedList, InstMap0, VarInsts),
+	mode_info_get_module_info(ModeInfo1, ModuleInfo0),
+	make_shared_inst_list(VarInsts, ModuleInfo0,
+		SharedVarInsts, ModuleInfo1),
+	mode_info_set_module_info(ModeInfo1, ModuleInfo1, ModeInfo2),
+	instmap__set_vars(InstMap0, SharedList, SharedVarInsts, InstMap1),
+	mode_info_set_instmap(InstMap1, ModeInfo2, ModeInfo).
+
 	% Just process each conjunct in turn.
 	% Because we have already done modechecking, we know that
 	% there are no attempts to bind a variable in multiple
 	% parallel conjuncts, so we don't need to lock/unlock variables.
+
+:- pred unique_modes__check_par_conj_1(list(hlds_goal), list(hlds_goal),
+		list(pair(instmap, set(prog_var))), mode_info, mode_info).
+:- mode unique_modes__check_par_conj_1(in, out, out,
+		mode_info_di, mode_info_uo) is det.
 
-unique_modes__check_par_conj([], [], []) --> [].
-unique_modes__check_par_conj([Goal0 | Goals0], [Goal | Goals],
+unique_modes__check_par_conj_1([], [], []) --> [].
+unique_modes__check_par_conj_1([Goal0 | Goals0], [Goal | Goals],
 		[InstMap - NonLocals|InstMaps]) -->
 	{ unique_modes__goal_get_nonlocals(Goal0, NonLocals) },
 	mode_info_dcg_get_instmap(InstMap0),
 	unique_modes__check_goal(Goal0, Goal),
 	mode_info_dcg_get_instmap(InstMap),
 	mode_info_set_instmap(InstMap0),
-	unique_modes__check_par_conj(Goals0, Goals, InstMaps).
+	unique_modes__check_par_conj_1(Goals0, Goals, InstMaps).
 
 %-----------------------------------------------------------------------------%
 
Index: par_conj_gen.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/par_conj_gen.m,v
retrieving revision 1.4
diff -u -r1.4 par_conj_gen.m
--- par_conj_gen.m	1999/04/16 06:04:48	1.4
+++ par_conj_gen.m	1999/08/30 01:39:49
@@ -68,7 +68,13 @@
 % conjunction, determinism analysis works by inferring the determinism of
 % each conjunct and reporting an error if it is not a model_det determinism.
 %
-% XXX Unique modes
+% We conservatively require that any variable that is nonlocal to more
+% than one parallel conjunct become shared at the start of the parallel
+% conjunction. This avoids problems where one conjunct has a use in a
+% di mode and another in a ui mode. This would introduce an implicit
+% dependency between the two conjuncts, which at present is illegal,
+% since parallel conjunction is currently *independent* parallel
+% conjunction only.
 %
 % The code generated for a parallel conjunction consists of a piece of
 % initialization code which creates a term on the heap to be used for
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------