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.
35 #include "irgraph_t.h"
46 # endif /* not defined TRUE */
49 static int verbose = 0;
53 static eset *_live_classes = NULL;
55 /* cache computed results */
56 static eset *_live_graphs = NULL;
59 Given a method, find the firm graph that implements that method.
61 static ir_graph *get_implementing_graph (ir_entity *method)
63 ir_graph *graph = NULL;
65 if (get_entity_peculiarity(method) != peculiarity_description)
66 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
72 * Add a graph to the set of live graphs.
74 * @param graph the graph to add
75 * @return non-zero if the graph was added, zero
76 * if it was already in the live set
78 static int add_graph (ir_graph *graph)
80 if (!eset_contains (_live_graphs, graph)) {
82 ir_fprintf(stdout, "RTA: new graph of %+F\n", graph);
85 eset_insert (_live_graphs, graph);
93 * Add a class to the set of live classes.
95 * @param clazz the class to add
96 * @return non-zero if the graph was added, zero
97 * if it was already in the live set
99 static int add_class (ir_type *clazz)
101 if (!eset_contains (_live_classes, clazz)) {
103 ir_fprintf(stdout, "RTA: new class: %+F\n", clazz);
106 eset_insert (_live_classes, clazz);
113 /** Given an entity, add all implementing graphs that belong to live classes
116 * Iff additions occurred, return TRUE, else FALSE.
118 static int add_implementing_graphs (ir_entity *method)
121 int n_over = get_entity_n_overwrittenby (method);
122 ir_graph *graph = get_entity_irg (method);
126 graph = get_implementing_graph (method);
130 ir_fprintf(stdout, "RTA: new call to %+F\n", method);
133 if (rta_is_alive_class (get_entity_owner (method))) {
135 change = add_graph (graph);
139 for (i = 0; i < n_over; i ++) {
140 ir_entity *over = get_entity_overwrittenby (method, i);
141 change |= add_implementing_graphs (over);
147 /** Enter all method accesses and all class allocations into
150 * Set *(int*)env to true iff (possibly) new graphs have been found.
152 static void rta_act (ir_node *node, void *env)
154 int *change = (int*) env;
155 ir_opcode op = get_irn_opcode (node);
157 if (iro_Call == op) { /* CALL */
158 ir_entity *ent = NULL;
160 ir_node *ptr = get_Call_ptr (node);
163 if (iro_Sel == get_irn_opcode (ptr)) {
164 ent = get_Sel_entity (ptr);
165 *change |= add_implementing_graphs (ent);
168 } else if (iro_SymConst == get_irn_opcode (ptr)) {
169 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
172 ent = get_SymConst_entity (ptr);
173 graph = get_entity_irg (ent);
175 *change |= add_graph (graph);
177 /* it's an external allocated thing. */
179 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
180 /* Entities of kind addr_name may not be allocated in this compilation unit.
181 If so, the frontend built faulty Firm. So just ignore. */
182 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
183 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
185 /* other symconst. */
186 assert(0 && "This SymConst can not be an address for a method call.");
191 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
194 } else if (iro_Alloc == op) { /* ALLOC */
195 ir_type *type = get_Alloc_type (node);
197 *change |= add_class (type);
202 Traverse the given graph to collect method accesses and
205 static int rta_fill_graph (ir_graph* graph)
208 irg_walk_graph (graph, rta_act, NULL, &change);
212 /** Traverse all graphs to collect method accesses and object allocations.
214 static int rta_fill_incremental (void)
219 #ifdef INTERPROCEDURAL_VIEW
220 int old_ip_view = get_interprocedural_view();
222 set_interprocedural_view(0); /* save this for later */
225 /* init_tables has added main_irg to _live_graphs */
227 /* Need to take care of graphs that are externally
228 visible or sticky. Pretend that they are called: */
230 for (i = 0; i < get_irp_n_irgs(); i++) {
231 ir_graph *graph = get_irp_irg (i);
232 ir_entity *ent = get_irg_entity (graph);
234 if ((visibility_external_visible == get_entity_visibility (ent)) ||
235 (stickyness_sticky == get_entity_stickyness (ent))) {
236 eset_insert (_live_graphs, graph);
237 // printf("external visible: "); DDMG(graph);
245 eset *live_graphs = _live_graphs;
246 _live_graphs = eset_create ();
249 fprintf(stdout, "RTA: RUN %i\n", n_runs);
252 /* collect what we have found previously */
253 eset_insert_all (_live_graphs, live_graphs);
256 for (graph = eset_first (live_graphs);
258 graph = eset_next (live_graphs)) {
261 ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs,
265 rerun |= rta_fill_graph (graph);
268 eset_destroy (live_graphs);
273 #ifdef INTERPROCEDURAL_VIEW
274 set_interprocedural_view(old_ip_view); /* cover up our traces */
281 * Count the number of graphs that we have found to be live.
283 static int stats (void)
286 int n_live_graphs = 0;
287 int n_graphs = get_irp_n_irgs();
289 for (i = 0; i < n_graphs; i++) {
290 ir_graph *graph = get_irp_irg(i);
292 if (rta_is_alive_graph (graph)) {
297 return (n_live_graphs);
300 /* remove a graph, part I */
302 We removed the first graph to implement the entity, so we're
303 abstract now. Pretend that it wasn't there at all, and every
304 entity that used to inherit this entity's graph is now abstract.
308 Initialize the static data structures.
310 static void init_tables (void)
315 _live_classes = eset_create ();
316 _live_graphs = eset_create ();
318 if (get_irp_main_irg ()) {
319 eset_insert (_live_graphs, get_irp_main_irg ());
322 /* Find static allocated classes */
323 tp = get_glob_type();
324 n = get_class_n_members(tp);
325 for (i = 0; i < n; ++i) {
326 ir_type *member_type = get_entity_type(get_class_member(tp, i));
327 if (is_Class_type(member_type))
328 eset_insert(_live_classes, member_type);
332 n = get_struct_n_members(tp);
333 for (i = 0; i < n; ++i) {
334 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
335 if (is_Class_type(member_type))
336 eset_insert(_live_classes, member_type);
341 * Initialize the RTA data structures, and perform RTA.
342 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
344 void rta_init (int do_verbose)
348 int rem_vpi = get_visit_pseudo_irgs();
349 set_visit_pseudo_irgs(1);
351 # ifdef DEBUG_libfirm
354 n = get_irp_n_irgs();
355 for (i = 0; i < n; i++) {
356 irg_vrfy (get_irp_irg(i));
360 # endif /* defined DEBUG_libfirm */
362 verbose = do_verbose;
366 n_runs = rta_fill_incremental ();
369 int n_live_graphs = stats ();
371 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
372 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
373 printf ("RTA: n_runs = %i\n", n_runs);
376 # ifdef DEBUG_libfirm
379 n = get_irp_n_irgs();
380 for (i = 0; i < n; i++) {
381 irg_vrfy (get_irp_irg(i));
385 # endif /* defined DEBUG_libfirm */
387 set_visit_pseudo_irgs(rem_vpi);
391 * walker for all types and entities
393 * Changes the peculiarity of entities that represents
394 * dead graphs to peculiarity_description.
396 static void make_entity_to_description(type_or_ent tore, void *env) {
398 if (is_entity(tore.ent)) {
399 ir_entity *ent = tore.ent;
401 if ((is_Method_type(get_entity_type(ent))) &&
402 (get_entity_peculiarity(ent) != peculiarity_description) &&
403 (get_entity_visibility(ent) != visibility_external_allocated) ) {
404 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
405 if (!eset_contains (_live_graphs, irg)) {
406 set_entity_peculiarity(ent, peculiarity_description);
407 set_entity_irg(ent, NULL);
413 /* Delete all graphs that we have found to be dead from the program
414 If verbose == 1, print statistics, if > 1, chatter about every detail
416 void rta_delete_dead_graphs (void)
419 int n_graphs = get_irp_n_irgs ();
420 ir_graph *graph = NULL;
421 int n_dead_graphs = 0;
422 ir_graph **dead_graphs;
424 int rem_vpi = get_visit_pseudo_irgs();
425 set_visit_pseudo_irgs(1);
427 dead_graphs = XMALLOCN(ir_graph*, get_irp_n_irgs());
429 for (i = 0; i < n_graphs; i++) {
430 graph = get_irp_irg(i);
432 if (rta_is_alive_graph (graph)) {
433 /* do nothing (except some debugging fprintf`s :-) */
436 ir_entity *ent = get_irg_entity (graph);
437 assert (visibility_external_visible != get_entity_visibility (ent));
440 dead_graphs[n_dead_graphs] = graph;
445 type_walk(make_entity_to_description, NULL, NULL);
446 for (i = 0; i < n_dead_graphs; ++i) {
447 remove_irp_irg (dead_graphs[i]);
451 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
454 set_visit_pseudo_irgs(rem_vpi);
459 /* Clean up the RTA data structures. Call this after calling rta_init */
460 void rta_cleanup (void)
462 # ifdef DEBUG_libfirm
464 for (i = 0; i < get_irp_n_irgs(); i++) {
465 irg_vrfy (get_irp_irg(i));
468 # endif /* defined DEBUG_libfirm */
471 eset_destroy (_live_classes);
472 _live_classes = NULL;
476 eset_destroy (_live_graphs);
481 /* Say whether this class might be instantiated at any point in the program: */
482 int rta_is_alive_class (ir_type *clazz)
484 return (eset_contains (_live_classes, clazz));
487 /* Say whether this graph might be run at any time in the program: */
488 int rta_is_alive_graph (ir_graph *graph)
490 return eset_contains (_live_graphs, graph);
493 /* dump our opinion */
494 void rta_report (void)
498 for (i = 0; i < get_irp_n_types(); ++i) {
499 ir_type *tp = get_irp_type(i);
500 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
501 ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp);
505 for (i = 0; i < get_irp_n_irgs(); i++) {
506 if (rta_is_alive_graph (get_irp_irg(i))) {
507 ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i));