[m-rev.] [reuse] diff: remove last sr_data-dependencies from hlds-modules
Nancy Mazur
Nancy.Mazur at cs.kuleuven.ac.be
Fri Jul 30 13:45:44 AEST 2004
Hi,
===================================================================
Estimated hours taken: 5
Branches: reuse
* Remove the last remaining dependencies from the hlds.* modules to some of the
structure reuse modules (in particular sr_data). This mainly required changing
the way deconstructions yielding dead cells are handled. Instead of marking
these deconstructions within the hlds_goal structure, we now use a separate
table to list these deconstructions.
* Remove sr_choice.m as it only dealt with the random selection strategy, and I
don't inted to support this strategy any longer: there are no advantages
whatsoever to use random instead of graph or lifo.
hlds_goal.m:
sr_data.m:
Change reuse_goal_info by removing the 'choice' option,
and move its definition to hlds_goal where it belongs.
The type short_reuse_info is also changed in the sense that the functor
'no_reuse' is not present anymore. Indeed, reuse(no_reuse) == empty.
hlds_out.m:
Remove sr_data dependency.
options.m:
Remove random option from the mmc-documentation.
pa_alias_as.m:
Small change, dedouble the least_upper_bound_list definition.
sr_choice.m:
(deleted)
sr_choice_graphing.m:
- Change the documentation so that it doesn't refer to sr_choice
anymore.
- use the dead_cell_table for identifying deconstructions yielding dead
cells. This table is constructed by the process_proc procedure in
sr_dead.
- as the 'choice'-functor for annotating goals is not available
anymore, the role of "clean_all_left_overs" is reduced to identifying
all unconditionally dying cells for which no reuse was found (needed
when cell caching is enabled).
sr_choice_util.m:
- remove "random" selection strategy.
sr_data.m:
Apart from moving the reuse_goal_info types:
- add dead_cell_table as a map in which deconstruction-annotations can
be kept.
sr_dead.m:
Simplify. The process_proc pass is now pure and only responsible for
identifying the deconstructions in which a dead cell might be produced.
Previously, this pass was also used to annotate each construction with
the possible list of deconstructed cells it might reuse. This is not
needed anymore, as the scoping issue and reuse-verification is taken
care of in sr_choice_graphing.
sr_direct.m:
- Use the dead_cell_table produced by the 'deadness'-pass.
- remove the 'random' strategy.
sr_split.m:
- remove the 'choice' option for reuse_goal_info.
structure_reuse.m:
- remove 'sr_choice'.
Index: handle_options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/handle_options.m,v
retrieving revision 1.90.2.17
diff -u -r1.90.2.17 handle_options.m
--- handle_options.m 11 Sep 2002 07:34:33 -0000 1.90.2.17
+++ handle_options.m 30 Jul 2004 03:37:34 -0000
@@ -1648,7 +1648,7 @@
convert_dump_alias("paths", "cP").
convert_dump_alias("petdr", "din").
convert_dump_alias("palias", "A").
-convert_dump_alias("sr", "Ap").
+convert_dump_alias("sr", "ApG").
convert_dump_alias("osv", "bcdglmnpruvP"). % for debugging
% --optimize-saved-vars-cell
Index: hlds_goal.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.76.2.18
diff -u -r1.76.2.18 hlds_goal.m
--- hlds_goal.m 24 Jun 2004 02:19:33 -0000 1.76.2.18
+++ hlds_goal.m 30 Jul 2004 03:37:39 -0000
@@ -12,8 +12,6 @@
:- interface.
-:- import_module structure_reuse.
-:- import_module structure_reuse__sr_data.
% :- import_module ll_backend__llds. % XXX needed for `lval'
:- import_module parse_tree__prog_data, parse_tree__inst.
:- import_module hlds__hlds_data, hlds__hlds_pred, hlds__hlds_llds.
@@ -592,7 +590,6 @@
%
% Information for all kinds of goals
%
-
%
% Access predicates for the hlds_goal_info data structure.
% For documentation on the meaning of the fields that these
@@ -792,6 +789,43 @@
:- pred goal_info_set_reuse(reuse_goal_info::in, hlds_goal_info::in,
hlds_goal_info::out) is det.
+ % Before the analysis, every goal is annotated with 'empty', ie. no
+ % information about any reuse.
+ % The field 'potential_reuse' states that in a reuse version of the
+ % current procedure, this goal can be replaced by a goal performing
+ % structure reuse.
+ % The field '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.
+:- type reuse_goal_info
+ ---> empty
+ ; potential_reuse(short_reuse_info)
+ ; reuse(short_reuse_info).
+
+ % 'cell_died' is only relevant for deconstructions.
+ % 'cell_reused' is only relevant for constructions.
+ % 'reuse_call' is obviously only applicable to procedure calls.
+ % 'missed_reuse_call' is only used for procedure calls.
+:- type short_reuse_info
+ ---> cell_died
+ ; cell_reused(
+ prog_var, % The dead variable selected
+ % for reusing.
+ bool, % Yes if the reuse is conditional.
+ list(cons_id), % What are the possible
+ % cons_ids that the variable
+ % to be reused can have.
+ list(bool) % Which of the fields of
+ % the cell to be reused
+ % already contain the
+ % correct value.
+ )
+ ; reuse_call(bool) % 'yes' if the call is conditional.
+ ; missed_reuse_call(list(string)).
+ % The strings give a description on why
+ % the call to the reuse version might
+ % not be safe.
%-----------------------------------------------------------------------------%
%
% Miscellaneous utility procedures for dealing with HLDS goals
@@ -1149,11 +1183,6 @@
% Information stored with all kinds of goals
%
-% XXX reuse_goal_info temporarely still defined in sr_data.
-% :- type reuse_info
- % ---> empty
- % ; potential_reuse(short_reuse_info)
- % ; reuse(short_reuse_info).
:- type hlds_goal_reuse_info
---> goal_reuse_info(
Index: hlds_out.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_out.m,v
retrieving revision 1.243.2.30
diff -u -r1.243.2.30 hlds_out.m
--- hlds_out.m 29 Jul 2004 01:59:50 -0000 1.243.2.30
+++ hlds_out.m 30 Jul 2004 03:37:52 -0000
@@ -267,10 +267,6 @@
:- import_module check_hlds__type_util.
:- import_module transform_hlds__termination, transform_hlds__term_errors.
-% Reuse modules
-:- import_module structure_reuse.
-:- import_module structure_reuse__sr_data.
-
% RL back-end modules (XXX should avoid using those here).
:- import_module aditi_backend__rl.
@@ -1324,9 +1320,6 @@
),
io__write_string(": "),
(
- { SR = no_reuse },
- io__write_string("nothing.\n")
- ;
{ SR = cell_died },
io__write_string("cell just died (deconstruction).\n")
;
Index: options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.288.2.25
diff -u -r1.288.2.25 options.m
--- options.m 11 Sep 2002 07:36:05 -0000 1.288.2.25
+++ options.m 30 Jul 2004 03:38:15 -0000
@@ -2572,7 +2572,7 @@
"--structure-reuse-selection",
"\tStrategy to decide which of the possible cells available",
- "\tfor reuse is reused. Currently lifo, random, or graph",
+ "\tfor reuse is reused. Currently lifo, or graph",
"\t(default = graph).",
"--cell-cache",
Index: pa_alias_as.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias_as.m,v
retrieving revision 1.1.2.43
diff -u -r1.1.2.43 pa_alias_as.m
--- pa_alias_as.m 29 Jun 2004 05:12:21 -0000 1.1.2.43
+++ pa_alias_as.m 30 Jul 2004 03:38:21 -0000
@@ -148,6 +148,8 @@
% Compute least upper bound of a list of abstract alias descriptions.
:- pred least_upper_bound_list(module_info::in, proc_info::in,
hlds_goal_info::in, list(alias_as)::in, alias_as::out) is det.
+:- pred least_upper_bound_list(module_info::in, proc_info::in,
+ list(alias_as)::in, alias_as::out) is det.
% extend(ProcInfo, ModuleInfo, NEW, OLD, RESULT).
% This is the "comb" operation used in the Nancy's Phd-textbook. It is
@@ -476,6 +478,9 @@
).
least_upper_bound_list(HLDS, ProcInfo, _GoalInfo, Alias_list0, AS) :-
+ least_upper_bound_list(HLDS, ProcInfo, Alias_list0, AS).
+
+least_upper_bound_list(HLDS, ProcInfo, Alias_list0, AS) :-
list__foldl(least_upper_bound(HLDS, ProcInfo) , Alias_list0,
bottom, AS).
Index: sr_choice.m
===================================================================
RCS file: sr_choice.m
diff -N sr_choice.m
--- sr_choice.m 28 Jul 2004 02:14:36 -0000 1.1.2.28
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,773 +0,0 @@
-%-----------------------------------------------------------------------------%
-% Copyright (C) 2000-2002,2004 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.
-%-----------------------------------------------------------------------------%
-%
-% Module: sr_choice
-% Main authors: petdr
-%
-% Given a goal annotated with information about which cells are
-% canditates for reuse and a strategy determine which cells will
-% actually be reused and the conditions that reuse implies on the head
-% variables.
-%
-%-----------------------------------------------------------------------------%
-
-:- module structure_reuse__sr_choice.
-:- interface.
-
-:- import_module hlds__hlds_goal.
-:- import_module hlds__hlds_pred.
-:- import_module hlds__hlds_module.
-:- import_module structure_reuse__sr_data.
-:- import_module structure_reuse__sr_choice_util.
-
-:- import_module list, std_util.
-
-:- pred sr_choice__process_goal(strategy::in, vartypes::in, module_info::in,
- proc_info::in, hlds_goal::in, hlds_goal::out,
- maybe(list(reuse_condition))::out) is det.
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-
-:- implementation.
-
-:- import_module check_hlds__type_util.
-:- import_module hlds__hlds_data.
-:- import_module libs__globals.
-:- import_module libs__options.
-:- import_module parse_tree__prog_data.
-
-:- import_module assoc_list, bool, int.
-:- import_module map, multi_map, require, set.
-:- import_module string.
-:- import_module queue.
-
-process_goal(Strategy, VarTypes, ModuleInfo, ProcInfo,
- Goal0, Goal, MaybeReuseConditions) :-
- Strategy = strategy(Constraint, SelectionRule),
- apply_constraint(Constraint, VarTypes, ModuleInfo, ProcInfo,
- Goal0, Goal1),
- select_reuses(SelectionRule, Goal1, Goal2, ReusedVars, ReuseConditions),
- determine_cgc(ReusedVars, Goal2, Goal),
- ( ReuseConditions = [] ->
- MaybeReuseConditions = no
- ;
- MaybeReuseConditions = yes(ReuseConditions)
- ).
-
-%-----------------------------------------------------------------------------%
-
-:- type constraint_info
- ---> constraint_info(
- map :: multi_map(prog_var,
- reuse_cell_data),
- module_info :: module_info,
- proc_info :: proc_info,
- vartypes :: vartypes
- ).
-
-:- type reuse_cell_data
- ---> data(
- cons_id :: cons_id,
- vars :: prog_vars,
- secondary_tag :: bool
- ).
-
-:- pred constraint_info_init(vartypes::in, module_info::in,
- proc_info::in, constraint_info::out) is det.
-
-constraint_info_init(VarTypes, ModuleInfo, ProcInfo,
- constraint_info(Map, ModuleInfo, ProcInfo, VarTypes)) :-
- multi_map__init(Map).
-
-:- pred apply_constraint(constraint::in, vartypes::in, module_info::in,
- proc_info::in, hlds_goal::in, hlds_goal::out) is det.
-
-apply_constraint(Constraint, VarTypes, ModuleInfo, ProcInfo, Goal0, Goal) :-
- constraint_info_init(VarTypes, ModuleInfo, ProcInfo, ConstraintInfo),
- apply_constraint_2(Constraint, Goal0, Goal, ConstraintInfo, _).
-
-:- pred apply_constraint_2(constraint::in, hlds_goal::in, hlds_goal::out,
- constraint_info::in, constraint_info::out) is det.
-
-apply_constraint_2(_Constraint, Goal - GoalInfo, Goal - GoalInfo, !CI) :-
- Goal = call(_PredId, _ProcId, _Args, _Builtin, _MaybeCtxt, _Name).
-
-apply_constraint_2(Constraint, Goal - GoalInfo0, Goal - GoalInfo, !CI) :-
- Goal = unify(_Var, _Rhs, _Mode, Unification, _Ctxt),
- apply_constraint_unification(Constraint, Unification,
- GoalInfo0, GoalInfo, !CI).
-
-apply_constraint_2(_Constraint, Goal0 - GoalInfo, Goal0 - GoalInfo, !CI) :-
- Goal0 = generic_call(_, _, _, _).
-apply_constraint_2(_Constraint, Goal0 - GoalInfo, Goal0 - GoalInfo, !CI) :-
- Goal0 = foreign_proc(_, _, _, _, _, _, _).
-apply_constraint_2(_Constraint, Goal0 - _GoalInfo, _, !CI) :-
- Goal0 = shorthand(_),
- error("structure_reuse: shorthand.\n").
-
-apply_constraint_2(Constraint, Goal0 - GoalInfo, Goal - GoalInfo, !CI) :-
- Goal0 = if_then_else(Vars, If0, Then0, Else0),
- BeforeIfInfo = !.CI,
- apply_constraint_2(Constraint, If0, If, !CI),
- IfInfo = !.CI,
- apply_constraint_2(Constraint, Then0, Then, IfInfo, ThenInfo),
- apply_constraint_2(Constraint, Else0, Else, BeforeIfInfo, ElseInfo),
- merge(ThenInfo, !CI),
- merge(ElseInfo, !CI),
- Goal = if_then_else(Vars, If, Then, Else).
-
-apply_constraint_2(Constraint, Goal0 - GoalInfo, Goal - GoalInfo, !CI) :-
- Goal0 = switch(Var, CanFail, Cases0),
- InitSwitchInfo = !.CI,
- apply_constraint_cases(Constraint, InitSwitchInfo, Cases0, Cases, !CI),
- Goal = switch(Var, CanFail, Cases).
-
-apply_constraint_2(Constraint, Goal0 - GoalInfo, Goal - GoalInfo, !CI) :-
- Goal0 = some(Vars, CanRemove, SomeGoal0),
- apply_constraint_2(Constraint, SomeGoal0, SomeGoal, !CI),
- Goal = some(Vars, CanRemove, SomeGoal).
-
-apply_constraint_2(Constraint, not(G0) - GoalInfo, not(G) - GoalInfo, !CI):-
- InitNotInfo = !.CI,
- % A negated goal cannot introduce new dead cells to the map of
- % available dead cells, as those dead cells are not allowed to
- % be reused outside of the negated goal.
- apply_constraint_2(Constraint, G0, G, InitNotInfo, _).
-
-apply_constraint_2(Constraint, conj(Goal0s) - GoalInfo,
- conj(Goals) - GoalInfo, !CI) :-
- apply_constraint_list(Constraint, Goal0s, Goals, !CI).
-
-apply_constraint_2(Constraint, disj(Goal0s) - GoalInfo,
- disj(Goals) - GoalInfo, !CI) :-
- InitDisjInfo = !.CI,
- apply_constraint_disj(Constraint, InitDisjInfo, Goal0s, Goals, !CI).
-
-apply_constraint_2(Constraint, par_conj(Goal0s) - GoalInfo,
- par_conj(Goals) - GoalInfo, !CI) :-
- apply_constraint_list(Constraint, Goal0s, Goals, !CI).
-
-:- pred apply_constraint_cases(constraint::in, constraint_info::in,
- list(case)::in, list(case)::out,
- constraint_info::in, constraint_info::out) is det.
-
-apply_constraint_cases(_Constraint, _Info0, [], [], !CI).
-apply_constraint_cases(Constraint, Info0, [Case0 | Case0s], [Case | Cases],
- !CI) :-
- Case0 = case(ConsId, Goal0),
- apply_constraint_2(Constraint, Goal0, Goal, Info0, Info),
- merge(Info, !CI),
- Case = case(ConsId, Goal),
- apply_constraint_cases(Constraint, Info0, Case0s, Cases, !CI).
-
-:- pred apply_constraint_list(constraint::in, hlds_goals::in, hlds_goals::out,
- constraint_info::in, constraint_info::out) is det.
-
-apply_constraint_list(_Constraint, [], [], !CI).
-apply_constraint_list(Constraint, [Goal0 | Goal0s], [Goal | Goals], !CI) :-
- apply_constraint_2(Constraint, Goal0, Goal, !CI),
- apply_constraint_list(Constraint, Goal0s, Goals, !CI).
-
-:- pred apply_constraint_disj(constraint::in,
- constraint_info::in, hlds_goals::in, hlds_goals::out,
- constraint_info::in, constraint_info::out) is det.
-
-apply_constraint_disj(_Constraint, _Info0, [], [], !CI).
-apply_constraint_disj(Constraint, Info0, [Goal0 | Goal0s], [Goal | Goals],
- !CI) :-
- apply_constraint_2(Constraint, Goal0, Goal, Info0, Info),
- merge(Info, !CI),
- apply_constraint_disj(Constraint, Info0, Goal0s, Goals, !CI).
-
-:- pred merge(constraint_info::in, constraint_info::in,
- constraint_info::out) is det.
-
-merge(InfoA, Info0, Info) :-
- multi_map__merge(InfoA ^ map, Info0 ^ map, Map),
- Info = Info0 ^ map := Map.
-
-:- pred apply_constraint_unification(constraint::in, unification::in,
- hlds_goal_info::in, hlds_goal_info::out,
- constraint_info::in, constraint_info::out) is det.
-
-apply_constraint_unification(Constraint, Unif, GoalInfo0, GoalInfo, !CI) :-
- Unif = construct(Var, ConsId, Vars, _Ms, _HTC, _IsUniq, _Aditi),
- goal_info_get_reuse(GoalInfo0, ReuseInfo),
- ( ReuseInfo = choice(construct(Pairs)) ->
- PossibleCandidates = set__to_sorted_list(Pairs)
- ;
- error("sr_choice__apply_constraint_unification")
- ),
- ModuleInfo = !.CI ^ module_info,
- VarTypes = !.CI ^ vartypes,
- has_secondary_tag(ModuleInfo, VarTypes, Var,
- ConsId, HasSecondaryTag),
- Map = !.CI ^ map,
- (
- Constraint = same_cons_id ,
-
- % XXX recode this more efficiently at some stage.
- P = (pred(Candidate::out) is nondet :-
- list__member(Candidate0, PossibleCandidates),
- CandidateVar = Candidate0 ^ var,
- multi_map__search(Map, CandidateVar, CandidateData),
- ConsIds = list__map((func(D) = D ^ cons_id),
- CandidateData),
- list__remove_dups(ConsIds, [ConsId]),
- ReuseFields = reuse_fields(HasSecondaryTag, Vars,
- CandidateData),
- Candidate = (Candidate0
- ^ cons_ids := yes([ConsId]))
- ^ reuse_fields := yes(ReuseFields)
- )
- ;
- Constraint = within_n_cells_difference(Difference),
- % XXX recode this more efficiently at some stage.
- P = (pred(Candidate::out) is nondet :-
- list__member(Candidate0, PossibleCandidates),
- CandidateVar = Candidate0 ^ var,
-
- \+ no_tag_type(ModuleInfo, VarTypes, CandidateVar),
-
- multi_map__search(Map, CandidateVar, CandidateData),
- ConsIds = list__remove_dups(
- list__map((func(D) = D ^ cons_id),
- CandidateData)),
- % XXX There is something wrong going on here. Removing
- % the list__remove_dups causes stack overflow in some
- % cases. Later some further investigation wouldn't be a
- % bad investment.
- ReuseSizes = list__remove_dups(list__map(
- (func(Data) = list__length(Data^vars)),
- CandidateData)),
-
- Size = list__length(Vars),
- all [ReuseSize] (
- list__member(ReuseSize, ReuseSizes)
- =>
- (
- ReuseSize - Size =< Difference
- )
- ),
- ReuseFields = reuse_fields(HasSecondaryTag, Vars,
- CandidateData),
- Candidate = (Candidate0
- ^ cons_ids := yes(ConsIds))
- ^ reuse_fields := yes(ReuseFields)
-
- )
- ),
- solutions(P, Candidates),
- goal_info_set_reuse(
- choice(construct(set__list_to_set(Candidates))),
- GoalInfo0,
- GoalInfo).
-
-
-apply_constraint_unification(_Constraint, Unif, GoalInfo, GoalInfo, !CI) :-
- Unif = deconstruct(Var, ConsId, Vars, _Modes, _CanFail, _CanCGC),
- Map0 = !.CI ^ map,
- ModuleInfo = !.CI ^ module_info,
- VarTypes = !.CI ^ vartypes,
- has_secondary_tag(ModuleInfo, VarTypes, Var, ConsId, SecondaryTag),
- NewData = data(ConsId, Vars, SecondaryTag),
- (
- multi_map__search(Map0, Var, ListData),
- cons_id_in_reuse_cell_data(ConsId, ListData)
- ->
- Map = Map0
- ;
- multi_map__set(Map0, Var, NewData, Map)
- ),
- !:CI = !.CI ^ map := Map.
-apply_constraint_unification(_Constraint, Unif, GoalInfo, GoalInfo, !CI) :-
- Unif = assign(_, _).
-apply_constraint_unification(_Constraint, Unif, GoalInfo, GoalInfo, !CI) :-
- Unif = simple_test(_, _).
-apply_constraint_unification(_Constraint, Unif, GoalInfo, GoalInfo, !CI) :-
- Unif = complicated_unify(_, _, _).
-
-:- pred cons_id_in_reuse_cell_data(cons_id, list(reuse_cell_data)).
-:- mode cons_id_in_reuse_cell_data(in, in) is semidet.
-cons_id_in_reuse_cell_data(ConsId, Data):-
- list__filter(
- (pred(ReuseData::in) is semidet :-
- ReuseData = data(ConsId, _, _)),
- Data, [_|_]).
-
- %
- % Determine which of the fields already contain references to
- % the correct variable, and hence don't need to be updated. To
- % do this requires knowledge of whether or not the current field
- % has a secondary tag or not.
- %
-:- func reuse_fields(bool, prog_vars, list(reuse_cell_data)) = list(bool).
-
-reuse_fields(HasSecTag, Vars, CandidateData)
- = list__foldl(and_list, Tail, Head) :-
- Pairs = list__map((func(Data) =
- Data ^ secondary_tag - Data ^ vars),
- CandidateData),
- BoolsList = list__map(
- already_correct_fields(HasSecTag, Vars), Pairs),
- ( BoolsList = [H | T] ->
- Head = H,
- Tail = T
- ;
- error("reuse_fields: empty list")
- ).
-
-
-:- func and_list(list(bool), list(bool)) = list(bool).
-
-and_list(ListA, ListB)
- = list__map((func(A - B) = A `and` B),
- from_corresponding_lists(ListA, ListB)).
-
-%-----------------------------------------------------------------------------%
-
-
-:- type selection_info
- ---> selection_info(
- local_used :: set(prog_var),
- global_used :: set(prog_var),
- reuse_conds :: list(reuse_condition),
-
- lifo :: lifo
- ).
-
-:- type lifo
- ---> lifo(
- all_locals :: list(list(prog_var)),
- local :: list(prog_var),
- global :: list(list(prog_var))
- ).
-
-:- func selection_info_init = selection_info.
-
-selection_info_init = selection_info(set__init, set__init, [], lifo([],[],[])).
-
-:- pred select_reuses(selection::in, hlds_goal::in, hlds_goal::out,
- set(prog_var)::out, list(reuse_condition)::out) is det.
-
-select_reuses(SelectionRule, Goal0, Goal, ReusedVars, ReuseConditions) :-
- select_reuses_2(SelectionRule, Goal0, Goal, selection_info_init, Info),
- ReusedVars = Info ^ local_used `union` Info ^ global_used,
- ReuseConditions = Info ^ reuse_conds.
-
-:- pred select_reuses_2(selection::in, hlds_goal::in, hlds_goal::out,
- selection_info::in, selection_info::out) is det.
-
-select_reuses_2(_Selection, Goal - GoalInfo, Goal - GoalInfo, !SI) :-
- Goal = call(_PredId, _ProcId, _Args, _Builtin, _MaybeCtxt, _Name).
-
-select_reuses_2(Selection, Goal - GoalInfo0, Goal - GoalInfo, !SI) :-
- Goal = unify(_Var, _Rhs, _Mode, Unification, _Ctxt),
- select_reuses_unification(Selection, Unification,
- GoalInfo0, GoalInfo, !SI).
-
-select_reuses_2(_Selection, Goal0 - GoalInfo, Goal - GoalInfo, !SI) :-
- Goal0 = generic_call(_, _, _, _),
- Goal = Goal0.
-select_reuses_2(_Selection, Goal0 - GoalInfo, Goal - GoalInfo, !SI) :-
- Goal0 = foreign_proc(_, _, _, _, _, _, _),
- Goal = Goal0.
-select_reuses_2(_Selection, Goal0 - _GoalInfo, _, !SI) :-
- Goal0 = shorthand(_),
- error("structure_reuse: shorthand.\n").
-
-select_reuses_2(Selection, Goal0 - GoalInfo, Goal - GoalInfo, !SI) :-
- Goal0 = if_then_else(Vars, If0, Then0, Else0),
- selection_start_branch(!SI),
- BeforeIfInfo = !.SI,
- select_reuses_2(Selection, If0, If, BeforeIfInfo, IfInfo),
- select_reuses_2(Selection, Then0, Then, IfInfo, ThenInfo),
- selection_merge(ThenInfo, !SI),
- select_reuses_2(Selection, Else0, Else, BeforeIfInfo, ElseInfo),
- selection_merge(ElseInfo, !SI),
- selection_end_branch(!SI),
- Goal = if_then_else(Vars, If, Then, Else).
-
-select_reuses_2(Selection, Goal0 - GoalInfo, Goal - GoalInfo, !SI) :-
- Goal0 = switch(Var, CanFail, Cases0),
- selection_start_branch(!SI),
- InitSwitchInfo = !.SI,
- select_reuses_cases(Selection, InitSwitchInfo, Cases0, Cases, !SI),
- Goal = switch(Var, CanFail, Cases).
-
-select_reuses_2(Selection, Goal0 - GoalInfo, Goal - GoalInfo, !SI) :-
- Goal0 = some(Vars, CanRemove, SomeGoal0),
- select_reuses_2(Selection, SomeGoal0, SomeGoal, !SI),
- Goal = some(Vars, CanRemove, SomeGoal).
-
-select_reuses_2(Selection, not(Goal0) - GoalInfo, not(Goal) - GoalInfo, !SI) :-
- select_reuses_2(Selection, Goal0, Goal, !SI).
-
-select_reuses_2(Selection, conj(Goal0s) - GoalInfo,
- conj(Goals) - GoalInfo, !SI) :-
- select_reuses_list(Selection, Goal0s, Goals, !SI).
-
-select_reuses_2(Selection, disj(Goal0s) - GoalInfo,
- disj(Goals) - GoalInfo, !SI) :-
- selection_start_branch(!SI),
- InitDisjInfo = !.SI,
- select_reuses_disj(Selection, InitDisjInfo, Goal0s, Goals, !SI).
-
-select_reuses_2(Selection, par_conj(Goal0s) - GoalInfo,
- par_conj(Goals) - GoalInfo, !SI) :-
- select_reuses_list(Selection, Goal0s, Goals, !SI).
-
-:- pred select_reuses_cases(selection::in, selection_info::in,
- list(case)::in, list(case)::out,
- selection_info::in, selection_info::out) is det.
-
-select_reuses_cases(_Selection, _Info0, [], [], !SI) :-
- selection_end_branch(!SI).
-select_reuses_cases(Selection, Info0, [Case0 | Case0s], [Case | Cases], !SI) :-
- Case0 = case(ConsId, Goal0),
- select_reuses_2(Selection, Goal0, Goal, Info0, Info),
- selection_merge(Info, !SI),
- Case = case(ConsId, Goal),
- select_reuses_cases(Selection, Info0, Case0s, Cases, !SI).
-
-:- pred select_reuses_list(selection::in, hlds_goals::in, hlds_goals::out,
- selection_info::in, selection_info::out) is det.
-
-select_reuses_list(_Selection, [], [], !SI).
-select_reuses_list(Selection, [Goal0 | Goal0s], [Goal | Goals], !SI) :-
- select_reuses_2(Selection, Goal0, Goal, !SI),
- select_reuses_list(Selection, Goal0s, Goals, !SI).
-
-:- pred select_reuses_disj(selection::in,
- selection_info::in, hlds_goals::in, hlds_goals::out,
- selection_info::in, selection_info::out) is det.
-
-select_reuses_disj(_Selection, _Info0, [], [], !SI) :-
- selection_end_branch(!SI).
-select_reuses_disj(Selection, Info0, [Goal0 | Goal0s],
- [Goal | Goals], !SI) :-
- select_reuses_2(Selection, Goal0, Goal, Info0, Info),
- selection_merge(Info, !SI),
- select_reuses_disj(Selection, Info0, Goal0s, Goals, !SI).
-
- %
- % This merges in the select_info left after the end of each
- % branch with the global one.
- %
-:- pred selection_merge(selection_info::in, selection_info::in,
- selection_info::out) is det.
-
-selection_merge(selection_info(LocalA, GlobalA, CondsA, LifoA),
- selection_info(LocalB, GlobalB, CondsB, LifoB),
- selection_info(Local, Global, Conds, Lifo)) :-
- Local = LocalA `set__union` LocalB,
- Global = GlobalA `set__union` GlobalB,
- Conds = CondsA ++ CondsB,
-
- LifoA = lifo(AllLocalsA, LocalsA, GlobalsA),
- LifoB = lifo(AllLocalsB, LocalsB, GlobalsB),
- Lifo = lifo([LocalsA | AllLocalsB], [], GlobalsB),
-
- require(unify(LocalsB, []),
- "selection_merge: LocalsB not empty"),
- require(unify(AllLocalsA, []),
- "selection_merge: AllLocalsA not equal"),
- require(unify(GlobalsA, GlobalsB),
- "selection_merge: Globals not equal").
-
-
- %
- % At the start of processing all branches of a
- % disj/switch/if_then_else this predicate should be called.
- %
-:- pred selection_start_branch(selection_info::in, selection_info::out) is det.
-
-selection_start_branch(selection_info(Local0, Global0, Conds0, Lifo0),
- selection_info(Local, Global, Conds, Lifo)) :-
- Local = set__init,
- Global = Local0 `set__union` Global0,
- Conds = Conds0,
-
- Lifo0 = lifo(AllLocals, Locals, Globals),
- Lifo = lifo(AllLocals, [], [Locals | Globals]).
-
- %
- % At the end of processing all branches of a
- % disj/switch/if_then_else this predicate should be called.
- %
-:- pred selection_end_branch(selection_info::in, selection_info::out) is det.
-
-selection_end_branch(selection_info(Local0, Global0, Conds0, Lifo0),
- selection_info(Local, Global, Conds, Lifo)) :-
- Local = set__init,
- Global = Local0 `set__union` Global0,
- Conds = Conds0,
-
- Lifo0 = lifo(AllLocals0, Locals0, Globals0),
- ( Globals0 = [G | Gs] ->
- Locals = list_merge([Locals0 | AllLocals0]) ++ G,
- Globals = Gs
- ;
- Locals = list_merge([Locals0 | AllLocals0]),
- Globals = []
- ),
- Lifo = lifo([], Locals, Globals).
-
- % [ [1a,2a], [2b,1b], [2c,3c,1c] ] -> [1a, 2b, 2c, 2a, 1b, 3c, 1c]
-:- func list_merge(list(list(T))) = list(T).
-
-list_merge(List) = Result :-
- list_merge(List, Tail, Head),
- ( Tail = [] ->
- Result = list__reverse(Head)
- ;
- Result = Head ++ list_merge(Tail)
- ).
-
-
-:- pred list_merge(list(list(T))::in, list(list(T))::out, list(T)::out) is det.
-
-list_merge([], [], []).
-list_merge([H | T], Tail, Head) :-
- (
- H = [],
- list_merge(T, Tail, Head)
- ;
- H = [X | Xs],
- list_merge(T, Tail0, Head0),
- Tail = [Xs | Tail0],
- Head = [X | Head0]
- ).
-
-:- pred select_reuses_unification(selection::in, unification::in,
- hlds_goal_info::in, hlds_goal_info::out,
- selection_info::in, selection_info::out) is det.
-
-select_reuses_unification(Selection, Unif, GoalInfo0, GoalInfo, !SI) :-
- Unif = construct(_Var, _ConsId, _Vars, _Ms, _HTC, _IsUniq, _Aditi),
- goal_info_get_reuse(GoalInfo0, ReuseInfo),
- (
- ReuseInfo = choice(construct(Pairs))
- ->
- PossibleCandidates = set__to_sorted_list(Pairs)
- ;
- error("sr_choice__apply_selection_unification")
- ),
-
- LocalReused0 = !.SI ^ local_used,
- GlobalReused = !.SI ^ global_used,
-
- (
- Selection = lifo,
- Locals = !.SI ^ lifo ^ local,
- Globals = !.SI ^ lifo ^ global,
- F = (pred(Var::in, LocalReuseVar::out) is semidet :-
- list__filter((pred(RV::in) is semidet :-
- Var = RV ^ var
- ), PossibleCandidates,
- [LocalReuseVar]),
- \+ set__member(Var, LocalReused0),
- \+ set__member(Var, GlobalReused)
- ),
- list__filter_map(F,
- Locals ++ list__condense(Globals), Candidates)
- ;
- Selection = random,
- % XXX If you ask me, I don't see much randomness around here.
- P = (pred(Choice::out) is nondet :-
- list__member(Choice, PossibleCandidates),
- ChoiceVar = Choice ^ var,
- \+ set__member(ChoiceVar, LocalReused0),
- \+ set__member(ChoiceVar, GlobalReused)
- ),
-
- solutions(P, Candidates)
- ;
- Selection = graph,
- require__error("(sr_choice) select_reuses_unification: selection graph is not an option at this place.")
- ),
- (
- Candidates = [Candidate | _]
- ->
- Candidate = reuse_var(ReuseVar, ReuseCond,
- MaybeConsIds, MaybeReuseFields),
- (
- MaybeConsIds = yes(ConsIds0),
- MaybeReuseFields = yes(ReuseFields0)
- ->
- ConsIds = ConsIds0,
- ReuseFields = ReuseFields0
- ;
- error("select_reuses_unification: no cons_ids.")
- ),
- set__insert(LocalReused0, ReuseVar, LocalReused),
- (
- ReuseCond = always,
- ConditionalReuse = no
- ;
- ReuseCond = condition(_, _, _),
- ConditionalReuse = yes
- ),
- goal_info_set_reuse(
- potential_reuse(cell_reused(ReuseVar,
- ConditionalReuse,
- ConsIds, ReuseFields)),
- GoalInfo0,
- GoalInfo),
- ReuseConditions = !.SI ^ reuse_conds,
- !:SI = !.SI ^ reuse_conds := [ReuseCond | ReuseConditions]
- ;
- LocalReused = LocalReused0,
- goal_info_set_reuse(
- potential_reuse(no_reuse),
- GoalInfo0,
- GoalInfo)
- ),
- !:SI = !.SI ^ local_used := LocalReused.
-
-select_reuses_unification(_Selection, Unif, GoalInfo, GoalInfo, !SI) :-
- Unif = deconstruct(Var, _ConsId, _Vars, _Modes, _CanFail, _CanCGC),
- Locals0 = !.SI ^ lifo ^ local,
- !:SI = !.SI ^ lifo ^ local := [Var | Locals0].
-
-select_reuses_unification(_Selection, Unif, GoalInfo, GoalInfo, !SI) :-
- Unif = assign(_, _).
-select_reuses_unification(_Selection, Unif, GoalInfo, GoalInfo, !SI) :-
- Unif = simple_test(_, _).
-select_reuses_unification(_Selection, Unif, GoalInfo, GoalInfo, !SI) :-
- Unif = complicated_unify(_, _, _).
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-
-:- pred determine_cgc(set(prog_var)::in, hlds_goal::in, hlds_goal::out) is det.
-
-determine_cgc(_ReusedVars, Goal - GoalInfo, Goal - GoalInfo) :-
- Goal = call(_PredId, _ProcId, _Args, _Builtin, _MaybeCtxt, _Name).
-
-determine_cgc(ReusedVars, Goal0 - GoalInfo0, Goal - GoalInfo) :-
- Goal0 = unify(Var, Rhs, Mode, Unif0, Ctxt),
- determine_cgc_unification(ReusedVars, Unif0, Unif, GoalInfo0, GoalInfo),
- Goal = unify(Var, Rhs, Mode, Unif, Ctxt).
-
-determine_cgc(_ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :-
- Goal0 = generic_call(_, _, _, _),
- Goal = Goal0.
-determine_cgc(_ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :-
- Goal0 = foreign_proc(_, _, _, _, _, _, _),
- Goal = Goal0.
-determine_cgc(_ReusedVars, Goal0 - _GoalInfo, _) :-
- Goal0 = shorthand(_),
- error("structure_reuse: shorthand.\n").
-
-determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :-
- Goal0 = if_then_else(Vars, If0, Then0, Else0),
- determine_cgc(ReusedVars, If0, If),
- determine_cgc(ReusedVars, Then0, Then),
- determine_cgc(ReusedVars, Else0, Else),
- Goal = if_then_else(Vars, If, Then, Else).
-
-determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :-
- Goal0 = switch(Var, CanFail, Cases0),
- determine_cgc_cases(ReusedVars, Cases0, Cases),
- Goal = switch(Var, CanFail, Cases).
-
-determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :-
- Goal0 = some(Vars, CanRemove, SomeGoal0),
- determine_cgc(ReusedVars, SomeGoal0, SomeGoal),
- Goal = some(Vars, CanRemove, SomeGoal).
-
-determine_cgc(ReusedVars, not(Goal0) - GoalInfo, not(Goal) - GoalInfo) :-
- determine_cgc(ReusedVars, Goal0, Goal).
-
-determine_cgc(ReusedVars, conj(Goal0s) - GoalInfo,
- conj(Goals) - GoalInfo) :-
- determine_cgc_list(ReusedVars, Goal0s, Goals).
-
-determine_cgc(ReusedVars, disj(Goal0s) - GoalInfo,
- disj(Goals) - GoalInfo) :-
- determine_cgc_list(ReusedVars, Goal0s, Goals).
-
-determine_cgc(ReusedVars, par_conj(Goal0s) - GoalInfo,
- par_conj(Goals) - GoalInfo) :-
- determine_cgc_list(ReusedVars, Goal0s, Goals).
-
-:- pred determine_cgc_cases(set(prog_var)::in, list(case)::in,
- list(case)::out) is det.
-
-determine_cgc_cases(_ReusedVars, [], []).
-determine_cgc_cases(ReusedVars, [Case0 | Case0s], [Case | Cases]) :-
- Case0 = case(ConsId, Goal0),
- determine_cgc(ReusedVars, Goal0, Goal),
- Case = case(ConsId, Goal),
- determine_cgc_cases(ReusedVars, Case0s, Cases).
-
-:- pred determine_cgc_list(set(prog_var)::in, hlds_goals::in,
- hlds_goals::out) is det.
-
-determine_cgc_list(_ReusedVars, [], []).
-determine_cgc_list(ReusedVars, [Goal0 | Goal0s], [Goal | Goals]) :-
- determine_cgc(ReusedVars, Goal0, Goal),
- determine_cgc_list(ReusedVars, Goal0s, Goals).
-
-:- pred determine_cgc_unification(set(prog_var)::in,
- unification::in, unification::out,
- hlds_goal_info::in, hlds_goal_info::out) is det.
-
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :-
- Unif = construct(_Var, _ConsId, _Vars, _Ms, _HTC, _IsUniq, _Aditi).
-
-determine_cgc_unification(ReusedVars, Unif0, Unif, GoalInfo0, GoalInfo) :-
- Unif0 = deconstruct(Var, ConsId, Vars, Modes, CanFail, _CanCGC),
-
- goal_info_get_reuse(GoalInfo0, ReuseInfo),
- ( ReuseInfo = choice(deconstruct(MaybeDies)) ->
- (
- MaybeDies = yes(Condition),
- goal_info_set_reuse(
- potential_reuse(cell_died),
- GoalInfo0,
- GoalInfo),
- ( set__member(Var, ReusedVars) ->
- CanCGC = no
- ;
- % XXX Currently we only compile time gc
- % cells which don't introduce a reuse
- % condition on the predicate.
- (
- Condition = always,
- CanCGC = yes
- ;
- Condition = condition(_, _, _),
- CanCGC = no
- )
- )
-
- ;
- MaybeDies = no,
- CanCGC = no,
- goal_info_set_reuse(
- potential_reuse(no_reuse),
- GoalInfo0,
- GoalInfo)
- )
- ;
- error("determine_cgc_unification")
- ),
- Unif = deconstruct(Var, ConsId, Vars, Modes, CanFail, CanCGC).
-
-
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :-
- Unif = assign(_, _).
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :-
- Unif = simple_test(_, _).
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :-
- Unif = complicated_unify(_, _, _).
-
-
-%-----------------------------------------------------------------------------%
-
Index: sr_choice_graphing.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_choice_graphing.m,v
retrieving revision 1.1.2.8
diff -u -r1.1.2.8 sr_choice_graphing.m
--- sr_choice_graphing.m 16 Jul 2004 08:05:40 -0000 1.1.2.8
+++ sr_choice_graphing.m 30 Jul 2004 03:38:46 -0000
@@ -7,14 +7,12 @@
% Module: sr_choice_graphing
% Main authors: nancy
%
-% Just as in module sr_choice, given a goal annotated with preliminary
-% possible reuse information, this pass computes the concrete assignements
-% of which constructions can profit of dead cells coming from deconstructions.
-% This module is presented as an alternative to sr_choice. The difference
-% lies in the way the assignements are computed: instead of using lifo/random
-% 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).
+% Given a goal annotated with preliminary possible reuse information, this pass
+% computes the concrete assignements of which constructions can profit of dead
+% cells coming from deconstructions. 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 which reflects the gain
@@ -87,9 +85,8 @@
% which might make that in one case, the constraints can be satisfied,
% but the other conditions can not.
%
-% XXX Current shortcoming compared to sr_choice: cells being deconstructed
-% in the different branches of a disjunction will not be reused after the
-% the disjunction. In sr_choice, this is made possible.
+% 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
@@ -97,9 +94,8 @@
% ..., X => g(... ), ... % X dies
% ),
% Y <= f(... ), ... % Y can reuse X
-% While sr_choice allows Y to reuse X (which is perfectly legal as
-% it dies in each of the branches of the disjunction), this will not
-% be discovered at this moment.
+% In this example, it is allowed to reuse X for Y. And it will also be
+% discovered by the analysis.
%
%-----------------------------------------------------------------------------%
@@ -123,6 +119,7 @@
% not possible for reuse.
:- pred sr_choice_graphing__process_goal(
background_info::in,
+ dead_cell_table::in,
hlds_goal::in, hlds_goal::out,
maybe(list(reuse_condition))::out,
io__state::di, io__state::uo) is det.
@@ -151,12 +148,6 @@
BG = background(Strategy, ModuleInfo, VarTypes).
%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-:- type program_point
- ---> pp(
- pp_context :: term__context,
- pp_path :: goal_path
- ).
:- type deconstruction_spec
---> decon(
decon_var :: prog_var,
@@ -208,22 +199,37 @@
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
-process_goal(Background, !Goal, MaybeConditions, !IO) :-
- process_goal_2(Background, !Goal, [], Conditions, !IO),
- clean_all_left_overs(!Goal),
+process_goal(Background, DeadCellTable0, !Goal, MaybeConditions, !IO) :-
+ globals__io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
+ process_goal_2(Background, DeadCellTable0, DeadCellTable1,
+ !Goal, [], Conditions, !IO),
+ dead_cell_table_remove_conditionals(DeadCellTable1,
+ DeadCellTable),
+ (
+ % If there are some unconditional dead cells unassigned, then
+ % annotate them for cgc.
+ \+ map__is_empty(DeadCellTable)
+ ->
+ maybe_write_string(VeryVerbose, "% Marking CGC's. \n", !IO),
+ check_cgc(DeadCellTable, !Goal)
+ ;
+ maybe_write_string(VeryVerbose, "% No CGC's. \n", !IO)
+ ),
(
Conditions = [_|_]
-> MaybeConditions = yes(Conditions)
; MaybeConditions = no
).
-:- pred process_goal_2(background_info::in, hlds_goal::in, hlds_goal::out,
+:- pred process_goal_2(background_info::in,
+ dead_cell_table::in, dead_cell_table::out,
+ hlds_goal::in, hlds_goal::out,
list(reuse_condition)::in,
list(reuse_condition)::out,
io__state::di, io__state::uo) is det.
-process_goal_2(Background, !Goal, !Conditions, !IO) :-
+process_goal_2(Background, !DC, !Goal, !Conditions, !IO) :-
globals__io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
- compute_match_table(Background, !.Goal, MatchTable, !IO),
+ compute_match_table(Background, !.DC, !.Goal, MatchTable, !IO),
(
multi_map__is_empty(MatchTable)
->
@@ -243,11 +249,20 @@
% 3. realise the reuses by explicitly annotating the
% procedure goal.
annotate_reuses(Match, !Goal),
+ % remove the deconstructions from the available map of
+ % dead cells:
+ list__foldl(
+ (pred(Dec::in, DCin::in, DCout::out) is det :-
+ PP = Dec ^ decon_pp,
+ dead_cell_table_remove(PP, DCin,
+ DCout)
+ ), Match ^ decon_specs, !DC),
% 4. Add the conditions involved in the reuses to the
% existing conditions.
merge_conditions(Match, !Conditions),
% 5. Process the goal for further reuse-matches.
- process_goal_2(Background, !Goal, !Conditions, !IO)
+ process_goal_2(Background, !DC, !Goal,
+ !Conditions, !IO)
;
true
)
@@ -306,10 +321,25 @@
:- pred dump_match_details(match::in, io__state::di, io__state::uo) is det.
dump_match_details(Match, !IO) :-
+ Conds = list__map(
+ (func(DeconSpec) = Cond :-
+ Cond = DeconSpec ^ decon_conds),
+ Match ^ decon_specs),
+ (
+ list__takewhile(
+ reuse_condition_equal(always),
+ Conds, _, [])
+ ->
+ CondsString = "A"
+ ;
+ CondsString = "C"
+ ),
+
D = list__length(Match ^ decon_specs),
C = list__length(Match ^ con_specs),
string__append_list(["d: ", int_to_string(D), ", c: ",
- int_to_string(C)], Details),
+ int_to_string(C),
+ ", Co: ", CondsString], Details),
io__write_string(Details, !IO).
:- pred dump_full_table(match_table::in, io__state::di, io__state::uo) is det.
@@ -347,39 +377,43 @@
% the code that follows that deconstruction.
:- pred compute_match_table(background_info::in,
+ dead_cell_table::in,
hlds_goal::in, match_table::out,
io__state::di, io__state::uo) is det.
-compute_match_table(Background, Goal, MatchTable, !IO) :-
+compute_match_table(Background, DC, Goal, MatchTable, !IO) :-
multi_map__init(MatchTable0),
- compute_match_table(Background, Goal, [], MatchTable0, MatchTable, !IO).
+ compute_match_table(Background, DC,
+ Goal, [], MatchTable0, MatchTable, !IO).
-:- pred compute_match_table(background_info::in, list(hlds_goal)::in,
+:- pred compute_match_table(background_info::in,
+ dead_cell_table::in, list(hlds_goal)::in,
match_table::in, match_table::out,
io__state::di, io__state::uo) is det.
-compute_match_table(_Background, [], !Table, !IO).
-compute_match_table(Background, [Goal | Goals], !Table, !IO) :-
- compute_match_table(Background, Goal, Goals, !Table, !IO).
+compute_match_table(_Background, _DC, [], !Table, !IO).
+compute_match_table(Background, DC, [Goal | Goals], !Table, !IO) :-
+ compute_match_table(Background, DC, Goal, Goals, !Table, !IO).
% compute_values(BG, CurrentGoal, Continuation, Values0, Values).
-:- pred compute_match_table(background_info::in, hlds_goal::in,
+:- pred compute_match_table(background_info::in,
+ dead_cell_table::in, hlds_goal::in,
list(hlds_goal)::in, match_table::in, match_table::out,
io__state::di, io__state::uo) is det.
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = conj(Goals),
% continuation Cont might be non-empty. This can occur in the case
% of if-then-elses, where the if- en then- parts are taken together.
list__append(Goals, Cont, NewGoals),
- compute_match_table(Background, NewGoals, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, NewGoals, !Table, !IO).
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = call(_, _, _, _, _, _),
- compute_match_table(Background, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Cont, !Table, !IO).
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = generic_call(_, _, _, _),
- compute_match_table(Background, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Cont, !Table, !IO).
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = switch(_, _, Cases),
list__map(
pred(C::in, G::out) is det:-
@@ -388,7 +422,7 @@
multi_map__init(Table0),
list__map_foldl(
pred(Goal::in, T::out, IO0::di, IO1::uo) is det:-
- ( compute_match_table(Background, Goal, [], Table0,
+ ( compute_match_table(Background, DC, Goal, [], Table0,
T, IO0, IO1) ),
Goals, SwitchTables, !IO),
list__foldl(multi_map__merge, SwitchTables, !Table),
@@ -404,14 +438,13 @@
;
true
),
- compute_match_table(Background, Cont, !Table, !IO).
-compute_match_table(Background, Expr - Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Cont, !Table, !IO).
+compute_match_table(Background, DC, Expr - Info, Cont, !Table, !IO) :-
Expr = unify(_Var, _Rhs, _Mode, Unification, _Context),
- goal_info_get_reuse(Info, ReuseInfo),
program_point_init(Info, PP),
(
- ReuseInfo = choice(deconstruct(yes(Condition))),
Unification = deconstruct(Var, ConsId, Args, _, _, _),
+ Condition = dead_cell_table_search(PP, DC),
% XXX this test should move to sr_dead!
\+ no_tag_type(Background ^ module_info,
Background ^ vartypes, Var)
@@ -424,14 +457,14 @@
;
true
),
- compute_match_table(Background, Cont, !Table, !IO).
+ compute_match_table(Background, DC, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = disj(Goals),
multi_map__init(DisjTable0),
list__map_foldl(
pred(G::in, T::out, IO0::di, IO1::uo) is det:-
- ( compute_match_table(Background, G, [],
+ ( compute_match_table(Background, DC, G, [],
DisjTable0, T, IO0, IO1) ),
Goals, DisjTables, !IO),
% Each of the DisjTables will contain an entry for each deconstruction
@@ -440,14 +473,15 @@
% disjunction.
list__foldl(multi_map__merge, DisjTables, !Table),
(
- process_possible_common_dead_vars(Background, Cont, DisjTables,
+ process_possible_common_dead_vars(Background,
+ Cont, DisjTables,
CommonDeadVarsDisjTables, !IO)
->
list__foldl(multi_map__merge, CommonDeadVarsDisjTables, !Table)
;
true
),
- compute_match_table(Background, Cont, !Table, !IO).
+ compute_match_table(Background, DC, Cont, !Table, !IO).
:- pred process_possible_common_dead_vars(background_info::in,
hlds_goals::in, list(match_table)::in,
@@ -487,20 +521,20 @@
multi_map__init(Table0),
multi_map__det_insert(Table0, CommonDeadVar, Match, Table).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = not(Goal),
% if Goal contains deconstructions, they should not
% be reused within Cont.
- compute_match_table(Background, Goal, [], !Table, !IO),
- compute_match_table(Background, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Goal, [], !Table, !IO),
+ compute_match_table(Background, DC, Cont, !Table, !IO).
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = some(_, _, Goal),
- compute_match_table(Background, Goal, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Goal, Cont, !Table, !IO).
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = if_then_else(_, If, Then, Else),
multi_map__init(Table0),
- compute_match_table(Background, If, [Then], Table0, TableThen, !IO),
- compute_match_table(Background, Else, [], Table0, TableElse, !IO),
+ compute_match_table(Background, DC, If, [Then], Table0, TableThen, !IO),
+ compute_match_table(Background, DC, Else, [], Table0, TableElse, !IO),
multi_map__merge(TableThen, !Table),
multi_map__merge(TableElse, !Table),
(
@@ -511,15 +545,15 @@
;
true
),
- compute_match_table(Background, Cont, !Table, !IO).
+ compute_match_table(Background, DC, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = foreign_proc(_, _, _, _, _, _, _),
- compute_match_table(Background, Cont, !Table, !IO).
-compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Cont, !Table, !IO).
+compute_match_table(Background, DC, Expr - _Info, Cont, !Table, !IO) :-
Expr = par_conj(_),
- compute_match_table(Background, Cont, !Table, !IO).
-compute_match_table(_Background, Expr - _Info, _Cont, !Table, !IO) :-
+ compute_match_table(Background, DC, Cont, !Table, !IO).
+compute_match_table(_Background, _DC, Expr - _Info, _Cont, !Table, !IO) :-
Expr = shorthand(_),
error("(sr_choice_graphing) shorthand goal should not occur.\n").
@@ -568,9 +602,6 @@
;
Background ^ strategy ^ selection = graph,
highest_match_in_list(ExclusiveMatches, !Match)
- ;
- Background ^ strategy ^ selection = random,
- require__error("(sr_choice_graphing) blabla not supported.")
),
!:Match = !.Match ^ match_degree := Degree.
@@ -631,63 +662,68 @@
program_point_init(Info, PP),
(
Unification = construct(Var, Cons, Args, _, _, _, _),
+
% The construction is still looking for
% reuse-possibilities...
- goal_info_get_reuse(Info, choice(_)),
+ goal_info_get_reuse(Info, ReuseInfo),
+ \+ assigned_reuse(ReuseInfo),
% Can fail if the construction can not reuse the
% deconstructed cell.
- verify_match(Background, Var, Cons, Args, PP, !Match),
+ verify_match(Background, Var, Cons, Args, PP, !Match)
- % XXX scope: this should be automatically satisfied, given
- % the way continuations are used to compute the reuse value in
- % the first place
- (
- goal_info_get_reuse(Info,
- choice(construct(ReuseVars)))
- ->
- PureReuseVars = set__map(
- func(RV) = V :-
- ( V = RV ^ var ),
- ReuseVars),
- (
- set__contains(PureReuseVars,
- match_get_dead_var(!.Match))
- ->
- true
- ;
- ReuseVarsStrings =
- list__map(int_to_string,
- list__map(var_to_int,
- to_sorted_list(PureReuseVars))),
- string__append_list([
- "(sr_choice_graphing) ",
- "value_of_dead_cel: ",
- "scoping error.\n",
- "Dead Variable ",
- int_to_string(
- var_to_int(
- match_get_dead_var(!.Match))),
- " is not in the list ",
- " of available vars: [",
- join_list(", ", ReuseVarsStrings),
- "]. \n"], Msg),
- error(Msg)
- )
- ;
- string__append_list([
- "(sr_choice_graphing) ",
- "value_of_dead_cel: ",
- "reuse for construction that didn't ",
- "have any candidates for reuse."], Msg),
- error(Msg)
- )
+ % Note on the scope: the dead variables automatically belong
+ % to the scope of the construction that is treated here,
+ % given the way continuations are used.
+% (
+% goal_info_get_reuse(Info,
+% choice(construct(ReuseVars)))
+% ->
+% PureReuseVars = set__map(
+% func(RV) = V :-
+% ( V = RV ^ var ),
+% ReuseVars),
+% (
+% set__contains(PureReuseVars,
+% match_get_dead_var(!.Match))
+% ->
+% true
+% ;
+% ReuseVarsStrings =
+% list__map(int_to_string,
+% list__map(var_to_int,
+% to_sorted_list(PureReuseVars))),
+% string__append_list([
+% "(sr_choice_graphing) ",
+% "value_of_dead_cel: ",
+% "scoping error.\n",
+% "Dead Variable ",
+% int_to_string(
+% var_to_int(
+% match_get_dead_var(!.Match))),
+% " is not in the list ",
+% " of available vars: [",
+% join_list(", ", ReuseVarsStrings),
+% "]. \n"], Msg),
+% error(Msg)
+% )
+% ;
+% string__append_list([
+% "(sr_choice_graphing) ",
+% "value_of_dead_cel: ",
+% "reuse for construction that didn't ",
+% "have any candidates for reuse."], Msg),
+% error(Msg)
+% )
->
true
;
true
).
+:- pred assigned_reuse(reuse_goal_info::in) is semidet.
+assigned_reuse(potential_reuse(_)).
+assigned_reuse(reuse(_)).
find_match_in_goal(Background, Goal - _Info, !Match) :-
Goal = disj(Branches),
@@ -1058,106 +1094,88 @@
).
%-----------------------------------------------------------------------------%
- % After the selection pass, a final pass is needed to clean up
- % all the pending reuse annotations. All choice-annotations
- % are replaced by either
- % - potential_reuse(cell_died) % unconditional death
- % - potentail_reuse(no_reuse)
- % All other reuse-annotations are kept as is.
-:- pred clean_all_left_overs(hlds_goal::in, hlds_goal::out) is det.
+ % After the selection pass, a final pass is performed to annotate all
+ % the deconstructions in which a cell dies unconditionally, and which
+ % has not yet been involved in a reuse.
+
+:- pred check_cgc(dead_cell_table::in,
+ hlds_goal::in, hlds_goal::out) is det.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(DC, G0 - I0, G - I):-
G0 = conj(Goals0),
- list__map(clean_all_left_overs, Goals0, Goals),
+ list__map(check_cgc(DC), Goals0, Goals),
G = conj(Goals),
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(_DC, G0 - I0, G - I):-
G0 = call( _, _, _, _, _, _),
G = G0,
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(_DC, G0 - I0, G - I):-
G0 = generic_call( _, _, _, _),
G = G0,
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(DC, G0 - I0, G - I):-
G0 = switch(A, B, Cases0),
list__map(
pred(C0::in, C::out) is det:-
( C0 = case(Cons, Goal0),
- clean_all_left_overs(Goal0, Goal),
+ check_cgc(DC, Goal0, Goal),
C = case(Cons, Goal) ),
Cases0, Cases),
G = switch(A, B, Cases),
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(DC, G0 - I0, G - I):-
G0 = unify(A, B, C, Unification0, D),
- goal_info_get_reuse(I0, ReuseInfo0),
- possible_cgc(Unification0, ReuseInfo0, Unification, ReuseInfo),
- G = unify(A, B, C, Unification, D),
- goal_info_set_reuse(ReuseInfo, I0, I).
-
-:- pred possible_cgc(hlds_goal__unification::in, reuse_goal_info::in,
- hlds_goal__unification::out, reuse_goal_info::out) is det.
-possible_cgc(Unif0, ReuseInfo0, Unif, ReuseInfo):-
+ program_point_init(I0, PP),
(
- Unif0 = deconstruct(A, B, C, D, E, _),
- ReuseInfo0 = choice(deconstruct(yes(always)))
- ->
- Unif = deconstruct(A, B, C, D, E, yes),
- ReuseInfo = potential_reuse(cell_died)
- ;
- Unif = Unif0,
- (
- ReuseInfo0 = choice(_)
- ->
- ReuseInfo = potential_reuse(no_reuse)
- ;
- ReuseInfo = ReuseInfo0
- )
+ Unification0 = deconstruct(A1, B1, C1, D1, E1, _),
+ Condition = dead_cell_table_search(PP, DC),
+ Condition = always
+ ->
+ Unification = deconstruct(A1, B1, C1, D1, E1, yes),
+ G = unify(A, B, C, Unification, D),
+ ReuseInfo = potential_reuse(cell_died),
+ goal_info_set_reuse(ReuseInfo, I0, I)
+ ;
+ G = G0,
+ I = I0
).
-
-clean_all_left_overs(G0 - I0, G - I):-
+
+check_cgc(DC, G0 - I0, G - I):-
G0 = disj(Goals0),
- list__map(clean_all_left_overs, Goals0, Goals),
+ list__map(check_cgc(DC), Goals0, Goals),
G = disj(Goals),
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(DC, G0 - I0, G - I):-
G0 = not(Goal0),
- clean_all_left_overs(Goal0, Goal),
+ check_cgc(DC, Goal0, Goal),
G = not(Goal),
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(DC, G0 - I0, G - I):-
G0 = some(A, B, Goal0),
- clean_all_left_overs(Goal0, Goal),
+ check_cgc(DC, Goal0, Goal),
G = some(A, B, Goal),
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(DC, G0 - I0, G - I):-
G0 = if_then_else(A, If0, Then0, Else0),
- clean_all_left_overs(If0, If),
- clean_all_left_overs(Then0, Then),
- clean_all_left_overs(Else0, Else),
+ check_cgc(DC, If0, If),
+ check_cgc(DC, Then0, Then),
+ check_cgc(DC, Else0, Else),
G = if_then_else(A, If, Then, Else),
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(_DC, G0 - I0, G - I):-
G0 = foreign_proc(_, _, _, _, _, _, _),
G = G0,
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(_DC, G0 - I0, G - I):-
G0 = par_conj(_),
G = G0,
I = I0.
-clean_all_left_overs(G0 - I0, G - I):-
+check_cgc(_DC, G0 - _I0, _G - _I):-
G0 = shorthand( _),
- G = G0,
- I = I0.
+ error("(sr_choice_graphing) check_cgc: shorthand.\n").
%-----------------------------------------------------------------------------%
-
-:- pred program_point_init(hlds_goal_info::in, program_point::out) is det.
-program_point_init(Info, PP) :-
- goal_info_get_context(Info, Context),
- goal_info_get_goal_path(Info, GoalPath),
- PP = pp(Context, GoalPath).
:- pred deconstruction_spec_init(prog_var::in, program_point::in, cons_id::in,
list(prog_var)::in, reuse_condition::in,
Index: sr_choice_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_choice_util.m,v
retrieving revision 1.1.2.3
diff -u -r1.1.2.3 sr_choice_util.m
--- sr_choice_util.m 2 Jun 2004 10:30:52 -0000 1.1.2.3
+++ sr_choice_util.m 30 Jul 2004 03:38:47 -0000
@@ -37,12 +37,11 @@
% candidates is either:
% - lifo: take the cell that has died the most recently with
% respect to the construction where it can be reused.
- % - random: pick the candidate randomly.
% - graph: build up a weighted graph, and select the
- % best fitting candidate (see sr_choice_graphing.m)
+ % best fitting candidate.
+ % Both strategies are implemented in module sr_choice_graphing.
:- type selection
---> lifo
- ; random
; graph
.
@@ -85,10 +84,14 @@
get_strategy(Strategy, ModuleInfo0, ModuleInfo) -->
io_lookup_string_option(structure_reuse_constraint, ConstraintStr),
- ( { ConstraintStr = "same_cons_id" } ->
+ (
+ { ConstraintStr = "same_cons_id" }
+ ->
{ Constraint = same_cons_id },
{ ModuleInfo1 = ModuleInfo0 }
- ; { ConstraintStr = "within_n_cells_difference" } ->
+ ;
+ { ConstraintStr = "within_n_cells_difference" }
+ ->
io_lookup_int_option(structure_reuse_constraint_arg, NCells),
{ Constraint = within_n_cells_difference(NCells) },
{ ModuleInfo1 = ModuleInfo0 }
@@ -99,13 +102,14 @@
{ module_info_incr_errors(ModuleInfo0, ModuleInfo1) }
),
io_lookup_string_option(structure_reuse_selection, SelectionStr),
- ( { SelectionStr = "lifo" } ->
+ (
+ { SelectionStr = "lifo" }
+ ->
{ Selection = lifo },
{ ModuleInfo = ModuleInfo1 }
- ; { SelectionStr = "random" } ->
- { Selection = random },
- { ModuleInfo = ModuleInfo1 }
- ; { SelectionStr = "graph" } ->
+ ;
+ { SelectionStr = "graph" }
+ ->
{ Selection = graph },
{ ModuleInfo = ModuleInfo1 }
;
Index: sr_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_data.m,v
retrieving revision 1.1.2.33
diff -u -r1.1.2.33 sr_data.m
--- sr_data.m 29 Jul 2004 02:00:01 -0000 1.1.2.33
+++ sr_data.m 30 Jul 2004 03:38:51 -0000
@@ -16,6 +16,7 @@
:- interface.
:- import_module hlds__hlds_data.
+:- import_module hlds__hlds_goal.
:- import_module hlds__hlds_module.
:- import_module hlds__hlds_pred.
:- import_module parse_tree__prog_data.
@@ -25,6 +26,27 @@
:- import_module bool, map, set, std_util, list, io, term.
%-----------------------------------------------------------------------------%
+:- type program_point
+ ---> pp(
+ pp_context :: term__context,
+ pp_path :: goal_path
+ ).
+:- pred program_point_init(hlds_goal_info::in, program_point::out) is det.
+
+:- type dead_cell_table == map(program_point, reuse_condition).
+:- func dead_cell_table_init = dead_cell_table.
+:- func dead_cell_table_search(program_point, dead_cell_table)
+ = reuse_condition is semidet.
+:- pred dead_cell_table_set(program_point::in, reuse_condition::in,
+ dead_cell_table::in, dead_cell_table::out) is det.
+:- pred dead_cell_table_remove(program_point::in,
+ dead_cell_table::in, dead_cell_table::out) is det.
+:- pred dead_cell_table_remove_conditionals(dead_cell_table::in,
+ dead_cell_table::out) is det.
+:- pred dead_cell_table_dump(dead_cell_table::in,
+ io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
:- type memo_reuse == maybe(list(reuse_condition)).
@@ -48,45 +70,6 @@
:- pred from_maybe_reuse_tuples_to_memo_reuse(maybe_reuse_tuples::in,
memo_reuse::out) is det.
%-----------------------------------------------------------------------------%
- % The information placed in the goal info which is used by
- % structure reuse.
- % This field should be initilaised to empty.
- % The sr_dead module replaces empty with choice.
- % The sr_choice&sr_indirect module replaces choice with
- % potential_reuse.
- % The sr_split module replaces potential_reuse with reuse for
- % the reuse-version of a procedure.
-:- type reuse_goal_info
- ---> empty
- ; choice(choice_info)
- ; potential_reuse(short_reuse_info)
- ; reuse(short_reuse_info).
-
-:- type short_reuse_info --->
- no_reuse
- ; cell_died
- ; cell_reused(
- % The variable selected
- % for reuse.
- prog_var,
- % Is the reuse conditional?
- bool,
- % What are the possible
- % cons_ids that the cell
- % to be reused can have.
- list(cons_id),
- % Which of the fields of
- % the cell to be reused
- % already contain the
- % correct value.
- list(bool)
- )
-
- % Call the reuse version of the
- % call and whether calling the
- % reuse version is conditional.
- ; reuse_call(bool)
- ; missed_reuse_call(list(string)).
:- type reuse_var
---> reuse_var(
@@ -143,7 +126,7 @@
% condition_init(Var, LFUi, LBUi, ALIASi, HVs, Condition).
:- pred reuse_condition_init(module_info::in, proc_info::in, prog_var::in,
set(prog_var)::in, set(prog_var)::in,
- alias_as::in, list(prog_var)::in,
+ alias_as::in,
reuse_condition::out) is det.
% Rename the reuse condition given a map from FromVars, to
@@ -214,7 +197,49 @@
:- import_module list, string, require, varset, bool, assoc_list.
%-----------------------------------------------------------------------------%
+program_point_init(Info, PP) :-
+ goal_info_get_context(Info, Context),
+ goal_info_get_goal_path(Info, GoalPath),
+ PP = pp(Context, GoalPath).
+
+dead_cell_table_init = map__init.
+dead_cell_table_search(PP, Table) = Table ^ elem(PP).
+dead_cell_table_set(PP, RC, Table0, Table) :-
+ map__set(Table0, PP, RC, Table).
+dead_cell_table_remove(PP, !Table) :-
+ map__det_remove(!.Table, PP, _, !:Table).
+dead_cell_table_remove_conditionals(!Table) :-
+ map__foldl(dead_cell_table_add_unconditional, !.Table,
+ dead_cell_table_init, !:Table).
+
+:- pred dead_cell_table_add_unconditional(program_point::in,
+ reuse_condition::in, dead_cell_table::in,
+ dead_cell_table::out) is det.
+dead_cell_table_add_unconditional(PP, C, !Table) :-
+ (
+ C = always
+ ->
+ dead_cell_table_set(PP, C, !Table)
+ ;
+ true
+ ).
+dead_cell_table_dump(Table, !IO) :-
+ io__write_string("\t\t|--------|\n", !IO),
+ map__foldl(dead_cell_entry_dump, Table, !IO),
+ io__write_string("\t\t|--------|\n", !IO).
+
+:- pred dead_cell_entry_dump(program_point::in, reuse_condition::in,
+ io__state::di, io__state::uo) is det.
+dead_cell_entry_dump(_PP, Cond, !IO) :-
+ Cond = always,
+ io__write_string("\t\t| always |\n", !IO).
+dead_cell_entry_dump(_PP, Cond, !IO) :-
+ Cond = condition(_, _, _),
+ io__write_string("\t\t| cond |\n", !IO).
+
+
+%-----------------------------------------------------------------------------%
reuse_condition_table_init = map__init.
reuse_condition_table_search(PredProcId, Table) = Table ^ elem(PredProcId).
reuse_condition_table_set(PredProcId, Conds, Table0, Table) :-
@@ -312,7 +337,8 @@
pa_alias_as__equal(LA1, LA2).
reuse_condition_init(ModuleInfo, ProcInfo,
- Var, LFUi, LBUi, ALIASi, HVs, Condition):-
+ Var, LFUi, LBUi, ALIASi, Condition):-
+ proc_info_headvars(ProcInfo, HVs),
% First determine the nodes to which the reuse is related.
% There are two cased:
% 1. Var is a headvar, then it is sufficient to keep the topcel
Index: sr_dead.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_dead.m,v
retrieving revision 1.1.2.26
diff -u -r1.1.2.26 sr_dead.m
--- sr_dead.m 1 Jul 2004 02:59:36 -0000 1.1.2.26
+++ sr_dead.m 30 Jul 2004 03:38:52 -0000
@@ -20,14 +20,13 @@
:- module structure_reuse__sr_dead.
:- interface.
-:- import_module hlds__hlds_goal.
:- import_module hlds__hlds_module.
:- import_module hlds__hlds_pred.
:- import_module possible_alias__pa_alias_as.
+:- import_module structure_reuse__sr_data.
:- pred sr_dead__process_goal(pred_id::in, proc_info::in, module_info::in,
- alias_as_table::in, hlds_goal::in, hlds_goal::out) is det.
-
+ alias_as_table::in, dead_cell_table::out) is det.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -35,447 +34,160 @@
:- implementation.
:- import_module hlds__hlds_data.
+:- import_module hlds__hlds_goal.
:- import_module parse_tree__prog_data.
:- import_module possible_alias__pa_alias_as.
:- import_module possible_alias__pa_run.
-:- import_module structure_reuse__sr_data.
:- import_module structure_reuse__sr_live.
:- import_module assoc_list, int, require.
:- import_module set, list, map, std_util.
-process_goal(_PredId, ProcInfo, ModuleInfo, AliasTable, !Goal) :-
+process_goal(_PredId, ProcInfo, ModuleInfo, AliasTable, DeadCellTable) :-
pa_alias_as__init(Alias0),
- hlds_pred__proc_info_headvars(ProcInfo, HeadVars),
- dead_cell_pool_init(HeadVars, Pool0),
- annotate_goal(ProcInfo, ModuleInfo, AliasTable, !Goal,
- Pool0, _Pool, Alias0, _Alias).
-
+ proc_info_goal(ProcInfo, Goal),
+ collect_dead_cells(ProcInfo, ModuleInfo, AliasTable, Goal,
+ Alias0, _Alias,
+ dead_cell_table_init, DeadCellTable).
%-----------------------------------------------------------------------------%
-:- pred annotate_goal(proc_info::in, module_info::in, alias_as_table::in,
- hlds_goal::in, hlds_goal::out,
- dead_cell_pool::in, dead_cell_pool::out,
- alias_as::in, alias_as::out) is det.
-
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias):-
- Expr0 = conj(Goals0),
- list__map_foldl2(
- annotate_goal(ProcInfo, HLDS, AliasTable),
- Goals0, Goals, !Pool, !Alias),
- Info = Info0,
+:- pred collect_dead_cells(proc_info::in, module_info::in, alias_as_table::in,
+ hlds_goal::in,
+ alias_as::in, alias_as::out,
+ dead_cell_table::in, dead_cell_table::out) is det.
+
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - _Info, !Alias, !DC) :-
Expr = conj(Goals),
- Goal = Expr - Info.
+ list__foldl2(collect_dead_cells(ProcInfo, HLDS, AliasTable),
+ Goals, !Alias, !DC).
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias):-
- Expr0 = call(PredId, ProcId, ActualVars, _, _, _),
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - _Info, !Alias, !DC) :-
+ Expr = call(PredId, ProcId, ActualVars, _, _, _),
proc_info_vartypes(ProcInfo, VarTypes),
list__map(map__lookup(VarTypes), ActualVars, ActualTypes),
pa_run__extend_with_call_alias(HLDS, ProcInfo, AliasTable,
- PredId, ProcId, ActualVars, ActualTypes, !Alias),
- Expr = Expr0,
- Info = Info0,
- Goal = Expr - Info.
-
-annotate_goal(_ProcInfo, _HLDS, _AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = generic_call(_, _, _, _),
- pa_alias_as__top("generic_call unhandled", !Alias),
- Goal = Expr0 - Info0.
-
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = switch(A, B, Cases0),
- goal_info_get_outscope(Info0, Outscope),
- list__map3(annotate_case(ProcInfo, HLDS, AliasTable,
- !.Pool, !.Alias),
- Cases0, Cases, ListPools, ListAliases),
- dead_cell_pool_least_upper_bound_disj(Outscope, ListPools, !:Pool),
- pa_alias_as__least_upper_bound_list(HLDS, ProcInfo, Info0,
- ListAliases, !:Alias),
- Info = Info0,
- Expr = switch(A, B, Cases),
- Goal = Expr - Info.
+ PredId, ProcId, ActualVars, ActualTypes, !Alias).
-annotate_goal(ProcInfo, HLDS, _AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = unify(_Var, _Rhs, _Mode, Unification0, _Context),
- unification_verify_reuse(HLDS, ProcInfo, Unification0, !.Alias,
- !Pool, Info0, Info),
+collect_dead_cells(_ProcInfo, _HLDS, _AliasTable, Expr - _Info, !Alias, !DC) :-
+ Expr = generic_call(_, _, _, _),
+ pa_alias_as__top("generic_call unhandled", !Alias).
+
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - _Info, !Alias, !DC) :-
+ Expr = switch(_A, _B, Cases),
+ Goals = list__map((func(C) = G :- C = case(_, G)), Cases),
+ annotate_disj(ProcInfo, HLDS, AliasTable, Goals, !Alias, !DC).
+
+:- pred annotate_disj(proc_info::in, module_info::in, alias_as_table::in,
+ hlds_goals::in, alias_as::in, alias_as::out,
+ dead_cell_table::in, dead_cell_table::out) is det.
+annotate_disj(ProcInfo, ModuleInfo, AliasTable, Goals, Alias0, Alias, !DC) :-
+ list__map_foldl(
+ (pred(G::in, A::out, DCin::in, DCout::out) is det :-
+ collect_dead_cells(ProcInfo, ModuleInfo, AliasTable,
+ G, Alias0, A, DCin, DCout)),
+ Goals, ListAliases, !DC),
+ pa_alias_as__least_upper_bound_list(ModuleInfo, ProcInfo,
+ ListAliases, Alias).
+
+collect_dead_cells(ProcInfo, HLDS, _AliasTable, Expr - Info, !Alias, !DC) :-
+ Expr = unify(_Var, _Rhs, _Mode, Unification, _Context),
+ program_point_init(Info, ProgramPoint),
+ unification_verify_reuse(HLDS, ProcInfo, Info, Unification,
+ ProgramPoint, !.Alias, !DC),
% XXX candidate for future optimization: if
% you annotate the deconstruct first, you might avoid
% creating the aliases altogether, thus reducing the
% number of aliases you cary along, and eventually
% having an impact on the analysis-time.
- pa_alias_as__extend_unification(HLDS, ProcInfo, Unification0,
- Info, !Alias),
- Expr = Expr0,
- Goal = Expr - Info.
+ pa_alias_as__extend_unification(HLDS, ProcInfo, Unification,
+ Info, !Alias).
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = disj(Goals0),
- Pool0 = !.Pool,
- Alias0 = !.Alias,
- (
- Goals0 = []
- ->
- Goals = Goals0
- ;
- list__map3(
- pred(Gin::in, Gout::out, P::out, A::out)
- is det :-
- (
- annotate_goal(ProcInfo, HLDS, AliasTable,
- Gin, Gout, Pool0, P,
- Alias0, A)
- ),
- Goals0, Goals,
- ListPools, ListAliases),
- goal_info_get_outscope(Info0, Outscope),
- dead_cell_pool_least_upper_bound_disj(Outscope,
- ListPools, !:Pool),
- pa_alias_as__least_upper_bound_list(HLDS, ProcInfo,
- Info0, ListAliases, !:Alias)
- ),
- Info = Info0,
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - _Info, !Alias, !DC) :-
Expr = disj(Goals),
- Goal = Expr - Info.
+ annotate_disj(ProcInfo, HLDS, AliasTable, Goals, !Alias, !DC).
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = not(NegatedGoal0),
- annotate_goal(ProcInfo, HLDS, AliasTable, NegatedGoal0, NegatedGoal,
- !Pool, !Alias),
- Info = Info0,
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - _Info, !Alias, !DC) :-
Expr = not(NegatedGoal),
- Goal = Expr - Info.
+ collect_dead_cells(ProcInfo, HLDS, AliasTable, NegatedGoal, !Alias, !DC).
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = some(A, B, SomeGoal0),
- % XXX
- annotate_goal(ProcInfo, HLDS, AliasTable,
- SomeGoal0, SomeGoal, !Pool, !Alias),
- Info = Info0,
- Expr = some(A, B, SomeGoal),
- Goal = Expr - Info.
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - _Info, !Alias, !DC) :-
+ Expr = some(_A, _B, SomeGoal),
+ collect_dead_cells(ProcInfo, HLDS, AliasTable,
+ SomeGoal, !Alias, !DC).
-annotate_goal(ProcInfo, HLDS, AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = if_then_else(Vars, Cond0, Then0, Else0),
- Pool0 = !.Pool,
+collect_dead_cells(ProcInfo, HLDS, AliasTable, Expr - Info, !Alias, !DC) :-
+ Expr = if_then_else(_Vars, Cond, Then, Else),
Alias0 = !.Alias,
- goal_info_get_outscope(Info0, Outscope),
- annotate_goal(ProcInfo, HLDS, AliasTable, Cond0, Cond, Pool0,
- PoolCond, Alias0, AliasCond),
- annotate_goal(ProcInfo, HLDS, AliasTable, Then0, Then, PoolCond,
- PoolThen, AliasCond, AliasThen),
- annotate_goal(ProcInfo, HLDS, AliasTable, Else0, Else, Pool0,
- PoolElse, Alias0, AliasElse),
- dead_cell_pool_least_upper_bound_disj(Outscope,
- [ PoolThen, PoolElse ], !:Pool),
- pa_alias_as__least_upper_bound_list(HLDS, ProcInfo, Info0,
- [ AliasThen, AliasElse ], !:Alias),
- Info = Info0,
- Expr = if_then_else(Vars, Cond, Then, Else),
- Goal = Expr - Info.
+ collect_dead_cells(ProcInfo, HLDS, AliasTable, Cond, !Alias, !DC),
+ collect_dead_cells(ProcInfo, HLDS, AliasTable, Then, !Alias, !DC),
+ collect_dead_cells(ProcInfo, HLDS, AliasTable, Else, Alias0, AliasElse,
+ !DC),
+ pa_alias_as__least_upper_bound_list(HLDS, ProcInfo, Info,
+ [ !.Alias, AliasElse ], !:Alias).
-annotate_goal(ProcInfo, HLDS, _AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = foreign_proc(Attrs, PredId, ProcId,
+collect_dead_cells(ProcInfo, HLDS, _AliasTable, Expr - Info, !Alias, !DC) :-
+ Expr = foreign_proc(Attrs, PredId, ProcId,
Vars, MaybeModes, Types, _),
extend_foreign_code(HLDS, ProcInfo, Attrs, PredId, ProcId,
- Vars, MaybeModes, Types, Info0, !Alias),
- Goal = Expr0 - Info0.
+ Vars, MaybeModes, Types, Info, !Alias).
-annotate_goal(_ProcInfo, _HLDS, _AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = par_conj(_),
- pa_alias_as__top("par_conj unhandled", !Alias),
- Goal = Expr0 - Info0.
+collect_dead_cells(_ProcInfo, _HLDS, _AliasTable, Expr - _Info, !Alias, !DC) :-
+ Expr = par_conj(_),
+ pa_alias_as__top("par_conj unhandled", !Alias).
-annotate_goal(_ProcInfo, _HLDS, _AliasTable, Expr0 - Info0, Goal,
- !Pool, !Alias) :-
- Expr0 = shorthand(_),
- pa_alias_as__top("shorthand unhandled", !Alias),
- Goal = Expr0 - Info0.
-
-:- pred annotate_case(proc_info::in, module_info::in, alias_as_table::in,
- dead_cell_pool::in, alias_as::in, case::in,
- case::out, dead_cell_pool::out, alias_as::out) is det.
-
-annotate_case(ProcInfo, HLDS, AliasTable, Pool0, Alias0, Case0,
- Case, Pool, Alias) :-
- Case0 = case(ConsId, Goal0),
- annotate_goal(ProcInfo, HLDS, AliasTable, Goal0, Goal,
- Pool0, Pool, Alias0, Alias),
- Case = case(ConsId, Goal).
+collect_dead_cells(_ProcInfo, _HLDS, _AliasTable, Expr - _Info, !Alias, !DC) :-
+ Expr = shorthand(_),
+ error("(sr_dead) shorthand unhandled(sr_dead).\n").
:- pred unification_verify_reuse(module_info::in, proc_info::in,
+ hlds_goal_info::in,
hlds_goal__unification::in,
- alias_as::in, dead_cell_pool::in, dead_cell_pool::out,
- hlds_goal_info::in, hlds_goal_info::out) is det.
+ program_point::in, alias_as::in,
+ dead_cell_table::in, dead_cell_table::out) is det.
-unification_verify_reuse(ModuleInfo, ProcInfo, Unification, Alias0,
- Pool0, Pool, Info0, Info) :-
+unification_verify_reuse(ModuleInfo, ProcInfo, Info,
+ Unification, PP, Alias0, !DC) :-
+ Unification = deconstruct(Var, ConsId, Vars, _, _, _),
+ goal_info_get_lfu(Info, LFU),
+ goal_info_get_lbu(Info, LBU),
(
- Unification = deconstruct(Var, ConsId, Vars, _, _, _)
- ->
- goal_info_get_lfu(Info0, LFU),
- goal_info_get_lbu(Info0, LBU),
(
- (
- % XXX things suchs as pred_const's cannot
- % die.
- cons_id_maybe_arity(ConsId, no)
- ;
- % Cells of arity 0 can not be reused.
- cons_id_arity(ConsId, 0),
- % Arity zero should imply that the size of the
- % cell is zero, just to be sure.
- list__length(Vars) = 0
- ;
- list__length(Vars) = 0
- ;
- set__union(LFU, LBU, LU),
- sr_live__init(Live0),
- pa_alias_as__live(ModuleInfo,
- ProcInfo, LU, Live0,
- Alias0, Live),
- sr_live__is_live(Var, Live)
- ;
- pa_alias_as__is_top(Alias0)
- )
-
- ->
- goal_info_set_reuse(choice(deconstruct(no)),
- Info0, Info),
- Pool = Pool0
+ % XXX things suchs as pred_const's cannot
+ % die.
+ cons_id_maybe_arity(ConsId, no)
;
- add_dead_cell(ModuleInfo, ProcInfo,
- Var, list__length(Vars),
- LFU, LBU,
- Alias0, Pool0, Pool,
- ReuseCondition),
- goal_info_set_reuse(
- choice(deconstruct(
- yes(ReuseCondition))), Info0, Info)
- )
- ;
- Unification = construct(_, ConsId, Vars, _, _, _, _)
- ->
- % XXX to avoid trying to reuse cells such as
- % pred_const, which don't have a valid cons_id
- % passed to them in ml_gen_new_object. ie
- % pred_const's.
- % Do not reuse cells for constructing functors
- % of arity zero.
- (
- ( cons_id_maybe_arity(ConsId, no) ;
- cons_id_arity(ConsId, 0) )
- ->
- set__init(ReuseVarsConds)
+ % Cells of arity 0 can not be reused.
+ cons_id_arity(ConsId, 0),
+ % Arity zero should imply that the size of the
+ % cell is zero, just to be sure.
+ list__length(Vars) = 0
+ ;
+ list__length(Vars) = 0
;
- dead_cell_pool_try_to_reuse(list__length(Vars),
- Pool0, ReuseVarsConds)
- ),
- goal_info_set_reuse(choice(construct(ReuseVarsConds)),
- Info0,
- Info),
- Pool = Pool0
- ;
- % assign
- % simple_test
- % complicated_unify
- Pool = Pool0,
- Info = Info0
- ).
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-
-% We use the notion of a pool to record all the dead cells that are available
-% for reuse within the scope of the goal that is considered at that moment.
-% This pool is used to identify the constructions which might possibly be
-% interested in reusing one of these available dead cells, and the reuse
-% conditions which would be implied by the reuse that is finally decided.
-
- % type used for threading through all the information about
- % eventual dead cells.
-:- type dead_cell_pool --->
- pool(
- list(prog_var), % real headvars
- map(prog_var, dead_extra_info)
- ).
-
- % for each dead cell, we need to keep it's reuse-condition,
- % and during this phase, fill in the names of all the vars
- % who would be interested in reusing the dead cell.
-:- type dead_extra_info --->
- extra(
- int, % The number of arguments of the dead cell.
- % Note that this can be different from the
- % arity of the constructor, as it may include
- % the fields for type-info's etc.
- reuse_condition,
- list(prog_var) % XXX for the moment always kept
- % empty
- ).
-
- % initialize dr_info
-:- pred dead_cell_pool_init(list(prog_var)::in, dead_cell_pool::out) is det.
- % test if empty
-:- pred dead_cell_pool_is_empty(dead_cell_pool::in) is semidet.
-
-:- pred add_dead_cell(module_info, proc_info, prog_var, int, set(prog_var),
- set(prog_var), alias_as,
- dead_cell_pool, dead_cell_pool,
- reuse_condition).
-:- mode add_dead_cell(in, in, in, in, in, in, in, in, out, out) is det.
-
- % given its reuse_condition, add the dead cell to dr_info.
-:- pred add_dead_cell(prog_var, int, reuse_condition,
- dead_cell_pool, dead_cell_pool) is det.
-:- mode add_dead_cell(in, in, in, in, out) is det.
-
-:- pred dead_cell_pool_least_upper_bound_disj(set(prog_var),
- list(dead_cell_pool), dead_cell_pool).
-:- mode dead_cell_pool_least_upper_bound_disj(in, in, out) is det.
-
-:- pred dead_cell_pool_least_upper_bound(dead_cell_pool,
- dead_cell_pool,
- dead_cell_pool).
-:- mode dead_cell_pool_least_upper_bound(in, in, out) is det.
-
- % given the set of currently non-local vars (all vars that
- % are in fact nonlocal, including the ones that were not
- % used within the goal that we are leaving), update the
- % dr_info::current_scope field.
-:- pred dead_cell_pool_leave_scope(set(prog_var), dead_cell_pool,
- dead_cell_pool).
-:- mode dead_cell_pool_leave_scope(in, in, out) is det.
-
-:- pred dead_cell_pool_try_to_reuse(int, dead_cell_pool,
- set(reuse_var)).
-:- mode dead_cell_pool_try_to_reuse(in, in, out) is det.
-
-dead_cell_pool_init(HVS, Pool):-
- map__init(Map),
- Pool = pool(HVS, Map).
-dead_cell_pool_is_empty(pool(_, Pool)):-
- map__is_empty(Pool).
-
-add_dead_cell(ModuleInfo, ProcInfo, Var, Size, LFU, LBU,
- Alias0, Pool0, Pool, Condition) :-
- Pool0 = pool(HVS, _Map0),
- reuse_condition_init(ModuleInfo, ProcInfo, Var, LFU, LBU,
- Alias0, HVS, Condition),
- add_dead_cell(Var, Size, Condition, Pool0, Pool).
-
-add_dead_cell(Var, Size, ReuseCond, pool(HVS, Pool0),
- pool(HVS, Pool)) :-
- % XXX Candidates are always zero. For the
- % moment we will not try to track this !
- Extra = extra(Size, ReuseCond, []),
- (
- map__insert(Pool0, Var, Extra, Pool1)
- ->
- Pool = Pool1
- ;
- error("(sr_dead) add_dead_cell: trying to add dead variable whilst already being marked as dead?")
- ).
-
-
-dead_cell_pool_least_upper_bound_disj(OutscopeVars, Pools, Pool):-
- list__map(dead_cell_pool_leave_scope(OutscopeVars),
- Pools, CleanedPools),
- (
- CleanedPools = [ C1 | _CR ]
- ->
- Pool0 = C1,
- list__foldl(
- dead_cell_pool_least_upper_bound,
- CleanedPools,
- Pool0,
- Pool)
- ;
- require__error("(sr_direct) dead_cell_pool_least_upper_bound_disj: trying to compute a lub_list of an empty list")
- ).
-
-dead_cell_pool_least_upper_bound(Pool1, Pool2, Pool) :-
- Pool1 = pool(HVS, Map1),
- map__init(Map0),
- Pool0 = pool(HVS, Map0),
- map__foldl(
- dead_cell_pool_merge_var(Pool2),
- Map1,
- Pool0,
- Pool).
-
-:- pred dead_cell_pool_merge_var(dead_cell_pool, prog_var,
- dead_extra_info,
- dead_cell_pool, dead_cell_pool).
-:- mode dead_cell_pool_merge_var(in, in, in, in, out) is det.
-
-dead_cell_pool_merge_var(P2, Key1, Extra1, P0, P) :-
- P2 = pool(_, Pool2),
- P0 = pool(HVS, Pool0),
- (
- map__search(Pool2, Key1, Extra2)
- ->
- Extra1 = extra(A1, R1, _Cands1),
- Extra2 = extra(A2, R2, _Cands2),
- int__min(A1, A2, A),
- reuse_condition_merge(R1, R2, R),
- % XXX candidates not tracked
- Extra = extra(A, R, []),
- (
- map__insert(Pool0, Key1, Extra, Pool01)
- ->
- P = pool(HVS, Pool01)
+ set__union(LFU, LBU, LU),
+ sr_live__init(Live0),
+ pa_alias_as__live(ModuleInfo, ProcInfo, LU,
+ Live0, Alias0, Live),
+ sr_live__is_live(Var, Live)
;
- require__error("(sr_direct) dead_cell_pool_merge_var: trying to add already existing key to pool")
+ pa_alias_as__is_top(Alias0)
)
- ;
- P = P0
+ ->
+ % No dead cell generated
+ true
+ ;
+ reuse_condition_init(ModuleInfo, ProcInfo,
+ Var, LFU, LBU, Alias0, ReuseCondition),
+ dead_cell_table_set(PP, ReuseCondition, !DC)
).
-dead_cell_pool_leave_scope(ScopeVarsSet, P0, P) :-
- P0 = pool(HVS, Pool0),
- set__to_sorted_list(ScopeVarsSet, ScopeVars),
- map__to_assoc_list(Pool0, AssocList0),
- list__filter(
- pred(Key::in) is semidet :-
- (
- Key = ProgVar - _Extra,
- list__member(ProgVar, ScopeVars)
- ),
- AssocList0,
- AssocList),
- map__from_assoc_list(AssocList, Pool),
- P = pool(HVS, Pool).
-
-dead_cell_pool_try_to_reuse(Size, Pool, Set) :-
- Pool = pool(_HVS, Map),
- map__to_assoc_list(Map, AssocList),
- list__filter(cons_can_reuse(Size), AssocList, CellsThatCanBeReused),
- list__map(to_pair_var_condition,
- CellsThatCanBeReused, VarConditionPairs),
- set__list_to_set(VarConditionPairs, Set).
-
-:- pred cons_can_reuse(int, pair(prog_var, dead_extra_info)).
-:- mode cons_can_reuse(in, in) is semidet.
-
-cons_can_reuse(Size, _Var - Extra) :-
- Extra = extra(DeadSize, _, _),
- Size =< DeadSize.
-
-:- pred to_pair_var_condition(pair(prog_var, dead_extra_info), reuse_var).
-:- mode to_pair_var_condition(in, out) is det.
+unification_verify_reuse(_, _, _, Unification, _, _, !DC) :-
+ Unification = construct(_, _, _, _, _, _, _).
+unification_verify_reuse(_, _, _, Unification, _, _, !DC) :-
+ Unification = assign(_, _).
+unification_verify_reuse(_, _, _, Unification, _, _, !DC) :-
+ Unification = simple_test(_,_).
+unification_verify_reuse(_, _, _, Unification, _, _, !DC) :-
+ Unification = complicated_unify(_, _, _).
-to_pair_var_condition(Var - Extra, reuse_var(Var, Condition, no, no)) :-
- Extra = extra(_, Condition, _).
Index: sr_direct.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_direct.m,v
retrieving revision 1.1.2.24
diff -u -r1.1.2.24 sr_direct.m
--- sr_direct.m 28 Jul 2004 02:31:59 -0000 1.1.2.24
+++ sr_direct.m 30 Jul 2004 03:38:53 -0000
@@ -45,7 +45,6 @@
:- import_module libs__globals.
:- import_module libs__options.
:- import_module parse_tree__prog_data.
-:- import_module structure_reuse__sr_choice.
:- import_module structure_reuse__sr_choice_graphing.
:- import_module structure_reuse__sr_dead.
:- import_module structure_reuse__sr_lbu.
@@ -79,14 +78,14 @@
passes_aux__write_proc_progress_message("% Analysing ",
PredId, ProcId, ModuleInfo, !IO),
- proc_info_goal(!.ProcInfo, Goal0),
+ proc_info_goal(!.ProcInfo, Goal1),
% 'Deadness' analysis: determine the deconstructions in which data
% structures potentially die.
passes_aux__maybe_write_string(VeryVerbose,
"%\tdeadness analysis...", !IO),
sr_dead__process_goal(PredId, !.ProcInfo, ModuleInfo,
- AliasTable, Goal0, Goal1) ,
+ AliasTable, DeadCellTable),
passes_aux__maybe_write_string(VeryVerbose, "done.\n", !IO),
% 'Choice' analysis: determine how the detected dead data structures
@@ -95,18 +94,11 @@
"%\tchoice analysis...\n", !IO),
proc_info_vartypes(!.ProcInfo, VarTypes),
- Strategy = strategy(_Constraint, Selection),
- (
- ( Selection = graph ; Selection = lifo )
- ->
- sr_choice_graphing__set_background_info(Strategy,
- ModuleInfo, VarTypes, Background),
- sr_choice_graphing__process_goal(Background, Goal1, Goal,
- MaybeReuseConditions, !IO)
- ;
- sr_choice__process_goal(Strategy, VarTypes, ModuleInfo,
- !.ProcInfo, Goal1, Goal, MaybeReuseConditions)
- ),
+ sr_choice_graphing__set_background_info(Strategy,
+ ModuleInfo, VarTypes, Background),
+ sr_choice_graphing__process_goal(Background,
+ DeadCellTable, Goal1, Goal,
+ MaybeReuseConditions, !IO),
(
VeryVerbose = yes
->
Index: sr_split.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_split.m,v
retrieving revision 1.1.2.21
diff -u -r1.1.2.21 sr_split.m
--- sr_split.m 28 Jul 2004 02:31:59 -0000 1.1.2.21
+++ sr_split.m 30 Jul 2004 03:38:55 -0000
@@ -416,8 +416,6 @@
:- pred convert_reuse(reuse_goal_info::in, reuse_goal_info::out) is det.
convert_reuse(R0, R):- R0 = empty, R = R0.
-convert_reuse(R0, _R):- R0 = choice(_),
- error("(sr_split) convert_reuse: reuse_goal_info should not be choice/1 at this stage. ").
convert_reuse(R0, R):- R0 = potential_reuse(S), R = reuse(S).
convert_reuse(R0, R):- R0 = reuse(_), R = R0.
Index: structure_reuse.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/structure_reuse.m,v
retrieving revision 1.1.2.13
diff -u -r1.1.2.13 structure_reuse.m
--- structure_reuse.m 30 Jun 2004 04:46:48 -0000 1.1.2.13
+++ structure_reuse.m 30 Jul 2004 03:38:55 -0000
@@ -10,7 +10,6 @@
:- module structure_reuse.
:- interface.
-:- include_module sr_choice.
:- include_module sr_choice_graphing.
:- include_module sr_choice_util.
:- include_module sr_data.
--
nancy.mazur at cs.kuleuven.ac.be ------------ Katholieke Universiteit Leuven -
tel: +32-16-327596 - fax: +32-16-327996 ------- Dept. of Computer Science -
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list