X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Frta.c;h=999247457a69f0ba4616d2fc142bf2d4b2eb9f8c;hb=46e776e9bca189a6cf06eef7634a162e9b41d386;hp=80fcc435616e18e3d5d3cc1866030173aa4bd24c;hpb=e1bd055d9e85a45dd762c1a7b2b8130dc39f515e;p=libfirm diff --git a/ir/ana/rta.c b/ir/ana/rta.c index 80fcc4356..999247457 100644 --- a/ir/ana/rta.c +++ b/ir/ana/rta.c @@ -7,19 +7,14 @@ * Author: Florian * Modified by: * Created: 09.06.2002 - * CVS-ID: $$ + * CVS-ID: $Id$ * Copyright: (c) 1999-2004 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. */ -/** - * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es - * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden - * bestimmt. - */ #ifdef HAVE_CONFIG_H -# include +# include "config.h" #endif #include "rta.h" @@ -27,16 +22,24 @@ #include #include "irnode_t.h" -#include "irprog.h" +#include "irprog_t.h" +#include "irgraph_t.h" #include "eset.h" #include "irgwalk.h" #include "irgmod.h" +#include "typewalk.h" #include "irvrfy.h" #include "trvrfy.h" -# define TRUE 1 -# define FALSE 0 +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* not defined TRUE */ + +/* flags */ +static int verbose = 0; + /* base data */ static eset *_live_classes = NULL; @@ -44,39 +47,58 @@ static eset *_live_classes = NULL; /* cache computed results */ static eset *_live_graphs = NULL; -static int whole_world = 0; -static int verbose = 0; - /** 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) { - ir_graph *graph = get_entity_irg ((entity*) method); +#if 0 + 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); } } + /* GL this is not valid in our remove irg algorithm ... which we removed by now ... */ + assert(get_entity_peculiarity(method) == peculiarity_description + || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)))); + /* we *must* always return a graph != NULL, *except* when we're used inside remove_irg or force_description */ /* assert (graph && "no graph"); */ return (graph); +#else + ir_graph *graph = NULL; + + if (get_entity_peculiarity(method) != peculiarity_description) + graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))); + + return graph; +#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_ent (graph)); + DDMEO(get_irg_entity (graph)); } eset_insert (_live_graphs, graph); @@ -86,13 +108,20 @@ 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); - } + if (verbose > 1) { + fprintf(stdout, "RTA: new class: "); + DDMT(clazz); + } eset_insert (_live_classes, clazz); return (TRUE); @@ -101,12 +130,12 @@ static int add_class (type *clazz) return (FALSE); } -/** - Given an entity, add all implementing graphs that belong to live classes to _live_graphs. - - Iff additions occurred, return TRUE, else FALSE. +/** Given an entity, add all implementing graphs that belong to live classes + * to _live_graphs. + * + * 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); @@ -129,51 +158,65 @@ 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); } return (change); } -/** - Enter all method accesses and all class allocations into - our tables. - - Set *(int*)env to true iff (possibly) new graphs have been found. -*/ +/** Enter all method accesses and all class allocations into + * our tables. + * + * Set *(int*)env to true iff (possibly) new graphs have been found. + */ static void rta_act (ir_node *node, void *env) { int *change = (int*) env; - 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); - if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */ + /* CALL SEL */ + if (iro_Sel == get_irn_opcode (ptr)) { ent = get_Sel_entity (ptr); - *change = add_implementing_graphs (ent); - } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */ - ent = get_tarval_entity (get_Const_tarval (ptr)); - ir_graph *graph = get_entity_irg (ent); - /* don't use get_implementing_graph on a Const! */ - if (graph) { - *change = add_graph (graph); + *change |= add_implementing_graphs (ent); + + /* 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); + 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."); */ } else { - /* it's an externally allocated thing. */ + /* other symconst. */ + assert(0 && "This SymConst can not be an address for a method call."); } - } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */ - /* If this SymConst refers to a method the method is external_visible - and therefore must be considered live anyways. */ - /* assert (ent && "couldn't determine entity of call to symConst"); */ + + /* 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); + *change |= add_class (type); } } @@ -184,27 +227,20 @@ 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 (get_irg_end (graph), rta_act, NULL, &change); - - return (change); + irg_walk_graph (graph, rta_act, NULL, &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 -*/ +/** Traverse all graphs to collect method accesses and object allocations. + */ static int rta_fill_incremental (void) { int i; int n_runs = 0; int rerun = TRUE; - int old_ip_view = interprocedural_view; + int old_ip_view = get_interprocedural_view(); - interprocedural_view = 0; /* save this for later */ + set_interprocedural_view(0); /* save this for later */ /* init_tables has added main_irg to _live_graphs */ @@ -213,12 +249,12 @@ 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 (((!whole_world) && - (visibility_external_visible == get_entity_visibility (ent))) || + if ((visibility_external_visible == get_entity_visibility (ent)) || (stickyness_sticky == get_entity_stickyness (ent))) { eset_insert (_live_graphs, graph); + // printf("external visible: "); DDMG(graph); } } @@ -237,14 +273,13 @@ static int rta_fill_incremental (void) eset_insert_all (_live_graphs, live_graphs); rerun = FALSE; - for (graph = eset_first (live_graphs); graph; graph = eset_next (live_graphs)) { if (verbose > 1) { fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs); - DDMEO(get_irg_ent (graph)); + DDMEO(get_irg_entity (graph)); } rerun |= rta_fill_graph (graph); @@ -255,14 +290,14 @@ static int rta_fill_incremental (void) n_runs ++; } - interprocedural_view = old_ip_view; /* cover up our traces */ + set_interprocedural_view(old_ip_view); /* cover up our traces */ 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; @@ -287,19 +322,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 = - tarval_to_entity(get_Const_tarval(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); @@ -307,9 +341,9 @@ 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 = tarval_to_entity (get_Const_tarval (f_addr)); + ir_entity *impl_ent = get_SymConst_entity (f_addr); - assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs"); + assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs"); if (impl_ent == addr) { assert (0 && "gibt's denn sowas"); force_description (over, addr); @@ -318,82 +352,61 @@ static void force_description (entity *ent, entity *addr) } } -/* remove a graph, part II */ -/* - Note: get_implementing_graph is not well defined here (graph->ent - could overwrite more than one superclass implementation (graph). - Since we *know* that this entity will not be called, this is OK. -*/ -static void remove_irg (ir_graph *graph) -{ - entity *ent = get_irg_entity (graph); - peculiarity pec = get_entity_peculiarity (ent); - - /* DDMEO (get_irg_ent(graph)); */ - - /* delete the ir_graph data */ - set_entity_peculiarity (ent, peculiarity_description); - remove_irp_irg (graph); - /* remove_irp_irg also removes the entities' reference to the graph */ - /* - if (NULL != get_entity_irg (ent)) { - set_entity_irg (ent, NULL); - } - */ - set_entity_peculiarity (ent, pec); - - /* find the implementation (graph) from *some* superclass: */ - graph = get_implementing_graph (ent); - - if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */ - /* nothing to inherit! pretend we're abstract */ - force_description (ent, ent); - } else { - /* pretend that we inherit the implementation (graph) from some superclass: */ - set_entity_peculiarity (ent, peculiarity_inherited); - - exchange (get_atomic_ent_value (ent), - get_atomic_ent_value (get_irg_ent(graph))); - } -} - /** - Initialise the static data structures. + Initialize the static data structures. */ static void init_tables (void) { - _live_classes = eset_create (); + ir_type *tp; + int i, n; - _live_graphs = eset_create (); + _live_classes = eset_create (); + _live_graphs = eset_create (); if (get_irp_main_irg ()) { eset_insert (_live_graphs, get_irp_main_irg ()); } - /* - if (get_glob_type ()) { - eset_insert (_live_classes, get_glob_type ()); + /* Find static allocated classes */ + 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. - @param do_verbose If == 1, print statistics, if > 1, chatter about every detail - @param do_whole_world Iff != 0, assume whole-world -*/ -void rta_init (int do_verbose, int do_whole_world) +/* + * 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) { int n_runs = 0; + int rem_vpi = get_visit_pseudo_irgs(); + 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 */ - whole_world = do_whole_world; verbose = do_verbose; init_tables (); @@ -403,20 +416,45 @@ void rta_init (int do_verbose, int do_whole_world) if (verbose) { int n_live_graphs = stats (); - if (whole_world) { - printf ("RTA: whole-world assumption\n"); - } printf ("RTA: n_graphs = %i\n", get_irp_n_irgs ()); printf ("RTA: n_live_graphs = %i\n", n_live_graphs); printf ("RTA: n_runs = %i\n", n_runs); } # 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); +} + +/** + * walker for all types and entities + * + * Changes the peculiarity of entities that represents + * dead graphs to peculiarity_description. + */ +static void make_entity_to_description(type_or_ent *tore, void *env) { + if (get_kind(tore) == k_entity) { + 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) ) { + 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); + } + } + } } /* Delete all graphs that we have found to be dead from the program @@ -428,10 +466,14 @@ 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; - eset *dead_graphs = eset_create (); + dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs()); for (i = 0; i < n_graphs; i++) { graph = get_irp_irg(i); @@ -440,32 +482,27 @@ void rta_delete_dead_graphs (void) /* do nothing (except some debugging fprintf`s :-) */ } else { # ifdef DEBUG_libfirm - entity *ent = get_irg_entity (graph); - assert (whole_world || - (visibility_external_visible != get_entity_visibility (ent))); + ir_entity *ent = get_irg_entity (graph); + assert (visibility_external_visible != get_entity_visibility (ent)); # endif /* defined DEBUG_libfirm */ + dead_graphs[n_dead_graphs] = graph; n_dead_graphs ++; - eset_insert (dead_graphs, graph); } } - /* now delete the graphs. */ - for (graph = eset_first (dead_graphs); - graph; - graph = (ir_graph*) eset_next (dead_graphs)) { - - if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) { - fprintf(stdout, "RTA: removing graph of "); - DDMEO(get_irg_ent (graph)); - } - - remove_irg (graph); + type_walk(make_entity_to_description, NULL, NULL); + for (i = 0; i < n_dead_graphs; ++i) { + remove_irp_irg (dead_graphs[i]); } if (verbose) { printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs); } + + set_visit_pseudo_irgs(rem_vpi); + + free(dead_graphs); } /* Clean up the RTA data structures. Call this after calling rta_init */ @@ -491,7 +528,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)); } @@ -499,11 +536,7 @@ int rta_is_alive_class (type *clazz) /* Say whether this graph might be run at any time in the program: */ int rta_is_alive_graph (ir_graph *graph) { - if (eset_contains (_live_graphs, graph)) { - return (TRUE); - } - - return (FALSE); + return eset_contains (_live_graphs, graph); } /* dump our opinion */ @@ -512,8 +545,8 @@ 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)) { + ir_type *tp = get_irp_type(i); + if (is_Class_type(tp) && rta_is_alive_class(tp)) { fprintf(stdout, "RTA: considered allocated: "); DDMT(tp); } } @@ -521,7 +554,7 @@ void rta_report (void) 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_ent (get_irp_irg(i))); + DDMEO(get_irg_entity (get_irp_irg(i))); } } } @@ -529,6 +562,78 @@ void rta_report (void) /* * $Log$ + * 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 + * + * Revision 1.28 2004/11/03 14:47:18 beck + * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions + * + * Revision 1.27 2004/10/21 07:23:34 goetz + * comments + * + * Revision 1.26 2004/10/20 14:59:27 liekweg + * Removed ecg + * + * Revision 1.25 2004/10/18 12:47:08 liekweg + * avoid warning + * + * Revision 1.24 2004/09/24 13:59:04 beck + * fixed doxygen comments, removed initialization for description entities + * + * Revision 1.23 2004/08/19 16:51:02 goetz + * fixed some errors, pushed closer to inteded firm semantics + * + * Revision 1.22 2004/08/13 08:57:15 beyhan + * normalized names of functions, enums ... + * added suffix as argument to dumpers, removed global variable + * removed support for tarval/Const + * + * Revision 1.21 2004/07/08 15:50:56 goetz + * firmstat added + * + * Revision 1.20 2004/07/08 11:17:40 goetz + * *** empty log message *** + * + * Revision 1.19 2004/07/06 12:30:37 beyhan + * new SymConst semantics + * + * Revision 1.18 2004/06/27 21:17:41 liekweg + * Added comment + * * Revision 1.17 2004/06/25 13:45:13 liekweg * observe stickyness; minor refactoring *