2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Interprocedural analysis to improve the call graph estimate.
37 #include "irgraph_t.h"
48 # endif /* not defined TRUE */
51 static int verbose = 0;
55 static eset *_live_classes = NULL;
57 /* cache computed results */
58 static eset *_live_graphs = NULL;
61 Given a method, find the firm graph that implements that method.
63 static ir_graph *get_implementing_graph (ir_entity *method)
66 ir_graph *graph = get_entity_irg ((ir_entity*) method);
68 /* Search upwards in the overwrites graph. */
69 /* GL: this will not work for multiple inheritance */
72 int n_over = get_entity_n_overwrites ((ir_entity*) method);
74 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
75 ir_entity *over = get_entity_overwrites ((ir_entity*) method, i);
76 graph = get_implementing_graph (over);
80 /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */
81 assert(get_entity_peculiarity(method) == peculiarity_description
82 || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
84 /* we *must* always return a graph != NULL, *except* when we're used
85 inside remove_irg or force_description */
86 /* assert (graph && "no graph"); */
90 ir_graph *graph = NULL;
92 if (get_entity_peculiarity(method) != peculiarity_description)
93 graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
100 * Add a graph to the set of live graphs.
102 * @param graph the graph to add
103 * @return non-zero if the graph was added, zero
104 * if it was already in the live set
106 static int add_graph (ir_graph *graph)
108 if (!eset_contains (_live_graphs, graph)) {
110 ir_fprintf(stdout, "RTA: new graph of %+F\n", graph);
113 eset_insert (_live_graphs, graph);
121 * Add a class to the set of live classes.
123 * @param clazz the class to add
124 * @return non-zero if the graph was added, zero
125 * if it was already in the live set
127 static int add_class (ir_type *clazz)
129 if (!eset_contains (_live_classes, clazz)) {
131 ir_fprintf(stdout, "RTA: new class: %+F\n", clazz);
134 eset_insert (_live_classes, clazz);
141 /** Given an entity, add all implementing graphs that belong to live classes
144 * Iff additions occurred, return TRUE, else FALSE.
146 static int add_implementing_graphs (ir_entity *method)
149 int n_over = get_entity_n_overwrittenby (method);
150 ir_graph *graph = get_entity_irg (method);
154 graph = get_implementing_graph (method);
158 ir_fprintf(stdout, "RTA: new call to %+F\n", method);
161 if (rta_is_alive_class (get_entity_owner (method))) {
163 change = add_graph (graph);
167 for (i = 0; i < n_over; i ++) {
168 ir_entity *over = get_entity_overwrittenby (method, i);
169 change |= add_implementing_graphs (over);
175 /** Enter all method accesses and all class allocations into
178 * Set *(int*)env to true iff (possibly) new graphs have been found.
180 static void rta_act (ir_node *node, void *env)
182 int *change = (int*) env;
183 ir_opcode op = get_irn_opcode (node);
185 if (iro_Call == op) { /* CALL */
186 ir_entity *ent = NULL;
188 ir_node *ptr = get_Call_ptr (node);
191 if (iro_Sel == get_irn_opcode (ptr)) {
192 ent = get_Sel_entity (ptr);
193 *change |= add_implementing_graphs (ent);
196 } else if (iro_SymConst == get_irn_opcode (ptr)) {
197 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
200 ent = get_SymConst_entity (ptr);
201 graph = get_entity_irg (ent);
203 *change |= add_graph (graph);
205 /* it's an external allocated thing. */
207 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
208 /* Entities of kind addr_name may not be allocated in this compilation unit.
209 If so, the frontend built faulty Firm. So just ignore. */
210 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
211 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
213 /* other symconst. */
214 assert(0 && "This SymConst can not be an address for a method call.");
219 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
222 } else if (iro_Alloc == op) { /* ALLOC */
223 ir_type *type = get_Alloc_type (node);
225 *change |= add_class (type);
230 Traverse the given graph to collect method accesses and
233 static int rta_fill_graph (ir_graph* graph)
236 irg_walk_graph (graph, rta_act, NULL, &change);
240 /** Traverse all graphs to collect method accesses and object allocations.
242 static int rta_fill_incremental (void)
247 int old_ip_view = get_interprocedural_view();
249 set_interprocedural_view(0); /* save this for later */
251 /* init_tables has added main_irg to _live_graphs */
253 /* Need to take care of graphs that are externally
254 visible or sticky. Pretend that they are called: */
256 for (i = 0; i < get_irp_n_irgs(); i++) {
257 ir_graph *graph = get_irp_irg (i);
258 ir_entity *ent = get_irg_entity (graph);
260 if ((visibility_external_visible == get_entity_visibility (ent)) ||
261 (stickyness_sticky == get_entity_stickyness (ent))) {
262 eset_insert (_live_graphs, graph);
263 // printf("external visible: "); DDMG(graph);
271 eset *live_graphs = _live_graphs;
272 _live_graphs = eset_create ();
275 fprintf(stdout, "RTA: RUN %i\n", n_runs);
278 /* collect what we have found previously */
279 eset_insert_all (_live_graphs, live_graphs);
282 for (graph = eset_first (live_graphs);
284 graph = eset_next (live_graphs)) {
287 ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs,
291 rerun |= rta_fill_graph (graph);
294 eset_destroy (live_graphs);
299 set_interprocedural_view(old_ip_view); /* cover up our traces */
305 * Count the number of graphs that we have found to be live.
307 static int stats (void)
310 int n_live_graphs = 0;
311 int n_graphs = get_irp_n_irgs();
313 for (i = 0; i < n_graphs; i++) {
314 ir_graph *graph = get_irp_irg(i);
316 if (rta_is_alive_graph (graph)) {
321 return (n_live_graphs);
324 /* remove a graph, part I */
326 We removed the first graph to implement the entity, so we're
327 abstract now. Pretend that it wasn't there at all, and every
328 entity that used to inherit this entity's graph is now abstract.
330 /* Since we *know* that this entity will not be called, this is OK. */
331 static void force_description (ir_entity *ent, ir_entity *addr)
333 int i, n_over = get_entity_n_overwrittenby (ent);
335 set_entity_peculiarity (ent, peculiarity_description);
337 for (i = 0; i < n_over; i ++) {
338 ir_entity *over = get_entity_overwrittenby (ent, i);
340 if (peculiarity_inherited == get_entity_peculiarity (over)) {
341 /* We rely on the fact that cse is performed on the const_code_irg. */
342 ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
344 if (addr == my_addr) {
345 force_description (over, addr);
347 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
348 /* check whether 'over' forces 'inheritance' of *our* graph: */
349 ir_node *f_addr = get_atomic_ent_value (over);
350 ir_entity *impl_ent = get_SymConst_entity (f_addr);
352 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
353 if (impl_ent == addr) {
354 assert (0 && "gibt's denn sowas");
355 force_description (over, addr);
362 Initialize the static data structures.
364 static void init_tables (void)
369 _live_classes = eset_create ();
370 _live_graphs = eset_create ();
372 if (get_irp_main_irg ()) {
373 eset_insert (_live_graphs, get_irp_main_irg ());
376 /* Find static allocated classes */
377 tp = get_glob_type();
378 n = get_class_n_members(tp);
379 for (i = 0; i < n; ++i) {
380 ir_type *member_type = get_entity_type(get_class_member(tp, i));
381 if (is_Class_type(member_type))
382 eset_insert(_live_classes, member_type);
386 n = get_struct_n_members(tp);
387 for (i = 0; i < n; ++i) {
388 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
389 if (is_Class_type(member_type))
390 eset_insert(_live_classes, member_type);
395 * Initialize the RTA data structures, and perform RTA.
396 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
398 void rta_init (int do_verbose)
402 int rem_vpi = get_visit_pseudo_irgs();
403 set_visit_pseudo_irgs(1);
405 # ifdef DEBUG_libfirm
408 n = get_irp_n_irgs();
409 for (i = 0; i < n; i++) {
410 irg_vrfy (get_irp_irg(i));
414 # endif /* defined DEBUG_libfirm */
416 verbose = do_verbose;
420 n_runs = rta_fill_incremental ();
423 int n_live_graphs = stats ();
425 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
426 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
427 printf ("RTA: n_runs = %i\n", n_runs);
430 # ifdef DEBUG_libfirm
433 n = get_irp_n_irgs();
434 for (i = 0; i < n; i++) {
435 irg_vrfy (get_irp_irg(i));
439 # endif /* defined DEBUG_libfirm */
441 set_visit_pseudo_irgs(rem_vpi);
445 * walker for all types and entities
447 * Changes the peculiarity of entities that represents
448 * dead graphs to peculiarity_description.
450 static void make_entity_to_description(type_or_ent *tore, void *env) {
451 if (get_kind(tore) == k_entity) {
452 ir_entity *ent = (ir_entity *)tore;
454 if ((is_Method_type(get_entity_type(ent))) &&
455 (get_entity_peculiarity(ent) != peculiarity_description) &&
456 (get_entity_visibility(ent) != visibility_external_allocated) ) {
457 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
458 if (!eset_contains (_live_graphs, irg)) {
459 set_entity_peculiarity(ent, peculiarity_description);
460 set_entity_irg(ent, NULL);
466 /* Delete all graphs that we have found to be dead from the program
467 If verbose == 1, print statistics, if > 1, chatter about every detail
469 void rta_delete_dead_graphs (void)
472 int n_graphs = get_irp_n_irgs ();
473 ir_graph *graph = NULL;
474 int n_dead_graphs = 0;
475 ir_graph **dead_graphs;
477 int rem_vpi = get_visit_pseudo_irgs();
478 set_visit_pseudo_irgs(1);
480 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
482 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
484 for (i = 0; i < n_graphs; i++) {
485 graph = get_irp_irg(i);
487 if (rta_is_alive_graph (graph)) {
488 /* do nothing (except some debugging fprintf`s :-) */
491 ir_entity *ent = get_irg_entity (graph);
492 assert (visibility_external_visible != get_entity_visibility (ent));
495 dead_graphs[n_dead_graphs] = graph;
500 type_walk(make_entity_to_description, NULL, NULL);
501 for (i = 0; i < n_dead_graphs; ++i) {
502 remove_irp_irg (dead_graphs[i]);
506 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
509 set_visit_pseudo_irgs(rem_vpi);
514 /* Clean up the RTA data structures. Call this after calling rta_init */
515 void rta_cleanup (void)
517 # ifdef DEBUG_libfirm
519 for (i = 0; i < get_irp_n_irgs(); i++) {
520 irg_vrfy (get_irp_irg(i));
523 # endif /* defined DEBUG_libfirm */
526 eset_destroy (_live_classes);
527 _live_classes = NULL;
531 eset_destroy (_live_graphs);
536 /* Say whether this class might be instantiated at any point in the program: */
537 int rta_is_alive_class (ir_type *clazz)
539 return (eset_contains (_live_classes, clazz));
542 /* Say whether this graph might be run at any time in the program: */
543 int rta_is_alive_graph (ir_graph *graph)
545 return eset_contains (_live_graphs, graph);
548 /* dump our opinion */
549 void rta_report (void)
553 for (i = 0; i < get_irp_n_types(); ++i) {
554 ir_type *tp = get_irp_type(i);
555 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
556 ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp);
560 for (i = 0; i < get_irp_n_irgs(); i++) {
561 if (rta_is_alive_graph (get_irp_irg(i))) {
562 ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i));
570 * Revision 1.41 2007/03/22 10:39:33 matze
571 * a bunch of fixes to make firm work with NDEBUG and without DEBUG_libfirm
573 * Revision 1.40 2007/01/16 15:45:15 beck
574 * renamed type opcode to ir_opcode
576 * Revision 1.39 2006/12/13 13:15:12 beck
577 * renamed entity -> ir_entity
579 * Revision 1.38 2006/12/12 16:12:05 beck
580 * Fixed missing initialization
582 * Revision 1.37 2006/12/11 15:28:48 matze
583 * - Several warning fixes
584 * - Fixes for compilation without DEBUG_libfirm
585 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
587 * Revision 1.36 2006/06/05 15:58:12 beck
588 * added support for Thread local storage
589 * added more doxygen docu
591 * Revision 1.35 2006/01/13 21:51:59 beck
592 * renamed all types 'type' to 'ir_type'
594 * Revision 1.34 2006/01/02 15:01:16 beck
595 * missing include added
597 * Revision 1.33 2005/11/17 17:26:57 beck
598 * removed bool type and depency from stdbool.h (not C89)
600 * Revision 1.32 2005/01/05 14:24:52 beck
601 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
603 * Revision 1.31 2004/12/21 13:45:14 beck
604 * removed C99 constructs
606 * Revision 1.30 2004/12/02 16:16:11 beck
607 * fixed config.h include
608 * used xmalloc instead of malloc
610 * Revision 1.29 2004/11/11 13:28:08 goetz
611 * made pseudo irg aware
613 * Revision 1.28 2004/11/03 14:47:18 beck
614 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
616 * Revision 1.27 2004/10/21 07:23:34 goetz
619 * Revision 1.26 2004/10/20 14:59:27 liekweg
622 * Revision 1.25 2004/10/18 12:47:08 liekweg
625 * Revision 1.24 2004/09/24 13:59:04 beck
626 * fixed doxygen comments, removed initialization for description entities
628 * Revision 1.23 2004/08/19 16:51:02 goetz
629 * fixed some errors, pushed closer to inteded firm semantics
631 * Revision 1.22 2004/08/13 08:57:15 beyhan
632 * normalized names of functions, enums ...
633 * added suffix as argument to dumpers, removed global variable
634 * removed support for tarval/Const
636 * Revision 1.21 2004/07/08 15:50:56 goetz
639 * Revision 1.20 2004/07/08 11:17:40 goetz
640 * *** empty log message ***
642 * Revision 1.19 2004/07/06 12:30:37 beyhan
643 * new SymConst semantics
645 * Revision 1.18 2004/06/27 21:17:41 liekweg
648 * Revision 1.17 2004/06/25 13:45:13 liekweg
649 * observe stickyness; minor refactoring
651 * Revision 1.16 2004/06/24 06:42:14 goetz
654 * Revision 1.15 2004/06/18 15:47:19 liekweg
655 * minor bug fix (go forward, not backward) --flo
657 * Revision 1.14 2004/06/18 13:12:43 liekweg
658 * final bug fix (calls via consts)
660 * Revision 1.13 2004/06/17 16:34:33 liekweg
663 * Revision 1.12 2004/06/17 16:33:33 liekweg
666 * Revision 1.11 2004/06/17 14:21:13 liekweg
669 * Revision 1.10 2004/06/17 10:31:41 goetz
670 * irscc: bugfix, can now deal with loops not reachable from start
671 * cgana: bugfix, skip_Tuple
674 * Revision 1.9 2004/06/17 08:56:03 liekweg
675 * Fixed typos in comments
677 * Revision 1.8 2004/06/17 08:33:01 liekweg
678 * Added comments; added remove_irg
680 * Revision 1.6 2004/06/14 13:02:03 goetz
683 * Revision 1.5 2004/06/13 15:03:45 liekweg
684 * RTA auf Iterative RTA aufgebohrt --flo
686 * Revision 1.4 2004/06/12 19:35:04 liekweg
687 * Kommentare eingef"ugt --flo
689 * Revision 1.3 2004/06/12 17:09:46 liekweg
690 * RTA works, outedges breaks. "Yay." --flo
692 * Revision 1.2 2004/06/11 18:25:39 liekweg
695 * Revision 1.1 2004/06/11 18:24:18 liekweg