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