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.
34 #include "dbginfo_t.h"
36 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
37 * Darstellung der unbekannten Methode. */
38 static void * MARK = &MARK;
42 /* --- sel methods ---------------------------------------------------------- */
45 static eset * entities = NULL;
48 /* Bestimmt die eindeutige Methode, die die Methode für den
49 * übergebenene (dynamischen) Typ überschreibt. */
50 static entity * get_implementation(type * class, entity * method) {
52 if (get_entity_peculiarity(method) != description &&
53 get_entity_owner(method) == class) {
56 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
57 entity * e = get_entity_overwrittenby(method, i);
58 if (get_entity_peculiarity(e) != description && get_entity_owner(e) == class) {
62 for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
63 entity * e = get_implementation(get_class_supertype(class, i), method);
68 assert(0 && "implemenation not found");
72 /* Returns the entity that contains the implementation of the inherited
73 entity if available, else returns the entity passed. */
74 entity *get_inherited_methods_implementation(entity *inh_meth) {
75 entity *impl_meth = NULL;
76 ir_node *addr = get_atomic_ent_value(inh_meth);
77 assert(addr && "constant entity without value");
79 if (get_irn_op(addr) == op_Const) {
80 impl_meth = tarval_to_entity(get_Const_tarval(addr));
82 assert(0 && "Complex constant values not supported -- adress of method should be straight constant!");
84 if (impl_meth && (get_entity_peculiarity(impl_meth) != existent)) {
85 printf("this_meth: "); DDMEO(inh_meth);
86 printf("impl meth: "); DDMEO(impl_meth);
87 assert(!impl_meth || get_entity_peculiarity(impl_meth) == existent);
89 return impl_meth? impl_meth : inh_meth;
93 /* Collect the entity representing the implementation of this
94 entity (not the same if inherited) and all entities for overwriting
95 implementations in "set".
96 If the implementation of the method is not included in the
97 compilation unit "open" is set to true.
98 A recursive descend in the overwritten relation.
99 Cycle-free, therefore must terminate. */
100 void collect_impls(entity *method, eset *set, int *size, bool *open) {
102 if (get_entity_peculiarity(method) == existent) {
103 if (get_entity_visibility(method) == external_allocated) {
104 assert(get_entity_irg(method) == NULL);
107 assert(get_entity_irg(method) != NULL);
108 if (!eset_contains(set, method)) {
109 eset_insert(set, method);
114 if (get_entity_peculiarity(method) == inherited) {
115 entity *impl_ent = get_inherited_methods_implementation(method);
116 assert(impl_ent && "no implementation for inherited entity");
117 if (get_entity_visibility(impl_ent) == external_allocated) {
118 assert(get_entity_irg(impl_ent) == NULL);
121 assert(get_entity_irg(impl_ent) != NULL);
122 if (!eset_contains(set, impl_ent)) {
123 eset_insert(set, impl_ent);
128 /** recursive descend **/
129 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
130 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
134 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
135 * (und implementieren). In der zurückgegebenen Reihung kommt jede
136 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
137 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
138 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
139 * keine Methoden, die die "method" überschreiben, so gibt die Methode
141 static entity ** get_impl_methods(entity * method) {
142 eset * set = eset_create();
147 /** Collect all method entities that can be called here **/
148 collect_impls(method, set, &size, &open);
151 Vorgaenger einfuegen. **/
152 if (size == 0 && !open) {
153 /* keine implementierte überschriebene Methode */
157 arr = NEW_ARR_F(entity *, size + 1);
158 arr[0] = NULL; /* Represents open method */
159 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
163 arr = NEW_ARR_F(entity *, size);
164 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
172 /* debug makros used in sel_methods_walker */
173 #define SIZ(x) sizeof(x)/sizeof((x)[0])
175 #define DBG_OPT_NORMALIZE \
176 __dbg_info_merge_pair(new_node, node, dbg_const_eval)
177 #define DBG_OPT_POLY_ALLOC \
181 ons[1] = skip_Proj(get_Sel_ptr(node)); \
182 __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
184 #define DBG_OPT_POLY \
185 __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
188 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
189 if (get_irn_op(node) == op_SymConst) {
190 /* Wenn möglich SymConst-Operation durch Const-Operation
192 if (get_SymConst_kind(node) == linkage_ptr_info) {
193 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
194 if (entry != NULL) { /* Method is declared in the compiled code */
195 entity * ent = entry->value;
196 if (get_opt_normalize() && (get_entity_visibility(ent) != external_allocated)) { /* Meth. is defined */
198 assert(get_entity_irg(ent));
199 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
200 new_node = new_d_Const(get_irn_dbg_info(node),
201 mode_P_mach, new_tarval_from_entity(ent, mode_P_mach)); DBG_OPT_NORMALIZE;
202 exchange(node, new_node);
206 } else if (get_irn_op(node) == op_Sel &&
207 is_method_type(get_entity_type(get_Sel_entity(node)))) {
208 entity * ent = get_Sel_entity(node);
209 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
210 (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
212 /* We know which method will be called, no dispatch necessary. */
213 assert(get_entity_peculiarity(ent) != description);
214 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
215 /* @@@ Is this correct?? Alloc could reference a subtype of the owner
216 of Sel that overwrites the method referenced in Sel. */
217 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
218 exchange (node, new_node);
220 assert(get_entity_peculiarity(ent) != inherited);
221 if (!eset_contains(entities, ent)) {
222 /* Entity noch nicht behandelt. Alle (intern oder extern)
223 * implementierten Methoden suchen, die diese Entity
224 * überschreiben. Die Menge an entity.link speichern. */
225 set_entity_link(ent, get_impl_methods(ent));
226 eset_insert(entities, ent);
228 if (get_entity_link(ent) == NULL) {
229 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
230 * Methode zurückgeben. Damit ist sie insbesondere nicht
231 * ausführbar und nicht erreichbar. */
232 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
233 fuer die es keine Implementierung gibt. */
234 if (get_entity_peculiarity(ent) == description) {
235 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
236 printf("WARNING: Calling method description %s in method %s which has "
237 "no implementation!\n", id_to_str(get_entity_ident(ent)),
238 id_to_str(get_entity_ident(get_irg_ent(current_ir_graph))));
240 exchange(node, new_Bad());
243 entity ** arr = get_entity_link(ent);
247 printf("\nCall site "); DDMN(node);
248 printf(" in "); DDME(get_irg_ent(current_ir_graph));
249 printf(" can call:\n");
250 for (i = 0; i < ARR_LEN(arr); i++) {
251 printf(" - "); DDME(arr[i]);
252 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
257 if (get_optimize() && get_opt_dyn_meth_dispatch() &&
258 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
260 /* Die Sel-Operation kann immer nur einen Wert auf eine
261 * interne Methode zurückgeben. Wir können daher die
262 * Sel-Operation durch eine Const- bzw. SymConst-Operation
264 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
265 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
266 exchange (node, new_node);
274 /* Datenstruktur initialisieren. Zusätzlich werden alle
275 * SymConst-Operationen, die auf interne Methoden verweisen, durch
276 * Const-Operationen ersetzt. */
277 static void sel_methods_init(void) {
279 pmap * ldname_map = pmap_create();
280 assert(entities == NULL);
281 entities = eset_create();
282 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
283 entity * ent = get_irg_ent(get_irp_irg(i));
284 /* Nur extern sichtbare Methode können überhaupt mit SymConst
285 * aufgerufen werden. */
286 if (get_entity_visibility(ent) != local) {
287 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
290 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
291 pmap_destroy(ldname_map);
294 /*****************************************************************************/
296 /* Datenstruktur freigeben. */
297 static void sel_methods_dispose(void) {
300 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
301 entity ** arr = get_entity_link(ent);
305 set_entity_link(ent, NULL);
307 eset_destroy(entities);
312 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
313 * zurückgegeben werden können. Die Liste enthält keine doppelten
315 static entity ** get_Sel_arr(ir_node * sel) {
316 static entity ** NULL_ARRAY = NULL;
319 assert(sel && get_irn_op(sel) == op_Sel);
320 ent = get_Sel_entity(sel);
321 assert(is_method_type(get_entity_type(ent))); /* what else? */
322 arr = get_entity_link(ent);
326 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
327 * kann für polymorphe (abstrakte) Methoden passieren. */
329 NULL_ARRAY = NEW_ARR_F(entity *, 0);
336 static int get_Sel_n_methods(ir_node * sel) {
337 return ARR_LEN(get_Sel_arr(sel));
341 static entity * get_Sel_method(ir_node * sel, int pos) {
342 entity ** arr = get_Sel_arr(sel);
343 assert(pos >= 0 && pos < ARR_LEN(arr));
349 /* --- callee analysis ------------------------------------------------------ */
352 static void callee_ana_node(ir_node * node, eset * methods);
355 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
356 assert(get_irn_mode(node) == mode_T);
357 if (get_irn_link(node) == MARK) {
358 /* already visited */
361 set_irn_link(node, MARK);
363 switch (get_irn_opcode(node)) {
365 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
366 * op_Tuple oder ein Knoten, der eine "freie Methode"
368 ir_node * pred = get_Proj_pred(node);
369 if (get_irn_link(pred) != MARK) {
370 if (get_irn_op(pred) == op_Tuple) {
371 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
373 eset_insert(methods, MARK); /* free method -> unknown */
380 callee_ana_node(get_Tuple_pred(node, n), methods);
384 callee_ana_proj(get_Id_pred(node), n, methods);
388 eset_insert(methods, MARK); /* free method -> unknown */
392 set_irn_link(node, NULL);
396 static void callee_ana_node(ir_node * node, eset * methods) {
399 assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
400 /* rekursion verhindern */
401 if (get_irn_link(node) == MARK) {
402 /* already visited */
405 set_irn_link(node, MARK);
407 switch (get_irn_opcode(node)) {
409 /* externe Methode (wegen fix_symconst!) */
410 eset_insert(methods, MARK); /* free method -> unknown */
414 /* interne Methode */
415 entity * ent = tarval_to_entity(get_Const_tarval(node));
416 assert(ent && is_method_type(get_entity_type(ent)));
417 if (get_entity_visibility(ent) != external_allocated) {
418 assert(get_entity_irg(ent));
419 eset_insert(methods, ent);
421 eset_insert(methods, MARK); /* free method -> unknown */
427 /* polymorphe Methode */
428 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
429 entity * ent = get_Sel_method(node, i);
431 eset_insert(methods, ent);
433 eset_insert(methods, MARK);
442 case iro_Phi: /* Vereinigung */
443 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
444 callee_ana_node(get_Phi_pred(node, i), methods);
449 callee_ana_node(get_Id_pred(node), methods);
453 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
460 eset_insert(methods, MARK); /* free method -> unknown */
464 assert(0 && "invalid opcode or opcode not implemented");
468 set_irn_link(node, NULL);
472 static void callee_walker(ir_node * call, void * env) {
473 if (get_irn_op(call) == op_Call) {
474 eset * methods = eset_create();
476 entity ** arr = NEW_ARR_F(entity *, 0);
477 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
478 if (eset_contains(methods, MARK)) { /* unknown method */
479 ARR_APP1(entity *, arr, NULL);
481 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
483 ARR_APP1(entity *, arr, ent);
486 if (ARR_LEN(arr) == 0) {
487 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
488 * Sel-Operation war, die keine Methoden zurückgeben
489 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
490 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
492 exchange(call, new_Bad());
494 set_Call_callee_arr(call, ARR_LEN(arr), arr);
497 eset_destroy(methods);
502 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
503 * und speichert das Ergebnis in der Call-Operation. (siehe
504 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
505 * muss bereits aufgebaut sein. */
506 static void callee_ana(void) {
508 /* Alle Graphen analysieren. */
509 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
510 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
516 /* --- free method analysis ------------------------------------------------- */
519 static void free_mark(ir_node * node, eset * set);
521 static void free_mark_proj(ir_node * node, long n, eset * set) {
522 assert(get_irn_mode(node) == mode_T);
523 if (get_irn_link(node) == MARK) {
524 /* already visited */
527 set_irn_link(node, MARK);
528 switch (get_irn_opcode(node)) {
530 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
531 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
533 ir_node * pred = get_Proj_pred(node);
534 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
535 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
537 /* nothing: da in "free_ana_walker" behandelt. */
543 free_mark(get_Tuple_pred(node, n), set);
547 free_mark_proj(get_Id_pred(node), n, set);
553 /* nothing: Die Operationen werden in "free_ana_walker" selbst
558 assert(0 && "unexpected opcode or opcode not implemented");
561 set_irn_link(node, NULL);
565 static void free_mark(ir_node * node, eset * set) {
567 assert(mode_is_reference(get_irn_mode(node)));
568 if (get_irn_link(node) == MARK) {
569 return; /* already visited */
571 set_irn_link(node, MARK);
572 switch (get_irn_opcode(node)) {
574 entity * ent = get_Sel_entity(node);
575 if (is_method_type(get_entity_type(ent))) {
576 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
577 eset_insert(set, get_Sel_method(node, i));
583 /* nothing: SymConst points to extern method */
586 tarval * val = get_Const_tarval(node);
587 if (tarval_is_entity(val)) { /* filter null pointer */
588 entity * ent = tarval_to_entity(val);
589 if (is_method_type(get_entity_type(ent))) {
590 eset_insert(set, ent);
596 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
597 free_mark(get_Phi_pred(node, i), set);
601 free_mark(get_Id_pred(node), set);
604 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
607 /* nothing: Wird unten behandelt! */
610 set_irn_link(node, NULL);
614 static void free_ana_walker(ir_node * node, eset * set) {
616 if (get_irn_link(node) == MARK) {
617 /* bereits in einem Zyklus besucht. */
620 switch (get_irn_opcode(node)) {
631 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
634 set_irn_link(node, MARK);
635 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
636 ir_node * pred = get_Call_param(node, i);
637 if (mode_is_reference(get_irn_mode(pred))) {
638 free_mark(pred, set);
642 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
643 * jemand das Gegenteil implementiert. */
645 set_irn_link(node, MARK);
646 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
647 ir_node * pred = get_irn_n(node, i);
648 if (mode_is_reference(get_irn_mode(pred))) {
649 free_mark(pred, set);
654 set_irn_link(node, NULL);
658 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
659 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
660 * SymConst-Operationen müssen in passende Const-Operationen
661 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
662 * auf eine echt externe Methode. */
663 static entity ** get_free_methods(void) {
664 eset * set = eset_create();
666 entity ** arr = NEW_ARR_F(entity *, 0);
668 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
669 ir_graph * irg = get_irp_irg(i);
670 entity * ent = get_irg_ent(irg);
671 /* insert "external visible" methods. */
672 if (get_entity_visibility(ent) != local) {
673 eset_insert(set, ent);
675 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
677 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
679 if(get_irp_main_irg()) {
680 eset_insert(set, get_irg_ent(get_irp_main_irg()));
682 for (ent = eset_first(set); ent; ent = eset_next(set)) {
683 ARR_APP1(entity *, arr, ent);
690 void cgana(int *length, entity ***free_methods) {
691 entity ** free_meths;
695 free_meths = get_free_methods();
697 sel_methods_dispose();
699 /* Convert the flexible array to an array that can be handled
701 *length = ARR_LEN(free_meths);
702 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
703 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
704 DEL_ARR_F(free_meths);
707 /* Optimize the address expressions passed to call nodes.
708 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
709 * werden durch Const-Operationen ersetzt.
710 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
711 * durch Const ersetzt.
712 * Sel Knoten, fuer die keine Implementierung existiert, werden
713 * durch Bad ersetzt. */
714 void opt_call_addrs(void) {
716 sel_methods_dispose();
719 pmap * ldname_map = pmap_create();
720 assert(entities == NULL);
721 entities = eset_create();
722 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
723 entity * ent = get_irg_ent(get_irp_irg(i));
724 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
725 * aufgerufen werden. */
726 if (get_entity_visibility(ent) != local) {
727 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
730 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
731 pmap_destroy(ldname_map);