From 41b022e5d3a77bd3743f6a7b4444b13179dbd2e0 Mon Sep 17 00:00:00 2001 From: Florian Liekweg Date: Thu, 21 Oct 2004 11:09:37 +0000 Subject: [PATCH] Moved memwalk stuf into irmemwalk Moved lset stuff into lset Moved typalise stuff into typalise [r4175] --- ir/ana2/Makefile.in | 6 +- ir/ana2/ecg.c | 861 +------------------------------------------- ir/ana2/irmemwalk.c | 239 ++++++++++++ ir/ana2/irmemwalk.h | 35 ++ ir/ana2/lset.c | 200 ++++++++++ ir/ana2/lset.h | 76 ++++ ir/ana2/pto.c | 231 ++---------- ir/ana2/pto.h | 17 +- ir/ana2/typalise.c | 707 ++++++++++++++++++++++++++++++++++++ ir/ana2/typalise.h | 70 ++++ 10 files changed, 1370 insertions(+), 1072 deletions(-) create mode 100644 ir/ana2/irmemwalk.c create mode 100644 ir/ana2/irmemwalk.h create mode 100644 ir/ana2/lset.c create mode 100644 ir/ana2/lset.h create mode 100644 ir/ana2/typalise.c create mode 100644 ir/ana2/typalise.h diff --git a/ir/ana2/Makefile.in b/ir/ana2/Makefile.in index df51fe353..035524c69 100644 --- a/ir/ana2/Makefile.in +++ b/ir/ana2/Makefile.in @@ -13,14 +13,14 @@ top_srcdir := @top_srcdir@ srcdir = @srcdir@ topdir = ../.. -subdir := ir/ana +subdir := ir/ana2 -INSTALL_HEADERS = pto.h ecg.h \ +INSTALL_HEADERS = pto.h ecg.h irmemwalk.h lset.h typalise.h \ SOURCES = $(INSTALL_HEADERS) SOURCES += Makefile.in \ - pto.c ecg.c + pto.c ecg.c irmemwalk.c lset.c typalise.c include $(topdir)/MakeRules diff --git a/ir/ana2/ecg.c b/ir/ana2/ecg.c index 4d2d32eff..7774587ed 100644 --- a/ir/ana2/ecg.c +++ b/ir/ana2/ecg.c @@ -29,52 +29,16 @@ #include "trvrfy.h" #include "xmalloc.h" -# define TRUE 1 -# define FALSE 0 +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* not defined TRUE */ # 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; +# include "typalise.h" +# include "lset.h" /* le flag @@ -101,814 +65,6 @@ 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 ==================== */ @@ -1626,6 +782,11 @@ void ecg_ecg () /* $Log$ + Revision 1.2 2004/10/21 11:09:37 liekweg + Moved memwalk stuf into irmemwalk + Moved lset stuff into lset + Moved typalise stuff into typalise + Revision 1.1 2004/10/20 14:59:41 liekweg Added ana2, added ecg and pto diff --git a/ir/ana2/irmemwalk.c b/ir/ana2/irmemwalk.c new file mode 100644 index 000000000..b4768e93e --- /dev/null +++ b/ir/ana2/irmemwalk.c @@ -0,0 +1,239 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana2/irmemwalk.c + * Purpose: walk along memory edges + * 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. + */ + +/* + Walk over a firm graph along its memory edges. + + Any number of graphs can be visited at the same time, but no graph + can be traversed more than once at any time. +*/ + + +# ifdef HAVE_CONFIG_H +# include +# endif + +# include "irgwalk.h" /* for irg_walk_func */ +# include "xmalloc.h" + +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* not defined TRUE */ + +/* + Data +*/ + +/* environment for a single memory walker */ +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; + +/* + Globals +*/ + +/* Link up walking instances */ +static walk_mem_env_t *walk_envs = NULL; + +/* + Walk over the firm nodes of a graph via the memory edges (only) + starting from a node that has a memory input. +*/ +static 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); + } +} + +/* + See whether the given graph is being visited right now. + We can't be visiting a graph multiple times. +*/ +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 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)); +} diff --git a/ir/ana2/irmemwalk.h b/ir/ana2/irmemwalk.h new file mode 100644 index 000000000..9aa34cc1c --- /dev/null +++ b/ir/ana2/irmemwalk.h @@ -0,0 +1,35 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana2/irmemwalk.h + * Purpose: walk along memory edges + * 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 _IRMEMWALK_H_ +# define _IRMEMWALK_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*); + +# endif /* not defined _IRMEMWALK_H_ */ + + +/* + $Log$ + Revision 1.1 2004/10/21 11:09:37 liekweg + Moved memwalk stuf into irmemwalk + Moved lset stuff into lset + Moved typalise stuff into typalise + + + */ diff --git a/ir/ana2/lset.c b/ir/ana2/lset.c new file mode 100644 index 000000000..8ed89a268 --- /dev/null +++ b/ir/ana2/lset.c @@ -0,0 +1,200 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana2/lset.c + * Purpose: Lists, err, Sets + * 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 "lset.h" +# include "xmalloc.h" + +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* not defined TRUE */ + +# include +# include /* need memset */ + +/* + Lists, err, Sets + */ + +/* create a new lset */ +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 */ +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 */ +int lset_empty (lset_t *lset) +{ + return (NULL == lset->first); +} + + +/* insert the data into the lset (unless there's an entry for it + already) */ +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 */ +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. */ +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 */ +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); +} + +/* prepare the given lset for an iteration. return the first element. */ +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 */ +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 */ +int lset_n_entries (lset_t *lset) +{ + return (lset->n_entries); +} + +/* deallocate the lset and all of its entries */ +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); +} + + + +/* + $Log$ + Revision 1.1 2004/10/21 11:09:37 liekweg + Moved memwalk stuf into irmemwalk + Moved lset stuff into lset + Moved typalise stuff into typalise + + + */ diff --git a/ir/ana2/lset.h b/ir/ana2/lset.h new file mode 100644 index 000000000..2fa7c1d59 --- /dev/null +++ b/ir/ana2/lset.h @@ -0,0 +1,76 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana2/lset.h + * Purpose: Lists, err, Sets + * 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 _LSET_H_ +# define _LSET_H_ + +/* + Data Types and 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; + +/* create a new lset */ +lset_t *lset_create (void); +/* check whether the lset contains an entry for the given data */ +int lset_contains (lset_t*, void*); +/* check whether the given lset is empty */ +int lset_empty (lset_t*); +/* insert the data into the lset (unless there's an entry for it + already) */ +void lset_insert (lset_t*, void*); +/* insert all entries from src into tgt */ +void lset_insert_all (lset_t*, lset_t*); +/* append src to tgt. src is deallocated. */ +void lset_append (lset_t*, lset_t*); + +/* 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 */ +int lset_remove (lset_t*, void*); +/* prepare the given lset for an iteration. return the first element. */ +void *lset_first (lset_t*); +/* after calling lset_first, get the next element, if applicable, or + NULL */ +void *lset_next (lset_t*); +/* say how many entries there are in the given lset */ +int lset_n_entries (lset_t*); +/* deallocate the lset and all of its entries */ +void lset_destroy (lset_t*); + + + +# endif /* not defined _LSET_H_ */ + + +/* + $Log$ + Revision 1.1 2004/10/21 11:09:37 liekweg + Moved memwalk stuf into irmemwalk + Moved lset stuff into lset + Moved typalise stuff into typalise + + + */ diff --git a/ir/ana2/pto.c b/ir/ana2/pto.c index 27769fd75..a94b54eb4 100644 --- a/ir/ana2/pto.c +++ b/ir/ana2/pto.c @@ -2,7 +2,7 @@ /* * Project: libFIRM - * File name: ir/ana/pto.c + * File name: ir/ana2/pto.c * Purpose: Pto * Author: Florian * Modified by: @@ -19,46 +19,38 @@ # include "pto.h" +# include "entity.h" + + # include "irnode_t.h" # include "irprog_t.h" -# include "eset.h" +/* # include "eset.h" */ +# include "irgraph.h" # include "irgwalk.h" # include "irgmod.h" # include "irvrfy.h" # include "trvrfy.h" # include "xmalloc.h" +# include "irmemwalk.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) +/* +static void pto_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) +static void pto_node_post (ir_node *node, void *__unused) { const opcode op = get_irn_opcode (node); @@ -89,204 +81,21 @@ static void print_node_post (ir_node *node, void *__unused) 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); + /* irg_walk_mem (graph, pto_node_pre, pto_node_post, NULL); */ + irg_walk_mem (graph, NULL, pto_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 */ @@ -303,16 +112,22 @@ void pto_test_mem () (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); + /* irg_walk_mem (graph, pto_node_pre, pto_node_post, NULL); */ + irg_walk_mem (graph, NULL, pto_node_post, NULL); fprintf (stdout, "END GRAPH (0x%08x)\n", (int) graph); } fprintf (stdout, "END PTO TEST\n"); } - + /* * $Log$ + * Revision 1.2 2004/10/21 11:09:37 liekweg + * Moved memwalk stuf into irmemwalk + * Moved lset stuff into lset + * Moved typalise stuff into typalise + * * 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 index 321875c84..2ac601b3c 100644 --- a/ir/ana2/pto.h +++ b/ir/ana2/pto.h @@ -2,7 +2,7 @@ /* * Project: libFIRM - * File name: ir/ana/pto.c + * File name: ir/ana2/pto.c * Purpose: Pto * Author: Florian * Modified by: @@ -15,16 +15,6 @@ # 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_ */ @@ -32,6 +22,11 @@ void pto_test_mem (void); /* * $Log$ + * Revision 1.2 2004/10/21 11:09:37 liekweg + * Moved memwalk stuf into irmemwalk + * Moved lset stuff into lset + * Moved typalise stuff into typalise + * * Revision 1.1 2004/10/20 14:59:42 liekweg * Added ana2, added ecg and pto * diff --git a/ir/ana2/typalise.c b/ir/ana2/typalise.c new file mode 100644 index 000000000..30cc87368 --- /dev/null +++ b/ir/ana2/typalise.c @@ -0,0 +1,707 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana2/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 "typalise.h" + +# ifndef TRUE +# define TRUE 1 +# define FALSE 0 +# endif /* not defined TRUE */ + +# include + +# include "irnode.h" +# include "irgwalk.h" +# include "xmalloc.h" + + +/* + Local Globals +*/ + +static long ta_id = 0; + +/* + Local Protos +*/ +static typalise_t *typalise_proj (ir_node*); + + +/* + Ctors, Dtors for typalise_t-s +*/ +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); +} + +/* + Helpers for inheritance, overwriting and stuff +*/ +/** + 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); +} + +/** + 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); +} + +/* + Handle typalise_t-s +*/ +/** + 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 */ + +/** + 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); +} + +/** + 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"); +} + + +/* =========== WHAT ELSE ? =========== */ + +/* + Helper to 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); +} + + + +/* + Public Interface +*/ +/** + 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. +*/ +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); +} + +/** + For the given ptr, do a quick check about what (class) types may be + brought along on it. +*/ +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); +} + + + + + +/* + $Log$ + Revision 1.1 2004/10/21 11:09:37 liekweg + Moved memwalk stuf into irmemwalk + Moved lset stuff into lset + Moved typalise stuff into typalise + + + */ diff --git a/ir/ana2/typalise.h b/ir/ana2/typalise.h new file mode 100644 index 000000000..fd4922792 --- /dev/null +++ b/ir/ana2/typalise.h @@ -0,0 +1,70 @@ +/* -*- c -*- */ + +/* + * Project: libFIRM + * File name: ir/ana2/typalise.h + * Purpose: Compute rough approximations of pointer types + * 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 _TYPALISE_H_ +# define _TYPALISE_H_ + +# include "lset.h" + +# include "type.h" + +/* + Data Types and Structures +*/ +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; + +/* + Protos +*/ +/** + 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. +*/ +lset_t *filter_for_ta (lset_t*, typalise_t*); + +/** + For the given ptr, do a quick check about what (class) types may be + brought along on it. +*/ +typalise_t *typalise (ir_node*); + +# endif /* not defined _TYPALISE_H_ */ + + +/* + $Log$ + Revision 1.1 2004/10/21 11:09:37 liekweg + Moved memwalk stuf into irmemwalk + Moved lset stuff into lset + Moved typalise stuff into typalise + + + */ -- 2.20.1