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

David Overton dmo at cs.mu.OZ.AU
Tue Jan 19 16:42:41 AEDT 1999


On Sat, Dec 19, 1998 at 08:50:22PM EST, Andrew Bromage wrote:
> 
> Owing to time constraints, I've only looked for for structural
> weaknesses rather than typos and style issues.  (Which is probably
> what you wanted out of me.)
> 

Hi,

I've addressed Andrew and Fergus's comments.  Would one of you please
review the following revised diff?  I can post a relative diff if
required.

I would also appreciate Simon's comments on how this change interacts
with structure re-use (see below).

> > compiler/modecheck_unify.m:
> > 	Modify `mode_info_make_aliased_insts' to only make aliases for
> > 	insts of live variables.  This should significantly reduce the
> > 	number of aliases that we need to keep track of.
> 
> Will this have bad implications for structure reuse?  You have to look
> at the modes of dead variables there.
> 

I've undone that change and instead check the liveness in
`inst_merge'.  Inst_keys which have only one live reference at the
merge point are removed at this stage.  I'm not sure exactly how
structure re-use works.  Will this be ok, Simon?

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

Estimated hours taken: 40 (+ unknown time by bromage)

Modify `instmap__merge' and `inst_merge' to preserve as much definite 
aliasing information as possible rather than just throwing it all away 
at the end of branched goals.

compiler/instmap.m:
	Modify `instmap__merge' to retain aliasing information.
	Algorithm:
	For each pair of final instmaps in a branched goal, 
		- Remove singleton inst_keys from each instmap.
		- Expand any inst_key substitutions that appear in one
		  instmap but not the other (done by `instmap__merge_subs').
		- Call inst_merge for each non-local variable. 
		- Work out which inst_keys need to become shared
		  and make them shared (uses information collected 
		  by calls to `inst_merge').
		- Recursively merge the resultant instmap with the
		  final instmap of the next branch.

compiler/inst_util.m:
	Modify `inst_merge' to retain aliasing information and to return 
	information about inst_keys which may need to be made shared. 
	Modify `make_shared_inst' to fail rather than abort when called
	with a free or partially-instantiated inst.
	Ensure that `make_shared_inst' does not remove `alias' insts.
	Add a higher order predicate `inst_fold' which traverses an inst
	data structure with an accumulator.

compiler/hlds_data.m: compiler/prog_data.m:
	Create a new table, the substitution_inst_table, within the
	inst_table, for insts created when expanding inst_key
	substitutions.

compiler/mercury_to_mercury.m:
compiler/mode_util.m: 
compiler/module_qual.m:
	Changes related to addition of the substitution_inst_table.

compiler/mode_info.m:
	Change a couple of mode declarations to allow them to compile
	with both the old and new mode-checkers.  Once the new
	mode-checker is installed, the modes for mode_info should be
	made more accurate so we can ensure the uniqueness of the
	io__state within the mode_info.

compiler/simplify.m:
	Instead of calling `instmap__merge' in the middle of simplifying
	a goal, record in the simplify_info that the instmap_delta needs
	to be recomputed and then call `recompute_instmap_deltas' after
	processing the entire procedure.  This is necessary because
	`instmap__merge' requires liveness information that can only be
	computed by processing the whole procedure.
	Remove unused predicates `simplify_info_set_rerun_simplify' and
	`simplify_info_recompute_atomic'.

Index: hlds_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_data.m,v
retrieving revision 1.17.2.12
diff -u -w -r1.17.2.12 hlds_data.m
--- 1.17.2.12	1998/11/24 06:28:35
+++ hlds_data.m	1998/12/21 23:57:47
@@ -14,7 +14,7 @@
 :- interface.
 
 :- import_module hlds_pred, llds, prog_data, (inst), term.
-:- import_module bool, list, map, std_util.
+:- import_module bool, list, map, std_util, set_bbbtree.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -367,6 +367,13 @@
 
 :- type mostly_uniq_inst_table == map(inst_name, maybe_inst).
 
+:- type substitution_inst_table == map(substitution_inst, maybe_inst).
+
+:- type substitution_inst
+	--->	substitution_inst(inst_name, inst_key_set, inst_key_sub).
+
+:- type inst_key_set == set_bbbtree(inst_key).
+
 :- type maybe_inst	--->	unknown
 			;	known(inst).
 
@@ -408,16 +415,21 @@
 :- pred inst_table_init(inst_table).
 :- mode inst_table_init(out) is det.
 
-:- pred inst_table_get_all_tables(inst_table, unify_inst_table,
-	merge_inst_table, ground_inst_table, any_inst_table,
+:- pred inst_table_get_all_tables(inst_table, substitution_inst_table,
+	unify_inst_table, merge_inst_table, ground_inst_table, any_inst_table,
 	shared_inst_table, mostly_uniq_inst_table, inst_key_table).
-:- mode inst_table_get_all_tables(in, out, out, out, out, out, out, out) is det.
+:- mode inst_table_get_all_tables(in, out, out, out, out, out, out, out, out)
+	is det.
 
-:- pred inst_table_set_all_tables(inst_table, unify_inst_table,
-	merge_inst_table, ground_inst_table, any_inst_table,
+:- pred inst_table_set_all_tables(inst_table, substitution_inst_table,
+	unify_inst_table, merge_inst_table, ground_inst_table, any_inst_table,
 	shared_inst_table, mostly_uniq_inst_table, inst_key_table,
 	inst_table).
-:- mode inst_table_set_all_tables(in, in, in, in, in, in, in, in, out) is det.
+:- mode inst_table_set_all_tables(in, in, in, in, in, in, in, in, in, out)
+	is det.
+
+:- pred inst_table_get_substitution_insts(inst_table, substitution_inst_table).
+:- mode inst_table_get_substitution_insts(in, out) is det.
 
 :- pred inst_table_get_unify_insts(inst_table, unify_inst_table).
 :- mode inst_table_get_unify_insts(in, out) is det.
@@ -440,6 +452,10 @@
 :- pred inst_table_get_inst_key_table(inst_table, inst_key_table).
 :- mode inst_table_get_inst_key_table(in, out) is det.
 
+:- pred inst_table_set_substitution_insts(inst_table, substitution_inst_table,
+	inst_table).
+:- mode inst_table_set_substitution_insts(in, in, out) is det.
+
 :- pred inst_table_set_unify_insts(inst_table, unify_inst_table, inst_table).
 :- mode inst_table_set_unify_insts(in, in, out) is det.
 
@@ -484,7 +500,7 @@
 
 :- type inst_table
 	--->	inst_table(
-			unit,
+			substitution_inst_table,
 			unify_inst_table,
 			merge_inst_table,
 			ground_inst_table,
@@ -503,8 +519,9 @@
 				% qualifying the modes of lambda expressions.
 		).
 
-inst_table_init(inst_table(unit, UnifyInsts, MergeInsts, GroundInsts,
+inst_table_init(inst_table(SubInsts, UnifyInsts, MergeInsts, GroundInsts,
 			AnyInsts, SharedInsts, NondetLiveInsts, InstKeys)) :-
+	map__init(SubInsts),
 	map__init(UnifyInsts),
 	map__init(MergeInsts),
 	map__init(GroundInsts),
@@ -513,17 +530,21 @@
 	map__init(NondetLiveInsts),
 	inst_key_table_init(InstKeys).
 
-inst_table_get_all_tables(InstTable, UnifyInsts, MergeInsts, GroundInsts,
-		AnyInsts, SharedInsts, NondetLiveInsts, InstKeys) :-
-	InstTable = inst_table(unit, UnifyInsts, MergeInsts, GroundInsts,
+inst_table_get_all_tables(InstTable, SubInsts, UnifyInsts, MergeInsts,
+		GroundInsts, AnyInsts, SharedInsts, NondetLiveInsts,
+		InstKeys) :-
+	InstTable = inst_table(SubInsts, UnifyInsts, MergeInsts, GroundInsts,
 		AnyInsts, SharedInsts, NondetLiveInsts, InstKeys).
 
-inst_table_set_all_tables(InstTable0, UnifyInsts, MergeInsts, GroundInsts,
-		AnyInsts, SharedInsts, NondetLiveInsts, InstKeys, InstTable) :-
-	InstTable0 = inst_table(A, _, _, _, _, _, _, _),
-	InstTable  = inst_table(A, UnifyInsts, MergeInsts, GroundInsts,
+inst_table_set_all_tables(_InstTable0, SubInsts, UnifyInsts, MergeInsts,
+		GroundInsts, AnyInsts, SharedInsts, NondetLiveInsts, InstKeys,
+		InstTable) :-
+	InstTable  = inst_table(SubInsts, UnifyInsts, MergeInsts, GroundInsts,
 		AnyInsts, SharedInsts, NondetLiveInsts, InstKeys).
 
+inst_table_get_substitution_insts(inst_table(SubInsts, _, _, _, _, _, _, _),
+			SubInsts).
+
 inst_table_get_unify_insts(inst_table(_, UnifyInsts, _, _, _, _, _, _),
 			UnifyInsts).
 
@@ -545,6 +566,9 @@
 inst_table_get_inst_key_table(inst_table(_, _, _, _, _, _, _, InstKeyTable),
 			InstKeyTable).
 
+inst_table_set_substitution_insts(inst_table(_, B, C, D, E, F, G, H), SubInsts,
+			inst_table(SubInsts, B, C, D, E, F, G, H)).
+
 inst_table_set_unify_insts(inst_table(A, _, C, D, E, F, G, H), UnifyInsts,
 			inst_table(A, UnifyInsts, C, D, E, F, G, H)).
 
Index: inst_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/inst_util.m,v
retrieving revision 1.3.2.16
diff -u -w -r1.3.2.16 inst_util.m
--- 1.3.2.16	1998/09/25 01:07:45
+++ inst_util.m	1999/01/19 05:11:11
@@ -42,7 +42,7 @@
 :- interface.
 
 :- import_module hlds_module, hlds_data, prog_data, (inst), instmap.
-:- import_module list.
+:- import_module list, map, std_util, set.
 
 :- pred abstractly_unify_inst(is_live, inst, inst, unify_is_real,
 		inst_table, module_info, instmap, inst, determinism,
@@ -91,10 +91,14 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred inst_merge(inst, inst, instmap, inst_table, module_info, inst,
-		instmap, inst_table, module_info).
-:- mode inst_merge(in, in, in, in, in, out, out, out, out) is semidet.
+:- type merge_subs == map(pair(inst_key), inst_key).
+:- type live_counts == pair(inst_key_counts).
 
+:- pred inst_merge(inst, inst, live_counts, instmap, inst_table, module_info,
+		merge_subs, inst, instmap, inst_table, module_info, merge_subs).
+:- mode inst_merge(in, in, in, in, in, in, in, out, out, out, out, out)
+		is semidet.
+
 	% inst_merge(InstA, InstB, InstC):
 	%       Combine the insts found in different arms of a
 	%       disjunction (or if-then-else).
@@ -102,6 +106,11 @@
 	%       information in InstA and InstB.  Where InstA and
 	%       InstB specify a binding (free or bound), it must be
 	%       the same in both.
+	%	Note: inst_merge is designed to be called only from
+	%	instmap__merge.  It does not make sense to merge a single pair
+	%	of insts in isolation.  In particular, the returned instmap is
+	%	not completely correct and needs to be fixed up by
+	%	instmap__merge after all insts in the instmap have been merged.
 
 %-----------------------------------------------------------------------------%
 
@@ -120,6 +129,33 @@
 :- mode inst_table_create_sub(in, in, out, out) is det.
 
 %-----------------------------------------------------------------------------%
+
+:- type inst_fold_pred(T) == pred(inst, set(inst_name), T, T).
+:- mode inst_fold_pred :: (pred(in, in, in, out) is semidet).
+
+:- type inst_fold_merge_pred(T) == pred(T, T, T).
+:- mode inst_fold_merge_pred :: (pred(in, in, out) is det).
+
+%	inst_fold(InstMap, InstTable, ModuleInfo, Before, After, Merge,
+%			Inst, T0, T)
+% 		Recursively traverse Inst calling Before before recursive
+%		calls and After after recursive calls.  Traverses sub-insts
+%		of `bound' and argument insts of `abstract_inst' and expands
+%		and traverses `alias' and `defined_inst'.
+%		Before and After are passed the current sub-inst, the set of
+%		previously seen inst_names and the current state of the
+%		accumulator; they return the new state of the accumulator.
+%		If a call to Before or After fails, the state of the accumulator
+%		is passed on unchanged.
+%		Merge is called to combine the results of the or-nodes of
+%		a `bound' inst.
+
+:- pred inst_fold(instmap, inst_table, module_info, inst_fold_pred(T),
+		inst_fold_pred(T), inst_fold_merge_pred(T), inst, T, T).
+:- mode inst_fold(in, in, in, inst_fold_pred, inst_fold_pred,
+		inst_fold_merge_pred, in, in, out) is det.
+
+%-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
 :- implementation.
@@ -1321,7 +1357,7 @@
 
 :- pred maybe_make_shared_inst_list(list(inst), list(is_live), unify_inst_info,
 				list(inst), unify_inst_info).
-:- mode maybe_make_shared_inst_list(in, in, in, out, out) is det.
+:- mode maybe_make_shared_inst_list(in, in, in, out, out) is semidet.
 
 maybe_make_shared_inst_list([], [], UI, [], UI).
 maybe_make_shared_inst_list([Inst0 | Insts0], [IsLive | IsLives], UI0,
@@ -1340,7 +1376,7 @@
 
 :- pred make_shared_inst_list(list(inst), unify_inst_info,
 				list(inst), unify_inst_info).
-:- mode make_shared_inst_list(in, in, out, out) is det.
+:- mode make_shared_inst_list(in, in, out, out) is semidet.
 
 make_shared_inst_list([], UI, [], UI).
 make_shared_inst_list([Inst0 | Insts0], UI0, [Inst | Insts], UI) :-
@@ -1352,14 +1388,20 @@
 make_shared_inst_list(Insts0, InstTable0, ModuleInfo0, Sub0,
 		Insts, InstTable, ModuleInfo, Sub) :-
 	UI0 = unify_inst_info(ModuleInfo0, InstTable0, Sub0),
-	make_shared_inst_list(Insts0, UI0, Insts, UI),
+	( make_shared_inst_list(Insts0, UI0, Insts1, UI1) ->
+		Insts = Insts1,
+		UI = UI1
+	;
+		% The caller should ensure that this case never happens.
+		error("make_shared_inst_list: inst is partially instantiated")
+	),
 	UI  = unify_inst_info(ModuleInfo, InstTable, Sub).
 
 % make an inst shared; replace all occurrences of `unique' or `mostly_unique'
-% in the inst with `shared'.
+% in the inst with `shared'.  Fails if the inst is only partially instantiated.
 
 :- pred make_shared_inst(inst, unify_inst_info, inst, unify_inst_info).
-:- mode make_shared_inst(in, in, out, out) is det.
+:- mode make_shared_inst(in, in, out, out) is semidet.
 
 make_shared_inst(not_reached, UI, not_reached, UI).
 make_shared_inst(alias(Key), UI0, Inst, UI) :-
@@ -1384,12 +1426,8 @@
 	).
 make_shared_inst(any(Uniq0), UI, any(Uniq), UI) :-
 	make_shared(Uniq0, Uniq).
-make_shared_inst(free(_), UI, free(_), UI) :-
-	% the caller should ensure that this never happens
-	error("make_shared_inst: cannot make shared version of `free'").
-make_shared_inst(free(_, T), UI, free(_, T), UI) :-
-	% the caller should ensure that this never happens
-	error("make_shared_inst: cannot make shared version of `free(T)'").
+make_shared_inst(free(_), UI, free(_), UI) :- fail.
+make_shared_inst(free(_, T), UI, free(_, T), UI) :- fail.
 make_shared_inst(bound(Uniq0, BoundInsts0), UI0, bound(Uniq, BoundInsts), UI) :-
 	make_shared(Uniq0, Uniq),
 	make_shared_bound_inst_list(BoundInsts0, UI0, BoundInsts, UI).
@@ -1396,7 +1434,7 @@
 make_shared_inst(ground(Uniq0, PredInst), UI, ground(Uniq, PredInst), UI) :-
 	make_shared(Uniq0, Uniq).
 make_shared_inst(inst_var(_), _, _, _) :-
-	error("free inst var").
+	error("make_shared_inst: free inst var").
 make_shared_inst(abstract_inst(_,_), UI, _, UI) :-
 	error("make_shared_inst(abstract_inst)").
 make_shared_inst(defined_inst(InstName), UI0, Inst, UI) :-
@@ -1424,9 +1462,8 @@
 		% expand the inst name, and invoke ourself recursively on
 		% it's expansion
 		unify_inst_info_get_module_info(UI1, ModuleInfo1),
-		unify_inst_info_get_instmap(UI1, InstMap1),
 		inst_lookup(InstTable1, ModuleInfo1, InstName, Inst0),
-		inst_expand(InstMap1, InstTable1, ModuleInfo1, Inst0, Inst1),
+		inst_expand_defined_inst(InstTable1, ModuleInfo1, Inst0, Inst1),
 		make_shared_inst(Inst1, UI1, SharedInst, UI2),
 
 		% now that we have determined the resulting Inst, store
@@ -1463,7 +1500,7 @@
 
 :- pred make_shared_bound_inst_list(list(bound_inst), unify_inst_info,
 					list(bound_inst), unify_inst_info).
-:- mode make_shared_bound_inst_list(in, in, out, out) is det.
+:- mode make_shared_bound_inst_list(in, in, out, out) is semidet.
 
 make_shared_bound_inst_list([], UI, [], UI).
 make_shared_bound_inst_list([Bound0 | Bounds0], UI0, [Bound | Bounds], UI) :-
@@ -1529,9 +1566,8 @@
 		% expand the inst name, and invoke ourself recursively on
 		% it's expansion
 		unify_inst_info_get_module_info(UI1, ModuleInfo1),
-		unify_inst_info_get_instmap(UI1, InstMap1),
 		inst_lookup(InstTable1, ModuleInfo1, InstName, Inst0),
-		inst_expand(InstMap1, InstTable1, ModuleInfo1, Inst0, Inst1),
+		inst_expand_defined_inst(InstTable1, ModuleInfo1, Inst0, Inst1),
 		make_mostly_uniq_inst_2(Inst1, UI1, NondetLiveInst, UI2),
 
 		% now that we have determined the resulting Inst, store
@@ -1619,6 +1655,7 @@
 allow_unify_bound_any(_) :- true.
 
 %-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
 
 	% inst_merge(InstA, InstB, InstC):
 	%       Combine the insts found in different arms of a
@@ -1627,9 +1664,15 @@
 	%       information in InstA and InstB.  Where InstA and
 	%       InstB specify a binding (free or bound), it must be
 	%       the same in both.
-
-inst_merge(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, Inst, InstMap,
-			InstTable, ModuleInfo) :-
+	%	Note: inst_merge is designed to be called only from
+	%	instmap__merge.  It does not make sense to merge a single pair
+	%	of insts in isolation.  In particular, the returned instmap is
+	%	not completely correct and needs to be fixed up by
+	%	instmap__merge after all insts in the instmap have been merged.
+
+inst_merge(InstA, InstB, LiveCounts, InstMap0, InstTable0,
+		ModuleInfo0, MergeSubs0, Inst, InstMap, InstTable, ModuleInfo,
+		MergeSubs) :-
 		% check whether this pair of insts is already in
 		% the merge_insts table
 	inst_table_get_merge_insts(InstTable0, MergeInstTable0),
@@ -1642,7 +1685,8 @@
 			Inst0 = defined_inst(merge_inst(InstA, InstB))
 		),
 		InstTable = InstTable0,
-		InstMap = InstMap0
+		InstMap = InstMap0,
+		MergeSubs = MergeSubs0
 	;
 			% insert ThisInstPair into the table with value
 			%`unknown'
@@ -1652,8 +1696,9 @@
 			InstTable1),
 
 			% merge the insts
-		inst_merge_2(InstA, InstB, InstMap0, InstTable1, ModuleInfo0,
-				Inst0, InstMap, InstTable2, ModuleInfo),
+		inst_merge_2(InstA, InstB, LiveCounts, InstMap0,
+			InstTable1, ModuleInfo0, MergeSubs0, Inst0, InstMap,
+			InstTable2, ModuleInfo, MergeSubs),
 
 			% now update the value associated with ThisInstPair
 		inst_table_get_merge_insts(InstTable2, MergeInstTable2),
@@ -1663,7 +1708,7 @@
 			InstTable)
 	),
 		% avoid expanding recursive insts
-	( inst_contains_instname(Inst0, InstMap0, InstTable, ModuleInfo,
+	( inst_contains_instname(Inst0, InstMap, InstTable, ModuleInfo,
 			merge_inst(InstA, InstB)) ->
 		Inst = defined_inst(merge_inst(InstA, InstB))
 	;
@@ -1670,12 +1715,13 @@
 		Inst = Inst0
 	).
 
-:- pred inst_merge_2(inst, inst, instmap, inst_table, module_info,
-		inst, instmap, inst_table, module_info).
-:- mode inst_merge_2(in, in, in, in, in, out, out, out, out) is semidet.
+:- pred inst_merge_2(inst, inst, live_counts, instmap, inst_table, module_info,
+		merge_subs, inst, instmap, inst_table, module_info, merge_subs).
+:- mode inst_merge_2(in, in, in, in, in, in, in, out, out, out, out, out)
+		is semidet.
 
-inst_merge_2(InstA, InstB, InstMap0, InstTable0, ModuleInfo0, Inst,
-		InstMap, InstTable, ModuleInfo) :-
+inst_merge_2(InstA, InstB, LiveCounts, InstMap0, InstTable0, ModuleInfo0,
+		MergeSubs0, Inst, InstMap, InstTable, ModuleInfo, MergeSubs) :-
 /*********
 		% would this test improve efficiency??
 	( InstA = InstB ->
@@ -1682,10 +1728,12 @@
 		Inst = InstA,
 		ModuleInfo = ModuleInfo0
 	;
-*********/
-	%     fixed!
-	inst_expand_defined_inst(InstTable0, ModuleInfo0, InstA, InstA2),
-	inst_expand_defined_inst(InstTable0, ModuleInfo0, InstB, InstB2),
+	************/
+	LiveCounts = LiveCountsA - LiveCountsB,
+	expand_inst(LiveCountsA, InstMap0, InstTable0, ModuleInfo0, InstA,
+		InstA2),
+	expand_inst(LiveCountsB, InstMap0, InstTable0, ModuleInfo0, InstB,
+		InstB2),
 	(
 		InstB2 = not_reached
 	->
@@ -1692,29 +1740,96 @@
 		Inst = InstA2,
 		ModuleInfo = ModuleInfo0,
 		InstTable = InstTable0,
-		InstMap = InstMap0
+		InstMap = InstMap0,
+		MergeSubs = MergeSubs0
 	;
-		InstA2 = alias(IKA)
+		InstA2 = not_reached
 	->
-		inst_table_get_inst_key_table(InstTable0, IKT0),
-		instmap__inst_key_table_lookup(InstMap0, IKT0, IKA, InstA3),
-		inst_merge_3(InstA3, InstB2, InstMap0, InstTable0, ModuleInfo0,
-			Inst, InstMap, InstTable, ModuleInfo)
+		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)
+	;
+		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,
+		(
+		    instmap__inst_keys_are_equivalent(IKA, InstMap0,
+			IKB, InstMap0)
+		->
+		    Inst = alias(IKA),
+		    InstTable = InstTable0,
+		    ModuleInfo = ModuleInfo0,
+		    InstMap = InstMap0,
+		    map__set(MergeSubs0, IKA - IKB, IKA, MergeSubs)
+		;
+		    ( map__search(MergeSubs0, IKA - IKB, IK0) ->
+			IK = IK0,
+			InstTable = InstTable0,
+			ModuleInfo = ModuleInfo0,
+			InstMap = InstMap0,
+			MergeSubs = MergeSubs0
+		    ;
 		inst_table_get_inst_key_table(InstTable0, IKT0),
-		instmap__inst_key_table_lookup(InstMap0, IKT0, IKB, InstB3),
-		inst_merge_3(InstA2, InstB3, InstMap0, InstTable0, ModuleInfo0,
-			Inst, InstMap, InstTable, ModuleInfo)
+			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, InstMap0, InstTable0, ModuleInfo0,
-			Inst, InstMap, InstTable, ModuleInfo)
+		inst_merge_3(InstA2, InstB2, LiveCounts, InstMap0, InstTable0,
+			ModuleInfo0, MergeSubs0, Inst, InstMap, InstTable,
+			ModuleInfo, MergeSubs)
 	).
 
-:- pred inst_merge_3(inst, inst, instmap, inst_table, module_info, inst,
-		instmap, inst_table, module_info).
-:- mode inst_merge_3(in, in, in, in, in, out, out, out, out) is semidet.
+:- pred inst_merge_3(inst, inst, live_counts, instmap, inst_table, module_info,
+		merge_subs, inst, instmap, inst_table, module_info, merge_subs).
+:- mode inst_merge_3(in, in, in, in, in, in, in, out, out, out, out, out)
+		is semidet.
 
 % We do not yet allow merging of `free' and `any',
 % except in the case where the any is `mostly_clobbered_any'
@@ -1732,15 +1847,15 @@
 % too weak -- it might not be able to detect bugs as well
 % as it can currently.
 
-inst_merge_3(any(UniqA), any(UniqB), InstMap, InstTable, M, any(Uniq),
-		InstMap, InstTable, M) :-
+inst_merge_3(any(UniqA), any(UniqB), _, InstMap, InstTable, M, MS, any(Uniq),
+		InstMap, InstTable, M, MS) :-
 	merge_uniq(UniqA, UniqB, Uniq).
-inst_merge_3(any(Uniq), free(_), InstMap, InstTable, M, any(Uniq), InstMap,
-		InstTable, M) :-
+inst_merge_3(any(Uniq), free(_), _, InstMap, InstTable, M, MS, any(Uniq),
+		InstMap, InstTable, M, MS) :-
 	% we do not yet allow merge of any with free, except for clobbered anys
 	( Uniq = clobbered ; Uniq = mostly_clobbered ).
-inst_merge_3(any(UniqA), bound(UniqB, ListB), InstMap, InstTable, M,
-		any(Uniq), InstMap, InstTable, M) :-
+inst_merge_3(any(UniqA), bound(UniqB, ListB), _, InstMap, InstTable, M, MS,
+		any(Uniq), InstMap, InstTable, M, MS) :-
 	merge_uniq_bound(UniqA, UniqB, ListB, InstMap, InstTable, M, Uniq),
 	% we do not yet allow merge of any with free, except for clobbered anys
 	( ( Uniq = clobbered ; Uniq = mostly_clobbered ) ->
@@ -1748,20 +1863,20 @@
 	;
 		bound_inst_list_is_ground_or_any(ListB, InstMap, InstTable, M)
 	).
-inst_merge_3(any(UniqA), ground(UniqB, _), InstMap, InstTable, M, any(Uniq),
-		InstMap, InstTable, M) :-
+inst_merge_3(any(UniqA), ground(UniqB, _), _, InstMap, InstTable, M, MS,
+		any(Uniq), InstMap, InstTable, M, MS) :-
 	merge_uniq(UniqA, UniqB, Uniq).
-inst_merge_3(any(UniqA), abstract_inst(_, _), InstMap, InstTable, M,
-		any(Uniq), InstMap, InstTable, M) :-
+inst_merge_3(any(UniqA), abstract_inst(_, _), _, InstMap, InstTable, M, MS,
+		any(Uniq), InstMap, InstTable, M, MS) :-
 	merge_uniq(UniqA, shared, Uniq),
 	% we do not yet allow merge of any with free, except for clobbered anys
 	( Uniq = clobbered ; Uniq = mostly_clobbered ).
-inst_merge_3(free(_), any(Uniq), InstMap, InstTable, M, any(Uniq),
-		InstMap, InstTable, M) :-
+inst_merge_3(free(_), any(Uniq), _, InstMap, InstTable, M, MS, any(Uniq),
+		InstMap, InstTable, M, MS) :-
 	% we do not yet allow merge of any with free, except for clobbered anys
 	( Uniq = clobbered ; Uniq = mostly_clobbered ).
-inst_merge_3(bound(UniqA, ListA), any(UniqB), InstMap, InstTable, M,
-		any(Uniq), InstMap, InstTable, M) :-
+inst_merge_3(bound(UniqA, ListA), any(UniqB), _, InstMap, InstTable, M, MS,
+		any(Uniq), InstMap, InstTable, M, MS) :-
 	merge_uniq_bound(UniqB, UniqA, ListA, InstMap, InstTable, M, Uniq),
 	% we do not yet allow merge of any with free, except for clobbered anys
 	( ( Uniq = clobbered ; Uniq = mostly_clobbered ) ->
@@ -1769,35 +1884,38 @@
 	;
 		bound_inst_list_is_ground_or_any(ListA, InstMap, InstTable, M)
 	).
-inst_merge_3(ground(UniqA, _), any(UniqB), InstMap, InstTable, M, any(Uniq),
-		InstMap, InstTable, M) :-
+inst_merge_3(ground(UniqA, _), any(UniqB), _, InstMap, InstTable, M, MS,
+		any(Uniq), InstMap, InstTable, M, MS) :-
 	merge_uniq(UniqA, UniqB, Uniq).
-inst_merge_3(abstract_inst(_, _), any(UniqB), InstMap, InstTable, M,
-		any(Uniq), InstMap, InstTable, M) :-
+inst_merge_3(abstract_inst(_, _), any(UniqB), _, InstMap, InstTable, M, MS,
+		any(Uniq), InstMap, InstTable, M, MS) :-
 	merge_uniq(shared, UniqB, Uniq),
 	% we do not yet allow merge of any with free, except for clobbered anys
 	( Uniq = clobbered ; Uniq = mostly_clobbered ).
-inst_merge_3(free(A), free(A), InstMap, InstTable, M, free(A), InstMap,
-		InstTable, M).
-inst_merge_3(bound(UniqA, ListA), bound(UniqB, ListB), InstMap0, InstTable0,
-		ModuleInfo0, bound(Uniq, List), InstMap, InstTable,
-		ModuleInfo) :-
+inst_merge_3(free(A), free(A), _, InstMap, InstTable, M, MS, free(A),
+		InstMap, InstTable, M, MS).
+inst_merge_3(bound(UniqA, ListA), bound(UniqB, ListB), LiveCounts,
+		InstMap0, InstTable0, ModuleInfo0, MergeSubs0,
+		bound(Uniq, List), InstMap, InstTable, ModuleInfo, MergeSubs) :-
 	merge_uniq(UniqA, UniqB, Uniq),
-	bound_inst_list_merge(ListA, ListB, InstMap0, InstTable0, ModuleInfo0,
-		List, InstMap, InstTable, ModuleInfo).
-inst_merge_3(bound(UniqA, ListA), ground(UniqB, _), InstMap, InstTable,
-		ModuleInfo, ground(Uniq, no), InstMap, InstTable, ModuleInfo) :-
+	bound_inst_list_merge(ListA, ListB, LiveCounts, InstMap0, InstTable0,
+		ModuleInfo0, MergeSubs0, List, InstMap, InstTable, ModuleInfo,
+		MergeSubs).
+inst_merge_3(bound(UniqA, ListA), ground(UniqB, _), _, InstMap,
+		InstTable, ModuleInfo, MS, ground(Uniq, no), InstMap, InstTable,
+		ModuleInfo, MS) :-
 	merge_uniq_bound(UniqB, UniqA, ListA, InstMap, InstTable, ModuleInfo,
 		Uniq),
 	bound_inst_list_is_ground(ListA, InstMap, InstTable, ModuleInfo).
-inst_merge_3(ground(UniqA, _), bound(UniqB, ListB), InstMap, InstTable,
-		ModuleInfo, ground(Uniq, no), InstMap, InstTable, ModuleInfo) :-
+inst_merge_3(ground(UniqA, _), bound(UniqB, ListB), _, InstMap,
+		InstTable, ModuleInfo, MS, ground(Uniq, no), InstMap, InstTable,
+		ModuleInfo, MS) :-
 	merge_uniq_bound(UniqA, UniqB, ListB, InstMap, InstTable,
 			ModuleInfo, Uniq),
 	bound_inst_list_is_ground(ListB, InstMap, InstTable, ModuleInfo).
-inst_merge_3(ground(UniqA, MaybePredA), ground(UniqB, MaybePredB), InstMap,
-		InstTable, ModuleInfo, ground(Uniq, MaybePred), InstMap,
-		InstTable, ModuleInfo) :-
+inst_merge_3(ground(UniqA, MaybePredA), ground(UniqB, MaybePredB), _,
+		InstMap, InstTable, ModuleInfo, MS, ground(Uniq, MaybePred),
+		InstMap, InstTable, ModuleInfo, MS) :-
 	(
 		MaybePredA = yes(PredA),
 		MaybePredB = yes(PredB)
@@ -1823,13 +1941,14 @@
 	),
 	merge_uniq(UniqA, UniqB, Uniq).
 inst_merge_3(abstract_inst(Name, ArgsA), abstract_inst(Name, ArgsB),
-			InstMap0, InstTable0, ModuleInfo0,
-			abstract_inst(Name, Args), InstMap, InstTable,
-			ModuleInfo) :-
-	inst_list_merge(ArgsA, ArgsB, InstMap0, InstTable0, ModuleInfo0, Args,
-			InstMap, InstTable, ModuleInfo).
-inst_merge_3(not_reached, Inst, InstMap, InstTable, M, Inst, InstMap,
-			InstTable, M).
+		LiveCounts, InstMap0, InstTable0, ModuleInfo0, MergeSubs0,
+		abstract_inst(Name, Args), InstMap, InstTable, ModuleInfo,
+		MergeSubs) :-
+	inst_list_merge(ArgsA, ArgsB, LiveCounts, InstMap0, InstTable0,
+		ModuleInfo0, MergeSubs0, Args, InstMap, InstTable, ModuleInfo,
+		MergeSubs).
+inst_merge_3(not_reached, Inst, _, InstMap, InstTable, M, MS, Inst, InstMap,
+			InstTable, M, MS).
 
 :- pred merge_uniq(uniqueness, uniqueness, uniqueness).
 :- mode merge_uniq(in, in, out) is det.
@@ -1922,19 +2041,22 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pred inst_list_merge(list(inst), list(inst), instmap, inst_table,
-		module_info, list(inst), instmap, inst_table, module_info).
-:- mode inst_list_merge(in, in, in, in, in, out, out, out, out) is semidet.
-
-inst_list_merge([], [], InstMap, InstTable, ModuleInfo, [], InstMap,
-		InstTable, ModuleInfo).
-inst_list_merge([ArgA | ArgsA], [ArgB | ArgsB], InstMap0, InstTable0,
-		ModuleInfo0,
-		[Arg | Args], InstMap, InstTable, ModuleInfo) :-
-	inst_merge(ArgA, ArgB, InstMap0, InstTable0, ModuleInfo0,
-		Arg, InstMap1, InstTable1, ModuleInfo1),
-	inst_list_merge(ArgsA, ArgsB, InstMap1, InstTable1, ModuleInfo1,
-		Args, InstMap, InstTable, ModuleInfo).
+:- pred inst_list_merge(list(inst), list(inst), live_counts, instmap,
+		inst_table, module_info, merge_subs, list(inst), instmap,
+		inst_table, module_info, merge_subs).
+:- mode inst_list_merge(in, in, in, in, in, in, in, out, out, out, out, out)
+		is semidet.
+
+inst_list_merge([], [], _, InstMap, InstTable, ModuleInfo, MergeSubs, [],
+		InstMap, InstTable, ModuleInfo, MergeSubs).
+inst_list_merge([ArgA | ArgsA], [ArgB | ArgsB], LiveCounts, InstMap0,
+		InstTable0, ModuleInfo0, MergeSubs0, [Arg | Args], InstMap,
+		InstTable, ModuleInfo, MergeSubs) :-
+	inst_merge(ArgA, ArgB, LiveCounts, InstMap0, InstTable0, ModuleInfo0,
+		MergeSubs0, Arg, InstMap1, InstTable1, ModuleInfo1, MergeSubs1),
+	inst_list_merge(ArgsA, ArgsB, LiveCounts, InstMap1, InstTable1,
+		ModuleInfo1, MergeSubs1, Args, InstMap, InstTable, ModuleInfo,
+		MergeSubs).
 
 	% bound_inst_list_merge(Xs, Ys, InstTable0, ModuleInfo0, Zs, InstTable,
 	%	ModuleInfo):
@@ -1943,24 +2065,26 @@
 	% so that the functors of the output list Zs are the union
 	% of the functors of the input lists Xs and Ys.
 
-:- pred bound_inst_list_merge(list(bound_inst), list(bound_inst),
-			instmap, inst_table, module_info,
-			list(bound_inst), instmap, inst_table, module_info).
-:- mode bound_inst_list_merge(in, in, in, in, in, out, out, out, out)
-			is semidet.
+:- pred bound_inst_list_merge(list(bound_inst), list(bound_inst), live_counts,
+		instmap, inst_table, module_info, merge_subs, list(bound_inst),
+		instmap, inst_table, module_info, merge_subs).
+:- mode bound_inst_list_merge(in, in, in, in, in, in, in, out, out, out, out,
+		out) is semidet.
 
-bound_inst_list_merge(Xs, Ys, InstMap0, InstTable0, ModuleInfo0,
-		Zs, InstMap, InstTable, ModuleInfo) :-
+bound_inst_list_merge(Xs, Ys, LiveCounts, InstMap0, InstTable0, ModuleInfo0,
+		MergeSubs0, Zs, InstMap, InstTable, ModuleInfo, MergeSubs) :-
 	( Xs = [] ->
-		Zs = Ys,
+		MergeSubs = MergeSubs0,
 		ModuleInfo = ModuleInfo0,
 		InstTable = InstTable0,
-		InstMap = InstMap0
+		InstMap = InstMap0,
+		Zs = Ys
 	; Ys = [] ->
-		Zs = Xs,
+		MergeSubs = MergeSubs0,
 		ModuleInfo = ModuleInfo0,
 		InstTable = InstTable0,
-		InstMap = InstMap0
+		InstMap = InstMap0,
+		Zs = Xs
 	;
 		Xs = [X | Xs1],
 		Ys = [Y | Ys1],
@@ -1967,27 +2091,60 @@
 		X = functor(ConsIdX, ArgsX),
 		Y = functor(ConsIdY, ArgsY),
 		( ConsIdX = ConsIdY ->
-			inst_list_merge(ArgsX, ArgsY, InstMap0, InstTable0,
-					ModuleInfo0, Args, InstMap1,
-					InstTable1, ModuleInfo1),
+			inst_list_merge(ArgsX, ArgsY, LiveCounts, InstMap0,
+				InstTable0, ModuleInfo0, MergeSubs0, Args,
+				InstMap1, InstTable1, ModuleInfo1, MergeSubs1),
 			Z = functor(ConsIdX, Args),
 			Zs = [Z | Zs1],
-			bound_inst_list_merge(Xs1, Ys1, InstMap1, InstTable1,
-				ModuleInfo1, Zs1, InstMap, InstTable,
-				ModuleInfo)
+			bound_inst_list_merge(Xs1, Ys1, LiveCounts, InstMap1,
+				InstTable1, ModuleInfo1, MergeSubs1, Zs1,
+				InstMap, InstTable, ModuleInfo, MergeSubs)
 		; compare(<, ConsIdX, ConsIdY) ->
 			Zs = [X | Zs1],
-			bound_inst_list_merge(Xs1, Ys, InstMap0, InstTable0,
-				ModuleInfo0, Zs1, InstMap, InstTable,
-				ModuleInfo)
+			bound_inst_list_merge(Xs1, Ys, LiveCounts, InstMap0,
+				InstTable0, ModuleInfo0, MergeSubs0, Zs1,
+				InstMap, InstTable, ModuleInfo, MergeSubs)
 		;
 			Zs = [Y | Zs1],
-			bound_inst_list_merge(Xs, Ys1, InstMap0, InstTable0,
-				ModuleInfo0, Zs1, InstMap, InstTable,
-				ModuleInfo)
+			bound_inst_list_merge(Xs, Ys1, LiveCounts, InstMap0,
+				InstTable0, ModuleInfo0, MergeSubs0, Zs1,
+				InstMap, InstTable, ModuleInfo, MergeSubs)
+		)
+	).
+
+%-----------------------------------------------------------------------------%
+
+:- pred expand_inst(inst_key_counts, instmap, inst_table, module_info, inst,
+		inst).
+:- mode expand_inst(in, in, in, in, in, out) is det.
+
+expand_inst(LiveCounts, InstMap, InstTable, ModuleInfo, Inst0, Inst) :-
+	( Inst0 = alias(IK) ->
+		( has_count_many(LiveCounts, IK) ->
+			Inst = Inst0
+		;
+			inst_expand(InstMap, InstTable, ModuleInfo, Inst0, Inst)
 		)
+	;
+		inst_expand_defined_inst(InstTable, ModuleInfo, Inst0, Inst)
 	).
 
+:- pred make_shared_merge_insts(inst_key, pred(inst), instmap, inst_table,
+	module_info, inst, instmap, inst_table, module_info).
+:- mode make_shared_merge_insts(in, pred(out) is nondet,
+	in, in, in, out, out, out, out) is semidet.
+
+make_shared_merge_insts(IK0, Lambda, InstMap0, InstTable0, ModuleInfo0, Inst,
+		InstMap, InstTable, ModuleInfo) :-
+	UI0 = unify_inst_info(ModuleInfo0, InstTable0, InstMap0),
+	make_shared_inst(alias(IK0), UI0, Inst1, UI1),
+	solutions(Lambda, Insts),
+	make_shared_inst_list(Insts, UI1, _, UI),
+	UI = unify_inst_info(ModuleInfo, InstTable, InstMap),
+	Inst1 = alias(IK),
+	inst_table_get_inst_key_table(InstTable, IKT),
+	instmap__inst_key_table_lookup(InstMap, IKT, IK, Inst).
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -2035,12 +2192,13 @@
 %-----------------------------------------------------------------------------%
 
 inst_table_create_sub(InstTable0, NewInstTable, Sub, InstTable) :-
-	inst_table_get_all_tables(InstTable0, UnifyInstTable0,
+	inst_table_get_all_tables(InstTable0, SubInstTable0, UnifyInstTable0,
 		MergeInstTable0, GroundInstTable0, AnyInstTable0,
 		SharedInstTable0, MostlyUniqInstTable0, IKT0),
-	inst_table_get_all_tables(NewInstTable, NewUnifyInstTable,
-		NewMergeInstTable, NewGroundInstTable, NewAnyInstTable,
-		NewSharedInstTable, NewMostlyUniqInstTable, NewIKT),
+	inst_table_get_all_tables(NewInstTable, NewSubInstTable,
+		NewUnifyInstTable, NewMergeInstTable, NewGroundInstTable,
+		NewAnyInstTable, NewSharedInstTable, NewMostlyUniqInstTable,
+		NewIKT),
 	inst_key_table_create_sub(IKT0, NewIKT, Sub, IKT),
 
 	maybe_inst_det_table_apply_sub(UnifyInstTable0, NewUnifyInstTable,
@@ -2049,6 +2207,9 @@
 	merge_inst_table_apply_sub(MergeInstTable0, NewMergeInstTable,
 		MergeInstTable, Sub),
 
+	substitution_inst_table_apply_sub(SubInstTable0, NewSubInstTable,
+		SubInstTable, Sub),
+
 	maybe_inst_det_table_apply_sub(GroundInstTable0, NewGroundInstTable,
 		GroundInstTable, Sub),
 
@@ -2067,7 +2228,7 @@
 	;
 		error("NYI: inst_table_create_sub (mostly_uniq_inst_table)")
 	),
-	inst_table_set_all_tables(InstTable0, UnifyInstTable,
+	inst_table_set_all_tables(InstTable0, SubInstTable, UnifyInstTable,
 		MergeInstTable, GroundInstTable, AnyInstTable,
 		SharedInstTable, MostlyUniqInstTable, IKT, InstTable).
 
@@ -2166,6 +2327,39 @@
 	map__set(Table0, IA - IB, Inst, Table1),
 	merge_inst_table_apply_sub_2(Rest, Table1, Table, Sub).
 
+:- pred substitution_inst_table_apply_sub(substitution_inst_table,
+	substitution_inst_table, substitution_inst_table, inst_key_sub).
+:- mode substitution_inst_table_apply_sub(in, in, out, in) is det.
+
+substitution_inst_table_apply_sub(Table0, NewTable, Table, Sub) :-
+	( map__is_empty(Table0) ->
+		% Optimise common case
+		Table = Table0
+	;
+		map__to_assoc_list(NewTable, NewTableAL),
+		substitution_inst_table_apply_sub_2(NewTableAL, Table0, Table,
+			Sub)
+	).
+
+:- pred substitution_inst_table_apply_sub_2(assoc_list(substitution_inst,
+	maybe_inst), substitution_inst_table, substitution_inst_table,
+	inst_key_sub).
+:- mode substitution_inst_table_apply_sub_2(in, in, out, in) is det.
+
+substitution_inst_table_apply_sub_2([], Table, Table, _).
+substitution_inst_table_apply_sub_2(
+		[substitution_inst(InstName0, K, S) - Inst0 | Rest],
+		Table0, Table, Sub) :-
+	inst_name_apply_sub(Sub, InstName0, InstName),
+	( Inst0 = unknown,
+		Inst = unknown
+	; Inst0 = known(I0),
+		inst_apply_sub(Sub, I0, I),
+		Inst = known(I)
+	),
+	map__set(Table0, substitution_inst(InstName, K, S), Inst, Table1),
+	substitution_inst_table_apply_sub_2(Rest, Table1, Table, Sub).
+
 :- pred inst_name_apply_sub(inst_key_sub, inst_name, inst_name).
 :- mode inst_name_apply_sub(in, in, out) is det.
 
@@ -2192,7 +2386,77 @@
 inst_name_apply_sub(_Sub, typed_ground(Uniq, Type), typed_ground(Uniq, Type)).
 inst_name_apply_sub(Sub, typed_inst(Type, Name0), typed_inst(Type, Name)) :-
 	inst_name_apply_sub(Sub, Name0, Name).
+inst_name_apply_sub(Sub, substitution_inst(Name0, K, S),
+		substitution_inst(Name, K, S)) :-
+	inst_name_apply_sub(Sub, Name0, Name).
+
+%-----------------------------------------------------------------------------%
 
+inst_fold(InstMap, InstTable, ModuleInfo, Before, After, Merge, Inst) -->
+	{ set__init(Recursive) },
+	inst_fold_2(InstMap, InstTable, ModuleInfo, Recursive, Before, After,
+		Merge, Inst).
+
+:- pred inst_fold_2(instmap, inst_table, module_info, set(inst_name),
+		inst_fold_pred(T), inst_fold_pred(T), inst_fold_merge_pred(T),
+		inst, T, T).
+:- mode inst_fold_2(in, in, in, in, inst_fold_pred, inst_fold_pred,
+		inst_fold_merge_pred, in, in, out) is det.
+
+inst_fold_2(InstMap, InstTable, ModuleInfo, Recursive, Before, After, Merge,
+		Inst) -->
+	( call(Before, Inst, Recursive) -> [] ; [] ),
+	inst_fold_3(InstMap, InstTable, ModuleInfo, Recursive, Before, After,
+		Merge, Inst),
+	( call(After, Inst, Recursive) -> [] ; [] ).
+
+:- pred inst_fold_3(instmap, inst_table, module_info, set(inst_name),
+		inst_fold_pred(T), inst_fold_pred(T), inst_fold_merge_pred(T),
+		inst, T, T).
+:- mode inst_fold_3(in, in, in, in, inst_fold_pred, inst_fold_pred,
+		inst_fold_merge_pred, in, in, out) is det.
+
+inst_fold_3(_, _, _, _, _, _, _, any(_)) --> [].
+inst_fold_3(InstMap, InstTable, ModuleInfo, Recursive, Before, After, Merge,
+		alias(Key)) -->
+	{ inst_table_get_inst_key_table(InstTable, IKT) },
+	{ instmap__inst_key_table_lookup(InstMap, IKT, Key, Inst) },
+	inst_fold_2(InstMap, InstTable, ModuleInfo, Recursive, Before, After,
+		Merge, Inst).
+inst_fold_3(_, _, _, _, _, _, _, free(_)) --> [].
+inst_fold_3(_, _, _, _, _, _, _, free(_, _)) --> [].
+inst_fold_3(InstMap, InstTable, ModuleInfo, Recursive, Before, After, Merge,
+		bound(_, BoundInsts0)) -->
+	( { BoundInsts0 = [] }
+	; { BoundInsts0 = [functor(_, Insts0) | BoundInsts1] },
+		=(Acc0),
+		list__foldl(inst_fold_2(InstMap, InstTable, ModuleInfo,
+			Recursive, Before, After, Merge), Insts0),
+		list__foldl(lambda([BI::in, A0::in, A::out] is det,
+		(   
+			BI = functor(_, Insts),
+			list__foldl(inst_fold_2(InstMap, InstTable, ModuleInfo,
+			    Recursive, Before, After, Merge), Insts, Acc0, A1),
+			call(Merge, A0, A1, A)
+		)), BoundInsts1)
+	).
+inst_fold_3(_, _, _, _, _, _, _, ground(_, _)) --> [].
+inst_fold_3(_, _, _, _, _, _, _, not_reached) --> [].
+inst_fold_3(_, _, _, _, _, _, _, inst_var(_)) --> [].
+inst_fold_3(InstMap, InstTable, ModuleInfo, Recursive0, Before, After,
+		Merge, defined_inst(InstName)) -->
+	( { set__member(InstName, Recursive0) } ->
+		[]
+	;
+		{ set__insert(Recursive0, InstName, Recursive) },
+		{ inst_lookup(InstTable, ModuleInfo, InstName, Inst) },
+		inst_fold_2(InstMap, InstTable, ModuleInfo, Recursive, Before,
+			After, Merge, Inst)
+	).
+inst_fold_3(InstMap, InstTable, ModuleInfo, Recursive, Before, After,
+		Merge, abstract_inst(_, Insts)) -->
+	list__foldl(inst_fold_2(InstMap, InstTable, ModuleInfo, Recursive,
+		Before, After, Merge), Insts).
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
Index: instmap.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/instmap.m,v
retrieving revision 1.15.2.19
diff -u -w -r1.15.2.19 instmap.m
--- 1.15.2.19	1998/11/24 06:28:56
+++ instmap.m	1999/01/19 01:32:34
@@ -165,12 +165,13 @@
 	%       instantiatedness of all the nonlocal variables,
 	%       checking that it is the same for every branch.
 	%
-:- pred instmap__merge(set(prog_var), list(instmap),
+:- pred instmap__merge(set(prog_var), list(prog_var), list(instmap),
 		instmap, instmap, module_info, inst_table,
 		module_info, inst_table, merge_errors).
-:- mode instmap__merge(in, in, in, out, in, in, out, out, out) is det.
+:- mode instmap__merge(in, in, in, in, out, in, in, out, out, out) is det.
 
-	% instmap_merge(NonLocalVars, InstMaps, MergeContext):
+	% instmap_merge(NonLocalVars, LiveVars, InstMaps, InitialInstMap,
+	%		FinalInstMap, MergeContext):
 	%       Merge the `InstMaps' resulting from different branches
 	%       of a disjunction or if-then-else, and update the
 	%       instantiatedness of all the nonlocal variables,
@@ -267,6 +268,11 @@
 
 %-----------------------------------------------------------------------------%
 
+:- pred instmap__inst_keys_are_equivalent(inst_key, instmap, inst_key, instmap).
+:- mode instmap__inst_keys_are_equivalent(in, in, in, in) is semidet.
+
+%-----------------------------------------------------------------------------%
+
 :- pred instmap__get_inst_key_sub(instmap, inst_key_sub).
 :- mode instmap__get_inst_key_sub(in, out) is det.
 
@@ -319,13 +325,17 @@
 
 %-----------------------------------------------------------------------------%
 
-instmap__from_assoc_list(AL, reachable(Instmapping, AliasMap)) :-
+instmap__from_assoc_list(AL, InstMap) :-
+	( list__member(_ - not_reached, AL) ->
+		InstMap = unreachable
+	;
 	map__from_assoc_list(AL, Instmapping),
-	map__init(AliasMap).
+		map__init(AliasMap),
+		InstMap = reachable(Instmapping, AliasMap)
+	).
 
-instmap_delta_from_assoc_list(AL, reachable(Instmapping, AliasMap)) :-
-	map__from_assoc_list(AL, Instmapping),
-	map__init(AliasMap).
+instmap_delta_from_assoc_list(AL, InstMapDelta) :-
+	instmap__from_assoc_list(AL, InstMapDelta).
 
 %-----------------------------------------------------------------------------%
 
@@ -499,7 +509,9 @@
 	mode_info_get_instmap(ModeInfo0, InstMapBefore),
 	mode_info_get_inst_table(ModeInfo0, InstTable0),
 	mode_info_get_module_info(ModeInfo0, ModuleInfo0),
-	instmap__merge(NonLocals, InstMapList, InstMapBefore,
+	mode_info_get_liveness(ModeInfo0, Liveness),
+	set__to_sorted_list(Liveness, LiveList),
+	instmap__merge(NonLocals, LiveList, InstMapList, InstMapBefore,
 		InstMapAfter, ModuleInfo0, InstTable0, ModuleInfo, InstTable,
 		ErrorList),
 	( ErrorList = [FirstError | _] ->
@@ -516,12 +528,12 @@
 	mode_info_set_instmap(InstMapAfter, ModeInfo2, ModeInfo3),
 	mode_info_set_inst_table(InstTable, ModeInfo3, ModeInfo).
 
-instmap__merge(NonLocals, InstMapList, InstMap0,
+instmap__merge(NonLocals, Liveness, InstMapList0, InstMap0,
 		InstMap, ModuleInfo0, InstTable0, ModuleInfo, InstTable,
 		ErrorList) :-
-	get_reachable_instmaps(InstMapList, InstMappingList),
+	get_reachable_instmaps(InstMapList0, InstMapList1),
 	(
-		InstMappingList = []
+		InstMapList1 = []
 	->
 		InstMap = unreachable,
 		ModuleInfo = ModuleInfo0,
@@ -529,22 +541,21 @@
 		ErrorList = []
 	;
 		InstMap0 = reachable(_, _),
-		InstMappingList = [InstMapping - AliasMap]
+		InstMapList1 = [InstMap1]
 	->
-		instmap__restrict(reachable(InstMapping, AliasMap), NonLocals,
-				InstMap),
+		InstMap = InstMap1,
 		ModuleInfo = ModuleInfo0,
 		InstTable = InstTable0,
 		ErrorList = []
 	;
-		InstMap0 = reachable(InstMapping0, _AliasMap0)
+		InstMap0 = reachable(_, _)
 	->
-		set__to_sorted_list(NonLocals, NonLocalsList),
-		instmap__merge_2(NonLocalsList, InstMapList, InstTable0,
-			ModuleInfo0, InstMapping0, InstTable, ModuleInfo,
-			InstMapping, ErrorList),
-		map__init(AliasMap),
-		InstMap = reachable(InstMapping, AliasMap)
+		instmap__vars(InstMap0, Vars0),
+		set__union(NonLocals, Vars0, AllNonLocals),
+		set__to_sorted_list(AllNonLocals, AllNonLocalsList),
+		instmap__merge_2(AllNonLocalsList, Liveness, InstMapList1,
+			InstTable0, ModuleInfo0, InstMap0, InstTable,
+			ModuleInfo, InstMap, ErrorList)
 	;
 		InstMap = unreachable,
 		ModuleInfo = ModuleInfo0,
@@ -552,187 +563,553 @@
 		ErrorList = []
 	).
 
-:- pred get_reachable_instmaps(list(instmap),
-		list(pair(map(prog_var, inst), inst_key_sub))).
+:- pred get_reachable_instmaps(list(instmap), list(instmap)).
 :- mode get_reachable_instmaps(in, out) is det.
 
-get_reachable_instmaps([], []).
-get_reachable_instmaps([InstMap | InstMaps], Reachables) :-
-	( InstMap = reachable(InstMapping, AliasMap) ->
-		Reachables = [InstMapping - AliasMap | Reachables1],
-		get_reachable_instmaps(InstMaps, Reachables1)
+get_reachable_instmaps -->
+	list__filter(instmap__is_reachable).
+
+%-----------------------------------------------------------------------------%
+
+:- interface.
+
+% Export this stuff for use in inst_util.m.
+  
+:- type uniq_count
+	--->	zero
+	;	one
+	;	many.
+
+:- type uniq_counts(T) == map(T, uniq_count).
+
+:- type inst_key_counts == uniq_counts(inst_key).
+
+:- pred inc_uniq_count(T, uniq_counts(T), uniq_counts(T)).
+:- mode inc_uniq_count(in, in, out) is det.
+
+:- pred set_uniq_count_many(T, uniq_counts(T), uniq_counts(T)).
+:- mode set_uniq_count_many(in, in, out) is det.
+
+:- pred has_count_zero(uniq_counts(T), T).
+:- mode has_count_zero(in, in) is semidet.
+
+:- pred has_count_one(uniq_counts(T), T).
+:- mode has_count_one(in, in) is semidet.
+
+:- pred has_count_many(uniq_counts(T), T).
+:- mode has_count_many(in, in) is semidet.
+
+:- pred uniq_count_max(uniq_count, uniq_count, uniq_count).
+:- mode uniq_count_max(in, in, out) is det.
+
+:- pred uniq_counts_max_merge(uniq_counts(T), uniq_counts(T), uniq_counts(T)).
+:- mode uniq_counts_max_merge(in, in, out) is det.
+
+:- implementation.
+
+inc_uniq_count(Item, Map0, Map) :-
+	( map__search(Map0, Item, C0) ->
+		( C0 = zero,
+			map__det_update(Map0, Item, one, Map)
+		; C0 = one,
+			map__det_update(Map0, Item, many, Map)
+		; C0 = many,
+			Map = Map0
+		)
 	;
-		get_reachable_instmaps(InstMaps, Reachables)
+		map__det_insert(Map0, Item, one, Map)
 	).
 
+set_uniq_count_many(Item, Map0, Map) :-
+	map__set(Map0, Item, many, Map).
+
+has_count_zero(Map, Item) :-
+	% map__search(Map, Item, Count) => Count = zero.
+	\+ ( map__search(Map, Item, Count), \+ Count = zero ).
+
+has_count_one(Map, Item) :-
+	map__search(Map, Item, one).
+
+has_count_many(Map, Item) :-
+	map__search(Map, Item, many).
+
+uniq_count_max(zero, Count, Count).
+uniq_count_max(many, _, many).
+uniq_count_max(one, zero, one).
+uniq_count_max(one, one, one).
+uniq_count_max(one, many, many).
+
+uniq_counts_max_merge(MapA, MapB, Map) :-
+	map__foldl(lambda([Item::in, CountA::in, M0::in, M::out] is det,
+		( map__search(M0, Item, CountB) ->
+			uniq_count_max(CountA, CountB, Count),
+			( Count = CountB ->
+				M = M0
+			;
+				map__det_update(M0, Item, Count, M)
+			)
+		;
+			map__det_insert(M0, Item, CountA, M)
+		)), MapA, MapB, Map).
+
 %-----------------------------------------------------------------------------%
 
-	% instmap__get_relevant_inst_keys(Vars, InstMaps, InstTable, SeenKeys,
+	% instmap__count_inst_keys(Vars, InstMaps, InstTable, SeenKeys,
 	%		DuplicateKeys, InstKeys):
 	%	Return a set of all inst_keys which appear more than
 	%	once in the instmaps.
 
-:- pred instmap__get_relevant_inst_keys(list(prog_var), list(instmap),
-		module_info, inst_table, set_bbbtree(inst_key)).
-:- mode instmap__get_relevant_inst_keys(in, in, in, in, out) is det.
-
-instmap__get_relevant_inst_keys(Vars, InstMaps, ModuleInfo, InstTable,
-		RelevantIKs) :-
-	set_bbbtree__init(Seen0),
-	set_bbbtree__init(Duplicate0),
-	list__foldl2(instmap__get_relevant_inst_keys_2(Vars, ModuleInfo,
-				InstTable),
-		InstMaps, Seen0, _Seen, Duplicate0, Duplicate),
-	RelevantIKs = Duplicate.
-
-:- pred instmap__get_relevant_inst_keys_2(list(prog_var), module_info,
-		inst_table, instmap, set_bbbtree(inst_key),
-		set_bbbtree(inst_key), set_bbbtree(inst_key),
-		set_bbbtree(inst_key)).
-:- mode instmap__get_relevant_inst_keys_2(in, in, in, in,
-		in, out, in, out) is det.
-
-instmap__get_relevant_inst_keys_2([], _InstTable, _ModuleInfo, _InstMap,
-		Seen, Seen, Duplicate, Duplicate).
-instmap__get_relevant_inst_keys_2([V | Vs], ModuleInfo, InstTable, InstMap,
-		Seen0, Seen, Duplicate0, Duplicate) :-
-	instmap__lookup_var(InstMap, V, Inst),
-	set_bbbtree__init(Recursive),
-	instmap__get_relevant_inst_keys_in_inst(Inst, Recursive, ModuleInfo,
-		InstTable, Seen0, Seen1, Duplicate0, Duplicate1),
-	instmap__get_relevant_inst_keys_2(Vs, ModuleInfo, InstTable, InstMap,
-		Seen1, Seen, Duplicate1, Duplicate).
-
-:- pred instmap__get_relevant_inst_keys_in_inst(inst, set_bbbtree(inst_name),
-		module_info, inst_table, set_bbbtree(inst_key),
-		set_bbbtree(inst_key), set_bbbtree(inst_key),
-		set_bbbtree(inst_key)).
-:- mode instmap__get_relevant_inst_keys_in_inst(in, in, in, in,
-		in, out, in, out) is det.
-
-instmap__get_relevant_inst_keys_in_inst(any(_), _, _, _, S, S, D, D).
-instmap__get_relevant_inst_keys_in_inst(alias(Key), Recursive, ModuleInfo,
-		InstTable, S0, S, D0, D) :-
-	inst_table_get_inst_key_table(InstTable, IKT),
-	inst_key_table_lookup(IKT, Key, Inst),
-	( set_bbbtree__member(Key, S0) ->
-		set_bbbtree__insert(D0, Key, D1),
-		S1 = S0
-	;
-		set_bbbtree__insert(S0, Key, S1),
-		D1 = D0
-	),
-	instmap__get_relevant_inst_keys_in_inst(Inst, Recursive, ModuleInfo,
-		InstTable, S1, S, D1, D).
-instmap__get_relevant_inst_keys_in_inst(free(_), _, _, _, S, S, D, D).
-instmap__get_relevant_inst_keys_in_inst(free(_, _), _, _, _, S, S, D, D).
-instmap__get_relevant_inst_keys_in_inst(bound(_, BoundInsts), Rec, ModuleInfo,
-		InstTable, S0, S, D0, D) :-
-	list__foldl2(lambda([BoundInst :: in, AS0 :: in, AS :: out,
-				AD0 :: in, AD :: out] is det,
-			( BoundInst = functor(_, Insts),
-			  list__foldl2(lambda([Inst :: in, BS0 :: in, BS :: out,
-						BD0 :: in, BD :: out] is det,
-				instmap__get_relevant_inst_keys_in_inst(Inst,
-					Rec, ModuleInfo, InstTable,
-					BS0, BS, BD0, BD)),
-				Insts, AS0, AS, AD0, AD)
-			)
-		), BoundInsts, S0, S, D0, D).
-instmap__get_relevant_inst_keys_in_inst(ground(_, _), _, _, _, S, S, D, D).
-instmap__get_relevant_inst_keys_in_inst(not_reached, _, _, _, _, _, _, _) :-
-	error("instmap__get_relevant_inst_keys_in_inst: not_reached").
-instmap__get_relevant_inst_keys_in_inst(inst_var(_), _, _, _, _, _, _, _) :-
-	error("instmap__get_relevant_inst_keys_in_inst: inst_var").
-instmap__get_relevant_inst_keys_in_inst(defined_inst(InstName), Recursive0,
-		ModuleInfo, InstTable, S0, S, D0, D) :-
-	% This is tricky, because an inst_key is "relevant" if it
-	% appears only once in an inst which is recursive.  (If we
-	% were to unfold the inst, it would appear multiple times.)
-	( set_bbbtree__member(InstName, Recursive0) ->
-		set_bbbtree__union(S0, D0, D),
-		S = S0
-	;
-		set_bbbtree__insert(Recursive0, InstName, Recursive),
-		set_bbbtree__init(NewS0),
-		inst_lookup(InstTable, ModuleInfo, InstName, Inst),
-		instmap__get_relevant_inst_keys_in_inst(Inst, Recursive,
-			ModuleInfo, InstTable, NewS0, NewS, D0, D1),
-		set_bbbtree__intersect(NewS, S0, NewD),
-		set_bbbtree__union(NewD, D1, D),
-		set_bbbtree__union(NewS, S0, S)
-	).
-instmap__get_relevant_inst_keys_in_inst(abstract_inst(_, Insts), Rec,
-		ModuleInfo, InstTable, S0, S, D0, D) :-
-	list__foldl2(lambda([Inst :: in, AS0 :: in, AS :: out,
-				AD0 :: in, AD :: out] is det,
-			instmap__get_relevant_inst_keys_in_inst(Inst,
-				Rec, ModuleInfo, InstTable, AS0, AS, AD0, AD)),
-		Insts, S0, S, D0, D).
+:- pred instmap__count_inst_keys_in_instmaps(list(prog_var), list(instmap),
+		module_info, inst_table, inst_key_counts).
+:- mode instmap__count_inst_keys_in_instmaps(in, in, in, in, out) is det.
+
+instmap__count_inst_keys_in_instmaps(Vars, InstMaps, ModuleInfo, InstTable,
+		IKCounts) :-
+	map__init(IKCounts0),
+	list__foldl(instmap__count_inst_keys_2(Vars, ModuleInfo, InstTable),
+		InstMaps, IKCounts0, IKCounts).
+
+:- pred instmap__count_inst_keys(list(prog_var), module_info, inst_table,
+	instmap, inst_key_counts).
+:- mode instmap__count_inst_keys(in, in, in, in, out) is det.
+
+instmap__count_inst_keys(Vars, ModuleInfo, InstTable, InstMap, IKCounts) :-
+	map__init(IKCounts0),
+	instmap__count_inst_keys_2(Vars, ModuleInfo, InstTable, InstMap,
+		IKCounts0, IKCounts).
+
+:- pred instmap__count_inst_keys_2(list(prog_var), module_info,
+	inst_table, instmap, inst_key_counts, inst_key_counts).
+:- mode instmap__count_inst_keys_2(in, in, in, in, in, out) is det.
+
+instmap__count_inst_keys_2([], _InstTable, _ModuleInfo, _InstMap) --> [].
+instmap__count_inst_keys_2([V | Vs], ModuleInfo, InstTable, InstMap) -->
+	{ instmap__lookup_var(InstMap, V, Inst) },
+	{ set__init(SeenTwice) },
+	instmap__count_inst_keys_in_inst(InstMap, InstTable, ModuleInfo,
+		SeenTwice, Inst),
+	instmap__count_inst_keys_2(Vs, ModuleInfo, InstTable, InstMap).
+
+:- pred instmap__count_inst_keys_in_inst(instmap, inst_table, module_info,
+	set(inst_name), inst, inst_key_counts, inst_key_counts).
+:- mode instmap__count_inst_keys_in_inst(in, in, in, in, in, in, out) is det.
+
+instmap__count_inst_keys_in_inst(InstMap, InstTable, ModuleInfo, SeenTwice,
+		Inst) -->
+	inst_fold(InstMap, InstTable, ModuleInfo, count_inst_keys_before, 
+	    count_inst_keys_after(InstMap, InstTable, ModuleInfo, SeenTwice),
+	    uniq_counts_max_merge, Inst).
+
+:- pred count_inst_keys_before((inst)::in, set(inst_name)::in,
+	inst_key_counts::in, inst_key_counts::out) is semidet.
+
+count_inst_keys_before(alias(Key), _) -->
+	inc_uniq_count(Key).
+
+:- pred count_inst_keys_after(instmap::in, inst_table::in, module_info::in,
+	set(inst_name)::in, (inst)::in, set(inst_name)::in,
+	inst_key_counts::in, inst_key_counts::out) is semidet.
+
+count_inst_keys_after(InstMap, InstTable, ModuleInfo, SeenTwice0,
+		defined_inst(InstName), SeenOnce) -->
+	{ set__member(InstName, SeenOnce) },
+	{ \+ set__member(InstName, SeenTwice0) },
+	{ set__insert(SeenTwice0, InstName, SeenTwice) },
+
+		% We need to count the inst_keys in a recursive inst twice
+		% because the inst may be unfolded an arbitrary number of
+		% times.
+	instmap__count_inst_keys_in_inst(InstMap, InstTable, ModuleInfo,
+		SeenTwice, defined_inst(InstName)).
 
 %-----------------------------------------------------------------------------%
 
-	% instmap__merge_2(Vars, InstMaps, ModuleInfo, ErrorList):
-	%       Let `ErrorList' be the list of variables in `Vars' for
+	% instmap__merge_2(Vars, Liveness, InstMaps, ModuleInfo, ErrorList):
+	%       Let `ErrorList' be the list of variables in `Vars' for which
 	%       there are two instmaps in `InstMaps' for which the inst
 	%       the variable is incompatible.
 
-:- pred instmap__merge_2(list(prog_var), list(instmap), inst_table, module_info,
-			map(prog_var, inst), inst_table, module_info,
-			map(prog_var, inst), merge_errors).
-:- mode instmap__merge_2(in, in, in, in, in, out, out, out, out) is det.
-
-instmap__merge_2([], _, InstTable, ModuleInfo, InstMap, InstTable, ModuleInfo,
-			InstMap, []).
-instmap__merge_2([Var|Vars], InstMapList, InstTable0, ModuleInfo0, InstMap0,
-			InstTable, ModuleInfo, InstMap, ErrorList) :-
-	instmap__merge_2(Vars, InstMapList, InstTable0, ModuleInfo0, InstMap0,
-			InstTable1, ModuleInfo1, InstMap1, ErrorList1),
-	instmap__merge_var(InstMapList, Var, InstTable1, ModuleInfo1,
-			Insts, Inst, InstTable, ModuleInfo, Error),
-	( Error = yes ->
-		ErrorList = [Var - Insts | ErrorList1],
-		map__set(InstMap1, Var, not_reached, InstMap)
+:- pred instmap__merge_2(list(prog_var), list(prog_var), list(instmap),
+		inst_table, module_info, instmap, inst_table, module_info,
+		instmap, merge_errors).
+:- mode instmap__merge_2(in, in, in, in, in, in, out, out, out, out) is det.
+
+instmap__merge_2(_, _, [], InstTable, ModuleInfo, InstMap, InstTable,
+		ModuleInfo, InstMap, []).
+instmap__merge_2(Vars, Liveness, [InstMapA | InstMaps], InstTable0, ModuleInfo0,
+		InstMap0, InstTable, ModuleInfo, InstMap, ErrorList) :-
+	instmap__merge_3(Vars, Liveness, InstMapA, InstMaps, InstTable0,
+		ModuleInfo0, InstMap0, InstTable, ModuleInfo, InstMap1,
+		ErrorList),
+	instmap__remove_singleton_inst_keys(Vars, ModuleInfo, InstTable,
+		InstMap1, InstMap).
+
+:- pred instmap__merge_3(list(prog_var), list(prog_var), instmap,
+		list(instmap), inst_table, module_info, instmap, inst_table,
+		module_info, instmap, merge_errors).
+:- mode instmap__merge_3(in, in, in, in, in, in, in, out, out, out, out)
+		is det.
+
+instmap__merge_3(_, _, InstMap, [], InstTable, ModuleInfo, _InstMap0,
+		InstTable, ModuleInfo, InstMap, []).
+instmap__merge_3(Vars, Liveness, InstMapA0, [InstMapB0 | InstMaps], InstTable0,
+		ModuleInfo0, InstMap00, InstTable, ModuleInfo, InstMap,
+		ErrorList) :-
+	instmap__remove_singleton_inst_keys(Vars, ModuleInfo0, InstTable0,
+		InstMapA0, InstMapA1),
+	instmap__remove_singleton_inst_keys(Vars, ModuleInfo0, InstTable0,
+		InstMapB0, InstMapB1),
+
+	instmap__merge_subs(InstMapA1, InstMapB1, InstMap00, InstTable0,
+		ModuleInfo0, InstMapA, InstMapB, InstMap0, InstTable1),
+
+	instmap__count_inst_keys(Liveness, ModuleInfo0, InstTable1, InstMapA,
+		LiveCountsA),
+	instmap__count_inst_keys(Liveness, ModuleInfo0, InstTable1, InstMapB,
+		LiveCountsB),
+	LiveCounts = LiveCountsA - LiveCountsB,
+
+	map__init(MergeSubs0),
+	instmap__merge_4(Vars, InstMapA, InstMapB, LiveCounts, InstTable1,
+		ModuleInfo0, InstMap0, MergeSubs0, InstTable2,
+		ModuleInfo1, InstMapAB0, MergeSubs, ErrorList0),
+
+	% Work out which inst keys need to be made shared.
+	solutions(lambda([I::out] is nondet, (
+		map__member(MergeSubs, IKA0 - IKB0, IK),
+		map__member(MergeSubs, IKA1 - IKB1, _),
+		\+ (
+			instmap__inst_keys_are_equivalent(IKA0, InstMapAB0,
+				IKA1, InstMapAB0)
+		<=>
+			instmap__inst_keys_are_equivalent(IKB0, InstMapAB0,
+				IKB1, InstMapAB0)
+		),
+		I = alias(IK) )), Insts),
+	make_shared_inst_list(Insts, InstTable2, ModuleInfo1, InstMapAB0,
+		_, InstTable3, ModuleInfo2, InstMapAB),
+
+	instmap__merge_3(Vars, Liveness, InstMapAB, InstMaps, InstTable3,
+		ModuleInfo2, InstMap0, InstTable, ModuleInfo, InstMap,
+		ErrorList1),
+	list__append(ErrorList0, ErrorList1, ErrorList).
+
+:- pred instmap__merge_4(list(prog_var), instmap, instmap,
+	pair(inst_key_counts), inst_table, module_info, instmap, merge_subs,
+	inst_table, module_info, instmap, merge_subs, merge_errors).
+:- mode instmap__merge_4(in, in, in, in, in, in, in, in, out, out, out,
+	out, out) is det.
+
+instmap__merge_4([], _, _, _, InstTable, ModuleInfo, InstMap, MergeSubs,
+		InstTable, ModuleInfo, InstMap, MergeSubs, []).
+instmap__merge_4([Var | Vars], InstMapA, InstMapB, LiveCounts, InstTable0,
+		ModuleInfo0, InstMap0, MergeSubs0, InstTable, ModuleInfo,
+		InstMap, MergeSubs, Errors) :-
+	instmap__merge_4(Vars, InstMapA, InstMapB, LiveCounts, InstTable0,
+		ModuleInfo0, InstMap0, MergeSubs0, InstTable1, ModuleInfo1,
+		InstMap1, MergeSubs1,  Errors1),
+	instmap__lookup_var(InstMapA, Var, InstA),
+	instmap__lookup_var(InstMapB, Var, InstB),
+	(
+		inst_merge(InstA, InstB, LiveCounts, InstMap1,
+			InstTable1, ModuleInfo1, MergeSubs1, Inst, InstMap2,
+			InstTable2, ModuleInfo2, MergeSubs2)
+	->
+		instmap__set(InstMap2, Var, Inst, InstMap),
+		Errors = Errors1,
+		ModuleInfo = ModuleInfo2,
+		InstTable = InstTable2,
+		MergeSubs = MergeSubs2
 	;
-		ErrorList = ErrorList1,
-		map__set(InstMap1, Var, Inst, InstMap)
+		instmap__set(InstMap1, Var, not_reached, InstMap),
+		Errors = [Var - [InstA, InstB] | Errors1],
+		ModuleInfo = ModuleInfo1,
+		InstTable = InstTable1,
+		MergeSubs = MergeSubs1
 	).
 
-	% instmap_merge_var(InstMaps, Var, ModuleInfo, Insts, Error):
-	%       Let `Insts' be the list of the inst of `Var' in the
-	%       corresponding `InstMaps'.  Let `Error' be yes iff
-	%       there are two instmaps for which the inst of `Var'
-	%       is incompatible.
-
-:- pred instmap__merge_var(list(instmap), prog_var, inst_table, module_info,
-			list(inst), inst, inst_table, module_info, bool).
-:- mode instmap__merge_var(in, in, in, in, out, out, out, out, out) is det.
-
-instmap__merge_var([], _, InstTable, ModuleInfo, [],
-		not_reached, InstTable, ModuleInfo, no).
-instmap__merge_var([InstMap | InstMaps], Var, InstTable0, ModuleInfo0,
-		InstList, Inst, InstTable, ModuleInfo, Error) :-
-	instmap__merge_var(InstMaps, Var, InstTable0, ModuleInfo0,
-		InstList0, Inst0, InstTable1, ModuleInfo1, Error0),
-	instmap__lookup_var(InstMap, Var, VarInst0),
-	inst_table_get_inst_key_table(InstTable1, IKT1),
-	inst_expand_fully(IKT1, InstMap, VarInst0, VarInst),
-	InstList = [VarInst | InstList0],
+:- pred instmap__merge_subs(instmap, instmap, instmap, inst_table, module_info,
+		instmap, instmap, instmap, inst_table).
+:- mode instmap__merge_subs(in, in, in, in, in, out, out, out, out) is det.
+
+instmap__merge_subs(InstMapA0, InstMapB0, InstMap00, InstTable0, ModuleInfo,
+		InstMapA, InstMapB, InstMap0, InstTable) :-
+	(
+		InstMapA0 = reachable(InstMappingA0, SubA0),
+		InstMapB0 = reachable(InstMappingB0, SubB0)
+	->
+		solutions(lambda([K::out] is nondet,
+			(
+				map__member(SubA0, K, V),
+				\+ map__search(SubB0, K, V)
+			;
+				map__member(SubB0, K, V),
+				\+ map__search(SubA0, K, V)
+			)), KeysList),
+		set_bbbtree__sorted_list_to_set(KeysList, Keys),
+		instmap__expand_subs(Keys, ModuleInfo, SubA0, InstMappingA0,
+			InstMappingA, InstTable0, InstTable1),
+		instmap__expand_subs(Keys, ModuleInfo, SubB0, InstMappingB0,
+			InstMappingB, InstTable1, InstTable),
+		map__delete_list(SubA0, KeysList, Sub),
+		InstMapA = reachable(InstMappingA, Sub),
+		InstMapB = reachable(InstMappingB, Sub),
+		( InstMap00 = reachable(InstMapping0, _) ->
+			InstMap0 = reachable(InstMapping0, Sub)
+		;
+			error("instmap__merge_subs: initial instmap unreachable")
+		)
+	;
+		error("instmap__merge_subs: unreachable instmap(s)")
+	).
+
+:- pred instmap__expand_subs(inst_key_set, module_info, inst_key_sub,
+		instmapping, instmapping, inst_table, inst_table).
+:- mode instmap__expand_subs(in, in, in, in, out, in, out) is det.
+
+instmap__expand_subs(Keys, ModuleInfo, Sub, InstMapping0, InstMapping,
+		InstTable0, InstTable) :-
+	map__to_assoc_list(InstMapping0, AL0),
+	map__init(SeenIKs),
+	instmap__expand_subs_2(Keys, ModuleInfo, Sub, SeenIKs, AL0, AL,
+		InstTable0, InstTable),
+	map__from_assoc_list(AL, InstMapping).
+
+:- pred instmap__expand_subs_2(inst_key_set, module_info, inst_key_sub,
+		inst_key_sub, assoc_list(prog_var, inst),
+		assoc_list(prog_var, inst), inst_table, inst_table).
+:- mode instmap__expand_subs_2(in, in, in, in, in, out, in, out) is det.
+
+instmap__expand_subs_2(_, _, _, _, [], [], InstTable, InstTable).
+instmap__expand_subs_2(Keys, ModuleInfo, Sub, SeenIKs0,
+		[Var - Inst0 | VarInsts0], [Var - Inst | VarInsts],
+		InstTable0, InstTable) :-
+	instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		Inst0, Inst, InstTable0, InstTable1),
+	instmap__expand_subs_2(Keys, ModuleInfo, Sub, SeenIKs,
+		VarInsts0, VarInsts, InstTable1, InstTable).
+
+:- pred instmap__expand_inst_sub(inst_key_set, module_info,
+	inst_key_sub, inst_key_sub, inst_key_sub, inst, inst,
+	inst_table, inst_table).
+:- mode instmap__expand_inst_sub(in, in, in, in, out, in, out, in, out) is det.
+
+instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		alias(IK0), Inst, InstTable0, InstTable) :-
+	( map__search(SeenIKs0, IK0, IK1) ->
+		% We have seen IK0 before and replaced it with IK1.
+		Inst = alias(IK1),
+		SeenIKs = SeenIKs0,
+		InstTable = InstTable0
+	; map__search(Sub, IK0, IK1) ->
+		% IK0 has a substitution so recursively expand it.
+		instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+			SeenIKs1, alias(IK1), Inst1, InstTable0, InstTable),
 	(
-		% YYY Not sure about the returned InstMap here.
-		inst_merge(Inst0, VarInst, InstMap, InstTable1, ModuleInfo1,
-			Inst1, _, InstTable2, ModuleInfo2)
+			Inst1 = alias(IK1),
+			\+ set_bbbtree__member(IK0, Keys)
 	->
+			Inst = alias(IK0),
+			map__det_insert(SeenIKs1, IK0, IK0, SeenIKs)
+		;
 		Inst = Inst1,
-		ModuleInfo = ModuleInfo2,
-		Error = Error0,
-		InstTable = InstTable2
+			( Inst = alias(IK2) ->
+				map__det_insert(SeenIKs1, IK0, IK2, SeenIKs)
 	;
-		Error = yes,
-		ModuleInfo = ModuleInfo1,
-		Inst = not_reached,
-		InstTable = InstTable1
+				error("instmap__expand_inst_sub")
+			)
+		)
+	;
+		inst_table_get_inst_key_table(InstTable0, IKT0),
+		inst_key_table_lookup(IKT0, IK0, Inst0),
+		instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+			SeenIKs1, Inst0, Inst1, InstTable0, InstTable1),
+		( Inst0 = Inst1 ->
+			Inst = alias(IK0),
+			InstTable = InstTable1,
+			map__det_insert(SeenIKs1, IK0, IK0, SeenIKs)
+		;
+			% Inst has changed so we need to create a new inst_key.
+			inst_table_get_inst_key_table(InstTable1, IKT1),
+			inst_key_table_add(IKT1, Inst1, IK1, IKT),
+			inst_table_set_inst_key_table(InstTable1, IKT,
+				InstTable),
+			map__det_insert(SeenIKs1, IK0, IK1, SeenIKs),
+			Inst = alias(IK1)
+		)
+	).
+instmap__expand_inst_sub(_, _, _, SeenIKs, SeenIKs, any(U), any(U),
+		InstTable, InstTable).
+instmap__expand_inst_sub(_, _, _, SeenIKs, SeenIKs, free(A), free(A),
+		InstTable, InstTable).
+instmap__expand_inst_sub(_, _, _, SeenIKs, SeenIKs, free(A, T),
+		free(A, T), InstTable, InstTable).
+instmap__expand_inst_sub(_, _, _, SeenIKs, SeenIKs, ground(U, P),
+		ground(U, P), InstTable, InstTable).
+instmap__expand_inst_sub(_, _, _, SeenIKs, SeenIKs, not_reached,
+		not_reached, InstTable, InstTable).
+instmap__expand_inst_sub(_, _, _, _, _, inst_var(_), _, _, _) :-
+	error("instmap__expand_inst_sub: inst_var(_)").
+instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		bound(U, BoundInsts0), bound(U, BoundInsts),
+		InstTable0, InstTable) :-
+	instmap__expand_bound_insts_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+		SeenIKs, BoundInsts0, BoundInsts, InstTable0, InstTable).
+instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		abstract_inst(N, Insts0), abstract_inst(N, Insts),
+		InstTable0, InstTable) :-
+	instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		Insts0, Insts, InstTable0, InstTable).
+instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		defined_inst(InstName), Inst, InstTable0, InstTable) :-
+	inst_table_get_substitution_insts(InstTable0, SubInsts0),
+	SubInst = substitution_inst(InstName, Keys, Sub),
+	SubInstName = substitution_inst(InstName, Keys, Sub),
+	(
+		map__search(SubInsts0, SubInst, Result)
+	->
+		( Result = known(Inst0) ->
+			Inst2 = Inst0
+		;
+			Inst2 = defined_inst(SubInstName)
+		),
+		SeenIKs = SeenIKs0,
+		InstTable = InstTable0
+	;
+		% Insert the inst_name in the substitution_inst_table with
+		% value `unknown' for the moment.
+		map__det_insert(SubInsts0, SubInst, unknown, SubInsts1),
+		inst_table_set_substitution_insts(InstTable0, SubInsts1,
+			InstTable1),
+
+		% Recursively expand the inst.
+		inst_lookup(InstTable1, ModuleInfo, InstName, Inst0),
+		inst_expand_defined_inst(InstTable1, ModuleInfo, Inst0, Inst1),
+		instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+			SeenIKs, Inst1, Inst2, InstTable1, InstTable2),
+
+		% Update the substitution_inst_table with the known value.
+		inst_table_get_substitution_insts(InstTable2, SubInsts2),
+		map__det_update(SubInsts2, SubInst, known(Inst2), SubInsts),
+		inst_table_set_substitution_insts(InstTable2, SubInsts,
+			InstTable)
+	),
+		% Avoid expanding recursive insts.
+	map__init(InstMapping),
+	(
+			% InstMapping is not used by inst_contains_instname.
+		inst_contains_instname(Inst2, reachable(InstMapping, Sub),
+			InstTable, ModuleInfo, InstName)
+	->
+		Inst = defined_inst(InstName)
+	;
+			% InstMapping is not used by inst_contains_instname.
+		inst_contains_instname(Inst2, reachable(InstMapping, Sub),
+			InstTable, ModuleInfo, SubInstName)
+	->
+		Inst = defined_inst(SubInstName)
+	;
+		Inst = Inst2
+	).
+
+:- pred instmap__expand_bound_insts_sub(inst_key_set, module_info,
+	inst_key_sub, inst_key_sub, inst_key_sub, list(bound_inst),
+	list(bound_inst), inst_table, inst_table).
+:- mode instmap__expand_bound_insts_sub(in, in, in, in, out, in, out, in, out)
+	is det.
+
+instmap__expand_bound_insts_sub(_, _, _, SeenIKs, SeenIKs, [], [],
+		InstTable, InstTable).
+instmap__expand_bound_insts_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+		[functor(ConsId, Insts0) | BoundInsts0],
+		[functor(ConsId, Insts) | BoundInsts], InstTable0, InstTable) :-
+	instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub,
+		SeenIKs0, SeenIKs1, Insts0, Insts, InstTable0, InstTable1),
+	instmap__expand_bound_insts_sub(Keys, ModuleInfo, Sub,
+		SeenIKs1, SeenIKs, BoundInsts0, BoundInsts,
+		InstTable1, InstTable).
+
+:- pred instmap__expand_inst_list_sub(inst_key_set, module_info,
+	inst_key_sub, inst_key_sub, inst_key_sub, list(inst), list(inst),
+	inst_table, inst_table).
+:- mode instmap__expand_inst_list_sub(in, in, in, in, out, in, out, in, out)
+	is det.
+
+instmap__expand_inst_list_sub(_, _, _, SeenIKs, SeenIKs, [], [],
+		InstTable, InstTable).
+instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub,
+		SeenIKs0, SeenIKs, [Inst0 | Insts0], [Inst | Insts],
+		InstTable0, InstTable) :-
+	instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+		SeenIKs1, Inst0, Inst, InstTable0, InstTable1),
+	instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub,
+		SeenIKs1, SeenIKs, Insts0, Insts, InstTable1, InstTable).
+
+%-----------------------------------------------------------------------------%
+
+:- pred instmap__remove_singleton_inst_keys(list(prog_var), module_info,
+	inst_table, instmap, instmap).
+:- mode instmap__remove_singleton_inst_keys(in, in, in, in, out) is det.
+
+instmap__remove_singleton_inst_keys(Vars, ModuleInfo, InstTable, InstMap0,
+		InstMap) :-
+	instmap__count_inst_keys(Vars, ModuleInfo, InstTable, InstMap0,
+		IKCounts),
+	list__foldl(instmap__remove_singleton_inst_keys_2(IKCounts, ModuleInfo,
+		InstTable), Vars, InstMap0, InstMap).
+
+:- pred instmap__remove_singleton_inst_keys_2(inst_key_counts,
+	module_info, inst_table, prog_var, instmap, instmap).
+:- mode instmap__remove_singleton_inst_keys_2(in, in, in, in, in, out) is det.
+
+instmap__remove_singleton_inst_keys_2(IKCounts, ModuleInfo, InstTable, Var,
+		InstMap0, InstMap) :-
+	instmap__lookup_var(InstMap0, Var, Inst0),
+	instmap__remove_singleton_inst_key_from_inst(IKCounts, ModuleInfo,
+		InstTable, InstMap0, Inst0, Inst),
+	instmap__set(InstMap0, Var, Inst, InstMap).
+
+:- pred instmap__remove_singleton_inst_key_from_inst(inst_key_counts,
+	module_info, inst_table, instmap, inst, inst).
+:- mode instmap__remove_singleton_inst_key_from_inst(in, in, in, in, in, out)
+	is det.
+
+instmap__remove_singleton_inst_key_from_inst(IKCounts, ModuleInfo, InstTable,
+		InstMap, alias(IK), Inst) :-
+	( has_count_one(IKCounts, IK) ->
+		inst_table_get_inst_key_table(InstTable, IKT),
+		instmap__inst_key_table_lookup(InstMap, IKT, IK, Inst1),
+		instmap__remove_singleton_inst_key_from_inst(IKCounts,
+			ModuleInfo, InstTable, InstMap, Inst1, Inst)
+	;
+		Inst = alias(IK)
 	).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _, any(U), any(U)).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _, free(A), free(A)).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _,
+		free(A, T), free(A, T)).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _,
+		ground(U, P), ground(U, P)).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _,
+		not_reached, not_reached).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _,
+		defined_inst(N), defined_inst(N)).
+instmap__remove_singleton_inst_key_from_inst(_, _, _, _, inst_var(_), _) :-
+	error("instmap__remove_singleton_inst_key_from_inst: inst_var").
+instmap__remove_singleton_inst_key_from_inst(IKCounts, ModuleInfo, InstTable,
+		InstMap, bound(U, BoundInsts0), bound(U, BoundInsts)) :-
+	list__map(lambda([BI0::in, BI::out] is det, (
+		BI0 = functor(C, Insts0),
+		list__map(instmap__remove_singleton_inst_key_from_inst(IKCounts,
+				ModuleInfo, InstTable, InstMap),
+			Insts0, Insts),
+		BI = functor(C, Insts)
+		)), BoundInsts0, BoundInsts).
+instmap__remove_singleton_inst_key_from_inst(IKCounts, ModuleInfo, InstTable,
+		InstMap, abstract_inst(N, Insts0), abstract_inst(N, Insts)) :-
+	list__map(instmap__remove_singleton_inst_key_from_inst(IKCounts,
+			ModuleInfo, InstTable, InstMap),
+		Insts0, Insts).
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -951,66 +1328,6 @@
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
-:- pred merge_instmapping_delta(instmap, set(prog_var), instmapping,
-		instmapping, instmapping, inst_table, inst_table,
-		module_info, module_info).
-:- mode merge_instmapping_delta(in, in, in, in, out, in, out, in, out) is det.
-
-merge_instmapping_delta(InstMap, NonLocals, InstMappingA,
-		InstMappingB, InstMapping, InstTable0, InstTable) -->
-	{ map__keys(InstMappingA, VarsInA) },
-	{ map__keys(InstMappingB, VarsInB) },
-	{ set__sorted_list_to_set(VarsInA, SetofVarsInA) },
-	{ set__insert_list(SetofVarsInA, VarsInB, SetofVars0) },
-	{ set__intersect(SetofVars0, NonLocals, SetofVars) },
-	{ map__init(InstMapping0) },
-	{ set__to_sorted_list(SetofVars, ListofVars) },
-	merge_instmapping_delta_2(ListofVars, InstMap, InstMappingA,
-		InstMappingB, InstMapping0, InstMapping, InstTable0, InstTable).
-
-:- pred merge_instmapping_delta_2(list(prog_var), instmap, instmapping,
-		instmapping, instmapping, instmapping, inst_table, inst_table,
-		module_info, module_info).
-:- mode merge_instmapping_delta_2(in, in, in, in, in, out, in, out, in, out)
-		is det.
-
-merge_instmapping_delta_2([], _, _, _, InstMapping, InstMapping,
-			InstTable, InstTable, ModInfo, ModInfo).
-merge_instmapping_delta_2([Var | Vars], InstMap, InstMappingA, InstMappingB,
-			InstMapping0, InstMapping, InstTable0, InstTable,
-			ModuleInfo0, ModuleInfo) :-
-	( map__search(InstMappingA, Var, InstInA) ->
-		InstA = InstInA
-	;
-		instmap__lookup_var(InstMap, Var, InstA)
-	),
-	( map__search(InstMappingB, Var, InstInB) ->
-		InstB = InstInB
-	;
-		instmap__lookup_var(InstMap, Var, InstB)
-	),
-	(
-		% YYY Not sure about the returned InstMap here.
-		inst_merge(InstA, InstB, InstMap, InstTable0, ModuleInfo0,
-			Inst, _, InstTable1, ModuleInfo1)
-	->
-		ModuleInfo2 = ModuleInfo1,
-		InstTable2 = InstTable1,
-		map__det_insert(InstMapping0, Var, Inst, InstMapping1)
-	;
-		term__var_to_int(Var, VarInt),
-		string__format(
-			"merge_instmapping_delta_2: error merging var %i",
-			[i(VarInt)], Msg),
-		error(Msg)
-	),
-	merge_instmapping_delta_2(Vars, InstMap, InstMappingA, InstMappingB,
-		InstMapping1, InstMapping, InstTable2, InstTable,
-		ModuleInfo2, ModuleInfo).
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-
 instmap__bind_var_to_functor(Var, ConsId, InstMap0, InstMap,
 		InstTable0, InstTable, ModuleInfo0, ModuleInfo) :-
 	instmap__lookup_var(InstMap0, Var, Inst0),
@@ -1120,6 +1437,18 @@
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
+instmap__inst_keys_are_equivalent(KeyA, InstMapA, KeyB, InstMapB) :-
+	(
+		KeyA = KeyB
+	;
+		InstMapA = reachable(_, AliasMapA),
+		InstMapB = reachable(_, AliasMapB),
+		find_latest_inst_key(AliasMapA, KeyA, Key),
+		find_latest_inst_key(AliasMapB, KeyB, Key)
+	).
+
+%-----------------------------------------------------------------------------%
+
 instmap__get_inst_key_sub(unreachable, Sub) :-
 	map__init(Sub).
 instmap__get_inst_key_sub(reachable(_, Sub), Sub).
Index: mercury_to_mercury.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_to_mercury.m,v
retrieving revision 1.115.2.22
diff -u -w -r1.115.2.22 mercury_to_mercury.m
--- 1.115.2.22	1998/11/24 06:29:44
+++ mercury_to_mercury.m	1998/12/15 03:17:22
@@ -959,6 +959,15 @@
 		InstMap, InstTable),
 	mercury_output_tabs(Indent),
 	io__write_string(")\n").
+mercury_output_structured_inst_name(Expand, substitution_inst(InstName, _, _),
+		Indent, VarSet, InstMap, InstTable) -->
+	mercury_output_tabs(Indent),
+	io__write_string("$substitution_inst(\n"),
+	{ Indent1 is Indent + 1 },
+	mercury_output_structured_inst_name(Expand, InstName, Indent1, VarSet,
+		InstMap, InstTable),
+	mercury_output_tabs(Indent),
+	io__write_string(")\n").
 
 :- pred mercury_output_inst_name(inst_name, inst_varset, inst_table,
 		io__state, io__state).
@@ -1051,6 +1060,11 @@
 	io__write_string(", "),
 	mercury_output_inst_name(InstName, VarSet, InstTable),
 	io__write_string(")").
+mercury_output_inst_name(substitution_inst(InstName, _, _), VarSet,
+		InstTable) -->
+	io__write_string("$substitution_inst("),
+	mercury_output_inst_name(InstName, VarSet, InstTable),
+	io__write_string(")").
 
 :- pred mercury_output_uniqueness(uniqueness, string, io__state, io__state).
 :- mode mercury_output_uniqueness(in, in, di, uo) is det.
Index: mode_info.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mode_info.m,v
retrieving revision 1.39.4.13
diff -u -w -r1.39.4.13 mode_info.m
--- 1.39.4.13	1998/11/24 06:29:57
+++ mode_info.m	1998/12/07 00:00:32
@@ -285,10 +285,11 @@
 				).
 */
 :- inst uniq_mode_info	=	ground.
+:- inst dead_mode_info  =	ground.
 
 :- mode mode_info_uo :: free -> uniq_mode_info.
 :- mode mode_info_ui :: uniq_mode_info -> uniq_mode_info.
-:- mode mode_info_di :: uniq_mode_info -> dead.
+:- mode mode_info_di :: uniq_mode_info -> dead_mode_info.
 
 	% Some fiddly modes used when we want to extract
 	% the io_state from a mode_info struct and then put it back again.
@@ -307,7 +308,7 @@
 
 :- mode mode_info_get_io_state	:: uniq_mode_info -> mode_info_no_io.
 :- mode mode_info_no_io		:: mode_info_no_io -> mode_info_no_io.
-:- mode mode_info_set_io_state	:: mode_info_no_io -> dead.
+:- mode mode_info_set_io_state	:: mode_info_no_io -> dead_mode_info.
 
 %-----------------------------------------------------------------------------%
 
Index: mode_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mode_util.m,v
retrieving revision 1.99.2.26
diff -u -w -r1.99.2.26 mode_util.m
--- 1.99.2.26	1998/11/24 06:30:01
+++ mode_util.m	1999/01/14 01:30:02
@@ -572,6 +572,15 @@
 		map__init(Subst),
 		propagate_type_into_inst(Type, Subst, InstTable, ModuleInfo,
 			Inst0, Inst)
+	; InstName = substitution_inst(SubInstName, SubKeys, Sub),
+		inst_table_get_substitution_insts(InstTable, SubInsts),
+		map__lookup(SubInsts, substitution_inst(SubInstName, SubKeys,
+			Sub), MaybeInst),
+		( MaybeInst = known(Inst0) ->
+			Inst = Inst0
+		;
+			Inst = defined_inst(InstName)
+		)
 	),
 	!.
 
@@ -1209,6 +1218,9 @@
 		typed_inst(T, Inst)) :-
 	inst_name_apply_substitution(Inst0, Subst, Inst).
 inst_name_apply_substitution(typed_ground(Uniq, T), _, typed_ground(Uniq, T)).
+inst_name_apply_substitution(substitution_inst(InstName0, K, S), Subst,
+		substitution_inst(InstName, K, S)) :-
+	inst_name_apply_substitution(InstName0, Subst, InstName).
 
 :- pred alt_list_apply_substitution(list(bound_inst), inst_subst,
 				list(bound_inst)).
@@ -1354,6 +1366,13 @@
 		recompute_info(A, B, C, D, yes)).
 
 
+:- pred recompute_info_get_live_vars_list(recompute_info, list(prog_var)).
+:- mode recompute_info_get_live_vars_list(in, out) is det.
+
+recompute_info_get_live_vars_list(RI, LiveVarsList) :-
+	recompute_info_get_live_vars(RI, LiveVarsBag),
+	bag__to_list_without_duplicates(LiveVarsBag, LiveVarsList).
+
 :- pred recompute_info_add_live_vars(set(prog_var), recompute_info,
 		recompute_info).
 :- mode recompute_info_add_live_vars(in, in, out) is det.
@@ -1567,7 +1586,8 @@
 		=(RI4),
 		{ recompute_info_get_module_info(RI4, M4) },
 		{ recompute_info_get_inst_table(RI4, InstTable4) },
-		{ instmap__merge(NonLocals, [InstMap2, InstMap3],
+		{ recompute_info_get_live_vars_list(RI4, Liveness) },
+		{ instmap__merge(NonLocals, Liveness, [InstMap2, InstMap3],
 			InstMap0, InstMapAfter, M4, InstTable4, M, InstTable,
 			Errors) },
 		{ Errors = [] ->
@@ -1682,9 +1702,10 @@
 	=(RI2),
 	{ recompute_info_get_module_info(RI2, M2) },
 	{ recompute_info_get_inst_table(RI2, InstTable2) },
-	{ instmap__merge(NonLocals, [InstMapBranches, InstMapThisBranch],
-		InstMap0, InstMapAfter, M2, InstTable2, M, InstTable,
-		Errors) },
+	{ recompute_info_get_live_vars_list(RI2, Liveness) },
+	{ instmap__merge(NonLocals, Liveness, 
+		[InstMapBranches, InstMapThisBranch], InstMap0, InstMapAfter,
+		M2, InstTable2, M, InstTable, Errors) },
 	{ Errors = [] ->
 		InstMap = InstMapAfter
 	;
@@ -1719,9 +1740,10 @@
 	=(RI4),
 	{ recompute_info_get_module_info(RI4, M4) },
 	{ recompute_info_get_inst_table(RI4, InstTable4) },
-	{ instmap__merge(NonLocals, [InstMapBranches, InstMapThisBranch],
-		InstMap0, InstMapAfter, M4, InstTable4, M, InstTable,
-		Errors) },
+	{ recompute_info_get_live_vars_list(RI4, Liveness) },
+	{ instmap__merge(NonLocals, Liveness,
+		[InstMapBranches, InstMapThisBranch], InstMap0, InstMapAfter,
+		M4, InstTable4, M, InstTable, Errors) },
 	{ Errors = [] ->
 		InstMap = InstMapAfter
 	;
Index: module_qual.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/module_qual.m,v
retrieving revision 1.22.2.14
diff -u -w -r1.22.2.14 module_qual.m
--- 1.22.2.14	1998/11/24 06:30:22
+++ module_qual.m	1998/12/15 02:23:54
@@ -581,6 +581,8 @@
 	{ error("compiler generated inst unexpected") }.
 qualify_inst_name(typed_inst(_, _), _, _, _) -->
 	{ error("compiler generated inst unexpected") }.
+qualify_inst_name(substitution_inst(_, _, _), _, _, _) -->
+	{ error("compiler generated inst unexpected") }.
 
 	% Qualify an inst of the form bound(functor(...)).
 :- pred qualify_bound_inst_list(list(bound_inst)::in, list(bound_inst)::out,
Index: prog_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/prog_data.m,v
retrieving revision 1.24.2.15
diff -u -w -r1.24.2.15 prog_data.m
--- 1.24.2.15	1998/11/24 06:31:07
+++ prog_data.m	1998/12/22 04:01:13
@@ -523,7 +523,8 @@
 	;	shared_inst(inst_name)
 	;	mostly_uniq_inst(inst_name)
 	;	typed_ground(uniqueness, type)
-	;	typed_inst(type, inst_name).
+	;	typed_inst(type, inst_name)
+	;	substitution_inst(inst_name, inst_key_set, inst_key_sub).
 
 	% Note: `is_live' records liveness in the sense used by
 	% mode analysis.  This is not the same thing as the notion of liveness
Index: simplify.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/simplify.m,v
retrieving revision 1.46.2.20
diff -u -w -r1.46.2.20 simplify.m
--- 1.46.2.20	1998/11/24 06:31:40
+++ simplify.m	1999/01/19 04:56:09
@@ -225,8 +225,13 @@
 			Goal2, VarSet, VarTypes, _),
 
 		simplify_info_set_varset(Info1, VarSet, Info2),
-		simplify_info_set_var_types(Info2, VarTypes, Info3),
-
+		simplify_info_set_var_types(Info2, VarTypes, Info3)
+	;
+		Goal2 = Goal1,
+		Info3 = Info1,
+		VarTypes = VarTypes0
+	),
+	( simplify_info_recompute_instmap_delta(Info3) ->
 		simplify_info_get_module_info(Info3, ModuleInfo3),
 		simplify_info_get_inst_table(Info3, InstTable0),
 		simplify_info_get_det_info(Info3, DetInfo0),
@@ -239,8 +244,8 @@
 		simplify_info_set_module_info(Info3, ModuleInfo4, Info4),
 		simplify_info_set_inst_table(Info4, InstTable, Info5)
 	;
-		Goal3 = Goal1,
-		Info5 = Info1
+		Goal3 = Goal2,
+		Info5 = Info3
 	),
 	( simplify_info_rerun_det(Info5) ->
 		Goal0 = _ - GoalInfo0,
@@ -338,7 +343,8 @@
 		( set__empty(NonLocals0) ->
 			Info1 = Info0
 		;
-			simplify_info_set_requantify(Info0, Info1)
+			simplify_info_set_requantify(Info0, Info0a),
+			simplify_info_set_recompute_instmap_delta(Info0a, Info1)
 		),
 		pd_cost__goal(Goal0, CostDelta),
 		simplify_info_incr_cost_delta(Info1, CostDelta, Info2),
@@ -382,7 +388,8 @@
 		( set__empty(NonLocals0) ->
 			Info1 = Info0
 		;
-			simplify_info_set_requantify(Info0, Info1)
+			simplify_info_set_requantify(Info0, Info0a),
+			simplify_info_set_recompute_instmap_delta(Info0a, Info1)
 		),
 		pd_cost__goal(Goal0, CostDelta),
 		simplify_info_incr_cost_delta(Info1, CostDelta, Info2),
@@ -499,8 +506,7 @@
 
 simplify__goal_2(disj(Disjuncts0, SM), GoalInfo0,
 		Goal, GoalInfo, Info0, Info) :-
-	simplify_info_get_instmap(Info0, InstMap0),
-	simplify__disj(Disjuncts0, [], Disjuncts, [], InstMaps,
+	simplify__disj(Disjuncts0, [], Disjuncts, [], _InstMaps,
 			Info0, Info0, Info1),
 	( Disjuncts = [] ->
 		goal_info_get_context(GoalInfo0, Context),
@@ -538,25 +544,8 @@
 		;
 	****/
 			Goal = disj(Disjuncts, SM),
-			simplify_info_get_module_info(Info1, ModuleInfo1),
-			simplify_info_get_inst_table(Info1, InstTable1),
-			goal_info_get_nonlocals(GoalInfo0, NonLocals),
-
-			instmap__merge(NonLocals, InstMaps, InstMap0,
-				NewInstMap, ModuleInfo1, InstTable1,
-				ModuleInfo2, InstTable2, MergeErrors),
-			( MergeErrors \= [] ->
-				error("simplify: merge error in disj")
-			;
-				compute_instmap_delta(InstMap0, NewInstMap,
-					NewDelta)
-			),
-
-			simplify_info_set_module_info(Info1, ModuleInfo2,
-				Info2),
-			simplify_info_set_inst_table(Info2, InstTable2, Info),
-			goal_info_set_instmap_delta(GoalInfo0, NewDelta,
-				GoalInfo)
+			simplify_info_set_recompute_instmap_delta(Info1, Info),
+			GoalInfo = GoalInfo0
 		)
 	).
 
@@ -578,7 +567,7 @@
 		Cases1 = Cases0,
 		MaybeConsIds = no
 	),
-	simplify__switch(Var, Cases1, [], Cases, [], InstMaps, 
+	simplify__switch(Var, Cases1, [], Cases, [], _InstMaps, 
 		SwitchCanFail0, SwitchCanFail, Info0, Info0, Info1),
 	( Cases = [] ->
 		% An empty switch always fails.
@@ -613,7 +602,9 @@
 			goal_info_init(NonLocals, InstMapDelta, Detism, 
 				CombinedGoalInfo),
 
-			simplify_info_set_requantify(Info2, Info3),
+			simplify_info_set_requantify(Info2, Info2a),
+			simplify_info_set_recompute_instmap_delta(Info2a,
+				Info3),
 			Goal = conj(GoalList),
 			GoalInfo = CombinedGoalInfo
 		;
@@ -626,23 +617,8 @@
 		simplify_info_incr_cost_delta(Info3, CostDelta, Info)
 	;
 		Goal = switch(Var, SwitchCanFail, Cases, SM),
-		simplify_info_get_module_info(Info1, ModuleInfo1),
-		simplify_info_get_inst_table(Info1, InstTable1),
-		goal_info_get_nonlocals(GoalInfo0, NonLocals),
-
-		instmap__merge(NonLocals, InstMaps, InstMap0, NewInstMap,
-			ModuleInfo1, InstTable1, ModuleInfo2, InstTable2,
-			MergeErrors),
-		( MergeErrors \= [] ->
-			error("simplify: merge error in switch")
-		;
-			compute_instmap_delta(InstMap0, NewInstMap, NewDelta)
-		),
-
-		simplify_info_set_module_info(Info1, ModuleInfo2, Info2),
-		simplify_info_set_inst_table(Info2, InstTable2, Info3),
-		simplify_info_set_instmap(Info3, NewInstMap, Info),
-		goal_info_set_instmap_delta(GoalInfo0, NewDelta, GoalInfo)
+		simplify_info_set_recompute_instmap_delta(Info1, Info),
+		GoalInfo = GoalInfo0
 	).
 
 simplify__goal_2(Goal0, GoalInfo, Goal, GoalInfo, Info0, Info) :-
@@ -792,8 +768,10 @@
 		->
 			Goal = Goal2,
 			GoalInfo = GoalInfo2,
-			simplify_info_set_module_info(Info3, ModuleInfo3, Info4),
-			simplify_info_set_requantify(Info4, Info)
+			simplify_info_set_module_info(Info3, ModuleInfo3,
+				Info4),
+			simplify_info_set_requantify(Info4, Info5),
+			simplify_info_set_recompute_instmap_delta(Info5, Info)
 		;
 			Goal = Goal1,
 			GoalInfo = GoalInfo0,
@@ -941,32 +919,15 @@
 		simplify__goal(conj(List) - GoalInfo0, Goal - GoalInfo,
 			Info0, Info)
 	;
-		simplify_info_get_instmap(Info0, InstMap0),
 		simplify__goal(Cond0, Cond, Info0, Info1),
 		simplify_info_update_instmap(Info1, Cond, Info2),
 		simplify__goal(Then0, Then, Info2, Info3),
-		simplify_info_get_instmap(Info3, CondThenMap),
 		simplify_info_post_branch_update(Info0, Info3, Info4),
 		simplify__goal(Else0, Else, Info4, Info5),
-		simplify_info_get_instmap(Info5, ElseMap),
 		simplify_info_post_branch_update(Info0, Info5, Info6),
 
-		goal_info_get_nonlocals(GoalInfo0, NonLocals),
-		simplify_info_get_module_info(Info6, ModuleInfo0),
-		simplify_info_get_inst_table(Info6, InstTable0),
-
-		instmap__merge(NonLocals, [CondThenMap, ElseMap], InstMap0,
-			NewInstMap, ModuleInfo0, InstTable0, ModuleInfo1,
-			InstTable1, MergeErrors),
-		( MergeErrors \= [] ->
-			error("simplify: merge error in ite")
-		;
-			compute_instmap_delta(InstMap0, NewInstMap, NewDelta)
-		),
-
-		simplify_info_set_inst_table(Info6, InstTable1, Info7),
-		simplify_info_set_module_info(Info7, ModuleInfo1, Info),
-		goal_info_set_instmap_delta(GoalInfo0, NewDelta, GoalInfo1),
+		simplify_info_set_recompute_instmap_delta(Info6, Info),
+
 		IfThenElse = if_then_else(Vars, Cond, Then, Else, SM),
 		%
 		% If-then-elses that are det or semidet may nevertheless
@@ -986,13 +947,13 @@
 		->
 			determinism_components(InnerDetism, IfThenElseCanFail,
 				at_most_many),
-			goal_info_set_determinism(GoalInfo1, InnerDetism,
+			goal_info_set_determinism(GoalInfo0, InnerDetism,
 				InnerInfo),
 			Goal = some([], IfThenElse - InnerInfo)
 		;
 			Goal = IfThenElse
 		),
-		GoalInfo = GoalInfo1
+		GoalInfo = GoalInfo0
 	).
 
 simplify__goal_2(not(Goal0), GoalInfo0, Goal, GoalInfo, Info0, Info) :-
@@ -1583,7 +1544,7 @@
 			map(prog_var, type),
 			bool,		% Does the goal need requantification.
 			bool,		% Do we need to recompute
-					% instmap_deltas for atomic goals
+					% instmap_deltas
 			bool,		% Does determinism analysis need to
 					% be rerun.
 			int,		% Measure of the improvement in
@@ -1632,7 +1593,7 @@
 :- pred simplify_info_get_var_types(simplify_info::in,
 		map(prog_var, type)::out) is det.
 :- pred simplify_info_requantify(simplify_info::in) is semidet.
-:- pred simplify_info_recompute_atomic(simplify_info::in) is semidet.
+:- pred simplify_info_recompute_instmap_delta(simplify_info::in) is semidet.
 :- pred simplify_info_rerun_det(simplify_info::in) is semidet.
 :- pred simplify_info_get_cost_delta(simplify_info::in, int::out) is det.
 
@@ -1656,7 +1617,8 @@
 simplify_info_get_var_types(simplify_info(_,_,_,_,_,_, VarTypes, _,_,_,_,_,_),
 	VarTypes). 
 simplify_info_requantify(simplify_info(_,_,_,_,_,_,_, yes, _,_,_,_,_)).
-simplify_info_recompute_atomic(simplify_info(_,_,_,_,_,_,_,_, yes,_,_,_,_)).
+simplify_info_recompute_instmap_delta(
+		simplify_info(_,_,_,_,_,_,_,_, yes,_,_,_,_)).
 simplify_info_rerun_det(simplify_info(_,_,_,_,_,_,_,_,_, yes,_,_,_)).
 simplify_info_get_cost_delta(simplify_info(_,_,_,_,_,_,_,_,_,_,CostDelta, _,_),
 	CostDelta).
@@ -1687,7 +1649,7 @@
 		simplify_info::out) is det.
 :- pred simplify_info_set_requantify(simplify_info::in,
 		simplify_info::out) is det.
-:- pred simplify_info_set_rerun_simplify(simplify_info::in,
+:- pred simplify_info_set_recompute_instmap_delta(simplify_info::in,
 		simplify_info::out) is det.
 :- pred simplify_info_set_rerun_det(simplify_info::in,
 		simplify_info::out) is det.
@@ -1740,7 +1702,7 @@
 simplify_info_set_requantify(
 		simplify_info(A, B, C, D, E, F, G, _, I, J, K, L, M),
 		simplify_info(A, B, C, D, E, F, G, yes, I, J, K, L, M)). 
-simplify_info_set_rerun_simplify(
+simplify_info_set_recompute_instmap_delta(
 		simplify_info(A, B, C, D, E, F, G,H,_,J,K,L, M),
 		simplify_info(A, B, C, D, E, F, G, H, yes, J, K, L, M)). 
 simplify_info_set_rerun_det(

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



More information about the developers mailing list