gcc/tree-ssanames.c

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