nsz Git - libfirm/blob - ir/ana/cgana.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/cgana.c
   4  * Purpose:     Intraprozedural analyses to estimate the call graph.
   5  * Author:      Hubert Schmid
   6  * Modified by:
   7  * Created:     09.06.2002
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1999-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14  * Intraprozedurale Analyse zur Abschätzung der Aufrulrelation. Es
  15  * wird eine Menge von freien Methoden und anschließend die an den
  16  * Call-Operationen aufrufbaren Methoden bestimmt.
  17  *
  18  */
  19
  20 #include <stdlib.h>
  21 #include "cgana.h"
  22
  23
  24 #include "eset.h"
  25 #include "pmap.h"
  26 #include "array.h"
  27 #include "irprog.h"
  28 #include "irgwalk.h"
  29 #include "ircons.h"
  30 #include "irgmod.h"
  31 #include "irnode.h"
  32 #include "irflag.h"
  33
  34 #include "dbginfo_t.h"
  35
  36 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
  37  * Darstellung der unbekannten Methode. */
  38 static void * MARK = &MARK;
  39
  40
  41
  42 /* --- sel methods ---------------------------------------------------------- */
  43
  44
  45 static eset * entities = NULL;
  46
  47
  48 /* Bestimmt die eindeutige Methode, die die Methode für den
  49  * übergebenene (dynamischen) Typ überschreibt. */
  50 static entity * get_implementation(type * class, entity * method) {
  51   int i;
  52   if (get_entity_peculiarity(method) != description &&
  53       get_entity_owner(method) == class) {
  54     return method;
  55   }
  56   for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
  57     entity * e = get_entity_overwrittenby(method, i);
  58     if (get_entity_peculiarity(e) != description && get_entity_owner(e) == class) {
  59       return e;
  60     }
  61   }
  62   for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
  63     entity * e = get_implementation(get_class_supertype(class, i), method);
  64     if (e) {
  65       return e;
  66     }
  67   }
  68   assert(0 && "implemenation not found");
  69   return NULL;
  70 }
  71
  72 /* Returns the entity that contains the implementation of the inherited
  73    entity if available, else returns the entity passed. */
  74 entity *get_inherited_methods_implementation(entity *inh_meth) {
  75   entity *impl_meth = NULL;
  76   ir_node *addr = get_atomic_ent_value(inh_meth);
  77   assert(addr && "constant entity without value");
  78
  79   if (get_irn_op(addr) == op_Const) {
  80     impl_meth = tarval_to_entity(get_Const_tarval(addr));
  81   } else {
  82     assert(0 && "Complex constant values not supported -- adress of method should be straight constant!");
  83   }
  84   if (impl_meth && (get_entity_peculiarity(impl_meth) != existent)) {
  85     printf("this_meth: "); DDMEO(inh_meth);
  86     printf("impl meth: "); DDMEO(impl_meth);
  87     assert(!impl_meth || get_entity_peculiarity(impl_meth) == existent);
  88   }
  89   return impl_meth? impl_meth : inh_meth;
  90 }
  91
  92
  93 /* Collect the entity representing the implementation of this
  94    entity (not the same if inherited) and all entities for overwriting
  95    implementations in "set".
  96    If the implementation of the method is not included in the
  97    compilation unit "open" is set to true.
  98    A recursive descend in the overwritten relation.
  99    Cycle-free, therefore must terminate. */
 100 void collect_impls(entity *method, eset *set, int *size, bool *open) {
 101   int i;
 102   if (get_entity_peculiarity(method) == existent) {
 103     if (get_entity_visibility(method) == external_allocated) {
 104       assert(get_entity_irg(method) == NULL);
 105       *open = true;
 106     } else {
 107       assert(get_entity_irg(method) != NULL);
 108       if (!eset_contains(set, method)) {
 109         eset_insert(set, method);
 110         ++(*size);
 111       }
 112     }
 113   }
 114   if (get_entity_peculiarity(method) == inherited) {
 115     entity *impl_ent = get_inherited_methods_implementation(method);
 116     assert(impl_ent && "no implementation for inherited entity");
 117     if (get_entity_visibility(impl_ent) == external_allocated) {
 118       assert(get_entity_irg(impl_ent) == NULL);
 119       *open = true;
 120     } else {
 121       assert(get_entity_irg(impl_ent) != NULL);
 122       if (!eset_contains(set, impl_ent)) {
 123         eset_insert(set, impl_ent);
 124         ++(*size);
 125       }
 126     }
 127   }
 128   /** recursive descend **/
 129   for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
 130     collect_impls(get_entity_overwrittenby(method, i), set, size, open);
 131 }
 132
 133
 134 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
 135  * (und implementieren). In der zurückgegebenen Reihung kommt jede
 136  * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
 137  * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
 138  * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
 139  * keine Methoden, die die "method" überschreiben, so gibt die Methode
 140  * "NULL" zurück. */
 141 static entity ** get_impl_methods(entity * method) {
 142   eset * set = eset_create();
 143   int size = 0;
 144   entity ** arr;
 145   bool open = false;
 146
 147   /** Collect all method entities that can be called here **/
 148   collect_impls(method, set, &size, &open);
 149
 150 /**
 151      Vorgaenger einfuegen. **/
 152   if (size == 0 && !open) {
 153     /* keine implementierte überschriebene Methode */
 154     arr = NULL;
 155   } else if (open) {
 156     entity * ent;
 157     arr = NEW_ARR_F(entity *, size + 1);
 158     arr[0] = NULL;  /* Represents open method */
 159     for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
 160       arr[size] = ent;
 161   } else {
 162     entity * ent;
 163     arr = NEW_ARR_F(entity *, size);
 164     for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
 165       arr[size] = ent;
 166   }
 167   eset_destroy(set);
 168   return arr;
 169 }
 170
 171
 172 /* debug makros used in sel_methods_walker */
 173 #define SIZ(x)    sizeof(x)/sizeof((x)[0])
 174
 175 #define DBG_OPT_NORMALIZE                                                      \
 176           __dbg_info_merge_pair(new_node, node, dbg_const_eval)
 177 #define DBG_OPT_POLY_ALLOC                                                     \
 178   do {                                                                         \
 179         ir_node *ons[2];                                                       \
 180         ons[0] = node;                                                         \
 181         ons[1] = skip_Proj(get_Sel_ptr(node));                                 \
 182         __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
 183      } while(0)
 184 #define DBG_OPT_POLY                                                           \
 185           __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
 186
 187
 188 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
 189   if (get_irn_op(node) == op_SymConst) {
 190     /* Wenn möglich SymConst-Operation durch Const-Operation
 191      * ersetzen. */
 192     if (get_SymConst_kind(node) == linkage_ptr_info) {
 193       pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
 194       if (entry != NULL) { /* Method is declared in the compiled code */
 195         entity * ent = entry->value;
 196         if (get_opt_normalize() && (get_entity_visibility(ent) != external_allocated)) { /* Meth. is defined */
 197           ir_node *new_node;
 198           assert(get_entity_irg(ent));
 199           set_irg_current_block(current_ir_graph, get_nodes_Block(node));
 200           new_node = new_d_Const(get_irn_dbg_info(node),
 201                                  mode_P_mach, new_tarval_from_entity(ent, mode_P_mach));       DBG_OPT_NORMALIZE;
 202           exchange(node, new_node);
 203         }
 204       }
 205     }
 206   } else if (get_irn_op(node) == op_Sel &&
 207              is_method_type(get_entity_type(get_Sel_entity(node)))) {
 208     entity * ent = get_Sel_entity(node);
 209     if (get_optimize() && get_opt_dyn_meth_dispatch() &&
 210         (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
 211       ir_node *new_node;
 212       /* We know which method will be called, no dispatch necessary. */
 213       assert(get_entity_peculiarity(ent) != description);
 214       set_irg_current_block(current_ir_graph, get_nodes_Block(node));
 215       /* @@@ Is this correct?? Alloc could reference a subtype of the owner
 216          of Sel that overwrites the method referenced in Sel. */
 217       new_node = copy_const_value(get_atomic_ent_value(ent));              DBG_OPT_POLY_ALLOC;
 218       exchange (node, new_node);
 219     } else {
 220       assert(get_entity_peculiarity(ent) != inherited);
 221       if (!eset_contains(entities, ent)) {
 222         /* Entity noch nicht behandelt. Alle (intern oder extern)
 223          * implementierten Methoden suchen, die diese Entity
 224          * überschreiben. Die Menge an entity.link speichern. */
 225         set_entity_link(ent, get_impl_methods(ent));
 226         eset_insert(entities, ent);
 227       }
 228       if (get_entity_link(ent) == NULL) {
 229         /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
 230          * Methode zurückgeben. Damit ist sie insbesondere nicht
 231          * ausführbar und nicht erreichbar. */
 232         /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
 233            fuer die es keine Implementierung gibt. */
 234         if (get_entity_peculiarity(ent) == description) {
 235           /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
 236           printf("WARNING: Calling method description %s in method %s which has "
 237                   "no implementation!\n", id_to_str(get_entity_ident(ent)),
 238                   id_to_str(get_entity_ident(get_irg_ent(current_ir_graph))));
 239         } else {
 240           exchange(node, new_Bad());
 241         }
 242       } else {
 243         entity ** arr = get_entity_link(ent);
 244
 245 #if 0
 246         int i;
 247         printf("\nCall site "); DDMN(node);
 248         printf("  in "); DDME(get_irg_ent(current_ir_graph));
 249         printf("  can call:\n");
 250         for (i = 0; i < ARR_LEN(arr); i++) {
 251           printf("   - "); DDME(arr[i]);
 252           printf("     with owner "); DDMT(get_entity_owner(arr[i]));
 253         }
 254         printf("\n");
 255 #endif
 256
 257         if (get_optimize() && get_opt_dyn_meth_dispatch() &&
 258             (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
 259           ir_node *new_node;
 260           /* Die Sel-Operation kann immer nur einen Wert auf eine
 261            * interne Methode zurückgeben. Wir können daher die
 262            * Sel-Operation durch eine Const- bzw. SymConst-Operation
 263            * ersetzen. */
 264           set_irg_current_block(current_ir_graph, get_nodes_Block(node));
 265           new_node = copy_const_value(get_atomic_ent_value(arr[0]));         DBG_OPT_POLY;
 266           exchange (node, new_node);
 267         }
 268       }
 269     }
 270   }
 271 }
 272
 273
 274 /* Datenstruktur initialisieren. Zusätzlich werden alle
 275  * SymConst-Operationen, die auf interne Methoden verweisen, durch
 276  * Const-Operationen ersetzt. */
 277 static void sel_methods_init(void) {
 278   int i;
 279   pmap * ldname_map = pmap_create();
 280   assert(entities == NULL);
 281   entities = eset_create();
 282   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 283     entity * ent = get_irg_ent(get_irp_irg(i));
 284     /* Nur extern sichtbare Methode können überhaupt mit SymConst
 285      * aufgerufen werden. */
 286     if (get_entity_visibility(ent) != local) {
 287       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 288     }
 289   }
 290   all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
 291   pmap_destroy(ldname_map);
 292 }
 293
 294 /*****************************************************************************/
 295
 296 /* Datenstruktur freigeben. */
 297 static void sel_methods_dispose(void) {
 298   entity * ent;
 299   assert(entities);
 300   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 301     entity ** arr = get_entity_link(ent);
 302     if (arr) {
 303       DEL_ARR_F(arr);
 304     }
 305     set_entity_link(ent, NULL);
 306   }
 307   eset_destroy(entities);
 308   entities = NULL;
 309 }
 310
 311
 312 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
 313  * zurückgegeben werden können. Die Liste enthält keine doppelten
 314  * Einträge. */
 315 static entity ** get_Sel_arr(ir_node * sel) {
 316   static entity ** NULL_ARRAY = NULL;
 317   entity * ent;
 318   entity ** arr;
 319   assert(sel && get_irn_op(sel) == op_Sel);
 320   ent = get_Sel_entity(sel);
 321   assert(is_method_type(get_entity_type(ent))); /* what else? */
 322   arr = get_entity_link(ent);
 323   if (arr) {
 324     return arr;
 325   } else {
 326     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 327      * kann für polymorphe (abstrakte) Methoden passieren. */
 328     if (!NULL_ARRAY) {
 329       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 330     }
 331     return NULL_ARRAY;
 332   }
 333 }
 334
 335
 336 static int get_Sel_n_methods(ir_node * sel) {
 337   return ARR_LEN(get_Sel_arr(sel));
 338 }
 339
 340
 341 static entity * get_Sel_method(ir_node * sel, int pos) {
 342   entity ** arr = get_Sel_arr(sel);
 343   assert(pos >= 0 && pos < ARR_LEN(arr));
 344   return arr[pos];
 345 }
 346
 347
 348
 349 /* --- callee analysis ------------------------------------------------------ */
 350
 351
 352 static void callee_ana_node(ir_node * node, eset * methods);
 353
 354
 355 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 356   assert(get_irn_mode(node) == mode_T);
 357   if (get_irn_link(node) == MARK) {
 358     /* already visited */
 359     return;
 360   }
 361   set_irn_link(node, MARK);
 362
 363   switch (get_irn_opcode(node)) {
 364   case iro_Proj: {
 365     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 366      * op_Tuple oder ein Knoten, der eine "freie Methode"
 367      * zurückgibt. */
 368     ir_node * pred = get_Proj_pred(node);
 369     if (get_irn_link(pred) != MARK) {
 370       if (get_irn_op(pred) == op_Tuple) {
 371         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 372       } else {
 373         eset_insert(methods, MARK); /* free method -> unknown */
 374       }
 375     }
 376     break;
 377   }
 378
 379   case iro_Tuple:
 380     callee_ana_node(get_Tuple_pred(node, n), methods);
 381     break;
 382
 383   case iro_Id:
 384     callee_ana_proj(get_Id_pred(node), n, methods);
 385     break;
 386
 387   default:
 388     eset_insert(methods, MARK); /* free method -> unknown */
 389     break;
 390   }
 391
 392   set_irn_link(node, NULL);
 393 }
 394
 395
 396 static void callee_ana_node(ir_node * node, eset * methods) {
 397   int i;
 398
 399   assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
 400   /* rekursion verhindern */
 401   if (get_irn_link(node) == MARK) {
 402     /* already visited */
 403     return;
 404   }
 405   set_irn_link(node, MARK);
 406
 407   switch (get_irn_opcode(node)) {
 408   case iro_SymConst:
 409     /* externe Methode (wegen fix_symconst!) */
 410     eset_insert(methods, MARK); /* free method -> unknown */
 411     break;
 412
 413   case iro_Const: {
 414     /* interne Methode */
 415     entity * ent = tarval_to_entity(get_Const_tarval(node));
 416     assert(ent && is_method_type(get_entity_type(ent)));
 417     if (get_entity_visibility(ent) != external_allocated) {
 418       assert(get_entity_irg(ent));
 419       eset_insert(methods, ent);
 420     } else {
 421       eset_insert(methods, MARK); /* free method -> unknown */
 422     }
 423     break;
 424   }
 425
 426   case iro_Sel:
 427     /* polymorphe Methode */
 428     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 429       entity * ent = get_Sel_method(node, i);
 430       if (ent) {
 431         eset_insert(methods, ent);
 432       } else {
 433         eset_insert(methods, MARK);
 434       }
 435     }
 436     break;
 437
 438   case iro_Bad:
 439     /* nothing */
 440     break;
 441
 442   case iro_Phi: /* Vereinigung */
 443     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 444       callee_ana_node(get_Phi_pred(node, i), methods);
 445     }
 446     break;
 447
 448   case iro_Id:
 449     callee_ana_node(get_Id_pred(node), methods);
 450     break;
 451
 452   case iro_Proj:
 453     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 454     break;
 455
 456   case iro_Add:
 457   case iro_Sub:
 458   case iro_Conv:
 459     /* extern */
 460     eset_insert(methods, MARK); /* free method -> unknown */
 461     break;
 462
 463   default:
 464     assert(0 && "invalid opcode or opcode not implemented");
 465     break;
 466   }
 467
 468   set_irn_link(node, NULL);
 469 }
 470
 471
 472 static void callee_walker(ir_node * call, void * env) {
 473   if (get_irn_op(call) == op_Call) {
 474     eset * methods = eset_create();
 475     entity * ent;
 476     entity ** arr = NEW_ARR_F(entity *, 0);
 477     callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
 478     if (eset_contains(methods, MARK)) { /* unknown method */
 479       ARR_APP1(entity *, arr, NULL);
 480     }
 481     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 482       if (ent != MARK) {
 483         ARR_APP1(entity *, arr, ent);
 484       }
 485     }
 486     if (ARR_LEN(arr) == 0) {
 487       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 488        * Sel-Operation war, die keine Methoden zurückgeben
 489        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 490        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 491        * werden! */
 492       exchange(call, new_Bad());
 493     } else {
 494       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 495     }
 496     DEL_ARR_F(arr);
 497     eset_destroy(methods);
 498   }
 499 }
 500
 501
 502 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 503  * und speichert das Ergebnis in der Call-Operation. (siehe
 504  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 505  * muss bereits aufgebaut sein. */
 506 static void callee_ana(void) {
 507   int i;
 508   /* Alle Graphen analysieren. */
 509   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 510     irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
 511   }
 512 }
 513
 514
 515
 516 /* --- free method analysis ------------------------------------------------- */
 517
 518
 519 static void free_mark(ir_node * node, eset * set);
 520
 521 static void free_mark_proj(ir_node * node, long n, eset * set) {
 522   assert(get_irn_mode(node) == mode_T);
 523   if (get_irn_link(node) == MARK) {
 524     /* already visited */
 525     return;
 526   }
 527   set_irn_link(node, MARK);
 528   switch (get_irn_opcode(node)) {
 529   case iro_Proj: {
 530     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 531      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 532      * wird. */
 533     ir_node * pred = get_Proj_pred(node);
 534     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 535       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 536     } else {
 537       /* nothing: da in "free_ana_walker" behandelt. */
 538     }
 539     break;
 540   }
 541
 542   case iro_Tuple:
 543     free_mark(get_Tuple_pred(node, n), set);
 544     break;
 545
 546   case iro_Id:
 547     free_mark_proj(get_Id_pred(node), n, set);
 548     break;
 549
 550   case iro_Start:
 551   case iro_Alloc:
 552   case iro_Load:
 553     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 554      * behandelt. */
 555     break;
 556
 557   default:
 558     assert(0 && "unexpected opcode or opcode not implemented");
 559     break;
 560   }
 561   set_irn_link(node, NULL);
 562 }
 563
 564
 565 static void free_mark(ir_node * node, eset * set) {
 566   int i;
 567   assert(mode_is_reference(get_irn_mode(node)));
 568   if (get_irn_link(node) == MARK) {
 569     return; /* already visited */
 570   }
 571   set_irn_link(node, MARK);
 572   switch (get_irn_opcode(node)) {
 573   case iro_Sel: {
 574     entity * ent = get_Sel_entity(node);
 575     if (is_method_type(get_entity_type(ent))) {
 576       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 577         eset_insert(set, get_Sel_method(node, i));
 578       }
 579     }
 580     break;
 581   }
 582   case iro_SymConst:
 583     /* nothing: SymConst points to extern method */
 584     break;
 585   case iro_Const: {
 586     tarval * val = get_Const_tarval(node);
 587     if (tarval_is_entity(val)) { /* filter null pointer */
 588       entity * ent = tarval_to_entity(val);
 589       if (is_method_type(get_entity_type(ent))) {
 590         eset_insert(set, ent);
 591       }
 592     }
 593     break;
 594   }
 595   case iro_Phi:
 596     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 597       free_mark(get_Phi_pred(node, i), set);
 598     }
 599     break;
 600   case iro_Id:
 601     free_mark(get_Id_pred(node), set);
 602     break;
 603   case iro_Proj:
 604     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 605     break;
 606   default:
 607     /* nothing: Wird unten behandelt! */
 608     break;
 609   }
 610   set_irn_link(node, NULL);
 611 }
 612
 613
 614 static void free_ana_walker(ir_node * node, eset * set) {
 615   int i;
 616   if (get_irn_link(node) == MARK) {
 617     /* bereits in einem Zyklus besucht. */
 618     return;
 619   }
 620   switch (get_irn_opcode(node)) {
 621   /* special nodes */
 622   case iro_Sel:
 623   case iro_SymConst:
 624   case iro_Const:
 625   case iro_Phi:
 626   case iro_Id:
 627   case iro_Proj:
 628   case iro_Tuple:
 629     /* nothing */
 630     break;
 631   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 632    * Verräter ist. */
 633   case iro_Call:
 634     set_irn_link(node, MARK);
 635     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 636       ir_node * pred = get_Call_param(node, i);
 637       if (mode_is_reference(get_irn_mode(pred))) {
 638         free_mark(pred, set);
 639       }
 640     }
 641     break;
 642   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 643    * jemand das Gegenteil implementiert. */
 644   default:
 645     set_irn_link(node, MARK);
 646     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 647       ir_node * pred = get_irn_n(node, i);
 648       if (mode_is_reference(get_irn_mode(pred))) {
 649         free_mark(pred, set);
 650       }
 651     }
 652     break;
 653   }
 654   set_irn_link(node, NULL);
 655 }
 656
 657
 658 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 659  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 660  * SymConst-Operationen müssen in passende Const-Operationen
 661  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 662  * auf eine echt externe Methode.  */
 663 static entity ** get_free_methods(void) {
 664   eset * set = eset_create();
 665   int i;
 666   entity ** arr = NEW_ARR_F(entity *, 0);
 667   entity * ent;
 668   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 669     ir_graph * irg = get_irp_irg(i);
 670     entity * ent = get_irg_ent(irg);
 671     /* insert "external visible" methods. */
 672     if (get_entity_visibility(ent) != local) {
 673       eset_insert(set, ent);
 674     }
 675     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 676   }
 677   /* Hauptprogramm ist auch frei, auch wenn es nicht "external
 678    * visible" ist. */
 679   if(get_irp_main_irg()) {
 680     eset_insert(set, get_irg_ent(get_irp_main_irg()));
 681   }
 682   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 683     ARR_APP1(entity *, arr, ent);
 684   }
 685   eset_destroy(set);
 686
 687   return arr;
 688 }
 689
 690 void cgana(int *length, entity ***free_methods) {
 691   entity ** free_meths;
 692   int i;
 693
 694   sel_methods_init();
 695   free_meths = get_free_methods();
 696   callee_ana();
 697   sel_methods_dispose();
 698
 699   /* Convert the flexible array to an array that can be handled
 700      by standard C. */
 701   *length = ARR_LEN(free_meths);
 702   *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
 703   for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
 704   DEL_ARR_F(free_meths);
 705 }
 706
 707 /* Optimize the address expressions passed to call nodes.
 708  * Alle SymConst-Operationen, die auf interne Methoden verweisen,
 709  * werden durch Const-Operationen ersetzt.
 710  * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
 711  * durch Const ersetzt.
 712  * Sel Knoten, fuer die keine Implementierung existiert, werden
 713  * durch Bad ersetzt. */
 714 void opt_call_addrs(void) {
 715   sel_methods_init();
 716   sel_methods_dispose();
 717 #if 0
 718   int i;
 719   pmap * ldname_map = pmap_create();
 720   assert(entities == NULL);
 721   entities = eset_create();
 722   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 723     entity * ent = get_irg_ent(get_irp_irg(i));
 724     /* Nur extern sichtbare Methoden können überhaupt mit SymConst
 725      * aufgerufen werden. */
 726     if (get_entity_visibility(ent) != local) {
 727       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 728     }
 729   }
 730   all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
 731   pmap_destroy(ldname_map);
 732 #endif
 733 }