symbol.c

   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                         if (base->type == SYM_NODE)
 247                                 base = base->ctype.base_type;
 248                         sym->type = SYM_NODE;
 249                         sym->ctype.base_type = base;
 250                 }
 251                 break;
 252         }
 253         default:
 254                 break;
 255         }
 256
 257         /* SYM_NODE - figure out what the type of the node was.. */
 258         base_type = sym->ctype.base_type;
 259         modifiers = sym->ctype.modifiers;
 260
 261         bit_size = 0;
 262         alignment = 0;
 263         if (base_type) {
 264                 base_type = examine_symbol_type(base_type);
 265                 sym->ctype.base_type = base_type;
 266                 if (base_type && base_type->type == SYM_NODE)
 267                         merge_type(sym, base_type);
 268
 269                 bit_size = base_type->bit_size;
 270                 alignment = base_type->ctype.alignment;
 271                 if (base_type->fieldwidth)
 272                         sym->fieldwidth = base_type->fieldwidth;
 273         }
 274
 275         if (!sym->ctype.alignment)
 276                 sym->ctype.alignment = alignment;
 277         sym->bit_size = bit_size;
 278         return sym;
 279 }
 280
 281 void check_declaration(struct symbol *sym)
 282 {
 283         struct symbol *next = sym;
 284
 285         while ((next = next->next_id) != NULL) {
 286                 if (next->namespace != sym->namespace)
 287                         continue;
 288                 if (sym->scope == next->scope) {
 289                         sym->same_symbol = next;
 290                         return;
 291                 }
 292                 if (sym->ctype.modifiers & next->ctype.modifiers & MOD_EXTERN) {
 293                         sym->same_symbol = next;
 294                         return;
 295                 }
 296 #if 0
 297                 // This may make sense from a warning standpoint:
 298                 //  consider top-level symbols to clash with everything
 299                 //  (but the scoping rules will mean that we actually
 300                 //  _use_ the innermost version)
 301                 if (toplevel(next->scope)) {
 302                         sym->same_symbol = next;
 303                         return;
 304                 }
 305 #endif
 306         }
 307 }
 308
 309 void bind_symbol(struct symbol *sym, struct ident *ident, enum namespace ns)
 310 {
 311         struct scope *scope;
 312         if (sym->id_list) {
 313                 warn(sym->pos, "internal error: symbol type already bound");
 314                 return;
 315         }
 316         sym->namespace = ns;
 317         sym->next_id = ident->symbols;
 318         ident->symbols = sym;
 319         sym->id_list = &ident->symbols;
 320
 321         scope = block_scope;
 322         if (ns != NS_TYPEDEF && toplevel(scope)) {
 323                 sym->ctype.modifiers |= MOD_TOPLEVEL | MOD_ADDRESSABLE;
 324                 if (sym->ctype.modifiers & MOD_STATIC)
 325                         scope = file_scope;
 326         }
 327         if (ns == NS_LABEL)
 328                 scope = function_scope;
 329         bind_scope(sym, scope);
 330 }
 331
 332 static struct symbol *create_symbol(int stream, const char *name, int type, int namespace)
 333 {
 334         struct token *token = built_in_token(stream, name);
 335         struct symbol *sym = alloc_symbol(token->pos, type);
 336
 337         sym->ident = token->ident;
 338         bind_symbol(sym, token->ident, namespace);
 339         return sym;
 340 }
 341
 342 static int evaluate_constant_p(struct expression *expr)
 343 {
 344         expr->ctype = &int_ctype;
 345         return 1;
 346 }
 347
 348 static int expand_constant_p(struct expression *expr)
 349 {
 350         struct expression *arg;
 351         struct expression_list *arglist = expr->args;
 352         int value = 1;
 353
 354         FOR_EACH_PTR (arglist, arg) {
 355                 if (arg->type != EXPR_VALUE && arg->type != EXPR_VALUE)
 356                         value = 0;
 357         } END_FOR_EACH_PTR;
 358
 359         expr->type = EXPR_VALUE;
 360         expr->value = value;
 361         return 0;
 362 }
 363
 364 /*
 365  * Type and storage class keywords need to have the symbols
 366  * created for them, so that the parser can have enough semantic
 367  * information to do parsing.
 368  *
 369  * "double" == "long float", "long double" == "long long float"
 370  */
 371 struct sym_init {
 372         const char *name;
 373         struct symbol *base_type;
 374         unsigned int modifiers;
 375         struct symbol_op *op;
 376 } symbol_init_table[] = {
 377         /* Storage class */
 378         { "auto",       NULL,           MOD_AUTO },
 379         { "register",   NULL,           MOD_REGISTER },
 380         { "static",     NULL,           MOD_STATIC },
 381         { "extern",     NULL,           MOD_EXTERN },
 382
 383         /* Type specifiers */
 384         { "void",       &void_ctype,    0 },
 385         { "char",       NULL,           MOD_CHAR },
 386         { "short",      NULL,           MOD_SHORT },
 387         { "int",        &int_type,      0 },
 388         { "long",       NULL,           MOD_LONG },
 389         { "float",      &fp_type,       0 },
 390         { "double",     &fp_type,       MOD_LONG },
 391         { "signed",     NULL,           MOD_SIGNED },
 392         { "__signed",   NULL,           MOD_SIGNED },
 393         { "__signed__", NULL,           MOD_SIGNED },
 394         { "unsigned",   NULL,           MOD_UNSIGNED },
 395         { "__label__",  &label_type,    MOD_LABEL | MOD_UNSIGNED },
 396
 397         /* Type qualifiers */
 398         { "const",      NULL,           MOD_CONST },
 399         { "__const",    NULL,           MOD_CONST },
 400         { "__const__",  NULL,           MOD_CONST },
 401         { "volatile",   NULL,           MOD_VOLATILE },
 402         { "__volatile", NULL,           MOD_VOLATILE },
 403         { "__volatile__", NULL,         MOD_VOLATILE },
 404
 405         /* Predeclared types */
 406         { "__builtin_va_list", &int_type, 0 },
 407
 408         /* Typedef.. */
 409         { "typedef",    NULL,           MOD_TYPEDEF },
 410
 411         /* Extended types */
 412         { "typeof",     NULL,           MOD_TYPEOF },
 413         { "__typeof",   NULL,           MOD_TYPEOF },
 414         { "__typeof__", NULL,           MOD_TYPEOF },
 415
 416 #if 0
 417         { "attribute",  NULL,           MOD_ATTRIBUTE },
 418 #endif
 419         { "__attribute", NULL,          MOD_ATTRIBUTE },
 420         { "__attribute__", NULL,        MOD_ATTRIBUTE },
 421
 422         { "struct",     NULL,           MOD_STRUCTOF },
 423         { "union",      NULL,           MOD_UNIONOF },
 424         { "enum",       NULL,           MOD_ENUMOF },
 425
 426         { "inline",     NULL,           MOD_INLINE },
 427         { "__inline",   NULL,           MOD_INLINE },
 428         { "__inline__", NULL,           MOD_INLINE },
 429
 430         /* Ignored for now.. */
 431         { "restrict",   NULL,           0 },
 432         { "__restrict", NULL,           0 },
 433
 434         { NULL,         NULL,           0 }
 435 };
 436
 437 struct symbol_op constant_p_op = {
 438         .evaluate = evaluate_constant_p,
 439         .expand = expand_constant_p
 440 };
 441
 442 /*
 443  * Builtin functions
 444  */
 445 static struct symbol builtin_fn_type = { .type = SYM_FN };
 446 struct sym_init eval_init_table[] = {
 447         { "__builtin_constant_p", &builtin_fn_type, MOD_TOPLEVEL, &constant_p_op },
 448
 449         { NULL,         NULL,           0 }
 450 };
 451
 452
 453 /*
 454  * Abstract types
 455  */
 456 struct symbol   int_type,
 457                 fp_type,
 458                 label_type,
 459                 vector_type,
 460                 bad_type;
 461
 462 /*
 463  * C types (ie actual instances that the abstract types
 464  * can map onto)
 465  */
 466 struct symbol   bool_ctype, void_ctype, type_ctype,
 467                 char_ctype, uchar_ctype,
 468                 short_ctype, ushort_ctype,
 469                 int_ctype, uint_ctype,
 470                 long_ctype, ulong_ctype,
 471                 llong_ctype, ullong_ctype,
 472                 float_ctype, double_ctype, ldouble_ctype,
 473                 string_ctype, ptr_ctype, lazy_ptr_ctype,
 474                 incomplete_ctype;
 475
 476 struct ctype_declare {
 477         struct symbol *ptr;
 478         unsigned long modifiers;
 479         int *bit_size;
 480         int *maxalign;
 481         struct symbol *base_type;
 482 } ctype_declaration[] = {
 483         { &bool_ctype,   0,                                       &bits_in_int,         &max_int_alignment, &int_type },
 484         { &void_ctype,   0,                                       NULL,                 NULL,                   NULL },
 485         { &type_ctype,   MOD_TYPE,                                NULL,                 NULL,                   NULL },
 486         { &incomplete_ctype, 0,                                   NULL,                 NULL,                   NULL },
 487
 488         { &char_ctype,   MOD_SIGNED | MOD_CHAR,                   &bits_in_char,        &max_int_alignment, &int_type },
 489         { &uchar_ctype,  MOD_UNSIGNED | MOD_CHAR,                 &bits_in_char,        &max_int_alignment, &int_type },
 490         { &short_ctype,  MOD_SIGNED | MOD_SHORT,                  &bits_in_short,       &max_int_alignment, &int_type },
 491         { &ushort_ctype, MOD_UNSIGNED | MOD_SHORT,                &bits_in_short,       &max_int_alignment, &int_type },
 492         { &int_ctype,    MOD_SIGNED,                              &bits_in_int,         &max_int_alignment, &int_type },
 493         { &uint_ctype,   MOD_UNSIGNED,                            &bits_in_int,         &max_int_alignment, &int_type },
 494         { &long_ctype,   MOD_SIGNED | MOD_LONG,                   &bits_in_long,        &max_int_alignment, &int_type },
 495         { &ulong_ctype,  MOD_UNSIGNED | MOD_LONG,                 &bits_in_long,        &max_int_alignment, &int_type },
 496         { &llong_ctype,  MOD_SIGNED | MOD_LONG | MOD_LONGLONG,    &bits_in_longlong,    &max_int_alignment, &int_type },
 497         { &ullong_ctype, MOD_UNSIGNED | MOD_LONG | MOD_LONGLONG,  &bits_in_longlong,    &max_int_alignment, &int_type },
 498
 499         { &float_ctype,  0,                                       &bits_in_float,       &max_fp_alignment, &fp_type },
 500         { &double_ctype, MOD_LONG,                                &bits_in_double,      &max_fp_alignment, &fp_type },
 501         { &ldouble_ctype,MOD_LONG | MOD_LONGLONG,                 &bits_in_longdouble,  &max_fp_alignment, &fp_type },
 502
 503         { &string_ctype,            0,  &bits_in_pointer, &pointer_alignment, &char_ctype },
 504         { &ptr_ctype,               0,  &bits_in_pointer, &pointer_alignment, &void_ctype },
 505         { &lazy_ptr_ctype,          0,  &bits_in_pointer, &pointer_alignment, &void_ctype },
 506         { NULL, }
 507 };
 508
 509
 510 #define __INIT_IDENT(str) { .len = sizeof(str)-1, .name = str }
 511 #define __IDENT(n,str) \
 512         struct ident n ## _ident = __INIT_IDENT(str)
 513 #define IDENT(n) __IDENT(n, #n)
 514
 515 IDENT(struct); IDENT(union); IDENT(enum);
 516 IDENT(sizeof);
 517 IDENT(alignof); IDENT(__alignof); IDENT(__alignof__);
 518 IDENT(if); IDENT(else); IDENT(return);
 519 IDENT(switch); IDENT(case); IDENT(default);
 520 IDENT(break); IDENT(continue);
 521 IDENT(for); IDENT(while); IDENT(do); IDENT(goto);
 522
 523 IDENT(__asm__); IDENT(__asm); IDENT(asm);
 524 IDENT(__volatile__); IDENT(__volatile); IDENT(volatile);
 525 IDENT(__attribute__); IDENT(__attribute);
 526 IDENT(defined);
 527
 528 __IDENT(pragma, "__pragma__");
 529
 530 struct ident __VA_ARGS___ident = __INIT_IDENT("__VA_ARGS__");
 531 struct ident __LINE___ident = __INIT_IDENT("__LINE__");
 532 struct ident __FILE___ident = __INIT_IDENT("__FILE__");
 533
 534 void init_symbols(void)
 535 {
 536         int stream = init_stream("builtin", -1);
 537         struct sym_init *ptr;
 538
 539         hash_ident(&sizeof_ident);
 540         hash_ident(&alignof_ident);
 541         hash_ident(&__alignof_ident);
 542         hash_ident(&__alignof___ident);
 543         hash_ident(&if_ident);
 544         hash_ident(&else_ident);
 545         hash_ident(&return_ident);
 546         hash_ident(&switch_ident);
 547         hash_ident(&case_ident);
 548         hash_ident(&default_ident);
 549         hash_ident(&break_ident);
 550         hash_ident(&continue_ident);
 551         hash_ident(&for_ident);
 552         hash_ident(&while_ident);
 553         hash_ident(&do_ident);
 554         hash_ident(&goto_ident);
 555         hash_ident(&__attribute___ident);
 556         hash_ident(&__attribute_ident);
 557         hash_ident(&__asm___ident);
 558         hash_ident(&__asm_ident);
 559         hash_ident(&asm_ident);
 560         hash_ident(&__volatile___ident);
 561         hash_ident(&__volatile_ident);
 562         hash_ident(&volatile_ident);
 563         hash_ident(&defined_ident);
 564         hash_ident(&__LINE___ident);
 565         hash_ident(&__FILE___ident);
 566         hash_ident(&__VA_ARGS___ident);
 567         hash_ident(&pragma_ident);
 568         for (ptr = symbol_init_table; ptr->name; ptr++) {
 569                 struct symbol *sym;
 570                 sym = create_symbol(stream, ptr->name, SYM_NODE, NS_TYPEDEF);
 571                 sym->ctype.base_type = ptr->base_type;
 572                 sym->ctype.modifiers = ptr->modifiers;
 573         }
 574
 575         builtin_fn_type.variadic = 1;
 576         for (ptr = eval_init_table; ptr->name; ptr++) {
 577                 struct symbol *sym;
 578                 sym = create_symbol(stream, ptr->name, SYM_NODE, NS_SYMBOL);
 579                 sym->ctype.base_type = ptr->base_type;
 580                 sym->ctype.modifiers = ptr->modifiers;
 581                 sym->op = ptr->op;
 582         }
 583 }
 584
 585 void init_ctype(void)
 586 {
 587         struct ctype_declare *ctype;
 588
 589         ptr_ctype.type = SYM_PTR;
 590         lazy_ptr_ctype.type = SYM_PTR;
 591         string_ctype.type = SYM_PTR;
 592         for (ctype = ctype_declaration ; ctype->ptr; ctype++) {
 593                 struct symbol *sym = ctype->ptr;
 594                 unsigned long bit_size = ctype->bit_size ? *ctype->bit_size : -1;
 595                 unsigned long maxalign = ctype->maxalign ? *ctype->maxalign : 0;
 596                 unsigned long alignment = bit_size >> 3;
 597
 598                 if (alignment > maxalign)
 599                         alignment = maxalign;
 600                 sym->bit_size = bit_size;
 601                 sym->ctype.alignment = alignment;
 602                 sym->ctype.base_type = ctype->base_type;
 603                 sym->ctype.modifiers = ctype->modifiers;
 604         }
 605 }