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. */
160 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
161 /* Entities of kind addr_name may not be allocated in this compilation unit.
162 If so, the frontend built faulty Firm. So just ignore. */
163 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
164 assert(ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
166 /* other symconst. */
167 panic("This SymConst can not be an address for a method call.");
172 panic("Unexpected address expression: can not analyse, therefore can not do correct rta!");
174 } else if (iro_Alloc == op) { /* ALLOC */
175 ir_type *type = get_Alloc_type(node);
177 *change |= add_class(type);
182 Traverse the given graph to collect method accesses and
185 static int rta_fill_graph(ir_graph* graph)
188 irg_walk_graph(graph, rta_act, NULL, &change);
193 * Traverse all graphs to collect method accesses and object allocations.
195 static int rta_fill_incremental(void)
200 #ifdef INTERPROCEDURAL_VIEW
201 int old_ip_view = get_interprocedural_view();
203 set_interprocedural_view(0); /* save this for later */
206 /* init_tables has added main_irg to _live_graphs */
208 /* Need to take care of graphs that are externally
209 visible or sticky. Pretend that they are called: */
210 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
211 ir_graph *graph = get_irp_irg(i);
212 ir_entity *ent = get_irg_entity(graph);
213 ir_linkage linkage = get_entity_linkage(ent);
215 if (!(linkage & IR_LINKAGE_LOCAL)
216 || (linkage & IR_LINKAGE_HIDDEN_USER)) {
217 eset_insert(_live_graphs, graph);
225 eset *live_graphs = _live_graphs;
226 _live_graphs = eset_create();
228 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
230 /* collect what we have found previously */
231 eset_insert_all(_live_graphs, live_graphs);
234 for (graph = eset_first(live_graphs);
236 graph = eset_next(live_graphs)) {
237 DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
238 rerun |= rta_fill_graph(graph);
240 eset_destroy(live_graphs);
244 #ifdef INTERPROCEDURAL_VIEW
245 set_interprocedural_view(old_ip_view); /* cover up our traces */
253 * Count the number of graphs that we have found to be live.
255 static int stats(void)
258 int n_live_graphs = 0;
260 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
261 ir_graph *graph = get_irp_irg(i);
263 if (rta_is_alive_graph(graph))
267 return n_live_graphs;
271 /* remove a graph, part I */
273 We removed the first graph to implement the entity, so we're
274 abstract now. Pretend that it wasn't there at all, and every
275 entity that used to inherit this entity's graph is now abstract.
279 Initialize the static data structures.
281 static void init_tables(void)
287 _live_classes = eset_create();
288 _live_graphs = eset_create();
290 irg = get_irp_main_irg();
292 /* add the main irg to the live set if one is specified */
293 eset_insert(_live_graphs, irg);
296 /* Find static allocated classes */
297 tp = get_glob_type();
298 n = get_class_n_members(tp);
299 for (i = 0; i < n; ++i) {
300 ir_type *member_type = get_entity_type(get_class_member(tp, i));
301 if (is_Class_type(member_type))
302 eset_insert(_live_classes, member_type);
306 n = get_struct_n_members(tp);
307 for (i = 0; i < n; ++i) {
308 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
309 if (is_Class_type(member_type))
310 eset_insert(_live_classes, member_type);
313 /** @FIXME: add constructors/destructors */
317 * Initialize the RTA data structures, and perform RTA.
322 int rem_vpi = get_visit_pseudo_irgs();
323 set_visit_pseudo_irgs(1);
325 FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
327 # ifdef DEBUG_libfirm
330 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
331 irg_vrfy(get_irp_irg(i));
335 # endif /* defined DEBUG_libfirm */
339 n_runs = rta_fill_incremental();
341 DB((dbg, LEVEL_1, "RTA: n_graphs = %i\n", get_irp_n_irgs()));
342 DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
343 DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs));
345 # ifdef DEBUG_libfirm
349 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
350 irg_vrfy(get_irp_irg(i));
354 # endif /* defined DEBUG_libfirm */
356 set_visit_pseudo_irgs(rem_vpi);
360 * walker for all types and entities
362 * Changes the peculiarity of entities that represents
363 * dead graphs to peculiarity_description.
365 static void make_entity_to_description(type_or_ent tore, void *env)
368 if (is_entity(tore.ent)) {
369 ir_entity *ent = tore.ent;
371 if ((is_Method_type(get_entity_type(ent))) &&
372 !entity_is_externally_visible(ent)) {
373 ir_graph *irg = get_entity_irg(ent);
374 if (irg != NULL && ! eset_contains(_live_graphs, irg)) {
375 set_entity_peculiarity(ent, peculiarity_description);
376 set_entity_irg(ent, NULL);
382 /* Delete all graphs that we have found to be dead from the program
383 If verbose == 1, print statistics, if > 1, chatter about every detail
385 void rta_delete_dead_graphs(void)
387 int i, n_dead_irgs, n_graphs = get_irp_n_irgs();
388 ir_graph *irg, *next_irg, *dead_irgs;
390 int rem_vpi = get_visit_pseudo_irgs();
391 set_visit_pseudo_irgs(1);
393 irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
397 for (i = n_graphs - 1; i >= 0; --i) {
398 irg = get_irp_irg(i);
400 if (! rta_is_alive_graph(irg)) {
401 set_irg_link(irg, dead_irgs);
407 /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
408 type_walk(make_entity_to_description, NULL, NULL);
409 for (irg = dead_irgs; irg != NULL; irg = next_irg) {
410 next_irg = get_irg_link(irg);
414 DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
416 irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
417 set_visit_pseudo_irgs(rem_vpi);
420 /* Clean up the RTA data structures. Call this after calling rta_init */
421 void rta_cleanup(void)
423 # ifdef DEBUG_libfirm
425 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
426 irg_vrfy(get_irp_irg(i));
429 # endif /* defined DEBUG_libfirm */
431 if (_live_classes != NULL) {
432 eset_destroy(_live_classes);
433 _live_classes = NULL;
436 if (_live_graphs != NULL) {
437 eset_destroy(_live_graphs);
442 /* Say whether this class might be instantiated at any point in the program: */
443 int rta_is_alive_class(ir_type *clazz)
445 return eset_contains(_live_classes, clazz);
448 /* Say whether this graph might be run at any time in the program: */
449 int rta_is_alive_graph(ir_graph *graph)
451 return eset_contains(_live_graphs, graph);
454 /* dump our opinion */
455 void rta_report(void)
459 n = get_irp_n_types();
460 for (i = 0; i < n; ++i) {
461 ir_type *tp = get_irp_type(i);
462 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
463 ir_printf("RTA: considered allocated: %+F\n", tp);
467 n = get_irp_n_irgs();
468 for (i = 0; i < n; i++) {
469 ir_graph *irg = get_irp_irg(i);
470 if (rta_is_alive_graph(irg)) {
471 ir_printf("RTA: considered called: graph of %+F\n", irg);