[m-rev.] for review: dead_pred_elim optimization
Peter Ross
pro at missioncriticalit.com
Sat Mar 8 02:40:47 AEDT 2003
===================================================================
Estimated hours taken: 6
Branches: main
Fix a performance bug where dead_pred_elim was taking a significant
amount of time to delete entries from the predicate_table. With this
change dead_pred_elim goes from 12 minutes to 55 seconds CPU time in
the IL grade when compiling accumulator.m with
--intermodule-optimization turned on.
compiler/hlds_module.m:
Implement a new predicate, predicate_table_restrict, which
restricts the predicate_table to include only a subset of the
predicates.
Rather than deleting all the non-needed entries, this
predicate builds the predicate_table from scratch again, hence
this predicate is only useful when the number of predicates to
keep is significantly less than the number of predicates to
delete.
Change predicate_table_do_insert so that it records in the
pred_info whether or not a predicate can only be accessed by
its fully qualified name, this is needed so that the
predicate_table can be rebuilt correctly.
compiler/dead_proc_elim.m:
Use predicate_table_restrict to restrict the set of pred_ids
in the predicate_table rather than module_info_remove_predicate
as the amount of predicates to keep is in general
significantly smaller than the number of predicates to keep.
compiler/hlds_pred.m:
Add a new pred_marker which indicates whether or not a
predicate can only be accessed by its fully qualified name.
compiler/hlds_out.m:
compiler/intermod.m:
Handle the new pred_marker.
diff -u compiler/dead_proc_elim.m compiler/dead_proc_elim.m
--- compiler/dead_proc_elim.m 5 Mar 2003 14:52:03 -0000
+++ compiler/dead_proc_elim.m 7 Mar 2003 15:31:16 -0000
@@ -746,7 +746,7 @@
ModuleInfo2),
module_info_get_predicate_table(ModuleInfo2, PredTable0),
- predicate_table_restrict(PredTable0,
+ predicate_table_restrict(ModuleInfo2, PredTable0,
set__to_sorted_list(NeededPreds), PredTable),
module_info_set_predicate_table(ModuleInfo2, PredTable, ModuleInfo).
diff -u compiler/hlds_module.m compiler/hlds_module.m
--- compiler/hlds_module.m 5 Mar 2003 14:52:03 -0000
+++ compiler/hlds_module.m 7 Mar 2003 15:31:16 -0000
@@ -1094,7 +1094,8 @@
% predicate_table size, as rather than removing entries from
% the table it builds a new table from scratch.
-:- pred predicate_table_restrict(predicate_table::in, list(pred_id)::in,
+:- pred predicate_table_restrict(module_info::in,
+ predicate_table::in, list(pred_id)::in,
predicate_table::out) is det.
% Set the pred_id->pred_info map.
@@ -1765,16 +1766,30 @@
%-----------------------------------------------------------------------------%
-predicate_table_restrict(OrigPredicateTable, PredIds, PredicateTable) :-
+predicate_table_restrict(ModuleInfo,
+ OrigPredicateTable, PredIds, PredicateTable) :-
predicate_table_reset(OrigPredicateTable, PredicateTable0),
predicate_table_get_preds(OrigPredicateTable, Preds),
+ module_info_get_partial_qualifier_info(ModuleInfo, PartialQualInfo),
PredicateTable = list__foldl(
(func(PredId, Table0) = Table :-
PredInfo = map__lookup(Preds, PredId),
+ pred_info_get_markers(PredInfo, Markers),
+ (
+ check_marker(Markers,
+ only_accessible_via_fully_qualifed_name)
+ ->
+ NeedQual = may_be_unqualified,
+ MaybeQualInfo = yes(PartialQualInfo)
+ ;
+ NeedQual = must_be_qualified,
+ MaybeQualInfo = no
+ ),
+
predicate_table_insert_2(Table0,
yes(PredId), PredInfo,
- must_be_qualified,
- no, _, Table)
+ NeedQual, MaybeQualInfo,
+ _, Table)
), PredIds, PredicateTable0).
@@ -1802,15 +1817,15 @@
maybe(partial_qualifier_info), pred_id, predicate_table).
:- mode predicate_table_insert_2(in, in, in, in, in, out, out) is det.
-predicate_table_insert_2(PredicateTable0, MaybePredId, PredInfo,
+predicate_table_insert_2(PredicateTable0, MaybePredId, PredInfo0,
NeedQual, MaybeQualInfo, PredId, PredicateTable) :-
PredicateTable0 = predicate_table(Preds0, NextPredId0, PredIds0,
Pred_N_Index0, Pred_NA_Index0, Pred_MNA_Index0,
Func_N_Index0, Func_NA_Index0, Func_MNA_Index0),
- pred_info_module(PredInfo, Module),
- pred_info_name(PredInfo, Name),
- pred_info_arity(PredInfo, Arity),
+ pred_info_module(PredInfo0, Module),
+ pred_info_name(PredInfo0, Name),
+ pred_info_arity(PredInfo0, Arity),
( MaybePredId = yes(PredId),
NextPredId = NextPredId0
@@ -1823,14 +1838,15 @@
% insert the pred_id into either the function or predicate
% indices, as appropriate
- pred_info_get_is_pred_or_func(PredInfo, PredOrFunc),
+ pred_info_get_is_pred_or_func(PredInfo0, PredOrFunc),
(
PredOrFunc = predicate,
predicate_table_do_insert(Module, Name, Arity,
NeedQual, MaybeQualInfo, PredId,
Pred_N_Index0, Pred_N_Index,
Pred_NA_Index0, Pred_NA_Index,
- Pred_MNA_Index0, Pred_MNA_Index),
+ Pred_MNA_Index0, Pred_MNA_Index,
+ PredInfo0, PredInfo),
Func_N_Index = Func_N_Index0,
Func_NA_Index = Func_NA_Index0,
@@ -1844,7 +1860,8 @@
NeedQual, MaybeQualInfo, PredId,
Func_N_Index0, Func_N_Index,
Func_NA_Index0, Func_NA_Index,
- Func_MNA_Index0, Func_MNA_Index),
+ Func_MNA_Index0, Func_MNA_Index,
+ PredInfo0, PredInfo),
Pred_N_Index = Pred_N_Index0,
Pred_NA_Index = Pred_NA_Index0,
@@ -1864,13 +1881,14 @@
:- pred predicate_table_do_insert(module_name, string, arity,
need_qualifier, maybe(partial_qualifier_info),
pred_id, name_index, name_index, name_arity_index,
- name_arity_index, module_name_arity_index, module_name_arity_index).
+ name_arity_index, module_name_arity_index, module_name_arity_index,
+ pred_info, pred_info).
:- mode predicate_table_do_insert(in, in, in, in, in, in,
- in, out, in, out, in, out) is det.
+ in, out, in, out, in, out, in, out) is det.
predicate_table_do_insert(Module, Name, Arity, NeedQual, MaybeQualInfo,
PredId, N_Index0, N_Index, NA_Index0, NA_Index,
- MNA_Index0, MNA_Index) :-
+ MNA_Index0, MNA_Index, PredInfo0, PredInfo) :-
( NeedQual = may_be_unqualified ->
% insert the unqualified name into the name index
multi_map__set(N_Index0, Name, PredId, N_Index),
@@ -1878,10 +1896,17 @@
% insert the unqualified name/arity into the
% name/arity index
NA = Name / Arity,
- multi_map__set(NA_Index0, NA, PredId, NA_Index)
+ multi_map__set(NA_Index0, NA, PredId, NA_Index),
+
+ PredInfo = PredInfo0
;
N_Index = N_Index0,
- NA_Index = NA_Index0
+ NA_Index = NA_Index0,
+
+ pred_info_get_markers(PredInfo0, Markers0),
+ add_marker(Markers0, only_accessible_via_fully_qualifed_name,
+ Markers),
+ pred_info_set_markers(PredInfo0, Markers, PredInfo)
),
( MaybeQualInfo = yes(QualInfo) ->
only in patch2:
--- compiler/intermod.m 28 Feb 2003 06:40:41 -0000 1.133
+++ compiler/intermod.m 7 Mar 2003 15:31:17 -0000
@@ -1817,6 +1817,7 @@
intermod__should_output_marker(generate_inline, _) :-
% This marker should only occur after the magic sets transformation.
error("intermod__should_output_marker: generate_inline").
+intermod__should_output_marker(only_accessible_via_fully_qualifed_name, no).
:- pred get_pragma_foreign_code_vars(list(prog_var)::in,
list(maybe(pair(string, mode)))::in, prog_varset::in,
only in patch2:
--- compiler/hlds_pred.m 28 Feb 2003 06:40:41 -0000 1.118
+++ compiler/hlds_pred.m 7 Mar 2003 15:31:17 -0000
@@ -500,6 +500,10 @@
% the termination of this predicate.
% If the compiler cannot guarantee termination
% then it must give an error message.
+
+ ; only_accessible_via_fully_qualifed_name
+ % This predicate can only be accessed by
+ % its fully qualified name.
.
only in patch2:
--- compiler/hlds_out.m 28 Feb 2003 06:40:41 -0000 1.297
+++ compiler/hlds_out.m 7 Mar 2003 15:31:16 -0000
@@ -976,6 +976,8 @@
hlds_out__marker_name(psn, "psn").
hlds_out__marker_name(supp_magic, "supp_magic").
hlds_out__marker_name(context, "context").
+hlds_out__marker_name(only_accessible_via_fully_qualifed_name,
+ "only_accessible_via_fully_qualifed_name").
hlds_out__write_marker(Marker) -->
{ hlds_out__marker_name(Marker, Name) },
Index: compiler/dead_proc_elim.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/dead_proc_elim.m,v
retrieving revision 1.76
diff -u -r1.76 dead_proc_elim.m
--- compiler/dead_proc_elim.m 28 Feb 2003 06:40:40 -0000 1.76
+++ compiler/dead_proc_elim.m 7 Mar 2003 15:31:16 -0000
@@ -745,11 +745,11 @@
SpecMap0, PragmaMap0),
ModuleInfo2),
- set__list_to_set(PredIds, PredIdSet),
- set__difference(PredIdSet, NeededPreds, DeadPreds),
- set__to_sorted_list(DeadPreds, DeadPredList),
- list__foldl(module_info_remove_predicate, DeadPredList,
- ModuleInfo2, ModuleInfo).
+ module_info_get_predicate_table(ModuleInfo2, PredTable0),
+ predicate_table_restrict(ModuleInfo2, PredTable0,
+ set__to_sorted_list(NeededPreds), PredTable),
+ module_info_set_predicate_table(ModuleInfo2, PredTable, ModuleInfo).
+
:- pred dead_pred_elim_add_entity(entity::in, queue(pred_id)::in,
queue(pred_id)::out, set(pred_id)::in, set(pred_id)::out) is det.
Index: compiler/hlds_module.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_module.m,v
retrieving revision 1.80
diff -u -r1.80 hlds_module.m
--- compiler/hlds_module.m 22 Feb 2003 13:18:24 -0000 1.80
+++ compiler/hlds_module.m 7 Mar 2003 15:31:16 -0000
@@ -1088,6 +1088,16 @@
:- pred predicate_table_get_preds(predicate_table, pred_table).
:- mode predicate_table_get_preds(in, out) is det.
+ % Restrict the predicate table to the list of predicates.
+ % This predicate should only be used when the set of predicates
+ % to restrict the table to is significantly smaller then the
+ % predicate_table size, as rather than removing entries from
+ % the table it builds a new table from scratch.
+
+:- pred predicate_table_restrict(module_info::in,
+ predicate_table::in, list(pred_id)::in,
+ predicate_table::out) is det.
+
% Set the pred_id->pred_info map.
% NB You shouldn't modify the keys in this table, only
% use predicate_table_insert, predicate_table_remove_predid and
@@ -1756,44 +1766,87 @@
%-----------------------------------------------------------------------------%
+predicate_table_restrict(ModuleInfo,
+ OrigPredicateTable, PredIds, PredicateTable) :-
+ predicate_table_reset(OrigPredicateTable, PredicateTable0),
+ predicate_table_get_preds(OrigPredicateTable, Preds),
+ module_info_get_partial_qualifier_info(ModuleInfo, PartialQualInfo),
+ PredicateTable = list__foldl(
+ (func(PredId, Table0) = Table :-
+ PredInfo = map__lookup(Preds, PredId),
+ pred_info_get_markers(PredInfo, Markers),
+ (
+ check_marker(Markers,
+ only_accessible_via_fully_qualifed_name)
+ ->
+ NeedQual = may_be_unqualified,
+ MaybeQualInfo = yes(PartialQualInfo)
+ ;
+ NeedQual = must_be_qualified,
+ MaybeQualInfo = no
+ ),
+
+ predicate_table_insert_2(Table0,
+ yes(PredId), PredInfo,
+ NeedQual, MaybeQualInfo,
+ _, Table)
+
+ ), PredIds, PredicateTable0).
+
+:- pred predicate_table_reset(predicate_table::in, predicate_table::out) is det.
+
+predicate_table_reset(PredicateTable0, PredicateTable) :-
+ PredicateTable0 = predicate_table(_, NextPredId, _, _, _, _, _, _, _),
+ PredicateTable = predicate_table(map__init, NextPredId, [], map__init,
+ map__init, map__init, map__init, map__init, map__init).
+
+%-----------------------------------------------------------------------------%
+
predicate_table_insert(PredicateTable0, PredInfo, PredId, PredicateTable) :-
- predicate_table_insert_2(PredicateTable0, PredInfo,
+ predicate_table_insert_2(PredicateTable0, no, PredInfo,
must_be_qualified, no, PredId, PredicateTable).
predicate_table_insert(PredicateTable0, PredInfo, NeedQual, QualInfo,
PredId, PredicateTable) :-
- predicate_table_insert_2(PredicateTable0, PredInfo,
+ predicate_table_insert_2(PredicateTable0, no, PredInfo,
NeedQual, yes(QualInfo),
PredId, PredicateTable).
-:- pred predicate_table_insert_2(predicate_table, pred_info, need_qualifier,
+:- pred predicate_table_insert_2(predicate_table, maybe(pred_id),
+ pred_info, need_qualifier,
maybe(partial_qualifier_info), pred_id, predicate_table).
-:- mode predicate_table_insert_2(in, in, in, in, out, out) is det.
+:- mode predicate_table_insert_2(in, in, in, in, in, out, out) is det.
-predicate_table_insert_2(PredicateTable0, PredInfo, NeedQual, MaybeQualInfo,
- PredId, PredicateTable) :-
+predicate_table_insert_2(PredicateTable0, MaybePredId, PredInfo0,
+ NeedQual, MaybeQualInfo, PredId, PredicateTable) :-
PredicateTable0 = predicate_table(Preds0, NextPredId0, PredIds0,
Pred_N_Index0, Pred_NA_Index0, Pred_MNA_Index0,
Func_N_Index0, Func_NA_Index0, Func_MNA_Index0),
- pred_info_module(PredInfo, Module),
- pred_info_name(PredInfo, Name),
- pred_info_arity(PredInfo, Arity),
+ pred_info_module(PredInfo0, Module),
+ pred_info_name(PredInfo0, Name),
+ pred_info_arity(PredInfo0, Arity),
+
+ ( MaybePredId = yes(PredId),
+ NextPredId = NextPredId0
% allocate a new pred_id
- PredId = NextPredId0,
- hlds_pred__next_pred_id(PredId, NextPredId),
+ ; MaybePredId = no,
+ PredId = NextPredId0,
+ hlds_pred__next_pred_id(PredId, NextPredId)
+ ),
% insert the pred_id into either the function or predicate
% indices, as appropriate
- pred_info_get_is_pred_or_func(PredInfo, PredOrFunc),
+ pred_info_get_is_pred_or_func(PredInfo0, PredOrFunc),
(
PredOrFunc = predicate,
predicate_table_do_insert(Module, Name, Arity,
NeedQual, MaybeQualInfo, PredId,
Pred_N_Index0, Pred_N_Index,
Pred_NA_Index0, Pred_NA_Index,
- Pred_MNA_Index0, Pred_MNA_Index),
+ Pred_MNA_Index0, Pred_MNA_Index,
+ PredInfo0, PredInfo),
Func_N_Index = Func_N_Index0,
Func_NA_Index = Func_NA_Index0,
@@ -1807,7 +1860,8 @@
NeedQual, MaybeQualInfo, PredId,
Func_N_Index0, Func_N_Index,
Func_NA_Index0, Func_NA_Index,
- Func_MNA_Index0, Func_MNA_Index),
+ Func_MNA_Index0, Func_MNA_Index,
+ PredInfo0, PredInfo),
Pred_N_Index = Pred_N_Index0,
Pred_NA_Index = Pred_NA_Index0,
@@ -1827,13 +1881,14 @@
:- pred predicate_table_do_insert(module_name, string, arity,
need_qualifier, maybe(partial_qualifier_info),
pred_id, name_index, name_index, name_arity_index,
- name_arity_index, module_name_arity_index, module_name_arity_index).
+ name_arity_index, module_name_arity_index, module_name_arity_index,
+ pred_info, pred_info).
:- mode predicate_table_do_insert(in, in, in, in, in, in,
- in, out, in, out, in, out) is det.
+ in, out, in, out, in, out, in, out) is det.
predicate_table_do_insert(Module, Name, Arity, NeedQual, MaybeQualInfo,
PredId, N_Index0, N_Index, NA_Index0, NA_Index,
- MNA_Index0, MNA_Index) :-
+ MNA_Index0, MNA_Index, PredInfo0, PredInfo) :-
( NeedQual = may_be_unqualified ->
% insert the unqualified name into the name index
multi_map__set(N_Index0, Name, PredId, N_Index),
@@ -1841,10 +1896,17 @@
% insert the unqualified name/arity into the
% name/arity index
NA = Name / Arity,
- multi_map__set(NA_Index0, NA, PredId, NA_Index)
+ multi_map__set(NA_Index0, NA, PredId, NA_Index),
+
+ PredInfo = PredInfo0
;
N_Index = N_Index0,
- NA_Index = NA_Index0
+ NA_Index = NA_Index0,
+
+ pred_info_get_markers(PredInfo0, Markers0),
+ add_marker(Markers0, only_accessible_via_fully_qualifed_name,
+ Markers),
+ pred_info_set_markers(PredInfo0, Markers, PredInfo)
),
( MaybeQualInfo = yes(QualInfo) ->
Index: compiler/hlds_out.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_out.m,v
retrieving revision 1.297
diff -u -r1.297 hlds_out.m
--- compiler/hlds_out.m 28 Feb 2003 06:40:41 -0000 1.297
+++ compiler/hlds_out.m 7 Mar 2003 15:31:16 -0000
@@ -976,6 +976,8 @@
hlds_out__marker_name(psn, "psn").
hlds_out__marker_name(supp_magic, "supp_magic").
hlds_out__marker_name(context, "context").
+hlds_out__marker_name(only_accessible_via_fully_qualifed_name,
+ "only_accessible_via_fully_qualifed_name").
hlds_out__write_marker(Marker) -->
{ hlds_out__marker_name(Marker, Name) },
Index: compiler/hlds_pred.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_pred.m,v
retrieving revision 1.118
diff -u -r1.118 hlds_pred.m
--- compiler/hlds_pred.m 28 Feb 2003 06:40:41 -0000 1.118
+++ compiler/hlds_pred.m 7 Mar 2003 15:31:17 -0000
@@ -500,6 +500,10 @@
% the termination of this predicate.
% If the compiler cannot guarantee termination
% then it must give an error message.
+
+ ; only_accessible_via_fully_qualifed_name
+ % This predicate can only be accessed by
+ % its fully qualified name.
.
Index: compiler/intermod.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/intermod.m,v
retrieving revision 1.133
diff -u -r1.133 intermod.m
--- compiler/intermod.m 28 Feb 2003 06:40:41 -0000 1.133
+++ compiler/intermod.m 7 Mar 2003 15:31:17 -0000
@@ -1817,6 +1817,7 @@
intermod__should_output_marker(generate_inline, _) :-
% This marker should only occur after the magic sets transformation.
error("intermod__should_output_marker: generate_inline").
+intermod__should_output_marker(only_accessible_via_fully_qualifed_name, no).
:- pred get_pragma_foreign_code_vars(list(prog_var)::in,
list(maybe(pair(string, mode)))::in, prog_varset::in,
--------------------------------------------------------------------------
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