gcc/tree-ssanames.c

   1 /* Generic routines for manipulating SSA_NAME expressions
   2    Copyright (C) 2003-2016 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 "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "tree-pass.h"
  27 #include "ssa.h"
  28 #include "gimple-iterator.h"
  29 #include "stor-layout.h"
  30 #include "tree-into-ssa.h"
  31 #include "tree-ssa.h"
  32
  33 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
  34    many of which may be thrown away shortly after their creation if jumps
  35    were threaded through PHI nodes.
  36
  37    While our garbage collection mechanisms will handle this situation, it
  38    is extremely wasteful to create nodes and throw them away, especially
  39    when the nodes can be reused.
  40
  41    For PR 8361, we can significantly reduce the number of nodes allocated
  42    and thus the total amount of memory allocated by managing SSA_NAMEs a
  43    little.  This additionally helps reduce the amount of work done by the
  44    garbage collector.  Similar results have been seen on a wider variety
  45    of tests (such as the compiler itself).
  46
  47    Right now we maintain our free list on a per-function basis.  It may
  48    or may not make sense to maintain the free list for the duration of
  49    a compilation unit.
  50
  51    External code should rely solely upon HIGHEST_SSA_VERSION and the
  52    externally defined functions.  External code should not know about
  53    the details of the free list management.
  54
  55    External code should also not assume the version number on nodes is
  56    monotonically increasing.  We reuse the version number when we
  57    reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
  58    more compact.  */
  59
  60
  61 /* Version numbers with special meanings.  We start allocating new version
  62    numbers after the special ones.  */
  63 #define UNUSED_NAME_VERSION 0
  64
  65 unsigned int ssa_name_nodes_reused;
  66 unsigned int ssa_name_nodes_created;
  67
  68 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
  69 #define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue
  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   FREE_SSANAMES_QUEUE (fn) = NULL;
  93
  94   fn->gimple_df->ssa_renaming_needed = 0;
  95   fn->gimple_df->rename_vops = 0;
  96 }
  97
  98 /* Finalize management of SSA_NAMEs.  */
  99
 100 void
 101 fini_ssanames (struct function *fn)
 102 {
 103   vec_free (SSANAMES (fn));
 104   vec_free (FREE_SSANAMES (fn));
 105   vec_free (FREE_SSANAMES_QUEUE (fn));
 106 }
 107
 108 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
 109
 110 void
 111 ssanames_print_statistics (void)
 112 {
 113   fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
 114   fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
 115 }
 116
 117 /* Verify the state of the SSA_NAME lists.
 118
 119    There must be no duplicates on the free list.
 120    Every name on the free list must be marked as on the free list.
 121    Any name on the free list must not appear in the IL.
 122    No names can be leaked.  */
 123
 124 DEBUG_FUNCTION void
 125 verify_ssaname_freelists (struct function *fun)
 126 {
 127   if (!gimple_in_ssa_p (fun))
 128     return;
 129
 130   bitmap names_in_il = BITMAP_ALLOC (NULL);
 131
 132   /* Walk the entire IL noting every SSA_NAME we see.  */
 133   basic_block bb;
 134   FOR_EACH_BB_FN (bb, fun)
 135     {
 136       tree t;
 137       /* First note the result and arguments of PHI nodes.  */
 138       for (gphi_iterator gsi = gsi_start_phis (bb);
 139            !gsi_end_p (gsi);
 140            gsi_next (&gsi))
 141         {
 142           gphi *phi = gsi.phi ();
 143           t = gimple_phi_result (phi);
 144           bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
 145
 146           for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
 147             {
 148               t = gimple_phi_arg_def (phi, i);
 149               if (TREE_CODE (t) == SSA_NAME)
 150                 bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
 151             }
 152         }
 153
 154       /* Then note the operands of each statement.  */
 155       for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 156            !gsi_end_p (gsi);
 157            gsi_next (&gsi))
 158         {
 159           ssa_op_iter iter;
 160           gimple *stmt = gsi_stmt (gsi);
 161           FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS)
 162             bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
 163         }
 164     }
 165
 166   /* Now walk the free list noting what we find there and verifying
 167      there are no duplicates.  */
 168   bitmap names_in_freelists = BITMAP_ALLOC (NULL);
 169   if (FREE_SSANAMES (fun))
 170     {
 171       for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++)
 172         {
 173           tree t = (*FREE_SSANAMES (fun))[i];
 174
 175           /* Verify that the name is marked as being in the free list.  */
 176           gcc_assert (SSA_NAME_IN_FREE_LIST (t));
 177
 178           /* Verify the name has not already appeared in the free list and
 179              note it in the list of names found in the free list.  */
 180           gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
 181           bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
 182         }
 183     }
 184
 185   /* Similarly for the names in the pending free list.  */
 186   if (FREE_SSANAMES_QUEUE (fun))
 187     {
 188       for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++)
 189         {
 190           tree t = (*FREE_SSANAMES_QUEUE (fun))[i];
 191
 192           /* Verify that the name is marked as being in the free list.  */
 193           gcc_assert (SSA_NAME_IN_FREE_LIST (t));
 194
 195           /* Verify the name has not already appeared in the free list and
 196              note it in the list of names found in the free list.  */
 197           gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
 198           bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
 199         }
 200     }
 201
 202   /* If any name appears in both the IL and the freelists, then
 203      something horrible has happened.  */
 204   bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists);
 205   gcc_assert (!intersect_p);
 206
 207   /* Names can be queued up for release if there is an ssa update
 208      pending.  Pretend we saw them in the IL.  */
 209   if (names_to_release)
 210     bitmap_ior_into (names_in_il, names_to_release);
 211
 212   /* Function splitting can "lose" SSA_NAMEs in an effort to ensure that
 213      debug/non-debug compilations have the same SSA_NAMEs.  So for each
 214      lost SSA_NAME, see if it's likely one from that wart.  These will always
 215      be marked as default definitions.  So we loosely assume that anything
 216      marked as a default definition isn't leaked by pretending they are
 217      in the IL.  */
 218   for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++)
 219     if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
 220       bitmap_set_bit (names_in_il, i);
 221
 222   unsigned int i;
 223   bitmap_iterator bi;
 224   bitmap all_names = BITMAP_ALLOC (NULL);
 225   bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1);
 226   bitmap_ior_into (names_in_il, names_in_freelists);
 227
 228   /* Any name not mentioned in the IL and not in the feelists
 229      has been leaked.  */
 230   EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il,
 231                                  UNUSED_NAME_VERSION + 1, i, bi)
 232     gcc_assert (!ssa_name (i));
 233
 234   BITMAP_FREE (all_names);
 235   BITMAP_FREE (names_in_freelists);
 236   BITMAP_FREE (names_in_il);
 237 }
 238
 239 /* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
 240
 241    We do not, but should have a mode to verify the state of the SSA_NAMEs
 242    lists.  In particular at this point every name must be in the IL,
 243    on the free list or in the queue.  Anything else is an error.  */
 244
 245 void
 246 flush_ssaname_freelist (void)
 247 {
 248   vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
 249   vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
 250 }
 251
 252 /* Return an SSA_NAME node for variable VAR defined in statement STMT
 253    in function FN.  STMT may be an empty statement for artificial
 254    references (e.g., default definitions created when a variable is
 255    used without a preceding definition).  */
 256
 257 tree
 258 make_ssa_name_fn (struct function *fn, tree var, gimple *stmt)
 259 {
 260   tree t;
 261   use_operand_p imm;
 262
 263   gcc_assert (TREE_CODE (var) == VAR_DECL
 264               || TREE_CODE (var) == PARM_DECL
 265               || TREE_CODE (var) == RESULT_DECL
 266               || (TYPE_P (var) && is_gimple_reg_type (var)));
 267
 268   /* If our free list has an element, then use it.  */
 269   if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
 270     {
 271       t = FREE_SSANAMES (fn)->pop ();
 272       ssa_name_nodes_reused++;
 273
 274       /* The node was cleared out when we put it on the free list, so
 275          there is no need to do so again here.  */
 276       gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
 277       (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
 278     }
 279   else
 280     {
 281       t = make_node (SSA_NAME);
 282       SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
 283       vec_safe_push (SSANAMES (fn), t);
 284       ssa_name_nodes_created++;
 285     }
 286
 287   if (TYPE_P (var))
 288     {
 289       TREE_TYPE (t) = TYPE_MAIN_VARIANT (var);
 290       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
 291     }
 292   else
 293     {
 294       TREE_TYPE (t) = TREE_TYPE (var);
 295       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
 296     }
 297   SSA_NAME_DEF_STMT (t) = stmt;
 298   if (POINTER_TYPE_P (TREE_TYPE (t)))
 299     SSA_NAME_PTR_INFO (t) = NULL;
 300   else
 301     SSA_NAME_RANGE_INFO (t) = NULL;
 302
 303   SSA_NAME_IN_FREE_LIST (t) = 0;
 304   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
 305   imm = &(SSA_NAME_IMM_USE_NODE (t));
 306   imm->use = NULL;
 307   imm->prev = imm;
 308   imm->next = imm;
 309   imm->loc.ssa_name = t;
 310
 311   return t;
 312 }
 313
 314 /* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME.  */
 315
 316 void
 317 set_range_info (tree name, enum value_range_type range_type,
 318                 const wide_int_ref &min, const wide_int_ref &max)
 319 {
 320   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 321   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
 322   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 323   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 324
 325   /* Allocate if not available.  */
 326   if (ri == NULL)
 327     {
 328       size_t size = (sizeof (range_info_def)
 329                      + trailing_wide_ints <3>::extra_size (precision));
 330       ri = static_cast<range_info_def *> (ggc_internal_alloc (size));
 331       ri->ints.set_precision (precision);
 332       SSA_NAME_RANGE_INFO (name) = ri;
 333       ri->set_nonzero_bits (wi::shwi (-1, precision));
 334     }
 335
 336   /* Record the range type.  */
 337   if (SSA_NAME_RANGE_TYPE (name) != range_type)
 338     SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
 339
 340   /* Set the values.  */
 341   ri->set_min (min);
 342   ri->set_max (max);
 343
 344   /* If it is a range, try to improve nonzero_bits from the min/max.  */
 345   if (range_type == VR_RANGE)
 346     {
 347       wide_int xorv = ri->get_min () ^ ri->get_max ();
 348       if (xorv != 0)
 349         xorv = wi::mask (precision - wi::clz (xorv), false, precision);
 350       ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv));
 351     }
 352 }
 353
 354
 355 /* Gets range information MIN, MAX and returns enum value_range_type
 356    corresponding to tree ssa_name NAME.  enum value_range_type returned
 357    is used to determine if MIN and MAX are valid values.  */
 358
 359 enum value_range_type
 360 get_range_info (const_tree name, wide_int *min, wide_int *max)
 361 {
 362   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 363   gcc_assert (min && max);
 364   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 365
 366   /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
 367      with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.  */
 368   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 369               > 2 * HOST_BITS_PER_WIDE_INT))
 370     return VR_VARYING;
 371
 372   *min = ri->get_min ();
 373   *max = ri->get_max ();
 374   return SSA_NAME_RANGE_TYPE (name);
 375 }
 376
 377 /* Change non-zero bits bitmask of NAME.  */
 378
 379 void
 380 set_nonzero_bits (tree name, const wide_int_ref &mask)
 381 {
 382   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 383   if (SSA_NAME_RANGE_INFO (name) == NULL)
 384     set_range_info (name, VR_RANGE,
 385                     TYPE_MIN_VALUE (TREE_TYPE (name)),
 386                     TYPE_MAX_VALUE (TREE_TYPE (name)));
 387   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 388   ri->set_nonzero_bits (mask);
 389 }
 390
 391 /* Return a widest_int with potentially non-zero bits in SSA_NAME
 392    NAME, or -1 if unknown.  */
 393
 394 wide_int
 395 get_nonzero_bits (const_tree name)
 396 {
 397   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 398   if (POINTER_TYPE_P (TREE_TYPE (name)))
 399     {
 400       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 401       if (pi && pi->align)
 402         return wi::shwi (-(HOST_WIDE_INT) pi->align
 403                          | (HOST_WIDE_INT) pi->misalign, precision);
 404       return wi::shwi (-1, precision);
 405     }
 406
 407   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 408   if (!ri)
 409     return wi::shwi (-1, precision);
 410
 411   return ri->get_nonzero_bits ();
 412 }
 413
 414 /* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false
 415    otherwise.
 416
 417    This can be because it is a boolean type, any unsigned integral
 418    type with a single bit of precision, or has known range of [0..1]
 419    via VRP analysis.  */
 420
 421 bool
 422 ssa_name_has_boolean_range (tree op)
 423 {
 424   gcc_assert (TREE_CODE (op) == SSA_NAME);
 425
 426   /* Boolean types always have a range [0..1].  */
 427   if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE)
 428     return true;
 429
 430   /* An integral type with a single bit of precision.  */
 431   if (INTEGRAL_TYPE_P (TREE_TYPE (op))
 432       && TYPE_UNSIGNED (TREE_TYPE (op))
 433       && TYPE_PRECISION (TREE_TYPE (op)) == 1)
 434     return true;
 435
 436   /* An integral type with more precision, but the object
 437      only takes on values [0..1] as determined by VRP
 438      analysis.  */
 439   if (INTEGRAL_TYPE_P (TREE_TYPE (op))
 440       && (TYPE_PRECISION (TREE_TYPE (op)) > 1)
 441       && wi::eq_p (get_nonzero_bits (op), 1))
 442     return true;
 443
 444   return false;
 445 }
 446
 447 /* We no longer need the SSA_NAME expression VAR, release it so that
 448    it may be reused.
 449
 450    Note it is assumed that no calls to make_ssa_name will be made
 451    until all uses of the ssa name are released and that the only
 452    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 453    other fields must be assumed clobbered.  */
 454
 455 void
 456 release_ssa_name_fn (struct function *fn, tree var)
 457 {
 458   if (!var)
 459     return;
 460
 461   /* Never release the default definition for a symbol.  It's a
 462      special SSA name that should always exist once it's created.  */
 463   if (SSA_NAME_IS_DEFAULT_DEF (var))
 464     return;
 465
 466   /* If VAR has been registered for SSA updating, don't remove it.
 467      After update_ssa has run, the name will be released.  */
 468   if (name_registered_for_update_p (var))
 469     {
 470       release_ssa_name_after_update_ssa (var);
 471       return;
 472     }
 473
 474   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 475      However, it should only end up on our free list one time.   We
 476      keep a status bit in the SSA_NAME node itself to indicate it has
 477      been put on the free list.
 478
 479      Note that once on the freelist you can not reference the SSA_NAME's
 480      defining statement.  */
 481   if (! SSA_NAME_IN_FREE_LIST (var))
 482     {
 483       tree saved_ssa_name_var = SSA_NAME_VAR (var);
 484       int saved_ssa_name_version = SSA_NAME_VERSION (var);
 485       use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
 486
 487       if (MAY_HAVE_DEBUG_STMTS)
 488         insert_debug_temp_for_var_def (NULL, var);
 489
 490       if (flag_checking)
 491         verify_imm_links (stderr, var);
 492       while (imm->next != imm)
 493         delink_imm_use (imm->next);
 494
 495       (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
 496       memset (var, 0, tree_size (var));
 497
 498       imm->prev = imm;
 499       imm->next = imm;
 500       imm->loc.ssa_name = var;
 501
 502       /* First put back the right tree node so that the tree checking
 503          macros do not complain.  */
 504       TREE_SET_CODE (var, SSA_NAME);
 505
 506       /* Restore the version number.  */
 507       SSA_NAME_VERSION (var) = saved_ssa_name_version;
 508
 509       /* Hopefully this can go away once we have the new incremental
 510          SSA updating code installed.  */
 511       SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
 512
 513       /* Note this SSA_NAME is now in the first list.  */
 514       SSA_NAME_IN_FREE_LIST (var) = 1;
 515
 516       /* And finally queue it so that it will be put on the free list.  */
 517       vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
 518     }
 519 }
 520
 521 /* If the alignment of the pointer described by PI is known, return true and
 522    store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
 523    respectively.  Otherwise return false.  */
 524
 525 bool
 526 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
 527                         unsigned int *misalignp)
 528 {
 529   if (pi->align)
 530     {
 531       *alignp = pi->align;
 532       *misalignp = pi->misalign;
 533       return true;
 534     }
 535   else
 536     return false;
 537 }
 538
 539 /* State that the pointer described by PI has unknown alignment.  */
 540
 541 void
 542 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
 543 {
 544   pi->align = 0;
 545   pi->misalign = 0;
 546 }
 547
 548 /* Store the power-of-two byte alignment and the deviation from that
 549    alignment of pointer described by PI to ALIOGN and MISALIGN
 550    respectively.  */
 551
 552 void
 553 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
 554                             unsigned int misalign)
 555 {
 556   gcc_checking_assert (align != 0);
 557   gcc_assert ((align & (align - 1)) == 0);
 558   gcc_assert ((misalign & ~(align - 1)) == 0);
 559
 560   pi->align = align;
 561   pi->misalign = misalign;
 562 }
 563
 564 /* If pointer described by PI has known alignment, increase its known
 565    misalignment by INCREMENT modulo its current alignment.  */
 566
 567 void
 568 adjust_ptr_info_misalignment (struct ptr_info_def *pi,
 569                               unsigned int increment)
 570 {
 571   if (pi->align != 0)
 572     {
 573       pi->misalign += increment;
 574       pi->misalign &= (pi->align - 1);
 575     }
 576 }
 577
 578 /* Return the alias information associated with pointer T.  It creates a
 579    new instance if none existed.  */
 580
 581 struct ptr_info_def *
 582 get_ptr_info (tree t)
 583 {
 584   struct ptr_info_def *pi;
 585
 586   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 587
 588   pi = SSA_NAME_PTR_INFO (t);
 589   if (pi == NULL)
 590     {
 591       pi = ggc_cleared_alloc<ptr_info_def> ();
 592       pt_solution_reset (&pi->pt);
 593       mark_ptr_info_alignment_unknown (pi);
 594       SSA_NAME_PTR_INFO (t) = pi;
 595     }
 596
 597   return pi;
 598 }
 599
 600
 601 /* Creates a new SSA name using the template NAME tobe defined by
 602    statement STMT in function FN.  */
 603
 604 tree
 605 copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
 606 {
 607   tree new_name;
 608
 609   if (SSA_NAME_VAR (name))
 610     new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
 611   else
 612     {
 613       new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
 614       SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
 615     }
 616
 617   return new_name;
 618 }
 619
 620
 621 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
 622    the SSA name NAME.  */
 623
 624 void
 625 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
 626 {
 627   struct ptr_info_def *new_ptr_info;
 628
 629   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 630   gcc_assert (!SSA_NAME_PTR_INFO (name));
 631
 632   if (!ptr_info)
 633     return;
 634
 635   new_ptr_info = ggc_alloc<ptr_info_def> ();
 636   *new_ptr_info = *ptr_info;
 637
 638   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 639 }
 640
 641 /* Creates a duplicate of the range_info_def at RANGE_INFO of type
 642    RANGE_TYPE for use by the SSA name NAME.  */
 643 void
 644 duplicate_ssa_name_range_info (tree name, enum value_range_type range_type,
 645                                struct range_info_def *range_info)
 646 {
 647   struct range_info_def *new_range_info;
 648
 649   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 650   gcc_assert (!SSA_NAME_RANGE_INFO (name));
 651
 652   if (!range_info)
 653     return;
 654
 655   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 656   size_t size = (sizeof (range_info_def)
 657                  + trailing_wide_ints <3>::extra_size (precision));
 658   new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size));
 659   memcpy (new_range_info, range_info, size);
 660
 661   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
 662   SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
 663   SSA_NAME_RANGE_INFO (name) = new_range_info;
 664 }
 665
 666
 667
 668 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
 669    in function FN.  */
 670
 671 tree
 672 duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
 673 {
 674   tree new_name = copy_ssa_name_fn (fn, name, stmt);
 675   if (POINTER_TYPE_P (TREE_TYPE (name)))
 676     {
 677       struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 678
 679       if (old_ptr_info)
 680         duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
 681     }
 682   else
 683     {
 684       struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 685
 686       if (old_range_info)
 687         duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
 688                                        old_range_info);
 689     }
 690
 691   return new_name;
 692 }
 693
 694
 695 /* Reset all flow sensitive data on NAME such as range-info, nonzero
 696    bits and alignment.  */
 697
 698 void
 699 reset_flow_sensitive_info (tree name)
 700 {
 701   if (POINTER_TYPE_P (TREE_TYPE (name)))
 702     {
 703       /* points-to info is not flow-sensitive.  */
 704       if (SSA_NAME_PTR_INFO (name))
 705         mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
 706     }
 707   else
 708     SSA_NAME_RANGE_INFO (name) = NULL;
 709 }
 710
 711 /* Clear all flow sensitive data from all statements and PHI definitions
 712    in BB.  */
 713
 714 void
 715 reset_flow_sensitive_info_in_bb (basic_block bb)
 716 {
 717   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
 718        gsi_next (&gsi))
 719     {
 720       gimple *stmt = gsi_stmt (gsi);
 721       ssa_op_iter i;
 722       tree op;
 723       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
 724         reset_flow_sensitive_info (op);
 725     }
 726
 727   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
 728        gsi_next (&gsi))
 729     {
 730       tree phi_def = gimple_phi_result (gsi.phi ());
 731       reset_flow_sensitive_info (phi_def);
 732     }
 733 }
 734
 735 /* Release all the SSA_NAMEs created by STMT.  */
 736
 737 void
 738 release_defs (gimple *stmt)
 739 {
 740   tree def;
 741   ssa_op_iter iter;
 742
 743   /* Make sure that we are in SSA.  Otherwise, operand cache may point
 744      to garbage.  */
 745   gcc_assert (gimple_in_ssa_p (cfun));
 746
 747   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 748     if (TREE_CODE (def) == SSA_NAME)
 749       release_ssa_name (def);
 750 }
 751
 752
 753 /* Replace the symbol associated with SSA_NAME with SYM.  */
 754
 755 void
 756 replace_ssa_name_symbol (tree ssa_name, tree sym)
 757 {
 758   SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
 759   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 760 }
 761
 762 /* Release the vector of free SSA_NAMEs and compact the vector of SSA_NAMEs
 763    that are live.  */
 764
 765 static void
 766 release_free_names_and_compact_live_names (function *fun)
 767 {
 768   unsigned i, j;
 769   int n = vec_safe_length (FREE_SSANAMES (fun));
 770
 771   /* Now release the freelist.  */
 772   vec_free (FREE_SSANAMES (fun));
 773
 774   /* And compact the SSA number space.  We make sure to not change the
 775      relative order of SSA versions.  */
 776   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
 777     {
 778       tree name = ssa_name (i);
 779       if (name)
 780         {
 781           if (i != j)
 782             {
 783               SSA_NAME_VERSION (name) = j;
 784               (*fun->gimple_df->ssa_names)[j] = name;
 785             }
 786           j++;
 787         }
 788     }
 789   fun->gimple_df->ssa_names->truncate (j);
 790
 791   statistics_counter_event (fun, "SSA names released", n);
 792   statistics_counter_event (fun, "SSA name holes removed", i - j);
 793   if (dump_file)
 794     fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
 795              n, n * 100.0 / num_ssa_names, i - j);
 796 }
 797
 798 /* Return SSA names that are unused to GGC memory and compact the SSA
 799    version namespace.  This is used to keep footprint of compiler during
 800    interprocedural optimization.  */
 801
 802 namespace {
 803
 804 const pass_data pass_data_release_ssa_names =
 805 {
 806   GIMPLE_PASS, /* type */
 807   "release_ssa", /* name */
 808   OPTGROUP_NONE, /* optinfo_flags */
 809   TV_TREE_SSA_OTHER, /* tv_id */
 810   PROP_ssa, /* properties_required */
 811   0, /* properties_provided */
 812   0, /* properties_destroyed */
 813   TODO_remove_unused_locals, /* todo_flags_start */
 814   0, /* todo_flags_finish */
 815 };
 816
 817 class pass_release_ssa_names : public gimple_opt_pass
 818 {
 819 public:
 820   pass_release_ssa_names (gcc::context *ctxt)
 821     : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
 822   {}
 823
 824   /* opt_pass methods: */
 825   virtual unsigned int execute (function *);
 826
 827 }; // class pass_release_ssa_names
 828
 829 unsigned int
 830 pass_release_ssa_names::execute (function *fun)
 831 {
 832   release_free_names_and_compact_live_names (fun);
 833   return 0;
 834 }
 835
 836 } // anon namespace
 837
 838 gimple_opt_pass *
 839 make_pass_release_ssa_names (gcc::context *ctxt)
 840 {
 841   return new pass_release_ssa_names (ctxt);
 842 }