[m-rev.] for review: dead_pred_elim optimization

[Peter Ross]

Hi,

For fjh to review.


===================================================================


Estimated hours taken: 4
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.

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.

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	5 Mar 2003 14:52:03 -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(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	5 Mar 2003 14:52:03 -0000
@@ -1088,6 +1088,15 @@
 :- 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(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,22 +1765,45 @@
 
 %-----------------------------------------------------------------------------%
 
+predicate_table_restrict(OrigPredicateTable, PredIds, PredicateTable) :-
+	predicate_table_reset(OrigPredicateTable, PredicateTable0),
+	predicate_table_get_preds(OrigPredicateTable, Preds),
+	PredicateTable = list__foldl(
+			(func(PredId, Table0) = Table :-
+				PredInfo = map__lookup(Preds, PredId),
+				predicate_table_insert_2(Table0,
+						yes(PredId), PredInfo,
+						must_be_qualified,
+						no, _, 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, PredInfo,
+		NeedQual, MaybeQualInfo, PredId, PredicateTable) :-
 
 	PredicateTable0 = predicate_table(Preds0, NextPredId0, PredIds0,
 				Pred_N_Index0, Pred_NA_Index0, Pred_MNA_Index0,
@@ -1780,9 +1812,14 @@
 	pred_info_name(PredInfo, Name),
 	pred_info_arity(PredInfo, 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

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------