Add native Windows binary for bison.

bison/src/bison/2.4.1/bison-2.4.1-src/lib/bitset_stats.c

+/* Bitset statistics.
+   Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* This file is a wrapper bitset implementation for the other bitset
+   implementations.  It provides bitset compatibility checking and
+   statistics gathering without having to instrument the bitset
+   implementations.  When statistics gathering is enabled, the bitset
+   operations get vectored through here and we then call the appropriate
+   routines.  */
+
+#include <config.h>
+
+#include "bitset_stats.h"
+
+#include "bbitset.h"
+#include "abitset.h"
+#include "ebitset.h"
+#include "lbitset.h"
+#include "vbitset.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "gettext.h"
+#define _(Msgid)  gettext (Msgid)
+
+/* Configuration macros.  */
+#define BITSET_STATS_FILE "bitset.dat"
+#define BITSET_LOG_COUNT_BINS 10
+#define BITSET_LOG_SIZE_BINS  16
+#define BITSET_DENSITY_BINS  20
+
+
+/* Accessor macros.  */
+#define BITSET_STATS_ALLOCS_INC(TYPE)                   \
+    bitset_stats_info->types[(TYPE)].allocs++
+#define BITSET_STATS_FREES_INC(BSET)                    \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++
+#define BITSET_STATS_SETS_INC(BSET)                     \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++
+#define BITSET_STATS_CACHE_SETS_INC(BSET)               \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++
+#define BITSET_STATS_RESETS_INC(BSET)                   \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++
+#define BITSET_STATS_CACHE_RESETS_INC(BSET)             \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++
+#define BITSET_STATS_TESTS_INC(BSET)                    \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++
+#define BITSET_STATS_CACHE_TESTS_INC(BSET)              \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++
+#define BITSET_STATS_LISTS_INC(BSET)                    \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++
+#define BITSET_STATS_LIST_COUNTS_INC(BSET, I)           \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
+#define BITSET_STATS_LIST_SIZES_INC(BSET, I)            \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
+#define BITSET_STATS_LIST_DENSITY_INC(BSET, I)          \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
+
+
+struct bitset_type_info_struct
+{
+  unsigned int allocs;
+  unsigned int frees;
+  unsigned int lists;
+  unsigned int sets;
+  unsigned int cache_sets;
+  unsigned int resets;
+  unsigned int cache_resets;
+  unsigned int tests;
+  unsigned int cache_tests;
+  unsigned int list_counts[BITSET_LOG_COUNT_BINS];
+  unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
+  unsigned int list_density[BITSET_DENSITY_BINS];
+};
+
+struct bitset_stats_info_struct
+{
+  unsigned int runs;
+  struct bitset_type_info_struct types[BITSET_TYPE_NUM];
+};
+
+
+struct bitset_stats_info_struct bitset_stats_info_data;
+struct bitset_stats_info_struct *bitset_stats_info;
+bool bitset_stats_enabled = false;
+
+
+/* Print a percentage histogram with message MSG to FILE.  */
+static void
+bitset_percent_histogram_print (FILE *file, const char *name, const char *msg,
+                                unsigned int n_bins, unsigned int *bins)
+{
+  unsigned int i;
+  unsigned int total;
+
+  total = 0;
+  for (i = 0; i < n_bins; i++)
+    total += bins[i];
+
+  if (!total)
+    return;
+
+  fprintf (file, "%s %s", name, msg);
+  for (i = 0; i < n_bins; i++)
+    fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n",
+             i * 100.0 / n_bins,
+             (i + 1) * 100.0 / n_bins, bins[i],
+             (100.0 * bins[i]) / total);
+}
+
+
+/* Print a log histogram with message MSG to FILE.  */
+static void
+bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
+                            unsigned int n_bins, unsigned int *bins)
+{
+  unsigned int i;
+  unsigned int total;
+  unsigned int max_width;
+
+  total = 0;
+  for (i = 0; i < n_bins; i++)
+    total += bins[i];
+
+  if (!total)
+    return;
+
+  /* Determine number of useful bins.  */
+  for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
+     continue;
+  n_bins = i;
+
+  /* 2 * ceil (log10 (2) * (N - 1)) + 1.  */
+  max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
+
+  fprintf (file, "%s %s", name, msg);
+  for (i = 0; i < 2; i++)
+    fprintf (file, "%*d\t%8u (%5.1f%%)\n",
+             max_width, i, bins[i], 100.0 * bins[i] / total);
+
+  for (; i < n_bins; i++)
+    fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
+             max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
+             1UL << (i - 1),
+             (1UL << i) - 1,
+             bins[i],
+             (100.0 * bins[i]) / total);
+}
+
+
+/* Print bitset statistics to FILE.  */
+static void
+bitset_stats_print_1 (FILE *file, const char *name,
+                      struct bitset_type_info_struct *stats)
+{
+  if (!stats)
+    return;
+
+  fprintf (file, "%s:\n", name);
+  fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),
+           stats->allocs, stats->frees,
+           stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
+  fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),
+           stats->sets, stats->cache_sets,
+           stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
+  fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),
+           stats->resets, stats->cache_resets,
+           stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
+  fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),
+           stats->tests, stats->cache_tests,
+           stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
+
+  fprintf (file, _("%u bitset_lists\n"), stats->lists);
+
+  bitset_log_histogram_print (file, name, _("count log histogram\n"),
+                              BITSET_LOG_COUNT_BINS, stats->list_counts);
+
+  bitset_log_histogram_print (file, name, _("size log histogram\n"),
+                              BITSET_LOG_SIZE_BINS, stats->list_sizes);
+
+  bitset_percent_histogram_print (file, name, _("density histogram\n"),
+                                  BITSET_DENSITY_BINS, stats->list_density);
+}
+
+
+/* Print all bitset statistics to FILE.  */
+static void
+bitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED)
+{
+  int i;
+
+  if (!bitset_stats_info)
+    return;
+
+  fprintf (file, _("Bitset statistics:\n\n"));
+
+  if (bitset_stats_info->runs > 1)
+    fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);
+
+  for (i = 0; i < BITSET_TYPE_NUM; i++)
+    bitset_stats_print_1 (file, bitset_type_names[i],
+                          &bitset_stats_info->types[i]);
+}
+
+
+/* Initialise bitset statistics logging.  */
+void
+bitset_stats_enable (void)
+{
+  if (!bitset_stats_info)
+    bitset_stats_info = &bitset_stats_info_data;
+  bitset_stats_enabled = true;
+}
+
+
+void
+bitset_stats_disable (void)
+{
+  bitset_stats_enabled = false;
+}
+
+
+/* Read bitset statistics file.  */
+void
+bitset_stats_read (const char *file_name)
+{
+  FILE *file;
+
+  if (!bitset_stats_info)
+    return;
+
+  if (!file_name)
+    file_name = BITSET_STATS_FILE;
+
+  file = fopen (file_name, "r");
+  if (file)
+    {
+      if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
+                 1, file) != 1)
+        {
+          if (ferror (file))
+            perror (_("Could not read stats file."));
+          else
+            fprintf (stderr, _("Bad stats file size.\n"));
+        }
+      if (fclose (file) != 0)
+        perror (_("Could not read stats file."));
+    }
+  bitset_stats_info_data.runs++;
+}
+
+
+/* Write bitset statistics file.  */
+void
+bitset_stats_write (const char *file_name)
+{
+  FILE *file;
+
+  if (!bitset_stats_info)
+    return;
+
+  if (!file_name)
+    file_name = BITSET_STATS_FILE;
+
+  file = fopen (file_name, "w");
+  if (file)
+    {
+      if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
+                  1, file) != 1)
+        perror (_("Could not write stats file."));
+      if (fclose (file) != 0)
+        perror (_("Could not write stats file."));
+    }
+  else
+    perror (_("Could not open stats file for writing."));
+}
+
+
+/* Dump bitset statistics to FILE.  */
+void
+bitset_stats_dump (FILE *file)
+{
+  bitset_stats_print (file, false);
+}
+
+
+/* Function to be called from debugger to print bitset stats.  */
+void
+debug_bitset_stats (void)
+{
+  bitset_stats_print (stderr, true);
+}
+
+
+static void
+bitset_stats_set (bitset dst, bitset_bindex bitno)
+{
+  bitset bset = dst->s.bset;
+  bitset_windex wordno = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = wordno - bset->b.cindex;
+
+  BITSET_STATS_SETS_INC (bset);
+
+  if (offset < bset->b.csize)
+    {
+      bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+      BITSET_STATS_CACHE_SETS_INC (bset);
+    }
+  else
+    BITSET_SET_ (bset, bitno);
+}
+
+
+static void
+bitset_stats_reset (bitset dst, bitset_bindex bitno)
+{
+  bitset bset = dst->s.bset;
+  bitset_windex wordno = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = wordno - bset->b.cindex;
+
+  BITSET_STATS_RESETS_INC (bset);
+
+  if (offset < bset->b.csize)
+    {
+      bset->b.cdata[offset] &=
+        ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+      BITSET_STATS_CACHE_RESETS_INC (bset);
+    }
+  else
+    BITSET_RESET_ (bset, bitno);
+}
+
+
+static bool
+bitset_stats_toggle (bitset src, bitset_bindex bitno)
+{
+    return BITSET_TOGGLE_ (src->s.bset, bitno);
+}
+
+
+static bool
+bitset_stats_test (bitset src, bitset_bindex bitno)
+{
+  bitset bset = src->s.bset;
+  bitset_windex wordno = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = wordno - bset->b.cindex;
+
+  BITSET_STATS_TESTS_INC (bset);
+
+  if (offset < bset->b.csize)
+    {
+      BITSET_STATS_CACHE_TESTS_INC (bset);
+      return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
+    }
+  else
+    return BITSET_TEST_ (bset, bitno);
+}
+
+
+static bitset_bindex
+bitset_stats_resize (bitset src, bitset_bindex size)
+{
+    return BITSET_RESIZE_ (src->s.bset, size);
+}
+
+
+static bitset_bindex
+bitset_stats_size (bitset src)
+{
+  return BITSET_SIZE_ (src->s.bset);
+}
+
+
+static bitset_bindex
+bitset_stats_count (bitset src)
+{
+  return BITSET_COUNT_ (src->s.bset);
+}
+
+
+static bool
+bitset_stats_empty_p (bitset dst)
+{
+  return BITSET_EMPTY_P_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_ones (bitset dst)
+{
+  BITSET_ONES_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_zero (bitset dst)
+{
+  BITSET_ZERO_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_copy (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  BITSET_COPY_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_disjoint_p (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_equal_p (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_not (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  BITSET_NOT_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_subset_p (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_and (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_andn (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_or (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_xor (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static void
+bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static void
+bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bitset_bindex
+bitset_stats_list (bitset bset, bitset_bindex *list,
+                   bitset_bindex num, bitset_bindex *next)
+{
+  bitset_bindex count;
+  bitset_bindex tmp;
+  bitset_bindex size;
+  bitset_bindex i;
+  enum bitset_type type;
+
+  count = BITSET_LIST_ (bset->s.bset, list, num, next);
+
+  type = BITSET_TYPE_ (bset->s.bset);
+  BITSET_STATS_LISTS_INC (bset->s.bset);
+
+  /* Log histogram of number of set bits.  */
+  for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
+     continue;
+  if (i >= BITSET_LOG_COUNT_BINS)
+     i = BITSET_LOG_COUNT_BINS - 1;
+  BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
+
+  /* Log histogram of number of bits in set.  */
+  size = BITSET_SIZE_ (bset->s.bset);
+  for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
+     continue;
+  if (i >= BITSET_LOG_SIZE_BINS)
+     i = BITSET_LOG_SIZE_BINS - 1;
+  BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
+
+  /* Histogram of fraction of bits set.  */
+  i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
+  if (i >= BITSET_DENSITY_BINS)
+     i = BITSET_DENSITY_BINS - 1;
+  BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
+  return count;
+}
+
+
+static bitset_bindex
+bitset_stats_list_reverse (bitset bset, bitset_bindex *list,
+                           bitset_bindex num, bitset_bindex *next)
+{
+  return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
+}
+
+
+static void
+bitset_stats_free (bitset bset)
+{
+  BITSET_STATS_FREES_INC (bset->s.bset);
+  BITSET_FREE_ (bset->s.bset);
+}
+
+
+struct bitset_vtable bitset_stats_vtable = {
+  bitset_stats_set,
+  bitset_stats_reset,
+  bitset_stats_toggle,
+  bitset_stats_test,
+  bitset_stats_resize,
+  bitset_stats_size,
+  bitset_stats_count,
+  bitset_stats_empty_p,
+  bitset_stats_ones,
+  bitset_stats_zero,
+  bitset_stats_copy,
+  bitset_stats_disjoint_p,
+  bitset_stats_equal_p,
+  bitset_stats_not,
+  bitset_stats_subset_p,
+  bitset_stats_and,
+  bitset_stats_and_cmp,
+  bitset_stats_andn,
+  bitset_stats_andn_cmp,
+  bitset_stats_or,
+  bitset_stats_or_cmp,
+  bitset_stats_xor,
+  bitset_stats_xor_cmp,
+  bitset_stats_and_or,
+  bitset_stats_and_or_cmp,
+  bitset_stats_andn_or,
+  bitset_stats_andn_or_cmp,
+  bitset_stats_or_and,
+  bitset_stats_or_and_cmp,
+  bitset_stats_list,
+  bitset_stats_list_reverse,
+  bitset_stats_free,
+  BITSET_STATS
+};
+
+
+/* Return enclosed bitset type.  */
+enum bitset_type
+bitset_stats_type_get (bitset bset)
+{
+   return BITSET_TYPE_ (bset->s.bset);
+}
+
+
+size_t
+bitset_stats_bytes (void)
+{
+  return sizeof (struct bitset_stats_struct);
+}
+
+
+bitset
+bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
+{
+  size_t bytes;
+  bitset sbset;
+
+  bset->b.vtable = &bitset_stats_vtable;
+
+  /* Disable cache.  */
+  bset->b.cindex = 0;
+  bset->b.csize = 0;
+  bset->b.cdata = 0;
+
+  BITSET_NBITS_ (bset) = n_bits;
+
+  /* Set up the actual bitset implementation that
+     we are a wrapper over.  */
+  switch (type)
+    {
+    default:
+      abort ();
+
+    case BITSET_ARRAY:
+      bytes = abitset_bytes (n_bits);
+      sbset = xcalloc (1, bytes);
+      abitset_init (sbset, n_bits);
+      break;
+
+    case BITSET_LIST:
+      bytes = lbitset_bytes (n_bits);
+      sbset = xcalloc (1, bytes);
+      lbitset_init (sbset, n_bits);
+      break;
+
+    case BITSET_TABLE:
+      bytes = ebitset_bytes (n_bits);
+      sbset = xcalloc (1, bytes);
+      ebitset_init (sbset, n_bits);
+      break;
+
+    case BITSET_VARRAY:
+      bytes = vbitset_bytes (n_bits);
+      sbset = xcalloc (1, bytes);
+      vbitset_init (sbset, n_bits);
+      break;
+    }
+
+  bset->s.bset = sbset;
+
+  BITSET_STATS_ALLOCS_INC (type);
+
+  return bset;
+}