[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