/*
- * pattern history
+ * Copyright (C) 1995-2008 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
+ * @version $Id$
+ */
+#include "config.h"
+
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include "pattern_dmp.h"
#include "hashptr.h"
+#ifdef FIRM_STATISTICS
+
/*
* just be make some things clear :-), the
* poor man "generics"
typedef unsigned char BYTE;
+/** Maximum size of the pattern store. */
+#define PATTERN_STORE_SIZE 2048
+
/**
* The code buffer.
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;
/**
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 */
};
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;
/*
/**
* Compare two pattern for its occurance counter.
*/
-static int pattern_count_cmp(const void *elt, const void *key)
-{
+static int pattern_count_cmp(const void *elt, const void *key) {
int cmp;
pattern_entry_t **e1 = (pattern_entry_t **)elt;
/**
* Compare two pattern for its pattern hash.
*/
-static int pattern_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;
* @param data a buffer address
* @param len the length of the data buffer
*/
-static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
-{
- buf->start = buf->next = data;
- buf->end = data + len;
- buf->hash = 0x2BAD4; /* An arbitrary seed. */
+static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len) {
+ buf->start =
+ buf->next = data;
+ buf->end = data + len;
+ buf->hash = 0x2BAD4; /* An arbitrary seed. */
+ buf->overrun = 0;
} /* init_buf */
/**
*
* 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;
+ buf->hash = (buf->hash * 9) ^ byte;
+ } else {
+ buf->overrun = 1;
} /* if */
} /* put_byte */
*
* @return the length of the buffer content
*/
-static unsigned buf_lenght(const CODE_BUFFER *buf)
-{
+static unsigned buf_lenght(const CODE_BUFFER *buf) {
return buf->next - buf->start;
} /* buf_lenght */
*
* @return the start address of the buffer content
*/
-static const BYTE *buf_content(const CODE_BUFFER *buf)
-{
+static const BYTE *buf_content(const CODE_BUFFER *buf) {
return buf->start;
} /* buf_content */
*
* @return the hash value of the buffer content
*/
-static unsigned buf_hash(const CODE_BUFFER *buf)
-{
+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.
*
*
* @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;
return VLC_TAG_END;
*
* @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++;
return VLC_TAG_END;
* @param buf the code buffer
* @param code the code to be written into the buffer
*/
-static void put_code(CODE_BUFFER *buf, unsigned code)
-{
+static void put_code(CODE_BUFFER *buf, unsigned code) {
if (code < BITS(7)) {
put_byte(buf, VLC_7BIT | code);
} else if (code < BITS(6 + 8)) {
*
* @return next 32bit value from the code buffer
*/
-static unsigned get_code(CODE_BUFFER *buf)
-{
+static unsigned get_code(CODE_BUFFER *buf) {
unsigned code = get_byte(buf);
if (code < VLC_14BIT)
* @param buf the code buffer
* @param tag the tag to write to the code buffer
*/
-static void put_tag(CODE_BUFFER *buf, BYTE tag)
-{
+static void put_tag(CODE_BUFFER *buf, BYTE tag) {
assert(tag >= VLC_TAG_FIRST && "invalid tag");
put_byte(buf, tag);
*
* @return the next tag in the code buffer
*/
-static BYTE next_tag(CODE_BUFFER *buf)
-{
+static BYTE next_tag(CODE_BUFFER *buf) {
BYTE b = look_byte(buf);
if (b >= VLC_TAG_FIRST)
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;
+ (void) size;
return e1->addr != e2->addr;
} /* addr_cmp */
*
* @return reached depth
*/
-static int _encode_node(ir_node *node, int max_depth, codec_env_t *env)
-{
+static int _encode_node(ir_node *node, int max_depth, codec_env_t *env) {
addr_entry_t entry, *r_entry;
set_entry *s_entry;
int i, preds;
int res, depth;
- opcode code = get_irn_opcode(node);
+ ir_opcode code = get_irn_opcode(node);
/* insert the node into our ID map */
entry.addr = node;
ir_mode *mode = get_irn_mode(node);
if (mode)
- /* FIXME: not 64bit save */
- put_code(env->buf, (unsigned)mode);
+ put_code(env->buf, stat_find_mode_index(mode));
else
put_tag(env->buf, VLC_TAG_EMPTY);
} /* if */
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
*
* @return The depth of the encoded graph (without cycles)
*/
-static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
-{
+static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth) {
codec_env_t env;
int res;
/**
* Decode an IR-node, recursive walker.
*/
-static void _decode_node(unsigned parent, int position, codec_env_t *env)
-{
+static void _decode_node(unsigned parent, int position, codec_env_t *env) {
unsigned code;
unsigned op_code;
unsigned mode_code = 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 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 */
/**
* Decode an IR-node.
*/
-static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump)
-{
+static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump) {
codec_env_t env;
CODE_BUFFER buf;
unsigned code, options = 0;
* 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)
-{
+static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set) {
pattern_entry_t *key, *elem;
unsigned 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);
/**
* Pre-walker for nodes pattern calculation.
*/
-static void calc_nodes_pattern(ir_node *node, void *ctx)
-{
- BYTE buffer[1024];
+static void calc_nodes_pattern(ir_node *node, void *ctx) {
pattern_env_t *env = 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)) {
+ fprintf(stderr, "Pattern store: buffer overrun at size %u. Pattern ignored.\n", (unsigned) sizeof(buffer));
+ } else
+ count_pattern(&buf, depth);
} /* calc_nodes_pattern */
/**
*
* @param fname filename for storage
*/
-static void store_pattern(const char *fname)
-{
+static void store_pattern(const char *fname) {
FILE *f;
pattern_entry_t *entry;
int i, count = pset_count(status->pattern_hash);
entry = pset_next(status->pattern_hash), ++i) {
fwrite(entry, offsetof(pattern_entry_t, buf) + entry->len, 1, f);
} /* for */
-
fclose(f);
} /* store_pattern */
*
* @param fname filename
*/
-static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname)
-{
+static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname) {
FILE *f;
pattern_entry_t *entry, tmp;
int 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;
f = fopen(fname, "rb");
return NULL;
} /* if */
-
/* read all pattern entries and put them into the hash table. */
for (i = 0; i < count; ++i) {
init_buf(&buf, buffer, sizeof(buffer));
entry = pattern_get_entry(&buf, pattern_hash);
memcpy(&entry->count, &tmp.count, sizeof(entry->count));
} /* for */
-
fclose(f);
- printf("Read %d pattern from %s\n", pset_count(pattern_hash), fname);
+ printf("Read %d pattern from %s\n", count, fname);
+ assert(pset_count(pattern_hash) == count);
return pattern_hash;
} /* read_pattern */
*
* @param fname name of the VCG file to create
*/
-static void pattern_output(const char *fname)
-{
+static void pattern_output(const char *fname) {
pattern_entry_t *entry;
pattern_entry_t **pattern_arr;
pattern_dumper_t *dump;
/* creates a dumper */
dump = new_vcg_dumper(fname, 100);
- pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
+ pattern_arr = XMALLOCN(pattern_entry_t*, count);
for (i = 0, entry = pset_first(status->pattern_hash);
entry && i < count;
entry = pset_next(status->pattern_hash), ++i) {
/*
* Calculates the pattern history.
*/
-void stat_calc_pattern_history(ir_graph *irg)
-{
+void stat_calc_pattern_history(ir_graph *irg) {
pattern_env_t env;
+ unsigned i;
if (! status->enable)
return;
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 */
/*
* Initializes the pattern history.
*/
-void stat_init_pattern_history(int enable)
-{
+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->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);
/*
* Finish the pattern history.
*/
-void stat_finish_pattern_history(void)
-{
+void stat_finish_pattern_history(const char *fname) {
+ (void) fname;
if (! status->enable)
return;
status->enable = 0;
} /* stat_finish_pattern_history */
+
+#endif /* FIRM_STATISTICS */
projects / libfirm / blobdiff