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