X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Frta.c;h=85084e4e05294e759087115a9f7b00a757771724;hb=34ba4cf5428e344224af2e4c31b2120cdd2fd12e;hp=5a844198d913f73117860ad13bc0775275ae6744;hpb=3aca2e53c994d837ce853e7ce65a8830ea6d542a;p=libfirm diff --git a/ir/ana/rta.c b/ir/ana/rta.c index 5a844198d..85084e4e0 100644 --- a/ir/ana/rta.c +++ b/ir/ana/rta.c @@ -1,20 +1,31 @@ -/* -*- c -*- */ - /* - * Project: libFIRM - * File name: ir/ana/rta.c - * Purpose: Interprocedural analysis to improve the call graph estimate. - * Author: Florian - * Modified by: - * Created: 09.06.2002 - * CVS-ID: $Id$ - * Copyright: (c) 1999-2004 Universität Karlsruhe - * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ - +/** + * @file + * @brief Interprocedural analysis to improve the call graph estimate. + * @author Florian + * @version 09.06.2002 + * @version $Id$ + */ #ifdef HAVE_CONFIG_H -# include +# include "config.h" #endif #include "rta.h" @@ -29,7 +40,7 @@ #include "irgwalk.h" #include "irgmod.h" #include "irvrfy.h" -#include "trvrfy.h" +#include "irprintf.h" # ifndef TRUE # define TRUE 1 @@ -49,19 +60,19 @@ static eset *_live_graphs = NULL; /** Given a method, find the firm graph that implements that method. */ -static ir_graph *get_implementing_graph (entity *method) +static ir_graph *get_implementing_graph (ir_entity *method) { #if 0 - ir_graph *graph = get_entity_irg ((entity*) method); + ir_graph *graph = get_entity_irg ((ir_entity*) method); /* Search upwards in the overwrites graph. */ /* GL: this will not work for multiple inheritance */ if (NULL == graph) { int i; - int n_over = get_entity_n_overwrites ((entity*) method); + int n_over = get_entity_n_overwrites ((ir_entity*) method); for (i = 0; (NULL == graph) && (i < n_over); i ++) { - entity *over = get_entity_overwrites ((entity*) method, i); + ir_entity *over = get_entity_overwrites ((ir_entity*) method, i); graph = get_implementing_graph (over); } } @@ -85,12 +96,18 @@ static ir_graph *get_implementing_graph (entity *method) #endif } +/** + * Add a graph to the set of live graphs. + * + * @param graph the graph to add + * @return non-zero if the graph was added, zero + * if it was already in the live set + */ static int add_graph (ir_graph *graph) { if (!eset_contains (_live_graphs, graph)) { if (verbose > 1) { - fprintf(stdout, "RTA: new graph of "); - DDMEO(get_irg_entity (graph)); + ir_fprintf(stdout, "RTA: new graph of %+F\n", graph); } eset_insert (_live_graphs, graph); @@ -100,12 +117,18 @@ static int add_graph (ir_graph *graph) return (FALSE); } -static int add_class (type *clazz) +/** + * Add a class to the set of live classes. + * + * @param clazz the class to add + * @return non-zero if the graph was added, zero + * if it was already in the live set + */ +static int add_class (ir_type *clazz) { if (!eset_contains (_live_classes, clazz)) { if (verbose > 1) { - fprintf(stdout, "RTA: new class: "); - DDMT(clazz); + ir_fprintf(stdout, "RTA: new class: %+F\n", clazz); } eset_insert (_live_classes, clazz); @@ -120,7 +143,7 @@ static int add_class (type *clazz) * * Iff additions occurred, return TRUE, else FALSE. */ -static int add_implementing_graphs (entity *method) +static int add_implementing_graphs (ir_entity *method) { int i; int n_over = get_entity_n_overwrittenby (method); @@ -132,8 +155,7 @@ static int add_implementing_graphs (entity *method) } if (verbose > 1) { - fprintf(stdout, "RTA: new call to "); - DDMEO(method); + ir_fprintf(stdout, "RTA: new call to %+F\n", method); } if (rta_is_alive_class (get_entity_owner (method))) { @@ -143,7 +165,7 @@ static int add_implementing_graphs (entity *method) } for (i = 0; i < n_over; i ++) { - entity *over = get_entity_overwrittenby (method, i); + ir_entity *over = get_entity_overwrittenby (method, i); change |= add_implementing_graphs (over); } @@ -158,11 +180,10 @@ static int add_implementing_graphs (entity *method) static void rta_act (ir_node *node, void *env) { int *change = (int*) env; - - opcode op = get_irn_opcode (node); + ir_opcode op = get_irn_opcode (node); if (iro_Call == op) { /* CALL */ - entity *ent = NULL; + ir_entity *ent = NULL; ir_node *ptr = get_Call_ptr (node); @@ -174,18 +195,20 @@ static void rta_act (ir_node *node, void *env) /* CALL SYMCONST */ } else if (iro_SymConst == get_irn_opcode (ptr)) { if (get_SymConst_kind(ptr) == symconst_addr_ent) { + ir_graph *graph; + ent = get_SymConst_entity (ptr); - ir_graph *graph = get_entity_irg (ent); + graph = get_entity_irg (ent); if (graph) { *change |= add_graph (graph); } else { /* it's an external allocated thing. */ } } else if (get_SymConst_kind(ptr) == symconst_addr_name) { - /* Entities of kind addr_name may not be allocated in this compilation unit. - If so, the frontend built faulty Firm. So just ignore. */ - /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch")) - assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */ + /* Entities of kind addr_name may not be allocated in this compilation unit. + If so, the frontend built faulty Firm. So just ignore. */ + /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch")) + assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */ } else { /* other symconst. */ assert(0 && "This SymConst can not be an address for a method call."); @@ -193,12 +216,11 @@ static void rta_act (ir_node *node, void *env) /* STRANGE */ } else { - DDMN(ptr); assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!"); } } else if (iro_Alloc == op) { /* ALLOC */ - type *type = get_Alloc_type (node); + ir_type *type = get_Alloc_type (node); *change |= add_class (type); } @@ -211,26 +233,22 @@ static void rta_act (ir_node *node, void *env) static int rta_fill_graph (ir_graph* graph) { int change = FALSE; - - current_ir_graph = graph; - irg_walk_graph (graph, rta_act, NULL, &change); - - return (change); + return change; } /** Traverse all graphs to collect method accesses and object allocations. - * - * @param rerun Whether to rely on is_alive in a second run */ static int rta_fill_incremental (void) { int i; int n_runs = 0; int rerun = TRUE; +#ifdef INTERPROCEDURAL_VIEW int old_ip_view = get_interprocedural_view(); - set_interprocedural_view(false); /* save this for later */ + set_interprocedural_view(0); /* save this for later */ +#endif /* init_tables has added main_irg to _live_graphs */ @@ -239,7 +257,7 @@ static int rta_fill_incremental (void) for (i = 0; i < get_irp_n_irgs(); i++) { ir_graph *graph = get_irp_irg (i); - entity *ent = get_irg_entity (graph); + ir_entity *ent = get_irg_entity (graph); if ((visibility_external_visible == get_entity_visibility (ent)) || (stickyness_sticky == get_entity_stickyness (ent))) { @@ -268,8 +286,8 @@ static int rta_fill_incremental (void) graph = eset_next (live_graphs)) { if (verbose > 1) { - fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs); - DDMEO(get_irg_entity (graph)); + ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs, + graph); } rerun |= rta_fill_graph (graph); @@ -280,14 +298,16 @@ static int rta_fill_incremental (void) n_runs ++; } +#ifdef INTERPROCEDURAL_VIEW set_interprocedural_view(old_ip_view); /* cover up our traces */ +#endif return (n_runs); } -/* - Count the number of graphs that we have found to be live. -*/ +/** + * Count the number of graphs that we have found to be live. + */ static int stats (void) { int i; @@ -312,18 +332,18 @@ static int stats (void) entity that used to inherit this entity's graph is now abstract. */ /* Since we *know* that this entity will not be called, this is OK. */ -static void force_description (entity *ent, entity *addr) +static void force_description (ir_entity *ent, ir_entity *addr) { int i, n_over = get_entity_n_overwrittenby (ent); set_entity_peculiarity (ent, peculiarity_description); for (i = 0; i < n_over; i ++) { - entity *over = get_entity_overwrittenby (ent, i); + ir_entity *over = get_entity_overwrittenby (ent, i); if (peculiarity_inherited == get_entity_peculiarity (over)) { /* We rely on the fact that cse is performed on the const_code_irg. */ - entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over)); + ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over)); if (addr == my_addr) { force_description (over, addr); @@ -331,7 +351,7 @@ static void force_description (entity *ent, entity *addr) } else if (peculiarity_existent == get_entity_peculiarity (over)) { /* check whether 'over' forces 'inheritance' of *our* graph: */ ir_node *f_addr = get_atomic_ent_value (over); - entity *impl_ent = get_SymConst_entity (f_addr); + ir_entity *impl_ent = get_SymConst_entity (f_addr); assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs"); if (impl_ent == addr) { @@ -343,11 +363,12 @@ static void force_description (entity *ent, entity *addr) } /** - Initialise the static data structures. + Initialize the static data structures. */ static void init_tables (void) { - int i, n_globs = get_class_n_members(get_glob_type()); + ir_type *tp; + int i, n; _live_classes = eset_create (); _live_graphs = eset_create (); @@ -357,15 +378,25 @@ static void init_tables (void) } /* Find static allocated classes */ - for (i = 0; i < n_globs; ++i) { - type *member_type = get_entity_type(get_class_member(get_glob_type(), i)); - if (is_class_type(member_type)) + tp = get_glob_type(); + n = get_class_n_members(tp); + for (i = 0; i < n; ++i) { + ir_type *member_type = get_entity_type(get_class_member(tp, i)); + if (is_Class_type(member_type)) + eset_insert(_live_classes, member_type); + } + + tp = get_tls_type(); + n = get_struct_n_members(tp); + for (i = 0; i < n; ++i) { + ir_type *member_type = get_entity_type(get_struct_member(tp, i)); + if (is_Class_type(member_type)) eset_insert(_live_classes, member_type); } } /* - * Initialise the RTA data structures, and perform RTA. + * Initialize the RTA data structures, and perform RTA. * do_verbose If == 1, print statistics, if > 1, chatter about every detail */ void rta_init (int do_verbose) @@ -376,11 +407,14 @@ void rta_init (int do_verbose) set_visit_pseudo_irgs(1); # ifdef DEBUG_libfirm - int i; - for (i = 0; i < get_irp_n_irgs(); i++) { - irg_vrfy (get_irp_irg(i)); + { + int i, n; + n = get_irp_n_irgs(); + for (i = 0; i < n; i++) { + irg_vrfy (get_irp_irg(i)); + } + tr_vrfy (); } - tr_vrfy (); # endif /* defined DEBUG_libfirm */ verbose = do_verbose; @@ -398,10 +432,14 @@ void rta_init (int do_verbose) } # ifdef DEBUG_libfirm - for (i = 0; i < get_irp_n_irgs(); i++) { - irg_vrfy (get_irp_irg(i)); + { + int i, n; + n = get_irp_n_irgs(); + for (i = 0; i < n; i++) { + irg_vrfy (get_irp_irg(i)); + } + tr_vrfy (); } - tr_vrfy (); # endif /* defined DEBUG_libfirm */ set_visit_pseudo_irgs(rem_vpi); @@ -414,16 +452,17 @@ void rta_init (int do_verbose) * dead graphs to peculiarity_description. */ static void make_entity_to_description(type_or_ent *tore, void *env) { + (void) env; if (get_kind(tore) == k_entity) { - entity *ent = (entity *)tore; + ir_entity *ent = (ir_entity *)tore; - if ((is_method_type(get_entity_type(ent))) && - (get_entity_peculiarity(ent) != peculiarity_description) && - (get_entity_visibility(ent) != visibility_external_allocated) ) { + if ((is_Method_type(get_entity_type(ent))) && + (get_entity_peculiarity(ent) != peculiarity_description) && + (get_entity_visibility(ent) != visibility_external_allocated) ) { ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent))); if (!eset_contains (_live_graphs, irg)) { - set_entity_peculiarity(ent, peculiarity_description); - set_entity_irg(ent, NULL); + set_entity_peculiarity(ent, peculiarity_description); + set_entity_irg(ent, NULL); } } } @@ -438,13 +477,12 @@ void rta_delete_dead_graphs (void) int n_graphs = get_irp_n_irgs (); ir_graph *graph = NULL; int n_dead_graphs = 0; + ir_graph **dead_graphs; int rem_vpi = get_visit_pseudo_irgs(); set_visit_pseudo_irgs(1); - if (!get_optimize() || !get_opt_dead_method_elimination()) return; - - ir_graph *dead_graphs[get_irp_n_irgs()]; + dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs()); for (i = 0; i < n_graphs; i++) { graph = get_irp_irg(i); @@ -452,10 +490,10 @@ void rta_delete_dead_graphs (void) if (rta_is_alive_graph (graph)) { /* do nothing (except some debugging fprintf`s :-) */ } else { -# ifdef DEBUG_libfirm - entity *ent = get_irg_entity (graph); +#ifndef NDEBUG + ir_entity *ent = get_irg_entity (graph); assert (visibility_external_visible != get_entity_visibility (ent)); -# endif /* defined DEBUG_libfirm */ +#endif dead_graphs[n_dead_graphs] = graph; n_dead_graphs ++; @@ -472,6 +510,8 @@ void rta_delete_dead_graphs (void) } set_visit_pseudo_irgs(rem_vpi); + + free(dead_graphs); } /* Clean up the RTA data structures. Call this after calling rta_init */ @@ -497,7 +537,7 @@ void rta_cleanup (void) } /* Say whether this class might be instantiated at any point in the program: */ -int rta_is_alive_class (type *clazz) +int rta_is_alive_class (ir_type *clazz) { return (eset_contains (_live_classes, clazz)); } @@ -514,16 +554,15 @@ void rta_report (void) int i; for (i = 0; i < get_irp_n_types(); ++i) { - type *tp = get_irp_type(i); - if (is_class_type(tp) && rta_is_alive_class(tp)) { - fprintf(stdout, "RTA: considered allocated: "); DDMT(tp); + ir_type *tp = get_irp_type(i); + if (is_Class_type(tp) && rta_is_alive_class(tp)) { + ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp); } } for (i = 0; i < get_irp_n_irgs(); i++) { if (rta_is_alive_graph (get_irp_irg(i))) { - fprintf(stdout, "RTA: considered called: graph of "); - DDMEO(get_irg_entity (get_irp_irg(i))); + ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i)); } } } @@ -531,6 +570,46 @@ void rta_report (void) /* * $Log$ + * Revision 1.41 2007/03/22 10:39:33 matze + * a bunch of fixes to make firm work with NDEBUG and without DEBUG_libfirm + * + * Revision 1.40 2007/01/16 15:45:15 beck + * renamed type opcode to ir_opcode + * + * Revision 1.39 2006/12/13 13:15:12 beck + * renamed entity -> ir_entity + * + * Revision 1.38 2006/12/12 16:12:05 beck + * Fixed missing initialization + * + * Revision 1.37 2006/12/11 15:28:48 matze + * - Several warning fixes + * - Fixes for compilation without DEBUG_libfirm + * - Fixed for compilation without WITH_LIBCORE (but it's still broken) + * + * Revision 1.36 2006/06/05 15:58:12 beck + * added support for Thread local storage + * added more doxygen docu + * + * Revision 1.35 2006/01/13 21:51:59 beck + * renamed all types 'type' to 'ir_type' + * + * Revision 1.34 2006/01/02 15:01:16 beck + * missing include added + * + * Revision 1.33 2005/11/17 17:26:57 beck + * removed bool type and depency from stdbool.h (not C89) + * + * Revision 1.32 2005/01/05 14:24:52 beck + * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend + * + * Revision 1.31 2004/12/21 13:45:14 beck + * removed C99 constructs + * + * Revision 1.30 2004/12/02 16:16:11 beck + * fixed config.h include + * used xmalloc instead of malloc + * * Revision 1.29 2004/11/11 13:28:08 goetz * made pseudo irg aware *