3 * File name: ir/ana/cgana.c
4 * Purpose: Intraprozedural analyses to estimate the call graph.
5 * Author: Hubert Schmid
9 * Copyright: (c) 1999-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
14 * Intraprozedurale Analyse zur Abschätzung der Aufrulrelation. Es
15 * wird eine Menge von freien Methoden und anschließend die an den
16 * Call-Operationen aufrufbaren Methoden bestimmt.
37 #include "dbginfo_t.h"
39 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
40 * Darstellung der unbekannten Methode. */
41 static void * MARK = &MARK;
45 /* --- sel methods ---------------------------------------------------------- */
48 static eset * entities = NULL;
51 /* Bestimmt die eindeutige Methode, die die Methode für den
52 * übergebenene (dynamischen) Typ überschreibt. */
53 static entity * get_implementation(type * class, entity * method) {
55 if (get_entity_peculiarity(method) != peculiarity_description &&
56 get_entity_owner(method) == class) {
59 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
60 entity * e = get_entity_overwrittenby(method, i);
61 if (get_entity_peculiarity(e) != peculiarity_description && get_entity_owner(e) == class) {
65 for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
66 entity * e = get_implementation(get_class_supertype(class, i), method);
71 assert(0 && "implemenation not found");
75 /* Returns the entity that contains the implementation of the inherited
76 entity if available, else returns the entity passed. */
77 entity *get_inherited_methods_implementation(entity *inh_meth) {
78 entity *impl_meth = NULL;
79 ir_node *addr = get_atomic_ent_value(inh_meth);
80 assert(addr && "constant entity without value");
82 if (get_irn_op(addr) == op_Const) {
83 impl_meth = tarval_to_entity(get_Const_tarval(addr));
85 assert(0 && "Complex constant values not supported -- adress of method should be straight constant!");
87 if (impl_meth && (get_entity_peculiarity(impl_meth) != peculiarity_existent)) {
88 printf("this_meth: "); DDMEO(inh_meth);
89 printf("impl meth: "); DDMEO(impl_meth);
90 assert(!impl_meth || get_entity_peculiarity(impl_meth) == peculiarity_existent);
92 return impl_meth? impl_meth : inh_meth;
96 /* Collect the entity representing the implementation of this
97 entity (not the same if inherited) and all entities for overwriting
98 implementations in "set".
99 If the implementation of the method is not included in the
100 compilation unit "open" is set to true.
101 A recursive descend in the overwritten relation.
102 Cycle-free, therefore must terminate. */
103 void collect_impls(entity *method, eset *set, int *size, bool *open) {
105 if (get_entity_peculiarity(method) == peculiarity_existent) {
106 if (get_entity_visibility(method) == visibility_external_allocated) {
107 assert(get_entity_irg(method) == NULL);
110 assert(get_entity_irg(method) != NULL);
111 if (!eset_contains(set, method)) {
112 eset_insert(set, method);
117 if (get_entity_peculiarity(method) == peculiarity_inherited) {
118 entity *impl_ent = get_inherited_methods_implementation(method);
119 assert(impl_ent && "no implementation for inherited entity");
120 if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
121 assert(get_entity_irg(impl_ent) == NULL);
124 assert(get_entity_irg(impl_ent) != NULL);
125 if (!eset_contains(set, impl_ent)) {
126 eset_insert(set, impl_ent);
131 /** recursive descend **/
132 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
133 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
137 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
138 * (und implementieren). In der zurückgegebenen Reihung kommt jede
139 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
140 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
141 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
142 * keine Methoden, die die "method" überschreiben, so gibt die Methode
144 static entity ** get_impl_methods(entity * method) {
145 eset * set = eset_create();
150 /** Collect all method entities that can be called here **/
151 collect_impls(method, set, &size, &open);
154 Vorgaenger einfuegen. **/
155 if (size == 0 && !open) {
156 /* keine implementierte überschriebene Methode */
160 arr = NEW_ARR_F(entity *, size + 1);
161 arr[0] = NULL; /* Represents open method */
162 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
166 arr = NEW_ARR_F(entity *, size);
167 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
175 /* debug makros used in sel_methods_walker */
176 #define SIZ(x) sizeof(x)/sizeof((x)[0])
178 #define DBG_OPT_NORMALIZE \
179 __dbg_info_merge_pair(new_node, node, dbg_const_eval)
180 #define DBG_OPT_POLY_ALLOC \
184 ons[1] = skip_Proj(get_Sel_ptr(node)); \
185 __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
187 #define DBG_OPT_POLY \
188 __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
191 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
192 if (get_irn_op(node) == op_SymConst) {
193 /* Wenn möglich SymConst-Operation durch Const-Operation
195 if (get_SymConst_kind(node) == linkage_ptr_info) {
196 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
197 if (entry != NULL) { /* Method is declared in the compiled code */
198 entity * ent = entry->value;
199 if (get_opt_normalize() && (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
201 assert(get_entity_irg(ent));
202 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
203 new_node = new_d_Const(get_irn_dbg_info(node),
204 mode_P_mach, new_tarval_from_entity(ent, mode_P_mach)); DBG_OPT_NORMALIZE;
205 exchange(node, new_node);
209 } else if (get_irn_op(node) == op_Sel &&
210 is_method_type(get_entity_type(get_Sel_entity(node)))) {
211 entity * ent = get_Sel_entity(node);
212 if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
213 (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
216 /* We know which method will be called, no dispatch necessary. */
218 assert(get_entity_peculiarity(ent) != peculiarity_description);
219 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
220 /* @@@ Is this correct?? Alloc could reference a subtype of the owner
221 of Sel that overwrites the method referenced in Sel. */
222 /* @@@ Yes, this is wrong. GL, 10.3.04 */
223 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
225 called_ent = resolve_ent_polymorphy(get_Alloc_type(skip_Proj(get_Sel_ptr(node))), ent);
226 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
227 /* called_ent may not be description: has no Address/Const to Call! */
228 assert(get_entity_peculiarity(called_ent) != peculiarity_description);
229 new_node = copy_const_value(get_atomic_ent_value(called_ent)); DBG_OPT_POLY_ALLOC;
231 exchange (node, new_node);
233 assert(get_entity_peculiarity(ent) != peculiarity_inherited);
234 if (!eset_contains(entities, ent)) {
235 /* Entity noch nicht behandelt. Alle (intern oder extern)
236 * implementierten Methoden suchen, die diese Entity
237 * überschreiben. Die Menge an entity.link speichern. */
238 set_entity_link(ent, get_impl_methods(ent));
239 eset_insert(entities, ent);
241 if (get_entity_link(ent) == NULL) {
242 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
243 * Methode zurückgeben. Damit ist sie insbesondere nicht
244 * ausführbar und nicht erreichbar. */
245 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
246 fuer die es keine Implementierung gibt. */
247 if (get_entity_peculiarity(ent) == peculiarity_description) {
248 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
249 printf("WARNING: Calling method description %s in method %s which has "
250 "no implementation!\n", get_entity_name(ent),
251 get_entity_name(get_irg_ent(current_ir_graph)));
253 exchange(node, new_Bad());
256 entity ** arr = get_entity_link(ent);
260 printf("\nCall site "); DDMN(node);
261 printf(" in "); DDME(get_irg_ent(current_ir_graph));
262 printf(" can call:\n");
263 for (i = 0; i < ARR_LEN(arr); i++) {
264 printf(" - "); DDME(arr[i]);
265 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
270 if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
271 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
273 /* Die Sel-Operation kann immer nur einen Wert auf eine
274 * interne Methode zurückgeben. Wir können daher die
275 * Sel-Operation durch eine Const- bzw. SymConst-Operation
277 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
278 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
279 exchange (node, new_node);
287 /* Datenstruktur initialisieren. Zusätzlich werden alle
288 * SymConst-Operationen, die auf interne Methoden verweisen, durch
289 * Const-Operationen ersetzt. */
290 static void sel_methods_init(void) {
292 pmap * ldname_map = pmap_create();
293 assert(entities == NULL);
294 entities = eset_create();
295 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
296 entity * ent = get_irg_ent(get_irp_irg(i));
297 /* Nur extern sichtbare Methode können überhaupt mit SymConst
298 * aufgerufen werden. */
299 if (get_entity_visibility(ent) != visibility_local) {
300 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
303 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
304 pmap_destroy(ldname_map);
307 /*****************************************************************************/
309 /* Datenstruktur freigeben. */
310 static void sel_methods_dispose(void) {
313 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
314 entity ** arr = get_entity_link(ent);
318 set_entity_link(ent, NULL);
320 eset_destroy(entities);
325 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
326 * zurückgegeben werden können. Die Liste enthält keine doppelten
328 static entity ** get_Sel_arr(ir_node * sel) {
329 static entity ** NULL_ARRAY = NULL;
332 assert(sel && get_irn_op(sel) == op_Sel);
333 ent = get_Sel_entity(sel);
334 assert(is_method_type(get_entity_type(ent))); /* what else? */
335 arr = get_entity_link(ent);
339 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
340 * kann für polymorphe (abstrakte) Methoden passieren. */
342 NULL_ARRAY = NEW_ARR_F(entity *, 0);
349 static int get_Sel_n_methods(ir_node * sel) {
350 return ARR_LEN(get_Sel_arr(sel));
354 static entity * get_Sel_method(ir_node * sel, int pos) {
355 entity ** arr = get_Sel_arr(sel);
356 assert(pos >= 0 && pos < ARR_LEN(arr));
362 /* --- callee analysis ------------------------------------------------------ */
365 static void callee_ana_node(ir_node * node, eset * methods);
368 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
369 assert(get_irn_mode(node) == mode_T);
370 if (get_irn_link(node) == MARK) {
371 /* already visited */
374 set_irn_link(node, MARK);
376 switch (get_irn_opcode(node)) {
378 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
379 * op_Tuple oder ein Knoten, der eine "freie Methode"
381 ir_node * pred = get_Proj_pred(node);
382 if (get_irn_link(pred) != MARK) {
383 if (get_irn_op(pred) == op_Tuple) {
384 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
386 eset_insert(methods, MARK); /* free method -> unknown */
393 callee_ana_node(get_Tuple_pred(node, n), methods);
397 callee_ana_proj(get_Id_pred(node), n, methods);
401 eset_insert(methods, MARK); /* free method -> unknown */
405 set_irn_link(node, NULL);
409 static void callee_ana_node(ir_node * node, eset * methods) {
412 assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
413 /* rekursion verhindern */
414 if (get_irn_link(node) == MARK) {
415 /* already visited */
418 set_irn_link(node, MARK);
420 switch (get_irn_opcode(node)) {
422 /* externe Methode (wegen fix_symconst!) */
423 eset_insert(methods, MARK); /* free method -> unknown */
427 /* interne Methode */
428 entity * ent = tarval_to_entity(get_Const_tarval(node));
429 assert(ent && is_method_type(get_entity_type(ent)));
430 if (get_entity_visibility(ent) != visibility_external_allocated) {
431 assert(get_entity_irg(ent));
432 eset_insert(methods, ent);
434 eset_insert(methods, MARK); /* free method -> unknown */
440 /* polymorphe Methode */
441 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
442 entity * ent = get_Sel_method(node, i);
444 eset_insert(methods, ent);
446 eset_insert(methods, MARK);
455 case iro_Phi: /* Vereinigung */
456 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
457 callee_ana_node(get_Phi_pred(node, i), methods);
462 callee_ana_node(get_Id_pred(node), methods);
466 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
473 eset_insert(methods, MARK); /* free method -> unknown */
477 assert(0 && "invalid opcode or opcode not implemented");
481 set_irn_link(node, NULL);
485 static void callee_walker(ir_node * call, void * env) {
486 if (get_irn_op(call) == op_Call) {
487 eset * methods = eset_create();
489 entity ** arr = NEW_ARR_F(entity *, 0);
490 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
491 if (eset_contains(methods, MARK)) { /* unknown method */
492 ARR_APP1(entity *, arr, NULL);
494 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
496 ARR_APP1(entity *, arr, ent);
499 if (ARR_LEN(arr) == 0) {
500 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
501 * Sel-Operation war, die keine Methoden zurückgeben
502 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
503 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
505 exchange(call, new_Bad());
507 set_Call_callee_arr(call, ARR_LEN(arr), arr);
510 eset_destroy(methods);
515 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
516 * und speichert das Ergebnis in der Call-Operation. (siehe
517 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
518 * muss bereits aufgebaut sein. */
519 static void callee_ana(void) {
521 /* Alle Graphen analysieren. */
522 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
523 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
524 set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
530 /* --- free method analysis ------------------------------------------------- */
533 static void free_mark(ir_node * node, eset * set);
535 static void free_mark_proj(ir_node * node, long n, eset * set) {
536 assert(get_irn_mode(node) == mode_T);
537 if (get_irn_link(node) == MARK) {
538 /* already visited */
541 set_irn_link(node, MARK);
542 switch (get_irn_opcode(node)) {
544 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
545 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
547 ir_node * pred = get_Proj_pred(node);
548 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
549 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
551 /* nothing: da in "free_ana_walker" behandelt. */
557 free_mark(get_Tuple_pred(node, n), set);
561 free_mark_proj(get_Id_pred(node), n, set);
567 /* nothing: Die Operationen werden in "free_ana_walker" selbst
572 assert(0 && "unexpected opcode or opcode not implemented");
575 set_irn_link(node, NULL);
579 static void free_mark(ir_node * node, eset * set) {
581 assert(mode_is_reference(get_irn_mode(node)));
582 if (get_irn_link(node) == MARK) {
583 return; /* already visited */
585 set_irn_link(node, MARK);
586 switch (get_irn_opcode(node)) {
588 entity * ent = get_Sel_entity(node);
589 if (is_method_type(get_entity_type(ent))) {
590 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
591 eset_insert(set, get_Sel_method(node, i));
597 /* nothing: SymConst points to extern method */
600 tarval * val = get_Const_tarval(node);
601 if (tarval_is_entity(val)) { /* filter null pointer */
602 entity * ent = tarval_to_entity(val);
603 if (is_method_type(get_entity_type(ent))) {
604 eset_insert(set, ent);
610 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
611 free_mark(get_Phi_pred(node, i), set);
615 free_mark(get_Id_pred(node), set);
618 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
621 /* nothing: Wird unten behandelt! */
624 set_irn_link(node, NULL);
628 static void free_ana_walker(ir_node * node, eset * set) {
630 if (get_irn_link(node) == MARK) {
631 /* bereits in einem Zyklus besucht. */
634 switch (get_irn_opcode(node)) {
645 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
648 set_irn_link(node, MARK);
649 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
650 ir_node * pred = get_Call_param(node, i);
651 if (mode_is_reference(get_irn_mode(pred))) {
652 free_mark(pred, set);
656 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
657 * jemand das Gegenteil implementiert. */
659 set_irn_link(node, MARK);
660 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
661 ir_node * pred = get_irn_n(node, i);
662 if (mode_is_reference(get_irn_mode(pred))) {
663 free_mark(pred, set);
668 set_irn_link(node, NULL);
672 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
673 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
674 * SymConst-Operationen müssen in passende Const-Operationen
675 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
676 * auf eine echt externe Methode. */
677 static entity ** get_free_methods(void) {
678 eset * set = eset_create();
680 entity ** arr = NEW_ARR_F(entity *, 0);
682 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
683 ir_graph * irg = get_irp_irg(i);
684 entity * ent = get_irg_ent(irg);
685 /* insert "external visible" methods. */
686 if (get_entity_visibility(ent) != visibility_local) {
687 eset_insert(set, ent);
689 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
691 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
693 if(get_irp_main_irg()) {
694 eset_insert(set, get_irg_ent(get_irp_main_irg()));
696 for (ent = eset_first(set); ent; ent = eset_next(set)) {
697 ARR_APP1(entity *, arr, ent);
704 void cgana(int *length, entity ***free_methods) {
705 entity ** free_meths;
709 free_meths = get_free_methods();
711 sel_methods_dispose();
713 /* Convert the flexible array to an array that can be handled
715 *length = ARR_LEN(free_meths);
716 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
717 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
718 DEL_ARR_F(free_meths);
721 /* Optimize the address expressions passed to call nodes.
722 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
723 * werden durch Const-Operationen ersetzt.
724 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
725 * durch Const ersetzt.
726 * Sel Knoten, fuer die keine Implementierung existiert, werden
727 * durch Bad ersetzt. */
728 void opt_call_addrs(void) {
730 sel_methods_dispose();
733 pmap * ldname_map = pmap_create();
734 assert(entities == NULL);
735 entities = eset_create();
736 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
737 entity * ent = get_irg_ent(get_irp_irg(i));
738 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
739 * aufgerufen werden. */
740 if (get_entity_visibility(ent) != local) {
741 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
744 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
745 pmap_destroy(ldname_map);