From 99071dec7d6174af4dde4f8a063b9d064e708cee Mon Sep 17 00:00:00 2001 From: Florian Liekweg Date: Thu, 17 Jun 2004 08:33:01 +0000 Subject: [PATCH] Added comments; added remove_irg [r3124] --- ir/ana/rta.c | 238 +++++++++++++++++++++++++++++++++++++++++---------- ir/ana/rta.h | 10 +++ 2 files changed, 205 insertions(+), 43 deletions(-) diff --git a/ir/ana/rta.c b/ir/ana/rta.c index f6becd8d4..53c279c29 100644 --- a/ir/ana/rta.c +++ b/ir/ana/rta.c @@ -25,20 +25,15 @@ #include "rta.h" #include -#include "cgana.h" /* get_implementation */ #include "irnode_t.h" #include "irprog.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 @@ -52,8 +47,9 @@ static eset *_called_methods = NULL; static eset *_live_graphs = NULL; static eset *_dead_graphs = NULL; -/* now the meat */ - +/** + Initialise the static data structures. +*/ static void init_tables (void) { _live_classes = eset_create (); @@ -73,29 +69,31 @@ static void init_tables (void) } /** - Enter all method and field accesses and all class allocations into our tables. + 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) { + if (iro_Call == op) { /* CALL */ entity *ent = NULL; ir_node *ptr = get_Call_ptr (node); - if (iro_Sel == get_irn_opcode (ptr)) { + if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */ ent = get_Sel_entity (ptr); - } else if (iro_Const == get_irn_opcode (ptr)) { + } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */ ent = get_tarval_entity (get_Const_tarval (ptr)); - } - /* assert (ent); */ + } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */ + assert (ent && "couldn't determine entity of call to symConst"); + } if (ent) { eset_insert (_called_methods, ent); } - } else if (iro_Load == op) { + } else if (iro_Load == op) { /* LOAD */ ir_node *ptr = get_Load_ptr (node); entity *ent = NULL; @@ -105,7 +103,7 @@ static void rta_act (ir_node *node, void *env) if (ent) { eset_insert (_live_fields, ent); } - } else if (iro_Store == op) { + } else if (iro_Store == op) { /* STORE */ ir_node *ptr = get_Store_ptr (node); entity *ent = NULL; @@ -115,7 +113,7 @@ static void rta_act (ir_node *node, void *env) if (ent) { eset_insert (_live_fields, ent); } - } else if (iro_Alloc == op) { + } else if (iro_Alloc == op) { /* ALLOC */ type *type = get_Alloc_type (node); eset_insert (_live_classes, type); @@ -123,18 +121,24 @@ static void rta_act (ir_node *node, void *env) } /** -Traverse the given graph to collect method and field accesses and object allocations. + Traverse the given graph to collect method and field accesses and + object allocations. */ static void rta_fill_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); } } } +/** + 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)) { @@ -145,7 +149,7 @@ static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs) return (FALSE); } - assert (0 && "what's up"); + assert (0 && "graph neither live not dead (shouldn't happen)"); } /** @@ -160,10 +164,9 @@ static void rta_fill_all (int rerun) eset *live_graphs = NULL; eset *dead_graphs = NULL; - interprocedural_view = 0; + interprocedural_view = 0; /* save this for later */ if (rerun) { - int i; int n_graphs = get_irp_n_irgs (); /* force all graphs to be entered in either live_graphs or dead_graphs */ @@ -183,11 +186,31 @@ static void rta_fill_all (int rerun) init_tables (); } - /* consider all graphs, possibly taking into account existing infos */ + /* 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 (!rerun || is_alive (graph, live_graphs, dead_graphs)) { + /* Need to take care of graphs that are externally + visible. Pretend that they are called: */ + entity *ent = get_irg_entity (graph); + if (visibility_local != 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); } } @@ -198,7 +221,7 @@ static void rta_fill_all (int rerun) eset_destroy (dead_graphs); } - interprocedural_view = old_ip_view; + interprocedural_view = old_ip_view; /* cover up our traces */ } /** @@ -245,7 +268,9 @@ static ir_graph *get_implementing_graph (const entity *method) } } - assert (graph && "no graph"); + /* we *must* always return a graph != NULL, *except* when we're used + inside remove_irg or force_description */ + /* assert (graph && "no graph"); */ return (graph); } @@ -260,7 +285,7 @@ static int has_live_call (entity *method, ir_graph *graph) int i, n_over; /* stop searching if a overwriting method comes with a new graph */ - if (get_irg_ent (graph) != method) { + if (get_irg_ent (graph) != method) { /* shouldn't we comare GRAPS????? */ return (FALSE); } @@ -326,8 +351,6 @@ static int has_live_class (entity *method, ir_graph *graph) int n_over; type *clazz; - /* const char *name = get_entity_name (method); */ - /* stop searching when an overwriting method provides a new graph */ if (get_implementing_graph (method) != graph) { return (FALSE); @@ -348,6 +371,12 @@ static int has_live_class (entity *method, ir_graph *graph) return (has_class); } +/* + 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. +*/ static int stats (void) { int i; @@ -365,15 +394,96 @@ static int stats (void) return (n_live_graphs); } +/* 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) +{ + 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 = + tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over))); + + if (addr == my_addr) { + force_description (over, addr); + } + } else if (peculiarity_existent == get_entity_peculiarity (over)) { + /* check wether '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)); + + assert ((get_irn_op(f_addr) == op_Const) && "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); + + /* 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))); + } +} + +/* Initialise the RTA data structures, and perform RTA. + @param verbose Iff != 0, print statistics as we go along +*/ void rta_init (int verbose) { int n_live_graphs = get_irp_n_irgs (); int n_graphs = 0; int n_runs = 0; +# 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 */ + init_tables (); - printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs); + 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) { @@ -381,6 +491,7 @@ void rta_init (int verbose) 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); } @@ -391,10 +502,56 @@ void rta_init (int verbose) 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)); + } + tr_vrfy (); +# endif /* defined DEBUG_libfirm */ +} + +/* Delete all graphs that we have found to be dead from the program */ +void rta_delete_dead_graphs () +{ + int i; + int n_graphs = get_irp_n_irgs (); + ir_graph *graph = NULL; + + eset *dead_graphs = eset_create (); + + for (i = 0; i < n_graphs; i++) { + graph = get_irp_irg(i); + + if (is_alive (graph, _live_graphs, _dead_graphs)) { + /* do nothing (except some debugging fprintf`s :-) */ + } else { + entity *ent = get_irg_entity (graph); + assert (visibility_external_visible != get_entity_visibility (ent)); + + eset_insert (dead_graphs, graph); + } + } + + /* now delete the graphs. */ + for (graph = eset_first (dead_graphs); + graph; + graph = (ir_graph*) eset_next (dead_graphs)) { + remove_irg (graph); + } } -void rta_cleanup (void) +/* Clean up the RTA data structures. Call this after calling rta_init */ +void rta_cleanup () { +# 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 (_live_classes) { eset_destroy (_live_classes); _live_classes = NULL; @@ -421,15 +578,15 @@ void rta_cleanup (void) } } +/* Say wether 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 wether this graph might be run at any time in the program: */ int rta_is_alive_graph (ir_graph *graph) { - entity *meth; - if (eset_contains (_live_graphs, graph)) { return (TRUE); } @@ -438,7 +595,7 @@ int rta_is_alive_graph (ir_graph *graph) return (FALSE); } - meth = get_irg_ent (graph); + entity *meth = get_irg_ent (graph); if (has_live_call (meth, graph) && has_live_class (meth, graph)) { eset_insert (_live_graphs, graph); @@ -451,6 +608,7 @@ int rta_is_alive_graph (ir_graph *graph) } } +/* Say wether there have been any accesses to this field: */ int rta_is_alive_field (entity *field) { return (eset_contains (_live_fields, field)); @@ -460,14 +618,8 @@ int rta_is_alive_field (entity *field) /* * $Log$ - * Revision 1.7 2004/06/15 11:44:54 beck - * New inlining schema implemented: - * - * small functions that should be inlined in libFirm are implemented in _t.h files - * with a __ prefix. - * Preprocessor magic is used to automatically inline these functions whenever a _t.h - * file is included instead of a .h file. - * Note that this magic did not work outside libFirm without accessing _t.h files. + * 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 diff --git a/ir/ana/rta.h b/ir/ana/rta.h index 01f917991..9debb65a4 100644 --- a/ir/ana/rta.h +++ b/ir/ana/rta.h @@ -5,17 +5,27 @@ # include "entity.h" +/* Initialise the RTA data structures and perform RTA */ void rta_init(int verbose); +/* Delete all graphs that have been found to be dead */ +void rta_delete_dead_graphs (void); +/* Clean up our data structures */ void rta_cleanup(void); +/* Inquire whether the given class is live */ int rta_is_alive_class(type *clazz); +/* Inquire whether the given graph is alive */ int rta_is_alive_graph(ir_graph *graph); +/* Inquire whether the given field is alive */ int rta_is_alive_field(entity *field); #endif /* def _RTA_H_ */ /* * $Log$ + * Revision 1.5 2004/06/17 08:33:01 liekweg + * Added comments; added remove_irg + * * Revision 1.4 2004/06/15 11:44:54 beck * New inlining schema implemented: * -- 2.20.1