2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Interprocedural analysis to improve the call graph estimate.
23 * @author Florian Liekweg
35 #include "irgraph_t.h"
48 # endif /* not defined TRUE */
50 /** The debug handle. */
51 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
54 static eset *_live_classes = NULL;
56 /* cache computed results */
57 static eset *_live_graphs = NULL;
60 * Given a method, find the firm graph that implements that method.
62 static ir_graph *get_implementing_graph(ir_entity *method)
64 ir_graph *graph = NULL;
66 if (get_entity_peculiarity(method) != peculiarity_description)
67 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
73 * Add a graph to the set of live graphs.
75 * @param graph the graph to add
76 * @return non-zero if the graph was added, zero
77 * if it was already in the live set
79 static int add_graph(ir_graph *graph)
81 if (!eset_contains(_live_graphs, graph)) {
82 DB((dbg, LEVEL_2, "RTA: new graph of %+F\n", graph));
84 eset_insert(_live_graphs, graph);
92 * Add a class to the set of live classes.
94 * @param clazz the class to add
95 * @return non-zero if the graph was added, zero
96 * if it was already in the live set
98 static int add_class(ir_type *clazz)
100 if (!eset_contains(_live_classes, clazz)) {
101 DB((dbg, LEVEL_2, "RTA: new class: %+F\n", clazz));
103 eset_insert(_live_classes, clazz);
110 /** Given an entity, add all implementing graphs that belong to live classes
113 * Iff additions occurred, return TRUE, else FALSE.
115 static int add_implementing_graphs(ir_entity *method)
118 int n_over = get_entity_n_overwrittenby(method);
119 ir_graph *graph = get_entity_irg(method);
123 graph = get_implementing_graph(method);
125 DB((dbg, LEVEL_2, "RTA: new call to %+F\n", method));
127 if (rta_is_alive_class(get_entity_owner(method))) {
129 change = add_graph(graph);
132 for (i = 0; i < n_over; ++i) {
133 ir_entity *over = get_entity_overwrittenby(method, i);
134 change |= add_implementing_graphs(over);
141 * Walker: Enter all method accesses and all class allocations into
144 * Set *(int*)env to true iff (possibly) new graphs have been found.
146 static void rta_act(ir_node *node, void *env)
148 int *change = (int *)env;
149 ir_opcode op = get_irn_opcode(node);
151 if (iro_Call == op) { /* CALL */
152 ir_entity *ent = NULL;
154 ir_node *ptr = get_Call_ptr(node);
157 if (iro_Sel == get_irn_opcode(ptr)) {
158 ent = get_Sel_entity(ptr);
159 *change |= add_implementing_graphs(ent);
162 } else if (iro_SymConst == get_irn_opcode(ptr)) {
163 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
166 ent = get_SymConst_entity(ptr);
167 graph = get_entity_irg(ent);
169 *change |= add_graph(graph);
171 /* it's an external allocated thing. */
173 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
174 /* Entities of kind addr_name may not be allocated in this compilation unit.
175 If so, the frontend built faulty Firm. So just ignore. */
176 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
177 assert(ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
179 /* other symconst. */
180 panic("This SymConst can not be an address for a method call.");
185 panic("Unexpected address expression: can not analyse, therefore can not do correct rta!");
187 } else if (iro_Alloc == op) { /* ALLOC */
188 ir_type *type = get_Alloc_type(node);
190 *change |= add_class(type);
195 Traverse the given graph to collect method accesses and
198 static int rta_fill_graph(ir_graph* graph)
201 irg_walk_graph(graph, rta_act, NULL, &change);
206 * Traverse all graphs to collect method accesses and object allocations.
208 static int rta_fill_incremental(void)
213 #ifdef INTERPROCEDURAL_VIEW
214 int old_ip_view = get_interprocedural_view();
216 set_interprocedural_view(0); /* save this for later */
219 /* init_tables has added main_irg to _live_graphs */
221 /* Need to take care of graphs that are externally
222 visible or sticky. Pretend that they are called: */
223 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
224 ir_graph *graph = get_irp_irg(i);
225 ir_entity *ent = get_irg_entity(graph);
227 if ((visibility_external_visible == get_entity_visibility(ent)) ||
228 (stickyness_sticky == get_entity_stickyness(ent))) {
229 eset_insert(_live_graphs, graph);
237 eset *live_graphs = _live_graphs;
238 _live_graphs = eset_create();
240 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
242 /* collect what we have found previously */
243 eset_insert_all(_live_graphs, live_graphs);
246 for (graph = eset_first(live_graphs);
248 graph = eset_next(live_graphs)) {
249 DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
250 rerun |= rta_fill_graph(graph);
252 eset_destroy(live_graphs);
256 #ifdef INTERPROCEDURAL_VIEW
257 set_interprocedural_view(old_ip_view); /* cover up our traces */
264 * Count the number of graphs that we have found to be live.
266 static int stats(void)
269 int n_live_graphs = 0;
271 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
272 ir_graph *graph = get_irp_irg(i);
274 if (rta_is_alive_graph(graph))
278 return n_live_graphs;
281 /* remove a graph, part I */
283 We removed the first graph to implement the entity, so we're
284 abstract now. Pretend that it wasn't there at all, and every
285 entity that used to inherit this entity's graph is now abstract.
289 Initialize the static data structures.
291 static void init_tables(void)
297 _live_classes = eset_create();
298 _live_graphs = eset_create();
300 irg = get_irp_main_irg();
302 /* add the main irg to the live set if one is specified */
303 eset_insert(_live_graphs, irg);
306 /* Find static allocated classes */
307 tp = get_glob_type();
308 n = get_class_n_members(tp);
309 for (i = 0; i < n; ++i) {
310 ir_type *member_type = get_entity_type(get_class_member(tp, i));
311 if (is_Class_type(member_type))
312 eset_insert(_live_classes, member_type);
316 n = get_struct_n_members(tp);
317 for (i = 0; i < n; ++i) {
318 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
319 if (is_Class_type(member_type))
320 eset_insert(_live_classes, member_type);
323 /** @FIXME: add constructors/destructors */
327 * Initialize the RTA data structures, and perform RTA.
332 int rem_vpi = get_visit_pseudo_irgs();
333 set_visit_pseudo_irgs(1);
335 FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
337 # ifdef DEBUG_libfirm
340 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
341 irg_vrfy(get_irp_irg(i));
345 # endif /* defined DEBUG_libfirm */
349 n_runs = rta_fill_incremental();
351 DB((dbg, LEVEL_1, "RTA: n_graphs = %i\n", get_irp_n_irgs()));
352 DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
353 DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs));
355 # ifdef DEBUG_libfirm
359 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
360 irg_vrfy(get_irp_irg(i));
364 # endif /* defined DEBUG_libfirm */
366 set_visit_pseudo_irgs(rem_vpi);
370 * walker for all types and entities
372 * Changes the peculiarity of entities that represents
373 * dead graphs to peculiarity_description.
375 static void make_entity_to_description(type_or_ent tore, void *env) {
377 if (is_entity(tore.ent)) {
378 ir_entity *ent = tore.ent;
380 if ((is_Method_type(get_entity_type(ent))) &&
381 (get_entity_peculiarity(ent) != peculiarity_description) &&
382 (get_entity_visibility(ent) != visibility_external_allocated) ) {
383 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
384 if (! eset_contains(_live_graphs, irg)) {
385 set_entity_peculiarity(ent, peculiarity_description);
386 set_entity_irg(ent, NULL);
392 /* Delete all graphs that we have found to be dead from the program
393 If verbose == 1, print statistics, if > 1, chatter about every detail
395 void rta_delete_dead_graphs(void)
397 int i, n_dead_irgs, n_graphs = get_irp_n_irgs();
398 ir_graph *irg, *next_irg, *dead_irgs;
400 int rem_vpi = get_visit_pseudo_irgs();
401 set_visit_pseudo_irgs(1);
403 irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
407 for (i = n_graphs - 1; i >= 0; --i) {
408 irg = get_irp_irg(i);
410 if (! rta_is_alive_graph(irg)) {
412 ir_entity *ent = get_irg_entity(irg);
413 assert(visibility_external_visible != get_entity_visibility(ent));
415 set_irg_link(irg, dead_irgs);
421 /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
422 type_walk(make_entity_to_description, NULL, NULL);
423 for (irg = dead_irgs; irg != NULL; irg = next_irg) {
424 next_irg = get_irg_link(irg);
428 DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
430 irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
431 set_visit_pseudo_irgs(rem_vpi);
434 /* Clean up the RTA data structures. Call this after calling rta_init */
435 void rta_cleanup(void)
437 # ifdef DEBUG_libfirm
439 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
440 irg_vrfy(get_irp_irg(i));
443 # endif /* defined DEBUG_libfirm */
445 if (_live_classes != NULL) {
446 eset_destroy(_live_classes);
447 _live_classes = NULL;
450 if (_live_graphs != NULL) {
451 eset_destroy(_live_graphs);
456 /* Say whether this class might be instantiated at any point in the program: */
457 int rta_is_alive_class(ir_type *clazz)
459 return eset_contains(_live_classes, clazz);
462 /* Say whether this graph might be run at any time in the program: */
463 int rta_is_alive_graph(ir_graph *graph)
465 return eset_contains(_live_graphs, graph);
468 /* dump our opinion */
469 void rta_report(void)
473 n = get_irp_n_types();
474 for (i = 0; i < n; ++i) {
475 ir_type *tp = get_irp_type(i);
476 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
477 ir_printf("RTA: considered allocated: %+F\n", tp);
481 n = get_irp_n_irgs();
482 for (i = 0; i < n; i++) {
483 ir_graph *irg = get_irp_irg(i);
484 if (rta_is_alive_graph(irg)) {
485 ir_printf("RTA: considered called: graph of %+F\n", irg);