X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fstat%2Fpattern.c;h=f1b712d5659f9991a85b11f0e6a20bcc2322a94c;hb=24a8ed9b437fa2ff3734c3dc8ea5c8fbe7fba45c;hp=f95b025bb5c12d9ea89d996f13fbfb4bd84c8b54;hpb=cc1eb7944af83960ce8ae56e85406a05640f443e;p=libfirm diff --git a/ir/stat/pattern.c b/ir/stat/pattern.c index f95b025bb..f1b712d56 100644 --- a/ir/stat/pattern.c +++ b/ir/stat/pattern.c @@ -3,13 +3,17 @@ */ #include #include +#include #include "ident.h" #include "irnode_t.h" #include "irgwalk.h" +#include "irprog.h" +#include "set.h" #include "pset.h" #include "counter.h" -#include "irprog.h" +#include "pattern_dmp.h" +#include "hashptr.h" /* * just be make some things clear :-), the @@ -43,6 +47,7 @@ enum vlc_code_t { VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */ VLC_TAG_FIRST = 0xF1, /**< first possible tag value */ + VLC_TAG_ICONST = 0xFB, /**< encodes an integer constant */ VLC_TAG_EMPTY = 0xFC, /**< encodes an empty entity */ VLC_TAG_OPTION = 0xFD, /**< options exists */ VLC_TAG_REF = 0xFE, /**< special tag, next code is an ID */ @@ -53,16 +58,18 @@ enum vlc_code_t { * An entry for patterns */ typedef struct _pattern_entry_t { - counter_t count; /**< amount of pattern occurance */ - unsigned len; /**< lenght of the VLC encoded buffer */ - BYTE buf[1]; /**< buffer contains the VLC encoded pattern */ + counter_t count; /**< amount of pattern occurance */ + unsigned len; /**< length of the VLC encoded buffer */ + BYTE buf[1]; /**< buffer contains the VLC encoded pattern */ } pattern_entry_t; /** * current options */ enum options_t { - OPT_WITH_MODE = 0x00000001, /**< use modes */ + OPT_WITH_MODE = 0x00000001, /**< use modes */ + OPT_ENC_GRAPH = 0x00000002, /**< encode graphs, not terms */ + OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */ }; @@ -70,11 +77,11 @@ enum options_t { * pattern info */ typedef struct _pattern_info_t { - int enable; /**< if non-zero, this module is enabled */ - struct obstack obst; /**< obstack containing the counters */ - HASH_MAP(pattern_entry_t) *pattern_hash; /**< hash map containing the counter for pattern */ - unsigned bound; /**< lowest value for output */ - unsigned options; /**< option mask */ + int enable; /**< if non-zero, this module is enabled */ + struct obstack obst; /**< obstack containing the counters */ + HASH_MAP(pattern_entry_t) *pattern_hash; /**< hash map containing the counter for pattern */ + unsigned bound; /**< lowest value for output */ + unsigned options; /**< option mask */ } pattern_info_t; /* @@ -83,7 +90,7 @@ typedef struct _pattern_info_t { static pattern_info_t _status, *status = &_status; /** - * compare two elemnts for counter + * compare two elements for counter */ static int pattern_count_cmp(const void *elt, const void *key) { @@ -114,7 +121,7 @@ static int pattern_cmp(const void *elt, const void *key) } /** - * initialise a code buffer + * initialize a code buffer */ static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len) { @@ -126,7 +133,7 @@ static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len) /** * put a byte into the buffer */ -static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte) +static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte) { if (buf->next < buf->end) { unsigned hash = buf->hash; @@ -138,7 +145,7 @@ static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte) } /** - * returns the current lenght of a buffer + * returns the current length of a buffer */ static unsigned buf_lenght(const CODE_BUFFER *buf) { @@ -146,7 +153,7 @@ static unsigned buf_lenght(const CODE_BUFFER *buf) } /** - * returns the current lenght of a buffer + * returns the current length of a buffer */ static const BYTE *buf_content(const CODE_BUFFER *buf) { @@ -274,93 +281,230 @@ static BYTE next_tag(CODE_BUFFER *buf) return 0; } -/* +/** + * environment for the pattern encoder + */ +typedef struct _codec_enc_t { + CODE_BUFFER *buf; /**< the code buffer */ + set *id_set; /**< the set containing all already seen nodes */ + unsigned curr_id; /**< current node id */ + unsigned options; /**< encoding options */ + pattern_dumper_t *dmp; /**< dumper for the decoder */ +} codec_env_t; + +typedef struct _addr_entry_t { + void *addr; /**< the address */ + unsigned id; /**< associated ID */ +} addr_entry_t; + +/** + * compare two addresses + */ +static int addr_cmp(const void *p1, const void *p2, size_t size) { + const addr_entry_t *e1 = p1; + const addr_entry_t *e2 = p2; + + return e1->addr != e2->addr; +} + +/** * encodes an IR-node, recursive worker + * + * @return reached depth */ -static void _encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) +static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) { + addr_entry_t entry, *r_entry; + set_entry *s_entry; int i, preds; + int res, depth; -#if 0 opcode code = get_irn_opcode(node); -#else - ir_op *code = get_irn_op(node); -#endif - put_code(buf, (unsigned)code); + /* insert the node into our ID map */ + entry.addr = node; + entry.id = env->curr_id; + + s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), HASH_PTR(node)); + r_entry = (addr_entry_t *)s_entry->dptr; + + if (r_entry->id != env->curr_id) { + /* already in the map, add an REF */ + put_tag(env->buf, VLC_TAG_REF); + put_code(env->buf, r_entry->id); - if (status->options & OPT_WITH_MODE) { + return max_depth; + } + else { + /* a new entry, proceed */ + ++env->curr_id; + } + + put_code(env->buf, (unsigned)code); + + /* do we need the mode ? */ + if (env->options & OPT_WITH_MODE) { ir_mode *mode = get_irn_mode(node); if (mode) - put_code(buf, (unsigned)mode); + /* FIXME: not 64bit save */ + put_code(env->buf, (unsigned)mode); else - put_tag(buf, VLC_TAG_EMPTY); + put_tag(env->buf, VLC_TAG_EMPTY); + } + + /* do we need integer constants */ + if (env->options & OPT_WITH_ICONST) { + if (code == iro_Const) { + tarval *tv = get_Const_tarval(node); + + if (tarval_is_long(tv)) { + long v = get_tarval_long(tv); + + put_tag(env->buf, VLC_TAG_ICONST); + put_code(env->buf, v); + } + } } --max_depth; if (max_depth <= 0) { - put_code(buf, 0); - return; + put_code(env->buf, 0); + return max_depth; } preds = get_irn_arity(node); - put_code(buf, preds); + put_code(env->buf, preds); + res = INT_MAX; for (i = 0; i < preds; ++i) { ir_node *n = get_irn_n(node, i); - _encode_node(n, buf, max_depth); + depth = _encode_node(n, max_depth, env); + if (depth < res) + res = depth; } + return res; } /** - * encode an IR-node - */ -static void encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) + * encode an IR-node (and its children) + * + * @param @node The root node of the graph + * @param buf The code buffer to store the bitstring in + * @param max_depth The maximum depth for descending + * + * @return The depth of the encoded graph (without cycles) + */ +static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) { - put_tag(buf, VLC_TAG_OPTION); - put_code(buf, status->options); - _encode_node(node, buf, max_depth); -} + codec_env_t env; + int res; + + env.buf = buf; + env.curr_id = 1; /* 0 is used for special purpose */ + env.options = status->options; + env.dmp = NULL; + + if (env.options & OPT_ENC_GRAPH) + env.id_set = new_set(addr_cmp, 32); + else + env.id_set = NULL; + + /* encode options if any */ + if (env.options) { + put_tag(buf, VLC_TAG_OPTION); + put_code(buf, env.options); + } + + res = _encode_node(node, max_depth, &env); + if (env.options & OPT_ENC_GRAPH) + del_set(env.id_set); + + return max_depth - res; +} /** * decode an IR-node, recursive walker */ -static void _decode_node(CODE_BUFFER *buf, unsigned options) +static void _decode_node(unsigned parent, int position, codec_env_t *env) { - unsigned op_code = get_code(buf); - unsigned code = next_tag(buf); - ir_op *op = (ir_op *)op_code; - - /* output the opcode-name */ - printf("%s", get_id_str(op->name)); - - if (options & OPT_WITH_MODE) { - if (next_tag(buf) != VLC_TAG_EMPTY) { - unsigned mode_code = get_code(buf); - ir_mode *mode = (ir_mode *)mode_code; - printf("%s", get_mode_name(mode)); + unsigned code; + unsigned op_code; + unsigned mode_code = 0; + long iconst; + void *attr = NULL; + + code = next_tag(env->buf); + if (code == VLC_TAG_REF) { /* it's a REF */ + code = get_code(env->buf); + + /* dump the edge */ + if (parent) { + int edge_mode = 0; + /* + * the mode of a Firm edge can be either computed from its target or + * from its source and position. We must take the second approach because + * we dont know the target here, it's a ref. + */ + pattern_dump_edge(env->dmp, code, parent, position, edge_mode); + } + + /* dump the node ref */ + pattern_dump_ref(env->dmp, code); + + return; + } + + /* get the opcode */ + op_code = get_code(env->buf); + + /* get the mode if encoded */ + if (env->options & OPT_WITH_MODE) { + if (next_tag(env->buf) != VLC_TAG_EMPTY) { + mode_code = get_code(env->buf); } } - /* enter it into the ID table */ + /* check, if a ICONST attribute is given */ + if (next_tag(env->buf) == VLC_TAG_ICONST) { + iconst = get_code(env->buf); + attr = &iconst; + } + + /* dump the edge */ + if (parent) { + int edge_mode = 0; + + /* + * the mode of a Firm edge can be either computed from its target or + * from its source and position. We take the second approach because + * we need it anyway for ref's. + */ + pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode); + } + + /* dump the node */ + parent = env->curr_id; + pattern_dump_node(env->dmp, parent, op_code, mode_code, attr); + /* ok, we have a new ID */ + ++env->curr_id; + + code = next_tag(env->buf); if (code != VLC_TAG_END) { /* more info, do recursion */ int i, preds; - preds = get_code(buf); + preds = get_code(env->buf); if (preds > 0) { - printf("("); + pattern_start_children(env->dmp, parent); for (i = 0; i < preds; ++i) { - if (i > 0) - printf(", "); - _decode_node(buf, options); + _decode_node(parent, i, env); } - printf(")"); + pattern_finish_children(env->dmp, parent); } } } @@ -368,18 +512,26 @@ static void _decode_node(CODE_BUFFER *buf, unsigned options) /** * decode an IR-node */ -static void decode_node(BYTE *b, unsigned len) +static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) { + codec_env_t env; CODE_BUFFER buf; unsigned code, options = 0; init_buf(&buf, b, len); + env.buf = &buf; + env.curr_id = 1; /* 0 is used for special purpose */ + env.dmp = dump; + + /* decode options */ code = next_tag(&buf); if (code == VLC_TAG_OPTION) { options = get_code(&buf); } - _decode_node(&buf, options); + env.options = options; + + _decode_node(0, 0, &env); } /** @@ -389,14 +541,6 @@ typedef struct _pattern_env { int max_depth; /**< maximum depth for pattern generation */ } pattern_env_t; -/** - * calculate a hash value for a pattern - */ -static unsigned pattern_hash(pattern_entry_t *key) -{ - return 9 * key->buf[0] + 31 * key->buf[key->len - 1] + 7 * key->buf[key->len >> 1]; -} - /** * Returns the associates pattern_entry_t for a CODE_BUF */ @@ -412,7 +556,7 @@ static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) key->len = len; memcpy(key->buf, buf_content(buf), len); - hash = buf_hash(buf); // pattern_hash(key); + hash = buf_hash(buf); elem = pset_find(set, key, hash); if (elem) { @@ -434,22 +578,28 @@ static void calc_nodes_pattern(ir_node *node, void *ctx) pattern_env_t *env = ctx; CODE_BUFFER buf; pattern_entry_t *entry; + int depth; init_buf(&buf, buffer, sizeof(buffer)); - encode_node(node, &buf, env->max_depth); + depth = encode_node(node, &buf, env->max_depth); - entry = pattern_get_entry(&buf, status->pattern_hash); + /* ignore single node pattern (i.e. constants) */ + if (depth > 1) { + entry = pattern_get_entry(&buf, status->pattern_hash); - /* increase count */ - cnt_inc(&entry->count); + /* increase count */ + cnt_inc(&entry->count); + } } /** + * output the collected pattern */ static void pattern_output(void) { - pattern_entry_t *entry; - pattern_entry_t **pattern_arr; + pattern_entry_t *entry; + pattern_entry_t **pattern_arr; + pattern_dumper_t *dump; int i, count = pset_count(status->pattern_hash); printf("\n%d pattern detected\n", count); @@ -457,6 +607,9 @@ static void pattern_output(void) if (count <= 0) return; + /* creates a dumper */ + dump = new_vcg_dumper("pattern.vcg", 100); + pattern_arr = xmalloc(sizeof(*pattern_arr) * count); for (i = 0, entry = pset_first(status->pattern_hash); entry && i < count; @@ -474,10 +627,14 @@ static void pattern_output(void) if (entry->count.cnt[0] < status->bound) continue; - printf("%8d\t", entry->count.cnt[0]); - decode_node(entry->buf, entry->len); - printf("\n"); + /* dump a pattern */ + pattern_dump_new_pattern(dump, &entry->count); + decode_node(entry->buf, entry->len, dump); + pattern_dump_finish_pattern(dump); } + + /* destroy it */ + pattern_end(dump); } /* @@ -494,12 +651,12 @@ void stat_calc_pattern_history(ir_graph *irg) if (irg == get_const_code_irg()) return; - env.max_depth = 4; + env.max_depth = 5; irg_walk_graph(irg, calc_nodes_pattern, NULL, &env); } /* - * initialises the pattern history + * initializes the pattern history */ void stat_init_pattern_history(int enable) { @@ -507,8 +664,8 @@ void stat_init_pattern_history(int enable) if (! enable) return; - status->bound = 3; - status->options = OPT_WITH_MODE; + status->bound = 10; + status->options = OPT_WITH_MODE | OPT_ENC_GRAPH | OPT_WITH_ICONST; obstack_init(&status->obst);