nsz Git - libfirm/blob - ir/tr/entity.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/tr/entity.c
   4  * Purpose:     Representation of all program known entities.
   5  * Author:      Martin Trapp, Christian Schaefer
   6  * Modified by: Goetz Lindenmaier
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include <config.h>
  15 #endif
  16
  17 # include <stdlib.h>
  18 # include <stddef.h>
  19 # include <string.h>
  20
  21 # include "entity_t.h"
  22 # include "mangle.h"
  23 # include "typegmod.h"
  24 # include "array.h"
  25 /* All this is needed to build the constant node for methods: */
  26 # include "irprog_t.h"
  27 # include "ircons.h"
  28 # include "tv_t.h"
  29
  30 /*******************************************************************/
  31 /** general                                                       **/
  32 /*******************************************************************/
  33
  34 void
  35 init_entity (void)
  36 {
  37 }
  38
  39 /*-----------------------------------------------------------------*/
  40 /* ENTITY                                                          */
  41 /*-----------------------------------------------------------------*/
  42
  43 static void insert_entity_in_owner (entity *ent) {
  44   type *owner = ent->owner;
  45   switch (get_type_tpop_code(owner)) {
  46   case tpo_class: {
  47     add_class_member (owner, ent);
  48   } break;
  49   case tpo_struct: {
  50     add_struct_member (owner, ent);
  51   } break;
  52   case tpo_union: {
  53     add_union_member (owner, ent);
  54   } break;
  55   case tpo_array: {
  56     set_array_element_entity(owner, ent);
  57   } break;
  58   default: assert(0);
  59   }
  60 }
  61
  62 entity *
  63 new_entity (type *owner, ident *name, type *type)
  64 {
  65   entity *res;
  66   ir_graph *rem;
  67
  68   assert(!id_contains_char(name, ' ') && "entity name should not contain spaces");
  69
  70   res = (entity *) xmalloc (sizeof (entity));
  71   res->kind = k_entity;
  72   assert_legal_owner_of_ent(owner);
  73   res->owner = owner;
  74   res->name = name;
  75   res->type = type;
  76
  77   if (get_type_tpop(type) == type_method)
  78     res->allocation = allocation_static;
  79   else
  80     res->allocation = allocation_automatic;
  81
  82   res->visibility = visibility_local;
  83   res->offset = -1;
  84   if (is_method_type(type)) {
  85     symconst_symbol sym;
  86     sym.entity_p = res;
  87     res->variability = variability_constant;
  88     rem = current_ir_graph;
  89     current_ir_graph = get_const_code_irg();
  90     res->value = new_SymConst(sym, symconst_addr_ent);
  91     current_ir_graph = rem;
  92   } else {
  93     res->variability = variability_uninitialized;
  94     res->value  = NULL;
  95     res->values = NULL;
  96     res->val_paths = NULL;
  97   }
  98   res->peculiarity   = peculiarity_existent;
  99   res->volatility    = volatility_non_volatile;
 100   res->stickyness    = stickyness_unsticky;
 101   res->ld_name       = NULL;
 102   if (is_class_type(owner)) {
 103     res->overwrites    = NEW_ARR_F(entity *, 0);
 104     res->overwrittenby = NEW_ARR_F(entity *, 0);
 105   } else {
 106     res->overwrites    = NULL;
 107     res->overwrittenby = NULL;
 108   }
 109   res->irg = NULL;
 110
 111 #ifdef DEBUG_libfirm
 112   res->nr = get_irp_new_node_nr();
 113 #endif
 114
 115   res->visit = 0;
 116
 117   /* Remember entity in it's owner. */
 118   insert_entity_in_owner (res);
 119   return res;
 120 }
 121 entity *
 122 new_d_entity (type *owner, ident *name, type *type, dbg_info *db) {
 123   entity *res = new_entity(owner, name, type);
 124   set_entity_dbg_info(res, db);
 125   return res;
 126 }
 127
 128 static void free_entity_attrs(entity *ent) {
 129   int i;
 130   if (get_type_tpop(get_entity_owner(ent)) == type_class) {
 131     DEL_ARR_F(ent->overwrites);    ent->overwrites = NULL;
 132     DEL_ARR_F(ent->overwrittenby); ent->overwrittenby = NULL;
 133   } else {
 134     assert(ent->overwrites == NULL);
 135     assert(ent->overwrittenby == NULL);
 136   }
 137   /* if (ent->values) DEL_ARR_F(ent->values); *//* @@@ warum nich? */
 138   if (ent->val_paths) {
 139     if (is_compound_entity(ent))
 140       for (i = 0; i < get_compound_ent_n_values(ent); i++)
 141     if (ent->val_paths[i]) ;
 142     /* free_compound_graph_path(ent->val_paths[i]) ;  * @@@ warum nich? */
 143     /* Geht nich: wird mehrfach verwendet!!! ==> mehrfach frei gegeben. */
 144     /* DEL_ARR_F(ent->val_paths); */
 145   }
 146   ent->val_paths = NULL;
 147   ent->values = NULL;
 148 }
 149
 150 entity *
 151 copy_entity_own (entity *old, type *new_owner) {
 152   entity *new;
 153   assert(old && old->kind == k_entity);
 154   assert_legal_owner_of_ent(new_owner);
 155
 156   if (old->owner == new_owner) return old;
 157   new = (entity *) xmalloc (sizeof (entity));
 158   memcpy (new, old, sizeof (entity));
 159   new->owner = new_owner;
 160   if (is_class_type(new_owner)) {
 161     new->overwrites    = NEW_ARR_F(entity *, 0);
 162     new->overwrittenby = NEW_ARR_F(entity *, 0);
 163   }
 164 #ifdef DEBUG_libfirm
 165   new->nr = get_irp_new_node_nr();
 166 #endif
 167
 168   insert_entity_in_owner (new);
 169
 170   return new;
 171 }
 172
 173 entity *
 174 copy_entity_name (entity *old, ident *new_name) {
 175   entity *new;
 176   assert(old && old->kind == k_entity);
 177
 178   if (old->name == new_name) return old;
 179   new = (entity *) xmalloc (sizeof (entity));
 180   memcpy (new, old, sizeof (entity));
 181   new->name = new_name;
 182   new->ld_name = NULL;
 183   if (is_class_type(new->owner)) {
 184     new->overwrites    = DUP_ARR_F(entity *, old->overwrites);
 185     new->overwrittenby = DUP_ARR_F(entity *, old->overwrittenby);
 186   }
 187 #ifdef DEBUG_libfirm
 188   new->nr = get_irp_new_node_nr();
 189 #endif
 190
 191   insert_entity_in_owner (new);
 192
 193   return new;
 194 }
 195
 196
 197 void
 198 free_entity (entity *ent) {
 199   assert(ent && ent->kind == k_entity);
 200   free_tarval_entity(ent);
 201   free_entity_attrs(ent);
 202   ent->kind = k_BAD;
 203   free(ent);
 204 }
 205
 206 /* Outputs a unique number for this node */
 207 long
 208 get_entity_nr(entity *ent) {
 209   assert(ent && ent->kind == k_entity);
 210 #ifdef DEBUG_libfirm
 211   return ent->nr;
 212 #else
 213   return 0;
 214 #endif
 215 }
 216
 217 const char *
 218 (get_entity_name)(entity *ent) {
 219   return __get_entity_name(ent);
 220 }
 221
 222 ident *
 223 (get_entity_ident)(entity *ent) {
 224   return get_entity_ident(ent);
 225 }
 226
 227 /*
 228 void   set_entitye_ld_name  (entity *, char *ld_name);
 229 void   set_entity_ld_ident (entity *, ident *ld_ident);
 230 */
 231
 232 type *
 233 (get_entity_owner)(entity *ent) {
 234   return __get_entity_owner(ent);
 235 }
 236
 237 void
 238 set_entity_owner (entity *ent, type *owner) {
 239   assert(ent && ent->kind == k_entity);
 240   assert_legal_owner_of_ent(owner);
 241   ent->owner = owner;
 242 }
 243
 244 void   /* should this go into type.c? */
 245 assert_legal_owner_of_ent(type *owner) {
 246   assert(get_type_tpop_code(owner) == tpo_class ||
 247           get_type_tpop_code(owner) == tpo_union ||
 248           get_type_tpop_code(owner) == tpo_struct ||
 249       get_type_tpop_code(owner) == tpo_array);   /* Yes, array has an entity
 250                             -- to select fields! */
 251 }
 252
 253 ident *
 254 (get_entity_ld_ident)(entity *ent) {
 255   return __get_entity_ld_ident(ent);
 256 }
 257
 258 void
 259 (set_entity_ld_ident)(entity *ent, ident *ld_ident) {
 260    __set_entity_ld_ident(ent, ld_ident);
 261 }
 262
 263 const char *
 264 (get_entity_ld_name)(entity *ent) {
 265   return __get_entity_ld_name(ent);
 266 }
 267
 268 type *
 269 (get_entity_type)(entity *ent) {
 270   return __get_entity_type(ent);
 271 }
 272
 273 void
 274 (set_entity_type)(entity *ent, type *type) {
 275   __set_entity_type(ent, type);
 276 }
 277
 278 ent_allocation
 279 (get_entity_allocation)(entity *ent) {
 280   return __get_entity_allocation(ent);
 281 }
 282
 283 void
 284 (set_entity_allocation)(entity *ent, ent_allocation al) {
 285   __set_entity_allocation(ent, al);
 286 }
 287
 288 /* return the name of the visibility */
 289 const char *get_allocation_name(ent_allocation all)
 290 {
 291 #define X(a)    case a: return #a
 292   switch (all) {
 293     X(allocation_automatic);
 294     X(allocation_parameter);
 295     X(allocation_dynamic);
 296     X(allocation_static);
 297     default: return "BAD VALUE";
 298   }
 299 #undef X
 300 }
 301
 302
 303 ent_visibility
 304 (get_entity_visibility)(entity *ent) {
 305   return __get_entity_visibility(ent);
 306 }
 307
 308 void
 309 set_entity_visibility (entity *ent, ent_visibility vis) {
 310   assert(ent && ent->kind == k_entity);
 311   if (vis != visibility_local)
 312     assert((ent->allocation == allocation_static) ||
 313        (ent->allocation == allocation_automatic));
 314   /* @@@ Test that the owner type is not local, but how??
 315          && get_class_visibility(get_entity_owner(ent)) != local));*/
 316   ent->visibility = vis;
 317 }
 318
 319 /* return the name of the visibility */
 320 const char *get_visibility_name(ent_visibility vis)
 321 {
 322 #define X(a)    case a: return #a
 323   switch (vis) {
 324     X(visibility_local);
 325     X(visibility_external_visible);
 326     X(visibility_external_allocated);
 327     default: return "BAD VALUE";
 328   }
 329 #undef X
 330 }
 331
 332 ent_variability
 333 (get_entity_variability)(entity *ent) {
 334   return __get_entity_variability(ent);
 335 }
 336
 337 void
 338 set_entity_variability (entity *ent, ent_variability var)
 339 {
 340   assert(ent && ent->kind == k_entity);
 341   if (var == variability_part_constant)
 342     assert(is_class_type(ent->type) || is_struct_type(ent->type));
 343
 344   if ((is_compound_type(ent->type)) &&
 345       (ent->variability == variability_uninitialized) && (var != variability_uninitialized)) {
 346     /* Allocate datastructures for constant values */
 347     ent->values    = NEW_ARR_F(ir_node *, 0);
 348     ent->val_paths = NEW_ARR_F(compound_graph_path *, 0);
 349   }
 350
 351   if ((is_compound_type(ent->type)) &&
 352       (var == variability_uninitialized) && (ent->variability != variability_uninitialized)) {
 353     /* Free datastructures for constant values */
 354     DEL_ARR_F(ent->values);    ent->values    = NULL;
 355     DEL_ARR_F(ent->val_paths); ent->val_paths = NULL;
 356   }
 357   ent->variability = var;
 358 }
 359
 360 /* return the name of the variablity */
 361 const char *get_variability_name(ent_variability var)
 362 {
 363 #define X(a)    case a: return #a
 364   switch (var) {
 365     X(variability_uninitialized);
 366     X(variability_initialized);
 367     X(variability_part_constant);
 368     X(variability_constant);
 369     default: return "BAD VALUE";
 370   }
 371 #undef X
 372 }
 373
 374 ent_volatility
 375 (get_entity_volatility)(entity *ent) {
 376   return __get_entity_volatility(ent);
 377 }
 378
 379 void
 380 (set_entity_volatility)(entity *ent, ent_volatility vol) {
 381   __set_entity_volatility(ent, vol);
 382 }
 383
 384 /* return the name of the volatility */
 385 const char *get_volatility_name(ent_volatility var)
 386 {
 387 #define X(a)    case a: return #a
 388   switch (var) {
 389     X(volatility_non_volatile);
 390     X(volatility_is_volatile);
 391     default: return "BAD VALUE";
 392   }
 393 #undef X
 394 }
 395
 396 peculiarity
 397 (get_entity_peculiarity)(entity *ent) {
 398   return __get_entity_peculiarity(ent);
 399 }
 400
 401 void
 402 (set_entity_peculiarity)(entity *ent, peculiarity pec) {
 403   __set_entity_peculiarity(ent, pec);
 404 }
 405
 406 /* return the name of the peculiarity */
 407 const char *get_peculiarity_name(peculiarity var)
 408 {
 409 #define X(a)    case a: return #a
 410   switch (var) {
 411     X(peculiarity_description);
 412     X(peculiarity_inherited);
 413     X(peculiarity_existent);
 414     default: return "BAD VALUE";
 415   }
 416 #undef X
 417 }
 418
 419 /* Get the entity's stickyness */
 420 ent_stickyness
 421 (get_entity_stickyness)(entity *ent) {
 422   return __get_entity_stickyness(ent);
 423 }
 424
 425 /* Set the entity's stickyness */
 426 void
 427 (set_entity_stickyness)(entity *ent, ent_stickyness stickyness) {
 428   __set_entity_stickyness(ent, stickyness);
 429 }
 430
 431 /* Set has no effect for existent entities of type method. */
 432 ir_node *
 433 get_atomic_ent_value(entity *ent)
 434 {
 435   assert(ent && is_atomic_entity(ent));
 436   assert(ent->variability != variability_uninitialized);
 437   return skip_Id (ent->value);
 438 }
 439
 440 void
 441 set_atomic_ent_value(entity *ent, ir_node *val) {
 442   assert(is_atomic_entity(ent) && (ent->variability != variability_uninitialized));
 443   if (is_method_type(ent->type) && (ent->peculiarity == peculiarity_existent))
 444     return;
 445   ent->value = val;
 446 }
 447
 448 /* Returns true if the the node is representable as code on
 449  *  const_code_irg. */
 450 int is_irn_const_expression(ir_node *n) {
 451   ir_mode *m;
 452
 453   m = get_irn_mode(n);
 454   switch(get_irn_opcode(n)) {
 455   case iro_Const:
 456   case iro_SymConst:
 457   case iro_Unknown:
 458     return true; break;
 459   case iro_Add:
 460   case iro_Sub:
 461   case iro_Mul:
 462   case iro_And:
 463   case iro_Or:
 464   case iro_Eor:
 465     if (is_irn_const_expression(get_binop_left(n)))
 466       return is_irn_const_expression(get_binop_right(n));
 467   case iro_Conv:
 468   case iro_Cast:
 469     return is_irn_const_expression(get_irn_n(n, 0));
 470   default:
 471     return false;
 472     break;
 473   }
 474   return false;
 475 }
 476
 477
 478 ir_node *copy_const_value(ir_node *n) {
 479   ir_node *nn;
 480   ir_mode *m;
 481
 482   m = get_irn_mode(n);
 483   switch(get_irn_opcode(n)) {
 484   case iro_Const:
 485     nn = new_Const(m, get_Const_tarval(n)); break;
 486   case iro_SymConst:
 487
 488     nn = new_SymConst(get_SymConst_symbol(n), get_SymConst_kind(n));
 489     break;
 490   case iro_Add:
 491     nn = new_Add(copy_const_value(get_Add_left(n)),
 492          copy_const_value(get_Add_right(n)), m); break;
 493   case iro_Sub:
 494     nn = new_Sub(copy_const_value(get_Sub_left(n)),
 495          copy_const_value(get_Sub_right(n)), m); break;
 496   case iro_Mul:
 497     nn = new_Mul(copy_const_value(get_Mul_left(n)),
 498          copy_const_value(get_Mul_right(n)), m); break;
 499   case iro_And:
 500     nn = new_And(copy_const_value(get_And_left(n)),
 501          copy_const_value(get_And_right(n)), m); break;
 502   case iro_Or:
 503     nn = new_Or(copy_const_value(get_Or_left(n)),
 504          copy_const_value(get_Or_right(n)), m); break;
 505   case iro_Eor:
 506     nn = new_Eor(copy_const_value(get_Eor_left(n)),
 507          copy_const_value(get_Eor_right(n)), m); break;
 508   case iro_Cast:
 509     nn = new_Cast(copy_const_value(get_Cast_op(n)), get_Cast_type(n)); break;
 510   case iro_Conv:
 511     nn = new_Conv(copy_const_value(get_Conv_op(n)), m); break;
 512   case iro_Unknown:
 513     nn = new_Unknown(m); break;
 514   default:
 515     DDMN(n);
 516     assert(0 && "opdope invalid or not implemented");
 517     nn = NULL;
 518     break;
 519   }
 520   return nn;
 521 }
 522
 523 compound_graph_path *
 524 new_compound_graph_path(type *tp, int length) {
 525   compound_graph_path *res;
 526   assert(is_type(tp) && is_compound_type(tp));
 527   assert(length > 0);
 528
 529   res = (compound_graph_path *) calloc (1, sizeof(compound_graph_path) + (length-1) * sizeof(entity *));
 530   res->kind          = k_ir_compound_graph_path;
 531   res->tp            = tp;
 532   res->len           = length;
 533   res ->arr_indicees = (int *) calloc(length, sizeof(int));
 534   return res;
 535 }
 536
 537 void
 538 free_compound_graph_path (compound_graph_path *gr) {
 539   assert(gr && is_compound_graph_path(gr));
 540   gr->kind = k_BAD;
 541   free(gr ->arr_indicees);
 542   free(gr);
 543 }
 544
 545 int
 546 is_compound_graph_path(void *thing) {
 547   return (get_kind(thing) == k_ir_compound_graph_path);
 548 }
 549
 550 /* checks whether nodes 0..pos are correct (all lie on a path.) */
 551 /* @@@ not implemented */
 552 int is_proper_compound_graph_path(compound_graph_path *gr, int pos) {
 553   int i;
 554   entity *node;
 555   type *owner = gr->tp;
 556   for (i = 0; i <= pos; i++) {
 557     node = get_compound_graph_path_node(gr, i);
 558     if (get_entity_owner(node) != owner) return false;
 559     owner = get_entity_type(node);
 560   }
 561   if (pos == get_compound_graph_path_length(gr))
 562     if (!is_atomic_type(owner)) return false;
 563   return true;
 564 }
 565
 566 int
 567 get_compound_graph_path_length(compound_graph_path *gr) {
 568   assert(gr && is_compound_graph_path(gr));
 569   return gr->len;
 570 }
 571
 572 entity *
 573 get_compound_graph_path_node(compound_graph_path *gr, int pos) {
 574   assert(gr && is_compound_graph_path(gr));
 575   assert(pos >= 0 && pos < gr->len);
 576   return gr->nodes[pos];
 577 }
 578
 579 void
 580 set_compound_graph_path_node(compound_graph_path *gr, int pos, entity *node) {
 581   assert(gr && is_compound_graph_path(gr));
 582   assert(pos >= 0 && pos < gr->len);
 583   assert(is_entity(node));
 584   gr->nodes[pos] = node;
 585   assert(is_proper_compound_graph_path(gr, pos));
 586 }
 587
 588 int
 589 get_compound_graph_path_array_index(compound_graph_path *gr, int pos) {
 590   assert(gr && is_compound_graph_path(gr));
 591   assert(pos >= 0 && pos < gr->len);
 592   return gr->arr_indicees[pos];
 593 }
 594
 595 void
 596 set_compound_graph_path_array_index(compound_graph_path *gr, int pos, int index) {
 597   assert(gr && is_compound_graph_path(gr));
 598   assert(pos >= 0 && pos < gr->len);
 599   gr->arr_indicees[pos] = index;
 600 }
 601
 602 /* A value of a compound entity is a pair of value and the corresponding path to a member of
 603    the compound. */
 604 void
 605 add_compound_ent_value_w_path(entity *ent, ir_node *val, compound_graph_path *path) {
 606   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 607   ARR_APP1 (ir_node *, ent->values, val);
 608   ARR_APP1 (compound_graph_path *, ent->val_paths, path);
 609 }
 610
 611 void
 612 set_compound_ent_value_w_path(entity *ent, ir_node *val, compound_graph_path *path, int pos) {
 613   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 614   ent->values[pos] = val;
 615   ent->val_paths[pos] = path;
 616 }
 617
 618 int
 619 get_compound_ent_n_values(entity *ent) {
 620   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 621   return (ARR_LEN (ent->values));
 622 }
 623
 624 ir_node  *
 625 get_compound_ent_value(entity *ent, int pos) {
 626   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 627   return ent->values[pos];
 628 }
 629
 630 compound_graph_path *
 631 get_compound_ent_value_path(entity *ent, int pos) {
 632   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 633   return ent->val_paths[pos];
 634 }
 635
 636 void
 637 remove_compound_ent_value(entity *ent, entity *value_ent) {
 638   int i;
 639   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 640   for (i = 0; i < (ARR_LEN (ent->val_paths)); i++) {
 641     compound_graph_path *path = ent->val_paths[i];
 642     if (path->nodes[path->len-1] == value_ent) {
 643       for(; i < (ARR_LEN (ent->val_paths))-1; i++) {
 644     ent->val_paths[i] = ent->val_paths[i+1];
 645     ent->values[i]   = ent->values[i+1];
 646       }
 647       ARR_SETLEN(entity*,  ent->val_paths, ARR_LEN(ent->val_paths) - 1);
 648       ARR_SETLEN(ir_node*, ent->values,    ARR_LEN(ent->values)    - 1);
 649       break;
 650     }
 651   }
 652 }
 653
 654 void
 655 add_compound_ent_value(entity *ent, ir_node *val, entity *member) {
 656   compound_graph_path *path;
 657   type *owner_tp = get_entity_owner(ent);
 658   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 659   path = new_compound_graph_path(owner_tp, 1);
 660   path->nodes[0] = member;
 661   if (is_array_type(owner_tp)) {
 662     assert(get_array_n_dimensions(owner_tp) == 1 && has_array_lower_bound(owner_tp, 0));
 663     int max = get_array_lower_bound_int(owner_tp, 0) -1;
 664     for (int i = 0; i < get_compound_ent_n_values(ent); ++i) {
 665       int index = get_compound_graph_path_array_index(get_compound_ent_value_path(ent, i), 0);
 666       if (index > max) max = index;
 667     }
 668     path->arr_indicees[0] = max + 1;
 669   }
 670   add_compound_ent_value_w_path(ent, val, path);
 671 }
 672
 673 /* Copies the firm subgraph referenced by val to const_code_irg and adds
 674    the node as constant initialization to ent.
 675    The subgraph may not contain control flow operations.
 676 void
 677 copy_and_add_compound_ent_value(entity *ent, ir_node *val, entity *member) {
 678   ir_graph *rem = current_ir_graph;
 679
 680   assert(get_entity_variability(ent) != variability_uninitialized);
 681   current_ir_graph = get_const_code_irg();
 682
 683   val = copy_const_value(val);
 684   add_compound_ent_value(ent, val, member);
 685   current_ir_graph = rem;
 686   }*/
 687
 688 /* Copies the value i of the entity to current_block in current_ir_graph.
 689 ir_node *
 690 copy_compound_ent_value(entity *ent, int pos) {
 691   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 692   return copy_const_value(ent->values[pos+1]);
 693   }*/
 694
 695 entity   *
 696 get_compound_ent_value_member(entity *ent, int pos) {
 697   compound_graph_path *path;
 698   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 699   path = get_compound_ent_value_path(ent, pos);
 700
 701   return get_compound_graph_path_node(path, get_compound_graph_path_length(path)-1);
 702 }
 703
 704 void
 705 set_compound_ent_value(entity *ent, ir_node *val, entity *member, int pos) {
 706   compound_graph_path *path;
 707   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 708   path = get_compound_ent_value_path(ent, pos);
 709   set_compound_graph_path_node(path, 0, member);
 710   set_compound_ent_value_w_path(ent, val, path, pos);
 711 }
 712
 713 void
 714 set_array_entity_values(entity *ent, tarval **values, int num_vals) {
 715   int i;
 716   ir_graph *rem = current_ir_graph;
 717   type *arrtp = get_entity_type(ent);
 718   ir_node *val;
 719
 720   assert(is_array_type(arrtp));
 721   assert(get_array_n_dimensions(arrtp) == 1);
 722   /* One bound is sufficient, the nunmber of constant fields makes the
 723      size. */
 724   assert(get_array_lower_bound (arrtp, 0) || get_array_upper_bound (arrtp, 0));
 725   assert(get_entity_variability(ent) != variability_uninitialized);
 726   current_ir_graph = get_const_code_irg();
 727
 728   for (i = 0; i < num_vals; i++) {
 729     val = new_Const(get_tarval_mode (values[i]), values[i]);
 730     add_compound_ent_value(ent, val, get_array_element_entity(arrtp));
 731     set_compound_graph_path_array_index(get_compound_ent_value_path(ent, i), 0, i);
 732   }
 733   current_ir_graph = rem;
 734 }
 735
 736 int  get_compound_ent_value_offset_bits(entity *ent, int pos) {
 737   assert(get_type_state(get_entity_type(ent)) == layout_fixed);
 738
 739   compound_graph_path *path = get_compound_ent_value_path(ent, pos);
 740   int i, path_len = get_compound_graph_path_length(path);
 741   int offset = 0;
 742
 743   for (i = 0; i < path_len; ++i) {
 744     entity *node = get_compound_graph_path_node(path, i);
 745     type *node_tp = get_entity_type(node);
 746     type *owner_tp = get_entity_owner(node);
 747     if (is_array_type(owner_tp)) {
 748       int size  = get_mode_size_bits (get_type_mode(node_tp));
 749       int align = get_mode_align_bits(get_type_mode(node_tp));
 750       if (size < align)
 751         size = align;
 752       else {
 753         assert(size % align == 0);
 754         /* ansonsten aufrunden */
 755       }
 756       offset += size * get_compound_graph_path_array_index(path, i);
 757     } else {
 758       offset += get_entity_offset_bits(node);
 759     }
 760   }
 761   return offset;
 762 }
 763
 764 int  get_compound_ent_value_offset_bytes(entity *ent, int pos) {
 765   int offset = get_compound_ent_value_offset_bits(ent, pos);
 766   assert(offset % 8 == 0);
 767   return offset >> 3;
 768 }
 769
 770
 771 static void init_index(type *arr) {
 772   int init;
 773   int dim = 0;
 774
 775   assert(get_array_n_dimensions(arr) == 1);
 776
 777   if (has_array_lower_bound(arr, dim))
 778     init = get_array_lower_bound_int(arr, 0) -1;
 779   else
 780     init = get_array_upper_bound_int(arr, 0) +1;
 781
 782   set_entity_link(get_array_element_entity(arr), (void *)init);
 783 }
 784
 785
 786 static int get_next_index(entity *elem_ent) {
 787   type *arr = get_entity_owner(elem_ent);
 788   int next;
 789   int dim = 0;
 790
 791   assert(get_array_n_dimensions(arr) == 1);
 792
 793   if (has_array_lower_bound(arr, dim)) {
 794     next = (int)get_entity_link(elem_ent) +1;
 795     if (has_array_upper_bound(arr, dim)) {
 796       int upper = get_array_upper_bound_int(arr, dim);
 797       if (next == upper) next = get_array_lower_bound_int(arr, dim);
 798     }
 799   } else {
 800     next = (int)get_entity_link(elem_ent) -1;
 801     if (has_array_lower_bound(arr, dim)) {
 802       int upper = get_array_upper_bound_int(arr, dim);
 803       if (next == upper) next = get_array_upper_bound_int(arr, dim);
 804     }
 805   }
 806
 807   set_entity_link(elem_ent, (void *)next);
 808   return next;
 809 }
 810
 811 /* Compute the array indicees in compound graph paths of initialized entities.
 812  *
 813  *  All arrays must have fixed lower and upper bounds.  One array can
 814  *  have an open bound.  If there are several open bounds, we do
 815  *  nothing.  There must be initializer elements for all array
 816  *  elements.  Uses the link field in the array element entities.  The
 817  *  array bounds must be representable as ints.
 818  *
 819  *  (If the bounds are not representable as ints we have to represent
 820  *  the indicees as firm nodes.  But the still we must be able to
 821  *  evaluate the index against the upper bound.)
 822  */
 823 void compute_compound_ent_array_indicees(entity *ent) {
 824   type *tp = get_entity_type(ent);
 825   int i, n_vals;
 826   entity *unknown_bound_entity = NULL;
 827
 828   if (!is_compound_type(tp) ||
 829       (ent->variability == variability_uninitialized)) return ;
 830
 831   n_vals = get_compound_ent_n_values(ent);
 832   if (n_vals == 0) return;
 833
 834   /* We can not compute the indicees if there is more than one array
 835      with an unknown bound.  For this remember the first entity that
 836      represents such an array. It could be ent. */
 837   if (is_array_type(tp)) {
 838     assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
 839     int dim = 0;
 840     if (!has_array_lower_bound(tp, dim) || !has_array_upper_bound(tp, dim))
 841      unknown_bound_entity = ent;
 842   }
 843
 844   /* Initialize the entity links to lower bound -1 and test all path elements
 845      for known bounds. */
 846   for (i = 0; i < n_vals; ++i) {
 847     compound_graph_path *path = get_compound_ent_value_path(ent, i);
 848     int j, path_len =  get_compound_graph_path_length(path);
 849     for (j = 0; j < path_len; ++j) {
 850       entity *node = get_compound_graph_path_node(path, j);
 851       type *elem_tp = get_entity_type(node);
 852
 853       if (is_array_type(elem_tp)) {
 854         assert(get_array_n_dimensions(elem_tp) == 1 && "other not implemented");
 855         int dim = 0;
 856         if (!has_array_lower_bound(elem_tp, dim) || !has_array_upper_bound(elem_tp, dim)) {
 857           if (!unknown_bound_entity) unknown_bound_entity = node;
 858           if (node != unknown_bound_entity) return;
 859         }
 860
 861         init_index(elem_tp);
 862       }
 863     }
 864   }
 865
 866   /* Finally compute the indicees ... */
 867   for (i = 0; i < n_vals; ++i) {
 868     compound_graph_path *path = get_compound_ent_value_path(ent, i);
 869     int j, path_len =  get_compound_graph_path_length(path);
 870     for (j = 0; j < path_len; ++j) {
 871       entity *node = get_compound_graph_path_node(path, j);
 872       type *owner_tp = get_entity_owner(node);
 873       if (is_array_type(owner_tp))
 874         set_compound_graph_path_array_index (path, j, get_next_index(node));
 875     }
 876   }
 877
 878 }
 879
 880
 881 static int *resize (int *buf, int new_size) {
 882   int *new_buf = (int *)calloc(new_size, 4);
 883   memcpy(new_buf, buf, new_size>1);
 884   free(buf);
 885   return new_buf;
 886 }
 887
 888 /* We sort the elements by placing them at their bit offset in an
 889    array where each entry represents one bit called permutation.  In
 890    fact, we do not place the values themselves, as we would have to
 891    copy two things, the value and the path.  We only remember the
 892    position in the old order. Each value should have a distinct
 893    position in the permutation.
 894
 895    A second iteration now permutes the actual elements into two
 896    new arrays. */
 897 void sort_compound_ent_values(entity *ent) {
 898   assert(get_type_state(get_entity_type(ent)) == layout_fixed);
 899
 900   type *tp = get_entity_type(ent);
 901   int i, n_vals = get_compound_ent_n_values(ent);
 902   int tp_size = get_type_size_bits(tp);
 903   int size;
 904   int *permutation;
 905
 906   if (!is_compound_type(tp)                           ||
 907       (ent->variability == variability_uninitialized) ||
 908       (get_type_state(tp) != layout_fixed)            ||
 909       (n_vals == 0)                                     ) return;
 910
 911   /* estimated upper bound for size. Better: use flexible array ... */
 912   size = ((tp_size > (n_vals * 32)) ? tp_size : (n_vals * 32)) * 4;
 913   permutation = (int *)calloc(size, 4);
 914   for (i = 0; i < n_vals; ++i) {
 915     int pos = get_compound_ent_value_offset_bits(ent, i);
 916     while (pos >= size) {
 917       size = size + size;
 918       permutation = resize(permutation, size);
 919     }
 920     assert(pos < size);
 921     assert(permutation[pos] == 0 && "two values with the same offset");
 922     permutation[pos] = i + 1;         /* We initialized with 0, so we can not distinguish entry 0.
 923                                          So inc all entries by one. */
 924     //fprintf(stderr, "i: %d, pos: %d \n", i, pos);
 925   }
 926
 927   int next = 0;
 928   ir_node **my_values = NEW_ARR_F(ir_node *, n_vals);
 929   compound_graph_path **my_paths  = NEW_ARR_F(compound_graph_path *, n_vals);
 930   for (i = 0; i < size; ++i) {
 931     int pos = permutation[i];
 932     if (pos) {
 933       //fprintf(stderr, "pos: %d i: %d  next %d \n", i, pos, next);
 934       assert(next < n_vals);
 935       pos--;   /* We increased the pos by one */
 936       my_values[next] = get_compound_ent_value     (ent, pos);
 937       my_paths [next] = get_compound_ent_value_path(ent, pos);
 938       next++;
 939     }
 940   }
 941   free(permutation);
 942
 943   DEL_ARR_F(ent->values);
 944   ent->values = my_values;
 945   DEL_ARR_F(ent->val_paths);
 946   ent->val_paths = my_paths;
 947 }
 948
 949 int
 950 (get_entity_offset_bytes)(entity *ent) {
 951   return __get_entity_offset_bytes(ent);
 952 }
 953
 954 int
 955 (get_entity_offset_bits)(entity *ent) {
 956   return __get_entity_offset_bits(ent);
 957 }
 958
 959 void
 960 (set_entity_offset_bytes)(entity *ent, int offset) {
 961   __set_entity_offset_bytes(ent, offset);
 962 }
 963
 964 void
 965 (set_entity_offset_bits)(entity *ent, int offset) {
 966   __set_entity_offset_bits(ent, offset);
 967 }
 968
 969 void
 970 add_entity_overwrites(entity *ent, entity *overwritten) {
 971   assert(ent && is_class_type(get_entity_owner(ent)));
 972   ARR_APP1(entity *, ent->overwrites, overwritten);
 973   ARR_APP1(entity *, overwritten->overwrittenby, ent);
 974 }
 975
 976 int
 977 get_entity_n_overwrites(entity *ent) {
 978   assert(ent && is_class_type(get_entity_owner(ent)));
 979   return (ARR_LEN(ent->overwrites));
 980 }
 981
 982 int
 983 get_entity_overwrites_index(entity *ent, entity *overwritten) {
 984   int i;
 985   assert(ent && is_class_type(get_entity_owner(ent)));
 986   for (i = 0; i < get_entity_n_overwrites(ent); i++)
 987     if (get_entity_overwrites(ent, i) == overwritten)
 988       return i;
 989   return -1;
 990 }
 991
 992 entity *
 993 get_entity_overwrites   (entity *ent, int pos) {
 994   assert(ent && is_class_type(get_entity_owner(ent)));
 995   assert(pos < get_entity_n_overwrites(ent));
 996   return ent->overwrites[pos];
 997 }
 998
 999 void
1000 set_entity_overwrites   (entity *ent, int pos, entity *overwritten) {
1001   assert(ent && is_class_type(get_entity_owner(ent)));
1002   assert(pos < get_entity_n_overwrites(ent));
1003   ent->overwrites[pos] = overwritten;
1004 }
1005
1006 void
1007 remove_entity_overwrites(entity *ent, entity *overwritten) {
1008   int i;
1009   assert(ent && is_class_type(get_entity_owner(ent)));
1010   for (i = 0; i < (ARR_LEN (ent->overwrites)); i++)
1011     if (ent->overwrites[i] == overwritten) {
1012       for(; i < (ARR_LEN (ent->overwrites))-1; i++)
1013     ent->overwrites[i] = ent->overwrites[i+1];
1014       ARR_SETLEN(entity*, ent->overwrites, ARR_LEN(ent->overwrites) - 1);
1015       break;
1016     }
1017 }
1018
1019 void
1020 add_entity_overwrittenby   (entity *ent, entity *overwrites) {
1021   assert(ent && is_class_type(get_entity_owner(ent)));
1022   add_entity_overwrites(overwrites, ent);
1023 }
1024
1025 int
1026 get_entity_n_overwrittenby (entity *ent) {
1027   assert(ent && is_class_type(get_entity_owner(ent)));
1028   return (ARR_LEN (ent->overwrittenby));
1029 }
1030
1031 int
1032 get_entity_overwrittenby_index(entity *ent, entity *overwrites) {
1033   int i;
1034   assert(ent && is_class_type(get_entity_owner(ent)));
1035   for (i = 0; i < get_entity_n_overwrittenby(ent); i++)
1036     if (get_entity_overwrittenby(ent, i) == overwrites)
1037       return i;
1038   return -1;
1039 }
1040
1041 entity *
1042 get_entity_overwrittenby   (entity *ent, int pos) {
1043   assert(ent && is_class_type(get_entity_owner(ent)));
1044   assert(pos < get_entity_n_overwrittenby(ent));
1045   return ent->overwrittenby[pos];
1046 }
1047
1048 void
1049 set_entity_overwrittenby   (entity *ent, int pos, entity *overwrites) {
1050   assert(ent && is_class_type(get_entity_owner(ent)));
1051   assert(pos < get_entity_n_overwrittenby(ent));
1052   ent->overwrittenby[pos] = overwrites;
1053 }
1054
1055 void    remove_entity_overwrittenby(entity *ent, entity *overwrites) {
1056   int i;
1057   assert(ent  && is_class_type(get_entity_owner(ent)));
1058   for (i = 0; i < (ARR_LEN (ent->overwrittenby)); i++)
1059     if (ent->overwrittenby[i] == overwrites) {
1060       for(; i < (ARR_LEN (ent->overwrittenby))-1; i++)
1061     ent->overwrittenby[i] = ent->overwrittenby[i+1];
1062       ARR_SETLEN(entity*, ent->overwrittenby, ARR_LEN(ent->overwrittenby) - 1);
1063       break;
1064     }
1065 }
1066
1067 /* A link to store intermediate information */
1068 void *
1069 (get_entity_link)(entity *ent) {
1070   return __get_entity_link(ent);
1071 }
1072
1073 void
1074 (set_entity_link)(entity *ent, void *l) {
1075   __set_entity_link(ent, l);
1076 }
1077
1078 ir_graph *
1079 (get_entity_irg)(entity *ent) {
1080   return __get_entity_irg(ent);
1081 }
1082
1083 void
1084 set_entity_irg(entity *ent, ir_graph *irg) {
1085   assert(ent && is_method_type(get_entity_type(ent)));
1086   /* Wie kann man die Referenz auf einen IRG löschen, z.B. wenn die
1087    * Methode selbst nicht mehr aufgerufen werden kann, die Entität
1088    * aber erhalten bleiben soll. */
1089   /* assert(irg); */
1090   assert((irg  && ent->peculiarity == peculiarity_existent) ||
1091          (!irg && ent->peculiarity == peculiarity_description) ||
1092          (!irg && ent->peculiarity == peculiarity_inherited));
1093   ent->irg = irg;
1094 }
1095
1096 int
1097 (is_entity)(void *thing) {
1098   return __is_entity(thing);
1099 }
1100
1101 int is_atomic_entity(entity *ent) {
1102   type* t = get_entity_type(ent);
1103   assert(ent && ent->kind == k_entity);
1104   return (is_primitive_type(t) || is_pointer_type(t) ||
1105       is_enumeration_type(t) || is_method_type(t));
1106 }
1107
1108 int is_compound_entity(entity *ent) {
1109   type* t = get_entity_type(ent);
1110   assert(ent && ent->kind == k_entity);
1111   return (is_class_type(t) || is_struct_type(t) ||
1112       is_array_type(t) || is_union_type(t));
1113 }
1114
1115 /**
1116  * @todo not implemnted!!! */
1117 bool equal_entity(entity *ent1, entity *ent2) {
1118   fprintf(stderr, " calling unimplemented equal entity!!! \n");
1119   return true;
1120 }
1121
1122
1123 unsigned long get_entity_visited(entity *ent) {
1124   assert(ent && ent->kind == k_entity);
1125   return ent->visit;
1126 }
1127 void        set_entity_visited(entity *ent, unsigned long num) {
1128   assert(ent && ent->kind == k_entity);
1129   ent->visit = num;
1130 }
1131 /* Sets visited field in entity to entity_visited. */
1132 void        mark_entity_visited(entity *ent) {
1133   assert(ent && ent->kind == k_entity);
1134   ent->visit = type_visited;
1135 }
1136
1137
1138 bool entity_visited(entity *ent) {
1139   assert(ent && ent->kind == k_entity);
1140   return get_entity_visited(ent) >= type_visited;
1141 }
1142
1143 bool entity_not_visited(entity *ent) {
1144   assert(ent && ent->kind == k_entity);
1145   return get_entity_visited(ent) < type_visited;
1146 }
1147
1148 /* Need two routines because I want to assert the result. */
1149 static entity *resolve_ent_polymorphy2 (type *dynamic_class, entity* static_ent) {
1150   int i, n_overwrittenby;
1151   entity *res = NULL;
1152
1153   if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
1154
1155   n_overwrittenby = get_entity_n_overwrittenby(static_ent);
1156   for (i = 0; i < n_overwrittenby; ++i) {
1157     res = resolve_ent_polymorphy2(dynamic_class, get_entity_overwrittenby(static_ent, i));
1158     if (res) break;
1159   }
1160
1161   return res;
1162 }
1163
1164 /** Resolve polymorphy in the inheritance relation.
1165  *
1166  * Returns the dynamically referenced entity if the static entity and the
1167  * dynamic type are given.
1168  * Search downwards in overwritten tree. */
1169 entity *resolve_ent_polymorphy(type *dynamic_class, entity* static_ent) {
1170   entity *res;
1171   assert(static_ent && static_ent->kind == k_entity);
1172
1173   res = resolve_ent_polymorphy2(dynamic_class, static_ent);
1174   if (!res) {
1175     printf(" Could not find entity "); DDME(static_ent);
1176     printf("  in "); DDMT(dynamic_class);
1177     printf("\n");
1178     dump_entity(static_ent);
1179     dump_type(get_entity_owner(static_ent));
1180     dump_type(dynamic_class);
1181   }
1182   assert(res);
1183   return res;
1184 }
1185
1186
1187
1188 /*******************************************************************/
1189 /** Debug aides                                                   **/
1190 /*******************************************************************/
1191
1192
1193 #if 1 || DEBUG_libfirm
1194 int dump_node_opcode(FILE *F, ir_node *n); /* from irdump.c */
1195
1196 #define X(a)    case a: printf(#a); break
1197 void dump_entity (entity *ent) {
1198   int i, j;
1199   type *owner = get_entity_owner(ent);
1200   type *type  = get_entity_type(ent);
1201   assert(ent && ent->kind == k_entity);
1202   printf("entity %s (%ld)\n", get_entity_name(ent), get_entity_nr(ent));
1203   printf("  type:  %s (%ld)\n", get_type_name(type),  get_type_nr(type));
1204   printf("  owner: %s (%ld)\n", get_type_name(owner), get_type_nr(owner));
1205
1206   if (get_entity_n_overwrites(ent) > 0) {
1207     printf("  overwrites:\n");
1208     for (i = 0; i < get_entity_n_overwrites(ent); ++i) {
1209       entity *ov = get_entity_overwrites(ent, i);
1210       printf("    %d: %s of class %s\n", i, get_entity_name(ov), get_type_name(get_entity_owner(ov)));
1211     }
1212   } else {
1213     printf("  Does not overwrite other entities. \n");
1214   }
1215   if (get_entity_n_overwrittenby(ent) > 0) {
1216     printf("  overwritten by:\n");
1217     for (i = 0; i < get_entity_n_overwrittenby(ent); ++i) {
1218       entity *ov = get_entity_overwrittenby(ent, i);
1219       printf("    %d: %s of class %s\n", i, get_entity_name(ov), get_type_name(get_entity_owner(ov)));
1220     }
1221   } else {
1222     printf("  Is not overwriten by other entities. \n");
1223   }
1224
1225   printf("  allocation:  ");
1226   switch (get_entity_allocation(ent)) {
1227     X(allocation_dynamic);
1228     X(allocation_automatic);
1229     X(allocation_static);
1230     X(allocation_parameter);
1231   }
1232
1233   printf("\n  visibility:  ");
1234   switch (get_entity_visibility(ent)) {
1235     X(visibility_local);
1236     X(visibility_external_visible);
1237     X(visibility_external_allocated);
1238   }
1239
1240   printf("\n  variability: ");
1241   switch (get_entity_variability(ent)) {
1242     X(variability_uninitialized);
1243     X(variability_initialized);
1244     X(variability_part_constant);
1245     X(variability_constant);
1246   }
1247
1248   if (get_entity_variability(ent) != variability_uninitialized) {
1249     if (is_atomic_entity(ent)) {
1250       printf("\n  atomic value: ");
1251       dump_node_opcode(stdout, get_atomic_ent_value(ent));
1252     } else {
1253       printf("\n  compound values:");
1254       for (i = 0; i < get_compound_ent_n_values(ent); ++i) {
1255         compound_graph_path *path = get_compound_ent_value_path(ent, i);
1256         entity *ent0 = get_compound_graph_path_node(path, 0);
1257         printf("\n    %3d ", get_entity_offset_bits(ent0));
1258         if (get_type_state(type) == layout_fixed)
1259           printf("(%3d) ",   get_compound_ent_value_offset_bits(ent, i));
1260         printf("%s", get_entity_name(ent0));
1261         for (j = 0; j < get_compound_graph_path_length(path); ++j) {
1262           entity *node = get_compound_graph_path_node(path, j);
1263           printf(".%s", get_entity_name(node));
1264           if (is_array_type(get_entity_owner(node)))
1265             printf("[%d]", get_compound_graph_path_array_index(path, j));
1266         }
1267         printf("\t = ");
1268         dump_node_opcode(stdout, get_compound_ent_value(ent, i));
1269       }
1270     }
1271   }
1272
1273   printf("\n  volatility:  ");
1274   switch (get_entity_volatility(ent)) {
1275     X(volatility_non_volatile);
1276     X(volatility_is_volatile);
1277   }
1278
1279   printf("\n  peculiarity: %s", get_peculiarity_string(get_entity_peculiarity(ent)));
1280   printf("\n  ld_name: %s", ent->ld_name ? get_entity_ld_name(ent) : "no yet set");
1281   printf("\n  offset:  %d", get_entity_offset_bits(ent));
1282   if (is_method_type(get_entity_type(ent))) {
1283     if (get_entity_irg(ent))   /* can be null */
1284       { printf("\n  irg = %ld", get_irg_graph_nr(get_entity_irg(ent))); }
1285     else
1286       { printf("\n  irg = NULL"); }
1287   }
1288   printf("\n\n");
1289 }
1290 #undef X
1291 #else  /* DEBUG_libfirm */
1292 void dump_entity (entity *ent) {}
1293 #endif /* DEBUG_libfirm */