2 * 'sparse' library helper routines.
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003-2004 Linus Torvalds
7 * Licensed under the Open Software License version 1.1
19 #include <sys/types.h>
26 #include "expression.h"
28 #include "linearize.h"
31 int verbose
, optimize
, preprocessing
;
33 struct token
*skip_to(struct token
*token
, int op
)
35 while (!match_op(token
, op
) && !eof_token(token
))
40 struct token
*expect(struct token
*token
, int op
, const char *where
)
42 if (!match_op(token
, op
)) {
43 static struct token bad_token
;
44 if (token
!= &bad_token
) {
45 bad_token
.next
= token
;
46 warning(token
->pos
, "Expected %s %s", show_special(op
), where
);
47 warning(token
->pos
, "got %s", show_token(token
));
50 return skip_to(token
, op
);
56 unsigned int hexval(unsigned int c
)
64 retval
= c
- 'a' + 10;
67 retval
= c
- 'A' + 10;
73 int ptr_list_size(struct ptr_list
*head
)
78 struct ptr_list
*list
= head
;
81 } while ((list
= list
->next
) != head
);
87 * Linearize the entries of a list up to a total of 'max',
88 * and return the nr of entries linearized.
90 * The array to linearize into (second argument) should really
91 * be "void *x[]", but we want to let people fill in any kind
92 * of pointer array, so let's just call it "void *".
94 int linearize_ptr_list(struct ptr_list
*head
, void **arr
, int max
)
97 if (head
&& max
> 0) {
98 struct ptr_list
*list
= head
;
104 memcpy(arr
, list
->list
, i
*sizeof(void *));
110 } while ((list
= list
->next
) != head
);
116 * When we've walked the list and deleted entries,
117 * we may need to re-pack it so that we don't have
118 * any empty blocks left (empty blocks upset the
121 void pack_ptr_list(struct ptr_list
**listp
)
123 struct ptr_list
*head
= *listp
;
126 struct ptr_list
*entry
= head
;
128 struct ptr_list
*next
;
132 struct ptr_list
*prev
;
149 } while (entry
!= head
);
153 void split_ptr_list_head(struct ptr_list
*head
)
155 int old
= head
->nr
, nr
= old
/ 2;
156 struct ptr_list
*newlist
= malloc(sizeof(*newlist
));
157 struct ptr_list
*next
= head
->next
;
161 newlist
->next
= next
;
162 next
->prev
= newlist
;
163 newlist
->prev
= head
;
164 head
->next
= newlist
;
166 memcpy(newlist
->list
, head
->list
+ old
, nr
* sizeof(void *));
167 memset(head
->list
+ old
, 0xf0, nr
* sizeof(void *));
170 void **__add_ptr_list(struct ptr_list
**listp
, void *ptr
)
172 struct ptr_list
*list
= *listp
;
173 struct ptr_list
*last
= NULL
; /* gcc complains needlessly */
177 /* The low two bits are reserved for tags */
178 assert((3 & (unsigned long)ptr
) == 0);
180 if (!list
|| (nr
= (last
= list
->prev
)->nr
) >= LIST_NODE_NR
) {
181 struct ptr_list
*newlist
= malloc(sizeof(*newlist
));
183 die("out of memory for symbol/statement lists");
184 memset(newlist
, 0, sizeof(*newlist
));
186 newlist
->next
= newlist
;
187 newlist
->prev
= newlist
;
190 newlist
->prev
= last
;
191 newlist
->next
= list
;
192 list
->prev
= newlist
;
193 last
->next
= newlist
;
198 ret
= last
->list
+ nr
;
205 void delete_ptr_list_entry(struct ptr_list
**list
, void *entry
, int count
)
209 FOR_EACH_PTR(*list
, ptr
) {
211 DELETE_CURRENT_PTR(ptr
);
215 } END_FOR_EACH_PTR(ptr
);
221 void replace_ptr_list_entry(struct ptr_list
**list
, void *old_ptr
, void *new_ptr
, int count
)
225 FOR_EACH_PTR(*list
, ptr
) {
227 REPLACE_CURRENT_PTR(ptr
, new_ptr
);
231 }END_FOR_EACH_PTR(ptr
);
235 void * delete_ptr_list_last(struct ptr_list
**head
)
238 struct ptr_list
*last
, *first
= *head
;
244 ptr
= last
->list
[--last
->nr
];
246 first
->prev
= last
->prev
;
247 last
->prev
->next
= first
;
255 void concat_ptr_list(struct ptr_list
*a
, struct ptr_list
**b
)
258 FOR_EACH_PTR(a
, entry
) {
259 add_ptr_list(b
, entry
);
260 } END_FOR_EACH_PTR(entry
);
263 void __free_ptr_list(struct ptr_list
**listp
)
265 struct ptr_list
*tmp
, *list
= *listp
;
270 list
->prev
->next
= NULL
;
280 static void do_warn(const char *type
, struct position pos
, const char * fmt
, va_list args
)
282 static char buffer
[512];
285 vsprintf(buffer
, fmt
, args
);
286 name
= stream_name(pos
.stream
);
288 fprintf(stderr
, "%s:%d:%d: %s%s\n",
289 name
, pos
.line
, pos
.pos
, type
, buffer
);
292 void info(struct position pos
, const char * fmt
, ...)
296 do_warn("", pos
, fmt
, args
);
300 void warning(struct position pos
, const char * fmt
, ...)
302 static int warnings
= 0;
305 if (warnings
> 100) {
309 fmt
= "too many warnings";
314 do_warn("warning: ", pos
, fmt
, args
);
319 void error(struct position pos
, const char * fmt
, ...)
321 static int errors
= 0;
328 fmt
= "too many errors";
333 do_warn("error: ", pos
, fmt
, args
);
338 void error_die(struct position pos
, const char * fmt
, ...)
342 do_warn("error: ", pos
, fmt
, args
);
347 void die(const char *fmt
, ...)
350 static char buffer
[512];
353 vsnprintf(buffer
, sizeof(buffer
), fmt
, args
);
356 fprintf(stderr
, "%s\n", buffer
);
360 unsigned int pre_buffer_size
;
361 unsigned char pre_buffer
[8192];
363 int Wdefault_bitfield_sign
= 0;
367 int Wundefined_preprocessor
= 0;
372 void add_pre_buffer(const char *fmt
, ...)
378 size
= pre_buffer_size
;
379 size
+= vsnprintf(pre_buffer
+ size
,
380 sizeof(pre_buffer
) - size
,
382 pre_buffer_size
= size
;
386 char **handle_switch_D(char *arg
, char **next
)
388 const char *name
= arg
+ 1;
389 const char *value
= "1";
395 if (isspace((unsigned char)c
) || c
== '=') {
401 add_pre_buffer("#define %s %s\n", name
, value
);
405 char **handle_switch_E(char *arg
, char **next
)
411 char **handle_switch_v(char *arg
, char **next
)
415 } while (*++arg
== 'v');
419 char **handle_switch_I(char *arg
, char **next
)
425 /* Explaining '-I-' with a google search:
427 * "Specifying -I after -I- searches for #include directories.
428 * If -I- is specified before, it searches for #include "file"
429 * and not #include ."
431 * Which didn't explain it at all to me. Maybe somebody else can
432 * explain it properly. We ignore it for now.
436 case '\0': /* Plain "-I" */
439 die("missing argument for -I option");
442 add_pre_buffer("#add_include \"%s/\"\n", path
);
447 char **handle_switch_i(char *arg
, char **next
)
449 if (*next
&& !strcmp(arg
, "include")) {
450 char *name
= *++next
;
451 int fd
= open(name
, O_RDONLY
);
461 char **handle_switch_M(char *arg
, char **next
)
463 if (!strcmp(arg
, "MF") || !strcmp(arg
,"MQ") || !strcmp(arg
,"MT")) {
465 die("missing argument for -%s option", arg
);
471 char **handle_switch_m(char *arg
, char **next
)
473 if (!strcmp(arg
, "m64")) {
475 max_int_alignment
= 8;
476 bits_in_pointer
= 64;
477 pointer_alignment
= 8;
482 char **handle_switch_o(char *arg
, char **next
)
484 if (!strcmp (arg
, "o") && *next
)
485 return next
+ 1; // "-o foo"
487 return next
; // "-ofoo" or (bogus) terminal "-o"
490 const struct warning
{
494 { "default-bitfield-sign", &Wdefault_bitfield_sign
},
495 { "undef", &Wundefined_preprocessor
},
496 { "bitwise", &Wbitwise
},
497 { "typesign", &Wtypesign
},
498 { "context", &Wcontext
},
502 char **handle_switch_W(char *arg
, char **next
)
508 // Prefixes "no" and "no-" mean to turn warning off.
509 if (p
[0] == 'n' && p
[1] == 'o') {
516 for (i
= 0; i
< sizeof(warnings
) / sizeof(warnings
[0]); i
++) {
517 if (!strcmp(p
,warnings
[i
].name
)) {
518 *warnings
[i
].flag
= !no
;
527 char **handle_switch_U(char *arg
, char **next
)
529 const char *name
= arg
+ 1;
530 add_pre_buffer ("#undef %s\n", name
);
534 char **handle_switch_O(char *arg
, char **next
)
537 if (arg
[1] >= '0' && arg
[1] <= '9')
538 level
= arg
[1] - '0';
543 char **handle_nostdinc(char *arg
, char **next
)
545 add_pre_buffer("#nostdinc\n");
551 char **(*fn
)(char *, char**);
554 char **handle_switch(char *arg
, char **next
)
557 static struct switches cmd
[] = {
558 { "nostdinc", handle_nostdinc
},
564 case 'D': rc
= handle_switch_D(arg
, next
); break;
565 case 'E': rc
= handle_switch_E(arg
, next
); break;
566 case 'I': rc
= handle_switch_I(arg
, next
); break;
567 case 'i': rc
= handle_switch_i(arg
, next
); break;
568 case 'M': rc
= handle_switch_M(arg
, next
); break;
569 case 'm': rc
= handle_switch_m(arg
, next
); break;
570 case 'o': rc
= handle_switch_o(arg
, next
); break;
571 case 'U': rc
= handle_switch_U(arg
, next
); break;
572 case 'v': rc
= handle_switch_v(arg
, next
); break;
573 case 'W': rc
= handle_switch_W(arg
, next
); break;
574 case 'O': rc
= handle_switch_O(arg
, next
); break;
581 if (!strcmp(s
->name
, arg
))
582 return s
->fn(arg
, next
);
587 * Ignore unknown command line options:
588 * they're probably gcc switches
593 void declare_builtin_functions(void)
595 add_pre_buffer("extern void *__builtin_memcpy(void *, const void *, __SIZE_TYPE__);\n");
596 add_pre_buffer("extern void *__builtin_return_address(unsigned int);\n");
597 add_pre_buffer("extern void *__builtin_frame_address(unsigned int);\n");
598 add_pre_buffer("extern void *__builtin_memset(void *, int, __SIZE_TYPE__);\n");
599 add_pre_buffer("extern void __builtin_trap(void);\n");
600 add_pre_buffer("extern int __builtin_ffs(int);\n");
601 add_pre_buffer("extern void *__builtin_alloca(__SIZE_TYPE__);\n");
604 void create_builtin_stream(void)
606 add_pre_buffer("#define __GNUC__ 2\n");
607 add_pre_buffer("#define __GNUC_MINOR__ 95\n");
608 add_pre_buffer("#define __extension__\n");
609 add_pre_buffer("#define __pragma__\n");
611 // gcc defines __SIZE_TYPE__ to be size_t. For linux/i86 and
612 // solaris/sparc that is really "unsigned int" and for linux/x86_64
613 // it is "long unsigned int". In either case we can probably
614 // get away with this. We need the #ifndef as cgcc will define
615 // the right __SIZE_TYPE__.
616 add_pre_buffer("#weak_define __SIZE_TYPE__ long unsigned int\n");
617 add_pre_buffer("#weak_define __STDC__ 1\n");
619 add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
620 add_pre_buffer("#define __builtin_va_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
621 add_pre_buffer("#define __builtin_va_arg(arg,type) ({ type __va_arg_ret = *(type *)(arg); arg += sizeof(type); __va_arg_ret; })\n");
622 add_pre_buffer("#define __builtin_va_alist (*(void *)0)\n");
623 add_pre_buffer("#define __builtin_va_arg_incr(x) ((x) + 1)\n");
624 add_pre_buffer("#define __builtin_va_end(arg)\n");
627 static void do_predefined(char *filename
)
629 add_pre_buffer("#define __BASE_FILE__ \"%s\"\n", filename
);
630 add_pre_buffer("#define __DATE__ \"??? ?? ????\"\n");
631 add_pre_buffer("#define __TIME__ \"??:??:??\"\n");
634 struct symbol_list
*sparse(int argc
, char **argv
)
637 char *filename
= NULL
, **args
;
640 // Initialize symbol stream first, so that we can add defines etc
648 if (arg
[0] == '-' && arg
[1]) {
649 args
= handle_switch(arg
+1, args
);
656 die("no input files given");
658 // Initialize type system
661 create_builtin_stream();
662 add_pre_buffer("#define __CHECKER__ 1\n");
663 if (!preprocess_only
)
664 declare_builtin_functions();
666 do_predefined(filename
);
668 if (strcmp (filename
, "-") == 0) {
671 fd
= open(filename
, O_RDONLY
);
673 die("No such file: %s", filename
);
676 // Tokenize the input stream
677 token
= tokenize(filename
, fd
, NULL
, includepath
);
680 // Prepend any "include" file to the stream.
682 token
= tokenize(include
, include_fd
, token
, includepath
);
684 // Prepend the initial built-in stream
685 token
= tokenize_buffer(pre_buffer
, pre_buffer_size
, token
);
687 // Pre-process the stream
688 token
= preprocess(token
);
690 if (preprocess_only
) {
691 while (!eof_token(token
)) {
693 struct token
*next
= token
->next
;
694 const char *separator
= "";
695 if (next
->pos
.whitespace
)
697 if (next
->pos
.newline
) {
698 separator
= "\n\t\t\t\t\t";
699 prec
= next
->pos
.pos
;
703 printf("%s%.*s", show_token(token
), prec
, separator
);
711 // Parse the resulting C code
712 return translation_unit(token
);