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