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
 165 #define __ALLOCATOR(type, size, x)                              \
 166         type *__alloc_##x(int extra)                            \
 167         {                                                       \
 168                 return allocate(&x##_allocator, size+extra);    \
 169         }                                                       \
 170         void show_##x##_alloc(void)                             \
 171         {                                                       \
 172                 show_allocations(&x##_allocator);               \
 173         }                                                       \
 174         void clear_##x##_alloc(void)                            \
 175         {                                                       \
 176                 drop_all_allocations(&x##_allocator);           \
 177         }
 178 #define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x)
 179
 180 ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol);
 181 ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string);
 182 ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes);
 183 ALLOCATOR(basic_block); ALLOCATOR(entrypoint);
 184 ALLOCATOR(instruction);
 185 ALLOCATOR(multijmp);
 186 ALLOCATOR(phi);
 187
 188 int ptr_list_size(struct ptr_list *head)
 189 {
 190         int nr = 0;
 191
 192         if (head) {
 193                 struct ptr_list *list = head;
 194                 do {
 195                         nr += list->nr;
 196                 } while ((list = list->next) != head);
 197         }
 198         return nr;
 199 }
 200
 201 void iterate(struct ptr_list *head, void (*callback)(void *, void *, int), void *data)
 202 {
 203         struct ptr_list *list = head;
 204         int flag = ITERATE_FIRST;
 205
 206         if (!head)
 207                 return;
 208         do {
 209                 int i;
 210                 for (i = 0; i < list->nr; i++) {
 211                         if (i == list->nr-1 && list->next == head)
 212                                 flag |= ITERATE_LAST;
 213                         callback(list->list[i], data, flag);
 214                         flag = 0;
 215                 }
 216                 list = list->next;
 217         } while (list != head);
 218 }
 219
 220 void add_ptr_list(struct ptr_list **listp, void *ptr)
 221 {
 222         struct ptr_list *list = *listp;
 223         struct ptr_list *last;
 224         int nr;
 225
 226         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 227                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 228                 if (!newlist)
 229                         die("out of memory for symbol/statement lists");
 230                 memset(newlist, 0, sizeof(*newlist));
 231                 if (!list) {
 232                         newlist->next = newlist;
 233                         newlist->prev = newlist;
 234                         *listp = newlist;
 235                 } else {
 236                         newlist->prev = last;
 237                         newlist->next = list;
 238                         list->prev = newlist;
 239                         last->next = newlist;
 240                 }
 241                 last = newlist;
 242                 nr = 0;
 243         }
 244         last->list[nr] = ptr;
 245         nr++;
 246         last->nr = nr;
 247 }
 248
 249 void init_iterator(struct ptr_list **head, struct list_iterator *iterator, int flags)
 250 {
 251         iterator->head = head;
 252         iterator->index = 0;
 253         iterator->active = NULL;
 254         iterator->flags = flags;
 255 }
 256
 257 void * next_iterator(struct list_iterator *iterator)
 258 {
 259         struct ptr_list *list = iterator->active;
 260         int index;
 261
 262         if (!list) {
 263                 if (*iterator->head==NULL)
 264                         return NULL;
 265
 266                 list = *iterator->head;
 267                 iterator->index = 0;
 268                 if (!(iterator->flags & ITERATOR_BACKWARDS)) {
 269                         iterator->active = list;
 270                         return list->list[0];
 271                 }
 272         }
 273
 274         if (iterator->flags & ITERATOR_BACKWARDS) {
 275                 index = iterator->index -1;
 276                 if (index < 0) {
 277                         if (list->prev == *iterator->head)
 278                                 return NULL;
 279                         list = iterator->active = list->prev;
 280                         index = list->nr -1;
 281                 }
 282         } else {
 283                 index = iterator->index + 1;
 284                 if (index >= list->nr) {
 285                         if (list->next == *iterator->head)
 286                                 return NULL;
 287                         list = iterator->active = list->next;
 288                         index = 0;
 289                 }
 290         }
 291         iterator->index = index;
 292         return list->list[index];
 293 }
 294
 295 void replace_iterator(struct list_iterator *iterator, void* ptr)
 296 {
 297         struct ptr_list *list = iterator->active;
 298         if (list)
 299                 list->list[iterator->index] = ptr;
 300 }
 301
 302 void delete_iterator(struct list_iterator *iterator)
 303 {
 304         struct ptr_list *list = iterator->active;
 305         int movsize = list->nr - iterator->index - 1;
 306         void ** curptr = list->list+iterator->index;
 307
 308         if (movsize>0)
 309                 memmove(curptr, curptr+1, movsize*sizeof curptr);
 310
 311         list->nr --;
 312         if (iterator->flags & ITERATOR_BACKWARDS) {
 313                 if (iterator->index + 1 >= list->nr) {
 314                         iterator->active = (list->next == *iterator->head) ? NULL : list->next;
 315                         iterator->index = 0;
 316                 }
 317         } else {
 318                 if (--iterator->index <0) {
 319                         iterator->active = (list->prev == *iterator->head) ? NULL : list->prev;
 320                         iterator->index = list->prev->nr;
 321                 }
 322         }
 323         if (list->nr <=0) {
 324                 list->prev->next = list->next;
 325                 list->next->prev = list->prev;
 326                 if (list == *iterator->head)
 327                         *iterator->head = (list->next == *iterator->head) ? NULL : list->next;
 328                 free(list);
 329         }
 330 }
 331
 332 void init_terminator_iterator(struct instruction* terminator, struct terminator_iterator *iterator)
 333 {
 334         iterator->terminator = terminator;
 335         if (!terminator)
 336                 return;
 337
 338         switch (terminator->opcode) {
 339         case OP_BR:
 340                 iterator->branch = BR_INIT;
 341                 break;
 342         case OP_SWITCH:
 343                 init_multijmp_iterator(&terminator->multijmp_list, &iterator->multijmp, 0);
 344                 break;
 345         }
 346 }
 347
 348 struct basic_block* next_terminator_bb(struct terminator_iterator *iterator)
 349 {
 350         struct instruction *terminator = iterator->terminator;
 351
 352         if (!terminator)
 353                 return NULL;
 354         switch (terminator->opcode) {
 355         case OP_BR:
 356                 switch(iterator->branch) {
 357                 case BR_INIT:
 358                         if (terminator->bb_true) {
 359                                 iterator->branch = BR_TRUE;
 360                                 return terminator->bb_true;
 361                         }
 362                 case BR_TRUE:
 363                         if (terminator->bb_false) {
 364                                 iterator->branch = BR_FALSE;
 365                                 return terminator->bb_false;
 366                         }
 367                 default:
 368                         iterator->branch = BR_END;
 369                         return NULL;
 370                 }
 371                 break;
 372         case OP_SWITCH: {
 373                 struct multijmp *jmp = next_multijmp(&iterator->multijmp);
 374                 return jmp ? jmp->target : NULL;
 375         }
 376         }
 377         return NULL;
 378 }
 379
 380 void replace_terminator_bb(struct terminator_iterator *iterator, struct basic_block* bb)
 381 {
 382         struct instruction *terminator = iterator->terminator;
 383         if (!terminator)
 384                 return;
 385
 386         switch (terminator->opcode) {
 387         case OP_BR:
 388                 switch(iterator->branch) {
 389                 case BR_TRUE:
 390                         if (terminator->bb_true) {
 391                                 terminator->bb_true = bb;
 392                                 return;
 393                         }
 394                 case BR_FALSE:
 395                         if (terminator->bb_false) {
 396                                 terminator->bb_false = bb;
 397                                 return;
 398                         }
 399                 }
 400                 break;
 401
 402         case OP_SWITCH: {
 403                 struct multijmp *jmp = (struct multijmp*) current_iterator(&iterator->multijmp);
 404                 if (jmp)
 405                        jmp->target = bb;
 406         }
 407         }
 408 }
 409
 410
 411
 412 int replace_ptr_list(struct ptr_list **head, void *old_ptr, void *new_ptr)
 413 {
 414         int count = 0;
 415         struct list_iterator iterator;
 416         void *ptr;
 417
 418         init_iterator(head, &iterator, 0);
 419         while ((ptr=next_iterator(&iterator))) {
 420                 if (ptr==old_ptr) {
 421                         if (new_ptr)
 422                                 replace_iterator(&iterator, new_ptr);
 423                         else
 424                                 delete_iterator(&iterator);
 425                         count ++;
 426                 }
 427         }
 428         return count;
 429 }
 430
 431 void * delete_ptr_list_last(struct ptr_list **head)
 432 {
 433         void *ptr = NULL;
 434         struct ptr_list *last;
 435
 436         if (!*head)
 437                 return NULL;
 438         last = (*head)->prev;
 439         if (last->nr)
 440                 ptr = last->list[--last->nr];
 441         if (last->nr <=0) {
 442                 if (last == *head)
 443                         *head = NULL;
 444                 free(last);
 445         }
 446         return ptr;
 447 }
 448
 449 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 450 {
 451         void *entry;
 452         FOR_EACH_PTR(a, entry) {
 453                 add_ptr_list(b, entry);
 454         } END_FOR_EACH_PTR;
 455 }
 456
 457 void free_ptr_list(struct ptr_list **listp)
 458 {
 459         struct ptr_list *tmp, *list = *listp;
 460
 461         if (!list)
 462                 return;
 463
 464         list->prev->next = NULL;
 465         while (list) {
 466                 tmp = list;
 467                 list = list->next;
 468                 free(tmp);
 469         }
 470
 471         *listp = NULL;
 472 }
 473
 474 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 475 {
 476         static char buffer[512];
 477         const char *name;
 478
 479         vsprintf(buffer, fmt, args);
 480         name = input_streams[pos.stream].name;
 481
 482         fprintf(stderr, "%s: %s:%d:%d: %s\n",
 483                 type, name, pos.line, pos.pos, buffer);
 484 }
 485
 486 void warn(struct position pos, const char * fmt, ...)
 487 {
 488         static int warnings = 0;
 489         va_list args;
 490
 491         if (warnings > 100) {
 492                 static int once = 0;
 493                 if (once)
 494                         return;
 495                 fmt = "too many warnings";
 496                 once = 1;
 497         }
 498
 499         va_start(args, fmt);
 500         do_warn("warning", pos, fmt, args);
 501         va_end(args);
 502         warnings++;
 503 }
 504
 505 void error(struct position pos, const char * fmt, ...)
 506 {
 507         va_list args;
 508         va_start(args, fmt);
 509         do_warn("error", pos, fmt, args);
 510         va_end(args);
 511         exit(1);
 512 }
 513
 514 void die(const char *fmt, ...)
 515 {
 516         va_list args;
 517         static char buffer[512];
 518
 519         va_start(args, fmt);
 520         vsnprintf(buffer, sizeof(buffer), fmt, args);
 521         va_end(args);
 522
 523         fprintf(stderr, "%s\n", buffer);
 524         exit(1);
 525 }
 526
 527 unsigned int pre_buffer_size;
 528 unsigned char pre_buffer[8192];
 529
 530 int preprocess_only;
 531 char *include;
 532 int include_fd = -1;
 533
 534 void add_pre_buffer(const char *fmt, ...)
 535 {
 536         va_list args;
 537         unsigned int size;
 538
 539         va_start(args, fmt);
 540         size = pre_buffer_size;
 541         size += vsnprintf(pre_buffer + size,
 542                 sizeof(pre_buffer) - size,
 543                 fmt, args);
 544         pre_buffer_size = size;
 545         va_end(args);
 546 }
 547
 548 char **handle_switch_D(char *arg, char **next)
 549 {
 550         const char *name = arg + 1;
 551         const char *value = "";
 552         for (;;) {
 553                 char c;
 554                 c = *++arg;
 555                 if (!c)
 556                         break;
 557                 if (isspace(c) || c == '=') {
 558                         *arg = '\0';
 559                         value = arg + 1;
 560                         break;
 561                 }
 562         }
 563         add_pre_buffer("#define %s %s\n", name, value);
 564         return next;
 565 }
 566
 567 char **handle_switch_E(char *arg, char **next)
 568 {
 569         preprocess_only = 1;
 570         return next;
 571 }
 572
 573 char **handle_switch_v(char *arg, char **next)
 574 {
 575         verbose = 1;
 576         return next;
 577 }
 578 char **handle_switch_I(char *arg, char **next)
 579 {
 580         add_pre_buffer("#add_include \"%s/\"\n", arg + 1);
 581         return next;
 582 }
 583
 584 char **handle_switch_i(char *arg, char **next)
 585 {
 586         if (*next && !strcmp(arg, "include")) {
 587                 char *name = *++next;
 588                 int fd = open(name, O_RDONLY);
 589
 590                 include_fd = fd;
 591                 include = name;
 592                 if (fd < 0)
 593                         perror(name);
 594         }
 595         return next;
 596 }
 597
 598 char **handle_switch(char *arg, char **next)
 599 {
 600         char **rc = next;
 601
 602         switch (*arg) {
 603         case 'D': rc = handle_switch_D(arg, next); break;
 604         case 'E': rc = handle_switch_E(arg, next); break;
 605         case 'v': rc = handle_switch_v(arg, next); break;
 606         case 'I': rc = handle_switch_I(arg, next); break;
 607         case 'i': rc = handle_switch_i(arg, next); break;
 608         default:
 609                 /*
 610                  * Ignore unknown command line options:
 611                  * they're probably gcc switches
 612                  */
 613                 break;
 614         }
 615         return rc;
 616 }
 617
 618 void create_builtin_stream(void)
 619 {
 620         add_pre_buffer("#define __i386__ 1\n");
 621         add_pre_buffer("#define __linux__ 1\n");
 622         add_pre_buffer("#define __STDC__ 1\n");
 623         add_pre_buffer("#define linux linux\n");
 624         add_pre_buffer("#define cond_syscall(x)\n");
 625         add_pre_buffer("#define __GNUC__ 2\n");
 626         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 627         add_pre_buffer("#define __func__ \"function\"\n");
 628         add_pre_buffer("#define __extension__\n");
 629         add_pre_buffer("#define __pragma__\n");
 630         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 631         add_pre_buffer("#define __builtin_va_arg(arg,type)  ((type)0)\n");
 632         add_pre_buffer("#define __builtin_va_end(arg)\n");
 633 }