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