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.
15 * Interprocedural analysis to estimate the calling relation.
17 * This analysis computes all entities representing methods that
18 * can be called at a Call node. Further it computes a set of
19 * methods that are 'free', i.e., their adress is handled by
20 * the program directly, or they are visible external.
44 #include "dbginfo_t.h"
45 #include "iropt_dbg.h"
57 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
58 * Darstellung der unbekannten Methode. */
59 static void *MARK = &MARK;
61 static eset *entities = NULL;
63 /*--------------------------------------------------------------------------*/
65 /*--------------------------------------------------------------------------*/
68 /*--------------------------------------------------------------------------*/
69 /* Initialize datastructures, remove unwanted constructs, optimize */
70 /* call target computations. */
71 /*--------------------------------------------------------------------------*/
73 /** Returns the entity that contains the implementation of the inherited
74 entity if available, else returns the entity passed. */
75 static entity *get_inherited_methods_implementation(entity *inh_meth) {
76 assert(get_atomic_ent_value(inh_meth) && "constant entity without value");
77 assert((get_irn_op(get_atomic_ent_value(inh_meth)) == op_SymConst) &&
78 (get_SymConst_kind(get_atomic_ent_value(inh_meth)) == symconst_addr_ent) &&
79 "Complex constant values not supported -- address of method should be straight constant!");
81 return get_SymConst_entity(get_atomic_ent_value(inh_meth));
84 /** Collect the entity representing the implementation of this
85 * entity (not the same if inherited) and all entities for overwriting
86 * implementations in "set".
87 * If the implementation of the method is not included in the
88 * compilation unit "open" is set to true.
89 * A recursive descend in the overwritten relation.
90 * Cycle-free, therefore must terminate.
93 * @param set A set of entities.
94 * @param size Number of entities in set.
97 static void collect_impls(entity *method, eset *set, int *size, bool *open) {
101 /* Only the assertions: */
102 if (get_entity_peculiarity(method) == peculiarity_existent) {
103 if ((get_entity_visibility(method) == visibility_external_allocated)
104 && (NULL == get_entity_irg(method))) {
106 assert(get_entity_irg(method) != NULL);
109 if (get_entity_peculiarity(method) == peculiarity_inherited) {
110 entity *impl_ent = get_inherited_methods_implementation(method);
111 if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
112 assert(get_entity_irg(impl_ent) == NULL);
114 assert(get_entity_irg(impl_ent) != NULL);
118 /* Add the implementation to the set if it contains an irg, else
119 remember that there are more methods called. */
120 /* @@@ We could also add unknown_entity, or the entities with the
121 unknown irgs. The first case would result in the exact same
122 behavior: all unknown irgs are represented by the one and only
123 unknown entity. If we add all entities, we known the number of
124 entities possibly called, and whether there are real unknown
125 entities, i.e, such not represented in the type description.
126 This would be better for an analysis: it could rule out more
129 if (get_entity_peculiarity(method) == peculiarity_inherited)
130 impl = get_inherited_methods_implementation(method);
132 if (get_entity_peculiarity(method) != peculiarity_description) {
133 //if (get_entity_irg(impl)) {
134 eset_insert(set, impl);
137 /* GL: better: eset_insert(set, unknown_entity); */
142 /*- recursive descent -*/
143 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
144 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
147 /** Alle Methoden bestimmen, die die übergebene Methode überschreiben
148 * (und implementieren). In der zurückgegebenen Reihung kommt jede
149 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
150 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
151 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
152 * keine Methoden, die "method" überschreiben, so gibt die Methode
157 static entity ** get_impl_methods(entity * method) {
158 eset * set = eset_create();
163 /* Collect all method entities that can be called here */
164 collect_impls(method, set, &size, &open);
166 /* Vorgaenger einfuegen. */
167 if (size == 0 && !open) {
168 /* keine implementierte überschriebene Methode */
172 arr = NEW_ARR_F(entity *, size + 1);
173 arr[0] = NULL; /* Represents open method */
174 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
178 arr = NEW_ARR_F(entity *, size);
179 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
186 /** Analyze address computations.
188 * Compute for all Sel nodes the set of methods that can be selected.
190 * Further do some optimizations:
191 * - Call standard optimizations for Sel nodes: this removes polymorphic
193 * - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
194 * For this we precomputed a map name->entity.
195 * - If the node is a Sel:
196 * If we found only a single method that can be called, replace the Sel
197 * by a SymConst. This is more powerful than the analysis in opt_polymorphy,
198 * as here we walk the typegraph. In opt_polymorphy we only apply a local
201 * @param node The node to analyze
202 * @param env A map that maps names of entities to the entities.
204 static void sel_methods_walker(ir_node * node, void *env) {
205 pmap *ldname_map = env;
207 if (get_irn_op(node) == op_Sel) {
208 ir_node *new_node = optimize_in_place(node);
209 if (node != new_node) exchange(node, new_node);
212 /* replace SymConst(name)-operations by SymConst(ent) */
213 if (get_irn_op(node) == op_SymConst) {
214 if (get_SymConst_kind(node) == symconst_addr_name) {
215 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
216 if (entry != NULL) { /* Method is declared in the compiled code */
217 assert(0 && "There should not be a SymConst[addr_name] addressing a method with an implementation"
218 "in this compilation unit. Use a SymConst[addr_ent].");
220 entity * ent = entry->value;
221 if (get_opt_normalize() &&
222 (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
225 set_irg_current_block(current_ir_graph, get_nodes_block(node));
226 new_node = copy_const_value(get_atomic_ent_value(ent));
228 DBG_OPT_CSTEVAL(node, new_node);
230 assert(get_entity_irg(ent));
232 exchange(node, new_node);
238 else if (get_irn_op(node) == op_Sel &&
239 is_Method_type(get_entity_type(get_Sel_entity(node)))) {
240 entity * ent = get_Sel_entity(node);
241 assert(get_entity_peculiarity(ent) != peculiarity_inherited);
243 if (!eset_contains(entities, ent)) {
244 /* Entity noch nicht behandelt. Alle (intern oder extern)
245 * implementierten Methoden suchen, die diese Entity
246 * überschreiben. Die Menge an entity.link speichern. */
247 set_entity_link(ent, get_impl_methods(ent));
248 eset_insert(entities, ent);
251 /* -- As an add on we get an optimization that removes polymorphic calls.
252 This optimization is more powerful than that in transform_node_Sel. -- */
253 if (get_entity_link(ent) == NULL) {
254 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
255 * Methode zurückgeben. Damit ist sie insbesondere nicht
256 * ausführbar und nicht erreichbar. */
257 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
258 fuer die es keine Implementierung gibt. */
259 if (get_entity_peculiarity(ent) == peculiarity_description) {
260 /* This is possible: We call a method in a dead part of the program. */
263 assert(0); /* Why should this happen ??? */
264 //exchange(node, new_Bad());
267 entity ** arr = get_entity_link(ent);
268 if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
269 (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
271 /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
272 * interne Methode zurückgeben. Wir können daher die
273 * Sel-Operation durch eine Const- bzw. SymConst-Operation
275 set_irg_current_block(current_ir_graph, get_nodes_block(node));
276 assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
277 peculiarity_existent);
278 new_node = copy_const_value(get_atomic_ent_value(arr[0]));
279 DBG_OPT_POLY(node, new_node);
280 exchange (node, new_node);
286 /** Datenstruktur initialisieren. Zusätzlich werden alle
287 * SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
288 * SymConst(entity)-Operationen ersetzt. */
289 static void sel_methods_init(void) {
291 pmap * ldname_map = pmap_create(); /* Map entity names to entities: to replace
292 SymConst(name) by SymConst(ent). */
293 assert(entities == NULL);
294 entities = eset_create();
295 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
296 entity * ent = get_irg_entity(get_irp_irg(i));
297 /* Nur extern sichtbare Methoden können überhaupt mit SymConst_ptr_name
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(sel_methods_walker, NULL, ldname_map);
304 pmap_destroy(ldname_map);
307 /*--------------------------------------------------------------------------*/
308 /* Find free methods.
310 * We expect that each entity has an array with all implementations in its
312 /*--------------------------------------------------------------------------*/
315 * Returns an array of all methods that could be called at a Sel node.
316 * This array contains every entry only once.
318 static entity ** get_Sel_arr(ir_node * sel) {
319 static entity ** NULL_ARRAY = NULL;
323 assert(sel && get_irn_op(sel) == op_Sel);
324 ent = get_Sel_entity(sel);
325 assert(is_Method_type(get_entity_type(ent))); /* what else? */
326 arr = get_entity_link(ent);
330 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
331 * kann für polymorphe (abstrakte) Methoden passieren. */
333 NULL_ARRAY = NEW_ARR_F(entity *, 0);
340 * Returns the number of possible called methods at a Sel node.
342 static int get_Sel_n_methods(ir_node * sel) {
343 return ARR_LEN(get_Sel_arr(sel));
347 * Returns the ith possible called method entity at a Sel node.
349 static entity * get_Sel_method(ir_node * sel, int pos) {
350 entity ** arr = get_Sel_arr(sel);
351 assert(pos >= 0 && pos < ARR_LEN(arr));
355 static void free_mark(ir_node * node, eset * set);
357 static void free_mark_proj(ir_node * node, long n, eset * set) {
358 assert(get_irn_mode(node) == mode_T);
359 if (get_irn_link(node) == MARK) {
360 /* already visited */
363 set_irn_link(node, MARK);
364 switch (get_irn_opcode(node)) {
366 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
367 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
369 ir_node * pred = get_Proj_pred(node);
370 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
371 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
373 /* nothing: da in "free_ana_walker" behandelt. */
379 free_mark(get_Tuple_pred(node, n), set);
383 free_mark_proj(get_Id_pred(node), n, set);
389 /* nothing: Die Operationen werden in "free_ana_walker" selbst
394 assert(0 && "unexpected opcode or opcode not implemented");
397 set_irn_link(node, NULL);
401 static void free_mark(ir_node * node, eset * set) {
404 if (get_irn_link(node) == MARK) {
405 return; /* already visited */
407 set_irn_link(node, MARK);
408 switch (get_irn_opcode(node)) {
410 entity * ent = get_Sel_entity(node);
411 if (is_Method_type(get_entity_type(ent))) {
412 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
413 eset_insert(set, get_Sel_method(node, i));
419 if (get_SymConst_kind(node) == symconst_addr_ent) {
420 entity * ent = get_SymConst_entity(node);
421 if (is_Method_type(get_entity_type(ent))) {
422 eset_insert(set, ent);
425 assert(get_SymConst_kind(node) == symconst_addr_name);
426 /* nothing: SymConst points to extern method */
431 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
432 free_mark(get_Phi_pred(node, i), set);
436 free_mark(get_Id_pred(node), set);
439 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
442 /* nothing: Wird unten behandelt! */
445 set_irn_link(node, NULL);
449 static void free_ana_walker(ir_node * node, eset * set) {
451 if (get_irn_link(node) == MARK) {
452 /* bereits in einem Zyklus besucht. */
455 switch (get_irn_opcode(node)) {
466 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
469 set_irn_link(node, MARK);
470 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
471 ir_node * pred = get_Call_param(node, i);
472 if (mode_is_reference(get_irn_mode(pred))) {
473 free_mark(pred, set);
477 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
478 * jemand das Gegenteil implementiert. */
480 set_irn_link(node, MARK);
481 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
482 ir_node * pred = get_irn_n(node, i);
483 if (mode_is_reference(get_irn_mode(pred))) {
484 free_mark(pred, set);
489 set_irn_link(node, NULL);
492 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
493 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
494 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
495 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
496 * auf eine echt externe Methode. */
497 static entity ** get_free_methods(void)
499 eset * set = eset_create();
501 entity ** arr = NEW_ARR_F(entity *, 0);
504 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
505 ir_graph * irg = get_irp_irg(i);
506 entity * ent = get_irg_entity(irg);
507 /* insert "external visible" methods. */
508 if (get_entity_visibility(ent) != visibility_local) {
509 eset_insert(set, ent);
511 /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
512 z.B. da die Adresse einer Methode abgespeichert wird. */
513 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
516 /* insert sticky methods, too */
517 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
518 entity * ent = get_irg_entity(get_irp_irg(i));
519 /* insert "external visible" methods. */
520 if (get_entity_stickyness (ent) == stickyness_sticky) {
521 eset_insert(set, ent);
525 /* Hauptprogramm ist auch dann frei, wenn es nicht "external
527 if (get_irp_main_irg()) {
528 eset_insert(set, get_irg_entity(get_irp_main_irg()));
530 /* Wandle Menge in Feld um. Effizienter. */
531 for (ent = eset_first(set); ent; ent = eset_next(set)) {
532 ARR_APP1(entity *, arr, ent);
539 /*--------------------------------------------------------------------------*/
540 /* Callee analysis. */
541 /*--------------------------------------------------------------------------*/
543 static void callee_ana_node(ir_node * node, eset * methods);
545 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
546 assert(get_irn_mode(node) == mode_T);
547 if (get_irn_link(node) == MARK) {
548 /* already visited */
551 set_irn_link(node, MARK);
553 switch (get_irn_opcode(node)) {
555 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
556 * op_Tuple oder ein Knoten, der eine "freie Methode"
558 ir_node * pred = get_Proj_pred(node);
559 if (get_irn_link(pred) != MARK) {
560 if (get_irn_op(pred) == op_Tuple) {
561 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
563 eset_insert(methods, MARK); /* free method -> unknown */
570 callee_ana_node(get_Tuple_pred(node, n), methods);
574 callee_ana_proj(get_Id_pred(node), n, methods);
578 eset_insert(methods, MARK); /* free method -> unknown */
582 set_irn_link(node, NULL);
586 static void callee_ana_node(ir_node * node, eset * methods) {
589 assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
590 /* rekursion verhindern */
591 if (get_irn_link(node) == MARK) {
592 /* already visited */
595 set_irn_link(node, MARK);
597 switch (get_irn_opcode(node)) {
599 if (get_SymConst_kind(node) == symconst_addr_ent) {
600 entity * ent = get_SymConst_entity(node);
601 assert(ent && is_Method_type(get_entity_type(ent)));
602 eset_insert(methods, ent);
604 assert(get_SymConst_kind(node) == symconst_addr_name);
605 /* externe Methode (wegen fix_symconst!) */
606 eset_insert(methods, MARK); /* free method -> unknown */
610 /* polymorphe Methode */
611 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
612 entity * ent = get_Sel_method(node, i);
614 eset_insert(methods, ent);
616 eset_insert(methods, MARK);
625 case iro_Phi: /* Vereinigung */
626 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
627 callee_ana_node(get_Phi_pred(node, i), methods);
632 callee_ana_node(get_Mux_false(node), methods);
633 callee_ana_node(get_Mux_true(node), methods);
637 callee_ana_node(get_Id_pred(node), methods);
641 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
648 eset_insert(methods, MARK); /* free method -> unknown */
652 assert(0 && "invalid opcode or opcode not implemented");
656 set_irn_link(node, NULL);
660 static void callee_walker(ir_node * call, void * env) {
661 if (get_irn_op(call) == op_Call) {
662 eset * methods = eset_create();
664 entity ** arr = NEW_ARR_F(entity *, 0);
665 assert(get_irn_op(get_Call_ptr(call)) != op_Id);
666 callee_ana_node(get_Call_ptr(call), methods);
667 if (eset_contains(methods, MARK)) { /* unknown method */
668 ARR_APP1(entity *, arr, unknown_entity);
670 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
672 ARR_APP1(entity *, arr, ent);
675 #if 0 /* This generates Bad nodes when we don't want it.
676 Call it with a check for valid cgana information in local_optimize. */
677 if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
678 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
679 * Sel-Operation war, die keine Methoden zurückgeben
680 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
681 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
683 ir_node *mem = get_Call_mem(call);
684 turn_into_tuple (call, 5 /* pn_Call_max */);
685 set_Tuple_pred(call, pn_Call_M_regular , mem);
686 set_Tuple_pred(call, pn_Call_T_result , new_Bad());
687 set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
688 set_Tuple_pred(call, pn_Call_X_except , new_Bad()); /* new_Jmp() ?? new_Raise() ?? */
689 set_Tuple_pred(call, pn_Call_M_except , new_Bad());
694 /* remove, what we repaired. */
696 for (i = 0; i < ARR_LEN(arr); ++i) {
700 set_Call_callee_arr(call, ARR_LEN(arr), arr);
703 eset_destroy(methods);
708 static void remove_Tuples(ir_node * proj, void * env) {
710 if (get_irn_opcode(proj) != iro_Proj) return;
712 new = skip_Tuple(proj);
713 if (new != proj) exchange(proj, new);
717 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
718 * und speichert das Ergebnis in der Call-Operation. (siehe
719 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
720 * muss bereits aufgebaut sein. */
721 static void callee_ana(void) {
723 /* Alle Graphen analysieren. */
724 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
725 irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
726 set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
728 set_irp_callee_info_state(irg_callee_info_consistent);
731 /*--------------------------------------------------------------------------*/
732 /* Cleanup after analyses. */
733 /*--------------------------------------------------------------------------*/
735 /** Frees intermediate data structures. */
736 static void sel_methods_dispose(void) {
739 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
740 entity ** arr = get_entity_link(ent);
744 set_entity_link(ent, NULL);
746 eset_destroy(entities);
750 /*--------------------------------------------------------------------------*/
751 /* Freeing the callee arrays. */
752 /*--------------------------------------------------------------------------*/
754 static void destruct_walker(ir_node * node, void * env) {
755 if (get_irn_op(node) == op_Call) {
756 remove_Call_callee_arr(node);
760 /*--------------------------------------------------------------------------*/
762 /*--------------------------------------------------------------------------*/
764 void cgana(int *length, entity ***free_methods) {
765 entity ** free_meths, **p;
768 free_meths = get_free_methods();
770 sel_methods_dispose();
772 /* Convert the flexible array to an array that can be handled
774 p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
775 memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));
777 *length = ARR_LEN(free_meths);
780 DEL_ARR_F(free_meths);
783 void free_callee_info(ir_graph *irg) {
784 irg_walk_graph(irg, destruct_walker, NULL, NULL);
785 set_irg_callee_info_state(irg, irg_callee_info_none);
788 /* Optimize the address expressions passed to call nodes.
790 * This optimization performs the following transformations for
792 * - All SymConst operations that refer to intern methods are replaced
793 * by Const operations refering to the corresponding entity.
794 * - Sel nodes, that select entities that are not overwritten are
795 * replaced by Const nodes refering to the selected entity.
796 * - Sel nodes, for which no method exists at all are replaced by Bad
798 * - Sel nodes with a pointer input that is an Alloc node are replaced
799 * by Const nodes refering to the entity that implements the method in
800 * the type given by the Alloc node.
802 void opt_call_addrs(void) {
804 sel_methods_dispose();