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

[David Overton]

On Sun, Jan 24, 1999 at 03:02:07AM EST, Simon Taylor wrote:
> 
> What happens if a variable whose inst contains the only live reference to
> an inst_key is passed into a branched goal, is assigned to another variable
> within the branched goal and is dead after the branched goal?
> The instmap after the branched goal should include the information that the
> new and old variables are aliases.

The instmap can only contain this aliasing information if the
assignment occurs in every branch.  E.g.,

:- mode q(in, di, uo).

q(X, Y, Z) :-
	(
		X = yes,
		Y = Z
	;
		X = no,
		Y = Z
	).

I had not allowed for this case.  I've included a relative diff for
inst_util.m that will retain the Y - Z alias after the branched goal
even if Y is dead.

The other possibility is when an alias occurs only in one branch:

:- mode p(in, di, di, uo).
	
p(X, A, B, C) :-
	(
		X = yes,
		C = A
	;
		X = no,
		C = B
	).

At the end of the first branch, C is aliased to A and at the end of
the second branch C is aliased to B.  Inst_merge removes these aliases
because they only occur in one branch.  However, because each inst_key
is only referenced by only one live variable at the end of the branch,
uniqueness is maintained.  (If A or B were still live after the
branched goal then all 3 vars would become shared.)

My question is, after the disjunction do you need to know that A/B may
_possibly_ be aliased to a live variable to ensure that the memory
associated with them is not re-used?

> 
> If an inst_key is only referenced (directly or indirectly) by one variable
> non-local to the branched goal, it's probably ok to remove it during the merge.

Yep, that's what I thought.  Thanks Simon.


David

--- inst_util.bak.m	Mon Jan 25 10:56:48 1999
+++ inst_util.m	Mon Jan 25 11:56:44 1999
@@ -1729,101 +1729,104 @@
 		ModuleInfo = ModuleInfo0
 	;
 	************/
-	LiveCounts = LiveCountsA - LiveCountsB,
-	expand_inst(LiveCountsA, InstMap0, InstTable0, ModuleInfo0, InstA,
-		InstA2),
-	expand_inst(LiveCountsB, InstMap0, InstTable0, ModuleInfo0, InstB,
-		InstB2),
 	(
-		InstB2 = not_reached
+		InstA = alias(IKA),
+		InstB = alias(IKB),
+		instmap__inst_keys_are_equivalent(IKA, InstMap0, IKB, InstMap0)
 	->
-		Inst = InstA2,
-		ModuleInfo = ModuleInfo0,
+		Inst = alias(IKA),
 		InstTable = InstTable0,
-		InstMap = InstMap0,
-		MergeSubs = MergeSubs0
-	;
-		InstA2 = not_reached
-	->
-		Inst = InstB2,
 		ModuleInfo = ModuleInfo0,
-		InstTable = InstTable0,
 		InstMap = InstMap0,
-		MergeSubs = MergeSubs0
-	;
-		InstA2 = alias(IKA0),
-		InstB2 \= alias(_)
-	->
-		Lambda = lambda([I::out] is nondet, (
-			map__member(MergeSubs0, IKA0 - _, MergeIK),
-			I = alias(MergeIK))),
-		make_shared_merge_insts(IKA0, Lambda, InstMap0, InstTable0,
-			ModuleInfo0, InstA3, InstMap1, InstTable1, ModuleInfo1),
-		inst_merge_3(InstA3, InstB2, LiveCounts, InstMap1, InstTable1,
-			ModuleInfo1, MergeSubs0, Inst, InstMap, InstTable,
-			ModuleInfo, MergeSubs)
+		map__set(MergeSubs0, IKA - IKB, IKA, MergeSubs)
 	;
-		InstB2 = alias(IKB0),
-		InstA2 \= alias(_)
-	->
-		Lambda = lambda([I::out] is nondet, (
-			map__member(MergeSubs0, _ - IKB0, MergeIK),
-			I = alias(MergeIK))),
-		make_shared_merge_insts(IKB0, Lambda, InstMap0, InstTable0,
-			ModuleInfo0, InstB3, InstMap1, InstTable1, ModuleInfo1),
-		inst_merge_3(InstA2, InstB3, LiveCounts, InstMap1, InstTable1,
-			ModuleInfo1, MergeSubs0, Inst, InstMap, InstTable,
-			ModuleInfo, MergeSubs)
-	;
-		InstA2 = alias(IKA),
-		InstB2 = alias(IKB)
-	->
 		LiveCounts = LiveCountsA - LiveCountsB,
+		expand_inst(LiveCountsA, InstMap0, InstTable0, ModuleInfo0,
+			InstA, InstA2),
+		expand_inst(LiveCountsB, InstMap0, InstTable0, ModuleInfo0,
+			InstB, InstB2),
 		(
-		    instmap__inst_keys_are_equivalent(IKA, InstMap0,
-			IKB, InstMap0)
+			InstB2 = not_reached
 		->
-		    Inst = alias(IKA),
-		    InstTable = InstTable0,
-		    ModuleInfo = ModuleInfo0,
-		    InstMap = InstMap0,
-		    map__set(MergeSubs0, IKA - IKB, IKA, MergeSubs)
-		;
-		    ( map__search(MergeSubs0, IKA - IKB, IK0) ->
-			IK = IK0,
+			Inst = InstA2,
+			ModuleInfo = ModuleInfo0,
 			InstTable = InstTable0,
+			InstMap = InstMap0,
+			MergeSubs = MergeSubs0
+		;
+			InstA2 = not_reached
+		->
+			Inst = InstB2,
 			ModuleInfo = ModuleInfo0,
+			InstTable = InstTable0,
 			InstMap = InstMap0,
 			MergeSubs = MergeSubs0
-		    ;
-			inst_table_get_inst_key_table(InstTable0, IKT0),
-			instmap__inst_key_table_lookup(InstMap0, IKT0, IKA,
-			    InstA3),
-			instmap__inst_key_table_lookup(InstMap0, IKT0, IKB,
-			    InstB3),
-			inst_merge_3(InstA3, InstB3, LiveCounts, InstMap0,
-			    InstTable0, ModuleInfo0, MergeSubs0, Inst0, InstMap,
-			    InstTable1, ModuleInfo, MergeSubs1),
-			( map__search(MergeSubs1, IKA - IKB, IK1) ->
-			    IK = IK1,
-			    MergeSubs = MergeSubs1,
-			    InstTable = InstTable1
+		;
+			InstA2 = alias(IKA0),
+			InstB2 \= alias(_)
+		->
+			Lambda = lambda([I::out] is nondet, (
+				map__member(MergeSubs0, IKA0 - _, MergeIK),
+				I = alias(MergeIK))),
+			make_shared_merge_insts(IKA0, Lambda, InstMap0,
+				InstTable0, ModuleInfo0, InstA3, InstMap1,
+				InstTable1, ModuleInfo1),
+			inst_merge_3(InstA3, InstB2, LiveCounts, InstMap1,
+				InstTable1, ModuleInfo1, MergeSubs0, Inst,
+				InstMap, InstTable, ModuleInfo, MergeSubs)
+		;
+			InstB2 = alias(IKB0),
+			InstA2 \= alias(_)
+		->
+			Lambda = lambda([I::out] is nondet, (
+				map__member(MergeSubs0, _ - IKB0, MergeIK),
+				I = alias(MergeIK))),
+			make_shared_merge_insts(IKB0, Lambda, InstMap0,
+				InstTable0, ModuleInfo0, InstB3, InstMap1,
+				InstTable1, ModuleInfo1),
+			inst_merge_3(InstA2, InstB3, LiveCounts, InstMap1,
+				InstTable1, ModuleInfo1, MergeSubs0, Inst,
+				InstMap, InstTable, ModuleInfo, MergeSubs)
+		;
+			InstA2 = alias(IKA),
+			InstB2 = alias(IKB)
+		->
+			LiveCounts = LiveCountsA - LiveCountsB,
+			( map__search(MergeSubs0, IKA - IKB, IK0) ->
+			    IK = IK0,
+			    InstTable = InstTable0,
+			    ModuleInfo = ModuleInfo0,
+			    InstMap = InstMap0,
+			    MergeSubs = MergeSubs0
 			;
-			    % 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)
+			    inst_table_get_inst_key_table(InstTable0, IKT0),
+			    instmap__inst_key_table_lookup(InstMap0, IKT0, IKA,
+			    	InstA3),
+			    instmap__inst_key_table_lookup(InstMap0, IKT0, IKB,
+			    	InstB3),
+			    inst_merge_3(InstA3, InstB3, LiveCounts, 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)
+		;
+			inst_merge_3(InstA2, InstB2, LiveCounts, InstMap0,
+				InstTable0, ModuleInfo0, MergeSubs0, Inst,
+				InstMap, InstTable, ModuleInfo, MergeSubs)
 		)
-	;
-		inst_merge_3(InstA2, InstB2, LiveCounts, InstMap0, InstTable0,
-			ModuleInfo0, MergeSubs0, Inst, InstMap, InstTable,
-			ModuleInfo, MergeSubs)
 	).
 
 :- pred inst_merge_3(inst, inst, live_counts, instmap, inst_table, module_info,

-- 
David Overton           Department of Computer Science & Software Engineering
MEngSc Student          The University of Melbourne, Australia
+61 3 9344 9159         http://www.cs.mu.oz.au/~dmo