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