[PATCH] evaluate_sign() typo
[smatch.git] / lib.c
blobfe8b63800d0955733b75e06d33a81b7f2c8713ed
1 /*
2 * 'sparse' library helper routines.
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003 Linus Torvalds
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>
17 #include <sys/mman.h>
18 #include <sys/types.h>
19 #include <sys/stat.h>
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"
30 struct token *skip_to(struct token *token, int op)
32 while (!match_op(token, op) && !eof_token(token))
33 token = token->next;
34 return token;
37 struct token *expect(struct token *token, int op, const char *where)
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));
46 if (op == ';')
47 return skip_to(token, op);
48 return &bad_token;
50 return token->next;
53 unsigned int hexval(unsigned int c)
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;
67 return retval;
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.
79 struct allocation_blob {
80 struct allocation_blob *next;
81 unsigned int left, offset;
82 unsigned char data[];
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)
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;
98 void drop_all_allocations(struct allocator_struct *desc)
100 struct allocation_blob *blob = desc->blobs;
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;
113 void *allocate(struct allocator_struct *desc, unsigned int size)
115 unsigned long alignment = desc->alignment;
116 struct allocation_blob *blob = desc->blobs;
117 void *retval;
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);
136 retval = blob->data + blob->offset;
137 blob->offset += size;
138 blob->left -= size;
139 return retval;
142 static void show_allocations(struct allocator_struct *x)
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);
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 };
166 #define __ALLOCATOR(type, size, x) \
167 type *__alloc_##x(int extra) \
169 return allocate(&x##_allocator, size+extra); \
171 void show_##x##_alloc(void) \
173 show_allocations(&x##_allocator); \
175 void clear_##x##_alloc(void) \
177 drop_all_allocations(&x##_allocator); \
179 #define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x)
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);
190 int ptr_list_size(struct ptr_list *head)
192 int nr = 0;
194 if (head) {
195 struct ptr_list *list = head;
196 do {
197 nr += list->nr;
198 } while ((list = list->next) != head);
200 return nr;
203 void iterate(struct ptr_list *head, void (*callback)(void *, void *, int), void *data)
205 struct ptr_list *list = head;
206 int flag = ITERATE_FIRST;
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;
218 list = list->next;
219 } while (list != head);
222 void add_ptr_list(struct ptr_list **listp, void *ptr)
224 struct ptr_list *list = *listp;
225 struct ptr_list *last = NULL; /* gcc complains needlessly */
226 int nr;
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;
243 last = newlist;
244 nr = 0;
246 last->list[nr] = ptr;
247 nr++;
248 last->nr = nr;
251 void init_iterator(struct ptr_list **head, struct list_iterator *iterator, int flags)
253 iterator->head = head;
254 iterator->index = 0;
255 iterator->active = NULL;
256 iterator->flags = flags;
259 void * next_iterator(struct list_iterator *iterator)
261 struct ptr_list *list = iterator->active;
262 int index;
264 if (!list) {
265 if (*iterator->head==NULL)
266 return NULL;
268 list = *iterator->head;
269 iterator->index = 0;
270 if (!(iterator->flags & ITERATOR_BACKWARDS)) {
271 iterator->active = list;
272 return list->list[0];
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;
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;
293 iterator->index = index;
294 return list->list[index];
297 void replace_iterator(struct list_iterator *iterator, void* ptr)
299 struct ptr_list *list = iterator->active;
300 if (list)
301 list->list[iterator->index] = ptr;
304 void delete_iterator(struct list_iterator *iterator)
306 struct ptr_list *list = iterator->active;
307 int movsize = list->nr - iterator->index - 1;
308 void ** curptr = list->list+iterator->index;
310 if (movsize>0)
311 memmove(curptr, curptr+1, movsize*sizeof curptr);
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;
319 } else {
320 if (--iterator->index <0) {
321 iterator->active = (list->prev == *iterator->head) ? NULL : list->prev;
322 iterator->index = list->prev->nr;
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);
334 void init_terminator_iterator(struct instruction* terminator, struct terminator_iterator *iterator)
336 iterator->terminator = terminator;
337 if (!terminator)
338 return;
340 switch (terminator->opcode) {
341 case OP_BR:
342 iterator->branch = BR_INIT;
343 break;
344 case OP_SWITCH:
345 case OP_COMPUTEDGOTO:
346 init_multijmp_iterator(&terminator->multijmp_list, &iterator->multijmp, 0);
347 break;
351 struct basic_block* next_terminator_bb(struct terminator_iterator *iterator)
353 struct instruction *terminator = iterator->terminator;
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;
365 case BR_TRUE:
366 if (terminator->bb_false) {
367 iterator->branch = BR_FALSE;
368 return terminator->bb_false;
370 default:
371 iterator->branch = BR_END;
372 return NULL;
374 break;
375 case OP_COMPUTEDGOTO:
376 case OP_SWITCH: {
377 struct multijmp *jmp = next_multijmp(&iterator->multijmp);
378 return jmp ? jmp->target : NULL;
381 return NULL;
384 void replace_terminator_bb(struct terminator_iterator *iterator, struct basic_block* bb)
386 struct instruction *terminator = iterator->terminator;
387 if (!terminator)
388 return;
390 switch (terminator->opcode) {
391 case OP_BR:
392 switch(iterator->branch) {
393 case BR_TRUE:
394 if (terminator->bb_true) {
395 terminator->bb_true = bb;
396 return;
398 case BR_FALSE:
399 if (terminator->bb_false) {
400 terminator->bb_false = bb;
401 return;
404 break;
406 case OP_COMPUTEDGOTO:
407 case OP_SWITCH: {
408 struct multijmp *jmp = (struct multijmp*) current_iterator(&iterator->multijmp);
409 if (jmp)
410 jmp->target = bb;
417 int replace_ptr_list(struct ptr_list **head, void *old_ptr, void *new_ptr)
419 int count = 0;
420 struct list_iterator iterator;
421 void *ptr;
423 init_iterator(head, &iterator, 0);
424 while ((ptr=next_iterator(&iterator)) != NULL) {
425 if (ptr==old_ptr) {
426 if (new_ptr)
427 replace_iterator(&iterator, new_ptr);
428 else
429 delete_iterator(&iterator);
430 count ++;
433 return count;
436 void * delete_ptr_list_last(struct ptr_list **head)
438 void *ptr = NULL;
439 struct ptr_list *last, *first = *head;
441 if (!first)
442 return NULL;
443 last = first->prev;
444 if (last->nr)
445 ptr = last->list[--last->nr];
446 if (last->nr <=0) {
447 first->prev = last->prev;
448 last->prev->next = first;
449 if (last == first)
450 *head = NULL;
451 free(last);
453 return ptr;
456 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
458 void *entry;
459 FOR_EACH_PTR(a, entry) {
460 add_ptr_list(b, entry);
461 } END_FOR_EACH_PTR;
464 void free_ptr_list(struct ptr_list **listp)
466 struct ptr_list *tmp, *list = *listp;
468 if (!list)
469 return;
471 list->prev->next = NULL;
472 while (list) {
473 tmp = list;
474 list = list->next;
475 free(tmp);
478 *listp = NULL;
481 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
483 static char buffer[512];
484 const char *name;
486 vsprintf(buffer, fmt, args);
487 name = input_streams[pos.stream].name;
489 fprintf(stderr, "%s:%d:%d: %s%s\n",
490 name, pos.line, pos.pos, type, buffer);
493 void info(struct position pos, const char * fmt, ...)
495 va_list args;
496 va_start(args, fmt);
497 do_warn("", pos, fmt, args);
498 va_end(args);
501 void warn(struct position pos, const char * fmt, ...)
503 static int warnings = 0;
504 va_list args;
506 if (warnings > 100) {
507 static int once = 0;
508 if (once)
509 return;
510 fmt = "too many warnings";
511 once = 1;
514 va_start(args, fmt);
515 do_warn("warning: ", pos, fmt, args);
516 va_end(args);
517 warnings++;
520 void error(struct position pos, const char * fmt, ...)
522 va_list args;
523 va_start(args, fmt);
524 do_warn("error: ", pos, fmt, args);
525 va_end(args);
526 exit(1);
529 void die(const char *fmt, ...)
531 va_list args;
532 static char buffer[512];
534 va_start(args, fmt);
535 vsnprintf(buffer, sizeof(buffer), fmt, args);
536 va_end(args);
538 fprintf(stderr, "%s\n", buffer);
539 exit(1);
542 unsigned int pre_buffer_size;
543 unsigned char pre_buffer[8192];
545 int Wdefault_bitfield_sign = 0;
546 int preprocess_only;
547 char *include;
548 int include_fd = -1;
550 void add_pre_buffer(const char *fmt, ...)
552 va_list args;
553 unsigned int size;
555 va_start(args, fmt);
556 size = pre_buffer_size;
557 size += vsnprintf(pre_buffer + size,
558 sizeof(pre_buffer) - size,
559 fmt, args);
560 pre_buffer_size = size;
561 va_end(args);
564 char **handle_switch_D(char *arg, char **next)
566 const char *name = arg + 1;
567 const char *value = "1";
568 for (;;) {
569 char c;
570 c = *++arg;
571 if (!c)
572 break;
573 if (isspace((unsigned char)c) || c == '=') {
574 *arg = '\0';
575 value = arg + 1;
576 break;
579 add_pre_buffer("#define %s %s\n", name, value);
580 return next;
583 char **handle_switch_E(char *arg, char **next)
585 preprocess_only = 1;
586 return next;
589 char **handle_switch_v(char *arg, char **next)
591 verbose = 1;
592 return next;
594 char **handle_switch_I(char *arg, char **next)
596 // FIXME: What about "-I-"?
597 if (!strcmp (arg, "I") && *next) {
598 add_pre_buffer("#add_include \"%s/\"\n", next);
599 return next + 1; // "-I foo"
600 } else {
601 add_pre_buffer("#add_include \"%s/\"\n", arg + 1);
602 return next; // "-Ifoo" or (bogus) terminal "-I"
606 char **handle_switch_i(char *arg, char **next)
608 if (*next && !strcmp(arg, "include")) {
609 char *name = *++next;
610 int fd = open(name, O_RDONLY);
612 include_fd = fd;
613 include = name;
614 if (fd < 0)
615 perror(name);
617 return next;
620 char **handle_switch_M(char *arg, char **next)
622 if (!strcmp(arg, "MF") || !strcmp(arg,"MQ") || !strcmp(arg,"MT")) {
623 if (!*next)
624 die("missing argument for -%s option", arg);
625 return next + 1;
627 return next;
630 char **handle_switch_m(char *arg, char **next)
632 if (!strcmp(arg, "m64")) {
633 bits_in_long = 64;
634 max_int_alignment = 8;
635 bits_in_pointer = 64;
636 pointer_alignment = 8;
638 return next;
641 char **handle_switch_o(char *arg, char **next)
643 if (!strcmp (arg, "o") && *next)
644 return next + 1; // "-o foo"
645 else
646 return next; // "-ofoo" or (bogus) terminal "-o"
649 struct warning {
650 const char *name;
651 int *flag;
652 } warnings[] = {
653 { "default-bitfield-sign", &Wdefault_bitfield_sign }
657 char **handle_switch_W(char *arg, char **next)
659 int no = 0;
660 char *p = arg + 1;
661 unsigned i;
663 // Prefixes "no" and "no-" mean to turn warning off.
664 if (p[0] == 'n' && p[1] == 'o') {
665 p += 2;
666 if (p[0] == '-')
667 p++;
668 no = 1;
671 for (i = 0; i < sizeof(warnings) / sizeof(warnings[0]); i++) {
672 if (!strcmp(p,warnings[i].name)) {
673 *warnings[i].flag = !no;
674 return next;
678 // Unknown.
679 return next;
682 char **handle_nostdinc(char *arg, char **next)
684 add_pre_buffer("#nostdinc\n");
685 return next;
688 struct switches {
689 const char *name;
690 char **(*fn)(char *, char**);
693 char **handle_switch(char *arg, char **next)
695 char **rc = next;
696 static struct switches cmd[] = {
697 { "nostdinc", handle_nostdinc },
698 { NULL, NULL }
700 struct switches *s;
702 switch (*arg) {
703 case 'D': rc = handle_switch_D(arg, next); break;
704 case 'E': rc = handle_switch_E(arg, next); break;
705 case 'v': rc = handle_switch_v(arg, next); break;
706 case 'I': rc = handle_switch_I(arg, next); break;
707 case 'i': rc = handle_switch_i(arg, next); break;
708 case 'M': rc = handle_switch_M(arg, next); break;
709 case 'm': rc = handle_switch_m(arg, next); break;
710 case 'o': rc = handle_switch_o(arg, next); break;
711 case 'W': rc = handle_switch_W(arg, next); break;
712 default:
713 break;
716 s = cmd;
717 while (s->name) {
718 if (!strcmp(s->name, arg))
719 return s->fn(arg, next);
720 s++;
724 * Ignore unknown command line options:
725 * they're probably gcc switches
727 return rc;
730 void create_builtin_stream(void)
732 add_pre_buffer("#define __linux__ 1\n");
733 add_pre_buffer("#define linux linux\n");
734 add_pre_buffer("#define unix 1\n");
735 add_pre_buffer("#define __unix 1\n");
736 add_pre_buffer("#define __unix__ 1\n");
737 add_pre_buffer("#define __STDC__ 1\n");
738 add_pre_buffer("#define __GNUC__ 2\n");
739 add_pre_buffer("#define __GNUC_MINOR__ 95\n");
740 add_pre_buffer("#define __extension__\n");
741 add_pre_buffer("#define __pragma__\n");
742 // gcc defines __SIZE_TYPE__ to be size_t. For linux/i86 and
743 // solaris/sparc that is really "unsigned int" and for linux/x86_64
744 // it is "long unsigned int". In either case we can probably
745 // get away with this:
746 add_pre_buffer("#define __SIZE_TYPE__ long unsigned int\n");
747 add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
748 add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
749 add_pre_buffer("#define __builtin_va_arg(arg,type) ((type)0)\n");
750 add_pre_buffer("#define __builtin_va_end(arg)\n");