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 ();
363 _live_graphs = eset_create ();
365 if (get_irp_main_irg ()) {
366 eset_insert (_live_graphs, get_irp_main_irg ());
369 /* Find static allocated classes */
370 for (i = 0; i < n_globs; ++i) {
371 type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
372 if (is_class_type(member_type))
373 eset_insert(_live_classes, member_type);
378 * Initialise the RTA data structures, and perform RTA.
379 * 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 * walker for all types and entities
418 * Changes the peculiarity of entities that represents
419 * dead graphs to peculiarity_description.
421 static void make_entity_to_description(type_or_ent *tore, void *env) {
422 if (get_kind(tore) == k_entity) {
423 entity *ent = (entity *)tore;
425 if ((is_method_type(get_entity_type(ent))) &&
426 (get_entity_peculiarity(ent) != peculiarity_description) &&
427 (get_entity_visibility(ent) != visibility_external_allocated) ) {
428 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
429 if (!eset_contains (_live_graphs, irg)) {
430 set_entity_peculiarity(ent, peculiarity_description);
431 set_entity_irg(ent, NULL);
437 /* Delete all graphs that we have found to be dead from the program
438 If verbose == 1, print statistics, if > 1, chatter about every detail
440 void rta_delete_dead_graphs (void)
443 int n_graphs = get_irp_n_irgs ();
444 ir_graph *graph = NULL;
445 int n_dead_graphs = 0;
447 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
449 ir_graph *dead_graphs[get_irp_n_irgs()];
451 for (i = 0; i < n_graphs; i++) {
452 graph = get_irp_irg(i);
454 if (rta_is_alive_graph (graph)) {
455 /* do nothing (except some debugging fprintf`s :-) */
457 # ifdef DEBUG_libfirm
458 entity *ent = get_irg_entity (graph);
459 assert (visibility_external_visible != get_entity_visibility (ent));
460 # endif /* defined DEBUG_libfirm */
462 dead_graphs[n_dead_graphs] = graph;
467 type_walk(make_entity_to_description, NULL, NULL);
468 for (i = 0; i < n_dead_graphs; ++i) {
469 remove_irp_irg (dead_graphs[i]);
473 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
477 /* Clean up the RTA data structures. Call this after calling rta_init */
478 void rta_cleanup (void)
480 # ifdef DEBUG_libfirm
482 for (i = 0; i < get_irp_n_irgs(); i++) {
483 irg_vrfy (get_irp_irg(i));
486 # endif /* defined DEBUG_libfirm */
489 eset_destroy (_live_classes);
490 _live_classes = NULL;
494 eset_destroy (_live_graphs);
499 /* Say whether this class might be instantiated at any point in the program: */
500 int rta_is_alive_class (type *clazz)
502 return (eset_contains (_live_classes, clazz));
505 /* Say whether this graph might be run at any time in the program: */
506 int rta_is_alive_graph (ir_graph *graph)
508 return eset_contains (_live_graphs, graph);
511 /* dump our opinion */
512 void rta_report (void)
516 for (i = 0; i < get_irp_n_types(); ++i) {
517 type *tp = get_irp_type(i);
518 if (is_class_type(tp) && rta_is_alive_class(tp)) {
519 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
523 for (i = 0; i < get_irp_n_irgs(); i++) {
524 if (rta_is_alive_graph (get_irp_irg(i))) {
525 fprintf(stdout, "RTA: considered called: graph of ");
526 DDMEO(get_irg_entity (get_irp_irg(i)));
534 * Revision 1.24 2004/09/24 13:59:04 beck
535 * fixed doxygen comments, removed initialization for description entities
537 * Revision 1.23 2004/08/19 16:51:02 goetz
538 * fixed some errors, pushed closer to inteded firm semantics
540 * Revision 1.22 2004/08/13 08:57:15 beyhan
541 * normalized names of functions, enums ...
542 * added suffix as argument to dumpers, removed global variable
543 * removed support for tarval/Const
545 * Revision 1.21 2004/07/08 15:50:56 goetz
548 * Revision 1.20 2004/07/08 11:17:40 goetz
549 * *** empty log message ***
551 * Revision 1.19 2004/07/06 12:30:37 beyhan
552 * new SymConst semantics
554 * Revision 1.18 2004/06/27 21:17:41 liekweg
557 * Revision 1.17 2004/06/25 13:45:13 liekweg
558 * observe stickyness; minor refactoring
560 * Revision 1.16 2004/06/24 06:42:14 goetz
563 * Revision 1.15 2004/06/18 15:47:19 liekweg
564 * minor bug fix (go forward, not backward) --flo
566 * Revision 1.14 2004/06/18 13:12:43 liekweg
567 * final bug fix (calls via consts)
569 * Revision 1.13 2004/06/17 16:34:33 liekweg
572 * Revision 1.12 2004/06/17 16:33:33 liekweg
575 * Revision 1.11 2004/06/17 14:21:13 liekweg
578 * Revision 1.10 2004/06/17 10:31:41 goetz
579 * irscc: bugfix, can now deal with loops not reachable from start
580 * cgana: bugfix, skip_Tuple
583 * Revision 1.9 2004/06/17 08:56:03 liekweg
584 * Fixed typos in comments
586 * Revision 1.8 2004/06/17 08:33:01 liekweg
587 * Added comments; added remove_irg
589 * Revision 1.6 2004/06/14 13:02:03 goetz
592 * Revision 1.5 2004/06/13 15:03:45 liekweg
593 * RTA auf Iterative RTA aufgebohrt --flo
595 * Revision 1.4 2004/06/12 19:35:04 liekweg
596 * Kommentare eingef"ugt --flo
598 * Revision 1.3 2004/06/12 17:09:46 liekweg
599 * RTA works, outedges breaks. "Yay." --flo
601 * Revision 1.2 2004/06/11 18:25:39 liekweg
604 * Revision 1.1 2004/06/11 18:24:18 liekweg