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 (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 (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 (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         (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 && 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 (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 (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 (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 (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());  invalid firm */
 510
 511       ir_node *mem = get_Call_mem(call);
 512       turn_into_tuple (call, pn_Call_max);
 513       set_Tuple_pred(call, pn_Call_M_regular       , mem);
 514       set_Tuple_pred(call, pn_Call_T_result        , new_Bad());
 515       set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
 516       set_Tuple_pred(call, pn_Call_X_except        , new_Bad());  /* new_Jmp() ?? new_Raise() ?? */
 517       set_Tuple_pred(call, pn_Call_M_except        , mem);
 518
 519     } else {
 520       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 521     }
 522     DEL_ARR_F(arr);
 523     eset_destroy(methods);
 524   }
 525 }
 526
 527
 528 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 529  * und speichert das Ergebnis in der Call-Operation. (siehe
 530  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 531  * muss bereits aufgebaut sein. */
 532 static void callee_ana(void) {
 533   int i;
 534   /* Alle Graphen analysieren. */
 535   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 536     irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
 537     set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
 538   }
 539 }
 540
 541
 542
 543 /* --- free method analysis ------------------------------------------------- */
 544
 545
 546 static void free_mark(ir_node * node, eset * set);
 547
 548 static void free_mark_proj(ir_node * node, long n, eset * set) {
 549   assert(get_irn_mode(node) == mode_T);
 550   if (get_irn_link(node) == MARK) {
 551     /* already visited */
 552     return;
 553   }
 554   set_irn_link(node, MARK);
 555   switch (get_irn_opcode(node)) {
 556   case iro_Proj: {
 557     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 558      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 559      * wird. */
 560     ir_node * pred = get_Proj_pred(node);
 561     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 562       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 563     } else {
 564       /* nothing: da in "free_ana_walker" behandelt. */
 565     }
 566     break;
 567   }
 568
 569   case iro_Tuple:
 570     free_mark(get_Tuple_pred(node, n), set);
 571     break;
 572
 573   case iro_Id:
 574     free_mark_proj(get_Id_pred(node), n, set);
 575     break;
 576
 577   case iro_Start:
 578   case iro_Alloc:
 579   case iro_Load:
 580     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 581      * behandelt. */
 582     break;
 583
 584   default:
 585     assert(0 && "unexpected opcode or opcode not implemented");
 586     break;
 587   }
 588   set_irn_link(node, NULL);
 589 }
 590
 591
 592 static void free_mark(ir_node * node, eset * set) {
 593   int i;
 594   assert(mode_is_reference(get_irn_mode(node)));
 595   if (get_irn_link(node) == MARK) {
 596     return; /* already visited */
 597   }
 598   set_irn_link(node, MARK);
 599   switch (get_irn_opcode(node)) {
 600   case iro_Sel: {
 601     entity * ent = get_Sel_entity(node);
 602     if (is_method_type(get_entity_type(ent))) {
 603       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 604     eset_insert(set, get_Sel_method(node, i));
 605       }
 606     }
 607     break;
 608   }
 609   case iro_SymConst:
 610     /* nothing: SymConst points to extern method */
 611     break;
 612   case iro_Const: {
 613     tarval * val = get_Const_tarval(node);
 614     if (tarval_is_entity(val)) { /* filter null pointer */
 615       entity * ent = tarval_to_entity(val);
 616       if (is_method_type(get_entity_type(ent))) {
 617         eset_insert(set, ent);
 618       }
 619     }
 620     break;
 621   }
 622   case iro_Phi:
 623     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 624       free_mark(get_Phi_pred(node, i), set);
 625     }
 626     break;
 627   case iro_Id:
 628     free_mark(get_Id_pred(node), set);
 629     break;
 630   case iro_Proj:
 631     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 632     break;
 633   default:
 634     /* nothing: Wird unten behandelt! */
 635     break;
 636   }
 637   set_irn_link(node, NULL);
 638 }
 639
 640
 641 static void free_ana_walker(ir_node * node, eset * set) {
 642   int i;
 643   if (get_irn_link(node) == MARK) {
 644     /* bereits in einem Zyklus besucht. */
 645     return;
 646   }
 647   switch (get_irn_opcode(node)) {
 648   /* special nodes */
 649   case iro_Sel:
 650   case iro_SymConst:
 651   case iro_Const:
 652   case iro_Phi:
 653   case iro_Id:
 654   case iro_Proj:
 655   case iro_Tuple:
 656     /* nothing */
 657     break;
 658   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 659    * Verräter ist. */
 660   case iro_Call:
 661     set_irn_link(node, MARK);
 662     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 663       ir_node * pred = get_Call_param(node, i);
 664       if (mode_is_reference(get_irn_mode(pred))) {
 665     free_mark(pred, set);
 666       }
 667     }
 668     break;
 669   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 670    * jemand das Gegenteil implementiert. */
 671   default:
 672     set_irn_link(node, MARK);
 673     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 674       ir_node * pred = get_irn_n(node, i);
 675       if (mode_is_reference(get_irn_mode(pred))) {
 676         free_mark(pred, set);
 677       }
 678     }
 679     break;
 680   }
 681   set_irn_link(node, NULL);
 682 }
 683
 684
 685 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 686  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 687  * SymConst-Operationen müssen in passende Const-Operationen
 688  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 689  * auf eine echt externe Methode.  */
 690 static entity ** get_free_methods(void) {
 691   eset * set = eset_create();
 692   int i;
 693   entity ** arr = NEW_ARR_F(entity *, 0);
 694   entity * ent;
 695
 696   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 697     ir_graph * irg = get_irp_irg(i);
 698     entity * ent = get_irg_ent(irg);
 699     /* insert "external visible" methods. */
 700     if (get_entity_visibility(ent) != visibility_local) {
 701       eset_insert(set, ent);
 702     }
 703     /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
 704        z.B. da die Adresse einer Methode abgespeichert wird. */
 705     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 706   }
 707   /* Hauptprogramm ist auch dann frei, wenn es nicht "external
 708    * visible" ist. */
 709   if (get_irp_main_irg()) {
 710     eset_insert(set, get_irg_ent(get_irp_main_irg()));
 711   }
 712   /* Wandle Menge in Feld um.  Effizienter. */
 713   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 714     ARR_APP1(entity *, arr, ent);
 715   }
 716   eset_destroy(set);
 717
 718   return arr;
 719 }
 720
 721 void cgana(int *length, entity ***free_methods) {
 722   entity ** free_meths;
 723   int i;
 724
 725   sel_methods_init();
 726   free_meths = get_free_methods();
 727   callee_ana();
 728   sel_methods_dispose();
 729
 730   /* Convert the flexible array to an array that can be handled
 731      by standard C. */
 732   *length = ARR_LEN(free_meths);
 733   *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
 734   for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
 735   DEL_ARR_F(free_meths);
 736 }
 737
 738 /* Optimize the address expressions passed to call nodes.
 739  * Alle SymConst-Operationen, die auf interne Methoden verweisen,
 740  * werden durch Const-Operationen ersetzt.
 741  * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
 742  * durch Const ersetzt.
 743  * Sel Knoten, fuer die keine Implementierung existiert, werden
 744  * durch Bad ersetzt. */
 745 void opt_call_addrs(void) {
 746   sel_methods_init();
 747   sel_methods_dispose();
 748 #if 0
 749   int i;
 750   pmap * ldname_map = pmap_create();
 751   assert(entities == NULL);
 752   entities = eset_create();
 753   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 754     entity * ent = get_irg_ent(get_irp_irg(i));
 755     /* Nur extern sichtbare Methoden können überhaupt mit SymConst
 756      * aufgerufen werden. */
 757     if (get_entity_visibility(ent) != local) {
 758       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 759     }
 760   }
 761   all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
 762   pmap_destroy(ldname_map);
 763 #endif
 764 }