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