/*
- * Copyright (C) 1995-2007 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.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
* @file
* @brief Statistics for Firm. Pattern history.
* @author Michael Beck
- * @version $Id$
*/
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
+#include "pattern.h"
#include "ident.h"
#include "irnode_t.h"
#include "irgwalk.h"
#include "counter.h"
#include "pattern_dmp.h"
#include "hashptr.h"
-
-#ifdef FIRM_STATISTICS
+#include "error.h"
+#include "lc_printf.h"
/*
* just be make some things clear :-), the
typedef unsigned char BYTE;
/** Maximum size of the pattern store. */
-#define PATTERN_STORE_SIZE 2048
+#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. */
/*
* 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;
/**
* 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. */
/**
* 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;
cmp = cnt_cmp(&(*e2)->count, &(*e1)->count);
return cmp;
-} /* pattern_count_cmp */
+}
/**
* Compare two pattern for its pattern hash.
*/
-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;
+static int pattern_cmp(const void *elt, const void *key)
+{
+ 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);
-} /* pattern_cmp */
+ return e1->len < e2->len ? -1 : +1;
+}
/**
* Initialize a code buffer.
* @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->overrun = 0;
-} /* init_buf */
+}
/**
* Put a byte into the buffer.
*
* The hash value for the buffer content is updated.
*/
-static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte) {
+static inline void put_byte(CODE_BUFFER *buf, BYTE byte)
+{
if (buf->next < buf->end) {
*buf->next++ = byte;
buf->hash = (buf->hash * 9) ^ byte;
} else {
buf->overrun = 1;
- } /* if */
-} /* put_byte */
+ }
+}
/**
* Returns the current length of a buffer.
*
* @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 */
+}
/**
* Returns the current content of a buffer.
*
* @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 */
+}
/**
* Returns the hash value of a buffer.
*
* @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) {
+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;
-} /* look_byte */
+}
/**
* Returns the next byte from the buffer WITH dropping.
*
* @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;
-} /* get_byte */
+}
#define BITS(n) (1 << (n))
* @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)) {
put_byte(buf, code >> 16);
put_byte(buf, code >> 8);
put_byte(buf, code);
- } /* if */
-} /* put_code */
+ }
+}
#define BIT_MASK(n) ((1 << (n)) - 1)
*
* @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)
code = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
code |= get_byte(buf);
return code;
- } /* if */
+ }
if (code < VLC_32BIT) {
code = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
code |= get_byte(buf) << 8;
code |= get_byte(buf);
return code;
- } /* if */
+ }
if (code == VLC_32BIT) {
code = get_byte(buf) << 24;
code |= get_byte(buf) << 16;
code |= get_byte(buf) << 8;
code |= get_byte(buf);
return code;
- } /* if */
+ }
/* should not happen */
- assert(0 && "Wrong code in buffer");
-
- return 0;
-} /* get_code */
+ panic("Wrong code in buffer");
+}
/**
* Put a tag into the buffer.
* @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);
-} /* put_tag */
+}
/**
* Returns the next tag or zero if the next code isn't a 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)
return get_byte(buf);
return 0;
-} /* next_tag */
+}
/**
* 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. */
/**
* An address entry.
*/
-typedef struct _addr_entry_t {
+typedef struct addr_entry_t {
void *addr; /**< the address */
unsigned id; /**< associated ID */
} 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.
*
* @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;
- ir_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) {
} else {
/* a new entry, proceed */
++env->curr_id;
- } /* if */
+ }
put_code(env->buf, (unsigned)code);
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 */
+ }
/* 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);
put_tag(env->buf, VLC_TAG_ICONST);
put_code(env->buf, v);
- } /* if */
- } /* if */
- } /* if */
+ }
+ }
+ }
--max_depth;
if (max_depth <= 0) {
put_code(env->buf, 0);
return max_depth;
- } /* if */
+ }
preds = get_irn_arity(node);
put_code(env->buf, preds);
} 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 */
+ }
/* special handling for commutative operators */
depth = _encode_node(l, max_depth, env);
depth = _encode_node(n, max_depth, env);
if (depth < res)
res = depth;
- } /* for */
- } /* if */
+ }
+ }
return res;
-} /* _encode_node */
+}
/**
* Encode a DAG starting by the IR-node node.
*
* @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;
if (env.options) {
put_tag(buf, VLC_TAG_OPTION);
put_code(buf, env.options);
- } /* if */
+ }
res = _encode_node(node, max_depth, &env);
del_set(env.id_set);
return max_depth - res;
-} /* encode_node */
+}
/**
* 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;
* we don't know the target here, it's a ref.
*/
pattern_dump_edge(env->dmp, code, parent, position, edge_mode);
- } /* if */
+ }
/* dump the node ref */
pattern_dump_ref(env->dmp, code);
return;
- } /* if */
+ }
/* get the opcode */
op_code = get_code(env->buf);
if (env->options & OPT_WITH_MODE) {
if (next_tag(env->buf) != VLC_TAG_EMPTY) {
mode_code = get_code(env->buf);
- } /* if */
- } /* if */
+ }
+ }
/* check, if a ICONST attribute is given */
if (next_tag(env->buf) == VLC_TAG_ICONST) {
iconst = get_code(env->buf);
attr = &iconst;
- } /* if */
+ }
/* dump the edge */
if (parent) {
* we need it anyway for ref's.
*/
pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode);
- } /* if */
+ }
/* dump the node */
parent = env->curr_id;
pattern_start_children(env->dmp, parent);
for (i = 0; i < preds; ++i) {
_decode_node(parent, i, env);
- } /* for */
+ }
pattern_finish_children(env->dmp, parent);
- } /* if */
- } /* if */
-} /* _decode_node */
+ }
+ }
+}
/**
* 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;
unsigned code, options = 0;
code = next_tag(&buf);
if (code == VLC_TAG_OPTION) {
options = get_code(&buf);
- } /* if */
+ }
env.options = options;
_decode_node(0, 0, &env);
-} /* decode_node */
+}
/**
* 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;
* 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);
+ size_t len = buf_lenght(buf);
unsigned hash;
- key = obstack_alloc(&status->obst, offsetof(pattern_entry_t, buf) + len);
- 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);
-} /* pattern_get_entry */
+ return (pattern_entry_t*)pset_insert(set, key, hash);
+}
/**
* Increase the count for a pattern.
*
* @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) */
/* increase count */
cnt_inc(&entry->count);
- } /* if */
-} /* count_pattern */
+ }
+}
/**
* Pre-walker for nodes pattern calculation.
*/
-static void calc_nodes_pattern(ir_node *node, void *ctx) {
- pattern_env_t *env = ctx;
+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;
depth = encode_node(node, &buf, env->max_depth);
if (buf_overrun(&buf)) {
- fprintf(stderr, "Pattern store: buffer overrun at size %d. Pattern ignored.\n", sizeof(buffer));
+ lc_fprintf(stderr, "Pattern store: buffer overrun at size %zu. Pattern ignored.\n", sizeof(buffer));
} else
count_pattern(&buf, depth);
-} /* calc_nodes_pattern */
+}
/**
* Store all collected patterns.
*
* @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);
+ size_t count = pset_count(status->pattern_hash);
if (count <= 0)
return;
if (! f) {
perror(fname);
return;
- } /* if */
+ }
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 */
+}
/**
* Read collected patterns from a file.
*
* @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;
+ 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;
- } /* 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));
- } /* for */
+ entry->count = tmp.count;
+ }
fclose(f);
- printf("Read %d pattern from %s\n", count, fname);
+ lc_printf("Read %zu pattern from %s\n", count, fname);
assert(pset_count(pattern_hash) == count);
return pattern_hash;
-} /* read_pattern */
+
+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 *entry;
+static void pattern_output(const char *fname)
+{
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;
- } /* for */
+ 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;
qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
for (i = 0; i < count; ++i) {
- entry = pattern_arr[i];
+ pattern_entry_t *const entry = pattern_arr[i];
if (cnt_to_uint(&entry->count) < status->bound)
continue;
pattern_dump_new_pattern(dump, &entry->count);
decode_node(entry->buf, entry->len, dump);
pattern_dump_finish_pattern(dump);
- } /* for */
+ }
/* destroy it */
pattern_end(dump);
-} /* pattern_output */
+}
/*
* 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;
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 (pattern_hash == NULL)
pattern_hash = new_pset(pattern_cmp, 8);
status->pattern_hash = pattern_hash;
-} /* stat_init_pattern_history */
+}
/*
* Finish the pattern history.
*/
-void stat_finish_pattern_history(const char *fname) {
+void stat_finish_pattern_history(const char *fname)
+{
(void) fname;
if (! status->enable)
return;
obstack_free(&status->obst, NULL);
status->enable = 0;
-} /* stat_finish_pattern_history */
-
-#endif /* FIRM_STATISTICS */
+}
projects / libfirm / blobdiff