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

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