gcc/stringpool.c

   1 /* String pool for GCC.
   2    Copyright (C) 2000-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 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 GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* String text, identifier text and identifier node allocator.
  21    Identifiers are uniquely stored in a hash table.
  22
  23    We use cpplib's hash table implementation.  libiberty's
  24    hashtab.c is not used because it requires 100% average space
  25    overhead per string, which is unacceptable.  Also, this algorithm
  26    is faster.  */
  27
  28 #include "config.h"
  29 #include "system.h"
  30 #include "coretypes.h"
  31 #include "ggc.h"
  32 #include "ggc-internal.h"
  33 #include "hash-set.h"
  34 #include "machmode.h"
  35 #include "vec.h"
  36 #include "double-int.h"
  37 #include "input.h"
  38 #include "alias.h"
  39 #include "symtab.h"
  40 #include "options.h"
  41 #include "wide-int.h"
  42 #include "inchash.h"
  43 #include "tree.h"
  44 #include "cpplib.h"
  45
  46 /* The "" allocated string.  */
  47 const char empty_string[] = "";
  48
  49 /* Character strings, each containing a single decimal digit.
  50    Written this way to save space.  */
  51 static const char digit_vector[] = {
  52   '0', 0, '1', 0, '2', 0, '3', 0, '4', 0,
  53   '5', 0, '6', 0, '7', 0, '8', 0, '9', 0
  54 };
  55
  56 #define digit_string(d) (digit_vector + ((d) * 2))
  57
  58 struct ht *ident_hash;
  59
  60 static hashnode alloc_node (cpp_hash_table *);
  61 static int mark_ident (struct cpp_reader *, hashnode, const void *);
  62
  63 static void *
  64 stringpool_ggc_alloc (size_t x)
  65 {
  66   return ggc_alloc_atomic (x);
  67 }
  68
  69 /* Initialize the string pool.  */
  70 void
  71 init_stringpool (void)
  72 {
  73   /* Clean up if we're called more than once.
  74      (We can't make this idempotent since identifiers contain state) */
  75   if (ident_hash)
  76     ht_destroy (ident_hash);
  77
  78   /* Create with 16K (2^14) entries.  */
  79   ident_hash = ht_create (14);
  80   ident_hash->alloc_node = alloc_node;
  81   ident_hash->alloc_subobject = stringpool_ggc_alloc;
  82 }
  83
  84 /* Allocate a hash node.  */
  85 static hashnode
  86 alloc_node (cpp_hash_table *table ATTRIBUTE_UNUSED)
  87 {
  88   return GCC_IDENT_TO_HT_IDENT (make_node (IDENTIFIER_NODE));
  89 }
  90
  91 /* Allocate and return a string constant of length LENGTH, containing
  92    CONTENTS.  If LENGTH is -1, CONTENTS is assumed to be a
  93    nul-terminated string, and the length is calculated using strlen.  */
  94
  95 const char *
  96 ggc_alloc_string (const char *contents, int length MEM_STAT_DECL)
  97 {
  98   char *result;
  99
 100   if (length == -1)
 101     length = strlen (contents);
 102
 103   if (length == 0)
 104     return empty_string;
 105   if (length == 1 && ISDIGIT (contents[0]))
 106     return digit_string (contents[0] - '0');
 107
 108   result = (char *) ggc_internal_cleared_alloc (length + 1 PASS_MEM_STAT);
 109   memcpy (result, contents, length);
 110   result[length] = '\0';
 111   return (const char *) result;
 112 }
 113
 114 /* Return an IDENTIFIER_NODE whose name is TEXT (a null-terminated string).
 115    If an identifier with that name has previously been referred to,
 116    the same node is returned this time.  */
 117
 118 #undef get_identifier
 119
 120 tree
 121 get_identifier (const char *text)
 122 {
 123   hashnode ht_node = ht_lookup (ident_hash,
 124                                 (const unsigned char *) text,
 125                                 strlen (text), HT_ALLOC);
 126
 127   /* ht_node can't be NULL here.  */
 128   return HT_IDENT_TO_GCC_IDENT (ht_node);
 129 }
 130
 131 /* Identical to get_identifier, except that the length is assumed
 132    known.  */
 133
 134 tree
 135 get_identifier_with_length (const char *text, size_t length)
 136 {
 137   hashnode ht_node = ht_lookup (ident_hash,
 138                                 (const unsigned char *) text,
 139                                 length, HT_ALLOC);
 140
 141   /* ht_node can't be NULL here.  */
 142   return HT_IDENT_TO_GCC_IDENT (ht_node);
 143 }
 144
 145 /* If an identifier with the name TEXT (a null-terminated string) has
 146    previously been referred to, return that node; otherwise return
 147    NULL_TREE.  */
 148
 149 tree
 150 maybe_get_identifier (const char *text)
 151 {
 152   hashnode ht_node;
 153
 154   ht_node = ht_lookup (ident_hash, (const unsigned char *) text,
 155                        strlen (text), HT_NO_INSERT);
 156   if (ht_node)
 157     return HT_IDENT_TO_GCC_IDENT (ht_node);
 158
 159   return NULL_TREE;
 160 }
 161
 162 /* Report some basic statistics about the string pool.  */
 163
 164 void
 165 stringpool_statistics (void)
 166 {
 167   ht_dump_statistics (ident_hash);
 168 }
 169 \f
 170 /* Mark an identifier for GC.  */
 171
 172 static int
 173 mark_ident (struct cpp_reader *pfile ATTRIBUTE_UNUSED, hashnode h,
 174             const void *v ATTRIBUTE_UNUSED)
 175 {
 176   gt_ggc_m_9tree_node (HT_IDENT_TO_GCC_IDENT (h));
 177   return 1;
 178 }
 179
 180 /* Return true if an identifier should be removed from the table.  */
 181
 182 static int
 183 maybe_delete_ident (struct cpp_reader *pfile ATTRIBUTE_UNUSED, hashnode h,
 184                     const void *v ATTRIBUTE_UNUSED)
 185 {
 186   return !ggc_marked_p (HT_IDENT_TO_GCC_IDENT (h));
 187 }
 188
 189 /* Mark the trees hanging off the identifier node for GGC.  These are
 190    handled specially (not using gengtype) because identifiers are only
 191    roots during one part of compilation.  */
 192
 193 void
 194 ggc_mark_stringpool (void)
 195 {
 196   ht_forall (ident_hash, mark_ident, NULL);
 197 }
 198
 199 /* Purge the identifier hash of identifiers which are no longer
 200    referenced.  */
 201
 202 void
 203 ggc_purge_stringpool (void)
 204 {
 205   ht_purge (ident_hash, maybe_delete_ident, NULL);
 206 }
 207
 208 /* Pointer-walking routine for strings (not very interesting, since
 209    strings don't contain pointers).  */
 210
 211 void
 212 gt_pch_p_S (void *obj ATTRIBUTE_UNUSED, void *x ATTRIBUTE_UNUSED,
 213             gt_pointer_operator op ATTRIBUTE_UNUSED,
 214             void *cookie ATTRIBUTE_UNUSED)
 215 {
 216 }
 217
 218 /* PCH pointer-walking routine for strings.  */
 219
 220 void
 221 gt_pch_n_S (const void *x)
 222 {
 223   gt_pch_note_object (CONST_CAST (void *, x), CONST_CAST (void *, x),
 224                       &gt_pch_p_S);
 225 }
 226
 227
 228 /* User-callable entry point for marking string X.  */
 229
 230 void
 231 gt_pch_nx (const char *& x)
 232 {
 233   gt_pch_n_S (x);
 234 }
 235
 236 void
 237 gt_pch_nx (unsigned char *& x)
 238 {
 239   gt_pch_n_S (x);
 240 }
 241
 242 void
 243 gt_pch_nx (unsigned char& x ATTRIBUTE_UNUSED)
 244 {
 245 }
 246
 247 void
 248 gt_pch_nx (unsigned char *x, gt_pointer_operator op, void *cookie)
 249 {
 250   op (x, cookie);
 251 }
 252 \f
 253 /* Handle saving and restoring the string pool for PCH.  */
 254
 255 /* SPD is saved in the PCH file and holds the information needed
 256    to restore the string pool.  */
 257
 258 struct GTY(()) string_pool_data {
 259   ht_identifier_ptr *
 260     GTY((length ("%h.nslots"),
 261          nested_ptr (union tree_node, "%h ? GCC_IDENT_TO_HT_IDENT (%h) : NULL",
 262                      "%h ? HT_IDENT_TO_GCC_IDENT (%h) : NULL")))
 263     entries;
 264   unsigned int nslots;
 265   unsigned int nelements;
 266 };
 267
 268 static GTY(()) struct string_pool_data * spd;
 269
 270 /* Save the stringpool data in SPD.  */
 271
 272 void
 273 gt_pch_save_stringpool (void)
 274 {
 275   spd = ggc_alloc<string_pool_data> ();
 276   spd->nslots = ident_hash->nslots;
 277   spd->nelements = ident_hash->nelements;
 278   spd->entries = ggc_vec_alloc<ht_identifier_ptr> (spd->nslots);
 279   memcpy (spd->entries, ident_hash->entries,
 280           spd->nslots * sizeof (spd->entries[0]));
 281 }
 282
 283 /* Return the stringpool to its state before gt_pch_save_stringpool
 284    was called.  */
 285
 286 void
 287 gt_pch_fixup_stringpool (void)
 288 {
 289 }
 290
 291 /* A PCH file has been restored, which loaded SPD; fill the real hash table
 292    from SPD.  */
 293
 294 void
 295 gt_pch_restore_stringpool (void)
 296 {
 297   ht_load (ident_hash, spd->entries, spd->nslots, spd->nelements, false);
 298   spd = NULL;
 299 }
 300
 301 #include "gt-stringpool.h"