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 * ---------------------------------------------------------------- */
26 #include "dbginfo_t.h"
28 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
29 * Darstellung der unbekannten Methode. */
30 static void * MARK = &MARK;
34 /* --- sel methods ---------------------------------------------------------- */
37 static eset * entities = NULL;
40 /* Bestimmt die eindeutige Methode, die die Methode für den
41 * übergebenene (dynamischen) Typ überschreibt. */
42 static entity * get_implementation(type * class, entity * method) {
44 if (get_entity_peculiarity(method) != description &&
45 get_entity_owner(method) == class) {
48 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
49 entity * e = get_entity_overwrittenby(method, i);
50 if (get_entity_peculiarity(e) != description && get_entity_owner(e) == class) {
54 for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
55 entity * e = get_implementation(get_class_supertype(class, i), method);
60 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));
74 assert(!impl_meth || get_entity_peculiarity(impl_meth) == existent);
75 return impl_meth? impl_meth : inh_meth;
79 /* Collect the entity representing the implementation of this
80 entity (not the same if inherited) and all entities for overwriting
81 implementations in "set".
82 If the implementation of the method is not included in the
83 compilation unit "open" is set to true.
84 A recursive descend in the overwritten relation.
85 Cycle-free, therefore must terminate. */
86 void collect_impls(entity *method, eset *set, int *size, bool *open) {
88 if (get_entity_peculiarity(method) == existent) {
89 if (get_entity_visibility(method) == external_allocated) {
90 assert(get_entity_irg(method) == NULL);
93 assert(get_entity_irg(method) != NULL);
94 if (!eset_contains(set, method)) {
95 eset_insert(set, method);
100 if (get_entity_peculiarity(method) == inherited) {
101 entity *impl_ent = get_inherited_methods_implementation(method);
102 assert(impl_ent && "no implementation for inherited entity");
103 if (get_entity_visibility(impl_ent) == external_allocated) {
104 assert(get_entity_irg(impl_ent) == NULL);
107 assert(get_entity_irg(impl_ent) != NULL);
108 if (!eset_contains(set, impl_ent)) {
109 eset_insert(set, impl_ent);
114 /** recursive descend **/
115 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
116 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
120 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
121 * (und implementieren). In der zurückgegebenen Reihung kommt jede
122 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
123 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
124 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
125 * keine Methoden, die die "method" überschreiben, so gibt die Methode
127 static entity ** get_impl_methods(entity * method) {
128 eset * set = eset_create();
133 /** Collect all method entities that can be called here **/
134 collect_impls(method, set, &size, &open);
137 Vorgaenger einfuegen. **/
138 if (size == 0 && !open) {
139 /* keine implementierte überschriebene Methode */
143 arr = NEW_ARR_F(entity *, size + 1);
144 arr[0] = NULL; /* Represents open method */
145 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
149 arr = NEW_ARR_F(entity *, size);
150 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
158 /* debug makros used in sel_methods_walker */
159 #define SIZ(x) sizeof(x)/sizeof((x)[0])
161 #define DBG_OPT_NORMALIZE \
162 __dbg_info_merge_pair(new_node, node, dbg_const_eval)
163 #define DBG_OPT_POLY_ALLOC \
167 ons[1] = skip_Proj(get_Sel_ptr(node)); \
168 __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
170 #define DBG_OPT_POLY \
171 __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
174 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
175 if (get_irn_op(node) == op_SymConst) {
176 /* Wenn möglich SymConst-Operation durch Const-Operation
178 if (get_SymConst_kind(node) == linkage_ptr_info) {
179 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
180 if (entry != NULL) { /* Method is declared in the compiled code */
181 entity * ent = entry->value;
182 if (get_opt_normalize() && (get_entity_visibility(ent) != external_allocated)) { /* Meth. is defined */
184 assert(get_entity_irg(ent));
185 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
186 new_node = new_d_Const(get_irn_dbg_info(node),
187 mode_P, new_tarval_from_entity(ent, mode_P)); DBG_OPT_NORMALIZE;
188 exchange(node, new_node);
192 } else if (get_irn_op(node) == op_Sel &&
193 is_method_type(get_entity_type(get_Sel_entity(node)))) {
194 entity * ent = get_Sel_entity(node);
195 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
196 (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
198 /* We know which method will be called, no dispatch necessary. */
199 assert(get_entity_peculiarity(ent) != description);
200 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
201 /* @@@ Is this correct?? Alloc could reference a subtype of the owner
202 of Sel that overwrites the method referenced in Sel. */
203 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
204 exchange (node, new_node);
206 assert(get_entity_peculiarity(ent) != inherited);
207 if (!eset_contains(entities, ent)) {
208 /* Entity noch nicht behandelt. Alle (intern oder extern)
209 * implementierten Methoden suchen, die diese Entity
210 * überschreiben. Die Menge an entity.link speichern. */
211 set_entity_link(ent, get_impl_methods(ent));
212 eset_insert(entities, ent);
214 if (get_entity_link(ent) == NULL) {
215 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
216 * Methode zurückgeben. Damit ist sie insbesondere nicht
217 * ausführbar und nicht erreichbar. */
218 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
219 fuer die es keine Implementierung gibt. */
220 if (get_entity_peculiarity(ent) == description) {
221 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
222 printf("WARNING: Calling method description %s in method %s which has "
223 "no implementation!\n", id_to_str(get_entity_ident(ent)),
224 id_to_str(get_entity_ident(get_irg_ent(current_ir_graph))));
226 exchange(node, new_Bad());
229 entity ** arr = get_entity_link(ent);
233 printf("\nCall site "); DDMN(node);
234 printf(" in "); DDME(get_irg_ent(current_ir_graph));
235 printf(" can call:\n");
236 for (i = 0; i < ARR_LEN(arr); i++) {
237 printf(" - "); DDME(arr[i]);
238 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
243 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
244 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
246 /* Die Sel-Operation kann immer nur einen Wert auf eine
247 * interne Methode zurückgeben. Wir können daher die
248 * Sel-Operation durch eine Const- bzw. SymConst-Operation
250 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
251 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
252 exchange (node, new_node);
260 /* Datenstruktur initialisieren. Zusätzlich werden alle
261 * SymConst-Operationen, die auf interne Methoden verweisen, durch
262 * Const-Operationen ersetzt. */
263 static void sel_methods_init(void) {
265 pmap * ldname_map = pmap_create();
266 assert(entities == NULL);
267 entities = eset_create();
268 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
269 entity * ent = get_irg_ent(get_irp_irg(i));
270 /* Nur extern sichtbare Methode können überhaupt mit SymConst
271 * aufgerufen werden. */
272 if (get_entity_visibility(ent) != local) {
273 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
276 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
277 pmap_destroy(ldname_map);
280 /*****************************************************************************/
282 /* Datenstruktur freigeben. */
283 static void sel_methods_dispose(void) {
286 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
287 entity ** arr = get_entity_link(ent);
291 set_entity_link(ent, NULL);
293 eset_destroy(entities);
298 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
299 * zurückgegeben werden können. Die Liste enthält keine doppelten
301 static entity ** get_Sel_arr(ir_node * sel) {
302 static entity ** NULL_ARRAY = NULL;
305 assert(sel && get_irn_op(sel) == op_Sel);
306 ent = get_Sel_entity(sel);
307 assert(is_method_type(get_entity_type(ent))); /* what else? */
308 arr = get_entity_link(ent);
312 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
313 * kann für polymorphe (abstrakte) Methoden passieren. */
315 NULL_ARRAY = NEW_ARR_F(entity *, 0);
322 static int get_Sel_n_methods(ir_node * sel) {
323 return ARR_LEN(get_Sel_arr(sel));
327 static entity * get_Sel_method(ir_node * sel, int pos) {
328 entity ** arr = get_Sel_arr(sel);
329 assert(pos >= 0 && pos < ARR_LEN(arr));
335 /* --- callee analysis ------------------------------------------------------ */
338 static void callee_ana_node(ir_node * node, eset * methods);
341 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
342 assert(get_irn_mode(node) == mode_T);
343 if (get_irn_link(node) == MARK) {
344 /* already visited */
347 set_irn_link(node, MARK);
349 switch (get_irn_opcode(node)) {
351 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
352 * op_Tuple oder ein Knoten, der eine "freie Methode"
354 ir_node * pred = get_Proj_pred(node);
355 if (get_irn_link(pred) != MARK) {
356 if (get_irn_op(pred) == op_Tuple) {
357 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
359 eset_insert(methods, MARK); /* free method -> unknown */
366 callee_ana_node(get_Tuple_pred(node, n), methods);
370 callee_ana_proj(get_Id_pred(node), n, methods);
374 eset_insert(methods, MARK); /* free method -> unknown */
378 set_irn_link(node, NULL);
382 static void callee_ana_node(ir_node * node, eset * methods) {
385 assert((get_irn_mode(node) == mode_P) || is_Bad(node));
386 /* rekursion verhindern */
387 if (get_irn_link(node) == MARK) {
388 /* already visited */
391 set_irn_link(node, MARK);
393 switch (get_irn_opcode(node)) {
395 /* externe Methode (wegen fix_symconst!) */
396 eset_insert(methods, MARK); /* free method -> unknown */
400 /* interne Methode */
401 entity * ent = tarval_to_entity(get_Const_tarval(node));
402 assert(ent && is_method_type(get_entity_type(ent)));
403 if (get_entity_visibility(ent) != external_allocated) {
404 assert(get_entity_irg(ent));
405 eset_insert(methods, ent);
407 eset_insert(methods, MARK); /* free method -> unknown */
413 /* polymorphe Methode */
414 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
415 entity * ent = get_Sel_method(node, i);
417 eset_insert(methods, ent);
419 eset_insert(methods, MARK);
428 case iro_Phi: /* Vereinigung */
429 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
430 callee_ana_node(get_Phi_pred(node, i), methods);
435 callee_ana_node(get_Id_pred(node), methods);
439 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
446 eset_insert(methods, MARK); /* free method -> unknown */
450 assert(0 && "invalid opcode or opcode not implemented");
454 set_irn_link(node, NULL);
458 static void callee_walker(ir_node * call, void * env) {
459 if (get_irn_op(call) == op_Call) {
460 eset * methods = eset_create();
462 entity ** arr = NEW_ARR_F(entity *, 0);
463 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
464 if (eset_contains(methods, MARK)) { /* unknown method */
465 ARR_APP1(entity *, arr, NULL);
467 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
469 ARR_APP1(entity *, arr, ent);
472 if (ARR_LEN(arr) == 0) {
473 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
474 * Sel-Operation war, die keine Methoden zurückgeben
475 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
476 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
478 exchange(call, new_Bad());
480 set_Call_callee_arr(call, ARR_LEN(arr), arr);
483 eset_destroy(methods);
488 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
489 * und speichert das Ergebnis in der Call-Operation. (siehe
490 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
491 * muss bereits aufgebaut sein. */
492 static void callee_ana(void) {
494 /* Alle Graphen analysieren. */
495 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
496 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
502 /* --- free method analysis ------------------------------------------------- */
505 static void free_mark(ir_node * node, eset * set);
507 static void free_mark_proj(ir_node * node, long n, eset * set) {
508 assert(get_irn_mode(node) == mode_T);
509 if (get_irn_link(node) == MARK) {
510 /* already visited */
513 set_irn_link(node, MARK);
514 switch (get_irn_opcode(node)) {
516 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
517 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
519 ir_node * pred = get_Proj_pred(node);
520 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
521 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
523 /* nothing: da in "free_ana_walker" behandelt. */
529 free_mark(get_Tuple_pred(node, n), set);
533 free_mark_proj(get_Id_pred(node), n, set);
539 /* nothing: Die Operationen werden in "free_ana_walker" selbst
544 assert(0 && "unexpected opcode or opcode not implemented");
547 set_irn_link(node, NULL);
551 static void free_mark(ir_node * node, eset * set) {
553 assert(get_irn_mode(node) == mode_P);
554 if (get_irn_link(node) == MARK) {
555 return; /* already visited */
557 set_irn_link(node, MARK);
558 switch (get_irn_opcode(node)) {
560 entity * ent = get_Sel_entity(node);
561 if (is_method_type(get_entity_type(ent))) {
562 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
563 eset_insert(set, get_Sel_method(node, i));
569 /* nothing: SymConst points to extern method */
572 tarval * val = get_Const_tarval(node);
573 if (tarval_is_entity(val)) { /* filter null pointer */
574 entity * ent = tarval_to_entity(val);
575 if (is_method_type(get_entity_type(ent))) {
576 eset_insert(set, ent);
582 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
583 free_mark(get_Phi_pred(node, i), set);
587 free_mark(get_Id_pred(node), set);
590 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
593 /* nothing: Wird unten behandelt! */
596 set_irn_link(node, NULL);
600 static void free_ana_walker(ir_node * node, eset * set) {
602 if (get_irn_link(node) == MARK) {
603 /* bereits in einem Zyklus besucht. */
606 switch (get_irn_opcode(node)) {
617 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
620 set_irn_link(node, MARK);
621 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
622 ir_node * pred = get_Call_param(node, i);
623 if (get_irn_mode(pred) == mode_P) {
624 free_mark(pred, set);
628 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
629 * jemand das Gegenteil implementiert. */
631 set_irn_link(node, MARK);
632 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
633 ir_node * pred = get_irn_n(node, i);
634 if (get_irn_mode(pred) == mode_P) {
635 free_mark(pred, set);
640 set_irn_link(node, NULL);
644 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
645 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
646 * SymConst-Operationen müssen in passende Const-Operationen
647 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
648 * auf eine echt externe Methode. */
649 static entity ** get_free_methods(void) {
650 eset * set = eset_create();
652 entity ** arr = NEW_ARR_F(entity *, 0);
654 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
655 ir_graph * irg = get_irp_irg(i);
656 entity * ent = get_irg_ent(irg);
657 /* insert "external visible" methods. */
658 if (get_entity_visibility(ent) != local) {
659 eset_insert(set, ent);
661 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
663 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
665 if(get_irp_main_irg()) {
666 eset_insert(set, get_irg_ent(get_irp_main_irg()));
668 for (ent = eset_first(set); ent; ent = eset_next(set)) {
669 ARR_APP1(entity *, arr, ent);
676 void cgana(int *length, entity ***free_methods) {
677 entity ** free_meths;
681 free_meths = get_free_methods();
683 sel_methods_dispose();
685 /* Convert the flexible array to an array that can be handled
687 *length = ARR_LEN(free_meths);
688 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
689 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
690 DEL_ARR_F(free_meths);
693 /* Optimize the address expressions passed to call nodes.
694 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
695 * werden durch Const-Operationen ersetzt.
696 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
697 * durch Const ersetzt.
698 * Sel Knoten, fuer die keine Implementierung existiert, werden
699 * durch Bad ersetzt. */
700 void opt_call_addrs(void) {
702 sel_methods_dispose();
705 pmap * ldname_map = pmap_create();
706 assert(entities == NULL);
707 entities = eset_create();
708 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
709 entity * ent = get_irg_ent(get_irp_irg(i));
710 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
711 * aufgerufen werden. */
712 if (get_entity_visibility(ent) != local) {
713 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
716 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
717 pmap_destroy(ldname_map);