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 (ir_entity *method)
56 ir_graph *graph = get_entity_irg ((ir_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 ((ir_entity*) method);
64 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
65 ir_entity *over = get_entity_overwrites ((ir_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 (ir_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 ir_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 ir_opcode op = get_irn_opcode (node);
178 if (iro_Call == op) { /* CALL */
179 ir_entity *ent = NULL;
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 ir_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 (ir_entity *ent, ir_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 ir_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 ir_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 ir_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 ir_entity *ent = (ir_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 :-) */
485 ir_entity *ent = get_irg_entity (graph);
486 assert (visibility_external_visible != get_entity_visibility (ent));
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.41 2007/03/22 10:39:33 matze
566 * a bunch of fixes to make firm work with NDEBUG and without DEBUG_libfirm
568 * Revision 1.40 2007/01/16 15:45:15 beck
569 * renamed type opcode to ir_opcode
571 * Revision 1.39 2006/12/13 13:15:12 beck
572 * renamed entity -> ir_entity
574 * Revision 1.38 2006/12/12 16:12:05 beck
575 * Fixed missing initialization
577 * Revision 1.37 2006/12/11 15:28:48 matze
578 * - Several warning fixes
579 * - Fixes for compilation without DEBUG_libfirm
580 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
582 * Revision 1.36 2006/06/05 15:58:12 beck
583 * added support for Thread local storage
584 * added more doxygen docu
586 * Revision 1.35 2006/01/13 21:51:59 beck
587 * renamed all types 'type' to 'ir_type'
589 * Revision 1.34 2006/01/02 15:01:16 beck
590 * missing include added
592 * Revision 1.33 2005/11/17 17:26:57 beck
593 * removed bool type and depency from stdbool.h (not C89)
595 * Revision 1.32 2005/01/05 14:24:52 beck
596 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
598 * Revision 1.31 2004/12/21 13:45:14 beck
599 * removed C99 constructs
601 * Revision 1.30 2004/12/02 16:16:11 beck
602 * fixed config.h include
603 * used xmalloc instead of malloc
605 * Revision 1.29 2004/11/11 13:28:08 goetz
606 * made pseudo irg aware
608 * Revision 1.28 2004/11/03 14:47:18 beck
609 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
611 * Revision 1.27 2004/10/21 07:23:34 goetz
614 * Revision 1.26 2004/10/20 14:59:27 liekweg
617 * Revision 1.25 2004/10/18 12:47:08 liekweg
620 * Revision 1.24 2004/09/24 13:59:04 beck
621 * fixed doxygen comments, removed initialization for description entities
623 * Revision 1.23 2004/08/19 16:51:02 goetz
624 * fixed some errors, pushed closer to inteded firm semantics
626 * Revision 1.22 2004/08/13 08:57:15 beyhan
627 * normalized names of functions, enums ...
628 * added suffix as argument to dumpers, removed global variable
629 * removed support for tarval/Const
631 * Revision 1.21 2004/07/08 15:50:56 goetz
634 * Revision 1.20 2004/07/08 11:17:40 goetz
635 * *** empty log message ***
637 * Revision 1.19 2004/07/06 12:30:37 beyhan
638 * new SymConst semantics
640 * Revision 1.18 2004/06/27 21:17:41 liekweg
643 * Revision 1.17 2004/06/25 13:45:13 liekweg
644 * observe stickyness; minor refactoring
646 * Revision 1.16 2004/06/24 06:42:14 goetz
649 * Revision 1.15 2004/06/18 15:47:19 liekweg
650 * minor bug fix (go forward, not backward) --flo
652 * Revision 1.14 2004/06/18 13:12:43 liekweg
653 * final bug fix (calls via consts)
655 * Revision 1.13 2004/06/17 16:34:33 liekweg
658 * Revision 1.12 2004/06/17 16:33:33 liekweg
661 * Revision 1.11 2004/06/17 14:21:13 liekweg
664 * Revision 1.10 2004/06/17 10:31:41 goetz
665 * irscc: bugfix, can now deal with loops not reachable from start
666 * cgana: bugfix, skip_Tuple
669 * Revision 1.9 2004/06/17 08:56:03 liekweg
670 * Fixed typos in comments
672 * Revision 1.8 2004/06/17 08:33:01 liekweg
673 * Added comments; added remove_irg
675 * Revision 1.6 2004/06/14 13:02:03 goetz
678 * Revision 1.5 2004/06/13 15:03:45 liekweg
679 * RTA auf Iterative RTA aufgebohrt --flo
681 * Revision 1.4 2004/06/12 19:35:04 liekweg
682 * Kommentare eingef"ugt --flo
684 * Revision 1.3 2004/06/12 17:09:46 liekweg
685 * RTA works, outedges breaks. "Yay." --flo
687 * Revision 1.2 2004/06/11 18:25:39 liekweg
690 * Revision 1.1 2004/06/11 18:24:18 liekweg