From ca285074159abb65a815db5c08284becaa297df0 Mon Sep 17 00:00:00 2001 From: xleroy Date: Thu, 26 Oct 2006 10:03:35 +0000 Subject: Ajout test stop© GC git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@133 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e --- test/cminor/Makefile | 7 +- test/cminor/stopcopy.cmp | 185 ++++++++++++++++++++++++++++++++++++++++ test/harness/maingc.c | 213 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 404 insertions(+), 1 deletion(-) create mode 100644 test/cminor/stopcopy.cmp create mode 100644 test/harness/maingc.c diff --git a/test/cminor/Makefile b/test/cminor/Makefile index f9b863ea..e4988416 100644 --- a/test/cminor/Makefile +++ b/test/cminor/Makefile @@ -5,7 +5,7 @@ CFLAGS=-arch ppc -g ASFLAGS=-arch ppc VPATH=../harness ../lib -PROGS=fib integr qsort fft sha1 aes almabench manyargs lists +PROGS=fib integr qsort fft sha1 aes almabench manyargs lists stopcopy all_s: $(PROGS:%=%.s) @@ -58,6 +58,11 @@ lists: lists.o mainlists.o clean:: rm -f lists +stopcopy: stopcopy.o maingc.o + $(CC) $(CFLAGS) -o stopcopy stopcopy.o maingc.o +clean:: + rm -f stopcopy + .SUFFIXES: .SUFFIXES: .cmp .cm .s .o .c .S diff --git a/test/cminor/stopcopy.cmp b/test/cminor/stopcopy.cmp new file mode 100644 index 00000000..366620d6 --- /dev/null +++ b/test/cminor/stopcopy.cmp @@ -0,0 +1,185 @@ +/* A simple stop-and-copy garbage collector */ + +var "alloc_ptr"[4] +var "fromspace_start_ptr"[4] +var "fromspace_end_ptr"[4] +var "tospace_start_ptr"[4] +var "tospace_end_ptr"[4] + +/* Format of blocks: + - header word: 30 bits size + 2 bits kind + kind = 0 block contains raw data (no pointers) + kind = 1 block contains pointer data + kind = 2 block is closure (all pointers except first word) + kind = 3 block was forwarded + - [size] words of data + + Blocks are stored in one big global array and addressed by pointers + within this block. The pointer goes to the first word of data. +*/ + +#define KIND_RAWDATA 0 +#define KIND_PTRDATA 1 +#define KIND_CLOSURE 2 +#define KIND_FORWARDED 3 +#define Kind_header(h) ((h) & 3) +#define Size_header(h) ((h) & 0xFFFFFFFC) + +/* Copy one block. The reference to that block is passed by reference + at address [location], and will be updated. */ + +"copy_block"(copy_ptr, location): int -> int -> int +{ + var optr, header, kind, size, src, dst; + + optr = int32[location]; + if (optr == 0) return copy_ptr; + header = int32[optr - 4]; + kind = Kind_header(header); + if (kind == KIND_FORWARDED) { + /* Already copied. Reference of copy is stored in the + first field of original. */ + int32[location] = int32[optr]; + } else { + /* Copy contents of original block (including header) */ + size = Size_header(header) + 4; + src = optr - 4; + dst = copy_ptr; + {{ loop { + int32[dst] = int32[src]; + src = src + 4; + dst = dst + 4; + size = size - 4; + if (size == 0) exit; + } }} + copy_ptr = copy_ptr + 4; + /* Mark original as forwarded */ + int32[optr - 4] = header | KIND_FORWARDED; + int32[optr] = copy_ptr; + /* Update location to point to copy */ + int32[location] = copy_ptr; + /* Finish allocating space for copy */ + copy_ptr = copy_ptr + Size_header(header); + } + return copy_ptr; +} + +/* Finish the copying */ + +"copy_all"(scan_ptr, copy_ptr): int -> int -> int +{ + var header, kind, size; + + {{ loop { + if (scan_ptr >= copy_ptr) exit; + header = int32[scan_ptr]; + scan_ptr = scan_ptr + 4; + kind = Kind_header(header); + size = Size_header(header); + if (kind == KIND_RAWDATA) { + /* Nothing to do for a RAWDATA block */ + scan_ptr = scan_ptr + size; + } else { + /* Apply [copy_block] to all fields if PTRDATA, all fields except + first if CLOSURE. */ + if (kind == KIND_CLOSURE) { scan_ptr = scan_ptr + 4; size = size - 4; } + {{ loop { + if (size == 0) exit; + copy_ptr = "copy_block"(copy_ptr, scan_ptr) : int -> int -> int; + scan_ptr = scan_ptr + 4; + size = size - 4; + } }} + } + } }} + return copy_ptr; +} + +/* Copy the roots. The roots are given as a linked list of blocks: + offset 0: pointer to next root block (or NULL) + offset 4: number of roots N + offset 8 and following words: the roots +*/ + +"copy_roots"(copy_ptr, root): int -> int -> int +{ + var n, p; + + {{ loop { + if (root == 0) exit; + n = int32[root + 4]; + p = root + 8; + {{ loop { + if (n == 0) exit; + copy_ptr = "copy_block"(copy_ptr, p) : int -> int -> int; + p = p + 4; + n = n - 1; + } }} + root = int32[root]; + } }} + return copy_ptr; +} + +/* Garbage collection */ + +extern "gc_alarm" : int -> void + +"garbage_collection"(root): int -> void +{ + var heap_base, copy_ptr, tmp; + + copy_ptr = int32["tospace_start_ptr"]; + copy_ptr = "copy_roots"(copy_ptr, root) : int -> int -> int; + copy_ptr = "copy_all"(int32["tospace_start_ptr"], copy_ptr) : int -> int -> int; + /* Swap fromspace and tospace */ + tmp = int32["tospace_start_ptr"]; + int32["tospace_start_ptr"] = int32["fromspace_start_ptr"]; + int32["fromspace_start_ptr"] = tmp; + tmp = int32["tospace_end_ptr"]; + int32["tospace_end_ptr"] = int32["fromspace_end_ptr"]; + int32["fromspace_end_ptr"] = tmp; + /* Reinitialise allocation pointer */ + int32["alloc_ptr"] = copy_ptr; + "gc_alarm"(copy_ptr - int32["fromspace_start_ptr"]) : int -> void; +} + +/* Allocation */ + +extern "abort" : void + +"alloc_block"(root, kind, size): int -> int -> int -> int +{ + var p, np; + + loop { + p = int32["alloc_ptr"]; + np = p + size + 4; + if (np <= int32["fromspace_end_ptr"]) { + int32["alloc_ptr"] = np; + int32[p] = size | kind; + return p + 4; + } + "garbage_collection"(root) : int -> void; + if (int32["alloc_ptr"] + size + 4 > int32["fromspace_end_ptr"]) { + "abort"() : void; + } + } +} + +/* Initialize a heap of size [hsize] bytes */ + +extern "malloc" : int -> int + +"init_heap"(hsize) : int -> int +{ + var hbase; + + hbase = "malloc"(hsize * 2) : int -> int; + if (hbase == 0) return -1; + int32["fromspace_start_ptr"] = hbase; + int32["fromspace_end_ptr"] = hbase + hsize; + int32["tospace_start_ptr"] = hbase + hsize; + int32["tospace_end_ptr"] = hbase + hsize * 2; + int32["alloc_ptr"] = hbase; + return 0; +} + diff --git a/test/harness/maingc.c b/test/harness/maingc.c new file mode 100644 index 00000000..4d5942f6 --- /dev/null +++ b/test/harness/maingc.c @@ -0,0 +1,213 @@ +/* Test harness for the simple garbage collectors */ + +#include +#include +#include +#include + +extern int init_heap(int hsize); + +enum block_kind { RAWDATA = 0, PTRDATA = 1, CLOSURE = 2 }; + +struct rootblock { + struct rootblock * next; + int numroots; + void * root[8]; +}; + +extern void * alloc_block(struct rootblock * roots, + enum block_kind kind, + int size); + +void gc_alarm(int live) +{ + printf("\n", live); +} + +/* Test with binary trees */ + +typedef struct { + long i; +} boxedInt; + +boxedInt * BoxInt(struct rootblock * r, long n) +{ + boxedInt * new = (boxedInt *) alloc_block(r, RAWDATA, sizeof(long)); + new->i = n; + return new; +} + +typedef struct tn { + struct tn* left; + struct tn* right; + boxedInt * item; +} treeNode; + +treeNode* NewTreeNode(struct rootblock * r, + treeNode* left, treeNode* right, long item) +{ + struct rootblock nr; + treeNode* new; + boxedInt* bitem; + + nr.next = r; nr.numroots = 2; nr.root[0] = left; nr.root[1] = right; + + bitem = BoxInt(&nr, item); + + nr.numroots = 3; nr.root[2] = bitem; + + new = (treeNode*) alloc_block(&nr, PTRDATA, sizeof(treeNode)); + + new->left = (treeNode *) nr.root[0]; + new->right = (treeNode *) nr.root[1]; + new->item = (boxedInt *) nr.root[2]; + + return new; +} + + +long ItemCheck(treeNode* tree) +{ + if (tree->left == NULL) + return tree->item->i; + else + return tree->item->i + ItemCheck(tree->left) - ItemCheck(tree->right); +} + + +treeNode* BottomUpTree(struct rootblock * r, long item, unsigned depth) +{ + struct rootblock nr; + + if (depth > 0) { + nr.next = r; nr.numroots = 0; + nr.root[0] = BottomUpTree(&nr, 2 * item - 1, depth - 1); + nr.numroots = 1; + nr.root[1] = BottomUpTree(&nr, 2 * item, depth - 1); + nr.numroots = 2; + return NewTreeNode(&nr, + (treeNode *) nr.root[0], + (treeNode *) nr.root[1], + item); + } else { + return NewTreeNode(r, NULL, NULL, item); + } +} + +treeNode* SkinnyTree(struct rootblock * r, unsigned depth) +{ + struct rootblock nr; + + if (depth > 0) { + nr.next = r; nr.numroots = 0; + nr.root[0] = SkinnyTree(&nr, depth - 1); + nr.numroots = 1; + return NewTreeNode(&nr, + (treeNode *) nr.root[0], + (treeNode *) nr.root[0], + depth); + } else { + return NULL; + } +} + +void test(unsigned N) +{ + unsigned depth, minDepth, maxDepth, stretchDepth; + struct rootblock r; + + minDepth = 4; + + if ((minDepth + 2) > N) + maxDepth = minDepth + 2; + else + maxDepth = N; + + stretchDepth = maxDepth + 1; + + r.next = NULL; r.numroots = 0; + + r.root[0] = BottomUpTree(&r, 0, stretchDepth); + printf + ( + "stretch tree of depth %u\t check: %li\n", + stretchDepth, + ItemCheck(r.root[0]) + ); + + r.root[0] = SkinnyTree(&r, stretchDepth); + + r.root[0] = BottomUpTree(&r, 0, maxDepth); + r.numroots = 1; + + r.root[1] = SkinnyTree(&r, stretchDepth); + r.numroots = 2; + + for (depth = minDepth; depth <= maxDepth; depth += 2) { + long i, iterations, check; + + iterations = pow(2, maxDepth - depth + minDepth); + + check = 0; + + for (i = 1; i <= iterations; i++) { + r.root[2] = BottomUpTree(&r, i, depth); + check += ItemCheck(r.root[2]); + r.root[2] = BottomUpTree(&r, -i, depth); + check += ItemCheck(r.root[2]); + } + + printf + ( + "%li\t trees of depth %u\t check: %li\n", + iterations * 2, + depth, + check + ); + } + + printf + ( + "long lived tree of depth %u\t check: %li\n", + maxDepth, + ItemCheck(r.root[0]) + ); + + printf + ( + "skinny tree of depth %u\t\t check: %li\n", + stretchDepth, + ItemCheck(r.root[1]) + ); +} + +int main(int argc, char ** argv) +{ + int N, heapsize; + + N = argc > 1 ? atoi(argv[1]) : 16; + heapsize = argc > 2 ? atoi(argv[2]) : 8 * 1024 * 1024; + + if (init_heap(heapsize) == -1) { + fprintf(stderr, "Failed to allocate heap.\n"); + return 2; + } + test(N); +} + +/********************************* + +PROGRAM OUTPUT +============== +stretch tree of depth 17 check: -1 +131072 trees of depth 4 check: -131072 +32768 trees of depth 6 check: -32768 +8192 trees of depth 8 check: -8192 +2048 trees of depth 10 check: -2048 +512 trees of depth 12 check: -512 +128 trees of depth 14 check: -128 +32 trees of depth 16 check: -32 +long lived tree of depth 16 check: -1 + +***********************************/ + -- cgit