[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