?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Clean up address-of evaluation, and mark symbols so evaluated
[smatch.git] / symbol.c
blobf1a0e6a966d4b6c2c7c173a33b6cbe96d0ad4d49
1 /*
2 * Symbol lookup and handling.
3 *
4 * Copyright (C) 2003 Transmeta Corp, all rights reserved.
5 */
6 #include <stdlib.h>
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10
11 #include "lib.h"
12 #include "token.h"
13 #include "parse.h"
14 #include "symbol.h"
15 #include "scope.h"
16 #include "expression.h"
17
18 #include "target.h"
19
20 struct symbol *lookup_symbol(struct ident *ident, enum namespace ns)
21 {
22 struct symbol *sym;
23
24 for (sym = ident->symbols; sym; sym = sym->next_id) {
25 if (sym->namespace == ns)
26 return sym;
27 }
28 return sym;
29 }
30
31 struct symbol *alloc_symbol(struct position pos, int type)
32 {
33 struct symbol *sym = __alloc_symbol(0);
34 sym->type = type;
35 sym->pos = pos;
36 return sym;
37 }
38
39 struct struct_union_info {
40 unsigned long max_align;
41 unsigned long bit_size;
42 };
43
44 /*
45 * Unions are easy to lay out ;)
46 */
47 static void lay_out_union(struct symbol *sym, void *_info, int flags)
48 {
49 struct struct_union_info *info = _info;
50
51 examine_symbol_type(sym);
52 if (sym->ctype.alignment > info->max_align)
53 info->max_align = sym->ctype.alignment;
54 if (sym->bit_size > info->bit_size)
55 info->bit_size = sym->bit_size;
56
57 sym->offset = 0;
58 }
59
60 /*
61 * Structures are a bit more interesting to lay out
62 */
63 static void lay_out_struct(struct symbol *sym, void *_info, int flags)
64 {
65 struct struct_union_info *info = _info;
66 unsigned long bit_size, base_size;
67 unsigned long align_bit_mask;
68
69 examine_symbol_type(sym);
70 if (sym->ctype.alignment > info->max_align)
71 info->max_align = sym->ctype.alignment;
72
73 bit_size = info->bit_size;
74 base_size = sym->bit_size;
75 align_bit_mask = (sym->ctype.alignment << 3) - 1;
76
77 /*
78 * Bitfields have some very special rules..
79 */
80 if (sym->fieldwidth) {
81 unsigned long bit_offset = bit_size & align_bit_mask;
82
83 if (bit_offset + sym->fieldwidth > base_size) {
84 bit_size = (bit_size + align_bit_mask) & ~align_bit_mask;
85 bit_offset = 0;
86 }
87 sym->offset = (bit_size - bit_offset) >> 3;
88 sym->bit_offset = bit_offset;
89 info->bit_size = bit_size + sym->fieldwidth;
90 return;
91 }
92
93 /*
94 * Otherwise, just align it right and add it up..
95 */
96 bit_size = (bit_size + align_bit_mask) & ~align_bit_mask;
97 sym->offset = bit_size >> 3;
98
99 info->bit_size = bit_size + sym->bit_size;
100 }
101
102 static void examine_struct_union_type(struct symbol *sym, int advance)
103 {
104 struct struct_union_info info = { 1, 0 };
105 unsigned long bit_size, bit_align;
106 void (*fn)(struct symbol *, void *, int);
107
108 fn = advance ? lay_out_struct : lay_out_union;
109 symbol_iterate(sym->symbol_list, fn, &info);
110
111 if (!sym->ctype.alignment)
112 sym->ctype.alignment = info.max_align;
113 bit_size = info.bit_size;
114 bit_align = (sym->ctype.alignment << 3)-1;
115 bit_size = (bit_size + bit_align) & ~bit_align;
116 sym->bit_size = bit_size;
117 }
118
119 static void examine_array_type(struct symbol *sym)
120 {
121 struct symbol *base_type = sym->ctype.base_type;
122 unsigned long bit_size, alignment;
123
124 if (!base_type)
125 return;
126 examine_symbol_type(base_type);
127 bit_size = base_type->bit_size * sym->array_size;
128 if (sym->array_size < 0)
129 bit_size = -1;
130 alignment = base_type->ctype.alignment;
131 if (!sym->ctype.alignment)
132 sym->ctype.alignment = alignment;
133 sym->bit_size = bit_size;
134 }
135
136 static void examine_bitfield_type(struct symbol *sym)
137 {
138 struct symbol *base_type = sym->ctype.base_type;
139 unsigned long bit_size, alignment;
140
141 if (!base_type)
142 return;
143 examine_symbol_type(base_type);
144 bit_size = base_type->bit_size;
145 if (sym->fieldwidth > bit_size) {
146 warn(sym->pos, "impossible field-width for this type");
147 sym->fieldwidth = bit_size;
148 }
149 alignment = base_type->ctype.alignment;
150 if (!sym->ctype.alignment)
151 sym->ctype.alignment = alignment;
152 sym->bit_size = bit_size;
153 }
154
155 /*
156 * Fill in type size and alignment information for
157 * regular SYM_TYPE things.
158 */
159 struct symbol *examine_symbol_type(struct symbol * sym)
160 {
161 unsigned int bit_size, alignment;
162 struct symbol *base_type;
163 unsigned long modifiers;
164
165 if (!sym)
166 return sym;
167
168 /* Already done? */
169 if (sym->bit_size)
170 return sym;
171
172 switch (sym->type) {
173 case SYM_ARRAY:
174 examine_array_type(sym);
175 return sym;
176 case SYM_STRUCT:
177 examine_struct_union_type(sym, 1);
178 return sym;
179 case SYM_UNION:
180 examine_struct_union_type(sym, 0);
181 return sym;
182 case SYM_PTR:
183 if (!sym->bit_size)
184 sym->bit_size = BITS_IN_POINTER;
185 if (!sym->ctype.alignment)
186 sym->ctype.alignment = POINTER_ALIGNMENT;
187 sym->ctype.base_type = examine_symbol_type(sym->ctype.base_type);
188 return sym;
189 case SYM_ENUM:
190 if (!sym->bit_size)
191 sym->bit_size = BITS_IN_ENUM;
192 if (!sym->ctype.alignment)
193 sym->ctype.alignment = ENUM_ALIGNMENT;
194 return sym;
195 case SYM_BITFIELD:
196 examine_bitfield_type(sym);
197 return sym;
198 case SYM_BASETYPE:
199 /* Size and alignment had better already be set up */
200 return sym;
201 case SYM_TYPEOF: {
202 struct symbol *base = evaluate_expression(sym->initializer);
203 if (base)
204 return base;
205 break;
206 }
207 default:
208 break;
209 }
210
211 /* SYM_NODE - figure out what the type of the node was.. */
212 base_type = sym->ctype.base_type;
213 modifiers = sym->ctype.modifiers;
214
215 if (base_type) {
216 base_type = examine_symbol_type(base_type);
217 sym->ctype.base_type = base_type;
218
219 bit_size = base_type->bit_size;
220 alignment = base_type->ctype.alignment;
221 if (base_type->fieldwidth)
222 sym->fieldwidth = base_type->fieldwidth;
223 } else
224 bit_size = 0;
225
226 if (!sym->ctype.alignment)
227 sym->ctype.alignment = alignment;
228 sym->bit_size = bit_size;
229 return sym;
230 }
231
232 void bind_symbol(struct symbol *sym, struct ident *ident, enum namespace ns)
233 {
234 struct scope *scope;
235 if (sym->id_list) {
236 warn(sym->pos, "internal error: symbol type already bound");
237 return;
238 }
239 sym->namespace = ns;
240 sym->next_id = ident->symbols;
241 ident->symbols = sym;
242 sym->id_list = &ident->symbols;
243
244 scope = block_scope;
245 if (toplevel(scope)) {
246 if (sym->ctype.modifiers & MOD_STATIC)
247 scope = file_scope;
248 }
249 if (ns == NS_LABEL)
250 scope = function_scope;
251 bind_scope(sym, scope);
252 }
253
254 struct symbol *create_symbol(int stream, const char *name, int type)
255 {
256 struct token *token = built_in_token(stream, name);
257 struct symbol *sym = alloc_symbol(token->pos, type);
258 bind_symbol(sym, token->ident, NS_TYPEDEF);
259 return sym;
260 }
261
262 /*
263 * Type and storage class keywords need to have the symbols
264 * created for them, so that the parser can have enough semantic
265 * information to do parsing.
266 *
267 * "double" == "long float", "long double" == "long long float"
268 */
269 struct sym_init {
270 const char *name;
271 struct symbol *base_type;
272 unsigned int modifiers;
273 } symbol_init_table[] = {
274 /* Storage class */
275 { "auto", NULL, MOD_AUTO },
276 { "register", NULL, MOD_REGISTER },
277 { "static", NULL, MOD_STATIC },
278 { "extern", NULL, MOD_EXTERN },
279
280 /* Type specifiers */
281 { "void", &void_ctype, 0 },
282 { "char", &int_type, MOD_CHAR },
283 { "short", &int_type, MOD_SHORT },
284 { "int", &int_type, 0 },
285 { "long", NULL, MOD_LONG },
286 { "float", &fp_type, 0 },
287 { "double", &fp_type, MOD_LONG },
288 { "signed", &int_type, MOD_SIGNED },
289 { "__signed", &int_type, MOD_SIGNED },
290 { "__signed__", &int_type, MOD_SIGNED },
291 { "unsigned", &int_type, MOD_UNSIGNED },
292
293 /* Type qualifiers */
294 { "const", NULL, MOD_CONST },
295 { "__const", NULL, MOD_CONST },
296 { "__const__", NULL, MOD_CONST },
297 { "volatile", NULL, MOD_VOLATILE },
298
299 /* Predeclared types */
300 { "__builtin_va_list", &int_type, 0 },
301
302 /* Typedef.. */
303 { "typedef", NULL, MOD_TYPEDEF },
304
305 /* Extended types */
306 { "typeof", NULL, MOD_TYPEOF },
307 { "__typeof", NULL, MOD_TYPEOF },
308 { "__typeof__", NULL, MOD_TYPEOF },
309
310 #if 0
311 { "attribute", NULL, MOD_ATTRIBUTE },
312 { "__attribute", NULL, MOD_ATTRIBUTE },
313 #endif
314 { "__attribute__", NULL, MOD_ATTRIBUTE },
315
316 { "struct", NULL, MOD_STRUCTOF },
317 { "union", NULL, MOD_UNIONOF },
318 { "enum", NULL, MOD_ENUMOF },
319
320 /* Ignored for now.. */
321 { "inline", NULL, MOD_INLINE },
322 { "__inline", NULL, MOD_INLINE },
323 { "__inline__", NULL, MOD_INLINE },
324 { "restrict", NULL, 0 },
325 { "__restrict", NULL, 0 },
326
327 { NULL, NULL, 0 }
328 };
329
330 /*
331 * Abstract types
332 */
333 struct symbol int_type,
334 fp_type,
335 vector_type,
336 bad_type;
337
338 /*
339 * C types (ie actual instances that the abstract types
340 * can map onto)
341 */
342 struct symbol bool_ctype, void_ctype,
343 char_ctype, uchar_ctype,
344 short_ctype, ushort_ctype,
345 int_ctype, uint_ctype,
346 long_ctype, ulong_ctype,
347 llong_ctype, ullong_ctype,
348 float_ctype, double_ctype, ldouble_ctype,
349 string_ctype, ptr_ctype;
350
351 struct ctype_declare {
352 struct symbol *ptr;
353 unsigned long modifiers;
354 unsigned long bit_size;
355 unsigned long maxalign;
356 struct symbol *base_type;
357 } ctype_declaration[] = {
358 { &bool_ctype, 0, BITS_IN_INT, MAX_INT_ALIGNMENT, &int_type },
359 { &void_ctype, 0, -1, 0, &void_ctype },
360
361 { &char_ctype, MOD_SIGNED | MOD_CHAR, BITS_IN_CHAR, MAX_INT_ALIGNMENT, &int_type },
362 { &uchar_ctype, MOD_UNSIGNED | MOD_CHAR, BITS_IN_CHAR, MAX_INT_ALIGNMENT, &int_type },
363 { &short_ctype, MOD_SIGNED | MOD_SHORT, BITS_IN_SHORT, MAX_INT_ALIGNMENT, &int_type },
364 { &ushort_ctype, MOD_UNSIGNED | MOD_SHORT, BITS_IN_SHORT, MAX_INT_ALIGNMENT, &int_type },
365 { &int_ctype, MOD_SIGNED, BITS_IN_INT, MAX_INT_ALIGNMENT, &int_type },
366 { &uint_ctype, MOD_UNSIGNED, BITS_IN_INT, MAX_INT_ALIGNMENT, &int_type },
367 { &long_ctype, MOD_SIGNED | MOD_LONG, BITS_IN_LONG, MAX_INT_ALIGNMENT, &int_type },
368 { &ulong_ctype, MOD_UNSIGNED | MOD_LONG, BITS_IN_LONG, MAX_INT_ALIGNMENT, &int_type },
369 { &llong_ctype, MOD_SIGNED | MOD_LONG | MOD_LONGLONG, BITS_IN_LONGLONG, MAX_INT_ALIGNMENT, &int_type },
370 { &ullong_ctype, MOD_UNSIGNED | MOD_LONG | MOD_LONGLONG, BITS_IN_LONGLONG, MAX_INT_ALIGNMENT, &int_type },
371
372 { &float_ctype, 0, BITS_IN_FLOAT, MAX_FP_ALIGNMENT, &fp_type },
373 { &double_ctype, MOD_LONG, BITS_IN_DOUBLE, MAX_FP_ALIGNMENT, &fp_type },
374 { &ldouble_ctype,MOD_LONG | MOD_LONGLONG, BITS_IN_LONGDOUBLE,MAX_FP_ALIGNMENT, &fp_type },
375
376 { &string_ctype, 0, BITS_IN_POINTER, POINTER_ALIGNMENT, &char_ctype },
377 { &ptr_ctype, 0, BITS_IN_POINTER, POINTER_ALIGNMENT, &void_ctype },
378 { NULL, }
379 };
380
381
382 #define __IDENT(n,str) \
383 struct ident n ## _ident = { len: sizeof(str)-1, name: str }
384 #define IDENT(n) __IDENT(n, #n)
385
386 IDENT(struct); IDENT(union); IDENT(enum);
387 IDENT(sizeof);
388 IDENT(alignof); IDENT(__alignof); IDENT(__alignof__);
389 IDENT(if); IDENT(else); IDENT(return);
390 IDENT(switch); IDENT(case); IDENT(default);
391 IDENT(break); IDENT(continue);
392 IDENT(for); IDENT(while); IDENT(do); IDENT(goto);
393
394 IDENT(__asm__); IDENT(__asm); IDENT(asm);
395 IDENT(__volatile__); IDENT(__volatile); IDENT(volatile);
396 IDENT(__attribute__); IDENT(__attribute);
397
398 void init_symbols(void)
399 {
400 int stream = init_stream("builtin", -1);
401 struct sym_init *ptr;
402 struct ctype_declare *ctype;
403
404 hash_ident(&sizeof_ident);
405 hash_ident(&alignof_ident);
406 hash_ident(&__alignof_ident);
407 hash_ident(&__alignof___ident);
408 hash_ident(&if_ident);
409 hash_ident(&else_ident);
410 hash_ident(&return_ident);
411 hash_ident(&switch_ident);
412 hash_ident(&case_ident);
413 hash_ident(&default_ident);
414 hash_ident(&break_ident);
415 hash_ident(&continue_ident);
416 hash_ident(&for_ident);
417 hash_ident(&while_ident);
418 hash_ident(&do_ident);
419 hash_ident(&goto_ident);
420 hash_ident(&__attribute___ident);
421 hash_ident(&__attribute_ident);
422 hash_ident(&__asm___ident);
423 hash_ident(&__asm_ident);
424 hash_ident(&asm_ident);
425 hash_ident(&__volatile___ident);
426 hash_ident(&__volatile_ident);
427 hash_ident(&volatile_ident);
428 for (ptr = symbol_init_table; ptr->name; ptr++) {
429 struct symbol *sym;
430 sym = create_symbol(stream, ptr->name, SYM_NODE);
431 sym->ctype.base_type = ptr->base_type;
432 sym->ctype.modifiers = ptr->modifiers;
433 }
434
435 ptr_ctype.type = SYM_PTR;
436 string_ctype.type = SYM_PTR;
437 for (ctype = ctype_declaration ; ctype->ptr; ctype++) {
438 struct symbol *sym = ctype->ptr;
439 unsigned long bit_size = ctype->bit_size;
440 unsigned long alignment = bit_size >> 3;
441
442 if (alignment > ctype->maxalign)
443 alignment = ctype->maxalign;
444 sym->bit_size = bit_size;
445 sym->ctype.alignment = alignment;
446 sym->ctype.base_type = ctype->base_type;
447 sym->ctype.modifiers = ctype->modifiers;
448 }
449 }
Static analysis for C