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