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