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;
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 assert (ent && "couldn't determine entity of call to symConst");
94 eset_insert (_called_methods, ent);
96 } else if (iro_Load == op) { /* LOAD */
97 ir_node *ptr = get_Load_ptr (node);
100 if (iro_Sel == get_irn_opcode (ptr)) {
101 ent = get_Sel_entity (ptr);
104 eset_insert (_live_fields, ent);
106 } else if (iro_Store == op) { /* STORE */
107 ir_node *ptr = get_Store_ptr (node);
110 if (iro_Sel == get_irn_opcode (ptr)) {
111 ent = get_Sel_entity (ptr);
114 eset_insert (_live_fields, ent);
116 } else if (iro_Alloc == op) { /* ALLOC */
117 type *type = get_Alloc_type (node);
119 eset_insert (_live_classes, type);
124 Traverse the given graph to collect method and field accesses and
127 static void rta_fill_graph (ir_graph* graph)
130 if (NULL != get_irg_end (graph)) {
131 current_ir_graph = graph;
133 irg_walk (get_irg_end (graph), rta_act, NULL, NULL);
139 Check whether the given graph is alive based on the contents of the
142 static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
144 if (eset_contains (live_graphs, graph)) {
148 if (eset_contains (dead_graphs, graph)) {
152 assert (0 && "graph neither live not dead (shouldn't happen)");
156 Traverse all graphs to collect method and field accesses and object allocations.
158 @param rerun Whether to rely on is_alive in a second run
160 static void rta_fill_all (int rerun)
163 int old_ip_view = interprocedural_view;
164 eset *live_graphs = NULL;
165 eset *dead_graphs = NULL;
167 interprocedural_view = 0; /* save this for later */
170 int n_graphs = get_irp_n_irgs ();
172 /* force all graphs to be entered in either live_graphs or dead_graphs */
173 for (i = 0; i < n_graphs; i ++) {
174 rta_is_alive_graph (get_irp_irg (i));
177 /* remember existing infos for later */
178 live_graphs = _live_graphs;
179 dead_graphs = _dead_graphs;
181 /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
189 /* Consider all graphs, possibly taking into account existing infos */
190 for (i = 0; i < get_irp_n_irgs(); i++) {
191 ir_graph *graph = get_irp_irg (i);
193 /* Need to take care of graphs that are externally
194 visible. Pretend that they are called: */
195 entity *ent = get_irg_entity (graph);
196 if (visibility_local != get_entity_visibility (ent)) {
197 eset_insert (_called_methods, ent);
199 if (get_entity_irg (ent)) {
200 eset_insert (_live_graphs, get_entity_irg (ent));
203 eset_insert (_live_classes, get_entity_owner (ent));
206 /* now check the graph */
208 if (is_alive (graph, live_graphs, dead_graphs)) {
209 rta_fill_graph (graph);
211 /* nothing (except debugging printf's :-) */
214 rta_fill_graph (graph);
219 /* clean up the tables that we have retained */
220 eset_destroy (live_graphs);
221 eset_destroy (dead_graphs);
224 interprocedural_view = old_ip_view; /* cover up our traces */
228 Find out whether the given method could be the target of a
231 static int is_call_target (const entity *method)
233 int is_target = FALSE;
237 /* The method could be the target of a polymorphic call if it is
238 called or if it overrides a method that is called. */
240 if (eset_contains (_called_methods, (entity*) method)) {
244 /* not called? check methods in superclass(es) */
245 n_over = get_entity_n_overwrittenby ((entity*) method);
246 for (i = 0; !is_target && (i < n_over); i ++) {
247 entity *over = get_entity_overwrittenby ((entity*) method, i);
248 is_target |= is_call_target (over);
255 Given a method, find the firm graph that implements that method.
257 static ir_graph *get_implementing_graph (const entity *method)
259 ir_graph *graph = get_entity_irg ((entity*) method);
263 int n_over = get_entity_n_overwrites ((entity*) method);
265 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
266 entity *over = get_entity_overwrites ((entity*) method, i);
267 graph = get_implementing_graph (over);
271 /* we *must* always return a graph != NULL, *except* when we're used
272 inside remove_irg or force_description */
273 /* assert (graph && "no graph"); */
279 Determine whether the give method or one of its overwriter have
280 been used in a call to the given graph.
282 static int has_live_call (entity *method, ir_graph *graph)
284 int has_call = FALSE;
287 /* stop searching if a overwriting method comes with a new graph */
288 if (get_irg_ent (graph) != method) { /* shouldn't we comare GRAPS????? */
292 /* maybe we're called (possibly through polymorphy)? */
293 if (is_call_target (method)) {
297 /* maybe we're overwritten by a method that is called? */
298 n_over = get_entity_n_overwrittenby ((entity*) method);
299 for (i = 0; !has_call && (i < n_over); i ++) {
300 entity *over = get_entity_overwrittenby((entity*) method, i);
301 has_call |= has_live_call (over, graph);
308 Determine whether the given class is live *and* uses the given
311 static int has_graph (type *clazz, ir_graph *graph)
313 int has_the_graph = FALSE;
317 if (eset_contains (_live_classes, clazz)) {
318 int n_meth = get_class_n_members (clazz);
320 for (i = 0; i < n_meth; i ++) {
321 entity *member = get_class_member (clazz, i);
322 if (is_method_type (get_entity_type (member))) {
323 ir_graph *impl = get_entity_irg (member);
330 } /* _live_classes.contains (clazz) */
332 /* our subclasses might be using that graph, no? */
333 n_sub = get_class_n_subtypes (clazz);
334 for (i = 0; !has_the_graph && (i < n_sub); i ++) {
335 type *sub = get_class_subtype (clazz, i);
337 has_the_graph |= has_graph (sub, graph);
340 return (has_the_graph);
344 Determine wether the given method could be used in a call to the
345 given graph on a live class.
347 static int has_live_class (entity *method, ir_graph *graph)
349 int has_class = FALSE;
354 /* stop searching when an overwriting method provides a new graph */
355 if (get_implementing_graph (method) != graph) {
359 clazz = get_entity_owner (method);
361 if (has_graph (clazz, graph)) { /* this also checks whether clazz is live*/
365 n_over = get_entity_n_overwrittenby (method);
366 for (i = 0; !has_class && (i < n_over); i ++) {
367 entity *over = get_entity_overwrittenby (method, i);
368 has_class |= has_live_class (over, graph);
375 Count the number of graphs that we have found to be live. Since
376 this touches every graph of the irp, it also forces that each graph
377 is either in _live_graphs xor in _dead_graphs. This is useful if
378 we use is_alive(ir_graph*) internally.
380 static int stats (void)
383 int n_live_graphs = 0;
384 int n_graphs = get_irp_n_irgs();
386 for (i = 0; i < n_graphs; i++) {
387 ir_graph *graph = get_irp_irg(i);
389 if (rta_is_alive_graph (graph)) {
394 return (n_live_graphs);
397 /* remove a graph, part I */
399 We removed the first graph to implement the entity, so we're
400 abstract now. Pretend that it wasn't there at all, and every
401 entity that used to inherit this entity's graph is now abstract.
403 /* Since we *know* that this entity will not be called, this is OK. */
404 static void force_description (entity *ent, entity *addr)
406 int i, n_over = get_entity_n_overwrittenby (ent);
408 set_entity_peculiarity (ent, peculiarity_description);
410 for (i = 0; i < n_over; i ++) {
411 entity *over = get_entity_overwrittenby (ent, i);
413 if (peculiarity_inherited == get_entity_peculiarity (over)) {
414 /* We rely on the fact that cse is performed on the const_code_irg. */
416 tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
418 if (addr == my_addr) {
419 force_description (over, addr);
421 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
422 /* check wether 'over' forces 'inheritance' of *our* graph: */
423 ir_node *f_addr = get_atomic_ent_value (over);
424 entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
426 assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
427 if (impl_ent == addr) {
428 assert (0 && "gibt's denn sowas");
429 force_description (over, addr);
435 /* remove a graph, part II */
437 Note: get_implementing_graph is not well defined here (graph->ent
438 could overwrite more than one superclass implementation (graph).
439 Since we *know* that this entity will not be called, this is OK.
441 static void remove_irg (ir_graph *graph)
443 entity *ent = get_irg_entity (graph);
445 /* delete the ir_graph data */
446 remove_irp_irg (graph);
447 /* remove reference to the graph */
448 set_entity_irg (ent, NULL);
449 /* find the implementation (graph) from *some* superclass: */
450 graph = get_implementing_graph (ent);
452 if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
453 /* nothing to inherit! pretend we're abstract */
454 force_description (ent, ent);
456 /* pretend that we inherit the implementation (graph) from some superclass: */
457 set_entity_peculiarity (ent, peculiarity_inherited);
459 exchange (get_atomic_ent_value (ent),
460 get_atomic_ent_value (get_irg_ent(graph)));
464 /* Initialise the RTA data structures, and perform RTA.
465 @param verbose Iff != 0, print statistics as we go along
467 void rta_init (int verbose)
469 int n_live_graphs = get_irp_n_irgs ();
473 # ifdef DEBUG_libfirm
475 for (i = 0; i < get_irp_n_irgs(); i++) {
476 irg_vrfy (get_irp_irg(i));
479 # endif /* defined DEBUG_libfirm */
484 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
487 rta_fill_all (FALSE);
489 while (n_graphs != n_live_graphs) {
490 n_graphs = n_live_graphs;
493 n_live_graphs = stats ();
496 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
501 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
502 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
503 printf ("RTA: n_runs = %i\n", n_runs);
506 # ifdef DEBUG_libfirm
507 for (i = 0; i < get_irp_n_irgs(); i++) {
508 irg_vrfy (get_irp_irg(i));
511 # endif /* defined DEBUG_libfirm */
514 /* Delete all graphs that we have found to be dead from the program */
515 void rta_delete_dead_graphs ()
518 int n_graphs = get_irp_n_irgs ();
519 ir_graph *graph = NULL;
521 eset *dead_graphs = eset_create ();
523 for (i = 0; i < n_graphs; i++) {
524 graph = get_irp_irg(i);
526 if (is_alive (graph, _live_graphs, _dead_graphs)) {
527 /* do nothing (except some debugging fprintf`s :-) */
529 entity *ent = get_irg_entity (graph);
530 assert (visibility_external_visible != get_entity_visibility (ent));
532 eset_insert (dead_graphs, graph);
536 /* now delete the graphs. */
537 for (graph = eset_first (dead_graphs);
539 graph = (ir_graph*) eset_next (dead_graphs)) {
544 /* Clean up the RTA data structures. Call this after calling rta_init */
547 # ifdef DEBUG_libfirm
549 for (i = 0; i < get_irp_n_irgs(); i++) {
550 irg_vrfy (get_irp_irg(i));
553 # endif /* defined DEBUG_libfirm */
556 eset_destroy (_live_classes);
557 _live_classes = NULL;
561 eset_destroy (_live_fields);
565 if (_called_methods) {
566 eset_destroy (_called_methods);
567 _called_methods = NULL;
571 eset_destroy (_live_graphs);
576 eset_destroy (_dead_graphs);
581 /* Say wether this class might be instantiated at any point in the program: */
582 int rta_is_alive_class (type *clazz)
584 return (eset_contains (_live_classes, clazz));
587 /* Say wether this graph might be run at any time in the program: */
588 int rta_is_alive_graph (ir_graph *graph)
590 if (eset_contains (_live_graphs, graph)) {
594 if (eset_contains (_dead_graphs, graph)) {
598 entity *meth = get_irg_ent (graph);
600 if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
601 eset_insert (_live_graphs, graph);
605 eset_insert (_dead_graphs, graph);
611 /* Say wether there have been any accesses to this field: */
612 int rta_is_alive_field (entity *field)
614 return (eset_contains (_live_fields, field));
621 * Revision 1.8 2004/06/17 08:33:01 liekweg
622 * Added comments; added remove_irg
624 * Revision 1.6 2004/06/14 13:02:03 goetz
627 * Revision 1.5 2004/06/13 15:03:45 liekweg
628 * RTA auf Iterative RTA aufgebohrt --flo
630 * Revision 1.4 2004/06/12 19:35:04 liekweg
631 * Kommentare eingef"ugt --flo
633 * Revision 1.3 2004/06/12 17:09:46 liekweg
634 * RTA works, outedges breaks. "Yay." --flo
636 * Revision 1.2 2004/06/11 18:25:39 liekweg
639 * Revision 1.1 2004/06/11 18:24:18 liekweg