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 (intern_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 (intern_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 (intern_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 (intern_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\n in method %s\n of class %s\n which has "
250 "no implementation!\n", get_entity_name(ent),
251 get_entity_name(get_irg_ent(current_ir_graph)),
252 get_type_name(get_entity_owner(get_irg_ent(current_ir_graph))));
253 printf("This happens when compiling a Java Interface that's never really used, i.e., "
254 "no class implementing the interface is ever used.\n");
256 exchange(node, new_Bad());
259 entity ** arr = get_entity_link(ent);
263 printf("\nCall site "); DDMN(node);
264 printf(" in "); DDME(get_irg_ent(current_ir_graph));
265 printf(" can call:\n");
266 for (i = 0; i < ARR_LEN(arr); i++) {
267 printf(" - "); DDME(arr[i]);
268 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
273 if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
274 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
276 /* Die Sel-Operation kann immer nur einen Wert auf eine
277 * interne Methode zurückgeben. Wir können daher die
278 * Sel-Operation durch eine Const- bzw. SymConst-Operation
280 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
281 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
282 exchange (node, new_node);
290 /* Datenstruktur initialisieren. Zusätzlich werden alle
291 * SymConst-Operationen, die auf interne Methoden verweisen, durch
292 * Const-Operationen ersetzt. */
293 static void sel_methods_init(void) {
295 pmap * ldname_map = pmap_create();
296 assert(entities == NULL);
297 entities = eset_create();
298 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
299 entity * ent = get_irg_ent(get_irp_irg(i));
300 /* Nur extern sichtbare Methode können überhaupt mit SymConst
301 * aufgerufen werden. */
302 if (get_entity_visibility(ent) != visibility_local) {
303 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
306 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
307 pmap_destroy(ldname_map);
310 /*****************************************************************************/
312 /* Datenstruktur freigeben. */
313 static void sel_methods_dispose(void) {
316 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
317 entity ** arr = get_entity_link(ent);
321 set_entity_link(ent, NULL);
323 eset_destroy(entities);
328 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
329 * zurückgegeben werden können. Die Liste enthält keine doppelten
331 static entity ** get_Sel_arr(ir_node * sel) {
332 static entity ** NULL_ARRAY = NULL;
335 assert(sel && intern_get_irn_op(sel) == op_Sel);
336 ent = get_Sel_entity(sel);
337 assert(is_method_type(get_entity_type(ent))); /* what else? */
338 arr = get_entity_link(ent);
342 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
343 * kann für polymorphe (abstrakte) Methoden passieren. */
345 NULL_ARRAY = NEW_ARR_F(entity *, 0);
352 static int get_Sel_n_methods(ir_node * sel) {
353 return ARR_LEN(get_Sel_arr(sel));
357 static entity * get_Sel_method(ir_node * sel, int pos) {
358 entity ** arr = get_Sel_arr(sel);
359 assert(pos >= 0 && pos < ARR_LEN(arr));
365 /* --- callee analysis ------------------------------------------------------ */
368 static void callee_ana_node(ir_node * node, eset * methods);
371 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
372 assert(get_irn_mode(node) == mode_T);
373 if (get_irn_link(node) == MARK) {
374 /* already visited */
377 set_irn_link(node, MARK);
379 switch (intern_get_irn_opcode(node)) {
381 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
382 * op_Tuple oder ein Knoten, der eine "freie Methode"
384 ir_node * pred = get_Proj_pred(node);
385 if (get_irn_link(pred) != MARK) {
386 if (intern_get_irn_op(pred) == op_Tuple) {
387 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
389 eset_insert(methods, MARK); /* free method -> unknown */
396 callee_ana_node(get_Tuple_pred(node, n), methods);
400 callee_ana_proj(get_Id_pred(node), n, methods);
404 eset_insert(methods, MARK); /* free method -> unknown */
408 set_irn_link(node, NULL);
412 static void callee_ana_node(ir_node * node, eset * methods) {
415 assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
416 /* rekursion verhindern */
417 if (get_irn_link(node) == MARK) {
418 /* already visited */
421 set_irn_link(node, MARK);
423 switch (intern_get_irn_opcode(node)) {
425 /* externe Methode (wegen fix_symconst!) */
426 eset_insert(methods, MARK); /* free method -> unknown */
430 /* interne Methode */
431 entity * ent = tarval_to_entity(get_Const_tarval(node));
432 assert(ent && is_method_type(get_entity_type(ent)));
433 if (get_entity_visibility(ent) != visibility_external_allocated) {
434 assert(get_entity_irg(ent));
435 eset_insert(methods, ent);
437 eset_insert(methods, MARK); /* free method -> unknown */
443 /* polymorphe Methode */
444 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
445 entity * ent = get_Sel_method(node, i);
447 eset_insert(methods, ent);
449 eset_insert(methods, MARK);
458 case iro_Phi: /* Vereinigung */
459 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
460 callee_ana_node(get_Phi_pred(node, i), methods);
465 callee_ana_node(get_Id_pred(node), methods);
469 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
476 eset_insert(methods, MARK); /* free method -> unknown */
480 assert(0 && "invalid opcode or opcode not implemented");
484 set_irn_link(node, NULL);
488 static void callee_walker(ir_node * call, void * env) {
489 if (intern_get_irn_op(call) == op_Call) {
490 eset * methods = eset_create();
492 entity ** arr = NEW_ARR_F(entity *, 0);
493 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
494 if (eset_contains(methods, MARK)) { /* unknown method */
495 ARR_APP1(entity *, arr, NULL);
497 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
499 ARR_APP1(entity *, arr, ent);
502 if (ARR_LEN(arr) == 0) {
503 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
504 * Sel-Operation war, die keine Methoden zurückgeben
505 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
506 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
508 exchange(call, new_Bad());
510 set_Call_callee_arr(call, ARR_LEN(arr), arr);
513 eset_destroy(methods);
518 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
519 * und speichert das Ergebnis in der Call-Operation. (siehe
520 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
521 * muss bereits aufgebaut sein. */
522 static void callee_ana(void) {
524 /* Alle Graphen analysieren. */
525 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
526 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
527 set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
533 /* --- free method analysis ------------------------------------------------- */
536 static void free_mark(ir_node * node, eset * set);
538 static void free_mark_proj(ir_node * node, long n, eset * set) {
539 assert(get_irn_mode(node) == mode_T);
540 if (get_irn_link(node) == MARK) {
541 /* already visited */
544 set_irn_link(node, MARK);
545 switch (intern_get_irn_opcode(node)) {
547 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
548 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
550 ir_node * pred = get_Proj_pred(node);
551 if (get_irn_link(pred) != MARK && intern_get_irn_op(pred) == op_Tuple) {
552 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
554 /* nothing: da in "free_ana_walker" behandelt. */
560 free_mark(get_Tuple_pred(node, n), set);
564 free_mark_proj(get_Id_pred(node), n, set);
570 /* nothing: Die Operationen werden in "free_ana_walker" selbst
575 assert(0 && "unexpected opcode or opcode not implemented");
578 set_irn_link(node, NULL);
582 static void free_mark(ir_node * node, eset * set) {
584 assert(mode_is_reference(get_irn_mode(node)));
585 if (get_irn_link(node) == MARK) {
586 return; /* already visited */
588 set_irn_link(node, MARK);
589 switch (intern_get_irn_opcode(node)) {
591 entity * ent = get_Sel_entity(node);
592 if (is_method_type(get_entity_type(ent))) {
593 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
594 eset_insert(set, get_Sel_method(node, i));
600 /* nothing: SymConst points to extern method */
603 tarval * val = get_Const_tarval(node);
604 if (tarval_is_entity(val)) { /* filter null pointer */
605 entity * ent = tarval_to_entity(val);
606 if (is_method_type(get_entity_type(ent))) {
607 eset_insert(set, ent);
613 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
614 free_mark(get_Phi_pred(node, i), set);
618 free_mark(get_Id_pred(node), set);
621 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
624 /* nothing: Wird unten behandelt! */
627 set_irn_link(node, NULL);
631 static void free_ana_walker(ir_node * node, eset * set) {
633 if (get_irn_link(node) == MARK) {
634 /* bereits in einem Zyklus besucht. */
637 switch (intern_get_irn_opcode(node)) {
648 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
651 set_irn_link(node, MARK);
652 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
653 ir_node * pred = get_Call_param(node, i);
654 if (mode_is_reference(intern_get_irn_mode(pred))) {
655 free_mark(pred, set);
659 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
660 * jemand das Gegenteil implementiert. */
662 set_irn_link(node, MARK);
663 for (i = intern_get_irn_arity(node) - 1; i >= 0; --i) {
664 ir_node * pred = get_irn_n(node, i);
665 if (mode_is_reference(intern_get_irn_mode(pred))) {
666 free_mark(pred, set);
671 set_irn_link(node, NULL);
675 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
676 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
677 * SymConst-Operationen müssen in passende Const-Operationen
678 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
679 * auf eine echt externe Methode. */
680 static entity ** get_free_methods(void) {
681 eset * set = eset_create();
683 entity ** arr = NEW_ARR_F(entity *, 0);
686 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
687 ir_graph * irg = get_irp_irg(i);
688 entity * ent = get_irg_ent(irg);
689 /* insert "external visible" methods. */
690 if (get_entity_visibility(ent) != visibility_local) {
691 eset_insert(set, ent);
693 /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
694 z.B. da die Adresse einer Methode abgespeichert wird. */
695 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
697 /* Hauptprogramm ist auch dann frei, wenn es nicht "external
699 if (get_irp_main_irg()) {
700 eset_insert(set, get_irg_ent(get_irp_main_irg()));
702 /* Wandle Menge in Feld um. Effizienter. */
703 for (ent = eset_first(set); ent; ent = eset_next(set)) {
704 ARR_APP1(entity *, arr, ent);
711 void cgana(int *length, entity ***free_methods) {
712 entity ** free_meths;
716 free_meths = get_free_methods();
718 sel_methods_dispose();
720 /* Convert the flexible array to an array that can be handled
722 *length = ARR_LEN(free_meths);
723 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
724 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
725 DEL_ARR_F(free_meths);
728 /* Optimize the address expressions passed to call nodes.
729 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
730 * werden durch Const-Operationen ersetzt.
731 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
732 * durch Const ersetzt.
733 * Sel Knoten, fuer die keine Implementierung existiert, werden
734 * durch Bad ersetzt. */
735 void opt_call_addrs(void) {
737 sel_methods_dispose();
740 pmap * ldname_map = pmap_create();
741 assert(entities == NULL);
742 entities = eset_create();
743 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
744 entity * ent = get_irg_ent(get_irp_irg(i));
745 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
746 * aufgerufen werden. */
747 if (get_entity_visibility(ent) != local) {
748 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
751 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
752 pmap_destroy(ldname_map);