2 * Copyright (C) 1995-2011 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 size_t 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 unsigned 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)
192 /* init_tables has added main_irg to _live_graphs */
194 /* Need to take care of graphs that are externally
195 visible or sticky. Pretend that they are called: */
196 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
197 ir_graph *graph = get_irp_irg(i);
198 ir_entity *ent = get_irg_entity(graph);
199 ir_linkage linkage = get_entity_linkage(ent);
201 if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent))
202 pset_new_insert(_live_graphs, graph);
207 pset_new_iterator_t iter;
210 pset_new_t *live_graphs = _live_graphs;
211 _live_graphs = XMALLOC(pset_new_t);
212 pset_new_init(_live_graphs);
214 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
216 /* collect what we have found previously */
217 foreach_pset_new(live_graphs, ir_graph*, graph, iter) {
218 pset_new_insert(_live_graphs, graph);
222 foreach_pset_new(live_graphs, ir_graph*, graph, iter) {
223 DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
224 rerun |= rta_fill_graph(graph);
226 pset_new_destroy(live_graphs);
236 * Count the number of graphs that we have found to be live.
238 static size_t stats(void)
241 size_t n_live_graphs = 0;
243 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
244 ir_graph *graph = get_irp_irg(i);
246 if (rta_is_alive_graph(graph))
250 return n_live_graphs;
254 /* remove a graph, part I */
256 We removed the first graph to implement the entity, so we're
257 abstract now. Pretend that it wasn't there at all, and every
258 entity that used to inherit this entity's graph is now abstract.
262 Initialize the static data structures.
264 static void init_tables(void)
267 ir_segment_t segment;
269 _live_classes = XMALLOC(pset_new_t);
270 pset_new_init(_live_classes);
271 _live_graphs = XMALLOC(pset_new_t);
272 pset_new_init(_live_graphs);
274 irg = get_irp_main_irg();
276 /* add the main irg to the live set if one is specified */
277 pset_new_insert(_live_graphs, irg);
280 /* Find static allocated classes in all segments */
281 for (segment = IR_SEGMENT_FIRST; segment <= IR_SEGMENT_LAST; ++segment) {
282 ir_type *tp = get_segment_type(segment);
283 size_t n = get_compound_n_members(tp);
286 for (i = 0; i < n; ++i) {
287 ir_type *member_type = get_entity_type(get_compound_member(tp, i));
288 if (is_Class_type(member_type))
289 pset_new_insert(_live_classes, member_type);
295 * Initialize the RTA data structures, and perform RTA.
301 FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
303 # ifdef DEBUG_libfirm
306 for (i = get_irp_n_irgs(); i > 0;) {
307 irg_verify(get_irp_irg(--i), 0);
311 # endif /* defined DEBUG_libfirm */
315 n_runs = rta_fill_incremental();
317 DB((dbg, LEVEL_1, "RTA: n_graphs = %zu\n", get_irp_n_irgs()));
318 DB((dbg, LEVEL_1, "RTA: n_live_graphs = %zu\n", stats()));
319 DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs));
321 # ifdef DEBUG_libfirm
325 for (i = get_irp_n_irgs(); i > 0;) {
326 irg_verify(get_irp_irg(--i), 0);
330 # endif /* defined DEBUG_libfirm */
334 * walker for all types and entities
336 * Changes the peculiarity of entities that represents
337 * dead graphs to peculiarity_description.
339 static void make_entity_to_description(type_or_ent tore, void *env)
342 if (is_entity(tore.ent)) {
343 ir_entity *ent = tore.ent;
345 if ((is_Method_type(get_entity_type(ent))) &&
346 !entity_is_externally_visible(ent)) {
347 ir_graph *irg = get_entity_irg(ent);
348 if (irg != NULL && ! pset_new_contains(_live_graphs, irg)) {
349 set_entity_peculiarity(ent, peculiarity_description);
350 set_entity_irg(ent, NULL);
356 /* Delete all graphs that we have found to be dead from the program
357 If verbose == 1, print statistics, if > 1, chatter about every detail
359 void rta_delete_dead_graphs(void)
361 size_t i, n_dead_irgs, n_graphs = get_irp_n_irgs();
362 ir_graph *irg, *next_irg, *dead_irgs;
364 irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
368 for (i = n_graphs; i > 0;) {
369 irg = get_irp_irg(--i);
371 if (! rta_is_alive_graph(irg)) {
372 set_irg_link(irg, dead_irgs);
378 /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
379 type_walk(make_entity_to_description, NULL, NULL);
380 for (irg = dead_irgs; irg != NULL; irg = next_irg) {
381 next_irg = (ir_graph*) get_irg_link(irg);
385 DB((dbg, LEVEL_1, "RTA: dead methods = %zu\n", n_dead_irgs));
387 irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
390 /* Clean up the RTA data structures. Call this after calling rta_init */
391 void rta_cleanup(void)
393 # ifdef DEBUG_libfirm
395 for (i = get_irp_n_irgs(); i > 0;) {
396 irg_verify(get_irp_irg(--i), 0);
399 # endif /* defined DEBUG_libfirm */
401 if (_live_classes != NULL) {
402 pset_new_destroy(_live_classes);
404 _live_classes = NULL;
407 if (_live_graphs != NULL) {
408 pset_new_destroy(_live_graphs);
414 /* Say whether this class might be instantiated at any point in the program: */
415 int rta_is_alive_class(ir_type *clazz)
417 return pset_new_contains(_live_classes, clazz);
420 /* Say whether this graph might be run at any time in the program: */
421 int rta_is_alive_graph(ir_graph *graph)
423 return pset_new_contains(_live_graphs, graph);
426 /* dump our opinion */
427 void rta_report(void)
431 n = get_irp_n_types();
432 for (i = 0; i < n; ++i) {
433 ir_type *tp = get_irp_type(i);
434 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
435 ir_printf("RTA: considered allocated: %+F\n", tp);
439 n = get_irp_n_irgs();
440 for (i = 0; i < n; i++) {
441 ir_graph *irg = get_irp_irg(i);
442 if (rta_is_alive_graph(irg)) {
443 ir_printf("RTA: considered called: graph of %+F\n", irg);