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"
37 # endif /* not defined TRUE */
40 static int verbose = 0;
44 static eset *_live_classes = NULL;
46 /* cache computed results */
47 static eset *_live_graphs = NULL;
50 Given a method, find the firm graph that implements that method.
52 static ir_graph *get_implementing_graph (entity *method)
55 ir_graph *graph = get_entity_irg ((entity*) method);
57 /* Search upwards in the overwrites graph. */
58 /* GL: this will not work for multiple inheritance */
61 int n_over = get_entity_n_overwrites ((entity*) method);
63 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
64 entity *over = get_entity_overwrites ((entity*) method, i);
65 graph = get_implementing_graph (over);
69 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
70 assert(get_entity_peculiarity(method) == peculiarity_description
71 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
73 /* we *must* always return a graph != NULL, *except* when we're used
74 inside remove_irg or force_description */
75 /* assert (graph && "no graph"); */
79 ir_graph *graph = NULL;
81 if (get_entity_peculiarity(method) != peculiarity_description)
82 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
88 static int add_graph (ir_graph *graph)
90 if (!eset_contains (_live_graphs, graph)) {
92 fprintf(stdout, "RTA: new graph of ");
93 DDMEO(get_irg_entity (graph));
96 eset_insert (_live_graphs, graph);
103 static int add_class (type *clazz)
105 if (!eset_contains (_live_classes, clazz)) {
107 fprintf(stdout, "RTA: new class: ");
111 eset_insert (_live_classes, clazz);
118 /** Given an entity, add all implementing graphs that belong to live classes
121 * Iff additions occurred, return TRUE, else FALSE.
123 static int add_implementing_graphs (entity *method)
126 int n_over = get_entity_n_overwrittenby (method);
127 ir_graph *graph = get_entity_irg (method);
131 graph = get_implementing_graph (method);
135 fprintf(stdout, "RTA: new call to ");
139 if (rta_is_alive_class (get_entity_owner (method))) {
141 change = add_graph (graph);
145 for (i = 0; i < n_over; i ++) {
146 entity *over = get_entity_overwrittenby (method, i);
147 change |= add_implementing_graphs (over);
153 /** Enter all method accesses and all class allocations into
156 * Set *(int*)env to true iff (possibly) new graphs have been found.
158 static void rta_act (ir_node *node, void *env)
160 int *change = (int*) env;
162 opcode op = get_irn_opcode (node);
164 if (iro_Call == op) { /* CALL */
167 ir_node *ptr = get_Call_ptr (node);
170 if (iro_Sel == get_irn_opcode (ptr)) {
171 ent = get_Sel_entity (ptr);
172 *change |= add_implementing_graphs (ent);
175 } else if (iro_SymConst == get_irn_opcode (ptr)) {
176 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
179 ent = get_SymConst_entity (ptr);
180 graph = get_entity_irg (ent);
182 *change |= add_graph (graph);
184 /* it's an external allocated thing. */
186 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
187 /* Entities of kind addr_name may not be allocated in this compilation unit.
188 If so, the frontend built faulty Firm. So just ignore. */
189 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
190 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
192 /* other symconst. */
193 assert(0 && "This SymConst can not be an address for a method call.");
199 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
202 } else if (iro_Alloc == op) { /* ALLOC */
203 type *type = get_Alloc_type (node);
205 *change |= add_class (type);
210 Traverse the given graph to collect method accesses and
213 static int rta_fill_graph (ir_graph* graph)
217 current_ir_graph = graph;
219 irg_walk_graph (graph, rta_act, NULL, &change);
224 /** Traverse all graphs to collect method accesses and object allocations.
226 * @param rerun Whether to rely on is_alive in a second run
228 static int rta_fill_incremental (void)
233 int old_ip_view = get_interprocedural_view();
235 set_interprocedural_view(false); /* save this for later */
237 /* init_tables has added main_irg to _live_graphs */
239 /* Need to take care of graphs that are externally
240 visible or sticky. Pretend that they are called: */
242 for (i = 0; i < get_irp_n_irgs(); i++) {
243 ir_graph *graph = get_irp_irg (i);
244 entity *ent = get_irg_entity (graph);
246 if ((visibility_external_visible == get_entity_visibility (ent)) ||
247 (stickyness_sticky == get_entity_stickyness (ent))) {
248 eset_insert (_live_graphs, graph);
249 // printf("external visible: "); DDMG(graph);
257 eset *live_graphs = _live_graphs;
258 _live_graphs = eset_create ();
261 fprintf(stdout, "RTA: RUN %i\n", n_runs);
264 /* collect what we have found previously */
265 eset_insert_all (_live_graphs, live_graphs);
268 for (graph = eset_first (live_graphs);
270 graph = eset_next (live_graphs)) {
273 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
274 DDMEO(get_irg_entity (graph));
277 rerun |= rta_fill_graph (graph);
280 eset_destroy (live_graphs);
285 set_interprocedural_view(old_ip_view); /* cover up our traces */
291 * Count the number of graphs that we have found to be live.
293 static int stats (void)
296 int n_live_graphs = 0;
297 int n_graphs = get_irp_n_irgs();
299 for (i = 0; i < n_graphs; i++) {
300 ir_graph *graph = get_irp_irg(i);
302 if (rta_is_alive_graph (graph)) {
307 return (n_live_graphs);
310 /* remove a graph, part I */
312 We removed the first graph to implement the entity, so we're
313 abstract now. Pretend that it wasn't there at all, and every
314 entity that used to inherit this entity's graph is now abstract.
316 /* Since we *know* that this entity will not be called, this is OK. */
317 static void force_description (entity *ent, entity *addr)
319 int i, n_over = get_entity_n_overwrittenby (ent);
321 set_entity_peculiarity (ent, peculiarity_description);
323 for (i = 0; i < n_over; i ++) {
324 entity *over = get_entity_overwrittenby (ent, i);
326 if (peculiarity_inherited == get_entity_peculiarity (over)) {
327 /* We rely on the fact that cse is performed on the const_code_irg. */
328 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
330 if (addr == my_addr) {
331 force_description (over, addr);
333 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
334 /* check whether 'over' forces 'inheritance' of *our* graph: */
335 ir_node *f_addr = get_atomic_ent_value (over);
336 entity *impl_ent = get_SymConst_entity (f_addr);
338 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
339 if (impl_ent == addr) {
340 assert (0 && "gibt's denn sowas");
341 force_description (over, addr);
348 Initialize the static data structures.
350 static void init_tables (void)
352 int i, n_globs = get_class_n_members(get_glob_type());
354 _live_classes = eset_create ();
355 _live_graphs = eset_create ();
357 if (get_irp_main_irg ()) {
358 eset_insert (_live_graphs, get_irp_main_irg ());
361 /* Find static allocated classes */
362 for (i = 0; i < n_globs; ++i) {
363 type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
364 if (is_class_type(member_type))
365 eset_insert(_live_classes, member_type);
370 * Initialize the RTA data structures, and perform RTA.
371 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
373 void rta_init (int do_verbose)
377 int rem_vpi = get_visit_pseudo_irgs();
378 set_visit_pseudo_irgs(1);
380 # ifdef DEBUG_libfirm
381 for (i = 0; i < get_irp_n_irgs(); i++) {
382 irg_vrfy (get_irp_irg(i));
385 # endif /* defined DEBUG_libfirm */
387 verbose = do_verbose;
391 n_runs = rta_fill_incremental ();
394 int n_live_graphs = stats ();
396 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
397 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
398 printf ("RTA: n_runs = %i\n", n_runs);
401 # ifdef DEBUG_libfirm
402 for (i = 0; i < get_irp_n_irgs(); i++) {
403 irg_vrfy (get_irp_irg(i));
406 # endif /* defined DEBUG_libfirm */
408 set_visit_pseudo_irgs(rem_vpi);
412 * walker for all types and entities
414 * Changes the peculiarity of entities that represents
415 * dead graphs to peculiarity_description.
417 static void make_entity_to_description(type_or_ent *tore, void *env) {
418 if (get_kind(tore) == k_entity) {
419 entity *ent = (entity *)tore;
421 if ((is_method_type(get_entity_type(ent))) &&
422 (get_entity_peculiarity(ent) != peculiarity_description) &&
423 (get_entity_visibility(ent) != visibility_external_allocated) ) {
424 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
425 if (!eset_contains (_live_graphs, irg)) {
426 set_entity_peculiarity(ent, peculiarity_description);
427 set_entity_irg(ent, NULL);
433 /* Delete all graphs that we have found to be dead from the program
434 If verbose == 1, print statistics, if > 1, chatter about every detail
436 void rta_delete_dead_graphs (void)
439 int n_graphs = get_irp_n_irgs ();
440 ir_graph *graph = NULL;
441 int n_dead_graphs = 0;
442 ir_graph **dead_graphs;
444 int rem_vpi = get_visit_pseudo_irgs();
445 set_visit_pseudo_irgs(1);
447 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
449 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
451 for (i = 0; i < n_graphs; i++) {
452 graph = get_irp_irg(i);
454 if (rta_is_alive_graph (graph)) {
455 /* do nothing (except some debugging fprintf`s :-) */
457 # ifdef DEBUG_libfirm
458 entity *ent = get_irg_entity (graph);
459 assert (visibility_external_visible != get_entity_visibility (ent));
460 # endif /* defined DEBUG_libfirm */
462 dead_graphs[n_dead_graphs] = graph;
467 type_walk(make_entity_to_description, NULL, NULL);
468 for (i = 0; i < n_dead_graphs; ++i) {
469 remove_irp_irg (dead_graphs[i]);
473 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
476 set_visit_pseudo_irgs(rem_vpi);
481 /* Clean up the RTA data structures. Call this after calling rta_init */
482 void rta_cleanup (void)
484 # ifdef DEBUG_libfirm
486 for (i = 0; i < get_irp_n_irgs(); i++) {
487 irg_vrfy (get_irp_irg(i));
490 # endif /* defined DEBUG_libfirm */
493 eset_destroy (_live_classes);
494 _live_classes = NULL;
498 eset_destroy (_live_graphs);
503 /* Say whether this class might be instantiated at any point in the program: */
504 int rta_is_alive_class (type *clazz)
506 return (eset_contains (_live_classes, clazz));
509 /* Say whether this graph might be run at any time in the program: */
510 int rta_is_alive_graph (ir_graph *graph)
512 return eset_contains (_live_graphs, graph);
515 /* dump our opinion */
516 void rta_report (void)
520 for (i = 0; i < get_irp_n_types(); ++i) {
521 type *tp = get_irp_type(i);
522 if (is_class_type(tp) && rta_is_alive_class(tp)) {
523 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
527 for (i = 0; i < get_irp_n_irgs(); i++) {
528 if (rta_is_alive_graph (get_irp_irg(i))) {
529 fprintf(stdout, "RTA: considered called: graph of ");
530 DDMEO(get_irg_entity (get_irp_irg(i)));
538 * Revision 1.31 2004/12/21 13:45:14 beck
539 * removed C99 constructs
541 * Revision 1.30 2004/12/02 16:16:11 beck
542 * fixed config.h include
543 * used xmalloc instead of malloc
545 * Revision 1.29 2004/11/11 13:28:08 goetz
546 * made pseudo irg aware
548 * Revision 1.28 2004/11/03 14:47:18 beck
549 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
551 * Revision 1.27 2004/10/21 07:23:34 goetz
554 * Revision 1.26 2004/10/20 14:59:27 liekweg
557 * Revision 1.25 2004/10/18 12:47:08 liekweg
560 * Revision 1.24 2004/09/24 13:59:04 beck
561 * fixed doxygen comments, removed initialization for description entities
563 * Revision 1.23 2004/08/19 16:51:02 goetz
564 * fixed some errors, pushed closer to inteded firm semantics
566 * Revision 1.22 2004/08/13 08:57:15 beyhan
567 * normalized names of functions, enums ...
568 * added suffix as argument to dumpers, removed global variable
569 * removed support for tarval/Const
571 * Revision 1.21 2004/07/08 15:50:56 goetz
574 * Revision 1.20 2004/07/08 11:17:40 goetz
575 * *** empty log message ***
577 * Revision 1.19 2004/07/06 12:30:37 beyhan
578 * new SymConst semantics
580 * Revision 1.18 2004/06/27 21:17:41 liekweg
583 * Revision 1.17 2004/06/25 13:45:13 liekweg
584 * observe stickyness; minor refactoring
586 * Revision 1.16 2004/06/24 06:42:14 goetz
589 * Revision 1.15 2004/06/18 15:47:19 liekweg
590 * minor bug fix (go forward, not backward) --flo
592 * Revision 1.14 2004/06/18 13:12:43 liekweg
593 * final bug fix (calls via consts)
595 * Revision 1.13 2004/06/17 16:34:33 liekweg
598 * Revision 1.12 2004/06/17 16:33:33 liekweg
601 * Revision 1.11 2004/06/17 14:21:13 liekweg
604 * Revision 1.10 2004/06/17 10:31:41 goetz
605 * irscc: bugfix, can now deal with loops not reachable from start
606 * cgana: bugfix, skip_Tuple
609 * Revision 1.9 2004/06/17 08:56:03 liekweg
610 * Fixed typos in comments
612 * Revision 1.8 2004/06/17 08:33:01 liekweg
613 * Added comments; added remove_irg
615 * Revision 1.6 2004/06/14 13:02:03 goetz
618 * Revision 1.5 2004/06/13 15:03:45 liekweg
619 * RTA auf Iterative RTA aufgebohrt --flo
621 * Revision 1.4 2004/06/12 19:35:04 liekweg
622 * Kommentare eingef"ugt --flo
624 * Revision 1.3 2004/06/12 17:09:46 liekweg
625 * RTA works, outedges breaks. "Yay." --flo
627 * Revision 1.2 2004/06/11 18:25:39 liekweg
630 * Revision 1.1 2004/06/11 18:24:18 liekweg