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