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.
16 * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es
17 * die Menge der instantiierten Klassen bestimmt, und daraus eine Abschätzung
18 * der aufgerufenen Methoden bestimmt.
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 ());
373 /* Adding the GlobalType is pointless, since its methods are always
374 called via a constant */
376 if (get_glob_type ()) {
377 eset_insert (_live_classes, get_glob_type ());
382 /* Initialise the RTA data structures, and perform RTA.
383 @param do_verbose If == 1, print statistics, if > 1, chatter about every detail
384 @param do_whole_world Iff != 0, assume whole-world
386 void rta_init (int do_verbose, int do_whole_world)
390 # ifdef DEBUG_libfirm
392 for (i = 0; i < get_irp_n_irgs(); i++) {
393 irg_vrfy (get_irp_irg(i));
396 # endif /* defined DEBUG_libfirm */
398 whole_world = do_whole_world;
399 verbose = do_verbose;
403 n_runs = rta_fill_incremental ();
406 int n_live_graphs = stats ();
409 printf ("RTA: whole-world assumption\n");
411 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
412 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
413 printf ("RTA: n_runs = %i\n", n_runs);
416 # ifdef DEBUG_libfirm
417 for (i = 0; i < get_irp_n_irgs(); i++) {
418 irg_vrfy (get_irp_irg(i));
421 # endif /* defined DEBUG_libfirm */
424 /* Delete all graphs that we have found to be dead from the program
425 If verbose == 1, print statistics, if > 1, chatter about every detail
427 void rta_delete_dead_graphs (void)
430 int n_graphs = get_irp_n_irgs ();
431 ir_graph *graph = NULL;
432 int n_dead_graphs = 0;
434 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
436 eset *dead_graphs = eset_create ();
438 for (i = 0; i < n_graphs; i++) {
439 graph = get_irp_irg(i);
441 if (rta_is_alive_graph (graph)) {
442 /* do nothing (except some debugging fprintf`s :-) */
444 # ifdef DEBUG_libfirm
445 entity *ent = get_irg_entity (graph);
446 assert (whole_world ||
447 (visibility_external_visible != get_entity_visibility (ent)));
448 # endif /* defined DEBUG_libfirm */
451 eset_insert (dead_graphs, graph);
455 /* now delete the graphs. */
456 for (graph = eset_first (dead_graphs);
458 graph = (ir_graph*) eset_next (dead_graphs)) {
460 if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
461 fprintf(stdout, "RTA: removing graph of ");
462 DDMEO(get_irg_ent (graph));
469 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
473 /* Clean up the RTA data structures. Call this after calling rta_init */
474 void rta_cleanup (void)
476 # ifdef DEBUG_libfirm
478 for (i = 0; i < get_irp_n_irgs(); i++) {
479 irg_vrfy (get_irp_irg(i));
482 # endif /* defined DEBUG_libfirm */
485 eset_destroy (_live_classes);
486 _live_classes = NULL;
490 eset_destroy (_live_graphs);
495 /* Say whether this class might be instantiated at any point in the program: */
496 int rta_is_alive_class (type *clazz)
498 return (eset_contains (_live_classes, clazz));
501 /* Say whether this graph might be run at any time in the program: */
502 int rta_is_alive_graph (ir_graph *graph)
504 if (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_ent (get_irp_irg(i)));
534 * Revision 1.18 2004/06/27 21:17:41 liekweg
537 * Revision 1.17 2004/06/25 13:45:13 liekweg
538 * observe stickyness; minor refactoring
540 * Revision 1.16 2004/06/24 06:42:14 goetz
543 * Revision 1.15 2004/06/18 15:47:19 liekweg
544 * minor bug fix (go forward, not backward) --flo
546 * Revision 1.14 2004/06/18 13:12:43 liekweg
547 * final bug fix (calls via consts)
549 * Revision 1.13 2004/06/17 16:34:33 liekweg
552 * Revision 1.12 2004/06/17 16:33:33 liekweg
555 * Revision 1.11 2004/06/17 14:21:13 liekweg
558 * Revision 1.10 2004/06/17 10:31:41 goetz
559 * irscc: bugfix, can now deal with loops not reachable from start
560 * cgana: bugfix, skip_Tuple
563 * Revision 1.9 2004/06/17 08:56:03 liekweg
564 * Fixed typos in comments
566 * Revision 1.8 2004/06/17 08:33:01 liekweg
567 * Added comments; added remove_irg
569 * Revision 1.6 2004/06/14 13:02:03 goetz
572 * Revision 1.5 2004/06/13 15:03:45 liekweg
573 * RTA auf Iterative RTA aufgebohrt --flo
575 * Revision 1.4 2004/06/12 19:35:04 liekweg
576 * Kommentare eingef"ugt --flo
578 * Revision 1.3 2004/06/12 17:09:46 liekweg
579 * RTA works, outedges breaks. "Yay." --flo
581 * Revision 1.2 2004/06/11 18:25:39 liekweg
584 * Revision 1.1 2004/06/11 18:24:18 liekweg