lib.c

   1 /*
   2  * 'sparse' library helper routines.
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003-2004 Linus Torvalds
   6  *
   7  *  Licensed under the Open Software License version 1.1
   8  */
   9 #include <ctype.h>
  10 #include <fcntl.h>
  11 #include <stdarg.h>
  12 #include <stddef.h>
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <unistd.h>
  17 #include <assert.h>
  18
  19 #include <sys/types.h>
  20 #include <sys/stat.h>
  21
  22 #include "lib.h"
  23 #include "allocate.h"
  24 #include "token.h"
  25 #include "parse.h"
  26 #include "symbol.h"
  27 #include "expression.h"
  28 #include "scope.h"
  29 #include "linearize.h"
  30 #include "target.h"
  31
  32 int verbose, optimize, preprocessing;
  33
  34 struct token *skip_to(struct token *token, int op)
  35 {
  36         while (!match_op(token, op) && !eof_token(token))
  37                 token = token->next;
  38         return token;
  39 }
  40
  41 struct token *expect(struct token *token, int op, const char *where)
  42 {
  43         if (!match_op(token, op)) {
  44                 static struct token bad_token;
  45                 if (token != &bad_token) {
  46                         bad_token.next = token;
  47                         warning(token->pos, "Expected %s %s", show_special(op), where);
  48                         warning(token->pos, "got %s", show_token(token));
  49                 }
  50                 if (op == ';')
  51                         return skip_to(token, op);
  52                 return &bad_token;
  53         }
  54         return token->next;
  55 }
  56
  57 unsigned int hexval(unsigned int c)
  58 {
  59         int retval = 256;
  60         switch (c) {
  61         case '0'...'9':
  62                 retval = c - '0';
  63                 break;
  64         case 'a'...'f':
  65                 retval = c - 'a' + 10;
  66                 break;
  67         case 'A'...'F':
  68                 retval = c - 'A' + 10;
  69                 break;
  70         }
  71         return retval;
  72 }
  73
  74 int ptr_list_size(struct ptr_list *head)
  75 {
  76         int nr = 0;
  77
  78         if (head) {
  79                 struct ptr_list *list = head;
  80                 do {
  81                         nr += list->nr;
  82                 } while ((list = list->next) != head);
  83         }
  84         return nr;
  85 }
  86
  87 /*
  88  * Linearize the entries of a list up to a total of 'max',
  89  * and return the nr of entries linearized.
  90  *
  91  * The array to linearize into (second argument) should really
  92  * be "void *x[]", but we want to let people fill in any kind
  93  * of pointer array, so let's just call it "void *".
  94  */
  95 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
  96 {
  97         int nr = 0;
  98         if (head && max > 0) {
  99                 struct ptr_list *list = head;
 100
 101                 do {
 102                         int i = list->nr;
 103                         if (i > max)
 104                                 i = max;
 105                         memcpy(arr, list->list, i*sizeof(void *));
 106                         arr += i;
 107                         nr += i;
 108                         max -= i;
 109                         if (!max)
 110                                 break;
 111                 } while ((list = list->next) != head);
 112         }
 113         return nr;
 114 }
 115
 116 /*
 117  * When we've walked the list and deleted entries,
 118  * we may need to re-pack it so that we don't have
 119  * any empty blocks left (empty blocks upset the
 120  * walking code
 121  */
 122 void pack_ptr_list(struct ptr_list **listp)
 123 {
 124         struct ptr_list *head = *listp;
 125
 126         if (head) {
 127                 struct ptr_list *entry = head;
 128                 do {
 129                         struct ptr_list *next;
 130 restart:
 131                         next = entry->next;
 132                         if (!entry->nr) {
 133                                 struct ptr_list *prev;
 134                                 if (next == entry) {
 135                                         *listp = NULL;
 136                                         return;
 137                                 }
 138                                 prev = entry->prev;
 139                                 prev->next = next;
 140                                 next->prev = prev;
 141                                 free(entry);
 142                                 if (entry == head) {
 143                                         *listp = next;
 144                                         head = next;
 145                                         entry = next;
 146                                         goto restart;
 147                                 }
 148                         }
 149                         entry = next;
 150                 } while (entry != head);
 151         }
 152 }
 153
 154 void split_ptr_list_head(struct ptr_list *head)
 155 {
 156         int old = head->nr, nr = old / 2;
 157         struct ptr_list *newlist = malloc(sizeof(*newlist));
 158         struct ptr_list *next = head->next;
 159
 160         old -= nr;
 161         head->nr = old;
 162         newlist->next = next;
 163         next->prev = newlist;
 164         newlist->prev = head;
 165         head->next = newlist;
 166         newlist->nr = nr;
 167         memcpy(newlist->list, head->list + old, nr * sizeof(void *));
 168         memset(head->list + old, 0xf0, nr * sizeof(void *));
 169 }
 170
 171 void **__add_ptr_list(struct ptr_list **listp, void *ptr)
 172 {
 173         struct ptr_list *list = *listp;
 174         struct ptr_list *last = NULL; /* gcc complains needlessly */
 175         void **ret;
 176         int nr;
 177
 178         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 179                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 180                 if (!newlist)
 181                         die("out of memory for symbol/statement lists");
 182                 memset(newlist, 0, sizeof(*newlist));
 183                 if (!list) {
 184                         newlist->next = newlist;
 185                         newlist->prev = newlist;
 186                         *listp = newlist;
 187                 } else {
 188                         newlist->prev = last;
 189                         newlist->next = list;
 190                         list->prev = newlist;
 191                         last->next = newlist;
 192                 }
 193                 last = newlist;
 194                 nr = 0;
 195         }
 196         ret = last->list + nr;
 197         *ret = ptr;
 198         nr++;
 199         last->nr = nr;
 200         return ret;
 201 }
 202
 203 void delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 204 {
 205         void *ptr;
 206
 207         FOR_EACH_PTR(*list, ptr) {
 208                 if (ptr == entry) {
 209                         DELETE_CURRENT_PTR(ptr);
 210                         if (!--count)
 211                                 goto out;
 212                 }
 213         } END_FOR_EACH_PTR(ptr);
 214         assert(count <= 0);
 215 out:
 216         pack_ptr_list(list);
 217 }
 218
 219 void replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 220 {
 221         void *ptr;
 222
 223         FOR_EACH_PTR(*list, ptr) {
 224                 if (ptr==old_ptr) {
 225                         REPLACE_CURRENT_PTR(ptr, new_ptr);
 226                         if (!--count)
 227                                 return;
 228                 }
 229         }END_FOR_EACH_PTR(ptr);
 230         assert(count <= 0);
 231 }
 232
 233 void * delete_ptr_list_last(struct ptr_list **head)
 234 {
 235         void *ptr = NULL;
 236         struct ptr_list *last, *first = *head;
 237
 238         if (!first)
 239                 return NULL;
 240         last = first->prev;
 241         if (last->nr)
 242                 ptr = last->list[--last->nr];
 243         if (last->nr <=0) {
 244                 first->prev = last->prev;
 245                 last->prev->next = first;
 246                 if (last == first)
 247                         *head = NULL;
 248                 free(last);
 249         }
 250         return ptr;
 251 }
 252
 253 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 254 {
 255         void *entry;
 256         FOR_EACH_PTR(a, entry) {
 257                 add_ptr_list(b, entry);
 258         } END_FOR_EACH_PTR(entry);
 259 }
 260
 261 void __free_ptr_list(struct ptr_list **listp)
 262 {
 263         struct ptr_list *tmp, *list = *listp;
 264
 265         if (!list)
 266                 return;
 267
 268         list->prev->next = NULL;
 269         while (list) {
 270                 tmp = list;
 271                 list = list->next;
 272                 free(tmp);
 273         }
 274
 275         *listp = NULL;
 276 }
 277
 278 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 279 {
 280         static char buffer[512];
 281         const char *name;
 282
 283         vsprintf(buffer, fmt, args);
 284         name = input_streams[pos.stream].name;
 285
 286         fprintf(stderr, "%s:%d:%d: %s%s\n",
 287                 name, pos.line, pos.pos, type, buffer);
 288 }
 289
 290 void info(struct position pos, const char * fmt, ...)
 291 {
 292         va_list args;
 293         va_start(args, fmt);
 294         do_warn("", pos, fmt, args);
 295         va_end(args);
 296 }
 297
 298 void warning(struct position pos, const char * fmt, ...)
 299 {
 300         static int warnings = 0;
 301         va_list args;
 302
 303         if (warnings > 100) {
 304                 static int once = 0;
 305                 if (once)
 306                         return;
 307                 fmt = "too many warnings";
 308                 once = 1;
 309         }
 310
 311         va_start(args, fmt);
 312         do_warn("warning: ", pos, fmt, args);
 313         va_end(args);
 314         warnings++;
 315 }
 316
 317 void error(struct position pos, const char * fmt, ...)
 318 {
 319         static int errors = 0;
 320         va_list args;
 321
 322         if (errors > 100) {
 323                 static int once = 0;
 324                 if (once)
 325                         return;
 326                 fmt = "too many errors";
 327                 once = 1;
 328         }
 329
 330         va_start(args, fmt);
 331         do_warn("error: ", pos, fmt, args);
 332         va_end(args);
 333         errors++;
 334 }
 335
 336 void error_die(struct position pos, const char * fmt, ...)
 337 {
 338         va_list args;
 339         va_start(args, fmt);
 340         do_warn("error: ", pos, fmt, args);
 341         va_end(args);
 342         exit(1);
 343 }
 344
 345 void die(const char *fmt, ...)
 346 {
 347         va_list args;
 348         static char buffer[512];
 349
 350         va_start(args, fmt);
 351         vsnprintf(buffer, sizeof(buffer), fmt, args);
 352         va_end(args);
 353
 354         fprintf(stderr, "%s\n", buffer);
 355         exit(1);
 356 }
 357
 358 unsigned int pre_buffer_size;
 359 unsigned char pre_buffer[8192];
 360
 361 int Wdefault_bitfield_sign = 0;
 362 int Wbitwise = 0;
 363 int Wtypesign = 0;
 364 int Wcontext = 0;
 365 int Wundefined_preprocessor = 0;
 366 int preprocess_only;
 367 char *include;
 368 int include_fd = -1;
 369
 370 void add_pre_buffer(const char *fmt, ...)
 371 {
 372         va_list args;
 373         unsigned int size;
 374
 375         va_start(args, fmt);
 376         size = pre_buffer_size;
 377         size += vsnprintf(pre_buffer + size,
 378                 sizeof(pre_buffer) - size,
 379                 fmt, args);
 380         pre_buffer_size = size;
 381         va_end(args);
 382 }
 383
 384 char **handle_switch_D(char *arg, char **next)
 385 {
 386         const char *name = arg + 1;
 387         const char *value = "1";
 388         for (;;) {
 389                 char c;
 390                 c = *++arg;
 391                 if (!c)
 392                         break;
 393                 if (isspace((unsigned char)c) || c == '=') {
 394                         *arg = '\0';
 395                         value = arg + 1;
 396                         break;
 397                 }
 398         }
 399         add_pre_buffer("#define %s %s\n", name, value);
 400         return next;
 401 }
 402
 403 char **handle_switch_E(char *arg, char **next)
 404 {
 405         preprocess_only = 1;
 406         return next;
 407 }
 408
 409 char **handle_switch_v(char *arg, char **next)
 410 {
 411         verbose++;
 412         return next;
 413 }
 414
 415 char **handle_switch_I(char *arg, char **next)
 416 {
 417         char *path = arg+1;
 418
 419         switch (arg[1]) {
 420         case '-':
 421                 /* Explaining '-I-' with a google search:
 422                  *
 423                  *      "Specifying -I after -I- searches for #include directories.
 424                  *       If -I- is specified before, it searches for #include "file"
 425                  *       and not #include ."
 426                  *
 427                  * Which didn't explain it at all to me. Maybe somebody else can
 428                  * explain it properly. We ignore it for now.
 429                  */
 430                 return next;
 431
 432         case '\0':      /* Plain "-I" */
 433                 path = *++next;
 434                 if (!path)
 435                         die("missing argument for -I option");
 436                 /* Fallthrough */
 437         default:
 438                 add_pre_buffer("#add_include \"%s/\"\n", path);
 439         }
 440         return next;
 441 }
 442
 443 char **handle_switch_i(char *arg, char **next)
 444 {
 445         if (*next && !strcmp(arg, "include")) {
 446                 char *name = *++next;
 447                 int fd = open(name, O_RDONLY);
 448
 449                 include_fd = fd;
 450                 include = name;
 451                 if (fd < 0)
 452                         perror(name);
 453         }
 454         return next;
 455 }
 456
 457 char **handle_switch_M(char *arg, char **next)
 458 {
 459         if (!strcmp(arg, "MF") || !strcmp(arg,"MQ") || !strcmp(arg,"MT")) {
 460                 if (!*next)
 461                         die("missing argument for -%s option", arg);
 462                 return next + 1;
 463         }
 464         return next;
 465 }
 466
 467 char **handle_switch_m(char *arg, char **next)
 468 {
 469         if (!strcmp(arg, "m64")) {
 470                 bits_in_long = 64;
 471                 max_int_alignment = 8;
 472                 bits_in_pointer = 64;
 473                 pointer_alignment = 8;
 474         }
 475         return next;
 476 }
 477
 478 char **handle_switch_o(char *arg, char **next)
 479 {
 480         if (!strcmp (arg, "o") && *next)
 481                 return next + 1; // "-o foo"
 482         else
 483                 return next;     // "-ofoo" or (bogus) terminal "-o"
 484 }
 485
 486 const struct warning {
 487         const char *name;
 488         int *flag;
 489 } warnings[] = {
 490         { "default-bitfield-sign", &Wdefault_bitfield_sign },
 491         { "undef", &Wundefined_preprocessor },
 492         { "bitwise", &Wbitwise },
 493         { "typesign", &Wtypesign },
 494         { "context", &Wcontext },
 495 };
 496
 497
 498 char **handle_switch_W(char *arg, char **next)
 499 {
 500         int no = 0;
 501         char *p = arg + 1;
 502         unsigned i;
 503
 504         // Prefixes "no" and "no-" mean to turn warning off.
 505         if (p[0] == 'n' && p[1] == 'o') {
 506                 p += 2;
 507                 if (p[0] == '-')
 508                         p++;
 509                 no = 1;
 510         }
 511
 512         for (i = 0; i < sizeof(warnings) / sizeof(warnings[0]); i++) {
 513                 if (!strcmp(p,warnings[i].name)) {
 514                         *warnings[i].flag = !no;
 515                         return next;
 516                 }
 517         }
 518
 519         // Unknown.
 520         return next;
 521 }
 522
 523 char **handle_switch_U(char *arg, char **next)
 524 {
 525         const char *name = arg + 1;
 526         add_pre_buffer ("#undef %s\n", name);
 527         return next;
 528 }
 529
 530 char **handle_switch_O(char *arg, char **next)
 531 {
 532         int level = 1;
 533         if (arg[1] >= '0' && arg[1] <= '9')
 534                 level = arg[1] - '0';
 535         optimize = level;
 536         return next;
 537 }
 538
 539 char **handle_nostdinc(char *arg, char **next)
 540 {
 541         add_pre_buffer("#nostdinc\n");
 542         return next;
 543 }
 544
 545 struct switches {
 546         const char *name;
 547         char **(*fn)(char *, char**);
 548 };
 549
 550 char **handle_switch(char *arg, char **next)
 551 {
 552         char **rc = next;
 553         static struct switches cmd[] = {
 554                 { "nostdinc", handle_nostdinc },
 555                 { NULL, NULL }
 556         };
 557         struct switches *s;
 558
 559         switch (*arg) {
 560         case 'D': rc = handle_switch_D(arg, next); break;
 561         case 'E': rc = handle_switch_E(arg, next); break;
 562         case 'I': rc = handle_switch_I(arg, next); break;
 563         case 'i': rc = handle_switch_i(arg, next); break;
 564         case 'M': rc = handle_switch_M(arg, next); break;
 565         case 'm': rc = handle_switch_m(arg, next); break;
 566         case 'o': rc = handle_switch_o(arg, next); break;
 567         case 'U': rc = handle_switch_U(arg, next); break;
 568         case 'v': rc = handle_switch_v(arg, next); break;
 569         case 'W': rc = handle_switch_W(arg, next); break;
 570         case 'O': rc = handle_switch_O(arg, next); break;
 571         default:
 572                 break;
 573         }
 574
 575         s = cmd;
 576         while (s->name) {
 577                 if (!strcmp(s->name, arg))
 578                         return s->fn(arg, next);
 579                 s++;
 580         }
 581
 582         /*
 583          * Ignore unknown command line options:
 584          * they're probably gcc switches
 585          */
 586         return rc;
 587 }
 588
 589 void declare_builtin_functions(void)
 590 {
 591         add_pre_buffer("extern void *__builtin_memcpy(void *, const void *, __SIZE_TYPE__);\n");
 592         add_pre_buffer("extern void *__builtin_return_address(unsigned int);\n");
 593         add_pre_buffer("extern void *__builtin_frame_address(unsigned int);\n");
 594         add_pre_buffer("extern void *__builtin_memset(void *, int, __SIZE_TYPE__);\n");
 595         add_pre_buffer("extern void __builtin_trap(void);\n");
 596         add_pre_buffer("extern int __builtin_ffs(int);\n");
 597         add_pre_buffer("extern void *__builtin_alloca(__SIZE_TYPE__);\n");
 598 }
 599
 600 void create_builtin_stream(void)
 601 {
 602         add_pre_buffer("#define __GNUC__ 2\n");
 603         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 604         add_pre_buffer("#define __extension__\n");
 605         add_pre_buffer("#define __pragma__\n");
 606
 607         // gcc defines __SIZE_TYPE__ to be size_t.  For linux/i86 and
 608         // solaris/sparc that is really "unsigned int" and for linux/x86_64
 609         // it is "long unsigned int".  In either case we can probably
 610         // get away with this.  We need the #ifndef as cgcc will define
 611         // the right __SIZE_TYPE__.
 612         add_pre_buffer("#weak_define __SIZE_TYPE__ long unsigned int\n");
 613         add_pre_buffer("#weak_define __STDC__ 1\n");
 614
 615         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 616         add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 617         add_pre_buffer("#define __builtin_va_arg(arg,type)  ({ type __va_arg_ret = *(type *)(arg); arg += sizeof(type); __va_arg_ret; })\n");
 618         add_pre_buffer("#define __builtin_va_alist (*(void *)0)\n");
 619         add_pre_buffer("#define __builtin_va_arg_incr(x) ((x) + 1)\n");
 620         add_pre_buffer("#define __builtin_va_end(arg)\n");
 621 }
 622
 623 static void do_predefined(char *filename)
 624 {
 625         add_pre_buffer("#define __BASE_FILE__ \"%s\"\n", filename);
 626         add_pre_buffer("#define __DATE__ \"??? ?? ????\"\n");
 627         add_pre_buffer("#define __TIME__ \"??:??:??\"\n");
 628 }
 629
 630 struct symbol_list *sparse(int argc, char **argv)
 631 {
 632         int fd;
 633         char *filename = NULL, **args;
 634         struct token *token;
 635
 636         // Initialize symbol stream first, so that we can add defines etc
 637         init_symbols();
 638
 639         args = argv;
 640         for (;;) {
 641                 char *arg = *++args;
 642                 if (!arg)
 643                         break;
 644                 if (arg[0] == '-' && arg[1]) {
 645                         args = handle_switch(arg+1, args);
 646                         continue;
 647                 }
 648                 filename = arg;
 649         }
 650
 651         if (!filename)
 652                 die("no input files given");
 653
 654         // Initialize type system
 655         init_ctype();
 656
 657         create_builtin_stream();
 658         add_pre_buffer("#define __CHECKER__ 1\n");
 659         if (!preprocess_only)
 660                 declare_builtin_functions();
 661
 662         do_predefined(filename);
 663
 664         if (strcmp (filename, "-") == 0) {
 665                 fd = 0;
 666         } else {
 667                 fd = open(filename, O_RDONLY);
 668                 if (fd < 0)
 669                         die("No such file: %s", filename);
 670         }
 671
 672         // Tokenize the input stream
 673         token = tokenize(filename, fd, NULL, includepath);
 674         close(fd);
 675
 676         // Prepend any "include" file to the stream.
 677         if (include_fd >= 0)
 678                 token = tokenize(include, include_fd, token, includepath);
 679
 680         // Prepend the initial built-in stream
 681         token = tokenize_buffer(pre_buffer, pre_buffer_size, token);
 682
 683         // Pre-process the stream
 684         token = preprocess(token);
 685
 686         if (preprocess_only) {
 687                 while (!eof_token(token)) {
 688                         int prec = 1;
 689                         struct token *next = token->next;
 690                         const char *separator = "";
 691                         if (next->pos.whitespace)
 692                                 separator = " ";
 693                         if (next->pos.newline) {
 694                                 separator = "\n\t\t\t\t\t";
 695                                 prec = next->pos.pos;
 696                                 if (prec > 4)
 697                                         prec = 4;
 698                         }
 699                         printf("%s%.*s", show_token(token), prec, separator);
 700                         token = next;
 701                 }
 702                 putchar('\n');
 703
 704                 return NULL;
 705         }
 706
 707         // Parse the resulting C code
 708         return translation_unit(token);
 709 }