From 7a4700d9c8fe432f785a480fdb14231061aa2531 Mon Sep 17 00:00:00 2001 From: Florian Liekweg Date: Fri, 11 Jun 2004 18:24:18 +0000 Subject: [PATCH] Added RTA --flo [r3057] --- ir/ana/cgana.c | 156 ++++++++++----------- ir/ana/rta.c | 362 +++++++++++++++++++++++++++++++++++++++++++++++++ ir/ana/rta.h | 39 ++++++ 3 files changed, 481 insertions(+), 76 deletions(-) create mode 100644 ir/ana/rta.c create mode 100644 ir/ana/rta.h diff --git a/ir/ana/cgana.c b/ir/ana/cgana.c index 5199e72a0..1809e2f72 100644 --- a/ir/ana/cgana.c +++ b/ir/ana/cgana.c @@ -11,7 +11,7 @@ */ /** - * Intraprozedurale Analyse zur Abschätzung der Aufrulrelation. Es + * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es * wird eine Menge von freien Methoden und anschließend die an den * Call-Operationen aufrufbaren Methoden bestimmt. * @@ -22,6 +22,7 @@ #include #include "cgana.h" +#include "rta.h" #include "eset.h" @@ -50,7 +51,7 @@ static eset * entities = NULL; /* Bestimmt die eindeutige Methode, die die Methode für den * übergebenene (dynamischen) Typ überschreibt. */ -static entity * get_implementation(type * class, entity * method) { +entity * get_implementation(type * class, entity * method) { int i; if (get_entity_peculiarity(method) != peculiarity_description && get_entity_owner(method) == class) { @@ -68,7 +69,7 @@ static entity * get_implementation(type * class, entity * method) { return e; } } - assert(0 && "implemenation not found"); + assert(0 && "implementation not found"); return NULL; } @@ -82,7 +83,7 @@ entity *get_inherited_methods_implementation(entity *inh_meth) { if (intern_get_irn_op(addr) == op_Const) { impl_meth = tarval_to_entity(get_Const_tarval(addr)); } else { - assert(0 && "Complex constant values not supported -- adress of method should be straight constant!"); + assert(0 && "Complex constant values not supported -- address of method should be straight constant!"); } if (impl_meth && (get_entity_peculiarity(impl_meth) != peculiarity_existent)) { printf("this_meth: "); DDMEO(inh_meth); @@ -109,8 +110,8 @@ void collect_impls(entity *method, eset *set, int *size, bool *open) { } else { assert(get_entity_irg(method) != NULL); if (!eset_contains(set, method)) { - eset_insert(set, method); - ++(*size); + eset_insert(set, method); + ++(*size); } } } @@ -123,8 +124,8 @@ void collect_impls(entity *method, eset *set, int *size, bool *open) { } else { assert(get_entity_irg(impl_ent) != NULL); if (!eset_contains(set, impl_ent)) { - eset_insert(set, impl_ent); - ++(*size); + eset_insert(set, impl_ent); + ++(*size); } } } @@ -176,16 +177,16 @@ static entity ** get_impl_methods(entity * method) { #define SIZ(x) sizeof(x)/sizeof((x)[0]) #define DBG_OPT_NORMALIZE \ - __dbg_info_merge_pair(new_node, node, dbg_const_eval) + __dbg_info_merge_pair(new_node, node, dbg_const_eval) #define DBG_OPT_POLY_ALLOC \ do { \ - ir_node *ons[2]; \ - ons[0] = node; \ - ons[1] = skip_Proj(get_Sel_ptr(node)); \ - __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \ + ir_node *ons[2]; \ + ons[0] = node; \ + ons[1] = skip_Proj(get_Sel_ptr(node)); \ + __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \ } while(0) #define DBG_OPT_POLY \ - __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call) + __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call) static void sel_methods_walker(ir_node * node, pmap * ldname_map) { @@ -195,22 +196,22 @@ static void sel_methods_walker(ir_node * node, pmap * ldname_map) { if (get_SymConst_kind(node) == linkage_ptr_info) { pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node)); if (entry != NULL) { /* Method is declared in the compiled code */ - entity * ent = entry->value; - if (get_opt_normalize() && (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */ - ir_node *new_node; - assert(get_entity_irg(ent)); - set_irg_current_block(current_ir_graph, get_nodes_Block(node)); - new_node = new_d_Const(get_irn_dbg_info(node), - mode_P_mach, new_tarval_from_entity(ent, mode_P_mach)); DBG_OPT_NORMALIZE; - exchange(node, new_node); - } + entity * ent = entry->value; + if (get_opt_normalize() && (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */ + ir_node *new_node; + assert(get_entity_irg(ent)); + set_irg_current_block(current_ir_graph, get_nodes_Block(node)); + new_node = new_d_Const(get_irn_dbg_info(node), + mode_P_mach, new_tarval_from_entity(ent, mode_P_mach)); DBG_OPT_NORMALIZE; + exchange(node, new_node); + } } } } else if (intern_get_irn_op(node) == op_Sel && - is_method_type(get_entity_type(get_Sel_entity(node)))) { + is_method_type(get_entity_type(get_Sel_entity(node)))) { entity * ent = get_Sel_entity(node); if (get_opt_optimize() && get_opt_dyn_meth_dispatch() && - (intern_get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) { + (intern_get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) { ir_node *new_node; entity *called_ent; /* We know which method will be called, no dispatch necessary. */ @@ -218,7 +219,7 @@ static void sel_methods_walker(ir_node * node, pmap * ldname_map) { assert(get_entity_peculiarity(ent) != peculiarity_description); set_irg_current_block(current_ir_graph, get_nodes_Block(node)); /* @@@ Is this correct?? Alloc could reference a subtype of the owner - of Sel that overwrites the method referenced in Sel. */ + of Sel that overwrites the method referenced in Sel. */ /* @@@ Yes, this is wrong. GL, 10.3.04 */ new_node = copy_const_value(get_atomic_ent_value(ent)); DBG_OPT_POLY_ALLOC; #else @@ -232,55 +233,55 @@ static void sel_methods_walker(ir_node * node, pmap * ldname_map) { } else { assert(get_entity_peculiarity(ent) != peculiarity_inherited); if (!eset_contains(entities, ent)) { - /* Entity noch nicht behandelt. Alle (intern oder extern) - * implementierten Methoden suchen, die diese Entity - * überschreiben. Die Menge an entity.link speichern. */ - set_entity_link(ent, get_impl_methods(ent)); - eset_insert(entities, ent); + /* Entity noch nicht behandelt. Alle (intern oder extern) + * implementierten Methoden suchen, die diese Entity + * überschreiben. Die Menge an entity.link speichern. */ + set_entity_link(ent, get_impl_methods(ent)); + eset_insert(entities, ent); } if (get_entity_link(ent) == NULL) { - /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare - * Methode zurückgeben. Damit ist sie insbesondere nicht - * ausführbar und nicht erreichbar. */ - /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist - fuer die es keine Implementierung gibt. */ - if (get_entity_peculiarity(ent) == peculiarity_description) { - /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */ - printf("WARNING: Calling method description %s\n in method %s\n of class %s\n which has " - "no implementation!\n", get_entity_name(ent), - get_entity_name(get_irg_ent(current_ir_graph)), - get_type_name(get_entity_owner(get_irg_ent(current_ir_graph)))); - printf("This happens when compiling a Java Interface that's never really used, i.e., " - "no class implementing the interface is ever used.\n"); - } else { - exchange(node, new_Bad()); - } + /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare + * Methode zurückgeben. Damit ist sie insbesondere nicht + * ausführbar und nicht erreichbar. */ + /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist + fuer die es keine Implementierung gibt. */ + if (get_entity_peculiarity(ent) == peculiarity_description) { + /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */ + printf("WARNING: Calling method description %s\n in method %s\n of class %s\n which has " + "no implementation!\n", get_entity_name(ent), + get_entity_name(get_irg_ent(current_ir_graph)), + get_type_name(get_entity_owner(get_irg_ent(current_ir_graph)))); + printf("This happens when compiling a Java Interface that's never really used, i.e., " + "no class implementing the interface is ever used.\n"); + } else { + exchange(node, new_Bad()); + } } else { - entity ** arr = get_entity_link(ent); + entity ** arr = get_entity_link(ent); #if 0 - int i; - printf("\nCall site "); DDMN(node); - printf(" in "); DDME(get_irg_ent(current_ir_graph)); - printf(" can call:\n"); - for (i = 0; i < ARR_LEN(arr); i++) { - printf(" - "); DDME(arr[i]); - printf(" with owner "); DDMT(get_entity_owner(arr[i])); - } - printf("\n"); + int i; + printf("\nCall site "); DDMN(node); + printf(" in "); DDME(get_irg_ent(current_ir_graph)); + printf(" can call:\n"); + for (i = 0; i < ARR_LEN(arr); i++) { + printf(" - "); DDME(arr[i]); + printf(" with owner "); DDMT(get_entity_owner(arr[i])); + } + printf("\n"); #endif - if (get_opt_optimize() && get_opt_dyn_meth_dispatch() && - (ARR_LEN(arr) == 1 && arr[0] != NULL)) { - ir_node *new_node; - /* Die Sel-Operation kann immer nur einen Wert auf eine - * interne Methode zurückgeben. Wir können daher die - * Sel-Operation durch eine Const- bzw. SymConst-Operation - * ersetzen. */ - set_irg_current_block(current_ir_graph, get_nodes_Block(node)); - new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY; - exchange (node, new_node); - } + if (get_opt_optimize() && get_opt_dyn_meth_dispatch() && + (ARR_LEN(arr) == 1 && arr[0] != NULL)) { + ir_node *new_node; + /* Die Sel-Operation kann immer nur einen Wert auf eine + * interne Methode zurückgeben. Wir können daher die + * Sel-Operation durch eine Const- bzw. SymConst-Operation + * ersetzen. */ + set_irg_current_block(current_ir_graph, get_nodes_Block(node)); + new_node = copy_const_value(get_atomic_ent_value(arr[0])); DBG_OPT_POLY; + exchange (node, new_node); + } } } } @@ -384,9 +385,9 @@ static void callee_ana_proj(ir_node * node, long n, eset * methods) { ir_node * pred = get_Proj_pred(node); if (get_irn_link(pred) != MARK) { if (intern_get_irn_op(pred) == op_Tuple) { - callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods); + callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods); } else { - eset_insert(methods, MARK); /* free method -> unknown */ + eset_insert(methods, MARK); /* free method -> unknown */ } } break; @@ -444,9 +445,9 @@ static void callee_ana_node(ir_node * node, eset * methods) { for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) { entity * ent = get_Sel_method(node, i); if (ent) { - eset_insert(methods, ent); + eset_insert(methods, ent); } else { - eset_insert(methods, MARK); + eset_insert(methods, MARK); } } break; @@ -496,7 +497,7 @@ static void callee_walker(ir_node * call, void * env) { } for (ent = eset_first(methods); ent; ent = eset_next(methods)) { if (ent != MARK) { - ARR_APP1(entity *, arr, ent); + ARR_APP1(entity *, arr, ent); } } if (ARR_LEN(arr) == 0) { @@ -591,7 +592,7 @@ static void free_mark(ir_node * node, eset * set) { entity * ent = get_Sel_entity(node); if (is_method_type(get_entity_type(ent))) { for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) { - eset_insert(set, get_Sel_method(node, i)); + eset_insert(set, get_Sel_method(node, i)); } } break; @@ -652,7 +653,7 @@ static void free_ana_walker(ir_node * node, eset * set) { for (i = get_Call_arity(node) - 1; i >= 0; --i) { ir_node * pred = get_Call_param(node, i); if (mode_is_reference(intern_get_irn_mode(pred))) { - free_mark(pred, set); + free_mark(pred, set); } } break; @@ -663,7 +664,7 @@ static void free_ana_walker(ir_node * node, eset * set) { for (i = intern_get_irn_arity(node) - 1; i >= 0; --i) { ir_node * pred = get_irn_n(node, i); if (mode_is_reference(intern_get_irn_mode(pred))) { - free_mark(pred, set); + free_mark(pred, set); } } break; @@ -712,6 +713,9 @@ void cgana(int *length, entity ***free_methods) { entity ** free_meths; int i; + rta_init (); + rta_cleanup (); + sel_methods_init(); free_meths = get_free_methods(); callee_ana(); diff --git a/ir/ana/rta.c b/ir/ana/rta.c new file mode 100644 index 000000000..e136ce93a --- /dev/null +++ b/ir/ana/rta.c @@ -0,0 +1,362 @@ +/* -*- 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. + */ + +/** + * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es + * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden + * bestimmt. + */ + +#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; + +typedef struct rta_set +{ + rta_set_elt_t *_list; +} rta_set_t; + +# define SET_T rta_set_t + +# 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 */ + +static SET_T *_live_classes = NULL; +static SET_T *_live_fields = NULL; +static SET_T *_called_methods = NULL; + +/* cache computed results */ +static SET_T *_live_graphs = NULL; +static SET_T *_dead_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 () +{ + rta_set_t *set = (rta_set_t*) xmalloc (sizeof (rta_set_t)); + + set->_list = NULL; + + return (set); +} + +static void delete_set (rta_set_t *set) +{ + rta_set_elt_t *elt = set->_list; + + while (NULL != elt) { + rta_set_elt_t *old = elt; + elt = elt->_next; + + old->_next = NULL; + old->_obj = NULL; + free (old); + } + + free (set); +} + +static void set_insert (rta_set_t *set, void *obj) +{ + rta_set_elt_t *elt = (rta_set_elt_t*) xmalloc (sizeof (rta_set_elt_t)); + + elt->_obj = obj; + elt->_next = set->_list; + set->_list = elt; +} + +static int set_contains (rta_set_t *set, void *obj) +{ + rta_set_elt_t *elt = set->_list; + + while (NULL != elt) { + if (elt->_obj == obj) { + return (TRUE); + } + + elt = elt->_next; + } + + return (FALSE); +} +# endif /* defined RTA_SET */ + +/* now the meat */ + +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); + } +} + +static void rta_fill_graph (ir_graph* graph) +{ + irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL); +} + +static void rta_fill_all () +{ + int i; + + for (i = 0; i < get_irp_n_irgs(); i++) { + rta_fill_graph (get_irp_irg (i)); + } +} + +static int is_call_target (entity *method) +{ + return (TRUE); +} + + +static ir_graph *get_implementing_graph (entity *method) +{ + ir_graph *graph = get_entity_irg (method); + + if (NULL == graph) { + int i; + int n_over = get_entity_n_overwrites (method); + + for (i = 0; (NULL == graph) && (i < n_over); i ++) { + entity *over = get_entity_overwrites (method, i); + graph = get_implementing_graph (over); + } + } + + assert (graph && "no graph"); + + return (graph); +} + +static int has_live_call (entity *method, ir_graph *graph) +{ + 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); +} + +static int has_graph (type *clazz, ir_graph *graph) +{ + 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); +} + +static int has_live_class (entity *method, ir_graph *graph) +{ + 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); +} + + +void rta_init () +{ + fprintf (stdout, "BEGIN %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__); + + _live_classes = new_set (); + _live_fields = new_set (); + _called_methods = new_set (); + + _live_graphs = new_set (); + _dead_graphs = new_set (); + + fprintf (stdout, "FILL %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__); + rta_fill_all (); + fprintf (stdout, "DONE %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__); + + /* + * shold be: + * rta_fill_queue () + */ +} + +void rta_cleanup () +{ + 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; + } +} + +int rta_is_alive_class (type *clazz) +{ + return (set_contains (_live_classes, clazz)); +} + +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); + } +} + +int rta_is_alive_field (entity *field) +{ + return (set_contains (_live_fields, field)); +} + + + +/* + * $Log$ + * Revision 1.1 2004/06/11 18:24:18 liekweg + * Added RTA --flo + * + */ diff --git a/ir/ana/rta.h b/ir/ana/rta.h new file mode 100644 index 000000000..4a5319c44 --- /dev/null +++ b/ir/ana/rta.h @@ -0,0 +1,39 @@ +/* -*- c -*- */ + +#ifndef _RTA_H_ +#define _RTA_H_ + +#ifdef HAVE_CONFIG_H +# include +#endif + +#include +#include "cgana.h" /* get_implementation */ + +#include "eset.h" +/* #include "pmap.h" */ +/* #include "array.h" */ +#include "irprog.h" +#include "irgwalk.h" +/* #include "ircons.h" */ +/* #include "irgmod.h" */ +#include "irnode_t.h" +/* #include "irflag_t.h" */ + +/* #include "dbginfo_t.h" */ + +void rta_init (void); +void rta_cleanup (void); + +int rta_is_alive_class (type*); +int rta_is_alive_graph (ir_graph*); +int rta_is_alive_field (entity*); + +#endif /* def _RTA_H_ */ + +/* + * $Log$ + * Revision 1.1 2004/06/11 18:24:18 liekweg + * Added RTA --flo + * + */ -- 2.20.1