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) {
179 ent = get_SymConst_entity (ptr);
180 graph = get_entity_irg (ent);
182 *change |= add_graph (graph);
184 /* it's an external allocated thing. */
186 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
187 /* Entities of kind addr_name may not be allocated in this compilation unit.
188 If so, the frontend built faulty Firm. So just ignore. */
189 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
190 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
192 /* other symconst. */
193 assert(0 && "This SymConst can not be an address for a method call.");
199 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
202 } else if (iro_Alloc == op) { /* ALLOC */
203 type *type = get_Alloc_type (node);
205 *change |= add_class (type);
210 Traverse the given graph to collect method accesses and
213 static int rta_fill_graph (ir_graph* graph)
217 current_ir_graph = graph;
219 irg_walk_graph (graph, rta_act, NULL, &change);
224 /** Traverse all graphs to collect method accesses and object allocations.
226 static int rta_fill_incremental (void)
231 int old_ip_view = get_interprocedural_view();
233 set_interprocedural_view(0); /* 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 Initialize 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 * Initialize 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
379 for (i = 0; i < get_irp_n_irgs(); i++) {
380 irg_vrfy (get_irp_irg(i));
383 # endif /* defined DEBUG_libfirm */
385 verbose = do_verbose;
389 n_runs = rta_fill_incremental ();
392 int n_live_graphs = stats ();
394 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
395 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
396 printf ("RTA: n_runs = %i\n", n_runs);
399 # ifdef DEBUG_libfirm
400 for (i = 0; i < get_irp_n_irgs(); i++) {
401 irg_vrfy (get_irp_irg(i));
404 # endif /* defined DEBUG_libfirm */
406 set_visit_pseudo_irgs(rem_vpi);
410 * walker for all types and entities
412 * Changes the peculiarity of entities that represents
413 * dead graphs to peculiarity_description.
415 static void make_entity_to_description(type_or_ent *tore, void *env) {
416 if (get_kind(tore) == k_entity) {
417 entity *ent = (entity *)tore;
419 if ((is_Method_type(get_entity_type(ent))) &&
420 (get_entity_peculiarity(ent) != peculiarity_description) &&
421 (get_entity_visibility(ent) != visibility_external_allocated) ) {
422 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
423 if (!eset_contains (_live_graphs, irg)) {
424 set_entity_peculiarity(ent, peculiarity_description);
425 set_entity_irg(ent, NULL);
431 /* Delete all graphs that we have found to be dead from the program
432 If verbose == 1, print statistics, if > 1, chatter about every detail
434 void rta_delete_dead_graphs (void)
437 int n_graphs = get_irp_n_irgs ();
438 ir_graph *graph = NULL;
439 int n_dead_graphs = 0;
440 ir_graph **dead_graphs;
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 dead_graphs = xmalloc(sizeof(*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);
479 /* Clean up the RTA data structures. Call this after calling rta_init */
480 void rta_cleanup (void)
482 # ifdef DEBUG_libfirm
484 for (i = 0; i < get_irp_n_irgs(); i++) {
485 irg_vrfy (get_irp_irg(i));
488 # endif /* defined DEBUG_libfirm */
491 eset_destroy (_live_classes);
492 _live_classes = NULL;
496 eset_destroy (_live_graphs);
501 /* Say whether this class might be instantiated at any point in the program: */
502 int rta_is_alive_class (type *clazz)
504 return (eset_contains (_live_classes, clazz));
507 /* Say whether this graph might be run at any time in the program: */
508 int rta_is_alive_graph (ir_graph *graph)
510 return eset_contains (_live_graphs, graph);
513 /* dump our opinion */
514 void rta_report (void)
518 for (i = 0; i < get_irp_n_types(); ++i) {
519 type *tp = get_irp_type(i);
520 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
521 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
525 for (i = 0; i < get_irp_n_irgs(); i++) {
526 if (rta_is_alive_graph (get_irp_irg(i))) {
527 fprintf(stdout, "RTA: considered called: graph of ");
528 DDMEO(get_irg_entity (get_irp_irg(i)));
536 * Revision 1.33 2005/11/17 17:26:57 beck
537 * removed bool type and depency from stdbool.h (not C89)
539 * Revision 1.32 2005/01/05 14:24:52 beck
540 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
542 * Revision 1.31 2004/12/21 13:45:14 beck
543 * removed C99 constructs
545 * Revision 1.30 2004/12/02 16:16:11 beck
546 * fixed config.h include
547 * used xmalloc instead of malloc
549 * Revision 1.29 2004/11/11 13:28:08 goetz
550 * made pseudo irg aware
552 * Revision 1.28 2004/11/03 14:47:18 beck
553 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
555 * Revision 1.27 2004/10/21 07:23:34 goetz
558 * Revision 1.26 2004/10/20 14:59:27 liekweg
561 * Revision 1.25 2004/10/18 12:47:08 liekweg
564 * Revision 1.24 2004/09/24 13:59:04 beck
565 * fixed doxygen comments, removed initialization for description entities
567 * Revision 1.23 2004/08/19 16:51:02 goetz
568 * fixed some errors, pushed closer to inteded firm semantics
570 * Revision 1.22 2004/08/13 08:57:15 beyhan
571 * normalized names of functions, enums ...
572 * added suffix as argument to dumpers, removed global variable
573 * removed support for tarval/Const
575 * Revision 1.21 2004/07/08 15:50:56 goetz
578 * Revision 1.20 2004/07/08 11:17:40 goetz
579 * *** empty log message ***
581 * Revision 1.19 2004/07/06 12:30:37 beyhan
582 * new SymConst semantics
584 * Revision 1.18 2004/06/27 21:17:41 liekweg
587 * Revision 1.17 2004/06/25 13:45:13 liekweg
588 * observe stickyness; minor refactoring
590 * Revision 1.16 2004/06/24 06:42:14 goetz
593 * Revision 1.15 2004/06/18 15:47:19 liekweg
594 * minor bug fix (go forward, not backward) --flo
596 * Revision 1.14 2004/06/18 13:12:43 liekweg
597 * final bug fix (calls via consts)
599 * Revision 1.13 2004/06/17 16:34:33 liekweg
602 * Revision 1.12 2004/06/17 16:33:33 liekweg
605 * Revision 1.11 2004/06/17 14:21:13 liekweg
608 * Revision 1.10 2004/06/17 10:31:41 goetz
609 * irscc: bugfix, can now deal with loops not reachable from start
610 * cgana: bugfix, skip_Tuple
613 * Revision 1.9 2004/06/17 08:56:03 liekweg
614 * Fixed typos in comments
616 * Revision 1.8 2004/06/17 08:33:01 liekweg
617 * Added comments; added remove_irg
619 * Revision 1.6 2004/06/14 13:02:03 goetz
622 * Revision 1.5 2004/06/13 15:03:45 liekweg
623 * RTA auf Iterative RTA aufgebohrt --flo
625 * Revision 1.4 2004/06/12 19:35:04 liekweg
626 * Kommentare eingef"ugt --flo
628 * Revision 1.3 2004/06/12 17:09:46 liekweg
629 * RTA works, outedges breaks. "Yay." --flo
631 * Revision 1.2 2004/06/11 18:25:39 liekweg
634 * Revision 1.1 2004/06/11 18:24:18 liekweg