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_Id:
 547     callee_ana_node(get_Id_pred(node), methods);
 548     break;
 549
 550   case iro_Proj:
 551     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 552     break;
 553
 554   case iro_Add:
 555   case iro_Sub:
 556   case iro_Conv:
 557     /* extern */
 558     eset_insert(methods, MARK); /* free method -> unknown */
 559     break;
 560
 561   default:
 562     assert(0 && "invalid opcode or opcode not implemented");
 563     break;
 564   }
 565
 566   set_irn_link(node, NULL);
 567 }
 568
 569
 570 static void callee_walker(ir_node * call, void * env) {
 571   if (get_irn_op(call) == op_Call) {
 572     eset * methods = eset_create();
 573     entity * ent;
 574     entity ** arr = NEW_ARR_F(entity *, 0);
 575     assert(get_irn_op(get_Call_ptr(call)) != op_Id);
 576     callee_ana_node(get_Call_ptr(call), methods);
 577     if (eset_contains(methods, MARK)) { /* unknown method */
 578       ARR_APP1(entity *, arr, unknown_entity);
 579     }
 580     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 581       if (ent != MARK) {
 582         ARR_APP1(entity *, arr, ent);
 583       }
 584     }
 585 #if 0  /* This generates Bad nodes when we don't want it.
 586           Call it with a check for valid cgana information in local_optimize. */
 587     if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
 588       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 589        * Sel-Operation war, die keine Methoden zurückgeben
 590        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 591        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 592        * werden! */
 593       ir_node *mem = get_Call_mem(call);
 594       turn_into_tuple (call, 5 /* pn_Call_max */);
 595       set_Tuple_pred(call, pn_Call_M_regular       , mem);
 596       set_Tuple_pred(call, pn_Call_T_result        , new_Bad());
 597       set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
 598       set_Tuple_pred(call, pn_Call_X_except        , new_Bad());  /* new_Jmp() ?? new_Raise() ?? */
 599       set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
 600
 601     } else
 602 #endif
 603     {
 604       /* remove, what we repaired. */
 605       int i;
 606       for (i = 0; i < ARR_LEN(arr); ++i) {
 607         assert(arr[i]);
 608         //if (arr[i] == unknown_entity) arr[i] = NULL;
 609       }
 610
 611       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 612     }
 613     DEL_ARR_F(arr);
 614     eset_destroy(methods);
 615   }
 616 }
 617
 618
 619 static void remove_Tuples(ir_node * proj, void * env) {
 620   ir_node *new;
 621   if (get_irn_opcode(proj) != iro_Proj) return;
 622
 623   new = skip_Tuple(proj);
 624   if (new != proj) exchange(proj, new);
 625 }
 626
 627
 628 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 629  * und speichert das Ergebnis in der Call-Operation. (siehe
 630  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 631  * muss bereits aufgebaut sein. */
 632 static void callee_ana(void) {
 633   int i;
 634   /* Alle Graphen analysieren. */
 635   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 636     irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
 637     set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
 638   }
 639   set_irp_callee_info_state(irg_callee_info_consistent);
 640 }
 641
 642
 643
 644 /* --- free method analysis ------------------------------------------------- */
 645
 646
 647 static void free_mark(ir_node * node, eset * set);
 648
 649 static void free_mark_proj(ir_node * node, long n, eset * set) {
 650   assert(get_irn_mode(node) == mode_T);
 651   if (get_irn_link(node) == MARK) {
 652     /* already visited */
 653     return;
 654   }
 655   set_irn_link(node, MARK);
 656   switch (get_irn_opcode(node)) {
 657   case iro_Proj: {
 658     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 659      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 660      * wird. */
 661     ir_node * pred = get_Proj_pred(node);
 662     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 663       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 664     } else {
 665       /* nothing: da in "free_ana_walker" behandelt. */
 666     }
 667     break;
 668   }
 669
 670   case iro_Tuple:
 671     free_mark(get_Tuple_pred(node, n), set);
 672     break;
 673
 674   case iro_Id:
 675     free_mark_proj(get_Id_pred(node), n, set);
 676     break;
 677
 678   case iro_Start:
 679   case iro_Alloc:
 680   case iro_Load:
 681     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 682      * behandelt. */
 683     break;
 684
 685   default:
 686     assert(0 && "unexpected opcode or opcode not implemented");
 687     break;
 688   }
 689   set_irn_link(node, NULL);
 690 }
 691
 692
 693 static void free_mark(ir_node * node, eset * set) {
 694   int i;
 695
 696   if (get_irn_link(node) == MARK) {
 697     return; /* already visited */
 698   }
 699   set_irn_link(node, MARK);
 700   switch (get_irn_opcode(node)) {
 701   case iro_Sel: {
 702     entity * ent = get_Sel_entity(node);
 703     if (is_Method_type(get_entity_type(ent))) {
 704       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 705         eset_insert(set, get_Sel_method(node, i));
 706       }
 707     }
 708     break;
 709   }
 710   case iro_SymConst:
 711     if (get_SymConst_kind(node) == symconst_addr_ent) {
 712       entity * ent = get_SymConst_entity(node);
 713       if (is_Method_type(get_entity_type(ent))) {
 714         eset_insert(set, ent);
 715       }
 716     } else {
 717       assert(get_SymConst_kind(node) == symconst_addr_name);
 718       /* nothing: SymConst points to extern method */
 719     }
 720     break;
 721
 722   case iro_Phi:
 723     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 724       free_mark(get_Phi_pred(node, i), set);
 725     }
 726     break;
 727   case iro_Id:
 728     free_mark(get_Id_pred(node), set);
 729     break;
 730   case iro_Proj:
 731     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 732     break;
 733   default:
 734     /* nothing: Wird unten behandelt! */
 735     break;
 736   }
 737   set_irn_link(node, NULL);
 738 }
 739
 740
 741 static void free_ana_walker(ir_node * node, eset * set) {
 742   int i;
 743   if (get_irn_link(node) == MARK) {
 744     /* bereits in einem Zyklus besucht. */
 745     return;
 746   }
 747   switch (get_irn_opcode(node)) {
 748   /* special nodes */
 749   case iro_Sel:
 750   case iro_SymConst:
 751   case iro_Const:
 752   case iro_Phi:
 753   case iro_Id:
 754   case iro_Proj:
 755   case iro_Tuple:
 756     /* nothing */
 757     break;
 758   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 759    * Verräter ist. */
 760   case iro_Call:
 761     set_irn_link(node, MARK);
 762     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 763       ir_node * pred = get_Call_param(node, i);
 764       if (mode_is_reference(get_irn_mode(pred))) {
 765         free_mark(pred, set);
 766       }
 767     }
 768     break;
 769   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 770    * jemand das Gegenteil implementiert. */
 771   default:
 772     set_irn_link(node, MARK);
 773     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 774       ir_node * pred = get_irn_n(node, i);
 775       if (mode_is_reference(get_irn_mode(pred))) {
 776         free_mark(pred, set);
 777       }
 778     }
 779     break;
 780   }
 781   set_irn_link(node, NULL);
 782 }
 783
 784
 785 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 786  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 787  * SymConst-Operationen müssen in passende Const-Operationen
 788  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 789  * auf eine echt externe Methode.  */
 790 static entity ** get_free_methods(void)
 791 {
 792   eset * set = eset_create();
 793   int i;
 794   entity ** arr = NEW_ARR_F(entity *, 0);
 795   entity * ent;
 796
 797   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 798     ir_graph * irg = get_irp_irg(i);
 799     entity * ent = get_irg_entity(irg);
 800     /* insert "external visible" methods. */
 801     if (get_entity_visibility(ent) != visibility_local) {
 802       eset_insert(set, ent);
 803     }
 804     /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
 805        z.B. da die Adresse einer Methode abgespeichert wird. */
 806     irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
 807   }
 808
 809   /* insert sticky methods, too */
 810   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 811     ir_graph * irg = get_irp_irg(i);
 812     entity * ent = get_irg_entity(irg);
 813     /* insert "external visible" methods. */
 814     if (get_entity_stickyness (ent) == stickyness_sticky) {
 815       eset_insert(set, ent);
 816     }
 817   }
 818
 819   /* Hauptprogramm ist auch dann frei, wenn es nicht "external
 820    * visible" ist. */
 821   if (get_irp_main_irg()) {
 822     eset_insert(set, get_irg_entity(get_irp_main_irg()));
 823   }
 824   /* Wandle Menge in Feld um.  Effizienter. */
 825   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 826     ARR_APP1(entity *, arr, ent);
 827   }
 828   eset_destroy(set);
 829
 830   return arr;
 831 }
 832
 833 void cgana(int *length, entity ***free_methods) {
 834   entity ** free_meths, **p;
 835
 836   sel_methods_init();
 837   free_meths = get_free_methods();
 838   callee_ana();
 839   sel_methods_dispose();
 840
 841   /* Convert the flexible array to an array that can be handled
 842      by standard C. */
 843   p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
 844   memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));
 845
 846   *length       = ARR_LEN(free_meths);
 847   *free_methods = p;
 848
 849   DEL_ARR_F(free_meths);
 850 }
 851
 852
 853
 854 static void destruct_walker(ir_node * node, void * env) {
 855   if (get_irn_op(node) == op_Call) {
 856     remove_Call_callee_arr(node);
 857   }
 858 }
 859
 860 void free_callee_info(ir_graph *irg) {
 861   irg_walk_graph(irg, destruct_walker, NULL, NULL);
 862   set_irg_callee_info_state(irg, irg_callee_info_none);
 863 }
 864
 865
 866 /* Optimize the address expressions passed to call nodes.
 867  *
 868  * This optimization performs the following transformations for
 869  * all ir graphs:
 870  * - All SymConst operations that refer to intern methods are replaced
 871  *   by Const operations refering to the corresponding entity.
 872  * - Sel nodes, that select entities that are not overwritten are
 873  *   replaced by Const nodes refering to the selected entity.
 874  * - Sel nodes, for witch no method exists at all are replaced by Bad
 875  *   nodes.
 876  * - Sel nodes with a pointer input that is an Alloc node are replaced
 877  *   by Const nodes refering to the entity that implements the method in
 878  *   the type given by the Alloc node.
 879  */
 880 void opt_call_addrs(void) {
 881   sel_methods_init();
 882   sel_methods_dispose();
 883 }