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)) {
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 verbose Iff != 0, print statistics as we go along
506 void rta_init (int verbose, int do_whole_world)
508 int n_live_graphs = get_irp_n_irgs ();
512 whole_world = do_whole_world;
514 # ifdef DEBUG_libfirm
516 for (i = 0; i < get_irp_n_irgs(); i++) {
517 irg_vrfy (get_irp_irg(i));
520 # endif /* defined DEBUG_libfirm */
524 if (verbose && whole_world) {
525 printf ("RTA: whole-world assumption\n");
529 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
532 rta_fill_all (FALSE);
534 while (n_graphs != n_live_graphs) {
535 n_graphs = n_live_graphs;
538 n_live_graphs = stats ();
541 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
546 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
547 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
548 printf ("RTA: n_runs = %i\n", n_runs);
551 # ifdef DEBUG_libfirm
552 for (i = 0; i < get_irp_n_irgs(); i++) {
553 irg_vrfy (get_irp_irg(i));
556 # endif /* defined DEBUG_libfirm */
559 /* Delete all graphs that we have found to be dead from the program */
560 void rta_delete_dead_graphs ()
563 int n_graphs = get_irp_n_irgs ();
564 ir_graph *graph = NULL;
566 eset *dead_graphs = eset_create ();
568 for (i = 0; i < n_graphs; i++) {
569 graph = get_irp_irg(i);
571 if (is_alive (graph, _live_graphs, _dead_graphs)) {
572 /* do nothing (except some debugging fprintf`s :-) */
574 # ifdef DEBUG_libfirm
575 entity *ent = get_irg_entity (graph);
576 assert (whole_world ||
577 (visibility_external_visible != get_entity_visibility (ent)));
578 # endif /* defined DEBUG_libfirm */
580 eset_insert (dead_graphs, graph);
584 /* now delete the graphs. */
585 for (graph = eset_first (dead_graphs);
587 graph = (ir_graph*) eset_next (dead_graphs)) {
592 /* Clean up the RTA data structures. Call this after calling rta_init */
595 # ifdef DEBUG_libfirm
597 for (i = 0; i < get_irp_n_irgs(); i++) {
598 irg_vrfy (get_irp_irg(i));
601 # endif /* defined DEBUG_libfirm */
604 eset_destroy (_live_classes);
605 _live_classes = NULL;
609 eset_destroy (_live_fields);
613 if (_called_methods) {
614 eset_destroy (_called_methods);
615 _called_methods = NULL;
619 eset_destroy (_live_graphs);
624 eset_destroy (_dead_graphs);
629 /* Say whether this class might be instantiated at any point in the program: */
630 int rta_is_alive_class (type *clazz)
632 return (eset_contains (_live_classes, clazz));
635 /* Say whether this graph might be run at any time in the program: */
636 int rta_is_alive_graph (ir_graph *graph)
638 int has_call = FALSE;
639 int has_class = FALSE;
641 if (eset_contains (_live_graphs, graph)) {
645 if (eset_contains (_dead_graphs, graph)) {
649 entity *meth = get_irg_ent (graph);
651 has_call = has_live_call (meth, graph);
652 has_class = has_live_class (meth, graph);
654 if (has_call && has_class) {
655 eset_insert (_live_graphs, graph);
659 eset_insert (_dead_graphs, graph);
665 /* Say whether there have been any accesses to this field: */
666 int rta_is_alive_field (entity *field)
668 return (eset_contains (_live_fields, field));
671 /* dump our opinion */
672 void rta_report (FILE *stream)
676 for (i = 0; i < get_irp_n_types(); ++i) {
677 type *tp = get_irp_type(i);
678 if (is_class_type(tp) && rta_is_alive_class(tp)) {
679 fprintf(stream, "RTA: considered allocated: "); DDMT(tp);
683 for (i = 0; i < get_irp_n_irgs(); i++) {
684 if (rta_is_alive_graph (get_irp_irg(i))) {
685 fprintf(stream, "RTA: considered called: graph of");
686 DDMEO(get_irg_ent (get_irp_irg(i)));
694 * Revision 1.13 2004/06/17 16:34:33 liekweg
697 * Revision 1.12 2004/06/17 16:33:33 liekweg
700 * Revision 1.11 2004/06/17 14:21:13 liekweg
703 * Revision 1.10 2004/06/17 10:31:41 goetz
704 * irscc: bugfix, can now deal with loops not reachable from start
705 * cgana: bugfix, skip_Tuple
708 * Revision 1.9 2004/06/17 08:56:03 liekweg
709 * Fixed typos in comments
711 * Revision 1.8 2004/06/17 08:33:01 liekweg
712 * Added comments; added remove_irg
714 * Revision 1.6 2004/06/14 13:02:03 goetz
717 * Revision 1.5 2004/06/13 15:03:45 liekweg
718 * RTA auf Iterative RTA aufgebohrt --flo
720 * Revision 1.4 2004/06/12 19:35:04 liekweg
721 * Kommentare eingef"ugt --flo
723 * Revision 1.3 2004/06/12 17:09:46 liekweg
724 * RTA works, outedges breaks. "Yay." --flo
726 * Revision 1.2 2004/06/11 18:25:39 liekweg
729 * Revision 1.1 2004/06/11 18:24:18 liekweg