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