nsz Git - libfirm/blob - ir/stat/pattern.c

   1 /*
   2  * pattern history
   3  */
   4 #include <assert.h>
   5
   6 #include "irnode_t.h"
   7
   8 typedef unsigned char BYTE;
   9
  10 /**
  11  * The code buffer
  12  */
  13 typedef struct _code_buf_t {
  14   BYTE          *next;          /**< next byte to be written */
  15   int           len;            /**< length of current string */
  16 } CODE_BUFFER;
  17
  18 enum vlc_code_t {
  19   VLC_7BIT      = 0x00, /**< 8 bit code, carrying 7 bits payload */
  20   VLC_14BIT     = 0x80, /**< 16 bit code, carrying 14 bits payload */
  21   VLC_21BIT     = 0xC0, /**< 24 bit code, carrying 21 bits payload */
  22   VLC_28BIT     = 0xE0, /**< 32 bit code, carrying 28 bits payload */
  23   VLC_32BIT     = 0xF0, /**< 40 bit code, carrying 32 bits payload */
  24
  25   VLC_TAG_FIRST = 0xF1, /**< first possible tag value */
  26   VLC_TAG_REF   = 0xFE, /**< special tag, next code is an ID */
  27   VLC_TAG_END   = 0xFF, /**< end tag */
  28 };
  29
  30 /**
  31  * put a byte into the buffer
  32  */
  33 static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte)
  34 {
  35   *buf->next++ = byte;
  36   ++buf->len;
  37 }
  38
  39 /**
  40  * returns the next byte from the buffer WITHOUT dropping
  41  */
  42 static INLINE BYTE look_byte(CODE_BUFFER *buf)
  43 {
  44   return *buf->next;
  45 }
  46
  47 /**
  48  * returns the next byte from the buffer WITH dropping
  49  */
  50 static INLINE BYTE get_byte(CODE_BUFFER *buf)
  51 {
  52   return *buf->next++;
  53 }
  54
  55 #define BITS(n)         (1 << (n))
  56
  57 /**
  58  * put a 32bit value into the buffer
  59  */
  60 static void put_code(CODE_BUFFER *buf, unsigned code)
  61 {
  62   if (code < BITS(7)) {
  63     put_byte(buf, VLC_7BIT | code);
  64   }
  65   else if (code < BITS(6 + 8)) {
  66     put_byte(buf, VLC_14BIT | (code >> 8));
  67     put_byte(buf, code);
  68   }
  69   else if (code < BITS(5 + 8 + 8)) {
  70     put_byte(buf, VLC_21BIT | (code >> 16));
  71     put_byte(buf, code >> 8);
  72     put_byte(buf, code);
  73   }
  74   else if (code < BITS(4 + 8 + 8 + 8)) {
  75     put_byte(buf, VLC_28BIT | (code >> 24));
  76     put_byte(buf, code >> 16);
  77     put_byte(buf, code >> 8);
  78     put_byte(buf, code);
  79   }
  80   else {
  81     put_byte(buf, VLC_32BIT);
  82     put_byte(buf, code >> 24);
  83     put_byte(buf, code >> 16);
  84     put_byte(buf, code >> 8);
  85     put_byte(buf, code);
  86   }
  87 }
  88
  89 /**
  90  * put a tag into the buffer
  91  */
  92 static void put_tag(CODE_BUFFER *buf, BYTE tag)
  93 {
  94   assert(tag >= VLC_TAG_FIRST && "invalid tag");
  95
  96   put_byte(buf, tag);
  97 }
  98
  99 /**
 100  * returns the next tag or zero if the next code isn't a tag
 101  */
 102 static BYTE next_tag(CODE_BUFFER *buf)
 103 {
 104   BYTE b = look_byte(buf);
 105
 106   if (b >= VLC_TAG_FIRST)
 107     return b;
 108   return 0;
 109 }
 110
 111 /*
 112  * encodes an IR-node, recursive worker
 113  */
 114 static void _encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
 115 {
 116   opcode code;
 117   int i, preds;
 118
 119   code = intern_get_irn_opcode(node);
 120   put_code(buf, code);
 121
 122   --max_depth;
 123
 124   if (max_depth <= 0) {
 125     put_code(buf, 0);
 126     return;
 127   }
 128
 129   preds = intern_get_irn_arity(node);
 130   put_code(buf, preds);
 131
 132   for (i = 0; i < preds; ++i) {
 133     ir_node *n = intern_get_irn_n(node, i);
 134
 135     _encode_node(n, buf, max_depth);
 136   }
 137 }
 138
 139 /**
 140  * encode an IR-node
 141  */
 142 static void encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
 143 {
 144   _encode_node(node, buf, max_depth);
 145   put_code(buf, VLC_TAG_END);
 146 }