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