[m-rev.] for review: fix bug with any insts in inst_merge

[Fergus Henderson]

On 11-Sep-2001, David Overton <dmo at cs.mu.OZ.AU> wrote:
> Fix a bug in inst_merge when merging a ground inst with a bound inst
> containing 'any' insts.  Previously,
> 
> 	inst_merge(ground, bound(f(..., any, ...)))
> 
> would return a result of 'any' which is not as accurate as we would
> like (e.g. this problem occurs often in Mercury code generated by the
> HAL compiler).  To improve this, we pass the type of the variable
> being merged to inst_merge and when this situation arises we expand
> 'ground' to 'bound(<functors of type>)' and use this inst in the
> merge.

That looks fine.

Just a few minor comments:

> An alternative to passing the types through inst_merge would be to
> reinstate the use of 'typed_inst' and 'typed_ground' which are created
> by (currently commented out) code in 'propagate_types_into_insts'.
> However, this has previously been found to cause performance problems
> since it greatly expands the size of all insts and instmaps in the
> program.  The approach used here is the same as that adopted for
> inst_matches_{initial,final} some time ago, where it does not appear
> to have a noticeable performance impact on typical programs.
> 
> compiler/inst_util.m:
> 	Pass types through inst_merge and implement the changes to
> 	inst_merge(ground, bound(...)) described above.
> 
> compiler/inst_match.m:
> compiler/instmap.m:
> compiler/mode_util.m:
> compiler/simplify.m:
> 	Pass types to calls to inst_merge.
> 
> compiler/inst_match.m:
> compiler/type_util.m:
> 	Move 'maybe_get_cons_id_arg_types' and
> 	'maybe_get_higher_order_arg_types' from inst_match.m to
> 	type_util.m and export them.
> 
> compiler/mode_util.m:
> 	Export 'constructors_to_bound_insts'.
> 
> tests/valid/Mmakefile:
> tests/valid/merge_ground_any.m :
> 	Add a regression test.
> 
> tests/invalid/Mmakefile:
> tests/invalid/merge_ground_any.err_exp:
> tests/invalid/merge_ground_any.m:
> 	Add a test to make sure the ground inst is expanded out to the
> 	full set of functors for the type.
> Index: compiler/inst_match.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/inst_match.m,v
> retrieving revision 1.46
> diff -u -r1.46 inst_match.m
> --- compiler/inst_match.m	13 Oct 2000 13:55:28 -0000	1.46
> +++ compiler/inst_match.m	11 Sep 2001 00:25:08 -0000
> @@ -344,7 +344,7 @@
>  	bound_inst_list_is_ground(ListA, Info^module_info),
>  	bound_inst_list_matches_uniq(ListA, UniqB, Info^module_info).
>  inst_matches_initial_3(bound(UniqA, ListA),
> -		ground(UniqB, constrained_inst_var(InstVarB)), _,
> +		ground(UniqB, constrained_inst_var(InstVarB)), MaybeType,
>  		Info0, Info) :-
>  	unique_matches_initial(UniqA, UniqB),
>  	ModuleInfo0 = Info0^module_info,
> @@ -358,7 +358,8 @@
>  	Live = dead,
>  	abstractly_unify_inst(Live, bound(UniqA, ListA), ground(UniqB, none),
>  		fake_unify, ModuleInfo0, Inst, _Det, ModuleInfo1),
> -	update_inst_var_sub(InstVarB, Inst, ModuleInfo1, ModuleInfo, Sub0, Sub),
> +	update_inst_var_sub(InstVarB, Inst, MaybeType, ModuleInfo1, ModuleInfo,
> +		Sub0, Sub),
>  	Info = (Info0^module_info := ModuleInfo)
>  		^sub := Sub.
>  inst_matches_initial_3(bound(Uniq, List), abstract_inst(_,_), _, Info, Info) :-
> @@ -506,18 +507,19 @@
>  	% Update the inst_var_sub that is computed by inst_matches_initial.
>  	% The inst_var_sub records what inst should be substituted for each
>  	% inst_var that occurs in the called procedure's argument modes.
> -:- pred update_inst_var_sub(inst_var, inst, module_info, module_info,
> -		maybe(inst_var_sub), maybe(inst_var_sub)).
> -:- mode update_inst_var_sub(in, in, in, out, in, out) is semidet.
> +:- pred update_inst_var_sub(inst_var, inst, maybe(type), module_info,
> +		module_info, maybe(inst_var_sub), maybe(inst_var_sub)).
> +:- mode update_inst_var_sub(in, in, in, in, out, in, out) is semidet.
>  
> -update_inst_var_sub(_, _, ModuleInfo, ModuleInfo, no, no).
> -update_inst_var_sub(InstVar, InstA, ModuleInfo0, ModuleInfo,
> +update_inst_var_sub(_, _, _, ModuleInfo, ModuleInfo, no, no).
> +update_inst_var_sub(InstVar, InstA, MaybeType, ModuleInfo0, ModuleInfo,
>  		yes(Sub0), yes(Sub)) :-
>  	( map__search(Sub0, InstVar, InstB) ->
>  		% If InstVar already has an inst associated with it,
>  		% merge the old inst and the new inst.  Fail if this merge
>  		% is not possible.
> -		inst_merge(InstA, InstB, ModuleInfo0, Inst, ModuleInfo),
> +		inst_merge(InstA, InstB, MaybeType, ModuleInfo0, Inst,
> +			ModuleInfo),
>  		map__det_update(Sub0, InstVar, Inst, Sub)
>  	;
>  		ModuleInfo = ModuleInfo0,
> @@ -534,15 +536,15 @@
>  
>  ground_inst_info_matches_initial(_, none, _, _) --> [].
>  ground_inst_info_matches_initial(higher_order(PredInstA),
> -		higher_order(PredInstB), _, Type) -->
> -	pred_inst_matches_initial(PredInstA, PredInstB, Type).
> +		higher_order(PredInstB), _, MaybeType) -->
> +	pred_inst_matches_initial(PredInstA, PredInstB, MaybeType).
>  ground_inst_info_matches_initial(GroundInstInfoA,
> -		constrained_inst_var(InstVarB), UniqB, _) -->
> +		constrained_inst_var(InstVarB), UniqB, MaybeType) -->
>  	{ Inst = ground(UniqB, GroundInstInfoA) },
>  	ModuleInfo0 =^ module_info,
>  	Sub0 =^ sub,
> -	{ update_inst_var_sub(InstVarB, Inst, ModuleInfo0, ModuleInfo,
> -		Sub0, Sub) },
> +	{ update_inst_var_sub(InstVarB, Inst, MaybeType, ModuleInfo0,
> +		ModuleInfo, Sub0, Sub) },
>  	^module_info := ModuleInfo,
>  	^sub := Sub.
>  
> @@ -719,56 +721,6 @@
>  inst_list_matches_initial([X|Xs], [Y|Ys], [Type | Types]) -->
>  	inst_matches_initial_2(X, Y, Type),
>  	inst_list_matches_initial(Xs, Ys, Types).
> -
> -	% If possible, get the argument types for the cons_id.
> -	% We need to pass in the arity rather than using the arity
> -	% from the cons_id because the arity in the cons_id will not
> -	% include any extra type_info arguments for existentially
> -	% quantified types.
> -:- pred maybe_get_cons_id_arg_types(module_info, maybe(type), cons_id,
> -		arity, list(maybe(type))).
> -:- mode maybe_get_cons_id_arg_types(in, in, in, in, out) is det.
> -
> -maybe_get_cons_id_arg_types(ModuleInfo, MaybeType, ConsId0, Arity, MaybeTypes)
> -		:-
> -	( ConsId0 = cons(SymName, _) ->
> -		( SymName = qualified(_, Name) ->
> -			% get_cons_id_non_existential_arg_types
> -			% expects an unqualified cons_id.
> -			ConsId = cons(unqualified(Name), Arity)
> -		;
> -			ConsId = ConsId0
> -		),
> -		(
> -			MaybeType = yes(Type),
> -
> -			% XXX get_cons_id_non_existential_arg_types will fail
> -			% for ConsIds with existentially typed arguments.
> -			get_cons_id_non_existential_arg_types(ModuleInfo, Type,
> -				ConsId, Types),
> -			list__length(Types, Arity)
> -		->
> -			list__map(pred(T::in, yes(T)::out) is det, Types,
> -				MaybeTypes)
> -		;
> -			list__duplicate(Arity, no, MaybeTypes)
> -		)
> -	;
> -		MaybeTypes = []
> -	).
> -
> -:- pred maybe_get_higher_order_arg_types(maybe(type), arity, list(maybe(type))).
> -:- mode maybe_get_higher_order_arg_types(in, in, out) is det.
> -
> -maybe_get_higher_order_arg_types(MaybeType, Arity, MaybeTypes) :-
> -	(
> -		MaybeType = yes(Type),
> -		type_is_higher_order(Type, _, _, Types)
> -	->
> -		list__map(pred(T::in, yes(T)::out) is det, Types, MaybeTypes)
> -	;
> -		list__duplicate(Arity, no, MaybeTypes)
> -	).
>  
>  %-----------------------------------------------------------------------------%
>  
> Index: compiler/inst_util.m
> @@ -1425,9 +1419,12 @@
>  	),
>  	merge_uniq(UniqA, UniqB, Uniq).
>  inst_merge_3(abstract_inst(Name, ArgsA), abstract_inst(Name, ArgsB),
> -		ModuleInfo0, abstract_inst(Name, Args), ModuleInfo) :-
> -	inst_list_merge(ArgsA, ArgsB, ModuleInfo0, Args, ModuleInfo).
> -inst_merge_3(not_reached, Inst, M, Inst, M).
> +		_, ModuleInfo0, abstract_inst(Name, Args), ModuleInfo) :-
> +	MaybeTypes = list__duplicate(list__length(ArgsA), no),
> +		% We don't know the arguments types of an abstract inst.

The comment here should precede the code to which it applies,
rather than following it.

> Index: compiler/type_util.m
...
> +		->
> +			list__map(pred(T::in, yes(T)::out) is det, Types,
> +				MaybeTypes)

I'd write that using the functional form:

			MaybeTypes = list__map(func(T) = yes(T), Types)

> +maybe_get_higher_order_arg_types(MaybeType, Arity, MaybeTypes) :-
> +	(
> +		MaybeType = yes(Type),
> +		type_is_higher_order(Type, _, _, Types)
> +	->
> +		list__map(pred(T::in, yes(T)::out) is det, Types, MaybeTypes)
> +	;
> +		list__duplicate(Arity, no, MaybeTypes)

Likewise here.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------