[m-rev.] for review: [CTGC] direct structure reuse analysis (2/2)
Nancy Mazur
Nancy.Mazur at cs.kuleuven.ac.be
Thu Apr 27 20:24:20 AEST 2006
Index: compiler/structure_reuse.direct.detect_garbage.m
===================================================================
RCS file: compiler/structure_reuse.direct.detect_garbage.m
diff -N compiler/structure_reuse.direct.detect_garbage.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/structure_reuse.direct.detect_garbage.m 27 Apr 2006 09:30:40 -0000
@@ -0,0 +1,237 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: structure_reuse.direct.detect_garbage.m
+% Main authors: nancy
+%
+% Detect where datastructures become garbage in a given procedure: construct
+% a dead cell table.
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.structure_reuse.direct.detect_garbage.
+
+:- interface.
+
+ % Using the sharing table listing all the structure sharing of all
+ % the known procedures, return a table of all data structures that may
+ % become available for reuse (i.e. cells that may become dead) of a given
+ % procedure goal. The table also records the reuse condition associated
+ % with each of the dead cells.
+ %
+:- pred determine_dead_deconstructions(module_info::in, proc_info::in,
+ sharing_as_table::in, hlds_goal::in, dead_cell_table::out) is det.
+
+:- implementation.
+
+:- import_module check_hlds.type_util.
+
+:- import_module pair.
+
+determine_dead_deconstructions(ModuleInfo, ProcInfo, SharingTable,
+ Goal, DeadCellTable):-
+ % In this process we need to know the sharing at each program point,
+ % which boils down to reconstructing that sharing information based on the
+ % sharing recorded in the sharing table.
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo, SharingTable,
+ Goal, sharing_as_init, _, dead_cell_table_init, DeadCellTable).
+
+ % Process a procedure goal, determining the sharing at each subgoal, as
+ % well as constructing the table of dead cells.
+ %
+ % This means:
+ % - at each program point: compute sharing
+ % - at deconstruction unifications: check for a dead cell.
+ %
+:- pred determine_dead_deconstructions_2(module_info::in, proc_info::in,
+ sharing_as_table::in, hlds_goal::in, sharing_as::in, sharing_as::out,
+ dead_cell_table::in, dead_cell_table::out) is det.
+
+determine_dead_deconstructions_2(ModuleInfo, ProcInfo, SharingTable,
+ TopGoal, !SharingAs, !DeadCellTable) :-
+
+ TopGoal = GoalExpr - GoalInfo,
+ (
+ GoalExpr = conj(_, Goals),
+ list.foldl2(
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo,
+ SharingTable),
+ Goals, !SharingAs, !DeadCellTable)
+ ;
+ GoalExpr = call(PredId, ProcId, ActualVars, _, _, _),
+ lookup_sharing_and_comb(ModuleInfo, ProcInfo, SharingTable,
+ PredId, ProcId, ActualVars, !SharingAs)
+ ;
+ GoalExpr = generic_call(_GenDetails, _, _, _),
+ goal_info_get_context(GoalInfo, Context),
+ context_to_string(Context, ContextString),
+ !:SharingAs = sharing_as_top_sharing_accumulate(
+ "generic call (" ++ ContextString ++ ")", !.SharingAs)
+ ;
+ GoalExpr = unify(_, _, _, Unification, _),
+ unification_verify_reuse(ModuleInfo, ProcInfo, GoalInfo,
+ Unification, program_point_init(GoalInfo), !.SharingAs,
+ !DeadCellTable),
+ !:SharingAs = add_unify_sharing(ModuleInfo, ProcInfo, Unification,
+ GoalInfo, !.SharingAs)
+ ;
+ GoalExpr = disj(Goals),
+ determine_dead_deconstructions_2_disj(ModuleInfo, ProcInfo,
+ SharingTable, Goals, !SharingAs, !DeadCellTable)
+ ;
+ GoalExpr = switch(_, _, Cases),
+ determine_dead_deconstructions_2_disj(ModuleInfo, ProcInfo,
+ SharingTable, list.map(case_get_goal, Cases), !SharingAs,
+ !DeadCellTable)
+ ;
+ GoalExpr = not(_Goal)
+ ;
+ GoalExpr = scope(_, SubGoal),
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo,
+ SharingTable, SubGoal, !SharingAs, !DeadCellTable)
+ ;
+ GoalExpr = if_then_else(_, IfGoal, ThenGoal, ElseGoal),
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo, SharingTable,
+ IfGoal, !.SharingAs, IfSharingAs, !DeadCellTable),
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo, SharingTable,
+ ThenGoal, IfSharingAs, ThenSharingAs, !DeadCellTable),
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo, SharingTable,
+ ElseGoal, !.SharingAs, ElseSharingAs, !DeadCellTable),
+ !:SharingAs = sharing_as_least_upper_bound(ModuleInfo, ProcInfo,
+ ThenSharingAs, ElseSharingAs)
+ ;
+ GoalExpr = foreign_proc(_Attrs, _ForeignPredId, _ForeignProcId,
+ _ForeignArgs, _, _),
+ % XXX User annotated structure sharing information is not yet
+ % supported.
+ goal_info_get_context(GoalInfo, Context),
+ context_to_string(Context, ContextString),
+ !:SharingAs = sharing_as_top_sharing_accumulate(
+ "foreign_proc not handled yet (" ++ ContextString ++ ")",
+ !.SharingAs)
+ ;
+ GoalExpr = shorthand(_),
+ unexpected(detect_garbage.this_file,
+ "determine_dead_deconstructions_2: shorthand goal.")
+ ).
+
+:- pred determine_dead_deconstructions_2_disj(module_info::in,
+ proc_info::in, sharing_as_table::in, list(hlds_goal)::in,
+ sharing_as::in, sharing_as::out, dead_cell_table::in,
+ dead_cell_table::out) is det.
+
+determine_dead_deconstructions_2_disj(ModuleInfo, ProcInfo,
+ SharingTable, Goals, !SharingAs, !DeadCellTable) :-
+ list.foldl2(determine_dead_deconstructions_2_disj_goal(ModuleInfo,
+ ProcInfo, SharingTable, !.SharingAs), Goals, !SharingAs,
+ !DeadCellTable).
+
+:- pred determine_dead_deconstructions_2_disj_goal(module_info::in,
+ proc_info::in, sharing_as_table::in, sharing_as::in, hlds_goal::in,
+ sharing_as::in, sharing_as::out, dead_cell_table::in,
+ dead_cell_table::out) is det.
+
+determine_dead_deconstructions_2_disj_goal(ModuleInfo, ProcInfo,
+ SharingTable, SharingBeforeDisj, Goal, !SharingAs,
+ !DeadCellTable) :-
+ determine_dead_deconstructions_2(ModuleInfo, ProcInfo, SharingTable,
+ Goal, SharingBeforeDisj, GoalSharing, !DeadCellTable),
+ !:SharingAs = sharing_as_least_upper_bound(ModuleInfo, ProcInfo,
+ !.SharingAs, GoalSharing).
+
+
+ % Verify whether the unification is a deconstruction in which the
+ % deconstructed data structure becomes garbage (under some reuse
+ % conditions).
+ %
+ % XXX Different implementation from the reuse-branch implementation.
+ %
+:- pred unification_verify_reuse(module_info::in, proc_info::in,
+ hlds_goal_info::in, unification::in, program_point::in,
+ sharing_as::in, dead_cell_table::in, dead_cell_table::out) is det.
+
+unification_verify_reuse(ModuleInfo, ProcInfo, GoalInfo, Unification,
+ PP, Sharing, !DeadCellTable):-
+ (
+ Unification = deconstruct(Var, ConsId, _, _, _, _),
+ LFU = goal_info_get_lfu(GoalInfo),
+ LBU = goal_info_get_lbu(GoalInfo),
+ (
+ % Reuse is only relevant for real constructors, with
+ % arity different from 0.
+ ConsId = cons(_, Arity),
+ Arity \= 0,
+
+ % Check if the top cel datastructure of Var is not live.
+ % If Sharing is top, then everything should automatically
+ % be considered live, hence no reuse possible.
+ \+ sharing_as_is_top(Sharing),
+
+ % Check the live set of data structures at this program point.
+ set.union(LFU, LBU, LU),
+ LU_data = set.to_sorted_list(set.map(datastruct_init, LU)),
+ LiveData = list.condense(
+ list.map(
+ extend_datastruct(ModuleInfo, ProcInfo, Sharing),
+ LU_data)),
+ \+ var_is_live(Var, LiveData)
+ ->
+ % If all the above conditions are met, then the top
+ % cell data structure based on Var is dead right after
+ % this deconstruction, hence, may be involved with
+ % structure reuse.
+ NewCondition = reuse_condition_init(ModuleInfo,
+ ProcInfo, Var, LFU, LBU, Sharing),
+ dead_cell_table_set(PP, NewCondition, !DeadCellTable)
+ ;
+ true
+ )
+ ;
+ Unification = construct(_, _, _, _, _, _, _)
+ ;
+ Unification = assign(_, _)
+ ;
+ Unification = simple_test(_, _)
+ ;
+ Unification = complicated_unify(_, _, _)
+ ).
+
+:- pred var_is_live(prog_var::in, list(datastruct)::in) is semidet.
+
+var_is_live(Var, LiveData) :-
+ list.member(datastruct_init(Var), LiveData).
+
+:- pred lookup_sharing_and_comb(module_info::in, proc_info::in,
+ sharing_as_table::in, pred_id::in, proc_id::in, list(prog_var)::in,
+ sharing_as::in, sharing_as::out) is det.
+lookup_sharing_and_comb(ModuleInfo, ProcInfo, SharingTable, PredId, ProcId,
+ ActualVars, !Sharing):-
+ PPId = proc(PredId, ProcId),
+
+ lookup_sharing_or_predict(ModuleInfo, SharingTable, PPId, FormalSharing),
+
+ proc_info_get_vartypes(ProcInfo, VarTypes),
+ list.map(map.lookup(VarTypes), ActualVars, ActualTypes),
+
+ % XXX To be checked!
+ ActualTVarset = varset.init,
+ sharing_as_rename_using_module_info(ModuleInfo, PPId,
+ ActualVars, ActualTypes, ActualTVarset, FormalSharing,
+ ActualSharing),
+
+ !:Sharing = sharing_as_comb(ModuleInfo, ProcInfo,
+ ActualSharing, !.Sharing).
+
+
+%-----------------------------------------------------------------------------%
+:- func this_file = string.
+
+this_file = "structure_sharing.direct.detect_garbage.m".
+
+
+:- end_module transform_hlds.ctgc.structure_reuse.direct.detect_garbage.
Index: compiler/structure_reuse.direct.m
===================================================================
RCS file: compiler/structure_reuse.direct.m
diff -N compiler/structure_reuse.direct.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/structure_reuse.direct.m 27 Apr 2006 09:30:41 -0000
@@ -0,0 +1,328 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: structure_reuse.direct.m
+% Main authors: nancy
+%
+% Procedures and data related to the detection of so called direct reuses
+% within the CTGC system. A "direct reuse" is a combination of the location of
+% a deconstruction unification (where a datastructure may become garbage under
+% certain conditions) and a set of locations of construction unifications where
+% the garbage datastructure can be reused locally.
+%
+% Direct reuse analysis requires two steps:
+% - detecting where datastructures may become garbage;
+% - and finding where these garbage datastructures can be reused.
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.structure_reuse.direct.
+
+:- interface.
+
+:- import_module hlds.hlds_module.
+:- import_module transform_hlds.ctgc.structure_reuse.domain.
+:- import_module transform_hlds.ctgc.structure_sharing.domain.
+
+:- import_module io.
+
+:- pred direct_reuse_pass(sharing_as_table::in, module_info::in,
+ module_info::out, reuse_as_table::in, reuse_as_table::out,
+ io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module hlds.hlds_goal.
+:- import_module hlds.hlds_pred.
+:- import_module hlds.passes_aux.
+:- import_module libs.compiler_util.
+:- import_module libs.globals.
+:- import_module libs.options.
+:- import_module parse_tree.error_util.
+:- import_module parse_tree.prog_data.
+:- import_module parse_tree.prog_out.
+:- import_module transform_hlds.ctgc.datastruct.
+:- import_module transform_hlds.ctgc.structure_reuse.direct.choose_reuse.
+:- import_module transform_hlds.ctgc.structure_reuse.direct.detect_garbage.
+:- import_module transform_hlds.ctgc.util.
+
+:- import_module bool.
+:- import_module int.
+:- import_module list.
+:- import_module map.
+:- import_module set.
+:- import_module std_util.
+:- import_module string.
+:- import_module term.
+:- import_module varset.
+
+:- include_module transform_hlds.ctgc.structure_reuse.direct.detect_garbage.
+:- include_module transform_hlds.ctgc.structure_reuse.direct.choose_reuse.
+
+ % The strategy for determining the reuse possibilities, i.e., either
+ % reuse is only allowed between terms that have exactly the same cons_id,
+ % or reuse is also allowed between terms that have different cons_id, yet
+ % where the difference in arity is not bigger than a given threshold.
+ %
+:- type strategy
+ ---> same_cons_id
+ ; within_n_cells_difference(int).
+
+ % Determine the strategy that was set by the user.
+ %
+:- pred get_strategy(strategy::out, module_info::in, module_info::out,
+ io::di, io::uo) is det.
+
+get_strategy(Strategy, !ModuleInfo, !IO):-
+ io_lookup_string_option(structure_reuse_constraint, ConstraintStr, !IO),
+ (
+ ConstraintStr = "same_cons_id"
+ ->
+ Strategy = same_cons_id
+ ;
+ ConstraintStr = "within_n_cells_difference"
+ ->
+ io_lookup_int_option(structure_reuse_constraint_arg, NCells, !IO),
+ Strategy = within_n_cells_difference(NCells)
+ ;
+ Strategy = same_cons_id,
+ Pieces = [words("error: Invalid argument to "),
+ words("`--structure-reuse-constraint.'")],
+ write_error_pieces_plain(Pieces, !IO),
+ module_info_incr_errors(!ModuleInfo)
+ ).
+
+direct_reuse_pass(SharingTable, !ModuleInfo, !ReuseTable, !IO):-
+ % Determine the reuse strategy:
+ get_strategy(Strategy, !ModuleInfo, !IO),
+
+ % Gather the pred-ids of the preds that need to be analysed.
+ module_info_predids(!.ModuleInfo, AllPredIds),
+ list.filter(pred_requires_analysis(!.ModuleInfo), AllPredIds,
+ ToBeAnalysedPredIds),
+
+ % Analyse and annotate each of the predicates.
+ list.foldl3(direct_reuse_process_pred(Strategy, SharingTable),
+ ToBeAnalysedPredIds, !ModuleInfo, !ReuseTable, !IO).
+
+:- pred direct_reuse_process_pred(strategy::in, sharing_as_table::in,
+ pred_id::in, module_info::in, module_info::out, reuse_as_table::in,
+ reuse_as_table::out, io::di, io::uo) is det.
+
+direct_reuse_process_pred(Strategy, SharingTable, PredId, !ModuleInfo,
+ !ReuseTable, !IO):-
+ module_info_pred_info(!.ModuleInfo, PredId, PredInfo0),
+ list.foldl3(direct_reuse_process_proc(Strategy, SharingTable, PredId),
+ pred_info_non_imported_procids(PredInfo0), !ModuleInfo,
+ !ReuseTable, !IO).
+
+:- pred direct_reuse_process_proc(strategy::in, sharing_as_table::in,
+ pred_id::in, proc_id::in, module_info::in, module_info::out,
+ reuse_as_table::in, reuse_as_table::out, io::di, io::uo) is det.
+
+direct_reuse_process_proc(Strategy, SharingTable, PredId, ProcId,
+ !ModuleInfo, !ReuseTable, !IO) :-
+ module_info_preds(!.ModuleInfo, Preds0),
+ map.lookup(Preds0, PredId, Pred0),
+ pred_info_get_procedures(Pred0, Procs0),
+ map.lookup(Procs0, ProcId, Proc0),
+
+ direct_reuse_process_procedure(Strategy, SharingTable, PredId, ProcId,
+ !.ModuleInfo, Proc0, Proc, ReuseAs, !IO),
+ reuse_as_table_set(proc(PredId, ProcId), ReuseAs, !ReuseTable),
+
+ map.det_update(Procs0, ProcId, Proc, Procs),
+ pred_info_set_procedures(Procs, Pred0, Pred),
+ map.det_update(Preds0, PredId, Pred, Preds),
+ module_info_set_preds(Preds, !ModuleInfo).
+
+ % Process one individual procedure.
+ %
+:- pred direct_reuse_process_procedure(strategy::in, sharing_as_table::in,
+ pred_id::in, proc_id::in, module_info::in, proc_info::in, proc_info::out,
+ reuse_as::out, io::di, io::uo) is det.
+
+direct_reuse_process_procedure(Strategy, SharingTable, PredId, ProcId,
+ ModuleInfo, !ProcInfo, ReuseAs, !IO):-
+ io_lookup_bool_option(very_verbose, VeryVerbose, !IO),
+
+ write_proc_progress_message("% Direct reuse analysis of ",
+ PredId, ProcId, ModuleInfo, !IO),
+
+ proc_info_get_goal(!.ProcInfo, Goal0),
+
+ % Determine the deconstructions in which data may potentially become
+ % garbage.
+ determine_dead_deconstructions(ModuleInfo, !.ProcInfo, SharingTable,
+ Goal0, DeadCellTable),
+ dead_cell_table_maybe_dump(VeryVerbose, DeadCellTable, !IO),
+
+ % Determine how the detected dead datastructures can be reused.
+ % This annotates the goal with potential reuses.
+ determine_reuse(Strategy, ModuleInfo, !.ProcInfo, DeadCellTable,
+ Goal0, Goal, ReuseAs, !IO),
+
+ proc_info_set_goal(Goal, !ProcInfo),
+ maybe_write_string(VeryVerbose, "% reuse analysis done.\n", !IO).
+
+
+%-----------------------------------------------------------------------------%
+% We use the type dead_cell_table to collect all deconstructions that possibly
+% leave garbage behind.
+%
+%
+ % To record the place at which a data structure possible becomes garbage,
+ % we use the notion of a program point. A program point is unique using
+ % the combination of the context of the goal, and its goal_path.
+ %
+:- type program_point
+ ---> pp(
+ pp_context :: term.context,
+ pp_path :: goal_path
+ ).
+
+ % A dead_cell_table maps program points onto reuse conditions.
+ %
+:- type dead_cell_table == map(program_point, reuse_condition).
+
+
+ % Compute the program point of a given goal.
+ %
+:- func program_point_init(hlds_goal_info) = program_point.
+
+ % Dump the information contained in a program point.
+ %
+:- pred dump_program_point(program_point::in, io::di, io::uo) is det.
+
+ % Initialise a dead_cell_table.
+ %
+:- func dead_cell_table_init = dead_cell_table.
+
+ % Check whether the table is empty.
+ %
+:- pred dead_cell_table_is_empty(dead_cell_table::in) is semidet.
+
+ % Succeeds if the given program point is listed in the table. Return
+ % the associated reuse_condition.
+ %
+:- func dead_cell_table_search(program_point, dead_cell_table)
+ = reuse_condition is semidet.
+
+ % Add a program point and its associated reuse_condition to the table.
+ %
+:- pred dead_cell_table_set(program_point::in, reuse_condition::in,
+ dead_cell_table::in, dead_cell_table::out) is det.
+
+ % Remove a program point from the table.
+ %
+:- pred dead_cell_table_remove(program_point::in,
+ dead_cell_table::in, dead_cell_table::out) is det.
+
+ % Remove all program points from the table for which the reuse_conditions
+ % are "conditional".
+ %
+:- pred dead_cell_table_remove_conditionals(dead_cell_table::in,
+ dead_cell_table::out) is det.
+
+ % Dump the contents of the table.
+ %
+:- pred dead_cell_table_maybe_dump(bool::in, dead_cell_table::in,
+ io__state::di, io__state::uo) is det.
+
+program_point_init(Info) = PP :-
+ goal_info_get_context(Info, Context),
+ goal_info_get_goal_path(Info, GoalPath),
+ PP = pp(Context, GoalPath).
+
+dump_program_point(pp(Context, GoalPath), !IO):-
+ % context
+ prog_out.write_context(Context, !IO),
+ io.write_string("--", !IO),
+ % goal path
+ list.foldl(dump_goal_path_step, GoalPath, !IO).
+
+:- pred dump_goal_path_step(goal_path_step::in, io::di, io::uo) is det.
+
+dump_goal_path_step(conj(N)) -->
+ io.write_char('c'),
+ io.write_int(N).
+dump_goal_path_step(disj(N)) -->
+ io.write_char('d'),
+ io.write_int(N).
+dump_goal_path_step(switch(N, _)) -->
+ io.write_char('s'),
+ io.write_int(N).
+dump_goal_path_step(ite_cond) -->
+ io.write_char('c').
+dump_goal_path_step(ite_then) -->
+ io.write_char('t').
+dump_goal_path_step(ite_else) -->
+ io.write_char('e').
+dump_goal_path_step(neg) -->
+ io.write_char('n').
+dump_goal_path_step(scope(_)) -->
+ io.write_char('q').
+dump_goal_path_step(first) -->
+ io.write_char('f').
+dump_goal_path_step(later) -->
+ io.write_char('l').
+
+dead_cell_table_init = map.init.
+dead_cell_table_is_empty(Table) :- map.is_empty(Table).
+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) :-
+ (
+ reuse_condition_is_conditional(C)
+ ->
+ true
+ ;
+ dead_cell_table_set(PP, C, !Table)
+ ).
+
+dead_cell_table_maybe_dump(MaybeDump, Table, !IO) :-
+ (
+ MaybeDump = no
+ ;
+ MaybeDump = yes,
+ 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) :-
+ (
+ reuse_condition_is_conditional(Cond)
+ ->
+ write_string("\t\t| cond |\t", !IO)
+ ;
+ write_string("\t\t| always |\t", !IO)
+ ),
+ dump_program_point(PP, !IO),
+ write_string("\n", !IO).
+
+
+%-----------------------------------------------------------------------------%
+:- func this_file = string.
+
+this_file = "structure_sharing.direct.m".
+
+:- end_module transform_hlds.ctgc.structure_reuse.direct.
+
Index: compiler/structure_reuse.domain.m
===================================================================
RCS file: compiler/structure_reuse.domain.m
diff -N compiler/structure_reuse.domain.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/structure_reuse.domain.m 27 Apr 2006 09:30:42 -0000
@@ -0,0 +1,438 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: structure_reuse.domain.m
+% Main authors: nancy
+%
+% Definition of the abstract domain for keeping track of opportunities for
+% structure reuse.
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.structure_reuse.domain.
+
+:- interface.
+
+:- import_module hlds.hlds_module.
+:- import_module hlds.hlds_pred.
+:- import_module parse_tree.prog_data.
+:- import_module transform_hlds.ctgc.structure_sharing.domain.
+
+:- import_module map.
+:- import_module set.
+:- import_module list.
+
+:- interface.
+
+ % A reuse condition stores all the necessary information to check if
+ % a procedure call is safe w.r.t. a structure reuse opportunity within
+ % the body of the called procedure.
+ %
+:- type reuse_condition.
+:- type reuse_conditions == list(reuse_condition).
+
+ % Abstract representation for a set of reuse conditions.
+ %
+:- type reuse_as.
+
+%-----------------------------------------------------------------------------%
+% reuse_condition
+%
+
+ % reuse_condition_init(ModuleInfo, ProcInfo, DeadVar, LocalForwardUse,
+ % LocalBackwardUse, SharingAs) = NewReuseCondition.
+ %
+ % Create a reuse condition for DeadVar, knowing the set of variables in
+ % local forward and backward use, as well as the local structure sharing.
+ %
+:- func reuse_condition_init(module_info, proc_info, prog_var,
+ set(prog_var), set(prog_var), sharing_as) = reuse_condition.
+
+:- pred reuse_condition_is_conditional(reuse_condition::in) is semidet.
+
+ % Renaming operation.
+ % This operation renames all occurrences of program variables and
+ % type variables according to a program and type variable mapping.
+ %
+:- pred reuse_condition_rename(map(prog_var, prog_var)::in, tsubst::in,
+ reuse_condition::in, reuse_condition::out) is det.
+
+ % Succeeds if the first condition is subsumed by the second one, i.e.,
+ % if a procedure call verifies the second condition, then it also
+ % verifies the first condition.
+ %
+:- pred reuse_condition_subsumed_by(module_info::in, proc_info::in,
+ reuse_condition::in, reuse_condition::in) is semidet.
+
+ % Translate a reuse condition to its new environment.
+ % E.g. Consider a procedure definition: p :- ..., q, ... ,
+ % where q contains a potential reuse expressed by a condition C, then this
+ % condition needs to be translated to calls to p, such that calls to p
+ % can be checked w.r.t. reuses that are possible in q.
+ %
+ % In order to translate a condition to its new environment, the same kind
+ % of information is needed as when creating an initial condition, i.e.:
+ % set of variables in local forward and backward use, as well as the
+ % structure sharing existing at that place.
+ %
+% XXX To be implemented. Used at indirect-reuse-analysis stage.
+% :- pred reuse_condition_translate(module_info::in, proc_info::in,
+% set(prog_var)::in, set(prog_var)::in, sharing_as::in, reuse_condition::in,
+% reuse_condition::out) is det.
+
+%-----------------------------------------------------------------------------%
+% reuse_as
+%
+% XXX The implementation of this type has changed wrt. its counterpart in the
+% reuse branch (called memo_reuse). While memo_reuse's didn't always keep a
+% minimal representation, reuse_as does.
+%
+
+ % Create an initial set of reuse descriptions.
+ %
+:- func reuse_as_init = reuse_as.
+:- func reuse_as_init_with_one_condition(reuse_condition) = reuse_as.
+
+ % Succeeds if the first reuses description is subsumed by the second
+ % description, i.e., if a procedure call satisfies all the conditions
+ % expressed by the second reuses description, then it also satisfies all
+ % the conditions expressed by the first reuses description.
+ %
+:- pred reuse_as_subsumed_by(module_info::in, proc_info::in, reuse_as::in,
+ reuse_as::in) is semidet.
+
+ % Tests to see whether the reuses description describes no reuses at all,
+ % only unconditional reuses, or conditional reuses resp.
+ %
+:- pred reuse_as_no_reuses(reuse_as::in) is semidet.
+:- pred reuse_as_all_unconditional_reuses(reuse_as::in) is semidet.
+:- pred reuse_as_conditional_reuses(reuse_as::in) is semidet.
+
+ % Given a variable and type variable mapping, rename the reuses
+ % conditions accordingly.
+ %
+:- pred reuse_as_rename(map(prog_var, prog_var)::in, tsubst::in, reuse_as::in,
+ reuse_as::out) is det.
+
+ % Add a reuse condition to the reuses description. The information of
+ % module_info and proc_info are needed to verify subsumption before adding
+ % the new condition.
+ %
+:- pred reuse_as_add_condition(module_info::in, proc_info::in,
+ reuse_condition::in, reuse_as::in, reuse_as::out) is det.
+
+ % Compute the least upper bound of two reuses descriptions. Module_info
+ % and proc_info are needed for verifying subsumption.
+ %
+:- pred reuse_as_least_upper_bound(module_info::in, proc_info::in,
+ reuse_as::in, reuse_as::in, reuse_as::out) is det.
+
+% XXX TO DO!
+% :- func from_reuse_domain(reuse_domain) = reuse_as.
+% :- func to_reuse_domain(reuse_as) = reuse_domain.
+
+%-----------------------------------------------------------------------------%
+%
+% reuse_as_table
+%
+
+ % Intermediate storage of the reuse results for individual procedures.
+ %
+:- type reuse_as_table == map(pred_proc_id, reuse_as).
+
+:- func reuse_as_table_init = reuse_as_table.
+:- func reuse_as_table_search(pred_proc_id, reuse_as_table)
+ = reuse_as is semidet.
+:- pred reuse_as_table_set(pred_proc_id::in, reuse_as::in,
+ reuse_as_table::in, reuse_as_table::out) is det.
+% XXX TO DO!
+% :- func load_structure_reuse_table(module_info) = reuse_as_table.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module transform_hlds.ctgc.datastruct.
+:- import_module parse_tree.prog_ctgc.
+
+:- import_module set.
+
+:- type reuse_condition
+ ---> always
+ ; condition(
+ reuseable_nodes :: list(datastruct),
+ % Description of the datastructures pointing to the
+ % memory that can be reused within a procedure.
+ local_use_headvars :: list(datastruct),
+ % Set of (headvar-related) datastructures that are
+ % inherently live at the place where the reuse is
+ % decided.
+ local_sharing_headvars :: sharing_as
+ % Description of the (headvar-related) structure sharing
+ % that exists at the place where the reuse is decided.
+ ).
+
+:- type reuse_as
+ ---> no_reuse
+ % = fictive bottom element representing the fact that no
+ % reuse has been detected so far.
+ ; unconditional
+ % no_reuse < unconditional.
+ % = element representing the fact that all reuses detected
+ % so far are unconditional.
+ % Semantically equivalent to "conditional(Cs)" where every C in
+ % Cs is "always".
+ ; conditional(reuse_conditions).
+ % no_reuse < unconditional < conditional(List)
+ % = element representing the collection of reuse conditions
+ % collected for the reuses detected so far.
+
+%-----------------------------------------------------------------------------%
+%
+% reuse_condition.
+%
+
+reuse_condition_init(ModuleInfo, ProcInfo, DeadVar, LFU, LBU,
+ Sharing) = Condition :-
+ proc_info_get_headvars(ProcInfo, HeadVars),
+
+ % First determine the nodes to which the reuse is related.
+ % There are two cases:
+ % 1. Var is a headvar, then it is sufficient to keep the topcel of that Var
+ % as only node. HeadVar-datastructures shared with that node will still
+ % be retraceable at the moment of verifying the condition
+ % 2. Var is a local var, then we must compute all the headvar-
+ % datastructures sharing the same memory representation as the topcel of
+ % this var (note that the datastructures that share with some
+ % substructure of this var are not relevant for the nodes). All the
+ % obtained datastructures are kept as the nodes for our condition.
+ TopCel = ctgc.datastruct.datastruct_init(DeadVar),
+ (
+ list__member(DeadVar, HeadVars)
+ ->
+ Nodes = [TopCel]
+ ;
+ SharedDatastructs = extend_datastruct(ModuleInfo, ProcInfo,
+ Sharing, TopCel),
+ Nodes = datastructs_project(HeadVars, SharedDatastructs)
+ ),
+
+ % It is possible that the obtained set of nodes is empty, in that
+ % case the condition is always satisfied, independent of any calling
+ % environment.
+ (
+ Nodes = []
+ ->
+ Condition = always
+ ;
+ set__union(LFU, LBU, LU),
+ % XXX the old implementation did not bother about extending at
+ % this place, which was contrary to the theory. Check the effect
+ % of this change!
+ SharedLU = list.condense(
+ list.map(extend_datastruct(ModuleInfo, ProcInfo, Sharing),
+ list.map(datastruct_init, set.to_sorted_list(LU)))),
+ HeadVarSharedLU = datastructs_project(HeadVars, SharedLU),
+
+ structure_sharing.domain.sharing_as_project(HeadVars, Sharing,
+ HeadVarSharing),
+ Condition = condition(Nodes, HeadVarSharedLU, HeadVarSharing)
+ ).
+
+reuse_condition_is_conditional(condition(_, _, _)).
+
+reuse_condition_subsumed_by(ModuleInfo, ProcInfo, Cond1, Cond2) :-
+ (
+ Cond1 = always
+ ;
+ Cond1 = condition(Nodes1, LocalUse1, LocalSharing1),
+ Cond2 = condition(Nodes2, LocalUse2, LocalSharing2),
+ datastructs_subsumed_by_list(ModuleInfo, ProcInfo, Nodes1, Nodes2),
+ datastructs_subsumed_by_list(ModuleInfo, ProcInfo, LocalUse1,
+ LocalUse2),
+ sharing_as_is_subsumed_by(ModuleInfo,
+ ProcInfo, LocalSharing1, LocalSharing2)
+ ).
+
+:- pred reuse_condition_subsumed_by_list(module_info::in, proc_info::in,
+ reuse_condition::in, reuse_conditions::in) is semidet.
+reuse_condition_subsumed_by_list(ModuleInfo, ProcInfo, Cond, [Cond1|Rest]) :-
+ (
+ reuse_condition_subsumed_by(ModuleInfo, ProcInfo, Cond, Cond1)
+ ;
+ reuse_condition_subsumed_by_list(ModuleInfo, ProcInfo, Cond, Rest)
+ ).
+
+:- pred reuse_conditions_subsume_reuse_condition(module_info::in,
+ proc_info::in, reuse_conditions::in, reuse_condition::in) is semidet.
+reuse_conditions_subsume_reuse_condition(ModuleInfo, ProcInfo, Conds, Cond):-
+ reuse_condition_subsumed_by_list(ModuleInfo, ProcInfo, Cond, Conds).
+
+reuse_condition_rename(MapVar, TypeSubst, Condition, RenamedCondition):-
+ (
+ Condition = always,
+ RenamedCondition = always
+ ;
+ Condition = condition(DeadNodes, InUseNodes, LocalSharing),
+ RenamedDeadNodes = list.map(rename_datastruct(MapVar, TypeSubst),
+ DeadNodes),
+ RenamedInUseNodes = list.map(rename_datastruct(MapVar, TypeSubst),
+ InUseNodes),
+ sharing_as_rename(MapVar, TypeSubst, LocalSharing,
+ RenamedLocalSharing),
+ RenamedCondition = condition(RenamedDeadNodes, RenamedInUseNodes,
+ RenamedLocalSharing)
+ ).
+
+%-----------------------------------------------------------------------------%
+%
+% reuse_as
+%
+
+reuse_as_init = no_reuse.
+reuse_as_init_with_one_condition(ReuseCondition) = ReuseAs :-
+ (
+ reuse_condition_is_conditional(ReuseCondition)
+ ->
+ ReuseAs = conditional([ReuseCondition])
+ ;
+ ReuseAs = unconditional
+ ).
+
+reuse_as_subsumed_by(ModuleInfo, ProcInfo, FirstReuseAs, SecondReuseAs) :-
+ (
+ FirstReuseAs = no_reuse
+ ;
+ FirstReuseAs = unconditional,
+ SecondReuseAs = conditional(_)
+ % Every calling environment satisfies the reuse conditions as all
+ % reuse is unconditional, hence also the calling environments that
+ % satisfy the conditions expressed by SecondReuseAs.
+ ;
+ FirstReuseAs = conditional(ReuseConditionsFirst),
+ SecondReuseAs = conditional(ReuseConditionsSecond),
+ list.takewhile(reuse_conditions_subsume_reuse_condition(ModuleInfo,
+ ProcInfo, ReuseConditionsSecond), ReuseConditionsFirst, _,
+ NotSubsumed),
+ NotSubsumed = []
+ ).
+
+reuse_as_no_reuses(no_reuse).
+reuse_as_all_unconditional_reuses(unconditional).
+reuse_as_conditional_reuses(conditional(_)).
+
+reuse_as_rename(MapVar, TypeSubst, ReuseAs, RenamedReuseAs) :-
+ (
+ ReuseAs = no_reuse,
+ RenamedReuseAs = no_reuse
+ ;
+ ReuseAs = unconditional,
+ RenamedReuseAs = unconditional
+ ;
+ ReuseAs = conditional(ReuseConditions),
+ list.map(reuse_condition_rename(MapVar, TypeSubst),
+ ReuseConditions, RenamedReuseConditions),
+ RenamedReuseAs = conditional(RenamedReuseConditions)
+ ).
+
+reuse_as_add_condition(ModuleInfo, ProcInfo, Condition, !ReuseAs) :-
+ (
+ Condition = always,
+ (
+ !.ReuseAs = no_reuse
+ ->
+ !:ReuseAs = unconditional
+ ;
+ true
+ )
+ ;
+ Condition = condition(_, _, _),
+ (
+ !.ReuseAs = no_reuse,
+ !:ReuseAs = conditional([Condition])
+ ;
+ !.ReuseAs = unconditional,
+ !:ReuseAs = conditional([Condition])
+ ;
+ !.ReuseAs = conditional(Conditions),
+ reuse_conditions_add_condition(ModuleInfo, ProcInfo,
+ Condition, Conditions, NewConditions),
+ !:ReuseAs = conditional(NewConditions)
+ )
+ ).
+
+:- pred reuse_conditions_add_condition(module_info::in, proc_info::in,
+ reuse_condition::in, reuse_conditions::in, reuse_conditions::out) is det.
+reuse_conditions_add_condition(ModuleInfo, ProcInfo, Condition, !Conds):-
+ (
+ reuse_condition_subsumed_by_list(ModuleInfo, ProcInfo,
+ Condition, !.Conds)
+ ->
+ true
+ ;
+ !:Conds = [Condition|!.Conds]
+ ).
+
+:- pred reuse_conditions_add_conditions(module_info::in, proc_info::in,
+ reuse_conditions::in, reuse_conditions::in, reuse_conditions::out) is det.
+reuse_conditions_add_conditions(ModuleInfo, ProcInfo, NewConds, !Conds):-
+ (
+ NewConds = [Cond|RemainingConds],
+ reuse_conditions_add_condition(ModuleInfo, ProcInfo, Cond, !Conds),
+ reuse_conditions_add_conditions(ModuleInfo, ProcInfo,
+ RemainingConds, !Conds)
+ ;
+ NewConds = []
+ ).
+
+reuse_as_least_upper_bound(ModuleInfo, ProcInfo, NewReuseAs, !ReuseAs) :-
+ (
+ NewReuseAs = no_reuse
+ ;
+ NewReuseAs = unconditional,
+ (
+ !.ReuseAs = no_reuse
+ ->
+ !:ReuseAs = unconditional
+ ;
+ true
+ )
+ ;
+ NewReuseAs = conditional(NewConditions),
+ (
+ !.ReuseAs = no_reuse,
+ !:ReuseAs = NewReuseAs
+ ;
+ !.ReuseAs = unconditional,
+ !:ReuseAs = NewReuseAs
+ ;
+ !.ReuseAs = conditional(Conditions),
+ reuse_conditions_add_conditions(ModuleInfo, ProcInfo,
+ NewConditions, Conditions, AllConditions),
+ !:ReuseAs = conditional(AllConditions)
+ )
+
+ ).
+
+%-----------------------------------------------------------------------------%
+%
+% reuse_as_table
+%
+
+reuse_as_table_init = map.init.
+reuse_as_table_search(PPId, Table) = Table ^ elem(PPId).
+reuse_as_table_set(PPId, ReuseAs, !Table) :-
+ !:Table = !.Table ^ elem(PPId) := ReuseAs.
+
+%-----------------------------------------------------------------------------%
+:- func this_file = string.
+this_file = "structure_reuse.domain.m".
+
+:- end_module transform_hlds.ctgc.structure_reuse.domain.
+
+
Index: compiler/structure_reuse.lbu.m
===================================================================
RCS file: compiler/structure_reuse.lbu.m
diff -N compiler/structure_reuse.lbu.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/structure_reuse.lbu.m 27 Apr 2006 09:30:42 -0000
@@ -0,0 +1,230 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: structure_reuse.lbu.m
+% Main authors: nancy
+%
+% Implementation of the process of annotating each program point within
+% a procedure with local backward use information.
+%
+% Each program point (goal within a procedure definition) is annotated with a
+% set of variables that are in Local Backward Use (LBU). A variable is said to
+% be in LBU if it may be accessed upon backtracking. This information is
+% computed based on the backtrack-vars (i.e. the input variables of the
+% alternative goals of a disjunction), and forward use information.
+%
+% The implementation is based on the theory detailed in Nancy Mazur's PhD
+% ("Instantiation 2", cf. Section 7.4).
+% XXX Note: slight variations as to the treatment of disjunctions,
+% switches and if-then-elses.
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.structure_reuse.lbu.
+
+:- interface.
+
+:- import_module hlds.hlds_module.
+:- import_module hlds.hlds_pred.
+
+:- pred backward_use_information(module_info::in, proc_info::in,
+ proc_info::out) is det.
+
+:- implementation.
+
+:- import_module hlds.hlds_goal.
+:- import_module hlds.hlds_llds.
+:- import_module libs.compiler_util.
+:- import_module parse_tree.prog_data.
+
+:- import_module list.
+:- import_module pair.
+:- import_module set.
+:- import_module string.
+
+backward_use_information(ModuleInfo, !ProcInfo):-
+ proc_info_get_goal(!.ProcInfo, Goal0),
+
+ % Before the first goal, the set of variables in LBU is empty.
+ LBU0 = set.init,
+ backward_use_in_goal(ModuleInfo, !.ProcInfo, Goal0, Goal, LBU0, _LBU),
+
+ proc_info_set_goal(Goal, !ProcInfo).
+
+:- pred backward_use_in_goal(module_info::in, proc_info::in,
+ hlds_goal::in, hlds_goal::out, set(prog_var)::in, set(prog_var)::out)
+ is det.
+
+backward_use_in_goal(ModuleInfo, ProcInfo, !TopGoal, !LBU) :-
+ !.TopGoal = Expr0 - Info0,
+
+ % Add resume_vars to the LBU-set.
+ set.union(get_backtrack_vars(Info0), !LBU),
+
+ % Handle each goal type separately:
+ (
+ Expr0 = unify(_, _, _, _, _),
+ Expr = Expr0
+ ;
+ Expr0 = call(_,_, _, _, _, _),
+ goal_info_get_determinism(Info0, Det),
+ (
+ determinism_is_nondet(Det)
+ ->
+ % Implementation of Instantiation 2 from Nancy's Phd.
+ % In this instantation, a non deterministic procedure
+ % call only adds its LFU-variables to the current set
+ % of lbu-variables. Cf. Phd Nancy Mazur.
+
+ goal_info_get_pre_births(Info0, PreBirths),
+ goal_info_get_post_births(Info0, PostBirths),
+ !:LBU = set.union_list([goal_info_get_lfu(Info0),
+ PreBirths, PostBirths, !.LBU])
+ ;
+ true
+ ),
+ Expr = Expr0
+ ;
+ Expr0 = generic_call(_, _, _, _),
+ Expr = Expr0
+ ;
+ % to !LBU.
+ Expr0 = foreign_proc(_, _, _, _, _, _),
+ Expr = Expr0
+ ;
+ Expr0 = conj(ConjType, Goals0),
+ backward_use_in_conj(ModuleInfo, ProcInfo,
+ Goals0, Goals, !LBU),
+ Expr = conj(ConjType, Goals)
+ ;
+ Expr0 = disj(Goals0),
+ backward_use_in_disj(ModuleInfo, ProcInfo, Goals0, Goals, !LBU),
+ Expr = disj(Goals)
+ ;
+ Expr0 = switch(A, B, Cases0),
+ backward_use_in_cases(ModuleInfo, ProcInfo, Cases0, Cases, !LBU),
+ Expr = switch(A, B, Cases)
+ ;
+ Expr0 = not(Goal0),
+ % handled as: if(Goal0) then fail else true
+ LBU0 = !.LBU,
+ backward_use_in_goal(ModuleInfo, ProcInfo, Goal0, Goal, !.LBU, _),
+ % A not does not introduce any choice-points! Hence the
+ % not itself is deterministic, and no new variables in LBU
+ % are introduced into the resulting LBU-set.
+ !:LBU = LBU0,
+ Expr = not(Goal)
+ ;
+ Expr0 = scope(Reason, SomeGoal0),
+ backward_use_in_goal(ModuleInfo, ProcInfo, SomeGoal0, SomeGoal, !LBU),
+ Expr = scope(Reason, SomeGoal)
+ ;
+ % XXX The implementation for if-then-else is different from the theory
+ % in the thesis. We can obtain more precision when the Condition-goal
+ % is deterministic, which means that the Then-goal can be analysed with
+ % the initial LBU-set (instead of the set obtained after the analysis
+ % of the Condition-goal).
+ Expr0 = if_then_else(Vars, Cond0, Then0, Else0),
+ LBU0 = !.LBU,
+
+ % Annotate Cond-goal.
+ backward_use_in_goal(ModuleInfo, ProcInfo, Cond0, Cond, LBU0, _),
+
+ % Annotate Then-goal.
+ % When annotating the then-part, the lbu used for it should not
+ % contain the resume-vars due to the else part.
+ % trick: to calculate inital LBU for the Then-goal, we set the
+ % resume-point of the condition to no_resume_point.
+ Cond0 = CondGoal0 - CondInfo0,
+ goal_info_set_resume_point(no_resume_point, CondInfo0, InfoTmp),
+ CondTmp = CondGoal0 - InfoTmp,
+ backward_use_in_goal(ModuleInfo, ProcInfo, CondTmp, _, LBU0, LBU0T),
+ backward_use_in_goal(ModuleInfo, ProcInfo, Then0, Then, LBU0T, LBUT),
+
+ % Annotate Else-goal.
+ backward_use_in_goal(ModuleInfo, ProcInfo, Else0, Else,
+ LBU0, LBUE),
+ set.union(LBUT, LBUE, !:LBU),
+ Expr = if_then_else(Vars, Cond, Then, Else)
+ ;
+ Expr0 = shorthand(_),
+ unexpected(this_file, "backward_use_in_goal: shorthand goal.")
+ ),
+ goal_info_set_lbu(!.LBU, Info0, Info),
+ !:TopGoal = Expr - Info.
+
+
+:- func get_backtrack_vars(hlds_goal_info) = set(prog_var).
+get_backtrack_vars(Info) = Vars :-
+ goal_info_get_resume_point(Info, ResPoint),
+ (
+ ResPoint = resume_point(ResVars, _),
+ Vars = ResVars
+ ;
+ ResPoint = no_resume_point,
+ Vars = set.init
+ ).
+
+:- pred determinism_is_nondet(prog_data__determinism::in) is semidet.
+determinism_is_nondet(nondet).
+determinism_is_nondet(multidet).
+determinism_is_nondet(cc_nondet).
+determinism_is_nondet(cc_multidet).
+
+:- pred backward_use_in_conj(module_info::in, proc_info::in,
+ list(hlds_goal)::in, list(hlds_goal)::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+backward_use_in_conj(ModuleInfo, ProcInfo, !Goals, !LBU) :-
+ list.map_foldl(backward_use_in_goal(ModuleInfo, ProcInfo), !Goals, !LBU).
+
+:- pred backward_use_in_cases(module_info::in, proc_info::in,
+ list(case)::in, list(case)::out, set(prog_var)::in, set(prog_var)::out)
+ is det.
+
+backward_use_in_cases(ModuleInfo, ProcInfo, !Cases, !LBU) :-
+ % Every case is analysed with the same initial set of LBU-vars.
+ LBU0 = !.LBU,
+ list.map_foldl(backward_use_in_case(LBU0, ModuleInfo, ProcInfo),
+ !Cases, !LBU).
+
+:- pred backward_use_in_case(set(prog_var)::in, module_info::in,
+ proc_info::in, case::in, case::out, set(prog_var)::in, set(prog_var)::out)
+ is det.
+
+backward_use_in_case(LBU0, ModuleInfo, ProcInfo, !Case, !LBU):-
+ !.Case = case(Cons, Goal0),
+ backward_use_in_goal(ModuleInfo, ProcInfo, Goal0, Goal, LBU0, NewLBU),
+ !:Case = case(Cons, Goal),
+ set.union(NewLBU, !LBU).
+
+:- pred backward_use_in_disj(module_info::in, proc_info::in,
+ list(hlds_goal)::in, list(hlds_goal)::out,
+ set(prog_var)::in, set(prog_var)::out) is det.
+
+backward_use_in_disj(ModuleInfo, ProcInfo, !Goals, !LBU) :-
+ % Every disj-goal is analysed with the same initial set of LBU-vars.
+ LBU0 = !.LBU,
+ list.map_foldl(backward_use_in_disj_goal(LBU0, ModuleInfo, ProcInfo),
+ !Goals, !LBU).
+
+:- pred backward_use_in_disj_goal(set(prog_var)::in, module_info::in,
+ proc_info::in, hlds_goal::in, hlds_goal::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+backward_use_in_disj_goal(LBU0, ModuleInfo, ProcInfo, !Goal, !LBU) :-
+ backward_use_in_goal(ModuleInfo, ProcInfo, !Goal, LBU0, NewLBU),
+ set.union(NewLBU, !LBU).
+
+%-----------------------------------------------------------------------------%
+
+:- func this_file = string.
+this_file = "structure_reuse.lbu.m".
+
+:- end_module transform_hlds.ctgc.structure_reuse.lbu.
Index: compiler/structure_reuse.lfu.m
===================================================================
RCS file: compiler/structure_reuse.lfu.m
diff -N compiler/structure_reuse.lfu.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/structure_reuse.lfu.m 27 Apr 2006 09:30:43 -0000
@@ -0,0 +1,196 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2006 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: structure_reuse.lfu.m
+% Main authors: nancy
+%
+% Implementation of the process of annotating each program point within
+% a procedure with local forward use information.
+%
+% At a program point (a goal), a variable is called in local forward use iff
+% * it was already instantiated before the goal
+% * and it is (syntactically) used in the goals following the current goal in
+% forward execution.
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.structure_reuse.lfu.
+
+:- interface.
+
+:- import_module hlds.hlds_pred.
+
+:- pred forward_use_information(proc_info::in, proc_info::out) is det.
+
+:- implementation.
+
+:- import_module hlds.hlds_goal.
+:- import_module hlds.hlds_llds.
+:- import_module hlds.hlds_pred.
+:- import_module libs.compiler_util.
+:- import_module parse_tree.prog_data.
+
+:- import_module list.
+:- import_module set.
+:- import_module pair.
+:- import_module string.
+
+forward_use_information(!ProcInfo) :-
+ proc_info_get_goal(!.ProcInfo, Goal0),
+
+ % Set of variables initially instantiated.
+ proc_info_get_liveness_info(!.ProcInfo, InstantiatedVars0),
+ % Set of variables initially "dead" = instantiated variables that
+ % syntactically do not occur in the remainder of the goal.
+ set.init(DeadVars0),
+
+ forward_use_in_goal(Goal0, Goal, InstantiatedVars0, _InstantiatedVars,
+ DeadVars0, _DeadVars),
+
+ proc_info_set_goal(Goal, !ProcInfo).
+
+
+:- pred forward_use_in_goal(hlds_goal::in, hlds_goal::out, set(prog_var)::in,
+ set(prog_var)::out, set(prog_var)::in, set(prog_var)::out) is det.
+
+forward_use_in_goal(!Goal, !InstantiatedVars, !DeadVars) :-
+ (
+ !.Goal = GoalExpr0 - GoalInfo0,
+ goal_is_atomic(GoalExpr0)
+ ->
+ InstantiatedVars0 = !.InstantiatedVars,
+ compute_instantiated_and_dead_vars(GoalInfo0, !InstantiatedVars,
+ !DeadVars),
+ set.difference(InstantiatedVars0, !.DeadVars, LFU),
+ goal_info_set_lfu(LFU, GoalInfo0, GoalInfo),
+ !:Goal = GoalExpr0 - GoalInfo
+ ;
+ forward_use_in_composite_goal(!Goal, !InstantiatedVars, !DeadVars)
+ ).
+
+
+:- pred compute_instantiated_and_dead_vars(hlds_goal_info::in,
+ set(prog_var)::in, set(prog_var)::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+compute_instantiated_and_dead_vars(Info, !Inst, !Dead) :-
+ % Inst = Inst0 + birth-set
+ % Dead = Dead0 + death-set
+ goal_info_get_pre_births(Info, PreBirths),
+ goal_info_get_post_births(Info, PostBirths),
+ goal_info_get_post_deaths(Info, PostDeaths),
+ goal_info_get_pre_deaths(Info, PreDeaths),
+ !:Inst = set.union_list([PreBirths, PostBirths, !.Inst]),
+ !:Dead = set.union_list([PreDeaths, PostDeaths, !.Dead]).
+
+:- pred forward_use_in_composite_goal(hlds_goal::in, hlds_goal::out,
+ set(prog_var)::in, set(prog_var)::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+forward_use_in_composite_goal(!Goal, !InstantiatedVars, !DeadVars) :-
+ !.Goal = GoalExpr0 - GoalInfo0,
+ InstantiadedBefore = !.InstantiatedVars,
+
+ (
+ GoalExpr0 = conj(A,Goals0)
+ ->
+ forward_use_in_conj(Goals0, Goals, !InstantiatedVars, !DeadVars),
+ GoalExpr = conj(A,Goals)
+ ;
+ GoalExpr0 = switch(A, B, Cases0)
+ ->
+ forward_use_in_cases(Cases0, Cases, !InstantiatedVars, !DeadVars),
+ GoalExpr = switch(A, B, Cases)
+ ;
+ GoalExpr0 = disj(Disj0)
+ ->
+ forward_use_in_disj(Disj0, Disj, !InstantiatedVars, !DeadVars),
+ GoalExpr = disj(Disj)
+ ;
+ GoalExpr0 = not(Goal0)
+ ->
+ forward_use_in_goal(Goal0, Goal, !InstantiatedVars, !DeadVars),
+ GoalExpr = not(Goal)
+ ;
+ GoalExpr0 = scope(A, Goal0)
+ ->
+ forward_use_in_goal(Goal0, Goal, !InstantiatedVars, !DeadVars),
+ GoalExpr = scope(A, Goal)
+ ;
+ GoalExpr0 = if_then_else(V, Cond0, Then0, Else0)
+ ->
+ Inst0 = !.InstantiatedVars,
+ Dead0 = !.DeadVars,
+ forward_use_in_goal(Cond0, Cond, !InstantiatedVars, !DeadVars),
+ forward_use_in_goal(Then0, Then, !InstantiatedVars, !DeadVars),
+ forward_use_in_goal(Else0, Else, Inst0, Inst1, Dead0, Dead1),
+ set.union(Inst1, !InstantiatedVars),
+ set.union(Dead1, !DeadVars),
+ GoalExpr = if_then_else(V, Cond, Then, Else)
+ ;
+ unexpected(this_file,
+ "Atomic goal in forward_use_in_composite_goal.")
+ ),
+ set.difference(InstantiadedBefore, !.DeadVars, LFU),
+ goal_info_set_lfu(LFU, GoalInfo0, GoalInfo),
+ !:Goal = GoalExpr - GoalInfo.
+
+:- pred forward_use_in_conj(list(hlds_goal)::in, list(hlds_goal)::out,
+ set(prog_var)::in, set(prog_var)::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+forward_use_in_conj(!Goals, !InstantiatedVars, !DeadVars) :-
+ list.map_foldl2(forward_use_in_goal, !Goals, !InstantiatedVars,
+ !DeadVars).
+
+:- pred forward_use_in_cases(list(case)::in, list(case)::out,
+ set(prog_var)::in, set(prog_var)::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+forward_use_in_cases(!Cases, !InstantiatedVars, !DeadVars) :-
+ Inst0 = !.InstantiatedVars,
+ Dead0 = !.DeadVars,
+ list.map_foldl2(forward_use_in_case(Inst0, Dead0),
+ !Cases, !InstantiatedVars, !DeadVars).
+
+:- pred forward_use_in_case(set(prog_var)::in, set(prog_var)::in,
+ case::in, case::out, set(prog_var)::in, set(prog_var)::out,
+ set(prog_var)::in, set(prog_var)::out) is det.
+
+forward_use_in_case(Inst0, Dead0, !Case, !InstantiatedVars, !DeadVars) :-
+ !.Case = case(Cons, Goal0),
+ forward_use_in_goal(Goal0, Goal, Inst0, Inst, Dead0, Dead),
+ !:Case = case(Cons, Goal),
+ set.union(Inst, !InstantiatedVars),
+ set.union(Dead, !DeadVars).
+
+:- pred forward_use_in_disj(list(hlds_goal)::in, list(hlds_goal)::out,
+ set(prog_var)::in, set(prog_var)::out, set(prog_var)::in,
+ set(prog_var)::out) is det.
+
+forward_use_in_disj(!Goals, !InstantiatedVars, !DeadVars):-
+ Inst0 = !.InstantiatedVars,
+ Dead0 = !.DeadVars,
+ list.map_foldl2(forward_use_in_disj_goal(Inst0, Dead0),
+ !Goals, !InstantiatedVars, !DeadVars).
+
+:- pred forward_use_in_disj_goal(set(prog_var)::in, set(prog_var)::in,
+ hlds_goal::in, hlds_goal::out, set(prog_var)::in, set(prog_var)::out,
+ set(prog_var)::in, set(prog_var)::out) is det.
+
+forward_use_in_disj_goal(Inst0, Dead0, !Goal, !InstantiatedVars, !DeadVars) :-
+ forward_use_in_goal(!Goal, Inst0, Inst, Dead0, Dead),
+ set.union(Inst, !InstantiatedVars),
+ set.union(Dead, !DeadVars).
+
+%-----------------------------------------------------------------------------%
+
+:- func this_file = string.
+this_file = "structure_reuse.lfu.m".
+
+:- end_module transform_hlds.ctgc.structure_reuse.lfu.
Index: compiler/structure_sharing.analysis.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_sharing.analysis.m,v
retrieving revision 1.10
diff -u -d -r1.10 structure_sharing.analysis.m
--- compiler/structure_sharing.analysis.m 29 Mar 2006 08:07:23 -0000 1.10
+++ compiler/structure_sharing.analysis.m 27 Apr 2006 09:30:44 -0000
@@ -19,14 +19,13 @@
:- import_module hlds.hlds_module.
:- import_module hlds.hlds_pred.
-:- import_module transform_hlds.ctgc.structure_sharing.domain.
:- import_module io.
%-----------------------------------------------------------------------------%
:- pred structure_sharing_analysis(module_info::in, module_info::out,
- sharing_as_table::out, io::di, io::uo) is det.
+ io::di, io::uo) is det.
:- pred write_pred_sharing_info(module_info::in, pred_id::in,
io::di, io::uo) is det.
@@ -36,8 +35,6 @@
:- implementation.
-:- import_module check_hlds.inst_match.
-:- import_module check_hlds.mode_util.
:- import_module check_hlds.type_util.
:- import_module hlds.hlds_goal.
:- import_module hlds.passes_aux.
@@ -52,10 +49,10 @@
:- import_module parse_tree.prog_data.
:- import_module parse_tree.prog_out.
:- import_module transform_hlds.ctgc.fixpoint_table.
+:- import_module transform_hlds.ctgc.structure_sharing.domain.
:- import_module transform_hlds.ctgc.util.
:- import_module transform_hlds.dependency_graph.
-:- import_module assoc_list.
:- import_module bool.
:- import_module io.
:- import_module list.
@@ -68,7 +65,7 @@
%-----------------------------------------------------------------------------%
-structure_sharing_analysis(!ModuleInfo, !:SharingTable, !IO) :-
+structure_sharing_analysis(!ModuleInfo, !IO) :-
%
% Annotate the HLDS with liveness information.
%
@@ -76,11 +73,11 @@
%
% Load all structure sharing information present in the HLDS.
%
- load_structure_sharing_table(!.ModuleInfo, !:SharingTable),
+ LoadedSharingTable = load_structure_sharing_table(!.ModuleInfo),
%
% Analyse structure sharing for the module.
%
- sharing_analysis(!ModuleInfo, !SharingTable, !IO),
+ sharing_analysis(!ModuleInfo, LoadedSharingTable, !IO),
%
% Maybe write structure sharing pragmas to .opt files.
%
@@ -98,38 +95,6 @@
% Preliminary steps
%
-:- pred load_structure_sharing_table(module_info::in, sharing_as_table::out)
- is det.
-
-load_structure_sharing_table(ModuleInfo, SharingTable) :-
- module_info_predids(ModuleInfo, PredIds),
- list.foldl(load_structure_sharing_table_2(ModuleInfo), PredIds,
- sharing_as_table_init, SharingTable).
-
-:- pred load_structure_sharing_table_2(module_info::in, pred_id::in,
- sharing_as_table::in, sharing_as_table::out) is det.
-
-load_structure_sharing_table_2(ModuleInfo, PredId, !SharingTable) :-
- module_info_pred_info(ModuleInfo, PredId, PredInfo),
- ProcIds = pred_info_procids(PredInfo),
- list.foldl(load_structure_sharing_table_3(ModuleInfo, PredId),
- ProcIds, !SharingTable).
-
-:- pred load_structure_sharing_table_3(module_info::in, pred_id::in,
- proc_id::in, sharing_as_table::in, sharing_as_table::out) is det.
-
-load_structure_sharing_table_3(ModuleInfo, PredId, ProcId, !SharingTable) :-
- module_info_proc_info(ModuleInfo, PredId, ProcId, ProcInfo),
- proc_info_get_structure_sharing(ProcInfo, MaybePublicSharing),
- (
- MaybePublicSharing = yes(PublicSharing),
- PPId = proc(PredId, ProcId),
- PrivateSharing = from_structure_sharing_domain(PublicSharing),
- sharing_as_table_set(PPId, PrivateSharing, !SharingTable)
- ;
- MaybePublicSharing = no
- ).
-
% Annotate the HLDS with pre-birth and post-death information, as
% used by the liveness pass (liveness.m). This information is used to
% eliminate useless sharing pairs during sharing analysis.
@@ -144,9 +109,9 @@
%-----------------------------------------------------------------------------%
:- pred sharing_analysis(module_info::in, module_info::out,
- sharing_as_table::in, sharing_as_table::out, io::di, io::uo) is det.
+ sharing_as_table::in, io::di, io::uo) is det.
-sharing_analysis(!ModuleInfo, !SharingTable, !IO) :-
+sharing_analysis(!ModuleInfo, !.SharingTable, !IO) :-
%
% Perform a bottom-up traversal of the SCCs in the program,
% analysing structure sharing in each one as we go.
@@ -272,40 +237,6 @@
ss_fixpoint_table_description(!.FixpointTable) ++ ")\n", !IO).
%-----------------------------------------------------------------------------%
-
- % Succeeds if the sharing of a procedure can safely be approximated by
- % "bottom", simply by looking at the modes and types of the arguments.
- %
-:- pred bottom_sharing_is_safe_approximation(module_info::in,
- proc_info::in) is semidet.
-
-bottom_sharing_is_safe_approximation(ModuleInfo, ProcInfo) :-
- proc_info_get_headvars(ProcInfo, HeadVars),
- proc_info_get_argmodes(ProcInfo, Modes),
- proc_info_get_vartypes(ProcInfo, VarTypes),
- list.map(map.lookup(VarTypes), HeadVars, Types),
-
- ModeTypePairs = assoc_list.from_corresponding_lists(Modes, Types),
-
- Test = (pred(Pair::in) is semidet :-
- Pair = Mode - Type,
-
- % mode is not unique nor clobbered.
- mode_get_insts(ModuleInfo, Mode, _LeftInst, RightInst),
- \+ inst_is_unique(ModuleInfo, RightInst),
- \+ inst_is_clobbered(ModuleInfo, RightInst),
-
- % mode is output.
- mode_to_arg_mode(ModuleInfo, Mode, Type, ArgMode),
- ArgMode = top_out,
-
- % type is not primitive
- \+ type_is_atomic(Type, ModuleInfo)
- ),
- list.filter(Test, ModeTypePairs, TrueModeTypePairs),
- TrueModeTypePairs = [].
-
-%-----------------------------------------------------------------------------%
%
% Structure sharing analysis of goals
%
@@ -396,7 +327,7 @@
goal_info_get_context(GoalInfo, Context),
context_to_string(Context, ContextString),
!:SharingAs = sharing_as_top_sharing_accumulate(
- "foreign_proc not handles yet (" ++ ContextString ++ ")",
+ "foreign_proc not handled yet (" ++ ContextString ++ ")",
!.SharingAs)
;
GoalExpr = shorthand(_),
@@ -445,86 +376,19 @@
% Lookup the sharing information of a procedure identified by its
% pred_proc_id.
- % 1 - first look in the fixpoint table (which may change the state
- % of this table wrt recursiveness);
- % 2 - then look in sharing_as_table (as we might already have analysed
- % the predicate, if defined in same module, or analysed in other
- % imported module)
- % 3 - try to predict bottom;
- % 4 - react appropriately if the calls happen to be to
- % * either compiler generated predicates
- % * or predicates from builtin.m and private_builtin.m
%
:- pred lookup_sharing(module_info::in, sharing_as_table::in, pred_proc_id::in,
ss_fixpoint_table::in, ss_fixpoint_table::out, sharing_as::out) is det.
lookup_sharing(ModuleInfo, SharingTable, PPId, !FixpointTable, SharingAs) :-
(
- % 1 -- check fixpoint table
+ % check fixpoint table
ss_fixpoint_table_get_as(PPId, SharingAs0, !FixpointTable)
->
SharingAs = SharingAs0
;
- % 2 -- look up in SharingTable
- SharingAs0 = sharing_as_table_search(PPId, SharingTable)
- ->
- SharingAs = SharingAs0
- ;
- % 3 -- predict bottom sharing
- %
- % If it is neither in the fixpoint table, nor in the sharing
- % table, then this means that we have never analysed the called
- % procedure, yet in some cases we can still simply predict that
- % the sharing the called procedure creates is bottom.
- predict_called_pred_is_bottom(ModuleInfo, PPId)
- ->
- SharingAs = sharing_as_init
- ;
- % 4 -- use top-sharing with appropriate message.
- SharingAs = top_sharing_not_found(ModuleInfo, PPId)
- ).
-
-:- pred predict_called_pred_is_bottom(module_info::in, pred_proc_id::in)
- is semidet.
-
-predict_called_pred_is_bottom(ModuleInfo, PPId) :-
- module_info_pred_proc_info(ModuleInfo, PPId, PredInfo, ProcInfo),
- (
- % 1. inferred determinism is erroneous/failure.
- proc_info_get_inferred_determinism(ProcInfo, Determinism),
- (
- Determinism = erroneous
- ;
- Determinism = failure
- )
- ;
- % 2. bottom_sharing_is_safe_approximation
- bottom_sharing_is_safe_approximation(ModuleInfo, ProcInfo)
- ;
- % 3. call to a compiler generate special predicate:
- % "unify", "index", "compare" or "initialise".
- pred_info_get_origin(PredInfo, Origin),
- Origin = special_pred(_)
- ;
- % 4. (XXX UNSAFE!! To verify) any call to private_builtin and builtin
- % procedures.
- PredModule = pred_info_module(PredInfo),
- any_mercury_builtin_module(PredModule)
+ lookup_sharing_or_predict(ModuleInfo, SharingTable, PPId, SharingAs)
).
-
-:- func top_sharing_not_found(module_info, pred_proc_id) = sharing_as.
-
-top_sharing_not_found(ModuleInfo, PPId) = TopSharing :-
- module_info_pred_proc_info(ModuleInfo, PPId, PredInfo, _),
- PPId = proc(PredId, ProcId),
- PredModuleName = pred_info_module(PredInfo),
-
- TopSharing = sharing_as_top_sharing("Lookup sharing failed for " ++
- sym_name_to_escaped_string(PredModuleName) ++ "." ++
- pred_info_name(PredInfo) ++ "/" ++
- int_to_string(pred_info_orig_arity(PredInfo)) ++ " (id = " ++
- int_to_string(pred_id_to_int(PredId)) ++ "," ++
- int_to_string(proc_id_to_int(ProcId))).
%-----------------------------------------------------------------------------%
Index: compiler/structure_sharing.domain.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_sharing.domain.m,v
retrieving revision 1.7
diff -u -d -r1.7 structure_sharing.domain.m
--- compiler/structure_sharing.domain.m 29 Mar 2006 08:07:23 -0000 1.7
+++ compiler/structure_sharing.domain.m 27 Apr 2006 09:30:49 -0000
@@ -6,7 +6,7 @@
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
-% File: ctgc.structure_sharing.domain.m.
+% File: structure_sharing.domain.m.
% Main author: nancy.
% This module defines the abstract domain for representing structure sharing
@@ -110,7 +110,7 @@
sharing_as::in, sharing_as::out) is det.
% sharing_as_rename_using_module_info(ModuleInfo, PPId,
- % ActualVars, ActualTypes, FormalSharing, ActualSharing):
+ % ActualVars, ActualTypes, ActualTVarset, FormalSharing, ActualSharing):
%
% Renaming of the formal description of data structure sharing to the
% actual description of the sharing. The formal information is given
@@ -173,7 +173,7 @@
% The operation produces a software error when called with a top alias
% description.
%
-:- func extend_datastruct(module_info, proc_info, datastruct, sharing_as)
+:- func extend_datastruct(module_info, proc_info, sharing_as, datastruct)
= list(datastruct).
% apply_widening(ModuleInfo, ProcInfo, WideningLimit, WideningDone,
@@ -229,23 +229,59 @@
sharing_as_table::in, sharing_as_table::out) is det.
%-----------------------------------------------------------------------------%
+
+ % Lookup the sharing information in the sharing table, or if it is not
+ % in there, try to predict it using the information available in the
+ % module_info.
+ %
+ % Lookup the sharing information of a procedure identified by its
+ % pred_proc_id.
+ % 1 - look in sharing_as_table (as we might already have analysed
+ % the predicate, if defined in same module, or analysed in other
+ % imported module)
+ % 2 - try to predict bottom;
+ % 3 - react appropriately if the calls happen to be to
+ % * either compiler generated predicates
+ % * or predicates from builtin.m and private_builtin.m
+ %
+:- pred lookup_sharing_or_predict(module_info::in, sharing_as_table::in,
+ pred_proc_id::in, sharing_as::out) is det.
+
+ % Succeeds if the sharing of a procedure can safely be approximated by
+ % "bottom", simply by looking at the modes and types of the arguments.
+ %
+:- pred bottom_sharing_is_safe_approximation(module_info::in,
+ proc_info::in) is semidet.
+
+ % Load all the structure sharing information present in the HLDS into
+ % a sharing table.
+ %
+:- func load_structure_sharing_table(module_info) = sharing_as_table.
+
%-----------------------------------------------------------------------------%
:- implementation.
+:- import_module check_hlds.inst_match.
+:- import_module check_hlds.mode_util.
:- import_module check_hlds.type_util.
:- import_module hlds.hlds_llds.
:- import_module libs.compiler_util.
+:- import_module mdbcomp.prim_data.
:- import_module parse_tree.prog_ctgc.
+:- import_module parse_tree.prog_out.
:- import_module parse_tree.prog_type.
:- import_module parse_tree.prog_type_subst.
:- import_module transform_hlds.ctgc.datastruct.
:- import_module transform_hlds.ctgc.selector.
+:- import_module assoc_list.
:- import_module int.
+:- import_module maybe.
:- import_module pair.
:- import_module require.
:- import_module solutions.
+:- import_module string.
:- import_module svmap.
:- import_module svset.
@@ -591,7 +627,7 @@
list.foldl(sharing_as_least_upper_bound(ModuleInfo, ProcInfo), SharingList,
sharing_as_init).
-extend_datastruct(ModuleInfo, ProcInfo, Datastruct, SharingAs)
+extend_datastruct(ModuleInfo, ProcInfo, SharingAs, Datastruct)
= Datastructures :-
(
SharingAs = bottom,
@@ -660,6 +696,130 @@
sharing_as_table_search(PPId, Table) = Table ^ elem(PPId).
sharing_as_table_set(PPId, Sharing, !Table) :-
!:Table = !.Table ^ elem(PPId) := Sharing.
+
+lookup_sharing_or_predict(ModuleInfo, SharingTable, PPId, SharingAs) :-
+ (
+ % look up in SharingTable
+ SharingAs0 = sharing_as_table_search(PPId, SharingTable)
+ ->
+ SharingAs = SharingAs0
+ ;
+ % or predict bottom sharing
+ %
+ % If it is neither in the fixpoint table, nor in the sharing
+ % table, then this means that we have never analysed the called
+ % procedure, yet in some cases we can still simply predict that
+ % the sharing the called procedure creates is bottom.
+ predict_called_pred_is_bottom(ModuleInfo, PPId)
+ ->
+ SharingAs = sharing_as_init
+ ;
+ % or use top-sharing with appropriate message.
+ SharingAs = top_sharing_not_found(ModuleInfo, PPId)
+ ).
+
+:- pred predict_called_pred_is_bottom(module_info::in, pred_proc_id::in)
+ is semidet.
+
+predict_called_pred_is_bottom(ModuleInfo, PPId) :-
+ module_info_pred_proc_info(ModuleInfo, PPId, PredInfo, ProcInfo),
+ (
+ % 1. inferred determinism is erroneous/failure.
+ proc_info_get_inferred_determinism(ProcInfo, Determinism),
+ (
+ Determinism = erroneous
+ ;
+ Determinism = failure
+ )
+ ;
+ % 2. bottom_sharing_is_safe_approximation
+ bottom_sharing_is_safe_approximation(ModuleInfo, ProcInfo)
+ ;
+ % 3. call to a compiler generate special predicate:
+ % "unify", "index", "compare" or "initialise".
+ pred_info_get_origin(PredInfo, Origin),
+ Origin = special_pred(_)
+ ;
+ % 4. (XXX UNSAFE!! To verify) any call to private_builtin and builtin
+ % procedures.
+ PredModule = pred_info_module(PredInfo),
+ any_mercury_builtin_module(PredModule)
+ ).
+
+:- func top_sharing_not_found(module_info, pred_proc_id) = sharing_as.
+
+top_sharing_not_found(ModuleInfo, PPId) = TopSharing :-
+ module_info_pred_proc_info(ModuleInfo, PPId, PredInfo, _),
+ PPId = proc(PredId, ProcId),
+ PredModuleName = pred_info_module(PredInfo),
+
+ TopSharing = sharing_as_top_sharing("Lookup sharing failed for " ++
+ sym_name_to_escaped_string(PredModuleName) ++ "." ++
+ pred_info_name(PredInfo) ++ "/" ++
+ int_to_string(pred_info_orig_arity(PredInfo)) ++ " (id = " ++
+ int_to_string(pred_id_to_int(PredId)) ++ "," ++
+ int_to_string(proc_id_to_int(ProcId))).
+
+
+%-----------------------------------------------------------------------------%
+
+load_structure_sharing_table(ModuleInfo) = SharingTable :-
+ module_info_predids(ModuleInfo, PredIds),
+ list.foldl(load_structure_sharing_table_2(ModuleInfo), PredIds,
+ sharing_as_table_init, SharingTable).
+
+:- pred load_structure_sharing_table_2(module_info::in, pred_id::in,
+ sharing_as_table::in, sharing_as_table::out) is det.
+
+load_structure_sharing_table_2(ModuleInfo, PredId, !SharingTable) :-
+ module_info_pred_info(ModuleInfo, PredId, PredInfo),
+ ProcIds = pred_info_procids(PredInfo),
+ list.foldl(load_structure_sharing_table_3(ModuleInfo, PredId),
+ ProcIds, !SharingTable).
+
+:- pred load_structure_sharing_table_3(module_info::in, pred_id::in,
+ proc_id::in, sharing_as_table::in, sharing_as_table::out) is det.
+
+load_structure_sharing_table_3(ModuleInfo, PredId, ProcId, !SharingTable) :-
+ module_info_proc_info(ModuleInfo, PredId, ProcId, ProcInfo),
+ proc_info_get_structure_sharing(ProcInfo, MaybePublicSharing),
+ (
+ MaybePublicSharing = yes(PublicSharing),
+ PPId = proc(PredId, ProcId),
+ PrivateSharing = from_structure_sharing_domain(PublicSharing),
+ sharing_as_table_set(PPId, PrivateSharing, !SharingTable)
+ ;
+ MaybePublicSharing = no
+ ).
+%-----------------------------------------------------------------------------%
+ % Succeeds if the sharing of a procedure can safely be approximated by
+ % "bottom", simply by looking at the modes and types of the arguments.
+ %
+bottom_sharing_is_safe_approximation(ModuleInfo, ProcInfo) :-
+ proc_info_get_headvars(ProcInfo, HeadVars),
+ proc_info_get_argmodes(ProcInfo, Modes),
+ proc_info_get_vartypes(ProcInfo, VarTypes),
+ list.map(map.lookup(VarTypes), HeadVars, Types),
+
+ ModeTypePairs = assoc_list.from_corresponding_lists(Modes, Types),
+
+ Test = (pred(Pair::in) is semidet :-
+ Pair = Mode - Type,
+
+ % mode is not unique nor clobbered.
+ mode_get_insts(ModuleInfo, Mode, _LeftInst, RightInst),
+ \+ inst_is_unique(ModuleInfo, RightInst),
+ \+ inst_is_clobbered(ModuleInfo, RightInst),
+
+ % mode is output.
+ mode_to_arg_mode(ModuleInfo, Mode, Type, ArgMode),
+ ArgMode = top_out,
+
+ % type is not primitive
+ \+ type_is_atomic(Type, ModuleInfo)
+ ),
+ list.filter(Test, ModeTypePairs, TrueModeTypePairs),
+ TrueModeTypePairs = [].
%-----------------------------------------------------------------------------%
% Type: sharing_set.
--
nancy.mazur at cs.kuleuven.ac.be ------------ Katholieke Universiteit Leuven -
tel: +32-16-327596 - fax: +32-16-327996 ------- Dept. of Computer Science -
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list