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