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.
37 #include "irgraph_t.h"
48 # endif /* not defined TRUE */
51 static int verbose = 0;
55 static eset *_live_classes = NULL;
57 /* cache computed results */
58 static eset *_live_graphs = NULL;
61 Given a method, find the firm graph that implements that method.
63 static ir_graph *get_implementing_graph (ir_entity *method)
66 ir_graph *graph = get_entity_irg ((ir_entity*) method);
68 /* Search upwards in the overwrites graph. */
69 /* GL: this will not work for multiple inheritance */
72 int n_over = get_entity_n_overwrites ((ir_entity*) method);
74 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
75 ir_entity *over = get_entity_overwrites ((ir_entity*) method, i);
76 graph = get_implementing_graph (over);
80 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
81 assert(get_entity_peculiarity(method) == peculiarity_description
82 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
84 /* we *must* always return a graph != NULL, *except* when we're used
85 inside remove_irg or force_description */
86 /* assert (graph && "no graph"); */
90 ir_graph *graph = NULL;
92 if (get_entity_peculiarity(method) != peculiarity_description)
93 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
100 * Add a graph to the set of live graphs.
102 * @param graph the graph to add
103 * @return non-zero if the graph was added, zero
104 * if it was already in the live set
106 static int add_graph (ir_graph *graph)
108 if (!eset_contains (_live_graphs, graph)) {
110 ir_fprintf(stdout, "RTA: new graph of %+F\n", graph);
113 eset_insert (_live_graphs, graph);
121 * Add a class to the set of live classes.
123 * @param clazz the class to add
124 * @return non-zero if the graph was added, zero
125 * if it was already in the live set
127 static int add_class (ir_type *clazz)
129 if (!eset_contains (_live_classes, clazz)) {
131 ir_fprintf(stdout, "RTA: new class: %+F\n", clazz);
134 eset_insert (_live_classes, clazz);
141 /** Given an entity, add all implementing graphs that belong to live classes
144 * Iff additions occurred, return TRUE, else FALSE.
146 static int add_implementing_graphs (ir_entity *method)
149 int n_over = get_entity_n_overwrittenby (method);
150 ir_graph *graph = get_entity_irg (method);
154 graph = get_implementing_graph (method);
158 ir_fprintf(stdout, "RTA: new call to %+F\n", method);
161 if (rta_is_alive_class (get_entity_owner (method))) {
163 change = add_graph (graph);
167 for (i = 0; i < n_over; i ++) {
168 ir_entity *over = get_entity_overwrittenby (method, i);
169 change |= add_implementing_graphs (over);
175 /** Enter all method accesses and all class allocations into
178 * Set *(int*)env to true iff (possibly) new graphs have been found.
180 static void rta_act (ir_node *node, void *env)
182 int *change = (int*) env;
183 ir_opcode op = get_irn_opcode (node);
185 if (iro_Call == op) { /* CALL */
186 ir_entity *ent = NULL;
188 ir_node *ptr = get_Call_ptr (node);
191 if (iro_Sel == get_irn_opcode (ptr)) {
192 ent = get_Sel_entity (ptr);
193 *change |= add_implementing_graphs (ent);
196 } else if (iro_SymConst == get_irn_opcode (ptr)) {
197 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
200 ent = get_SymConst_entity (ptr);
201 graph = get_entity_irg (ent);
203 *change |= add_graph (graph);
205 /* it's an external allocated thing. */
207 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
208 /* Entities of kind addr_name may not be allocated in this compilation unit.
209 If so, the frontend built faulty Firm. So just ignore. */
210 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
211 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
213 /* other symconst. */
214 assert(0 && "This SymConst can not be an address for a method call.");
219 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
222 } else if (iro_Alloc == op) { /* ALLOC */
223 ir_type *type = get_Alloc_type (node);
225 *change |= add_class (type);
230 Traverse the given graph to collect method accesses and
233 static int rta_fill_graph (ir_graph* graph)
236 irg_walk_graph (graph, rta_act, NULL, &change);
240 /** Traverse all graphs to collect method accesses and object allocations.
242 static int rta_fill_incremental (void)
247 #ifdef INTERPROCEDURAL_VIEW
248 int old_ip_view = get_interprocedural_view();
250 set_interprocedural_view(0); /* save this for later */
253 /* init_tables has added main_irg to _live_graphs */
255 /* Need to take care of graphs that are externally
256 visible or sticky. Pretend that they are called: */
258 for (i = 0; i < get_irp_n_irgs(); i++) {
259 ir_graph *graph = get_irp_irg (i);
260 ir_entity *ent = get_irg_entity (graph);
262 if ((visibility_external_visible == get_entity_visibility (ent)) ||
263 (stickyness_sticky == get_entity_stickyness (ent))) {
264 eset_insert (_live_graphs, graph);
265 // printf("external visible: "); DDMG(graph);
273 eset *live_graphs = _live_graphs;
274 _live_graphs = eset_create ();
277 fprintf(stdout, "RTA: RUN %i\n", n_runs);
280 /* collect what we have found previously */
281 eset_insert_all (_live_graphs, live_graphs);
284 for (graph = eset_first (live_graphs);
286 graph = eset_next (live_graphs)) {
289 ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs,
293 rerun |= rta_fill_graph (graph);
296 eset_destroy (live_graphs);
301 #ifdef INTERPROCEDURAL_VIEW
302 set_interprocedural_view(old_ip_view); /* cover up our traces */
309 * Count the number of graphs that we have found to be live.
311 static int stats (void)
314 int n_live_graphs = 0;
315 int n_graphs = get_irp_n_irgs();
317 for (i = 0; i < n_graphs; i++) {
318 ir_graph *graph = get_irp_irg(i);
320 if (rta_is_alive_graph (graph)) {
325 return (n_live_graphs);
328 /* remove a graph, part I */
330 We removed the first graph to implement the entity, so we're
331 abstract now. Pretend that it wasn't there at all, and every
332 entity that used to inherit this entity's graph is now abstract.
334 /* Since we *know* that this entity will not be called, this is OK. */
335 static void force_description (ir_entity *ent, ir_entity *addr)
337 int i, n_over = get_entity_n_overwrittenby (ent);
339 set_entity_peculiarity (ent, peculiarity_description);
341 for (i = 0; i < n_over; i ++) {
342 ir_entity *over = get_entity_overwrittenby (ent, i);
344 if (peculiarity_inherited == get_entity_peculiarity (over)) {
345 /* We rely on the fact that cse is performed on the const_code_irg. */
346 ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
348 if (addr == my_addr) {
349 force_description (over, addr);
351 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
352 /* check whether 'over' forces 'inheritance' of *our* graph: */
353 ir_node *f_addr = get_atomic_ent_value (over);
354 ir_entity *impl_ent = get_SymConst_entity (f_addr);
356 assert(is_SymConst(f_addr) && "can't do complex addrs");
357 if (impl_ent == addr) {
358 assert (0 && "gibt's denn sowas");
359 force_description (over, addr);
366 Initialize the static data structures.
368 static void init_tables (void)
373 _live_classes = eset_create ();
374 _live_graphs = eset_create ();
376 if (get_irp_main_irg ()) {
377 eset_insert (_live_graphs, get_irp_main_irg ());
380 /* Find static allocated classes */
381 tp = get_glob_type();
382 n = get_class_n_members(tp);
383 for (i = 0; i < n; ++i) {
384 ir_type *member_type = get_entity_type(get_class_member(tp, i));
385 if (is_Class_type(member_type))
386 eset_insert(_live_classes, member_type);
390 n = get_struct_n_members(tp);
391 for (i = 0; i < n; ++i) {
392 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
393 if (is_Class_type(member_type))
394 eset_insert(_live_classes, member_type);
399 * Initialize the RTA data structures, and perform RTA.
400 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
402 void rta_init (int do_verbose)
406 int rem_vpi = get_visit_pseudo_irgs();
407 set_visit_pseudo_irgs(1);
409 # ifdef DEBUG_libfirm
412 n = get_irp_n_irgs();
413 for (i = 0; i < n; i++) {
414 irg_vrfy (get_irp_irg(i));
418 # endif /* defined DEBUG_libfirm */
420 verbose = do_verbose;
424 n_runs = rta_fill_incremental ();
427 int n_live_graphs = stats ();
429 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
430 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
431 printf ("RTA: n_runs = %i\n", n_runs);
434 # ifdef DEBUG_libfirm
437 n = get_irp_n_irgs();
438 for (i = 0; i < n; i++) {
439 irg_vrfy (get_irp_irg(i));
443 # endif /* defined DEBUG_libfirm */
445 set_visit_pseudo_irgs(rem_vpi);
449 * walker for all types and entities
451 * Changes the peculiarity of entities that represents
452 * dead graphs to peculiarity_description.
454 static void make_entity_to_description(type_or_ent tore, void *env) {
456 if (is_entity(tore.ent)) {
457 ir_entity *ent = tore.ent;
459 if ((is_Method_type(get_entity_type(ent))) &&
460 (get_entity_peculiarity(ent) != peculiarity_description) &&
461 (get_entity_visibility(ent) != visibility_external_allocated) ) {
462 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
463 if (!eset_contains (_live_graphs, irg)) {
464 set_entity_peculiarity(ent, peculiarity_description);
465 set_entity_irg(ent, NULL);
471 /* Delete all graphs that we have found to be dead from the program
472 If verbose == 1, print statistics, if > 1, chatter about every detail
474 void rta_delete_dead_graphs (void)
477 int n_graphs = get_irp_n_irgs ();
478 ir_graph *graph = NULL;
479 int n_dead_graphs = 0;
480 ir_graph **dead_graphs;
482 int rem_vpi = get_visit_pseudo_irgs();
483 set_visit_pseudo_irgs(1);
485 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
487 for (i = 0; i < n_graphs; i++) {
488 graph = get_irp_irg(i);
490 if (rta_is_alive_graph (graph)) {
491 /* do nothing (except some debugging fprintf`s :-) */
494 ir_entity *ent = get_irg_entity (graph);
495 assert (visibility_external_visible != get_entity_visibility (ent));
498 dead_graphs[n_dead_graphs] = graph;
503 type_walk(make_entity_to_description, NULL, NULL);
504 for (i = 0; i < n_dead_graphs; ++i) {
505 remove_irp_irg (dead_graphs[i]);
509 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
512 set_visit_pseudo_irgs(rem_vpi);
517 /* Clean up the RTA data structures. Call this after calling rta_init */
518 void rta_cleanup (void)
520 # ifdef DEBUG_libfirm
522 for (i = 0; i < get_irp_n_irgs(); i++) {
523 irg_vrfy (get_irp_irg(i));
526 # endif /* defined DEBUG_libfirm */
529 eset_destroy (_live_classes);
530 _live_classes = NULL;
534 eset_destroy (_live_graphs);
539 /* Say whether this class might be instantiated at any point in the program: */
540 int rta_is_alive_class (ir_type *clazz)
542 return (eset_contains (_live_classes, clazz));
545 /* Say whether this graph might be run at any time in the program: */
546 int rta_is_alive_graph (ir_graph *graph)
548 return eset_contains (_live_graphs, graph);
551 /* dump our opinion */
552 void rta_report (void)
556 for (i = 0; i < get_irp_n_types(); ++i) {
557 ir_type *tp = get_irp_type(i);
558 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
559 ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp);
563 for (i = 0; i < get_irp_n_irgs(); i++) {
564 if (rta_is_alive_graph (get_irp_irg(i))) {
565 ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i));