[m-dev.] for review: alias branch improvements [1/2]

[Fergus Henderson]

On 23-Jul-1999, David Overton <dmo at cs.mu.OZ.AU> wrote:
> Improve handling of aliasing in the modes of procedure arguments, in
> particular for unification procedures.
> Re-organise the inst_table and place it in a new module together with
> the predicates that operate on it.
...
> compiler/inst_table.m:
> 	New module for the inst_table and related stuff.  Changed the
> 	substitution_inst_table to a more generally useful
> 	other_inst_table which can be used by many transformations that
> 	turn one recursive inst into another.
> 	Having this new module allows parts of the inst_table to
> 	become more abstract by including all predicates that operate
> 	on the inst_table as a whole in the same module.
> 	It also means that prog_data no longer needs to import
> 	hlds_data just to get the definition of the inst_table type.

You also changed the code which you moved to inst_table.m to use typeclasses.
I think this warrants a mention in the log message,
particularly since this is the first use of typeclasses in the compiler.

inst_match.m:
>  pred_inst_matches_2(
> -		pred_inst_info(PredOrFunc, argument_modes(_InstTableA, ModesA),
> +		pred_inst_info(PredOrFunc, argument_modes(InstTableA, ModesA),
>  				Det),
>  		InstMapA,
> -		pred_inst_info(PredOrFunc, argument_modes(_InstTableB, ModesB),
> +		pred_inst_info(PredOrFunc, argument_modes(InstTableB, ModesB0),
>  				Det),
> -		InstMapB, InstTable, ModuleInfo, Expansions) :-
> -	% XXX This is incorrect in the case where the pred insts have
> -	%     aliasing in their argument_modes.
> +		InstMapB, _InstTable, ModuleInfo, Expansions) :-
> +	inst_table_create_sub(InstTableA, InstTableB, Sub, InstTable),
> +	list__map(apply_inst_table_sub_mode(Sub), ModesB0, ModesB),
> +	map__init(AliasMap0),
>  	pred_inst_argmodes_matches(ModesA, InstMapA, ModesB, InstMapB,
> -			InstTable, ModuleInfo, Expansions).
> +		InstTable, ModuleInfo, Expansions, AliasMap0, AliasMap0).

I think a comment explaining the code here would be helpful.

> +:- pred inst_matches_aliasing(bool, inst, inst, alias_map, alias_map).
> +:- mode inst_matches_aliasing(in, in, in, in, out) is semidet.
> +
> +inst_matches_aliasing(yes, _, _, AliasMap, AliasMap).
> +inst_matches_aliasing(no, InstA, InstB, AliasMap0, AliasMap) :-
> +	( InstB = alias(IKB) ->
> +		( map__search(AliasMap0, IKB, MaybeIK) ->
> +			MaybeIK = yes(IKA),
> +			InstA = alias(IKA),
> +			AliasMap = AliasMap0
> +		; InstA = alias(IKA) ->
> +			map__det_insert(AliasMap0, IKB, yes(IKA), AliasMap)
> +		;
> +			map__det_insert(AliasMap0, IKB, no, AliasMap)
> +		)
> +	;
> +		AliasMap = AliasMap0
> +	).

You should document the meaning of this predicate.
In particular, the meaning of the first parameter should be explained.
Also, why are InstA and InstB treated assymetrically here?

inst_table.m:
> +inst_table_create_sub(InstTable0, NewInstTable, Sub, InstTable) :-
> +	inst_table_get_all_tables(InstTable0, UnifyInstTable0, MergeInstTable0,
> +		GroundInstTable0, AnyInstTable0, SharedInstTable0,
> +		ClobberedInstTable0, MostlyUniqInstTable0, OtherInstTable0,
> +		IKT0),
> +	inst_table_get_all_tables(NewInstTable, NewUnifyInstTable,
> +		NewMergeInstTable, NewGroundInstTable, NewAnyInstTable,
> +		NewSharedInstTable, NewMostlyUniqInstTable,
> +		NewClobberedInstTable, NewOtherInstTable, NewIKT),
> +	inst_key_table_create_sub(IKT0, NewIKT, IKSub, IKT),
> +	OtherInstTable0 = other_inst_table(Id0, OtherInsts0),
> +	OtherInstIdSub = other_inst_id_create_sub(Id0),
> +	Sub = inst_table_sub(IKSub, OtherInstIdSub),
> +
> +	map_apply_sub(Sub, UnifyInstTable0, NewUnifyInstTable, UnifyInstTable),
> +	map_apply_sub(Sub, MergeInstTable0, NewMergeInstTable, MergeInstTable),
> +	map_apply_sub(Sub, GroundInstTable0, NewGroundInstTable,
> +		GroundInstTable),
> +	map_apply_sub(Sub, AnyInstTable0, NewAnyInstTable, AnyInstTable),
> +	map_apply_sub(Sub, SharedInstTable0, NewSharedInstTable,
> +		SharedInstTable),
> +	map_apply_sub(Sub, MostlyUniqInstTable0, NewMostlyUniqInstTable,
> +		MostlyUniqInstTable),
> +	map_apply_sub(Sub, ClobberedInstTable0, NewClobberedInstTable,
> +		ClobberedInstTable),
> +
> +	NewOtherInstTable = other_inst_table(NewId, NewOtherInsts),
> +	map_apply_sub(Sub, OtherInsts0, NewOtherInsts, OtherInsts),
> +	OtherInstId = other_inst_id_apply_sub(OtherInstIdSub, NewId),
> +	OtherInstTable = other_inst_table(OtherInstId, OtherInsts),
> +
> +	inst_table_set_all_tables(InstTable0, UnifyInstTable,
> +		MergeInstTable, GroundInstTable, AnyInstTable,
> +		SharedInstTable, MostlyUniqInstTable, ClobberedInstTable,
> +		OtherInstTable, IKT, InstTable).
> +
> +:- pred maybe_inst_apply_sub(inst_table_sub, maybe_inst, maybe_inst).
> +:- mode maybe_inst_apply_sub(in, in, out) is det.
> +
> +maybe_inst_apply_sub(_, unknown, unknown).
> +maybe_inst_apply_sub(Sub, known(I0), known(I)) :-
> +	inst_apply_inst_table_sub(Sub, I0, I).
> +
> +:- pred maybe_inst_det_apply_sub(inst_table_sub, maybe_inst_det,
> +		maybe_inst_det).
> +:- mode maybe_inst_det_apply_sub(in, in, out) is det.
> +
> +maybe_inst_det_apply_sub(_, unknown, unknown).
> +maybe_inst_det_apply_sub(Sub, known(I0, D), known(I, D)) :-
> +	inst_apply_inst_table_sub(Sub, I0, I).
> +
> +:- pred merge_inst_pair_apply_sub(inst_table_sub, merge_inst_pair,
> +		merge_inst_pair).
> +:- mode merge_inst_pair_apply_sub(in, in, out) is det.
> +
> +merge_inst_pair_apply_sub(Sub, Pair0, Pair) :-
> +	Pair0 = merge_inst_pair(IsLive, IA0, IB0),
> +	inst_apply_inst_table_sub(Sub, IA0, IA),
> +	inst_apply_inst_table_sub(Sub, IB0, IB),
> +	Pair = merge_inst_pair(IsLive, IA, IB).
> +
> +:- pred other_inst_apply_sub(inst_table_sub, other_inst, other_inst).
> +:- mode other_inst_apply_sub(in, in, out) is det.
> +
> +other_inst_apply_sub(Sub, other_inst(Id0, Name0), other_inst(Id, Name)) :-
> +	Sub = inst_table_sub(_IKSub, IdSub),
> +	Id = other_inst_id_apply_sub(IdSub, Id0),
> +	inst_name_apply_sub(Sub, Name0, Name).
> +
> +:- pred map_apply_sub(inst_table_sub, map(K, V), map(K, V), map(K, V)) 
> +		<= (inst_table_entry(K), inst_table_entry(V)).
> +:- mode map_apply_sub(in, in, in, out) is det.
> +
> +map_apply_sub(Sub, Map0, NewMap, Map) :-
> +	map__foldl((pred(K0::in, V0::in, M0::in, M::out) is det :-
> +			inst_table_entry_apply_sub(Sub, K0, K),
> +			inst_table_entry_apply_sub(Sub, V0, V),
> +			map__set(M0, K, V, M)),
> +		NewMap, Map0, Map).
> +
> +:- typeclass inst_table_entry(T) where [
> +	pred inst_table_entry_apply_sub(inst_table_sub, T, T),
> +	mode inst_table_entry_apply_sub(in, in, out) is det
> +].
> +
> +:- instance inst_table_entry(inst_name) where [
> +	pred(inst_table_entry_apply_sub/3) is inst_name_apply_sub
> +].
> +
> +:- instance inst_table_entry(maybe_inst) where [
> +	pred(inst_table_entry_apply_sub/3) is maybe_inst_apply_sub
> +].
> +
> +:- instance inst_table_entry(maybe_inst_det) where [
> +	pred(inst_table_entry_apply_sub/3) is maybe_inst_det_apply_sub
> +].
> +
> +:- instance inst_table_entry(merge_inst_pair) where [
> +	pred(inst_table_entry_apply_sub/3) is merge_inst_pair_apply_sub
> +].
> +
> +:- instance inst_table_entry(other_inst) where [
> +	pred(inst_table_entry_apply_sub/3) is other_inst_apply_sub
> +].
> +
> +:- pred inst_name_apply_sub(inst_table_sub, inst_name, inst_name).
> +:- mode inst_name_apply_sub(in, in, out) is det.

Just a minor point: the ordering of the code seems a little inconsistent
here.  Why is inst_name_apply_sub defined after the typeclass and instance
declarations, whereas the other predicates maybe_inst*_apply_sub
and other_inst_apply_sub are defined before the typeclass declaration?

I suggest moving the definitions of maybe_inst*_apply_sub and
other_inst_apply_sub to the end of the file.

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