[m-dev.] for review: retain aliasing information when merging instmaps of branched goals

[Fergus Henderson]

On 16-Dec-1998, David Overton <dmo at cs.mu.OZ.AU> wrote:
> Modify `instmap__merge' and `inst_merge' to preserve as much definite 
> aliasing information as possible rather than just throwing it all away 
> at the end of branched goals.
...

inst_util.m:

> +:- type substitution_inst
> +	--->	substitution_inst(inst_name, set_bbbtree(inst_key),
> +			inst_key_sub).

If the `set_bbbtree(inst_key)' type is used in other places,
it might be a good idea to abstract this a little via

	:- type inst_key_set == set_bbbtree(inst_key).

> +:- type inst_fold_pred(T) == pred(inst, set(inst_name), T, T).
> +:- mode inst_fold_pred :: (pred(in, in, in, out) is semidet).
> +
> +%	inst_fold(InstMap, InstTable, ModuleInfo, Before, After, Inst, T0, T)
> +% 		Recursively traverse Inst calling Before before recursive
> +%		calls and After after recursive calls.  Traverses sub insts
> +%		of `bound' and `abstract_inst' and expands and traverses
> +%		`alias' and `defined_inst'.

Hmm, `abstract_inst's won't have any sub-insts, will they?

(Also I suggest s/sub inst/sub-inst/)

> +abstractly_unify_inst_functor_2(dead, Real, bound(Uniq, ListX), ConsId, Args0,
> +			_ArgLives, UI0, bound(Uniq, List), Args, Det, UI) :-
> +	ListY = [functor(ConsId, Args0)],
>  	abstractly_unify_bound_inst_list(dead, ListX, ListY, Real, UI0,
> -		List, Det, UI).
> +		List, Det, UI),
> +	( List = [functor(_, Args1)] ->
> +		Args = Args1
> +	; List = [] ->
> +		Args = Args0

Hmm, in this case, where the final inst of the term is `bound([])',
it might be better to set the insts of the term and and all the args
to `not_reached'.  On the other hand, maybe we already do that propagation
of bound([]) ==> not_reached somewhere else.  If so, a comment would
be helpful.

> @@ -1424,9 +1461,8 @@
>  		% expand the inst name, and invoke ourself recursively on
>  		% it's expansion
>  		unify_inst_info_get_module_info(UI1, ModuleInfo1),
> -		unify_inst_info_get_instmap(UI1, InstMap1),
>  		inst_lookup(InstTable1, ModuleInfo1, InstName, Inst0),
> -		inst_expand(InstMap1, InstTable1, ModuleInfo1, Inst0, Inst1),
> +		inst_expand_defined_inst(InstTable1, ModuleInfo1, Inst0, Inst1),
>  		make_shared_inst(Inst1, UI1, SharedInst, UI2),

The log message didn't explain that change.

> @@ -1529,9 +1565,8 @@
>  		% expand the inst name, and invoke ourself recursively on
>  		% it's expansion
>  		unify_inst_info_get_module_info(UI1, ModuleInfo1),
> -		unify_inst_info_get_instmap(UI1, InstMap1),
>  		inst_lookup(InstTable1, ModuleInfo1, InstName, Inst0),
> -		inst_expand(InstMap1, InstTable1, ModuleInfo1, Inst0, Inst1),
> +		inst_expand_defined_inst(InstTable1, ModuleInfo1, Inst0, Inst1),
>  		make_mostly_uniq_inst_2(Inst1, UI1, NondetLiveInst, UI2),

Likewise.

> +	% YYY The InstMap returned from this may be bogus.
> +inst_merge(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, MergeSubs0, Inst,
> +			InstMap, InstTable, ModuleInfo, MergeSubs) :-

Hmm, that comment is a bit worrying.  Could you explain in a bit more
detail when and why it might be bogus?

> @@ -1652,10 +1690,12 @@
...
> -			% now update the value associated with ThisInstPair
> +			% now update the value associated with
> +			% ThisInstPair

Better the old way, IMHO.

> +inst_merge_2(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, MergeSubs0, Inst,
> @@ -1692,29 +1732,105 @@
...
> +		InstA2 = alias(IKA0),
> +		InstB2 \= alias(_)
> +	->
> +		UI0 = unify_inst_info(ModuleInfo0, InstTable0, InstMap0),
> +		make_shared_inst(InstA2, UI0, InstA3, UI1),
> +		solutions(lambda([I::out] is nondet, (
> +			map__member(MergeSubs0, IKA0 - _, MergeIK),
> +			I = alias(MergeIK))), Insts),
> +		make_shared_inst_list(Insts, UI1, _, UI),
> +		UI = unify_inst_info(ModuleInfo1, InstTable1, InstMap1),
> +		InstA3 = alias(IKA),
> +		inst_table_get_inst_key_table(InstTable1, IKT0),
> +		instmap__inst_key_table_lookup(InstMap1, IKT0, IKA, InstA4),
> +		inst_merge_3(InstA4, InstB2, InstMap1, InstTable1, ModuleInfo1,
> +			MergeSubs0, Inst, InstMap, InstTable, ModuleInfo,
> +			MergeSubs)
> +	;
> +		InstB2 = alias(IKB0),
> +		InstA2 \= alias(_)
> +	->
> +		UI0 = unify_inst_info(ModuleInfo0, InstTable0, InstMap0),
> +		make_shared_inst(InstB2, UI0, InstB3, UI1),
> +		solutions(lambda([I::out] is nondet, (
> +			map__member(MergeSubs0, _ - IKB0, MergeIK),
> +			I = alias(MergeIK))), Insts),
> +		make_shared_inst_list(Insts, UI1, _, UI),
> +		UI = unify_inst_info(ModuleInfo1, InstTable1, InstMap1),
> +		InstB3 = alias(IKB),
> +		inst_table_get_inst_key_table(InstTable1, IKT0),
> +		instmap__inst_key_table_lookup(InstMap1, IKT0, IKB, InstB4),
> +		inst_merge_3(InstA2, InstB4, InstMap1, InstTable1, ModuleInfo1,
> +			MergeSubs0, Inst, InstMap, InstTable, ModuleInfo,
> +			MergeSubs)
> +	;

The duplicate code there ought to be factored out into a new
predicate.

> +	% YYY Returned instmaps are completely bogus here.
> +
> +inst_merge_3(any(UniqA), any(UniqB), InstMap, InstTable, M, MS, any(Uniq),
> +		InstMap, InstTable, M, MS) :-

If the returned instmaps are bogus, why return them?

[... to be continued.]

-- 
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.