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 (intern_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 (intern_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 (intern_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 (intern_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 && intern_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 (intern_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 (intern_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 (intern_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 (intern_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());
511 set_Call_callee_arr(call, ARR_LEN(arr), arr);
514 eset_destroy(methods);
519 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
520 * und speichert das Ergebnis in der Call-Operation. (siehe
521 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
522 * muss bereits aufgebaut sein. */
523 static void callee_ana(void) {
525 /* Alle Graphen analysieren. */
526 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
527 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
528 set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
534 /* --- free method analysis ------------------------------------------------- */
537 static void free_mark(ir_node * node, eset * set);
539 static void free_mark_proj(ir_node * node, long n, eset * set) {
540 assert(get_irn_mode(node) == mode_T);
541 if (get_irn_link(node) == MARK) {
542 /* already visited */
545 set_irn_link(node, MARK);
546 switch (intern_get_irn_opcode(node)) {
548 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
549 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
551 ir_node * pred = get_Proj_pred(node);
552 if (get_irn_link(pred) != MARK && intern_get_irn_op(pred) == op_Tuple) {
553 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
555 /* nothing: da in "free_ana_walker" behandelt. */
561 free_mark(get_Tuple_pred(node, n), set);
565 free_mark_proj(get_Id_pred(node), n, set);
571 /* nothing: Die Operationen werden in "free_ana_walker" selbst
576 assert(0 && "unexpected opcode or opcode not implemented");
579 set_irn_link(node, NULL);
583 static void free_mark(ir_node * node, eset * set) {
585 assert(mode_is_reference(get_irn_mode(node)));
586 if (get_irn_link(node) == MARK) {
587 return; /* already visited */
589 set_irn_link(node, MARK);
590 switch (intern_get_irn_opcode(node)) {
592 entity * ent = get_Sel_entity(node);
593 if (is_method_type(get_entity_type(ent))) {
594 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
595 eset_insert(set, get_Sel_method(node, i));
601 /* nothing: SymConst points to extern method */
604 tarval * val = get_Const_tarval(node);
605 if (tarval_is_entity(val)) { /* filter null pointer */
606 entity * ent = tarval_to_entity(val);
607 if (is_method_type(get_entity_type(ent))) {
608 eset_insert(set, ent);
614 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
615 free_mark(get_Phi_pred(node, i), set);
619 free_mark(get_Id_pred(node), set);
622 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
625 /* nothing: Wird unten behandelt! */
628 set_irn_link(node, NULL);
632 static void free_ana_walker(ir_node * node, eset * set) {
634 if (get_irn_link(node) == MARK) {
635 /* bereits in einem Zyklus besucht. */
638 switch (intern_get_irn_opcode(node)) {
649 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
652 set_irn_link(node, MARK);
653 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
654 ir_node * pred = get_Call_param(node, i);
655 if (mode_is_reference(intern_get_irn_mode(pred))) {
656 free_mark(pred, set);
660 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
661 * jemand das Gegenteil implementiert. */
663 set_irn_link(node, MARK);
664 for (i = intern_get_irn_arity(node) - 1; i >= 0; --i) {
665 ir_node * pred = get_irn_n(node, i);
666 if (mode_is_reference(intern_get_irn_mode(pred))) {
667 free_mark(pred, set);
672 set_irn_link(node, NULL);
676 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
677 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
678 * SymConst-Operationen müssen in passende Const-Operationen
679 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
680 * auf eine echt externe Methode. */
681 static entity ** get_free_methods(void) {
682 eset * set = eset_create();
684 entity ** arr = NEW_ARR_F(entity *, 0);
687 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
688 ir_graph * irg = get_irp_irg(i);
689 entity * ent = get_irg_ent(irg);
690 /* insert "external visible" methods. */
691 if (get_entity_visibility(ent) != visibility_local) {
692 eset_insert(set, ent);
694 /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
695 z.B. da die Adresse einer Methode abgespeichert wird. */
696 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
698 /* Hauptprogramm ist auch dann frei, wenn es nicht "external
700 if (get_irp_main_irg()) {
701 eset_insert(set, get_irg_ent(get_irp_main_irg()));
703 /* Wandle Menge in Feld um. Effizienter. */
704 for (ent = eset_first(set); ent; ent = eset_next(set)) {
705 ARR_APP1(entity *, arr, ent);
712 void cgana(int *length, entity ***free_methods) {
713 entity ** free_meths;
720 free_meths = get_free_methods();
722 sel_methods_dispose();
724 /* Convert the flexible array to an array that can be handled
726 *length = ARR_LEN(free_meths);
727 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
728 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
729 DEL_ARR_F(free_meths);
732 /* Optimize the address expressions passed to call nodes.
733 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
734 * werden durch Const-Operationen ersetzt.
735 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
736 * durch Const ersetzt.
737 * Sel Knoten, fuer die keine Implementierung existiert, werden
738 * durch Bad ersetzt. */
739 void opt_call_addrs(void) {
741 sel_methods_dispose();
744 pmap * ldname_map = pmap_create();
745 assert(entities == NULL);
746 entities = eset_create();
747 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
748 entity * ent = get_irg_ent(get_irp_irg(i));
749 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
750 * aufgerufen werden. */
751 if (get_entity_visibility(ent) != local) {
752 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
755 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
756 pmap_destroy(ldname_map);