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