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)
64 ir_graph *graph = get_entity_irg ((ir_entity*) method);
66 /* Search upwards in the overwrites graph. */
67 /* GL: this will not work for multiple inheritance */
70 int n_over = get_entity_n_overwrites ((ir_entity*) method);
72 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
73 ir_entity *over = get_entity_overwrites ((ir_entity*) method, i);
74 graph = get_implementing_graph (over);
78 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
79 assert(get_entity_peculiarity(method) == peculiarity_description
80 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
82 /* we *must* always return a graph != NULL, *except* when we're used
83 inside remove_irg or force_description */
84 /* assert (graph && "no graph"); */
88 ir_graph *graph = NULL;
90 if (get_entity_peculiarity(method) != peculiarity_description)
91 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
98 * Add a graph to the set of live graphs.
100 * @param graph the graph to add
101 * @return non-zero if the graph was added, zero
102 * if it was already in the live set
104 static int add_graph (ir_graph *graph)
106 if (!eset_contains (_live_graphs, graph)) {
108 ir_fprintf(stdout, "RTA: new graph of %+F\n", graph);
111 eset_insert (_live_graphs, graph);
119 * Add a class to the set of live classes.
121 * @param clazz the class to add
122 * @return non-zero if the graph was added, zero
123 * if it was already in the live set
125 static int add_class (ir_type *clazz)
127 if (!eset_contains (_live_classes, clazz)) {
129 ir_fprintf(stdout, "RTA: new class: %+F\n", clazz);
132 eset_insert (_live_classes, clazz);
139 /** Given an entity, add all implementing graphs that belong to live classes
142 * Iff additions occurred, return TRUE, else FALSE.
144 static int add_implementing_graphs (ir_entity *method)
147 int n_over = get_entity_n_overwrittenby (method);
148 ir_graph *graph = get_entity_irg (method);
152 graph = get_implementing_graph (method);
156 ir_fprintf(stdout, "RTA: new call to %+F\n", method);
159 if (rta_is_alive_class (get_entity_owner (method))) {
161 change = add_graph (graph);
165 for (i = 0; i < n_over; i ++) {
166 ir_entity *over = get_entity_overwrittenby (method, i);
167 change |= add_implementing_graphs (over);
173 /** Enter all method accesses and all class allocations into
176 * Set *(int*)env to true iff (possibly) new graphs have been found.
178 static void rta_act (ir_node *node, void *env)
180 int *change = (int*) env;
181 ir_opcode op = get_irn_opcode (node);
183 if (iro_Call == op) { /* CALL */
184 ir_entity *ent = NULL;
186 ir_node *ptr = get_Call_ptr (node);
189 if (iro_Sel == get_irn_opcode (ptr)) {
190 ent = get_Sel_entity (ptr);
191 *change |= add_implementing_graphs (ent);
194 } else if (iro_SymConst == get_irn_opcode (ptr)) {
195 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
198 ent = get_SymConst_entity (ptr);
199 graph = get_entity_irg (ent);
201 *change |= add_graph (graph);
203 /* it's an external allocated thing. */
205 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
206 /* Entities of kind addr_name may not be allocated in this compilation unit.
207 If so, the frontend built faulty Firm. So just ignore. */
208 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
209 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
211 /* other symconst. */
212 assert(0 && "This SymConst can not be an address for a method call.");
217 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
220 } else if (iro_Alloc == op) { /* ALLOC */
221 ir_type *type = get_Alloc_type (node);
223 *change |= add_class (type);
228 Traverse the given graph to collect method accesses and
231 static int rta_fill_graph (ir_graph* graph)
234 irg_walk_graph (graph, rta_act, NULL, &change);
238 /** Traverse all graphs to collect method accesses and object allocations.
240 static int rta_fill_incremental (void)
245 #ifdef INTERPROCEDURAL_VIEW
246 int old_ip_view = get_interprocedural_view();
248 set_interprocedural_view(0); /* save this for later */
251 /* init_tables has added main_irg to _live_graphs */
253 /* Need to take care of graphs that are externally
254 visible or sticky. Pretend that they are called: */
256 for (i = 0; i < get_irp_n_irgs(); i++) {
257 ir_graph *graph = get_irp_irg (i);
258 ir_entity *ent = get_irg_entity (graph);
260 if ((visibility_external_visible == get_entity_visibility (ent)) ||
261 (stickyness_sticky == get_entity_stickyness (ent))) {
262 eset_insert (_live_graphs, graph);
263 // printf("external visible: "); DDMG(graph);
271 eset *live_graphs = _live_graphs;
272 _live_graphs = eset_create ();
275 fprintf(stdout, "RTA: RUN %i\n", n_runs);
278 /* collect what we have found previously */
279 eset_insert_all (_live_graphs, live_graphs);
282 for (graph = eset_first (live_graphs);
284 graph = eset_next (live_graphs)) {
287 ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs,
291 rerun |= rta_fill_graph (graph);
294 eset_destroy (live_graphs);
299 #ifdef INTERPROCEDURAL_VIEW
300 set_interprocedural_view(old_ip_view); /* cover up our traces */
307 * Count the number of graphs that we have found to be live.
309 static int stats (void)
312 int n_live_graphs = 0;
313 int n_graphs = get_irp_n_irgs();
315 for (i = 0; i < n_graphs; i++) {
316 ir_graph *graph = get_irp_irg(i);
318 if (rta_is_alive_graph (graph)) {
323 return (n_live_graphs);
326 /* remove a graph, part I */
328 We removed the first graph to implement the entity, so we're
329 abstract now. Pretend that it wasn't there at all, and every
330 entity that used to inherit this entity's graph is now abstract.
332 /* Since we *know* that this entity will not be called, this is OK. */
333 static void force_description (ir_entity *ent, ir_entity *addr)
335 int i, n_over = get_entity_n_overwrittenby (ent);
337 set_entity_peculiarity (ent, peculiarity_description);
339 for (i = 0; i < n_over; i ++) {
340 ir_entity *over = get_entity_overwrittenby (ent, i);
342 if (peculiarity_inherited == get_entity_peculiarity (over)) {
343 /* We rely on the fact that cse is performed on the const_code_irg. */
344 ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
346 if (addr == my_addr) {
347 force_description (over, addr);
349 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
350 /* check whether 'over' forces 'inheritance' of *our* graph: */
351 ir_node *f_addr = get_atomic_ent_value (over);
352 ir_entity *impl_ent = get_SymConst_entity (f_addr);
354 assert(is_SymConst(f_addr) && "can't do complex addrs");
355 if (impl_ent == addr) {
356 assert (0 && "gibt's denn sowas");
357 force_description (over, addr);
364 Initialize the static data structures.
366 static void init_tables (void)
371 _live_classes = eset_create ();
372 _live_graphs = eset_create ();
374 if (get_irp_main_irg ()) {
375 eset_insert (_live_graphs, get_irp_main_irg ());
378 /* Find static allocated classes */
379 tp = get_glob_type();
380 n = get_class_n_members(tp);
381 for (i = 0; i < n; ++i) {
382 ir_type *member_type = get_entity_type(get_class_member(tp, i));
383 if (is_Class_type(member_type))
384 eset_insert(_live_classes, member_type);
388 n = get_struct_n_members(tp);
389 for (i = 0; i < n; ++i) {
390 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
391 if (is_Class_type(member_type))
392 eset_insert(_live_classes, member_type);
397 * Initialize the RTA data structures, and perform RTA.
398 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
400 void rta_init (int do_verbose)
404 int rem_vpi = get_visit_pseudo_irgs();
405 set_visit_pseudo_irgs(1);
407 # ifdef DEBUG_libfirm
410 n = get_irp_n_irgs();
411 for (i = 0; i < n; i++) {
412 irg_vrfy (get_irp_irg(i));
416 # endif /* defined DEBUG_libfirm */
418 verbose = do_verbose;
422 n_runs = rta_fill_incremental ();
425 int n_live_graphs = stats ();
427 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
428 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
429 printf ("RTA: n_runs = %i\n", n_runs);
432 # ifdef DEBUG_libfirm
435 n = get_irp_n_irgs();
436 for (i = 0; i < n; i++) {
437 irg_vrfy (get_irp_irg(i));
441 # endif /* defined DEBUG_libfirm */
443 set_visit_pseudo_irgs(rem_vpi);
447 * walker for all types and entities
449 * Changes the peculiarity of entities that represents
450 * dead graphs to peculiarity_description.
452 static void make_entity_to_description(type_or_ent tore, void *env) {
454 if (is_entity(tore.ent)) {
455 ir_entity *ent = tore.ent;
457 if ((is_Method_type(get_entity_type(ent))) &&
458 (get_entity_peculiarity(ent) != peculiarity_description) &&
459 (get_entity_visibility(ent) != visibility_external_allocated) ) {
460 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
461 if (!eset_contains (_live_graphs, irg)) {
462 set_entity_peculiarity(ent, peculiarity_description);
463 set_entity_irg(ent, NULL);
469 /* Delete all graphs that we have found to be dead from the program
470 If verbose == 1, print statistics, if > 1, chatter about every detail
472 void rta_delete_dead_graphs (void)
475 int n_graphs = get_irp_n_irgs ();
476 ir_graph *graph = NULL;
477 int n_dead_graphs = 0;
478 ir_graph **dead_graphs;
480 int rem_vpi = get_visit_pseudo_irgs();
481 set_visit_pseudo_irgs(1);
483 dead_graphs = XMALLOCN(ir_graph*, get_irp_n_irgs());
485 for (i = 0; i < n_graphs; i++) {
486 graph = get_irp_irg(i);
488 if (rta_is_alive_graph (graph)) {
489 /* do nothing (except some debugging fprintf`s :-) */
492 ir_entity *ent = get_irg_entity (graph);
493 assert (visibility_external_visible != get_entity_visibility (ent));
496 dead_graphs[n_dead_graphs] = graph;
501 type_walk(make_entity_to_description, NULL, NULL);
502 for (i = 0; i < n_dead_graphs; ++i) {
503 remove_irp_irg (dead_graphs[i]);
507 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
510 set_visit_pseudo_irgs(rem_vpi);
515 /* Clean up the RTA data structures. Call this after calling rta_init */
516 void rta_cleanup (void)
518 # ifdef DEBUG_libfirm
520 for (i = 0; i < get_irp_n_irgs(); i++) {
521 irg_vrfy (get_irp_irg(i));
524 # endif /* defined DEBUG_libfirm */
527 eset_destroy (_live_classes);
528 _live_classes = NULL;
532 eset_destroy (_live_graphs);
537 /* Say whether this class might be instantiated at any point in the program: */
538 int rta_is_alive_class (ir_type *clazz)
540 return (eset_contains (_live_classes, clazz));
543 /* Say whether this graph might be run at any time in the program: */
544 int rta_is_alive_graph (ir_graph *graph)
546 return eset_contains (_live_graphs, graph);
549 /* dump our opinion */
550 void rta_report (void)
554 for (i = 0; i < get_irp_n_types(); ++i) {
555 ir_type *tp = get_irp_type(i);
556 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
557 ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp);
561 for (i = 0; i < get_irp_n_irgs(); i++) {
562 if (rta_is_alive_graph (get_irp_irg(i))) {
563 ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i));