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 Find out whether the given method could be the target of a
237 static int is_call_target (entity *method)
239 int is_target = FALSE;
243 /* The method could be the target of a polymorphic call if it is
244 called or if it overrides a method that is called. */
246 if (eset_contains (_called_methods, (entity*) method)) {
250 /* not called? check methods in superclass(es) */
251 n_over = get_entity_n_overwrites ((entity*) method);
252 for (i = 0; !is_target && (i < n_over); i ++) {
253 entity *over = get_entity_overwrites ((entity*) method, i);
254 is_target |= is_call_target (over);
261 Given a method, find the firm graph that implements that method.
263 static ir_graph *get_implementing_graph (entity *method)
265 ir_graph *graph = get_entity_irg ((entity*) method);
269 int n_over = get_entity_n_overwrites ((entity*) method);
271 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
272 entity *over = get_entity_overwrites ((entity*) method, i);
273 graph = get_implementing_graph (over);
277 /* we *must* always return a graph != NULL, *except* when we're used
278 inside remove_irg or force_description */
279 /* assert (graph && "no graph"); */
285 Determine wether the given method is called through polymorphy with
288 static int has_live_downcall (entity *method, ir_graph *graph)
290 int has_downcall = FALSE;
293 if (graph != get_entity_irg ((entity*) method)) {
297 if (eset_contains (_called_methods, method)) {
301 /* maybe we're overwritten by a method that is called? */
302 n_over = get_entity_n_overwrittenby ((entity*) method);
303 for (i = 0; !has_downcall && (i < n_over); i ++) {
304 entity *over = get_entity_overwrittenby ((entity*) method, i);
305 has_downcall |= has_live_downcall (over, graph);
308 return (has_downcall);
312 Determine whether the given method or one of its overwriters have
313 been used in a call to the given graph.
315 static int has_live_call (entity *method, ir_graph *graph)
317 /* maybe we're called (possibly through polymorphy)? */
318 if (is_call_target (method)) {
322 /* maybe our subclasses have seen a call? */
323 if (has_live_downcall (method, graph)) {
332 Determine whether the given method could be used in a call to the
333 given graph on a live class.
335 static int has_live_class (entity *method, ir_graph *graph)
337 int has_class = FALSE;
342 /* DON'T stop searching when an overwriting method provides a new graph */
344 clazz = get_entity_owner (method);
346 if (rta_is_alive_class (clazz)) {
350 n_over = get_entity_n_overwrites (method);
351 for (i = 0; !has_class && (i < n_over); i ++) {
352 entity *over = get_entity_overwrites (method, i);
353 has_class |= has_live_class (over, graph);
360 Count the number of graphs that we have found to be live. Since
361 this touches every graph of the irp, it also forces that each graph
362 is either in _live_graphs xor in _dead_graphs. This is useful if
363 we use is_alive(ir_graph*) internally.
365 static int stats (void)
368 int n_live_graphs = 0;
369 int n_graphs = get_irp_n_irgs();
371 for (i = 0; i < n_graphs; i++) {
372 ir_graph *graph = get_irp_irg(i);
374 if (rta_is_alive_graph (graph)) {
379 return (n_live_graphs);
382 /* remove a graph, part I */
384 We removed the first graph to implement the entity, so we're
385 abstract now. Pretend that it wasn't there at all, and every
386 entity that used to inherit this entity's graph is now abstract.
388 /* Since we *know* that this entity will not be called, this is OK. */
389 static void force_description (entity *ent, entity *addr)
391 int i, n_over = get_entity_n_overwrittenby (ent);
393 set_entity_peculiarity (ent, peculiarity_description);
395 for (i = 0; i < n_over; i ++) {
396 entity *over = get_entity_overwrittenby (ent, i);
398 if (peculiarity_inherited == get_entity_peculiarity (over)) {
399 /* We rely on the fact that cse is performed on the const_code_irg. */
401 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
403 if (addr == my_addr) {
404 force_description (over, addr);
406 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
407 /* check whether 'over' forces 'inheritance' of *our* graph: */
408 ir_node *f_addr = get_atomic_ent_value (over);
409 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
411 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
412 if (impl_ent == addr) {
413 assert (0 && "gibt's denn sowas");
414 force_description (over, addr);
420 /* remove a graph, part II */
422 Note: get_implementing_graph is not well defined here (graph->ent
423 could overwrite more than one superclass implementation (graph).
424 Since we *know* that this entity will not be called, this is OK.
426 static void remove_irg (ir_graph *graph)
428 entity *ent = get_irg_entity (graph);
430 /* DDMEO (get_irg_ent(graph)); */
432 /* delete the ir_graph data */
433 remove_irp_irg (graph);
434 /* remove reference to the graph */
435 set_entity_irg (ent, NULL);
436 /* find the implementation (graph) from *some* superclass: */
437 graph = get_implementing_graph (ent);
439 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
440 /* nothing to inherit! pretend we're abstract */
441 force_description (ent, ent);
443 /* pretend that we inherit the implementation (graph) from some superclass: */
444 set_entity_peculiarity (ent, peculiarity_inherited);
446 exchange (get_atomic_ent_value (ent),
447 get_atomic_ent_value (get_irg_ent(graph)));
451 /* Initialise the RTA data structures, and perform RTA.
452 @param verbose Iff != 0, print statistics as we go along
454 void rta_init (int verbose, int whole_world)
456 int n_live_graphs = get_irp_n_irgs ();
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 */
470 if (verbose && whole_world) {
471 printf ("RTA: whole-world assumption\n");
475 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
478 rta_fill_all (FALSE);
480 while (n_graphs != n_live_graphs) {
481 n_graphs = n_live_graphs;
484 n_live_graphs = stats ();
487 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
492 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
493 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
494 printf ("RTA: n_runs = %i\n", n_runs);
497 # ifdef DEBUG_libfirm
498 for (i = 0; i < get_irp_n_irgs(); i++) {
499 irg_vrfy (get_irp_irg(i));
502 # endif /* defined DEBUG_libfirm */
505 /* Delete all graphs that we have found to be dead from the program */
506 void rta_delete_dead_graphs ()
509 int n_graphs = get_irp_n_irgs ();
510 ir_graph *graph = NULL;
512 eset *dead_graphs = eset_create ();
514 for (i = 0; i < n_graphs; i++) {
515 graph = get_irp_irg(i);
517 if (is_alive (graph, _live_graphs, _dead_graphs)) {
518 /* do nothing (except some debugging fprintf`s :-) */
520 # ifdef DEBUG_libfirm
521 entity *ent = get_irg_entity (graph);
522 assert (whole_world ||
523 (visibility_external_visible != get_entity_visibility (ent)));
524 # endif /* defined DEBUG_libfirm */
526 eset_insert (dead_graphs, graph);
530 /* now delete the graphs. */
531 for (graph = eset_first (dead_graphs);
533 graph = (ir_graph*) eset_next (dead_graphs)) {
538 /* Clean up the RTA data structures. Call this after calling rta_init */
541 # ifdef DEBUG_libfirm
543 for (i = 0; i < get_irp_n_irgs(); i++) {
544 irg_vrfy (get_irp_irg(i));
547 # endif /* defined DEBUG_libfirm */
550 eset_destroy (_live_classes);
551 _live_classes = NULL;
555 eset_destroy (_live_fields);
559 if (_called_methods) {
560 eset_destroy (_called_methods);
561 _called_methods = NULL;
565 eset_destroy (_live_graphs);
570 eset_destroy (_dead_graphs);
575 /* Say whether this class might be instantiated at any point in the program: */
576 int rta_is_alive_class (type *clazz)
578 return (eset_contains (_live_classes, clazz));
581 /* Say whether this graph might be run at any time in the program: */
582 int rta_is_alive_graph (ir_graph *graph)
584 int has_call = FALSE;
585 int has_class = FALSE;
587 if (eset_contains (_live_graphs, graph)) {
591 if (eset_contains (_dead_graphs, graph)) {
595 entity *meth = get_irg_ent (graph);
597 has_call = has_live_call (meth, graph);
598 has_class = has_live_class (meth, graph);
600 if (has_call && has_class) {
601 eset_insert (_live_graphs, graph);
605 eset_insert (_dead_graphs, graph);
611 /* Say whether there have been any accesses to this field: */
612 int rta_is_alive_field (entity *field)
614 return (eset_contains (_live_fields, field));
617 /* dump our opinion */
618 void rta_report (FILE *stream)
622 for (i = 0; i < get_irp_n_types(); ++i) {
623 type *tp = get_irp_type(i);
624 if (is_class_type(tp) && rta_is_alive_class(tp)) {
625 fprintf(stream, "RTA: considered allocated: "); DDMT(tp);
629 for (i = 0; i < get_irp_n_irgs(); i++) {
630 if (rta_is_alive_graph (get_irp_irg(i))) {
631 fprintf(stream, "RTA: considered called: graph of");
632 DDMEO(get_irg_ent (get_irp_irg(i)));
640 * Revision 1.11 2004/06/17 14:21:13 liekweg
643 * Revision 1.10 2004/06/17 10:31:41 goetz
644 * irscc: bugfix, can now deal with loops not reachable from start
645 * cgana: bugfix, skip_Tuple
648 * Revision 1.9 2004/06/17 08:56:03 liekweg
649 * Fixed typos in comments
651 * Revision 1.8 2004/06/17 08:33:01 liekweg
652 * Added comments; added remove_irg
654 * Revision 1.6 2004/06/14 13:02:03 goetz
657 * Revision 1.5 2004/06/13 15:03:45 liekweg
658 * RTA auf Iterative RTA aufgebohrt --flo
660 * Revision 1.4 2004/06/12 19:35:04 liekweg
661 * Kommentare eingef"ugt --flo
663 * Revision 1.3 2004/06/12 17:09:46 liekweg
664 * RTA works, outedges breaks. "Yay." --flo
666 * Revision 1.2 2004/06/11 18:25:39 liekweg
669 * Revision 1.1 2004/06/11 18:24:18 liekweg