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 in method %s which has "
 250                   "no implementation!\n", get_entity_name(ent),
 251                   get_entity_name(get_irg_ent(current_ir_graph)));
 252         } else {
 253           exchange(node, new_Bad());
 254         }
 255       } else {
 256         entity ** arr = get_entity_link(ent);
 257
 258 #if 0
 259         int i;
 260         printf("\nCall site "); DDMN(node);
 261         printf("  in "); DDME(get_irg_ent(current_ir_graph));
 262         printf("  can call:\n");
 263         for (i = 0; i < ARR_LEN(arr); i++) {
 264           printf("   - "); DDME(arr[i]);
 265           printf("     with owner "); DDMT(get_entity_owner(arr[i]));
 266         }
 267         printf("\n");
 268 #endif
 269
 270         if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
 271             (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
 272           ir_node *new_node;
 273           /* Die Sel-Operation kann immer nur einen Wert auf eine
 274            * interne Methode zurückgeben. Wir können daher die
 275            * Sel-Operation durch eine Const- bzw. SymConst-Operation
 276            * ersetzen. */
 277           set_irg_current_block(current_ir_graph, get_nodes_Block(node));
 278           new_node = copy_const_value(get_atomic_ent_value(arr[0]));         DBG_OPT_POLY;
 279           exchange (node, new_node);
 280         }
 281       }
 282     }
 283   }
 284 }
 285
 286
 287 /* Datenstruktur initialisieren. Zusätzlich werden alle
 288  * SymConst-Operationen, die auf interne Methoden verweisen, durch
 289  * Const-Operationen ersetzt. */
 290 static void sel_methods_init(void) {
 291   int i;
 292   pmap * ldname_map = pmap_create();
 293   assert(entities == NULL);
 294   entities = eset_create();
 295   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 296     entity * ent = get_irg_ent(get_irp_irg(i));
 297     /* Nur extern sichtbare Methode können überhaupt mit SymConst
 298      * aufgerufen werden. */
 299     if (get_entity_visibility(ent) != visibility_local) {
 300       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 301     }
 302   }
 303   all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
 304   pmap_destroy(ldname_map);
 305 }
 306
 307 /*****************************************************************************/
 308
 309 /* Datenstruktur freigeben. */
 310 static void sel_methods_dispose(void) {
 311   entity * ent;
 312   assert(entities);
 313   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 314     entity ** arr = get_entity_link(ent);
 315     if (arr) {
 316       DEL_ARR_F(arr);
 317     }
 318     set_entity_link(ent, NULL);
 319   }
 320   eset_destroy(entities);
 321   entities = NULL;
 322 }
 323
 324
 325 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
 326  * zurückgegeben werden können. Die Liste enthält keine doppelten
 327  * Einträge. */
 328 static entity ** get_Sel_arr(ir_node * sel) {
 329   static entity ** NULL_ARRAY = NULL;
 330   entity * ent;
 331   entity ** arr;
 332   assert(sel && intern_get_irn_op(sel) == op_Sel);
 333   ent = get_Sel_entity(sel);
 334   assert(is_method_type(get_entity_type(ent))); /* what else? */
 335   arr = get_entity_link(ent);
 336   if (arr) {
 337     return arr;
 338   } else {
 339     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 340      * kann für polymorphe (abstrakte) Methoden passieren. */
 341     if (!NULL_ARRAY) {
 342       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 343     }
 344     return NULL_ARRAY;
 345   }
 346 }
 347
 348
 349 static int get_Sel_n_methods(ir_node * sel) {
 350   return ARR_LEN(get_Sel_arr(sel));
 351 }
 352
 353
 354 static entity * get_Sel_method(ir_node * sel, int pos) {
 355   entity ** arr = get_Sel_arr(sel);
 356   assert(pos >= 0 && pos < ARR_LEN(arr));
 357   return arr[pos];
 358 }
 359
 360
 361
 362 /* --- callee analysis ------------------------------------------------------ */
 363
 364
 365 static void callee_ana_node(ir_node * node, eset * methods);
 366
 367
 368 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 369   assert(get_irn_mode(node) == mode_T);
 370   if (get_irn_link(node) == MARK) {
 371     /* already visited */
 372     return;
 373   }
 374   set_irn_link(node, MARK);
 375
 376   switch (intern_get_irn_opcode(node)) {
 377   case iro_Proj: {
 378     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 379      * op_Tuple oder ein Knoten, der eine "freie Methode"
 380      * zurückgibt. */
 381     ir_node * pred = get_Proj_pred(node);
 382     if (get_irn_link(pred) != MARK) {
 383       if (intern_get_irn_op(pred) == op_Tuple) {
 384         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 385       } else {
 386         eset_insert(methods, MARK); /* free method -> unknown */
 387       }
 388     }
 389     break;
 390   }
 391
 392   case iro_Tuple:
 393     callee_ana_node(get_Tuple_pred(node, n), methods);
 394     break;
 395
 396   case iro_Id:
 397     callee_ana_proj(get_Id_pred(node), n, methods);
 398     break;
 399
 400   default:
 401     eset_insert(methods, MARK); /* free method -> unknown */
 402     break;
 403   }
 404
 405   set_irn_link(node, NULL);
 406 }
 407
 408
 409 static void callee_ana_node(ir_node * node, eset * methods) {
 410   int i;
 411
 412   assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
 413   /* rekursion verhindern */
 414   if (get_irn_link(node) == MARK) {
 415     /* already visited */
 416     return;
 417   }
 418   set_irn_link(node, MARK);
 419
 420   switch (intern_get_irn_opcode(node)) {
 421   case iro_SymConst:
 422     /* externe Methode (wegen fix_symconst!) */
 423     eset_insert(methods, MARK); /* free method -> unknown */
 424     break;
 425
 426   case iro_Const: {
 427     /* interne Methode */
 428     entity * ent = tarval_to_entity(get_Const_tarval(node));
 429     assert(ent && is_method_type(get_entity_type(ent)));
 430     if (get_entity_visibility(ent) != visibility_external_allocated) {
 431       assert(get_entity_irg(ent));
 432       eset_insert(methods, ent);
 433     } else {
 434       eset_insert(methods, MARK); /* free method -> unknown */
 435     }
 436     break;
 437   }
 438
 439   case iro_Sel:
 440     /* polymorphe Methode */
 441     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 442       entity * ent = get_Sel_method(node, i);
 443       if (ent) {
 444         eset_insert(methods, ent);
 445       } else {
 446         eset_insert(methods, MARK);
 447       }
 448     }
 449     break;
 450
 451   case iro_Bad:
 452     /* nothing */
 453     break;
 454
 455   case iro_Phi: /* Vereinigung */
 456     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 457       callee_ana_node(get_Phi_pred(node, i), methods);
 458     }
 459     break;
 460
 461   case iro_Id:
 462     callee_ana_node(get_Id_pred(node), methods);
 463     break;
 464
 465   case iro_Proj:
 466     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 467     break;
 468
 469   case iro_Add:
 470   case iro_Sub:
 471   case iro_Conv:
 472     /* extern */
 473     eset_insert(methods, MARK); /* free method -> unknown */
 474     break;
 475
 476   default:
 477     assert(0 && "invalid opcode or opcode not implemented");
 478     break;
 479   }
 480
 481   set_irn_link(node, NULL);
 482 }
 483
 484
 485 static void callee_walker(ir_node * call, void * env) {
 486   if (intern_get_irn_op(call) == op_Call) {
 487     eset * methods = eset_create();
 488     entity * ent;
 489     entity ** arr = NEW_ARR_F(entity *, 0);
 490     callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
 491     if (eset_contains(methods, MARK)) { /* unknown method */
 492       ARR_APP1(entity *, arr, NULL);
 493     }
 494     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 495       if (ent != MARK) {
 496         ARR_APP1(entity *, arr, ent);
 497       }
 498     }
 499     if (ARR_LEN(arr) == 0) {
 500       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 501        * Sel-Operation war, die keine Methoden zurückgeben
 502        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 503        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 504        * werden! */
 505       exchange(call, new_Bad());
 506     } else {
 507       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 508     }
 509     DEL_ARR_F(arr);
 510     eset_destroy(methods);
 511   }
 512 }
 513
 514
 515 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 516  * und speichert das Ergebnis in der Call-Operation. (siehe
 517  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 518  * muss bereits aufgebaut sein. */
 519 static void callee_ana(void) {
 520   int i;
 521   /* Alle Graphen analysieren. */
 522   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 523     irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
 524     set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
 525   }
 526 }
 527
 528
 529
 530 /* --- free method analysis ------------------------------------------------- */
 531
 532
 533 static void free_mark(ir_node * node, eset * set);
 534
 535 static void free_mark_proj(ir_node * node, long n, eset * set) {
 536   assert(get_irn_mode(node) == mode_T);
 537   if (get_irn_link(node) == MARK) {
 538     /* already visited */
 539     return;
 540   }
 541   set_irn_link(node, MARK);
 542   switch (intern_get_irn_opcode(node)) {
 543   case iro_Proj: {
 544     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 545      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 546      * wird. */
 547     ir_node * pred = get_Proj_pred(node);
 548     if (get_irn_link(pred) != MARK && intern_get_irn_op(pred) == op_Tuple) {
 549       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 550     } else {
 551       /* nothing: da in "free_ana_walker" behandelt. */
 552     }
 553     break;
 554   }
 555
 556   case iro_Tuple:
 557     free_mark(get_Tuple_pred(node, n), set);
 558     break;
 559
 560   case iro_Id:
 561     free_mark_proj(get_Id_pred(node), n, set);
 562     break;
 563
 564   case iro_Start:
 565   case iro_Alloc:
 566   case iro_Load:
 567     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 568      * behandelt. */
 569     break;
 570
 571   default:
 572     assert(0 && "unexpected opcode or opcode not implemented");
 573     break;
 574   }
 575   set_irn_link(node, NULL);
 576 }
 577
 578
 579 static void free_mark(ir_node * node, eset * set) {
 580   int i;
 581   assert(mode_is_reference(get_irn_mode(node)));
 582   if (get_irn_link(node) == MARK) {
 583     return; /* already visited */
 584   }
 585   set_irn_link(node, MARK);
 586   switch (intern_get_irn_opcode(node)) {
 587   case iro_Sel: {
 588     entity * ent = get_Sel_entity(node);
 589     if (is_method_type(get_entity_type(ent))) {
 590       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 591         eset_insert(set, get_Sel_method(node, i));
 592       }
 593     }
 594     break;
 595   }
 596   case iro_SymConst:
 597     /* nothing: SymConst points to extern method */
 598     break;
 599   case iro_Const: {
 600     tarval * val = get_Const_tarval(node);
 601     if (tarval_is_entity(val)) { /* filter null pointer */
 602       entity * ent = tarval_to_entity(val);
 603       if (is_method_type(get_entity_type(ent))) {
 604         eset_insert(set, ent);
 605       }
 606     }
 607     break;
 608   }
 609   case iro_Phi:
 610     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 611       free_mark(get_Phi_pred(node, i), set);
 612     }
 613     break;
 614   case iro_Id:
 615     free_mark(get_Id_pred(node), set);
 616     break;
 617   case iro_Proj:
 618     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 619     break;
 620   default:
 621     /* nothing: Wird unten behandelt! */
 622     break;
 623   }
 624   set_irn_link(node, NULL);
 625 }
 626
 627
 628 static void free_ana_walker(ir_node * node, eset * set) {
 629   int i;
 630   if (get_irn_link(node) == MARK) {
 631     /* bereits in einem Zyklus besucht. */
 632     return;
 633   }
 634   switch (intern_get_irn_opcode(node)) {
 635   /* special nodes */
 636   case iro_Sel:
 637   case iro_SymConst:
 638   case iro_Const:
 639   case iro_Phi:
 640   case iro_Id:
 641   case iro_Proj:
 642   case iro_Tuple:
 643     /* nothing */
 644     break;
 645   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 646    * Verräter ist. */
 647   case iro_Call:
 648     set_irn_link(node, MARK);
 649     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 650       ir_node * pred = get_Call_param(node, i);
 651       if (mode_is_reference(intern_get_irn_mode(pred))) {
 652         free_mark(pred, set);
 653       }
 654     }
 655     break;
 656   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 657    * jemand das Gegenteil implementiert. */
 658   default:
 659     set_irn_link(node, MARK);
 660     for (i = intern_get_irn_arity(node) - 1; i >= 0; --i) {
 661       ir_node * pred = get_irn_n(node, i);
 662       if (mode_is_reference(intern_get_irn_mode(pred))) {
 663         free_mark(pred, set);
 664       }
 665     }
 666     break;
 667   }
 668   set_irn_link(node, NULL);
 669 }
 670
 671
 672 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 673  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 674  * SymConst-Operationen müssen in passende Const-Operationen
 675  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 676  * auf eine echt externe Methode.  */
 677 static entity ** get_free_methods(void) {
 678   eset * set = eset_create();
 679   int i;
 680   entity ** arr = NEW_ARR_F(entity *, 0);
 681   entity * ent;
 682   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 683     ir_graph * irg = get_irp_irg(i);
 684     entity * ent = get_irg_ent(irg);
 685     /* insert "external visible" methods. */
 686     if (get_entity_visibility(ent) != visibility_local) {
 687       eset_insert(set, ent);
 688     }
 689     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 690   }
 691   /* Hauptprogramm ist auch frei, auch wenn es nicht "external
 692    * visible" ist. */
 693   if(get_irp_main_irg()) {
 694     eset_insert(set, get_irg_ent(get_irp_main_irg()));
 695   }
 696   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 697     ARR_APP1(entity *, arr, ent);
 698   }
 699   eset_destroy(set);
 700
 701   return arr;
 702 }
 703
 704 void cgana(int *length, entity ***free_methods) {
 705   entity ** free_meths;
 706   int i;
 707
 708   sel_methods_init();
 709   free_meths = get_free_methods();
 710   callee_ana();
 711   sel_methods_dispose();
 712
 713   /* Convert the flexible array to an array that can be handled
 714      by standard C. */
 715   *length = ARR_LEN(free_meths);
 716   *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
 717   for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
 718   DEL_ARR_F(free_meths);
 719 }
 720
 721 /* Optimize the address expressions passed to call nodes.
 722  * Alle SymConst-Operationen, die auf interne Methoden verweisen,
 723  * werden durch Const-Operationen ersetzt.
 724  * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
 725  * durch Const ersetzt.
 726  * Sel Knoten, fuer die keine Implementierung existiert, werden
 727  * durch Bad ersetzt. */
 728 void opt_call_addrs(void) {
 729   sel_methods_init();
 730   sel_methods_dispose();
 731 #if 0
 732   int i;
 733   pmap * ldname_map = pmap_create();
 734   assert(entities == NULL);
 735   entities = eset_create();
 736   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 737     entity * ent = get_irg_ent(get_irp_irg(i));
 738     /* Nur extern sichtbare Methoden können überhaupt mit SymConst
 739      * aufgerufen werden. */
 740     if (get_entity_visibility(ent) != local) {
 741       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 742     }
 743   }
 744   all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
 745   pmap_destroy(ldname_map);
 746 #endif
 747 }