[m-rev.] for review: [CTGC] direct structure reuse analysis (1/2)
Julien Fischer
juliensf at cs.mu.OZ.AU
Tue May 2 17:20:34 AEST 2006
On Thu, 27 Apr 2006, Nancy Mazur wrote:
> Hi,
>
> Here is a big chunk from the structure reuse analysis: the direct reuse
> analysis.
>
> Still missing (mainly):
> - (structure reuse) indirect reuse analysis;
> - (structure reuse) the definition of the public representation for
> reuse conditions and manipulating, printing and whatever operations
> needed on that representation;
> - generating/loading structure reuse pragma's (trans_opt);
> - (structure sharing) pre-annotating foreign code with structure
> sharing information;
>
> There are quite some "XXX"s. But I'd like to be able to submit all this
> material before going on.
>
> Anybody in for reviewing this?
> Nancy
>
>
> ===================================================================
>
>
> Estimated hours taken: 20
> Branches: main
>
> Provide the direct reuse analysis part of the structure reuse analysis (which
> itself is part of the CTGC system).
>
> compiler/ctgc.datastruct.m:
> compiler/ctgc.util.m:
> Additional predicates.
>
> compiler/ctgc.m:
> Add structure reuse module.
>
> compiler/handle_options.m:
> compiler/options.m:
> Add new options "structure_reuse_analysis" and related ones.
>
> compiler/handle_options.m:
> compiler/hlds_out.m:
> Add dump option "R" to dump structure reuse related information
> in the hlds_dump files.
>
> compiler/hlds_goal.m:
> Types to record structure reuse information at the level of each
> goal.
> Additional "case_get_goal" function to extract the goal from an case.
>
> compiler/mercury_compile.m:
> Add structure reuse analysis as a new compiler stage.
>
> compiler/structure_reuse.analysis.m:
> The top level analysis predicates.
>
> compiler/structure_reuse.direct.m:
> compiler/structure_reuse.direct.choose_reuse.m:
> compiler/structure_reuse.direct.detect_garbage.m:
> Direct reuse analysis is split into 2 steps: determining when and how
> data structures become garbage, and then choosing how these dead
> data structures might best be reused.
>
> compiler/structure_reuse.domain.m:
> The abstract domain for keeping track of reuse conditions, the main
> domain in the structure reuse analysis.
>
> compiler/structure_reuse.lbu.m:
> compiler/structure_reuse.lfu.m:
> To determine whether data structures become dead or not, one needs to
> know which variables in a goal are needed with respect to forward
> execution (lfu = local forward use), and backward execution, i.e.
> backtracking (lbu = local backward use). These two modules provide
> the necessary functionality to pre-annotate the goals with lfu and
> lbu information.
>
> compiler/structure_sharing.analysis.m:
> compiler/structure_sharing.domain.m:
> Remove the structure sharing table from the interface of the analysis
> predicate in structure_sharing.analysis.m;
> Move predicates to structure_sharing.domain.m so that they become
> more easily accessible for the structure_reuse modules.
...
> Index: compiler/ctgc.datastruct.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/ctgc.datastruct.m,v
> retrieving revision 1.5
> diff -u -d -r1.5 ctgc.datastruct.m
> --- compiler/ctgc.datastruct.m 27 Mar 2006 09:36:04 -0000 1.5
> +++ compiler/ctgc.datastruct.m 27 Apr 2006 09:29:45 -0000
> @@ -133,6 +137,17 @@
> datastruct_subsumed_by_list(ModuleInfo, ProcInfo, Data0, Rest)
> ).
>
> +datastructs_subsumed_by_list(ModuleInfo, ProcInfo, PerhapsSubsumedData,
> + Data) :-
> + list.takewhile(datastructs_subsume_datastruct(ModuleInfo, ProcInfo, Data),
> + PerhapsSubsumedData, _, NotSubsumed),
> + NotSubsumed = [].
> +
> +:- pred datastructs_subsume_datastruct(module_info::in, proc_info::in,
> + list(datastruct)::in, datastruct::in) is semidet.
We usually leave a blank line between the predicate declaration and
its definition.
> +datastructs_subsume_datastruct(ModuleInfo, ProcInfo, Datastructs, Data):-
> + datastruct_subsumed_by_list(ModuleInfo, ProcInfo, Data, Datastructs).
> +
> datastruct_apply_widening(ModuleInfo, ProcInfo, !Data) :-
> Var = !.Data ^ sc_var,
> Sel0 = !.Data ^ sc_selector,
> @@ -140,6 +155,12 @@
> map.lookup(VarTypes, Var, Type),
> selector_apply_widening(ModuleInfo, Type, Sel0, Sel),
> !:Data = datastruct_init_with_selector(Var, Sel).
...
> Index: compiler/hlds_goal.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
> retrieving revision 1.155
> diff -u -d -r1.155 hlds_goal.m
> --- compiler/hlds_goal.m 20 Apr 2006 05:36:52 -0000 1.155
> +++ compiler/hlds_goal.m 27 Apr 2006 09:29:59 -0000
> @@ -769,6 +769,8 @@
> hlds_goal % goal to execute if match succeeds.
> ).
>
> +:- func case_get_goal(case) = hlds_goal.
> +
Why not just give the fields in the case structure names and use the
automatically generated field access function to retrieve the goal.
e.g.
:- type case --->
case(
case_functor :: cons_id,
case_goal :: hlds_goal
).
> %-----------------------------------------------------------------------------%
> %
> % Information for all kinds of goals
> @@ -1072,6 +1074,91 @@
>
> %-----------------------------------------------------------------------------%
> %
> +% Types and get/set predicates for the CTGC related information stored for each
> +% goal.
> +%
> +
> +
> + % Information describing possible kinds of reuse on a per goal basis.
> + % - 'empty': before CTGC analysis, every goal is annotated with the reuse
> + % description 'empty', ie. no information about any reuse.
s/ie./i.e./
> + % - 'potential_reuse': the value 'potential_reuse' states that in a reuse
> + % version of the procedure to which the goal belongs, this goal may safely
> + % be replaced by a goal implementing structure reuse.
> + % - 'reuse': the value 'reuse' states that in the current procedure (either
> + % the specialised reuse version of a procedure, or the original procedure
> + % itself) the current goal can safely be replaced by a goal performing
> + % structure reuse.
> + % - 'missed_reuse': the value 'missed_reuse' gives some feedback when an
> + % opportunity for reuse was missed for some reason (only used for calls).
> + %
> +:- type reuse_description
> + ---> empty
> + ; missed_reuse(list(missed_message))
> + ; potential_reuse(short_reuse_description)
> + ; reuse(short_reuse_description).
> +
> + % A short description of the kind of reuse allowed in the associated
> + % goal:
> + % - 'cell_died' (only relevant for deconstructions): states that the cell
> + % of the deconstruction becomes dead after that deconstruction.
> + % - 'cell_reused' (only relevant for constructions): states that it is
> + % allowed to reuse a previously discovered dead term for constructing a
> + % new term in the given construction. Details of which term is reused are
> + % recorded.
> + % - 'reuse_call' (only applicable to procedure calls): the called
> + % procedure is an optimised procedure w.r.t. CTGC. Records whether the
> + % call is conditional or not.
> + %
> +:- type short_reuse_description
> + ---> cell_died
> + ; cell_reused(
> + prog_var, % The dead variable selected
> + % for reusing.
> + is_conditional, % states if the reuse is conditional.
> + list(cons_id), % What are the possible cons_ids that the
> + % variable to be reused can have.
> + list(needs_update)
> + % Which of the fields of the cell to be
> + % reused already contain the correct value.
> + )
> + ; reuse_call(is_conditional).
> +
> +:- type is_conditional
> + ---> conditional_reuse
> + ; unconditional_reuse.
> +
Add a comment describing the above type.
> +:- type needs_update
> + ---> needs_update
> + ; does_not_need_update.
> +
> +:- type missed_message == string.
> +
...
> @@ -2243,14 +2330,16 @@
>
> :- type hlds_goal_extra_info
> ---> extra_info(
> - extra_info_ho_vals :: ho_values
> + extra_info_ho_vals :: ho_values,
> + maybe_reuse :: maybe(ctgc_info)
For consistency the field name should be `extra_info_maybe_reuse'
(perhaps `extra_info_maybe_ctgc_info' would be better)?
...
> Index: compiler/options.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
> retrieving revision 1.511
> diff -u -d -r1.511 options.m
> --- compiler/options.m 26 Apr 2006 03:05:38 -0000 1.511
> +++ compiler/options.m 27 Apr 2006 09:30:36 -0000
> @@ -530,6 +530,9 @@
> % Stuff for the CTGC system (structure sharing / structure reuse).
> ; structure_sharing_analysis
> ; structure_sharing_widening
> + ; structure_reuse_analysis
> + ; structure_reuse_constraint
> + ; structure_reuse_constraint_arg
>
> % Stuff for the new termination analyser.
> ; termination2
> @@ -1149,6 +1152,9 @@
> verbose_check_termination - bool(no),
> structure_sharing_analysis - bool(no),
> structure_sharing_widening - int(0),
> + structure_reuse_analysis - bool(no),
> + structure_reuse_constraint - string("within_n_cells_difference"),
> + structure_reuse_constraint_arg - int(0),
> termination - bool(no),
> termination_single_args - int(0),
> termination_norm - string("total"),
> @@ -1981,6 +1987,12 @@
> % CTGC related options.
> long_option("structure-sharing", structure_sharing_analysis).
> long_option("structure-sharing-widening", structure_sharing_widening).
> +long_option("structure-reuse", structure_reuse_analysis).
> +long_option("ctgc", structure_reuse_analysis).
> +long_option("structure-reuse-constraint", structure_reuse_constraint).
> +long_option("ctgc-constraint", structure_reuse_constraint).
> +long_option("structure-reuse-constraint-arg", structure_reuse_constraint_arg).
> +long_option("ctgc-constraint-arg", structure_reuse_constraint_arg).
You must also update the predicate option_defaults_2 in order to
provide default values for the new options.
> @@ -3197,7 +3209,23 @@
> "--structure-sharing-widening <n>",
> "\tPerform widening when the set of structure sharing pairs becomes",
> "\tlarger than <n>. When n=0, widening is not enabled.",
> - "\t(default: 0)."
> + "\t(default: 0).",
> + "--structure-reuse, --ctgc",
> + "\tPerform structure reuse analysis for all encountered",
> + "\tpredicates (Compile Time Garbage Collection).",
Just "Perform structure reuse analysis" would be sufficient, I'm not
sure what you mean by "encountered predicates" anyway.
> + "--structure-reuse-constraint, --ctgc-constraint",
> + "\tConstraint on the way we allow structure reuse. Either reuse",
> + "\tis only allowed for terms with the same type and same constructor",
> + "\t(option same_cons_id), or reuse is allowed between terms of",
> + "\tdifferent constructors as long as the difference between the",
> + "\tarities does not exceed a certain threshold (option ",
> + "\twithin_n_cells_difference(n), where n specifies the threshold,",
> + "\tn needs to be set using --structure-reuse-constraint-arg).",
> + "\t(default: within_n_cells_difference(0))",
To be consistent with the way the rest of the options are documented,
that should really be something like:
--structure-reuse-constraint {same_cons_id, within_n_cells_difference(n)}
(See the documentation of the option `--termination-norm' for an
example.)
> + "--structure-reuse-constraint-arg, --ctgc-constraint-arg",
> + "\tSpecify the allowed difference in arities between the terms that",
> + "\tcan be reused, and the terms that reuse these terms.",
> + "\t(default: 0)"
> ]).
So the arities of the terms are allowed to differ up to that limit?
In that case I suggest "Specify the maximum difference in arities ...".
> Index: compiler/structure_reuse.analysis.m
> ===================================================================
> RCS file: compiler/structure_reuse.analysis.m
> diff -N compiler/structure_reuse.analysis.m
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ compiler/structure_reuse.analysis.m 27 Apr 2006 09:30:36 -0000
> @@ -0,0 +1,135 @@
> +%-----------------------------------------------------------------------------%
> +% 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: structure_reuse.analysis.m
> +% Main authors: nancy
> +%
> +% Implementation of the structure reuse analysis (compile-time garbage
> +% collection system): each procedure is analysed to see whether some
> +% of the terms it manipulates becomes garbage thus making it possible
s/becomes/become/
> +% to reuse that garbage straight away for creating new terms.
> +%
> +% Structure reuse is broken up into three phases:
> +% * the direct reuse analysis (structure_reuse.direct.m)
> +% * the indirect analysis (structure_reuse.indirect.m)
> +% * and the generation of the optimised procedures.
> +%
You need to add something like:
The following example shows instances of direct and indirect
use:
> +% list__append(H1, H2, H3) :-
> +% (
> +% H1 => [],
> +% H3 := H2
> +% ;
> +% % Cell H1 dies provided some condition about the
> +% % structure sharing of H1 is true. A deconstruction
> +% % generating a dead cell, followed by a
> +% % construction reusing that cell, is called a direct
> +% % reuse.
> +% H1 => [X | Xs],
> +%
> +% % If the condition about the structure sharing of H1
> +% % is true then we can call the version of list__append
> +% % which does reuse. Calling the optimised version here leads
> +% % to a new condition to be met by the headvars of any
> +% % call to the resulting optimised version of append.
> +% % This is an indirect reuse.
> +% list__append(Xs, H2, Zs),
> +%
> +% % Reuse the dead cell H1. This is a direct reuse.
> +% H3 <= [X | Zs]
> +% ).
> +%
...
> Index: compiler/structure_reuse.direct.choose_reuse.m
> ===================================================================
> RCS file: compiler/structure_reuse.direct.choose_reuse.m
> diff -N compiler/structure_reuse.direct.choose_reuse.m
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ compiler/structure_reuse.direct.choose_reuse.m 27 Apr 2006 09:30:40 -0000
> @@ -0,0 +1,1363 @@
> +%-----------------------------------------------------------------------------%
> +% 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: structure_reuse.direct.choose_reuse.m
> +% Main authors: nancy
> +%
> +% Given a dead cell table listing the deconstructions that may leave garbage
> +% (dead cells), we compute the concrete assignements of which constructions can
s/assignements/assignments/
> +% profit of these dead cells. Obviously, we want to find those assignments
s/of/from/
> +% which result in the 'best' form of memory reuse possible for the given goals.
> +%
> +% Hence, the assignment problem is translated into a mapping problem (inspired
> +% from Debray's paper: "On copy avoidance in single assignment languages", and
> +% restricted to reuse of dead cells by at most one new cell).
> +%
> +% When assigning constructions to dead deconstructions, a table is first
> +% computed. For each dead cell, a value is computed that reflects the gain
> +% a reuse might bring, and the list of constructions involved with reusing it.
> +% The cell with highest value is selected first, the according constructions
> +% are annotated, and the table is recomputed. This process is repeated until
> +% no reusable dead deconstructions are left.
> +%
> +% The value of a dead cell (a specific deconstruction) is computed taking
> +% into account the call graph which can be simplified to take only into account
> +% construction-unifications, conjunctions, and disjunctions.
Does it also take calls into account?
> +% The source of the graph is the deconstruction, the leaves are
> +% either constructions, or empty. The branches are either conjunctions
> +% or disjunctions.
...
> +% The value of the dead cell is then computed as follows:
> +% - value of a conjunction = maximum of the values of each of the
> +% conjunct branches.
> +% Intuitively: if a dead deconstruction is followed by
> +% two constructions which might reuse the dead cell: pick
> +% the one which allows the most potential gain.
> +% - value of a disjunction = average of the value of each of the
> +% disjunct branches.
> +% Intuitively: if a dead deconstruction is followed by
> +% a disjunction with 2 disjuncts. If reuse is only possible
> +% in one of the branches, allowing this reuse means that
> +% a priori reuse will occur in only 50% of the cases.
> +% The value of the disjunct should take this into account.
> +% Without precise notion of which branches are executed
> +% more often, taking the simple average of the values is
> +% a good approximation.
> +% - value of a construction = a value that takes into account
> +% the cost of constructing a new cell and compares it
> +% to the cost of updating a dead cell. If the arities
> +% between the dead and new cell differ, a penalty cost
> +% is added (approximated as the gain one would have had if
> +% the unusable words would have been reused too).
> +% Weights are used to estimate all of these costs and are
> +% hard-coded. I don't think there is any need in making
> +% these values an option.
> +%
> +% Once the table is computed, usually the cell with highest value is selected.
usually? - when would the one with highest values not be selected.
> +% To cut the decision between different dead cells with the same
> +% value, we select the dead cell that has the least number of
> +% opportunities to be reused.
> +% E.g.
> +% X can be reused by 5 different constructions,
> +% but reaches its highest value for a construction C1
> +% (value 10).
> +% Y can be reused by only one construction, also C1 (value 10).
> +%
> +% First selecting X (and reusing it with construction C1) would
> +% jeopardize the reuse of Y and leaves us with only one cell reused.
> +% If, on the contrary, one would select Y first, chances are that
> +% after recomputing the table, X can still be reused by other
> +% constructions, hence possibly 2 cells reused.
> +% Even if Y would be of smaller value, selecting Y first would still
> +% be more interesting. Hence, instead of selecting the cell
> +% with highest value, we select the cell with highest
> +% value/degree ratio, degree being the number of constructions at which
> +% the cell could potentially be reused.
> +%
> +% Note that cells being deconstructed in the different branches of a
> +% disjunction can now also be reused after the the disjunction.
> +% e.g.:
> +% (
> +% ..., X => f(... ), ... % X dies
> +% ;
> +% ..., X => g(... ), ... % X dies
> +% ),
> +% Y <= f(... ), ... % Y can reuse X
> +% In this example, it is allowed to reuse X for Y. And it will also be
> +% discovered by the analysis.
> +%
> +%-----------------------------------------------------------------------------%
...
> +:- module transform_hlds.ctgc.structure_reuse.direct.choose_reuse.
> +
> +:- interface.
> +
> +:- pred determine_reuse(strategy::in, module_info::in, proc_info::in,
> + dead_cell_table::in, hlds_goal::in, hlds_goal::out, reuse_as::out,
> + io::di, io::uo) is det.
> +
I think I have mentioned this elsewhere but reuse_strategy would be a
better name for the strategy type.
...
> +determine_reuse(Strategy, ModuleInfo, ProcInfo, DeadCellTable,
> + !Goal, ReuseAs, !IO):-
> + % Check for local reuse:
> + process_goal(
> + background_info_init(Strategy, ModuleInfo, ProcInfo), DeadCellTable,
> + RemainingDeadCellTable, !Goal, reuse_as_init, ReuseAs, !IO),
> +
> + % Check for cell caching.
> + check_for_cell_caching(RemainingDeadCellTable, !Goal, !IO).
> +
> +%-----------------------------------------------------------------------------%
> +:- type background_info
> + ---> background(
> + strategy :: strategy,
> + module_info :: module_info,
> + proc_info :: proc_info,
> + vartypes :: vartypes
> + ).
> +
Add a comment describing this type.
> +:- func background_info_init(strategy, module_info, proc_info) =
> + background_info.
> +
> +background_info_init(Strategy, ModuleInfo, ProcInfo) = Background :-
> + proc_info_get_vartypes(ProcInfo, VarTypes),
> + Background = background(Strategy, ModuleInfo, ProcInfo, VarTypes).
> +
> +%-----------------------------------------------------------------------------%
> +% Some types and predicates for the administration of the deconstructions,
> +% constructions and the 'matches' we want to derive from them.
> +%
> +
> + % Details of a deconstruction yielding garbage.
> + %
> +:- type deconstruction_spec
> + ---> decon(
> + decon_var :: prog_var,
> + decon_pp :: program_point,
> + decon_cons_id :: cons_id,
> + decon_args :: prog_vars,
> + decon_conds :: reuse_as
> + ).
> +
> + % Details of a construction possibly reusing some specific garbage cells
> + % generated at a deconstruction.
> + %
> +:- type construction_spec
> + ---> con(
> + con_pp :: program_point,
> + con_reuse :: reuse_type
> + ).
> +
> + % The reuse-type is a basic identification of whether the cons-ids involved
> + % in the reuse are the same, what the arities of the old and new cells are,
> + % and which arguments don't have to be updated.
> + %
s/have to/need/
> +:- type reuse_type
> + ---> reuse_type(
> + same_cons :: bool,
> + reuse_fields :: list(needs_update),
> + % States whether the corresponding argument in the list of
> + % arguments of the reused cons needs to be updated when reused
> + % or not.
> + % Note that list.length(reuse_fields) is the arity of the
> + % reused term.
> + tmp_value :: float
> + % A metrics measuring the value of the reuse. A high value
> + % should represent a 'good' reuse (yielding possibly good
> + % results on the general memory behaviour of the procedure)
> + % compared to a reuse with a lower value.
tmp_value is not a good field name, perhaps reuse_value instead?
...
> + % One match is a description of a list of deconstructions and a list of
s/One/A/
> + % constructions. The deconstructions and constructions can all be coded
> + % into reuses, as they are such that at run-time at most one
> + % deconstruction yielding the dead cell will occur on the same
> + % execution path as a construction that
> + % can reuse that cell.
> + % This means that all the deconstructions can be coded as
> + % deconstructions yielding dead cell, and all the constructions can be
> + % coded as constructions reusing the cell that becomes available
> + % through one of the deconstructions.
> + %
> +:- type match
> + ---> match(
> + decon_specs :: list(deconstruction_spec),
> + con_specs :: list(construction_spec),
> + match_value :: float,
> + match_degree :: int
> + ).
> +
> +:- type match_table == multi_map(prog_var, match).
> +
> + % Initialise a deconstruction_spec.
> + %
> +:- func deconstruction_spec_init(prog_var, program_point, cons_id,
> + list(prog_var), reuse_as) = deconstruction_spec.
The above line is over-indented.
...
> + % Get the list of cons_ids that the dead variable may have when it
> + % will be reused.
> + %
> +:- func match_get_dead_cons_ids(match) = list(cons_id).
> +match_get_dead_cons_ids(Match) = ConsIds :-
> + GetConsId = (pred(D::in, C::out) is det :-
> + C = D ^ decon_cons_id),
> + list.map(GetConsId, Match ^ decon_specs, ConsIds).
That would be cleaner with functional notation, e.g.
GetConsId = (func(D) = D ^ decon_cons_id),
ConsId = list.map(GetConsId, Match ^ decon_specs).
> + % Determine the reuse condition of the match.
> + %
> +:- func match_get_condition(background_info, match) = reuse_as.
> +match_get_condition(Background, Match) = Condition :-
> + GetCond = (pred(D::in, C::out) is det :-
> + C = D ^ decon_conds),
> + list.map(GetCond, Match ^ decon_specs, Conditions),
Likewise here.
> + (
> + Conditions = [First | Rest],
> + list.foldl(
> + reuse_as_least_upper_bound(Background ^ module_info,
> + Background ^ proc_info),
> + Rest, First, Condition)
The indentation has gone funny here.
> + ;
> + Conditions = [],
> + unexpected(choose_reuse.this_file, "match_get_condition: " ++
> + "no reuse conditions.\n")
> + ).
...
> +%-----------------------------------------------------------------------------%
> +% Process one single goal:
> +% * determine a match table
> +% * find the best match
> +% * annotate the goal with the reuse described by that match
> +% * and reprocess the goal until no matches are found.
> +%
> +
> +:- pred process_goal(background_info::in, dead_cell_table::in,
> + dead_cell_table::out, hlds_goal::in, hlds_goal::out, reuse_as::in,
> + reuse_as::out, io::di, io::uo) is det.
> +
> +process_goal(Background, !DeadCellTable, !Goal, !ReuseAs, !IO):-
> + globals.io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
> +
> + % Compute a match table.
> + compute_match_table(Background, !.DeadCellTable, !.Goal,
> + MatchTable, !IO),
> +
> + % As long as the match table is not empty, pick out the match
> + % with the highest value, annotate the goal accordingly, and
> + % repeat the procedure.
> + % If the match table is empty, the work is finished.
> + (
> + multi_map__is_empty(MatchTable)
> + ->
> + true
> + ;
> + % 1. select the deconstructions-constructions with
> + % highest value.
> + Match = highest_match_degree_ratio(MatchTable),
> +
> + % 2. dump all the matches recorded in the table, highlight the
> + % match with the highest value.
> + maybe_write_string(VeryVerbose, "% Reuse results: \n",
> + !IO),
> + maybe_dump_match_table(VeryVerbose, MatchTable,
> + Match, !IO),
> +
> + % 3. realise the reuses by explicitly annotating the
> + % procedure goal.
> + annotate_reuses_in_goal(Background, Match, !Goal),
> + % remove the deconstructions from the available map of
> + % dead cells:
> + remove_deconstructions_from_dead_cell_table(Match, !DeadCellTable),
> +
> + % 4. Add the conditions involved in the reuses to the
> + % existing conditions.
> + reuse_as_least_upper_bound(Background ^ module_info,
> + Background ^ proc_info, match_get_condition(Background, Match),
> + !ReuseAs),
> + % 5. Process the goal for further reuse-matches.
> + process_goal(Background, !DeadCellTable, !Goal,
> + !ReuseAs, !IO)
> + ).
> +
...
> +:- pred compute_match_table_goal_list(background_info::in, dead_cell_table::in,
> + list(hlds_goal)::in, match_table::in, match_table::out, io::di,
> + io::uo) is det.
> +
> +compute_match_table_goal_list(Background, DeadCellTable, Goals,
> + !Table, !IO) :-
> + (
> + Goals = []
> + ;
> + Goals = [CurrentGoal | Cont],
> + compute_match_table_with_continuation(Background, DeadCellTable,
> + CurrentGoal, Cont, !Table, !IO)
> + ).
> +
> +:- pred compute_match_table_with_continuation(background_info::in,
> + dead_cell_table::in, hlds_goal::in, list(hlds_goal)::in,
> + match_table::in, match_table::out, io::di, io::uo) is det.
> +
> +compute_match_table_with_continuation(Background, DeadCellTable,
> + CurrentGoal, Cont, !Table, !IO) :-
> + CurrentGoal = GoalExpr - GoalInfo,
> + (
> + GoalExpr = unify(_, _, _, Unification, _),
> + (
> + Unification = deconstruct(Var, ConsId, Args, _, _, _)
> + ->
> +
> + ProgramPoint = program_point_init(GoalInfo),
> + (
> + Condition = dead_cell_table_search(ProgramPoint,
> + DeadCellTable)
> + ->
> + ReuseAs = reuse_as_init_with_one_condition(Condition),
> + DeconstructionSpec = deconstruction_spec_init(Var,
> + ProgramPoint, ConsId, Args, ReuseAs),
> + Match0 = match_init([DeconstructionSpec]),
> + find_best_match_in_conjunction(Background, Cont, Match0, Match),
> + multi_map.set(!.Table, Var, Match, !:Table)
You might want to use the version of set from the svmulti_map module,
which would be more concise here:
svmulti_map.set(Var, Match, !Table)
> +:- pred compute_match_table_in_disjunction(background_info::in,
> + dead_cell_table::in, hlds_goals::in, hlds_goals::in,
> + match_table::in, match_table::out, io::di, io::uo) is det.
> +compute_match_table_in_disjunction(Background, DeadCellTable, DisjGoals, Cont,
> + !Table, !IO) :-
> + % Compute a match table for each of the branches of the disjunction.
> + % Each of these tables will contain information about local reuses
> + % w.r.t. the disjunction, i.e. a data structure is reused within the
> + % same branch in which it dies.
> + compute_match_table_in_disjs(Background, DeadCellTable, DisjGoals,
> + DisjTables, !IO),
> + list.foldl(multi_map.merge, DisjTables, !Table),
> +
> + % It is possible that each of the branches of the disjunctions
> + % deconstructs the same (non local) dead variable. In such a case, we
> + % need to check if that dead variable can be reused outside of the
> + % disjunction.
> + process_possible_common_dead_vars(Background, Cont, DisjTables,
> + CommonDeadVarsDisjTables, !IO),
> + list.foldl(multi_map.merge, CommonDeadVarsDisjTables, !Table).
> +
...
> +:- func deconstruction_specs(prog_var, list(match_table)) =
> + list(deconstruction_spec).
Perhaps the equivalence dead_var == prog_var should be defined
somewhere?
> +deconstruction_specs(DeadVar, Tables) = DeconstructionSpecs :-
> + list.foldl(deconstruction_specs_2(DeadVar), Tables, [],
> + DeconstructionSpecs).
> +
> +:- pred deconstruction_specs_2(prog_var::in, match_table::in,
> + list(deconstruction_spec)::in, list(deconstruction_spec)::out) is det.
> +deconstruction_specs_2(DeadVar, Table, !DeconstructionSpecs) :-
> + multi_map.lookup(Table, DeadVar, Matches),
> + NewSpecs = list.condense(list.map(match_get_decon_specs, Matches)),
> + append(NewSpecs, !DeconstructionSpecs).
> +
> +:- func match_get_decon_specs(match) = list(deconstruction_spec).
> +match_get_decon_specs(Match) = Match ^ decon_specs.
> +
> +%-----------------------------------------------------------------------------%
> +%
> +% Find construction unifications for dead cells, compute the values of the
> +% matches.
> +%
> +
> + %
> + % Compute the value of a dead cel with respect to its possible reusesi in a
s/cel/cell
s/resusesi/reuses/
> + % conjunction of goals. If reuse is possible, add the specification of the
> + % construction where it can be reused to the list of constructions recorded
> + % in the match.
> + %
> + % In a conjunction, a dead cell can only be reused in at most one of its
> + % direct childs.
s/childs/children/
> + % This means that for each child a new value is computed. At
> + % the end of a conjunction, we immediately choose the reuse with the
> + % highest value.
> + %
> + % XXX This may not be such a good idea, as the notion of "degree" is used
> + % to decide between reuses with the same value later on, once the full
> + % match_table is computed.
> + %
> + %
> +:- pred find_best_match_in_conjunction(background_info::in,
> + hlds_goals::in, match::in, match::out) is det.
> +
> +find_best_match_in_conjunction(Background, Goals, !Match) :-
> + Match0 = !.Match,
> + list.map(find_match_in_goal(Background, Match0), Goals, ExclusiveMatches),
> + Degree = count_candidates(ExclusiveMatches),
> + highest_match_in_list(ExclusiveMatches, !Match),
> + !:Match = !.Match ^ match_degree := Degree.
> +
> + % Compute the matches for a dead cell in the context of a disjunction. For
> + % each of the branches of the disjunction, a different match may be found.
s/of the branches/branch/
...
> + % After determining all local reuses of dead datastructures (a data
> + % structure becomes dead and is reused in one and the same procedure), we
> + % determine the 'global reuses': deconstructions that yield dead data
> + % structures, without imposing any reuse constraints are annotated so that
> + % these cells can be cached whenever the user specifies that option.
> + %
> +:- pred check_for_cell_caching(dead_cell_table::in, hlds_goal::in,
> + hlds_goal::out, io::di, io::uo) is det.
> +
> +check_for_cell_caching(DeadCellTable0, !Goal, !IO) :-
> + dead_cell_table_remove_conditionals(DeadCellTable0, DeadCellTable),
> + globals__io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
> + (
> + \+ dead_cell_table_is_empty(DeadCellTable)
> + ->
> + maybe_write_string(VeryVerbose, "% Marking cacheable cells.\n", !IO),
> + check_cc(DeadCellTable, !Goal)
> + ;
> + maybe_write_string(VeryVerbose, "% No cells to be cached.\n", !IO)
> + ).
> +
> +:- pred check_cc(dead_cell_table::in, hlds_goal::in, hlds_goal::out) is det.
I suggest calling this predicate check_for_cell_caching_2 and similarly
check_cell_caching_in_unification etc below.
> +check_cc(DeadCellTable, !Goal):-
> + !.Goal = GoalExpr0 - GoalInfo0,
> + (
> + GoalExpr0 = unify(A, B, C, Unification0, D),
> + check_cc_for_unification(DeadCellTable,
> + Unification0, Unification, GoalInfo0, GoalInfo),
> + GoalExpr = unify(A, B, C, Unification, D)
> + ;
> + GoalExpr0 = call(_, _, _, _, _, _),
> + GoalExpr = GoalExpr0,
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = generic_call( _, _, _, _),
> + GoalExpr = GoalExpr0,
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = foreign_proc(_, _, _, _, _, _),
> + GoalExpr = GoalExpr0,
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = conj(A, Goals0),
> + list.map(check_cc(DeadCellTable), Goals0, Goals),
> + GoalExpr = conj(A, Goals),
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = disj(Goals0),
> + list.map(check_cc(DeadCellTable), Goals0, Goals),
> + GoalExpr = disj(Goals),
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = switch(A, B, Cases0),
> + list.map(check_cc_in_case(DeadCellTable), Cases0, Cases),
> + GoalExpr = switch(A, B, Cases),
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = not(_),
> + GoalExpr = GoalExpr0,
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = scope(A, ScopeGoal0),
> + check_cc(DeadCellTable, ScopeGoal0, ScopeGoal),
> + GoalExpr = scope(A, ScopeGoal),
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = if_then_else(A, CondGoal0, ThenGoal0, ElseGoal0),
> + check_cc(DeadCellTable, CondGoal0, CondGoal),
> + check_cc(DeadCellTable, ThenGoal0, ThenGoal),
> + check_cc(DeadCellTable, ElseGoal0, ElseGoal),
> + GoalExpr = if_then_else(A, CondGoal, ThenGoal, ElseGoal),
> + GoalInfo = GoalInfo0
> + ;
> + GoalExpr0 = shorthand(_),
> + unexpected(choose_reuse.this_file, "check_cc: " ++
> + "shorthand goal.")
> + ),
> + !:Goal = GoalExpr - GoalInfo.
Once you've addressed the above comments I'm happy for you to commit the rest
of this as is (providing that it bootstraps and that all CTGC options are
turned off by default).
Julien.
--------------------------------------------------------------------------
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