15 #include "pattern_dmp.h"
19 * just be make some things clear :-), the
22 #define HASH_MAP(type) pset_##type
24 typedef pset pset_pattern_entry_t;
26 typedef unsigned char BYTE;
32 typedef struct _code_buf_t {
33 BYTE *next; /**< next byte to be written */
34 BYTE *end; /**< end of the buffer */
35 BYTE *start; /**< start of the buffer */
36 unsigned hash; /**< calculates the hash value */
43 VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */
44 VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */
45 VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */
46 VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */
47 VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */
49 VLC_TAG_FIRST = 0xF1, /**< first possible tag value */
50 VLC_TAG_ICONST = 0xFB, /**< encodes an integer constant */
51 VLC_TAG_EMPTY = 0xFC, /**< encodes an empty entity */
52 VLC_TAG_OPTION = 0xFD, /**< options exists */
53 VLC_TAG_REF = 0xFE, /**< special tag, next code is an ID */
54 VLC_TAG_END = 0xFF, /**< end tag */
58 * An entry for patterns.
60 typedef struct _pattern_entry_t {
61 counter_t count; /**< amount of pattern occurance */
62 unsigned len; /**< length of the VLC encoded buffer */
63 BYTE buf[1]; /**< buffer contains the VLC encoded pattern */
70 OPT_WITH_MODE = 0x00000001, /**< use modes */
71 OPT_ENC_DAG = 0x00000002, /**< encode DAGs, not terms */
72 OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */
79 typedef struct _pattern_info_t {
80 int enable; /**< if non-zero, this module is enabled */
81 struct obstack obst; /**< obstack containing the counters */
82 HASH_MAP(pattern_entry_t) *pattern_hash; /**< hash map containing the counter for pattern */
83 unsigned bound; /**< lowest value for output */
84 unsigned options; /**< option mask */
90 static pattern_info_t _status, *status = &_status;
93 * compare two elements for counter
95 static int pattern_count_cmp(const void *elt, const void *key)
99 pattern_entry_t **e1 = (pattern_entry_t **)elt;
100 pattern_entry_t **e2 = (pattern_entry_t **)key;
102 /* we want it sorted in descending order */
103 cmp = cnt_cmp(&(*e2)->count, &(*e1)->count);
109 * compare two elements of the pattern hash
111 static int pattern_cmp(const void *elt, const void *key)
113 const pattern_entry_t *e1 = elt;
114 const pattern_entry_t *e2 = key;
115 int diff = e1->len - e2->len;
120 return memcmp(e1->buf, e2->buf, e1->len);
124 * initialize a code buffer
126 static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
128 buf->start = buf->next = data;
129 buf->end = data + len;
134 * put a byte into the buffer
136 static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte)
138 if (buf->next < buf->end) {
139 unsigned hash = buf->hash;
141 hash = (hash * 9) ^ byte;
148 * returns the current length of a buffer
150 static unsigned buf_lenght(const CODE_BUFFER *buf)
152 return buf->next - buf->start;
156 * returns the current content of a buffer
158 static const BYTE *buf_content(const CODE_BUFFER *buf)
164 * returns the hash value of a buffer
166 static unsigned buf_hash(const CODE_BUFFER *buf)
172 * returns the next byte from the buffer WITHOUT dropping
174 static INLINE BYTE look_byte(CODE_BUFFER *buf)
176 if (buf->next < buf->end)
182 * returns the next byte from the buffer WITH dropping
184 static INLINE BYTE get_byte(CODE_BUFFER *buf)
186 if (buf->next < buf->end)
191 #define BITS(n) (1 << (n))
194 * put a 32bit value into the buffer
196 static void put_code(CODE_BUFFER *buf, unsigned code)
198 if (code < BITS(7)) {
199 put_byte(buf, VLC_7BIT | code);
201 else if (code < BITS(6 + 8)) {
202 put_byte(buf, VLC_14BIT | (code >> 8));
205 else if (code < BITS(5 + 8 + 8)) {
206 put_byte(buf, VLC_21BIT | (code >> 16));
207 put_byte(buf, code >> 8);
210 else if (code < BITS(4 + 8 + 8 + 8)) {
211 put_byte(buf, VLC_28BIT | (code >> 24));
212 put_byte(buf, code >> 16);
213 put_byte(buf, code >> 8);
217 put_byte(buf, VLC_32BIT);
218 put_byte(buf, code >> 24);
219 put_byte(buf, code >> 16);
220 put_byte(buf, code >> 8);
225 #define BIT_MASK(n) ((1 << (n)) - 1)
228 * get 32 bit from the buffer
230 static unsigned get_code(CODE_BUFFER *buf)
232 unsigned code = get_byte(buf);
234 if (code < VLC_14BIT)
236 if (code < VLC_21BIT)
237 return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
238 if (code < VLC_28BIT) {
239 code = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
240 code |= get_byte(buf);
243 if (code < VLC_32BIT) {
244 code = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
245 code |= get_byte(buf) << 8;
246 code |= get_byte(buf);
249 if (code == VLC_32BIT) {
250 code = get_byte(buf) << 24;
251 code |= get_byte(buf) << 16;
252 code |= get_byte(buf) << 8;
253 code |= get_byte(buf);
256 /* should not happen */
257 assert(0 && "Wrong code in buffer");
263 * put a tag into the buffer
265 static void put_tag(CODE_BUFFER *buf, BYTE tag)
267 assert(tag >= VLC_TAG_FIRST && "invalid tag");
273 * returns the next tag or zero if the next code isn't a tag
275 static BYTE next_tag(CODE_BUFFER *buf)
277 BYTE b = look_byte(buf);
279 if (b >= VLC_TAG_FIRST)
280 return get_byte(buf);
285 * environment for the pattern encoder
287 typedef struct _codec_enc_t {
288 CODE_BUFFER *buf; /**< the code buffer */
289 set *id_set; /**< the set containing all already seen nodes */
290 unsigned curr_id; /**< current node id */
291 unsigned options; /**< encoding options */
292 pattern_dumper_t *dmp; /**< dumper for the decoder */
295 typedef struct _addr_entry_t {
296 void *addr; /**< the address */
297 unsigned id; /**< associated ID */
301 * compare two addresses
303 static int addr_cmp(const void *p1, const void *p2, size_t size) {
304 const addr_entry_t *e1 = p1;
305 const addr_entry_t *e2 = p2;
307 return e1->addr != e2->addr;
311 * encodes an IR-node, recursive worker
313 * @return reached depth
315 static int _encode_node(ir_node *node, int max_depth, codec_env_t *env)
317 addr_entry_t entry, *r_entry;
322 opcode code = get_irn_opcode(node);
324 /* insert the node into our ID map */
326 entry.id = env->curr_id;
328 s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), HASH_PTR(node));
329 r_entry = (addr_entry_t *)s_entry->dptr;
331 if (r_entry->id != env->curr_id) {
332 /* already in the map, add an REF */
333 put_tag(env->buf, VLC_TAG_REF);
334 put_code(env->buf, r_entry->id);
339 /* a new entry, proceed */
343 put_code(env->buf, (unsigned)code);
345 /* do we need the mode ? */
346 if (env->options & OPT_WITH_MODE) {
347 ir_mode *mode = get_irn_mode(node);
350 /* FIXME: not 64bit save */
351 put_code(env->buf, (unsigned)mode);
353 put_tag(env->buf, VLC_TAG_EMPTY);
356 /* do we need integer constants */
357 if (env->options & OPT_WITH_ICONST) {
358 if (code == iro_Const) {
359 tarval *tv = get_Const_tarval(node);
361 if (tarval_is_long(tv)) {
362 long v = get_tarval_long(tv);
364 put_tag(env->buf, VLC_TAG_ICONST);
365 put_code(env->buf, v);
372 if (max_depth <= 0) {
373 put_code(env->buf, 0);
377 preds = get_irn_arity(node);
378 put_code(env->buf, preds);
381 for (i = 0; i < preds; ++i) {
382 ir_node *n = get_irn_n(node, i);
384 depth = _encode_node(n, max_depth, env);
392 * encode a DAG staring by the IR-node node
394 * @param node The root node of the graph
395 * @param buf The code buffer to store the bitstring in
396 * @param max_depth The maximum depth for descending
398 * @return The depth of the encoded graph (without cycles)
400 static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
406 env.curr_id = 1; /* 0 is used for special purpose */
407 env.options = status->options;
410 if (env.options & OPT_ENC_DAG)
411 env.id_set = new_set(addr_cmp, 32);
415 /* encode options if any */
417 put_tag(buf, VLC_TAG_OPTION);
418 put_code(buf, env.options);
421 res = _encode_node(node, max_depth, &env);
423 if (env.options & OPT_ENC_DAG)
426 return max_depth - res;
430 * decode an IR-node, recursive walker
432 static void _decode_node(unsigned parent, int position, codec_env_t *env)
436 unsigned mode_code = 0;
440 code = next_tag(env->buf);
441 if (code == VLC_TAG_REF) { /* it's a REF */
442 code = get_code(env->buf);
448 * the mode of a Firm edge can be either computed from its target or
449 * from its source and position. We must take the second approach because
450 * we dont know the target here, it's a ref.
452 pattern_dump_edge(env->dmp, code, parent, position, edge_mode);
455 /* dump the node ref */
456 pattern_dump_ref(env->dmp, code);
462 op_code = get_code(env->buf);
464 /* get the mode if encoded */
465 if (env->options & OPT_WITH_MODE) {
466 if (next_tag(env->buf) != VLC_TAG_EMPTY) {
467 mode_code = get_code(env->buf);
471 /* check, if a ICONST attribute is given */
472 if (next_tag(env->buf) == VLC_TAG_ICONST) {
473 iconst = get_code(env->buf);
482 * the mode of a Firm edge can be either computed from its target or
483 * from its source and position. We take the second approach because
484 * we need it anyway for ref's.
486 pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode);
490 parent = env->curr_id;
491 pattern_dump_node(env->dmp, parent, op_code, mode_code, attr);
493 /* ok, we have a new ID */
496 code = next_tag(env->buf);
497 if (code != VLC_TAG_END) {
498 /* more info, do recursion */
501 preds = get_code(env->buf);
503 pattern_start_children(env->dmp, parent);
504 for (i = 0; i < preds; ++i) {
505 _decode_node(parent, i, env);
507 pattern_finish_children(env->dmp, parent);
515 static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump)
519 unsigned code, options = 0;
521 init_buf(&buf, b, len);
524 env.curr_id = 1; /* 0 is used for special purpose */
528 code = next_tag(&buf);
529 if (code == VLC_TAG_OPTION) {
530 options = get_code(&buf);
532 env.options = options;
534 _decode_node(0, 0, &env);
538 * the environment for the pattern calculation
540 typedef struct _pattern_env {
541 int max_depth; /**< maximum depth for pattern generation */
545 * Returns the associates pattern_entry_t for a CODE_BUF
547 * @param buf the code buffer
548 * @param set the hash table containing all pattern entries
550 static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
552 pattern_entry_t *key, *elem;
553 unsigned len = buf_lenght(buf);
556 key = obstack_alloc(&status->obst, sizeof(*key) + len - 1);
560 memcpy(key->buf, buf_content(buf), len);
562 hash = buf_hash(buf);
564 elem = pset_find(set, key, hash);
566 obstack_free(&status->obst, key);
570 cnt_clr(&key->count);
571 return pset_insert(set, key, hash);
577 static void count_pattern(CODE_BUFFER *buf, int depth) {
578 pattern_entry_t *entry;
580 /* ignore single node pattern (i.e. constants) */
582 entry = pattern_get_entry(buf, status->pattern_hash);
585 cnt_inc(&entry->count);
590 * pre-walker for nodes pattern calculation
592 static void calc_nodes_pattern(ir_node *node, void *ctx)
595 pattern_env_t *env = ctx;
599 init_buf(&buf, buffer, sizeof(buffer));
600 depth = encode_node(node, &buf, env->max_depth);
602 count_pattern(&buf, depth);
606 * output the collected pattern
608 static void pattern_output(void)
610 pattern_entry_t *entry;
611 pattern_entry_t **pattern_arr;
612 pattern_dumper_t *dump;
613 int i, count = pset_count(status->pattern_hash);
615 printf("\n%d pattern detected\n", count);
620 /* creates a dumper */
621 dump = new_vcg_dumper("pattern.vcg", 100);
623 pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
624 for (i = 0, entry = pset_first(status->pattern_hash);
626 entry = pset_next(status->pattern_hash), ++i) {
627 pattern_arr[i] = entry;
633 qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
635 for (i = 0; i < count; ++i) {
636 entry = pattern_arr[i];
637 if (cnt_to_uint(&entry->count) < status->bound)
641 pattern_dump_new_pattern(dump, &entry->count);
642 decode_node(entry->buf, entry->len, dump);
643 pattern_dump_finish_pattern(dump);
651 * calculates the pattern history
653 void stat_calc_pattern_history(ir_graph *irg)
657 if (! status->enable)
660 /* do NOT count the const code IRG */
661 if (irg == get_const_code_irg())
665 irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
669 * initializes the pattern history
671 void stat_init_pattern_history(int enable)
673 status->enable = enable;
678 status->options = OPT_WITH_MODE | OPT_ENC_DAG | OPT_WITH_ICONST;
680 obstack_init(&status->obst);
682 /* create the hash-table */
683 status->pattern_hash = new_pset(pattern_cmp, 8);
687 * finishes the pattern history
689 void stat_finish_pattern_history(void)
691 if (! status->enable)
696 del_pset(status->pattern_hash);
697 obstack_free(&status->obst, NULL);