parse.c

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