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
  29 struct token *skip_to(struct token *token, int op)
  30 {
  31         while (!match_op(token, op) && !eof_token(token))
  32                 token = token->next;
  33         return token;
  34 }
  35
  36 struct token *expect(struct token *token, int op, const char *where)
  37 {
  38         if (!match_op(token, op)) {
  39                 static struct token bad_token;
  40                 if (token != &bad_token) {
  41                         bad_token.next = token;
  42                         warn(token->pos, "Expected %s %s", show_special(op), where);
  43                         warn(token->pos, "got %s", show_token(token));
  44                 }
  45                 if (op == ';')
  46                         return skip_to(token, op);
  47                 return &bad_token;
  48         }
  49         return token->next;
  50 }
  51
  52 unsigned int hexval(unsigned int c)
  53 {
  54         int retval = 256;
  55         switch (c) {
  56         case '0'...'9':
  57                 retval = c - '0';
  58                 break;
  59         case 'a'...'f':
  60                 retval = c - 'a' + 10;
  61                 break;
  62         case 'A'...'F':
  63                 retval = c - 'A' + 10;
  64                 break;
  65         }
  66         return retval;
  67 }
  68
  69 /*
  70  * Simple allocator for data that doesn't get partially free'd.
  71  * The tokenizer and parser allocate a _lot_ of small data structures
  72  * (often just two-three bytes for things like small integers),
  73  * and since they all depend on each other you can't free them
  74  * individually _anyway_. So do something that is very space-
  75  * efficient: allocate larger "blobs", and give out individual
  76  * small bits and pieces of it with no maintenance overhead.
  77  */
  78 struct allocation_blob {
  79         struct allocation_blob *next;
  80         unsigned int left, offset;
  81         unsigned char data[];
  82 };
  83
  84 #define CHUNK 32768
  85 #define blob_alloc(size) mmap(NULL, ((size)+4095) & ~4095, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)
  86 #define blob_free(addr,size) munmap((addr), ((size)+4095) & ~4095)
  87
  88 struct allocator_struct {
  89         const char *name;
  90         struct allocation_blob *blobs;
  91         unsigned int alignment;
  92         unsigned int chunking;
  93         /* statistics */
  94         unsigned int allocations, total_bytes, useful_bytes;
  95 };
  96
  97 void drop_all_allocations(struct allocator_struct *desc)
  98 {
  99         struct allocation_blob *blob = desc->blobs;
 100
 101         desc->blobs = NULL;
 102         desc->allocations = 0;
 103         desc->total_bytes = 0;
 104         desc->useful_bytes = 0;
 105         while (blob) {
 106                 struct allocation_blob *next = blob->next;
 107                 blob_free(blob, desc->chunking);
 108                 blob = next;
 109         }
 110 }
 111
 112 void *allocate(struct allocator_struct *desc, unsigned int size)
 113 {
 114         unsigned long alignment = desc->alignment;
 115         struct allocation_blob *blob = desc->blobs;
 116         void *retval;
 117
 118         desc->allocations++;
 119         desc->useful_bytes += size;
 120         size = (size + alignment - 1) & ~(alignment-1);
 121         if (!blob || blob->left < size) {
 122                 unsigned int offset, chunking = desc->chunking;
 123                 struct allocation_blob *newblob = blob_alloc(chunking);
 124                 if (!newblob)
 125                         die("out of memory");
 126                 desc->total_bytes += chunking;
 127                 newblob->next = blob;
 128                 blob = newblob;
 129                 desc->blobs = newblob;
 130                 offset = offsetof(struct allocation_blob, data);
 131                 if (alignment > offset)
 132                         offset = alignment;
 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;
 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))) {
 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;
 437
 438         if (!*head)
 439                 return NULL;
 440         last = (*head)->prev;
 441         if (last->nr)
 442                 ptr = last->list[--last->nr];
 443         if (last->nr <=0) {
 444                 if (last == *head)
 445                         *head = NULL;
 446                 free(last);
 447         }
 448         return ptr;
 449 }
 450
 451 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 452 {
 453         void *entry;
 454         FOR_EACH_PTR(a, entry) {
 455                 add_ptr_list(b, entry);
 456         } END_FOR_EACH_PTR;
 457 }
 458
 459 void free_ptr_list(struct ptr_list **listp)
 460 {
 461         struct ptr_list *tmp, *list = *listp;
 462
 463         if (!list)
 464                 return;
 465
 466         list->prev->next = NULL;
 467         while (list) {
 468                 tmp = list;
 469                 list = list->next;
 470                 free(tmp);
 471         }
 472
 473         *listp = NULL;
 474 }
 475
 476 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 477 {
 478         static char buffer[512];
 479         const char *name;
 480
 481         vsprintf(buffer, fmt, args);
 482         name = input_streams[pos.stream].name;
 483
 484         fprintf(stderr, "%s: %s:%d:%d: %s\n",
 485                 type, name, pos.line, pos.pos, buffer);
 486 }
 487
 488 void warn(struct position pos, const char * fmt, ...)
 489 {
 490         static int warnings = 0;
 491         va_list args;
 492
 493         if (warnings > 100) {
 494                 static int once = 0;
 495                 if (once)
 496                         return;
 497                 fmt = "too many warnings";
 498                 once = 1;
 499         }
 500
 501         va_start(args, fmt);
 502         do_warn("warning", pos, fmt, args);
 503         va_end(args);
 504         warnings++;
 505 }
 506
 507 void error(struct position pos, const char * fmt, ...)
 508 {
 509         va_list args;
 510         va_start(args, fmt);
 511         do_warn("error", pos, fmt, args);
 512         va_end(args);
 513         exit(1);
 514 }
 515
 516 void die(const char *fmt, ...)
 517 {
 518         va_list args;
 519         static char buffer[512];
 520
 521         va_start(args, fmt);
 522         vsnprintf(buffer, sizeof(buffer), fmt, args);
 523         va_end(args);
 524
 525         fprintf(stderr, "%s\n", buffer);
 526         exit(1);
 527 }
 528
 529 unsigned int pre_buffer_size;
 530 unsigned char pre_buffer[8192];
 531
 532 int preprocess_only;
 533 char *include;
 534 int include_fd = -1;
 535
 536 void add_pre_buffer(const char *fmt, ...)
 537 {
 538         va_list args;
 539         unsigned int size;
 540
 541         va_start(args, fmt);
 542         size = pre_buffer_size;
 543         size += vsnprintf(pre_buffer + size,
 544                 sizeof(pre_buffer) - size,
 545                 fmt, args);
 546         pre_buffer_size = size;
 547         va_end(args);
 548 }
 549
 550 char **handle_switch_D(char *arg, char **next)
 551 {
 552         const char *name = arg + 1;
 553         const char *value = "";
 554         for (;;) {
 555                 char c;
 556                 c = *++arg;
 557                 if (!c)
 558                         break;
 559                 if (isspace(c) || c == '=') {
 560                         *arg = '\0';
 561                         value = arg + 1;
 562                         break;
 563                 }
 564         }
 565         add_pre_buffer("#define %s %s\n", name, value);
 566         return next;
 567 }
 568
 569 char **handle_switch_E(char *arg, char **next)
 570 {
 571         preprocess_only = 1;
 572         return next;
 573 }
 574
 575 char **handle_switch_v(char *arg, char **next)
 576 {
 577         verbose = 1;
 578         return next;
 579 }
 580 char **handle_switch_I(char *arg, char **next)
 581 {
 582         add_pre_buffer("#add_include \"%s/\"\n", arg + 1);
 583         return next;
 584 }
 585
 586 char **handle_switch_i(char *arg, char **next)
 587 {
 588         if (*next && !strcmp(arg, "include")) {
 589                 char *name = *++next;
 590                 int fd = open(name, O_RDONLY);
 591
 592                 include_fd = fd;
 593                 include = name;
 594                 if (fd < 0)
 595                         perror(name);
 596         }
 597         return next;
 598 }
 599
 600 char **handle_switch(char *arg, char **next)
 601 {
 602         char **rc = next;
 603
 604         switch (*arg) {
 605         case 'D': rc = handle_switch_D(arg, next); break;
 606         case 'E': rc = handle_switch_E(arg, next); break;
 607         case 'v': rc = handle_switch_v(arg, next); break;
 608         case 'I': rc = handle_switch_I(arg, next); break;
 609         case 'i': rc = handle_switch_i(arg, next); break;
 610         default:
 611                 /*
 612                  * Ignore unknown command line options:
 613                  * they're probably gcc switches
 614                  */
 615                 break;
 616         }
 617         return rc;
 618 }
 619
 620 void create_builtin_stream(void)
 621 {
 622         add_pre_buffer("#define __i386__ 1\n");
 623         add_pre_buffer("#define __linux__ 1\n");
 624         add_pre_buffer("#define __STDC__ 1\n");
 625         add_pre_buffer("#define linux linux\n");
 626         add_pre_buffer("#define cond_syscall(x)\n");
 627         add_pre_buffer("#define __GNUC__ 2\n");
 628         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 629         add_pre_buffer("#define __func__ \"function\"\n");
 630         add_pre_buffer("#define __extension__\n");
 631         add_pre_buffer("#define __pragma__\n");
 632         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 633         add_pre_buffer("#define __builtin_va_arg(arg,type)  ((type)0)\n");
 634         add_pre_buffer("#define __builtin_va_end(arg)\n");
 635 }