14 #include "pattern_dmp.h"
17 * just be make some things clear :-), the
20 #define HASH_MAP(type) pset_##type
22 typedef pset pset_pattern_entry_t;
24 typedef unsigned char BYTE;
30 typedef struct _code_buf_t {
31 BYTE *next; /**< next byte to be written */
32 BYTE *end; /**< end of the buffer */
33 BYTE *start; /**< start of the buffer */
34 unsigned hash; /**< calculates the hash value */
41 VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */
42 VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */
43 VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */
44 VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */
45 VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */
47 VLC_TAG_FIRST = 0xF1, /**< first possible tag value */
48 VLC_TAG_EMPTY = 0xFC, /**< encodes an empty entity */
49 VLC_TAG_OPTION = 0xFD, /**< options exists */
50 VLC_TAG_REF = 0xFE, /**< special tag, next code is an ID */
51 VLC_TAG_END = 0xFF, /**< end tag */
55 * An entry for patterns
57 typedef struct _pattern_entry_t {
58 counter_t count; /**< amount of pattern occurance */
59 unsigned len; /**< lenght of the VLC encoded buffer */
60 BYTE buf[1]; /**< buffer contains the VLC encoded pattern */
67 OPT_WITH_MODE = 0x00000001, /**< use modes */
68 OPT_ENC_GRAPH = 0x00000002, /**< encode graphs, not terms */
75 typedef struct _pattern_info_t {
76 int enable; /**< if non-zero, this module is enabled */
77 struct obstack obst; /**< obstack containing the counters */
78 HASH_MAP(pattern_entry_t) *pattern_hash; /**< hash map containing the counter for pattern */
79 unsigned bound; /**< lowest value for output */
80 unsigned options; /**< option mask */
86 static pattern_info_t _status, *status = &_status;
89 * compare two elemnts for counter
91 static int pattern_count_cmp(const void *elt, const void *key)
95 pattern_entry_t **e1 = (pattern_entry_t **)elt;
96 pattern_entry_t **e2 = (pattern_entry_t **)key;
98 cmp = cnt_cmp(&(*e1)->count, &(*e2)->count);
100 /* we want it sorted in descending order */
105 * compare two elements of the pattern hash
107 static int pattern_cmp(const void *elt, const void *key)
109 const pattern_entry_t *e1 = elt;
110 const pattern_entry_t *e2 = key;
111 int diff = e1->len - e2->len;
116 return memcmp(e1->buf, e2->buf, e1->len);
120 * initialise a code buffer
122 static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
124 buf->start = buf->next = data;
125 buf->end = data + len;
130 * put a byte into the buffer
132 static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte)
134 if (buf->next < buf->end) {
135 unsigned hash = buf->hash;
137 hash = (hash * 9) ^ byte;
144 * returns the current lenght of a buffer
146 static unsigned buf_lenght(const CODE_BUFFER *buf)
148 return buf->next - buf->start;
152 * returns the current lenght of a buffer
154 static const BYTE *buf_content(const CODE_BUFFER *buf)
160 * returns the hash value of a buffer
162 static unsigned buf_hash(const CODE_BUFFER *buf)
168 * returns the next byte from the buffer WITHOUT dropping
170 static INLINE BYTE look_byte(CODE_BUFFER *buf)
172 if (buf->next < buf->end)
178 * returns the next byte from the buffer WITH dropping
180 static INLINE BYTE get_byte(CODE_BUFFER *buf)
182 if (buf->next < buf->end)
187 #define BITS(n) (1 << (n))
190 * put a 32bit value into the buffer
192 static void put_code(CODE_BUFFER *buf, unsigned code)
194 if (code < BITS(7)) {
195 put_byte(buf, VLC_7BIT | code);
197 else if (code < BITS(6 + 8)) {
198 put_byte(buf, VLC_14BIT | (code >> 8));
201 else if (code < BITS(5 + 8 + 8)) {
202 put_byte(buf, VLC_21BIT | (code >> 16));
203 put_byte(buf, code >> 8);
206 else if (code < BITS(4 + 8 + 8 + 8)) {
207 put_byte(buf, VLC_28BIT | (code >> 24));
208 put_byte(buf, code >> 16);
209 put_byte(buf, code >> 8);
213 put_byte(buf, VLC_32BIT);
214 put_byte(buf, code >> 24);
215 put_byte(buf, code >> 16);
216 put_byte(buf, code >> 8);
221 #define BIT_MASK(n) ((1 << (n)) - 1)
224 * get 32 bit from the buffer
226 static unsigned get_code(CODE_BUFFER *buf)
228 unsigned code = get_byte(buf);
230 if (code < VLC_14BIT)
232 if (code < VLC_21BIT)
233 return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
234 if (code < VLC_28BIT) {
235 code = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
236 code |= get_byte(buf);
239 if (code < VLC_32BIT) {
240 code = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
241 code |= get_byte(buf) << 8;
242 code |= get_byte(buf);
245 if (code == VLC_32BIT) {
246 code = get_byte(buf) << 24;
247 code |= get_byte(buf) << 16;
248 code |= get_byte(buf) << 8;
249 code |= get_byte(buf);
252 /* should not happen */
253 assert(0 && "Wrong code in buffer");
259 * put a tag into the buffer
261 static void put_tag(CODE_BUFFER *buf, BYTE tag)
263 assert(tag >= VLC_TAG_FIRST && "invalid tag");
269 * returns the next tag or zero if the next code isn't a tag
271 static BYTE next_tag(CODE_BUFFER *buf)
273 BYTE b = look_byte(buf);
275 if (b >= VLC_TAG_FIRST)
276 return get_byte(buf);
281 * environment for the pattern encoder
283 typedef struct _codec_enc_t {
284 CODE_BUFFER *buf; /**< the code buffer */
285 set *id_set; /**< the set containing all already seen nodes */
286 unsigned curr_id; /**< current node id */
287 unsigned options; /**< encoding options */
288 pattern_dumper_t *dmp; /**< dumper for the decoder */
291 typedef struct _addr_entry_t {
292 void *addr; /**< the address */
293 unsigned id; /**< associated ID */
297 * hash value of an address
299 static INLINE unsigned addr_hash(void *addr)
301 return ((unsigned)addr) >> 3;
305 * compare two addresses
307 static int addr_cmp(const void *p1, const void *p2, size_t size) {
308 const addr_entry_t *e1 = p1;
309 const addr_entry_t *e2 = p2;
311 return e1->addr != e2->addr;
315 * encodes an IR-node, recursive worker
317 static void _encode_node(ir_node *node, int max_depth, codec_env_t *env)
319 addr_entry_t entry, *r_entry;
324 opcode code = get_irn_opcode(node);
326 ir_op *code = get_irn_op(node);
329 /* insert the node into our ID map */
331 entry.id = env->curr_id;
333 s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), addr_hash(node));
334 r_entry = (addr_entry_t *)s_entry->dptr;
336 if (r_entry->id != env->curr_id) {
337 /* already in the map, add an REF */
338 put_tag(env->buf, VLC_TAG_REF);
339 put_code(env->buf, r_entry->id);
344 /* a new entry, proceed */
348 put_code(env->buf, (unsigned)code);
350 if (env->options & OPT_WITH_MODE) {
351 ir_mode *mode = get_irn_mode(node);
354 put_code(env->buf, (unsigned)mode);
356 put_tag(env->buf, VLC_TAG_EMPTY);
361 if (max_depth <= 0) {
362 put_code(env->buf, 0);
366 preds = get_irn_arity(node);
367 put_code(env->buf, preds);
369 for (i = 0; i < preds; ++i) {
370 ir_node *n = get_irn_n(node, i);
372 _encode_node(n, max_depth, env);
379 static void encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
384 env.curr_id = 1; /* 0 is used for special purpose */
385 env.options = status->options;
388 if (env.options & OPT_ENC_GRAPH)
389 env.id_set = new_set(addr_cmp, 32);
393 /* encode options if any */
395 put_tag(buf, VLC_TAG_OPTION);
396 put_code(buf, env.options);
399 _encode_node(node, max_depth, &env);
401 if (env.options & OPT_ENC_GRAPH)
406 * decode an IR-node, recursive walker
408 static void _decode_node(unsigned parent, int position, codec_env_t *env)
412 unsigned mode_code = 0;
414 code = next_tag(env->buf);
415 if (code == VLC_TAG_REF) { /* it's a REF */
416 code = get_code(env->buf);
420 pattern_dump_edge(env->dmp, code, parent, position);
422 /* dump the node ref */
423 pattern_dump_ref(env->dmp, code);
429 op_code = get_code(env->buf);
431 /* get the mode if encoded */
432 if (env->options & OPT_WITH_MODE) {
433 if (next_tag(env->buf) != VLC_TAG_EMPTY) {
434 mode_code = get_code(env->buf);
440 pattern_dump_edge(env->dmp, env->curr_id, parent, position);
443 parent = env->curr_id;
444 pattern_dump_node(env->dmp, parent, op_code, mode_code);
446 /* ok, we have a new ID */
449 code = next_tag(env->buf);
450 if (code != VLC_TAG_END) {
451 /* more info, do recursion */
454 preds = get_code(env->buf);
456 pattern_start_children(env->dmp, parent);
457 for (i = 0; i < preds; ++i) {
458 _decode_node(parent, i, env);
460 pattern_finish_children(env->dmp, parent);
468 static void decode_node(BYTE *b, unsigned len)
472 unsigned code, options = 0;
474 init_buf(&buf, b, len);
477 env.curr_id = 1; /* 0 is used for special purpose */
478 env.dmp = &stdout_dump;
481 code = next_tag(&buf);
482 if (code == VLC_TAG_OPTION) {
483 options = get_code(&buf);
485 env.options = options;
487 _decode_node(0, 0, &env);
491 * the environment for the pattern calculation
493 typedef struct _pattern_env {
494 int max_depth; /**< maximum depth for pattern generation */
498 * Returns the associates pattern_entry_t for a CODE_BUF
500 static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
502 pattern_entry_t *key, *elem;
503 unsigned len = buf_lenght(buf);
506 key = obstack_alloc(&status->obst, sizeof(*key) + len - 1);
510 memcpy(key->buf, buf_content(buf), len);
512 hash = buf_hash(buf);
514 elem = pset_find(set, key, hash);
516 obstack_free(&status->obst, key);
520 cnt_clr(&key->count);
521 assert(key != (void *)4);
522 return pset_insert(set, key, hash);
526 * walker for nodes pattern calculation
528 static void calc_nodes_pattern(ir_node *node, void *ctx)
531 pattern_env_t *env = ctx;
533 pattern_entry_t *entry;
535 init_buf(&buf, buffer, sizeof(buffer));
536 encode_node(node, &buf, env->max_depth);
538 entry = pattern_get_entry(&buf, status->pattern_hash);
541 cnt_inc(&entry->count);
546 static void pattern_output(void)
548 pattern_entry_t *entry;
549 pattern_entry_t **pattern_arr;
550 int i, count = pset_count(status->pattern_hash);
552 printf("\n%d pattern detected\n", count);
557 pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
558 for (i = 0, entry = pset_first(status->pattern_hash);
560 entry = pset_next(status->pattern_hash), ++i) {
561 pattern_arr[i] = entry;
567 qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
569 for (i = 0; i < count; ++i) {
570 entry = pattern_arr[i];
571 if (entry->count.cnt[0] < status->bound)
574 printf("%8d\t", entry->count.cnt[0]);
575 decode_node(entry->buf, entry->len);
581 * calculates the pattern history
583 void stat_calc_pattern_history(ir_graph *irg)
587 if (! status->enable)
590 /* do NOT count the const code IRG */
591 if (irg == get_const_code_irg())
595 irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
599 * initialises the pattern history
601 void stat_init_pattern_history(int enable)
603 status->enable = enable;
608 status->options = OPT_WITH_MODE | OPT_ENC_GRAPH;
610 obstack_init(&status->obst);
612 /* create the hash-table */
613 status->pattern_hash = new_pset(pattern_cmp, 8);
617 * finishes the pattern history
619 void stat_finish_pattern_history(void)
621 if (! status->enable)
626 del_pset(status->pattern_hash);
627 obstack_free(&status->obst, NULL);