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.
36 # endif /* not defined TRUE */
39 static int verbose = 0;
43 static eset *_live_classes = NULL;
45 /* cache computed results */
46 static eset *_live_graphs = NULL;
49 Given a method, find the firm graph that implements that method.
51 static ir_graph *get_implementing_graph (entity *method)
54 ir_graph *graph = get_entity_irg ((entity*) method);
56 /* Search upwards in the overwrites graph. */
57 /* GL: this will not work for multiple inheritance */
60 int n_over = get_entity_n_overwrites ((entity*) method);
62 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
63 entity *over = get_entity_overwrites ((entity*) method, i);
64 graph = get_implementing_graph (over);
68 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
69 assert(get_entity_peculiarity(method) == peculiarity_description
70 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
72 /* we *must* always return a graph != NULL, *except* when we're used
73 inside remove_irg or force_description */
74 /* assert (graph && "no graph"); */
78 ir_graph *graph = NULL;
80 if (get_entity_peculiarity(method) != peculiarity_description)
81 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
87 static int add_graph (ir_graph *graph)
89 if (!eset_contains (_live_graphs, graph)) {
91 fprintf(stdout, "RTA: new graph of ");
92 DDMEO(get_irg_entity (graph));
95 eset_insert (_live_graphs, graph);
102 static int add_class (type *clazz)
104 if (!eset_contains (_live_classes, clazz)) {
106 fprintf(stdout, "RTA: new class: ");
110 eset_insert (_live_classes, clazz);
117 /** Given an entity, add all implementing graphs that belong to live classes
120 * Iff additions occurred, return TRUE, else FALSE.
122 static int add_implementing_graphs (entity *method)
125 int n_over = get_entity_n_overwrittenby (method);
126 ir_graph *graph = get_entity_irg (method);
130 graph = get_implementing_graph (method);
134 fprintf(stdout, "RTA: new call to ");
138 if (rta_is_alive_class (get_entity_owner (method))) {
140 change = add_graph (graph);
144 for (i = 0; i < n_over; i ++) {
145 entity *over = get_entity_overwrittenby (method, i);
146 change |= add_implementing_graphs (over);
152 /** Enter all method accesses and all class allocations into
155 * Set *(int*)env to true iff (possibly) new graphs have been found.
157 static void rta_act (ir_node *node, void *env)
159 int *change = (int*) env;
161 opcode op = get_irn_opcode (node);
163 if (iro_Call == op) { /* CALL */
166 ir_node *ptr = get_Call_ptr (node);
169 if (iro_Sel == get_irn_opcode (ptr)) {
170 ent = get_Sel_entity (ptr);
171 *change |= add_implementing_graphs (ent);
174 } else if (iro_SymConst == get_irn_opcode (ptr)) {
175 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
176 ent = get_SymConst_entity (ptr);
177 ir_graph *graph = get_entity_irg (ent);
179 *change |= add_graph (graph);
181 /* it's an external allocated thing. */
183 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
184 /* Entities of kind addr_name may not be allocated in this compilation unit.
185 If so, the frontend built faulty Firm. So just ignore. */
186 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
187 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
189 /* other symconst. */
190 assert(0 && "This SymConst can not be an address for a method call.");
196 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
199 } else if (iro_Alloc == op) { /* ALLOC */
200 type *type = get_Alloc_type (node);
202 *change |= add_class (type);
207 Traverse the given graph to collect method accesses and
210 static int rta_fill_graph (ir_graph* graph)
214 current_ir_graph = graph;
216 irg_walk_graph (graph, rta_act, NULL, &change);
221 /** Traverse all graphs to collect method accesses and object allocations.
223 * @param rerun Whether to rely on is_alive in a second run
225 static int rta_fill_incremental (void)
230 int old_ip_view = interprocedural_view;
232 interprocedural_view = 0; /* save this for later */
234 /* init_tables has added main_irg to _live_graphs */
236 /* Need to take care of graphs that are externally
237 visible or sticky. Pretend that they are called: */
239 for (i = 0; i < get_irp_n_irgs(); i++) {
240 ir_graph *graph = get_irp_irg (i);
241 entity *ent = get_irg_entity (graph);
243 if ((visibility_external_visible == get_entity_visibility (ent)) ||
244 (stickyness_sticky == get_entity_stickyness (ent))) {
245 eset_insert (_live_graphs, graph);
246 // printf("external visible: "); DDMG(graph);
254 eset *live_graphs = _live_graphs;
255 _live_graphs = eset_create ();
258 fprintf(stdout, "RTA: RUN %i\n", n_runs);
261 /* collect what we have found previously */
262 eset_insert_all (_live_graphs, live_graphs);
265 for (graph = eset_first (live_graphs);
267 graph = eset_next (live_graphs)) {
270 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
271 DDMEO(get_irg_entity (graph));
274 rerun |= rta_fill_graph (graph);
277 eset_destroy (live_graphs);
282 interprocedural_view = old_ip_view; /* cover up our traces */
288 Count the number of graphs that we have found to be live.
290 static int stats (void)
293 int n_live_graphs = 0;
294 int n_graphs = get_irp_n_irgs();
296 for (i = 0; i < n_graphs; i++) {
297 ir_graph *graph = get_irp_irg(i);
299 if (rta_is_alive_graph (graph)) {
304 return (n_live_graphs);
307 /* remove a graph, part I */
309 We removed the first graph to implement the entity, so we're
310 abstract now. Pretend that it wasn't there at all, and every
311 entity that used to inherit this entity's graph is now abstract.
313 /* Since we *know* that this entity will not be called, this is OK. */
314 static void force_description (entity *ent, entity *addr)
316 int i, n_over = get_entity_n_overwrittenby (ent);
318 set_entity_peculiarity (ent, peculiarity_description);
320 for (i = 0; i < n_over; i ++) {
321 entity *over = get_entity_overwrittenby (ent, i);
323 if (peculiarity_inherited == get_entity_peculiarity (over)) {
324 /* We rely on the fact that cse is performed on the const_code_irg. */
325 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
327 if (addr == my_addr) {
328 force_description (over, addr);
330 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
331 /* check whether 'over' forces 'inheritance' of *our* graph: */
332 ir_node *f_addr = get_atomic_ent_value (over);
333 entity *impl_ent = get_SymConst_entity (f_addr);
335 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
336 if (impl_ent == addr) {
337 assert (0 && "gibt's denn sowas");
338 force_description (over, addr);
345 Initialise the static data structures.
347 static void init_tables (void)
349 int i, n_globs = get_class_n_members(get_glob_type());
351 _live_classes = eset_create ();
352 _live_graphs = eset_create ();
354 if (get_irp_main_irg ()) {
355 eset_insert (_live_graphs, get_irp_main_irg ());
358 /* Find static allocated classes */
359 for (i = 0; i < n_globs; ++i) {
360 type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
361 if (is_class_type(member_type))
362 eset_insert(_live_classes, member_type);
367 * Initialise the RTA data structures, and perform RTA.
368 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
370 void rta_init (int do_verbose)
374 # ifdef DEBUG_libfirm
376 for (i = 0; i < get_irp_n_irgs(); i++) {
377 irg_vrfy (get_irp_irg(i));
380 # endif /* defined DEBUG_libfirm */
382 verbose = do_verbose;
386 n_runs = rta_fill_incremental ();
389 int n_live_graphs = stats ();
391 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
392 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
393 printf ("RTA: n_runs = %i\n", n_runs);
396 # ifdef DEBUG_libfirm
397 for (i = 0; i < get_irp_n_irgs(); i++) {
398 irg_vrfy (get_irp_irg(i));
401 # endif /* defined DEBUG_libfirm */
405 * walker for all types and entities
407 * Changes the peculiarity of entities that represents
408 * dead graphs to peculiarity_description.
410 static void make_entity_to_description(type_or_ent *tore, void *env) {
411 if (get_kind(tore) == k_entity) {
412 entity *ent = (entity *)tore;
414 if ((is_method_type(get_entity_type(ent))) &&
415 (get_entity_peculiarity(ent) != peculiarity_description) &&
416 (get_entity_visibility(ent) != visibility_external_allocated) ) {
417 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
418 if (!eset_contains (_live_graphs, irg)) {
419 set_entity_peculiarity(ent, peculiarity_description);
420 set_entity_irg(ent, NULL);
426 /* Delete all graphs that we have found to be dead from the program
427 If verbose == 1, print statistics, if > 1, chatter about every detail
429 void rta_delete_dead_graphs (void)
432 int n_graphs = get_irp_n_irgs ();
433 ir_graph *graph = NULL;
434 int n_dead_graphs = 0;
436 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
438 ir_graph *dead_graphs[get_irp_n_irgs()];
440 for (i = 0; i < n_graphs; i++) {
441 graph = get_irp_irg(i);
443 if (rta_is_alive_graph (graph)) {
444 /* do nothing (except some debugging fprintf`s :-) */
446 # ifdef DEBUG_libfirm
447 entity *ent = get_irg_entity (graph);
448 assert (visibility_external_visible != get_entity_visibility (ent));
449 # endif /* defined DEBUG_libfirm */
451 dead_graphs[n_dead_graphs] = graph;
456 type_walk(make_entity_to_description, NULL, NULL);
457 for (i = 0; i < n_dead_graphs; ++i) {
458 remove_irp_irg (dead_graphs[i]);
462 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
466 /* Clean up the RTA data structures. Call this after calling rta_init */
467 void rta_cleanup (void)
469 # ifdef DEBUG_libfirm
471 for (i = 0; i < get_irp_n_irgs(); i++) {
472 irg_vrfy (get_irp_irg(i));
475 # endif /* defined DEBUG_libfirm */
478 eset_destroy (_live_classes);
479 _live_classes = NULL;
483 eset_destroy (_live_graphs);
488 /* Say whether this class might be instantiated at any point in the program: */
489 int rta_is_alive_class (type *clazz)
491 return (eset_contains (_live_classes, clazz));
494 /* Say whether this graph might be run at any time in the program: */
495 int rta_is_alive_graph (ir_graph *graph)
497 return eset_contains (_live_graphs, graph);
500 /* dump our opinion */
501 void rta_report (void)
505 for (i = 0; i < get_irp_n_types(); ++i) {
506 type *tp = get_irp_type(i);
507 if (is_class_type(tp) && rta_is_alive_class(tp)) {
508 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
512 for (i = 0; i < get_irp_n_irgs(); i++) {
513 if (rta_is_alive_graph (get_irp_irg(i))) {
514 fprintf(stdout, "RTA: considered called: graph of ");
515 DDMEO(get_irg_entity (get_irp_irg(i)));
523 * Revision 1.27 2004/10/21 07:23:34 goetz
526 * Revision 1.26 2004/10/20 14:59:27 liekweg
529 * Revision 1.25 2004/10/18 12:47:08 liekweg
532 * Revision 1.24 2004/09/24 13:59:04 beck
533 * fixed doxygen comments, removed initialization for description entities
535 * Revision 1.23 2004/08/19 16:51:02 goetz
536 * fixed some errors, pushed closer to inteded firm semantics
538 * Revision 1.22 2004/08/13 08:57:15 beyhan
539 * normalized names of functions, enums ...
540 * added suffix as argument to dumpers, removed global variable
541 * removed support for tarval/Const
543 * Revision 1.21 2004/07/08 15:50:56 goetz
546 * Revision 1.20 2004/07/08 11:17:40 goetz
547 * *** empty log message ***
549 * Revision 1.19 2004/07/06 12:30:37 beyhan
550 * new SymConst semantics
552 * Revision 1.18 2004/06/27 21:17:41 liekweg
555 * Revision 1.17 2004/06/25 13:45:13 liekweg
556 * observe stickyness; minor refactoring
558 * Revision 1.16 2004/06/24 06:42:14 goetz
561 * Revision 1.15 2004/06/18 15:47:19 liekweg
562 * minor bug fix (go forward, not backward) --flo
564 * Revision 1.14 2004/06/18 13:12:43 liekweg
565 * final bug fix (calls via consts)
567 * Revision 1.13 2004/06/17 16:34:33 liekweg
570 * Revision 1.12 2004/06/17 16:33:33 liekweg
573 * Revision 1.11 2004/06/17 14:21:13 liekweg
576 * Revision 1.10 2004/06/17 10:31:41 goetz
577 * irscc: bugfix, can now deal with loops not reachable from start
578 * cgana: bugfix, skip_Tuple
581 * Revision 1.9 2004/06/17 08:56:03 liekweg
582 * Fixed typos in comments
584 * Revision 1.8 2004/06/17 08:33:01 liekweg
585 * Added comments; added remove_irg
587 * Revision 1.6 2004/06/14 13:02:03 goetz
590 * Revision 1.5 2004/06/13 15:03:45 liekweg
591 * RTA auf Iterative RTA aufgebohrt --flo
593 * Revision 1.4 2004/06/12 19:35:04 liekweg
594 * Kommentare eingef"ugt --flo
596 * Revision 1.3 2004/06/12 17:09:46 liekweg
597 * RTA works, outedges breaks. "Yay." --flo
599 * Revision 1.2 2004/06/11 18:25:39 liekweg
602 * Revision 1.1 2004/06/11 18:24:18 liekweg