nsz Git - libfirm/blob - ir/ana/cgana.c

   1 /* -------------------------------------------------------------------
   2  * $Id$
   3  * -------------------------------------------------------------------
   4  * Intraprozedurale Analyse zur Abschätzung der Aufrulrelation. Es
   5  * wird eine Menge von freien Methoden und anschließend die an den
   6  * Call-Operationen aufrufbaren Methoden bestimmt.
   7  *
   8  * Erstellt: Hubert Schmid, 09.06.2002
   9  * ---------------------------------------------------------------- */
  10
  11
  12 #include "cgana.h"
  13
  14
  15 #include "eset.h"
  16 #include "pmap.h"
  17 #include "array.h"
  18 #include "irprog.h"
  19 #include "irgwalk.h"
  20 #include "ircons.h"
  21 #include "irgmod.h"
  22
  23
  24 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
  25  * Darstellung der unbekannten Methode. */
  26 static void * MARK = &MARK;
  27
  28
  29
  30 /* --- sel methods ---------------------------------------------------------- */
  31
  32
  33 static eset * entities = NULL;
  34
  35
  36 /* Bestimmt die eindeutige Methode, die die Methode für den
  37  * übergebenene (dynamischen) Typ überschreibt. */
  38 static entity * get_implementation(type * class, entity * method) {
  39   int i;
  40   if (get_entity_peculiarity(method) != description && get_entity_owner(method) == class) {
  41     return method;
  42   }
  43   for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
  44     entity * e = get_entity_overwrittenby(method, i);
  45     if (get_entity_peculiarity(e) != description && get_entity_owner(e) == class) {
  46       return e;
  47     }
  48   }
  49   for (i = get_class_n_supertype(class) - 1; i >= 0; --i) {
  50     entity * e = get_implementation(get_class_supertype(class, i), method);
  51     if (e) {
  52       return e;
  53     }
  54   }
  55   assert(0 && "implemenation not found");
  56 }
  57
  58
  59 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
  60  * (und implementieren). In der zurückgegebenen Reihung kommt jede
  61  * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
  62  * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
  63  * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
  64  * keine Methoden, die die "method" überschreiben, so gibt die Methode
  65  * "NULL" zurück. */
  66 static entity ** get_impl_methods(entity * method) {
  67   eset * set = eset_create();
  68   int size = 0;
  69   int i;
  70   entity ** arr;
  71   bool open = false;
  72   if (get_entity_peculiarity(method) == existent) {
  73     if (get_entity_visibility(method) == external_allocated) {
  74       assert(get_entity_irg(method) == NULL);
  75       open = true;
  76     } else {
  77       assert(get_entity_irg(method) != NULL);
  78       eset_insert(set, method);
  79       ++size;
  80     }
  81   }
  82   for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
  83     entity * ent = get_entity_overwrittenby(method, i);
  84     if (get_entity_peculiarity(ent) == existent) {
  85       if (get_entity_visibility(ent) == external_allocated) {
  86         assert(get_entity_irg(ent) == NULL);
  87         open = true;
  88       } else {
  89         assert(get_entity_irg(ent) != NULL);
  90         if (!eset_contains(set, ent)) {
  91           eset_insert(set, ent);
  92           ++size;
  93         }
  94       }
  95     }
  96   }
  97   if (size == 0 && !open) {
  98     /* keine implementierte überschriebene Methode */
  99     arr = NULL;
 100   } else if (open) {
 101     entity * ent;
 102     arr = NEW_ARR_F(entity *, size + 1);
 103     arr[0] = NULL;
 104     for (ent = eset_first(set); size > 0; ent = eset_next(set), --size) arr[size] = ent;
 105   } else {
 106     entity * ent;
 107     arr = NEW_ARR_F(entity *, size);
 108     for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size) arr[size] = ent;
 109   }
 110   eset_destroy(set);
 111   return arr;
 112 }
 113
 114
 115 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
 116   if (get_irn_op(node) == op_SymConst) {
 117     /* Wenn möglich SymConst-Operation durch Const-Operation
 118      * ersetzen. */
 119     if (get_SymConst_kind(node) == linkage_ptr_info) {
 120       pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
 121       if (entry != NULL) {
 122         entity * ent = entry->value;
 123         if (get_entity_visibility(ent) != external_allocated) {
 124           assert(get_entity_irg(ent));
 125           set_irg_current_block(current_ir_graph, get_nodes_Block(node));
 126           exchange(node, new_Const(mode_p, tarval_p_from_entity(ent)));
 127         }
 128       }
 129     }
 130   } else if (get_irn_op(node) == op_Sel && is_method_type(get_entity_type(get_Sel_entity(node)))) {
 131     entity * ent = get_Sel_entity(node);
 132     if (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc) {
 133       ent = get_implementation(get_Alloc_type(skip_Proj(get_Sel_ptr(node))), ent);
 134       if (get_entity_visibility(ent) == external_allocated) {
 135         exchange(node, new_SymConst((type_or_id_p) get_entity_ld_ident(ent), linkage_ptr_info));
 136       } else {
 137         exchange(node, new_Const(mode_p, tarval_p_from_entity(ent)));
 138       }
 139     } else {
 140       if (!eset_contains(entities, ent)) {
 141         /* Entity noch nicht behandelt. Alle (intern oder extern)
 142          * implementierten Methoden suchen, die diese Entity
 143          * überschreiben. Die Menge an entity.link speichern. */
 144         set_entity_link(ent, get_impl_methods(ent));
 145         eset_insert(entities, ent);
 146       }
 147       if (get_entity_link(ent) == NULL) {
 148         /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
 149          * Methode zurückgeben. Damit ist sie insbesondere nicht
 150          * ausführbar und nicht erreichbar. */
 151         /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
 152            fuer die es keine Implementierung gibt. */
 153         if (get_entity_peculiarity(ent) == description) {
 154           /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
 155           xprintf("WARNING: Calling method description %I in method %I which has "
 156                   "no implementation!\n", get_entity_ident(ent),
 157                   get_entity_ident(get_irg_ent(current_ir_graph)));
 158         } else {
 159           exchange(node, new_Bad());
 160         }
 161       } else {
 162         entity ** arr = get_entity_link(ent);
 163         if (ARR_LEN(arr) == 1 && arr[0] != NULL) {
 164           /* Die Sel-Operation kann immer nur einen Wert auf eine
 165            * interne Methode zurückgeben. Wir können daher die
 166            * Sel-Operation durch eine Const- bzw. SymConst-Operation
 167            * ersetzen. */
 168           if (get_entity_visibility(arr[0]) == external_allocated) {
 169             exchange(node, new_SymConst((type_or_id_p) get_entity_ld_ident(arr[0]),
 170                                         linkage_ptr_info));
 171           } else {
 172             exchange(node, new_Const(mode_p, tarval_p_from_entity(arr[0])));
 173           }
 174         }
 175       }
 176     }
 177   }
 178 }
 179
 180
 181 /* Datenstruktur initialisieren. Zusätzlich werden alle
 182  * SymConst-Operationen, die auf interne Methode verweisen, durch
 183  * Const-Operationen ersetzt. */
 184 static void sel_methods_init(void) {
 185   int i;
 186   pmap * ldname_map = pmap_create();
 187   assert(entities == NULL);
 188   entities = eset_create();
 189   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 190     entity * ent = get_irg_ent(get_irp_irg(i));
 191     /* Nur extern sichtbare Methode können überhaupt mit SymConst
 192      * aufgerufen werden. */
 193     if (get_entity_visibility(ent) != local) {
 194       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 195     }
 196   }
 197   all_irg_walk((irg_walk_func) sel_methods_walker, NULL, ldname_map);
 198   pmap_destroy(ldname_map);
 199 }
 200
 201
 202 /* Datenstruktur freigeben. */
 203 static void sel_methods_dispose(void) {
 204   entity * ent;
 205   assert(entities);
 206   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 207     entity ** arr = get_entity_link(ent);
 208     if (arr) {
 209       DEL_ARR_F(arr);
 210     }
 211     set_entity_link(ent, NULL);
 212   }
 213   eset_destroy(entities);
 214   entities = NULL;
 215 }
 216
 217
 218 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
 219  * zurückgegeben werden können. Die Liste enthält keine doppelten
 220  * Einträge. */
 221 static entity ** get_Sel_arr(ir_node * sel) {
 222   static entity ** NULL_ARRAY = NULL;
 223   entity * ent;
 224   entity ** arr;
 225   assert(sel && get_irn_op(sel) == op_Sel);
 226   ent = get_Sel_entity(sel);
 227   assert(is_method_type(get_entity_type(ent))); /* what else? */
 228   arr = get_entity_link(ent);
 229   if (arr) {
 230     return arr;
 231   } else {
 232     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 233      * kann für polymorphe (abstrakte) Methoden passieren. */
 234     if (!NULL_ARRAY) {
 235       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 236     }
 237     return NULL_ARRAY;
 238   }
 239 }
 240
 241
 242 static int get_Sel_n_methods(ir_node * sel) {
 243   return ARR_LEN(get_Sel_arr(sel));
 244 }
 245
 246
 247 static entity * get_Sel_method(ir_node * sel, int pos) {
 248   entity ** arr = get_Sel_arr(sel);
 249   assert(pos >= 0 && pos < ARR_LEN(arr));
 250   return arr[pos];
 251 }
 252
 253
 254
 255 /* --- callee analysis ------------------------------------------------------ */
 256
 257
 258 static void callee_ana_node(ir_node * node, eset * methods);
 259
 260
 261 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 262   assert(get_irn_mode(node) == mode_T);
 263   if (get_irn_link(node) == MARK) {
 264     /* already visited */
 265     return;
 266   }
 267   set_irn_link(node, MARK);
 268
 269   switch (get_irn_opcode(node)) {
 270   case iro_Proj: {
 271     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 272      * op_Tuple oder ein Knoten, der eine "freie Methode"
 273      * zurückgibt. */
 274     ir_node * pred = get_Proj_pred(node);
 275     if (get_irn_link(pred) != MARK) {
 276       if (get_irn_op(pred) == op_Tuple) {
 277         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 278       } else {
 279         eset_insert(methods, MARK); /* free method -> unknown */
 280       }
 281     }
 282     break;
 283   }
 284
 285   case iro_Tuple:
 286     callee_ana_node(get_Tuple_pred(node, n), methods);
 287     break;
 288
 289   case iro_Id:
 290     callee_ana_proj(get_Id_pred(node), n, methods);
 291     break;
 292
 293   default:
 294     eset_insert(methods, MARK); /* free method -> unknown */
 295     break;
 296   }
 297
 298   set_irn_link(node, NULL);
 299 }
 300
 301
 302 static void callee_ana_node(ir_node * node, eset * methods) {
 303   int i;
 304
 305   assert(get_irn_mode(node) == mode_p);
 306   /* rekursion verhindern */
 307   if (get_irn_link(node) == MARK) {
 308     /* already visited */
 309     return;
 310   }
 311   set_irn_link(node, MARK);
 312
 313   switch (get_irn_opcode(node)) {
 314   case iro_SymConst:
 315     /* externe Methode (wegen fix_symconst!) */
 316     eset_insert(methods, MARK); /* free method -> unknown */
 317     break;
 318
 319   case iro_Const: {
 320     /* interne Methode */
 321     entity * ent = get_Const_tarval(node)->u.p.ent;
 322     assert(ent && is_method_type(get_entity_type(ent)));
 323     if (get_entity_visibility(ent) != external_allocated) {
 324       assert(get_entity_irg(ent));
 325       eset_insert(methods, ent);
 326     } else {
 327       eset_insert(methods, MARK); /* free method -> unknown */
 328     }
 329     break;
 330   }
 331
 332   case iro_Sel:
 333     /* polymorphe Methode */
 334     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 335       entity * ent = get_Sel_method(node, i);
 336       if (ent) {
 337         eset_insert(methods, ent);
 338       } else {
 339         eset_insert(methods, MARK);
 340       }
 341     }
 342     break;
 343
 344   case iro_Bad:
 345     /* nothing */
 346     break;
 347
 348   case iro_Phi: /* Vereinigung */
 349     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 350       callee_ana_node(get_Phi_pred(node, i), methods);
 351     }
 352     break;
 353
 354   case iro_Id:
 355     callee_ana_node(get_Id_pred(node), methods);
 356     break;
 357
 358   case iro_Proj:
 359     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 360     break;
 361
 362   case iro_Add:
 363   case iro_Sub:
 364   case iro_Conv:
 365     /* extern */
 366     eset_insert(methods, MARK); /* free method -> unknown */
 367     break;
 368
 369   default:
 370     assert(0 && "invalid opcode or opcode not implemented");
 371     break;
 372   }
 373
 374   set_irn_link(node, NULL);
 375 }
 376
 377
 378 static void callee_walker(ir_node * call, void * env) {
 379   if (get_irn_op(call) == op_Call) {
 380     eset * methods = eset_create();
 381     entity * ent;
 382     entity ** arr = NEW_ARR_F(entity *, 0);
 383     callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
 384     if (eset_contains(methods, MARK)) { /* unknown method */
 385       ARR_APP1(entity *, arr, NULL);
 386     }
 387     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 388       if (ent != MARK) {
 389         ARR_APP1(entity *, arr, ent);
 390       }
 391     }
 392     if (ARR_LEN(arr) == 0) {
 393       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 394        * Sel-Operation war, die keine Methoden zurückgeben
 395        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 396        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 397        * werden! */
 398       exchange(call, new_Bad());
 399     } else {
 400       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 401     }
 402     DEL_ARR_F(arr);
 403     eset_destroy(methods);
 404   }
 405 }
 406
 407
 408 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 409  * und speichert das Ergebnis in der Call-Operation. (siehe
 410  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 411  * muss bereits aufgebaut sein. */
 412 static void callee_ana(void) {
 413   int i;
 414   /* Alle Graphen analysieren. */
 415   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 416     irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
 417   }
 418 }
 419
 420
 421
 422 /* --- free method analysis ------------------------------------------------- */
 423
 424
 425 static void free_mark(ir_node * node, eset * set);
 426
 427 static void free_mark_proj(ir_node * node, long n, eset * set) {
 428   assert(get_irn_mode(node) == mode_T);
 429   if (get_irn_link(node) == MARK) {
 430     /* already visited */
 431     return;
 432   }
 433   set_irn_link(node, MARK);
 434   switch (get_irn_opcode(node)) {
 435   case iro_Proj: {
 436     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 437      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 438      * wird. */
 439     ir_node * pred = get_Proj_pred(node);
 440     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 441       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 442     } else {
 443       /* nothing: da in "free_ana_walker" behandelt. */
 444     }
 445     break;
 446   }
 447
 448   case iro_Tuple:
 449     free_mark(get_Tuple_pred(node, n), set);
 450     break;
 451
 452   case iro_Id:
 453     free_mark_proj(get_Id_pred(node), n, set);
 454     break;
 455
 456   case iro_Start:
 457   case iro_Alloc:
 458   case iro_Load:
 459     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 460      * behandelt. */
 461     break;
 462
 463   default:
 464     assert(0 && "unexpected opcode or opcode not implemented");
 465     break;
 466   }
 467   set_irn_link(node, NULL);
 468 }
 469
 470
 471 static void free_mark(ir_node * node, eset * set) {
 472   int i;
 473   assert(get_irn_mode(node) == mode_p);
 474   if (get_irn_link(node) == MARK) {
 475     return; /* already visited */
 476   }
 477   set_irn_link(node, MARK);
 478   switch (get_irn_opcode(node)) {
 479   case iro_Sel: {
 480     entity * ent = get_Sel_entity(node);
 481     if (is_method_type(get_entity_type(ent))) {
 482       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 483         eset_insert(set, get_Sel_method(node, i));
 484       }
 485     }
 486     break;
 487   }
 488   case iro_SymConst:
 489     /* nothing: SymConst points to extern method */
 490     break;
 491   case iro_Const: {
 492     tarval * val = get_Const_tarval(node);
 493     entity * ent = val->u.p.ent;
 494     if (ent != NULL && is_method_type(get_entity_type(ent))) {
 495       eset_insert(set, ent);
 496     }
 497     break;
 498   }
 499   case iro_Phi:
 500     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 501       free_mark(get_Phi_pred(node, i), set);
 502     }
 503     break;
 504   case iro_Id:
 505     free_mark(get_Id_pred(node), set);
 506     break;
 507   case iro_Proj:
 508     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 509     break;
 510   default:
 511     /* nothing: Wird unten behandelt! */
 512     break;
 513   }
 514   set_irn_link(node, NULL);
 515 }
 516
 517
 518 static void free_ana_walker(ir_node * node, eset * set) {
 519   int i;
 520   if (get_irn_link(node) == MARK) {
 521     /* bereits in einem Zyklus besucht. */
 522     return;
 523   }
 524   switch (get_irn_opcode(node)) {
 525   /* special nodes */
 526   case iro_Sel:
 527   case iro_SymConst:
 528   case iro_Const:
 529   case iro_Phi:
 530   case iro_Id:
 531   case iro_Proj:
 532   case iro_Tuple:
 533     /* nothing */
 534     break;
 535   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 536    * Verräter ist. */
 537   case iro_Call:
 538     set_irn_link(node, MARK);
 539     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 540       ir_node * pred = get_Call_param(node, i);
 541       if (get_irn_mode(pred) == mode_p) {
 542         free_mark(pred, set);
 543       }
 544     }
 545     break;
 546   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 547    * jemand das Gegenteil implementiert. */
 548   default:
 549     set_irn_link(node, MARK);
 550     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 551       ir_node * pred = get_irn_n(node, i);
 552       if (get_irn_mode(pred) == mode_p) {
 553         free_mark(pred, set);
 554       }
 555     }
 556     break;
 557   }
 558   set_irn_link(node, NULL);
 559 }
 560
 561
 562 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 563  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 564  * SymConst-Operationen müssen in passende Const-Operationen
 565  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 566  * auf eine echt externe Methode.  */
 567 static entity ** get_free_methods(void) {
 568   eset * set = eset_create();
 569   int i;
 570   entity ** arr = NEW_ARR_F(entity *, 0);
 571   entity * ent;
 572   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 573     ir_graph * irg = get_irp_irg(i);
 574     entity * ent = get_irg_ent(irg);
 575     /* insert "external visible" methods. */
 576     if (get_entity_visibility(ent) != local) {
 577       eset_insert(set, ent);
 578     }
 579     irg_walk_graph(irg, NULL, (irg_walk_func) free_ana_walker, set);
 580   }
 581   /* Hauptprogramm ist auch frei, auch wenn es nicht "external
 582    * visible" ist. */
 583   eset_insert(set, get_irg_ent(get_irp_main_irg()));
 584   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 585     ARR_APP1(entity *, arr, ent);
 586   }
 587   eset_destroy(set);
 588
 589   return arr;
 590 }
 591
 592 void cgana(int *length, entity ***free_methods) {
 593   entity ** free_meths;
 594   int i;
 595
 596   sel_methods_init();
 597   free_meths = get_free_methods();
 598   callee_ana();
 599   sel_methods_dispose();
 600
 601   /* Convert the flexible array to an array that can be handled
 602      by standard C. */
 603   *length = ARR_LEN(free_meths);
 604   *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
 605   for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
 606   DEL_ARR_F(free_meths);
 607 }