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
28 #include "cgana.h" /* get_implementation */
34 /* #include "pmap.h" */
35 /* #include "array.h" */
37 /* #include "ircons.h" */
38 /* #include "irgmod.h" */
39 /* #include "irflag_t.h" */
41 /* #include "dbginfo_t.h" */
47 static eset *_live_classes = NULL;
48 static eset *_live_fields = NULL;
49 static eset *_called_methods = NULL;
51 /* cache computed results */
52 static eset *_live_graphs = NULL;
53 static eset *_dead_graphs = NULL;
57 static void init_tables (void)
59 _live_classes = eset_create ();
60 _live_fields = eset_create ();
61 _called_methods = eset_create ();
63 _live_graphs = eset_create ();
64 _dead_graphs = eset_create ();
66 if (get_irp_main_irg ()) {
67 eset_insert (_live_graphs, get_irp_main_irg ());
70 if (get_glob_type ()) {
71 eset_insert (_live_classes, get_glob_type ());
76 Enter all method and field accesses and all class allocations into our tables.
78 static void rta_act (ir_node *node, void *env)
80 opcode op = get_irn_opcode (node);
85 ir_node *ptr = get_Call_ptr (node);
87 if (iro_Sel == get_irn_opcode (ptr)) {
88 ent = get_Sel_entity (ptr);
89 } else if (iro_Const == get_irn_opcode (ptr)) {
90 ent = get_tarval_entity (get_Const_tarval (ptr));
96 eset_insert (_called_methods, ent);
98 } else if (iro_Load == op) {
99 ir_node *ptr = get_Load_ptr (node);
102 if (iro_Sel == get_irn_opcode (ptr)) {
103 ent = get_Sel_entity (ptr);
106 eset_insert (_live_fields, ent);
108 } else if (iro_Store == op) {
109 ir_node *ptr = get_Store_ptr (node);
112 if (iro_Sel == get_irn_opcode (ptr)) {
113 ent = get_Sel_entity (ptr);
116 eset_insert (_live_fields, ent);
118 } else if (iro_Alloc == op) {
119 type *type = get_Alloc_type (node);
121 eset_insert (_live_classes, type);
126 Traverse the given graph to collect method and field accesses and object allocations.
128 static void rta_fill_graph (ir_graph* graph)
131 if (NULL != get_irg_end (graph)) {
132 current_ir_graph = graph;
133 irg_walk (get_irg_end (graph), rta_act, NULL, NULL);
138 static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
140 if (eset_contains (live_graphs, graph)) {
144 if (eset_contains (dead_graphs, graph)) {
148 assert (0 && "what's up");
152 Traverse all graphs to collect method and field accesses and object allocations.
154 @param rerun Whether to rely on is_alive in a second run
156 static void rta_fill_all (int rerun)
159 int old_ip_view = interprocedural_view;
160 eset *live_graphs = NULL;
161 eset *dead_graphs = NULL;
163 interprocedural_view = 0;
167 int n_graphs = get_irp_n_irgs ();
169 /* force all graphs to be entered in either live_graphs or dead_graphs */
170 for (i = 0; i < n_graphs; i ++) {
171 rta_is_alive_graph (get_irp_irg (i));
174 /* remember existing infos for later */
175 live_graphs = _live_graphs;
176 dead_graphs = _dead_graphs;
178 /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
186 /* consider all graphs, possibly taking into account existing infos */
187 for (i = 0; i < get_irp_n_irgs(); i++) {
188 ir_graph *graph = get_irp_irg (i);
190 if (!rerun || is_alive (graph, live_graphs, dead_graphs)) {
191 rta_fill_graph (graph);
196 /* clean up the tables that we have retained */
197 eset_destroy (live_graphs);
198 eset_destroy (dead_graphs);
201 interprocedural_view = old_ip_view;
205 Find out whether the given method could be the target of a
208 static int is_call_target (const entity *method)
210 int is_target = FALSE;
214 /* The method could be the target of a polymorphic call if it is
215 called or if it overrides a method that is called. */
217 if (eset_contains (_called_methods, (entity*) method)) {
221 /* not called? check methods in superclass(es) */
222 n_over = get_entity_n_overwrittenby ((entity*) method);
223 for (i = 0; !is_target && (i < n_over); i ++) {
224 entity *over = get_entity_overwrittenby ((entity*) method, i);
225 is_target |= is_call_target (over);
232 Given a method, find the firm graph that implements that method.
234 static ir_graph *get_implementing_graph (const entity *method)
236 ir_graph *graph = get_entity_irg ((entity*) method);
240 int n_over = get_entity_n_overwrites ((entity*) method);
242 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
243 entity *over = get_entity_overwrites ((entity*) method, i);
244 graph = get_implementing_graph (over);
248 assert (graph && "no graph");
254 Determine whether the give method or one of its overwriter have
255 been used in a call to the given graph.
257 static int has_live_call (entity *method, ir_graph *graph)
259 int has_call = FALSE;
262 /* stop searching if a overwriting method comes with a new graph */
263 if (get_irg_ent (graph) != method) {
267 /* maybe we're called (possibly through polymorphy)? */
268 if (is_call_target (method)) {
272 /* maybe we're overwritten by a method that is called? */
273 n_over = get_entity_n_overwrittenby ((entity*) method);
274 for (i = 0; !has_call && (i < n_over); i ++) {
275 entity *over = get_entity_overwrittenby((entity*) method, i);
276 has_call |= has_live_call (over, graph);
283 Determine whether the given class is live *and* uses the given
286 static int has_graph (type *clazz, ir_graph *graph)
288 int has_the_graph = FALSE;
292 if (eset_contains (_live_classes, clazz)) {
293 int n_meth = get_class_n_members (clazz);
295 for (i = 0; i < n_meth; i ++) {
296 entity *member = get_class_member (clazz, i);
297 if (is_method_type (get_entity_type (member))) {
298 ir_graph *impl = get_entity_irg (member);
305 } /* _live_classes.contains (clazz) */
307 /* our subclasses might be using that graph, no? */
308 n_sub = get_class_n_subtypes (clazz);
309 for (i = 0; !has_the_graph && (i < n_sub); i ++) {
310 type *sub = get_class_subtype (clazz, i);
312 has_the_graph |= has_graph (sub, graph);
315 return (has_the_graph);
319 Determine wether the given method could be used in a call to the
320 given graph on a live class.
322 static int has_live_class (entity *method, ir_graph *graph)
324 int has_class = FALSE;
329 /* const char *name = get_entity_name (method); */
331 /* stop searching when an overwriting method provides a new graph */
332 if (get_implementing_graph (method) != graph) {
336 clazz = get_entity_owner (method);
338 if (has_graph (clazz, graph)) { /* this also checks whether clazz is live*/
342 n_over = get_entity_n_overwrittenby (method);
343 for (i = 0; !has_class && (i < n_over); i ++) {
344 entity *over = get_entity_overwrittenby (method, i);
345 has_class |= has_live_class (over, graph);
351 static int stats (void)
354 int n_live_graphs = 0;
355 int n_graphs = get_irp_n_irgs();
357 for (i = 0; i < n_graphs; i++) {
358 ir_graph *graph = get_irp_irg(i);
360 if (rta_is_alive_graph (graph)) {
365 return (n_live_graphs);
368 void rta_init (int verbose)
370 int n_live_graphs = get_irp_n_irgs ();
376 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
377 rta_fill_all (FALSE);
379 while (n_graphs != n_live_graphs) {
380 n_graphs = n_live_graphs;
383 n_live_graphs = stats ();
385 printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
390 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
391 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
392 printf ("RTA: n_runs = %i\n", n_runs);
396 void rta_cleanup (void)
399 eset_destroy (_live_classes);
400 _live_classes = NULL;
404 eset_destroy (_live_fields);
408 if (_called_methods) {
409 eset_destroy (_called_methods);
410 _called_methods = NULL;
414 eset_destroy (_live_graphs);
419 eset_destroy (_dead_graphs);
424 int rta_is_alive_class (type *clazz)
426 return (eset_contains (_live_classes, clazz));
429 int rta_is_alive_graph (ir_graph *graph)
433 if (eset_contains (_live_graphs, graph)) {
437 if (eset_contains (_dead_graphs, graph)) {
441 meth = get_irg_ent (graph);
443 if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
444 eset_insert (_live_graphs, graph);
448 eset_insert (_dead_graphs, graph);
454 int rta_is_alive_field (entity *field)
456 return (eset_contains (_live_fields, field));
463 * Revision 1.7 2004/06/15 11:44:54 beck
464 * New inlining schema implemented:
466 * small functions that should be inlined in libFirm are implemented in _t.h files
468 * Preprocessor magic is used to automatically inline these functions whenever a _t.h
469 * file is included instead of a .h file.
470 * Note that this magic did not work outside libFirm without accessing _t.h files.
472 * Revision 1.6 2004/06/14 13:02:03 goetz
475 * Revision 1.5 2004/06/13 15:03:45 liekweg
476 * RTA auf Iterative RTA aufgebohrt --flo
478 * Revision 1.4 2004/06/12 19:35:04 liekweg
479 * Kommentare eingef"ugt --flo
481 * Revision 1.3 2004/06/12 17:09:46 liekweg
482 * RTA works, outedges breaks. "Yay." --flo
484 * Revision 1.2 2004/06/11 18:25:39 liekweg
487 * Revision 1.1 2004/06/11 18:24:18 liekweg