gcc/tree-streamer.c

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