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