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