[m-rev.] [reuse] diff: bugfix: data-structure representation in reuse info
Nancy Mazur
Nancy.Mazur at cs.kuleuven.ac.be
Tue Feb 22 14:39:28 AEDT 2005
Hi,
sorry for this huge break, but slowly getting back to it...
Nancy
===================================================================
Estimated hours taken: 10
Branches: reuse
Bugfix!
According to the theory (phd Nancy), reuse condition information consists of
three types of information:
1. the datastructures approximating the memory cells that can
potentially be reused;
2. the datastructures that are definitely live at the reuse site;
3. the set of aliases to take into account at that reuse site.
We always approximated (2) by a set of variables, yet the implementation of
that approximation was wrong. Indeed, it is not enough to take all the local in
use information and project it on the headvars, it first has to be extended
w.r.t. the present aliasing information (cf theory phd Nancy). By using the
pure variable representation, the result of extending and then projecting
becomes a huge overestimation of what is actually in use at that reuse site,
hence resulting in stricter reuse conditions and thus an overall worse memory
reuse behavior. It therefore becomes mandatory to switch to a
datastructure-representation of the inuse-part of the reuse information.
This diff is therefore a bugfix (the in use information is now extended w.r.t.
aliasing before being projected) combined with an increase in the analysis
precision wrt that bugfix by conforming the analysis implementation to the
theory (phd Nancy): the in use part of the structure reuse is now represented
using data structures instead of pure variables.
As a consequence of this bugfix, the results obtained with the icfp-benchmark
are slightly worse (about 1-2% more memory cells are needed to run the
optimised code). Indeed, the bugfix adds more information to be taken
into account when verifying the safeness of some of the reuses, which means
that some reuses are now identified as unsafe instead of safe, hence less
overall reuses.
sr_data.m:
When computing the reuse information generated at a reuse site,
take into account the local in use information represented as data
structures instead of pure variables, and extend it using the local
aliases before projecting it onto the headvariables. This conforms to
the theory.
pa_alias.m:
pa_alias_as.m:
prog_io_pasr.m:
sr_dead.m:
sr_indirect.m:
sr_live.m:
All InUse information is now represented using data structures during
the analysis.
Changes supporting the main change in sr_data.
Index: pa_alias.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias.m,v
retrieving revision 1.1.2.22
diff -u -r1.1.2.22 pa_alias.m
--- pa_alias.m 30 Jun 2004 04:46:46 -0000 1.1.2.22
+++ pa_alias.m 22 Feb 2005 02:55:05 -0000
@@ -39,7 +39,11 @@
hlds_goal__unification::in, hlds_goal__hlds_goal_info::in,
list(alias)::out) is det.
-:- pred live_from_in_use(set(prog_var)::in, list(alias)::in,
+ % In use information is stored as a set of datastructures. This
+ % procedure computes the set of live datastructure using the in-use set
+ % and extending it wrt the alias information.
+:- pred live_from_in_use(module_info::in, proc_info::in,
+ set(datastruct)::in, list(alias)::in,
live_set::out) is det.
:- pred live_from_live0(module_info::in, proc_info::in,
@@ -60,7 +64,6 @@
:- import_module varset, require, int, map, std_util, string.
%-------------------------------------------------------------------%
-% parsing routines
%-------------------------------------------------------------------%
% contains_one_of_vars(SET, ALIAS, DATA)
@@ -342,13 +345,15 @@
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
-live_from_in_use(InUse, Aliases, Live):-
+live_from_in_use(ModuleInfo, ProcInfo, InUse, Aliases, Live):-
% filter the list of aliases, keeping only the ones that
% involve at least one variable from the IN_USE set
- list__filter_map(
- pa_alias__contains_one_of_vars(InUse),
+ set__to_sorted_list(InUse, InUseList),
+ list__map(
+ pa_alias__one_of_vars_is_live(ModuleInfo, ProcInfo, InUseList),
Aliases,
- Datastructs),
+ DatastructsLists),
+ list__condense(DatastructsLists, Datastructs),
sr_live__from_datastructs(Datastructs, Live).
live_from_live0(ModuleInfo, ProcInfo, Live0, Aliases, Live):-
Index: pa_alias_as.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias_as.m,v
retrieving revision 1.1.2.44
diff -u -r1.1.2.44 pa_alias_as.m
--- pa_alias_as.m 30 Jul 2004 03:47:42 -0000 1.1.2.44
+++ pa_alias_as.m 22 Feb 2005 02:55:06 -0000
@@ -215,7 +215,7 @@
% Compute the (sr_live__)live-set Live based on an initial InUse set,
% an initial Live0 set, and a list of aliases Alias.
:- pred live(module_info::in, proc_info::in,
- set(prog_var)::in, live_set::in, alias_as::in,
+ set(datastruct)::in, live_set::in, alias_as::in,
sr_live__live_set::out) is det.
% :- func live(module_info, proc_info,
@@ -918,7 +918,7 @@
% AS bottom?
is_bottom(AS)
->
- sr_live__init(IN_USE, LIVE_1),
+ sr_live__from_datastructs_set(IN_USE, LIVE_1),
sr_live__union([LIVE_1, LIVE_0], LIVE)
;
@@ -934,7 +934,7 @@
% live_2(IN_USE, Aliases, Liveset)
% pre-condition: IN_USE is not empty
-:- pred live_2(module_info, proc_info, set(prog_var),sr_live__live_set,
+:- pred live_2(module_info, proc_info, set(datastruct), sr_live__live_set,
list(prog_data__alias), sr_live__live_set).
:- mode live_2(in, in, in, in, in, out) is det.
@@ -964,10 +964,11 @@
LIVE0 = LIVE_0,
% (LIVE1)
- sr_live__init(IN_USE, LIVE1),
+ from_datastructs_set(IN_USE, LIVE1),
% (LIVE2)
- pa_alias__live_from_in_use(IN_USE, ALIASES, LIVE2),
+ pa_alias__live_from_in_use(ModuleInfo, ProcInfo,
+ IN_USE, ALIASES, LIVE2),
% (LIVE3)
pa_alias__live_from_live0(ModuleInfo, ProcInfo,
Index: prog_io_pasr.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/prog_io_pasr.m,v
retrieving revision 1.1.2.6
diff -u -r1.1.2.6 prog_io_pasr.m
--- prog_io_pasr.m 29 Jul 2004 02:00:00 -0000 1.1.2.6
+++ prog_io_pasr.m 22 Feb 2005 02:55:07 -0000
@@ -301,8 +301,6 @@
print_reuse_tuple(ProgVarSet, TVarSet, conditional(Nodes, LUiH, LAiH), !IO) :-
set__to_sorted_list(Nodes, NodesList),
set__to_sorted_list(LUiH, ListLUiH),
- ListLUiHVars = list__map(
- (func(D) = V :- V = D ^ sc_var), ListLUiH),
io__write_string("condition(", !IO),
% write out the list of headvar-nodes involved
@@ -311,9 +309,10 @@
print_datastruct(ProgVarSet, TVarSet), !IO),
io__write_string("], ", !IO),
- % write out LUiH, list of prog_vars
+ % write out LUiH, list of datastructs
io__write_string("[", !IO),
- mercury_output_vars(ListLUiHVars, ProgVarSet, bool__no, !IO),
+ io__write_list(ListLUiH, ",",
+ print_datastruct(ProgVarSet, TVarSet), !IO),
io__write_string("], ", !IO),
% write out LAiH, the aliases at the reuse-point
@@ -705,13 +704,11 @@
->
nodes_parse(NodesTerm, NodesList),
set__list_to_set(NodesList, Nodes),
- vars_parse(LUiHTerm, LUiH),
- LUiHData = set__map(
- (func(V) = selected_cel(V,[])),
- LUiH),
+ nodes_parse(LUiHTerm, LUiHList),
+ set__list_to_set(LUiHList, LUiH),
parse_aliases_domain(LAiHTerm,
LAiH),
- ReuseTuple = conditional(Nodes, LUiHData, LAiH)
+ ReuseTuple = conditional(Nodes, LUiH, LAiH)
;
list__length(Args, L),
string__int_to_string(L, LS),
Index: sr_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_data.m,v
retrieving revision 1.1.2.34
diff -u -r1.1.2.34 sr_data.m
--- sr_data.m 30 Jul 2004 03:47:43 -0000 1.1.2.34
+++ sr_data.m 22 Feb 2005 02:55:10 -0000
@@ -101,8 +101,18 @@
---> always
; condition(
nodes :: set(datastruct),
- local_use_headvars :: set(prog_var),
+ % A description of the node that is reused if the
+ % reuse is allowed. Given the existence of possible
+ % aliases, the single node may be translated into a set
+ % of nodes.
+ local_use_headvars :: set(datastruct),
+ % A description of the nodes that are inherently live
+ % at the site of the last deconstruction of the
+ % structure to be reused.
local_alias_headvars :: alias_as
+ % A description of the existing aliases at the site of
+ % the last deconstruction of the structure to be
+ % reused.
).
@@ -251,9 +261,8 @@
Condition = always,
Tuple = unconditional
;
- Condition = condition(Nodes, LocalUse, AliasAs),
+ Condition = condition(Nodes, LocalUseData, AliasAs),
from_alias_as_to_aliases_domain(AliasAs, AliasesDomain),
- LocalUseData = set__map(pa_datastruct__init, LocalUse),
Tuple = conditional(Nodes, LocalUseData, AliasesDomain)
).
from_reuse_tuple_to_reuse_condition(Tuple, Condition) :-
@@ -263,10 +272,7 @@
;
Tuple = conditional(Nodes, LocalUseData, AliasesDomain),
from_aliases_domain_to_alias_as(AliasesDomain, AliasAs),
- LocalUse = set__map(
- (func(D) = V :-
- V = D ^ sc_var), LocalUseData),
- Condition = condition(Nodes, LocalUse, AliasAs)
+ Condition = condition(Nodes, LocalUseData, AliasAs)
).
from_memo_reuse_to_maybe_reuse_typles(no, no).
from_memo_reuse_to_maybe_reuse_typles(yes(Conditions), yes(Tuples)):-
@@ -378,9 +384,10 @@
% headvariables.
% XXX Thus: WRONG here!!
set__intersect(LUi, HVsSet, LUiHVs),
+ LUiHVsData = set__map(pa_datastruct__init, LUiHVs),
pa_alias_as__project(HVs, ALIASi, LAiHVs),
set__list_to_set(Nodes, Nodes_set),
- Condition = condition(Nodes_set, LUiHVs, LAiHVs)
+ Condition = condition(Nodes_set, LUiHVsData, LAiHVs)
).
reuse_condition_rename(Dict, MaybeSubst, Cin, Cout) :-
@@ -393,16 +400,16 @@
pa_datastruct__rename(Dict, MaybeSubst),
NodesList,
RenNodesList),
- % rename the datastructures
+ set__list_to_set(RenNodesList, RenNodes),
+ % rename the datastructures in use:
set__to_sorted_list(LUiH, ListLUiH),
list__map(
- map__lookup(Dict),
+ pa_datastruct__rename(Dict, MaybeSubst),
ListLUiH,
ListRenLUiH),
set__list_to_set(ListRenLUiH, RenLUiH),
% rename the alias
pa_alias_as__rename(Dict, MaybeSubst, LAiH, RenLAiH),
- set__list_to_set(RenNodesList, RenNodes),
Cout = condition(RenNodes, RenLUiH, RenLAiH)
;
Cout = Cin
@@ -478,10 +485,27 @@
pa_alias_as__normalize(HLDS, ProcInfo, InstMap0,
NEW_LAiH0, NEW_LAiH),
+ % collect the datastructs in use part of the reuse condition:
+ % 1. collect all the in use information (as datastructs!);
+ % 2. extend wrt the local aliases;
+ % 3. project on the headvars;
set__union(LFUi, LBUi, LUi),
- set__union(LUi, OLD_LUiH, NEW_LUi),
- set__list_to_set(HVs, HVsSet),
- set__intersect(NEW_LUi, HVsSet, NEW_LUiH),
+ LUi_data = set__map(pa_datastruct__init, LUi),
+ set__union(LUi_data, OLD_LUiH, NEW_LUi_data),
+ set__to_sorted_list(NEW_LUi_data, NEW_LUi_data_list),
+ list__map(
+ pred(TopCell::in, AliasedCells::out) is det :-
+ (pa_alias_as__collect_aliases_of_datastruct(HLDS,
+ ProcInfo, TopCell, NewALIASi, AliasedCells)),
+ NEW_LUi_data_list, ListAliasedCells),
+ list__condense([NEW_LUi_data_list | ListAliasedCells],
+ Extended_LUi_list),
+ list__filter(
+ pred(Data::in) is semidet :-
+ (list__member(Data^sc_var, HVs)),
+ Extended_LUi_list, Extended_LUiHvs_list),
+ set__list_to_set(Extended_LUiHvs_list, NEW_LUiH),
+
set__list_to_set(NORM_NODES, NORM_NODES_set),
CONDITION = condition(NORM_NODES_set, NEW_LUiH, NEW_LAiH)
).
Index: sr_dead.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_dead.m,v
retrieving revision 1.1.2.27
diff -u -r1.1.2.27 sr_dead.m
--- sr_dead.m 30 Jul 2004 03:47:43 -0000 1.1.2.27
+++ sr_dead.m 22 Feb 2005 02:55:10 -0000
@@ -37,6 +37,7 @@
:- import_module hlds__hlds_goal.
:- import_module parse_tree__prog_data.
:- import_module possible_alias__pa_alias_as.
+:- import_module possible_alias__pa_datastruct.
:- import_module possible_alias__pa_run.
:- import_module structure_reuse__sr_live.
@@ -166,8 +167,9 @@
list__length(Vars) = 0
;
set__union(LFU, LBU, LU),
+ LU_data = set__map(pa_datastruct__init, LU),
sr_live__init(Live0),
- pa_alias_as__live(ModuleInfo, ProcInfo, LU,
+ pa_alias_as__live(ModuleInfo, ProcInfo, LU_data,
Live0, Alias0, Live),
sr_live__is_live(Var, Live)
;
Index: sr_indirect.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_indirect.m,v
retrieving revision 1.1.2.36
diff -u -r1.1.2.36 sr_indirect.m
--- sr_indirect.m 28 Jul 2004 02:31:59 -0000 1.1.2.36
+++ sr_indirect.m 22 Feb 2005 02:55:11 -0000
@@ -568,7 +568,9 @@
goal_info_get_lfu(Info0, LFUi),
goal_info_get_lbu(Info0, LBUi),
set__union(LFUi, LBUi, LUi),
- pa_alias_as__live(HLDS, ProcInfo, LUi, LIVE0, Alias0, Live_i),
+ LUiData = set__map(pa_datastruct__init, LUi),
+ pa_alias_as__live(HLDS, ProcInfo, LUiData,
+ LIVE0, Alias0, Live_i),
% 3.b. project the live-set to the actual vars:
sr_live__project(ActualVars, Live_i, ActualLive_i),
% 4. project the aliases to the actual vars
@@ -650,9 +652,11 @@
sr_live__init(DummyLive),
pa_alias_as__init(BottomAlias),
pa_alias_as__live(ModuleInfo, ProcInfo,
- LFU, DummyLive, BottomAlias, LFU_Live),
+ set__map(pa_datastruct__init, LFU),
+ DummyLive, BottomAlias, LFU_Live),
pa_alias_as__live(ModuleInfo, ProcInfo,
- LBU, DummyLive, BottomAlias, LBU_Live),
+ set__map(pa_datastruct__init, LBU),
+ DummyLive, BottomAlias, LBU_Live),
Condition = condition(Nodes, _LU, _LA),
%
NodesL = set__to_sorted_list(Nodes),
Index: sr_live.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_live.m,v
retrieving revision 1.1.2.7
diff -u -r1.1.2.7 sr_live.m
--- sr_live.m 11 Jun 2004 02:56:55 -0000 1.1.2.7
+++ sr_live.m 22 Feb 2005 02:55:11 -0000
@@ -37,6 +37,9 @@
:- pred from_datastructs(list(prog_data__datastruct), live_set).
:- mode from_datastructs(in, out) is det.
+:- pred from_datastructs_set(set(prog_data__datastruct), live_set).
+:- mode from_datastructs_set(in, out) is det.
+
:- pred bottom(live_set).
:- mode bottom(out) is det.
:- mode bottom(in) is semidet.
@@ -88,9 +91,13 @@
set__to_sorted_list(LiveSet,LiveList),
live_wrap(LiveList, LIVE).
-from_datastructs(DATASTRUCTS, LIVE) :-
+from_datastructs(Datastructs, Live) :-
% check whether minimal !!
- live_wrap(DATASTRUCTS, LIVE).
+ live_wrap(Datastructs, Live).
+
+from_datastructs_set(Datastructs, Live) :-
+ set__to_sorted_list(Datastructs, List),
+ from_datastructs(List, Live).
:- func func_datastruct_init(prog_var) = prog_data__datastruct.
:- mode func_datastruct_init(in) = out is det.
--
nancy.mazur at cs.kuleuven.ac.be ------------ Katholieke Universiteit Leuven -
tel: +32-16-327596 - fax: +32-16-327996 ------- Dept. of Computer Science -
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list