2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Statistics for Firm. Pattern history.
23 * @author Michael Beck
41 #include "pattern_dmp.h"
44 #ifdef FIRM_STATISTICS
47 * just be make some things clear :-), the
50 #define HASH_MAP(type) pset_##type
52 typedef pset pset_pattern_entry_t;
54 typedef unsigned char BYTE;
56 /** Maximum size of the pattern store. */
57 #define PATTERN_STORE_SIZE 2048
63 typedef struct _code_buf_t {
64 BYTE *next; /**< Next byte address to be written. */
65 BYTE *end; /**< End address of the buffer. */
66 BYTE *start; /**< Start address of the buffer. */
67 unsigned hash; /**< The hash value for the buffer content. */
68 unsigned overrun; /**< flag set if the buffer was overrun */
75 VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */
76 VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */
77 VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */
78 VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */
79 VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */
81 VLC_TAG_FIRST = 0xF1, /**< First possible tag value. */
82 VLC_TAG_ICONST = 0xFB, /**< Encodes an integer constant. */
83 VLC_TAG_EMPTY = 0xFC, /**< Encodes an empty entity. */
84 VLC_TAG_OPTION = 0xFD, /**< Options exists. */
85 VLC_TAG_REF = 0xFE, /**< Special tag, next code is an ID. */
86 VLC_TAG_END = 0xFF, /**< End tag. */
90 * An entry for holding one pattern.
92 typedef struct _pattern_entry_t {
93 counter_t count; /**< Amount of pattern occurance. */
94 unsigned len; /**< The length of the VLC encoded buffer. */
95 BYTE buf[1]; /**< The buffer containing the VLC encoded pattern. */
99 * Current options for the pattern matcher.
102 OPT_WITH_MODE = 0x00000001, /**< use modes */
103 OPT_ENC_DAG = 0x00000002, /**< encode DAGs, not terms */
104 OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */
105 OPT_PERSIST_PATTERN = 0x00000008, /**< persistent pattern hash */
112 typedef struct _pattern_info_t {
113 int enable; /**< If non-zero, this module is enabled. */
114 struct obstack obst; /**< An obstack containing the counters. */
115 HASH_MAP(pattern_entry_t) *pattern_hash; /**< A hash map containing the pattern. */
116 unsigned bound; /**< Lowest value for pattern output. */
117 unsigned options; /**< Current option mask. */
118 unsigned min_depth; /**< Minimum pattern depth. */
119 unsigned max_depth; /**< Maximum pattern depth. */
125 static pattern_info_t _status, *status = &_status;
128 * Compare two pattern for its occurance counter.
130 static int pattern_count_cmp(const void *elt, const void *key) {
133 pattern_entry_t **e1 = (pattern_entry_t **)elt;
134 pattern_entry_t **e2 = (pattern_entry_t **)key;
136 /* we want it sorted in descending order */
137 cmp = cnt_cmp(&(*e2)->count, &(*e1)->count);
140 } /* pattern_count_cmp */
143 * Compare two pattern for its pattern hash.
145 static int pattern_cmp(const void *elt, const void *key) {
146 const pattern_entry_t *e1 = elt;
147 const pattern_entry_t *e2 = key;
148 int diff = e1->len - e2->len;
153 return memcmp(e1->buf, e2->buf, e1->len);
157 * Initialize a code buffer.
159 * @param buf the code buffer
160 * @param data a buffer address
161 * @param len the length of the data buffer
163 static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len) {
166 buf->end = data + len;
167 buf->hash = 0x2BAD4; /* An arbitrary seed. */
172 * Put a byte into the buffer.
174 * @param buf the code buffer
175 * @param byte the byte to write
177 * The hash value for the buffer content is updated.
179 static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte) {
180 if (buf->next < buf->end) {
182 buf->hash = (buf->hash * 9) ^ byte;
189 * Returns the current length of a buffer.
191 * @param buf the code buffer
193 * @return the length of the buffer content
195 static unsigned buf_lenght(const CODE_BUFFER *buf) {
196 return buf->next - buf->start;
200 * Returns the current content of a buffer.
202 * @param buf the code buffer
204 * @return the start address of the buffer content
206 static const BYTE *buf_content(const CODE_BUFFER *buf) {
211 * Returns the hash value of a buffer.
213 * @param buf the code buffer
215 * @return the hash value of the buffer content
217 static unsigned buf_hash(const CODE_BUFFER *buf) {
222 * Returns non-zero if a buffer overrun has occurred.
224 * @param buf the code buffer
226 static unsigned buf_overrun(const CODE_BUFFER *buf) {
231 * Returns the next byte from the buffer WITHOUT dropping.
233 * @param buf the code buffer
235 * @return the next byte from the code buffer
237 static INLINE BYTE look_byte(CODE_BUFFER *buf) {
238 if (buf->next < buf->end)
244 * Returns the next byte from the buffer WITH dropping.
246 * @param buf the code buffer
248 * @return the next byte from the code buffer
250 static INLINE BYTE get_byte(CODE_BUFFER *buf) {
251 if (buf->next < buf->end)
256 #define BITS(n) (1 << (n))
259 * Put a 32bit value into the buffer.
261 * @param buf the code buffer
262 * @param code the code to be written into the buffer
264 static void put_code(CODE_BUFFER *buf, unsigned code) {
265 if (code < BITS(7)) {
266 put_byte(buf, VLC_7BIT | code);
267 } else if (code < BITS(6 + 8)) {
268 put_byte(buf, VLC_14BIT | (code >> 8));
270 } else if (code < BITS(5 + 8 + 8)) {
271 put_byte(buf, VLC_21BIT | (code >> 16));
272 put_byte(buf, code >> 8);
274 } else if (code < BITS(4 + 8 + 8 + 8)) {
275 put_byte(buf, VLC_28BIT | (code >> 24));
276 put_byte(buf, code >> 16);
277 put_byte(buf, code >> 8);
280 put_byte(buf, VLC_32BIT);
281 put_byte(buf, code >> 24);
282 put_byte(buf, code >> 16);
283 put_byte(buf, code >> 8);
288 #define BIT_MASK(n) ((1 << (n)) - 1)
291 * Get 32 bit from the buffer.
293 * @param buf the code buffer
295 * @return next 32bit value from the code buffer
297 static unsigned get_code(CODE_BUFFER *buf) {
298 unsigned code = get_byte(buf);
300 if (code < VLC_14BIT)
302 if (code < VLC_21BIT)
303 return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
304 if (code < VLC_28BIT) {
305 code = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
306 code |= get_byte(buf);
309 if (code < VLC_32BIT) {
310 code = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
311 code |= get_byte(buf) << 8;
312 code |= get_byte(buf);
315 if (code == VLC_32BIT) {
316 code = get_byte(buf) << 24;
317 code |= get_byte(buf) << 16;
318 code |= get_byte(buf) << 8;
319 code |= get_byte(buf);
322 /* should not happen */
323 assert(0 && "Wrong code in buffer");
329 * Put a tag into the buffer.
331 * @param buf the code buffer
332 * @param tag the tag to write to the code buffer
334 static void put_tag(CODE_BUFFER *buf, BYTE tag) {
335 assert(tag >= VLC_TAG_FIRST && "invalid tag");
341 * Returns the next tag or zero if the next code isn't a tag.
343 * @param buf the code buffer
345 * @return the next tag in the code buffer
347 static BYTE next_tag(CODE_BUFFER *buf) {
348 BYTE b = look_byte(buf);
350 if (b >= VLC_TAG_FIRST)
351 return get_byte(buf);
356 * An Environment for the pattern encoder.
358 typedef struct _codec_enc_t {
359 CODE_BUFFER *buf; /**< The current code buffer. */
360 set *id_set; /**< A set containing all already seen Firm nodes. */
361 unsigned curr_id; /**< The current node id. */
362 unsigned options; /**< The encoding options. */
363 pattern_dumper_t *dmp; /**< The dumper for the decoder. */
369 typedef struct _addr_entry_t {
370 void *addr; /**< the address */
371 unsigned id; /**< associated ID */
375 * Compare two addresses.
377 static int addr_cmp(const void *p1, const void *p2, size_t size) {
378 const addr_entry_t *e1 = p1;
379 const addr_entry_t *e2 = p2;
382 return e1->addr != e2->addr;
386 * Encodes an IR-node, recursive worker.
388 * @return reached depth
390 static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) {
391 addr_entry_t entry, *r_entry;
396 ir_opcode code = get_irn_opcode(node);
398 /* insert the node into our ID map */
400 entry.id = env->curr_id;
402 s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), HASH_PTR(node));
403 r_entry = (addr_entry_t *)s_entry->dptr;
405 if (r_entry->id != env->curr_id) {
406 /* already in the map, add an REF */
407 put_tag(env->buf, VLC_TAG_REF);
408 put_code(env->buf, r_entry->id);
412 /* a new entry, proceed */
416 put_code(env->buf, (unsigned)code);
418 /* do we need the mode ? */
419 if (env->options & OPT_WITH_MODE) {
420 ir_mode *mode = get_irn_mode(node);
423 /* FIXME: not 64bit save */
424 put_code(env->buf, (unsigned)mode);
426 put_tag(env->buf, VLC_TAG_EMPTY);
429 /* do we need integer constants */
430 if (env->options & OPT_WITH_ICONST) {
431 if (code == iro_Const) {
432 tarval *tv = get_Const_tarval(node);
434 if (tarval_is_long(tv)) {
435 long v = get_tarval_long(tv);
437 put_tag(env->buf, VLC_TAG_ICONST);
438 put_code(env->buf, v);
445 if (max_depth <= 0) {
446 put_code(env->buf, 0);
450 preds = get_irn_arity(node);
451 put_code(env->buf, preds);
454 if (is_op_commutative(get_irn_op(node))) {
455 ir_node *l = get_binop_left(node);
456 ir_node *r = get_binop_right(node);
457 int opcode_diff = (int)get_irn_opcode(l) - (int)get_irn_opcode(r);
459 if (opcode_diff > 0) {
463 } else if (opcode_diff == 0 && l != r) {
464 /* Both nodes have the same opcode, but are different.
465 Need a better method here to decide which goes to the left side. */
468 /* special handling for commutative operators */
469 depth = _encode_node(l, max_depth, env);
472 depth = _encode_node(r, max_depth, env);
476 for (i = 0; i < preds; ++i) {
477 ir_node *n = get_irn_n(node, i);
479 depth = _encode_node(n, max_depth, env);
488 * Encode a DAG starting by the IR-node node.
490 * @param node The root node of the graph
491 * @param buf The code buffer to store the bitstring in
492 * @param max_depth The maximum depth for descending
494 * @return The depth of the encoded graph (without cycles)
496 static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) {
500 /* initialize the encoder environment */
502 env.curr_id = 1; /* 0 is used for special purpose */
503 env.options = status->options;
506 if (env.options & OPT_ENC_DAG)
507 env.id_set = new_set(addr_cmp, 32);
511 /* encode options if any for the decoder */
513 put_tag(buf, VLC_TAG_OPTION);
514 put_code(buf, env.options);
517 res = _encode_node(node, max_depth, &env);
519 if (env.id_set != NULL)
522 return max_depth - res;
526 * Decode an IR-node, recursive walker.
528 static void _decode_node(unsigned parent, int position, codec_env_t *env) {
531 unsigned mode_code = 0;
535 code = next_tag(env->buf);
536 if (code == VLC_TAG_REF) { /* it's a REF */
537 code = get_code(env->buf);
543 * the mode of a Firm edge can be either computed from its target or
544 * from its source and position. We must take the second approach because
545 * we don't know the target here, it's a ref.
547 pattern_dump_edge(env->dmp, code, parent, position, edge_mode);
550 /* dump the node ref */
551 pattern_dump_ref(env->dmp, code);
557 op_code = get_code(env->buf);
559 /* get the mode if encoded */
560 if (env->options & OPT_WITH_MODE) {
561 if (next_tag(env->buf) != VLC_TAG_EMPTY) {
562 mode_code = get_code(env->buf);
566 /* check, if a ICONST attribute is given */
567 if (next_tag(env->buf) == VLC_TAG_ICONST) {
568 iconst = get_code(env->buf);
577 * the mode of a Firm edge can be either computed from its target or
578 * from its source and position. We take the second approach because
579 * we need it anyway for ref's.
581 pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode);
585 parent = env->curr_id;
586 pattern_dump_node(env->dmp, parent, op_code, mode_code, attr);
588 /* ok, we have a new ID */
591 code = next_tag(env->buf);
592 if (code != VLC_TAG_END) {
593 /* more info, do recursion */
596 preds = get_code(env->buf);
598 pattern_start_children(env->dmp, parent);
599 for (i = 0; i < preds; ++i) {
600 _decode_node(parent, i, env);
602 pattern_finish_children(env->dmp, parent);
610 static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) {
613 unsigned code, options = 0;
615 init_buf(&buf, b, len);
618 env.curr_id = 1; /* 0 is used for special purpose */
622 code = next_tag(&buf);
623 if (code == VLC_TAG_OPTION) {
624 options = get_code(&buf);
626 env.options = options;
628 _decode_node(0, 0, &env);
632 * The environment for the pattern calculation.
634 typedef struct _pattern_env {
635 int max_depth; /**< maximum depth for pattern generation. */
639 * Returns the associates pattern_entry_t for a CODE_BUF.
641 * @param buf the code buffer
642 * @param set the hash table containing all pattern entries
644 * @return the associated pattern_entry_t for the given code buffer
646 * If the code content was never seen before, a new pattern_entry is created
649 static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) {
650 pattern_entry_t *key, *elem;
651 unsigned len = buf_lenght(buf);
654 key = obstack_alloc(&status->obst, offsetof(pattern_entry_t, buf) + len);
658 memcpy(key->buf, buf_content(buf), len);
660 hash = buf_hash(buf);
662 elem = pset_find(set, key, hash);
664 obstack_free(&status->obst, key);
668 cnt_clr(&key->count);
669 return pset_insert(set, key, hash);
670 } /* pattern_get_entry */
673 * Increase the count for a pattern.
675 * @param buf the code buffer containing the pattern
676 * @param depth the pattern depth
678 * @note Single node patterns are ignored
680 static void count_pattern(CODE_BUFFER *buf, int depth) {
681 pattern_entry_t *entry;
683 /* ignore single node pattern (i.e. constants) */
685 entry = pattern_get_entry(buf, status->pattern_hash);
688 cnt_inc(&entry->count);
690 } /* count_pattern */
693 * Pre-walker for nodes pattern calculation.
695 static void calc_nodes_pattern(ir_node *node, void *ctx) {
696 pattern_env_t *env = ctx;
697 BYTE buffer[PATTERN_STORE_SIZE];
701 init_buf(&buf, buffer, sizeof(buffer));
702 depth = encode_node(node, &buf, env->max_depth);
704 if (buf_overrun(&buf)) {
705 fprintf(stderr, "Pattern store: buffer overrun at size %d. Pattern ignored.\n", sizeof(buffer));
707 count_pattern(&buf, depth);
708 } /* calc_nodes_pattern */
711 * Store all collected patterns.
713 * @param fname filename for storage
715 static void store_pattern(const char *fname) {
717 pattern_entry_t *entry;
718 int i, count = pset_count(status->pattern_hash);
723 f = fopen(fname, "wb");
729 fwrite("FPS1", 4, 1, f);
730 fwrite(&count, sizeof(count), 1, f);
732 for (i = 0, entry = pset_first(status->pattern_hash);
734 entry = pset_next(status->pattern_hash), ++i) {
735 fwrite(entry, offsetof(pattern_entry_t, buf) + entry->len, 1, f);
738 } /* store_pattern */
741 * Read collected patterns from a file.
743 * @param fname filename
745 static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname) {
747 pattern_entry_t *entry, tmp;
751 HASH_MAP(pattern_entry_t) *pattern_hash = new_pset(pattern_cmp, 8);
752 BYTE buffer[PATTERN_STORE_SIZE];
755 f = fopen(fname, "rb");
761 fread(magic, 4, 1, f);
763 fread(&count, sizeof(count), 1, f);
764 if (memcmp(magic, "FPS1", 4) != 0 || count <= 0) {
765 fprintf(stderr, "Error: %s is not a Firm pattern store. Ignored.\n", fname);
770 /* read all pattern entries and put them into the hash table. */
771 for (i = 0; i < count; ++i) {
772 init_buf(&buf, buffer, sizeof(buffer));
773 fread(&tmp, offsetof(pattern_entry_t, buf), 1, f);
774 for (j = 0; j < tmp.len; ++j)
775 put_byte(&buf, fgetc(f));
776 entry = pattern_get_entry(&buf, pattern_hash);
777 memcpy(&entry->count, &tmp.count, sizeof(entry->count));
781 printf("Read %d pattern from %s\n", count, fname);
782 assert(pset_count(pattern_hash) == count);
788 * Write the collected patterns to a VCG file for inspection.
790 * @param fname name of the VCG file to create
792 static void pattern_output(const char *fname) {
793 pattern_entry_t *entry;
794 pattern_entry_t **pattern_arr;
795 pattern_dumper_t *dump;
796 int i, count = pset_count(status->pattern_hash);
798 printf("\n%d pattern detected\n", count);
803 /* creates a dumper */
804 dump = new_vcg_dumper(fname, 100);
806 pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
807 for (i = 0, entry = pset_first(status->pattern_hash);
809 entry = pset_next(status->pattern_hash), ++i) {
810 pattern_arr[i] = entry;
816 qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
818 for (i = 0; i < count; ++i) {
819 entry = pattern_arr[i];
820 if (cnt_to_uint(&entry->count) < status->bound)
824 pattern_dump_new_pattern(dump, &entry->count);
825 decode_node(entry->buf, entry->len, dump);
826 pattern_dump_finish_pattern(dump);
831 } /* pattern_output */
834 * Calculates the pattern history.
836 void stat_calc_pattern_history(ir_graph *irg) {
840 if (! status->enable)
843 /* do NOT count the const code IRG */
844 if (irg == get_const_code_irg())
847 for (i = status->min_depth; i <= status->max_depth; ++i) {
849 irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
851 } /* stat_calc_pattern_history */
854 * Initializes the pattern history.
856 void stat_init_pattern_history(int enable) {
857 HASH_MAP(pattern_entry_t) *pattern_hash = NULL;
859 status->enable = enable;
864 status->options = /* OPT_WITH_MODE | */ OPT_ENC_DAG | OPT_WITH_ICONST | OPT_PERSIST_PATTERN;
865 status->min_depth = 3;
866 status->max_depth = 5;
868 obstack_init(&status->obst);
870 /* create the hash-table */
871 if (status->options & OPT_PERSIST_PATTERN)
872 pattern_hash = read_pattern("pattern.fps");
873 if (pattern_hash == NULL)
874 pattern_hash = new_pset(pattern_cmp, 8);
875 status->pattern_hash = pattern_hash;
876 } /* stat_init_pattern_history */
879 * Finish the pattern history.
881 void stat_finish_pattern_history(const char *fname) {
883 if (! status->enable)
886 store_pattern("pattern.fps");
887 pattern_output("pattern.vcg");
889 del_pset(status->pattern_hash);
890 obstack_free(&status->obst, NULL);
893 } /* stat_finish_pattern_history */
895 #endif /* FIRM_STATISTICS */