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         exchange(node, new_Bad());
 152       } else {
 153         entity ** arr = get_entity_link(ent);
 154         if (ARR_LEN(arr) == 1 && arr[0] != NULL) {
 155           /* Die Sel-Operation kann immer nur einen Wert auf eine
 156            * interne Methode zurückgeben. Wir können daher die
 157            * Sel-Operation durch eine Const- bzw. SymConst-Operation
 158            * ersetzen. */
 159           if (get_entity_visibility(arr[0]) == external_allocated) {
 160             exchange(node, new_SymConst((type_or_id_p) get_entity_ld_ident(arr[0]), linkage_ptr_info));
 161           } else {
 162             exchange(node, new_Const(mode_p, tarval_p_from_entity(arr[0])));
 163           }
 164         }
 165       }
 166     }
 167   }
 168 }
 169
 170
 171 /* Datenstruktur initialisieren. Zusätzlich werden alle
 172  * SymConst-Operationen, die auf interne Methode verweisen, durch
 173  * Const-Operationen ersetzt. */
 174 static void sel_methods_init(void) {
 175   int i;
 176   pmap * ldname_map = pmap_create();
 177   assert(entities == NULL);
 178   entities = eset_create();
 179   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 180     entity * ent = get_irg_ent(get_irp_irg(i));
 181     /* Nur extern sichtbare Methode können überhaupt mit SymConst
 182      * aufgerufen werden. */
 183     if (get_entity_visibility(ent) != local) {
 184       pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
 185     }
 186   }
 187   all_irg_walk((irg_walk_func) sel_methods_walker, NULL, ldname_map);
 188   pmap_destroy(ldname_map);
 189 }
 190
 191
 192 /* Datenstruktur freigeben. */
 193 static void sel_methods_dispose(void) {
 194   entity * ent;
 195   assert(entities);
 196   for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
 197     entity ** arr = get_entity_link(ent);
 198     if (arr) {
 199       DEL_ARR_F(arr);
 200     }
 201     set_entity_link(ent, NULL);
 202   }
 203   eset_destroy(entities);
 204   entities = NULL;
 205 }
 206
 207
 208 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
 209  * zurückgegeben werden können. Die Liste enthält keine doppelten
 210  * Einträge. */
 211 static entity ** get_Sel_arr(ir_node * sel) {
 212   static entity ** NULL_ARRAY = NULL;
 213   entity * ent;
 214   entity ** arr;
 215   assert(sel && get_irn_op(sel) == op_Sel);
 216   ent = get_Sel_entity(sel);
 217   assert(is_method_type(get_entity_type(ent))); /* what else? */
 218   arr = get_entity_link(ent);
 219   if (arr) {
 220     return arr;
 221   } else {
 222     /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
 223      * kann für polymorphe (abstrakte) Methoden passieren. */
 224     if (!NULL_ARRAY) {
 225       NULL_ARRAY = NEW_ARR_F(entity *, 0);
 226     }
 227     return NULL_ARRAY;
 228   }
 229 }
 230
 231
 232 static int get_Sel_n_methods(ir_node * sel) {
 233   return ARR_LEN(get_Sel_arr(sel));
 234 }
 235
 236
 237 static entity * get_Sel_method(ir_node * sel, int pos) {
 238   entity ** arr = get_Sel_arr(sel);
 239   assert(pos >= 0 && pos < ARR_LEN(arr));
 240   return arr[pos];
 241 }
 242
 243
 244
 245 /* --- callee analysis ------------------------------------------------------ */
 246
 247
 248 static void callee_ana_node(ir_node * node, eset * methods);
 249
 250
 251 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
 252   assert(get_irn_mode(node) == mode_T);
 253   if (get_irn_link(node) == MARK) {
 254     /* already visited */
 255     return;
 256   }
 257   set_irn_link(node, MARK);
 258
 259   switch (get_irn_opcode(node)) {
 260   case iro_Proj: {
 261     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 262      * op_Tuple oder ein Knoten, der eine "freie Methode"
 263      * zurückgibt. */
 264     ir_node * pred = get_Proj_pred(node);
 265     if (get_irn_link(pred) != MARK) {
 266       if (get_irn_op(pred) == op_Tuple) {
 267         callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
 268       } else {
 269         eset_insert(methods, MARK); /* free method -> unknown */
 270       }
 271     }
 272     break;
 273   }
 274
 275   case iro_Tuple:
 276     callee_ana_node(get_Tuple_pred(node, n), methods);
 277     break;
 278
 279   case iro_Id:
 280     callee_ana_proj(get_Id_pred(node), n, methods);
 281     break;
 282
 283   default:
 284     eset_insert(methods, MARK); /* free method -> unknown */
 285     break;
 286   }
 287
 288   set_irn_link(node, NULL);
 289 }
 290
 291
 292 static void callee_ana_node(ir_node * node, eset * methods) {
 293   int i;
 294
 295   assert(get_irn_mode(node) == mode_p);
 296   /* rekursion verhindern */
 297   if (get_irn_link(node) == MARK) {
 298     /* already visited */
 299     return;
 300   }
 301   set_irn_link(node, MARK);
 302
 303   switch (get_irn_opcode(node)) {
 304   case iro_SymConst:
 305     /* externe Methode (wegen fix_symconst!) */
 306     eset_insert(methods, MARK); /* free method -> unknown */
 307     break;
 308
 309   case iro_Const: {
 310     /* interne Methode */
 311     entity * ent = get_Const_tarval(node)->u.p.ent;
 312     assert(ent && is_method_type(get_entity_type(ent)));
 313     if (get_entity_visibility(ent) != external_allocated) {
 314       assert(get_entity_irg(ent));
 315       eset_insert(methods, ent);
 316     } else {
 317       eset_insert(methods, MARK); /* free method -> unknown */
 318     }
 319     break;
 320   }
 321
 322   case iro_Sel:
 323     /* polymorphe Methode */
 324     for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 325       entity * ent = get_Sel_method(node, i);
 326       if (ent) {
 327         eset_insert(methods, ent);
 328       } else {
 329         eset_insert(methods, MARK);
 330       }
 331     }
 332     break;
 333
 334   case iro_Bad:
 335     /* nothing */
 336     break;
 337
 338   case iro_Phi: /* Vereinigung */
 339     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 340       callee_ana_node(get_Phi_pred(node, i), methods);
 341     }
 342     break;
 343
 344   case iro_Id:
 345     callee_ana_node(get_Id_pred(node), methods);
 346     break;
 347
 348   case iro_Proj:
 349     callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
 350     break;
 351
 352   case iro_Add:
 353   case iro_Sub:
 354   case iro_Conv:
 355     /* extern */
 356     eset_insert(methods, MARK); /* free method -> unknown */
 357     break;
 358
 359   default:
 360     assert(0 && "invalid opcode or opcode not implemented");
 361     break;
 362   }
 363
 364   set_irn_link(node, NULL);
 365 }
 366
 367
 368 static void callee_walker(ir_node * call, void * env) {
 369   if (get_irn_op(call) == op_Call) {
 370     eset * methods = eset_create();
 371     entity * ent;
 372     entity ** arr = NEW_ARR_F(entity *, 0);
 373     callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
 374     if (eset_contains(methods, MARK)) { /* unknown method */
 375       ARR_APP1(entity *, arr, NULL);
 376     }
 377     for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
 378       if (ent != MARK) {
 379         ARR_APP1(entity *, arr, ent);
 380       }
 381     }
 382     if (ARR_LEN(arr) == 0) {
 383       /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
 384        * Sel-Operation war, die keine Methoden zurückgeben
 385        * konnte. Wir ersetzen die Call-Operation ebenfalls durch
 386        * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
 387        * werden! */
 388       exchange(call, new_Bad());
 389     } else {
 390       set_Call_callee_arr(call, ARR_LEN(arr), arr);
 391     }
 392     DEL_ARR_F(arr);
 393     eset_destroy(methods);
 394   }
 395 }
 396
 397
 398 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 399  * und speichert das Ergebnis in der Call-Operation. (siehe
 400  * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 401  * muss bereits aufgebaut sein. */
 402 static void callee_ana(void) {
 403   int i;
 404   /* Alle Graphen analysieren. */
 405   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 406     irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
 407   }
 408 }
 409
 410
 411
 412 /* --- free method analysis ------------------------------------------------- */
 413
 414
 415 static void free_mark(ir_node * node, eset * set);
 416
 417 static void free_mark_proj(ir_node * node, long n, eset * set) {
 418   assert(get_irn_mode(node) == mode_T);
 419   if (get_irn_link(node) == MARK) {
 420     /* already visited */
 421     return;
 422   }
 423   set_irn_link(node, MARK);
 424   switch (get_irn_opcode(node)) {
 425   case iro_Proj: {
 426     /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
 427      * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
 428      * wird. */
 429     ir_node * pred = get_Proj_pred(node);
 430     if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
 431       free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
 432     } else {
 433       /* nothing: da in "free_ana_walker" behandelt. */
 434     }
 435     break;
 436   }
 437
 438   case iro_Tuple:
 439     free_mark(get_Tuple_pred(node, n), set);
 440     break;
 441
 442   case iro_Id:
 443     free_mark_proj(get_Id_pred(node), n, set);
 444     break;
 445
 446   case iro_Start:
 447   case iro_Alloc:
 448   case iro_Load:
 449     /* nothing: Die Operationen werden in "free_ana_walker" selbst
 450      * behandelt. */
 451     break;
 452
 453   default:
 454     assert(0 && "unexpected opcode or opcode not implemented");
 455     break;
 456   }
 457   set_irn_link(node, NULL);
 458 }
 459
 460
 461 static void free_mark(ir_node * node, eset * set) {
 462   int i;
 463   assert(get_irn_mode(node) == mode_p);
 464   if (get_irn_link(node) == MARK) {
 465     return; /* already visited */
 466   }
 467   set_irn_link(node, MARK);
 468   switch (get_irn_opcode(node)) {
 469   case iro_Sel: {
 470     entity * ent = get_Sel_entity(node);
 471     if (is_method_type(get_entity_type(ent))) {
 472       for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
 473         eset_insert(set, get_Sel_method(node, i));
 474       }
 475     }
 476     break;
 477   }
 478   case iro_SymConst:
 479     /* nothing: SymConst points to extern method */
 480     break;
 481   case iro_Const: {
 482     tarval * val = get_Const_tarval(node);
 483     entity * ent = val->u.p.ent;
 484     if (ent != NULL && is_method_type(get_entity_type(ent))) {
 485       eset_insert(set, ent);
 486     }
 487     break;
 488   }
 489   case iro_Phi:
 490     for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
 491       free_mark(get_Phi_pred(node, i), set);
 492     }
 493     break;
 494   case iro_Id:
 495     free_mark(get_Id_pred(node), set);
 496     break;
 497   case iro_Proj:
 498     free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
 499     break;
 500   default:
 501     /* nothing: Wird unten behandelt! */
 502     break;
 503   }
 504   set_irn_link(node, NULL);
 505 }
 506
 507
 508 static void free_ana_walker(ir_node * node, eset * set) {
 509   int i;
 510   if (get_irn_link(node) == MARK) {
 511     /* bereits in einem Zyklus besucht. */
 512     return;
 513   }
 514   switch (get_irn_opcode(node)) {
 515   /* special nodes */
 516   case iro_Sel:
 517   case iro_SymConst:
 518   case iro_Const:
 519   case iro_Phi:
 520   case iro_Id:
 521   case iro_Proj:
 522   case iro_Tuple:
 523     /* nothing */
 524     break;
 525   /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
 526    * Verräter ist. */
 527   case iro_Call:
 528     set_irn_link(node, MARK);
 529     for (i = get_Call_arity(node) - 1; i >= 0; --i) {
 530       ir_node * pred = get_Call_param(node, i);
 531       if (get_irn_mode(pred) == mode_p) {
 532         free_mark(pred, set);
 533       }
 534     }
 535     break;
 536   /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
 537    * jemand das Gegenteil implementiert. */
 538   default:
 539     set_irn_link(node, MARK);
 540     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 541       ir_node * pred = get_irn_n(node, i);
 542       if (get_irn_mode(pred) == mode_p) {
 543         free_mark(pred, set);
 544       }
 545     }
 546     break;
 547   }
 548   set_irn_link(node, NULL);
 549 }
 550
 551
 552 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
 553  * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 554  * SymConst-Operationen müssen in passende Const-Operationen
 555  * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 556  * auf eine echt externe Methode.  */
 557 static entity ** get_free_methods(void) {
 558   eset * set = eset_create();
 559   int i;
 560   entity ** arr = NEW_ARR_F(entity *, 0);
 561   entity * ent;
 562   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 563     ir_graph * irg = get_irp_irg(i);
 564     entity * ent = get_irg_ent(irg);
 565     /* insert "external visible" methods. */
 566     if (get_entity_visibility(ent) != local) {
 567       eset_insert(set, ent);
 568     }
 569     irg_walk_graph(irg, NULL, (irg_walk_func) free_ana_walker, set);
 570   }
 571   /* Hauptprogramm ist auch frei, auch wenn es nicht "external
 572    * visible" ist. */
 573   eset_insert(set, get_irg_ent(get_irp_main_irg()));
 574   for (ent = eset_first(set); ent; ent = eset_next(set)) {
 575     ARR_APP1(entity *, arr, ent);
 576   }
 577   eset_destroy(set);
 578
 579   return arr;
 580 }
 581
 582 void cgana(int *length, entity ***free_methods) {
 583   entity ** free_meths;
 584   int i;
 585
 586   sel_methods_init();
 587   free_meths = get_free_methods();
 588   callee_ana();
 589   sel_methods_dispose();
 590
 591   /* Convert the flexible array to an array that can be handled
 592      by standard C. */
 593   *length = ARR_LEN(free_meths);
 594   *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
 595   for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
 596   DEL_ARR_F(free_meths);
 597 }