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 "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
  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
 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
 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
 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
 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
 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
 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
 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
 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 *
 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
 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 }