?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] strip modifiers and address space in "typeof()"
[smatch.git] / symbol.c
blob31ec4ecce6f0aa3a99b149bb2be57a386df42ec7
1 /*
2 * Symbol lookup and handling.
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 <stdlib.h>
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include "lib.h"
15 #include "token.h"
16 #include "parse.h"
17 #include "symbol.h"
18 #include "scope.h"
19 #include "expression.h"
20
21 #include "target.h"
22
23 /*
24 * Secondary symbol list for stuff that needs to be output because it
25 * was used.
26 */
27 struct symbol_list *used_list = NULL;
28
29 /*
30 * If the symbol is an inline symbol, add it to the list of symbols to parse
31 */
32 void access_symbol(struct symbol *sym)
33 {
34 if (sym->ctype.modifiers & MOD_INLINE) {
35 if (!(sym->ctype.modifiers & MOD_ACCESSED)) {
36 add_symbol(&used_list, sym);
37 sym->ctype.modifiers |= MOD_ACCESSED;
38 }
39 }
40 }
41
42 struct symbol *lookup_symbol(struct ident *ident, enum namespace ns)
43 {
44 struct symbol *sym;
45
46 for (sym = ident->symbols; sym; sym = sym->next_id) {
47 if (sym->namespace & ns) {
48 sym->used = 1;
49 return sym;
50 }
51 }
52 return sym;
53 }
54
55 struct symbol *alloc_symbol(struct position pos, int type)
56 {
57 struct symbol *sym = __alloc_symbol(0);
58 sym->type = type;
59 sym->pos = pos;
60 return sym;
61 }
62
63 struct struct_union_info {
64 unsigned long max_align;
65 unsigned long bit_size;
66 };
67
68 /*
69 * Unions are easy to lay out ;)
70 */
71 static void lay_out_union(struct symbol *sym, void *_info, int flags)
72 {
73 struct struct_union_info *info = _info;
74
75 examine_symbol_type(sym);
76 if (sym->ctype.alignment > info->max_align)
77 info->max_align = sym->ctype.alignment;
78 if (sym->bit_size > info->bit_size)
79 info->bit_size = sym->bit_size;
80
81 sym->offset = 0;
82 }
83
84 /*
85 * Structures are a bit more interesting to lay out
86 */
87 static void lay_out_struct(struct symbol *sym, void *_info, int flags)
88 {
89 struct struct_union_info *info = _info;
90 unsigned long bit_size, base_size;
91 unsigned long align_bit_mask;
92
93 examine_symbol_type(sym);
94 if (sym->ctype.alignment > info->max_align)
95 info->max_align = sym->ctype.alignment;
96
97 bit_size = info->bit_size;
98 base_size = sym->bit_size;
99 align_bit_mask = (sym->ctype.alignment << 3) - 1;
100
101 /*
102 * Bitfields have some very special rules..
103 */
104 if (sym->fieldwidth) {
105 unsigned long bit_offset = bit_size & align_bit_mask;
106
107 if (bit_offset + sym->fieldwidth > base_size) {
108 bit_size = (bit_size + align_bit_mask) & ~align_bit_mask;
109 bit_offset = 0;
110 }
111 sym->offset = (bit_size - bit_offset) >> 3;
112 sym->bit_offset = bit_offset;
113 info->bit_size = bit_size + sym->fieldwidth;
114 return;
115 }
116
117 /*
118 * Otherwise, just align it right and add it up..
119 */
120 bit_size = (bit_size + align_bit_mask) & ~align_bit_mask;
121 sym->offset = bit_size >> 3;
122
123 info->bit_size = bit_size + sym->bit_size;
124 }
125
126 static void examine_struct_union_type(struct symbol *sym, int advance)
127 {
128 struct struct_union_info info = { 1, 0 };
129 unsigned long bit_size, bit_align;
130 void (*fn)(struct symbol *, void *, int);
131
132 fn = advance ? lay_out_struct : lay_out_union;
133 symbol_iterate(sym->symbol_list, fn, &info);
134
135 if (!sym->ctype.alignment)
136 sym->ctype.alignment = info.max_align;
137 bit_size = info.bit_size;
138 bit_align = (sym->ctype.alignment << 3)-1;
139 bit_size = (bit_size + bit_align) & ~bit_align;
140 sym->bit_size = bit_size;
141 }
142
143 static void examine_array_type(struct symbol *sym)
144 {
145 struct symbol *base_type = sym->ctype.base_type;
146 unsigned long bit_size, alignment;
147
148 if (!base_type)
149 return;
150 examine_symbol_type(base_type);
151 bit_size = base_type->bit_size * get_expression_value(sym->array_size);
152 if (!sym->array_size || sym->array_size->type != EXPR_VALUE)
153 bit_size = -1;
154 alignment = base_type->ctype.alignment;
155 if (!sym->ctype.alignment)
156 sym->ctype.alignment = alignment;
157 sym->bit_size = bit_size;
158 }
159
160 static void examine_bitfield_type(struct symbol *sym)
161 {
162 struct symbol *base_type = sym->ctype.base_type;
163 unsigned long bit_size, alignment;
164
165 if (!base_type)
166 return;
167 examine_symbol_type(base_type);
168 bit_size = base_type->bit_size;
169 if (sym->fieldwidth > bit_size) {
170 warn(sym->pos, "impossible field-width for this type");
171 sym->fieldwidth = bit_size;
172 }
173 alignment = base_type->ctype.alignment;
174 if (!sym->ctype.alignment)
175 sym->ctype.alignment = alignment;
176 sym->bit_size = bit_size;
177 }
178
179 /*
180 * "typeof" will have to merge the types together
181 */
182 void merge_type(struct symbol *sym, struct symbol *base_type)
183 {
184 sym->ctype.as |= base_type->ctype.as;
185 sym->ctype.modifiers |= (base_type->ctype.modifiers & ~MOD_STORAGE);
186 sym->ctype.context |= base_type->ctype.context;
187 sym->ctype.contextmask |= base_type->ctype.contextmask;
188 sym->ctype.base_type = base_type->ctype.base_type;
189 }
190
191 /*
192 * Fill in type size and alignment information for
193 * regular SYM_TYPE things.
194 */
195 #define MOD_STRIP (MOD_CONST | MOD_VOLATILE | MOD_ADDRESSABLE | \
196 MOD_NODEREF | MOD_ACCESSED | MOD_ASSIGNED | \
197 MOD_SAFE | MOD_FORCE | MOD_STORAGE)
198 struct symbol *examine_symbol_type(struct symbol * sym)
199 {
200 unsigned int bit_size, alignment;
201 struct symbol *base_type;
202 unsigned long modifiers;
203
204 if (!sym)
205 return sym;
206
207 /* Already done? */
208 if (sym->bit_size)
209 return sym;
210
211 switch (sym->type) {
212 case SYM_ARRAY:
213 examine_array_type(sym);
214 return sym;
215 case SYM_STRUCT:
216 examine_struct_union_type(sym, 1);
217 return sym;
218 case SYM_UNION:
219 examine_struct_union_type(sym, 0);
220 return sym;
221 case SYM_PTR:
222 if (!sym->bit_size)
223 sym->bit_size = bits_in_pointer;
224 if (!sym->ctype.alignment)
225 sym->ctype.alignment = pointer_alignment;
226 base_type = sym->ctype.base_type;
227 base_type = examine_symbol_type(base_type);
228 if (base_type && base_type->type == SYM_NODE)
229 merge_type(sym, base_type);
230 return sym;
231 case SYM_ENUM:
232 if (!sym->bit_size)
233 sym->bit_size = bits_in_enum;
234 if (!sym->ctype.alignment)
235 sym->ctype.alignment = enum_alignment;
236 return sym;
237 case SYM_BITFIELD:
238 examine_bitfield_type(sym);
239 return sym;
240 case SYM_BASETYPE:
241 /* Size and alignment had better already be set up */
242 return sym;
243 case SYM_TYPEOF: {
244 struct symbol *base = evaluate_expression(sym->initializer);
245 if (base) {
246 struct symbol *node;
247 unsigned long mod;
248 if (base->type != SYM_NODE)
249 return base;
250 mod = base->ctype.modifiers;
251 /* do we have anything to get rid of? */
252 if (!base->ctype.as && !(mod & MOD_STRIP))
253 return base;
254 node = alloc_symbol(sym->pos, SYM_NODE);
255 node->bit_size = base->bit_size;
256 node->array_size = base->array_size;
257 node->ctype.modifiers = mod & ~MOD_STRIP;
258 node->ctype.context = base->ctype.context;
259 node->ctype.contextmask = base->ctype.contextmask;
260 node->ctype.base_type = base->ctype.base_type;
261 return node;
262 }
263 break;
264 }
265 default:
266 break;
267 }
268
269 /* SYM_NODE - figure out what the type of the node was.. */
270 base_type = sym->ctype.base_type;
271 modifiers = sym->ctype.modifiers;
272
273 bit_size = 0;
274 alignment = 0;
275 if (base_type) {
276 base_type = examine_symbol_type(base_type);
277 sym->ctype.base_type = base_type;
278 if (base_type && base_type->type == SYM_NODE)
279 merge_type(sym, base_type);
280
281 bit_size = base_type->bit_size;
282 alignment = base_type->ctype.alignment;
283 if (base_type->fieldwidth)
284 sym->fieldwidth = base_type->fieldwidth;
285 }
286
287 if (!sym->ctype.alignment)
288 sym->ctype.alignment = alignment;
289 sym->bit_size = bit_size;
290 return sym;
291 }
292
293 void check_declaration(struct symbol *sym)
294 {
295 struct symbol *next = sym;
296
297 while ((next = next->next_id) != NULL) {
298 if (next->namespace != sym->namespace)
299 continue;
300 if (sym->scope == next->scope) {
301 sym->same_symbol = next;
302 return;
303 }
304 if (sym->ctype.modifiers & next->ctype.modifiers & MOD_EXTERN) {
305 sym->same_symbol = next;
306 return;
307 }
308 #if 0
309 // This may make sense from a warning standpoint:
310 // consider top-level symbols to clash with everything
311 // (but the scoping rules will mean that we actually
312 // _use_ the innermost version)
313 if (toplevel(next->scope)) {
314 sym->same_symbol = next;
315 return;
316 }
317 #endif
318 }
319 }
320
321 void bind_symbol(struct symbol *sym, struct ident *ident, enum namespace ns)
322 {
323 struct scope *scope;
324 if (sym->id_list) {
325 warn(sym->pos, "internal error: symbol type already bound");
326 return;
327 }
328 sym->namespace = ns;
329 sym->next_id = ident->symbols;
330 ident->symbols = sym;
331 sym->id_list = &ident->symbols;
332
333 scope = block_scope;
334 if (ns != NS_TYPEDEF && toplevel(scope)) {
335 sym->ctype.modifiers |= MOD_TOPLEVEL | MOD_ADDRESSABLE;
336 if (sym->ctype.modifiers & MOD_STATIC)
337 scope = file_scope;
338 }
339 if (ns == NS_LABEL)
340 scope = function_scope;
341 bind_scope(sym, scope);
342 }
343
344 static struct symbol *create_symbol(int stream, const char *name, int type, int namespace)
345 {
346 struct token *token = built_in_token(stream, name);
347 struct symbol *sym = alloc_symbol(token->pos, type);
348
349 sym->ident = token->ident;
350 bind_symbol(sym, token->ident, namespace);
351 return sym;
352 }
353
354 static int evaluate_constant_p(struct expression *expr)
355 {
356 expr->ctype = &int_ctype;
357 return 1;
358 }
359
360 static void expand_constant_p(struct expression *expr)
361 {
362 struct expression *arg;
363 struct expression_list *arglist = expr->args;
364 int value = 1;
365
366 FOR_EACH_PTR (arglist, arg) {
367 if (arg->type != EXPR_VALUE && arg->type != EXPR_VALUE)
368 value = 0;
369 } END_FOR_EACH_PTR;
370
371 expr->type = EXPR_VALUE;
372 expr->value = value;
373 }
374
375 /*
376 * Type and storage class keywords need to have the symbols
377 * created for them, so that the parser can have enough semantic
378 * information to do parsing.
379 *
380 * "double" == "long float", "long double" == "long long float"
381 */
382 struct sym_init {
383 const char *name;
384 struct symbol *base_type;
385 unsigned int modifiers;
386 struct symbol_op *op;
387 } symbol_init_table[] = {
388 /* Storage class */
389 { "auto", NULL, MOD_AUTO },
390 { "register", NULL, MOD_REGISTER },
391 { "static", NULL, MOD_STATIC },
392 { "extern", NULL, MOD_EXTERN },
393
394 /* Type specifiers */
395 { "void", &void_ctype, 0 },
396 { "char", NULL, MOD_CHAR },
397 { "short", NULL, MOD_SHORT },
398 { "int", &int_type, 0 },
399 { "long", NULL, MOD_LONG },
400 { "float", &fp_type, 0 },
401 { "double", &fp_type, MOD_LONG },
402 { "signed", NULL, MOD_SIGNED },
403 { "__signed", NULL, MOD_SIGNED },
404 { "__signed__", NULL, MOD_SIGNED },
405 { "unsigned", NULL, MOD_UNSIGNED },
406 { "__label__", &label_type, MOD_LABEL | MOD_UNSIGNED },
407
408 /* Type qualifiers */
409 { "const", NULL, MOD_CONST },
410 { "__const", NULL, MOD_CONST },
411 { "__const__", NULL, MOD_CONST },
412 { "volatile", NULL, MOD_VOLATILE },
413 { "__volatile", NULL, MOD_VOLATILE },
414 { "__volatile__", NULL, MOD_VOLATILE },
415
416 /* Predeclared types */
417 { "__builtin_va_list", &int_type, 0 },
418
419 /* Typedef.. */
420 { "typedef", NULL, MOD_TYPEDEF },
421
422 /* Extended types */
423 { "typeof", NULL, MOD_TYPEOF },
424 { "__typeof", NULL, MOD_TYPEOF },
425 { "__typeof__", NULL, MOD_TYPEOF },
426
427 #if 0
428 { "attribute", NULL, MOD_ATTRIBUTE },
429 #endif
430 { "__attribute", NULL, MOD_ATTRIBUTE },
431 { "__attribute__", NULL, MOD_ATTRIBUTE },
432
433 { "struct", NULL, MOD_STRUCTOF },
434 { "union", NULL, MOD_UNIONOF },
435 { "enum", NULL, MOD_ENUMOF },
436
437 { "inline", NULL, MOD_INLINE },
438 { "__inline", NULL, MOD_INLINE },
439 { "__inline__", NULL, MOD_INLINE },
440
441 /* Ignored for now.. */
442 { "restrict", NULL, 0 },
443 { "__restrict", NULL, 0 },
444
445 { NULL, NULL, 0 }
446 };
447
448 struct symbol_op constant_p_op = {
449 .evaluate = evaluate_constant_p,
450 .expand = expand_constant_p
451 };
452
453 /*
454 * Builtin functions
455 */
456 static struct symbol builtin_fn_type = { .type = SYM_FN };
457 struct sym_init eval_init_table[] = {
458 { "__builtin_constant_p", &builtin_fn_type, MOD_TOPLEVEL, &constant_p_op },
459
460 { NULL, NULL, 0 }
461 };
462
463
464 /*
465 * Abstract types
466 */
467 struct symbol int_type,
468 fp_type,
469 label_type,
470 vector_type,
471 bad_type;
472
473 /*
474 * C types (ie actual instances that the abstract types
475 * can map onto)
476 */
477 struct symbol bool_ctype, void_ctype, type_ctype,
478 char_ctype, uchar_ctype,
479 short_ctype, ushort_ctype,
480 int_ctype, uint_ctype,
481 long_ctype, ulong_ctype,
482 llong_ctype, ullong_ctype,
483 float_ctype, double_ctype, ldouble_ctype,
484 string_ctype, ptr_ctype, incomplete_ctype;
485
486 struct ctype_declare {
487 struct symbol *ptr;
488 unsigned long modifiers;
489 int *bit_size;
490 int *maxalign;
491 struct symbol *base_type;
492 } ctype_declaration[] = {
493 { &bool_ctype, 0, &bits_in_int, &max_int_alignment, &int_type },
494 { &void_ctype, 0, NULL, NULL, NULL },
495 { &type_ctype, MOD_TYPE, NULL, NULL, NULL },
496 { &incomplete_ctype, 0, NULL, NULL, NULL },
497
498 { &char_ctype, MOD_SIGNED | MOD_CHAR, &bits_in_char, &max_int_alignment, &int_type },
499 { &uchar_ctype, MOD_UNSIGNED | MOD_CHAR, &bits_in_char, &max_int_alignment, &int_type },
500 { &short_ctype, MOD_SIGNED | MOD_SHORT, &bits_in_short, &max_int_alignment, &int_type },
501 { &ushort_ctype, MOD_UNSIGNED | MOD_SHORT, &bits_in_short, &max_int_alignment, &int_type },
502 { &int_ctype, MOD_SIGNED, &bits_in_int, &max_int_alignment, &int_type },
503 { &uint_ctype, MOD_UNSIGNED, &bits_in_int, &max_int_alignment, &int_type },
504 { &long_ctype, MOD_SIGNED | MOD_LONG, &bits_in_long, &max_int_alignment, &int_type },
505 { &ulong_ctype, MOD_UNSIGNED | MOD_LONG, &bits_in_long, &max_int_alignment, &int_type },
506 { &llong_ctype, MOD_SIGNED | MOD_LONG | MOD_LONGLONG, &bits_in_longlong, &max_int_alignment, &int_type },
507 { &ullong_ctype, MOD_UNSIGNED | MOD_LONG | MOD_LONGLONG, &bits_in_longlong, &max_int_alignment, &int_type },
508
509 { &float_ctype, 0, &bits_in_float, &max_fp_alignment, &fp_type },
510 { &double_ctype, MOD_LONG, &bits_in_double, &max_fp_alignment, &fp_type },
511 { &ldouble_ctype,MOD_LONG | MOD_LONGLONG, &bits_in_longdouble, &max_fp_alignment, &fp_type },
512
513 { &string_ctype, 0, &bits_in_pointer, &pointer_alignment, &char_ctype },
514 { &ptr_ctype, 0, &bits_in_pointer, &pointer_alignment, &void_ctype },
515 { NULL, }
516 };
517
518
519 #define __INIT_IDENT(str) { .len = sizeof(str)-1, .name = str }
520 #define __IDENT(n,str) \
521 struct ident n ## _ident = __INIT_IDENT(str)
522 #define IDENT(n) __IDENT(n, #n)
523
524 IDENT(struct); IDENT(union); IDENT(enum);
525 IDENT(sizeof);
526 IDENT(alignof); IDENT(__alignof); IDENT(__alignof__);
527 IDENT(if); IDENT(else); IDENT(return);
528 IDENT(switch); IDENT(case); IDENT(default);
529 IDENT(break); IDENT(continue);
530 IDENT(for); IDENT(while); IDENT(do); IDENT(goto);
531
532 IDENT(__asm__); IDENT(__asm); IDENT(asm);
533 IDENT(__volatile__); IDENT(__volatile); IDENT(volatile);
534 IDENT(__attribute__); IDENT(__attribute);
535 IDENT(defined);
536
537 __IDENT(pragma, "__pragma__");
538
539 struct ident __VA_ARGS___ident = __INIT_IDENT("__VA_ARGS__");
540 struct ident __LINE___ident = __INIT_IDENT("__LINE__");
541 struct ident __FILE___ident = __INIT_IDENT("__FILE__");
542
543 void init_symbols(void)
544 {
545 int stream = init_stream("builtin", -1);
546 struct sym_init *ptr;
547
548 hash_ident(&sizeof_ident);
549 hash_ident(&alignof_ident);
550 hash_ident(&__alignof_ident);
551 hash_ident(&__alignof___ident);
552 hash_ident(&if_ident);
553 hash_ident(&else_ident);
554 hash_ident(&return_ident);
555 hash_ident(&switch_ident);
556 hash_ident(&case_ident);
557 hash_ident(&default_ident);
558 hash_ident(&break_ident);
559 hash_ident(&continue_ident);
560 hash_ident(&for_ident);
561 hash_ident(&while_ident);
562 hash_ident(&do_ident);
563 hash_ident(&goto_ident);
564 hash_ident(&__attribute___ident);
565 hash_ident(&__attribute_ident);
566 hash_ident(&__asm___ident);
567 hash_ident(&__asm_ident);
568 hash_ident(&asm_ident);
569 hash_ident(&__volatile___ident);
570 hash_ident(&__volatile_ident);
571 hash_ident(&volatile_ident);
572 hash_ident(&defined_ident);
573 hash_ident(&__LINE___ident);
574 hash_ident(&__FILE___ident);
575 hash_ident(&__VA_ARGS___ident);
576 hash_ident(&pragma_ident);
577 for (ptr = symbol_init_table; ptr->name; ptr++) {
578 struct symbol *sym;
579 sym = create_symbol(stream, ptr->name, SYM_NODE, NS_TYPEDEF);
580 sym->ctype.base_type = ptr->base_type;
581 sym->ctype.modifiers = ptr->modifiers;
582 }
583
584 builtin_fn_type.variadic = 1;
585 for (ptr = eval_init_table; ptr->name; ptr++) {
586 struct symbol *sym;
587 sym = create_symbol(stream, ptr->name, SYM_NODE, NS_SYMBOL);
588 sym->ctype.base_type = ptr->base_type;
589 sym->ctype.modifiers = ptr->modifiers;
590 sym->op = ptr->op;
591 }
592 }
593
594 void init_ctype(void)
595 {
596 struct ctype_declare *ctype;
597
598 ptr_ctype.type = SYM_PTR;
599 string_ctype.type = SYM_PTR;
600 for (ctype = ctype_declaration ; ctype->ptr; ctype++) {
601 struct symbol *sym = ctype->ptr;
602 unsigned long bit_size = ctype->bit_size ? *ctype->bit_size : -1;
603 unsigned long maxalign = ctype->maxalign ? *ctype->maxalign : 0;
604 unsigned long alignment = bit_size >> 3;
605
606 if (alignment > maxalign)
607 alignment = maxalign;
608 sym->bit_size = bit_size;
609 sym->ctype.alignment = alignment;
610 sym->ctype.base_type = ctype->base_type;
611 sym->ctype.modifiers = ctype->modifiers;
612 }
613 }
Static analysis for C