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