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         int is_signed;
 165
 166         if (!base_type)
 167                 return;
 168         examine_symbol_type(base_type);
 169         bit_size = base_type->bit_size;
 170         if (sym->fieldwidth > bit_size) {
 171                 warn(sym->pos, "impossible field-width, %d, for this type",
 172                      sym->fieldwidth);
 173                 sym->fieldwidth = bit_size;
 174         }
 175
 176         is_signed = !(base_type->ctype.modifiers & MOD_UNSIGNED);
 177         if (sym->fieldwidth == 1 && is_signed) {
 178                 // Valid values are either {-1;0} or {0}, depending on integer
 179                 // representation.  The latter makes for very efficient code...
 180                 warn(sym->pos, "dubious one-bit signed bitfield");
 181         }
 182         alignment = base_type->ctype.alignment;
 183         if (!sym->ctype.alignment)
 184                 sym->ctype.alignment = alignment;
 185         sym->bit_size = bit_size;
 186 }
 187
 188 /*
 189  * "typeof" will have to merge the types together
 190  */
 191 void merge_type(struct symbol *sym, struct symbol *base_type)
 192 {
 193         sym->ctype.as |= base_type->ctype.as;
 194         sym->ctype.modifiers |= (base_type->ctype.modifiers & ~MOD_STORAGE);
 195         sym->ctype.context |= base_type->ctype.context;
 196         sym->ctype.contextmask |= base_type->ctype.contextmask;
 197         sym->ctype.base_type = base_type->ctype.base_type;
 198 }
 199
 200 /*
 201  * Fill in type size and alignment information for
 202  * regular SYM_TYPE things.
 203  */
 204 #define MOD_STRIP (MOD_CONST | MOD_VOLATILE | MOD_ADDRESSABLE | \
 205                   MOD_NODEREF | MOD_ACCESSED | MOD_ASSIGNED | \
 206                   MOD_SAFE | MOD_FORCE | MOD_STORAGE)
 207 struct symbol *examine_symbol_type(struct symbol * sym)
 208 {
 209         unsigned int bit_size, alignment;
 210         struct symbol *base_type;
 211         unsigned long modifiers;
 212
 213         if (!sym)
 214                 return sym;
 215
 216         /* Already done? */
 217         if (sym->bit_size)
 218                 return sym;
 219
 220         switch (sym->type) {
 221         case SYM_ARRAY:
 222                 examine_array_type(sym);
 223                 return sym;
 224         case SYM_STRUCT:
 225                 examine_struct_union_type(sym, 1);
 226                 return sym;
 227         case SYM_UNION:
 228                 examine_struct_union_type(sym, 0);
 229                 return sym;
 230         case SYM_PTR:
 231                 if (!sym->bit_size)
 232                         sym->bit_size = bits_in_pointer;
 233                 if (!sym->ctype.alignment)
 234                         sym->ctype.alignment = pointer_alignment;
 235                 base_type = sym->ctype.base_type;
 236                 base_type = examine_symbol_type(base_type);
 237                 if (base_type && base_type->type == SYM_NODE)
 238                         merge_type(sym, base_type);
 239                 return sym;
 240         case SYM_ENUM:
 241                 if (!sym->bit_size)
 242                         sym->bit_size = bits_in_enum;
 243                 if (!sym->ctype.alignment)
 244                         sym->ctype.alignment = enum_alignment;
 245                 return sym;
 246         case SYM_BITFIELD:
 247                 examine_bitfield_type(sym);
 248                 return sym;
 249         case SYM_BASETYPE:
 250                 /* Size and alignment had better already be set up */
 251                 return sym;
 252         case SYM_TYPEOF: {
 253                 struct symbol *base = evaluate_expression(sym->initializer);
 254                 if (base) {
 255                         if (base->type == SYM_NODE)
 256                                 base = base->ctype.base_type;
 257                         sym->type = SYM_NODE;
 258                         sym->ctype.base_type = base;
 259                 }
 260                 break;
 261         }
 262         default:
 263                 break;
 264         }
 265
 266         /* SYM_NODE - figure out what the type of the node was.. */
 267         base_type = sym->ctype.base_type;
 268         modifiers = sym->ctype.modifiers;
 269
 270         bit_size = 0;
 271         alignment = 0;
 272         if (base_type) {
 273                 base_type = examine_symbol_type(base_type);
 274                 sym->ctype.base_type = base_type;
 275                 if (base_type && base_type->type == SYM_NODE)
 276                         merge_type(sym, base_type);
 277
 278                 bit_size = base_type->bit_size;
 279                 alignment = base_type->ctype.alignment;
 280                 if (base_type->fieldwidth)
 281                         sym->fieldwidth = base_type->fieldwidth;
 282         }
 283
 284         if (!sym->ctype.alignment)
 285                 sym->ctype.alignment = alignment;
 286         sym->bit_size = bit_size;
 287         return sym;
 288 }
 289
 290 void check_declaration(struct symbol *sym)
 291 {
 292         struct symbol *next = sym;
 293
 294         while ((next = next->next_id) != NULL) {
 295                 if (next->namespace != sym->namespace)
 296                         continue;
 297                 if (sym->scope == next->scope) {
 298                         sym->same_symbol = next;
 299                         return;
 300                 }
 301                 if (sym->ctype.modifiers & next->ctype.modifiers & MOD_EXTERN) {
 302                         sym->same_symbol = next;
 303                         return;
 304                 }
 305 #if 0
 306                 // This may make sense from a warning standpoint:
 307                 //  consider top-level symbols to clash with everything
 308                 //  (but the scoping rules will mean that we actually
 309                 //  _use_ the innermost version)
 310                 if (toplevel(next->scope)) {
 311                         sym->same_symbol = next;
 312                         return;
 313                 }
 314 #endif
 315         }
 316 }
 317
 318 void bind_symbol(struct symbol *sym, struct ident *ident, enum namespace ns)
 319 {
 320         struct scope *scope;
 321         if (sym->id_list) {
 322                 warn(sym->pos, "internal error: symbol type already bound");
 323                 return;
 324         }
 325         sym->namespace = ns;
 326         sym->next_id = ident->symbols;
 327         ident->symbols = sym;
 328         sym->id_list = &ident->symbols;
 329
 330         scope = block_scope;
 331         if (ns != NS_TYPEDEF && toplevel(scope)) {
 332                 sym->ctype.modifiers |= MOD_TOPLEVEL | MOD_ADDRESSABLE;
 333                 if (sym->ctype.modifiers & MOD_STATIC)
 334                         scope = file_scope;
 335         }
 336         if (ns == NS_LABEL)
 337                 scope = function_scope;
 338         bind_scope(sym, scope);
 339 }
 340
 341 static struct symbol *create_symbol(int stream, const char *name, int type, int namespace)
 342 {
 343         struct token *token = built_in_token(stream, name);
 344         struct symbol *sym = alloc_symbol(token->pos, type);
 345
 346         sym->ident = token->ident;
 347         bind_symbol(sym, token->ident, namespace);
 348         return sym;
 349 }
 350
 351 static int evaluate_constant_p(struct expression *expr)
 352 {
 353         expr->ctype = &int_ctype;
 354         return 1;
 355 }
 356
 357 static int expand_constant_p(struct expression *expr)
 358 {
 359         struct expression *arg;
 360         struct expression_list *arglist = expr->args;
 361         int value = 1;
 362
 363         FOR_EACH_PTR (arglist, arg) {
 364                 if (arg->type != EXPR_VALUE && arg->type != EXPR_VALUE)
 365                         value = 0;
 366         } END_FOR_EACH_PTR;
 367
 368         expr->type = EXPR_VALUE;
 369         expr->value = value;
 370         return 0;
 371 }
 372
 373 /*
 374  * Type and storage class keywords need to have the symbols
 375  * created for them, so that the parser can have enough semantic
 376  * information to do parsing.
 377  *
 378  * "double" == "long float", "long double" == "long long float"
 379  */
 380 struct sym_init {
 381         const char *name;
 382         struct symbol *base_type;
 383         unsigned int modifiers;
 384         struct symbol_op *op;
 385 } symbol_init_table[] = {
 386         /* Storage class */
 387         { "auto",       NULL,           MOD_AUTO },
 388         { "register",   NULL,           MOD_REGISTER },
 389         { "static",     NULL,           MOD_STATIC },
 390         { "extern",     NULL,           MOD_EXTERN },
 391
 392         /* Type specifiers */
 393         { "void",       &void_ctype,    0 },
 394         { "char",       NULL,           MOD_CHAR },
 395         { "short",      NULL,           MOD_SHORT },
 396         { "int",        &int_type,      0 },
 397         { "long",       NULL,           MOD_LONG },
 398         { "float",      &fp_type,       0 },
 399         { "double",     &fp_type,       MOD_LONG },
 400         { "signed",     NULL,           MOD_SIGNED },
 401         { "__signed",   NULL,           MOD_SIGNED },
 402         { "__signed__", NULL,           MOD_SIGNED },
 403         { "unsigned",   NULL,           MOD_UNSIGNED },
 404         { "__label__",  &label_type,    MOD_LABEL | MOD_UNSIGNED },
 405
 406         /* Type qualifiers */
 407         { "const",      NULL,           MOD_CONST },
 408         { "__const",    NULL,           MOD_CONST },
 409         { "__const__",  NULL,           MOD_CONST },
 410         { "volatile",   NULL,           MOD_VOLATILE },
 411         { "__volatile", NULL,           MOD_VOLATILE },
 412         { "__volatile__", NULL,         MOD_VOLATILE },
 413
 414         /* Predeclared types */
 415         { "__builtin_va_list", &int_type, 0 },
 416
 417         /* Typedef.. */
 418         { "typedef",    NULL,           MOD_TYPEDEF },
 419
 420         /* Extended types */
 421         { "typeof",     NULL,           MOD_TYPEOF },
 422         { "__typeof",   NULL,           MOD_TYPEOF },
 423         { "__typeof__", NULL,           MOD_TYPEOF },
 424
 425 #if 0
 426         { "attribute",  NULL,           MOD_ATTRIBUTE },
 427 #endif
 428         { "__attribute", NULL,          MOD_ATTRIBUTE },
 429         { "__attribute__", NULL,        MOD_ATTRIBUTE },
 430
 431         { "struct",     NULL,           MOD_STRUCTOF },
 432         { "union",      NULL,           MOD_UNIONOF },
 433         { "enum",       NULL,           MOD_ENUMOF },
 434
 435         { "inline",     NULL,           MOD_INLINE },
 436         { "__inline",   NULL,           MOD_INLINE },
 437         { "__inline__", NULL,           MOD_INLINE },
 438
 439         /* Ignored for now.. */
 440         { "restrict",   NULL,           0 },
 441         { "__restrict", NULL,           0 },
 442
 443         { NULL,         NULL,           0 }
 444 };
 445
 446 struct symbol_op constant_p_op = {
 447         .evaluate = evaluate_constant_p,
 448         .expand = expand_constant_p
 449 };
 450
 451 /*
 452  * Builtin functions
 453  */
 454 static struct symbol builtin_fn_type = { .type = SYM_FN };
 455 struct sym_init eval_init_table[] = {
 456         { "__builtin_constant_p", &builtin_fn_type, MOD_TOPLEVEL, &constant_p_op },
 457
 458         { NULL,         NULL,           0 }
 459 };
 460
 461
 462 /*
 463  * Abstract types
 464  */
 465 struct symbol   int_type,
 466                 fp_type,
 467                 label_type,
 468                 vector_type,
 469                 bad_type;
 470
 471 /*
 472  * C types (ie actual instances that the abstract types
 473  * can map onto)
 474  */
 475 struct symbol   bool_ctype, void_ctype, type_ctype,
 476                 char_ctype, uchar_ctype,
 477                 short_ctype, ushort_ctype,
 478                 int_ctype, uint_ctype,
 479                 long_ctype, ulong_ctype,
 480                 llong_ctype, ullong_ctype,
 481                 float_ctype, double_ctype, ldouble_ctype,
 482                 string_ctype, ptr_ctype, lazy_ptr_ctype,
 483                 incomplete_ctype;
 484
 485 struct ctype_declare {
 486         struct symbol *ptr;
 487         unsigned long modifiers;
 488         int *bit_size;
 489         int *maxalign;
 490         struct symbol *base_type;
 491 } ctype_declaration[] = {
 492         { &bool_ctype,   0,                                       &bits_in_int,         &max_int_alignment, &int_type },
 493         { &void_ctype,   0,                                       NULL,                 NULL,                   NULL },
 494         { &type_ctype,   MOD_TYPE,                                NULL,                 NULL,                   NULL },
 495         { &incomplete_ctype, 0,                                   NULL,                 NULL,                   NULL },
 496
 497         { &char_ctype,   MOD_SIGNED | MOD_CHAR,                   &bits_in_char,        &max_int_alignment, &int_type },
 498         { &uchar_ctype,  MOD_UNSIGNED | MOD_CHAR,                 &bits_in_char,        &max_int_alignment, &int_type },
 499         { &short_ctype,  MOD_SIGNED | MOD_SHORT,                  &bits_in_short,       &max_int_alignment, &int_type },
 500         { &ushort_ctype, MOD_UNSIGNED | MOD_SHORT,                &bits_in_short,       &max_int_alignment, &int_type },
 501         { &int_ctype,    MOD_SIGNED,                              &bits_in_int,         &max_int_alignment, &int_type },
 502         { &uint_ctype,   MOD_UNSIGNED,                            &bits_in_int,         &max_int_alignment, &int_type },
 503         { &long_ctype,   MOD_SIGNED | MOD_LONG,                   &bits_in_long,        &max_int_alignment, &int_type },
 504         { &ulong_ctype,  MOD_UNSIGNED | MOD_LONG,                 &bits_in_long,        &max_int_alignment, &int_type },
 505         { &llong_ctype,  MOD_SIGNED | MOD_LONG | MOD_LONGLONG,    &bits_in_longlong,    &max_int_alignment, &int_type },
 506         { &ullong_ctype, MOD_UNSIGNED | MOD_LONG | MOD_LONGLONG,  &bits_in_longlong,    &max_int_alignment, &int_type },
 507
 508         { &float_ctype,  0,                                       &bits_in_float,       &max_fp_alignment, &fp_type },
 509         { &double_ctype, MOD_LONG,                                &bits_in_double,      &max_fp_alignment, &fp_type },
 510         { &ldouble_ctype,MOD_LONG | MOD_LONGLONG,                 &bits_in_longdouble,  &max_fp_alignment, &fp_type },
 511
 512         { &string_ctype,            0,  &bits_in_pointer, &pointer_alignment, &char_ctype },
 513         { &ptr_ctype,               0,  &bits_in_pointer, &pointer_alignment, &void_ctype },
 514         { &lazy_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         lazy_ptr_ctype.type = SYM_PTR;
 600         string_ctype.type = SYM_PTR;
 601         for (ctype = ctype_declaration ; ctype->ptr; ctype++) {
 602                 struct symbol *sym = ctype->ptr;
 603                 unsigned long bit_size = ctype->bit_size ? *ctype->bit_size : -1;
 604                 unsigned long maxalign = ctype->maxalign ? *ctype->maxalign : 0;
 605                 unsigned long alignment = bit_size >> 3;
 606
 607                 if (alignment > maxalign)
 608                         alignment = maxalign;
 609                 sym->bit_size = bit_size;
 610                 sym->ctype.alignment = alignment;
 611                 sym->ctype.base_type = ctype->base_type;
 612                 sym->ctype.modifiers = ctype->modifiers;
 613         }
 614 }