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

Quan Phan quan.phan at cs.kuleuven.be
Sat Oct 6 09:20:32 AEST 2007


Hi,

Estimated hours taken: 50h.
Branch: main.

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

This advanced support deals with the resurrection of regions
and provides the ability of instant reclaiming when backtracking happens.
The support is provided for if-then-elses, disjunctions, and commit operations.
The technical details of the advanced support is documented in a seperate
document.

Make use of the rbmm_goal_info when generating the backtracking-support code
for if-then-elses, disjunctions and commit operations.

library/region_builtin.m:

runtime/mercury_region.h
runtime/mercury_region.c
runtime/Mmakefile

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,
	just as 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.
	Add XXX comment for the wrong protection of regions.

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. It is a workaround and is probably not the way to
	go.

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

runtime/mercury_region.h
runtime/mercury_region.c
	Implementation of the region runtime system.

	I also implement the profiler and debugging messages here. They can be
	turned on and off by MR_RBMM_PROFILING and MR_RBMM_DEBUG flags. I
	am not sure that this is a correct way or not so currently the 2 flags
	have to be changed manually and require re-compilation of the compiler.

The diff is below.

Regards,
Quan.


-------------- next part --------------
cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bench
cvs diff: Diffing bench/progs
cvs diff: Diffing bench/progs/compress
cvs diff: Diffing bench/progs/icfp2000
cvs diff: Diffing bench/progs/icfp2001
cvs diff: Diffing bench/progs/nuc
cvs diff: Diffing bench/progs/ray
cvs diff: Diffing bench/progs/tree234
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 browser/test
cvs diff: Diffing bytecode
cvs diff: Diffing bytecode/test
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 -r1.350 code_info.m
--- compiler/code_info.m	1 Oct 2007 04:06:47 -0000	1.350
+++ compiler/code_info.m	5 Oct 2007 22:50:34 -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,75 +2298,78 @@
 %---------------------------------------------------------------------------%
 
 :- 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,
-
-        RemovedRegionVarList = set.to_sorted_list(RemovedRegionVars),
-
-        NumRemovedRegionVars = list.length(RemovedRegionVarList),
-
-        code_info.get_globals(!.CI, Globals),
-        globals.lookup_int_option(Globals, size_region_commit_fixed,
-            FixedSize),
-        globals.lookup_int_option(Globals, size_region_commit_entry,
-            EntrySize),
-        FrameSize = FixedSize + EntrySize * NumRemovedRegionVars,
-        Items = list.duplicate(FrameSize, slot_region_commit),
-        acquire_several_temp_slots(Items, non_persistent_temp_slot,
-            StackVars, MainStackId, FirstSlotNum, LastSlotNum, !CI),
-        EmbeddedStackFrame = embedded_stack_frame_id(MainStackId,
-            FirstSlotNum, LastSlotNum),
-        FirstSavedRegionAddr =
-            first_nonfixed_embedded_slot_addr(EmbeddedStackFrame, FixedSize),
-        acquire_reg(reg_r, NumRegLval, !CI),
-        acquire_reg(reg_r, AddrRegLval, !CI),
-        PushInitCode = node([
-            llds_instr(
-                push_region_frame(region_stack_commit, EmbeddedStackFrame),
-                "Save stack pointer of embedded region commit stack"),
-            llds_instr(
-                assign(NumRegLval, const(llconst_int(0))),
-                "Initialize number of unprotected live regions"),
-            llds_instr(
-                assign(AddrRegLval, FirstSavedRegionAddr),
-                "Initialize pointer to the next unprotected live region slot")
-        ]),
-        save_unprotected_live_regions(NumRegLval, AddrRegLval,
-            EmbeddedStackFrame, RemovedRegionVarList, FillCode, !CI),
-        SetCode = node([
-            llds_instr(
-                region_set_fixed_slot(region_set_commit_num_entries,
-                    EmbeddedStackFrame, lval(NumRegLval)),
-                "Store the number of unprotected live regions")
-        ]),
-        release_reg(NumRegLval, !CI),
-        release_reg(AddrRegLval, !CI),
+        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(CommitRemovedRegionVars),
+
+            NumRemovedRegionVars = list.length(RemovedRegionVarList),
+
+            code_info.get_globals(!.CI, Globals),
+            globals.lookup_int_option(Globals, size_region_commit_fixed,
+                FixedSize),
+            globals.lookup_int_option(Globals, size_region_commit_entry,
+                EntrySize),
+            FrameSize = FixedSize + EntrySize * NumRemovedRegionVars,
+            Items = list.duplicate(FrameSize, slot_region_commit),
+            acquire_several_temp_slots(Items, non_persistent_temp_slot,
+                StackVars, MainStackId, FirstSlotNum, LastSlotNum, !CI),
+            EmbeddedStackFrame = embedded_stack_frame_id(MainStackId,
+                FirstSlotNum, LastSlotNum),
+            FirstSavedRegionAddr = first_nonfixed_embedded_slot_addr(
+                EmbeddedStackFrame, FixedSize),
+            acquire_reg(reg_r, NumRegLval, !CI),
+            acquire_reg(reg_r, AddrRegLval, !CI),
+            PushInitCode = node([
+                llds_instr(
+                    push_region_frame(region_stack_commit, EmbeddedStackFrame),
+                    "Save stack pointer of embedded region commit stack"),
+                llds_instr(
+                    assign(NumRegLval, const(llconst_int(0))),
+                    "Initialize number of unprotected live regions"),
+                llds_instr(
+                    assign(AddrRegLval, FirstSavedRegionAddr),
+                    "Initialize pointer to the next unprotected live" ++
+                    " region slot")
+            ]),
+            save_unprotected_live_regions(NumRegLval, AddrRegLval,
+                EmbeddedStackFrame, RemovedRegionVarList, FillCode, !CI),
+            SetCode = node([
+                llds_instr(
+                    region_set_fixed_slot(region_set_commit_num_entries,
+                        EmbeddedStackFrame, lval(NumRegLval)),
+                    "Store the number of unprotected live regions")
+            ]),
+            release_reg(NumRegLval, !CI),
+            release_reg(AddrRegLval, !CI),
 
-        RegionCommitFrameInfo = region_commit_stack_frame(EmbeddedStackFrame,
-            StackVars),
-        MaybeRegionCommitFrameInfo = yes(RegionCommitFrameInfo),
+            RegionCommitFrameInfo =
+                region_commit_stack_frame(EmbeddedStackFrame, StackVars),
+            MaybeRegionCommitFrameInfo = yes(RegionCommitFrameInfo),
 
-        Code = tree_list([
-            PushInitCode,
-            FillCode,
-            SetCode
-        ])
+            Code = tree_list([
+                PushInitCode,
+                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 -r1.19 commit_gen.m
--- compiler/commit_gen.m	27 Sep 2007 10:42:05 -0000	1.19
+++ compiler/commit_gen.m	5 Oct 2007 22:50:34 -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 -r1.105 disj_gen.m
--- compiler/disj_gen.m	27 Sep 2007 10:42:05 -0000	1.105
+++ compiler/disj_gen.m	5 Oct 2007 22:50:35 -0000
@@ -386,16 +386,38 @@
         % 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
-        ;
+        % 
+        % Now this is handled as below.
+        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),
+            ( if
+                    set.empty(DisjCreatedRegionVars),
+                    set.empty(DisjRemovedRegionVars),
+                    set.empty(DisjAllocRegionVars)
+              then
+                    FirstRegionCode = empty,
+                    LaterRegionCode = empty,
+                    LastRegionCode = empty,
+                    RegionStackVarsToRelease = []
+              else
+                    % 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
+            )
         )
     ),
 
@@ -445,7 +467,7 @@
     unexpected(this_file, "generate_disjuncts: empty disjunction!").
 generate_disjuncts([Goal0 | Goals], CodeModel, FullResumeMap,
         MaybeEntryResumePoint, HijackInfo, DisjGoalInfo, EndLabel, ReclaimHeap,
-        MaybeHpSlot0, MaybeTicketSlot, LaterRegionCode, LastRegionCode,
+        MaybeHpSlot0, MaybeTicketSlot, LaterRegionCode0, LastRegionCode,
         BranchStart0, MaybeEnd0, MaybeEnd, Code, !CI) :-
 
     reset_to_position(BranchStart0, !CI),
@@ -475,11 +497,13 @@
 
             % Reset the solver state if necessary.
             maybe_reset_ticket(MaybeTicketSlot, reset_reason_undo,
-                RestoreTicketCode)
+                RestoreTicketCode),
+            LaterRegionCode = LaterRegionCode0
         ;
             MaybeEntryResumePoint = no,
             RestoreHpCode = empty,
-            RestoreTicketCode = empty
+            RestoreTicketCode = empty,
+            LaterRegionCode = empty
         ),
 
         % The pre_goal_update sanity check insists on no_resume_point, to make
@@ -573,7 +597,7 @@
         generate_disjuncts(Goals, CodeModel, FullResumeMap,
             yes(NextResumePoint), HijackInfo, DisjGoalInfo,
             EndLabel, ReclaimHeap, MaybeHpSlot, MaybeTicketSlot,
-            LaterRegionCode, LastRegionCode, BranchStart,
+            LaterRegionCode0, LastRegionCode, BranchStart,
             MaybeEnd1, MaybeEnd, RestCode, !CI),
 
         Code = tree_list([
@@ -654,6 +678,10 @@
         % variables that are statically known to be already protected by
         % an outer disjunction, but we don't yet have the program analysis
         % required to gather such information.
+        % XXX Protecting only forward live region variables is not enough,
+        % therefore not correct. We need to protect backward live region
+        % variables also. How can we find this information? It seems that we
+        % need to run liveness.m first.
         ProtectRegionVars = LiveRegionVars,
         SnapshotRegionVars = LiveRegionVars,
 
Index: compiler/ite_gen.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/ite_gen.m,v
retrieving revision 1.102
diff -u -r1.102 ite_gen.m
--- compiler/ite_gen.m	1 Oct 2007 04:06:48 -0000	1.102
+++ compiler/ite_gen.m	5 Oct 2007 22:50:35 -0000
@@ -559,144 +559,163 @@
         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),
-        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,
-
-        ProtectRegionVars = set.intersect(LiveRegionVars,
-            CondRemovedRegionVars),
-        SnapshotRegionVars0 = set.intersect(LiveRegionVars,
-            CondAllocRegionVars),
-        ( set.empty(UnprotectedRemovedAtStartOfElse) ->
-            SnapshotRegionVars = SnapshotRegionVars0
-        ;
-            SnapshotRegionVars = set.difference(SnapshotRegionVars0,
-                UnprotectedRemovedAtStartOfElse)
-        ),
-
-        ProtectRegionVarList = set.to_sorted_list(ProtectRegionVars),
-        SnapshotRegionVarList = set.to_sorted_list(SnapshotRegionVars),
-
-        list.length(ProtectRegionVarList, NumProtectRegionVars),
-        list.length(SnapshotRegionVarList, NumSnapshotRegionVars),
-
-        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),
-        FrameSize = FixedSize
-            + ProtectSize * NumProtectRegionVars
-            + SnapshotSize * NumSnapshotRegionVars,
-
-        Items = list.duplicate(FrameSize, slot_region_ite),
-        acquire_several_temp_slots(Items, non_persistent_temp_slot,
-            StackVars, MainStackId, FirstSlotNum, LastSlotNum, !CI),
-        EmbeddedStackFrameId = embedded_stack_frame_id(MainStackId,
-            FirstSlotNum, LastSlotNum),
-        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),
-                "Save stack pointer of embedded region ite stack"),
-            llds_instr(
-                assign(ProtectNumRegLval, const(llconst_int(0))),
-                "Initialize number of protect_infos"),
-            llds_instr(
-                assign(SnapshotNumRegLval, const(llconst_int(0))),
-                "Initialize number of snapshot_infos"),
-            llds_instr(
-                assign(AddrRegLval, FirstNonFixedAddr),
-                "Initialize pointer to nonfixed part of embedded frame")
-        ]),
-        ite_protect_regions(ProtectNumRegLval, AddrRegLval,
-            EmbeddedStackFrameId, ProtectRegionVarList, ProtectRegionCode,
-            !CI),
-        ite_alloc_snapshot_regions(SnapshotNumRegLval, AddrRegLval,
-            EmbeddedStackFrameId, RemovedAtStartOfElse, SnapshotRegionVarList,
-            SnapshotRegionCode, !CI),
-        SetCode = node([
-            llds_instr(
-                region_set_fixed_slot(region_set_ite_num_protects,
-                    EmbeddedStackFrameId, lval(ProtectNumRegLval)),
-                "Store the number of protect_infos"),
-            llds_instr(
-                region_set_fixed_slot(region_set_ite_num_snapshots,
-                    EmbeddedStackFrameId, lval(SnapshotNumRegLval)),
-                "Store the number of snapshot_infos")
-        ]),
-        release_reg(ProtectNumRegLval, !CI),
-        release_reg(SnapshotNumRegLval, !CI),
-        release_reg(AddrRegLval, !CI),
-
-        CondCodeModel = goal_info_get_code_model(CondGoalInfo),
+        MaybeRbmmInfo = goal_info_get_maybe_rbmm(CondGoalInfo),
         (
-            CondCodeModel = model_non,
-            CondKind = region_ite_nondet_cond,
-            MaybeEmbeddedStackFrameId = yes(EmbeddedStackFrameId)
-        ;
-            CondCodeModel = model_semi,
-            CondKind = region_ite_semidet_cond,
+            MaybeRbmmInfo = no,
+            CondCode = empty,
+            ThenCode = empty,
+            ElseCode = empty,
+            StackVars = [],
             MaybeEmbeddedStackFrameId = no
         ;
-            CondCodeModel = model_det,
-            unexpected(this_file, "maybe_create_ite_region_frame: det cond")
-        ),
-
-        CondCode = tree_list([
-            PushInitCode,
-            ProtectRegionCode,
-            SnapshotRegionCode,
-            SetCode
-        ]),
-        ThenCode = node([
-            llds_instr(
-                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),
-                    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.
+            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),
+
+                % 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),
+                SnapshotRegionVars0 = set.intersect(LiveRegionVars,
+                    CondAllocRegionVars),
+                ( set.empty(UnprotectedRemovedAtStartOfElse) ->
+                    SnapshotRegionVars = SnapshotRegionVars0
+                ;
+                    SnapshotRegionVars = set.difference(SnapshotRegionVars0,
+                        UnprotectedRemovedAtStartOfElse)
+                ),
+
+                ProtectRegionVarList = set.to_sorted_list(ProtectRegionVars),
+                SnapshotRegionVarList = set.to_sorted_list(SnapshotRegionVars),
+
+                list.length(ProtectRegionVarList, NumProtectRegionVars),
+                list.length(SnapshotRegionVarList, NumSnapshotRegionVars),
+
+                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),
+                FrameSize = FixedSize
+                    + ProtectSize * NumProtectRegionVars
+                    + SnapshotSize * NumSnapshotRegionVars,
+
+                Items = list.duplicate(FrameSize, slot_region_ite),
+                acquire_several_temp_slots(Items, non_persistent_temp_slot,
+                    StackVars, MainStackId, FirstSlotNum, LastSlotNum, !CI),
+                EmbeddedStackFrameId = embedded_stack_frame_id(MainStackId,
+                    FirstSlotNum, LastSlotNum),
+                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),
+                        "Save stack pointer of embedded region ite stack"),
+                    llds_instr(
+                        assign(ProtectNumRegLval, const(llconst_int(0))),
+                        "Initialize number of protect_infos"),
+                    llds_instr(
+                        assign(SnapshotNumRegLval, const(llconst_int(0))),
+                        "Initialize number of snapshot_infos"),
+                    llds_instr(
+                        assign(AddrRegLval, FirstNonFixedAddr),
+                        "Initialize pointer to nonfixed part of" ++
+                        " embedded frame")
+                ]),
+                ite_protect_regions(ProtectNumRegLval, AddrRegLval,
+                    EmbeddedStackFrameId, ProtectRegionVarList,
+                    ProtectRegionCode, !CI),
+                ite_alloc_snapshot_regions(SnapshotNumRegLval, AddrRegLval,
+                    EmbeddedStackFrameId, RemovedAtStartOfElse,
+                    SnapshotRegionVarList, SnapshotRegionCode, !CI),
+                SetCode = node([
+                    llds_instr(
+                        region_set_fixed_slot(region_set_ite_num_protects,
+                            EmbeddedStackFrameId, lval(ProtectNumRegLval)),
+                        "Store the number of protect_infos"),
+                    llds_instr(
+                        region_set_fixed_slot(region_set_ite_num_snapshots,
+                            EmbeddedStackFrameId, lval(SnapshotNumRegLval)),
+                        "Store the number of snapshot_infos")
+                ]),
+                release_reg(ProtectNumRegLval, !CI),
+                release_reg(SnapshotNumRegLval, !CI),
+                release_reg(AddrRegLval, !CI),
+
+                CondCodeModel = goal_info_get_code_model(CondGoalInfo),
+                (
+                    CondCodeModel = model_non,
+                    CondKind = region_ite_nondet_cond,
+                    MaybeEmbeddedStackFrameId = yes(EmbeddedStackFrameId)
+                ;
+                    CondCodeModel = model_semi,
+                    CondKind = region_ite_semidet_cond,
+                    MaybeEmbeddedStackFrameId = no
+                ;
+                    CondCodeModel = model_det,
+                    unexpected(this_file,
+                        "maybe_create_ite_region_frame: det cond")
+                ),
+
+                CondCode = tree_list([
+                    PushInitCode,
+                    ProtectRegionCode,
+                    SnapshotRegionCode,
+                    SetCode
+                ]),
+                ThenCode = node([
+                    llds_instr(
+                        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),
+                            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.
+            )
+        )
     ).
 
     % 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 -r1.587 options.m
--- compiler/options.m	4 Oct 2007 09:04:43 -0000	1.587
+++ compiler/options.m	5 Oct 2007 22:50:39 -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
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing detail
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
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/concurrency/samples
cvs diff: Diffing extras/concurrency/samples/midi
cvs diff: Diffing extras/concurrency/tests
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/exceptions
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/lazy_evaluation/examples
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/opium_m
cvs diff: Diffing extras/opium_m/non-regression-tests
cvs diff: Diffing extras/opium_m/scripts
cvs diff: Diffing extras/opium_m/source
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/stream
cvs diff: Diffing extras/stream/tests
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/library
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 -r1.1 region_builtin.m
--- library/region_builtin.m	12 Jun 2007 03:22:25 -0000	1.1
+++ library/region_builtin.m	5 Oct 2007 22:50:39 -0000
@@ -38,30 +38,36 @@
     %
 :- impure pred remove_region(region::in) is det.
 
+:- impure pred print_rbmm_profiling_info 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.\");
+    Region = MR_region_create_region();
 ").
 
 :- pragma foreign_proc("C",
     remove_region(Region::in),
     [will_not_call_mercury],
 "
-    /* Region */
-    MR_fatal_error(\"region_builtin.remove_region/1 NYI.\");
+    MR_region_remove_region(Region);
+").
+
+:- pragma foreign_proc("C",
+    print_rbmm_profiling_info,
+    [will_not_call_mercury],
+"
+    MR_print_profiling_info();
 ").
 
 %-----------------------------------------------------------------------------%
cvs diff: Diffing lp_solve
cvs diff: Diffing lp_solve/lp_examples
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing quickcheck
cvs diff: Diffing quickcheck/tutes
cvs diff: Diffing readline
cvs diff: Diffing readline/doc
cvs diff: Diffing readline/examples
cvs diff: Diffing readline/shlib
cvs diff: Diffing readline/support
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 -r1.142 Mmakefile
--- runtime/Mmakefile	3 Oct 2007 12:11:57 -0000	1.142
+++ runtime/Mmakefile	5 Oct 2007 22:50:40 -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_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	5 Oct 2007 22:50:40 -0000
@@ -0,0 +1,781 @@
+/*
+** 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 authors: qph
+*/
+
+#include "mercury_imp.h"
+
+#include "mercury_region.h"
+
+#if !defined(MR_USE_REGIONS)
+MR_Region*
+MR_region_create_region() {
+    return NULL;
+}
+
+void
+MR_region_remove_region(MR_Region *region) {}
+
+#else /* defined(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_Prof_Unit    words_used = {0, 0, 0};
+MR_Prof_Unit    regions_used = {0, 0, 0};
+MR_Prof_Unit    pages_used = {0, 0, 0};
+unsigned int    pages_requested = 0;
+unsigned int    biggest_region_size = 0;
+MR_Prof_Unit    regions_saved_at_commit = {0, 0, 0};
+unsigned int regions_protected_at_ite;
+unsigned int snapshots_saved_at_ite;
+unsigned int regions_protected_at_disj;
+unsigned int snapshots_saved_at_disj;
+double       page_utilized;
+
+#endif
+
+/*---------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Page operations. */
+
+/* Request for more pages from the operating system. */
+static MR_RegionPage *request_pages(void);
+
+static MR_RegionPage * 
+request_pages() {
+    MR_RegionPage *pages;
+    int i;
+    pages = (MR_RegionPage *) MR_malloc(
+            MR_REGION_NUM_PAGES_TO_REQUEST*sizeof(MR_RegionPage));
+    if (!pages) {
+        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)
+    pages_requested += MR_REGION_NUM_PAGES_TO_REQUEST;
+#endif
+    return &(pages[MR_REGION_NUM_PAGES_TO_REQUEST - 1]);
+}
+
+/* Take a page from the free page list. */
+static MR_RegionPage *get_free_page(void);
+
+static MR_RegionPage *
+get_free_page() {
+    if (MR_region_free_page_list == 0) {
+        MR_region_free_page_list = request_pages();
+    }
+
+    MR_RegionPage *page = MR_region_free_page_list;
+    MR_region_free_page_list = MR_region_free_page_list->MR_regionpage_next;
+    /* Disconnected the first free page from the free list. */
+    page->MR_regionpage_next = NULL;
+#if defined(MR_RBMM_PROFILING)
+    update_profiling_unit(&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() {
+    /* This is the first page of the region. */
+    MR_RegionPage *page = 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.
+    */
+    MR_Region *region = (MR_Region *)(page->MR_regionpage_space);
+    region->next_available_word =
+        (MR_Word *)(page->MR_regionpage_space + word_sizeof(MR_Region));
+    region->last_page = page;
+    region->available_space =
+        MR_REGION_PAGE_SPACE_SIZE - word_sizeof(MR_Region);
+    region->removal_counter = 1;
+    region->sequential_number = MR_region_sequence_number++;
+    region->logical_removed = 0;
+    region->ite_protected = NULL;
+    region->disj_protected = NULL;
+    region->commit_frame = NULL;
+    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->previous_region = region;
+    }
+    region->next_region = MR_live_region_list;
+    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)
+    update_profiling_unit(&regions_used, 1);
+    ((MR_RegionPage *)region)->allocated_size = 0;
+#endif
+
+    return region;
+}
+
+static void nullify_entries_in_commit_stack(MR_Region *region);
+static void nullify_in_commit_frame(MR_Word *frame, MR_Region *region);
+static void nullify_in_ite_frame(MR_Region *region);
+
+static void
+nullify_entries_in_commit_stack(MR_Region *region) {
+    MR_Word *frame = region->commit_frame;
+    while (frame != NULL) {
+        nullify_in_commit_frame(frame, region);
+        frame = (MR_Word *) *frame;
+    }
+}
+
+static void
+nullify_in_commit_frame(MR_Word *frame, MR_Region *region) {
+    int num_saved_regions = *(frame + 
+            MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);
+    MR_Word *saved_region = frame + MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION;
+    int i;
+    /*
+    ** 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
+nullify_in_ite_frame(MR_Region *region) {
+    MR_Word *ite_frame = region->ite_protected;
+    int num_protected_regions = *((MR_Word *)
+            (ite_frame + MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS));
+    int i;
+    MR_Word *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->commit_frame != NULL) {
+        nullify_entries_in_commit_stack(region);
+    } else {}
+
+    /* Break the region from the live region list. */
+    if (region == MR_live_region_list) {
+        /* Detach the newest. */
+        MR_live_region_list = region->next_region;
+    } else {
+        region->previous_region->next_region = region->next_region;
+        if (region->next_region != NULL) {
+            /* Detach one in the middle. */
+            region->next_region->previous_region = region->previous_region;
+        }
+    }
+
+    /* Return the page list of the region to the free page list. */
+    MR_region_return_page_list((MR_RegionPage *)region, region->last_page);
+
+    /* Collect profiling information. */
+    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->disj_protected == NULL) {
+        MR_region_destroy_region(region);
+    } else { /* Logically removed. */
+        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->disj_protected == NULL) {
+        nullify_in_ite_frame(region);
+        MR_region_destroy_region(region);
+    } else { /* Logically removed. */
+        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->ite_protected == NULL && region->disj_protected == NULL) {
+        MR_region_destroy_region(region);
+    } else { /* Logically removed. */
+        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->commit_frame != NULL) {
+            region->destroy_at_commit = 1;
+        } else {}
+#if defined(MR_RBMM_DEBUG)
+        MR_region_logically_remove_region_msg(region);
+#endif
+    }
+}
+
+static void extend_region(MR_Region *);
+
+MR_Word *
+MR_region_alloc(MR_Region *region, unsigned int words) {
+    if (region->available_space < words) {
+        extend_region(region);
+    }
+    MR_Word *allocated_cell = region->next_available_word;
+    /* Allocate in the increasing direction of address. */
+    region->next_available_word += words;
+    region->available_space -= words;
+#if defined(MR_RBMM_PROFILING)
+    update_profiling_unit(&words_used, words);
+    ((MR_RegionPage *)region)->allocated_size += words;
+#endif
+    return allocated_cell;
+}
+
+static void
+extend_region(MR_Region *region) {
+    MR_RegionPage *page = get_free_page();
+    region->last_page->MR_regionpage_next = page;
+    region->last_page = page;
+    region->next_available_word = (MR_Word *)page->MR_regionpage_space;
+    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->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->commit_frame = (MR_Word *)(*(region->commit_frame));
+                 */
+                MR_fatal_error("MR_destroy_marked_old_regions_at_commit: need to rethink.");
+            }
+        } else {}
+    }
+}
+
+/* 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 = MR_live_region_list;
+    while (region != NULL && 
+            region->sequential_number > saved_region_seq_number) {
+        if (region->destroy_at_commit) {
+            MR_region_destroy_region(region);
+        } else {
+            region = region->next_region;
+        }
+    }
+}
+
+//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;
+//}
+
+/*---------------------------------------------------------------------------*/
+/* Debugging messages for RBMM. */
+#if defined(MR_RBMM_DEBUG)
+static int  get_frame_number(MR_Word *);
+
+static int
+get_frame_number(MR_Word *frame) {
+    int number = 0;
+    while (frame != NULL) {
+        number++;
+        frame = (MR_Word *)(*frame);
+    }
+    return number;
+}
+
+void
+MR_region_create_region_msg(MR_Region *region) {
+    printf("Create region #%d:\n", region->sequential_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->sequential_number);
+    printf("\tHandle: %d\n", region);
+    printf("\tLogically removed: %d\n", region->logical_removed);
+    printf("\tProtected by ite frame #%d: %d\n",
+            get_frame_number(region->ite_protected), region->ite_protected);
+    printf("\tProtected by disj frame #%d: %d\n",
+            get_frame_number(region->disj_protected),
+            region->disj_protected);
+    printf("\tSaved in commit frame #%d: %d\n",
+            get_frame_number(region->commit_frame), region->commit_frame);
+    printf("\tBe destroyed at commit: %d\n", region->destroy_at_commit);
+}
+
+void
+MR_region_push_ite_frame_msg(MR_Word *ite_frame) {
+    int frame_number = get_frame_number(ite_frame);
+    printf("Push ite frame #%d: %d\n", frame_number, ite_frame);
+    printf("\tPrevious frame at push #%d: %d\n",
+            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", get_frame_number(ite_frame), ite_frame);
+    printf("\tPrevious frame #%d: %d\n",
+            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) {
+    int num_protected_regions = *(ite_frame +
+            MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    MR_Word *first_protected_region = ite_frame + MR_REGION_FRAME_FIXED_SIZE; 
+    int i;
+    /*
+    ** 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++) {
+        MR_Word *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) {
+    int num_snapshots = *(ite_frame + MR_REGION_FRAME_NUMBER_SNAPSHOTS);
+    int num_protected_regions = *(ite_frame +
+            MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    MR_Word *first_snapshot = ite_frame + MR_REGION_FRAME_FIXED_SIZE +
+        num_protected_regions * MR_REGION_ITE_PROT_SIZE;
+    int i;
+
+    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++) {
+        MR_Word *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", get_frame_number(disj_frame),
+            disj_frame);
+    printf("\tPrevious frame at push #%d: %d\n",
+            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", get_frame_number(disj_frame), disj_frame);
+    printf("\tPrevious frame #%d: %d\n",
+            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) {
+    int num_protected_regions = *(disj_frame +
+            MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    MR_Word *first_protected_region = disj_frame + MR_REGION_FRAME_FIXED_SIZE; 
+    int i;
+
+    /*
+    ** 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++) {
+        MR_Word *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) {
+    int num_snapshots = *(disj_frame + MR_REGION_FRAME_NUMBER_SNAPSHOTS);
+    int num_protected_regions = *(disj_frame +
+            MR_REGION_FRAME_NUMBER_PROTECTED_REGIONS);
+    MR_Word *first_snapshot = disj_frame + MR_REGION_FRAME_FIXED_SIZE +
+        num_protected_regions * MR_REGION_DISJ_PROT_SIZE;
+    int i;
+
+    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++) {
+        MR_Word *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", get_frame_number(commit_frame),
+            commit_frame);
+    printf("\tPrevious frame at push #%d: %d\n",
+            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) {
+    int i;
+    int num_saved_regions = *(commit_frame +
+            MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);
+    MR_Word *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++) {
+        MR_Word *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) {
+    int num_saved_regions = *(commit_frame +
+            MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);
+    MR_Word *first_saved_region =
+        commit_frame + MR_REGION_COMMIT_FRAME_FIXED_SIZE; 
+    int i;
+
+    /*
+    ** 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++) {
+        MR_Word *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
+update_profiling_unit(MR_Prof_Unit *profiling_unit, int quantity) {
+    profiling_unit->current += quantity;
+    if (quantity > 0) {
+        profiling_unit->total += quantity;
+    } else {}
+    if (profiling_unit->current > profiling_unit->max) {
+        profiling_unit->max = profiling_unit->current;
+    } else {}
+}
+
+void
+profile_destroyed_region(MR_Region *region) {
+    int allocated_size_of_region;
+
+    update_profiling_unit(&regions_used, -1);
+    update_profiling_unit(&pages_used,
+            -get_number_of_pages((MR_RegionPage *)region, region->last_page));
+    allocated_size_of_region = ((MR_RegionPage *)region)->allocated_size;
+    update_profiling_unit(&words_used, -allocated_size_of_region);
+    if (allocated_size_of_region > biggest_region_size)
+        biggest_region_size = allocated_size_of_region;
+}
+
+void
+profile_restore_from_snapshot(MR_RegionSnapshot *snapshot) {
+    MR_Region *restoring_region = snapshot->region;
+    MR_RegionPage *first_new_page =
+        snapshot->saved_last_page->MR_regionpage_next;
+    int new_words;
+    if (first_new_page != NULL) {
+        int new_pages = get_number_of_pages(first_new_page,
+                 restoring_region->last_page);
+        update_profiling_unit(&pages_used, -new_pages);
+        new_words = (new_pages * MR_REGION_PAGE_SPACE_SIZE -
+                 restoring_region->available_space +
+                 snapshot->saved_available_space);
+    } else {
+        new_words = snapshot->saved_available_space -
+            restoring_region->available_space;
+    }
+    ((MR_RegionPage *)restoring_region)->allocated_size -= new_words;
+    update_profiling_unit(&words_used, -new_words);    
+}
+
+int
+get_number_of_pages(MR_RegionPage *from_page, MR_RegionPage *to_page) {
+    MR_RegionPage *page = from_page;
+    int 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;
+}
+
+static void print_profiling_unit(const char *str,
+        MR_Prof_Unit *profiling_unit);
+
+void
+print_profiling_unit(const char *str, MR_Prof_Unit *profiling_unit) {
+    printf(str);
+    printf("\n");
+    printf("\tTotal: %d.\n", profiling_unit->total);
+    printf("\tMaximum: %d.\n", profiling_unit->max);
+    printf("\tCurrent: %d.\n", profiling_unit->current);
+}
+
+void
+MR_print_profiling_info() {
+    print_profiling_unit("Regions:", &regions_used);
+    printf("Biggest region size: %d.\n", biggest_region_size);
+    print_profiling_unit("Words:", &words_used);
+    print_profiling_unit("Pages used:", &pages_used);
+    printf("Pages requested: %d.\n", pages_requested);
+}
+
+#else /* Not define MR_RBMM_PROFILING. */
+void
+update_profiling_unit(int p, int q) {}
+
+void
+profile_destroyed_region(MR_Region *r) {}
+
+void
+profile_restore_from_snapshot(MR_RegionSnapshot *s) {}
+
+int
+get_number_of_pages(MR_RegionPage *fp, MR_RegionPage *tp) {
+    return 0;
+}
+
+void
+MR_print_profiling_info() {}
+
+#endif /* End of Not define MR_RBMM_PROFILING. */
+#endif /* defined(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	5 Oct 2007 22:50:41 -0000
@@ -0,0 +1,954 @@
+/* 
+** 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
+
+#if !defined(MR_USE_REGIONS)
+
+/*
+** Some dummy definitions because the foreign code in region_builtin.m
+** requires them.
+*/
+typedef int MR_Region;
+extern  MR_Region   *MR_region_create_region(void);
+extern  void    MR_region_remove_region(MR_Region*);
+
+#else /* defined(MR_USE_REGIONS) */
+
+/*#define MR_RBMM_DEBUG
+#define MR_RBMM_PROFILING*/
+
+/* 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
+
+#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).
+*/
+typedef 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. */
+    struct MR_RegionPage_Struct     *MR_regionpage_next;
+
+#if defined(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                             allocated_size;
+#endif
+
+} MR_RegionPage;
+
+/*
+** 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.
+*/
+typedef 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.
+    */
+    struct MR_RegionPage_Struct     *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                         *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                         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                    removal_counter;
+
+    /* Sequential number of the region. */
+    MR_Word                         sequential_number;
+
+    /* If the region has been removed in forward execution. */
+    MR_Word                         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                         *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                         *disj_protected;
+
+    /* If the region is saved at this frame in the region_commit_stack. */
+    MR_Word                         *commit_frame;
+
+    /*
+    ** true if the region has been removed logically in a commit context and
+    ** therefore needs to be destroyed at commit.
+    */
+    MR_Word                         destroy_at_commit;
+
+    struct MR_Region_Struct         *previous_region;
+    struct MR_Region_Struct         *next_region;
+} MR_Region;
+
+/*
+** To save the current size of a region in preparation for instant reclaiming.
+*/
+typedef struct MR_RegionSnapshot_Struct {
+    struct MR_Region_Struct         *region;
+    struct MR_RegionPage_Struct     *saved_last_page;
+    MR_Word                         *saved_next_available_word;
+    MR_Word                         saved_available_space;
+} MR_RegionSnapshot;
+
+/* Protection information in a disj frame. */
+typedef struct MR_Disj_Protection_Struct {
+    struct MR_Region_Struct         *region;
+    /* XXX We no longer need to save ite_protected into a disj-frame*/
+    /*MR_Word                         *ite_protected;*/
+} MR_Disj_Protection;
+
+/*
+** 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 = (MR_Region *) (region_ptr);             \
+                if (region->disj_protected == NULL &&                       \
+                        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->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 = (MR_Region *)(region_ptr);              \
+                if (region->ite_protected != NULL ||                        \
+                        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 = (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 = (MR_Region *) (region_ptr);             \
+                if (region->disj_protected == NULL) {                       \
+                    MR_save_disj_protection(region, protection_block);      \
+                    (num_protected_regions)++;                              \
+                    MR_next_disj_protection_block(protection_block);        \
+                    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 = (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 = (MR_Region *) (region_ptr);             \
+                if (region->disj_protected == NULL &&                       \
+                        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)->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_region_frame_number_protected_regions(ite_sp);       \
+                int i;                                                      \
+                MR_Word *first_protected_region = (ite_sp) +                \
+                    MR_REGION_FRAME_FIXED_SIZE;                             \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    MR_Region *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_region_frame_number_protected_regions(ite_sp);       \
+                int i;                                                      \
+                MR_Word *first_protected_region = (ite_sp) +                \
+                    MR_REGION_FRAME_FIXED_SIZE;                             \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    MR_Region *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 =                           \
+                    *((commit_sp) +                                         \
+                            MR_REGION_COMMIT_FRAME_SEQUENCE_NUMBER);        \
+                MR_Word number_of_saved_regions =                           \
+                    *((commit_sp) +                                         \
+                            MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);   \
+                MR_Word *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 =                           \
+                    *((commit_sp) +                                         \
+                            MR_REGION_COMMIT_FRAME_NUMBER_SAVED_REGIONS);   \
+                MR_Word *first_saved_region_slot =                          \
+                    (commit_sp) + MR_REGION_COMMIT_FRAME_FIRST_SAVED_REGION;\
+                int i;                                                      \
+                for (i = 0; i < number_of_saved_regions; i++) {             \
+                    MR_Region *region = (MR_Region *)(                      \
+                            first_saved_region_slot +                       \
+                            i * MR_REGION_COMMIT_ENTRY_SIZE);               \
+                    if (region != NULL) {                                   \
+                        region->commit_frame = NULL;                        \
+                        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_region_debug_ite_frame(ite_sp);                          \
+                MR_Word num_protected_regions =                             \
+                    MR_region_frame_number_protected_regions(ite_sp);       \
+                int i;                                                      \
+                int first_protected_region = MR_REGION_FRAME_FIXED_SIZE;    \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    MR_Region *protected_region =                           \
+                        (MR_Region *)(*((ite_sp) +                          \
+                                      first_protected_region + i));         \
+                    /* Try to protect the region by an outer condition. */  \
+                    protected_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_region_frame_number_snapshots(ite_sp);               \
+                MR_Word first_snapshot_index;                               \
+                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 =                                 \
+                    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_Disj_Protection *first_block = (MR_Disj_Protection *)(   \
+                        disj_sp + MR_REGION_FRAME_FIXED_SIZE);              \
+                MR_Word num_protected_regions =                             \
+                    MR_region_frame_number_protected_regions(disj_sp);      \
+                MR_Word i;                                                  \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    MR_Disj_Protection *block = first_block + i;            \
+                    block->region->ite_protected = block->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_region_frame_number_snapshots(disj_sp);              \
+                MR_Word first_snapshot_index;                               \
+                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_Disj_Protection *first_block = (MR_Disj_Protection *)(   \
+                        disj_sp + MR_REGION_FRAME_FIXED_SIZE);              \
+                MR_Word num_protected_regions =                             \
+                    MR_region_frame_number_protected_regions(disj_sp);      \
+                MR_Word i;                                                  \
+                for (i = 0; i < num_protected_regions; i++) {               \
+                    MR_Disj_Protection *block = first_block + i;            \
+                    block->region->disj_protected = NULL;                 \
+                }                                                           \
+            } while (0)
+
+#define     MR_disj_frame_get_first_snapshot_index(disj_frame,              \
+                first_snapshot_index)                                       \
+            do {                                                            \
+                int 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_Disj_Protection *disj_prot = (MR_Disj_Protection *)(     \
+                        (protection_block));                                \
+                disj_prot->region = (region);                               \
+                /*disj_prot->ite_protected = (region)->ite_protected;*/     \
+            } while (0)
+
+#define     MR_next_disj_protection_block(block) (                          \
+            (block) = (MR_Word)(( (MR_Disj_Protection *)(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 = (MR_RegionSnapshot *)(        \
+                        (snapshot_block));                                  \
+                snapshot->region = (region);                                \
+                snapshot->saved_last_page = (region)->last_page;            \
+                snapshot->saved_next_available_word =                       \
+                    (region)->next_available_word;                          \
+                snapshot->saved_available_space = (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 *)(  \
+                        (frame) + (first_snapshot_index));                  \
+                int i;                                                      \
+                for (i = 0; i < (num_snapshots); i++) {                     \
+                    MR_RegionSnapshot *snapshot = first_snapshot + i;       \
+                    MR_Region *restoring_region = snapshot->region;         \
+                    MR_RegionPage *saved_last_page =                        \
+                        snapshot->saved_last_page;                          \
+                    MR_RegionPage *first_new_page =                         \
+                        saved_last_page->MR_regionpage_next;                \
+                    profile_restore_from_snapshot(snapshot);                \
+                    if (first_new_page != NULL) {                           \
+                        MR_region_return_page_list(first_new_page,          \
+                                restoring_region->last_page);               \
+                        restoring_region->last_page = saved_last_page;      \
+                    } else {/* No new page added. */ }                      \
+                    restoring_region->next_available_word =                 \
+                        snapshot->saved_next_available_word;                \
+                    restoring_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 *)(*((frame) + MR_REGION_FRAME_REGION_LIST));\
+                MR_Region *region = MR_live_region_list;                    \
+                while (region != saved_most_recent_region) {                \
+                    MR_Region *next_region = 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. */
+#if defined(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   /* Not define 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 /* Not defined MR_RBMM_DEBUG. */
+ 
+extern  void    MR_region_create_region_msg(MR_Region *);
+extern  void    MR_region_try_remove_region_msg(MR_Region *);
+extern  void    MR_region_region_struct_removal_info_msg(MR_Region *);
+extern  void    MR_region_destroy_region_msg(MR_Region *);
+extern  void    MR_region_logically_remove_region_msg(MR_Region *);
+
+extern  void    MR_region_push_ite_frame_msg(MR_Word *);
+extern  void    MR_region_ite_frame_msg(MR_Word *);
+extern  void    MR_region_ite_frame_protected_regions_msg(MR_Word *);
+extern  void    MR_region_ite_frame_snapshots_msg(MR_Word *);
+
+extern  void    MR_region_push_disj_frame_msg(MR_Word *);
+extern  void    MR_region_disj_frame_msg(MR_Word *);
+extern  void    MR_region_disj_frame_protected_regions_msg(MR_Word *);
+extern  void    MR_region_disj_frame_snapshots_msg(MR_Word *);
+
+extern  void    MR_region_push_commit_frame_msg(MR_Word *);
+extern  void    MR_region_commit_frame_msg(MR_Word *);
+extern  void    MR_region_commit_frame_saved_regions_msg(MR_Word *);
+extern  void    MR_region_destroy_marked_regions_at_commit_msg(int, int,
+                    MR_Word *);
+
+/*---------------------------------------------------------------------------*/
+/* Profiling RBMM. */
+#if defined(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
+*/
+typedef struct MR_Prof_Unit_Struct {
+    int        current;
+    int        max;
+    int        total;
+} MR_Prof_Unit;
+
+extern MR_Prof_Unit     words_used;
+extern MR_Prof_Unit     regions_used;
+extern MR_Prof_Unit     pages_used;
+extern unsigned int     page_requested;
+extern unsigned int     biggest_region_size;
+extern MR_Prof_Unit     regions_saved_at_commit;
+extern unsigned int     regions_protected_at_ite;
+extern unsigned int     snapshots_saved_at_ite;
+extern unsigned int     regions_protected_at_disj;
+extern unsigned int     snapshots_saved_at_disj;
+extern double           page_utilized;
+
+void    update_profiling_unit(MR_Prof_Unit *profiling_unit, int quantity);
+void    profile_destroyed_region(MR_Region *);
+void    profile_restore_from_snapshot(MR_RegionSnapshot *);
+int     get_number_of_pages(MR_RegionPage*, MR_RegionPage*);
+void    MR_print_profiling_info(void);
+
+#else /* Not define MR_RBMM_PROFILING. */
+void    update_profiling_unit(int profiling_unit, int quantity);
+void    profile_destroyed_region(MR_Region *);
+void    profile_restore_from_snapshot(MR_RegionSnapshot *);
+int     get_number_of_pages(MR_RegionPage *, MR_RegionPage *);
+void    MR_print_profiling_info(void);
+
+#endif /* Not define MR_RBMM_PROFILING. */
+
+/*---------------------------------------------------------------------------*/
+
+#endif /* defined(MR_USE_REGIONS) */
+#endif /* MERCURY_REGION_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 tools
cvs diff: Diffing trace
cvs diff: Diffing trax
cvs diff: Diffing trial
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax


More information about the reviews mailing list