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 * Add a graph to the set of live graphs.
62 * @param graph the graph to add
63 * @return non-zero if the graph was added, zero
64 * if it was already in the live set
66 static int add_graph(ir_graph *graph)
68 if (!eset_contains(_live_graphs, graph)) {
69 DB((dbg, LEVEL_2, "RTA: new graph of %+F\n", graph));
71 eset_insert(_live_graphs, graph);
79 * Add a class to the set of live classes.
81 * @param clazz the class to add
82 * @return non-zero if the graph was added, zero
83 * if it was already in the live set
85 static int add_class(ir_type *clazz)
87 if (!eset_contains(_live_classes, clazz)) {
88 DB((dbg, LEVEL_2, "RTA: new class: %+F\n", clazz));
90 eset_insert(_live_classes, clazz);
97 /** Given an entity, add all implementing graphs that belong to live classes
100 * Iff additions occurred, return TRUE, else FALSE.
102 static int add_implementing_graphs(ir_entity *method)
105 int n_over = get_entity_n_overwrittenby(method);
106 ir_graph *graph = get_entity_irg(method);
110 graph = get_entity_irg(method);
112 DB((dbg, LEVEL_2, "RTA: new call to %+F\n", method));
114 if (rta_is_alive_class(get_entity_owner(method))) {
116 change = add_graph(graph);
119 for (i = 0; i < n_over; ++i) {
120 ir_entity *over = get_entity_overwrittenby(method, i);
121 change |= add_implementing_graphs(over);
128 * Walker: Enter all method accesses and all class allocations into
131 * Set *(int*)env to true iff (possibly) new graphs have been found.
133 static void rta_act(ir_node *node, void *env)
135 int *change = (int *)env;
136 ir_opcode op = get_irn_opcode(node);
138 if (iro_Call == op) { /* CALL */
139 ir_entity *ent = NULL;
141 ir_node *ptr = get_Call_ptr(node);
144 if (iro_Sel == get_irn_opcode(ptr)) {
145 ent = get_Sel_entity(ptr);
146 *change |= add_implementing_graphs(ent);
149 } else if (iro_SymConst == get_irn_opcode(ptr)) {
150 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
153 ent = get_SymConst_entity(ptr);
154 graph = get_entity_irg(ent);
156 *change |= add_graph(graph);
158 /* it's an external allocated thing. */
161 /* other symconst. */
162 panic("This SymConst can not be an address for a method call.");
167 panic("Unexpected address expression: can not analyse, therefore can not do correct rta!");
169 } else if (iro_Alloc == op) { /* ALLOC */
170 ir_type *type = get_Alloc_type(node);
172 *change |= add_class(type);
177 Traverse the given graph to collect method accesses and
180 static int rta_fill_graph(ir_graph* graph)
183 irg_walk_graph(graph, rta_act, NULL, &change);
188 * Traverse all graphs to collect method accesses and object allocations.
190 static int rta_fill_incremental(void)
195 #ifdef INTERPROCEDURAL_VIEW
196 int old_ip_view = get_interprocedural_view();
198 set_interprocedural_view(0); /* save this for later */
201 /* init_tables has added main_irg to _live_graphs */
203 /* Need to take care of graphs that are externally
204 visible or sticky. Pretend that they are called: */
205 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
206 ir_graph *graph = get_irp_irg(i);
207 ir_entity *ent = get_irg_entity(graph);
208 ir_linkage linkage = get_entity_linkage(ent);
210 if (entity_is_externally_visible(ent)
211 || (linkage & IR_LINKAGE_HIDDEN_USER)) {
212 eset_insert(_live_graphs, graph);
220 eset *live_graphs = _live_graphs;
221 _live_graphs = eset_create();
223 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
225 /* collect what we have found previously */
226 eset_insert_all(_live_graphs, live_graphs);
229 for (graph = eset_first(live_graphs);
231 graph = eset_next(live_graphs)) {
232 DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
233 rerun |= rta_fill_graph(graph);
235 eset_destroy(live_graphs);
239 #ifdef INTERPROCEDURAL_VIEW
240 set_interprocedural_view(old_ip_view); /* cover up our traces */
248 * Count the number of graphs that we have found to be live.
250 static int stats(void)
253 int n_live_graphs = 0;
255 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
256 ir_graph *graph = get_irp_irg(i);
258 if (rta_is_alive_graph(graph))
262 return n_live_graphs;
266 /* remove a graph, part I */
268 We removed the first graph to implement the entity, so we're
269 abstract now. Pretend that it wasn't there at all, and every
270 entity that used to inherit this entity's graph is now abstract.
274 Initialize the static data structures.
276 static void init_tables(void)
282 _live_classes = eset_create();
283 _live_graphs = eset_create();
285 irg = get_irp_main_irg();
287 /* add the main irg to the live set if one is specified */
288 eset_insert(_live_graphs, irg);
291 /* Find static allocated classes */
292 tp = get_glob_type();
293 n = get_class_n_members(tp);
294 for (i = 0; i < n; ++i) {
295 ir_type *member_type = get_entity_type(get_class_member(tp, i));
296 if (is_Class_type(member_type))
297 eset_insert(_live_classes, member_type);
301 n = get_struct_n_members(tp);
302 for (i = 0; i < n; ++i) {
303 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
304 if (is_Class_type(member_type))
305 eset_insert(_live_classes, member_type);
308 /** @FIXME: add constructors/destructors */
312 * Initialize the RTA data structures, and perform RTA.
317 int rem_vpi = get_visit_pseudo_irgs();
318 set_visit_pseudo_irgs(1);
320 FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
322 # ifdef DEBUG_libfirm
325 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
326 irg_vrfy(get_irp_irg(i));
330 # endif /* defined DEBUG_libfirm */
334 n_runs = rta_fill_incremental();
336 DB((dbg, LEVEL_1, "RTA: n_graphs = %i\n", get_irp_n_irgs()));
337 DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
338 DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs));
340 # ifdef DEBUG_libfirm
344 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
345 irg_vrfy(get_irp_irg(i));
349 # endif /* defined DEBUG_libfirm */
351 set_visit_pseudo_irgs(rem_vpi);
355 * walker for all types and entities
357 * Changes the peculiarity of entities that represents
358 * dead graphs to peculiarity_description.
360 static void make_entity_to_description(type_or_ent tore, void *env)
363 if (is_entity(tore.ent)) {
364 ir_entity *ent = tore.ent;
366 if ((is_Method_type(get_entity_type(ent))) &&
367 !entity_is_externally_visible(ent)) {
368 ir_graph *irg = get_entity_irg(ent);
369 if (irg != NULL && ! eset_contains(_live_graphs, irg)) {
370 set_entity_peculiarity(ent, peculiarity_description);
371 set_entity_irg(ent, NULL);
377 /* Delete all graphs that we have found to be dead from the program
378 If verbose == 1, print statistics, if > 1, chatter about every detail
380 void rta_delete_dead_graphs(void)
382 int i, n_dead_irgs, n_graphs = get_irp_n_irgs();
383 ir_graph *irg, *next_irg, *dead_irgs;
385 int rem_vpi = get_visit_pseudo_irgs();
386 set_visit_pseudo_irgs(1);
388 irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
392 for (i = n_graphs - 1; i >= 0; --i) {
393 irg = get_irp_irg(i);
395 if (! rta_is_alive_graph(irg)) {
396 set_irg_link(irg, dead_irgs);
402 /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
403 type_walk(make_entity_to_description, NULL, NULL);
404 for (irg = dead_irgs; irg != NULL; irg = next_irg) {
405 next_irg = get_irg_link(irg);
409 DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
411 irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
412 set_visit_pseudo_irgs(rem_vpi);
415 /* Clean up the RTA data structures. Call this after calling rta_init */
416 void rta_cleanup(void)
418 # ifdef DEBUG_libfirm
420 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
421 irg_vrfy(get_irp_irg(i));
424 # endif /* defined DEBUG_libfirm */
426 if (_live_classes != NULL) {
427 eset_destroy(_live_classes);
428 _live_classes = NULL;
431 if (_live_graphs != NULL) {
432 eset_destroy(_live_graphs);
437 /* Say whether this class might be instantiated at any point in the program: */
438 int rta_is_alive_class(ir_type *clazz)
440 return eset_contains(_live_classes, clazz);
443 /* Say whether this graph might be run at any time in the program: */
444 int rta_is_alive_graph(ir_graph *graph)
446 return eset_contains(_live_graphs, graph);
449 /* dump our opinion */
450 void rta_report(void)
454 n = get_irp_n_types();
455 for (i = 0; i < n; ++i) {
456 ir_type *tp = get_irp_type(i);
457 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
458 ir_printf("RTA: considered allocated: %+F\n", tp);
462 n = get_irp_n_irgs();
463 for (i = 0; i < n; i++) {
464 ir_graph *irg = get_irp_irg(i);
465 if (rta_is_alive_graph(irg)) {
466 ir_printf("RTA: considered called: graph of %+F\n", irg);