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