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