[m-rev.] diff: fix inconsistent structure reuse conditions problem

Peter Wang novalazy at gmail.com
Wed Jul 23 15:13:21 AEST 2008


Branches: main

Fix a problem with intermodule analysis and structure reuse analysis.
During the `--make-analysis-registry' step we may find one set of reuse
conditions for a procedure, but during the making target code step, we find
a different, harsher set of reuse conditions (due to extra information being
available later).  We cannot generate code which would violate the weaker
conditions presented in the analysis file, as calls from external modules
may satisfy the weaker conditions but not the stronger conditions.  

The same problem occurs with --transitive- and `--intermodule-optimisation'.

compiler/structure_reuse.versions.m:
compiler/structure_reuse.analysis.m:
	Fix the problem above.

compiler/structure_reuse.domain.m:
	Improve reverse lookups for a field in the reuse_as_table.

compiler/structure_reuse.indirect.m:
	Conform to reuse_as_table change.

diff --git a/compiler/structure_reuse.analysis.m b/compiler/structure_reuse.analysis.m
index 0738917..34fdabc 100644
--- a/compiler/structure_reuse.analysis.m
+++ b/compiler/structure_reuse.analysis.m
@@ -53,7 +53,9 @@
 :- import_module analysis.
 :- import_module hlds.hlds_module.
 :- import_module hlds.hlds_pred.
+:- import_module transform_hlds.ctgc.structure_reuse.domain.
 
+:- import_module bool.
 :- import_module io. 
 
 %-----------------------------------------------------------------------------%
@@ -87,6 +89,9 @@
 :- instance partial_order(structure_reuse_func_info, structure_reuse_answer).
 :- instance to_term(structure_reuse_answer).
 
+:- pred structure_reuse_answer_harsher_than_in_analysis_registry(
+    module_info::in, reuse_as_table::in, pred_proc_id::in, bool::out) is det.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -116,12 +121,14 @@
 :- import_module transform_hlds.ctgc.structure_sharing.domain.
 :- import_module transform_hlds.mmc_analysis.
 
+:- import_module bimap.
 :- import_module bool.
 :- import_module int.
 :- import_module list.
 :- import_module map.
 :- import_module maybe.
 :- import_module set.
+:- import_module string.
 :- import_module svmap.
 :- import_module term.
 
@@ -246,9 +253,8 @@ structure_reuse_analysis(!ModuleInfo, !IO):-
         MakeAnalysisRegistry = yes,
         some [!AnalysisInfo] (
             module_info_get_analysis_info(!.ModuleInfo, !:AnalysisInfo),
-            CondReuseRevMap = map.reverse_map(ReuseVersionMap),
             map.foldl(
-                record_structure_reuse_results(!.ModuleInfo, CondReuseRevMap),
+                record_structure_reuse_results(!.ModuleInfo, ReuseVersionMap),
                 ReuseInfoMap, !AnalysisInfo),
             set.fold(handle_structure_reuse_dependency(!.ModuleInfo),
                 DepProcs, !AnalysisInfo),
@@ -265,7 +271,7 @@ structure_reuse_analysis(!ModuleInfo, !IO):-
     % remove them if they were created from exported procedures (so would be
     % exported themselves). 
     module_info_get_predicate_table(!.ModuleInfo, PredTable0),
-    map.foldl(
+    bimap.foldl(
         remove_useless_reuse_proc(!.ModuleInfo, VeryVerbose, ReuseInfoMap),
         ReuseVersionMap, PredTable0, PredTable),
     module_info_set_predicate_table(PredTable, !ModuleInfo).
@@ -903,21 +909,16 @@ reuse_answer_from_term(Term, Answer) :-
 %
 
 :- pred record_structure_reuse_results(module_info::in,
-    map(pred_proc_id, set(ppid_no_clobbers))::in, pred_proc_id::in,
+    bimap(ppid_no_clobbers, pred_proc_id)::in, pred_proc_id::in,
     reuse_as_and_status::in, analysis_info::in, analysis_info::out) is det.
 
-record_structure_reuse_results(ModuleInfo, CondReuseReverseMap,
-        PPId, ReuseAs_Status, !AnalysisInfo) :-
-    ( map.search(CondReuseReverseMap, PPId, Set) ->
+record_structure_reuse_results(ModuleInfo, CondReuseMap, PPId, ReuseAs_Status,
+        !AnalysisInfo) :-
+    ( bimap.reverse_search(CondReuseMap, Key, PPId) ->
         % PPId is a conditional reuse procedure created from another procedure.
         % We need to record the result using the name of the original
         % procedure.
-        ( set.singleton_set(Set, Elem) ->
-            Elem = ppid_no_clobbers(RecordPPId, NoClobbers)
-        ;
-            unexpected(this_file,
-                "record_structure_reuse_results: non-singleton set")
-        )
+        Key = ppid_no_clobbers(RecordPPId, NoClobbers)
     ;
         RecordPPId = PPId,
         NoClobbers = []
@@ -939,21 +940,7 @@ record_structure_reuse_results_2(ModuleInfo, PPId, NoClobbers, ReuseAs_Status,
         for_analysis_framework, ShouldWrite),
     (
         ShouldWrite = yes,
-        ( reuse_as_no_reuses(ReuseAs) ->
-            Answer = structure_reuse_answer_no_reuse
-        ; reuse_as_all_unconditional_reuses(ReuseAs) ->
-            Answer = structure_reuse_answer_unconditional
-        ; reuse_as_conditional_reuses(ReuseAs) ->
-            module_info_pred_proc_info(ModuleInfo, PPId, _PredInfo,
-                ProcInfo),
-            proc_info_get_headvars(ProcInfo, HeadVars),
-            proc_info_get_vartypes(ProcInfo, VarTypes),
-            map.apply_to_list(HeadVars, VarTypes, HeadVarTypes),
-            Answer = structure_reuse_answer_conditional(HeadVars,
-                HeadVarTypes, ReuseAs)
-        ;
-            unexpected(this_file, "record_structure_reuse_results")
-        ),
+        reuse_as_to_structure_reuse_answer(ModuleInfo, PPId, ReuseAs, Answer),
         module_name_func_id(ModuleInfo, PPId, ModuleName, FuncId),
         record_result(ModuleName, FuncId, structure_reuse_call(NoClobbers),
             Answer, Status, !AnalysisInfo)
@@ -961,6 +948,26 @@ record_structure_reuse_results_2(ModuleInfo, PPId, NoClobbers, ReuseAs_Status,
         ShouldWrite = no
     ).
 
+:- pred reuse_as_to_structure_reuse_answer(module_info::in, pred_proc_id::in,
+    reuse_as::in, structure_reuse_answer::out) is det.
+
+reuse_as_to_structure_reuse_answer(ModuleInfo, PPId, ReuseAs, Answer) :-
+    ( reuse_as_no_reuses(ReuseAs) ->
+         Answer = structure_reuse_answer_no_reuse
+     ; reuse_as_all_unconditional_reuses(ReuseAs) ->
+         Answer = structure_reuse_answer_unconditional
+     ; reuse_as_conditional_reuses(ReuseAs) ->
+         module_info_pred_proc_info(ModuleInfo, PPId, _PredInfo,
+             ProcInfo),
+         proc_info_get_headvars(ProcInfo, HeadVars),
+         proc_info_get_vartypes(ProcInfo, VarTypes),
+         map.apply_to_list(HeadVars, VarTypes, HeadVarTypes),
+         Answer = structure_reuse_answer_conditional(HeadVars,
+             HeadVarTypes, ReuseAs)
+     ;
+         unexpected(this_file, "reuse_as_to_structure_reuse_answer")
+     ).
+
 :- pred handle_structure_reuse_dependency(module_info::in,
     ppid_no_clobbers::in, analysis_info::in, analysis_info::out) is det.
 
@@ -1022,6 +1029,72 @@ should_write_reuse_info(ModuleInfo, PredId, ProcId, PredInfo, WhatFor,
     ).
 
 %-----------------------------------------------------------------------------%
+%
+% for structure_reuse.versions
+%
+
+structure_reuse_answer_harsher_than_in_analysis_registry(ModuleInfo,
+        ReuseTable, ReusePPId, Harsher) :-
+    module_info_get_analysis_info(ModuleInfo, AnalysisInfo), 
+
+    % Find the original pred_proc_id and no-clobber list that this reuse
+    % procedure was made for.
+    reuse_as_table_reverse_search_reuse_version_proc(ReuseTable, ReusePPId,
+        OrigPPId, NoClobbers),
+
+    % Look up the old result.
+    module_name_func_id(ModuleInfo, OrigPPId, ModuleName, FuncId),
+    module_info_proc_info(ModuleInfo, OrigPPId, ProcInfo),
+    FuncInfo = structure_reuse_func_info(ModuleInfo, ProcInfo),
+    Call = structure_reuse_call(NoClobbers),
+    analysis.lookup_best_result(AnalysisInfo, ModuleName, FuncId, FuncInfo,
+        Call, MaybeOldResult),
+    (
+        MaybeOldResult = yes(analysis_result(OldCall, OldAnswer, _)),
+        equivalent(FuncInfo, Call, OldCall)
+    ->
+        % Compare with the new result.
+        lookup_new_structure_reuse_answer(ModuleInfo, ReuseTable, ReusePPId,
+            NewAnswer),
+        ( more_precise_than(FuncInfo, NewAnswer, OldAnswer) ->
+            Harsher = yes,
+            trace [
+                compile_time(flag("harsher_answer_check")),
+                runtime(env("HARSHER_ANSWER_CHECK")),
+                io(!IO)
+            ] (
+                io.write_string("Structure reuse answer for ", !IO),
+                write_pred_proc_id(ModuleInfo, ReusePPId, !IO),
+                io.write_string(" has harsher conditions than listed " ++
+                    "in analysis file.\n", !IO),
+                io.write_string("was: ", !IO),
+                io.write(OldAnswer, !IO),
+                io.nl(!IO),
+                io.write_string("now: ", !IO),
+                io.write(NewAnswer, !IO),
+                io.nl(!IO)
+            )
+        ;
+            Harsher = no
+        )
+    ;
+        Harsher = no
+    ).
+
+:- pred lookup_new_structure_reuse_answer(module_info::in, reuse_as_table::in,
+    pred_proc_id::in, structure_reuse_answer::out) is det.
+
+lookup_new_structure_reuse_answer(ModuleInfo, ReuseTable, ReusePPId,
+        NewAnswer) :-
+    ( reuse_as_table_search(ReuseTable, ReusePPId, ReuseAs_Status) ->
+        ReuseAs_Status = reuse_as_and_status(NewReuseAs, _)
+    ;
+        unexpected(this_file, "lookup_new_structure_reuse_answer")
+    ),
+    reuse_as_to_structure_reuse_answer(ModuleInfo, ReusePPId, NewReuseAs,
+        NewAnswer).
+
+%-----------------------------------------------------------------------------%
 
 :- pred remove_useless_reuse_proc(module_info::in, bool::in,
     map(pred_proc_id, reuse_as_and_status)::in,
diff --git a/compiler/structure_reuse.domain.m b/compiler/structure_reuse.domain.m
index db5a5ef..1fa3538 100644
--- a/compiler/structure_reuse.domain.m
+++ b/compiler/structure_reuse.domain.m
@@ -24,6 +24,7 @@
 :- import_module transform_hlds.ctgc.livedata.
 :- import_module transform_hlds.ctgc.structure_sharing.domain.
 
+:- import_module bimap.
 :- import_module bool. 
 :- import_module io. 
 :- import_module map. 
@@ -214,7 +215,7 @@
                 reuse_info_map      :: map(pred_proc_id, reuse_as_and_status),
                 % Maps pred_proc_ids to their reuse information and status.
 
-                reuse_version_map   :: map(ppid_no_clobbers, pred_proc_id)
+                reuse_version_map   :: bimap(ppid_no_clobbers, pred_proc_id)
                 % Maps original procedures and associated no-clobber argument
                 % lists to the reuse version procedures already created.
             ).
@@ -243,6 +244,9 @@
 :- pred reuse_as_table_search_reuse_version_proc(reuse_as_table::in,
     pred_proc_id::in, list(int)::in, pred_proc_id::out) is semidet.
 
+:- pred reuse_as_table_reverse_search_reuse_version_proc(reuse_as_table::in,
+    pred_proc_id::in, pred_proc_id::out, list(int)::out) is det.
+
 :- pred reuse_as_table_set(pred_proc_id::in, reuse_as_and_status::in, 
     reuse_as_table::in, reuse_as_table::out) is det.
 
@@ -919,15 +923,24 @@ to_structure_reuse_condition(Condition) = StructureReuseCondition :-
 % reuse_as_table
 %
 
-reuse_as_table_init = reuse_as_table(map.init, map.init).
+reuse_as_table_init = reuse_as_table(map.init, bimap.init).
 
 reuse_as_table_search(Table, PPId, ReuseAs_Status) :-
     map.search(Table ^ reuse_info_map, PPId, ReuseAs_Status).
 
 reuse_as_table_search_reuse_version_proc(Table, PPId, NoClobbers, NewPPId) :-
-    map.search(Table ^ reuse_version_map, ppid_no_clobbers(PPId, NoClobbers),
+    bimap.search(Table ^ reuse_version_map, ppid_no_clobbers(PPId, NoClobbers),
         NewPPId).
 
+reuse_as_table_reverse_search_reuse_version_proc(Table, NewPPId,
+        OrigPPId, NoClobbers) :-
+    ( bimap.reverse_search(Table ^ reuse_version_map, Key, NewPPId) ->
+        Key = ppid_no_clobbers(OrigPPId, NoClobbers)
+    ;
+        unexpected(this_file,
+            "reuse_as_table_reverse_search_reuse_version_proc")
+    ).
+
 reuse_as_table_set(PPId, ReuseAs_Status, !Table) :- 
     T0 = !.Table ^ reuse_info_map,
     map.set(T0, PPId, ReuseAs_Status, T),
@@ -935,7 +948,7 @@ reuse_as_table_set(PPId, ReuseAs_Status, !Table) :-
 
 reuse_as_table_insert_reuse_version_proc(PPId, NoClobbers, NewPPId, !Table) :- 
     T0 = !.Table ^ reuse_version_map,
-    map.det_insert(T0, ppid_no_clobbers(PPId, NoClobbers), NewPPId, T),
+    bimap.det_insert(T0, ppid_no_clobbers(PPId, NoClobbers), NewPPId, T),
     !Table ^ reuse_version_map := T.
 
 reuse_as_table_maybe_dump(DoDump, ModuleInfo, Table, !IO) :-
diff --git a/compiler/structure_reuse.indirect.m b/compiler/structure_reuse.indirect.m
index 0e1633e..4fbb09c 100644
--- a/compiler/structure_reuse.indirect.m
+++ b/compiler/structure_reuse.indirect.m
@@ -85,6 +85,7 @@
 :- import_module transform_hlds.ctgc.util.
 :- import_module transform_hlds.dependency_graph.
 
+:- import_module bimap.
 :- import_module bool.
 :- import_module int.
 :- import_module io.
@@ -183,7 +184,7 @@ indirect_reuse_rerun_analyse_scc(SharingTable, SCC, !ModuleInfo,
     list(pred_proc_id)::out) is det.
 
 extend_scc_with_reuse_procs(ReuseTable, SCC, ExtendedSCC) :-
-    ReuseVersionMap = ReuseTable ^ reuse_version_map,
+    ReuseVersionMap = bimap.forward_map(ReuseTable ^ reuse_version_map),
     solutions(
         (pred(NewPPId::out) is nondet :-
             member(OrigPPId, SCC),
diff --git a/compiler/structure_reuse.versions.m b/compiler/structure_reuse.versions.m
index 1ca1b8c..38c675e 100644
--- a/compiler/structure_reuse.versions.m
+++ b/compiler/structure_reuse.versions.m
@@ -66,10 +66,15 @@
 :- import_module hlds.pred_table.
 :- import_module hlds.quantification.
 :- import_module libs.compiler_util.
+:- import_module libs.globals.
+:- import_module libs.options.
 :- import_module mdbcomp.
 :- import_module mdbcomp.prim_data.
 :- import_module parse_tree.prog_util.
+:- import_module transform_hlds.ctgc.structure_reuse.analysis.
 
+:- import_module bimap.
+:- import_module bool.
 :- import_module list.
 :- import_module map.
 :- import_module maybe.
@@ -102,7 +107,7 @@ generate_reuse_name(ModuleInfo, PPId, NoClobbers) = ReuseName :-
     %
 create_reuse_procedures(!ReuseTable, !ModuleInfo) :-
     % Get the list of conditional reuse procedures already created.
-    ExistingReusePPIds = map.values(!.ReuseTable ^ reuse_version_map),
+    ExistingReusePPIds = bimap.coordinates(!.ReuseTable ^ reuse_version_map),
     ExistingReusePPIdsSet = set.from_list(ExistingReusePPIds),
 
     map.foldl2(divide_reuse_procs(ExistingReusePPIdsSet),
@@ -118,9 +123,9 @@ create_reuse_procedures(!ReuseTable, !ModuleInfo) :-
     % Process all the goals to update the reuse annotations.  In the reuse
     % versions of procedures we can take advantage of potential reuse
     % opportunities.
-    list.foldl(process_proc(convert_potential_reuse, !.ReuseTable),
+    list.foldl(check_cond_process_proc(convert_potential_reuse, !.ReuseTable),
         ReuseCondPPIds, !ModuleInfo),
-    list.foldl(process_proc(convert_potential_reuse, !.ReuseTable),
+    list.foldl(check_cond_process_proc(convert_potential_reuse, !.ReuseTable),
         ExistingReusePPIds, !ModuleInfo),
 
     % In the original procedures, only the unconditional reuse opportunities
@@ -235,6 +240,50 @@ create_fresh_pred_proc_info_copy_2(PredId, PredInfo, ProcInfo, ReusePredName,
     --->    convert_potential_reuse
     ;       leave_potential_reuse.
 
+    % When generating target code, we may find a set of reuse conditions on a
+    % procedure which are *harsher* than the reuse conditions that we found
+    % during the `--make-analysis-registry' step.  This can happen due extra
+    % analysis information gathered for other modules in the meantime.  In that
+    % case, we may have external callers to the procedure which have verified
+    % only against the *laxer* reuse conditions.
+    %
+    % Hence we need to be careful that we don't generate any code which
+    % violates the weaker reuse conditions.  One (conservative) way to do that
+    % is to ignore all the potential reuse annotations and only use the
+    % unconditional reuse annotations.
+    %
+    % XXX the same problem occurs with `--intermodule-optimisation'
+    % 
+:- pred check_cond_process_proc(convert_potential_reuse::in,
+    reuse_as_table::in, pred_proc_id::in, module_info::in, module_info::out)
+    is det.
+
+check_cond_process_proc(ConvertPotentialReuse, ReuseTable, ReusePPId,
+        !ModuleInfo) :-
+    module_info_get_globals(!.ModuleInfo, Globals),
+    globals.lookup_bool_option(Globals, intermodule_analysis,
+        IntermodAnalysis),
+    globals.lookup_bool_option(Globals, make_analysis_registry,
+        MakeAnalysisReg),
+    (
+        IntermodAnalysis = yes,
+        MakeAnalysisReg = no
+    ->
+        structure_reuse_answer_harsher_than_in_analysis_registry(!.ModuleInfo,
+            ReuseTable, ReusePPId, IsHarsher)
+    ;
+        IsHarsher = no
+    ),
+    (
+        IsHarsher = yes,
+        % Ignoring potential reuse is equivalent to having only unconditional
+        % structure reuse.
+        process_proc(leave_potential_reuse, ReuseTable, ReusePPId, !ModuleInfo)
+    ;
+        IsHarsher = no,
+        process_proc(ConvertPotentialReuse, ReuseTable, ReusePPId, !ModuleInfo)
+    ).
+
     % Process the goal of the procedure with the given pred_proc_id so that
     % all potential reuses are replaced by real reuses, and all calls to
     % procedures that have a reuse version are replaced by calls to their


--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the reviews mailing list