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"
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 (ir_entity *method)
67 ir_graph *graph = get_entity_irg ((ir_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 ((ir_entity*) method);
75 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
76 ir_entity *over = get_entity_overwrites ((ir_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)));
101 * Add a graph to the set of live graphs.
103 * @param graph the graph to add
104 * @return non-zero if the graph was added, zero
105 * if it was already in the live set
107 static int add_graph (ir_graph *graph)
109 if (!eset_contains (_live_graphs, graph)) {
111 fprintf(stdout, "RTA: new graph of ");
112 DDMEO(get_irg_entity (graph));
115 eset_insert (_live_graphs, graph);
123 * Add a class to the set of live classes.
125 * @param clazz the class to add
126 * @return non-zero if the graph was added, zero
127 * if it was already in the live set
129 static int add_class (ir_type *clazz)
131 if (!eset_contains (_live_classes, clazz)) {
133 fprintf(stdout, "RTA: new class: ");
137 eset_insert (_live_classes, clazz);
144 /** Given an entity, add all implementing graphs that belong to live classes
147 * Iff additions occurred, return TRUE, else FALSE.
149 static int add_implementing_graphs (ir_entity *method)
152 int n_over = get_entity_n_overwrittenby (method);
153 ir_graph *graph = get_entity_irg (method);
157 graph = get_implementing_graph (method);
161 fprintf(stdout, "RTA: new call to ");
165 if (rta_is_alive_class (get_entity_owner (method))) {
167 change = add_graph (graph);
171 for (i = 0; i < n_over; i ++) {
172 ir_entity *over = get_entity_overwrittenby (method, i);
173 change |= add_implementing_graphs (over);
179 /** Enter all method accesses and all class allocations into
182 * Set *(int*)env to true iff (possibly) new graphs have been found.
184 static void rta_act (ir_node *node, void *env)
186 int *change = (int*) env;
187 ir_opcode op = get_irn_opcode (node);
189 if (iro_Call == op) { /* CALL */
190 ir_entity *ent = NULL;
192 ir_node *ptr = get_Call_ptr (node);
195 if (iro_Sel == get_irn_opcode (ptr)) {
196 ent = get_Sel_entity (ptr);
197 *change |= add_implementing_graphs (ent);
200 } else if (iro_SymConst == get_irn_opcode (ptr)) {
201 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
204 ent = get_SymConst_entity (ptr);
205 graph = get_entity_irg (ent);
207 *change |= add_graph (graph);
209 /* it's an external allocated thing. */
211 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
212 /* Entities of kind addr_name may not be allocated in this compilation unit.
213 If so, the frontend built faulty Firm. So just ignore. */
214 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
215 assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
217 /* other symconst. */
218 assert(0 && "This SymConst can not be an address for a method call.");
224 assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
227 } else if (iro_Alloc == op) { /* ALLOC */
228 ir_type *type = get_Alloc_type (node);
230 *change |= add_class (type);
235 Traverse the given graph to collect method accesses and
238 static int rta_fill_graph (ir_graph* graph)
241 irg_walk_graph (graph, rta_act, NULL, &change);
245 /** Traverse all graphs to collect method accesses and object allocations.
247 static int rta_fill_incremental (void)
252 int old_ip_view = get_interprocedural_view();
254 set_interprocedural_view(0); /* save this for later */
256 /* init_tables has added main_irg to _live_graphs */
258 /* Need to take care of graphs that are externally
259 visible or sticky. Pretend that they are called: */
261 for (i = 0; i < get_irp_n_irgs(); i++) {
262 ir_graph *graph = get_irp_irg (i);
263 ir_entity *ent = get_irg_entity (graph);
265 if ((visibility_external_visible == get_entity_visibility (ent)) ||
266 (stickyness_sticky == get_entity_stickyness (ent))) {
267 eset_insert (_live_graphs, graph);
268 // printf("external visible: "); DDMG(graph);
276 eset *live_graphs = _live_graphs;
277 _live_graphs = eset_create ();
280 fprintf(stdout, "RTA: RUN %i\n", n_runs);
283 /* collect what we have found previously */
284 eset_insert_all (_live_graphs, live_graphs);
287 for (graph = eset_first (live_graphs);
289 graph = eset_next (live_graphs)) {
292 fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
293 DDMEO(get_irg_entity (graph));
296 rerun |= rta_fill_graph (graph);
299 eset_destroy (live_graphs);
304 set_interprocedural_view(old_ip_view); /* cover up our traces */
310 * Count the number of graphs that we have found to be live.
312 static int stats (void)
315 int n_live_graphs = 0;
316 int n_graphs = get_irp_n_irgs();
318 for (i = 0; i < n_graphs; i++) {
319 ir_graph *graph = get_irp_irg(i);
321 if (rta_is_alive_graph (graph)) {
326 return (n_live_graphs);
329 /* remove a graph, part I */
331 We removed the first graph to implement the entity, so we're
332 abstract now. Pretend that it wasn't there at all, and every
333 entity that used to inherit this entity's graph is now abstract.
335 /* Since we *know* that this entity will not be called, this is OK. */
336 static void force_description (ir_entity *ent, ir_entity *addr)
338 int i, n_over = get_entity_n_overwrittenby (ent);
340 set_entity_peculiarity (ent, peculiarity_description);
342 for (i = 0; i < n_over; i ++) {
343 ir_entity *over = get_entity_overwrittenby (ent, i);
345 if (peculiarity_inherited == get_entity_peculiarity (over)) {
346 /* We rely on the fact that cse is performed on the const_code_irg. */
347 ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
349 if (addr == my_addr) {
350 force_description (over, addr);
352 } else if (peculiarity_existent == get_entity_peculiarity (over)) {
353 /* check whether 'over' forces 'inheritance' of *our* graph: */
354 ir_node *f_addr = get_atomic_ent_value (over);
355 ir_entity *impl_ent = get_SymConst_entity (f_addr);
357 assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
358 if (impl_ent == addr) {
359 assert (0 && "gibt's denn sowas");
360 force_description (over, addr);
367 Initialize the static data structures.
369 static void init_tables (void)
374 _live_classes = eset_create ();
375 _live_graphs = eset_create ();
377 if (get_irp_main_irg ()) {
378 eset_insert (_live_graphs, get_irp_main_irg ());
381 /* Find static allocated classes */
382 tp = get_glob_type();
383 n = get_class_n_members(tp);
384 for (i = 0; i < n; ++i) {
385 ir_type *member_type = get_entity_type(get_class_member(tp, i));
386 if (is_Class_type(member_type))
387 eset_insert(_live_classes, member_type);
391 n = get_struct_n_members(tp);
392 for (i = 0; i < n; ++i) {
393 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
394 if (is_Class_type(member_type))
395 eset_insert(_live_classes, member_type);
400 * Initialize the RTA data structures, and perform RTA.
401 * do_verbose If == 1, print statistics, if > 1, chatter about every detail
403 void rta_init (int do_verbose)
407 int rem_vpi = get_visit_pseudo_irgs();
408 set_visit_pseudo_irgs(1);
410 # ifdef DEBUG_libfirm
413 n = get_irp_n_irgs();
414 for (i = 0; i < n; i++) {
415 irg_vrfy (get_irp_irg(i));
419 # endif /* defined DEBUG_libfirm */
421 verbose = do_verbose;
425 n_runs = rta_fill_incremental ();
428 int n_live_graphs = stats ();
430 printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ());
431 printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
432 printf ("RTA: n_runs = %i\n", n_runs);
435 # ifdef DEBUG_libfirm
438 n = get_irp_n_irgs();
439 for (i = 0; i < n; i++) {
440 irg_vrfy (get_irp_irg(i));
444 # endif /* defined DEBUG_libfirm */
446 set_visit_pseudo_irgs(rem_vpi);
450 * walker for all types and entities
452 * Changes the peculiarity of entities that represents
453 * dead graphs to peculiarity_description.
455 static void make_entity_to_description(type_or_ent *tore, void *env) {
456 if (get_kind(tore) == k_entity) {
457 ir_entity *ent = (ir_entity *)tore;
459 if ((is_Method_type(get_entity_type(ent))) &&
460 (get_entity_peculiarity(ent) != peculiarity_description) &&
461 (get_entity_visibility(ent) != visibility_external_allocated) ) {
462 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
463 if (!eset_contains (_live_graphs, irg)) {
464 set_entity_peculiarity(ent, peculiarity_description);
465 set_entity_irg(ent, NULL);
471 /* Delete all graphs that we have found to be dead from the program
472 If verbose == 1, print statistics, if > 1, chatter about every detail
474 void rta_delete_dead_graphs (void)
477 int n_graphs = get_irp_n_irgs ();
478 ir_graph *graph = NULL;
479 int n_dead_graphs = 0;
480 ir_graph **dead_graphs;
482 int rem_vpi = get_visit_pseudo_irgs();
483 set_visit_pseudo_irgs(1);
485 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
487 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
489 for (i = 0; i < n_graphs; i++) {
490 graph = get_irp_irg(i);
492 if (rta_is_alive_graph (graph)) {
493 /* do nothing (except some debugging fprintf`s :-) */
496 ir_entity *ent = get_irg_entity (graph);
497 assert (visibility_external_visible != get_entity_visibility (ent));
500 dead_graphs[n_dead_graphs] = graph;
505 type_walk(make_entity_to_description, NULL, NULL);
506 for (i = 0; i < n_dead_graphs; ++i) {
507 remove_irp_irg (dead_graphs[i]);
511 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
514 set_visit_pseudo_irgs(rem_vpi);
519 /* Clean up the RTA data structures. Call this after calling rta_init */
520 void rta_cleanup (void)
522 # ifdef DEBUG_libfirm
524 for (i = 0; i < get_irp_n_irgs(); i++) {
525 irg_vrfy (get_irp_irg(i));
528 # endif /* defined DEBUG_libfirm */
531 eset_destroy (_live_classes);
532 _live_classes = NULL;
536 eset_destroy (_live_graphs);
541 /* Say whether this class might be instantiated at any point in the program: */
542 int rta_is_alive_class (ir_type *clazz)
544 return (eset_contains (_live_classes, clazz));
547 /* Say whether this graph might be run at any time in the program: */
548 int rta_is_alive_graph (ir_graph *graph)
550 return eset_contains (_live_graphs, graph);
553 /* dump our opinion */
554 void rta_report (void)
558 for (i = 0; i < get_irp_n_types(); ++i) {
559 ir_type *tp = get_irp_type(i);
560 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
561 fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
565 for (i = 0; i < get_irp_n_irgs(); i++) {
566 if (rta_is_alive_graph (get_irp_irg(i))) {
567 fprintf(stdout, "RTA: considered called: graph of ");
568 DDMEO(get_irg_entity (get_irp_irg(i)));
576 * Revision 1.41 2007/03/22 10:39:33 matze
577 * a bunch of fixes to make firm work with NDEBUG and without DEBUG_libfirm
579 * Revision 1.40 2007/01/16 15:45:15 beck
580 * renamed type opcode to ir_opcode
582 * Revision 1.39 2006/12/13 13:15:12 beck
583 * renamed entity -> ir_entity
585 * Revision 1.38 2006/12/12 16:12:05 beck
586 * Fixed missing initialization
588 * Revision 1.37 2006/12/11 15:28:48 matze
589 * - Several warning fixes
590 * - Fixes for compilation without DEBUG_libfirm
591 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
593 * Revision 1.36 2006/06/05 15:58:12 beck
594 * added support for Thread local storage
595 * added more doxygen docu
597 * Revision 1.35 2006/01/13 21:51:59 beck
598 * renamed all types 'type' to 'ir_type'
600 * Revision 1.34 2006/01/02 15:01:16 beck
601 * missing include added
603 * Revision 1.33 2005/11/17 17:26:57 beck
604 * removed bool type and depency from stdbool.h (not C89)
606 * Revision 1.32 2005/01/05 14:24:52 beck
607 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
609 * Revision 1.31 2004/12/21 13:45:14 beck
610 * removed C99 constructs
612 * Revision 1.30 2004/12/02 16:16:11 beck
613 * fixed config.h include
614 * used xmalloc instead of malloc
616 * Revision 1.29 2004/11/11 13:28:08 goetz
617 * made pseudo irg aware
619 * Revision 1.28 2004/11/03 14:47:18 beck
620 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
622 * Revision 1.27 2004/10/21 07:23:34 goetz
625 * Revision 1.26 2004/10/20 14:59:27 liekweg
628 * Revision 1.25 2004/10/18 12:47:08 liekweg
631 * Revision 1.24 2004/09/24 13:59:04 beck
632 * fixed doxygen comments, removed initialization for description entities
634 * Revision 1.23 2004/08/19 16:51:02 goetz
635 * fixed some errors, pushed closer to inteded firm semantics
637 * Revision 1.22 2004/08/13 08:57:15 beyhan
638 * normalized names of functions, enums ...
639 * added suffix as argument to dumpers, removed global variable
640 * removed support for tarval/Const
642 * Revision 1.21 2004/07/08 15:50:56 goetz
645 * Revision 1.20 2004/07/08 11:17:40 goetz
646 * *** empty log message ***
648 * Revision 1.19 2004/07/06 12:30:37 beyhan
649 * new SymConst semantics
651 * Revision 1.18 2004/06/27 21:17:41 liekweg
654 * Revision 1.17 2004/06/25 13:45:13 liekweg
655 * observe stickyness; minor refactoring
657 * Revision 1.16 2004/06/24 06:42:14 goetz
660 * Revision 1.15 2004/06/18 15:47:19 liekweg
661 * minor bug fix (go forward, not backward) --flo
663 * Revision 1.14 2004/06/18 13:12:43 liekweg
664 * final bug fix (calls via consts)
666 * Revision 1.13 2004/06/17 16:34:33 liekweg
669 * Revision 1.12 2004/06/17 16:33:33 liekweg
672 * Revision 1.11 2004/06/17 14:21:13 liekweg
675 * Revision 1.10 2004/06/17 10:31:41 goetz
676 * irscc: bugfix, can now deal with loops not reachable from start
677 * cgana: bugfix, skip_Tuple
680 * Revision 1.9 2004/06/17 08:56:03 liekweg
681 * Fixed typos in comments
683 * Revision 1.8 2004/06/17 08:33:01 liekweg
684 * Added comments; added remove_irg
686 * Revision 1.6 2004/06/14 13:02:03 goetz
689 * Revision 1.5 2004/06/13 15:03:45 liekweg
690 * RTA auf Iterative RTA aufgebohrt --flo
692 * Revision 1.4 2004/06/12 19:35:04 liekweg
693 * Kommentare eingef"ugt --flo
695 * Revision 1.3 2004/06/12 17:09:46 liekweg
696 * RTA works, outedges breaks. "Yay." --flo
698 * Revision 1.2 2004/06/11 18:25:39 liekweg
701 * Revision 1.1 2004/06/11 18:24:18 liekweg