From 5ced6d6aef1fcefbabcc070269fa8ba607138043 Mon Sep 17 00:00:00 2001 From: ceriel Date: Mon, 24 Nov 1986 20:58:35 +0000 Subject: [PATCH] Initial revision --- mach/arm/top/Makefile | 41 +++ mach/m68020/top/Makefile | 41 +++ mach/m68k2/top/Makefile | 41 +++ mach/pdp/top/Makefile | 41 +++ mach/proto/top/Makefile | 41 +++ mach/proto/top/queue.c | 72 +++++ mach/proto/top/queue.h | 12 + mach/proto/top/top.c | 651 +++++++++++++++++++++++++++++++++++++++ mach/proto/top/top.h | 88 ++++++ mach/vax4/top/Makefile | 41 +++ mach/vax4/top/table | 287 +++++++++++++++++ 11 files changed, 1356 insertions(+) create mode 100644 mach/arm/top/Makefile create mode 100644 mach/m68020/top/Makefile create mode 100644 mach/m68k2/top/Makefile create mode 100644 mach/pdp/top/Makefile create mode 100644 mach/proto/top/Makefile create mode 100644 mach/proto/top/queue.c create mode 100644 mach/proto/top/queue.h create mode 100644 mach/proto/top/top.c create mode 100644 mach/proto/top/top.h create mode 100644 mach/vax4/top/Makefile create mode 100644 mach/vax4/top/table diff --git a/mach/arm/top/Makefile b/mach/arm/top/Makefile new file mode 100644 index 000000000..37628d51b --- /dev/null +++ b/mach/arm/top/Makefile @@ -0,0 +1,41 @@ +EM=../../.. +PREFLAGS=-I. +PFLAGS= +CFLAGS=$(PREFLAGS) $(PFLAGS) -O +LDFLAGS=-i $(PFLAGS) +LINTOPTS=-hbxac +CDIR=$(EM)/mach/proto/top +CFILES=$(CDIR)/top.c $(CDIR)/queue.c gen.c +OFILES=top.o queue.o gen.o + +all: gen.c + make top + +top: $(OFILES) + $(CC) $(LDFLAGS) $(OFILES) $(LIBS) -o top + +top.o: $(CDIR)/top.c + $(CC) -c $(CFLAGS) $(CDIR)/top.c + +queue.o: $(CDIR)/queue.c + $(CC) -c $(CFLAGS) $(CDIR)/queue.c + +install: all + $(EM)/mach/install top + +cmp: all + -$(EM)/mach/compare top + +gen.c: table + $(EM)/lib/topgen table + +lint: $(CFILES) + lint $(LINTOPTS) $(PREFLAGS) $(CFILES) + +clean: + rm -f *.o gen.c gen.h top + +top.o: gen.h +top.o: $(CDIR)/top.h +top.o: $(CDIR)/queue.h +queue.o: $(CDIR)/queue.h diff --git a/mach/m68020/top/Makefile b/mach/m68020/top/Makefile new file mode 100644 index 000000000..37628d51b --- /dev/null +++ b/mach/m68020/top/Makefile @@ -0,0 +1,41 @@ +EM=../../.. +PREFLAGS=-I. +PFLAGS= +CFLAGS=$(PREFLAGS) $(PFLAGS) -O +LDFLAGS=-i $(PFLAGS) +LINTOPTS=-hbxac +CDIR=$(EM)/mach/proto/top +CFILES=$(CDIR)/top.c $(CDIR)/queue.c gen.c +OFILES=top.o queue.o gen.o + +all: gen.c + make top + +top: $(OFILES) + $(CC) $(LDFLAGS) $(OFILES) $(LIBS) -o top + +top.o: $(CDIR)/top.c + $(CC) -c $(CFLAGS) $(CDIR)/top.c + +queue.o: $(CDIR)/queue.c + $(CC) -c $(CFLAGS) $(CDIR)/queue.c + +install: all + $(EM)/mach/install top + +cmp: all + -$(EM)/mach/compare top + +gen.c: table + $(EM)/lib/topgen table + +lint: $(CFILES) + lint $(LINTOPTS) $(PREFLAGS) $(CFILES) + +clean: + rm -f *.o gen.c gen.h top + +top.o: gen.h +top.o: $(CDIR)/top.h +top.o: $(CDIR)/queue.h +queue.o: $(CDIR)/queue.h diff --git a/mach/m68k2/top/Makefile b/mach/m68k2/top/Makefile new file mode 100644 index 000000000..37628d51b --- /dev/null +++ b/mach/m68k2/top/Makefile @@ -0,0 +1,41 @@ +EM=../../.. +PREFLAGS=-I. +PFLAGS= +CFLAGS=$(PREFLAGS) $(PFLAGS) -O +LDFLAGS=-i $(PFLAGS) +LINTOPTS=-hbxac +CDIR=$(EM)/mach/proto/top +CFILES=$(CDIR)/top.c $(CDIR)/queue.c gen.c +OFILES=top.o queue.o gen.o + +all: gen.c + make top + +top: $(OFILES) + $(CC) $(LDFLAGS) $(OFILES) $(LIBS) -o top + +top.o: $(CDIR)/top.c + $(CC) -c $(CFLAGS) $(CDIR)/top.c + +queue.o: $(CDIR)/queue.c + $(CC) -c $(CFLAGS) $(CDIR)/queue.c + +install: all + $(EM)/mach/install top + +cmp: all + -$(EM)/mach/compare top + +gen.c: table + $(EM)/lib/topgen table + +lint: $(CFILES) + lint $(LINTOPTS) $(PREFLAGS) $(CFILES) + +clean: + rm -f *.o gen.c gen.h top + +top.o: gen.h +top.o: $(CDIR)/top.h +top.o: $(CDIR)/queue.h +queue.o: $(CDIR)/queue.h diff --git a/mach/pdp/top/Makefile b/mach/pdp/top/Makefile new file mode 100644 index 000000000..37628d51b --- /dev/null +++ b/mach/pdp/top/Makefile @@ -0,0 +1,41 @@ +EM=../../.. +PREFLAGS=-I. +PFLAGS= +CFLAGS=$(PREFLAGS) $(PFLAGS) -O +LDFLAGS=-i $(PFLAGS) +LINTOPTS=-hbxac +CDIR=$(EM)/mach/proto/top +CFILES=$(CDIR)/top.c $(CDIR)/queue.c gen.c +OFILES=top.o queue.o gen.o + +all: gen.c + make top + +top: $(OFILES) + $(CC) $(LDFLAGS) $(OFILES) $(LIBS) -o top + +top.o: $(CDIR)/top.c + $(CC) -c $(CFLAGS) $(CDIR)/top.c + +queue.o: $(CDIR)/queue.c + $(CC) -c $(CFLAGS) $(CDIR)/queue.c + +install: all + $(EM)/mach/install top + +cmp: all + -$(EM)/mach/compare top + +gen.c: table + $(EM)/lib/topgen table + +lint: $(CFILES) + lint $(LINTOPTS) $(PREFLAGS) $(CFILES) + +clean: + rm -f *.o gen.c gen.h top + +top.o: gen.h +top.o: $(CDIR)/top.h +top.o: $(CDIR)/queue.h +queue.o: $(CDIR)/queue.h diff --git a/mach/proto/top/Makefile b/mach/proto/top/Makefile new file mode 100644 index 000000000..37628d51b --- /dev/null +++ b/mach/proto/top/Makefile @@ -0,0 +1,41 @@ +EM=../../.. +PREFLAGS=-I. +PFLAGS= +CFLAGS=$(PREFLAGS) $(PFLAGS) -O +LDFLAGS=-i $(PFLAGS) +LINTOPTS=-hbxac +CDIR=$(EM)/mach/proto/top +CFILES=$(CDIR)/top.c $(CDIR)/queue.c gen.c +OFILES=top.o queue.o gen.o + +all: gen.c + make top + +top: $(OFILES) + $(CC) $(LDFLAGS) $(OFILES) $(LIBS) -o top + +top.o: $(CDIR)/top.c + $(CC) -c $(CFLAGS) $(CDIR)/top.c + +queue.o: $(CDIR)/queue.c + $(CC) -c $(CFLAGS) $(CDIR)/queue.c + +install: all + $(EM)/mach/install top + +cmp: all + -$(EM)/mach/compare top + +gen.c: table + $(EM)/lib/topgen table + +lint: $(CFILES) + lint $(LINTOPTS) $(PREFLAGS) $(CFILES) + +clean: + rm -f *.o gen.c gen.h top + +top.o: gen.h +top.o: $(CDIR)/top.h +top.o: $(CDIR)/queue.h +queue.o: $(CDIR)/queue.h diff --git a/mach/proto/top/queue.c b/mach/proto/top/queue.c new file mode 100644 index 000000000..3cf1e59c9 --- /dev/null +++ b/mach/proto/top/queue.c @@ -0,0 +1,72 @@ +#include "top.h" +#include "queue.h" + +empty_queue(q) + queue q; +{ + q->head = q->tail = (instr_p) 0; + q->qlen = 0; +} + +int empty(q) + queue q; +{ + return q->qlen == 0; +} + +remove_head(q) + queue q; +{ + if ( (q->head = q->head->fw) == (instr_p) 0) { + q->tail = (instr_p) 0; + } else { + q->head->bw = (instr_p) 0; + } + q->qlen--; +} + +add(q,instr) + register queue q; + register instr_p instr; +{ + if (q->qlen++ == 0) { + q->head = q->tail = instr; + instr->bw = (instr_p) 0; + } else { + q->tail->fw = instr; + instr->bw = q->tail; + q->tail = instr; + } + instr->fw = (instr_p) 0; +} + +insert(q,instr) + queue q; + instr_p instr; +{ + if (q->qlen++ == 0) { + q->head = q->tail = instr; + instr->fw = (instr_p) 0; + } else { + q->head->bw = instr; + instr->fw = q->head; + q->head = instr; + } + instr->bw = (instr_p) 0; +} + +join_queues(q1,q2) + queue q1,q2; +{ + if (q1->qlen > 0) { + q2->qlen += q1->qlen; + q1->tail->fw = q2->head; + if (q2->qlen > 0) { + q2->head->bw = q1->tail; + } else { + q2->tail = q1->tail; + } + q2->head = q1->head; + empty_queue(q1); + } +} diff --git a/mach/proto/top/queue.h b/mach/proto/top/queue.h new file mode 100644 index 000000000..d2adebf04 --- /dev/null +++ b/mach/proto/top/queue.h @@ -0,0 +1,12 @@ +typedef struct item *item_p; +typedef struct queue_t *queue; + +struct queue_t { + instr_p head; + instr_p tail; + int qlen; +}; + +#define qhead(q) (q)->head +#define qlength(q) (q)->qlen +#define next(x) (x)->fw diff --git a/mach/proto/top/top.c b/mach/proto/top/top.c new file mode 100644 index 000000000..11ea82476 --- /dev/null +++ b/mach/proto/top/top.c @@ -0,0 +1,651 @@ +#include +#include "gen.h" +#include "top.h" +#include "queue.h" + +/* STANDARD MACHINE-INDEPENT C CODE *************/ + +extern char *lstrip(); +extern instr_p newinstr(); +extern instr_p read_instr(); +extern instr_p gen_instr(); +extern char *eval_templ(); +extern instr_p malloc(); + +struct variable var[NRVARS+1]; +struct variable ANY; /* ANY symbol matching any instruction */ + +char *REST; /* Opcode of first instruction not matched by current pattern */ + +#include "gen.c" + + +/* Macros for efficiency: */ + +#define is_white(c) ( (c) == ' ' || (c) == '\t') + +/* Skip white space in the unprocessed part of instruction 'ip' */ +#define skip_white(ip) while (is_white(*(ip)->rest_line)) (ip)->rest_line++ + +main() +{ + optimize(); + exit(0); +} + + +/* Optimize the standard input. + * The optimizer uses a moving window. The instructions in the current + * window are matched against a set of patterns generated from the + * machine description table. If the match fails, the first instruction of + * the window is moved to a back-up queue and a new instruction is + * read from the input and appended to the end of the window. + * If a matching pattern is found (and its operands etc. are ok), + * the instructions at the head of the window are replaced by new + * instructions, as indicated in the descriptor table; a new window + * is created, consisting of the back-up instructions and the new + * instructions and the rest of the old window. So effectively the + * window moves a bit to the left after every hit. Hence sequences of + * optimizations like: + * movl r0,x ; cmpl $0,x -> movl r0,x ; tstl x -> movl r0,x + * are captured without having a separate pattern for "movl ; cmpl". + * + * Whenever the backup queue exceeds some threshold, its first instruction + * is written to the output and is removed. + */ + +optimize() +{ + struct queue_t windowq, backupq; + queue window, backup; + instr_p ip; + bool change; + + window = &windowq; + backup = &backupq; + empty_queue(window); + empty_queue(backup); + fill_window(window,MIN_WINDOW_SIZE); + while (!empty(window)) { + if (try_hashentry(hashtab[hash(window)],window) || + try_hashentry(hashany,window)) { + join_queues(backup,window); + } else { + ip = qhead(window); + remove_head(window); + add(backup,ip); + if (qlength(backup) > MIN_WINDOW_SIZE) { + write_first(backup); + } + } + fill_window(window,MIN_WINDOW_SIZE); + } + while (!empty(backup)) write_first(backup); +} + + + +bool try_hashentry(list,window) + int *list; + queue window; +{ + int *pp; + patdescr_p p; + + for (pp = list; *pp != -1; pp++) { + p = &patterns[*pp]; + if (check_pattern(p,window) && + check_operands(p,window) && + check_constraint(p-patterns)) { + xform(p,window); + return TRUE; + } + } + return FALSE; +} + + +/* TEMP. */ + +/* int hash(w) + queue w; +{ + instr_p ip; + + ip = qhead(w); + return ip->opc[0] % 31; +} +*/ + + +int hash(w) + queue w; +{ + register char *p; + register sum,i; + instr_p ip; + + ip = qhead(w); +/* for (sum=0,p=ip->opc;*p;p++) + sum += *p; +*/ + + for (sum=i=0,p=ip->opc;*p;i += 3) + sum += (*p++)<<(i&07); + return(sum%127); +} + +/* Fill the working window until it contains at least 'len' items. + * When end-of-file is encountered it may contain fewer items. + */ + +fill_window(w,len) + queue w; +{ + instr_p ip; + + while(qlength(w) < len) { + if ((ip = read_instr()) == NIL) break; + ip->rest_line = ip->line; + set_opcode(ip); + add(w,ip); + } +} + +write_first(w) + queue w; +{ + instr_p ip; + + write_instr(ip = qhead(w)); + remove_head(w); + oldinstr(ip); +} + + +/* Try to recognize the opcode part of an instruction */ + +set_opcode(ip) + instr_p ip; +{ + register char *p,*q; + char *qlim; + + if (ip->state == JUNK) return; + skip_white(ip); + p = ip->rest_line; + if (*p == LABEL_STARTER) { + strcpy(ip->opc,"labdef"); + ip->state = ONLY_OPC; + return; + } + q = ip->opc; + qlim = q + MAX_OPC_LEN; + while(*p != OPC_TERMINATOR && *p != '\n') { + if (q == qlim) { + ip->state = JUNK; + return; + } + *q++ = *p++; + } + *q = '\0'; + ip->rest_line = p; + ip->state = (well_shaped(ip->opc) ? ONLY_OPC : JUNK); +} + + + +/* Check if pattern 'p' matches the current input */ + +bool check_pattern(p,w) + patdescr_p p; + queue w; +{ + register idescr_p id_p; + idescr_p idlim; + register instr_p ip; + + ip = qhead(w); + ANY.vstate = UNINSTANTIATED; + idlim = &p->pat[p->patlen]; + for (id_p = p->pat; id_p < idlim; id_p++) { + if (ip == NIL || ip->state == JUNK) return FALSE; + if (id_p->opcode == (char *) 0) { + unify(ip->opc,&ANY); + } else { + if (strcmp(ip->opc,id_p->opcode) != 0) return FALSE; + } + ip = next(ip); + } + REST = ip->opc; + return TRUE; +} + + + +bool check_operands(p,w) + patdescr_p p; + queue w; +{ + instr_p ip; + idescr_p id_p; + int n; + + /* fprintf(stderr,"try pattern %d\n",p-patterns); */ + clear_vars(); + for (id_p = p->pat, ip = qhead(w); id_p < &p->pat[p->patlen]; + id_p++, ip = next(ip)) { + assert(ip != NIL); + if (ip->state == JUNK || + (ip->state == ONLY_OPC && !split_operands(ip))) { + return FALSE; + } + for (n = 0; n < MAXOP; n++) { + if (!opmatch(&id_p->templates[n],ip->op[n])) { + return FALSE; + } + } + } + /* fprintf(stderr,"yes\n"); */ + return TRUE; +} + + + +/* Reset all variables to uninstantiated */ + +clear_vars() +{ + register v; + + for (v = 1; v <= NRVARS; v++) var[v].vstate = UNINSTANTIATED; +} + + +/* See if operand 's' matches the operand described by template 't'. + * As a side effect, any uninstantiated variables used in the + * template may become instantiated. For such a variable we also + * check if it satisfies the constraint imposed on it in the + * mode-definitions part of the table. + */ + +bool opmatch(t,s) + templ_p t; + char *s; +{ + char *l, buf[MAXOPLEN]; + bool was_instantiated; + int vno; + + vno = t->varno; + if (vno == -1 || s[0] == '\0' ) { + return (vno == -1 && s[0] == '\0'); + } + was_instantiated = (var[vno].vstate == INSTANTIATED); + strcpy(buf,s); + if ( (l=lstrip(buf,t->lctxt)) != NULLSTRING && rstrip(l,t->rctxt)) { + return vno == 0 || (unify(l,&var[vno]) && + (was_instantiated || tok_chk(vno))); + } + return FALSE; +} + + + +/* Try to recognize the operands of an instruction */ + +bool split_operands(ip) + instr_p ip; +{ + int i; + bool res; + + if (strcmp(ip->opc,"labdef") ==0) { + labeldef(ip); + } else { + for (i = 0; operand(ip,i) && op_separator(ip); i++); + } + res = remainder_empty(ip); + ip->state = (res ? DONE : JUNK); + return res; +} + + + +labeldef(ip) + instr_p ip; +{ + char *p; + int oplen; + + p = ip->rest_line; + while( *p != LABEL_TERMINATOR) p++; + oplen = p - ip->rest_line; + if (oplen == 0 || oplen > MAXOPLEN) return; + strncpy(ip->op[0],ip->rest_line,oplen); + ip->op[0][oplen] = '\0'; + ip->rest_line = ++p; + return; +} + + + + +/* Try to recognize the next operand of instruction 'ip' */ + +bool operand(ip,n) + register instr_p ip; +{ + register char *p; + int oplen; + + skip_white(ip); + p = ip->rest_line; + while( *p != OP_SEPARATOR && *p != '\n') p++; + oplen = p - ip->rest_line; + if (oplen == 0 || oplen > MAXOPLEN) return FALSE; + strncpy(ip->op[n],ip->rest_line,oplen); + ip->op[n][oplen] = '\0'; + ip->rest_line = p; + return TRUE; +} + + + +/* See if the unprocessed part of instruction 'ip' is empty + * (or contains only white space). + */ + +bool remainder_empty(ip) + instr_p ip; +{ + skip_white(ip); + return *ip->rest_line == '\n'; +} + + +/* Try to match 'ctxt' at the beginning of string 'str'. If this + * succeeds then return a pointer to the rest (unmatched part) of 'str'. + */ + +char *lstrip(str,ctxt) + register char *str, *ctxt; +{ + assert(ctxt != NULLSTRING); + while (*str != '\0' && *str == *ctxt) { + str++; + ctxt++; + } + return (*ctxt == '\0' ? str : NULLSTRING); +} + + + +/* Try to match 'ctxt' at the end of 'str'. If this succeeds then + * replace truncate 'str'. + */ + +bool rstrip(str,ctxt) + char *str,*ctxt; +{ + register char *s, *c; + + for (s = str; *s != '\0'; s++); + for (c = ctxt; *c != '\0'; c++); + while (c >= ctxt) { + if (s < str || *s != *c--) return FALSE; + *s-- = '\0'; + } + return TRUE; +} + + + +/* Try to unify variable 'v' with string 'str'. If the variable + * was instantiated the unification only succeeds if the variable + * and the string match; else the unification succeeds and the + * variable becomes instantiated to the string. + */ + +bool unify(str,v) + char *str; + struct variable *v; +{ + if (v->vstate == UNINSTANTIATED) { + v->vstate = INSTANTIATED; + strcpy(v->value,str); + return TRUE; + } else { + return strcmp(v->value,str) == 0; + } +} + + + +/* Transform the working window according to pattern 'p' */ + +xform(p,w) + patdescr_p p; + queue w; +{ + register instr_p ip; + int i; + + for (i = 0; i < p->patlen; i++) { + ip = qhead(w); + remove_head(w); + oldinstr(ip); + } + replacement(p,w); +} + + + +/* Generate the replacement for pattern 'p' and insert it + * at the front of the working window. + * Note that we generate instructions in reverser order. + */ + +replacement(p,w) + patdescr_p p; + queue w; +{ + idescr_p id_p; + + for (id_p = &p->repl[p->replen-1]; id_p >= p->repl; id_p--) { + insert(w,gen_instr(id_p)); + } +} + + + +/* Generate an instruction described by 'id_p'. + * We build a 'line' for the new instruction and call set_opcode() + * to re-recognize its opcode. Hence generated instructions are treated + * in exactly the same way as normal instructions that are just read in. + */ + +instr_p gen_instr(id_p) + idescr_p id_p; +{ + char *opc; + instr_p ip; + templ_p t; + register char *s; + bool islabdef; + int n; + static char tmp[] = "x"; + + ip = newinstr(); + s = ip->line; + opc = id_p->opcode; + if (opc == (char *) 0) opc = ANY.value; + if (strcmp(opc,"labdef") == 0) { + islabdef = TRUE; + s[0] = '\0'; + } else { + strcpy(s,opc); + tmp[0] = OPC_TERMINATOR; + strcat(s,tmp); + islabdef = FALSE; + } + for (n = 0; n < MAXOP;) { + t = &id_p->templates[n++]; + if (t->varno == -1) break; + strcat(s,t->lctxt); + if (t->varno != 0) strcat(s,var[t->varno].value); + strcat(s,t->rctxt); + if (ntemplates[n].varno!=-1) { + tmp[0] = OP_SEPARATOR; + strcat(s,tmp); + } + } + if (islabdef) { + tmp[0] = LABEL_TERMINATOR; + strcat(s,tmp); + } + strcat(s,"\n"); + ip->rest_line = ip->line; + set_opcode(ip); + return ip; +} + + + +/* Reading and writing instructions. + * An instruction is assumed to be on one line. The line + * is copied to the 'line' field of an instruction struct, + * terminated by a \n and \0. If the line is too long (>MAXLINELEN), + * it is split into pieces of length MAXLINELEN and the state of + * each such struct is set to JUNK (so it will not be optimized). + */ + +static bool junk_state = FALSE; /* TRUE while processing a very long line */ + +instr_p read_instr() +{ + register instr_p ip; + register int c; + register char *p; + char *plim; + + ip = newinstr(); + plim = &ip->line[MAXLINELEN]; + if (( c = getchar()) == EOF) return NIL; + for (p = ip->line; p < plim;) { + *p++ = c; + if (c == '\n') { + *p = '\0'; + if (junk_state) ip->state = JUNK; + junk_state = FALSE; + return ip; + } + c = getchar(); + } + ungetc(c,stdin); + *p = '\0'; + junk_state = ip->state = JUNK; + return ip; +} + + +write_instr(ip) + instr_p ip; +{ + register char *p; + + for (p = ip->line; *p != '\0'; p++) { + putchar(*p); + } +} + + + +/* Core allocation. + * As all instruction struct have the same size we can re-use every struct. + * We maintain a pool of free instruction structs. + */ + +static instr_p instr_pool; +int nr_mallocs = 0; /* for statistics */ + +instr_p newinstr() +{ + register instr_p ip; + int i; + + if (instr_pool == NIL) { + instr_pool = malloc(sizeof(struct instruction)); + nr_mallocs++; + } + assert(instr_pool != NIL); + ip = instr_pool; + instr_pool = instr_pool->fw; + ip->fw = ip->bw = NIL; + ip->rest_line = NULLSTRING; + ip->line[0] = ip->opc[0] = '\0'; + ip->state = ONLY_OPC; + for (i = 0; i < MAXOP; i++) ip->op[i][0] = '\0'; + return ip; +} + +oldinstr(ip) + instr_p ip; +{ + ip->fw = instr_pool; + instr_pool = ip; +} + + + +/* Debugging stuff */ + +badassertion(file,line) + char *file; + unsigned line; +{ + fprintf(stderr,"assertion failed file %s, line %u\n",file,line); + error("assertion"); +} + +/* VARARGS1 */ +error(s,a) + char *s,*a; +{ + fprintf(stderr,s,a); + fprintf(stderr,"\n"); + _cleanup(); + abort(); + exit(-1); +} + +/* Low level routines */ + +bool op_separator(ip) + instr_p ip; +{ + skip_white(ip); + if (*(ip->rest_line) == OP_SEPARATOR) { + ip->rest_line++; + return TRUE; + } else { + return FALSE; + } +} + + + +bool well_shaped(opc) + char *opc; +{ + return is_letter(opc[0]); +} + + +bool is_letter(c) +{ + return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); +} + +/* is_white(c) : turned into a macro, see beginning of file */ + diff --git a/mach/proto/top/top.h b/mach/proto/top/top.h new file mode 100644 index 000000000..899b7fe20 --- /dev/null +++ b/mach/proto/top/top.h @@ -0,0 +1,88 @@ +/* Tunable constants; may be overruled by machine descriptor table */ + +#ifndef OP_SEPARATOR +#define OP_SEPARATOR ',' +#endif +#ifndef LABEL_TERMINATOR +#define LABEL_TERMINATOR ':' +#endif +#ifndef LABEL_STARTER +#define LABEL_STARTER 'I' +#endif +#ifndef OPC_TERMINATOR +#define OPC_TERMINATOR ' ' +#endif + +#ifndef MAX_OPC_LEN +#define MAX_OPC_LEN 10 +#endif +#ifndef MAXOPLEN +#define MAXOPLEN 25 +#endif +#ifndef MAXOP +#define MAXOP 2 +#endif +#ifndef MAXLINELEN +#define MAXLINELEN 100 +#endif +#ifndef MAXVARLEN +#define MAXVARLEN 25 +#endif + + +typedef struct instruction *instr_p; +typedef struct pattern_descr *patdescr_p; +typedef struct instr_descr *idescr_p; +typedef struct template *templ_p; + +struct instruction { + instr_p fw; + instr_p bw; + char line[MAXLINELEN+1]; + char *rest_line; + char opc[MAX_OPC_LEN+1]; + char op[MAXOP][MAXOPLEN+1]; + short state; +}; + +/* state: */ +#define ONLY_OPC 0 +#define JUNK 1 +#define DONE 2 + +struct variable { + int vstate; + char value[MAXVARLEN]; +}; + +/* vstate: */ +#define UNINSTANTIATED 0 +#define INSTANTIATED 1 + +struct pattern_descr { + int patlen; + idescr_p pat; + int replen; + idescr_p repl; +}; + +struct template { + char *lctxt; + int varno; + char *rctxt; +}; + +struct instr_descr { + char *opcode; + struct template templates[MAXOP]; +}; + +typedef int bool; + +#define TRUE 1 +#define FALSE 0 + +#define NIL (instr_p) 0 +#define NULLSTRING (char *) 0 + +#define assert(x) if(!(x)) badassertion(__FILE__,__LINE__) diff --git a/mach/vax4/top/Makefile b/mach/vax4/top/Makefile new file mode 100644 index 000000000..37628d51b --- /dev/null +++ b/mach/vax4/top/Makefile @@ -0,0 +1,41 @@ +EM=../../.. +PREFLAGS=-I. +PFLAGS= +CFLAGS=$(PREFLAGS) $(PFLAGS) -O +LDFLAGS=-i $(PFLAGS) +LINTOPTS=-hbxac +CDIR=$(EM)/mach/proto/top +CFILES=$(CDIR)/top.c $(CDIR)/queue.c gen.c +OFILES=top.o queue.o gen.o + +all: gen.c + make top + +top: $(OFILES) + $(CC) $(LDFLAGS) $(OFILES) $(LIBS) -o top + +top.o: $(CDIR)/top.c + $(CC) -c $(CFLAGS) $(CDIR)/top.c + +queue.o: $(CDIR)/queue.c + $(CC) -c $(CFLAGS) $(CDIR)/queue.c + +install: all + $(EM)/mach/install top + +cmp: all + -$(EM)/mach/compare top + +gen.c: table + $(EM)/lib/topgen table + +lint: $(CFILES) + lint $(LINTOPTS) $(PREFLAGS) $(CFILES) + +clean: + rm -f *.o gen.c gen.h top + +top.o: gen.h +top.o: $(CDIR)/top.h +top.o: $(CDIR)/queue.h +queue.o: $(CDIR)/queue.h diff --git a/mach/vax4/top/table b/mach/vax4/top/table new file mode 100644 index 000000000..ea754dd4c --- /dev/null +++ b/mach/vax4/top/table @@ -0,0 +1,287 @@ +/* VAX descriptor table for ACK target optimizer, + * Prolog prototype + */ + +/* tunable constants-> */ + +MAXOP 4; +MAXLINELEN 50; +LABEL_STARTER 'L'; +OPC_TERMINATOR ' '; + +%%; + +ZERO {strcmp(VAL,"$0") == 0}; +ONE {strcmp(VAL,"$1") == 0}; +M_ONE {strcmp(VAL,"$-1") == 0}; +CONST {VAL[0] == '$'}; +NUM,NUM1 {is_number(VAL)}; +REG {is_register(VAL)}; +SREG {is_scratchreg(VAL)}; +LAB,LAB2 {VAL[0] == 'L'}; +A,B {no_side_effects(VAL) }; +X,Y,LOG {TRUE}; + +%%; + +movab 1(X),X -> incl X; +movab -1(X),X -> decl X; + +movzbw ZERO,X -> clrw X; +movzbl ZERO,X -> clrl X; +movb ZERO,X -> clrb X; +movw ZERO,X -> clrw X; +movl ZERO,X -> clrl X; +cvtbw ZERO,X -> clrw X; +cvtww ZERO,X -> clrw X; +cvtbl ZERO,X -> clrl X; +cvtwl ZERO,X -> clrl X; + +/* change 3-operand instructions to 2-operand instructions */ + +addw3 X,Y,Y -> addw2 X,Y; +addl3 X,Y,Y -> addl2 X,Y; +addf3 X,Y,Y -> addf2 X,Y; +addd3 X,Y,Y -> addd2 X,Y; + +addw3 X,Y,X -> addw2 Y,X; +addl3 X,Y,X -> addl2 Y,X; +addf3 X,Y,X -> addf2 Y,X; +addd3 X,Y,X -> addd2 Y,X; + +subw3 X,Y,Y -> subw2 X,Y; +subl3 X,Y,Y -> subl2 X,Y; +subf3 X,Y,Y -> subf2 X,Y; +subd3 X,Y,Y -> subd2 X,Y; + +mulw3 X,Y,Y -> mulw2 X,Y; +mull3 X,Y,Y -> mull2 X,Y; +mulf3 X,Y,Y -> mulf2 X,Y; +muld3 X,Y,Y -> muld2 X,Y; + +mulw3 X,Y,X -> mulw2 Y,X; +mull3 X,Y,X -> mull2 Y,X; +mulf3 X,Y,X -> mulf2 Y,X; +muld3 X,Y,X -> muld2 Y,X; + +divw3 X,Y,Y -> divw2 X,Y; +divl3 X,Y,Y -> divl2 X,Y; +divf3 X,Y,Y -> divf2 X,Y; +divd3 X,Y,Y -> divd2 X,Y; + +xorw3 X,Y,Y -> xorw2 X,Y; +xorl3 X,Y,Y -> xorl2 X,Y; + +bisw3 X,Y,Y -> bisw2 X,Y; +bisl3 X,Y,Y -> bisl2 X,Y; +bisw3 X,Y,X -> bisw2 Y,X; +bisl3 X,Y,X -> bisl2 Y,X; + +bicw3 X,Y,Y -> bicw2 X,Y; +bicl3 X,Y,Y -> bicl2 X,Y; + +/* eliminate negative constants */ + +addw2 $-NUM,X -> subw2 $NUM,X; +addl2 $-NUM,X -> subl2 $NUM,X; +addw3 $-NUM,X,Y -> subw3 $NUM,X,Y; +addl3 $-NUM,X,Y -> subl3 $NUM,X,Y; +addw3 X,$-NUM,Y -> subw3 $NUM,X,Y; +addl3 X,$-NUM,Y -> subl3 $NUM,X,Y; + +subw2 $-NUM,X -> addw2 $NUM,X; +subl2 $-NUM,X -> addl2 $NUM,X; +subw3 $-NUM,X,Y -> addw3 $NUM,X,Y; +subl3 $-NUM,X,Y -> addl3 $NUM,X,Y; +subw3 X,$-NUM,Y -> addw3 $NUM,X,Y; +subl3 X,$-NUM,Y -> addl3 $NUM,X,Y; + +/* use special instructions */ + +addw2 ONE,X -> incw X; +addl2 ONE,X -> incl X; +subw2 ONE,X -> decw X; +subl2 ONE,X -> decl X; + +addw2 M_ONE,X -> decw X; +addl2 M_ONE,X -> decl X; +subw2 M_ONE,X -> incw X; +subl2 M_ONE,X -> incl X; + +bitw $NUM,A : jneq LAB + {is_poweroftwo(NUM,LOG)}-> jbs $LOG,A,LAB; +bitl $NUM,A : jneq LAB + {is_poweroftwo(NUM,LOG)}-> jbs $LOG,A,LAB; +bitw $NUM,A : jeql LAB + {is_poweroftwo(NUM,LOG)}-> jbc $LOG,A,LAB; +bitl $NUM,A : jeql LAB + {is_poweroftwo(NUM,LOG)}-> jbc $LOG,A,LAB; +bitw ONE,A : jneq LAB -> jlbs A,LAB; +bitl ONE,A : jneq LAB -> jlbs A,LAB; +bitw ONE,A : jneq LAB -> jlbc A,LAB; +bitl ONE,A : jneq LAB -> jlbc A,LAB; +ashl $-NUM,A,REG : bicw2 $~NUM1,REG + {is_p2m1(NUM1,LOG)} -> extzv $NUM,$LOG,A,REG; +ashl $-NUM,A,REG : bicl2 $~NUM1,REG + {is_p2m1(NUM1,LOG)} -> extzv $NUM,$LOG,A,REG; + +/* stack optimizations */ + +movl (sp)+,X : pushl X -> movl (sp),X; +tstw (sp)+ : movw X,-(sp) -> movw X,(sp); +tstl (sp)+ : movl X,-(sp) -> movl X,(sp); +tstw (sp)+ : clrw -(sp) -> clrw (sp); +tstl (sp)+ : clrl -(sp) -> clrl (sp); +tstw (sp)+ : movzbw X,-(sp) -> movzbw X,(sp); +tstl (sp)+ : movzbl X,-(sp) -> movzbl X,(sp); +tstw (sp)+ : cvtbw X,-(sp) -> cvtbw X,(sp); +tstl (sp)+ : cvtbl X,-(sp) -> cvtbl X,(sp); +tstw (sp)+ : tstw X -> movw X,(sp)+; +tstl (sp)+ : tstl X -> movl X,(sp)+; +tstl (sp)+ : pushl X -> movl X,(sp); +tstl (sp)+ : pushab X -> movab X,(sp); +tstl (sp)+ : pushaw X -> movaw X,(sp); +tstl (sp)+ : pushal X -> moval X,(sp); +tstl (sp)+ : pushaq X -> movaq X,(sp); + +/* push constants */ + +clrw -(sp) : movw $NUM,-(sp) -> pushl $NUM; +clrw -(sp) : mnegw $NUM, -(sp) -> movzwl $-NUM,-(sp); +clrw -(sp) : movw X,-(sp) -> movzwl X,-(sp); +clrw -(sp) : cvtbw $NUM,-(sp) -> pushl $NUM; +clrw -(sp) : cvtbw CONST,-(sp) -> movzwl CONST,-(sp); + +/* compare with zero */ + +cmpb X,ZERO -> tstb X; +cmpw X,ZERO -> tstw X; +cmpl X,ZERO -> tstl X; +cmpb ZERO,X : jneq LAB -> tstb X: jneq LAB; +cmpw ZERO,X : jneq LAB -> tstw X: jneq LAB; +cmpl ZERO,X : jneq LAB -> tstl X: jneq LAB; + +cmpb ZERO,X : jeql LAB -> tstb X: jeql LAB; +cmpw ZERO,X : jeql LAB -> tstw X: jeql LAB; +cmpl ZERO,X : jeql LAB -> tstl X: jeql LAB; + +cmpb ZERO,X : jgtr LAB -> tstb X: jlss LAB; +cmpw ZERO,X : jgtr LAB -> tstw X: jlss LAB; +cmpl ZERO,X : jgtr LAB -> tstl X: jlss LAB; + +cmpb ZERO,X : jlss LAB -> tstb X: jgtr LAB; +cmpw ZERO,X : jlss LAB -> tstw X: jgtr LAB; +cmpl ZERO,X : jlss LAB -> tstl X: jgtr LAB; + +cmpb ZERO,X : jgeq LAB -> tstb X: jleq LAB; +cmpw ZERO,X : jgeq LAB -> tstw X: jleq LAB; +cmpl ZERO,X : jgeq LAB -> tstl X: jleq LAB; + +cmpb ZERO,X : jleq LAB -> tstb X: jgeq LAB; +cmpw ZERO,X : jleq LAB -> tstw X: jgeq LAB; +cmpl ZERO,X : jleq LAB -> tstl X: jgeq LAB; + +/* compare with -1 */ + +cmpw M_ONE,SREG : jeql LAB -> incw SREG : jeql LAB; +cmpl M_ONE,SREG : jeql LAB -> incl SREG : jeql LAB; +cmpw M_ONE,SREG : jneq LAB -> incw SREG : jneq LAB; +cmpl M_ONE,SREG : jneq LAB -> incl SREG : jneq LAB; + +/* eliminate redundant tests */ + +movw X,A : tstw A -> movw X,A; +movl X,A : tstl A -> movl X,A; +movw A,X : tstw A -> movw A,X; +movl A,X : tstl A -> movl A,X; + +/* skip over jumps */ + +jeql LAB : jbr LAB2 : labdef LAB -> jneq LAB2 : labdef LAB; +jgeq LAB : jbr LAB2 : labdef LAB -> jlss LAB2 : labdef LAB; +jgtr LAB : jbr LAB2 : labdef LAB -> jleq LAB2 : labdef LAB; +jlss LAB : jbr LAB2 : labdef LAB -> jgeq LAB2 : labdef LAB; +jleq LAB : jbr LAB2 : labdef LAB -> jgtr LAB2 : labdef LAB; +jneq LAB : jbr LAB2 : labdef LAB -> jeql LAB2 : labdef LAB; + +/* Register propagation */ + +movl REG,A : ANY *A -> movl REG,A : ANY *REG; +movl REG,A : ANY *A,X -> movl REG,A : ANY *REG,X; +movl REG,A : ANY X,*A -> movl REG,A : ANY X,*REG; +movl REG,A : ANY *A,X,Y -> movl REG,A : ANY *REG,X,Y; +movl REG,A : ANY X,*A,Y -> movl REG,A : ANY X,*REG,Y; +movl REG,A : ANY X,Y,*A -> movl REG,A : ANY X,Y,*REG; + + +%%; + +/* Auxiliary routines: */ + +int is_number(s) + register char *s; +{ + while (*s >= '0' && *s <= '9') s++; + return *s == '\0'; +} + +int is_poweroftwo(s,t) + char *s,*t; +{ + long arg, pow; + register int i; + + arg = atol(s); + pow = 1; + i = 0; + while (pow > 0) { + if (pow == arg) { + sprintf(t,"%d",i); + return 1; + } + pow <<= 1; + i++; + } + return 0; +} + +int is_p2m1(s,t) + char *s,*t; +{ + long arg; + char buf[MAXLINELEN]; + + arg = atol(s)+1; + sprintf(buf,"%ld",arg); + return is_poweroftwo(buf,t); +} + +int no_side_effects(s) + register char *s; +{ + + for(;;) { + switch(*s++) { + case '\0': return TRUE; + case '-': if (*s == '(') return FALSE; break; + case ')': if (*s == '+') return FALSE; break; + } + } + /* NOTREACHED */ +} + +int is_register(s) + register char *s; +{ + if (*s++ == 'r' && *s >= '0' && *s <= '9') { + if (*s++ == '1' && (*s == '0' || *s == '1')) s++; + return *s == '\0'; + } + return FALSE; +} + +int is_scratchreg(s) + register char *s; +{ + return *s++ == 'r' && *s >= '0' && *s++ <= '3' && *s == '\0'; +} -- 2.34.1