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