tcc.c

   1 /*
   2  *  TCC - Tiny C Compiler
   3  *
   4  *  Copyright (c) 2001 Fabrice Bellard
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  */
  20 #include "tcclib.h"
  21
  22 #define INCLUDE_PATH "/usr/include"
  23
  24 #define TEXT_SIZE           50000
  25 #define DATA_SIZE           50000
  26 #define SYM_TABLE_SIZE      10000
  27 #define MACRO_STACK_SIZE    32
  28 #define INCLUDE_STACK_SIZE  32
  29
  30 #define NB_REGS             3
  31
  32 /* symbol management */
  33 typedef struct Sym {
  34     int v;    /* symbol token */
  35     int t;    /* associated type */
  36     int c;    /* associated number */
  37     struct Sym *next; /* next related symbol */
  38     struct Sym *prev; /* prev symbol in stack */
  39 } Sym;
  40
  41 #define SYM_STRUCT 0x40000000 /* struct/union/enum symbol space */
  42 #define SYM_FIELD  0x20000000 /* struct/union field symbol space */
  43
  44 typedef struct {
  45     FILE *file; /* stdio file */
  46     char *filename;
  47     int line_num;
  48 } IncludeFile;
  49
  50 /* loc : local variable index
  51    glo : global variable index
  52    ind : output code ptr
  53    rsym: return symbol
  54    prog: output code
  55    anon_sym: anonymous symbol index
  56 */
  57 FILE *file;
  58 int tok, tok1, tokc, rsym, anon_sym,
  59     prog, ind, loc, glo, vt, *vstack, *vstack_ptr,
  60     vc, line_num;
  61 char *idtable, *idptr, *filename;
  62 Sym *define_stack, *global_stack, *local_stack, *label_stack;
  63
  64 char *macro_stack[MACRO_STACK_SIZE], **macro_stack_ptr, *macro_ptr;
  65 IncludeFile include_stack[INCLUDE_STACK_SIZE], *include_stack_ptr;
  66
  67 /* The current value can be: */
  68 #define VT_VALMASK 0x000f
  69 #define VT_CONST   0x000a  /* constant in vc
  70                               (must be first non register value) */
  71 #define VT_LLOCAL  0x000b  /* lvalue, offset on stack */
  72 #define VT_LOCAL   0x000c  /* offset on stack */
  73 #define VT_CMP     0x000d  /* the value is stored in processor flags (in vc) */
  74 #define VT_JMP     0x000e  /* value is the consequence of jmp true */
  75 #define VT_JMPI    0x000f  /* value is the consequence of jmp false */
  76 #define VT_LVAL    0x0010  /* var is an lvalue */
  77 #define VT_LVALN   -17         /* ~VT_LVAL */
  78 #define VT_FORWARD 0x0020  /* value is forward reference
  79                               (only used for functions) */
  80
  81 #define VT_VOID     0x00040
  82 #define VT_BYTE     0x00080  /* byte type */
  83 #define VT_PTR      0x00100  /* pointer increment */
  84 #define VT_UNSIGNED 0x00200  /* unsigned type */
  85 #define VT_ARRAY    0x00400  /* array type (only used in parsing) */
  86 #define VT_ENUM     0x00800  /* enum definition */
  87 #define VT_FUNC     0x01000  /* function type */
  88 #define VT_STRUCT  0x002000  /* struct/union definition */
  89 #define VT_TYPEDEF 0x004000  /* typedef definition */
  90 #define VT_EXTERN  0x008000   /* extern definition */
  91 #define VT_STATIC  0x010000   /* static variable */
  92 #define VT_STRUCT_SHIFT 17   /* structure/enum name shift (12 bits lefts) */
  93
  94 #define VT_TYPE    0xffffffc0  /* type mask */
  95 #define VT_TYPEN   0x0000003f  /* ~VT_TYPE */
  96 #define VT_FUNCN   -4097       /* ~VT_FUNC */
  97
  98
  99 /* Special infos */
 100
 101 /* token values */
 102 #define TOK_INT      256
 103 #define TOK_VOID     257
 104 #define TOK_CHAR     258
 105 #define TOK_IF       259
 106 #define TOK_ELSE     260
 107 #define TOK_WHILE    261
 108 #define TOK_BREAK    262
 109 #define TOK_RETURN   263
 110 #define TOK_DEFINE   264
 111 #define TOK_MAIN     265
 112 #define TOK_FOR      266
 113 #define TOK_EXTERN   267
 114 #define TOK_STATIC   268
 115 #define TOK_UNSIGNED 269
 116 #define TOK_GOTO     270
 117 #define TOK_DO       271
 118 #define TOK_CONTINUE 272
 119 #define TOK_SWITCH   273
 120 #define TOK_CASE     274
 121
 122 /* ignored types Must have contiguous values */
 123 #define TOK_CONST    275
 124 #define TOK_VOLATILE 276
 125 #define TOK_LONG     277
 126 #define TOK_REGISTER 278
 127 #define TOK_SIGNED   279
 128 #define TOK_AUTO     280
 129 #define TOK_INLINE   281
 130
 131 #define TOK_FLOAT    282 /* unsupported */
 132 #define TOK_DOUBLE   283 /* unsupported */
 133
 134 #define TOK_STRUCT   284
 135 #define TOK_UNION    285
 136 #define TOK_TYPEDEF  286
 137 #define TOK_DEFAULT  287
 138 #define TOK_ENUM     288
 139 #define TOK_SIZEOF   289
 140 #define TOK_INCLUDE  290
 141
 142 #define TOK_EQ 0x94 /* warning: depend on asm code */
 143 #define TOK_NE 0x95 /* warning: depend on asm code */
 144 #define TOK_LT 0x9c /* warning: depend on asm code */
 145 #define TOK_GE 0x9d /* warning: depend on asm code */
 146 #define TOK_LE 0x9e /* warning: depend on asm code */
 147 #define TOK_GT 0x9f /* warning: depend on asm code */
 148
 149 #define TOK_LAND  0xa0
 150 #define TOK_LOR   0xa1
 151
 152 #define TOK_DEC   0xa2
 153 #define TOK_MID   0xa3 /* inc/dec, to void constant */
 154 #define TOK_INC   0xa4
 155 #define TOK_ARROW 0xa7
 156 #define TOK_DOTS  0xa8 /* three dots */
 157 #define TOK_SHR   0xa9 /* unsigned shift right */
 158 #define TOK_UDIV  0xb0 /* unsigned division */
 159 #define TOK_UMOD  0xb1 /* unsigned modulo */
 160 #define TOK_PDIV  0xb2 /* fast division with undefined rounding for pointers */
 161 #define TOK_NUM   0xb3 /* number in tokc */
 162
 163 #define TOK_SHL   0x01 /* shift left */
 164 #define TOK_SAR   0x02 /* signed shift right */
 165
 166 /* assignement operators : normal operator or 0x80 */
 167 #define TOK_A_MOD 0xa5
 168 #define TOK_A_AND 0xa6
 169 #define TOK_A_MUL 0xaa
 170 #define TOK_A_ADD 0xab
 171 #define TOK_A_SUB 0xad
 172 #define TOK_A_DIV 0xaf
 173 #define TOK_A_XOR 0xde
 174 #define TOK_A_OR  0xfc
 175 #define TOK_A_SHL 0x81
 176 #define TOK_A_SAR 0x82
 177
 178 void sum();
 179 void next();
 180 void expr_eq();
 181 void expr();
 182 void decl();
 183 int gv();
 184 void move_reg();
 185 void save_reg();
 186
 187 int isid(c)
 188 {
 189     return (c >= 'a' & c <= 'z') |
 190         (c >= 'A' & c <= 'Z') |
 191         c == '_';
 192 }
 193
 194 int isnum(c)
 195 {
 196     return c >= '0' & c <= '9';
 197 }
 198
 199 #ifndef TINY
 200 /* XXX: use stderr ? */
 201 void error(char *msg)
 202 {
 203     printf("%s:%d: %s\n", filename, line_num, msg);
 204     exit(1);
 205 }
 206
 207 void expect(char *msg)
 208 {
 209     printf("%s:%d: %s expected\n", filename, line_num, msg);
 210     exit(1);
 211 }
 212
 213 void warning(char *msg)
 214 {
 215     printf("%s:%d: warning: %s\n", filename, line_num, msg);
 216 }
 217
 218 void skip(c)
 219 {
 220     if (tok != c) {
 221         printf("%s:%d: '%c' expected\n", filename, line_num, c);
 222         exit(1);
 223     }
 224     next();
 225 }
 226
 227 void test_lvalue()
 228 {
 229     if (!(vt & VT_LVAL))
 230         expect("lvalue");
 231 }
 232
 233 #else
 234
 235 #define skip(c) next()
 236 #define test_lvalue()
 237
 238 #endif
 239
 240 char *get_tok_str(int v)
 241 {
 242     int t;
 243     char *p;
 244     p = idtable;
 245     t = 256;
 246     while (t != v) {
 247         if (p >= idptr)
 248             return 0;
 249         while (*p++);
 250         t++;
 251     }
 252     return p;
 253 }
 254
 255 /* find a symbol and return its associated structure. 's' is the top
 256    of the symbol stack */
 257 Sym *sym_find1(Sym *s, int v)
 258 {
 259     while (s) {
 260         if (s->v == v)
 261             return s;
 262         s = s->prev;
 263     }
 264     return 0;
 265 }
 266
 267 Sym *sym_push1(Sym **ps, int v, int t, int c)
 268 {
 269     Sym *s;
 270     s = malloc(sizeof(Sym));
 271     if (!s)
 272         error("memory full");
 273     s->v = v;
 274     s->t = t;
 275     s->c = c;
 276     s->next = 0;
 277     s->prev = *ps;
 278     *ps = s;
 279     return s;
 280 }
 281
 282 /* find a symbol in the right symbol space */
 283 Sym *sym_find(int v)
 284 {
 285     Sym *s;
 286     s = sym_find1(local_stack, v);
 287     if (!s)
 288         s = sym_find1(global_stack, v);
 289     return s;
 290 }
 291
 292 /* push a given symbol on the symbol stack */
 293 Sym *sym_push(int v, int t, int c)
 294 {
 295     //    printf("sym_push: %x %s type=%x\n", v, get_tok_str(v), t);
 296     if (local_stack)
 297         return sym_push1(&local_stack, v, t, c);
 298     else
 299         return sym_push1(&global_stack, v, t, c);
 300 }
 301
 302 /* pop symbols until top reaches 'b' */
 303 void sym_pop(Sym **ps, Sym *b)
 304 {
 305     Sym *s, *ss;
 306
 307     s = *ps;
 308     while(s != b) {
 309         ss = s->prev;
 310         //        printf("sym_pop: %x %s type=%x\n", s->v, get_tok_str(s->v), s->t);
 311         free(s);
 312         s = ss;
 313     }
 314     *ps = b;
 315 }
 316
 317 int ch, ch1;
 318
 319 /* read next char from current input file */
 320 void inp()
 321 {
 322     int c;
 323
 324  redo:
 325     ch1 = fgetc(file);
 326     if (ch1 == -1) {
 327         if (include_stack_ptr == include_stack)
 328             return;
 329         /* pop include stack */
 330         fclose(file);
 331         free(filename);
 332         include_stack_ptr--;
 333         file = include_stack_ptr->file;
 334         filename = include_stack_ptr->filename;
 335         line_num = include_stack_ptr->line_num;
 336         goto redo;
 337     }
 338     if (ch1 == '\n')
 339         line_num++;
 340     //    printf("ch1=%c\n", ch1);
 341 }
 342
 343 /* input with '\\n' handling and macro subtitution if in macro state */
 344 void minp()
 345 {
 346     if (macro_ptr != 0) {
 347         ch = *macro_ptr++;
 348         /* end of macro ? */
 349         if (ch == '\0') {
 350             macro_ptr = *--macro_stack_ptr;
 351             ch = (int)*--macro_stack_ptr;
 352         }
 353     } else {
 354     redo:
 355         ch = ch1;
 356         inp();
 357         if (ch == '\\' && ch1 == '\n') {
 358             inp();
 359             goto redo;
 360         }
 361     }
 362 }
 363
 364 /* same as minp, but also skip comments */
 365 void cinp()
 366 {
 367     int c;
 368
 369     if (ch1 == '/') {
 370         inp();
 371         if (ch1 == '/') {
 372             /* single line C++ comments */
 373             inp();
 374             while (ch1 != '\n' && ch1 != -1)
 375                 inp();
 376             inp();
 377             ch = ' '; /* return space */
 378         } else if (ch1 == '*') {
 379             /* C comments */
 380             inp();
 381             while (ch1 != -1) {
 382                 c = ch1;
 383                 inp();
 384                 if (c == '*' && ch1 == '/') {
 385                     inp();
 386                     ch = ' '; /* return space */
 387                     break;
 388                 }
 389             }
 390         } else {
 391             ch = '/';
 392         }
 393     } else {
 394         minp();
 395     }
 396 }
 397
 398 void skip_spaces()
 399 {
 400     while (ch == ' ' || ch == '\t')
 401         cinp();
 402 }
 403
 404 void preprocess()
 405 {
 406     char *str;
 407     int size, n, c;
 408     char buf[1024], *q, *p;
 409     char buf1[1024];
 410     FILE *f;
 411
 412     cinp();
 413     next(); /* XXX: should pass parameter to avoid macro subst */
 414     if (tok == TOK_DEFINE) {
 415         next(); /* XXX: should pass parameter to avoid macro subst */
 416         skip_spaces();
 417         /* now 'tok' is the macro symbol */
 418         str = NULL;
 419         size = 0;
 420         n = 0;
 421         while (1) {
 422             if ((n + 1) >= size) {
 423                 size += 128;
 424                 str = realloc(str, size);
 425                 if (!str)
 426                     error("memory full");
 427             }
 428             if (ch == -1 || ch == '\n') {
 429                 str[n++] = ' '; /* a space is inserted after each macro */
 430                 str[n++] = '\0';
 431                 break;
 432             }
 433             str[n++] = ch;
 434             cinp();
 435         }
 436         sym_push1(&define_stack, tok, 0, (int)str);
 437     } else if (tok == TOK_INCLUDE) {
 438         skip_spaces();
 439         if (ch == '<') {
 440             c = '>';
 441             goto read_name;
 442         } else if (ch == '\"') {
 443             c = ch;
 444         read_name:
 445             minp();
 446             q = buf;
 447             while (ch != c && ch != '\n' && ch != -1) {
 448                 if ((q - buf) < sizeof(buf) - 1)
 449                     *q++ = ch;
 450                 minp();
 451             }
 452             *q = '\0';
 453             if (include_stack_ptr >= include_stack + INCLUDE_STACK_SIZE)
 454                 error("memory full");
 455             if (c == '\"') {
 456                 /* first search in current dir if "header.h" */
 457                 /* XXX: buffer overflow */
 458                 size = 0;
 459                 p = strrchr(filename, '/');
 460                 if (p)
 461                     size = p + 1 - filename;
 462                 memcpy(buf1, filename, size);
 463                 buf1[size] = '\0';
 464                 strcat(buf1, buf);
 465                 f = fopen(buf1, "r");
 466                 if (f)
 467                     goto found;
 468             }
 469             /* now search in standard include path */
 470             strcpy(buf1, INCLUDE_PATH);
 471             strcat(buf1, "/");
 472             strcat(buf1, buf);
 473             f = fopen(buf1, "r");
 474             if (!f)
 475                 error("include file not found");
 476         found:
 477             /* push current file in stack */
 478             include_stack_ptr->file = file;
 479             include_stack_ptr->filename = filename;
 480             include_stack_ptr->line_num = line_num;
 481             include_stack_ptr++;
 482             file = f;
 483             filename = strdup(buf1);
 484             line_num = 1;
 485         }
 486
 487     }
 488     /* ignore other preprocess commands or #! for C scripts */
 489     while (ch != '\n' && ch != -1)
 490         cinp();
 491 }
 492
 493 /* read a number in base b */
 494 int getn(b)
 495 {
 496     int n, t;
 497     n = 0;
 498     while (1) {
 499         if (ch >= 'a' & ch <= 'f')
 500             t = ch - 'a' + 10;
 501         else if (ch >= 'A' & ch <= 'F')
 502             t = ch - 'A' + 10;
 503         else if (isnum(ch))
 504             t = ch - '0';
 505         else
 506             break;
 507         if (t < 0 | t >= b)
 508             break;
 509         n = n * b + t;
 510         cinp();
 511     }
 512     return n;
 513 }
 514
 515 void next()
 516 {
 517     int v, b;
 518     char *q, *p;
 519     Sym *s;
 520
 521     /* special 'ungettok' case for label parsing */
 522     if (tok1) {
 523         tok = tok1;
 524         tok1 = 0;
 525         return;
 526     }
 527  redo:
 528     /* skip spaces */
 529     while(1) {
 530         while (ch == '\n') {
 531             cinp();
 532             while (ch == ' ' || ch == 9)
 533                 cinp();
 534             if (ch == '#') {
 535                 /* preprocessor command if # at start of line after
 536                    spaces */
 537                 preprocess();
 538             }
 539         }
 540         if (ch != ' ' && ch != 9)
 541             break;
 542         cinp();
 543     }
 544     if (isid(ch)) {
 545         q = idptr;
 546         while(isid(ch) | isnum(ch)) {
 547             *q++ = ch;
 548             cinp();
 549         }
 550         *q++ = '\0';
 551         p = idtable;
 552         tok = 256;
 553         while (p < idptr) {
 554             if (strcmp(p, idptr) == 0)
 555                 break;
 556             while (*p++);
 557             tok++;
 558         }
 559         //        printf("id=%s\n", idptr);
 560         /* if not found, add symbol */
 561         if (p == idptr)
 562             idptr = q;
 563         /* if symbol is a define, prepare substitution */
 564         if (s = sym_find1(define_stack, tok)) {
 565             if ((macro_stack_ptr - macro_stack) >= MACRO_STACK_SIZE)
 566                 error("too many nested macros");
 567             *macro_stack_ptr++ = (char *)ch;
 568             *macro_stack_ptr++ = macro_ptr;
 569             macro_ptr = (char *)s->c;
 570             cinp();
 571             goto redo;
 572         }
 573     } else if (isnum(ch)) {
 574         /* number */
 575         b = 10;
 576         if (ch == '0') {
 577             cinp();
 578             b = 8;
 579             if (ch == 'x') {
 580                 cinp();
 581                 b = 16;
 582             }
 583         }
 584         tokc = getn(b);
 585         tok = TOK_NUM;
 586     } else {
 587 #ifdef TINY
 588         q = "<=\236>=\235!=\225++\244--\242==\224";
 589 #else
 590         q = "<=\236>=\235!=\225&&\240||\241++\244--\242==\224<<\1>>\2+=\253-=\255*=\252/=\257%=\245&=\246^=\336|=\374->\247..\250";
 591 #endif
 592         /* two chars */
 593         tok = ch;
 594         cinp();
 595         while (*q) {
 596             if (*q == tok & q[1] == ch) {
 597                 cinp();
 598                 tok = q[2] & 0xff;
 599                 /* three chars tests */
 600                 if (tok == TOK_SHL | tok == TOK_SAR) {
 601                     if (ch == '=') {
 602                         tok = tok | 0x80;
 603                         cinp();
 604                     }
 605                 } else if (tok == TOK_DOTS) {
 606                     if (ch != '.')
 607                         error("parse error");
 608                     cinp();
 609                 }
 610                 return;
 611             }
 612             q = q + 3;
 613         }
 614         /* single char substitutions */
 615         if (tok == '<')
 616             tok = TOK_LT;
 617         else if (tok == '>')
 618             tok = TOK_GT;
 619     }
 620 }
 621
 622 void swap(int *p, int *q)
 623 {
 624     int t;
 625     t = *p;
 626     *p = *q;
 627     *q = t;
 628 }
 629
 630 void vset(t, v)
 631 {
 632     vt = t;
 633     vc = v;
 634 }
 635
 636 /******************************************************/
 637 /* X86 code generator */
 638
 639 void g(c)
 640 {
 641     *(char *)ind++ = c;
 642 }
 643
 644 void o(c)
 645 {
 646     while (c) {
 647         g(c);
 648         c = c / 256;
 649     }
 650 }
 651
 652 /* output a symbol and patch all calls to it */
 653 void gsym_addr(t, a)
 654 {
 655     int n;
 656     while (t) {
 657         n = *(int *)t; /* next value */
 658         *(int *)t = a - t - 4;
 659         t = n;
 660     }
 661 }
 662
 663 void gsym(t)
 664 {
 665     gsym_addr(t, ind);
 666 }
 667
 668 /* psym is used to put an instruction with a data field which is a
 669    reference to a symbol. It is in fact the same as oad ! */
 670 #define psym oad
 671
 672 /* instruction + 4 bytes data. Return the address of the data */
 673 int oad(c, s)
 674 {
 675     o(c);
 676     *(int *)ind = s;
 677     s = ind;
 678     ind = ind + 4;
 679     return s;
 680 }
 681
 682 /* XXX: generate correct pointer for forward references to functions */
 683 /* r = (ft, fc) */
 684 void load(r, ft, fc)
 685 {
 686     int v, t;
 687
 688     v = ft & VT_VALMASK;
 689     if (ft & VT_LVAL) {
 690         if (v == VT_LLOCAL) {
 691             load(r, VT_LOCAL | VT_LVAL, fc);
 692             v = r;
 693         }
 694         if ((ft & VT_TYPE) == VT_BYTE)
 695             o(0xbe0f);   /* movsbl */
 696         else
 697             o(0x8b);     /* movl */
 698         if (v == VT_CONST) {
 699             oad(0x05 + r * 8, fc); /* 0xXX, r */
 700         } else if (v == VT_LOCAL) {
 701             oad(0x85 + r * 8, fc); /* xx(%ebp), r */
 702         } else {
 703             g(0x00 + r * 8 + v); /* (v), r */
 704         }
 705     } else {
 706         if (v == VT_CONST) {
 707             oad(0xb8 + r, fc); /* mov $xx, r */
 708         } else if (v == VT_LOCAL) {
 709             o(0x8d);
 710             oad(0x85 + r * 8, fc); /* lea xxx(%ebp), r */
 711         } else if (v == VT_CMP) {
 712             oad(0xb8 + r, 0); /* mov $0, r */
 713             o(0x0f); /* setxx %br */
 714             o(fc);
 715             o(0xc0 + r);
 716         } else if (v == VT_JMP || v == VT_JMPI) {
 717             t = v & 1;
 718             oad(0xb8 + r, t); /* mov $1, r */
 719             oad(0xe9, 5); /* jmp after */
 720             gsym(fc);
 721             oad(0xb8 + r, t ^ 1); /* mov $0, r */
 722         } else if (v != r) {
 723             o(0x89);
 724             o(0xc0 + r + v * 8); /* mov v, r */
 725         }
 726     }
 727 }
 728
 729 /* (ft, fc) = r */
 730 /* WARNING: r must not be allocated on the stack */
 731 void store(r, ft, fc)
 732 {
 733     int fr, b;
 734
 735     fr = ft & VT_VALMASK;
 736     b = (ft & VT_TYPE) == VT_BYTE;
 737     o(0x89 - b);
 738     if (fr == VT_CONST) {
 739         oad(0x05 + r * 8, fc); /* mov r,xxx */
 740     } else if (fr == VT_LOCAL) {
 741         oad(0x85 + r * 8, fc); /* mov r,xxx(%ebp) */
 742     } else if (ft & VT_LVAL) {
 743         g(fr + r * 8); /* mov r, (fr) */
 744     } else if (fr != r) {
 745         o(0xc0 + fr + r * 8); /* mov r, fr */
 746     }
 747 }
 748
 749 int gjmp(t)
 750 {
 751     return psym(0xe9, t);
 752 }
 753
 754 /* generate a test. set 'inv' to invert test */
 755 int gtst(inv, t)
 756 {
 757     int v, *p;
 758     v = vt & VT_VALMASK;
 759     if (v == VT_CMP) {
 760         /* fast case : can jump directly since flags are set */
 761         g(0x0f);
 762         t = psym((vc - 16) ^ inv, t);
 763     } else if (v == VT_JMP || v == VT_JMPI) {
 764         /* && or || optimization */
 765         if ((v & 1) == inv) {
 766             /* insert vc jump list in t */
 767             p = &vc;
 768             while (*p != 0)
 769                 p = (int *)*p;
 770             *p = t;
 771             t = vc;
 772         } else {
 773             t = gjmp(t);
 774             gsym(vc);
 775         }
 776     } else if ((vt & (VT_VALMASK | VT_LVAL)) == VT_CONST) {
 777         /* constant jmp optimization */
 778         if ((vc != 0) != inv)
 779             t = gjmp(t);
 780     } else {
 781         v = gv();
 782         o(0x85);
 783         o(0xc0 + v * 9);
 784         g(0x0f);
 785         t = psym(0x85 ^ inv, t);
 786     }
 787     return t;
 788 }
 789
 790 /* generate a binary operation 'v = r op fr' instruction and modifies
 791    (vt,vc) if needed */
 792 void gen_op1(op, r, fr)
 793 {
 794     int t;
 795     if (op == '+') {
 796         o(0x01);
 797         o(0xc0 + r + fr * 8);
 798     } else if (op == '-') {
 799         o(0x29);
 800         o(0xc0 + r + fr * 8);
 801     } else if (op == '&') {
 802         o(0x21);
 803         o(0xc0 + r + fr * 8);
 804     } else if (op == '^') {
 805         o(0x31);
 806         o(0xc0 + r + fr * 8);
 807     } else if (op == '|') {
 808         o(0x09);
 809         o(0xc0 + r + fr * 8);
 810     } else if (op == '*') {
 811         o(0xaf0f); /* imul fr, r */
 812         o(0xc0 + fr + r * 8);
 813     } else if (op == TOK_SHL | op == TOK_SHR | op == TOK_SAR) {
 814         /* op2 is %ecx */
 815         if (fr != 1) {
 816             if (r == 1) {
 817                 r = fr;
 818                 fr = 1;
 819                 o(0x87); /* xchg r, %ecx */
 820                 o(0xc1 + r * 8);
 821             } else
 822                 move_reg(1, fr);
 823         }
 824         o(0xd3); /* shl/shr/sar %cl, r */
 825         if (op == TOK_SHL)
 826             o(0xe0 + r);
 827         else if (op == TOK_SHR)
 828             o(0xe8 + r);
 829         else
 830             o(0xf8 + r);
 831         vt = (vt & VT_TYPE) | r;
 832     } else if (op == '/' | op == TOK_UDIV | op == TOK_PDIV |
 833                op == '%' | op == TOK_UMOD) {
 834         save_reg(2); /* save edx */
 835         t = save_reg_forced(fr); /* save fr and get op2 location */
 836         move_reg(0, r); /* op1 is %eax */
 837         if (op == TOK_UDIV | op == TOK_UMOD) {
 838             o(0xf7d231); /* xor %edx, %edx, div t(%ebp), %eax */
 839             oad(0xb5, t);
 840         } else {
 841             o(0xf799); /* cltd, idiv t(%ebp), %eax */
 842             oad(0xbd, t);
 843         }
 844         if (op == '%' | op == TOK_UMOD)
 845             r = 2;
 846         else
 847             r = 0;
 848         vt = (vt & VT_TYPE) | r;
 849     } else {
 850         o(0x39);
 851         o(0xc0 + r + fr * 8); /* cmp fr, r */
 852         vset(VT_CMP, op);
 853     }
 854 }
 855
 856 /* end of X86 code generator */
 857 /*************************************************************/
 858
 859 int save_reg_forced(r)
 860 {
 861     int i, l, *p, t;
 862     /* store register */
 863     loc = (loc - 4) & -3;
 864     store(r, VT_LOCAL, loc);
 865     l = loc;
 866
 867     /* modify all stack values */
 868     for(p=vstack;p<vstack_ptr;p+=2) {
 869         i = p[0] & VT_VALMASK;
 870         if (i == r) {
 871             if (p[0] & VT_LVAL)
 872                 t = VT_LLOCAL;
 873             else
 874                 t = VT_LOCAL;
 875             p[0] = (p[0] & VT_TYPE) | VT_LVAL | t;
 876             p[1] = l;
 877         }
 878     }
 879     return l;
 880 }
 881
 882 /* save r to memory. and mark it as being free */
 883 void save_reg(r)
 884 {
 885     int i, *p;
 886
 887     /* modify all stack values */
 888     for(p=vstack;p<vstack_ptr;p+=2) {
 889         i = p[0] & VT_VALMASK;
 890         if (i == r) {
 891             save_reg_forced(r);
 892             break;
 893         }
 894     }
 895 }
 896
 897 /* find a free register. If none, save one register */
 898 int get_reg()
 899 {
 900     int r, i, *p;
 901
 902     /* find a free register */
 903     for(r=0;r<NB_REGS;r++) {
 904         for(p=vstack;p<vstack_ptr;p+=2) {
 905             i = p[0] & VT_VALMASK;
 906             if (i == r)
 907                 goto notfound;
 908         }
 909         return r;
 910     notfound: ;
 911     }
 912
 913     /* no register left : free the first one on the stack (very
 914        important to start from the bottom to ensure that we don't
 915        spill registers used in gen_op()) */
 916     for(p=vstack;p<vstack_ptr;p+=2) {
 917         r = p[0] & VT_VALMASK;
 918         if (r < VT_CONST) {
 919             save_reg(r);
 920             break;
 921         }
 922     }
 923     return r;
 924 }
 925
 926 void save_regs()
 927 {
 928     int r, *p;
 929     for(p=vstack;p<vstack_ptr;p+=2) {
 930         r = p[0] & VT_VALMASK;
 931         if (r < VT_CONST) {
 932             save_reg(r);
 933         }
 934     }
 935 }
 936
 937 /* move register 's' to 'r', and flush previous value of r to memory
 938    if needed */
 939 void move_reg(r, s)
 940 {
 941     if (r != s) {
 942         save_reg(r);
 943         load(r, s, 0);
 944     }
 945 }
 946
 947 /* convert a stack entry in register */
 948 int gvp(int *p)
 949 {
 950     int r;
 951     r = p[0] & VT_VALMASK;
 952     if (r >= VT_CONST || (p[0] & VT_LVAL))
 953         r = get_reg();
 954     load(r, p[0], p[1]);
 955     p[0] = (p[0] & VT_TYPE) | r;
 956     return r;
 957 }
 958
 959 void vpush()
 960 {
 961     *vstack_ptr++ = vt;
 962     *vstack_ptr++ = vc;
 963     /* cannot let cpu flags if other instruction are generated */
 964     if ((vt & VT_VALMASK) == VT_CMP)
 965         gvp(vstack_ptr - 2);
 966 }
 967
 968 void vpop(int *ft, int *fc)
 969 {
 970     *fc = *--vstack_ptr;
 971     *ft = *--vstack_ptr;
 972 }
 973
 974 /* generate a value in a register from vt and vc */
 975 int gv()
 976 {
 977     int r;
 978     vpush();
 979     r = gvp(vstack_ptr - 2);
 980     vpop(&vt, &vc);
 981     return r;
 982 }
 983
 984 /* handle constant optimizations and various machine independant opt */
 985 void gen_opc(op)
 986 {
 987     int fr, ft, fc, r, c1, c2, n;
 988
 989     vpop(&ft, &fc);
 990     vpop(&vt, &vc);
 991     c1 = (vt & (VT_VALMASK | VT_LVAL)) == VT_CONST;
 992     c2 = (ft & (VT_VALMASK | VT_LVAL)) == VT_CONST;
 993     if (c1 && c2) {
 994         switch(op) {
 995         case '+': vc += fc; break;
 996         case '-': vc -= fc; break;
 997         case '&': vc &= fc; break;
 998         case '^': vc ^= fc; break;
 999         case '|': vc |= fc; break;
1000         case '*': vc *= fc; break;
1001         case TOK_PDIV:
1002         case '/': vc /= fc; break; /* XXX: zero case ? */
1003         case '%': vc %= fc; break; /* XXX: zero case ? */
1004         case TOK_UDIV: vc = (unsigned)vc / fc; break; /* XXX: zero case ? */
1005         case TOK_UMOD: vc = (unsigned)vc % fc; break; /* XXX: zero case ? */
1006         case TOK_SHL: vc <<= fc; break;
1007         case TOK_SHR: vc = (unsigned)vc >> fc; break;
1008         case TOK_SAR: vc >>= fc; break;
1009         default:
1010             goto general_case;
1011         }
1012     } else {
1013         /* if commutative ops, put c2 as constant */
1014         if (c1 && (op == '+' || op == '&' || op == '^' ||
1015                    op == '|' || op == '*')) {
1016             swap(&vt, &ft);
1017             swap(&vc, &fc);
1018             swap(&c1, &c2);
1019         }
1020         if (c2 && (((op == '*' || op == '/' || op == TOK_UDIV ||
1021                      op == TOK_PDIV) &&
1022                     fc == 1) ||
1023                    ((op == '+' || op == '-' || op == '|' || op == '^' ||
1024                      op == TOK_SHL || op == TOK_SHR || op == TOK_SAR) &&
1025                     fc == 0) ||
1026                    (op == '&' &&
1027                     fc == -1))) {
1028         } else if (c2 && (op == '*' || op == TOK_PDIV || op == TOK_UDIV)) {
1029             /* try to use shifts instead of muls or divs */
1030             if (fc > 0 && (fc & (fc - 1)) == 0) {
1031                 n = -1;
1032                 while (fc) {
1033                     fc >>= 1;
1034                     n++;
1035                 }
1036                 fc = n;
1037                 if (op == '*')
1038                     op = TOK_SHL;
1039                 else if (op == TOK_PDIV)
1040                     op = TOK_SAR;
1041                 else
1042                     op = TOK_SHR;
1043             }
1044             goto general_case;
1045         } else {
1046         general_case:
1047             vpush();
1048             vt = ft;
1049             vc = fc;
1050             vpush();
1051             r = gvp(vstack_ptr - 4);
1052             fr = gvp(vstack_ptr - 2);
1053             vpop(&ft, &fc);
1054             vpop(&vt, &vc);
1055             /* call low level op generator */
1056             gen_op1(op, r, fr);
1057         }
1058     }
1059 }
1060
1061 int pointed_size(t)
1062 {
1063     return type_size(pointed_type(t), &t);
1064 }
1065
1066 /* generic gen_op: handles types problems */
1067 void gen_op(op)
1068 {
1069     int u, t1, t2;
1070
1071     vpush();
1072     t1 = vstack_ptr[-4];
1073     t2 = vstack_ptr[-2];
1074     if (op == '+' | op == '-') {
1075         if ((t1 & VT_PTR) && (t2 & VT_PTR)) {
1076             if (op != '-')
1077                 error("invalid type");
1078             /* XXX: check that types are compatible */
1079             u = pointed_size(t1);
1080             gen_opc(op);
1081             vpush();
1082             vstack_ptr[-2] &= ~VT_TYPE; /* set to integer */
1083             vset(VT_CONST, u);
1084             gen_op(TOK_PDIV);
1085         } else if ((t1 | t2) & VT_PTR) {
1086             if (t2 & VT_PTR) {
1087                 swap(vstack_ptr - 4, vstack_ptr - 2);
1088                 swap(vstack_ptr - 3, vstack_ptr - 1);
1089                 swap(&t1, &t2);
1090             }
1091             /* stack-4 contains pointer, stack-2 value to add */
1092             vset(VT_CONST, pointed_size(vstack_ptr[-4]));
1093             gen_op('*');
1094             vpush();
1095             gen_opc(op);
1096             /* put again type if gen_opc() swaped operands */
1097             vt = (vt & VT_TYPEN) | (t1 & VT_TYPE);
1098         } else {
1099             gen_opc(op);
1100         }
1101     } else {
1102         if ((t1 | t2) & VT_UNSIGNED) {
1103             if (op == TOK_SAR)
1104                 op = TOK_SHR;
1105             else if (op == '/')
1106                 op = TOK_UDIV;
1107             else if (op == '%')
1108                 op = TOK_UMOD;
1109         }
1110         gen_opc(op);
1111     }
1112 }
1113
1114 /* return type size. Put alignment at 'a' */
1115 int type_size(int t, int *a)
1116 {
1117     Sym *s;
1118
1119     /* int, enum or pointer */
1120     if (t & VT_STRUCT) {
1121         /* struct/union */
1122         s = sym_find(((unsigned)t >> VT_STRUCT_SHIFT) | SYM_STRUCT);
1123         *a = 4; /* XXX: cannot store it yet. Doing that is safe */
1124         return s->c;
1125     } else if (t & VT_ARRAY) {
1126         s = sym_find(((unsigned)t >> VT_STRUCT_SHIFT));
1127         return type_size(s->t, a) * s->c;
1128     } else if ((t & VT_PTR) |
1129                (t & VT_TYPE) == 0 |
1130                (t & VT_ENUM)) {
1131         *a = 4;
1132         return 4;
1133     } else {
1134         *a = 1;
1135         return 1;
1136     }
1137 }
1138
1139 /* return the pointed type of t */
1140 int pointed_type(int t)
1141 {
1142     Sym *s;
1143     s = sym_find(((unsigned)t >> VT_STRUCT_SHIFT));
1144     return s->t | (t & VT_TYPEN);
1145 }
1146
1147 int mk_pointer(int t)
1148 {
1149     int p;
1150     p = anon_sym++;
1151     sym_push(p, t, -1);
1152     return VT_PTR | (p << VT_STRUCT_SHIFT) | (t & VT_TYPEN);
1153 }
1154
1155 /* store value in lvalue pushed on stack */
1156 void vstore()
1157 {
1158     int ft, fc, r, t;
1159
1160     r = gv();  /* generate value */
1161     vpush();
1162     ft = vstack_ptr[-4];
1163     fc = vstack_ptr[-3];
1164     if ((ft & VT_VALMASK) == VT_LLOCAL) {
1165         t = get_reg();
1166         load(t, VT_LOCAL | VT_LVAL, fc);
1167         ft = (ft & ~VT_VALMASK) | t;
1168     }
1169     store(r, ft, fc);
1170     vstack_ptr -= 4;
1171 }
1172
1173 /* post defines POST/PRE add. c is the token ++ or -- */
1174 void inc(post, c)
1175 {
1176     int r, r1;
1177     test_lvalue();
1178     if (post)
1179         vpush(); /* room for returned value */
1180     vpush(); /* save lvalue */
1181     r = gv();
1182     vpush(); /* save value */
1183     if (post) {
1184         /* duplicate value */
1185         r1 = get_reg();
1186         load(r1, r, 0); /* move r to r1 */
1187         vstack_ptr[-6] = (vt & VT_TYPE) | r1;
1188         vstack_ptr[-5] = 0;
1189     }
1190     /* add constant */
1191     vset(VT_CONST, c - TOK_MID);
1192     gen_op('+');
1193     vstore(); /* store value */
1194     if (post)
1195         vpop(&vt, &vc);
1196 }
1197
1198 int expr_const()
1199 {
1200     expr_eq();
1201     if ((vt & (VT_CONST | VT_LVAL)) != VT_CONST)
1202         expect("constant");
1203     return vc;
1204 }
1205
1206 /* enum/struct/union declaration */
1207 int struct_decl(u)
1208 {
1209     int a, t, b, v, size, align, maxalign, c;
1210     Sym *slast, *s, *ss;
1211
1212     a = tok; /* save decl type */
1213     next();
1214     if (tok != '{') {
1215         v = tok;
1216         next();
1217         /* struct already defined ? return it */
1218         /* XXX: check consistency */
1219         if (s = sym_find(v | SYM_STRUCT)) {
1220             if (s->t != a)
1221                 error("invalid type");
1222             u = u | (v << VT_STRUCT_SHIFT);
1223             return u;
1224         }
1225     } else {
1226         v = anon_sym++;
1227     }
1228     s = sym_push(v | SYM_STRUCT, a, 0);
1229     /* put struct/union/enum name in type */
1230     u = u | (v << VT_STRUCT_SHIFT);
1231
1232     if (tok == '{') {
1233         next();
1234         /* cannot be empty */
1235         c = 0;
1236         maxalign = 0;
1237         slast = 0;
1238         while (1) {
1239             if (a == TOK_ENUM) {
1240                 v = tok;
1241                 next();
1242                 if (tok == '=') {
1243                     next();
1244                     c = expr_const();
1245                 }
1246                 sym_push(v, VT_CONST, c);
1247                 if (tok == ',')
1248                     next();
1249                 c++;
1250             } else {
1251                 b = ist();
1252                 while (1) {
1253                     t = typ(&v, b);
1254                     if (t & (VT_FUNC | VT_TYPEDEF))
1255                         error("invalid type");
1256                     /* XXX: align & correct type size */
1257                     v |= SYM_FIELD;
1258                     size = type_size(t, &align);
1259                     if (a == TOK_STRUCT) {
1260                         c = (c + align - 1) & -align;
1261                         ss = sym_push(v, t, c);
1262                         c += size;
1263                     } else {
1264                         ss = sym_push(v, t, 0);
1265                         if (size > c)
1266                             c = size;
1267                     }
1268                     if (align > maxalign)
1269                         maxalign = align;
1270                     ss->next = slast;
1271                     slast = ss;
1272                     if (tok == ';' || tok == -1)
1273                         break;
1274                     skip(',');
1275                 }
1276                 skip(';');
1277             }
1278             if (tok == '}')
1279                 break;
1280         }
1281         skip('}');
1282         s->next = slast;
1283         /* size for struct/union, dummy for enum */
1284         s->c = (c + maxalign - 1) & -maxalign;
1285     }
1286     return u;
1287 }
1288
1289 /* return 0 if no type declaration. otherwise, return the basic type
1290    and skip it.
1291    XXX: A '2' is ored to ensure non zero return if int type.
1292  */
1293 int ist()
1294 {
1295     int t, n, v;
1296     Sym *s;
1297
1298     t = 0;
1299     while(1) {
1300 #ifndef TINY
1301         if (tok == TOK_ENUM) {
1302             t |= struct_decl(VT_ENUM);
1303         } else if (tok == TOK_STRUCT || tok == TOK_UNION) {
1304             t |= struct_decl(VT_STRUCT);
1305         } else
1306 #endif
1307         {
1308             if (tok == TOK_CHAR) {
1309                 t |= VT_BYTE;
1310             } else if (tok == TOK_VOID) {
1311                 t |= VT_VOID;
1312             } else if (tok == TOK_INT |
1313                        (tok >= TOK_CONST & tok <= TOK_INLINE)) {
1314                 /* ignored types */
1315             } else if (tok == TOK_FLOAT & tok == TOK_DOUBLE) {
1316                 error("floats not supported");
1317             } else if (tok == TOK_EXTERN) {
1318                 t |= VT_EXTERN;
1319             } else if (tok == TOK_STATIC) {
1320                 t |= VT_STATIC;
1321             } else if (tok == TOK_UNSIGNED) {
1322                 t |= VT_UNSIGNED;
1323             } else if (tok == TOK_TYPEDEF) {
1324                 t |= VT_TYPEDEF;
1325             } else {
1326                 s = sym_find(tok);
1327                 if (!s || !(s->t & VT_TYPEDEF))
1328                     break;
1329                 t = s->t & ~VT_TYPEDEF;
1330             }
1331             next();
1332         }
1333         t |= 2;
1334     }
1335     return t;
1336 }
1337
1338 int post_type(u, t)
1339 {
1340     int p, n, pt, l;
1341
1342     if (tok == '(') {
1343         /* function declaration */
1344         next();
1345         /* push a dummy symbol to force local symbol stack usage */
1346         sym_push1(&local_stack, 0, 0, 0);
1347         p = 4;
1348         l = 0;
1349         while (tok != ')') {
1350             /* read param name and compute offset */
1351             if (l != 2) {
1352                 if (!(pt = ist())) {
1353                     if (l) {
1354                         error("invalid type");
1355                     } else {
1356                         l = 2;
1357                         goto old_proto;
1358                     }
1359                 }
1360                 if (pt & VT_VOID && tok == ')')
1361                     break;
1362                 l = 1;
1363                 pt = typ(&n, pt); /* XXX: should accept
1364                                      both arg/non arg if v == 0 */
1365             } else {
1366             old_proto:
1367                 n = tok;
1368                 pt = 0; /* int type */
1369                 next();
1370             }
1371             /* array must be transformed to pointer according to ANSI C */
1372             pt &= ~VT_ARRAY;
1373             p = p + 4;
1374             sym_push(n, VT_LOCAL | VT_LVAL | pt, p);
1375             if (tok == ',') {
1376                 next();
1377                 if (l == 1 && tok == TOK_DOTS) {
1378                     next();
1379                     break;
1380                 }
1381             }
1382         }
1383         skip(')');
1384         t = post_type(0, t); /* XXX: may be incorrect */
1385         /* transform function pointer to 'char *' */
1386         if (u)
1387             t = u + VT_BYTE;
1388         else
1389             t = t | VT_FUNC;
1390     } else if (tok == '[') {
1391         /* array definition */
1392         next();
1393         n = -1;
1394         if (tok != ']') {
1395             n = expr_const();
1396             if (n < 0)
1397                 error("invalid array size");
1398         }
1399         skip(']');
1400         /* parse next post type */
1401         t = post_type(u, t);
1402
1403         /* we push a anonymous symbol which will contain the array
1404            element type */
1405         p = anon_sym++;
1406         sym_push(p, t, n);
1407         t = VT_ARRAY | VT_PTR | (p << VT_STRUCT_SHIFT);
1408     }
1409     return t;
1410 }
1411
1412 /* Read a type declaration (except basic type), and return the
1413    type. If v is true, then also put variable name in 'vc' */
1414 int typ(int *v, int t)
1415 {
1416     int u;
1417
1418     t = t & -3; /* suppress the ored '2' */
1419     while (tok == '*') {
1420         next();
1421         t = mk_pointer(t);
1422     }
1423
1424     /* recursive type */
1425     /* XXX: incorrect if abstract type for functions (e.g. 'int ()') */
1426     if (tok == '(') {
1427         next();
1428         u = typ(v, 0);
1429         skip(')');
1430     } else {
1431         u = 0;
1432         /* type identifier */
1433         if (v) {
1434             *v = tok;
1435             next();
1436         }
1437     }
1438     return post_type(u, t);
1439 }
1440
1441 /* define a new external reference to a function 'v' of type 'u' */
1442 Sym *external_func(v, u)
1443 {
1444     int t, n;
1445     Sym *s;
1446     s = sym_find(v);
1447     if (!s) {
1448         n = dlsym(0, get_tok_str(v));
1449         if (n == 0) {
1450             /* used to generate symbol list */
1451             s = sym_push1(&global_stack,
1452                           v, u | VT_CONST | VT_LVAL | VT_FORWARD, 0);
1453         } else {
1454             /* int f() */
1455             s = sym_push1(&global_stack,
1456                           v, u | VT_CONST | VT_LVAL, n);
1457         }
1458     }
1459     return s;
1460 }
1461
1462 /* read a character for string or char constant and eval escape codes */
1463 int getq()
1464 {
1465     int c;
1466
1467     c = ch;
1468     minp();
1469     if (c == '\\') {
1470         if (isnum(ch)) {
1471             return getn(8);
1472         } else {
1473             if (ch == 'n')
1474                 c = '\n';
1475             else if (ch == 'r')
1476                 c = '\r';
1477             else if (ch == 't')
1478                 c = '\t';
1479             else
1480                 c = ch;
1481             minp();
1482         }
1483     }
1484     return c;
1485 }
1486
1487 void indir()
1488 {
1489     if (vt & VT_LVAL)
1490         gv();
1491     if (!(vt & VT_PTR))
1492         expect("pointer");
1493     vt = pointed_type(vt);
1494     if (!(vt & VT_ARRAY)) /* an array is never an lvalue */
1495         vt |= VT_LVAL;
1496 }
1497
1498 void unary()
1499 {
1500     int n, t, ft, fc, p, r;
1501     Sym *s;
1502
1503     if (tok == TOK_NUM) {
1504         vset(VT_CONST, tokc);
1505         next();
1506     } else
1507     if (tok == '\'') {
1508         vset(VT_CONST, getq());
1509         next(); /* skip char */
1510         skip('\'');
1511     } else if (tok == '\"') {
1512         /* generate (char *) type */
1513         vset(VT_CONST | mk_pointer(VT_TYPE), glo);
1514         while (tok == '\"') {
1515             while (ch != '\"') {
1516                 if (ch == -1)
1517                     error("unterminated string");
1518                 *(char *)glo++ = getq();
1519             }
1520             minp();
1521             next();
1522         }
1523         *(char *)glo++ = 0;
1524     } else {
1525         t = tok;
1526         next();
1527         if (t == '(') {
1528             /* cast ? */
1529             if (t = ist()) {
1530                 ft = typ(0, t);
1531                 skip(')');
1532                 unary();
1533                 vt = (vt & VT_TYPEN) | ft;
1534             } else {
1535                 expr();
1536                 skip(')');
1537             }
1538         } else if (t == '*') {
1539             unary();
1540             indir();
1541         } else if (t == '&') {
1542             unary();
1543             test_lvalue();
1544             vt = mk_pointer(vt & VT_LVALN);
1545         } else
1546         if (t == '!') {
1547             unary();
1548             if ((vt & VT_VALMASK) == VT_CMP)
1549                 vc = vc ^ 1;
1550             else
1551                 vset(VT_JMP, gtst(1, 0));
1552         } else
1553         if (t == '~') {
1554             unary();
1555             vpush();
1556             vset(VT_CONST, -1);
1557             gen_op('^');
1558         } else
1559         if (t == '+') {
1560             unary();
1561         } else
1562         if (t == TOK_SIZEOF) {
1563             /* XXX: some code can be generated */
1564             if (tok == '(') {
1565                 next();
1566                 if (t = ist())
1567                     vt = typ(0, t);
1568                 else
1569                     expr();
1570                 skip(')');
1571             } else {
1572                 unary();
1573             }
1574             vset(VT_CONST, type_size(vt, &t));
1575         } else
1576         if (t == TOK_INC | t == TOK_DEC) {
1577             unary();
1578             inc(0, t);
1579         } else if (t == '-') {
1580             vset(VT_CONST, 0);
1581             vpush();
1582             unary();
1583             gen_op('-');
1584         } else
1585         {
1586             s = sym_find(t);
1587             if (!s) {
1588                 if (tok != '(')
1589                     error("undefined symbol");
1590                 /* for simple function calls, we tolerate undeclared
1591                    external reference */
1592                 s = external_func(t, VT_FUNC); /* int() function */
1593             }
1594             vset(s->t, s->c);
1595             /* if forward reference, we must point to s->c */
1596             if (vt & VT_FORWARD)
1597                 vc = (int)&s->c;
1598         }
1599     }
1600
1601     /* post operations */
1602     while (1) {
1603         if (tok == TOK_INC | tok == TOK_DEC) {
1604             inc(1, tok);
1605             next();
1606         } else if (tok == '.' | tok == TOK_ARROW) {
1607             /* field */
1608             if (tok == TOK_ARROW)
1609                 indir();
1610             test_lvalue();
1611             vt &= VT_LVALN;
1612             next();
1613             /* expect pointer on structure */
1614             if (!(vt & VT_STRUCT))
1615                 expect("struct or union");
1616             s = sym_find(((unsigned)vt >> VT_STRUCT_SHIFT) | SYM_STRUCT);
1617             /* find field */
1618             tok |= SYM_FIELD;
1619             while (s = s->next) {
1620                 if (s->v == tok)
1621                     break;
1622             }
1623             if (!s)
1624                 error("field not found");
1625             /* add field offset to pointer */
1626             vt = vt & VT_TYPEN; /* change type to int */
1627             vpush();
1628             vset(VT_CONST, s->c);
1629             gen_op('+');
1630             /* change type to field type, and set to lvalue */
1631             vt = (vt & VT_TYPEN) | VT_LVAL | s->t;
1632             next();
1633         } else if (tok == '[') {
1634             next();
1635             vpush();
1636             expr();
1637             gen_op('+');
1638             indir();
1639             skip(']');
1640         } else if (tok == '(') {
1641             /* function call  */
1642             save_regs(); /* save used temporary registers */
1643             /* lvalue is implied */
1644             vt = vt & VT_LVALN;
1645             if ((vt & VT_VALMASK) != VT_CONST) {
1646                 /* evaluate function address */
1647                 r = gv();
1648                 o(0x50 + r); /* push r */
1649             }
1650             ft = vt;
1651             fc = vc;
1652             next();
1653             t = 0;
1654             while (tok != ')') {
1655                 t = t + 4;
1656                 expr_eq();
1657                 r = gv();
1658                 o(0x50 + r); /* push r */
1659                 if (tok == ',')
1660                     next();
1661             }
1662             skip(')');
1663             /* horrible, but needed : convert to native ordering (could
1664                parse parameters in reverse order, but would cost more
1665                code) */
1666             n = 0;
1667             p = t - 4;
1668             while (n < p) {
1669                 oad(0x24848b, p); /* mov x(%esp,1), %eax */
1670                 oad(0x248487, n); /* xchg   x(%esp,1), %eax */
1671                 oad(0x248489, p); /* mov %eax, x(%esp,1) */
1672                 n = n + 4;
1673                 p = p - 4;
1674             }
1675             if ((ft & VT_VALMASK) == VT_CONST) {
1676                 /* forward reference */
1677                 if (ft & VT_FORWARD) {
1678                     *(int *)fc = psym(0xe8, *(int *)fc);
1679                 } else
1680                     oad(0xe8, fc - ind - 5);
1681                 /* return value is %eax, and take type from function proto */
1682                 vt = 0 | (ft & VT_TYPE & VT_FUNCN);
1683             } else {
1684                 oad(0x2494ff, t); /* call *xxx(%esp) */
1685                 t = t + 4;
1686                 /* return value is %eax, integer */
1687                 vt = 0;
1688             }
1689             if (t)
1690                 oad(0xc481, t);
1691         } else {
1692             break;
1693         }
1694     }
1695 }
1696
1697 void uneq()
1698 {
1699     int t;
1700
1701     unary();
1702     if (tok == '=' |
1703         (tok >= TOK_A_MOD & tok <= TOK_A_DIV) |
1704         tok == TOK_A_XOR | tok == TOK_A_OR |
1705         tok == TOK_A_SHL | tok == TOK_A_SAR) {
1706         test_lvalue();
1707         vpush();
1708         t = tok;
1709         next();
1710         if (t == '=') {
1711             expr_eq();
1712             /* XXX: be more precise */
1713             if ((vt & VT_PTR) != (vstack_ptr[-2] & VT_PTR))
1714                 warning("incompatible type");
1715         } else {
1716             vpush();
1717             expr_eq();
1718             gen_op(t & 0x7f);
1719         }
1720         vstore();
1721     }
1722 }
1723
1724 void sum(l)
1725 {
1726     int ft, fc, t;
1727
1728     if (l == 0)
1729         uneq();
1730     else {
1731         sum(--l);
1732         while ((l == 0 & (tok == '*' | tok == '/' | tok == '%')) |
1733                (l == 1 & (tok == '+' | tok == '-')) |
1734                (l == 2 & (tok == TOK_SHL | tok == TOK_SAR)) |
1735                (l == 3 & (tok >= TOK_LT & tok <= TOK_GT)) |
1736                (l == 4 & (tok == TOK_EQ | tok == TOK_NE)) |
1737                (l == 5 & tok == '&') |
1738                (l == 6 & tok == '^') |
1739                (l == 7 & tok == '|')) {
1740             vpush();
1741             t = tok;
1742             next();
1743             sum(l);
1744             gen_op(t);
1745        }
1746     }
1747 }
1748
1749 #ifdef TINY
1750 void expr()
1751 {
1752     sum(8);
1753 }
1754 #else
1755 void eand()
1756 {
1757     int t;
1758
1759     sum(8);
1760     t = 0;
1761     while (1) {
1762         if (tok != TOK_LAND) {
1763             if (t) {
1764                 t = gtst(1, t);
1765                 vset(VT_JMPI, t);
1766             }
1767             break;
1768         }
1769         t = gtst(1, t);
1770         next();
1771         sum(8);
1772     }
1773 }
1774
1775 void eor()
1776 {
1777     int t, u;
1778
1779     eand();
1780     t = 0;
1781     while (1) {
1782         if (tok != TOK_LOR) {
1783             if (t) {
1784                 t = gtst(0, t);
1785                 vset(VT_JMP, t);
1786             }
1787             break;
1788         }
1789         t = gtst(0, t);
1790         next();
1791         eand();
1792     }
1793 }
1794
1795 void expr_eq()
1796 {
1797     int t, u;
1798
1799     eor();
1800     if (tok == '?') {
1801         next();
1802         t = gtst(1, 0);
1803         expr();
1804         gv();
1805         skip(':');
1806         u = gjmp(0);
1807         gsym(t);
1808         expr_eq();
1809         gv();
1810         gsym(u);
1811     }
1812 }
1813
1814 void expr()
1815 {
1816     while (1) {
1817         expr_eq();
1818         if (tok != ',')
1819             break;
1820         next();
1821     }
1822 }
1823
1824 #endif
1825
1826 void block(int *bsym, int *csym, int *case_sym, int *def_sym, int case_reg)
1827 {
1828     int a, b, c, d;
1829     Sym *s;
1830
1831     if (tok == TOK_IF) {
1832         /* if test */
1833         next();
1834         skip('(');
1835         expr();
1836         skip(')');
1837         a = gtst(1, 0);
1838         block(bsym, csym, case_sym, def_sym, case_reg);
1839         c = tok;
1840         if (c == TOK_ELSE) {
1841             next();
1842             d = gjmp(0);
1843             gsym(a);
1844             block(bsym, csym, case_sym, def_sym, case_reg);
1845             gsym(d); /* patch else jmp */
1846         } else
1847             gsym(a);
1848     } else if (tok == TOK_WHILE) {
1849         next();
1850         d = ind;
1851         skip('(');
1852         expr();
1853         skip(')');
1854         a = gtst(1, 0);
1855         b = 0;
1856         block(&a, &b, case_sym, def_sym, case_reg);
1857         oad(0xe9, d - ind - 5); /* jmp */
1858         gsym(a);
1859         gsym_addr(b, d);
1860     } else if (tok == '{') {
1861         next();
1862         /* declarations */
1863         s = local_stack;
1864         decl(VT_LOCAL);
1865         while (tok != '}')
1866             block(bsym, csym, case_sym, def_sym, case_reg);
1867         /* pop locally defined symbols */
1868         sym_pop(&local_stack, s);
1869         next();
1870     } else if (tok == TOK_RETURN) {
1871         next();
1872         if (tok != ';') {
1873             expr();
1874             move_reg(0, gv());
1875         }
1876         skip(';');
1877         rsym = gjmp(rsym); /* jmp */
1878     } else if (tok == TOK_BREAK) {
1879         /* compute jump */
1880         if (!bsym)
1881             error("cannot break");
1882         *bsym = gjmp(*bsym);
1883         next();
1884         skip(';');
1885     } else if (tok == TOK_CONTINUE) {
1886         /* compute jump */
1887         if (!csym)
1888             error("cannot continue");
1889         *csym = gjmp(*csym);
1890         next();
1891         skip(';');
1892     } else
1893 #ifndef TINY
1894     if (tok == TOK_FOR) {
1895         int e;
1896         next();
1897         skip('(');
1898         if (tok != ';')
1899             expr();
1900         skip(';');
1901         d = ind;
1902         c = ind;
1903         a = 0;
1904         b = 0;
1905         if (tok != ';') {
1906             expr();
1907             a = gtst(1, 0);
1908         }
1909         skip(';');
1910         if (tok != ')') {
1911             e = gjmp(0);
1912             c = ind;
1913             expr();
1914             oad(0xe9, d - ind - 5); /* jmp */
1915             gsym(e);
1916         }
1917         skip(')');
1918         block(&a, &b, case_sym, def_sym, case_reg);
1919         oad(0xe9, c - ind - 5); /* jmp */
1920         gsym(a);
1921         gsym_addr(b, c);
1922     } else
1923     if (tok == TOK_DO) {
1924         next();
1925         a = 0;
1926         b = 0;
1927         d = ind;
1928         block(&a, &b, case_sym, def_sym, case_reg);
1929         skip(TOK_WHILE);
1930         skip('(');
1931         gsym(b);
1932         expr();
1933         c = gtst(0, 0);
1934         gsym_addr(c, d);
1935         skip(')');
1936         gsym(a);
1937     } else
1938     if (tok == TOK_SWITCH) {
1939         next();
1940         skip('(');
1941         expr();
1942         case_reg = gv();
1943         skip(')');
1944         a = 0;
1945         b = 0;
1946         c = 0;
1947         block(&a, csym, &b, &c, case_reg);
1948         /* if no default, jmp after switch */
1949         if (c == 0)
1950             c = ind;
1951         /* default label */
1952         gsym_addr(b, c);
1953         /* break label */
1954         gsym(a);
1955     } else
1956     if (tok == TOK_CASE) {
1957         next();
1958         a = expr_const();
1959         if (!case_sym)
1960             expect("switch");
1961         gsym(*case_sym);
1962         vset(case_reg, 0);
1963         vpush();
1964         vset(VT_CONST, a);
1965         gen_op(TOK_EQ);
1966         *case_sym = gtst(1, 0);
1967         skip(':');
1968         block(bsym, csym, case_sym, def_sym, case_reg);
1969     } else
1970     if (tok == TOK_DEFAULT) {
1971         next();
1972         skip(':');
1973         if (!def_sym)
1974             expect("switch");
1975         if (*def_sym)
1976             error("too many 'default'");
1977         *def_sym = ind;
1978         block(bsym, csym, case_sym, def_sym, case_reg);
1979     } else
1980     if (tok == TOK_GOTO) {
1981         next();
1982         s = sym_find1(label_stack, tok);
1983         /* put forward definition if needed */
1984         if (!s)
1985             s = sym_push1(&label_stack, tok, VT_FORWARD, 0);
1986         /* label already defined */
1987         if (s->t & VT_FORWARD)
1988             s->c = gjmp(s->c); /* jmp xxx */
1989         else
1990             oad(0xe9, s->c - ind - 5); /* jmp xxx */
1991         next();
1992         skip(';');
1993     } else
1994 #endif
1995     {
1996         b = tok;
1997         next();
1998         if (tok == ':') {
1999             next();
2000             /* label case */
2001             s = sym_find1(label_stack, b);
2002             if (s) {
2003                 if (!(s->t & VT_FORWARD))
2004                     error("multiple defined label");
2005                 gsym(s->c);
2006                 s->c = ind;
2007                 s->t = 0;
2008             } else {
2009                 sym_push1(&label_stack, b, 0, ind);
2010             }
2011             block(bsym, csym, case_sym, def_sym, case_reg);
2012         } else {
2013             /* expression case: go backward of one token */
2014             /* XXX: currently incorrect if number/string/char */
2015             tok1 = tok;
2016             tok = b;
2017             if (tok != ';') {
2018                 expr();
2019             }
2020             skip(';');
2021         }
2022     }
2023 }
2024
2025 /* 'l' is VT_LOCAL or VT_CONST to define default storage type */
2026 void decl(l)
2027 {
2028     int *a, t, b, size, align, v, u, n;
2029     Sym *sym;
2030
2031     while (b = ist()) {
2032         if ((b & (VT_ENUM | VT_STRUCT)) && tok == ';') {
2033             /* we accept no variable after */
2034             next();
2035             continue;
2036         }
2037         while (1) { /* iterate thru each declaration */
2038             t = typ(&v, b);
2039             if (tok == '{') {
2040                 /* patch forward references */
2041                 if ((sym = sym_find(v)) && (sym->t & VT_FORWARD)) {
2042                     gsym(sym->c);
2043                     sym->c = ind;
2044                     sym->t = VT_CONST | VT_LVAL | t;
2045                 } else {
2046                     /* put function address */
2047                     sym_push1(&global_stack, v, VT_CONST | VT_LVAL | t, ind);
2048                 }
2049                 loc = 0;
2050                 o(0xe58955); /* push   %ebp, mov    %esp, %ebp */
2051                 a = (int *)oad(0xec81, 0); /* sub $xxx, %esp */
2052                 rsym = 0;
2053                 block(0, 0, 0, 0, 0);
2054                 gsym(rsym);
2055                 o(0xc3c9); /* leave, ret */
2056                 *a = (-loc + 3) & -4; /* align local size to word &
2057                                          save local variables */
2058                 sym_pop(&label_stack, 0); /* reset label stack */
2059                 sym_pop(&local_stack, 0); /* reset local stack */
2060                 break;
2061             } else {
2062                 if (b & VT_TYPEDEF) {
2063                     /* save typedefed type */
2064                     sym_push(v, t | VT_TYPEDEF, 0);
2065                 } else if (t & VT_FUNC) {
2066                     /* XXX: incorrect to flush, but needed while
2067                        waiting for function prototypes */
2068                     /* external function definition */
2069                     external_func(v, t);
2070                 } else {
2071                     /* not lvalue if array */
2072                     if (!(t & VT_ARRAY))
2073                         t |= VT_LVAL;
2074                     if (t & VT_EXTERN) {
2075                         /* external variable */
2076                         /* XXX: factorize with external function def */
2077                         n = dlsym(NULL, get_tok_str(v));
2078                         if (!n)
2079                             error("unknown external variable");
2080                         sym_push(v, VT_CONST | t, n);
2081                     } else {
2082                         u = l;
2083                         if (t & VT_STATIC)
2084                             u = VT_CONST;
2085                         u |= t;
2086                         size = type_size(t, &align);
2087                         if (size < 0)
2088                             error("invalid size");
2089                         if ((u & VT_VALMASK) == VT_LOCAL) {
2090                             /* allocate space down on the stack */
2091                             loc = (loc - size) & -align;
2092                             sym_push(v, u, loc);
2093                         } else {
2094                             /* allocate space up in the data space */
2095                             glo = (glo + align - 1) & -align;
2096                             sym_push(v, u, glo);
2097                             glo += size;
2098                         }
2099                     }
2100                 }
2101                 if (tok != ',') {
2102                     skip(';');
2103                     break;
2104                 }
2105                 next();
2106             }
2107         }
2108     }
2109 }
2110
2111 int main(int c, char **v)
2112 {
2113     Sym *s;
2114     int (*t)();
2115     if (c < 2) {
2116         printf("usage: tcc source ...\n");
2117         return 1;
2118     }
2119     v++;
2120     filename = *v;
2121     line_num = 1;
2122     file = fopen(filename, "r");
2123     if (!file) {
2124         perror(filename);
2125         exit(1);
2126     }
2127     include_stack_ptr = include_stack;
2128
2129     idtable = malloc(SYM_TABLE_SIZE);
2130     memcpy(idtable,
2131            "int\0void\0char\0if\0else\0while\0break\0return\0define\0main\0for\0extern\0static\0unsigned\0goto\0do\0continue\0switch\0case\0const\0volatile\0long\0register\0signed\0auto\0inline\0float\0double\0struct\0union\0typedef\0default\0enum\0sizeof\0include", 219);
2132     idptr = idtable + 219;
2133
2134     glo = malloc(DATA_SIZE);
2135     memset((void *)glo, 0, DATA_SIZE);
2136     prog = malloc(TEXT_SIZE);
2137     vstack = malloc(256);
2138     vstack_ptr = vstack;
2139     macro_stack_ptr = macro_stack;
2140     anon_sym = 1 << (31 - VT_STRUCT_SHIFT);
2141     ind = prog;
2142     inp();
2143     ch = '\n'; /* needed to parse correctly first preprocessor command */
2144     next();
2145     decl(VT_CONST);
2146 #ifdef TEST
2147     {
2148         FILE *f;
2149         f = fopen(v[1], "w");
2150         fwrite((void *)prog, 1, ind - prog, f);
2151         fclose(f);
2152         return 0;
2153     }
2154 #else
2155     s = sym_find(TOK_MAIN);
2156     if (!s)
2157         error("main() not defined");
2158     t = s->c;
2159     return (*t)(c - 1, v);
2160 #endif
2161 }