ncc.c

   1 /*
   2  * neatcc - A small and simple x86_64 C compiler
   3  *
   4  * Copyright (C) 2010 Ali Gholami Rudi
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License, as published by the
   8  * Free Software Foundation.
   9  */
  10 #include <fcntl.h>
  11 #include <unistd.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <sys/stat.h>
  15 #include <sys/types.h>
  16 #include "gen.h"
  17 #include "tok.h"
  18
  19 #define MAXLOCALS       (1 << 10)
  20 #define MAXGLOBALS      (1 << 10)
  21 #define MAXARGS         (1 << 5)
  22 #define print(s)        write(2, (s), strlen(s));
  23
  24 #define TYPE_BT(t)              ((t)->ptr ? 8 : (t)->bt)
  25 #define TYPE_SZ(t)              ((t)->ptr ? 8 : (t)->bt & BT_SZMASK)
  26
  27 #define T_ARRAY         0x01
  28 #define T_STRUCT        0x02
  29 #define T_FUNC          0x04
  30
  31 #define F_INIT          0x01
  32 #define F_STATIC        0x02
  33
  34 struct type {
  35         unsigned bt;
  36         unsigned flags;
  37         int ptr;
  38         int id;         /* for structs, functions and arrays */
  39 };
  40
  41 /* type stack */
  42 static struct type ts[MAXTMP];
  43 static int nts;
  44
  45 static void ts_push_bt(unsigned bt)
  46 {
  47         ts[nts].ptr = 0;
  48         ts[nts].flags = 0;
  49         ts[nts++].bt = bt;
  50 }
  51
  52 static void ts_push(struct type *t)
  53 {
  54         memcpy(&ts[nts++], t, sizeof(*t));
  55         if (t->flags & (T_FUNC | T_ARRAY) && !t->ptr)
  56                 o_addr();
  57 }
  58
  59 static void ts_pop(struct type *type)
  60 {
  61         nts--;
  62         if (type)
  63                 *type = ts[nts];
  64 }
  65
  66 struct name {
  67         char name[NAMELEN];
  68         struct type type;
  69         long addr;
  70 };
  71
  72 static struct name locals[MAXLOCALS];
  73 static int nlocals;
  74 static struct name globals[MAXGLOBALS];
  75 static int nglobals;
  76
  77 static void local_add(struct name *name)
  78 {
  79         memcpy(&locals[nlocals++], name, sizeof(*name));
  80 }
  81
  82 static int global_find(char *name)
  83 {
  84         int i;
  85         for (i = 0; i < nglobals; i++)
  86                 if (!strcmp(name, globals[i].name))
  87                         return i;
  88         return -1;
  89 }
  90
  91 static void global_add(struct name *name)
  92 {
  93         int found = global_find(name->name);
  94         int i = found == -1 ? nglobals++ : found;
  95         memcpy(&globals[i], name, sizeof(*name));
  96 }
  97
  98 static void die(char *s)
  99 {
 100         print(s);
 101         exit(1);
 102 }
 103
 104 #define MAXENUMS                (1 << 10)
 105
 106 static struct enumval {
 107         char name[NAMELEN];
 108         int n;
 109 } enums[MAXENUMS];
 110 static int nenums;
 111
 112 static void enum_add(char *name, int val)
 113 {
 114         struct enumval *ev = &enums[nenums++];
 115         strcpy(ev->name, name);
 116         ev->n = val;
 117 }
 118
 119 static int enum_find(int *val, char *name)
 120 {
 121         int i;
 122         for (i = nenums - 1; i >= 0; --i)
 123                 if (!strcmp(name, enums[i].name)) {
 124                         *val = enums[i].n;
 125                         return 0;
 126                 }
 127         return 1;
 128 }
 129
 130 #define MAXTYPEDEFS             (1 << 5)
 131
 132 static struct typdefinfo {
 133         char name[NAMELEN];
 134         struct type type;
 135 } typedefs[MAXTYPEDEFS];
 136 static int ntypedefs;
 137
 138 static void typedef_add(char *name, struct type *type)
 139 {
 140         struct typdefinfo *ti = &typedefs[ntypedefs++];
 141         strcpy(ti->name, name);
 142         memcpy(&ti->type, type, sizeof(*type));
 143 }
 144
 145 static int typedef_find(char *name)
 146 {
 147         int i;
 148         for (i = ntypedefs - 1; i >= 0; --i)
 149                 if (!strcmp(name, typedefs[i].name))
 150                         return i;
 151         return -1;
 152 }
 153
 154 #define MAXARRAYS               (1 << 5)
 155
 156 static struct array {
 157         struct type type;
 158         int n;
 159 } arrays[MAXARRAYS];
 160 static int narrays;
 161
 162 static int array_add(struct type *type, int n)
 163 {
 164         struct array *a = &arrays[narrays++];
 165         memcpy(&a->type, type, sizeof(*type));
 166         a->n = n;
 167         return a - arrays;
 168 }
 169
 170 static void array2ptr(struct type *t)
 171 {
 172         if (!(t->flags & T_ARRAY) || t->ptr)
 173                 return;
 174         memcpy(t, &arrays[t->id].type, sizeof(*t));
 175         t->ptr++;
 176 }
 177
 178 #define MAXTYPES                (1 << 7)
 179 #define MAXFIELDS               (1 << 5)
 180
 181 static struct structinfo {
 182         char name[NAMELEN];
 183         struct name fields[MAXFIELDS];
 184         int nfields;
 185         int isunion;
 186         int size;
 187 } structs[MAXTYPES];
 188 static int nstructs;
 189
 190 static int struct_find(char *name, int isunion)
 191 {
 192         int i;
 193         for (i = nstructs - 1; i >= 0; --i)
 194                 if (!strcmp(name, structs[i].name) &&
 195                                 structs[i].isunion == isunion)
 196                         return i;
 197         i = nstructs++;
 198         memset(&structs[i], 0, sizeof(structs[i]));
 199         strcpy(structs[i].name, name);
 200         structs[i].isunion = isunion;
 201         return i;
 202 }
 203
 204 static struct name *struct_field(int id, char *name)
 205 {
 206         struct structinfo *si = &structs[id];
 207         int i;
 208         for (i = 0; i < si->nfields; i++)
 209                 if (!strcmp(name, si->fields[i].name))
 210                         return &si->fields[i];
 211         die("field not found\n");
 212 }
 213
 214 #define MAXBREAK                (1 << 7)
 215 static long breaks[MAXBREAK];
 216 static int nbreaks;
 217 static long continues[MAXBREAK];
 218 static int ncontinues;
 219
 220 static void break_fill(long addr, int till)
 221 {
 222         int i;
 223         for (i = till; i < nbreaks; i++)
 224                 o_filljmp2(breaks[i], addr);
 225         nbreaks = till;
 226 }
 227
 228 static void continue_fill(long addr, int till)
 229 {
 230         int i;
 231         for (i = till; i < ncontinues; i++)
 232                 o_filljmp2(continues[i], addr);
 233         ncontinues = till;
 234 }
 235
 236 static int type_totsz(struct type *t)
 237 {
 238         if (t->ptr)
 239                 return 8;
 240         if (t->flags & T_ARRAY)
 241                 return arrays[t->id].n * type_totsz(&arrays[t->id].type);
 242         return t->flags & T_STRUCT ? structs[t->id].size : BT_SZ(t->bt);
 243 }
 244
 245 static unsigned type_szde(struct type *t)
 246 {
 247         if (t->flags & T_ARRAY)
 248                 return t->ptr > 0 ? 8 : TYPE_SZ(&arrays[t->id].type);
 249         else
 250                 return t->ptr > 1 ? 8 : BT_SZ(t->bt);
 251 }
 252
 253 static int tok_jmp(int tok)
 254 {
 255         if (tok_see() != tok)
 256                 return 1;
 257         tok_get();
 258         return 0;
 259 }
 260
 261 static void tok_expect(int tok)
 262 {
 263         if (tok_get() != tok)
 264                 die("syntax error\n");
 265 }
 266
 267 static unsigned bt_op(unsigned bt1, unsigned bt2)
 268 {
 269         unsigned s1 = BT_SZ(bt1);
 270         unsigned s2 = BT_SZ(bt2);
 271         return (bt1 | bt2) & BT_SIGNED | (s1 > s2 ? s1 : s2);
 272 }
 273
 274 static void ts_binop(void (*o_sth)(void))
 275 {
 276         struct type t1, t2;
 277         ts_pop(&t1);
 278         ts_pop(&t2);
 279         o_sth();
 280         ts_push_bt(bt_op(TYPE_BT(&t1), TYPE_BT(&t2)));
 281 }
 282
 283 static int shifts(int n)
 284 {
 285         int i = -1;
 286         while (i++ < 16)
 287                 if (n == 1 << i)
 288                         break;
 289         return i;
 290 }
 291
 292 static void ts_binop_add(void (*o_sth)(void))
 293 {
 294         struct type t1, t2;
 295         ts_pop(&t1);
 296         ts_pop(&t2);
 297         array2ptr(&t1);
 298         array2ptr(&t2);
 299         if (!t1.ptr && !t2.ptr) {
 300                 o_sth();
 301                 ts_push_bt(bt_op(TYPE_BT(&t1), TYPE_BT(&t2)));
 302                 return;
 303         }
 304         if (t1.ptr && !t2.ptr) {
 305                 struct type t = t2;
 306                 t2 = t1;
 307                 t1 = t;
 308                 o_tmpswap();
 309         }
 310         if (!t1.ptr && t2.ptr)
 311                 if (type_szde(&t2) > 1) {
 312                         o_num(shifts(type_szde(&t2)), 1);
 313                         o_shl();
 314                 }
 315         o_sth();
 316         if (t1.ptr && t2.ptr) {
 317                 o_num(shifts(type_szde(&t1)), 1);
 318                 o_shr();
 319                 ts_push_bt(4 | BT_SIGNED);
 320         } else {
 321                 ts_push(&t2);
 322         }
 323 }
 324
 325 static void structdef(void *data, struct name *name, unsigned flags)
 326 {
 327         struct structinfo *si = data;
 328         if (si->isunion) {
 329                 name->addr = 0;
 330                 if (si->size < type_totsz(&name->type))
 331                         si->size = type_totsz(&name->type);
 332         } else {
 333                 name->addr = si->size;
 334                 si->size += type_totsz(&name->type);
 335         }
 336         memcpy(&si->fields[si->nfields++], name, sizeof(*name));
 337 }
 338
 339 static int readdefs(void (*def)(void *, struct name *, unsigned f), void *data);
 340
 341 static int struct_create(char *name, int isunion)
 342 {
 343         int id = struct_find(name, isunion);
 344         struct structinfo *si = &structs[id];
 345         tok_expect('{');
 346         while (tok_jmp('}')) {
 347                 readdefs(structdef, si);
 348                 tok_expect(';');
 349         }
 350         return id;
 351 }
 352
 353 static void readexpr(void);
 354
 355 static void enum_create(void)
 356 {
 357         long n = 0;
 358         tok_expect('{');
 359         while (tok_jmp('}')) {
 360                 char name[NAMELEN];
 361                 tok_expect(TOK_NAME);
 362                 strcpy(name, tok_id());
 363                 if (tok_see() == '=') {
 364                         tok_get();
 365                         readexpr();
 366                         ts_pop(NULL);
 367                         if (o_popnum(&n))
 368                                 die("const expr expected!\n");
 369                 }
 370                 enum_add(name, n++);
 371                 tok_jmp(',');
 372         }
 373 }
 374
 375 static int basetype(struct type *type, unsigned *flags)
 376 {
 377         int sign = 1;
 378         int size = 4;
 379         int done = 0;
 380         int i = 0;
 381         int isunion;
 382         char name[NAMELEN];
 383         *flags = 0;
 384         type->flags = 0;
 385         type->ptr = 0;
 386         while (!done) {
 387                 switch (tok_see()) {
 388                 case TOK_STATIC:
 389                         *flags |= F_STATIC;
 390                         break;
 391                 case TOK_VOID:
 392                         sign = 0;
 393                         size = 0;
 394                         done = 1;
 395                         break;
 396                 case TOK_INT:
 397                         done = 1;
 398                         break;
 399                 case TOK_CHAR:
 400                         size = 1;
 401                         done = 1;
 402                         break;
 403                 case TOK_SHORT:
 404                         size = 2;
 405                         break;
 406                 case TOK_LONG:
 407                         size = 8;
 408                         break;
 409                 case TOK_UNSIGNED:
 410                         sign = 0;
 411                         break;
 412                 case TOK_UNION:
 413                 case TOK_STRUCT:
 414                         isunion = tok_get() == TOK_UNION;
 415                         tok_expect(TOK_NAME);
 416                         strcpy(name, tok_id());
 417                         if (tok_see() == '{')
 418                                 type->id = struct_create(name, isunion);
 419                         else
 420                                 type->id = struct_find(name, isunion);
 421                         type->flags |= T_STRUCT;
 422                         type->bt = 8;
 423                         return 0;
 424                 case TOK_ENUM:
 425                         tok_get();
 426                         tok_expect(TOK_NAME);
 427                         if (tok_see() == '{')
 428                                 enum_create();
 429                         type->bt = 4 | BT_SIGNED;
 430                         return 0;
 431                 default:
 432                         if (tok_see() == TOK_NAME) {
 433                                 int id = typedef_find(tok_id());
 434                                 if (id != -1) {
 435                                         tok_get();
 436                                         memcpy(type, &typedefs[id].type,
 437                                                 sizeof(*type));
 438                                         return 0;
 439                                 }
 440                         }
 441                         if (!i)
 442                                 return 1;
 443                         done = 1;
 444                         continue;
 445                 }
 446                 i++;
 447                 tok_get();
 448         }
 449         type->bt = size | (sign ? BT_SIGNED : 0);
 450         return 0;
 451 }
 452
 453 static void readptrs(struct type *type)
 454 {
 455         while (!tok_jmp('*'))
 456                 type->ptr++;
 457 }
 458
 459 static int readtype(struct type *type)
 460 {
 461         unsigned flags;
 462         if (basetype(type, &flags))
 463                 return 1;
 464         readptrs(type);
 465         return 0;
 466 }
 467
 468 static void readpre(void);
 469
 470 static void readprimary(void)
 471 {
 472         struct name name;
 473         int i;
 474         if (!tok_jmp(TOK_NUM)) {
 475                 ts_push_bt(4 | BT_SIGNED);
 476                 o_num(tok_num(), 4 | BT_SIGNED);
 477                 return;
 478         }
 479         if (!tok_jmp(TOK_STR)) {
 480                 struct type t;
 481                 char buf[BUFSIZE];
 482                 int len;
 483                 t.bt = 1 | BT_SIGNED;
 484                 t.ptr = 1;
 485                 t.flags = 0;
 486                 ts_push(&t);
 487                 len = tok_str(buf);
 488                 o_symaddr(o_mkdat(NULL, buf, len, 0), TYPE_BT(&t));
 489                 o_addr();
 490                 return;
 491         }
 492         if (!tok_jmp(TOK_NAME)) {
 493                 int n;
 494                 for (i = nlocals - 1; i >= 0; --i) {
 495                         struct type *t = &locals[i].type;
 496                         if (!strcmp(locals[i].name, tok_id())) {
 497                                 o_local(locals[i].addr, TYPE_BT(t));
 498                                 ts_push(t);
 499                                 return;
 500                         }
 501                 }
 502                 if ((n = global_find(tok_id())) != -1) {
 503                         struct type *t = &globals[n].type;
 504                         o_symaddr(globals[n].addr, TYPE_BT(t));
 505                         ts_push(t);
 506                         return;
 507                 }
 508                 if (!enum_find(&n, tok_id())) {
 509                         ts_push_bt(4 | BT_SIGNED);
 510                         o_num(n, 4 | BT_SIGNED);
 511                         return;
 512                 }
 513                 strcpy(name.name, tok_id());
 514                 name.addr = o_mkundef(name.name);
 515                 global_add(&name);
 516                 ts_push_bt(8);
 517                 o_symaddr(name.addr, 8);
 518                 return;
 519         }
 520         if (!tok_jmp('(')) {
 521                 struct type t;
 522                 if (!readtype(&t)) {
 523                         struct type o;
 524                         tok_expect(')');
 525                         readpre();
 526                         ts_pop(&o);
 527                         ts_push(&t);
 528                         if (!t.ptr || !o.ptr)
 529                                 o_cast(TYPE_BT(&t));
 530                 } else {
 531                         readexpr();
 532                         tok_expect(')');
 533                 }
 534                 return;
 535         }
 536 }
 537
 538 void arrayderef(struct type *t)
 539 {
 540         int sz = type_totsz(t);
 541         if (sz > 1) {
 542                 o_num(sz, 4);
 543                 o_mul();
 544         }
 545         o_add();
 546         o_deref(TYPE_BT(t));
 547 }
 548
 549 static void inc_post(void (*op)(void))
 550 {
 551         unsigned bt = TYPE_BT(&ts[nts - 1]);
 552         o_tmpcopy();
 553         o_load();
 554         o_tmpswap();
 555         o_tmpcopy();
 556         o_num(1, 4);
 557         ts_push_bt(bt);
 558         ts_push_bt(bt);
 559         ts_binop_add(op);
 560         ts_pop(NULL);
 561         o_assign(bt);
 562         o_tmpdrop(1);
 563 }
 564
 565 static void readfield(void)
 566 {
 567         struct name *field;
 568         struct type t;
 569         tok_expect(TOK_NAME);
 570         ts_pop(&t);
 571         field = struct_field(t.id, tok_id());
 572         if (field->addr) {
 573                 o_num(field->addr, 4);
 574                 o_add();
 575         }
 576         o_deref(TYPE_BT(&field->type));
 577         ts_push(&field->type);
 578 }
 579
 580 #define MAXFUNCS                (1 << 10)
 581
 582 static struct funcinfo {
 583         struct type args[MAXFIELDS];
 584         struct type ret;
 585         int nargs;
 586 } funcs[MAXFUNCS];
 587 static int nfuncs;
 588 static unsigned ret_bt;
 589
 590 static int func_create(struct type *ret, struct name *args, int nargs)
 591 {
 592         struct funcinfo *fi = &funcs[nfuncs++];
 593         int i;
 594         memcpy(&fi->ret, ret, sizeof(*ret));
 595         for (i = 0; i < nargs; i++)
 596                 memcpy(&fi->args[i], &args[i].type, sizeof(*ret));
 597         fi->nargs = nargs;
 598         return fi - funcs;
 599 }
 600
 601 static void readcall(void)
 602 {
 603         struct type t;
 604         unsigned bt[MAXARGS];
 605         struct funcinfo *fi;
 606         int argc = 0;
 607         int i;
 608         if (tok_see() != ')') {
 609                 readexpr();
 610                 ts_pop(&t);
 611                 bt[argc++] = TYPE_BT(&t);
 612         }
 613         while (!tok_jmp(',')) {
 614                 readexpr();
 615                 ts_pop(&t);
 616                 bt[argc++] = TYPE_BT(&t);
 617         }
 618         tok_expect(')');
 619         ts_pop(&t);
 620         if (t.flags & T_FUNC && t.ptr > 0)
 621                 o_deref(8);
 622         fi = t.flags & T_FUNC ? &funcs[t.id] : NULL;
 623         if (fi)
 624                 for (i = 0; i < fi->nargs; i++)
 625                         bt[i] = TYPE_BT(&fi->args[i]);
 626         o_call(argc, bt, fi ? TYPE_BT(&fi->ret) : 4 | BT_SIGNED);
 627         if (fi)
 628                 ts_push(&fi->ret);
 629         else
 630                 ts_push_bt(4 | BT_SIGNED);
 631 }
 632
 633 static void readpost(void)
 634 {
 635         readprimary();
 636         while (1) {
 637                 if (!tok_jmp('[')) {
 638                         struct type t;
 639                         ts_pop(&t);
 640                         readexpr();
 641                         ts_pop(NULL);
 642                         tok_expect(']');
 643                         array2ptr(&t);
 644                         t.ptr--;
 645                         arrayderef(&t);
 646                         ts_push(&t);
 647                         continue;
 648                 }
 649                 if (!tok_jmp('(')) {
 650                         readcall();
 651                         continue;
 652                 }
 653                 if (!tok_jmp(TOK2("++"))) {
 654                         inc_post(o_add);
 655                         continue;
 656                 }
 657                 if (!tok_jmp(TOK2("--"))) {
 658                         inc_post(o_sub);
 659                         continue;
 660                 }
 661                 if (!tok_jmp('.')) {
 662                         o_addr();
 663                         readfield();
 664                         continue;
 665                 }
 666                 if (!tok_jmp(TOK2("->"))) {
 667                         readfield();
 668                         continue;
 669                 }
 670                 break;
 671         }
 672 }
 673
 674 static void inc_pre(void (*op)(void))
 675 {
 676         unsigned bt = TYPE_BT(&ts[nts - 1]);
 677         readpre();
 678         o_tmpcopy();
 679         o_num(1, 4);
 680         ts_push_bt(bt);
 681         ts_push_bt(bt);
 682         ts_binop_add(op);
 683         ts_pop(NULL);
 684         o_assign(bt);
 685 }
 686
 687 static void readpre(void)
 688 {
 689         if (!tok_jmp('&')) {
 690                 struct type type;
 691                 readpre();
 692                 ts_pop(&type);
 693                 if (!(type.flags & T_FUNC) && !type.ptr)
 694                         type.ptr++;
 695                 ts_push(&type);
 696                 o_addr();
 697                 return;
 698         }
 699         if (!tok_jmp('*')) {
 700                 struct type t;
 701                 readpre();
 702                 ts_pop(&t);
 703                 array2ptr(&t);
 704                 if (!(t.flags & T_FUNC) || t.ptr > 0) {
 705                         t.ptr--;
 706                         o_deref(TYPE_BT(&t));
 707                 }
 708                 ts_push(&t);
 709                 return;
 710         }
 711         if (!tok_jmp('!')) {
 712                 struct type type;
 713                 readpre();
 714                 ts_pop(&type);
 715                 o_lnot();
 716                 ts_push_bt(4 | BT_SIGNED);
 717                 return;
 718         }
 719         if (!tok_jmp('-')) {
 720                 readpre();
 721                 o_neg();
 722                 return;
 723         }
 724         if (!tok_jmp('~')) {
 725                 readpre();
 726                 o_not();
 727                 return;
 728         }
 729         if (!tok_jmp(TOK2("++"))) {
 730                 inc_pre(o_add);
 731                 return;
 732         }
 733         if (!tok_jmp(TOK2("--"))) {
 734                 inc_pre(o_sub);
 735                 return;
 736         }
 737         if (!tok_jmp(TOK_SIZEOF)) {
 738                 struct type t;
 739                 int op = !tok_jmp('(');
 740                 if (readtype(&t)) {
 741                         int nogen = !o_nogen();
 742                         readexpr();
 743                         if (nogen)
 744                                 o_dogen();
 745                         ts_pop(&t);
 746                         o_tmpdrop(1);
 747                 }
 748                 ts_push_bt(4);
 749                 o_num(type_totsz(&t), 4);
 750                 if (op)
 751                         tok_expect(')');
 752                 return;
 753         }
 754         readpost();
 755 }
 756
 757 static void readmul(void)
 758 {
 759         readpre();
 760         while (1) {
 761                 if (!tok_jmp('*')) {
 762                         readpre();
 763                         ts_binop(o_mul);
 764                         continue;
 765                 }
 766                 if (!tok_jmp('/')) {
 767                         readpre();
 768                         ts_binop(o_div);
 769                         continue;
 770                 }
 771                 if (!tok_jmp('%')) {
 772                         readpre();
 773                         ts_binop(o_mod);
 774                         continue;
 775                 }
 776                 break;
 777         }
 778 }
 779
 780 static void readadd(void)
 781 {
 782         readmul();
 783         while (1) {
 784                 if (!tok_jmp('+')) {
 785                         readmul();
 786                         ts_binop_add(o_add);
 787                         continue;
 788                 }
 789                 if (!tok_jmp('-')) {
 790                         readmul();
 791                         ts_binop_add(o_sub);
 792                         continue;
 793                 }
 794                 break;
 795         }
 796 }
 797
 798 static void shift(void (*op)(void))
 799 {
 800         struct type t;
 801         readadd();
 802         ts_pop(NULL);
 803         ts_pop(&t);
 804         op();
 805         ts_push_bt(TYPE_BT(&t));
 806 }
 807
 808 static void readshift(void)
 809 {
 810         readadd();
 811         while (1) {
 812                 if (!tok_jmp(TOK2("<<"))) {
 813                         shift(o_shl);
 814                         continue;
 815                 }
 816                 if (!tok_jmp(TOK2(">>"))) {
 817                         shift(o_shr);
 818                         continue;
 819                 }
 820                 break;
 821         }
 822 }
 823
 824 static void cmp(void (*op)(void))
 825 {
 826         readshift();
 827         ts_pop(NULL);
 828         ts_pop(NULL);
 829         op();
 830         ts_push_bt(4 | BT_SIGNED);
 831 }
 832
 833 static void readcmp(void)
 834 {
 835         readshift();
 836         while (1) {
 837                 if (!tok_jmp('<')) {
 838                         cmp(o_lt);
 839                         continue;
 840                 }
 841                 if (!tok_jmp('>')) {
 842                         cmp(o_gt);
 843                         continue;
 844                 }
 845                 if (!tok_jmp(TOK2("<="))) {
 846                         cmp(o_le);
 847                         continue;
 848                 }
 849                 if (!tok_jmp(TOK2(">="))) {
 850                         cmp(o_ge);
 851                         continue;
 852                 }
 853                 break;
 854         }
 855 }
 856
 857 static void eq(void (*op)(void))
 858 {
 859         readcmp();
 860         ts_pop(NULL);
 861         ts_pop(NULL);
 862         op();
 863         ts_push_bt(4 | BT_SIGNED);
 864 }
 865
 866 static void readeq(void)
 867 {
 868         readcmp();
 869         while (1) {
 870                 if (!tok_jmp(TOK2("=="))) {
 871                         eq(o_eq);
 872                         continue;
 873                 }
 874                 if (!tok_jmp(TOK2("!="))) {
 875                         eq(o_neq);
 876                         continue;
 877                 }
 878                 break;
 879         }
 880 }
 881
 882 static void readbitand(void)
 883 {
 884         readeq();
 885         while (!tok_jmp('&')) {
 886                 readeq();
 887                 ts_binop(o_and);
 888         }
 889 }
 890
 891 static void readxor(void)
 892 {
 893         readbitand();
 894         while (!tok_jmp('^')) {
 895                 readbitand();
 896                 ts_binop(o_xor);
 897         }
 898 }
 899
 900 static void readbitor(void)
 901 {
 902         readxor();
 903         while (!tok_jmp('|')) {
 904                 readxor();
 905                 ts_binop(o_or);
 906         }
 907 }
 908
 909 #define MAXCOND                 (1 << 5)
 910
 911 static void readand(void)
 912 {
 913         long conds[MAXCOND];
 914         int nconds = 0;
 915         long passed;
 916         int i;
 917         readbitor();
 918         if (tok_see() != TOK2("&&"))
 919                 return;
 920         conds[nconds++] = o_jz(0);
 921         ts_pop(NULL);
 922         while (!tok_jmp(TOK2("&&"))) {
 923                 readbitor();
 924                 conds[nconds++] = o_jz(0);
 925                 ts_pop(NULL);
 926         }
 927         o_num(1, 4 | BT_SIGNED);
 928         o_tmpfork();
 929         passed = o_jmp(0);
 930         for (i = 0; i < nconds; i++)
 931                 o_filljmp(conds[i]);
 932         o_num(0, 4 | BT_SIGNED);
 933         o_tmpjoin();
 934         o_filljmp(passed);
 935         ts_push_bt(4 | BT_SIGNED);
 936 }
 937
 938 static void reador(void)
 939 {
 940         long conds[MAXCOND];
 941         int nconds = 0;
 942         long failed;
 943         int i;
 944         readand();
 945         if (tok_see() != TOK2("||"))
 946                 return;
 947         conds[nconds++] = o_jnz(0);
 948         ts_pop(NULL);
 949         while (!tok_jmp(TOK2("||"))) {
 950                 readand();
 951                 conds[nconds++] = o_jnz(0);
 952                 ts_pop(NULL);
 953         }
 954         o_num(0, 4 | BT_SIGNED);
 955         o_tmpfork();
 956         failed = o_jmp(0);
 957         for (i = 0; i < nconds; i++)
 958                 o_filljmp(conds[i]);
 959         o_num(1, 4 | BT_SIGNED);
 960         o_tmpjoin();
 961         o_filljmp(failed);
 962         ts_push_bt(4 | BT_SIGNED);
 963 }
 964
 965 static void readcexpr(void)
 966 {
 967         long l1, l2;
 968         long c;
 969         int cexpr, nogen;
 970         reador();
 971         if (tok_jmp('?'))
 972                 return;
 973         cexpr = !o_popnum(&c);
 974         ts_pop(NULL);
 975         if (cexpr) {
 976                 if (!c)
 977                         nogen = !o_nogen();
 978         } else {
 979                 l1 = o_jz(0);
 980         }
 981         reador();
 982         if (!cexpr) {
 983                 o_tmpfork();
 984                 l2 = o_jmp(0);
 985         }
 986         ts_pop(NULL);
 987         tok_expect(':');
 988         if (cexpr) {
 989                 if (c) {
 990                         nogen = !o_nogen();
 991                 } else {
 992                         if (nogen)
 993                                 o_dogen();
 994                         o_tmpdrop(1);
 995                 }
 996         } else {
 997                 o_filljmp(l1);
 998         }
 999         reador();
1000         if (cexpr) {
1001                 if (c) {
1002                         if (nogen)
1003                                 o_dogen();
1004                         o_tmpdrop(1);
1005                 }
1006         } else {
1007                 o_tmpjoin();
1008                 o_filljmp(l2);
1009         }
1010 }
1011
1012 static void opassign(void (*bop)(void (*op)(void)), void (*op)(void))
1013 {
1014         unsigned bt = TYPE_BT(&ts[nts - 1]);
1015         o_tmpcopy();
1016         readexpr();
1017         bop(op);
1018         ts_pop(NULL);
1019         o_assign(bt);
1020 }
1021
1022 static void doassign(void)
1023 {
1024         struct type t;
1025         ts_pop(&t);
1026         if (!t.ptr && t.flags & T_STRUCT)
1027                 o_memcpy(type_totsz(&t));
1028         else
1029                 o_assign(TYPE_BT(&ts[nts - 1]));
1030 }
1031
1032 static void readexpr(void)
1033 {
1034         readcexpr();
1035         if (!tok_jmp('=')) {
1036                 readexpr();
1037                 doassign();
1038                 return;
1039         }
1040         if (!tok_jmp(TOK2("+="))) {
1041                 opassign(ts_binop_add, o_add);
1042                 return;
1043         }
1044         if (!tok_jmp(TOK2("-="))) {
1045                 opassign(ts_binop_add, o_sub);
1046                 return;
1047         }
1048         if (!tok_jmp(TOK2("*="))) {
1049                 opassign(ts_binop, o_mul);
1050                 return;
1051         }
1052         if (!tok_jmp(TOK2("/="))) {
1053                 opassign(ts_binop, o_div);
1054                 return;
1055         }
1056         if (!tok_jmp(TOK2("%="))) {
1057                 opassign(ts_binop, o_mod);
1058                 return;
1059         }
1060         if (!tok_jmp(TOK3("<<="))) {
1061                 opassign(ts_binop, o_shl);
1062                 return;
1063         }
1064         if (!tok_jmp(TOK3(">>="))) {
1065                 opassign(ts_binop, o_shr);
1066                 return;
1067         }
1068         if (!tok_jmp(TOK3("&="))) {
1069                 opassign(ts_binop, o_and);
1070                 return;
1071         }
1072         if (!tok_jmp(TOK3("|="))) {
1073                 opassign(ts_binop, o_or);
1074                 return;
1075         }
1076         if (!tok_jmp(TOK3("^="))) {
1077                 opassign(ts_binop, o_xor);
1078                 return;
1079         }
1080 }
1081
1082 static void readestmt(void)
1083 {
1084         do {
1085                 o_tmpdrop(-1);
1086                 nts = 0;
1087                 readexpr();
1088         } while (!tok_jmp(','));
1089 }
1090
1091 #define F_GLOBAL(flags)         (!((flags) & F_STATIC))
1092
1093 static void globaldef(void *data, struct name *name, unsigned flags)
1094 {
1095         char *varname = flags & F_STATIC ? NULL : name->name;
1096         name->addr = o_mkvar(varname, type_totsz(&name->type), F_GLOBAL(flags));
1097         global_add(name);
1098 }
1099
1100 static void o_localoff(long addr, int off, unsigned bt)
1101 {
1102         o_local(addr, bt);
1103         if (off) {
1104                 o_addr();
1105                 o_num(off, 4);
1106                 o_add();
1107                 o_deref(bt);
1108         }
1109 }
1110
1111 static struct type *innertype(struct type *t)
1112 {
1113         if (t->flags & T_ARRAY && !t->ptr)
1114                 return innertype(&arrays[t->id].type);
1115         return t;
1116 }
1117
1118 static void initexpr(struct type *t, long addr, int off)
1119 {
1120         if (t->flags & T_ARRAY && tok_see() == TOK_STR) {
1121                 struct type *t_de = &arrays[t->id].type;
1122                 if (!t_de->ptr && !t_de->flags && TYPE_SZ(t_de) == 1) {
1123                         char buf[BUFSIZE];
1124                         int len;
1125                         tok_expect(TOK_STR);
1126                         len = tok_str(buf);
1127                         o_localoff(addr, off, TYPE_BT(t));
1128                         o_symaddr(o_mkdat(NULL, buf, len, 0), TYPE_BT(t));
1129                         o_memcpy(len);
1130                         o_tmpdrop(1);
1131                         o_localoff(addr, off + len, TYPE_BT(t));
1132                         o_memset(0, arrays[t->id].n - len);
1133                         o_tmpdrop(1);
1134                         return;
1135                 }
1136         }
1137         if (tok_jmp('{')) {
1138                 o_localoff(addr, off, TYPE_BT(t));
1139                 ts_push(t);
1140                 readexpr();
1141                 doassign();
1142                 ts_pop(NULL);
1143                 o_tmpdrop(1);
1144                 return;
1145         }
1146         if (!t->ptr && t->flags & T_STRUCT) {
1147                 struct structinfo *si = &structs[t->id];
1148                 int i;
1149                 for (i = 0; i < si->nfields; i++) {
1150                         struct name *field = &si->fields[i];
1151                         if (!tok_jmp('.')) {
1152                                 tok_expect(TOK_NAME);
1153                                 field = struct_field(t->id, tok_id());
1154                                 tok_expect('=');
1155                         }
1156                         initexpr(&field->type, addr, off + field->addr);
1157                         if (tok_jmp(',') || tok_see() == '}')
1158                                 break;
1159                 }
1160         } else if (t->flags & T_ARRAY) {
1161                 struct type *t_de = &arrays[t->id].type;
1162                 int i;
1163                 for (i = 0; ; i++) {
1164                         long idx = i;
1165                         struct type *it = t_de;
1166                         if (!tok_jmp('[')) {
1167                                 readexpr();
1168                                 o_popnum(&idx);
1169                                 ts_pop(NULL);
1170                                 tok_expect(']');
1171                                 tok_expect('=');
1172                         }
1173                         if (tok_see() != '{')
1174                                 it = innertype(t_de);
1175                         initexpr(it, addr, off + type_totsz(it) * idx);
1176                         if (tok_jmp(',') || tok_see() == '}')
1177                                 break;
1178                 }
1179         }
1180         tok_expect('}');
1181 }
1182
1183 static void localdef(void *data, struct name *name, unsigned flags)
1184 {
1185         if (flags & F_STATIC) {
1186                 globaldef(data, name, flags);
1187                 return;
1188         }
1189         name->addr = o_mklocal(type_totsz(&name->type));
1190         local_add(name);
1191         if (flags & F_INIT) {
1192                 struct type *t = &name->type;
1193                 if (tok_see() == '{') {
1194                         o_local(name->addr, TYPE_BT(t));
1195                         o_memset(0, type_totsz(t));
1196                         o_tmpdrop(1);
1197                 }
1198                 initexpr(t, name->addr, 0);
1199         }
1200 }
1201
1202 static void funcdef(struct name *name, struct name *args,
1203                         int nargs, unsigned flags)
1204 {
1205         int i;
1206         name->addr = o_func_beg(name->name, F_GLOBAL(flags));
1207         global_add(name);
1208         ret_bt = TYPE_BT(&funcs[name->type.id].ret);
1209         for (i = 0; i < nargs; i++) {
1210                 args[i].addr = o_arg(i, type_totsz(&args[i].type));
1211                 local_add(&args[i]);
1212         }
1213 }
1214
1215 static int readargs(struct name *args)
1216 {
1217         int nargs = 0;
1218         tok_expect('(');
1219         while (tok_see() != ')') {
1220                 readtype(&args[nargs].type);
1221                 if (!tok_jmp(TOK_NAME))
1222                         strcpy(args[nargs++].name, tok_id());
1223                 if (tok_jmp(','))
1224                         break;
1225         }
1226         tok_expect(')');
1227         return nargs;
1228 }
1229
1230 static int readdefs(void (*def)(void *data, struct name *name, unsigned flags),
1231                         void *data)
1232 {
1233         struct type base;
1234         unsigned flags;
1235         if (basetype(&base, &flags))
1236                 return 1;
1237         while (tok_see() != ';' && tok_see() != '{') {
1238                 struct type tpool[3];
1239                 struct name name;
1240                 int npool = 0;
1241                 struct type *type = &tpool[npool++];
1242                 struct type *func = NULL;
1243                 struct type *ret = NULL;
1244                 memset(tpool, 0, sizeof(tpool));
1245                 memcpy(type, &base, sizeof(base));
1246                 readptrs(type);
1247                 if (!tok_jmp('(')) {
1248                         ret = type;
1249                         type = &tpool[npool++];
1250                         func = type;
1251                         readptrs(type);
1252                 }
1253                 tok_expect(TOK_NAME);
1254                 strcpy(name.name, tok_id());
1255                 while (!tok_jmp('[')) {
1256                         long n;
1257                         readexpr();
1258                         ts_pop(NULL);
1259                         if (o_popnum(&n))
1260                                 die("const expr expected\n");
1261                         type->id = array_add(type, n);
1262                         if (type->flags & T_FUNC)
1263                                 func = &arrays[type->id].type;
1264                         type->flags = T_ARRAY;
1265                         type->bt = 8;
1266                         type->ptr = 0;
1267                         tok_expect(']');
1268                 }
1269                 if (func)
1270                         tok_expect(')');
1271                 if (tok_see() == '(') {
1272                         struct name args[MAXARGS];
1273                         int nargs = readargs(args);
1274                         int fdef = !func;
1275                         if (!func) {
1276                                 ret = type;
1277                                 type = &tpool[npool++];
1278                                 func = type;
1279                         }
1280                         func->flags = T_FUNC;
1281                         func->bt = 8;
1282                         func->id = func_create(ret, args, nargs);
1283                         if (fdef && tok_see() == '{') {
1284                                 memcpy(&name.type, func, sizeof(*func));
1285                                 funcdef(&name, args, nargs, flags);
1286                                 return 0;
1287                         }
1288                 }
1289                 memcpy(&name.type, type, sizeof(*type));
1290                 if (!tok_jmp('='))
1291                         flags |= F_INIT;
1292                 def(data, &name, flags);
1293                 tok_jmp(',');
1294         }
1295         return 0;
1296 }
1297
1298 static void typedefdef(void *data, struct name *name, unsigned flags)
1299 {
1300         typedef_add(name->name, &name->type);
1301 }
1302
1303 #define MAXCASES                (1 << 7)
1304
1305 static void readstmt(void);
1306
1307 static void readswitch(void)
1308 {
1309         int break_beg = nbreaks;
1310         long val_addr = o_mklocal(8);
1311         long matched[MAXCASES];
1312         int nmatched = 0;
1313         struct type t;
1314         long next;
1315         int ref = 1;
1316         int i;
1317         tok_expect('(');
1318         readexpr();
1319         ts_pop(&t);
1320         o_local(val_addr, TYPE_BT(&t));
1321         o_tmpswap();
1322         o_assign(TYPE_BT(&t));
1323         o_tmpdrop(1);
1324         tok_expect(')');
1325         tok_expect('{');
1326         while (tok_jmp('}')) {
1327                 int n = 0;
1328                 while (tok_see() == TOK_CASE || tok_see() == TOK_DEFAULT) {
1329                         if (n++ > 0)
1330                                 matched[nmatched++] = o_jmp(0);
1331                         if (!ref++)
1332                                 o_filljmp(next);
1333                         if (!tok_jmp(TOK_CASE)) {
1334                                 readexpr();
1335                                 o_local(val_addr, TYPE_BT(&t));
1336                                 o_eq();
1337                                 next = o_jz(0);
1338                                 ref = 0;
1339                                 tok_expect(':');
1340                                 o_tmpdrop(1);
1341                                 ts_pop(NULL);
1342                                 continue;
1343                         }
1344                         if (!tok_jmp(TOK_DEFAULT)) {
1345                                 tok_expect(':');
1346                                 continue;
1347                         }
1348                 }
1349                 for (i = 0; i < nmatched; i++)
1350                         o_filljmp(matched[i]);
1351                 nmatched = 0;
1352                 readstmt();
1353         }
1354         o_rmlocal(val_addr, 8);
1355         if (!ref++)
1356                 o_filljmp(next);
1357         break_fill(o_mklabel(), break_beg);
1358 }
1359
1360 #define MAXGOTO                 (1 << 7)
1361
1362 static struct gotoinfo {
1363         char name[NAMELEN];
1364         long addr;
1365 } gotos[MAXGOTO];
1366 static int ngotos;
1367
1368 static struct labelinfo {
1369         char name[NAMELEN];
1370         long addr;
1371 } labels[MAXGOTO];
1372 static int nlabels;
1373
1374 static void goto_add(char *name)
1375 {
1376         strcpy(gotos[ngotos].name, name);
1377         gotos[ngotos++].addr = o_jmp(0);
1378 }
1379
1380 static void label_add(char *name)
1381 {
1382         strcpy(labels[nlabels].name, name);
1383         labels[nlabels++].addr = o_mklabel();
1384 }
1385
1386 static void goto_fill(void)
1387 {
1388         int i, j;
1389         for (i = 0; i < ngotos; i++)
1390                 for (j = 0; j < nlabels; j++)
1391                         if (!strcmp(gotos[i].name, labels[j].name)) {
1392                                 o_filljmp2(gotos[i].addr, labels[j].addr);
1393                                 break;
1394                         }
1395 }
1396
1397 static void readstmt(void)
1398 {
1399         o_tmpdrop(-1);
1400         nts = 0;
1401         if (!tok_jmp('{')) {
1402                 int _nlocals = nlocals;
1403                 int _nglobals = nglobals;
1404                 int _nenums = nenums;
1405                 int _ntypedefs = ntypedefs;
1406                 int _nstructs = nstructs;
1407                 int _nfuncs = nfuncs;
1408                 int _narrays = narrays;
1409                 while (tok_jmp('}'))
1410                         readstmt();
1411                 nlocals = _nlocals;
1412                 nenums = _nenums;
1413                 ntypedefs = _ntypedefs;
1414                 nstructs = _nstructs;
1415                 nfuncs = _nfuncs;
1416                 narrays = _narrays;
1417                 nglobals = _nglobals;
1418                 return;
1419         }
1420         if (!readdefs(localdef, NULL)) {
1421                 tok_expect(';');
1422                 return;
1423         }
1424         if (!tok_jmp(TOK_TYPEDEF)) {
1425                 readdefs(typedefdef, NULL);
1426                 tok_expect(';');
1427                 return;
1428         }
1429         if (!tok_jmp(TOK_IF)) {
1430                 long l1, l2;
1431                 tok_expect('(');
1432                 readexpr();
1433                 tok_expect(')');
1434                 l1 = o_jz(0);
1435                 readstmt();
1436                 if (!tok_jmp(TOK_ELSE)) {
1437                         l2 = o_jmp(0);
1438                         o_filljmp(l1);
1439                         readstmt();
1440                         o_filljmp(l2);
1441                 } else {
1442                         o_filljmp(l1);
1443                 }
1444                 return;
1445         }
1446         if (!tok_jmp(TOK_WHILE)) {
1447                 long l1, l2;
1448                 int break_beg = nbreaks;
1449                 int continue_beg = ncontinues;
1450                 l1 = o_mklabel();
1451                 tok_expect('(');
1452                 readexpr();
1453                 tok_expect(')');
1454                 l2 = o_jz(0);
1455                 readstmt();
1456                 o_jmp(l1);
1457                 o_filljmp(l2);
1458                 break_fill(o_mklabel(), break_beg);
1459                 continue_fill(l1, continue_beg);
1460                 return;
1461         }
1462         if (!tok_jmp(TOK_DO)) {
1463                 long l1, l2;
1464                 int break_beg = nbreaks;
1465                 int continue_beg = ncontinues;
1466                 l1 = o_mklabel();
1467                 readstmt();
1468                 tok_expect(TOK_WHILE);
1469                 tok_expect('(');
1470                 l2 = o_mklabel();
1471                 readexpr();
1472                 o_jnz(l1);
1473                 tok_expect(')');
1474                 break_fill(o_mklabel(), break_beg);
1475                 continue_fill(l2, continue_beg);
1476                 return;
1477         }
1478         if (!tok_jmp(TOK_FOR)) {
1479                 long check, jump, end, body;
1480                 int break_beg = nbreaks;
1481                 int continue_beg = ncontinues;
1482                 tok_expect('(');
1483                 if (tok_see() != ';')
1484                         readestmt();
1485                 tok_expect(';');
1486                 check = o_mklabel();
1487                 if (tok_see() != ';')
1488                         readestmt();
1489                 tok_expect(';');
1490                 end = o_jz(0);
1491                 body = o_jmp(0);
1492                 jump = o_mklabel();
1493                 if (tok_see() != ')')
1494                         readestmt();
1495                 tok_expect(')');
1496                 o_jmp(check);
1497                 o_filljmp(body);
1498                 readstmt();
1499                 o_jmp(jump);
1500                 o_filljmp(end);
1501                 break_fill(o_mklabel(), break_beg);
1502                 continue_fill(jump, continue_beg);
1503                 return;
1504         }
1505         if (!tok_jmp(TOK_SWITCH)) {
1506                 readswitch();
1507                 return;
1508         }
1509         if (!tok_jmp(TOK_RETURN)) {
1510                 int ret = tok_see() != ';';
1511                 if (ret)
1512                         readexpr();
1513                 tok_expect(';');
1514                 o_ret(ret_bt);
1515                 return;
1516         }
1517         if (!tok_jmp(TOK_BREAK)) {
1518                 tok_expect(';');
1519                 breaks[nbreaks++] = o_jmp(0);
1520                 return;
1521         }
1522         if (!tok_jmp(TOK_CONTINUE)) {
1523                 tok_expect(';');
1524                 continues[ncontinues++] = o_jmp(0);
1525                 return;
1526         }
1527         if (!tok_jmp(TOK_GOTO)) {
1528                 tok_expect(TOK_NAME);
1529                 goto_add(tok_id());
1530                 tok_expect(';');
1531                 return;
1532         }
1533         readestmt();
1534         /* labels */
1535         if (!tok_jmp(':')) {
1536                 label_add(tok_id());
1537                 return;
1538         }
1539         tok_expect(';');
1540 }
1541
1542 static void readdecl(void)
1543 {
1544         if (!tok_jmp(TOK_TYPEDEF)) {
1545                 readdefs(typedefdef, NULL);
1546                 tok_expect(';');
1547                 return;
1548         }
1549         readdefs(globaldef, NULL);
1550         if (tok_see() == '{') {
1551                 readstmt();
1552                 goto_fill();
1553                 o_func_end();
1554                 nlocals = 0;
1555                 ngotos = 0;
1556                 nlabels = 0;
1557                 return;
1558         }
1559         tok_expect(';');
1560 }
1561
1562 static void parse(void)
1563 {
1564         while (tok_see() != TOK_EOF)
1565                 readdecl();
1566 }
1567
1568 int main(int argc, char *argv[])
1569 {
1570         char obj[128];
1571         int ifd, ofd;
1572         int i = 1;
1573         while (i < argc && argv[i][0] == '-')
1574                 i++;
1575         if (i == argc)
1576                 die("no file given\n");
1577         ifd = open(argv[i], O_RDONLY);
1578         tok_init(ifd);
1579         close(ifd);
1580         parse();
1581
1582         strcpy(obj, argv[i]);
1583         obj[strlen(obj) - 1] = 'o';
1584         ofd = open(obj, O_WRONLY | O_TRUNC | O_CREAT, 0600);
1585         out_write(ofd);
1586         close(ofd);
1587         return 0;
1588 }