[m-rev.] [reuse] diff: enable type-widening again

[Nancy Mazur]

Hi,


===================================================================


Estimated hours taken: 4
Branches: reuse

Complete the mechanism of type-widening. When changing the internal
representation of the alias-sets, type-widening was not yet provided. 
This is now done. Also added a new compiler option `possible-alias-widening'
with which one can enable widening (given an integer which states
the limit of the size of the alias-sets, at which point widening is
performed). 

pa_alias_as.m:
pa_alias_set.m:
pa_datastruct.m:
	Completed the code for widening. 
	
pa_run.m:
	Instead of widening within the analysis of procedures, the
	widening is now performed at the end of each fixpoint-run of
	a procedure: if the size of the obtained alias-set is greater
	than the widening-limit, then widening is performed. 
	
options.m:
	Added new option `pa-widening' or `possible-alias-widening'. 



Index: options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.288.2.10
diff -u -r1.288.2.10 options.m
--- options.m	2001/03/13 16:06:45	1.288.2.10
+++ options.m	2001/03/20 17:23:58
@@ -360,6 +360,7 @@
 		;	structure_reuse_constraint
 		;	structure_reuse_constraint_arg
 		;	structure_reuse_selection
+		; 	possible_alias_widening
 	%	- HLDS->LLDS
 		;	smart_indexing
 		;	  dense_switch_req_density
@@ -710,7 +711,9 @@
 
 	structure_reuse_constraint - 	string("within_n_cells_difference"),
 	structure_reuse_constraint_arg - int(0),
-	structure_reuse_selection -	string("lifo")
+	structure_reuse_selection -	string("lifo"),
+	
+	possible_alias_widening - 	int(0)
 ]).
 option_defaults_2(optimization_option, [
 		% Optimization options
@@ -1178,6 +1181,8 @@
 long_option("structure-reuse-constraint-arg",structure_reuse_constraint_arg).
 long_option("sr-selection",		structure_reuse_selection).
 long_option("structure-reuse-selection",structure_reuse_selection).
+long_option("pa-widening", 		possible_alias_widening).
+long_option("possible-alias-widening", 	possible_alias_widening).
 long_option("verbose-check-termination",verbose_check_termination).
 long_option("verb-check-term",		verbose_check_termination).
 long_option("verb-chk-term",		verbose_check_termination).
@@ -1909,6 +1914,11 @@
 		"--structure-reuse-selection",
 		"\tStrategy to decide which of the possible cells available",
 		"\tfor reuse is reused.  Currently lifo or random.",
+
+		"--pa-widening, --possible-alias-widening <n>", 
+		"\tEnable widening when deriving possible aliases.",
+		"\tThe default value = 0 (off). For each n > 0, widening",
+		"\twill be done when the number of aliases exceeds n.",
 
 		"--no-infer-det, --no-infer-determinism",
 		"\tIf there is no determinism declaration for a procedure,",
Index: pa_alias_as.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias_as.m,v
retrieving revision 1.1.2.14
diff -u -r1.1.2.14 pa_alias_as.m
--- pa_alias_as.m	2001/03/15 13:11:36	1.1.2.14
+++ pa_alias_as.m	2001/03/20 17:23:59
@@ -169,6 +169,9 @@
 :- func size(alias_as) = int.
 :- mode size(in) = out is det.
 
+:- pred apply_widening(module_info::in, proc_info::in, alias_as::in, 	
+		alias_as::out) is det. 
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 :- implementation.
@@ -654,7 +657,7 @@
 		{ AS = real_as(Aliases) }
 	->
 		pa_alias_set__print(PredInfo, ProcInfo, Aliases, 
-				"% ", "\n")
+				"\n% ", "")
 	;
 		{ AS = top(Msgs) }
 	->
@@ -819,11 +822,21 @@
 		AS = real_as(AliasList)
 	).
 **/
-
 
-%-------------------------------------------------------------------%
+apply_widening(_, _, A0, A):- 
+	A0 = bottom, 
+	A = A0. 
+apply_widening(_, _, A0, A):- 
+	A0 = top(_), 
+	A = A0. 
+apply_widening(ModuleInfo, ProcInfo, A0, A):- 
+	A0 = real_as(AliasSet0), 
+	pa_alias_set__apply_widening(ModuleInfo, ProcInfo, 
+			AliasSet0, AliasSet), 
+	A = real_as(AliasSet).
+%-----------------------------------------------------------------------------%
 % computing LIVE_SET
-%-------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
 live(ModuleInfo, ProcInfo, IN_USE, LIVE_0, AS, LIVE) :-
 	(
 		set__empty(IN_USE)
Index: pa_alias_set.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias_set.m,v
retrieving revision 1.1.2.1
diff -u -r1.1.2.1 pa_alias_set.m
--- pa_alias_set.m	2001/03/05 17:06:51	1.1.2.1
+++ pa_alias_set.m	2001/03/20 17:24:00
@@ -112,6 +112,9 @@
 :- pred remove_vars( list(prog_var)::in, alias_set::in, 
 		alias_set::out ) is det. 
 
+:- pred apply_widening(module_info::in, proc_info::in, alias_set::in, 
+		alias_set::out) is det.
+
 	% printing predicates
 
 	% print( PredInfo, ProcInfo, AliasSet, StartingString, EndString )
@@ -609,6 +612,14 @@
 	recount( AliasSet1, AliasSet). 
 
 
+apply_widening(ModuleInfo, ProcInfo, AliasSet0, AliasSet):- 
+	alias_set_map_values_with_key(
+		alias_set2_apply_widening(ModuleInfo, ProcInfo),
+		AliasSet0, 
+		AliasSet1), 
+	recount(AliasSet1, AliasSet). 
+	
+
 print( PredInfo, ProcInfo, AliasSet, StartingString, EndString) --> 
 	{ pa_alias_set__to_pair_alias_list( AliasSet, AliasList ) },
 	io__write_list( AliasList, ",", 
@@ -623,20 +634,34 @@
 alias_set_fold(_Pred, AliasSet, AliasSet). 
 	% XXXXXXXXXX
 
-:- pred alias_set_map_values( pred( alias_set2, alias_set2), 
+:- pred alias_set_map_values(pred(alias_set2, alias_set2), 
 			alias_set, alias_set).
-:- mode alias_set_map_values( pred( in, out) is det, in, out ) is det.
-alias_set_map_values( Pred, AliasSet0, AliasSet) :- 
-	AliasSet0 = alias_set( Size, Map0 ), 
+:- mode alias_set_map_values(pred(in, out) is det, in, out) is det.
+alias_set_map_values(Pred, AliasSet0, AliasSet) :- 
+	AliasSet0 = alias_set(Size, Map0), 
 	map__map_values( 
-		pred( _K::in, S0::in, S::out) is det:-
+		pred(_K::in, S0::in, S::out) is det:-
 		    (
 			Pred(S0, S)
 		    ), 
 		Map0, 
 		Map),
-	AliasSet = alias_set( Size, Map ).
+	AliasSet = alias_set(Size, Map).
 
+:- pred alias_set_map_values_with_key(pred(prog_var, alias_set2, alias_set2), 
+			alias_set, alias_set).
+:- mode alias_set_map_values_with_key(pred(in, in, out) is det, 
+			in, out) is det.
+alias_set_map_values_with_key(Pred, AliasSet0, AliasSet) :- 
+	AliasSet0 = alias_set(Size, Map0), 
+	map__map_values( 
+		pred(K::in, S0::in, S::out) is det:-
+		    (
+			Pred(K, S0, S)
+		    ), 
+		Map0, 
+		Map),
+	AliasSet = alias_set(Size, Map).
 			
 	
 
@@ -648,6 +673,7 @@
 :- pred alias_set2_empty( alias_set2 ). 
 :- mode alias_set2_empty( out ) is det.
 :- mode alias_set2_empty( in ) is semidet. 
+:- func alias_set2_init = alias_set2. 
 :- pred alias_set2_new_entry( selector::in, datastruct::in, 
 			alias_set2::in, bool::out, alias_set2::out) is det.
 :- pred alias_set2_new_entry( selector::in, datastruct::in, 
@@ -674,8 +700,11 @@
 			alias_set2::in, alias_set2::out) is det.
 :- pred alias_set2_remove_vars( list(prog_var)::in, alias_set2::in, 
 			alias_set2::out) is det.
+:- pred alias_set2_apply_widening(module_info::in, proc_info::in,
+			prog_var::in, alias_set2::in, alias_set2::out) is det.
 
 alias_set2_empty( alias_sel_set( 0, map__init ) ). 
+alias_set2_init = AliasSet :- alias_set2_empty(AliasSet). 
 
 alias_set2_new_entry( Selector, Datastruct, AliasSet0, Added, AliasSet ):- 
 	AliasSet0 = alias_sel_set( Size0, Map0 ), 
@@ -1004,6 +1033,50 @@
 		Map ), 
 	alias_set2_recount( alias_sel_set( 0, Map), SelectorSet).
 
+alias_set2_apply_widening(ModuleInfo, ProcInfo, ProgVar, 
+		SelectorSet0, SelectorSet):- 
+	SelectorSet0 = alias_sel_set(_, Map0), 
+	map__keys(Map0, Selectors),
+	list__foldl(
+		pred(Sel0::in, M0::in, M::out) is det:- 
+		    (
+			% widening of the associated datastructures
+			map__lookup(Map0, Sel0, DataSet0), 
+			data_set_apply_widening(ModuleInfo, ProcInfo, 
+				DataSet0, DataSet1), 
+
+			% widening of the selector
+			pa_datastruct__create(ProgVar, Sel0, Data0), 
+			pa_datastruct__apply_widening(ModuleInfo, 
+				ProcInfo, Data0, Data), 
+			pa_datastruct__get_selector(Data, Sel), 
+
+			% regroup the widened dataset with the dataset
+			% that is associated with the widened Sel, as this
+			% Sel might already be in M0. 
+			(
+				map__search(M0, Sel, DataSetOld)
+			->
+				% XXX should also take subsumption into 
+				% account !
+				data_set_add(DataSet1, DataSetOld, DataSet)
+			;
+				DataSet = DataSet1
+			), 
+			map__set(M0, Sel, DataSet, M)
+		),
+		Selectors,
+		map__init, 
+		Map1), 
+	% the precaution of checking whether the widened selector might
+	% already be present in the built-up map might not be enough. 
+	% A last check is necessary to be sure that there are no
+	% selectors which are subsumed by other selectors in the list. 
+	proc_info_vartypes(ProcInfo, VarTypes), 
+	map__lookup(VarTypes, ProgVar, VarType), 
+	alias_set2_least_upper_bound(ModuleInfo, VarType, 
+		alias_sel_set(0, Map1), alias_set2_init, SelectorSet). 
+
 
 % data_set
 
@@ -1036,6 +1109,8 @@
 	% data_set_difference( A, B, C ):- C = A - B. 
 :- pred data_set_difference( data_set::in, data_set::in, 
 				data_set::out) is det.
+:- pred data_set_apply_widening(module_info::in, proc_info::in, 
+				data_set::in, data_set::out) is det.
 
 data_set_empty( datastructs(0, set__init ) ). 
 data_set_empty = D :- data_set_empty(D).
@@ -1165,6 +1240,13 @@
 	DataSet2 = datastructs( _, Data2), 
 	Data = set__difference( Data1, Data2 ), 
 	DataSet = datastructs( set__count( Data ), Data ).
+
+data_set_apply_widening(ModuleInfo, ProcInfo, DataSet0, DataSet):- 
+	DataSet0 = datastructs(_, Data0), 
+	% XXX should also take subsumption into account ! 
+	Data = set__map(pa_datastruct__apply_widening(ModuleInfo, ProcInfo), 
+			Data0),
+	DataSet = datastructs(set__count(Data), Data). 
 	
 	
 :- pred set_cross_product( set(T1)::in, set(T2)::in, 
@@ -1194,3 +1276,4 @@
 		string__append_list([ Msg, ": map_det_insert-problem"], Msg2),
 		require__error( Msg2 )
 	). 
+
Index: pa_datastruct.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_datastruct.m,v
retrieving revision 1.1.2.4
diff -u -r1.1.2.4 pa_datastruct.m
--- pa_datastruct.m	2001/03/05 17:06:51	1.1.2.4
+++ pa_datastruct.m	2001/03/20 17:24:00
@@ -100,6 +100,7 @@
 
 :- pred apply_widening( module_info::in, proc_info::in, datastruct::in, 
 			datastruct::out) is det.
+:- func apply_widening(module_info, proc_info, datastruct) = datastruct.
 
 %-------------------------------------------------------------------%
 %-------------------------------------------------------------------%
@@ -231,6 +232,9 @@
 	map__lookup( VarTypes, ProgVar, ProgVarType), 
 	pa_selector__apply_widening( ModuleInfo, ProgVarType, Sel0, Sel), 
 	D = cel( ProgVar, Sel ). 
+
+apply_widening(ModuleInfo, ProcInfo, D0) = D :- 
+	apply_widening(ModuleInfo, ProcInfo, D0, D).
 
 	
 
Index: pa_run.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_run.m,v
retrieving revision 1.1.2.17
diff -u -r1.1.2.17 pa_run.m
--- pa_run.m	2001/03/16 17:15:47	1.1.2.17
+++ pa_run.m	2001/03/20 17:24:01
@@ -163,6 +163,7 @@
 
 analyse_pred_proc( HLDS, PRED_PROC_ID , FPtable0, FPtable) -->
 	globals__io_lookup_bool_option(very_verbose,Verbose),
+	globals__io_lookup_int_option(possible_alias_widening, WideningLimit),
 
 	{ module_info_pred_proc_info( HLDS, PRED_PROC_ID,_PredInfo,
 			ProcInfo_tmp) },
@@ -195,14 +196,26 @@
 	
 	analyse_goal( ProcInfo, HLDS, Goal, 
 			FPtable0, FPtable1, Alias0, Alias1 ),
-	% XXX
 	FullSize = pa_alias_as__size( Alias1 ), 
+
 	pa_alias_as__project( HeadVars, Alias1, Alias2),
-	% XXX
 	ProjectSize = pa_alias_as__size( Alias2 ),
-	pa_alias_as__normalize( ProcInfo, HLDS, InstMap, Alias2, Alias ),
-	% XXX
-	NormSize = pa_alias_as__size( Alias ),
+
+	pa_alias_as__normalize( ProcInfo, HLDS, InstMap, Alias2, Alias3 ),
+	NormSize = pa_alias_as__size( Alias3 ),
+
+	(
+		WideningLimit \= 0, NormSize > WideningLimit
+	->
+		pa_alias_as__apply_widening(HLDS, ProcInfo, Alias3, Alias),
+		Widening = bool__yes, 
+		WidenSize = pa_alias_as__size(Alias) 
+		
+	; 	
+		Alias = Alias3, 
+		Widening = bool__no, 
+		WidenSize = NormSize
+	),
 		
 	pa_fixpoint_table_new_as( HLDS, ProcInfo, 
 				PRED_PROC_ID, Alias, FPtable1, FPtable)
@@ -220,7 +233,16 @@
 			string__int_to_string( NormSize, NormS )
 		},
 		io__write_strings(["\t\t: ", FullS, "/", ProjectS, "/", 
-					NormS, "\n"])
+					NormS]), 
+		(
+			{ Widening = bool__yes }
+		-> 
+			{ string__int_to_string(WidenSize, WidenS) }, 
+			{ string__int_to_string(WideningLimit, WidLimitS) },
+			io__write_strings(["/-->widening(", WidLimitS,"): ", WidenS, "\n"])
+		;
+			io__write_string("\n")
+		)
 	
 %		pa_alias_as__print_aliases(Alias, ProcInfo, PredInfo),
 %		io__write_string("\n")

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