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 nn * 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;
51 Initialise the static data structures.
53 static void init_tables (void)
55 _live_classes = eset_create ();
56 _live_fields = eset_create ();
57 _called_methods = eset_create ();
59 _live_graphs = eset_create ();
60 _dead_graphs = eset_create ();
62 if (get_irp_main_irg ()) {
63 eset_insert (_live_graphs, get_irp_main_irg ());
66 if (get_glob_type ()) {
67 eset_insert (_live_classes, get_glob_type ());
72 Enter all method and field accesses and all class allocations into
75 static void rta_act (ir_node *node, void *env)
77 opcode op = get_irn_opcode (node);
79 if (iro_Call == op) { /* CALL */
82 ir_node *ptr = get_Call_ptr (node);
84 if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
85 ent = get_Sel_entity (ptr);
86 } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
87 ent = get_tarval_entity (get_Const_tarval (ptr));
89 } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
90 /* If this SymConst refers to a method the method is external_visible
91 and therefore must be considered executed anyways. */
92 //dump_ir_block_graph(get_irn_irg(ptr));
93 //assert (ent && "couldn't determine entity of call to symConst");
97 eset_insert (_called_methods, ent);
99 } else if (iro_Load == op) { /* LOAD */
100 ir_node *ptr = get_Load_ptr (node);
103 if (iro_Sel == get_irn_opcode (ptr)) {
104 ent = get_Sel_entity (ptr);
107 eset_insert (_live_fields, ent);
109 } else if (iro_Store == op) { /* STORE */
110 ir_node *ptr = get_Store_ptr (node);
113 if (iro_Sel == get_irn_opcode (ptr)) {
114 ent = get_Sel_entity (ptr);
117 eset_insert (_live_fields, ent);
119 } else if (iro_Alloc == op) { /* ALLOC */
120 type *type = get_Alloc_type (node);
122 eset_insert (_live_classes, type);
127 Traverse the given graph to collect method and field accesses and
130 static void rta_fill_graph (ir_graph* graph)
133 if (NULL != get_irg_end (graph)) {
134 current_ir_graph = graph;
136 irg_walk (get_irg_end (graph), rta_act, NULL, NULL);
142 Check whether the given graph is alive based on the contents of the
145 static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
147 if (eset_contains (live_graphs, graph)) {
151 if (eset_contains (dead_graphs, graph)) {
155 assert (0 && "graph neither live not dead (shouldn't happen)");
159 Traverse all graphs to collect method and field accesses and object allocations.
161 @param rerun Whether to rely on is_alive in a second run
163 static void rta_fill_all (int rerun)
166 int old_ip_view = interprocedural_view;
167 eset *live_graphs = NULL;
168 eset *dead_graphs = NULL;
170 interprocedural_view = 0; /* save this for later */
173 int n_graphs = get_irp_n_irgs ();
175 /* force all graphs to be entered in either live_graphs or dead_graphs */
176 for (i = 0; i < n_graphs; i ++) {
177 rta_is_alive_graph (get_irp_irg (i));
180 /* remember existing infos for later */
181 live_graphs = _live_graphs;
182 dead_graphs = _dead_graphs;
184 /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
192 /* Consider all graphs, possibly taking into account existing infos */
193 for (i = 0; i < get_irp_n_irgs(); i++) {
194 ir_graph *graph = get_irp_irg (i);
196 /* Need to take care of graphs that are externally
197 visible. Pretend that they are called: */
198 entity *ent = get_irg_entity (graph);
199 if (visibility_local != get_entity_visibility (ent)) {
200 eset_insert (_called_methods, ent);
202 if (get_entity_irg (ent)) {
203 eset_insert (_live_graphs, get_entity_irg (ent));
206 eset_insert (_live_classes, get_entity_owner (ent));
209 /* now check the graph */
211 if (is_alive (graph, live_graphs, dead_graphs)) {
212 rta_fill_graph (graph);
214 /* nothing (except debugging printf's :-) */
217 rta_fill_graph (graph);
222 /* clean up the tables that we have retained */
223 eset_destroy (live_graphs);
224 eset_destroy (dead_graphs);
227 interprocedural_view = old_ip_view; /* cover up our traces */
231 Find out whether the given method could be the target of a
234 static int is_call_target (const entity *method)
236 int is_target = FALSE;
240 /* The method could be the target of a polymorphic call if it is
241 called or if it overrides a method that is called. */
243 if (eset_contains (_called_methods, (entity*) method)) {
247 /* not called? check methods in superclass(es) */
248 n_over = get_entity_n_overwrittenby ((entity*) method);
249 for (i = 0; !is_target && (i < n_over); i ++) {
250 entity *over = get_entity_overwrittenby ((entity*) method, i);
251 is_target |= is_call_target (over);
258 Given a method, find the firm graph that implements that method.
260 static ir_graph *get_implementing_graph (const entity *method)
262 ir_graph *graph = get_entity_irg ((entity*) method);
266 int n_over = get_entity_n_overwrites ((entity*) method);
268 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
269 entity *over = get_entity_overwrites ((entity*) method, i);
270 graph = get_implementing_graph (over);
274 /* we *must* always return a graph != NULL, *except* when we're used
275 inside remove_irg or force_description */
276 /* assert (graph && "no graph"); */
282 Determine whether the give method or one of its overwriter have
283 been used in a call to the given graph.
285 static int has_live_call (entity *method, ir_graph *graph)
287 int has_call = FALSE;
290 /* stop searching if a overwriting method comes with a new graph */
291 /* if (get_irg_ent (graph) != method) *
292 { /* shouldn't we compare GRAPHS here????? *
297 if (graph != get_entity_irg (method)) {
301 /* maybe we're called (possibly through polymorphy)? */
302 if (is_call_target (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_call && (i < n_over); i ++) {
309 entity *over = get_entity_overwrittenby((entity*) method, i);
310 has_call |= has_live_call (over, graph);
317 Determine whether the given class is live *and* uses the given
318 graph at some point, or has live subclasses that use the graph.
320 static int has_graph (type *clazz, ir_graph *graph)
322 int has_the_graph = FALSE;
326 if (eset_contains (_live_classes, clazz)) {
327 int n_meth = get_class_n_members (clazz);
329 for (i = 0; i < n_meth; i ++) {
330 entity *member = get_class_member (clazz, i);
331 if (is_method_type (get_entity_type (member))) {
332 ir_graph *impl = get_entity_irg (member);
339 } /* _live_classes.contains (clazz) */
341 /* our subclasses might be using that graph, no? */
342 n_sub = get_class_n_subtypes (clazz);
343 for (i = 0; !has_the_graph && (i < n_sub); i ++) {
344 type *sub = get_class_subtype (clazz, i);
346 has_the_graph |= has_graph (sub, graph);
349 return (has_the_graph);
353 Determine whether the given method could be used in a call to the
354 given graph on a live class.
356 static int has_live_class (entity *method, ir_graph *graph)
358 int has_class = FALSE;
363 /* stop searching when an overwriting method provides a new graph */
364 if (get_implementing_graph (method) != graph) {
368 clazz = get_entity_owner (method);
370 if (has_graph (clazz, graph)) { /* this also checks whether clazz is live*/
374 n_over = get_entity_n_overwrittenby (method);
375 for (i = 0; !has_class && (i < n_over); i ++) {
376 entity *over = get_entity_overwrittenby (method, i);
377 has_class |= has_live_class (over, graph);
384 Count the number of graphs that we have found to be live. Since
385 this touches every graph of the irp, it also forces that each graph
386 is either in _live_graphs xor in _dead_graphs. This is useful if
387 we use is_alive(ir_graph*) internally.
389 static int stats (void)
392 int n_live_graphs = 0;
393 int n_graphs = get_irp_n_irgs();
395 for (i = 0; i < n_graphs; i++) {
396 ir_graph *graph = get_irp_irg(i);
398 if (rta_is_alive_graph (graph)) {
403 return (n_live_graphs);
406 /* remove a graph, part I */
408 We removed the first graph to implement the entity, so we're
409 abstract now. Pretend that it wasn't there at all, and every
410 entity that used to inherit this entity's graph is now abstract.
412 /* Since we *know* that this entity will not be called, this is OK. */
413 static void force_description (entity *ent, entity *addr)
415 int i, n_over = get_entity_n_overwrittenby (ent);
417 set_entity_peculiarity (ent, peculiarity_description);
419 for (i = 0; i < n_over; i ++) {
420 entity *over = get_entity_overwrittenby (ent, i);
422 if (peculiarity_inherited == get_entity_peculiarity (over)) {
423 /* We rely on the fact that cse is performed on the const_code_irg. */
425 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
427 if (addr == my_addr) {
428 force_description (over, addr);
430 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
431 /* check whether 'over' forces 'inheritance' of *our* graph: */
432 ir_node *f_addr = get_atomic_ent_value (over);
433 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
435 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
436 if (impl_ent == addr) {
437 assert (0 && "gibt's denn sowas");
438 force_description (over, addr);
444 /* remove a graph, part II */
446 Note: get_implementing_graph is not well defined here (graph->ent
447 could overwrite more than one superclass implementation (graph).
448 Since we *know* that this entity will not be called, this is OK.
450 static void remove_irg (ir_graph *graph)
452 entity *ent = get_irg_entity (graph);
454 //DDMEO(get_irg_ent(graph));
456 /* delete the ir_graph data */
457 remove_irp_irg (graph);
458 /* remove reference to the graph */
459 set_entity_irg (ent, NULL);
460 /* find the implementation (graph) from *some* superclass: */
461 graph = get_implementing_graph (ent);
463 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
464 /* nothing to inherit! pretend we're abstract */
465 force_description (ent, ent);
467 /* pretend that we inherit the implementation (graph) from some superclass: */
468 set_entity_peculiarity (ent, peculiarity_inherited);
470 exchange (get_atomic_ent_value (ent),
471 get_atomic_ent_value (get_irg_ent(graph)));
475 /* Initialise the RTA data structures, and perform RTA.
476 @param verbose Iff != 0, print statistics as we go along
478 void rta_init (int verbose)
480 int n_live_graphs = get_irp_n_irgs ();
484 # ifdef DEBUG_libfirm
486 for (i = 0; i < get_irp_n_irgs(); i++) {
487 irg_vrfy (get_irp_irg(i));
490 # endif /* defined DEBUG_libfirm */
495 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
498 rta_fill_all (FALSE);
500 while (n_graphs != n_live_graphs) {
501 n_graphs = n_live_graphs;
504 n_live_graphs = stats ();
507 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
512 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
513 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
514 printf ("RTA: n_runs = %i\n", n_runs);
517 # 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 */
525 /* Delete all graphs that we have found to be dead from the program */
526 void rta_delete_dead_graphs ()
529 int n_graphs = get_irp_n_irgs ();
530 ir_graph *graph = NULL;
532 eset *dead_graphs = eset_create ();
534 for (i = 0; i < n_graphs; i++) {
535 graph = get_irp_irg(i);
537 if (is_alive (graph, _live_graphs, _dead_graphs)) {
538 /* do nothing (except some debugging fprintf`s :-) */
540 # ifdef DEBUG_libfirm
541 entity *ent = get_irg_entity (graph);
542 assert (visibility_external_visible != get_entity_visibility (ent));
543 # endif /* defined DEBUG_libfirm */
545 eset_insert (dead_graphs, graph);
549 for (i = 0; i < get_irp_n_types(); ++i) {
550 type *tp = get_irp_type(i);
551 if (is_class_type(tp) && !rta_is_alive_class(tp)) {
552 printf(" never allocated: "); DDMT(tp);
556 /* now delete the graphs. */
557 for (graph = eset_first (dead_graphs);
559 graph = (ir_graph*) eset_next (dead_graphs)) {
564 /* Clean up the RTA data structures. Call this after calling rta_init */
567 # ifdef DEBUG_libfirm
569 for (i = 0; i < get_irp_n_irgs(); i++) {
570 irg_vrfy (get_irp_irg(i));
573 # endif /* defined DEBUG_libfirm */
576 eset_destroy (_live_classes);
577 _live_classes = NULL;
581 eset_destroy (_live_fields);
585 if (_called_methods) {
586 eset_destroy (_called_methods);
587 _called_methods = NULL;
591 eset_destroy (_live_graphs);
596 eset_destroy (_dead_graphs);
601 /* Say whether this class might be instantiated at any point in the program: */
602 int rta_is_alive_class (type *clazz)
604 return (eset_contains (_live_classes, clazz));
607 /* Say whether this graph might be run at any time in the program: */
608 int rta_is_alive_graph (ir_graph *graph)
610 if (eset_contains (_live_graphs, graph)) {
614 if (eset_contains (_dead_graphs, graph)) {
618 entity *meth = get_irg_ent (graph);
620 if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
621 eset_insert (_live_graphs, graph);
625 eset_insert (_dead_graphs, graph);
631 /* Say whether there have been any accesses to this field: */
632 int rta_is_alive_field (entity *field)
634 return (eset_contains (_live_fields, field));
641 * Revision 1.10 2004/06/17 10:31:41 goetz
642 * irscc: bugfix, can now deal with loops not reachable from start
643 * cgana: bugfix, skip_Tuple
646 * Revision 1.9 2004/06/17 08:56:03 liekweg
647 * Fixed typos in comments
649 * Revision 1.8 2004/06/17 08:33:01 liekweg
650 * Added comments; added remove_irg
652 * Revision 1.6 2004/06/14 13:02:03 goetz
655 * Revision 1.5 2004/06/13 15:03:45 liekweg
656 * RTA auf Iterative RTA aufgebohrt --flo
658 * Revision 1.4 2004/06/12 19:35:04 liekweg
659 * Kommentare eingef"ugt --flo
661 * Revision 1.3 2004/06/12 17:09:46 liekweg
662 * RTA works, outedges breaks. "Yay." --flo
664 * Revision 1.2 2004/06/11 18:25:39 liekweg
667 * Revision 1.1 2004/06/11 18:24:18 liekweg