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 external allocated thing. */
168 } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
169 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
170 ent = get_SymConst_entity (ptr);
171 ir_graph *graph = get_entity_irg (ent);
172 /* don't use get_implementing_graph on a SymConst! */
174 *change = add_graph (graph);
176 /* it's an external allocated thing. */
178 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
179 /* If this SymConst refers to a method the method is external_visible
180 and therefore must be considered live anyways. */
181 /* assert (ent && "couldn't determine entity of call to symConst"); */
183 /* other symconst. */
187 } else if (iro_Alloc == op) { /* ALLOC */
188 type *type = get_Alloc_type (node);
190 *change = add_class (type);
195 Traverse the given graph to collect method accesses and
198 static int rta_fill_graph (ir_graph* graph)
202 current_ir_graph = graph;
204 irg_walk (get_irg_end (graph), rta_act, NULL, &change);
210 Traverse all graphs to collect method accesses and object allocations.
212 @param rerun Whether to rely on is_alive in a second run
214 static int rta_fill_incremental (void)
219 int old_ip_view = interprocedural_view;
221 interprocedural_view = 0; /* save this for later */
223 /* init_tables has added main_irg to _live_graphs */
225 /* Need to take care of graphs that are externally
226 visible or sticky. Pretend that they are called: */
228 for (i = 0; i < get_irp_n_irgs(); i++) {
229 ir_graph *graph = get_irp_irg (i);
230 entity *ent = get_irg_entity (graph);
232 if (((!whole_world) &&
233 (visibility_external_visible == get_entity_visibility (ent))) ||
234 (stickyness_sticky == get_entity_stickyness (ent))) {
235 eset_insert (_live_graphs, graph);
243 eset *live_graphs = _live_graphs;
244 _live_graphs = eset_create ();
247 fprintf(stdout, "RTA: RUN %i\n", n_runs);
250 /* collect what we have found previously */
251 eset_insert_all (_live_graphs, live_graphs);
255 for (graph = eset_first (live_graphs);
257 graph = eset_next (live_graphs)) {
260 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
261 DDMEO(get_irg_ent (graph));
264 rerun |= rta_fill_graph (graph);
267 eset_destroy (live_graphs);
272 interprocedural_view = old_ip_view; /* cover up our traces */
278 Count the number of graphs that we have found to be live.
280 static int stats (void)
283 int n_live_graphs = 0;
284 int n_graphs = get_irp_n_irgs();
286 for (i = 0; i < n_graphs; i++) {
287 ir_graph *graph = get_irp_irg(i);
289 if (rta_is_alive_graph (graph)) {
294 return (n_live_graphs);
297 /* remove a graph, part I */
299 We removed the first graph to implement the entity, so we're
300 abstract now. Pretend that it wasn't there at all, and every
301 entity that used to inherit this entity's graph is now abstract.
303 /* Since we *know* that this entity will not be called, this is OK. */
304 static void force_description (entity *ent, entity *addr)
306 int i, n_over = get_entity_n_overwrittenby (ent);
308 set_entity_peculiarity (ent, peculiarity_description);
310 for (i = 0; i < n_over; i ++) {
311 entity *over = get_entity_overwrittenby (ent, i);
313 if (peculiarity_inherited == get_entity_peculiarity (over)) {
314 /* We rely on the fact that cse is performed on the const_code_irg. */
315 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
317 if (addr == my_addr) {
318 force_description (over, addr);
320 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
321 /* check whether 'over' forces 'inheritance' of *our* graph: */
322 ir_node *f_addr = get_atomic_ent_value (over);
323 entity *impl_ent = get_SymConst_entity (f_addr);
325 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
326 if (impl_ent == addr) {
327 assert (0 && "gibt's denn sowas");
328 force_description (over, addr);
334 /* remove a graph, part II */
336 Note: get_implementing_graph is not well defined here (graph->ent
337 could overwrite more than one superclass implementation (graph).
338 Since we *know* that this entity will not be called, this is OK.
340 static void remove_irg (ir_graph *graph)
342 entity *ent = get_irg_entity (graph);
343 peculiarity pec = get_entity_peculiarity (ent);
345 /* DDMEO (get_irg_ent(graph)); */
347 /* delete the ir_graph data */
348 set_entity_peculiarity (ent, peculiarity_description);
349 remove_irp_irg (graph);
350 /* remove_irp_irg also removes the entities' reference to the graph */
352 if (NULL != get_entity_irg (ent)) {
353 set_entity_irg (ent, NULL);
356 set_entity_peculiarity (ent, pec);
358 /* find the implementation (graph) from *some* superclass: */
359 graph = get_implementing_graph (ent);
361 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
362 /* nothing to inherit! pretend we're abstract */
363 force_description (ent, ent);
365 /* pretend that we inherit the implementation (graph) from some superclass: */
366 set_entity_peculiarity (ent, peculiarity_inherited);
368 exchange (get_atomic_ent_value (ent),
369 get_atomic_ent_value (get_irg_ent(graph)));
374 Initialise the static data structures.
376 static void init_tables (void)
378 _live_classes = eset_create ();
380 _live_graphs = eset_create ();
382 if (get_irp_main_irg ()) {
383 eset_insert (_live_graphs, get_irp_main_irg ());
386 /* Adding the GlobalType is pointless, since its methods are always
387 called via a constant */
389 if (get_glob_type ()) {
390 eset_insert (_live_classes, get_glob_type ());
395 /* Initialise the RTA data structures, and perform RTA.
396 @param do_verbose If == 1, print statistics, if > 1, chatter about every detail
397 @param do_whole_world Iff != 0, assume whole-world
399 void rta_init (int do_verbose, int do_whole_world)
403 # ifdef DEBUG_libfirm
405 for (i = 0; i < get_irp_n_irgs(); i++) {
406 irg_vrfy (get_irp_irg(i));
409 # endif /* defined DEBUG_libfirm */
411 whole_world = do_whole_world;
412 verbose = do_verbose;
416 n_runs = rta_fill_incremental ();
419 int n_live_graphs = stats ();
422 printf ("RTA: whole-world assumption\n");
424 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
425 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
426 printf ("RTA: n_runs = %i\n", n_runs);
429 # ifdef DEBUG_libfirm
430 for (i = 0; i < get_irp_n_irgs(); i++) {
431 irg_vrfy (get_irp_irg(i));
434 # endif /* defined DEBUG_libfirm */
437 /* Delete all graphs that we have found to be dead from the program
438 If verbose == 1, print statistics, if > 1, chatter about every detail
440 void rta_delete_dead_graphs (void)
443 int n_graphs = get_irp_n_irgs ();
444 ir_graph *graph = NULL;
445 int n_dead_graphs = 0;
447 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
449 eset *dead_graphs = eset_create ();
451 for (i = 0; i < n_graphs; i++) {
452 graph = get_irp_irg(i);
454 if (rta_is_alive_graph (graph)) {
455 /* do nothing (except some debugging fprintf`s :-) */
457 # ifdef DEBUG_libfirm
458 entity *ent = get_irg_entity (graph);
459 assert (whole_world ||
460 (visibility_external_visible != get_entity_visibility (ent)));
461 # endif /* defined DEBUG_libfirm */
464 eset_insert (dead_graphs, graph);
468 /* now delete the graphs. */
469 for (graph = eset_first (dead_graphs);
471 graph = (ir_graph*) eset_next (dead_graphs)) {
473 if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
474 fprintf(stdout, "RTA: removing graph of ");
475 DDMEO(get_irg_ent (graph));
482 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
486 /* Clean up the RTA data structures. Call this after calling rta_init */
487 void rta_cleanup (void)
489 # ifdef DEBUG_libfirm
491 for (i = 0; i < get_irp_n_irgs(); i++) {
492 irg_vrfy (get_irp_irg(i));
495 # endif /* defined DEBUG_libfirm */
498 eset_destroy (_live_classes);
499 _live_classes = NULL;
503 eset_destroy (_live_graphs);
508 /* Say whether this class might be instantiated at any point in the program: */
509 int rta_is_alive_class (type *clazz)
511 return (eset_contains (_live_classes, clazz));
514 /* Say whether this graph might be run at any time in the program: */
515 int rta_is_alive_graph (ir_graph *graph)
517 if (eset_contains (_live_graphs, graph)) {
524 /* dump our opinion */
525 void rta_report (void)
529 for (i = 0; i < get_irp_n_types(); ++i) {
530 type *tp = get_irp_type(i);
531 if (is_class_type(tp) && rta_is_alive_class(tp)) {
532 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
536 for (i = 0; i < get_irp_n_irgs(); i++) {
537 if (rta_is_alive_graph (get_irp_irg(i))) {
538 fprintf(stdout, "RTA: considered called: graph of ");
539 DDMEO(get_irg_ent (get_irp_irg(i)));
547 * Revision 1.21 2004/07/08 15:50:56 goetz
550 * Revision 1.20 2004/07/08 11:17:40 goetz
551 * *** empty log message ***
553 * Revision 1.19 2004/07/06 12:30:37 beyhan
554 * new SymConst semantics
556 * Revision 1.18 2004/06/27 21:17:41 liekweg
559 * Revision 1.17 2004/06/25 13:45:13 liekweg
560 * observe stickyness; minor refactoring
562 * Revision 1.16 2004/06/24 06:42:14 goetz
565 * Revision 1.15 2004/06/18 15:47:19 liekweg
566 * minor bug fix (go forward, not backward) --flo
568 * Revision 1.14 2004/06/18 13:12:43 liekweg
569 * final bug fix (calls via consts)
571 * Revision 1.13 2004/06/17 16:34:33 liekweg
574 * Revision 1.12 2004/06/17 16:33:33 liekweg
577 * Revision 1.11 2004/06/17 14:21:13 liekweg
580 * Revision 1.10 2004/06/17 10:31:41 goetz
581 * irscc: bugfix, can now deal with loops not reachable from start
582 * cgana: bugfix, skip_Tuple
585 * Revision 1.9 2004/06/17 08:56:03 liekweg
586 * Fixed typos in comments
588 * Revision 1.8 2004/06/17 08:33:01 liekweg
589 * Added comments; added remove_irg
591 * Revision 1.6 2004/06/14 13:02:03 goetz
594 * Revision 1.5 2004/06/13 15:03:45 liekweg
595 * RTA auf Iterative RTA aufgebohrt --flo
597 * Revision 1.4 2004/06/12 19:35:04 liekweg
598 * Kommentare eingef"ugt --flo
600 * Revision 1.3 2004/06/12 17:09:46 liekweg
601 * RTA works, outedges breaks. "Yay." --flo
603 * Revision 1.2 2004/06/11 18:25:39 liekweg
606 * Revision 1.1 2004/06/11 18:24:18 liekweg