-/* -*- 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 <stdlib.h>
+#include <stdbool.h>
-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_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);
+ }
+ }
}
-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
- *
- */