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");
63 /* Returns the entity that contains the implementation of the inherited
64 entity if available, else returns the entity passed. */
65 entity *get_inherited_methods_implementation(entity *inh_meth) {
66 entity *impl_meth = NULL;
67 ir_node *addr = get_atomic_ent_value(inh_meth);
68 assert(addr && "constant entity without value");
70 if (get_irn_op(addr) == op_Const) {
71 impl_meth = tarval_to_entity(get_Const_tarval(addr));
73 assert(0 && "Complex constant values not supported -- adress of method should be straight constant!");
75 if (impl_meth && (get_entity_peculiarity(impl_meth) != existent)) {
76 printf("this_meth: "); DDMEO(inh_meth);
77 printf("impl meth: "); DDMEO(impl_meth);
78 assert(!impl_meth || get_entity_peculiarity(impl_meth) == existent);
80 return impl_meth? impl_meth : inh_meth;
84 /* Collect the entity representing the implementation of this
85 entity (not the same if inherited) and all entities for overwriting
86 implementations in "set".
87 If the implementation of the method is not included in the
88 compilation unit "open" is set to true.
89 A recursive descend in the overwritten relation.
90 Cycle-free, therefore must terminate. */
91 void collect_impls(entity *method, eset *set, int *size, bool *open) {
93 if (get_entity_peculiarity(method) == existent) {
94 if (get_entity_visibility(method) == external_allocated) {
95 assert(get_entity_irg(method) == NULL);
98 assert(get_entity_irg(method) != NULL);
99 if (!eset_contains(set, method)) {
100 eset_insert(set, method);
105 if (get_entity_peculiarity(method) == inherited) {
106 entity *impl_ent = get_inherited_methods_implementation(method);
107 assert(impl_ent && "no implementation for inherited entity");
108 if (get_entity_visibility(impl_ent) == external_allocated) {
109 assert(get_entity_irg(impl_ent) == NULL);
112 assert(get_entity_irg(impl_ent) != NULL);
113 if (!eset_contains(set, impl_ent)) {
114 eset_insert(set, impl_ent);
119 /** recursive descend **/
120 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
121 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
125 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
126 * (und implementieren). In der zurückgegebenen Reihung kommt jede
127 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
128 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
129 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
130 * keine Methoden, die die "method" überschreiben, so gibt die Methode
132 static entity ** get_impl_methods(entity * method) {
133 eset * set = eset_create();
138 /** Collect all method entities that can be called here **/
139 collect_impls(method, set, &size, &open);
142 Vorgaenger einfuegen. **/
143 if (size == 0 && !open) {
144 /* keine implementierte überschriebene Methode */
148 arr = NEW_ARR_F(entity *, size + 1);
149 arr[0] = NULL; /* Represents open method */
150 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
154 arr = NEW_ARR_F(entity *, size);
155 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
163 /* debug makros used in sel_methods_walker */
164 #define SIZ(x) sizeof(x)/sizeof((x)[0])
166 #define DBG_OPT_NORMALIZE \
167 __dbg_info_merge_pair(new_node, node, dbg_const_eval)
168 #define DBG_OPT_POLY_ALLOC \
172 ons[1] = skip_Proj(get_Sel_ptr(node)); \
173 __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
175 #define DBG_OPT_POLY \
176 __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
179 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
180 if (get_irn_op(node) == op_SymConst) {
181 /* Wenn möglich SymConst-Operation durch Const-Operation
183 if (get_SymConst_kind(node) == linkage_ptr_info) {
184 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
185 if (entry != NULL) { /* Method is declared in the compiled code */
186 entity * ent = entry->value;
187 if (get_opt_normalize() && (get_entity_visibility(ent) != external_allocated)) { /* Meth. is defined */
189 assert(get_entity_irg(ent));
190 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
191 new_node = new_d_Const(get_irn_dbg_info(node),
192 mode_P_mach, new_tarval_from_entity(ent, mode_P_mach)); DBG_OPT_NORMALIZE;
193 exchange(node, new_node);
197 } else if (get_irn_op(node) == op_Sel &&
198 is_method_type(get_entity_type(get_Sel_entity(node)))) {
199 entity * ent = get_Sel_entity(node);
200 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
201 (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
203 /* We know which method will be called, no dispatch necessary. */
204 assert(get_entity_peculiarity(ent) != description);
205 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
206 /* @@@ Is this correct?? Alloc could reference a subtype of the owner
207 of Sel that overwrites the method referenced in Sel. */
208 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
209 exchange (node, new_node);
211 assert(get_entity_peculiarity(ent) != inherited);
212 if (!eset_contains(entities, ent)) {
213 /* Entity noch nicht behandelt. Alle (intern oder extern)
214 * implementierten Methoden suchen, die diese Entity
215 * überschreiben. Die Menge an entity.link speichern. */
216 set_entity_link(ent, get_impl_methods(ent));
217 eset_insert(entities, ent);
219 if (get_entity_link(ent) == NULL) {
220 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
221 * Methode zurückgeben. Damit ist sie insbesondere nicht
222 * ausführbar und nicht erreichbar. */
223 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
224 fuer die es keine Implementierung gibt. */
225 if (get_entity_peculiarity(ent) == description) {
226 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
227 printf("WARNING: Calling method description %s in method %s which has "
228 "no implementation!\n", id_to_str(get_entity_ident(ent)),
229 id_to_str(get_entity_ident(get_irg_ent(current_ir_graph))));
231 exchange(node, new_Bad());
234 entity ** arr = get_entity_link(ent);
238 printf("\nCall site "); DDMN(node);
239 printf(" in "); DDME(get_irg_ent(current_ir_graph));
240 printf(" can call:\n");
241 for (i = 0; i < ARR_LEN(arr); i++) {
242 printf(" - "); DDME(arr[i]);
243 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
248 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
249 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
251 /* Die Sel-Operation kann immer nur einen Wert auf eine
252 * interne Methode zurückgeben. Wir können daher die
253 * Sel-Operation durch eine Const- bzw. SymConst-Operation
255 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
256 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
257 exchange (node, new_node);
265 /* Datenstruktur initialisieren. Zusätzlich werden alle
266 * SymConst-Operationen, die auf interne Methoden verweisen, durch
267 * Const-Operationen ersetzt. */
268 static void sel_methods_init(void) {
270 pmap * ldname_map = pmap_create();
271 assert(entities == NULL);
272 entities = eset_create();
273 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
274 entity * ent = get_irg_ent(get_irp_irg(i));
275 /* Nur extern sichtbare Methode können überhaupt mit SymConst
276 * aufgerufen werden. */
277 if (get_entity_visibility(ent) != local) {
278 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
281 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
282 pmap_destroy(ldname_map);
285 /*****************************************************************************/
287 /* Datenstruktur freigeben. */
288 static void sel_methods_dispose(void) {
291 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
292 entity ** arr = get_entity_link(ent);
296 set_entity_link(ent, NULL);
298 eset_destroy(entities);
303 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
304 * zurückgegeben werden können. Die Liste enthält keine doppelten
306 static entity ** get_Sel_arr(ir_node * sel) {
307 static entity ** NULL_ARRAY = NULL;
310 assert(sel && get_irn_op(sel) == op_Sel);
311 ent = get_Sel_entity(sel);
312 assert(is_method_type(get_entity_type(ent))); /* what else? */
313 arr = get_entity_link(ent);
317 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
318 * kann für polymorphe (abstrakte) Methoden passieren. */
320 NULL_ARRAY = NEW_ARR_F(entity *, 0);
327 static int get_Sel_n_methods(ir_node * sel) {
328 return ARR_LEN(get_Sel_arr(sel));
332 static entity * get_Sel_method(ir_node * sel, int pos) {
333 entity ** arr = get_Sel_arr(sel);
334 assert(pos >= 0 && pos < ARR_LEN(arr));
340 /* --- callee analysis ------------------------------------------------------ */
343 static void callee_ana_node(ir_node * node, eset * methods);
346 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
347 assert(get_irn_mode(node) == mode_T);
348 if (get_irn_link(node) == MARK) {
349 /* already visited */
352 set_irn_link(node, MARK);
354 switch (get_irn_opcode(node)) {
356 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
357 * op_Tuple oder ein Knoten, der eine "freie Methode"
359 ir_node * pred = get_Proj_pred(node);
360 if (get_irn_link(pred) != MARK) {
361 if (get_irn_op(pred) == op_Tuple) {
362 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
364 eset_insert(methods, MARK); /* free method -> unknown */
371 callee_ana_node(get_Tuple_pred(node, n), methods);
375 callee_ana_proj(get_Id_pred(node), n, methods);
379 eset_insert(methods, MARK); /* free method -> unknown */
383 set_irn_link(node, NULL);
387 static void callee_ana_node(ir_node * node, eset * methods) {
390 assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
391 /* rekursion verhindern */
392 if (get_irn_link(node) == MARK) {
393 /* already visited */
396 set_irn_link(node, MARK);
398 switch (get_irn_opcode(node)) {
400 /* externe Methode (wegen fix_symconst!) */
401 eset_insert(methods, MARK); /* free method -> unknown */
405 /* interne Methode */
406 entity * ent = tarval_to_entity(get_Const_tarval(node));
407 assert(ent && is_method_type(get_entity_type(ent)));
408 if (get_entity_visibility(ent) != external_allocated) {
409 assert(get_entity_irg(ent));
410 eset_insert(methods, ent);
412 eset_insert(methods, MARK); /* free method -> unknown */
418 /* polymorphe Methode */
419 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
420 entity * ent = get_Sel_method(node, i);
422 eset_insert(methods, ent);
424 eset_insert(methods, MARK);
433 case iro_Phi: /* Vereinigung */
434 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
435 callee_ana_node(get_Phi_pred(node, i), methods);
440 callee_ana_node(get_Id_pred(node), methods);
444 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
451 eset_insert(methods, MARK); /* free method -> unknown */
455 assert(0 && "invalid opcode or opcode not implemented");
459 set_irn_link(node, NULL);
463 static void callee_walker(ir_node * call, void * env) {
464 if (get_irn_op(call) == op_Call) {
465 eset * methods = eset_create();
467 entity ** arr = NEW_ARR_F(entity *, 0);
468 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
469 if (eset_contains(methods, MARK)) { /* unknown method */
470 ARR_APP1(entity *, arr, NULL);
472 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
474 ARR_APP1(entity *, arr, ent);
477 if (ARR_LEN(arr) == 0) {
478 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
479 * Sel-Operation war, die keine Methoden zurückgeben
480 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
481 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
483 exchange(call, new_Bad());
485 set_Call_callee_arr(call, ARR_LEN(arr), arr);
488 eset_destroy(methods);
493 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
494 * und speichert das Ergebnis in der Call-Operation. (siehe
495 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
496 * muss bereits aufgebaut sein. */
497 static void callee_ana(void) {
499 /* Alle Graphen analysieren. */
500 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
501 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
507 /* --- free method analysis ------------------------------------------------- */
510 static void free_mark(ir_node * node, eset * set);
512 static void free_mark_proj(ir_node * node, long n, eset * set) {
513 assert(get_irn_mode(node) == mode_T);
514 if (get_irn_link(node) == MARK) {
515 /* already visited */
518 set_irn_link(node, MARK);
519 switch (get_irn_opcode(node)) {
521 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
522 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
524 ir_node * pred = get_Proj_pred(node);
525 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
526 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
528 /* nothing: da in "free_ana_walker" behandelt. */
534 free_mark(get_Tuple_pred(node, n), set);
538 free_mark_proj(get_Id_pred(node), n, set);
544 /* nothing: Die Operationen werden in "free_ana_walker" selbst
549 assert(0 && "unexpected opcode or opcode not implemented");
552 set_irn_link(node, NULL);
556 static void free_mark(ir_node * node, eset * set) {
558 assert(mode_is_reference(get_irn_mode(node)));
559 if (get_irn_link(node) == MARK) {
560 return; /* already visited */
562 set_irn_link(node, MARK);
563 switch (get_irn_opcode(node)) {
565 entity * ent = get_Sel_entity(node);
566 if (is_method_type(get_entity_type(ent))) {
567 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
568 eset_insert(set, get_Sel_method(node, i));
574 /* nothing: SymConst points to extern method */
577 tarval * val = get_Const_tarval(node);
578 if (tarval_is_entity(val)) { /* filter null pointer */
579 entity * ent = tarval_to_entity(val);
580 if (is_method_type(get_entity_type(ent))) {
581 eset_insert(set, ent);
587 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
588 free_mark(get_Phi_pred(node, i), set);
592 free_mark(get_Id_pred(node), set);
595 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
598 /* nothing: Wird unten behandelt! */
601 set_irn_link(node, NULL);
605 static void free_ana_walker(ir_node * node, eset * set) {
607 if (get_irn_link(node) == MARK) {
608 /* bereits in einem Zyklus besucht. */
611 switch (get_irn_opcode(node)) {
622 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
625 set_irn_link(node, MARK);
626 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
627 ir_node * pred = get_Call_param(node, i);
628 if (mode_is_reference(get_irn_mode(pred))) {
629 free_mark(pred, set);
633 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
634 * jemand das Gegenteil implementiert. */
636 set_irn_link(node, MARK);
637 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
638 ir_node * pred = get_irn_n(node, i);
639 if (mode_is_reference(get_irn_mode(pred))) {
640 free_mark(pred, set);
645 set_irn_link(node, NULL);
649 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
650 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
651 * SymConst-Operationen müssen in passende Const-Operationen
652 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
653 * auf eine echt externe Methode. */
654 static entity ** get_free_methods(void) {
655 eset * set = eset_create();
657 entity ** arr = NEW_ARR_F(entity *, 0);
659 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
660 ir_graph * irg = get_irp_irg(i);
661 entity * ent = get_irg_ent(irg);
662 /* insert "external visible" methods. */
663 if (get_entity_visibility(ent) != local) {
664 eset_insert(set, ent);
666 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
668 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
670 if(get_irp_main_irg()) {
671 eset_insert(set, get_irg_ent(get_irp_main_irg()));
673 for (ent = eset_first(set); ent; ent = eset_next(set)) {
674 ARR_APP1(entity *, arr, ent);
681 void cgana(int *length, entity ***free_methods) {
682 entity ** free_meths;
686 free_meths = get_free_methods();
688 sel_methods_dispose();
690 /* Convert the flexible array to an array that can be handled
692 *length = ARR_LEN(free_meths);
693 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
694 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
695 DEL_ARR_F(free_meths);
698 /* Optimize the address expressions passed to call nodes.
699 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
700 * werden durch Const-Operationen ersetzt.
701 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
702 * durch Const ersetzt.
703 * Sel Knoten, fuer die keine Implementierung existiert, werden
704 * durch Bad ersetzt. */
705 void opt_call_addrs(void) {
707 sel_methods_dispose();
710 pmap * ldname_map = pmap_create();
711 assert(entities == NULL);
712 entities = eset_create();
713 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
714 entity * ent = get_irg_ent(get_irp_irg(i));
715 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
716 * aufgerufen werden. */
717 if (get_entity_visibility(ent) != local) {
718 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
721 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
722 pmap_destroy(ldname_map);