qbe

Internal scc patchset buffer for QBE
Log | Files | Refs | README | LICENSE

parse.c (23072B)


      1 #include "all.h"
      2 #include <ctype.h>
      3 #include <stdarg.h>
      4 
      5 enum {
      6 	Ke = -2, /* Erroneous mode */
      7 	Km = Kl, /* Memory pointer */
      8 };
      9 
     10 Op optab[NOp] = {
     11 #define O(op, t, cf) [O##op]={#op, t, cf},
     12 	#include "ops.h"
     13 };
     14 
     15 typedef enum {
     16 	PXXX,
     17 	PLbl,
     18 	PPhi,
     19 	PIns,
     20 	PEnd,
     21 } PState;
     22 
     23 enum {
     24 	Txxx = 0,
     25 
     26 	/* aliases */
     27 	Tloadw = NPubOp,
     28 	Tloadl,
     29 	Tloads,
     30 	Tloadd,
     31 	Talloc1,
     32 	Talloc2,
     33 
     34 	Tcall,
     35 	Tenv,
     36 	Tphi,
     37 	Tjmp,
     38 	Tjnz,
     39 	Tret,
     40 	Texport,
     41 	Tfunc,
     42 	Ttype,
     43 	Tdata,
     44 	Tsection,
     45 	Talign,
     46 	Tl,
     47 	Tw,
     48 	Th,
     49 	Tb,
     50 	Td,
     51 	Ts,
     52 	Tz,
     53 
     54 	Tint,
     55 	Tflts,
     56 	Tfltd,
     57 	Ttmp,
     58 	Tlbl,
     59 	Tglo,
     60 	Ttyp,
     61 	Tstr,
     62 
     63 	Tplus,
     64 	Teq,
     65 	Tcomma,
     66 	Tlparen,
     67 	Trparen,
     68 	Tlbrace,
     69 	Trbrace,
     70 	Tnl,
     71 	Tdots,
     72 	Teof,
     73 
     74 	Ntok
     75 };
     76 
     77 static char *kwmap[Ntok] = {
     78 	[Tloadw] = "loadw",
     79 	[Tloadl] = "loadl",
     80 	[Tloads] = "loads",
     81 	[Tloadd] = "loadd",
     82 	[Talloc1] = "alloc1",
     83 	[Talloc2] = "alloc2",
     84 	[Tcall] = "call",
     85 	[Tenv] = "env",
     86 	[Tphi] = "phi",
     87 	[Tjmp] = "jmp",
     88 	[Tjnz] = "jnz",
     89 	[Tret] = "ret",
     90 	[Texport] = "export",
     91 	[Tfunc] = "function",
     92 	[Ttype] = "type",
     93 	[Tdata] = "data",
     94 	[Tsection] = "section",
     95 	[Talign] = "align",
     96 	[Tl] = "l",
     97 	[Tw] = "w",
     98 	[Th] = "h",
     99 	[Tb] = "b",
    100 	[Td] = "d",
    101 	[Ts] = "s",
    102 	[Tz] = "z",
    103 	[Tdots] = "...",
    104 };
    105 
    106 enum {
    107 	NPred = 63,
    108 
    109 	TMask = 16383, /* for temps hash */
    110 	BMask = 8191, /* for blocks hash */
    111 
    112 	K = 3233235, /* found using tools/lexh.c */
    113 	M = 23,
    114 };
    115 
    116 static char lexh[1 << (32-M)];
    117 static FILE *inf;
    118 static char *inpath;
    119 static int thead;
    120 static struct {
    121 	char chr;
    122 	double fltd;
    123 	float flts;
    124 	int64_t num;
    125 	char *str;
    126 } tokval;
    127 static int lnum;
    128 
    129 static Fn *curf;
    130 static int tmph[TMask+1];
    131 static Phi **plink;
    132 static Blk *curb;
    133 static Blk **blink;
    134 static Blk *blkh[BMask+1];
    135 static int nblk;
    136 static int rcls;
    137 static uint ntyp;
    138 
    139 void
    140 err(char *s, ...)
    141 {
    142 	va_list ap;
    143 
    144 	va_start(ap, s);
    145 	fprintf(stderr, "%s:%d: ", inpath, lnum);
    146 	vfprintf(stderr, s, ap);
    147 	fprintf(stderr, "\n");
    148 	va_end(ap);
    149 	exit(1);
    150 }
    151 
    152 static void
    153 lexinit()
    154 {
    155 	static int done;
    156 	int i;
    157 	long h;
    158 
    159 	if (done)
    160 		return;
    161 	for (i=0; i<NPubOp; ++i)
    162 		if (optab[i].name)
    163 			kwmap[i] = optab[i].name;
    164 	assert(Ntok <= CHAR_MAX);
    165 	for (i=0; i<Ntok; ++i)
    166 		if (kwmap[i]) {
    167 			h = hash(kwmap[i])*K >> M;
    168 			assert(lexh[h] == Txxx);
    169 			lexh[h] = i;
    170 		}
    171 	done = 1;
    172 }
    173 
    174 static int64_t
    175 getint()
    176 {
    177 	uint64_t n;
    178 	int c, m;
    179 
    180 	n = 0;
    181 	c = fgetc(inf);
    182 	m = (c == '-');
    183 	if (m || c == '+')
    184 		c = fgetc(inf);
    185 	do {
    186 		n = 10*n + (c - '0');
    187 		c = fgetc(inf);
    188 	} while ('0' <= c && c <= '9');
    189 	ungetc(c, inf);
    190 	if (m)
    191 		n = 1 + ~n;
    192 	return *(int64_t *)&n;
    193 }
    194 
    195 static int
    196 lex()
    197 {
    198 	static char tok[NString];
    199 	int c, i, esc;
    200 	int t;
    201 
    202 	do
    203 		c = fgetc(inf);
    204 	while (isblank(c));
    205 	t = Txxx;
    206 	tokval.chr = c;
    207 	switch (c) {
    208 	case EOF:
    209 		return Teof;
    210 	case ',':
    211 		return Tcomma;
    212 	case '(':
    213 		return Tlparen;
    214 	case ')':
    215 		return Trparen;
    216 	case '{':
    217 		return Tlbrace;
    218 	case '}':
    219 		return Trbrace;
    220 	case '=':
    221 		return Teq;
    222 	case '+':
    223 		return Tplus;
    224 	case 's':
    225 		if (fscanf(inf, "_%f", &tokval.flts) != 1)
    226 			break;
    227 		return Tflts;
    228 	case 'd':
    229 		if (fscanf(inf, "_%lf", &tokval.fltd) != 1)
    230 			break;
    231 		return Tfltd;
    232 	case '%':
    233 		t = Ttmp;
    234 		c = fgetc(inf);
    235 		goto Alpha;
    236 	case '@':
    237 		t = Tlbl;
    238 		c = fgetc(inf);
    239 		goto Alpha;
    240 	case '$':
    241 		t = Tglo;
    242 		if ((c = fgetc(inf)) == '"')
    243 			goto Quoted;
    244 		goto Alpha;
    245 	case ':':
    246 		t = Ttyp;
    247 		c = fgetc(inf);
    248 		goto Alpha;
    249 	case '#':
    250 		while ((c=fgetc(inf)) != '\n' && c != EOF)
    251 			;
    252 		/* fall through */
    253 	case '\n':
    254 		lnum++;
    255 		return Tnl;
    256 	}
    257 	if (isdigit(c) || c == '-' || c == '+') {
    258 		ungetc(c, inf);
    259 		tokval.num = getint();
    260 		return Tint;
    261 	}
    262 	if (c == '"') {
    263 		t = Tstr;
    264 	Quoted:
    265 		tokval.str = vnew(2, 1, Pfn);
    266 		tokval.str[0] = c;
    267 		esc = 0;
    268 		for (i=1;; i++) {
    269 			c = fgetc(inf);
    270 			if (c == EOF)
    271 				err("unterminated string");
    272 			vgrow(&tokval.str, i+2);
    273 			tokval.str[i] = c;
    274 			if (c == '"' && !esc) {
    275 				tokval.str[i+1] = 0;
    276 				return t;
    277 			}
    278 			esc = (c == '\\' && !esc);
    279 		}
    280 	}
    281 Alpha:
    282 	if (!isalpha(c) && c != '.' && c != '_')
    283 		err("invalid character %c (%d)", c, c);
    284 	i = 0;
    285 	do {
    286 		if (i >= NString-1)
    287 			err("identifier too long");
    288 		tok[i++] = c;
    289 		c = fgetc(inf);
    290 	} while (isalpha(c) || c == '$' || c == '.' || c == '_' || isdigit(c));
    291 	tok[i] = 0;
    292 	ungetc(c, inf);
    293 	tokval.str = tok;
    294 	if (t != Txxx) {
    295 		return t;
    296 	}
    297 	t = lexh[hash(tok)*K >> M];
    298 	if (t == Txxx || strcmp(kwmap[t], tok) != 0) {
    299 		err("unknown keyword %s", tok);
    300 		return Txxx;
    301 	}
    302 	return t;
    303 }
    304 
    305 static int
    306 peek()
    307 {
    308 	if (thead == Txxx)
    309 		thead = lex();
    310 	return thead;
    311 }
    312 
    313 static int
    314 next()
    315 {
    316 	int t;
    317 
    318 	t = peek();
    319 	thead = Txxx;
    320 	return t;
    321 }
    322 
    323 static int
    324 nextnl()
    325 {
    326 	int t;
    327 
    328 	while ((t = next()) == Tnl)
    329 		;
    330 	return t;
    331 }
    332 
    333 static void
    334 expect(int t)
    335 {
    336 	static char *ttoa[] = {
    337 		[Tlbl] = "label",
    338 		[Tcomma] = ",",
    339 		[Teq] = "=",
    340 		[Tnl] = "newline",
    341 		[Tlparen] = "(",
    342 		[Trparen] = ")",
    343 		[Tlbrace] = "{",
    344 		[Trbrace] = "}",
    345 		[Teof] = 0,
    346 	};
    347 	char buf[128], *s1, *s2;
    348 	int t1;
    349 
    350 	t1 = next();
    351 	if (t == t1)
    352 		return;
    353 	s1 = ttoa[t] ? ttoa[t] : "??";
    354 	s2 = ttoa[t1] ? ttoa[t1] : "??";
    355 	sprintf(buf, "%s expected, got %s instead", s1, s2);
    356 	err(buf);
    357 }
    358 
    359 static Ref
    360 tmpref(char *v)
    361 {
    362 	int t, *h;
    363 
    364 	h = &tmph[hash(v) & TMask];
    365 	t = *h;
    366 	if (t) {
    367 		if (strcmp(curf->tmp[t].name, v) == 0)
    368 			return TMP(t);
    369 		for (t=curf->ntmp-1; t>=Tmp0; t--)
    370 			if (strcmp(curf->tmp[t].name, v) == 0)
    371 				return TMP(t);
    372 	}
    373 	t = curf->ntmp;
    374 	*h = t;
    375 	newtmp(0, Kx, curf);
    376 	strcpy(curf->tmp[t].name, v);
    377 	return TMP(t);
    378 }
    379 
    380 static Ref
    381 parseref()
    382 {
    383 	Con c;
    384 	int i;
    385 
    386 	memset(&c, 0, sizeof c);
    387 	switch (next()) {
    388 	case Ttmp:
    389 		return tmpref(tokval.str);
    390 	case Tint:
    391 		c.type = CBits;
    392 		c.bits.i = tokval.num;
    393 		goto Look;
    394 	case Tflts:
    395 		c.type = CBits;
    396 		c.bits.s = tokval.flts;
    397 		c.flt = 1;
    398 		goto Look;
    399 	case Tfltd:
    400 		c.type = CBits;
    401 		c.bits.d = tokval.fltd;
    402 		c.flt = 2;
    403 		goto Look;
    404 	case Tglo:
    405 		c.type = CAddr;
    406 		c.label = intern(tokval.str);
    407 	Look:
    408 		for (i=0; i<curf->ncon; i++)
    409 			if (curf->con[i].type == c.type
    410 			&& curf->con[i].bits.i == c.bits.i
    411 			&& curf->con[i].label == c.label)
    412 				return CON(i);
    413 		vgrow(&curf->con, ++curf->ncon);
    414 		curf->con[i] = c;
    415 		return CON(i);
    416 	default:
    417 		return R;
    418 	}
    419 }
    420 
    421 static int
    422 findtyp(int i)
    423 {
    424 	while (--i >= 0)
    425 		if (strcmp(tokval.str, typ[i].name) == 0)
    426 			return i;
    427 	err("undefined type :%s", tokval.str);
    428 }
    429 
    430 static int
    431 parsecls(int *tyn)
    432 {
    433 	switch (next()) {
    434 	default:
    435 		err("invalid class specifier");
    436 	case Ttyp:
    437 		*tyn = findtyp(ntyp);
    438 		return 4;
    439 	case Tw:
    440 		return Kw;
    441 	case Tl:
    442 		return Kl;
    443 	case Ts:
    444 		return Ks;
    445 	case Td:
    446 		return Kd;
    447 	}
    448 }
    449 
    450 static int
    451 parserefl(int arg)
    452 {
    453 	int k, ty, env, hasenv, vararg;
    454 	Ref r;
    455 
    456 	hasenv = 0;
    457 	vararg = 0;
    458 	expect(Tlparen);
    459 	while (peek() != Trparen) {
    460 		if (curi - insb >= NIns)
    461 			err("too many instructions (1)");
    462 		if (!arg && vararg)
    463 			err("no parameters allowed after '...'");
    464 		switch (peek()) {
    465 		case Tdots:
    466 			if (vararg)
    467 				err("only one '...' allowed");
    468 			vararg = 1;
    469 			if (arg) {
    470 				*curi = (Ins){.op = Oargv};
    471 				curi++;
    472 			}
    473 			next();
    474 			goto Next;
    475 		case Tenv:
    476 			if (hasenv)
    477 				err("only one environment allowed");
    478 			hasenv = 1;
    479 			env = 1;
    480 			next();
    481 			k = Kl;
    482 			break;
    483 		default:
    484 			env = 0;
    485 			k = parsecls(&ty);
    486 			break;
    487 		}
    488 		r = parseref();
    489 		if (req(r, R))
    490 			err("invalid argument");
    491 		if (!arg && rtype(r) != RTmp)
    492 			err("invalid function parameter");
    493 		if (k == 4)
    494 			if (arg)
    495 				*curi = (Ins){Oargc, Kl, R, {TYPE(ty), r}};
    496 			else
    497 				*curi = (Ins){Oparc, Kl, r, {TYPE(ty)}};
    498 		else if (env)
    499 			if (arg)
    500 				*curi = (Ins){Oarge, k, R, {r}};
    501 			else
    502 				*curi = (Ins){Opare, k, r, {R}};
    503 		else
    504 			if (arg)
    505 				*curi = (Ins){Oarg, k, R, {r}};
    506 			else
    507 				*curi = (Ins){Opar, k, r, {R}};
    508 		curi++;
    509 	Next:
    510 		if (peek() == Trparen)
    511 			break;
    512 		expect(Tcomma);
    513 	}
    514 	expect(Trparen);
    515 	return vararg;
    516 }
    517 
    518 static Blk *
    519 findblk(char *name)
    520 {
    521 	Blk *b;
    522 	uint32_t h;
    523 
    524 	h = hash(name) & BMask;
    525 	for (b=blkh[h]; b; b=b->dlink)
    526 		if (strcmp(b->name, name) == 0)
    527 			return b;
    528 	b = blknew();
    529 	b->id = nblk++;
    530 	strcpy(b->name, name);
    531 	b->dlink = blkh[h];
    532 	blkh[h] = b;
    533 	return b;
    534 }
    535 
    536 static void
    537 closeblk()
    538 {
    539 	curb->nins = curi - insb;
    540 	idup(&curb->ins, insb, curb->nins);
    541 	blink = &curb->link;
    542 	curi = insb;
    543 }
    544 
    545 static PState
    546 parseline(PState ps)
    547 {
    548 	Ref arg[NPred] = {R};
    549 	Blk *blk[NPred];
    550 	Phi *phi;
    551 	Ref r;
    552 	Blk *b;
    553 	int t, op, i, k, ty;
    554 
    555 	t = nextnl();
    556 	if (ps == PLbl && t != Tlbl && t != Trbrace)
    557 		err("label or } expected");
    558 	switch (t) {
    559 	default:
    560 		if (isstore(t)) {
    561 		case Tcall:
    562 		case Ovastart:
    563 			/* operations without result */
    564 			r = R;
    565 			k = Kw;
    566 			op = t;
    567 			goto DoOp;
    568 		}
    569 		err("label, instruction or jump expected");
    570 	case Trbrace:
    571 		return PEnd;
    572 	case Ttmp:
    573 		break;
    574 	case Tlbl:
    575 		b = findblk(tokval.str);
    576 		if (curb && curb->jmp.type == Jxxx) {
    577 			closeblk();
    578 			curb->jmp.type = Jjmp;
    579 			curb->s1 = b;
    580 		}
    581 		if (b->jmp.type != Jxxx)
    582 			err("multiple definitions of block @%s", b->name);
    583 		*blink = b;
    584 		curb = b;
    585 		plink = &curb->phi;
    586 		expect(Tnl);
    587 		return PPhi;
    588 	case Tret:
    589 		curb->jmp.type = (int[]){
    590 			Jretw, Jretl,
    591 			Jrets, Jretd,
    592 			Jretc, Jret0
    593 		}[rcls];
    594 		if (peek() == Tnl)
    595 			curb->jmp.type = Jret0;
    596 		else if (rcls < 5) {
    597 			r = parseref();
    598 			if (req(r, R))
    599 				err("invalid return value");
    600 			curb->jmp.arg = r;
    601 		}
    602 		goto Close;
    603 	case Tjmp:
    604 		curb->jmp.type = Jjmp;
    605 		goto Jump;
    606 	case Tjnz:
    607 		curb->jmp.type = Jjnz;
    608 		r = parseref();
    609 		if (req(r, R))
    610 			err("invalid argument for jnz jump");
    611 		curb->jmp.arg = r;
    612 		expect(Tcomma);
    613 	Jump:
    614 		expect(Tlbl);
    615 		curb->s1 = findblk(tokval.str);
    616 		if (curb->jmp.type != Jjmp) {
    617 			expect(Tcomma);
    618 			expect(Tlbl);
    619 			curb->s2 = findblk(tokval.str);
    620 		}
    621 		if (curb->s1 == curf->start || curb->s2 == curf->start)
    622 			err("invalid jump to the start node");
    623 	Close:
    624 		expect(Tnl);
    625 		closeblk();
    626 		return PLbl;
    627 	}
    628 	r = tmpref(tokval.str);
    629 	expect(Teq);
    630 	k = parsecls(&ty);
    631 	op = next();
    632 DoOp:
    633 	if (op == Tphi) {
    634 		if (ps != PPhi || curb == curf->start)
    635 			err("unexpected phi instruction");
    636 		op = -1;
    637 	}
    638 	if (op == Tcall) {
    639 		arg[0] = parseref();
    640 		parserefl(1);
    641 		op = Ocall;
    642 		expect(Tnl);
    643 		if (k == 4) {
    644 			k = Kl;
    645 			arg[1] = TYPE(ty);
    646 		} else
    647 			arg[1] = R;
    648 		goto Ins;
    649 	}
    650 	if (op == Tloadw)
    651 		op = Oloadsw;
    652 	if (op >= Tloadl && op <= Tloadd)
    653 		op = Oload;
    654 	if (op == Talloc1 || op == Talloc2)
    655 		op = Oalloc;
    656 	if (k == 4)
    657 		err("size class must be w, l, s, or d");
    658 	if (op >= NPubOp)
    659 		err("invalid instruction");
    660 	i = 0;
    661 	if (peek() != Tnl)
    662 		for (;;) {
    663 			if (i == NPred)
    664 				err("too many arguments");
    665 			if (op == -1) {
    666 				expect(Tlbl);
    667 				blk[i] = findblk(tokval.str);
    668 			}
    669 			arg[i] = parseref();
    670 			if (req(arg[i], R))
    671 				err("invalid instruction argument");
    672 			i++;
    673 			t = peek();
    674 			if (t == Tnl)
    675 				break;
    676 			if (t != Tcomma)
    677 				err(", or end of line expected");
    678 			next();
    679 		}
    680 	next();
    681 Ins:
    682 	if (op != -1) {
    683 		if (curi - insb >= NIns)
    684 			err("too many instructions (2)");
    685 		curi->op = op;
    686 		curi->cls = k;
    687 		curi->to = r;
    688 		curi->arg[0] = arg[0];
    689 		curi->arg[1] = arg[1];
    690 		curi++;
    691 		return PIns;
    692 	} else {
    693 		phi = alloc(sizeof *phi);
    694 		phi->to = r;
    695 		phi->cls = k;
    696 		phi->arg = vnew(i, sizeof arg[0], Pfn);
    697 		memcpy(phi->arg, arg, i * sizeof arg[0]);
    698 		phi->blk = vnew(i, sizeof blk[0], Pfn);
    699 		memcpy(phi->blk, blk, i * sizeof blk[0]);
    700 		phi->narg = i;
    701 		*plink = phi;
    702 		plink = &phi->link;
    703 		return PPhi;
    704 	}
    705 }
    706 
    707 static int
    708 usecheck(Ref r, int k, Fn *fn)
    709 {
    710 	return rtype(r) != RTmp || fn->tmp[r.val].cls == k
    711 		|| (fn->tmp[r.val].cls == Kl && k == Kw);
    712 }
    713 
    714 static void
    715 typecheck(Fn *fn)
    716 {
    717 	Blk *b;
    718 	Phi *p;
    719 	Ins *i;
    720 	uint n;
    721 	int k;
    722 	Tmp *t;
    723 	Ref r;
    724 	BSet pb[1], ppb[1];
    725 
    726 	fillpreds(fn);
    727 	bsinit(pb, fn->nblk);
    728 	bsinit(ppb, fn->nblk);
    729 	for (b=fn->start; b; b=b->link) {
    730 		for (p=b->phi; p; p=p->link)
    731 			fn->tmp[p->to.val].cls = p->cls;
    732 		for (i=b->ins; i<&b->ins[b->nins]; i++)
    733 			if (rtype(i->to) == RTmp) {
    734 				t = &fn->tmp[i->to.val];
    735 				if (clsmerge(&t->cls, i->cls))
    736 					err("temporary %%%s is assigned with"
    737 						" multiple types", t->name);
    738 			}
    739 	}
    740 	for (b=fn->start; b; b=b->link) {
    741 		bszero(pb);
    742 		for (n=0; n<b->npred; n++)
    743 			bsset(pb, b->pred[n]->id);
    744 		for (p=b->phi; p; p=p->link) {
    745 			bszero(ppb);
    746 			t = &fn->tmp[p->to.val];
    747 			for (n=0; n<p->narg; n++) {
    748 				k = t->cls;
    749 				if (bshas(ppb, p->blk[n]->id))
    750 					err("multiple entries for @%s in phi %%%s",
    751 						p->blk[n]->name, t->name);
    752 				if (!usecheck(p->arg[n], k, fn))
    753 					err("invalid type for operand %%%s in phi %%%s",
    754 						fn->tmp[p->arg[n].val].name, t->name);
    755 				bsset(ppb, p->blk[n]->id);
    756 			}
    757 			if (!bsequal(pb, ppb))
    758 				err("predecessors not matched in phi %%%s", t->name);
    759 		}
    760 		for (i=b->ins; i<&b->ins[b->nins]; i++)
    761 			for (n=0; n<2; n++) {
    762 				k = optab[i->op].argcls[n][i->cls];
    763 				r = i->arg[n];
    764 				t = &fn->tmp[r.val];
    765 				if (k == Ke)
    766 					err("invalid instruction type in %s",
    767 						optab[i->op].name);
    768 				if (rtype(r) == RType)
    769 					continue;
    770 				if (rtype(r) != -1 && k == Kx)
    771 					err("no %s operand expected in %s",
    772 						n == 1 ? "second" : "first",
    773 						optab[i->op].name);
    774 				if (rtype(r) == -1 && k != Kx)
    775 					err("missing %s operand in %s",
    776 						n == 1 ? "second" : "first",
    777 						optab[i->op].name);
    778 				if (!usecheck(r, k, fn))
    779 					err("invalid type for %s operand %%%s in %s",
    780 						n == 1 ? "second" : "first",
    781 						t->name, optab[i->op].name);
    782 			}
    783 		r = b->jmp.arg;
    784 		if (isret(b->jmp.type)) {
    785 			if (b->jmp.type == Jretc) {
    786 				if (!usecheck(r, Kl, fn))
    787 					goto JErr;
    788 			} else if (!usecheck(r, b->jmp.type-Jretw, fn))
    789 				goto JErr;
    790 		}
    791 		if (b->jmp.type == Jjnz && !usecheck(r, Kw, fn))
    792 		JErr:
    793 			err("invalid type for jump argument %%%s in block @%s",
    794 				fn->tmp[r.val].name, b->name);
    795 		if (b->s1 && b->s1->jmp.type == Jxxx)
    796 			err("block @%s is used undefined", b->s1->name);
    797 		if (b->s2 && b->s2->jmp.type == Jxxx)
    798 			err("block @%s is used undefined", b->s2->name);
    799 	}
    800 }
    801 
    802 static Fn *
    803 parsefn(int export)
    804 {
    805 	Blk *b;
    806 	int i;
    807 	PState ps;
    808 
    809 	curb = 0;
    810 	nblk = 0;
    811 	curi = insb;
    812 	curf = alloc(sizeof *curf);
    813 	curf->ntmp = 0;
    814 	curf->ncon = 1; /* first constant must be 0 */
    815 	curf->tmp = vnew(curf->ntmp, sizeof curf->tmp[0], Pfn);
    816 	curf->con = vnew(curf->ncon, sizeof curf->con[0], Pfn);
    817 	for (i=0; i<Tmp0; ++i)
    818 		if (T.fpr0 <= i && i < T.fpr0 + T.nfpr)
    819 			newtmp(0, Kd, curf);
    820 		else
    821 			newtmp(0, Kl, curf);
    822 	curf->con[0].type = CBits;
    823 	curf->export = export;
    824 	blink = &curf->start;
    825 	curf->retty = Kx;
    826 	if (peek() != Tglo)
    827 		rcls = parsecls(&curf->retty);
    828 	else
    829 		rcls = 5;
    830 	if (next() != Tglo)
    831 		err("function name expected");
    832 	strncpy(curf->name, tokval.str, NString-1);
    833 	curf->vararg = parserefl(0);
    834 	if (nextnl() != Tlbrace)
    835 		err("function body must start with {");
    836 	ps = PLbl;
    837 	do
    838 		ps = parseline(ps);
    839 	while (ps != PEnd);
    840 	if (!curb)
    841 		err("empty function");
    842 	if (curb->jmp.type == Jxxx)
    843 		err("last block misses jump");
    844 	curf->mem = vnew(0, sizeof curf->mem[0], Pfn);
    845 	curf->nmem = 0;
    846 	curf->nblk = nblk;
    847 	curf->rpo = 0;
    848 	for (b=0; b; b=b->link)
    849 		b->dlink = 0; /* was trashed by findblk() */
    850 	for (i=0; i<BMask+1; ++i)
    851 		blkh[i] = 0;
    852 	memset(tmph, 0, sizeof tmph);
    853 	typecheck(curf);
    854 	return curf;
    855 }
    856 
    857 static void
    858 parsefields(Field *fld, Typ *ty, int t)
    859 {
    860 	Typ *ty1;
    861 	int n, c, a, al, type;
    862 	uint64_t sz, s;
    863 
    864 	n = 0;
    865 	sz = 0;
    866 	al = ty->align;
    867 	while (t != Trbrace) {
    868 		ty1 = 0;
    869 		switch (t) {
    870 		default: err("invalid type member specifier");
    871 		case Td: type = Fd; s = 8; a = 3; break;
    872 		case Tl: type = Fl; s = 8; a = 3; break;
    873 		case Ts: type = Fs; s = 4; a = 2; break;
    874 		case Tw: type = Fw; s = 4; a = 2; break;
    875 		case Th: type = Fh; s = 2; a = 1; break;
    876 		case Tb: type = Fb; s = 1; a = 0; break;
    877 		case Ttyp:
    878 			type = FTyp;
    879 			ty1 = &typ[findtyp(ntyp-1)];
    880 			s = ty1->size;
    881 			a = ty1->align;
    882 			break;
    883 		}
    884 		if (a > al)
    885 			al = a;
    886 		a = (1 << a) - 1;
    887 		a = ((sz + a) & ~a) - sz;
    888 		if (a) {
    889 			if (n < NField) {
    890 				/* padding */
    891 				fld[n].type = FPad;
    892 				fld[n].len = a;
    893 				n++;
    894 			}
    895 		}
    896 		t = nextnl();
    897 		if (t == Tint) {
    898 			c = tokval.num;
    899 			t = nextnl();
    900 		} else
    901 			c = 1;
    902 		sz += a + c*s;
    903 		if (type == FTyp)
    904 			s = ty1 - typ;
    905 		for (; c>0 && n<NField; c--, n++) {
    906 			fld[n].type = type;
    907 			fld[n].len = s;
    908 		}
    909 		if (t != Tcomma)
    910 			break;
    911 		t = nextnl();
    912 	}
    913 	if (t != Trbrace)
    914 		err(", or } expected");
    915 	fld[n].type = FEnd;
    916 	a = 1 << al;
    917 	if (sz < ty->size)
    918 		sz = ty->size;
    919 	ty->size = (sz + a - 1) & -a;
    920 	ty->align = al;
    921 }
    922 
    923 static void
    924 parsetyp()
    925 {
    926 	Typ *ty;
    927 	int t, al;
    928 	uint n;
    929 
    930 	/* be careful if extending the syntax
    931 	 * to handle nested types, any pointer
    932 	 * held to typ[] might be invalidated!
    933 	 */
    934 	vgrow(&typ, ntyp+1);
    935 	ty = &typ[ntyp++];
    936 	ty->dark = 0;
    937 	ty->align = -1;
    938 	ty->size = 0;
    939 	if (nextnl() != Ttyp ||  nextnl() != Teq)
    940 		err("type name and then = expected");
    941 	strcpy(ty->name, tokval.str);
    942 	t = nextnl();
    943 	if (t == Talign) {
    944 		if (nextnl() != Tint)
    945 			err("alignment expected");
    946 		for (al=0; tokval.num /= 2; al++)
    947 			;
    948 		ty->align = al;
    949 		t = nextnl();
    950 	}
    951 	if (t != Tlbrace)
    952 		err("type body must start with {");
    953 	t = nextnl();
    954 	if (t == Tint) {
    955 		ty->dark = 1;
    956 		ty->size = tokval.num;
    957 		if (ty->align == -1)
    958 			err("dark types need alignment");
    959 		if (nextnl() != Trbrace)
    960 			err("} expected");
    961 		return;
    962 	}
    963 	n = 0;
    964 	ty->fields = vnew(1, sizeof ty->fields[0], Pheap);
    965 	if (t == Tlbrace)
    966 		do {
    967 			if (t != Tlbrace)
    968 				err("invalid union member");
    969 			vgrow(&ty->fields, n+1);
    970 			parsefields(ty->fields[n++], ty, nextnl());
    971 			t = nextnl();
    972 		} while (t != Trbrace);
    973 	else
    974 		parsefields(ty->fields[n++], ty, t);
    975 	ty->nunion = n;
    976 }
    977 
    978 static void
    979 parsedatref(Dat *d)
    980 {
    981 	int t;
    982 
    983 	d->isref = 1;
    984 	d->u.ref.nam = tokval.str;
    985 	d->u.ref.off = 0;
    986 	t = peek();
    987 	if (t == Tplus) {
    988 		next();
    989 		if (next() != Tint)
    990 			err("invalid token after offset in ref");
    991 		d->u.ref.off = tokval.num;
    992 	}
    993 }
    994 
    995 static void
    996 parsedatstr(Dat *d)
    997 {
    998 	d->isstr = 1;
    999 	d->u.str = tokval.str;
   1000 }
   1001 
   1002 static void
   1003 parsedat(void cb(Dat *), int export)
   1004 {
   1005 	char name[NString] = {0};
   1006 	int t;
   1007 	Dat d;
   1008 
   1009 	if (nextnl() != Tglo || nextnl() != Teq)
   1010 		err("data name, then = expected");
   1011 	strncpy(name, tokval.str, NString-1);
   1012 	t = nextnl();
   1013 	d.u.str = 0;
   1014 	if (t == Tsection) {
   1015 		if (nextnl() != Tstr)
   1016 			err("section \"name\" expected");
   1017 		d.u.str = tokval.str;
   1018 		t = nextnl();
   1019 	}
   1020 	d.type = DStart;
   1021 	cb(&d);
   1022 	if (t == Talign) {
   1023 		if (nextnl() != Tint)
   1024 			err("alignment expected");
   1025 		d.type = DAlign;
   1026 		d.u.num = tokval.num;
   1027 		d.isstr = 0;
   1028 		d.isref = 0;
   1029 		cb(&d);
   1030 		t = nextnl();
   1031 	}
   1032 	d.type = DName;
   1033 	d.u.str = name;
   1034 	d.export = export;
   1035 	cb(&d);
   1036 
   1037 	if (t != Tlbrace)
   1038 		err("expected data contents in { .. }");
   1039 	for (;;) {
   1040 		switch (nextnl()) {
   1041 		default: err("invalid size specifier %c in data", tokval.chr);
   1042 		case Trbrace: goto Done;
   1043 		case Tl: d.type = DL; break;
   1044 		case Tw: d.type = DW; break;
   1045 		case Th: d.type = DH; break;
   1046 		case Tb: d.type = DB; break;
   1047 		case Ts: d.type = DW; break;
   1048 		case Td: d.type = DL; break;
   1049 		case Tz: d.type = DZ; break;
   1050 		}
   1051 		t = nextnl();
   1052 		do {
   1053 			d.isstr = 0;
   1054 			d.isref = 0;
   1055 			memset(&d.u, 0, sizeof d.u);
   1056 			if (t == Tflts)
   1057 				d.u.flts = tokval.flts;
   1058 			else if (t == Tfltd)
   1059 				d.u.fltd = tokval.fltd;
   1060 			else if (t == Tint)
   1061 				d.u.num = tokval.num;
   1062 			else if (t == Tglo)
   1063 				parsedatref(&d);
   1064 			else if (t == Tstr)
   1065 				parsedatstr(&d);
   1066 			else
   1067 				err("constant literal expected");
   1068 			cb(&d);
   1069 			t = nextnl();
   1070 		} while (t == Tint || t == Tflts || t == Tfltd);
   1071 		if (t == Trbrace)
   1072 			break;
   1073 		if (t != Tcomma)
   1074 			err(", or } expected");
   1075 	}
   1076 Done:
   1077 	d.type = DEnd;
   1078 	cb(&d);
   1079 }
   1080 
   1081 void
   1082 parse(FILE *f, char *path, void data(Dat *), void func(Fn *))
   1083 {
   1084 	int t, export;
   1085 
   1086 	lexinit();
   1087 	inf = f;
   1088 	inpath = path;
   1089 	lnum = 1;
   1090 	thead = Txxx;
   1091 	ntyp = 0;
   1092 	typ = vnew(0, sizeof typ[0], Pheap);
   1093 	for (;;) {
   1094 		export = 0;
   1095 		switch (nextnl()) {
   1096 		default:
   1097 			err("top-level definition expected");
   1098 		case Texport:
   1099 			export = 1;
   1100 			t = nextnl();
   1101 			if (t == Tfunc) {
   1102 		case Tfunc:
   1103 				func(parsefn(export));
   1104 				break;
   1105 			}
   1106 			else if (t == Tdata) {
   1107 		case Tdata:
   1108 				parsedat(data, export);
   1109 				break;
   1110 			}
   1111 			else
   1112 				err("export can only qualify data and function");
   1113 		case Ttype:
   1114 			parsetyp();
   1115 			break;
   1116 		case Teof:
   1117 			vfree(typ);
   1118 			return;
   1119 		}
   1120 	}
   1121 }
   1122 
   1123 static void
   1124 printcon(Con *c, FILE *f)
   1125 {
   1126 	switch (c->type) {
   1127 	case CUndef:
   1128 		break;
   1129 	case CAddr:
   1130 		fprintf(f, "$%s", str(c->label));
   1131 		if (c->bits.i)
   1132 			fprintf(f, "%+"PRIi64, c->bits.i);
   1133 		break;
   1134 	case CBits:
   1135 		if (c->flt == 1)
   1136 			fprintf(f, "s_%f", c->bits.s);
   1137 		else if (c->flt == 2)
   1138 			fprintf(f, "d_%lf", c->bits.d);
   1139 		else
   1140 			fprintf(f, "%"PRIi64, c->bits.i);
   1141 		break;
   1142 	}
   1143 }
   1144 
   1145 void
   1146 printref(Ref r, Fn *fn, FILE *f)
   1147 {
   1148 	int i;
   1149 	Mem *m;
   1150 
   1151 	switch (rtype(r)) {
   1152 	case RTmp:
   1153 		if (r.val < Tmp0)
   1154 			fprintf(f, "R%d", r.val);
   1155 		else
   1156 			fprintf(f, "%%%s", fn->tmp[r.val].name);
   1157 		break;
   1158 	case RCon:
   1159 		printcon(&fn->con[r.val], f);
   1160 		break;
   1161 	case RSlot:
   1162 		fprintf(f, "S%d", (r.val&(1<<28)) ? r.val-(1<<29) : r.val);
   1163 		break;
   1164 	case RCall:
   1165 		fprintf(f, "%04x", r.val);
   1166 		break;
   1167 	case RType:
   1168 		fprintf(f, ":%s", typ[r.val].name);
   1169 		break;
   1170 	case RMem:
   1171 		i = 0;
   1172 		m = &fn->mem[r.val];
   1173 		fputc('[', f);
   1174 		if (m->offset.type != CUndef) {
   1175 			printcon(&m->offset, f);
   1176 			i = 1;
   1177 		}
   1178 		if (!req(m->base, R)) {
   1179 			if (i)
   1180 				fprintf(f, " + ");
   1181 			printref(m->base, fn, f);
   1182 			i = 1;
   1183 		}
   1184 		if (!req(m->index, R)) {
   1185 			if (i)
   1186 				fprintf(f, " + ");
   1187 			fprintf(f, "%d * ", m->scale);
   1188 			printref(m->index, fn, f);
   1189 		}
   1190 		fputc(']', f);
   1191 		break;
   1192 	}
   1193 }
   1194 
   1195 void
   1196 printfn(Fn *fn, FILE *f)
   1197 {
   1198 	static char ktoc[] = "wlsd";
   1199 	static char *jtoa[NJmp] = {
   1200 	#define X(j) [J##j] = #j,
   1201 		JMPS(X)
   1202 	#undef X
   1203 	};
   1204 	Blk *b;
   1205 	Phi *p;
   1206 	Ins *i;
   1207 	uint n;
   1208 
   1209 	if (fn->export)
   1210 		fprintf(f, "export ");
   1211 	fprintf(f, "function $%s() {\n", fn->name);
   1212 	for (b=fn->start; b; b=b->link) {
   1213 		fprintf(f, "@%s\n", b->name);
   1214 		for (p=b->phi; p; p=p->link) {
   1215 			fprintf(f, "\t");
   1216 			printref(p->to, fn, f);
   1217 			fprintf(f, " =%c phi ", ktoc[p->cls]);
   1218 			assert(p->narg);
   1219 			for (n=0;; n++) {
   1220 				fprintf(f, "@%s ", p->blk[n]->name);
   1221 				printref(p->arg[n], fn, f);
   1222 				if (n == p->narg-1) {
   1223 					fprintf(f, "\n");
   1224 					break;
   1225 				} else
   1226 					fprintf(f, ", ");
   1227 			}
   1228 		}
   1229 		for (i=b->ins; i<&b->ins[b->nins]; i++) {
   1230 			fprintf(f, "\t");
   1231 			if (!req(i->to, R)) {
   1232 				printref(i->to, fn, f);
   1233 				fprintf(f, " =%c ", ktoc[i->cls]);
   1234 			}
   1235 			assert(optab[i->op].name);
   1236 			fprintf(f, "%s", optab[i->op].name);
   1237 			if (req(i->to, R))
   1238 				switch (i->op) {
   1239 				case Oarg:
   1240 				case Oswap:
   1241 				case Oxcmp:
   1242 				case Oacmp:
   1243 				case Oacmn:
   1244 				case Oafcmp:
   1245 				case Oxtest:
   1246 				case Oxdiv:
   1247 				case Oxidiv:
   1248 					fputc(ktoc[i->cls], f);
   1249 				}
   1250 			if (!req(i->arg[0], R)) {
   1251 				fprintf(f, " ");
   1252 				printref(i->arg[0], fn, f);
   1253 			}
   1254 			if (!req(i->arg[1], R)) {
   1255 				fprintf(f, ", ");
   1256 				printref(i->arg[1], fn, f);
   1257 			}
   1258 			fprintf(f, "\n");
   1259 		}
   1260 		switch (b->jmp.type) {
   1261 		case Jret0:
   1262 		case Jretw:
   1263 		case Jretl:
   1264 		case Jrets:
   1265 		case Jretd:
   1266 		case Jretc:
   1267 			fprintf(f, "\t%s", jtoa[b->jmp.type]);
   1268 			if (b->jmp.type != Jret0 || !req(b->jmp.arg, R)) {
   1269 				fprintf(f, " ");
   1270 				printref(b->jmp.arg, fn, f);
   1271 			}
   1272 			if (b->jmp.type == Jretc)
   1273 				fprintf(f, ", :%s", typ[fn->retty].name);
   1274 			fprintf(f, "\n");
   1275 			break;
   1276 		case Jjmp:
   1277 			if (b->s1 != b->link)
   1278 				fprintf(f, "\tjmp @%s\n", b->s1->name);
   1279 			break;
   1280 		default:
   1281 			fprintf(f, "\t%s ", jtoa[b->jmp.type]);
   1282 			if (b->jmp.type == Jjnz) {
   1283 				printref(b->jmp.arg, fn, f);
   1284 				fprintf(f, ", ");
   1285 			}
   1286 			fprintf(f, "@%s, @%s\n", b->s1->name, b->s2->name);
   1287 			break;
   1288 		}
   1289 	}
   1290 	fprintf(f, "}\n");
   1291 }