[m-rev.] for review: [CTGC] indirect reuse analysis.
Nancy Mazur
Nancy.Mazur at cs.kuleuven.ac.be
Thu May 18 22:13:47 AEST 2006
Hi,
anybody in for reviewing this bit?
Many thanks,
Nancy
===================================================================
Estimated hours taken: 10
Branches: main
Provide the indirect reuse analysis part of the CTGC system. Using a fixpoint
computation, this propagates the reuse conditions determined by the direct
reuse analysis step through procedure calls.
compiler/ctgc.datastruct.m:
Minor additions.
compiler/ctgc.livedata.m:
(new file) Types and operations needed for defining the lattice of
possibly live datastructures.
compiler/ctgc.m:
Add livedata submodule.
compiler/ctgc.util.m:
Provide the operations for determining variable and type renamings,
used both by the structure sharing analysis as well as the reuse
analysis.
compiler/hlds_module.m:
Add structure reuse information to collect the mapping between
procedures, and their reuse versions.
compiler/prog_data.m:
New types "dead_vars", "live_vars".
compiler/structure_reuse.analysis.m:
Add the indirect reuse analysis step.
compiler/structure_reuse.direct.detect_garbage.m:
compiler/structure_sharing.domain.m:
Mainly moving the operation of looking up sharing information and
combining it with existing sharing to a more appropriate place, namely
structure_sharing.domain.m
compiler/structure_reuse.domain.m:
Add a renaming operation but especially two predicates needed to
verify whether a given procedure call satisfies the derived reuse
conditions, and to translate these reuse conditions to the
head variables of the procedure in which the procedure call occurs.
compiler/structure_reuse.indirect.m:
The actual indirect reuse analysis.
compiler/structure_reuse.m:
Add "structure_reuse.indirect" as a submodule.
compiler/structure_sharing.analysis.m:
small changes.
Index: compiler/ctgc.datastruct.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ctgc.datastruct.m,v
retrieving revision 1.6
diff -u -d -r1.6 ctgc.datastruct.m
--- compiler/ctgc.datastruct.m 10 May 2006 10:56:49 -0000 1.6
+++ compiler/ctgc.datastruct.m 18 May 2006 12:01:04 -0000
@@ -35,6 +35,11 @@
%
:- pred datastruct_equal(datastruct::in, datastruct::in) is semidet.
+ % Verify whether the datastructure represents a top cell, ie. where
+ % the selector path is an empty path.
+ %
+:- pred datastruct_refers_to_topcell(datastruct::in) is semidet.
+
% Select a subterm of the given datastructure using the specified selector.
% It is assumed that the selector is a valid selector for that
% datastructure.
@@ -69,6 +74,9 @@
:- pred datastructs_subsumed_by_list(module_info::in, proc_info::in,
list(datastruct)::in, list(datastruct)::in) is semidet.
+:- func datastruct_lists_least_upper_bound(module_info, proc_info,
+ list(datastruct), list(datastruct)) = list(datastruct).
+
:- pred datastruct_apply_widening(module_info::in, proc_info::in,
datastruct::in, datastruct::out) is det.
@@ -94,6 +102,10 @@
datastruct_equal(D1, D2) :- D1 = D2.
+datastruct_refers_to_topcell(Data):-
+ DSel = Data ^ sc_selector,
+ DSel = [].
+
datastruct_termshift(Sel, Data0, Data) :-
DSel = Data0 ^ sc_selector,
selector_termshift(DSel, Sel, NewSel),
@@ -156,6 +168,13 @@
map.lookup(VarTypes, Var, Type),
selector_apply_widening(ModuleInfo, Type, Sel0, Sel),
!:Data = datastruct_init_with_selector(Var, Sel).
+
+datastruct_lists_least_upper_bound(ModuleInfo, ProcInfo, Data1, Data2)
+ = Data :-
+ list.filter(
+ datastructs_subsume_datastruct(ModuleInfo, ProcInfo, Data1),
+ Data2, _SubsumedData, NotSubsumedData),
+ Data = list.append(NotSubsumedData, Data1).
datastructs_project(Vars, DataIn) =
list__filter(
Index: compiler/ctgc.livedata.m
===================================================================
RCS file: compiler/ctgc.livedata.m
diff -N compiler/ctgc.livedata.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/ctgc.livedata.m 18 May 2006 12:01:05 -0000
@@ -0,0 +1,292 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 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: ctgc.livedata.m.
+% Main author: nancy.
+%
+% Definition of the live_data type used to represent the set of datastructures
+% that are probably (not definitely!) live at a given program point (goal).
+% A data structure is said to be "live" if the memory used to represent
+% that data structure may possibly be accessed during the further execution
+% of the program w.r.t. the program point (goal) looked at.
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.livedata.
+:- interface.
+
+:- import_module parse_tree.prog_data.
+:- import_module hlds.hlds_module.
+:- import_module hlds.hlds_pred.
+:- import_module transform_hlds.ctgc.structure_sharing.
+:- import_module transform_hlds.ctgc.structure_sharing.domain.
+:- import_module hlds.hlds_goal.
+
+:- import_module list.
+
+%-----------------------------------------------------------------------------%
+
+:- type livedata.
+
+ % Create an initial set of live data structure, possibly given a list
+ % of live variables or data structures.
+ %
+:- func livedata_init = livedata. % Which assumes that nothing is live.
+:- func livedata_init_from_vars(live_vars) = livedata.
+:- func livedata_init_from_datastructs(live_datastructs) = livedata.
+:- func livedata_init_as_top = livedata.
+
+ % Verify whether the liveness set is bottom resp. top.
+:- pred livedata_is_bottom(livedata::in) is semidet.
+:- pred livedata_is_top(livedata::in) is semidet.
+
+ % Return the list of live data structures represented by livedata.
+ % Returns a software error when the livedata set is top.
+ %
+:- func livedata_get_datastructs(livedata) = list(datastruct).
+
+ % Least upper bound of all the livedata.
+ %
+:- func livedata_least_upper_bound(module_info, proc_info, livedata,
+ livedata) = livedata.
+:- func livedata_least_upper_bound_list(module_info, proc_info,
+ list(livedata)) = livedata.
+
+ % Subsumption predicates.
+ %
+:- pred livedata_subsumes_prog_var(livedata::in, prog_var::in) is semidet.
+:- pred livedata_subsumes_datastruct(module_info::in, proc_info::in,
+ livedata::in, datastruct::in) is semidet.
+
+ % Projection operation.
+ %
+:- func livedata_project(list(prog_var), livedata) = livedata.
+
+%-----------------------------------------------------------------------------%
+
+:- func livedata_init_at_goal(module_info, proc_info, hlds_goal_info,
+ sharing_as) = livedata.
+:- func livedata_add_liveness(module_info, proc_info, live_datastructs,
+ sharing_as, livedata) = livedata.
+
+:- pred nodes_are_not_live(module_info::in, proc_info::in,
+ list(datastruct)::in, livedata::in) is semidet.
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module libs.compiler_util.
+:- import_module transform_hlds.ctgc.datastruct.
+
+:- import_module set.
+
+
+:- type livedata
+ ---> bottom % There are no live data structures.
+ ; top % All data structures may be live.
+ ; live(list(datastruct)).
+ % Only the listed datastructures can possibly
+ % be live.
+
+%-----------------------------------------------------------------------------%
+
+livedata_init = bottom.
+livedata_init_from_vars(LiveVars) = live(list.map(datastruct_init, LiveVars)).
+livedata_init_from_datastructs(Data) = live(Data).
+livedata_init_as_top = top.
+
+livedata_is_bottom(bottom).
+livedata_is_top(top).
+
+livedata_get_datastructs(bottom) = [].
+livedata_get_datastructs(live(Data)) = Data.
+livedata_get_datastructs(top) = unexpected(this_file,
+ "livedata_get_datastructs: livedata is top.").
+
+livedata_least_upper_bound(ModuleInfo, ProcInfo, LiveData1,
+ LiveData2) = LiveData :-
+ (
+ LiveData1 = bottom,
+ LiveData = LiveData2
+ ;
+ LiveData1 = top,
+ LiveData = top
+ ;
+ LiveData1 = live(Data1),
+ (
+ LiveData2 = bottom,
+ LiveData = LiveData1
+ ;
+ LiveData2 = top,
+ LiveData = top
+ ;
+ LiveData2 = live(Data2),
+ LiveData = live(datastruct_lists_least_upper_bound(ModuleInfo,
+ ProcInfo, Data1, Data2))
+ )
+ ).
+
+livedata_least_upper_bound_list(ModuleInfo, ProcInfo, LiveDataList)
+ = list.foldl(livedata_least_upper_bound(ModuleInfo, ProcInfo),
+ LiveDataList, bottom).
+
+livedata_subsumes_prog_var(LiveData, ProgVar) :-
+ livedata_subsumes_topcell(LiveData, datastruct_init(ProgVar)).
+
+:- pred livedata_subsumes_topcell(livedata::in, datastruct::in) is semidet.
+livedata_subsumes_topcell(LiveData, TopCell) :-
+ (
+ LiveData = top
+ ;
+ LiveData = live(Data),
+ list.member(TopCell, Data)
+ ).
+
+livedata_subsumes_datastruct(ModuleInfo, ProcInfo, LiveData, Datastruct):-
+ (
+ datastruct_refers_to_topcell(Datastruct)
+ ->
+ livedata_subsumes_topcell(LiveData, Datastruct)
+ ;
+ livedata_subsumes_datastruct_with_selector(ModuleInfo, ProcInfo,
+ LiveData, Datastruct)
+ ).
+
+:- pred livedata_subsumes_datastruct_with_selector(module_info::in,
+ proc_info::in, livedata::in, datastruct::in) is semidet.
+livedata_subsumes_datastruct_with_selector(ModuleInfo, ProcInfo, LiveData,
+ Datastruct) :-
+ (
+ LiveData = top
+ ;
+ LiveData = live(Data),
+ datastruct_subsumed_by_list(ModuleInfo, ProcInfo, Datastruct, Data)
+ ).
+
+livedata_project(ProgVars, LiveData) = ProjectedLiveData :-
+ (
+ LiveData = bottom,
+ ProjectedLiveData = bottom
+ ;
+ LiveData = top,
+ ProjectedLiveData = top
+ ;
+ LiveData = live(Data),
+ list.filter(list_contains_datastruct_var(ProgVars),
+ Data, FilteredData),
+ ( FilteredData = [] -> ProjectedLiveData = bottom
+ ; ProjectedLiveData = live(FilteredData)
+ )
+ ).
+
+:- pred list_contains_datastruct_var(prog_vars::in, datastruct::in) is semidet.
+
+list_contains_datastruct_var(ProgVars, Datastruct) :-
+ list.member(Datastruct ^ sc_var, ProgVars).
+
+%-----------------------------------------------------------------------------%
+
+livedata_init_at_goal(ModuleInfo, ProcInfo, GoalInfo, SharingAs) = LiveData :-
+ % Collect the
+ Lfu = goal_info_get_lfu(GoalInfo),
+ Lbu = goal_info_get_lbu(GoalInfo),
+ Lu = set.to_sorted_list(set.union(Lfu, Lbu)),
+ (
+ % When there are no data structure in forward nor backward use,
+ % then the livedata set is empty.
+ Lu = []
+ ->
+ LiveData = livedata_init
+ ;
+ % If Lu is not empty, and sharing is top, then all possible
+ % datastructures might possibly be live.
+ sharing_as_is_top(SharingAs)
+ ->
+ LiveData = livedata_init_as_top
+ ;
+ % Lu not empty, and sharing is bottom... then only the
+ % datastructures in local use are live.
+ sharing_as_is_bottom(SharingAs)
+ ->
+ LiveData = livedata_init_from_vars(Lu)
+ ;
+ % otherwise we have the most general case: Lu not empty, Sharing
+ % not top nor bottom.
+ LiveData = livedata_init_at_goal_2(ModuleInfo, ProcInfo, Lu,
+ SharingAs)
+ ).
+
+ % Preconditions: live_vars is not empty, sharing_as is not top.
+ %
+:- func livedata_init_at_goal_2(module_info, proc_info, live_vars,
+ sharing_as) = livedata.
+
+livedata_init_at_goal_2(ModuleInfo, ProcInfo, Lu, SharingAs) = LiveData :-
+ % Let Data0 be the set of data structures pointed at by the
+ % set of live vars Lu, then LiveData is the result of "extending"
+ % (Cf. structure_sharing.domain.m) each of the data structures in Data0.
+ Data0 = list.map(datastruct_init, Lu),
+ DataList = extend_datastructs(ModuleInfo, ProcInfo, SharingAs,
+ Data0),
+ LiveData = live(DataList).
+
+livedata_add_liveness(ModuleInfo, ProcInfo, LuData, LocalSharing, LiveData0)
+ = LiveData :-
+ (
+ sharing_as_is_top(LocalSharing)
+ ->
+ LiveData = livedata_init_as_top
+ ;
+ sharing_as_is_bottom(LocalSharing)
+ ->
+ LiveData = livedata_least_upper_bound(ModuleInfo, ProcInfo,
+ LiveData0, livedata_init_from_datastructs(LuData))
+ ;
+ % most general case: normal sharing.
+ LuLiveData = livedata_init_from_datastructs(
+ extend_datastructs(ModuleInfo, ProcInfo,
+ LocalSharing, LuData)),
+ ExtendLiveData = extend_livedata(ModuleInfo, ProcInfo,
+ LocalSharing, LiveData0),
+ LiveData = livedata_least_upper_bound(ModuleInfo, ProcInfo,
+ LuLiveData, ExtendLiveData)
+ ).
+
+:- func extend_livedata(module_info, proc_info, sharing_as, livedata)
+ = livedata.
+
+extend_livedata(ModuleInfo, ProcInfo, SharingAs, LiveData0) = LiveData :-
+ (
+ LiveData0 = bottom,
+ LiveData = bottom
+ ;
+ LiveData0 = top,
+ LiveData = top
+ ;
+ LiveData0 = live(Data0),
+ LiveData = live(extend_datastructs(ModuleInfo, ProcInfo,
+ SharingAs, Data0))
+ ).
+
+nodes_are_not_live(ModuleInfo, ProcInfo, Nodes, LiveData) :-
+ (
+ LiveData = top,
+ fail
+ ;
+ LiveData = bottom,
+ true
+ ;
+ LiveData = live(Data),
+ \+ datastructs_subsumed_by_list(ModuleInfo, ProcInfo, Nodes, Data)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- func this_file = string.
+this_file = "ctgc.livedata.m".
+
+:- end_module transform_hlds.ctgc.livedata.
Index: compiler/ctgc.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ctgc.m,v
retrieving revision 1.5
diff -u -d -r1.5 ctgc.m
--- compiler/ctgc.m 10 May 2006 10:56:49 -0000 1.5
+++ compiler/ctgc.m 18 May 2006 12:01:05 -0000
@@ -19,9 +19,10 @@
:- include_module datastruct.
:- include_module fixpoint_table.
+:- include_module livedata.
:- include_module selector.
-:- include_module structure_sharing.
:- include_module structure_reuse.
+:- include_module structure_sharing.
:- include_module util.
:- end_module transform_hlds.ctgc.
Index: compiler/ctgc.util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ctgc.util.m,v
retrieving revision 1.5
diff -u -d -r1.5 ctgc.util.m
--- compiler/ctgc.util.m 10 May 2006 10:56:49 -0000 1.5
+++ compiler/ctgc.util.m 18 May 2006 12:01:05 -0000
@@ -18,8 +18,10 @@
:- import_module hlds.hlds_module.
:- import_module hlds.hlds_pred.
+:- import_module parse_tree.prog_data.
:- import_module list.
+:- import_module map.
%-----------------------------------------------------------------------------%
@@ -34,16 +36,32 @@
:- pred pred_requires_no_analysis(module_info::in, pred_id::in) is semidet.
:- pred pred_requires_analysis(module_info::in, pred_id::in) is semidet.
+ % Given the pred_proc_id of a procedure call and its actual arguments,
+ % determine the variable renaming to rename anything which is defined
+ % in terms of the formal arguments of the called procedure to the context
+ % of the actual arguments.
+ %
+:- func get_variable_renaming(module_info, pred_proc_id, prog_vars) =
+ map(prog_var, prog_var).
+
+ % Same as above, but then in the context of the types of the called
+ % procedures.
+ %
+:- func get_type_substitution(module_info, pred_proc_id, list(mer_type),
+ tvarset) = tsubst.
+
+
%-----------------------------------------------------------------------------%
:- implementation.
+:- import_module libs.compiler_util.
+:- import_module parse_tree.prog_type.
+:- import_module parse_tree.prog_type_subst.
+
:- import_module bool.
:- import_module list.
-:- import_module map.
-
-
-%-----------------------------------------------------------------------------%
+:- import_module string.
pred_requires_no_analysis(ModuleInfo, PredId) :-
module_info_get_special_pred_map(ModuleInfo, SpecialPredMap),
@@ -75,6 +93,36 @@
pred_info_get_import_status(PredInfo, Status),
status_defined_in_this_module(Status, no).
+get_variable_renaming(ModuleInfo, PPId, ActualArgs) = VariableRenaming :-
+ module_info_pred_proc_info(ModuleInfo, PPId, _PredInfo, ProcInfo),
+
+ % head variables.
+ proc_info_get_headvars(ProcInfo, FormalVars),
+ map.from_corresponding_lists(FormalVars, ActualArgs, VariableRenaming).
+
+get_type_substitution(ModuleInfo, PPId, ActualTypes, ActualTVarset) =
+ TypeSubstitution :-
+ module_info_pred_proc_info(ModuleInfo, PPId, PredInfo, _ProcInfo),
+
+ % types of the head variables.
+ pred_info_get_arg_types(PredInfo, FormalTVarset, _, FormalTypes),
+
+ % (this is a bit that was inspired by the code for
+ % arg_type_list_subsumes/6)
+ tvarset_merge_renaming(ActualTVarset, FormalTVarset,_TVarSet1, Renaming),
+ apply_variable_renaming_to_type_list(Renaming, FormalTypes,
+ RenFormalTypes),
+
+ ( type_list_subsumes(RenFormalTypes, ActualTypes, TypeSubstitution0) ->
+ TypeSubstitution = TypeSubstitution0
+ ;
+ unexpected(this_file, "Types are supposed to be unifiable.")
+ ).
+
+
%-----------------------------------------------------------------------------%
+
+:- func this_file = string.
+this_file = "ctgc.util.m".
+
:- end_module transform_hlds.ctgc.util.
-%-----------------------------------------------------------------------------%
Index: compiler/hlds_module.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_module.m,v
retrieving revision 1.134
diff -u -d -r1.134 hlds_module.m
--- compiler/hlds_module.m 29 Mar 2006 08:06:48 -0000 1.134
+++ compiler/hlds_module.m 18 May 2006 12:01:07 -0000
@@ -185,6 +185,14 @@
; complexity_input_fixed_size
; complexity_output.
+ % This type is used to record the mapping between original
+ % procedures, and their optimised versions with respect to
+ % structure reuse (CTGC).
+ %
+:- type structure_reuse_info
+ ---> structure_reuse_info(
+ map(pred_proc_id, pair(pred_proc_id, sym_name))
+ ).
%-----------------------------------------------------------------------------%
%
% Various predicates for manipulating the module_info data structure
@@ -455,6 +463,12 @@
:- pred module_info_user_final_pred_c_names(module_info::in,
list(string)::out) is det.
+:- pred module_info_get_structure_reuse_info(module_info::in,
+ structure_reuse_info::out) is det.
+
+:- pred module_info_set_structure_reuse_info(structure_reuse_info::in,
+ module_info::in, module_info::out) is det.
+
%-----------------------------------------------------------------------------%
:- pred module_info_preds(module_info::in, pred_table::out) is det.
@@ -698,7 +712,10 @@
% Export C names fored pred appearing in `:- finalise
% finalpred' directives in this module, in order of
% appearance.
- user_final_pred_c_names :: assoc_list(sym_name, string)
+ user_final_pred_c_names :: assoc_list(sym_name, string),
+
+ % Information about which procedures implement structure reuse.
+ structure_reuse_info :: structure_reuse_info
).
module_info_init(Name, Items, Globals, QualifierInfo, RecompInfo,
@@ -740,7 +757,7 @@
[], [], StratPreds, UnusedArgInfo, ExceptionInfo, TrailingInfo,
map.init, counter.init(1), ImportedModules,
IndirectlyImportedModules, TypeSpecInfo, NoTagTypes, no, [],
- init_analysis_info(mmc), [], []),
+ init_analysis_info(mmc), [], [], structure_reuse_info(map.init)),
ModuleInfo = module_info(ModuleSubInfo, PredicateTable, Requests,
UnifyPredMap, QualifierInfo, Types, Insts, Modes, Ctors,
ClassTable, SuperClassTable, InstanceTable, AssertionTable,
@@ -826,6 +843,8 @@
MI ^ sub_info ^ maybe_complexity_proc_map).
module_info_get_complexity_proc_infos(MI,
MI ^ sub_info ^ complexity_proc_infos).
+module_info_get_structure_reuse_info(MI,
+ MI ^ sub_info ^ structure_reuse_info).
% XXX There is some debate as to whether duplicate initialise directives
% in the same module should constitute an error. Currently it is not, but
@@ -935,6 +954,8 @@
MI ^ sub_info ^ maybe_complexity_proc_map := NewVal).
module_info_set_complexity_proc_infos(NewVal, MI,
MI ^ sub_info ^ complexity_proc_infos := NewVal).
+module_info_set_structure_reuse_info(ReuseMap, MI,
+ MI ^ sub_info ^ structure_reuse_info := ReuseMap).
%-----------------------------------------------------------------------------%
Index: compiler/prog_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/prog_data.m,v
retrieving revision 1.163
diff -u -d -r1.163 prog_data.m
--- compiler/prog_data.m 10 May 2006 10:56:55 -0000 1.163
+++ compiler/prog_data.m 18 May 2006 12:01:09 -0000
@@ -359,9 +359,11 @@
%
:- type dead_var == prog_var.
+:- type dead_vars == list(dead_var).
:- type dead_datastruct == datastruct.
:- type dead_datastructs == list(dead_datastruct).
:- type live_var == prog_var.
+:- type live_vars == list(live_var).
:- type live_datastruct == datastruct.
:- type live_datastructs == list(live_datastruct).
Index: compiler/structure_reuse.analysis.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_reuse.analysis.m,v
retrieving revision 1.1
diff -u -d -r1.1 structure_reuse.analysis.m
--- compiler/structure_reuse.analysis.m 10 May 2006 10:56:56 -0000 1.1
+++ compiler/structure_reuse.analysis.m 18 May 2006 12:01:10 -0000
@@ -68,6 +68,7 @@
:- import_module parse_tree.prog_out.
:- import_module transform_hlds.ctgc.structure_reuse.direct.
:- import_module transform_hlds.ctgc.structure_reuse.domain.
+:- import_module transform_hlds.ctgc.structure_reuse.indirect.
:- import_module transform_hlds.ctgc.structure_reuse.lbu.
:- import_module transform_hlds.ctgc.structure_reuse.lfu.
:- import_module transform_hlds.ctgc.structure_sharing.domain.
@@ -98,19 +99,24 @@
maybe_write_string(VeryVerbose, "% Direct reuse...\n", !IO),
DummyReuseTable = reuse_as_table_init,
direct_reuse_pass(SharingTable, !ModuleInfo,
- DummyReuseTable, _ReuseTable, !IO),
- maybe_write_string(VeryVerbose, "% Direct reuse: done.\n", !IO).
+ DummyReuseTable, ReuseTable1, !IO),
+ maybe_write_string(VeryVerbose, "% Direct reuse: done.\n", !IO),
+ reuse_as_table_maybe_dump(VeryVerbose, ReuseTable1, !IO),
% Determine information about possible indirect reuses.
% XXX TO DO!
- % indirect_reuse_pass(SharingTable, ReuseTable1, ReuseTable2,
- % !ModuleInfo, !IO),
+ maybe_write_string(VeryVerbose, "% Indirect reuse...\n", !IO),
+ indirect_reuse_pass(SharingTable, !ModuleInfo, ReuseTable1, ReuseTable2,
+ !IO),
+ maybe_write_string(VeryVerbose, "% Indirect reuse: done.\n", !IO),
+ reuse_as_table_maybe_dump(VeryVerbose, ReuseTable2, !IO).
% For every procedure that has some potential (conditional) reuse (either
% direct or indirect), create a new procedure that actually implements
% that reuse.
% XXX TO DO!
- % split_reuse_procedures(ReuseTable2, ReuseTable3, !ModuleInfo, !IO),
+ % split_reuse_procedures(!ModuleInfo, ReuseTable2, ReuseTable3, !IO),
+ % reuse_as_table_maybe_dump(VeryVerbose, ReuseTable3, !IO).
% Record the results of the reuse table into the HLDS.
% XXX TO DO!
Index: compiler/structure_reuse.direct.detect_garbage.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_reuse.direct.detect_garbage.m,v
retrieving revision 1.1
diff -u -d -r1.1 structure_reuse.direct.detect_garbage.m
--- compiler/structure_reuse.direct.detect_garbage.m 10 May 2006 10:56:56 -0000 1.1
+++ compiler/structure_reuse.direct.detect_garbage.m 18 May 2006 12:01:12 -0000
@@ -90,6 +90,7 @@
func(C) = G :- (G = C ^ case_goal), Cases), !SharingAs,
!DeadCellTable)
;
+ % XXX
GoalExpr = not(_Goal)
;
GoalExpr = scope(_, SubGoal),
@@ -208,28 +209,6 @@
var_is_live(Var, LiveData) :-
list.member(datastruct_init(Var), LiveData).
-
-:- pred lookup_sharing_and_comb(module_info::in, proc_info::in,
- sharing_as_table::in, pred_id::in, proc_id::in, prog_vars::in,
- sharing_as::in, sharing_as::out) is det.
-lookup_sharing_and_comb(ModuleInfo, ProcInfo, SharingTable, PredId, ProcId,
- ActualVars, !Sharing):-
- PPId = proc(PredId, ProcId),
-
- lookup_sharing_or_predict(ModuleInfo, SharingTable, PPId, FormalSharing),
-
- proc_info_get_vartypes(ProcInfo, VarTypes),
- list.map(map.lookup(VarTypes), ActualVars, ActualTypes),
-
- % XXX To be checked!
- ActualTVarset = varset.init,
- sharing_as_rename_using_module_info(ModuleInfo, PPId,
- ActualVars, ActualTypes, ActualTVarset, FormalSharing,
- ActualSharing),
-
- !:Sharing = sharing_as_comb(ModuleInfo, ProcInfo,
- ActualSharing, !.Sharing).
-
%-----------------------------------------------------------------------------%
:- func this_file = string.
Index: compiler/structure_reuse.domain.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_reuse.domain.m,v
retrieving revision 1.1
diff -u -d -r1.1 structure_reuse.domain.m
--- compiler/structure_reuse.domain.m 10 May 2006 10:56:56 -0000 1.1
+++ compiler/structure_reuse.domain.m 18 May 2006 12:01:13 -0000
@@ -21,8 +21,11 @@
:- import_module hlds.hlds_module.
:- import_module hlds.hlds_pred.
:- import_module parse_tree.prog_data.
+:- import_module transform_hlds.ctgc.livedata.
:- import_module transform_hlds.ctgc.structure_sharing.domain.
+:- import_module bool.
+:- import_module io.
:- import_module map.
:- import_module set.
:- import_module list.
@@ -96,6 +99,10 @@
:- func reuse_as_init = reuse_as.
:- func reuse_as_init_with_one_condition(reuse_condition) = reuse_as.
+ % Return a short description of the reuse information.
+ %
+:- func reuse_as_short_description(reuse_as) = string.
+
% Succeeds if the first reuses description is subsumed by the second
% description, i.e., if a procedure call satisfies all the conditions
% expressed by the second reuses description, then it also satisfies all
@@ -111,6 +118,19 @@
:- pred reuse_as_all_unconditional_reuses(reuse_as::in) is semidet.
:- pred reuse_as_conditional_reuses(reuse_as::in) is semidet.
+ % reuse_as_rename_using_module_info(ModuleInfo, PPId,
+ % ActualVars, ActualTypes, ActualTVarset, FormalReuse, ActualReuse):
+ %
+ % Renaming of the formal description of structure reuse conditions to the
+ % actual description of these conditions. The information about the formal
+ % variables needs to be extracted from the module information.
+ % A list of variables and types is used as the actual variables and types.
+ % The type variables set in the actual context must also be specified.
+ %
+:- pred reuse_as_rename_using_module_info(module_info::in,
+ pred_proc_id::in, prog_vars::in, list(mer_type)::in, tvarset::in,
+ reuse_as::in, reuse_as::out) is det.
+
% Given a variable and type variable mapping, rename the reuses
% conditions accordingly.
%
@@ -123,12 +143,44 @@
%
:- pred reuse_as_add_condition(module_info::in, proc_info::in,
reuse_condition::in, reuse_as::in, reuse_as::out) is det.
+
+ % A shortcut version of the above procedure when the additional condition
+ % is "unconditional".
+ %
+:- pred reuse_as_add_unconditional(reuse_as::in, reuse_as::out) is det.
% Compute the least upper bound of two reuses descriptions. Module_info
% and proc_info are needed for verifying subsumption.
%
:- pred reuse_as_least_upper_bound(module_info::in, proc_info::in,
reuse_as::in, reuse_as::in, reuse_as::out) is det.
+:- func reuse_as_least_upper_bound(module_info, proc_info, reuse_as,
+ reuse_as) = reuse_as.
+
+ % reuse_as_from_called_procedure_to_local_reuse_as(ModuleInfo,
+ % ProcInfo, HeadVars, InUseData, SharingAs, CalledReuseAs) =
+ % LocalReuseAs.
+ %
+ % Translate the reuse description of a called procedure to the
+ % environment of the caller. This means taking into account the local
+ % sets of in use variables, as well as the local sharing.
+ %
+ % Pre-condition: the reuse description of the called procedure is already
+ % correctly renamed to the caller's environment.
+ % Pre-condition: the reuse_as from the called procedure contains at
+ % least one conditional reuse condition.
+ %
+:- func reuse_as_from_called_procedure_to_local_reuse_as(module_info,
+ proc_info, prog_vars, live_datastructs, sharing_as, reuse_as) = reuse_as.
+
+
+ % Succeeds if taking into account the live data and static variables the
+ % reuse conditions expressed by reuse_as are all satisfied, hence making
+ % the associated memory reuses safe for that particular calling
+ % environment.
+ %
+:- pred reuse_as_satisfied(module_info::in, proc_info::in, livedata::in,
+ sharing_as::in, prog_vars::in, reuse_as::in) is semidet.
% XXX TO DO!
% :- func from_reuse_domain(reuse_domain) = reuse_as.
@@ -148,6 +200,10 @@
= reuse_as is semidet.
:- pred reuse_as_table_set(pred_proc_id::in, reuse_as::in,
reuse_as_table::in, reuse_as_table::out) is det.
+
+:- pred reuse_as_table_maybe_dump(bool::in, reuse_as_table::in,
+ io::di, io::uo) is det.
+
% XXX TO DO!
% :- func load_structure_reuse_table(module_info) = reuse_as_table.
@@ -155,10 +211,14 @@
:- implementation.
-:- import_module transform_hlds.ctgc.datastruct.
+:- import_module libs.compiler_util.
:- import_module parse_tree.prog_ctgc.
+:- import_module transform_hlds.ctgc.datastruct.
+:- import_module transform_hlds.ctgc.util.
+:- import_module pair.
:- import_module set.
+:- import_module string.
:- type reuse_condition
---> always % The reuse is always safe and does not actually
@@ -303,6 +363,12 @@
ReuseAs = unconditional
).
+reuse_as_short_description(no_reuse) = "n".
+reuse_as_short_description(unconditional) = "u".
+reuse_as_short_description(conditional(Conds)) = "c(" ++ Size ++ ")" :-
+ Size = string.int_to_string(list.length(Conds)).
+
+
reuse_as_subsumed_by(ModuleInfo, ProcInfo, FirstReuseAs, SecondReuseAs) :-
(
FirstReuseAs = no_reuse
@@ -325,6 +391,13 @@
reuse_as_all_unconditional_reuses(unconditional).
reuse_as_conditional_reuses(conditional(_)).
+reuse_as_rename_using_module_info(ModuleInfo, PPId, ActualArgs, ActualTypes,
+ ActualTVarset, FormalReuse, ActualReuse) :-
+ reuse_as_rename(
+ get_variable_renaming(ModuleInfo, PPId, ActualArgs),
+ get_type_substitution(ModuleInfo, PPId, ActualTypes, ActualTVarset),
+ FormalReuse, ActualReuse).
+
reuse_as_rename(MapVar, TypeSubst, ReuseAs, RenamedReuseAs) :-
(
ReuseAs = no_reuse,
@@ -365,6 +438,16 @@
)
).
+reuse_as_add_unconditional(!ReuseAs) :-
+ (
+ !.ReuseAs = no_reuse,
+ !:ReuseAs = unconditional
+ ;
+ !.ReuseAs = unconditional
+ ;
+ !.ReuseAs = conditional(_)
+ ).
+
:- pred reuse_conditions_add_condition(module_info::in, proc_info::in,
reuse_condition::in, reuse_conditions::in, reuse_conditions::out) is det.
reuse_conditions_add_condition(ModuleInfo, ProcInfo, Condition, !Conds):-
@@ -418,6 +501,116 @@
).
+reuse_as_least_upper_bound(ModuleInfo, ProcInfo, Reuse1, Reuse2) = Reuse :-
+ reuse_as_least_upper_bound(ModuleInfo, ProcInfo, Reuse1, Reuse2, Reuse).
+
+reuse_as_from_called_procedure_to_local_reuse_as(ModuleInfo, ProcInfo,
+ HeadVars, LuData, SharingAs, CalledReuseAs) = LocalReuseAs :-
+ (
+ CalledReuseAs = no_reuse,
+ unexpected(this_file,
+ "reuse_as_from_called_procedure_to_local_reuse_as: " ++
+ "reuse_as does not specify any reuses.")
+ ;
+ CalledReuseAs = unconditional,
+ unexpected(this_file,
+ "reuse_as_from_called_procedure_to_local_reuse_as: " ++
+ "reuse_as is unconditional.")
+ ;
+ CalledReuseAs = conditional(ConditionsCaller),
+ ConditionsCallee =
+ list.map(reuse_condition_from_called_proc_to_local_condition(
+ ModuleInfo, ProcInfo, HeadVars, LuData, SharingAs),
+ ConditionsCaller),
+ list.foldl(reuse_as_add_condition(ModuleInfo, ProcInfo),
+ ConditionsCallee, reuse_as_init, LocalReuseAs)
+ ).
+
+:- func reuse_condition_from_called_proc_to_local_condition(module_info,
+ proc_info, prog_vars, live_datastructs, sharing_as, reuse_condition) =
+ reuse_condition.
+
+reuse_condition_from_called_proc_to_local_condition(ModuleInfo, ProcInfo,
+ HeadVars, LuData, SharingAs, CalledCondition) = LocalCondition :-
+ (
+ CalledCondition = always, % should not occur though...
+ LocalCondition = always
+ ;
+ CalledCondition = condition(CalledDeadNodes,
+ CalledInUseNodes, CalledSharingAs),
+
+ % Translate the dead nodes:
+ AllDeadNodes = extend_datastructs(ModuleInfo, ProcInfo,
+ SharingAs, CalledDeadNodes),
+ AllDeadHeadVarNodes = datastructs_project(HeadVars, AllDeadNodes),
+
+ (
+ AllDeadHeadVarNodes = []
+ ->
+ LocalCondition = always
+ ;
+ % Translate the in use nodes:
+ AllInUseNodes = extend_datastructs(ModuleInfo, ProcInfo,
+ SharingAs, list.append(LuData, CalledInUseNodes)),
+ AllInUseHeadVarNodes = datastructs_project(HeadVars,
+ AllInUseNodes),
+
+ % Translate the sharing information:
+ AllLocalSharing = sharing_as_comb(ModuleInfo, ProcInfo,
+ CalledSharingAs, SharingAs),
+ AllHeadVarLocalSharing = sharing_as_project(HeadVars,
+ AllLocalSharing),
+
+ LocalCondition = condition(AllDeadHeadVarNodes,
+ AllInUseHeadVarNodes, AllHeadVarLocalSharing)
+ )
+ ).
+
+reuse_as_satisfied(ModuleInfo, ProcInfo, LiveData, SharingAs, StaticVars,
+ ReuseAs) :-
+ (
+ ReuseAs = no_reuse,
+ fail
+ ;
+ ReuseAs = unconditional,
+ true
+ ;
+ ReuseAs = conditional(Conditions),
+ list.all_true(reuse_condition_satisfied(ModuleInfo, ProcInfo,
+ LiveData, SharingAs, StaticVars), Conditions)
+ % XXX something about reuse conditions pointing to the
+ % same datastructure to be reused...
+ ).
+
+:- pred reuse_condition_satisfied(module_info::in, proc_info::in,
+ livedata::in, sharing_as::in, prog_vars::in, reuse_condition::in)
+ is semidet.
+
+reuse_condition_satisfied(ModuleInfo, ProcInfo, LiveData, SharingAs,
+ StaticVars, Condition) :-
+ (
+ Condition = always
+ ;
+ Condition = condition(DeadNodes, InUseNodes, SharingNodes),
+ % Reuse of static vars is not allowed:
+ StaticDeadNodes = datastructs_project(StaticVars, DeadNodes),
+ StaticDeadNodes = [],
+
+ % Using the InUseNodes, and the sharing recorded by the condition,
+ % compute a new set of livedata that (safely) approximates the
+ % set of livedata that would have been obtained when looking at
+ % the program point from where the reuse condition actually comes from.
+ NewSharing = sharing_as_comb(ModuleInfo, ProcInfo, SharingNodes,
+ SharingAs),
+ UpdatedLiveData = livedata_add_liveness(ModuleInfo, ProcInfo,
+ InUseNodes, NewSharing, LiveData),
+ nodes_are_not_live(ModuleInfo, ProcInfo, DeadNodes,
+ UpdatedLiveData)
+ ).
+
+
+
+
%-----------------------------------------------------------------------------%
%
% reuse_as_table
@@ -427,6 +620,35 @@
reuse_as_table_search(PPId, Table) = Table ^ elem(PPId).
reuse_as_table_set(PPId, ReuseAs, !Table) :-
!:Table = !.Table ^ elem(PPId) := ReuseAs.
+
+reuse_as_table_maybe_dump(DoDump, Table, !IO) :-
+ (
+ DoDump = no
+ ;
+ DoDump = yes,
+ reuse_as_table_dump(Table, !IO)
+ ).
+
+:- pred reuse_as_table_dump(reuse_as_table::in, io::di, io::uo) is det.
+
+reuse_as_table_dump(Table, !IO) :-
+ (
+ map.is_empty(Table)
+ ->
+ io.write_string("% ReuseTable: Empty", !IO)
+ ;
+ io.write_string("% ReuseTable: PPId --> Reuse\n", !IO),
+ io.write_list(map.to_assoc_list(Table), "", dump_entries, !IO)
+ ).
+
+:- pred dump_entries(pair(pred_proc_id, reuse_as)::in, io::di, io::uo) is det.
+
+dump_entries(PPId - ReuseAs, !IO) :-
+ PPId = proc(PredId, ProcId),
+ io.write_string(
+ "% " ++ string.int_to_string(pred_id_to_int(PredId)) ++ ", " ++
+ string.int_to_string(proc_id_to_int(ProcId)) ++ "\t-->" ++
+ reuse_as_short_description(ReuseAs) ++ "\n", !IO).
%-----------------------------------------------------------------------------%
:- func this_file = string.
Index: compiler/structure_reuse.indirect.m
===================================================================
RCS file: compiler/structure_reuse.indirect.m
diff -N compiler/structure_reuse.indirect.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/structure_reuse.indirect.m 18 May 2006 12:01:14 -0000
@@ -0,0 +1,676 @@
+%------------------------------------------------------------------------------%
+% vim: ft=mercury ff=unix ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 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: structure_reuse.indirect.m
+% Main authors: nancy
+%
+% Determine the indirect reuse. This requires a fixpoint computation.
+%------------------------------------------------------------------------------%
+
+:- module structure_reuse.indirect.
+
+:- interface.
+
+:- import_module hlds.hlds_module.
+:- import_module transform_hlds.ctgc.structure_reuse.domain.
+:- import_module transform_hlds.ctgc.structure_sharing.domain.
+
+:- import_module io.
+
+ % Direct reuse analysis derives information about deconstructions that
+ % under certain circumstances (formalised as "reuse conditions") form
+ % the last ever (memory) access to the deconstructed term.
+ %
+ % Indirect reuse analysis is about verifying procedure calls to see
+ % whether these procedure calls satisfy these reuse conditions for
+ % direct reuse, and under what circumstances (again expressed as
+ % reuse conditions). Using a fixpoint computation, we determine the
+ % overall reuse conditions for a procedure call to be replaced by a
+ % call to an optimised version of that procedure w.r.t. its memory usage.
+ %
+ % The results of the analysis are primarely stored in the reuse table, yet
+ % also involves annotations at the level of the individual procedure calls,
+ % which explains the need for updating the HLDS as well.
+ %
+:- pred indirect_reuse_pass(sharing_as_table::in, module_info::in,
+ module_info::out, reuse_as_table::in, reuse_as_table::out,
+ io::di, io::uo) is det.
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module hlds.hlds_goal.
+:- import_module hlds.hlds_pred.
+:- import_module hlds.passes_aux.
+:- import_module libs.compiler_util.
+:- import_module libs.globals.
+:- import_module libs.options.
+:- import_module parse_tree.prog_data.
+:- import_module parse_tree.prog_out.
+:- import_module transform_hlds.ctgc.datastruct.
+:- import_module transform_hlds.ctgc.fixpoint_table.
+:- import_module transform_hlds.ctgc.livedata.
+:- import_module transform_hlds.ctgc.util.
+:- import_module transform_hlds.dependency_graph.
+
+:- import_module list.
+:- import_module map.
+:- import_module maybe.
+:- import_module pair.
+:- import_module set.
+:- import_module string.
+
+indirect_reuse_pass(SharingTable, !ModuleInfo, !ReuseTable, !IO):-
+ %
+ % Perform a bottom-up traversal of the SCCs in the program,
+ % analysing indirect structure reuse in each one as we go.
+ %
+ module_info_ensure_dependency_info(!ModuleInfo),
+ module_info_get_maybe_dependency_info(!.ModuleInfo, MaybeDepInfo),
+ (
+ MaybeDepInfo = yes(DepInfo),
+ hlds_dependency_info_get_dependency_ordering(DepInfo, SCCs),
+ list.foldl3(indirect_reuse_analyse_scc(SharingTable),
+ SCCs, !ModuleInfo, !ReuseTable, !IO)
+ ;
+ MaybeDepInfo = no,
+ unexpected(this_file, "No dependency information.")
+ ).
+
+:- pred indirect_reuse_analyse_scc(sharing_as_table::in,
+ list(pred_proc_id)::in, module_info::in, module_info::out,
+ reuse_as_table::in, reuse_as_table::out, io::di, io::uo) is det.
+
+indirect_reuse_analyse_scc(SharingTable, SCC, !ModuleInfo, !ReuseTable, !IO) :-
+ ( preds_requiring_no_analysis(!.ModuleInfo, SCC) ->
+ true
+ ;
+ indirect_reuse_analyse_scc_until_fixpoint(SharingTable,
+ SCC, !.ReuseTable, !ModuleInfo,
+ sr_fixpoint_table_init(SCC, !.ReuseTable), FixpointTable, !IO),
+ list.foldl(update_reuse_in_table(FixpointTable), SCC, !ReuseTable)
+ ).
+
+:- pred indirect_reuse_analyse_scc_until_fixpoint(sharing_as_table::in,
+ list(pred_proc_id)::in, reuse_as_table::in,
+ module_info::in, module_info::out, sr_fixpoint_table::in,
+ sr_fixpoint_table::out, io::di, io::uo) is det.
+
+indirect_reuse_analyse_scc_until_fixpoint(SharingTable, SCC,
+ ReuseTable, !ModuleInfo, !FixpointTable, !IO):-
+ list.foldl3(indirect_reuse_analyse_pred_proc(SharingTable, ReuseTable),
+ SCC, !ModuleInfo, !FixpointTable, !IO),
+ ( sr_fixpoint_table_stable(!.FixpointTable) ->
+ true
+ ;
+ sr_fixpoint_table_new_run(!FixpointTable),
+ indirect_reuse_analyse_scc_until_fixpoint(SharingTable,
+ SCC, ReuseTable, !ModuleInfo, !FixpointTable, !IO)
+ ).
+
+%-----------------------------------------------------------------------------%
+:- pred indirect_reuse_analyse_pred_proc(sharing_as_table::in,
+ reuse_as_table::in, pred_proc_id::in, module_info::in, module_info::out,
+ sr_fixpoint_table::in, sr_fixpoint_table::out, io::di, io::uo) is det.
+
+indirect_reuse_analyse_pred_proc(SharingTable, ReuseTable, PPId,
+ !ModuleInfo, !FixpointTable, !IO):-
+ globals.io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
+
+ module_info_pred_proc_info(!.ModuleInfo, PPId, PredInfo0, ProcInfo0),
+ PPId = proc(PredId, ProcId),
+
+ % Some feedback..
+ Run = string.int_to_string(sr_fixpoint_table_which_run(!.FixpointTable)),
+ passes_aux.write_proc_progress_message(
+ "% Indirect reuse analysis (run " ++ Run ++ ") ",
+ PredId, ProcId, !.ModuleInfo, !IO),
+
+ % Some initialisation work...
+ proc_info_get_goal(ProcInfo0, Goal0),
+ BaseInfo = ir_background_info_init(!.ModuleInfo, PredInfo0, ProcInfo0,
+ SharingTable, ReuseTable),
+ AnalysisInfo0 = analysis_info_init(PPId, !.FixpointTable),
+
+ % The actual analysis of the goal:
+ indirect_reuse_analyse_goal(BaseInfo, Goal0, Goal, AnalysisInfo0,
+ AnalysisInfo, !IO),
+ !:FixpointTable = AnalysisInfo ^ fptable,
+
+ % Some feedback.
+ maybe_write_string(VeryVerbose, "% FPT: " ++
+ sr_fixpoint_table_get_short_description(PPId, !.FixpointTable)
+ ++ "\n", !IO),
+
+ % Record the obtained reuse description in the fixpoint table...
+ sr_fixpoint_table_new_as(!.ModuleInfo, ProcInfo0, PPId,
+ AnalysisInfo ^ reuse_as, !FixpointTable),
+
+ % As the analysis changes the goal, we must update proc_info and
+ % module_info:
+ proc_info_set_goal(Goal, ProcInfo0, ProcInfo),
+ module_info_set_pred_proc_info(PPId, PredInfo0, ProcInfo, !ModuleInfo).
+
+%-----------------------------------------------------------------------------%
+
+ % The type ir_background_info has the purpose to collect all the necessary
+ % background information needed to be able to perform the indirect reuse
+ % (ir) analysis of a specific procedure.
+ %
+:- type ir_background_info
+ ---> ir_background_info(
+ module_info :: module_info,
+ pred_info :: pred_info,
+ proc_info :: proc_info,
+ sharing_table :: sharing_as_table,
+ reuse_table :: reuse_as_table,
+ headvars :: list(prog_var)
+ ).
+
+ % The type analysis_info gathers the analysis information that may change
+ % from goal to goal.
+ %
+:- type analysis_info
+ ---> analysis_info(
+ sharing_as :: sharing_as,
+ reuse_as :: reuse_as,
+ static_vars :: set(prog_var),
+ fptable :: sr_fixpoint_table
+ ).
+
+:- func ir_background_info_init(module_info, pred_info, proc_info,
+ sharing_as_table, reuse_as_table) = ir_background_info.
+
+ir_background_info_init(ModuleInfo, PredInfo, ProcInfo, SharingTable,
+ ReuseTable) = BG :-
+ proc_info_get_headvars(ProcInfo, HeadVars),
+ BG = ir_background_info(ModuleInfo, PredInfo, ProcInfo,
+ SharingTable, ReuseTable, HeadVars).
+
+:- func analysis_info_init(pred_proc_id, sr_fixpoint_table) = analysis_info.
+
+analysis_info_init(PPId, FixpointTable) = Info :-
+ ReuseAs = sr_fixpoint_table_get_final_as(PPId, FixpointTable),
+ Info = analysis_info(sharing_as_init, ReuseAs, set.init, FixpointTable).
+
+ % When analysing disjuncts (or switches) each branch yields its own
+ % analysis information. This needs to be combined to form one single
+ % analysis information to continue the analysis with.
+ %
+:- pred analysis_info_combine(ir_background_info::in, list(analysis_info)::in,
+ sr_fixpoint_table::in, analysis_info::in, analysis_info::out) is det.
+
+analysis_info_combine(BaseInfo, AnalysisInfoList, FixpointTable,
+ !AnalysisInfo) :-
+ % If the AnalysisInfoList = [], then the disjunct was simply empty, hence
+ % nothing to be done. Otherwise, compute the lub of each of the components
+ % of analysis_info.
+ (
+ AnalysisInfoList = []
+ ;
+ AnalysisInfoList = [_|_],
+ list.foldl(analysis_info_lub(BaseInfo), AnalysisInfoList,
+ !AnalysisInfo),
+ !:AnalysisInfo = !.AnalysisInfo ^ fptable := FixpointTable
+ ).
+
+:- pred analysis_info_lub(ir_background_info::in, analysis_info::in,
+ analysis_info::in, analysis_info::out) is det.
+
+analysis_info_lub(BaseInfo, AnalysisInfo0, !AnalysisInfo):-
+ ModuleInfo = BaseInfo ^ module_info,
+ ProcInfo = BaseInfo ^ proc_info,
+ % Lub of the sharing
+ NewSharing = sharing_as_least_upper_bound(ModuleInfo, ProcInfo,
+ !.AnalysisInfo ^ sharing_as, AnalysisInfo0 ^ sharing_as),
+ % Lub of the reuse
+ NewReuse = reuse_as_least_upper_bound(ModuleInfo, ProcInfo,
+ !.AnalysisInfo ^ reuse_as, AnalysisInfo0 ^ reuse_as),
+ % Union of the static vars
+ NewStaticVars = set.union(!.AnalysisInfo ^ static_vars,
+ AnalysisInfo0 ^ static_vars),
+ !:AnalysisInfo = analysis_info(NewSharing, NewReuse, NewStaticVars,
+ !.AnalysisInfo ^ fptable).
+
+%-----------------------------------------------------------------------------%
+
+:- pred indirect_reuse_analyse_goal(ir_background_info::in, hlds_goal::in,
+ hlds_goal::out, analysis_info::in, analysis_info::out,
+ io::di, io::uo) is det.
+
+indirect_reuse_analyse_goal(BaseInfo, !Goal, !AnalysisInfo, !IO) :-
+ !.Goal = GoalExpr0 - GoalInfo0,
+ (
+ GoalExpr0 = conj(ConjType, Goals0),
+ list.map_foldl2(indirect_reuse_analyse_goal(BaseInfo), Goals0,
+ Goals, !AnalysisInfo, !IO),
+ GoalExpr = conj(ConjType, Goals),
+ !:Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = call(CalleePredId, CalleeProcId, CalleeArgs, _, _, _),
+ verify_indirect_reuse(BaseInfo, CalleePredId, CalleeProcId,
+ CalleeArgs, GoalInfo0, GoalInfo, !AnalysisInfo, !IO),
+ lookup_sharing_and_comb(BaseInfo ^ module_info, BaseInfo ^ proc_info,
+ BaseInfo ^ sharing_table, CalleePredId, CalleeProcId,
+ CalleeArgs, !.AnalysisInfo ^ sharing_as, NewSharing),
+ !:AnalysisInfo = !.AnalysisInfo ^ sharing_as := NewSharing,
+ GoalExpr = GoalExpr0,
+ !:Goal = GoalExpr - GoalInfo
+ ;
+ GoalExpr0 = generic_call(_GenDetails, _, _, _),
+ goal_info_get_context(GoalInfo0, Context),
+ context_to_string(Context, ContextString),
+ !:AnalysisInfo = !.AnalysisInfo ^ sharing_as :=
+ sharing_as_top_sharing_accumulate("generic call ("
+ ++ ContextString ++ ")",
+ !.AnalysisInfo ^ sharing_as)
+ ;
+ GoalExpr0 = unify(_, _, _, Unification, _),
+ % Record the statically constructed variables:
+ ( Unification = construct(Var, _, _, _,
+ construct_statically(_), _, _) ->
+ !:AnalysisInfo = !.AnalysisInfo ^ static_vars :=
+ set.insert(!.AnalysisInfo ^ static_vars, Var)
+ ;
+ true
+ ),
+ !:AnalysisInfo = !.AnalysisInfo ^ sharing_as :=
+ add_unify_sharing(BaseInfo ^ module_info, BaseInfo ^ proc_info,
+ Unification, GoalInfo0, !.AnalysisInfo ^ sharing_as)
+ ;
+ GoalExpr0 = disj(Goals0),
+ list.map2_foldl2(
+ indirect_reuse_analyse_disj(BaseInfo, !.AnalysisInfo),
+ Goals0, Goals, AnalysisInfoList, !.AnalysisInfo ^ fptable,
+ NewFixpointTable, !IO),
+ analysis_info_combine(BaseInfo, AnalysisInfoList, NewFixpointTable,
+ !AnalysisInfo),
+ GoalExpr = disj(Goals),
+ !:Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = switch(A, B, Cases0),
+ list.map2_foldl2(
+ indirect_reuse_analyse_case(BaseInfo, !.AnalysisInfo),
+ Cases0, Cases, AnalysisInfoList, !.AnalysisInfo ^ fptable,
+ NewFixpointTable, !IO),
+ analysis_info_combine(BaseInfo, AnalysisInfoList, NewFixpointTable,
+ !AnalysisInfo),
+ GoalExpr = switch(A, B, Cases),
+ !:Goal = GoalExpr - GoalInfo0
+ ;
+ % XXX
+ GoalExpr0 = not(_Goal)
+ ;
+ GoalExpr0 = scope(A, SubGoal0),
+ indirect_reuse_analyse_goal(BaseInfo, SubGoal0, SubGoal,
+ !AnalysisInfo, !IO),
+ GoalExpr = scope(A, SubGoal),
+ !:Goal = GoalExpr - GoalInfo0
+ ;
+ % Brief sketch:
+ % * AnalysisInfo0 --> IfGoal --> AnalysisInfoIfGoal,
+ % * AnalysisInfoIfGoal --> ThenGoal --> AnalysisInfoThenGoal,
+ % * update AnalysisInfo0 to include the latest state of the fixpoint
+ % table, yields AnalysisInfoElseGoal0
+ % * AnalysisInfoElseGoal0 --> ElseGoal --> AnalysisInfoElseGoal
+ % * and then compute the lub of AnalysisInfoThenGoal,
+ % and AnalysisInfoElseGoal. Make sure that the result contains
+ % the latest state of the fixpoint table, i.e., the one recorded
+ % in AnalysisInfoElseGoal.
+ GoalExpr0 = if_then_else(A, IfGoal0, ThenGoal0, ElseGoal0),
+ AnalysisInfo0 = !.AnalysisInfo,
+ indirect_reuse_analyse_goal(BaseInfo, IfGoal0, IfGoal,
+ AnalysisInfo0, AnalysisInfoIfGoal, !IO),
+ indirect_reuse_analyse_goal(BaseInfo, ThenGoal0, ThenGoal,
+ AnalysisInfoIfGoal, AnalysisInfoThenGoal, !IO),
+ AnalysisInfoElseGoal0 = AnalysisInfo0 ^ fptable :=
+ AnalysisInfoThenGoal ^ fptable,
+ indirect_reuse_analyse_goal(BaseInfo, ElseGoal0, ElseGoal,
+ AnalysisInfoElseGoal0, AnalysisInfoElseGoal, !IO),
+ analysis_info_lub(BaseInfo, AnalysisInfoThenGoal,
+ AnalysisInfoElseGoal, !:AnalysisInfo),
+ GoalExpr = if_then_else(A, IfGoal, ThenGoal, ElseGoal),
+ !:Goal = GoalExpr - GoalInfo0
+ ;
+ GoalExpr0 = foreign_proc(_Attrs, _ForeignPredId, _ForeignProcId,
+ _ForeignArgs, _, _),
+ % XXX User annotated structure sharing information is not yet
+ % supported.
+ goal_info_get_context(GoalInfo0, Context),
+ context_to_string(Context, ContextString),
+ !:AnalysisInfo = !.AnalysisInfo ^ sharing_as :=
+ sharing_as_top_sharing_accumulate(
+ "foreign_proc not handled yet (" ++ ContextString ++ ")",
+ !.AnalysisInfo ^ sharing_as)
+ ;
+ GoalExpr0 = shorthand(_),
+ unexpected(this_file, "indirect_reuse_analyse_goal: shorthand goal.")
+ ).
+
+ % Analyse each branch of a disjunction with respect to an input
+ % analysis_info, producing a resulting analysis_info, and possibly
+ % updating the state of the sr_fixpoint_table.
+ %
+:- pred indirect_reuse_analyse_disj(ir_background_info::in, analysis_info::in,
+ hlds_goal::in, hlds_goal::out, analysis_info::out, sr_fixpoint_table::in,
+ sr_fixpoint_table::out, io::di, io::uo) is det.
+
+indirect_reuse_analyse_disj(BaseInfo, AnalysisInfo0, Goal0, Goal, AnalysisInfo,
+ !FixpointTable, !IO) :-
+ % Replace the state of the fixpoint_table in AnalysisInfo0:
+ NewAnalysisInfo = AnalysisInfo0 ^ fptable := !.FixpointTable,
+ indirect_reuse_analyse_goal(BaseInfo, Goal0, Goal, NewAnalysisInfo,
+ AnalysisInfo, !IO),
+ !:FixpointTable = AnalysisInfo ^ fptable.
+
+ % Similar to indirect_reuse_analyse_disj.
+:- pred indirect_reuse_analyse_case(ir_background_info::in, analysis_info::in,
+ case::in, case::out, analysis_info::out, sr_fixpoint_table::in,
+ sr_fixpoint_table::out, io::di, io::uo) is det.
+
+indirect_reuse_analyse_case(BaseInfo, AnalysisInfo0, Case0, Case, AnalysisInfo,
+ !FixpointTable, !IO) :-
+ Case0 = case(ConsId, Goal0),
+ % Replace the state of the fixpoint_table in AnalysisInfo0:
+ NewAnalysisInfo = AnalysisInfo0 ^ fptable := !.FixpointTable,
+ indirect_reuse_analyse_goal(BaseInfo, Goal0, Goal, NewAnalysisInfo,
+ AnalysisInfo, !IO),
+ !:FixpointTable = AnalysisInfo ^ fptable,
+ Case = case(ConsId, Goal).
+
+%-----------------------------------------------------------------------------%
+
+:- pred verify_indirect_reuse(ir_background_info::in, pred_id::in, proc_id::in,
+ list(prog_var)::in, hlds_goal_info::in, hlds_goal_info::out,
+ analysis_info::in, analysis_info::out,
+ io::di, io::uo) is det.
+
+verify_indirect_reuse(BaseInfo, CalleePredId, CalleeProcId, CalleeArgs,
+ !GoalInfo, !AnalysisInfo, !IO):-
+ globals.io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
+ reuse_as_table_maybe_dump(VeryVerbose, BaseInfo ^ reuse_table, !IO),
+
+ ModuleInfo = BaseInfo ^ module_info,
+
+ % Check if the called procedure already has a reuse version (which can
+ % be the case if it is a procedure belonging to an imported module).
+ module_info_get_structure_reuse_info(ModuleInfo, ModuleReuseInfo),
+ ModuleReuseInfo = structure_reuse_info(ReuseMap),
+ ( map.search(ReuseMap, proc(CalleePredId, CalleeProcId), Result) ->
+ Result = proc(ReuseCalleePredId, ReuseCalleeProcId) - _Name,
+ CalleePPId = proc(ReuseCalleePredId, ReuseCalleeProcId),
+ passes_aux.write_proc_progress_message(
+ "%\t\tSuccess lookup in reuse map: ",
+ CalleePredId, CalleeProcId, ModuleInfo, !IO)
+ ;
+ CalleePPId = proc(CalleePredId, CalleeProcId)
+ ),
+
+ % Find the reuse information of the called procedure (or its explicit
+ % reuse version) in the reuse table:
+ lookup_reuse_as(BaseInfo, CalleePPId, !AnalysisInfo, FormalReuseAs),
+
+ (
+ % If there is no reuse, then nothing can be done.
+ reuse_as_no_reuses(FormalReuseAs)
+ ->
+ true
+ ;
+ reuse_as_all_unconditional_reuses(FormalReuseAs)
+ ->
+ % With unconditional reuse, we need to mark that the call is always
+ % a reuse call, yet without implying conditions.
+ reuse_as_add_unconditional(!.AnalysisInfo ^ reuse_as, NewReuseAs),
+ !:AnalysisInfo = !.AnalysisInfo ^ reuse_as := NewReuseAs,
+ goal_info_set_reuse(reuse(reuse_call(unconditional_reuse)),
+ !GoalInfo)
+ ;
+ % With a conditional reuse, we need to check the conditions. If they
+ % are satisfied, these conditions need to be translated to the callers
+ % environment. This translation can result in the reuse being
+ % unconditional (this is the case if the reused data structures are
+ % local to the procedure in which the call appears), or conditional.
+ (
+ % If the current sharing is top, then there is no use in
+ % verifying reuse explicitly, as we don't have any information
+ % anymore about existing (and therefore non-existing) sharing
+ % pairs. In this case, reuse is not allowed.
+ sharing_as_is_top(!.AnalysisInfo ^ sharing_as)
+ ->
+ % no need to update anything
+ true
+ ;
+ verify_indirect_reuse_2(BaseInfo, !.AnalysisInfo, !.GoalInfo,
+ CalleePPId, CalleeArgs, FormalReuseAs,
+ NewAndRenamedReuseAs),
+ (
+ reuse_as_no_reuses(NewAndRenamedReuseAs)
+ ->
+ % Don't do anything.
+ true
+ ;
+ reuse_as_all_unconditional_reuses(NewAndRenamedReuseAs)
+ ->
+ % Update reuse information and goal_info:
+ reuse_as_add_unconditional(!.AnalysisInfo ^ reuse_as,
+ NewReuseAs),
+ !:AnalysisInfo = !.AnalysisInfo ^ reuse_as := NewReuseAs,
+ goal_info_set_reuse(reuse(reuse_call(unconditional_reuse)),
+ !GoalInfo)
+ ;
+ % Update reuse information and goal_info:
+ reuse_as_least_upper_bound(BaseInfo ^ module_info,
+ BaseInfo ^ proc_info, !.AnalysisInfo ^ reuse_as,
+ NewAndRenamedReuseAs, NewReuseAs),
+ !:AnalysisInfo = !.AnalysisInfo ^ reuse_as := NewReuseAs,
+ goal_info_set_reuse(
+ potential_reuse(reuse_call(conditional_reuse)),
+ !GoalInfo)
+ )
+ )
+ ).
+
+:- pred lookup_reuse_as(ir_background_info::in, pred_proc_id::in,
+ analysis_info::in, analysis_info::out, reuse_as::out) is det.
+
+lookup_reuse_as(BaseInfo, PPId, !AnalysisInfo, ReuseAs) :-
+ (
+ % Check in the fixpoint table
+ sr_fixpoint_table_get_as(PPId, ReuseAs0, !.AnalysisInfo ^ fptable,
+ NewFixpointTable)
+ ->
+ ReuseAs = ReuseAs0,
+ !:AnalysisInfo = !.AnalysisInfo ^ fptable := NewFixpointTable
+ ;
+ % Or check in the reuse table
+ ReuseAs0 = reuse_as_table_search(PPId, BaseInfo ^ reuse_table)
+ ->
+ ReuseAs = ReuseAs0
+ ;
+ ReuseAs = reuse_as_init
+ ).
+
+ % Verify whether the caller's environment satisfies the reuse conditions
+ % stated in the reuse description of the called procedure. If this
+ % succeeds, then translate those reuse conditions to this caller's
+ % environment.
+ %
+ % Pre-conditions: The sharing is not top, and reuse_as contains at least
+ % one conditional reuse condition.
+ %
+:- pred verify_indirect_reuse_2(ir_background_info::in, analysis_info::in,
+ hlds_goal_info::in, pred_proc_id::in, list(prog_var)::in, reuse_as::in,
+ reuse_as::out) is det.
+
+verify_indirect_reuse_2(BaseInfo, AnalysisInfo, GoalInfo, CalleePPId,
+ CalleeArgs, FormalReuseAs, NewReuseAs):-
+ ModuleInfo = BaseInfo ^ module_info,
+ PredInfo = BaseInfo ^ pred_info,
+ ProcInfo = BaseInfo ^ proc_info,
+ SharingAs = AnalysisInfo ^ sharing_as,
+ proc_info_get_vartypes(ProcInfo, ActualVarTypes),
+ pred_info_get_typevarset(PredInfo, ActualTVarset),
+ list.map(map.lookup(ActualVarTypes), CalleeArgs, CalleeTypes),
+ reuse_as_rename_using_module_info(ModuleInfo, CalleePPId,
+ CalleeArgs, CalleeTypes, ActualTVarset, FormalReuseAs, ActualReuseAs),
+ LiveData = livedata_init_at_goal(ModuleInfo, ProcInfo, GoalInfo,
+ SharingAs),
+ ProjectedLiveData = livedata_project(CalleeArgs, LiveData),
+ (
+ % Given the preconditions, livedata wil not be empty, and
+ % reuse_as contains at least one reuse condition.
+ reuse_as_satisfied(ModuleInfo, ProcInfo, ProjectedLiveData,
+ SharingAs, set.to_sorted_list(AnalysisInfo ^ static_vars),
+ ActualReuseAs)
+ ->
+ LuData = list.map(datastruct_init,
+ set.to_sorted_list(set.union(goal_info_get_lfu(GoalInfo),
+ goal_info_get_lbu(GoalInfo)))),
+ NewReuseAs = reuse_as_from_called_procedure_to_local_reuse_as(
+ ModuleInfo, ProcInfo, BaseInfo ^ headvars, LuData, SharingAs,
+ ActualReuseAs)
+ ;
+ NewReuseAs = reuse_as_init % no reuse
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred update_reuse_in_table(sr_fixpoint_table::in, pred_proc_id::in,
+ reuse_as_table::in, reuse_as_table::out) is det.
+
+update_reuse_in_table(FixpointTable, PPId, !ReuseTable) :-
+ reuse_as_table_set(PPId,
+ sr_fixpoint_table_get_final_as(PPId, FixpointTable),
+ !ReuseTable).
+
+%-----------------------------------------------------------------------------%
+%
+% Structure reuse fixpoint table.
+%
+
+:- type sr_fixpoint_table == fixpoint_table(pred_proc_id, reuse_as).
+
+ % Initialise the fixpoint table for the given set of pred_proc_id's.
+ %
+:- func sr_fixpoint_table_init(list(pred_proc_id), reuse_as_table)
+ = sr_fixpoint_table.
+
+ % Add the results of a new analysis pass to the already existing
+ % fixpoint table.
+ %
+:- pred sr_fixpoint_table_new_run(sr_fixpoint_table::in,
+ sr_fixpoint_table::out) is det.
+
+ % The fixpoint table keeps track of the number of analysis passes. This
+ % predicate returns this number.
+ %
+:- func sr_fixpoint_table_which_run(sr_fixpoint_table) = int.
+
+ % A fixpoint is reached if all entries in the table are stable,
+ % i.e. haven't been modified by the last analysis pass.
+ %
+:- pred sr_fixpoint_table_stable(sr_fixpoint_table::in) is semidet.
+
+ % Give a string description of the state of the fixpoint table.
+ %
+:- func sr_fixpoint_table_description(sr_fixpoint_table) = string.
+
+ % Enter the newly computed structure reuse description for a given
+ % procedure. If the description is different from the one that was
+ % already stored for that procedure, the stability of the fixpoint
+ % table is set to "unstable".
+ % Software error if the procedure is not in the fixpoint table.
+ %
+:- pred sr_fixpoint_table_new_as(module_info::in, proc_info::in,
+ pred_proc_id::in, reuse_as::in,
+ sr_fixpoint_table::in, sr_fixpoint_table::out) is det.
+
+ % Retrieve the structure reuse information for a given pred_proc_id.
+ %
+ % If the id is part of the fixpoint table, but does not yet record any
+ % reuse information about that pred_proc_id, then this means that the
+ % set of pred_proc_id's to which the fixpoint table relates is mutually
+ % recursive, hence the table is characterised as recursive.
+ %
+ % If the id is not part of the fixpoint table: fail.
+ %
+:- pred sr_fixpoint_table_get_as(pred_proc_id::in, reuse_as::out,
+ sr_fixpoint_table::in, sr_fixpoint_table::out) is semidet.
+
+:- func sr_fixpoint_table_get_short_description(pred_proc_id,
+ sr_fixpoint_table) = string.
+
+ % Retrieve the structure reuse information without changing the table.
+ % To be used after fixpoint has been reached.
+ % Software error if the procedure is not in the table.
+ %
+:- func sr_fixpoint_table_get_final_as(pred_proc_id,
+ sr_fixpoint_table) = reuse_as.
+
+ % Same as sr_fixpoint_table_get_final_as, yet fails instead of aborting
+ % if the procedure is not in the table.
+ %
+:- func sr_fixpoint_table_get_final_as_semidet(pred_proc_id,
+ sr_fixpoint_table) = reuse_as is semidet.
+
+%-----------------------------------------------------------------------------%
+
+:- func get_reuse_as(reuse_as_table, pred_proc_id) = reuse_as.
+
+get_reuse_as(ReuseTable, PPId) = ReuseAs :-
+ ( ReuseAs0 = reuse_as_table_search(PPId, ReuseTable) ->
+ ReuseAs = ReuseAs0
+ ;
+ ReuseAs = reuse_as_init
+ ).
+
+sr_fixpoint_table_init(Keys, ReuseTable) = Table :-
+ Table = init_fixpoint_table(get_reuse_as(ReuseTable), Keys).
+
+
+sr_fixpoint_table_new_run(!Table) :-
+ fixpoint_table.new_run(!Table).
+
+sr_fixpoint_table_which_run(Tin) = fixpoint_table.which_run(Tin).
+
+sr_fixpoint_table_stable(Table) :-
+ fixpoint_table.fixpoint_reached(Table).
+
+sr_fixpoint_table_description(Table) = fixpoint_table.description(Table).
+
+sr_fixpoint_table_new_as(ModuleInfo, ProcInfo, Id, ReuseAs, !Table) :-
+ add_to_fixpoint_table(reuse_as_subsumed_by(ModuleInfo, ProcInfo),
+ Id, ReuseAs, !Table).
+
+sr_fixpoint_table_get_as(PPId, ReuseAs, !Table) :-
+ get_from_fixpoint_table(PPId, ReuseAs, !Table).
+
+sr_fixpoint_table_get_short_description(PPId, Table) = Descr :-
+ ( fixpoint_table.is_recursive(Table) -> Rec = "(r)" ; Rec = "(-)"),
+ ( As = sr_fixpoint_table_get_final_as_semidet(PPId, Table) ->
+ Descr0 = reuse_as_short_description(As)
+ ;
+ Descr0 = "-"
+ ),
+ Descr = Descr0 ++ " " ++ Rec.
+
+sr_fixpoint_table_get_final_as(PPId, T) =
+ get_from_fixpoint_table_final(PPId, T).
+
+sr_fixpoint_table_get_final_as_semidet(PPId, T) =
+ get_from_fixpoint_table_final_semidet(PPId, T).
+
+%------------------------------------------------------------------------------%
+
+:- func this_file = string.
+
+this_file = "structure_reuse.indirect.m".
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
Index: compiler/structure_reuse.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_reuse.m,v
retrieving revision 1.2
diff -u -d -r1.2 structure_reuse.m
--- compiler/structure_reuse.m 10 May 2006 15:20:57 -0000 1.2
+++ compiler/structure_reuse.m 18 May 2006 12:01:14 -0000
@@ -20,7 +20,7 @@
:- include_module lfu.
:- include_module lbu.
:- include_module direct.
- %:- include_module indirect.
+ :- include_module indirect.
% :- include_module util.
:- include_module domain.
Index: compiler/structure_sharing.analysis.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_sharing.analysis.m,v
retrieving revision 1.11
diff -u -d -r1.11 structure_sharing.analysis.m
--- compiler/structure_sharing.analysis.m 10 May 2006 10:56:56 -0000 1.11
+++ compiler/structure_sharing.analysis.m 18 May 2006 12:01:14 -0000
@@ -54,7 +54,6 @@
:- import_module transform_hlds.dependency_graph.
:- import_module bool.
-:- import_module io.
:- import_module list.
:- import_module map.
:- import_module maybe.
@@ -209,16 +208,16 @@
proc_info_get_goal(ProcInfo, Goal),
analyse_goal(ModuleInfo, PredInfo, ProcInfo, SharingTable, Goal,
!FixpointTable, !Sharing, !IO),
- FullAsDescr = short_description(!.Sharing),
+ FullAsDescr = sharing_as_short_description(!.Sharing),
sharing_as_project(HeadVars, !Sharing),
- ProjAsDescr = short_description(!.Sharing),
+ ProjAsDescr = sharing_as_short_description(!.Sharing),
domain.apply_widening(ModuleInfo, ProcInfo, WideningLimit,
WideningDone, !Sharing),
(
WideningDone = yes,
- WidenAsDescr = short_description(!.Sharing)
+ WidenAsDescr = sharing_as_short_description(!.Sharing)
;
WideningDone = no,
WidenAsDescr = "-"
@@ -496,7 +495,7 @@
ss_fixpoint_table_get_short_description(PPId, Table) = Descr :-
( As = ss_fixpoint_table_get_final_as_semidet(PPId, Table) ->
- Descr = short_description(As)
+ Descr = sharing_as_short_description(As)
;
Descr = "-"
).
Index: compiler/structure_sharing.domain.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_sharing.domain.m,v
retrieving revision 1.8
diff -u -d -r1.8 structure_sharing.domain.m
--- compiler/structure_sharing.domain.m 10 May 2006 10:56:57 -0000 1.8
+++ compiler/structure_sharing.domain.m 18 May 2006 12:01:17 -0000
@@ -87,7 +87,7 @@
% Return a short description of the sharing information.
%
-:- func short_description(sharing_as) = string.
+:- func sharing_as_short_description(sharing_as) = string.
% Projection operation.
% This operation reduces the sharing information to information
@@ -98,6 +98,7 @@
%
:- pred sharing_as_project(prog_vars::in,
sharing_as::in, sharing_as::out) is det.
+:- func sharing_as_project(prog_vars, sharing_as) = sharing_as.
:- pred sharing_as_project_set(set(prog_var)::in,
sharing_as::in, sharing_as::out) is det.
@@ -113,10 +114,11 @@
% ActualVars, ActualTypes, ActualTVarset, FormalSharing, ActualSharing):
%
% Renaming of the formal description of data structure sharing to the
- % actual description of the sharing. The formal information is given
- % using the module information. A list of variables and types is used as
- % the actual variables and types.
- % recorded in the module info.
+ % actual description of the sharing. The information about the formal
+ % variables needs to be extracted from the module information.
+ % A list of variables and types is used as the actual variables and types.
+ % The type variables set in the actual context must also be specified.
+ %
%
:- pred sharing_as_rename_using_module_info(module_info::in,
pred_proc_id::in, prog_vars::in, list(mer_type)::in, tvarset::in,
@@ -175,6 +177,8 @@
%
:- func extend_datastruct(module_info, proc_info, sharing_as, datastruct)
= list(datastruct).
+:- func extend_datastructs(module_info, proc_info, sharing_as,
+ list(datastruct)) = list(datastruct).
% apply_widening(ModuleInfo, ProcInfo, WideningLimit, WideningDone,
% SharingIn, SharingOut):
@@ -230,6 +234,15 @@
%-----------------------------------------------------------------------------%
+ % Lookup the sharing information of a called procedure (given its
+ % pred_id and proc_id), and combine it with the already existing
+ % sharing information.
+ %
+:- pred lookup_sharing_and_comb(module_info::in, proc_info::in,
+ sharing_as_table::in, pred_id::in, proc_id::in, prog_vars::in,
+ sharing_as::in, sharing_as::out) is det.
+
+
% Lookup the sharing information in the sharing table, or if it is not
% in there, try to predict it using the information available in the
% module_info.
@@ -274,6 +287,7 @@
:- import_module parse_tree.prog_type_subst.
:- import_module transform_hlds.ctgc.datastruct.
:- import_module transform_hlds.ctgc.selector.
+:- import_module transform_hlds.ctgc.util.
:- import_module assoc_list.
:- import_module int.
@@ -284,6 +298,7 @@
:- import_module string.
:- import_module svmap.
:- import_module svset.
+:- import_module varset.
%-----------------------------------------------------------------------------%
@@ -313,9 +328,9 @@
sharing_as_size(bottom) = 0.
sharing_as_size(real_as(SharingSet)) = sharing_set_size(SharingSet).
-short_description(bottom) = "b".
-short_description(top(_)) = "t".
-short_description(real_as(SharingSet)) =
+sharing_as_short_description(bottom) = "b".
+sharing_as_short_description(top(_)) = "t".
+sharing_as_short_description(real_as(SharingSet)) =
string.from_int(sharing_set_size(SharingSet)).
% inproject = projection such that result contains information about
@@ -330,6 +345,8 @@
sharing_as_project(ListVars, !SharingAs) :-
sharing_as_project_with_type(inproject, ListVars, !SharingAs).
+sharing_as_project(ListVars, SharingAs) = NewSharingAs :-
+ sharing_as_project(ListVars, SharingAs, NewSharingAs).
:- pred sharing_as_project_with_type(projection_type::in, prog_vars::in,
sharing_as::in, sharing_as::out) is det.
@@ -361,26 +378,9 @@
sharing_as_rename_using_module_info(ModuleInfo, PPId, ActualVars, ActualTypes,
ActualTVarset, FormalSharing, ActualSharing):-
- module_info_pred_proc_info(ModuleInfo, PPId, PredInfo, ProcInfo),
-
- % head variables.
- proc_info_get_headvars(ProcInfo, FormalVars),
- map.from_corresponding_lists(FormalVars, ActualVars, Dict),
-
- % types of the head variables.
- pred_info_get_arg_types(PredInfo, FormalTVarset, _, FormalTypes),
-
- % (this is a bit that was inspired by the code for
- % arg_type_list_subsumes/6)
- tvarset_merge_renaming(ActualTVarset, FormalTVarset,_TVarSet1, Renaming),
- apply_variable_renaming_to_type_list(Renaming, FormalTypes,
- RenFormalTypes),
-
- ( type_list_subsumes(RenFormalTypes, ActualTypes, TypeSubstitution) ->
- sharing_as_rename(Dict, TypeSubstitution, FormalSharing, ActualSharing)
- ;
- unexpected(this_file, "Types are supposed to be unifiable.")
- ).
+ sharing_as_rename(get_variable_renaming(ModuleInfo, PPId, ActualVars),
+ get_type_substitution(ModuleInfo, PPId, ActualTypes, ActualTVarset),
+ FormalSharing, ActualSharing).
sharing_as_comb(ModuleInfo, ProcInfo, NewSharing, OldSharing) = ResultSharing :-
(
@@ -631,7 +631,7 @@
= Datastructures :-
(
SharingAs = bottom,
- Datastructures = []
+ Datastructures = [Datastruct]
;
SharingAs = real_as(SharingSet),
Datastructures = sharing_set_extend_datastruct(ModuleInfo, ProcInfo,
@@ -641,6 +641,14 @@
unexpected(this_file, "extend_datastruct with top sharing set.")
).
+extend_datastructs(ModuleInfo, ProcInfo, SharingAs, Datastructs)
+ = ExtendedDatastructs :-
+ DataLists = list.map(extend_datastruct(ModuleInfo, ProcInfo,
+ SharingAs), Datastructs),
+ ExtendedDatastructs = list.foldl(
+ datastruct_lists_least_upper_bound(ModuleInfo, ProcInfo),
+ DataLists, []).
+
apply_widening(ModuleInfo, ProcInfo, WideningLimit, WideningDone, !Sharing):-
(
!.Sharing = bottom,
@@ -696,6 +704,26 @@
sharing_as_table_search(PPId, Table) = Table ^ elem(PPId).
sharing_as_table_set(PPId, Sharing, !Table) :-
!:Table = !.Table ^ elem(PPId) := Sharing.
+
+%-----------------------------------------------------------------------------%
+
+lookup_sharing_and_comb(ModuleInfo, ProcInfo, SharingTable, PredId, ProcId,
+ ActualVars, !Sharing):-
+ PPId = proc(PredId, ProcId),
+
+ lookup_sharing_or_predict(ModuleInfo, SharingTable, PPId, FormalSharing),
+
+ proc_info_get_vartypes(ProcInfo, VarTypes),
+ list.map(map.lookup(VarTypes), ActualVars, ActualTypes),
+
+ % XXX To be checked!
+ ActualTVarset = varset.init,
+ sharing_as_rename_using_module_info(ModuleInfo, PPId,
+ ActualVars, ActualTypes, ActualTVarset, FormalSharing,
+ ActualSharing),
+
+ !:Sharing = sharing_as_comb(ModuleInfo, ProcInfo,
+ ActualSharing, !.Sharing).
lookup_sharing_or_predict(ModuleInfo, SharingTable, PPId, SharingAs) :-
(
--
nancy.mazur at cs.kuleuven.ac.be ------------ Katholieke Universiteit Leuven -
tel: +32-16-327596 - fax: +32-16-327996 ------- Dept. of Computer Science -
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
--------------------------------------------------------------------------
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