+/**
+ * Put a 32bit value into the buffer.
+ *
+ * @param buf the code buffer
+ * @param code the code to be written into the buffer
+ */
+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, VLC_14BIT | (code >> 8));
+ put_byte(buf, code);
+ } else if (code < BITS(5 + 8 + 8)) {
+ put_byte(buf, VLC_21BIT | (code >> 16));
+ put_byte(buf, code >> 8);
+ put_byte(buf, code);
+ } else if (code < BITS(4 + 8 + 8 + 8)) {
+ put_byte(buf, VLC_28BIT | (code >> 24));
+ put_byte(buf, code >> 16);
+ put_byte(buf, code >> 8);
+ put_byte(buf, code);
+ } else {
+ put_byte(buf, VLC_32BIT);
+ put_byte(buf, code >> 24);
+ put_byte(buf, code >> 16);
+ put_byte(buf, code >> 8);
+ put_byte(buf, code);
+ } /* if */
+} /* put_code */
+
+#define BIT_MASK(n) ((1 << (n)) - 1)
+
+/**
+ * Get 32 bit from the buffer.
+ *
+ * @param buf the code buffer
+ *
+ * @return next 32bit value from the code buffer
+ */
+static unsigned get_code(CODE_BUFFER *buf) {
+ unsigned code = get_byte(buf);
+
+ if (code < VLC_14BIT)
+ return code;
+ if (code < VLC_21BIT)
+ return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
+ if (code < VLC_28BIT) {
+ 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 */
+
+/**
+ * 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) {
+ 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.
+ *
+ * @param buf the code buffer
+ *
+ * @return the next tag in the code buffer
+ */
+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 {
+ 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. */
+ unsigned options; /**< The encoding options. */
+ pattern_dumper_t *dmp; /**< The dumper for the decoder. */
+} codec_env_t;
+
+/**
+ * An address entry.
+ */
+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;
+
+ return e1->addr != e2->addr;
+} /* addr_cmp */
+
+/**
+ * Encodes an IR-node, recursive worker.
+ *
+ * @return reached depth
+ */
+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);
+
+ /* 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));
+ r_entry = (addr_entry_t *)s_entry->dptr;
+
+ if (r_entry->id != env->curr_id) {
+ /* already in the map, add an REF */
+ put_tag(env->buf, VLC_TAG_REF);
+ put_code(env->buf, r_entry->id);
+
+ return max_depth;
+ } else {
+ /* a new entry, proceed */
+ ++env->curr_id;
+ } /* if */
+
+ 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);
+ } /* if */
+
+ /* 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);
+ } /* 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);
+
+ res = INT_MAX;
+ 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 */
+
+ /* special handling for commutative operators */
+ depth = _encode_node(l, max_depth, env);
+ if (depth < res)
+ res = depth;
+ 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 starting 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;
+
+ /* initialize the encoder environment */
+ env.buf = buf;
+ env.curr_id = 1; /* 0 is used for special purpose */
+ env.options = status->options;
+ env.dmp = NULL;
+
+ if (env.options & OPT_ENC_DAG)
+ env.id_set = new_set(addr_cmp, 32);
+ else
+ env.id_set = NULL;
+
+ /* encode options if any for the decoder */
+ if (env.options) {
+ put_tag(buf, VLC_TAG_OPTION);
+ put_code(buf, env.options);
+ } /* if */
+
+ res = _encode_node(node, max_depth, &env);
+
+ if (env.id_set != NULL)
+ 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) {
+ 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);
+ } /* if */
+
+ /* dump the node ref */
+ pattern_dump_ref(env->dmp, code);
+
+ return;
+ } /* if */
+
+ /* 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);
+ } /* 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) {
+ 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);
+ } /* if */
+
+ /* 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);
+ } /* 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) {
+ 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);
+ } /* if */
+ env.options = options;
+
+ _decode_node(0, 0, &env);
+} /* decode_node */
+
+/**
+ * The environment for the pattern calculation.