*/
#include <assert.h>
#include <stdlib.h>
+#include <limits.h>
#include "ident.h"
#include "irnode_t.h"
#include "pset.h"
#include "counter.h"
#include "pattern_dmp.h"
+#include "hashptr.h"
/*
* just be make some things clear :-), the
* The code buffer
*/
typedef struct _code_buf_t {
- BYTE *next; /**< next byte to be written */
- BYTE *end; /**< end of the buffer */
- BYTE *start; /**< start of the buffer */
- unsigned hash; /**< calculates the hash value */
+ BYTE *next; /**< next byte to be written */
+ BYTE *end; /**< end of the buffer */
+ BYTE *start; /**< start of the buffer */
+ unsigned hash; /**< calculates the hash value */
} CODE_BUFFER;
/**
* VLC codes
*/
enum vlc_code_t {
- VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */
- VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */
- VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */
- VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */
- VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */
-
- VLC_TAG_FIRST = 0xF1, /**< first possible tag value */
- VLC_TAG_EMPTY = 0xFC, /**< encodes an empty entity */
- VLC_TAG_OPTION = 0xFD, /**< options exists */
- VLC_TAG_REF = 0xFE, /**< special tag, next code is an ID */
- VLC_TAG_END = 0xFF, /**< end tag */
+ VLC_7BIT = 0x00, /**< 8 bit code, carrying 7 bits payload */
+ VLC_14BIT = 0x80, /**< 16 bit code, carrying 14 bits payload */
+ VLC_21BIT = 0xC0, /**< 24 bit code, carrying 21 bits payload */
+ VLC_28BIT = 0xE0, /**< 32 bit code, carrying 28 bits payload */
+ VLC_32BIT = 0xF0, /**< 40 bit code, carrying 32 bits payload */
+
+ VLC_TAG_FIRST = 0xF1, /**< first possible tag value */
+ VLC_TAG_ICONST = 0xFB, /**< encodes an integer constant */
+ VLC_TAG_EMPTY = 0xFC, /**< encodes an empty entity */
+ VLC_TAG_OPTION = 0xFD, /**< options exists */
+ VLC_TAG_REF = 0xFE, /**< special tag, next code is an ID */
+ VLC_TAG_END = 0xFF, /**< end tag */
};
/*
- * An entry for patterns
+ * An entry for patterns.
*/
typedef struct _pattern_entry_t {
- counter_t count; /**< amount of pattern occurance */
- unsigned len; /**< lenght of the VLC encoded buffer */
- BYTE buf[1]; /**< buffer contains the VLC encoded pattern */
+ counter_t count; /**< amount of pattern occurance */
+ unsigned len; /**< length of the VLC encoded buffer */
+ BYTE buf[1]; /**< buffer contains the VLC encoded pattern */
} pattern_entry_t;
/**
* current options
*/
enum options_t {
- OPT_WITH_MODE = 0x00000001, /**< use modes */
- OPT_ENC_GRAPH = 0x00000002, /**< encode graphs, not terms */
+ OPT_WITH_MODE = 0x00000001, /**< use modes */
+ OPT_ENC_DAG = 0x00000002, /**< encode DAGs, not terms */
+ OPT_WITH_ICONST = 0x00000004, /**< encode integer constants */
};
* pattern info
*/
typedef struct _pattern_info_t {
- int enable; /**< if non-zero, this module is enabled */
- struct obstack obst; /**< obstack containing the counters */
- HASH_MAP(pattern_entry_t) *pattern_hash; /**< hash map containing the counter for pattern */
- unsigned bound; /**< lowest value for output */
- unsigned options; /**< option mask */
+ int enable; /**< if non-zero, this module is enabled */
+ struct obstack obst; /**< obstack containing the counters */
+ HASH_MAP(pattern_entry_t) *pattern_hash; /**< hash map containing the counter for pattern */
+ unsigned bound; /**< lowest value for output */
+ unsigned options; /**< option mask */
} pattern_info_t;
/*
static pattern_info_t _status, *status = &_status;
/**
- * compare two elemnts for counter
+ * compare two elements for counter
*/
static int pattern_count_cmp(const void *elt, const void *key)
{
pattern_entry_t **e1 = (pattern_entry_t **)elt;
pattern_entry_t **e2 = (pattern_entry_t **)key;
- cmp = cnt_cmp(&(*e1)->count, &(*e2)->count);
-
/* we want it sorted in descending order */
- return cmp * - 1;
+ cmp = cnt_cmp(&(*e2)->count, &(*e1)->count);
+
+ return cmp;
}
/**
}
/**
- * initialise a code buffer
+ * initialize a code buffer
*/
static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
{
/**
* put a byte into the buffer
*/
-static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte)
+static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte)
{
if (buf->next < buf->end) {
unsigned hash = buf->hash;
}
/**
- * returns the current lenght of a buffer
+ * returns the current length of a buffer
*/
static unsigned buf_lenght(const CODE_BUFFER *buf)
{
}
/**
- * returns the current lenght of a buffer
+ * returns the current content of a buffer
*/
static const BYTE *buf_content(const CODE_BUFFER *buf)
{
return VLC_TAG_END;
}
-#define BITS(n) (1 << (n))
+#define BITS(n) (1 << (n))
/**
* put a 32bit value into the buffer
}
}
-#define BIT_MASK(n) ((1 << (n)) - 1)
+#define BIT_MASK(n) ((1 << (n)) - 1)
/**
* get 32 bit from the buffer
* environment for the pattern encoder
*/
typedef struct _codec_enc_t {
- CODE_BUFFER *buf; /**< the code buffer */
- set *id_set; /**< the set containing all already seen nodes */
- unsigned curr_id; /**< current node id */
- unsigned options; /**< encoding options */
- pattern_dumper_t *dmp; /**< dumper for the decoder */
+ CODE_BUFFER *buf; /**< the code buffer */
+ set *id_set; /**< the set containing all already seen nodes */
+ unsigned curr_id; /**< current node id */
+ unsigned options; /**< encoding options */
+ pattern_dumper_t *dmp; /**< dumper for the decoder */
} codec_env_t;
typedef struct _addr_entry_t {
- void *addr; /**< the address */
- unsigned id; /**< associated ID */
+ void *addr; /**< the address */
+ unsigned id; /**< associated ID */
} addr_entry_t;
-/**
- * hash value of an address
- */
-static INLINE unsigned addr_hash(void *addr)
-{
- return ((unsigned)addr) >> 3;
-}
-
/**
* compare two addresses
*/
return e1->addr != e2->addr;
}
-/*
+/**
* encodes an IR-node, recursive worker
+ *
+ * @return reached depth
*/
-static void _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;
-#if 0
opcode code = get_irn_opcode(node);
-#else
- ir_op *code = get_irn_op(node);
-#endif
/* 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), addr_hash(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) {
put_tag(env->buf, VLC_TAG_REF);
put_code(env->buf, r_entry->id);
- return;
+ return max_depth;
}
else {
/* a new entry, proceed */
put_code(env->buf, (unsigned)code);
+ /* do we need the mode ? */
if (env->options & OPT_WITH_MODE) {
ir_mode *mode = get_irn_mode(node);
if (mode)
+ /* FIXME: not 64bit save */
put_code(env->buf, (unsigned)mode);
else
put_tag(env->buf, VLC_TAG_EMPTY);
}
+ /* do we need integer constants */
+ if (env->options & OPT_WITH_ICONST) {
+ if (code == iro_Const) {
+ 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);
+ }
+ }
+ }
+
--max_depth;
if (max_depth <= 0) {
put_code(env->buf, 0);
- return;
+ return max_depth;
}
preds = get_irn_arity(node);
put_code(env->buf, preds);
+ res = INT_MAX;
for (i = 0; i < preds; ++i) {
ir_node *n = get_irn_n(node, i);
- _encode_node(n, max_depth, env);
+ depth = _encode_node(n, max_depth, env);
+ if (depth < res)
+ res = depth;
}
+ return res;
}
/**
- * encode an IR-node
- */
-static void encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
+ * encode a DAG staring by the IR-node node
+ *
+ * @param node The root node of the graph
+ * @param buf The code buffer to store the bitstring in
+ * @param max_depth The maximum depth for descending
+ *
+ * @return The depth of the encoded graph (without cycles)
+ */
+static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
{
codec_env_t env;
+ int res;
env.buf = buf;
- env.curr_id = 1; /* 0 is used for special purpose */
+ env.curr_id = 1; /* 0 is used for special purpose */
env.options = status->options;
env.dmp = NULL;
- if (env.options & OPT_ENC_GRAPH)
+ if (env.options & OPT_ENC_DAG)
env.id_set = new_set(addr_cmp, 32);
else
env.id_set = NULL;
put_code(buf, env.options);
}
- _encode_node(node, max_depth, &env);
+ res = _encode_node(node, max_depth, &env);
- if (env.options & OPT_ENC_GRAPH)
+ if (env.options & OPT_ENC_DAG)
del_set(env.id_set);
+
+ return max_depth - res;
}
/**
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)
- pattern_dump_edge(env->dmp, code, parent, position);
+ 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 dont 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);
}
}
+ /* 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)
- pattern_dump_edge(env->dmp, env->curr_id, parent, position);
+ 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);
+ pattern_dump_node(env->dmp, parent, op_code, mode_code, attr);
/* ok, we have a new ID */
++env->curr_id;
/**
* decode an IR-node
*/
-static void decode_node(BYTE *b, unsigned len)
+static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump)
{
codec_env_t env;
CODE_BUFFER buf;
init_buf(&buf, b, len);
env.buf = &buf;
- env.curr_id = 1; /* 0 is used for special purpose */
- env.dmp = &stdout_dump;
+ env.curr_id = 1; /* 0 is used for special purpose */
+ env.dmp = dump;
/* decode options */
code = next_tag(&buf);
* the environment for the pattern calculation
*/
typedef struct _pattern_env {
- int max_depth; /**< maximum depth for pattern generation */
+ 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
*/
static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
{
}
cnt_clr(&key->count);
- assert(key != (void *)4);
return pset_insert(set, key, hash);
}
/**
- * walker for nodes pattern calculation
+ * count a pattern
+ */
+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)
{
BYTE buffer[1024];
pattern_env_t *env = ctx;
CODE_BUFFER buf;
- pattern_entry_t *entry;
+ int depth;
init_buf(&buf, buffer, sizeof(buffer));
- encode_node(node, &buf, env->max_depth);
+ depth = encode_node(node, &buf, env->max_depth);
- entry = pattern_get_entry(&buf, status->pattern_hash);
-
- /* increase count */
- cnt_inc(&entry->count);
+ count_pattern(&buf, depth);
}
/**
+ * output the collected pattern
*/
static void pattern_output(void)
{
- pattern_entry_t *entry;
- pattern_entry_t **pattern_arr;
+ pattern_entry_t *entry;
+ pattern_entry_t **pattern_arr;
+ pattern_dumper_t *dump;
int i, count = pset_count(status->pattern_hash);
printf("\n%d pattern detected\n", count);
if (count <= 0)
return;
+ /* creates a dumper */
+ dump = new_vcg_dumper("pattern.vcg", 100);
+
pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
for (i = 0, entry = pset_first(status->pattern_hash);
entry && i < count;
for (i = 0; i < count; ++i) {
entry = pattern_arr[i];
- if (entry->count.cnt[0] < status->bound)
+ if (cnt_to_uint(&entry->count) < status->bound)
continue;
- printf("%8d\t", entry->count.cnt[0]);
- decode_node(entry->buf, entry->len);
- printf("\n");
+ /* 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);
}
/*
if (irg == get_const_code_irg())
return;
- env.max_depth = 4;
+ env.max_depth = 5;
irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
}
/*
- * initialises the pattern history
+ * initializes the pattern history
*/
void stat_init_pattern_history(int enable)
{
if (! enable)
return;
- status->bound = 3;
- status->options = OPT_WITH_MODE | OPT_ENC_GRAPH;
+ status->bound = 10;
+ status->options = OPT_WITH_MODE | OPT_ENC_DAG | OPT_WITH_ICONST;
obstack_init(&status->obst);
projects / libfirm / blobdiff