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)
394 int i, n, n_runs = 0;
396 int rem_vpi = get_visit_pseudo_irgs();
397 set_visit_pseudo_irgs(1);
399 # ifdef DEBUG_libfirm
400 n = get_irp_n_irgs();
401 for (i = 0; i < n; i++) {
402 irg_vrfy (get_irp_irg(i));
405 # endif /* defined DEBUG_libfirm */
407 verbose = do_verbose;
411 n_runs = rta_fill_incremental ();
414 int n_live_graphs = stats ();
416 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
417 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
418 printf ("RTA: n_runs = %i\n", n_runs);
421 # ifdef DEBUG_libfirm
422 for (i = 0; i < n; i++) {
423 irg_vrfy (get_irp_irg(i));
426 # endif /* defined DEBUG_libfirm */
428 set_visit_pseudo_irgs(rem_vpi);
432 * walker for all types and entities
434 * Changes the peculiarity of entities that represents
435 * dead graphs to peculiarity_description.
437 static void make_entity_to_description(type_or_ent *tore, void *env) {
438 if (get_kind(tore) == k_entity) {
439 entity *ent = (entity *)tore;
441 if ((is_Method_type(get_entity_type(ent))) &&
442 (get_entity_peculiarity(ent) != peculiarity_description) &&
443 (get_entity_visibility(ent) != visibility_external_allocated) ) {
444 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
445 if (!eset_contains (_live_graphs, irg)) {
446 set_entity_peculiarity(ent, peculiarity_description);
447 set_entity_irg(ent, NULL);
453 /* Delete all graphs that we have found to be dead from the program
454 If verbose == 1, print statistics, if > 1, chatter about every detail
456 void rta_delete_dead_graphs (void)
459 int n_graphs = get_irp_n_irgs ();
460 ir_graph *graph = NULL;
461 int n_dead_graphs = 0;
462 ir_graph **dead_graphs;
464 int rem_vpi = get_visit_pseudo_irgs();
465 set_visit_pseudo_irgs(1);
467 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
469 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
471 for (i = 0; i < n_graphs; i++) {
472 graph = get_irp_irg(i);
474 if (rta_is_alive_graph (graph)) {
475 /* do nothing (except some debugging fprintf`s :-) */
477 # ifdef DEBUG_libfirm
478 entity *ent = get_irg_entity (graph);
479 assert (visibility_external_visible != get_entity_visibility (ent));
480 # endif /* defined DEBUG_libfirm */
482 dead_graphs[n_dead_graphs] = graph;
487 type_walk(make_entity_to_description, NULL, NULL);
488 for (i = 0; i < n_dead_graphs; ++i) {
489 remove_irp_irg (dead_graphs[i]);
493 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
496 set_visit_pseudo_irgs(rem_vpi);
501 /* Clean up the RTA data structures. Call this after calling rta_init */
502 void rta_cleanup (void)
504 # ifdef DEBUG_libfirm
506 for (i = 0; i < get_irp_n_irgs(); i++) {
507 irg_vrfy (get_irp_irg(i));
510 # endif /* defined DEBUG_libfirm */
513 eset_destroy (_live_classes);
514 _live_classes = NULL;
518 eset_destroy (_live_graphs);
523 /* Say whether this class might be instantiated at any point in the program: */
524 int rta_is_alive_class (ir_type *clazz)
526 return (eset_contains (_live_classes, clazz));
529 /* Say whether this graph might be run at any time in the program: */
530 int rta_is_alive_graph (ir_graph *graph)
532 return eset_contains (_live_graphs, graph);
535 /* dump our opinion */
536 void rta_report (void)
540 for (i = 0; i < get_irp_n_types(); ++i) {
541 ir_type *tp = get_irp_type(i);
542 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
543 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
547 for (i = 0; i < get_irp_n_irgs(); i++) {
548 if (rta_is_alive_graph (get_irp_irg(i))) {
549 fprintf(stdout, "RTA: considered called: graph of ");
550 DDMEO(get_irg_entity (get_irp_irg(i)));
558 * Revision 1.36 2006/06/05 15:58:12 beck
559 * added support for Thread local storage
560 * added more doxygen docu
562 * Revision 1.35 2006/01/13 21:51:59 beck
563 * renamed all types 'type' to 'ir_type'
565 * Revision 1.34 2006/01/02 15:01:16 beck
566 * missing include added
568 * Revision 1.33 2005/11/17 17:26:57 beck
569 * removed bool type and depency from stdbool.h (not C89)
571 * Revision 1.32 2005/01/05 14:24:52 beck
572 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
574 * Revision 1.31 2004/12/21 13:45:14 beck
575 * removed C99 constructs
577 * Revision 1.30 2004/12/02 16:16:11 beck
578 * fixed config.h include
579 * used xmalloc instead of malloc
581 * Revision 1.29 2004/11/11 13:28:08 goetz
582 * made pseudo irg aware
584 * Revision 1.28 2004/11/03 14:47:18 beck
585 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
587 * Revision 1.27 2004/10/21 07:23:34 goetz
590 * Revision 1.26 2004/10/20 14:59:27 liekweg
593 * Revision 1.25 2004/10/18 12:47:08 liekweg
596 * Revision 1.24 2004/09/24 13:59:04 beck
597 * fixed doxygen comments, removed initialization for description entities
599 * Revision 1.23 2004/08/19 16:51:02 goetz
600 * fixed some errors, pushed closer to inteded firm semantics
602 * Revision 1.22 2004/08/13 08:57:15 beyhan
603 * normalized names of functions, enums ...
604 * added suffix as argument to dumpers, removed global variable
605 * removed support for tarval/Const
607 * Revision 1.21 2004/07/08 15:50:56 goetz
610 * Revision 1.20 2004/07/08 11:17:40 goetz
611 * *** empty log message ***
613 * Revision 1.19 2004/07/06 12:30:37 beyhan
614 * new SymConst semantics
616 * Revision 1.18 2004/06/27 21:17:41 liekweg
619 * Revision 1.17 2004/06/25 13:45:13 liekweg
620 * observe stickyness; minor refactoring
622 * Revision 1.16 2004/06/24 06:42:14 goetz
625 * Revision 1.15 2004/06/18 15:47:19 liekweg
626 * minor bug fix (go forward, not backward) --flo
628 * Revision 1.14 2004/06/18 13:12:43 liekweg
629 * final bug fix (calls via consts)
631 * Revision 1.13 2004/06/17 16:34:33 liekweg
634 * Revision 1.12 2004/06/17 16:33:33 liekweg
637 * Revision 1.11 2004/06/17 14:21:13 liekweg
640 * Revision 1.10 2004/06/17 10:31:41 goetz
641 * irscc: bugfix, can now deal with loops not reachable from start
642 * cgana: bugfix, skip_Tuple
645 * Revision 1.9 2004/06/17 08:56:03 liekweg
646 * Fixed typos in comments
648 * Revision 1.8 2004/06/17 08:33:01 liekweg
649 * Added comments; added remove_irg
651 * Revision 1.6 2004/06/14 13:02:03 goetz
654 * Revision 1.5 2004/06/13 15:03:45 liekweg
655 * RTA auf Iterative RTA aufgebohrt --flo
657 * Revision 1.4 2004/06/12 19:35:04 liekweg
658 * Kommentare eingef"ugt --flo
660 * Revision 1.3 2004/06/12 17:09:46 liekweg
661 * RTA works, outedges breaks. "Yay." --flo
663 * Revision 1.2 2004/06/11 18:25:39 liekweg
666 * Revision 1.1 2004/06/11 18:24:18 liekweg