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

   1 /*
   2  * pattern history
   3  */
   4 #include <assert.h>
   5 #include <stdlib.h>
   6
   7 #include "ident.h"
   8 #include "irnode_t.h"
   9 #include "irgwalk.h"
  10 #include "pset.h"
  11 #include "counter.h"
  12 #include "irprog.h"
  13
  14 /*
  15  * just be make some things clear :-), the
  16  * poor man "generics"
  17  */
  18 #define HASH_MAP(type) pset_##type
  19
  20 typedef pset pset_pattern_entry_t;
  21
  22 typedef unsigned char BYTE;
  23
  24
  25 /**
  26  * The code buffer
  27  */
  28 typedef struct _code_buf_t {
  29   BYTE          *next;          /**< next byte to be written */
  30   BYTE          *end;           /**< end of the buffer */
  31   BYTE          *start;         /**< start of the buffer */
  32   unsigned      hash;           /**< calculates the hash value */
  33 } CODE_BUFFER;
  34
  35 /**
  36  * VLC codes
  37  */
  38 enum vlc_code_t {
  39   VLC_7BIT       = 0x00,        /**< 8 bit code, carrying 7 bits payload */
  40   VLC_14BIT      = 0x80,        /**< 16 bit code, carrying 14 bits payload */
  41   VLC_21BIT      = 0xC0,        /**< 24 bit code, carrying 21 bits payload */
  42   VLC_28BIT      = 0xE0,        /**< 32 bit code, carrying 28 bits payload */
  43   VLC_32BIT      = 0xF0,        /**< 40 bit code, carrying 32 bits payload */
  44
  45   VLC_TAG_FIRST  = 0xF1,        /**< first possible tag value */
  46   VLC_TAG_EMPTY  = 0xFC,        /**< encodes an empty entity */
  47   VLC_TAG_OPTION = 0xFD,        /**< options exists */
  48   VLC_TAG_REF    = 0xFE,        /**< special tag, next code is an ID */
  49   VLC_TAG_END    = 0xFF,        /**< end tag */
  50 };
  51
  52 /*
  53  * An entry for patterns
  54  */
  55 typedef struct _pattern_entry_t {
  56   counter_t   count;            /**< amount of pattern occurance */
  57   unsigned    len;              /**< lenght of the VLC encoded buffer */
  58   BYTE        buf[1];           /**< buffer contains the VLC encoded pattern */
  59 } pattern_entry_t;
  60
  61 /**
  62  * current options
  63  */
  64 enum options_t {
  65   OPT_WITH_MODE = 0x00000001,   /**< use modes */
  66 };
  67
  68
  69 /**
  70  * pattern info
  71  */
  72 typedef struct _pattern_info_t {
  73   int                       enable;             /**< if non-zero, this module is enabled */
  74   struct obstack            obst;               /**< obstack containing the counters */
  75   HASH_MAP(pattern_entry_t) *pattern_hash;      /**< hash map containing the counter for pattern */
  76   unsigned                  bound;              /**< lowest value for output */
  77   unsigned                  options;            /**< option mask */
  78 } pattern_info_t;
  79
  80 /*
  81  * global status
  82  */
  83 static pattern_info_t _status, *status = &_status;
  84
  85 /**
  86  * compare two elemnts for counter
  87  */
  88 static int pattern_count_cmp(const void *elt, const void *key)
  89 {
  90   int cmp;
  91
  92   pattern_entry_t **e1 = (pattern_entry_t **)elt;
  93   pattern_entry_t **e2 = (pattern_entry_t **)key;
  94
  95   cmp = cnt_cmp(&(*e1)->count, &(*e2)->count);
  96
  97   /* we want it sorted in descending order */
  98   return cmp * - 1;
  99 }
 100
 101 /**
 102  * compare two elements of the pattern hash
 103  */
 104 static int pattern_cmp(const void *elt, const void *key)
 105 {
 106   const pattern_entry_t *e1 = elt;
 107   const pattern_entry_t *e2 = key;
 108   int diff = e1->len - e2->len;
 109
 110   if (diff)
 111     return diff;
 112
 113   return memcmp(e1->buf, e2->buf, e1->len);
 114 }
 115
 116 /**
 117  * initialise a code buffer
 118  */
 119 static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
 120 {
 121   buf->start = buf->next = data;
 122   buf->end   = data + len;
 123   buf->hash  = 0x2BAD4;
 124 }
 125
 126 /**
 127  * put a byte into the buffer
 128  */
 129 static INLINE void put_byte(CODE_BUFFER *buf, BYTE byte)
 130 {
 131   if (buf->next < buf->end) {
 132     unsigned hash = buf->hash;
 133
 134     hash = (hash * 9) ^ byte;
 135     *buf->next++ = byte;
 136     buf->hash    = hash;
 137   }
 138 }
 139
 140 /**
 141  * returns the current lenght of a buffer
 142  */
 143 static unsigned buf_lenght(const CODE_BUFFER *buf)
 144 {
 145   return buf->next - buf->start;
 146 }
 147
 148 /**
 149  * returns the current lenght of a buffer
 150  */
 151 static const BYTE *buf_content(const CODE_BUFFER *buf)
 152 {
 153   return buf->start;
 154 }
 155
 156 /**
 157  * returns the hash value of a buffer
 158  */
 159 static unsigned buf_hash(const CODE_BUFFER *buf)
 160 {
 161   return buf->hash;
 162 }
 163
 164 /**
 165  * returns the next byte from the buffer WITHOUT dropping
 166  */
 167 static INLINE BYTE look_byte(CODE_BUFFER *buf)
 168 {
 169   if (buf->next < buf->end)
 170     return *buf->next;
 171   return VLC_TAG_END;
 172 }
 173
 174 /**
 175  * returns the next byte from the buffer WITH dropping
 176  */
 177 static INLINE BYTE get_byte(CODE_BUFFER *buf)
 178 {
 179   if (buf->next < buf->end)
 180     return *buf->next++;
 181   return VLC_TAG_END;
 182 }
 183
 184 #define BITS(n)         (1 << (n))
 185
 186 /**
 187  * put a 32bit value into the buffer
 188  */
 189 static void put_code(CODE_BUFFER *buf, unsigned code)
 190 {
 191   if (code < BITS(7)) {
 192     put_byte(buf, VLC_7BIT | code);
 193   }
 194   else if (code < BITS(6 + 8)) {
 195     put_byte(buf, VLC_14BIT | (code >> 8));
 196     put_byte(buf, code);
 197   }
 198   else if (code < BITS(5 + 8 + 8)) {
 199     put_byte(buf, VLC_21BIT | (code >> 16));
 200     put_byte(buf, code >> 8);
 201     put_byte(buf, code);
 202   }
 203   else if (code < BITS(4 + 8 + 8 + 8)) {
 204     put_byte(buf, VLC_28BIT | (code >> 24));
 205     put_byte(buf, code >> 16);
 206     put_byte(buf, code >> 8);
 207     put_byte(buf, code);
 208   }
 209   else {
 210     put_byte(buf, VLC_32BIT);
 211     put_byte(buf, code >> 24);
 212     put_byte(buf, code >> 16);
 213     put_byte(buf, code >> 8);
 214     put_byte(buf, code);
 215   }
 216 }
 217
 218 #define BIT_MASK(n)     ((1 << (n)) - 1)
 219
 220 /**
 221  * get 32 bit from the buffer
 222  */
 223 static unsigned get_code(CODE_BUFFER *buf)
 224 {
 225   unsigned code = get_byte(buf);
 226
 227   if (code < VLC_14BIT)
 228     return code;
 229   if (code < VLC_21BIT)
 230     return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
 231   if (code < VLC_28BIT) {
 232     code  = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
 233     code |= get_byte(buf);
 234     return code;
 235   }
 236   if (code < VLC_32BIT) {
 237     code  = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
 238     code |= get_byte(buf) <<  8;
 239     code |= get_byte(buf);
 240     return code;
 241   }
 242   if (code == VLC_32BIT) {
 243     code  = get_byte(buf) << 24;
 244     code |= get_byte(buf) << 16;
 245     code |= get_byte(buf) <<  8;
 246     code |= get_byte(buf);
 247     return code;
 248   }
 249   /* should not happen */
 250   assert(0 && "Wrong code in buffer");
 251
 252   return 0;
 253 }
 254
 255 /**
 256  * put a tag into the buffer
 257  */
 258 static void put_tag(CODE_BUFFER *buf, BYTE tag)
 259 {
 260   assert(tag >= VLC_TAG_FIRST && "invalid tag");
 261
 262   put_byte(buf, tag);
 263 }
 264
 265 /**
 266  * returns the next tag or zero if the next code isn't a tag
 267  */
 268 static BYTE next_tag(CODE_BUFFER *buf)
 269 {
 270   BYTE b = look_byte(buf);
 271
 272   if (b >= VLC_TAG_FIRST)
 273     return get_byte(buf);
 274   return 0;
 275 }
 276
 277 /*
 278  * encodes an IR-node, recursive worker
 279  */
 280 static void _encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
 281 {
 282   int i, preds;
 283
 284 #if 0
 285   opcode code = get_irn_opcode(node);
 286 #else
 287   ir_op *code = get_irn_op(node);
 288 #endif
 289
 290   put_code(buf, (unsigned)code);
 291
 292   if (status->options & OPT_WITH_MODE) {
 293     ir_mode *mode = get_irn_mode(node);
 294
 295     if (mode)
 296       put_code(buf, (unsigned)mode);
 297     else
 298       put_tag(buf, VLC_TAG_EMPTY);
 299   }
 300
 301   --max_depth;
 302
 303   if (max_depth <= 0) {
 304     put_code(buf, 0);
 305     return;
 306   }
 307
 308   preds = get_irn_arity(node);
 309   put_code(buf, preds);
 310
 311   for (i = 0; i < preds; ++i) {
 312     ir_node *n = get_irn_n(node, i);
 313
 314     _encode_node(n, buf, max_depth);
 315   }
 316 }
 317
 318 /**
 319  * encode an IR-node
 320  */
 321 static void encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
 322 {
 323   put_tag(buf, VLC_TAG_OPTION);
 324   put_code(buf, status->options);
 325   _encode_node(node, buf, max_depth);
 326 }
 327
 328
 329 /**
 330  * decode an IR-node, recursive walker
 331  */
 332 static void _decode_node(CODE_BUFFER *buf, unsigned options)
 333 {
 334   unsigned op_code = get_code(buf);
 335   unsigned code    = next_tag(buf);
 336   ir_op *op = (ir_op *)op_code;
 337
 338   /* output the opcode-name */
 339   printf("%s", get_id_str(op->name));
 340
 341   if (options & OPT_WITH_MODE) {
 342     if (next_tag(buf) != VLC_TAG_EMPTY) {
 343       unsigned mode_code = get_code(buf);
 344       ir_mode *mode = (ir_mode *)mode_code;
 345       printf("%s", get_mode_name(mode));
 346     }
 347   }
 348
 349   /* enter it into the ID table */
 350
 351   if (code != VLC_TAG_END) {
 352     /* more info, do recursion */
 353     int i, preds;
 354
 355     preds = get_code(buf);
 356     if (preds > 0) {
 357       printf("(");
 358       for (i = 0; i < preds; ++i) {
 359         if (i > 0)
 360           printf(", ");
 361         _decode_node(buf, options);
 362       }
 363       printf(")");
 364     }
 365   }
 366 }
 367
 368 /**
 369  * decode an IR-node
 370  */
 371 static void decode_node(BYTE *b, unsigned len)
 372 {
 373   CODE_BUFFER buf;
 374   unsigned code, options = 0;
 375
 376   init_buf(&buf, b, len);
 377
 378   code = next_tag(&buf);
 379   if (code == VLC_TAG_OPTION) {
 380     options = get_code(&buf);
 381   }
 382   _decode_node(&buf, options);
 383 }
 384
 385 /**
 386  * the environment for the pattern calculation
 387  */
 388 typedef struct _pattern_env {
 389   int max_depth;                /**< maximum depth for pattern generation */
 390 } pattern_env_t;
 391
 392 /**
 393  * calculate a hash value for a pattern
 394  */
 395 static unsigned pattern_hash(pattern_entry_t *key)
 396 {
 397   return 9 * key->buf[0] + 31 * key->buf[key->len - 1] + 7 * key->buf[key->len >> 1];
 398 }
 399
 400 /**
 401  * Returns the associates pattern_entry_t for a CODE_BUF
 402  */
 403 static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
 404 {
 405   pattern_entry_t *key, *elem;
 406   unsigned len = buf_lenght(buf);
 407   unsigned hash;
 408
 409   key = obstack_alloc(&status->obst, sizeof(*key) + len - 1);
 410   assert(key);
 411
 412   key->len = len;
 413   memcpy(key->buf, buf_content(buf), len);
 414
 415   hash = buf_hash(buf); // pattern_hash(key);
 416
 417   elem = pset_find(set, key, hash);
 418   if (elem) {
 419     obstack_free(&status->obst, key);
 420     return elem;
 421   }
 422
 423   cnt_clr(&key->count);
 424   assert(key != (void *)4);
 425   return pset_insert(set, key, hash);
 426 }
 427
 428 /**
 429  * walker for nodes pattern calculation
 430  */
 431 static void calc_nodes_pattern(ir_node *node, void *ctx)
 432 {
 433   BYTE            buffer[1024];
 434   pattern_env_t   *env = ctx;
 435   CODE_BUFFER     buf;
 436   pattern_entry_t *entry;
 437
 438   init_buf(&buf, buffer, sizeof(buffer));
 439   encode_node(node, &buf, env->max_depth);
 440
 441   entry = pattern_get_entry(&buf, status->pattern_hash);
 442
 443   /* increase count */
 444   cnt_inc(&entry->count);
 445 }
 446
 447 /**
 448  */
 449 static void pattern_output(void)
 450 {
 451   pattern_entry_t *entry;
 452   pattern_entry_t **pattern_arr;
 453   int i, count = pset_count(status->pattern_hash);
 454
 455   printf("\n%d pattern detected\n", count);
 456
 457   if (count <= 0)
 458     return;
 459
 460   pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
 461   for (i = 0, entry = pset_first(status->pattern_hash);
 462        entry && i < count;
 463        entry = pset_next(status->pattern_hash), ++i) {
 464     pattern_arr[i] =  entry;
 465   }
 466   assert(count == i);
 467   count = i;
 468
 469   /* sort it */
 470   qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
 471
 472   for (i = 0; i < count; ++i) {
 473     entry = pattern_arr[i];
 474     if (entry->count.cnt[0] < status->bound)
 475       continue;
 476
 477     printf("%8d\t", entry->count.cnt[0]);
 478     decode_node(entry->buf, entry->len);
 479     printf("\n");
 480   }
 481 }
 482
 483 /*
 484  * calculates the pattern history
 485  */
 486 void stat_calc_pattern_history(ir_graph *irg)
 487 {
 488   pattern_env_t env;
 489
 490   if (! status->enable)
 491     return;
 492
 493   /* do NOT count the const code IRG */
 494   if (irg == get_const_code_irg())
 495     return;
 496
 497   env.max_depth = 4;
 498   irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
 499 }
 500
 501 /*
 502  * initialises the pattern history
 503  */
 504 void stat_init_pattern_history(int enable)
 505 {
 506   status->enable = enable;
 507   if (! enable)
 508     return;
 509
 510   status->bound   = 3;
 511   status->options = OPT_WITH_MODE;
 512
 513   obstack_init(&status->obst);
 514
 515   /* create the hash-table */
 516   status->pattern_hash = new_pset(pattern_cmp, 8);
 517 }
 518
 519 /*
 520  * finishes the pattern history
 521  */
 522 void stat_finish_pattern_history(void)
 523 {
 524   if (! status->enable)
 525     return;
 526
 527   pattern_output();
 528
 529   del_pset(status->pattern_hash);
 530   obstack_free(&status->obst, NULL);
 531
 532   status->enable = 0;
 533 }