nsz Git - libfirm/blob - ir/tr/entity.c

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