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 /** @file cgana.c
  14  *
  15  * Interprocedural analysis to estimate the calling relation.
  16  *
  17  * This analysis computes all entities representing methods that
  18  * can be called at a Call node.  Further it computes a set of
  19  * methods that are 'free', i.e., their adress is handled by
  20  * the program directly, or they are visible external.
  21  */
  22
  23 #ifdef HAVE_CONFIG_H
  24 # include "config.h"
  25 #endif
  26
  27 #ifdef HAVE_STRING_H
  28 # include <string.h>
  29 #endif
  30
  31 #include "cgana.h"
  32 #include "rta.h"
  33
  34 #include "xmalloc.h"
  35 #include "irnode_t.h"
  36 #include "irmode_t.h"
  37 #include "irprog_t.h"
  38 #include "irgwalk.h"
  39 #include "ircons.h"
  40 #include "irgmod.h"
  41 #include "iropt.h"
  42
  43 #include "irflag_t.h"
  44 #include "dbginfo_t.h"
  45 #include "iropt_dbg.h"
  46
  47 #include "eset.h"
  48 #include "pmap.h"
  49 #include "array.h"
  50
  51 #include "irdump.h"
  52
  53 #include "irhooks.h"
  54
  55
  56
  57 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
  58  * Darstellung der unbekannten Methode. */
  59 static void *MARK = &MARK;
  60
  61 static eset *entities = NULL;
  62
  63 /*--------------------------------------------------------------------------*/
  64 /* The analysis                                                             */
  65 /*--------------------------------------------------------------------------*/
  66
  67
  68 /*--------------------------------------------------------------------------*/
  69 /* Initialize datastructures, remove unwanted constructs, optimize          */
  70 /* call target computations.                                                */
  71 /*--------------------------------------------------------------------------*/
  72
  73 /** Returns the entity that contains the implementation of the inherited
  74  *  entity if available, else returns the entity passed. */
  75 static entity *get_inherited_methods_implementation(entity *inh_meth) {
  76   assert(get_atomic_ent_value(inh_meth) && "constant entity without value");
  77   assert((get_irn_op(get_atomic_ent_value(inh_meth)) == op_SymConst) &&
  78          (get_SymConst_kind(get_atomic_ent_value(inh_meth)) == symconst_addr_ent) &&
  79          "Complex constant values not supported -- address of method should be straight constant!");
  80
  81   return get_SymConst_entity(get_atomic_ent_value(inh_meth));
  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  *
  92  * @param method
  93  * @param set      A set of entities.
  94  * @param size     Number of entities in set.
  95  * @param open
  96  */
  97 static void collect_impls(entity *method, eset *set, int *size, bool *open) {
  98   int i;
  99   entity *impl;
 100
 101   /* Only the assertions: */
 102   if (get_entity_peculiarity(method) == peculiarity_existent) {
 103     if ((get_entity_visibility(method) == visibility_external_allocated)
 104          && (NULL == get_entity_irg(method))) {
 105     } else {
 106       assert(get_entity_irg(method) != NULL);
 107     }
 108   }
 109   if (get_entity_peculiarity(method) == peculiarity_inherited) {
 110     entity *impl_ent = get_inherited_methods_implementation(method);
 111     if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
 112       assert(get_entity_irg(impl_ent) == NULL);
 113     } else {
 114       assert(get_entity_irg(impl_ent) != NULL);
 115     }
 116   }
 117
 118   /* Add the implementation to the set if it contains an irg, else
 119      remember that there are more methods called. */
 120   /* @@@ We could also add unknown_entity, or the entities with the
 121      unknown irgs.  The first case would result in the exact same
 122      behavior: all unknown irgs are represented by the one and only
 123      unknown entity. If we add all entities, we known the number of
 124      entities possibly called, and whether there are real unknown
 125      entities, i.e, such not represented in the type description.
 126      This would be better for an analysis: it could rule out more
 127      cases. */
 128   impl = method;
 129   if (get_entity_peculiarity(method) == peculiarity_inherited)
 130     impl = get_inherited_methods_implementation(method);
 131
 132   if (get_entity_peculiarity(method) != peculiarity_description) {
 133     //if (get_entity_irg(impl)) {
 134     eset_insert(set, impl);
 135     ++(*size);
 136       //} else {
 137       /* GL: better: eset_insert(set, unknown_entity); */
 138       //*open = true;
 139       //}
 140   }
 141
 142   /*- recursive descent -*/
 143   for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
 144     collect_impls(get_entity_overwrittenby(method, i), set, size, open);
 145 }
 146
 147 /** Alle Methoden bestimmen, die die übergebene Methode überschreiben
 148  *  (und implementieren). In der zurückgegebenen Reihung kommt jede
 149  *  Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
 150  *  (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
 151  *  wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
 152  *  keine Methoden, die "method" überschreiben, so gibt die Methode
 153  *  "NULL" zurück.
 154  *
 155  *  @param method
 156  */
 157 static entity ** get_impl_methods(entity * method) {
 158   eset * set = eset_create();
 159   int size = 0;
 160   entity ** arr;
 161   bool open = false;
 162
 163   /* Collect all method entities that can be called here */
 164   collect_impls(method, set, &size, &open);
 165
 166   /* Vorgaenger einfuegen. */
 167   if (size == 0 && !open) {
 168     /* keine implementierte überschriebene Methode */
 169     arr = NULL;
 170   } else if (open) {
 171     entity * ent;
 172     arr = NEW_ARR_F(entity *, size + 1);
 173     arr[0] = NULL;  /* Represents open method */
 174     for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
 175       arr[size] = ent;
 176   } else {
 177     entity * ent;
 178     arr = NEW_ARR_F(entity *, size);
 179     for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
 180       arr[size] = ent;
 181   }
 182   eset_destroy(set);
 183   return arr;
 184 }
 185
 186 /** Analyze address computations.
 187  *
 188  *  Compute for all Sel nodes the set of methods that can be selected.
 189  *
 190  *  Further do some optimizations:
 191  *  - Call standard optimizations for Sel nodes: this removes polymorphic
 192  *    calls.
 193  *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
 194  *    For this we precomputed a map name->entity.
 195  *  - If the node is a Sel:
 196  *     If we found only a single method that can be called, replace the Sel
 197  *     by a SymConst.  This is more powerful than the analysis in opt_polymorphy,
 198  *     as here we walk the type graph.  In opt_polymorphy we only apply a local
 199  *     pattern.
 200  *
 201  *  @param node The node to analyze
 202  *  @param env  A map that maps names of entities to the entities.
 203  */
 204 static void sel_methods_walker(ir_node * node, void *env) {
 205   pmap *ldname_map = env;
 206
 207   if (get_irn_op(node) == op_Sel) {
 208     ir_node *new_node = optimize_in_place(node);
 209     if (node != new_node) exchange(node, new_node);
 210   }
 211
 212   /* replace SymConst(name)-operations by SymConst(ent) */
 213   if (get_irn_op(node) == op_SymConst) {
 214     if (get_SymConst_kind(node) == symconst_addr_name) {
 215       pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
 216       if (entry != NULL) { /* Method is declared in the compiled code */
 217         assert(0 && "There should not be a SymConst[addr_name] addressing a method with an implementation"
 218                     "in this compilation unit.  Use a SymConst[addr_ent].");
 219 #if 0
 220         /* the following code would handle that case, but it should not
 221          * happen anymore, so we add the above assertion
 222          */
 223         entity * ent = entry->value;
 224         if (get_opt_normalize() &&
 225             (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
 226           ir_node *new_node;
 227
 228           set_irg_current_block(current_ir_graph, get_nodes_block(node));
 229           new_node = copy_const_value(get_atomic_ent_value(ent));
 230
 231           DBG_OPT_CSTEVAL(node, new_node);
 232
 233           assert(get_entity_irg(ent));
 234           DDMN(new_node);
 235           exchange(node, new_node);
 236         }
 237 #endif
 238       }
 239     }
 240   }
 241   else if (get_irn_op(node) == op_Sel &&
 242            is_Method_type(get_entity_type(get_Sel_entity(node)))) {
 243     entity * ent = get_Sel_entity(node);
 244     assert(get_entity_peculiarity(ent) != peculiarity_inherited);
 245
 246     if (!eset_contains(entities, ent)) {
 247       /* Entity noch nicht behandelt. Alle (intern oder extern)
 248        * implementierten Methoden suchen, die diese Entity
 249        * überschreiben. Die Menge an entity.link speichern. */
 250       set_entity_link(ent, get_impl_methods(ent));
 251       eset_insert(entities, ent);
 252     }
 253
 254     /* -- As an add on we get an optimization that removes polymorphic calls.
 255        This optimization is more powerful than that in transform_node_Sel.  -- */
 256     if (get_entity_link(ent) == NULL) {
 257       /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
 258        * Methode zurückgeben. Damit ist sie insbesondere nicht
 259        * ausführbar und nicht erreichbar. */
 260       /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
 261          fuer die es keine Implementierung gibt. */
 262       if (get_entity_peculiarity(ent) == peculiarity_description) {
 263         /* This is possible:  We call a method in a dead part of the program. */
 264       } else {
 265         DDMN(node);
 266         assert(0);  /* Why should this happen ??? */
 267         //exchange(node, new_Bad());
 268       }
 269     } else {
 270       entity ** arr = get_entity_link(ent);
 271       if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
 272           (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
 273         ir_node *new_node;
 274         /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
 275          * interne Methode zurückgeben. Wir können daher die
 276          * Sel-Operation durch eine Const- bzw. SymConst-Operation
 277          * ersetzen. */
 278         set_irg_current_block(current_ir_graph, get_nodes_block(node));
 279         assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
 280                peculiarity_existent);
 281         new_node = copy_const_value(get_atomic_ent_value(arr[0]));
 282         DBG_OPT_POLY(node, new_node);
 283         exchange (node, new_node);
 284       }
 285     }
 286   }
 287 }
 288
 289 /** Datenstruktur initialisieren. Zusätzlich werden alle
 290  *  SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
 291  *  SymConst(entity)-Operationen ersetzt. */
 292 static void sel_methods_init(void) {
 293   int i;
 294   pmap * ldname_map = pmap_create();   /* Map entity names to entities: to replace
 295                                           SymConst(name) by SymConst(ent). */
 296   assert(entities == NULL);
 297   entities = eset_create();
 298   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 299     entity * ent = get_irg_entity(get_irp_irg(i));
 300     /* Nur extern sichtbare Methoden können überhaupt mit SymConst_ptr_name
 301      * aufgerufen werden. */
 302     if (get_entity_visibility(ent) != visibility_local) {
 303       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 304     }
 305   }
 306   all_irg_walk(sel_methods_walker, NULL, ldname_map);
 307   pmap_destroy(ldname_map);
 308 }
 309
 310 /*--------------------------------------------------------------------------*/
 311 /* Find free methods.
 312  *
 313  * We expect that each entity has an array with all implementations in its
 314  * link field.                                                              */
 315 /*--------------------------------------------------------------------------*/
 316
 317 /**
 318  * Returns an array of all methods that could be called at a Sel node.
 319  * This array contains every entry only once.
 320  */
 321 static entity ** get_Sel_arr(ir_node * sel) {
 322   static entity ** NULL_ARRAY = NULL;
 323   entity * ent;
 324   entity ** arr;
 325
 326   assert(sel && get_irn_op(sel) == op_Sel);
 327   ent = get_Sel_entity(sel);
 328   assert(is_Method_type(get_entity_type(ent))); /* what else? */
 329   arr = get_entity_link(ent);
 330   if (arr) {
 331     return arr;
 332   } else {
 333     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 334      * kann für polymorphe (abstrakte) Methoden passieren. */
 335     if (!NULL_ARRAY) {
 336       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 337     }
 338     return NULL_ARRAY;
 339   }
 340 }
 341
 342 /**
 343  * Returns the number of possible called methods at a Sel node.
 344  */
 345 static int get_Sel_n_methods(ir_node * sel) {
 346   return ARR_LEN(get_Sel_arr(sel));
 347 }
 348
 349 /**
 350  * Returns the ith possible called method entity at a Sel node.
 351  */
 352 static entity * get_Sel_method(ir_node * sel, int pos) {
 353   entity ** arr = get_Sel_arr(sel);
 354   assert(pos >= 0 && pos < ARR_LEN(arr));
 355   return arr[pos];
 356 }
 357
 358 static void free_mark(ir_node * node, eset * set);
 359
 360 static void free_mark_proj(ir_node * node, long n, eset * set) {
 361   assert(get_irn_mode(node) == mode_T);
 362   if (get_irn_link(node) == MARK) {
 363     /* already visited */
 364     return;
 365   }
 366   set_irn_link(node, MARK);
 367   switch (get_irn_opcode(node)) {
 368   case iro_Proj: {
 369     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 370      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 371      * wird. */
 372     ir_node * pred = get_Proj_pred(node);
 373     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 374       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 375     } else {
 376       /* nothing: da in "free_ana_walker" behandelt. */
 377     }
 378     break;
 379   }
 380
 381   case iro_Tuple:
 382     free_mark(get_Tuple_pred(node, n), set);
 383     break;
 384
 385   case iro_Id:
 386     free_mark_proj(get_Id_pred(node), n, set);
 387     break;
 388
 389   case iro_Start:
 390   case iro_Alloc:
 391   case iro_Load:
 392     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 393      * behandelt. */
 394     break;
 395
 396   default:
 397     assert(0 && "unexpected opcode or opcode not implemented");
 398     break;
 399   }
 400   set_irn_link(node, NULL);
 401 }
 402
 403
 404 static void free_mark(ir_node * node, eset * set) {
 405   int i;
 406
 407   if (get_irn_link(node) == MARK) {
 408     return; /* already visited */
 409   }
 410   set_irn_link(node, MARK);
 411   switch (get_irn_opcode(node)) {
 412   case iro_Sel: {
 413     entity * ent = get_Sel_entity(node);
 414     if (is_Method_type(get_entity_type(ent))) {
 415       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 416         eset_insert(set, get_Sel_method(node, i));
 417       }
 418     }
 419     break;
 420   }
 421   case iro_SymConst:
 422     if (get_SymConst_kind(node) == symconst_addr_ent) {
 423       entity * ent = get_SymConst_entity(node);
 424       if (is_Method_type(get_entity_type(ent))) {
 425         eset_insert(set, ent);
 426       }
 427     } else {
 428       assert(get_SymConst_kind(node) == symconst_addr_name);
 429       /* nothing: SymConst points to extern method */
 430     }
 431     break;
 432
 433   case iro_Phi:
 434     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 435       free_mark(get_Phi_pred(node, i), set);
 436     }
 437     break;
 438   case iro_Id:
 439     free_mark(get_Id_pred(node), set);
 440     break;
 441   case iro_Proj:
 442     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 443     break;
 444   default:
 445     /* nothing: Wird unten behandelt! */
 446     break;
 447   }
 448   set_irn_link(node, NULL);
 449 }
 450
 451
 452 static void free_ana_walker(ir_node * node, eset * set) {
 453   int i;
 454   if (get_irn_link(node) == MARK) {
 455     /* bereits in einem Zyklus besucht. */
 456     return;
 457   }
 458   switch (get_irn_opcode(node)) {
 459   /* special nodes */
 460   case iro_Sel:
 461   case iro_SymConst:
 462   case iro_Const:
 463   case iro_Phi:
 464   case iro_Id:
 465   case iro_Proj:
 466   case iro_Tuple:
 467     /* nothing */
 468     break;
 469   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 470    * Verräter ist. */
 471   case iro_Call:
 472     set_irn_link(node, MARK);
 473     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 474       ir_node * pred = get_Call_param(node, i);
 475       if (mode_is_reference(get_irn_mode(pred))) {
 476         free_mark(pred, set);
 477       }
 478     }
 479     break;
 480   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 481    * jemand das Gegenteil implementiert. */
 482   default:
 483     set_irn_link(node, MARK);
 484     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 485       ir_node * pred = get_irn_n(node, i);
 486       if (mode_is_reference(get_irn_mode(pred))) {
 487         free_mark(pred, set);
 488       }
 489     }
 490     break;
 491   }
 492   set_irn_link(node, NULL);
 493 }
 494
 495 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 496  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 497  * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
 498  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 499  * auf eine echt externe Methode. */
 500 static entity ** get_free_methods(void)
 501 {
 502   eset * set = eset_create();
 503   int i;
 504   entity ** arr = NEW_ARR_F(entity *, 0);
 505   entity * ent;
 506
 507   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 508     ir_graph * irg = get_irp_irg(i);
 509     entity * ent = get_irg_entity(irg);
 510     /* insert "external visible" methods. */
 511     if (get_entity_visibility(ent) != visibility_local) {
 512       eset_insert(set, ent);
 513     }
 514     /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
 515        z.B. da die Adresse einer Methode abgespeichert wird. */
 516     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 517   }
 518
 519   /* insert sticky methods, too */
 520   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 521     entity * ent = get_irg_entity(get_irp_irg(i));
 522     /* insert "external visible" methods. */
 523     if (get_entity_stickyness (ent) == stickyness_sticky) {
 524       eset_insert(set, ent);
 525     }
 526   }
 527
 528   /* Hauptprogramm ist auch dann frei, wenn es nicht "external
 529    * visible" ist. */
 530   if (get_irp_main_irg()) {
 531     eset_insert(set, get_irg_entity(get_irp_main_irg()));
 532   }
 533   /* Wandle Menge in Feld um.  Effizienter. */
 534   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 535     ARR_APP1(entity *, arr, ent);
 536   }
 537   eset_destroy(set);
 538
 539   return arr;
 540 }
 541
 542 /*--------------------------------------------------------------------------*/
 543 /* Callee analysis.                                                         */
 544 /*--------------------------------------------------------------------------*/
 545
 546 static void callee_ana_node(ir_node * node, eset * methods);
 547
 548 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 549   assert(get_irn_mode(node) == mode_T);
 550   if (get_irn_link(node) == MARK) {
 551     /* already visited */
 552     return;
 553   }
 554   set_irn_link(node, MARK);
 555
 556   switch (get_irn_opcode(node)) {
 557   case iro_Proj: {
 558     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 559      * op_Tuple oder ein Knoten, der eine "freie Methode"
 560      * zurückgibt. */
 561     ir_node * pred = get_Proj_pred(node);
 562     if (get_irn_link(pred) != MARK) {
 563       if (get_irn_op(pred) == op_Tuple) {
 564         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 565       } else {
 566         eset_insert(methods, MARK); /* free method -> unknown */
 567       }
 568     }
 569     break;
 570   }
 571
 572   case iro_Tuple:
 573     callee_ana_node(get_Tuple_pred(node, n), methods);
 574     break;
 575
 576   case iro_Id:
 577     callee_ana_proj(get_Id_pred(node), n, methods);
 578     break;
 579
 580   default:
 581     eset_insert(methods, MARK); /* free method -> unknown */
 582     break;
 583   }
 584
 585   set_irn_link(node, NULL);
 586 }
 587
 588
 589 static void callee_ana_node(ir_node * node, eset * methods) {
 590   int i;
 591
 592   assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
 593   /* rekursion verhindern */
 594   if (get_irn_link(node) == MARK) {
 595     /* already visited */
 596     return;
 597   }
 598   set_irn_link(node, MARK);
 599
 600   switch (get_irn_opcode(node)) {
 601   case iro_SymConst:
 602     if (get_SymConst_kind(node) == symconst_addr_ent) {
 603       entity * ent = get_SymConst_entity(node);
 604       assert(ent && is_Method_type(get_entity_type(ent)));
 605       eset_insert(methods, ent);
 606     } else {
 607       assert(get_SymConst_kind(node) == symconst_addr_name);
 608       /* externe Methode (wegen fix_symconst!) */
 609       eset_insert(methods, MARK); /* free method -> unknown */
 610     }
 611     break;
 612   case iro_Sel:
 613     /* polymorphe Methode */
 614     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 615       entity * ent = get_Sel_method(node, i);
 616       if (ent) {
 617         eset_insert(methods, ent);
 618       } else {
 619         eset_insert(methods, MARK);
 620       }
 621     }
 622     break;
 623
 624   case iro_Bad:
 625     /* nothing */
 626     break;
 627
 628   case iro_Phi: /* Vereinigung */
 629     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 630       callee_ana_node(get_Phi_pred(node, i), methods);
 631     }
 632     break;
 633
 634   case iro_Mux:
 635     callee_ana_node(get_Mux_false(node), methods);
 636     callee_ana_node(get_Mux_true(node), methods);
 637     break;
 638
 639   case iro_Id:
 640     callee_ana_node(get_Id_pred(node), methods);
 641     break;
 642
 643   case iro_Proj:
 644     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 645     break;
 646
 647   case iro_Add:
 648   case iro_Sub:
 649   case iro_Conv:
 650     /* extern */
 651     eset_insert(methods, MARK); /* free method -> unknown */
 652     break;
 653
 654   default:
 655     assert(0 && "invalid opcode or opcode not implemented");
 656     break;
 657   }
 658
 659   set_irn_link(node, NULL);
 660 }
 661
 662
 663 static void callee_walker(ir_node * call, void * env) {
 664   if (get_irn_op(call) == op_Call) {
 665     eset * methods = eset_create();
 666     entity * ent;
 667     entity ** arr = NEW_ARR_F(entity *, 0);
 668     assert(get_irn_op(get_Call_ptr(call)) != op_Id);
 669     callee_ana_node(get_Call_ptr(call), methods);
 670     if (eset_contains(methods, MARK)) { /* unknown method */
 671       ARR_APP1(entity *, arr, unknown_entity);
 672     }
 673     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 674       if (ent != MARK) {
 675         ARR_APP1(entity *, arr, ent);
 676       }
 677     }
 678 #if 0  /* This generates Bad nodes when we don't want it.
 679           Call it with a check for valid cgana information in local_optimize. */
 680     if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
 681       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 682        * Sel-Operation war, die keine Methoden zurückgeben
 683        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 684        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 685        * werden! */
 686       ir_node *mem = get_Call_mem(call);
 687       turn_into_tuple (call, 5 /* pn_Call_max */);
 688       set_Tuple_pred(call, pn_Call_M_regular       , mem);
 689       set_Tuple_pred(call, pn_Call_T_result        , new_Bad());
 690       set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
 691       set_Tuple_pred(call, pn_Call_X_except        , new_Bad());  /* new_Jmp() ?? new_Raise() ?? */
 692       set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
 693
 694     } else
 695 #endif
 696     {
 697       /* remove, what we repaired. */
 698       int i;
 699       for (i = 0; i < ARR_LEN(arr); ++i) {
 700         assert(arr[i]);
 701       }
 702
 703       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 704     }
 705     DEL_ARR_F(arr);
 706     eset_destroy(methods);
 707   }
 708 }
 709
 710
 711 static void remove_Tuples(ir_node * proj, void * env) {
 712   ir_node *new;
 713   if (get_irn_opcode(proj) != iro_Proj) return;
 714
 715   new = skip_Tuple(proj);
 716   if (new != proj) exchange(proj, new);
 717 }
 718
 719
 720 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 721  * und speichert das Ergebnis in der Call-Operation. (siehe
 722  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 723  * muss bereits aufgebaut sein. */
 724 static void callee_ana(void) {
 725   int i;
 726   /* Alle Graphen analysieren. */
 727   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 728     irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
 729     set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
 730   }
 731   set_irp_callee_info_state(irg_callee_info_consistent);
 732 }
 733
 734 /*--------------------------------------------------------------------------*/
 735 /* Cleanup after analyses.                                                  */
 736 /*--------------------------------------------------------------------------*/
 737
 738 /** Frees intermediate data structures. */
 739 static void sel_methods_dispose(void) {
 740   entity * ent;
 741   assert(entities);
 742   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 743     entity ** arr = get_entity_link(ent);
 744     if (arr) {
 745       DEL_ARR_F(arr);
 746     }
 747     set_entity_link(ent, NULL);
 748   }
 749   eset_destroy(entities);
 750   entities = NULL;
 751 }
 752
 753 /*--------------------------------------------------------------------------*/
 754 /* Freeing the callee arrays.                                               */
 755 /*--------------------------------------------------------------------------*/
 756
 757 static void destruct_walker(ir_node * node, void * env) {
 758   if (get_irn_op(node) == op_Call) {
 759     remove_Call_callee_arr(node);
 760   }
 761 }
 762
 763 /*--------------------------------------------------------------------------*/
 764 /* Main drivers.                                                            */
 765 /*--------------------------------------------------------------------------*/
 766
 767 void cgana(int *length, entity ***free_methods) {
 768   entity ** free_meths, **p;
 769
 770   sel_methods_init();
 771   free_meths = get_free_methods();
 772   callee_ana();
 773   sel_methods_dispose();
 774
 775   /* Convert the flexible array to an array that can be handled
 776      by standard C. */
 777   p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
 778   memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));
 779
 780   *length       = ARR_LEN(free_meths);
 781   *free_methods = p;
 782
 783   DEL_ARR_F(free_meths);
 784 }
 785
 786 void free_callee_info(ir_graph *irg) {
 787   irg_walk_graph(irg, destruct_walker, NULL, NULL);
 788   set_irg_callee_info_state(irg, irg_callee_info_none);
 789 }
 790
 791 /* Optimize the address expressions passed to call nodes.
 792  *
 793  * This optimization performs the following transformations for
 794  * all ir graphs:
 795  * - All SymConst operations that refer to intern methods are replaced
 796  *   by Const operations refering to the corresponding entity.
 797  * - Sel nodes, that select entities that are not overwritten are
 798  *   replaced by Const nodes refering to the selected entity.
 799  * - Sel nodes, for which no method exists at all are replaced by Bad
 800  *   nodes.
 801  * - Sel nodes with a pointer input that is an Alloc node are replaced
 802  *   by Const nodes refering to the entity that implements the method in
 803  *   the type given by the Alloc node.
 804  */
 805 void opt_call_addrs(void) {
 806   sel_methods_init();
 807   sel_methods_dispose();
 808 }