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 protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es
17 * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden
42 static eset *_live_classes = NULL;
44 /* cache computed results */
45 static eset *_live_graphs = NULL;
47 static int whole_world = 0;
48 static int verbose = 0;
51 Given a method, find the firm graph that implements that method.
53 static ir_graph *get_implementing_graph (entity *method)
55 ir_graph *graph = get_entity_irg ((entity*) method);
59 int n_over = get_entity_n_overwrites ((entity*) method);
61 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
62 entity *over = get_entity_overwrites ((entity*) method, i);
63 graph = get_implementing_graph (over);
67 /* we *must* always return a graph != NULL, *except* when we're used
68 inside remove_irg or force_description */
69 /* assert (graph && "no graph"); */
74 static int add_graph (ir_graph *graph)
76 if (!eset_contains (_live_graphs, graph)) {
78 fprintf(stdout, "RTA: new graph of ");
79 DDMEO(get_irg_ent (graph));
82 eset_insert (_live_graphs, graph);
89 static int add_class (type *clazz)
91 if (!eset_contains (_live_classes, clazz)) {
93 fprintf(stdout, "RTA: new class: ");
97 eset_insert (_live_classes, clazz);
105 Given an entity, add all implementing graphs that belong to live classes to _live_graphs.
107 Iff additions occurred, return TRUE, else FALSE.
109 static int add_implementing_graphs (entity *method)
112 int n_over = get_entity_n_overwrittenby (method);
113 ir_graph *graph = get_entity_irg (method);
117 graph = get_implementing_graph (method);
121 fprintf(stdout, "RTA: new call to ");
125 if (rta_is_alive_class (get_entity_owner (method))) {
127 change = add_graph (graph);
131 for (i = 0; i < n_over; i ++) {
132 entity *over = get_entity_overwrittenby (method, i);
133 change |= add_implementing_graphs (over);
140 Enter all method accesses and all class allocations into
143 Set *(int*)env to true iff (possibly) new graphs have been found.
145 static void rta_act (ir_node *node, void *env)
147 int *change = (int*) env;
149 opcode op = get_irn_opcode (node);
151 if (iro_Call == op) { /* CALL */
154 ir_node *ptr = get_Call_ptr (node);
156 if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
157 ent = get_Sel_entity (ptr);
158 *change = add_implementing_graphs (ent);
159 } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
160 ent = get_tarval_entity (get_Const_tarval (ptr));
161 ir_graph *graph = get_entity_irg (ent);
162 /* don't use get_implementing_graph on a Const! */
164 *change = add_graph (graph);
166 /* it's an externally allocated thing. */
168 } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
169 /* If this SymConst refers to a method the method is external_visible
170 and therefore must be considered live anyways. */
171 /* assert (ent && "couldn't determine entity of call to symConst"); */
173 } else if (iro_Alloc == op) { /* ALLOC */
174 type *type = get_Alloc_type (node);
176 *change = add_class (type);
181 Traverse the given graph to collect method accesses and
184 static int rta_fill_graph (ir_graph* graph)
188 current_ir_graph = graph;
190 irg_walk (get_irg_end (graph), rta_act, NULL, &change);
196 Traverse all graphs to collect method accesses and object allocations.
198 @param rerun Whether to rely on is_alive in a second run
200 static int rta_fill_incremental (void)
205 int old_ip_view = interprocedural_view;
207 interprocedural_view = 0; /* save this for later */
209 /* init_tables has added main_irg to _live_graphs */
211 /* Need to take care of graphs that are externally
212 visible or sticky. Pretend that they are called: */
214 for (i = 0; i < get_irp_n_irgs(); i++) {
215 ir_graph *graph = get_irp_irg (i);
216 entity *ent = get_irg_entity (graph);
218 if (((!whole_world) &&
219 (visibility_external_visible == get_entity_visibility (ent))) ||
220 (stickyness_sticky == get_entity_stickyness (ent))) {
221 eset_insert (_live_graphs, graph);
229 eset *live_graphs = _live_graphs;
230 _live_graphs = eset_create ();
233 fprintf(stdout, "RTA: RUN %i\n", n_runs);
236 /* collect what we have found previously */
237 eset_insert_all (_live_graphs, live_graphs);
241 for (graph = eset_first (live_graphs);
243 graph = eset_next (live_graphs)) {
246 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
247 DDMEO(get_irg_ent (graph));
250 rerun |= rta_fill_graph (graph);
253 eset_destroy (live_graphs);
258 interprocedural_view = old_ip_view; /* cover up our traces */
264 Count the number of graphs that we have found to be live.
266 static int stats (void)
269 int n_live_graphs = 0;
270 int n_graphs = get_irp_n_irgs();
272 for (i = 0; i < n_graphs; i++) {
273 ir_graph *graph = get_irp_irg(i);
275 if (rta_is_alive_graph (graph)) {
280 return (n_live_graphs);
283 /* remove a graph, part I */
285 We removed the first graph to implement the entity, so we're
286 abstract now. Pretend that it wasn't there at all, and every
287 entity that used to inherit this entity's graph is now abstract.
289 /* Since we *know* that this entity will not be called, this is OK. */
290 static void force_description (entity *ent, entity *addr)
292 int i, n_over = get_entity_n_overwrittenby (ent);
294 set_entity_peculiarity (ent, peculiarity_description);
296 for (i = 0; i < n_over; i ++) {
297 entity *over = get_entity_overwrittenby (ent, i);
299 if (peculiarity_inherited == get_entity_peculiarity (over)) {
300 /* We rely on the fact that cse is performed on the const_code_irg. */
302 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
304 if (addr == my_addr) {
305 force_description (over, addr);
307 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
308 /* check whether 'over' forces 'inheritance' of *our* graph: */
309 ir_node *f_addr = get_atomic_ent_value (over);
310 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
312 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
313 if (impl_ent == addr) {
314 assert (0 && "gibt's denn sowas");
315 force_description (over, addr);
321 /* remove a graph, part II */
323 Note: get_implementing_graph is not well defined here (graph->ent
324 could overwrite more than one superclass implementation (graph).
325 Since we *know* that this entity will not be called, this is OK.
327 static void remove_irg (ir_graph *graph)
329 entity *ent = get_irg_entity (graph);
330 peculiarity pec = get_entity_peculiarity (ent);
332 /* DDMEO (get_irg_ent(graph)); */
334 /* delete the ir_graph data */
335 set_entity_peculiarity (ent, peculiarity_description);
336 remove_irp_irg (graph);
337 /* remove_irp_irg also removes the entities' reference to the graph */
339 if (NULL != get_entity_irg (ent)) {
340 set_entity_irg (ent, NULL);
343 set_entity_peculiarity (ent, pec);
345 /* find the implementation (graph) from *some* superclass: */
346 graph = get_implementing_graph (ent);
348 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
349 /* nothing to inherit! pretend we're abstract */
350 force_description (ent, ent);
352 /* pretend that we inherit the implementation (graph) from some superclass: */
353 set_entity_peculiarity (ent, peculiarity_inherited);
355 exchange (get_atomic_ent_value (ent),
356 get_atomic_ent_value (get_irg_ent(graph)));
361 Initialise the static data structures.
363 static void init_tables (void)
365 _live_classes = eset_create ();
367 _live_graphs = eset_create ();
369 if (get_irp_main_irg ()) {
370 eset_insert (_live_graphs, get_irp_main_irg ());
374 if (get_glob_type ()) {
375 eset_insert (_live_classes, get_glob_type ());
380 /* Initialise the RTA data structures, and perform RTA.
381 @param do_verbose If == 1, print statistics, if > 1, chatter about every detail
382 @param do_whole_world Iff != 0, assume whole-world
384 void rta_init (int do_verbose, int do_whole_world)
388 # ifdef DEBUG_libfirm
390 for (i = 0; i < get_irp_n_irgs(); i++) {
391 irg_vrfy (get_irp_irg(i));
394 # endif /* defined DEBUG_libfirm */
396 whole_world = do_whole_world;
397 verbose = do_verbose;
401 n_runs = rta_fill_incremental ();
404 int n_live_graphs = stats ();
407 printf ("RTA: whole-world assumption\n");
409 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
410 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
411 printf ("RTA: n_runs = %i\n", n_runs);
414 # ifdef DEBUG_libfirm
415 for (i = 0; i < get_irp_n_irgs(); i++) {
416 irg_vrfy (get_irp_irg(i));
419 # endif /* defined DEBUG_libfirm */
422 /* Delete all graphs that we have found to be dead from the program
423 If verbose == 1, print statistics, if > 1, chatter about every detail
425 void rta_delete_dead_graphs (void)
428 int n_graphs = get_irp_n_irgs ();
429 ir_graph *graph = NULL;
430 int n_dead_graphs = 0;
432 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
434 eset *dead_graphs = eset_create ();
436 for (i = 0; i < n_graphs; i++) {
437 graph = get_irp_irg(i);
439 if (rta_is_alive_graph (graph)) {
440 /* do nothing (except some debugging fprintf`s :-) */
442 # ifdef DEBUG_libfirm
443 entity *ent = get_irg_entity (graph);
444 assert (whole_world ||
445 (visibility_external_visible != get_entity_visibility (ent)));
446 # endif /* defined DEBUG_libfirm */
449 eset_insert (dead_graphs, graph);
453 /* now delete the graphs. */
454 for (graph = eset_first (dead_graphs);
456 graph = (ir_graph*) eset_next (dead_graphs)) {
458 if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
459 fprintf(stdout, "RTA: removing graph of ");
460 DDMEO(get_irg_ent (graph));
467 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
471 /* Clean up the RTA data structures. Call this after calling rta_init */
472 void rta_cleanup (void)
474 # ifdef DEBUG_libfirm
476 for (i = 0; i < get_irp_n_irgs(); i++) {
477 irg_vrfy (get_irp_irg(i));
480 # endif /* defined DEBUG_libfirm */
483 eset_destroy (_live_classes);
484 _live_classes = NULL;
488 eset_destroy (_live_graphs);
493 /* Say whether this class might be instantiated at any point in the program: */
494 int rta_is_alive_class (type *clazz)
496 return (eset_contains (_live_classes, clazz));
499 /* Say whether this graph might be run at any time in the program: */
500 int rta_is_alive_graph (ir_graph *graph)
502 if (eset_contains (_live_graphs, graph)) {
509 /* dump our opinion */
510 void rta_report (void)
514 for (i = 0; i < get_irp_n_types(); ++i) {
515 type *tp = get_irp_type(i);
516 if (is_class_type(tp) && rta_is_alive_class(tp)) {
517 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
521 for (i = 0; i < get_irp_n_irgs(); i++) {
522 if (rta_is_alive_graph (get_irp_irg(i))) {
523 fprintf(stdout, "RTA: considered called: graph of ");
524 DDMEO(get_irg_ent (get_irp_irg(i)));
532 * Revision 1.17 2004/06/25 13:45:13 liekweg
533 * observe stickyness; minor refactoring
535 * Revision 1.16 2004/06/24 06:42:14 goetz
538 * Revision 1.15 2004/06/18 15:47:19 liekweg
539 * minor bug fix (go forward, not backward) --flo
541 * Revision 1.14 2004/06/18 13:12:43 liekweg
542 * final bug fix (calls via consts)
544 * Revision 1.13 2004/06/17 16:34:33 liekweg
547 * Revision 1.12 2004/06/17 16:33:33 liekweg
550 * Revision 1.11 2004/06/17 14:21:13 liekweg
553 * Revision 1.10 2004/06/17 10:31:41 goetz
554 * irscc: bugfix, can now deal with loops not reachable from start
555 * cgana: bugfix, skip_Tuple
558 * Revision 1.9 2004/06/17 08:56:03 liekweg
559 * Fixed typos in comments
561 * Revision 1.8 2004/06/17 08:33:01 liekweg
562 * Added comments; added remove_irg
564 * Revision 1.6 2004/06/14 13:02:03 goetz
567 * Revision 1.5 2004/06/13 15:03:45 liekweg
568 * RTA auf Iterative RTA aufgebohrt --flo
570 * Revision 1.4 2004/06/12 19:35:04 liekweg
571 * Kommentare eingef"ugt --flo
573 * Revision 1.3 2004/06/12 17:09:46 liekweg
574 * RTA works, outedges breaks. "Yay." --flo
576 * Revision 1.2 2004/06/11 18:25:39 liekweg
579 * Revision 1.1 2004/06/11 18:24:18 liekweg