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

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