X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fstat%2Fpattern.c;h=966217615e71428c1e731e7d3bbfefa412114e8a;hb=d49a8741d0780f324c8ee35176cb37b0188ec8f2;hp=9a27807f12cfa5223c6f461aaebb4fd49a3b7367;hpb=1580176436dd0df7f1a0b608aef904d5f6d24e5a;p=libfirm diff --git a/ir/stat/pattern.c b/ir/stat/pattern.c index 9a27807f1..966217615 100644 --- a/ir/stat/pattern.c +++ b/ir/stat/pattern.c @@ -3,6 +3,7 @@ */ #include #include +#include #include "ident.h" #include "irnode_t.h" @@ -12,6 +13,7 @@ #include "pset.h" #include "counter.h" #include "pattern_dmp.h" +#include "hashptr.h" /* * just be make some things clear :-), the @@ -28,44 +30,46 @@ typedef unsigned char BYTE; * The code buffer */ typedef struct _code_buf_t { - BYTE *next; /**< next byte to be written */ - BYTE *end; /**< end of the buffer */ - BYTE *start; /**< start of the buffer */ - unsigned hash; /**< calculates the hash value */ + BYTE *next; /**< next byte to be written */ + BYTE *end; /**< end of the buffer */ + BYTE *start; /**< start of the buffer */ + unsigned hash; /**< calculates the hash value */ } CODE_BUFFER; /** * VLC codes */ enum vlc_code_t { - VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */ - VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */ - VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */ - VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */ - VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */ - - VLC_TAG_FIRST = 0xF1, /**< first possible tag value */ - 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 */ - VLC_TAG_END = 0xFF, /**< end tag */ + VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */ + VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */ + VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */ + VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */ + 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 */ + VLC_TAG_END = 0xFF, /**< end tag */ }; /* - * An entry for patterns + * 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_ENC_GRAPH = 0x00000002, /**< encode graphs, not terms */ + OPT_WITH_MODE = 0x00000001, /**< use modes */ + OPT_ENC_DAG = 0x00000002, /**< encode DAGs, not terms */ + OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */ }; @@ -73,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; /* @@ -86,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) { @@ -95,10 +99,10 @@ static int pattern_count_cmp(const void *elt, const void *key) pattern_entry_t **e1 = (pattern_entry_t **)elt; pattern_entry_t **e2 = (pattern_entry_t **)key; - cmp = cnt_cmp(&(*e1)->count, &(*e2)->count); - /* we want it sorted in descending order */ - return cmp * - 1; + cmp = cnt_cmp(&(*e2)->count, &(*e1)->count); + + return cmp; } /** @@ -117,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) { @@ -129,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; @@ -141,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) { @@ -149,7 +153,7 @@ static unsigned buf_lenght(const CODE_BUFFER *buf) } /** - * returns the current lenght of a buffer + * returns the current content of a buffer */ static const BYTE *buf_content(const CODE_BUFFER *buf) { @@ -184,7 +188,7 @@ static INLINE BYTE get_byte(CODE_BUFFER *buf) return VLC_TAG_END; } -#define BITS(n) (1 << (n)) +#define BITS(n) (1 << (n)) /** * put a 32bit value into the buffer @@ -218,7 +222,7 @@ static void put_code(CODE_BUFFER *buf, unsigned code) } } -#define BIT_MASK(n) ((1 << (n)) - 1) +#define BIT_MASK(n) ((1 << (n)) - 1) /** * get 32 bit from the buffer @@ -281,26 +285,18 @@ static BYTE next_tag(CODE_BUFFER *buf) * 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 */ + 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 */ + void *addr; /**< the address */ + unsigned id; /**< associated ID */ } addr_entry_t; -/** - * hash value of an address - */ -static INLINE unsigned addr_hash(void *addr) -{ - return ((unsigned)addr) >> 3; -} - /** * compare two addresses */ @@ -311,26 +307,25 @@ static int addr_cmp(const void *p1, const void *p2, size_t size) { return e1->addr != e2->addr; } -/* +/** * encodes an IR-node, recursive worker + * + * @return reached depth */ -static void _encode_node(ir_node *node, int max_depth, codec_env_t *env) +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 /* 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), addr_hash(node)); + 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) { @@ -338,7 +333,7 @@ static void _encode_node(ir_node *node, int max_depth, codec_env_t *env) put_tag(env->buf, VLC_TAG_REF); put_code(env->buf, r_entry->id); - return; + return max_depth; } else { /* a new entry, proceed */ @@ -347,45 +342,72 @@ static void _encode_node(ir_node *node, int max_depth, codec_env_t *env) 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) + /* FIXME: not 64bit save */ put_code(env->buf, (unsigned)mode); else 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(env->buf, 0); - return; + return max_depth; } preds = get_irn_arity(node); 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, max_depth, env); + 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 a DAG staring by the IR-node node + * + * @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) { codec_env_t env; + int res; env.buf = buf; - env.curr_id = 1; /* 0 is used for special purpose */ + env.curr_id = 1; /* 0 is used for special purpose */ env.options = status->options; env.dmp = NULL; - if (env.options & OPT_ENC_GRAPH) + if (env.options & OPT_ENC_DAG) env.id_set = new_set(addr_cmp, 32); else env.id_set = NULL; @@ -396,10 +418,12 @@ static void encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) put_code(buf, env.options); } - _encode_node(node, max_depth, &env); + res = _encode_node(node, max_depth, &env); - if (env.options & OPT_ENC_GRAPH) + if (env.options & OPT_ENC_DAG) del_set(env.id_set); + + return max_depth - res; } /** @@ -410,14 +434,23 @@ static void _decode_node(unsigned parent, int position, codec_env_t *env) 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) - pattern_dump_edge(env->dmp, code, parent, position); + 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); @@ -435,13 +468,27 @@ static void _decode_node(unsigned parent, int position, codec_env_t *env) } } + /* 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) - pattern_dump_edge(env->dmp, env->curr_id, parent, position); + 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); + pattern_dump_node(env->dmp, parent, op_code, mode_code, attr); /* ok, we have a new ID */ ++env->curr_id; @@ -465,7 +512,7 @@ static void _decode_node(unsigned parent, int position, codec_env_t *env) /** * 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; @@ -474,8 +521,8 @@ static void decode_node(BYTE *b, unsigned len) init_buf(&buf, b, len); env.buf = &buf; - env.curr_id = 1; /* 0 is used for special purpose */ - env.dmp = &stdout_dump; + env.curr_id = 1; /* 0 is used for special purpose */ + env.dmp = dump; /* decode options */ code = next_tag(&buf); @@ -491,11 +538,14 @@ static void decode_node(BYTE *b, unsigned len) * the environment for the pattern calculation */ typedef struct _pattern_env { - int max_depth; /**< maximum depth for pattern generation */ + int max_depth; /**< maximum depth for pattern generation */ } pattern_env_t; /** * Returns the associates pattern_entry_t for a CODE_BUF + * + * @param buf the code buffer + * @param set the hash table containing all pattern entries */ static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) { @@ -518,35 +568,48 @@ static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) } cnt_clr(&key->count); - assert(key != (void *)4); return pset_insert(set, key, hash); } /** - * walker for nodes pattern calculation + * count a pattern + */ +static void count_pattern(CODE_BUFFER *buf, int depth) { + pattern_entry_t *entry; + + /* ignore single node pattern (i.e. constants) */ + if (depth > 1) { + entry = pattern_get_entry(buf, status->pattern_hash); + + /* increase count */ + cnt_inc(&entry->count); + } +} + +/** + * pre-walker for nodes pattern calculation */ static void calc_nodes_pattern(ir_node *node, void *ctx) { BYTE buffer[1024]; 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); - - /* increase count */ - cnt_inc(&entry->count); + count_pattern(&buf, depth); } /** + * 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); @@ -554,6 +617,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; @@ -568,13 +634,17 @@ static void pattern_output(void) for (i = 0; i < count; ++i) { entry = pattern_arr[i]; - if (entry->count.cnt[0] < status->bound) + if (cnt_to_uint(&entry->count) < 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); } /* @@ -591,12 +661,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) { @@ -604,8 +674,8 @@ void stat_init_pattern_history(int enable) if (! enable) return; - status->bound = 3; - status->options = OPT_WITH_MODE | OPT_ENC_GRAPH; + status->bound = 10; + status->options = OPT_WITH_MODE | OPT_ENC_DAG | OPT_WITH_ICONST; obstack_init(&status->obst);