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 address to be written. */
  34         BYTE     *end;     /**< End address of the buffer. */
  35         BYTE     *start;   /**< Start address of the buffer. */
  36         unsigned hash;     /**< The hash value for the buffer content. */
  37 } CODE_BUFFER;
  38
  39 /**
  40  * Reserved 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 holding one pattern.
  59  */
  60 typedef struct _pattern_entry_t {
  61         counter_t   count;        /**< Amount of pattern occurance. */
  62         unsigned    len;          /**< The length of the VLC encoded buffer. */
  63         BYTE        buf[1];       /**< The buffer containing the VLC encoded pattern. */
  64 } pattern_entry_t;
  65
  66 /**
  67  * Current options for the pattern matcher.
  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         OPT_PERSIST_PATTERN = 0x00000008, /**< persistant pattern hash */
  74 };
  75
  76
  77 /**
  78  * Pattern info.
  79  */
  80 typedef struct _pattern_info_t {
  81         int                       enable;         /**< If non-zero, this module is enabled. */
  82         struct obstack            obst;           /**< An obstack containing the counters. */
  83         HASH_MAP(pattern_entry_t) *pattern_hash;  /**< A hash map containing the pattern. */
  84         unsigned                  bound;          /**< Lowest value for pattern output. */
  85         unsigned                  options;        /**< Current option mask. */
  86 } pattern_info_t;
  87
  88 /*
  89  * global status
  90  */
  91 static pattern_info_t _status, *status = &_status;
  92
  93 /**
  94  * Compare two pattern for its occurance counter.
  95  */
  96 static int pattern_count_cmp(const void *elt, const void *key)
  97 {
  98         int cmp;
  99
 100         pattern_entry_t **e1 = (pattern_entry_t **)elt;
 101         pattern_entry_t **e2 = (pattern_entry_t **)key;
 102
 103         /* we want it sorted in descending order */
 104         cmp = cnt_cmp(&(*e2)->count, &(*e1)->count);
 105
 106         return cmp;
 107 }  /* pattern_count_cmp */
 108
 109 /**
 110  * Compare two pattern for its pattern hash.
 111  */
 112 static int pattern_cmp(const void *elt, const void *key)
 113 {
 114         const pattern_entry_t *e1 = elt;
 115         const pattern_entry_t *e2 = key;
 116         int diff = e1->len - e2->len;
 117
 118         if (diff)
 119                 return diff;
 120
 121         return memcmp(e1->buf, e2->buf, e1->len);
 122 }  /* pattern_cmp */
 123
 124 /**
 125  * Initialize a code buffer.
 126  *
 127  * @param buf   the code buffer
 128  * @param data  a buffer address
 129  * @param len   the length of the data buffer
 130  */
 131 static void init_buf(CODE_BUFFER *buf, BYTE *data, unsigned len)
 132 {
 133         buf->start = buf->next = data;
 134         buf->end   = data + len;
 135         buf->hash  = 0x2BAD4;      /* An arbitrary seed. */
 136 }  /* init_buf */
 137
 138 /**
 139  * Put a byte into the buffer.
 140  *
 141  * @param buf   the code buffer
 142  * @param byte  the byte to write
 143  *
 144  * The hash value for the buffer content is updated.
 145  */
 146 static INLINE void put_byte(CODE_BUFFER *buf, unsigned byte)
 147 {
 148         if (buf->next < buf->end) {
 149                 unsigned hash = buf->hash;
 150
 151                 hash = (hash * 9) ^ byte;
 152                 *buf->next++ = byte;
 153                 buf->hash    = hash;
 154         }  /* if */
 155 }  /* put_byte */
 156
 157 /**
 158  * Returns the current length of a buffer.
 159  *
 160  * @param buf   the code buffer
 161  *
 162  * @return  the length of the buffer content
 163  */
 164 static unsigned buf_lenght(const CODE_BUFFER *buf)
 165 {
 166         return buf->next - buf->start;
 167 }  /* buf_lenght */
 168
 169 /**
 170  * Returns the current content of a buffer.
 171  *
 172  * @param buf   the code buffer
 173  *
 174  * @return  the start address of the buffer content
 175  */
 176 static const BYTE *buf_content(const CODE_BUFFER *buf)
 177 {
 178         return buf->start;
 179 }  /* buf_content */
 180
 181 /**
 182  * Returns the hash value of a buffer.
 183  *
 184  * @param buf   the code buffer
 185  *
 186  * @return  the hash value of the buffer content
 187  */
 188 static unsigned buf_hash(const CODE_BUFFER *buf)
 189 {
 190         return buf->hash;
 191 }  /* buf_hash */
 192
 193 /**
 194  * Returns the next byte from the buffer WITHOUT dropping.
 195  *
 196  * @param buf   the code buffer
 197  *
 198  * @return  the next byte from the code buffer
 199  */
 200 static INLINE BYTE look_byte(CODE_BUFFER *buf)
 201 {
 202         if (buf->next < buf->end)
 203                 return *buf->next;
 204         return VLC_TAG_END;
 205 }  /* look_byte */
 206
 207 /**
 208  * Returns the next byte from the buffer WITH dropping.
 209  *
 210  * @param buf   the code buffer
 211  *
 212  * @return  the next byte from the code buffer
 213  */
 214 static INLINE BYTE get_byte(CODE_BUFFER *buf)
 215 {
 216         if (buf->next < buf->end)
 217                 return *buf->next++;
 218         return VLC_TAG_END;
 219 }  /* get_byte */
 220
 221 #define BITS(n)   (1 << (n))
 222
 223 /**
 224  * Put a 32bit value into the buffer.
 225  *
 226  * @param buf   the code buffer
 227  * @param code  the code to be written into the buffer
 228  */
 229 static void put_code(CODE_BUFFER *buf, unsigned code)
 230 {
 231         if (code < BITS(7)) {
 232                 put_byte(buf, VLC_7BIT | code);
 233         } else if (code < BITS(6 + 8)) {
 234                 put_byte(buf, VLC_14BIT | (code >> 8));
 235                 put_byte(buf, code);
 236         } else if (code < BITS(5 + 8 + 8)) {
 237                 put_byte(buf, VLC_21BIT | (code >> 16));
 238                 put_byte(buf, code >> 8);
 239                 put_byte(buf, code);
 240         } else if (code < BITS(4 + 8 + 8 + 8)) {
 241                 put_byte(buf, VLC_28BIT | (code >> 24));
 242                 put_byte(buf, code >> 16);
 243                 put_byte(buf, code >> 8);
 244                 put_byte(buf, code);
 245         } else {
 246                 put_byte(buf, VLC_32BIT);
 247                 put_byte(buf, code >> 24);
 248                 put_byte(buf, code >> 16);
 249                 put_byte(buf, code >> 8);
 250                 put_byte(buf, code);
 251         }  /* if */
 252 }  /* put_code */
 253
 254 #define BIT_MASK(n) ((1 << (n)) - 1)
 255
 256 /**
 257  * Get 32 bit from the buffer.
 258  *
 259  * @param buf   the code buffer
 260  *
 261  * @return  next 32bit value from the code buffer
 262  */
 263 static unsigned get_code(CODE_BUFFER *buf)
 264 {
 265         unsigned code = get_byte(buf);
 266
 267         if (code < VLC_14BIT)
 268                 return code;
 269         if (code < VLC_21BIT)
 270                 return ((code & BIT_MASK(6)) << 8) | get_byte(buf);
 271         if (code < VLC_28BIT) {
 272                 code  = ((code & BIT_MASK(5)) << 16) | (get_byte(buf) << 8);
 273                 code |= get_byte(buf);
 274                 return code;
 275         }  /* if */
 276         if (code < VLC_32BIT) {
 277                 code  = ((code & BIT_MASK(4)) << 24) | (get_byte(buf) << 16);
 278                 code |= get_byte(buf) <<  8;
 279                 code |= get_byte(buf);
 280                 return code;
 281         }  /* if */
 282         if (code == VLC_32BIT) {
 283                 code  = get_byte(buf) << 24;
 284                 code |= get_byte(buf) << 16;
 285                 code |= get_byte(buf) <<  8;
 286                 code |= get_byte(buf);
 287                 return code;
 288         }  /* if */
 289         /* should not happen */
 290         assert(0 && "Wrong code in buffer");
 291
 292         return 0;
 293 }  /* get_code */
 294
 295 /**
 296  * Put a tag into the buffer.
 297  *
 298  * @param buf   the code buffer
 299  * @param tag   the tag to write to the code buffer
 300  */
 301 static void put_tag(CODE_BUFFER *buf, BYTE tag)
 302 {
 303         assert(tag >= VLC_TAG_FIRST && "invalid tag");
 304
 305         put_byte(buf, tag);
 306 }  /* put_tag */
 307
 308 /**
 309  * Returns the next tag or zero if the next code isn't a tag.
 310  *
 311  * @param buf   the code buffer
 312  *
 313  * @return the next tag in the code buffer
 314  */
 315 static BYTE next_tag(CODE_BUFFER *buf)
 316 {
 317         BYTE b = look_byte(buf);
 318
 319         if (b >= VLC_TAG_FIRST)
 320                 return get_byte(buf);
 321         return 0;
 322 }  /* next_tag */
 323
 324 /**
 325  * An Environment for the pattern encoder.
 326  */
 327 typedef struct _codec_enc_t {
 328         CODE_BUFFER      *buf;      /**< The current code buffer. */
 329         set              *id_set;   /**< A set containing all already seen Firm nodes. */
 330         unsigned         curr_id;   /**< The current node id. */
 331         unsigned         options;   /**< The encoding options. */
 332         pattern_dumper_t *dmp;      /**< The dumper for the decoder. */
 333 } codec_env_t;
 334
 335 /**
 336  * An address entry.
 337  */
 338 typedef struct _addr_entry_t {
 339         void *addr;     /**< the address */
 340         unsigned id;    /**< associated ID */
 341 } addr_entry_t;
 342
 343 /**
 344  * Compare two addresses.
 345  */
 346 static int addr_cmp(const void *p1, const void *p2, size_t size) {
 347         const addr_entry_t *e1 = p1;
 348         const addr_entry_t *e2 = p2;
 349
 350         return e1->addr != e2->addr;
 351 }  /* addr_cmp */
 352
 353 /**
 354  * Encodes an IR-node, recursive worker.
 355  *
 356  * @return reached depth
 357  */
 358 static int _encode_node(ir_node *node, int max_depth, codec_env_t *env)
 359 {
 360         addr_entry_t entry, *r_entry;
 361         set_entry *s_entry;
 362         int i, preds;
 363         int res, depth;
 364
 365         opcode code = get_irn_opcode(node);
 366
 367         /* insert the node into our ID map */
 368         entry.addr = node;
 369         entry.id   = env->curr_id;
 370
 371         s_entry = set_hinsert(env->id_set, &entry, sizeof(entry), HASH_PTR(node));
 372         r_entry = (addr_entry_t *)s_entry->dptr;
 373
 374         if (r_entry->id != env->curr_id) {
 375                 /* already in the map, add an REF */
 376                 put_tag(env->buf, VLC_TAG_REF);
 377                 put_code(env->buf, r_entry->id);
 378
 379                 return max_depth;
 380         } else {
 381                 /* a new entry, proceed */
 382                 ++env->curr_id;
 383         }  /* if */
 384
 385         put_code(env->buf, (unsigned)code);
 386
 387         /* do we need the mode ? */
 388         if (env->options & OPT_WITH_MODE) {
 389                 ir_mode *mode = get_irn_mode(node);
 390
 391                 if (mode)
 392                         /* FIXME: not 64bit save */
 393                         put_code(env->buf, (unsigned)mode);
 394                 else
 395                         put_tag(env->buf, VLC_TAG_EMPTY);
 396         }  /* if */
 397
 398         /* do we need integer constants */
 399         if (env->options & OPT_WITH_ICONST) {
 400                 if (code == iro_Const) {
 401                         tarval *tv = get_Const_tarval(node);
 402
 403                         if (tarval_is_long(tv)) {
 404                                 long v = get_tarval_long(tv);
 405
 406                                 put_tag(env->buf, VLC_TAG_ICONST);
 407                                 put_code(env->buf, v);
 408                         }  /* if */
 409                 }  /* if */
 410         }  /* if */
 411
 412         --max_depth;
 413
 414         if (max_depth <= 0) {
 415                 put_code(env->buf, 0);
 416                 return max_depth;
 417         } /* if */
 418
 419         preds = get_irn_arity(node);
 420         put_code(env->buf, preds);
 421
 422         res = INT_MAX;
 423         for (i = 0; i < preds; ++i) {
 424                 ir_node *n = get_irn_n(node, i);
 425
 426                 depth = _encode_node(n, max_depth, env);
 427                 if (depth < res)
 428                         res = depth;
 429         }  /* for */
 430         return res;
 431 }  /* _encode_node */
 432
 433 /**
 434  * Encode a DAG staring by the IR-node node.
 435  *
 436  * @param node       The root node of the graph
 437  * @param buf        The code buffer to store the bitstring in
 438  * @param max_depth  The maximum depth for descending
 439  *
 440  * @return The depth of the encoded graph (without cycles)
 441  */
 442 static int encode_node(ir_node *node, CODE_BUFFER *buf, int max_depth)
 443 {
 444         codec_env_t env;
 445         int         res;
 446
 447         /* initialize the encoder environment */
 448         env.buf     = buf;
 449         env.curr_id = 1;  /* 0 is used for special purpose */
 450         env.options = status->options;
 451         env.dmp     = NULL;
 452
 453         if (env.options & OPT_ENC_DAG)
 454                 env.id_set = new_set(addr_cmp, 32);
 455         else
 456                 env.id_set = NULL;
 457
 458         /* encode options if any for the decoder */
 459         if (env.options) {
 460                 put_tag(buf, VLC_TAG_OPTION);
 461                 put_code(buf, env.options);
 462         }  /* if */
 463
 464         res = _encode_node(node, max_depth, &env);
 465
 466         if (env.id_set != NULL)
 467                 del_set(env.id_set);
 468
 469         return max_depth - res;
 470 }  /* encode_node */
 471
 472 /**
 473  * Decode an IR-node, recursive walker.
 474  */
 475 static void _decode_node(unsigned parent, int position, codec_env_t *env)
 476 {
 477         unsigned code;
 478         unsigned op_code;
 479         unsigned mode_code = 0;
 480         long iconst;
 481         void *attr = NULL;
 482
 483         code = next_tag(env->buf);
 484         if (code == VLC_TAG_REF) { /* it's a REF */
 485                 code = get_code(env->buf);
 486
 487                 /* dump the edge */
 488                 if (parent) {
 489                         int edge_mode = 0;
 490                         /*
 491                          * the mode of a Firm edge can be either computed from its target or
 492                          * from its source and position. We must take the second approach because
 493                          * we dont know the target here, it's a ref.
 494                          */
 495                         pattern_dump_edge(env->dmp, code, parent, position, edge_mode);
 496                 }  /* if */
 497
 498                 /* dump the node ref */
 499                 pattern_dump_ref(env->dmp, code);
 500
 501                 return;
 502         }  /* if */
 503
 504         /* get the opcode */
 505         op_code = get_code(env->buf);
 506
 507         /* get the mode if encoded */
 508         if (env->options & OPT_WITH_MODE) {
 509                 if (next_tag(env->buf) != VLC_TAG_EMPTY) {
 510                         mode_code = get_code(env->buf);
 511                 }  /* if */
 512         }  /* if */
 513
 514         /* check, if a ICONST attribute is given */
 515         if (next_tag(env->buf) == VLC_TAG_ICONST) {
 516                 iconst = get_code(env->buf);
 517                 attr   = &iconst;
 518         }  /* if */
 519
 520         /* dump the edge */
 521         if (parent) {
 522                 int edge_mode = 0;
 523
 524                 /*
 525                  * the mode of a Firm edge can be either computed from its target or
 526                  * from its source and position. We take the second approach because
 527                  * we need it anyway for ref's.
 528                  */
 529                 pattern_dump_edge(env->dmp, env->curr_id, parent, position, edge_mode);
 530         }  /* if */
 531
 532         /* dump the node */
 533         parent = env->curr_id;
 534         pattern_dump_node(env->dmp, parent, op_code, mode_code, attr);
 535
 536         /* ok, we have a new ID */
 537         ++env->curr_id;
 538
 539         code = next_tag(env->buf);
 540         if (code != VLC_TAG_END) {
 541                 /* more info, do recursion */
 542                 int i, preds;
 543
 544                 preds = get_code(env->buf);
 545                 if (preds > 0) {
 546                         pattern_start_children(env->dmp, parent);
 547                         for (i = 0; i < preds; ++i) {
 548                                 _decode_node(parent, i, env);
 549                         }  /* for */
 550                         pattern_finish_children(env->dmp, parent);
 551                 }  /* if */
 552         }  /* if */
 553 }  /* _decode_node */
 554
 555 /**
 556  * Decode an IR-node.
 557  */
 558 static void decode_node(BYTE *b, unsigned len, pattern_dumper_t *dump)
 559 {
 560         codec_env_t env;
 561         CODE_BUFFER buf;
 562         unsigned code, options = 0;
 563
 564         init_buf(&buf, b, len);
 565
 566         env.buf     = &buf;
 567         env.curr_id = 1;  /* 0 is used for special purpose */
 568         env.dmp     = dump;
 569
 570         /* decode options */
 571         code = next_tag(&buf);
 572         if (code == VLC_TAG_OPTION) {
 573                 options = get_code(&buf);
 574         }  /* if */
 575         env.options = options;
 576
 577         _decode_node(0, 0, &env);
 578 }  /* decode_node */
 579
 580 /**
 581  * The environment for the pattern calculation.
 582  */
 583 typedef struct _pattern_env {
 584         int max_depth;    /**< maximum depth for pattern generation. */
 585 } pattern_env_t;
 586
 587 /**
 588  * Returns the associates pattern_entry_t for a CODE_BUF.
 589  *
 590  * @param buf  the code buffer
 591  * @param set  the hash table containing all pattern entries
 592  *
 593  * @return   the associated pattern_entry_t for the given code buffer
 594  *
 595  * If the code content was never seen before, a new pattern_entry is created
 596  * and returned.
 597  */
 598 static pattern_entry_t *pattern_get_entry(CODE_BUFFER *buf, pset *set)
 599 {
 600         pattern_entry_t *key, *elem;
 601         unsigned len = buf_lenght(buf);
 602         unsigned hash;
 603
 604         key = obstack_alloc(&status->obst, sizeof(*key) + len - 1);
 605         assert(key);
 606
 607         key->len = len;
 608         memcpy(key->buf, buf_content(buf), len);
 609
 610         hash = buf_hash(buf);
 611
 612         elem = pset_find(set, key, hash);
 613         if (elem != NULL) {
 614                 obstack_free(&status->obst, key);
 615                 return elem;
 616         }  /* if */
 617
 618         cnt_clr(&key->count);
 619         return pset_insert(set, key, hash);
 620 }  /* pattern_get_entry */
 621
 622 /**
 623  * Increase the count for a pattern.
 624  *
 625  * @param buf    the code buffer containing the pattern
 626  * @param depth  the pattern depth
 627  *
 628  * @note Single node patterns are ignored
 629  */
 630 static void count_pattern(CODE_BUFFER *buf, int depth) {
 631         pattern_entry_t *entry;
 632
 633         /* ignore single node pattern (i.e. constants) */
 634         if (depth > 1) {
 635                 entry = pattern_get_entry(buf, status->pattern_hash);
 636
 637                 /* increase count */
 638                 cnt_inc(&entry->count);
 639         }  /* if */
 640 }  /* count_pattern */
 641
 642 /**
 643  * Pre-walker for nodes pattern calculation.
 644  */
 645 static void calc_nodes_pattern(ir_node *node, void *ctx)
 646 {
 647         BYTE            buffer[1024];
 648         pattern_env_t   *env = ctx;
 649         CODE_BUFFER     buf;
 650         int             depth;
 651
 652         init_buf(&buf, buffer, sizeof(buffer));
 653         depth = encode_node(node, &buf, env->max_depth);
 654
 655         count_pattern(&buf, depth);
 656 }  /* calc_nodes_pattern */
 657
 658 /**
 659  * Store all collected patterns.
 660  *
 661  * @param fname  filename for storage
 662  */
 663 static void store_pattern(const char *fname)
 664 {
 665         FILE *f;
 666         pattern_entry_t *entry;
 667         int i, count = pset_count(status->pattern_hash);
 668
 669         if (count <= 0)
 670                 return;
 671
 672         f = fopen(fname, "wb");
 673         if (! f) {
 674                 perror(fname);
 675                 return;
 676         }  /* if */
 677
 678         fwrite("FPS1", 4, 1, f);
 679         fwrite(&count, sizeof(count), 1, f);
 680
 681         for (i = 0, entry = pset_first(status->pattern_hash);
 682              entry && i < count;
 683              entry = pset_next(status->pattern_hash), ++i) {
 684                 fwrite(entry, sizeof(*entry) + (entry->len - 1), 1, f);
 685         }  /* for */
 686
 687         fclose(f);
 688 }  /* store_pattern */
 689
 690 /**
 691  * Read collected patterns from a file.
 692  *
 693  * @param fname  filename
 694  */
 695 static HASH_MAP(pattern_entry_t) *read_pattern(const char *fname)
 696 {
 697         FILE *f;
 698         pattern_entry_t *entry, tmp;
 699         int i, count;
 700         unsigned j;
 701         char magic[4];
 702         HASH_MAP(pattern_entry_t) *pattern_hash = new_pset(pattern_cmp, 8);
 703         BYTE            buffer[1024];
 704         CODE_BUFFER     buf;
 705
 706         f = fopen(fname, "rb");
 707         if (! f) {
 708                 perror(fname);
 709                 return NULL;
 710         }  /* if */
 711
 712         fread(magic, 4, 1, f);
 713         count = 0;
 714         fread(&count, sizeof(count), 1, f);
 715         if (memcmp(magic, "FPS1", 4) != 0 || count <= 0) {
 716                 fprintf(stderr, "Error: %s is not a Firm pattern store. Ignored.\n", fname);
 717                 fclose(f);
 718                 return NULL;
 719         }  /* if */
 720
 721
 722         /* read all pattern entries and put them into the hash table. */
 723         for (i = 0; i < count; ++i) {
 724                 init_buf(&buf, buffer, sizeof(buffer));
 725                 fread(&tmp, sizeof(tmp), 1, f);
 726                 put_byte(&buf, tmp.buf[0]);
 727                 for (j = 1; j < tmp.len; ++j)
 728                         put_byte(&buf, fgetc(f));
 729                 entry = pattern_get_entry(&buf, pattern_hash);
 730                 memcpy(&entry->count, &tmp.count, sizeof(entry->count));
 731         }  /* for */
 732
 733         fclose(f);
 734
 735         printf("Read %d pattern from %s\n", pset_count(pattern_hash), fname);
 736
 737         return pattern_hash;
 738 }  /* read_pattern */
 739
 740 /**
 741  * Write the collected patterns to a VCG file for inspection.
 742  *
 743  * @param fname  name of the VCG file to create
 744  */
 745 static void pattern_output(const char *fname)
 746 {
 747         pattern_entry_t  *entry;
 748         pattern_entry_t  **pattern_arr;
 749         pattern_dumper_t *dump;
 750         int i, count = pset_count(status->pattern_hash);
 751
 752         printf("\n%d pattern detected\n", count);
 753
 754         if (count <= 0)
 755                 return;
 756
 757         /* creates a dumper */
 758         dump = new_vcg_dumper(fname, 100);
 759
 760         pattern_arr = xmalloc(sizeof(*pattern_arr) * count);
 761         for (i = 0, entry = pset_first(status->pattern_hash);
 762              entry && i < count;
 763              entry = pset_next(status->pattern_hash), ++i) {
 764                 pattern_arr[i] =  entry;
 765         }  /* for */
 766         assert(count == i);
 767         count = i;
 768
 769         /* sort it */
 770         qsort(pattern_arr, count, sizeof(*pattern_arr), pattern_count_cmp);
 771
 772         for (i = 0; i < count; ++i) {
 773                 entry = pattern_arr[i];
 774                 if (cnt_to_uint(&entry->count) < status->bound)
 775                         continue;
 776
 777                 /* dump a pattern */
 778                 pattern_dump_new_pattern(dump, &entry->count);
 779                 decode_node(entry->buf, entry->len, dump);
 780                 pattern_dump_finish_pattern(dump);
 781         }  /* for */
 782
 783         /* destroy it */
 784         pattern_end(dump);
 785 }  /* pattern_output */
 786
 787 /*
 788  * Calculates the pattern history.
 789  */
 790 void stat_calc_pattern_history(ir_graph *irg)
 791 {
 792         pattern_env_t env;
 793
 794         if (! status->enable)
 795                 return;
 796
 797         /* do NOT count the const code IRG */
 798         if (irg == get_const_code_irg())
 799                 return;
 800
 801         env.max_depth = 5;
 802         irg_walk_graph(irg, calc_nodes_pattern, NULL, &env);
 803 }  /* stat_calc_pattern_history */
 804
 805 /*
 806  * Initializes the pattern history.
 807  */
 808 void stat_init_pattern_history(int enable)
 809 {
 810         HASH_MAP(pattern_entry_t) *pattern_hash = NULL;
 811
 812         status->enable = enable;
 813         if (! enable)
 814                 return;
 815
 816         status->bound   = 10;
 817         status->options = OPT_WITH_MODE | OPT_ENC_DAG | OPT_WITH_ICONST | OPT_PERSIST_PATTERN;
 818
 819         obstack_init(&status->obst);
 820
 821         /* create the hash-table */
 822         if (status->options & OPT_PERSIST_PATTERN)
 823                 pattern_hash = read_pattern("pattern.fps");
 824         if (pattern_hash == NULL)
 825                 pattern_hash = new_pset(pattern_cmp, 8);
 826         status->pattern_hash = pattern_hash;
 827 }  /* stat_init_pattern_history */
 828
 829 /*
 830  * Finish the pattern history.
 831  */
 832 void stat_finish_pattern_history(void)
 833 {
 834         if (! status->enable)
 835                 return;
 836
 837         store_pattern("pattern.fps");
 838         pattern_output("pattern.vcg");
 839
 840         del_pset(status->pattern_hash);
 841         obstack_free(&status->obst, NULL);
 842
 843         status->enable = 0;
 844 }  /* stat_finish_pattern_history */