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) {
177 ent = get_SymConst_entity (ptr);
178 ir_graph *graph = get_entity_irg (ent);
180 *change |= add_graph (graph);
182 /* it's an external allocated thing. */
184 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
185 /* Entities of kind addr_name may not be allocated in this compilation unit.
186 If so, the frontend built faulty Firm. So just ignore. */
187 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
188 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
190 /* other symconst. */
191 assert(0 && "This SymConst can not be an address for a method call.");
197 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
200 } else if (iro_Alloc == op) { /* ALLOC */
201 type *type = get_Alloc_type (node);
203 *change |= add_class (type);
208 Traverse the given graph to collect method accesses and
211 static int rta_fill_graph (ir_graph* graph)
215 current_ir_graph = graph;
217 irg_walk_graph (graph, rta_act, NULL, &change);
222 /** Traverse all graphs to collect method accesses and object allocations.
224 * @param rerun Whether to rely on is_alive in a second run
226 static int rta_fill_incremental (void)
231 int old_ip_view = get_interprocedural_view();
233 set_interprocedural_view(false); /* save this for later */
235 /* init_tables has added main_irg to _live_graphs */
237 /* Need to take care of graphs that are externally
238 visible or sticky. Pretend that they are called: */
240 for (i = 0; i < get_irp_n_irgs(); i++) {
241 ir_graph *graph = get_irp_irg (i);
242 entity *ent = get_irg_entity (graph);
244 if ((visibility_external_visible == get_entity_visibility (ent)) ||
245 (stickyness_sticky == get_entity_stickyness (ent))) {
246 eset_insert (_live_graphs, graph);
247 // printf("external visible: "); DDMG(graph);
255 eset *live_graphs = _live_graphs;
256 _live_graphs = eset_create ();
259 fprintf(stdout, "RTA: RUN %i\n", n_runs);
262 /* collect what we have found previously */
263 eset_insert_all (_live_graphs, live_graphs);
266 for (graph = eset_first (live_graphs);
268 graph = eset_next (live_graphs)) {
271 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
272 DDMEO(get_irg_entity (graph));
275 rerun |= rta_fill_graph (graph);
278 eset_destroy (live_graphs);
283 set_interprocedural_view(old_ip_view); /* cover up our traces */
289 Count the number of graphs that we have found to be live.
291 static int stats (void)
294 int n_live_graphs = 0;
295 int n_graphs = get_irp_n_irgs();
297 for (i = 0; i < n_graphs; i++) {
298 ir_graph *graph = get_irp_irg(i);
300 if (rta_is_alive_graph (graph)) {
305 return (n_live_graphs);
308 /* remove a graph, part I */
310 We removed the first graph to implement the entity, so we're
311 abstract now. Pretend that it wasn't there at all, and every
312 entity that used to inherit this entity's graph is now abstract.
314 /* Since we *know* that this entity will not be called, this is OK. */
315 static void force_description (entity *ent, entity *addr)
317 int i, n_over = get_entity_n_overwrittenby (ent);
319 set_entity_peculiarity (ent, peculiarity_description);
321 for (i = 0; i < n_over; i ++) {
322 entity *over = get_entity_overwrittenby (ent, i);
324 if (peculiarity_inherited == get_entity_peculiarity (over)) {
325 /* We rely on the fact that cse is performed on the const_code_irg. */
326 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
328 if (addr == my_addr) {
329 force_description (over, addr);
331 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
332 /* check whether 'over' forces 'inheritance' of *our* graph: */
333 ir_node *f_addr = get_atomic_ent_value (over);
334 entity *impl_ent = get_SymConst_entity (f_addr);
336 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
337 if (impl_ent == addr) {
338 assert (0 && "gibt's denn sowas");
339 force_description (over, addr);
346 Initialise the static data structures.
348 static void init_tables (void)
350 int i, n_globs = get_class_n_members(get_glob_type());
352 _live_classes = eset_create ();
353 _live_graphs = eset_create ();
355 if (get_irp_main_irg ()) {
356 eset_insert (_live_graphs, get_irp_main_irg ());
359 /* Find static allocated classes */
360 for (i = 0; i < n_globs; ++i) {
361 type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
362 if (is_class_type(member_type))
363 eset_insert(_live_classes, member_type);
368 * Initialise the RTA data structures, and perform RTA.
369 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
371 void rta_init (int do_verbose)
375 int rem_vpi = get_visit_pseudo_irgs();
376 set_visit_pseudo_irgs(1);
378 # ifdef DEBUG_libfirm
380 for (i = 0; i < get_irp_n_irgs(); i++) {
381 irg_vrfy (get_irp_irg(i));
384 # endif /* defined DEBUG_libfirm */
386 verbose = do_verbose;
390 n_runs = rta_fill_incremental ();
393 int n_live_graphs = stats ();
395 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
396 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
397 printf ("RTA: n_runs = %i\n", n_runs);
400 # ifdef DEBUG_libfirm
401 for (i = 0; i < get_irp_n_irgs(); i++) {
402 irg_vrfy (get_irp_irg(i));
405 # endif /* defined DEBUG_libfirm */
407 set_visit_pseudo_irgs(rem_vpi);
411 * walker for all types and entities
413 * Changes the peculiarity of entities that represents
414 * dead graphs to peculiarity_description.
416 static void make_entity_to_description(type_or_ent *tore, void *env) {
417 if (get_kind(tore) == k_entity) {
418 entity *ent = (entity *)tore;
420 if ((is_method_type(get_entity_type(ent))) &&
421 (get_entity_peculiarity(ent) != peculiarity_description) &&
422 (get_entity_visibility(ent) != visibility_external_allocated) ) {
423 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
424 if (!eset_contains (_live_graphs, irg)) {
425 set_entity_peculiarity(ent, peculiarity_description);
426 set_entity_irg(ent, NULL);
432 /* Delete all graphs that we have found to be dead from the program
433 If verbose == 1, print statistics, if > 1, chatter about every detail
435 void rta_delete_dead_graphs (void)
438 int n_graphs = get_irp_n_irgs ();
439 ir_graph *graph = NULL;
440 int n_dead_graphs = 0;
442 int rem_vpi = get_visit_pseudo_irgs();
443 set_visit_pseudo_irgs(1);
445 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
447 ir_graph *dead_graphs[get_irp_n_irgs()];
449 for (i = 0; i < n_graphs; i++) {
450 graph = get_irp_irg(i);
452 if (rta_is_alive_graph (graph)) {
453 /* do nothing (except some debugging fprintf`s :-) */
455 # ifdef DEBUG_libfirm
456 entity *ent = get_irg_entity (graph);
457 assert (visibility_external_visible != get_entity_visibility (ent));
458 # endif /* defined DEBUG_libfirm */
460 dead_graphs[n_dead_graphs] = graph;
465 type_walk(make_entity_to_description, NULL, NULL);
466 for (i = 0; i < n_dead_graphs; ++i) {
467 remove_irp_irg (dead_graphs[i]);
471 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
474 set_visit_pseudo_irgs(rem_vpi);
477 /* Clean up the RTA data structures. Call this after calling rta_init */
478 void rta_cleanup (void)
480 # ifdef DEBUG_libfirm
482 for (i = 0; i < get_irp_n_irgs(); i++) {
483 irg_vrfy (get_irp_irg(i));
486 # endif /* defined DEBUG_libfirm */
489 eset_destroy (_live_classes);
490 _live_classes = NULL;
494 eset_destroy (_live_graphs);
499 /* Say whether this class might be instantiated at any point in the program: */
500 int rta_is_alive_class (type *clazz)
502 return (eset_contains (_live_classes, clazz));
505 /* Say whether this graph might be run at any time in the program: */
506 int rta_is_alive_graph (ir_graph *graph)
508 return eset_contains (_live_graphs, graph);
511 /* dump our opinion */
512 void rta_report (void)
516 for (i = 0; i < get_irp_n_types(); ++i) {
517 type *tp = get_irp_type(i);
518 if (is_class_type(tp) && rta_is_alive_class(tp)) {
519 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
523 for (i = 0; i < get_irp_n_irgs(); i++) {
524 if (rta_is_alive_graph (get_irp_irg(i))) {
525 fprintf(stdout, "RTA: considered called: graph of ");
526 DDMEO(get_irg_entity (get_irp_irg(i)));
534 * Revision 1.30 2004/12/02 16:16:11 beck
535 * fixed config.h include
536 * used xmalloc instead of malloc
538 * Revision 1.29 2004/11/11 13:28:08 goetz
539 * made pseudo irg aware
541 * Revision 1.28 2004/11/03 14:47:18 beck
542 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
544 * Revision 1.27 2004/10/21 07:23:34 goetz
547 * Revision 1.26 2004/10/20 14:59:27 liekweg
550 * Revision 1.25 2004/10/18 12:47:08 liekweg
553 * Revision 1.24 2004/09/24 13:59:04 beck
554 * fixed doxygen comments, removed initialization for description entities
556 * Revision 1.23 2004/08/19 16:51:02 goetz
557 * fixed some errors, pushed closer to inteded firm semantics
559 * Revision 1.22 2004/08/13 08:57:15 beyhan
560 * normalized names of functions, enums ...
561 * added suffix as argument to dumpers, removed global variable
562 * removed support for tarval/Const
564 * Revision 1.21 2004/07/08 15:50:56 goetz
567 * Revision 1.20 2004/07/08 11:17:40 goetz
568 * *** empty log message ***
570 * Revision 1.19 2004/07/06 12:30:37 beyhan
571 * new SymConst semantics
573 * Revision 1.18 2004/06/27 21:17:41 liekweg
576 * Revision 1.17 2004/06/25 13:45:13 liekweg
577 * observe stickyness; minor refactoring
579 * Revision 1.16 2004/06/24 06:42:14 goetz
582 * Revision 1.15 2004/06/18 15:47:19 liekweg
583 * minor bug fix (go forward, not backward) --flo
585 * Revision 1.14 2004/06/18 13:12:43 liekweg
586 * final bug fix (calls via consts)
588 * Revision 1.13 2004/06/17 16:34:33 liekweg
591 * Revision 1.12 2004/06/17 16:33:33 liekweg
594 * Revision 1.11 2004/06/17 14:21:13 liekweg
597 * Revision 1.10 2004/06/17 10:31:41 goetz
598 * irscc: bugfix, can now deal with loops not reachable from start
599 * cgana: bugfix, skip_Tuple
602 * Revision 1.9 2004/06/17 08:56:03 liekweg
603 * Fixed typos in comments
605 * Revision 1.8 2004/06/17 08:33:01 liekweg
606 * Added comments; added remove_irg
608 * Revision 1.6 2004/06/14 13:02:03 goetz
611 * Revision 1.5 2004/06/13 15:03:45 liekweg
612 * RTA auf Iterative RTA aufgebohrt --flo
614 * Revision 1.4 2004/06/12 19:35:04 liekweg
615 * Kommentare eingef"ugt --flo
617 * Revision 1.3 2004/06/12 17:09:46 liekweg
618 * RTA works, outedges breaks. "Yay." --flo
620 * Revision 1.2 2004/06/11 18:25:39 liekweg
623 * Revision 1.1 2004/06/11 18:24:18 liekweg