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

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