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