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 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 >_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 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" 302