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