[m-dev.] [reuse] bugfix: verify whether nodes of conditional reuse are not aliased

[Nancy Mazur]

Hi,


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


Estimated hours taken: 7 (6 for peter tracking the bug, 1 for fixing it)

Bugfix. When a procedure has conditional reuse, even if each of the
conditions are satisfied within the callers context, still reuse
is not allowed if the nodes which are being reused in the procedure
are aliased to each other within the callers context. 

sr_data.m:
	The bug can be fixed by controlling whether none of reuse
	nodes is aliased to any of the other reuse-nodes (or itself)
	within the callers-context. 


Index: sr_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_data.m,v
retrieving revision 1.1.2.14
diff -u -r1.1.2.14 sr_data.m
--- sr_data.m	2001/03/07 17:20:33	1.1.2.14
+++ sr_data.m	2001/03/09 10:28:44
@@ -385,6 +385,18 @@
 		CONDITION = condition(NORM_NODES_set, NEW_LUiH, NEW_LAiH)
 	).
 
+	% Collect the nodes a reuse-condition is talking about. Fail 
+	% if the reuse condition is `always'. 
+:- pred reuse_condition_get_nodes(reuse_condition::in, 
+			set(pa_datastruct__datastruct)::out) is semidet.
+reuse_condition_get_nodes(Condition, Condition ^ nodes). 
+
+	% Collect the nodes a reuse-condition is talking about. Fail 
+	% if the reuse condition is `always'. 
+:- pred reuse_condition_get_nodes_list(reuse_condition::in, 
+			list(pa_datastruct__datastruct)::out) is semidet.
+reuse_condition_get_nodes_list(Condition, List):-
+	set__to_sorted_list(Condition ^ nodes, List). 
 
 reuse_conditions_simplify(ReuseCondition0, ReuseCondition):- 
 	list__foldl( 
@@ -679,8 +691,86 @@
 	Memo = yes(Conditions), 
 	list__takewhile(reuse_condition_verify(ProcInfo, HLDS, 
 						Live0, Alias0, Static), 
-				Conditions, _, []).
+				Conditions, _, []), 
+	% Next to verifying each condition separately, one has to
+	% verify whether the nodes which are reused in each of the
+	% conditions are not aliased within the current context. If
+	% this would be the case, then reuse is not allowed. If
+	% this would be allowed, then the callee want to reuse
+	% the different parts of the input while these may point
+	% to exactly the same structure, resulting in undefined
+	% behaviour. 
+	no_aliases_between_reuse_nodes(HLDS, ProcInfo, Conditions, 
+				Alias0 ). 
+
+:- pred no_aliases_between_reuse_nodes(
+		module_info::in, 
+		proc_info::in, 
+		list(reuse_condition)::in, 
+		alias_as::in) is semidet.
+no_aliases_between_reuse_nodes(ModuleInfo, ProcInfo, 
+		Conditions, Alias):- 
+	list__filter_map(
+		reuse_condition_get_nodes_list,
+		Conditions, 
+		ListNodes), 
+	list__condense(ListNodes, AllNodes), 
+	(
+		AllNodes = [Node | Rest] 
+	-> 
+		no_aliases_between_reuse_nodes_2(ModuleInfo, ProcInfo, 
+					Node, Rest, Alias)
+	;
+		require__error("(sr_data): no_aliases_between_reuse_nodes has no nodes.")
+	).
 
+:- pred no_aliases_between_reuse_nodes_2(module_info::in, proc_info::in,
+		pa_datastruct__datastruct::in, 
+		list(pa_datastruct__datastruct)::in, 
+		alias_as::in) is semidet. 
+no_aliases_between_reuse_nodes_2(ModuleInfo, ProcInfo, Node, OtherNodes, 
+		Alias):- 
+	pa_alias_as__collect_aliases_of_datastruct(ModuleInfo, ProcInfo, 
+		Node, Alias, AliasedNodes), 
+	% Check whether none of the structures to which the current
+	% Node is aliased is subsumed by or subsumes one of 
+	% the other nodes, including the current node itself. 
+	list__filter(
+		there_is_a_subsumption_relation(ModuleInfo, ProcInfo, 
+			[Node | OtherNodes]), 
+		AliasedNodes, 
+		[]), 
+	(
+		OtherNodes = [NextNode | NextOtherNodes],
+		no_aliases_between_reuse_nodes_2(ModuleInfo, ProcInfo, 
+			NextNode, NextOtherNodes, Alias)
+	; 
+		OtherNodes = [], 
+		true
+	).
+
+	% there_is_a_subsumption_relation(ModuleInfo, ProcInfo, Datastructs, 
+	% Data): This procedure succeeds if Data is subsumed or subsumes
+	% some of the datastructures in Datastructs. 
+:- pred there_is_a_subsumption_relation(module_info::in, proc_info::in, 
+		list(pa_datastruct__datastruct)::in, 
+		pa_datastruct__datastruct::in) is semidet.
+there_is_a_subsumption_relation(ModuleInfo, ProcInfo, 
+		Datastructs0, Data0):-
+	list__filter(
+		pred(Data1::in) is semidet:-
+		    (
+			( pa_datastruct__less_or_equal(ModuleInfo, ProcInfo, 
+				Data0, Data1, _) ; 
+			  pa_datastruct__less_or_equal(ModuleInfo, ProcInfo, 
+				Data1, Data0, _)
+			)
+		     ), 
+		Datastructs0, 
+		SubsumedStructs), 
+	SubsumedStructs \= []. 
+
+		
 memo_reuse_is_conditional(yes([_|_])).
 memo_reuse_is_unconditional(yes([])).
 

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