5 * File name: ir/ana/rta.c
6 * Purpose: Intraprozedural analyses 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. Pretend that they are called: */
215 for (i = 0; i < get_irp_n_irgs(); i++) {
216 ir_graph *graph = get_irp_irg (i);
218 entity *ent = get_irg_entity (graph);
219 if (visibility_external_visible == get_entity_visibility (ent)) {
221 eset_insert (_live_graphs, graph);
223 /* eset_insert (_live_classes, get_entity_owner (ent)); */
232 eset *live_graphs = _live_graphs;
233 _live_graphs = eset_create ();
236 fprintf(stdout, "RTA: RUN %i\n", n_runs);
239 /* collect what we have found previously */
240 eset_insert_all (_live_graphs, live_graphs);
244 for (graph = eset_first (live_graphs);
246 graph = eset_next (live_graphs)) {
249 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
250 DDMEO(get_irg_ent (graph));
253 rerun |= rta_fill_graph (graph);
256 eset_destroy (live_graphs);
261 interprocedural_view = old_ip_view; /* cover up our traces */
267 Count the number of graphs that we have found to be live.
269 static int stats (void)
272 int n_live_graphs = 0;
273 int n_graphs = get_irp_n_irgs();
275 for (i = 0; i < n_graphs; i++) {
276 ir_graph *graph = get_irp_irg(i);
278 if (rta_is_alive_graph (graph)) {
283 return (n_live_graphs);
286 /* remove a graph, part I */
288 We removed the first graph to implement the entity, so we're
289 abstract now. Pretend that it wasn't there at all, and every
290 entity that used to inherit this entity's graph is now abstract.
292 /* Since we *know* that this entity will not be called, this is OK. */
293 static void force_description (entity *ent, entity *addr)
295 int i, n_over = get_entity_n_overwrittenby (ent);
297 set_entity_peculiarity (ent, peculiarity_description);
299 for (i = 0; i < n_over; i ++) {
300 entity *over = get_entity_overwrittenby (ent, i);
302 if (peculiarity_inherited == get_entity_peculiarity (over)) {
303 /* We rely on the fact that cse is performed on the const_code_irg. */
305 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
307 if (addr == my_addr) {
308 force_description (over, addr);
310 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
311 /* check whether 'over' forces 'inheritance' of *our* graph: */
312 ir_node *f_addr = get_atomic_ent_value (over);
313 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
315 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
316 if (impl_ent == addr) {
317 assert (0 && "gibt's denn sowas");
318 force_description (over, addr);
324 /* remove a graph, part II */
326 Note: get_implementing_graph is not well defined here (graph->ent
327 could overwrite more than one superclass implementation (graph).
328 Since we *know* that this entity will not be called, this is OK.
330 static void remove_irg (ir_graph *graph)
332 entity *ent = get_irg_entity (graph);
334 /* DDMEO (get_irg_ent(graph)); */
336 /* delete the ir_graph data */
337 remove_irp_irg (graph);
338 /* remove reference to the graph */
339 set_entity_irg (ent, NULL);
340 /* find the implementation (graph) from *some* superclass: */
341 graph = get_implementing_graph (ent);
343 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
344 /* nothing to inherit! pretend we're abstract */
345 force_description (ent, ent);
347 /* pretend that we inherit the implementation (graph) from some superclass: */
348 set_entity_peculiarity (ent, peculiarity_inherited);
350 exchange (get_atomic_ent_value (ent),
351 get_atomic_ent_value (get_irg_ent(graph)));
356 Initialise the static data structures.
358 static void init_tables (void)
360 _live_classes = eset_create ();
362 _live_graphs = eset_create ();
364 if (get_irp_main_irg ()) {
365 eset_insert (_live_graphs, get_irp_main_irg ());
369 if (get_glob_type ()) {
370 eset_insert (_live_classes, get_glob_type ());
375 /* Initialise the RTA data structures, and perform RTA.
376 @param do_verbose Iff != 0, print statistics as we go along
377 @param do_whole_world Iff != 0, assume whole-world
379 void rta_init (int do_verbose, int do_whole_world)
381 int n_live_graphs = 0;
384 # ifdef DEBUG_libfirm
386 for (i = 0; i < get_irp_n_irgs(); i++) {
387 irg_vrfy (get_irp_irg(i));
390 # endif /* defined DEBUG_libfirm */
392 whole_world = do_whole_world;
393 verbose = do_verbose;
397 n_runs = rta_fill_incremental ();
399 n_live_graphs = stats ();
403 printf ("RTA: whole-world assumption\n");
405 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
406 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
407 printf ("RTA: n_runs = %i\n", n_runs);
410 # ifdef DEBUG_libfirm
411 for (i = 0; i < get_irp_n_irgs(); i++) {
412 irg_vrfy (get_irp_irg(i));
415 # endif /* defined DEBUG_libfirm */
418 /* Delete all graphs that we have found to be dead from the program */
419 void rta_delete_dead_graphs (void)
422 int n_graphs = get_irp_n_irgs ();
423 ir_graph *graph = NULL;
425 eset *dead_graphs = eset_create ();
427 for (i = 0; i < n_graphs; i++) {
428 graph = get_irp_irg(i);
430 if (rta_is_alive_graph (graph)) {
431 /* do nothing (except some debugging fprintf`s :-) */
433 # ifdef DEBUG_libfirm
434 entity *ent = get_irg_entity (graph);
435 assert (whole_world ||
436 (visibility_external_visible != get_entity_visibility (ent)));
437 # endif /* defined DEBUG_libfirm */
439 eset_insert (dead_graphs, graph);
443 /* now delete the graphs. */
444 for (graph = eset_first (dead_graphs);
446 graph = (ir_graph*) eset_next (dead_graphs)) {
449 fprintf(stdout, "RTA: removing graph of ");
450 DDMEO(get_irg_ent (graph));
457 /* Clean up the RTA data structures. Call this after calling rta_init */
458 void rta_cleanup (void)
460 # ifdef DEBUG_libfirm
462 for (i = 0; i < get_irp_n_irgs(); i++) {
463 irg_vrfy (get_irp_irg(i));
466 # endif /* defined DEBUG_libfirm */
469 eset_destroy (_live_classes);
470 _live_classes = NULL;
474 eset_destroy (_live_graphs);
479 /* Say whether this class might be instantiated at any point in the program: */
480 int rta_is_alive_class (type *clazz)
482 return (eset_contains (_live_classes, clazz));
485 /* Say whether this graph might be run at any time in the program: */
486 int rta_is_alive_graph (ir_graph *graph)
488 if (eset_contains (_live_graphs, graph)) {
495 /* dump our opinion */
496 void rta_report (void)
500 for (i = 0; i < get_irp_n_types(); ++i) {
501 type *tp = get_irp_type(i);
502 if (is_class_type(tp) && rta_is_alive_class(tp)) {
503 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
507 for (i = 0; i < get_irp_n_irgs(); i++) {
508 if (rta_is_alive_graph (get_irp_irg(i))) {
509 fprintf(stdout, "RTA: considered called: graph of ");
510 DDMEO(get_irg_ent (get_irp_irg(i)));
518 * Revision 1.15 2004/06/18 15:47:19 liekweg
519 * minor bug fix (go forward, not backward) --flo
521 * Revision 1.14 2004/06/18 13:12:43 liekweg
522 * final bug fix (calls via consts)
524 * Revision 1.13 2004/06/17 16:34:33 liekweg
527 * Revision 1.12 2004/06/17 16:33:33 liekweg
530 * Revision 1.11 2004/06/17 14:21:13 liekweg
533 * Revision 1.10 2004/06/17 10:31:41 goetz
534 * irscc: bugfix, can now deal with loops not reachable from start
535 * cgana: bugfix, skip_Tuple
538 * Revision 1.9 2004/06/17 08:56:03 liekweg
539 * Fixed typos in comments
541 * Revision 1.8 2004/06/17 08:33:01 liekweg
542 * Added comments; added remove_irg
544 * Revision 1.6 2004/06/14 13:02:03 goetz
547 * Revision 1.5 2004/06/13 15:03:45 liekweg
548 * RTA auf Iterative RTA aufgebohrt --flo
550 * Revision 1.4 2004/06/12 19:35:04 liekweg
551 * Kommentare eingef"ugt --flo
553 * Revision 1.3 2004/06/12 17:09:46 liekweg
554 * RTA works, outedges breaks. "Yay." --flo
556 * Revision 1.2 2004/06/11 18:25:39 liekweg
559 * Revision 1.1 2004/06/11 18:24:18 liekweg