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