[m-rev.] For review: Implemention of the region runtime system

Zoltan Somogyi zs at csse.unimelb.edu.au
Tue Oct 9 17:57:27 AEST 2007


On 08-Oct-2007, Quan Phan <quan.phan at cs.kuleuven.be> wrote:
> Zoltan, do you have a running rbmm system yet?

Yes. It passes bootcheck with flying colours.

> To compile crypt.m, I
> need to use --no-inlining, otherwise the region analysis falls into an
> infinite loop. If you can run crypt and reproduce the error, we can
> discuss this problem in another email.

I found the infinite loop myself, though haven't yet looked for a workaround
when I found your mail.

> Yes, not only the corresponding #defines, but also the corresponding
> type structs if we will use any of them. The effort to keep the comment
> consistent seems worth it because I once got a bug due to the change of
> size_region_disj_protect from 2 to 1 and I forgot to delete a field in
> MR_Disj_Protection struct. The bug is not easy to detect.

Which is we should switch over to using structures, instead of pointer
arithmetic. I will do that tomorrow or the day after.

> Because you also produce a diff, i.e., making changes here and there,
> could you also make the small changes you mentioned above (variable
> names, ite style, etc)?

I have done most of those changes. I will do the rest soon.

The updated log message and diff follow. Since I have tested it several
different ways, and in any case any problems shouldn't affect anyone but
Quan and me, I am committing it.

Quan, please do the following.

1.	Keep unchanged the workspace that you did your work in, the one
	that your original diff was derived from.
2.	Check out a fresh workspace that includes my commit of the updated
	diff.
3.	Run diff to compare the runtime, library and compile directories
	of your old workspace and the new one.
4.	Check the diff output to see if there is anything that looks
	suspicious. (I did some of the work after midnight.)

If you have any changes in your old workspace that you did *after* you sent the
original diff, and it is not superseded by my update, then treat it as a new
change and post it for review when ready.

If you read this mail too late and have already updated the old workspace,
you would have got lots of conflicts. This is okay. The old versions of the
files from your workspace will still be there. CVS doesn't delete them, it just
renames them by putting ".#" before their names and the version number of the
version they collided with after their names. You can do your diff with those.

> Or should I make the changes in the *.m files
> and commit them before the C files?

No.

Zoltan.

------------------------------------------------------------------------

Implement the runtime system for region-based memory management. This includes
the implementation of regions, region instructions and support for
backtracking.

Support for backtracking deals with preventing the destruction of backward
live regions and provides instant reclaiming of space in regions when
backtracking reaches a resume point. This support now exploits the data
in rbmm_goal_info structures. The mechanisms are documented in the
papers/rbmm module of the Mercury repository.

compiler/code_info.m:
	Change the option to control the addition of region operations from
	use_region to region_analysis so that no region operations are
	introduced when compiling a compiler in .rbmm grade. This is temporary,
	as is the re-adding of --region-analysis option.
	
	Make use of rbmm_goal_info when generating backtrack-supporting code
	for commit operations.

compiler/commit_gen.m:
	Make use of rbmm_goal_info when generating backtrack-supporting code.

compiler/disj_gen.m:
	Make use of rbmm_goal_info when generating semidet disjunction.
	Correct one error so that use_region_disj_later is not generated in
	the code for the first disjunct.

compiler/ite_gen.m:
	Make use of rbmm_goal_info.

compiler/options.m:
	Modify the size of disj_protect(ion) to 1 instead of 2.

library/region_builtin.m:
	Change the region builtins to call to the correct region operations
	in the region runtime system.

	Add a predicate to print out profiling information for region-based
	memory management.

runtime/mercury_region.h
runtime/mercury_region.c
	New files containing the implementation of the region runtime system.

	This runtime system supports its own profiling and debugging messages,
	which can be turned on and off via the MR_RBMM_PROFILING and
	MR_RBMM_DEBUG flags.

	Note that these files are still in a state of flux.

runtime/mercury_types.h:
	Add typedefs needed by declarations in mercury_region.h.

runtime/mercury_conf_paramh:
	Document MR_RBMM_PROFILING and MR_RBMM_DEBUG.

runtime/mercury_imp.h:
	#include mercury_region.h in rbmm grades.

runtime/Mmakefile:
	Link the region runtime system into the runtime system of Mercury.

tests/tabling/Mmakefile:
	Avoid accidental matches on the "mm" in "rbmm".

cvs diff: Diffing .
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/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing boehm_gc/windows-untested
cvs diff: Diffing boehm_gc/windows-untested/vc60
cvs diff: Diffing boehm_gc/windows-untested/vc70
cvs diff: Diffing boehm_gc/windows-untested/vc71
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/code_info.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/code_info.m,v
retrieving revision 1.350
diff -u -b -r1.350 code_info.m
--- compiler/code_info.m	1 Oct 2007 04:06:47 -0000	1.350
+++ compiler/code_info.m	8 Oct 2007 05:11:04 -0000
@@ -535,7 +535,7 @@
     ),
     globals.lookup_bool_option(Globals, optimize_trail_usage, OptTrailOps),
     globals.lookup_bool_option(Globals, optimize_region_ops, OptRegionOps),
-    globals.lookup_bool_option(Globals, use_regions, UseRegions),
+    globals.lookup_bool_option(Globals, region_analysis, UseRegions),
     (
         UseRegions = yes,
         EmitRegionOps = add_region_ops
@@ -1343,8 +1343,8 @@
 :- type det_commit_info.
 
 :- pred prepare_for_det_commit(add_trail_ops::in, add_region_ops::in,
-    set(prog_var)::in, det_commit_info::out, code_tree::out,
-    code_info::in, code_info::out) is det.
+    set(prog_var)::in, hlds_goal_info::in, det_commit_info::out,
+    code_tree::out, code_info::in, code_info::out) is det.
 
 :- pred generate_det_commit(det_commit_info::in,
     code_tree::out, code_info::in, code_info::out) is det.
@@ -1360,8 +1360,8 @@
 :- type semi_commit_info.
 
 :- pred prepare_for_semi_commit(add_trail_ops::in, add_region_ops::in,
-    set(prog_var)::in, semi_commit_info::out, code_tree::out,
-    code_info::in, code_info::out) is det.
+    set(prog_var)::in, hlds_goal_info::in, semi_commit_info::out,
+    code_tree::out, code_info::in, code_info::out) is det.
 
 :- pred generate_semi_commit(semi_commit_info::in,
     code_tree::out, code_info::in, code_info::out) is det.
@@ -1976,7 +1976,7 @@
             ).
 
 prepare_for_det_commit(AddTrailOps, AddRegionOps, ForwardLiveVarsBeforeGoal,
-        DetCommitInfo, Code, !CI) :-
+        CommitGoalInfo, DetCommitInfo, Code, !CI) :-
     get_fail_info(!.CI, FailInfo0),
     FailInfo0 = fail_info(_, _, CurfrMaxfr, _, _),
     (
@@ -1994,7 +1994,8 @@
     ),
     maybe_save_trail_info(AddTrailOps, MaybeTrailSlots, SaveTrailCode, !CI),
     maybe_save_region_commit_frame(AddRegionOps, ForwardLiveVarsBeforeGoal,
-        MaybeRegionCommitFrameInfo, SaveRegionCommitFrameCode, !CI),
+        CommitGoalInfo, MaybeRegionCommitFrameInfo, SaveRegionCommitFrameCode,
+        !CI),
     DetCommitInfo = det_commit_info(MaybeMaxfrSlot, MaybeTrailSlots,
         MaybeRegionCommitFrameInfo),
     Code = tree_list([
@@ -2063,7 +2064,7 @@
             ).
 
 prepare_for_semi_commit(AddTrailOps, AddRegionOps, ForwardLiveVarsBeforeGoal,
-        SemiCommitInfo, Code, !CI) :-
+        CommitGoalInfo, SemiCommitInfo, Code, !CI) :-
     get_fail_info(!.CI, FailInfo0),
     FailInfo0 = fail_info(ResumePoints0, ResumeKnown, CurfrMaxfr, CondEnv,
         Allow),
@@ -2170,7 +2171,8 @@
     ),
     maybe_save_trail_info(AddTrailOps, MaybeTrailSlots, SaveTrailCode, !CI),
     maybe_save_region_commit_frame(AddRegionOps, ForwardLiveVarsBeforeGoal,
-        MaybeRegionCommitFrameInfo, SaveRegionCommitFrameCode, !CI),
+        CommitGoalInfo, MaybeRegionCommitFrameInfo, SaveRegionCommitFrameCode,
+        !CI),
     SemiCommitInfo = semi_commit_info(FailInfo0, NewResumePoint,
         HijackInfo, MaybeTrailSlots, MaybeRegionCommitFrameInfo),
     Code = tree_list([
@@ -2296,26 +2298,27 @@
 %---------------------------------------------------------------------------%
 
 :- pred maybe_save_region_commit_frame(add_region_ops::in, set(prog_var)::in,
-    maybe(region_commit_stack_frame)::out, code_tree::out,
+    hlds_goal_info::in, maybe(region_commit_stack_frame)::out, code_tree::out,
     code_info::in, code_info::out) is det.
 
-maybe_save_region_commit_frame(AddRegionOps, ForwardLiveVarsBeforeGoal,
-        MaybeRegionCommitFrameInfo, Code, !CI) :-
+maybe_save_region_commit_frame(AddRegionOps, _ForwardLiveVarsBeforeGoal,
+        CommitGoalInfo, MaybeRegionCommitFrameInfo, Code, !CI) :-
     (
         AddRegionOps = do_not_add_region_ops,
         MaybeRegionCommitFrameInfo = no,
         Code = empty
     ;
         AddRegionOps = add_region_ops,
-        RegionVars = filter_region_vars(!.CI, ForwardLiveVarsBeforeGoal),
-
-        % XXX RemovedRegionVars should be the set of region vars whose
-        % regions are removed in the scope. However, this information
-        % is not yet available in the HLDS, and there is no simple way here
-        % to reconstruct it.
-        RemovedRegionVars = RegionVars,
+        MaybeRbmmInfo = goal_info_get_maybe_rbmm(CommitGoalInfo),
+        (
+            MaybeRbmmInfo = no,
+            MaybeRegionCommitFrameInfo = no,
+            Code = empty
+        ;
+            MaybeRbmmInfo = yes(RbmmInfo),
+            RbmmInfo = rbmm_goal_info(_, CommitRemovedRegionVars, _, _, _),
 
-        RemovedRegionVarList = set.to_sorted_list(RemovedRegionVars),
+            RemovedRegionVarList = set.to_sorted_list(CommitRemovedRegionVars),
 
         NumRemovedRegionVars = list.length(RemovedRegionVarList),
 
@@ -2330,8 +2333,8 @@
             StackVars, MainStackId, FirstSlotNum, LastSlotNum, !CI),
         EmbeddedStackFrame = embedded_stack_frame_id(MainStackId,
             FirstSlotNum, LastSlotNum),
-        FirstSavedRegionAddr =
-            first_nonfixed_embedded_slot_addr(EmbeddedStackFrame, FixedSize),
+            FirstSavedRegionAddr = first_nonfixed_embedded_slot_addr(
+                EmbeddedStackFrame, FixedSize),
         acquire_reg(reg_r, NumRegLval, !CI),
         acquire_reg(reg_r, AddrRegLval, !CI),
         PushInitCode = node([
@@ -2343,7 +2346,8 @@
                 "Initialize number of unprotected live regions"),
             llds_instr(
                 assign(AddrRegLval, FirstSavedRegionAddr),
-                "Initialize pointer to the next unprotected live region slot")
+                    "Initialize pointer to the next unprotected live" ++
+                    " region slot")
         ]),
         save_unprotected_live_regions(NumRegLval, AddrRegLval,
             EmbeddedStackFrame, RemovedRegionVarList, FillCode, !CI),
@@ -2356,8 +2360,8 @@
         release_reg(NumRegLval, !CI),
         release_reg(AddrRegLval, !CI),
 
-        RegionCommitFrameInfo = region_commit_stack_frame(EmbeddedStackFrame,
-            StackVars),
+            RegionCommitFrameInfo =
+                region_commit_stack_frame(EmbeddedStackFrame, StackVars),
         MaybeRegionCommitFrameInfo = yes(RegionCommitFrameInfo),
 
         Code = tree_list([
@@ -2365,6 +2369,7 @@
             FillCode,
             SetCode
         ])
+        )
     ).
 
 :- pred save_unprotected_live_regions(lval::in, lval::in,
Index: compiler/commit_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/commit_gen.m,v
retrieving revision 1.19
diff -u -b -r1.19 commit_gen.m
--- compiler/commit_gen.m	27 Sep 2007 10:42:05 -0000	1.19
+++ compiler/commit_gen.m	8 Oct 2007 05:11:04 -0000
@@ -82,7 +82,8 @@
         ;
             InnerCodeModel = model_non,
             prepare_for_det_commit(AddTrailOps, AddRegionOps,
-                ForwardLiveVarsBeforeGoal, CommitInfo, PreCommit, !CI),
+                ForwardLiveVarsBeforeGoal, InnerGoalInfo, CommitInfo,
+                PreCommit, !CI),
             code_gen.generate_goal(InnerCodeModel, Goal, GoalCode, !CI),
             generate_det_commit(CommitInfo, Commit, !CI),
             Code = tree_list([PreCommit, GoalCode, Commit])
@@ -98,7 +99,8 @@
         ;
             InnerCodeModel = model_non,
             prepare_for_semi_commit(AddTrailOps, AddRegionOps,
-                ForwardLiveVarsBeforeGoal, CommitInfo, PreCommit, !CI),
+                ForwardLiveVarsBeforeGoal, InnerGoalInfo, CommitInfo,
+                PreCommit, !CI),
             code_gen.generate_goal(InnerCodeModel, Goal, GoalCode, !CI),
             generate_semi_commit(CommitInfo, Commit, !CI),
             Code = tree_list([PreCommit, GoalCode, Commit])
Index: compiler/disj_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/disj_gen.m,v
retrieving revision 1.105
diff -u -b -r1.105 disj_gen.m
--- compiler/disj_gen.m	27 Sep 2007 10:42:05 -0000	1.105
+++ compiler/disj_gen.m	9 Oct 2007 07:43:28 -0000
@@ -383,19 +383,35 @@
         SaveHpCode = empty,
         MaybeHpSlot = no,
 
-        % XXX The condition should succeed only if some disjunct performs
-        % some region operations (allocation or removal). The HLDS does not yet
-        % contain the information we need to decide whether this is the case.
-        ( semidet_succeed ->
-            maybe_create_disj_region_frame(AddRegionOps, DisjGoalInfo,
-                FirstRegionCode, LaterRegionCode, LastRegionCode,
-                RegionStackVars, !CI),
-            RegionStackVarsToRelease = RegionStackVars
+        MaybeRbmmInfo = goal_info_get_maybe_rbmm(DisjGoalInfo),
+        (
+            MaybeRbmmInfo = no,
+            FirstRegionCode = empty,
+            LaterRegionCode = empty,
+            LastRegionCode = empty,
+            RegionStackVarsToRelease = []
         ;
+            MaybeRbmmInfo = yes(RbmmInfo),
+            RbmmInfo = rbmm_goal_info(DisjCreatedRegionVars,
+                DisjRemovedRegionVars, _DisjCarriedRegionVars,
+                DisjAllocRegionVars, _DisjUsedRegionVars),
+            (
+                set.empty(DisjCreatedRegionVars),
+                set.empty(DisjRemovedRegionVars),
+                set.empty(DisjAllocRegionVars)
+            ->
             FirstRegionCode = empty,
             LaterRegionCode = empty,
             LastRegionCode = empty,
             RegionStackVarsToRelease = []
+            ;
+                % We only need region support for backtracking if some disjunct
+                % performs some region operations (allocation or removal).
+                maybe_create_disj_region_frame(AddRegionOps, DisjGoalInfo,
+                    FirstRegionCode, LaterRegionCode, LastRegionCode,
+                    RegionStackVars, !CI),
+                RegionStackVarsToRelease = RegionStackVars
+            )
         )
     ),
 
@@ -475,11 +491,13 @@
 
             % Reset the solver state if necessary.
             maybe_reset_ticket(MaybeTicketSlot, reset_reason_undo,
-                RestoreTicketCode)
+                RestoreTicketCode),
+            ThisDisjunctRegionCode = LaterRegionCode
         ;
             MaybeEntryResumePoint = no,
             RestoreHpCode = empty,
-            RestoreTicketCode = empty
+            RestoreTicketCode = empty,
+            ThisDisjunctRegionCode = empty
         ),
 
         % The pre_goal_update sanity check insists on no_resume_point, to make
@@ -581,7 +599,7 @@
             RestoreHpCode,
             RestoreTicketCode,
             SaveHpCode,
-            LaterRegionCode,
+            ThisDisjunctRegionCode,
             ModContCode,
             TraceCode,
             GoalCode,
Index: compiler/ite_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ite_gen.m,v
retrieving revision 1.102
diff -u -b -r1.102 ite_gen.m
--- compiler/ite_gen.m	1 Oct 2007 04:06:48 -0000	1.102
+++ compiler/ite_gen.m	9 Oct 2007 00:20:06 -0000
@@ -559,32 +559,44 @@
         get_forward_live_vars(!.CI, ForwardLiveVars),
         LiveRegionVars = filter_region_vars(!.CI, ForwardLiveVars),
 
-        CondNonLocals = goal_info_get_nonlocals(CondGoalInfo),
-        CondNonlocalRegionVars = filter_region_vars(!.CI, CondNonLocals),
-
-        % XXX CondRemovedRegionVars should be the set of region vars whose
-        % regions are removed in the condition, and CondAllocRegionVars should
-        % be the set of region vars whose regions may be allocated into in the
-        % condition. However, this information is not yet available in the
-        % HLDS, and there is no simple way here to reconstruct it.
-        % (For example, the set of region vars live after the condition
-        % is *not* sufficient to compute CondRemovedRegionVars, since
-        % a region variable can become dead (in the absence of further
-        % references to the region in this procedure) even if the associated
-        % region hasn't been removed.
-        CondRemovedRegionVars = CondNonlocalRegionVars,
-        CondAllocRegionVars = CondNonlocalRegionVars,
-
-        get_module_info(!.CI, ModuleInfo),
+        MaybeRbmmInfo = goal_info_get_maybe_rbmm(CondGoalInfo),
+        (
+            MaybeRbmmInfo = no,
+            CondCode = empty,
+            ThenCode = empty,
+            ElseCode = empty,
+            StackVars = [],
+            MaybeEmbeddedStackFrameId = no
+        ;
+            MaybeRbmmInfo = yes(RbmmInfo),
+            RbmmInfo = rbmm_goal_info(CondCreatedRegionVars,
+                CondRemovedRegionVars, CondCarriedRegionVars, 
+                CondAllocRegionVars, _CondUsedRegionVars),
+            (
+                set.empty(CondCreatedRegionVars),
+                set.empty(CondRemovedRegionVars),
+                set.empty(CondAllocRegionVars)
+            ->
+                % When no region-related operations occur in the
+                % condition we do not need the backtracking support code.
+                CondCode = empty,
+                ThenCode = empty,
+                ElseCode = empty,
+                StackVars = [],
+                MaybeEmbeddedStackFrameId = no
+            ;
+                code_info.get_module_info(!.CI, ModuleInfo),
         find_regions_removed_at_start_of_else(ElseGoals, ModuleInfo,
             set.init, RemovedAtStartOfElse),
 
-        % XXX We want to compute UnprotectedRemovedAtStartOfElse as the
-        % intersection of RemovedAtStartOfElse and the set of region variables
-        % whose regions are statically known to be unprotected at this point in
-        % the code. However, in the absence of the required program analysis,
-        % we can't know of any statically unprotected regions.
-        UnprotectedRemovedAtStartOfElse = set.init,
+                % The UnprotectedRemovedAtStartOfElse is the
+                % intersection of RemovedAtStartOfElse and the set of region
+                % variables whose regions are statically known to be
+                % unprotected at this point in the code. These are actually
+                % carried regions because carried region are statically known
+                % to be not protected by the condition.
+                UnprotectedRemovedAtStartOfElse = set.intersect(
+                    RemovedAtStartOfElse, CondCarriedRegionVars),
 
         ProtectRegionVars = set.intersect(LiveRegionVars,
             CondRemovedRegionVars),
@@ -603,13 +615,13 @@
         list.length(ProtectRegionVarList, NumProtectRegionVars),
         list.length(SnapshotRegionVarList, NumSnapshotRegionVars),
 
-        get_globals(!.CI, Globals),
+                code_info.get_globals(!.CI, Globals),
         globals.lookup_int_option(Globals, size_region_ite_fixed,
             FixedSize),
         globals.lookup_int_option(Globals, size_region_ite_protect,
             ProtectSize),
-        globals.lookup_int_option(Globals, size_region_ite_snapshot,
-            SnapshotSize),
+                globals.lookup_int_option(Globals,
+                    size_region_ite_snapshot, SnapshotSize),
         FrameSize = FixedSize
             + ProtectSize * NumProtectRegionVars
             + SnapshotSize * NumSnapshotRegionVars,
@@ -619,14 +631,15 @@
             StackVars, MainStackId, FirstSlotNum, LastSlotNum, !CI),
         EmbeddedStackFrameId = embedded_stack_frame_id(MainStackId,
             FirstSlotNum, LastSlotNum),
-        FirstNonFixedAddr =
-            first_nonfixed_embedded_slot_addr(EmbeddedStackFrameId, FixedSize),
+                FirstNonFixedAddr = first_nonfixed_embedded_slot_addr(
+                    EmbeddedStackFrameId, FixedSize),
         acquire_reg(reg_r, ProtectNumRegLval, !CI),
         acquire_reg(reg_r, SnapshotNumRegLval, !CI),
         acquire_reg(reg_r, AddrRegLval, !CI),
         PushInitCode = node([
             llds_instr(
-                push_region_frame(region_stack_ite, EmbeddedStackFrameId),
+                        push_region_frame(region_stack_ite,
+                            EmbeddedStackFrameId),
                 "Save stack pointer of embedded region ite stack"),
             llds_instr(
                 assign(ProtectNumRegLval, const(llconst_int(0))),
@@ -636,14 +649,15 @@
                 "Initialize number of snapshot_infos"),
             llds_instr(
                 assign(AddrRegLval, FirstNonFixedAddr),
-                "Initialize pointer to nonfixed part of embedded frame")
+                        "Initialize pointer to nonfixed part of" ++
+                        " embedded frame")
         ]),
         ite_protect_regions(ProtectNumRegLval, AddrRegLval,
-            EmbeddedStackFrameId, ProtectRegionVarList, ProtectRegionCode,
-            !CI),
+                    EmbeddedStackFrameId, ProtectRegionVarList,
+                    ProtectRegionCode, !CI),
         ite_alloc_snapshot_regions(SnapshotNumRegLval, AddrRegLval,
-            EmbeddedStackFrameId, RemovedAtStartOfElse, SnapshotRegionVarList,
-            SnapshotRegionCode, !CI),
+                    EmbeddedStackFrameId, RemovedAtStartOfElse,
+                    SnapshotRegionVarList, SnapshotRegionCode, !CI),
         SetCode = node([
             llds_instr(
                 region_set_fixed_slot(region_set_ite_num_protects,
@@ -669,7 +683,8 @@
             MaybeEmbeddedStackFrameId = no
         ;
             CondCodeModel = model_det,
-            unexpected(this_file, "maybe_create_ite_region_frame: det cond")
+                    unexpected(this_file,
+                        "maybe_create_ite_region_frame: det cond")
         ),
 
         CondCode = tree_list([
@@ -680,23 +695,28 @@
         ]),
         ThenCode = node([
             llds_instr(
-                use_and_maybe_pop_region_frame(region_ite_then(CondKind),
+                        use_and_maybe_pop_region_frame(
+                            region_ite_then(CondKind),
                     EmbeddedStackFrameId),
                 "region enter then")
         ]),
         ElseCode = node([
             llds_instr(
-                use_and_maybe_pop_region_frame(region_ite_else(CondKind),
+                        use_and_maybe_pop_region_frame(
+                            region_ite_else(CondKind),
                     EmbeddedStackFrameId),
                 "region enter else")
         ])
 
-        % XXX A model_non condition can succeed more than once, so the
-        % region_ite_then(region_ite_nondet_cond) operation cannot pop
-        % the ite stack frame. We need to pop this frame when the condition
-        % fails *after* succeeding at least once. This requires modifying the
-        % failure continuation and/or the resume point. This has not yet been
-        % implemented.
+                % XXX A model_non condition can succeed more than once, so
+                % the region_ite_then(region_ite_nondet_cond) operation
+                % cannot pop the ite stack frame. We need to pop this
+                % frame when the condition fails *after* succeeding at
+                % least once. This requires modifying the failure
+                % continuation and/or the resume point. This has not yet
+                % been implemented.
+            )
+        )
     ).
 
     % Given the list of goals in the else branch, accumulate the region
Index: compiler/options.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.587
diff -u -b -r1.587 options.m
--- compiler/options.m	4 Oct 2007 09:04:43 -0000	1.587
+++ compiler/options.m	8 Oct 2007 05:11:04 -0000
@@ -1204,7 +1204,7 @@
     size_region_commit_fixed            -   int(3),
     size_region_ite_protect             -   int(1),
     size_region_ite_snapshot            -   int(4),
-    size_region_disj_protect            -   int(2),
+    size_region_disj_protect            -   int(1),
     size_region_disj_snapshot           -   int(4),
     size_region_commit_entry            -   int(1)
 ]).
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing debian/patches
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
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/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
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/log4m
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/mopenssl
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/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
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/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
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/region_builtin.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/region_builtin.m,v
retrieving revision 1.1
diff -u -b -r1.1 region_builtin.m
--- library/region_builtin.m	12 Jun 2007 03:22:25 -0000	1.1
+++ library/region_builtin.m	8 Oct 2007 08:53:52 -0000
@@ -24,6 +24,8 @@
 :- module region_builtin.
 :- interface.
 
+:- import_module io.
+
 %-----------------------------------------------------------------------------%
 
     % A pointer to a memory region.
@@ -38,30 +40,49 @@
     %
 :- impure pred remove_region(region::in) is det.
 
+:- pred print_rbmm_profiling_info(io::di, io::uo) is det.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
 :- implementation.
 
-% XXX the following definitions are just placeholders.  When runtime
-% support for RBMM is introduced they will be changed.
+:- pragma foreign_decl("C", "#include ""mercury_region.h""").
 
-:- type region == c_pointer.
+:- pragma foreign_type("C", region, "MR_Region *",
+    [can_pass_as_mercury_type]).
 
 :- pragma foreign_proc("C",
     create_region(Region::out),
     [will_not_call_mercury],
 "
-    /* Region */
-    MR_fatal_error(\"region_builtin.create_region/1 NYI.\");
+#ifdef MR_USE_REGIONS
+    Region = MR_region_create_region();
+#else
+    MR_fatal_error(""create_region: non-rbmm grade"");
+#endif
 ").
 
 :- pragma foreign_proc("C",
     remove_region(Region::in),
     [will_not_call_mercury],
 "
-    /* Region */
-    MR_fatal_error(\"region_builtin.remove_region/1 NYI.\");
+#ifdef MR_USE_REGIONS
+    MR_region_remove_region(Region);
+#else
+    MR_fatal_error(""remove_region: non-rbmm grade"");
+#endif
+").
+
+:- pragma foreign_proc("C",
+    print_rbmm_profiling_info(_IO0::di, _IO::uo),
+    [will_not_call_mercury, promise_pure],
+"
+#ifdef MR_USE_REGIONS
+    MR_region_print_profiling_info();
+#else
+    MR_fatal_error(""print_rbmm_profiling_info: non-rbmm grade"");
+#endif
 ").
 
 %-----------------------------------------------------------------------------%
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
Index: runtime/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/Mmakefile,v
retrieving revision 1.142
diff -u -b -r1.142 Mmakefile
--- runtime/Mmakefile	3 Oct 2007 12:11:57 -0000	1.142
+++ runtime/Mmakefile	8 Oct 2007 05:11:04 -0000
@@ -73,6 +73,7 @@
 			mercury_prof_mem.h	\
 			mercury_prof_time.h	\
 			mercury_profiling_builtin.h	\
+			mercury_region.h	\
 			mercury_regs.h		\
 			mercury_reg_workarounds.h	\
 			mercury_runtime_util.h	\
@@ -178,6 +179,7 @@
 			mercury_profiling_builtin.c	\
 			mercury_prof_mem.c	\
 			mercury_prof_time.c	\
+			mercury_region.c	\
 			mercury_regs.c		\
 			mercury_reg_workarounds.c	\
 			mercury_runtime_util.c	\
Index: runtime/mercury_conf_param.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_conf_param.h,v
retrieving revision 1.99
diff -u -b -r1.99 mercury_conf_param.h
--- runtime/mercury_conf_param.h	13 Sep 2007 04:40:51 -0000	1.99
+++ runtime/mercury_conf_param.h	8 Oct 2007 06:02:23 -0000
@@ -304,8 +304,16 @@
 **	representations of all the terms reachable from the stack.
 **
 ** MR_STM_DEBUG
-**	Enabled low-level debugging messages from the code that implements
+**	Enables low-level debugging messages from the code that implements
 **	transactions used by software transactional memory.
+**
+** MR_RBMM_DEBUG
+**	Enables low-level debugging messages from the code that implements
+**	region-based memory management.
+**
+** MR_RBMM_PROFILING
+**	Enables low-level profiling messages from the code that implements
+**	region-based memory management.
 */
 
 /*
Index: runtime/mercury_imp.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_imp.h,v
retrieving revision 1.26
diff -u -b -r1.26 mercury_imp.h
--- runtime/mercury_imp.h	24 Feb 2006 07:11:20 -0000	1.26
+++ runtime/mercury_imp.h	8 Oct 2007 05:16:19 -0000
@@ -81,6 +81,7 @@
 #include	"mercury_prof.h"
 #include	"mercury_misc.h"
 
+#include	"mercury_region.h"
 #include	"mercury_tabling.h"
 #ifdef MR_USE_MINIMAL_MODEL_STACK_COPY
 #include	"mercury_minimal_model.h"
Index: runtime/mercury_region.c
===================================================================
RCS file: runtime/mercury_region.c
diff -N runtime/mercury_region.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ runtime/mercury_region.c	8 Oct 2007 08:54:49 -0000
@@ -0,0 +1,930 @@
+/*
+** vim:sw=4 ts=4 expandtab
+*/
+/*
+** Copyright (C) 2007 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: mercury_region.c
+** main author: qph
+*/
+
+#include "mercury_imp.h"
+#include "mercury_region.h"
+
+#ifdef MR_USE_REGIONS
+
+#define word_sizeof(s) (sizeof(s) / sizeof(MR_Word))
+
+MR_RegionPage       *MR_region_free_page_list;
+MR_Region           *MR_live_region_list;
+
+MR_Word             *MR_region_ite_sp = NULL;
+MR_Word             *MR_region_disj_sp = NULL;
+MR_Word             *MR_region_commit_sp = NULL;
+
+MR_Word             MR_region_sequence_number = 1;
+
+#if defined(MR_RBMM_PROFILING)
+
+MR_RegionProfUnit   MR_rbmmp_words_used = {0, 0, 0};
+MR_RegionProfUnit   MR_rbmmp_regions_used = {0, 0, 0};
+MR_RegionProfUnit   MR_rbmmp_pages_used = {0, 0, 0};
+unsigned int        MR_rbmmp_pages_requested = 0;
+unsigned int        MR_rbmmp_biggest_region_size = 0;
+MR_RegionProfUnit   MR_rbmmp_regions_saved_at_commit = {0, 0, 0};
+unsigned int        MR_rbmmp_regions_protected_at_ite;
+unsigned int        MR_rbmmp_snapshots_saved_at_ite;
+unsigned int        MR_rbmmp_regions_protected_at_disj;
+unsigned int        MR_rbmmp_snapshots_saved_at_disj;
+double              MR_rbmmp_page_utilized;
+
+#endif
+
+/* Request for more pages from the operating system. */
+static MR_RegionPage    *MR_region_request_pages(void);
+
+/* Take a page from the free page list. */
+static MR_RegionPage    *MR_region_get_free_page(void);
+
+static void             MR_region_nullify_entries_in_commit_stack(
+                            MR_Region *region);
+static void             MR_region_nullify_in_commit_frame(MR_Word *frame,
+                            MR_Region *region);
+static void             MR_region_nullify_in_ite_frame(MR_Region *region);
+
+static void             MR_region_extend_region(MR_Region *);
+
+#ifdef  MR_RBMM_DEBUG
+static int              MR_region_get_frame_number(MR_Word *);
+#endif
+
+#ifdef  MR_RBMM_PROFILING
+static void             MR_region_print_profiling_unit(const char *str,
+                            MR_RegionProfUnit *profiling_unit);
+#endif
+
+/*---------------------------------------------------------------------------*/
+/* Page operations. */
+
+static MR_RegionPage *
+MR_region_request_pages()
+{
+    MR_RegionPage   *pages;
+    int             bytes_to_request;
+    int             i;
+
+    bytes_to_request = MR_REGION_NUM_PAGES_TO_REQUEST * sizeof(MR_RegionPage);
+    pages = (MR_RegionPage *) MR_malloc(bytes_to_request);
+    if (pages == NULL) {
+        MR_fatal_error("Cannot request more memory from the operating system");
+    }
+
+    pages[0].MR_regionpage_next = NULL;
+    for (i = 1; i < MR_REGION_NUM_PAGES_TO_REQUEST; i++) {
+        pages[i].MR_regionpage_next = &pages[i - 1];
+    }
+
+#if defined(MR_RBMM_PROFILING)
+    MR_rbmmp_pages_requested += MR_REGION_NUM_PAGES_TO_REQUEST;
+#endif
+
+    return &(pages[MR_REGION_NUM_PAGES_TO_REQUEST - 1]);
+}
+
+static MR_RegionPage *
+MR_region_get_free_page(void)
+{
+    MR_RegionPage   *page;
+
+    if (MR_region_free_page_list == 0) {
+        MR_region_free_page_list = MR_region_request_pages();
+    }
+
+    page = MR_region_free_page_list;
+    MR_region_free_page_list = MR_region_free_page_list->MR_regionpage_next;
+    /* Disconnect the first free page from the free list. */
+    page->MR_regionpage_next = NULL;
+
+#if defined(MR_RBMM_PROFILING)
+    MR_region_update_profiling_unit(&MR_rbmmp_pages_used, 1);
+#endif
+
+    return page;
+}
+
+/*---------------------------------------------------------------------------*/
+/*
+** Region operations.
+*/
+
+/*
+** Create a region.
+** The MR_REGION_PAGE_SPACE_SIZE must be larger than the size of
+** Region_Struct.
+*/
+
+MR_Region *
+MR_region_create_region(void)
+{
+    MR_RegionPage   *page;
+    MR_Region       *region;
+
+    /* This is the first page of the region. */
+    page = MR_region_get_free_page();
+
+    /*
+    ** In the first page we will store region information, which occupies
+    ** word_sizeof(MR_Region) words from the start of the first page.
+    */
+    region = (MR_Region *) (page->MR_regionpage_space);
+    region->MR_region_next_available_word = (MR_Word *)
+        (page->MR_regionpage_space + word_sizeof(MR_Region));
+    region->MR_region_last_page = page;
+    region->MR_region_available_space =
+        MR_REGION_PAGE_SPACE_SIZE - word_sizeof(MR_Region);
+    region->MR_region_removal_counter = 1;
+    region->MR_region_sequence_number = MR_region_sequence_number++;
+    region->MR_region_logical_removed = 0;
+    region->MR_region_ite_protected = NULL;
+    region->MR_region_disj_protected = NULL;
+    region->MR_region_commit_frame = NULL;
+    region->MR_region_destroy_at_commit = 0;
+
+    /* Add the region to the head of the live region list. */
+    if (MR_live_region_list != NULL) {
+        MR_live_region_list->MR_region_previous_region = region;
+    }
+    region->MR_region_next_region = MR_live_region_list;
+    region->MR_region_previous_region = NULL;
+    MR_live_region_list = region;
+
+#if defined(MR_RBMM_DEBUG)
+    MR_region_debug_create_region(region);
+#endif
+
+#if defined(MR_RBMM_PROFILING)
+    MR_region_update_profiling_unit(&MR_rbmmp_regions_used, 1);
+    ((MR_RegionPage *) region)->MR_regionpage_allocated_size = 0;
+#endif
+
+    return region;
+}
+
+static void
+MR_region_nullify_entries_in_commit_stack(MR_Region *region)
+{
+    MR_Word *frame;
+
+    frame = region->MR_region_commit_frame;
+    while (frame != NULL) {
+        MR_region_nullify_in_commit_frame(frame, region);
+        frame = (MR_Word *) *frame;
+    }
+}
+
+static void
+MR_region_nullify_in_commit_frame(MR_Word *frame, MR_Region *region)
+{
+    MR_Word *saved_region;
+    int     num_saved_regions;
+    int     i;
+
+    num_saved_regions = *(frame + MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);
+    saved_region = frame + MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION;
+
+    /*
+    ** Loop through the saved regions and nullify the entry of the input
+    ** region if found.
+    */
+    for (i = 0; i < num_saved_regions; i++) {
+        if ((MR_Region *) (*saved_region) == region) {
+            (*saved_region) = (MR_Word) NULL;
+            break;
+        } else {
+            saved_region += 1;
+        }
+    }
+}
+
+static void
+MR_region_nullify_in_ite_frame(MR_Region *region)
+{
+    MR_Word *ite_frame;
+    MR_Word *protected_region;
+    int     num_protected_regions;
+    int     i;
+
+    ite_frame = region->MR_region_ite_protected;
+    num_protected_regions = * ((MR_Word *)
+        (ite_frame + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS));
+    protected_region = ite_frame + MR_REGION_FRAME_FIXED_SIZE;
+
+    /*
+    ** Loop through the protected regions and nullify the entry of the input
+    ** region if found.
+    */
+    for (i = 0; i < num_protected_regions; i++) {
+        if ((MR_Region *) (*protected_region) == region) {
+            (*protected_region) = (MR_Word) NULL;
+            break;
+        } else {
+            protected_region += 1;
+        }
+    }
+}
+
+void
+MR_region_destroy_region(MR_Region *region)
+{
+    MR_region_debug_destroy_region(region);
+
+    if (region->MR_region_commit_frame != NULL) {
+        MR_region_nullify_entries_in_commit_stack(region);
+    }
+
+    /* Break the region from the live region list. */
+    if (region == MR_live_region_list) {
+        /* Detach the newest. */
+        MR_live_region_list = region->MR_region_next_region;
+    } else {
+        region->MR_region_previous_region->MR_region_next_region =
+            region->MR_region_next_region;
+        if (region->MR_region_next_region != NULL) {
+            /* Detach one in the middle. */
+            region->MR_region_next_region->MR_region_previous_region =
+                region->MR_region_previous_region;
+        }
+    }
+
+    /* Return the page list of the region to the free page list. */
+    MR_region_return_page_list((MR_RegionPage *) region,
+        region->MR_region_last_page);
+
+    /* Collect profiling information. */
+    MR_region_profile_destroyed_region(region);
+}
+
+/*
+** This method is to be called at the start of the then part of an ite with
+** semidet condition (most of the times).
+** At that point we will only check if the region is disj-protected or not.
+*/
+
+void
+MR_remove_undisjprotected_region_ite_then_semidet(MR_Region *region)
+{
+    MR_region_debug_try_remove_region(region);
+    if (region->MR_region_disj_protected == NULL) {
+        MR_region_destroy_region(region);
+    } else {
+        region->MR_region_logical_removed = 1;
+
+#if defined(MR_RBMM_DEBUG)
+        MR_region_logically_remove_region_msg(region);
+#endif
+    }
+}
+
+/*
+** This method is to be called at the start of the then part of an ite with
+** nondet condition.
+** We will destroy the region if it is not disj-protected and we will also
+** nullify its entry in the ite frame.
+*/
+
+void
+MR_remove_undisjprotected_region_ite_then_nondet(MR_Region *region)
+{
+    MR_region_debug_try_remove_region(region);
+
+    if (region->MR_region_disj_protected == NULL) {
+        MR_region_nullify_in_ite_frame(region);
+        MR_region_destroy_region(region);
+    } else {
+        region->MR_region_logical_removed = 1;
+
+#if defined(MR_RBMM_DEBUG)
+        MR_region_logically_remove_region_msg(region);
+#endif
+    }
+}
+
+void
+MR_region_remove_region(MR_Region *region)
+{
+    MR_region_debug_try_remove_region(region);
+
+    if (region->MR_region_ite_protected == NULL &&
+        region->MR_region_disj_protected == NULL)
+    {
+        MR_region_destroy_region(region);
+    } else {
+        region->MR_region_logical_removed = 1;
+
+        /*
+        ** This means this logical removal happens in the condition of an
+        ** if-then-else and this region is protected by the if-then-else, so
+        ** we "ite-unprotect" it.
+        if (region->ite_protected != NULL) {
+            region->ite_protected = (MR_Word *) (*MR_region_ite_sp);
+        } else {}
+        */
+
+        /*
+        ** The region is saved at a commit frame, and this logical removal
+        ** happens in the commit context. So we can and need to destroy the
+        ** region at commit point.
+        */
+        if (region->MR_region_commit_frame != NULL) {
+            region->MR_region_destroy_at_commit = 1;
+        }
+
+#if defined(MR_RBMM_DEBUG)
+        MR_region_logically_remove_region_msg(region);
+#endif
+    }
+}
+
+MR_Word *
+MR_region_alloc(MR_Region *region, unsigned int words)
+{
+    MR_Word *allocated_cell;
+
+    if (region->MR_region_available_space < words) {
+        MR_region_extend_region(region);
+    }
+
+    allocated_cell = region->MR_region_next_available_word;
+    /* Allocate in the increasing direction of address. */
+    region->MR_region_next_available_word += words;
+    region->MR_region_available_space -= words;
+#if defined(MR_RBMM_PROFILING)
+    MR_region_update_profiling_unit(&MR_rbmmp_words_used, words);
+    ((MR_RegionPage *) region)->MR_regionpage_allocated_size += words;
+#endif
+
+    return allocated_cell;
+}
+
+static void
+MR_region_extend_region(MR_Region *region)
+{
+    MR_RegionPage   *page;
+
+    page = MR_region_get_free_page();
+    region->MR_region_last_page->MR_regionpage_next = page;
+    region->MR_region_last_page = page;
+    /* XXX Why the cast? */
+    region->MR_region_next_available_word = (MR_Word *)
+        page->MR_regionpage_space;
+    region->MR_region_available_space = MR_REGION_PAGE_SPACE_SIZE;
+}
+
+/* Destroy any marked regions allocated before scope entry. */
+void
+MR_destroy_marked_old_regions_at_commit(MR_Word number_of_saved_regions,
+    MR_Word *first_saved_region_slot)
+{
+    MR_Region   *region;
+    int         i;
+
+    for (i = 0; i < number_of_saved_regions; i++) {
+        region = (MR_Region *)
+            *(first_saved_region_slot + i * MR_REGION_COMMIT_ENTRY_SIZE);
+        if (region != NULL) {
+            /*
+            ** The region is saved here and has not been destroyed.
+            ** XXX If we save only regions that are live at entry and not live
+            ** at exit, at commit it should be the case that a logical removal
+            ** has happened to the region, i.e., destroy_at_commit = 1. So just
+            ** need to destroy it at commit. The check and the else below are
+            ** redundant.
+            */
+            if (region->MR_region_destroy_at_commit) {
+                /*
+                ** Logical removal happens to the region in the commit
+                ** context. So destroy it at commit.
+                */
+                MR_region_destroy_region(region);
+            } else {
+                /*
+                ** The saved region is not removed in this commit context.
+                ** We need to update the commit context that R may be saved
+                ** after this frame is discarded.
+                ** The reason here is that if R is saved at this
+                ** current frame and also saved at any other frames, it must
+                ** be saved at the previous frame of this frame.
+                */
+                /*
+                region->MR_region_commit_frame =
+                    (MR_Word *) (*(region->MR_region_commit_frame));
+                */
+                MR_fatal_error("MR_destroy_marked_old_regions_at_commit: "
+                    "need to rethink.");
+            }
+        }
+    }
+}
+
+/* Destroy any marked regions allocated since scope entry. */
+void
+MR_destroy_marked_new_regions_at_commit(MR_Word saved_region_seq_number)
+{
+    MR_Region   *region;
+
+    region = MR_live_region_list;
+    while (region != NULL &&
+        region->MR_region_sequence_number > saved_region_seq_number)
+    {
+        if (region->MR_region_destroy_at_commit) {
+            MR_region_destroy_region(region);
+        } else {
+            region = region->MR_region_next_region;
+        }
+    }
+}
+
+#if 0
+static void restore_region(MR_Snapshot *);
+static void shrink_region(MR_Region *);
+
+/*
+** Shrink the region to the size which has been saved to the
+** snapshot list of the topmost nondet frame (maxfr).
+*/
+
+static void
+shrink_region(MR_Region *region) {
+    if (region->nondet_frame_of_newest_snapshot == nondet_maxfr) {
+        MR_Snapshot *snapshot = (MR_Snapshot *) region->newest_snapshot;
+        restore_region(snapshot);
+    }
+}
+
+/* Restore a region to a state saved in the snapshot. */
+static void
+restore_region(MR_Snapshot *snapshot) {
+    MR_Region *region = snapshot->MR_snapshot_region;
+    /* Return the list of pages added since the save to the global free
+    ** page list.
+    */
+    region->last_page->MR_regionpage_next = MR_region_free_page_list;
+    MR_region_free_page_list =
+        snapshot->MR_snapshot_saved_last_page->MR_regionpage_next;
+
+    /* Disconnect the saved last page (i.e., the last page of the restored
+    ** region) from the free list.
+    */
+    snapshot->MR_snapshot_saved_last_page->MR_regionpage_next = NULL;
+
+    /* Restore the saved region. */
+    region->last_page = snapshot->MR_snapshot_saved_last_page;
+    region->next_available_word =
+        snapshot->MR_snapshot_saved_next_available_word;
+    region->available_space = snapshot->MR_snapshot_saved_available_space;
+    region->removal_counter = snapshot->MR_snapshot_saved_removal_counter;
+}
+#endif
+
+/*---------------------------------------------------------------------------*/
+/* Debugging messages for RBMM. */
+
+#ifdef MR_RBMM_DEBUG
+
+static int
+MR_region_get_frame_number(MR_Word *frame)
+{
+    int frame_number;
+
+    frame_number = 0;
+    while (frame != NULL) {
+        frame_number++;
+        frame = (MR_Word *) (*frame);
+    }
+
+    return frame_number;
+}
+
+void
+MR_region_create_region_msg(MR_Region *region)
+{
+    printf("Create region #%d:\n", region->MR_region_sequence_number);
+    printf("\tHandle: %d\n", region);
+}
+
+void
+MR_region_try_remove_region_msg(MR_Region *region)
+{
+    printf("Try removing region ");
+    MR_region_region_struct_removal_info_msg(region);
+}
+
+void
+MR_region_destroy_region_msg(MR_Region *region)
+{
+    printf("Destroy region ");
+    MR_region_region_struct_removal_info_msg(region);
+    printf("ite frame: %d\n", MR_region_ite_sp);
+    printf("disj frame: %d\n", MR_region_disj_sp);
+    printf("commit frame: %d\n", MR_region_commit_sp);
+}
+
+void
+MR_region_logically_remove_region_msg(MR_Region *region)
+{
+    printf("Logically remove region ");
+    MR_region_region_struct_removal_info_msg(region);
+}
+
+void
+MR_region_region_struct_removal_info_msg(MR_Region *region)
+{
+    printf("#%d\n", region->MR_region_sequence_number);
+    printf("\tHandle: %d\n", region);
+    printf("\tLogically removed: %d\n", region->MR_region_logical_removed);
+    printf("\tProtected by ite frame #%d: %d\n",
+        MR_region_get_frame_number(region->MR_region_ite_protected),
+        region->MR_region_ite_protected);
+    printf("\tProtected by disj frame #%d: %d\n",
+        MR_region_get_frame_number(region->MR_region_disj_protected),
+        region->MR_region_disj_protected);
+    printf("\tSaved in commit frame #%d: %d\n",
+        MR_region_get_frame_number(region->MR_region_commit_frame),
+        region->MR_region_commit_frame);
+    printf("\tBe destroyed at commit: %d\n",
+        region->MR_region_destroy_at_commit);
+}
+
+void
+MR_region_push_ite_frame_msg(MR_Word *ite_frame)
+{
+    int frame_number;
+
+    frame_number = MR_region_get_frame_number(ite_frame);
+    printf("Push ite frame #%d: %d\n", frame_number, ite_frame);
+    printf("\tPrevious frame at push #%d: %d\n",
+        MR_region_get_frame_number((MR_Word *) (*ite_frame)), *ite_frame);
+    printf("\tSaved most recent region at push: %d\n",
+        *(ite_frame + MR_REGION_FRAME_REGION_LIST));
+}
+
+void
+MR_region_ite_frame_msg(MR_Word *ite_frame)
+{
+    printf("Ite frame #%d: %d\n",
+        MR_region_get_frame_number(ite_frame), ite_frame);
+    printf("\tPrevious frame #%d: %d\n",
+        MR_region_get_frame_number((MR_Word *) (*ite_frame)), *ite_frame);
+    printf("\tSaved most recent: %d\n",
+        *(ite_frame + MR_REGION_FRAME_REGION_LIST));
+    MR_region_ite_frame_protected_regions_msg(ite_frame);
+    MR_region_ite_frame_snapshots_msg(ite_frame);
+}
+
+void
+MR_region_ite_frame_protected_regions_msg(MR_Word *ite_frame)
+{
+    MR_Word *first_protected_region;
+    MR_Word *slot;
+    int     num_protected_regions;
+    int     i;
+
+    num_protected_regions =
+        *(ite_frame + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    first_protected_region = ite_frame + MR_REGION_FRAME_FIXED_SIZE;
+
+    /*
+    ** This check is for development, when it becomes more stable,
+    ** the check can be removed. Normally we expect not many regions.
+    */
+    if (num_protected_regions > 10) {
+        printf("Number of protected region: %d\n", num_protected_regions);
+        MR_fatal_error("Too many protected regions.");
+    }
+
+    for (i = 0; i < num_protected_regions; i++) {
+        slot = first_protected_region + i * MR_REGION_ITE_PROT_SIZE;
+        printf("\tAt slot: %d, ite-protect region: %d\n", slot, *slot);
+    }
+}
+
+void
+MR_region_ite_frame_snapshots_msg(MR_Word *ite_frame)
+{
+    MR_Word *first_snapshot;
+    MR_Word *slot;
+    int     num_snapshots;
+    int     num_protected_regions;
+    int     i;
+
+    num_snapshots = *(ite_frame + MR_REGION_FRAME_NUMBER_SNAPSHOTS);
+    num_protected_regions =
+        *(ite_frame + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    first_snapshot = ite_frame + MR_REGION_FRAME_FIXED_SIZE +
+        num_protected_regions * MR_REGION_ITE_PROT_SIZE;
+
+    if (num_snapshots > 10) {
+        printf("Number of snapshots: %d\n", num_snapshots);
+        MR_fatal_error("Too many snapshots");
+    }
+
+    for (i = 0; i < num_snapshots; i++) {
+        slot = first_snapshot + i * MR_REGION_SNAPSHOT_SIZE;
+        printf("\tAt slot: %d, snapshot of region: %d\n", slot, *slot);
+    }
+}
+
+void
+MR_region_push_disj_frame_msg(MR_Word *disj_frame)
+{
+    printf("Push disj frame #%d: %d\n",
+        MR_region_get_frame_number(disj_frame), disj_frame);
+    printf("\tPrevious frame at push #%d: %d\n",
+        MR_region_get_frame_number((MR_Word *) (*disj_frame)), *disj_frame);
+    printf("\tSaved most recent region at push: %d\n",
+        *(disj_frame + MR_REGION_FRAME_REGION_LIST));
+}
+
+void
+MR_region_disj_frame_msg(MR_Word *disj_frame)
+{
+    printf("Disj frame #%d: %d\n",
+        MR_region_get_frame_number(disj_frame), disj_frame);
+    printf("\tPrevious frame #%d: %d\n",
+        MR_region_get_frame_number((MR_Word *) (*disj_frame)), *disj_frame);
+    printf("\tSaved most recent region: %d\n",
+        *(disj_frame + MR_REGION_FRAME_REGION_LIST));
+}
+
+void
+MR_region_disj_frame_protected_regions_msg(MR_Word *disj_frame)
+{
+    MR_Word *first_protected_region;
+    MR_Word *slot;
+    int     num_protected_regions;
+    int     i;
+
+    num_protected_regions =
+        *(disj_frame + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    first_protected_region = disj_frame + MR_REGION_FRAME_FIXED_SIZE;
+
+    /*
+    ** This check is for development, when it becomes more stable,
+    ** the check can be removed.
+    */
+    if (num_protected_regions > 10) {
+        printf("Number of protected region: %d\n", num_protected_regions);
+        MR_fatal_error("Too many protected regions.");
+    }
+
+    for (i = 0; i < num_protected_regions; i++) {
+        slot = first_protected_region + i * MR_REGION_DISJ_PROT_SIZE;
+        printf("\tAt slot: %d, disj-protect region: %d\n", slot, *slot);
+    }
+
+}
+
+void
+MR_region_disj_frame_snapshots_msg(MR_Word *disj_frame)
+{
+    MR_Word *first_snapshot;
+    MR_Word *slot;
+    int     num_snapshots;
+    int     num_protected_regions;
+    int     i;
+
+    num_snapshots = *(disj_frame + MR_REGION_FRAME_NUMBER_SNAPSHOTS);
+    num_protected_regions =
+        *(disj_frame + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    first_snapshot = disj_frame + MR_REGION_FRAME_FIXED_SIZE +
+        num_protected_regions * MR_REGION_DISJ_PROT_SIZE;
+
+    if (num_snapshots > 10) {
+        printf("Number of snapshots: %d\n", num_snapshots);
+        MR_fatal_error("Too many snapshots");
+    }
+
+    for (i = 0; i < num_snapshots; i++) {
+        slot = first_snapshot + i * MR_REGION_SNAPSHOT_SIZE;
+        printf("\tAt slot: %d, snapshot of region: %d\n", slot, *slot);
+    }
+}
+
+void
+MR_region_push_commit_frame_msg(MR_Word *commit_frame)
+{
+    int i;
+
+    printf("Push commit frame #%d: %d\n",
+        MR_region_get_frame_number(commit_frame), commit_frame);
+    printf("\tPrevious frame at push #%d: %d\n",
+        MR_region_get_frame_number((MR_Word *) *commit_frame), *commit_frame);
+    printf("\tSequence number at push: %d\n",
+        *(commit_frame + MR_REGION_COMMIT_FRAME_SEQUENCE_NUMBER));
+}
+
+void
+MR_region_commit_frame_msg(MR_Word *commit_frame)
+{
+    MR_Word *first_saved_region;
+    MR_Word *saved_region;
+    int     i;
+    int     num_saved_regions;
+
+    num_saved_regions =
+        *(commit_frame + MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);
+    first_saved_region = commit_frame +
+        MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION;
+
+    printf("\tNumber of saved regions: %d\n", num_saved_regions);
+    for (i = 0; i < num_saved_regions; i++) {
+        saved_region = first_saved_region + i * MR_REGION_COMMIT_ENTRY_SIZE;
+        printf("Slot: %d, region: %d\n", saved_region, *saved_region);
+    }
+}
+
+void
+MR_region_commit_frame_saved_regions_msg(MR_Word *commit_frame)
+{
+    MR_Word *first_saved_region;
+    MR_Word *slot;
+    int     num_saved_regions;
+    int     i;
+
+    num_saved_regions =
+        *(commit_frame + MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);
+    first_saved_region = commit_frame + MR_REGION_COMMIT_FRAME_FIXED_SIZE;
+
+    /*
+    ** This check is for development, when it becomes more stable, the
+    ** check can be removed.
+    */
+    if (num_saved_regions > 10) {
+        printf("Number of saved region: %d\n", num_saved_regions);
+        MR_fatal_error("Too many regions were saved.");
+    }
+
+    for (i = 0; i < num_saved_regions; i++) {
+        slot = first_saved_region + i;
+        printf("\tAt slot: %d, saved region: %d\n", slot, *slot);
+    }
+
+}
+
+void
+MR_region_destroy_marked_regions_at_commit_msg(int saved_seq_number,
+    int number_of_saved_regions, MR_Word *first_saved_region_slot)
+{
+    printf("Destroy marked regions at commit:\n");
+    printf("\tSaved sequence number: %d\n", saved_seq_number);
+    printf("\tNumber of saved regions: %d\n", number_of_saved_regions);
+
+    if (number_of_saved_regions > 0)
+        printf("\tThe first slot of saved regions: %d\n",
+            first_saved_region_slot);
+}
+
+#endif /* End of MR_RBMM_DEBUG. */
+
+/*---------------------------------------------------------------------------*/
+/*
+** Profiling methods for RBMM.
+*/
+
+#if defined(MR_RBMM_PROFILING)
+
+void
+MR_region_update_profiling_unit(MR_RegionProfUnit *profiling_unit,
+    int quantity)
+{
+    profiling_unit->MR_rbmmpu_current += quantity;
+    if (quantity > 0) {
+        profiling_unit->MR_rbmmpu_total += quantity;
+    }
+
+    if (profiling_unit->MR_rbmmpu_current > profiling_unit->MR_rbmmpu_max) {
+        profiling_unit->MR_rbmmpu_max = profiling_unit->MR_rbmmpu_current;
+    }
+}
+
+void
+MR_region_profile_destroyed_region(MR_Region *region)
+{
+    int allocated_size_of_region;
+
+    MR_region_update_profiling_unit(&MR_rbmmp_regions_used, -1);
+    MR_region_update_profiling_unit(&MR_rbmmp_pages_used,
+        -MR_region_get_number_of_pages((MR_RegionPage *) region,
+        region->MR_region_last_page));
+    allocated_size_of_region =
+        ((MR_RegionPage *) region)->MR_regionpage_allocated_size;
+    MR_region_update_profiling_unit(&MR_rbmmp_words_used,
+        -allocated_size_of_region);
+    if (allocated_size_of_region > MR_rbmmp_biggest_region_size) {
+        MR_rbmmp_biggest_region_size = allocated_size_of_region;
+    }
+}
+
+void
+MR_region_profile_restore_from_snapshot(MR_RegionSnapshot *snapshot)
+{
+    MR_Region       *restoring_region;
+    MR_RegionPage   *first_new_page;
+    int             new_words;
+    int             new_pages;
+
+    restoring_region = snapshot->region;
+    first_new_page = snapshot->saved_last_page->MR_regionpage_next;
+
+    if (first_new_page != NULL) {
+        new_pages = MR_region_get_number_of_pages(first_new_page,
+             restoring_region->MR_region_last_page);
+        MR_region_update_profiling_unit(&MR_rbmmp_pages_used, -new_pages);
+        new_words = (new_pages * MR_REGION_PAGE_SPACE_SIZE -
+             restoring_region->MR_region_available_space +
+             snapshot->saved_available_space);
+    } else {
+        new_words = snapshot->saved_available_space -
+            restoring_region->MR_region_available_space;
+    }
+    ((MR_RegionPage *) restoring_region)->MR_regionpage_allocated_size
+        -= new_words;
+    MR_region_update_profiling_unit(&MR_rbmmp_words_used, -new_words);
+}
+
+int
+MR_region_get_number_of_pages(MR_RegionPage *from_page, MR_RegionPage *to_page)
+{
+    MR_RegionPage   *page;
+    int             number_of_pages;
+
+    page = from_page;
+    number_of_pages = 0;
+    while (page != to_page) {
+        number_of_pages += 1;
+        page = page->MR_regionpage_next;
+    }
+    /* Plus the last page. */
+    number_of_pages += 1;
+    return number_of_pages;
+}
+
+void
+MR_region_print_profiling_unit(const char *str,
+    MR_RegionProfUnit *profiling_unit)
+{
+    printf(str);    /* XXX This is dangerous. */
+    printf("\n");
+    printf("\tTotal: %d.\n", profiling_unit->MR_rbmmpu_total);
+    printf("\tMaximum: %d.\n", profiling_unit->MR_rbmmpu_max);
+    printf("\tCurrent: %d.\n", profiling_unit->MR_rbmmpu_current);
+}
+
+void
+MR_region_print_profiling_info(void)
+{
+    MR_region_print_profiling_unit("Regions:", &MR_rbmmp_regions_used);
+    printf("Biggest region size: %d.\n", MR_rbmmp_biggest_region_size);
+    MR_region_print_profiling_unit("Words:", &MR_rbmmp_words_used);
+    MR_region_print_profiling_unit("Pages used:", &MR_rbmmp_pages_used);
+    printf("Pages requested: %d.\n", MR_rbmmp_pages_requested);
+}
+
+#else /* Not define MR_RBMM_PROFILING. */
+
+void
+MR_region_update_profiling_unit(MR_RegionProfUnit *pu, int q)
+{
+    /* do nothing */
+}
+
+void
+MR_region_profile_destroyed_region(MR_Region *r)
+{
+    /* do nothing */
+}
+
+void
+MR_region_profile_restore_from_snapshot(MR_RegionSnapshot *s)
+{
+    /* do nothing */
+}
+
+int
+MR_region_get_number_of_pages(MR_RegionPage *fp, MR_RegionPage *tp)
+{
+    return 0;
+}
+
+void
+MR_region_print_profiling_info(void)
+{
+}
+
+#endif /* End of Not define MR_RBMM_PROFILING. */
+
+#endif  /* MR_USE_REGIONS */
Index: runtime/mercury_region.h
===================================================================
RCS file: runtime/mercury_region.h
diff -N runtime/mercury_region.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ runtime/mercury_region.h	8 Oct 2007 15:26:38 -0000
@@ -0,0 +1,1036 @@
+/*
+** vim: ts=4 sw=4 expandtab
+*/
+/*
+** Copyright (C) 2007 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: mercury_region.h
+** main author: Quan Phan
+*/
+
+#ifndef MERCURY_REGION_H
+#define MERCURY_REGION_H
+
+#include "mercury_types.h"
+
+#ifdef MR_USE_REGIONS
+
+/*
+** See the documentation of MR_RBMM_DEBUG and MR_RBMM_PROFILING in
+** mercury_conf_param.h.
+*/
+
+/*
+** XXX: Many of these macros would be more efficient if they updated the
+** pointer processed in each loop iteration using pointer increment operations
+** instead of recomputing it each time from the pointer to the first element,
+** and the loop variable  i.
+**
+** XXX Many of these macros would be more readable if they used array notation.
+** For example, stack_pointer[offset] instead *(stack_pointer + offset),
+** and &stack_pointer[offset] instead (stack_pointer + offset).
+*/
+
+/* XXX This should be made configurable when compiling a program. */
+#define     MR_REGION_NUM_PAGES_TO_REQUEST                  100
+#define     MR_REGION_PAGE_SPACE_SIZE                       256
+
+/*
+** The following constants should match the values of the Mercury compiler
+** options with corresponding names.
+*/
+
+#define     MR_REGION_FRAME_FIXED_SIZE                      4
+#define     MR_REGION_FRAME_PREVIOUS_FRAME                  0
+#define     MR_REGION_FRAME_REGION_LIST                     1
+#define     MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS        2
+#define     MR_REGION_FRAME_NUMBER_SNAPSHOTS                3
+
+#define     MR_REGION_COMMIT_FRAME_FIXED_SIZE               3
+#define     MR_REGION_COMMIT_FRAME_PREVIOUS_FRAME           0
+#define     MR_REGION_COMMIT_FRAME_SEQUENCE_NUMBER          1
+#define     MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS     2
+#define     MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION       3
+
+#define     MR_REGION_SNAPSHOT_SIZE                         4
+#define     MR_REGION_SNAPSHOT_REGION                       0
+#define     MR_REGION_SNAPSHOT_LAST_PAGE                    1
+#define     MR_REGION_SNAPSHOT_NEXT_AVAILABLE_WORD          2
+#define     MR_REGION_SNAPSHOT_AVAILABLE_SPACE              3
+
+#define     MR_REGION_ITE_PROT_SIZE                         1
+#define     MR_REGION_DISJ_PROT_SIZE                        1
+#define     MR_REGION_COMMIT_ENTRY_SIZE                     1
+
+/*
+** A region page contains an array (of MR_Word) to store program data and
+** a pointer to the next to form a single-linked-list.  Note: the order of
+** fields in this struct is important. We make use of the order for several
+** computations (such as the address of a region).
+*/
+
+struct MR_RegionPage_Struct {
+    /* The space to store program data. */
+    MR_Word             MR_regionpage_space[MR_REGION_PAGE_SPACE_SIZE];
+
+    /* Pointer to the next page to form the linked list. */
+    MR_RegionPage       *MR_regionpage_next;
+
+#ifdef MR_RBMM_PROFILING
+    /*
+    ** This is to count the number of words which are currently allocated into
+    ** the region. It means that it will be reset at backtracking if the region
+    ** is restored from its snapshot.
+    */
+    int                 MR_regionpage_allocated_size;
+#endif
+};
+
+/*
+** A region is implemented as a single-linked list of (region) pages.
+** The information of the region itself (pointer to next available word,
+** removal counter, some other operational data) is stored in its first page.
+*/
+
+struct MR_Region_Struct {
+    /*
+    ** Pointer to the last page of the region, i.e., the newest or last added
+    ** page. This is needed when we need to enlarge the region.
+    */
+    MR_RegionPage       *MR_region_last_page;
+
+    /*
+    ** Pointer to the next available word for allocation. Allocations into
+    ** a region always occur at its last page therefore this pointer always
+    ** points into the last page.
+    */
+    MR_Word             *MR_region_next_available_word;
+
+    /*
+    ** The current number of words (in the last page) available for allocation
+    ** into the region. When an allocation requires more words than what is
+    ** available the region is extended by adding a new page.
+    */
+    MR_Word             MR_region_available_space;
+
+    /*
+    ** Currently not used. To be used for implementing conditional removals
+    ** of regions, i.e., the region is only actually removed when the counter
+    ** equals to one.
+    */
+    unsigned int        MR_region_removal_counter;
+
+    /* Sequence number of the region. */
+    MR_Word             MR_region_sequence_number;
+
+    /* If the region has been removed in forward execution. */
+    MR_Word             MR_region_logical_removed;
+
+    /*
+    ** NULL if the region is not protected by any if-then-else. Otherwise
+    ** it points to region_ite_stack frame that protects it.
+    */
+    MR_Word             *MR_region_ite_protected;
+
+    /*
+    ** NULL if the region is not protected by any disj goal. If some disj
+    ** frames exist and the region is protected from being destroyed by a
+    ** disj goal, this field will point to the top region_disj_stack
+    ** frame.
+    */
+    MR_Word             *MR_region_disj_protected;
+
+    /* If the region is saved at this frame in the region_commit_stack. */
+    MR_Word             *MR_region_commit_frame;
+
+    /*
+    ** True if the region has been removed logically in a commit context and
+    ** therefore needs to be destroyed at commit.
+    */
+    MR_Word             MR_region_destroy_at_commit;
+
+    MR_Region           *MR_region_previous_region;
+    MR_Region           *MR_region_next_region;
+};
+
+/*
+** To save the current size of a region in preparation for instant reclaiming.
+*/
+
+struct MR_RegionSnapshot_Struct {
+    MR_Region           *region;
+    MR_RegionPage       *saved_last_page;
+    MR_Word             *saved_next_available_word;
+    MR_Word             saved_available_space;
+};
+
+/* Protection information in a disj frame. */
+struct MR_RegionDisjProtect_Struct {
+    MR_Region           *region;
+    /* XXX We no longer need to save ite_protected into a disj-frame*/
+    /*MR_Word                         *ite_protected;*/
+};
+
+/*
+** The region runtime maintains a list of free pages, when a program needs
+** a page for a region the page is taken from the list.
+*/
+
+extern MR_RegionPage    *MR_region_free_page_list;
+
+/* The live regions are linked in a list. */
+extern MR_Region        *MR_live_region_list;
+
+extern MR_Word          MR_region_sequence_number;
+
+/* Pointers to the top frames of ite, disj, and commit stacks. */
+extern MR_Word          *MR_region_ite_sp;
+extern MR_Word          *MR_region_disj_sp;
+extern MR_Word          *MR_region_commit_sp;
+
+/*---------------------------------------------------------------------------*/
+
+/* Create a region. */
+extern  MR_Region       *MR_region_create_region(void);
+
+/* Destroy a region, i.e., physically deallocate the region. */
+extern  void            MR_region_destroy_region(MR_Region *);
+
+/*
+** Remove a region.
+** If the region is not protected it is destroyed, otherwise it is only
+** logically removed, i.e., we mark it as removed but not actually deallocate.
+*/
+
+extern  void            MR_region_remove_region(MR_Region *);
+extern  void            MR_remove_undisjprotected_region_ite_then_semidet(
+                            MR_Region *);
+extern  void            MR_remove_undisjprotected_region_ite_then_nondet(
+                            MR_Region *);
+
+/* Allocate a number of words into a region. */
+extern  MR_Word         *MR_region_alloc(MR_Region *, unsigned int);
+
+#define     MR_alloc_in_region(dest, region, num)                           \
+            MR_tag_alloc_in_region(dest, 0, region, num)                    \
+
+#define     MR_tag_alloc_in_region(dest, tag, region, num)                  \
+            do {                                                            \
+                (dest) = (MR_Word) MR_mkword((tag), (MR_Word)               \
+                    MR_region_alloc((MR_Region *) (region), (num)));        \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+/*
+** push_region_frame
+*/
+
+#define     MR_push_region_ite_frame(new_ite_sp)                            \
+            do {                                                            \
+                *(new_ite_sp) = (MR_Word) MR_region_ite_sp;                 \
+                MR_save_live_region_list(                                   \
+                        *((new_ite_sp) + MR_REGION_FRAME_REGION_LIST));     \
+                MR_region_ite_sp = (new_ite_sp);                            \
+                MR_region_debug_push_ite_frame(new_ite_sp);                 \
+            } while (0)
+
+#define     MR_push_region_disj_frame(new_disj_sp)                          \
+            do {                                                            \
+                *(new_disj_sp) = (MR_Word) MR_region_disj_sp;               \
+                MR_save_live_region_list(                                   \
+                    *((new_disj_sp) + MR_REGION_FRAME_REGION_LIST));        \
+                MR_region_disj_sp = (new_disj_sp);                          \
+                MR_region_debug_push_disj_frame(new_disj_sp);               \
+                if (MR_live_region_list != NULL) {                          \
+                    MR_region_debug_region_struct_removal_info(             \
+                        MR_live_region_list);                               \
+                }                                                           \
+            } while (0)
+
+#define     MR_push_region_commit_frame(new_commit_sp)                      \
+            do {                                                            \
+                *(new_commit_sp) = (MR_Word) MR_region_commit_sp;           \
+                *(new_commit_sp + MR_REGION_COMMIT_FRAME_SEQUENCE_NUMBER) = \
+                     MR_region_sequence_number;                             \
+                MR_region_commit_sp = (new_commit_sp);                      \
+                MR_region_debug_push_commit_frame(new_commit_sp);           \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+/*
+** region_fill_frame
+*/
+/*
+** Save the region if it satisfies:
+** (a) live before condition
+** (c2) aren't already protected (ite_protected or disj_protected).
+** If save the region, then set the ite_protected field in these regions
+** to point to the frame.
+*/
+#define     MR_region_fill_ite_protect(ite_sp, region_ptr,                  \
+                num_protected_regions, region_slot_reg)                     \
+            do {                                                            \
+                MR_Region *region;                                          \
+                                                                            \
+                region = (MR_Region *) (region_ptr);                        \
+                if (region->MR_region_disj_protected == NULL &&             \
+                    region->MR_region_ite_protected == NULL)                \
+                {                                                           \
+                    *((MR_Word *) (region_slot_reg)) = (MR_Word) region;    \
+                    (num_protected_regions)++;                              \
+                    (region_slot_reg) = (MR_Word)                           \
+                        (((MR_Word *) (region_slot_reg)) +                  \
+                            MR_REGION_ITE_PROT_SIZE);                       \
+                    region->MR_region_ite_protected = (ite_sp);             \
+                }                                                           \
+            } while (0)
+
+/*
+** This is to prepare for instant reclaiming at the start of else. For instant
+** reclaiming a region we save its current size by taking a snapshot of it. The
+** natural question would be for which regions.  The very first
+** criterion is whether a region will be destroyed right at the start of the
+** else. It is because we need not to reclaim memory for those which will be
+** destroyed anyway right after that. To decide if a region will be destroyed
+** at the start of the else we need information at both compile-time and
+** runtime. That is at compile-time we only know if the region is removed or
+** not, and at runtime we will know if the region is protected from being
+** destroyed. So,
+** 1. Those that are removed and protected need to be saved.
+** 2. Those that are not removed (so not destroyed) will need to be saved.
+*/
+/*
+** XXX ite_sp is not used here.
+*/
+#define     MR_region_fill_ite_snapshot_removed(ite_sp, region_ptr,         \
+                num_snapshots, snapshot_block)                              \
+            do {                                                            \
+                MR_Region   *region;                                        \
+                                                                            \
+                region = (MR_Region *) (region_ptr);                        \
+                if (region->MR_region_ite_protected != NULL ||              \
+                    region->MR_region_disj_protected != NULL)               \
+                {                                                           \
+                    MR_save_snapshot(region, snapshot_block);               \
+                    MR_next_snapshot_block(snapshot_block);                 \
+                    (num_snapshots)++;                                      \
+                } /* Else the region is not protected. */                   \
+            } while (0)
+
+#define     MR_region_fill_ite_snapshot_not_removed(ite_sp, region_ptr,     \
+                num_snapshots, snapshot_block)                              \
+            do {                                                            \
+                MR_Region   *region;                                        \
+                                                                            \
+                region = (MR_Region *) (region_ptr);                        \
+                MR_save_snapshot(region, (snapshot_block));                 \
+                MR_next_snapshot_block(snapshot_block);                     \
+                (num_snapshots)++;                                          \
+            } while (0)
+
+#define     MR_region_fill_disj_protect(disj_sp, region_ptr,                \
+                num_protected_regions, protection_block)                    \
+            do {                                                            \
+                MR_Region   *region;                                        \
+                                                                            \
+                region = (MR_Region *) (region_ptr);                        \
+                if (region->MR_region_disj_protected == NULL) {             \
+                    MR_save_disj_protection(region, protection_block);      \
+                    (num_protected_regions)++;                              \
+                    MR_next_disj_protection_block(protection_block);        \
+                    region->MR_region_disj_protected = (disj_sp);           \
+                }                                                           \
+            } while (0)
+
+#define     MR_region_fill_disj_snapshot(disj_sp, region_ptr,               \
+                num_snapshots, snapshot_block)                              \
+            do {                                                            \
+                MR_Region   *region;                                        \
+                                                                            \
+                region = (MR_Region *) (region_ptr);                        \
+                MR_save_snapshot(region, (snapshot_block));                 \
+                MR_next_snapshot_block(snapshot_block);                     \
+                (num_snapshots)++;                                          \
+            } while (0)
+
+/*
+** Save the live and unprotected regions which are input to the commit goal
+** into the top commit stack frame.
+** Set the commit_frame field in these regions to point to the frame.
+*/
+#define     MR_region_fill_commit(commit_sp, region_ptr,                    \
+                    num_saved_region_reg, region_slot_reg)                  \
+            do {                                                            \
+                MR_Region   *region;                                        \
+                                                                            \
+                region = (MR_Region *) (region_ptr);                        \
+                if (region->MR_region_disj_protected == NULL &&             \
+                    region->MR_region_ite_protected == NULL)                \
+                {                                                           \
+                    *((MR_Word *) (region_slot_reg)) = (MR_Word) region;    \
+                    num_saved_region_reg++;                                 \
+                    (region_slot_reg) = (MR_Word)                           \
+                        (((MR_Word *) (region_slot_reg)) +                  \
+                            MR_REGION_COMMIT_ENTRY_SIZE);                   \
+                    (region)->MR_region_commit_frame = (commit_sp);         \
+                }                                                           \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+/*
+** region_set_fixed_slot
+*/
+#define     MR_region_set_ite_num_protects(ite_sp, num)                     \
+            do {                                                            \
+                *((ite_sp) + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS)      \
+                    = (num);                                                \
+                MR_region_debug_ite_frame_protected_regions(ite_sp);        \
+            } while (0)
+
+#define     MR_region_set_ite_num_snapshots(ite_sp, num)                    \
+            do {                                                            \
+                *((ite_sp) + MR_REGION_FRAME_NUMBER_SNAPSHOTS) = (num);     \
+                MR_region_debug_ite_frame_snapshots(ite_sp);                \
+            } while (0)
+
+#define     MR_region_set_disj_num_protects(disj_sp, num)                   \
+            do {                                                            \
+                *((disj_sp) + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS)     \
+                    = (num);                                                \
+                MR_region_debug_disj_frame_protected_regions(disj_sp);      \
+            } while (0)
+
+#define     MR_region_set_disj_num_snapshots(disj_sp, num)                  \
+            do {                                                            \
+                *((disj_sp) + MR_REGION_FRAME_NUMBER_SNAPSHOTS) = (num);    \
+                MR_region_debug_disj_frame_snapshots(disj_sp);              \
+            } while (0)
+
+#define     MR_region_set_commit_num_entries(commit_sp, num)                \
+            do {                                                            \
+                *((commit_sp) + MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS)\
+                    = (num);                                                \
+                MR_region_debug_commit_frame_saved_regions(commit_sp);      \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+/*
+** use_and_maybe_pop_region_frame
+*/
+
+/*
+** The next two macros are to remove each protected region at the start of the
+** then part. If the condition is semidet we just need to destroy all the
+** protected regions (whose are not disj-protected).
+** If the condition is nondet we have to do 2 more things:
+**  + 1. check if a protected region has already been destroyed
+**  + 2. if we destroy a protected region, we have to nullify its
+**  corresponding entry in the ite frame.
+*/
+#define     MR_use_region_ite_then_semidet(ite_sp)                          \
+            do {                                                            \
+                MR_Word     num_protected_regions;                          \
+                MR_Word     *first_protected_region;                        \
+                MR_Region   *protected_region;                              \
+                int         i;                                              \
+                                                                            \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions(ite_sp);       \
+                first_protected_region =                                    \
+                    (ite_sp) + MR_REGION_FRAME_FIXED_SIZE;                  \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    protected_region = (MR_Region *)                        \
+                        (*(first_protected_region + i));                    \
+                    MR_remove_undisjprotected_region_ite_then_semidet(      \
+                        protected_region);                                  \
+                }                                                           \
+                MR_pop_region_ite_frame(ite_sp);                            \
+            } while (0)
+
+#define     MR_use_region_ite_then_nondet(ite_sp)                           \
+            do {                                                            \
+                MR_Word     num_protected_regions;                          \
+                MR_Word     *first_protected_region;                        \
+                MR_Region   *protected_region;                              \
+                int         i;                                              \
+                                                                            \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions(ite_sp);       \
+                first_protected_region =                                    \
+                    (ite_sp) + MR_REGION_FRAME_FIXED_SIZE;                  \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    protected_region = (MR_Region *)                        \
+                        (*(first_protected_region + i));                    \
+                    if (protected_region != NULL) {                         \
+                        MR_remove_undisjprotected_region_ite_then_nondet(   \
+                            protected_region);                              \
+                    }                                                       \
+                }                                                           \
+            } while (0)
+
+#define     MR_use_region_ite_else_semidet(ite_sp)                          \
+            do {                                                            \
+                MR_region_process_at_ite_else(ite_sp);                      \
+            } while (0)
+
+#define     MR_use_region_ite_else_nondet(ite_sp)                           \
+            do {                                                            \
+                MR_region_process_at_ite_else(ite_sp);                      \
+            } while (0)
+
+/*
+** XXX  What am I supposed to do here?
+** I think it should be exactly the same as the process at the start of
+** any else branch, i.e., after the condition fails (to produce any solution).
+*/
+#define     MR_use_region_ite_nondet_cond_fail(ite_sp)                      \
+            do {                                                            \
+                MR_region_process_at_ite_else(ite_sp)                       \
+            } while (0)
+
+#define     MR_use_region_disj_later(disj_sp)                               \
+            do {                                                            \
+                MR_region_disj_restore_from_snapshots(disj_sp);             \
+                MR_region_disj_destroy_new_regions(disj_sp);                \
+            } while (0)
+
+#define     MR_use_region_disj_last(disj_sp)                                \
+            do {                                                            \
+                MR_region_disj_restore_from_snapshots(disj_sp);             \
+                MR_region_disj_destroy_new_regions(disj_sp);                \
+                MR_region_disj_unprotect_regions(disj_sp);                  \
+                MR_pop_region_disj_frame(disj_sp);                          \
+            } while (0)
+
+#define     MR_use_region_commit_success(commit_sp)                         \
+            do {                                                            \
+                MR_Word saved_region_seq_number;                            \
+                MR_Word number_of_saved_regions;                            \
+                MR_Word *first_saved_region_slot;                           \
+                                                                            \
+                saved_region_seq_number =                                   \
+                    *((commit_sp) +                                         \
+                        MR_REGION_COMMIT_FRAME_SEQUENCE_NUMBER);            \
+                number_of_saved_regions =                                   \
+                    *((commit_sp) +                                         \
+                        MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);       \
+                first_saved_region_slot =                                   \
+                    (commit_sp) + MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION;\
+                MR_region_debug_commit_frame(commit_sp);                    \
+                MR_region_debug_destroy_marked_regions_at_commit(           \
+                    saved_region_seq_number, number_of_saved_regions,       \
+                    first_saved_region_slot);                               \
+                MR_destroy_marked_new_regions_at_commit(                    \
+                    saved_region_seq_number);                               \
+                MR_destroy_marked_old_regions_at_commit(                    \
+                    number_of_saved_regions, first_saved_region_slot);      \
+                MR_pop_region_commit_frame(commit_sp);                      \
+            } while (0)
+
+/*
+** Commit failure means that the goal in the commit operation has failed.
+** We reset any changes to the commit-related state of saved regions
+** i.e., commit_frame and destroy_at_commit, to NULL and false, respectively.
+** Then the top commit frame is popped.
+*/
+#define     MR_use_region_commit_failure(commit_sp)                         \
+            do {                                                            \
+                MR_Word     number_of_saved_regions;                        \
+                MR_Word     *first_saved_region_slot;                       \
+                MR_Region   *region;                                        \
+                int         i;                                              \
+                                                                            \
+                number_of_saved_regions =                                   \
+                    *((commit_sp) +                                         \
+                        MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);       \
+                first_saved_region_slot =                                   \
+                    (commit_sp) + MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION;\
+                for (i = 0; i < number_of_saved_regions; i++) {             \
+                    region = (MR_Region *)                                  \
+                        (first_saved_region_slot +                          \
+                        i * MR_REGION_COMMIT_ENTRY_SIZE);                   \
+                    if (region != NULL) {                                   \
+                        region->MR_region_commit_frame = NULL;              \
+                        region->MR_region_destroy_at_commit = MR_FALSE;     \
+                    }                                                       \
+                }                                                           \
+                MR_pop_region_commit_frame(commit_sp);                      \
+            } while (0)
+
+extern  void    MR_destroy_marked_old_regions_at_commit(
+                    MR_Word number_of_saved_regions,
+                    MR_Word *first_saved_region_slot);
+
+extern  void    MR_destroy_marked_new_regions_at_commit(
+                    MR_Word saved_region_seq_number);
+
+/*---------------------------------------------------------------------------*/
+
+#define     MR_pop_region_ite_frame(ite_sp)                                 \
+            do {                                                            \
+                MR_region_ite_sp = (MR_Word *) (*ite_sp);                   \
+            } while (0)
+
+#define     MR_pop_region_disj_frame(disj_sp)                               \
+            do {                                                            \
+                MR_region_disj_sp = (MR_Word *) (*disj_sp);                 \
+            } while (0)
+
+#define     MR_pop_region_commit_frame(commit_sp)                           \
+            do {                                                            \
+                MR_region_commit_sp = (MR_Word *) (*commit_sp);             \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+/* Helpers for ite support. */
+
+/*
+** At the start of else, we
+** 1. unprotect the protected regions,
+** 2. instant reclaiming using snapshots,
+** 3. instant reclaiming by destroying new regions created in the condition,
+** 4. pop the current ite frame.
+*/
+#define     MR_region_process_at_ite_else(ite_sp)                           \
+            do {                                                            \
+                MR_region_ite_unprotect(ite_sp);                            \
+                MR_region_ite_restore_from_snapshots(ite_sp);               \
+                MR_region_ite_destroy_new_regions(ite_sp);                  \
+                MR_pop_region_ite_frame(ite_sp);                            \
+            } while (0)
+
+/*
+** Unprotect the protected regions at the beginning of the else part.
+*/
+#define     MR_region_ite_unprotect(ite_sp)                                 \
+            do {                                                            \
+                MR_Word     num_protected_regions;                          \
+                MR_Region   *protected_region;                              \
+                int         i;                                              \
+                int         first_protected_region;                         \
+                                                                            \
+                MR_region_debug_ite_frame(ite_sp);                          \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions(ite_sp);       \
+                first_protected_region = MR_REGION_FRAME_FIXED_SIZE;        \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    protected_region = (MR_Region *)                        \
+                        (*((ite_sp) + first_protected_region + i));         \
+                    /* Try to protect the region by an outer condition. */  \
+                    protected_region->MR_region_ite_protected = (MR_Word *) \
+                        (*(ite_sp));                                        \
+                    MR_region_debug_region_struct_removal_info(             \
+                        protected_region);                                  \
+                }                                                           \
+            } while (0)
+
+#define     MR_region_ite_restore_from_snapshots(ite_sp)                    \
+            do {                                                            \
+                MR_Word num_snapshots;                                      \
+                MR_Word first_snapshot_index;                               \
+                                                                            \
+                num_snapshots = MR_region_frame_number_snapshots(ite_sp);   \
+                MR_ite_frame_get_first_snapshot_index(ite_sp,               \
+                    first_snapshot_index);                                  \
+                MR_restore_snapshots(ite_sp, num_snapshots,                 \
+                    first_snapshot_index);                                  \
+            } while (0)
+
+#define     MR_region_ite_destroy_new_regions(ite_sp)                       \
+            MR_region_frame_destroy_new_regions(ite_sp)
+
+#define     MR_ite_frame_get_first_snapshot_index(ite_frame,                \
+                first_snapshot_index)                                       \
+            do {                                                            \
+                int num_protected_regions;                                  \
+                                                                            \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions((ite_frame));  \
+                (first_snapshot_index) = MR_REGION_FRAME_FIXED_SIZE +       \
+                    num_protected_regions * MR_REGION_ITE_PROT_SIZE;        \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+/* Helpers for nondet disjunction support. */
+
+/* XXX This macro should no long be used.
+** At any non-first disjunct, reset the ite_protected to the state before
+** the disjunction.
+*/
+#define     MR_region_disj_restore_ite_protected(disj_sp)                   \
+            do {                                                            \
+                MR_RegionDisjProtect    *first_block;                       \
+                MR_RegionDisjProtect    *block;                             \
+                MR_Word                 num_protected_regions;              \
+                MR_Word                 i;                                  \
+                                                                            \
+                first_block = (MR_RegionDisjProtect *)                      \
+                    (disj_sp + MR_REGION_FRAME_FIXED_SIZE);                 \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions(disj_sp);      \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    block = first_block + i;                                \
+                    block->region->MR_region_ite_protected =                \
+                        block->MR_region_ite_protected;                     \
+                }                                                           \
+            } while (0)
+
+/*
+** At any non-first disjunct, try instant reclaiming from snapshots.
+*/
+#define     MR_region_disj_restore_from_snapshots(disj_sp)                  \
+            do {                                                            \
+                MR_Word num_snapshots;                                      \
+                MR_Word first_snapshot_index;                               \
+                                                                            \
+                num_snapshots = MR_region_frame_number_snapshots(disj_sp);  \
+                MR_disj_frame_get_first_snapshot_index(disj_sp,             \
+                    first_snapshot_index);                                  \
+                MR_restore_snapshots(disj_sp, num_snapshots,                \
+                    first_snapshot_index);                                  \
+            } while (0)
+
+/*
+** At any non-first disjunct, try instant reclaiming by destroying new
+** regions.
+*/
+#define     MR_region_disj_destroy_new_regions(disj_sp)                     \
+            MR_region_frame_destroy_new_regions(disj_sp)
+
+/*
+** At the last disjunct, we do not disj-protect the regions anymore.
+*/
+#define     MR_region_disj_unprotect_regions(disj_sp)                       \
+            do {                                                            \
+                MR_RegionDisjProtect    *first_block;                       \
+                MR_RegionDisjProtect    *block;                             \
+                MR_Word                 num_protected_regions;              \
+                MR_Word                 i;                                  \
+                                                                            \
+                first_block = (MR_RegionDisjProtect *)                      \
+                    (disj_sp + MR_REGION_FRAME_FIXED_SIZE);                 \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions(disj_sp);      \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    block = first_block + i;                                \
+                    block->region->MR_region_disj_protected = NULL;         \
+                }                                                           \
+            } while (0)
+
+#define     MR_disj_frame_get_first_snapshot_index(disj_frame,              \
+                first_snapshot_index)                                       \
+            do {                                                            \
+                int num_protected_regions;                                  \
+                                                                            \
+                num_protected_regions =                                     \
+                    MR_region_frame_number_protected_regions(disj_frame);   \
+                (first_snapshot_index) = MR_REGION_FRAME_FIXED_SIZE +       \
+                    num_protected_regions * MR_REGION_DISJ_PROT_SIZE;       \
+            } while (0)
+
+/*---------------------------------------------------------------------------*/
+
+#define     MR_region_frame_number_protected_regions(frame) (               \
+                *((frame) + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS)       \
+            )
+
+#define     MR_save_disj_protection(region, protection_block)               \
+            do {                                                            \
+                MR_RegionDisjProtect *disj_prot;                            \
+                                                                            \
+                disj_prot = (MR_RegionDisjProtect *) (protection_block);    \
+                disj_prot->region = (region);                               \
+                /* disj_prot->MR_region_ite_protected =                     \
+                    (region)->MR_region_ite_protected; */                   \
+            } while (0)
+
+#define     MR_next_disj_protection_block(block) (                          \
+                (block) = (MR_Word) (((MR_RegionDisjProtect *) (block)) + 1) \
+            )
+
+#define     MR_region_frame_number_snapshots(frame) (                       \
+                *((frame) + MR_REGION_FRAME_NUMBER_SNAPSHOTS)               \
+            )
+
+#define     MR_save_snapshot(region, snapshot_block)                        \
+            do {                                                            \
+                MR_RegionSnapshot *snapshot;                                \
+                                                                            \
+                snapshot = (MR_RegionSnapshot *) (snapshot_block);          \
+                snapshot->region = (region);                                \
+                snapshot->saved_last_page = (region)->MR_region_last_page;  \
+                snapshot->saved_next_available_word =                       \
+                    (region)->MR_region_next_available_word;                \
+                snapshot->saved_available_space =                           \
+                    (region)->MR_region_available_space;                    \
+            } while (0)
+
+#define     MR_next_snapshot_block(snapshot_block) (                        \
+                (snapshot_block) = (MR_Word)                                \
+                    (((MR_RegionSnapshot *) (snapshot_block) ) + 1)         \
+            )
+
+/*
+** XXX For profiling:
+** One correct way to reset the allocated_size is to save it in the snapshot
+** so that here we have the old value right away. But having an extra slot
+** in the disj frame causes changes at other places. From the snapshot
+** information (as it is now) we can only compute the old value correctly if
+** there is no wasteful space at the end of the region's pages. Therefore the
+** allocated_size sometimes is not realiable.
+*/
+
+#define     MR_restore_snapshots(frame, num_snapshots, first_snapshot_index)\
+            do {                                                            \
+                MR_RegionSnapshot   *first_snapshot;                        \
+                MR_RegionSnapshot   *snapshot;                              \
+                MR_Region           *restoring_region;                      \
+                MR_RegionPage       *saved_last_page;                       \
+                MR_RegionPage       *first_new_page;                        \
+                int                 i;                                      \
+                                                                            \
+                first_snapshot = (MR_RegionSnapshot *)                      \
+                    ((frame) + (first_snapshot_index));                     \
+                for (i = 0; i < (num_snapshots); i++) {                     \
+                    snapshot = first_snapshot + i;                          \
+                    restoring_region = snapshot->region;                    \
+                    saved_last_page = snapshot->saved_last_page;            \
+                    first_new_page = saved_last_page->MR_regionpage_next;   \
+                    MR_region_profile_restore_from_snapshot(snapshot);      \
+                    if (first_new_page != NULL) {                           \
+                        MR_region_return_page_list(first_new_page,          \
+                            restoring_region->MR_region_last_page);         \
+                        restoring_region->MR_region_last_page =             \
+                            saved_last_page;                                \
+                    } /* else no new page added. */                         \
+                    restoring_region->MR_region_next_available_word =       \
+                        snapshot->saved_next_available_word;                \
+                    restoring_region->MR_region_available_space =           \
+                        snapshot->saved_available_space;                    \
+                }                                                           \
+            } while(0)
+
+#define     MR_region_frame_destroy_new_regions(frame)                      \
+            do {                                                            \
+                MR_Region   *saved_most_recent_region;                      \
+                MR_Region   *region;                                        \
+                MR_Region   *next_region;                                   \
+                                                                            \
+                saved_most_recent_region = (MR_Region *)                    \
+                    (*((frame) + MR_REGION_FRAME_REGION_LIST));             \
+                region = MR_live_region_list;                               \
+                while (region != saved_most_recent_region) {                \
+                    next_region = region->MR_region_next_region;            \
+                    MR_region_debug_disj_frame(frame);\
+                    /* We destroy regions upto before the saved one. */     \
+                    MR_region_destroy_region(region);                       \
+                    region = next_region;                                   \
+                }                                                           \
+                MR_live_region_list = saved_most_recent_region;             \
+            } while (0)
+
+/* from_page must not be NULL. */
+#define     MR_region_return_page_list(from_page, to_page)                  \
+            do {                                                            \
+                (to_page)->MR_regionpage_next = MR_region_free_page_list;   \
+                MR_region_free_page_list = (from_page);                     \
+            } while (0)
+
+#define     MR_save_live_region_list(slot) (                                \
+                (slot) = (MR_Word) MR_live_region_list                      \
+            )
+
+/*---------------------------------------------------------------------------*/
+/* Debug RBMM messages. */
+
+#ifdef MR_RBMM_DEBUG
+    #define     MR_region_debug_create_region(region)                       \
+                MR_region_create_region_msg(region)
+
+    #define     MR_region_debug_try_remove_region(region)                   \
+                MR_region_try_remove_region_msg(region)
+
+    #define     MR_region_debug_region_struct_removal_info(region)          \
+                MR_region_region_struct_removal_info_msg(region)
+
+    #define     MR_region_debug_destroy_region(region)                      \
+                MR_region_destroy_region_msg(region)
+
+/* Debug ite frame messages. */
+    #define     MR_region_debug_push_ite_frame(ite_sp)                      \
+                MR_region_push_ite_frame_msg(ite_sp)
+
+    #define     MR_region_debug_ite_frame(ite_sp);                          \
+                MR_region_ite_frame_msg(ite_sp)
+
+    #define     MR_region_debug_ite_frame_protected_regions(ite_sp);        \
+                MR_region_ite_frame_protected_regions_msg(ite_sp)
+
+    #define     MR_region_debug_ite_frame_snapshots(ite_sp);                \
+                MR_region_ite_frame_snapshots_msg(ite_sp)
+
+/* Debug disj frame messages. */
+    #define     MR_region_debug_push_disj_frame(disj_sp)                    \
+                MR_region_push_disj_frame_msg(disj_sp)
+
+    #define     MR_region_debug_disj_frame(disj_sp)                         \
+                MR_region_disj_frame_msg(disj_sp)
+
+    #define     MR_region_debug_disj_frame_protected_regions(disj_sp);      \
+                MR_region_disj_frame_protected_regions_msg(disj_sp);
+
+    #define     MR_region_debug_disj_frame_snapshots(disj_sp);              \
+                MR_region_disj_frame_snapshots_msg(disj_sp);
+
+/* Debug commit frame messages. */
+    #define     MR_region_debug_push_commit_frame(frame)                    \
+                MR_region_push_commit_frame_msg(frame)
+
+    #define     MR_region_debug_commit_frame(frame)                         \
+                MR_region_commit_frame_msg(frame)
+
+    #define     MR_region_debug_commit_frame_saved_regions(commit_sp);      \
+                MR_region_commit_frame_saved_regions_msg(commit_sp)
+
+    #define     MR_region_debug_destroy_marked_regions_at_commit(           \
+                    saved_region_seq_number, number_of_saved_regions,       \
+                    first_saved_region_slot)                                \
+                MR_region_destroy_marked_regions_at_commit_msg(             \
+                    saved_region_seq_number, number_of_saved_regions,       \
+                    first_saved_region_slot)
+
+#else   /* MR_RBMM_DEBUG */
+    #define     MR_region_debug_create_region(region)                       \
+                ((void) 0)
+
+    #define     MR_region_debug_try_remove_region(region)                   \
+                ((void) 0)
+
+
+    #define     MR_region_debug_region_struct_removal_info(region)          \
+                ((void) 0)
+
+    #define     MR_region_debug_destroy_region(region)                      \
+                ((void) 0)
+
+    #define     MR_region_debug_push_ite_frame(frame)                       \
+                ((void) 0)
+
+    #define     MR_region_debug_ite_frame(ite_sp);                          \
+                ((void) 0)
+
+    #define     MR_region_debug_ite_frame_protected_regions(ite_sp);        \
+                ((void) 0)
+
+    #define     MR_region_debug_ite_frame_snapshots(ite_sp);                \
+                ((void) 0)
+
+    #define     MR_region_debug_push_disj_frame(disj_sp)                    \
+                ((void) 0)
+
+    #define     MR_region_debug_disj_frame(frame)                           \
+                ((void) 0)
+
+    #define     MR_region_debug_disj_frame_protected_regions(disj_sp);      \
+                ((void) 0)
+
+    #define     MR_region_debug_disj_frame_snapshots(disj_sp);              \
+                ((void) 0)
+
+    #define     MR_region_debug_push_commit_frame(frame)                    \
+                ((void) 0)
+
+    #define     MR_region_debug_commit_frame(frame)                         \
+                ((void) 0)
+
+    #define     MR_region_debug_commit_frame_saved_regions(commit_sp)       \
+                ((void) 0)
+
+    #define     MR_region_debug_destroy_marked_regions_at_commit(           \
+                    saved_region_seq_number, number_of_saved_regions,       \
+                    first_saved_region_slot)                                \
+                ((void) 0)
+#endif /* MR_RBMM_DEBUG */
+
+extern  void    MR_region_create_region_msg(MR_Region *region);
+extern  void    MR_region_try_remove_region_msg(MR_Region *region);
+extern  void    MR_region_region_struct_removal_info_msg(MR_Region *region);
+extern  void    MR_region_destroy_region_msg(MR_Region *region);
+extern  void    MR_region_logically_remove_region_msg(MR_Region *region);
+
+extern  void    MR_region_push_ite_frame_msg(MR_Word *ite_frame);
+extern  void    MR_region_ite_frame_msg(MR_Word *ite_frame);
+extern  void    MR_region_ite_frame_protected_regions_msg(MR_Word *ite_frame);
+extern  void    MR_region_ite_frame_snapshots_msg(MR_Word *ite_frame);
+
+extern  void    MR_region_push_disj_frame_msg(MR_Word *disj_frame);
+extern  void    MR_region_disj_frame_msg(MR_Word *disj_frame);
+extern  void    MR_region_disj_frame_protected_regions_msg(
+                    MR_Word *disj_frame);
+extern  void    MR_region_disj_frame_snapshots_msg(MR_Word *disj_frame);
+
+extern  void    MR_region_push_commit_frame_msg(MR_Word *commit_frame);
+extern  void    MR_region_commit_frame_msg(MR_Word *commit_frame);
+extern  void    MR_region_commit_frame_saved_regions_msg(MR_Word *commit_frame);
+extern  void    MR_region_destroy_marked_regions_at_commit_msg(
+                    int saved_seq_number, int number_of_saved_regions,
+                    MR_Word *commit_frame);
+
+/*---------------------------------------------------------------------------*/
+/* Profiling RBMM. */
+
+#ifdef MR_RBMM_PROFILING
+
+/*
+** This is the profiling wish list, not all of them have been yet collected.
+** - How many words are allocated
+** - Maximum number of words
+** - How many regions are allocated
+** - Maximum number of regions
+** - Size of the biggest region
+** - How many regions are saved at commit entries
+** - How many regions are protected at entry to a condition
+** - How many snapshots are saved at entry to a condition
+** - How many regions are protected at entry to a disj goal
+** - How many snapshots are saved at entry to a disj goal
+** - How many pages are requested from the OS
+** - Time profiling: compile-time and runtime
+*/
+
+struct MR_RegionProfUnit_Struct {
+    int        MR_rbmmpu_current;
+    int        MR_rbmmpu_max;
+    int        MR_rbmmpu_total;
+};
+
+extern MR_RegionProfUnit    MR_rbmmp_words_used;
+extern MR_RegionProfUnit    MR_rbmmp_regions_used;
+extern MR_RegionProfUnit    MR_rbmmp_pages_used;
+extern unsigned int         MR_rbmmp_page_requested;
+extern unsigned int         MR_rbmmp_biggest_region_size;
+extern MR_RegionProfUnit    MR_rbmmp_regions_saved_at_commit;
+extern unsigned int         MR_rbmmp_regions_protected_at_ite;
+extern unsigned int         MR_rbmmp_snapshots_saved_at_ite;
+extern unsigned int         MR_rbmmp_regions_protected_at_disj;
+extern unsigned int         MR_rbmmp_snapshots_saved_at_disj;
+extern double               MR_rbmmp_page_utilized;
+
+#endif /* MR_RBMM_PROFILING. */
+
+extern  void    MR_region_update_profiling_unit(
+                    MR_RegionProfUnit *profiling_unit, int quantity);
+extern  void    MR_region_profile_destroyed_region(MR_Region *);
+extern  void    MR_region_profile_restore_from_snapshot(MR_RegionSnapshot *);
+extern  int     MR_region_get_number_of_pages(MR_RegionPage *,
+                    MR_RegionPage *);
+extern  void    MR_region_print_profiling_info(void);
+
+/*---------------------------------------------------------------------------*/
+
+#endif  /* MR_USE_REGIONS */
+
+#endif  /* MERCURY_REGION_H */
Index: runtime/mercury_types.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_types.h,v
retrieving revision 1.51
diff -u -b -r1.51 mercury_types.h
--- runtime/mercury_types.h	12 Sep 2007 06:21:16 -0000	1.51
+++ runtime/mercury_types.h	8 Oct 2007 07:16:55 -0000
@@ -295,4 +295,11 @@
 typedef struct MR_ProcTableInfo_Struct          MR_ProcTableInfo;
 typedef MR_ProcTableInfo                        *MR_ProcTableInfoPtr;
 
+typedef struct MR_Region_Struct                 MR_Region;
+typedef struct MR_RegionPage_Struct             MR_RegionPage;
+typedef struct MR_RegionSnapshot_Struct         MR_RegionSnapshot;
+typedef struct MR_RegionDisjProtect_Struct      MR_RegionDisjProtect;
+typedef struct MR_RegionIteProtect_Struct       MR_RegionIteProtect;
+typedef struct MR_RegionProfUnit_Struct         MR_RegionProfUnit;
+
 #endif /* not MERCURY_TYPES_H */
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/c_interface/standalone_c
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
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 slice
cvs diff: Diffing ssdb
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/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/tabling
Index: tests/tabling/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/tabling/Mmakefile,v
retrieving revision 1.48
diff -u -b -r1.48 Mmakefile
--- tests/tabling/Mmakefile	21 Aug 2007 16:52:43 -0000	1.48
+++ tests/tabling/Mmakefile	8 Oct 2007 12:35:02 -0000
@@ -130,7 +130,8 @@
 ALL_MINIMAL_PROGS = $(MINIMAL_NONLOOP_PROGS)
 
 ifneq "$(findstring .gc,$(GRADE))" ""
-	ifneq "$(findstring mm,$(GRADE))" ""
+	# The substitution is there to avoid unwanted "mm" matches from "rbmm".
+	ifneq "$(findstring mm,$(subst rbmm,x,$(GRADE)))" ""
 		PROGS0=$(ALL_SIMPLE_PROGS) $(ALL_MINIMAL_PROGS)
 		NONLOOP_PROGS=$(SIMPLE_NONLOOP_PROGS) \
 				$(MINIMAL_NONLOOP_PROGS)
@@ -142,8 +143,9 @@
 	PROGS0=
 endif
 
-# Tabling is buggy in the lowlevel .par grades so it's
-# disabled for now.
+# Tabling is buggy in the lowlevel .par grades so it's disabled for now.
+# XXX What is the bug? If it is lack of synchronization on table updates,
+# why are these tests enabled for hlc par grades?
 ifeq "$(findstring .par,$(GRADE))" ""
 	PROGS=$(PROGS0)
 else
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
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