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