1/* String pool for GCC. 2 Copyright (C) 2000-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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. */ 47const char empty_string[] = ""; 48 49/* Character strings, each containing a single decimal digit. 50 Written this way to save space. */ 51static 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 58struct ht *ident_hash; 59 60static hashnode alloc_node (cpp_hash_table *); 61static int mark_ident (struct cpp_reader *, hashnode, const void *); 62 63static void * 64stringpool_ggc_alloc (size_t x) 65{ 66 return ggc_alloc_atomic (x); 67} 68 69/* Initialize the string pool. */ 70void 71init_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. */ 85static hashnode 86alloc_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 95const char * 96ggc_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 120tree 121get_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 134tree 135get_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 149tree 150maybe_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 164void 165stringpool_statistics (void) 166{ 167 ht_dump_statistics (ident_hash); 168} 169 170/* Mark an identifier for GC. */ 171 172static int 173mark_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 182static int 183maybe_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 193void 194ggc_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 202void 203ggc_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 211void 212gt_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 220void 221gt_pch_n_S (const void *x) 222{ 223 gt_pch_note_object (CONST_CAST (void *, x), CONST_CAST (void *, x), 224 >_pch_p_S); 225} 226 227 228/* User-callable entry point for marking string X. */ 229 230void 231gt_pch_nx (const char *& x) 232{ 233 gt_pch_n_S (x); 234} 235 236void 237gt_pch_nx (unsigned char *& x) 238{ 239 gt_pch_n_S (x); 240} 241 242void 243gt_pch_nx (unsigned char& x ATTRIBUTE_UNUSED) 244{ 245} 246 247void 248gt_pch_nx (unsigned char *x, gt_pointer_operator op, void *cookie) 249{ 250 op (x, cookie); 251} 252 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 258struct 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 268static GTY(()) struct string_pool_data * spd; 269 270/* Save the stringpool data in SPD. */ 271 272void 273gt_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 286void 287gt_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 294void 295gt_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" 302