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

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