[m-rev.] for review: Region runtime system

Quan Phan Quan.Phan at cs.kuleuven.be
Fri Jun 29 15:45:31 AEST 2007


Hi,

Estimated hours taken: 25.
Branch: main.

Implement the region runtime system and partly integrate it with the runtime
system of Mercury. This partly integrated runtime only supports "deterministic"
programs (deterministic programs in which no region-related actions happen in
condition of if-then-elses, at least no removals of regions happen).
For example, it now works with nrev, qsort, life, which are some
small deterministic benchmarks I used in my related paper.

runtime/Mmakefile.m:
	Link the files that implement the region runtime to the Mercury
	runtime system.

runtime/mercury_heap.m:
	Link the region runtime to the Mercury runtime when RBMM is used.
	Add a macro to allocate terms in a region.

runtime/mercury_region.h:
	New file.
	The interface to the region runtime.
runtime/mercury_region.c:
	New file.
	Implementation of the region runtime.
        - implement the regions themselves as a linked-list of pages.
        - basic methods for create regions, remove regions, and allocate
        words in regions.
        - implement the mechanism to support backtracking. This part has not
        been integrated into the runtime yet.


library/region_builtin.m:
        Change the builtins to make call to the region runtime interface.
 
Regards,
Quan

Index: Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/Mmakefile,v
retrieving revision 1.138
diff -u -u -r1.138 Mmakefile
--- Mmakefile	13 Feb 2007 01:58:55 -0000	1.138
+++ Mmakefile	20 Jun 2007 06:32:24 -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	\
@@ -181,6 +182,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: mercury_heap.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_heap.h,v
retrieving revision 1.38
diff -u -u -r1.38 mercury_heap.h
--- mercury_heap.h	14 Oct 2006 16:59:41 -0000	1.38
+++ mercury_heap.h	29 Jun 2007 00:38:48 -0000
@@ -50,6 +50,10 @@
   #endif
 #endif
 
+#if defined(MR_USE_REGIONS)
+  #include "mercury_region.h"
+#endif
+
 /***************************************************************************/
 
 /*
@@ -225,6 +229,22 @@
 
 #endif /* not MR_CONSERVATIVE_GC */
 
+#if defined(MR_USE_REGIONS)
+  #define   MR_tag_alloc_in_region(dest, tag, region, count)                \
+            (                                                               \
+                (dest) = (MR_Word) MR_mkword(tag,                           \
+                            (MR_Word)                                       \
+                            ((MR_Word *) MR_region_alloc_in_region(         \
+                                         region, (count)) )),               \
+                (void) 0                                                    \
+            )
+
+#else /* not MR_USE_REGIONS */
+    /* Dummy definitions */
+  #define   MR_tag_alloc_in_region(dest, tag, region, count)                \
+            MR_tag_incr_hp(dest, tag, count)
+#endif /* not MR_USE_REGIONS */
+
 /***************************************************************************/
 
 /*
@@ -313,6 +333,24 @@
 
 #endif /* MR_CONSERVATIVE_GC */
 
+#if defined(MR_USE_REGIONS)
+  #define   MR_alloc_in_region(dest, region, count)                         \
+            (                                                               \
+                (dest) = (MR_Word) MR_mkword(tag,                           \
+                            (MR_Word)                                       \
+                            ((MR_Word *) MR_region_alloc_in_region(         \
+                                         region, (count)) )),               \
+                (void) 0                                                    \
+            )
+
+#else /* not MR_USE_REGIONS */
+
+    /* Dummy definitions */
+  #define   MR_alloc_in_region(dest, region, count)                         \
+            MR_tag_offset_incr_hp(dest, 0, 0, count)
+
+#endif
+
 /***************************************************************************/
 
 /*
Index: mercury_region.c
===================================================================
RCS file: mercury_region.c
diff -N mercury_region.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ mercury_region.c	29 Jun 2007 00:44:30 -0000
@@ -0,0 +1,765 @@
+/*
+** 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_misc.h"
+
+#include "mercury_region.h"
+
+/*
+** Currently word_sizeof is used for MR_Region struct only. This is always
+** the case then it should be better to make it an (inline) function.
+*/
+#define word_sizeof(s) (sizeof(s) / sizeof(MR_Word))
+
+MR_Word     *ite_stack_min;
+MR_Word     *ite_stack_max;
+MR_Word     *ite_sp;
+
+MR_Word     *nondet_stack_min;
+MR_Word     *nondet_stack_max;
+MR_Word     *nondet_maxfr;
+
+/*---------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Supporting list management. */
+
+static void region_list_add(MR_Region *region, MR_Word *sp, int frame);
+static void region_list_remove(MR_Region *region, MR_Word *sp, int frame);
+static Snapshot* snapshot_list_add(MR_Region *region, MR_Word *sp, int frame);
+static void free_region_list(MR_Word *sp, int frame);
+static void free_snapshot_list(MR_Word *sp, int frame);
+
+/*
+** Add to the head of the list.
+*/
+static void
+region_list_add(MR_Region *region, MR_Word *sp, int frame) {
+    Region_List *element = 
+        (Region_List*) malloc(sizeof(Region_List));
+    element->region = region;
+    element->prev = NULL;
+    if (sp[frame] == NULL) { // Adding the first element.
+        element->next = NULL;
+        sp[frame] = element;
+    } else {
+        Region_List *first;
+        first = (Region_List*)sp[frame];
+        element->next = first;
+        sp[frame] = element;
+    }
+}
+
+/*
+** Remove an element.
+*/
+static void
+region_list_remove(MR_Region *region, MR_Word *sp, int frame) {
+    Region_List *element;
+    for (element = sp[frame]; element != NULL; element = element->next) {
+        if (element->region == region) {
+            if (element->prev == NULL) { // the first element
+                if (element->next == NULL) { // also the last
+                    sp[frame] = element->prev;
+                } else {
+                    sp[frame] = element->next;
+                    (element->next)->prev = NULL;
+                }
+            } else {
+                if (element->next == NULL) { // the last
+                    (element->prev)->next = NULL;
+                } else {
+                    (element->prev)->next = element->next;
+                    (element->next)->prev = element->prev;
+                }
+            }
+            free(element);
+            return;
+        }
+    }
+
+}
+
+static Snapshot *
+snapshot_list_add(MR_Region *region, MR_Word *sp, int frame) {
+    Snapshot *snapshot = 
+        (Snapshot *) malloc(sizeof(Snapshot));
+    snapshot->region = region;
+    snapshot->saved_last_page = region->last_page;
+    snapshot->saved_pointer = region->pointer;
+    snapshot->saved_removal_counter = region->removal_counter;
+    snapshot->saved_avail_space = region->avail_space;
+
+    if ((int *)sp[frame] == NULL) { // Add the first element.
+        snapshot->next = NULL;
+        snapshot->prev = NULL;
+        sp[frame] = snapshot;
+    } else {
+        Snapshot *first;
+        first = (Snapshot*)sp[frame];
+        snapshot->next = first;
+        snapshot->prev = NULL;
+        first->prev = snapshot;
+        sp[frame] = snapshot;
+    }
+    return snapshot;
+}
+
+static void
+free_region_list(MR_Word *sp, int frame) {
+    Region_List *element;
+    element = (Region_List *)sp[frame];
+    while (element != NULL) {
+        Region_List *element2 = element;
+        element = element->next;
+        free(element2);
+    }
+    sp[frame] = NULL;
+}
+
+static void
+free_snapshot_list(MR_Word *sp, int frame) {
+    Snapshot *snapshot;
+    snapshot = (Snapshot *)sp[frame];
+    while (snapshot != NULL) {
+        Snapshot *snapshot2 = snapshot;
+        snapshot = snapshot->next;
+        free(snapshot2);
+    }
+    sp[frame] = NULL;
+}
+
+/*---------------------------------------------------------------------------*/
+/* Implementation of the ite stack. */
+
+static void ite_stack_init(void);
+static void ite_stack_push(void);
+static void ite_stack_pop(void);
+static int ite_stack_is_empty(void);
+static void ite_stack_frame_delete_data(void);
+
+static void
+ite_stack_init() {
+    ite_sp = (int *)malloc(ITE_STACK_SIZE);
+    ite_stack_min = ite_sp;
+    ite_stack_max = ite_stack_min + ITE_STACK_SIZE - 1;
+}
+
+static void
+ite_stack_push() {
+    ite_sp += ITE_STACK_FRAME_SIZE;
+    if (ite_sp > ite_stack_max) {
+        MR_fatal_error("ite stack overflow");
+    }   
+    ite_sp[SNAPSHOT_LIST] = 0;
+    ite_sp[TERMINATION_LIST] = 0;
+    ite_sp[REMOVAL_LIST] = 0;
+}
+
+static void
+ite_stack_pop() {
+    if (ite_sp <= ite_stack_min) {
+        MR_fatal_error("pop while ite stack is empty");
+    } else {
+        ite_sp -= ITE_STACK_FRAME_SIZE;
+    }
+}
+
+static int
+ite_stack_is_empty() {
+    return (ite_sp == ite_stack_min);
+}
+
+/*
+** Clean up an ite frame.
+*/
+static void
+ite_stack_frame_delete_data() {
+    free_snapshot_list(ite_sp, SNAPSHOT_LIST);
+    free_region_list(ite_sp, TERMINATION_LIST);
+    free_region_list(ite_sp, REMOVAL_LIST);
+}
+
+/*---------------------------------------------------------------------------*/
+/* Implementation of the nondet stack. */
+
+static void nondet_stack_init(void);
+static void nondet_stack_push(void);
+static void nondet_stack_pop(void);
+static int nondet_stack_is_empty(void);
+static void nondet_stack_frame_delete_data(void);
+
+static void nondet_stack_init() {
+    nondet_stack_min = (int *)malloc(NONDET_STACK_SIZE);
+    nondet_stack_max = nondet_stack_min + NONDET_STACK_SIZE - 1;
+    nondet_maxfr = nondet_stack_min;
+    // a dummy nondet frame
+    nondet_stack_push();
+}
+
+static void nondet_stack_push() {
+    nondet_maxfr += NONDET_STACK_FRAME_SIZE;
+    if (nondet_maxfr > nondet_stack_max) {
+        MR_fatal_error("nondet stack overflow");
+    }
+    nondet_maxfr[TERMINATION_LIST] = 0;
+    nondet_maxfr[SNAPSHOT_LIST] = 0;
+}
+
+static void nondet_stack_pop() {
+    if (nondet_maxfr < nondet_stack_min) {
+        MR_fatal_error("pop while nondet stack is empty");
+    } else {
+        nondet_maxfr -= NONDET_STACK_FRAME_SIZE;
+    }
+}
+
+static int nondet_stack_is_empty() {
+    return (nondet_maxfr == nondet_stack_min);
+}
+
+static void nondet_stack_frame_delete_data() {
+    if (nondet_stack_is_empty()) {
+        MR_fatal_error("delete data while the nondet stack is empty");
+    }
+    free_region_list(nondet_maxfr, TERMINATION_LIST);
+    free_snapshot_list(nondet_maxfr, SNAPSHOT_LIST);
+}
+
+static int is_region_manager_initialized = 0;
+
+void MR_region_init_region_manager() {
+    if (!is_region_manager_initialized) {
+        is_region_manager_initialized = 1;
+        ite_stack_init();
+        nondet_stack_init();
+    }
+}
+
+/*---------------------------------------------------------------------------*/
+/*
+** Page operations.
+*/
+
+/*
+** Request for more pages from the operating system. 
+*/
+static MR_Page *request_pages(void);
+
+static MR_Page * 
+request_pages() {
+    MR_Page *pages;
+    pages = (MR_Page *) malloc(MR_NUM_PAGES_TO_REQUEST*sizeof(MR_Page));
+    if (!pages) {
+        MR_fatal_error(
+                "Cannot request more memory from the operating system");
+    }
+    pages[0].next_page = NULL;
+    int i;
+    for (i = 1; i < MR_NUM_PAGES_TO_REQUEST; i++) {
+        pages[i].next_page = &pages[i - 1];
+    }
+    return &(pages[MR_NUM_PAGES_TO_REQUEST - 1]);
+}
+
+/*
+** Take a page from the free page list.
+*/
+static MR_Page *get_free_page(void);
+
+static MR_Page *
+get_free_page() {
+    if (free_page_list == 0) {
+        free_page_list = request_pages();
+    }
+
+    MR_Page *page = free_page_list;
+    free_page_list = free_page_list->next_page;
+    // Disconnected the first free page from the free list.
+    page->next_page = NULL;
+    return page;
+}
+
+/*---------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/*
+** Region operations.
+*/
+
+/*
+** Create the region straight away.
+** The MR_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_Page *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->space;
+    region->pointer = (MR_Word *)(page->space + word_sizeof(MR_Region));
+    region->last_page = page;
+    region->avail_space = MR_PAGE_SPACE_SIZE - word_sizeof(MR_Region);
+    region->removal_counter = 1;
+    region->in_termination_list_of_ite_frame = NULL;
+    region->in_removal_list_of_ite_frame = NULL;
+    region->in_termination_list_of_nondet_frame = NULL;
+    region->newest_snapshot = NULL;
+    region->nondet_frame_of_newest_snapshot = NULL;
+    region->ite_frame_of_newest_snapshot = NULL;
+    return region;
+}
+
+void
+MR_region_remove_region(MR_Region *region) {
+    // Return the page list of the region to the free page list.
+    region->last_page->next_page = free_page_list;
+    free_page_list = (MR_Page *)region;
+}
+
+static void extend_region(MR_Region *);
+
+MR_Word *
+MR_region_alloc_in_region(MR_Region *region, unsigned int words) {
+    if (region->avail_space < words) {
+       extend_region(region);
+    }
+    MR_Word *allocated_cell = region->pointer;
+    // Allocate in the increasing direction of address.
+    region->pointer += words;
+    region->avail_space -= words;
+    return allocated_cell;
+}
+
+static void
+extend_region(MR_Region *region) {
+    MR_Page *page = get_free_page();
+    region->last_page->next_page = page;
+    region->last_page = page;
+    region->pointer = (MR_Word *)page->space;
+    region->avail_space = MR_PAGE_SPACE_SIZE;
+}
+
+/*---------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------*/
+
+/*
+** Backtrack supporting region operations.
+*/
+
+static void restore_region(Snapshot *);
+static void shrink_region(MR_Region *);
+
+/* Create a region and prepare undo information if necessary. */
+MR_Region *
+MR_region_backtrack_support_create_region() {
+    MR_Region *region;
+    region = MR_region_create_region();
+    // Prepare undo information because of nondet code.
+    if (!nondet_stack_is_empty()) { 
+        region_list_add(region, nondet_maxfr, TERMINATION_LIST);
+        region->in_termination_list_of_nondet_frame = nondet_maxfr;
+    } else ;    
+    
+    // ... because of if-then-else.
+    if (!ite_stack_is_empty()) {
+        region_list_add(region, ite_sp, TERMINATION_LIST);
+        region->in_termination_list_of_ite_frame = ite_sp;
+    } else ;
+    
+    return region;
+}
+
+/* Remove a region but we may need to:
+** - postpone or ignore the removal,
+** - record related undo information.
+*/
+void
+MR_region_backtrack_support_remove_region(MR_Region *region) {
+    if (!nondet_stack_is_empty()) {
+        if (region->in_termination_list_of_nondet_frame == nondet_maxfr) { 
+            if (!ite_stack_is_empty()) { 
+                if (region->in_termination_list_of_ite_frame == ite_sp) {
+                    region_list_remove(region, ite_sp, TERMINATION_LIST);
+                    region_list_remove(region, nondet_maxfr, TERMINATION_LIST);
+                    if (region->removal_counter > 1) {
+                        region->removal_counter -= 1;
+                    } else {
+                        MR_region_remove_region(region);
+                    }
+                } else {
+                    region->in_removal_list_of_ite_frame == ite_sp;
+                    region_list_add(region, ite_sp, REMOVAL_LIST);
+                }
+            } else {
+                if (region->removal_counter > 1) {
+                    region->removal_counter -= 1;
+                } else {
+                    region_list_remove(region, nondet_maxfr, TERMINATION_LIST);
+                    MR_region_remove_region(region);
+                }
+            }
+        } else { // Not in the maxfr's termination list.
+            if (!ite_stack_is_empty()) {
+                if (region->in_termination_list_of_ite_frame == ite_sp) {
+                    shrink_region(region);
+                } else {
+                    region->in_removal_list_of_ite_frame = ite_sp;
+                    region_list_add(region, ite_sp, REMOVAL_LIST);
+                }
+            } else {
+                shrink_region(region);
+            }
+        }
+    } // End of nondet stack NOT empty.
+    else { // No choice point exists.
+        if (!ite_stack_is_empty()) { // in the condition of some ite
+            if (region->in_termination_list_of_ite_frame == ite_sp) {
+                MR_region_remove_region(region);
+                region_list_remove(region, ite_sp, TERMINATION_LIST);
+            } else {
+                region->in_removal_list_of_ite_frame == ite_sp;
+                region_list_add(region, ite_sp, REMOVAL_LIST);
+            }
+        } else { // Not in the condition of any ite, so remove it.
+            MR_region_remove_region(region);
+        }
+    }
+}
+
+/* 1. The first allocation into a region needs to be recorded.
+** 2. Only record first allocation into a region NOT in Termination List of
+** maxfr and ite_sp.
+*/
+MR_Word *
+MR_region_backtrack_support_region_alloc(MR_Region *region,
+        unsigned int words) {
+    if (!nondet_stack_is_empty()) {
+        if ((region->nondet_frame_of_newest_snapshot != nondet_maxfr) &&
+            (region->in_termination_list_of_nondet_frame != nondet_maxfr)) { 
+            /* This is the first allocation into the region since the
+            ** topmost choice point is created and the region is created
+            ** before the choice point, so prepare undoing.
+            ** The newest snapshot is stored to ease shrinking the region.
+            */
+            region->nondet_frame_of_newest_snapshot = nondet_maxfr;
+            region->newest_snapshot =
+                snapshot_list_add(region, nondet_maxfr, SNAPSHOT_LIST);
+        }
+    }
+    
+    if (!ite_stack_is_empty()) {
+        if ((region->ite_frame_of_newest_snapshot != ite_sp) &&
+            (region->in_termination_list_of_ite_frame != ite_sp)) {
+            /* This is the first allocation into the region since the
+            ** topmost ite frame is created and the region is created
+            ** before the frame, so prepare undoing.
+            */
+            region->ite_frame_of_newest_snapshot = ite_sp;
+            snapshot_list_add(region, ite_sp, SNAPSHOT_LIST);
+        }
+    }
+    
+    return MR_region_alloc_in_region(region, words);
+}
+
+/*
+** 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) {
+        Snapshot *snapshot = (Snapshot *)region->newest_snapshot;
+        restore_region(snapshot);
+    }
+}
+
+/* Restore a region to a state saved in the snapshot.
+** When collecting statistics:
+** - the total memory use is not reset,
+** - current memory use need be reset,
+** - max memory use is not reset because the saved size is <= the current size.
+*/
+static void
+restore_region(Snapshot *snapshot) {
+    MR_Region *region = snapshot->region;
+    // Return the list of pages added since the save to the global free
+    // page list.
+    region->last_page->next_page = free_page_list;
+    free_page_list = snapshot->saved_last_page->next_page; 
+
+    // Disconnect the saved last page (i.e., the last page of the restored
+    // region) from the free list.
+    snapshot->saved_last_page->next_page = NULL;
+
+    // Restore the saved region.
+    region->last_page = snapshot->saved_last_page;
+    region->pointer = snapshot->saved_pointer;
+    region->avail_space = snapshot->saved_avail_space;
+    region->removal_counter = snapshot->saved_removal_counter;
+}
+
+
+/*---------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------*/
+/* Operations for managing the ite stack. */
+static void discard_ite_frame(void);
+
+/*
+** Create an ite frame when entering the condition of an if-then-else.
+*/
+void
+MR_region_create_ite_frame() {
+    ite_stack_push();
+}
+
+/*
+** When the control reaches the then branch of an if-then-else, we commit
+** the removals of regions which were removed (but delayed) during the 
+** execution of the condition. This "undo" information is in removal list at
+** the top ite frame. 
+** XXX Currently this method discards the top ite frame after undoing.
+** This is not correct when the condition is a nondet goal.
+** What to do seems to have something to do with the process of cc_multi.
+**
+** Note: need to take care the case when committing removals while there 
+** are other ite frames. That is we also need to remove regions from
+** termination lists if they are in any. 
+*/
+void
+MR_region_ite_then_do_removal() {
+    Region_List *removal;
+    for (
+        removal = (Region_List *)ite_sp[REMOVAL_LIST];
+        removal != NULL; 
+        removal = removal->next
+    ) {
+        // If a region is in termination list of another ite frame,
+        // remove it from there also, so that it will not be removed
+        // twice.
+        // Note that the region can never be in the termination list of
+        // this same frame therefore if in_termination_list_of_ite_frame != 0
+        // it points to another ite frame.
+        MR_Region *region = removal->region;
+        MR_Word *ite_frame = region->in_termination_list_of_ite_frame;
+        if (ite_frame != NULL) {
+            region_list_remove(region, ite_frame, TERMINATION_LIST);
+            region->in_termination_list_of_ite_frame = NULL;
+        }
+
+        if (!nondet_stack_is_empty()) {
+            if (region->in_termination_list_of_nondet_frame == nondet_maxfr) {
+                region_list_remove(region, nondet_maxfr, TERMINATION_LIST);
+                MR_region_remove_region(region);
+            } else {
+                shrink_region(region);
+                // The region still "exists" so we set this field to NULL
+                // for consistency.
+                region->in_removal_list_of_ite_frame = NULL;
+            }
+        } else { // Nondet stack is empty.
+            MR_region_remove_region(region);
+        }
+    }
+    discard_ite_frame();
+}
+
+/*
+** When the control reaches the else branch of an if-then-else (i.e.,
+** the condition failed), we undo allocations (instant reclaming) and
+** creations of regions which occured during the trial of the condition.
+** The "undo" information is in the top ite frame and after the undo we
+** can discard that top frame.
+*/
+void
+MR_region_ite_else_undo_changes() {
+    // Remove regions which are in ite_sp's Termination List.
+    // We will also need to exclude them from termination list of 
+    // the top nondet frame if they happen to be there.
+    Region_List *termination;
+    for (
+            termination = (Region_List *)ite_sp[TERMINATION_LIST];
+            termination != NULL;
+            termination = termination->next
+    ) {
+        MR_Region *region;
+        region = termination->region;
+        MR_region_remove_region(region);
+
+        if (region->in_termination_list_of_nondet_frame == nondet_maxfr) {
+            region_list_remove(region, nondet_maxfr, TERMINATION_LIST);
+            region->in_termination_list_of_nondet_frame = NULL;
+        }
+    }
+    
+    // Reset size of regions that are in ite_sp's Snapshot list.
+    Snapshot *snapshot;
+    for (
+            snapshot = (Snapshot *)ite_sp[SNAPSHOT_LIST];
+            snapshot != NULL;
+            snapshot = snapshot->next
+    ) {
+        restore_region(snapshot);
+    }
+    
+    // Destroy this frame.
+    discard_ite_frame();
+}
+
+/*
+** Pop the topmost ite frame.
+** When popping we need to release the memory of the termination list,
+** snapshot list, and removal list at the frame.
+*/
+static void
+discard_ite_frame() {
+    ite_stack_frame_delete_data();
+    ite_stack_pop();
+}
+
+/*---------------------------------------------------------------------------*/
+/*---------------------------------------------------------------------------*/
+
+/*
+** Operations for managing the nondet stack.
+*/
+
+static void undo_nondet_creations(void);
+static void undo_nondet_allocations(void);
+
+/*
+** When we enter a nondeterministic context, a nondet frame is created.
+*/
+void
+MR_region_create_nondet_frame() {
+    if (is_region_manager_initialized) {
+        nondet_stack_push();
+    }
+}
+
+/*
+** When there is no more alternative for a nondet goal, the nondet frame 
+** corresponding to the goal is removed.
+*/
+void
+MR_region_discard_nondet_frame() {
+    if (is_region_manager_initialized) {
+        MR_region_undo_creations_and_allocations();
+        nondet_stack_pop();
+
+        /*
+        ** XXX  After the top frame has been popped, we need to undo any
+        ** changes from the current (just-become) top frame to
+        ** the just-popped frame, i.e., we restore memory to the state
+        ** right before the current top frame is created.
+        ** The reason for this is because, in the last alternative of the 
+        ** top frame, the redoip of the current nondet frame is reset to 
+        ** do_fail. This do_fail macro executes the fail macro, which
+        ** removes the topmost nondet frame, sets the curfr to the newly 
+        ** exposed frame, and branches to "the label" whose address is in 
+        ** the redoip of that frame (paper:Mercury 1996). This implies 
+        ** that the redo marco has not been called to execute "the label",
+        ** which is the next alternative of the newly exposed frame.
+        ** So this call below "simulates" the effect as if redo is called.
+        */
+        MR_region_undo_creations_and_allocations();
+    }
+}
+
+/*
+** When the program backtracks to a choice point of a nondet goal and
+** there still are alternatives for the nondet goal, we just use the undo
+** data at the nondet frame corresponding to the goal to restore memory
+** state before starting an alternative. Then we delete the data but
+** not the frame.
+*/
+void
+MR_region_undo_creations_and_allocations() {
+    if (is_region_manager_initialized) {
+        undo_nondet_creations();
+        undo_nondet_allocations();
+
+        // We only delete the current data at this frame. The frame itself
+        // will be discarded only when 'fail' happens.
+        nondet_stack_frame_delete_data();
+    }   
+}
+
+/*
+** Remove regions in nondet stack's Termination List.
+** Algorithm:
+** (1) If a region in this TL is also in TL of an ite frame 
+** (i.e. if ... nondet ..., create R ... then ... else ...) it is also removed
+** from the ite frame's TL.
+** (2) If a region in this TL is also in RL of an ite frame 
+** (i.e. ...nondet ... create R ... if ... remove R ... then ... else ...) 
+** it is also removed from the ite frame's TL.
+*/
+
+static void
+undo_nondet_creations() {
+    Region_List *termination;
+    for (
+            termination = (Region_List *)nondet_maxfr[TERMINATION_LIST];
+            termination != NULL;
+            termination = termination->next
+    ) {
+        // (1)
+        MR_Region *region; 
+        region = termination->region;
+        MR_Word *ite_frame = region->in_termination_list_of_ite_frame;
+        if (ite_frame != 0) {
+            region_list_remove(region, ite_frame, TERMINATION_LIST);
+            region->in_termination_list_of_ite_frame = NULL;
+        }
+        
+        // (2): It seems that this never happens because the control should
+        // reach "then" or "else" before it may fail. If it reaches "then" 
+        // the removal of R is committed and R will also be removed from
+        // this termination list, i.e., when this method is called, if a
+        // region is in this termination list, it cannot be in the removal
+        // list of some ite frame.
+        int *ite_frame_2 = region->in_removal_list_of_ite_frame;
+        if (ite_frame_2 != NULL) {
+            region_list_remove(region, ite_frame_2, REMOVAL_LIST);
+            region->in_removal_list_of_ite_frame = NULL;
+        }
+        
+        MR_region_remove_region(region);
+    }
+}
+
+/*
+** Reset size of regions which are in snapshot list of the maxfr. 
+*/
+static void
+undo_nondet_allocations() {
+    Snapshot *snapshot;
+    for (
+            snapshot = (Snapshot *)nondet_maxfr[SNAPSHOT_LIST];
+            snapshot != NULL;
+            snapshot = snapshot->next
+    ) {
+        restore_region(snapshot);
+    }
+}
+
+/*---------------------------------------------------------------------------*/
Index: mercury_region.h
===================================================================
RCS file: mercury_region.h
diff -N mercury_region.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ mercury_region.h	20 Jun 2007 06:29:58 -0000
@@ -0,0 +1,128 @@
+/* 
+** 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)
+
+/* Put dummy defn for MR_Region */
+
+typedef int MR_Region;
+
+#else /* defined(MR_USE_REGIONS) */
+
+/*
+** XXX This should be made configurable when compiling a program.
+*/
+#define MR_NUM_PAGES_TO_REQUEST 100
+#define MR_PAGE_SPACE_SIZE 30
+
+#define ITE_STACK_SIZE 1024	/* 4KB, each slot is 4 bytes*/
+#define ITE_STACK_FRAME_SIZE 3
+#define NONDET_STACK_SIZE 1024	/* 4KB, each slot is 4 bytes*/
+#define NONDET_STACK_FRAME_SIZE 2
+#define SNAPSHOT_LIST -1
+#define TERMINATION_LIST -2
+#define REMOVAL_LIST -3
+
+typedef struct MR_Page_Struct {
+    MR_Word                     space[MR_PAGE_SPACE_SIZE];
+    struct MR_Page_Struct       *next_page;
+} MR_Page;
+
+typedef struct MR_Region_Struct {
+    struct MR_Page_Struct       *last_page;
+    MR_Word                     *pointer;
+    MR_Word                     avail_space;
+    unsigned int                removal_counter;
+
+    /*
+    ** The fields below are redundant information, which is used to 
+    ** facilitate the check if a region is in one of the list or not.
+    ** We will have to pay the price of keeping the redundancy 
+    ** consistent.
+    */
+    /* A region can only be in the below lists of one frame. */
+    MR_Word                     *in_termination_list_of_ite_frame;
+    MR_Word                     *in_removal_list_of_ite_frame;
+    MR_Word                     *in_termination_list_of_nondet_frame;
+
+    /* A region can have several snapshots snapshot-lists of several
+    ** nondet/ite frames.
+    **
+    ** We store the newest_snapshot (in a nondet frame) here to faciliate
+    ** shrinking the region. When shrinking we always shrink the region to
+    ** the size in the snapshot of the topmost nondet frame.
+    ** 
+    ** The newest frames containing a snapshot is used to check whether a 
+    ** snapshot needs to be stored for an allocation or not.
+    */
+    struct Snapshot_Struct      *newest_snapshot; 
+    MR_Word                     *nondet_frame_of_newest_snapshot;
+    MR_Word                     *ite_frame_of_newest_snapshot; 
+} MR_Region;
+
+/* Region is used to represent termination list and removal list. */
+typedef struct Region_List_Struct {
+	struct Region_List_Struct   *next;
+	struct Region_List_Struct   *prev;
+	struct MR_Region_Struct     *region;
+} Region_List;
+
+/* This is to represent snapshot list. */
+typedef struct Snapshot_Struct {
+	struct Snapshot_Struct      *next;
+	struct Snapshot_Struct      *prev;
+	struct MR_Region_Struct     *region;
+    struct MR_Page_Struct       *saved_last_page;
+	MR_Word                     *saved_pointer;
+	MR_Word                     saved_removal_counter;
+	MR_Word                     saved_avail_space;
+} Snapshot;
+
+/*---------------------------------------------------------------------------*/
+/*
+** A region is implemented as a single-linked list of pages. A page contains
+** a pointer to the next to form a single-linked-list and an array
+** (of MR_Word) to store program data.
+** The region allocator maintains a list of free pages, when we need a page 
+** for a region it is taken from the list.
+** The information of the region itself (pointer to next available cell, 
+** removal counter, some other operational data) is stored in its first page.
+*/
+
+MR_Page     *free_page_list;
+
+MR_Region   *MR_region_create_region(void);
+void        MR_region_remove_region(MR_Region *);
+MR_Word     *MR_region_alloc_in_region(MR_Region *, unsigned int);
+
+MR_Region   *MR_region_backtrack_support_create_region(void);
+void        MR_region_backtrack_support_remove_region(MR_Region *);
+MR_Word     *MR_region_backtrack_support_region_alloc(MR_Region *,
+                unsigned int);
+
+void MR_region_create_ite_frame(void);
+void MR_region_ite_then_do_removal(void);
+void MR_region_ite_else_undo_changes(void);
+
+void MR_region_create_nondet_frame(void);
+void MR_region_discard_nondet_frame(void);
+void MR_region_undo_creations_and_allocations(void);
+
+void MR_region_init_region_manager(void);
+
+#endif /* defined(MR_USE_REGIONS) */
+#endif /* MERCURY_REGION_H */
Index: region_builtin.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/region_builtin.m,v
retrieving revision 1.1
diff -u -u -r1.1 region_builtin.m
--- region_builtin.m	12 Jun 2007 03:22:25 -0000	1.1
+++ region_builtin.m	29 Jun 2007 04:36:09 -0000
@@ -43,17 +43,17 @@
 
 :- 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",
@@ -61,7 +61,7 @@
     [will_not_call_mercury],
 "
     /* Region */
-    MR_fatal_error(\"region_builtin.remove_region/1 NYI.\");
+    MR_region_remove_region(Region);
 ").
 
 %-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the reviews mailing list