nsz Git - libfirm/blob - ir/tr/entity.c

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