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;
53 Initialise the static data structures.
55 static void init_tables (void)
57 _live_classes = eset_create ();
58 _live_fields = eset_create ();
59 _called_methods = eset_create ();
61 _live_graphs = eset_create ();
62 _dead_graphs = eset_create ();
64 if (get_irp_main_irg ()) {
65 eset_insert (_live_graphs, get_irp_main_irg ());
68 if (get_glob_type ()) {
69 eset_insert (_live_classes, get_glob_type ());
74 Enter all method and field accesses and all class allocations into
77 static void rta_act (ir_node *node, void *env)
79 opcode op = get_irn_opcode (node);
81 if (iro_Call == op) { /* CALL */
84 ir_node *ptr = get_Call_ptr (node);
86 if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
87 ent = get_Sel_entity (ptr);
88 } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
89 ent = get_tarval_entity (get_Const_tarval (ptr));
91 } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
92 /* If this SymConst refers to a method the method is external_visible
93 and therefore must be considered live anyways. */
94 /* assert (ent && "couldn't determine entity of call to symConst"); */
98 eset_insert (_called_methods, ent);
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)) {
274 /* fprintf (stdout, "RTA: found call to "); DDMEO (meth); */
278 /* not called? check methods in superclass(es) */
279 n_over = get_entity_n_overwrites ((entity*) method);
280 for (i = 0; !is_target && (i < n_over); i ++) {
281 entity *over = get_entity_overwrites ((entity*) method, i);
282 /* fprintf (stdout, "RTA: check in superclass "); DDMEO (over); */
283 is_target |= has_live_upcall (over);
290 Determine wether the given method is called through polymorphy with
293 static int has_live_downcall (entity *method, ir_graph *graph)
295 int has_downcall = FALSE;
298 if (graph != get_entity_irg ((entity*) method)) {
302 if (eset_contains (_called_methods, method)) {
306 /* maybe we're overwritten by a method that is called? */
307 n_over = get_entity_n_overwrittenby ((entity*) method);
308 for (i = 0; !has_downcall && (i < n_over); i ++) {
309 entity *over = get_entity_overwrittenby ((entity*) method, i);
310 has_downcall |= has_live_downcall (over, graph);
313 return (has_downcall);
317 Determine whether the given method or one of its overwriters have
318 been used in a call to the given graph.
320 static int has_live_call (entity *method, ir_graph *graph)
322 /* maybe we're called (possibly through polymorphy)? */
323 if (has_live_upcall (method)) {
327 /* maybe our subclasses have seen a call? */
328 if (has_live_downcall (method, graph)) {
335 /* -------------------------------------------------------------------
337 ------------------------------------------------------------------- */
338 static int has_live_superclass (entity *method, ir_graph *graph)
340 int has_super = FALSE;
344 /* The method could be the target of a polymorphic call if it is
345 called or if it overrides a method that is called. */
347 if (eset_contains (_live_classes, get_entity_owner (method))) {
351 /* not allocated? check methods in superclass(es) */
352 n_over = get_entity_n_overwrites ((entity*) method);
353 for (i = 0; !has_super && (i < n_over); i ++) {
354 entity *over = get_entity_overwrites ((entity*) method, i);
355 /* fprintf (stdout, "RTA: check in superclass "); DDMEO (over); */
356 has_super |= has_live_superclass (over, graph);
362 static int has_live_subclass (entity *method, ir_graph *graph)
368 /* a class that doesn't use the graph in question can't help here: */
369 ir_graph *impl = get_implementing_graph (method);
371 /* this function is only called starting at 'graph's method, and
372 we're checking *downwards*, so impl must be != NULL */
378 /* otherwise, an instantiated class helps a lot! */
379 if (rta_is_alive_class (get_entity_owner (method))) {
383 /* maybe our subclasses use this graph *and* have been instantiated ? */
384 n_over = get_entity_n_overwrittenby ((entity*) method);
385 for (i = 0; !has_sub && (i < n_over); i ++) {
386 entity *over = get_entity_overwrittenby ((entity*) method, i);
387 has_sub |= has_live_subclass (over, graph);
395 Determine whether the given method could be used in a call to the
396 given graph on a live class.
398 static int has_live_class (entity *method, ir_graph *graph)
400 /* maybe we're called (possibly through polymorphy)? */
401 if (has_live_superclass (method, graph)) {
405 /* maybe our subclasses have seen a call? */
406 if (has_live_subclass (method, graph)) {
415 Count the number of graphs that we have found to be live. Since
416 this touches every graph of the irp, it also forces that each graph
417 is either in _live_graphs xor in _dead_graphs. This is useful if
418 we use is_alive(ir_graph*) internally.
420 static int stats (void)
423 int n_live_graphs = 0;
424 int n_graphs = get_irp_n_irgs();
426 for (i = 0; i < n_graphs; i++) {
427 ir_graph *graph = get_irp_irg(i);
429 if (rta_is_alive_graph (graph)) {
434 return (n_live_graphs);
437 /* remove a graph, part I */
439 We removed the first graph to implement the entity, so we're
440 abstract now. Pretend that it wasn't there at all, and every
441 entity that used to inherit this entity's graph is now abstract.
443 /* Since we *know* that this entity will not be called, this is OK. */
444 static void force_description (entity *ent, entity *addr)
446 int i, n_over = get_entity_n_overwrittenby (ent);
448 set_entity_peculiarity (ent, peculiarity_description);
450 for (i = 0; i < n_over; i ++) {
451 entity *over = get_entity_overwrittenby (ent, i);
453 if (peculiarity_inherited == get_entity_peculiarity (over)) {
454 /* We rely on the fact that cse is performed on the const_code_irg. */
456 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
458 if (addr == my_addr) {
459 force_description (over, addr);
461 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
462 /* check whether 'over' forces 'inheritance' of *our* graph: */
463 ir_node *f_addr = get_atomic_ent_value (over);
464 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
466 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
467 if (impl_ent == addr) {
468 assert (0 && "gibt's denn sowas");
469 force_description (over, addr);
475 /* remove a graph, part II */
477 Note: get_implementing_graph is not well defined here (graph->ent
478 could overwrite more than one superclass implementation (graph).
479 Since we *know* that this entity will not be called, this is OK.
481 static void remove_irg (ir_graph *graph)
483 entity *ent = get_irg_entity (graph);
485 /* DDMEO (get_irg_ent(graph)); */
487 /* delete the ir_graph data */
488 remove_irp_irg (graph);
489 /* remove reference to the graph */
490 set_entity_irg (ent, NULL);
491 /* find the implementation (graph) from *some* superclass: */
492 graph = get_implementing_graph (ent);
494 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
495 /* nothing to inherit! pretend we're abstract */
496 force_description (ent, ent);
498 /* pretend that we inherit the implementation (graph) from some superclass: */
499 set_entity_peculiarity (ent, peculiarity_inherited);
501 exchange (get_atomic_ent_value (ent),
502 get_atomic_ent_value (get_irg_ent(graph)));
506 /* Initialise the RTA data structures, and perform RTA.
507 @param verbose Iff != 0, print statistics as we go along
509 void rta_init (int verbose, int do_whole_world)
511 int n_live_graphs = get_irp_n_irgs ();
515 whole_world = do_whole_world;
517 # ifdef DEBUG_libfirm
519 for (i = 0; i < get_irp_n_irgs(); i++) {
520 irg_vrfy (get_irp_irg(i));
523 # endif /* defined DEBUG_libfirm */
527 if (verbose && whole_world) {
528 printf ("RTA: whole-world assumption\n");
532 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
535 rta_fill_all (FALSE);
537 while (n_graphs != n_live_graphs) {
538 n_graphs = n_live_graphs;
541 n_live_graphs = stats ();
544 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
549 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
550 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
551 printf ("RTA: n_runs = %i\n", n_runs);
554 # ifdef DEBUG_libfirm
555 for (i = 0; i < get_irp_n_irgs(); i++) {
556 irg_vrfy (get_irp_irg(i));
559 # endif /* defined DEBUG_libfirm */
562 /* Delete all graphs that we have found to be dead from the program */
563 void rta_delete_dead_graphs ()
566 int n_graphs = get_irp_n_irgs ();
567 ir_graph *graph = NULL;
569 eset *dead_graphs = eset_create ();
571 for (i = 0; i < n_graphs; i++) {
572 graph = get_irp_irg(i);
574 if (is_alive (graph, _live_graphs, _dead_graphs)) {
575 /* do nothing (except some debugging fprintf`s :-) */
577 # ifdef DEBUG_libfirm
578 entity *ent = get_irg_entity (graph);
579 assert (whole_world ||
580 (visibility_external_visible != get_entity_visibility (ent)));
581 # endif /* defined DEBUG_libfirm */
583 eset_insert (dead_graphs, graph);
587 /* now delete the graphs. */
588 for (graph = eset_first (dead_graphs);
590 graph = (ir_graph*) eset_next (dead_graphs)) {
595 /* Clean up the RTA data structures. Call this after calling rta_init */
598 # ifdef DEBUG_libfirm
600 for (i = 0; i < get_irp_n_irgs(); i++) {
601 irg_vrfy (get_irp_irg(i));
604 # endif /* defined DEBUG_libfirm */
607 eset_destroy (_live_classes);
608 _live_classes = NULL;
612 eset_destroy (_live_fields);
616 if (_called_methods) {
617 eset_destroy (_called_methods);
618 _called_methods = NULL;
622 eset_destroy (_live_graphs);
627 eset_destroy (_dead_graphs);
632 /* Say whether this class might be instantiated at any point in the program: */
633 int rta_is_alive_class (type *clazz)
635 return (eset_contains (_live_classes, clazz));
638 /* Say whether this graph might be run at any time in the program: */
639 int rta_is_alive_graph (ir_graph *graph)
641 int has_call = FALSE;
642 int has_class = FALSE;
644 if (eset_contains (_live_graphs, graph)) {
648 if (eset_contains (_dead_graphs, graph)) {
652 entity *meth = get_irg_ent (graph);
654 has_call = has_live_call (meth, graph);
655 has_class = has_live_class (meth, graph);
657 fprintf (stdout, "RTA: checking "); DDMEO (meth);
660 fprintf (stdout, "RTA: has_call "); DDMEO (meth);
664 fprintf (stdout, "RTA: has_class "); DDMEO (meth);
667 if (has_call && has_class) {
668 fprintf (stdout, "RTA: is_called "); DDMEO (meth);
670 fprintf (stdout, "RTA: UNCALLED "); DDMEO (meth);
673 if (has_call && has_class) {
674 eset_insert (_live_graphs, graph);
678 eset_insert (_dead_graphs, graph);
684 /* Say whether there have been any accesses to this field: */
685 int rta_is_alive_field (entity *field)
687 return (eset_contains (_live_fields, field));
690 /* dump our opinion */
691 void rta_report (FILE *stream)
695 for (i = 0; i < get_irp_n_types(); ++i) {
696 type *tp = get_irp_type(i);
697 if (is_class_type(tp) && rta_is_alive_class(tp)) {
698 fprintf(stream, "RTA: considered allocated: "); DDMT(tp);
702 for (i = 0; i < get_irp_n_irgs(); i++) {
703 if (rta_is_alive_graph (get_irp_irg(i))) {
704 fprintf(stream, "RTA: considered called: graph of");
705 DDMEO(get_irg_ent (get_irp_irg(i)));
713 * Revision 1.12 2004/06/17 16:33:33 liekweg
716 * Revision 1.11 2004/06/17 14:21:13 liekweg
719 * Revision 1.10 2004/06/17 10:31:41 goetz
720 * irscc: bugfix, can now deal with loops not reachable from start
721 * cgana: bugfix, skip_Tuple
724 * Revision 1.9 2004/06/17 08:56:03 liekweg
725 * Fixed typos in comments
727 * Revision 1.8 2004/06/17 08:33:01 liekweg
728 * Added comments; added remove_irg
730 * Revision 1.6 2004/06/14 13:02:03 goetz
733 * Revision 1.5 2004/06/13 15:03:45 liekweg
734 * RTA auf Iterative RTA aufgebohrt --flo
736 * Revision 1.4 2004/06/12 19:35:04 liekweg
737 * Kommentare eingef"ugt --flo
739 * Revision 1.3 2004/06/12 17:09:46 liekweg
740 * RTA works, outedges breaks. "Yay." --flo
742 * Revision 1.2 2004/06/11 18:25:39 liekweg
745 * Revision 1.1 2004/06/11 18:24:18 liekweg