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) {
452 if (get_kind(tore) == k_entity) {
453 ir_entity *ent = (ir_entity *)tore;
455 if ((is_Method_type(get_entity_type(ent))) &&
456 (get_entity_peculiarity(ent) != peculiarity_description) &&
457 (get_entity_visibility(ent) != visibility_external_allocated) ) {
458 ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
459 if (!eset_contains (_live_graphs, irg)) {
460 set_entity_peculiarity(ent, peculiarity_description);
461 set_entity_irg(ent, NULL);
467 /* Delete all graphs that we have found to be dead from the program
468 If verbose == 1, print statistics, if > 1, chatter about every detail
470 void rta_delete_dead_graphs (void)
473 int n_graphs = get_irp_n_irgs ();
474 ir_graph *graph = NULL;
475 int n_dead_graphs = 0;
476 ir_graph **dead_graphs;
478 int rem_vpi = get_visit_pseudo_irgs();
479 set_visit_pseudo_irgs(1);
481 if (!get_optimize() || !get_opt_dead_method_elimination()) return;
483 dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
485 for (i = 0; i < n_graphs; i++) {
486 graph = get_irp_irg(i);
488 if (rta_is_alive_graph (graph)) {
489 /* do nothing (except some debugging fprintf`s :-) */
492 ir_entity *ent = get_irg_entity (graph);
493 assert (visibility_external_visible != get_entity_visibility (ent));
496 dead_graphs[n_dead_graphs] = graph;
501 type_walk(make_entity_to_description, NULL, NULL);
502 for (i = 0; i < n_dead_graphs; ++i) {
503 remove_irp_irg (dead_graphs[i]);
507 printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
510 set_visit_pseudo_irgs(rem_vpi);
515 /* Clean up the RTA data structures. Call this after calling rta_init */
516 void rta_cleanup (void)
518 # ifdef DEBUG_libfirm
520 for (i = 0; i < get_irp_n_irgs(); i++) {
521 irg_vrfy (get_irp_irg(i));
524 # endif /* defined DEBUG_libfirm */
527 eset_destroy (_live_classes);
528 _live_classes = NULL;
532 eset_destroy (_live_graphs);
537 /* Say whether this class might be instantiated at any point in the program: */
538 int rta_is_alive_class (ir_type *clazz)
540 return (eset_contains (_live_classes, clazz));
543 /* Say whether this graph might be run at any time in the program: */
544 int rta_is_alive_graph (ir_graph *graph)
546 return eset_contains (_live_graphs, graph);
549 /* dump our opinion */
550 void rta_report (void)
554 for (i = 0; i < get_irp_n_types(); ++i) {
555 ir_type *tp = get_irp_type(i);
556 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
557 ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp);
561 for (i = 0; i < get_irp_n_irgs(); i++) {
562 if (rta_is_alive_graph (get_irp_irg(i))) {
563 ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i));
571 * Revision 1.41 2007/03/22 10:39:33 matze
572 * a bunch of fixes to make firm work with NDEBUG and without DEBUG_libfirm
574 * Revision 1.40 2007/01/16 15:45:15 beck
575 * renamed type opcode to ir_opcode
577 * Revision 1.39 2006/12/13 13:15:12 beck
578 * renamed entity -> ir_entity
580 * Revision 1.38 2006/12/12 16:12:05 beck
581 * Fixed missing initialization
583 * Revision 1.37 2006/12/11 15:28:48 matze
584 * - Several warning fixes
585 * - Fixes for compilation without DEBUG_libfirm
586 * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
588 * Revision 1.36 2006/06/05 15:58:12 beck
589 * added support for Thread local storage
590 * added more doxygen docu
592 * Revision 1.35 2006/01/13 21:51:59 beck
593 * renamed all types 'type' to 'ir_type'
595 * Revision 1.34 2006/01/02 15:01:16 beck
596 * missing include added
598 * Revision 1.33 2005/11/17 17:26:57 beck
599 * removed bool type and depency from stdbool.h (not C89)
601 * Revision 1.32 2005/01/05 14:24:52 beck
602 * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
604 * Revision 1.31 2004/12/21 13:45:14 beck
605 * removed C99 constructs
607 * Revision 1.30 2004/12/02 16:16:11 beck
608 * fixed config.h include
609 * used xmalloc instead of malloc
611 * Revision 1.29 2004/11/11 13:28:08 goetz
612 * made pseudo irg aware
614 * Revision 1.28 2004/11/03 14:47:18 beck
615 * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
617 * Revision 1.27 2004/10/21 07:23:34 goetz
620 * Revision 1.26 2004/10/20 14:59:27 liekweg
623 * Revision 1.25 2004/10/18 12:47:08 liekweg
626 * Revision 1.24 2004/09/24 13:59:04 beck
627 * fixed doxygen comments, removed initialization for description entities
629 * Revision 1.23 2004/08/19 16:51:02 goetz
630 * fixed some errors, pushed closer to inteded firm semantics
632 * Revision 1.22 2004/08/13 08:57:15 beyhan
633 * normalized names of functions, enums ...
634 * added suffix as argument to dumpers, removed global variable
635 * removed support for tarval/Const
637 * Revision 1.21 2004/07/08 15:50:56 goetz
640 * Revision 1.20 2004/07/08 11:17:40 goetz
641 * *** empty log message ***
643 * Revision 1.19 2004/07/06 12:30:37 beyhan
644 * new SymConst semantics
646 * Revision 1.18 2004/06/27 21:17:41 liekweg
649 * Revision 1.17 2004/06/25 13:45:13 liekweg
650 * observe stickyness; minor refactoring
652 * Revision 1.16 2004/06/24 06:42:14 goetz
655 * Revision 1.15 2004/06/18 15:47:19 liekweg
656 * minor bug fix (go forward, not backward) --flo
658 * Revision 1.14 2004/06/18 13:12:43 liekweg
659 * final bug fix (calls via consts)
661 * Revision 1.13 2004/06/17 16:34:33 liekweg
664 * Revision 1.12 2004/06/17 16:33:33 liekweg
667 * Revision 1.11 2004/06/17 14:21:13 liekweg
670 * Revision 1.10 2004/06/17 10:31:41 goetz
671 * irscc: bugfix, can now deal with loops not reachable from start
672 * cgana: bugfix, skip_Tuple
675 * Revision 1.9 2004/06/17 08:56:03 liekweg
676 * Fixed typos in comments
678 * Revision 1.8 2004/06/17 08:33:01 liekweg
679 * Added comments; added remove_irg
681 * Revision 1.6 2004/06/14 13:02:03 goetz
684 * Revision 1.5 2004/06/13 15:03:45 liekweg
685 * RTA auf Iterative RTA aufgebohrt --flo
687 * Revision 1.4 2004/06/12 19:35:04 liekweg
688 * Kommentare eingef"ugt --flo
690 * Revision 1.3 2004/06/12 17:09:46 liekweg
691 * RTA works, outedges breaks. "Yay." --flo
693 * Revision 1.2 2004/06/11 18:25:39 liekweg
696 * Revision 1.1 2004/06/11 18:24:18 liekweg