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 = get_tv_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, tarval_P_from_entity(ent)); 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 xprintf("WARNING: Calling method description %I in method %I which has "
223 "no implementation!\n", get_entity_ident(ent),
224 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 = get_Const_tarval(node)->u.P.ent;
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 entity * ent = val->u.P.ent;
574 if (ent != NULL && is_method_type(get_entity_type(ent))) {
575 eset_insert(set, ent);
580 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
581 free_mark(get_Phi_pred(node, i), set);
585 free_mark(get_Id_pred(node), set);
588 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
591 /* nothing: Wird unten behandelt! */
594 set_irn_link(node, NULL);
598 static void free_ana_walker(ir_node * node, eset * set) {
600 if (get_irn_link(node) == MARK) {
601 /* bereits in einem Zyklus besucht. */
604 switch (get_irn_opcode(node)) {
615 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
618 set_irn_link(node, MARK);
619 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
620 ir_node * pred = get_Call_param(node, i);
621 if (get_irn_mode(pred) == mode_P) {
622 free_mark(pred, set);
626 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
627 * jemand das Gegenteil implementiert. */
629 set_irn_link(node, MARK);
630 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
631 ir_node * pred = get_irn_n(node, i);
632 if (get_irn_mode(pred) == mode_P) {
633 free_mark(pred, set);
638 set_irn_link(node, NULL);
642 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
643 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
644 * SymConst-Operationen müssen in passende Const-Operationen
645 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
646 * auf eine echt externe Methode. */
647 static entity ** get_free_methods(void) {
648 eset * set = eset_create();
650 entity ** arr = NEW_ARR_F(entity *, 0);
652 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
653 ir_graph * irg = get_irp_irg(i);
654 entity * ent = get_irg_ent(irg);
655 /* insert "external visible" methods. */
656 if (get_entity_visibility(ent) != local) {
657 eset_insert(set, ent);
659 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
661 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
663 if(get_irp_main_irg()) {
664 eset_insert(set, get_irg_ent(get_irp_main_irg()));
666 for (ent = eset_first(set); ent; ent = eset_next(set)) {
667 ARR_APP1(entity *, arr, ent);
674 void cgana(int *length, entity ***free_methods) {
675 entity ** free_meths;
679 free_meths = get_free_methods();
681 sel_methods_dispose();
683 /* Convert the flexible array to an array that can be handled
685 *length = ARR_LEN(free_meths);
686 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
687 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
688 DEL_ARR_F(free_meths);
691 /* Optimize the address expressions passed to call nodes.
692 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
693 * werden durch Const-Operationen ersetzt.
694 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
695 * durch Const ersetzt.
696 * Sel Knoten, fuer die keine Implementierung existiert, werden
697 * durch Bad ersetzt. */
698 void opt_call_addrs(void) {
700 sel_methods_dispose();
703 pmap * ldname_map = pmap_create();
704 assert(entities == NULL);
705 entities = eset_create();
706 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
707 entity * ent = get_irg_ent(get_irp_irg(i));
708 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
709 * aufgerufen werden. */
710 if (get_entity_visibility(ent) != local) {
711 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
714 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
715 pmap_destroy(ldname_map);