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