gcc/stringpool.c

   1 /* String pool for GCC.
   2    Copyright (C) 2000 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GNU CC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* String pool allocator.  All strings allocated by ggc_alloc_string are
  22    uniquified and stored in an obstack which is never shrunk.  You can
  23    associate a tree with a string if you wish; this is used to implement
  24    get_identifier.
  25
  26    We have our own private hash table implementation which is similar
  27    to the one in cpphash.c (actually, it's a further refinement of
  28    that code).  libiberty's hashtab.c is not used because it requires
  29    100% average space overhead per string, which is unacceptable.
  30    Also, this algorithm is faster.  */
  31
  32 #include "config.h"
  33 #include "system.h"
  34 #include "ggc.h"
  35 #include "tree.h"
  36 #include "obstack.h"
  37 #include "flags.h"
  38 #include "toplev.h"
  39
  40 /* The "" allocated string.  */
  41 const char empty_string[] = "";
  42
  43 /* Character strings, each containing a single decimal digit.
  44    Written this way to save space.  */
  45 const char digit_vector[] = {
  46   '0', 0, '1', 0, '2', 0, '3', 0, '4', 0,
  47   '5', 0, '6', 0, '7', 0, '8', 0, '9', 0
  48 };
  49
  50 static struct obstack string_stack;
  51
  52 /* This is the hash entry associated with each string.  It lives in
  53    the hash table; only the string lives in the obstack.  Note that
  54    the string is not necessarily NUL terminated.  */
  55
  56 struct str_header
  57 {
  58   const char *ptr;
  59   tree data;    /* for get_identifier */
  60   unsigned int len;
  61 };
  62
  63 /* This is the hash table structure.  There's only one.  */
  64 struct str_hash
  65 {
  66   struct str_header *entries;
  67   size_t nslots;        /* total slots in the entries array */
  68   size_t nelements;     /* number of live elements */
  69
  70   /* table usage statistics */
  71   unsigned int searches;
  72   unsigned int collisions;
  73 };
  74 #define INITIAL_HASHSIZE (16*1024)
  75
  76 static struct str_hash string_hash = { 0, INITIAL_HASHSIZE, 0, 0, 0 };
  77
  78 enum insert_option { INSERT, NO_INSERT };
  79
  80 static struct str_header *alloc_string PARAMS ((const char *, size_t,
  81                                                 enum insert_option));
  82 static inline unsigned int calc_hash PARAMS ((const unsigned char *, size_t));
  83 static void mark_string_hash PARAMS ((void *));
  84 static struct str_header *expand_string_table PARAMS ((struct str_header *));
  85
  86 /* Convenience macro for iterating over the hash table.  E is set to
  87    each live entry in turn.  */
  88 #define FORALL_STRINGS(E) \
  89 for (E = string_hash.entries; E < string_hash.entries+string_hash.nslots; E++) \
  90   if (E->ptr != NULL)
  91     /* block here */
  92
  93 /* Likewise, but tests ->data instead of ->ptr (for cases where we only
  94    care about entries with ->data set)  */
  95 #define FORALL_IDS(E) \
  96 for (E = string_hash.entries; E < string_hash.entries+string_hash.nslots; E++) \
  97   if (E->data != NULL)
  98
  99 /* 0 while creating built-in identifiers.  */
 100 static int do_identifier_warnings;
 101
 102 /* Initialize the string pool.  */
 103 void
 104 init_stringpool ()
 105 {
 106   gcc_obstack_init (&string_stack);
 107   ggc_add_root (&string_hash, 1, sizeof string_hash, mark_string_hash);
 108
 109   /* Strings need no alignment.  */
 110   obstack_alignment_mask (&string_stack) = 0;
 111
 112   string_hash.entries = (struct str_header *)
 113     xcalloc (string_hash.nslots, sizeof (struct str_header));
 114 }
 115
 116 /* Enable warnings on similar identifiers (if requested).
 117    Done after the built-in identifiers are created.  */
 118 void
 119 start_identifier_warnings ()
 120 {
 121   do_identifier_warnings = 1;
 122 }
 123
 124 /* Record the size of an identifier node for the language in use.
 125    SIZE is the total size in bytes.
 126    This is called by the language-specific files.  This must be
 127    called before allocating any identifiers.  */
 128 void
 129 set_identifier_size (size)
 130      int size;
 131 {
 132   tree_code_length[(int) IDENTIFIER_NODE]
 133     = (size - sizeof (struct tree_common)) / sizeof (tree);
 134 }
 135
 136 /* Calculate the hash of the string STR, which is of length LEN.  */
 137 static inline unsigned int
 138 calc_hash (str, len)
 139      const unsigned char *str;
 140      size_t len;
 141 {
 142   size_t n = len;
 143   unsigned int r = 0;
 144 #define HASHSTEP(r, c) ((r) * 67 + (c - 113));
 145
 146   while (n--)
 147     r = HASHSTEP (r, *str++);
 148
 149   return r + len;
 150 #undef HASHSTEP
 151 }
 152
 153 /* Internal primitive: returns the header structure for the string of
 154    length LENGTH, containing CONTENTS.  If that string already exists
 155    in the table, returns the existing entry.  If the string hasn't
 156    been seen before and the last argument is INSERT, inserts and returns
 157    a new entry. Otherwise returns NULL.  */
 158 static struct str_header *
 159 alloc_string (contents, length, insert)
 160      const char *contents;
 161      size_t length;
 162      enum insert_option insert;
 163 {
 164   unsigned int hash = calc_hash ((const unsigned char *)contents, length);
 165   unsigned int hash2;
 166   unsigned int index;
 167   size_t sizemask;
 168   struct str_header *entry;
 169   struct str_header *entries = string_hash.entries;
 170
 171   sizemask = string_hash.nslots - 1;
 172   index = hash & sizemask;
 173
 174   /* hash2 must be odd, so we're guaranteed to visit every possible
 175      location in the table during rehashing.  */
 176   hash2 = ((hash * 17) & sizemask) | 1;
 177   string_hash.searches++;
 178
 179   for (;;)
 180     {
 181       entry = entries + index;
 182
 183       if (entry->ptr == NULL)
 184         break;
 185
 186       if (entry->len == length
 187           && !memcmp (entry->ptr, contents, length))
 188         return entry;
 189
 190       index = (index + hash2) & sizemask;
 191       string_hash.collisions++;
 192     }
 193
 194   if (insert == NO_INSERT)
 195     return NULL;
 196
 197   obstack_grow0 (&string_stack, contents, length);
 198   entry->ptr = (const char *) obstack_finish (&string_stack);
 199   entry->len = length;
 200   entry->data = NULL;
 201
 202   if (++string_hash.nelements * 4 < string_hash.nslots * 3)
 203     return entry;
 204
 205   /* Must expand the string table.  */
 206   return expand_string_table (entry);
 207 }
 208
 209 /* Subroutine of alloc_string which doubles the size of the hash table
 210    and rehashes all the strings into the new table.  Returns the entry
 211    in the new table corresponding to ENTRY.  */
 212 static struct str_header *
 213 expand_string_table (entry)
 214      struct str_header *entry;
 215 {
 216   struct str_header *nentries;
 217   struct str_header *e, *nentry = NULL;
 218   size_t size, sizemask;
 219
 220   size = string_hash.nslots * 2;
 221   nentries = (struct str_header *) xcalloc (size, sizeof (struct str_header));
 222   sizemask = size - 1;
 223
 224   FORALL_STRINGS (e)
 225     {
 226       unsigned int index, hash, hash2;
 227
 228       hash = calc_hash ((const unsigned char *) e->ptr, e->len);
 229       hash2 = ((hash * 17) & sizemask) | 1;
 230       index = hash & sizemask;
 231
 232       for (;;)
 233         {
 234           if (nentries[index].ptr == NULL)
 235             {
 236               nentries[index].ptr = e->ptr;
 237               nentries[index].len = e->len;
 238               nentries[index].data = e->data;
 239               if (e == entry)
 240                 nentry = nentries + index;
 241               break;
 242             }
 243
 244           index = (index + hash2) & sizemask;
 245         }
 246     }
 247
 248   free (string_hash.entries);
 249   string_hash.entries = nentries;
 250   string_hash.nslots = size;
 251   return nentry;
 252 }
 253
 254 /* Allocate and return a string constant of length LENGTH, containing
 255    CONTENTS.  If LENGTH is -1, CONTENTS is assumed to be a
 256    nul-terminated string, and the length is calculated using strlen.
 257    If the same string constant has been allocated before, that copy is
 258    returned this time too.  */
 259
 260 const char *
 261 ggc_alloc_string (contents, length)
 262      const char *contents;
 263      int length;
 264 {
 265   struct str_header *str;
 266
 267   if (length == -1)
 268     length = strlen (contents);
 269
 270   if (length == 0)
 271     return empty_string;
 272   if (length == 1 && contents[0] >= '0' && contents[0] <= '9')
 273     return digit_string (contents[0] - '0');
 274
 275   str = alloc_string (contents, length, INSERT);
 276   return str->ptr;
 277 }
 278
 279 /* Return an IDENTIFIER_NODE whose name is TEXT (a null-terminated string).
 280    If an identifier with that name has previously been referred to,
 281    the same node is returned this time.  */
 282 tree
 283 get_identifier (text)
 284      const char *text;
 285 {
 286   tree idp;
 287   struct str_header *str;
 288   size_t length = strlen (text);
 289
 290   str = alloc_string (text, length, INSERT);
 291   idp = str->data;
 292   if (idp == NULL)
 293     {
 294       if (TREE_CODE_LENGTH (IDENTIFIER_NODE) < 0)
 295         abort ();       /* set_identifier_size hasn't been called.  */
 296
 297       /* If this identifier is longer than the clash-warning length,
 298          do a brute force search of the entire table for clashes.  */
 299       if (warn_id_clash && do_identifier_warnings && length >= (size_t) id_clash_len)
 300         {
 301           struct str_header *e;
 302           FORALL_IDS (e)
 303             {
 304               if (e->len >= (size_t)id_clash_len
 305                   && !strncmp (e->ptr, text, id_clash_len))
 306                 {
 307                   warning ("\"%s\" and \"%s\" identical in first %d characters",
 308                            text, e->ptr, id_clash_len);
 309                   break;
 310                 }
 311             }
 312         }
 313
 314       idp = make_node (IDENTIFIER_NODE);
 315       IDENTIFIER_LENGTH (idp) = length;
 316       IDENTIFIER_POINTER (idp) = str->ptr;
 317 #ifdef GATHER_STATISTICS
 318       id_string_size += length;
 319 #endif
 320       str->data = idp;
 321     }
 322   return idp;
 323 }
 324
 325 /* If an identifier with the name TEXT (a null-terminated string) has
 326    previously been referred to, return that node; otherwise return
 327    NULL_TREE.  */
 328
 329 tree
 330 maybe_get_identifier (text)
 331      const char *text;
 332 {
 333   struct str_header *str;
 334   size_t length = strlen (text);
 335
 336   str = alloc_string (text, length, NO_INSERT);
 337   if (str)
 338     return str->data;  /* N.B. str->data might be null here, if the
 339                           string has been used but not as an identifier.  */
 340   return NULL_TREE;
 341 }
 342
 343 /* Report some basic statistics about the string pool.  */
 344
 345 void
 346 stringpool_statistics ()
 347 {
 348   size_t nelts, nids, overhead, headers;
 349   size_t total_bytes, longest, sum_of_squares;
 350   double exp_len, exp_len2, exp2_len;
 351   struct str_header *e;
 352 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 353                   ? (x) \
 354                   : ((x) < 1024*1024*10 \
 355                      ? (x) / 1024 \
 356                      : (x) / (1024*1024))))
 357 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 358
 359   total_bytes = longest = sum_of_squares = nids = 0;
 360   FORALL_STRINGS (e)
 361     {
 362       size_t n = e->len;
 363
 364       total_bytes += n;
 365       sum_of_squares += n*n;
 366       if (n > longest)
 367         longest = n;
 368       if (e->data)
 369         nids++;
 370     }
 371
 372   nelts = string_hash.nelements;
 373   overhead = obstack_memory_used (&string_stack) - total_bytes;
 374   headers = string_hash.nslots * sizeof (struct str_header);
 375
 376   fprintf (stderr,
 377 "\nString pool\n\
 378 entries\t\t%lu\n\
 379 identifiers\t%lu (%.2f%%)\n\
 380 slots\t\t%lu\n\
 381 bytes\t\t%lu%c (%lu%c overhead)\n\
 382 table size\t%lu%c\n",
 383            (unsigned long) nelts,
 384            (unsigned long) nids, nids * 100.0 / nelts,
 385            (unsigned long) string_hash.nslots,
 386            SCALE (total_bytes), LABEL (total_bytes),
 387            SCALE (overhead), LABEL (overhead),
 388            SCALE (headers), LABEL (headers));
 389
 390   exp_len = (double)total_bytes / (double)nelts;
 391   exp2_len = exp_len * exp_len;
 392   exp_len2 = (double)sum_of_squares / (double)nelts;
 393
 394   fprintf (stderr,
 395 "coll/search\t%.4f\n\
 396 ins/search\t%.4f\n\
 397 avg. entry\t%.2f bytes (+/- %.2f)\n\
 398 longest entry\t%lu\n",
 399            (double) string_hash.collisions / (double) string_hash.searches,
 400            (double) nelts / (double) string_hash.searches,
 401            exp_len, approx_sqrt (exp_len2 - exp2_len),
 402            (unsigned long) longest);
 403 #undef SCALE
 404 #undef LABEL
 405 }
 406
 407 /* Mark the string hash for GC.  */
 408
 409 static void
 410 mark_string_hash (arg)
 411      void *arg ATTRIBUTE_UNUSED;
 412 {
 413   struct str_header *h;
 414
 415   FORALL_IDS (h)
 416     {
 417       ggc_mark_tree (h->data);
 418     }
 419 }