X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Frta.c;h=ea0ae3fb6c0e2eb22edbb0a1a0d1a131462cf958;hb=65daf5bc390b02d68581f4c431dbdbfaae11b88f;hp=bbc9da2ccf409a3807cb73abadfea5750970be25;hpb=e07b61c6ed5d198a484761f8a40a4f26520d964d;p=libfirm diff --git a/ir/ana/rta.c b/ir/ana/rta.c index bbc9da2cc..ea0ae3fb6 100644 --- a/ir/ana/rta.c +++ b/ir/ana/rta.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -20,81 +20,37 @@ /** * @file * @brief Interprocedural analysis to improve the call graph estimate. - * @author Florian + * @author Florian Liekweg * @version 09.06.2002 * @version $Id$ */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif +#include "config.h" #include "rta.h" #include +#include #include "irnode_t.h" #include "irprog_t.h" #include "irgraph_t.h" -#include "eset.h" +#include "pset_new.h" #include "irgwalk.h" #include "irgmod.h" -#include "irvrfy.h" +#include "irverify.h" #include "irprintf.h" +#include "debug.h" +#include "error.h" -# ifndef TRUE -# define TRUE 1 -# define FALSE 0 -# endif /* not defined TRUE */ - -/* flags */ -static int verbose = 0; - +/** The debug handle. */ +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) /* base data */ -static eset *_live_classes = NULL; +static pset_new_t *_live_classes = NULL; /* cache computed results */ -static eset *_live_graphs = NULL; - -/** - Given a method, find the firm graph that implements that method. -*/ -static ir_graph *get_implementing_graph (ir_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 ((ir_entity*) method); - - for (i = 0; (NULL == graph) && (i < n_over); 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 -} +static pset_new_t *_live_graphs = NULL; /** * Add a graph to the set of live graphs. @@ -103,18 +59,16 @@ static ir_graph *get_implementing_graph (ir_entity *method) * @return non-zero if the graph was added, zero * if it was already in the live set */ -static int add_graph (ir_graph *graph) +static bool add_graph(ir_graph *graph) { - if (!eset_contains (_live_graphs, graph)) { - if (verbose > 1) { - ir_fprintf(stdout, "RTA: new graph of %+F\n", graph); - } + if (!pset_new_contains(_live_graphs, graph)) { + DB((dbg, LEVEL_2, "RTA: new graph of %+F\n", graph)); - eset_insert (_live_graphs, graph); - return (TRUE); - } + pset_new_insert(_live_graphs, graph); + return true; + } - return (FALSE); + return false; } /** @@ -124,206 +78,178 @@ static int add_graph (ir_graph *graph) * @return non-zero if the graph was added, zero * if it was already in the live set */ -static int add_class (ir_type *clazz) +static bool add_class(ir_type *clazz) { - if (!eset_contains (_live_classes, clazz)) { - if (verbose > 1) { - ir_fprintf(stdout, "RTA: new class: %+F\n", clazz); - } + if (!pset_new_contains(_live_classes, clazz)) { + DB((dbg, LEVEL_2, "RTA: new class: %+F\n", clazz)); - eset_insert (_live_classes, clazz); - return (TRUE); - } + pset_new_insert(_live_classes, clazz); + return true; + } - return (FALSE); + return false; } /** Given an entity, add all implementing graphs that belong to live classes * to _live_graphs. * - * Iff additions occurred, return TRUE, else FALSE. + * Iff additions occurred, return true, else false. */ -static int add_implementing_graphs (ir_entity *method) +static bool add_implementing_graphs(ir_entity *method) { - int i; - int n_over = get_entity_n_overwrittenby (method); - ir_graph *graph = get_entity_irg (method); - int change = FALSE; - - if (NULL == graph) { - graph = get_implementing_graph (method); - } - - if (verbose > 1) { - ir_fprintf(stdout, "RTA: new call to %+F\n", method); - } - - if (rta_is_alive_class (get_entity_owner (method))) { - if (NULL != graph) { - change = add_graph (graph); - } - } - - for (i = 0; i < n_over; i ++) { - ir_entity *over = get_entity_overwrittenby (method, i); - change |= add_implementing_graphs (over); - } - - return (change); + size_t i; + size_t n_over = get_entity_n_overwrittenby(method); + ir_graph *graph = get_entity_irg(method); + bool change = false; + + if (NULL == graph) + graph = get_entity_irg(method); + + DB((dbg, LEVEL_2, "RTA: new call to %+F\n", method)); + + if (rta_is_alive_class(get_entity_owner(method))) { + if (NULL != graph) + change = add_graph(graph); + } + + for (i = 0; i < n_over; ++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. +/** + * Walker: Enter all method accesses and all class allocations into + * our tables. * - * Set *(int*)env to true iff (possibly) new graphs have been found. + * Set *(int*)env to true iff (possibly) new graphs have been found. */ -static void rta_act (ir_node *node, void *env) +static void rta_act(ir_node *node, void *env) { - int *change = (int*) env; - ir_opcode op = get_irn_opcode (node); - - if (iro_Call == op) { /* CALL */ - ir_entity *ent = NULL; - - ir_node *ptr = get_Call_ptr (node); - - /* CALL SEL */ - if (iro_Sel == get_irn_opcode (ptr)) { - ent = get_Sel_entity (ptr); - *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 { - /* other symconst. */ - assert(0 && "This SymConst can not be an address for a method call."); - } - - /* STRANGE */ - } else { - assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!"); - } - - } else if (iro_Alloc == op) { /* ALLOC */ - ir_type *type = get_Alloc_type (node); - - *change |= add_class (type); - } + bool *change = (bool*)env; + unsigned op = get_irn_opcode(node); + + if (iro_Call == op) { /* CALL */ + ir_entity *ent = NULL; + + ir_node *ptr = get_Call_ptr(node); + + /* CALL SEL */ + if (iro_Sel == get_irn_opcode(ptr)) { + ent = get_Sel_entity(ptr); + *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 { + /* other symconst. */ + panic("This SymConst can not be an address for a method call."); + } + + /* STRANGE */ + } else { + panic("Unexpected address expression: can not analyse, therefore can not do correct rta!"); + } + } else if (iro_Alloc == op) { /* ALLOC */ + ir_type *type = get_Alloc_type(node); + + *change |= add_class(type); + } } /** Traverse the given graph to collect method accesses and object allocations. */ -static int rta_fill_graph (ir_graph* graph) +static bool rta_fill_graph(ir_graph* graph) { - int change = FALSE; - irg_walk_graph (graph, rta_act, NULL, &change); - return change; + bool change = false; + irg_walk_graph(graph, rta_act, NULL, &change); + return change; } -/** Traverse all graphs to collect method accesses and object allocations. +/** + * Traverse all graphs to collect method accesses and object allocations. */ -static int rta_fill_incremental (void) +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(0); /* save this for later */ -#endif - - /* init_tables has added main_irg to _live_graphs */ - - /* Need to take care of graphs that are externally - visible or sticky. Pretend that they are called: */ - - for (i = 0; i < get_irp_n_irgs(); i++) { - ir_graph *graph = get_irp_irg (i); - ir_entity *ent = get_irg_entity (graph); + size_t i, n; + int n_runs = 0; + bool rerun = true; - if ((visibility_external_visible == get_entity_visibility (ent)) || - (stickyness_sticky == get_entity_stickyness (ent))) { - eset_insert (_live_graphs, graph); - // printf("external visible: "); DDMG(graph); - } - } + /* init_tables has added main_irg to _live_graphs */ - while (rerun) { - ir_graph *graph; + /* Need to take care of graphs that are externally + visible or sticky. Pretend that they are called: */ + for (i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *graph = get_irp_irg(i); + ir_entity *ent = get_irg_entity(graph); + ir_linkage linkage = get_entity_linkage(ent); - /* start off new */ - eset *live_graphs = _live_graphs; - _live_graphs = eset_create (); - - if (verbose > 1) { - fprintf(stdout, "RTA: RUN %i\n", n_runs); - } - - /* collect what we have found previously */ - eset_insert_all (_live_graphs, live_graphs); - - rerun = FALSE; - for (graph = eset_first (live_graphs); - graph; - graph = eset_next (live_graphs)) { - - if (verbose > 1) { - ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs, - graph); - } - - rerun |= rta_fill_graph (graph); - } - - eset_destroy (live_graphs); - - n_runs ++; - } + if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) + pset_new_insert(_live_graphs, graph); + } -#ifdef INTERPROCEDURAL_VIEW - set_interprocedural_view(old_ip_view); /* cover up our traces */ -#endif + while (rerun) { + ir_graph *graph; + pset_new_iterator_t iter; + + /* start off new */ + pset_new_t *live_graphs = _live_graphs; + _live_graphs = XMALLOC(pset_new_t); + pset_new_init(_live_graphs); + + DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs)); + + /* collect what we have found previously */ + foreach_pset_new(live_graphs, ir_graph*, graph, iter) { + pset_new_insert(_live_graphs, graph); + } + + rerun = false; + foreach_pset_new(live_graphs, ir_graph*, graph, iter) { + DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph)); + rerun |= rta_fill_graph(graph); + } + pset_new_destroy(live_graphs); + free(live_graphs); + ++n_runs; + } - return (n_runs); + return n_runs; } +#ifdef DEBUG_libfirm /** * Count the number of graphs that we have found to be live. */ -static int stats (void) +static size_t stats(void) { - int i; - int n_live_graphs = 0; - int n_graphs = get_irp_n_irgs(); + size_t i, n; + size_t n_live_graphs = 0; - for (i = 0; i < n_graphs; i++) { - ir_graph *graph = get_irp_irg(i); + for (i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *graph = get_irp_irg(i); - if (rta_is_alive_graph (graph)) { - n_live_graphs ++; - } - } + if (rta_is_alive_graph(graph)) + ++n_live_graphs; + } - return (n_live_graphs); + return n_live_graphs; } +#endif /* remove a graph, part I */ /* @@ -331,118 +257,77 @@ static int stats (void) abstract now. Pretend that it wasn't there at all, and every 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 (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 ++) { - 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. */ - ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over)); - - if (addr == my_addr) { - force_description (over, 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); - ir_entity *impl_ent = get_SymConst_entity (f_addr); - - assert(is_SymConst(f_addr) && "can't do complex addrs"); - if (impl_ent == addr) { - assert (0 && "gibt's denn sowas"); - force_description (over, addr); - } - } - } -} /** Initialize the static data structures. */ -static void init_tables (void) +static void init_tables(void) { - ir_type *tp; - int i, n; - - _live_classes = eset_create (); - _live_graphs = eset_create (); - - if (get_irp_main_irg ()) { - eset_insert (_live_graphs, get_irp_main_irg ()); - } - - /* 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); - } + ir_graph *irg; + ir_segment_t segment; + + _live_classes = XMALLOC(pset_new_t); + pset_new_init(_live_classes); + _live_graphs = XMALLOC(pset_new_t); + pset_new_init(_live_graphs); + + irg = get_irp_main_irg(); + if (irg != NULL) { + /* add the main irg to the live set if one is specified */ + pset_new_insert(_live_graphs, irg); + } + + /* Find static allocated classes in all segments */ + for (segment = IR_SEGMENT_FIRST; segment <= IR_SEGMENT_LAST; ++segment) { + ir_type *tp = get_segment_type(segment); + size_t n = get_compound_n_members(tp); + size_t i; + + for (i = 0; i < n; ++i) { + ir_type *member_type = get_entity_type(get_compound_member(tp, i)); + if (is_Class_type(member_type)) + pset_new_insert(_live_classes, member_type); + } + } } /* * 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) +void rta_init(void) { - int n_runs = 0; + int n_runs = 0; - int rem_vpi = get_visit_pseudo_irgs(); - set_visit_pseudo_irgs(1); + FIRM_DBG_REGISTER(dbg, "firm.ana.rta"); # ifdef DEBUG_libfirm - { - int i, n; - n = get_irp_n_irgs(); - for (i = 0; i < n; i++) { - irg_vrfy (get_irp_irg(i)); + { + size_t i; + for (i = get_irp_n_irgs(); i > 0;) { + irg_verify(get_irp_irg(--i), 0); + } + tr_verify(); } - tr_vrfy (); - } # endif /* defined DEBUG_libfirm */ - verbose = do_verbose; + init_tables(); - init_tables (); + n_runs = rta_fill_incremental(); - n_runs = rta_fill_incremental (); - - if (verbose) { - int n_live_graphs = stats (); - - 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); - } + DB((dbg, LEVEL_1, "RTA: n_graphs = %zu\n", get_irp_n_irgs())); + DB((dbg, LEVEL_1, "RTA: n_live_graphs = %zu\n", stats())); + DB((dbg, LEVEL_1, "RTA: n_runs = %i\n", n_runs)); # ifdef DEBUG_libfirm - { - int i, n; - n = get_irp_n_irgs(); - for (i = 0; i < n; i++) { - irg_vrfy (get_irp_irg(i)); + { + size_t i; + + for (i = get_irp_n_irgs(); i > 0;) { + irg_verify(get_irp_irg(--i), 0); + } + tr_verify(); } - tr_vrfy (); - } # endif /* defined DEBUG_libfirm */ - - set_visit_pseudo_irgs(rem_vpi); } /** @@ -451,118 +336,111 @@ void rta_init (int do_verbose) * Changes the peculiarity of entities that represents * dead graphs to peculiarity_description. */ -static void make_entity_to_description(type_or_ent tore, void *env) { - (void) env; - if (is_entity(tore.ent)) { - ir_entity *ent = tore.ent; - - 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); - } - } - } +static void make_entity_to_description(type_or_ent tore, void *env) +{ + (void) env; + if (is_entity(tore.ent)) { + ir_entity *ent = tore.ent; + + if ((is_Method_type(get_entity_type(ent))) && + !entity_is_externally_visible(ent)) { + ir_graph *irg = get_entity_irg(ent); + if (irg != NULL && ! pset_new_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 If verbose == 1, print statistics, if > 1, chatter about every detail */ -void rta_delete_dead_graphs (void) +void rta_delete_dead_graphs(void) { - int i; - 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); - - dead_graphs = XMALLOCN(ir_graph*, get_irp_n_irgs()); - - for (i = 0; i < n_graphs; i++) { - graph = get_irp_irg(i); - - if (rta_is_alive_graph (graph)) { - /* do nothing (except some debugging fprintf`s :-) */ - } else { -#ifndef NDEBUG - ir_entity *ent = get_irg_entity (graph); - assert (visibility_external_visible != get_entity_visibility (ent)); -#endif + size_t i, n_dead_irgs, n_graphs = get_irp_n_irgs(); + ir_graph *irg, *next_irg, *dead_irgs; + + irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK); - dead_graphs[n_dead_graphs] = graph; - n_dead_graphs ++; - } - } + n_dead_irgs = 0; + dead_irgs = NULL; + for (i = n_graphs; i > 0;) { + irg = get_irp_irg(--i); - type_walk(make_entity_to_description, NULL, NULL); - for (i = 0; i < n_dead_graphs; ++i) { - remove_irp_irg (dead_graphs[i]); - } + if (! rta_is_alive_graph(irg)) { + set_irg_link(irg, dead_irgs); + dead_irgs = irg; + ++n_dead_irgs; + } + } - if (verbose) { - printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs); - } + /* Hmm, probably we need to run this only if dead_irgs is non-NULL */ + type_walk(make_entity_to_description, NULL, NULL); + for (irg = dead_irgs; irg != NULL; irg = next_irg) { + next_irg = (ir_graph*) get_irg_link(irg); + remove_irp_irg(irg); + } - set_visit_pseudo_irgs(rem_vpi); + DB((dbg, LEVEL_1, "RTA: dead methods = %zu\n", n_dead_irgs)); - free(dead_graphs); + irp_free_resources(irp, IR_RESOURCE_IRG_LINK); } /* Clean up the RTA data structures. Call this after calling rta_init */ -void rta_cleanup (void) +void rta_cleanup(void) { # ifdef DEBUG_libfirm - int i; - for (i = 0; i < get_irp_n_irgs(); i++) { - irg_vrfy (get_irp_irg(i)); - } - tr_vrfy (); + size_t i; + for (i = get_irp_n_irgs(); i > 0;) { + irg_verify(get_irp_irg(--i), 0); + } + tr_verify(); # endif /* defined DEBUG_libfirm */ - if (_live_classes) { - eset_destroy (_live_classes); - _live_classes = NULL; - } + if (_live_classes != NULL) { + pset_new_destroy(_live_classes); + free(_live_classes); + _live_classes = NULL; + } - if (_live_graphs) { - eset_destroy (_live_graphs); - _live_graphs = NULL; - } + if (_live_graphs != NULL) { + pset_new_destroy(_live_graphs); + free(_live_graphs); + _live_graphs = NULL; + } } /* Say whether this class might be instantiated at any point in the program: */ -int rta_is_alive_class (ir_type *clazz) +int rta_is_alive_class(ir_type *clazz) { - return (eset_contains (_live_classes, clazz)); + return pset_new_contains(_live_classes, clazz); } /* Say whether this graph might be run at any time in the program: */ -int rta_is_alive_graph (ir_graph *graph) +int rta_is_alive_graph(ir_graph *graph) { - return eset_contains (_live_graphs, graph); + return pset_new_contains(_live_graphs, graph); } /* dump our opinion */ -void rta_report (void) +void rta_report(void) { - int i; - - for (i = 0; i < get_irp_n_types(); ++i) { - 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))) { - ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i)); - } - } + size_t i, n; + + n = get_irp_n_types(); + for (i = 0; i < n; ++i) { + ir_type *tp = get_irp_type(i); + if (is_Class_type(tp) && rta_is_alive_class(tp)) { + ir_printf("RTA: considered allocated: %+F\n", tp); + } + } + + n = get_irp_n_irgs(); + for (i = 0; i < n; i++) { + ir_graph *irg = get_irp_irg(i); + if (rta_is_alive_graph(irg)) { + ir_printf("RTA: considered called: graph of %+F\n", irg); + } + } }