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