From ca913a4d0dd937845c6c951602e03f4a1948f574 Mon Sep 17 00:00:00 2001 From: Florian Liekweg Date: Wed, 20 Oct 2004 14:59:42 +0000 Subject: [PATCH] Added ana2, added ecg and pto [r4166] --- ir/ana2/ecg.c | 1641 +++++++++++++++++++++++++++++++++++++++++++++++++ ir/ana2/ecg.h | 65 ++ ir/ana2/pto.c | 319 ++++++++++ ir/ana2/pto.h | 38 ++ 4 files changed, 2063 insertions(+) create mode 100644 ir/ana2/ecg.c create mode 100644 ir/ana2/ecg.h create mode 100644 ir/ana2/pto.c create mode 100644 ir/ana2/pto.h diff --git a/ir/ana2/ecg.c b/ir/ana2/ecg.c new file mode 100644 index 000000000..4d2d32eff --- /dev/null +++ b/ir/ana2/ecg.c @@ -0,0 +1,1641 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana/ecg.c + * Purpose: Extended Call Graph + * Author: Florian + * Modified by: + * Created: 14.09.2004 + * CVS-ID: $$ + * Copyright: (c) 1999-2004 Universität Karlsruhe + * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifdef HAVE_CONFIG_H +# include +#endif + +/** + Erweiterter Aufrufgraph. + */ + +#include "irnode.h" +#include "pmap.h" +/* #include "eset.h" */ +#include "irgwalk.h" +#include "irgmod.h" +#include "irvrfy.h" +#include "trvrfy.h" +#include "xmalloc.h" + +# define TRUE 1 +# define FALSE 0 + +# define BUF_SIZE 1024 + +# include "ecg.h" + +#include /* need memset */ + +/* + data structures +*/ + +/* Lists, err, Sets */ +typedef struct lset_entry +{ + void *data; + struct lset_entry *next; +} lset_entry_t; + +typedef struct lset +{ + lset_entry_t *first; + lset_entry_t *last; /* useful for lset_append */ + lset_entry_t *curs; /* for lset_first/lset_next */ + int n_entries; +} lset_t; + + +typedef enum typalise_kind_enum { + type_invalid = 0, /* invalid (only set at deletion time) */ + type_exact = 1, /* this and only this type (res.type) */ + type_types = 2, /* these types (res.types) */ + type_type = 3 /* this type and sub types (res.type) */ +} typalise_kind; + +typedef struct typalise +{ + typalise_kind kind; + union + { + type *type; /* for kind == kind_exact and kind == kind_type */ + lset_t *types; /* for kind == kind_types */ + } res; + int id; +} typalise_t; + +/* + le flag +*/ +/* static int verbose = 0; */ +static int do_typalise = 0; + +/* + globals +*/ + +/* mapping from method graphs (callR) to method graphs (lset_ts of callEds) */ +/* static pmap *calls; */ +static pmap *graph_infos; + +/** Counters for ecg_ecg and friends */ +static long _graphs = 0; +static long _calls = 0; +static long _allocs = 0; + +static int _depth = 0; +static int _max_depth = 0; + +static int _max_callEds = 0; +static entity* _max_callEds_callR = NULL; + +static long ta_id = 0; + +/* + Lists, err, Sets + */ + + +/* create a new lset */ +static lset_t *lset_create (void) +{ + lset_t *lset = xmalloc (sizeof (lset_t)); + + return (lset); +} + +/* check whether the lset contains an entry for the given data */ +static int lset_contains (lset_t *lset, void *data) +{ + lset_entry_t *entry = lset->first; + + while (NULL != entry) { + if (data == entry->data) { + return (TRUE); + } + + entry = entry->next; + } + + return (FALSE); +} + +/* check whether the given lset is empty */ +static int lset_empty (lset_t *lset) +{ + return (NULL == lset->first); +} + + +/* insert the data into the lset (unless there's an entry for it + already) */ +static void lset_insert (lset_t *lset, void *data) +{ + if (! lset_contains (lset, data)) { + lset_entry_t *entry = xmalloc (sizeof (lset_entry_t)); + entry->data = data; + entry->next = lset->first; + lset->first = entry; + + if (NULL == lset->last) { + lset->last = entry; + } + + lset->n_entries ++; + } +} + +/* insert all entries from src into tgt */ +static void lset_insert_all (lset_t *tgt, lset_t *src) +{ + lset_entry_t *curs = src->first; + + while (NULL != curs) { + lset_insert (tgt, curs->data); + + curs = curs->next; + } +} + +/* append src to tgt. src is deallocated. */ +static void lset_append (lset_t *tgt, lset_t *src) +{ + assert (! tgt->last->next); + + tgt->last->next = src->first; + tgt->last = src->last; + tgt->n_entries += src->n_entries; + + memset (src, 0x00, sizeof (lset_t)); + free (src); +} + +/* remove the entry for the given data element from the lset. return + TRUE iff it was on the list in the first place, FALSE else */ +# ifdef SHUT_UP_GCC +static int lset_remove (lset_t *lset, void *data) +{ + lset_entry_t *entry = lset->first; + lset_entry_t *prev = NULL; + + while (NULL != entry) { + if (data == entry->data) { + /* ok, dike it out */ + + if (NULL == prev) { /* ok, it's lset->first that needs diking */ + lset->first = entry->next; + } else { + prev->next = entry->next; + } + + memset (entry, 0x00, sizeof (lset_entry_t)); + free (entry); + + lset->n_entries --; + + return (TRUE); + } + + prev = entry; + entry = entry->next; + } + + return (FALSE); +} +# endif /* def SHUT_UP_GCC */ +/* prepare the given lset for an iteration. return the first element. */ +static void *lset_first (lset_t *lset) +{ + lset->curs = lset->first; + + if (lset->first) { + return (lset->first->data); + } else { + return (NULL); + } +} + +/* after calling lset_first, get the next element, if applicable, or + NULL */ +static void *lset_next (lset_t *lset) +{ + lset->curs = lset->curs->next; + + if (lset->curs) { + return (lset->curs->data); + } else { + return (NULL); + } +} + +/* say how many entries there are in the given lset */ +static int lset_n_entries (lset_t *lset) +{ + return (lset->n_entries); +} + +/* deallocate the lset and all of its entries */ +static void lset_destroy (lset_t *lset) +{ + lset_entry_t *curs = lset->first; + + while (NULL != curs) { + lset_entry_t *tmp = curs->next; + + memset (curs, 0x00, sizeof (lset_entry_t)); + free (curs); + + curs = tmp; + } + + memset (lset, 0x00, sizeof (lset_t)); + free (lset); +} + +/* ==================== + Typalize Ptr + ==================== */ +/** + Find out whether the given clazz uses the given implementation of a + method. Presumably, this is because clazz inherits the graph as + the implementation for a method. +*/ +static int uses_graph (type *clazz, entity *meth, ir_graph *graph) +{ + type *g_clazz = get_entity_owner (meth); + + if (g_clazz == clazz) { + return (TRUE); + } + + if (peculiarity_existent == get_entity_peculiarity (meth)) { + ir_graph *g_graph = get_entity_irg (meth); + + if (g_graph != graph) { + return (FALSE); + } + } + + /* else inherited or description */ + int use = FALSE; + int i; + int n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */ + + for (i = 0; (i < n_over) && (!use); i ++) { + entity *over = get_entity_overwrittenby (meth, i); + + use |= uses_graph (clazz, over, graph); + } + + return (use); +} + + +/** + Find out whether otype is a subtype of stype. + Return non-zero iff otype is a subtype of stype. +*/ +static int is_subtype (type *otype, type *stype) +{ + int n_sub = get_class_n_subtypes (stype); + int is_sub = FALSE; + int i; + + if (otype == stype) { + return (TRUE); + } + + for (i = 0; (!is_sub) && (i < n_sub); i ++) { + type *sub = get_class_subtype (stype, i); + + is_sub |= is_subtype (otype, sub); + } + + + return (is_sub); +} + +/** + Compute the closure of all subtypes of otype (including otype + itself) +*/ +static void _collect_subtypes (type *otype, lset_t *set) +{ + lset_insert (set, otype); + + int n_sub = get_class_n_subtypes (otype); + int i; + + for (i = 0; i < n_sub; i ++) { + type *sub = get_class_subtype (otype, i); + + _collect_subtypes (sub, set); + } +} + +static lset_t *subtype_closure (type *otype) +{ + lset_t *set = lset_create (); + + _collect_subtypes (otype, set); + + return (set); +} + +/** + Helper method for get_owner_types +*/ +static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps) +{ + /* search DOWNwards in clazz hierarchy */ + + if ((peculiarity_description == get_entity_peculiarity (method)) || + (peculiarity_inherited == get_entity_peculiarity (method))) { + lset_insert (tps, get_entity_owner (method)); + } else if (peculiarity_existent == get_entity_peculiarity (method)) { + ir_graph *ex_graph = get_entity_irg (method); + + if ((NULL == ex_graph) || (ex_graph == graph)) { + /* wtf? they define the same graph again? well, whatever: */ + lset_insert (tps, get_entity_owner (method)); + } else { + /* aha: they define a new graph. can't have that, so bail out */ + return; + } + } + + int n_over = get_entity_n_overwrittenby (method); + int i; + + for (i = 0; i < n_over; i ++) { + entity *ometh = get_entity_overwrittenby (method, i); + + _collect_owner_types (ometh, graph, tps); + } +} + + +/** + Collect all classes that use the given implementation of a method. +*/ +static lset_t *get_owner_types (ir_graph *graph) +{ + lset_t *tps = lset_create (); + entity *meth = get_irg_entity (graph); + + _collect_owner_types (meth, graph, tps); + + return (tps); +} + + +/** + Convenience funcs to create a typalise_t +*/ +static typalise_t *ta_exact (type *tp) +{ + typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t)); + ta->kind = type_exact; + ta->res.type = tp; + ta->id = ta_id ++; + + assert (is_class_type (tp)); + + return (ta); +} + +static typalise_t *ta_types (lset_t *set) +{ + typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t)); + ta->kind = type_types; + ta->res.types = set; + ta->id = ta_id ++; + + return (ta); +} + +static typalise_t *ta_type (type *tp) +{ + typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t)); + ta->kind = type_type; + ta->res.type = tp; + ta->id = ta_id ++; + + assert (is_class_type (tp)); + + return (ta); +} + +static void ta_delete (typalise_t *ta) +{ + if (type_types == ta->kind) { + lset_destroy (ta->res.types); + ta->res.types = NULL; + } else { + ta->res.type = NULL; + } + + ta->kind = type_invalid; + + free (ta); +} + +/** + Join 'one' and 'two'; both args are deallocated, result is freshly + allocated. +*/ +static typalise_t *ta_join (typalise_t *one, typalise_t *two) +{ + typalise_t *res = NULL; + + switch (one->kind) { + case (type_invalid): { /* shut up, gcc */ } + case (type_exact): { + switch (two->kind) { + case (type_invalid): { /* shut up, gcc */ } + case (type_exact): { + if (one->res.type == two->res.type) { + res = one; + } else { + lset_t *set = lset_create (); + lset_insert (set, one->res.type); + lset_insert (set, two->res.type); + res = ta_types (set); + + ta_delete (one); + } + + ta_delete (two); + } break; + case (type_types): { + lset_insert (two->res.types, one->res.type); + ta_delete (one); + + res = two; + } break; + case (type_type): { + if (is_subtype (one->res.type, two->res.type)) { + ta_delete (one); + res = two; + } else { + lset_t *closure = subtype_closure (two->res.type); + lset_insert (closure, one->res.type); + + ta_delete (two); + + res = one; + } + } break; + } + } break; + case (type_types): { + switch (two->kind) { + case (type_invalid): { /* shut up, gcc */ } + case (type_exact): { + res = ta_join (two, one); + } break; + case (type_types): { + lset_insert_all (one->res.types, two->res.types); + ta_delete (two); + + res = one; + } break; + case (type_type): { + lset_t *closure = subtype_closure (two->res.type); + lset_append (one->res.types, closure); + + ta_delete (two); + + res = one; + } break; + } + } break; + case (type_type): { + switch (two->kind) { + case (type_invalid): { /* shut up, gcc */ } + case (type_exact): { + res = ta_join (two, one); + } break; + case (type_types): { + res = ta_join (two, one); + } break; + case (type_type): { + type *one_type = one->res.type; + type *two_type = two->res.type; + + if (is_subtype (one_type, two_type)) { + ta_delete (one); + res = two; + } else if (is_subtype (two_type, one_type)) { + ta_delete (two); + res = one; + } else { + lset_t *one_closure = subtype_closure (one->res.type); + lset_t *two_closure = subtype_closure (two->res.type); + + lset_append (one_closure, two_closure); + + ta_delete (two); + ta_delete (one); + + res = ta_types (one_closure); + } + } break; + } + } break; + } + + assert (res && "no result"); + + return (res); +} + + +# ifdef SHUT_UP_GCC +static const char *ta_name (typalise_t *ta) +{ + /* # define BUF_SIZE 1024 */ + static char buf [BUF_SIZE]; + + int len = sprintf (buf, "[%d] ", ta->id); + + switch (ta->kind) { + case (type_invalid): { /* shut up, gcc */ } + case (type_exact): { + len += sprintf (buf+len, "only "); + strncat (buf, get_type_name (ta->res.type), BUF_SIZE); + } break; + case (type_types): { + len += sprintf (buf+len, "one_of "); + + type *iter = lset_first (ta->res.types); + + int size = BUF_SIZE - len - 1; + while ((NULL != iter) && (0 < size)) { + char *dest = strncat (buf, get_type_name (iter), size); + size = (dest - buf); + + iter = lset_next (ta->res.types); + } + } break; + case (type_type): { + len += sprintf (buf+len, "poly "); + strncat (buf, get_type_name (ta->res.type), BUF_SIZE); + } break; + } + + return (buf); + /* # undef BUF_SIZE */ +} +# endif /* SHUT_UP_GCC */ + +/** + Check whether the given typalise_t includes the given type. +*/ +static int ta_supports (typalise_t *ta, ir_graph *graph) +{ + switch (ta->kind) { + case (type_invalid): { /* shut up, gcc */ } + case (type_exact): { + int res = FALSE; + lset_t *tps = get_owner_types (graph); + + if (lset_contains (tps, ta->res.type)) { + res = TRUE; + } + + lset_destroy (tps); + + return (res); + } + case (type_type): { + entity *meth = get_irg_entity (graph); + type *tp = get_entity_owner (meth); + int res = is_subtype (tp, ta->res.type); + + if (res) { + return (TRUE); + } else { + res = uses_graph (ta->res.type, meth, graph); + } + + return (res); + } + case (type_types): { + type *tp = get_entity_owner (get_irg_entity (graph)); + + return (lset_contains (ta->res.types, tp)); + } + } + + assert (0 && "invalid ta"); +} + + +/** + Given a set of graphs and a typalise_t, return the method (s) in + the set that are supported by the typalise_t. Also, deallocates + the given set. +*/ +static lset_t *filter_for_ta (lset_t *set, typalise_t *ta) +{ + lset_t *res = lset_create (); + ir_graph *curs = (ir_graph*) lset_first (set); + + while (NULL != curs) { + if (ta_supports (ta, curs)) { + lset_insert (res, curs); + } + + curs = lset_next (set); + } + + lset_destroy (set); + + return (res); +} + + +/** + Return a list containing all types of 'set' which are a subtype of 'type'. +*/ +static lset_t *filter_for_type (lset_t *set, type *stype) +{ + type *curs = (type*) lset_first (set); + lset_t *lset = lset_create (); + + while (NULL != curs) { + if (is_subtype (curs, stype)) { + lset_insert (lset, curs); + } + + curs = lset_next (set); + } + + return (lset); +} + +/** + Find an approximation to the given node's value's types +*/ +static typalise_t *typalise (ir_node*); + +/** + Find an approximation to the given proj node's value's types +*/ +static typalise_t *typalise_proj (ir_node *proj) +{ + typalise_t *res = NULL; + ir_node *proj_in = get_Proj_pred (proj); + + if (iro_Proj == get_irn_opcode (proj_in)) { + /* fprintf (stdout, "\tProj (Proj)\n"); */ + + proj_in = get_Proj_pred (proj_in); + if (iro_Start == get_irn_opcode (proj_in)) { + long n = get_Proj_proj (proj); + if (1 == n) { + /* yay proj this */ + ir_graph *graph = get_irn_irg (proj); + entity *meth = get_irg_entity (graph); + type *tp = get_entity_owner (meth); + + /* res = ta_exact (tp); */ + res = ta_type (tp); /* TODO */ + } else { + /* ugh proj arg */ + /* hey, even 'filtering' this NULL by the select of the actual + call is probably as "precise" as anything: */ + return (NULL); + } + } else if (iro_Call == get_irn_opcode (proj_in)) { + /* call result ... 'whatever' */ + ir_node *call_ptr = get_Call_ptr (proj_in); + + res = typalise (call_ptr); + } else { + fprintf (stdout, "\n Proj (Proj (%s)) not handled\n", + get_op_name (get_irn_op (proj_in))); + assert (0); + } + } else { + opcode op = get_irn_opcode (proj_in); + if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) { + fprintf (stdout, "\n Proj (%s) not handled\n", + get_op_name (get_irn_op (proj_in))); + assert (0); + } + res = typalise (proj_in); /* everything else */ + /* Proj (Load), Proj (New), Proj (Call) */ + } + + return (res); +} + + +/** + For the given ptr, do a quick check about what (class) types may be + brought along on it. +*/ +static typalise_t *typalise (ir_node *node) +{ + opcode op = get_irn_opcode (node); + typalise_t *res = NULL; + + switch (op) { + case (iro_Cast): { + /* casts always succeed */ + typalise_t *ta = NULL; + type *tp = get_Cast_type (node); + + if (is_pointer_type (tp)) { + tp = get_pointer_points_to_type (tp); + } + assert (is_class_type (tp)); + + ta = typalise (get_Cast_op (node)); + + if (NULL == ta) { /* no type found */ + ta = ta_type (tp); + } else if (type_exact == ta->kind) { /* one type found */ + /* nothing (maybe check cast? */ + } else if (type_type == ta->kind) { /* some types found */ + if (is_subtype (tp, ta->res.type)) { + ta->res.type = tp; /* assume cast is correct */ + } else { + /* should assert (is_subtype (ta->res.type, tp)) */ + } + } else if (type_types == ta->kind) { + lset_t *ftp = filter_for_type (ta->res.types, tp); + lset_destroy (ta->res.types); + ta->res.types = ftp; + } + + res = ta; + } break; + + case (iro_Proj): { + res = typalise_proj (node); + } break; + + case (iro_Load): { + /* presumably it's call (load (ptr)) we're analyzing. */ + ir_node *load_ptr = get_Load_ptr (node); + + res = typalise (load_ptr); + } break; + + case (iro_Sel): { + /* FILTER */ + /* it's call (sel (ptr)) or load (sel (ptr)) */ + entity *ent = get_Sel_entity (node); + type *tp = get_entity_type (ent); + + if (is_method_type (tp)) { + tp = get_entity_type (ent); + tp = get_method_res_type (tp, 0); + + if (is_pointer_type (tp)) { + tp = get_pointer_points_to_type (tp); + } + + res = ta_type (tp); + } else if (is_class_type (tp)) { + tp = get_entity_type (ent); + + if (is_pointer_type (tp)) { + tp = get_pointer_points_to_type (tp); + } + + res = ta_type (tp); + } else if (is_pointer_type (tp)) { + tp = get_pointer_points_to_type (tp); + res = ta_type (tp); + } else { + assert (0 && "select not handled"); + } + } break; + + case (iro_Phi): { + int n_ins = get_irn_arity (node); + int i; + ir_node *phi_in = NULL; + typalise_t *ta = NULL; + /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */ + + for (i = 0; i < n_ins; i ++) { + phi_in = get_irn_n (node, i); + ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in)); + } + + res = ta; + } break; + + case (iro_Alloc): { + type *type = get_Alloc_type (node); + res = ta_exact (type); + } break; + + case (iro_Call): { + /* presumably call (sel (proj (call))) */ + ir_node *ptr = get_Call_ptr (node); + entity *meth = NULL; + if (iro_Sel == get_irn_opcode (ptr)) { + meth = get_Sel_entity (ptr); + } else if (iro_SymConst == get_irn_opcode (ptr)) { + if (get_SymConst_kind (ptr) == symconst_addr_ent) { + meth = get_SymConst_entity (ptr); + } else { + meth = NULL; /* WTF? */ + } + } + + if (NULL != meth) { + type *tp = get_method_res_type ((type*) meth, 0); + res = ta_type (tp); + } else { + /* could be anything */ + /* fprintf (stdout, "meth= (null)"); */ + res = NULL; + } + + fprintf (stdout, "]\n"); + + } break; + + case (iro_SymConst): { + if (get_SymConst_kind (node) == symconst_type_tag) { + type *tp = get_SymConst_type (node); + + res = ta_type (tp); + } else if (get_SymConst_kind (node) == symconst_addr_ent) { + entity *ent = get_SymConst_entity (node); + type *tp = get_entity_type (ent); + tp = get_pointer_points_to_type (tp); + assert (is_class_type (tp)); + + res = ta_type (tp); /* can't use ta_exact */ + } else { + fprintf (stdout, "can't handle SymConst %s?\n", + get_op_name (get_irn_op (node))); + res = NULL; + } + } break; + + /* template: + case (iro_Cast): {} + break; + */ + + default: { + fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node))); + assert (0); + } break; + } + + return (res); +} + + +/* ==================== + Alloc stuff + ==================== */ +static void append_alloc (graph_info_t *ginfo, ir_node *alloc, type *tp) +{ + alloc_info_t *ainfo = (alloc_info_t*) xmalloc (sizeof (alloc_info_t)); + + ainfo->graph = ginfo->graph; + ainfo->alloc = alloc; + ainfo->tp = tp; + + ainfo->prev = ginfo->allocs; + ginfo->allocs = ainfo; +} + + +/* ==================== + CallEd stuff + ==================== */ +/** + Append the given callEd to the given callEd info. +*/ +static callEd_info_t *append_callEd_info (callEd_info_t *ced, ir_graph *callEd) +{ + callEd_info_t *nced = (callEd_info_t*) xmalloc (sizeof (sizeof (callEd_info_t))); + + nced->callEd = callEd; + nced->prev = ced; + + return (nced); +} + +/** + Append all callEd methods of the given (call) node to the given graph_info. +*/ +static void append_calls (graph_info_t *info, ir_node *call, lset_t *callEds) +{ + call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t)); + + /* setup */ + cinfo->call = call; + cinfo->prev = info->calls; + info->calls = cinfo; + cinfo->callEds = NULL; + + /* enter */ + ir_graph *callEd = lset_first (callEds); + while (callEd) { + cinfo->callEds = append_callEd_info (cinfo->callEds, callEd); + + callEd = lset_next (callEds); + } +} + +/** + Append the (single) callEd to the given (call) node of the given graph_info. +*/ +static void append_call (graph_info_t *info, ir_node *call, ir_graph *callEd) +{ + call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t)); + + cinfo->call = call; + cinfo->prev = info->calls; + info->calls = cinfo; + + cinfo->callEds = append_callEd_info (cinfo->callEds, callEd); +} + +/** + Given a method, find the firm graph that implements that method. + Return NULL for abstract and native methods. +*/ +static ir_graph *_get_implementing_graph (entity *method) +{ + ir_graph *graph = NULL; + + /* What's up with the fenced out stuff in rta? */ + if (peculiarity_existent == get_entity_peculiarity (method)) { + if (visibility_external_allocated == get_entity_visibility (method)) { + /* Todo: native implementation */ + + return (NULL); + } else { + graph = get_entity_irg (get_SymConst_entity (get_atomic_ent_value (method))); + assert (graph && "no graph"); + + return (graph); + } + } else if (0 && (peculiarity_description == get_entity_peculiarity (method))) { + /* abstract --- can't find an implementation */ + graph = get_entity_irg (method); + assert (!graph && "graph in abstract method"); + + return (NULL); + } else if ((peculiarity_description == get_entity_peculiarity (method)) || + (peculiarity_inherited == get_entity_peculiarity (method))) { + /* search UPWARDS */ + int i; + int n_over = get_entity_n_overwrites (method); + + assert (!graph); + + for (i = 0; (NULL == graph) && (i < n_over); i ++) { + entity *over = get_entity_overwrites (method, i); + + graph = _get_implementing_graph (over); + } + } else { + assert (0 && "invalid peculiarity"); + } + + + return (graph); +} + +/** + Collect all graphs of 'method' in the given set. +*/ +static void _collect_implementing_graphs (entity *method, lset_t *set) +{ + /* search DOWN-wards in clazz hierarchy */ + int i; + int n_over = get_entity_n_overwrittenby (method); + ir_graph *graph = get_entity_irg (method); + + if (NULL == graph) { + graph = _get_implementing_graph (method); + } + + if (graph) { + lset_insert (set, graph); + } + + for (i = 0; i < n_over; i ++) { + entity *over = get_entity_overwrittenby (method, i); + + _collect_implementing_graphs (over, set); + } +} + + +/** + Collect all graphs that could possibly be executed when 'method' is called. +*/ +static lset_t *get_implementing_graphs (entity *method, ir_node *select) +{ + lset_t *set = lset_create (); + { + ir_graph *impl = _get_implementing_graph (method); + + if (NULL != impl) { + lset_insert (set, impl); + } else { + /* actually, abstract OR native */ + } + } + + _collect_implementing_graphs (method, set); + + if (lset_empty (set)) { + /* then it's a method which is only implemented natively, and we + don' bother to analyse anything */ + return (set); + } + + /* void *tmp = lset_first (set); */ + int n_graphs = lset_n_entries (set); + + /* typalise select_in */ + if (do_typalise) { + ir_node *select_in = get_Sel_ptr (select); + typalise_t *ta = typalise (select_in); + assert (ta && "typalise failed (go figure)"); + + /* const char *res = ta_name (ta); */ + + /* fprintf (stdout, "typalyse res = %s\n", res); */ + + if (1 != n_graphs) { + set = filter_for_ta (set, ta); + + int n_filtered_graphs = lset_n_entries (set); + + /* + fprintf (stdout, "%s: %02d %02d\n", + __FUNCTION__, + n_graphs, + n_filtered_graphs, + n_graphs - n_filtered_graphs); + */ + n_graphs = n_filtered_graphs; + } + } + + if (n_graphs > _max_callEds) { + _max_callEds = n_graphs; + _max_callEds_callR = method; + } + + + if (visibility_external_allocated != get_entity_visibility (method)) { + if (0 == n_graphs) { + /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */ + assert (n_graphs && "no graphs for method"); + } + } + + return (set); +} + +/** + Action for the graph. +*/ +static void ecg_calls_act (ir_node *node, void *env) +{ + opcode op = get_irn_opcode (node); + graph_info_t *graph_info = (graph_info_t*) env; + + if (iro_Call == op) { /* CALL */ + entity *ent = NULL; + ir_node *ptr = get_Call_ptr (node); + + /* CALL SEL */ + if (iro_Sel == get_irn_opcode (ptr)) { + ent = get_Sel_entity (ptr); + lset_t *graphs = get_implementing_graphs (ent, ptr); + + append_calls (graph_info, node, graphs); + } else if (iro_SymConst == get_irn_opcode (ptr)) { + if (get_SymConst_kind (ptr) == symconst_addr_ent) { + ent = get_SymConst_entity (ptr); + ir_graph *graph = get_entity_irg (ent); + + if (graph) { + append_call (graph_info, node, graph); + } else { + /* it's an externally allocated thingy */ + } + } 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. */ + if (get_SymConst_name (ptr) != new_id_from_str ("iro_Catch")) { + assert (ent && "couldn't determine entity of call to symConst"); + } + } else { + /* other symconst. */ + assert (0 && "This SymConst can not be an address for a method call."); + } + + /* STRANGE, no less ... */ + } else { + DDMN (ptr); + assert (0 && "Unexpected address expression"); + } + } else if (iro_Alloc == op) { + type *tp = get_Alloc_type (node); + const char *name = get_type_name (tp); + + append_alloc (graph_info, node, tp); + + fprintf (stdout, "NEW \"%s\"\n", name); + } +} + +/** + Collect called graphs for the given graph. +*/ +static void ecg_fill_graph_calls (ir_graph *graph) +{ + graph_info_t *graph_info = (graph_info_t*) xmalloc (sizeof (graph_info_t)); + + graph_info->graph = graph; + graph_info->calls = NULL; + graph_info->ecg_seen = 0; + + /* entity *method = get_irg_entity (graph); */ + /* type *clazz = get_entity_owner (method); */ + + irg_walk_graph (graph, ecg_calls_act, NULL, graph_info); + + pmap_insert (graph_infos, graph, graph_info); +} + +/** + For each graph, collect called graphs, and enter them into calls. +*/ +static void ecg_fill_calls (void) +{ + int i; + + for (i = 0; i < get_irp_n_irgs (); i++) { + ir_graph *graph = get_irp_irg (i); + + ecg_fill_graph_calls (graph); + } +} + +/* ==================== + ECG stuff + ==================== */ + +/* + get the call infos for the given graph +*/ +graph_info_t *ecg_get_info (ir_graph *graph) +{ + graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph); + + assert (ginfo && "no info for graph"); + + return (ginfo); +} + + + +/** + Dump the given graph and it's calls and it's calls callEds to the given file. +*/ +static int ecg_ecg_graph (FILE *dot, ir_graph *graph) +{ + const char *name = get_irg_entity (graph) ? + get_entity_name (get_irg_entity (graph)) : "noEntity"; + const char *color = + (get_entity_stickyness + (get_irg_entity (graph)) == stickyness_sticky) ? + "red" : "lightyellow"; + + graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph); + + if (0 != ginfo->ecg_seen) { + fprintf (dot, "\t/* recursive call to \"%s\" (%d) */\n", + name, (int) ginfo->ecg_seen); +# if 0 + fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n", + name, (int) graph); +# endif /* 0 */ + return (ginfo->ecg_seen); + } + + assert (0L <= _graphs); + + const int graph_no = _graphs ++; + ginfo->ecg_seen = graph_no; + + fprintf (dot, "\t/* Graph of \"%s.%s\" */\n", + get_type_name (get_entity_owner (get_irg_entity (graph))), + name); + fprintf (dot, "\tgraph_%i [label=\"%s\\l%s\", color=\"%s\"];\n", + graph_no, + get_type_name (get_entity_owner (get_irg_entity (graph))), + name, + color); + fprintf (dot, "\n"); + + if (visibility_external_allocated == + get_entity_visibility (get_irg_entity (graph))) { + fprintf (dot, "\t/* graph \"%s\" is external */\n", name); + + return (graph_no); + } + + call_info_t *cinfo = ginfo->calls; + while (NULL != cinfo) { + ir_node *call = cinfo->call; + callEd_info_t *ced = cinfo->callEds; + const int call_no = _calls ++; + + fprintf (dot, "\t/* Call 0x%08x */\n", (int) call); + fprintf (dot, "\tcall_%i [label=\"call\\l0x%08x\"];\n", + call_no, (int) call); + fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no); + + while (NULL != ced) { + ir_graph *callEd_graph = ced->callEd; + const int callEd_no = ecg_ecg_graph (dot, callEd_graph); + const char *callEd_name = get_irg_entity (callEd_graph) ? + get_entity_name (get_irg_entity (callEd_graph)) : "noEntity"; + const char *direction = (callEd_no <= graph_no) ? "forward" : "forward"; + const char *callEd_color = (callEd_no <= graph_no) ? "red" : "black"; + + fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n", + name, + callEd_name); + /* Check for recursive calls */ + /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */ + fprintf (dot, "\tcall_%i -> graph_%i [color=\"%s\", dir=\"%s\"];\n", + call_no, callEd_no, callEd_color, direction); + } + + ced = ced->prev; + /* ced = NULL; */ + } /* done all calEds (call) */ + + cinfo = cinfo->prev; + } /* done all calls (graph) */ + + /* now the allocs */ + alloc_info_t *ainfo = ginfo->allocs; + if (ainfo) { + fprintf (dot, "\t/* now the allocs */\n"); + } else { + fprintf (dot, "\t/* no allocs */\n"); + } + + while (NULL != ainfo) { + ir_node *alloc = ainfo->alloc; + const char *name = get_type_name (ainfo->tp); + const char *color = "red1"; + + /* if (0 == ginfo->allocs_seen) { */ + _allocs ++; + fprintf (dot, "\talloc_0x%08x_%i [label=\"%s\", color=\"%s\"]\n", + (int) alloc, graph_no, name, color); + /* } */ + + fprintf (dot, "\tgraph_%i -> alloc_0x%08x_%i\n", graph_no, (int) alloc, graph_no); + + ainfo = ainfo->prev; + } + + if (0 == ginfo->allocs_seen) { + ginfo->allocs_seen = 1; + } + + fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name); + + fflush (dot); + ginfo->ecg_seen = 0; + + return (graph_no); +} + +/** + Count how many nodes the ECG will have +*/ +static char spaces [BUF_SIZE]; + +static void ecg_ecg_count (ir_graph *graph) +{ + graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph); + + if (0 != ginfo->ecg_seen) { + return; + } + + _depth ++; + if (_depth > _max_depth) { + _max_depth = _depth; + + /* + fprintf (stdout, "_max_depth = %i\n", _max_depth); + fprintf (stdout, "\tn_graphs: %i\n", _graphs); + */ + } + + assert (0L <= _graphs); + + /* + if (0 == (_graphs % 1000000)) { + fprintf (stdout, "\tn_graphs: %i\n", _graphs); + fprintf (stdout, "_depth = %i\n", _depth); + } + */ + + const int graph_no = _graphs ++; + ginfo->ecg_seen = graph_no; + + fprintf (stdout, "%sMethod \"%s.%s\"\n", + spaces + BUF_SIZE - _depth, + get_type_name (get_entity_owner (get_irg_entity (graph))), + get_entity_name (get_irg_entity (graph))); + + call_info_t *cinfo = ginfo->calls; + while (NULL != cinfo) { + + callEd_info_t *ced = cinfo->callEds; + + fprintf (stdout, "%sCall \"0x%08x\"\n", + spaces + BUF_SIZE - _depth, + (int) cinfo->call); + + while (NULL != ced) { + ir_graph *callEd_graph = ced->callEd; + + fprintf (stdout, "%sCall Target \"%s.%s\"\n", + spaces + BUF_SIZE - _depth, + get_type_name (get_entity_owner (get_irg_entity (callEd_graph))), + get_entity_name (get_irg_entity (callEd_graph))); + + ecg_ecg_count (callEd_graph); + + ced = ced->prev; + } /* done all calEds (call) */ + cinfo = cinfo->prev; + } /* done all calls (graph) */ + + ginfo->ecg_seen = 0; + _depth --; +} + +/* ==================== + Public Interface + ==================== */ + +/** + Initialise our data structures. +*/ +void ecg_init (int typalise) +{ + do_typalise = typalise; + + graph_infos = pmap_create (); + + ecg_fill_calls (); +} + +/** + Clean up our mess. +*/ +void ecg_cleanup () +{ + int i; + + for (i = 0; i < get_irp_n_irgs (); i++) { + ir_graph *graph = get_irp_irg (i); + + graph_info_t *info = pmap_get (graph_infos, graph); + call_info_t *cinfo = info->calls; + + while (NULL != cinfo) { + free (cinfo->callEds); + cinfo->call = NULL; + + callEd_info_t *ced = cinfo->callEds; + + while (NULL != ced) { + callEd_info_t *nced = ced->prev; + free (ced); + ced->prev = NULL; + ced->callEd = NULL; + ced = nced; + } + + /* Todo: delete callEds */ + cinfo->callEds = NULL; + + free (cinfo); + cinfo = cinfo->prev; + } + + free (info); + pmap_insert (graph_infos, graph, NULL); + } + + + pmap_destroy (graph_infos); + + /* BEGIN mild paranoia mode */ + graph_infos = NULL; + /* END mild paranoia mode */ +} + +/** + Show what we have found. +*/ +void ecg_report () +{ + int i; + + FILE *dot = fopen ("calls.dot", "w"); + + fprintf (dot, "digraph \"calls\" {\n"); + fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n"); + fprintf (dot, "\tedge [color = \"black\"];\n"); + fprintf (dot, "\n"); + fprintf (dot, "\tsize = \"11, 7\";\n"); + fprintf (dot, "\trotate = \"90\";\n"); + fprintf (dot, "\tratio = \"fill\";\n"); + fprintf (dot, "\trankdir = \"LR\";\n"); + fprintf (dot, "\n"); + + for (i = 0; i < get_irp_n_irgs (); i++) { + ir_graph *graph = get_irp_irg (i); + graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph); + + const char *name = get_irg_entity (graph) ? + get_entity_name (get_irg_entity (graph)) : "noEntity"; + + const char *oname = get_type_name + (get_entity_owner (get_irg_entity (graph))); + + const char *color = + (get_entity_stickyness + (get_irg_entity (graph)) == stickyness_sticky) ? + "red3" : "lightyellow"; + + fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", (int) graph, name); + fprintf (dot, + "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n", + (int) graph, oname, name, color); + fprintf (dot, "\n"); + + call_info_t *cinfo = info->calls; + if (cinfo) { + fprintf (dot, "\t/* now the calls */\n"); + } else { + fprintf (dot, "\t/* no calls, nothing to see, move along! */\n"); + } + + while (NULL != cinfo) { + ir_node *call = cinfo->call; + + fprintf (dot, "\t/* call_0x%08x */\n", (int) call); + fprintf (dot, "\tcall_0x%08x [label=\"call\\l0x%08x\"];\n", + (int) call, (int) call); + fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n", + (int) graph, (int) call); + + callEd_info_t *ced = cinfo->callEds; + while (NULL != ced) { + fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n", + (int) call, (int) ced->callEd); + ced = ced->prev; + } + fprintf (dot, "\n"); + + cinfo = cinfo->prev; + } + fprintf (dot, "\n"); + + alloc_info_t *ainfo = info->allocs; + if (ainfo) { + fprintf (dot, "\t/* now the allocs */\n"); + } else { + fprintf (dot, "\t/* no allocs */\n"); + } + + + while (NULL != ainfo) { + ir_node *alloc = ainfo->alloc; + const char *name = get_type_name (ainfo->tp); + const char *color = "red1"; + + fprintf (dot, "\talloc_0x%08x [label=\"%s\", color=\"%s\"]\n", + (int) alloc, name, color); + fprintf (dot, "\tgraph_0x%08x -> alloc_0x%08x\n", + (int) graph, (int) alloc); + + ainfo = ainfo->prev; + } + } + fprintf (dot, "}\n"); + + /* + fprintf (stdout, " max_callEds: %i\n", _max_callEds); + fprintf (stdout, " max_callEds_callR: \"%s\"\n", + get_entity_name (_max_callEds_callR)); + */ + fclose (dot); + + ecg_ecg (); +} + +/** + Experimental: Print the ecg +*/ +void ecg_ecg () +{ + _graphs = 0; + _calls = 0; + + ir_graph *main_graph = get_irp_main_irg (); + + /* + memset (spaces, '.', BUF_SIZE); + spaces [BUF_SIZE-1] = '\0'; + + ecg_ecg_count (main_graph); + fprintf (stdout, "n_graphs: %i\n", _graphs); + fprintf (stdout, "max_depth = %i\n", _max_depth); + */ + + /* return; */ + + _graphs = 0; + _calls = 0; + + FILE *dot = fopen ("ecg.dot", "w"); + + fprintf (dot, "digraph \"ecg\" {\n"); + fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n"); + fprintf (dot, "\tedge [color = \"black\"];\n"); + fprintf (dot, "\n"); + fprintf (dot, "\tsize = \"11, 7\";\n"); + fprintf (dot, "\trotate = \"90\";\n"); + fprintf (dot, "\tratio = \"fill\";\n"); + fprintf (dot, "\trankdir = \"LR\";\n"); + fprintf (dot, "\n"); + + /* ir_graph *main_graph = get_irp_main_irg (); */ + ecg_ecg_graph (dot, main_graph); + + fprintf (dot, "\t/* Grand Total: */\n"); + fprintf (dot, "\t/* calls: %i */\n", (int) _calls); + fprintf (dot, "\t/* graphs: %i */\n", (int) _graphs); + fprintf (dot, "\t/* allocs: %i */\n", (int) _allocs); + fprintf (dot, "\t/* (sales tax not included) */\n"); + + fprintf (dot, "}\n"); + + fclose (dot); +} + + + +/* + $Log$ + Revision 1.1 2004/10/20 14:59:41 liekweg + Added ana2, added ecg and pto + + Revision 1.6 2004/10/18 12:47:19 liekweg + minor fix + + Revision 1.5 2004/10/14 11:31:28 liekweg + SHUTUP_GCC + + Revision 1.4 2004/10/12 11:02:01 liekweg + wtf? + +*/ diff --git a/ir/ana2/ecg.h b/ir/ana2/ecg.h new file mode 100644 index 000000000..15c9e0ff8 --- /dev/null +++ b/ir/ana2/ecg.h @@ -0,0 +1,65 @@ +/* -*- c -*- */ + +#ifndef _EGC_H_ +#define _EGC_H_ + +/* + data +*/ + +typedef struct alloc_info +{ + ir_graph *graph; + ir_node *alloc; + type *tp; + struct alloc_info *prev; +} alloc_info_t; + + +typedef struct callEd_info +{ + ir_graph *callEd; + struct callEd_info *prev; +} callEd_info_t; + +typedef struct call_info +{ + ir_node *call; + callEd_info_t *callEds; + struct call_info *prev; +} call_info_t; + +typedef struct graph_info +{ + ir_graph *graph; + call_info_t *calls; + alloc_info_t *allocs; + int ecg_seen; + int allocs_seen; +} graph_info_t; + +/* protos */ +void ecg_init (int); +graph_info_t *ecg_get_info (ir_graph*); +alloc_info_t *ecg_get_alloc_info (ir_graph*); +void ecg_cleanup (void); +void ecg_report (void); +void ecg_ecg (void); + +#endif /* defined _EGC_H_ */ + + +/* +$Log$ +Revision 1.1 2004/10/20 14:59:42 liekweg +Added ana2, added ecg and pto + +Revision 1.3 2004/10/14 11:31:29 liekweg +SHUTUP_GCC + +Revision 1.2 2004/10/12 11:02:03 liekweg +wtf? + +Revision 1.1 2004/09/29 12:03:39 liekweg +Added ecg mod + */ diff --git a/ir/ana2/pto.c b/ir/ana2/pto.c new file mode 100644 index 000000000..27769fd75 --- /dev/null +++ b/ir/ana2/pto.c @@ -0,0 +1,319 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana/pto.c + * Purpose: Pto + * Author: Florian + * Modified by: + * Created: Mon 18 Oct 2004 + * CVS-ID: $Id$ + * Copyright: (c) 1999-2004 Universität Karlsruhe + * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + + +# ifdef HAVE_CONFIG_H +# include +# endif + +# include "pto.h" + +# include "irnode_t.h" +# include "irprog_t.h" + +# include "eset.h" +# include "irgwalk.h" +# include "irgmod.h" +# include "irvrfy.h" +# include "trvrfy.h" +# include "xmalloc.h" + +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* not defined TRUE */ + +typedef struct walk_mem_env_str { + ir_graph *graph; /* the graph we're visiting */ + int visited; /* 'visited' marker */ + irg_walk_func *pre; /* pre action */ + irg_walk_func *post; /* post action */ + void *env; /* user-defined environment */ + + struct walk_mem_env_str *prev; /* link up walking instances */ + /* what else? */ +} walk_mem_env_t; + +/* Link up walking instances */ +static walk_mem_env_t *walk_envs = NULL; + +/* MEMORY WALK */ + +/* BEGIN TEST */ +static void print_node_pre (ir_node *node, void *__unused) +{ + fprintf (stdout, "PRE MEM Node (0x%08x) (%s)\n", + (int) node, + get_op_name (get_irn_op (node))); +} + +static void print_node_post (ir_node *node, void *__unused) +{ + const opcode op = get_irn_opcode (node); + + + if (iro_Call == op) { + entity *ent = NULL; + ir_graph *graph = NULL; + fprintf (stdout, "POST MEM Call Node (0x%08x)\n", + (int) node); + + ir_node *ptr = get_Call_ptr (node); + + if (iro_Sel == get_irn_opcode (ptr)) { + ent = get_Sel_entity (ptr); + } else if (iro_SymConst == get_irn_opcode (ptr)) { + if (get_SymConst_kind(ptr) == symconst_addr_ent) { + ent = get_SymConst_entity (ptr); + } + } + + if (NULL != ent) { + graph = get_entity_irg (ent); + if (NULL != graph) { + if (! get_irg_is_mem_visited (graph)) { + + fprintf (stdout, " -> visit graph (0x%08x) of \"%s.%s\"\n", + (int) graph, + get_type_name (get_entity_owner (get_irg_entity (graph))), + get_entity_name (get_irg_entity (graph))); + + irg_walk_mem (graph, print_node_pre, print_node_post, NULL); + } + } + } + + } else { + fprintf (stdout, "POST MEM Node (0x%08x) (%s)\n", + (int) node, + get_op_name (get_irn_op (node))); + } + +} + + +/* END TEST */ + +/* + See whether the given graph is being visited right now. +*/ +int get_irg_is_mem_visited (ir_graph *graph) +{ + walk_mem_env_t *walk_env = walk_envs; + + while (NULL != walk_env) { + if (graph == walk_env->graph) { + return (TRUE); + } + + walk_env = walk_env->prev; + } + + return (FALSE); +} + +/* + Walk over the firm nodes of a graph via the memory edges (only) + starting from a node that has a memory input. +*/ +void irg_walk_mem_node (ir_node *node, + walk_mem_env_t *walk_env) +{ + const opcode op = get_irn_opcode (node); + ir_node *in = NULL; + + if (get_irn_visited (node) >= walk_env->visited) { + return; + } else { + set_irn_visited (node, walk_env->visited + 1); + } + + fprintf (stdout, "Node (0x%08x).op = %s\n", (int) + node, + get_op_name (get_irn_op (node))); + + if (NULL != walk_env->pre) { + walk_env->pre (node, walk_env->env); + } + + switch (op) { + case (iro_Start): { + } break; + case (iro_Load): { + in = get_Load_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Store): { + in = get_Store_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Alloc): { + in = get_Alloc_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Free): { + in = get_Free_mem (node); + /* WTF? */ + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Raise): { + in = get_Raise_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Sel): { + in = get_Sel_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Call): { + in = get_Call_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Return): { + in = get_Return_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Proj): { + in = get_Proj_pred (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Phi): { + int i; + int n_ins = get_irn_arity (node); + + + for (i = 0; i < n_ins; i ++) { + in = get_irn_n (node, i); + + irg_walk_mem_node (in, walk_env); + } + } break; + case (iro_Div): { + in = get_Div_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Quot): { + in = get_Quot_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_Mod): { + in = get_Mod_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + case (iro_DivMod): { + in = get_DivMod_mem (node); + + irg_walk_mem_node (in, walk_env); + } break; + default: { + assert (0 && "something not handled"); + } + } + + if (NULL != walk_env->post) { + walk_env->post (node, walk_env->env); + } +} + +/* + Walk over the nodes of the given graph via the memory edges (only). + Each graph can only be subject to this walk once at any given time. +*/ +void irg_walk_mem (ir_graph *graph, + irg_walk_func *pre, irg_walk_func *post, + void *env) +{ + int i; + ir_node *ret = NULL; + ir_node *end = get_irg_end_block (graph); + int n_ins; + walk_mem_env_t *walk_env = (walk_mem_env_t*) xmalloc (sizeof (walk_mem_env_t)); + + assert (! get_irg_is_mem_visited (graph)); + + walk_env->graph = graph; + inc_irg_visited (walk_env->graph); + walk_env->visited = get_irg_visited (graph); + + walk_env->prev = walk_envs; + walk_envs = walk_env; + + walk_env->pre = pre; + walk_env->post = post; + walk_env->env = env; + + /* 'graph' is not actually being visited right now, but it should be reported that way */ + assert (get_irg_is_mem_visited (graph)); + + /* all return nodes */ + n_ins = get_irn_arity (end); + for (i = 0; i < n_ins; i ++) { + ret = get_irn_n (end, i); + + irg_walk_mem_node (ret, walk_env); + } + + /* + The end NODE sometimes has some more ins. not sure whether we need to walk them. + */ + + /* allow only properly nested calls right now */ + assert (walk_envs == walk_env); + walk_envs = walk_envs->prev; + + free (walk_env); + + assert (! get_irg_is_mem_visited (graph)); +} + +/* + Test irg_walk_mem +*/ +void pto_test_mem () +{ + int i; + + fprintf (stdout, "START PTO TEST\n"); + + for (i = 0; i < get_irp_n_irgs(); i++) { + ir_graph *graph = get_irp_irg (i); + + fprintf (stdout, "START GRAPH (0x%08x) of \"%s.%s\"\n", + (int) graph, + get_type_name (get_entity_owner (get_irg_entity (graph))), + get_entity_name (get_irg_entity (graph))); + irg_walk_mem (graph, print_node_pre, print_node_post, NULL); + fprintf (stdout, "END GRAPH (0x%08x)\n", (int) graph); + } + + fprintf (stdout, "END PTO TEST\n"); +} + + +/* + * $Log$ + * Revision 1.1 2004/10/20 14:59:42 liekweg + * Added ana2, added ecg and pto + * + */ diff --git a/ir/ana2/pto.h b/ir/ana2/pto.h new file mode 100644 index 000000000..321875c84 --- /dev/null +++ b/ir/ana2/pto.h @@ -0,0 +1,38 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana/pto.c + * Purpose: Pto + * Author: Florian + * Modified by: + * Created: Mon 18 Oct 2004 + * CVS-ID: $Id$ + * Copyright: (c) 1999-2004 Universität Karlsruhe + * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +# ifndef _PTO_H_ +# define _PTO_H_ + +# include "entity.h" + +# include "irgraph.h" +# include "irgwalk.h" + +void irg_walk_mem (ir_graph*, irg_walk_func*, irg_walk_func*, void*); + +int get_irg_is_mem_visited (ir_graph*); + +/* ...! */ +void pto_test_mem (void); + +# endif /* not defined _PTO_H_ */ + + +/* + * $Log$ + * Revision 1.1 2004/10/20 14:59:42 liekweg + * Added ana2, added ecg and pto + * + */ -- 2.20.1