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

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