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;
43 static eset *_live_fields = NULL;
44 static eset *_called_methods = NULL;
46 /* cache computed results */
47 static eset *_live_graphs = NULL;
48 static eset *_dead_graphs = NULL;
50 static int whole_world = 0;
51 static int verbose = 0;
54 Initialise the static data structures.
56 static void init_tables (void)
58 _live_classes = eset_create ();
59 _live_fields = eset_create ();
60 _called_methods = eset_create ();
62 _live_graphs = eset_create ();
63 _dead_graphs = eset_create ();
65 if (get_irp_main_irg ()) {
66 eset_insert (_live_graphs, get_irp_main_irg ());
69 if (get_glob_type ()) {
70 eset_insert (_live_classes, get_glob_type ());
75 Enter all method and field accesses and all class allocations into
78 static void rta_act (ir_node *node, void *env)
80 opcode op = get_irn_opcode (node);
82 if (iro_Call == op) { /* CALL */
85 ir_node *ptr = get_Call_ptr (node);
87 if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
88 ent = get_Sel_entity (ptr);
89 eset_insert (_called_methods, ent);
90 } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
91 ent = get_tarval_entity (get_Const_tarval (ptr));
92 ir_graph *graph = get_entity_irg (ent);
94 eset_insert (_live_graphs, graph);
95 } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
96 /* If this SymConst refers to a method the method is external_visible
97 and therefore must be considered live anyways. */
98 /* assert (ent && "couldn't determine entity of call to symConst"); */
100 } else if (iro_Load == op) { /* LOAD */
101 ir_node *ptr = get_Load_ptr (node);
104 if (iro_Sel == get_irn_opcode (ptr)) {
105 ent = get_Sel_entity (ptr);
108 eset_insert (_live_fields, ent);
110 } else if (iro_Store == op) { /* STORE */
111 ir_node *ptr = get_Store_ptr (node);
114 if (iro_Sel == get_irn_opcode (ptr)) {
115 ent = get_Sel_entity (ptr);
118 eset_insert (_live_fields, ent);
120 } else if (iro_Alloc == op) { /* ALLOC */
121 type *type = get_Alloc_type (node);
123 eset_insert (_live_classes, type);
128 Traverse the given graph to collect method and field accesses and
131 static void rta_fill_graph (ir_graph* graph)
134 if (NULL != get_irg_end (graph)) {
135 current_ir_graph = graph;
137 irg_walk (get_irg_end (graph), rta_act, NULL, NULL);
143 Check whether the given graph is alive based on the contents of the
146 static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
148 if (eset_contains (live_graphs, graph)) {
152 if (eset_contains (dead_graphs, graph)) {
156 assert (0 && "graph neither live not dead (shouldn't happen)");
160 Traverse all graphs to collect method and field accesses and object allocations.
162 @param rerun Whether to rely on is_alive in a second run
164 static void rta_fill_all (int rerun)
167 int old_ip_view = interprocedural_view;
168 eset *live_graphs = NULL;
169 eset *dead_graphs = NULL;
171 interprocedural_view = 0; /* save this for later */
174 int n_graphs = get_irp_n_irgs ();
176 /* force all graphs to be entered in either live_graphs or dead_graphs */
177 for (i = 0; i < n_graphs; i ++) {
178 rta_is_alive_graph (get_irp_irg (i));
181 /* remember existing infos for later */
182 live_graphs = _live_graphs;
183 dead_graphs = _dead_graphs;
185 /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
193 /* Consider all graphs, possibly taking into account existing infos */
194 for (i = 0; i < get_irp_n_irgs(); i++) {
195 ir_graph *graph = get_irp_irg (i);
198 /* Need to take care of graphs that are externally
199 visible. Pretend that they are called: */
200 entity *ent = get_irg_entity (graph);
201 if (visibility_external_visible == get_entity_visibility (ent)) {
202 /* eset_insert (_called_methods, ent); */
204 if (get_entity_irg (ent)) {
205 eset_insert (_live_graphs, get_entity_irg (ent));
208 /* eset_insert (_live_classes, get_entity_owner (ent)); */
212 /* now check the graph */
214 if (is_alive (graph, live_graphs, dead_graphs)) {
215 rta_fill_graph (graph);
217 /* nothing (except debugging printf's :-) */
220 rta_fill_graph (graph);
225 /* clean up the tables that we have retained */
226 eset_destroy (live_graphs);
227 eset_destroy (dead_graphs);
230 interprocedural_view = old_ip_view; /* cover up our traces */
234 Given a method, find the firm graph that implements that method.
236 static ir_graph *get_implementing_graph (entity *method)
238 ir_graph *graph = get_entity_irg ((entity*) method);
242 int n_over = get_entity_n_overwrites ((entity*) method);
244 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
245 entity *over = get_entity_overwrites ((entity*) method, i);
246 graph = get_implementing_graph (over);
250 /* we *must* always return a graph != NULL, *except* when we're used
251 inside remove_irg or force_description */
252 /* assert (graph && "no graph"); */
257 /* -------------------------------------------------------------------
259 ------------------------------------------------------------------- */
261 Find out whether the given method could be the target of a
264 static int has_live_upcall (entity *method)
266 int is_target = FALSE;
270 /* The method could be the target of a polymorphic call if it is
271 called or if it overrides a method that is called. */
273 if (eset_contains (_called_methods, (entity*) method)) {
277 /* not called? check methods in superclass(es) */
278 n_over = get_entity_n_overwrites ((entity*) method);
279 for (i = 0; !is_target && (i < n_over); i ++) {
280 entity *over = get_entity_overwrites ((entity*) method, i);
281 is_target |= has_live_upcall (over);
288 Determine wether the given method is called through polymorphy with
291 static int has_live_downcall (entity *method, ir_graph *graph)
293 int has_downcall = FALSE;
296 if (graph != get_entity_irg ((entity*) method)) {
300 if (eset_contains (_called_methods, method)) {
304 /* maybe we're overwritten by a method that is called? */
305 n_over = get_entity_n_overwrittenby ((entity*) method);
306 for (i = 0; !has_downcall && (i < n_over); i ++) {
307 entity *over = get_entity_overwrittenby ((entity*) method, i);
308 has_downcall |= has_live_downcall (over, graph);
311 return (has_downcall);
315 Determine whether the given method or one of its overwriters have
316 been used in a call to the given graph.
318 static int has_live_call (entity *method, ir_graph *graph)
320 /* maybe we're called (possibly through polymorphy)? */
321 if (has_live_upcall (method)) {
325 /* maybe our subclasses have seen a call? */
326 if (has_live_downcall (method, graph)) {
333 /* -------------------------------------------------------------------
335 ------------------------------------------------------------------- */
336 static int has_live_superclass (entity *method, ir_graph *graph)
338 int has_super = FALSE;
342 /* The method could be the target of a polymorphic call if it is
343 called or if it overrides a method that is called. */
345 if (eset_contains (_live_classes, get_entity_owner (method))) {
349 /* not allocated? check methods in superclass(es) */
350 n_over = get_entity_n_overwrites ((entity*) method);
351 for (i = 0; !has_super && (i < n_over); i ++) {
352 entity *over = get_entity_overwrites ((entity*) method, i);
353 has_super |= has_live_superclass (over, graph);
359 static int has_live_subclass (entity *method, ir_graph *graph)
365 /* a class that doesn't use the graph in question can't help here: */
366 ir_graph *impl = get_implementing_graph (method);
368 /* this function is only called starting at 'graph's method, and
369 we're checking *downwards*, so impl must be != NULL */
375 /* otherwise, an instantiated class helps a lot! */
376 if (rta_is_alive_class (get_entity_owner (method))) {
380 /* maybe our subclasses use this graph *and* have been instantiated ? */
381 n_over = get_entity_n_overwrittenby ((entity*) method);
382 for (i = 0; !has_sub && (i < n_over); i ++) {
383 entity *over = get_entity_overwrittenby ((entity*) method, i);
384 has_sub |= has_live_subclass (over, graph);
392 Determine whether the given method could be used in a call to the
393 given graph on a live class.
395 static int has_live_class (entity *method, ir_graph *graph)
397 /* maybe we're called (possibly through polymorphy)? */
398 if (has_live_superclass (method, graph)) {
402 /* maybe our subclasses have seen a call? */
403 if (has_live_subclass (method, graph)) {
412 Count the number of graphs that we have found to be live. Since
413 this touches every graph of the irp, it also forces that each graph
414 is either in _live_graphs xor in _dead_graphs. This is useful if
415 we use is_alive(ir_graph*) internally.
417 static int stats (void)
420 int n_live_graphs = 0;
421 int n_graphs = get_irp_n_irgs();
423 for (i = 0; i < n_graphs; i++) {
424 ir_graph *graph = get_irp_irg(i);
426 if (rta_is_alive_graph (graph)) {
431 return (n_live_graphs);
434 /* remove a graph, part I */
436 We removed the first graph to implement the entity, so we're
437 abstract now. Pretend that it wasn't there at all, and every
438 entity that used to inherit this entity's graph is now abstract.
440 /* Since we *know* that this entity will not be called, this is OK. */
441 static void force_description (entity *ent, entity *addr)
443 int i, n_over = get_entity_n_overwrittenby (ent);
445 set_entity_peculiarity (ent, peculiarity_description);
447 for (i = 0; i < n_over; i ++) {
448 entity *over = get_entity_overwrittenby (ent, i);
450 if (peculiarity_inherited == get_entity_peculiarity (over)) {
451 /* We rely on the fact that cse is performed on the const_code_irg. */
453 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
455 if (addr == my_addr) {
456 force_description (over, addr);
458 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
459 /* check whether 'over' forces 'inheritance' of *our* graph: */
460 ir_node *f_addr = get_atomic_ent_value (over);
461 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
463 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
464 if (impl_ent == addr) {
465 assert (0 && "gibt's denn sowas");
466 force_description (over, addr);
472 /* remove a graph, part II */
474 Note: get_implementing_graph is not well defined here (graph->ent
475 could overwrite more than one superclass implementation (graph).
476 Since we *know* that this entity will not be called, this is OK.
478 static void remove_irg (ir_graph *graph)
480 entity *ent = get_irg_entity (graph);
482 /* DDMEO (get_irg_ent(graph)); */
484 /* delete the ir_graph data */
485 remove_irp_irg (graph);
486 /* remove reference to the graph */
487 set_entity_irg (ent, NULL);
488 /* find the implementation (graph) from *some* superclass: */
489 graph = get_implementing_graph (ent);
491 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
492 /* nothing to inherit! pretend we're abstract */
493 force_description (ent, ent);
495 /* pretend that we inherit the implementation (graph) from some superclass: */
496 set_entity_peculiarity (ent, peculiarity_inherited);
498 exchange (get_atomic_ent_value (ent),
499 get_atomic_ent_value (get_irg_ent(graph)));
503 /* Initialise the RTA data structures, and perform RTA.
504 @param do_verbose Iff != 0, print statistics as we go along
505 @param do_whole_world Iff != 0, assume whole-world
507 void rta_init (int do_verbose, int do_whole_world)
509 int n_live_graphs = get_irp_n_irgs ();
513 whole_world = do_whole_world;
514 verbose = do_verbose;
516 # ifdef DEBUG_libfirm
518 for (i = 0; i < get_irp_n_irgs(); i++) {
519 irg_vrfy (get_irp_irg(i));
522 # endif /* defined DEBUG_libfirm */
526 if (verbose && whole_world) {
527 printf ("RTA: whole-world assumption\n");
531 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
534 rta_fill_all (FALSE);
536 while (n_graphs != n_live_graphs) {
537 n_graphs = n_live_graphs;
540 n_live_graphs = stats ();
543 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
548 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
549 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
550 printf ("RTA: n_runs = %i\n", n_runs);
553 # ifdef DEBUG_libfirm
554 for (i = 0; i < get_irp_n_irgs(); i++) {
555 irg_vrfy (get_irp_irg(i));
558 # endif /* defined DEBUG_libfirm */
561 /* Delete all graphs that we have found to be dead from the program */
562 void rta_delete_dead_graphs (void)
565 int n_graphs = get_irp_n_irgs ();
566 ir_graph *graph = NULL;
568 eset *dead_graphs = eset_create ();
570 for (i = 0; i < n_graphs; i++) {
571 graph = get_irp_irg(i);
573 if (is_alive (graph, _live_graphs, _dead_graphs)) {
574 /* do nothing (except some debugging fprintf`s :-) */
576 # ifdef DEBUG_libfirm
577 entity *ent = get_irg_entity (graph);
578 assert (whole_world ||
579 (visibility_external_visible != get_entity_visibility (ent)));
580 # endif /* defined DEBUG_libfirm */
582 eset_insert (dead_graphs, graph);
586 /* now delete the graphs. */
587 for (graph = eset_first (dead_graphs);
589 graph = (ir_graph*) eset_next (dead_graphs)) {
592 fprintf(stdout, "RTA: removing graph of ");
593 DDMEO(get_irg_ent (graph));
600 /* Clean up the RTA data structures. Call this after calling rta_init */
601 void rta_cleanup (void)
603 # ifdef DEBUG_libfirm
605 for (i = 0; i < get_irp_n_irgs(); i++) {
606 irg_vrfy (get_irp_irg(i));
609 # endif /* defined DEBUG_libfirm */
612 eset_destroy (_live_classes);
613 _live_classes = NULL;
617 eset_destroy (_live_fields);
621 if (_called_methods) {
622 eset_destroy (_called_methods);
623 _called_methods = NULL;
627 eset_destroy (_live_graphs);
632 eset_destroy (_dead_graphs);
637 /* Say whether this class might be instantiated at any point in the program: */
638 int rta_is_alive_class (type *clazz)
640 return (eset_contains (_live_classes, clazz));
643 /* Say whether this graph might be run at any time in the program: */
644 int rta_is_alive_graph (ir_graph *graph)
646 int has_call = FALSE;
647 int has_class = FALSE;
649 if (eset_contains (_live_graphs, graph)) {
653 if (eset_contains (_dead_graphs, graph)) {
657 entity *meth = get_irg_ent (graph);
659 has_call = has_live_call (meth, graph);
660 has_class = has_live_class (meth, graph);
662 if (has_call && has_class) {
663 eset_insert (_live_graphs, graph);
667 eset_insert (_dead_graphs, graph);
673 /* Say whether there have been any accesses to this field: */
674 int rta_is_alive_field (entity *field)
676 return (eset_contains (_live_fields, field));
679 /* dump our opinion */
680 void rta_report (void)
684 for (i = 0; i < get_irp_n_types(); ++i) {
685 type *tp = get_irp_type(i);
686 if (is_class_type(tp) && rta_is_alive_class(tp)) {
687 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
691 for (i = 0; i < get_irp_n_irgs(); i++) {
692 if (rta_is_alive_graph (get_irp_irg(i))) {
693 fprintf(stdout, "RTA: considered called: graph of ");
694 DDMEO(get_irg_ent (get_irp_irg(i)));
702 * Revision 1.14 2004/06/18 13:12:43 liekweg
703 * final bug fix (calls via consts)
705 * Revision 1.13 2004/06/17 16:34:33 liekweg
708 * Revision 1.12 2004/06/17 16:33:33 liekweg
711 * Revision 1.11 2004/06/17 14:21:13 liekweg
714 * Revision 1.10 2004/06/17 10:31:41 goetz
715 * irscc: bugfix, can now deal with loops not reachable from start
716 * cgana: bugfix, skip_Tuple
719 * Revision 1.9 2004/06/17 08:56:03 liekweg
720 * Fixed typos in comments
722 * Revision 1.8 2004/06/17 08:33:01 liekweg
723 * Added comments; added remove_irg
725 * Revision 1.6 2004/06/14 13:02:03 goetz
728 * Revision 1.5 2004/06/13 15:03:45 liekweg
729 * RTA auf Iterative RTA aufgebohrt --flo
731 * Revision 1.4 2004/06/12 19:35:04 liekweg
732 * Kommentare eingef"ugt --flo
734 * Revision 1.3 2004/06/12 17:09:46 liekweg
735 * RTA works, outedges breaks. "Yay." --flo
737 * Revision 1.2 2004/06/11 18:25:39 liekweg
740 * Revision 1.1 2004/06/11 18:24:18 liekweg