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 address to be written. */
34 BYTE *end; /**< End address of the buffer. */
35 BYTE *start; /**< Start address of the buffer. */
36 unsigned hash; /**< The hash value for the buffer content. */
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 holding one pattern.
60 typedef struct _pattern_entry_t {
61 counter_t count; /**< Amount of pattern occurance. */
62 unsigned len; /**< The length of the VLC encoded buffer. */
63 BYTE buf[1]; /**< The buffer containing the VLC encoded pattern. */
67 * Current options for the pattern matcher.
70 OPT_WITH_MODE = 0x00000001, /**< use modes */
71 OPT_ENC_DAG = 0x00000002, /**< encode DAGs, not terms */
72 OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */
73 OPT_PERSIST_PATTERN = 0x00000008, /**< persistant pattern hash */
80 typedef struct _pattern_info_t {
81 int enable; /**< If non-zero, this module is enabled. */
82 struct obstack obst; /**< An obstack containing the counters. */
83 HASH_MAP(pattern_entry_t) *pattern_hash; /**< A hash map containing the pattern. */
84 unsigned bound; /**< Lowest value for pattern output. */
85 unsigned options; /**< Current option mask. */
91 static pattern_info_t _status, *status = &_status;
94 * Compare two pattern for its occurance counter.
96 static int pattern_count_cmp(const void *elt, const void *key)
100 pattern_entry_t **e1 = (pattern_entry_t **)elt;
101 pattern_entry_t **e2 = (pattern_entry_t **)key;
103 /* we want it sorted in descending order */
104 cmp = cnt_cmp(&(*e2)->count, &(*e1)->count);
107 } /* pattern_count_cmp */
110 * Compare two pattern for its pattern hash.
112 static int pattern_cmp(const void *elt, const void *key)
114 const pattern_entry_t *e1 = elt;
115 const pattern_entry_t *e2 = key;
116 int diff = e1->len - e2->len;
121 return memcmp(e1->buf, e2->buf, e1->len);
125 * Initialize a code buffer.
127 * @param buf the code buffer
128 * @param data a buffer address
129 * @param len the length of the data buffer
131 static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
133 buf->start = buf->next = data;
134 buf->end = data + len;
135 buf->hash = 0x2BAD4; /* An arbitrary seed. */
139 * Put a byte into the buffer.
141 * @param buf the code buffer
142 * @param byte the byte to write
144 * The hash value for the buffer content is updated.
146 static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte)
148 if (buf->next < buf->end) {
149 unsigned hash = buf->hash;
151 hash = (hash * 9) ^ byte;
158 * Returns the current length of a buffer.
160 * @param buf the code buffer
162 * @return the length of the buffer content
164 static unsigned buf_lenght(const CODE_BUFFER *buf)
166 return buf->next - buf->start;
170 * Returns the current content of a buffer.
172 * @param buf the code buffer
174 * @return the start address of the buffer content
176 static const BYTE *buf_content(const CODE_BUFFER *buf)
182 * Returns the hash value of a buffer.
184 * @param buf the code buffer
186 * @return the hash value of the buffer content
188 static unsigned buf_hash(const CODE_BUFFER *buf)
194 * Returns the next byte from the buffer WITHOUT dropping.
196 * @param buf the code buffer
198 * @return the next byte from the code buffer
200 static INLINE BYTE look_byte(CODE_BUFFER *buf)
202 if (buf->next < buf->end)
208 * Returns the next byte from the buffer WITH dropping.
210 * @param buf the code buffer
212 * @return the next byte from the code buffer
214 static INLINE BYTE get_byte(CODE_BUFFER *buf)
216 if (buf->next < buf->end)
221 #define BITS(n) (1 << (n))
224 * Put a 32bit value into the buffer.
226 * @param buf the code buffer
227 * @param code the code to be written into the buffer
229 static void put_code(CODE_BUFFER *buf, unsigned code)
231 if (code < BITS(7)) {
232 put_byte(buf, VLC_7BIT | code);
233 } else if (code < BITS(6 + 8)) {
234 put_byte(buf, VLC_14BIT | (code >> 8));
236 } else if (code < BITS(5 + 8 + 8)) {
237 put_byte(buf, VLC_21BIT | (code >> 16));
238 put_byte(buf, code >> 8);
240 } else if (code < BITS(4 + 8 + 8 + 8)) {
241 put_byte(buf, VLC_28BIT | (code >> 24));
242 put_byte(buf, code >> 16);
243 put_byte(buf, code >> 8);
246 put_byte(buf, VLC_32BIT);
247 put_byte(buf, code >> 24);
248 put_byte(buf, code >> 16);
249 put_byte(buf, code >> 8);
254 #define BIT_MASK(n) ((1 << (n)) - 1)
257 * Get 32 bit from the buffer.
259 * @param buf the code buffer
261 * @return next 32bit value from the code buffer
263 static unsigned get_code(CODE_BUFFER *buf)
265 unsigned code = get_byte(buf);
267 if (code < VLC_14BIT)
269 if (code < VLC_21BIT)
270 return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
271 if (code < VLC_28BIT) {
272 code = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
273 code |= get_byte(buf);
276 if (code < VLC_32BIT) {
277 code = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
278 code |= get_byte(buf) << 8;
279 code |= get_byte(buf);
282 if (code == VLC_32BIT) {
283 code = get_byte(buf) << 24;
284 code |= get_byte(buf) << 16;
285 code |= get_byte(buf) << 8;
286 code |= get_byte(buf);
289 /* should not happen */
290 assert(0 && "Wrong code in buffer");
296 * Put a tag into the buffer.
298 * @param buf the code buffer
299 * @param tag the tag to write to the code buffer
301 static void put_tag(CODE_BUFFER *buf, BYTE tag)
303 assert(tag >= VLC_TAG_FIRST && "invalid tag");
309 * Returns the next tag or zero if the next code isn't a tag.
311 * @param buf the code buffer
313 * @return the next tag in the code buffer
315 static BYTE next_tag(CODE_BUFFER *buf)
317 BYTE b = look_byte(buf);
319 if (b >= VLC_TAG_FIRST)
320 return get_byte(buf);
325 * An Environment for the pattern encoder.
327 typedef struct _codec_enc_t {
328 CODE_BUFFER *buf; /**< The current code buffer. */
329 set *id_set; /**< A set containing all already seen Firm nodes. */
330 unsigned curr_id; /**< The current node id. */
331 unsigned options; /**< The encoding options. */
332 pattern_dumper_t *dmp; /**< The dumper for the decoder. */
338 typedef struct _addr_entry_t {
339 void *addr; /**< the address */
340 unsigned id; /**< associated ID */
344 * Compare two addresses.
346 static int addr_cmp(const void *p1, const void *p2, size_t size) {
347 const addr_entry_t *e1 = p1;
348 const addr_entry_t *e2 = p2;
350 return e1->addr != e2->addr;
354 * Encodes an IR-node, recursive worker.
356 * @return reached depth
358 static int _encode_node(ir_node *node, int max_depth, codec_env_t *env)
360 addr_entry_t entry, *r_entry;
365 opcode code = get_irn_opcode(node);
367 /* insert the node into our ID map */
369 entry.id = env->curr_id;
371 s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), HASH_PTR(node));
372 r_entry = (addr_entry_t *)s_entry->dptr;
374 if (r_entry->id != env->curr_id) {
375 /* already in the map, add an REF */
376 put_tag(env->buf, VLC_TAG_REF);
377 put_code(env->buf, r_entry->id);
381 /* a new entry, proceed */
385 put_code(env->buf, (unsigned)code);
387 /* do we need the mode ? */
388 if (env->options & OPT_WITH_MODE) {
389 ir_mode *mode = get_irn_mode(node);
392 /* FIXME: not 64bit save */
393 put_code(env->buf, (unsigned)mode);
395 put_tag(env->buf, VLC_TAG_EMPTY);
398 /* do we need integer constants */
399 if (env->options & OPT_WITH_ICONST) {
400 if (code == iro_Const) {
401 tarval *tv = get_Const_tarval(node);
403 if (tarval_is_long(tv)) {
404 long v = get_tarval_long(tv);
406 put_tag(env->buf, VLC_TAG_ICONST);
407 put_code(env->buf, v);
414 if (max_depth <= 0) {
415 put_code(env->buf, 0);
419 preds = get_irn_arity(node);
420 put_code(env->buf, preds);
423 for (i = 0; i < preds; ++i) {
424 ir_node *n = get_irn_n(node, i);
426 depth = _encode_node(n, max_depth, env);
434 * Encode a DAG staring by the IR-node node.
436 * @param node The root node of the graph
437 * @param buf The code buffer to store the bitstring in
438 * @param max_depth The maximum depth for descending
440 * @return The depth of the encoded graph (without cycles)
442 static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
447 /* initialize the encoder environment */
449 env.curr_id = 1; /* 0 is used for special purpose */
450 env.options = status->options;
453 if (env.options & OPT_ENC_DAG)
454 env.id_set = new_set(addr_cmp, 32);
458 /* encode options if any for the decoder */
460 put_tag(buf, VLC_TAG_OPTION);
461 put_code(buf, env.options);
464 res = _encode_node(node, max_depth, &env);
466 if (env.id_set != NULL)
469 return max_depth - res;
473 * Decode an IR-node, recursive walker.
475 static void _decode_node(unsigned parent, int position, codec_env_t *env)
479 unsigned mode_code = 0;
483 code = next_tag(env->buf);
484 if (code == VLC_TAG_REF) { /* it's a REF */
485 code = get_code(env->buf);
491 * the mode of a Firm edge can be either computed from its target or
492 * from its source and position. We must take the second approach because
493 * we dont know the target here, it's a ref.
495 pattern_dump_edge(env->dmp, code, parent, position, edge_mode);
498 /* dump the node ref */
499 pattern_dump_ref(env->dmp, code);
505 op_code = get_code(env->buf);
507 /* get the mode if encoded */
508 if (env->options & OPT_WITH_MODE) {
509 if (next_tag(env->buf) != VLC_TAG_EMPTY) {
510 mode_code = get_code(env->buf);
514 /* check, if a ICONST attribute is given */
515 if (next_tag(env->buf) == VLC_TAG_ICONST) {
516 iconst = get_code(env->buf);
525 * the mode of a Firm edge can be either computed from its target or
526 * from its source and position. We take the second approach because
527 * we need it anyway for ref's.
529 pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode);
533 parent = env->curr_id;
534 pattern_dump_node(env->dmp, parent, op_code, mode_code, attr);
536 /* ok, we have a new ID */
539 code = next_tag(env->buf);
540 if (code != VLC_TAG_END) {
541 /* more info, do recursion */
544 preds = get_code(env->buf);
546 pattern_start_children(env->dmp, parent);
547 for (i = 0; i < preds; ++i) {
548 _decode_node(parent, i, env);
550 pattern_finish_children(env->dmp, parent);
558 static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump)
562 unsigned code, options = 0;
564 init_buf(&buf, b, len);
567 env.curr_id = 1; /* 0 is used for special purpose */
571 code = next_tag(&buf);
572 if (code == VLC_TAG_OPTION) {
573 options = get_code(&buf);
575 env.options = options;
577 _decode_node(0, 0, &env);
581 * The environment for the pattern calculation.
583 typedef struct _pattern_env {
584 int max_depth; /**< maximum depth for pattern generation. */
588 * Returns the associates pattern_entry_t for a CODE_BUF.
590 * @param buf the code buffer
591 * @param set the hash table containing all pattern entries
593 * @return the associated pattern_entry_t for the given code buffer
595 * If the code content was never seen before, a new pattern_entry is created
598 static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
600 pattern_entry_t *key, *elem;
601 unsigned len = buf_lenght(buf);
604 key = obstack_alloc(&status->obst, sizeof(*key) + len - 1);
608 memcpy(key->buf, buf_content(buf), len);
610 hash = buf_hash(buf);
612 elem = pset_find(set, key, hash);
614 obstack_free(&status->obst, key);
618 cnt_clr(&key->count);
619 return pset_insert(set, key, hash);
620 } /* pattern_get_entry */
623 * Increase the count for a pattern.
625 * @param buf the code buffer containing the pattern
626 * @param depth the pattern depth
628 * @note Single node patterns are ignored
630 static void count_pattern(CODE_BUFFER *buf, int depth) {
631 pattern_entry_t *entry;
633 /* ignore single node pattern (i.e. constants) */
635 entry = pattern_get_entry(buf, status->pattern_hash);
638 cnt_inc(&entry->count);
640 } /* count_pattern */
643 * Pre-walker for nodes pattern calculation.
645 static void calc_nodes_pattern(ir_node *node, void *ctx)
648 pattern_env_t *env = ctx;
652 init_buf(&buf, buffer, sizeof(buffer));
653 depth = encode_node(node, &buf, env->max_depth);
655 count_pattern(&buf, depth);
656 } /* calc_nodes_pattern */
659 * Store all collected patterns.
661 * @param fname filename for storage
663 static void store_pattern(const char *fname)
666 pattern_entry_t *entry;
667 int i, count = pset_count(status->pattern_hash);
672 f = fopen(fname, "wb");
678 fwrite("FPS1", 4, 1, f);
679 fwrite(&count, sizeof(count), 1, f);
681 for (i = 0, entry = pset_first(status->pattern_hash);
683 entry = pset_next(status->pattern_hash), ++i) {
684 fwrite(entry, offsetof(pattern_entry_t, buf) + entry->len, 1, f);
688 } /* store_pattern */
691 * Read collected patterns from a file.
693 * @param fname filename
695 static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname)
698 pattern_entry_t *entry, tmp;
702 HASH_MAP(pattern_entry_t) *pattern_hash = new_pset(pattern_cmp, 8);
706 f = fopen(fname, "rb");
712 fread(magic, 4, 1, f);
714 fread(&count, sizeof(count), 1, f);
715 if (memcmp(magic, "FPS1", 4) != 0 || count <= 0) {
716 fprintf(stderr, "Error: %s is not a Firm pattern store. Ignored.\n", fname);
722 /* read all pattern entries and put them into the hash table. */
723 for (i = 0; i < count; ++i) {
724 init_buf(&buf, buffer, sizeof(buffer));
725 fread(&tmp, offsetof(pattern_entry_t, buf), 1, f);
726 for (j = 0; j < tmp.len; ++j)
727 put_byte(&buf, fgetc(f));
728 entry = pattern_get_entry(&buf, pattern_hash);
729 memcpy(&entry->count, &tmp.count, sizeof(entry->count));
734 printf("Read %d pattern from %s\n", pset_count(pattern_hash), fname);
740 * Write the collected patterns to a VCG file for inspection.
742 * @param fname name of the VCG file to create
744 static void pattern_output(const char *fname)
746 pattern_entry_t *entry;
747 pattern_entry_t **pattern_arr;
748 pattern_dumper_t *dump;
749 int i, count = pset_count(status->pattern_hash);
751 printf("\n%d pattern detected\n", count);
756 /* creates a dumper */
757 dump = new_vcg_dumper(fname, 100);
759 pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
760 for (i = 0, entry = pset_first(status->pattern_hash);
762 entry = pset_next(status->pattern_hash), ++i) {
763 pattern_arr[i] = entry;
769 qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
771 for (i = 0; i < count; ++i) {
772 entry = pattern_arr[i];
773 if (cnt_to_uint(&entry->count) < status->bound)
777 pattern_dump_new_pattern(dump, &entry->count);
778 decode_node(entry->buf, entry->len, dump);
779 pattern_dump_finish_pattern(dump);
784 } /* pattern_output */
787 * Calculates the pattern history.
789 void stat_calc_pattern_history(ir_graph *irg)
793 if (! status->enable)
796 /* do NOT count the const code IRG */
797 if (irg == get_const_code_irg())
801 irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
802 } /* stat_calc_pattern_history */
805 * Initializes the pattern history.
807 void stat_init_pattern_history(int enable)
809 HASH_MAP(pattern_entry_t) *pattern_hash = NULL;
811 status->enable = enable;
816 status->options = /* OPT_WITH_MODE | */ OPT_ENC_DAG | OPT_WITH_ICONST | OPT_PERSIST_PATTERN;
818 obstack_init(&status->obst);
820 /* create the hash-table */
821 if (status->options & OPT_PERSIST_PATTERN)
822 pattern_hash = read_pattern("pattern.fps");
823 if (pattern_hash == NULL)
824 pattern_hash = new_pset(pattern_cmp, 8);
825 status->pattern_hash = pattern_hash;
826 } /* stat_init_pattern_history */
829 * Finish the pattern history.
831 void stat_finish_pattern_history(void)
833 if (! status->enable)
836 store_pattern("pattern.fps");
837 pattern_output("pattern.vcg");
839 del_pset(status->pattern_hash);
840 obstack_free(&status->obst, NULL);
843 } /* stat_finish_pattern_history */