From 4ba6e7a39c2e0ef4671709baa928bf4859dbc140 Mon Sep 17 00:00:00 2001 From: sater Date: Tue, 8 Jan 1985 15:34:54 +0000 Subject: [PATCH] *** empty log message *** --- mach/proto/ncg/assert.h | 7 + mach/proto/ncg/codegen.c | 874 +++++++++++++++++++++++++++++++++++++++ mach/proto/ncg/compute.c | 366 ++++++++++++++++ mach/proto/ncg/data.h | 64 +++ mach/proto/ncg/equiv.c | 105 +++++ mach/proto/ncg/equiv.h | 8 + mach/proto/ncg/extern.h | 50 +++ mach/proto/ncg/fillem.c | 676 ++++++++++++++++++++++++++++++ mach/proto/ncg/gencode.c | 143 +++++++ mach/proto/ncg/glosym.c | 52 +++ mach/proto/ncg/glosym.h | 9 + mach/proto/ncg/main.c | 99 +++++ mach/proto/ncg/move.c | 149 +++++++ mach/proto/ncg/nextem.c | 133 ++++++ mach/proto/ncg/param.h | 20 + mach/proto/ncg/reg.c | 175 ++++++++ mach/proto/ncg/regvar.c | 151 +++++++ mach/proto/ncg/regvar.h | 19 + mach/proto/ncg/result.h | 19 + mach/proto/ncg/salloc.c | 150 +++++++ mach/proto/ncg/state.c | 78 ++++ mach/proto/ncg/state.h | 18 + mach/proto/ncg/subr.c | 617 +++++++++++++++++++++++++++ mach/proto/ncg/types.h | 27 ++ mach/proto/ncg/var.c | 41 ++ 25 files changed, 4050 insertions(+) create mode 100644 mach/proto/ncg/assert.h create mode 100644 mach/proto/ncg/codegen.c create mode 100644 mach/proto/ncg/compute.c create mode 100644 mach/proto/ncg/data.h create mode 100644 mach/proto/ncg/equiv.c create mode 100644 mach/proto/ncg/equiv.h create mode 100644 mach/proto/ncg/extern.h create mode 100644 mach/proto/ncg/fillem.c create mode 100644 mach/proto/ncg/gencode.c create mode 100644 mach/proto/ncg/glosym.c create mode 100644 mach/proto/ncg/glosym.h create mode 100644 mach/proto/ncg/main.c create mode 100644 mach/proto/ncg/move.c create mode 100644 mach/proto/ncg/nextem.c create mode 100644 mach/proto/ncg/param.h create mode 100644 mach/proto/ncg/reg.c create mode 100644 mach/proto/ncg/regvar.c create mode 100644 mach/proto/ncg/regvar.h create mode 100644 mach/proto/ncg/result.h create mode 100644 mach/proto/ncg/salloc.c create mode 100644 mach/proto/ncg/state.c create mode 100644 mach/proto/ncg/state.h create mode 100644 mach/proto/ncg/subr.c create mode 100644 mach/proto/ncg/types.h create mode 100644 mach/proto/ncg/var.c diff --git a/mach/proto/ncg/assert.h b/mach/proto/ncg/assert.h new file mode 100644 index 000000000..3cc93b88b --- /dev/null +++ b/mach/proto/ncg/assert.h @@ -0,0 +1,7 @@ +/* $Header$ */ + +#ifndef NDEBUG +#define assert(x) if(!(x)) badassertion("x",__FILE__,__LINE__) +#else +#define assert(x) /* nothing */ +#endif diff --git a/mach/proto/ncg/codegen.c b/mach/proto/ncg/codegen.c new file mode 100644 index 000000000..b9e862c22 --- /dev/null +++ b/mach/proto/ncg/codegen.c @@ -0,0 +1,874 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "state.h" +#include "equiv.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +#define ALLOW_NEXTEM /* code generator is allowed new try of NEXTEM + in exceptional cases */ + +#define MAXPATTERN 5 +#define MAXREPLLEN 5 /* Max length of EM-replacement, should come from boot */ + +byte startupcode[] = { DO_NEXTEM }; + +byte *nextem(); +unsigned costcalc(); +unsigned docoerc(); +unsigned stackupto(); +string tostring(); +string ad2str(); + +#ifdef NDEBUG +#define DEBUG(string) +#else +#include +#define DEBUG(string) {if(Debug) fprintf(stderr,"%-*d%s\n",4*level,level,string);} +#endif + +#define BROKE() {assert(origcp!=startupcode);DEBUG("BROKE");totalcost=INFINITY;goto doreturn;} +#define CHKCOST() {if (totalcost>=costlimit) BROKE();} + +#ifdef TABLEDEBUG +int tablelines[MAXTDBUG]; +int ntableline; +int set_fd,set_size; +short *set_val; +char *set_flag; +#endif + +unsigned codegen(codep,ply,toplevel,costlimit,forced) byte *codep; unsigned costlimit; { +#ifndef NDEBUG + byte *origcp=codep; + static int level=0; +#endif + unsigned totalcost = 0; + int inscoerc=0; + int procarg[2]; +#ifdef ALLOW_NEXTEM + int paniced; + char *savebp; +#endif + state_t state; +#define SAVEST savestatus(&state) +#define RESTST restorestatus(&state) +#define FREEST /* nothing */ +#ifdef TABLEDEBUG + extern char *tablename; +#endif + +#ifndef NDEBUG + level++; + DEBUG("Entering codegen"); +#endif + for (;;) { + switch( (*codep++)&037 ) { + default: + assert(FALSE); + /* NOTREACHED */ +#ifdef TABLEDEBUG + case DO_DLINE: { + int n; + + getint(n,codep); + tablelines[ntableline++] = n; + if (ntableline>=MAXTDBUG) + ntableline -= MAXTDBUG; + if (set_fd) + set_val[n>>4] &= ~(1<<(n&017)); +#ifndef NDEBUG + if (Debug) + fprintf(stderr,"code from \"%s\", line %d\n",tablename,n); +#endif + break; + } +#endif + case DO_NEXTEM: { + byte *bp; + int n; + unsigned mindistance,dist; + register i; + int cindex; + int npos,pos[MAXRULE]; + unsigned mincost,t; + + DEBUG("NEXTEM"); + tokpatlen = 0; + nallreg=0; + if (toplevel) { + garbage_collect(); + totalcost=0; + } else { + if (--ply <= 0) + goto doreturn; + } + if (stackheight>MAXFSTACK-7) { +#ifndef NDEBUG + if (Debug) + fprintf(stderr,"Fakestack overflow threatens(%d), action ...\n",stackheight); +#endif + totalcost += stackupto(&fakestack[6],ply,toplevel); + } +#ifndef ALLOW_NEXTEM + bp = nextem(toplevel); +#else + paniced=0; + savebp = nextem(toplevel); + panic: + bp = savebp; +#endif + if (bp == 0) { + /* + * No pattern found, can be pseudo or error + * in table. + */ + if (toplevel) { + codep--; + DEBUG("pseudo"); + dopseudo(); + } else + goto doreturn; + } else { +#ifndef NDEBUG + chkregs(); +#endif + n = *bp++; + if (n==0) { /* "procedure" */ + getint(i,bp); + getint(procarg[0],bp); + getint(procarg[1],bp); + bp= &pattern[i]; + n = *bp++; + DEBUG("PROC_CALL"); + } + assert(n>0 && n<=MAXRULE); + if (n>1) { + mindistance = MAXINT; npos=0; + for(i=0;i1) { + /* + * More than 1 tokenpattern is a candidate. + * Decision has to be made by lookahead. + */ + SAVEST; + mincost = costlimit-totalcost+1; + for(i=0;icostlimit) + BROKE(); + } else { + cindex = pos[0]; + } + } else { + getint(cindex,bp); + } + + gotit: + /* + * Now cindex contains the code-index of the best candidate + * so proceed to use it. + */ + codep = &coderules[cindex]; + } + break; + } + case DO_COERC: { + DEBUG("COERC"); + tokpatlen=1; + inscoerc=1; + break; + } + case DO_XXMATCH: + DEBUG("XXMATCH"); + case DO_XMATCH: { + register i; + int temp; + + DEBUG("XMATCH"); + tokpatlen=(codep[-1]>>5)&07; + for (i=0;i>5)&07; + for(i=0;i=fakestack) { + size=tsize(tp); + while (i= fakestack) { + size = tsize(tp); + lsize= ssize(tokexp[i]); + if (size != lsize) { /* find coercion */ +#ifdef MAXSPLIT + sret = split(tp,&tokexp[i],ply,toplevel); + if (sret==0) { +#endif MAXSPLIT + totalcost += stackupto(tp,ply,toplevel); + CHKCOST(); + break; +#ifdef MAXSPLIT + } + i += sret; +#endif MAXSPLIT + } else + i += 1; + tp--; + } + nextmatch: + tp = &fakestack[stackheight-1]; + i=0; nregneeded = 0; + while (i=fakestack) { + if (!match(tp,&machsets[tokexp[i]],0)) { + cp = findcoerc(tp, &machsets[tokexp[i]]); +#ifndef NDEBUG +if (Debug>1) fprintf(stderr,"findcoerc returns %d at position %d\n",cp,i); +#endif + if (cp==0) { + for (j=0;jc3_prop==0) { + totalcost+=docoerc(tp,cp,ply,toplevel,0); + CHKCOST(); + } else { +#ifndef NDEBUG +if(Debug>1) fprintf(stderr,"Register of type %d needed, remembering...\n",cp->c3_prop); +#endif + assert(nregneededstackheight) { +#ifndef NDEBUG +if(Debug>1) fprintf(stderr,"Pattern too long, %d with only %d items on stack\n", + tokpatlen,stackheight); +#endif + stackpad = tokpatlen-stackheight; + for (j=stackheight-1;j>=0;j--) + fakestack[j+stackpad] = fakestack[j]; + for (j=0;j=fakestack;i++,tp--) { + cp = findcoerc((token_p) 0, &machsets[tokexp[i]]); + if (cp==0) { + for (j=0;jc3_prop==0) { + totalcost+=docoerc(tp,cp,ply,toplevel,0); + CHKCOST(); + } else { + assert(nregneeded1) fprintf(stderr,"Next tuple %d,%d,%d,%d\n", + tup->p_rar[0], + tup->p_rar[1], + tup->p_rar[2], + tup->p_rar[3]); +#endif + ntup = tup->p_next; + for (i=0,t=0;ip_rar[i]); + if (t2) + fprintf(stderr,"Continuing match after coercions\n"); +#endif + t += codegen(codep,ply,FALSE,mincost-t,0); + } + if (tcostlimit) { + if (besttup) + myfree(besttup); +normalfailed: if (stackpad!=tokpatlen) { + if (stackpad) { + if (costlimitp_rar[i]); + myfree(besttup); + break; + } + case DO_REMOVE: { + int texpno,nodeno; + token_p tp; + struct reginfo *rp; + + DEBUG("REMOVE"); + if (codep[-1]&32) { + getint(texpno,codep); + getint(nodeno,codep); + } else { + getint(texpno,codep); + nodeno=0; + } + for (tp= &fakestack[stackheight-tokpatlen-1];tp>=&fakestack[0];tp--) + if (match(tp,&machsets[texpno],nodeno)) { + /* investigate possible coercion to register */ + totalcost += stackupto(tp,ply,toplevel); + CHKCOST(); + break; + } + for (rp=machregs;rpr_contents,&machsets[texpno],nodeno)) + rp->r_contents.t_token=0; + break; + } + case DO_RREMOVE: { /* register remove */ + register i; + int nodeno; + token_p tp; + tkdef_p tdp; + result_t result; + + getint(nodeno,codep); + result=compute(&enodes[nodeno]); + assert(result.e_typ==EV_REG); + for (tp= &fakestack[stackheight-tokpatlen-1];tp>=&fakestack[0];tp--) + if (tp->t_token==-1) { + if(tp->t_att[0].ar==result.e_v.e_reg) + goto gotone; + } else { + tdp = &tokens[tp->t_token]; + for(i=0;it_type[i]==EV_REG && + tp->t_att[i].ar==result.e_v.e_reg) + goto gotone; + } + break; + gotone: + /* investigate possible coercion to register */ + totalcost += stackupto(tp,ply,toplevel); + CHKCOST(); + break; + } + case DO_DEALLOCATE: { + register i; + tkdef_p tdp; + int tinstno; + token_t token; + + DEBUG("DEALLOCATE"); + getint(tinstno,codep); + instance(tinstno,&token); + if (token.t_token==-1) + chrefcount(token.t_att[0].ar,-1,TRUE); + else { + tdp= &tokens[token.t_token]; + for (i=0;it_type[i]==EV_REG) + chrefcount(token.t_att[i].ar,-1,TRUE); + } + break; + } + case DO_REALLOCATE: { + struct reginfo *rp; + + DEBUG("REALLOCATE"); + for(rp=machregs+1;rpr_tcount) { + rp->r_refcount -= rp->r_tcount; + rp->r_tcount = 0; + } + break; + } + case DO_ALLOCATE: { + register i; + int j; + int tinstno; + int npos,npos2,pos[NREGS],pos2[NREGS]; + unsigned mincost,t; + struct reginfo *rp,**rpp; + token_t token,mtoken,token2; + int propno; + int exactmatch; + int decision; + + if (codep[-1]&32) { + getint(propno,codep); + getint(tinstno,codep); + DEBUG("ALLOCATE,INIT"); + } else { + getint(propno,codep); + tinstno=0; + DEBUG("ALLOCATE,EMPTY"); + } + instance(tinstno,&token); + if (!forced) { + do { + npos=exactmatch=0; + for(rpp=reglist[propno];rp= *rpp; rpp++) + if (getrefcount(rp-machregs)==0) { + pos[npos++] = rp-machregs; + if (eqtoken(&rp->r_contents,&token)) + exactmatch++; + } + /* + * Now pos[] contains all free registers with desired + * property. If none then some stacking has to take place. + */ + if (npos==0) { + if (stackheight<=tokpatlen) { + if (!toplevel) { + BROKE(); + } else + fatal("No regs available"); + } + totalcost += stackupto( &fakestack[0],ply,toplevel); + CHKCOST(); + } + } while (npos==0); + if (!exactmatch) { + npos2=npos; + for(i=0;icostlimit) + BROKE(); + } + } else { + decision = forced; + if (getrefcount(decision)!=0) + BROKE(); + token2.t_token = -1; + } + chrefcount(decision,1,FALSE); + token2.t_att[0].ar=decision; + if (token.t_token != 0) { + totalcost+=move(&token,&token2,ply,toplevel,MAXINT); + CHKCOST(); + } else + erasereg(decision); + allreg[nallreg++]=decision; + break; + } + case DO_INSTR: { + register i; + int n; + int tinstno; + token_t token; + int stringno; + + DEBUG("INSTR"); + n=((codep[-1]>>5)&07); + getint(stringno,codep); + if (toplevel) { + swtxt(); + if (stringno>10000) { + assert(stringno== 10001 || stringno== 10002); + genstr(procarg[stringno-10001]); + } else + genstr(stringno); + } + for(i=0;i0) + totalcost += tokens[token.t_token].t_cost.ct_space; + } + if (toplevel) + gennl(); + break; + } + case DO_MOVE: { + int tinstno; + token_t token,token2; + + DEBUG("MOVE"); + getint(tinstno,codep); + instance(tinstno,&token); + getint(tinstno,codep); + instance(tinstno,&token2); + totalcost += move(&token,&token2,ply,toplevel,costlimit-totalcost+1); + CHKCOST(); + break; + } + case DO_TEST: { + int tinstno; + token_t token; + + DEBUG("TEST"); + getint(tinstno,codep); + instance(tinstno,&token); + totalcost += test(&token,ply,toplevel,costlimit-totalcost+1); + CHKCOST(); + break; + } + case DO_SETCC: { + int tinstno; + token_t token; + + DEBUG("SETCC"); + getint(tinstno,codep); + instance(tinstno,&token); + setcc(&token); + break; + } + case DO_ERASE: { + int nodeno; + result_t result; + + DEBUG("ERASE"); + getint(nodeno,codep); + result=compute(&enodes[nodeno]); + assert(result.e_typ!=EV_INT && result.e_typ!=EV_ADDR); + if (result.e_typ==EV_REG) + erasereg(result.e_v.e_reg); + break; + } + case DO_TOKREPLACE: { + register i; + int tinstno; + int repllen; + token_t reptoken[MAXREPLLEN]; + + DEBUG("TOKREPLACE"); + assert(stackheight>=tokpatlen); + repllen=(codep[-1]>>5)&07; +#ifndef NDEBUG + if (Debug>2) + fprintf(stderr,"Stackheight=%d, tokpatlen=%d, repllen=%d %s\n", + stackheight,tokpatlen,repllen,inscoerc ? "(inscoerc)":""); +#endif + for(i=0;i>5)&07; + j=emp-emlines; + if (emrepllen>j) { + assert(nemlines+emrepllen-j=0;i--) + emlines[i+emrepllen-j] = emlines[i]; + nemlines += emrepllen-j; + emp += emrepllen-j; + } + emp -= emrepllen; + for (i=0;i>4]&(1<<(i&017))) + fprintf(stderr,"\"%s\", line %d\n",tablename,i); + } + } +} +#endif diff --git a/mach/proto/ncg/compute.c b/mach/proto/ncg/compute.c new file mode 100644 index 000000000..4682fb71a --- /dev/null +++ b/mach/proto/ncg/compute.c @@ -0,0 +1,366 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "glosym.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +#define LLEAF 01 +#define LDEF 02 +#define RLEAF 04 +#define RDEF 010 +#define LLDEF LLEAF|LDEF +#define RLDEF RLEAF|RDEF + +char opdesc[] = { + 0, /* EX_TOKFIELD */ + 0, /* EX_ARG */ + 0, /* EX_CON */ + 0, /* EX_ALLREG */ + LLDEF|RLDEF, /* EX_SAMESIGN */ + LLDEF|RLDEF, /* EX_SFIT */ + LLDEF|RLDEF, /* EX_UFIT */ + 0, /* EX_ROM */ + LLDEF|RLDEF, /* EX_NCPEQ */ + LLDEF|RLDEF, /* EX_SCPEQ */ + LLDEF|RLDEF, /* EX_RCPEQ */ + LLDEF|RLDEF, /* EX_NCPNE */ + LLDEF|RLDEF, /* EX_SCPNE */ + LLDEF|RLDEF, /* EX_RCPNE */ + LLDEF|RLDEF, /* EX_NCPGT */ + LLDEF|RLDEF, /* EX_NCPGE */ + LLDEF|RLDEF, /* EX_NCPLT */ + LLDEF|RLDEF, /* EX_NCPLE */ + LLDEF, /* EX_OR2 */ + LLDEF, /* EX_AND2 */ + LLDEF|RLDEF, /* EX_PLUS */ + LLDEF|RLDEF, /* EX_CAT */ + LLDEF|RLDEF, /* EX_MINUS */ + LLDEF|RLDEF, /* EX_TIMES */ + LLDEF|RLDEF, /* EX_DIVIDE */ + LLDEF|RLDEF, /* EX_MOD */ + LLDEF|RLDEF, /* EX_LSHIFT */ + LLDEF|RLDEF, /* EX_RSHIFT */ + LLDEF, /* EX_NOT */ + LLDEF, /* EX_COMP */ + 0, /* EX_COST */ + 0, /* EX_STRING */ + LLEAF, /* EX_DEFINED */ + 0, /* EX_SUBREG */ + LLDEF, /* EX_TOSTRING */ + LLDEF, /* EX_UMINUS */ + 0, /* EX_REG */ + 0, /* EX_LOWW */ + 0, /* EX_HIGHW */ + LLDEF, /* EX_INREG */ + LLDEF, /* EX_REGVAR */ +}; + +string salloc(),strcpy(),strcat(); + +string mycat(s1,s2) register string s1,s2; { + register string s; + + if (s1==0) return(s2); + if (s2==0) return(s1); + s=salloc(strlen(s1)+strlen(s2)+1); + strcpy(s,s1); + strcat(s,"+"); + strcat(s,s2); + return(s); +} + +string mystrcpy(s) register string s; { + register string r; + + r=salloc(strlen(s)); + strcpy(r,s); + return(r); +} + +char digstr[21][15]; + +string tostring(n) register word n; { + char buf[25]; + + if (n>=-20 && n<=20 && (n&1)==0) { + if (digstr[(n>>1)+10][0]==0) + sprintf(digstr[(n>>1)+10],WRD_FMT,n); + return(digstr[(n>>1)+10]); + } + sprintf(buf,WRD_FMT,n); + return(mystrcpy(buf)); +} + +result_t undefres= {EV_UNDEF}; + +result_t compute(node) register node_p node; { + result_t leaf1,leaf2,result; + register token_p tp; + int desc; + long mask,tmp; + int i,tmpreg; + glosym_p gp; + + desc=opdesc[node->ex_operator]; + if (desc&LLEAF) { + leaf1 = compute(&enodes[node->ex_lnode]); + if (desc&LDEF && leaf1.e_typ==EV_UNDEF) + return(undefres); + } + if (desc&RLEAF) { + leaf2 = compute(&enodes[node->ex_rnode]); + if (desc&RDEF && leaf2.e_typ==EV_UNDEF) + return(undefres); + } + result.e_typ=EV_INT; + switch(node->ex_operator) { + default: assert(FALSE); + case EX_TOKFIELD: + if (node->ex_lnode!=0) + tp = &fakestack[stackheight-node->ex_lnode]; + else + tp = curtoken; + switch(result.e_typ = tokens[tp->t_token].t_type[node->ex_rnode-1]) { + default: + assert(FALSE); + case EV_INT: + result.e_v.e_con = tp->t_att[node->ex_rnode-1].aw; + break; + case EV_ADDR: + result.e_v.e_addr = tp->t_att[node->ex_rnode-1].aa; + break; + case EV_REG: + result.e_v.e_reg = tp->t_att[node->ex_rnode-1].ar; + break; + } + return(result); + case EX_ARG: + return(dollar[node->ex_lnode-1]); + case EX_CON: + result.e_typ = EV_INT; + result.e_v.e_con = ((long) node->ex_rnode << 16) | ((long)node->ex_lnode&0xffff); + return(result); + case EX_REG: + result.e_typ = EV_REG; + result.e_v.e_reg = node->ex_lnode; + return(result); + case EX_ALLREG: + result.e_typ = EV_REG; + result.e_v.e_reg = allreg[node->ex_lnode-1]; +#if MAXMEMBERS!=0 + if (node->ex_rnode!=0) + result.e_v.e_reg = machregs[result.e_v.e_reg]. + r_members[node->ex_rnode-1]; +#endif + return(result); + case EX_SAMESIGN: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_typ = EV_INT; + if (leaf1.e_v.e_con>=0) + result.e_v.e_con= leaf2.e_v.e_con>=0; + else + result.e_v.e_con= leaf2.e_v.e_con<0; + return(result); + case EX_SFIT: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + mask = 0xFFFFFFFFL; + for (i=0;iex_rnode>=0 &&node->ex_rnodeex_lnode]; + if (leaf2.e_typ != EV_ADDR) + return(undefres); + if (leaf2.e_v.e_addr.ea_off!=0) + return(undefres); + gp = lookglo(leaf2.e_v.e_addr.ea_str); + if (gp == (glosym_p) 0) + return(undefres); + if ((gp->gl_rom[MAXROM]&(1<ex_rnode))==0) + return(undefres); + result.e_v.e_con = gp->gl_rom[node->ex_rnode]; + return(result); + case EX_LOWW: + result.e_v.e_con = saveemp[node->ex_lnode].em_u.em_loper&0xFFFF; + return(result); + case EX_HIGHW: + result.e_v.e_con = saveemp[node->ex_lnode].em_u.em_loper>>16; + return(result); + case EX_NCPEQ: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con==leaf2.e_v.e_con; + return(result); + case EX_SCPEQ: + assert(leaf1.e_typ == EV_ADDR && leaf2.e_typ == EV_ADDR); + result.e_v.e_con = + (strcmp(leaf1.e_v.e_addr.ea_str,leaf2.e_v.e_addr.ea_str)==0 && + leaf1.e_v.e_addr.ea_off==leaf2.e_v.e_addr.ea_off); + return(result); + case EX_RCPEQ: + assert(leaf1.e_typ == EV_REG && leaf2.e_typ == EV_REG); + result.e_v.e_con = leaf1.e_v.e_reg==leaf2.e_v.e_reg; + return(result); + case EX_NCPNE: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con!=leaf2.e_v.e_con; + return(result); + case EX_SCPNE: + assert(leaf1.e_typ == EV_ADDR && leaf2.e_typ == EV_ADDR); + result.e_v.e_con = + !(strcmp(leaf1.e_v.e_addr.ea_str,leaf2.e_v.e_addr.ea_str)==0 && + leaf1.e_v.e_addr.ea_off==leaf2.e_v.e_addr.ea_off); + return(result); + case EX_RCPNE: + assert(leaf1.e_typ == EV_REG && leaf2.e_typ == EV_REG); + result.e_v.e_con = leaf1.e_v.e_reg!=leaf2.e_v.e_reg; + return(result); + case EX_NCPGT: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con>leaf2.e_v.e_con; + return(result); + case EX_NCPGE: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con>=leaf2.e_v.e_con; + return(result); + case EX_NCPLT: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_conex_rnode])); + return(leaf1); + case EX_AND2: + assert(leaf1.e_typ == EV_INT); + if (leaf1.e_v.e_con!=0) + return(compute(&enodes[node->ex_rnode])); + return(leaf1); + case EX_PLUS: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con=leaf1.e_v.e_con+leaf2.e_v.e_con; + return(result); + case EX_CAT: + assert(leaf1.e_typ == EV_ADDR && leaf2.e_typ == EV_ADDR); + result.e_typ = EV_ADDR; + result.e_v.e_addr.ea_str = mycat(leaf1.e_v.e_addr.ea_str,leaf2.e_v.e_addr.ea_str); + result.e_v.e_addr.ea_off = leaf1.e_v.e_addr.ea_off+leaf2.e_v.e_addr.ea_off; + return(result); + case EX_MINUS: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con - leaf2.e_v.e_con; + return(result); + case EX_TIMES: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con * leaf2.e_v.e_con; + return(result); + case EX_DIVIDE: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con / leaf2.e_v.e_con; + return(result); + case EX_MOD: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con % leaf2.e_v.e_con; + return(result); + case EX_LSHIFT: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con << leaf2.e_v.e_con; + return(result); + case EX_RSHIFT: + assert(leaf1.e_typ == EV_INT && leaf2.e_typ == EV_INT); + result.e_v.e_con = leaf1.e_v.e_con >> leaf2.e_v.e_con; + return(result); + case EX_NOT: + assert(leaf1.e_typ == EV_INT); + result.e_v.e_con = !leaf1.e_v.e_con; + return(result); + case EX_COMP: + assert(leaf1.e_typ == EV_INT); + result.e_v.e_con = ~leaf1.e_v.e_con; + return(result); + case EX_STRING: + result.e_typ = EV_ADDR; + result.e_v.e_addr.ea_str = codestrings[node->ex_lnode]; + result.e_v.e_addr.ea_off = 0; + return(result); + case EX_DEFINED: + result.e_v.e_con=leaf1.e_typ!=EV_UNDEF; + return(result); + case EX_SUBREG: + result.e_typ = EV_REG; + tp= &fakestack[stackheight-node->ex_lnode]; + assert(tp->t_token == -1); + tmpreg= tp->t_att[0].ar; +#if MAXMEMBERS!=0 + if (node->ex_rnode) + tmpreg=machregs[tmpreg].r_members[node->ex_rnode-1]; +#endif + result.e_v.e_reg=tmpreg; + return(result); + case EX_TOSTRING: + assert(leaf1.e_typ == EV_INT); + result.e_typ = EV_ADDR; + result.e_v.e_addr.ea_str = 0; + result.e_v.e_addr.ea_off = leaf1.e_v.e_con; + return(result); +#ifdef REGVARS + case EX_INREG: + assert(leaf1.e_typ == EV_INT); + if ((result.e_v.e_con = isregvar((long) leaf1.e_v.e_con))>0) + result.e_v.e_con = machregs[result.e_v.e_con].r_size; + return(result); + case EX_REGVAR: + assert(leaf1.e_typ == EV_INT); + i = isregvar((long) leaf1.e_v.e_con); + if (i<=0) + return(undefres); + result.e_typ = EV_REG; + result.e_v.e_reg=i; + return(result); +#endif + case EX_UMINUS: + assert(leaf1.e_typ == EV_INT); + result.e_v.e_con = -leaf1.e_v.e_con; + return(result); + } +} diff --git a/mach/proto/ncg/data.h b/mach/proto/ncg/data.h new file mode 100644 index 000000000..809baeb07 --- /dev/null +++ b/mach/proto/ncg/data.h @@ -0,0 +1,64 @@ +/* $Header$ */ + +typedef struct cost { + short ct_space; + short ct_time; +} cost_t,*cost_p; + +typedef struct { + string ea_str; + word ea_off; +} addr_t; + +typedef struct { + int t_token; /* kind of token, -1 for register */ + union { + word aw; /* integer type */ + addr_t aa; /* address type */ + int ar; /* register type */ + } t_att[TOKENSIZE]; +} token_t,*token_p; + +struct reginfo { + int r_repr; /* index in string table */ + int r_size; /* size in bytes */ +#if MAXMEMBERS!=0 + int r_members[MAXMEMBERS]; /* register contained within this reg */ + short r_clash[REGSETSIZE]; /* set of clashing registers */ +#endif + int r_refcount; /* Times in use */ + token_t r_contents; /* Current contents */ + int r_tcount; /* Temporary count difference */ +}; + +#if MAXMEMBERS!=0 +#define clash(a,b) ((machregs[a].r_clash[(b)>>4]&(1<<((b)&017)))!=0) +#else +#define clash(a,b) ((a)==(b)) +#endif + +typedef struct { + int t_size; /* size in bytes */ + cost_t t_cost; /* cost in bytes and time */ + byte t_type[TOKENSIZE]; /* types of attributes, TT_??? */ + int t_format; /* index of formatstring */ +} tkdef_t,*tkdef_p; + +struct emline { + int em_instr; + int em_optyp; + string em_soper; + union { + word em_ioper; + long em_loper; + } em_u; +}; + +#define OPNO 0 +#define OPINT 1 +#define OPSYMBOL 2 + +typedef struct { + int rl_n; /* number in list */ + int rl_list[NREGS]; +} rl_t,*rl_p; diff --git a/mach/proto/ncg/equiv.c b/mach/proto/ncg/equiv.c new file mode 100644 index 000000000..54a695a31 --- /dev/null +++ b/mach/proto/ncg/equiv.c @@ -0,0 +1,105 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include "equiv.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +extern string myalloc(); + +int rar[MAXCREG]; +rl_p *lar; +int maxindex; +int regclass[NREGS]; +struct perm *perms; + +struct perm * +tuples(regls,nregneeded) rl_p *regls; { + int class=0; + register i,j; + + /* + * First compute equivalence classes of registers. + */ + + for (i=0;ip_next) { + for (i=0; ip_rar[i]]) + goto diff; + for (i=0; ip_rar[i],pp->p_rar[j])) + goto diff; + return; + diff: ; + } + pp = (struct perm *) myalloc(sizeof ( *pp )); + pp->p_next = perms; + for (i=0; ip_rar[i] = rar[i]; + perms = pp; + } else { + rlp=lar[index]; + for (i=rlp->rl_n-1; i>=0; i--) { + rar[index] = rlp->rl_list[i]; + permute(index+1); + } + } +} diff --git a/mach/proto/ncg/equiv.h b/mach/proto/ncg/equiv.h new file mode 100644 index 000000000..f1dc6c852 --- /dev/null +++ b/mach/proto/ncg/equiv.h @@ -0,0 +1,8 @@ +/* $Header$ */ + +#define MAXCREG 4 + +struct perm { + struct perm *p_next; + int p_rar[MAXCREG]; +}; diff --git a/mach/proto/ncg/extern.h b/mach/proto/ncg/extern.h new file mode 100644 index 000000000..a50224e6b --- /dev/null +++ b/mach/proto/ncg/extern.h @@ -0,0 +1,50 @@ +/* $Header$ */ + +extern int maxply; /* amount of lookahead allowed */ +extern int stackheight; /* # of tokens on fakestack */ +extern token_t fakestack[]; /* fakestack itself */ +extern int nallreg; /* number of allocated registers */ +extern int allreg[]; /* array of allocated registers */ +extern token_p curtoken; /* pointer to current token */ +extern result_t dollar[]; /* Values of $1,$2 etc.. */ +extern int nemlines; /* # of EM instructions in core */ +extern struct emline emlines[]; /* EM instructions itself */ +extern struct emline *emp; /* pointer to current instr */ +extern struct emline *saveemp; /* pointer to start of pattern */ +extern int tokpatlen; /* length of current stackpattern */ +extern rl_p curreglist; /* side effect of findcoerc() */ +#ifndef NDEBUG +extern int Debug; /* on/off debug printout */ +#endif + +/* + * Next descriptions are external declarations for tables created + * by bootgram. + * All definitions are to be found in tables.c (Not for humans) + */ + +extern byte coderules[]; /* pseudo code for cg itself */ +extern char stregclass[]; /* static register class */ +extern struct reginfo machregs[]; /* register info */ +extern tkdef_t tokens[]; /* token info */ +extern node_t enodes[]; /* expression nodes */ +extern string codestrings[]; /* table of strings */ +extern set_t machsets[]; /* token expression table */ +extern inst_t tokeninstances[]; /* token instance description table */ +extern move_t moves[]; /* move descriptors */ +extern test_t tests[]; /* test descriptors */ +extern byte pattern[]; /* EM patterns */ +extern int pathash[256]; /* Indices into previous */ +extern c1_t c1coercs[]; /* coercions type 1 */ +#ifdef MAXSPLIT +extern c2_t c2coercs[]; /* coercions type 2 */ +#endif MAXSPLIT +extern c3_t c3coercs[]; /* coercions type 3 */ +extern struct reginfo **reglist[]; /* lists of registers per property */ + +#define eqregclass(r1,r2) (stregclass[r1]==stregclass[r2]) + +#ifdef REGVARS +extern int nregvar[]; /* # of register variables per type */ +extern int *rvnumbers[]; /* lists of numbers */ +#endif diff --git a/mach/proto/ncg/fillem.c b/mach/proto/ncg/fillem.c new file mode 100644 index 000000000..5e87991bc --- /dev/null +++ b/mach/proto/ncg/fillem.c @@ -0,0 +1,676 @@ +#ifndef NORCSID +static char rcsid2[] = "$Header$"; +#endif + +#include +#include "assert.h" +#include +#include +#include +#include +#include +#include "mach.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#ifdef REGVARS +#include "regvar.h" +#include +#endif +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +#ifndef newplb /* retrofit for older mach.h */ +#define newplb newilb +#endif + +#ifdef fmt_id +#ifdef id_first +It is an error to define both fmt_id and id_first. +Read the documentation. +#endif +#endif + +#ifdef fmt_ilb +#ifdef ilb_fmt +It is an error to define both fmt_ilb and ilb_fmt. +Read the documentation. +#endif +#endif + +/* segment types for switchseg() */ +#define SEGTXT 0 +#define SEGCON 1 +#define SEGROM 2 +#define SEGBSS 3 + +long con(); + +#define get8() getc(emfile) + +#define MAXSTR 256 + +FILE *emfile; +extern FILE *codefile; + +int nextispseu,savetab1; +int opcode; +int offtyp; +long argval; +int dlbval; +char str[MAXSTR],argstr[32],labstr[32]; +int strsiz; +int holno=0; +int procno=0; +int curseg= -1; +int part_size=0; +word part_word=0; +int endofprog=0; +#ifdef REGVARS +int regallowed=0; +#endif + +extern char em_flag[]; +extern short em_ptyp[]; +extern long atol(); +extern double atof(); + +#define sp_cstx sp_cst2 + +string tostring(); +string holstr(); +string strarg(); +string mystrcpy(); +long get32(); + +in_init(filename) char *filename; { + + if ((emfile=freopen(filename,"r",stdin))==NULL) + error("Can't open %s",filename); + if (get16()!=sp_magic) + error("Bad format %s",filename); +} + +in_finish() { +} + +fillemlines() { + register int t,i; + register struct emline *lp; + + while ((emlines+nemlines)-empem_instr = 0; + return; + case EOF: + nextispseu=1; savetab1=t; + endofprog=1; + nemlines--; + lp->em_instr = 0; + return; + case sp_fmnem: + lp->em_instr = opcode; + break; + } + i=em_flag[lp->em_instr-sp_fmnem] & EM_PAR; + if ( i == PAR_NO ) { + lp->em_optyp = OPNO; + lp->em_soper = 0; + continue; + } + t= em_ptyp[i]; + t= getarg(t); + switch(i) { + case PAR_L: + assert(t == sp_cstx); + if (argval >= 0) + argval += TEM_BSIZE; + lp->em_optyp = OPINT; + lp->em_u.em_ioper = argval; + lp->em_soper = tostring((word) argval); + continue; + case PAR_G: + if (t != sp_cstx) + break; + lp->em_optyp = OPSYMBOL; + lp->em_soper = holstr((word) argval); + continue; + case PAR_B: + t = sp_ilb2; + break; + case PAR_D: + assert(t == sp_cstx); + lp->em_optyp = OPSYMBOL; + lp->em_soper = strarg(t); + lp->em_u.em_loper = argval; + continue; + } + lp->em_soper = strarg(t); + if (t==sp_cend) + lp->em_optyp = OPNO; + else if (t==sp_cstx) { + lp->em_optyp = OPINT; + lp->em_u.em_ioper = argval; + } else + lp->em_optyp = OPSYMBOL; + } +} + +dopseudo() { + register b,t; + register full n; + register long save; + word romcont[MAXROM+1]; + int nromwords; + int rombit,rommask; + unsigned dummy,stackupto(); + + if (nextispseu==0 || nemlines>0) + error("No table entry for %d",emlines[0].em_instr); + nextispseu=0; + switch(savetab1) { + case sp_ilb1: + case sp_ilb2: + swtxt(); + dummy = stackupto(&fakestack[stackheight-1],maxply,TRUE); + cleanregs(); + strarg(savetab1); + newilb(argstr); +#ifndef NDEBUG + { extern int Debug; extern char * strtdebug; + if (strcmp(strtdebug,argstr)==0) + Debug = strtdebug[-2]-'0'; + } +#endif + return; + case sp_dlb1: + case sp_dlb2: + case sp_dnam: + strarg(savetab1); + savelab(); + return; + case sp_fpseu: + break; + case EOF: + swtxt(); + in_finish(); + out_finish(); + popstr(0); + tstoutput(); + exit(0); + default: + error("Unknown opcode %d",savetab1); + } + switch (opcode) { + case ps_hol: + sprintf(labstr,hol_fmt,++holno); + case ps_bss: + getarg(cst_ptyp); + n = (full) argval; + t = getarg(val_ptyp); + save = argval; + getarg(cst_ptyp); + b = (int) argval; + argval = save; + bss(n,t,b); + break; + case ps_con: + switchseg(SEGCON); + dumplab(); + con(getarg(val_ptyp)); + while ((t = getarg(any_ptyp)) != sp_cend) + con(t); + break; + case ps_rom: + switchseg(SEGROM); + xdumplab(); + nromwords=0; + rommask=0; + rombit=1; + t=getarg(val_ptyp); + while (t!=sp_cend) { + if (t==sp_cstx && nromwords= 0) + r_off += TEM_BSIZE; + getarg(ptyp(sp_cst2)); + r_size = argval; + getarg(ptyp(sp_cst2)); + r_type = argval; + if (r_typereg_float) + fatal("Bad type in register message"); + if(getarg(ptyp(sp_cst2)|ptyp(sp_cend)) == sp_cend) + r_score = 0; + else { + r_score = argval; + if ( getarg(any_ptyp)!=sp_cend ) + fatal("too many parameters"); + } + tryreg(linkreg(r_off,r_size,r_type,r_score),r_type); + } +#endif + } else + mes((word)argval); + break; + case ps_exa: + strarg(getarg(sym_ptyp)); + ex_ap(argstr); + break; + case ps_ina: + strarg(getarg(sym_ptyp)); + in_ap(argstr); + break; + case ps_exp: + strarg(getarg(ptyp(sp_pnam))); + ex_ap(argstr); + break; + case ps_inp: + strarg(getarg(ptyp(sp_pnam))); + in_ap(argstr); + break; + case ps_pro: + switchseg(SEGTXT); + procno++; + strarg(getarg(ptyp(sp_pnam))); + newplb(argstr); + getarg(cst_ptyp); + prolog((full)argval); +#ifdef REGVARS + regallowed++; +#endif + break; + case ps_end: + getarg(cst_ptyp | ptyp(sp_cend)); + cleanregs(); +#ifdef REGVARS + unlinkregs(); +#endif + tstoutput(); + break; + default: + error("No table entry for %d",savetab1); + } +} + +/* ----- input ----- */ + +int getarg(typset) { + register t,argtyp; + + argtyp = t = table2(); + if (t == EOF) + fatal("unexpected EOF"); + t -= sp_fspec; + t = 1 << t; + if ((typset & t) == 0) + error("bad argument type %d",argtyp); + return(argtyp); +} + +int table1() { + register i; + + i = get8(); + if (i < sp_fmnem+sp_nmnem && i >= sp_fmnem) { + opcode = i; + return(sp_fmnem); + } + if (i < sp_fpseu+sp_npseu && i >= sp_fpseu) { + opcode = i; + return(sp_fpseu); + } + if (i < sp_filb0+sp_nilb0 && i >= sp_filb0) { + argval = i - sp_filb0; + return(sp_ilb2); + } + return(table3(i)); +} + +int table2() { + register i; + + i = get8(); + if (i < sp_fcst0+sp_ncst0 && i >= sp_fcst0) { + argval = i - sp_zcst0; + return(sp_cstx); + } + return(table3(i)); +} + +int table3(i) { + word consiz; + + switch(i) { + case sp_ilb1: + argval = get8(); + break; + case sp_dlb1: + dlbval = get8(); + break; + case sp_dlb2: + dlbval = get16(); + break; + case sp_cst2: + i = sp_cstx; + case sp_ilb2: + argval = get16(); + break; + case sp_cst4: + i = sp_cstx; + argval = get32(); + break; + case sp_dnam: + case sp_pnam: + case sp_scon: + getstring(); + break; + case sp_doff: + offtyp = getarg(sym_ptyp); + getarg(cst_ptyp); + break; + case sp_icon: + case sp_ucon: + case sp_fcon: + getarg(cst_ptyp); + consiz = (word) argval; + getstring(); + argval = consiz; + break; + } + return(i); +} + +int get16() { + register int l_byte, h_byte; + + l_byte = get8(); + h_byte = get8(); + if ( h_byte>=128 ) h_byte -= 256 ; + return l_byte | (h_byte*256) ; +} + +long get32() { + register long l; + register int h_byte; + + l = get8(); + l |= ((unsigned) get8())*256 ; + l |= get8()*256L*256L ; + h_byte = get8() ; + if ( h_byte>=128 ) h_byte -= 256 ; + return l | (h_byte*256L*256*256L) ; +} + +getstring() { + register char *p; + register n; + + getarg(cst_ptyp); + if (argval < 0 || argval > MAXSTR-1) + fatal("string/identifier too long"); + strsiz = n = (int) argval; + p = str; + while (--n >= 0) + *p++ = get8(); + *p++ = '\0'; +} + +char *strarg(t) { + register char *p; + + switch (t) { + case sp_ilb1: + case sp_ilb2: +#ifdef fmt_ilb + fmt_ilb(procno,((int) argval),argstr); +#else + sprintf(argstr,ilb_fmt,procno,(int)argval); +#endif + break; + case sp_dlb1: + case sp_dlb2: + sprintf(argstr,dlb_fmt,dlbval); + break; + case sp_cstx: + sprintf(argstr,cst_fmt,(full)argval); + break; + case sp_dnam: + case sp_pnam: +#ifdef fmt_id + fmt_id(str,argstr); +#else + p = argstr; + if (strsiz < 8 || str[0] == id_first) + *p++ = id_first; + sprintf(p,"%.*s",strsiz,str); +#endif + break; + case sp_doff: + strarg(offtyp); + for (p = argstr; *p; p++) + ; + if (argval >= 0) + *p++ = '+'; + sprintf(p,off_fmt,(full)argval); + break; + case sp_cend: + return(""); + } + return(mystrcpy(argstr)); +} + +bss(n,t,b) full n; { + register long s; + + if (n % TEM_WSIZE) + fatal("bad BSS size"); + if (b==0 +#ifdef BSS_INIT + || (t==sp_cstx && argval==BSS_INIT) +#endif BSS_INIT + ) { + switchseg(SEGBSS); + newlbss(labstr,n); + labstr[0]=0; + return; + } + switchseg(SEGCON); + dumplab(); + while (n > 0) + n -= (s = con(t)); + if (s % TEM_WSIZE) + fatal("bad BSS initializer"); +} + +long con(t) { + register i; + + strarg(t); + switch (t) { + case sp_ilb1: + case sp_ilb2: + case sp_pnam: + part_flush(); + con_ilb(argstr); + return((long)TEM_PSIZE); + case sp_dlb1: + case sp_dlb2: + case sp_dnam: + case sp_doff: + part_flush(); + con_dlb(argstr); + return((long)TEM_PSIZE); + case sp_cstx: + con_part(TEM_WSIZE,(word)argval); + return((long)TEM_WSIZE); + case sp_scon: + for (i = 0; i < strsiz; i++) + con_part(1,(word) str[i]); + return((long)strsiz); + case sp_icon: + case sp_ucon: + if (argval > TEM_WSIZE) { + part_flush(); + con_mult((word)argval); + } else { + con_part((int)argval,(word)atol(str)); + } + return(argval); + case sp_fcon: + part_flush(); + con_float(); + return(argval); + } + assert(FALSE); + /* NOTREACHED */ +} + +extern char *segname[]; + +swtxt() { + switchseg(SEGTXT); +} + +switchseg(s) { + + if (s == curseg) + return; + part_flush(); + if ((curseg = s) >= 0) + fprintf(codefile,"%s\n",segname[s]); +} + +savelab() { + register char *p,*q; + + part_flush(); + if (labstr[0]) { + dlbdlb(argstr,labstr); + return; + } + p = argstr; + q = labstr; + while (*q++ = *p++) + ; +} + +dumplab() { + + if (labstr[0] == 0) + return; + assert(part_size == 0); + newdlb(labstr); + labstr[0] = 0; +} + +xdumplab() { + + if (labstr[0] == 0) + return; + assert(part_size == 0); + newdlb(labstr); +} + +part_flush() { + + /* + * Each new data fragment and each data label starts at + * a new target machine word + */ + if (part_size == 0) + return; + con_cst(part_word); + part_size = 0; + part_word = 0; +} + +string holstr(n) word n; { + + sprintf(str,hol_off,n,holno); + return(mystrcpy(str)); +} + + +/* ----- machine dependent routines ----- */ + +#include "mach.c" diff --git a/mach/proto/ncg/gencode.c b/mach/proto/ncg/gencode.c new file mode 100644 index 000000000..d2ee010a7 --- /dev/null +++ b/mach/proto/ncg/gencode.c @@ -0,0 +1,143 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +string mystrcpy(); + +FILE *codefile; + +out_init(filename) char *filename; { + +#ifndef NDEBUG + static char stderrbuff[BUFSIZ]; + + if (Debug) { + codefile = stderr; + if (!isatty(2)) + setbuf(stderr,stderrbuff); + } else { +#endif + if (filename == (char *) 0) + codefile = stdout; + else + if ((codefile=freopen(filename,"w",stdout))==NULL) + error("Can't create %s",filename); +#ifndef NDEBUG + } +#endif +} + +out_finish() { + +#ifndef NDEBUG + if (Debug) + fflush(stderr); + else +#endif + fclose(codefile); +#ifdef TABLEDEBUG + termlset(); +#endif +} + +tstoutput() { + + if (ferror(codefile)) + error("Write error on output"); +} + +genstr(stringno) { + + fputs(codestrings[stringno],codefile); +} + +string ad2str(ad) addr_t ad; { + static char buf[100]; + + if (ad.ea_str==0) + ad.ea_str=""; + sprintf(buf,"%s%c%ld",ad.ea_str,ad.ea_off>=0 ? '+' : ' ',(long)ad.ea_off); + return(mystrcpy(buf)); +} + +praddr(ad) addr_t ad; { + + if (ad.ea_str==0) + fprintf(codefile,WRD_FMT,ad.ea_off); + else { + fprintf(codefile,"%s",ad.ea_str); + if (ad.ea_off<0) + fprintf(codefile,WRD_FMT,ad.ea_off); + else if(ad.ea_off>0) { + fputc('+',codefile); + fprintf(codefile,WRD_FMT,ad.ea_off); + } + } +} + +gennl() { + fputc('\n',codefile); +} + +prtoken(tp,leadingchar) token_p tp; { + register c; + register char *code; + register tkdef_p tdp; + + fputc(leadingchar,codefile); + if (tp->t_token == -1) { + fprintf(codefile,"%s",codestrings[machregs[tp->t_att[0].ar].r_repr]); + return; + } + tdp = &tokens[tp->t_token]; + assert(tdp->t_format != -1); + code = codestrings[tdp->t_format]; + while ((c = *code++) != 0) { + if (c>=' ' && c<='~') + fputc(c,codefile); + else { + assert(c>0 && c<=TOKENSIZE); + switch(tdp->t_type[c-1]) { + default: + assert(FALSE); + case EV_INT: + fprintf(codefile,WRD_FMT,tp->t_att[c-1].aw); + break; + case EV_ADDR: + praddr(tp->t_att[c-1].aa); + break; + case EV_REG: + fprintf(codefile,"%s",codestrings[machregs[tp->t_att[c-1].ar].r_repr]); + break; + } + } + } +} diff --git a/mach/proto/ncg/glosym.c b/mach/proto/ncg/glosym.c new file mode 100644 index 000000000..cf8f0297f --- /dev/null +++ b/mach/proto/ncg/glosym.c @@ -0,0 +1,52 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "param.h" +#include "tables.h" +#include "types.h" +#include "glosym.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +extern string myalloc(); + +glosym_p glolist= (glosym_p) 0; + +enterglo(name,romp) string name; word *romp; { + register glosym_p gp; + register i; + + gp = (glosym_p) myalloc(sizeof *gp); + gp->gl_next = glolist; + gp->gl_name = (string) myalloc(strlen(name)+1); + strcpy(gp->gl_name,name); + for (i=0;i<=MAXROM;i++) + gp->gl_rom[i] = romp[i]; + glolist = gp; +} + +glosym_p lookglo(name) string name; { + register glosym_p gp; + + for (gp=glolist;gp != (glosym_p) 0; gp=gp->gl_next) + if (strcmp(gp->gl_name,name)==0) + return(gp); + return((glosym_p) 0); +} diff --git a/mach/proto/ncg/glosym.h b/mach/proto/ncg/glosym.h new file mode 100644 index 000000000..7fb4c7cf1 --- /dev/null +++ b/mach/proto/ncg/glosym.h @@ -0,0 +1,9 @@ +/* $Header$ */ + +typedef struct glosym { + struct glosym *gl_next; + string gl_name; + word gl_rom[MAXROM+1]; +} glosym_t,*glosym_p; + +glosym_p lookglo(); diff --git a/mach/proto/ncg/main.c b/mach/proto/ncg/main.c new file mode 100644 index 000000000..f8f7d0077 --- /dev/null +++ b/mach/proto/ncg/main.c @@ -0,0 +1,99 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "param.h" +#include "tables.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +char *progname; +extern char startupcode[]; +int maxply=1; +#ifndef NDEBUG +int Debug=0; +char *strtdebug=""; +#endif + +extern int endofprog; + +main(argc,argv) char **argv; { + register unsigned n; + extern unsigned cc1,cc2,cc3,cc4; + unsigned ggd(); + + progname = argv[0]; + while (--argc && **++argv == '-') { + switch(argv[0][1]) { +#ifndef NDEBUG + case 'd': + if ((Debug = argv[0][2]) != 0) { + Debug -= '0'; + if (argv[0][3] == '@') { + Debug = 0; + strtdebug = &argv[0][4]; + } + } else + Debug++; + break; +#endif +#ifdef TABLEDEBUG + case 'u': + case 'U': + initlset(argv[0]+1); + break; +#endif + case 'p': + maxply = atoi(argv[0]+2); + break; + case 'w': /* weight percentage for size */ + n=atoi(argv[0]+2); + cc1 *= n; + cc2 *= 50; + cc3 *= (100-n); + cc4 *= 50; + n=ggd(cc1,cc2); + cc1 /= n; + cc2 /= n; + n=ggd(cc3,cc4); + cc3 /= n; + cc4 /= n; + break; + default: + error("Unknown flag %c",argv[0][1]); + } + } + if (argc < 1 || argc > 2) + error("Usage: %s EMfile [ asfile ]",progname); + in_init(argv[0]); + out_init(argv[1]); + readcodebytes(); + itokcost(); + codegen(startupcode,maxply,TRUE,MAXINT,0); + error("Bombed out of codegen"); +} + +unsigned ggd(a,b) register unsigned a,b; { + register unsigned c; + + do { + c = a%b; a=b; b=c; + } while (c!=0); + return(a); +} diff --git a/mach/proto/ncg/move.c b/mach/proto/ncg/move.c new file mode 100644 index 000000000..4c2e7fa81 --- /dev/null +++ b/mach/proto/ncg/move.c @@ -0,0 +1,149 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +unsigned costcalc(); + +move(tp1,tp2,ply,toplevel,maxcost) token_p tp1,tp2; unsigned maxcost; { + register move_p mp; + register unsigned t; + register struct reginfo *rp; + tkdef_p tdp; + int i; + unsigned codegen(); + + if (eqtoken(tp1,tp2)) + return(0); + if (tp2->t_token == -1) { + if (tp1->t_token == -1) { + if (eqtoken(&machregs[tp1->t_att[0].ar].r_contents, + &machregs[tp2->t_att[0].ar].r_contents) && + machregs[tp1->t_att[0].ar].r_contents.t_token!=0) + return(0); + erasereg(tp2->t_att[0].ar); + machregs[tp2->t_att[0].ar].r_contents = + machregs[tp1->t_att[0].ar].r_contents ; + + } else { + if (eqtoken(&machregs[tp2->t_att[0].ar].r_contents,tp1)) + return(0); + erasereg(tp2->t_att[0].ar); + machregs[tp2->t_att[0].ar].r_contents = *tp1; + } + for (rp=machregs+1;rpr_contents.t_token == 0) + continue; + assert(rp->r_contents.t_token > 0); + tdp = &tokens[rp->r_contents.t_token]; + for (i=0;it_type[i] == EV_REG && + clash(rp->r_contents.t_att[i].ar,tp2->t_att[0].ar)) { + erasereg(rp-machregs); + break; + } + } + } else if (tp1->t_token == -1) { + if (eqtoken(tp2,&machregs[tp1->t_att[0].ar].r_contents)) + return(0); + machregs[tp1->t_att[0].ar].r_contents = *tp2; + } + /* + * If we arrive here the move must really be executed + */ + for (mp=moves;mp->m_set1>=0;mp++) { + if (!match(tp1,&machsets[mp->m_set1],mp->m_expr1)) + continue; + if (match(tp2,&machsets[mp->m_set2],mp->m_expr2)) + break; + /* + * Correct move rule is found + */ + } + assert(mp->m_set1>=0); + /* + * To get correct interpretation of things like %[1] + * in move code we stack tp2 and tp1. This little trick + * saves a lot of testing in other places. + */ + + fakestack[stackheight] = *tp2; + fakestack[stackheight+1] = *tp1; + stackheight += 2; + t = codegen(&coderules[mp->m_cindex],ply,toplevel,maxcost,0); + stackheight -= 2; + return(t); +} + +#define cocoreg machregs[0].r_contents + +setcc(tp) token_p tp; { + + cocoreg = *tp; +} + +test(tp,ply,toplevel,maxcost) token_p tp; unsigned maxcost; { + register test_p mp; + register unsigned t; + register struct reginfo *rp; + tkdef_p tdp; + int i; + unsigned codegen(); + + if (cocoreg.t_token!=0) { + if (eqtoken(tp,&cocoreg)) + return(0); + if (tp->t_token == -1) { + if (eqtoken(&machregs[tp->t_att[0].ar].r_contents,&cocoreg)) + return(0); + } + } + /* + * If we arrive here the test must really be executed + */ + for (mp=tests;mp->t_set>=0;mp++) { + if (match(tp,&machsets[mp->t_set],mp->t_expr)) + break; + /* + * Correct move rule is found + */ + } + assert(mp->t_set>=0); + /* + * To get correct interpretation of things like %[1] + * in test code we stack tp. This little trick + * saves a lot of testing in other places. + */ + + fakestack[stackheight] = *tp; + stackheight++; + t = codegen(&coderules[mp->t_cindex],ply,toplevel,maxcost,0); + stackheight--; + return(t); +} diff --git a/mach/proto/ncg/nextem.c b/mach/proto/ncg/nextem.c new file mode 100644 index 000000000..4b74b4400 --- /dev/null +++ b/mach/proto/ncg/nextem.c @@ -0,0 +1,133 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include +#include +#include "assert.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +#ifndef NDEBUG +#include +extern char em_mnem[][4]; +#endif + +byte *trypat(bp,len) register byte *bp; { + register patlen,i; + result_t result; + + getint(patlen,bp); + if (len == 3) { + if (patlen < 3) + return(0); + } else { + if (patlen != len) + return(0); + } + for(i=0;iemlines) { + nemlines -= emp-emlines; + for (i=0,ep=emlines;i=0;i--) { + index = pathash[hash[i]&BMASK]; + while (index != 0) { + bp = &pattern[index]; + if ( bp[PO_HASH] == (hash[i]>>8)) + if ((cp=trypat(&bp[PO_MATCH],i+1)) != 0) + return(cp); + index = (bp[PO_NEXT]&BMASK) | (bp[PO_NEXT+1]<<8); + } + } + return(0); +} diff --git a/mach/proto/ncg/param.h b/mach/proto/ncg/param.h new file mode 100644 index 000000000..073d0da7d --- /dev/null +++ b/mach/proto/ncg/param.h @@ -0,0 +1,20 @@ +/* $Header$ */ + +#define BMASK 0377 +#define BSHIFT 8 + +#define TRUE 1 +#define FALSE 0 + +#define MAXINT 32767 +#define INFINITY (MAXINT+100) + +#define MAXROM 3 + +/* + * Tunable constants + */ + +#define MAXEMLINES 20 +#define MAXFSTACK 20 +#define MAXTDBUG 32 diff --git a/mach/proto/ncg/reg.c b/mach/proto/ncg/reg.c new file mode 100644 index 000000000..fc3546c6c --- /dev/null +++ b/mach/proto/ncg/reg.c @@ -0,0 +1,175 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +chrefcount(regno,amount,tflag) { + register struct reginfo *rp; + register i; + + rp= &machregs[regno]; +#if MAXMEMBERS!=0 + if (rp->r_members[0]==0) { +#endif + rp->r_refcount += amount; + if (tflag) + rp->r_tcount += amount; + assert(rp->r_refcount >= 0); +#if MAXMEMBERS!=0 + } else + for (i=0;ir_members[i]!=0) + chrefcount(rp->r_members[i],amount,tflag); +#endif +} + +getrefcount(regno) { + register struct reginfo *rp; + register i,maxcount; + + rp= &machregs[regno]; +#if MAXMEMBERS!=0 + if (rp->r_members[0]==0) +#endif + return(rp->r_refcount); +#if MAXMEMBERS!=0 + else { + maxcount=0; + for (i=0;ir_members[i]!=0) + maxcount=max(maxcount,getrefcount(rp->r_members[i])); + return(maxcount); + } +#endif +} + +erasereg(regno) { + register struct reginfo *rp; + +#if MAXMEMBERS==0 + awayreg(regno); +#else + for (rp=machregs+1;rpr_clash[regno>>4]&(1<<(regno&017))) + awayreg(rp-machregs); +#endif +} + +awayreg(regno) { + register struct reginfo *rp; + register tkdef_p tdp; + register i; + + rp = &machregs[regno]; + rp->r_contents.t_token = 0; + for (i=0;ir_contents.t_att[i].aw = 0; + + /* Now erase recursively all registers containing + * something using this one + */ + for (rp=machregs;rpr_contents.t_token == -1) { + if (rp->r_contents.t_att[0].ar == regno) + erasereg(rp-machregs); + } else { + tdp= & tokens[rp->r_contents.t_token]; + for (i=0;it_type[i] == EV_REG && + rp->r_contents.t_att[i].ar == regno) { + erasereg(rp-machregs); + break; + } + } + } +} + +cleanregs() { + register struct reginfo *rp; + register i; + + for (rp=machregs;rpr_contents.t_token = 0; + for (i=0;ir_contents.t_att[i].aw = 0; + } +} + +#ifndef NDEBUG +inctcount(regno) { + register struct reginfo *rp; + register i; + + rp = &machregs[regno]; +#if MAXMEMBERS!=0 + if (rp->r_members[0] == 0) { +#endif + rp->r_tcount++; +#if MAXMEMBERS!=0 + } else { + for (i=0;ir_members[i] != 0) + inctcount(rp->r_members[i]); + } +#endif +} + +chkregs() { + register struct reginfo *rp; + register token_p tp; + register tkdef_p tdp; + int i; + + for (rp=machregs+1;rpr_tcount==0); + } + for (tp=fakestack;tpt_token == -1) + inctcount(tp->t_att[0].ar); + else { + tdp = &tokens[tp->t_token]; + for (i=0;it_type[i]==EV_REG) + inctcount(tp->t_att[i].ar); + } + } +#ifdef REGVARS +#include + for(i=reg_any;i<=reg_float;i++) { + int j; + for(j=0;jr_refcount==rp->r_tcount); + rp->r_tcount=0; + } +} +#endif diff --git a/mach/proto/ncg/regvar.c b/mach/proto/ncg/regvar.c new file mode 100644 index 000000000..9805d0ec6 --- /dev/null +++ b/mach/proto/ncg/regvar.c @@ -0,0 +1,151 @@ +#include "assert.h" +#include "param.h" +#include "tables.h" + +#ifdef REGVARS + +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "types.h" +#include +#include "data.h" +#include "regvar.h" +#include +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ +extern string myalloc(); +struct regvar *rvlist; + +struct regvar * +linkreg(of,sz,tp,sc) long of; { + register struct regvar *rvlp; + + rvlp= (struct regvar *) myalloc(sizeof *rvlp); + rvlp->rv_next = rvlist; + rvlist=rvlp; + rvlp->rv_off = of; + rvlp->rv_size = sz; + rvlp->rv_type = tp; + rvlp->rv_score = sc; + rvlp->rv_reg = 0; /* no register assigned yet */ + return(rvlp); +} + +tryreg(rvlp,typ) register struct regvar *rvlp; { + int score; + register i; + register struct regassigned *ra; + struct regvar *save; + + if (typ != reg_any && nregvar[typ]!=0) { + if (machregs[rvnumbers[typ][0]].r_size!=rvlp->rv_size) + score = -1; + else + score = regscore(rvlp->rv_off, + rvlp->rv_size, + rvlp->rv_type, + rvlp->rv_score, + typ); /* machine dependent */ + ra = regassigned[typ]; + if (score>ra[nregvar[typ]-1].ra_score) { + save = ra[nregvar[typ]-1].ra_rv; + for (i=nregvar[typ]-1;i>0 && ra[i-1].ra_scorerv_size) + score = -1; + else + score = regscore(rvlp->rv_off, + rvlp->rv_size, + rvlp->rv_type, + rvlp->rv_score, + reg_any); /* machine dependent */ + ra = regassigned[reg_any]; + if (score>ra[nregvar[reg_any]-1].ra_score) { + for (i=nregvar[reg_any]-1;i>0 && ra[i-1].ra_scorer_repr],(long)-TEM_WSIZE,rp->r_size); + } else if(regassigned[rvtyp][i].ra_score>0) { + rv=regassigned[rvtyp][i].ra_rv; + rv->rv_reg=rvnumbers[rvtyp][i]; + regsave(codestrings[machregs[rv->rv_reg].r_repr], + rv->rv_off,rv->rv_size); + } + } + f_regsave(); +} + +isregvar(off) long off; { + register struct regvar *rvlp; + + for(rvlp=rvlist;rvlp!=0;rvlp=rvlp->rv_next) + if(rvlp->rv_off == off) + return(rvlp->rv_reg); + return(-1); +} + +unlinkregs() { + register struct regvar *rvlp,*t; + register struct regassigned *ra; + int rvtyp,i; + + for(rvlp=rvlist;rvlp!=0;rvlp=t) { + t=rvlp->rv_next; + myfree(rvlp); + } + rvlist=0; + for (rvtyp=reg_any;rvtyp<=reg_float;rvtyp++) { + for(i=0;ira_rv = 0; + ra->ra_score = 0; + } + } +} + +#endif REGVARS + +/* nothing after this */ diff --git a/mach/proto/ncg/regvar.h b/mach/proto/ncg/regvar.h new file mode 100644 index 000000000..716a68f2b --- /dev/null +++ b/mach/proto/ncg/regvar.h @@ -0,0 +1,19 @@ +/* $Header$ */ + +struct regvar { + struct regvar *rv_next; + long rv_off; + int rv_size; + int rv_type; + int rv_score; + int rv_reg; +}; + +struct regassigned { + struct regvar *ra_rv; + int ra_score; +}; + +extern struct regvar *rvlist; +extern int nregvar[]; +extern struct regassigned *regassigned[]; diff --git a/mach/proto/ncg/result.h b/mach/proto/ncg/result.h new file mode 100644 index 000000000..15f9e8a22 --- /dev/null +++ b/mach/proto/ncg/result.h @@ -0,0 +1,19 @@ +/* $Header$ */ + +struct result { + int e_typ; /* EV_INT,EV_REG,EV_STR */ + union { + word e_con; + int e_reg; + addr_t e_addr; + } e_v; /* value */ +}; + +#define EV_UNDEF 0 +#define EV_INT 1 +#define EV_REG 2 +#define EV_ADDR 3 + +typedef struct result result_t; + +extern result_t compute(); diff --git a/mach/proto/ncg/salloc.c b/mach/proto/ncg/salloc.c new file mode 100644 index 000000000..45377d452 --- /dev/null +++ b/mach/proto/ncg/salloc.c @@ -0,0 +1,150 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +/* + * Package for string allocation and garbage collection. + * Call salloc(size) to get room for string. + * Every now and then call garbage_collect() from toplevel. + */ + +#define MAXSTAB 500 +#define THRESHOLD 200 + +char *stab[MAXSTAB]; +int nstab=0; +string malloc(); + +string myalloc(size) { + register string p; + + p = (string) malloc(size); + if (p==0) + fatal("Out of memory"); + return(p); +} + +myfree(p) string p; { + + free(p); +} + +popstr(nnstab) { + register i; + + for (i=nnstab;iem_soper,used); + for (tp= fakestack;tp<&fakestack[stackheight];tp++) { + if (tp->t_token== -1) + continue; + tdp = &tokens[tp->t_token]; + for (i=0;it_type[i] == EV_ADDR) + chkstr(tp->t_att[i].aa.ea_str,used); + } + for (rp= machregs+1; rpr_contents; + assert(tp->t_token != -1); + tdp= &tokens[tp->t_token]; + for (i=0;it_type[i] == EV_ADDR) + chkstr(tp->t_att[i].aa.ea_str,used); + } + for (i=0;ilow) { + middle= (low+high)>>1; + if (str==stab[middle]) { + used[middle]=1; + return; + } + if (str +#include "data.h" +#include "result.h" +#include "state.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +extern int nstab; /* salloc.c */ + +savestatus(sp) register state_p sp; { + + sp->st_sh = stackheight; + bmove((short *)fakestack,(short *)sp->st_fs,stackheight*sizeof(token_t)); + sp->st_na = nallreg; + bmove((short *)allreg,(short *)sp->st_ar,nallreg*sizeof(int)); + sp->st_ct = curtoken; + bmove((short *)dollar,(short *)sp->st_do,LONGESTPATTERN*sizeof(result_t)); + bmove((short *)machregs,(short *)sp->st_mr,NREGS*sizeof(struct reginfo)); + sp->st_ne = nemlines; + bmove((short *)emlines,(short *)sp->st_el,nemlines*sizeof(struct emline)); + sp->st_em = emp; + sp->st_se = saveemp; + sp->st_tl = tokpatlen; + sp->st_ns = nstab; +} + +restorestatus(sp) register state_p sp; { + + stackheight = sp->st_sh; + bmove((short *)sp->st_fs,(short *)fakestack,stackheight*sizeof(token_t)); + nallreg = sp->st_na; + bmove((short *)sp->st_ar,(short *)allreg,nallreg*sizeof(int)); + curtoken = sp->st_ct; + bmove((short *)sp->st_do,(short *)dollar,LONGESTPATTERN*sizeof(result_t)); + bmove((short *)sp->st_mr,(short *)machregs,NREGS*sizeof(struct reginfo)); + nemlines = sp->st_ne; + bmove((short *)sp->st_el,(short *)emlines,nemlines*sizeof(struct emline)); + emp = sp->st_em; + saveemp = sp->st_se; + tokpatlen = sp->st_tl; + popstr(sp->st_ns); +} + +bmove(from,to,nbytes) register short *from,*to; register nbytes; { + + if (nbytes<=0) + return; + assert(sizeof(short)==2 && (nbytes&1)==0); + nbytes>>=1; + do + *to++ = *from++; + while (--nbytes); +} diff --git a/mach/proto/ncg/state.h b/mach/proto/ncg/state.h new file mode 100644 index 000000000..45e2ba48f --- /dev/null +++ b/mach/proto/ncg/state.h @@ -0,0 +1,18 @@ +/* $Header$ */ + +typedef struct state { + struct state *st_next; /* for linked list */ + int st_sh; /* stackheight */ + token_t st_fs[MAXFSTACK]; /* fakestack */ + int st_na; /* nallreg */ + int st_ar[MAXALLREG]; /* allreg[] */ + token_p st_ct; /* curtoken */ + result_t st_do[LONGESTPATTERN]; /* dollar[] */ + struct reginfo st_mr[NREGS]; /* machregs[] */ + int st_ne; /* nemlines */ + struct emline st_el[MAXEMLINES]; /* emlines[] */ + struct emline *st_em; /* emp */ + struct emline *st_se; /* saveemp */ + int st_tl; /* tokpatlen */ + int st_ns; /* nstab */ +} state_t,*state_p; diff --git a/mach/proto/ncg/subr.c b/mach/proto/ncg/subr.c new file mode 100644 index 000000000..b04086d57 --- /dev/null +++ b/mach/proto/ncg/subr.c @@ -0,0 +1,617 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "assert.h" +#include +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" +#include "extern.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +string myalloc(); +unsigned codegen(); + +match(tp,tep,optexp) register token_p tp; register set_p tep; { + register bitno; + token_p ct; + result_t result; + + if (tp->t_token == -1) { /* register frame */ + bitno = tp->t_att[0].ar; + if (tep->set_val[bitno>>4]&(1<<(bitno&017))) + if (tep->set_val[0]&1 || getrefcount(tp->t_att[0].ar)<=1) + goto oklabel; + return(0); + } else { /* token frame */ + bitno = tp->t_token+NREGS; + if ((tep->set_val[bitno>>4]&(1<<(bitno&017)))==0) + return(0); + } + oklabel: + if (optexp==0) + return(1); + ct=curtoken; + curtoken=tp; + result=compute(&enodes[optexp]); + curtoken=ct; + return(result.e_v.e_con); +} + +instance(instno,token) register token_p token; { + register inst_p inp; + int i; + register token_p tp; + struct reginfo *rp; + int regno; + result_t result; + + if (instno==0) { + token->t_token = 0; + for(i=0;it_att[i].aw=0; + return; + } + inp= &tokeninstances[instno]; + switch(inp->in_which) { + default: + assert(FALSE); + case IN_COPY: + tp= &fakestack[stackheight-inp->in_info[0]]; + if (inp->in_info[1]==0) { + *token = *tp; + } else { + token->t_token= -1; +#if MAXMEMBERS!=0 + assert(tp->t_token == -1); + rp = &machregs[tp->t_att[0].ar]; + token->t_att[0].ar=rp->r_members[inp->in_info[1]-1]; +#else + assert(FALSE); +#endif + } + return; + case IN_MEMB: + tp= &fakestack[stackheight-inp->in_info[0]]; + assert(inp->in_info[1]!=0); + assert(tp->t_token>0); + token->t_token= -1; + assert(tokens[tp->t_token].t_type[inp->in_info[1]-1] == EV_REG); + token->t_att[0].ar=tp->t_att[inp->in_info[1]-1].ar; + return; + case IN_RIDENT: + token->t_token= -1; + token->t_att[0].ar= inp->in_info[0]; + return; + case IN_ALLOC: + token->t_token= -1; + regno=allreg[inp->in_info[0]]; +#if MAXMEMBERS!=0 + if (inp->in_info[1]) + regno=machregs[regno].r_members[inp->in_info[1]-1]; +#endif + token->t_att[0].ar = regno; + return; +#ifdef REGVARS + case IN_S_DESCR: + case IN_D_DESCR: + result=compute(&enodes[inp->in_info[1]]); + assert(result.e_typ==EV_INT); + if ((regno=isregvar(result.e_v.e_con)) > 0) { + token->t_token = -1; + token->t_att[0].ar = regno; + for(i=1;it_att[i].aw = 0; + return; + } + /* fall through */ +#endif + case IN_DESCR: + token->t_token=inp->in_info[0]; + for (i=0;iin_info[i+1]==0) { + assert(tokens[token->t_token].t_type[i]==0); + token->t_att[i].aw=0; + } else { + result=compute(&enodes[inp->in_info[i+1]]); + assert(tokens[token->t_token].t_type[i]==result.e_typ); + if (result.e_typ==EV_INT) + token->t_att[i].aw=result.e_v.e_con; + else if (result.e_typ==EV_ADDR) + token->t_att[i].aa= result.e_v.e_addr; + else + token->t_att[i].ar=result.e_v.e_reg; + } + return; + } +} + +cinstance(instno,token,tp,regno) register token_p token,tp; { + register inst_p inp; + int i; + struct reginfo *rp; + result_t result; + int sh; /* saved stackheight */ + + assert(instno!=0); + inp= &tokeninstances[instno]; + switch(inp->in_which) { + default: + assert(FALSE); + case IN_COPY: + assert(inp->in_info[0] == 1); + if (inp->in_info[1]==0) { + *token = *tp; + } else { + token->t_token= -1; +#if MAXMEMBERS!=0 + assert(tp->t_token == -1); + rp = &machregs[tp->t_att[0].ar]; + token->t_att[0].ar=rp->r_members[inp->in_info[1]-1]; +#else + assert(FALSE); +#endif + } + return; + case IN_MEMB: + assert(inp->in_info[0] == 1); + token->t_token= -1; + assert(tp->t_token>0); + assert(tokens[tp->t_token].t_type[inp->in_info[1]-1] == EV_REG); + token->t_att[0].ar=tp->t_att[inp->in_info[1]-1].ar; + return; + case IN_RIDENT: + token->t_token= -1; + token->t_att[0].ar= inp->in_info[0]; + return; + case IN_ALLOC: + token->t_token= -1; + assert(inp->in_info[0]==0); +#if MAXMEMBERS!=0 + if (inp->in_info[1]) + regno=machregs[regno].r_members[inp->in_info[1]-1]; +#endif + token->t_att[0].ar = regno; + return; +#ifdef REGVARS + case IN_S_DESCR: + case IN_D_DESCR: + result=compute(&enodes[inp->in_info[1]]); + assert(result.e_typ==EV_INT); + if ((regno=isregvar(result.e_v.e_con)) > 0) { + token->t_token = -1; + token->t_att[0].ar = regno; + for(i=1;it_att[i].aw = 0; + return; + } + /* fall through */ +#endif + case IN_DESCR: + sh = stackheight; + stackheight = tp - fakestack + 1; + token->t_token=inp->in_info[0]; + for (i=0;iin_info[i+1]==0) { + assert(tokens[token->t_token].t_type[i]==0); + token->t_att[i].aw=0; + } else { + result=compute(&enodes[inp->in_info[i+1]]); + assert(tokens[token->t_token].t_type[i]==result.e_typ); + if (result.e_typ==EV_INT) + token->t_att[i].aw=result.e_v.e_con; + else if (result.e_typ==EV_ADDR) + token->t_att[i].aa= result.e_v.e_addr; + else + token->t_att[i].ar=result.e_v.e_reg; + } + stackheight = sh; + return; + } +} + +eqtoken(tp1,tp2) token_p tp1,tp2; { + register i; + register tkdef_p tdp; + + if (tp1->t_token!=tp2->t_token) + return(0); + if (tp1->t_token==0) + return(1); + if (tp1->t_token==-1) { + if (tp1->t_att[0].ar!=tp2->t_att[0].ar) + return(0); + return(1); + } + tdp = &tokens[tp1->t_token]; + for (i=0;it_type[i]) { + default: + return(1); + case EV_INT: + if (tp1->t_att[i].aw != tp2->t_att[i].aw) + return(0); + break; + case EV_REG: + if (tp1->t_att[i].ar != tp2->t_att[i].ar) + return(0); + break; + case EV_ADDR: + if (strcmp(tp1->t_att[i].aa.ea_str, tp2->t_att[i].aa.ea_str)) + return(0); + if (tp1->t_att[i].aa.ea_off!=tp2->t_att[i].aa.ea_off) + return(0); + break; + } + return(1); +} + +distance(cindex) { + register char *bp; + register i; + register token_p tp; + int tokexp,tpl; + int expsize,toksize,exact; + int xsekt=0; + + bp = &coderules[cindex]; +#ifndef NDEBUG + if (*bp==DO_DLINE) { + ++bp; + getint(i,bp); + } +#endif + switch( (*bp)&037 ) { + default: + return(stackheight==0 ? 0 : 100); + case DO_MATCH: + break; + case DO_XXMATCH: + xsekt++; + case DO_XMATCH: + xsekt++; + break; + } + tpl= ((*bp++)>>5)&07; + if (stackheight < tpl) { + if (xsekt) + return(MAXINT); + tpl = stackheight; + } else + if (stackheight != tpl && xsekt==2) + return(MAXINT); + exact=0; + tp= &fakestack[stackheight-1]; + for (i=0;itoksize) + return(100); + if (expsizet_token==-1) + return(machregs[tp->t_att[0].ar].r_size); + return(tokens[tp->t_token].t_size); +} + +#ifdef MAXSPLIT +instsize(tinstno,tp) token_p tp; { + inst_p inp; + struct reginfo *rp; + + inp = &tokeninstances[tinstno]; + switch(inp->in_which) { + default: + assert(FALSE); + case IN_COPY: + assert(inp->in_info[0]==1); +#if MAXMEMBERS!=0 + if (inp->in_info[1]==0) +#endif + return(tsize(tp)); +#if MAXMEMBERS!=0 + else { + assert(tp->t_token == -1); + rp = &machregs[tp->t_att[0].ar]; + return(machregs[rp->r_members[inp->in_info[1]-1]].r_size); + } +#endif + case IN_RIDENT: + return(machregs[inp->in_info[0]].r_size); + case IN_ALLOC: + assert(FALSE); /* cannot occur in splitting coercion */ + case IN_DESCR: + case IN_S_DESCR: + case IN_D_DESCR: + return(tokens[inp->in_info[0]].t_size); + } +} +#endif MAXSPLIT + +tref(tp,amount) register token_p tp; { + register i; + register tkdef_p tdp; + + if (tp->t_token==-1) + chrefcount(tp->t_att[0].ar,amount,FALSE); + else { + tdp= &tokens[tp->t_token]; + for(i=0;it_type[i]==EV_REG) + chrefcount(tp->t_att[i].ar,amount,FALSE); + } +} + +#define MAXSAVE 10 + +#ifdef MAXSPLIT +split(tp,ip,ply,toplevel) token_p tp; register int *ip; { + register c2_p cp; + token_t savestack[MAXSAVE]; + int ok; + register i; + int diff; + token_p stp; + int tpl; + + for (cp=c2coercs;cp->c2_texpno>=0; cp++) { + if (!match(tp,&machsets[cp->c2_texpno],0)) + continue; + ok=1; + for (i=0; ok && ic2_nsplit;i++) { + if (ip[i]==0) + goto found; + if (instsize(cp->c2_repl[i],tp) != ssize(ip[i])) + ok=0; + } + goto found; + } + return(0); +found: + assert(stackheight+cp->c2_nsplit-1c2_codep],ply,toplevel,MAXINT,0); + tokpatlen = tpl; + for (i=0;ic2_nsplit); +} +#endif MAXSPLIT + +unsigned docoerc(tp,cp,ply,toplevel,forced) token_p tp; register c3_p cp; { + token_t savestack[MAXSAVE]; + token_p stp; + register int i,diff; + unsigned cost; + int tpl; /* saved tokpatlen */ + + stp = &fakestack[stackheight-1]; + diff = stp -tp; + assert(diff<=MAXSAVE); +#ifndef NDEBUG + if (diff!=0 && Debug>1) + fprintf(stderr,"Saving %d items from fakestack\n",diff); +#endif + for (i=1;i<=diff;i++) + savestack[i-1] = tp[i]; + stackheight -= diff; + tpl = tokpatlen; + tokpatlen = 1; + cost = codegen(&coderules[cp->c3_codep],ply,toplevel,MAXINT,forced); + tokpatlen = tpl; +#ifndef NDEBUG + if (diff!=0 && Debug>1) + fprintf(stderr,"Restoring %d items to fakestack(%d)\n",diff,stackheight); +#endif + for (i=0;ic1_texpno>=0; cp++) { + if (match(tp,&machsets[cp->c1_texpno],cp->c1_expr)) { + if (cp->c1_prop>=0) { + for (rpp=reglist[cp->c1_prop]; + (rp = *rpp)!=0 && + getrefcount(rp-machregs)!=0; + rpp++) + ; + if (rp==0) + continue; + /* look for other possibility */ + } + stp = &fakestack[stackheight-1]; + diff = stp -tp; + assert(diff<=MAXFSTACK); + for (i=1;i<=diff;i++) + savestack[i-1] = tp[i]; + stackheight -= diff; + tpl = tokpatlen; + tokpatlen = 1; + nareg = nallreg; + for (i=0;ic1_prop>=0) { + nallreg=1; allreg[0] = rp-machregs; + chrefcount(allreg[0],1,FALSE); + } else + nallreg=0; + totalcost+= codegen(&coderules[cp->c1_codep],ply,toplevel,MAXINT,0); + tokpatlen = tpl; + for (i=0;ic3_texpno>=0; cp++) { + if (tp!=(token_p) 0) { + if (cp->c3_texpno==0) + continue; + if (!match(tp,&machsets[cp->c3_texpno],cp->c3_expr)) + continue; + } else { + if (cp->c3_texpno!=0) + continue; + } + if (cp->c3_prop==0) { /* no reg needed */ + cinstance(cp->c3_repl,&rtoken,tp,0); + if (match(&rtoken,tep,0)) + return(cp); + } else { + curreglist = (rl_p) myalloc(sizeof (rl_t)); + curreglist->rl_n = 0; + for (rpp=reglist[cp->c3_prop];*rpp;rpp++) { + i = *rpp - machregs; + cinstance(cp->c3_repl,&rtoken,tp,i); + if (match(&rtoken,tep,0)) + curreglist->rl_list[curreglist->rl_n++] = i; + } + if (curreglist->rl_n != 0) + return(cp); + myfree(curreglist); + } + } + return(0); /* nothing found */ +} + +itokcost() { + register tkdef_p tdp; + + for(tdp=tokens+1;tdp->t_size!=0;tdp++) + tdp->t_cost.ct_space = costcalc(tdp->t_cost); +} + +error(s,a1,a2,a3,a4,a5,a6,a7,a8) char *s; { + + fatal(s,a1,a2,a3,a4,a5,a6,a7,a8); +} + +fatal(s,a1,a2,a3,a4,a5,a6,a7,a8) char *s; { + + fprintf(stderr,"Error: "); + fprintf(stderr,s,a1,a2,a3,a4,a5,a6,a7,a8); + fprintf(stderr,"\n"); +#ifdef TABLEDEBUG + ruletrace(); +#endif + out_finish(); + abort(); + exit(-1); +} + +#ifdef TABLEDEBUG + +ruletrace() { + register i; + extern int tablelines[MAXTDBUG]; + extern int ntableline; + extern char *tablename; + + fprintf(stderr,"Last code rules used\n"); + i=ntableline-1; + while(i!=ntableline) { + if (i<0) + i += MAXTDBUG; + if (tablelines[i]!=0) + fprintf(stderr,"\%d: \"%s\", line %d\n",i,tablename,tablelines[i]); + i--; + } +} +#endif + +#ifndef NDEBUG +badassertion(asstr,file,line) char *asstr, *file; { + + fatal("\"%s\", line %d:Assertion \"%s\" failed",file,line,asstr); +} +#endif + +max(a,b) { + + return(a>b ? a : b); +} diff --git a/mach/proto/ncg/types.h b/mach/proto/ncg/types.h new file mode 100644 index 000000000..ee666132f --- /dev/null +++ b/mach/proto/ncg/types.h @@ -0,0 +1,27 @@ +/* $Header$ */ + +#ifndef TEM_WSIZE +TEM_WSIZE should be defined at this point +#endif +#ifndef TEM_PSIZE +TEM_PSIZE should be defined at this point +#endif +#if TEM_WSIZE>4 || TEM_PSIZE>4 +Implementation will not be correct unless a long integer +has more then 4 bytes of precision. +#endif + +typedef char byte; +typedef char * string; + +#if TEM_WSIZE>2 || TEM_PSIZE>2 +#define full long +#else +#define full int +#endif + +#if TEM_WSIZE>2 +#define word long +#else +#define word int +#endif diff --git a/mach/proto/ncg/var.c b/mach/proto/ncg/var.c new file mode 100644 index 000000000..6ba1d460b --- /dev/null +++ b/mach/proto/ncg/var.c @@ -0,0 +1,41 @@ +#ifndef NORCSID +static char rcsid[] = "$Header$"; +#endif + +#include "param.h" +#include "tables.h" +#include "types.h" +#include +#include "data.h" +#include "result.h" + +/* + * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands. + * + * This product is part of the Amsterdam Compiler Kit. + * + * Permission to use, sell, duplicate or disclose this software must be + * obtained in writing. Requests for such permissions may be sent to + * + * Dr. Andrew S. Tanenbaum + * Wiskundig Seminarium + * Vrije Universiteit + * Postbox 7161 + * 1007 MC Amsterdam + * The Netherlands + * + * Author: Hans van Staveren + */ + +int stackheight = 0; +token_t fakestack[MAXFSTACK]; +int nallreg = 0; +int allreg[MAXALLREG]; +token_p curtoken = (token_p) 0; +result_t dollar[LONGESTPATTERN]; +int nemlines =0; +struct emline emlines[MAXEMLINES]; +struct emline *emp=emlines; +struct emline *saveemp; +int tokpatlen; +rl_p curreglist; -- 2.34.1