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