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