[m-rev.] diff/for review: improving the compiler's worst case performance

Zoltan Somogyi zs at cs.mu.OZ.AU
Mon Jan 10 16:21:45 AEDT 2005


For post-commit review by anyone.

I have tested the effect of this diff on the performance of the compiler
using tools/speedtest, which times the compilation of the six largest
modules of the compiler. The result was that this diff generates a 1.7%
slowdown. However, on the file generated by caribou, car.m, it yields
a 55% speedup:

	lmc11 -vS car.m >& LMC11
	122.710u 0.850s 2:09.12 95.6%   0+0k 0+0io 3721pf+0w
	lmc20 -vS car.m > & LMC20
	79.050u 0.470s 1:19.99 99.4%    0+0k 0+0io 3720pf+0w

lmc11 is the original compiler, lmc20 is the one with the following changes.

Zoltan.

Fix performance problems in the compiler when handling automatically generated
code (specifically, code generated by caribou). These depend on new facilities
in the library.

Fix a problem with the debugger: get the debugger to stop when given an
interrupt signal. (I needed this fix to find the performance problems above.)
The problem was that the variable set by the interrupt handler wasn't the
right one.

library/map.m:
	The map__overlay predicate takes time linear in the new map.
	However, sometimes the compiler wants to overlay a large map on a small
	one. Add a new version, map__overlay_large_map, which does the same job
	but whose complexity is linear in the size of the old map.

library/set.m:
library/set__ordlist.m:
	Add a new version of set__divide specialized to a situation that
	occurs in some performance-critical code in the compiler. This lowers
	the complexity from quadratic to linear.

library/bag.m:
	Add predicates for operating on sets alongside for predicates for
	operating on lists. These should be able to exploit the sortedness
	of the set, although we don't do so yet.

library/svbag.m:
	Add this new module to make some of the changes to the compiler easier.

library/library.m:
NEWS:
	Mention the new module.

compiler/instmap.m:
	Use either map__overlay or map__overlay_large_map, depending on which
	one is likely to be more efficient.

compiler/deforest.m:
compiler/goal_util.m:
compiler/mode_util.m:
compiler/simplify.m:
compiler/table_gen.m:
	Conform to the changes in instmap.m.

compiler/liveness.m:
	Use the specialized version of set__divide.

compiler/mode_info.m:
	The original representation of liveness information in the mode
	analyzer had a fast insert operation, but a slow delete operation
	and a lookup operation that is *very* slow when analyzing long
	conjunctions. Replace that representation with a more direct
	and more compact representation with slower insert operation
	but much faster lookup operation and significantly faster delete
	operation.

compiler/modes.m:
compiler/unique_modes.m:
	Conform to the changes in mode_info.m.

trace/mercury_trace.c:
	Make the debugger's interrupt handler set the variable actually used
	by MR_trace to select which function to call.

runtime/mercury_trace_base.[ch]:
	Make MR_selected_trace_func_ptr volatile, since it is now set from
	an interrupt handler.

runtime/mercury_wrapper.[ch]:
	Make MR_trace_handler non-volatile, since it is no longer set from
	an interrupt handler. Change its name to MR_exec_trace_handler to
	reflect the fact that it is not the only trace handler.

util/mkinit.c:
	Refer to MR_trace_handler by its new name.

cvs diff: Diffing .
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.358
diff -u -b -r1.358 NEWS
--- NEWS	7 Jan 2005 06:10:31 -0000	1.358
+++ NEWS	10 Jan 2005 01:26:10 -0000
@@ -22,9 +22,9 @@
   version_array2d, version_bitmap, version_hash_table, and version_store,
   implementing non-unique versions of these types supporting O(1) access for
   non-persistent use.  A new module term_to_xml has been added for converting
-  arbitrary terms to XML documents. Five new modules, svarray, svmap, svbimap,
-  svset and svqueue now provide more convenient ways to update arrays, maps,
-  bimaps, sets and queues in code that uses state variables.
+  arbitrary terms to XML documents. Six new modules, svarray, svmap, svbimap,
+  svset, svbag and svqueue now provide more convenient ways to update arrays,
+  maps, bimaps, sets, bags and queues in code that uses state variables.
 * New procedures have been added to many of the existing standard library
   modules.  Most notably, these include procedures for creating
   directories and symbolic links, for checking file types and file
@@ -232,8 +232,8 @@
   useful with higher-order code.  It can also be useful with state
   variables.  We've also added a function version. 
 
-* We've added some new predicates, map__common_subset and map__foldl3,
-  to map.m.
+* We've added some new predicates, map__common_subset, map__foldl3,
+  and map__overlay_large_map, to map.m.
 
 * We've added a predicate, map_fold, to set.m.
 
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/deforest.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/deforest.m,v
retrieving revision 1.40
diff -u -b -r1.40 deforest.m
--- compiler/deforest.m	2 Sep 2004 23:49:32 -0000	1.40
+++ compiler/deforest.m	9 Jan 2005 05:23:01 -0000
@@ -1708,7 +1708,7 @@
 	goal_list_instmap_delta([EarlierGoal | BetweenGoals], Delta0),
 	LaterGoal = _ - LaterInfo,
 	goal_info_get_instmap_delta(LaterInfo, Delta1),
-	instmap_delta_apply_instmap_delta(Delta0, Delta1, Delta2),
+	instmap_delta_apply_instmap_delta(Delta0, Delta1, test_size, Delta2),
 	instmap_delta_restrict(Delta2, NonLocals, Delta),
 	goal_list_determinism([EarlierGoal | BetweenGoals], Detism0),
 	goal_info_get_determinism(LaterInfo, Detism1),
Index: compiler/goal_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/goal_util.m,v
retrieving revision 1.99
diff -u -b -r1.99 goal_util.m
--- compiler/goal_util.m	23 Dec 2004 04:52:21 -0000	1.99
+++ compiler/goal_util.m	9 Jan 2005 04:52:50 -0000
@@ -1047,8 +1047,8 @@
 	goal_info_get_nonlocals(CaseGoalInfo, CaseNonLocals0),
 	set__insert(CaseNonLocals0, Var, CaseNonLocals),
 	goal_info_get_instmap_delta(CaseGoalInfo, CaseInstMapDelta),
-	instmap_delta_apply_instmap_delta(ExtraInstMapDelta,
-		CaseInstMapDelta, InstMapDelta),
+	instmap_delta_apply_instmap_delta(ExtraInstMapDelta, CaseInstMapDelta,
+		test_size, InstMapDelta),
 	goal_info_get_determinism(CaseGoalInfo, CaseDetism0),
 	det_conjunction_detism(semidet, CaseDetism0, Detism),
 	infer_goal_info_purity(CaseGoalInfo, CasePurity),
@@ -1120,7 +1120,8 @@
 
 	goal_info_get_instmap_delta(GoalInfo1, Delta1),
 	goal_info_get_instmap_delta(GoalInfo2, Delta2),
-	instmap_delta_apply_instmap_delta(Delta1, Delta2, CombinedDelta0),
+	instmap_delta_apply_instmap_delta(Delta1, Delta2, test_size,
+		CombinedDelta0),
 	instmap_delta_restrict(CombinedDelta0, OuterNonLocals, CombinedDelta),
 
 	goal_info_get_determinism(GoalInfo1, Detism1),
Index: compiler/hlds_goal.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.120
diff -u -b -r1.120 hlds_goal.m
--- compiler/hlds_goal.m	20 Dec 2004 01:15:37 -0000	1.120
+++ compiler/hlds_goal.m	9 Jan 2005 04:53:08 -0000
@@ -1872,8 +1872,8 @@
 	ApplyDelta = (pred(Goal::in, Delta0::in, Delta::out) is det :-
 			Goal = _ - GoalInfo,
 			goal_info_get_instmap_delta(GoalInfo, Delta1),
-			instmap_delta_apply_instmap_delta(Delta0,
-				Delta1, Delta)
+			instmap_delta_apply_instmap_delta(Delta0, Delta1,
+				test_size, Delta)
 		),
 	instmap_delta_init_reachable(InstMapDelta0),
 	list__foldl(ApplyDelta, Goals, InstMapDelta0, InstMapDelta).
Index: compiler/instmap.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/instmap.m,v
retrieving revision 1.36
diff -u -b -r1.36 instmap.m
--- compiler/instmap.m	23 Dec 2004 06:49:16 -0000	1.36
+++ compiler/instmap.m	10 Jan 2005 05:01:03 -0000
@@ -169,6 +169,11 @@
 
 %-----------------------------------------------------------------------------%
 
+:- type overlay_how
+	--->	large_base
+	;	large_overlay
+	;	test_size.
+
 	% Given two instmaps and a set of variables, compute an instmap delta
 	% which records the change in the instantiation state of those
 	% variables.
@@ -187,7 +192,7 @@
 	% instmap_delta.
 	%
 :- pred instmap_delta_apply_instmap_delta(instmap_delta::in, instmap_delta::in,
-	instmap_delta::out) is det.
+	overlay_how::in, instmap_delta::out) is det.
 
 	% instmap_merge(NonLocalVars, InstMaps, MergeContext):
 	%       Merge the `InstMaps' resulting from different branches
@@ -301,7 +306,7 @@
 :- import_module hlds__hlds_data.
 :- import_module parse_tree__prog_data.
 
-:- import_module std_util, require, string, term, svmap.
+:- import_module std_util, require, string, int, term, svmap.
 
 :- type instmap_delta	==	instmap.
 
@@ -565,11 +570,41 @@
 	% instmap_delta on top of those in the first to produce a new
 	% instmap_delta.
 
-instmap_delta_apply_instmap_delta(unreachable, _, unreachable).
-instmap_delta_apply_instmap_delta(reachable(_), unreachable, unreachable).
-instmap_delta_apply_instmap_delta(reachable(InstMappingDelta0),
-		reachable(InstMappingDelta1), reachable(InstMappingDelta)) :-
-	map__overlay(InstMappingDelta0, InstMappingDelta1, InstMappingDelta).
+instmap_delta_apply_instmap_delta(InstMap1, InstMap2, How, InstMap) :-
+	(
+		InstMap1 = unreachable,
+		InstMap = unreachable
+	;
+		InstMap1 = reachable(_),
+		InstMap2 = unreachable,
+		InstMap = unreachable
+	;
+		InstMap1 = reachable(InstMappingDelta1),
+		InstMap2 = reachable(InstMappingDelta2),
+		(
+			How = large_base,
+			map__overlay(InstMappingDelta1, InstMappingDelta2,
+				InstMappingDelta)
+		;
+			How = large_overlay,
+			map__overlay_large_map(InstMappingDelta1,
+				InstMappingDelta2, InstMappingDelta)
+		;
+			How = test_size,
+ 			(
+ 				map__count(InstMappingDelta1, Count1),
+ 				map__count(InstMappingDelta2, Count2),
+ 				Count1 >= Count2
+ 			->
+ 				map__overlay(InstMappingDelta1,
+ 					InstMappingDelta2, InstMappingDelta)
+ 			;
+ 				map__overlay_large_map(InstMappingDelta1,
+ 					InstMappingDelta2, InstMappingDelta)
+ 			)
+		),
+		InstMap = reachable(InstMappingDelta)
+	).
 
 %-----------------------------------------------------------------------------%
 
Index: compiler/liveness.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/liveness.m,v
retrieving revision 1.130
diff -u -b -r1.130 liveness.m
--- compiler/liveness.m	30 Jun 2004 02:48:02 -0000	1.130
+++ compiler/liveness.m	9 Jan 2005 11:23:17 -0000
@@ -848,8 +848,7 @@
 	set__difference(Liveness3, PostDeaths, Liveness4),
 	set__union(Liveness4, PostBirths, Liveness5),
 
-	set__divide(set__contains(Liveness0), Liveness5,
-		OldLiveness, NewLiveness0),
+	set__divide_by_set(Liveness0, Liveness5, OldLiveness, NewLiveness0),
 	liveness__get_nonlocals_and_typeinfos(LiveInfo, GoalInfo,
 		_, CompletedNonLocals),
 	set__intersect(NewLiveness0, CompletedNonLocals, NewLiveness),
@@ -997,8 +996,7 @@
 	set__divide(var_is_named(VarSet), PostDeaths2,
 		PostDelayedDead, UnnamedPostDeaths),
 	set__union(DelayedDead2, PostDelayedDead, DelayedDead3),
-	set__divide(set__contains(BornVars0), DelayedDead3,
-		DelayedDead, ToBeKilled),
+	set__divide_by_set(BornVars0, DelayedDead3, DelayedDead, ToBeKilled),
 	set__union(UnnamedPostDeaths, ToBeKilled, PostDeaths),
 	goal_info_set_post_deaths(GoalInfo2, PostDeaths, GoalInfo).
 
Index: compiler/mode_info.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/mode_info.m,v
retrieving revision 1.67
diff -u -b -r1.67 mode_info.m
--- compiler/mode_info.m	23 Dec 2004 04:52:24 -0000	1.67
+++ compiler/mode_info.m	9 Jan 2005 02:54:18 -0000
@@ -25,7 +25,7 @@
 :- import_module hlds__instmap.
 :- import_module parse_tree__prog_data.
 
-:- import_module map, list, set, bool, assoc_list, std_util.
+:- import_module map, list, set, bag, bool, assoc_list, std_util.
 
 :- interface.
 
@@ -112,10 +112,9 @@
 :- pred mode_info_get_var_types(mode_info::in,
 	map(prog_var, type)::out) is det.
 :- pred mode_info_get_delay_info(mode_info::in, delay_info::out) is det.
-:- pred mode_info_get_live_vars(mode_info::in,
-	list(set(prog_var))::out) is det.
-:- pred mode_info_get_nondet_live_vars(mode_info::in,
-	list(set(prog_var))::out) is det.
+:- pred mode_info_get_live_vars(mode_info::in, bag(prog_var)::out) is det.
+:- pred mode_info_get_nondet_live_vars(mode_info::in, bag(prog_var)::out)
+	is det.
 :- pred mode_info_get_last_checkpoint_insts(mode_info::in,
 	assoc_list(prog_var, inst)::out) is det.
 :- pred mode_info_get_parallel_vars(mode_info::in,
@@ -160,9 +159,9 @@
 	mode_info::in, mode_info::out) is det.
 :- pred mode_info_set_delay_info(delay_info::in,
 	mode_info::in, mode_info::out) is det.
-:- pred mode_info_set_live_vars(list(set(prog_var))::in,
+:- pred mode_info_set_live_vars(bag(prog_var)::in,
 	mode_info::in, mode_info::out) is det.
-:- pred mode_info_set_nondet_live_vars(list(set(prog_var))::in,
+:- pred mode_info_set_nondet_live_vars(bag(prog_var)::in,
 	mode_info::in, mode_info::out) is det.
 :- pred mode_info_set_last_checkpoint_insts(assoc_list(prog_var, inst)::in,
 	mode_info::in, mode_info::out) is det.
@@ -239,7 +238,7 @@
 :- import_module check_hlds__mode_errors.
 :- import_module check_hlds__mode_util.
 
-:- import_module string, term, varset.
+:- import_module svbag, string, term, varset.
 :- import_module require, std_util, queue.
 
 :- type mode_info --->
@@ -272,7 +271,7 @@
 		errors		:: list(mode_error_info),
 				% The mode errors found
 
-		live_vars	:: list(set(prog_var)),
+		live_vars	:: bag(prog_var),
 				% The live variables, i.e. those variables
 				% which may be referenced again on forward
 				% execution or after shallow backtracking.
@@ -281,7 +280,7 @@
 				% or semidet disjunction within the current
 				% predicate.)
 
-		nondet_live_vars :: list(set(prog_var)),
+		nondet_live_vars :: bag(prog_var),
 				% The nondet-live variables,
 				% i.e. those variables which may be
 				% referenced again after deep backtracking
@@ -368,8 +367,8 @@
 	proc_info_vartypes(ProcInfo, VarTypes),
 	proc_info_inst_varset(ProcInfo, InstVarSet),
 
-	LiveVarsList = [LiveVars],
-	NondetLiveVarsList = [LiveVars],
+	bag__from_set(LiveVars, LiveVarsBag),
+	bag__from_set(LiveVars, NondetLiveVarsBag),
 
 	Changed = no,
 	CheckingExtraGoals = no,
@@ -377,7 +376,7 @@
 
 	ModeInfo = mode_info(ModuleInfo, PredId, ProcId, VarSet, VarTypes,
 		Context, ModeContext, InstMapping0, LockedVars, DelayInfo,
-		ErrorList, LiveVarsList, NondetLiveVarsList, InstVarSet,
+		ErrorList, LiveVarsBag, NondetLiveVarsBag, InstVarSet,
 		[], [], Changed, HowToCheck, MayChangeProc,
 		CheckingExtraGoals, MayInitSolverVars
 	).
@@ -491,8 +490,10 @@
 mode_info_add_live_vars(NewLiveVars, !MI) :-
 	LiveVars0 = !.MI ^ live_vars,
 	NondetLiveVars0 = !.MI ^ nondet_live_vars,
-	!:MI = !.MI ^ live_vars := [NewLiveVars | LiveVars0],
-	!:MI = !.MI ^ nondet_live_vars := [NewLiveVars | NondetLiveVars0].
+	svbag__insert_set(NewLiveVars, LiveVars0, LiveVars),
+	svbag__insert_set(NewLiveVars, NondetLiveVars0, NondetLiveVars),
+	!:MI = !.MI ^ live_vars := LiveVars,
+	!:MI = !.MI ^ nondet_live_vars := NondetLiveVars.
 
 	% Remove a set of vars from the bag of live vars and
 	% the bag of nondet-live vars.
@@ -500,16 +501,8 @@
 mode_info_remove_live_vars(OldLiveVars, !MI) :-
 	LiveVars0 = !.MI ^ live_vars,
 	NondetLiveVars0 = !.MI ^ nondet_live_vars,
-	(
-		list__delete_first(LiveVars0, OldLiveVars, LiveVars1),
-		list__delete_first(NondetLiveVars0, OldLiveVars,
-			NondetLiveVars1)
-	->
-		LiveVars = LiveVars1,
-		NondetLiveVars = NondetLiveVars1
-	;
-		error("mode_info_remove_live_vars: failed")
-	),
+	svbag__det_remove_set(OldLiveVars, LiveVars0, LiveVars),
+	svbag__det_remove_set(OldLiveVars, NondetLiveVars0, NondetLiveVars),
 	!:MI = !.MI ^ live_vars := LiveVars,
 	!:MI = !.MI ^ nondet_live_vars := NondetLiveVars,
 		% when a variable becomes dead, we may be able to wake
@@ -529,11 +522,7 @@
 	% Check whether a variable is live or not
 
 mode_info_var_is_live(ModeInfo, Var, Result) :-
-	(
-		% some [LiveVars]
-		list__member(LiveVars, ModeInfo^live_vars),
-		set__member(Var, LiveVars)
-	->
+	( bag__contains(ModeInfo ^ live_vars, Var) ->
 		Result = live
 	;
 		Result = dead
@@ -542,27 +531,15 @@
 	% Check whether a variable is nondet_live or not.
 
 mode_info_var_is_nondet_live(ModeInfo, Var, Result) :-
-	(
-		% some [LiveVars]
-		list__member(LiveVars, ModeInfo^nondet_live_vars),
-		set__member(Var, LiveVars)
-	->
+	( bag__contains(ModeInfo ^ nondet_live_vars, Var) ->
 		Result = live
 	;
 		Result = dead
 	).
 
 mode_info_get_liveness(ModeInfo, LiveVars) :-
-	set__init(LiveVars0),
-	mode_info_get_liveness_2(ModeInfo ^ live_vars, LiveVars0, LiveVars).
-
-:- pred mode_info_get_liveness_2(list(set(prog_var))::in, set(prog_var)::in,
-	set(prog_var)::out) is det.
-
-mode_info_get_liveness_2([], LiveVars, LiveVars).
-mode_info_get_liveness_2([LiveVarsSet | LiveVarsList], LiveVars0, LiveVars) :-
-	set__union(LiveVars0, LiveVarsSet, LiveVars1),
-	mode_info_get_liveness_2(LiveVarsList, LiveVars1, LiveVars).
+	bag__to_list_without_duplicates(ModeInfo ^ live_vars, SortedList),
+	set__sorted_list_to_set(SortedList, LiveVars).
 
 %-----------------------------------------------------------------------------%
 
Index: compiler/mode_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/mode_util.m,v
retrieving revision 1.160
diff -u -b -r1.160 mode_util.m
--- compiler/mode_util.m	23 Dec 2004 06:49:17 -0000	1.160
+++ compiler/mode_util.m	9 Jan 2005 05:22:29 -0000
@@ -973,7 +973,7 @@
 	recompute_instmap_delta_1(Atomic, Else0, Else, VarTypes, InstMap0,
 		InstMapDeltaElse, !RI),
 	instmap_delta_apply_instmap_delta(InstMapDeltaCond, InstMapDeltaThen,
-		InstMapDeltaCondThen),
+		test_size, InstMapDeltaCondThen),
 	goal_info_get_nonlocals(GoalInfo, NonLocals),
 	update_module_info(merge_instmap_delta(InstMap0, NonLocals,
 		VarTypes, InstMapDeltaElse, InstMapDeltaCondThen),
@@ -1041,7 +1041,7 @@
 		instmap_delta_restrict(OldInstMapDelta,
 			set__list_to_set(ExtraArgVars), ExtraArgsInstMapDelta),
 		instmap_delta_apply_instmap_delta(InstMapDelta0,
-			ExtraArgsInstMapDelta, InstMapDelta)
+			ExtraArgsInstMapDelta, large_base, InstMapDelta)
 	).
 
 recompute_instmap_delta_2(_, shorthand(_), _, _, _, _, _, !RI) :-
@@ -1064,7 +1064,7 @@
 	recompute_instmap_delta_conj(Atomic, Goals0, Goals, VarTypes, InstMap1,
 		InstMapDelta1, !RI),
 	instmap_delta_apply_instmap_delta(InstMapDelta0, InstMapDelta1,
-		InstMapDelta).
+		large_overlay, InstMapDelta).
 
 %-----------------------------------------------------------------------------%
 
Index: compiler/modes.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/modes.m,v
retrieving revision 1.287
diff -u -b -r1.287 modes.m
--- compiler/modes.m	23 Dec 2004 06:49:18 -0000	1.287
+++ compiler/modes.m	9 Jan 2005 02:54:38 -0000
@@ -364,7 +364,7 @@
 :- import_module parse_tree__prog_out.
 
 :- import_module int, set, term, varset.
-:- import_module list, map, string, require, std_util.
+:- import_module list, map, bag, string, require, std_util.
 :- import_module assoc_list.
 
 %-----------------------------------------------------------------------------%
@@ -1167,7 +1167,7 @@
 	% later on by unique_modes.m.)
 	%
 	mode_info_get_live_vars(!.ModeInfo, LiveVars0),
-	mode_info_set_live_vars([], !ModeInfo),
+	mode_info_set_live_vars(bag__init, !ModeInfo),
 	%
 	% We need to lock the non-local variables, to ensure
 	% that the negation does not bind them.
Index: compiler/simplify.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/simplify.m,v
retrieving revision 1.133
diff -u -b -r1.133 simplify.m
--- compiler/simplify.m	20 Jul 2004 04:41:06 -0000	1.133
+++ compiler/simplify.m	9 Jan 2005 04:52:20 -0000
@@ -952,7 +952,7 @@
 		Then = _ - ThenInfo,
 		goal_info_get_instmap_delta(ThenInfo, ThenDelta),
 		instmap_delta_apply_instmap_delta(CondDelta, ThenDelta,
-			CondThenDelta),
+			test_size, CondThenDelta),
 		Else = _ - ElseInfo,
 		goal_info_get_instmap_delta(ElseInfo, ElseDelta),
                 goal_info_get_nonlocals(GoalInfo0, NonLocals),
Index: compiler/table_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/table_gen.m,v
retrieving revision 1.70
diff -u -b -r1.70 table_gen.m
--- compiler/table_gen.m	22 Dec 2004 06:32:35 -0000	1.70
+++ compiler/table_gen.m	9 Jan 2005 05:23:22 -0000
@@ -3068,7 +3068,7 @@
 	Goal = _ - GoalInfo,
 	goal_info_get_instmap_delta(GoalInfo, IMD0),
 	create_instmap_delta(Rest, IMD1),
-	instmap_delta_apply_instmap_delta(IMD0, IMD1, IMD).
+	instmap_delta_apply_instmap_delta(IMD0, IMD1, test_size, IMD).
 
 %-----------------------------------------------------------------------------%
 
Index: compiler/unique_modes.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/unique_modes.m,v
retrieving revision 1.84
diff -u -b -r1.84 unique_modes.m
--- compiler/unique_modes.m	23 Dec 2004 06:49:21 -0000	1.84
+++ compiler/unique_modes.m	9 Jan 2005 02:53:11 -0000
@@ -132,7 +132,7 @@
 	( determinism_components(Detism, _, at_most_many) ->
 		true
 	;
-		mode_info_set_nondet_live_vars([], !ModeInfo)
+		mode_info_set_nondet_live_vars(bag__init, !ModeInfo)
 	),
 
 	%
@@ -423,7 +423,7 @@
 	% So we need to set the live variables set to empty here.
 	%
 	mode_info_get_live_vars(!.ModeInfo, LiveVars0),
-	mode_info_set_live_vars([], !ModeInfo),
+	mode_info_set_live_vars(bag__init, !ModeInfo),
 	%
 	% We need to lock the non-local variables, to ensure
 	% that the negation does not bind them.
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/stream
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
Index: library/bag.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/bag.m,v
retrieving revision 1.23
diff -u -b -r1.23 bag.m
--- library/bag.m	15 Mar 2004 23:49:29 -0000	1.23
+++ library/bag.m	9 Jan 2005 02:51:22 -0000
@@ -16,7 +16,7 @@
 
 :- interface.
 
-:- import_module list, assoc_list.
+:- import_module list, assoc_list, set.
 
 :- type bag(T).
 
@@ -35,11 +35,21 @@
 :- pred bag__insert_list(bag(T)::in, list(T)::in, bag(T)::out) is det.
 :- func bag__insert_list(bag(T), list(T)) = bag(T).
 
+	% Insert a list of values into a bag.
+	%
+:- pred bag__insert_set(bag(T)::in, set(T)::in, bag(T)::out) is det.
+:- func bag__insert_set(bag(T), set(T)) = bag(T).
+
 	% Make a bag from a list.
 	%
 :- pred bag__from_list(list(T)::in, bag(T)::out) is det.
 :- func bag__from_list(list(T)) = bag(T).
 
+	% Make a bag from a set.
+	%
+:- pred bag__from_set(set(T)::in, bag(T)::out) is det.
+:- func bag__from_set(set(T)) = bag(T).
+
 	% Given a bag, produce a sorted list containing all the values in
 	% the bag.  Each value will appear in the list the same number of
 	% times that it appears in the bag.
@@ -61,6 +71,11 @@
 :- pred bag__to_list_without_duplicates(bag(T)::in, list(T)::out) is det.
 :- func bag__to_list_without_duplicates(bag(T)) = list(T).
 
+	% Given a bag, produce a set containing all the values in the bag.
+	%
+:- pred bag__to_set_without_duplicates(bag(T)::in, set(T)::out) is det.
+:- func bag__to_set_without_duplicates(bag(T)) = set(T).
+
 	% Remove one occurrence of a particular value from a bag.
 	% Fail if the item does not exist in the bag.
 	%
@@ -85,13 +100,23 @@
 	%
 :- pred bag__remove_list(bag(T)::in, list(T)::in, bag(T)::out) is semidet.
 
-:- func bag__det_remove_list(bag(T), list(T)) = bag(T).
-
 	% Remove a list of values from a bag.  Duplicates are removed
 	% from the bag the appropriate number of times.  Abort if any
 	% of the items in the list do not exist in the bag.
 	%
 :- pred bag__det_remove_list(bag(T)::in, list(T)::in, bag(T)::out) is det.
+:- func bag__det_remove_list(bag(T), list(T)) = bag(T).
+
+	% Remove a set of values from a bag. Each value is removed once.
+	% Fail if any of the items in the set do not exist in the bag.
+	%
+:- pred bag__remove_set(bag(T)::in, set(T)::in, bag(T)::out) is semidet.
+
+	% Remove a set of values from a bag. Each value is removed once.
+	% Abort if any of the items in the set do not exist in the bag.
+	%
+:- pred bag__det_remove_set(bag(T)::in, set(T)::in, bag(T)::out) is det.
+:- func bag__det_remove_set(bag(T), set(T)) = bag(T).
 
 	% Delete one occurrence of a particular value from a bag.
 	% If the key is not present, leave the bag unchanged.
@@ -219,10 +244,21 @@
 	bag__insert(Bag0, Item, Bag1),
 	bag__insert_list(Bag1, Items, Bag).
 
+bag__insert_set(Bag0, Set, Bag) :-
+	set__to_sorted_list(Set, List),
+		% XXX We should exploit the sortedness of List.
+	bag__insert_list(Bag0, List, Bag).
+
 bag__from_list(List, Bag) :-
 	bag__init(Bag0),
 	bag__insert_list(Bag0, List, Bag).
 
+bag__from_set(Set, Bag) :-
+	set__to_sorted_list(Set, List),
+	bag__init(Bag0),
+		% XXX We should exploit the sortedness of List.
+	bag__insert_list(Bag0, List, Bag).
+
 bag__to_list(Bag, List) :-
 	map__to_assoc_list(Bag, AssocList),
 	bag__to_list_2(AssocList, List).
@@ -245,6 +281,10 @@
 bag__to_list_without_duplicates(Bag, List) :-
 	map__keys(Bag, List).
 
+bag__to_set_without_duplicates(Bag, Set) :-
+	map__keys(Bag, List),
+	set__sorted_list_to_set(List, Set).
+
 %---------------------------------------------------------------------------%
 
 bag__delete(Bag0, Item, Bag) :-
@@ -282,6 +322,16 @@
 		error("bag__det_remove_list: Missing item in bag.")
 	).
 
+bag__remove_set(Bag0, Set, Bag) :-
+	set__to_sorted_list(Set, List),
+		% XXX We should exploit the sortedness of List.
+	bag__remove_list(Bag0, List, Bag).
+
+bag__det_remove_set(Bag0, Set, Bag) :-
+	set__to_sorted_list(Set, List),
+		% XXX We should exploit the sortedness of List.
+	bag__det_remove_list(Bag0, List, Bag).
+
 bag__remove_all(Bag0, Item, Bag) :- 	% semidet
 	map__remove(Bag0, Item, _Val, Bag).
 
@@ -449,9 +499,15 @@
 bag__insert_list(B1, Xs) = B2 :-
 	bag__insert_list(B1, Xs, B2).
 
+bag__insert_set(B1, Xs) = B2 :-
+	bag__insert_set(B1, Xs, B2).
+
 bag__from_list(Xs) = B :-
 	bag__from_list(Xs, B).
 
+bag__from_set(Xs) = B :-
+	bag__from_set(Xs, B).
+
 bag__to_list(B) = Xs :-
 	bag__to_list(B, Xs).
 
@@ -461,11 +517,17 @@
 bag__to_list_without_duplicates(B) = Xs :-
 	bag__to_list_without_duplicates(B, Xs).
 
+bag__to_set_without_duplicates(B) = Xs :-
+	bag__to_set_without_duplicates(B, Xs).
+
 bag__det_remove(B1, X) = B2 :-
 	bag__det_remove(B1, X, B2).
 
 bag__det_remove_list(B1, Xs) = B2 :-
 	bag__det_remove_list(B1, Xs, B2).
+
+bag__det_remove_set(B1, Xs) = B2 :-
+	bag__det_remove_set(B1, Xs, B2).
 
 bag__delete(B1, X) = B2 :-
 	bag__delete(B1, X, B2).
Index: library/library.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/library.m,v
retrieving revision 1.80
diff -u -b -r1.80 library.m
--- library/library.m	6 Jan 2005 05:08:14 -0000	1.80
+++ library/library.m	9 Jan 2005 01:57:28 -0000
@@ -65,6 +65,7 @@
 :- import_module float.
 :- import_module gc.
 :- import_module getopt.
+:- import_module getopt_io.
 :- import_module graph.
 :- import_module group.
 :- import_module hash_table.
@@ -98,6 +99,7 @@
 :- import_module store.
 :- import_module string.
 :- import_module svarray.
+:- import_module svbag.
 :- import_module svbimap.
 :- import_module svmap.
 :- import_module svqueue.
@@ -190,6 +192,7 @@
 mercury_std_library_module("float").
 mercury_std_library_module("gc").
 mercury_std_library_module("getopt").
+mercury_std_library_module("getopt_io").
 mercury_std_library_module("graph").
 mercury_std_library_module("group").
 mercury_std_library_module("hash_table").
@@ -227,6 +230,7 @@
 mercury_std_library_module("store").
 mercury_std_library_module("string").
 mercury_std_library_module("svarray").
+mercury_std_library_module("svbag").
 mercury_std_library_module("svbimap").
 mercury_std_library_module("svmap").
 mercury_std_library_module("svqueue").
Index: library/map.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.92
diff -u -b -r1.92 map.m
--- library/map.m	6 Jan 2005 05:08:15 -0000	1.92
+++ library/map.m	9 Jan 2005 04:26:39 -0000
@@ -207,6 +207,15 @@
 :- pred map__overlay(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.
 :- func map__overlay(map(K, V), map(K, V)) = map(K, V).
 
+	% map__overlay_large_map(MapA, MapB, Map) performs the same task as
+	% map__overlay(MapA, MapB, Map). However, while map__overlay takes time
+	% proportional to the size of MapB, map__overlay_large_map takes time
+	% proportional to the size of MapA. In other words, it preferable when
+	% MapB is a large map.
+:- pred map__overlay_large_map(map(K, V)::in, map(K, V)::in, map(K, V)::out)
+	is det.
+:- func map__overlay_large_map(map(K, V), map(K, V)) = map(K, V).
+
 	% map__select takes a map and a set of keys and returns
 	% a map containing the keys in the set and their corresponding
 	% values.
@@ -642,6 +651,23 @@
 	map__set(Map0, K, V, Map1),
 	map__overlay_2(AssocList, Map1, Map).
 
+map__overlay_large_map(Map0, Map1, Map) :-
+	map__to_assoc_list(Map0, AssocList),
+	map__overlay_2(AssocList, Map1, Map).
+
+:- pred map__overlay_large_map_2(assoc_list(K, V)::in,
+	map(K, V)::in, map(K, V)::out) is det.
+:- pragma type_spec(map__overlay_large_map_2/3, K = var(_)).
+
+map__overlay_large_map_2([], Map, Map).
+map__overlay_large_map_2([K - V | AssocList], Map0, Map) :-
+	( map__insert(Map0, K, V, Map1) ->
+		Map2 = Map1
+	;
+		Map2 = Map0
+	),
+	map__overlay_large_map_2(AssocList, Map2, Map).
+
 %-----------------------------------------------------------------------------%
 
 map__select(Original, KeySet, NewMap) :-
@@ -937,6 +963,9 @@
 
 map__overlay(M1, M2) = M3 :-
 	map__overlay(M1, M2, M3).
+
+map__overlay_large_map(M1, M2) = M3 :-
+	map__overlay_large_map(M1, M2, M3).
 
 map__select(M1, S) = M2 :-
 	map__select(M1, S, M2).
Index: library/set.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set.m,v
retrieving revision 1.63
diff -u -b -r1.63 set.m
--- library/set.m	15 Mar 2004 23:49:34 -0000	1.63
+++ library/set.m	9 Jan 2005 07:00:51 -0000
@@ -250,8 +250,15 @@
 	% TruePart consists of those elements of Set for which Pred succeeds;
 	% FalsePart consists of those elements of Set for which Pred fails.
 	%
-:- pred set__divide(pred(T1), set(T1), set(T1), set(T1)).
-:- mode set__divide(pred(in) is semidet, in, out, out) is det.
+:- pred set__divide(pred(T)::in(pred(in) is semidet), set(T)::in,
+	set(T)::out, set(T)::out) is det.
+
+	% set_divide_by_set(DivideBySet, Set, InPart, OutPart):
+	% InPart consists of those elements of Set which are also in
+	% DivideBySet; OutPart consists of those elements of which are
+	% not in DivideBySet.
+:- pred set__divide_by_set(set(T)::in, set(T)::in, set(T)::out, set(T)::out)
+	is det.
 
 %--------------------------------------------------------------------------%
 
@@ -448,3 +455,6 @@
 
 set__divide(P, Set, TruePart, FalsePart) :-
 	set_ordlist__divide(P, Set, TruePart, FalsePart).
+
+set__divide_by_set(DivideBySet, Set, TruePart, FalsePart) :-
+	set_ordlist__divide_by_set(DivideBySet, Set, TruePart, FalsePart).
Index: library/set_ordlist.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_ordlist.m,v
retrieving revision 1.16
diff -u -b -r1.16 set_ordlist.m
--- library/set_ordlist.m	15 Mar 2004 23:49:35 -0000	1.16
+++ library/set_ordlist.m	9 Jan 2005 09:49:31 -0000
@@ -216,10 +216,17 @@
 	% set_ordlist__divide(Pred, Set, TruePart, FalsePart):
 	% TruePart consists of those elements of Set for which Pred succeeds;
 	% FalsePart consists of those elements of Set for which Pred fails.
-:- pred set_ordlist__divide(pred(T1)::in(pred(in) is semidet),
-	set_ordlist(T1)::in, set_ordlist(T1)::out, set_ordlist(T1)::out)
+:- pred set_ordlist__divide(pred(T)::in(pred(in) is semidet),
+	set_ordlist(T)::in, set_ordlist(T)::out, set_ordlist(T)::out)
 	is det.
 
+	% set_ordlist__divide_by_set(DivideBySet, Set, InPart, OutPart):
+	% InPart consists of those elements of Set which are also in
+	% DivideBySet; OutPart consists of those elements of which are
+	% not in DivideBySet.
+:- pred set_ordlist__divide_by_set(set_ordlist(T)::in, set_ordlist(T)::in,
+	set_ordlist(T)::out, set_ordlist(T)::out) is det.
+
 %--------------------------------------------------------------------------%
 
 :- implementation.
@@ -490,10 +497,10 @@
 	list__reverse(RevTruePart, TruePart),
 	list__reverse(RevFalsePart, FalsePart).
 
-:- pred set_ordlist__divide_2(pred(T1)::in(pred(in) is semidet),
-	set_ordlist(T1)::in,
-	set_ordlist(T1)::in, set_ordlist(T1)::out,
-	set_ordlist(T1)::in, set_ordlist(T1)::out) is det.
+:- pred set_ordlist__divide_2(pred(T)::in(pred(in) is semidet),
+	set_ordlist(T)::in,
+	set_ordlist(T)::in, set_ordlist(T)::out,
+	set_ordlist(T)::in, set_ordlist(T)::out) is det.
 
 set_ordlist__divide_2(_Pred, [], RevTrue, RevTrue, RevFalse, RevFalse).
 set_ordlist__divide_2(Pred, [H | T], RevTrue0, RevTrue, RevFalse0, RevFalse) :-
@@ -505,3 +512,45 @@
 		RevFalse1 = [H | RevFalse0]
 	),
 	set_ordlist__divide_2(Pred, T, RevTrue1, RevTrue, RevFalse1, RevFalse).
+
+set_ordlist__divide_by_set(DivideBySet, Set, TruePart, FalsePart) :-
+	set_ordlist__divide_by_set_2(DivideBySet, Set,
+		[], RevTruePart, [], RevFalsePart),
+	list__reverse(RevTruePart, TruePart),
+	list__reverse(RevFalsePart, FalsePart),
+	(
+		set_ordlist__divide(set_ordlist__contains(DivideBySet),
+			Set, TruePart, FalsePart)
+	->
+		true
+	;
+		error("divide_by_set")
+	).
+
+:- import_module require.
+
+:- pred set_ordlist__divide_by_set_2(set_ordlist(T1)::in,
+	set_ordlist(T1)::in,
+	set_ordlist(T1)::in, set_ordlist(T1)::out,
+	set_ordlist(T1)::in, set_ordlist(T1)::out) is det.
+
+set_ordlist__divide_by_set_2([], [], !RevTrue, !RevFalse).
+set_ordlist__divide_by_set_2([], [H | T], !RevTrue, !RevFalse) :-
+	list__append(list__reverse([H | T]), !RevFalse).
+set_ordlist__divide_by_set_2([_ | _], [], !RevTrue, !RevFalse).
+set_ordlist__divide_by_set_2([Div | Divs], [H | T], !RevTrue, !RevFalse) :-
+	compare(R, Div, H),
+	(
+		R = (=),
+		!:RevTrue = [H | !.RevTrue],
+		set_ordlist__divide_by_set_2(Divs, T, !RevTrue, !RevFalse)
+	;
+		R = (<),
+		set_ordlist__divide_by_set_2(Divs, [H | T],
+			!RevTrue, !RevFalse)
+	;
+		R = (>),
+		!:RevFalse = [H | !.RevFalse],
+		set_ordlist__divide_by_set_2([Div | Divs], T,
+			!RevTrue, !RevFalse)
+	).
Index: library/svbag.m
===================================================================
RCS file: library/svbag.m
diff -N library/svbag.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ library/svbag.m	9 Jan 2005 02:50:37 -0000
@@ -0,0 +1,149 @@
+%---------------------------------------------------------------------------%
+% Copyright (C) 2004 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%---------------------------------------------------------------------------%
+%
+% File: svbag.m
+%
+% This file provides an interface to the 'bag' ADT that is conducive to the
+% use of state variable notation. The predicates here do the same thing as
+% their counterparts in the bag module; the only difference is the order of the
+% arguments.
+%
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- module svbag.
+
+:- interface.
+
+:- import_module bag.
+:- import_module list, set.
+
+	% Insert a particular value in a bag.
+	%
+:- pred svbag__insert(T::in, bag(T)::in, bag(T)::out) is det.
+
+	% Insert a list of values into a bag.
+	%
+:- pred svbag__insert_list(list(T)::in, bag(T)::in, bag(T)::out) is det.
+
+	% Insert a set of values into a bag.
+	%
+:- pred svbag__insert_set(set(T)::in, bag(T)::in, bag(T)::out) is det.
+
+	% Remove one occurrence of a particular value from a bag.
+	% Fail if the item does not exist in the bag.
+	%
+:- pred svbag__remove(T::in, bag(T)::in, bag(T)::out) is semidet.
+
+	% Remove one occurrence of a particular value from a bag.
+	% Abort if the item does not exist in the bag.
+	%
+:- pred svbag__det_remove(T::in, bag(T)::in, bag(T)::out) is det.
+
+	% Remove a list of values from a bag.  Duplicates are removed
+	% from the bag the appropriate number of times.  Fail if any
+	% of the items in the list do not exist in the bag.
+	%
+	% This call is logically equivalent to:
+	%
+	%	svbag__remove_list(RemoveList, Bag0, Bag) :-
+	%		bag__from_list(RemoveList, RemoveBag),
+	%		bag__is_subbag(RemoveBag, Bag0),
+	%		svbag__subtract(RemoveBag, Bag0, Bag).
+	%
+:- pred svbag__remove_list(list(T)::in, bag(T)::in, bag(T)::out) is semidet.
+
+	% Remove a list of values from a bag.  Duplicates are removed
+	% from the bag the appropriate number of times.  Abort if any
+	% of the items in the list do not exist in the bag.
+	%
+:- pred svbag__det_remove_list(list(T)::in, bag(T)::in, bag(T)::out) is det.
+
+	% Remove a set of values from a bag. Each value is removed once.
+	% Fail if any of the items in the set do not exist in the bag.
+	% 
+:- pred svbag__remove_set(set(T)::in, bag(T)::in, bag(T)::out) is semidet.
+
+	% Remove a set of values from a bag. Each value is removed once.
+	% Abort if any of the items in the set do not exist in the bag.
+	% 
+:- pred svbag__det_remove_set(set(T)::in, bag(T)::in, bag(T)::out) is det.
+
+	% Delete one occurrence of a particular value from a bag.
+	% If the key is not present, leave the bag unchanged.
+	%
+:- pred svbag__delete(T::in, bag(T)::in, bag(T)::out) is det.
+
+	% Remove all occurrences of a particular value from a bag.
+	% Fail if the item does not exist in the bag.
+	%
+:- pred svbag__remove_all(T::in, bag(T)::in, bag(T)::out) is semidet.
+
+	% Delete all occurrences of a particular value from a bag.
+	%
+:- pred svbag__delete_all(T::in, bag(T)::in, bag(T)::out) is det.
+
+	% svbag__subtract(Bag0, SubBag, Bag)
+	% subtracts SubBag from Bag0 to produce Bag
+	% each element in SubBag is removed from Bag0 to produce Bag.
+	% If an element exists in SubBag, but not in Bag, then that
+	% element is not removed.
+	% e.g. svbag__subtract({1, 1, 2, 2, 3 }, {1, 1, 2, 3, 3, 3}, {2}).
+	%
+:- pred svbag__subtract(bag(T)::in, bag(T)::in, bag(T)::out) is det.
+
+	% Fails if the bag is empty.
+	%
+:- pred svbag__remove_smallest(T::out, bag(T)::in, bag(T)::out) is semidet.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+svbag__insert(Item, Bag0, Bag) :-
+	bag__insert(Bag0, Item, Bag).
+
+svbag__insert_list(List, Bag0, Bag) :-
+	bag__insert_list(Bag0, List, Bag).
+
+svbag__insert_set(Set, Bag0, Bag) :-
+	bag__insert_set(Bag0, Set, Bag).
+
+svbag__remove(Item, Bag0, Bag) :-
+	bag__remove(Bag0, Item, Bag).
+
+svbag__det_remove(Item, Bag0, Bag) :-
+	bag__det_remove(Bag0, Item, Bag).
+
+svbag__remove_list(List, Bag0, Bag) :-
+	bag__remove_list(Bag0, List, Bag).
+
+svbag__det_remove_list(List, Bag0, Bag) :-
+	bag__det_remove_list(Bag0, List, Bag).
+
+svbag__remove_set(Set, Bag0, Bag) :-
+	bag__remove_set(Bag0, Set, Bag).
+
+svbag__det_remove_set(Set, Bag0, Bag) :-
+	bag__det_remove_set(Bag0, Set, Bag).
+
+svbag__delete(Item, Bag0, Bag) :-
+	bag__delete(Bag0, Item, Bag).
+
+svbag__remove_all(Item, Bag0, Bag) :-
+	bag__remove_all(Bag0, Item, Bag).
+
+svbag__delete_all(Item, Bag0, Bag) :-
+	bag__delete_all(Bag0, Item, Bag).
+
+svbag__subtract(SubBag, Bag0, Bag) :-
+	bag__subtract(Bag0, SubBag, Bag).
+
+svbag__remove_smallest(Item, Bag0, Bag) :-
+	bag__remove_smallest(Bag0, Item, Bag).
+
+%---------------------------------------------------------------------------%
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
Index: runtime/mercury_trace_base.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_trace_base.c,v
retrieving revision 1.58
diff -u -b -r1.58 mercury_trace_base.c
--- runtime/mercury_trace_base.c	16 Aug 2004 03:51:09 -0000	1.58
+++ runtime/mercury_trace_base.c	9 Jan 2005 01:33:22 -0000
@@ -49,7 +49,8 @@
 MR_bool         MR_debug_enabled = MR_FALSE;
 MR_bool         MR_trace_count_enabled = MR_FALSE;
 MR_bool         MR_trace_func_enabled = MR_FALSE;
-MR_Code         *(*MR_selected_trace_func_ptr)(const MR_Label_Layout *);
+MR_Code         *(*volatile MR_selected_trace_func_ptr)(
+                    const MR_Label_Layout *);
 MR_Unsigned     MR_trace_call_seqno = 0;
 MR_Unsigned     MR_trace_call_depth = 0;
 MR_Unsigned     MR_trace_event_number = 0;
Index: runtime/mercury_trace_base.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_trace_base.h,v
retrieving revision 1.41
diff -u -b -r1.41 mercury_trace_base.h
--- runtime/mercury_trace_base.h	16 Aug 2004 03:51:10 -0000	1.41
+++ runtime/mercury_trace_base.h	9 Jan 2005 01:32:36 -0000
@@ -207,9 +207,13 @@
 /*
 ** MR_selected_trace_func_ptr contains the address of the function to call
 ** in MR_trace if MR_trace_func_enabled is true.
+**
+** Since it is set from a signal handler (MR_trace_interrupt_handler),
+** it must be declared `volatile'.
 */
 
-extern	MR_Code *(*MR_selected_trace_func_ptr)(const MR_Label_Layout *);
+extern	MR_Code *(*volatile MR_selected_trace_func_ptr)(
+			const MR_Label_Layout *);
 
 
 /*
Index: runtime/mercury_wrapper.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_wrapper.c,v
retrieving revision 1.140
diff -u -b -r1.140 mercury_wrapper.c
--- runtime/mercury_wrapper.c	20 Dec 2004 05:53:44 -0000	1.140
+++ runtime/mercury_wrapper.c	9 Jan 2005 01:34:17 -0000
@@ -392,7 +392,7 @@
 		/* normally ML_DI_found_match (output_current/12) */
 void	(*MR_DI_read_request_from_socket)(MR_Word, MR_Word *, MR_Integer *);
 
-MR_Code	*(*volatile MR_trace_func_ptr)(const MR_Label_Layout *);
+MR_Code	*(*MR_exec_trace_func_ptr)(const MR_Label_Layout *);
 
 void	(*MR_address_of_trace_interrupt_handler)(void);
 
@@ -615,7 +615,7 @@
 	MR_trace_start(MR_debug_enabled);
 
 	if (MR_debug_enabled) {
-		MR_selected_trace_func_ptr = MR_trace_func_ptr;
+		MR_selected_trace_func_ptr = MR_exec_trace_func_ptr;
 		/* MR_debug_enabled overrides MR_trace_count_enabled */
 		MR_trace_count_enabled = MR_FALSE;
 	} else if (MR_trace_count_enabled) {
Index: runtime/mercury_wrapper.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_wrapper.h,v
retrieving revision 1.65
diff -u -b -r1.65 mercury_wrapper.h
--- runtime/mercury_wrapper.h	14 Dec 2004 07:04:43 -0000	1.65
+++ runtime/mercury_wrapper.h	9 Jan 2005 01:30:33 -0000
@@ -151,19 +151,13 @@
 extern	void		(*MR_address_of_trace_final_external)(void);
 
 /*
-** MR_trace_func_ptr is set to either MR_trace_real (trace/mercury_trace.c),
-** or MR_trace_fake (runtime/mercury_trace_base.c),
-** depending on whether tracing was enabled when creating the _init.c
-** file.  It is also temporarily set to MR_trace_interrupt by
-** MR_trace_interrupt_handler if tracing was enabled and the
-** process receives a SIGINT signal.
-** It is called from MR_trace (runtime/mercury_trace_base.c).
-**
-** Since it is set from a signal handler, it must be declared `volatile'.
+** MR_exec_trace_func_ptr is set to either MR_trace_real
+** (trace/mercury_trace.c), or MR_trace_fake (runtime/mercury_trace_base.c),
+** depending on whether execution tracing was enabled when creating the _init.c
+** file.
 */
 
-extern	MR_Code		*(*volatile MR_trace_func_ptr)(
-				const MR_Label_Layout *);
+extern	MR_Code		*(*MR_exec_trace_func_ptr)(const MR_Label_Layout *);
 
 /*
 ** If the init file was built with tracing enabled, then
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
Index: trace/mercury_trace.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/trace/mercury_trace.c,v
retrieving revision 1.75
diff -u -b -r1.75 mercury_trace.c
--- trace/mercury_trace.c	19 Nov 2004 05:46:25 -0000	1.75
+++ trace/mercury_trace.c	9 Jan 2005 01:27:10 -0000
@@ -392,8 +392,8 @@
     MR_Unsigned     depth;
     MR_Trace_Port   port;
 
-    /* restore the original MR_trace_func_ptr value */
-    MR_trace_func_ptr = MR_trace_real;
+    /* restore the original MR_selected_trace_func_ptr value */
+    MR_selected_trace_func_ptr = MR_trace_real;
 
     if (MR_trace_handler == MR_TRACE_INTERNAL) {
         MR_trace_interrupt_message();
@@ -422,11 +422,11 @@
     /*
     ** This function is a signal handler, so there is not
     ** much that we can safely do here.  We just set the volatile
-    ** variable MR_trace_func_ptr; the real work will be done
+    ** variable MR_selected_trace_func_ptr; the real work will be done
     ** by MR_trace_interrupt(), which will be called by MR_trace()
     ** at the next debugger event.
     */
-    MR_trace_func_ptr = MR_trace_interrupt;
+    MR_selected_trace_func_ptr = MR_trace_interrupt;
 }
 
 static MR_Code *
cvs diff: Diffing util
Index: util/mkinit.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/util/mkinit.c,v
retrieving revision 1.94
diff -u -b -r1.94 mkinit.c
--- util/mkinit.c	14 Dec 2004 01:07:32 -0000	1.94
+++ util/mkinit.c	9 Jan 2005 12:50:09 -0000
@@ -316,7 +316,7 @@
 	"	MR_io_print_to_cur_stream = ML_io_print_to_cur_stream;\n"
 	"	MR_io_print_to_stream = ML_io_print_to_stream;\n"
 	"#if MR_TRACE_ENABLED\n"
-	"	MR_trace_func_ptr = MR_trace_real;\n"
+	"	MR_exec_trace_func_ptr = MR_trace_real;\n"
 	"	MR_register_module_layout = MR_register_module_layout_real;\n"
 	"	MR_address_of_trace_getline = MR_trace_getline;\n"
 	"	MR_address_of_trace_get_command = MR_trace_get_command;\n"
@@ -329,7 +329,7 @@
 	"	MR_address_of_trace_final_external = MR_trace_final_external;\n"
 	"  #endif\n"
 	"#else\n"
-	"	MR_trace_func_ptr = MR_trace_fake;\n"
+	"	MR_exec_trace_func_ptr = MR_trace_fake;\n"
 	"	MR_register_module_layout = NULL;\n"
 	"	MR_address_of_trace_getline = NULL;\n"
 	"	MR_address_of_trace_get_command = NULL;\n"
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
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