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
36 #include "irgraph_t.h"
46 /** The debug handle. */
47 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
50 static pset_new_t *_live_classes = NULL;
52 /* cache computed results */
53 static pset_new_t *_live_graphs = NULL;
56 * Add a graph to the set of live graphs.
58 * @param graph the graph to add
59 * @return non-zero if the graph was added, zero
60 * if it was already in the live set
62 static bool add_graph(ir_graph *graph)
64 if (!pset_new_contains(_live_graphs, graph)) {
65 DB((dbg, LEVEL_2, "RTA: new graph of %+F\n", graph));
67 pset_new_insert(_live_graphs, graph);
75 * Add a class to the set of live classes.
77 * @param clazz the class to add
78 * @return non-zero if the graph was added, zero
79 * if it was already in the live set
81 static bool add_class(ir_type *clazz)
83 if (!pset_new_contains(_live_classes, clazz)) {
84 DB((dbg, LEVEL_2, "RTA: new class: %+F\n", clazz));
86 pset_new_insert(_live_classes, clazz);
93 /** Given an entity, add all implementing graphs that belong to live classes
96 * Iff additions occurred, return true, else false.
98 static bool add_implementing_graphs(ir_entity *method)
101 int n_over = get_entity_n_overwrittenby(method);
102 ir_graph *graph = get_entity_irg(method);
106 graph = get_entity_irg(method);
108 DB((dbg, LEVEL_2, "RTA: new call to %+F\n", method));
110 if (rta_is_alive_class(get_entity_owner(method))) {
112 change = add_graph(graph);
115 for (i = 0; i < n_over; ++i) {
116 ir_entity *over = get_entity_overwrittenby(method, i);
117 change |= add_implementing_graphs(over);
124 * Walker: Enter all method accesses and all class allocations into
127 * Set *(int*)env to true iff (possibly) new graphs have been found.
129 static void rta_act(ir_node *node, void *env)
131 bool *change = (bool*)env;
132 ir_opcode op = get_irn_opcode(node);
134 if (iro_Call == op) { /* CALL */
135 ir_entity *ent = NULL;
137 ir_node *ptr = get_Call_ptr(node);
140 if (iro_Sel == get_irn_opcode(ptr)) {
141 ent = get_Sel_entity(ptr);
142 *change |= add_implementing_graphs(ent);
145 } else if (iro_SymConst == get_irn_opcode(ptr)) {
146 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
149 ent = get_SymConst_entity(ptr);
150 graph = get_entity_irg(ent);
152 *change |= add_graph(graph);
154 /* it's an external allocated thing. */
157 /* other symconst. */
158 panic("This SymConst can not be an address for a method call.");
163 panic("Unexpected address expression: can not analyse, therefore can not do correct rta!");
165 } else if (iro_Alloc == op) { /* ALLOC */
166 ir_type *type = get_Alloc_type(node);
168 *change |= add_class(type);
173 Traverse the given graph to collect method accesses and
176 static bool rta_fill_graph(ir_graph* graph)
179 irg_walk_graph(graph, rta_act, NULL, &change);
184 * Traverse all graphs to collect method accesses and object allocations.
186 static int rta_fill_incremental(void)
191 #ifdef INTERPROCEDURAL_VIEW
192 int old_ip_view = get_interprocedural_view();
194 set_interprocedural_view(0); /* save this for later */
197 /* init_tables has added main_irg to _live_graphs */
199 /* Need to take care of graphs that are externally
200 visible or sticky. Pretend that they are called: */
201 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
202 ir_graph *graph = get_irp_irg(i);
203 ir_entity *ent = get_irg_entity(graph);
204 ir_linkage linkage = get_entity_linkage(ent);
206 if (entity_is_externally_visible(ent)
207 || (linkage & IR_LINKAGE_HIDDEN_USER)) {
208 pset_new_insert(_live_graphs, graph);
214 pset_new_iterator_t iter;
217 pset_new_t *live_graphs = _live_graphs;
218 _live_graphs = XMALLOC(pset_new_t);
219 pset_new_init(_live_graphs);
221 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
223 /* collect what we have found previously */
224 foreach_pset_new(live_graphs, graph, iter) {
225 pset_new_insert(_live_graphs, graph);
229 foreach_pset_new(live_graphs, graph, iter) {
230 DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
231 rerun |= rta_fill_graph(graph);
233 pset_new_destroy(live_graphs);
238 #ifdef INTERPROCEDURAL_VIEW
239 set_interprocedural_view(old_ip_view); /* cover up our traces */
247 * Count the number of graphs that we have found to be live.
249 static int stats(void)
252 int n_live_graphs = 0;
254 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
255 ir_graph *graph = get_irp_irg(i);
257 if (rta_is_alive_graph(graph))
261 return n_live_graphs;
265 /* remove a graph, part I */
267 We removed the first graph to implement the entity, so we're
268 abstract now. Pretend that it wasn't there at all, and every
269 entity that used to inherit this entity's graph is now abstract.
273 Initialize the static data structures.
275 static void init_tables(void)
281 _live_classes = XMALLOC(pset_new_t);
282 pset_new_init(_live_classes);
283 _live_graphs = XMALLOC(pset_new_t);
284 pset_new_init(_live_graphs);
286 irg = get_irp_main_irg();
288 /* add the main irg to the live set if one is specified */
289 pset_new_insert(_live_graphs, irg);
292 /* Find static allocated classes */
293 tp = get_glob_type();
294 n = get_class_n_members(tp);
295 for (i = 0; i < n; ++i) {
296 ir_type *member_type = get_entity_type(get_class_member(tp, i));
297 if (is_Class_type(member_type))
298 pset_new_insert(_live_classes, member_type);
302 n = get_struct_n_members(tp);
303 for (i = 0; i < n; ++i) {
304 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
305 if (is_Class_type(member_type))
306 pset_new_insert(_live_classes, member_type);
309 /** @FIXME: add constructors/destructors */
313 * Initialize the RTA data structures, and perform RTA.
318 int rem_vpi = get_visit_pseudo_irgs();
319 set_visit_pseudo_irgs(1);
321 FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
323 # ifdef DEBUG_libfirm
326 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
327 irg_vrfy(get_irp_irg(i));
331 # endif /* defined DEBUG_libfirm */
335 n_runs = rta_fill_incremental();
337 DB((dbg, LEVEL_1, "RTA: n_graphs = %i\n", get_irp_n_irgs()));
338 DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
339 DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs));
341 # ifdef DEBUG_libfirm
345 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
346 irg_vrfy(get_irp_irg(i));
350 # endif /* defined DEBUG_libfirm */
352 set_visit_pseudo_irgs(rem_vpi);
356 * walker for all types and entities
358 * Changes the peculiarity of entities that represents
359 * dead graphs to peculiarity_description.
361 static void make_entity_to_description(type_or_ent tore, void *env)
364 if (is_entity(tore.ent)) {
365 ir_entity *ent = tore.ent;
367 if ((is_Method_type(get_entity_type(ent))) &&
368 !entity_is_externally_visible(ent)) {
369 ir_graph *irg = get_entity_irg(ent);
370 if (irg != NULL && ! pset_new_contains(_live_graphs, irg)) {
371 set_entity_peculiarity(ent, peculiarity_description);
372 set_entity_irg(ent, NULL);
378 /* Delete all graphs that we have found to be dead from the program
379 If verbose == 1, print statistics, if > 1, chatter about every detail
381 void rta_delete_dead_graphs(void)
383 int i, n_dead_irgs, n_graphs = get_irp_n_irgs();
384 ir_graph *irg, *next_irg, *dead_irgs;
386 int rem_vpi = get_visit_pseudo_irgs();
387 set_visit_pseudo_irgs(1);
389 irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
393 for (i = n_graphs - 1; i >= 0; --i) {
394 irg = get_irp_irg(i);
396 if (! rta_is_alive_graph(irg)) {
397 set_irg_link(irg, dead_irgs);
403 /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
404 type_walk(make_entity_to_description, NULL, NULL);
405 for (irg = dead_irgs; irg != NULL; irg = next_irg) {
406 next_irg = get_irg_link(irg);
410 DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
412 irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
413 set_visit_pseudo_irgs(rem_vpi);
416 /* Clean up the RTA data structures. Call this after calling rta_init */
417 void rta_cleanup(void)
419 # ifdef DEBUG_libfirm
421 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
422 irg_vrfy(get_irp_irg(i));
425 # endif /* defined DEBUG_libfirm */
427 if (_live_classes != NULL) {
428 pset_new_destroy(_live_classes);
430 _live_classes = NULL;
433 if (_live_graphs != NULL) {
434 pset_new_destroy(_live_graphs);
440 /* Say whether this class might be instantiated at any point in the program: */
441 int rta_is_alive_class(ir_type *clazz)
443 return pset_new_contains(_live_classes, clazz);
446 /* Say whether this graph might be run at any time in the program: */
447 int rta_is_alive_graph(ir_graph *graph)
449 return pset_new_contains(_live_graphs, graph);
452 /* dump our opinion */
453 void rta_report(void)
457 n = get_irp_n_types();
458 for (i = 0; i < n; ++i) {
459 ir_type *tp = get_irp_type(i);
460 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
461 ir_printf("RTA: considered allocated: %+F\n", tp);
465 n = get_irp_n_irgs();
466 for (i = 0; i < n; i++) {
467 ir_graph *irg = get_irp_irg(i);
468 if (rta_is_alive_graph(irg)) {
469 ir_printf("RTA: considered called: graph of %+F\n", irg);