1 /* -------------------------------------------------------------------
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.
8 * Erstellt: Hubert Schmid, 09.06.2002
9 * ---------------------------------------------------------------- */
25 #include "dbginfo_t.h"
27 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
28 * Darstellung der unbekannten Methode. */
29 static void * MARK = &MARK;
33 /* --- sel methods ---------------------------------------------------------- */
36 static eset * entities = NULL;
39 /* Bestimmt die eindeutige Methode, die die Methode für den
40 * übergebenene (dynamischen) Typ überschreibt. */
41 static entity * get_implementation(type * class, entity * method) {
43 if (get_entity_peculiarity(method) != description &&
44 get_entity_owner(method) == class) {
47 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
48 entity * e = get_entity_overwrittenby(method, i);
49 if (get_entity_peculiarity(e) != description && get_entity_owner(e) == class) {
53 for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
54 entity * e = get_implementation(get_class_supertype(class, i), method);
59 assert(0 && "implemenation not found");
62 /* Returns the entity that contains the implementation of the inherited
63 entity if available, else returns the entity passed. */
64 entity *get_inherited_methods_implementation(entity *inh_meth) {
65 entity *impl_meth = NULL;
66 ir_node *addr = get_atomic_ent_value(inh_meth);
67 assert(addr && "constant entity without value");
69 if (get_irn_op(addr) == op_Const) {
70 impl_meth = tarval_to_entity(get_Const_tarval(addr));
73 assert(!impl_meth || get_entity_peculiarity(impl_meth) == existent);
74 return impl_meth? impl_meth : inh_meth;
78 /* Collect the entity representing the implementation of this
79 entity (not the same if inherited) and all entities for overwriting
80 implementations in "set".
81 If the implementation of the method is not included in the
82 compilation unit "open" is set to true.
83 A recursive descend in the overwritten relation.
84 Cycle-free, therefore must terminate. */
85 void collect_impls(entity *method, eset *set, int *size, bool *open) {
87 if (get_entity_peculiarity(method) == existent) {
88 if (get_entity_visibility(method) == external_allocated) {
89 assert(get_entity_irg(method) == NULL);
92 assert(get_entity_irg(method) != NULL);
93 if (!eset_contains(set, method)) {
94 eset_insert(set, method);
99 if (get_entity_peculiarity(method) == inherited) {
100 entity *impl_ent = get_inherited_methods_implementation(method);
101 assert(impl_ent && "no implementation for inherited entity");
102 if (get_entity_visibility(impl_ent) == external_allocated) {
103 assert(get_entity_irg(impl_ent) == NULL);
106 assert(get_entity_irg(impl_ent) != NULL);
107 if (!eset_contains(set, impl_ent)) {
108 eset_insert(set, impl_ent);
113 /** recursive descend **/
114 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
115 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
119 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
120 * (und implementieren). In der zurückgegebenen Reihung kommt jede
121 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
122 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
123 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
124 * keine Methoden, die die "method" überschreiben, so gibt die Methode
126 static entity ** get_impl_methods(entity * method) {
127 eset * set = eset_create();
132 /** Collect all method entities that can be called here **/
133 collect_impls(method, set, &size, &open);
136 Vorgaenger einfuegen. **/
137 if (size == 0 && !open) {
138 /* keine implementierte überschriebene Methode */
142 arr = NEW_ARR_F(entity *, size + 1);
143 arr[0] = NULL; /* Represents open method */
144 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
148 arr = NEW_ARR_F(entity *, size);
149 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
157 /* debug makros used in sel_methods_walker */
158 #define SIZ(x) sizeof(x)/sizeof((x)[0])
160 #define DBG_OPT_NORMALIZE \
161 __dbg_info_merge_pair(new_node, node, dbg_const_eval)
162 #define DBG_OPT_POLY_ALLOC \
166 ons[1] = skip_Proj(get_Sel_ptr(node)); \
167 __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
169 #define DBG_OPT_POLY \
170 __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
173 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
174 if (get_irn_op(node) == op_SymConst) {
175 /* Wenn möglich SymConst-Operation durch Const-Operation
177 if (get_SymConst_kind(node) == linkage_ptr_info) {
178 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
179 if (entry != NULL) { /* Method is declared in the compiled code */
180 entity * ent = entry->value;
181 if (get_opt_normalize() && (get_entity_visibility(ent) != external_allocated)) { /* Meth. is defined */
183 assert(get_entity_irg(ent));
184 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
185 new_node = new_d_Const(get_irn_dbg_info(node),
186 mode_P, new_tarval_from_entity(ent, mode_P)); DBG_OPT_NORMALIZE;
187 exchange(node, new_node);
191 } else if (get_irn_op(node) == op_Sel &&
192 is_method_type(get_entity_type(get_Sel_entity(node)))) {
193 entity * ent = get_Sel_entity(node);
194 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
195 (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
197 /* We know which method will be called, no dispatch necessary. */
198 assert(get_entity_peculiarity(ent) != description);
199 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
200 /* @@@ Is this correct?? Alloc could reference a subtype of the owner
201 of Sel that overwrites the method referenced in Sel. */
202 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
203 exchange (node, new_node);
205 assert(get_entity_peculiarity(ent) != inherited);
206 if (!eset_contains(entities, ent)) {
207 /* Entity noch nicht behandelt. Alle (intern oder extern)
208 * implementierten Methoden suchen, die diese Entity
209 * überschreiben. Die Menge an entity.link speichern. */
210 set_entity_link(ent, get_impl_methods(ent));
211 eset_insert(entities, ent);
213 if (get_entity_link(ent) == NULL) {
214 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
215 * Methode zurückgeben. Damit ist sie insbesondere nicht
216 * ausführbar und nicht erreichbar. */
217 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
218 fuer die es keine Implementierung gibt. */
219 if (get_entity_peculiarity(ent) == description) {
220 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
221 printf("WARNING: Calling method description %s in method %s which has "
222 "no implementation!\n", id_to_str(get_entity_ident(ent)),
223 id_to_str(get_entity_ident(get_irg_ent(current_ir_graph))));
225 exchange(node, new_Bad());
228 entity ** arr = get_entity_link(ent);
232 printf("\nCall site "); DDMN(node);
233 printf(" in "); DDME(get_irg_ent(current_ir_graph));
234 printf(" can call:\n");
235 for (i = 0; i < ARR_LEN(arr); i++) {
236 printf(" - "); DDME(arr[i]);
237 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
242 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
243 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
245 /* Die Sel-Operation kann immer nur einen Wert auf eine
246 * interne Methode zurückgeben. Wir können daher die
247 * Sel-Operation durch eine Const- bzw. SymConst-Operation
249 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
250 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
251 exchange (node, new_node);
259 /* Datenstruktur initialisieren. Zusätzlich werden alle
260 * SymConst-Operationen, die auf interne Methoden verweisen, durch
261 * Const-Operationen ersetzt. */
262 static void sel_methods_init(void) {
264 pmap * ldname_map = pmap_create();
265 assert(entities == NULL);
266 entities = eset_create();
267 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
268 entity * ent = get_irg_ent(get_irp_irg(i));
269 /* Nur extern sichtbare Methode können überhaupt mit SymConst
270 * aufgerufen werden. */
271 if (get_entity_visibility(ent) != local) {
272 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
275 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
276 pmap_destroy(ldname_map);
279 /*****************************************************************************/
281 /* Datenstruktur freigeben. */
282 static void sel_methods_dispose(void) {
285 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
286 entity ** arr = get_entity_link(ent);
290 set_entity_link(ent, NULL);
292 eset_destroy(entities);
297 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
298 * zurückgegeben werden können. Die Liste enthält keine doppelten
300 static entity ** get_Sel_arr(ir_node * sel) {
301 static entity ** NULL_ARRAY = NULL;
304 assert(sel && get_irn_op(sel) == op_Sel);
305 ent = get_Sel_entity(sel);
306 assert(is_method_type(get_entity_type(ent))); /* what else? */
307 arr = get_entity_link(ent);
311 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
312 * kann für polymorphe (abstrakte) Methoden passieren. */
314 NULL_ARRAY = NEW_ARR_F(entity *, 0);
321 static int get_Sel_n_methods(ir_node * sel) {
322 return ARR_LEN(get_Sel_arr(sel));
326 static entity * get_Sel_method(ir_node * sel, int pos) {
327 entity ** arr = get_Sel_arr(sel);
328 assert(pos >= 0 && pos < ARR_LEN(arr));
334 /* --- callee analysis ------------------------------------------------------ */
337 static void callee_ana_node(ir_node * node, eset * methods);
340 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
341 assert(get_irn_mode(node) == mode_T);
342 if (get_irn_link(node) == MARK) {
343 /* already visited */
346 set_irn_link(node, MARK);
348 switch (get_irn_opcode(node)) {
350 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
351 * op_Tuple oder ein Knoten, der eine "freie Methode"
353 ir_node * pred = get_Proj_pred(node);
354 if (get_irn_link(pred) != MARK) {
355 if (get_irn_op(pred) == op_Tuple) {
356 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
358 eset_insert(methods, MARK); /* free method -> unknown */
365 callee_ana_node(get_Tuple_pred(node, n), methods);
369 callee_ana_proj(get_Id_pred(node), n, methods);
373 eset_insert(methods, MARK); /* free method -> unknown */
377 set_irn_link(node, NULL);
381 static void callee_ana_node(ir_node * node, eset * methods) {
384 assert((get_irn_mode(node) == mode_P) || is_Bad(node));
385 /* rekursion verhindern */
386 if (get_irn_link(node) == MARK) {
387 /* already visited */
390 set_irn_link(node, MARK);
392 switch (get_irn_opcode(node)) {
394 /* externe Methode (wegen fix_symconst!) */
395 eset_insert(methods, MARK); /* free method -> unknown */
399 /* interne Methode */
400 entity * ent = tarval_to_entity(get_Const_tarval(node));
401 assert(ent && is_method_type(get_entity_type(ent)));
402 if (get_entity_visibility(ent) != external_allocated) {
403 assert(get_entity_irg(ent));
404 eset_insert(methods, ent);
406 eset_insert(methods, MARK); /* free method -> unknown */
412 /* polymorphe Methode */
413 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
414 entity * ent = get_Sel_method(node, i);
416 eset_insert(methods, ent);
418 eset_insert(methods, MARK);
427 case iro_Phi: /* Vereinigung */
428 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
429 callee_ana_node(get_Phi_pred(node, i), methods);
434 callee_ana_node(get_Id_pred(node), methods);
438 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
445 eset_insert(methods, MARK); /* free method -> unknown */
449 assert(0 && "invalid opcode or opcode not implemented");
453 set_irn_link(node, NULL);
457 static void callee_walker(ir_node * call, void * env) {
458 if (get_irn_op(call) == op_Call) {
459 eset * methods = eset_create();
461 entity ** arr = NEW_ARR_F(entity *, 0);
462 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
463 if (eset_contains(methods, MARK)) { /* unknown method */
464 ARR_APP1(entity *, arr, NULL);
466 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
468 ARR_APP1(entity *, arr, ent);
471 if (ARR_LEN(arr) == 0) {
472 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
473 * Sel-Operation war, die keine Methoden zurückgeben
474 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
475 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
477 exchange(call, new_Bad());
479 set_Call_callee_arr(call, ARR_LEN(arr), arr);
482 eset_destroy(methods);
487 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
488 * und speichert das Ergebnis in der Call-Operation. (siehe
489 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
490 * muss bereits aufgebaut sein. */
491 static void callee_ana(void) {
493 /* Alle Graphen analysieren. */
494 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
495 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
501 /* --- free method analysis ------------------------------------------------- */
504 static void free_mark(ir_node * node, eset * set);
506 static void free_mark_proj(ir_node * node, long n, eset * set) {
507 assert(get_irn_mode(node) == mode_T);
508 if (get_irn_link(node) == MARK) {
509 /* already visited */
512 set_irn_link(node, MARK);
513 switch (get_irn_opcode(node)) {
515 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
516 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
518 ir_node * pred = get_Proj_pred(node);
519 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
520 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
522 /* nothing: da in "free_ana_walker" behandelt. */
528 free_mark(get_Tuple_pred(node, n), set);
532 free_mark_proj(get_Id_pred(node), n, set);
538 /* nothing: Die Operationen werden in "free_ana_walker" selbst
543 assert(0 && "unexpected opcode or opcode not implemented");
546 set_irn_link(node, NULL);
550 static void free_mark(ir_node * node, eset * set) {
552 assert(get_irn_mode(node) == mode_P);
553 if (get_irn_link(node) == MARK) {
554 return; /* already visited */
556 set_irn_link(node, MARK);
557 switch (get_irn_opcode(node)) {
559 entity * ent = get_Sel_entity(node);
560 if (is_method_type(get_entity_type(ent))) {
561 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
562 eset_insert(set, get_Sel_method(node, i));
568 /* nothing: SymConst points to extern method */
571 tarval * val = get_Const_tarval(node);
572 if (tarval_is_entity(val)) { /* filter null pointer */
573 entity * ent = tarval_to_entity(val);
574 if (is_method_type(get_entity_type(ent))) {
575 eset_insert(set, ent);
581 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
582 free_mark(get_Phi_pred(node, i), set);
586 free_mark(get_Id_pred(node), set);
589 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
592 /* nothing: Wird unten behandelt! */
595 set_irn_link(node, NULL);
599 static void free_ana_walker(ir_node * node, eset * set) {
601 if (get_irn_link(node) == MARK) {
602 /* bereits in einem Zyklus besucht. */
605 switch (get_irn_opcode(node)) {
616 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
619 set_irn_link(node, MARK);
620 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
621 ir_node * pred = get_Call_param(node, i);
622 if (get_irn_mode(pred) == mode_P) {
623 free_mark(pred, set);
627 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
628 * jemand das Gegenteil implementiert. */
630 set_irn_link(node, MARK);
631 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
632 ir_node * pred = get_irn_n(node, i);
633 if (get_irn_mode(pred) == mode_P) {
634 free_mark(pred, set);
639 set_irn_link(node, NULL);
643 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
644 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
645 * SymConst-Operationen müssen in passende Const-Operationen
646 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
647 * auf eine echt externe Methode. */
648 static entity ** get_free_methods(void) {
649 eset * set = eset_create();
651 entity ** arr = NEW_ARR_F(entity *, 0);
653 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
654 ir_graph * irg = get_irp_irg(i);
655 entity * ent = get_irg_ent(irg);
656 /* insert "external visible" methods. */
657 if (get_entity_visibility(ent) != local) {
658 eset_insert(set, ent);
660 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
662 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
664 if(get_irp_main_irg()) {
665 eset_insert(set, get_irg_ent(get_irp_main_irg()));
667 for (ent = eset_first(set); ent; ent = eset_next(set)) {
668 ARR_APP1(entity *, arr, ent);
675 void cgana(int *length, entity ***free_methods) {
676 entity ** free_meths;
680 free_meths = get_free_methods();
682 sel_methods_dispose();
684 /* Convert the flexible array to an array that can be handled
686 *length = ARR_LEN(free_meths);
687 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
688 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
689 DEL_ARR_F(free_meths);
692 /* Optimize the address expressions passed to call nodes.
693 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
694 * werden durch Const-Operationen ersetzt.
695 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
696 * durch Const ersetzt.
697 * Sel Knoten, fuer die keine Implementierung existiert, werden
698 * durch Bad ersetzt. */
699 void opt_call_addrs(void) {
701 sel_methods_dispose();
704 pmap * ldname_map = pmap_create();
705 assert(entities == NULL);
706 entities = eset_create();
707 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
708 entity * ent = get_irg_ent(get_irp_irg(i));
709 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
710 * aufgerufen werden. */
711 if (get_entity_visibility(ent) != local) {
712 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
715 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
716 pmap_destroy(ldname_map);