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 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 :-) */
484 # ifdef DEBUG_libfirm
485 ir_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.39 2006/12/13 13:15:12 beck
566 * renamed entity -> ir_entity
568 * Revision 1.38 2006/12/12 16:12:05 beck
569 * Fixed missing initialization
571 * Revision 1.37 2006/12/11 15:28:48 matze
572 * - Several warning fixes
573 * - Fixes for compilation without DEBUG_libfirm
574 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
576 * Revision 1.36 2006/06/05 15:58:12 beck
577 * added support for Thread local storage
578 * added more doxygen docu
580 * Revision 1.35 2006/01/13 21:51:59 beck
581 * renamed all types 'type' to 'ir_type'
583 * Revision 1.34 2006/01/02 15:01:16 beck
584 * missing include added
586 * Revision 1.33 2005/11/17 17:26:57 beck
587 * removed bool type and depency from stdbool.h (not C89)
589 * Revision 1.32 2005/01/05 14:24:52 beck
590 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
592 * Revision 1.31 2004/12/21 13:45:14 beck
593 * removed C99 constructs
595 * Revision 1.30 2004/12/02 16:16:11 beck
596 * fixed config.h include
597 * used xmalloc instead of malloc
599 * Revision 1.29 2004/11/11 13:28:08 goetz
600 * made pseudo irg aware
602 * Revision 1.28 2004/11/03 14:47:18 beck
603 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
605 * Revision 1.27 2004/10/21 07:23:34 goetz
608 * Revision 1.26 2004/10/20 14:59:27 liekweg
611 * Revision 1.25 2004/10/18 12:47:08 liekweg
614 * Revision 1.24 2004/09/24 13:59:04 beck
615 * fixed doxygen comments, removed initialization for description entities
617 * Revision 1.23 2004/08/19 16:51:02 goetz
618 * fixed some errors, pushed closer to inteded firm semantics
620 * Revision 1.22 2004/08/13 08:57:15 beyhan
621 * normalized names of functions, enums ...
622 * added suffix as argument to dumpers, removed global variable
623 * removed support for tarval/Const
625 * Revision 1.21 2004/07/08 15:50:56 goetz
628 * Revision 1.20 2004/07/08 11:17:40 goetz
629 * *** empty log message ***
631 * Revision 1.19 2004/07/06 12:30:37 beyhan
632 * new SymConst semantics
634 * Revision 1.18 2004/06/27 21:17:41 liekweg
637 * Revision 1.17 2004/06/25 13:45:13 liekweg
638 * observe stickyness; minor refactoring
640 * Revision 1.16 2004/06/24 06:42:14 goetz
643 * Revision 1.15 2004/06/18 15:47:19 liekweg
644 * minor bug fix (go forward, not backward) --flo
646 * Revision 1.14 2004/06/18 13:12:43 liekweg
647 * final bug fix (calls via consts)
649 * Revision 1.13 2004/06/17 16:34:33 liekweg
652 * Revision 1.12 2004/06/17 16:33:33 liekweg
655 * Revision 1.11 2004/06/17 14:21:13 liekweg
658 * Revision 1.10 2004/06/17 10:31:41 goetz
659 * irscc: bugfix, can now deal with loops not reachable from start
660 * cgana: bugfix, skip_Tuple
663 * Revision 1.9 2004/06/17 08:56:03 liekweg
664 * Fixed typos in comments
666 * Revision 1.8 2004/06/17 08:33:01 liekweg
667 * Added comments; added remove_irg
669 * Revision 1.6 2004/06/14 13:02:03 goetz
672 * Revision 1.5 2004/06/13 15:03:45 liekweg
673 * RTA auf Iterative RTA aufgebohrt --flo
675 * Revision 1.4 2004/06/12 19:35:04 liekweg
676 * Kommentare eingef"ugt --flo
678 * Revision 1.3 2004/06/12 17:09:46 liekweg
679 * RTA works, outedges breaks. "Yay." --flo
681 * Revision 1.2 2004/06/11 18:25:39 liekweg
684 * Revision 1.1 2004/06/11 18:24:18 liekweg