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