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 "gimple.h"
  26 #include "gimple-ssa.h"
  27 #include "tree-phinodes.h"
  28 #include "ssa-iterators.h"
  29 #include "tree-ssanames.h"
  30 #include "tree-into-ssa.h"
  31 #include "tree-ssa.h"
  32 #include "tree-pass.h"
  33
  34 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
  35    many of which may be thrown away shortly after their creation if jumps
  36    were threaded through PHI nodes.
  37
  38    While our garbage collection mechanisms will handle this situation, it
  39    is extremely wasteful to create nodes and throw them away, especially
  40    when the nodes can be reused.
  41
  42    For PR 8361, we can significantly reduce the number of nodes allocated
  43    and thus the total amount of memory allocated by managing SSA_NAMEs a
  44    little.  This additionally helps reduce the amount of work done by the
  45    garbage collector.  Similar results have been seen on a wider variety
  46    of tests (such as the compiler itself).
  47
  48    Right now we maintain our free list on a per-function basis.  It may
  49    or may not make sense to maintain the free list for the duration of
  50    a compilation unit.
  51
  52    External code should rely solely upon HIGHEST_SSA_VERSION and the
  53    externally defined functions.  External code should not know about
  54    the details of the free list management.
  55
  56    External code should also not assume the version number on nodes is
  57    monotonically increasing.  We reuse the version number when we
  58    reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
  59    more compact.  */
  60
  61
  62 /* Version numbers with special meanings.  We start allocating new version
  63    numbers after the special ones.  */
  64 #define UNUSED_NAME_VERSION 0
  65
  66 unsigned int ssa_name_nodes_reused;
  67 unsigned int ssa_name_nodes_created;
  68
  69 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
  70
  71
  72 /* Initialize management of SSA_NAMEs to default SIZE.  If SIZE is
  73    zero use default.  */
  74
  75 void
  76 init_ssanames (struct function *fn, int size)
  77 {
  78   if (size < 50)
  79     size = 50;
  80
  81   vec_alloc (SSANAMES (fn), size);
  82
  83   /* Version 0 is special, so reserve the first slot in the table.  Though
  84      currently unused, we may use version 0 in alias analysis as part of
  85      the heuristics used to group aliases when the alias sets are too
  86      large.
  87
  88      We use vec::quick_push here because we know that SSA_NAMES has at
  89      least 50 elements reserved in it.  */
  90   SSANAMES (fn)->quick_push (NULL_TREE);
  91   FREE_SSANAMES (fn) = NULL;
  92
  93   fn->gimple_df->ssa_renaming_needed = 0;
  94   fn->gimple_df->rename_vops = 0;
  95 }
  96
  97 /* Finalize management of SSA_NAMEs.  */
  98
  99 void
 100 fini_ssanames (void)
 101 {
 102   vec_free (SSANAMES (cfun));
 103   vec_free (FREE_SSANAMES (cfun));
 104 }
 105
 106 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
 107
 108 void
 109 ssanames_print_statistics (void)
 110 {
 111   fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
 112   fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
 113 }
 114
 115 /* Return an SSA_NAME node for variable VAR defined in statement STMT
 116    in function FN.  STMT may be an empty statement for artificial
 117    references (e.g., default definitions created when a variable is
 118    used without a preceding definition).  */
 119
 120 tree
 121 make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
 122 {
 123   tree t;
 124   use_operand_p imm;
 125
 126   gcc_assert (TREE_CODE (var) == VAR_DECL
 127               || TREE_CODE (var) == PARM_DECL
 128               || TREE_CODE (var) == RESULT_DECL
 129               || (TYPE_P (var) && is_gimple_reg_type (var)));
 130
 131   /* If our free list has an element, then use it.  */
 132   if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
 133     {
 134       t = FREE_SSANAMES (fn)->pop ();
 135       if (GATHER_STATISTICS)
 136         ssa_name_nodes_reused++;
 137
 138       /* The node was cleared out when we put it on the free list, so
 139          there is no need to do so again here.  */
 140       gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
 141       (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
 142     }
 143   else
 144     {
 145       t = make_node (SSA_NAME);
 146       SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
 147       vec_safe_push (SSANAMES (fn), t);
 148       if (GATHER_STATISTICS)
 149         ssa_name_nodes_created++;
 150     }
 151
 152   if (TYPE_P (var))
 153     {
 154       TREE_TYPE (t) = var;
 155       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
 156     }
 157   else
 158     {
 159       TREE_TYPE (t) = TREE_TYPE (var);
 160       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
 161     }
 162   SSA_NAME_DEF_STMT (t) = stmt;
 163   if (POINTER_TYPE_P (TREE_TYPE (t)))
 164     SSA_NAME_PTR_INFO (t) = NULL;
 165   else
 166     SSA_NAME_RANGE_INFO (t) = NULL;
 167
 168   SSA_NAME_IN_FREE_LIST (t) = 0;
 169   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
 170   imm = &(SSA_NAME_IMM_USE_NODE (t));
 171   imm->use = NULL;
 172   imm->prev = imm;
 173   imm->next = imm;
 174   imm->loc.ssa_name = t;
 175
 176   return t;
 177 }
 178
 179 /* Store range information MIN, and MAX to tree ssa_name NAME.  */
 180
 181 void
 182 set_range_info (tree name, double_int min, double_int max)
 183 {
 184   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 185   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 186
 187   /* Allocate if not available.  */
 188   if (ri == NULL)
 189     {
 190       ri = ggc_alloc_cleared_range_info_def ();
 191       SSA_NAME_RANGE_INFO (name) = ri;
 192     }
 193
 194   /* Set the values.  */
 195   ri->min = min;
 196   ri->max = max;
 197 }
 198
 199
 200 /* Gets range information MIN, MAX and returns enum value_range_type
 201    corresponding to tree ssa_name NAME.  enum value_range_type returned
 202    is used to determine if MIN and MAX are valid values.  */
 203
 204 enum value_range_type
 205 get_range_info (tree name, double_int *min, double_int *max)
 206 {
 207   enum value_range_type range_type;
 208   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 209   gcc_assert (min && max);
 210   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 211
 212   /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
 213      with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.  */
 214   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 215               > 2 * HOST_BITS_PER_WIDE_INT))
 216     return VR_VARYING;
 217
 218   /* If min > max, it is VR_ANTI_RANGE.  */
 219   if (ri->min.cmp (ri->max, TYPE_UNSIGNED (TREE_TYPE (name))) == 1)
 220     {
 221       /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1].  */
 222       range_type = VR_ANTI_RANGE;
 223       *min = ri->max + double_int_one;
 224       *max = ri->min - double_int_one;
 225     }
 226   else
 227   {
 228     /* Otherwise (when min <= max), it is VR_RANGE.  */
 229     range_type = VR_RANGE;
 230     *min = ri->min;
 231     *max = ri->max;
 232   }
 233   return range_type;
 234 }
 235
 236 /* We no longer need the SSA_NAME expression VAR, release it so that
 237    it may be reused.
 238
 239    Note it is assumed that no calls to make_ssa_name will be made
 240    until all uses of the ssa name are released and that the only
 241    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 242    other fields must be assumed clobbered.  */
 243
 244 void
 245 release_ssa_name (tree var)
 246 {
 247   if (!var)
 248     return;
 249
 250   /* Never release the default definition for a symbol.  It's a
 251      special SSA name that should always exist once it's created.  */
 252   if (SSA_NAME_IS_DEFAULT_DEF (var))
 253     return;
 254
 255   /* If VAR has been registered for SSA updating, don't remove it.
 256      After update_ssa has run, the name will be released.  */
 257   if (name_registered_for_update_p (var))
 258     {
 259       release_ssa_name_after_update_ssa (var);
 260       return;
 261     }
 262
 263   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 264      However, it should only end up on our free list one time.   We
 265      keep a status bit in the SSA_NAME node itself to indicate it has
 266      been put on the free list.
 267
 268      Note that once on the freelist you can not reference the SSA_NAME's
 269      defining statement.  */
 270   if (! SSA_NAME_IN_FREE_LIST (var))
 271     {
 272       tree saved_ssa_name_var = SSA_NAME_VAR (var);
 273       int saved_ssa_name_version = SSA_NAME_VERSION (var);
 274       use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
 275
 276       if (MAY_HAVE_DEBUG_STMTS)
 277         insert_debug_temp_for_var_def (NULL, var);
 278
 279 #ifdef ENABLE_CHECKING
 280       verify_imm_links (stderr, var);
 281 #endif
 282       while (imm->next != imm)
 283         delink_imm_use (imm->next);
 284
 285       (*SSANAMES (cfun))[SSA_NAME_VERSION (var)] = NULL_TREE;
 286       memset (var, 0, tree_size (var));
 287
 288       imm->prev = imm;
 289       imm->next = imm;
 290       imm->loc.ssa_name = var;
 291
 292       /* First put back the right tree node so that the tree checking
 293          macros do not complain.  */
 294       TREE_SET_CODE (var, SSA_NAME);
 295
 296       /* Restore the version number.  */
 297       SSA_NAME_VERSION (var) = saved_ssa_name_version;
 298
 299       /* Hopefully this can go away once we have the new incremental
 300          SSA updating code installed.  */
 301       SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
 302
 303       /* Note this SSA_NAME is now in the first list.  */
 304       SSA_NAME_IN_FREE_LIST (var) = 1;
 305
 306       /* And finally put it on the free list.  */
 307       vec_safe_push (FREE_SSANAMES (cfun), var);
 308     }
 309 }
 310
 311 /* If the alignment of the pointer described by PI is known, return true and
 312    store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
 313    respectively.  Otherwise return false.  */
 314
 315 bool
 316 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
 317                         unsigned int *misalignp)
 318 {
 319   if (pi->align)
 320     {
 321       *alignp = pi->align;
 322       *misalignp = pi->misalign;
 323       return true;
 324     }
 325   else
 326     return false;
 327 }
 328
 329 /* State that the pointer described by PI has unknown alignment.  */
 330
 331 void
 332 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
 333 {
 334   pi->align = 0;
 335   pi->misalign = 0;
 336 }
 337
 338 /* Store the the power-of-two byte alignment and the deviation from that
 339    alignment of pointer described by PI to ALIOGN and MISALIGN
 340    respectively.  */
 341
 342 void
 343 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
 344                             unsigned int misalign)
 345 {
 346   gcc_checking_assert (align != 0);
 347   gcc_assert ((align & (align - 1)) == 0);
 348   gcc_assert ((misalign & ~(align - 1)) == 0);
 349
 350   pi->align = align;
 351   pi->misalign = misalign;
 352 }
 353
 354 /* If pointer described by PI has known alignment, increase its known
 355    misalignment by INCREMENT modulo its current alignment.  */
 356
 357 void
 358 adjust_ptr_info_misalignment (struct ptr_info_def *pi,
 359                               unsigned int increment)
 360 {
 361   if (pi->align != 0)
 362     {
 363       pi->misalign += increment;
 364       pi->misalign &= (pi->align - 1);
 365     }
 366 }
 367
 368 /* Return the alias information associated with pointer T.  It creates a
 369    new instance if none existed.  */
 370
 371 struct ptr_info_def *
 372 get_ptr_info (tree t)
 373 {
 374   struct ptr_info_def *pi;
 375
 376   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 377
 378   pi = SSA_NAME_PTR_INFO (t);
 379   if (pi == NULL)
 380     {
 381       pi = ggc_alloc_cleared_ptr_info_def ();
 382       pt_solution_reset (&pi->pt);
 383       mark_ptr_info_alignment_unknown (pi);
 384       SSA_NAME_PTR_INFO (t) = pi;
 385     }
 386
 387   return pi;
 388 }
 389
 390
 391 /* Creates a new SSA name using the template NAME tobe defined by
 392    statement STMT in function FN.  */
 393
 394 tree
 395 copy_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 396 {
 397   tree new_name;
 398
 399   if (SSA_NAME_VAR (name))
 400     new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
 401   else
 402     {
 403       new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
 404       SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
 405     }
 406
 407   return new_name;
 408 }
 409
 410
 411 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
 412    the SSA name NAME.  */
 413
 414 void
 415 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
 416 {
 417   struct ptr_info_def *new_ptr_info;
 418
 419   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 420   gcc_assert (!SSA_NAME_PTR_INFO (name));
 421
 422   if (!ptr_info)
 423     return;
 424
 425   new_ptr_info = ggc_alloc_ptr_info_def ();
 426   *new_ptr_info = *ptr_info;
 427
 428   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 429 }
 430
 431 /* Creates a duplicate of the range_info_def at RANGE_INFO for use by
 432    the SSA name NAME.  */
 433 void
 434 duplicate_ssa_name_range_info (tree name, struct range_info_def *range_info)
 435 {
 436   struct range_info_def *new_range_info;
 437
 438   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 439   gcc_assert (!SSA_NAME_RANGE_INFO (name));
 440
 441   if (!range_info)
 442     return;
 443
 444   new_range_info = ggc_alloc_range_info_def ();
 445   *new_range_info = *range_info;
 446
 447   SSA_NAME_RANGE_INFO (name) = new_range_info;
 448 }
 449
 450
 451
 452 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
 453    in function FN.  */
 454
 455 tree
 456 duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 457 {
 458   tree new_name = copy_ssa_name_fn (fn, name, stmt);
 459   if (POINTER_TYPE_P (TREE_TYPE (name)))
 460     {
 461       struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 462
 463       if (old_ptr_info)
 464         duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
 465     }
 466   else
 467     {
 468       struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 469
 470       if (old_range_info)
 471         duplicate_ssa_name_range_info (new_name, old_range_info);
 472     }
 473
 474   return new_name;
 475 }
 476
 477
 478 /* Release all the SSA_NAMEs created by STMT.  */
 479
 480 void
 481 release_defs (gimple stmt)
 482 {
 483   tree def;
 484   ssa_op_iter iter;
 485
 486   /* Make sure that we are in SSA.  Otherwise, operand cache may point
 487      to garbage.  */
 488   gcc_assert (gimple_in_ssa_p (cfun));
 489
 490   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 491     if (TREE_CODE (def) == SSA_NAME)
 492       release_ssa_name (def);
 493 }
 494
 495
 496 /* Replace the symbol associated with SSA_NAME with SYM.  */
 497
 498 void
 499 replace_ssa_name_symbol (tree ssa_name, tree sym)
 500 {
 501   SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
 502   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 503 }
 504
 505 /* Return SSA names that are unused to GGC memory and compact the SSA
 506    version namespace.  This is used to keep footprint of compiler during
 507    interprocedural optimization.  */
 508 static unsigned int
 509 release_dead_ssa_names (void)
 510 {
 511   unsigned i, j;
 512   int n = vec_safe_length (FREE_SSANAMES (cfun));
 513
 514   /* Now release the freelist.  */
 515   vec_free (FREE_SSANAMES (cfun));
 516
 517   /* And compact the SSA number space.  We make sure to not change the
 518      relative order of SSA versions.  */
 519   for (i = 1, j = 1; i < cfun->gimple_df->ssa_names->length (); ++i)
 520     {
 521       tree name = ssa_name (i);
 522       if (name)
 523         {
 524           if (i != j)
 525             {
 526               SSA_NAME_VERSION (name) = j;
 527               (*cfun->gimple_df->ssa_names)[j] = name;
 528             }
 529           j++;
 530         }
 531     }
 532   cfun->gimple_df->ssa_names->truncate (j);
 533
 534   statistics_counter_event (cfun, "SSA names released", n);
 535   statistics_counter_event (cfun, "SSA name holes removed", i - j);
 536   if (dump_file)
 537     fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
 538              n, n * 100.0 / num_ssa_names, i - j);
 539   return 0;
 540 }
 541
 542 namespace {
 543
 544 const pass_data pass_data_release_ssa_names =
 545 {
 546   GIMPLE_PASS, /* type */
 547   "release_ssa", /* name */
 548   OPTGROUP_NONE, /* optinfo_flags */
 549   false, /* has_gate */
 550   true, /* has_execute */
 551   TV_TREE_SSA_OTHER, /* tv_id */
 552   PROP_ssa, /* properties_required */
 553   0, /* properties_provided */
 554   0, /* properties_destroyed */
 555   TODO_remove_unused_locals, /* todo_flags_start */
 556   0, /* todo_flags_finish */
 557 };
 558
 559 class pass_release_ssa_names : public gimple_opt_pass
 560 {
 561 public:
 562   pass_release_ssa_names (gcc::context *ctxt)
 563     : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
 564   {}
 565
 566   /* opt_pass methods: */
 567   unsigned int execute () { return release_dead_ssa_names (); }
 568
 569 }; // class pass_release_ssa_names
 570
 571 } // anon namespace
 572
 573 gimple_opt_pass *
 574 make_pass_release_ssa_names (gcc::context *ctxt)
 575 {
 576   return new pass_release_ssa_names (ctxt);
 577 }