parse.c

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