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