+ unsigned code;
+ unsigned op_code;
+ unsigned mode_code = 0;
+ long iconst;
+ void *attr = NULL;
+
+ code = next_tag(env->buf);
+ if (code == VLC_TAG_REF) { /* it's a REF */
+ code = get_code(env->buf);
+
+ /* dump the edge */
+ if (parent) {
+ int edge_mode = 0;
+ /*
+ * the mode of a Firm edge can be either computed from its target or
+ * from its source and position. We must take the second approach because
+ * we don't know the target here, it's a ref.
+ */
+ pattern_dump_edge(env->dmp, code, parent, position, edge_mode);
+ }
+
+ /* dump the node ref */
+ pattern_dump_ref(env->dmp, code);
+
+ return;
+ }
+
+ /* get the opcode */
+ op_code = get_code(env->buf);
+
+ /* get the mode if encoded */
+ if (env->options & OPT_WITH_MODE) {
+ if (next_tag(env->buf) != VLC_TAG_EMPTY) {
+ mode_code = get_code(env->buf);
+ }
+ }
+
+ /* check, if a ICONST attribute is given */
+ if (next_tag(env->buf) == VLC_TAG_ICONST) {
+ iconst = get_code(env->buf);
+ attr = &iconst;
+ }
+
+ /* dump the edge */
+ if (parent) {
+ int edge_mode = 0;
+
+ /*
+ * the mode of a Firm edge can be either computed from its target or
+ * from its source and position. We take the second approach because
+ * we need it anyway for ref's.
+ */
+ pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode);
+ }
+
+ /* dump the node */
+ parent = env->curr_id;
+ pattern_dump_node(env->dmp, parent, op_code, mode_code, attr);
+
+ /* ok, we have a new ID */
+ ++env->curr_id;
+
+ code = next_tag(env->buf);
+ if (code != VLC_TAG_END) {
+ /* more info, do recursion */
+ int i, preds;
+
+ preds = get_code(env->buf);
+ if (preds > 0) {
+ pattern_start_children(env->dmp, parent);
+ for (i = 0; i < preds; ++i) {
+ _decode_node(parent, i, env);
+ }
+ pattern_finish_children(env->dmp, parent);
+ }
+ }
+}
+
+/**
+ * Decode an IR-node.
+ */
+static void decode_node(BYTE *b, size_t len, pattern_dumper_t *dump)
+{
+ codec_env_t env;
+ CODE_BUFFER buf;
+ unsigned code, options = 0;
+
+ init_buf(&buf, b, len);
+
+ env.buf = &buf;
+ env.curr_id = 1; /* 0 is used for special purpose */
+ env.dmp = dump;
+
+ /* decode options */
+ code = next_tag(&buf);
+ if (code == VLC_TAG_OPTION) {
+ options = get_code(&buf);
+ }
+ env.options = options;
+
+ _decode_node(0, 0, &env);
+}
+
+/**
+ * The environment for the pattern calculation.
+ */
+typedef struct pattern_env {
+ 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
+ *
+ * @return the associated pattern_entry_t for the given code buffer
+ *
+ * If the code content was never seen before, a new pattern_entry is created
+ * and returned.
+ */
+static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
+{
+ pattern_entry_t *key, *elem;
+ size_t len = buf_lenght(buf);
+ unsigned hash;
+
+ key = OALLOCF(&status->obst, pattern_entry_t, buf, len);
+ key->len = len;
+ memcpy(key->buf, buf_content(buf), len);
+
+ hash = buf_hash(buf);
+
+ elem = (pattern_entry_t*)pset_find(set, key, hash);
+ if (elem != NULL) {
+ obstack_free(&status->obst, key);
+ return elem;
+ }
+
+ cnt_clr(&key->count);
+ return (pattern_entry_t*)pset_insert(set, key, hash);
+}
+
+/**
+ * Increase the count for a pattern.
+ *
+ * @param buf the code buffer containing the pattern
+ * @param depth the pattern depth
+ *
+ * @note Single node patterns are ignored
+ */
+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)
+{
+ pattern_env_t *env = (pattern_env_t*)ctx;
+ BYTE buffer[PATTERN_STORE_SIZE];
+ CODE_BUFFER buf;
+ int depth;
+
+ init_buf(&buf, buffer, sizeof(buffer));
+ depth = encode_node(node, &buf, env->max_depth);
+
+ if (buf_overrun(&buf)) {
+ lc_fprintf(stderr, "Pattern store: buffer overrun at size %zu. Pattern ignored.\n", sizeof(buffer));
+ } else
+ count_pattern(&buf, depth);
+}
+
+/**
+ * Store all collected patterns.
+ *
+ * @param fname filename for storage
+ */
+static void store_pattern(const char *fname)
+{
+ FILE *f;
+ size_t count = pset_count(status->pattern_hash);
+
+ if (count <= 0)
+ return;
+
+ f = fopen(fname, "wb");
+ if (! f) {
+ perror(fname);
+ return;
+ }
+
+ fwrite("FPS1", 4, 1, f);
+ fwrite(&count, sizeof(count), 1, f);
+
+ foreach_pset(status->pattern_hash, pattern_entry_t, entry) {
+ fwrite(entry, offsetof(pattern_entry_t, buf) + entry->len, 1, f);
+ }
+ fclose(f);
+}
+
+/**
+ * Read collected patterns from a file.
+ *
+ * @param fname filename
+ */
+static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname)
+{
+ FILE *f;
+ pattern_entry_t *entry, tmp;
+ size_t i, count;
+ unsigned j;
+ char magic[4];
+ HASH_MAP(pattern_entry_t) *pattern_hash = new_pset(pattern_cmp, 8);
+ BYTE buffer[PATTERN_STORE_SIZE];
+ CODE_BUFFER buf;
+ int res;
+
+ f = fopen(fname, "rb");
+ if (! f) {
+ perror(fname);
+ return NULL;
+ }
+
+ res = fread(magic, 4, 1, f);
+ if (res != 1)
+ goto read_error;
+ count = 0;
+ res = fread(&count, sizeof(count), 1, f);
+ if (res != 1 || memcmp(magic, "FPS1", 4) != 0 || count <= 0)
+ goto read_error;
+
+ /* read all pattern entries and put them into the hash table. */
+ for (i = 0; i < count; ++i) {
+ init_buf(&buf, buffer, sizeof(buffer));
+ res = fread(&tmp, offsetof(pattern_entry_t, buf), 1, f);
+ if (res != 1)
+ goto read_error;
+ for (j = 0; j < tmp.len; ++j)
+ put_byte(&buf, fgetc(f));
+ entry = pattern_get_entry(&buf, pattern_hash);
+ entry->count = tmp.count;
+ }
+ fclose(f);
+
+ lc_printf("Read %zu pattern from %s\n", count, fname);
+ assert(pset_count(pattern_hash) == count);
+
+ return pattern_hash;
+
+read_error:
+ fprintf(stderr, "Error: %s is not a Firm pattern store. Ignored.\n", fname);
+ fclose(f);
+ return NULL;
+}
+
+/**
+ * Write the collected patterns to a VCG file for inspection.
+ *
+ * @param fname name of the VCG file to create
+ */
+static void pattern_output(const char *fname)
+{
+ pattern_entry_t **pattern_arr;
+ pattern_dumper_t *dump;
+ size_t i, count = pset_count(status->pattern_hash);
+
+ lc_printf("\n%zu pattern detected\n", count);
+
+ if (count == 0)
+ return;
+
+ /* creates a dumper */
+ dump = new_vcg_dumper(fname, 100);
+
+ pattern_arr = XMALLOCN(pattern_entry_t*, count);
+ i = 0;
+ foreach_pset(status->pattern_hash, pattern_entry_t, entry) {
+ pattern_arr[i++] = entry;
+ }
+ assert(count == i);
+ count = i;
+
+ /* sort it */
+ qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
+
+ for (i = 0; i < count; ++i) {
+ pattern_entry_t *const entry = pattern_arr[i];
+ if (cnt_to_uint(&entry->count) < status->bound)
+ continue;
+
+ /* dump a pattern */
+ pattern_dump_new_pattern(dump, &entry->count);
+ decode_node(entry->buf, entry->len, dump);
+ pattern_dump_finish_pattern(dump);
+ }
+
+ /* destroy it */
+ pattern_end(dump);
+}
+
+/*
+ * Calculates the pattern history.
+ */
+void stat_calc_pattern_history(ir_graph *irg)
+{
+ pattern_env_t env;
+ unsigned i;
+
+ if (! status->enable)
+ return;
+
+ /* do NOT count the const code IRG */
+ if (irg == get_const_code_irg())
+ return;
+
+ for (i = status->min_depth; i <= status->max_depth; ++i) {
+ env.max_depth = i;
+ irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
+ }
+}
+
+/*
+ * Initializes the pattern history.
+ */
+void stat_init_pattern_history(int enable)
+{
+ HASH_MAP(pattern_entry_t) *pattern_hash = NULL;
+
+ status->enable = enable;
+ if (! enable)
+ return;
+
+ status->bound = 10;
+ status->options = /* OPT_WITH_MODE | */ OPT_ENC_DAG | OPT_WITH_ICONST | OPT_PERSIST_PATTERN;
+ status->min_depth = 3;
+ status->max_depth = 5;
+
+ obstack_init(&status->obst);
+
+ /* create the hash-table */
+ if (status->options & OPT_PERSIST_PATTERN)
+ pattern_hash = read_pattern("pattern.fps");
+ if (pattern_hash == NULL)
+ pattern_hash = new_pset(pattern_cmp, 8);
+ status->pattern_hash = pattern_hash;
+}
+
+/*
+ * Finish the pattern history.
+ */
+void stat_finish_pattern_history(const char *fname)
+{
+ (void) fname;
+ if (! status->enable)
+ return;
+
+ store_pattern("pattern.fps");
+ pattern_output("pattern.vcg");
+
+ del_pset(status->pattern_hash);
+ obstack_free(&status->obst, NULL);
+
+ status->enable = 0;