diff options
author | blazy <blazy@fca1b0fc-160b-0410-b1d3-a4f43f01ea2e> | 2006-10-20 12:37:13 +0000 |
---|---|---|
committer | blazy <blazy@fca1b0fc-160b-0410-b1d3-a4f43f01ea2e> | 2006-10-20 12:37:13 +0000 |
commit | ca0c62265eb8cdd5fb0d8a8b34ee77baf3de987e (patch) | |
tree | 50a139db8e2ac51c6ff41f3790ff72aa417ed3be /test/ccured_olden/mst | |
parent | 43668d9109b1f36329646fd07324d435be6f0050 (diff) | |
download | compcert-kvx-ca0c62265eb8cdd5fb0d8a8b34ee77baf3de987e.tar.gz compcert-kvx-ca0c62265eb8cdd5fb0d8a8b34ee77baf3de987e.zip |
Ajout du banc de tests de CCured (Olden benchmark suite, cf.
CCured: type-safe retrofitting of legacy code, G.Necula et al.)
rapportCompcert_all.txt liste les erreurs produites par ccomp.
git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@121 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e
Diffstat (limited to 'test/ccured_olden/mst')
-rw-r--r-- | test/ccured_olden/mst/.cvsignore | 26 | ||||
-rw-r--r-- | test/ccured_olden/mst/CVS/Entries | 16 | ||||
-rw-r--r-- | test/ccured_olden/mst/CVS/Repository | 1 | ||||
-rw-r--r-- | test/ccured_olden/mst/CVS/Root | 1 | ||||
-rw-r--r-- | test/ccured_olden/mst/HOWTO | 1 | ||||
-rw-r--r-- | test/ccured_olden/mst/Makefile | 62 | ||||
-rw-r--r-- | test/ccured_olden/mst/Makefile.plain | 7 | ||||
-rw-r--r-- | test/ccured_olden/mst/Makefile.ss | 7 | ||||
-rw-r--r-- | test/ccured_olden/mst/args.c | 20 | ||||
-rw-r--r-- | test/ccured_olden/mst/args.s | 37 | ||||
-rw-r--r-- | test/ccured_olden/mst/hash.c | 105 | ||||
-rw-r--r-- | test/ccured_olden/mst/hash.h | 23 | ||||
-rw-r--r-- | test/ccured_olden/mst/hash.s | 354 | ||||
-rw-r--r-- | test/ccured_olden/mst/main.c | 142 | ||||
-rw-r--r-- | test/ccured_olden/mst/makegraph.c | 93 | ||||
-rw-r--r-- | test/ccured_olden/mst/mst.h | 33 | ||||
-rw-r--r-- | test/ccured_olden/mst/out.orig | 13 | ||||
-rw-r--r-- | test/ccured_olden/mst/output | 13 | ||||
-rw-r--r-- | test/ccured_olden/mst/ssplain.c | 38 | ||||
-rw-r--r-- | test/ccured_olden/mst/ssplain.h | 128 | ||||
-rwxr-xr-x | test/ccured_olden/mst/testit | 25 |
21 files changed, 1145 insertions, 0 deletions
diff --git a/test/ccured_olden/mst/.cvsignore b/test/ccured_olden/mst/.cvsignore new file mode 100644 index 00000000..0b0377b1 --- /dev/null +++ b/test/ccured_olden/mst/.cvsignore @@ -0,0 +1,26 @@ +*.o +*.obj +*.exe +*.pdb +*.ilk +*.cpp +*.i +*.s +*.asm +*cil.c +*.rtl +*box.c +*infer.c +*_ppp.c +*.origi +*.stackdump +*_all.c +allcfiles +ope.m +*cured.c +*.optim.c +*_comb.c +*.exe_comb.browser +changes +output +out.diff diff --git a/test/ccured_olden/mst/CVS/Entries b/test/ccured_olden/mst/CVS/Entries new file mode 100644 index 00000000..862ae447 --- /dev/null +++ b/test/ccured_olden/mst/CVS/Entries @@ -0,0 +1,16 @@ +/HOWTO/1.1/Fri Jun 29 11:07:28 2001// +/Makefile/1.6/Fri Oct 12 01:25:10 2001// +/Makefile.plain/1.1/Fri Jun 29 11:07:28 2001// +/Makefile.ss/1.1/Fri Jun 29 11:07:28 2001// +/args.c/1.1/Fri Jun 29 11:07:28 2001// +/hash.h/1.1/Fri Jun 29 11:07:28 2001// +/main.c/1.1/Fri Jun 29 11:07:28 2001// +/makegraph.c/1.1/Fri Jun 29 11:07:28 2001// +/mst.h/1.1/Fri Jun 29 11:07:28 2001// +/ssplain.c/1.6/Wed Oct 31 04:00:37 2001// +/out.orig/1.1/Mon Nov 12 08:08:28 2001// +/testit/1.2/Tue Dec 4 05:07:50 2001// +/.cvsignore/1.8/Fri Oct 4 16:28:44 2002// +/hash.c/1.8/Tue Jan 7 00:17:16 2003// +/ssplain.h/1.6/Mon Jan 6 23:29:27 2003// +D diff --git a/test/ccured_olden/mst/CVS/Repository b/test/ccured_olden/mst/CVS/Repository new file mode 100644 index 00000000..8ebc6045 --- /dev/null +++ b/test/ccured_olden/mst/CVS/Repository @@ -0,0 +1 @@ +cil/test/olden/mst diff --git a/test/ccured_olden/mst/CVS/Root b/test/ccured_olden/mst/CVS/Root new file mode 100644 index 00000000..35f411e9 --- /dev/null +++ b/test/ccured_olden/mst/CVS/Root @@ -0,0 +1 @@ +/home/cvs-repository diff --git a/test/ccured_olden/mst/HOWTO b/test/ccured_olden/mst/HOWTO new file mode 100644 index 00000000..1058d0f1 --- /dev/null +++ b/test/ccured_olden/mst/HOWTO @@ -0,0 +1 @@ +1024 1 diff --git a/test/ccured_olden/mst/Makefile b/test/ccured_olden/mst/Makefile new file mode 100644 index 00000000..d3f950b6 --- /dev/null +++ b/test/ccured_olden/mst/Makefile @@ -0,0 +1,62 @@ +# /* For copyright information, see olden_v1.0/COPYRIGHT */ + +BINARY = mst.exe +PROGS = main makegraph hash args ssplain + +OLDENHOME = /tmp/olden + +ifdef _MSVC +CC = cl +DEF = /D +CONLY = /c +OBJOUT = /Fo +EXEOUT = /Fe +OBJ = .obj + +OPTFLAGS = /Ox +LIBS = + +else + +CC = gcc -arch ppc +CCOMP=../../../../ccomp +CCOMPFLAGS=-dump-c +DEF = -D +CONLY = -c +OBJOUT= -o +EXEOUT= -o + +OBJ = .o + +OPTFLAGS = -g -Wall -O3 + +LIBS = +LIBPATH = +endif + +SRC = .c +ASM = .s +EXTRA_CDEFS = $(DEF)I_TIME $(DEF)I_SYS_TIME $(DEF)ULTRIX +CDEFS = $(DEF)PLAIN $(DEF)SS_PLAIN +SRCS = $(addsuffix $(SRC),$(PROGS)) +OBJS = $(addsuffix $(OBJ),$(PROGS)) +ASMS = $(addsuffix $(ASM),$(PROGS)) + +all_s: $(PROGS:%=%.s) + +all: $(PROGS:%=%.compcert) + +all_gcc: $(PROGS:%=%.gcc) + +%.compcert: %.s + $(CC) $(CFLAGS) $(LDFALGS) $(OPTFLAGS) -o $*.compcert $*.s $(LIBS) + +%.s: %.c ../../../../ccomp + $(CCOMP) $(CCOMPFLAGS) $*.c + +%.gcc: %.c + $(CC) $(CFLAGS) $(LDFALGS) $(OPTFLAGS) -o $*.gcc $*.c $(LIBS) + +clean: + rm -f $(BINARY) $(OBJS) $(OBJS) *~ *infer.c *cured.c *cil.c *_comb.c *.i *.light.c + diff --git a/test/ccured_olden/mst/Makefile.plain b/test/ccured_olden/mst/Makefile.plain new file mode 100644 index 00000000..7e4450ac --- /dev/null +++ b/test/ccured_olden/mst/Makefile.plain @@ -0,0 +1,7 @@ +# /* For copyright information, see olden_v1.0/COPYRIGHT */ + +BINARY = mst +FILES = main makegraph hash args ssplain + +include ../Makefile.plain + diff --git a/test/ccured_olden/mst/Makefile.ss b/test/ccured_olden/mst/Makefile.ss new file mode 100644 index 00000000..92ac11a1 --- /dev/null +++ b/test/ccured_olden/mst/Makefile.ss @@ -0,0 +1,7 @@ +# /* For copyright information, see olden_v1.0/COPYRIGHT */ + +BINARY = mst +FILES = main makegraph hash args ssplain + +include ../Makefile.ss + diff --git a/test/ccured_olden/mst/args.c b/test/ccured_olden/mst/args.c new file mode 100644 index 00000000..169d87ab --- /dev/null +++ b/test/ccured_olden/mst/args.c @@ -0,0 +1,20 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#ifdef SS_PLAIN +#include "ssplain.h" +#include "mst.h" +#endif SS_PLAIN + + +int dealwithargs(int argc, char *argv[]) +{ + int level; + + if (argc > 1) + level = atoi(argv[1]); + else + level = 1024; + + return level; +} + diff --git a/test/ccured_olden/mst/args.s b/test/ccured_olden/mst/args.s new file mode 100644 index 00000000..a397dc72 --- /dev/null +++ b/test/ccured_olden/mst/args.s @@ -0,0 +1,37 @@ + .text + .align 2 +Latoi$i$stub: + mflr r0 + stwu r1, -56(r1) + stw r0, 60(r1) + addis r11, 0, ha16(Latoi$i$ptr) + lwz r11, lo16(Latoi$i$ptr)(r11) + mtctr r11 + bctrl + lwz r0, 60(r1) + mtlr r0 + addi r1, r1, 56 + blr + .non_lazy_symbol_pointer +Latoi$i$ptr: + .indirect_symbol _atoi + .long 0 + .text + .align 2 + .globl _dealwithargs +_dealwithargs: + stwu r1, -32(r1) + mflr r2 + stw r2, 12(r1) + cmpwi cr0, r3, 1 + bt 1, L100 + addi r3, 0, 1024 + b L101 +L100: + lwz r3, 4(r4) + bl Latoi$i$stub +L101: + lwz r2, 12(r1) + mtlr r2 + lwz r1, 0(r1) + blr diff --git a/test/ccured_olden/mst/hash.c b/test/ccured_olden/mst/hash.c new file mode 100644 index 00000000..67e460dd --- /dev/null +++ b/test/ccured_olden/mst/hash.c @@ -0,0 +1,105 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#include "ssplain.h" +#ifdef SS_PLAIN +#include "mst.h" +#else SS_PLAIN +#include "hash.h" +#endif SS_PLAIN +#include <string.h> + +#define assert(num,a) if (!(a)) {chatting("Assertion failure:%d in hash\n",num); exit(-1);} +#undef assert +#define assert(num,a) + +#ifndef CCURED + #define __NOCUREBLOCK +#endif + +#ifdef CCURED + #pragma ccuredalloc("localmalloc", nozero, sizein(1)) +#endif +static char *localmalloc(int size); + +static int remaining = 0; +static char *temp; +static char *localmalloc(int size) { + char *blah; + + if (size>remaining) + { + temp = (char *) malloc(32768); + if (!temp) chatting("Error! malloc returns null\n"); + remaining = 32768; + } + blah = temp; + temp += size; + remaining -= size; + return blah; +} + +#define localfree(sz) + +Hash MakeHash(int size, int (*map)(unsigned int)) +{ + Hash retval; + + retval = (Hash) localmalloc(sizeof(*retval)); + retval->array = (HashEntry *) localmalloc(size*sizeof(retval->array[0])); + { __NOCUREBLOCK + memset((char*)retval->array, 0, size * sizeof(retval->array[0])); + } + retval->mapfunc = map; + retval->size = size; + retval->padding = 0; + return retval; +} + +void *HashLookup(unsigned int key, Hash hash) +{ + int j; + HashEntry ent; + + j = (hash->mapfunc)(key); + assert(1,j>=0); + assert(2,j<hash->size); + + for (ent = hash->array[j]; ent && ent->key!=key; ent=ent->next) ; + + if (ent) return ent->entry; + return NULL; +} + +void HashInsert(void *entry,unsigned int key,Hash hash) +{ + HashEntry ent; + int j; + + assert(3,!HashLookup(key,hash)); + + j = (hash->mapfunc)(key); + + ent = (HashEntry) localmalloc(sizeof(*ent)); + ent->next = hash->array[j]; + hash->array[j]=ent; + ent->key = key; + ent->entry = entry; +} + +void HashDelete(unsigned int key,Hash hash) +{ + HashEntry *ent; + HashEntry tmp; + int j; + + j = (hash->mapfunc)(key); + for (ent=&(hash->array[j]); (*ent) && (*ent)->key!=key; ent=&((*ent)->next)); + assert(4,*ent); + tmp = *ent; + *ent = (*ent)->next; + localfree(tmp); +} + + + + diff --git a/test/ccured_olden/mst/hash.h b/test/ccured_olden/mst/hash.h new file mode 100644 index 00000000..99475263 --- /dev/null +++ b/test/ccured_olden/mst/hash.h @@ -0,0 +1,23 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#include "stdio.h" + +typedef struct hash_entry { + unsigned int key; + void *entry; + struct hash_entry *next; + unsigned int padding; +} *HashEntry; + +typedef struct hash { + HashEntry *array; + int (*mapfunc)(unsigned int); + int size; + unsigned int padding; +} *Hash; + +Hash MakeHash(int size, int map(unsigned int)); +void *HashLookup(unsigned int key, Hash hash); +void HashInsert(void *entry,unsigned int key, Hash hash); +void HashDelete(unsigned int key, Hash hash); + diff --git a/test/ccured_olden/mst/hash.s b/test/ccured_olden/mst/hash.s new file mode 100644 index 00000000..f418b39d --- /dev/null +++ b/test/ccured_olden/mst/hash.s @@ -0,0 +1,354 @@ + .data + .globl __hash__stringlit_1 +__hash__stringlit_1: + .byte 69 + .byte 114 + .byte 114 + .byte 111 + .byte 114 + .byte 33 + .byte 32 + .byte 109 + .byte 97 + .byte 108 + .byte 108 + .byte 111 + .byte 99 + .byte 32 + .byte 114 + .byte 101 + .byte 116 + .byte 117 + .byte 114 + .byte 110 + .byte 115 + .byte 32 + .byte 110 + .byte 117 + .byte 108 + .byte 108 + .byte 10 + .byte 0 + .data + .globl _remaining +_remaining: + .long 0 + .data + .globl _temp +_temp: + .space 4 + .text + .align 2 +Lchatting$i$stub: + mflr r0 + stwu r1, -56(r1) + stw r0, 60(r1) + addis r11, 0, ha16(Lchatting$i$ptr) + lwz r11, lo16(Lchatting$i$ptr)(r11) + mtctr r11 + bctrl + lwz r0, 60(r1) + mtlr r0 + addi r1, r1, 56 + blr + .non_lazy_symbol_pointer +Lchatting$i$ptr: + .indirect_symbol _chatting + .long 0 + .text + .align 2 +Lmalloc$stub: + addis r11, 0, ha16(Lmalloc$ptr) + lwz r11, lo16(Lmalloc$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +Lmalloc$ptr: + .indirect_symbol _malloc + .long 0 + .text + .align 2 +LMakeHash$stub: + addis r11, 0, ha16(LMakeHash$ptr) + lwz r11, lo16(LMakeHash$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +LMakeHash$ptr: + .indirect_symbol _MakeHash + .long 0 + .text + .align 2 +LHashLookup$stub: + addis r11, 0, ha16(LHashLookup$ptr) + lwz r11, lo16(LHashLookup$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +LHashLookup$ptr: + .indirect_symbol _HashLookup + .long 0 + .text + .align 2 +LHashInsert$stub: + addis r11, 0, ha16(LHashInsert$ptr) + lwz r11, lo16(LHashInsert$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +LHashInsert$ptr: + .indirect_symbol _HashInsert + .long 0 + .text + .align 2 +LHashDelete$stub: + addis r11, 0, ha16(LHashDelete$ptr) + lwz r11, lo16(LHashDelete$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +LHashDelete$ptr: + .indirect_symbol _HashDelete + .long 0 + .text + .align 2 +Lmemset$stub: + addis r11, 0, ha16(Lmemset$ptr) + lwz r11, lo16(Lmemset$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +Lmemset$ptr: + .indirect_symbol _memset + .long 0 + .text + .align 2 +Llocalmalloc$stub: + addis r11, 0, ha16(Llocalmalloc$ptr) + lwz r11, lo16(Llocalmalloc$ptr)(r11) + mtctr r11 + bctr + .non_lazy_symbol_pointer +Llocalmalloc$ptr: + .indirect_symbol _localmalloc + .long 0 + .text + .align 2 + .globl Llocalmalloc$stub +Llocalmalloc$stub: + stwu r1, -32(r1) + mflr r2 + stw r2, 12(r1) + stw r13, 28(r1) + mr r13, r3 + addis r2, 0, ha16(_remaining) + lwz r6, lo16(_remaining)(r2) + cmpw cr0, r13, r6 + bf 1, L100 + addis r3, 0, 0 + ori r3, r3, 32768 + bl Lmalloc$stub + addis r2, 0, ha16(_temp) + stw r3, lo16(_temp)(r2) + addis r2, 0, ha16(_temp) + lwz r3, lo16(_temp)(r2) + cmplwi cr0, r3, 0 + bf 2, L101 + addis r3, 0, hi16(__hash__stringlit_1) + ori r3, r3, lo16(__hash__stringlit_1) + bl Lchatting$i$stub +L101: + addis r8, 0, 0 + ori r8, r8, 32768 + addis r2, 0, ha16(_remaining) + stw r8, lo16(_remaining)(r2) +L100: + addis r2, 0, ha16(_temp) + lwz r3, lo16(_temp)(r2) + add r4, r3, r13 + addis r2, 0, ha16(_temp) + stw r4, lo16(_temp)(r2) + addis r2, 0, ha16(_remaining) + lwz r5, lo16(_remaining)(r2) + subfc r7, r13, r5 + addis r2, 0, ha16(_remaining) + stw r7, lo16(_remaining)(r2) + lwz r13, 28(r1) + lwz r2, 12(r1) + mtlr r2 + lwz r1, 0(r1) + blr + .text + .align 2 + .globl LMakeHash$stub +LMakeHash$stub: + stwu r1, -48(r1) + mflr r2 + stw r2, 12(r1) + stw r13, 36(r1) + stw r14, 40(r1) + stw r15, 44(r1) + mr r14, r3 + mr r13, r4 + addi r3, 0, 16 + bl Llocalmalloc$stub + mr r15, r3 + rlwinm r3, r14, 2, 0xfffffffc + bl Llocalmalloc$stub + stw r3, 0(r15) + lwz r3, 0(r15) + addi r4, 0, 0 + rlwinm r5, r14, 2, 0xfffffffc + bl Lmemset$stub + stw r13, 4(r15) + stw r14, 8(r15) + addi r3, 0, 0 + stw r3, 12(r15) + mr r3, r15 + lwz r13, 36(r1) + lwz r14, 40(r1) + lwz r15, 44(r1) + lwz r2, 12(r1) + mtlr r2 + lwz r1, 0(r1) + blr + .text + .align 2 + .globl LHashLookup$stub +LHashLookup$stub: + stwu r1, -48(r1) + mflr r2 + stw r2, 12(r1) + stw r13, 28(r1) + stw r14, 32(r1) + mr r14, r3 + mr r13, r4 + lwz r8, 4(r13) + mr r0, r8 + mr r3, r14 + mtctr r0 + bctrl + lwz r4, 0(r13) + rlwinm r5, r3, 2, 0xfffffffc + lwzx r3, r4, r5 +L102: + cmplwi cr0, r3, 0 + bt 2, L103 + lwz r7, 0(r3) + cmplw cr0, r7, r14 + bt 2, L104 + addi r6, 0, 1 + b L105 +L104: + addi r6, 0, 0 + b L105 +L103: + addi r6, 0, 0 +L105: + cmpwi cr0, r6, 0 + bt 2, L106 + lwz r3, 8(r3) + b L102 +L106: + cmplwi cr0, r3, 0 + bt 2, L107 + lwz r3, 4(r3) + b L108 +L107: + addi r3, 0, 0 +L108: + lwz r13, 28(r1) + lwz r14, 32(r1) + lwz r2, 12(r1) + mtlr r2 + lwz r1, 0(r1) + blr + .text + .align 2 + .globl LHashInsert$stub +LHashInsert$stub: + stwu r1, -48(r1) + mflr r2 + stw r2, 12(r1) + stw r13, 28(r1) + stw r14, 32(r1) + stw r15, 36(r1) + stw r16, 40(r1) + mr r14, r3 + mr r13, r4 + mr r16, r5 + lwz r6, 4(r16) + mr r0, r6 + mr r3, r13 + mtctr r0 + bctrl + mr r15, r3 + addi r3, 0, 16 + bl Llocalmalloc$stub + lwz r7, 0(r16) + rlwinm r4, r15, 2, 0xfffffffc + lwzx r5, r7, r4 + stw r5, 8(r3) + lwz r5, 0(r16) + stwx r3, r5, r4 + stw r13, 0(r3) + stw r14, 4(r3) + # undef r3 + lwz r13, 28(r1) + lwz r14, 32(r1) + lwz r15, 36(r1) + lwz r16, 40(r1) + lwz r2, 12(r1) + mtlr r2 + lwz r1, 0(r1) + blr + .text + .align 2 + .globl LHashDelete$stub +LHashDelete$stub: + stwu r1, -48(r1) + mflr r2 + stw r2, 12(r1) + stw r13, 28(r1) + stw r14, 32(r1) + mr r14, r3 + mr r13, r4 + lwz r9, 4(r13) + mr r0, r9 + mr r3, r14 + mtctr r0 + bctrl + lwz r4, 0(r13) + rlwinm r8, r3, 2, 0xfffffffc + add r3, r4, r8 +L109: + lwz r5, 0(r3) + cmplwi cr0, r5, 0 + bt 2, L110 + lwz r4, 0(r5) + cmplw cr0, r4, r14 + bt 2, L111 + addi r7, 0, 1 + b L112 +L111: + addi r7, 0, 0 + b L112 +L110: + addi r7, 0, 0 +L112: + cmpwi cr0, r7, 0 + bt 2, L113 + lwz r10, 0(r3) + addi r3, r10, 8 + b L109 +L113: + lwz r4, 0(r3) + lwz r6, 8(r4) + stw r6, 0(r3) + # undef r3 + lwz r13, 28(r1) + lwz r14, 32(r1) + lwz r2, 12(r1) + mtlr r2 + lwz r1, 0(r1) + blr diff --git a/test/ccured_olden/mst/main.c b/test/ccured_olden/mst/main.c new file mode 100644 index 00000000..0e464d7c --- /dev/null +++ b/test/ccured_olden/mst/main.c @@ -0,0 +1,142 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#include <string.h> +#include "mst.h" +#include "ssplain.h" + +typedef struct blue_return { + Vertex vert; + int dist; +} BlueReturn; + +static BlueReturn BlueRule(Vertex inserted, Vertex vlist) +{ + BlueReturn retval; + Vertex tmp,prev; + Hash hash; + int dist,dist2; + int count; + + if (!vlist) { + retval.dist = 999999; + return retval; + } + prev = vlist; + retval.vert = vlist; + retval.dist = vlist->mindist; + hash = vlist->edgehash; + dist = (int) HashLookup((unsigned int) inserted, hash); + /*chatting("Found %d at 0x%x for 0x%x\n",dist,inserted,vlist);*/ + if (dist) + { + if (dist<retval.dist) + { + vlist->mindist = dist; + retval.dist = dist; + } + } + else chatting("Not found\n"); + + count = 0; + + /* We are guaranteed that inserted is not first in list */ + for (tmp=vlist->next; tmp; prev=tmp,tmp=tmp->next) + { + count++; + + /* Splice chosen vertex out of the list */ + if (tmp==inserted) + { + Vertex next; + next = tmp->next; + prev->next = next; + } + /* Find the shortest distance to any other vertex not in the list */ + else + { + hash = tmp->edgehash; + dist2 = tmp->mindist; + dist = (int) HashLookup((unsigned int) inserted, hash); + /*chatting("Found %d at 0x%x for 0x%x\n",dist,inserted,tmp);*/ + if (dist) + { + if (dist<dist2) + { + tmp->mindist = dist; + dist2 = dist; + } + } + else chatting("Not found\n"); + if (dist2<retval.dist) + { + retval.vert = tmp; + retval.dist = dist2; + } + } /* else */ + + } /* for */ + /*chatting("Count was %d\n",count);*/ + return retval; +} + + + +static Vertex MyVertexList = NULL; + +static int ComputeMst(Graph graph,int numvert) +{ + Vertex inserted,tmp; + int cost=0,dist; + + /* make copy of graph */ + chatting("Compute phase 1\n"); + + /* Insert first node */ + inserted = graph->vlist; + tmp = inserted->next; + graph->vlist = tmp; + MyVertexList = tmp; + numvert--; + + /* Announce insertion and find next one */ + chatting("Compute phase 2\n"); + while (numvert) + { + BlueReturn br; + + if (inserted == MyVertexList) + MyVertexList = MyVertexList->next; + br = BlueRule(inserted, MyVertexList); + inserted = br.vert; + dist = br.dist; + numvert--; + cost = cost+dist; + } + return cost; +} + +extern int dealwithargs(int argc, char *argv[]); + +int main(int argc, char *argv[]) +{ + Graph graph; + int dist; + int size; + + chatting("Hash entry size = %d\n", sizeof(struct hash_entry)); + chatting("Hash size = %d\n", sizeof(struct hash)); + chatting("Vertex size = %d\n", sizeof(struct vert_st)); + + size = dealwithargs(argc,argv); + + chatting("Making graph of size %d\n",size); + graph = MakeGraph(size); + chatting("Graph completed\n"); + + chatting("About to compute mst \n"); + dist = ComputeMst(graph,size); + + chatting("MST has cost %d\n",dist); + exit(0); +} + diff --git a/test/ccured_olden/mst/makegraph.c b/test/ccured_olden/mst/makegraph.c new file mode 100644 index 00000000..c99fad96 --- /dev/null +++ b/test/ccured_olden/mst/makegraph.c @@ -0,0 +1,93 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#include "mst.h" +#include "ssplain.h" + +#define CONST_m1 10000 +#define CONST_b 31415821 +#define RANGE 2048 +static int HashRange; + +static int mult(int p, int q) +{ + int p1, p0, q1, q0; + + p1=p/CONST_m1; p0=p%CONST_m1; + q1=q/CONST_m1; q0=q%CONST_m1; + return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0); +} + +static int mst_random(int seed) +{ + int tmp; + tmp = (mult(seed,CONST_b)+1); + return tmp; +} + +static int compute_dist(int i,int j, int numvert) +{ + int less, gt; + if (i<j) {less = i; gt = j;} else {less = j; gt = i;} + return (mst_random(less*numvert+gt) % RANGE)+1; +} + +static int hashfunc(unsigned int key) +{ + return ((key>>4) % HashRange); +} + +static void AddEdges(Graph retval, int numvert) +{ + Vertex src, dest; + Hash hash; + int i, j, dist, num_inserted = 0; + + for (j = 0; j < numvert; j++) + { + src = &(retval->vlist[j]); + hash = src->edgehash; + + for (i=0; i<numvert; i++) + { + if (i!=j) + { + dist = compute_dist(i,j,numvert); + dest = &(retval->vlist[i]); + HashInsert((void *) dist,(unsigned int) dest,hash); + num_inserted++; + } + } /* for i */ + } /* for j */ + + chatting("%d edges inserted\n", num_inserted); +} + +Graph MakeGraph(int numvert) +{ + int i; + Vertex vf, vt; + Graph retval; + + retval = (Graph) malloc (sizeof(*retval)); + + chatting("Make phase 1: Creating hash tables\n"); + retval->vlist = (Vertex) malloc (numvert*(sizeof(*vf))); + vt = NULL; + + for (i = numvert - 1; i >= 0; i--) + { + vf = &(retval->vlist[i]); + HashRange = numvert/4; + vf->mindist = 9999999; + vf->edgehash = MakeHash(HashRange,hashfunc); + vf->next = vt; + vt=vf; + } + + chatting("Make phase 3: Creating graph\n"); + AddEdges(retval, numvert); + chatting("Make returning\n"); + return retval; +} + + diff --git a/test/ccured_olden/mst/mst.h b/test/ccured_olden/mst/mst.h new file mode 100644 index 00000000..4af1e346 --- /dev/null +++ b/test/ccured_olden/mst/mst.h @@ -0,0 +1,33 @@ +/* For copyright information, see olden_v1.0/COPYRIGHT */ + +#ifdef SS_PLAIN +#include <stdlib.h> +#endif SS_PLAIN + +#include "hash.h" +#define MAXPROC 1 + +#ifndef SS_PLAIN +/* Amir: Get these out of here for SS, piggyback on the PLAIN definition */ +#include "mem-ref.h" +#define NULL 0 +#endif SS_PLAIN + +typedef struct vert_st { + int mindist; + struct vert_st *next; + Hash edgehash; + unsigned int padding; +} *Vertex; + +typedef struct graph_st { + Vertex vlist; +} *Graph; + +Graph MakeGraph(int numvert); + +#ifdef SS_PLAIN +#include <stdarg.h> +void chatting(char *s, ...); +#endif SS_PLAIN + diff --git a/test/ccured_olden/mst/out.orig b/test/ccured_olden/mst/out.orig new file mode 100644 index 00000000..a50096d7 --- /dev/null +++ b/test/ccured_olden/mst/out.orig @@ -0,0 +1,13 @@ +Hash entry size = xx +Hash size = xx +Vertex size = xx +Making graph of size 2048 +Make phase 1: Creating hash tables +Make phase 3: Creating graph +4192256 edges inserted +Make returning +Graph completed +About to compute mst +Compute phase 1 +Compute phase 2 +MST has cost 13615 diff --git a/test/ccured_olden/mst/output b/test/ccured_olden/mst/output new file mode 100644 index 00000000..d2677157 --- /dev/null +++ b/test/ccured_olden/mst/output @@ -0,0 +1,13 @@ +Hash entry size = 16 +Hash size = 20 +Vertex size = 20 +Making graph of size 2048 +Make phase 1: Creating hash tables +Make phase 3: Creating graph +4192256 edges inserted +Make returning +Graph completed +About to compute mst +Compute phase 1 +Compute phase 2 +MST has cost 13615 diff --git a/test/ccured_olden/mst/ssplain.c b/test/ccured_olden/mst/ssplain.c new file mode 100644 index 00000000..645d3a1e --- /dev/null +++ b/test/ccured_olden/mst/ssplain.c @@ -0,0 +1,38 @@ +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdarg.h> +#include <limits.h> +#include <stddef.h> +#include "ssplain.h" + +void chatting(char *s, ...) +{ + va_list ap; + va_start(ap,s); + vfprintf(stderr, s, ap); + va_end(ap); +} + + +#ifdef SS_RAND +double drand48() +{ + double d; + d = (double) random() / LONG_MAX; + return d; +} + + +long lrand48() +{ + long l = random(); + return l; +} + +void srand48(long seed) +{ + srand(seed); +} +#endif SS_RAND + diff --git a/test/ccured_olden/mst/ssplain.h b/test/ccured_olden/mst/ssplain.h new file mode 100644 index 00000000..865fbf47 --- /dev/null +++ b/test/ccured_olden/mst/ssplain.h @@ -0,0 +1,128 @@ +#ifndef SS_PLAIN_H +#define SS_PLAIN_H + +void * ssplain_malloc(int size); +void * ssplain_calloc(int nelems, int size); +void ssplain_alloc_stats(); + +/* Convert MP shutdown to exit */ +#define __ShutDown(ID) { ssplain_alloc_stats(); exit(ID); } + +/* All these CM-5 things are nops */ +#define CMMD_node_timer_clear(ID) +#define CMMD_node_timer_start(ID) +#define CMMD_node_timer_stop(ID) +#define CMMD_node_timer_elapsed(ID) ((double)0) + +#define CMMD_self_address() 0 + +#define ClearAllStats() + +/* define away the CM-5 allocator */ +#include <stdlib.h> + +#ifndef ALLOC +#define ALLOC(NUM,ESIZE) ssplain_calloc (NUM+1,ESIZE) +#endif ALLOC + +#ifndef mymalloc +#define mymalloc malloc +#endif mymalloc + +/* Get all of these multiprocessing things out of here. */ +/* My id will stay that way */ +#define IDMASK 0xffffffff + +/* Nothing is getting tested */ +#ifndef RETEST +#define RETEST() +#endif RETEST + +#ifndef NOTEST +#define NOTEST() +#endif NOTEST + +/* Everything is local */ +#ifndef local +#define local +#endif local + +#ifndef LOCAL +#define LOCAL(VAL) (VAL) +#endif LOCAL + +#ifndef ISLOCPTR +#define ISLOCPTR(VAL) (1) +#endif ISLOCPTR + +#ifndef MLOCAL +#define MLOCAL(VAL) +#endif MLOCAL + +/* An atomic increment is a normal increment */ +#ifndef ATOMICINC +#define ATOMICINC(PVAL) (*(PVAL) = *(PVAL) + 1) +#endif ATOMICINC + +/* Nothing is migrating anywhere */ +#ifndef MIGRATE +#define MIGRATE(ID) +#endif MIGRATE + +#ifndef MIGRPH +#define MIGRPH() +#endif MIGRPH + +#ifndef UNPHASE +#define UNPHASE() +#endif UNPHASE + +#ifndef PID +#define PID(VAL) (0) +#endif PID + +/* All these functions */ +#pragma ccuredvararg("chatting", printf(1)) +void chatting(char *s, ...); + +/* just define these guys, they are not going to change */ +#define __NumNodes 1 +#define __MyNodeId 0 +#define __NDim 0 + +typedef struct ss_future_cell_int { + int value; +} future_cell_int; + +/* Where are these things for real? */ +#ifdef SS_RAND +long lrand48(); +double drand48(); +void srand48(long seed); +#endif SS_RAND + +#define MOD(V,M) ((V) & ((M) - 1)) +#define INC_MOD(V,M) (V) = MOD((V) + 1, (M)) + +/* Prefetch instructions */ + +/* Use these for 1 lookahead prefetching */ + +#ifdef OVERHEAD_ONLY +#define ASSEMBLE_PREFETCH(ARG) +#define ASSEMBLE_PREFETCH_HEAD(ARG) +#else !OVERHEAD_ONLY + +#define ASSEMBLE_PREFETCH(ARG) \ + asm ("lw $0, %0" : /* no outputs */ : "g" (ARG)) + +/* Use these for infinite lookahead prefetching */ +#define ASSEMBLE_PREFETCH_HEAD(ARG) \ + asm ("lh $0, %0" : /* no outputs */ : "g" (ARG)) + +#endif OVERHEAD_ONLY + +#endif SS_PLAIN_H + + + diff --git a/test/ccured_olden/mst/testit b/test/ccured_olden/mst/testit new file mode 100755 index 00000000..2ef87d18 --- /dev/null +++ b/test/ccured_olden/mst/testit @@ -0,0 +1,25 @@ +#!/bin/sh +# test an mst binary + +if [ "$1" = "" ]; then + echo "usage: $0 ./mst.exe" + exit +fi + +# all of mst's output is to stderr +echo "running: $1 2048 1 2>output" +if ! $1 2048 1 2>output; then + echo "$1 failed directly" + exit 2 +fi + +# mst prints sizes of its structures, which increase after boxing +if ! sed 's/size = [0-9][0-9]/size = xx/' <output | diff out.orig - >out.diff; then + if test -s out.diff; then + echo "$1 got the wrong answer. See out.diff" + exit 4 + fi +fi +echo "$1 seems to work" +rm -f out.diff +
\ No newline at end of file |