1 /* Miscellaneous utilities for tree streaming. Things that are used
2 in both input and output are here.
3
4 Copyright (C) 2011-2014 Free Software Foundation, Inc.
5 Contributed by Diego Novillo <dnovillo@google.com>
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tree.h"
27 #include "basic-block.h"
28 #include "tree-ssa-alias.h"
29 #include "internal-fn.h"
30 #include "gimple-expr.h"
31 #include "is-a.h"
32 #include "gimple.h"
33 #include "streamer-hooks.h"
34 #include "tree-streamer.h"
35
36 /* Check that all the TS_* structures handled by the streamer_write_* and
37 streamer_read_* routines are exactly ALL the structures defined in
38 treestruct.def. */
39
40 void
streamer_check_handled_ts_structures(void)41 streamer_check_handled_ts_structures (void)
42 {
43 bool handled_p[LAST_TS_ENUM];
44 unsigned i;
45
46 memset (&handled_p, 0, sizeof (handled_p));
47
48 /* These are the TS_* structures that are either handled or
49 explicitly ignored by the streamer routines. */
50 handled_p[TS_BASE] = true;
51 handled_p[TS_TYPED] = true;
52 handled_p[TS_COMMON] = true;
53 handled_p[TS_INT_CST] = true;
54 handled_p[TS_REAL_CST] = true;
55 handled_p[TS_FIXED_CST] = true;
56 handled_p[TS_VECTOR] = true;
57 handled_p[TS_STRING] = true;
58 handled_p[TS_COMPLEX] = true;
59 handled_p[TS_IDENTIFIER] = true;
60 handled_p[TS_DECL_MINIMAL] = true;
61 handled_p[TS_DECL_COMMON] = true;
62 handled_p[TS_DECL_WRTL] = true;
63 handled_p[TS_DECL_NON_COMMON] = true;
64 handled_p[TS_DECL_WITH_VIS] = true;
65 handled_p[TS_FIELD_DECL] = true;
66 handled_p[TS_VAR_DECL] = true;
67 handled_p[TS_PARM_DECL] = true;
68 handled_p[TS_LABEL_DECL] = true;
69 handled_p[TS_RESULT_DECL] = true;
70 handled_p[TS_CONST_DECL] = true;
71 handled_p[TS_TYPE_DECL] = true;
72 handled_p[TS_FUNCTION_DECL] = true;
73 handled_p[TS_TYPE_COMMON] = true;
74 handled_p[TS_TYPE_WITH_LANG_SPECIFIC] = true;
75 handled_p[TS_TYPE_NON_COMMON] = true;
76 handled_p[TS_LIST] = true;
77 handled_p[TS_VEC] = true;
78 handled_p[TS_EXP] = true;
79 handled_p[TS_SSA_NAME] = true;
80 handled_p[TS_BLOCK] = true;
81 handled_p[TS_BINFO] = true;
82 handled_p[TS_STATEMENT_LIST] = true;
83 handled_p[TS_CONSTRUCTOR] = true;
84 handled_p[TS_OMP_CLAUSE] = true;
85 handled_p[TS_OPTIMIZATION] = true;
86 handled_p[TS_TARGET_OPTION] = true;
87 handled_p[TS_TRANSLATION_UNIT_DECL] = true;
88
89 /* Anything not marked above will trigger the following assertion.
90 If this assertion triggers, it means that there is a new TS_*
91 structure that should be handled by the streamer. */
92 for (i = 0; i < LAST_TS_ENUM; i++)
93 gcc_assert (handled_p[i]);
94 }
95
96
97 /* Helper for streamer_tree_cache_insert_1. Add T to CACHE->NODES at
98 slot IX. */
99
100 static void
streamer_tree_cache_add_to_node_array(struct streamer_tree_cache_d * cache,unsigned ix,tree t,hashval_t hash)101 streamer_tree_cache_add_to_node_array (struct streamer_tree_cache_d *cache,
102 unsigned ix, tree t, hashval_t hash)
103 {
104 /* We're either replacing an old element or appending consecutively. */
105 if (cache->nodes.exists ())
106 {
107 if (cache->nodes.length () == ix)
108 cache->nodes.safe_push (t);
109 else
110 cache->nodes[ix] = t;
111 }
112 if (cache->hashes.exists ())
113 {
114 if (cache->hashes.length () == ix)
115 cache->hashes.safe_push (hash);
116 else
117 cache->hashes[ix] = hash;
118 }
119 }
120
121
122 /* Helper for streamer_tree_cache_insert and streamer_tree_cache_insert_at.
123 CACHE, T, and IX_P are as in streamer_tree_cache_insert.
124
125 If INSERT_AT_NEXT_SLOT_P is true, T is inserted at the next available
126 slot in the cache. Otherwise, T is inserted at the position indicated
127 in *IX_P.
128
129 If T already existed in CACHE, return true. Otherwise,
130 return false. */
131
132 static bool
streamer_tree_cache_insert_1(struct streamer_tree_cache_d * cache,tree t,hashval_t hash,unsigned * ix_p,bool insert_at_next_slot_p)133 streamer_tree_cache_insert_1 (struct streamer_tree_cache_d *cache,
134 tree t, hashval_t hash, unsigned *ix_p,
135 bool insert_at_next_slot_p)
136 {
137 unsigned *slot;
138 unsigned ix;
139 bool existed_p;
140
141 gcc_assert (t);
142
143 slot = cache->node_map->insert (t, &existed_p);
144 if (!existed_p)
145 {
146 /* Determine the next slot to use in the cache. */
147 if (insert_at_next_slot_p)
148 ix = cache->next_idx++;
149 else
150 ix = *ix_p;
151 *slot = ix;
152
153 streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
154 }
155 else
156 {
157 ix = *slot;
158
159 if (!insert_at_next_slot_p && ix != *ix_p)
160 {
161 /* If the caller wants to insert T at a specific slot
162 location, and ENTRY->TO does not match *IX_P, add T to
163 the requested location slot. */
164 ix = *ix_p;
165 streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
166 *slot = ix;
167 }
168 }
169
170 if (ix_p)
171 *ix_p = ix;
172
173 return existed_p;
174 }
175
176
177 /* Insert tree node T in CACHE. If T already existed in the cache
178 return true. Otherwise, return false.
179
180 If IX_P is non-null, update it with the index into the cache where
181 T has been stored. */
182
183 bool
streamer_tree_cache_insert(struct streamer_tree_cache_d * cache,tree t,hashval_t hash,unsigned * ix_p)184 streamer_tree_cache_insert (struct streamer_tree_cache_d *cache, tree t,
185 hashval_t hash, unsigned *ix_p)
186 {
187 return streamer_tree_cache_insert_1 (cache, t, hash, ix_p, true);
188 }
189
190
191 /* Replace the tree node with T in CACHE at slot IX. */
192
193 void
streamer_tree_cache_replace_tree(struct streamer_tree_cache_d * cache,tree t,unsigned ix)194 streamer_tree_cache_replace_tree (struct streamer_tree_cache_d *cache,
195 tree t, unsigned ix)
196 {
197 hashval_t hash = 0;
198 if (cache->hashes.exists ())
199 hash = streamer_tree_cache_get_hash (cache, ix);
200 if (!cache->node_map)
201 streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
202 else
203 streamer_tree_cache_insert_1 (cache, t, hash, &ix, false);
204 }
205
206
207 /* Appends tree node T to CACHE, even if T already existed in it. */
208
209 void
streamer_tree_cache_append(struct streamer_tree_cache_d * cache,tree t,hashval_t hash)210 streamer_tree_cache_append (struct streamer_tree_cache_d *cache,
211 tree t, hashval_t hash)
212 {
213 unsigned ix = cache->next_idx++;
214 if (!cache->node_map)
215 streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
216 else
217 streamer_tree_cache_insert_1 (cache, t, hash, &ix, false);
218 }
219
220 /* Return true if tree node T exists in CACHE, otherwise false. If IX_P is
221 not NULL, write to *IX_P the index into the cache where T is stored
222 ((unsigned)-1 if T is not found). */
223
224 bool
streamer_tree_cache_lookup(struct streamer_tree_cache_d * cache,tree t,unsigned * ix_p)225 streamer_tree_cache_lookup (struct streamer_tree_cache_d *cache, tree t,
226 unsigned *ix_p)
227 {
228 unsigned *slot;
229 bool retval;
230 unsigned ix;
231
232 gcc_assert (t);
233
234 slot = cache->node_map->contains (t);
235 if (slot == NULL)
236 {
237 retval = false;
238 ix = -1;
239 }
240 else
241 {
242 retval = true;
243 ix = *slot;
244 }
245
246 if (ix_p)
247 *ix_p = ix;
248
249 return retval;
250 }
251
252
253 /* Record NODE in CACHE. */
254
255 static void
record_common_node(struct streamer_tree_cache_d * cache,tree node)256 record_common_node (struct streamer_tree_cache_d *cache, tree node)
257 {
258 /* If we recursively end up at nodes we do not want to preload simply don't.
259 ??? We'd want to verify that this doesn't happen, or alternatively
260 do not recurse at all. */
261 if (node == char_type_node)
262 return;
263
264 gcc_checking_assert (node != boolean_type_node
265 && node != boolean_true_node
266 && node != boolean_false_node);
267
268 /* We have to make sure to fill exactly the same number of
269 elements for all frontends. That can include NULL trees.
270 As our hash table can't deal with zero entries we'll simply stream
271 a random other tree. A NULL tree never will be looked up so it
272 doesn't matter which tree we replace it with, just to be sure
273 use error_mark_node. */
274 if (!node)
275 node = error_mark_node;
276
277 /* ??? FIXME, devise a better hash value. But the hash needs to be equal
278 for all frontend and lto1 invocations. So just use the position
279 in the cache as hash value. */
280 streamer_tree_cache_append (cache, node, cache->nodes.length ());
281
282 if (POINTER_TYPE_P (node)
283 || TREE_CODE (node) == COMPLEX_TYPE
284 || TREE_CODE (node) == ARRAY_TYPE)
285 record_common_node (cache, TREE_TYPE (node));
286 else if (TREE_CODE (node) == RECORD_TYPE)
287 {
288 /* The FIELD_DECLs of structures should be shared, so that every
289 COMPONENT_REF uses the same tree node when referencing a field.
290 Pointer equality between FIELD_DECLs is used by the alias
291 machinery to compute overlapping component references (see
292 nonoverlapping_component_refs_p and
293 nonoverlapping_component_refs_of_decl_p). */
294 for (tree f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f))
295 record_common_node (cache, f);
296 }
297 }
298
299
300 /* Preload common nodes into CACHE and make sure they are merged
301 properly according to the gimple type table. */
302
303 static void
preload_common_nodes(struct streamer_tree_cache_d * cache)304 preload_common_nodes (struct streamer_tree_cache_d *cache)
305 {
306 unsigned i;
307
308 for (i = 0; i < itk_none; i++)
309 /* Skip itk_char. char_type_node is dependent on -f[un]signed-char. */
310 if (i != itk_char)
311 record_common_node (cache, integer_types[i]);
312
313 for (i = 0; i < stk_type_kind_last; i++)
314 record_common_node (cache, sizetype_tab[i]);
315
316 for (i = 0; i < TI_MAX; i++)
317 /* Skip boolean type and constants, they are frontend dependent. */
318 if (i != TI_BOOLEAN_TYPE
319 && i != TI_BOOLEAN_FALSE
320 && i != TI_BOOLEAN_TRUE)
321 record_common_node (cache, global_trees[i]);
322 }
323
324
325 /* Create a cache of pickled nodes. */
326
327 struct streamer_tree_cache_d *
streamer_tree_cache_create(bool with_hashes,bool with_map,bool with_vec)328 streamer_tree_cache_create (bool with_hashes, bool with_map, bool with_vec)
329 {
330 struct streamer_tree_cache_d *cache;
331
332 cache = XCNEW (struct streamer_tree_cache_d);
333
334 if (with_map)
335 cache->node_map = new pointer_map<unsigned>;
336 cache->next_idx = 0;
337 if (with_vec)
338 cache->nodes.create (165);
339 if (with_hashes)
340 cache->hashes.create (165);
341
342 /* Load all the well-known tree nodes that are always created by
343 the compiler on startup. This prevents writing them out
344 unnecessarily. */
345 preload_common_nodes (cache);
346
347 return cache;
348 }
349
350
351 /* Delete the streamer cache C. */
352
353 void
streamer_tree_cache_delete(struct streamer_tree_cache_d * c)354 streamer_tree_cache_delete (struct streamer_tree_cache_d *c)
355 {
356 if (c == NULL)
357 return;
358
359 if (c->node_map)
360 delete c->node_map;
361 c->nodes.release ();
362 c->hashes.release ();
363 free (c);
364 }
365