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