lib.c

   1 /*
   2  * 'sparse' library helper routines.
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003 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
  17 #include <sys/mman.h>
  18 #include <sys/types.h>
  19 #include <sys/stat.h>
  20
  21 #include "lib.h"
  22 #include "token.h"
  23 #include "parse.h"
  24 #include "symbol.h"
  25 #include "expression.h"
  26 #include "scope.h"
  27 #include "linearize.h"
  28 #include "target.h"
  29
  30 struct token *skip_to(struct token *token, int op)
  31 {
  32         while (!match_op(token, op) && !eof_token(token))
  33                 token = token->next;
  34         return token;
  35 }
  36
  37 struct token *expect(struct token *token, int op, const char *where)
  38 {
  39         if (!match_op(token, op)) {
  40                 static struct token bad_token;
  41                 if (token != &bad_token) {
  42                         bad_token.next = token;
  43                         warn(token->pos, "Expected %s %s", show_special(op), where);
  44                         warn(token->pos, "got %s", show_token(token));
  45                 }
  46                 if (op == ';')
  47                         return skip_to(token, op);
  48                 return &bad_token;
  49         }
  50         return token->next;
  51 }
  52
  53 unsigned int hexval(unsigned int c)
  54 {
  55         int retval = 256;
  56         switch (c) {
  57         case '0'...'9':
  58                 retval = c - '0';
  59                 break;
  60         case 'a'...'f':
  61                 retval = c - 'a' + 10;
  62                 break;
  63         case 'A'...'F':
  64                 retval = c - 'A' + 10;
  65                 break;
  66         }
  67         return retval;
  68 }
  69
  70 /*
  71  * Simple allocator for data that doesn't get partially free'd.
  72  * The tokenizer and parser allocate a _lot_ of small data structures
  73  * (often just two-three bytes for things like small integers),
  74  * and since they all depend on each other you can't free them
  75  * individually _anyway_. So do something that is very space-
  76  * efficient: allocate larger "blobs", and give out individual
  77  * small bits and pieces of it with no maintenance overhead.
  78  */
  79 struct allocation_blob {
  80         struct allocation_blob *next;
  81         unsigned int left, offset;
  82         unsigned char data[];
  83 };
  84
  85 #define CHUNK 32768
  86 #define blob_alloc(size) mmap(NULL, ((size)+4095) & ~4095, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)
  87 #define blob_free(addr,size) munmap((addr), ((size)+4095) & ~4095)
  88
  89 struct allocator_struct {
  90         const char *name;
  91         struct allocation_blob *blobs;
  92         unsigned int alignment;
  93         unsigned int chunking;
  94         /* statistics */
  95         unsigned int allocations, total_bytes, useful_bytes;
  96 };
  97
  98 void drop_all_allocations(struct allocator_struct *desc)
  99 {
 100         struct allocation_blob *blob = desc->blobs;
 101
 102         desc->blobs = NULL;
 103         desc->allocations = 0;
 104         desc->total_bytes = 0;
 105         desc->useful_bytes = 0;
 106         while (blob) {
 107                 struct allocation_blob *next = blob->next;
 108                 blob_free(blob, desc->chunking);
 109                 blob = next;
 110         }
 111 }
 112
 113 void *allocate(struct allocator_struct *desc, unsigned int size)
 114 {
 115         unsigned long alignment = desc->alignment;
 116         struct allocation_blob *blob = desc->blobs;
 117         void *retval;
 118
 119         desc->allocations++;
 120         desc->useful_bytes += size;
 121         size = (size + alignment - 1) & ~(alignment-1);
 122         if (!blob || blob->left < size) {
 123                 unsigned int offset, chunking = desc->chunking;
 124                 struct allocation_blob *newblob = blob_alloc(chunking);
 125                 if (!newblob)
 126                         die("out of memory");
 127                 desc->total_bytes += chunking;
 128                 newblob->next = blob;
 129                 blob = newblob;
 130                 desc->blobs = newblob;
 131                 offset = offsetof(struct allocation_blob, data);
 132                 offset = (offset + alignment - 1) & ~(alignment-1);
 133                 blob->left = chunking - offset;
 134                 blob->offset = offset - offsetof(struct allocation_blob, data);
 135         }
 136         retval = blob->data + blob->offset;
 137         blob->offset += size;
 138         blob->left -= size;
 139         return retval;
 140 }
 141
 142 static void show_allocations(struct allocator_struct *x)
 143 {
 144         fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
 145                         "%6.2f%% usage, %6.2f average size)\n",
 146                 x->name, x->allocations, x->useful_bytes, x->total_bytes,
 147                 100 * (double) x->useful_bytes / x->total_bytes,
 148                 (double) x->useful_bytes / x->allocations);
 149 }
 150
 151 struct allocator_struct ident_allocator = { "identifiers", NULL, __alignof__(struct ident), CHUNK };
 152 struct allocator_struct token_allocator = { "tokens", NULL, __alignof__(struct token), CHUNK };
 153 struct allocator_struct symbol_allocator = { "symbols", NULL, __alignof__(struct symbol), CHUNK };
 154 struct allocator_struct expression_allocator = { "expressions", NULL, __alignof__(struct expression), CHUNK };
 155 struct allocator_struct statement_allocator = { "statements", NULL, __alignof__(struct statement), CHUNK };
 156 struct allocator_struct string_allocator = { "strings", NULL, __alignof__(struct statement), CHUNK };
 157 struct allocator_struct scope_allocator = { "scopes", NULL, __alignof__(struct scope), CHUNK };
 158 struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK };
 159 struct allocator_struct basic_block_allocator = { "basic_block", NULL, __alignof__(struct basic_block), CHUNK };
 160 struct allocator_struct entrypoint_allocator = { "entrypoint", NULL, __alignof__(struct entrypoint), CHUNK };
 161 struct allocator_struct instruction_allocator = { "instruction", NULL, __alignof__(struct instruction), CHUNK };
 162 struct allocator_struct multijmp_allocator = { "multijmp", NULL, __alignof__(struct multijmp), CHUNK };
 163 struct allocator_struct phi_allocator = { "phi", NULL, __alignof__(struct phi), CHUNK };
 164 struct allocator_struct pseudo_allocator = { "pseudo", NULL, __alignof__(struct pseudo), CHUNK };
 165
 166 #define __ALLOCATOR(type, size, x)                              \
 167         type *__alloc_##x(int extra)                            \
 168         {                                                       \
 169                 return allocate(&x##_allocator, size+extra);    \
 170         }                                                       \
 171         void show_##x##_alloc(void)                             \
 172         {                                                       \
 173                 show_allocations(&x##_allocator);               \
 174         }                                                       \
 175         void clear_##x##_alloc(void)                            \
 176         {                                                       \
 177                 drop_all_allocations(&x##_allocator);           \
 178         }
 179 #define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x)
 180
 181 ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol);
 182 ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string);
 183 ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes);
 184 ALLOCATOR(basic_block); ALLOCATOR(entrypoint);
 185 ALLOCATOR(instruction);
 186 ALLOCATOR(multijmp);
 187 ALLOCATOR(phi);
 188 ALLOCATOR(pseudo);
 189
 190 int ptr_list_size(struct ptr_list *head)
 191 {
 192         int nr = 0;
 193
 194         if (head) {
 195                 struct ptr_list *list = head;
 196                 do {
 197                         nr += list->nr;
 198                 } while ((list = list->next) != head);
 199         }
 200         return nr;
 201 }
 202
 203 void iterate(struct ptr_list *head, void (*callback)(void *, void *, int), void *data)
 204 {
 205         struct ptr_list *list = head;
 206         int flag = ITERATE_FIRST;
 207
 208         if (!head)
 209                 return;
 210         do {
 211                 int i;
 212                 for (i = 0; i < list->nr; i++) {
 213                         if (i == list->nr-1 && list->next == head)
 214                                 flag |= ITERATE_LAST;
 215                         callback(list->list[i], data, flag);
 216                         flag = 0;
 217                 }
 218                 list = list->next;
 219         } while (list != head);
 220 }
 221
 222 void add_ptr_list(struct ptr_list **listp, void *ptr)
 223 {
 224         struct ptr_list *list = *listp;
 225         struct ptr_list *last = NULL; /* gcc complains needlessly */
 226         int nr;
 227
 228         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 229                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 230                 if (!newlist)
 231                         die("out of memory for symbol/statement lists");
 232                 memset(newlist, 0, sizeof(*newlist));
 233                 if (!list) {
 234                         newlist->next = newlist;
 235                         newlist->prev = newlist;
 236                         *listp = newlist;
 237                 } else {
 238                         newlist->prev = last;
 239                         newlist->next = list;
 240                         list->prev = newlist;
 241                         last->next = newlist;
 242                 }
 243                 last = newlist;
 244                 nr = 0;
 245         }
 246         last->list[nr] = ptr;
 247         nr++;
 248         last->nr = nr;
 249 }
 250
 251 void init_iterator(struct ptr_list **head, struct list_iterator *iterator, int flags)
 252 {
 253         iterator->head = head;
 254         iterator->index = 0;
 255         iterator->active = NULL;
 256         iterator->flags = flags;
 257 }
 258
 259 void * next_iterator(struct list_iterator *iterator)
 260 {
 261         struct ptr_list *list = iterator->active;
 262         int index;
 263
 264         if (!list) {
 265                 if (*iterator->head==NULL)
 266                         return NULL;
 267
 268                 list = *iterator->head;
 269                 iterator->index = 0;
 270                 if (!(iterator->flags & ITERATOR_BACKWARDS)) {
 271                         iterator->active = list;
 272                         return list->list[0];
 273                 }
 274         }
 275
 276         if (iterator->flags & ITERATOR_BACKWARDS) {
 277                 index = iterator->index -1;
 278                 if (index < 0) {
 279                         if (list->prev == *iterator->head)
 280                                 return NULL;
 281                         list = iterator->active = list->prev;
 282                         index = list->nr -1;
 283                 }
 284         } else {
 285                 index = iterator->index + 1;
 286                 if (index >= list->nr) {
 287                         if (list->next == *iterator->head)
 288                                 return NULL;
 289                         list = iterator->active = list->next;
 290                         index = 0;
 291                 }
 292         }
 293         iterator->index = index;
 294         return list->list[index];
 295 }
 296
 297 void replace_iterator(struct list_iterator *iterator, void* ptr)
 298 {
 299         struct ptr_list *list = iterator->active;
 300         if (list)
 301                 list->list[iterator->index] = ptr;
 302 }
 303
 304 void delete_iterator(struct list_iterator *iterator)
 305 {
 306         struct ptr_list *list = iterator->active;
 307         int movsize = list->nr - iterator->index - 1;
 308         void ** curptr = list->list+iterator->index;
 309
 310         if (movsize>0)
 311                 memmove(curptr, curptr+1, movsize*sizeof curptr);
 312
 313         list->nr --;
 314         if (iterator->flags & ITERATOR_BACKWARDS) {
 315                 if (iterator->index + 1 >= list->nr) {
 316                         iterator->active = (list->next == *iterator->head) ? NULL : list->next;
 317                         iterator->index = 0;
 318                 }
 319         } else {
 320                 if (--iterator->index <0) {
 321                         iterator->active = (list->prev == *iterator->head) ? NULL : list->prev;
 322                         iterator->index = list->prev->nr;
 323                 }
 324         }
 325         if (list->nr <=0) {
 326                 list->prev->next = list->next;
 327                 list->next->prev = list->prev;
 328                 if (list == *iterator->head)
 329                         *iterator->head = (list->next == *iterator->head) ? NULL : list->next;
 330                 free(list);
 331         }
 332 }
 333
 334 void init_terminator_iterator(struct instruction* terminator, struct terminator_iterator *iterator)
 335 {
 336         iterator->terminator = terminator;
 337         if (!terminator)
 338                 return;
 339
 340         switch (terminator->opcode) {
 341         case OP_BR:
 342                 iterator->branch = BR_INIT;
 343                 break;
 344         case OP_SWITCH:
 345                 init_multijmp_iterator(&terminator->multijmp_list, &iterator->multijmp, 0);
 346                 break;
 347         }
 348 }
 349
 350 struct basic_block* next_terminator_bb(struct terminator_iterator *iterator)
 351 {
 352         struct instruction *terminator = iterator->terminator;
 353
 354         if (!terminator)
 355                 return NULL;
 356         switch (terminator->opcode) {
 357         case OP_BR:
 358                 switch(iterator->branch) {
 359                 case BR_INIT:
 360                         if (terminator->bb_true) {
 361                                 iterator->branch = BR_TRUE;
 362                                 return terminator->bb_true;
 363                         }
 364                 case BR_TRUE:
 365                         if (terminator->bb_false) {
 366                                 iterator->branch = BR_FALSE;
 367                                 return terminator->bb_false;
 368                         }
 369                 default:
 370                         iterator->branch = BR_END;
 371                         return NULL;
 372                 }
 373                 break;
 374         case OP_SWITCH: {
 375                 struct multijmp *jmp = next_multijmp(&iterator->multijmp);
 376                 return jmp ? jmp->target : NULL;
 377         }
 378         }
 379         return NULL;
 380 }
 381
 382 void replace_terminator_bb(struct terminator_iterator *iterator, struct basic_block* bb)
 383 {
 384         struct instruction *terminator = iterator->terminator;
 385         if (!terminator)
 386                 return;
 387
 388         switch (terminator->opcode) {
 389         case OP_BR:
 390                 switch(iterator->branch) {
 391                 case BR_TRUE:
 392                         if (terminator->bb_true) {
 393                                 terminator->bb_true = bb;
 394                                 return;
 395                         }
 396                 case BR_FALSE:
 397                         if (terminator->bb_false) {
 398                                 terminator->bb_false = bb;
 399                                 return;
 400                         }
 401                 }
 402                 break;
 403
 404         case OP_SWITCH: {
 405                 struct multijmp *jmp = (struct multijmp*) current_iterator(&iterator->multijmp);
 406                 if (jmp)
 407                        jmp->target = bb;
 408         }
 409         }
 410 }
 411
 412
 413
 414 int replace_ptr_list(struct ptr_list **head, void *old_ptr, void *new_ptr)
 415 {
 416         int count = 0;
 417         struct list_iterator iterator;
 418         void *ptr;
 419
 420         init_iterator(head, &iterator, 0);
 421         while ((ptr=next_iterator(&iterator)) != NULL) {
 422                 if (ptr==old_ptr) {
 423                         if (new_ptr)
 424                                 replace_iterator(&iterator, new_ptr);
 425                         else
 426                                 delete_iterator(&iterator);
 427                         count ++;
 428                 }
 429         }
 430         return count;
 431 }
 432
 433 void * delete_ptr_list_last(struct ptr_list **head)
 434 {
 435         void *ptr = NULL;
 436         struct ptr_list *last, *first = *head;
 437
 438         if (!first)
 439                 return NULL;
 440         last = first->prev;
 441         if (last->nr)
 442                 ptr = last->list[--last->nr];
 443         if (last->nr <=0) {
 444                 first->prev = last->prev;
 445                 last->prev->next = first;
 446                 if (last == first)
 447                         *head = NULL;
 448                 free(last);
 449         }
 450         return ptr;
 451 }
 452
 453 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 454 {
 455         void *entry;
 456         FOR_EACH_PTR(a, entry) {
 457                 add_ptr_list(b, entry);
 458         } END_FOR_EACH_PTR;
 459 }
 460
 461 void free_ptr_list(struct ptr_list **listp)
 462 {
 463         struct ptr_list *tmp, *list = *listp;
 464
 465         if (!list)
 466                 return;
 467
 468         list->prev->next = NULL;
 469         while (list) {
 470                 tmp = list;
 471                 list = list->next;
 472                 free(tmp);
 473         }
 474
 475         *listp = NULL;
 476 }
 477
 478 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 479 {
 480         static char buffer[512];
 481         const char *name;
 482
 483         vsprintf(buffer, fmt, args);
 484         name = input_streams[pos.stream].name;
 485
 486         fprintf(stderr, "%s:%d:%d: %s%s\n",
 487                 name, pos.line, pos.pos, type, buffer);
 488 }
 489
 490 void info(struct position pos, const char * fmt, ...)
 491 {
 492         va_list args;
 493         va_start(args, fmt);
 494         do_warn("", pos, fmt, args);
 495         va_end(args);
 496 }
 497
 498 void warn(struct position pos, const char * fmt, ...)
 499 {
 500         static int warnings = 0;
 501         va_list args;
 502
 503         if (warnings > 100) {
 504                 static int once = 0;
 505                 if (once)
 506                         return;
 507                 fmt = "too many warnings";
 508                 once = 1;
 509         }
 510
 511         va_start(args, fmt);
 512         do_warn("warning: ", pos, fmt, args);
 513         va_end(args);
 514         warnings++;
 515 }
 516
 517 void error(struct position pos, const char * fmt, ...)
 518 {
 519         va_list args;
 520         va_start(args, fmt);
 521         do_warn("error: ", pos, fmt, args);
 522         va_end(args);
 523         exit(1);
 524 }
 525
 526 void die(const char *fmt, ...)
 527 {
 528         va_list args;
 529         static char buffer[512];
 530
 531         va_start(args, fmt);
 532         vsnprintf(buffer, sizeof(buffer), fmt, args);
 533         va_end(args);
 534
 535         fprintf(stderr, "%s\n", buffer);
 536         exit(1);
 537 }
 538
 539 unsigned int pre_buffer_size;
 540 unsigned char pre_buffer[8192];
 541
 542 int preprocess_only;
 543 char *include;
 544 int include_fd = -1;
 545
 546 void add_pre_buffer(const char *fmt, ...)
 547 {
 548         va_list args;
 549         unsigned int size;
 550
 551         va_start(args, fmt);
 552         size = pre_buffer_size;
 553         size += vsnprintf(pre_buffer + size,
 554                 sizeof(pre_buffer) - size,
 555                 fmt, args);
 556         pre_buffer_size = size;
 557         va_end(args);
 558 }
 559
 560 char **handle_switch_D(char *arg, char **next)
 561 {
 562         const char *name = arg + 1;
 563         const char *value = "";
 564         for (;;) {
 565                 char c;
 566                 c = *++arg;
 567                 if (!c)
 568                         break;
 569                 if (isspace(c) || c == '=') {
 570                         *arg = '\0';
 571                         value = arg + 1;
 572                         break;
 573                 }
 574         }
 575         add_pre_buffer("#define %s %s\n", name, value);
 576         return next;
 577 }
 578
 579 char **handle_switch_E(char *arg, char **next)
 580 {
 581         preprocess_only = 1;
 582         return next;
 583 }
 584
 585 char **handle_switch_v(char *arg, char **next)
 586 {
 587         verbose = 1;
 588         return next;
 589 }
 590 char **handle_switch_I(char *arg, char **next)
 591 {
 592         add_pre_buffer("#add_include \"%s/\"\n", arg + 1);
 593         return next;
 594 }
 595
 596 char **handle_switch_i(char *arg, char **next)
 597 {
 598         if (*next && !strcmp(arg, "include")) {
 599                 char *name = *++next;
 600                 int fd = open(name, O_RDONLY);
 601
 602                 include_fd = fd;
 603                 include = name;
 604                 if (fd < 0)
 605                         perror(name);
 606         }
 607         return next;
 608 }
 609
 610 char **handle_switch_m(char *arg, char **next)
 611 {
 612         if (!strcmp(arg, "m64")) {
 613                 bits_in_long = 64;
 614                 max_int_alignment = 8;
 615                 bits_in_pointer = 64;
 616                 pointer_alignment = 8;
 617         }
 618         return next;
 619 }
 620
 621 char **handle_switch(char *arg, char **next)
 622 {
 623         char **rc = next;
 624
 625         switch (*arg) {
 626         case 'D': rc = handle_switch_D(arg, next); break;
 627         case 'E': rc = handle_switch_E(arg, next); break;
 628         case 'v': rc = handle_switch_v(arg, next); break;
 629         case 'I': rc = handle_switch_I(arg, next); break;
 630         case 'i': rc = handle_switch_i(arg, next); break;
 631         case 'm': rc = handle_switch_m(arg, next); break;
 632         default:
 633                 /*
 634                  * Ignore unknown command line options:
 635                  * they're probably gcc switches
 636                  */
 637                 break;
 638         }
 639         return rc;
 640 }
 641
 642 void create_builtin_stream(void)
 643 {
 644         add_pre_buffer("#define __linux__ 1\n");
 645         add_pre_buffer("#define __STDC__ 1\n");
 646         add_pre_buffer("#define linux linux\n");
 647         add_pre_buffer("#define __GNUC__ 2\n");
 648         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 649         add_pre_buffer("#define __func__ \"function\"\n");
 650         add_pre_buffer("#define __extension__\n");
 651         add_pre_buffer("#define __pragma__\n");
 652         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 653         add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 654         add_pre_buffer("#define __builtin_va_arg(arg,type)  ((type)0)\n");
 655         add_pre_buffer("#define __builtin_va_end(arg)\n");
 656 }