/*
* Project: libFIRM
* File name: ir/ana/rta.c
- * Purpose: Intraprozedural analyses to improve the call graph estimate.
+ * Purpose: Interprocedural analysis to improve the call graph estimate.
* 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 <config.h>
+# include "config.h"
#endif
#include "rta.h"
#include <stdlib.h>
#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;
-static eset *_live_fields = NULL;
-static eset *_called_methods = NULL;
/* cache computed results */
static eset *_live_graphs = NULL;
-static eset *_dead_graphs = NULL;
-
-static int whole_world = 0;
-static int verbose = 0;
/**
- Initialise the static data structures.
+ Given a method, find the firm graph that implements that method.
*/
-static void init_tables (void)
+static ir_graph *get_implementing_graph (ir_entity *method)
{
- _live_classes = eset_create ();
- _live_fields = eset_create ();
- _called_methods = eset_create ();
+#if 0
+ ir_graph *graph = get_entity_irg ((ir_entity*) method);
- _live_graphs = eset_create ();
- _dead_graphs = eset_create ();
-
- if (get_irp_main_irg ()) {
- eset_insert (_live_graphs, get_irp_main_irg ());
- }
+ /* 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);
- if (get_glob_type ()) {
- eset_insert (_live_classes, get_glob_type ());
+ for (i = 0; (NULL == graph) && (i < n_over); i ++) {
+ ir_entity *over = get_entity_overwrites ((ir_entity*) method, i);
+ graph = get_implementing_graph (over);
+ }
}
-}
-
-/**
- Enter all method and field accesses and all class allocations into
- our tables.
-*/
-static void rta_act (ir_node *node, void *env)
-{
- opcode op = get_irn_opcode (node);
-
- if (iro_Call == op) { /* CALL */
- entity *ent = NULL;
- ir_node *ptr = get_Call_ptr (node);
-
- if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
- ent = get_Sel_entity (ptr);
- eset_insert (_called_methods, 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);
+ /* 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))));
- eset_insert (_live_graphs, graph);
- } 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"); */
- }
- } else if (iro_Load == op) { /* LOAD */
- ir_node *ptr = get_Load_ptr (node);
- entity *ent = NULL;
+ /* we *must* always return a graph != NULL, *except* when we're used
+ inside remove_irg or force_description */
+ /* assert (graph && "no graph"); */
- if (iro_Sel == get_irn_opcode (ptr)) {
- ent = get_Sel_entity (ptr);
- }
- if (ent) {
- eset_insert (_live_fields, ent);
- }
- } else if (iro_Store == op) { /* STORE */
- ir_node *ptr = get_Store_ptr (node);
- entity *ent = NULL;
+ return (graph);
+#else
+ ir_graph *graph = NULL;
- if (iro_Sel == get_irn_opcode (ptr)) {
- ent = get_Sel_entity (ptr);
- }
- if (ent) {
- eset_insert (_live_fields, ent);
- }
- } else if (iro_Alloc == op) { /* ALLOC */
- type *type = get_Alloc_type (node);
+ if (get_entity_peculiarity(method) != peculiarity_description)
+ graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
- eset_insert (_live_classes, type);
- }
+ return graph;
+#endif
}
/**
- Traverse the given graph to collect method and field accesses and
- object allocations.
-*/
-static void rta_fill_graph (ir_graph* graph)
+ * 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 (NULL != graph) {
- if (NULL != get_irg_end (graph)) {
- current_ir_graph = graph;
-
- irg_walk (get_irg_end (graph), rta_act, NULL, NULL);
+ if (!eset_contains (_live_graphs, graph)) {
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: new graph of ");
+ DDMEO(get_irg_entity (graph));
}
- }
-}
-/**
- Check whether the given graph is alive based on the contents of the
- given esets.
-*/
-static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
-{
- if (eset_contains (live_graphs, graph)) {
+ eset_insert (_live_graphs, graph);
return (TRUE);
}
- if (eset_contains (dead_graphs, graph)) {
- return (FALSE);
- }
-
- assert (0 && "graph neither live not dead (shouldn't happen)");
+ return (FALSE);
}
/**
- Traverse all graphs to collect method and field accesses and object allocations.
-
- @param rerun Whether to rely on is_alive in a second run
-*/
-static void rta_fill_all (int rerun)
+ * 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)
{
- int i;
- int old_ip_view = interprocedural_view;
- eset *live_graphs = NULL;
- eset *dead_graphs = NULL;
-
- interprocedural_view = 0; /* save this for later */
-
- if (rerun) {
- int n_graphs = get_irp_n_irgs ();
-
- /* force all graphs to be entered in either live_graphs or dead_graphs */
- for (i = 0; i < n_graphs; i ++) {
- rta_is_alive_graph (get_irp_irg (i));
- }
-
- /* remember existing infos for later */
- live_graphs = _live_graphs;
- dead_graphs = _dead_graphs;
-
- /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
- _live_graphs = NULL;
- _dead_graphs = NULL;
-
- rta_cleanup ();
- init_tables ();
- }
-
- /* Consider all graphs, possibly taking into account existing infos */
- for (i = 0; i < get_irp_n_irgs(); i++) {
- ir_graph *graph = get_irp_irg (i);
-
- if (! whole_world) {
- /* Need to take care of graphs that are externally
- visible. Pretend that they are called: */
- entity *ent = get_irg_entity (graph);
- if (visibility_external_visible == get_entity_visibility (ent)) {
- /* eset_insert (_called_methods, ent); */
-
- if (get_entity_irg (ent)) {
- eset_insert (_live_graphs, get_entity_irg (ent));
- }
-
- /* eset_insert (_live_classes, get_entity_owner (ent)); */
- }
- }
-
- /* now check the graph */
- if (rerun) {
- if (is_alive (graph, live_graphs, dead_graphs)) {
- rta_fill_graph (graph);
- } else {
- /* nothing (except debugging printf's :-) */
- }
- } else {
- rta_fill_graph (graph);
+ if (!eset_contains (_live_classes, clazz)) {
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: new class: ");
+ DDMT(clazz);
}
- }
- if (rerun) {
- /* clean up the tables that we have retained */
- eset_destroy (live_graphs);
- eset_destroy (dead_graphs);
+ eset_insert (_live_classes, clazz);
+ return (TRUE);
}
- interprocedural_view = old_ip_view; /* cover up our traces */
+ return (FALSE);
}
-/**
- Given a method, find the firm graph that implements that method.
+/** Given an entity, add all implementing graphs that belong to live classes
+ * to _live_graphs.
+ *
+ * Iff additions occurred, return TRUE, else FALSE.
*/
-static ir_graph *get_implementing_graph (entity *method)
+static int add_implementing_graphs (ir_entity *method)
{
- ir_graph *graph = get_entity_irg ((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) {
- int i;
- int n_over = get_entity_n_overwrites ((entity*) method);
+ graph = get_implementing_graph (method);
+ }
- for (i = 0; (NULL == graph) && (i < n_over); i ++) {
- entity *over = get_entity_overwrites ((entity*) method, i);
- graph = get_implementing_graph (over);
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: new call to ");
+ DDMEO(method);
+ }
+
+ if (rta_is_alive_class (get_entity_owner (method))) {
+ if (NULL != graph) {
+ change = add_graph (graph);
}
}
- /* we *must* always return a graph != NULL, *except* when we're used
- inside remove_irg or force_description */
- /* assert (graph && "no graph"); */
+ for (i = 0; i < n_over; i ++) {
+ ir_entity *over = get_entity_overwrittenby (method, i);
+ change |= add_implementing_graphs (over);
+ }
- return (graph);
+ return (change);
}
-/* -------------------------------------------------------------------
- Method Calls
- ------------------------------------------------------------------- */
-/**
- Find out whether the given method could be the target of a
- polymorphic call.
-*/
-static int has_live_upcall (entity *method)
+/** 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 is_target = FALSE;
- int i;
- int n_over;
-
- /* The method could be the target of a polymorphic call if it is
- called or if it overrides a method that is called. */
-
- if (eset_contains (_called_methods, (entity*) method)) {
- return (TRUE);
- }
+ int *change = (int*) env;
+ opcode op = get_irn_opcode (node);
- /* not called? check methods in superclass(es) */
- n_over = get_entity_n_overwrites ((entity*) method);
- for (i = 0; !is_target && (i < n_over); i ++) {
- entity *over = get_entity_overwrites ((entity*) method, i);
- is_target |= has_live_upcall (over);
- }
+ if (iro_Call == op) { /* CALL */
+ ir_entity *ent = NULL;
- return (is_target);
-}
+ ir_node *ptr = get_Call_ptr (node);
-/**
- Determine wether the given method is called through polymorphy with
- the given graph
-*/
-static int has_live_downcall (entity *method, ir_graph *graph)
-{
- int has_downcall = FALSE;
- int i, n_over;
+ /* 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.");
+ }
- if (graph != get_entity_irg ((entity*) method)) {
- return (FALSE);
- }
+ /* STRANGE */
+ } else {
+ DDMN(ptr);
+ assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
+ }
- if (eset_contains (_called_methods, method)) {
- return (TRUE);
- }
+ } else if (iro_Alloc == op) { /* ALLOC */
+ ir_type *type = get_Alloc_type (node);
- /* maybe we're overwritten by a method that is called? */
- n_over = get_entity_n_overwrittenby ((entity*) method);
- for (i = 0; !has_downcall && (i < n_over); i ++) {
- entity *over = get_entity_overwrittenby ((entity*) method, i);
- has_downcall |= has_live_downcall (over, graph);
+ *change |= add_class (type);
}
-
- return (has_downcall);
}
/**
- Determine whether the given method or one of its overwriters have
- been used in a call to the given graph.
+ Traverse the given graph to collect method accesses and
+ object allocations.
*/
-static int has_live_call (entity *method, ir_graph *graph)
+static int rta_fill_graph (ir_graph* graph)
{
- /* maybe we're called (possibly through polymorphy)? */
- if (has_live_upcall (method)) {
- return (TRUE);
- }
-
- /* maybe our subclasses have seen a call? */
- if (has_live_downcall (method, graph)) {
- return (TRUE);
- }
-
- return (FALSE);
+ int change = FALSE;
+ irg_walk_graph (graph, rta_act, NULL, &change);
+ return change;
}
-/* -------------------------------------------------------------------
- Class Instantiations
- ------------------------------------------------------------------- */
-static int has_live_superclass (entity *method, ir_graph *graph)
+/** Traverse all graphs to collect method accesses and object allocations.
+ */
+static int rta_fill_incremental (void)
{
- int has_super = FALSE;
int i;
- int n_over;
+ int n_runs = 0;
+ int rerun = TRUE;
+ int old_ip_view = get_interprocedural_view();
- /* The method could be the target of a polymorphic call if it is
- called or if it overrides a method that is called. */
+ set_interprocedural_view(0); /* save this for later */
- if (eset_contains (_live_classes, get_entity_owner (method))) {
- return (TRUE);
- }
+ /* init_tables has added main_irg to _live_graphs */
- /* not allocated? check methods in superclass(es) */
- n_over = get_entity_n_overwrites ((entity*) method);
- for (i = 0; !has_super && (i < n_over); i ++) {
- entity *over = get_entity_overwrites ((entity*) method, i);
- has_super |= has_live_superclass (over, graph);
- }
+ /* Need to take care of graphs that are externally
+ visible or sticky. Pretend that they are called: */
- return (has_super);
-}
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ ir_graph *graph = get_irp_irg (i);
+ ir_entity *ent = get_irg_entity (graph);
-static int has_live_subclass (entity *method, ir_graph *graph)
-{
- int has_sub = FALSE;
- int i;
- int n_over;
+ if ((visibility_external_visible == get_entity_visibility (ent)) ||
+ (stickyness_sticky == get_entity_stickyness (ent))) {
+ eset_insert (_live_graphs, graph);
+ // printf("external visible: "); DDMG(graph);
+ }
+ }
- /* a class that doesn't use the graph in question can't help here: */
- ir_graph *impl = get_implementing_graph (method);
+ while (rerun) {
+ ir_graph *graph;
- /* this function is only called starting at 'graph's method, and
- we're checking *downwards*, so impl must be != NULL */
- assert (impl);
- if (impl != graph) {
- return (FALSE);
- }
+ /* start off new */
+ eset *live_graphs = _live_graphs;
+ _live_graphs = eset_create ();
- /* otherwise, an instantiated class helps a lot! */
- if (rta_is_alive_class (get_entity_owner (method))) {
- return (TRUE);
- }
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: RUN %i\n", n_runs);
+ }
- /* maybe our subclasses use this graph *and* have been instantiated ? */
- n_over = get_entity_n_overwrittenby ((entity*) method);
- for (i = 0; !has_sub && (i < n_over); i ++) {
- entity *over = get_entity_overwrittenby ((entity*) method, i);
- has_sub |= has_live_subclass (over, graph);
- }
+ /* collect what we have found previously */
+ eset_insert_all (_live_graphs, live_graphs);
- return (has_sub);
-}
+ 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_entity (graph));
+ }
+ rerun |= rta_fill_graph (graph);
+ }
-/**
- Determine whether the given method could be used in a call to the
- given graph on a live class.
-*/
-static int has_live_class (entity *method, ir_graph *graph)
-{
- /* maybe we're called (possibly through polymorphy)? */
- if (has_live_superclass (method, graph)) {
- return (TRUE);
- }
+ eset_destroy (live_graphs);
- /* maybe our subclasses have seen a call? */
- if (has_live_subclass (method, graph)) {
- return (TRUE);
+ n_runs ++;
}
- return (FALSE);
+ 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. Since
- this touches every graph of the irp, it also forces that each graph
- is either in _live_graphs xor in _dead_graphs. This is useful if
- we use is_alive(ir_graph*) internally.
-*/
+/**
+ * Count the number of graphs that we have found to be live.
+ */
static int stats (void)
{
int i;
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);
} 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);
}
}
-/* 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.
+/**
+ Initialize the static data structures.
*/
-static void remove_irg (ir_graph *graph)
+static void init_tables (void)
{
- entity *ent = get_irg_entity (graph);
-
-/* DDMEO (get_irg_ent(graph)); */
-
- /* delete the ir_graph data */
- remove_irp_irg (graph);
- /* remove reference to the graph */
- set_entity_irg (ent, NULL);
- /* 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)));
+ 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);
}
}
-/* Initialise the RTA data structures, and perform RTA.
- @param do_verbose Iff != 0, print statistics as we go along
- @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_live_graphs = get_irp_n_irgs ();
- int n_graphs = 0;
int n_runs = 0;
- whole_world = do_whole_world;
- verbose = do_verbose;
+ 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 */
+ verbose = do_verbose;
+
init_tables ();
- if (verbose && whole_world) {
- printf ("RTA: whole-world assumption\n");
- }
+ n_runs = rta_fill_incremental ();
if (verbose) {
- printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
- }
-
- rta_fill_all (FALSE);
-
- while (n_graphs != n_live_graphs) {
- n_graphs = n_live_graphs;
- n_runs ++;
- rta_fill_all (TRUE);
- n_live_graphs = stats ();
-
- if (verbose) {
- printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
- }
- }
+ int n_live_graphs = stats ();
- if (verbose) {
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 */
+/* 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 i;
int n_graphs = get_irp_n_irgs ();
ir_graph *graph = NULL;
+ int n_dead_graphs = 0;
+ ir_graph **dead_graphs;
- eset *dead_graphs = eset_create ();
+ int rem_vpi = get_visit_pseudo_irgs();
+ set_visit_pseudo_irgs(1);
+
+ if (!get_optimize() || !get_opt_dead_method_elimination()) return;
+
+ dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
for (i = 0; i < n_graphs; i++) {
graph = get_irp_irg(i);
- if (is_alive (graph, _live_graphs, _dead_graphs)) {
+ if (rta_is_alive_graph (graph)) {
/* 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 */
- eset_insert (dead_graphs, graph);
+ dead_graphs[n_dead_graphs] = graph;
+ n_dead_graphs ++;
}
}
- /* now delete the graphs. */
- for (graph = eset_first (dead_graphs);
- graph;
- graph = (ir_graph*) eset_next (dead_graphs)) {
-
- if (verbose) {
- fprintf(stdout, "RTA: removing graph of ");
- DDMEO(get_irg_ent (graph));
- }
+ type_walk(make_entity_to_description, NULL, NULL);
+ for (i = 0; i < n_dead_graphs; ++i) {
+ remove_irp_irg (dead_graphs[i]);
+ }
- remove_irg (graph);
+ 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 */
_live_classes = NULL;
}
- if (_live_fields) {
- eset_destroy (_live_fields);
- _live_fields = NULL;
- }
-
- if (_called_methods) {
- eset_destroy (_called_methods);
- _called_methods = NULL;
- }
-
if (_live_graphs) {
eset_destroy (_live_graphs);
_live_graphs = NULL;
}
-
- if (_dead_graphs) {
- eset_destroy (_dead_graphs);
- _dead_graphs = NULL;
- }
}
/* 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));
}
/* Say whether this graph might be run at any time in the program: */
int rta_is_alive_graph (ir_graph *graph)
{
- int has_call = FALSE;
- int has_class = FALSE;
-
- if (eset_contains (_live_graphs, graph)) {
- return (TRUE);
- }
-
- if (eset_contains (_dead_graphs, graph)) {
- return (FALSE);
- }
-
- entity *meth = get_irg_ent (graph);
-
- has_call = has_live_call (meth, graph);
- has_class = has_live_class (meth, graph);
-
- if (has_call && has_class) {
- eset_insert (_live_graphs, graph);
-
- return (TRUE);
- } else {
- eset_insert (_dead_graphs, graph);
-
- return (FALSE);
- }
-}
-
-/* Say whether there have been any accesses to this field: */
-int rta_is_alive_field (entity *field)
-{
- return (eset_contains (_live_fields, field));
+ return eset_contains (_live_graphs, graph);
}
/* dump our opinion */
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);
}
}
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)));
}
}
}
/*
* $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
+ *
+ * Revision 1.16 2004/06/24 06:42:14 goetz
+ * test of firm flags
+ *
+ * Revision 1.15 2004/06/18 15:47:19 liekweg
+ * minor bug fix (go forward, not backward) --flo
+ *
* Revision 1.14 2004/06/18 13:12:43 liekweg
* final bug fix (calls via consts)
*
projects / libfirm / blobdiff