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 = get_tv_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_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, tarval_P_from_entity(ent)); 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_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc) {
196 /* We know which method will be called, no dispatch necessary. */
197 assert(get_entity_peculiarity(ent) != description);
198 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
199 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
200 exchange (node, new_node);
202 assert(get_entity_peculiarity(ent) != inherited);
203 if (!eset_contains(entities, ent)) {
204 /* Entity noch nicht behandelt. Alle (intern oder extern)
205 * implementierten Methoden suchen, die diese Entity
206 * überschreiben. Die Menge an entity.link speichern. */
207 set_entity_link(ent, get_impl_methods(ent));
208 eset_insert(entities, ent);
210 if (get_entity_link(ent) == NULL) {
211 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
212 * Methode zurückgeben. Damit ist sie insbesondere nicht
213 * ausführbar und nicht erreichbar. */
214 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
215 fuer die es keine Implementierung gibt. */
216 if (get_entity_peculiarity(ent) == description) {
217 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
218 xprintf("WARNING: Calling method description %I in method %I which has "
219 "no implementation!\n", get_entity_ident(ent),
220 get_entity_ident(get_irg_ent(current_ir_graph)));
222 exchange(node, new_Bad());
225 entity ** arr = get_entity_link(ent);
229 printf("\nCall site "); DDMN(node);
230 printf(" in "); DDME(get_irg_ent(current_ir_graph));
231 printf(" can call:\n");
232 for (i = 0; i < ARR_LEN(arr); i++) {
233 printf(" - "); DDME(arr[i]);
234 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
239 if (ARR_LEN(arr) == 1 && arr[0] != NULL) {
241 /* Die Sel-Operation kann immer nur einen Wert auf eine
242 * interne Methode zurückgeben. Wir können daher die
243 * Sel-Operation durch eine Const- bzw. SymConst-Operation
245 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
246 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
247 exchange (node, new_node);
255 /* Datenstruktur initialisieren. Zusätzlich werden alle
256 * SymConst-Operationen, die auf interne Methoden verweisen, durch
257 * Const-Operationen ersetzt. */
258 static void sel_methods_init(void) {
260 pmap * ldname_map = pmap_create();
261 assert(entities == NULL);
262 entities = eset_create();
263 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
264 entity * ent = get_irg_ent(get_irp_irg(i));
265 /* Nur extern sichtbare Methode können überhaupt mit SymConst
266 * aufgerufen werden. */
267 if (get_entity_visibility(ent) != local) {
268 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
271 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
272 pmap_destroy(ldname_map);
275 /*****************************************************************************/
277 /* Datenstruktur freigeben. */
278 static void sel_methods_dispose(void) {
281 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
282 entity ** arr = get_entity_link(ent);
286 set_entity_link(ent, NULL);
288 eset_destroy(entities);
293 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
294 * zurückgegeben werden können. Die Liste enthält keine doppelten
296 static entity ** get_Sel_arr(ir_node * sel) {
297 static entity ** NULL_ARRAY = NULL;
300 assert(sel && get_irn_op(sel) == op_Sel);
301 ent = get_Sel_entity(sel);
302 assert(is_method_type(get_entity_type(ent))); /* what else? */
303 arr = get_entity_link(ent);
307 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
308 * kann für polymorphe (abstrakte) Methoden passieren. */
310 NULL_ARRAY = NEW_ARR_F(entity *, 0);
317 static int get_Sel_n_methods(ir_node * sel) {
318 return ARR_LEN(get_Sel_arr(sel));
322 static entity * get_Sel_method(ir_node * sel, int pos) {
323 entity ** arr = get_Sel_arr(sel);
324 assert(pos >= 0 && pos < ARR_LEN(arr));
330 /* --- callee analysis ------------------------------------------------------ */
333 static void callee_ana_node(ir_node * node, eset * methods);
336 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
337 assert(get_irn_mode(node) == mode_T);
338 if (get_irn_link(node) == MARK) {
339 /* already visited */
342 set_irn_link(node, MARK);
344 switch (get_irn_opcode(node)) {
346 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
347 * op_Tuple oder ein Knoten, der eine "freie Methode"
349 ir_node * pred = get_Proj_pred(node);
350 if (get_irn_link(pred) != MARK) {
351 if (get_irn_op(pred) == op_Tuple) {
352 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
354 eset_insert(methods, MARK); /* free method -> unknown */
361 callee_ana_node(get_Tuple_pred(node, n), methods);
365 callee_ana_proj(get_Id_pred(node), n, methods);
369 eset_insert(methods, MARK); /* free method -> unknown */
373 set_irn_link(node, NULL);
377 static void callee_ana_node(ir_node * node, eset * methods) {
380 assert((get_irn_mode(node) == mode_P) || is_Bad(node));
381 /* rekursion verhindern */
382 if (get_irn_link(node) == MARK) {
383 /* already visited */
386 set_irn_link(node, MARK);
388 switch (get_irn_opcode(node)) {
390 /* externe Methode (wegen fix_symconst!) */
391 eset_insert(methods, MARK); /* free method -> unknown */
395 /* interne Methode */
396 entity * ent = get_Const_tarval(node)->u.P.ent;
397 assert(ent && is_method_type(get_entity_type(ent)));
398 if (get_entity_visibility(ent) != external_allocated) {
399 assert(get_entity_irg(ent));
400 eset_insert(methods, ent);
402 eset_insert(methods, MARK); /* free method -> unknown */
408 /* polymorphe Methode */
409 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
410 entity * ent = get_Sel_method(node, i);
412 eset_insert(methods, ent);
414 eset_insert(methods, MARK);
423 case iro_Phi: /* Vereinigung */
424 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
425 callee_ana_node(get_Phi_pred(node, i), methods);
430 callee_ana_node(get_Id_pred(node), methods);
434 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
441 eset_insert(methods, MARK); /* free method -> unknown */
445 assert(0 && "invalid opcode or opcode not implemented");
449 set_irn_link(node, NULL);
453 static void callee_walker(ir_node * call, void * env) {
454 if (get_irn_op(call) == op_Call) {
455 eset * methods = eset_create();
457 entity ** arr = NEW_ARR_F(entity *, 0);
458 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
459 if (eset_contains(methods, MARK)) { /* unknown method */
460 ARR_APP1(entity *, arr, NULL);
462 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
464 ARR_APP1(entity *, arr, ent);
467 if (ARR_LEN(arr) == 0) {
468 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
469 * Sel-Operation war, die keine Methoden zurückgeben
470 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
471 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
473 exchange(call, new_Bad());
475 set_Call_callee_arr(call, ARR_LEN(arr), arr);
478 eset_destroy(methods);
483 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
484 * und speichert das Ergebnis in der Call-Operation. (siehe
485 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
486 * muss bereits aufgebaut sein. */
487 static void callee_ana(void) {
489 /* Alle Graphen analysieren. */
490 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
491 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
497 /* --- free method analysis ------------------------------------------------- */
500 static void free_mark(ir_node * node, eset * set);
502 static void free_mark_proj(ir_node * node, long n, eset * set) {
503 assert(get_irn_mode(node) == mode_T);
504 if (get_irn_link(node) == MARK) {
505 /* already visited */
508 set_irn_link(node, MARK);
509 switch (get_irn_opcode(node)) {
511 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
512 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
514 ir_node * pred = get_Proj_pred(node);
515 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
516 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
518 /* nothing: da in "free_ana_walker" behandelt. */
524 free_mark(get_Tuple_pred(node, n), set);
528 free_mark_proj(get_Id_pred(node), n, set);
534 /* nothing: Die Operationen werden in "free_ana_walker" selbst
539 assert(0 && "unexpected opcode or opcode not implemented");
542 set_irn_link(node, NULL);
546 static void free_mark(ir_node * node, eset * set) {
548 assert(get_irn_mode(node) == mode_P);
549 if (get_irn_link(node) == MARK) {
550 return; /* already visited */
552 set_irn_link(node, MARK);
553 switch (get_irn_opcode(node)) {
555 entity * ent = get_Sel_entity(node);
556 if (is_method_type(get_entity_type(ent))) {
557 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
558 eset_insert(set, get_Sel_method(node, i));
564 /* nothing: SymConst points to extern method */
567 tarval * val = get_Const_tarval(node);
568 entity * ent = val->u.P.ent;
569 if (ent != NULL && is_method_type(get_entity_type(ent))) {
570 eset_insert(set, ent);
575 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
576 free_mark(get_Phi_pred(node, i), set);
580 free_mark(get_Id_pred(node), set);
583 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
586 /* nothing: Wird unten behandelt! */
589 set_irn_link(node, NULL);
593 static void free_ana_walker(ir_node * node, eset * set) {
595 if (get_irn_link(node) == MARK) {
596 /* bereits in einem Zyklus besucht. */
599 switch (get_irn_opcode(node)) {
610 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
613 set_irn_link(node, MARK);
614 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
615 ir_node * pred = get_Call_param(node, i);
616 if (get_irn_mode(pred) == mode_P) {
617 free_mark(pred, set);
621 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
622 * jemand das Gegenteil implementiert. */
624 set_irn_link(node, MARK);
625 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
626 ir_node * pred = get_irn_n(node, i);
627 if (get_irn_mode(pred) == mode_P) {
628 free_mark(pred, set);
633 set_irn_link(node, NULL);
637 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
638 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
639 * SymConst-Operationen müssen in passende Const-Operationen
640 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
641 * auf eine echt externe Methode. */
642 static entity ** get_free_methods(void) {
643 eset * set = eset_create();
645 entity ** arr = NEW_ARR_F(entity *, 0);
647 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
648 ir_graph * irg = get_irp_irg(i);
649 entity * ent = get_irg_ent(irg);
650 /* insert "external visible" methods. */
651 if (get_entity_visibility(ent) != local) {
652 eset_insert(set, ent);
654 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
656 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
658 if(get_irp_main_irg()) {
659 eset_insert(set, get_irg_ent(get_irp_main_irg()));
661 for (ent = eset_first(set); ent; ent = eset_next(set)) {
662 ARR_APP1(entity *, arr, ent);
669 void cgana(int *length, entity ***free_methods) {
670 entity ** free_meths;
674 free_meths = get_free_methods();
676 sel_methods_dispose();
678 /* Convert the flexible array to an array that can be handled
680 *length = ARR_LEN(free_meths);
681 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
682 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
683 DEL_ARR_F(free_meths);
686 /* Optimize the address expressions passed to call nodes.
687 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
688 * werden durch Const-Operationen ersetzt.
689 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
690 * durch Const ersetzt.
691 * Sel Knoten, fuer die keine Implementierung existiert, werden
692 * durch Bad ersetzt. */
693 void opt_call_addrs(void) {
695 sel_methods_dispose();
698 pmap * ldname_map = pmap_create();
699 assert(entities == NULL);
700 entities = eset_create();
701 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
702 entity * ent = get_irg_ent(get_irp_irg(i));
703 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
704 * aufgerufen werden. */
705 if (get_entity_visibility(ent) != local) {
706 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
709 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
710 pmap_destroy(ldname_map);