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

[Andrew Bromage]

G'day all.

You (David Overton) wrote:

> Do you have time to review this at the moment?  If not, would someone
> else mind looking at it?

Owing to time constraints, I've only looked for for structural
weaknesses rather than typos and style issues.  (Which is probably
what you wanted out of me.)

> compiler/modecheck_unify.m:
> 	Modify `mode_info_make_aliased_insts' to only make aliases for
> 	insts of live variables.  This should significantly reduce the
> 	number of aliases that we need to keep track of.

Will this have bad implications for structure reuse?  You have to look
at the modes of dead variables there.

> compiler/simplify.m:
> 	Re-order a conjuction in predicate simplify__goal_2. (Andrew did
> 	this and I'm not sure why).

I'm pretty sure that it's because at one point I moved that unification
inside the comment (along with other changes which have since been undone).

> Index: inst_util.m
> ===================================================================

> @@ -1628,8 +1664,9 @@
>  	%       InstB specify a binding (free or bound), it must be
>  	%       the same in both.
>  
> -inst_merge(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, Inst, InstMap,
> -			InstTable, ModuleInfo) :-
> +	% YYY The InstMap returned from this may be bogus.
> +inst_merge(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, MergeSubs0, Inst,
> +			InstMap, InstTable, ModuleInfo, MergeSubs) :-

This was true in the development version.  Is it still true?

> -:- pred inst_merge_2(inst, inst, instmap, inst_table, module_info,
> -		inst, instmap, inst_table, module_info).
> -:- mode inst_merge_2(in, in, in, in, in, out, out, out, out) is semidet.
> +:- pred inst_merge_2(inst, inst, instmap, inst_table, module_info, merge_subs,
> +		inst, instmap, inst_table, module_info, merge_subs).
> +:- mode inst_merge_2(in, in, in, in, in, in, out, out, out, out, out)
> +		is semidet.
>  
> -inst_merge_2(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, Inst,
> -		InstMap, InstTable, ModuleInfo) :-
> +inst_merge_2(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, MergeSubs0, Inst,
> +		InstMap, InstTable, ModuleInfo, MergeSubs) :-
>  /*********
>  		% would this test improve efficiency??
>  	( InstA = InstB ->
> @@ -1682,8 +1723,7 @@
>  		Inst = InstA,
>  		ModuleInfo = ModuleInfo0
>  	;
> -*********/
> -	%     fixed!
> +	************/
>  	inst_expand_defined_inst(InstTable0, ModuleInfo0, InstA, InstA2),
>  	inst_expand_defined_inst(InstTable0, ModuleInfo0, InstB, InstB2),
>  	(
> @@ -1692,29 +1732,105 @@
>  		Inst = InstA2,
>  		ModuleInfo = ModuleInfo0,
>  		InstTable = InstTable0,
> -		InstMap = InstMap0
> +		InstMap = InstMap0,
> +		MergeSubs = MergeSubs0
>  	;
> -		InstA2 = alias(IKA)
> +		InstA2 = not_reached
>  	->
> -		inst_table_get_inst_key_table(InstTable0, IKT0),
> -		instmap__inst_key_table_lookup(InstMap0, IKT0, IKA, InstA3),
> -		inst_merge_3(InstA3, InstB2, InstMap0, InstTable0, ModuleInfo0,
> -			Inst, InstMap, InstTable, ModuleInfo)
> +		Inst = InstB2,
> +		ModuleInfo = ModuleInfo0,
> +		InstTable = InstTable0,
> +		InstMap = InstMap0,
> +		MergeSubs = MergeSubs0
>  	;
> +		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)
> +	;
> +		InstA2 = alias(IKA),
>  		InstB2 = alias(IKB)
>  	->
> +		(
> +		    instmap__inst_keys_are_equivalent(IKA, InstMap0,
> +			IKB, InstMap0)
> +		->
> +		    Inst = alias(IKA),
> +		    InstTable = InstTable0,
> +		    ModuleInfo = ModuleInfo0,
> +		    InstMap = InstMap0,
> +		    map__set(MergeSubs0, IKA - IKB, IKA, MergeSubs)
> +		;
> +		    ( map__search(MergeSubs0, IKA - IKB, IK0) ->
> +			IK = IK0,
> +			InstTable = InstTable0,
> +			ModuleInfo = ModuleInfo0,
> +			InstMap = InstMap0,
> +			MergeSubs = MergeSubs0
> +		    ;
>  		inst_table_get_inst_key_table(InstTable0, IKT0),
> -		instmap__inst_key_table_lookup(InstMap0, IKT0, IKB, InstB3),
> -		inst_merge_3(InstA2, InstB3, InstMap0, InstTable0, ModuleInfo0,
> -			Inst, InstMap, InstTable, ModuleInfo)
> +			instmap__inst_key_table_lookup(InstMap0, IKT0, IKA,
> +			    InstA3),
> +			instmap__inst_key_table_lookup(InstMap0, IKT0, IKB,
> +			    InstB3),
> +			inst_merge_3(InstA3, InstB3, InstMap0, InstTable0,
> +			    ModuleInfo0, MergeSubs0, Inst0, InstMap, InstTable1,
> +			    ModuleInfo, MergeSubs1),
> +			( map__search(MergeSubs1, IKA - IKB, IK1) ->
> +			    IK = IK1,
> +			    MergeSubs = MergeSubs1,
> +			    InstTable = InstTable1
> +			;
> +			    % Create a new inst key for the merged inst.
> +			    inst_table_get_inst_key_table(InstTable1, IKT1),
> +			    inst_key_table_add(IKT1, Inst0, IK, IKT),
> +			    inst_table_set_inst_key_table(InstTable1, IKT,
> +				InstTable),
> +			    map__det_insert(MergeSubs1, IKA - IKB, IK,
> +				MergeSubs)
> +			)
> +		    ),
> +		    Inst = alias(IK)
> +		)

OK, here is where the instmaps get bogus.  If, say, an inst_key from
before the branched goal is updated in some branch of that goal (say, a
unique object becomes shared in one branch), the instmap at the end of
the merge point needs its alias_map updated to reflect the changed
inst_key.  (The rest of the mode system just pretends there was an
abstract unification which aliased and shared the inst_key inside the
goal.)

I think you could get away with fixing up the instmaps as a post-pass,
using the merge_subs to get the information.

> Index: instmap.m
> ===================================================================

> +:- type uniq_count
> +	--->	zero
> +	;	one
> +	;	many.
> +
> +:- type uniq_counts(T) == map(T, uniq_count).
> +
> +:- pred inc_uniq_count(T, uniq_counts(T), uniq_counts(T)).
> +:- mode inc_uniq_count(in, in, out) is det.

I realise that we don't do much "counting" abstract analysis yet, but
this looks like an opportunity for type classes, if we ever have to do
something similar in future.  Don't worry about this now, naturally. :-)

Thanks, David.

Cheers,
Andrew Bromage