[m-dev.] for review: correct aliasing in args of compiler generated procedures
David Overton
dmo at cs.mu.OZ.AU
Fri Oct 8 23:51:26 AEST 1999
Hi,
This is for Simon Taylor to review, please.
David
Estimated hours taken: 10
Fix up the predicates that create procedures during mode analysis and later
phases so that they correctly handle aliasing in the procedure's arguments.
compiler/inst_util.m:
Move count_inst_keys_in_inst from instmap.m to here.
Add new predicate normalise_inst_keys_in_insts which takes a list of
insts and ``normalises'' their inst keys. It does this by first
removing any alias insts with singleton inst_keys and then expanding
all instmap alias substitutions so that they insts no longer depend on
the instmap.
compiler/modecheck_call.m:
In insert_new_mode, call normalise_inst_keys_in_insts to make sure
all the inst_keys_are correct.
Also, call normalise_insts after normalise_inst_keys_in_insts,
instead of in get_var_insts_and_lives because we only want to normalise
the insts after we have normalised the inst_keys.
compiler/hlds_pred.m:
In compute_arg_modes, which is called by hlds_pred__define_new_pred,
call normalise_inst_keys_in_insts to make sure all the inst_keys are
correct.
compiler/mode_util.m:
In normalise_inst, do not normalise unique insts if they contain
aliases. This is because removing the aliases may cause the insts
to become shared.
compiler/instmap.m:
Move the uniq_count type and predicates which operate on it to a new
module, uniq_count.m.
Move count_inst_keys_in_inst to inst_util.m.
Export instmap__expand_alias_substitutions and
instmap__remove_singleton_inst_key_from_inst.
Add a new predicate instmap__find_latest_inst_key.
compiler/uniq_count.m:
New module containing the uniq_count type extracted from instmap.m.
compiler/inst_match.m:
Add new predicate inst_contains_aliases.
Index: hlds_pred.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_pred.m,v
retrieving revision 1.35.4.25
diff -u -r1.35.4.25 hlds_pred.m
--- hlds_pred.m 1999/08/27 00:30:17 1.35.4.25
+++ hlds_pred.m 1999/10/08 10:01:00
@@ -20,7 +20,7 @@
:- implementation.
:- import_module code_aux, goal_util, make_hlds, prog_util.
-:- import_module mode_util, type_util, options.
+:- import_module inst_util, mode_util, type_util, options.
:- import_module int, string, require, assoc_list.
%-----------------------------------------------------------------------------%
@@ -1266,13 +1266,14 @@
hlds_pred__define_new_pred(Goal0, Goal, ArgVars0, ExtraTypeInfos, InstMap0,
PredName, TVarSet, VarTypes0, ClassContext, TVarMap, TCVarMap,
- VarSet0, Markers, Owner, IsAddressTaken, InstTable,
+ VarSet0, Markers, Owner, IsAddressTaken, InstTable0,
ModuleInfo0, ModuleInfo, PredProcId) :-
Goal0 = _GoalExpr - GoalInfo,
goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
instmap__apply_instmap_delta(InstMap0, InstMapDelta, InstMap),
- compute_arg_modes(ArgVars0, InstMap0, InstMap, ArgModes),
+ compute_arg_modes(ModuleInfo0, ArgVars0, InstMap0, InstMap, ArgModes,
+ InstTable0, InstTable),
hlds_pred__define_new_pred(Goal0, Goal, ArgVars0, ExtraTypeInfos,
InstMap0, ArgModes, PredName, TVarSet, VarTypes0,
ClassContext, TVarMap, TCVarMap, VarSet0, Markers,
@@ -1358,15 +1359,20 @@
Goal = GoalExpr - GoalInfo,
PredProcId = proc(PredId, ProcId).
-:- pred compute_arg_modes(list(prog_var)::in, instmap::in, instmap::in,
- list(mode)::out) is det.
+:- pred compute_arg_modes(module_info::in, list(prog_var)::in, instmap::in,
+ instmap::in, list(mode)::out, inst_table::in, inst_table::out) is det.
-compute_arg_modes([], _, _, []).
-compute_arg_modes([Var | Vars], InstMap0, InstMap, [Mode | Modes]) :-
- instmap__lookup_var(InstMap0, Var, Inst0),
- instmap__lookup_var(InstMap, Var, Inst),
- Mode = (Inst0 -> Inst),
- compute_arg_modes(Vars, InstMap0, InstMap, Modes).
+compute_arg_modes(ModuleInfo, Vars, InitialInstMap, FinalInstMap, Modes,
+ InstTable0, InstTable) :-
+ instmap__lookup_vars(Vars, InitialInstMap, InitialInsts0),
+ normalise_inst_keys_in_insts(InitialInstMap, ModuleInfo, InitialInsts0,
+ InitialInsts, InstTable0, InstTable1),
+
+ instmap__lookup_vars(Vars, FinalInstMap, FinalInsts0),
+ normalise_inst_keys_in_insts(FinalInstMap, ModuleInfo, FinalInsts0,
+ FinalInsts, InstTable1, InstTable),
+
+ inst_lists_to_mode_list(InitialInsts, FinalInsts, Modes).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
Index: inst_match.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/inst_match.m,v
retrieving revision 1.34.2.15
diff -u -r1.34.2.15 inst_match.m
--- inst_match.m 1999/07/28 05:36:38 1.34.2.15
+++ inst_match.m 1999/10/08 13:19:18
@@ -293,6 +293,10 @@
inst_key).
:- mode inst_contains_inst_key(in, in, in, in, in) is semidet.
+ % Succeed iff the specified inst contains any alias insts.
+:- pred inst_contains_aliases(inst, inst_table, module_info).
+:- mode inst_contains_aliases(in, in, in) is semidet.
+
% Nondeterministically produce all the inst_vars contained
% in the specified list of modes.
@@ -1628,6 +1632,31 @@
list__member(Inst, Insts),
inst_contains_inst_key_2(InstMap, InstTable, ModuleInfo, Expansions,
Inst, Key).
+
+%-----------------------------------------------------------------------------%
+
+inst_contains_aliases(Inst, InstTable, ModuleInfo) :-
+ set__init(Expansions),
+ inst_contains_aliases_2(Inst, InstTable, ModuleInfo, Expansions).
+
+:- pred inst_contains_aliases_2(inst, inst_table, module_info, set(inst_name)).
+:- mode inst_contains_aliases_2(in, in, in, in) is semidet.
+
+inst_contains_aliases_2(alias(_), _, _, _).
+inst_contains_aliases_2(bound(_, BIs), InstTable, ModuleInfo, Expansions) :-
+ list__member(functor(_, Insts), BIs),
+ list__member(Inst, Insts),
+ inst_contains_aliases_2(Inst, InstTable, ModuleInfo, Expansions).
+inst_contains_aliases_2(abstract_inst(_, Insts), InstTable, ModuleInfo,
+ Expansions) :-
+ list__member(Inst, Insts),
+ inst_contains_aliases_2(Inst, InstTable, ModuleInfo, Expansions).
+inst_contains_aliases_2(defined_inst(InstName), InstTable, ModuleInfo,
+ Expansions0) :-
+ \+ set__member(InstName, Expansions0),
+ set__insert(Expansions0, InstName, Expansions),
+ inst_lookup(InstTable, ModuleInfo, InstName, Inst),
+ inst_contains_aliases_2(Inst, InstTable, ModuleInfo, Expansions).
%-----------------------------------------------------------------------------%
Index: inst_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/inst_util.m,v
retrieving revision 1.3.2.21
diff -u -r1.3.2.21 inst_util.m
--- inst_util.m 1999/07/28 05:36:39 1.3.2.21
+++ inst_util.m 1999/10/08 11:54:49
@@ -179,7 +179,31 @@
inst_fold_merge_pred, in, in, out) is det.
%-----------------------------------------------------------------------------%
+
+:- import_module uniq_count.
+
+:- type inst_key_counts == uniq_counts(inst_key).
+
+ % Count the occurrences of each inst_key in an inst.
+:- pred count_inst_keys_in_inst(instmap, inst_table, module_info,
+ inst, inst_key_counts, inst_key_counts).
+:- mode count_inst_keys_in_inst(in, in, in, in, in, out) is det.
+
+ % Count the occurrences of each inst_key in a list of insts.
+:- pred count_inst_keys_in_insts(instmap, inst_table, module_info,
+ list(inst), inst_key_counts).
+:- mode count_inst_keys_in_insts(in, in, in, in, out) is det.
+
+ % ``Normalise'' the inst_keys in a list of insts. This is done
+ % by first removing any alias insts with singleton inst_keys and
+ % then expanding all instmap alias substitutions so they no longer
+ % depend on the instmap.
+:- pred normalise_inst_keys_in_insts(instmap, module_info,
+ list(inst), list(inst), inst_table, inst_table).
+:- mode normalise_inst_keys_in_insts(in, in, in, out, in, out) is det.
+
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
:- implementation.
:- import_module hlds_data, inst_match, mode_util, det_analysis.
@@ -2480,6 +2504,69 @@
Merge, abstract_inst(_, Insts)) -->
list__foldl(inst_fold_2(InstMap, InstTable, ModuleInfo, Recursive,
Before, After, Merge), Insts).
+
+%-----------------------------------------------------------------------------%
+
+count_inst_keys_in_inst(InstMap, InstTable, ModuleInfo, Inst) -->
+ { set__init(SeenTwice) },
+ count_inst_keys_in_inst(no, InstMap, InstTable, ModuleInfo,
+ SeenTwice, Inst).
+
+count_inst_keys_in_insts(InstMap, InstTable, ModuleInfo, Insts, Count) :-
+ map__init(Count0),
+ list__foldl(count_inst_keys_in_inst(InstMap, InstTable, ModuleInfo),
+ Insts, Count0, Count).
+
+:- pred count_inst_keys_in_inst(bool, instmap, inst_table, module_info,
+ set(inst_name), inst, inst_key_counts, inst_key_counts).
+:- mode count_inst_keys_in_inst(in, in, in, in, in, in, in, out)
+ is det.
+
+count_inst_keys_in_inst(SetCountMany, InstMap, InstTable, ModuleInfo,
+ SeenTwice, Inst) -->
+ inst_fold(InstMap, InstTable, ModuleInfo,
+ count_inst_keys_before(SetCountMany, InstMap),
+ count_inst_keys_after(InstMap, InstTable, ModuleInfo, SeenTwice),
+ uniq_counts_max_merge, Inst).
+
+:- pred count_inst_keys_before(bool::in, instmap::in, (inst)::in,
+ set(inst_name)::in, inst_key_counts::in, inst_key_counts::out)
+ is semidet.
+
+count_inst_keys_before(SetCountMany, InstMap, alias(Key0), _) -->
+ { instmap__find_latest_inst_key(InstMap, Key0, 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,
+ 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.
+ count_inst_keys_in_inst(yes, InstMap, InstTable, ModuleInfo,
+ SeenTwice, defined_inst(InstName)).
+
+normalise_inst_keys_in_insts(InstMap, ModuleInfo, Insts0, Insts, InstTable0,
+ InstTable) :-
+ count_inst_keys_in_insts(InstMap, InstTable0, ModuleInfo, Insts0,
+ IKCounts),
+ list__map(instmap__remove_singleton_inst_key_from_inst(IKCounts,
+ ModuleInfo, InstTable0, InstMap), Insts0, Insts1),
+ instmap__expand_alias_substitutions(InstMap, ModuleInfo, Insts1,
+ Insts, InstTable0, InstTable).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
Index: instmap.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/instmap.m,v
retrieving revision 1.15.2.23
diff -u -r1.15.2.23 instmap.m
--- instmap.m 1999/07/28 05:36:41 1.15.2.23
+++ instmap.m 1999/10/08 09:25:35
@@ -20,7 +20,7 @@
:- interface.
:- import_module hlds_module, prog_data, mode_info, (inst), mode_errors.
-:- import_module hlds_data, inst_table.
+:- import_module hlds_data, inst_table, inst_util.
:- import_module map, bool, set, list, assoc_list, std_util.
@@ -276,8 +276,22 @@
inst).
:- mode instmap__inst_key_table_lookup(in, in, in, out) is det.
+ % Remove all dependencies on instmap alias substitutions from the
+ % list of insts.
+:- pred instmap__expand_alias_substitutions(instmap, module_info, list(inst),
+ list(inst), inst_table, inst_table).
+:- mode instmap__expand_alias_substitutions(in, in, in, out, in, out) is det.
+
+:- 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.
+
%-----------------------------------------------------------------------------%
+:- pred instmap__find_latest_inst_key(instmap, inst_key, inst_key).
+:- mode instmap__find_latest_inst_key(in, in, out) is det.
+
:- pred instmap__inst_keys_are_equivalent(inst_key, instmap, inst_key, instmap).
:- mode instmap__inst_keys_are_equivalent(in, in, in, in) is semidet.
@@ -295,7 +309,7 @@
:- implementation.
:- import_module mode_util, inst_match, prog_data, goal_util.
-:- import_module hlds_data, inst_util, term.
+:- import_module hlds_data, uniq_count, term.
:- import_module std_util, require, multi_map, set_bbbtree, string.
@@ -448,12 +462,12 @@
instmap__set_vars(_, [], [_ | _], _) :-
error("instmap__set_vars").
-:- pred find_latest_inst_key(inst_key_sub, inst_key, inst_key).
-:- mode find_latest_inst_key(in, in, out) is det.
+:- pred find_latest_inst_key_from_sub(inst_key_sub, inst_key, inst_key).
+:- mode find_latest_inst_key_from_sub(in, in, out) is det.
-find_latest_inst_key(Sub, IK0, IK) :-
+find_latest_inst_key_from_sub(Sub, IK0, IK) :-
( map__search(Sub, IK0, IK1) ->
- find_latest_inst_key(Sub, IK1, IK)
+ find_latest_inst_key_from_sub(Sub, IK1, IK)
;
IK = IK0
).
@@ -461,8 +475,8 @@
instmap__add_alias(unreachable, _, _, unreachable).
instmap__add_alias(reachable(Fwd, Alias0), From0, To0, reachable(Fwd, Alias)) :-
% XXX Do we need to path compress the alias map here?
- find_latest_inst_key(Alias0, From0, From),
- find_latest_inst_key(Alias0, To0, To),
+ find_latest_inst_key_from_sub(Alias0, From0, From),
+ find_latest_inst_key_from_sub(Alias0, To0, To),
map__det_insert(Alias0, From, To, Alias).
instmap__set(unreachable, _Var, _Inst, unreachable).
@@ -621,108 +635,6 @@
%-----------------------------------------------------------------------------%
-:- interface.
-
-% Export this stuff for use in inst_util.m.
-
-:- type uniq_count
- ---> known(int)
- ; 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 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.
-
-:- 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 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.
-
-:- 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.
-
-:- import_module int.
-
-inc_uniq_count(Item, Map0, Map) :-
- ( map__search(Map0, Item, C0) ->
- (
- C0 = known(N),
- map__det_update(Map0, Item, known(N + 1), Map)
- ;
- C0 = many,
- Map = Map0
- )
- ;
- map__det_insert(Map0, Item, known(1), 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 = known(0).
-
-has_count_one(Map, Item) :-
- map__search(Map, Item, known(1)).
-
-has_count_many(Map, Item) :-
- 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(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,
- ( 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__count_inst_keys(Vars, InstMaps, InstTable, SeenKeys,
% DuplicateKeys, InstKeys):
% Return a set of all inst_keys which appear more than
@@ -754,51 +666,8 @@
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(no, InstMap, InstTable, ModuleInfo,
- SeenTwice, Inst),
+ count_inst_keys_in_inst(InstMap, InstTable, ModuleInfo, Inst),
instmap__count_inst_keys_2(Vs, ModuleInfo, InstTable, InstMap).
-
-:- 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, in, out)
- is det.
-
-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(bool::in, (inst)::in, set(inst_name)::in,
- inst_key_counts::in, inst_key_counts::out) is semidet.
-
-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,
- 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(yes, InstMap, InstTable, ModuleInfo,
- SeenTwice, defined_inst(InstName)).
-
%-----------------------------------------------------------------------------%
% instmap__merge_2(Vars, Liveness, InstMaps, ModuleInfo, ErrorList):
@@ -972,17 +841,49 @@
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,
+ instmap__expand_inst_sub(yes(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,
+instmap__expand_alias_substitutions(unreachable, _, Insts, Insts) --> [].
+instmap__expand_alias_substitutions(reachable(_, Sub), ModuleInfo, Insts0,
+ Insts) -->
+ ( { map__is_empty(Sub) } ->
+ % Optimise this case.
+ { Insts = Insts0 }
+ ;
+ { map__init(SeenIKs0) },
+ instmap__expand_alias_substitutions_2(ModuleInfo, Sub, SeenIKs0,
+ Insts0, Insts)
+ ).
+
+:- pred instmap__expand_alias_substitutions_2(module_info, inst_key_sub,
+ inst_key_sub, list(inst), list(inst), inst_table, inst_table).
+:- mode instmap__expand_alias_substitutions_2(in, in, in, in, out, in, out)
+ is det.
+
+instmap__expand_alias_substitutions_2(_, _, _, [], []) --> [].
+instmap__expand_alias_substitutions_2(ModuleInfo, Sub, SeenIKs0,
+ [Inst0 | Insts0], [Inst | Insts]) -->
+ instmap__expand_inst_sub(no, ModuleInfo, Sub, SeenIKs0, SeenIKs1,
+ Inst0, Inst),
+ instmap__expand_alias_substitutions_2(ModuleInfo, Sub, SeenIKs1,
+ Insts0, Insts).
+
+ % instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeekIKs0,
+ % SeenIKs, Inst0, Inst, InstTable0, InstTable)
+ % Expand alias substitutions in Inst0.
+ % If MaybeKeys = yes(Keys) then only expand inst_keys that
+ % are members of Keys. Otherwise, expand all inst_keys that
+ % have substitutions on them.
+
+:- pred instmap__expand_inst_sub(maybe(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,
+instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
alias(IK0), Inst, InstTable0, InstTable) :-
( map__search(SeenIKs0, IK0, IK1) ->
% We have seen IK0 before and replaced it with IK1.
@@ -991,11 +892,12 @@
InstTable = InstTable0
; map__search(Sub, IK0, IK1) ->
% IK0 has a substitution so recursively expand it.
- instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+ instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0,
SeenIKs1, alias(IK1), Inst1, InstTable0, InstTable),
(
Inst1 = alias(IK1),
- \+ set_bbbtree__member(IK0, Keys)
+ MaybeKeys = yes(KeysToExpand),
+ \+ set_bbbtree__member(IK0, KeysToExpand)
->
Inst = alias(IK0),
map__det_insert(SeenIKs1, IK0, IK0, SeenIKs)
@@ -1010,7 +912,7 @@
;
inst_table_get_inst_key_table(InstTable0, IKT0),
inst_key_table_lookup(IKT0, IK0, Inst0),
- instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+ instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0,
SeenIKs1, Inst0, Inst1, InstTable0, InstTable1),
( Inst0 = Inst1 ->
Inst = alias(IK0),
@@ -1038,17 +940,17 @@
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,
+instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
bound(U, BoundInsts0), bound(U, BoundInsts),
InstTable0, InstTable) :-
- instmap__expand_bound_insts_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+ instmap__expand_bound_insts_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0,
SeenIKs, BoundInsts0, BoundInsts, InstTable0, InstTable).
-instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+instmap__expand_inst_sub(MaybeKeys, 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,
+ instmap__expand_inst_list_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0,
+ SeenIKs, Insts0, Insts, InstTable0, InstTable).
+instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
defined_inst(InstName), Inst, InstTable0, InstTable) :-
inst_table_get_other_insts(InstTable0, OtherInsts0),
other_inst_table_mark_inst_name(OtherInsts0, InstName, NewInstName),
@@ -1070,7 +972,7 @@
% 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,
+ instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0,
SeenIKs, Inst1, Inst2, InstTable1, InstTable2),
% Update the substitution_inst_table with the known value.
@@ -1097,7 +999,7 @@
Inst = Inst2
).
-:- pred instmap__expand_bound_insts_sub(inst_key_set, module_info,
+:- pred instmap__expand_bound_insts_sub(maybe(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)
@@ -1105,16 +1007,16 @@
instmap__expand_bound_insts_sub(_, _, _, SeenIKs, SeenIKs, [], [],
InstTable, InstTable).
-instmap__expand_bound_insts_sub(Keys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
+instmap__expand_bound_insts_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0, SeenIKs,
[functor(ConsId, Insts0) | BoundInsts0],
[functor(ConsId, Insts) | BoundInsts], InstTable0, InstTable) :-
- instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub,
+ instmap__expand_inst_list_sub(MaybeKeys, ModuleInfo, Sub,
SeenIKs0, SeenIKs1, Insts0, Insts, InstTable0, InstTable1),
- instmap__expand_bound_insts_sub(Keys, ModuleInfo, Sub,
+ instmap__expand_bound_insts_sub(MaybeKeys, ModuleInfo, Sub,
SeenIKs1, SeenIKs, BoundInsts0, BoundInsts,
InstTable1, InstTable).
-:- pred instmap__expand_inst_list_sub(inst_key_set, module_info,
+:- pred instmap__expand_inst_list_sub(maybe(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)
@@ -1122,12 +1024,12 @@
instmap__expand_inst_list_sub(_, _, _, SeenIKs, SeenIKs, [], [],
InstTable, InstTable).
-instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub,
+instmap__expand_inst_list_sub(MaybeKeys, ModuleInfo, Sub,
SeenIKs0, SeenIKs, [Inst0 | Insts0], [Inst | Insts],
InstTable0, InstTable) :-
- instmap__expand_inst_sub(Keys, ModuleInfo, Sub, SeenIKs0,
+ instmap__expand_inst_sub(MaybeKeys, ModuleInfo, Sub, SeenIKs0,
SeenIKs1, Inst0, Inst, InstTable0, InstTable1),
- instmap__expand_inst_list_sub(Keys, ModuleInfo, Sub,
+ instmap__expand_inst_list_sub(MaybeKeys, ModuleInfo, Sub,
SeenIKs1, SeenIKs, Insts0, Insts, InstTable1, InstTable).
%-----------------------------------------------------------------------------%
@@ -1154,11 +1056,6 @@
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) ->
@@ -1519,21 +1416,25 @@
instmap__inst_key_table_lookup(unreachable, IKT, Key, Inst) :-
inst_key_table_lookup(IKT, Key, Inst).
instmap__inst_key_table_lookup(reachable(_, Alias), IKT, Key0, Inst) :-
- find_latest_inst_key(Alias, Key0, Key),
+ find_latest_inst_key_from_sub(Alias, Key0, Key),
inst_key_table_lookup(IKT, Key, Inst0),
inst_apply_sub(Alias, Inst0, Inst).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
+instmap__find_latest_inst_key(InstMap, IK0, IK) :-
+ instmap__get_inst_key_sub(InstMap, Sub),
+ find_latest_inst_key_from_sub(Sub, IK0, IK).
+
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)
+ find_latest_inst_key_from_sub(AliasMapA, KeyA, Key),
+ find_latest_inst_key_from_sub(AliasMapB, KeyB, Key)
).
%-----------------------------------------------------------------------------%
Index: mode_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mode_util.m,v
retrieving revision 1.99.2.31
diff -u -r1.99.2.31 mode_util.m
--- mode_util.m 1999/07/28 05:37:00 1.99.2.31
+++ mode_util.m 1999/10/08 13:09:14
@@ -2342,6 +2342,9 @@
(
inst_is_ground(Inst, InstMap, InstTable, ModuleInfo),
inst_is_unique(Inst, InstMap, InstTable, ModuleInfo),
+ % If a unique insts contains aliases then removing
+ % them may cause the inst to become shared.
+ \+ inst_contains_aliases(Inst, InstTable, ModuleInfo),
% don't infer unique modes for introduced type_infos
% arguments, because that leads to an increase
% in the number of inferred modes without any benefit
@@ -2352,6 +2355,9 @@
inst_is_ground(Inst, InstMap, InstTable, ModuleInfo),
inst_is_mostly_unique(Inst, InstMap, InstTable,
ModuleInfo),
+ % If a unique insts contains aliases then removing
+ % them may cause the inst to become shared.
+ \+ inst_contains_aliases(Inst, InstTable, ModuleInfo),
% don't infer unique modes for introduced type_infos
% arguments, because that leads to an increase
% in the number of inferred modes without any benefit
Index: modecheck_call.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/modecheck_call.m,v
retrieving revision 1.15.2.19
diff -u -r1.15.2.19 modecheck_call.m
--- modecheck_call.m 1999/08/27 00:30:49 1.15.2.19
+++ modecheck_call.m 1999/10/08 12:33:20
@@ -449,8 +449,18 @@
insert_new_mode(PredId, ArgVars, MaybeDet, ProcId, ModeInfo0, ModeInfo) :-
% figure out the values of all the variables we need to
% create a new mode for this predicate
- get_var_insts_and_lives(ArgVars, ModeInfo0, InitialInsts, ArgLives),
+ get_var_insts_and_lives(ArgVars, ModeInfo0, InitialInsts0, ArgLives),
mode_info_get_module_info(ModeInfo0, ModuleInfo0),
+ mode_info_get_inst_table(ModeInfo0, InstTable0),
+ mode_info_get_instmap(ModeInfo0, InstMap0),
+ mode_info_get_var_types(ModeInfo0, Types),
+ map__apply_to_list(ArgVars, Types, ArgTypes),
+
+ normalise_inst_keys_in_insts(InstMap0, ModuleInfo0, InitialInsts0,
+ InitialInsts1, InstTable0, InstTable),
+ normalise_insts(InitialInsts1, ArgTypes, InstMap0, InstTable,
+ ModuleInfo0, InitialInsts),
+
module_info_preds(ModuleInfo0, Preds0),
map__lookup(Preds0, PredId, PredInfo0),
pred_info_context(PredInfo0, Context),
@@ -464,8 +474,7 @@
% and insert it into the queue of requested procedures.
%
% create the new mode
- inst_table_init(ArgInstTable),
- unify_proc__request_proc(PredId, argument_modes(ArgInstTable, Modes),
+ unify_proc__request_proc(PredId, argument_modes(InstTable, Modes),
yes(ArgLives), MaybeDet, Context, ModuleInfo0, ProcId,
ModuleInfo),
@@ -486,10 +495,7 @@
mode_info_get_module_info(ModeInfo, ModuleInfo),
mode_info_get_instmap(ModeInfo, InstMap),
mode_info_get_inst_table(ModeInfo, InstTable),
- mode_info_get_var_types(ModeInfo, VarTypes),
- instmap__lookup_var(InstMap, Var, Inst0),
- map__lookup(VarTypes, Var, Type),
- normalise_inst(Inst0, Type, InstMap, InstTable, ModuleInfo, Inst),
+ instmap__lookup_var(InstMap, Var, Inst),
mode_info_var_is_live(ModeInfo, Var, IsLive0),
Index: uniq_count.m
===================================================================
RCS file: uniq_count.m
diff -N uniq_count.m
--- /dev/null Fri Oct 8 23:34:20 1999
+++ uniq_count.m Fri Oct 8 19:50:31 1999
@@ -0,0 +1,110 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 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.
+%-----------------------------------------------------------------------------%
+% File: uniq_count.m
+% Main author: dmo
+%
+% This module contains the uniq_count type and operations on it.
+%
+%-----------------------------------------------------------------------------%
+
+:- module uniq_count.
+:- interface.
+
+:- import_module map, int.
+
+:- type uniq_count
+ ---> known(int)
+ ; many.
+
+:- type uniq_counts(T) == map(T, uniq_count).
+
+:- pred inc_uniq_count(T, uniq_counts(T), uniq_counts(T)).
+:- mode inc_uniq_count(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.
+
+:- 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 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.
+
+:- 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.
+
+:- import_module int.
+
+inc_uniq_count(Item, Map0, Map) :-
+ ( map__search(Map0, Item, C0) ->
+ (
+ C0 = known(N),
+ map__det_update(Map0, Item, known(N + 1), Map)
+ ;
+ C0 = many,
+ Map = Map0
+ )
+ ;
+ map__det_insert(Map0, Item, known(1), 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 = known(0).
+
+has_count_one(Map, Item) :-
+ map__search(Map, Item, known(1)).
+
+has_count_many(Map, Item) :-
+ 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(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,
+ ( 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).
--
David Overton Department of Computer Science & Software Engineering
PhD Student The University of Melbourne, Australia
+61 3 9344 9159 http://www.cs.mu.oz.au/~dmo
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions: mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
More information about the developers
mailing list