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 */
265 * Count the number of graphs that we have found to be live.
267 static int stats(void)
270 int n_live_graphs = 0;
272 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
273 ir_graph *graph = get_irp_irg(i);
275 if (rta_is_alive_graph(graph))
279 return n_live_graphs;
283 /* remove a graph, part I */
285 We removed the first graph to implement the entity, so we're
286 abstract now. Pretend that it wasn't there at all, and every
287 entity that used to inherit this entity's graph is now abstract.
291 Initialize the static data structures.
293 static void init_tables(void)
299 _live_classes = eset_create();
300 _live_graphs = eset_create();
302 irg = get_irp_main_irg();
304 /* add the main irg to the live set if one is specified */
305 eset_insert(_live_graphs, irg);
308 /* Find static allocated classes */
309 tp = get_glob_type();
310 n = get_class_n_members(tp);
311 for (i = 0; i < n; ++i) {
312 ir_type *member_type = get_entity_type(get_class_member(tp, i));
313 if (is_Class_type(member_type))
314 eset_insert(_live_classes, member_type);
318 n = get_struct_n_members(tp);
319 for (i = 0; i < n; ++i) {
320 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
321 if (is_Class_type(member_type))
322 eset_insert(_live_classes, member_type);
325 /** @FIXME: add constructors/destructors */
329 * Initialize the RTA data structures, and perform RTA.
334 int rem_vpi = get_visit_pseudo_irgs();
335 set_visit_pseudo_irgs(1);
337 FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
339 # ifdef DEBUG_libfirm
342 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
343 irg_vrfy(get_irp_irg(i));
347 # endif /* defined DEBUG_libfirm */
351 n_runs = rta_fill_incremental();
353 DB((dbg, LEVEL_1, "RTA: n_graphs = %i\n", get_irp_n_irgs()));
354 DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
355 DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs));
357 # ifdef DEBUG_libfirm
361 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
362 irg_vrfy(get_irp_irg(i));
366 # endif /* defined DEBUG_libfirm */
368 set_visit_pseudo_irgs(rem_vpi);
372 * walker for all types and entities
374 * Changes the peculiarity of entities that represents
375 * dead graphs to peculiarity_description.
377 static void make_entity_to_description(type_or_ent tore, void *env) {
379 if (is_entity(tore.ent)) {
380 ir_entity *ent = tore.ent;
382 if ((is_Method_type(get_entity_type(ent))) &&
383 (get_entity_peculiarity(ent) != peculiarity_description) &&
384 (get_entity_visibility(ent) != visibility_external_allocated) ) {
385 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
386 if (! eset_contains(_live_graphs, irg)) {
387 set_entity_peculiarity(ent, peculiarity_description);
388 set_entity_irg(ent, NULL);
394 /* Delete all graphs that we have found to be dead from the program
395 If verbose == 1, print statistics, if > 1, chatter about every detail
397 void rta_delete_dead_graphs(void)
399 int i, n_dead_irgs, n_graphs = get_irp_n_irgs();
400 ir_graph *irg, *next_irg, *dead_irgs;
402 int rem_vpi = get_visit_pseudo_irgs();
403 set_visit_pseudo_irgs(1);
405 irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
409 for (i = n_graphs - 1; i >= 0; --i) {
410 irg = get_irp_irg(i);
412 if (! rta_is_alive_graph(irg)) {
414 ir_entity *ent = get_irg_entity(irg);
415 assert(visibility_external_visible != get_entity_visibility(ent));
417 set_irg_link(irg, dead_irgs);
423 /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
424 type_walk(make_entity_to_description, NULL, NULL);
425 for (irg = dead_irgs; irg != NULL; irg = next_irg) {
426 next_irg = get_irg_link(irg);
430 DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
432 irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
433 set_visit_pseudo_irgs(rem_vpi);
436 /* Clean up the RTA data structures. Call this after calling rta_init */
437 void rta_cleanup(void)
439 # ifdef DEBUG_libfirm
441 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
442 irg_vrfy(get_irp_irg(i));
445 # endif /* defined DEBUG_libfirm */
447 if (_live_classes != NULL) {
448 eset_destroy(_live_classes);
449 _live_classes = NULL;
452 if (_live_graphs != NULL) {
453 eset_destroy(_live_graphs);
458 /* Say whether this class might be instantiated at any point in the program: */
459 int rta_is_alive_class(ir_type *clazz)
461 return eset_contains(_live_classes, clazz);
464 /* Say whether this graph might be run at any time in the program: */
465 int rta_is_alive_graph(ir_graph *graph)
467 return eset_contains(_live_graphs, graph);
470 /* dump our opinion */
471 void rta_report(void)
475 n = get_irp_n_types();
476 for (i = 0; i < n; ++i) {
477 ir_type *tp = get_irp_type(i);
478 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
479 ir_printf("RTA: considered allocated: %+F\n", tp);
483 n = get_irp_n_irgs();
484 for (i = 0; i < n; i++) {
485 ir_graph *irg = get_irp_irg(i);
486 if (rta_is_alive_graph(irg)) {
487 ir_printf("RTA: considered called: graph of %+F\n", irg);