5 * File name: ir/ana/rta.c
6 * Purpose: Interprocedural analysis to improve the call graph estimate.
11 * Copyright: (c) 1999-2004 Universität Karlsruhe
12 * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
26 #include "irgraph_t.h"
38 # endif /* not defined TRUE */
41 static int verbose = 0;
45 static eset *_live_classes = NULL;
47 /* cache computed results */
48 static eset *_live_graphs = NULL;
51 Given a method, find the firm graph that implements that method.
53 static ir_graph *get_implementing_graph (entity *method)
56 ir_graph *graph = get_entity_irg ((entity*) method);
58 /* Search upwards in the overwrites graph. */
59 /* GL: this will not work for multiple inheritance */
62 int n_over = get_entity_n_overwrites ((entity*) method);
64 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
65 entity *over = get_entity_overwrites ((entity*) method, i);
66 graph = get_implementing_graph (over);
70 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
71 assert(get_entity_peculiarity(method) == peculiarity_description
72 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
74 /* we *must* always return a graph != NULL, *except* when we're used
75 inside remove_irg or force_description */
76 /* assert (graph && "no graph"); */
80 ir_graph *graph = NULL;
82 if (get_entity_peculiarity(method) != peculiarity_description)
83 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
90 * Add a graph to the set of live graphs.
92 * @param graph the graph to add
93 * @return non-zero if the graph was added, zero
94 * if it was already in the live set
96 static int add_graph (ir_graph *graph)
98 if (!eset_contains (_live_graphs, graph)) {
100 fprintf(stdout, "RTA: new graph of ");
101 DDMEO(get_irg_entity (graph));
104 eset_insert (_live_graphs, graph);
112 * Add a class to the set of live classes.
114 * @param clazz the class to add
115 * @return non-zero if the graph was added, zero
116 * if it was already in the live set
118 static int add_class (ir_type *clazz)
120 if (!eset_contains (_live_classes, clazz)) {
122 fprintf(stdout, "RTA: new class: ");
126 eset_insert (_live_classes, clazz);
133 /** Given an entity, add all implementing graphs that belong to live classes
136 * Iff additions occurred, return TRUE, else FALSE.
138 static int add_implementing_graphs (entity *method)
141 int n_over = get_entity_n_overwrittenby (method);
142 ir_graph *graph = get_entity_irg (method);
146 graph = get_implementing_graph (method);
150 fprintf(stdout, "RTA: new call to ");
154 if (rta_is_alive_class (get_entity_owner (method))) {
156 change = add_graph (graph);
160 for (i = 0; i < n_over; i ++) {
161 entity *over = get_entity_overwrittenby (method, i);
162 change |= add_implementing_graphs (over);
168 /** Enter all method accesses and all class allocations into
171 * Set *(int*)env to true iff (possibly) new graphs have been found.
173 static void rta_act (ir_node *node, void *env)
175 int *change = (int*) env;
176 opcode op = get_irn_opcode (node);
178 if (iro_Call == op) { /* CALL */
181 ir_node *ptr = get_Call_ptr (node);
184 if (iro_Sel == get_irn_opcode (ptr)) {
185 ent = get_Sel_entity (ptr);
186 *change |= add_implementing_graphs (ent);
189 } else if (iro_SymConst == get_irn_opcode (ptr)) {
190 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
193 ent = get_SymConst_entity (ptr);
194 graph = get_entity_irg (ent);
196 *change |= add_graph (graph);
198 /* it's an external allocated thing. */
200 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
201 /* Entities of kind addr_name may not be allocated in this compilation unit.
202 If so, the frontend built faulty Firm. So just ignore. */
203 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
204 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
206 /* other symconst. */
207 assert(0 && "This SymConst can not be an address for a method call.");
213 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
216 } else if (iro_Alloc == op) { /* ALLOC */
217 ir_type *type = get_Alloc_type (node);
219 *change |= add_class (type);
224 Traverse the given graph to collect method accesses and
227 static int rta_fill_graph (ir_graph* graph)
230 irg_walk_graph (graph, rta_act, NULL, &change);
234 /** Traverse all graphs to collect method accesses and object allocations.
236 static int rta_fill_incremental (void)
241 int old_ip_view = get_interprocedural_view();
243 set_interprocedural_view(0); /* save this for later */
245 /* init_tables has added main_irg to _live_graphs */
247 /* Need to take care of graphs that are externally
248 visible or sticky. Pretend that they are called: */
250 for (i = 0; i < get_irp_n_irgs(); i++) {
251 ir_graph *graph = get_irp_irg (i);
252 entity *ent = get_irg_entity (graph);
254 if ((visibility_external_visible == get_entity_visibility (ent)) ||
255 (stickyness_sticky == get_entity_stickyness (ent))) {
256 eset_insert (_live_graphs, graph);
257 // printf("external visible: "); DDMG(graph);
265 eset *live_graphs = _live_graphs;
266 _live_graphs = eset_create ();
269 fprintf(stdout, "RTA: RUN %i\n", n_runs);
272 /* collect what we have found previously */
273 eset_insert_all (_live_graphs, live_graphs);
276 for (graph = eset_first (live_graphs);
278 graph = eset_next (live_graphs)) {
281 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
282 DDMEO(get_irg_entity (graph));
285 rerun |= rta_fill_graph (graph);
288 eset_destroy (live_graphs);
293 set_interprocedural_view(old_ip_view); /* cover up our traces */
299 * Count the number of graphs that we have found to be live.
301 static int stats (void)
304 int n_live_graphs = 0;
305 int n_graphs = get_irp_n_irgs();
307 for (i = 0; i < n_graphs; i++) {
308 ir_graph *graph = get_irp_irg(i);
310 if (rta_is_alive_graph (graph)) {
315 return (n_live_graphs);
318 /* remove a graph, part I */
320 We removed the first graph to implement the entity, so we're
321 abstract now. Pretend that it wasn't there at all, and every
322 entity that used to inherit this entity's graph is now abstract.
324 /* Since we *know* that this entity will not be called, this is OK. */
325 static void force_description (entity *ent, entity *addr)
327 int i, n_over = get_entity_n_overwrittenby (ent);
329 set_entity_peculiarity (ent, peculiarity_description);
331 for (i = 0; i < n_over; i ++) {
332 entity *over = get_entity_overwrittenby (ent, i);
334 if (peculiarity_inherited == get_entity_peculiarity (over)) {
335 /* We rely on the fact that cse is performed on the const_code_irg. */
336 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
338 if (addr == my_addr) {
339 force_description (over, addr);
341 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
342 /* check whether 'over' forces 'inheritance' of *our* graph: */
343 ir_node *f_addr = get_atomic_ent_value (over);
344 entity *impl_ent = get_SymConst_entity (f_addr);
346 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
347 if (impl_ent == addr) {
348 assert (0 && "gibt's denn sowas");
349 force_description (over, addr);
356 Initialize the static data structures.
358 static void init_tables (void)
363 _live_classes = eset_create ();
364 _live_graphs = eset_create ();
366 if (get_irp_main_irg ()) {
367 eset_insert (_live_graphs, get_irp_main_irg ());
370 /* Find static allocated classes */
371 tp = get_glob_type();
372 n = get_class_n_members(tp);
373 for (i = 0; i < n; ++i) {
374 ir_type *member_type = get_entity_type(get_class_member(tp, i));
375 if (is_Class_type(member_type))
376 eset_insert(_live_classes, member_type);
380 n = get_struct_n_members(tp);
381 for (i = 0; i < n; ++i) {
382 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
383 if (is_Class_type(member_type))
384 eset_insert(_live_classes, member_type);
389 * Initialize the RTA data structures, and perform RTA.
390 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
392 void rta_init (int do_verbose)
396 int rem_vpi = get_visit_pseudo_irgs();
397 set_visit_pseudo_irgs(1);
399 # ifdef DEBUG_libfirm
402 n = get_irp_n_irgs();
403 for (i = 0; i < n; i++) {
404 irg_vrfy (get_irp_irg(i));
408 # endif /* defined DEBUG_libfirm */
410 verbose = do_verbose;
414 n_runs = rta_fill_incremental ();
417 int n_live_graphs = stats ();
419 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
420 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
421 printf ("RTA: n_runs = %i\n", n_runs);
424 # ifdef DEBUG_libfirm
427 for (i = 0; i < n; i++) {
428 irg_vrfy (get_irp_irg(i));
432 # endif /* defined DEBUG_libfirm */
434 set_visit_pseudo_irgs(rem_vpi);
438 * walker for all types and entities
440 * Changes the peculiarity of entities that represents
441 * dead graphs to peculiarity_description.
443 static void make_entity_to_description(type_or_ent *tore, void *env) {
444 if (get_kind(tore) == k_entity) {
445 entity *ent = (entity *)tore;
447 if ((is_Method_type(get_entity_type(ent))) &&
448 (get_entity_peculiarity(ent) != peculiarity_description) &&
449 (get_entity_visibility(ent) != visibility_external_allocated) ) {
450 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
451 if (!eset_contains (_live_graphs, irg)) {
452 set_entity_peculiarity(ent, peculiarity_description);
453 set_entity_irg(ent, NULL);
459 /* Delete all graphs that we have found to be dead from the program
460 If verbose == 1, print statistics, if > 1, chatter about every detail
462 void rta_delete_dead_graphs (void)
465 int n_graphs = get_irp_n_irgs ();
466 ir_graph *graph = NULL;
467 int n_dead_graphs = 0;
468 ir_graph **dead_graphs;
470 int rem_vpi = get_visit_pseudo_irgs();
471 set_visit_pseudo_irgs(1);
473 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
475 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
477 for (i = 0; i < n_graphs; i++) {
478 graph = get_irp_irg(i);
480 if (rta_is_alive_graph (graph)) {
481 /* do nothing (except some debugging fprintf`s :-) */
483 # ifdef DEBUG_libfirm
484 entity *ent = get_irg_entity (graph);
485 assert (visibility_external_visible != get_entity_visibility (ent));
486 # endif /* defined DEBUG_libfirm */
488 dead_graphs[n_dead_graphs] = graph;
493 type_walk(make_entity_to_description, NULL, NULL);
494 for (i = 0; i < n_dead_graphs; ++i) {
495 remove_irp_irg (dead_graphs[i]);
499 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
502 set_visit_pseudo_irgs(rem_vpi);
507 /* Clean up the RTA data structures. Call this after calling rta_init */
508 void rta_cleanup (void)
510 # ifdef DEBUG_libfirm
512 for (i = 0; i < get_irp_n_irgs(); i++) {
513 irg_vrfy (get_irp_irg(i));
516 # endif /* defined DEBUG_libfirm */
519 eset_destroy (_live_classes);
520 _live_classes = NULL;
524 eset_destroy (_live_graphs);
529 /* Say whether this class might be instantiated at any point in the program: */
530 int rta_is_alive_class (ir_type *clazz)
532 return (eset_contains (_live_classes, clazz));
535 /* Say whether this graph might be run at any time in the program: */
536 int rta_is_alive_graph (ir_graph *graph)
538 return eset_contains (_live_graphs, graph);
541 /* dump our opinion */
542 void rta_report (void)
546 for (i = 0; i < get_irp_n_types(); ++i) {
547 ir_type *tp = get_irp_type(i);
548 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
549 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
553 for (i = 0; i < get_irp_n_irgs(); i++) {
554 if (rta_is_alive_graph (get_irp_irg(i))) {
555 fprintf(stdout, "RTA: considered called: graph of ");
556 DDMEO(get_irg_entity (get_irp_irg(i)));
564 * Revision 1.37 2006/12/11 15:28:48 matze
565 * - Several warning fixes
566 * - Fixes for compilation without DEBUG_libfirm
567 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
569 * Revision 1.36 2006/06/05 15:58:12 beck
570 * added support for Thread local storage
571 * added more doxygen docu
573 * Revision 1.35 2006/01/13 21:51:59 beck
574 * renamed all types 'type' to 'ir_type'
576 * Revision 1.34 2006/01/02 15:01:16 beck
577 * missing include added
579 * Revision 1.33 2005/11/17 17:26:57 beck
580 * removed bool type and depency from stdbool.h (not C89)
582 * Revision 1.32 2005/01/05 14:24:52 beck
583 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
585 * Revision 1.31 2004/12/21 13:45:14 beck
586 * removed C99 constructs
588 * Revision 1.30 2004/12/02 16:16:11 beck
589 * fixed config.h include
590 * used xmalloc instead of malloc
592 * Revision 1.29 2004/11/11 13:28:08 goetz
593 * made pseudo irg aware
595 * Revision 1.28 2004/11/03 14:47:18 beck
596 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
598 * Revision 1.27 2004/10/21 07:23:34 goetz
601 * Revision 1.26 2004/10/20 14:59:27 liekweg
604 * Revision 1.25 2004/10/18 12:47:08 liekweg
607 * Revision 1.24 2004/09/24 13:59:04 beck
608 * fixed doxygen comments, removed initialization for description entities
610 * Revision 1.23 2004/08/19 16:51:02 goetz
611 * fixed some errors, pushed closer to inteded firm semantics
613 * Revision 1.22 2004/08/13 08:57:15 beyhan
614 * normalized names of functions, enums ...
615 * added suffix as argument to dumpers, removed global variable
616 * removed support for tarval/Const
618 * Revision 1.21 2004/07/08 15:50:56 goetz
621 * Revision 1.20 2004/07/08 11:17:40 goetz
622 * *** empty log message ***
624 * Revision 1.19 2004/07/06 12:30:37 beyhan
625 * new SymConst semantics
627 * Revision 1.18 2004/06/27 21:17:41 liekweg
630 * Revision 1.17 2004/06/25 13:45:13 liekweg
631 * observe stickyness; minor refactoring
633 * Revision 1.16 2004/06/24 06:42:14 goetz
636 * Revision 1.15 2004/06/18 15:47:19 liekweg
637 * minor bug fix (go forward, not backward) --flo
639 * Revision 1.14 2004/06/18 13:12:43 liekweg
640 * final bug fix (calls via consts)
642 * Revision 1.13 2004/06/17 16:34:33 liekweg
645 * Revision 1.12 2004/06/17 16:33:33 liekweg
648 * Revision 1.11 2004/06/17 14:21:13 liekweg
651 * Revision 1.10 2004/06/17 10:31:41 goetz
652 * irscc: bugfix, can now deal with loops not reachable from start
653 * cgana: bugfix, skip_Tuple
656 * Revision 1.9 2004/06/17 08:56:03 liekweg
657 * Fixed typos in comments
659 * Revision 1.8 2004/06/17 08:33:01 liekweg
660 * Added comments; added remove_irg
662 * Revision 1.6 2004/06/14 13:02:03 goetz
665 * Revision 1.5 2004/06/13 15:03:45 liekweg
666 * RTA auf Iterative RTA aufgebohrt --flo
668 * Revision 1.4 2004/06/12 19:35:04 liekweg
669 * Kommentare eingef"ugt --flo
671 * Revision 1.3 2004/06/12 17:09:46 liekweg
672 * RTA works, outedges breaks. "Yay." --flo
674 * Revision 1.2 2004/06/11 18:25:39 liekweg
677 * Revision 1.1 2004/06/11 18:24:18 liekweg