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 fairly 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
  77         // Unnamed bitfields do not affect alignment.
  78         if (sym->ident || !is_bitfield_type(sym)) {
  79                 if (sym->ctype.alignment > info->max_align)
  80                         info->max_align = sym->ctype.alignment;
  81         }
  82
  83         if (sym->bit_size > info->bit_size)
  84                 info->bit_size = sym->bit_size;
  85
  86         sym->offset = 0;
  87 }
  88
  89 /*
  90  * Structures are a bit more interesting to lay out
  91  */
  92 static void lay_out_struct(struct symbol *sym, void *_info, int flags)
  93 {
  94         struct struct_union_info *info = _info;
  95         unsigned long bit_size, base_size;
  96         unsigned long align_bit_mask;
  97
  98         examine_symbol_type(sym);
  99
 100         // Unnamed bitfields do not affect alignment.
 101         if (sym->ident || !is_bitfield_type(sym)) {
 102                 if (sym->ctype.alignment > info->max_align)
 103                         info->max_align = sym->ctype.alignment;
 104         }
 105
 106         bit_size = info->bit_size;
 107         base_size = sym->bit_size;
 108         align_bit_mask = (sym->ctype.alignment << 3) - 1;
 109
 110         /*
 111          * Bitfields have some very special rules..
 112          */
 113         if (is_bitfield_type (sym)) {
 114                 unsigned long bit_offset = bit_size & align_bit_mask;
 115                 int room = base_size - bit_offset;
 116                 // Zero-width fields just fill up the unit.
 117                 int width = sym->fieldwidth ? sym->fieldwidth : (bit_offset ? room : 0);
 118
 119                 if (width > room) {
 120                         bit_size = (bit_size + align_bit_mask) & ~align_bit_mask;
 121                         bit_offset = 0;
 122                 }
 123                 sym->offset = (bit_size - bit_offset) >> 3;
 124                 sym->bit_offset = bit_offset;
 125                 info->bit_size = bit_size + width;
 126                 // warn (sym->pos, "bitfield: offset=%d:%d  size=:%d", sym->offset, sym->bit_offset, width);
 127
 128                 return;
 129         }
 130
 131         /*
 132          * Otherwise, just align it right and add it up..
 133          */
 134         bit_size = (bit_size + align_bit_mask) & ~align_bit_mask;
 135         sym->offset = bit_size >> 3;
 136
 137         info->bit_size = bit_size + sym->bit_size;
 138         // warn (sym->pos, "regular: offset=%d", sym->offset);
 139 }
 140
 141 static void examine_struct_union_type(struct symbol *sym, int advance)
 142 {
 143         struct struct_union_info info = { 1, 0 };
 144         unsigned long bit_size, bit_align;
 145         void (*fn)(struct symbol *, void *, int);
 146
 147         fn = advance ? lay_out_struct : lay_out_union;
 148         symbol_iterate(sym->symbol_list, fn, &info);
 149
 150         if (!sym->ctype.alignment)
 151                 sym->ctype.alignment = info.max_align;
 152         bit_size = info.bit_size;
 153         bit_align = (sym->ctype.alignment << 3)-1;
 154         bit_size = (bit_size + bit_align) & ~bit_align;
 155         sym->bit_size = bit_size;
 156 }
 157
 158 static void examine_array_type(struct symbol *sym)
 159 {
 160         struct symbol *base_type = sym->ctype.base_type;
 161         unsigned long bit_size, alignment;
 162
 163         if (!base_type)
 164                 return;
 165         examine_symbol_type(base_type);
 166         bit_size = base_type->bit_size * get_expression_value(sym->array_size);
 167         if (!sym->array_size || sym->array_size->type != EXPR_VALUE)
 168                 bit_size = -1;
 169         alignment = base_type->ctype.alignment;
 170         if (!sym->ctype.alignment)
 171                 sym->ctype.alignment = alignment;
 172         sym->bit_size = bit_size;
 173 }
 174
 175 static void examine_bitfield_type(struct symbol *sym)
 176 {
 177         struct symbol *base_type = sym->ctype.base_type;
 178         unsigned long bit_size, alignment;
 179
 180         if (!base_type)
 181                 return;
 182         examine_symbol_type(base_type);
 183         bit_size = base_type->bit_size;
 184         if (sym->fieldwidth > bit_size) {
 185                 warn(sym->pos, "impossible field-width, %d, for this type",
 186                      sym->fieldwidth);
 187                 sym->fieldwidth = bit_size;
 188         }
 189
 190         alignment = base_type->ctype.alignment;
 191         if (!sym->ctype.alignment)
 192                 sym->ctype.alignment = alignment;
 193         sym->bit_size = bit_size;
 194 }
 195
 196 /*
 197  * "typeof" will have to merge the types together
 198  */
 199 void merge_type(struct symbol *sym, struct symbol *base_type)
 200 {
 201         sym->ctype.as |= base_type->ctype.as;
 202         sym->ctype.modifiers |= (base_type->ctype.modifiers & ~MOD_STORAGE);
 203         sym->ctype.context |= base_type->ctype.context;
 204         sym->ctype.contextmask |= base_type->ctype.contextmask;
 205         sym->ctype.base_type = base_type->ctype.base_type;
 206 }
 207
 208 /*
 209  * Fill in type size and alignment information for
 210  * regular SYM_TYPE things.
 211  */
 212 struct symbol *examine_symbol_type(struct symbol * sym)
 213 {
 214         unsigned int bit_size, alignment;
 215         struct symbol *base_type;
 216         unsigned long modifiers;
 217
 218         if (!sym)
 219                 return sym;
 220
 221         /* Already done? */
 222         if (sym->bit_size)
 223                 return sym;
 224
 225         switch (sym->type) {
 226         case SYM_ARRAY:
 227                 examine_array_type(sym);
 228                 return sym;
 229         case SYM_STRUCT:
 230                 examine_struct_union_type(sym, 1);
 231                 return sym;
 232         case SYM_UNION:
 233                 examine_struct_union_type(sym, 0);
 234                 return sym;
 235         case SYM_PTR:
 236                 if (!sym->bit_size)
 237                         sym->bit_size = bits_in_pointer;
 238                 if (!sym->ctype.alignment)
 239                         sym->ctype.alignment = pointer_alignment;
 240                 base_type = sym->ctype.base_type;
 241                 base_type = examine_symbol_type(base_type);
 242                 if (base_type && base_type->type == SYM_NODE)
 243                         merge_type(sym, base_type);
 244                 return sym;
 245         case SYM_ENUM:
 246                 if (!sym->bit_size)
 247                         sym->bit_size = bits_in_enum;
 248                 if (!sym->ctype.alignment)
 249                         sym->ctype.alignment = enum_alignment;
 250                 return sym;
 251         case SYM_BITFIELD:
 252                 examine_bitfield_type(sym);
 253                 return sym;
 254         case SYM_BASETYPE:
 255                 /* Size and alignment had better already be set up */
 256                 return sym;
 257         case SYM_TYPEOF: {
 258                 struct symbol *base = evaluate_expression(sym->initializer);
 259                 if (is_bitfield_type (base))
 260                         warn(base->pos, "typeof applied to bitfield type");
 261                 if (base) {
 262                         if (base->type == SYM_NODE)
 263                                 base = base->ctype.base_type;
 264                         sym->type = SYM_NODE;
 265                         sym->ctype.base_type = base;
 266                 }
 267                 break;
 268         }
 269         default:
 270                 break;
 271         }
 272
 273         /* SYM_NODE - figure out what the type of the node was.. */
 274         base_type = sym->ctype.base_type;
 275         modifiers = sym->ctype.modifiers;
 276
 277         bit_size = 0;
 278         alignment = 0;
 279         if (base_type) {
 280                 base_type = examine_symbol_type(base_type);
 281                 sym->ctype.base_type = base_type;
 282                 if (base_type && base_type->type == SYM_NODE)
 283                         merge_type(sym, base_type);
 284
 285                 bit_size = base_type->bit_size;
 286                 alignment = base_type->ctype.alignment;
 287                 if (base_type->fieldwidth)
 288                         sym->fieldwidth = base_type->fieldwidth;
 289         }
 290
 291         if (!sym->ctype.alignment)
 292                 sym->ctype.alignment = alignment;
 293         sym->bit_size = bit_size;
 294         return sym;
 295 }
 296
 297 void check_declaration(struct symbol *sym)
 298 {
 299         struct symbol *next = sym;
 300
 301         while ((next = next->next_id) != NULL) {
 302                 if (next->namespace != sym->namespace)
 303                         continue;
 304                 if (sym->scope == next->scope) {
 305                         sym->same_symbol = next;
 306                         return;
 307                 }
 308                 if (sym->ctype.modifiers & next->ctype.modifiers & MOD_EXTERN) {
 309                         sym->same_symbol = next;
 310                         return;
 311                 }
 312 #if 0
 313                 // This may make sense from a warning standpoint:
 314                 //  consider top-level symbols to clash with everything
 315                 //  (but the scoping rules will mean that we actually
 316                 //  _use_ the innermost version)
 317                 if (toplevel(next->scope)) {
 318                         sym->same_symbol = next;
 319                         return;
 320                 }
 321 #endif
 322         }
 323 }
 324
 325 void bind_symbol(struct symbol *sym, struct ident *ident, enum namespace ns)
 326 {
 327         struct scope *scope;
 328         if (sym->id_list) {
 329                 warn(sym->pos, "internal error: symbol type already bound");
 330                 return;
 331         }
 332         sym->namespace = ns;
 333         sym->next_id = ident->symbols;
 334         ident->symbols = sym;
 335         sym->id_list = &ident->symbols;
 336
 337         scope = block_scope;
 338         if (ns != NS_TYPEDEF && toplevel(scope)) {
 339                 sym->ctype.modifiers |= MOD_TOPLEVEL | MOD_ADDRESSABLE;
 340                 if (sym->ctype.modifiers & MOD_STATIC)
 341                         scope = file_scope;
 342         }
 343         if (ns == NS_LABEL)
 344                 scope = function_scope;
 345         bind_scope(sym, scope);
 346 }
 347
 348 static struct symbol *create_symbol(int stream, const char *name, int type, int namespace)
 349 {
 350         struct token *token = built_in_token(stream, name);
 351         struct symbol *sym = alloc_symbol(token->pos, type);
 352
 353         sym->ident = token->ident;
 354         bind_symbol(sym, token->ident, namespace);
 355         return sym;
 356 }
 357
 358 static int evaluate_constant_p(struct expression *expr)
 359 {
 360         expr->ctype = &int_ctype;
 361         return 1;
 362 }
 363
 364 static int expand_constant_p(struct expression *expr)
 365 {
 366         struct expression *arg;
 367         struct expression_list *arglist = expr->args;
 368         int value = 1;
 369
 370         FOR_EACH_PTR (arglist, arg) {
 371                 if (arg->type != EXPR_VALUE && arg->type != EXPR_FVALUE)
 372                         value = 0;
 373         } END_FOR_EACH_PTR;
 374
 375         expr->type = EXPR_VALUE;
 376         expr->value = value;
 377         return 0;
 378 }
 379
 380 /*
 381  * Type and storage class keywords need to have the symbols
 382  * created for them, so that the parser can have enough semantic
 383  * information to do parsing.
 384  *
 385  * "double" == "long float", "long double" == "long long float"
 386  */
 387 struct sym_init {
 388         const char *name;
 389         struct symbol *base_type;
 390         unsigned int modifiers;
 391         struct symbol_op *op;
 392 } symbol_init_table[] = {
 393         /* Storage class */
 394         { "auto",       NULL,           MOD_AUTO },
 395         { "register",   NULL,           MOD_REGISTER },
 396         { "static",     NULL,           MOD_STATIC },
 397         { "extern",     NULL,           MOD_EXTERN },
 398
 399         /* Type specifiers */
 400         { "void",       &void_ctype,    0 },
 401         { "char",       NULL,           MOD_CHAR },
 402         { "short",      NULL,           MOD_SHORT },
 403         { "int",        &int_type,      0 },
 404         { "long",       NULL,           MOD_LONG },
 405         { "float",      &fp_type,       0 },
 406         { "double",     &fp_type,       MOD_LONG },
 407         { "signed",     NULL,           MOD_SIGNED | MOD_EXPLICITLY_SIGNED },
 408         { "__signed",   NULL,           MOD_SIGNED | MOD_EXPLICITLY_SIGNED },
 409         { "__signed__", NULL,           MOD_SIGNED | MOD_EXPLICITLY_SIGNED },
 410         { "unsigned",   NULL,           MOD_UNSIGNED },
 411         { "__label__",  &label_type,    MOD_LABEL | MOD_UNSIGNED },
 412
 413         /* Type qualifiers */
 414         { "const",      NULL,           MOD_CONST },
 415         { "__const",    NULL,           MOD_CONST },
 416         { "__const__",  NULL,           MOD_CONST },
 417         { "volatile",   NULL,           MOD_VOLATILE },
 418         { "__volatile", NULL,           MOD_VOLATILE },
 419         { "__volatile__", NULL,         MOD_VOLATILE },
 420
 421         /* Predeclared types */
 422         { "__builtin_va_list", &int_type, 0 },
 423
 424         /* Typedef.. */
 425         { "typedef",    NULL,           MOD_TYPEDEF },
 426
 427         /* Extended types */
 428         { "typeof",     NULL,           MOD_TYPEOF },
 429         { "__typeof",   NULL,           MOD_TYPEOF },
 430         { "__typeof__", NULL,           MOD_TYPEOF },
 431
 432 #if 0
 433         { "attribute",  NULL,           MOD_ATTRIBUTE },
 434 #endif
 435         { "__attribute", NULL,          MOD_ATTRIBUTE },
 436         { "__attribute__", NULL,        MOD_ATTRIBUTE },
 437
 438         { "struct",     NULL,           MOD_STRUCTOF },
 439         { "union",      NULL,           MOD_UNIONOF },
 440         { "enum",       NULL,           MOD_ENUMOF },
 441
 442         { "inline",     NULL,           MOD_INLINE },
 443         { "__inline",   NULL,           MOD_INLINE },
 444         { "__inline__", NULL,           MOD_INLINE },
 445
 446         /* Ignored for now.. */
 447         { "restrict",   NULL,           0 },
 448         { "__restrict", NULL,           0 },
 449
 450         { NULL,         NULL,           0 }
 451 };
 452
 453 struct symbol_op constant_p_op = {
 454         .evaluate = evaluate_constant_p,
 455         .expand = expand_constant_p
 456 };
 457
 458 /*
 459  * Builtin functions
 460  */
 461 static struct symbol builtin_fn_type = { .type = SYM_FN /* , .variadic =1 */ };
 462 static struct sym_init eval_init_table[] = {
 463         { "__builtin_constant_p", &builtin_fn_type, MOD_TOPLEVEL, &constant_p_op },
 464         { NULL,         NULL,           0 }
 465 };
 466
 467
 468 /*
 469  * Abstract types
 470  */
 471 struct symbol   int_type,
 472                 fp_type,
 473                 label_type,
 474                 vector_type,
 475                 bad_type;
 476
 477 /*
 478  * C types (ie actual instances that the abstract types
 479  * can map onto)
 480  */
 481 struct symbol   bool_ctype, void_ctype, type_ctype,
 482                 char_ctype, uchar_ctype,
 483                 short_ctype, ushort_ctype,
 484                 int_ctype, uint_ctype,
 485                 long_ctype, ulong_ctype,
 486                 llong_ctype, ullong_ctype,
 487                 float_ctype, double_ctype, ldouble_ctype,
 488                 string_ctype, ptr_ctype, lazy_ptr_ctype,
 489                 incomplete_ctype;
 490
 491 const struct ctype_declare {
 492         struct symbol *ptr;
 493         unsigned long modifiers;
 494         int *bit_size;
 495         int *maxalign;
 496         struct symbol *base_type;
 497 } ctype_declaration[] = {
 498         { &bool_ctype,   0,                                       &bits_in_int,         &max_int_alignment, &int_type },
 499         { &void_ctype,   0,                                       NULL,                 NULL,                   NULL },
 500         { &type_ctype,   MOD_TYPE,                                NULL,                 NULL,                   NULL },
 501         { &incomplete_ctype, 0,                                   NULL,                 NULL,                   NULL },
 502
 503         { &char_ctype,   MOD_SIGNED | MOD_CHAR,                   &bits_in_char,        &max_int_alignment, &int_type },
 504         { &uchar_ctype,  MOD_UNSIGNED | MOD_CHAR,                 &bits_in_char,        &max_int_alignment, &int_type },
 505         { &short_ctype,  MOD_SIGNED | MOD_SHORT,                  &bits_in_short,       &max_int_alignment, &int_type },
 506         { &ushort_ctype, MOD_UNSIGNED | MOD_SHORT,                &bits_in_short,       &max_int_alignment, &int_type },
 507         { &int_ctype,    MOD_SIGNED,                              &bits_in_int,         &max_int_alignment, &int_type },
 508         { &uint_ctype,   MOD_UNSIGNED,                            &bits_in_int,         &max_int_alignment, &int_type },
 509         { &long_ctype,   MOD_SIGNED | MOD_LONG,                   &bits_in_long,        &max_int_alignment, &int_type },
 510         { &ulong_ctype,  MOD_UNSIGNED | MOD_LONG,                 &bits_in_long,        &max_int_alignment, &int_type },
 511         { &llong_ctype,  MOD_SIGNED | MOD_LONG | MOD_LONGLONG,    &bits_in_longlong,    &max_int_alignment, &int_type },
 512         { &ullong_ctype, MOD_UNSIGNED | MOD_LONG | MOD_LONGLONG,  &bits_in_longlong,    &max_int_alignment, &int_type },
 513
 514         { &float_ctype,  0,                                       &bits_in_float,       &max_fp_alignment, &fp_type },
 515         { &double_ctype, MOD_LONG,                                &bits_in_double,      &max_fp_alignment, &fp_type },
 516         { &ldouble_ctype,MOD_LONG | MOD_LONGLONG,                 &bits_in_longdouble,  &max_fp_alignment, &fp_type },
 517
 518         { &string_ctype,            0,  &bits_in_pointer, &pointer_alignment, &char_ctype },
 519         { &ptr_ctype,               0,  &bits_in_pointer, &pointer_alignment, &void_ctype },
 520         { &lazy_ptr_ctype,          0,  &bits_in_pointer, &pointer_alignment, &void_ctype },
 521         { NULL, }
 522 };
 523
 524
 525 #define __INIT_IDENT(str) { .len = sizeof(str)-1, .name = str }
 526 #define __IDENT(n,str) \
 527         struct ident n  = __INIT_IDENT(str)
 528
 529 #include "ident-list.h"
 530
 531 void init_symbols(void)
 532 {
 533         int stream = init_stream("builtin", -1, includepath);
 534         struct sym_init *ptr;
 535
 536 #define __IDENT(n,str) \
 537         hash_ident(&n)
 538 #include "ident-list.h"
 539
 540         for (ptr = symbol_init_table; ptr->name; ptr++) {
 541                 struct symbol *sym;
 542                 sym = create_symbol(stream, ptr->name, SYM_NODE, NS_TYPEDEF);
 543                 sym->ctype.base_type = ptr->base_type;
 544                 sym->ctype.modifiers = ptr->modifiers;
 545         }
 546
 547         builtin_fn_type.variadic = 1;
 548         for (ptr = eval_init_table; ptr->name; ptr++) {
 549                 struct symbol *sym;
 550                 sym = create_symbol(stream, ptr->name, SYM_NODE, NS_SYMBOL);
 551                 sym->ctype.base_type = ptr->base_type;
 552                 sym->ctype.modifiers = ptr->modifiers;
 553                 sym->op = ptr->op;
 554         }
 555 }
 556
 557 void init_ctype(void)
 558 {
 559         const struct ctype_declare *ctype;
 560
 561         ptr_ctype.type = SYM_PTR;
 562         lazy_ptr_ctype.type = SYM_PTR;
 563         string_ctype.type = SYM_PTR;
 564         for (ctype = ctype_declaration ; ctype->ptr; ctype++) {
 565                 struct symbol *sym = ctype->ptr;
 566                 unsigned long bit_size = ctype->bit_size ? *ctype->bit_size : -1;
 567                 unsigned long maxalign = ctype->maxalign ? *ctype->maxalign : 0;
 568                 unsigned long alignment = bit_size >> 3;
 569
 570                 if (alignment > maxalign)
 571                         alignment = maxalign;
 572                 sym->bit_size = bit_size;
 573                 sym->ctype.alignment = alignment;
 574                 sym->ctype.base_type = ctype->base_type;
 575                 sym->ctype.modifiers = ctype->modifiers;
 576         }
 577 }