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

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