[m-rev.] [reuse] diff: rewritten sr_choice_graphing
Nancy Mazur
Nancy.Mazur at cs.kuleuven.ac.be
Fri Jul 16 18:04:44 AEST 2004
Hi,
===================================================================
Estimated hours taken: 20
Branches: reuse
Completely rewritten sr_choice_graphing:
* Changed the data structures recording all the reuse-matches, such
that multiple deconstructions can be seen as one single source of a
dead cell.
* Changed the treatment of disjunctions/switches/if-then-elses, such
that if each branch of the disjunction/switch/then-else deconstructs
the same variable, and each of these deconstructions yields a dead
cell, then this dead cell is also a potential candidate for being
reused _after_ the disjunction/switch/if-then-else.
Example:
:- type tt ---> f(int, int); g(int, int).
:- pred choose(tt::in, tt::out) is det.
choose(In, Out) :-
(
In = f(A,B)
;
In = g(A,B)
),
Out = f(A, B).
Previously, even when differing consId's where allowed, the graph-selection
strategy would not detect the reuse of In for constructing Out (while the old
lifo and random strategies would have). This is now changed, and the reuse is
succesfully identified.
sr_choice_graphing.m:
Completely rewritten.
Index: sr_choice_graphing.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_choice_graphing.m,v
retrieving revision 1.1.2.7
diff -u -r1.1.2.7 sr_choice_graphing.m
--- sr_choice_graphing.m 5 Jul 2004 03:50:10 -0000 1.1.2.7
+++ sr_choice_graphing.m 16 Jul 2004 07:50:54 -0000
@@ -132,12 +132,13 @@
:- import_module check_hlds__type_util.
:- import_module hlds__hlds_data.
+:- import_module hlds__passes_aux.
:- import_module libs__globals.
:- import_module libs__options.
:- import_module parse_tree__prog_data.
:- import_module term, map, float, bool, set, require, int.
-:- import_module string.
+:- import_module string, multi_map.
%-----------------------------------------------------------------------------%
:- type background_info
---> background(
@@ -150,32 +151,24 @@
BG = background(Strategy, ModuleInfo, VarTypes).
%-----------------------------------------------------------------------------%
-
- % In the process of choosing the most interesting
- % deconstruction-construction combinations, we identify each
- % deconstruction and each construction by a so called "contextvar".
- % This unique identification is done using the goal_path of the
- % unification. (the goal_path is filled by sr_direct__process_proc/7).
-:- type contextvar
- ---> context(
- pvar :: prog_var,
- context :: term__context,
- path :: goal_path
+%-----------------------------------------------------------------------------%
+:- type program_point
+ ---> pp(
+ pp_context :: term__context,
+ pp_path :: goal_path
).
-
- % To identify the reuse of a deconstructed cell by a specific
- % construction unification, we keep track of a so called "context" of
- % the reuse. This context consists of the identification of the
- % construction, the cons-id of the deconstructed cell it could be set
- % to reuse, and the type of reuse this would be.
- % Each construction can only reuse the cells of one specific
- % deconstruction, hence only one cons-id (instead of a list as was kept
- % before).
-:- type context_reuse_var
- ---> context_reuse_var(
- var :: contextvar,
- cons_id :: cons_id,
- reuse_type :: reuse_type
+:- type deconstruction_spec
+ ---> decon(
+ decon_var :: prog_var,
+ decon_pp :: program_point,
+ decon_cons_id :: cons_id,
+ decon_args :: prog_vars,
+ decon_conds :: reuse_condition
+ ).
+:- type construction_spec
+ ---> con(
+ con_pp :: program_point,
+ con_reuse :: reuse_type
).
% The reuse-type is a basic identification of whether the cons-ids
@@ -184,161 +177,168 @@
:- type reuse_type
---> reuse_type(
same_cons :: bool,
- arity_old :: int, % arity of dead cell
- arity_new :: int, % arity of new cell
- reuse_fields :: list(bool)
+ reuse_fields :: list(bool),
% Each 'no' means that the corresponding
% argument within the constructed cell does not
% need to be updated. Note that
% list__length(reuse_fields) = arity_old.
+ tmp_value :: float
).
-
- % For each deconstruction of a dead cell, we store a kind of "value"
- % for reusing that dead cell. This value contains the reuse-condition
- % of reusing the dead cell, the calculated best weight found for
- % reusing that cell, the constructions that can reuse the dead cell at
- % the given weight. Note that there can be more than one construction
- % reusing the available cell from a deconstruction.
- % E.g.:
- % X => f(...),
- % ( Y <= f(...) ; Y <= f(...) ).
- % In this case the dead cell of X can be reused for both constructions
- % of variable Y.
- % Finally, a value also contains a notion of "degree", which records
- % the number of constructions that can potentially reuse the dead cell.
-:- type value
- ---> entry(
- conds :: reuse_condition,
- weight :: maybe(float), % computed value.
- vars :: list(context_reuse_var),
- % variables involved with reusing the
- % dead var
- degree :: int
- % keep track of how much constructions
- % could be interested in reusing the
- % dead var.
+
+ % One match is a description of a list of deconstructions and a
+ % list of 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(
+ % dead_var :: prog_var,
+ decon_specs :: list(deconstruction_spec),
+ con_specs :: list(construction_spec),
+ match_value :: float,
+ match_degree :: int
).
-
- % Finally, during the process, we build a map of deconstructions with
- % their values.
-:- type values == map(contextvar, value).
-
-
-
-
+:- type match_table == multi_map(prog_var, match).
+%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
-process_goal(Background, Goal0, Goal, MaybeConditions) -->
- { Values0 = map__init },
- process_goal_2(Background, Goal0, Goal1, no, MaybeConditions, Values0),
- { clean_all_left_overs(Goal1, Goal) }.
+process_goal(Background, !Goal, MaybeConditions, !IO) :-
+ process_goal_2(Background, !Goal, [], Conditions, !IO),
+ clean_all_left_overs(!Goal),
+ (
+ Conditions = [_|_]
+ -> MaybeConditions = yes(Conditions)
+ ; MaybeConditions = no
+ ).
:- pred process_goal_2(background_info::in, hlds_goal::in, hlds_goal::out,
- maybe(list(reuse_condition))::in,
- maybe(list(reuse_condition))::out, values::in,
+ list(reuse_condition)::in,
+ list(reuse_condition)::out,
io__state::di, io__state::uo) is det.
-process_goal_2(Background, Goal0, Goal, MaybeCond0, MaybeCond, Values0) -->
- { compute_values_single_goal(Background, Goal0, Values0, Values1) },
+process_goal_2(Background, !Goal, !Conditions, !IO) :-
+ globals__io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
+ compute_match_table(Background, !.Goal, MatchTable, !IO),
(
- { map__is_empty(Values1) }
+ multi_map__is_empty(MatchTable)
->
- { Goal = Goal0 },
- { MaybeCond = MaybeCond0 }
- ;
- { highest_degree_value(Values1, ContextVar, HighestValue) },
- dump_table(Values1, ContextVar, HighestValue),
- { annotate_reuses(ContextVar, HighestValue, Goal0, Goal1) },
- { merge_conditions(HighestValue ^ conds,
- MaybeCond0, MaybeCond1) },
- process_goal_2(Background, Goal1, Goal,
- MaybeCond1, MaybeCond, Values0)
+ true
+ ;
+ % 1. select the deconstructions-constructions with
+ % highest value.
+ (
+ highest_match_degree_ratio(MatchTable, Match)
+ ->
+ % 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(Match, !Goal),
+ % 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)
+ ;
+ true
+ )
).
%-----------------------------------------------------------------------------%
-% dumping the reuse-selections to output
-%-----------------------------------------------------------------------------%
-:- pred dump_table(values::in, contextvar::in, value::in,
+:- func line_length = int.
+line_length = 79.
+
+:- pred dump_line(string::in, io__state::di, io__state::uo) is det.
+dump_line(Msg, !IO) :-
+ Prefix = "%---",
+ Start = string__append(Prefix, Msg),
+ Remainder = line_length - string__length(Start) - 1,
+ Line = Start ++ string__duplicate_char('-', Remainder),
+ io__write_string(Line, !IO),
+ io__write_string("%\n", !IO).
+
+:- pred maybe_dump_match_table(bool::in, match_table::in, match::in,
io__state::di, io__state::uo) is det.
-dump_table(Values, ContextVar, HighestValue) -->
- globals__io_lookup_bool_option(very_verbose, VeryVerbose),
+
+maybe_dump_match_table(VeryVerbose, MatchTable, HighestMatch, !IO) :-
(
- { VeryVerbose = yes }
+ VeryVerbose = yes
->
- io__write_string( "\n%---reuse table---------------------------------------------------------------%\n"),
- io__write_string( "%\t|\tvar\t|\tvalue\t|\tdegree\n"),
- io__write_string("%-sel- "),
- dump_selected_var(ContextVar, HighestValue),
- io__write_string( "%---full table----------------------------------------------------------------%\n"),
- dump_full_table(Values),
- io__write_string( "%-----------------------------------------------------------------------------%\n")
+ dump_line("reuse table", !IO),
+ io__write_string("%\t|\tvar\t|\tvalue\t|\tdegree\n", !IO),
+ dump_match("%-sel- ", HighestMatch, !IO),
+ dump_full_table(MatchTable, !IO),
+ dump_line("", !IO)
;
- []
+ true
).
-:- pred dump_selected_var(contextvar::in, value::in,
- io__state::di, io__state::uo) is det.
-dump_selected_var(context(Var, _Context, _GoalPath), Value) -->
- io__write_string("\t|\t"),
- io__write_int(term__var_to_int(Var)),
- io__write_string("\t|\t"),
- { Val = Value ^ weight },
+:- pred dump_match(string::in, match::in, io__state::di, io__state::uo) is det.
+dump_match(Prefix, Match, !IO):-
+ io__write_string(Prefix, !IO),
+ io__write_string("\t|\t", !IO),
+ io__write_int(term__var_to_int(match_get_dead_var(Match)), !IO),
+ io__write_string("\t|\t", !IO),
+ Val = Match ^ match_value,
(
- { Val = yes(Float) }
+ Val \= 0.00
->
- io__format("%.2f", [f(Float)])
+ io__format("%.2f", [f(Val)], !IO)
;
- io__write_string("no reuse")
+ io__write_string("-", !IO)
),
- { Degree = Value ^ degree },
- io__write_string("\t|\t"),
- io__write_int(Degree),
- io__write_string("\t"),
- dump_value(Value),
- io__nl.
-
-:- pred dump_value(value::in, io__state::di, io__state::uo) is det.
-dump_value(Value) -->
- io__write_string("("),
- io__write_list(Value ^ vars, ",\n%----- \t|\t\t|\t\t|\t\t ",
- dump_context_reuse_var),
- io__write_string(")").
+ Degree = Match ^ match_degree,
+ io__write_string("\t|\t", !IO),
+ io__write_int(Degree, !IO),
+ io__write_string("\t", !IO),
+ dump_match_details(Match, !IO),
+ io__nl(!IO).
+
+:- pred dump_match_details(match::in, io__state::di, io__state::uo) is det.
+dump_match_details(Match, !IO) :-
+ 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),
+ io__write_string(Details, !IO).
-:- pred dump_context_reuse_var(context_reuse_var::in,
- io__state::di, io__state::uo) is det.
-dump_context_reuse_var(ContextReuseVar) -->
- { ReuseType = ContextReuseVar ^ reuse_type },
- { ReuseType = reuse_type(SameCons, Aold, Anew,
- _ReuseFields)},
- { ( SameCons = yes -> S1 = "y" ; S1 = "n") },
- { string__int_to_string(arity_diff(ReuseType), S2) },
- { string__int_to_string(Aold, S3) },
- { string__int_to_string(Anew, S4) },
- { string__append_list([S1,"-",S2,"-",S3,"-",S4], String) },
- io__write_string(String).
-
+:- pred dump_full_table(match_table::in, io__state::di, io__state::uo) is det.
+dump_full_table(MatchTable, !IO) :-
+ (
+ multi_map__is_empty(MatchTable)
+ ->
+ dump_line("empty match table", !IO)
+ ;
+ dump_line("full table (start)", !IO),
+ multi_map__values(MatchTable, Matches),
+ list__foldl(dump_match("%-----"), Matches, !IO),
+ dump_line("full table (end)", !IO)
+ ).
-:- pred dump_full_table(values::in, io__state::di, io__state::uo) is det.
-dump_full_table(Values) -->
- { map__to_assoc_list(Values, AssocList) },
- list__foldl(
- pred(Entry::in, IO0::di, IO::uo) is det :-
- (
- Entry = ContextVar - Value,
- io__write_string("%----- ", IO0, IO1),
- dump_selected_var(ContextVar, Value, IO1, IO)
- ),
- AssocList).
-
+:- pred maybe_dump_full_table(bool::in, match_table::in, io__state::di,
+ io__state::uo) is det.
+maybe_dump_full_table(no, _M, !IO).
+maybe_dump_full_table(yes, M, !IO) :- dump_full_table(M, !IO).
%-----------------------------------------------------------------------------%
-:- pred merge_conditions(reuse_condition::in,
- maybe(list(reuse_condition))::in,
- maybe(list(reuse_condition))::out) is det.
+:- pred merge_conditions(match::in, list(reuse_condition)::in,
+ list(reuse_condition)::out) is det.
-merge_conditions(C, no, yes([C])).
-merge_conditions(C, yes(Conds), yes([C | Conds])).
+merge_conditions(Match, !Conditions) :-
+ P = (pred(D::in, C::out) is det :-
+ C = D ^ decon_conds),
+ list__map(P, Match ^ decon_specs, Conds),
+ list__append(Conds, !Conditions).
%-----------------------------------------------------------------------------%
@@ -346,221 +346,299 @@
% dead deconstruction encountered, the value is computed based on
% the code that follows that deconstruction.
-:- pred compute_values_single_goal(background_info::in,
- hlds_goal::in, values::in, values::out) is det.
+:- pred compute_match_table(background_info::in,
+ hlds_goal::in, match_table::out,
+ io__state::di, io__state::uo) is det.
-compute_values_single_goal(Background, Goal, Values0, Values):-
- compute_values(Background, Goal, [], Values0, Values).
+compute_match_table(Background, Goal, MatchTable, !IO) :-
+ multi_map__init(MatchTable0),
+ compute_match_table(Background, Goal, [], MatchTable0, MatchTable, !IO).
-:- pred compute_values(background_info::in,
- list(hlds_goal)::in, values::in, values::out) is det.
+:- pred compute_match_table(background_info::in, list(hlds_goal)::in,
+ match_table::in, match_table::out,
+ io__state::di, io__state::uo) is det.
-compute_values(_Background, []) --> [].
-compute_values(Background, [Goal | Goals]) -->
- compute_values(Background, Goal, Goals).
+compute_match_table(_Background, [], !Table, !IO).
+compute_match_table(Background, [Goal | Goals], !Table, !IO) :-
+ compute_match_table(Background, Goal, Goals, !Table, !IO).
% compute_values(BG, CurrentGoal, Continuation, Values0, Values).
-:- pred compute_values(background_info::in, hlds_goal::in, list(hlds_goal)::in,
- values::in, values::out) is det.
+:- pred compute_match_table(background_info::in, hlds_goal::in,
+ list(hlds_goal)::in, match_table::in, match_table::out,
+ io__state::di, io__state::uo) is det.
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = conj(Goals) },
+compute_match_table(Background, 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_values(Background, NewGoals).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = call(_, _, _, _, _, _) },
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = generic_call(_, _, _, _) },
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = switch(_, _, Cases) },
- { list__map(
+ list__append(Goals, Cont, NewGoals),
+ compute_match_table(Background, NewGoals, !Table, !IO).
+compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ Expr = call(_, _, _, _, _, _),
+ compute_match_table(Background, Cont, !Table, !IO).
+compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ Expr = generic_call(_, _, _, _),
+ compute_match_table(Background, Cont, !Table, !IO).
+compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ Expr = switch(_, _, Cases),
+ list__map(
pred(C::in, G::out) is det:-
( C = case(_, G) ),
- Cases, Goals) },
- list__foldl(
- pred(Goal::in, V0::in, V::out) is det:-
- ( compute_values(Background, Goal, [], V0, V) ),
- Goals),
- compute_values(Background, Cont).
-compute_values(Background, Expr - Info, Cont, Values0, Values):-
+ Cases, Goals),
+ multi_map__init(Table0),
+ list__map_foldl(
+ pred(Goal::in, T::out, IO0::di, IO1::uo) is det:-
+ ( compute_match_table(Background, Goal, [], Table0,
+ T, IO0, IO1) ),
+ Goals, SwitchTables, !IO),
+ list__foldl(multi_map__merge, SwitchTables, !Table),
+ % Each of the SwitchTables will contain an entry for each
+ % deconstruction yielding a dead variable. If every branch contains the
+ % same var dying, then we may need to check if it can not be used
+ % outside of the switch.
+ (
+ process_possible_common_dead_vars(Background, Cont,
+ SwitchTables, CommonDeadVarsTables, !IO)
+ ->
+ list__foldl(multi_map__merge, CommonDeadVarsTables, !Table)
+ ;
+ true
+ ),
+ compute_match_table(Background, Cont, !Table, !IO).
+compute_match_table(Background, 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, _, _, _, _, _),
+ Unification = deconstruct(Var, ConsId, Args, _, _, _),
% XXX this test should move to sr_dead!
\+ no_tag_type(Background ^ module_info,
Background ^ vartypes, Var)
->
- value_init(Condition, Val0),
- conjunction_value_of_dead_cel(Background, Unification,
- Cont, Val0, Val),
- (
- value_allows_reuse(Val)
- ->
- goal_info_get_context(Info, Context),
- goal_info_get_goal_path(Info, Path),
- ContextVar = context(Var, Context, Path),
- map__det_insert(Values0, ContextVar, Val, Values1)
- ;
- Values1 = Values0
- )
+ deconstruction_spec_init(Var, PP, ConsId, Args, Condition, DS),
+ match_init([DS], Match0),
+ find_best_match_in_conjunction(Background, Cont,
+ Match0, Match),
+ multi_map__set(!.Table, Var, Match, !:Table)
;
- Values1 = Values0
+ true
),
- compute_values(Background, Cont, Values1, Values).
+ compute_match_table(Background, Cont, !Table, !IO).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = disj(Goals) },
- list__foldl(
- pred(G::in, V0::in, V::out) is det:-
- ( compute_values(Background, G, [], V0, V) ),
- Goals),
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = not(Goal) },
+compute_match_table(Background, 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, [],
+ DisjTable0, T, IO0, IO1) ),
+ Goals, DisjTables, !IO),
+ % Each of the DisjTables will contain an entry for each deconstruction
+ % yielding a dead variable. If every branch contains the same var
+ % dying, then we may need to check if it can not be used outside of the
+ % disjunction.
+ list__foldl(multi_map__merge, DisjTables, !Table),
+ (
+ 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).
+
+:- pred process_possible_common_dead_vars(background_info::in,
+ hlds_goals::in, list(match_table)::in,
+ list(match_table)::out,
+ io__state::di, io__state::uo) is semidet.
+process_possible_common_dead_vars(Background, Cont, DisjTables,
+ ExtraTables, !IO) :-
+ globals__io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
+ maybe_write_string(VeryVerbose, "\n% Processing possible common dead vars.\n", !IO),
+ list__foldl(maybe_dump_full_table(VeryVerbose), DisjTables, !IO),
+ DisjTables = [First | Rest],
+ Intersect = (pred(T::in, Set0::in, Set::out) is det :-
+ map__keys(T, Keys),
+ Set = set__intersect(Set0, list_to_set(Keys))
+ ),
+ FirstSet = list_to_set(map__keys(First)),
+ list__foldl(Intersect, Rest, FirstSet, CommonDeadVars),
+ list__filter_map(process_common_var(Background, Cont, DisjTables),
+ to_sorted_list(CommonDeadVars), ExtraTables).
+
+:- pred process_common_var(background_info::in, hlds_goals::in,
+ list(match_table)::in, prog_var::in,
+ match_table::out) is semidet.
+process_common_var(Background, Cont, DisjTables, CommonDeadVar, Table) :-
+ P = (pred(T::in, DeconSpecs0::in, DeconSpecs::out) is det :-
+ multi_map__lookup(T, CommonDeadVar, Ms),
+ PP = (pred(M::in, Ds0::in, Ds::out) is det :-
+ D = M ^ decon_specs,
+ append(D, Ds0, Ds)),
+ list__foldl(PP, Ms, [], NewDeconSpecs),
+ append(DeconSpecs0, NewDeconSpecs, DeconSpecs)
+ ),
+ list__foldl(P, DisjTables, [], FullDeconSpecs),
+ match_init(FullDeconSpecs, Match0),
+ find_best_match_in_conjunction(Background, Cont, Match0, Match),
+ match_allows_reuse(Match), % can fail
+ multi_map__init(Table0),
+ multi_map__det_insert(Table0, CommonDeadVar, Match, Table).
+
+compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ Expr = not(Goal),
% if Goal contains deconstructions, they should not
% be reused within Cont.
- compute_values(Background, Goal, []),
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = some(_, _, Goal) },
- compute_values(Background, Goal, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = if_then_else(_, If, Then, Else) },
- compute_values(Background, If, [Then]),
- compute_values(Background, Else, []),
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = foreign_proc(_, _, _, _, _, _, _) },
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = par_conj(_) },
- compute_values(Background, Cont).
-compute_values(Background, Expr - _Info, Cont) -->
- { Expr = shorthand(_) },
- compute_values(Background, Cont).
+ compute_match_table(Background, Goal, [], !Table, !IO),
+ compute_match_table(Background, Cont, !Table, !IO).
+compute_match_table(Background, 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) :-
+ 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),
+ multi_map__merge(TableThen, !Table),
+ multi_map__merge(TableElse, !Table),
+ (
+ process_possible_common_dead_vars(Background, Cont,
+ [TableThen, TableElse], CommonDeadVarsTables, !IO)
+ ->
+ list__foldl(multi_map__merge, CommonDeadVarsTables, !Table)
+ ;
+ true
+ ),
+ compute_match_table(Background, Cont, !Table, !IO).
+
+compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ Expr = foreign_proc(_, _, _, _, _, _, _),
+ compute_match_table(Background, Cont, !Table, !IO).
+compute_match_table(Background, Expr - _Info, Cont, !Table, !IO) :-
+ Expr = par_conj(_),
+ compute_match_table(Background, Cont, !Table, !IO).
+compute_match_table(_Background, Expr - _Info, _Cont, !Table, !IO) :-
+ Expr = shorthand(_),
+ error("(sr_choice_graphing) shorthand goal should not occur.\n").
%-----------------------------------------------------------------------------%
+ % Compute the value of a dead cel with respect to its possible
+ % reuses. If reuse is possible, add the specification of the
+ % construction where it can be reused to the list of constructions
+ % already recorded in the match.
+
+ % In a conjunction, a dead cell can only be reused in at most one of
+ % its direct childs. This means that for each child a new value is
+ % computed, and at the end of the conjunction, we will only be
+ % interested in the one with the highest value.
+
+ % PS: note that one could keep them all, but then the elimination of
+ % the uninteresting branches is simply postponed to later, hence
+ % useless information is caried around.
- % compute the value of a dead cel with respect to its possible
- % reuses. If reuse is possible, collect the context_reuse_var
- % information of the constructions involved.
- % In every conjunction, the dead cell can only be reused once:
- % this means that for each branch of the conjunction, a separate
- % value must be computed, and only the one with the highest value
- % is kept.
-:- pred conjunction_value_of_dead_cel(background_info::in,
- unification::in, list(hlds_goal)::in,
- value::in, value::out) is det.
-
-conjunction_value_of_dead_cel(Background, Deconstruction,
- Cont, !Value) :-
- Val0 = !.Value,
+:- pred find_best_match_in_conjunction(background_info::in,
+ list(hlds_goal)::in, match::in, match::out) is det.
+
+find_best_match_in_conjunction(Background, Cont, !Match) :-
+ Match0 = !.Match,
list__map(
- pred(G::in, V::out) is det:-
- ( value_of_dead_cel_in_goal(Background,
- Deconstruction, G, Val0, V)),
- Cont, DisjunctiveVals),
- count_candidates(DisjunctiveVals, Degree),
+ pred(G::in, M::out) is det:-
+ ( find_match_in_goal(Background, G, Match0, M)),
+ Cont, ExclusiveMatches),
+ count_candidates(ExclusiveMatches, Degree),
(
Background ^ strategy ^ selection = lifo,
(
- value_empty(Val0),
- list__takewhile(value_empty, DisjunctiveVals,
+ % Only select a new candidate if there has not been
+ % selected any yet.
+ match_empty(Match0),
+ % If all matches are empty, the unification
+ % with FirstNonEmpty will fail, hence, we keep
+ % the old (empty) match as the solution for the
+ % conjunction.
+ list__takewhile(match_empty, ExclusiveMatches,
_EmptyVals, [FirstNonEmpty|_])
->
- !:Value= FirstNonEmpty
+ !:Match = FirstNonEmpty
;
- !:Value= Val0
+ !:Match = Match0
)
;
Background ^ strategy ^ selection = graph,
- highest_value_in_list(DisjunctiveVals, !Value)
+ highest_match_in_list(ExclusiveMatches, !Match)
;
Background ^ strategy ^ selection = random,
require__error("(sr_choice_graphing) blabla not supported.")
),
- !:Value = !.Value ^ degree := Degree.
+ !:Match = !.Match ^ match_degree := Degree.
- % compute the value of a dead cell with respect to a
- % disjunction. If reuse is possible within the branches, the value
- % of the disjunction is set to the average of the values of the
- % branches. Branches not allowing any reuse have value 0.
- % The context_reuse_vars are the union of all the
- % context_reuse_vars of the branches.
-:- pred disjunction_value_of_dead_cel(background_info::in,
- unification::in, list(hlds_goal)::in,
- value::in, value::out) is det.
-disjunction_value_of_dead_cel(Background, Deconstruction,
- Branches, Val0, Val):-
+ % 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. At the end, these matches are
+ % merged together into one single match, taking the average of
+ % match values to be the value of the final match.
+ % Each construction involved in the reuses is counted as a
+ % possibility for reuse, hence is reflected in the degree of the final
+ % match description.
+:- pred find_match_in_disjunction(background_info::in,
+ list(hlds_goal)::in, match::in, match::out) is det.
+find_match_in_disjunction(Background, Branches, !Match) :-
(
Branches = []
->
- Val = Val0
+ true
;
list__map(
- pred(G::in, V::out) is det:-
- ( value_of_dead_cel_in_goal(Background,
- Deconstruction, G, Val0, V)),
- Branches, BranchVals),
- count_candidates(BranchVals, Degree),
- average_value(BranchVals, Val1),
- Val = Val1 ^ degree := Degree
+ pred(G::in, M::out) is det:-
+ ( find_match_in_goal(Background, G, !.Match, M)),
+ Branches, BranchMatches),
+ % count_candidates(BranchMatches, Degree),
+ average_match(BranchMatches, !:Match)
).
-:- pred count_candidates(list(value)::in, int::out) is det.
-count_candidates(Values, Degree):-
+:- pred count_candidates(list(match)::in, int::out) is det.
+count_candidates(Matches, Degree):-
list__foldl(
- pred(Val::in, D0::in, D::out) is det:-
+ pred(Match::in, D0::in, D::out) is det:-
(
- D = D0 + Val ^ degree
+ D = D0 + Match ^ match_degree
),
- Values,
+ Matches,
0, Degree).
% Compute the value of a dead cell for a specific goal.
-:- pred value_of_dead_cel_in_goal(background_info::in,
- unification::in, hlds_goal::in,
- value::in, value::out) is det.
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - _Info) -->
- { Goal = conj(Goals) },
- conjunction_value_of_dead_cel(Background,
- Deconstruct, Goals).
-value_of_dead_cel_in_goal(_Background,
- _Deconstruct, Goal - _Info) -->
- { Goal = call(_, _, _, _, _, _) }.
-value_of_dead_cel_in_goal(_Background,
- _Deconstruct, Goal - _Info) -->
- { Goal = generic_call(_, _, _, _) }.
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - _Info) -->
- { Goal = switch(_, _, Cases) },
- { list__map(
+:- pred find_match_in_goal(background_info::in, hlds_goal::in,
+ match::in, match::out) is det.
+
+find_match_in_goal(Background, Goal - _Info, !Match) :-
+ Goal = conj(Goals),
+ find_best_match_in_conjunction(Background, Goals, !Match).
+find_match_in_goal(_Background, Goal - _Info, !Match) :-
+ Goal = call(_, _, _, _, _, _).
+find_match_in_goal(_Background, Goal - _Info, !Match) :-
+ Goal = generic_call(_, _, _, _).
+find_match_in_goal(Background, Goal - _Info, !Match) :-
+ Goal = switch(_, _, Cases),
+ list__map(
pred(C::in, G::out) is det:-
( C = case(_, G) ),
- Cases, Branches) },
- disjunction_value_of_dead_cel(Background,
- Deconstruct, Branches).
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - Info, Val0, Value):-
- Goal = unify(_, _, _, Unification, _Context),
+ Cases, Branches),
+ find_match_in_disjunction(Background, Branches, !Match).
+find_match_in_goal(Background, Goal - Info, !Match) :-
+ Goal = unify(_, _, _, Unification, _),
+ program_point_init(Info, PP),
(
Unification = construct(Var, Cons, Args, _, _, _, _),
- Deconstruct = deconstruct(DeadVar, DeadCons,
- DeadArgs, _, _, _),
+ % The construction is still looking for
+ % reuse-possibilities...
+ goal_info_get_reuse(Info, choice(_)),
+
% Can fail if the construction can not reuse the
% deconstructed cell.
- compute_new_value(Background, Var, DeadVar, Cons,
- DeadCons, Args, DeadArgs, Weight, ReuseType),
- % The construction is still looking for reuse-possibilities...
- goal_info_get_reuse(Info, choice(_)),
-
+ 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
@@ -573,7 +651,8 @@
( V = RV ^ var ),
ReuseVars),
(
- set__contains(PureReuseVars, DeadVar)
+ set__contains(PureReuseVars,
+ match_get_dead_var(!.Match))
->
true
;
@@ -587,7 +666,8 @@
"scoping error.\n",
"Dead Variable ",
int_to_string(
- var_to_int(DeadVar)),
+ var_to_int(
+ match_get_dead_var(!.Match))),
" is not in the list ",
" of available vars: [",
join_list(", ", ReuseVarsStrings),
@@ -603,53 +683,36 @@
error(Msg)
)
->
- make_contextvar(Var, Info, ContextVar),
- ContextReuseVar = context_reuse_var(
- ContextVar,
- DeadCons,
- ReuseType),
- Value = entry(Val0 ^ conds, yes(float(Weight)),
- [ContextReuseVar], 1)
+ true
;
- Value = Val0
+ true
).
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - _Info) -->
- { Goal = disj(Branches) },
- disjunction_value_of_dead_cel(Background,
- Deconstruct, Branches).
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - _Info) -->
- { Goal = not(NegatedGoal) },
- value_of_dead_cel_in_goal(Background,
- Deconstruct, NegatedGoal).
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - _Info) -->
- { Goal = some(_, _, SGoal) },
- value_of_dead_cel_in_goal(Background,
- Deconstruct, SGoal).
-value_of_dead_cel_in_goal(Background,
- Deconstruct, Goal - _Info, Val0, Value):-
+find_match_in_goal(Background, Goal - _Info, !Match) :-
+ Goal = disj(Branches),
+ find_match_in_disjunction(Background, Branches, !Match).
+find_match_in_goal(Background, Goal - _Info, !Match) :-
+ Goal = not(NegatedGoal),
+ find_match_in_goal(Background, NegatedGoal, !Match).
+find_match_in_goal(Background, Goal - _Info, !Match) :-
+ Goal = some(_, _, SGoal),
+ find_match_in_goal(Background, SGoal, !Match).
+find_match_in_goal(Background, Goal - _Info, !Match) :-
+ Match0 = !.Match,
Goal = if_then_else(_, If, Then, Else),
- conjunction_value_of_dead_cel(Background,
- Deconstruct, [If, Then], Val0, Val1),
- value_of_dead_cel_in_goal(Background,
- Deconstruct, Else, Val0, Val2),
- average_value([Val1, Val2], Value).
-value_of_dead_cel_in_goal(_Background,
- _Deconstruct, Goal - _Info) -->
- { Goal = foreign_proc(_, _, _, _, _, _, _) }.
-value_of_dead_cel_in_goal(_Background,
- _Deconstruct, Goal - _Info) -->
- { Goal = par_conj(_) }.
-value_of_dead_cel_in_goal(_Background,
- _Deconstruct, Goal - _Info) -->
- { Goal = shorthand(_) }.
+ find_best_match_in_conjunction(Background, [If, Then], !Match),
+ find_match_in_goal(Background, Else, Match0, Match2),
+ average_match([!.Match, Match2], !:Match).
+find_match_in_goal(_Background, Goal - _Info, !Match) :-
+ Goal = foreign_proc(_, _, _, _, _, _, _).
+find_match_in_goal(_Background, Goal - _Info, !Match) :-
+ Goal = par_conj(_).
+find_match_in_goal(_Background, Goal - _Info, !Match) :-
+ Goal = shorthand(_),
+ error("(sr_choice_graphing) shorthand goal should not occur.\n").
-
%-----------------------------------------------------------------------------%
% Gain = (Alfa + Gamma) * ArityNewCell + Beta
% - Gamma * (ArityNewCell - UptoDateFields)
@@ -664,6 +727,62 @@
% compute_new_value(Constraint, ArityNewCell, ArityDeadCell,
% UptoDateFields, MaybeFloat).
+:- pred verify_match(background_info::in, prog_var::in, cons_id::in,
+ list(prog_var)::in, program_point::in,
+ match::in, match::out) is semidet.
+verify_match(Background, NewVar, NewCons, NewArgs, PP, Match0, Match) :-
+ DeconSpecs = Match0 ^ decon_specs,
+ list__map(compute_reuse_type(Background, NewVar, NewCons, NewArgs),
+ DeconSpecs, MaybeReuseTypes),
+ glb_reuse_types(MaybeReuseTypes, yes(ReuseType)), % can fail
+ ConSpec = con(PP, ReuseType),
+ match_add_construction(ConSpec, Match0, Match).
+
+:- pred glb_reuse_types(list(maybe(reuse_type))::in,
+ maybe(reuse_type)::out) is det.
+
+glb_reuse_types(List, MaybeR) :-
+ (
+ List = [First|Rest],
+ list__foldl(glb_reuse_types_2, Rest, First, MaybeR)
+ ;
+ List = [],
+ error("(sr_choice_graphing) no reuse types.\n")
+ ).
+
+:- pred glb_reuse_types_2(maybe(reuse_type)::in, maybe(reuse_type)::in,
+ maybe(reuse_type)::out) is det.
+
+glb_reuse_types_2(MaybeR1, MaybeR2, MaybeR) :-
+ (
+ MaybeR1 = yes(R1),
+ MaybeR2 = yes(R2)
+ ->
+ R1 = reuse_type(SameCons1, Fields1, V1),
+ R2 = reuse_type(SameCons2, Fields2, V2),
+ R = reuse_type(SameCons1 `and` SameCons2,
+ Fields1 `ands` Fields2,
+ (V1 + V2) / 2.00 ),
+ MaybeR = yes(R)
+ ;
+ MaybeR = no
+ ).
+
+:- func ands(list(bool), list(bool)) = list(bool).
+ands(L1, L2) = L :-
+ (
+ length(L1) =< length(L2)
+ ->
+ L1b = L1,
+ L2b = take_upto(length(L1), L2)
+ ;
+ L1b = take_upto(length(L2), L1),
+ L2b = L2
+ ),
+ L = list__map_corresponding(bool__and, L1b, L2b).
+
+
+
:- func alfa_value = int is det.
:- func gamma_value = int is det.
:- func beta_value = int is det.
@@ -671,329 +790,273 @@
gamma_value = 1.
beta_value = 1.
-:- pred compute_new_value(background_info::in,
- prog_var::in, prog_var::in,
- cons_id::in, cons_id::in,
- list(prog_var)::in, list(prog_var)::in,
- int::out, reuse_type::out) is semidet.
+:- pred compute_reuse_type(background_info::in, prog_var::in, cons_id::in,
+ list(prog_var)::in, deconstruction_spec::in,
+ maybe(reuse_type)::out) is det.
+
+compute_reuse_type(Background, NewVar, NewCons, NewCellArgs, DeconSpec,
+ MaybeReuseType) :-
+ DeconSpec = decon(DeadVar, _, DeadCons, DeadCellArgs, _),
-compute_new_value(Background, NewVar, DeadVar, NewCons, DeadCons,
- NewCellArgs, DeadCellArgs, Weight, ReuseType) :-
Constraint = Background ^ strategy ^ constraint,
ModuleInfo = Background ^ module_info,
Vartypes = Background ^ vartypes,
NewArity = list__length(NewCellArgs),
DeadArity = list__length(DeadCellArgs),
- % 1. if the new cell has arity zero, it shouldn't be allowed to reuse
- % anything.
- NewArity \= 0,
-
- % 2. the new cell may not be bigger than the dead cell
- NewArity =< DeadArity,
-
- % 3. verify the reuse constraint, either same cons, or within a certain
- % arity difference:
- DiffArity = DeadArity - NewArity,
- ( NewCons = DeadCons -> SameCons = yes ; SameCons = no),
- (
+ (
+ % 1. if the new cell has arity zero, it shouldn't be allowed to
+ % reuse anything.
+ NewArity \= 0,
+
+ % 2. the new cell may not be bigger than the dead cell
+ NewArity =< DeadArity,
+
+ % 3. verify the reuse constraint, either same cons, or within a
+ % certain arity difference:
+ DiffArity = DeadArity - NewArity,
+ ( NewCons = DeadCons -> SameCons = yes ; SameCons = no),
+ (
Constraint = within_n_cells_difference(N),
DiffArity =< N
- ;
+ ;
Constraint = same_cons_id,
SameCons = yes
- ),
+ ),
- % 4. if all the checks are satisfied, determine the number of fields
- % that would not need an update if the construction would use the
- % deconstructed cell:
- has_secondary_tag(ModuleInfo, Vartypes, NewVar, NewCons, SecTag),
- has_secondary_tag(ModuleInfo, Vartypes, DeadVar, DeadCons, DeadSecTag),
- ReuseFields = already_correct_fields(SecTag, NewCellArgs,
- DeadSecTag - DeadCellArgs),
- UpToDateFields = list__length(list__delete_all(ReuseFields, no)),
- %
- % Finally, compute the weight of this reuse-configuration.
- ( SameCons = yes -> SameConsV = 0; SameConsV = 1),
- Weight = ( (alfa_value + gamma_value) * NewArity + beta_value
- - gamma_value * (NewArity - UpToDateFields)
- - beta_value * SameConsV
- - alfa_value * DiffArity ),
-
- Weight > 0,
- ReuseType = reuse_type(SameCons, DeadArity, NewArity,
- ReuseFields).
+ % 4. if all the checks are satisfied, determine the number of
+ % fields that would not need an update if the construction
+ % would use the deconstructed cell:
+ has_secondary_tag(ModuleInfo, Vartypes, NewVar,
+ NewCons, SecTag),
+ has_secondary_tag(ModuleInfo, Vartypes, DeadVar,
+ DeadCons, DeadSecTag),
+ ReuseFields = already_correct_fields(SecTag, NewCellArgs,
+ DeadSecTag - DeadCellArgs),
+ UpToDateFields = list__length(
+ list__delete_all(ReuseFields, no)),
+ %
+ % Finally, compute the value of this reuse-configuration.
+ ( SameCons = yes -> SameConsV = 0; SameConsV = 1),
+ Weight = ( (alfa_value + gamma_value) * NewArity + beta_value
+ - gamma_value * (NewArity - UpToDateFields)
+ - beta_value * SameConsV
+ - alfa_value * DiffArity ),
+ Weight > 0,
+ ReuseType = reuse_type(SameCons, ReuseFields, float(Weight))
+ ->
+ MaybeReuseType = yes(ReuseType)
+ ;
+ MaybeReuseType = no
+ ).
%-----------------------------------------------------------------------------%
% Once a dead cell is selected from the table, all the constructions
% involved with reusing this dead cell have to be marked.
-:- pred annotate_reuses(contextvar::in, value::in, hlds_goal::in,
+:- pred annotate_reuses(match::in, hlds_goal::in,
hlds_goal::out) is det.
-annotate_reuses(ContextVar, Value, E0 - I0, E - I):-
+annotate_reuses(Match, E0 - I0, E - I):-
E0 = conj(Goals0),
- list__map(annotate_reuses(ContextVar, Value), Goals0, Goals),
+ list__map(annotate_reuses(Match), Goals0, Goals),
E = conj(Goals),
I = I0.
-annotate_reuses(_ContextVar, _Value, E0 - I0, E - I):-
+annotate_reuses(_Match, E0 - I0, E - I):-
E0 = call(_,_,_,_,_,_),
E = E0,
I = I0.
-annotate_reuses(_ContextVar, _Value, E0 - I0, E - I):-
+annotate_reuses(_Match, E0 - I0, E - I):-
E0 = generic_call(_,_,_,_),
E = E0,
I = I0.
-annotate_reuses(ContextVar, Value, E0 - I0, E - I):-
+annotate_reuses(Match, E0 - I0, E - I):-
E0 = switch(V, CF, Cases0),
list__map(
pred(C0::in, C::out) is det:-
( C0 = case(Cons, Goal0),
- annotate_reuses(ContextVar, Value, Goal0, Goal),
+ annotate_reuses(Match, Goal0, Goal),
C = case(Cons, Goal)
),
Cases0, Cases),
E = switch(V, CF, Cases),
I = I0.
-:- pred make_contextvar(prog_var::in, hlds_goal_info::in,
- contextvar::out) is det.
-make_contextvar(Var, Info, ContextVar):-
- goal_info_get_context(Info, Context),
- goal_info_get_goal_path(Info, Path),
- ContextVar = context(Var, Context, Path).
-:- pred contextvar_equal(contextvar::in, contextvar::in) is semidet.
-contextvar_equal(C1, C2):-
- C1 = context(Var, Context, Path),
- C2 = context(Var, Context, Path).
-
-annotate_reuses(DeadContextVar, Value, E0 - I0, E - I):-
- E0 = unify(Var, _Rhs, _Mode, _Unification0, _Context),
- make_contextvar(Var, I0, ContextVar),
+:- pred program_point_equality(program_point::in, program_point::in)
+ is semidet.
+program_point_equality(C1, C2):-
+ C1 = pp(Context, Path),
+ C2 = pp(Context, Path).
+
+annotate_reuses(Match, E0 - I0, E - I):-
+ E0 = unify(_Var, _Rhs, _Mode, _Unification0, _Context),
+ program_point_init(I0, PP),
(
- contextvar_equal(ContextVar, DeadContextVar)
- ->
+ P = (pred(D::in) is semidet :-
+ program_point_equality(D ^ decon_pp, PP)),
+ list__filter(P, Match ^ decon_specs, [_DeconSpec])
+ ->
% then this must be a deconstruction
goal_info_set_reuse(potential_reuse(cell_died), I0, I),
E = E0
;
- list__filter(
- pred(ReuseContextVar::in) is semidet :-
- (
- contextvar_equal(ContextVar,
- ReuseContextVar ^ var)
- ),
- Value ^ vars,
- ReuseVars),
+ P = (pred(C::in) is semidet :-
+ program_point_equality(C ^ con_pp, PP)),
+ list__filter(P, Match ^ con_specs, [ConSpec])
+ ->
+ ConsIds = match_get_cons_ids(Match),
+ Condition = match_get_condition(Match),
+ ReuseFields = ConSpec ^ con_reuse ^ reuse_fields,
(
- ReuseVars = []
- ->
- I = I0,
- E = E0
+ Condition = always,
+ Conditional = no
;
- NoDups = list__remove_dups(ReuseVars),
- NoDups = [ReuseVar],
- ReuseVar = context_reuse_var(_, ConsId,
- ReuseType),
- ReuseFields = ReuseType ^ reuse_fields
- ->
- Cond = Value ^ conds,
- (
- Cond = always,
- Conditional = no
- ;
- Cond = condition(_,_,_),
- Conditional = yes
- ),
- CellReused = cell_reused(DeadContextVar ^ pvar,
- Conditional,
- [ConsId], ReuseFields),
- (
- Conditional = yes,
- KindReuse = potential_reuse(CellReused)
- ;
- Conditional = no,
- % If the reuse is unconditional, then
- % reuse is not just potentially possible,
- % but alwasy possible, so skipping the
- % potential phase is perfectly safe.
- % (see also sr_indirect__call_verify_reuse)
- KindReuse = reuse(CellReused)
- ),
- goal_info_set_reuse(KindReuse, I0, I),
- E = E0
- ;
- % ReuseVars = [_|_]
- require__error("(sr_choice_graphing) annotate_reuses: multiple reuses for same contextvariable.\n")
- )
+ Condition = condition(_,_,_),
+ Conditional = yes
+ ),
+ CellReused = cell_reused(match_get_dead_var(Match),
+ Conditional, ConsIds, ReuseFields),
+ (
+ Conditional = yes,
+ KindReuse = potential_reuse(CellReused)
+ ;
+ Conditional = no,
+ % If the reuse is unconditional, then reuse is not just
+ % potentially possible, but alwasy possible, so
+ % skipping the potential phase is perfectly safe. (see
+ % also sr_indirect__call_verify_reuse)
+ KindReuse = reuse(CellReused)
+ ),
+ goal_info_set_reuse(KindReuse, I0, I),
+ E = E0
+ ;
+ E = E0,
+ I = I0
).
-annotate_reuses(ContextVar, Value, E0 - I0, E - I):-
+annotate_reuses(Match, E0 - I0, E - I):-
E0 = disj(Goals0),
- list__map(annotate_reuses(ContextVar, Value), Goals0, Goals),
+ list__map(annotate_reuses(Match), Goals0, Goals),
E = disj(Goals),
I = I0.
-annotate_reuses(ContextVar, Value, E0 - I0, E - I):-
+annotate_reuses(Match, E0 - I0, E - I):-
E0 = not(Goal0),
- annotate_reuses(ContextVar, Value, Goal0, Goal),
+ annotate_reuses(Match, Goal0, Goal),
E = not(Goal),
I = I0.
-annotate_reuses(ContextVar, Value, E0 - I0, E - I):-
+annotate_reuses(Match, E0 - I0, E - I):-
E0 = some(Vars, CanRemove, Goal0),
- annotate_reuses(ContextVar, Value, Goal0, Goal),
+ annotate_reuses(Match, Goal0, Goal),
E = some(Vars, CanRemove, Goal),
I = I0.
-annotate_reuses(ContextVar, Value, E0 - I0, E - I):-
+annotate_reuses(Match, E0 - I0, E - I):-
E0 = if_then_else(V, If0, Then0, Else0),
- annotate_reuses(ContextVar, Value, If0, If),
- annotate_reuses(ContextVar, Value, Then0, Then),
- annotate_reuses(ContextVar, Value, Else0, Else),
+ annotate_reuses(Match, If0, If),
+ annotate_reuses(Match, Then0, Then),
+ annotate_reuses(Match, Else0, Else),
E = if_then_else(V, If, Then, Else),
I0 = I.
-annotate_reuses(_ContextVar, _Value, E0 - I0, E - I):-
+annotate_reuses(_Match, E0 - I0, E - I):-
E0 = foreign_proc(_, _, _, _, _, _, _),
E = E0,
I = I0.
-annotate_reuses(_ContextVar, _Value, E0 - I0, E - I):-
+annotate_reuses(_Match, E0 - I0, E - I):-
E0 = par_conj(_),
E = E0,
I = I0.
-annotate_reuses(_ContextVar, _Value, E0 - I0, E - I):-
+annotate_reuses(_Match, E0 - _I0, _E - _I):-
E0 = shorthand(_),
- E = E0,
- I = I0.
+ error("(sr_choice_graphing) shorthand goal should not occur.\n").
%-----------------------------------------------------------------------------%
% Genaral manipulations on values, value, etc..
%-----------------------------------------------------------------------------%
-:- pred highest_degree_value(values::in, contextvar::out, value::out) is det.
-highest_degree_value(Values0, Key, Value):-
- map__keys(Values0, Keys),
+:- pred highest_match_degree_ratio(match_table::in, match::out) is semidet.
+highest_match_degree_ratio(MatchTable, Match):-
+ multi_map__values(MatchTable, Matches),
+ list__sort(reverse_compare_matches_value_degree,
+ Matches, Sorted),
(
- Keys = [K|R]
- ->
- map__lookup(Values0, K, V),
- list__foldl(maximal_degree_value(Values0), R,
- K - V, Key - Value)
- ;
- require__error("(sr_choice_graphing) highest value: empty map.\n")
- ).
-
-:- pred maximal_degree_value(map(contextvar, value)::in,
- contextvar::in, pair(contextvar, value)::in,
- pair(contextvar, value)::out) is det.
-maximal_degree_value(Map, Var, TempMax, NewMax):-
- map__lookup(Map, Var, Value),
- TempMax = TempVar - TempValue,
- (
- % if the values are equal, the first solution is kept,
- % i.e. TempMax
- degree_value_gt(Value, TempValue)
- ->
- NewMax = Var - Value
+ Sorted = [Match|_],
+ \+ match_empty(Match)
;
- NewMax = TempVar - TempValue
+ Sorted = [],
+ error("sr_choice_graphing: empty multi_map.\n")
).
-:- pred degree_value_gt(value::in, value::in) is semidet.
-degree_value_gt(V1, V2):-
- Val1 = V1 ^ weight,
- Val2 = V2 ^ weight,
- (
- Val2 = no
- ;
- Val2 = yes(Float2),
- Val1 = yes(Float1),
- D1 = Float1 / float(V1 ^ degree),
- D2 = Float2 / float(V2 ^ degree),
- D1 > D2
- ).
-
-:- pred value_gt(value::in, value::in) is semidet.
-value_gt(V1, V2):-
- Val1 = V1 ^ weight,
- Val2 = V2 ^ weight,
- (
- Val2 = no
- ;
- Val2 = yes(Float2),
- Val1 = yes(Float1),
- Float1 > Float2
- ).
+:- pred compare_matches_value_degree(match::in, match::in,
+ comparison_result::out) is det.
+compare_matches_value_degree(Match1, Match2, Result) :-
+ match_value_degree(Match1, V1),
+ match_value_degree(Match2, V2),
+ compare(Result, V1, V2).
+:- pred reverse_compare_matches_value_degree(match::in, match::in,
+ comparison_result::out) is det.
+reverse_compare_matches_value_degree(Match1, Match2, Result) :-
+ compare_matches_value_degree(Match2, Match1, Result).
-:- pred value_allows_reuse(value::in) is semidet.
-value_allows_reuse(Value) :-
- Val = Value ^ weight,
- Val = yes(Float),
- % the computed value should be larger than zero.
- Float > 0.0.
-
-:- pred highest_value_in_list(list(value)::in, value::in, value::out) is det.
-highest_value_in_list([], Val0, Val0).
-highest_value_in_list([V | R], Val0, Val):-
+:- pred match_value_degree(match::in, float::out) is det.
+match_value_degree(Match, V) :-
(
- value_gt(V, Val0)
+ Match ^ match_value \= 0.00
->
- highest_value_in_list(R, V, Val)
- ;
- highest_value_in_list(R, Val0, Val)
- ).
+ V = Match ^ match_value / float(Match ^ match_degree)
+ ;
+ V = 0.00
+ ).
-:- pred average_value(list(value)::in, value::out) is det.
-average_value(List, Value):-
+:- pred compare_matches_value(match::in, match::in,
+ comparison_result::out) is det.
+compare_matches_value(Match1, Match2, Result) :-
+ V1 = Match1 ^ match_value,
+ V2 = Match2 ^ match_value,
+ compare(Result, V1, V2).
+:- pred reverse_compare_matches_value(match::in, match::in,
+ comparison_result::out) is det.
+reverse_compare_matches_value(Match1, Match2, Result) :-
+ compare_matches_value(Match2, Match1, Result).
+
+:- pred match_allows_reuse(match::in) is semidet.
+match_allows_reuse(Match) :-
+ Constructions = Match ^ con_specs,
+ Value = Match ^ match_value,
+ Constructions = [_|_],
+ Value > 0.00.
+
+:- pred highest_match_in_list(list(match)::in, match::in, match::out) is det.
+highest_match_in_list(Matches, Match0, Match) :-
+ list__sort(reverse_compare_matches_value, [Match0 | Matches], Sorted),
(
- List = [ Val1 | _ ]
- ->
- list__length(List, Length),
- list__foldl2(
- pred(V::in, S0::in, S::out, R0::in, R::out) is det:-
- (
- MaybeVal = V ^ weight,
- ReuseVars = V ^ vars,
- (
- MaybeVal = yes(Fnew),
- (
- S0 = yes(F0)
- ->
- S = yes(F0 + Fnew)
- ;
- S = yes(Fnew)
- ),
- list__append(ReuseVars, R0, R)
- ;
- MaybeVal = no,
- S = S0, R = R0
- )
- ),
- List,
- no, TotalS,
- [], ContextReuseVars ),
- (
- TotalS = yes(Float)
- ->
- AverageFloat = Float / float(Length),
- AverageVal = yes(AverageFloat)
- ;
- AverageVal = no
- ),
- Value = entry(Val1 ^ conds, AverageVal, ContextReuseVars, 1)
+ Sorted = [Match|_]
;
- require__error("(sr_choice_graphing) average_value: empty list.\n")
+ Sorted = [],
+ error("sr_choice_graphing: list_sort returned empty list.\n")
+ ).
+
+ % Given a list of matches concerning the same (list of) deconstruction,
+ % compute the average reuse value of that deconstruction. This means
+ % merging all the constructions together into one list, and using the
+ % average value of the reuses of each of the matches. The final degree
+ % of the match is set to the sum of all degrees.
+:- pred average_match(list(match)::in, match::out) is det.
+average_match(List, AverageMatch):-
+ (
+ List = [First|Rest],
+ list__length(List, Length),
+ P = (pred(M::in, Acc0::in, Acc::out) is det :-
+ DeconSpecs = Acc0 ^ decon_specs,
+ ConSpecs = append(Acc0 ^ con_specs, M ^ con_specs),
+ Val = Acc0 ^ match_value + M ^ match_value,
+ Deg = Acc0 ^ match_degree + M ^ match_degree,
+ Acc = match(DeconSpecs, ConSpecs, Val, Deg)),
+ list__foldl(P, Rest, First, Match0),
+ AverageMatch = (Match0 ^ match_value :=
+ (Match0 ^ match_value / float(Length)))
+ ;
+ List = [],
+ require__error("(sr_choice_graphing) average_match: empty list.\n")
).
-
-
-:- pred value_init(reuse_condition::in, value::out) is det.
-value_init(Cond, entry(Cond, no, [], 0)).
-
-:- pred value_empty(value::in) is semidet.
-value_empty(entry(_, no, _, _)).
-
-:- func arity_diff(reuse_type) = int.
-arity_diff(T) = R :-
- T = reuse_type(_, O, N, _),
- R = O - N.
-
%-----------------------------------------------------------------------------%
% After the selection pass, a final pass is needed to clean up
% all the pending reuse annotations. All choice-annotations
@@ -1087,3 +1150,73 @@
G0 = shorthand( _),
G = G0,
I = I0.
+
+%-----------------------------------------------------------------------------%
+
+:- 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,
+ deconstruction_spec::out) is det.
+deconstruction_spec_init(Var, PP, ConsId, Args, Cond, DS) :-
+ DS = decon(Var, PP, ConsId, Args, Cond).
+
+:- pred match_init(list(deconstruction_spec)::in, match::out) is det.
+match_init(DS, match(DS, [], 0.00, 0)).
+
+:- pred match_empty(match::in) is semidet.
+match_empty(match(_, [], _, _)).
+
+:- func match_get_dead_var(match) = prog_var.
+match_get_dead_var(Match) = Var :-
+ GetVar = (pred(D::in, V::out) is det :-
+ V = D ^ decon_var),
+ list__map(GetVar, Match ^ decon_specs, DeadVars0),
+ list__remove_dups(DeadVars0, DeadVars),
+ (
+ DeadVars = [Var|Rest],
+ (
+ Rest = [_|_]
+ ->
+ error("(sr_choice_graphing) too many dead vars.\n")
+ ;
+ true
+ )
+ ;
+ DeadVars = [],
+ error("(sr_choice_graphing) too few dead vars.\n")
+ ).
+
+:- func match_get_cons_ids(match) = list(cons_id).
+match_get_cons_ids(Match) = ConsIds :-
+ GetConsId = (pred(D::in, C::out) is det :-
+ C = D ^ decon_cons_id),
+ list__map(GetConsId, Match ^ decon_specs, ConsIds).
+
+:- func match_get_condition(match) = reuse_condition.
+match_get_condition(Match) = Condition :-
+ GetCond = (pred(D::in, C::out) is det :-
+ C = D ^ decon_conds),
+ list__map(GetCond, Match ^ decon_specs, Conditions),
+ (
+ Conditions = [First | Rest],
+ list__foldl(reuse_condition_merge, Rest, First, Condition)
+ ;
+ Conditions = [],
+ error("(sr_choice_graphing) no reuse conditions.\n")
+ ).
+
+:- pred match_add_construction(construction_spec::in, match::in,
+ match::out) is det.
+match_add_construction(ConSpec, Match0, Match) :-
+ Match0 = match(DeconSpecs0, ConSpecs0, Value0, Degree0),
+ ConSpecs = [ConSpec | ConSpecs0],
+ Degree = Degree0 + 1,
+ FDegree0 = float(Degree0),
+ FDegree = float(Degree),
+ Value = (Value0 * FDegree0 + ConSpec ^ con_reuse ^ tmp_value) / FDegree,
+ Match = match(DeconSpecs0, ConSpecs, Value, Degree).
Index: sr_direct.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_direct.m,v
retrieving revision 1.1.2.23
diff -u -r1.1.2.23 sr_direct.m
--- sr_direct.m 5 Jul 2004 03:50:10 -0000 1.1.2.23
+++ sr_direct.m 16 Jul 2004 07:50:58 -0000
@@ -89,7 +89,7 @@
% 'Choice' analysis: determine how the detected dead data structures
% can be reused locally.
passes_aux__maybe_write_string(VeryVerbose,
- "%\tchoice analysis...", !IO),
+ "%\tchoice analysis...\n", !IO),
proc_info_vartypes(!.ProcInfo, VarTypes),
% XXX Getting the strategy also performs the check whether the
--
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