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

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