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.
49 # endif /* not defined TRUE */
52 static int verbose = 0;
56 static eset *_live_classes = NULL;
58 /* cache computed results */
59 static eset *_live_graphs = NULL;
62 Given a method, find the firm graph that implements that method.
64 static ir_graph *get_implementing_graph (entity *method)
67 ir_graph *graph = get_entity_irg ((entity*) method);
69 /* Search upwards in the overwrites graph. */
70 /* GL: this will not work for multiple inheritance */
73 int n_over = get_entity_n_overwrites ((entity*) method);
75 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
76 entity *over = get_entity_overwrites ((entity*) method, i);
77 graph = get_implementing_graph (over);
81 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
82 assert(get_entity_peculiarity(method) == peculiarity_description
83 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
85 /* we *must* always return a graph != NULL, *except* when we're used
86 inside remove_irg or force_description */
87 /* assert (graph && "no graph"); */
91 ir_graph *graph = NULL;
93 if (get_entity_peculiarity(method) != peculiarity_description)
94 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
100 static int add_graph (ir_graph *graph)
102 if (!eset_contains (_live_graphs, graph)) {
104 fprintf(stdout, "RTA: new graph of ");
105 DDMEO(get_irg_entity (graph));
108 eset_insert (_live_graphs, graph);
115 static int add_class (type *clazz)
117 if (!eset_contains (_live_classes, clazz)) {
119 fprintf(stdout, "RTA: new class: ");
123 eset_insert (_live_classes, clazz);
130 /** Given an entity, add all implementing graphs that belong to live classes
133 * Iff additions occurred, return TRUE, else FALSE.
135 static int add_implementing_graphs (entity *method)
138 int n_over = get_entity_n_overwrittenby (method);
139 ir_graph *graph = get_entity_irg (method);
143 graph = get_implementing_graph (method);
147 fprintf(stdout, "RTA: new call to ");
151 if (rta_is_alive_class (get_entity_owner (method))) {
153 change = add_graph (graph);
157 for (i = 0; i < n_over; i ++) {
158 entity *over = get_entity_overwrittenby (method, i);
159 change |= add_implementing_graphs (over);
165 /** Enter all method accesses and all class allocations into
168 * Set *(int*)env to true iff (possibly) new graphs have been found.
170 static void rta_act (ir_node *node, void *env)
172 int *change = (int*) env;
174 opcode op = get_irn_opcode (node);
176 if (iro_Call == op) { /* CALL */
179 ir_node *ptr = get_Call_ptr (node);
182 if (iro_Sel == get_irn_opcode (ptr)) {
183 ent = get_Sel_entity (ptr);
184 *change |= add_implementing_graphs (ent);
187 } else if (iro_SymConst == get_irn_opcode (ptr)) {
188 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
189 ent = get_SymConst_entity (ptr);
190 ir_graph *graph = get_entity_irg (ent);
192 *change |= add_graph (graph);
194 /* it's an external allocated thing. */
196 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
197 /* If this SymConst refers to a method the method is external_visible
198 and therefore must be considered live anyways. */
199 if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
200 assert (ent && "couldn't determine entity of call to symConst");
202 /* other symconst. */
203 assert(0 && "This SymConst can not be an address for a method call.");
209 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
212 } else if (iro_Alloc == op) { /* ALLOC */
213 type *type = get_Alloc_type (node);
215 *change |= add_class (type);
220 Traverse the given graph to collect method accesses and
223 static int rta_fill_graph (ir_graph* graph)
227 current_ir_graph = graph;
229 irg_walk_graph (graph, rta_act, NULL, &change);
234 /** Traverse all graphs to collect method accesses and object allocations.
236 * @param rerun Whether to rely on is_alive in a second run
238 static int rta_fill_incremental (void)
243 int old_ip_view = interprocedural_view;
245 interprocedural_view = 0; /* save this for later */
247 /* init_tables has added main_irg to _live_graphs */
249 /* Need to take care of graphs that are externally
250 visible or sticky. Pretend that they are called: */
252 for (i = 0; i < get_irp_n_irgs(); i++) {
253 ir_graph *graph = get_irp_irg (i);
254 entity *ent = get_irg_entity (graph);
256 if ((visibility_external_visible == get_entity_visibility (ent)) ||
257 (stickyness_sticky == get_entity_stickyness (ent))) {
258 eset_insert (_live_graphs, graph);
259 // printf("external visible: "); DDMG(graph);
267 eset *live_graphs = _live_graphs;
268 _live_graphs = eset_create ();
271 fprintf(stdout, "RTA: RUN %i\n", n_runs);
274 /* collect what we have found previously */
275 eset_insert_all (_live_graphs, live_graphs);
278 for (graph = eset_first (live_graphs);
280 graph = eset_next (live_graphs)) {
283 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
284 DDMEO(get_irg_entity (graph));
287 rerun |= rta_fill_graph (graph);
290 eset_destroy (live_graphs);
295 interprocedural_view = old_ip_view; /* cover up our traces */
301 Count the number of graphs that we have found to be live.
303 static int stats (void)
306 int n_live_graphs = 0;
307 int n_graphs = get_irp_n_irgs();
309 for (i = 0; i < n_graphs; i++) {
310 ir_graph *graph = get_irp_irg(i);
312 if (rta_is_alive_graph (graph)) {
317 return (n_live_graphs);
320 /* remove a graph, part I */
322 We removed the first graph to implement the entity, so we're
323 abstract now. Pretend that it wasn't there at all, and every
324 entity that used to inherit this entity's graph is now abstract.
326 /* Since we *know* that this entity will not be called, this is OK. */
327 static void force_description (entity *ent, entity *addr)
329 int i, n_over = get_entity_n_overwrittenby (ent);
331 set_entity_peculiarity (ent, peculiarity_description);
333 for (i = 0; i < n_over; i ++) {
334 entity *over = get_entity_overwrittenby (ent, i);
336 if (peculiarity_inherited == get_entity_peculiarity (over)) {
337 /* We rely on the fact that cse is performed on the const_code_irg. */
338 entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
340 if (addr == my_addr) {
341 force_description (over, addr);
343 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
344 /* check whether 'over' forces 'inheritance' of *our* graph: */
345 ir_node *f_addr = get_atomic_ent_value (over);
346 entity *impl_ent = get_SymConst_entity (f_addr);
348 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
349 if (impl_ent == addr) {
350 assert (0 && "gibt's denn sowas");
351 force_description (over, addr);
358 Initialise the static data structures.
360 static void init_tables (void)
362 int i, n_globs = get_class_n_members(get_glob_type());
364 _live_classes = eset_create ();
365 _live_graphs = eset_create ();
367 if (get_irp_main_irg ()) {
368 eset_insert (_live_graphs, get_irp_main_irg ());
371 /* Find static allocated classes */
372 for (i = 0; i < n_globs; ++i) {
373 type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
374 if (is_class_type(member_type))
375 eset_insert(_live_classes, member_type);
380 * Initialise the RTA data structures, and perform RTA.
381 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
383 void rta_init (int do_verbose)
387 # ifdef DEBUG_libfirm
389 for (i = 0; i < get_irp_n_irgs(); i++) {
390 irg_vrfy (get_irp_irg(i));
393 # endif /* defined DEBUG_libfirm */
395 verbose = do_verbose;
399 n_runs = rta_fill_incremental ();
402 int n_live_graphs = stats ();
404 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
405 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
406 printf ("RTA: n_runs = %i\n", n_runs);
409 # ifdef DEBUG_libfirm
410 for (i = 0; i < get_irp_n_irgs(); i++) {
411 irg_vrfy (get_irp_irg(i));
414 # endif /* defined DEBUG_libfirm */
418 * walker for all types and entities
420 * Changes the peculiarity of entities that represents
421 * dead graphs to peculiarity_description.
423 static void make_entity_to_description(type_or_ent *tore, void *env) {
424 if (get_kind(tore) == k_entity) {
425 entity *ent = (entity *)tore;
427 if ((is_method_type(get_entity_type(ent))) &&
428 (get_entity_peculiarity(ent) != peculiarity_description) &&
429 (get_entity_visibility(ent) != visibility_external_allocated) ) {
430 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
431 if (!eset_contains (_live_graphs, irg)) {
432 set_entity_peculiarity(ent, peculiarity_description);
433 set_entity_irg(ent, NULL);
439 /* Delete all graphs that we have found to be dead from the program
440 If verbose == 1, print statistics, if > 1, chatter about every detail
442 void rta_delete_dead_graphs (void)
445 int n_graphs = get_irp_n_irgs ();
446 ir_graph *graph = NULL;
447 int n_dead_graphs = 0;
449 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
451 ir_graph *dead_graphs[get_irp_n_irgs()];
453 for (i = 0; i < n_graphs; i++) {
454 graph = get_irp_irg(i);
456 if (rta_is_alive_graph (graph)) {
457 /* do nothing (except some debugging fprintf`s :-) */
459 # ifdef DEBUG_libfirm
460 entity *ent = get_irg_entity (graph);
461 assert (visibility_external_visible != get_entity_visibility (ent));
462 # endif /* defined DEBUG_libfirm */
464 dead_graphs[n_dead_graphs] = graph;
469 type_walk(make_entity_to_description, NULL, NULL);
470 for (i = 0; i < n_dead_graphs; ++i) {
471 remove_irp_irg (dead_graphs[i]);
475 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
479 /* Clean up the RTA data structures. Call this after calling rta_init */
480 void rta_cleanup (void)
482 # ifdef DEBUG_libfirm
484 for (i = 0; i < get_irp_n_irgs(); i++) {
485 irg_vrfy (get_irp_irg(i));
488 # endif /* defined DEBUG_libfirm */
491 eset_destroy (_live_classes);
492 _live_classes = NULL;
496 eset_destroy (_live_graphs);
501 /* Say whether this class might be instantiated at any point in the program: */
502 int rta_is_alive_class (type *clazz)
504 return (eset_contains (_live_classes, clazz));
507 /* Say whether this graph might be run at any time in the program: */
508 int rta_is_alive_graph (ir_graph *graph)
510 return eset_contains (_live_graphs, graph);
513 /* dump our opinion */
514 void rta_report (void)
518 for (i = 0; i < get_irp_n_types(); ++i) {
519 type *tp = get_irp_type(i);
520 if (is_class_type(tp) && rta_is_alive_class(tp)) {
521 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
525 for (i = 0; i < get_irp_n_irgs(); i++) {
526 if (rta_is_alive_graph (get_irp_irg(i))) {
527 fprintf(stdout, "RTA: considered called: graph of ");
528 DDMEO(get_irg_entity (get_irp_irg(i)));
536 * Revision 1.26 2004/10/20 14:59:27 liekweg
539 * Revision 1.25 2004/10/18 12:47:08 liekweg
542 * Revision 1.24 2004/09/24 13:59:04 beck
543 * fixed doxygen comments, removed initialization for description entities
545 * Revision 1.23 2004/08/19 16:51:02 goetz
546 * fixed some errors, pushed closer to inteded firm semantics
548 * Revision 1.22 2004/08/13 08:57:15 beyhan
549 * normalized names of functions, enums ...
550 * added suffix as argument to dumpers, removed global variable
551 * removed support for tarval/Const
553 * Revision 1.21 2004/07/08 15:50:56 goetz
556 * Revision 1.20 2004/07/08 11:17:40 goetz
557 * *** empty log message ***
559 * Revision 1.19 2004/07/06 12:30:37 beyhan
560 * new SymConst semantics
562 * Revision 1.18 2004/06/27 21:17:41 liekweg
565 * Revision 1.17 2004/06/25 13:45:13 liekweg
566 * observe stickyness; minor refactoring
568 * Revision 1.16 2004/06/24 06:42:14 goetz
571 * Revision 1.15 2004/06/18 15:47:19 liekweg
572 * minor bug fix (go forward, not backward) --flo
574 * Revision 1.14 2004/06/18 13:12:43 liekweg
575 * final bug fix (calls via consts)
577 * Revision 1.13 2004/06/17 16:34:33 liekweg
580 * Revision 1.12 2004/06/17 16:33:33 liekweg
583 * Revision 1.11 2004/06/17 14:21:13 liekweg
586 * Revision 1.10 2004/06/17 10:31:41 goetz
587 * irscc: bugfix, can now deal with loops not reachable from start
588 * cgana: bugfix, skip_Tuple
591 * Revision 1.9 2004/06/17 08:56:03 liekweg
592 * Fixed typos in comments
594 * Revision 1.8 2004/06/17 08:33:01 liekweg
595 * Added comments; added remove_irg
597 * Revision 1.6 2004/06/14 13:02:03 goetz
600 * Revision 1.5 2004/06/13 15:03:45 liekweg
601 * RTA auf Iterative RTA aufgebohrt --flo
603 * Revision 1.4 2004/06/12 19:35:04 liekweg
604 * Kommentare eingef"ugt --flo
606 * Revision 1.3 2004/06/12 17:09:46 liekweg
607 * RTA works, outedges breaks. "Yay." --flo
609 * Revision 1.2 2004/06/11 18:25:39 liekweg
612 * Revision 1.1 2004/06/11 18:24:18 liekweg