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 typegraph.  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         entity * ent = entry->value;
 221         if (get_opt_normalize() &&
 222             (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
 223           ir_node *new_node;
 224
 225           set_irg_current_block(current_ir_graph, get_nodes_block(node));
 226           new_node = copy_const_value(get_atomic_ent_value(ent));
 227
 228           DBG_OPT_CSTEVAL(node, new_node);
 229
 230           assert(get_entity_irg(ent));
 231           DDMN(new_node);
 232           exchange(node, new_node);
 233         }
 234 #endif
 235       }
 236     }
 237   }
 238   else if (get_irn_op(node) == op_Sel &&
 239            is_Method_type(get_entity_type(get_Sel_entity(node)))) {
 240     entity * ent = get_Sel_entity(node);
 241     assert(get_entity_peculiarity(ent) != peculiarity_inherited);
 242
 243     if (!eset_contains(entities, ent)) {
 244       /* Entity noch nicht behandelt. Alle (intern oder extern)
 245        * implementierten Methoden suchen, die diese Entity
 246        * überschreiben. Die Menge an entity.link speichern. */
 247       set_entity_link(ent, get_impl_methods(ent));
 248       eset_insert(entities, ent);
 249     }
 250
 251     /* -- As an add on we get an optimization that removes polymorphic calls.
 252        This optimization is more powerful than that in transform_node_Sel.  -- */
 253     if (get_entity_link(ent) == NULL) {
 254       /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
 255        * Methode zurückgeben. Damit ist sie insbesondere nicht
 256        * ausführbar und nicht erreichbar. */
 257       /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
 258          fuer die es keine Implementierung gibt. */
 259       if (get_entity_peculiarity(ent) == peculiarity_description) {
 260         /* This is possible:  We call a method in a dead part of the program. */
 261       } else {
 262         DDMN(node);
 263         assert(0);  /* Why should this happen ??? */
 264         //exchange(node, new_Bad());
 265       }
 266     } else {
 267       entity ** arr = get_entity_link(ent);
 268       if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
 269           (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
 270         ir_node *new_node;
 271         /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
 272          * interne Methode zurückgeben. Wir können daher die
 273          * Sel-Operation durch eine Const- bzw. SymConst-Operation
 274          * ersetzen. */
 275         set_irg_current_block(current_ir_graph, get_nodes_block(node));
 276         assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
 277                peculiarity_existent);
 278         new_node = copy_const_value(get_atomic_ent_value(arr[0]));
 279         DBG_OPT_POLY(node, new_node);
 280         exchange (node, new_node);
 281       }
 282     }
 283   }
 284 }
 285
 286 /** Datenstruktur initialisieren. Zusätzlich werden alle
 287  *  SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
 288  *  SymConst(entity)-Operationen ersetzt. */
 289 static void sel_methods_init(void) {
 290   int i;
 291   pmap * ldname_map = pmap_create();   /* Map entity names to entities: to replace
 292                                           SymConst(name) by SymConst(ent). */
 293   assert(entities == NULL);
 294   entities = eset_create();
 295   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 296     entity * ent = get_irg_entity(get_irp_irg(i));
 297     /* Nur extern sichtbare Methoden können überhaupt mit SymConst_ptr_name
 298      * aufgerufen werden. */
 299     if (get_entity_visibility(ent) != visibility_local) {
 300       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 301     }
 302   }
 303   all_irg_walk(sel_methods_walker, NULL, ldname_map);
 304   pmap_destroy(ldname_map);
 305 }
 306
 307 /*--------------------------------------------------------------------------*/
 308 /* Find free methods.
 309  *
 310  * We expect that each entity has an array with all implementations in its
 311  * link field.                                                              */
 312 /*--------------------------------------------------------------------------*/
 313
 314 /**
 315  * Returns an array of all methods that could be called at a Sel node.
 316  * This array contains every entry only once.
 317  */
 318 static entity ** get_Sel_arr(ir_node * sel) {
 319   static entity ** NULL_ARRAY = NULL;
 320   entity * ent;
 321   entity ** arr;
 322
 323   assert(sel && get_irn_op(sel) == op_Sel);
 324   ent = get_Sel_entity(sel);
 325   assert(is_Method_type(get_entity_type(ent))); /* what else? */
 326   arr = get_entity_link(ent);
 327   if (arr) {
 328     return arr;
 329   } else {
 330     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 331      * kann für polymorphe (abstrakte) Methoden passieren. */
 332     if (!NULL_ARRAY) {
 333       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 334     }
 335     return NULL_ARRAY;
 336   }
 337 }
 338
 339 /**
 340  * Returns the number of possible called methods at a Sel node.
 341  */
 342 static int get_Sel_n_methods(ir_node * sel) {
 343   return ARR_LEN(get_Sel_arr(sel));
 344 }
 345
 346 /**
 347  * Returns the ith possible called method entity at a Sel node.
 348  */
 349 static entity * get_Sel_method(ir_node * sel, int pos) {
 350   entity ** arr = get_Sel_arr(sel);
 351   assert(pos >= 0 && pos < ARR_LEN(arr));
 352   return arr[pos];
 353 }
 354
 355 static void free_mark(ir_node * node, eset * set);
 356
 357 static void free_mark_proj(ir_node * node, long n, eset * set) {
 358   assert(get_irn_mode(node) == mode_T);
 359   if (get_irn_link(node) == MARK) {
 360     /* already visited */
 361     return;
 362   }
 363   set_irn_link(node, MARK);
 364   switch (get_irn_opcode(node)) {
 365   case iro_Proj: {
 366     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 367      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 368      * wird. */
 369     ir_node * pred = get_Proj_pred(node);
 370     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 371       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 372     } else {
 373       /* nothing: da in "free_ana_walker" behandelt. */
 374     }
 375     break;
 376   }
 377
 378   case iro_Tuple:
 379     free_mark(get_Tuple_pred(node, n), set);
 380     break;
 381
 382   case iro_Id:
 383     free_mark_proj(get_Id_pred(node), n, set);
 384     break;
 385
 386   case iro_Start:
 387   case iro_Alloc:
 388   case iro_Load:
 389     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 390      * behandelt. */
 391     break;
 392
 393   default:
 394     assert(0 && "unexpected opcode or opcode not implemented");
 395     break;
 396   }
 397   set_irn_link(node, NULL);
 398 }
 399
 400
 401 static void free_mark(ir_node * node, eset * set) {
 402   int i;
 403
 404   if (get_irn_link(node) == MARK) {
 405     return; /* already visited */
 406   }
 407   set_irn_link(node, MARK);
 408   switch (get_irn_opcode(node)) {
 409   case iro_Sel: {
 410     entity * ent = get_Sel_entity(node);
 411     if (is_Method_type(get_entity_type(ent))) {
 412       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 413         eset_insert(set, get_Sel_method(node, i));
 414       }
 415     }
 416     break;
 417   }
 418   case iro_SymConst:
 419     if (get_SymConst_kind(node) == symconst_addr_ent) {
 420       entity * ent = get_SymConst_entity(node);
 421       if (is_Method_type(get_entity_type(ent))) {
 422         eset_insert(set, ent);
 423       }
 424     } else {
 425       assert(get_SymConst_kind(node) == symconst_addr_name);
 426       /* nothing: SymConst points to extern method */
 427     }
 428     break;
 429
 430   case iro_Phi:
 431     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 432       free_mark(get_Phi_pred(node, i), set);
 433     }
 434     break;
 435   case iro_Id:
 436     free_mark(get_Id_pred(node), set);
 437     break;
 438   case iro_Proj:
 439     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 440     break;
 441   default:
 442     /* nothing: Wird unten behandelt! */
 443     break;
 444   }
 445   set_irn_link(node, NULL);
 446 }
 447
 448
 449 static void free_ana_walker(ir_node * node, eset * set) {
 450   int i;
 451   if (get_irn_link(node) == MARK) {
 452     /* bereits in einem Zyklus besucht. */
 453     return;
 454   }
 455   switch (get_irn_opcode(node)) {
 456   /* special nodes */
 457   case iro_Sel:
 458   case iro_SymConst:
 459   case iro_Const:
 460   case iro_Phi:
 461   case iro_Id:
 462   case iro_Proj:
 463   case iro_Tuple:
 464     /* nothing */
 465     break;
 466   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 467    * Verräter ist. */
 468   case iro_Call:
 469     set_irn_link(node, MARK);
 470     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 471       ir_node * pred = get_Call_param(node, i);
 472       if (mode_is_reference(get_irn_mode(pred))) {
 473         free_mark(pred, set);
 474       }
 475     }
 476     break;
 477   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 478    * jemand das Gegenteil implementiert. */
 479   default:
 480     set_irn_link(node, MARK);
 481     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 482       ir_node * pred = get_irn_n(node, i);
 483       if (mode_is_reference(get_irn_mode(pred))) {
 484         free_mark(pred, set);
 485       }
 486     }
 487     break;
 488   }
 489   set_irn_link(node, NULL);
 490 }
 491
 492 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 493  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 494  * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
 495  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 496  * auf eine echt externe Methode. */
 497 static entity ** get_free_methods(void)
 498 {
 499   eset * set = eset_create();
 500   int i;
 501   entity ** arr = NEW_ARR_F(entity *, 0);
 502   entity * ent;
 503
 504   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 505     ir_graph * irg = get_irp_irg(i);
 506     entity * ent = get_irg_entity(irg);
 507     /* insert "external visible" methods. */
 508     if (get_entity_visibility(ent) != visibility_local) {
 509       eset_insert(set, ent);
 510     }
 511     /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
 512        z.B. da die Adresse einer Methode abgespeichert wird. */
 513     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 514   }
 515
 516   /* insert sticky methods, too */
 517   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 518     entity * ent = get_irg_entity(get_irp_irg(i));
 519     /* insert "external visible" methods. */
 520     if (get_entity_stickyness (ent) == stickyness_sticky) {
 521       eset_insert(set, ent);
 522     }
 523   }
 524
 525   /* Hauptprogramm ist auch dann frei, wenn es nicht "external
 526    * visible" ist. */
 527   if (get_irp_main_irg()) {
 528     eset_insert(set, get_irg_entity(get_irp_main_irg()));
 529   }
 530   /* Wandle Menge in Feld um.  Effizienter. */
 531   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 532     ARR_APP1(entity *, arr, ent);
 533   }
 534   eset_destroy(set);
 535
 536   return arr;
 537 }
 538
 539 /*--------------------------------------------------------------------------*/
 540 /* Callee analysis.                                                         */
 541 /*--------------------------------------------------------------------------*/
 542
 543 static void callee_ana_node(ir_node * node, eset * methods);
 544
 545 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 546   assert(get_irn_mode(node) == mode_T);
 547   if (get_irn_link(node) == MARK) {
 548     /* already visited */
 549     return;
 550   }
 551   set_irn_link(node, MARK);
 552
 553   switch (get_irn_opcode(node)) {
 554   case iro_Proj: {
 555     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 556      * op_Tuple oder ein Knoten, der eine "freie Methode"
 557      * zurückgibt. */
 558     ir_node * pred = get_Proj_pred(node);
 559     if (get_irn_link(pred) != MARK) {
 560       if (get_irn_op(pred) == op_Tuple) {
 561         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 562       } else {
 563         eset_insert(methods, MARK); /* free method -> unknown */
 564       }
 565     }
 566     break;
 567   }
 568
 569   case iro_Tuple:
 570     callee_ana_node(get_Tuple_pred(node, n), methods);
 571     break;
 572
 573   case iro_Id:
 574     callee_ana_proj(get_Id_pred(node), n, methods);
 575     break;
 576
 577   default:
 578     eset_insert(methods, MARK); /* free method -> unknown */
 579     break;
 580   }
 581
 582   set_irn_link(node, NULL);
 583 }
 584
 585
 586 static void callee_ana_node(ir_node * node, eset * methods) {
 587   int i;
 588
 589   assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
 590   /* rekursion verhindern */
 591   if (get_irn_link(node) == MARK) {
 592     /* already visited */
 593     return;
 594   }
 595   set_irn_link(node, MARK);
 596
 597   switch (get_irn_opcode(node)) {
 598   case iro_SymConst:
 599     if (get_SymConst_kind(node) == symconst_addr_ent) {
 600       entity * ent = get_SymConst_entity(node);
 601       assert(ent && is_Method_type(get_entity_type(ent)));
 602       eset_insert(methods, ent);
 603     } else {
 604       assert(get_SymConst_kind(node) == symconst_addr_name);
 605       /* externe Methode (wegen fix_symconst!) */
 606       eset_insert(methods, MARK); /* free method -> unknown */
 607     }
 608     break;
 609   case iro_Sel:
 610     /* polymorphe Methode */
 611     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 612       entity * ent = get_Sel_method(node, i);
 613       if (ent) {
 614         eset_insert(methods, ent);
 615       } else {
 616         eset_insert(methods, MARK);
 617       }
 618     }
 619     break;
 620
 621   case iro_Bad:
 622     /* nothing */
 623     break;
 624
 625   case iro_Phi: /* Vereinigung */
 626     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 627       callee_ana_node(get_Phi_pred(node, i), methods);
 628     }
 629     break;
 630
 631   case iro_Mux:
 632     callee_ana_node(get_Mux_false(node), methods);
 633     callee_ana_node(get_Mux_true(node), methods);
 634     break;
 635
 636   case iro_Id:
 637     callee_ana_node(get_Id_pred(node), methods);
 638     break;
 639
 640   case iro_Proj:
 641     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 642     break;
 643
 644   case iro_Add:
 645   case iro_Sub:
 646   case iro_Conv:
 647     /* extern */
 648     eset_insert(methods, MARK); /* free method -> unknown */
 649     break;
 650
 651   default:
 652     assert(0 && "invalid opcode or opcode not implemented");
 653     break;
 654   }
 655
 656   set_irn_link(node, NULL);
 657 }
 658
 659
 660 static void callee_walker(ir_node * call, void * env) {
 661   if (get_irn_op(call) == op_Call) {
 662     eset * methods = eset_create();
 663     entity * ent;
 664     entity ** arr = NEW_ARR_F(entity *, 0);
 665     assert(get_irn_op(get_Call_ptr(call)) != op_Id);
 666     callee_ana_node(get_Call_ptr(call), methods);
 667     if (eset_contains(methods, MARK)) { /* unknown method */
 668       ARR_APP1(entity *, arr, unknown_entity);
 669     }
 670     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 671       if (ent != MARK) {
 672         ARR_APP1(entity *, arr, ent);
 673       }
 674     }
 675 #if 0  /* This generates Bad nodes when we don't want it.
 676           Call it with a check for valid cgana information in local_optimize. */
 677     if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
 678       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 679        * Sel-Operation war, die keine Methoden zurückgeben
 680        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 681        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 682        * werden! */
 683       ir_node *mem = get_Call_mem(call);
 684       turn_into_tuple (call, 5 /* pn_Call_max */);
 685       set_Tuple_pred(call, pn_Call_M_regular       , mem);
 686       set_Tuple_pred(call, pn_Call_T_result        , new_Bad());
 687       set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
 688       set_Tuple_pred(call, pn_Call_X_except        , new_Bad());  /* new_Jmp() ?? new_Raise() ?? */
 689       set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
 690
 691     } else
 692 #endif
 693     {
 694       /* remove, what we repaired. */
 695       int i;
 696       for (i = 0; i < ARR_LEN(arr); ++i) {
 697         assert(arr[i]);
 698       }
 699
 700       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 701     }
 702     DEL_ARR_F(arr);
 703     eset_destroy(methods);
 704   }
 705 }
 706
 707
 708 static void remove_Tuples(ir_node * proj, void * env) {
 709   ir_node *new;
 710   if (get_irn_opcode(proj) != iro_Proj) return;
 711
 712   new = skip_Tuple(proj);
 713   if (new != proj) exchange(proj, new);
 714 }
 715
 716
 717 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 718  * und speichert das Ergebnis in der Call-Operation. (siehe
 719  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 720  * muss bereits aufgebaut sein. */
 721 static void callee_ana(void) {
 722   int i;
 723   /* Alle Graphen analysieren. */
 724   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 725     irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
 726     set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
 727   }
 728   set_irp_callee_info_state(irg_callee_info_consistent);
 729 }
 730
 731 /*--------------------------------------------------------------------------*/
 732 /* Cleanup after analyses.                                                  */
 733 /*--------------------------------------------------------------------------*/
 734
 735 /** Frees intermediate data structures. */
 736 static void sel_methods_dispose(void) {
 737   entity * ent;
 738   assert(entities);
 739   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 740     entity ** arr = get_entity_link(ent);
 741     if (arr) {
 742       DEL_ARR_F(arr);
 743     }
 744     set_entity_link(ent, NULL);
 745   }
 746   eset_destroy(entities);
 747   entities = NULL;
 748 }
 749
 750 /*--------------------------------------------------------------------------*/
 751 /* Freeing the callee arrays.                                               */
 752 /*--------------------------------------------------------------------------*/
 753
 754 static void destruct_walker(ir_node * node, void * env) {
 755   if (get_irn_op(node) == op_Call) {
 756     remove_Call_callee_arr(node);
 757   }
 758 }
 759
 760 /*--------------------------------------------------------------------------*/
 761 /* Main drivers.                                                            */
 762 /*--------------------------------------------------------------------------*/
 763
 764 void cgana(int *length, entity ***free_methods) {
 765   entity ** free_meths, **p;
 766
 767   sel_methods_init();
 768   free_meths = get_free_methods();
 769   callee_ana();
 770   sel_methods_dispose();
 771
 772   /* Convert the flexible array to an array that can be handled
 773      by standard C. */
 774   p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
 775   memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));
 776
 777   *length       = ARR_LEN(free_meths);
 778   *free_methods = p;
 779
 780   DEL_ARR_F(free_meths);
 781 }
 782
 783 void free_callee_info(ir_graph *irg) {
 784   irg_walk_graph(irg, destruct_walker, NULL, NULL);
 785   set_irg_callee_info_state(irg, irg_callee_info_none);
 786 }
 787
 788 /* Optimize the address expressions passed to call nodes.
 789  *
 790  * This optimization performs the following transformations for
 791  * all ir graphs:
 792  * - All SymConst operations that refer to intern methods are replaced
 793  *   by Const operations refering to the corresponding entity.
 794  * - Sel nodes, that select entities that are not overwritten are
 795  *   replaced by Const nodes refering to the selected entity.
 796  * - Sel nodes, for which no method exists at all are replaced by Bad
 797  *   nodes.
 798  * - Sel nodes with a pointer input that is an Alloc node are replaced
 799  *   by Const nodes refering to the entity that implements the method in
 800  *   the type given by the Alloc node.
 801  */
 802 void opt_call_addrs(void) {
 803   sel_methods_init();
 804   sel_methods_dispose();
 805 }