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, unsigned long tag)
 171 {
 172         struct ptr_list *list = *listp;
 173         struct ptr_list *last = NULL; /* gcc complains needlessly */
 174         void **ret;
 175         int nr;
 176
 177         /* The low two bits are reserved for tags */
 178         assert((3 & (unsigned long)ptr) == 0);
 179         assert((~3 & tag) == 0);
 180         ptr = (void *)(tag | (unsigned long)ptr);
 181
 182         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 183                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 184                 if (!newlist)
 185                         die("out of memory for symbol/statement lists");
 186                 memset(newlist, 0, sizeof(*newlist));
 187                 if (!list) {
 188                         newlist->next = newlist;
 189                         newlist->prev = newlist;
 190                         *listp = newlist;
 191                 } else {
 192                         newlist->prev = last;
 193                         newlist->next = list;
 194                         list->prev = newlist;
 195                         last->next = newlist;
 196                 }
 197                 last = newlist;
 198                 nr = 0;
 199         }
 200         ret = last->list + nr;
 201         *ret = ptr;
 202         nr++;
 203         last->nr = nr;
 204         return ret;
 205 }
 206
 207 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 208 {
 209         void *ptr;
 210
 211         FOR_EACH_PTR(*list, ptr) {
 212                 if (ptr == entry) {
 213                         DELETE_CURRENT_PTR(ptr);
 214                         if (!--count)
 215                                 goto out;
 216                 }
 217         } END_FOR_EACH_PTR(ptr);
 218         assert(count <= 0);
 219 out:
 220         pack_ptr_list(list);
 221         return count;
 222 }
 223
 224 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 225 {
 226         void *ptr;
 227
 228         FOR_EACH_PTR(*list, ptr) {
 229                 if (ptr==old_ptr) {
 230                         REPLACE_CURRENT_PTR(ptr, new_ptr);
 231                         if (!--count)
 232                                 goto out;
 233                 }
 234         }END_FOR_EACH_PTR(ptr);
 235         assert(count <= 0);
 236 out:
 237         return count;
 238 }
 239
 240 void * delete_ptr_list_last(struct ptr_list **head)
 241 {
 242         void *ptr = NULL;
 243         struct ptr_list *last, *first = *head;
 244
 245         if (!first)
 246                 return NULL;
 247         last = first->prev;
 248         if (last->nr)
 249                 ptr = last->list[--last->nr];
 250         if (last->nr <=0) {
 251                 first->prev = last->prev;
 252                 last->prev->next = first;
 253                 if (last == first)
 254                         *head = NULL;
 255                 free(last);
 256         }
 257         return ptr;
 258 }
 259
 260 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 261 {
 262         void *entry;
 263         FOR_EACH_PTR(a, entry) {
 264                 add_ptr_list(b, entry);
 265         } END_FOR_EACH_PTR(entry);
 266 }
 267
 268 void __free_ptr_list(struct ptr_list **listp)
 269 {
 270         struct ptr_list *tmp, *list = *listp;
 271
 272         if (!list)
 273                 return;
 274
 275         list->prev->next = NULL;
 276         while (list) {
 277                 tmp = list;
 278                 list = list->next;
 279                 free(tmp);
 280         }
 281
 282         *listp = NULL;
 283 }
 284
 285 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 286 {
 287         static char buffer[512];
 288         const char *name;
 289
 290         vsprintf(buffer, fmt, args);
 291         name = stream_name(pos.stream);
 292
 293         fprintf(stderr, "%s:%d:%d: %s%s\n",
 294                 name, pos.line, pos.pos, type, buffer);
 295 }
 296
 297 void info(struct position pos, const char * fmt, ...)
 298 {
 299         va_list args;
 300         va_start(args, fmt);
 301         do_warn("", pos, fmt, args);
 302         va_end(args);
 303 }
 304
 305 void warning(struct position pos, const char * fmt, ...)
 306 {
 307         static int warnings = 0;
 308         va_list args;
 309
 310         if (warnings > 100) {
 311                 static int once = 0;
 312                 if (once)
 313                         return;
 314                 fmt = "too many warnings";
 315                 once = 1;
 316         }
 317
 318         va_start(args, fmt);
 319         do_warn("warning: ", pos, fmt, args);
 320         va_end(args);
 321         warnings++;
 322 }
 323
 324 void error(struct position pos, const char * fmt, ...)
 325 {
 326         static int errors = 0;
 327         va_list args;
 328
 329         if (errors > 100) {
 330                 static int once = 0;
 331                 if (once)
 332                         return;
 333                 fmt = "too many errors";
 334                 once = 1;
 335         }
 336
 337         va_start(args, fmt);
 338         do_warn("error: ", pos, fmt, args);
 339         va_end(args);
 340         errors++;
 341 }
 342
 343 void error_die(struct position pos, const char * fmt, ...)
 344 {
 345         va_list args;
 346         va_start(args, fmt);
 347         do_warn("error: ", pos, fmt, args);
 348         va_end(args);
 349         exit(1);
 350 }
 351
 352 void die(const char *fmt, ...)
 353 {
 354         va_list args;
 355         static char buffer[512];
 356
 357         va_start(args, fmt);
 358         vsnprintf(buffer, sizeof(buffer), fmt, args);
 359         va_end(args);
 360
 361         fprintf(stderr, "%s\n", buffer);
 362         exit(1);
 363 }
 364
 365 unsigned int pre_buffer_size;
 366 unsigned char pre_buffer[8192];
 367
 368 int Wdefault_bitfield_sign = 0;
 369 int Wbitwise = 0;
 370 int Wtypesign = 0;
 371 int Wcontext = 0;
 372 int Wundefined_preprocessor = 0;
 373 int preprocess_only;
 374 char *include;
 375 int include_fd = -1;
 376
 377 void add_pre_buffer(const char *fmt, ...)
 378 {
 379         va_list args;
 380         unsigned int size;
 381
 382         va_start(args, fmt);
 383         size = pre_buffer_size;
 384         size += vsnprintf(pre_buffer + size,
 385                 sizeof(pre_buffer) - size,
 386                 fmt, args);
 387         pre_buffer_size = size;
 388         va_end(args);
 389 }
 390
 391 char **handle_switch_D(char *arg, char **next)
 392 {
 393         const char *name = arg + 1;
 394         const char *value = "1";
 395         for (;;) {
 396                 char c;
 397                 c = *++arg;
 398                 if (!c)
 399                         break;
 400                 if (isspace((unsigned char)c) || c == '=') {
 401                         *arg = '\0';
 402                         value = arg + 1;
 403                         break;
 404                 }
 405         }
 406         add_pre_buffer("#define %s %s\n", name, value);
 407         return next;
 408 }
 409
 410 char **handle_switch_E(char *arg, char **next)
 411 {
 412         preprocess_only = 1;
 413         return next;
 414 }
 415
 416 char **handle_switch_v(char *arg, char **next)
 417 {
 418         do {
 419                 verbose++;
 420         } while (*++arg == 'v');
 421         return next;
 422 }
 423
 424 char **handle_switch_I(char *arg, char **next)
 425 {
 426         char *path = arg+1;
 427
 428         switch (arg[1]) {
 429         case '-':
 430                 /* Explaining '-I-' with a google search:
 431                  *
 432                  *      "Specifying -I after -I- searches for #include directories.
 433                  *       If -I- is specified before, it searches for #include "file"
 434                  *       and not #include ."
 435                  *
 436                  * Which didn't explain it at all to me. Maybe somebody else can
 437                  * explain it properly. We ignore it for now.
 438                  */
 439                 return next;
 440
 441         case '\0':      /* Plain "-I" */
 442                 path = *++next;
 443                 if (!path)
 444                         die("missing argument for -I option");
 445                 /* Fallthrough */
 446         default:
 447                 add_pre_buffer("#add_include \"%s/\"\n", path);
 448         }
 449         return next;
 450 }
 451
 452 char **handle_switch_i(char *arg, char **next)
 453 {
 454         if (*next && !strcmp(arg, "include")) {
 455                 char *name = *++next;
 456                 int fd = open(name, O_RDONLY);
 457
 458                 include_fd = fd;
 459                 include = name;
 460                 if (fd < 0)
 461                         perror(name);
 462         }
 463         return next;
 464 }
 465
 466 char **handle_switch_M(char *arg, char **next)
 467 {
 468         if (!strcmp(arg, "MF") || !strcmp(arg,"MQ") || !strcmp(arg,"MT")) {
 469                 if (!*next)
 470                         die("missing argument for -%s option", arg);
 471                 return next + 1;
 472         }
 473         return next;
 474 }
 475
 476 char **handle_switch_m(char *arg, char **next)
 477 {
 478         if (!strcmp(arg, "m64")) {
 479                 bits_in_long = 64;
 480                 max_int_alignment = 8;
 481                 bits_in_pointer = 64;
 482                 pointer_alignment = 8;
 483         }
 484         return next;
 485 }
 486
 487 char **handle_switch_o(char *arg, char **next)
 488 {
 489         if (!strcmp (arg, "o") && *next)
 490                 return next + 1; // "-o foo"
 491         else
 492                 return next;     // "-ofoo" or (bogus) terminal "-o"
 493 }
 494
 495 const struct warning {
 496         const char *name;
 497         int *flag;
 498 } warnings[] = {
 499         { "default-bitfield-sign", &Wdefault_bitfield_sign },
 500         { "undef", &Wundefined_preprocessor },
 501         { "bitwise", &Wbitwise },
 502         { "typesign", &Wtypesign },
 503         { "context", &Wcontext },
 504 };
 505
 506
 507 char **handle_switch_W(char *arg, char **next)
 508 {
 509         int no = 0;
 510         char *p = arg + 1;
 511         unsigned i;
 512
 513         // Prefixes "no" and "no-" mean to turn warning off.
 514         if (p[0] == 'n' && p[1] == 'o') {
 515                 p += 2;
 516                 if (p[0] == '-')
 517                         p++;
 518                 no = 1;
 519         }
 520
 521         for (i = 0; i < sizeof(warnings) / sizeof(warnings[0]); i++) {
 522                 if (!strcmp(p,warnings[i].name)) {
 523                         *warnings[i].flag = !no;
 524                         return next;
 525                 }
 526         }
 527
 528         // Unknown.
 529         return next;
 530 }
 531
 532 char **handle_switch_U(char *arg, char **next)
 533 {
 534         const char *name = arg + 1;
 535         add_pre_buffer ("#undef %s\n", name);
 536         return next;
 537 }
 538
 539 char **handle_switch_O(char *arg, char **next)
 540 {
 541         int level = 1;
 542         if (arg[1] >= '0' && arg[1] <= '9')
 543                 level = arg[1] - '0';
 544         optimize = level;
 545         return next;
 546 }
 547
 548 char **handle_nostdinc(char *arg, char **next)
 549 {
 550         add_pre_buffer("#nostdinc\n");
 551         return next;
 552 }
 553
 554 struct switches {
 555         const char *name;
 556         char **(*fn)(char *, char**);
 557 };
 558
 559 char **handle_switch(char *arg, char **next)
 560 {
 561         char **rc = next;
 562         static struct switches cmd[] = {
 563                 { "nostdinc", handle_nostdinc },
 564                 { NULL, NULL }
 565         };
 566         struct switches *s;
 567
 568         switch (*arg) {
 569         case 'D': rc = handle_switch_D(arg, next); break;
 570         case 'E': rc = handle_switch_E(arg, next); break;
 571         case 'I': rc = handle_switch_I(arg, next); break;
 572         case 'i': rc = handle_switch_i(arg, next); break;
 573         case 'M': rc = handle_switch_M(arg, next); break;
 574         case 'm': rc = handle_switch_m(arg, next); break;
 575         case 'o': rc = handle_switch_o(arg, next); break;
 576         case 'U': rc = handle_switch_U(arg, next); break;
 577         case 'v': rc = handle_switch_v(arg, next); break;
 578         case 'W': rc = handle_switch_W(arg, next); break;
 579         case 'O': rc = handle_switch_O(arg, next); break;
 580         default:
 581                 break;
 582         }
 583
 584         s = cmd;
 585         while (s->name) {
 586                 if (!strcmp(s->name, arg))
 587                         return s->fn(arg, next);
 588                 s++;
 589         }
 590
 591         /*
 592          * Ignore unknown command line options:
 593          * they're probably gcc switches
 594          */
 595         return rc;
 596 }
 597
 598 void declare_builtin_functions(void)
 599 {
 600         add_pre_buffer("extern void *__builtin_memcpy(void *, const void *, __SIZE_TYPE__);\n");
 601         add_pre_buffer("extern void *__builtin_return_address(unsigned int);\n");
 602         add_pre_buffer("extern void *__builtin_frame_address(unsigned int);\n");
 603         add_pre_buffer("extern void *__builtin_memset(void *, int, __SIZE_TYPE__);\n");
 604         add_pre_buffer("extern void __builtin_trap(void);\n");
 605         add_pre_buffer("extern int __builtin_ffs(int);\n");
 606         add_pre_buffer("extern void *__builtin_alloca(__SIZE_TYPE__);\n");
 607 }
 608
 609 void create_builtin_stream(void)
 610 {
 611         add_pre_buffer("#define __GNUC__ 2\n");
 612         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 613         add_pre_buffer("#define __extension__\n");
 614         add_pre_buffer("#define __pragma__\n");
 615
 616         // gcc defines __SIZE_TYPE__ to be size_t.  For linux/i86 and
 617         // solaris/sparc that is really "unsigned int" and for linux/x86_64
 618         // it is "long unsigned int".  In either case we can probably
 619         // get away with this.  We need the #ifndef as cgcc will define
 620         // the right __SIZE_TYPE__.
 621         add_pre_buffer("#weak_define __SIZE_TYPE__ long unsigned int\n");
 622         add_pre_buffer("#weak_define __STDC__ 1\n");
 623
 624         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 625         add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 626         add_pre_buffer("#define __builtin_va_arg(arg,type)  ({ type __va_arg_ret = *(type *)(arg); arg += sizeof(type); __va_arg_ret; })\n");
 627         add_pre_buffer("#define __builtin_va_alist (*(void *)0)\n");
 628         add_pre_buffer("#define __builtin_va_arg_incr(x) ((x) + 1)\n");
 629         add_pre_buffer("#define __builtin_va_end(arg)\n");
 630 }
 631
 632 static void do_predefined(char *filename)
 633 {
 634         add_pre_buffer("#define __BASE_FILE__ \"%s\"\n", filename);
 635         add_pre_buffer("#define __DATE__ \"??? ?? ????\"\n");
 636         add_pre_buffer("#define __TIME__ \"??:??:??\"\n");
 637 }
 638
 639 struct symbol_list *sparse(int argc, char **argv)
 640 {
 641         int fd;
 642         char *filename = NULL, **args;
 643         struct token *token;
 644
 645         // Initialize symbol stream first, so that we can add defines etc
 646         init_symbols();
 647
 648         args = argv;
 649         for (;;) {
 650                 char *arg = *++args;
 651                 if (!arg)
 652                         break;
 653                 if (arg[0] == '-' && arg[1]) {
 654                         args = handle_switch(arg+1, args);
 655                         continue;
 656                 }
 657                 filename = arg;
 658         }
 659
 660         if (!filename)
 661                 die("no input files given");
 662
 663         // Initialize type system
 664         init_ctype();
 665
 666         create_builtin_stream();
 667         add_pre_buffer("#define __CHECKER__ 1\n");
 668         if (!preprocess_only)
 669                 declare_builtin_functions();
 670
 671         do_predefined(filename);
 672
 673         if (strcmp (filename, "-") == 0) {
 674                 fd = 0;
 675         } else {
 676                 fd = open(filename, O_RDONLY);
 677                 if (fd < 0)
 678                         die("No such file: %s", filename);
 679         }
 680
 681         // Tokenize the input stream
 682         token = tokenize(filename, fd, NULL, includepath);
 683         close(fd);
 684
 685         // Prepend any "include" file to the stream.
 686         if (include_fd >= 0)
 687                 token = tokenize(include, include_fd, token, includepath);
 688
 689         // Prepend the initial built-in stream
 690         token = tokenize_buffer(pre_buffer, pre_buffer_size, token);
 691
 692         // Pre-process the stream
 693         token = preprocess(token);
 694
 695         if (preprocess_only) {
 696                 while (!eof_token(token)) {
 697                         int prec = 1;
 698                         struct token *next = token->next;
 699                         const char *separator = "";
 700                         if (next->pos.whitespace)
 701                                 separator = " ";
 702                         if (next->pos.newline) {
 703                                 separator = "\n\t\t\t\t\t";
 704                                 prec = next->pos.pos;
 705                                 if (prec > 4)
 706                                         prec = 4;
 707                         }
 708                         printf("%s%.*s", show_token(token), prec, separator);
 709                         token = next;
 710                 }
 711                 putchar('\n');
 712
 713                 return NULL;
 714         }
 715
 716         // Parse the resulting C code
 717         return translation_unit(token);
 718 }