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