diff options
Diffstat (limited to 'usr.bin/pcc/mip')
| -rw-r--r-- | usr.bin/pcc/mip/common.c | 631 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/manifest.h | 316 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/match.c | 995 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/mkext.c | 318 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/node.h | 194 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/optim2.c | 882 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/pass2.h | 418 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/protos.h | 83 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/reader.c | 1098 | ||||
| -rw-r--r-- | usr.bin/pcc/mip/regs.c | 2244 |
10 files changed, 7179 insertions, 0 deletions
diff --git a/usr.bin/pcc/mip/common.c b/usr.bin/pcc/mip/common.c new file mode 100644 index 00000000000..e5d49df9282 --- /dev/null +++ b/usr.bin/pcc/mip/common.c @@ -0,0 +1,631 @@ +/* $Id: common.c,v 1.1 2007/09/15 18:12:35 otto Exp $ */ +/* + * Copyright (c) 2003 Anders Magnusson (ragge@ludd.luth.se). + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code and documentation must retain the above + * copyright notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditionsand the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed or owned by Caldera + * International, Inc. + * Neither the name of Caldera International, Inc. nor the names of other + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA + * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE + * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <stdarg.h> +#include <stdlib.h> +#include <stdio.h> +#include <string.h> + +#include "pass2.h" + +# ifndef EXIT +# define EXIT exit +# endif + +int nerrors = 0; /* number of errors */ +char *ftitle; +int lineno; + +#ifndef WHERE +#define WHERE(ch) fprintf(stderr, "%s, line %d: ", ftitle, lineno); +#endif + +/* + * nonfatal error message + * the routine where is different for pass 1 and pass 2; + * it tells where the error took place + */ +void +uerror(char *s, ...) +{ + va_list ap; + + va_start(ap, s); + ++nerrors; + WHERE('u'); + vfprintf(stderr, s, ap); + fprintf(stderr, "\n"); + if (nerrors > 30) + cerror("too many errors"); + va_end(ap); +} + +/* + * compiler error: die + */ +void +cerror(char *s, ...) +{ + va_list ap; + + va_start(ap, s); + WHERE('c'); + + /* give the compiler the benefit of the doubt */ + if (nerrors && nerrors <= 30) { + fprintf(stderr, + "cannot recover from earlier errors: goodbye!\n"); + } else { + fprintf(stderr, "compiler error: "); + vfprintf(stderr, s, ap); + fprintf(stderr, "\n"); + } + va_end(ap); + EXIT(1); +} + +/* + * warning + */ +void +werror(char *s, ...) +{ + va_list ap; + + va_start(ap, s); + WHERE('w'); + fprintf(stderr, "warning: "); + vfprintf(stderr, s, ap); + fprintf(stderr, "\n"); +} + +#ifndef MKEXT +static NODE *freelink; +static int usednodes; + +NODE * +talloc() +{ + extern int inlnodecnt, recovernodes; + register NODE *p; + + usednodes++; + + if (recovernodes) + inlnodecnt++; + if (freelink != NULL) { + p = freelink; + freelink = p->next; + if (p->n_op != FREE) + cerror("node not FREE: %p", p); + if (nflag) + printf("alloc node %p from freelist\n", p); + return p; + } + + p = permalloc(sizeof(NODE)); + p->n_op = FREE; + if (nflag) + printf("alloc node %p from memory\n", p); + return p; +} + +/* + * make a fresh copy of p + */ +NODE * +tcopy(NODE *p) +{ + NODE *q; + + q = talloc(); + *q = *p; + + switch (optype(q->n_op)) { + case BITYPE: + q->n_right = tcopy(p->n_right); + case UTYPE: + q->n_left = tcopy(p->n_left); + } + + return(q); +} + + +/* + * ensure that all nodes have been freed + */ +void +tcheck() +{ + extern int inlnodecnt; + + if (nerrors) + return; + + if ((usednodes - inlnodecnt) != 0) + cerror("usednodes == %d, inlnodecnt %d", usednodes, inlnodecnt); +} + +/* + * free the tree p + */ +void +tfree(NODE *p) +{ + if (p->n_op != FREE) + walkf(p, (void (*)(NODE *))nfree); +} + +/* + * Free a node, and return its left descendant. + * It is up to the caller to know whether the return value is usable. + */ +NODE * +nfree(NODE *p) +{ + extern int inlnodecnt, recovernodes; + NODE *l; +#ifdef PCC_DEBUG_NODES + NODE *q; +#endif + + if (p == NULL) + cerror("freeing blank node!"); + + l = p->n_left; + if (p->n_op == FREE) + cerror("freeing FREE node", p); +#ifdef PCC_DEBUG_NODES + q = freelink; + while (q != NULL) { + if (q == p) + cerror("freeing free node %p", p); + q = q->next; + } +#endif + + if (nflag) + printf("freeing node %p\n", p); + p->n_op = FREE; + p->next = freelink; + freelink = p; + usednodes--; + if (recovernodes) + inlnodecnt--; + return l; +} +#endif + +#ifdef MKEXT +#define coptype(o) (dope[o]&TYFLG) +#else +int cdope(int); +#define coptype(o) (cdope(o)&TYFLG) +#endif + +void +fwalk(NODE *t, void (*f)(NODE *, int, int *, int *), int down) +{ + + int down1, down2; + + more: + down1 = down2 = 0; + + (*f)(t, down, &down1, &down2); + + switch (coptype( t->n_op )) { + + case BITYPE: + fwalk( t->n_left, f, down1 ); + t = t->n_right; + down = down2; + goto more; + + case UTYPE: + t = t->n_left; + down = down1; + goto more; + + } +} + +void +walkf(NODE *t, void (*f)(NODE *)) +{ + int opty; + + opty = coptype(t->n_op); + + if (opty != LTYPE) + walkf( t->n_left, f ); + if (opty == BITYPE) + walkf( t->n_right, f ); + (*f)(t); +} + +int dope[DSIZE]; +char *opst[DSIZE]; + +struct dopest { + int dopeop; + char opst[8]; + int dopeval; +} indope[] = { + { NAME, "NAME", LTYPE, }, + { REG, "REG", LTYPE, }, + { OREG, "OREG", LTYPE, }, + { TEMP, "TEMP", LTYPE, }, + { MOVE, "MOVE", UTYPE, }, + { ICON, "ICON", LTYPE, }, + { FCON, "FCON", LTYPE, }, + { CCODES, "CCODES", LTYPE, }, + { UMINUS, "U-", UTYPE, }, + { UMUL, "U*", UTYPE, }, + { FUNARG, "FUNARG", UTYPE, }, + { UCALL, "UCALL", UTYPE|CALLFLG, }, + { UFORTCALL, "UFCALL", UTYPE|CALLFLG, }, + { COMPL, "~", UTYPE, }, + { FORCE, "FORCE", UTYPE, }, +/* { INIT, "INIT", UTYPE, }, */ + { SCONV, "SCONV", UTYPE, }, + { PCONV, "PCONV", UTYPE, }, + { PLUS, "+", BITYPE|FLOFLG|SIMPFLG|COMMFLG, }, + { MINUS, "-", BITYPE|FLOFLG|SIMPFLG, }, + { MUL, "*", BITYPE|FLOFLG|MULFLG, }, + { AND, "&", BITYPE|SIMPFLG|COMMFLG, }, + { CM, ",", BITYPE, }, + { ASSIGN, "=", BITYPE|ASGFLG, }, + { DIV, "/", BITYPE|FLOFLG|MULFLG|DIVFLG, }, + { MOD, "%", BITYPE|DIVFLG, }, + { LS, "<<", BITYPE|SHFFLG, }, + { RS, ">>", BITYPE|SHFFLG, }, + { OR, "|", BITYPE|COMMFLG|SIMPFLG, }, + { ER, "^", BITYPE|COMMFLG|SIMPFLG, }, + { STREF, "->", BITYPE, }, + { CALL, "CALL", BITYPE|CALLFLG, }, + { FORTCALL, "FCALL", BITYPE|CALLFLG, }, + { EQ, "==", BITYPE|LOGFLG, }, + { NE, "!=", BITYPE|LOGFLG, }, + { LE, "<=", BITYPE|LOGFLG, }, + { LT, "<", BITYPE|LOGFLG, }, + { GE, ">=", BITYPE|LOGFLG, }, + { GT, ">", BITYPE|LOGFLG, }, + { UGT, "UGT", BITYPE|LOGFLG, }, + { UGE, "UGE", BITYPE|LOGFLG, }, + { ULT, "ULT", BITYPE|LOGFLG, }, + { ULE, "ULE", BITYPE|LOGFLG, }, + { CBRANCH, "CBRANCH", BITYPE, }, + { FLD, "FLD", UTYPE, }, + { PMCONV, "PMCONV", BITYPE, }, + { PVCONV, "PVCONV", BITYPE, }, + { RETURN, "RETURN", BITYPE|ASGFLG|ASGOPFLG, }, + { GOTO, "GOTO", UTYPE, }, + { STASG, "STASG", BITYPE|ASGFLG, }, + { STARG, "STARG", UTYPE, }, + { STCALL, "STCALL", BITYPE|CALLFLG, }, + { USTCALL, "USTCALL", UTYPE|CALLFLG, }, + { ADDROF, "U&", UTYPE, }, + + { -1, "", 0 }, +}; + +void +mkdope() +{ + struct dopest *q; + + for( q = indope; q->dopeop >= 0; ++q ){ + dope[q->dopeop] = q->dopeval; + opst[q->dopeop] = q->opst; + } +} + +/* + * output a nice description of the type of t + */ +void +tprint(FILE *fp, TWORD t, TWORD q) +{ + static char * tnames[] = { + "undef", + "farg", + "char", + "uchar", + "short", + "ushort", + "int", + "unsigned", + "long", + "ulong", + "longlong", + "ulonglong", + "float", + "double", + "ldouble", + "strty", + "unionty", + "enumty", + "moety", + "void", + "signed", /* pass1 */ + "bool", /* pass1 */ + "?", "?" + }; + + for(;; t = DECREF(t), q = DECREF(q)) { + if (ISCON(q)) + fputc('C', fp); + if (ISVOL(q)) + fputc('V', fp); + + if (ISPTR(t)) + fprintf(fp, "PTR "); + else if (ISFTN(t)) + fprintf(fp, "FTN "); + else if (ISARY(t)) + fprintf(fp, "ARY "); + else { + fprintf(fp, "%s%s%s", ISCON(q << TSHIFT) ? "const " : "", + ISVOL(q << TSHIFT) ? "volatile " : "", tnames[t]); + return; + } + } +} + +int crslab = 10; +/* + * Return a number for internal labels. + */ +int +getlab() +{ + return crslab++; +} + +/* + * Memory allocation routines. + * Memory are allocated from the system in MEMCHUNKSZ blocks. + * permalloc() returns a bunch of memory that is never freed. + * Memory allocated through tmpalloc() will be released the + * next time a function is ended (via tmpfree()). + */ + +#define MEMCHUNKSZ 8192 /* 8k per allocation */ +struct b { + char a1; + union { + long long l; + long double d; + } a2; +}; + +#define ALIGNMENT ((int)&((struct b *)0)->a2) +#define ROUNDUP(x) ((x) + (sizeof(ALIGNMENT)-1)) & ~(sizeof(ALIGNMENT)-1) + +static char *allocpole; +static int allocleft; +static char *tmppole; +static int tmpleft; +int permallocsize, tmpallocsize, lostmem; + +void * +permalloc(int size) +{ + void *rv; + +//printf("permalloc: allocpole %p allocleft %d size %d ", allocpole, allocleft, size); + if (size > MEMCHUNKSZ) + cerror("permalloc"); + if (size <= 0) + cerror("permalloc2"); + if (allocleft < size) { + /* looses unused bytes */ + lostmem += allocleft; +//fprintf(stderr, "allocating perm\n"); + if ((allocpole = malloc(MEMCHUNKSZ)) == NULL) + cerror("permalloc: out of memory"); + allocleft = MEMCHUNKSZ; + } + size = ROUNDUP(size); + rv = &allocpole[MEMCHUNKSZ-allocleft]; +//printf("rv %p\n", rv); + allocleft -= size; + permallocsize += size; + return rv; +} + +static char *tmplink; + +void * +tmpcalloc(int size) +{ + void *rv; + + rv = tmpalloc(size); + memset(rv, 0, size); + return rv; +} + +#define TMPOLE &tmppole[MEMCHUNKSZ-tmpleft] +void * +tmpalloc(int size) +{ + void *rv; + + if (size > MEMCHUNKSZ) { + return malloc(size); + // cerror("tmpalloc %d", size); + } + if (size <= 0) + cerror("tmpalloc2"); +//printf("tmpalloc: tmppole %p tmpleft %d size %d ", tmppole, tmpleft, size); + size = ROUNDUP(size); + if (tmpleft < size) { + if ((tmppole = malloc(MEMCHUNKSZ)) == NULL) + cerror("tmpalloc: out of memory"); +//fprintf(stderr, "allocating tmp\n"); + tmpleft = MEMCHUNKSZ - (ROUNDUP(sizeof(char *))); + *(char **)tmppole = tmplink; + tmplink = tmppole; + } + rv = TMPOLE; +//printf("rv %p\n", rv); + tmpleft -= size; + tmpallocsize += size; + return rv; +} + +#if 0 +/* + * Print and pack strings on heap. + */ +char *tmpsprintf(char *fmt, ...); +char * +tmpsprintf(char *fmt, ...) +{ + va_list ap; + int len; + char *tmp; + + tmp = TMPOLE; + va_start(ap, fmt); + if ((len = vsnprintf(tmp, tmpleft, fmt, ap)) >= tmpleft) { + (void)tmpalloc(tmpleft); /* ugly */ + tmp = TMPOLE; + if ((len = vsnprintf(tmp, tmpleft, fmt, ap)) >= tmpleft) + cerror("bad tmpsprintf len"); + } + va_end(ap); + tmpleft += len; + return tmp; +} +#endif + +/* + * Print and pack vararg string on heap. + */ +char *tmpvsprintf(char *fmt, va_list ap); +char * +tmpvsprintf(char *fmt, va_list ap) +{ + int len; + char *tmp; + + if (tmpleft == 0) + (void)tmpalloc(1); /* XXX ugly */ + tmp = TMPOLE; + if ((len = vsnprintf(tmp, tmpleft, fmt, ap)) >= tmpleft) { + (void)tmpalloc(tmpleft+1); /* ugly */ + tmp = TMPOLE; + if ((len = vsnprintf(tmp, tmpleft, fmt, ap)) >= tmpleft) + cerror("bad tmpsprintf len"); + } + tmpleft -= len+1; + return tmp; +} + +void +tmpfree() +{ + char *f, *of; + + f = tmplink; + if (f == NULL) + return; + if (*(char **)f == NULL) { + tmpleft = MEMCHUNKSZ - (ROUNDUP(sizeof(char *))); + return; + } + while (f != NULL) { + of = f; + f = *(char **)f; + free(of); + } + tmplink = tmppole = NULL; + tmpleft = 0; +//fprintf(stderr, "freeing tmp\n"); + /* XXX - nothing right now */ +} + +/* + * Allocate space on the permanent stack for a string of length len+1 + * and copy it there. + * Return the new address. + */ +char * +newstring(char *s, int len) +{ + char *u, *c; + + len++; + if (allocleft < len) { + u = c = permalloc(len); + } else { + u = c = &allocpole[MEMCHUNKSZ-allocleft]; + allocleft -= ROUNDUP(len+1); + } + while (len--) + *c++ = *s++; + return u; +} diff --git a/usr.bin/pcc/mip/manifest.h b/usr.bin/pcc/mip/manifest.h new file mode 100644 index 00000000000..dd4cf0ecafb --- /dev/null +++ b/usr.bin/pcc/mip/manifest.h @@ -0,0 +1,316 @@ +/* $Id: manifest.h,v 1.1 2007/09/15 18:12:35 otto Exp $ */ +/* + * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code and documentation must retain the above + * copyright notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditionsand the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed or owned by Caldera + * International, Inc. + * Neither the name of Caldera International, Inc. nor the names of other + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA + * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE + * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef MANIFEST +#define MANIFEST + +#include <stdio.h> +#include "../config.h" +#include "macdefs.h" +#include "node.h" + +/* + * Node types + */ +#define LTYPE 02 /* leaf */ +#define UTYPE 04 /* unary */ +#define BITYPE 010 /* binary */ + +/* + * DSIZE is the size of the dope array + */ +#define DSIZE (MAXOP+1) + +/* + * Type names, used in symbol table building. + * The order of the integer types are important. + * Signed types must have bit 0 unset, unsigned types set (used below). + */ +#define UNDEF 0 /* free symbol table entry */ +#define FARG 1 /* function argument */ +#define CHAR 2 +#define UCHAR 3 +#define SHORT 4 +#define USHORT 5 +#define INT 6 +#define UNSIGNED 7 +#define LONG 8 +#define ULONG 9 +#define LONGLONG 10 +#define ULONGLONG 11 +#define FLOAT 12 +#define DOUBLE 13 +#define LDOUBLE 14 +#define STRTY 15 +#define UNIONTY 16 +#define ENUMTY 17 +#define MOETY 18 /* member of enum */ +#define VOID 19 + +#define MAXTYPES 19 /* highest type+1 to be used by lang code */ +/* + * Various flags + */ +#define NOLAB (-1) + +/* + * Type modifiers. + */ +#define PTR 0x20 +#define FTN 0x40 +#define ARY 0x60 +#define CON 0x20 +#define VOL 0x40 + +/* + * Type packing constants + */ +#define TMASK 0x060 +#define TMASK1 0x180 +#define TMASK2 0x1e0 +#define BTMASK 0x1f +#define BTSHIFT 5 +#define TSHIFT 2 + +/* + * Macros + */ +#define MODTYPE(x,y) x = ((x)&(~BTMASK))|(y) /* set basic type of x to y */ +#define BTYPE(x) ((x)&BTMASK) /* basic type of x */ +#define ISLONGLONG(x) ((x) == LONGLONG || (x) == ULONGLONG) +#define ISUNSIGNED(x) (((x) <= ULONGLONG) && (((x) & 1) == (UNSIGNED & 1))) +#define UNSIGNABLE(x) (((x)<=ULONGLONG&&(x)>=CHAR) && !ISUNSIGNED(x)) +#define ENUNSIGN(x) ((x)|1) +#define DEUNSIGN(x) ((x)&~1) +#define ISPTR(x) (((x)&TMASK)==PTR) +#define ISFTN(x) (((x)&TMASK)==FTN) /* is x a function type? */ +#define ISARY(x) (((x)&TMASK)==ARY) /* is x an array type? */ +#define ISCON(x) (((x)&CON)==CON) /* is x const? */ +#define ISVOL(x) (((x)&VOL)==VOL) /* is x volatile? */ +#define INCREF(x) ((((x)&~BTMASK)<<TSHIFT)|PTR|((x)&BTMASK)) +#define INCQAL(x) ((((x)&~BTMASK)<<TSHIFT)|((x)&BTMASK)) +#define DECREF(x) ((((x)>>TSHIFT)&~BTMASK)|((x)&BTMASK)) +#define DECQAL(x) ((((x)>>TSHIFT)&~BTMASK)|((x)&BTMASK)) +#define SETOFF(x,y) { if ((x)%(y) != 0) (x) = (((x)/(y) + 1) * (y)); } + /* advance x to a multiple of y */ +#define NOFIT(x,y,z) (((x)%(z) + (y)) > (z)) + /* can y bits be added to x without overflowing z */ + +#ifndef SPECIAL_INTEGERS +#define ASGLVAL(lval, val) +#endif + +/* + * Pack and unpack field descriptors (size and offset) + */ +#define PKFIELD(s,o) (((o)<<6)| (s)) +#define UPKFSZ(v) ((v)&077) +#define UPKFOFF(v) ((v)>>6) + +/* + * Operator information + */ +#define TYFLG 016 +#define ASGFLG 01 +#define LOGFLG 020 + +#define SIMPFLG 040 +#define COMMFLG 0100 +#define DIVFLG 0200 +#define FLOFLG 0400 +#define LTYFLG 01000 +#define CALLFLG 02000 +#define MULFLG 04000 +#define SHFFLG 010000 +#define ASGOPFLG 020000 + +#define SPFLG 040000 + +/* + * Location counters + */ +#define PROG 0 /* (ro) program segment */ +#define DATA 1 /* (rw) data segment */ +#define RDATA 2 /* (ro) data segment */ +#define STRNG 3 /* (ro) string segment */ + + +/* + * + */ +extern int bdebug, tdebug, edebug; +extern int ddebug, xdebug, f2debug; +extern int iTflag, oTflag; +extern int vdebug, sflag, nflag, gflag; +extern int Wstrict_prototypes, Wmissing_prototypes, Wimplicit_int, + Wimplicit_function_declaration; +extern int xssaflag, xtailcallflag, xtemps, xdeljumps; + +int yyparse(void); +void yyaccpt(void); + +/* + * List handling macros, similar to those in 4.4BSD. + * The double-linked list is insque-style. + */ +/* Double-linked list macros */ +#define DLIST_INIT(h,f) { (h)->f.q_forw = (h); (h)->f.q_back = (h); } +#define DLIST_ENTRY(t) struct { struct t *q_forw, *q_back; } +#define DLIST_NEXT(h,f) (h)->f.q_forw +#define DLIST_PREV(h,f) (h)->f.q_back +#define DLIST_ISEMPTY(h,f) ((h)->f.q_forw == (h)) +#define DLIST_FOREACH(v,h,f) \ + for ((v) = (h)->f.q_forw; (v) != (h); (v) = (v)->f.q_forw) +#define DLIST_FOREACH_REVERSE(v,h,f) \ + for ((v) = (h)->f.q_back; (v) != (h); (v) = (v)->f.q_back) +#define DLIST_INSERT_BEFORE(h,e,f) { \ + (e)->f.q_forw = (h); \ + (e)->f.q_back = (h)->f.q_back; \ + (e)->f.q_back->f.q_forw = (e); \ + (h)->f.q_back = (e); \ +} +#define DLIST_INSERT_AFTER(h,e,f) { \ + (e)->f.q_forw = (h)->f.q_forw; \ + (e)->f.q_back = (h); \ + (e)->f.q_forw->f.q_back = (e); \ + (h)->f.q_forw = (e); \ +} +#define DLIST_REMOVE(e,f) { \ + (e)->f.q_forw->f.q_back = (e)->f.q_back; \ + (e)->f.q_back->f.q_forw = (e)->f.q_forw; \ +} + +/* Single-linked list */ +#define SLIST_INIT(h) \ + { (h)->q_forw = NULL; (h)->q_last = &(h)->q_forw; } +#define SLIST_ENTRY(t) struct { struct t *q_forw; } +#define SLIST_HEAD(n,t) struct n { struct t *q_forw, **q_last; } +#define SLIST_FIRST(h) ((h)->q_forw) +#define SLIST_FOREACH(v,h,f) \ + for ((v) = (h)->q_forw; (v) != NULL; (v) = (v)->f.q_forw) +#define SLIST_INSERT_LAST(h,e,f) { \ + (e)->f.q_forw = NULL; \ + *(h)->q_last = (e); \ + (h)->q_last = &(e)->f.q_forw; \ +} + +/* + * Functions for inter-pass communication. + * + */ +struct interpass { + DLIST_ENTRY(interpass) qelem; + int type; + int lineno; + union { + NODE *_p; + int _locctr; + int _label; + int _curoff; + char *_name; + } _un; +}; + +/* + * Special struct for prologue/epilogue. + * - ip_lblnum contains the lowest/highest+1 label used + * - ip_lbl is set before/after all code and after/before the prolog/epilog. + */ +struct interpass_prolog { + struct interpass ipp_ip; + char *ipp_name; /* Function name */ + int ipp_vis; /* Function visibility */ + TWORD ipp_type; /* Function type */ + int ipp_regs; /* Bitmask of registers to save */ + int ipp_autos; /* Size on stack needed */ + int ip_tmpnum; /* # allocated temp nodes so far */ + int ip_lblnum; /* # used labels so far */ +}; + +/* + * Epilog/prolog takes following arguments (in order): + * - type + * - regs + * - autos + * - name + * - type + * - retlab + */ + +#define ip_node _un._p +#define ip_locc _un._locctr +#define ip_lbl _un._label +#define ip_name _un._name +#define ip_asm _un._name +#define ip_off _un._curoff + +/* Types of inter-pass structs */ +#define IP_NODE 1 +#define IP_PROLOG 2 +#define IP_EPILOG 4 +#define IP_DEFLAB 5 +#define IP_DEFNAM 6 +#define IP_ASM 7 +#define MAXIP 7 + +void send_passt(int type, ...); +/* + * External declarations, typedefs and the like + */ +char *hash(char *s); +char *savestr(char *cp); +char *tstr(char *cp); + +/* memory management stuff */ +void *permalloc(int size); +void *tmpcalloc(int size); +void *tmpalloc(int size); +void tmpfree(void); +char *newstring(char *, int len); + +void tprint(FILE *, TWORD, TWORD); + +/* pass t communication subroutines */ +void topt_compile(struct interpass *); + +/* pass 2 communication subroutines */ +void pass2_compile(struct interpass *); + +/* node routines */ +NODE *nfree(NODE *); +void fwalk(NODE *t, void (*f)(NODE *, int, int *, int *), int down); + +extern int nerrors; /* number of errors seen so far */ +#endif diff --git a/usr.bin/pcc/mip/match.c b/usr.bin/pcc/mip/match.c new file mode 100644 index 00000000000..503b4698ab0 --- /dev/null +++ b/usr.bin/pcc/mip/match.c @@ -0,0 +1,995 @@ +/* $Id: match.c,v 1.1 2007/09/15 18:12:36 otto Exp $ */ +/* + * Copyright (c) 2003 Anders Magnusson (ragge@ludd.luth.se). + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code and documentation must retain the above + * copyright notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditionsand the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed or owned by Caldera + * International, Inc. + * Neither the name of Caldera International, Inc. nor the names of other + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA + * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE + * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +# include "pass2.h" + +#include <strings.h> + +void prttype(int t); +void setclass(int tmp, int class); +int getclass(int tmp); + +int fldsz, fldshf; + +int s2debug = 0; + +extern char *ltyp[], *rtyp[]; + +static char *srtyp[] = { "SRNOPE", "SRDIR", "SROREG", "SRREG" }; + +/* + * return true if shape is appropriate for the node p + * side effect for SFLD is to set up fldsz, etc + * + * Return values: + * SRNOPE Cannot match this shape. + * SRDIR Direct match, may or may not traverse down. + * SRREG Will match if put in a regster XXX - kill this? + */ +int +tshape(NODE *p, int shape) +{ + int o, mask; + + o = p->n_op; + +#ifdef PCC_DEBUG + if (s2debug) + printf("tshape(%p, %s) op = %s\n", p, prcook(shape), opst[o]); +#endif + + if (shape & SPECIAL) { + + switch (shape) { + case SZERO: + case SONE: + case SMONE: + case SSCON: + case SCCON: + if (o != ICON || p->n_name[0]) + return SRNOPE; + if (p->n_lval == 0 && shape == SZERO) + return SRDIR; + if (p->n_lval == 1 && shape == SONE) + return SRDIR; + if (p->n_lval == -1 && shape == SMONE) + return SRDIR; + if (p->n_lval > -257 && p->n_lval < 256 && + shape == SCCON) + return SRDIR; + if (p->n_lval > -32769 && p->n_lval < 32768 && + shape == SSCON) + return SRDIR; + return SRNOPE; + + case SSOREG: /* non-indexed OREG */ + if (o == OREG && !R2TEST(p->n_rval)) + return SRDIR; + return SRNOPE; + + default: + return (special(p, shape)); + } + } + + if (shape & SANY) + return SRDIR; + + if ((shape&INTEMP) && shtemp(p)) /* XXX remove? */ + return SRDIR; + + if ((shape&SWADD) && (o==NAME||o==OREG)) + if (BYTEOFF(p->n_lval)) + return SRNOPE; + + switch (o) { + + case NAME: + if (shape & SNAME) + return SRDIR; + break; + + case ICON: + if (shape & SCON) + return SRDIR; + break; + + case FLD: + if (shape & SFLD) { + int sh; + + if ((sh = flshape(p->n_left)) == SRNOPE) + return sh; + /* it is a FIELD shape; make side-effects */ + /* XXX - this will not work for multi-matches */ + o = p->n_rval; + fldsz = UPKFSZ(o); +# ifdef RTOLBYTES + fldshf = UPKFOFF(o); +# else + fldshf = SZINT - fldsz - UPKFOFF(o); +# endif + return sh; + } + break; + + case CCODES: + if (shape & SCC) + return SRDIR; + break; + + case REG: + case TEMP: + mask = PCLASS(p); + if (shape & mask) + return SRDIR; + break; + + case OREG: + if (shape & SOREG) + return SRDIR; + break; + + case UMUL: + if (shumul(p->n_left) & shape) + return SROREG; /* Calls offstar to traverse down */ + break; + + } + return SRNOPE; +} + +/* + * does the type t match tword + */ +int +ttype(TWORD t, int tword) +{ + if (tword & TANY) + return(1); + +#ifdef PCC_DEBUG + if (t2debug) + printf("ttype(%o, %o)\n", t, tword); +#endif + if (ISPTR(t) && ISFTN(DECREF(t)) && (tword & TFTN)) { + /* For funny function pointers */ + return 1; + } + if (ISPTR(t) && (tword&TPTRTO)) { + do { + t = DECREF(t); + } while (ISARY(t)); + /* arrays that are left are usually only + * in structure references... + */ + return (ttype(t, tword&(~TPTRTO))); + } + if (t != BTYPE(t)) + return (tword & TPOINT); /* TPOINT means not simple! */ + if (tword & TPTRTO) + return(0); + + switch (t) { + case CHAR: + return( tword & TCHAR ); + case SHORT: + return( tword & TSHORT ); + case STRTY: + case UNIONTY: + return( tword & TSTRUCT ); + case INT: + return( tword & TINT ); + case UNSIGNED: + return( tword & TUNSIGNED ); + case USHORT: + return( tword & TUSHORT ); + case UCHAR: + return( tword & TUCHAR ); + case ULONG: + return( tword & TULONG ); + case LONG: + return( tword & TLONG ); + case LONGLONG: + return( tword & TLONGLONG ); + case ULONGLONG: + return( tword & TULONGLONG ); + case FLOAT: + return( tword & TFLOAT ); + case DOUBLE: + return( tword & TDOUBLE ); + case LDOUBLE: + return( tword & TLDOUBLE ); + } + + return(0); +} + +/* + * generate code by interpreting table entry + */ +void +expand(NODE *p, int cookie, char *cp) +{ + CONSZ val; + + for( ; *cp; ++cp ){ + switch( *cp ){ + + default: + PUTCHAR( *cp ); + continue; /* this is the usual case... */ + + case 'Z': /* special machine dependent operations */ + zzzcode( p, *++cp ); + continue; + + case 'F': /* this line deleted if FOREFF is active */ + if( cookie & FOREFF ) while( *++cp != '\n' ) ; /* VOID */ + continue; + + case 'S': /* field size */ + printf( "%d", fldsz ); + continue; + + case 'H': /* field shift */ + printf( "%d", fldshf ); + continue; + + case 'M': /* field mask */ + case 'N': /* complement of field mask */ + val = 1; + val <<= fldsz; + --val; + val <<= fldshf; + adrcon( *cp=='M' ? val : ~val ); + continue; + + case 'L': /* output special label field */ + if (*++cp == 'C') + printf(LABFMT, p->n_label); + else + printf(LABFMT, (int)getlr(p,*cp)->n_lval); + continue; + + case 'O': /* opcode string */ + hopcode( *++cp, p->n_op ); + continue; + + case 'B': /* byte offset in word */ + val = getlr(p,*++cp)->n_lval; + val = BYTEOFF(val); + printf( CONFMT, val ); + continue; + + case 'C': /* for constant value only */ + conput(stdout, getlr( p, *++cp ) ); + continue; + + case 'I': /* in instruction */ + insput( getlr( p, *++cp ) ); + continue; + + case 'A': /* address of */ + adrput(stdout, getlr( p, *++cp ) ); + continue; + + case 'U': /* for upper half of address, only */ + upput(getlr(p, *++cp), SZLONG); + continue; + + } + + } + + } + +NODE resc[4]; + +NODE * +getlr(NODE *p, int c) +{ + NODE *q; + + /* return the pointer to the left or right side of p, or p itself, + depending on the optype of p */ + + switch (c) { + + case '1': + case '2': + case '3': + case 'D': + if (c == 'D') + c = 0; + else + c -= '0'; + q = &resc[c]; + q->n_op = REG; + q->n_type = p->n_type; /* XXX should be correct type */ + q->n_rval = DECRA(p->n_reg, c); + q->n_su = p->n_su; + return q; + + case 'L': + return( optype( p->n_op ) == LTYPE ? p : p->n_left ); + + case 'R': + return( optype( p->n_op ) != BITYPE ? p : p->n_right ); + + } + cerror( "bad getlr: %c", c ); + /* NOTREACHED */ + return NULL; +} + +static char *tarr[] = { + "CHAR", "SHORT", "INT", "LONG", "FLOAT", "DOUBLE", "POINT", "UCHAR", + "USHORT", "UINT", "ULONG", "PTRTO", "ANY", "STRUCT", "LONGLONG", + "ULONGLONG", +}; + +void +prttype(int t) +{ + int i, gone = 0; + + for (i = 0; i < 16; i++) + if ((t >> i) & 1) { + if (gone) putchar('|'); + gone++; + printf("%s", tarr[i]); + } +} + + +#ifdef PCC_DEBUG +#define F2DEBUG(x) if (f2debug) printf x +#define F2WALK(x) if (f2debug) fwalk(x, e2print, 0) +#else +#define F2DEBUG(x) +#define F2WALK(x) +#endif + +/* + * Convert a node to REG or OREG. + * Shape is register class where we want the result. + * Returns register class if register nodes. + * If w is: (should be shapes) + * - LREG - result in register, call geninsn(). + * - LOREG - create OREG; call offstar(). + * - 0 - clear su, walk down. + */ +static int +swmatch(NODE *p, int shape, int w) +{ + int rv = 0; + + switch (w) { + case LREG: + rv = geninsn(p, shape); + break; + + case LOREG: + /* should be here only if op == UMUL */ + if (p->n_op != UMUL && p->n_op != FLD) + comperr("swmatch %p", p); + if (p->n_op == FLD) { + offstar(p->n_left->n_left, shape); + p->n_left->n_su = 0; + } else + offstar(p->n_left, shape); + p->n_su = 0; + rv = ffs(shape)-1; + break; + + case 0: + if (optype(p->n_op) == BITYPE) + swmatch(p->n_right, 0, 0); + if (optype(p->n_op) != LTYPE) + swmatch(p->n_left, 0, 0); + p->n_su = 0; + } + return rv; + +} + +/* + * Help routines for find*() functions. + * If the node will be a REG node and it will be rewritten in the + * instruction, ask for it to be put in a register. + */ +static int +chcheck(NODE *p, int shape, int rew) +{ + int sh, sha; + + sha = shape; + if (shape & SPECIAL) + shape = 0; + + switch ((sh = tshape(p, sha))) { + case SRNOPE: + if (shape & INREGS) + sh = SRREG; + break; + + case SROREG: + case SRDIR: + if (rew == 0) + break; + if (shape & INREGS) + sh = SRREG; + else + sh = SRNOPE; + break; + } + return sh; +} + +/* + * Check how to walk further down. + * Merge with swmatch()? + * sh - shape for return value (register class). + * p - node (for this leg) + * shape - given shape for this leg + * cookie - cookie given for parent node + * rv - switch key for traversing down + * returns register class. + */ +static int +shswitch(int sh, NODE *p, int shape, int cookie, int rew, int go) +{ + int lsh; + + switch (go) { + case SRDIR: /* direct match, just clear su */ + (void)swmatch(p, 0, 0); + break; + + case SROREG: /* call offstar to prepare for OREG conversion */ + (void)swmatch(p, shape, LOREG); + break; + + case SRREG: /* call geninsn() to get value into register */ + lsh = shape & INREGS; + if (rew && cookie != FOREFF) + lsh &= (cookie & INREGS); + lsh = swmatch(p, lsh, LREG); + if (rew) + sh = lsh; + break; + } + return sh; +} + +/* + * Find the best instruction to evaluate the given tree. + * Best is to match both subnodes directly, second-best is if + * subnodes must be evaluated into OREGs, thereafter if nodes + * must be put into registers. + * Whether 2-op instructions or 3-op is preferred is depending on in + * which order they are found in the table. + * mtchno is set to the count of regs needed for its legs. + */ +int +findops(NODE *p, int cookie) +{ + extern int *qtable[]; + struct optab *q, *qq = NULL; + int i, shl, shr, *ixp, sh; + int lvl = 10, idx = 0, gol = 0, gor = 0; + NODE *l, *r; + + F2DEBUG(("findops node %p (%s)\n", p, prcook(cookie))); + F2WALK(p); + + ixp = qtable[p->n_op]; + l = getlr(p, 'L'); + r = getlr(p, 'R'); + for (i = 0; ixp[i] >= 0; i++) { + q = &table[ixp[i]]; + + F2DEBUG(("findop: ixp %d\n", ixp[i])); + if (ttype(l->n_type, q->ltype) == 0 || + ttype(r->n_type, q->rtype) == 0) + continue; /* Types must be correct */ + + if ((cookie & q->visit) == 0) + continue; /* must get a result */ + + F2DEBUG(("findop got types\n")); + + if ((shl = chcheck(l, q->lshape, q->rewrite & RLEFT)) == SRNOPE) + continue; + + F2DEBUG(("findop lshape %d\n", shl)); + F2WALK(l); + + if ((shr = chcheck(r, q->rshape, q->rewrite & RRIGHT))== SRNOPE) continue; + + F2DEBUG(("findop rshape %d\n", shr)); + F2WALK(r); + + if (q->needs & REWRITE) + break; /* Done here */ + + if (lvl <= (shl + shr)) + continue; + lvl = shl + shr; + qq = q; + idx = ixp[i]; + gol = shl; + gor = shr; + } + if (lvl == 10) { + F2DEBUG(("findops failed\n")); + if (setbin(p)) + return FRETRY; + return FFAIL; + } + + F2DEBUG(("findops entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor])); + + sh = -1; + + sh = shswitch(sh, p->n_left, qq->lshape, cookie, + qq->rewrite & RLEFT, gol); + sh = shswitch(sh, p->n_right, qq->rshape, cookie, + qq->rewrite & RRIGHT, gor); + + if (sh == -1) { + if (cookie == FOREFF) + sh = 0; + else + sh = ffs(cookie & qq->visit & INREGS)-1; + } + F2DEBUG(("findops: node %p (%s)\n", p, prcook(1 << sh))); + p->n_su = MKIDX(idx, 0); + SCLASS(p->n_su, sh); + return sh; +} + +/* + * Find the best relation op for matching the two trees it has. + * This is a sub-version of the function findops() above. + * The instruction with the lowest grading is emitted. + * + * Level assignment for priority: + * left right prio + * - - - + * direct direct 1 + * direct OREG 2 # make oreg + * OREG direct 2 # make oreg + * OREG OREG 2 # make both oreg + * direct REG 3 # put in reg + * OREG REG 3 # put in reg, make oreg + * REG direct 3 # put in reg + * REG OREG 3 # put in reg, make oreg + * REG REG 4 # put both in reg + */ +int +relops(NODE *p) +{ + extern int *qtable[]; + struct optab *q; + int i, shl = 0, shr = 0; + NODE *l, *r; + int *ixp, idx = 0; + int lvl = 10, gol = 0, gor = 0; + + F2DEBUG(("relops tree:\n")); + F2WALK(p); + + l = getlr(p, 'L'); + r = getlr(p, 'R'); + ixp = qtable[p->n_op]; + for (i = 0; ixp[i] >= 0; i++) { + q = &table[ixp[i]]; + + F2DEBUG(("relops: ixp %d\n", ixp[i])); + if (ttype(l->n_type, q->ltype) == 0 || + ttype(r->n_type, q->rtype) == 0) + continue; /* Types must be correct */ + + F2DEBUG(("relops got types\n")); + if ((shl = chcheck(l, q->lshape, 0)) == SRNOPE) + continue; + F2DEBUG(("relops lshape %d\n", shl)); + F2WALK(p); + if ((shr = chcheck(r, q->rshape, 0)) == SRNOPE) + continue; + F2DEBUG(("relops rshape %d\n", shr)); + F2WALK(p); + if (q->needs & REWRITE) + break; /* Done here */ + + if (lvl <= (shl + shr)) + continue; + lvl = shl + shr; + idx = ixp[i]; + gol = shl; + gor = shr; + } + if (lvl == 10) { + F2DEBUG(("relops failed\n")); + if (setbin(p)) + return FRETRY; + return FFAIL; + } + F2DEBUG(("relops entry %d(%s %s)\n", idx, srtyp[gol], srtyp[gor])); + + q = &table[idx]; + + (void)shswitch(-1, p->n_left, q->lshape, FORCC, + q->rewrite & RLEFT, gol); + + (void)shswitch(-1, p->n_right, q->rshape, FORCC, + q->rewrite & RRIGHT, gor); + + F2DEBUG(("findops: node %p\n", p)); + p->n_su = MKIDX(idx, 0); + SCLASS(p->n_su, CLASSA); /* XXX */ + return 0; +} + +/* + * Find a matching assign op. + * + * Level assignment for priority: + * left right prio + * - - - + * direct direct 1 + * direct REG 2 + * direct OREG 3 + * OREG direct 4 + * OREG REG 5 + * OREG OREG 6 + */ +int +findasg(NODE *p, int cookie) +{ + extern int *qtable[]; + struct optab *q; + int i, sh, shl, shr, lvl = 10; + NODE *l, *r; + int *ixp; + struct optab *qq = NULL; /* XXX gcc */ + int idx = 0, gol = 0, gor = 0; + + shl = shr = 0; + + F2DEBUG(("findasg tree: %s\n", prcook(cookie))); + F2WALK(p); + + ixp = qtable[p->n_op]; + l = getlr(p, 'L'); + r = getlr(p, 'R'); + for (i = 0; ixp[i] >= 0; i++) { + q = &table[ixp[i]]; + + F2DEBUG(("asgop: ixp %d\n", ixp[i])); + if (ttype(l->n_type, q->ltype) == 0 || + ttype(r->n_type, q->rtype) == 0) + continue; /* Types must be correct */ + + if ((cookie & q->visit) == 0) + continue; /* must get a result */ + + F2DEBUG(("asgop got types\n")); + if ((shl = tshape(l, q->lshape)) == SRNOPE) + continue; + + if (shl == SRREG) + continue; + + F2DEBUG(("asgop lshape %d\n", shl)); + F2WALK(l); + + if ((shr = chcheck(r, q->rshape, q->rewrite & RRIGHT))== SRNOPE) + continue; + + F2DEBUG(("asgop rshape %d\n", shr)); + F2WALK(r); + if (q->needs & REWRITE) + break; /* Done here */ + + if (lvl <= (shl + shr)) + continue; + + lvl = shl + shr; + qq = q; + idx = ixp[i]; + gol = shl; + gor = shr; + } + + if (lvl == 10) { + F2DEBUG(("findasg failed\n")); + if (setasg(p, cookie)) + return FRETRY; + return FFAIL; + } + F2DEBUG(("findasg entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor])); + + sh = -1; + sh = shswitch(sh, p->n_left, qq->lshape, cookie, + qq->rewrite & RLEFT, gol); + + sh = shswitch(sh, p->n_right, qq->rshape, cookie, + qq->rewrite & RRIGHT, gor); + + if (sh == -1) { + if (cookie == FOREFF) + sh = 0; + else + sh = ffs(cookie & qq->visit & INREGS)-1; + } + F2DEBUG(("findasg: node %p class %d\n", p, sh)); + + p->n_su = MKIDX(idx, 0); + SCLASS(p->n_su, sh); + + return sh; +} + +/* + * Search for an UMUL table entry that can turn an indirect node into + * a move from an OREG. + */ +int +findumul(NODE *p, int cookie) +{ + extern int *qtable[]; + struct optab *q = NULL; /* XXX gcc */ + int i, shl = 0, shr = 0, sh; + int *ixp; + + F2DEBUG(("findumul p %p (%s)\n", p, prcook(cookie))); + F2WALK(p); + + ixp = qtable[p->n_op]; + for (i = 0; ixp[i] >= 0; i++) { + q = &table[ixp[i]]; + + F2DEBUG(("findumul: ixp %d\n", ixp[i])); + if ((q->visit & cookie) == 0) + continue; /* wrong registers */ + + if (ttype(p->n_type, q->rtype) == 0) + continue; /* Types must be correct */ + + + F2DEBUG(("findumul got types, rshape %s\n", prcook(q->rshape))); + /* + * Try to create an OREG of the node. + * Fake left even though it's right node, + * to be sure of conversion if going down left. + */ + if ((shl = chcheck(p, q->rshape, 0)) == SRNOPE) + continue; + + shr = 0; + + if (q->needs & REWRITE) + break; /* Done here */ + + F2DEBUG(("findumul got shape %s\n", srtyp[shl])); + + break; /* XXX search better matches */ + } + if (ixp[i] < 0) { + F2DEBUG(("findumul failed\n")); + if (setuni(p, cookie)) + return FRETRY; + return FFAIL; + } + F2DEBUG(("findumul entry %d(%s %s)\n", ixp[i], srtyp[shl], srtyp[shr])); + + sh = shswitch(-1, p, q->rshape, cookie, q->rewrite & RLEFT, shl); + if (sh == -1) + sh = ffs(cookie & q->visit & INREGS)-1; + + F2DEBUG(("findumul: node %p (%s)\n", p, prcook(1 << sh))); + p->n_su = MKIDX(ixp[i], 0); + SCLASS(p->n_su, sh); + return sh; +} + +/* + * Find a leaf type node that puts the value into a register. + */ +int +findleaf(NODE *p, int cookie) +{ + extern int *qtable[]; + struct optab *q = NULL; /* XXX gcc */ + int i, sh; + int *ixp; + + F2DEBUG(("findleaf p %p (%s)\n", p, prcook(cookie))); + F2WALK(p); + + ixp = qtable[p->n_op]; + for (i = 0; ixp[i] >= 0; i++) { + q = &table[ixp[i]]; + + F2DEBUG(("findleaf: ixp %d\n", ixp[i])); + if ((q->visit & cookie) == 0) + continue; /* wrong registers */ + + if (ttype(p->n_type, q->rtype) == 0 || + ttype(p->n_type, q->ltype) == 0) + continue; /* Types must be correct */ + + F2DEBUG(("findleaf got types, rshape %s\n", prcook(q->rshape))); + + if (chcheck(p, q->rshape, 0) != SRDIR) + continue; + + if (q->needs & REWRITE) + break; /* Done here */ + + break; + } + if (ixp[i] < 0) { + F2DEBUG(("findleaf failed\n")); + if (setuni(p, cookie)) + return FRETRY; + return FFAIL; + } + F2DEBUG(("findleaf entry %d\n", ixp[i])); + + sh = ffs(cookie & q->visit & INREGS)-1; + F2DEBUG(("findleaf: node %p (%s)\n", p, prcook(1 << sh))); + p->n_su = MKIDX(ixp[i], 0); + SCLASS(p->n_su, sh); + return sh; +} + +/* + * Find a UNARY op that satisfy the needs. + * For now, the destination is always a register. + * Both source and dest types must match, but only source (left) + * shape is of interest. + */ +int +finduni(NODE *p, int cookie) +{ + extern int *qtable[]; + struct optab *q; + NODE *l, *r; + int i, shl = 0, num = 4; + int *ixp, idx = 0; + int sh; + + F2DEBUG(("finduni tree: %s\n", prcook(cookie))); + F2WALK(p); + + l = getlr(p, 'L'); + if (p->n_op == CALL || p->n_op == FORTCALL || p->n_op == STCALL) + r = p; + else + r = getlr(p, 'R'); + ixp = qtable[p->n_op]; + for (i = 0; ixp[i] >= 0; i++) { + q = &table[ixp[i]]; + + F2DEBUG(("finduni: ixp %d\n", ixp[i])); + if (ttype(l->n_type, q->ltype) == 0) + continue; /* Type must be correct */ + + F2DEBUG(("finduni got left type\n")); + if (ttype(r->n_type, q->rtype) == 0) + continue; /* Type must be correct */ + + F2DEBUG(("finduni got types\n")); + if ((shl = chcheck(l, q->lshape, q->rewrite & RLEFT)) == SRNOPE) + continue; + + F2DEBUG(("finduni got shapes %d\n", shl)); + + if ((cookie & q->visit) == 0) /* check correct return value */ + continue; /* XXX - should check needs */ + + /* avoid clobbering of longlived regs */ + /* let register allocator coalesce */ + if ((q->rewrite & RLEFT) && (shl == SRDIR) /* && isreg(l) */) + shl = SRREG; + + F2DEBUG(("finduni got cookie\n")); + if (q->needs & REWRITE) + break; /* Done here */ + + if (shl >= num) + continue; + num = shl; + idx = ixp[i]; + + if (shl == SRDIR) + break; + } + + if (num == 4) { + F2DEBUG(("finduni failed\n")); + } else + F2DEBUG(("finduni entry %d(%s)\n", idx, srtyp[num])); + + if (num == 4) { + if (setuni(p, cookie)) + return FRETRY; + return FFAIL; + } + q = &table[idx]; + + sh = shswitch(-1, p->n_left, q->lshape, cookie, + q->rewrite & RLEFT, num); + if (sh == -1) + sh = ffs(cookie & q->visit & INREGS)-1; + if (sh == -1) + sh = 0; + + F2DEBUG(("finduni: node %p (%s)\n", p, prcook(1 << sh))); + p->n_su = MKIDX(idx, 0); + SCLASS(p->n_su, sh); + return sh; +} diff --git a/usr.bin/pcc/mip/mkext.c b/usr.bin/pcc/mip/mkext.c new file mode 100644 index 00000000000..347dd8ee43f --- /dev/null +++ b/usr.bin/pcc/mip/mkext.c @@ -0,0 +1,318 @@ + +/* + * Generate defines for the needed hardops. + */ +#include "pass2.h" + +#include <string.h> + +int chkop[MAXOP]; + +void mktables(void); + +char *cname = "external.c"; +char *hname = "external.h"; +FILE *fc, *fh; + +/* + * masks for matching dope with shapes + */ +int mamask[] = { + SIMPFLG, /* OPSIMP */ + SIMPFLG|ASGFLG, /* ASG OPSIMP */ + COMMFLG, /* OPCOMM */ + COMMFLG|ASGFLG, /* ASG OPCOMM */ + MULFLG, /* OPMUL */ + MULFLG|ASGFLG, /* ASG OPMUL */ + DIVFLG, /* OPDIV */ + DIVFLG|ASGFLG, /* ASG OPDIV */ + UTYPE, /* OPUNARY */ + TYFLG, /* ASG OPUNARY is senseless */ + LTYPE, /* OPLEAF */ + TYFLG, /* ASG OPLEAF is senseless */ + 0, /* OPANY */ + ASGOPFLG|ASGFLG, /* ASG OPANY */ + LOGFLG, /* OPLOG */ + TYFLG, /* ASG OPLOG is senseless */ + FLOFLG, /* OPFLOAT */ + FLOFLG|ASGFLG, /* ASG OPFLOAT */ + SHFFLG, /* OPSHFT */ + SHFFLG|ASGFLG, /* ASG OPSHIFT */ + SPFLG, /* OPLTYPE */ + TYFLG, /* ASG OPLTYPE is senseless */ + }; + + +struct checks { + int op, type; + char *name; +} checks[] = { + { MUL, TLONGLONG, "SMULLL", }, + { DIV, TLONGLONG, "SDIVLL", }, + { MOD, TLONGLONG, "SMODLL", }, + { PLUS, TLONGLONG, "SPLUSLL", }, + { MINUS, TLONGLONG, "SMINUSLL", }, + { MUL, TULONGLONG, "UMULLL", }, + { DIV, TULONGLONG, "UDIVLL", }, + { MOD, TULONGLONG, "UMODLL", }, + { PLUS, TULONGLONG, "UPLUSLL", }, + { MINUS, TULONGLONG, "UMINUSLL", }, + { 0, 0, 0, }, +}; + +int rstatus[] = { RSTATUS }; +int roverlay[MAXREGS][MAXREGS] = { ROVERLAP }; +int regclassmap[NUMCLASS][MAXREGS]; + +static void +compl(struct optab *q, char *str) +{ + printf("table entry %td, op %s: %s\n", q - table, opst[q->op], str); +} + +int +main(int argc, char *argv[]) +{ + struct optab *q; + struct checks *ch; + int i, j, areg, breg, creg, dreg, mx; + char *bitary; + int bitsz, rval, nelem; + + mkdope(); + + for (q = table; q->op != FREE; q++) { + if (q->op >= OPSIMP) + continue; + if ((q->ltype & TLONGLONG) && + (q->rtype & TLONGLONG)) + chkop[q->op] |= TLONGLONG; + if ((q->ltype & TULONGLONG) && + (q->rtype & TULONGLONG)) + chkop[q->op] |= TULONGLONG; + } + if ((fc = fopen(cname, "w")) == NULL) { + perror("open cfile"); + return(1); + } + if ((fh = fopen(hname, "w")) == NULL) { + perror("open hfile"); + return(1); + } + for (ch = checks; ch->op != 0; ch++) { + if ((chkop[ch->op] & ch->type) == 0) + fprintf(fh, "#define NEED_%s\n", ch->name); + } + + fprintf(fc, "#include \"pass2.h\"\n"); + /* create fast-lookup tables */ + mktables(); + + /* create efficient bitset sizes */ + if (sizeof(long) == 8) { /* 64-bit arch */ + bitary = "long"; + bitsz = 64; + } else { + bitary = "int"; + bitsz = sizeof(int) == 4 ? 32 : 16; + } + fprintf(fh, "#define NUMBITS %d\n", bitsz); + fprintf(fh, "#define BITSET(arr, bit) " + "(arr[bit/NUMBITS] |= (1 << (bit & (NUMBITS-1))))\n"); + fprintf(fh, "#define BITCLEAR(arr, bit) " + "(arr[bit/NUMBITS] &= ~(1 << (bit & (NUMBITS-1))))\n"); + fprintf(fh, "#define TESTBIT(arr, bit) " + "(arr[bit/NUMBITS] & (1 << (bit & (NUMBITS-1))))\n"); + fprintf(fh, "typedef %s bittype;\n", bitary); + + /* register class definitions, used by graph-coloring */ + /* TODO */ + + /* Sanity-check the table */ + rval = 0; + for (q = table; q->op != FREE; q++) { + if (q->op == ASSIGN) { +#define F(x) (q->visit & x && q->rewrite & (RLEFT|RRIGHT) && \ + q->lshape & ~x && q->rshape & ~x) + if (F(INAREG) || F(INBREG) || F(INCREG) || F(INDREG)) { + compl(q, "may match without result register"); + rval++; + } +#undef F + if ((q->visit & INREGS) && q->rewrite != RDEST) { + compl(q, "ASSIGN reclaim must be RDEST"); + rval++; + } + } + if (q->rewrite & (RESC1|RESC2|RESC1) && q->visit & FOREFF) + compl(q, "FOREFF may cause reclaim of wrong class"); + } + + /* print out list of scratched and permanent registers */ + fprintf(fh, "extern int tempregs[], permregs[];\n"); + fprintf(fc, "int tempregs[] = { "); + for (i = j = 0; i < MAXREGS; i++) + if (rstatus[i] & TEMPREG) + fprintf(fc, "%d, ", i), j++; + fprintf(fc, "-1 };\n"); + fprintf(fh, "#define NTEMPREG %d\n", j+1); + fprintf(fh, "#define FREGS %d\n", j); /* XXX - to die */ + fprintf(fc, "int permregs[] = { "); + for (i = j = 0; i < MAXREGS; i++) + if (rstatus[i] & PERMREG) + fprintf(fc, "%d, ", i), j++; + fprintf(fc, "-1 };\n"); + fprintf(fh, "#define NPERMREG %d\n", j+1); + + /* + * The register allocator uses bitmasks of registers for each class. + */ + areg = breg = creg = dreg = 0; + for (i = 0; i < MAXREGS; i++) { + regclassmap[0][i] = regclassmap[1][i] = regclassmap[2][i] = + regclassmap[3][i] = -1; + if (rstatus[i] & SAREG) regclassmap[0][i] = areg++; + if (rstatus[i] & SBREG) regclassmap[1][i] = breg++; + if (rstatus[i] & SCREG) regclassmap[2][i] = creg++; + if (rstatus[i] & SDREG) regclassmap[3][i] = dreg++; + } + fprintf(fh, "#define AREGCNT %d\n", areg); + fprintf(fh, "#define BREGCNT %d\n", breg); + fprintf(fh, "#define CREGCNT %d\n", creg); + fprintf(fh, "#define DREGCNT %d\n", dreg); + if (areg > bitsz) + printf("%d regs in class A (max %d)\n", areg, bitsz), rval++; + if (breg > bitsz) + printf("%d regs in class B (max %d)\n", breg, bitsz), rval++; + if (creg > bitsz) + printf("%d regs in class C (max %d)\n", creg, bitsz), rval++; + if (dreg > bitsz) + printf("%d regs in class D (max %d)\n", dreg, bitsz), rval++; + + fprintf(fc, "static int amap[MAXREGS][NUMCLASS] = {\n"); + for (i = 0; i < MAXREGS; i++) { + int ba, bb, bc, bd, r; + ba = bb = bc = bd = 0; + if (rstatus[i] & SAREG) ba = (1 << regclassmap[0][i]); + if (rstatus[i] & SBREG) bb = (1 << regclassmap[1][i]); + if (rstatus[i] & SCREG) bc = (1 << regclassmap[2][i]); + if (rstatus[i] & SDREG) bd = (1 << regclassmap[3][i]); + for (j = 0; roverlay[i][j] >= 0; j++) { + r = roverlay[i][j]; + if (rstatus[r] & SAREG) + ba |= (1 << regclassmap[0][r]); + if (rstatus[r] & SBREG) + bb |= (1 << regclassmap[1][r]); + if (rstatus[r] & SCREG) + bc |= (1 << regclassmap[2][r]); + if (rstatus[r] & SDREG) + bd |= (1 << regclassmap[3][r]); + } + fprintf(fc, "\t{ 0x%x,0x%x,0x%x,0x%x },\n", ba, bb, bc, bd); + } + fprintf(fc, "};\n"); + + fprintf(fh, "int aliasmap(int class, int regnum);\n"); + fprintf(fc, "int\naliasmap(int class, int regnum)\n{\n"); + fprintf(fc, " return amap[regnum][class-1];\n}\n"); + + /* routines to convert back from color to regnum */ + mx = areg; + if (breg > mx) mx = breg; + if (creg > mx) mx = creg; + if (dreg > mx) mx = dreg; + fprintf(fc, "static int rmap[NUMCLASS][%d] = {\n", mx); + for (j = 0; j < NUMCLASS; j++) { + int cl = (1 << (j+1)); + fprintf(fc, "\t{ "); + for (i = 0; i < MAXREGS; i++) + if (rstatus[i] & cl) fprintf(fc, "%d, ", i); + fprintf(fc, "},\n"); + } + fprintf(fc, "};\n\n"); + + fprintf(fh, "int color2reg(int color, int class);\n"); + fprintf(fc, "int\ncolor2reg(int color, int class)\n{\n"); + fprintf(fc, " return rmap[class-1][color];\n}\n"); + + /* used by register allocator */ + fprintf(fc, "int regK[] = { 0, %d, %d, %d, %d };\n", + areg, breg, creg, dreg); + fprintf(fc, "int\nclassmask(int class)\n{\n"); + fprintf(fc, "\tif(class == CLASSA) return 0x%x;\n", (1 << areg)-1); + fprintf(fc, "\tif(class == CLASSB) return 0x%x;\n", (1 << breg)-1); + fprintf(fc, "\tif(class == CLASSC) return 0x%x;\n", (1 << creg)-1); + fprintf(fc, "\treturn 0x%x;\n}\n", (1 << dreg)-1); + + fprintf(fh, "int interferes(int reg1, int reg2);\n"); + nelem = (MAXREGS+bitsz-1)/bitsz; + fprintf(fc, "static bittype ovlarr[MAXREGS][%d] = {\n", nelem); + for (i = 0; i < MAXREGS; i++) { + int el[10]; + memset(el, 0, sizeof(el)); + el[i/bitsz] = 1 << (i % bitsz); + for (j = 0; roverlay[i][j] >= 0; j++) { + int k = roverlay[i][j]; + el[k/bitsz] |= (1 << (k % bitsz)); + } + fprintf(fc, "{ "); + for (j = 0; j < MAXREGS; j += bitsz) + fprintf(fc, "0x%x, ", el[j/bitsz]); + fprintf(fc, " },\n"); + } + fprintf(fc, "};\n"); + + fprintf(fc, "int\ninterferes(int reg1, int reg2)\n{\n"); + fprintf(fc, "return TESTBIT(ovlarr[reg1], reg2);\n}\n"); + fclose(fc); + fclose(fh); + return rval; +} + +#define P(x) fprintf x + +void +mktables() +{ + struct optab *op; + int mxalen = 0, curalen; + int i; + +// P((fc, "#include \"pass2.h\"\n\n")); + for (i = 0; i <= MAXOP; i++) { + curalen = 0; + P((fc, "static int op%d[] = { ", i)); + if (dope[i] != 0) + for (op = table; op->op != FREE; op++) { + if (op->op < OPSIMP) { + if (op->op == i) { + P((fc, "%td, ", op - table)); + curalen++; + } + } else { + int opmtemp; + if ((opmtemp=mamask[op->op - OPSIMP])&SPFLG) { + if (i==NAME || i==ICON || i==TEMP || + i==OREG || i == REG) { + P((fc, "%td, ", op - table)); + curalen++; + } + } else if ((dope[i]&(opmtemp|ASGFLG))==opmtemp){ + P((fc, "%td, ", op - table)); + curalen++; + } + } + } + if (curalen > mxalen) + mxalen = curalen; + P((fc, "-1 };\n")); + } + P((fc, "\n")); + + P((fc, "int *qtable[] = { \n")); + for (i = 0; i <= MAXOP; i++) { + P((fc, " op%d,\n", i)); + } + P((fc, "};\n")); + P((fh, "#define MAXOPLEN %d\n", mxalen+1)); +} diff --git a/usr.bin/pcc/mip/node.h b/usr.bin/pcc/mip/node.h new file mode 100644 index 00000000000..3d42df7500c --- /dev/null +++ b/usr.bin/pcc/mip/node.h @@ -0,0 +1,194 @@ +/* $Id: node.h,v 1.1 2007/09/15 18:12:36 otto Exp $ */ +/* + * Copyright (c) 2003 Anders Magnusson (ragge@ludd.luth.se). + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * The node structure is the basic element in the compiler. + * Depending on the operator, it may be one of several types. + * + * This is rewritten to be a struct instead of a union as it + * was in the old compiler. + */ +typedef unsigned int TWORD; +#define NIL (NODE *)0 + +struct symtab; +struct suedef; +struct regw; + +typedef struct node { + struct node *next; + int n_op; + union { + int _reg; + struct regw *_regw; + } n_3; +#define n_reg n_3._reg +#define n_regw n_3._regw + TWORD n_type; + TWORD n_qual; + int n_su; + union { + char * _name; + int _stsize; + union dimfun *_df; + } n_5; + union { + int _label; + int _stalign; + struct suedef *_sue; + } n_6; + union { + struct { + union { + struct node *_left; + CONSZ _lval; +#ifdef SPECIAL_INTEGERS + SPECLVAL _slval; +#endif + } n_l; + union { + struct node *_right; + int _rval; + struct symtab *_sp; + } n_r; + } n_u; + long double _dcon; + } n_f; +} NODE; + +#define n_name n_5._name +#define n_stsize n_5._stsize +#define n_df n_5._df + +#define n_label n_6._label +#define n_stalign n_6._stalign +#define n_sue n_6._sue + +#define n_left n_f.n_u.n_l._left +#define n_lval n_f.n_u.n_l._lval +#define n_slval n_f.n_u.n_l._slval +#define n_right n_f.n_u.n_r._right +#define n_rval n_f.n_u.n_r._rval +#define n_sp n_f.n_u.n_r._sp +#define n_dcon n_f._dcon + +/* + * Node types. + * + * MAXOP is the highest number used by the backend. + */ + +#define FREE 1 +/* + * Value nodes. + */ +#define NAME 2 +#define ICON 4 +#define FCON 5 +#define REG 6 +#define OREG 7 +#define TEMP 8 +#define MOVE 9 /* Special reg-reg move node */ + +/* + * Arithmetic nodes. + */ +#define PLUS 10 +#define MINUS 11 +#define DIV 12 +#define MOD 13 +#define MUL 14 + +/* + * Bitwise operations. + */ +#define AND 15 +#define OR 16 +#define ER 17 +#define LS 18 +#define RS 19 +#define COMPL 20 + +#define UMUL 23 +#define UMINUS 24 + +/* + * Logical compare nodes. + */ +#define EQ 25 +#define NE 26 +#define LE 27 +#define LT 28 +#define GE 29 +#define GT 30 +#define ULE 31 +#define ULT 32 +#define UGE 33 +#define UGT 34 + +/* + * Branch nodes. + */ +#define CBRANCH 35 + +/* + * Convert types. + */ +#define FLD 36 +#define SCONV 37 +#define PCONV 38 +#define PMCONV 39 +#define PVCONV 40 + +/* + * Function calls. + */ +#define CALL 41 +#define UCALL 42 +#define FORTCALL 43 +#define UFORTCALL 44 +#define STCALL 45 +#define USTCALL 46 + +/* + * Other used nodes. + */ +#define CCODES 47 +#define CM 48 +#define ASSIGN 49 +#define STASG 50 +#define STARG 51 +#define FORCE 52 +/* #define INIT 53 */ +#define GOTO 54 +#define RETURN 55 +#define STREF 56 +#define FUNARG 57 +#define ADDROF 58 + +#define MAXOP 58 diff --git a/usr.bin/pcc/mip/optim2.c b/usr.bin/pcc/mip/optim2.c new file mode 100644 index 00000000000..fcf367eb412 --- /dev/null +++ b/usr.bin/pcc/mip/optim2.c @@ -0,0 +1,882 @@ +/* $Id: optim2.c,v 1.1 2007/09/15 18:12:36 otto Exp $ */ +/* + * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se). + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "pass2.h" + +#include <string.h> +#include <stdlib.h> + +#ifndef MIN +#define MIN(a,b) (((a)<(b))?(a):(b)) +#endif + +#ifndef MAX +#define MAX(a,b) (((a) > (b)) ? (a) : (b)) +#endif + +#define BDEBUG(x) if (b2debug) printf x + +static int dfsnum; + +void saveip(struct interpass *ip); +void deljumps(struct interpass *); +void optdump(struct interpass *ip); +void printip(struct interpass *pole); + +static struct varinfo defsites; +struct interpass *storesave; +static struct interpass_prolog *ipp, *epp; /* prolog/epilog */ + +void bblocks_build(struct interpass *, struct labelinfo *, struct bblockinfo *); +void cfg_build(struct labelinfo *labinfo); +void cfg_dfs(struct basicblock *bb, unsigned int parent, + struct bblockinfo *bbinfo); +void dominators(struct bblockinfo *bbinfo); +struct basicblock * +ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo); +void link(struct basicblock *parent, struct basicblock *child); +void computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo); +void findTemps(struct interpass *ip); +void placePhiFunctions(struct bblockinfo *bbinfo); +void remunreach(void); + +struct basicblock bblocks; +int nbblocks; +static struct interpass *cvpole; + +struct addrof { + struct addrof *next; + int tempnum; + int oregoff; +} *otlink; + +static int +getoff(int num) +{ + struct addrof *w; + + for (w = otlink; w; w = w->next) + if (w->tempnum == num) + return w->oregoff; + return 0; +} + +/* + * Use stack argument addresses instead of copying if & is used on a var. + */ +static int +setargs(int tval, struct addrof *w) +{ + struct interpass *ip; + NODE *p; + + ip = DLIST_NEXT(cvpole, qelem); /* PROLOG */ + ip = DLIST_NEXT(ip, qelem); /* first DEFLAB */ + ip = DLIST_NEXT(ip, qelem); /* first NODE */ + for (; ip->type != IP_DEFLAB; ip = DLIST_NEXT(ip, qelem)) { + p = ip->ip_node; +#ifdef PCC_DEBUG + if (p->n_op != ASSIGN || p->n_left->n_op != TEMP) + comperr("temparg"); +#endif + if (p->n_right->n_op != OREG) + continue; /* arg in register */ + if (tval != p->n_left->n_lval) + continue; /* wrong assign */ + w->oregoff = p->n_right->n_lval; + tfree(p); + DLIST_REMOVE(ip, qelem); + return 1; + } + return 0; +} + +/* + * Search for ADDROF elements and, if found, record them. + */ +static void +findaddrof(NODE *p) +{ + struct addrof *w; + + if (p->n_op != ADDROF) + return; + if (getoff(p->n_left->n_lval)) + return; + w = tmpalloc(sizeof(struct addrof)); + w->tempnum = p->n_left->n_lval; + if (setargs(p->n_left->n_lval, w) == 0) + w->oregoff = BITOOR(freetemp(szty(p->n_left->n_type))); + w->next = otlink; + otlink = w; +} + + +/* + * Convert address-taken temps to OREGs. + */ +static void +cvtaddrof(NODE *p) +{ + NODE *l; + int n; + + if (p->n_op != ADDROF && p->n_op != TEMP) + return; + if (p->n_op == TEMP) { + n = getoff(p->n_lval); + if (n == 0) + return; + p->n_op = OREG; + p->n_lval = n; + p->n_rval = FPREG; + } else { + l = p->n_left; + l->n_type = p->n_type; + p->n_right = mklnode(ICON, l->n_lval, 0, l->n_type); + p->n_op = PLUS; + l->n_op = REG; + l->n_lval = 0; + l->n_rval = FPREG; + + } +} + +void +optimize(struct interpass *ipole) +{ + struct interpass *ip; + struct labelinfo labinfo; + struct bblockinfo bbinfo; + + ipp = (struct interpass_prolog *)DLIST_NEXT(ipole, qelem); + epp = (struct interpass_prolog *)DLIST_PREV(ipole, qelem); + + if (b2debug) { + printf("initial links\n"); + printip(ipole); + } + + /* + * Convert ADDROF TEMP to OREGs. + */ + if (xtemps) { + otlink = NULL; + cvpole = ipole; + DLIST_FOREACH(ip, ipole, qelem) { + if (ip->type != IP_NODE) + continue; + walkf(ip->ip_node, findaddrof); + } + if (otlink) { + DLIST_FOREACH(ip, ipole, qelem) { + if (ip->type != IP_NODE) + continue; + walkf(ip->ip_node, cvtaddrof); + } + } + } + + if (xdeljumps) + deljumps(ipole); /* Delete redundant jumps and dead code */ + +#ifdef PCC_DEBUG + if (b2debug) { + printf("links after deljumps\n"); + printip(ipole); + } +#endif + if (xssaflag || xtemps) { + DLIST_INIT(&bblocks, bbelem); + bblocks_build(ipole, &labinfo, &bbinfo); + BDEBUG(("Calling cfg_build\n")); + cfg_build(&labinfo); + } + if (xssaflag) { + BDEBUG(("Calling dominators\n")); + dominators(&bbinfo); + BDEBUG(("Calling computeDF\n")); + computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo); + BDEBUG(("Calling remunreach\n")); + remunreach(); +#if 0 + dfg = dfg_build(cfg); + ssa = ssa_build(cfg, dfg); +#endif + } + +#ifdef PCC_DEBUG + if (epp->ipp_regs != 0) + comperr("register error"); +#endif + +#ifdef MYOPTIM + myoptim((struct interpass *)ipp); +#endif +} + +/* + * Delete unused labels, excess of labels, gotos to gotos. + * This routine can be made much more efficient. + */ +void +deljumps(struct interpass *ipole) +{ + struct interpass *ip, *n, *ip2; + int gotone,low, high; + int *lblary, sz, o, i; + + low = ipp->ip_lblnum; + high = epp->ip_lblnum; + +#ifdef notyet + mark = tmpmark(); /* temporary used memory */ +#endif + + sz = (high-low) * sizeof(int); + lblary = tmpalloc(sz); + +again: gotone = 0; + memset(lblary, 0, sz); + + /* refcount and coalesce all labels */ + DLIST_FOREACH(ip, ipole, qelem) { + if (ip->type == IP_DEFLAB) { + n = DLIST_NEXT(ip, qelem); + while (n->type == IP_DEFLAB) { + if (n->type == IP_DEFLAB && + lblary[n->ip_lbl-low] >= 0) + lblary[n->ip_lbl-low] = -ip->ip_lbl; + n = DLIST_NEXT(n, qelem); + } + } + if (ip->type != IP_NODE) + continue; + o = ip->ip_node->n_op; + if (o == GOTO) + i = ip->ip_node->n_left->n_lval; + else if (o == CBRANCH) + i = ip->ip_node->n_right->n_lval; + else + continue; + lblary[i-low] |= 1; + } + + /* delete coalesced/unused labels and rename gotos */ + DLIST_FOREACH(ip, ipole, qelem) { + n = DLIST_NEXT(ip, qelem); + if (n->type == IP_DEFLAB) { + if (lblary[n->ip_lbl-low] <= 0) { + DLIST_REMOVE(n, qelem); + gotone = 1; + } + continue; + } + if (n->type != IP_NODE) + continue; + o = n->ip_node->n_op; + if (o == GOTO) + i = n->ip_node->n_left->n_lval; + else if (o == CBRANCH) + i = n->ip_node->n_right->n_lval; + else + continue; + if (lblary[i-low] < 0) { + if (o == GOTO) + n->ip_node->n_left->n_lval = -lblary[i-low]; + else + n->ip_node->n_right->n_lval = -lblary[i-low]; + } + } + + /* Delete gotos to the next statement */ + DLIST_FOREACH(ip, ipole, qelem) { + n = DLIST_NEXT(ip, qelem); + if (n->type != IP_NODE) + continue; + o = n->ip_node->n_op; + if (o == GOTO) + i = n->ip_node->n_left->n_lval; + else if (o == CBRANCH) + i = n->ip_node->n_right->n_lval; + else + continue; + + ip2 = n; + ip2 = DLIST_NEXT(ip2, qelem); + + if (ip2->type != IP_DEFLAB) + continue; + if (ip2->ip_lbl == i) { + tfree(n->ip_node); + DLIST_REMOVE(n, qelem); + gotone = 1; + } + } + + if (gotone) + goto again; + +#ifdef notyet + tmpfree(mark); +#endif +} + +void +optdump(struct interpass *ip) +{ + static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr", + "deflab", "defnam", "asm" }; + printf("type %s\n", nm[ip->type-1]); + switch (ip->type) { + case IP_NODE: + fwalk(ip->ip_node, e2print, 0); + break; + case IP_DEFLAB: + printf("label " LABFMT "\n", ip->ip_lbl); + break; + case IP_ASM: + printf(": %s\n", ip->ip_asm); + break; + } +} + +/* + * Build the basic blocks, algorithm 9.1, pp 529 in Compilers. + * + * Also fills the labelinfo struct with information about which bblocks + * that contain which label. + */ + +void +bblocks_build(struct interpass *ipole, struct labelinfo *labinfo, + struct bblockinfo *bbinfo) +{ + struct interpass *ip; + struct basicblock *bb = NULL; + int low, high; + int count = 0; + int i; + + BDEBUG(("bblocks_build (%p, %p)\n", labinfo, bbinfo)); + low = ipp->ip_lblnum; + high = epp->ip_lblnum; + + /* + * First statement is a leader. + * Any statement that is target of a jump is a leader. + * Any statement that immediately follows a jump is a leader. + */ + DLIST_FOREACH(ip, ipole, qelem) { + if (bb == NULL || (ip->type == IP_EPILOG) || + (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) { + bb = tmpalloc(sizeof(struct basicblock)); + bb->first = ip; + SLIST_INIT(&bb->children); + SLIST_INIT(&bb->parents); + bb->dfnum = 0; + bb->dfparent = 0; + bb->semi = 0; + bb->ancestor = 0; + bb->idom = 0; + bb->samedom = 0; + bb->bucket = NULL; + bb->df = NULL; + bb->dfchildren = NULL; + bb->Aorig = NULL; + bb->Aphi = NULL; + bb->bbnum = count; + DLIST_INSERT_BEFORE(&bblocks, bb, bbelem); + count++; + } + bb->last = ip; + if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || + ip->ip_node->n_op == CBRANCH)) + bb = NULL; + if (ip->type == IP_PROLOG) + bb = NULL; + } + nbblocks = count; + + if (b2debug) { + printf("Basic blocks in func: %d, low %d, high %d\n", + count, low, high); + DLIST_FOREACH(bb, &bblocks, bbelem) { + printf("bb %p: first %p last %p\n", bb, + bb->first, bb->last); + } + } + + labinfo->low = low; + labinfo->size = high - low + 1; + labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *)); + for (i = 0; i < labinfo->size; i++) { + labinfo->arr[i] = NULL; + } + + bbinfo->size = count + 1; + bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *)); + for (i = 0; i < bbinfo->size; i++) { + bbinfo->arr[i] = NULL; + } + + /* Build the label table */ + DLIST_FOREACH(bb, &bblocks, bbelem) { + if (bb->first->type == IP_DEFLAB) + labinfo->arr[bb->first->ip_lbl - low] = bb; + } + + if (b2debug) { + printf("Label table:\n"); + for (i = 0; i < labinfo->size; i++) + if (labinfo->arr[i]) + printf("Label %d bblock %p\n", i+low, + labinfo->arr[i]); + } +} + +/* + * Build the control flow graph. + */ + +void +cfg_build(struct labelinfo *labinfo) +{ + /* Child and parent nodes */ + struct cfgnode *cnode; + struct cfgnode *pnode; + struct basicblock *bb; + + DLIST_FOREACH(bb, &bblocks, bbelem) { + + if (bb->first->type == IP_EPILOG) { + break; + } + + cnode = tmpalloc(sizeof(struct cfgnode)); + pnode = tmpalloc(sizeof(struct cfgnode)); + pnode->bblock = bb; + + if ((bb->last->type == IP_NODE) && + (bb->last->ip_node->n_op == GOTO)) { + if (bb->last->ip_node->n_left->n_lval - labinfo->low > + labinfo->size) { + comperr("Label out of range: %d, base %d", + bb->last->ip_node->n_left->n_lval, + labinfo->low); + } + cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low]; + SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); + SLIST_INSERT_LAST(&bb->children, cnode, cfgelem); + continue; + } + if ((bb->last->type == IP_NODE) && + (bb->last->ip_node->n_op == CBRANCH)) { + if (bb->last->ip_node->n_right->n_lval - labinfo->low > + labinfo->size) + comperr("Label out of range: %d", + bb->last->ip_node->n_left->n_lval); + + cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low]; + SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); + SLIST_INSERT_LAST(&bb->children, cnode, cfgelem); + cnode = tmpalloc(sizeof(struct cfgnode)); + pnode = tmpalloc(sizeof(struct cfgnode)); + pnode->bblock = bb; + } + + cnode->bblock = DLIST_NEXT(bb, bbelem); + SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem); + SLIST_INSERT_LAST(&bb->children, cnode, cfgelem); + } +} + +void +cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo) +{ + struct cfgnode *cnode; + + if (bb->dfnum != 0) + return; + + bb->dfnum = ++dfsnum; + bb->dfparent = parent; + bbinfo->arr[bb->dfnum] = bb; + SLIST_FOREACH(cnode, &bb->children, cfgelem) { + cfg_dfs(cnode->bblock, bb->dfnum, bbinfo); + } + /* Don't bring in unreachable nodes in the future */ + bbinfo->size = dfsnum + 1; +} + +static bittype * +setalloc(int nelem) +{ + bittype *b; + int sz = (nelem+NUMBITS-1)/NUMBITS; + + b = tmpalloc(sz * sizeof(bittype)); + memset(b, 0, sz * sizeof(bittype)); + return b; +} + +/* + * Algorithm 19.9, pp 414 from Appel. + */ + +void +dominators(struct bblockinfo *bbinfo) +{ + struct cfgnode *cnode; + struct basicblock *bb, *y, *v; + struct basicblock *s, *sprime, *p; + int h, i; + + DLIST_FOREACH(bb, &bblocks, bbelem) { + bb->bucket = setalloc(bbinfo->size); + bb->df = setalloc(bbinfo->size); + bb->dfchildren = setalloc(bbinfo->size); + } + + dfsnum = 0; + cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo); + + if (b2debug) { + struct basicblock *bbb; + struct cfgnode *ccnode; + + DLIST_FOREACH(bbb, &bblocks, bbelem) { + printf("Basic block %d, parents: ", bbb->dfnum); + SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) { + printf("%d, ", ccnode->bblock->dfnum); + } + printf("\nChildren: "); + SLIST_FOREACH(ccnode, &bbb->children, cfgelem) { + printf("%d, ", ccnode->bblock->dfnum); + } + printf("\n"); + } + } + + for(h = bbinfo->size - 1; h > 1; h--) { + bb = bbinfo->arr[h]; + p = s = bbinfo->arr[bb->dfparent]; + SLIST_FOREACH(cnode, &bb->parents, cfgelem) { + if (cnode->bblock->dfnum <= bb->dfnum) + sprime = cnode->bblock; + else + sprime = bbinfo->arr[ancestorwithlowestsemi + (cnode->bblock, bbinfo)->semi]; + if (sprime->dfnum < s->dfnum) + s = sprime; + } + bb->semi = s->dfnum; + BITSET(s->bucket, bb->dfnum); + link(p, bb); + for (i = 1; i < bbinfo->size; i++) { + if(TESTBIT(p->bucket, i)) { + v = bbinfo->arr[i]; + y = ancestorwithlowestsemi(v, bbinfo); + if (y->semi == v->semi) + v->idom = p->dfnum; + else + v->samedom = y->dfnum; + } + } + memset(p->bucket, 0, (bbinfo->size + 7)/8); + } + + if (b2debug) { + printf("Num\tSemi\tAncest\tidom\n"); + DLIST_FOREACH(bb, &bblocks, bbelem) { + printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi, + bb->ancestor, bb->idom); + } + } + + for(h = 2; h < bbinfo->size; h++) { + bb = bbinfo->arr[h]; + if (bb->samedom != 0) { + bb->idom = bbinfo->arr[bb->samedom]->idom; + } + } + DLIST_FOREACH(bb, &bblocks, bbelem) { + if (bb->idom != 0 && bb->idom != bb->dfnum) { + BDEBUG(("Setting child %d of %d\n", + bb->dfnum, bbinfo->arr[bb->idom]->dfnum)); + BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum); + } + } +} + + +struct basicblock * +ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo) +{ + struct basicblock *u = bblock; + struct basicblock *v = bblock; + + while (v->ancestor != 0) { + if (bbinfo->arr[v->semi]->dfnum < + bbinfo->arr[u->semi]->dfnum) + u = v; + v = bbinfo->arr[v->ancestor]; + } + return u; +} + +void +link(struct basicblock *parent, struct basicblock *child) +{ + child->ancestor = parent->dfnum; +} + +void +computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo) +{ + struct cfgnode *cnode; + int h, i; + + SLIST_FOREACH(cnode, &bblock->children, cfgelem) { + if (cnode->bblock->idom != bblock->dfnum) + BITSET(bblock->df, cnode->bblock->dfnum); + } + for (h = 1; h < bbinfo->size; h++) { + if (!TESTBIT(bblock->dfchildren, h)) + continue; + computeDF(bbinfo->arr[h], bbinfo); + for (i = 1; i < bbinfo->size; i++) { + if (TESTBIT(bbinfo->arr[h]->df, i) && + (bbinfo->arr[h] == bblock || + (bblock->idom != bbinfo->arr[h]->dfnum))) + BITSET(bblock->df, i); + } + } +} + +static struct basicblock *currbb; +static struct interpass *currip; + +/* Helper function for findTemps, Find assignment nodes. */ +static void +searchasg(NODE *p) +{ + struct pvarinfo *pv; + + if (p->n_op != ASSIGN) + return; + + if (p->n_left->n_op != TEMP) + return; + + pv = tmpcalloc(sizeof(struct pvarinfo)); + pv->next = defsites.arr[p->n_left->n_lval]; + pv->bb = currbb; + pv->top = currip->ip_node; + pv->n = p->n_left; + BITSET(currbb->Aorig, p->n_left->n_lval); + + defsites.arr[p->n_left->n_lval] = pv; +} + +/* Walk the interpass looking for assignment nodes. */ +void findTemps(struct interpass *ip) +{ + if (ip->type != IP_NODE) + return; + + currip = ip; + + walkf(ip->ip_node, searchasg); +} + +/* + * Algorithm 19.6 from Appel. + */ + +void +placePhiFunctions(struct bblockinfo *bbinfo) +{ + struct basicblock *bb; + struct interpass *ip; + int maxtmp, i, j, k, l; + struct pvarinfo *n; + struct cfgnode *cnode; + TWORD ntype; + NODE *p; + struct pvarinfo *pv; + + bb = DLIST_NEXT(&bblocks, bbelem); + defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum; + bb = DLIST_PREV(&bblocks, bbelem); + maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum; + defsites.size = maxtmp - defsites.low + 1; + defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *)); + + /* Find all defsites */ + DLIST_FOREACH(bb, &bblocks, bbelem) { + currbb = bb; + ip = bb->first; + bb->Aorig = setalloc(defsites.size); + bb->Aphi = setalloc(defsites.size); + + + while (ip != bb->last) { + findTemps(ip); + ip = DLIST_NEXT(ip, qelem); + } + /* Make sure we get the last statement in the bblock */ + findTemps(ip); + } + /* For each variable */ + for (i = defsites.low; i < defsites.size; i++) { + /* While W not empty */ + while (defsites.arr[i] != NULL) { + /* Remove some node n from W */ + n = defsites.arr[i]; + defsites.arr[i] = n->next; + /* For each y in n->bb->df */ + for (j = 0; j < bbinfo->size; j++) { + if (!TESTBIT(n->bb->df, j)) + continue; + + if (TESTBIT(bbinfo->arr[j]->Aphi, i)) + continue; + + ntype = n->n->n_type; + k = 0; + /* Amount of predecessors for y */ + SLIST_FOREACH(cnode, &n->bb->parents, cfgelem) + k++; + /* Construct phi(...) */ + p = mklnode(TEMP, i, 0, ntype); + for (l = 0; l < k-1; l++) + p = mkbinode(PHI, p, + mklnode(TEMP, i, 0, ntype), ntype); + ip = ipnode(mkbinode(ASSIGN, + mklnode(TEMP, i, 0, ntype), p, ntype)); + /* Insert phi at top of basic block */ + DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem); + n->bb->first = ip; + BITSET(bbinfo->arr[j]->Aphi, i); + if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) { + pv = tmpalloc(sizeof(struct pvarinfo)); + // XXXpj Ej fullständig information. + pv->bb = bbinfo->arr[j]; + pv->next = defsites.arr[i]->next; + defsites.arr[i] = pv; + } + + + } + } + } +} + +/* + * Remove unreachable nodes in the CFG. + */ + +void +remunreach(void) +{ + struct basicblock *bb, *nbb; + struct interpass *next, *ctree; + + bb = DLIST_NEXT(&bblocks, bbelem); + while (bb != &bblocks) { + nbb = DLIST_NEXT(bb, bbelem); + + /* Code with dfnum 0 is unreachable */ + if (bb->dfnum != 0) { + bb = nbb; + continue; + } + + /* Need the epilogue node for other parts of the + compiler, set its label to 0 and backend will + handle it. */ + if (bb->first->type == IP_EPILOG) { + bb->first->ip_lbl = 0; + bb = nbb; + continue; + } + + next = bb->first; + do { + ctree = next; + next = DLIST_NEXT(ctree, qelem); + + if (ctree->type == IP_NODE) + tfree(ctree->ip_node); + DLIST_REMOVE(ctree, qelem); + } while (ctree != bb->last); + + DLIST_REMOVE(bb, bbelem); + bb = nbb; + } +} + +void +printip(struct interpass *pole) +{ + static char *foo[] = { + 0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" }; + struct interpass *ip; + struct interpass_prolog *ipp, *epp; + + DLIST_FOREACH(ip, pole, qelem) { + if (ip->type > MAXIP) + printf("IP(%d) (%p): ", ip->type, ip); + else + printf("%s (%p): ", foo[ip->type], ip); + switch (ip->type) { + case IP_NODE: printf("\n"); + fwalk(ip->ip_node, e2print, 0); break; + case IP_PROLOG: + ipp = (struct interpass_prolog *)ip; + printf("%s %s regs %x autos %d mintemp %d minlbl %d\n", + ipp->ipp_name, ipp->ipp_vis ? "(local)" : "", + ipp->ipp_regs, ipp->ipp_autos, ipp->ip_tmpnum, + ipp->ip_lblnum); + break; + case IP_EPILOG: + epp = (struct interpass_prolog *)ip; + printf("%s %s regs %x autos %d mintemp %d minlbl %d\n", + epp->ipp_name, epp->ipp_vis ? "(local)" : "", + epp->ipp_regs, epp->ipp_autos, epp->ip_tmpnum, + epp->ip_lblnum); + break; + case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break; + case IP_DEFNAM: printf("\n"); break; + case IP_ASM: printf("%s\n", ip->ip_asm); break; + default: + break; + } + } +} diff --git a/usr.bin/pcc/mip/pass2.h b/usr.bin/pcc/mip/pass2.h new file mode 100644 index 00000000000..35ccb7f4220 --- /dev/null +++ b/usr.bin/pcc/mip/pass2.h @@ -0,0 +1,418 @@ +/* $Id: pass2.h,v 1.1 2007/09/15 18:12:36 otto Exp $ */ +/* + * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code and documentation must retain the above + * copyright notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditionsand the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed or owned by Caldera + * International, Inc. + * Neither the name of Caldera International, Inc. nor the names of other + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA + * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE + * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include <sys/types.h> + +#include "manifest.h" +#include "protos.h" +#ifndef MKEXT +#include "external.h" +#else +typedef int bittype; /* XXX - for basicblock */ +#endif + +/* cookies, used as arguments to codgen */ +#define FOREFF 01 /* compute for effects only */ +#define INAREG 02 /* compute into a register */ +#define INBREG 04 /* compute into a register */ +#define INCREG 010 /* compute into a register */ +#define INDREG 020 /* compute into a register */ +#define INREGS (INAREG|INBREG|INCREG|INDREG) +#define FORCC 040 /* compute for condition codes only */ +#define INTEMP 010000 /* compute into a temporary location */ +#define FORREW 040000 /* search the table for a rewrite rule */ + +/* + * OP descriptors, + * the ASG operator may be used on some of these + */ +#define OPSIMP 010000 /* +, -, &, |, ^ */ +#define OPCOMM 010002 /* +, &, |, ^ */ +#define OPMUL 010004 /* *, / */ +#define OPDIV 010006 /* /, % */ +#define OPUNARY 010010 /* unary ops */ +#define OPLEAF 010012 /* leaves */ +#define OPANY 010014 /* any op... */ +#define OPLOG 010016 /* logical ops */ +#define OPFLOAT 010020 /* +, -, *, or / (for floats) */ +#define OPSHFT 010022 /* <<, >> */ +#define OPLTYPE 010024 /* leaf type nodes (e.g, NAME, ICON, etc.) */ + +/* shapes */ +#define SANY 01 /* same as FOREFF */ +#define SAREG 02 /* same as INAREG */ +#define SBREG 04 /* same as INBREG */ +#define SCREG 010 /* same as INCREG */ +#define SDREG 020 /* same as INDREG */ +#define SCC 040 /* same as FORCC */ +#define SNAME 0100 +#define SCON 0200 +#define SFLD 0400 +#define SOREG 01000 +#define STARNM 02000 +#define STARREG 04000 +#define SWADD 040000 +#define SPECIAL 0100000 +#define SZERO SPECIAL +#define SONE (SPECIAL|1) +#define SMONE (SPECIAL|2) +#define SCCON (SPECIAL|3) /* -256 <= constant < 256 */ +#define SSCON (SPECIAL|4) /* -32768 <= constant < 32768 */ +#define SSOREG (SPECIAL|5) /* non-indexed OREG */ +#define MAXSPECIAL (SPECIAL|5) + +/* These are used in rstatus[] in conjunction with SxREG */ +#define TEMPREG 0100 +#define PERMREG 0200 + +/* tshape() return values */ +#define SRNOPE 0 /* Cannot match any shape */ +#define SRDIR 1 /* Direct match */ +#define SROREG 2 /* Can convert into OREG */ +#define SRREG 3 /* Must put into REG */ + +/* find*() return values */ +#define FRETRY -2 +#define FFAIL -1 + +/* INTEMP is carefully not conflicting with shapes */ + +/* types */ +#define TCHAR 01 /* char */ +#define TSHORT 02 /* short */ +#define TINT 04 /* int */ +#define TLONG 010 /* long */ +#define TFLOAT 020 /* float */ +#define TDOUBLE 040 /* double */ +#define TPOINT 0100 /* pointer to something */ +#define TUCHAR 0200 /* unsigned char */ +#define TUSHORT 0400 /* unsigned short */ +#define TUNSIGNED 01000 /* unsigned int */ +#define TULONG 02000 /* unsigned long */ +#define TPTRTO 04000 /* pointer to one of the above */ +#define TANY 010000 /* matches anything within reason */ +#define TSTRUCT 020000 /* structure or union */ +#define TLONGLONG 040000 /* long long */ +#define TULONGLONG 0100000 /* unsigned long long */ +#define TLDOUBLE 0200000 /* long double; exceeds 16 bit */ +#define TFTN 0400000 /* function pointer; exceeds 16 bit */ + +/* reclamation cookies */ +#define RNULL 0 /* clobber result */ +#define RLEFT 01 +#define RRIGHT 02 +#define RESC1 04 +#define RESC2 010 +#define RESC3 020 +#define RDEST 040 +#define RESCC 04000 +#define RNOP 010000 /* DANGER: can cause loops.. */ + +/* needs */ +#define NAREG 0000001 +#define NACOUNT 0000003 +#define NAMASK 0000017 +#define NASL 0000004 /* may share left register */ +#define NASR 0000010 /* may share right register */ +#define NBREG 0000020 +#define NBCOUNT 0000060 +#define NBMASK 0000360 +#define NBSL 0000100 +#define NBSR 0000200 +#define NTEMP 0000400 +#define NTMASK 0001400 +#define NSPECIAL 0040000 /* need special register treatment */ +#define REWRITE 0100000 +#define NCSL 0x10000 /* Above 16 bit */ +#define NCSR 0x20000 /* Above 16 bit */ +#define NCREG 0x40000 /* Above 16 bit */ +#define NCCOUNT 0xc0000 +#define NDSL 0x100000 /* Above 16 bit */ +#define NDSR 0x200000 /* Above 16 bit */ +#define NDREG 0x400000 /* Above 16 bit */ +#define NDCOUNT 0xc00000 + +/* special treatment */ +#define NLEFT (0001) /* left leg register (moveadd) */ +#define NOLEFT (0002) /* avoid regs for left (addedge) */ +#define NRIGHT (0004) /* right leg register */ +#define NORIGHT (0010) /* avoid reg for right */ +#define NEVER (0020) /* registers trashed (addalledges) */ +#define NRES (0040) /* result register (moveadd) */ +#define NMOVTO (0100) /* move between classes */ + + +#define MUSTDO 010000 /* force register requirements */ +#define NOPREF 020000 /* no preference for register assignment */ + +#define isreg(p) (p->n_op == REG || p->n_op == TEMP) + +#define TBUSY 01000 + +#define SETSTO(x,y) (stotree = (x), stocook = (y)) +extern int stocook; + +extern NODE *stotree; +extern int callflag; + +extern int fregs; + +/* code tables */ +extern struct optab { + int op; + int visit; + int lshape; + int ltype; + int rshape; + int rtype; + int needs; + int rewrite; + char *cstring; +} table[]; + +/* Special needs for register allocations */ +struct rspecial { + int op, num; +#if 0 + int left; /* left leg register */ + int noleft; /* avoid regs for left */ + int right; /* right leg register */ + int noright; /* avoid right leg register */ + int *rmask; /* array of destroyed registers */ + int res; /* Result ends up here */ +// void (*rew)(struct optab *, NODE *); /* special rewrite */ +#endif +}; + +extern NODE resc[]; + +extern int p2autooff, p2maxautooff; + +extern NODE + *talloc(void), + *eread(void), + *tcopy(NODE *), + *mklnode(int, CONSZ, int, TWORD), + *mkbinode(int, NODE *, NODE *, TWORD), + *mkunode(int, NODE *, int, TWORD), + *getlr(NODE *p, int); + +void eoftn(struct interpass_prolog *); +void prologue(struct interpass_prolog *); +void setlocc(int locctr); +void e2print(NODE *p, int down, int *a, int *b); +void myoptim(struct interpass *); +void cbgen(int op, int label); +struct optab *nxtmatch(struct optab *); +int chkmatch(NODE *, int, int, int); +int match(NODE *p, int cookie); +int nmatch(NODE *p, int what); +#ifndef special +int special(NODE *, int); +#endif +int setasg(NODE *, int); +int setuni(NODE *, int); +int sucomp(NODE *); +int nsucomp(NODE *); +int setorder(NODE *); +int geninsn(NODE *, int cookie); +void adrput(FILE *, NODE *); +void comperr(char *str, ...); +void genregs(NODE *p); +void ngenregs(struct interpass *); +NODE *store(NODE *); +void gencall(NODE *, NODE *prev); +struct interpass *ipnode(NODE *); +void deflab(int); +void rmove(int, int, TWORD); +int rspecial(struct optab *, int); +struct rspecial *nspecial(struct optab *q); +void printip(struct interpass *pole); +int findops(NODE *p, int); +int findasg(NODE *p, int); +int finduni(NODE *p, int); +int findumul(NODE *p, int); +int findleaf(NODE *p, int); +int relops(NODE *p); +void offstar(NODE *p, int shape); +int gclass(TWORD); +void lastcall(NODE *); +void myreader(struct interpass *pole); +int oregok(NODE *p, int sharp); +void myormake(NODE *); + +char *prcook(int); + +void conput(FILE *, NODE *); + +extern char *rnames[]; +extern int rstatus[]; +extern int roverlap[MAXREGS][MAXREGS]; + +extern int classmask(int), tclassmask(int); +extern void cmapinit(void); +extern int aliasmap(int adjclass, int regnum); +extern int regK[]; +#define CLASSA 1 +#define CLASSB 2 +#define CLASSC 3 +#define CLASSD 4 +#define CLASSE 5 + +/* routines to handle double indirection */ +#ifdef R2REGS +void makeor2(NODE *p, NODE *q, int, int); +int base(NODE *); +int offset(NODE *p, int); +#endif + +extern int lineno; +extern int fldshf, fldsz; +extern int lflag, x2debug, udebug, e2debug, odebug, mdebug; +extern int rdebug, radebug, t2debug, s2debug, b2debug, c2debug; +extern int kflag; +#ifdef FORT +extern int Oflag; +#endif + +#ifndef callchk +#define callchk(x) allchk() +#endif + +#ifndef PUTCHAR +#define PUTCHAR(x) putchar(x) +#endif + +#define optype(o) (dope[o]&TYFLG) +#define asgop(o) (dope[o]&ASGFLG) +#define logop(o) (dope[o]&LOGFLG) +#define callop(o) (dope[o]&CALLFLG) +extern int dope[]; /* a vector containing operator information */ +extern char *opst[]; /* a vector containing names for ops */ + + /* macros for doing double indexing */ +#define R2PACK(x,y,z) (0200*((x)+1)+y+040000*z) +#define R2UPK1(x) ((((x)>>7)-1)&0177) +#define R2UPK2(x) ((x)&0177) +#define R2UPK3(x) (x>>14) +#define R2TEST(x) ((x)>=0200) + +/* + * Layout of findops() return value: + * bit 0-1 where to store left node. + * bit 2-3 where to store right node. + * bit 4 set if right leg should be evaluated first + * bit 5- table index + * + * LOREG means: walk down left node, after code emission call canon() to + * convert the tree to an OREG. + */ +#define LREG 001 +#define LOREG 002 +#define LTEMP 003 +#define LDIR 003 +#define LMASK 003 +#define RREG 004 +#define ROREG 010 +#define RTEMP 014 +#define RDIR 014 +#define RMASK 014 +#define DORIGHT 020 +#define SCLASS(v,x) ((v) |= ((x) << 5)) +#define TCLASS(x) (((x) >> 5) & 7) +#define TBSH 8 +#define TBLIDX(idx) ((idx) >> TBSH) +#define MKIDX(tbl,mod) (((tbl) << TBSH) | (mod)) + +#ifndef BREGS +#define BREGS 0 +#define TBREGS 0 +#endif +#define REGBIT(x) (1 << (x)) + +void emit(struct interpass *); +void optimize(struct interpass *); + +struct basicblock { + DLIST_ENTRY(basicblock) bbelem; + SLIST_HEAD(, cfgnode) children; /* CFG - children to this node */ + SLIST_HEAD(, cfgnode) parents; /* CFG - parents to this node */ + int bbnum; /* this basic block number */ + unsigned int dfnum; /* DFS-number */ + unsigned int dfparent; /* Parent in DFS */ + unsigned int semi; + unsigned int ancestor; + unsigned int idom; + unsigned int samedom; + bittype *bucket; + bittype *df; + bittype *dfchildren; + bittype *Aorig; + bittype *Aphi; + struct interpass *first; /* first element of basic block */ + struct interpass *last; /* last element of basic block */ +}; + +struct labelinfo { + struct basicblock **arr; + unsigned int size; + unsigned int low; +}; + +struct bblockinfo { + unsigned int size; + struct basicblock **arr; +}; + +struct varinfo { + struct pvarinfo **arr; + int size; + int low; +}; + +struct pvarinfo { + struct pvarinfo *next; + struct basicblock *bb; + NODE *top, *n; +}; + +struct cfgnode { + SLIST_ENTRY(cfgnode) cfgelem; + struct basicblock *bblock; +}; + +/* + * C compiler second pass extra defines. + */ +#define PHI (MAXOP + 1) /* Used in SSA trees */ diff --git a/usr.bin/pcc/mip/protos.h b/usr.bin/pcc/mip/protos.h new file mode 100644 index 00000000000..a0a436fdd45 --- /dev/null +++ b/usr.bin/pcc/mip/protos.h @@ -0,0 +1,83 @@ + +struct optab; +struct symtab; +struct sw; + +void cerror(char *s, ...); +void werror(char *s, ...); +void uerror(char *s, ...); +void reclaim(NODE *p, int, int); +void walkf(NODE *, void (*f)(NODE *)); +void allchk(void); +void tfree(NODE *); +int tshape(NODE *, int); +void prtdcon(NODE *p); +void tinit(void); +void tcheck(void); +void mkdope(void); +int tshape(NODE *p, int shape); +int shtemp(NODE *p); +int flshape(NODE *p); +int shumul(NODE *p); +int ttype(TWORD t, int tword); +void expand(NODE *, int, char *); +void hopcode(int, int); +void adrcon(CONSZ); +void zzzcode(NODE *, int); +void insput(NODE *); +void upput(NODE *, int); +void econvert(NODE *); +int andable(NODE *); +int conval(NODE *, int, NODE *); +int ispow2(CONSZ); +void defid(NODE *q, int class); +int getlab(void); +void ftnend(void); +void efcode(void); +void dclargs(void); +void fixarg(struct symtab *); +void cendarg(void); +void defalign(int); +int fldal(unsigned int); +void vfdzero(int); +void zecode(int); +void putbyte(int v); +void ecomp(NODE *p); +void cinit(NODE *, int); +void bccode(void); +int upoff(int size, int alignment, int *poff); +void fldty(struct symtab *p); +void nidcl(NODE *p, int class); +int noinit(void); +void eprint(NODE *, int, int *, int *); +int uclass(int class); +int fixclass(int, TWORD type); +void lineid(int, char *); +void mycanon(NODE *); +void delay(NODE *); +int delay1(NODE *); +void delay2(NODE *); +void setregs(void); +int autoincr(NODE *); +int deltest(NODE *); +void canon(NODE *); +void order(NODE *, int); +int tlen(NODE *p); +int setincr(NODE *); +int setbin(NODE *); +void stoarg(NODE *p, int); +void constore(NODE *); +void markcall(NODE *); +void oreg2(NODE *p); +int notoff(TWORD, int, CONSZ, char *); +void bycode(int, int); +void pstab(char *, int); +void psline(void); +int notlval(NODE *); +int icons(NODE *); +void ecode(NODE *p); +int yylex(void); +void yyerror(char *s); +void p2tree(NODE *p); +int rewfld(NODE *p); +int freetemp(int k); diff --git a/usr.bin/pcc/mip/reader.c b/usr.bin/pcc/mip/reader.c new file mode 100644 index 00000000000..01135685094 --- /dev/null +++ b/usr.bin/pcc/mip/reader.c @@ -0,0 +1,1098 @@ +/* $Id: reader.c,v 1.1 2007/09/15 18:12:37 otto Exp $ */ +/* + * Copyright (c) 2003 Anders Magnusson (ragge@ludd.luth.se). + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code and documentation must retain the above + * copyright notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditionsand the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed or owned by Caldera + * International, Inc. + * Neither the name of Caldera International, Inc. nor the names of other + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA + * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE + * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Everything is entered via pass2_compile(). Three functions are + * allowed to recurse into pass2_compile(), so be careful: + * - deluseless() + * - myreader() + * Especially in myreader note that trees may be rewritten twice if + * things are not carefully handled. + */ + +# include "pass2.h" + +#include <string.h> +#include <stdarg.h> +#include <stdlib.h> + +/* some storage declarations */ +int nrecur; +int lflag; +int x2debug; +int udebug = 0; +int thisline; +int fregs; +int p2autooff, p2maxautooff; + +NODE *nodepole; +FILE *prfil; + +void saveip(struct interpass *ip); +void deljumps(void); +void deltemp(NODE *p); +void mkhardops(NODE *p); +void optdump(struct interpass *ip); +void cvtemps(struct interpass *epil); +NODE *store(NODE *); +void rcount(void); +void compile2(struct interpass *ip); +void compile3(struct interpass *ip); +void compile4(struct interpass *ip); + +static void gencode(NODE *p, int cookie); + +char *ltyp[] = { "", "LREG", "LOREG", "LTEMP" }; +char *rtyp[] = { "", "RREG", "ROREG", "RTEMP" }; + +/* used when removing nodes */ +struct tmpsave { + struct tmpsave *next; + CONSZ tempaddr; + int tempno; +} *tmpsave; + +#ifdef PCC_DEBUG +static void +cktree(NODE *p) +{ + if (p->n_op > MAXOP) + cerror("op %d slipped through", p->n_op); + if (BTYPE(p->n_type) > MAXTYPES) + cerror("type %x slipped through", p->n_type); + if (p->n_op == CBRANCH && !logop(p->n_left->n_op)) + cerror("not logop branch"); + if ((dope[p->n_op] & ASGOPFLG) && p->n_op != RETURN) + cerror("asgop %d slipped through", p->n_op); +} +#endif + +/* + * Check if a node has side effects. + */ +static int +isuseless(NODE *n) +{ + switch (n->n_op) { + case FUNARG: + case UCALL: + case UFORTCALL: + case FORCE: +/* case INIT: */ + case ASSIGN: + case CALL: + case FORTCALL: + case CBRANCH: + case RETURN: + case GOTO: + case STCALL: + case USTCALL: + case STASG: + case STARG: + return 0; + default: + return 1; + } +} + +/* + * Delete statements with no meaning (like a+b; or 513.4;) + */ +static NODE * +deluseless(NODE *p) +{ + struct interpass *ip; + NODE *l, *r; + + if (optype(p->n_op) == LTYPE) { + nfree(p); + return NULL; + } + if (isuseless(p) == 0) + return p; + + if (optype(p->n_op) == UTYPE) { + l = p->n_left; + nfree(p); + return deluseless(l); + } + + /* Be sure that both leaves may be valid */ + l = deluseless(p->n_left); + r = deluseless(p->n_right); + nfree(p); + if (l && r) { + /* Put left on queue first */ + ip = tmpalloc(sizeof(*ip)); + ip->type = IP_NODE; + ip->lineno = 0; /* XXX */ + ip->ip_node = l; + pass2_compile(ip); + return r; + } else if (l) + return l; + else if (r) + return r; + return NULL; +} + +static struct interpass ipole; +struct interpass_prolog *ipp, *epp; + +/* + * Receives interpass structs from pass1. + */ +void +pass2_compile(struct interpass *ip) +{ + if (ip->type == IP_PROLOG) { + tmpsave = NULL; + ipp = (struct interpass_prolog *)ip; + DLIST_INIT(&ipole, qelem); + } + DLIST_INSERT_BEFORE(&ipole, ip, qelem); + if (ip->type != IP_EPILOG) + return; + +#ifdef PCC_DEBUG + if (e2debug) { + printf("Entering pass2\n"); + printip(&ipole); + } +#endif + + epp = (struct interpass_prolog *)DLIST_PREV(&ipole, qelem); + p2maxautooff = p2autooff = epp->ipp_autos; + + myreader(&ipole); /* local massage of input */ + + DLIST_FOREACH(ip, &ipole, qelem) { + if (ip->type != IP_NODE) + continue; + if (xtemps == 0) + walkf(ip->ip_node, deltemp); + } + DLIST_FOREACH(ip, &ipole, qelem) { + if (ip->type != IP_NODE) + continue; + canon(ip->ip_node); + walkf(ip->ip_node, cktree); + if ((ip->ip_node = deluseless(ip->ip_node)) == NULL) + DLIST_REMOVE(ip, qelem); + } + + optimize(&ipole); + ngenregs(&ipole); + + DLIST_FOREACH(ip, &ipole, qelem) + emit(ip); +} + +void +emit(struct interpass *ip) +{ + NODE *p; + int o; + + switch (ip->type) { + case IP_NODE: + p = ip->ip_node; + + nodepole = p; +//printf("bu:\n"); +//fwalk(p, e2print, 0); + canon(p); /* may convert stuff after genregs */ +//fwalk(p, e2print, 0); + switch (p->n_op) { + case CBRANCH: + /* Only emit branch insn if RESCC */ + if (table[TBLIDX(p->n_left->n_su)].rewrite & RESCC) { + o = p->n_left->n_op; + gencode(p, FORCC); + cbgen(o, p->n_right->n_lval); + } else + gencode(p, FORCC); + break; + case FORCE: + gencode(p->n_left, INREGS); + break; + default: + if (p->n_op != REG || p->n_type != VOID) /* XXX */ + gencode(p, FOREFF); /* Emit instructions */ + } + + tfree(p); + break; + case IP_PROLOG: + prologue((struct interpass_prolog *)ip); + break; + case IP_EPILOG: + eoftn((struct interpass_prolog *)ip); + tmpsave = NULL; /* Always forget old nodes */ + p2maxautooff = p2autooff = AUTOINIT/SZCHAR; + break; + case IP_DEFLAB: + deflab(ip->ip_lbl); + break; + case IP_ASM: + printf("\t%s\n", ip->ip_asm); + break; + default: + cerror("compile4 %d", ip->type); + } +} + +#ifdef PCC_DEBUG +char *cnames[] = { + "SANY", + "SAREG", + "SBREG", + "SCREG", + "SDREG", + "SCC", + "SNAME", + "SCON", + "SFLD", + "SOREG", + "STARNM", + "STARREG", + "INTEMP", + "FORARG", + "SWADD", + 0, +}; + +/* + * print a nice-looking description of cookie + */ +char * +prcook(int cookie) +{ + static char buf[50]; + int i, flag; + + if (cookie & SPECIAL) { + switch (cookie) { + case SZERO: + return "SZERO"; + case SONE: + return "SONE"; + case SMONE: + return "SMONE"; + default: + snprintf(buf, sizeof(buf), "SPECIAL+%d", cookie & ~SPECIAL); + return buf; + } + } + + flag = 0; + buf[0] = 0; + for (i = 0; cnames[i]; ++i) { + if (cookie & (1<<i)) { + if (flag) + strlcat(buf, "|", sizeof(buf)); + ++flag; + strlcat(buf, cnames[i], sizeof(buf)); + } + } + return buf; +} + +#endif + +int odebug = 0; + +int +geninsn(NODE *p, int cookie) +{ + NODE *p1, *p2; + int o, rv = 0; + +#ifdef PCC_DEBUG + if (odebug) { + printf("geninsn(%p, %s)\n", p, prcook(cookie)); + fwalk(p, e2print, 0); + } +#endif + +again: switch (o = p->n_op) { + case EQ: + case NE: + case LE: + case LT: + case GE: + case GT: + case ULE: + case ULT: + case UGE: + case UGT: + rv = relops(p); + break; + + case PLUS: + case MINUS: + case MUL: + case DIV: + case MOD: + case AND: + case OR: + case ER: + case LS: + case RS: + rv = findops(p, cookie); + break; + + case ASSIGN: + case STASG: + rv = findasg(p, cookie); + break; + + case UMUL: /* May turn into an OREG */ + rv = findumul(p, cookie); + break; + + case REG: + case TEMP: + case NAME: + case ICON: + case OREG: + rv = findleaf(p, cookie); + break; + + case STCALL: + case CALL: + /* CALL arguments are handled special */ + for (p1 = p->n_right; p1->n_op == CM; p1 = p1->n_left) + geninsn(p1->n_right, FOREFF); + geninsn(p1, FOREFF); + /* FALLTHROUGH */ + case COMPL: + case UMINUS: + case PCONV: + case SCONV: +/* case INIT: */ + case GOTO: + case FUNARG: + case STARG: + case UCALL: + case USTCALL: + rv = finduni(p, cookie); + break; + + case CBRANCH: + p1 = p->n_left; + p2 = p->n_right; + p1->n_label = p2->n_lval; + o = p1->n_op; + geninsn(p1, FORCC); + p->n_su = 0; + break; + + case FORCE: /* XXX needed? */ + geninsn(p->n_left, INREGS); + p->n_su = 0; /* su calculations traverse left */ + break; + + default: + comperr("geninsn: bad op %s, node %p", opst[o], p); + } + if (rv == FFAIL) + comperr("Cannot generate code, node %p op %s", p,opst[p->n_op]); + if (rv == FRETRY) + goto again; + return rv; +} + +/* + * Store a given subtree in a temporary location. + * Return an OREG node where it is located. + */ +NODE * +store(NODE *p) +{ + extern struct interpass *storesave; + struct interpass *ip; + NODE *q, *r; + int s; + + s = BITOOR(freetemp(szty(p->n_type))); + q = mklnode(OREG, s, FPREG, p->n_type); + r = mklnode(OREG, s, FPREG, p->n_type); + ip = ipnode(mkbinode(ASSIGN, q, p, p->n_type)); + + storesave = ip; + return r; +} + +#ifdef PCC_DEBUG +#define CDEBUG(x) if (c2debug) printf x +#else +#define CDEBUG(x) +#endif + +/* + * Do a register-register move if necessary. + */ +static void +ckmove(NODE *p, NODE *q) +{ + if (q->n_op != REG || p->n_reg == -1) + return; /* no register */ + if (DECRA(p->n_reg, 0) == DECRA(q->n_reg, 0)) + return; /* no move necessary */ + CDEBUG(("rmove: node %p, %s -> %s\n", p, rnames[DECRA(q->n_reg, 0)], + rnames[DECRA(p->n_reg, 0)])); + rmove(DECRA(q->n_reg, 0), DECRA(p->n_reg, 0), p->n_type); + q->n_reg = q->n_rval = DECRA(p->n_reg, 0); +} + +/* + * Rewrite node to register after instruction emit. + */ +static void +rewrite(NODE *p, int rewrite, int cookie) +{ + NODE *l, *r; + int o; + + l = getlr(p, 'L'); + r = getlr(p, 'R'); + o = p->n_op; + p->n_op = REG; + p->n_lval = 0; + p->n_name = ""; + + if (o == ASSIGN) { + /* special rewrite care */ + int reg = DECRA(p->n_reg, 0); +#define TL(x) (TBLIDX(x->n_su) || x->n_op == REG) + if (p->n_reg == -1) + ; + else if (TL(l) && (DECRA(l->n_reg, 0) == reg)) + ; + else if (TL(r) && (DECRA(r->n_reg, 0) == reg)) + ; + else if (TL(l)) + rmove(DECRA(l->n_reg, 0), reg, p->n_type); + else if (TL(r)) + rmove(DECRA(r->n_reg, 0), reg, p->n_type); +#if 0 + else + comperr("rewrite"); +#endif +#undef TL + } + if (optype(o) != LTYPE) + tfree(l); + if (optype(o) == BITYPE) + tfree(r); + if (rewrite == 0) + return; + CDEBUG(("rewrite: %p, reg %s\n", p, rnames[DECRA(p->n_reg, 0)])); + p->n_rval = DECRA(p->n_reg, 0); +} + +void +gencode(NODE *p, int cookie) +{ + struct optab *q = &table[TBLIDX(p->n_su)]; + NODE *p1, *l, *r; + int o = optype(p->n_op); + + l = p->n_left; + r = p->n_right; + + if (TBLIDX(p->n_su) == 0) { + if (o == BITYPE && (p->n_su & DORIGHT)) + gencode(r, 0); + if (optype(p->n_op) != LTYPE) + gencode(l, 0); + if (o == BITYPE && !(p->n_su & DORIGHT)) + gencode(r, 0); + return; + } + + CDEBUG(("gencode: node %p\n", p)); + + if (p->n_op == REG && DECRA(p->n_reg, 0) == p->n_rval) + return; /* meaningless move to itself */ + + if (callop(p->n_op)) + lastcall(p); /* last chance before function args */ + if (p->n_op == CALL || p->n_op == FORTCALL || p->n_op == STCALL) { + /* Print out arguments first */ + for (p1 = r; p1->n_op == CM; p1 = p1->n_left) + gencode(p1->n_right, FOREFF); + gencode(p1, FOREFF); + o = UTYPE; /* avoid going down again */ + } + + if (o == BITYPE && (p->n_su & DORIGHT)) { + gencode(r, INREGS); + if (q->rewrite & RRIGHT) + ckmove(p, r); + } + if (o != LTYPE) { + gencode(l, INREGS); + if (q->rewrite & RLEFT) + ckmove(p, l); + } + if (o == BITYPE && !(p->n_su & DORIGHT)) { + gencode(r, INREGS); + if (q->rewrite & RRIGHT) + ckmove(p, r); + } + + canon(p); + + if (q->needs & NSPECIAL) { + int rr = rspecial(q, NRIGHT); + int lr = rspecial(q, NLEFT); + + if (rr >= 0) { + if (r->n_op != REG) + comperr("gencode: rop != REG"); + if (rr != r->n_rval) + rmove(r->n_rval, rr, r->n_type); + r->n_rval = r->n_reg = rr; + } + if (lr >= 0) { + if (l->n_op != REG) + comperr("gencode: %p lop != REG", p); + if (lr != l->n_rval) + rmove(l->n_rval, lr, l->n_type); + l->n_rval = l->n_reg = lr; + } + if (rr >= 0 && lr >= 0 && (l->n_reg == rr || r->n_reg == lr)) + comperr("gencode: cross-reg-move"); + } + + if (p->n_op == ASSIGN && + p->n_left->n_op == REG && p->n_right->n_op == REG && + p->n_left->n_rval == p->n_right->n_rval){ + /* do not emit anything */ + CDEBUG(("gencode(%p) assign nothing\n", p)); + rewrite(p, q->rewrite, cookie); + return; + } + + CDEBUG(("emitting node %p\n", p)); + if (TBLIDX(p->n_su) == 0) + return; + + expand(p, cookie, q->cstring); + if (callop(p->n_op) && cookie != FOREFF && + DECRA(p->n_reg, 0) != RETREG(p->n_type)) { + CDEBUG(("gencode(%p) retreg\n", p)); + rmove(RETREG(p->n_type), DECRA(p->n_reg, 0), p->n_type); + } else if (q->needs & NSPECIAL) { + int rr = rspecial(q, NRES); + + if (rr >= 0 && DECRA(p->n_reg, 0) != rr) { + CDEBUG(("gencode(%p) nspec retreg\n", p)); + rmove(rr, DECRA(p->n_reg, 0), p->n_type); + } + } else if ((q->rewrite & RESC1) && + (DECRA(p->n_reg, 1) != DECRA(p->n_reg, 0))) { + CDEBUG(("gencode(%p) RESC1 retreg\n", p)); + rmove(DECRA(p->n_reg, 1), DECRA(p->n_reg, 0), p->n_type); + } +#if 0 + /* XXX - kolla upp det här */ + else if (p->n_op == ASSIGN) { + /* may need move added if RLEFT/RRIGHT */ + /* XXX should be handled in sucomp() */ + if ((q->rewrite & RLEFT) && (p->n_left->n_op == REG) && + (p->n_left->n_rval != DECRA(p->n_reg, 0)) && + TCLASS(p->n_su)) { + rmove(p->n_left->n_rval, DECRA(p->n_reg, 0), p->n_type); + } else if ((q->rewrite & RRIGHT) && (p->n_right->n_op == REG) && + (p->n_right->n_rval != DECRA(p->n_reg, 0)) && + TCLASS(p->n_su)) { + rmove(p->n_right->n_rval, DECRA(p->n_reg, 0), p->n_type); + } + } +#endif + rewrite(p, q->rewrite, cookie); +} + +int negrel[] = { NE, EQ, GT, GE, LT, LE, UGT, UGE, ULT, ULE } ; /* negatives of relationals */ + +#ifdef PCC_DEBUG +#undef PRTABLE +void +e2print(NODE *p, int down, int *a, int *b) +{ +#ifdef PRTABLE + extern int tablesize; +#endif + + prfil = stdout; + *a = *b = down+1; + while( down >= 2 ){ + fprintf(prfil, "\t"); + down -= 2; + } + if( down-- ) fprintf(prfil, " " ); + + + fprintf(prfil, "%p) %s", p, opst[p->n_op] ); + switch( p->n_op ) { /* special cases */ + + case REG: + fprintf(prfil, " %s", rnames[p->n_rval] ); + break; + + case TEMP: + fprintf(prfil, " " CONFMT, p->n_lval); + break; + + case ICON: + case NAME: + case OREG: + fprintf(prfil, " " ); + adrput(prfil, p ); + break; + + case STCALL: + case USTCALL: + case STARG: + case STASG: + fprintf(prfil, " size=%d", p->n_stsize ); + fprintf(prfil, " align=%d", p->n_stalign ); + break; + } + + fprintf(prfil, ", " ); + tprint(prfil, p->n_type, p->n_qual); + fprintf(prfil, ", " ); + { + int gregn(struct regw *); + if (p->n_reg == -1) + fprintf(prfil, "REG <undef>"); + else if (p->n_reg < 100000) /* XXX */ + fprintf(prfil, "REG %s", rnames[DECRA(p->n_reg, 0)]); + else + fprintf(prfil, "TEMP %d", gregn(p->n_regw)); + } + fprintf(prfil, ", SU= %d(%cREG,%s,%s,%s,%s)\n", + TBLIDX(p->n_su), + TCLASS(p->n_su)+'@', +#ifdef PRTABLE + TBLIDX(p->n_su) >= 0 && TBLIDX(p->n_su) <= tablesize ? + table[TBLIDX(p->n_su)].cstring : "", +#else + "", +#endif + ltyp[LMASK&p->n_su], + rtyp[(p->n_su&RMASK) >> 2], p->n_su & DORIGHT ? "DORIGHT" : ""); +} +#endif + +#ifndef FIELDOPS +/* + * do this if there is no special hardware support for fields + */ +static void +ffld(NODE *p, int down, int *down1, int *down2 ) +{ + /* + * look for fields that are not in an lvalue context, + * and rewrite them... + */ + NODE *shp; + int s, o, v, ty; + + *down1 = asgop( p->n_op ); + *down2 = 0; + + if( !down && p->n_op == FLD ){ /* rewrite the node */ + + if( !rewfld(p) ) return; + + ty = p->n_type; + v = p->n_rval; + s = UPKFSZ(v); +# ifdef RTOLBYTES + o = UPKFOFF(v); /* amount to shift */ +# else + o = szty(p->n_type)*SZINT - s - UPKFOFF(v); /* amount to shift */ +#endif + + /* make & mask part */ + + p->n_left->n_type = ty; + + p->n_op = AND; + p->n_right = mklnode(ICON, (1 << s)-1, 0, ty); + + /* now, if a shift is needed, do it */ + + if( o != 0 ){ + shp = mkbinode(RS, p->n_left, + mklnode(ICON, o, 0, INT), ty); + p->n_left = shp; + /* whew! */ + } + } +} +#endif + +/* + * change left TEMPs into OREGs + */ +void +deltemp(NODE *p) +{ + struct tmpsave *w; + NODE *l; + + if (p->n_op == TEMP) { + /* Check if already existing */ + for (w = tmpsave; w; w = w->next) + if (w->tempno == p->n_lval) + break; + if (w == NULL) { + /* new on stack */ + w = tmpalloc(sizeof(struct tmpsave)); + w->tempno = p->n_lval; + w->tempaddr = BITOOR(freetemp(szty(p->n_type))); + w->next = tmpsave; + tmpsave = w; + } + p->n_op = OREG; + p->n_rval = FPREG; + p->n_lval = w->tempaddr; + } else if (p->n_op == ADDROF) { + /* TEMPs are already converted to OREGs */ + if ((l = p->n_left)->n_op != OREG) + comperr("bad U&"); + p->n_op = PLUS; + l->n_op = REG; + l->n_type = INCREF(l->n_type); + p->n_right = mklnode(ICON, l->n_lval, 0, INT); + } +} + +/* + * for pointer/integer arithmetic, set pointer at left node + */ +static void +setleft(NODE *p) +{ + NODE *q; + + /* only additions for now */ + if (p->n_op != PLUS) + return; + if (ISPTR(p->n_right->n_type) && !ISPTR(p->n_left->n_type)) { + q = p->n_right; + p->n_right = p->n_left; + p->n_left = q; + } +} + +/* It is OK to have these as externals */ +static int oregr; +static CONSZ oregtemp; +static char *oregcp; +/* + * look for situations where we can turn * into OREG + * If sharp then do not allow temps. + */ +int +oregok(NODE *p, int sharp) +{ + + NODE *q; + NODE *ql, *qr; + int r; + CONSZ temp; + char *cp; + + q = p->n_left; +#if 0 + if ((q->n_op == REG || (q->n_op == TEMP && !sharp)) && + q->n_rval == DECRA(q->n_reg, 0)) { +#endif + if (q->n_op == REG || (q->n_op == TEMP && !sharp)) { + temp = q->n_lval; + r = q->n_rval; + cp = q->n_name; + goto ormake; + } + + if (q->n_op != PLUS && q->n_op != MINUS) + return 0; + ql = q->n_left; + qr = q->n_right; + +#ifdef R2REGS + + /* look for doubly indexed expressions */ + /* XXX - fix checks */ + + if( q->n_op == PLUS) { + int i; + if( (r=base(ql))>=0 && (i=offset(qr, tlen(p)))>=0) { + makeor2(p, ql, r, i); + return; + } else if((r=base(qr))>=0 && (i=offset(ql, tlen(p)))>=0) { + makeor2(p, qr, r, i); + return; + } + } + + +#endif + +#if 0 + if( (q->n_op==PLUS || q->n_op==MINUS) && qr->n_op == ICON && + (ql->n_op==REG || (ql->n_op==TEMP && !sharp)) && + szty(qr->n_type)==1 && + (ql->n_rval == DECRA(ql->n_reg, 0) || + /* XXX */ + ql->n_rval == FPREG || ql->n_rval == STKREG)) { +#endif + if ((q->n_op==PLUS || q->n_op==MINUS) && qr->n_op == ICON && + (ql->n_op==REG || (ql->n_op==TEMP && !sharp))) { + + temp = qr->n_lval; + if( q->n_op == MINUS ) temp = -temp; + r = ql->n_rval; + temp += ql->n_lval; + cp = qr->n_name; + if( *cp && ( q->n_op == MINUS || *ql->n_name ) ) + return 0; + if( !*cp ) cp = ql->n_name; + + ormake: + if( notoff( p->n_type, r, temp, cp )) + return 0; + oregtemp = temp; + oregr = r; + oregcp = cp; + return 1; + } + return 0; +} + +static void +ormake(NODE *p) +{ + NODE *q = p->n_left; + + p->n_op = OREG; + p->n_rval = oregr; + p->n_lval = oregtemp; + p->n_name = oregcp; + tfree(q); +} + +/* + * look for situations where we can turn * into OREG + */ +void +oreg2(NODE *p) +{ + if (p->n_op != UMUL) + return; + if (oregok(p, 1)) + ormake(p); + if (p->n_op == UMUL) + myormake(p); +} + +void +canon(p) NODE *p; { + /* put p in canonical form */ + + walkf(p, setleft); /* ptrs at left node for arithmetic */ + walkf(p, oreg2); /* look for and create OREG nodes */ +#ifndef FIELDOPS + fwalk(p, ffld, 0); /* look for field operators */ +# endif +#ifdef MYCANON + MYCANON(p); /* your own canonicalization routine(s) */ +#endif + +} + +void +comperr(char *str, ...) +{ + extern char *ftitle; + va_list ap; + + va_start(ap, str); + fprintf(stderr, "%s, line %d: compiler error: ", ftitle, thisline); + vfprintf(stderr, str, ap); + fprintf(stderr, "\n"); + va_end(ap); + prfil = stderr; + + if (nodepole && nodepole->n_op != FREE) + fwalk(nodepole, e2print, 0); + exit(1); +} + +/* + * allocate k integers worth of temp space + * we also make the convention that, if the number of words is + * more than 1, it must be aligned for storing doubles... + * Returns bits offset from base register. + * XXX - redo this. + */ +int +freetemp(int k) +{ +#ifndef BACKTEMP + int t; + + if (k > 1) + SETOFF(p2autooff, ALDOUBLE/ALCHAR); + + t = p2autooff; + p2autooff += k*(SZINT/SZCHAR); + if (p2autooff > p2maxautooff) + p2maxautooff = p2autooff; + return (t); + +#else + p2autooff += k*(SZINT/SZCHAR); + if (k > 1) + SETOFF(p2autooff, ALDOUBLE/ALCHAR); + + if (p2autooff > p2maxautooff) + p2maxautooff = p2autooff; + return( -p2autooff ); +#endif + } + +NODE * +mklnode(int op, CONSZ lval, int rval, TWORD type) +{ + NODE *p = talloc(); + + p->n_name = ""; + p->n_qual = 0; + p->n_op = op; + p->n_lval = lval; + p->n_rval = rval; + p->n_type = type; + p->n_regw = NULL; + p->n_su = 0; + return p; +} + +NODE * +mkbinode(int op, NODE *left, NODE *right, TWORD type) +{ + NODE *p = talloc(); + + p->n_name = ""; + p->n_qual = 0; + p->n_op = op; + p->n_left = left; + p->n_right = right; + p->n_type = type; + p->n_regw = NULL; + return p; +} + +NODE * +mkunode(int op, NODE *left, int rval, TWORD type) +{ + NODE *p = talloc(); + + p->n_name = ""; + p->n_qual = 0; + p->n_op = op; + p->n_left = left; + p->n_rval = rval; + p->n_type = type; + p->n_regw = NULL; + return p; +} + +struct interpass * +ipnode(NODE *p) +{ + struct interpass *ip = tmpalloc(sizeof(struct interpass)); + + ip->ip_node = p; + ip->type = IP_NODE; + ip->lineno = thisline; + return ip; +} + +int +rspecial(struct optab *q, int what) +{ + struct rspecial *r = nspecial(q); + while (r->op) { + if (r->op == what) + return r->num; + r++; + } + return -1; +} diff --git a/usr.bin/pcc/mip/regs.c b/usr.bin/pcc/mip/regs.c new file mode 100644 index 00000000000..3371b4bee79 --- /dev/null +++ b/usr.bin/pcc/mip/regs.c @@ -0,0 +1,2244 @@ +/* $Id: regs.c,v 1.1 2007/09/15 18:12:37 otto Exp $ */ +/* + * Copyright (c) 2005 Anders Magnusson (ragge@ludd.luth.se). + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "pass2.h" +#include <string.h> +#include <stdlib.h> + +#define MAXLOOP 20 /* Max number of allocation loops XXX 3 should be enough */ + +#define MAX(a,b) (((a) > (b)) ? (a) : (b)) + +/* + * New-style register allocator using graph coloring. + * The design is based on the George and Appel paper + * "Iterated Register Coalescing", ACM Transactions, No 3, May 1996. + */ + +#define BIT2BYTE(bits) ((((bits)+NUMBITS-1)/NUMBITS)*(NUMBITS/8)) +#define BITALLOC(ptr,all,sz) { \ + int __s = BIT2BYTE(sz); ptr = all(__s); memset(ptr, 0, __s); } + +#undef COMPERR_PERM_MOVE +#define RDEBUG(x) if (rdebug) printf x +#define RRDEBUG(x) if (rdebug > 1) printf x +#define RPRINTIP(x) if (rdebug) printip(x) +#define RDX(x) x +#define UDEBUG(x) if (udebug) printf x + +/* + * Data structure overview for this implementation of graph coloring: + * + * Each temporary (called "node") is described by the type REGW. + * Space for all nodes is allocated initially as an array, so + * the nodes can be can be referenced both by the node number and + * by pointer. + * + * All moves are represented by the type REGM, allocated when needed. + * + * The "live" set used during graph building is represented by a bitset. + * + * Interference edges are represented by struct AdjSet, hashed and linked + * from index into the edgehash array. + * + * A mapping from each node to the moves it is assiciated with is + * maintained by an array moveList which for each node number has a linked + * list of MOVL types, each pointing to a REGM. + * + * Adjacency list is maintained by the adjList array, indexed by the + * node number. Each adjList entry points to an ADJL type, and is a + * single-linked list for all adjacent nodes. + * + * degree, alias and color are integer arrays indexed by node number. + */ + +/* + * linked list of adjacent nodes. + */ +typedef struct regw3 { + struct regw3 *r_next; + struct regw *a_temp; +} ADJL; + +/* + * Structure describing a move. + */ +typedef struct regm { + DLIST_ENTRY(regm) link; + struct regw *src, *dst; + int queue; +} REGM; + +typedef struct movlink { + struct movlink *next; + REGM *regm; +} MOVL; + +/* + * Structure describing a temporary. + */ +typedef struct regw { + DLIST_ENTRY(regw) link; + ADJL *r_adjList; /* linked list of adjacent nodes */ + int r_class; /* this nodes class */ + int r_nclass[NUMCLASS+1]; /* count of adjacent classes */ + struct regw *r_alias; /* aliased temporary */ + int r_color; /* final node color */ + struct regw *r_onlist; /* which work list this node belongs to */ + MOVL *r_moveList; /* moves associated with this node */ +#ifdef PCC_DEBUG + int nodnum; /* Debug number */ +#endif +} REGW; + +/* + * Worklists, a node is always on exactly one of these lists. + */ +static REGW precolored, simplifyWorklist, freezeWorklist, spillWorklist, + spilledNodes, coalescedNodes, coloredNodes, selectStack; +static REGW initial, *nblock; +static void insnwalk(NODE *p); +#ifdef PCC_DEBUG +int nodnum = 100; +#define SETNUM(x) (x)->nodnum = nodnum++ +#define ASGNUM(x) (x)->nodnum +#else +#define SETNUM(x) +#define ASGNUM(x) +#endif + +#define ALLNEEDS (NACOUNT|NBCOUNT|NCCOUNT|NDCOUNT) + +/* XXX */ +REGW *ablock; + +static int tempmin, tempmax, basetemp, xbits; +/* + * nsavregs is an array that matches the permregs array. + * Each entry in the array may have the values: + * 0 : register coalesced, just ignore. + * 1 : save register on stack + * If the entry is 0 but the resulting color differs from the + * corresponding permregs index, add moves. + * XXX - should be a bitfield! + */ +static int *nsavregs, *ndontregs; + +/* + * Return the REGW struct for a temporary. + * If first time touched, enter into list for existing vars. + * Only called from sucomp(). + */ +static REGW * +newblock(NODE *p) +{ + REGW *nb = &nblock[(int)p->n_lval]; + if (nb->link.q_forw == 0) { + DLIST_INSERT_AFTER(&initial, nb, link); + ASGNUM(nb) = p->n_lval; + RDEBUG(("Adding longtime %d for tmp %d\n", + nb->nodnum, (int)p->n_lval)); + } + if (nb->r_class == 0) + nb->r_class = gclass(p->n_type); + RDEBUG(("newblock: p %p, node %d class %d\n", + p, nb->nodnum, nb->r_class)); + return nb; +} + +/* + * Count the number of registers needed to evaluate a tree. + * This is only done to find the evaluation order of the tree. + * While here, assign temp numbers to the registers that will + * be needed when the tree is evaluated. + * + * While traversing the tree, assign REGW nodes to the registers + * used by all instructions: + * - n_regw[0] is always set to the outgoing node. If the + * instruction is 2-op (addl r0,r1) then an implicit move + * is inserted just before the left (clobbered) operand. + * - if the instruction has needs then REGW nodes are + * allocated as n_regw[1] etc. + */ +int +nsucomp(NODE *p) +{ + struct optab *q; + int left, right; + int nreg, need, i, nxreg, o; + int nareg, nbreg, ncreg, ndreg; + REGW *w; + + o = optype(p->n_op); + + UDEBUG(("entering nsucomp, node %p\n", p)); + + if (TBLIDX(p->n_su) == 0) { + int a = 0, b; + + p->n_regw = NULL; + if (o == LTYPE ) { + if (p->n_op == TEMP) + p->n_regw = newblock(p); + } else + a = nsucomp(p->n_left); + if (o == BITYPE) { + b = nsucomp(p->n_right); + if (b > a) + p->n_su |= DORIGHT; + a = MAX(a, b); + } + return a; + } + + q = &table[TBLIDX(p->n_su)]; + nareg = (q->needs & NACOUNT); + + for (i = (q->needs & NBCOUNT), nbreg = 0; i; i -= NBREG) + nbreg++; + for (i = (q->needs & NCCOUNT), ncreg = 0; i; i -= NCREG) + ncreg++; + for (i = (q->needs & NDCOUNT), ndreg = 0; i; i -= NDREG) + ndreg++; + + nxreg = nareg + nbreg + ncreg + ndreg; + nreg = nxreg; + if (callop(p->n_op)) + nreg = MAX(fregs, nreg); + + if (o == BITYPE) { + right = nsucomp(p->n_right); + } else + right = 0; + + if (o != LTYPE) + left = nsucomp(p->n_left); + else + left = 0; + + UDEBUG(("node %p left %d right %d\n", p, left, right)); + + if (o == BITYPE) { + /* Two children */ + if (right == left) { + need = left + MAX(nreg, 1); + } else { + need = MAX(right, left); + need = MAX(need, nreg); + } + if (setorder(p) == 0) { + /* XXX - should take care of overlapping needs */ + if (right > left) { + p->n_su |= DORIGHT; + } else if (right == left) { + /* A favor to 2-operand architectures */ + if ((q->rewrite & RRIGHT) == 0) + p->n_su |= DORIGHT; + } + } + } else if (o != LTYPE) { + /* One child */ + need = MAX(right, left) + nreg; + } else + need = nreg; + + if (p->n_op == TEMP) + (void)newblock(p); + + if (TCLASS(p->n_su) == 0 && nxreg == 0) { + UDEBUG(("node %p no class\n", p)); + p->n_regw = NULL; /* may be set earlier */ + return need; + } + +#define ADCL(n, cl) \ + for (i = 0; i < n; i++, w++) { w->r_class = cl; \ + DLIST_INSERT_BEFORE(&initial, w, link); SETNUM(w); \ + UDEBUG(("Adding " #n " %d\n", w->nodnum)); \ + } + + UDEBUG(("node %p numregs %d\n", p, nxreg+1)); + w = p->n_regw = tmpalloc(sizeof(REGW) * (nxreg+1)); + memset(w, 0, sizeof(REGW) * (nxreg+1)); + + w->r_class = TCLASS(p->n_su); + if (w->r_class == 0) + w->r_class = gclass(p->n_type); + SETNUM(w); + if (w->r_class) + DLIST_INSERT_BEFORE(&initial, w, link); + UDEBUG(("Adding short %d calss %d\n", w->nodnum, w->r_class)); + w++; + ADCL(nareg, CLASSA); + ADCL(nbreg, CLASSB); + ADCL(ncreg, CLASSC); + ADCL(ndreg, CLASSD); + + if (q->rewrite & RESC1) { + w = p->n_regw + 1; + w->r_class = -1; + DLIST_REMOVE(w,link); + } else if (q->rewrite & RESC2) { + w = p->n_regw + 2; + w->r_class = -1; + DLIST_REMOVE(w,link); + } else if (q->rewrite & RESC3) { + w = p->n_regw + 3; + w->r_class = -1; + DLIST_REMOVE(w,link); + } + + UDEBUG(("node %p return regs %d\n", p, need)); + + return need; +} + +#define CLASS(x) (x)->r_class +#define NCLASS(x,c) (x)->r_nclass[c] +#define ADJLIST(x) (x)->r_adjList +#define ALIAS(x) (x)->r_alias +#define ONLIST(x) (x)->r_onlist +#define MOVELIST(x) (x)->r_moveList +#define COLOR(x) (x)->r_color + +static bittype *live; + +#define PUSHWLIST(w, l) DLIST_INSERT_AFTER(&l, w, link); w->r_onlist = &l +#define POPWLIST(l) popwlist(&l); +#define DELWLIST(w) DLIST_REMOVE(w, link) +#define WLISTEMPTY(h) DLIST_ISEMPTY(&h,link) +#define PUSHMLIST(w, l, q) DLIST_INSERT_AFTER(&l, w, link); w->queue = q +#define POPMLIST(l) popmlist(&l); + +#define trivially_colorable(x) \ + trivially_colorable_p((x)->r_class, (x)->r_nclass) +/* + * Determine if a node is trivially colorable ("degree < K"). + * This implementation is a dumb one, without considering speed. + */ +static int +trivially_colorable_p(int c, int *n) +{ + int r[NUMCLASS+1]; + int i; + + for (i = 1; i < NUMCLASS+1; i++) + r[i] = n[i] < regK[i] ? n[i] : regK[i]; + +#if 0 + /* add the exclusion nodes. */ + /* XXX can we do someything smart here? */ + /* worst-case for exclusion nodes are better than the `worst-case' */ + for (; excl; excl >>= 1) + if (excl & 1) + r[c]++; +#endif + + i = COLORMAP(c, r); +if (i < 0 || i > 1) + comperr("trivially_colorable_p"); +//printf("trivially_colorable_p: n[1] %d n[2] %d n[3] %d n[4] %d class %d, triv %d\n", n[1], n[2], n[3], n[4], c, i); + return i; +} + +static int +ncnt(int needs) +{ + int i = 0; + + while (needs & NACOUNT) + needs -= NAREG, i++; + while (needs & NBCOUNT) + needs -= NBREG, i++; + while (needs & NCCOUNT) + needs -= NCREG, i++; + while (needs & NDCOUNT) + needs -= NDREG, i++; + return i; +} + +static inline REGW * +popwlist(REGW *l) +{ + REGW *w = DLIST_NEXT(l, link); + + DLIST_REMOVE(w, link); + w->r_onlist = NULL; + return w; +} + +/* + * Move lists, a move node is always on only one list. + */ +static REGM coalescedMoves, constrainedMoves, frozenMoves, + worklistMoves, activeMoves; +enum { COAL, CONSTR, FROZEN, WLIST, ACTIVE }; + +static inline REGM * +popmlist(REGM *l) +{ + REGM *w = DLIST_NEXT(l, link); + + DLIST_REMOVE(w, link); + return w; +} + +/* + * About data structures used in liveness analysis: + * + * The temporaries generated in pass1 are numbered between tempmin and + * tempmax. Temporaries generated in pass2 are numbered above tempmax, + * so they are sequentially numbered. + * + * Bitfields are used for liveness. Bit arrays are allocated on the + * heap for the "live" variable and on the stack for the in, out, gen + * and kill variables. Therefore, for a temp number, the bit number must + * be biased with tempmin. + * + * There may be an idea to use a different data structure to store + * pass2 allocated temporaries, because they are very sparse. + */ + +#ifdef PCC_DEBUG +static void +LIVEADD(int x) +{ + RDEBUG(("Liveadd: %d\n", x)); + if (x < tempmin || x >= tempmax) + comperr("LIVEADD: out of range"); + BITSET(live, (x-tempmin)); +} +static void +LIVEDEL(int x) +{ + RDEBUG(("Livedel: %d\n", x)); + if (x < tempmin || x >= tempmax) + comperr("LIVEDEL: out of range"); + BITCLEAR(live, (x-tempmin)); +} +#else +#define LIVEADD(x) BITSET(live, (x-tempmin)) +#define LIVEDEL(x) BITCLEAR(live, (x-tempmin)) +#endif + +static struct lives { + DLIST_ENTRY(lives) link; + REGW *var; +} lused, lunused; + +static void +LIVEADDR(REGW *x) +{ + struct lives *l; + +#ifdef PCC_DEBUG + RDEBUG(("LIVEADDR: %d\n", x->nodnum)); + DLIST_FOREACH(l, &lused, link) + if (l->var == x) + return; +// comperr("LIVEADDR: multiple %d", ASGNUM(x)); +#endif + if (!DLIST_ISEMPTY(&lunused, link)) { + l = DLIST_NEXT(&lunused, link); + DLIST_REMOVE(l, link); + } else + l = tmpalloc(sizeof(struct lives)); + + l->var = x; + DLIST_INSERT_AFTER(&lused, l, link); +} + +static void +LIVEDELR(REGW *x) +{ + struct lives *l; + + RDEBUG(("LIVEDELR: %d\n", x->nodnum)); + DLIST_FOREACH(l, &lused, link) { + if (l->var != x) + continue; + DLIST_REMOVE(l, link); + DLIST_INSERT_AFTER(&lunused, l, link); + return; + } +// comperr("LIVEDELR: %p not found", x); +} + +#define MOVELISTADD(t, p) movelistadd(t, p) +#define WORKLISTMOVEADD(s,d) worklistmoveadd(s,d) + +static void +movelistadd(REGW *t, REGM *p) +{ + MOVL *w = tmpalloc(sizeof(MOVL)); + + w->regm = p; + w->next = t->r_moveList; + t->r_moveList = w; +} + +static REGM * +worklistmoveadd(REGW *src, REGW *dst) +{ + REGM *w = tmpalloc(sizeof(REGM)); + + DLIST_INSERT_AFTER(&worklistMoves, w, link); + w->src = src; + w->dst = dst; + w->queue = WLIST; + return w; +} + +struct AdjSet { + struct AdjSet *next; + REGW *u, *v; +} *edgehash[256]; + +/* Check if a node pair is adjacent */ +static int +adjSet(REGW *u, REGW *v) +{ + struct AdjSet *w; + REGW *t; + + if (ONLIST(u) == &precolored) { + ADJL *a = ADJLIST(v); + /* + * Check if any of the registers that have edges against v + * alias to u. + */ + for (; a; a = a->r_next) { + if (ONLIST(a->a_temp) != &precolored) + continue; + t = a->a_temp; + if (interferes(t - ablock, u - ablock)) + return 1; + } + } + if (u > v) + t = v, v = u, u = t; + w = edgehash[((int)u+(int)v) & 255]; + for (; w; w = w->next) { + if (u == w->u && v == w->v) + return 1; + } + return 0; +} + +/* Add a pair to adjset. No check for dups */ +static void +adjSetadd(REGW *u, REGW *v) +{ + struct AdjSet *w; + int x; + REGW *t; + + if (u > v) + t = v, v = u, u = t; + x = ((int)u+(int)v) & 255; + w = tmpalloc(sizeof(struct AdjSet)); + w->u = u, w->v = v; + w->next = edgehash[x]; + edgehash[x] = w; +} + +/* + * Add an interference edge between two nodes. + */ +static void +AddEdge(REGW *u, REGW *v) +{ + ADJL *x; + + RRDEBUG(("AddEdge: u %d v %d\n", ASGNUM(u), ASGNUM(v))); + +#ifdef PCC_DEBUG +#if 0 + if (ASGNUM(u) == 0) + comperr("AddEdge 0"); +#endif + if (CLASS(u) == 0 || CLASS(v) == 0) + comperr("AddEdge class == 0 (%d=%d, %d=%d)", + CLASS(u), ASGNUM(u), CLASS(v), ASGNUM(v)); +#endif + + if (u == v) + return; + if (adjSet(u, v)) + return; + + adjSetadd(u, v); + +#if 0 + if (ONLIST(u) == &precolored || ONLIST(v) == &precolored) + comperr("precolored node in AddEdge"); +#endif + + if (ONLIST(u) != &precolored) { + x = tmpalloc(sizeof(ADJL)); + x->a_temp = v; + x->r_next = u->r_adjList; + u->r_adjList = x; + NCLASS(u, CLASS(v))++; + } + + if (ONLIST(v) != &precolored) { + x = tmpalloc(sizeof(ADJL)); + x->a_temp = u; + x->r_next = v->r_adjList; + v->r_adjList = x; + NCLASS(v, CLASS(u))++; + } + +#if 0 + RDEBUG(("AddEdge: u %d(d %d) v %d(d %d)\n", u, DEGREE(u), v, DEGREE(v))); +#endif +} + +static int +MoveRelated(REGW *n) +{ + MOVL *l; + REGM *w; + + for (l = MOVELIST(n); l; l = l->next) { + w = l->regm; + if (w->queue == ACTIVE || w->queue == WLIST) + return 1; + } + return 0; +} + +static void +MkWorklist(void) +{ + REGW *w; + + RDX(int s=0); + RDX(int f=0); + RDX(int d=0); + + DLIST_INIT(&precolored, link); + DLIST_INIT(&simplifyWorklist, link); + DLIST_INIT(&freezeWorklist, link); + DLIST_INIT(&spillWorklist, link); + DLIST_INIT(&spilledNodes, link); + DLIST_INIT(&coalescedNodes, link); + DLIST_INIT(&coloredNodes, link); + DLIST_INIT(&selectStack, link); + + /* + * Remove all nodes from the initial list and put them on + * one of the worklists. + */ + while (!DLIST_ISEMPTY(&initial, link)) { + w = DLIST_NEXT(&initial, link); + DLIST_REMOVE(w, link); + if (!trivially_colorable(w)) { + PUSHWLIST(w, spillWorklist); + RDX(s++); + } else if (MoveRelated(w)) { + PUSHWLIST(w, freezeWorklist); + RDX(f++); + } else { + PUSHWLIST(w, simplifyWorklist); + RDX(d++); + } + } + RDEBUG(("MkWorklist: spill %d freeze %d simplify %d\n", s,f,d)); +} + +static void +addalledges(REGW *e) +{ + int i, j, k; + int nbits = xbits; + struct lives *l; + + RDEBUG(("addalledges for %d\n", e->nodnum)); + + if (e->r_class == -1) + return; /* unused */ + + if (ONLIST(e) != &precolored) { + for (i = 0; ndontregs[i] >= 0; i++) + AddEdge(e, &ablock[ndontregs[i]]); + } + + /* First add to long-lived temps */ + RDEBUG(("addalledges longlived ")); + for (i = 0; i < nbits; i += NUMBITS) { + if ((k = live[i/NUMBITS]) == 0) + continue; + while (k) { + j = ffs(k)-1; + AddEdge(&nblock[i+j+tempmin], e); + RRDEBUG(("%d ", i+j+tempmin)); + k &= ~(1 << j); + } + } + RDEBUG(("done\n")); + /* short-lived temps */ + RDEBUG(("addalledges shortlived ")); + DLIST_FOREACH(l, &lused, link) { + RRDEBUG(("%d ", ASGNUM(l->var))); + AddEdge(l->var, e); + } + RDEBUG(("done\n")); +} + +/* + * Add a move edge between def and use. + */ +static void +moveadd(REGW *def, REGW *use) +{ + REGM *r; + + if (def == use) + return; /* no move to itself XXX - ``shouldn't happen'' */ + RDEBUG(("moveadd: def %d use %d\n", ASGNUM(def), ASGNUM(use))); + + r = WORKLISTMOVEADD(use, def); + MOVELISTADD(def, r); + MOVELISTADD(use, r); +} + +/* + * Traverse arguments backwards. + * XXX - can this be tricked in some other way? + */ +static void +argswalk(NODE *p) +{ + + if (p->n_op == CM) { + argswalk(p->n_left); + insnwalk(p->n_right); + } else + insnwalk(p); +} + +/* + * Add to (or remove from) live set variables that must not + * be clobbered when traversing down on the other leg for + * a BITYPE node. + */ +static void +setlive(NODE *p, int set, REGW *rv) +{ + if (rv != NULL) + return set ? LIVEADDR(rv) : LIVEDELR(rv); + + if (p->n_regw != NULL) + return set ? LIVEADDR(p->n_regw) : LIVEDELR(p->n_regw); + + switch (optype(p->n_op)) { + case LTYPE: + if (p->n_op == TEMP) + set ? LIVEADD((int)p->n_lval) : LIVEDEL((int)p->n_lval); +#ifdef notyet + else if (p->n_op == REG) + ... +#endif + break; + case BITYPE: + setlive(p->n_right, set, rv); + /* FALLTHROUGH */ + case UTYPE: + setlive(p->n_left, set, rv); + break; + } +} + +/* + * Add edges for temporary w against all temporaries that may be + * used simultaneously (like index registers). + */ +static void +addedge_r(NODE *p, REGW *w) +{ + if (p->n_regw != NULL) + return AddEdge(p->n_regw, w); + + if (optype(p->n_op) == BITYPE) + addedge_r(p->n_right, w); + if (optype(p->n_op) != LTYPE) + addedge_r(p->n_left, w); +} + +/* + * Do the in-tree part of liveness analysis. (the difficult part) + * + * Walk down the tree in reversed-evaluation order (backwards). + * The moves and edges inserted and evaluation order for + * instructions when code is emitted is described here, hence + * this code runs the same but backwards. + * + * 2-op reclaim LEFT: eval L, move to DEST, eval R. + * moveadd L,DEST; addedge DEST,R + * 2-op reclaim LEFT DORIGHT: eval R, eval L, move to DEST. + * moveadd L,DEST; addedge DEST,R; addedge L,R + * 2-op reclaim RIGHT; eval L, eval R, move to DEST. + * moveadd R,DEST; addedge DEST,L; addedge L,R + * 2-op reclaim RIGHT DORIGHT: eval R, move to DEST, eval L. + * moveadd R,DEST; addedge DEST,L + * 3-op: eval L, eval R + * addedge L,R + * 3-op DORIGHT: eval R, eval L + * addedge L,R + * + * Instructions with special needs are handled just like these variants, + * with the exception of extra added moves and edges. + * Moves to special regs are scheduled after the evaluation of both legs. + */ + +#define ASGLEFT(p) (p->n_op == ASSIGN && p->n_left->n_op == TEMP) + +static void +insnwalk(NODE *p) +{ + int o = p->n_op; + struct optab *q = &table[TBLIDX(p->n_su)]; + REGW *lr, *rr, *rv, *r, *rrv, *lrv; + int i, n; + + RDEBUG(("insnwalk %p\n", p)); + + rv = p->n_regw; + + rrv = lrv = NULL; + if (ASGLEFT(p)) { + int v = p->n_left->n_lval; + LIVEDEL(v); /* remove assigned temp from live set */ + addalledges(&nblock[v]); + } + + /* Add edges for the result of this node */ + if (rv && (q->visit & INREGS || o == TEMP)) + addalledges(rv); + + /* special handling of CALL operators */ + if (callop(o)) { + if (rv) + moveadd(rv, &ablock[RETREG(p->n_type)]); + for (i = 0; tempregs[i] >= 0; i++) + addalledges(&ablock[tempregs[i]]); + } + + /* for special return value registers add moves */ + if ((q->needs & NSPECIAL) && (n = rspecial(q, NRES)) >= 0) { + rv = &ablock[n]; + moveadd(p->n_regw, rv); + } + + /* Check leaves for results in registers */ + lr = optype(o) != LTYPE ? p->n_left->n_regw : NULL; + rr = optype(o) == BITYPE ? p->n_right->n_regw : NULL; + + /* simple needs */ + n = ncnt(q->needs); + for (i = 0; i < n; i++) { +#if 1 + static int ncl[] = { 0, NASL, NBSL, NCSL, NDSL }; + static int ncr[] = { 0, NASR, NBSR, NCSR, NDSR }; + + /* edges are already added */ + if ((r = &p->n_regw[1+i])->r_class == -1) + r = p->n_regw; + else + addalledges(r); + if (optype(o) != LTYPE && (q->needs & ncl[CLASS(r)]) == 0) + addedge_r(p->n_left, r); + if (optype(o) == BITYPE && (q->needs & ncr[CLASS(r)]) == 0) + addedge_r(p->n_right, r); +#else + if ((r = &p->n_regw[1+i])->r_class == -1) + continue; + addalledges(r); + if (optype(o) != LTYPE && (q->needs & NASL) == 0) + addedge_r(p->n_left, r); + if (optype(o) == BITYPE && (q->needs & NASR) == 0) + addedge_r(p->n_right, r); +#endif + } + + /* special needs */ + if (q->needs & NSPECIAL) { + struct rspecial *rc; + for (rc = nspecial(q); rc->op; rc++) { + switch (rc->op) { +#define ONLY(c,s) if (c) s(c, &ablock[rc->num]) + case NLEFT: + addalledges(&ablock[rc->num]); + ONLY(lr, moveadd); + break; + case NOLEFT: + addedge_r(p->n_left, &ablock[rc->num]); + break; + case NRIGHT: + addalledges(&ablock[rc->num]); + ONLY(rr, moveadd); + break; + case NORIGHT: + addedge_r(p->n_right, &ablock[rc->num]); + break; + case NEVER: + addalledges(&ablock[rc->num]); + break; +#undef ONLY + } + } + } + + if (o == ASSIGN) { + /* needs special treatment */ + if (lr && rr) + moveadd(lr, rr); + if (lr && rv) + moveadd(lr, rv); + if (rr && rv) + moveadd(rr, rv); + } else if (callop(o)) { +#ifdef notdef + /* calls needs special treatment */ + for (i = 0; tempregs[i] >= 0; i++) + addalledges(&ablock[i]); + if (rv) + moveadd(rv, &ablock[RETREG(p->n_type)]); +#endif + /* XXX - here must all live arg registers be added + * for archs with arguments in registers */ + } else if (q->rewrite & (RESC1|RESC2|RESC3)) { + if (lr && rr) + AddEdge(lr, rr); + } else if (q->rewrite & RLEFT) { + if (lr && rv) + moveadd(rv, lr), lrv = rv; + if (rr && rv) + AddEdge(rr, rv); + } else if (q->rewrite & RRIGHT) { + if (rr && rv) + moveadd(rv, rr), rrv = rv; + if (lr && rv) + AddEdge(lr, rv); + } + + switch (optype(o)) { + case BITYPE: + if (ASGLEFT(p)) { + /* only go down right node */ + insnwalk(p->n_right); + } else if (callop(o)) { + insnwalk(p->n_left); + /* Do liveness analysis on arguments (backwards) */ + argswalk(p->n_right); + } else if ((p->n_su & DORIGHT) == 0) { + setlive(p->n_left, 1, lrv); + insnwalk(p->n_right); + setlive(p->n_left, 0, lrv); + insnwalk(p->n_left); + } else { + setlive(p->n_right, 1, rrv); + insnwalk(p->n_left); + setlive(p->n_right, 0, rrv); + insnwalk(p->n_right); + } + break; + + case UTYPE: + insnwalk(p->n_left); + break; + + case LTYPE: + switch (o) { + case TEMP: + rr = &nblock[(int)p->n_lval]; + if (rv != rr) { + addalledges(rr); + moveadd(rv, rr); + } + LIVEADD((int)p->n_lval); + break; + case REG: + case OREG: + /* Liveness for regs??? */ + break; + default: + break; + } + break; + } +} + +static bittype **gen, **kill, **in, **out; + +static void +unionize(NODE *p, int bb) +{ + int i, o, ty; + + if ((o = p->n_op) == TEMP) { +#ifdef notyet + for (i = 0; i < szty(p->n_type); i++) { + BITSET(gen[bb], ((int)p->n_lval - tempmin+i)); + } +#else + i = 0; + BITSET(gen[bb], ((int)p->n_lval - tempmin+i)); +#endif + } + if (asgop(o) && p->n_left->n_op == TEMP) { + int b = p->n_left->n_lval - tempmin; +#ifdef notyet + for (i = 0; i < szty(p->n_type); i++) { + BITCLEAR(gen[bb], (b+i)); + BITSET(kill[bb], (b+i)); + } +#else + i = 0; + BITCLEAR(gen[bb], (b+i)); + BITSET(kill[bb], (b+i)); +#endif + unionize(p->n_right, bb); + return; + } + ty = optype(o); + if (ty != LTYPE) + unionize(p->n_left, bb); + if (ty == BITYPE) + unionize(p->n_right, bb); +} + +/* + * Do variable liveness analysis. Only analyze the long-lived + * variables, and save the live-on-exit temporaries in a bit-field + * at the end of each basic block. This bit-field is later used + * when doing short-range liveness analysis in Build(). + */ +static void +LivenessAnalysis(void) +{ + extern struct basicblock bblocks; + struct basicblock *bb; + struct interpass *ip; + int i, bbnum; + + /* + * generate the gen-kill sets for all basic blocks. + */ + DLIST_FOREACH(bb, &bblocks, bbelem) { + bbnum = bb->bbnum; + for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { + /* gen/kill is 'p', this node is 'n' */ + if (ip->type == IP_NODE) + unionize(ip->ip_node, bbnum); + if (ip == bb->first) + break; + } + memcpy(in[bbnum], gen[bbnum], BIT2BYTE(tempmax-tempmin)); +#ifdef PCC_DEBUG + if (rdebug) { + printf("basic block %d\ngen: ", bbnum); + for (i = 0; i < tempmax-tempmin; i++) + if (TESTBIT(gen[bbnum], i)) + printf("%d ", i+tempmin); + printf("\nkill: "); + for (i = 0; i < tempmax-tempmin; i++) + if (TESTBIT(kill[bbnum], i)) + printf("%d ", i+tempmin); + printf("\n"); + } +#endif + } +} + +#define SETCOPY(t,f,i,n) for (i = 0; i < n/NUMBITS; i++) t[i] = f[i] +#define SETSET(t,f,i,n) for (i = 0; i < n/NUMBITS; i++) t[i] |= f[i] +#define SETCLEAR(t,f,i,n) for (i = 0; i < n/NUMBITS; i++) t[i] &= ~f[i] +#define SETCMP(v,t,f,i,n) for (i = 0; i < n/NUMBITS; i++) \ + if (t[i] != f[i]) v = 1 + +/* + * Build the set of interference edges and adjacency list. + */ +static void +Build(struct interpass *ipole) +{ + extern struct basicblock bblocks; + struct basicblock bbfake; + struct interpass *ip; + struct basicblock *bb; + struct cfgnode *cn; + extern int nbblocks; + bittype *saved; + int i, j, again, nbits; + + if (xtemps == 0) { + /* + * No basic block splitup is done if not optimizing, + * so fake one basic block to keep the liveness analysis + * happy. + */ + nbblocks = 1; + bbfake.bbnum = 0; + bbfake.last = DLIST_PREV(ipole, qelem); + bbfake.first = DLIST_NEXT(ipole, qelem); + DLIST_INIT(&bblocks, bbelem); + DLIST_INSERT_AFTER(&bblocks, &bbfake, bbelem); + SLIST_INIT(&bbfake.children); + } + + /* Just fetch space for the temporaries from stack */ + nbits = xbits+(NUMBITS-1); + gen = alloca(nbblocks*sizeof(bittype*)); + kill = alloca(nbblocks*sizeof(bittype*)); + in = alloca(nbblocks*sizeof(bittype*)); + out = alloca(nbblocks*sizeof(bittype*)); + for (i = 0; i < nbblocks; i++) { + BITALLOC(gen[i],alloca,nbits); + BITALLOC(kill[i],alloca,nbits); + BITALLOC(in[i],alloca,nbits); + BITALLOC(out[i],alloca,nbits); + } + BITALLOC(saved,alloca,nbits); + LivenessAnalysis(); + + /* register variable temporaries are live */ + for (i = 0; i < NPERMREG-1; i++) { + if (nsavregs[i]) + continue; + BITSET(out[nbblocks-1], i); + for (j = i+1; j < NPERMREG-1; j++) { + if (nsavregs[j]) + continue; + AddEdge(&nblock[i+tempmin], &nblock[j+tempmin]); + } + } + + /* do liveness analysis on basic block level */ + do { + again = 0; + /* XXX - loop should be in reversed execution-order */ + DLIST_FOREACH_REVERSE(bb, &bblocks, bbelem) { + int i = bb->bbnum; + SETCOPY(saved, out[i], j, nbits); + SLIST_FOREACH(cn, &bb->children, cfgelem) { + SETSET(out[i], in[cn->bblock->bbnum], + j, nbits); + } + SETCMP(again, saved, out[i], j, nbits); + SETCOPY(saved, in[i], j, nbits); + SETCOPY(in[i], out[i], j, nbits); + SETCLEAR(in[i], kill[i], j, nbits); + SETSET(in[i], gen[i], j, nbits); + SETCMP(again, saved, in[i], j, nbits); + } + } while (again); + +#ifdef PCC_DEBUG + if (rdebug) { + DLIST_FOREACH(bb, &bblocks, bbelem) { + printf("basic block %d\nin: ", bb->bbnum); + for (i = 0; i < tempmax-tempmin; i++) + if (TESTBIT(in[bb->bbnum], i)) + printf("%d ", i+tempmin); + printf("\nout: "); + for (i = 0; i < tempmax-tempmin; i++) + if (TESTBIT(out[bb->bbnum], i)) + printf("%d ", i+tempmin); + printf("\n"); + } + } +#endif + + DLIST_FOREACH(bb, &bblocks, bbelem) { + RDEBUG(("liveadd bb %d\n", bb->bbnum)); + i = bb->bbnum; + for (j = 0; j < (tempmax-tempmin); j += NUMBITS) + live[j/NUMBITS] = 0; + SETCOPY(live, out[i], j, nbits); + for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) { + if (ip->type == IP_NODE) + insnwalk(ip->ip_node); + if (ip == bb->first) + break; + } + } + +#ifdef PCC_DEBUG + if (rdebug) { + int i; + struct AdjSet *w; + ADJL *x; + REGW *y; + MOVL *m; + + printf("Interference edges\n"); + for (i = 0; i < 256; i++) { + if ((w = edgehash[i]) == NULL) + continue; + for (; w; w = w->next) + printf("%d <-> %d\n", ASGNUM(w->u), ASGNUM(w->v)); + } + printf("Degrees\n"); + DLIST_FOREACH(y, &initial, link) { + printf("%d (%c): trivial [%d] ", ASGNUM(y), + CLASS(y)+'@', trivially_colorable(y)); + for (x = ADJLIST(y); x; x = x->r_next) { + if (ONLIST(x->a_temp) != &selectStack && + ONLIST(x->a_temp) != &coalescedNodes) + printf("%d ", ASGNUM(x->a_temp)); + else + printf("(%d) ", ASGNUM(x->a_temp)); + } + printf("\n"); + } + printf("Move nodes\n"); + DLIST_FOREACH(y, &initial, link) { + if (MOVELIST(y) == NULL) + continue; + printf("%d: ", ASGNUM(y)); + for (m = MOVELIST(y); m; m = m->next) { + REGW *yy = m->regm->src == y ? + m->regm->dst : m->regm->src; + printf("%d ", ASGNUM(yy)); + } + printf("\n"); + } + } +#endif + +} + +static void +EnableMoves(REGW *n) +{ + MOVL *l; + REGM *m; + + for (l = MOVELIST(n); l; l = l->next) { + m = l->regm; + if (m->queue != ACTIVE) + continue; + DLIST_REMOVE(m, link); + PUSHMLIST(m, worklistMoves, WLIST); + } +} + +static void +EnableAdjMoves(REGW *nodes) +{ + ADJL *w; + REGW *n; + + EnableMoves(nodes); + for (w = ADJLIST(nodes); w; w = w->r_next) { + n = w->a_temp; + if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) + continue; + EnableMoves(w->a_temp); + } +} + +/* + * Decrement the degree of node w for class c. + */ +static void +DecrementDegree(REGW *w, int c) +{ + int wast; + + RRDEBUG(("DecrementDegree: w %d, c %d\n", ASGNUM(w), c)); + + wast = trivially_colorable(w); + NCLASS(w, c)--; + if (wast == trivially_colorable(w)) + return; + + EnableAdjMoves(w); + DELWLIST(w); + ONLIST(w) = 0; + if (MoveRelated(w)) { + PUSHWLIST(w, freezeWorklist); + } else { + PUSHWLIST(w, simplifyWorklist); + } +} + +static void +Simplify(void) +{ + REGW *w; + ADJL *l; + + w = POPWLIST(simplifyWorklist); + PUSHWLIST(w, selectStack); + RDEBUG(("Simplify: node %d class %d\n", ASGNUM(w), w->r_class)); + + l = w->r_adjList; + for (; l; l = l->r_next) { + if (ONLIST(l->a_temp) == &selectStack || + ONLIST(l->a_temp) == &coalescedNodes) + continue; + DecrementDegree(l->a_temp, w->r_class); + } +} + +static REGW * +GetAlias(REGW *n) +{ + if (ONLIST(n) == &coalescedNodes) + return GetAlias(ALIAS(n)); + return n; +} + +static int +OK(REGW *t, REGW *r) +{ + RDEBUG(("OK: t %d CLASS(t) %d adjSet(%d,%d)=%d\n", + ASGNUM(t), CLASS(t), ASGNUM(t), ASGNUM(r), adjSet(t, r))); + +#ifdef PCC_DEBUG + if (rdebug > 1) { + ADJL *w; + int ndeg = 0; + printf("OK degree: "); + for (w = ADJLIST(t); w; w = w->r_next) { + if (ONLIST(w->a_temp) != &selectStack && + ONLIST(w->a_temp) != &coalescedNodes) + printf("%c%d ", CLASS(w->a_temp)+'@', + ASGNUM(w->a_temp)), ndeg++; + else + printf("(%d) ", ASGNUM(w->a_temp)); + } + printf("\n"); +#if 0 + if (ndeg != DEGREE(t) && DEGREE(t) >= 0) + printf("!!!ndeg %d != DEGREE(t) %d\n", ndeg, DEGREE(t)); +#endif + } +#endif + + if (trivially_colorable(t) || ONLIST(t) == &precolored || + (adjSet(t, r) || !aliasmap(CLASS(t), COLOR(r))))/* XXX - check aliasmap */ + return 1; + return 0; +} + +static int +adjok(REGW *v, REGW *u) +{ + ADJL *w; + REGW *t; + + RDEBUG(("adjok\n")); + for (w = ADJLIST(v); w; w = w->r_next) { + t = w->a_temp; + if (ONLIST(t) == &selectStack || ONLIST(t) == &coalescedNodes) + continue; + if (OK(t, u) == 0) + return 0; + } + RDEBUG(("adjok returns OK\n")); + return 1; +} + +#define oldcons /* check some more */ +/* + * Do a conservative estimation of whether two temporaries can + * be coalesced. This is "Briggs-style" check. + * Neither u nor v is precolored when called. + */ +static int +Conservative(REGW *u, REGW *v) +{ + ADJL *w, *ww; + REGW *n; +#ifdef oldcons + int i, ncl[NUMCLASS+1]; + + if (CLASS(u) != CLASS(v)) + comperr("Conservative: u(%d = %d), v(%d = %d)", + ASGNUM(u), CLASS(u), ASGNUM(v), CLASS(v)); + + for (i = 0; i < NUMCLASS+1; i++) + ncl[i] = 0; + + RDEBUG(("Conservative (%d,%d)\n", ASGNUM(u), ASGNUM(v))); + + for (w = ADJLIST(u); w; w = w->r_next) { + n = w->a_temp; + if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) + continue; + for (ww = ADJLIST(v); ww; ww = ww->r_next) + if (ww->a_temp == n) + break; + if (ww) + continue; + if (!trivially_colorable(n)) + ncl[CLASS(n)]++; + } + for (w = ADJLIST(v); w; w = w->r_next) { + n = w->a_temp; + if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) + continue; + if (!trivially_colorable(n)) + ncl[CLASS(n)]++; + } + i = trivially_colorable_p(CLASS(u), ncl); +#endif +{ + int xncl[NUMCLASS+1], mcl = 0, j; + for (j = 0; j < NUMCLASS+1; j++) + xncl[j] = 0; + /* + * Increment xncl[class] up to K for each class. + * If all classes has reached K then check colorability and return. + */ + for (w = ADJLIST(u); w; w = w->r_next) { + n = w->a_temp; + if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) + continue; + if (xncl[CLASS(n)] == regK[CLASS(n)]) + continue; + if (!trivially_colorable(n)) + xncl[CLASS(n)]++; + if (xncl[CLASS(n)] < regK[CLASS(n)]) + continue; + if (++mcl == NUMCLASS) + goto out; /* cannot get more out of it */ + } + for (w = ADJLIST(v); w; w = w->r_next) { + n = w->a_temp; + if (ONLIST(n) == &selectStack || ONLIST(n) == &coalescedNodes) + continue; + if (xncl[CLASS(n)] == regK[CLASS(n)]) + continue; + /* ugly: have we been here already? */ + for (ww = ADJLIST(u); ww; ww = ww->r_next) + if (ww->a_temp == n) + break; + if (ww) + continue; + if (!trivially_colorable(n)) + xncl[CLASS(n)]++; + if (xncl[CLASS(n)] < regK[CLASS(n)]) + continue; + if (++mcl == NUMCLASS) + break; + } +out: j = trivially_colorable_p(CLASS(u), xncl); +#ifdef oldcons + if (j != i) + comperr("Conservative: j %d i %d", j, i); +#else + return j; +#endif +} +#ifdef oldcons + RDEBUG(("Conservative i=%d\n", i)); + return i; +#endif +} + +static void +AddWorkList(REGW *w) +{ + + if (ONLIST(w) != &precolored && !MoveRelated(w) && + trivially_colorable(w)) { + DELWLIST(w); + PUSHWLIST(w, simplifyWorklist); + } +} + +static void +Combine(REGW *u, REGW *v) +{ + MOVL *m; + ADJL *l; + REGW *t; + + RDEBUG(("Combine (%d,%d)\n", ASGNUM(u), ASGNUM(v))); + + if (ONLIST(v) == &freezeWorklist) { + DELWLIST(v); + } else { + DELWLIST(v); + } + PUSHWLIST(v, coalescedNodes); + ALIAS(v) = u; + if (rdebug) { + printf("adjlist(%d): ", ASGNUM(v)); + for (l = ADJLIST(v); l; l = l->r_next) + printf("%d ", l->a_temp->nodnum); + printf("\n"); + } +#if 1 +{ + MOVL *m0 = MOVELIST(v); + + for (m0 = MOVELIST(v); m0; m0 = m0->next) { + for (m = MOVELIST(u); m; m = m->next) + if (m->regm == m0->regm) + break; /* Already on list */ + if (m) + continue; /* already on list */ + MOVELISTADD(u, m0->regm); + } +} +#else + + if ((m = MOVELIST(u))) { + while (m->next) + m = m->next; + m->next = MOVELIST(v); + } else + MOVELIST(u) = MOVELIST(v); +#endif + EnableMoves(v); + for (l = ADJLIST(v); l; l = l->r_next) { + t = l->a_temp; + if (ONLIST(t) == &selectStack || ONLIST(t) == &coalescedNodes) + continue; + /* Do not add edge if u cannot affect the colorability of t */ + /* XXX - check aliasmap */ + if (ONLIST(u) != &precolored || aliasmap(CLASS(t), COLOR(u))) + AddEdge(t, u); + DecrementDegree(t, CLASS(v)); + } + if (!trivially_colorable(u) && ONLIST(u) == &freezeWorklist) { + DELWLIST(u); + PUSHWLIST(u, spillWorklist); + } +if (rdebug) { + ADJL *w; + printf("Combine %d class (%d): ", ASGNUM(u), CLASS(u)); + for (w = ADJLIST(u); w; w = w->r_next) { + if (ONLIST(w->a_temp) != &selectStack && + ONLIST(w->a_temp) != &coalescedNodes) + printf("%d ", ASGNUM(w->a_temp)); + else + printf("(%d) ", ASGNUM(w->a_temp)); + } + printf("\n"); +} +} + +static void +Coalesce(void) +{ + REGM *m; + REGW *x, *y, *u, *v; + + m = POPMLIST(worklistMoves); + x = GetAlias(m->src); + y = GetAlias(m->dst); + + if (ONLIST(y) == &precolored) + u = y, v = x; + else + u = x, v = y; + + RDEBUG(("Coalesce: src %d dst %d u %d v %d x %d y %d\n", + ASGNUM(m->src), ASGNUM(m->dst), ASGNUM(u), ASGNUM(v), + ASGNUM(x), ASGNUM(y))); + + if (CLASS(m->src) != CLASS(m->dst)) + comperr("Coalesce: src class %d, dst class %d", + CLASS(m->src), CLASS(m->dst)); + + if (u == v) { + RDEBUG(("Coalesce: u == v\n")); + PUSHMLIST(m, coalescedMoves, COAL); + AddWorkList(u); + } else if (ONLIST(v) == &precolored || adjSet(u, v)) { + RDEBUG(("Coalesce: constrainedMoves\n")); + PUSHMLIST(m, constrainedMoves, CONSTR); + AddWorkList(u); + AddWorkList(v); + } else if ((ONLIST(u) == &precolored && adjok(v, u)) || + (ONLIST(u) != &precolored && Conservative(u, v))) { + RDEBUG(("Coalesce: Conservative\n")); + PUSHMLIST(m, coalescedMoves, COAL); + Combine(u, v); + AddWorkList(u); + } else { + RDEBUG(("Coalesce: activeMoves\n")); + PUSHMLIST(m, activeMoves, ACTIVE); + } +} + +static void +FreezeMoves(REGW *u) +{ + MOVL *w, *o; + REGM *m; + REGW *z; + REGW *x, *y, *v; + + for (w = MOVELIST(u); w; w = w->next) { + m = w->regm; + if (m->queue != WLIST && m->queue != ACTIVE) + continue; + x = m->src; + y = m->dst; + if (GetAlias(y) == GetAlias(u)) + v = GetAlias(x); + else + v = GetAlias(y); + RDEBUG(("FreezeMoves: u %d (%d,%d) v %d\n", + ASGNUM(u),ASGNUM(x),ASGNUM(y),ASGNUM(v))); + DLIST_REMOVE(m, link); + PUSHMLIST(m, frozenMoves, FROZEN); + if (ONLIST(v) != &freezeWorklist) + continue; + for (o = MOVELIST(v); o; o = o->next) + if (o->regm->queue == WLIST || o->regm->queue == ACTIVE) + break; + if (o == NULL) { + z = v; + DELWLIST(z); + PUSHWLIST(z, simplifyWorklist); + } + } +} + +static void +Freeze(void) +{ + REGW *u; + + /* XXX + * Should check if the moves to freeze have exactly the same + * interference edges. If they do, coalesce them instead, it + * may free up other nodes that they interfere with. + */ + u = POPWLIST(freezeWorklist); + PUSHWLIST(u, simplifyWorklist); + RDEBUG(("Freeze %d\n", ASGNUM(u))); + FreezeMoves(u); +} + +static void +SelectSpill(void) +{ + REGW *w; + + RDEBUG(("SelectSpill\n")); + if (rdebug) + DLIST_FOREACH(w, &spillWorklist, link) + printf("SelectSpill: %d\n", ASGNUM(w)); + + /* First check if we can spill register variables */ + DLIST_FOREACH(w, &spillWorklist, link) { + if (w >= &nblock[tempmin] && w < &nblock[basetemp]) + break; + } + + if (w == &spillWorklist) { + /* try to find another long-range variable */ + DLIST_FOREACH(w, &spillWorklist, link) { + if (w >= &nblock[tempmin] && w < &nblock[tempmax]) + break; + } + } + + if (w == &spillWorklist) { + /* no heuristics, just fetch first element */ + w = DLIST_NEXT(&spillWorklist, link); + } + + DLIST_REMOVE(w, link); + + PUSHWLIST(w, simplifyWorklist); + RDEBUG(("Freezing node %d\n", ASGNUM(w))); + FreezeMoves(w); +} + +int gregn(REGW *); + +int +gregn(REGW *w) +{ + return w->nodnum; +} + +/* + * Set class on long-lived temporaries based on its type. + */ +static void +traclass(NODE *p) +{ + REGW *nb; + + if (p->n_op != TEMP) + return; + + nb = &nblock[(int)p->n_lval]; + if (CLASS(nb) == 0) + CLASS(nb) = gclass(p->n_type); +} + +static void +paint(NODE *p) +{ + struct optab *q; + REGW *w, *ww; + int i; + + if (p->n_regw != NULL) { + /* Must color all allocated regs also */ + ww = w = p->n_regw; + q = &table[TBLIDX(p->n_su)]; + p->n_reg = COLOR(w); + w++; + if (q->needs & ALLNEEDS) + for (i = 0; i < ncnt(q->needs); i++) { + if (w->r_class == -1) + p->n_reg |= ENCRA(COLOR(ww), i); + else + p->n_reg |= ENCRA(COLOR(w), i); + w++; + } + } else + p->n_reg = -1; + if (p->n_op == TEMP) { + REGW *nb = &nblock[(int)p->n_lval]; + p->n_rval = COLOR(nb); + if (TCLASS(p->n_su) == 0) + SCLASS(p->n_su, CLASS(nb)); + p->n_op = REG; + p->n_lval = 0; + } +} + +static void +AssignColors(struct interpass *ip) +{ + int okColors, c; + REGW *o, *w; + ADJL *x; + + RDEBUG(("AssignColors\n")); + while (!WLISTEMPTY(selectStack)) { + w = POPWLIST(selectStack); + okColors = classmask(CLASS(w)); + RDEBUG(("classmask av %d, class %d: %x\n", + w->nodnum, CLASS(w), okColors)); + + for (x = ADJLIST(w); x; x = x->r_next) { + o = GetAlias(x->a_temp); + RRDEBUG(("Adj(%d): %d (%d)\n", + ASGNUM(w), ASGNUM(o), ASGNUM(x->a_temp))); + + if (ONLIST(o) == &coloredNodes || + ONLIST(o) == &precolored) { + c = aliasmap(CLASS(w), COLOR(o)); + RRDEBUG(("aliasmap in class %d by color %d: " + "%x, okColors %x\n", + CLASS(w), COLOR(o), c, okColors)); + + okColors &= ~c; + } + } + if (okColors == 0) { + PUSHWLIST(w, spilledNodes); + RDEBUG(("Spilling node %d\n", ASGNUM(w))); + } else { + PUSHWLIST(w, coloredNodes); + c = ffs(okColors)-1; + COLOR(w) = color2reg(c, CLASS(w)); + RDEBUG(("Coloring %d with %s, free %x\n", + ASGNUM(w), rnames[COLOR(w)], okColors)); + } + } + DLIST_FOREACH(w, &coalescedNodes, link) { + REGW *ww = GetAlias(w); + COLOR(w) = COLOR(ww); + if (ONLIST(ww) == &spilledNodes) { + RDEBUG(("coalesced node %d spilled\n", w->nodnum)); + ww = DLIST_PREV(w, link); + DLIST_REMOVE(w, link); + PUSHWLIST(w, spilledNodes); + w = ww; + } else + RDEBUG(("Giving coalesced node %d color %s\n", + w->nodnum, rnames[COLOR(w)])); + } + + if (rdebug) + DLIST_FOREACH(w, &coloredNodes, link) + printf("%d: color %s\n", ASGNUM(w), rnames[COLOR(w)]); + if (DLIST_ISEMPTY(&spilledNodes, link)) { + struct interpass *ip2; + DLIST_FOREACH(ip2, ip, qelem) + if (ip2->type == IP_NODE) + walkf(ip2->ip_node, paint); + } +} + +static REGW *spole; +/* + * Store all spilled nodes in memory by fetching a temporary on the stack. + * Will never end up here if not optimizing. + */ +static void +longtemp(NODE *p) +{ + REGW *w; + + if (p->n_op != TEMP) + return; + /* XXX - should have a bitmask to find temps to convert */ + DLIST_FOREACH(w, spole, link) { + if (w != &nblock[(int)p->n_lval]) + continue; + if (w->r_class == 0) { + w->r_color = BITOOR(freetemp(szty(p->n_type))); + w->r_class = 1; + } + p->n_op = OREG; + p->n_lval = w->r_color; + p->n_rval = FPREG; + p->n_regw = NULL; + break; + } +} + +static struct interpass *cip; +/* + * Rewrite a tree by storing a variable in memory. + * XXX - must check if basic block structure is destroyed! + */ +static void +shorttemp(NODE *p) +{ + struct interpass *nip; + REGW *w; + NODE *l, *r; + int off; + + /* XXX - optimize this somewhat */ + DLIST_FOREACH(w, spole, link) { + if (w != p->n_regw) + continue; + /* XXX - use canaddr() */ + if (p->n_op == OREG || p->n_op == NAME) { + DLIST_REMOVE(w, link); + RDEBUG(("Node %d already in memory\n", ASGNUM(w))); + break; + } + RDEBUG(("rewriting node %d\n", ASGNUM(w))); + off = BITOOR(freetemp(szty(p->n_type))); + l = mklnode(OREG, off, FPREG, p->n_type); + r = talloc(); + *r = *p; + nip = ipnode(mkbinode(ASSIGN, l, r, p->n_type)); + *p = *l; + DLIST_INSERT_BEFORE(cip, nip, qelem); + DLIST_REMOVE(w, link); + break; + } +} + +/* + * Change the TEMPs in the ipole list to stack variables. + */ +static void +treerewrite(struct interpass *ipole, REGW *rpole) +{ + struct interpass *ip; + + spole = rpole; + + DLIST_FOREACH(ip, ipole, qelem) { + if (ip->type != IP_NODE) + continue; + cip = ip; + walkf(ip->ip_node, shorttemp); /* convert temps to oregs */ + } + if (!DLIST_ISEMPTY(spole, link)) + comperr("treerewrite not empty"); +} + +/* + * Change the TEMPs in the ipole list to stack variables. + */ +static void +leafrewrite(struct interpass *ipole, REGW *rpole) +{ + extern NODE *nodepole; + extern int thisline; + struct interpass *ip; + + spole = rpole; + DLIST_FOREACH(ip, ipole, qelem) { + if (ip->type != IP_NODE) + continue; + nodepole = ip->ip_node; + thisline = ip->lineno; + walkf(ip->ip_node, longtemp); /* convert temps to oregs */ + } + nodepole = NIL; +} + +/* + * Avoid copying spilled argument to new position on stack. + */ +static int +temparg(struct interpass *ipole, REGW *w) +{ + struct interpass *ip; + NODE *p; + + ip = DLIST_NEXT(ipole, qelem); /* PROLOG */ + ip = DLIST_NEXT(ip, qelem); /* first DEFLAB */ + ip = DLIST_NEXT(ip, qelem); /* first NODE */ + for (; ip->type != IP_DEFLAB; ip = DLIST_NEXT(ip, qelem)) { + if (ip->type == IP_ASM) + continue; + p = ip->ip_node; +#ifdef PCC_DEBUG + if (p->n_op != ASSIGN || p->n_left->n_op != TEMP) + comperr("temparg"); +#endif + if (p->n_right->n_op != OREG) + continue; /* arg in register */ + if (w != &nblock[(int)p->n_left->n_lval]) + continue; + w->r_color = p->n_right->n_lval; + tfree(p); + /* Cannot DLIST_REMOVE here, would break basic blocks */ + /* Make it a nothing instead */ + ip->type = IP_ASM; + ip->ip_asm=""; + return 1; + } + return 0; +} + +#define ONLYPERM 1 +#define LEAVES 2 +#define SMALL 3 + +/* + * Scan the whole function and search for temporaries to be stored + * on-stack. + * + * Be careful to not destroy the basic block structure in the first scan. + */ +static int +RewriteProgram(struct interpass *ip) +{ + REGW shortregs, longregs, saveregs, *q; + REGW *w; + int rwtyp; + + RDEBUG(("RewriteProgram\n")); + DLIST_INIT(&shortregs, link); + DLIST_INIT(&longregs, link); + DLIST_INIT(&saveregs, link); + + /* sort the temporaries in three queues, short, long and perm */ + while (!DLIST_ISEMPTY(&spilledNodes, link)) { + w = DLIST_NEXT(&spilledNodes, link); + DLIST_REMOVE(w, link); + + if (w >= &nblock[tempmin] && w < &nblock[basetemp]) { + q = &saveregs; + } else if (w >= &nblock[basetemp] && w < &nblock[tempmax]) { + q = &longregs; + } else + q = &shortregs; + DLIST_INSERT_AFTER(q, w, link); + } +#ifdef PCC_DEBUG + if (rdebug) { + printf("permanent: "); + DLIST_FOREACH(w, &saveregs, link) + printf("%d ", ASGNUM(w)); + printf("\nlong-lived: "); + DLIST_FOREACH(w, &longregs, link) + printf("%d ", ASGNUM(w)); + printf("\nshort-lived: "); + DLIST_FOREACH(w, &shortregs, link) + printf("%d ", ASGNUM(w)); + printf("\n"); + } +#endif + rwtyp = 0; + + if (!DLIST_ISEMPTY(&saveregs, link)) { + rwtyp = ONLYPERM; + DLIST_FOREACH(w, &saveregs, link) { + int num = w - nblock - tempmin; + nsavregs[num] = 1; + } + } + if (!DLIST_ISEMPTY(&longregs, link)) { + rwtyp = LEAVES; + DLIST_FOREACH(w, &longregs, link) { + w->r_class = xtemps ? temparg(ip, w) : 0; + } + } + + if (rwtyp == LEAVES) { + leafrewrite(ip, &longregs); + rwtyp = ONLYPERM; + } + + if (rwtyp == 0 && !DLIST_ISEMPTY(&shortregs, link)) { + /* Must rewrite the trees */ + treerewrite(ip, &shortregs); +// if (xtemps) +// comperr("treerewrite"); + rwtyp = SMALL; + } + + RDEBUG(("savregs %x rwtyp %d\n", 0, rwtyp)); + + return rwtyp; +} + +#ifdef notyet +/* + * Assign instructions, calculate evaluation order and + * set temporary register numbers. + */ +static void +insgen() +{ + geninsn(); /* instruction assignment */ + sucomp(); /* set evaluation order */ + slong(); /* set long temp types */ + sshort(); /* set short temp numbers */ +} +#endif + +/* + * Do register allocation for trees by graph-coloring. + */ +void +ngenregs(struct interpass *ipole) +{ + extern NODE *nodepole; + struct interpass_prolog *ipp, *epp; + struct interpass *ip; + int i, j, nbits = 0; + int uu[NPERMREG] = { -1 }; + int xnsavregs[NPERMREG]; + int beenhere = 0; + + DLIST_INIT(&lunused, link); + DLIST_INIT(&lused, link); + + /* + * Do some setup before doing the real thing. + */ + ipp = (struct interpass_prolog *)DLIST_NEXT(ipole, qelem); + epp = (struct interpass_prolog *)DLIST_PREV(ipole, qelem); + + tempmin = ipp->ip_tmpnum; + tempmax = epp->ip_tmpnum; + + /* + * Allocate space for the permanent registers in the + * same block as the long-lived temporaries. + * These temporaries will be handled the same way as + * all other variables. + */ + basetemp = tempmin; + nsavregs = xnsavregs; + for (i = 0; i < NPERMREG; i++) + xnsavregs[i] = 0; + ndontregs = uu; /* currently never avoid any regs */ + + tempmin -= (NPERMREG-1); +#ifdef notyet + if (xavoidfp) + dontregs |= REGBIT(FPREG); +#endif + +#ifdef PCC_DEBUG + nodnum = tempmax; +#endif + nbits = xbits = tempmax - tempmin; + if (nbits) { + nblock = tmpalloc(nbits * sizeof(REGW)); + + nblock -= tempmin; + live = tmpalloc(BIT2BYTE(nbits)); + RDEBUG(("nblock %p num %d size %d\n", + nblock, nbits, (int)(nbits * sizeof(REGW)))); + } + + + /* Block for precolored nodes */ + ablock = tmpalloc(sizeof(REGW)*MAXREGS); + memset(ablock, 0, sizeof(REGW)*MAXREGS); + for (i = 0; i < MAXREGS; i++) { + ablock[i].r_onlist = &precolored; + ablock[i].r_class = GCLASS(i); /* XXX */ + ablock[i].r_color = i; +#ifdef PCC_DEBUG + ablock[i].nodnum = i; +#endif + } +#ifdef notyet + TMPMARK(); +#endif + + +recalc: +onlyperm: /* XXX - should not have to redo all */ + + if (nbits) { + memset(nblock+tempmin, 0, nbits * sizeof(REGW)); + memset(live, 0, BIT2BYTE(nbits)); + memset(edgehash, 0, sizeof(edgehash)); +#ifdef PCC_DEBUG + for (i = tempmin; i < tempmax; i++) + nblock[i].nodnum = i; +#endif + } + RPRINTIP(ipole); + DLIST_INIT(&initial, link); + DLIST_FOREACH(ip, ipole, qelem) { + extern int thisline; + if (ip->type != IP_NODE) + continue; + nodepole = ip->ip_node; + thisline = ip->lineno; + geninsn(ip->ip_node, FOREFF); + nsucomp(ip->ip_node); + walkf(ip->ip_node, traclass); + } + nodepole = NIL; + RDEBUG(("nsucomp allocated %d temps (%d,%d)\n", + tempmax-tempmin, tempmin, tempmax)); + + RPRINTIP(ipole); + RDEBUG(("ngenregs: numtemps %d (%d, %d)\n", tempmax-tempmin, + tempmin, tempmax)); + + DLIST_INIT(&coalescedMoves, link); + DLIST_INIT(&constrainedMoves, link); + DLIST_INIT(&frozenMoves, link); + DLIST_INIT(&worklistMoves, link); + DLIST_INIT(&activeMoves, link); + + /* Set class and move-related for perm regs */ + for (i = 0; i < (NPERMREG-1); i++) { + if (nsavregs[i]) + continue; + nblock[i+tempmin].r_class = GCLASS(permregs[i]); + DLIST_INSERT_AFTER(&initial, &nblock[i+tempmin], link); + moveadd(&nblock[i+tempmin], &ablock[permregs[i]]); + addalledges(&nblock[i+tempmin]); + } + + Build(ipole); + RDEBUG(("Build done\n")); + MkWorklist(); + RDEBUG(("MkWorklist done\n")); + do { + if (!WLISTEMPTY(simplifyWorklist)) + Simplify(); + else if (!WLISTEMPTY(worklistMoves)) + Coalesce(); + else if (!WLISTEMPTY(freezeWorklist)) + Freeze(); + else if (!WLISTEMPTY(spillWorklist)) + SelectSpill(); + } while (!WLISTEMPTY(simplifyWorklist) || !WLISTEMPTY(worklistMoves) || + !WLISTEMPTY(freezeWorklist) || !WLISTEMPTY(spillWorklist)); + AssignColors(ipole); + + RDEBUG(("After AssignColors\n")); + RPRINTIP(ipole); + + if (!WLISTEMPTY(spilledNodes)) { + switch (RewriteProgram(ipole)) { + case ONLYPERM: + goto onlyperm; + case SMALL: + optimize(ipole); + if (beenhere++ == MAXLOOP) + comperr("beenhere"); + goto recalc; + } + } + + /* fill in regs to save */ + ipp->ipp_regs = 0; + for (i = 0; i < NPERMREG-1; i++) { + NODE *p; + + if (nsavregs[i]) { + ipp->ipp_regs |= (1 << permregs[i]); + continue; /* Spilled */ + } + if (nblock[i+tempmin].r_color == permregs[i]) + continue; /* Coalesced */ + /* + * If the original color of this permreg is used for + * coloring another register, swap them to avoid + * unneccessary moves. + */ + for (j = i+1; j < NPERMREG-1; j++) { + if (nblock[j+tempmin].r_color != permregs[i]) + continue; + nblock[j+tempmin].r_color = nblock[i+tempmin].r_color; + break; + } + if (j != NPERMREG-1) + continue; + + /* Generate reg-reg move nodes for save */ + p = mkbinode(ASSIGN, + mklnode(REG, 0, nblock[i+tempmin].r_color, INT), + mklnode(REG, 0, permregs[i], INT), INT); + p->n_reg = p->n_left->n_reg = p->n_right->n_reg = -1; + p->n_left->n_su = p->n_right->n_su = 0; + geninsn(p, FOREFF); + ip = ipnode(p); + DLIST_INSERT_AFTER(ipole->qelem.q_forw, ip, qelem); + /* XXX not int */ + p = mkbinode(ASSIGN, mklnode(REG, 0, permregs[i], INT), + mklnode(REG, 0, nblock[i+tempmin].r_color, INT), INT); + p->n_reg = p->n_left->n_reg = p->n_right->n_reg = -1; + p->n_left->n_su = p->n_right->n_su = 0; + geninsn(p, FOREFF); + ip = ipnode(p); + DLIST_INSERT_BEFORE(ipole->qelem.q_back, ip, qelem); + } + epp->ipp_regs = ipp->ipp_regs; + /* Done! */ +} |