X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fstat%2Fpattern.c;h=9f0a0110e1b8b68b0eb326e9d597d086b42e0214;hb=26b9008643da89a023fd6839ded5b9abf21ef328;hp=cde9a0295462855cc8d1a375a7aaad2d695720da;hpb=d723446b12363d2350eab855be3b61c27968ef5f;p=libfirm diff --git a/ir/stat/pattern.c b/ir/stat/pattern.c index cde9a0295..9f0a0110e 100644 --- a/ir/stat/pattern.c +++ b/ir/stat/pattern.c @@ -1,10 +1,34 @@ /* - * pattern history + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ + +/** + * @file + * @brief Statistics for Firm. Pattern history. + * @author Michael Beck + */ +#include "config.h" + #include #include #include +#include "pattern.h" #include "ident.h" #include "irnode_t.h" #include "irgwalk.h" @@ -14,6 +38,8 @@ #include "counter.h" #include "pattern_dmp.h" #include "hashptr.h" +#include "error.h" +#include "lc_printf.h" /* * just be make some things clear :-), the @@ -25,15 +51,19 @@ typedef pset pset_pattern_entry_t; typedef unsigned char BYTE; +/** Maximum size of the pattern store. */ +#define PATTERN_STORE_SIZE 2048 + /** * The code buffer. */ -typedef struct _code_buf_t { +typedef struct code_buf_t { BYTE *next; /**< Next byte address to be written. */ BYTE *end; /**< End address of the buffer. */ BYTE *start; /**< Start address of the buffer. */ unsigned hash; /**< The hash value for the buffer content. */ + unsigned overrun; /**< flag set if the buffer was overrun */ } CODE_BUFFER; /** @@ -57,9 +87,9 @@ enum vlc_code_t { /* * An entry for holding one pattern. */ -typedef struct _pattern_entry_t { +typedef struct pattern_entry_t { counter_t count; /**< Amount of pattern occurance. */ - unsigned len; /**< The length of the VLC encoded buffer. */ + size_t len; /**< The length of the VLC encoded buffer. */ BYTE buf[1]; /**< The buffer containing the VLC encoded pattern. */ } pattern_entry_t; @@ -70,19 +100,21 @@ enum options_t { OPT_WITH_MODE = 0x00000001, /**< use modes */ OPT_ENC_DAG = 0x00000002, /**< encode DAGs, not terms */ OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */ - OPT_PERSIST_PATTERN = 0x00000008, /**< persistant pattern hash */ + OPT_PERSIST_PATTERN = 0x00000008, /**< persistent pattern hash */ }; /** * Pattern info. */ -typedef struct _pattern_info_t { +typedef struct pattern_info_t { int enable; /**< If non-zero, this module is enabled. */ struct obstack obst; /**< An obstack containing the counters. */ HASH_MAP(pattern_entry_t) *pattern_hash; /**< A hash map containing the pattern. */ unsigned bound; /**< Lowest value for pattern output. */ unsigned options; /**< Current option mask. */ + unsigned min_depth; /**< Minimum pattern depth. */ + unsigned max_depth; /**< Maximum pattern depth. */ } pattern_info_t; /* @@ -111,14 +143,13 @@ static int pattern_count_cmp(const void *elt, const void *key) */ static int pattern_cmp(const void *elt, const void *key) { - const pattern_entry_t *e1 = elt; - const pattern_entry_t *e2 = key; - int diff = e1->len - e2->len; + const pattern_entry_t *e1 = (const pattern_entry_t*)elt; + const pattern_entry_t *e2 = (const pattern_entry_t*)key; - if (diff) - return diff; + if (e1->len == e2->len) + return memcmp(e1->buf, e2->buf, e1->len); - return memcmp(e1->buf, e2->buf, e1->len); + return e1->len < e2->len ? -1 : +1; } /* pattern_cmp */ /** @@ -128,11 +159,13 @@ static int pattern_cmp(const void *elt, const void *key) * @param data a buffer address * @param len the length of the data buffer */ -static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len) +static void init_buf(CODE_BUFFER *buf, BYTE *data, size_t len) { - buf->start = buf->next = data; - buf->end = data + len; - buf->hash = 0x2BAD4; /* An arbitrary seed. */ + buf->start = + buf->next = data; + buf->end = data + len; + buf->hash = 0x2BAD4; /* An arbitrary seed. */ + buf->overrun = 0; } /* init_buf */ /** @@ -143,15 +176,14 @@ static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len) * * The hash value for the buffer content is updated. */ -static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte) +static inline void put_byte(CODE_BUFFER *buf, BYTE byte) { if (buf->next < buf->end) { - unsigned hash = buf->hash; - - hash = (hash * 9) ^ byte; *buf->next++ = byte; - buf->hash = hash; - } /* if */ + buf->hash = (buf->hash * 9) ^ byte; + } else { + buf->overrun = 1; + } } /* put_byte */ /** @@ -161,7 +193,7 @@ static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte) * * @return the length of the buffer content */ -static unsigned buf_lenght(const CODE_BUFFER *buf) +static size_t buf_lenght(const CODE_BUFFER *buf) { return buf->next - buf->start; } /* buf_lenght */ @@ -190,6 +222,16 @@ static unsigned buf_hash(const CODE_BUFFER *buf) return buf->hash; } /* buf_hash */ +/** + * Returns non-zero if a buffer overrun has occurred. + * + * @param buf the code buffer + */ +static unsigned buf_overrun(const CODE_BUFFER *buf) +{ + return buf->overrun; +} /* buf_overrun */ + /** * Returns the next byte from the buffer WITHOUT dropping. * @@ -197,7 +239,7 @@ static unsigned buf_hash(const CODE_BUFFER *buf) * * @return the next byte from the code buffer */ -static INLINE BYTE look_byte(CODE_BUFFER *buf) +static inline BYTE look_byte(CODE_BUFFER *buf) { if (buf->next < buf->end) return *buf->next; @@ -211,7 +253,7 @@ static INLINE BYTE look_byte(CODE_BUFFER *buf) * * @return the next byte from the code buffer */ -static INLINE BYTE get_byte(CODE_BUFFER *buf) +static inline BYTE get_byte(CODE_BUFFER *buf) { if (buf->next < buf->end) return *buf->next++; @@ -287,9 +329,7 @@ static unsigned get_code(CODE_BUFFER *buf) return code; } /* if */ /* should not happen */ - assert(0 && "Wrong code in buffer"); - - return 0; + panic("Wrong code in buffer"); } /* get_code */ /** @@ -324,7 +364,7 @@ static BYTE next_tag(CODE_BUFFER *buf) /** * An Environment for the pattern encoder. */ -typedef struct _codec_enc_t { +typedef struct codec_enc_t { CODE_BUFFER *buf; /**< The current code buffer. */ set *id_set; /**< A set containing all already seen Firm nodes. */ unsigned curr_id; /**< The current node id. */ @@ -335,7 +375,7 @@ typedef struct _codec_enc_t { /** * An address entry. */ -typedef struct _addr_entry_t { +typedef struct addr_entry_t { void *addr; /**< the address */ unsigned id; /**< associated ID */ } addr_entry_t; @@ -343,13 +383,31 @@ typedef struct _addr_entry_t { /** * Compare two addresses. */ -static int addr_cmp(const void *p1, const void *p2, size_t size) { - const addr_entry_t *e1 = p1; - const addr_entry_t *e2 = p2; +static int addr_cmp(const void *p1, const void *p2, size_t size) +{ + const addr_entry_t *e1 = (const addr_entry_t*)p1; + const addr_entry_t *e2 = (const addr_entry_t*)p2; + (void) size; return e1->addr != e2->addr; } /* addr_cmp */ +/** + * Return the index of a (existing) mode. + */ +static size_t find_mode_index(const ir_mode *mode) +{ + size_t i, n = ir_get_n_modes(); + + for (i = 0; i < n; ++i) { + if (ir_get_mode(i) == mode) + return i; + } + /* should really not happen */ + assert(!"Cound not find index of mode in find_mode_index()"); + return (size_t)-1; +} + /** * Encodes an IR-node, recursive worker. * @@ -362,13 +420,13 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) int i, preds; int res, depth; - opcode code = get_irn_opcode(node); + unsigned code = get_irn_opcode(node); /* insert the node into our ID map */ entry.addr = node; entry.id = env->curr_id; - s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), HASH_PTR(node)); + s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), hash_ptr(node)); r_entry = (addr_entry_t *)s_entry->dptr; if (r_entry->id != env->curr_id) { @@ -389,8 +447,7 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) ir_mode *mode = get_irn_mode(node); if (mode) - /* FIXME: not 64bit save */ - put_code(env->buf, (unsigned)mode); + put_code(env->buf, find_mode_index(mode)); else put_tag(env->buf, VLC_TAG_EMPTY); } /* if */ @@ -398,7 +455,7 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) /* do we need integer constants */ if (env->options & OPT_WITH_ICONST) { if (code == iro_Const) { - tarval *tv = get_Const_tarval(node); + ir_tarval *tv = get_Const_tarval(node); if (tarval_is_long(tv)) { long v = get_tarval_long(tv); @@ -420,18 +477,41 @@ static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) put_code(env->buf, preds); res = INT_MAX; - for (i = 0; i < preds; ++i) { - ir_node *n = get_irn_n(node, i); + if (is_op_commutative(get_irn_op(node))) { + ir_node *l = get_binop_left(node); + ir_node *r = get_binop_right(node); + int opcode_diff = (int)get_irn_opcode(l) - (int)get_irn_opcode(r); + + if (opcode_diff > 0) { + ir_node *t = l; + l = r; + r = t; + } else if (opcode_diff == 0 && l != r) { + /* Both nodes have the same opcode, but are different. + Need a better method here to decide which goes to the left side. */ + } /* if */ - depth = _encode_node(n, max_depth, env); + /* special handling for commutative operators */ + depth = _encode_node(l, max_depth, env); if (depth < res) res = depth; - } /* for */ + depth = _encode_node(r, max_depth, env); + if (depth < res) + res = depth; + } else { + for (i = 0; i < preds; ++i) { + ir_node *n = get_irn_n(node, i); + + depth = _encode_node(n, max_depth, env); + if (depth < res) + res = depth; + } /* for */ + } /* if */ return res; } /* _encode_node */ /** - * Encode a DAG staring by the IR-node node. + * Encode a DAG starting by the IR-node node. * * @param node The root node of the graph * @param buf The code buffer to store the bitstring in @@ -490,7 +570,7 @@ static void _decode_node(unsigned parent, int position, codec_env_t *env) /* * 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 dont know the target here, it's a ref. + * we don't know the target here, it's a ref. */ pattern_dump_edge(env->dmp, code, parent, position, edge_mode); } /* if */ @@ -555,7 +635,7 @@ static void _decode_node(unsigned parent, int position, codec_env_t *env) /** * Decode an IR-node. */ -static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) +static void decode_node(BYTE *b, size_t len, pattern_dumper_t *dump) { codec_env_t env; CODE_BUFFER buf; @@ -580,7 +660,7 @@ static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) /** * The environment for the pattern calculation. */ -typedef struct _pattern_env { +typedef struct pattern_env { int max_depth; /**< maximum depth for pattern generation. */ } pattern_env_t; @@ -598,25 +678,23 @@ typedef struct _pattern_env { static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) { pattern_entry_t *key, *elem; - unsigned len = buf_lenght(buf); + size_t len = buf_lenght(buf); unsigned hash; - key = obstack_alloc(&status->obst, sizeof(*key) + len - 1); - assert(key); - + key = OALLOCF(&status->obst, pattern_entry_t, buf, len); key->len = len; memcpy(key->buf, buf_content(buf), len); hash = buf_hash(buf); - elem = pset_find(set, key, hash); + elem = (pattern_entry_t*)pset_find(set, key, hash); if (elem != NULL) { obstack_free(&status->obst, key); return elem; } /* if */ cnt_clr(&key->count); - return pset_insert(set, key, hash); + return (pattern_entry_t*)pset_insert(set, key, hash); } /* pattern_get_entry */ /** @@ -627,7 +705,8 @@ static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) * * @note Single node patterns are ignored */ -static void count_pattern(CODE_BUFFER *buf, int depth) { +static void count_pattern(CODE_BUFFER *buf, int depth) +{ pattern_entry_t *entry; /* ignore single node pattern (i.e. constants) */ @@ -644,15 +723,18 @@ static void count_pattern(CODE_BUFFER *buf, int depth) { */ static void calc_nodes_pattern(ir_node *node, void *ctx) { - BYTE buffer[1024]; - pattern_env_t *env = 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); - count_pattern(&buf, 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); } /* calc_nodes_pattern */ /** @@ -664,7 +746,7 @@ static void store_pattern(const char *fname) { FILE *f; pattern_entry_t *entry; - int i, count = pset_count(status->pattern_hash); + size_t count = pset_count(status->pattern_hash); if (count <= 0) return; @@ -678,12 +760,9 @@ static void store_pattern(const char *fname) fwrite("FPS1", 4, 1, f); fwrite(&count, sizeof(count), 1, f); - for (i = 0, entry = pset_first(status->pattern_hash); - entry && i < count; - entry = pset_next(status->pattern_hash), ++i) { + foreach_pset(status->pattern_hash, pattern_entry_t*, entry) { fwrite(entry, offsetof(pattern_entry_t, buf) + entry->len, 1, f); } /* for */ - fclose(f); } /* store_pattern */ @@ -696,12 +775,13 @@ static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname) { FILE *f; pattern_entry_t *entry, tmp; - int i, count; + size_t i, count; unsigned j; char magic[4]; HASH_MAP(pattern_entry_t) *pattern_hash = new_pset(pattern_cmp, 8); - BYTE buffer[1024]; + BYTE buffer[PATTERN_STORE_SIZE]; CODE_BUFFER buf; + int res; f = fopen(fname, "rb"); if (! f) { @@ -709,31 +789,36 @@ static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname) return NULL; } /* if */ - fread(magic, 4, 1, f); + res = fread(magic, 4, 1, f); + if (res != 1) + goto read_error; count = 0; - fread(&count, sizeof(count), 1, f); - if (memcmp(magic, "FPS1", 4) != 0 || count <= 0) { - fprintf(stderr, "Error: %s is not a Firm pattern store. Ignored.\n", fname); - fclose(f); - return NULL; - } /* if */ - + 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)); - fread(&tmp, offsetof(pattern_entry_t, buf), 1, f); + 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); - memcpy(&entry->count, &tmp.count, sizeof(entry->count)); + entry->count = tmp.count; } /* for */ - fclose(f); - printf("Read %d pattern from %s\n", pset_count(pattern_hash), fname); + 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; } /* read_pattern */ /** @@ -746,21 +831,20 @@ static void pattern_output(const char *fname) pattern_entry_t *entry; pattern_entry_t **pattern_arr; pattern_dumper_t *dump; - int i, count = pset_count(status->pattern_hash); + size_t i, count = pset_count(status->pattern_hash); - printf("\n%d pattern detected\n", count); + lc_printf("\n%zu pattern detected\n", count); - if (count <= 0) + if (count == 0) return; /* creates a dumper */ dump = new_vcg_dumper(fname, 100); - pattern_arr = xmalloc(sizeof(*pattern_arr) * count); - for (i = 0, entry = pset_first(status->pattern_hash); - entry && i < count; - entry = pset_next(status->pattern_hash), ++i) { - pattern_arr[i] = entry; + pattern_arr = XMALLOCN(pattern_entry_t*, count); + i = 0; + foreach_pset(status->pattern_hash, pattern_entry_t*, entry) { + pattern_arr[i++] = entry; } /* for */ assert(count == i); count = i; @@ -789,6 +873,7 @@ static void pattern_output(const char *fname) void stat_calc_pattern_history(ir_graph *irg) { pattern_env_t env; + unsigned i; if (! status->enable) return; @@ -797,8 +882,10 @@ void stat_calc_pattern_history(ir_graph *irg) if (irg == get_const_code_irg()) return; - env.max_depth = 5; - irg_walk_graph(irg, calc_nodes_pattern, NULL, &env); + for (i = status->min_depth; i <= status->max_depth; ++i) { + env.max_depth = i; + irg_walk_graph(irg, calc_nodes_pattern, NULL, &env); + } /* for */ } /* stat_calc_pattern_history */ /* @@ -812,8 +899,10 @@ void stat_init_pattern_history(int enable) if (! enable) return; - status->bound = 10; - status->options = /* OPT_WITH_MODE | */ OPT_ENC_DAG | OPT_WITH_ICONST | OPT_PERSIST_PATTERN; + 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); @@ -828,8 +917,9 @@ void stat_init_pattern_history(int enable) /* * Finish the pattern history. */ -void stat_finish_pattern_history(void) +void stat_finish_pattern_history(const char *fname) { + (void) fname; if (! status->enable) return;