For review: parallel conjunction compiler diff.

[Fergus Henderson]

Hi Tom,

I'm glad to see we're making progress.

When you have addressed the comments below, can you please send/post a
diff from the version as of this diff.

conway at mundook.cs.mu.OZ.AU (Thomas Charles CONWAY) writes:

 >+			io__write_string("( % parallel conjunction\n"),
 >+			hlds_out__write_conj(Goal, Goals, ModuleInfo, VarSet,
 >+				AppendVarnums, Indent1, "", Verbose, "&\n",
 >+				TypeQual),
 > 			hlds_out__write_indent(Indent),
 > 			io__write_string(")"),
 > 			io__write_string(Follow),
 > 			io__write_string("\n")
 > 		;
 > 			hlds_out__write_conj(Goal, Goals, ModuleInfo, VarSet,
 >-				AppendVarnums, Indent, Follow, Verbose,
 >+				AppendVarnums, Indent, Follow, Verbose, "&\n",
 > 				TypeQual)

s/&/ &/g

 >+	(
 >+		List = [],
 >+		Inst = not_reached
 >+	;
 >+		List = [_|_],
 >+		Inst = bound(Uniq, List)
 >+	).

Don't duplicate that code four times; use a subroutine.

 > 	% merge_instmap_delta(InitialInstMap, NonLocals,
 > 	%	InstMapDeltaA, InstMapDeltaB, ModuleInfo0, ModuleInfo)
 >-	% Merge the instmap_deltas of different branches of an ite, disj
 >-	% or switch.
 >+	% Merge the instmap_deltas of different branches of an if-then-else,
 >+	% disj or switch.
 > :- pred merge_instmap_delta(instmap, set(var), instmap_delta, instmap_delta,
 > 		instmap_delta, module_info, module_info).
 > :- mode merge_instmap_delta(in, in, in, in, out, in, out) is det.
 > 
 >+	% join_instmap_delta(InitialInstMap, NonLocals,
 >+	%	InstMapDeltaA, InstMapDeltaB, ModuleInfo0, ModuleInfo)
 >+	% Merge the instmap_deltas of different branches of an if-then-else,
 >+	% disj or switch.
 >+:- pred join_instmap_delta(instmap, set(var), instmap_delta, instmap_delta,
 >+		instmap_delta, module_info, module_info).
 >+:- mode join_instmap_delta(in, in, in, in, out, in, out) is det.

Hmm, the documentation for these two is suspiciously similar.
You should document the differences.

 >+	% instmap_join_var(InstMaps, Var, InitialInstMap, ModuleInfo,
 >+	%		Insts, Error):
 >+	%       Let `Insts' be the list of the inst of `Var' in the
 >+	%       corresponding `InstMaps'.  Let `Error' be yes iff
 >+	%       there are two instmaps for which the inst of `Var'
 >+	%       is incompatible.
 >+
 >+:- pred instmap__unify_var(list(instmap), var, (inst), module_info,
 >+				list(inst), inst, module_info, bool).
 >+:- mode instmap__unify_var(in, in, in, in, out, out, out, out) is det.

The name in the documentation doesn't match the name in the declaration.

Probably the name `unify' is better, but you need to make that change
consistently here and in other places.

 >+instmap__unify_var([], _, InitialInst, ModuleInfo, [],
 >+		InitialInst, ModuleInfo, no).
 >+instmap__unify_var([InstMap | InstMaps], Var, InitialVarInst, ModuleInfo0,
 >+		InstList, Inst, ModuleInfo, Error) :-
 >+	instmap__unify_var(InstMaps, Var, InitialVarInst, ModuleInfo0,
 >+		InstList0, Inst0, ModuleInfo1, Error0),

You should make this tail-recursive.

 >+	instmap__lookup_var(InstMap, Var, VarInst),
 >+	InstList = [VarInst | InstList0],
 >+	(
 >+		abstractly_unify_inst(live, Inst0, VarInst, fake_unify,
 >+			ModuleInfo1, Inst1, _Det, ModuleInfo2)
 >+	->

Are you sure it is safe to ignore `_Det' here?
If that's deliberate, I think it might be worth documenting why.
(Ditto for join_instmapping_delta_2.)

 >+	;
 >+		% Value numbering doesn't handle fork [yet] so
 >+		% set DontValueNumber to yes.
 >+		Uinstr0 = fork(_, _, _),
 >+		Livemap = Livemap0,
 >+		Livevals = Livevals0,
 >+		Instrs = Instrs0,
 >+		DontValueNumber = yes
 >+	;
 >+		% Value numbering doesn't handle join_and_terminate [yet] so
 >+		% set DontValueNumber to yes.
 >+		Uinstr0 = join_and_terminate(_),
 >+		Livemap = Livemap0,
 >+		Livevals = Livevals0,
 >+		Instrs = Instrs0,
 >+		DontValueNumber = yes
 >+	;
 >+		% Value numbering doesn't handle join_and_continue [yet] so
 >+		% set DontValueNumber to yes.
 >+		Uinstr0 = join_and_continue(_, _),
 >+		Livemap = Livemap0,
 >+		Livevals = Livevals0,
 >+		Instrs = Instrs0,
 >+		DontValueNumber = yes

These comments deserve an XXX, IMHO.

 >+mercury_output_goal_2((A & B), VarSet, Indent) -->
 >+	mercury_output_goal(A, VarSet, Indent),
 >+	io__write_string(" &"),
 >+	mercury_output_newline(Indent),
 >+	mercury_output_goal(B, VarSet, Indent).

That is a bug!  You need to output some parentheses.

 >+modecheck_par_conj_list([], [], _NonLocals, []) --> [].
 >+modecheck_par_conj_list([Goal0|Goals0], [Goal|Goals], NonLocals, 
 >+		[InstMap|InstMaps]) -->
 >+	mode_info_dcg_get_instmap(InstMap0),
 >+	modecheck_goal(Goal0, Goal),
 >+	mode_info_dcg_get_instmap(InstMap),
 >+	mode_info_set_instmap(InstMap0),
 >+	=(ModeInfo),
 >+	{ mode_info_get_module_info(ModeInfo, ModuleInfo) },
 >+	{ find_bound_vars(NonLocals, InstMap0, InstMap, ModuleInfo, LockVars) },
 >+		% Any variables that got bound in this parallel conjunct are
 >+		% locked to prevent them being bound in any other conjunct.
 >+	mode_info_lock_vars(LockVars),
 >+	modecheck_par_conj_list(Goals0, Goals, NonLocals, InstMaps),
 >+	mode_info_unlock_vars(LockVars).

The problem with using lock_vars is that the diagnostics will be really
untolerably awful.  Please fix this.

 >+	% find_bound_vars returns the set of variables that became more
 >+	% instantiated from the initial instmap to the final instmap.
 >+:- pred find_bound_vars(list(var), instmap, instmap, module_info, set(var)).
 >+:- mode find_bound_vars(in, in, in, in, out) is det.
 >+
 >+find_bound_vars([], _, _, _, Empty) :-
 >+	set__init(Empty).
 >+find_bound_vars([Var|Vars], Initial, Final, ModuleInfo, BoundVars) :-
 >+	find_bound_vars(Vars, Initial, Final, ModuleInfo, BoundVars0),
 >+	instmap__lookup_var(Initial, Var, InitialInst),
 >+	instmap__lookup_var(Final, Var, FinalInst),
 >+	( \+ inst_matches_binding(InitialInst, FinalInst, ModuleInfo) ->
 >+		set__insert(BoundVars0, Var, BoundVars)
 >+	;
 >+		BoundVars = BoundVars0
 >+	).

What happens with something like

	p :-
		(
			X = "foo", error(X)
		&
			X = "bar", error(X)
		).

?

 >+simplify__goal_2(par_conj(Goals0, SM), GoalInfo, Goal, GoalInfo, Info0, Info) :-
 >+	(
 >+		Goals0 = [Goal0]
 >+	->
 >+		simplify__goal(Goal0, Goal - _, Info0, Info)
 >+	;
 >+		simplify__par_conj(Goals0, Goals, Info0, Info0, Info),
 >+		Goal = par_conj(Goals, SM)
 >+	).

It's probably not a bad idea to check for Goals0 = []
and convert that to conj([]).

 >+unique_modes__check_goal_2(par_conj(List0, SM), GoalInfo0,
 >+		par_conj(List, SM)) -->
 >+	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),
 >+	instmap__unify(NonLocals, InstMapList),
 >+	mode_checkpoint(exit, "par_conj").
...
 >+	% Just process each conjunct in turn.
 >+	% Note that we don't do any reordering of conjuncts here.
 >+
 >+unique_modes__check_par_conj([], [], []) --> [].
 >+unique_modes__check_par_conj([Goal0 | Goals0], [Goal | Goals],
 >+		[InstMap|InstMaps]) -->
 >+	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).

That is a bug: you are not handling unique modes correctly.
Obviously you need to think about that a little bit harder.
It might help if you wrote the test cases at the same time as
writing the code.

 >+vn_block__handle_instr(fork(_, _, _),
 >+		_Livemap, _Params, VnTables, VnTables, Liveset, Liveset,
 >+		SeenIncr, SeenIncr, Tuple, Tuple) :-
 >+	error("value numbering not supported for fork").
 >+vn_block__handle_instr(join_and_terminate(_),
 >+		_Livemap, _Params, VnTables, VnTables, Liveset, Liveset,
 >+		SeenIncr, SeenIncr, Tuple, Tuple) :-
 >+	error("value numbering not supported for join").
 >+vn_block__handle_instr(join_and_continue(_, _),
 >+		_Livemap, _Params, VnTables, VnTables, Liveset, Liveset,
 >+		SeenIncr, SeenIncr, Tuple, Tuple) :-
 >+	error("value numbering not supported for wait").

Be consistent with the names: is it `wait' or `join_and_continue'?

(Ditto for vn_cost.m.)

 >% A parallel conjunction (A & B) denotes that the goals `A' and `B' should
 >% be executed concurrently. Ideally, parallel conjunction should have exactly
 >% the same declarative semantics as normal conjunction; in practice this is
 >% not quite the case for a couple of reasons:

No, no, it _is_ the case.  The only differences are in the _operational_
semantics.

 >%	- `,'/2 does not quite behave as *logical* conjunction;

This is not true; ','/2 _is_ a sound implementation of logical conjunction.

 >	  by default,
 >%	  conjunctions are not reordered beyond the minimum necessary for
 >%	  mode correctness, so there is definitely an implied ordering in
 >%	  the code.

Not correct. 
Replace with

	  if `--no-reorder-conj' is set, there is an implied ordering
	  in the code:  conjunctions must not be reordered beyond the
	  minimum necessary for mode correctness.

 >%	This is justified for reasons performance modeling.

Ensuring termination -- and avoidance of spurious calls to error/1 --
is a more important issue than performance.

 >%	  Parallel conjunction does not of itself suggest any information
 >%	  about which order two goals should be executed, however if
 >%	  coroutining (not currently implemented) is being used, then the
 >%	  data dependancies between the two goals will constrain the order
 >%	  of execution at runtime.

Is execution required to be done in parallel, i.e.
is `loop & fail' guaranteed to terminate?
I know the current implementation doesn't support semidet, but
you should document the intended operational semantics of
parallel conjunction.
(I think the answer should be `yes'.)

 >% The current implementation only supports independant and-parallelism.
 >% The syntax for parallel conjunction is `&'/2 which behaves like `,'/2
 >% in that sequences get flattened (ie A & (B & C) <=> (A & B) & C).

Incidentally, makes me think of another a question: should `A <=> B' mean
	(a) `A => B, B <= A'
	(b) `A <= B', `B => A'
	(c) either (a) or (b), but it is unspecified which
     or	(d) `A => B & B <= A'?

 >% XXX Unique modes

Please follow our coding standards: the XXX should explain
the reason in terms that those other than the original developer
will understand.


Also, I would like to see lots of test cases for this change.
You should be careful to test all the tricky cases for mode
analysis, determinism analysis, and uniqueness analysis
of parallel conjunctions.

Cheers,
	Fergus.

--
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.