parse.c

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