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)));
89 static int add_graph (ir_graph *graph)
91 if (!eset_contains (_live_graphs, graph)) {
93 fprintf(stdout, "RTA: new graph of ");
94 DDMEO(get_irg_entity (graph));
97 eset_insert (_live_graphs, graph);
104 static int add_class (ir_type *clazz)
106 if (!eset_contains (_live_classes, clazz)) {
108 fprintf(stdout, "RTA: new class: ");
112 eset_insert (_live_classes, clazz);
119 /** Given an entity, add all implementing graphs that belong to live classes
122 * Iff additions occurred, return TRUE, else FALSE.
124 static int add_implementing_graphs (entity *method)
127 int n_over = get_entity_n_overwrittenby (method);
128 ir_graph *graph = get_entity_irg (method);
132 graph = get_implementing_graph (method);
136 fprintf(stdout, "RTA: new call to ");
140 if (rta_is_alive_class (get_entity_owner (method))) {
142 change = add_graph (graph);
146 for (i = 0; i < n_over; i ++) {
147 entity *over = get_entity_overwrittenby (method, i);
148 change |= add_implementing_graphs (over);
154 /** Enter all method accesses and all class allocations into
157 * Set *(int*)env to true iff (possibly) new graphs have been found.
159 static void rta_act (ir_node *node, void *env)
161 int *change = (int*) env;
163 opcode op = get_irn_opcode (node);
165 if (iro_Call == op) { /* CALL */
168 ir_node *ptr = get_Call_ptr (node);
171 if (iro_Sel == get_irn_opcode (ptr)) {
172 ent = get_Sel_entity (ptr);
173 *change |= add_implementing_graphs (ent);
176 } else if (iro_SymConst == get_irn_opcode (ptr)) {
177 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
180 ent = get_SymConst_entity (ptr);
181 graph = get_entity_irg (ent);
183 *change |= add_graph (graph);
185 /* it's an external allocated thing. */
187 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
188 /* Entities of kind addr_name may not be allocated in this compilation unit.
189 If so, the frontend built faulty Firm. So just ignore. */
190 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
191 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
193 /* other symconst. */
194 assert(0 && "This SymConst can not be an address for a method call.");
200 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
203 } else if (iro_Alloc == op) { /* ALLOC */
204 ir_type *type = get_Alloc_type (node);
206 *change |= add_class (type);
211 Traverse the given graph to collect method accesses and
214 static int rta_fill_graph (ir_graph* graph)
218 current_ir_graph = graph;
220 irg_walk_graph (graph, rta_act, NULL, &change);
225 /** Traverse all graphs to collect method accesses and object allocations.
227 static int rta_fill_incremental (void)
232 int old_ip_view = get_interprocedural_view();
234 set_interprocedural_view(0); /* save this for later */
236 /* init_tables has added main_irg to _live_graphs */
238 /* Need to take care of graphs that are externally
239 visible or sticky. Pretend that they are called: */
241 for (i = 0; i < get_irp_n_irgs(); i++) {
242 ir_graph *graph = get_irp_irg (i);
243 entity *ent = get_irg_entity (graph);
245 if ((visibility_external_visible == get_entity_visibility (ent)) ||
246 (stickyness_sticky == get_entity_stickyness (ent))) {
247 eset_insert (_live_graphs, graph);
248 // printf("external visible: "); DDMG(graph);
256 eset *live_graphs = _live_graphs;
257 _live_graphs = eset_create ();
260 fprintf(stdout, "RTA: RUN %i\n", n_runs);
263 /* collect what we have found previously */
264 eset_insert_all (_live_graphs, live_graphs);
267 for (graph = eset_first (live_graphs);
269 graph = eset_next (live_graphs)) {
272 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
273 DDMEO(get_irg_entity (graph));
276 rerun |= rta_fill_graph (graph);
279 eset_destroy (live_graphs);
284 set_interprocedural_view(old_ip_view); /* cover up our traces */
290 * Count the number of graphs that we have found to be live.
292 static int stats (void)
295 int n_live_graphs = 0;
296 int n_graphs = get_irp_n_irgs();
298 for (i = 0; i < n_graphs; i++) {
299 ir_graph *graph = get_irp_irg(i);
301 if (rta_is_alive_graph (graph)) {
306 return (n_live_graphs);
309 /* remove a graph, part I */
311 We removed the first graph to implement the entity, so we're
312 abstract now. Pretend that it wasn't there at all, and every
313 entity that used to inherit this entity's graph is now abstract.
315 /* Since we *know* that this entity will not be called, this is OK. */
316 static void force_description (entity *ent, entity *addr)
318 int i, n_over = get_entity_n_overwrittenby (ent);
320 set_entity_peculiarity (ent, peculiarity_description);
322 for (i = 0; i < n_over; i ++) {
323 entity *over = get_entity_overwrittenby (ent, i);
325 if (peculiarity_inherited == get_entity_peculiarity (over)) {
326 /* We rely on the fact that cse is performed on the const_code_irg. */
327 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
329 if (addr == my_addr) {
330 force_description (over, addr);
332 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
333 /* check whether 'over' forces 'inheritance' of *our* graph: */
334 ir_node *f_addr = get_atomic_ent_value (over);
335 entity *impl_ent = get_SymConst_entity (f_addr);
337 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
338 if (impl_ent == addr) {
339 assert (0 && "gibt's denn sowas");
340 force_description (over, addr);
347 Initialize the static data structures.
349 static void init_tables (void)
351 int i, n_globs = get_class_n_members(get_glob_type());
353 _live_classes = eset_create ();
354 _live_graphs = eset_create ();
356 if (get_irp_main_irg ()) {
357 eset_insert (_live_graphs, get_irp_main_irg ());
360 /* Find static allocated classes */
361 for (i = 0; i < n_globs; ++i) {
362 ir_type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
363 if (is_Class_type(member_type))
364 eset_insert(_live_classes, member_type);
369 * Initialize the RTA data structures, and perform RTA.
370 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
372 void rta_init (int do_verbose)
376 int rem_vpi = get_visit_pseudo_irgs();
377 set_visit_pseudo_irgs(1);
379 # ifdef DEBUG_libfirm
380 for (i = 0; i < get_irp_n_irgs(); i++) {
381 irg_vrfy (get_irp_irg(i));
384 # endif /* defined DEBUG_libfirm */
386 verbose = do_verbose;
390 n_runs = rta_fill_incremental ();
393 int n_live_graphs = stats ();
395 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
396 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
397 printf ("RTA: n_runs = %i\n", n_runs);
400 # ifdef DEBUG_libfirm
401 for (i = 0; i < get_irp_n_irgs(); i++) {
402 irg_vrfy (get_irp_irg(i));
405 # endif /* defined DEBUG_libfirm */
407 set_visit_pseudo_irgs(rem_vpi);
411 * walker for all types and entities
413 * Changes the peculiarity of entities that represents
414 * dead graphs to peculiarity_description.
416 static void make_entity_to_description(type_or_ent *tore, void *env) {
417 if (get_kind(tore) == k_entity) {
418 entity *ent = (entity *)tore;
420 if ((is_Method_type(get_entity_type(ent))) &&
421 (get_entity_peculiarity(ent) != peculiarity_description) &&
422 (get_entity_visibility(ent) != visibility_external_allocated) ) {
423 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
424 if (!eset_contains (_live_graphs, irg)) {
425 set_entity_peculiarity(ent, peculiarity_description);
426 set_entity_irg(ent, NULL);
432 /* Delete all graphs that we have found to be dead from the program
433 If verbose == 1, print statistics, if > 1, chatter about every detail
435 void rta_delete_dead_graphs (void)
438 int n_graphs = get_irp_n_irgs ();
439 ir_graph *graph = NULL;
440 int n_dead_graphs = 0;
441 ir_graph **dead_graphs;
443 int rem_vpi = get_visit_pseudo_irgs();
444 set_visit_pseudo_irgs(1);
446 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
448 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
450 for (i = 0; i < n_graphs; i++) {
451 graph = get_irp_irg(i);
453 if (rta_is_alive_graph (graph)) {
454 /* do nothing (except some debugging fprintf`s :-) */
456 # ifdef DEBUG_libfirm
457 entity *ent = get_irg_entity (graph);
458 assert (visibility_external_visible != get_entity_visibility (ent));
459 # endif /* defined DEBUG_libfirm */
461 dead_graphs[n_dead_graphs] = graph;
466 type_walk(make_entity_to_description, NULL, NULL);
467 for (i = 0; i < n_dead_graphs; ++i) {
468 remove_irp_irg (dead_graphs[i]);
472 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
475 set_visit_pseudo_irgs(rem_vpi);
480 /* Clean up the RTA data structures. Call this after calling rta_init */
481 void rta_cleanup (void)
483 # ifdef DEBUG_libfirm
485 for (i = 0; i < get_irp_n_irgs(); i++) {
486 irg_vrfy (get_irp_irg(i));
489 # endif /* defined DEBUG_libfirm */
492 eset_destroy (_live_classes);
493 _live_classes = NULL;
497 eset_destroy (_live_graphs);
502 /* Say whether this class might be instantiated at any point in the program: */
503 int rta_is_alive_class (ir_type *clazz)
505 return (eset_contains (_live_classes, clazz));
508 /* Say whether this graph might be run at any time in the program: */
509 int rta_is_alive_graph (ir_graph *graph)
511 return eset_contains (_live_graphs, graph);
514 /* dump our opinion */
515 void rta_report (void)
519 for (i = 0; i < get_irp_n_types(); ++i) {
520 ir_type *tp = get_irp_type(i);
521 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
522 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
526 for (i = 0; i < get_irp_n_irgs(); i++) {
527 if (rta_is_alive_graph (get_irp_irg(i))) {
528 fprintf(stdout, "RTA: considered called: graph of ");
529 DDMEO(get_irg_entity (get_irp_irg(i)));
537 * Revision 1.35 2006/01/13 21:51:59 beck
538 * renamed all types 'type' to 'ir_type'
540 * Revision 1.34 2006/01/02 15:01:16 beck
541 * missing include added
543 * Revision 1.33 2005/11/17 17:26:57 beck
544 * removed bool type and depency from stdbool.h (not C89)
546 * Revision 1.32 2005/01/05 14:24:52 beck
547 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
549 * Revision 1.31 2004/12/21 13:45:14 beck
550 * removed C99 constructs
552 * Revision 1.30 2004/12/02 16:16:11 beck
553 * fixed config.h include
554 * used xmalloc instead of malloc
556 * Revision 1.29 2004/11/11 13:28:08 goetz
557 * made pseudo irg aware
559 * Revision 1.28 2004/11/03 14:47:18 beck
560 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
562 * Revision 1.27 2004/10/21 07:23:34 goetz
565 * Revision 1.26 2004/10/20 14:59:27 liekweg
568 * Revision 1.25 2004/10/18 12:47:08 liekweg
571 * Revision 1.24 2004/09/24 13:59:04 beck
572 * fixed doxygen comments, removed initialization for description entities
574 * Revision 1.23 2004/08/19 16:51:02 goetz
575 * fixed some errors, pushed closer to inteded firm semantics
577 * Revision 1.22 2004/08/13 08:57:15 beyhan
578 * normalized names of functions, enums ...
579 * added suffix as argument to dumpers, removed global variable
580 * removed support for tarval/Const
582 * Revision 1.21 2004/07/08 15:50:56 goetz
585 * Revision 1.20 2004/07/08 11:17:40 goetz
586 * *** empty log message ***
588 * Revision 1.19 2004/07/06 12:30:37 beyhan
589 * new SymConst semantics
591 * Revision 1.18 2004/06/27 21:17:41 liekweg
594 * Revision 1.17 2004/06/25 13:45:13 liekweg
595 * observe stickyness; minor refactoring
597 * Revision 1.16 2004/06/24 06:42:14 goetz
600 * Revision 1.15 2004/06/18 15:47:19 liekweg
601 * minor bug fix (go forward, not backward) --flo
603 * Revision 1.14 2004/06/18 13:12:43 liekweg
604 * final bug fix (calls via consts)
606 * Revision 1.13 2004/06/17 16:34:33 liekweg
609 * Revision 1.12 2004/06/17 16:33:33 liekweg
612 * Revision 1.11 2004/06/17 14:21:13 liekweg
615 * Revision 1.10 2004/06/17 10:31:41 goetz
616 * irscc: bugfix, can now deal with loops not reachable from start
617 * cgana: bugfix, skip_Tuple
620 * Revision 1.9 2004/06/17 08:56:03 liekweg
621 * Fixed typos in comments
623 * Revision 1.8 2004/06/17 08:33:01 liekweg
624 * Added comments; added remove_irg
626 * Revision 1.6 2004/06/14 13:02:03 goetz
629 * Revision 1.5 2004/06/13 15:03:45 liekweg
630 * RTA auf Iterative RTA aufgebohrt --flo
632 * Revision 1.4 2004/06/12 19:35:04 liekweg
633 * Kommentare eingef"ugt --flo
635 * Revision 1.3 2004/06/12 17:09:46 liekweg
636 * RTA works, outedges breaks. "Yay." --flo
638 * Revision 1.2 2004/06/11 18:25:39 liekweg
641 * Revision 1.1 2004/06/11 18:24:18 liekweg