[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