/*
* 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: $$
* 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.
+ * die Menge der instantiierten Klassen bestimmt, und daraus eine Abschätzung
+ * der aufgerufenen Methoden bestimmt.
*/
#ifdef HAVE_CONFIG_H
#include "rta.h"
#include <stdlib.h>
-#include "cgana.h" /* get_implementation */
#include "irnode_t.h"
-#include "irprog.h"
+#include "irprog_t.h"
#include "eset.h"
-/* #include "pmap.h" */
-/* #include "array.h" */
#include "irgwalk.h"
-/* #include "ircons.h" */
-/* #include "irgmod.h" */
-/* #include "irflag_t.h" */
-
-/* #include "dbginfo_t.h" */
+#include "irgmod.h"
+#include "irvrfy.h"
+#include "trvrfy.h"
# define TRUE 1
# define FALSE 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;
-/* now the meat */
+static int whole_world = 0;
+static int verbose = 0;
-static void rta_act (ir_node *node, void *env)
+/**
+ Given a method, find the firm graph that implements that method.
+*/
+static ir_graph *get_implementing_graph (entity *method)
{
- opcode op = get_irn_opcode (node);
-
- if (iro_Call == op) {
- entity *ent = NULL;
-
- ir_node *ptr = get_Call_ptr (node);
- // TODO: test: ptr.op == Const
+ ir_graph *graph = get_entity_irg ((entity*) method);
- if (iro_Sel == get_irn_opcode (ptr)) {
- ent = get_Sel_entity (ptr);
- }
+ if (NULL == graph) {
+ int i;
+ int n_over = get_entity_n_overwrites ((entity*) method);
- if (ent) {
- eset_insert (_called_methods, ent);
+ for (i = 0; (NULL == graph) && (i < n_over); i ++) {
+ entity *over = get_entity_overwrites ((entity*) method, i);
+ graph = get_implementing_graph (over);
}
- } 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) {
- eset_insert (_live_fields, ent);
- }
- } else if (iro_Store == op) {
- ir_node *ptr = get_Store_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_Alloc == op) {
- type *type = get_Alloc_type (node);
- eset_insert (_live_classes, type);
- }
+ return (graph);
}
-static void rta_fill_graph (ir_graph* graph)
+static int add_graph (ir_graph *graph)
{
- if (NULL != graph) {
- if (NULL != get_irg_end_block (graph)) {
- irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL);
+ if (!eset_contains (_live_graphs, graph)) {
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: new graph of ");
+ DDMEO(get_irg_ent (graph));
}
+
+ eset_insert (_live_graphs, graph);
+ return (TRUE);
}
+
+ return (FALSE);
}
-static void rta_fill_all ()
+static int add_class (type *clazz)
{
- int i;
- int old_ip_view = interprocedural_view;
+ if (!eset_contains (_live_classes, clazz)) {
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: new class: ");
+ DDMT(clazz);
+ }
- interprocedural_view = 0;
- for (i = 0; i < get_irp_n_irgs(); i++) {
- rta_fill_graph (get_irp_irg (i));
+ eset_insert (_live_classes, clazz);
+ return (TRUE);
}
- interprocedural_view = old_ip_view;
+
+ return (FALSE);
}
-static int is_call_target (entity *method)
+/**
+ Given an entity, add all implementing graphs that belong to live classes to _live_graphs.
+
+ Iff additions occurred, return TRUE, else FALSE.
+*/
+static int add_implementing_graphs (entity *method)
{
- int is_target = FALSE;
int i;
- int n_over;
+ int n_over = get_entity_n_overwrittenby (method);
+ ir_graph *graph = get_entity_irg (method);
+ int change = FALSE;
- /* The method could be the target of a polymorphic call if it is
- called or if it overrides a method that is called. */
+ if (NULL == graph) {
+ graph = get_implementing_graph (method);
+ }
- if (eset_contains (_called_methods, method)) {
- return (TRUE);
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: new call to ");
+ DDMEO(method);
}
- n_over = get_entity_n_overwrittenby (method);
- for (i = 0; !is_target && (i < n_over); i ++) {
+ if (rta_is_alive_class (get_entity_owner (method))) {
+ if (NULL != graph) {
+ change = add_graph (graph);
+ }
+ }
+
+ for (i = 0; i < n_over; i ++) {
entity *over = get_entity_overwrittenby (method, i);
- is_target |= is_call_target (over);
+ change |= add_implementing_graphs (over);
}
- return (is_target);
+ return (change);
}
+/**
+ Enter all method accesses and all class allocations into
+ our tables.
-static ir_graph *get_implementing_graph (entity *method)
+ Set *(int*)env to true iff (possibly) new graphs have been found.
+*/
+static void rta_act (ir_node *node, void *env)
{
- ir_graph *graph = get_entity_irg (method);
+ int *change = (int*) env;
- if (NULL == graph) {
- int i;
- int n_over = get_entity_n_overwrites (method);
+ 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);
+ *change = add_implementing_graphs (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);
+ /* don't use get_implementing_graph on a Const! */
+ if (graph) {
+ *change = add_graph (graph);
+ } else {
+ /* it's an external allocated thing. */
+ }
+ } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
+ if (get_SymConst_kind(ptr) == symconst_addr_ent) {
+ ent = get_SymConst_entity (ptr);
+ ir_graph *graph = get_entity_irg (ent);
+ /* don't use get_implementing_graph on a SymConst! */
+ if (graph) {
+ *change = add_graph (graph);
+ } else {
+ /* it's an external allocated thing. */
+ }
+ } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
+ /* 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 {
+ /* other symconst. */
+ }
- for (i = 0; (NULL == graph) && (i < n_over); i ++) {
- entity *over = get_entity_overwrites (method, i);
- graph = get_implementing_graph (over);
}
+ } else if (iro_Alloc == op) { /* ALLOC */
+ type *type = get_Alloc_type (node);
+
+ *change = add_class (type);
}
+}
- assert (graph && "no graph");
+/**
+ Traverse the given graph to collect method accesses and
+ object allocations.
+*/
+static int rta_fill_graph (ir_graph* graph)
+{
+ int change = FALSE;
- return (graph);
+ current_ir_graph = graph;
+
+ irg_walk (get_irg_end (graph), rta_act, NULL, &change);
+
+ return (change);
}
-static int has_live_call (entity *method, ir_graph *graph)
+/**
+ Traverse all graphs to collect method accesses and object allocations.
+
+ @param rerun Whether to rely on is_alive in a second run
+*/
+static int rta_fill_incremental (void)
{
- int has_call = FALSE;
- int i, n_over;
+ int i;
+ int n_runs = 0;
+ int rerun = TRUE;
+ int old_ip_view = interprocedural_view;
- if (get_irg_ent (graph) != method) {
- return (FALSE);
- }
+ interprocedural_view = 0; /* save this for later */
- if (is_call_target (method)) {
- return (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; i < get_irp_n_irgs(); i++) {
+ ir_graph *graph = get_irp_irg (i);
+ entity *ent = get_irg_entity (graph);
- 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);
+ if (((!whole_world) &&
+ (visibility_external_visible == get_entity_visibility (ent))) ||
+ (stickyness_sticky == get_entity_stickyness (ent))) {
+ eset_insert (_live_graphs, graph);
+ }
}
- return (has_call);
-}
+ while (rerun) {
+ ir_graph *graph;
-static int has_graph (type *clazz, ir_graph *graph)
-{
- int has_the_graph = FALSE;
- int i;
- int n_sub;
+ /* start off new */
+ eset *live_graphs = _live_graphs;
+ _live_graphs = eset_create ();
+
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: RUN %i\n", n_runs);
+ }
- if (eset_contains (_live_classes, clazz)) {
- int n_meth = get_class_n_members (clazz);
+ /* collect what we have found previously */
+ eset_insert_all (_live_graphs, live_graphs);
- 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);
+ rerun = FALSE;
- if (impl == graph) {
- return (TRUE);
- }
- } /* is_method */
- } /* all methods */
- } /* _live_classes.contains (clazz) */
+ for (graph = eset_first (live_graphs);
+ graph;
+ graph = eset_next (live_graphs)) {
- n_sub = get_class_n_subtypes (clazz);
- for (i = 0; !has_the_graph && (i < n_sub); i ++) {
- type *sub = get_class_subtype (clazz, i);
+ if (verbose > 1) {
+ fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
+ DDMEO(get_irg_ent (graph));
+ }
- has_the_graph |= has_graph (sub, graph);
+ rerun |= rta_fill_graph (graph);
+ }
+
+ eset_destroy (live_graphs);
+
+ n_runs ++;
}
- return (has_the_graph);
+ interprocedural_view = old_ip_view; /* cover up our traces */
+
+ return (n_runs);
}
-static int has_live_class (entity *method, ir_graph *graph)
+/*
+ Count the number of graphs that we have found to be live.
+*/
+static int stats (void)
{
- int has_class = FALSE;
int i;
- int n_over;
- type *clazz;
-
- if (get_implementing_graph (method) != graph) {
- return (FALSE);
- }
+ int n_live_graphs = 0;
+ int n_graphs = get_irp_n_irgs();
- clazz = get_entity_owner (method);
- if (has_graph (clazz, graph)) {
- return (TRUE);
- }
+ for (i = 0; i < n_graphs; i++) {
+ ir_graph *graph = get_irp_irg(i);
- 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);
+ if (rta_is_alive_graph (graph)) {
+ n_live_graphs ++;
+ }
}
- return (has_class);
+ return (n_live_graphs);
}
-static int rta_check (ir_graph *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.
+*/
+/* Since we *know* that this entity will not be called, this is OK. */
+static void force_description (entity *ent, entity *addr)
{
- return (rta_is_alive_graph (graph));
+ 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);
+
+ if (peculiarity_inherited == get_entity_peculiarity (over)) {
+ /* We rely on the fact that cse is performed on the const_code_irg. */
+ 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 = get_SymConst_entity (f_addr);
+
+ 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.
+*/
+static void remove_irg (ir_graph *graph)
+{
+ entity *ent = get_irg_entity (graph);
+ peculiarity pec = get_entity_peculiarity (ent);
+
+ /* DDMEO (get_irg_ent(graph)); */
+
+ /* delete the ir_graph data */
+ set_entity_peculiarity (ent, peculiarity_description);
+ remove_irp_irg (graph);
+ /* remove_irp_irg also removes the entities' reference to the graph */
+ /*
+ if (NULL != get_entity_irg (ent)) {
+ set_entity_irg (ent, NULL);
+ }
+ */
+ set_entity_peculiarity (ent, pec);
+
+ /* 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)));
+ }
+}
-void rta_init ()
+/**
+ Initialise the static data structures.
+*/
+static void init_tables (void)
{
_live_classes = eset_create ();
- _live_fields = eset_create ();
- _called_methods = eset_create ();
_live_graphs = eset_create ();
- _dead_graphs = eset_create ();
- /*
- * shold be:
- * rta_fill_queue ()
- */
if (get_irp_main_irg ()) {
eset_insert (_live_graphs, get_irp_main_irg ());
}
- rta_fill_all ();
+ /* Adding the GlobalType is pointless, since its methods are always
+ called via a constant */
+ /*
+ if (get_glob_type ()) {
+ eset_insert (_live_classes, get_glob_type ());
+ }
+ */
}
-void rta_cleanup ()
+/* Initialise the RTA data structures, and perform RTA.
+ @param do_verbose If == 1, print statistics, if > 1, chatter about every detail
+ @param do_whole_world Iff != 0, assume whole-world
+*/
+void rta_init (int do_verbose, int do_whole_world)
{
+ int n_runs = 0;
+
+# ifdef DEBUG_libfirm
int i;
- int n_live_graphs = 0;
- int n_graphs = get_irp_n_irgs();
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ irg_vrfy (get_irp_irg(i));
+ }
+ tr_vrfy ();
+# endif /* defined DEBUG_libfirm */
- for (i = 0; i < n_graphs; i++) {
- ir_graph *graph = get_irp_irg(i);
+ whole_world = do_whole_world;
+ verbose = do_verbose;
- if (rta_check (graph)) {
- char *name = NULL;
+ init_tables ();
- n_live_graphs ++;
- name = get_entity_name (get_irg_ent (graph));
+ n_runs = rta_fill_incremental ();
+
+ if (verbose) {
+ int n_live_graphs = stats ();
- fprintf (stdout, "LIVE %s\n", name);
+ if (whole_world) {
+ printf ("RTA: whole-world assumption\n");
}
+ 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);
}
- fprintf (stdout, "RES %s: %i graphs, %i live\n", __FUNCTION__, n_graphs, n_live_graphs);
+# ifdef DEBUG_libfirm
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ irg_vrfy (get_irp_irg(i));
+ }
+ tr_vrfy ();
+# endif /* defined DEBUG_libfirm */
+}
- if (_live_classes) {
- eset_destroy (_live_classes);
- _live_classes = 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;
+
+ if (!get_optimize() || !get_opt_dead_method_elimination()) return;
+
+ eset *dead_graphs = eset_create ();
+
+ for (i = 0; i < n_graphs; i++) {
+ graph = get_irp_irg(i);
+
+ if (rta_is_alive_graph (graph)) {
+ /* do nothing (except some debugging fprintf`s :-) */
+ } else {
+# ifdef DEBUG_libfirm
+ entity *ent = get_irg_entity (graph);
+ assert (whole_world ||
+ (visibility_external_visible != get_entity_visibility (ent)));
+# endif /* defined DEBUG_libfirm */
+
+ n_dead_graphs ++;
+ eset_insert (dead_graphs, graph);
+ }
+ }
+
+ /* now delete the graphs. */
+ for (graph = eset_first (dead_graphs);
+ graph;
+ graph = (ir_graph*) eset_next (dead_graphs)) {
+
+ if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
+ fprintf(stdout, "RTA: removing graph of ");
+ DDMEO(get_irg_ent (graph));
+ }
+
+ remove_irg (graph);
}
- if (_live_fields) {
- eset_destroy (_live_fields);
- _live_fields = NULL;
+ if (verbose) {
+ printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
}
+}
+
+/* Clean up the RTA data structures. Call this after calling rta_init */
+void rta_cleanup (void)
+{
+# ifdef DEBUG_libfirm
+ int i;
+ for (i = 0; i < get_irp_n_irgs(); i++) {
+ irg_vrfy (get_irp_irg(i));
+ }
+ tr_vrfy ();
+# endif /* defined DEBUG_libfirm */
- if (_called_methods) {
- eset_destroy (_called_methods);
- _called_methods = NULL;
+ if (_live_classes) {
+ eset_destroy (_live_classes);
+ _live_classes = 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)
{
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)
{
if (eset_contains (_live_graphs, graph)) {
return (TRUE);
}
- if (eset_contains (_dead_graphs, graph)) {
- return (FALSE);
- }
-
- entity *meth = get_irg_ent (graph);
-
- if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
- eset_insert (_live_graphs, graph);
+ return (FALSE);
+}
- return (TRUE);
- } else {
- eset_insert (_dead_graphs, graph);
+/* dump our opinion */
+void rta_report (void)
+{
+ int i;
- return (FALSE);
+ 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(stdout, "RTA: considered allocated: "); DDMT(tp);
+ }
}
-}
-int rta_is_alive_field (entity *field)
-{
- return (eset_contains (_live_fields, field));
+ 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)));
+ }
+ }
}
-
/*
* $Log$
+ * 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
+ *
+ * Revision 1.10 2004/06/17 10:31:41 goetz
+ * irscc: bugfix, can now deal with loops not reachable from start
+ * cgana: bugfix, skip_Tuple
+ * rta: improved
+ *
+ * Revision 1.9 2004/06/17 08:56:03 liekweg
+ * Fixed typos in comments
+ *
+ * Revision 1.8 2004/06/17 08:33:01 liekweg
+ * Added comments; added remove_irg
+ *
+ * Revision 1.6 2004/06/14 13:02:03 goetz
+ * bugfixesbug
+ *
+ * Revision 1.5 2004/06/13 15:03:45 liekweg
+ * RTA auf Iterative RTA aufgebohrt --flo
+ *
+ * Revision 1.4 2004/06/12 19:35:04 liekweg
+ * Kommentare eingef"ugt --flo
+ *
* Revision 1.3 2004/06/12 17:09:46 liekweg
* RTA works, outedges breaks. "Yay." --flo
*
projects / libfirm / blobdiff