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

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