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_allirgs() - 1; i >= 0; --i) {
 373     entity * ent = get_irg_entity(get_irp_allirg(i));
 374     /* Nur extern sichtbare Methode können überhaupt mit SymConst
 375      * aufgerufen werden. */
 376     if (get_entity_visibility(ent) != visibility_local) {
 377       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 378     }
 379   }
 380   all_irg_walk(sel_methods_walker, NULL, ldname_map);
 381   pmap_destroy(ldname_map);
 382 }
 383
 384 /*****************************************************************************/
 385
 386 /** Frees the allocated entity map */
 387 static void sel_methods_dispose(void) {
 388   entity * ent;
 389   assert(entities);
 390   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 391     entity ** arr = get_entity_link(ent);
 392     if (arr) {
 393       DEL_ARR_F(arr);
 394     }
 395     set_entity_link(ent, NULL);
 396   }
 397   eset_destroy(entities);
 398   entities = NULL;
 399 }
 400
 401
 402 /**
 403  * Returns an array of all methods that could be called at a Sel node.
 404  * This array contains every entry only once.
 405  */
 406 static entity ** get_Sel_arr(ir_node * sel) {
 407   static entity ** NULL_ARRAY = NULL;
 408   entity * ent;
 409   entity ** arr;
 410
 411   assert(sel && get_irn_op(sel) == op_Sel);
 412   ent = get_Sel_entity(sel);
 413   assert(is_method_type(get_entity_type(ent))); /* what else? */
 414   arr = get_entity_link(ent);
 415   if (arr) {
 416     return arr;
 417   } else {
 418     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 419      * kann für polymorphe (abstrakte) Methoden passieren. */
 420     if (!NULL_ARRAY) {
 421       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 422     }
 423     return NULL_ARRAY;
 424   }
 425 }
 426
 427 /**
 428  * Returns the number of possible called methods at a Sel node.
 429  */
 430 static int get_Sel_n_methods(ir_node * sel) {
 431   return ARR_LEN(get_Sel_arr(sel));
 432 }
 433
 434 /**
 435  * Returns the ith possible called method entity at a Sel node.
 436  */
 437 static entity * get_Sel_method(ir_node * sel, int pos) {
 438   entity ** arr = get_Sel_arr(sel);
 439   assert(pos >= 0 && pos < ARR_LEN(arr));
 440   return arr[pos];
 441 }
 442
 443
 444
 445 /* --- callee analysis ------------------------------------------------------ */
 446
 447
 448 static void callee_ana_node(ir_node * node, eset * methods);
 449
 450
 451 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 452   assert(get_irn_mode(node) == mode_T);
 453   if (get_irn_link(node) == MARK) {
 454     /* already visited */
 455     return;
 456   }
 457   set_irn_link(node, MARK);
 458
 459   switch (get_irn_opcode(node)) {
 460   case iro_Proj: {
 461     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 462      * op_Tuple oder ein Knoten, der eine "freie Methode"
 463      * zurückgibt. */
 464     ir_node * pred = get_Proj_pred(node);
 465     if (get_irn_link(pred) != MARK) {
 466       if (get_irn_op(pred) == op_Tuple) {
 467         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 468       } else {
 469         eset_insert(methods, MARK); /* free method -> unknown */
 470       }
 471     }
 472     break;
 473   }
 474
 475   case iro_Tuple:
 476     callee_ana_node(get_Tuple_pred(node, n), methods);
 477     break;
 478
 479   case iro_Id:
 480     callee_ana_proj(get_Id_pred(node), n, methods);
 481     break;
 482
 483   default:
 484     eset_insert(methods, MARK); /* free method -> unknown */
 485     break;
 486   }
 487
 488   set_irn_link(node, NULL);
 489 }
 490
 491
 492 static void callee_ana_node(ir_node * node, eset * methods) {
 493   int i;
 494
 495   assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
 496   /* rekursion verhindern */
 497   if (get_irn_link(node) == MARK) {
 498     /* already visited */
 499     return;
 500   }
 501   set_irn_link(node, MARK);
 502
 503   switch (get_irn_opcode(node)) {
 504   case iro_SymConst:
 505     if (get_SymConst_kind(node) == symconst_addr_ent) {
 506       entity * ent = get_SymConst_entity(node);
 507       assert(ent && is_method_type(get_entity_type(ent)));
 508       eset_insert(methods, ent);
 509     } else {
 510       assert(get_SymConst_kind(node) == symconst_addr_name);
 511       /* externe Methode (wegen fix_symconst!) */
 512       eset_insert(methods, MARK); /* free method -> unknown */
 513     }
 514     break;
 515   case iro_Sel:
 516     /* polymorphe Methode */
 517     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 518       entity * ent = get_Sel_method(node, i);
 519       if (ent) {
 520         eset_insert(methods, ent);
 521       } else {
 522         eset_insert(methods, MARK);
 523       }
 524     }
 525     break;
 526
 527   case iro_Bad:
 528     /* nothing */
 529     break;
 530
 531   case iro_Phi: /* Vereinigung */
 532     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 533       callee_ana_node(get_Phi_pred(node, i), methods);
 534     }
 535     break;
 536
 537   case iro_Id:
 538     callee_ana_node(get_Id_pred(node), methods);
 539     break;
 540
 541   case iro_Proj:
 542     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 543     break;
 544
 545   case iro_Add:
 546   case iro_Sub:
 547   case iro_Conv:
 548     /* extern */
 549     eset_insert(methods, MARK); /* free method -> unknown */
 550     break;
 551
 552   default:
 553     assert(0 && "invalid opcode or opcode not implemented");
 554     break;
 555   }
 556
 557   set_irn_link(node, NULL);
 558 }
 559
 560
 561 static void callee_walker(ir_node * call, void * env) {
 562   if (get_irn_op(call) == op_Call) {
 563     eset * methods = eset_create();
 564     entity * ent;
 565     entity ** arr = NEW_ARR_F(entity *, 0);
 566     assert(get_irn_op(get_Call_ptr(call)) != op_Id);
 567     callee_ana_node(get_Call_ptr(call), methods);
 568     if (eset_contains(methods, MARK)) { /* unknown method */
 569       ARR_APP1(entity *, arr, unknown_entity);
 570     }
 571     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 572       if (ent != MARK) {
 573         ARR_APP1(entity *, arr, ent);
 574       }
 575     }
 576 #if 0  /* This generates Bad nodes when we don't want it.
 577           Call it with a check for valid cgana information in local_optimize. */
 578     if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
 579       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 580        * Sel-Operation war, die keine Methoden zurückgeben
 581        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 582        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 583        * werden! */
 584       ir_node *mem = get_Call_mem(call);
 585       turn_into_tuple (call, 5 /* pn_Call_max */);
 586       set_Tuple_pred(call, pn_Call_M_regular       , mem);
 587       set_Tuple_pred(call, pn_Call_T_result        , new_Bad());
 588       set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
 589       set_Tuple_pred(call, pn_Call_X_except        , new_Bad());  /* new_Jmp() ?? new_Raise() ?? */
 590       set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
 591
 592     } else
 593 #endif
 594     {
 595       /* remove, what we repaired. */
 596       int i;
 597       for (i = 0; i < ARR_LEN(arr); ++i) {
 598         assert(arr[i]);
 599         //if (arr[i] == unknown_entity) arr[i] = NULL;
 600       }
 601
 602       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 603     }
 604     DEL_ARR_F(arr);
 605     eset_destroy(methods);
 606   }
 607 }
 608
 609
 610 static void remove_Tuples(ir_node * proj, void * env) {
 611   ir_node *new;
 612   if (get_irn_opcode(proj) != iro_Proj) return;
 613
 614   new = skip_Tuple(proj);
 615   if (new != proj) exchange(proj, new);
 616 }
 617
 618
 619 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 620  * und speichert das Ergebnis in der Call-Operation. (siehe
 621  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 622  * muss bereits aufgebaut sein. */
 623 static void callee_ana(void) {
 624   int i;
 625   /* Alle Graphen analysieren. */
 626   for (i = get_irp_n_allirgs() - 1; i >= 0; --i) {
 627     irg_walk_graph(get_irp_allirg(i), callee_walker, remove_Tuples, NULL);
 628     set_irg_callee_info_state(get_irp_allirg(i), irg_callee_info_consistent);
 629   }
 630   set_irp_callee_info_state(irg_callee_info_consistent);
 631 }
 632
 633
 634
 635 /* --- free method analysis ------------------------------------------------- */
 636
 637
 638 static void free_mark(ir_node * node, eset * set);
 639
 640 static void free_mark_proj(ir_node * node, long n, eset * set) {
 641   assert(get_irn_mode(node) == mode_T);
 642   if (get_irn_link(node) == MARK) {
 643     /* already visited */
 644     return;
 645   }
 646   set_irn_link(node, MARK);
 647   switch (get_irn_opcode(node)) {
 648   case iro_Proj: {
 649     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 650      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 651      * wird. */
 652     ir_node * pred = get_Proj_pred(node);
 653     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 654       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 655     } else {
 656       /* nothing: da in "free_ana_walker" behandelt. */
 657     }
 658     break;
 659   }
 660
 661   case iro_Tuple:
 662     free_mark(get_Tuple_pred(node, n), set);
 663     break;
 664
 665   case iro_Id:
 666     free_mark_proj(get_Id_pred(node), n, set);
 667     break;
 668
 669   case iro_Start:
 670   case iro_Alloc:
 671   case iro_Load:
 672     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 673      * behandelt. */
 674     break;
 675
 676   default:
 677     assert(0 && "unexpected opcode or opcode not implemented");
 678     break;
 679   }
 680   set_irn_link(node, NULL);
 681 }
 682
 683
 684 static void free_mark(ir_node * node, eset * set) {
 685   int i;
 686
 687   if (get_irn_link(node) == MARK) {
 688     return; /* already visited */
 689   }
 690   set_irn_link(node, MARK);
 691   switch (get_irn_opcode(node)) {
 692   case iro_Sel: {
 693     entity * ent = get_Sel_entity(node);
 694     if (is_method_type(get_entity_type(ent))) {
 695       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 696     eset_insert(set, get_Sel_method(node, i));
 697       }
 698     }
 699     break;
 700   }
 701   case iro_SymConst:
 702     if (get_SymConst_kind(node) == symconst_addr_ent) {
 703       entity * ent = get_SymConst_entity(node);
 704       if (is_method_type(get_entity_type(ent))) {
 705         eset_insert(set, ent);
 706       }
 707     } else {
 708       assert(get_SymConst_kind(node) == symconst_addr_name);
 709       /* nothing: SymConst points to extern method */
 710     }
 711     break;
 712
 713   case iro_Phi:
 714     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 715       free_mark(get_Phi_pred(node, i), set);
 716     }
 717     break;
 718   case iro_Id:
 719     free_mark(get_Id_pred(node), set);
 720     break;
 721   case iro_Proj:
 722     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 723     break;
 724   default:
 725     /* nothing: Wird unten behandelt! */
 726     break;
 727   }
 728   set_irn_link(node, NULL);
 729 }
 730
 731
 732 static void free_ana_walker(ir_node * node, eset * set) {
 733   int i;
 734   if (get_irn_link(node) == MARK) {
 735     /* bereits in einem Zyklus besucht. */
 736     return;
 737   }
 738   switch (get_irn_opcode(node)) {
 739   /* special nodes */
 740   case iro_Sel:
 741   case iro_SymConst:
 742   case iro_Const:
 743   case iro_Phi:
 744   case iro_Id:
 745   case iro_Proj:
 746   case iro_Tuple:
 747     /* nothing */
 748     break;
 749   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 750    * Verräter ist. */
 751   case iro_Call:
 752     set_irn_link(node, MARK);
 753     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 754       ir_node * pred = get_Call_param(node, i);
 755       if (mode_is_reference(get_irn_mode(pred))) {
 756         free_mark(pred, set);
 757       }
 758     }
 759     break;
 760   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 761    * jemand das Gegenteil implementiert. */
 762   default:
 763     set_irn_link(node, MARK);
 764     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 765       ir_node * pred = get_irn_n(node, i);
 766       if (mode_is_reference(get_irn_mode(pred))) {
 767         free_mark(pred, set);
 768       }
 769     }
 770     break;
 771   }
 772   set_irn_link(node, NULL);
 773 }
 774
 775
 776 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 777  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 778  * SymConst-Operationen müssen in passende Const-Operationen
 779  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 780  * auf eine echt externe Methode.  */
 781 static entity ** get_free_methods(void)
 782 {
 783   eset * set = eset_create();
 784   int i;
 785   entity ** arr = NEW_ARR_F(entity *, 0);
 786   entity * ent;
 787
 788   for (i = get_irp_n_allirgs() - 1; i >= 0; --i) {
 789     ir_graph * irg = get_irp_allirg(i);
 790     entity * ent = get_irg_entity(irg);
 791     /* insert "external visible" methods. */
 792     if (get_entity_visibility(ent) != visibility_local) {
 793       eset_insert(set, ent);
 794     }
 795     /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
 796        z.B. da die Adresse einer Methode abgespeichert wird. */
 797     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 798   }
 799
 800   /* insert sticky methods, too */
 801   for (i = get_irp_n_allirgs() - 1; i >= 0; --i) {
 802     ir_graph * irg = get_irp_allirg(i);
 803     entity * ent = get_irg_entity(irg);
 804     /* insert "external visible" methods. */
 805     if (get_entity_stickyness (ent) == stickyness_sticky) {
 806       eset_insert(set, ent);
 807     }
 808   }
 809
 810   /* Hauptprogramm ist auch dann frei, wenn es nicht "external
 811    * visible" ist. */
 812   if (get_irp_main_irg()) {
 813     eset_insert(set, get_irg_entity(get_irp_main_irg()));
 814   }
 815   /* Wandle Menge in Feld um.  Effizienter. */
 816   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 817     ARR_APP1(entity *, arr, ent);
 818   }
 819   eset_destroy(set);
 820
 821   return arr;
 822 }
 823
 824 void cgana(int *length, entity ***free_methods) {
 825   entity ** free_meths, **p;
 826
 827   sel_methods_init();
 828   free_meths = get_free_methods();
 829   callee_ana();
 830   sel_methods_dispose();
 831
 832   /* Convert the flexible array to an array that can be handled
 833      by standard C. */
 834   p = (entity **)malloc(sizeof(*p) * ARR_LEN(free_meths));
 835   memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));
 836
 837   *length       = ARR_LEN(free_meths);
 838   *free_methods = p;
 839
 840   DEL_ARR_F(free_meths);
 841 }
 842
 843
 844
 845 static void destruct_walker(ir_node * node, void * env) {
 846   if (get_irn_op(node) == op_Call) {
 847     remove_Call_callee_arr(node);
 848   }
 849 }
 850
 851 void free_callee_info(ir_graph *irg) {
 852   irg_walk_graph(irg, destruct_walker, NULL, NULL);
 853   set_irg_callee_info_state(irg, irg_callee_info_none);
 854 }
 855
 856
 857 /* Optimize the address expressions passed to call nodes.
 858  *
 859  * This optimization performs the following transformations for
 860  * all ir graphs:
 861  * - All SymConst operations that refer to intern methods are replaced
 862  *   by Const operations refering to the corresponding entity.
 863  * - Sel nodes, that select entities that are not overwritten are
 864  *   replaced by Const nodes refering to the selected entity.
 865  * - Sel nodes, for witch no method exists at all are replaced by Bad
 866  *   nodes.
 867  * - Sel nodes with a pointer input that is an Alloc node are replaced
 868  *   by Const nodes refering to the entity that implements the method in
 869  *   the type given by the Alloc node.
 870  */
 871 void opt_call_addrs(void) {
 872   sel_methods_init();
 873   sel_methods_dispose();
 874 }