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