X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fstat%2Fpattern.c;h=03593a14c7722a62d86e42ab5c6dbf9466828327;hb=0f6661f05f5ca3bb05e45a1f08d1c61ed8e4a45d;hp=683911f19e3a2db6657ec85a957ccb3cdb264d20;hpb=36536dc04864a20b95938e28a4ba1a5b77ba21d8;p=libfirm diff --git a/ir/stat/pattern.c b/ir/stat/pattern.c index 683911f19..03593a14c 100644 --- a/ir/stat/pattern.c +++ b/ir/stat/pattern.c @@ -13,6 +13,7 @@ #include "pset.h" #include "counter.h" #include "pattern_dmp.h" +#include "hashptr.h" /* * just be make some things clear :-), the @@ -29,45 +30,45 @@ 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_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 */ + 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 */ }; @@ -76,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; /* @@ -89,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) { @@ -98,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; } /** @@ -120,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) { @@ -132,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; @@ -144,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) { @@ -152,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) { @@ -187,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 @@ -221,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 @@ -284,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 */ @@ -332,7 +325,7 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) 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) { @@ -354,6 +347,7 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) 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); @@ -365,10 +359,10 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) tarval *tv = get_Const_tarval(node); if (tarval_is_long(tv)) { - long v = get_tarval_long(tv); + long v = get_tarval_long(tv); - put_tag(env->buf, VLC_TAG_ICONST); - put_code(env->buf, v); + put_tag(env->buf, VLC_TAG_ICONST); + put_code(env->buf, v); } } } @@ -395,9 +389,9 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) } /** - * encode an IR-node (and its children) + * encode a DAG staring by the IR-node node * - * @param @node The root node of the graph + * @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 * @@ -409,11 +403,11 @@ static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) 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; @@ -426,7 +420,7 @@ static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) 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; @@ -527,7 +521,7 @@ static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) init_buf(&buf, b, len); env.buf = &buf; - env.curr_id = 1; /* 0 is used for special purpose */ + env.curr_id = 1; /* 0 is used for special purpose */ env.dmp = dump; /* decode options */ @@ -544,11 +538,14 @@ static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) * 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) { @@ -571,31 +568,38 @@ 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)); depth = encode_node(node, &buf, env->max_depth); - /* ignore single node pattern (i.e. constants) */ - if (depth > 1) { - entry = pattern_get_entry(&buf, status->pattern_hash); - - /* increase count */ - cnt_inc(&entry->count); - } + count_pattern(&buf, depth); } /** @@ -662,7 +666,7 @@ void stat_calc_pattern_history(ir_graph *irg) } /* - * initialises the pattern history + * initializes the pattern history */ void stat_init_pattern_history(int enable) { @@ -671,7 +675,7 @@ void stat_init_pattern_history(int enable) return; status->bound = 10; - status->options = OPT_WITH_MODE | OPT_ENC_GRAPH | OPT_WITH_ICONST; + status->options = OPT_WITH_MODE | OPT_ENC_DAG | OPT_WITH_ICONST; obstack_init(&status->obst);