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