X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Frta.c;h=1e5fda8c8ab7839d05d1bc18370b02a45876ff75;hb=ff0e8d7fcb34481652f0bf521ba04b1eca5e2106;hp=df50cb5a326323dcadf572c9292333bb79d8b372;hpb=11e483781b26316bb25c8371d79d831a760113ce;p=libfirm

diff --git a/ir/ana/rta.c b/ir/ana/rta.c
index df50cb5a3..1e5fda8c8 100644
--- a/ir/ana/rta.c
+++ b/ir/ana/rta.c
@@ -3,23 +3,18 @@
 /*
  * 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"
@@ -27,341 +22,282 @@
 #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;
 
 /**
-   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 (entity *method)
 {
-  _live_classes   = eset_create ();
-  _live_fields    = eset_create ();
-  _called_methods = eset_create ();
-
-  _live_graphs = eset_create ();
-  _dead_graphs = eset_create ();
+#if 0
+  ir_graph *graph = get_entity_irg ((entity*) method);
 
-  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 ((entity*) method);
 
-  if (get_glob_type ()) {
-    eset_insert (_live_classes, get_glob_type ());
+    for (i = 0; (NULL == graph) && (i < n_over); i ++) {
+      entity *over = get_entity_overwrites ((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);
+  /* 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))));
 
-  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);
-    } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
-      ent = get_tarval_entity (get_Const_tarval (ptr));
-
-    } 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"); */
-    }
-
-    if (ent) {
-      eset_insert (_called_methods, ent);
-    }
-  } 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));
     }
+
+    eset_insert (_live_graphs, graph);
+    return (TRUE);
   }
+
+  return (FALSE);
 }
 
 /**
-   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)
+ * 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_graphs, graph)) {
-    return (TRUE);
-  }
+  if (!eset_contains (_live_classes, clazz)) {
+    if (verbose > 1) {
+      fprintf(stdout, "RTA:        new class: ");
+      DDMT(clazz);
+    }
 
-  if (eset_contains (dead_graphs, graph)) {
-    return (FALSE);
+    eset_insert (_live_classes, clazz);
+    return (TRUE);
   }
 
-  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
+/** Given an entity, add all implementing graphs that belong to live classes
+ *  to _live_graphs.
+ *
+ *  Iff additions occurred, return TRUE, else FALSE.
 */
-static void rta_fill_all (int rerun)
+static int add_implementing_graphs (entity *method)
 {
   int i;
-  int old_ip_view = interprocedural_view;
-  eset *live_graphs = NULL;
-  eset *dead_graphs = NULL;
+  int n_over = get_entity_n_overwrittenby (method);
+  ir_graph *graph = get_entity_irg (method);
+  int change = FALSE;
 
-  interprocedural_view = 0;     /* save this for later */
+  if (NULL == graph) {
+    graph = get_implementing_graph (method);
+  }
 
-  if (rerun) {
-    int n_graphs = get_irp_n_irgs ();
+  if (verbose > 1) {
+    fprintf(stdout, "RTA:        new call to ");
+    DDMEO(method);
+  }
 
-    /* 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));
+  if (rta_is_alive_class (get_entity_owner (method))) {
+    if (NULL != graph) {
+      change = add_graph (graph);
     }
+  }
 
-    /* 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 ();
+  for (i = 0; i < n_over; i ++) {
+    entity *over = get_entity_overwrittenby (method, i);
+    change |= add_implementing_graphs (over);
   }
 
-  /* 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);
+  return (change);
+}
 
-    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);
+/** 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 (get_entity_irg (ent)) {
-          eset_insert (_live_graphs, get_entity_irg (ent));
-        }
+  if (iro_Call == op) {         /* CALL */
+    entity *ent = NULL;
 
-        eset_insert (_live_classes, get_entity_owner (ent));
-      }
-    }
+    ir_node *ptr = get_Call_ptr (node);
 
-    /* now check the graph */
-    if (rerun) {
-      if (is_alive (graph, live_graphs, dead_graphs)) {
-        rta_fill_graph (graph);
+    /* 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 {
-        /* nothing (except debugging printf's :-) */
+        /* other symconst. */
+        assert(0 && "This SymConst can not be an address for a method call.");
       }
+
+      /* STRANGE */
     } else {
-      rta_fill_graph (graph);
+      DDMN(ptr);
+      assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
     }
-  }
 
-  if (rerun) {
-    /* clean up the tables that we have retained */
-    eset_destroy (live_graphs);
-    eset_destroy (dead_graphs);
-  }
+  } else if (iro_Alloc == op) { /* ALLOC */
+    ir_type *type = get_Alloc_type (node);
 
-  interprocedural_view = old_ip_view; /* cover up our traces */
+    *change |= add_class (type);
+  }
 }
 
 /**
-   Find out whether the given method could be the target of a
-   polymorphic call.
+   Traverse the given graph to collect method accesses and
+   object allocations.
 */
-static int is_call_target (entity *method)
+static int rta_fill_graph (ir_graph* graph)
 {
-  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);
-  }
-
-  /* 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 |= is_call_target (over);
-  }
-
-  return (is_target);
+  int change = FALSE;
+  irg_walk_graph (graph, rta_act, NULL, &change);
+  return change;
 }
 
-/**
-   Given a method, find the firm graph that implements that method.
-*/
-static ir_graph *get_implementing_graph (entity *method)
+/** Traverse all graphs to collect method accesses and object allocations.
+ */
+static int rta_fill_incremental (void)
 {
-  ir_graph *graph = get_entity_irg ((entity*) method);
-
-  if (NULL == graph) {
-    int i;
-    int n_over = get_entity_n_overwrites ((entity*) method);
-
-    for (i = 0; (NULL == graph) && (i < n_over); i ++) {
-      entity *over = get_entity_overwrites ((entity*) method, i);
-      graph = get_implementing_graph (over);
-    }
-  }
-
-  /* we *must* always return a graph != NULL, *except* when we're used
-     inside remove_irg or force_description */
-  /* assert (graph && "no graph"); */
+  int i;
+  int n_runs = 0;
+  int rerun  = TRUE;
+  int old_ip_view = get_interprocedural_view();
 
-  return (graph);
-}
+  set_interprocedural_view(0);     /* save this for later */
 
-/**
-   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;
+  /* init_tables has added main_irg to _live_graphs */
 
-  if (graph != get_entity_irg ((entity*) method)) {
-    return (FALSE);
-  }
+  /* Need to take care of graphs that are externally
+     visible or sticky. Pretend that they are called: */
 
-  if (eset_contains (_called_methods, method)) {
-    return (TRUE);
-  }
+  for (i = 0; i < get_irp_n_irgs(); i++) {
+    ir_graph *graph = get_irp_irg (i);
+    entity *ent = get_irg_entity (graph);
 
-  /* 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);
+    if ((visibility_external_visible == get_entity_visibility (ent)) ||
+        (stickyness_sticky == get_entity_stickyness (ent))) {
+      eset_insert (_live_graphs, graph);
+      // printf("external visible: "); DDMG(graph);
+    }
   }
 
-  return (has_downcall);
-}
+  while (rerun) {
+    ir_graph *graph;
 
-/**
-   Determine whether the given method or one of its overwriters have
-   been used in a call to the given graph.
-*/
-static int has_live_call (entity *method, ir_graph *graph)
-{
-  /* maybe we're called (possibly through polymorphy)? */
-  if (is_call_target (method)) {
-    return (TRUE);
-  }
+    /* start off new */
+    eset *live_graphs = _live_graphs;
+    _live_graphs = eset_create ();
 
-  /* maybe our subclasses have seen a call? */
-  if (has_live_downcall (method, graph)) {
-    return (TRUE);
-  }
+    if (verbose > 1) {
+      fprintf(stdout, "RTA: RUN %i\n", n_runs);
+    }
 
-  return (FALSE);
-}
+    /* 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)) {
 
-/**
-   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)
-{
-  int has_class = FALSE;
-  int i;
-  int n_over;
-  type *clazz;
+      if (verbose > 1) {
+        fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
+        DDMEO(get_irg_entity (graph));
+      }
 
-  /* DON'T stop searching when an overwriting method provides a new graph */
+      rerun |= rta_fill_graph (graph);
+    }
 
-  clazz = get_entity_owner (method);
+    eset_destroy (live_graphs);
 
-  if (rta_is_alive_class (clazz)) {
-    return (TRUE);
+    n_runs ++;
   }
 
-  n_over = get_entity_n_overwrites (method);
-  for (i = 0; !has_class && (i < n_over); i ++) {
-    entity *over = get_entity_overwrites (method, i);
-    has_class |= has_live_class (over, graph);
-  }
+  set_interprocedural_view(old_ip_view); /* cover up our traces */
 
-  return (has_class);
+  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;
@@ -397,8 +333,7 @@ static void force_description (entity *ent, entity *addr)
 
     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)));
+      entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
 
       if (addr == my_addr) {
         force_description (over, addr);
@@ -406,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));
+      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);
@@ -417,126 +352,154 @@ 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.
+/**
+   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   verbose Iff != 0, print statistics as we go along
-*/
-void rta_init (int verbose, int 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;
+  int i, n, 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++) {
+  n = get_irp_n_irgs();
+  for (i = 0; i < n; i++) {
     irg_vrfy (get_irp_irg(i));
   }
   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 ();
+    int n_live_graphs = stats ();
 
-    if (verbose) {
-      printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
-    }
-  }
-
-  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++) {
+  for (i = 0; i < n; i++) {
     irg_vrfy (get_irp_irg(i));
   }
   tr_vrfy ();
 # endif /* defined DEBUG_libfirm */
+
+  set_visit_pseudo_irgs(rem_vpi);
 }
 
-/* Delete all graphs that we have found to be dead from the program */
-void rta_delete_dead_graphs ()
+/**
+ * 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) {
+    entity *ent = (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
+   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;
+
+  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);
 
-    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)));
+      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)) {
-    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 */
-void rta_cleanup ()
+void rta_cleanup (void)
 {
 # ifdef DEBUG_libfirm
   int i;
@@ -551,29 +514,14 @@ void rta_cleanup ()
     _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));
 }
@@ -581,55 +529,25 @@ 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)
 {
-  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 */
-void rta_report (FILE *stream)
+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)) {
-      fprintf(stream, "RTA: considered allocated: "); DDMT(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(stream, "RTA: considered called: graph of");
-      DDMEO(get_irg_ent (get_irp_irg(i)));
+      fprintf(stdout, "RTA: considered called: graph of ");
+      DDMEO(get_irg_entity (get_irp_irg(i)));
     }
   }
 }
@@ -637,6 +555,85 @@ void rta_report (FILE *stream)
 
 /*
  * $Log$
+ * 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)
+ *
+ * Revision 1.13  2004/06/17 16:34:33  liekweg
+ * removed DD*s
+ *
+ * Revision 1.12  2004/06/17 16:33:33  liekweg
+ * minor bug fix
+ *
  * Revision 1.11  2004/06/17 14:21:13  liekweg
  * major bugfix
  *