X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Frta.c;h=dafef1d7974bdbf49e18d16d67d6fcea4a4dd485;hb=431a1085882dfc835148fe8f2662cc901380eb1b;hp=e136ce93a73451576ffb37601cdb45d0d69df1a6;hpb=7a4700d9c8fe432f785a480fdb14231061aa2531;p=libfirm diff --git a/ir/ana/rta.c b/ir/ana/rta.c index e136ce93a..dafef1d79 100644 --- a/ir/ana/rta.c +++ b/ir/ana/rta.c @@ -1,362 +1,453 @@ -/* -*- c -*- */ - /* - * Project: libFIRM - * File name: ir/ana/rta.c - * Purpose: Intraprozedural analyses to improve the call graph estimate. - * Author: Florian - * Modified by: - * Created: 09.06.2002 - * CVS-ID: $$ - * Copyright: (c) 1999-2004 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2011 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. */ /** - * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es - * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden - * bestimmt. + * @file + * @brief Interprocedural analysis to improve the call graph estimate. + * @author Florian Liekweg + * @version 09.06.2002 + * @version $Id$ */ +#include "config.h" #include "rta.h" -# define TRUE 1 -# define FALSE 0 - -/* # define RTA_SET */ -# ifdef RTA_SET -typedef struct rta_set_elt -{ - struct rta_set_elt *_next; - void *_obj; -} rta_set_elt_t; +#include +#include -typedef struct rta_set -{ - rta_set_elt_t *_list; -} rta_set_t; +#include "irnode_t.h" +#include "irprog_t.h" +#include "irgraph_t.h" -# define SET_T rta_set_t +#include "pset_new.h" +#include "irgwalk.h" +#include "irgmod.h" +#include "irverify.h" +#include "irprintf.h" +#include "debug.h" +#include "error.h" -# else /* if defined RTA_SET */ -# define SET_T eset -# define new_set eset_create -# define delete_set(SET) eset_destroy(SET) -# define set_insert(SET,ELT) eset_insert(SET,ELT) -# define set_contains(SET,ELT) eset_contains(SET,ELT) -# endif /* defined RTA_SET */ +/** The debug handle. */ +DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) -static SET_T *_live_classes = NULL; -static SET_T *_live_fields = NULL; -static SET_T *_called_methods = NULL; +/* base data */ +static pset_new_t *_live_classes = NULL; /* cache computed results */ -static SET_T *_live_graphs = NULL; -static SET_T *_dead_graphs = NULL; +static pset_new_t *_live_graphs = NULL; -# ifdef RTA_SET -/* Reinvent the wheel, err, set. */ -/* eset uses obstacks, which fucks up the graph somehow */ -static rta_set_t *new_set () +/** + * 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 bool add_graph(ir_graph *graph) { - rta_set_t *set = (rta_set_t*) xmalloc (sizeof (rta_set_t)); + if (!pset_new_contains(_live_graphs, graph)) { + DB((dbg, LEVEL_2, "RTA: new graph of %+F\n", graph)); - set->_list = NULL; + pset_new_insert(_live_graphs, graph); + return true; + } - return (set); + return false; } -static void delete_set (rta_set_t *set) +/** + * 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 bool add_class(ir_type *clazz) { - rta_set_elt_t *elt = set->_list; + if (!pset_new_contains(_live_classes, clazz)) { + DB((dbg, LEVEL_2, "RTA: new class: %+F\n", clazz)); - while (NULL != elt) { - rta_set_elt_t *old = elt; - elt = elt->_next; + pset_new_insert(_live_classes, clazz); + return true; + } - old->_next = NULL; - old->_obj = NULL; - free (old); - } - - free (set); + return false; } -static void set_insert (rta_set_t *set, void *obj) +/** Given an entity, add all implementing graphs that belong to live classes + * to _live_graphs. + * + * Iff additions occurred, return true, else false. +*/ +static bool add_implementing_graphs(ir_entity *method) { - rta_set_elt_t *elt = (rta_set_elt_t*) xmalloc (sizeof (rta_set_elt_t)); + size_t i; + size_t n_over = get_entity_n_overwrittenby(method); + ir_graph *graph = get_entity_irg(method); + bool change = false; - elt->_obj = obj; - elt->_next = set->_list; - set->_list = elt; -} + if (NULL == graph) + graph = get_entity_irg(method); -static int set_contains (rta_set_t *set, void *obj) -{ - rta_set_elt_t *elt = set->_list; + DB((dbg, LEVEL_2, "RTA: new call to %+F\n", method)); - while (NULL != elt) { - if (elt->_obj == obj) { - return (TRUE); - } + if (rta_is_alive_class(get_entity_owner(method))) { + if (NULL != graph) + change = add_graph(graph); + } - elt = elt->_next; - } + for (i = 0; i < n_over; ++i) { + ir_entity *over = get_entity_overwrittenby(method, i); + change |= add_implementing_graphs(over); + } - return (FALSE); + return change; } -# endif /* defined RTA_SET */ -/* now the meat */ - -static void rta_act (ir_node *node, void *env) +/** + * Walker: 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) { - opcode op = get_irn_opcode (node); - - if (iro_Call == op) { - entity *ent = NULL; - - ir_node *ptr = get_Call_ptr (node); - // test: ptr.op == Const - - if (iro_Sel == get_irn_opcode (ptr)) { - ent = get_Sel_entity (ptr); - set_insert (_called_methods, ent); - } - - if (ent) { - } - } else if (iro_Load == op) { - ir_node *ptr = get_Load_ptr (node); - entity *ent = NULL; - - if (iro_Sel == get_irn_opcode (ptr)) { - ent = get_Sel_entity (ptr); - } - if (ent) { - set_insert (_live_fields, ent); - } - } else if (iro_Store == op) { - ir_node *ptr = get_Store_ptr (node); - entity *ent = NULL; - - if (iro_Sel == get_irn_opcode (ptr)) { - ent = get_Sel_entity (ptr); - } - if (ent) { - set_insert (_live_fields, ent); - } - } else if (iro_Alloc == op) { - type *type = get_Alloc_type (node); - set_insert (_live_classes, 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); + } } -static void rta_fill_graph (ir_graph* graph) +/** + Traverse the given graph to collect method accesses and + object allocations. +*/ +static bool rta_fill_graph(ir_graph* graph) { - irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL); + bool change = false; + irg_walk_graph(graph, rta_act, NULL, &change); + return change; } -static void rta_fill_all () +/** + * Traverse all graphs to collect method accesses and object allocations. + */ +static int rta_fill_incremental(void) { - int i; - - for (i = 0; i < get_irp_n_irgs(); i++) { - rta_fill_graph (get_irp_irg (i)); - } + size_t i, n; + int n_runs = 0; + bool rerun = true; + + /* 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, 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); + + if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) + pset_new_insert(_live_graphs, graph); + } + + 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; } -static int is_call_target (entity *method) +#ifdef DEBUG_libfirm +/** + * Count the number of graphs that we have found to be live. + */ +static size_t stats(void) { - return (TRUE); -} - + size_t i, n; + size_t n_live_graphs = 0; -static ir_graph *get_implementing_graph (entity *method) -{ - ir_graph *graph = get_entity_irg (method); + for (i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *graph = get_irp_irg(i); - if (NULL == graph) { - int i; - int n_over = get_entity_n_overwrites (method); + if (rta_is_alive_graph(graph)) + ++n_live_graphs; + } - for (i = 0; (NULL == graph) && (i < n_over); i ++) { - entity *over = get_entity_overwrites (method, i); - graph = get_implementing_graph (over); - } - } + return n_live_graphs; +} +#endif - assert (graph && "no graph"); +/* remove a graph, part I */ +/* + We removed the first graph to implement the entity, so we're + abstract now. Pretend that it wasn't there at all, and every + entity that used to inherit this entity's graph is now abstract. +*/ - return (graph); +/** + Initialize the static data structures. +*/ +static void init_tables(void) +{ + ir_type *tp; + size_t i, n; + ir_graph *irg; + + _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 */ + 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)) + pset_new_insert(_live_classes, member_type); + } + + tp = get_tls_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)) + pset_new_insert(_live_classes, member_type); + } + + /** @FIXME: add constructors/destructors */ } -static int has_live_call (entity *method, ir_graph *graph) +/* + * Initialize the RTA data structures, and perform RTA. + */ +void rta_init(void) { - int has_call = FALSE; - int i, n_over; - - if (get_irg_ent (graph) != method) { - return (FALSE); - } - - if (is_call_target (method)) { - return (TRUE); - } - - n_over = get_entity_n_overwrittenby (method); - for (i = 0; !has_call && (i < n_over); i ++) { - entity *over = get_entity_overwrittenby(method, i); - has_call |= has_live_call (over, graph); - } - - return (has_call); + int n_runs = 0; + + FIRM_DBG_REGISTER(dbg, "firm.ana.rta"); + +# ifdef DEBUG_libfirm + { + size_t i; + for (i = get_irp_n_irgs(); i > 0;) { + irg_verify(get_irp_irg(--i), 0); + } + tr_verify(); + } +# endif /* defined DEBUG_libfirm */ + + init_tables(); + + n_runs = rta_fill_incremental(); + + 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 + { + size_t i; + + for (i = get_irp_n_irgs(); i > 0;) { + irg_verify(get_irp_irg(--i), 0); + } + tr_verify(); + } +# endif /* defined DEBUG_libfirm */ } -static int has_graph (type *clazz, ir_graph *graph) +/** + * 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) { - int has_the_graph = FALSE; - int i; - int n_sub; - - if (set_contains (_live_classes, clazz)) { - int n_meth = get_class_n_members (clazz); - - for (i = 0; i < n_meth; i ++) { - entity *member = get_class_member (clazz, i); - if (is_method_type (get_entity_type (member))) { - ir_graph *impl = get_entity_irg (member); - - if (impl == graph) { - return (TRUE); - } - } /* is_method */ - } /* all methods */ - } /* _live_classes.contains (clazz) */ - - n_sub = get_class_n_subtypes (clazz); - for (i = 0; !has_the_graph && (i < n_sub); i ++) { - type *sub = get_class_subtype (clazz, i); - - has_the_graph |= has_graph (sub, graph); - } - - return (has_the_graph); + (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); + } + } + } } -static int has_live_class (entity *method, ir_graph *graph) +/* 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) { - int has_class = FALSE; - int i; - int n_over; - type *clazz; - - if (get_implementing_graph (method) != graph) { - return (FALSE); - } - - clazz = get_entity_owner (method); - if (has_graph (clazz, graph)) { - return (TRUE); - } - - n_over = get_entity_n_overwrittenby (method); - for (i = 0; !has_class && (i < n_over); i ++) { - entity *over = get_entity_overwrittenby (method, i); - has_class |= has_live_class (over, graph); - } - - return (has_class); -} + 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); -void rta_init () -{ - fprintf (stdout, "BEGIN %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__); + n_dead_irgs = 0; + dead_irgs = NULL; + for (i = n_graphs; i > 0;) { + irg = get_irp_irg(--i); - _live_classes = new_set (); - _live_fields = new_set (); - _called_methods = new_set (); + if (! rta_is_alive_graph(irg)) { + set_irg_link(irg, dead_irgs); + dead_irgs = irg; + ++n_dead_irgs; + } + } - _live_graphs = new_set (); - _dead_graphs = new_set (); + /* 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); + } - fprintf (stdout, "FILL %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__); - rta_fill_all (); - fprintf (stdout, "DONE %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__); + DB((dbg, LEVEL_1, "RTA: dead methods = %zu\n", n_dead_irgs)); - /* - * shold be: - * rta_fill_queue () - */ + irp_free_resources(irp, IR_RESOURCE_IRG_LINK); } -void rta_cleanup () +/* Clean up the RTA data structures. Call this after calling rta_init */ +void rta_cleanup(void) { - if (_live_classes) { - delete_set (_live_classes); - _live_classes = NULL; - } - - if (_live_fields) { - delete_set (_live_fields); - _live_fields = NULL; - } - - if (_called_methods) { - delete_set (_called_methods); - _called_methods = NULL; - } - - if (_live_graphs) { - delete_set (_live_graphs); - _live_graphs = NULL; - } - - if (_dead_graphs) { - delete_set (_dead_graphs); - _dead_graphs = NULL; - } +# ifdef DEBUG_libfirm + 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 != NULL) { + pset_new_destroy(_live_classes); + free(_live_classes); + _live_classes = NULL; + } + + if (_live_graphs != NULL) { + pset_new_destroy(_live_graphs); + free(_live_graphs); + _live_graphs = NULL; + } } -int rta_is_alive_class (type *clazz) +/* Say whether this class might be instantiated at any point in the program: */ +int rta_is_alive_class(ir_type *clazz) { - return (set_contains (_live_classes, clazz)); + return pset_new_contains(_live_classes, clazz); } -int rta_is_alive_graph (ir_graph *graph) +/* Say whether this graph might be run at any time in the program: */ +int rta_is_alive_graph(ir_graph *graph) { - if (set_contains (_live_graphs, graph)) { - return (TRUE); - } - - if (set_contains (_dead_graphs, graph)) { - return (FALSE); - } - - entity *meth = get_irg_ent (graph); - - if (has_live_call (meth, graph) && has_live_class (meth, graph)) { - set_insert (_live_graphs, graph); - - return (TRUE); - } else { - set_insert (_dead_graphs, graph); - - return (FALSE); - } + return pset_new_contains(_live_graphs, graph); } -int rta_is_alive_field (entity *field) +/* dump our opinion */ +void rta_report(void) { - return (set_contains (_live_fields, field)); + 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); + } + } } - - - -/* - * $Log$ - * Revision 1.1 2004/06/11 18:24:18 liekweg - * Added RTA --flo - * - */