gcc/tree-ssanames.c

   1 /* Generic routines for manipulating SSA_NAME expressions
   2    Copyright (C) 2003-2013 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
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License 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 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "tree.h"
  25 #include "tree-flow.h"
  26 #include "tree-pass.h"
  27
  28 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
  29    many of which may be thrown away shortly after their creation if jumps
  30    were threaded through PHI nodes.
  31
  32    While our garbage collection mechanisms will handle this situation, it
  33    is extremely wasteful to create nodes and throw them away, especially
  34    when the nodes can be reused.
  35
  36    For PR 8361, we can significantly reduce the number of nodes allocated
  37    and thus the total amount of memory allocated by managing SSA_NAMEs a
  38    little.  This additionally helps reduce the amount of work done by the
  39    garbage collector.  Similar results have been seen on a wider variety
  40    of tests (such as the compiler itself).
  41
  42    Right now we maintain our free list on a per-function basis.  It may
  43    or may not make sense to maintain the free list for the duration of
  44    a compilation unit.
  45
  46    External code should rely solely upon HIGHEST_SSA_VERSION and the
  47    externally defined functions.  External code should not know about
  48    the details of the free list management.
  49
  50    External code should also not assume the version number on nodes is
  51    monotonically increasing.  We reuse the version number when we
  52    reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
  53    more compact.  */
  54
  55
  56 /* Version numbers with special meanings.  We start allocating new version
  57    numbers after the special ones.  */
  58 #define UNUSED_NAME_VERSION 0
  59
  60 unsigned int ssa_name_nodes_reused;
  61 unsigned int ssa_name_nodes_created;
  62
  63 /* Initialize management of SSA_NAMEs to default SIZE.  If SIZE is
  64    zero use default.  */
  65
  66 void
  67 init_ssanames (struct function *fn, int size)
  68 {
  69   if (size < 50)
  70     size = 50;
  71
  72   vec_alloc (SSANAMES (fn), size);
  73
  74   /* Version 0 is special, so reserve the first slot in the table.  Though
  75      currently unused, we may use version 0 in alias analysis as part of
  76      the heuristics used to group aliases when the alias sets are too
  77      large.
  78
  79      We use vec::quick_push here because we know that SSA_NAMES has at
  80      least 50 elements reserved in it.  */
  81   SSANAMES (fn)->quick_push (NULL_TREE);
  82   FREE_SSANAMES (fn) = NULL;
  83
  84   fn->gimple_df->ssa_renaming_needed = 0;
  85   fn->gimple_df->rename_vops = 0;
  86 }
  87
  88 /* Finalize management of SSA_NAMEs.  */
  89
  90 void
  91 fini_ssanames (void)
  92 {
  93   vec_free (SSANAMES (cfun));
  94   vec_free (FREE_SSANAMES (cfun));
  95 }
  96
  97 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
  98
  99 void
 100 ssanames_print_statistics (void)
 101 {
 102   fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
 103   fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
 104 }
 105
 106 /* Return an SSA_NAME node for variable VAR defined in statement STMT
 107    in function FN.  STMT may be an empty statement for artificial
 108    references (e.g., default definitions created when a variable is
 109    used without a preceding definition).  */
 110
 111 tree
 112 make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
 113 {
 114   tree t;
 115   use_operand_p imm;
 116
 117   gcc_assert (TREE_CODE (var) == VAR_DECL
 118               || TREE_CODE (var) == PARM_DECL
 119               || TREE_CODE (var) == RESULT_DECL
 120               || (TYPE_P (var) && is_gimple_reg_type (var)));
 121
 122   /* If our free list has an element, then use it.  */
 123   if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
 124     {
 125       t = FREE_SSANAMES (fn)->pop ();
 126       if (GATHER_STATISTICS)
 127         ssa_name_nodes_reused++;
 128
 129       /* The node was cleared out when we put it on the free list, so
 130          there is no need to do so again here.  */
 131       gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
 132       (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
 133     }
 134   else
 135     {
 136       t = make_node (SSA_NAME);
 137       SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
 138       vec_safe_push (SSANAMES (fn), t);
 139       if (GATHER_STATISTICS)
 140         ssa_name_nodes_created++;
 141     }
 142
 143   if (TYPE_P (var))
 144     {
 145       TREE_TYPE (t) = var;
 146       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
 147     }
 148   else
 149     {
 150       TREE_TYPE (t) = TREE_TYPE (var);
 151       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
 152     }
 153   SSA_NAME_DEF_STMT (t) = stmt;
 154   SSA_NAME_PTR_INFO (t) = NULL;
 155   SSA_NAME_IN_FREE_LIST (t) = 0;
 156   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
 157   imm = &(SSA_NAME_IMM_USE_NODE (t));
 158   imm->use = NULL;
 159   imm->prev = imm;
 160   imm->next = imm;
 161   imm->loc.ssa_name = t;
 162
 163   return t;
 164 }
 165
 166
 167 /* We no longer need the SSA_NAME expression VAR, release it so that
 168    it may be reused.
 169
 170    Note it is assumed that no calls to make_ssa_name will be made
 171    until all uses of the ssa name are released and that the only
 172    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 173    other fields must be assumed clobbered.  */
 174
 175 void
 176 release_ssa_name (tree var)
 177 {
 178   if (!var)
 179     return;
 180
 181   /* Never release the default definition for a symbol.  It's a
 182      special SSA name that should always exist once it's created.  */
 183   if (SSA_NAME_IS_DEFAULT_DEF (var))
 184     return;
 185
 186   /* If VAR has been registered for SSA updating, don't remove it.
 187      After update_ssa has run, the name will be released.  */
 188   if (name_registered_for_update_p (var))
 189     {
 190       release_ssa_name_after_update_ssa (var);
 191       return;
 192     }
 193
 194   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 195      However, it should only end up on our free list one time.   We
 196      keep a status bit in the SSA_NAME node itself to indicate it has
 197      been put on the free list.
 198
 199      Note that once on the freelist you can not reference the SSA_NAME's
 200      defining statement.  */
 201   if (! SSA_NAME_IN_FREE_LIST (var))
 202     {
 203       tree saved_ssa_name_var = SSA_NAME_VAR (var);
 204       int saved_ssa_name_version = SSA_NAME_VERSION (var);
 205       use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
 206
 207       if (MAY_HAVE_DEBUG_STMTS)
 208         insert_debug_temp_for_var_def (NULL, var);
 209
 210 #ifdef ENABLE_CHECKING
 211       verify_imm_links (stderr, var);
 212 #endif
 213       while (imm->next != imm)
 214         delink_imm_use (imm->next);
 215
 216       (*SSANAMES (cfun))[SSA_NAME_VERSION (var)] = NULL_TREE;
 217       memset (var, 0, tree_size (var));
 218
 219       imm->prev = imm;
 220       imm->next = imm;
 221       imm->loc.ssa_name = var;
 222
 223       /* First put back the right tree node so that the tree checking
 224          macros do not complain.  */
 225       TREE_SET_CODE (var, SSA_NAME);
 226
 227       /* Restore the version number.  */
 228       SSA_NAME_VERSION (var) = saved_ssa_name_version;
 229
 230       /* Hopefully this can go away once we have the new incremental
 231          SSA updating code installed.  */
 232       SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
 233
 234       /* Note this SSA_NAME is now in the first list.  */
 235       SSA_NAME_IN_FREE_LIST (var) = 1;
 236
 237       /* And finally put it on the free list.  */
 238       vec_safe_push (FREE_SSANAMES (cfun), var);
 239     }
 240 }
 241
 242 /* If the alignment of the pointer described by PI is known, return true and
 243    store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
 244    respectively.  Otherwise return false.  */
 245
 246 bool
 247 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
 248                         unsigned int *misalignp)
 249 {
 250   if (pi->align)
 251     {
 252       *alignp = pi->align;
 253       *misalignp = pi->misalign;
 254       return true;
 255     }
 256   else
 257     return false;
 258 }
 259
 260 /* State that the pointer described by PI has unknown alignment.  */
 261
 262 void
 263 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
 264 {
 265   pi->align = 0;
 266   pi->misalign = 0;
 267 }
 268
 269 /* Store the the power-of-two byte alignment and the deviation from that
 270    alignment of pointer described by PI to ALIOGN and MISALIGN
 271    respectively.  */
 272
 273 void
 274 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
 275                             unsigned int misalign)
 276 {
 277   gcc_checking_assert (align != 0);
 278   gcc_assert ((align & (align - 1)) == 0);
 279   gcc_assert ((misalign & ~(align - 1)) == 0);
 280
 281   pi->align = align;
 282   pi->misalign = misalign;
 283 }
 284
 285 /* If pointer described by PI has known alignment, increase its known
 286    misalignment by INCREMENT modulo its current alignment.  */
 287
 288 void
 289 adjust_ptr_info_misalignment (struct ptr_info_def *pi,
 290                               unsigned int increment)
 291 {
 292   if (pi->align != 0)
 293     {
 294       pi->misalign += increment;
 295       pi->misalign &= (pi->align - 1);
 296     }
 297 }
 298
 299 /* Return the alias information associated with pointer T.  It creates a
 300    new instance if none existed.  */
 301
 302 struct ptr_info_def *
 303 get_ptr_info (tree t)
 304 {
 305   struct ptr_info_def *pi;
 306
 307   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 308
 309   pi = SSA_NAME_PTR_INFO (t);
 310   if (pi == NULL)
 311     {
 312       pi = ggc_alloc_cleared_ptr_info_def ();
 313       pt_solution_reset (&pi->pt);
 314       mark_ptr_info_alignment_unknown (pi);
 315       SSA_NAME_PTR_INFO (t) = pi;
 316     }
 317
 318   return pi;
 319 }
 320
 321
 322 /* Creates a new SSA name using the template NAME tobe defined by
 323    statement STMT in function FN.  */
 324
 325 tree
 326 copy_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 327 {
 328   tree new_name;
 329
 330   if (SSA_NAME_VAR (name))
 331     new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
 332   else
 333     {
 334       new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
 335       SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
 336     }
 337
 338   return new_name;
 339 }
 340
 341
 342 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
 343    the SSA name NAME.  */
 344
 345 void
 346 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
 347 {
 348   struct ptr_info_def *new_ptr_info;
 349
 350   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 351   gcc_assert (!SSA_NAME_PTR_INFO (name));
 352
 353   if (!ptr_info)
 354     return;
 355
 356   new_ptr_info = ggc_alloc_ptr_info_def ();
 357   *new_ptr_info = *ptr_info;
 358
 359   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 360 }
 361
 362
 363 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
 364    in function FN.  */
 365
 366 tree
 367 duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 368 {
 369   tree new_name = copy_ssa_name_fn (fn, name, stmt);
 370   struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 371
 372   if (old_ptr_info)
 373     duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
 374
 375   return new_name;
 376 }
 377
 378
 379 /* Release all the SSA_NAMEs created by STMT.  */
 380
 381 void
 382 release_defs (gimple stmt)
 383 {
 384   tree def;
 385   ssa_op_iter iter;
 386
 387   /* Make sure that we are in SSA.  Otherwise, operand cache may point
 388      to garbage.  */
 389   gcc_assert (gimple_in_ssa_p (cfun));
 390
 391   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 392     if (TREE_CODE (def) == SSA_NAME)
 393       release_ssa_name (def);
 394 }
 395
 396
 397 /* Replace the symbol associated with SSA_NAME with SYM.  */
 398
 399 void
 400 replace_ssa_name_symbol (tree ssa_name, tree sym)
 401 {
 402   SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
 403   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 404 }
 405
 406 /* Return SSA names that are unused to GGC memory and compact the SSA
 407    version namespace.  This is used to keep footprint of compiler during
 408    interprocedural optimization.  */
 409 static unsigned int
 410 release_dead_ssa_names (void)
 411 {
 412   unsigned i, j;
 413   int n = vec_safe_length (FREE_SSANAMES (cfun));
 414
 415   /* Now release the freelist.  */
 416   vec_free (FREE_SSANAMES (cfun));
 417
 418   /* And compact the SSA number space.  We make sure to not change the
 419      relative order of SSA versions.  */
 420   for (i = 1, j = 1; i < cfun->gimple_df->ssa_names->length (); ++i)
 421     {
 422       tree name = ssa_name (i);
 423       if (name)
 424         {
 425           if (i != j)
 426             {
 427               SSA_NAME_VERSION (name) = j;
 428               (*cfun->gimple_df->ssa_names)[j] = name;
 429             }
 430           j++;
 431         }
 432     }
 433   cfun->gimple_df->ssa_names->truncate (j);
 434
 435   statistics_counter_event (cfun, "SSA names released", n);
 436   statistics_counter_event (cfun, "SSA name holes removed", i - j);
 437   if (dump_file)
 438     fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
 439              n, n * 100.0 / num_ssa_names, i - j);
 440   return 0;
 441 }
 442
 443 struct gimple_opt_pass pass_release_ssa_names =
 444 {
 445  {
 446   GIMPLE_PASS,
 447   "release_ssa",                        /* name */
 448   OPTGROUP_NONE,                        /* optinfo_flags */
 449   NULL,                                 /* gate */
 450   release_dead_ssa_names,               /* execute */
 451   NULL,                                 /* sub */
 452   NULL,                                 /* next */
 453   0,                                    /* static_pass_number */
 454   TV_TREE_SSA_OTHER,                    /* tv_id */
 455   PROP_ssa,                             /* properties_required */
 456   0,                                    /* properties_provided */
 457   0,                                    /* properties_destroyed */
 458   TODO_remove_unused_locals,            /* todo_flags_start */
 459   0                                     /* todo_flags_finish */
 460  }
 461 };