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 # ifdef DEBUG_libfirm
377 for (i = 0; i < get_irp_n_irgs(); i++) {
378 irg_vrfy (get_irp_irg(i));
381 # endif /* defined DEBUG_libfirm */
383 verbose = do_verbose;
387 n_runs = rta_fill_incremental ();
390 int n_live_graphs = stats ();
392 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
393 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
394 printf ("RTA: n_runs = %i\n", n_runs);
397 # ifdef DEBUG_libfirm
398 for (i = 0; i < get_irp_n_irgs(); i++) {
399 irg_vrfy (get_irp_irg(i));
402 # endif /* defined DEBUG_libfirm */
406 * walker for all types and entities
408 * Changes the peculiarity of entities that represents
409 * dead graphs to peculiarity_description.
411 static void make_entity_to_description(type_or_ent *tore, void *env) {
412 if (get_kind(tore) == k_entity) {
413 entity *ent = (entity *)tore;
415 if ((is_method_type(get_entity_type(ent))) &&
416 (get_entity_peculiarity(ent) != peculiarity_description) &&
417 (get_entity_visibility(ent) != visibility_external_allocated) ) {
418 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
419 if (!eset_contains (_live_graphs, irg)) {
420 set_entity_peculiarity(ent, peculiarity_description);
421 set_entity_irg(ent, NULL);
427 /* Delete all graphs that we have found to be dead from the program
428 If verbose == 1, print statistics, if > 1, chatter about every detail
430 void rta_delete_dead_graphs (void)
433 int n_graphs = get_irp_n_irgs ();
434 ir_graph *graph = NULL;
435 int n_dead_graphs = 0;
437 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
439 ir_graph *dead_graphs[get_irp_n_irgs()];
441 for (i = 0; i < n_graphs; i++) {
442 graph = get_irp_irg(i);
444 if (rta_is_alive_graph (graph)) {
445 /* do nothing (except some debugging fprintf`s :-) */
447 # ifdef DEBUG_libfirm
448 entity *ent = get_irg_entity (graph);
449 assert (visibility_external_visible != get_entity_visibility (ent));
450 # endif /* defined DEBUG_libfirm */
452 dead_graphs[n_dead_graphs] = graph;
457 type_walk(make_entity_to_description, NULL, NULL);
458 for (i = 0; i < n_dead_graphs; ++i) {
459 remove_irp_irg (dead_graphs[i]);
463 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
467 /* Clean up the RTA data structures. Call this after calling rta_init */
468 void rta_cleanup (void)
470 # ifdef DEBUG_libfirm
472 for (i = 0; i < get_irp_n_irgs(); i++) {
473 irg_vrfy (get_irp_irg(i));
476 # endif /* defined DEBUG_libfirm */
479 eset_destroy (_live_classes);
480 _live_classes = NULL;
484 eset_destroy (_live_graphs);
489 /* Say whether this class might be instantiated at any point in the program: */
490 int rta_is_alive_class (type *clazz)
492 return (eset_contains (_live_classes, clazz));
495 /* Say whether this graph might be run at any time in the program: */
496 int rta_is_alive_graph (ir_graph *graph)
498 return eset_contains (_live_graphs, graph);
501 /* dump our opinion */
502 void rta_report (void)
506 for (i = 0; i < get_irp_n_types(); ++i) {
507 type *tp = get_irp_type(i);
508 if (is_class_type(tp) && rta_is_alive_class(tp)) {
509 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
513 for (i = 0; i < get_irp_n_irgs(); i++) {
514 if (rta_is_alive_graph (get_irp_irg(i))) {
515 fprintf(stdout, "RTA: considered called: graph of ");
516 DDMEO(get_irg_entity (get_irp_irg(i)));
524 * Revision 1.28 2004/11/03 14:47:18 beck
525 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
527 * Revision 1.27 2004/10/21 07:23:34 goetz
530 * Revision 1.26 2004/10/20 14:59:27 liekweg
533 * Revision 1.25 2004/10/18 12:47:08 liekweg
536 * Revision 1.24 2004/09/24 13:59:04 beck
537 * fixed doxygen comments, removed initialization for description entities
539 * Revision 1.23 2004/08/19 16:51:02 goetz
540 * fixed some errors, pushed closer to inteded firm semantics
542 * Revision 1.22 2004/08/13 08:57:15 beyhan
543 * normalized names of functions, enums ...
544 * added suffix as argument to dumpers, removed global variable
545 * removed support for tarval/Const
547 * Revision 1.21 2004/07/08 15:50:56 goetz
550 * Revision 1.20 2004/07/08 11:17:40 goetz
551 * *** empty log message ***
553 * Revision 1.19 2004/07/06 12:30:37 beyhan
554 * new SymConst semantics
556 * Revision 1.18 2004/06/27 21:17:41 liekweg
559 * Revision 1.17 2004/06/25 13:45:13 liekweg
560 * observe stickyness; minor refactoring
562 * Revision 1.16 2004/06/24 06:42:14 goetz
565 * Revision 1.15 2004/06/18 15:47:19 liekweg
566 * minor bug fix (go forward, not backward) --flo
568 * Revision 1.14 2004/06/18 13:12:43 liekweg
569 * final bug fix (calls via consts)
571 * Revision 1.13 2004/06/17 16:34:33 liekweg
574 * Revision 1.12 2004/06/17 16:33:33 liekweg
577 * Revision 1.11 2004/06/17 14:21:13 liekweg
580 * Revision 1.10 2004/06/17 10:31:41 goetz
581 * irscc: bugfix, can now deal with loops not reachable from start
582 * cgana: bugfix, skip_Tuple
585 * Revision 1.9 2004/06/17 08:56:03 liekweg
586 * Fixed typos in comments
588 * Revision 1.8 2004/06/17 08:33:01 liekweg
589 * Added comments; added remove_irg
591 * Revision 1.6 2004/06/14 13:02:03 goetz
594 * Revision 1.5 2004/06/13 15:03:45 liekweg
595 * RTA auf Iterative RTA aufgebohrt --flo
597 * Revision 1.4 2004/06/12 19:35:04 liekweg
598 * Kommentare eingef"ugt --flo
600 * Revision 1.3 2004/06/12 17:09:46 liekweg
601 * RTA works, outedges breaks. "Yay." --flo
603 * Revision 1.2 2004/06/11 18:25:39 liekweg
606 * Revision 1.1 2004/06/11 18:24:18 liekweg