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 Aufrufrelation. Es
15 * wird eine Menge von freien Methoden und anschließend die an den
16 * Call-Operationen aufrufbaren Methoden bestimmt.
38 #include "dbginfo_t.h"
40 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
41 * Darstellung der unbekannten Methode. */
42 static void * MARK = &MARK;
46 /* --- sel methods ---------------------------------------------------------- */
49 static eset * entities = NULL;
52 /* Bestimmt die eindeutige Methode, die die Methode für den
53 * übergebenene (dynamischen) Typ überschreibt. */
54 entity * get_implementation(type * class, entity * method) {
56 if (get_entity_peculiarity(method) != peculiarity_description &&
57 get_entity_owner(method) == class) {
60 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
61 entity * e = get_entity_overwrittenby(method, i);
62 if (get_entity_peculiarity(e) != peculiarity_description && get_entity_owner(e) == class) {
66 for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
67 entity * e = get_implementation(get_class_supertype(class, i), method);
72 assert(0 && "implementation not found");
76 /* Returns the entity that contains the implementation of the inherited
77 entity if available, else returns the entity passed. */
78 entity *get_inherited_methods_implementation(entity *inh_meth) {
79 entity *impl_meth = NULL;
80 ir_node *addr = get_atomic_ent_value(inh_meth);
81 assert(addr && "constant entity without value");
83 if (get_irn_op(addr) == op_Const) {
84 impl_meth = tarval_to_entity(get_Const_tarval(addr));
86 assert(0 && "Complex constant values not supported -- address of method should be straight constant!");
88 if (impl_meth && (get_entity_peculiarity(impl_meth) != peculiarity_existent)) {
89 printf("this_meth: "); DDMEO(inh_meth);
90 printf("impl meth: "); DDMEO(impl_meth);
91 assert(!impl_meth || get_entity_peculiarity(impl_meth) == peculiarity_existent);
93 return impl_meth? impl_meth : inh_meth;
97 /* Collect the entity representing the implementation of this
98 entity (not the same if inherited) and all entities for overwriting
99 implementations in "set".
100 If the implementation of the method is not included in the
101 compilation unit "open" is set to true.
102 A recursive descend in the overwritten relation.
103 Cycle-free, therefore must terminate. */
104 void collect_impls(entity *method, eset *set, int *size, bool *open) {
106 if (get_entity_peculiarity(method) == peculiarity_existent) {
107 if (get_entity_visibility(method) == visibility_external_allocated) {
108 assert(get_entity_irg(method) == NULL);
111 assert(get_entity_irg(method) != NULL);
112 if (!eset_contains(set, method)) {
113 eset_insert(set, method);
118 if (get_entity_peculiarity(method) == peculiarity_inherited) {
119 entity *impl_ent = get_inherited_methods_implementation(method);
120 assert(impl_ent && "no implementation for inherited entity");
121 if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
122 assert(get_entity_irg(impl_ent) == NULL);
125 assert(get_entity_irg(impl_ent) != NULL);
126 if (!eset_contains(set, impl_ent)) {
127 eset_insert(set, impl_ent);
132 /** recursive descend **/
133 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
134 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
138 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
139 * (und implementieren). In der zurückgegebenen Reihung kommt jede
140 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
141 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
142 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
143 * keine Methoden, die die "method" überschreiben, so gibt die Methode
145 static entity ** get_impl_methods(entity * method) {
146 eset * set = eset_create();
151 /** Collect all method entities that can be called here **/
152 collect_impls(method, set, &size, &open);
155 Vorgaenger einfuegen. **/
156 if (size == 0 && !open) {
157 /* keine implementierte überschriebene Methode */
161 arr = NEW_ARR_F(entity *, size + 1);
162 arr[0] = NULL; /* Represents open method */
163 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
167 arr = NEW_ARR_F(entity *, size);
168 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
176 /* debug makros used in sel_methods_walker */
177 #define SIZ(x) sizeof(x)/sizeof((x)[0])
179 #define DBG_OPT_NORMALIZE \
180 __dbg_info_merge_pair(new_node, node, dbg_const_eval)
181 #define DBG_OPT_POLY_ALLOC \
185 ons[1] = skip_Proj(get_Sel_ptr(node)); \
186 __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
188 #define DBG_OPT_POLY \
189 __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
192 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
193 if (get_irn_op(node) == op_SymConst) {
194 /* Wenn möglich SymConst-Operation durch Const-Operation
196 if (get_SymConst_kind(node) == linkage_ptr_info) {
197 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
198 if (entry != NULL) { /* Method is declared in the compiled code */
199 entity * ent = entry->value;
200 if (get_opt_normalize() && (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
202 assert(get_entity_irg(ent));
203 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
204 new_node = new_d_Const(get_irn_dbg_info(node),
205 mode_P_mach, new_tarval_from_entity(ent, mode_P_mach)); DBG_OPT_NORMALIZE;
206 exchange(node, new_node);
210 } else if (get_irn_op(node) == op_Sel &&
211 is_method_type(get_entity_type(get_Sel_entity(node)))) {
212 entity * ent = get_Sel_entity(node);
213 if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
214 (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
217 /* We know which method will be called, no dispatch necessary. */
219 assert(get_entity_peculiarity(ent) != peculiarity_description);
220 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
221 /* @@@ Is this correct?? Alloc could reference a subtype of the owner
222 of Sel that overwrites the method referenced in Sel. */
223 /* @@@ Yes, this is wrong. GL, 10.3.04 */
224 new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC;
226 called_ent = resolve_ent_polymorphy(get_Alloc_type(skip_Proj(get_Sel_ptr(node))), ent);
227 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
228 /* called_ent may not be description: has no Address/Const to Call! */
229 assert(get_entity_peculiarity(called_ent) != peculiarity_description);
230 new_node = copy_const_value(get_atomic_ent_value(called_ent)); DBG_OPT_POLY_ALLOC;
232 exchange (node, new_node);
234 assert(get_entity_peculiarity(ent) != peculiarity_inherited);
235 if (!eset_contains(entities, ent)) {
236 /* Entity noch nicht behandelt. Alle (intern oder extern)
237 * implementierten Methoden suchen, die diese Entity
238 * überschreiben. Die Menge an entity.link speichern. */
239 set_entity_link(ent, get_impl_methods(ent));
240 eset_insert(entities, ent);
242 if (get_entity_link(ent) == NULL) {
243 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
244 * Methode zurückgeben. Damit ist sie insbesondere nicht
245 * ausführbar und nicht erreichbar. */
246 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
247 fuer die es keine Implementierung gibt. */
248 if (get_entity_peculiarity(ent) == peculiarity_description) {
249 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
250 printf("WARNING: Calling method description %s\n in method %s\n of class %s\n which has "
251 "no implementation!\n", get_entity_name(ent),
252 get_entity_name(get_irg_ent(current_ir_graph)),
253 get_type_name(get_entity_owner(get_irg_ent(current_ir_graph))));
254 printf("This happens when compiling a Java Interface that's never really used, i.e., "
255 "no class implementing the interface is ever used.\n");
257 exchange(node, new_Bad());
260 entity ** arr = get_entity_link(ent);
264 printf("\nCall site "); DDMN(node);
265 printf(" in "); DDME(get_irg_ent(current_ir_graph));
266 printf(" can call:\n");
267 for (i = 0; i < ARR_LEN(arr); i++) {
268 printf(" - "); DDME(arr[i]);
269 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
274 if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
275 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
277 /* Die Sel-Operation kann immer nur einen Wert auf eine
278 * interne Methode zurückgeben. Wir können daher die
279 * Sel-Operation durch eine Const- bzw. SymConst-Operation
281 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
282 new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY;
283 exchange (node, new_node);
291 /* Datenstruktur initialisieren. Zusätzlich werden alle
292 * SymConst-Operationen, die auf interne Methoden verweisen, durch
293 * Const-Operationen ersetzt. */
294 static void sel_methods_init(void) {
296 pmap * ldname_map = pmap_create();
297 assert(entities == NULL);
298 entities = eset_create();
299 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
300 entity * ent = get_irg_ent(get_irp_irg(i));
301 /* Nur extern sichtbare Methode können überhaupt mit SymConst
302 * aufgerufen werden. */
303 if (get_entity_visibility(ent) != visibility_local) {
304 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
307 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
308 pmap_destroy(ldname_map);
311 /*****************************************************************************/
313 /* Datenstruktur freigeben. */
314 static void sel_methods_dispose(void) {
317 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
318 entity ** arr = get_entity_link(ent);
322 set_entity_link(ent, NULL);
324 eset_destroy(entities);
329 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
330 * zurückgegeben werden können. Die Liste enthält keine doppelten
332 static entity ** get_Sel_arr(ir_node * sel) {
333 static entity ** NULL_ARRAY = NULL;
336 assert(sel && get_irn_op(sel) == op_Sel);
337 ent = get_Sel_entity(sel);
338 assert(is_method_type(get_entity_type(ent))); /* what else? */
339 arr = get_entity_link(ent);
343 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
344 * kann für polymorphe (abstrakte) Methoden passieren. */
346 NULL_ARRAY = NEW_ARR_F(entity *, 0);
353 static int get_Sel_n_methods(ir_node * sel) {
354 return ARR_LEN(get_Sel_arr(sel));
358 static entity * get_Sel_method(ir_node * sel, int pos) {
359 entity ** arr = get_Sel_arr(sel);
360 assert(pos >= 0 && pos < ARR_LEN(arr));
366 /* --- callee analysis ------------------------------------------------------ */
369 static void callee_ana_node(ir_node * node, eset * methods);
372 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
373 assert(get_irn_mode(node) == mode_T);
374 if (get_irn_link(node) == MARK) {
375 /* already visited */
378 set_irn_link(node, MARK);
380 switch (get_irn_opcode(node)) {
382 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
383 * op_Tuple oder ein Knoten, der eine "freie Methode"
385 ir_node * pred = get_Proj_pred(node);
386 if (get_irn_link(pred) != MARK) {
387 if (get_irn_op(pred) == op_Tuple) {
388 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
390 eset_insert(methods, MARK); /* free method -> unknown */
397 callee_ana_node(get_Tuple_pred(node, n), methods);
401 callee_ana_proj(get_Id_pred(node), n, methods);
405 eset_insert(methods, MARK); /* free method -> unknown */
409 set_irn_link(node, NULL);
413 static void callee_ana_node(ir_node * node, eset * methods) {
416 assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
417 /* rekursion verhindern */
418 if (get_irn_link(node) == MARK) {
419 /* already visited */
422 set_irn_link(node, MARK);
424 switch (get_irn_opcode(node)) {
426 /* externe Methode (wegen fix_symconst!) */
427 eset_insert(methods, MARK); /* free method -> unknown */
431 /* interne Methode */
432 entity * ent = tarval_to_entity(get_Const_tarval(node));
433 assert(ent && is_method_type(get_entity_type(ent)));
434 if (get_entity_visibility(ent) != visibility_external_allocated) {
435 assert(get_entity_irg(ent));
436 eset_insert(methods, ent);
438 eset_insert(methods, MARK); /* free method -> unknown */
444 /* polymorphe Methode */
445 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
446 entity * ent = get_Sel_method(node, i);
448 eset_insert(methods, ent);
450 eset_insert(methods, MARK);
459 case iro_Phi: /* Vereinigung */
460 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
461 callee_ana_node(get_Phi_pred(node, i), methods);
466 callee_ana_node(get_Id_pred(node), methods);
470 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
477 eset_insert(methods, MARK); /* free method -> unknown */
481 assert(0 && "invalid opcode or opcode not implemented");
485 set_irn_link(node, NULL);
489 static void callee_walker(ir_node * call, void * env) {
490 if (get_irn_op(call) == op_Call) {
491 eset * methods = eset_create();
493 entity ** arr = NEW_ARR_F(entity *, 0);
494 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
495 if (eset_contains(methods, MARK)) { /* unknown method */
496 ARR_APP1(entity *, arr, NULL);
498 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
500 ARR_APP1(entity *, arr, ent);
503 if (ARR_LEN(arr) == 0) {
504 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
505 * Sel-Operation war, die keine Methoden zurückgeben
506 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
507 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
509 /* exchange(call, new_Bad()); invalid firm */
511 ir_node *mem = get_Call_mem(call);
512 turn_into_tuple (call, pn_Call_max);
513 set_Tuple_pred(call, pn_Call_M_regular , mem);
514 set_Tuple_pred(call, pn_Call_T_result , new_Bad());
515 set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
516 set_Tuple_pred(call, pn_Call_X_except , new_Bad()); /* new_Jmp() ?? new_Raise() ?? */
517 set_Tuple_pred(call, pn_Call_M_except , mem);
520 set_Call_callee_arr(call, ARR_LEN(arr), arr);
523 eset_destroy(methods);
528 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
529 * und speichert das Ergebnis in der Call-Operation. (siehe
530 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
531 * muss bereits aufgebaut sein. */
532 static void callee_ana(void) {
534 /* Alle Graphen analysieren. */
535 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
536 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
537 set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
543 /* --- free method analysis ------------------------------------------------- */
546 static void free_mark(ir_node * node, eset * set);
548 static void free_mark_proj(ir_node * node, long n, eset * set) {
549 assert(get_irn_mode(node) == mode_T);
550 if (get_irn_link(node) == MARK) {
551 /* already visited */
554 set_irn_link(node, MARK);
555 switch (get_irn_opcode(node)) {
557 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
558 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
560 ir_node * pred = get_Proj_pred(node);
561 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
562 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
564 /* nothing: da in "free_ana_walker" behandelt. */
570 free_mark(get_Tuple_pred(node, n), set);
574 free_mark_proj(get_Id_pred(node), n, set);
580 /* nothing: Die Operationen werden in "free_ana_walker" selbst
585 assert(0 && "unexpected opcode or opcode not implemented");
588 set_irn_link(node, NULL);
592 static void free_mark(ir_node * node, eset * set) {
594 assert(mode_is_reference(get_irn_mode(node)));
595 if (get_irn_link(node) == MARK) {
596 return; /* already visited */
598 set_irn_link(node, MARK);
599 switch (get_irn_opcode(node)) {
601 entity * ent = get_Sel_entity(node);
602 if (is_method_type(get_entity_type(ent))) {
603 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
604 eset_insert(set, get_Sel_method(node, i));
610 /* nothing: SymConst points to extern method */
613 tarval * val = get_Const_tarval(node);
614 if (tarval_is_entity(val)) { /* filter null pointer */
615 entity * ent = tarval_to_entity(val);
616 if (is_method_type(get_entity_type(ent))) {
617 eset_insert(set, ent);
623 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
624 free_mark(get_Phi_pred(node, i), set);
628 free_mark(get_Id_pred(node), set);
631 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
634 /* nothing: Wird unten behandelt! */
637 set_irn_link(node, NULL);
641 static void free_ana_walker(ir_node * node, eset * set) {
643 if (get_irn_link(node) == MARK) {
644 /* bereits in einem Zyklus besucht. */
647 switch (get_irn_opcode(node)) {
658 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
661 set_irn_link(node, MARK);
662 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
663 ir_node * pred = get_Call_param(node, i);
664 if (mode_is_reference(get_irn_mode(pred))) {
665 free_mark(pred, set);
669 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
670 * jemand das Gegenteil implementiert. */
672 set_irn_link(node, MARK);
673 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
674 ir_node * pred = get_irn_n(node, i);
675 if (mode_is_reference(get_irn_mode(pred))) {
676 free_mark(pred, set);
681 set_irn_link(node, NULL);
685 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
686 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
687 * SymConst-Operationen müssen in passende Const-Operationen
688 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
689 * auf eine echt externe Methode. */
690 static entity ** get_free_methods(void) {
691 eset * set = eset_create();
693 entity ** arr = NEW_ARR_F(entity *, 0);
696 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
697 ir_graph * irg = get_irp_irg(i);
698 entity * ent = get_irg_ent(irg);
699 /* insert "external visible" methods. */
700 if (get_entity_visibility(ent) != visibility_local) {
701 eset_insert(set, ent);
703 /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
704 z.B. da die Adresse einer Methode abgespeichert wird. */
705 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
707 /* Hauptprogramm ist auch dann frei, wenn es nicht "external
709 if (get_irp_main_irg()) {
710 eset_insert(set, get_irg_ent(get_irp_main_irg()));
712 /* Wandle Menge in Feld um. Effizienter. */
713 for (ent = eset_first(set); ent; ent = eset_next(set)) {
714 ARR_APP1(entity *, arr, ent);
721 void cgana(int *length, entity ***free_methods) {
722 entity ** free_meths;
726 free_meths = get_free_methods();
728 sel_methods_dispose();
730 /* Convert the flexible array to an array that can be handled
732 *length = ARR_LEN(free_meths);
733 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
734 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
735 DEL_ARR_F(free_meths);
738 /* Optimize the address expressions passed to call nodes.
739 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
740 * werden durch Const-Operationen ersetzt.
741 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
742 * durch Const ersetzt.
743 * Sel Knoten, fuer die keine Implementierung existiert, werden
744 * durch Bad ersetzt. */
745 void opt_call_addrs(void) {
747 sel_methods_dispose();
750 pmap * ldname_map = pmap_create();
751 assert(entities == NULL);
752 entities = eset_create();
753 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
754 entity * ent = get_irg_ent(get_irp_irg(i));
755 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
756 * aufgerufen werden. */
757 if (get_entity_visibility(ent) != local) {
758 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
761 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
762 pmap_destroy(ldname_map);