5 * File name: ir/ana/rta.c
6 * Purpose: Interprocedural analysis to improve the call graph estimate.
11 * Copyright: (c) 1999-2004 Universität Karlsruhe
12 * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es wird
17 * die Menge der instantiierten Klassen bestimmt, und daraus eine Abschätzung
18 * der aufgerufenen Methoden.
20 * Voraussetzung ist, dass das Programm keine Methodenzeiger handhaben kann.
21 * In diesem Fall koennten Methoden verloren gehen. Oder wir muessen nach
22 * allen "freien" Methoden suchen (siehe cgana).
24 * @@@ Die Analyse sollte wissen, von welchen Klassen Instanzen ausserhalb
25 * der Uebersetzungseinheit alloziert werden koennen. Diese muessen in
26 * die initiale Menge allozierter Klassen aufgenommern werden.
50 static int verbose = 0;
54 static eset *_live_classes = NULL;
56 /* cache computed results */
57 static eset *_live_graphs = NULL;
60 Given a method, find the firm graph that implements that method.
62 static ir_graph *get_implementing_graph (entity *method)
65 ir_graph *graph = get_entity_irg ((entity*) method);
67 /* Search upwards in the overwrites graph. */
68 /* GL: this will not work for multiple inheritance */
71 int n_over = get_entity_n_overwrites ((entity*) method);
73 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
74 entity *over = get_entity_overwrites ((entity*) method, i);
75 graph = get_implementing_graph (over);
79 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
80 assert(get_entity_peculiarity(method) == peculiarity_description
81 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
83 /* we *must* always return a graph != NULL, *except* when we're used
84 inside remove_irg or force_description */
85 /* assert (graph && "no graph"); */
89 ir_graph *graph = NULL;
91 if (get_entity_peculiarity(method) != peculiarity_description)
92 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
98 static int add_graph (ir_graph *graph)
100 if (!eset_contains (_live_graphs, graph)) {
102 fprintf(stdout, "RTA: new graph of ");
103 DDMEO(get_irg_entity (graph));
106 eset_insert (_live_graphs, graph);
113 static int add_class (type *clazz)
115 if (!eset_contains (_live_classes, clazz)) {
117 fprintf(stdout, "RTA: new class: ");
121 eset_insert (_live_classes, clazz);
128 /** Given an entity, add all implementing graphs that belong to live classes
131 * Iff additions occurred, return TRUE, else FALSE.
133 static int add_implementing_graphs (entity *method)
136 int n_over = get_entity_n_overwrittenby (method);
137 ir_graph *graph = get_entity_irg (method);
141 graph = get_implementing_graph (method);
145 fprintf(stdout, "RTA: new call to ");
149 if (rta_is_alive_class (get_entity_owner (method))) {
151 change = add_graph (graph);
155 for (i = 0; i < n_over; i ++) {
156 entity *over = get_entity_overwrittenby (method, i);
157 change |= add_implementing_graphs (over);
163 /** Enter all method accesses and all class allocations into
166 * Set *(int*)env to true iff (possibly) new graphs have been found.
168 static void rta_act (ir_node *node, void *env)
170 int *change = (int*) env;
172 opcode op = get_irn_opcode (node);
174 if (iro_Call == op) { /* CALL */
177 ir_node *ptr = get_Call_ptr (node);
180 if (iro_Sel == get_irn_opcode (ptr)) {
181 ent = get_Sel_entity (ptr);
182 *change |= add_implementing_graphs (ent);
185 } else if (iro_SymConst == get_irn_opcode (ptr)) {
186 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
187 ent = get_SymConst_entity (ptr);
188 ir_graph *graph = get_entity_irg (ent);
190 *change |= add_graph (graph);
192 /* it's an external allocated thing. */
194 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
195 /* If this SymConst refers to a method the method is external_visible
196 and therefore must be considered live anyways. */
197 if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
198 assert (ent && "couldn't determine entity of call to symConst");
200 /* other symconst. */
201 assert(0 && "This SymConst can not be an address for a method call.");
207 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
210 } else if (iro_Alloc == op) { /* ALLOC */
211 type *type = get_Alloc_type (node);
213 *change |= add_class (type);
218 Traverse the given graph to collect method accesses and
221 static int rta_fill_graph (ir_graph* graph)
225 current_ir_graph = graph;
227 irg_walk_graph (graph, rta_act, NULL, &change);
232 /** Traverse all graphs to collect method accesses and object allocations.
234 * @param rerun Whether to rely on is_alive in a second run
236 static int rta_fill_incremental (void)
241 int old_ip_view = interprocedural_view;
243 interprocedural_view = 0; /* save this for later */
245 /* init_tables has added main_irg to _live_graphs */
247 /* Need to take care of graphs that are externally
248 visible or sticky. Pretend that they are called: */
250 for (i = 0; i < get_irp_n_irgs(); i++) {
251 ir_graph *graph = get_irp_irg (i);
252 entity *ent = get_irg_entity (graph);
254 if ((visibility_external_visible == get_entity_visibility (ent)) ||
255 (stickyness_sticky == get_entity_stickyness (ent))) {
256 eset_insert (_live_graphs, graph);
257 // printf("external visible: "); DDMG(graph);
265 eset *live_graphs = _live_graphs;
266 _live_graphs = eset_create ();
269 fprintf(stdout, "RTA: RUN %i\n", n_runs);
272 /* collect what we have found previously */
273 eset_insert_all (_live_graphs, live_graphs);
276 for (graph = eset_first (live_graphs);
278 graph = eset_next (live_graphs)) {
281 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
282 DDMEO(get_irg_entity (graph));
285 rerun |= rta_fill_graph (graph);
288 eset_destroy (live_graphs);
293 interprocedural_view = old_ip_view; /* cover up our traces */
299 Count the number of graphs that we have found to be live.
301 static int stats (void)
304 int n_live_graphs = 0;
305 int n_graphs = get_irp_n_irgs();
307 for (i = 0; i < n_graphs; i++) {
308 ir_graph *graph = get_irp_irg(i);
310 if (rta_is_alive_graph (graph)) {
315 return (n_live_graphs);
318 /* remove a graph, part I */
320 We removed the first graph to implement the entity, so we're
321 abstract now. Pretend that it wasn't there at all, and every
322 entity that used to inherit this entity's graph is now abstract.
324 /* Since we *know* that this entity will not be called, this is OK. */
325 static void force_description (entity *ent, entity *addr)
327 int i, n_over = get_entity_n_overwrittenby (ent);
329 set_entity_peculiarity (ent, peculiarity_description);
331 for (i = 0; i < n_over; i ++) {
332 entity *over = get_entity_overwrittenby (ent, i);
334 if (peculiarity_inherited == get_entity_peculiarity (over)) {
335 /* We rely on the fact that cse is performed on the const_code_irg. */
336 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
338 if (addr == my_addr) {
339 force_description (over, addr);
341 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
342 /* check whether 'over' forces 'inheritance' of *our* graph: */
343 ir_node *f_addr = get_atomic_ent_value (over);
344 entity *impl_ent = get_SymConst_entity (f_addr);
346 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
347 if (impl_ent == addr) {
348 assert (0 && "gibt's denn sowas");
349 force_description (over, addr);
356 Initialise the static data structures.
358 static void init_tables (void)
360 int i, n_globs = get_class_n_members(get_glob_type());
362 _live_classes = eset_create ();
364 _live_graphs = eset_create ();
366 if (get_irp_main_irg ()) {
367 eset_insert (_live_graphs, get_irp_main_irg ());
370 /* Find static allocated classes */
371 for (i = 0; i < n_globs; ++i) {
372 type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
373 if (is_class_type(member_type))
374 eset_insert(_live_classes, member_type);
378 /* Initialise the RTA data structures, and perform RTA.
379 @param do_verbose If == 1, print statistics, if > 1, chatter about every detail
381 void rta_init (int do_verbose)
385 # ifdef DEBUG_libfirm
387 for (i = 0; i < get_irp_n_irgs(); i++) {
388 irg_vrfy (get_irp_irg(i));
391 # endif /* defined DEBUG_libfirm */
393 verbose = do_verbose;
397 n_runs = rta_fill_incremental ();
400 int n_live_graphs = stats ();
402 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
403 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
404 printf ("RTA: n_runs = %i\n", n_runs);
407 # ifdef DEBUG_libfirm
408 for (i = 0; i < get_irp_n_irgs(); i++) {
409 irg_vrfy (get_irp_irg(i));
412 # endif /* defined DEBUG_libfirm */
416 void make_entity_to_description(type_or_ent *tore, void *env) {
417 if (get_kind(tore) == k_entity) {
418 entity *ent = (entity *)tore;
420 if ((is_method_type(get_entity_type(ent))) &&
421 (get_entity_peculiarity(ent) != peculiarity_description) &&
422 (get_entity_visibility(ent) != visibility_external_allocated) ) {
423 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
424 if (!eset_contains (_live_graphs, irg)) {
425 set_entity_peculiarity(ent, peculiarity_description);
426 set_entity_irg(ent, NULL);
427 set_atomic_ent_value(ent, new_Const(mode_P, get_tarval_null(mode_P)));
433 /* Delete all graphs that we have found to be dead from the program
434 If verbose == 1, print statistics, if > 1, chatter about every detail
436 void rta_delete_dead_graphs (void)
439 int n_graphs = get_irp_n_irgs ();
440 ir_graph *graph = NULL;
441 int n_dead_graphs = 0;
443 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
445 ir_graph *dead_graphs[get_irp_n_irgs()];
447 for (i = 0; i < n_graphs; i++) {
448 graph = get_irp_irg(i);
450 if (rta_is_alive_graph (graph)) {
451 /* do nothing (except some debugging fprintf`s :-) */
453 # ifdef DEBUG_libfirm
454 entity *ent = get_irg_entity (graph);
455 assert (visibility_external_visible != get_entity_visibility (ent));
456 # endif /* defined DEBUG_libfirm */
458 dead_graphs[n_dead_graphs] = graph;
463 current_ir_graph = get_const_code_irg();
464 type_walk(make_entity_to_description, NULL, NULL);
465 for (i = 0; i < n_dead_graphs; ++i) {
466 remove_irp_irg (dead_graphs[i]);
470 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
474 /* Clean up the RTA data structures. Call this after calling rta_init */
475 void rta_cleanup (void)
477 # ifdef DEBUG_libfirm
479 for (i = 0; i < get_irp_n_irgs(); i++) {
480 irg_vrfy (get_irp_irg(i));
483 # endif /* defined DEBUG_libfirm */
486 eset_destroy (_live_classes);
487 _live_classes = NULL;
491 eset_destroy (_live_graphs);
496 /* Say whether this class might be instantiated at any point in the program: */
497 int rta_is_alive_class (type *clazz)
499 return (eset_contains (_live_classes, clazz));
502 /* Say whether this graph might be run at any time in the program: */
503 int rta_is_alive_graph (ir_graph *graph)
505 if (eset_contains (_live_graphs, graph)) {
512 /* dump our opinion */
513 void rta_report (void)
517 for (i = 0; i < get_irp_n_types(); ++i) {
518 type *tp = get_irp_type(i);
519 if (is_class_type(tp) && rta_is_alive_class(tp)) {
520 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
524 for (i = 0; i < get_irp_n_irgs(); i++) {
525 if (rta_is_alive_graph (get_irp_irg(i))) {
526 fprintf(stdout, "RTA: considered called: graph of ");
527 DDMEO(get_irg_entity (get_irp_irg(i)));
535 * Revision 1.23 2004/08/19 16:51:02 goetz
536 * fixed some errors, pushed closer to inteded firm semantics
538 * Revision 1.22 2004/08/13 08:57:15 beyhan
539 * normalized names of functions, enums ...
540 * added suffix as argument to dumpers, removed global variable
541 * removed support for tarval/Const
543 * Revision 1.21 2004/07/08 15:50:56 goetz
546 * Revision 1.20 2004/07/08 11:17:40 goetz
547 * *** empty log message ***
549 * Revision 1.19 2004/07/06 12:30:37 beyhan
550 * new SymConst semantics
552 * Revision 1.18 2004/06/27 21:17:41 liekweg
555 * Revision 1.17 2004/06/25 13:45:13 liekweg
556 * observe stickyness; minor refactoring
558 * Revision 1.16 2004/06/24 06:42:14 goetz
561 * Revision 1.15 2004/06/18 15:47:19 liekweg
562 * minor bug fix (go forward, not backward) --flo
564 * Revision 1.14 2004/06/18 13:12:43 liekweg
565 * final bug fix (calls via consts)
567 * Revision 1.13 2004/06/17 16:34:33 liekweg
570 * Revision 1.12 2004/06/17 16:33:33 liekweg
573 * Revision 1.11 2004/06/17 14:21:13 liekweg
576 * Revision 1.10 2004/06/17 10:31:41 goetz
577 * irscc: bugfix, can now deal with loops not reachable from start
578 * cgana: bugfix, skip_Tuple
581 * Revision 1.9 2004/06/17 08:56:03 liekweg
582 * Fixed typos in comments
584 * Revision 1.8 2004/06/17 08:33:01 liekweg
585 * Added comments; added remove_irg
587 * Revision 1.6 2004/06/14 13:02:03 goetz
590 * Revision 1.5 2004/06/13 15:03:45 liekweg
591 * RTA auf Iterative RTA aufgebohrt --flo
593 * Revision 1.4 2004/06/12 19:35:04 liekweg
594 * Kommentare eingef"ugt --flo
596 * Revision 1.3 2004/06/12 17:09:46 liekweg
597 * RTA works, outedges breaks. "Yay." --flo
599 * Revision 1.2 2004/06/11 18:25:39 liekweg
602 * Revision 1.1 2004/06/11 18:24:18 liekweg