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