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