[m-dev.] for review: retain aliasing information when merging instmaps of branched goals
David Overton
dmo at cs.mu.OZ.AU
Fri Feb 19 14:46:43 AEDT 1999
On Thu, Feb 11, 1999 at 04:06:33AM EST, Fergus Henderson wrote:
>
> That description should be included in a comment in the source code.
[...]
>
> Some comments here about what these types are supposed to represent
> would be helpful. In particular, what is the meaning of the
> threefields of a substitution_inst?
>
[...]
>
> It might be better to add an extra bool parameter
> (or make it a function returning bool), so ensure that
> next time we add a new alternative to the `inst' type, we
> will get a compile error if we forget to add new clauses
> to this predicate.
>
> Apart from that, I didn't spot anything obviously wrong in your code,
> but I didn't look at it in great detail.
>
The relative diff below addresses Fergus's comments and also merges
insts of dead variables correctly so that structure re-use knows which
dead variables have been clobbered.
The way this works is: if inst_merge finds an alias on a dead variable
it will remove the alias. If there are other references to this alias
then it will clobber the inst.
----
Estimated hours taken: 70 (+ 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:
1. Remove unreachable instmaps.
2. Take the first two instmaps and remove singleton inst_keys
from each.
3. Expand any inst_key substitutions that occur in one instmap
but not the other (done by `instmap__merge_subs').
4. Call `inst_merge' for each non-local variable.
5. Work out which inst_keys need to become shared and make
them shared (uses information collected by `inst_merge').
6. Recursively merge the resulting instmap with the instmap
from the next branch (go back to step 2).
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.
Add a new bool output to `make_shared_inst' which is bound to `no'
if a partially-instantiated or free inst is found rather than aborting.
Ensure that `make_shared_inst' does not remove `alias' insts.
Add a predicate `make_clobbered_inst' which clobbers an inst.
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 two new tables within the inst_table:
1. the substitution_inst_table, for insts created when
expanding inst_key substitutions
2. the clobbered_inst_table for inst created when clobbering
other insts.
Add an extra field of type `is_live' to merge_insts. This is because
the result of inst_merge now depends on the liveness of the variable.
compiler/mercury_to_mercury.m:
compiler/mode_util.m:
compiler/module_qual.m:
Changes related to addition of the substitution_inst_table,
and clobbered_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'.
----
--- hlds_data.m.bak2 Mon Feb 1 12:51:00 1999
+++ hlds_data.m Thu Feb 18 16:20:30 1999
@@ -357,8 +357,10 @@
:- type unify_inst_pair ---> unify_inst_pair(is_live, inst, inst,
unify_is_real).
-:- type merge_inst_table == map(pair(inst), maybe_inst).
+:- type merge_inst_table == map(merge_inst_pair, maybe_inst).
+:- type merge_inst_pair ---> merge_inst_pair(is_live, inst, inst).
+
:- type ground_inst_table == map(inst_name, maybe_inst_det).
:- type any_inst_table == map(inst_name, maybe_inst_det).
@@ -369,8 +371,16 @@
:- type substitution_inst_table == map(substitution_inst, maybe_inst).
+:- type clobbered_inst_table == map(inst_name, maybe_inst).
+
:- type substitution_inst
- ---> substitution_inst(inst_name, inst_key_set, inst_key_sub).
+ ---> substitution_inst(
+ inst_name,
+ inst_key_set, % The set of inst_keys that have
+ % had their substitutions expanced.
+ inst_key_sub % The substitution map used to expand
+ % the substitutions.
+ ).
:- type inst_key_set == set_bbbtree(inst_key).
@@ -417,15 +427,16 @@
:- 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, out)
- is det.
+ shared_inst_table, mostly_uniq_inst_table, clobbered_inst_table,
+ inst_key_table).
+:- mode inst_table_get_all_tables(in, out, out, out, out, out, out, out,
+ out, out) is det.
:- 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, in, out)
+ shared_inst_table, mostly_uniq_inst_table, clobbered_inst_table,
+ inst_key_table, inst_table).
+:- mode inst_table_set_all_tables(in, in, in, in, in, in, in, in, in, in, out)
is det.
:- pred inst_table_get_substitution_insts(inst_table, substitution_inst_table).
@@ -449,6 +460,9 @@
:- pred inst_table_get_mostly_uniq_insts(inst_table, mostly_uniq_inst_table).
:- mode inst_table_get_mostly_uniq_insts(in, out) is det.
+:- pred inst_table_get_clobbered_insts(inst_table, clobbered_inst_table).
+:- mode inst_table_get_clobbered_insts(in, out) is det.
+
:- pred inst_table_get_inst_key_table(inst_table, inst_key_table).
:- mode inst_table_get_inst_key_table(in, out) is det.
@@ -475,6 +489,10 @@
inst_table).
:- mode inst_table_set_mostly_uniq_insts(in, in, out) is det.
+:- pred inst_table_set_clobbered_insts(inst_table, clobbered_inst_table,
+ inst_table).
+:- mode inst_table_set_clobbered_insts(in, in, out) is det.
+
:- pred inst_table_set_inst_key_table(inst_table, inst_key_table, inst_table).
:- mode inst_table_set_inst_key_table(in, in, out) is det.
@@ -507,6 +525,7 @@
any_inst_table,
shared_inst_table,
mostly_uniq_inst_table,
+ clobbered_inst_table,
inst_key_table
).
@@ -520,7 +539,8 @@
).
inst_table_init(inst_table(SubInsts, UnifyInsts, MergeInsts, GroundInsts,
- AnyInsts, SharedInsts, NondetLiveInsts, InstKeys)) :-
+ AnyInsts, SharedInsts, NondetLiveInsts, ClobberedInsts,
+ InstKeys)) :-
map__init(SubInsts),
map__init(UnifyInsts),
map__init(MergeInsts),
@@ -528,68 +548,81 @@
map__init(AnyInsts),
map__init(SharedInsts),
map__init(NondetLiveInsts),
+ map__init(ClobberedInsts),
inst_key_table_init(InstKeys).
inst_table_get_all_tables(InstTable, SubInsts, UnifyInsts, MergeInsts,
GroundInsts, AnyInsts, SharedInsts, NondetLiveInsts,
- InstKeys) :-
+ ClobberedInsts, InstKeys) :-
InstTable = inst_table(SubInsts, UnifyInsts, MergeInsts, GroundInsts,
- AnyInsts, SharedInsts, NondetLiveInsts, InstKeys).
+ AnyInsts, SharedInsts, NondetLiveInsts, ClobberedInsts,
+ InstKeys).
inst_table_set_all_tables(_InstTable0, SubInsts, UnifyInsts, MergeInsts,
- GroundInsts, AnyInsts, SharedInsts, NondetLiveInsts, InstKeys,
- InstTable) :-
+ GroundInsts, AnyInsts, SharedInsts, NondetLiveInsts,
+ ClobberedInsts, InstKeys, InstTable) :-
InstTable = inst_table(SubInsts, UnifyInsts, MergeInsts, GroundInsts,
- AnyInsts, SharedInsts, NondetLiveInsts, InstKeys).
+ AnyInsts, SharedInsts, NondetLiveInsts, ClobberedInsts,
+ InstKeys).
-inst_table_get_substitution_insts(inst_table(SubInsts, _, _, _, _, _, _, _),
+inst_table_get_substitution_insts(inst_table(SubInsts, _, _, _, _, _, _, _, _),
SubInsts).
-inst_table_get_unify_insts(inst_table(_, UnifyInsts, _, _, _, _, _, _),
+inst_table_get_unify_insts(inst_table(_, UnifyInsts, _, _, _, _, _, _, _),
UnifyInsts).
-inst_table_get_merge_insts(inst_table(_, _, MergeInsts, _, _, _, _, _),
+inst_table_get_merge_insts(inst_table(_, _, MergeInsts, _, _, _, _, _, _),
MergeInsts).
-inst_table_get_ground_insts(inst_table(_, _, _, GroundInsts, _, _, _, _),
+inst_table_get_ground_insts(inst_table(_, _, _, GroundInsts, _, _, _, _, _),
GroundInsts).
-inst_table_get_any_insts(inst_table(_, _, _, _, AnyInsts, _, _, _), AnyInsts).
+inst_table_get_any_insts(inst_table(_, _, _, _, AnyInsts, _, _, _, _),
+ AnyInsts).
-inst_table_get_shared_insts(inst_table(_, _, _, _, _, SharedInsts, _, _),
+inst_table_get_shared_insts(inst_table(_, _, _, _, _, SharedInsts, _, _, _),
SharedInsts).
inst_table_get_mostly_uniq_insts(
- inst_table(_, _, _, _, _, _, NondetLiveInsts, _),
+ inst_table(_, _, _, _, _, _, NondetLiveInsts, _, _),
NondetLiveInsts).
-inst_table_get_inst_key_table(inst_table(_, _, _, _, _, _, _, InstKeyTable),
+inst_table_get_clobbered_insts(
+ inst_table(_, _, _, _, _, _, _, ClobberedInsts, _),
+ ClobberedInsts).
+
+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_substitution_insts(inst_table(_, B, C, D, E, F, G, H, I),
+ SubInsts,
+ inst_table(SubInsts, B, C, D, E, F, G, H, I)).
-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)).
+inst_table_set_unify_insts(inst_table(A, _, C, D, E, F, G, H, I), UnifyInsts,
+ inst_table(A, UnifyInsts, C, D, E, F, G, H, I)).
-inst_table_set_merge_insts(inst_table(A, B, _, D, E, F, G, H), MergeInsts,
- inst_table(A, B, MergeInsts, D, E, F, G, H)).
+inst_table_set_merge_insts(inst_table(A, B, _, D, E, F, G, H, I), MergeInsts,
+ inst_table(A, B, MergeInsts, D, E, F, G, H, I)).
-inst_table_set_ground_insts(inst_table(A, B, C, _, E, F, G, H), GroundInsts,
- inst_table(A, B, C, GroundInsts, E, F, G, H)).
+inst_table_set_ground_insts(inst_table(A, B, C, _, E, F, G, H, I), GroundInsts,
+ inst_table(A, B, C, GroundInsts, E, F, G, H, I)).
-inst_table_set_any_insts(inst_table(A, B, C, D, _, F, G, H), AnyInsts,
- inst_table(A, B, C, D, AnyInsts, F, G, H)).
+inst_table_set_any_insts(inst_table(A, B, C, D, _, F, G, H, I), AnyInsts,
+ inst_table(A, B, C, D, AnyInsts, F, G, H, I)).
-inst_table_set_shared_insts(inst_table(A, B, C, D, E, _, G, H), SharedInsts,
- inst_table(A, B, C, D, E, SharedInsts, G, H)).
+inst_table_set_shared_insts(inst_table(A, B, C, D, E, _, G, H, I), SharedInsts,
+ inst_table(A, B, C, D, E, SharedInsts, G, H, I)).
-inst_table_set_mostly_uniq_insts(inst_table(A, B, C, D, E, F, _, H),
+inst_table_set_mostly_uniq_insts(inst_table(A, B, C, D, E, F, _, H, I),
NondetLiveInsts,
- inst_table(A, B, C, D, E, F, NondetLiveInsts, H)).
+ inst_table(A, B, C, D, E, F, NondetLiveInsts, H, I)).
+
+inst_table_set_clobbered_insts(inst_table(A, B, C, D, E, F, G, _, I),
+ ClobberedInsts,
+ inst_table(A, B, C, D, E, F, G, ClobberedInsts, I)).
-inst_table_set_inst_key_table(inst_table(A, B, C, D, E, F, G, _), InstKeys,
- inst_table(A, B, C, D, E, F, G, InstKeys)).
+inst_table_set_inst_key_table(inst_table(A, B, C, D, E, F, G, H, _), InstKeys,
+ inst_table(A, B, C, D, E, F, G, H, InstKeys)).
user_inst_table_init(user_inst_table(InstDefns, InstIds)) :-
map__init(InstDefns),
--- inst_match.m.bak2 Fri Feb 5 14:48:17 1999
+++ inst_match.m Fri Feb 5 15:19:29 1999
@@ -263,9 +263,14 @@
% Succeed iff the specified inst contains (directly or indirectly)
% the specified inst_name.
-:- pred inst_contains_instname(inst, instmap, inst_table, module_info, inst_name).
+:- pred inst_contains_instname(inst, instmap, inst_table, module_info,
+ inst_name).
:- mode inst_contains_instname(in, in, in, in, in) is semidet.
+:- pred inst_contains_inst_key(instmap, inst_table, module_info, inst,
+ inst_key).
+:- mode inst_contains_inst_key(in, in, in, in, in) is semidet.
+
% Nondeterministically produce all the inst_vars contained
% in the specified list of modes.
@@ -1458,6 +1463,49 @@
%-----------------------------------------------------------------------------%
+inst_contains_inst_key(InstMap, InstTable, ModuleInfo, Inst, Key) :-
+ set__init(Expansions),
+ inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
+ Inst, Key).
+
+:- pred inst_contains_inst_key_2(instmap, inst_table, module_info,
+ set(inst_name), inst, inst_key).
+:- mode inst_contains_inst_key_2(in, in, in, in, in, in) is semidet.
+
+inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
+ alias(Key0), Key) :-
+ ( instmap__inst_keys_are_equivalent(Key0, InstMap, Key, InstMap) ->
+ true
+ ;
+ inst_table_get_inst_key_table(InstTable, IKT),
+ instmap__inst_key_table_lookup(InstMap, IKT, Key0, Inst),
+ inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo,
+ Expansions, Inst, Key)
+ ).
+inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
+ bound(_, BoundInsts), Key) :-
+ list__member(functor(_, Insts), BoundInsts),
+ list__member(Inst, Insts),
+ inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
+ Inst, Key).
+inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions0,
+ defined_inst(InstName), Key) :-
+ ( set__member(InstName, Expansions0) ->
+ fail
+ ;
+ set__insert(Expansions0, InstName, Expansions),
+ inst_lookup(InstTable, ModuleInfo, InstName, Inst),
+ inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo,
+ Expansions, Inst, Key)
+ ).
+inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
+ abstract_inst(_, Insts), Key) :-
+ list__member(Inst, Insts),
+ inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
+ Inst, Key).
+
+%-----------------------------------------------------------------------------%
+
:- pred inst_contains_inst_var(inst, instmap, inst_table, module_info,
inst_var).
:- mode inst_contains_inst_var(in, in, in, in, out) is nondet.
--- inst_util.m.bak2 Fri Jan 29 11:56:05 1999
+++ inst_util.m Fri Feb 19 12:34:05 1999
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1997-1998 The University of Melbourne.
+% Copyright (C) 1997-1999 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -89,13 +89,39 @@
% of `unique' replaced with `shared'. It is an error if any part
% of the inst list is free.
+:- pred make_clobbered_inst(inst, inst_table, module_info, instmap,
+ inst, inst_table, module_info, instmap, list(inst_key)).
+:- mode make_clobbered_inst(in, in, in, in, out, out, out, out, out) is det.
+
%-----------------------------------------------------------------------------%
+ % Info collected by inst_merge for use in instmap__merge.
+:- type merge_info
+ ---> merge_info(
+ merge_subs,
+ ref_counts
+ ).
+ % Inst_key substitutions made when merging pairs of alias() insts.
:- type merge_subs == map(pair(inst_key), inst_key).
-:- type live_counts == pair(inst_key_counts).
+
+ % Reference counts for inst_keys in the two branches. The first two
+ % fields are for references in live variable only. These are passed
+ % in by instmap__merge and not changed within inst_merge.
+ % The last two fields are the total number of references among all
+ % non-local variables. The total reference counts are decremented by
+ % one whenever a dead variable containing an inst_key reference is
+ % clobbered.
+:- type ref_counts
+ ---> ref_counts(
+ inst_key_counts, % Live count for branch A.
+ inst_key_counts, % Live count for branch B.
+ inst_key_counts, % Total reference count, A.
+ inst_key_counts % Total reference count, B.
+ ).
-:- pred inst_merge(inst, inst, live_counts, instmap, inst_table, module_info,
- merge_subs, inst, instmap, inst_table, module_info, merge_subs).
+:- pred inst_merge(inst, inst, is_live, instmap, inst_table,
+ module_info, merge_info, inst, instmap, inst_table,
+ module_info, merge_info).
:- mode inst_merge(in, in, in, in, in, in, in, out, out, out, out, out)
is semidet.
@@ -448,7 +474,7 @@
% since both are live, we must make the result shared
% (unless it was already shared)
( ( UniqY = unique ; UniqY = mostly_unique ) ->
- make_shared_bound_inst_list(List0, UI0, List, UI)
+ make_shared_bound_inst_list(List0, UI0, List, UI, yes)
;
List = List0, UI = UI0
).
@@ -475,7 +501,7 @@
unify_inst_info_get_inst_table(UI0, InstTable0),
unify_inst_info_get_instmap(UI0, InstMap0),
bound_inst_list_is_ground_or_any(List0, InstMap0, InstTable0, M0),
- make_shared_bound_inst_list(List0, UI0, List, UI).
+ make_shared_bound_inst_list(List0, UI0, List, UI, yes).
abstractly_unify_inst_3(live, Real, bound(UniqX, ListX), bound(UniqY, ListY),
UI0, bound(Uniq, List), Det, UI) :-
@@ -1233,8 +1259,25 @@
:- mode make_any_inst(in, in, in, in, in, out, out, out) is semidet.
make_any_inst(not_reached, _, _, _, UI, not_reached, erroneous, UI).
-make_any_inst(alias(_), _, _, _, _, _, _, _) :-
- error("make_any_inst: alias() NYI"). % YYY
+make_any_inst(alias(IK0), IsLive, Uniq0, Real, UI0, alias(IK), Det, UI) :-
+ unify_inst_info_get_inst_table(UI0, InstTable0),
+ inst_table_get_inst_key_table(InstTable0, IKT0),
+ unify_inst_info_get_instmap(UI0, InstMap0),
+ instmap__inst_key_table_lookup(InstMap0, IKT0, IK0, Inst0),
+ make_any_inst(Inst0, IsLive, Uniq0, Real, UI0, Inst, Det, UI1),
+ ( Inst = Inst0 ->
+ IK = IK0,
+ UI = UI1
+ ;
+ unify_inst_info_get_inst_table(UI1, InstTable1),
+ inst_table_get_inst_key_table(InstTable1, IKT1),
+ inst_key_table_add(IKT1, Inst, IK, IKT),
+ inst_table_set_inst_key_table(InstTable1, IKT, InstTable),
+ unify_inst_info_set_inst_table(UI1, InstTable, UI2),
+ unify_inst_info_get_instmap(UI2, InstMap2),
+ instmap__add_alias(InstMap2, IK0, IK, InstMap),
+ unify_inst_info_set_instmap(UI2, InstMap, UI)
+ ).
make_any_inst(any(Uniq0), IsLive, Uniq1, Real, UI, any(Uniq),
semidet, UI) :-
allow_unify_bound_any(Real),
@@ -1363,7 +1406,7 @@
maybe_make_shared_inst_list([Inst0 | Insts0], [IsLive | IsLives], UI0,
[Inst | Insts], UI) :-
( IsLive = live ->
- make_shared_inst(Inst0, UI0, Inst, UI1)
+ make_shared_inst(Inst0, UI0, Inst, UI1, yes)
;
Inst = Inst0,
UI1 = UI0
@@ -1375,13 +1418,14 @@
error("maybe_make_shared_inst_list: length mismatch").
:- 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 semidet.
+ list(inst), unify_inst_info, bool).
+:- mode make_shared_inst_list(in, in, out, out, out) is det.
-make_shared_inst_list([], UI, [], UI).
-make_shared_inst_list([Inst0 | Insts0], UI0, [Inst | Insts], UI) :-
- make_shared_inst(Inst0, UI0, Inst, UI1),
- make_shared_inst_list(Insts0, UI1, Insts, UI).
+make_shared_inst_list([], UI, [], UI, yes).
+make_shared_inst_list([Inst0 | Insts0], UI0, [Inst | Insts], UI, Success) :-
+ make_shared_inst(Inst0, UI0, Inst, UI1, Success0),
+ make_shared_inst_list(Insts0, UI1, Insts, UI, Success1),
+ bool__and(Success0, Success1, Success).
% This is a wrapper for the above predicate, since this
% operation is exported (used in modecheck_unify.m).
@@ -1388,7 +1432,7 @@
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, Insts1, UI1) ->
+ ( make_shared_inst_list(Insts0, UI0, Insts1, UI1, yes) ->
Insts = Insts1,
UI = UI1
;
@@ -1400,16 +1444,16 @@
% make an inst shared; replace all occurrences of `unique' or `mostly_unique'
% 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 semidet.
+:- pred make_shared_inst(inst, unify_inst_info, inst, unify_inst_info, bool).
+:- mode make_shared_inst(in, in, out, out, out) is det.
-make_shared_inst(not_reached, UI, not_reached, UI).
-make_shared_inst(alias(Key), UI0, Inst, UI) :-
+make_shared_inst(not_reached, UI, not_reached, UI, yes).
+make_shared_inst(alias(Key), UI0, Inst, UI, Success) :-
unify_inst_info_get_instmap(UI0, InstMap0),
unify_inst_info_get_inst_table(UI0, InstTable0),
inst_table_get_inst_key_table(InstTable0, IKT0),
instmap__inst_key_table_lookup(InstMap0, IKT0, Key, Inst0),
- make_shared_inst(Inst0, UI0, Inst1, UI1),
+ make_shared_inst(Inst0, UI0, Inst1, UI1, Success),
( Inst0 = Inst1 ->
Inst = alias(Key),
UI = UI1
@@ -1424,20 +1468,22 @@
unify_inst_info_set_instmap(UI2, InstMap, UI),
Inst = alias(NewKey)
).
-make_shared_inst(any(Uniq0), UI, any(Uniq), UI) :-
+make_shared_inst(any(Uniq0), UI, any(Uniq), UI, yes) :-
make_shared(Uniq0, Uniq).
-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_inst(free(A), UI, free(A), UI, no).
+make_shared_inst(free(A, T), UI, free(A, T), UI, no).
+make_shared_inst(bound(Uniq0, BoundInsts0), UI0, bound(Uniq, BoundInsts), UI,
+ Success) :-
make_shared(Uniq0, Uniq),
- make_shared_bound_inst_list(BoundInsts0, UI0, BoundInsts, UI).
-make_shared_inst(ground(Uniq0, PredInst), UI, ground(Uniq, PredInst), UI) :-
+ make_shared_bound_inst_list(BoundInsts0, UI0, BoundInsts, UI, Success).
+make_shared_inst(ground(Uniq0, PredInst), UI, ground(Uniq, PredInst), UI, yes)
+ :-
make_shared(Uniq0, Uniq).
-make_shared_inst(inst_var(_), _, _, _) :-
+make_shared_inst(inst_var(_), _, _, _, _) :-
error("make_shared_inst: free inst var").
-make_shared_inst(abstract_inst(_,_), UI, _, UI) :-
+make_shared_inst(abstract_inst(_,_), UI, _, UI, _) :-
error("make_shared_inst(abstract_inst)").
-make_shared_inst(defined_inst(InstName), UI0, Inst, UI) :-
+make_shared_inst(defined_inst(InstName), UI0, Inst, UI, Success) :-
% check whether the inst name is already in the
% shared_inst table
unify_inst_info_get_inst_table(UI0, InstTable0),
@@ -1450,7 +1496,8 @@
;
SharedInst = defined_inst(InstName)
),
- UI = UI0
+ UI = UI0,
+ Success = yes
;
% insert the inst name in the shared_inst table, with
% value `unknown' for the moment
@@ -1464,7 +1511,7 @@
unify_inst_info_get_module_info(UI1, ModuleInfo1),
inst_lookup(InstTable1, ModuleInfo1, InstName, Inst0),
inst_expand_defined_inst(InstTable1, ModuleInfo1, Inst0, Inst1),
- make_shared_inst(Inst1, UI1, SharedInst, UI2),
+ make_shared_inst(Inst1, UI1, SharedInst, UI2, Success),
% now that we have determined the resulting Inst, store
% the appropriate value `known(SharedInst)' in the shared_inst
@@ -1499,15 +1546,17 @@
make_shared(clobbered, clobbered).
:- 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 semidet.
+ list(bound_inst), unify_inst_info, bool).
+:- mode make_shared_bound_inst_list(in, in, out, out, out) is det.
-make_shared_bound_inst_list([], UI, [], UI).
-make_shared_bound_inst_list([Bound0 | Bounds0], UI0, [Bound | Bounds], UI) :-
+make_shared_bound_inst_list([], UI, [], UI, yes).
+make_shared_bound_inst_list([Bound0 | Bounds0], UI0, [Bound | Bounds], UI,
+ Success) :-
Bound0 = functor(ConsId, ArgInsts0),
- make_shared_inst_list(ArgInsts0, UI0, ArgInsts, UI1),
+ make_shared_inst_list(ArgInsts0, UI0, ArgInsts, UI1, Success0),
Bound = functor(ConsId, ArgInsts),
- make_shared_bound_inst_list(Bounds0, UI1, Bounds, UI).
+ make_shared_bound_inst_list(Bounds0, UI1, Bounds, UI, Success1),
+ bool__and(Success0, Success1, Success).
%-----------------------------------------------------------------------------%
@@ -1646,6 +1695,105 @@
%-----------------------------------------------------------------------------%
+make_clobbered_inst(Inst0, InstTable0, ModuleInfo0, InstMap0,
+ Inst, InstTable, ModuleInfo, InstMap, RemovedKeys) :-
+ UI0 = unify_inst_info(ModuleInfo0, InstTable0, InstMap0),
+ make_clobbered_inst(Inst0, Inst, [] - UI0, RemovedKeys - UI),
+ UI = unify_inst_info(ModuleInfo, InstTable, InstMap).
+
+:- type clobber_inst_info == pair(list(inst_key), unify_inst_info).
+
+:- pred make_clobbered_inst(inst, inst, clobber_inst_info, clobber_inst_info).
+:- mode make_clobbered_inst(in, out, in, out) is det.
+
+make_clobbered_inst(any(U0), any(U), CI, CI) :-
+ clobber(U0, U).
+make_clobbered_inst(alias(IK), Inst, Rem0 - UI0, CI) :-
+ unify_inst_info_get_inst_table(UI0, InstTable0),
+ inst_table_get_inst_key_table(InstTable0, IKT0),
+ unify_inst_info_get_instmap(UI0, InstMap0),
+ instmap__inst_key_table_lookup(InstMap0, IKT0, IK, Inst0),
+ make_clobbered_inst(Inst0, Inst, [IK | Rem0] - UI0, CI).
+make_clobbered_inst(free(A), free(A), CI, CI).
+make_clobbered_inst(free(A, T), free(A, T), CI, CI).
+make_clobbered_inst(bound(U0, Bs0), bound(U, Bs), CI0, CI) :-
+ clobber(U0, U),
+ list__map_foldl(
+ ( pred(functor(C, Is0)::in, functor(C, Is)::out, in, out) is det -->
+ list__map_foldl(make_clobbered_inst, Is0, Is)
+ ), Bs0, Bs, CI0, CI).
+make_clobbered_inst(ground(U0, P), ground(U, P), CI, CI) :-
+ clobber(U0, U).
+make_clobbered_inst(not_reached, not_reached, CI, CI).
+make_clobbered_inst(inst_var(_), _, _, _) :-
+ error("inst_util__make_clobbered_inst: inst_var").
+make_clobbered_inst(abstract_inst(S, Is0), abstract_inst(S, Is), CI0, CI) :-
+ list__map_foldl(make_clobbered_inst, Is0, Is, CI0, CI).
+make_clobbered_inst(defined_inst(InstName), Inst, Rem0 - UI0, Rem - UI) :-
+ unify_inst_info_get_inst_table(UI0, InstTable0),
+ inst_table_get_clobbered_insts(InstTable0, ClobberedInsts0),
+ (
+ map__search(ClobberedInsts0, InstName, Result)
+ ->
+ ( Result = known(ClobberedInst0) ->
+ ClobberedInst = ClobberedInst0
+ ;
+ ClobberedInst = defined_inst(InstName)
+ ),
+ UI = UI0,
+ Rem = Rem0
+ ;
+ % insert the inst name in the clobbered_inst table, with
+ % value `unknown' for the moment
+ map__det_insert(ClobberedInsts0, InstName, unknown,
+ ClobberedInsts1),
+ inst_table_set_clobbered_insts(InstTable0, ClobberedInsts1,
+ InstTable1),
+ unify_inst_info_set_inst_table(UI0, InstTable1, UI1),
+
+ % expand the inst name, and invoke ourself recursively on
+ % it's expansion
+ unify_inst_info_get_module_info(UI1, ModuleInfo1),
+ inst_lookup(InstTable1, ModuleInfo1, InstName, Inst0),
+ inst_expand_defined_inst(InstTable1, ModuleInfo1, Inst0, Inst1),
+ make_clobbered_inst(Inst1, ClobberedInst, Rem0 - UI1,
+ Rem - UI2),
+
+ % now that we have determined the resulting Inst, store
+ % the appropriate value `known(ClobberedInst)' in the
+ % clobbered_inst table
+ unify_inst_info_get_inst_table(UI2, InstTable2),
+ inst_table_get_clobbered_insts(InstTable2, ClobberedInsts2),
+ map__det_update(ClobberedInsts2, InstName, known(ClobberedInst),
+ ClobberedInsts),
+ inst_table_set_clobbered_insts(InstTable2, ClobberedInsts,
+ InstTable),
+ unify_inst_info_set_inst_table(UI2, InstTable, UI)
+ ),
+ % avoid expanding recursive insts
+ unify_inst_info_get_inst_table(UI, LastInstTable),
+ unify_inst_info_get_module_info(UI, LastModuleInfo),
+ unify_inst_info_get_instmap(UI, LastInstMap),
+ (
+ inst_contains_instname(ClobberedInst, LastInstMap,
+ LastInstTable, LastModuleInfo, InstName)
+ ->
+ Inst = defined_inst(InstName)
+ ;
+ Inst = ClobberedInst
+ ).
+
+:- pred clobber(uniqueness, uniqueness).
+:- mode clobber(in, out) is det.
+
+clobber(shared, shared).
+clobber(unique, clobbered).
+clobber(mostly_unique, mostly_clobbered).
+clobber(clobbered, clobbered).
+clobber(mostly_clobbered, mostly_clobbered).
+
+%-----------------------------------------------------------------------------%
+
% Should we allow unifications between bound (or ground) insts
% and `any' insts?
% Previously we only allowed this for fake_unifies,
@@ -1670,23 +1818,23 @@
% 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) :-
+inst_merge(InstA, InstB, IsLive, InstMap0, InstTable0,
+ ModuleInfo0, MergeInfo0, Inst, InstMap, InstTable, ModuleInfo,
+ MergeInfo) :-
% check whether this pair of insts is already in
% the merge_insts table
inst_table_get_merge_insts(InstTable0, MergeInstTable0),
- ThisInstPair = InstA - InstB,
+ ThisInstPair = merge_inst_pair(IsLive, InstA, InstB),
( map__search(MergeInstTable0, ThisInstPair, Result) ->
ModuleInfo = ModuleInfo0,
( Result = known(MergedInst) ->
Inst0 = MergedInst
;
- Inst0 = defined_inst(merge_inst(InstA, InstB))
+ Inst0 = defined_inst(merge_inst(IsLive, InstA, InstB))
),
InstTable = InstTable0,
InstMap = InstMap0,
- MergeSubs = MergeSubs0
+ MergeInfo = MergeInfo0
;
% insert ThisInstPair into the table with value
%`unknown'
@@ -1696,9 +1844,9 @@
InstTable1),
% merge the insts
- inst_merge_2(InstA, InstB, LiveCounts, InstMap0,
- InstTable1, ModuleInfo0, MergeSubs0, Inst0, InstMap,
- InstTable2, ModuleInfo, MergeSubs),
+ inst_merge_2(InstA, InstB, IsLive, InstMap0,
+ InstTable1, ModuleInfo0, MergeInfo0, Inst0, InstMap,
+ InstTable2, ModuleInfo, MergeInfo),
% now update the value associated with ThisInstPair
inst_table_get_merge_insts(InstTable2, MergeInstTable2),
@@ -1708,129 +1856,134 @@
InstTable)
),
% avoid expanding recursive insts
- ( inst_contains_instname(Inst0, InstMap, InstTable, ModuleInfo,
- merge_inst(InstA, InstB)) ->
- Inst = defined_inst(merge_inst(InstA, InstB))
+ (
+ inst_contains_instname(Inst0, InstMap, InstTable, ModuleInfo,
+ merge_inst(IsLive, InstA, InstB))
+ ->
+ Inst = defined_inst(merge_inst(IsLive, InstA, InstB))
;
Inst = Inst0
).
-:- pred inst_merge_2(inst, inst, is_live, live_counts, instmap, inst_table, module_info,
- merge_subs, inst, instmap, inst_table, module_info, merge_subs).
+:- pred inst_merge_2(inst, inst, is_live, instmap, inst_table,
+ module_info, merge_info, inst, instmap, inst_table,
+ module_info, merge_info).
:- mode inst_merge_2(in, in, in, in, in, in, in, out, out, out, out, out)
is semidet.
-inst_merge_2(InstA, InstB, LiveCounts, InstMap0, InstTable0, ModuleInfo0,
- MergeSubs0, Inst, InstMap, InstTable, ModuleInfo, MergeSubs) :-
- /*********
- % would this test improve efficiency??
- ( InstA = InstB ->
- Inst = InstA,
- ModuleInfo = ModuleInfo0
- ;
- ************/
+inst_merge_2(InstA, InstB, IsLive, InstMap0, InstTable0,
+ ModuleInfo0, MergeInfo0, Inst, InstMap, InstTable, ModuleInfo,
+ MergeInfo) :-
+ MergeInfo0 = merge_info(MergeSubs0, RefCounts0),
+ RefCounts0 = ref_counts(LiveCountsA, LiveCountsB, CountsA0, CountsB0),
+ expand_inst(IsLive, LiveCountsA, InstA, InstMap0, InstTable0,
+ ModuleInfo0, CountsA0, InstA2, InstMap1,
+ InstTable1, ModuleInfo1, CountsA),
+ expand_inst(IsLive, LiveCountsB, InstB, InstMap1, InstTable1,
+ ModuleInfo1, CountsB0, InstB2, InstMap2,
+ InstTable2, ModuleInfo2, CountsB),
+ RefCounts1 = ref_counts(LiveCountsA, LiveCountsB, CountsA, CountsB),
+ MergeInfo1 = merge_info(MergeSubs0, RefCounts1),
(
- InstA = alias(IKA),
- InstB = alias(IKB),
- instmap__inst_keys_are_equivalent(IKA, InstMap0, IKB, InstMap0)
+ InstB2 = not_reached
->
- Inst = alias(IKA),
- InstTable = InstTable0,
- ModuleInfo = ModuleInfo0,
- InstMap = InstMap0,
- map__set(MergeSubs0, IKA - IKB, IKA, MergeSubs)
+ Inst = InstA2,
+ ModuleInfo = ModuleInfo2,
+ InstTable = InstTable2,
+ InstMap = InstMap2,
+ MergeInfo = MergeInfo1
+ ;
+ InstA2 = not_reached
+ ->
+ Inst = InstB2,
+ ModuleInfo = ModuleInfo2,
+ InstTable = InstTable2,
+ InstMap = InstMap2,
+ MergeInfo = MergeInfo1
+ ;
+ 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, InstMap2,
+ InstTable2, ModuleInfo2, InstA3, InstMap3,
+ InstTable3, ModuleInfo3),
+ inst_merge_3(InstA3, InstB2, IsLive,
+ InstMap3, InstTable3, ModuleInfo3, MergeInfo1,
+ Inst, InstMap, InstTable, ModuleInfo, MergeInfo)
+ ;
+ 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, InstMap2,
+ InstTable2, ModuleInfo2, InstB3, InstMap3,
+ InstTable3, ModuleInfo3),
+ inst_merge_3(InstA2, InstB3, IsLive,
+ InstMap3, InstTable3, ModuleInfo3, MergeInfo1,
+ Inst, InstMap, InstTable, ModuleInfo, MergeInfo)
;
- LiveCounts = LiveCountsA - LiveCountsB,
- expand_inst(LiveCountsA, InstMap0, InstTable0, ModuleInfo0,
- InstA, InstA2),
- expand_inst(LiveCountsB, InstMap0, InstTable0, ModuleInfo0,
- InstB, InstB2),
+ InstA2 = alias(IKA),
+ InstB2 = alias(IKB)
+ ->
(
- InstB2 = not_reached
- ->
- Inst = InstA2,
- ModuleInfo = ModuleInfo0,
- InstTable = InstTable0,
- InstMap = InstMap0,
- MergeSubs = MergeSubs0
- ;
- InstA2 = not_reached
- ->
- Inst = InstB2,
- ModuleInfo = ModuleInfo0,
- InstTable = InstTable0,
- InstMap = InstMap0,
- MergeSubs = MergeSubs0
- ;
- InstA2 = alias(IKA0),
- InstB2 \= alias(_)
+ instmap__inst_keys_are_equivalent(IKA, InstMap2,
+ IKB, InstMap2)
->
- 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)
+ IK = IKA,
+ InstTable = InstTable2,
+ ModuleInfo = ModuleInfo2,
+ InstMap = InstMap2,
+ map__set(MergeSubs0, IKA - IKB, IKA, MergeSubs),
+ MergeInfo = merge_info(MergeSubs, RefCounts1)
;
- InstB2 = alias(IKB0),
- InstA2 \= alias(_)
+ map__search(MergeSubs0, IKA - IKB, IK0)
->
- Lambda = lambda([I::out] is nondet, (
- map__member(MergeSubs0, _ - IKB0, MergeIK),
- I = alias(MergeIK))),
- make_shared_merge_insts(IKB0, Lambda, InstMap0,
- InstTable0, ModuleInfo0, InstB3, InstMap1,
- InstTable1, ModuleInfo1),
- inst_merge_3(InstA2, InstB3, LiveCounts, InstMap1,
- InstTable1, ModuleInfo1, MergeSubs0, Inst,
- InstMap, InstTable, ModuleInfo, MergeSubs)
- ;
- InstA2 = alias(IKA),
- InstB2 = alias(IKB)
- ->
- LiveCounts = LiveCountsA - LiveCountsB,
- ( map__search(MergeSubs0, IKA - IKB, IK0) ->
- IK = IK0,
- InstTable = InstTable0,
- ModuleInfo = ModuleInfo0,
- InstMap = InstMap0,
- MergeSubs = MergeSubs0
+ IK = IK0,
+ InstTable = InstTable2,
+ ModuleInfo = ModuleInfo2,
+ InstMap = InstMap2,
+ MergeInfo = MergeInfo1
+ ;
+ inst_table_get_inst_key_table(InstTable2, IKT0),
+ instmap__inst_key_table_lookup(InstMap2, IKT0, IKA,
+ InstA3),
+ instmap__inst_key_table_lookup(InstMap2, IKT0, IKB,
+ InstB3),
+ inst_merge_3(InstA3, InstB3, IsLive, InstMap2,
+ InstTable2, ModuleInfo2, MergeInfo1,
+ Inst0, InstMap, InstTable3, ModuleInfo,
+ MergeInfo2),
+ MergeInfo2 = merge_info(MergeSubs2, RefCounts),
+ ( map__search(MergeSubs2, IKA - IKB, IK1) ->
+ IK = IK1,
+ MergeSubs = MergeSubs2,
+ InstTable = InstTable3
;
- inst_table_get_inst_key_table(InstTable0, IKT0),
- instmap__inst_key_table_lookup(InstMap0, IKT0, IKA,
- InstA3),
- instmap__inst_key_table_lookup(InstMap0, IKT0, IKB,
- InstB3),
- inst_merge_3(InstA3, InstB3, LiveCounts, InstMap0,
- InstTable0, ModuleInfo0, MergeSubs0, Inst0,
- InstMap, InstTable1, ModuleInfo, MergeSubs1),
- ( map__search(MergeSubs1, IKA - IKB, IK1) ->
- IK = IK1,
- MergeSubs = MergeSubs1,
- InstTable = InstTable1
- ;
- % Create a new inst key for the merged inst.
- inst_table_get_inst_key_table(InstTable1, IKT1),
- inst_key_table_add(IKT1, Inst0, IK, IKT),
- inst_table_set_inst_key_table(InstTable1, IKT,
- InstTable),
- map__det_insert(MergeSubs1, IKA - IKB, IK,
- MergeSubs)
- )
+ % Create a new inst key for the merged inst.
+ inst_table_get_inst_key_table(InstTable3, IKT1),
+ inst_key_table_add(IKT1, Inst0, IK, IKT),
+ inst_table_set_inst_key_table(InstTable3, IKT,
+ InstTable),
+ map__det_insert(MergeSubs2, IKA - IKB, IK,
+ MergeSubs)
),
- Inst = alias(IK)
- ;
- inst_merge_3(InstA2, InstB2, LiveCounts, InstMap0,
- InstTable0, ModuleInfo0, MergeSubs0, Inst,
- InstMap, InstTable, ModuleInfo, MergeSubs)
- )
+ MergeInfo = merge_info(MergeSubs, RefCounts)
+ ),
+ Inst = alias(IK)
+ ;
+ inst_merge_3(InstA2, InstB2, IsLive, InstMap2,
+ InstTable2, ModuleInfo2, MergeInfo1, Inst,
+ InstMap, InstTable, ModuleInfo, MergeInfo)
).
-:- pred inst_merge_3(inst, inst, live_counts, instmap, inst_table, module_info,
- merge_subs, inst, instmap, inst_table, module_info, merge_subs).
+:- pred inst_merge_3(inst, inst, is_live, instmap, inst_table,
+ module_info, merge_info, inst, instmap, inst_table,
+ module_info, merge_info).
:- mode inst_merge_3(in, in, in, in, in, in, in, out, out, out, out, out)
is semidet.
@@ -1850,8 +2003,8 @@
% 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, MS, any(Uniq),
- InstMap, InstTable, M, MS) :-
+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, MS, any(Uniq),
InstMap, InstTable, M, MS) :-
@@ -1897,13 +2050,13 @@
( Uniq = clobbered ; Uniq = mostly_clobbered ).
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) :-
+inst_merge_3(bound(UniqA, ListA), bound(UniqB, ListB), IsLive, InstMap0,
+ InstTable0, ModuleInfo0, MergeInfo0, bound(Uniq, List),
+ InstMap, InstTable, ModuleInfo, MergeInfo) :-
merge_uniq(UniqA, UniqB, Uniq),
- bound_inst_list_merge(ListA, ListB, LiveCounts, InstMap0, InstTable0,
- ModuleInfo0, MergeSubs0, List, InstMap, InstTable, ModuleInfo,
- MergeSubs).
+ bound_inst_list_merge(ListA, ListB, IsLive, InstMap0, InstTable0,
+ ModuleInfo0, MergeInfo0, List, InstMap, InstTable,
+ ModuleInfo, MergeInfo).
inst_merge_3(bound(UniqA, ListA), ground(UniqB, _), _, InstMap,
InstTable, ModuleInfo, MS, ground(Uniq, no), InstMap, InstTable,
ModuleInfo, MS) :-
@@ -1943,13 +2096,13 @@
MaybePred = no
),
merge_uniq(UniqA, UniqB, Uniq).
-inst_merge_3(abstract_inst(Name, ArgsA), abstract_inst(Name, ArgsB),
- LiveCounts, InstMap0, InstTable0, ModuleInfo0, MergeSubs0,
+inst_merge_3(abstract_inst(Name, ArgsA), abstract_inst(Name, ArgsB), IsLive,
+ InstMap0, InstTable0, ModuleInfo0, MergeInfo0,
abstract_inst(Name, Args), InstMap, InstTable, ModuleInfo,
- MergeSubs) :-
- inst_list_merge(ArgsA, ArgsB, LiveCounts, InstMap0, InstTable0,
- ModuleInfo0, MergeSubs0, Args, InstMap, InstTable, ModuleInfo,
- MergeSubs).
+ MergeInfo) :-
+ inst_list_merge(ArgsA, ArgsB, IsLive, InstMap0, InstTable0,
+ ModuleInfo0, MergeInfo0, Args, InstMap, InstTable, ModuleInfo,
+ MergeInfo).
inst_merge_3(not_reached, Inst, _, InstMap, InstTable, M, MS, Inst, InstMap,
InstTable, M, MS).
@@ -2044,22 +2197,23 @@
%-----------------------------------------------------------------------------%
-:- 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).
+:- pred inst_list_merge(list(inst), list(inst), is_live, instmap,
+ inst_table, module_info, merge_info, list(inst), instmap,
+ inst_table, module_info, merge_info).
+:- mode inst_list_merge(in, in, in, in, in, in, in, out, out, out,
+ out, out) is semidet.
+
+inst_list_merge([], [], _, InstMap, InstTable, ModuleInfo, MergeInfo, [],
+ InstMap, InstTable, ModuleInfo, MergeInfo).
+inst_list_merge([ArgA | ArgsA], [ArgB | ArgsB], IsLive, InstMap0,
+ InstTable0, ModuleInfo0, MergeInfo0, [Arg | Args], InstMap,
+ InstTable, ModuleInfo, MergeInfo) :-
+ inst_merge(ArgA, ArgB, IsLive, InstMap0, InstTable0,
+ ModuleInfo0, MergeInfo0, Arg, InstMap1, InstTable1,
+ ModuleInfo1, MergeInfo1),
+ inst_list_merge(ArgsA, ArgsB, IsLive, InstMap1, InstTable1,
+ ModuleInfo1, MergeInfo1, Args, InstMap, InstTable, ModuleInfo,
+ MergeInfo).
% bound_inst_list_merge(Xs, Ys, InstTable0, ModuleInfo0, Zs, InstTable,
% ModuleInfo):
@@ -2068,22 +2222,23 @@
% 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), 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, LiveCounts, InstMap0, InstTable0, ModuleInfo0,
- MergeSubs0, Zs, InstMap, InstTable, ModuleInfo, MergeSubs) :-
+:- pred bound_inst_list_merge(list(bound_inst), list(bound_inst), is_live,
+ instmap, inst_table, module_info, merge_info,
+ list(bound_inst), instmap, inst_table, module_info, merge_info).
+:- 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, IsLive, InstMap0, InstTable0,
+ ModuleInfo0, MergeInfo0, Zs, InstMap, InstTable, ModuleInfo,
+ MergeInfo) :-
( Xs = [] ->
- MergeSubs = MergeSubs0,
+ MergeInfo = MergeInfo0,
ModuleInfo = ModuleInfo0,
InstTable = InstTable0,
InstMap = InstMap0,
Zs = Ys
; Ys = [] ->
- MergeSubs = MergeSubs0,
+ MergeInfo = MergeInfo0,
ModuleInfo = ModuleInfo0,
InstTable = InstTable0,
InstMap = InstMap0,
@@ -2094,55 +2249,110 @@
X = functor(ConsIdX, ArgsX),
Y = functor(ConsIdY, ArgsY),
( ConsIdX = ConsIdY ->
- inst_list_merge(ArgsX, ArgsY, LiveCounts, InstMap0,
- InstTable0, ModuleInfo0, MergeSubs0, Args,
- InstMap1, InstTable1, ModuleInfo1, MergeSubs1),
+ MergeInfo0 = merge_info(_, RefCounts0),
+ RefCounts0 = ref_counts(_, _, TotalA0, TotalB0),
+
+ inst_list_merge(ArgsX, ArgsY, IsLive, InstMap0,
+ InstTable0, ModuleInfo0, MergeInfo0,
+ Args, InstMap1, InstTable1, ModuleInfo1,
+ MergeInfo1),
Z = functor(ConsIdX, Args),
Zs = [Z | Zs1],
- bound_inst_list_merge(Xs1, Ys1, LiveCounts, InstMap1,
- InstTable1, ModuleInfo1, MergeSubs1, Zs1,
- InstMap, InstTable, ModuleInfo, MergeSubs)
+
+ MergeInfo1 = merge_info(MergeSubs1, RefCounts1),
+ RefCounts1 = ref_counts(LiveA1, LiveB1, TotalA1,
+ TotalB1),
+ RefCounts2 = ref_counts(LiveA1, LiveB1, TotalA0,
+ TotalB0),
+ MergeInfo2 = merge_info(MergeSubs1, RefCounts2),
+
+ bound_inst_list_merge(Xs1, Ys1, IsLive, InstMap1,
+ InstTable1, ModuleInfo1, MergeInfo2, Zs1,
+ InstMap, InstTable, ModuleInfo, MergeInfo3),
+
+ MergeInfo3 = merge_info(MergeSubs, RefCounts3),
+ RefCounts3 = ref_counts(LiveA, LiveB, TotalA3, TotalB3),
+ uniq_counts_max_merge(TotalA1, TotalA3, TotalA),
+ uniq_counts_max_merge(TotalB1, TotalB3, TotalB),
+ RefCounts = ref_counts(LiveA, LiveB, TotalA, TotalB),
+ MergeInfo = merge_info(MergeSubs, RefCounts)
; compare(<, ConsIdX, ConsIdY) ->
Zs = [X | Zs1],
- bound_inst_list_merge(Xs1, Ys, LiveCounts, InstMap0,
- InstTable0, ModuleInfo0, MergeSubs0, Zs1,
- InstMap, InstTable, ModuleInfo, MergeSubs)
+ bound_inst_list_merge(Xs1, Ys, IsLive, InstMap0,
+ InstTable0, ModuleInfo0, MergeInfo0,
+ Zs1, InstMap, InstTable, ModuleInfo, MergeInfo)
;
Zs = [Y | Zs1],
- bound_inst_list_merge(Xs, Ys1, LiveCounts, InstMap0,
- InstTable0, ModuleInfo0, MergeSubs0, Zs1,
- InstMap, InstTable, ModuleInfo, MergeSubs)
+ bound_inst_list_merge(Xs, Ys1, IsLive, InstMap0,
+ InstTable0, ModuleInfo0, MergeInfo0,
+ Zs1, InstMap, InstTable, ModuleInfo, MergeInfo)
)
).
%-----------------------------------------------------------------------------%
-:- pred expand_inst(inst_key_counts, instmap, inst_table, module_info, inst,
- inst).
-:- mode expand_inst(in, in, in, in, in, out) is det.
+:- pred expand_inst(is_live, inst_key_counts, inst, instmap, inst_table,
+ module_info, inst_key_counts, inst, instmap, inst_table,
+ module_info, inst_key_counts).
+:- mode expand_inst(in, in, in, in, in, in, in, out, out, out, out, out)
+ is det.
-expand_inst(LiveCounts, InstMap, InstTable, ModuleInfo, Inst0, Inst) :-
+expand_inst(IsLive, LiveCounts, Inst0, InstMap0, InstTable0, ModuleInfo0,
+ Counts0, Inst, InstMap, InstTable, ModuleInfo, Counts) :-
( Inst0 = alias(IK) ->
- ( has_count_many(LiveCounts, IK) ->
- Inst = Inst0
+ ( IsLive = dead ->
+ inst_expand(InstMap0, InstTable0, ModuleInfo0, Inst0,
+ Inst1),
+ ( has_count_many(Counts0, IK) ->
+ make_clobbered_inst(Inst1, InstTable0,
+ ModuleInfo0, InstMap0, Inst, InstTable,
+ ModuleInfo, InstMap, RemovedKeys),
+ list__foldl(dec_uniq_count, [IK | RemovedKeys],
+ Counts0, Counts)
+ ;
+ Inst = Inst1,
+ InstMap = InstMap0,
+ InstTable = InstTable0,
+ ModuleInfo = ModuleInfo0,
+ Counts = Counts0
+ )
+ ; has_count_many(LiveCounts, IK) ->
+ % If the inst_key has multiple references, we need to
+ % hang on to it.
+ Inst = Inst0,
+ InstMap = InstMap0,
+ InstTable = InstTable0,
+ ModuleInfo = ModuleInfo0,
+ Counts = Counts0
;
- inst_expand(InstMap, InstTable, ModuleInfo, Inst0, Inst)
+ % This is the only live reference to the inst_key so
+ % we can remove the alias.
+ InstMap = InstMap0,
+ InstTable = InstTable0,
+ ModuleInfo = ModuleInfo0,
+ inst_expand(InstMap0, InstTable0, ModuleInfo0, Inst0,
+ Inst),
+ Counts = Counts0
)
;
+ InstMap = InstMap0,
+ InstTable = InstTable0,
+ ModuleInfo = ModuleInfo0,
+ Counts = Counts0,
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).
+:- 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) :-
+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),
+ make_shared_inst(alias(IK0), UI0, Inst1, UI1, yes),
solutions(Lambda, Insts),
- make_shared_inst_list(Insts, UI1, _, UI),
+ make_shared_inst_list(Insts, UI1, _, UI, yes),
UI = unify_inst_info(ModuleInfo, InstTable, InstMap),
Inst1 = alias(IK),
inst_table_get_inst_key_table(InstTable, IKT),
@@ -2197,11 +2407,12 @@
inst_table_create_sub(InstTable0, NewInstTable, Sub, InstTable) :-
inst_table_get_all_tables(InstTable0, SubInstTable0, UnifyInstTable0,
MergeInstTable0, GroundInstTable0, AnyInstTable0,
- SharedInstTable0, MostlyUniqInstTable0, IKT0),
+ SharedInstTable0, ClobberedInstTable0, MostlyUniqInstTable0,
+ IKT0),
inst_table_get_all_tables(NewInstTable, NewSubInstTable,
NewUnifyInstTable, NewMergeInstTable, NewGroundInstTable,
NewAnyInstTable, NewSharedInstTable, NewMostlyUniqInstTable,
- NewIKT),
+ NewClobberedInstTable, NewIKT),
inst_key_table_create_sub(IKT0, NewIKT, Sub, IKT),
maybe_inst_det_table_apply_sub(UnifyInstTable0, NewUnifyInstTable,
@@ -2231,9 +2442,15 @@
;
error("NYI: inst_table_create_sub (mostly_uniq_inst_table)")
),
+ ( map__is_empty(NewClobberedInstTable) ->
+ ClobberedInstTable = ClobberedInstTable0
+ ;
+ error("NYI: inst_table_create_sub (clobbered_inst_table)")
+ ),
inst_table_set_all_tables(InstTable0, SubInstTable, UnifyInstTable,
MergeInstTable, GroundInstTable, AnyInstTable,
- SharedInstTable, MostlyUniqInstTable, IKT, InstTable).
+ SharedInstTable, MostlyUniqInstTable, ClobberedInstTable, IKT,
+ InstTable).
:- pred maybe_inst_table_apply_sub(map(inst_name, maybe_inst),
map(inst_name, maybe_inst), map(inst_name, maybe_inst),
@@ -2312,13 +2529,13 @@
merge_inst_table_apply_sub_2(NewTableAL, Table0, Table, Sub)
).
-:- pred merge_inst_table_apply_sub_2(assoc_list(pair(inst), maybe_inst),
+:- pred merge_inst_table_apply_sub_2(assoc_list(merge_inst_pair, maybe_inst),
merge_inst_table, merge_inst_table, inst_key_sub).
:- mode merge_inst_table_apply_sub_2(in, in, out, in) is det.
merge_inst_table_apply_sub_2([], Table, Table, _).
-merge_inst_table_apply_sub_2([(IA0 - IB0) - Inst0 | Rest], Table0, Table,
- Sub) :-
+merge_inst_table_apply_sub_2([Pair0 - Inst0 | Rest], Table0, Table, Sub) :-
+ Pair0 = merge_inst_pair(IsLive, IA0, IB0),
inst_apply_sub(Sub, IA0, IA),
inst_apply_sub(Sub, IB0, IB),
( Inst0 = unknown,
@@ -2327,7 +2544,7 @@
inst_apply_sub(Sub, I0, I),
Inst = known(I)
),
- map__set(Table0, IA - IB, Inst, Table1),
+ map__set(Table0, merge_inst_pair(IsLive, IA, IB), Inst, Table1),
merge_inst_table_apply_sub_2(Rest, Table1, Table, Sub).
:- pred substitution_inst_table_apply_sub(substitution_inst_table,
@@ -2368,8 +2585,8 @@
inst_name_apply_sub(Sub, user_inst(Sym, Insts0), user_inst(Sym, Insts)) :-
list__map(inst_apply_sub(Sub), Insts0, Insts).
-inst_name_apply_sub(Sub, merge_inst(InstA0, InstB0),
- merge_inst(InstA, InstB)) :-
+inst_name_apply_sub(Sub, merge_inst(IsLive, InstA0, InstB0),
+ merge_inst(IsLive, InstA, InstB)) :-
inst_apply_sub(Sub, InstA0, InstA),
inst_apply_sub(Sub, InstB0, InstB).
inst_name_apply_sub(Sub, unify_inst(IsLive, InstA0, InstB0, IsReal),
--- instmap.m.bak2 Fri Jan 29 11:56:52 1999
+++ instmap.m Fri Feb 19 12:03:14 1999
@@ -504,6 +504,17 @@
% of a disjunction or if-then-else, and update the
% instantiatedness of all the nonlocal variables,
% checking that it is the same for every branch.
+ % Algorithm:
+ % 1. Remove unreachable instmaps.
+ % 2. Take the first two instmaps and remove singleton inst_keys
+ % from each.
+ % 3. Expand any inst_key substitutions that occur in one instmap
+ % but not the other (done by `instmap__merge_subs').
+ % 4. Call `inst_merge' for each non-local variable.
+ % 5. Work out which inst_keys need to become shared and make
+ % them shared (uses information collected by `inst_merge').
+ % 6. Recursively merge the resulting instmap with the instmap
+ % from the next branch (go back to step 2).
instmap__merge(NonLocals, InstMapList, MergeContext, ModeInfo0, ModeInfo) :-
mode_info_get_instmap(ModeInfo0, InstMapBefore),
@@ -576,8 +587,7 @@
% Export this stuff for use in inst_util.m.
:- type uniq_count
- ---> zero
- ; one
+ ---> known(int)
; many.
:- type uniq_counts(T) == map(T, uniq_count).
@@ -587,8 +597,8 @@
:- 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 dec_uniq_count(T, uniq_counts(T), uniq_counts(T)).
+:- mode dec_uniq_count(in, in, out) is det.
:- pred has_count_zero(uniq_counts(T), T).
:- mode has_count_zero(in, in) is semidet.
@@ -599,6 +609,9 @@
:- pred has_count_many(uniq_counts(T), T).
:- mode has_count_many(in, in) is semidet.
+:- pred set_count_many(T, uniq_counts(T), uniq_counts(T)).
+:- mode set_count_many(in, in, out) is det.
+
:- pred uniq_count_max(uniq_count, uniq_count, uniq_count).
:- mode uniq_count_max(in, in, out) is det.
@@ -607,37 +620,54 @@
:- implementation.
+:- import_module int.
+
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,
+ (
+ C0 = known(N),
+ map__det_update(Map0, Item, known(N + 1), Map)
+ ;
+ C0 = many,
Map = Map0
)
;
- map__det_insert(Map0, Item, one, Map)
+ map__det_insert(Map0, Item, known(1), Map)
).
-set_uniq_count_many(Item, Map0, Map) :-
- map__set(Map0, Item, many, Map).
+dec_uniq_count(Item, Map0, Map) :-
+ ( map__search(Map0, Item, C0) ->
+ (
+ C0 = known(N0),
+ int__max(N0 - 1, 0, N),
+ map__det_update(Map0, Item, known(N), Map)
+ ;
+ C0 = many,
+ Map = Map0
+ )
+ ;
+ Map = Map0
+ ).
has_count_zero(Map, Item) :-
- % map__search(Map, Item, Count) => Count = zero.
- \+ ( map__search(Map, Item, Count), \+ Count = zero ).
+ map__search(Map, Item, Count) => Count = known(0).
has_count_one(Map, Item) :-
- map__search(Map, Item, one).
+ map__search(Map, Item, known(1)).
has_count_many(Map, Item) :-
- map__search(Map, Item, many).
+ map__search(Map, Item, Count),
+ ( Count = known(N), N > 1
+ ; Count = many
+ ).
+
+set_count_many(Item, Map0, Map) :-
+ map__set(Map0, Item, many, Map).
-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_count_max(known(_), many, many).
+uniq_count_max(known(A), known(B), known(C)) :-
+ int__max(A, B, C).
uniq_counts_max_merge(MapA, MapB, Map) :-
map__foldl(lambda([Item::in, CountA::in, M0::in, M::out] is det,
@@ -686,25 +716,33 @@
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,
+ instmap__count_inst_keys_in_inst(no, 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,
+:- pred instmap__count_inst_keys_in_inst(bool, 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.
+:- mode instmap__count_inst_keys_in_inst(in, 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,
+instmap__count_inst_keys_in_inst(SetCountMany, InstMap, InstTable, ModuleInfo,
+ SeenTwice, Inst) -->
+ inst_fold(InstMap, InstTable, ModuleInfo,
+ count_inst_keys_before(SetCountMany),
count_inst_keys_after(InstMap, InstTable, ModuleInfo, SeenTwice),
uniq_counts_max_merge, Inst).
-:- pred count_inst_keys_before((inst)::in, set(inst_name)::in,
+:- pred count_inst_keys_before(bool::in, (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).
+count_inst_keys_before(SetCountMany, alias(Key), _) -->
+ (
+ { SetCountMany = yes },
+ set_count_many(Key)
+ ;
+ { SetCountMany = no },
+ 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,
@@ -719,7 +757,7 @@
% 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,
+ instmap__count_inst_keys_in_inst(yes, InstMap, InstTable, ModuleInfo,
SeenTwice, defined_inst(InstName)).
%-----------------------------------------------------------------------------%
@@ -767,12 +805,19 @@
LiveCountsA),
instmap__count_inst_keys(Liveness, ModuleInfo0, InstTable1, InstMapB,
LiveCountsB),
- LiveCounts = LiveCountsA - LiveCountsB,
+ instmap__count_inst_keys(Vars, ModuleInfo0, InstTable1, InstMapA,
+ TotalCountsA),
+ instmap__count_inst_keys(Vars, ModuleInfo0, InstTable1, InstMapB,
+ TotalCountsB),
+ RefCounts0 = ref_counts(LiveCountsA, LiveCountsB, TotalCountsA,
+ TotalCountsB),
map__init(MergeSubs0),
- instmap__merge_4(Vars, InstMapA, InstMapB, LiveCounts, InstTable1,
- ModuleInfo0, InstMap0, MergeSubs0, InstTable2,
- ModuleInfo1, InstMapAB0, MergeSubs, ErrorList0),
+ MergeInfo0 = merge_info(MergeSubs0, RefCounts0),
+ instmap__merge_4(Vars, InstMapA, InstMapB, Liveness, InstTable1,
+ ModuleInfo0, InstMap0, MergeInfo0, InstTable2,
+ ModuleInfo1, InstMapAB0, MergeInfo, ErrorList0),
+ MergeInfo = merge_info(MergeSubs, _RefCounts),
% Work out which inst keys need to be made shared.
solutions(lambda([I::out] is nondet, (
@@ -794,38 +839,39 @@
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).
+:- pred instmap__merge_4(list(prog_var), instmap, instmap, list(prog_var),
+ inst_table, module_info, instmap, merge_info, inst_table, module_info,
+ instmap, merge_info, 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__merge_4([], _, _, _, InstTable, ModuleInfo, InstMap, MergeInfo,
+ InstTable, ModuleInfo, InstMap, MergeInfo, []).
+instmap__merge_4([Var | Vars], InstMapA, InstMapB, Liveness, InstTable0,
+ ModuleInfo0, InstMap0, MergeInfo0, InstTable, ModuleInfo,
+ InstMap, MergeInfo, Errors) :-
+ instmap__merge_4(Vars, InstMapA, InstMapB, Liveness, InstTable0,
+ ModuleInfo0, InstMap0, MergeInfo0, InstTable1,
+ ModuleInfo1, InstMap1, MergeInfo1, Errors1),
instmap__lookup_var(InstMapA, Var, InstA),
instmap__lookup_var(InstMapB, Var, InstB),
+ IsLive = ( list__member(Var, Liveness) -> live ; dead ),
(
- inst_merge(InstA, InstB, LiveCounts, InstMap1,
- InstTable1, ModuleInfo1, MergeSubs1, Inst, InstMap2,
- InstTable2, ModuleInfo2, MergeSubs2)
+ inst_merge(InstA, InstB, IsLive, InstMap1, InstTable1,
+ ModuleInfo1, MergeInfo1, Inst, InstMap2, InstTable2,
+ ModuleInfo2, MergeInfo2)
->
instmap__set(InstMap2, Var, Inst, InstMap),
Errors = Errors1,
ModuleInfo = ModuleInfo2,
InstTable = InstTable2,
- MergeSubs = MergeSubs2
+ MergeInfo = MergeInfo2
;
instmap__set(InstMap1, Var, not_reached, InstMap),
Errors = [Var - [InstA, InstB] | Errors1],
ModuleInfo = ModuleInfo1,
InstTable = InstTable1,
- MergeSubs = MergeSubs1
+ MergeInfo = MergeInfo1
).
:- pred instmap__merge_subs(instmap, instmap, instmap, inst_table, module_info,
--- mercury_to_mercury.m.bak2 Thu Feb 4 15:24:42 1999
+++ mercury_to_mercury.m Thu Feb 4 15:40:35 1999
@@ -847,10 +847,15 @@
mercury_output_tabs(Indent),
io__write_string(")\n")
).
-mercury_output_structured_inst_name(Expand, merge_inst(InstA, InstB), Indent,
- VarSet, InstMap, InstTable) -->
+mercury_output_structured_inst_name(Expand, merge_inst(Liveness, InstA, InstB),
+ Indent, VarSet, InstMap, InstTable) -->
mercury_output_tabs(Indent),
io__write_string("$merge_inst(\n"),
+ ( { Liveness = live } ->
+ io__write_string("live, ")
+ ;
+ io__write_string("dead, ")
+ ),
{ Indent1 is Indent + 1 },
mercury_output_structured_inst_list(Expand, [InstA, InstB], Indent1,
VarSet, InstMap, InstTable),
@@ -983,8 +988,14 @@
InstTable),
io__write_string(")")
).
-mercury_output_inst_name(merge_inst(InstA, InstB), VarSet, InstTable) -->
+mercury_output_inst_name(merge_inst(Liveness, InstA, InstB), VarSet,
+ InstTable) -->
io__write_string("$merge_inst("),
+ ( { Liveness = live } ->
+ io__write_string("live, ")
+ ;
+ io__write_string("dead, ")
+ ),
mercury_output_inst_list(expand_noisily, [InstA, InstB], VarSet,
InstTable),
io__write_string(")").
--- mode_util.m.bak2 Thu Feb 4 15:24:32 1999
+++ mode_util.m Thu Feb 4 15:31:37 1999
@@ -510,9 +510,10 @@
;
Inst = defined_inst(InstName)
)
- ; InstName = merge_inst(A, B),
+ ; InstName = merge_inst(IsLive, A, B),
inst_table_get_merge_insts(InstTable, MergeInstTable),
- map__lookup(MergeInstTable, A - B, MaybeInst),
+ map__lookup(MergeInstTable, merge_inst_pair(IsLive, A, B),
+ MaybeInst),
( MaybeInst = known(Inst0) ->
Inst = Inst0
;
@@ -1198,8 +1199,8 @@
unify_inst(Live, InstA, InstB, Real)) :-
inst_apply_substitution(InstA0, Subst, InstA),
inst_apply_substitution(InstB0, Subst, InstB).
-inst_name_apply_substitution(merge_inst(InstA0, InstB0), Subst,
- merge_inst(InstA, InstB)) :-
+inst_name_apply_substitution(merge_inst(IsLive, InstA0, InstB0), Subst,
+ merge_inst(IsLive, InstA, InstB)) :-
inst_apply_substitution(InstA0, Subst, InstA),
inst_apply_substitution(InstB0, Subst, InstB).
inst_name_apply_substitution(ground_inst(Inst0, IsLive, Uniq, Real), Subst,
--- module_qual.m.bak2 Thu Feb 4 15:25:00 1999
+++ module_qual.m Thu Feb 4 15:31:54 1999
@@ -565,7 +565,7 @@
{ list__length(Insts0, Arity) },
find_unique_match(SymName0 - Arity, SymName - _,
InstIds, inst_id, Info1, Info).
-qualify_inst_name(merge_inst(_, _), _, _, _) -->
+qualify_inst_name(merge_inst(_, _, _), _, _, _) -->
{ error("compiler generated inst unexpected") }.
qualify_inst_name(unify_inst(_, _, _, _), _, _, _) -->
{ error("compiler generated inst unexpected") }.
--- prog_data.m.bak2 Thu Feb 4 14:52:11 1999
+++ prog_data.m Thu Feb 4 14:52:17 1999
@@ -516,7 +516,7 @@
:- type inst_name
---> user_inst(sym_name, list(inst))
- ; merge_inst(inst, inst)
+ ; merge_inst(is_live, inst, inst)
; unify_inst(is_live, inst, inst, unify_is_real)
; ground_inst(inst_name, is_live, uniqueness, unify_is_real)
; any_inst(inst_name, is_live, uniqueness, unify_is_real)
--
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