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