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 n = get_irp_n_irgs();
428 for (i = 0; i < n; i++) {
429 irg_vrfy (get_irp_irg(i));
433 # endif /* defined DEBUG_libfirm */
435 set_visit_pseudo_irgs(rem_vpi);
439 * walker for all types and entities
441 * Changes the peculiarity of entities that represents
442 * dead graphs to peculiarity_description.
444 static void make_entity_to_description(type_or_ent *tore, void *env) {
445 if (get_kind(tore) == k_entity) {
446 entity *ent = (entity *)tore;
448 if ((is_Method_type(get_entity_type(ent))) &&
449 (get_entity_peculiarity(ent) != peculiarity_description) &&
450 (get_entity_visibility(ent) != visibility_external_allocated) ) {
451 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
452 if (!eset_contains (_live_graphs, irg)) {
453 set_entity_peculiarity(ent, peculiarity_description);
454 set_entity_irg(ent, NULL);
460 /* Delete all graphs that we have found to be dead from the program
461 If verbose == 1, print statistics, if > 1, chatter about every detail
463 void rta_delete_dead_graphs (void)
466 int n_graphs = get_irp_n_irgs ();
467 ir_graph *graph = NULL;
468 int n_dead_graphs = 0;
469 ir_graph **dead_graphs;
471 int rem_vpi = get_visit_pseudo_irgs();
472 set_visit_pseudo_irgs(1);
474 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
476 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
478 for (i = 0; i < n_graphs; i++) {
479 graph = get_irp_irg(i);
481 if (rta_is_alive_graph (graph)) {
482 /* do nothing (except some debugging fprintf`s :-) */
484 # ifdef DEBUG_libfirm
485 entity *ent = get_irg_entity (graph);
486 assert (visibility_external_visible != get_entity_visibility (ent));
487 # endif /* defined DEBUG_libfirm */
489 dead_graphs[n_dead_graphs] = graph;
494 type_walk(make_entity_to_description, NULL, NULL);
495 for (i = 0; i < n_dead_graphs; ++i) {
496 remove_irp_irg (dead_graphs[i]);
500 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
503 set_visit_pseudo_irgs(rem_vpi);
508 /* Clean up the RTA data structures. Call this after calling rta_init */
509 void rta_cleanup (void)
511 # ifdef DEBUG_libfirm
513 for (i = 0; i < get_irp_n_irgs(); i++) {
514 irg_vrfy (get_irp_irg(i));
517 # endif /* defined DEBUG_libfirm */
520 eset_destroy (_live_classes);
521 _live_classes = NULL;
525 eset_destroy (_live_graphs);
530 /* Say whether this class might be instantiated at any point in the program: */
531 int rta_is_alive_class (ir_type *clazz)
533 return (eset_contains (_live_classes, clazz));
536 /* Say whether this graph might be run at any time in the program: */
537 int rta_is_alive_graph (ir_graph *graph)
539 return eset_contains (_live_graphs, graph);
542 /* dump our opinion */
543 void rta_report (void)
547 for (i = 0; i < get_irp_n_types(); ++i) {
548 ir_type *tp = get_irp_type(i);
549 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
550 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
554 for (i = 0; i < get_irp_n_irgs(); i++) {
555 if (rta_is_alive_graph (get_irp_irg(i))) {
556 fprintf(stdout, "RTA: considered called: graph of ");
557 DDMEO(get_irg_entity (get_irp_irg(i)));
565 * Revision 1.38 2006/12/12 16:12:05 beck
566 * Fixed missing initialization
568 * Revision 1.37 2006/12/11 15:28:48 matze
569 * - Several warning fixes
570 * - Fixes for compilation without DEBUG_libfirm
571 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
573 * Revision 1.36 2006/06/05 15:58:12 beck
574 * added support for Thread local storage
575 * added more doxygen docu
577 * Revision 1.35 2006/01/13 21:51:59 beck
578 * renamed all types 'type' to 'ir_type'
580 * Revision 1.34 2006/01/02 15:01:16 beck
581 * missing include added
583 * Revision 1.33 2005/11/17 17:26:57 beck
584 * removed bool type and depency from stdbool.h (not C89)
586 * Revision 1.32 2005/01/05 14:24:52 beck
587 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
589 * Revision 1.31 2004/12/21 13:45:14 beck
590 * removed C99 constructs
592 * Revision 1.30 2004/12/02 16:16:11 beck
593 * fixed config.h include
594 * used xmalloc instead of malloc
596 * Revision 1.29 2004/11/11 13:28:08 goetz
597 * made pseudo irg aware
599 * Revision 1.28 2004/11/03 14:47:18 beck
600 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
602 * Revision 1.27 2004/10/21 07:23:34 goetz
605 * Revision 1.26 2004/10/20 14:59:27 liekweg
608 * Revision 1.25 2004/10/18 12:47:08 liekweg
611 * Revision 1.24 2004/09/24 13:59:04 beck
612 * fixed doxygen comments, removed initialization for description entities
614 * Revision 1.23 2004/08/19 16:51:02 goetz
615 * fixed some errors, pushed closer to inteded firm semantics
617 * Revision 1.22 2004/08/13 08:57:15 beyhan
618 * normalized names of functions, enums ...
619 * added suffix as argument to dumpers, removed global variable
620 * removed support for tarval/Const
622 * Revision 1.21 2004/07/08 15:50:56 goetz
625 * Revision 1.20 2004/07/08 11:17:40 goetz
626 * *** empty log message ***
628 * Revision 1.19 2004/07/06 12:30:37 beyhan
629 * new SymConst semantics
631 * Revision 1.18 2004/06/27 21:17:41 liekweg
634 * Revision 1.17 2004/06/25 13:45:13 liekweg
635 * observe stickyness; minor refactoring
637 * Revision 1.16 2004/06/24 06:42:14 goetz
640 * Revision 1.15 2004/06/18 15:47:19 liekweg
641 * minor bug fix (go forward, not backward) --flo
643 * Revision 1.14 2004/06/18 13:12:43 liekweg
644 * final bug fix (calls via consts)
646 * Revision 1.13 2004/06/17 16:34:33 liekweg
649 * Revision 1.12 2004/06/17 16:33:33 liekweg
652 * Revision 1.11 2004/06/17 14:21:13 liekweg
655 * Revision 1.10 2004/06/17 10:31:41 goetz
656 * irscc: bugfix, can now deal with loops not reachable from start
657 * cgana: bugfix, skip_Tuple
660 * Revision 1.9 2004/06/17 08:56:03 liekweg
661 * Fixed typos in comments
663 * Revision 1.8 2004/06/17 08:33:01 liekweg
664 * Added comments; added remove_irg
666 * Revision 1.6 2004/06/14 13:02:03 goetz
669 * Revision 1.5 2004/06/13 15:03:45 liekweg
670 * RTA auf Iterative RTA aufgebohrt --flo
672 * Revision 1.4 2004/06/12 19:35:04 liekweg
673 * Kommentare eingef"ugt --flo
675 * Revision 1.3 2004/06/12 17:09:46 liekweg
676 * RTA works, outedges breaks. "Yay." --flo
678 * Revision 1.2 2004/06/11 18:25:39 liekweg
681 * Revision 1.1 2004/06/11 18:24:18 liekweg