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 (node == NULL)
 619       /* Path not yet complete. */
 620       return true;
 621     if (get_entity_owner(node) != owner) return false;
 622     owner = get_entity_type(node);
 623   }
 624   if (pos == get_compound_graph_path_length(gr))
 625     if (!is_atomic_type(owner)) return false;
 626   return true;
 627 }
 628
 629 int
 630 get_compound_graph_path_length(compound_graph_path *gr) {
 631   assert(gr && is_compound_graph_path(gr));
 632   return gr->len;
 633 }
 634
 635 entity *
 636 get_compound_graph_path_node(compound_graph_path *gr, int pos) {
 637   assert(gr && is_compound_graph_path(gr));
 638   assert(pos >= 0 && pos < gr->len);
 639   return gr->nodes[pos];
 640 }
 641
 642 void
 643 set_compound_graph_path_node(compound_graph_path *gr, int pos, entity *node) {
 644   assert(gr && is_compound_graph_path(gr));
 645   assert(pos >= 0 && pos < gr->len);
 646   assert(is_entity(node));
 647   gr->nodes[pos] = node;
 648   assert(is_proper_compound_graph_path(gr, pos));
 649 }
 650
 651 int
 652 get_compound_graph_path_array_index(compound_graph_path *gr, int pos) {
 653   assert(gr && is_compound_graph_path(gr));
 654   assert(pos >= 0 && pos < gr->len);
 655   return gr->arr_indicees[pos];
 656 }
 657
 658 void
 659 set_compound_graph_path_array_index(compound_graph_path *gr, int pos, int index) {
 660   assert(gr && is_compound_graph_path(gr));
 661   assert(pos >= 0 && pos < gr->len);
 662   gr->arr_indicees[pos] = index;
 663 }
 664
 665 /* A value of a compound entity is a pair of value and the corresponding path to a member of
 666    the compound. */
 667 void
 668 add_compound_ent_value_w_path(entity *ent, ir_node *val, compound_graph_path *path) {
 669   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 670   ARR_APP1 (ir_node *, ent->values, val);
 671   ARR_APP1 (compound_graph_path *, ent->val_paths, path);
 672 }
 673
 674 void
 675 set_compound_ent_value_w_path(entity *ent, ir_node *val, compound_graph_path *path, int pos) {
 676   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 677   ent->values[pos] = val;
 678   ent->val_paths[pos] = path;
 679 }
 680
 681 int
 682 get_compound_ent_n_values(entity *ent) {
 683   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 684   return (ARR_LEN (ent->values));
 685 }
 686
 687 ir_node  *
 688 get_compound_ent_value(entity *ent, int pos) {
 689   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 690   return ent->values[pos];
 691 }
 692
 693 compound_graph_path *
 694 get_compound_ent_value_path(entity *ent, int pos) {
 695   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 696   return ent->val_paths[pos];
 697 }
 698
 699 void
 700 remove_compound_ent_value(entity *ent, entity *value_ent) {
 701   int i;
 702   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 703   for (i = 0; i < (ARR_LEN (ent->val_paths)); i++) {
 704     compound_graph_path *path = ent->val_paths[i];
 705     if (path->nodes[path->len-1] == value_ent) {
 706       for(; i < (ARR_LEN (ent->val_paths))-1; i++) {
 707         ent->val_paths[i] = ent->val_paths[i+1];
 708         ent->values[i]   = ent->values[i+1];
 709       }
 710       ARR_SETLEN(entity*,  ent->val_paths, ARR_LEN(ent->val_paths) - 1);
 711       ARR_SETLEN(ir_node*, ent->values,    ARR_LEN(ent->values)    - 1);
 712       break;
 713     }
 714   }
 715 }
 716
 717 void
 718 add_compound_ent_value(entity *ent, ir_node *val, entity *member) {
 719   compound_graph_path *path;
 720   type *owner_tp = get_entity_owner(ent);
 721   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 722   path = new_compound_graph_path(owner_tp, 1);
 723   path->nodes[0] = member;
 724   if (is_Array_type(owner_tp)) {
 725     int max;
 726     int i;
 727
 728     assert(get_array_n_dimensions(owner_tp) == 1 && has_array_lower_bound(owner_tp, 0));
 729     max = get_array_lower_bound_int(owner_tp, 0) -1;
 730     for (i = 0; i < get_compound_ent_n_values(ent); ++i) {
 731       int index = get_compound_graph_path_array_index(get_compound_ent_value_path(ent, i), 0);
 732       if (index > max) {
 733         max = index;
 734       }
 735     }
 736     path->arr_indicees[0] = max + 1;
 737   }
 738   add_compound_ent_value_w_path(ent, val, path);
 739 }
 740
 741 /* Copies the firm subgraph referenced by val to const_code_irg and adds
 742    the node as constant initialization to ent.
 743    The subgraph may not contain control flow operations.
 744 void
 745 copy_and_add_compound_ent_value(entity *ent, ir_node *val, entity *member) {
 746   ir_graph *rem = current_ir_graph;
 747
 748   assert(get_entity_variability(ent) != variability_uninitialized);
 749   current_ir_graph = get_const_code_irg();
 750
 751   val = copy_const_value(val);
 752   add_compound_ent_value(ent, val, member);
 753   current_ir_graph = rem;
 754   }*/
 755
 756 /* Copies the value i of the entity to current_block in current_ir_graph.
 757 ir_node *
 758 copy_compound_ent_value(entity *ent, int pos) {
 759   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 760   return copy_const_value(ent->values[pos+1]);
 761   }*/
 762
 763 entity   *
 764 get_compound_ent_value_member(entity *ent, int pos) {
 765   compound_graph_path *path;
 766   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 767   path = get_compound_ent_value_path(ent, pos);
 768
 769   return get_compound_graph_path_node(path, get_compound_graph_path_length(path)-1);
 770 }
 771
 772 void
 773 set_compound_ent_value(entity *ent, ir_node *val, entity *member, int pos) {
 774   compound_graph_path *path;
 775   assert(is_compound_entity(ent) && (ent->variability != variability_uninitialized));
 776   path = get_compound_ent_value_path(ent, pos);
 777   set_compound_graph_path_node(path, 0, member);
 778   set_compound_ent_value_w_path(ent, val, path, pos);
 779 }
 780
 781 void
 782 set_array_entity_values(entity *ent, tarval **values, int num_vals) {
 783   int i;
 784   ir_graph *rem = current_ir_graph;
 785   type *arrtp = get_entity_type(ent);
 786   ir_node *val;
 787   type *elttp = get_array_element_type(arrtp);
 788
 789   assert(is_Array_type(arrtp));
 790   assert(get_array_n_dimensions(arrtp) == 1);
 791   /* One bound is sufficient, the number of constant fields makes the
 792      size. */
 793   assert(get_array_lower_bound (arrtp, 0) || get_array_upper_bound (arrtp, 0));
 794   assert(get_entity_variability(ent) != variability_uninitialized);
 795   current_ir_graph = get_const_code_irg();
 796
 797   for (i = 0; i < num_vals; i++) {
 798     val = new_Const_type(values[i], elttp);
 799     add_compound_ent_value(ent, val, get_array_element_entity(arrtp));
 800     set_compound_graph_path_array_index(get_compound_ent_value_path(ent, i), 0, i);
 801   }
 802   current_ir_graph = rem;
 803 }
 804
 805 int  get_compound_ent_value_offset_bits(entity *ent, int pos) {
 806   compound_graph_path *path;
 807   int i, path_len;
 808   int offset = 0;
 809
 810   assert(get_type_state(get_entity_type(ent)) == layout_fixed);
 811
 812   path = get_compound_ent_value_path(ent, pos);
 813   path_len = get_compound_graph_path_length(path);
 814
 815   for (i = 0; i < path_len; ++i) {
 816     entity *node = get_compound_graph_path_node(path, i);
 817     type *node_tp = get_entity_type(node);
 818     type *owner_tp = get_entity_owner(node);
 819     if (is_Array_type(owner_tp)) {
 820       int size  = get_type_size_bits(node_tp);
 821       int align = get_type_alignment_bits(node_tp);
 822       if (size < align)
 823         size = align;
 824       else {
 825         assert(size % align == 0);
 826         /* ansonsten aufrunden */
 827       }
 828       offset += size * get_compound_graph_path_array_index(path, i);
 829     } else {
 830       offset += get_entity_offset_bits(node);
 831     }
 832   }
 833   return offset;
 834 }
 835
 836 int  get_compound_ent_value_offset_bytes(entity *ent, int pos) {
 837   int offset = get_compound_ent_value_offset_bits(ent, pos);
 838   assert(offset % 8 == 0);
 839   return offset >> 3;
 840 }
 841
 842
 843 static void init_index(type *arr) {
 844   int init;
 845   int dim = 0;
 846
 847   assert(get_array_n_dimensions(arr) == 1);
 848
 849   if (has_array_lower_bound(arr, dim))
 850     init = get_array_lower_bound_int(arr, 0) -1;
 851   else
 852     init = get_array_upper_bound_int(arr, 0) +1;
 853
 854   set_entity_link(get_array_element_entity(arr), (void *)init);
 855 }
 856
 857
 858 static int get_next_index(entity *elem_ent) {
 859   type *arr = get_entity_owner(elem_ent);
 860   int next;
 861   int dim = 0;
 862
 863   assert(get_array_n_dimensions(arr) == 1);
 864
 865   if (has_array_lower_bound(arr, dim)) {
 866     next = (int)get_entity_link(elem_ent) +1;
 867     if (has_array_upper_bound(arr, dim)) {
 868       int upper = get_array_upper_bound_int(arr, dim);
 869       if (next == upper) next = get_array_lower_bound_int(arr, dim);
 870     }
 871   } else {
 872     next = (int)get_entity_link(elem_ent) -1;
 873     if (has_array_lower_bound(arr, dim)) {
 874       int upper = get_array_upper_bound_int(arr, dim);
 875       if (next == upper) next = get_array_upper_bound_int(arr, dim);
 876     }
 877   }
 878
 879   set_entity_link(elem_ent, (void *)next);
 880   return next;
 881 }
 882
 883 /* Compute the array indices in compound graph paths of initialized entities.
 884  *
 885  *  All arrays must have fixed lower and upper bounds.  One array can
 886  *  have an open bound.  If there are several open bounds, we do
 887  *  nothing.  There must be initializer elements for all array
 888  *  elements.  Uses the link field in the array element entities.  The
 889  *  array bounds must be representable as ints.
 890  *
 891  *  (If the bounds are not representable as ints we have to represent
 892  *  the indices as firm nodes.  But the still we must be able to
 893  *  evaluate the index against the upper bound.)
 894  */
 895 void compute_compound_ent_array_indicees(entity *ent) {
 896   type *tp = get_entity_type(ent);
 897   int i, n_vals;
 898   entity *unknown_bound_entity = NULL;
 899
 900   if (!is_compound_type(tp) ||
 901       (ent->variability == variability_uninitialized)) return ;
 902
 903   n_vals = get_compound_ent_n_values(ent);
 904   if (n_vals == 0) return;
 905
 906   /* We can not compute the indexes if there is more than one array
 907      with an unknown bound.  For this remember the first entity that
 908      represents such an array. It could be ent. */
 909   if (is_Array_type(tp)) {
 910     int dim = 0;
 911
 912     assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
 913     if (!has_array_lower_bound(tp, dim) || !has_array_upper_bound(tp, dim))
 914      unknown_bound_entity = ent;
 915   }
 916
 917   /* Initialize the entity links to lower bound -1 and test all path elements
 918      for known bounds. */
 919   for (i = 0; i < n_vals; ++i) {
 920     compound_graph_path *path = get_compound_ent_value_path(ent, i);
 921     int j, path_len =  get_compound_graph_path_length(path);
 922     for (j = 0; j < path_len; ++j) {
 923       entity *node = get_compound_graph_path_node(path, j);
 924       type *elem_tp = get_entity_type(node);
 925
 926       if (is_Array_type(elem_tp)) {
 927         int dim = 0;
 928         assert(get_array_n_dimensions(elem_tp) == 1 && "other not implemented");
 929         if (!has_array_lower_bound(elem_tp, dim) || !has_array_upper_bound(elem_tp, dim)) {
 930           if (!unknown_bound_entity) unknown_bound_entity = node;
 931           if (node != unknown_bound_entity) return;
 932         }
 933
 934         init_index(elem_tp);
 935       }
 936     }
 937   }
 938
 939   /* Finally compute the indexes ... */
 940   for (i = 0; i < n_vals; ++i) {
 941     compound_graph_path *path = get_compound_ent_value_path(ent, i);
 942     int j, path_len =  get_compound_graph_path_length(path);
 943     for (j = 0; j < path_len; ++j) {
 944       entity *node = get_compound_graph_path_node(path, j);
 945       type *owner_tp = get_entity_owner(node);
 946       if (is_Array_type(owner_tp))
 947         set_compound_graph_path_array_index (path, j, get_next_index(node));
 948     }
 949   }
 950
 951 }
 952
 953 /** resize: double the allocated buffer */
 954 static int *resize (int *buf, int *size) {
 955   int new_size =  *size * 2;
 956   int *new_buf = xcalloc(new_size, sizeof(new_buf[0]));
 957   memcpy(new_buf, buf, *size);
 958   free(buf);
 959   *size = new_size;
 960   return new_buf;
 961 }
 962
 963 /* We sort the elements by placing them at their bit offset in an
 964    array where each entry represents one bit called permutation.  In
 965    fact, we do not place the values themselves, as we would have to
 966    copy two things, the value and the path.  We only remember the
 967    position in the old order. Each value should have a distinct
 968    position in the permutation.
 969
 970    A second iteration now permutes the actual elements into two
 971    new arrays. */
 972 void sort_compound_ent_values(entity *ent) {
 973   type *tp;
 974   int i, n_vals;
 975   int tp_size;
 976   int size;
 977   int *permutation;
 978
 979   int next;
 980   ir_node **my_values;
 981   compound_graph_path **my_paths;
 982
 983   assert(get_type_state(get_entity_type(ent)) == layout_fixed);
 984
 985   tp      = get_entity_type(ent);
 986   n_vals  = get_compound_ent_n_values(ent);
 987   tp_size = get_type_size_bits(tp);
 988
 989   if (!is_compound_type(tp)                           ||
 990       (ent->variability == variability_uninitialized) ||
 991       (get_type_state(tp) != layout_fixed)            ||
 992       (n_vals == 0)                                     ) return;
 993
 994   /* estimated upper bound for size. Better: use flexible array ... */
 995   size = ((tp_size > (n_vals * 32)) ? tp_size : (n_vals * 32)) * 4;
 996   permutation = xcalloc(size, sizeof(permutation[0]));
 997
 998   for (i = 0; i < n_vals; ++i) {
 999     int pos = get_compound_ent_value_offset_bits(ent, i);
1000     while (pos >= size) {
1001       permutation = resize(permutation, &size);
1002     }
1003     assert(pos < size);
1004     assert(permutation[pos] == 0 && "two values with the same offset");
1005     permutation[pos] = i + 1;         /* We initialized with 0, so we can not distinguish entry 0.
1006                      So inc all entries by one. */
1007     //fprintf(stderr, "i: %d, pos: %d \n", i, pos);
1008   }
1009
1010   next = 0;
1011   my_values = NEW_ARR_F(ir_node *, n_vals);
1012   my_paths  = NEW_ARR_F(compound_graph_path *, n_vals);
1013   for (i = 0; i < size; ++i) {
1014     int pos = permutation[i];
1015     if (pos) {
1016       //fprintf(stderr, "pos: %d i: %d  next %d \n", i, pos, next);
1017       assert(next < n_vals);
1018       pos--;   /* We increased the pos by one */
1019       my_values[next] = get_compound_ent_value     (ent, pos);
1020       my_paths [next] = get_compound_ent_value_path(ent, pos);
1021       next++;
1022     }
1023   }
1024   free(permutation);
1025
1026   DEL_ARR_F(ent->values);
1027   ent->values = my_values;
1028   DEL_ARR_F(ent->val_paths);
1029   ent->val_paths = my_paths;
1030 }
1031
1032 int
1033 (get_entity_offset_bytes)(const entity *ent) {
1034   return __get_entity_offset_bytes(ent);
1035 }
1036
1037 int
1038 (get_entity_offset_bits)(const entity *ent) {
1039   return __get_entity_offset_bits(ent);
1040 }
1041
1042 void
1043 (set_entity_offset_bytes)(entity *ent, int offset) {
1044   __set_entity_offset_bytes(ent, offset);
1045 }
1046
1047 void
1048 (set_entity_offset_bits)(entity *ent, int offset) {
1049   __set_entity_offset_bits(ent, offset);
1050 }
1051
1052 void
1053 add_entity_overwrites(entity *ent, entity *overwritten) {
1054   assert(ent && is_Class_type(get_entity_owner(ent)));
1055   ARR_APP1(entity *, ent->overwrites, overwritten);
1056   ARR_APP1(entity *, overwritten->overwrittenby, ent);
1057 }
1058
1059 int
1060 get_entity_n_overwrites(entity *ent) {
1061   assert(ent && is_Class_type(get_entity_owner(ent)));
1062   return (ARR_LEN(ent->overwrites));
1063 }
1064
1065 int
1066 get_entity_overwrites_index(entity *ent, entity *overwritten) {
1067   int i;
1068   assert(ent && is_Class_type(get_entity_owner(ent)));
1069   for (i = 0; i < get_entity_n_overwrites(ent); i++)
1070     if (get_entity_overwrites(ent, i) == overwritten)
1071       return i;
1072   return -1;
1073 }
1074
1075 entity *
1076 get_entity_overwrites   (entity *ent, int pos) {
1077   assert(ent && is_Class_type(get_entity_owner(ent)));
1078   assert(pos < get_entity_n_overwrites(ent));
1079   return ent->overwrites[pos];
1080 }
1081
1082 void
1083 set_entity_overwrites   (entity *ent, int pos, entity *overwritten) {
1084   assert(ent && is_Class_type(get_entity_owner(ent)));
1085   assert(pos < get_entity_n_overwrites(ent));
1086   ent->overwrites[pos] = overwritten;
1087 }
1088
1089 void
1090 remove_entity_overwrites(entity *ent, entity *overwritten) {
1091   int i;
1092   assert(ent && is_Class_type(get_entity_owner(ent)));
1093   for (i = 0; i < (ARR_LEN (ent->overwrites)); i++)
1094     if (ent->overwrites[i] == overwritten) {
1095       for(; i < (ARR_LEN (ent->overwrites))-1; i++)
1096     ent->overwrites[i] = ent->overwrites[i+1];
1097       ARR_SETLEN(entity*, ent->overwrites, ARR_LEN(ent->overwrites) - 1);
1098       break;
1099     }
1100 }
1101
1102 void
1103 add_entity_overwrittenby   (entity *ent, entity *overwrites) {
1104   assert(ent && is_Class_type(get_entity_owner(ent)));
1105   add_entity_overwrites(overwrites, ent);
1106 }
1107
1108 int
1109 get_entity_n_overwrittenby (entity *ent) {
1110   assert(ent && is_Class_type(get_entity_owner(ent)));
1111   return (ARR_LEN (ent->overwrittenby));
1112 }
1113
1114 int
1115 get_entity_overwrittenby_index(entity *ent, entity *overwrites) {
1116   int i;
1117   assert(ent && is_Class_type(get_entity_owner(ent)));
1118   for (i = 0; i < get_entity_n_overwrittenby(ent); i++)
1119     if (get_entity_overwrittenby(ent, i) == overwrites)
1120       return i;
1121   return -1;
1122 }
1123
1124 entity *
1125 get_entity_overwrittenby   (entity *ent, int pos) {
1126   assert(ent && is_Class_type(get_entity_owner(ent)));
1127   assert(pos < get_entity_n_overwrittenby(ent));
1128   return ent->overwrittenby[pos];
1129 }
1130
1131 void
1132 set_entity_overwrittenby   (entity *ent, int pos, entity *overwrites) {
1133   assert(ent && is_Class_type(get_entity_owner(ent)));
1134   assert(pos < get_entity_n_overwrittenby(ent));
1135   ent->overwrittenby[pos] = overwrites;
1136 }
1137
1138 void    remove_entity_overwrittenby(entity *ent, entity *overwrites) {
1139   int i;
1140   assert(ent  && is_Class_type(get_entity_owner(ent)));
1141   for (i = 0; i < (ARR_LEN (ent->overwrittenby)); i++)
1142     if (ent->overwrittenby[i] == overwrites) {
1143       for(; i < (ARR_LEN (ent->overwrittenby))-1; i++)
1144     ent->overwrittenby[i] = ent->overwrittenby[i+1];
1145       ARR_SETLEN(entity*, ent->overwrittenby, ARR_LEN(ent->overwrittenby) - 1);
1146       break;
1147     }
1148 }
1149
1150 /* A link to store intermediate information */
1151 void *
1152 (get_entity_link)(const entity *ent) {
1153   return __get_entity_link(ent);
1154 }
1155
1156 void
1157 (set_entity_link)(entity *ent, void *l) {
1158   __set_entity_link(ent, l);
1159 }
1160
1161 ir_graph *
1162 (get_entity_irg)(const entity *ent) {
1163   return __get_entity_irg(ent);
1164 }
1165
1166 void
1167 set_entity_irg(entity *ent, ir_graph *irg) {
1168   assert(ent && is_Method_type(get_entity_type(ent)));
1169   /* Wie kann man die Referenz auf einen IRG löschen, z.B. wenn die
1170    * Methode selbst nicht mehr aufgerufen werden kann, die Entität
1171    * aber erhalten bleiben soll?  Wandle die Entitaet in description oder
1172    * inherited um! */
1173   /* assert(irg); */
1174   assert((irg  && ent->peculiarity == peculiarity_existent) ||
1175          (!irg && (ent->peculiarity == peculiarity_existent)
1176           && (ent -> visibility == visibility_external_allocated)) ||
1177          (!irg && ent->peculiarity == peculiarity_description) ||
1178          (!irg && ent->peculiarity == peculiarity_inherited));
1179   ent->irg = irg;
1180 }
1181
1182 int
1183 (is_entity)(const void *thing) {
1184   return __is_entity(thing);
1185 }
1186
1187 int is_atomic_entity(entity *ent) {
1188   type* t = get_entity_type(ent);
1189   assert(ent && ent->kind == k_entity);
1190   return (is_Primitive_type(t) || is_Pointer_type(t) ||
1191       is_Enumeration_type(t) || is_Method_type(t));
1192 }
1193
1194 int is_compound_entity(entity *ent) {
1195   type* t = get_entity_type(ent);
1196   assert(ent && ent->kind == k_entity);
1197   return (is_Class_type(t) || is_Struct_type(t) ||
1198       is_Array_type(t) || is_Union_type(t));
1199 }
1200
1201 /**
1202  * @todo not implemented!!! */
1203 bool equal_entity(entity *ent1, entity *ent2) {
1204   fprintf(stderr, " calling unimplemented equal entity!!! \n");
1205   return true;
1206 }
1207
1208
1209 unsigned long get_entity_visited(entity *ent) {
1210   assert(ent && ent->kind == k_entity);
1211   return ent->visit;
1212 }
1213 void        set_entity_visited(entity *ent, unsigned long num) {
1214   assert(ent && ent->kind == k_entity);
1215   ent->visit = num;
1216 }
1217 /* Sets visited field in entity to entity_visited. */
1218 void        mark_entity_visited(entity *ent) {
1219   assert(ent && ent->kind == k_entity);
1220   ent->visit = type_visited;
1221 }
1222
1223
1224 bool entity_visited(entity *ent) {
1225   assert(ent && ent->kind == k_entity);
1226   return get_entity_visited(ent) >= type_visited;
1227 }
1228
1229 bool entity_not_visited(entity *ent) {
1230   assert(ent && ent->kind == k_entity);
1231   return get_entity_visited(ent) < type_visited;
1232 }
1233
1234 /* Need two routines because I want to assert the result. */
1235 static entity *resolve_ent_polymorphy2 (type *dynamic_class, entity *static_ent) {
1236   int i, n_overwrittenby;
1237   entity *res = NULL;
1238
1239   if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
1240
1241   n_overwrittenby = get_entity_n_overwrittenby(static_ent);
1242   for (i = 0; i < n_overwrittenby; ++i) {
1243     res = resolve_ent_polymorphy2(dynamic_class, get_entity_overwrittenby(static_ent, i));
1244     if (res)
1245       break;
1246   }
1247
1248   return res;
1249 }
1250
1251 /** Resolve polymorphy in the inheritance relation.
1252  *
1253  * Returns the dynamically referenced entity if the static entity and the
1254  * dynamic type are given.
1255  * Search downwards in overwritten tree. */
1256 entity *resolve_ent_polymorphy(type *dynamic_class, entity *static_ent) {
1257   entity *res;
1258   assert(static_ent && static_ent->kind == k_entity);
1259
1260   res = resolve_ent_polymorphy2(dynamic_class, static_ent);
1261 #if DEBUG_libfirm
1262   if (!res) {
1263     printf(" Could not find entity "); DDME(static_ent);
1264     printf("  in "); DDMT(dynamic_class);
1265     printf("\n");
1266     dump_entity(static_ent);
1267     dump_type(get_entity_owner(static_ent));
1268     dump_type(dynamic_class);
1269   }
1270 #endif
1271   assert(res);
1272   return res;
1273 }